JP5134281B2 - Distributed information generating apparatus, secret information restoring apparatus, shared information generating method, secret information restoring method, and program - Google Patents

Description

  The present invention relates to a shared information generating apparatus, a secret information restoring apparatus, a shared information generating method, a secret information restoring method, and a program for protecting confidential information.

  In recent years, with the increasing importance of information security, measures against theft and loss of information have become important issues. For this reason, the (k, n) threshold secret sharing method as shown in Non-Patent Document 1 is attracting attention as a method for simultaneously realizing confidentiality of information and avoidance of risk due to loss. Here, (k, n) threshold secret sharing means that secret information is distributed into n pieces of shared information, and if any k pieces of shared information are gathered, it can be restored.

  However, the (k, n) threshold secret sharing method shown in Non-Patent Document 1 needs to process a (k−1) -order polynomial when distributing and restoring information, and the amount of calculation is enormous. Become. Therefore, as shown in Non-Patent Document 2, a (2, n) threshold secret sharing method that can be distributed and restored at high speed using exclusive OR (XOR) has been proposed.

On the other hand, as a threshold secret sharing method using an XOR other than the threshold 2, a non-patent document 3 proposes a (3, n) threshold secret sharing method. However, a threshold secret sharing method using XOR with a threshold value of 4 or higher has not been proposed yet. Also, Non-Patent Document 4 proposes a (k, n) threshold secret sharing method that can be distributed and restored at high speed using XOR or additive operation. Compared to the data length of the secret information, the data of the distributed information The length is several times larger and the efficiency is poor. Further, Patent Document 1 proposes a (k, n) threshold secret sharing method, but secret information may be restored even when a smaller number of pieces of shared information are available. It does not satisfy generality as a secret sharing method.
A. Shamir, “How to Share a Secret,” Commun. ACM, vol. 22 no. 11 pp. 612-613, 1979. Yoshihiro Fujii, Minako Tada, Norikazu Hosaka, Takaya Tochikubo, Takehisa Kato, “Structure Method of Fast (2, n) Threshold Method and Application to System,” CSS 2005 Proceedings, 2005. Satoshi Kurihara, Atsushi Kiyomoto, Kazuhide Fukushima, Toshiaki Tanaka, “(3, n) Threshold Secret Sharing Method Using XOR, SCIS 2007 Proceedings, 2007. Nobuyuki Shiina, Ken Okamoto, Eiji Okamoto, “How to raise from 1-out-of-n proof to k-out-of-n proof” SCIS 2004 Proceedings, 2004. JP 2006-18850 A

  As described above, the (k, n) threshold secret sharing method disclosed in Non-Patent Document 1 has a problem that the amount of calculation becomes enormous. Further, the method shown in Non-Patent Document 4 has a problem that the data length of the distributed information is several times larger than that of the secret information. Thus, there is a demand for an efficient threshold secret sharing method that enables high-speed computation using XOR and that the data length of the shared information is equal to the data length of the secret information. The current (k, n) threshold secret sharing scheme has not yet been proposed.

  Therefore, the present invention has been made in view of the above-described problems, and high-speed calculation is possible by using XOR. The data lengths of secret information and shared information are equal, and general (k, n It is an object of the present invention to provide a shared information generating device, a secret information restoring device, a shared information generating method, a secret information restoring method, and a program that can constitute a threshold secret sharing method.

In order to solve the above-described problems, the present invention proposes the following matters.
(1) The present invention relates to a dividing unit that divides k pieces of shared information into k (n _p −1) pieces of partial shared information (n _p is a prime number satisfying n _p ≧ n with respect to the number of distributed n), and the division A conversion means for converting the partial dispersion information into a vector representation, a matrix generation means for generating a matrix based on the converted vector, and performing a matrix operation on the generated matrix to obtain an exclusive to the partial dispersion information A matrix operation means for obtaining a combination of logical sum (XOR) operations, a restoration means for restoring the partial secret information by applying the obtained combination of XOR operations to the partial shared information, and connecting the restored partial secret information Thus, there is proposed a secret information restoring apparatus comprising a connecting means for generating the original secret information K.

(2) The present invention includes a dividing unit that divides the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n for the distributed number n), and dummy partial secret information XOR using dummy information generating means for generating, k-1 random number generating means for generating mutually independent random numbers R, dummy partial secret information and partial secret information, and random numbers A partial shared information generating means for generating partial shared information by calculation, a connecting means for connecting the partial shared information to generate n pieces of shared information, and a partial distributed that constitutes the shared information in the generated shared information Proposed is a distributed information generating apparatus comprising header information adding means for adding header information obtained by converting information into a vector representation.

  (3) The present invention provides header information acquisition means for separating and acquiring header information from information obtained by adding header information obtained by converting partial shared information constituting the shared information into vector representation to shared information, and the acquired header Based on the information, a matrix generating unit that generates a matrix, a dividing unit that divides the shared information into partial shared information, and a matrix operation on the generated matrix are executed to perform exclusive OR ( XOR) matrix operation means for obtaining a combination of operations, a combination means for applying the obtained combination of XOR operations to the partial shared information to restore partial secret information, and connecting the restored partial secret information to obtain the original A secret information restoration apparatus characterized by comprising a connecting means for generating the secret information K.

(4) The present invention provides a dividing means for dividing the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n), and dummy partial secret information XOR using dummy information generating means for generating, k-1 random number generating means for generating mutually independent random numbers R, dummy partial secret information and partial secret information, and random numbers By calculation, partial shared information generating means for generating partial shared information, header information adding means for adding header information obtained by converting the partial shared information into a vector representation to the generated partial shared information, and the header information are added. And a connecting means for generating n pieces of shared information by connecting the partial shared information.

  (5) The present invention provides a dividing unit that divides shared information obtained by concatenating partial shared information to which header information obtained by converting partial shared information into a vector representation is added into partial shared information to which header information is added; Matrix generating means for generating a matrix based on the partial shared information to which the header information is added, a calculating means for executing a matrix operation on the generated matrix and calculating partial secret information accompanied by header information, and A secret information restoration apparatus comprising: removal means for removing the header information from a calculation result; and connection means for generating secret information K by connecting the partial secret information from which the header information has been removed. is suggesting.

(6) The present invention includes a first step of dividing k pieces of distributed information into k (n _p −1) pieces of partial shared information (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n); A second step of converting the divided partial dispersion information into a vector representation; a third step of generating a matrix based on the converted vector; and performing a matrix operation on the generated matrix, A fourth step of obtaining a combination of exclusive OR (XOR) operations on the shared information, and a fifth step of restoring the partial secret information by applying the obtained combination of XOR operations to the partial shared information; And a sixth step of generating the original secret information K by concatenating the restored partial secret information, and proposes a secret information restoration method characterized by comprising:

(7) The present invention generates the first step of dividing the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n) and A second step of generating partial shared information by exclusive OR (XOR) operation using dummy partial secret information and partial secret information and a random number, and connecting the partial shared information to n distributed A third step of generating information; and a third step of adding header information obtained by converting partial shared information constituting the shared information into a vector representation to the generated shared information. A distributed information generation method is proposed.

  (8) The present invention includes a first step of separating and acquiring header information from information obtained by adding header information obtained by converting partial shared information constituting the shared information into vector representation to shared information, and the acquired header A second step of generating a matrix based on the information; a third step of dividing the shared information into partial shared information; and performing a matrix operation on the generated matrix to obtain an exclusive to the partial shared information A third step of obtaining a combination of logical sum (XOR) operations, a fourth step of applying the obtained combination of XOR operations to the partial shared information to restore partial secret information, and the restored partial secret And a fifth step of generating the original secret information K by concatenating the information, and proposes a secret information restoration method characterized by comprising:

(9) The present invention generates the first step of dividing the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n for the distributed number n) and A second step of generating partial shared information by exclusive OR (XOR) operation using dummy partial secret information and partial secret information and a random number, and the partial shared information is added to the generated partial shared information. A third step of adding header information converted into a vector representation; and a fourth step of generating n pieces of shared information by concatenating the partial shared information to which the header information is added. The distributed information generation method is proposed.

  (10) The present invention includes a first step of dividing the shared information obtained by concatenating the partial shared information to which the header information obtained by converting the partial shared information into the vector representation into the partial shared information to which the header information is added; A second step of generating a matrix based on the partial shared information to which the divided header information is added; and a third step of performing a matrix operation on the generated matrix and restoring partial secret information accompanied by the header information A fourth step of removing the header information from the calculation result, and a fifth step of generating the secret information K by concatenating the partial secret information from which the header information has been removed. A secret information restoration method is proposed.

(11) According to the present invention, a computer first divides k pieces of distributed information into k (n _p −1) pieces of partial shared information (n _p is a prime number satisfying n _p ≧ n for the distributed number n). A step, a second step of converting the divided partial dispersion information into a vector representation, a third step of generating a matrix based on the converted vector, and performing a matrix operation on the generated matrix A fourth step of obtaining a combination of exclusive OR (XOR) operations on the partial shared information, and applying a combination of the obtained XOR operations to the partial shared information to restore partial secret information. A program for executing the step and the sixth step of generating the original secret information K by concatenating the restored partial secret information is proposed.

(12) The present invention includes a first step in which the computer divides the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n for the distributed number n); A second step of generating partial shared information by exclusive OR (XOR) operation using the generated dummy partial secret information and partial secret information and a random number, and connecting the partial shared information to n A third step of generating a piece of shared information, and a third step of adding header information obtained by converting partial shared information constituting the shared information into a vector representation to the generated shared information Propose a program.

  (13) The present invention includes a first step of separating and obtaining header information from information obtained by adding header information obtained by converting partial shared information constituting the shared information into vector representation to the shared information. Based on the acquired header information, a second step of generating a matrix, a third step of dividing the distribution information into partial distribution information, and performing a matrix operation on the generated matrix, the partial distribution information A third step of finding a combination of exclusive OR (XOR) operations on the fourth, a fourth step of restoring the partial secret information by applying the obtained combination of XOR operations to the partial shared information, and the restoration A program for executing the fifth step of generating the original secret information K by concatenating the partial secret information is proposed.

(14) The present invention includes a first step in which the computer divides the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n for the distributed number n). A second step of generating partial shared information by exclusive OR (XOR) operation using the generated dummy partial secret information and partial secret information and random numbers, and the generated partial shared information And executing a third step of adding header information obtained by converting the shared information into a vector representation and a fourth step of generating n pieces of shared information by concatenating the partial shared information to which the header information is added. A program for this is proposed.

  (15) In the first aspect of the present invention, the computer divides the shared information obtained by concatenating the partial shared information added with the header information obtained by converting the partial shared information into the vector representation into the partial shared information added with the header information. And a second step of generating a matrix based on the partial shared information to which the divided header information is added, and a matrix operation on the generated matrix is executed to restore the partial secret information accompanied by the header information A third step of removing the header information from the calculation result, and a fifth step of generating the secret information K by concatenating the partial secret information from which the header information has been removed. A program to execute it is proposed.

  According to the present invention, a general (k, n) threshold secret sharing scheme can be configured using exclusive OR (XOR). For this reason, since dispersion and restoration can be performed by XOR operation, there is an effect that high-speed processing becomes possible.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

<First Embodiment>
In this embodiment, secret information is distributed and restored by the (k, n) threshold method. FIG. 1 is a functional block diagram showing an overview of a distributed information generation and distribution apparatus according to this embodiment.

In FIG. 1, secret information K is sent to a divider 11 and divided into (n _p −1) pieces of partial secret information K _q . Further, dummy partial secret information K ₀ is generated by the dummy information generator 12. The dummy partial secret information K ₀ and the partial secret information K _q are sent to the partial shared information generator 13.

  The random number generator 14 generates random numbers R that are independent of each other. Then, k−1 similar random number generators 14 are provided. The random number R from the random number generator 14 is sent to the partial shared information generator 13.

The partial shared information generator 13 uses the dummy partial secret information K ₀ and (n _p −1) pieces of partial secret information K _q and the random number R from the random number generator 14 to perform an exclusive OR (XOR). Partial distribution information is generated by the calculation. The partial shared information is linked by the coupler 16 to generate n pieces of shared information S _i . The shared information S _i is securely transmitted to the administrator P _i by the transmission device 17.

In the present embodiment, the secret information K can be distributed to the distributed information S _i of the distribution number n by the general (k, n) threshold secret distribution method of the distribution number n. In addition, since the operation necessary for distribution is exclusive OR (XOR), high-speed operation can be performed.

In the present invention, it is necessary to equally divide the secret information into (n _p −1) pieces. However, n _p is a prime number satisfying n _p ≧ n for the dispersion number n. Therefore, when the desired variance number n is a composite number, by using n pieces of variance information of the (k, n _p ) threshold method using prime numbers n _p satisfying n _p > n, (k, n) Realize the threshold method.

  The threshold secret sharing method of this embodiment will be described in detail. First, prior to describing the threshold secret sharing method of the present embodiment, operators and symbols used in this specification are defined as follows.

  First, the distributed processing method will be described. In the threshold secret sharing method of this embodiment, the (k, n) threshold secret sharing method is realized by performing distributed processing according to the following procedure.

As described above, in the present invention, it is necessary to equally divide the secret information K into (n _p −1) pieces, and n _p is a prime number that satisfies n _p ≧ n with respect to the number of distributions n. Therefore, when the desired distribution number n is a composite number, by using n pieces of distribution information of (k, n _p ) threshold secret sharing method using prime numbers n _p satisfying n _p > n, ( k, n) Realize the threshold method.

(Step 1)
The secret information K is divided into (n _p −1) pieces of partial secret information K ₁ ,..., K _np−1 for every d bits.

(Step 2)
Dummy partial secret information K ₀ that is a d-bit “0” string is generated.

(Step 3)
Total _{(k-1) n} p -1 pieces of d-bit random number ^{_{R l 0, R l 1,}} ···, R np-2 0, R l 1, ···, R np-2 1, ·· R ₀ ^k-2 , R ₁ ^k-2 ,..., R _np-1 ^k-2 are all generated independently.

(Step 4)
The partial distribution information S _{(i, m)} is generated by the XOR operation as follows.

(Step 5)
The partial shared information S _{(i, 0)} ,..., S _{(i, np−2)} is connected to generate the shared information S _i and securely distributed to the manager P _i .

  The configuration table of the partial shared information configured by the above steps is as shown in Table 1. The number of bits distributed to one manager is equal to the number of bits of K.

  Next, the restoration method will be described. Restoration is performed using the decompressor 21 shown in FIG. This is a device with k inputs and 1 output. When k + 1 or more managers gather, distributed information is obtained from any k managers of them and is input to the devices. That is, the partial secret information is restored from the collected partial shared information by the configuration of the partial shared information shown in Table 1. As a result, all partial secret information can be restored by any combination of k pieces of distributed information.

  As shown in FIG. 2, the specific configuration includes a distributed information dividing unit 21, a vector expression converting unit 22, a matrix generating unit 23, a matrix calculating unit 24, a partial secret information restoring unit 25, and a connecting unit 26. It is made up of.

K pieces of _shared information (S _i0 ,..., S _ik-1 ) are input to the _shared information dividing unit 21 and divided into k (n _p −1) pieces of partial shared information. The divided k (n _p −1) pieces of partial dispersion information are converted into vector representations in the vector representation conversion unit 22 and input to the matrix generation unit 23 to generate a matrix. The generated matrix is subjected to matrix calculation in the matrix calculation unit 24 to obtain a combination of exclusive OR (XOR) calculation for partial dispersion information. The partial secret information restoration unit 25 restores the partial secret information based on the calculation result in the matrix calculation unit 24, and the restored partial secret information is connected in the connection unit 26 to generate the secret information K.

Hereinafter, the procedure of the restoration process will be described more specifically. As a premise, k different managers P _i0 ,... P _ik-1 are gathered, and k pieces of distributed information are _designated as S _i0 ,..., S _ik-1 (i _{0 ,.} , I _k-1 are all different from each other).

(Step 1)
Each _shared information S _i0 ,..., S _ik−1 is divided into partial shared information. That is, the following k (n _p −1) pieces of partial dispersion information are obtained.

(Step 2)
All the components of the partial shared information are expressed by k · n _p -2 bit vectors as shown in Equation 6. Equation 6 is a vector expression V _{(it, m)} for the partial dispersion information S _{(it, m)} . Only the portion corresponding to the component (partial secret information, random number) of S _{(it, m)} is “1”, and otherwise “0”. That is, each bit of the vector and each component correspond as follows. Here, K ₀ is dummy information that is a column of “0” of d bits, and therefore does not need to be considered in vector expression.
_{(K 1, K 2, ···} , K np-1, R 0 0, R l 0, ···, R np-2 0, R l 1, ···, R np-1 1, ·· ., R ₀ ^k-2 , R ₁ ^k-2 ,..., R _np-1 ^k-2 )

(Step 3)
A matrix is generated with each row representing a vector representation of the constituent elements related to all partial distribution information. Using this matrix, a vertical vector of k (n _p −1) rows of partial dispersion information on the left side, a binary k (n _p −1) row of vector representation on the right side, and a matrix of k · n _p −2 columns, Equation 7 is obtained as a product of the vertical vector X _{(k, n) of} k · n _p −2 rows.

(Step 4)
Next, the matrix operation using only the XOR operation and the row basic transformation is performed on the right-side matrix of Equation 7, and the left-hand side is transformed to the right-hand side to obtain Equation 8. As a result, the matrix part on the right side is deformed by matrix operation, and the left side indicates a combination of XOR operations for obtaining deformation of the right side. Note that the combination of XOR operations is different for each row on the right side. In this example, Gauss-Jordan elimination is used as a matrix calculation method.

(Step 5)
Further, the XOR operation of the partial dispersion information shown from the first line to the n _p −1 line on the left side of Equation 8 is executed. Thereby, all partial secret information of K ₁ , K ₂ ,..., K _n−1 is obtained corresponding to each row number. In addition to executing the calculation of the left side of Equation 8 after executing a matrix operation to obtain an XOR operation expression, partial distribution information corresponding to the row basic transformation by the XOR operation performed during the execution of the matrix operation It is also possible to sequentially perform the XOR operation. In this case, when the matrix operation is completed, all partial secret information is obtained at the same time.

(Step 6)
All the partial secret information is connected, and the original secret information K is restored.

  Therefore, according to the present embodiment, high-speed computation is possible by using XOR, the data lengths of the secret information and the shared information are equal, and a general (k, n) threshold secret sharing method can be configured.

<Second Embodiment>
In this embodiment, as shown in FIG. 3, by adding the vector representation of the component related to the partial shared information to the generated shared information as header information, even if there is no shared information index or component management table, This is a method that enables restoration of secret information.

  As shown in FIG. 4, the shared information generation apparatus according to the present embodiment is different from the shared information generation apparatus according to the first embodiment in that a header information embedding unit 18 is provided between the coupler 16 and the transmission apparatus 17. Is provided. Here, the header information embedding unit 18 adds, to the shared information, header information obtained by converting the partial shared information constituting the shared information into a vector representation.

A specific processing procedure is to divide the secret information K into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n for the distributed number n), and the generated dummy partial secret information and Partially shared information is generated by exclusive OR (XOR) operation using partial secret information and random numbers. Then, n pieces of shared information are generated by concatenating the partial shared information, and header information obtained by converting the partial shared information constituting this shared information into a vector representation is added to the generated shared information.

  On the other hand, as shown in FIG. 5, the secret information restoring apparatus according to the present embodiment includes a distributed information dividing unit 21, a matrix generating unit 23, a matrix calculating unit 24, a partial secret information restoring unit 25, and a connecting unit 26. And a header information acquisition unit 27.

  Here, the header information acquisition unit 27 separates and acquires the header information from the information obtained by adding the header information obtained by converting the partial shared information constituting the shared information into the vector representation to the shared information. The matrix generation unit 23 generates a matrix based on the header information acquired by the header information acquisition unit 27. The shared information dividing unit 21 divides the shared information from which the header information is removed into partial shared information.

  The matrix operation unit 24 performs a matrix operation on the matrix generated by the matrix generation unit 23 to obtain a combination of exclusive OR (XOR) operations on the partial dispersion information. The partial secret information restoration unit 25 applies the combination of XOR operations obtained by the matrix calculation unit 24 to the partial shared information, and restores the partial secret information. The linking unit 26 generates the original secret information K by linking the partial secret information restored by the partial secret information restoring unit 25.

  A specific processing procedure is to separate header information from information obtained by adding header information obtained by converting partial shared information constituting this shared information into vector representation to shared information, and generate a matrix based on the acquired header information. . Next, the shared information from which the header information is removed is divided into partial shared information, and a matrix operation is performed on the generated matrix to obtain a combination of exclusive OR (XOR) operations on the partial shared information. Then, the obtained combination of XOR operations is applied to the partial shared information to restore the partial secret information, and the restored partial secret information is connected to generate the original secret information K.

  Therefore, according to the present embodiment, by adding the vector representation of the component related to the partial shared information as header information to the generated shared information, the secret information can be stored without the shared information index or the component management table. Restoration can be performed.

<Third Embodiment>
In the present embodiment, as shown in FIG. 6, the distributed information is generated by adding the vector representation of the component as header information to the generated partial shared information. This is a scheme that enables the restoration of secret information even without it.

  As shown in FIG. 8, the shared information generation apparatus according to the present embodiment embeds header information between the partial shared information generator and the coupler 16 in the shared information generation apparatus according to the first embodiment. The configuration is provided with the portion 19. Here, the header information embedding unit 18 adds header information obtained by converting the partial shared information into a vector representation to the partial shared information.

Specifically, the secret information K is divided into (n _p −1) pieces of partial secret information (n _p is a prime number satisfying n _p ≧ n with respect to the distribution number n), and the generated dummy partial secret information and part Partially shared information is generated by an exclusive OR (XOR) operation using secret information and random numbers. Then, header information obtained by converting the partial shared information into a vector representation is added to the generated partial shared information, and the partial shared information to which the header information is added is connected to generate n pieces of shared information.

  On the other hand, as shown in FIG. 9, the secret information restoring apparatus according to the present embodiment includes a shared information dividing unit 21, a matrix generating unit 23, a matrix calculating unit 24, a connecting unit 26, and a header information removing unit 28. It is composed of

  Here, the shared information dividing unit 21 divides the shared information obtained by concatenating the partial shared information to which the header information obtained by converting the partial shared information into the vector representation is connected into the partial shared information to which the header information is added. The matrix generation unit 23 generates a matrix based on the partial distribution information to which the divided header information is added. The matrix computation unit 24 performs matrix computation on the generated matrix and restores partial secret information accompanied by header information. The header information removing unit 28 removes the header information from the calculation result, and the concatenating unit 26 generates the secret information K by concatenating the partial secret information from which the header information has been removed.

As a specific process, as shown in FIG. 7, a binary sequence of partial shared information with header information added is treated as a vector, and a matrix operation is performed on the binary sequence to sequentially restore secret information. Then, after the execution of the matrix operation is completed, all the partial secret information K ₁ ,..., K _nP-1 is restored by taking out the n _p −1 row from the first row and removing the header information. Is done.

  Therefore, according to the present embodiment, by adding the vector representation of the component related to the partial shared information as header information to the generated shared information, the secret information can be stored without the shared information index or the component management table. Restoration can be performed. In addition, the configuration of the restoration device can be simplified.

<Example 1>
As a specific example, a restoration example when the (3, 5) threshold secret sharing method is configured will be described. The secret information restorer in the (3, 5) threshold secret sharing method restores the partial shared information K ₁ , K ₂ , K ₃ , and K ₄ by referring to the configuration table of the partial shared information shown in Table 2. .

In this restoration example, a case is considered where three managers P ₀ , P ₁ , and P ₂ gather.

(Step 1)
Each piece of shared information is divided to obtain partial secret information shown in Equation 10 below.

(Step 2)
Next, a vector representation of each component of the partial shared information is obtained from the component management table. When the information embedded as the header of the distributed information is extracted in advance, a vector representation is obtained from the information.

(Step 3)
Generate a matrix with vector representation in each row. The generated matrix satisfies the formula 11 below.

(Step 4)
Matrix operation is performed on the matrix part on the right side of the above equation (11), and the right side is modified to match the left side to obtain the following equation (12). In this example, Gauss-Jordan elimination is used as a matrix calculation method.

(Step 5)
By executing from the first row to the fourth row on the left side of Equation 12, all partial secret information is restored corresponding to each row number as shown in Equation 13 below.

(Step 6)
Finally, the restored partial secret information is concatenated to restore the original secret information K as shown in Equation 14.

<Example 2>
Next, as another specific example, a description will be given of a restoration method in the case where a vector expression related to the constituent elements of the partial shared information is added as header information of the partial shared information. In this embodiment, the (4, 5) threshold method shown in the configuration table in Table 3 is used.

In this restoration example, a case is considered in which four managers P ₀ , P ₁ , P ₂ , and P ₃ gather.

(Step 1)
Each shared information is divided to obtain partial shared information to which header information is added.

(Step 2)
A binary matrix as shown in Equation 15 is generated in which the partial distribution information with the header information added is arranged in each row. In the following, the header information and the partial distribution information are simply connected in binary.

(Step 3)
The matrix calculation is performed on the matrix shown in Equation 15 to obtain a matrix as shown in Equation 16 below. In this example, Gauss-Jordan elimination is used as a matrix calculation method.

(Step 4)
By extracting the first to fourth rows of the matrix shown in Equation 16 and removing the header information, all partial secret information is restored as shown in Equation 17.

(Step 5)
Finally, the restored partial secret information is concatenated to restore the original secret information K as shown in Equation 18.

  As described above, in this embodiment, a secret sharing system based on the (k, n) threshold secret sharing method using XOR capable of generating shared information and restoring secret information at high speed can be realized.

  The secret sharing and restoration process described above can be recorded on a computer-readable recording medium, and the program recorded on the recording medium can be read by a recording device and executed to implement the control of the present invention. . The computer system here includes an OS and hardware such as peripheral devices.

  Further, the “computer system” includes a homepage providing environment (or display environment) if a WWW (World Wide Web) system is used. The program may be transmitted from a computer system storing the program in a storage device or the like to another computer system via a transmission medium or by a transmission wave in the transmission medium. Here, the “transmission medium” for transmitting the program refers to a medium having a function of transmitting information, such as a network (communication network) such as the Internet or a communication line (communication line) such as a telephone line.

  The program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient.

  The embodiments of the present invention have been described in detail with reference to the drawings. However, the specific configuration is not limited to the embodiments, and includes designs and the like that do not depart from the gist of the present invention.

  The present invention can be used to securely process confidential data handled in a company or the like.

It is a functional block diagram of the distribution information generating device concerning a 1st embodiment. It is a functional block diagram of the secret information restoration device concerning a 1st embodiment. It is the figure which showed the structure of the shared information which concerns on 2nd Embodiment. It is a functional block diagram of the shared information generating device concerning a 2nd embodiment. It is a functional block diagram of the secret information restoration apparatus concerning a 2nd embodiment. It is the figure which showed the structure of the shared information which concerns on 3rd Embodiment. It is the figure which showed the structure of the matrix which concerns on 3rd Embodiment. It is a functional block diagram of the distributed information generation apparatus which concerns on 3rd Embodiment. It is a functional block diagram of the secret information decompression device concerning a 3rd embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 11 ... Divider, 12 ... Dummy secret information generator, 13 ... Partially distributed information generator 14, 15 ... Random number generator, 16 ... Concatenator, 17 ... Transmission device, 18, 19 ... header information embedding unit, 21 ... distributed information dividing unit, 22 ... vector expression conversion unit, 23 ... matrix generation unit, 24 ... matrix operation unit, 25 ... part Secret information restoration unit, 26 ... connection unit, 27 ... header information acquisition unit, 28 ... header information removal unit,

Claims (15)

A secret information restoration apparatus for restoring secret information from shared information in a (k, n) threshold secret sharing method,
dividing means for dividing k pieces of distributed information into k (n _p −1) pieces of partial shared information (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n);
Conversion means for converting the partial secret information and the part corresponding to the random number, which is a component of the divided partial shared information , into a k · n _p -2 bit vector representation in which only 1 corresponds to the other and 0 otherwise ;
Matrix generating means for generating a matrix of k (n _p −1) rows k · n _p −2 columns , which is a matrix related to all the partial shared information and includes the vector representation of each partial shared information as a component ;
Matrix operation means for executing a matrix operation on the generated matrix to obtain a combination of exclusive OR (XOR) operations on the partial dispersion information;
A restoration unit that restores partial secret information by applying the obtained combination of XOR operations to the partial shared information;
Concatenation means for concatenating the restored partial secret information to generate the original secret information K;
A secret information restoring apparatus comprising: A shared information generating device for generating shared information in a (k, n) threshold secret sharing method,
Dividing means for dividing the secret information K into (n _p −1) pieces of partial secret information K _q (1 ≦ q ≦ n _p −1) (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n ) ; ,
Dummy information generating means for generating dummy partial secret information K ₀ ;
K-1 random number generators for generating mutually independent random numbers R;
Said dummy portion secret information K ₀ and the partial secret information K _q, using said random number R, the calculation formula A, and the partial shared information generation means for generating partial shared information S _{(i, m),}
Concatenating means for concatenating the partial shared information S _{(i, m)} to generate n pieces of shared information S _i ;
The distributed information S _i thus generated, the partial shared information S _{(i, m)} said portion portion corresponding to the secret information K _q and random number R which is a component of only 1 constituting the distributed information to others 0 Header information adding means for adding header information converted into a vector representation of k · n _p -2 bits ,
A distributed information generating apparatus comprising:

A secret information restoration apparatus for restoring secret information from shared information in a (k, n) threshold secret sharing method,
Wherein the distributed information, the k · n p _-2-bit (n _p where only parts corresponding to the parts secret information and the random number which is a component of the partial shared information constituting the shared information and 1 to the rest zero dispersion the header information converted into a vector representation of the prime) satisfying n _p ≧ n from the information added to the number n, the header information obtaining means for obtaining by separating the header information,
A matrix of k (n _p −1) rows k · n _p −2 columns, which is a matrix related to all partial shared information based on the acquired header information and includes the vector representation of each partial shared information. Matrix generating means for generating
Dividing means for dividing the shared information into partial shared information;
Matrix operation means for executing a matrix operation on the generated matrix to obtain a combination of exclusive OR (XOR) operations on the partial dispersion information;
A restoration unit that restores partial secret information by applying the obtained combination of XOR operations to the partial shared information;
Concatenation means for concatenating the restored partial secret information to generate the original secret information K;
A secret information restoring apparatus comprising: A shared information generating device for generating shared information in a (k, n) threshold secret sharing method,
Dividing means for dividing the secret information K into (n _p −1) pieces of partial secret information K _q (1 ≦ q ≦ n _p −1) (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n ) ; ,
Dummy information generating means for generating dummy partial secret information K ₀ ;
K-1 random number generators for generating mutually independent random numbers R;
Said dummy portion secret information K ₀ and the partial secret information K _q, using said random number R, the calculation formula A, and the partial shared information generation means for generating partial shared information S _{(i, m),}
The generated partial shared information S _{(i, m),} the partial shared information S _{(i, m)} and 1 only the portion corresponding to the partial secret information K _q and random number R which is a component of the others 0 Header information adding means for adding header information converted into a vector representation of k · n _p -2 bits ,
Concatenation means for concatenating the partial shared information S _{(i, m)} to which the header information is added to generate n pieces of shared information S _i ;
A distributed information generating apparatus comprising:

A secret information restoration apparatus for restoring secret information from shared information in a (k, n) threshold secret sharing method,
K · n _p −2 bits in which only the part corresponding to the partial secret information and the random number, which is a component of the partial shared information, is 1 and the other is 0 (n _p is a prime number satisfying n _p ≧ n for the distributed number n ) Dividing means for dividing the distributed information obtained by concatenating the partial shared information added with the header information converted into the vector representation of the information into the partial shared information added with the header information;
Based on the partial shared information to which the divided header information is added, it is a matrix related to all the partial shared information, and k (n _p −1) rows k. matrix generating means for generating a matrix of n _p -2 columns ;
A computing means for performing matrix computation on the generated matrix and computing partial secret information accompanied by header information;
And removing means for removing the header information from the result of the said operation,
Concatenation means for concatenating the partial secret information from which the header information has been removed to generate secret information K;
A secret information restoring apparatus comprising: A secret information restoring method executed by the secret information restoring device according to claim 1 ,
A first step in which the dividing means divides the k pieces of shared information into k (n _p −1) pieces of partial shared information (n _p is a prime number satisfying n _p ≧ n for the number of distributed n);
The conversion means converts the partial secret information, which is a component of the divided partial shared information , into a k · n _p -2 bit vector representation in which only the portion corresponding to the random number is 1 and the other is 0 And the steps
The matrix generation means generates a matrix of k (n _p −1) rows k · n _p −2 columns, which is a matrix related to all partial shared information and includes the vector representation of each partial shared information. A third step;
A fourth step in which the matrix operation means performs a matrix operation on the generated matrix to obtain a combination of exclusive OR (XOR) operations on the partial dispersion information;
A fifth step in which the restoration means applies the obtained combination of XOR operations to the partial shared information to restore partial secret information;
A sixth step in which the connecting means generates the original secret information K by connecting the restored partial secret information;
A method for restoring secret information, comprising: A shared information generation method executed by the shared information generation device according to claim 2 ,
The dividing means divides the secret information K into (n _p −1) partial secret information K _q (1 ≦ q ≦ n _p −1) (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n ) . A first step of dividing;
The dummy information generating means, a second step of generating a dummy portion secret information K _0,
A third step in which the k-1 random number generators generate random numbers R independent of each other;
Said partial shared information generating means, wherein by using the dummy portion secret information K ₀ and the partial secret information K _q, and the random number R, the calculation formula A, first generates partial shared information S _{(i, m)} 4 steps ,
A fifth step in which the connecting means generates n pieces of shared information S _i by connecting the partial shared information S _{(i, m)} ;
The header information adding means adds only the portion corresponding to the partial secret information K _q and the random number R, which are constituent elements of the partial shared information S _{(i, m)} constituting the shared information , to the generated shared information S _i. A sixth step of adding header information converted into a vector representation of k · n _p -2 bits where 1 is 1 and the others are 0 ;
A distributed information generation method characterized by comprising:

A secret information restoring method executed by the secret information restoring device according to claim 3,
The header information acquisition unit, to the distributed information, k · n _p where only parts corresponding to the parts secret information and the random number which is a component of the partial shared information constituting the shared information and 1 to the rest 0 - 2-bit information (n _p is the prime number that satisfies n _p ≧ n for sharing number n) by adding a header information converted into a vector representation of a first step of obtaining by separating the header information,
Based on the acquired header information , the matrix generation means is a matrix related to all partial shared information and includes the vector representation of each partial shared information as a component of k (n _p −1) rows k · n. a second step of generating a _p -2 column matrix;
A third step in which the dividing means divides the shared information into partial shared information;
A fourth step in which the matrix operation means performs a matrix operation on the generated matrix to obtain a combination of exclusive OR (XOR) operations on the partial dispersion information;
A fifth step in which the restoration means applies the obtained combination of XOR operations to the partial shared information to restore partial secret information;
A sixth step in which the connecting means generates the original secret information K by connecting the restored partial secret information;
A method for restoring secret information, comprising: A shared information generation method executed by the shared information generation apparatus according to claim 4,
The dividing means divides the secret information K into (n _p −1) partial secret information K _q (1 ≦ q ≦ n _p −1) (n _p is a prime number satisfying n _p ≧ n with respect to the distributed number n ) . A first step of dividing;
The dummy information generating means, a second step of generating a dummy portion secret information K _0,
A third step in which the k-1 random number generators generate random numbers R independent of each other;
Said partial shared information generating means, wherein by using the dummy portion secret information K ₀ and the partial secret information K _q, and the random number R, the calculation formula A, first generates partial shared information S _{(i, m)} 4 steps ,
Said header information adding means, partial shared information S _{(i, m)} thus generated, the partial shared information S _{(i, m)} said portion portion corresponding to the secret information K _q and random number R which is a component of only A fifth step of adding header information converted into a k · n _p -2 bit vector representation in which 1 is set to 1 and 0 otherwise ;
A sixth step in which the connecting means generates n pieces of shared information S _i by connecting the partial shared information S _{(i, m)} to which the header information has been added;
A distributed information generation method characterized by comprising:

A secret information restoring method executed by the secret information restoring device according to claim 5, comprising:
It said dividing means, said portion only a portion corresponding to the partial secret information and the random number which is a component of the distributed information and 1 to the rest and 0 k · n p _-2-bit (n _p is n _p for sharing number n A first step of dividing the shared information obtained by concatenating the partial shared information added with the header information converted into a vector representation of a prime number satisfying ≧ n into the partial shared information added with the header information;
The matrix generation unit is a matrix related to all partial shared information based on the partial shared information to which the divided header information is added, and k (n _p -1) a second step of generating a matrix of rows k · n _p -2 columns ;
It said computing means, a third step of running the matrix operation for the matrix thus generated, calculates the partial secret information with the header information,
The removing means, and a fourth step of removing the header information from the result of the said operation,
A fifth step in which the concatenating means concatenates the partial secret information from which the header information has been removed to generate secret information K;
A method for restoring secret information, comprising: A program for causing a computer to execute each step of the secret information restoring method according to claim 6 . A program for causing a computer to execute each step of the distributed information generation method according to claim 7 . The program for making a computer perform each step of the secret information restoration method of Claim 8 . A program for causing a computer to execute each step of the distributed information generation method according to claim 9 . A program for causing a computer to execute each step of the secret information restoring method according to claim 10 .

Images