JP5683503B2 - Data distribution device, distributed data conversion device, and data restoration device - Google Patents

Description

  The present invention relates to a secret sharing technique.

Secret sharing is a technology that converts data into a plurality of distributed values and restores the original data by using more than a certain number of distributed values, and makes it impossible to restore the original data from less than a certain number of distributed values. . Assuming that the total number of variance values is N and the minimum number of variance values required for restoration is K (≦ N), there are some schemes in which the values of N and K are not limited. As a simple method of secret sharing, there is additive secret sharing. This is a subset of A = {a ₀ , a ₁ , ..., a _M-1 } for data a = a ₀ + a ₁ + ... + a _M-1 where M is an integer greater than or equal to 2 And However, a, a ₀ , a ₁ ,..., A _M-1 are elements of the additive group, particularly a ₀ , a ₁ ,..., A _M-2 are values randomly selected from the additive group.

  A secret calculation (multi-party calculation) method using secret sharing as an elemental technology has also been proposed (see, for example, Non-Patent Documents 1 and 2). In such a secret calculation method, a distributed value of data held by each subject is sent to another subject, and the intended calculation is executed without revealing the distributed value to the other subject. A variance value of the calculation result is obtained from each subject that has performed the calculation. If K or more of such dispersion values are obtained, the calculation result can be restored, and if not obtained, the calculation result cannot be restored.

For example, in the secret calculation method of Non-Patent Document 1, an additive secret sharing method is used as a secret sharing method, and the distributed value of a is set to S _i (a) = a _i (i = 0, 1,..., N−1 ) And M = N = K, and the secret calculation is performed. In this method, a can obviously be restored from N dispersion values S _i (a), and a cannot be restored from N−1 dispersion values. In the secret calculation method of Non-Patent Document 2, an additive secret sharing method is used as a secret sharing method, and the distributed value of a is expressed as S _i (a) = {a _i , a _{i + 1 mod 3} } (i = 0, 1,..., N-1), and M = N = 3, K = 2, and the secret calculation is performed. In this method, a can obviously be restored from any two variance values S _i (a), and a cannot be restored from any one variance value.

D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” Cryptology ePrint Archive: Report 2008/289, [searched November 30, 2011], Internet <http: //eprint.iacr.org/2008/289> Koji Senda, Univ. Igarashi, Katsumi Takahashi, “Proposal of efficient three-party secret function calculation and consideration of its operational model,” IPSJ 48th CSEC meeting, 2010.

In the additive secret sharing described in Non-Patent Documents 1 and 2, the total data amount of the distributed values is N times and 6 times that of the original data, respectively. The total amount of data required for restoration is N times and 3 times the original data. Since an increase in the data amount of the variance value leads to an increase in communication time and stored data, it is desirable to suppress the data amount of the variance value as much as possible. Such a problem is common not only to additive secret sharing but also to other secret sharing schemes.
The present invention has been made in view of such a point, and an object thereof is to suppress the data amount of the shared value of the secret sharing scheme.

M and N are integers greater than or equal to 2, _Ni (i = 0, ..., N-1) is an integer greater than or equal to 1 and less than or equal to M-1, G is a set, and P (x) Is a mapping that maps values corresponding to x to elements of the set G, and y = f (y (0), ..., y (M-1)) are M values y ( 0), ..., y (M-1) is a mapping that transfers a subset (y (0), ..., y (M-1)) to a value y that is an element of set G, and g M (y, y (0), ..., y (M-2)) are elements of the set G satisfying y = f (y (0), ..., y (M-1)) A subset (y, y (0), ..., y (M-2)) consisting of y, y (0), ..., y (M-2) Suppose it is a mapping to be transferred.

When distributing data, select M-1 values v (m) (m = 0, ..., M-2) and M-1 values a (m) = P (v (m)) ( m = 0, ..., M-2) and the value a (M-1) = g (α, a (0), ..., a (M -2)), the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1)) (i = Get 0, ..., N-1). However, a subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., a n-1), which is _{a (i, n i) ≠} a (M-1) (i, n i) (n i ∈ {0 ,. .., N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )), and a (i, q _i ) = a (M-1) V (i, q _i ) corresponding to a certain (i, q _i ) (q _i ∈ {0, ..., N _i -1}) is a (i, q _i ).

When data restoration, the dispersion value _{T i (α) (i =} 0, ..., N-1) at least a portion with M-1 single values a in (m) = P (v ( m)) ( m = 0, ..., M- 2) to obtain a value a (m) (m = 0 , ..., M-2) and the dispersion value T _i (alpha) either contains a value a of (M -1) to obtain α = f (a (0), ..., a (M-1)).

  In the present invention, it is possible to suppress the data amount of the shared value of the secret sharing scheme.

FIG. 1 is a block diagram illustrating a functional configuration of a secret sharing system. FIG. 2A is a block diagram illustrating a functional configuration of the data distribution apparatus, and FIG. 2B is a block diagram illustrating a functional configuration of the data restoration apparatus. FIG. 3 is a block diagram illustrating a functional configuration of the distributed data conversion apparatus. FIG. 4 is a flowchart for illustrating processing of the data distribution apparatus. FIG. 5 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 6 is a flowchart for illustrating the processing of the data restoration apparatus. FIG. 7 is a flowchart for illustrating processing of the data distribution apparatus. FIG. 8 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 9 is a flowchart for illustrating the processing of the data restoration apparatus. FIG. 10A is a block diagram illustrating the functional configuration of the data distribution apparatus, and FIG. 10B is a block diagram illustrating the functional configuration of the data restoration apparatus. 11A and 11B are block diagrams illustrating the functional configuration of the distributed data conversion apparatus. FIG. 12 is a flowchart for illustrating processing of the data distribution apparatus. 13A and 13B are flowcharts for illustrating the processing of the data distribution apparatus. FIG. 14 is a flowchart for illustrating the processing of the data restoration apparatus. FIG. 15 is a block diagram illustrating a functional configuration of the secret sharing system. FIG. 16A is a block diagram illustrating a functional configuration of the data distribution apparatus, and FIG. 16B is a block diagram illustrating a functional configuration of the data restoration apparatus. FIG. 17 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 18 is a flowchart for illustrating processing of the data distribution apparatus. FIG. 19 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 20 is a flowchart for illustrating processing of the data restoration device. FIG. 21 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 22 is a flowchart for illustrating processing of the distributed data conversion apparatus. FIG. 23 is a flowchart for illustrating processing of the data restoration device.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[First Embodiment]
First, the outline of the first embodiment will be described.
In the first embodiment, M, N is an integer of 2 or _{more, N i (i = 0,} ..., N-1) is 1 or more M-1 an integer, G is a certain set Yes, P (x) is a mapping that moves the value corresponding to x to an element of set G, and y = f (y (0), ..., y (M-1)) is an element of set G A subset (y (0), ..., y (M-1)) of M values y (0), ..., y (M-1) is changed to a value y that is an element of the set G. G (y, y (0), ..., y (M-2)) satisfying y = f (y (0), ..., y (M-1)) A subset (y, y (0), ..., y (M-2)) consisting of M elements y, y (0), ..., y (M-2) This is the map to be transferred to (M-1).

The set G is a set in which operations are defined, and specific examples of the set G are groups (for example, additive groups and multiplicative groups) and fields. For example, the set G can be an additive group {0, 1,..., Μ−1} consisting of a representative element of a residue class modulo an arbitrary positive integer μ. An example of a positive integer mu are μ = 2 ^32. The mapping P (x) outputs elements of the set G with respect to the input “value corresponding to x”. The same “P (x)” corresponds to the same “value corresponding to x”. That is, the map P (x) is a deterministic function in which the outputs are equal if the inputs are equal. “Value corresponding to x” and “P (x)” may or may not correspond one-on-one. The “value corresponding to x” may be the value x itself or a combination value of x and other values (for example, a value z (r, x) corresponding to r and x). Good. An example of the mapping P (x) is a pseudorandom number generation function that returns elements of the set G using x as a seed. Also, for example, a common key encryption function that outputs a ciphertext belonging to the set G for a fixed plaintext with x as a secret key can be used as P (x). Specific examples of the mapping y = f (y (0), ..., y (M-1)) and g (y, y (0), ..., y (M-2)) are as follows: is there. For example, if the set G is an additive group, y = y (0) + ... + y (M-1) ∈G, y = -y (0) -...- y (M-1) ∈G , Y = y (0) -y (1) + y (2) -... + y (M-1) ∈G and so on map y = f (y (0), ..., y (M- 1)). For example, if the set G is an additive group consisting of representatives of residue classes modulo μ, for example, y = y (0) + ... + y (M-1) (mod μ) f (y (0), ..., y (M-1)). If the set G is a multiplicative group, for example, y = y (0) ···· y (M-1) ∈G, y = {y (0)} ^-1 ···· y {(M- 1)} ^-1 ∈G, y = y (0) ・ {y (1)} ^-1・ y (2) ・ {y (3)} ^-1 ...... y (M-1) etc. The map y = f (y (0), ..., y (M-1)). The map g (y, y (0), ..., y (M-2)) has the above relationship to the map y = f (y (0), ..., y (M-1)) Fulfill. For example, if the map y = f (y (0), ..., y (M-1)) is y = y (0) + ... + y (M-1) (mod μ), the map g (y, y (0), ..., y (M-2)) is y (M-1) = yy (0) -y (1) ...- y (M-2) (mod μ ). The “mapping” may be a function or an algorithm. Further, M ≦ N or M ≧ N may be satisfied.

The secret sharing system according to the first embodiment includes a data distribution device, a data restoration device, and N distributed data conversion devices.
The data distribution apparatus of this embodiment selects M-1 values v (m) (m = 0, ..., M-2) and M-1 values a (m) = P (v ( m)) (m = 0, ..., M-2) and the value a (M-1) = g (α, a (0), ... , a (M-2)), and the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1) ) Get (i = 0, ..., N-1). However, a subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., a n-1), which is _{a (i, n i) ≠} a (M-1) (i, n i) (n i ∈ {0 ,. .., N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )), and a (i, q _i ) = a (M-1) V (i, q _i ) corresponding to a certain (i, q _i ) (q _i ∈ {0, ..., N _i -1}) is a (i, q _i ). N distributed values T _i (α) (i = 0,..., N−1) obtained by the data distribution apparatus are provided to, for example, each of the N distributed data conversion apparatuses.

The data restoration device according to the present embodiment uses M−1 values a (m) = P using at least a part of N dispersion values T _i (α) (i = 0,..., N−1). (v (m)) (m = 0, ..., M-2) is obtained, and the obtained value a (m) (m = 0, ..., M-2) and the variance T _i ( α = f (a (0), ..., a (M-1)) is obtained using the value a (M-1) included in any of α).

Each of the distributed data conversion apparatuses of the present embodiment uses the distributed value T _i (α) provided to itself, and a (i, n _i ) ≠ a (M−1) (i, n _i ) (n _the value a (i, n _i ) = P (v (i, n _i ) for v (i, n _i ) ∈T _i (α) corresponding to _i ∈ {0, ..., N _i -1}) ) And values a (i, n _i ) and v (i, q _i ) = a (M-1) (q _i ∈ {0, ..., N _i -1}, n _i ≠ q _i ) A (i, q _i ) = v (i, q _i ) ∈T _i (α) and S _i (α) = (a (i, 0), ..., a ( i, N _i -1)} can also be obtained as the transformation variance value. The transform variance value S _i (α) thus obtained is used as an input value for secret calculation. For example, each result obtained by performing the same secret calculation on the transformed variance value S _i (α) obtained by the plurality of distributed data transformation devices 120-i is the computation result obtained by computing α. Secret sharing value. A specific example of the secret calculation is a linear calculation disclosed in Non-Patent Documents 1 and 2 and the like. The secret calculation may be a unary operation or a multinomial operation.

Preferably, in this embodiment, the total value of the data amount of M−1 values v (m) (m = 0,..., M−2) is the data amount of the elements of M−1 sets G. Less than the total value. More preferably, the data amount of each value v (m) is smaller than the data amount of the elements (one element) of the set G. Even more preferably, the data amount of each value v (m) is negligible with respect to the data amount of the elements of the set G (for example, (data amount of each of v (m)) / (set G The amount of data in the element) ≦ 80/10 ⁶ ).

<Configuration>
As illustrated in FIG. 1, the secret sharing system 1 according to the first embodiment includes a data distribution device 110, N distributed data conversion devices 120-i (i = 0,..., N−1), and data. A restoration device 130 is included. The data distribution device 110 can provide information to N distributed data conversion devices 120-i (i = 0,..., N-1) via a network or a portable recording medium. is there. Each of the N distributed data conversion apparatuses 120-i (i = 0,..., N-1) can provide information to the data restoration apparatus 130 via a network or a portable recording medium. Is possible.

  As illustrated in FIG. 2A, the data distribution apparatus 110 according to the present exemplary embodiment includes an input unit 111, an output unit 112, a memory 113, a control unit 114, a selection unit 115, a conversion unit 116, a calculation unit 117, and a distributed value generation unit 118. Have The data distribution apparatus 110 of this embodiment is a special apparatus configured by reading a special program into a known or dedicated computer having a CPU (central processing unit), a RAM (random-access memory), and the like. Although not described below, the data distribution apparatus 110 according to the present embodiment executes each process under the control of the control unit 114. Data input to the input unit 111 and data obtained in each process are stored in the memory 113, and the data stored in the memory 113 is read as necessary and used for other processes.

  As illustrated in FIG. 2B, the data restoration device 130 according to the present exemplary embodiment includes an input unit 131, an output unit 132, a memory 133, a control unit 134, a conversion unit 135, and a restoration unit 136. The data restoration device 130 of this embodiment is a special device configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data restoration device 130 according to the present embodiment executes each process under the control of the control unit 134. Data input to the input unit 131 and data obtained in each process are stored in the memory 133, and the data stored in the memory 133 is read as necessary and used for other processes.

  As illustrated in FIG. 3, the distributed data conversion apparatus 120-i (i = 0,..., N−1) of this embodiment includes an input unit 121-i, an output unit 122-i, a memory 123 a-i, The storage units 123b-i and 123c-i, the control unit 124-i, the conversion unit 125-i, the conversion variance value generation unit 126-i, and the secret calculation unit 127-i. The distributed data conversion apparatus 120-i of this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the distributed data conversion apparatus 120-i according to the present embodiment executes each process under the control of the control unit 124-i. Data input to the input unit 121-i and data obtained in each process are stored in the memory 123a-i and the storage unit 123b-i, and data stored in the memory 123a-i and the storage unit 123b-i are necessary. Is read out and used for other processing.

<Data distribution processing>
As illustrated in FIG. 4, the value αεG that is secretly shared is input to the input unit 111 of the data distribution apparatus 110 (FIG. 2A) (step S111). Examples of the value α are a moving image file, an audio file, a text file, a table file, and the like. The data amount of the value α, that is, the data amount of the elements of the set G is, for example, 1 megabyte or more.

  The selection unit 115 selects M-1 values v (m) (m = 0, ..., M-2), and values v (m) (m = 0, ..., M-2). Is output (step S112). The selection unit 115 may select M−1 values v (m) (m = 0,..., M−2) randomly at a time, or is generated in advance and stored in the memory. M−1 values v (m) (m = 0,..., M−2) may be selected from a plurality of values according to a predetermined rule. For example, the data amount of each of the selected values v (m) (m = 0,..., M-2) is desirably sufficiently smaller than the data amount of the elements (one element) of the set G. In consideration of safety, the value v (m) is a value that makes it difficult to specify the value v (m) from the value a (m) or P (x) generated from the value v (m) ( In consideration of the exhaustive search attack and the performance of the current computer, the value v (m) is preferably a random number of about 80 bits or more.

  The value v (m) (m = 0,..., M−2) is input to the conversion unit 116. The conversion unit 116 converts the input value v (m) (m = 0,..., M-2) to M−1 values a (m) = P (v (m)) (m = 0, .., M-2) are calculated, and the M-1 values a (m) (m = 0,..., M-2) are output (step S113). When P (x) is a pseudorandom number generation function, the value a (m) is a pseudorandom number.

  The value α input to the input unit 111 and the M−1 values a (m) (m = 0,..., M−2) output from the conversion unit 116 are input to the calculation unit 117. The calculation unit 117 calculates the value a (M-1) = g (α, a (0), ..., a from these values α, a (m) (m = 0, ..., M-2). (M-2)) εG is calculated, and the value a (M-1) is output (step S114). For example, the map g (y, y (0), ..., y (M-2)) is y (M-1) = yy (0) -y (1) ...- y (M-2) If (mod μ), the calculation unit 117 calculates a (M−1) = α−a (0) −a (1)... −a (M−2) (mod μ), and thereby The obtained value a (M-1) is output.

The M−1 values v (m) (m = 0,..., M−2) output from the selection unit 115 and the value a (M−1) output from the calculation unit 117 are used to generate a variance value. Input to the unit 118. The variance value generation unit 118 uses these values a (M−1), v (m) (m = 0,..., M−2), and N variance values T _i (α) of the value α. = (v (i, 0), v (i, 1), ..., v (i, N _i -1)) (i = 0, ..., N-1) is generated and output. However, a subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., a n-1), which is _{a (i, n i) ≠} a (M-1) (i, n i) (n i ∈ {0 ,. .., N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )), and a (i, q _i ) = a (M-1) V (i, q _i ) corresponding to a certain (i, q _i ) (q _i ∈ {0, ..., N _i -1}) is a (i, q _i ). P ⁻¹ (X) (X∈G) represents the inverse mapping of P (x) (step S115).
For example, the variance value generation unit 118 sets M = N, N _i = N−1, and uses the subset A \ a (i) obtained by removing the value a (i) from the set A as S _i (α ) (i = 0,..., N-1), and a variance value T _i (α) (i = 0,..., N-1) is generated as follows.
T ₀ (α) = (v (1), v (2), ..., v (M-2), a (M-1)),
T ₁ (α) = (v (0), v (2), ..., v (M-2), a (M-1)), ...,
T _M-2 (α) = (v (0), v (1), ..., v (M-3), a (M-1)),
T _M-1 (α) = (v (0), v (1), ..., v (M-3), v (M-2)) ... (1)

N variance values T _i (α) (i = 0,..., N−1) are input to the output unit 112, and the output unit 112 outputs N variance values T _i (α) (i = 0, ..., N-1) are output (step S116). Each of the output distributed values T _i (α) (i = 0,..., N−1) is assigned to each of the distributed data converters 120-i (i = 0,..., N−1). Provided. For example, the distributed value T _i (α) is transmitted to the corresponding distributed data conversion apparatus 120-i (FIG. 3) via a network or the like. The distributed value T _i (α) provided to each of the distributed data converters 120-i (i = 0,..., N−1) is input to the input unit 121-i and stored in the storage unit 123b-i. Is done.

<Distributed data conversion processing / distributed value output processing>
A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 120-i (i = 0,..., N-1) will be described. These processes may be executed by all the distributed data converters 120-i (i = 0,..., N-1), or K (K ≦ N) distributed data converters among them. It may be executed only by 120-k (kε {0,..., N−1}).
As illustrated in FIG. 5, when each of the distributed data converters 120-i (i = 0,..., N−1) outputs a distributed value without converting the distributed value, the control unit 124- i instructs the storage unit 123b-i to read the dispersion value T _i (α) without performing the conversion of the dispersion value (step S121-i). Receiving this instruction, the storage unit 123b-i reads and outputs the stored dispersion value T _i (α). The variance value T _i (α) is sent to the output unit 122-i, and the output unit 122-i outputs the variance value T _i (α) (step S122-i). The output variance value T _i (α) is provided to the data restoration device 130. For example, the variance value T _i (α) is transmitted to the data restoration device 130 via a network or the like. When the distributed data converter 120-i (i = 0,..., N-1) outputs a distributed value without converting the distributed value, a distributed data conversion process and a distributed value output process are executed. All the distributed data converters 120-i (i = 0,..., N−1) output the distributed values without performing the conversion of the distributed values.

On the other hand, when each of the distributed data converters 120-i (i = 0,..., N-1) performs the conversion of the variance value, the control unit 124-i performs the variance value conversion in order to convert the variance value. The storage unit 123b-i is instructed to read T _i (α) = (v (i, 0), v (i, 1),..., V (i, N _i −1)) (step S121). -I). Receiving this instruction, the storage unit 123b-i reads the variance value T _i (α).
Of the elements constituting the read dispersion value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1)), a ( i, n _i ) ≠ a (M-1), the value v (i, n _i ) ∈T corresponding to (i, n _i ) (n _i ∈ {0, ..., N _i -1}) _i (α) (n _i ε {0,..., N _i −1}) is input to the conversion unit 125-i. The read variance T _i (α) is v (i, q _i ) = a (i, q _i ) = a (M-1) ∈ T _i (α) (q _i ∈ {0, ... _{, n i -1}, n i} ≠ q i) a is the value v (i, if it contains q _i), the value v _(i, q i) are input to the conversion variance generating unit 126-i.

Conversion unit 125-i is input value v _(i, n i) from the values _{a (i, n i) =} P (v (i, n i)) is calculated, and the value a (i, n _i ) Is output (step S123-i).

The conversion variance value generation unit 126-i includes a value a (i, n _i ) (n _i ε {0,..., N _i −1}) obtained by the conversion unit 125-i, and a storage unit 123b. V (i, q _i ) = a (i, q _i ) = a (M−1) (q _i ∈ {0, ..., N _i −1}, n _i ≠ q _i ) and (if present) are entered. The conversion variance value generation unit 126-i generates a conversion variance value S _i (α) = {a (i, 0), ..., a (i, N _i -1)} composed of input values. (Step S124-i), the transformation variance value S _i (α) is stored in the storage unit 123c-i (Step S125-i). For example, the transformed variance value S _i (α) corresponding to the variance value T _i (α) in equation (1) is as follows.
S ₀ (α) = (a (1), a (2), ..., a (M-2), a (M-1)),
S ₁ (α) = (a (0), a (2), ..., a (M-2), a (M-1)), ...,
S _M-2 (α) = (a (0), a (1), ..., a (M-3), a (M-1)),
S _M-1 (α) = (a (0), a (1), ..., a (M-3), a (M-2))

The secret calculation unit 127-i receives the transformation variance value S _i (α) = {a (i, 0), ..., a (i, N _i −1) stored in the storage unit 123c-i at a predetermined opportunity. )} Is read, and a secret calculation is performed with the transformed variance value S _i (α) as an input, and the variance value E _i = {e (i, 0), ..., e (i, N _i -1)} is output. The variance value E _i is output from the output unit 122-i and provided to the data restoration device 130. For example, the distributed value E _i is transmitted to the data restoration device 130 via a network or the like. An example of a simple secret calculation is scalar multiplication in the additive group G of the transformation variance S _i (α) = {a (i, 0), ..., a (i, N _i -1)} In this case, E _i = υ · S _i (α), that is, {e (i, 0), ..., e (i, N _i -1)} = {υ · a (i, 0), ..., υ · a (i, N _i -1)}. Where υ is an element of an integer ring.

<Data restoration processing>
As illustrated in FIG. 6, any K distributed values T _k (α) (k∈ {0,..., N−1}) are input to the input unit 131 of the data restoration device 130 (FIG. 2B). Or, any K variance values E _k = {e (k, 0), ..., e (k, N _k -1)} (k∈ {0, ..., N-1}) Input (step S131). The control unit 134 determines whether the variance value T _k (α) is input or the variance value E _k is input (step S132).

When it is determined in step S132 that the variance value T _k (α) is input, any K variance values T _k (α) (k∈ {0,..., N−1}) 135 is input. The conversion unit 135 uses the at least part of the K dispersion values T _k (α) (k∈ {0, ..., N-1}) to obtain M−1 values a (m) = P ( v (m)) (m = 0,..., M-2) is calculated, and the value a (m) (m = 0,..., M-2) is output (step S133). For example, when the variance values T ₀ (α) and T ₁ (α) of the above equation (1) are input to the conversion unit 135, the conversion unit 135 includes v (1) included in the variance value T ₀ (α). , v (2), ..., v (M-2) and v (0) included in the variance T ₁ (α), M-1 values a (m) = P (v (m )) Calculate (m = 0, ..., M-2).
The restoration unit 136 includes M−1 values a (m) = P (v (m)) (m = 0,..., M−2) and the variance value T _k input to the input unit 131. A value a (M−1) included in any of (α) is input. The restoration unit 136 calculates α = f (a (0),..., A (M−1)) using these, and outputs the obtained value α (step S134). For example, the map y = f (y (0), ..., y (M-1)) is y = y (0) + y (1) ... + y (M-1) (mod μ) In some cases, the restoration unit 136 calculates α = a (0) + a (1) +... + A (M−1) (mod μ) and outputs the value α obtained thereby. The value α is input to and output from the output unit 132 (step S135).

On the other hand, when it is determined in step S132 that the variance value E _k is input, K variance values E _k (kε {0,..., N−1}) are input to the restoration unit 136. The restoration unit 136 uses K variance values E _k = {e (k, 0), ..., e (k, N _k -1)} (k∈ {0, ..., N-1}). Obtain M values e (0), ..., e (M-1) consisting of the elements of, and calculate ε = f (e (0), ..., e (M-1)) As a result, ε is output (step S136). As a simple example, the restoration unit 136 has two variance values E ₀ = υ · S ₀ (α) = (υ · a (1), υ · a (2), ..., υ · a (M− 2), υ ・ a (M-1)), and E ₁ = υ ・ S ₁ (α) = (υ ・ a (0), υ ・ a (2), ..., υ ・ a (M- 2), a (M-1)) is input, the restoration unit 136 determines that υ · a (0), υ · a (1), υ · a (2), ..., υ · a (M-2), υ ・ a (M-1), ε = f (υ ・ a (0), υ ・ a (1), υ ・ a (2), ..., υ ・ a (M-2), υ · a (M-1)) is calculated. The result ε is input to the output unit 132 and is output therefrom (step S137).

<Features of this embodiment>
In this embodiment, compared to the conventional secret sharing scheme, the data amount of the distributed value can be greatly reduced. That is, the element v (i, n) that constitutes the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1)) in this embodiment. 0), v (i, 1), ..., v (i, N _i -1) is at least part of v (m) (m = 0, ..., M-2) . Therefore, the data amount of the variance value can be reduced as compared with the conventional variance value including only the elements of the set G. How much the data amount of the variance value can be reduced depends on the difference between the data amount of v (m) and the data amount of the elements of the set G. For example, the sum of the data amount of M-1 values v (m) (m = 0, ..., M-2) is smaller than the sum of the data amounts of the elements of M-1 sets G In this case, the total data amount of the distributed value of this embodiment is smaller than the total data amount of the distributed value of the conventional secret sharing scheme. For example, if the data amount of each of v (m) is smaller than the data amount of the elements of the set G, the total data amount of the distributed value in the method of the present embodiment is larger than the total data amount of the distributed value of the conventional secret sharing method. Becomes smaller. If the data amount of each v (m) is negligibly small compared to the data amount of the elements of the set G, the data amount of each variance value T _i (α) is the data amount of one element of the set G And the same level.
Furthermore, the distributed data conversion process in the distributed data conversion device generates a converted distributed value that can be used as an input for the secret calculation without restoring the original value α from the distributed value obtained by the data distribution device. It is also possible to execute a secret calculation.

[Second Embodiment]
Next, a second embodiment of the present invention will be described. This embodiment is a modification of the first embodiment, and the data value of the distributed value is further reduced by diverting the same value v (m) to a plurality of secret sharing. Below, it demonstrates centering on difference with 1st Embodiment. The same reference numerals as those in the first embodiment are used for the processing units and steps common to the first embodiment, and the description will be simplified.
In the second embodiment, M, N, and R are integers of 2 or more, and _{Ni, r} (i = 0, ..., N-1, r = 0, ..., R-1) is 1. Is an integer less than or equal to M-1, G is a set, P (x) is a mapping that moves a value corresponding to x to an element of set G, and y = f (y (0),. ., y (M-1)) is a subset (y (0), ..., y) of M values y (0), ..., y (M-1), with elements of the set G (M-1)) to a value y that is an element of the set G, and g (y, y (0), ..., y (M-2)) is y = f (y (0) , ..., y (M-1)), a subset (y, y (0) of M elements y, y (0), ..., y (M-2) that are elements of set G ), ..., y (M-2)) to the value y (M-1). Set G of this form, map P (x), y = f (y (0), ..., y (N-1)) and g (y, y (0), ..., y (N- Specific examples of 2)) include the set G, the mapping P (x), y = f (y (0), ..., y (N-1)) and g (y, y) described in the first embodiment. (0), ..., y (N-2)) is the same as the specific example. M ≦ N or M ≧ N may be satisfied. M ≧ R or M ≦ R may be satisfied. N ≧ R or N ≦ R may be satisfied.

The secret sharing system according to the second embodiment includes a data distribution device, a data restoration device, and N distributed data conversion devices.
The data distribution apparatus of this embodiment selects M-1 values v (m) (m = 0, ..., M-2), and sets values corresponding to r and value v (m) to z ( r, v (m)) and M-1 values for each r a _r (m) = P (z (r, v (m))) (r = 0, ..., R- 1, m = 0, ..., M-2) to obtain a value for an element of the set G value _{α r a r (M-1} ) = g (α r, a r (0) ,. .., a _r (M-2)), and variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) (i = 0, ..., N-1, r = 0, ..., R-1). Where a subset of the set A _r = {a _r (0), ..., a _r (M-1)} is S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1) and a _r (i, n _{i, r} ) ≠ a _r (M-1) (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1 ) At least one of R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) corresponding to) is a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (r′∈ {0, ..., R-1}) satisfying v _{r ′} (i, n _{i, r '} ) ∈ {v (0), ..., v (M-2)} and a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r ) (q i, r ∈ {} 0, ..., n i, r -1}, n i, r ≠ q i, v r (i corresponding to _r), q _{i, r)} is a _r (i , q _{i, r} ) = a _r (M−1). The same “z (r, v (m))” corresponds to the same “r and v (m) combination (r, v (m))”. z (r, v (m)) and “combination of r and v (m) (r, v (m))” may or may not correspond one-to-one.

The data restoration apparatus of the present embodiment uses M−1 values a for each of r using at least a part of the variance values T _i (α _r ) (i = 0,..., N−1). _r (m) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2), and the value a _r (m ) Using (m = 0, ..., M-2) and the value a _r (M-1) included in any of the variance values T _i (α _r ), α _r = f (a _r (0) , ..., a _r (M-1)).

Each of the distributed data conversion apparatuses of the present embodiment includes v _{r ′} (i, n _{i, r ′} ) (r ′ included in the distributed value T _i (α _r ) (r = 0,..., R−1). ∈ {0, ..., R-1}) value a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} )))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}) and the resulting values a _r (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}) and v _r (i, q _{i, r} ) = a _r (M-1) (q _{i, r} ∈ {0, ..., N _{i, r} -1}, n _{i, r} ≠ q _{i, r)} a is _{a r (i, q i,} r) = v r (i, q i, r) ∈T i (α r) S i (α r containing at least one of the) = { a _r (i, 0), ..., a _r (i, N _{i, r} -1)} are obtained as transformation variance values. The transform variance value S _i (α _r ) thus obtained is used as an input value for secret calculation.

Preferably, in this embodiment, the total value of the data amount of M−1 values v (m) (m = 0,..., M−2) is the data amount of the elements of M−1 sets G. Less than the total value. More preferably, the data amount of each value v (m) is smaller than the data amount of the elements (one element) of the set G. Even more preferably, the data amount of each value v (m) is negligible with respect to the data amount of the elements of the set G (for example, (data amount of each of v (m)) / (set G The amount of data in the element) ≦ 80/10 ⁶ ).

<Configuration>
As illustrated in FIG. 1, the secret sharing system 2 according to the second embodiment includes a data distribution device 210, N distributed data conversion devices 220-i (i = 0,..., N−1), and data. A restoration device 230 is included. The data distribution device 210 can provide information to the N distributed data conversion devices 220-i (i = 0,..., N-1) via a network or a portable recording medium. is there. Each of the N distributed data conversion devices 220-i (i = 0,..., N-1) can provide information to the data restoration device 230 via a network or a portable recording medium. Is possible.

  As illustrated in FIG. 2A, the data distribution apparatus 210 according to the present exemplary embodiment includes an input unit 111, an output unit 112, a memory 113, a division unit 211, a control unit 214, a selection unit 115, a conversion unit 216, a calculation unit 217, and a distribution. A value generation unit 218 is included. The data distribution apparatus 210 according to this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data distribution apparatus 210 according to the present embodiment executes each process under the control of the control unit 214. Data input to the input unit 111 and data obtained in each process are stored in the memory 113, and the data stored in the memory 113 is read as necessary and used for other processes.

  As illustrated in FIG. 2B, the data restoration device 230 according to this embodiment includes an input unit 131, an output unit 132, a memory 133, a control unit 234, a conversion unit 235, a restoration unit 236, and a combining unit 237. The data restoration device 230 according to the present embodiment is a special device configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data restoration device 230 according to the present embodiment executes each process under the control of the control unit 234. Data input to the input unit 131 and data obtained in each process are stored in the memory 133, and the data stored in the memory 133 is read as necessary and used for other processes.

  As illustrated in FIG. 3, the distributed data conversion apparatus 220-i (i = 0,..., N−1) of this embodiment includes an input unit 121-i, an output unit 122-i, a memory 123 a-i, The storage units 123b-i and 123c-i, the control unit 224-i, the conversion unit 225-i, the conversion variance value generation unit 226-i, and the secret calculation unit 227-i. The distributed data conversion apparatus 220-i of this embodiment is a special apparatus configured by reading a special program into a known or dedicated computer, for example. Although not described below, the distributed data conversion apparatus 220-i according to the present embodiment executes each process under the control of the control unit 224-i. Data input to the input unit 121-i and data obtained in each process are stored in the memory 123a-i and the storage unit 123b-i, and data stored in the memory 123a-i and the storage unit 123b-i are necessary. Is read out and used for other processing.

<Data distribution processing>
As illustrated in FIG. 7, the value α to be secretly shared is input to the input unit 111 of the data distribution device 210 (FIG. 2A) (step S111). The value α is input to the dividing unit 211. The dividing unit 211 divides the value α into R values α _r ∈G (r = 0,..., R-1) that are elements of the set G, and R values α _r ∈G (r = 0,..., R-1) are output (step S211). For example, when the set G is an additive group {0, 1,..., Μ−1} and α ≧ μ, the dividing unit 211 sets α = α ₀ + μ · α so that R is minimized, for example. ₁ + ... + μ ^R-1・ α _R-1 and 0 to μ-1 R values α ₀ , α ₁ , ..., α _R-1 ∈ {0,1, ... ., μ-1} and outputs the values α ₀ , α ₁ , ..., α _R−1 .

  The selection unit 115 selects M-1 values v (m) (m = 0, ..., M-2), and values v (m) (m = 0, ..., M-2). Is output (step S112). For example, if M = 3, the selection unit 115 selects two values v (0) and v (1) and outputs values v (0) and v (1).

The value v (m) (m = 0,..., M−2) is input to the conversion unit 216. The conversion unit 216 sets a value corresponding to r and the value v (m) to z (r, v (m)), and M−1 values a _r (m) = P (z for each r. (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2), and (M-1) x R values a _r (m) = P (z (r, v (m))) (r = 0,..., R-1, m = 0,..., M-2) is output (step S213). For example, if M = 3, the conversion unit 216 has a _r (0) = P (z (r, v (0))), a _r (1) = P (z (r, v (1))) Output (r = 0, ..., R-1). When P (x) is a pseudorandom number generation function, the value a _r (m) is a pseudorandom number.

R values α _r ∈G (r = 0,..., R−1) output from the dividing unit 211 and (M−1) × R values a _r (output from the converting unit 216. m) = P (z (r, v (m))) (r = 0,..., R-1, m = 0,..., M-2) is input to the calculation unit 217. The calculation unit 217 calculates the values α _r and a _r (m) (r = 0,..., R−1, m = 0,..., M−2) from the values α _r . Generates the value a _r (M-1) = g (α _r , a _r (0), ..., a _r (M-2)), and R a _r (M-1) (r = 0,..., R-1) are output (step S214). For example, the map g (y, y (0), ..., y (M-2)) is y (M-1) = yy (0) -y (1) ...- y (M-2) If a (mod mu), calculation unit 217 _{a r (M-1) =} α r -a r (0) -a r (1) ...- a r (M-2) and (mod mu) It calculates and outputs the value a _r (M-1) obtained thereby. In this example, if M = 3, the calculation unit 217 calculates a _r (2) = α _r −a _r (0) −a _r (1) (mod μ), and the value a obtained thereby _r (2) Outputs (r = 0, ..., R-1).

M−1 values v (m) (m = 0,..., M−2) output from the selection unit 115 and values a _r (M−1) (r = 0) output from the calculation unit 217 ,..., R−1) are input to the variance value generation unit 218. The variance value generation unit 218 uses these values a _r (M-1), v (m) (r = 0, ..., R-1, m = 0, ..., M-2), Variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) (i = 0, ... ., N−1, r = 0,..., R−1) are generated and the variance value T _i (α _r ) is output (step S215).
Where a subset of the set A _r = {a _r (0), ..., a _r (M-1)} is _expressed as S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1). Among the elements constituting the variance value T _i (α _r ), (i, n _{i, r} ) (n _{i, r} ∈ {) where a _r (i, n _{i, r} ) ≠ a _r (M-1) 0, ..., N _{i, r} -1}, r = 0, ..., R-1), R v ₀ (i, n _{i, 0} ), ..., v _{R- 1} (i, n _{i, R-1} ) at least one (preferably R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) Only) a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (r′∈ {0, ..., R-1}) satisfying v _{r ′} (i, n _{i, r ′} ) ∈ {v (0),..., V (M−2)}. For example, a ₀ (i, n _{i, 0} ) ≠ a ₀ (M-1) (i, n _{i, 0} ) (n _{i, 0} ∈ {0, ..., N _{i, 0} -1} ) corresponding to _{v 0 (i, n i,} 0) _{is, a r (i, n i} , r) = P (z (r, v 0 (i, n i, 0))) satisfy v ₀ ( i, n _{i, 0} ) ∈ {v (0), ..., v (M-2)}. It is _{a r (i, n i,} r) ≠ a r (M-1) (i, n i, r) v 0 corresponding to the _{(i, n i, 0)} , ..., v R-1 Of (i, n _{i, R-1} ), values other than v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} are, for example, empty It may be a value or a parameter such as r or R. Among the elements constituting the variance value T _i (α _r ), a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r} ) (q _{i, r} ∈ { _{0, ..., n i, r} -1}, n i, r ≠ q i, v r (i corresponding to _r), q _{i, r)} is _{a r (i, q i,} r) = a _r (M-1).
The following is the dispersion value T _i (α _r ) (i = 0, for M = N = 3, K = 2, N _{i, r} = 2 and G = {0,1, ..., μ-1}. ..., 2, r = 0, ..., R-1). However, φ indicates a null value.
T ₀ (α ₀ ) = (v (0), v (1)), T ₁ (α ₀ ) = (v (1), a ₀ (2)), T ₂ (α ₀ ) = (a ₀ ( 2), v (0)),
T ₀ (α ₁ ) = φ, T ₁ (α ₁ ) = (a ₁ (2)), T ₂ (α ₁ ) = (a ₁ (2)),
T ₀ (α ₂ ) = φ, T ₁ (α ₂ ) = (a ₂ (2)), T ₂ (α ₂ ) = (a ₂ (2)), ...,
T ₀ (α _R-1 ) = φ, T ₁ (α _R-1 ) = (a _R-1 (2)), T ₂ (α _R-1 ) = (a _R-1 (2)) .. . (2)

Variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) (i = 0, ... ., N-1, r = 0, ..., R-1) are input to the output unit 112, and the output unit 112 outputs the variance T _i (α _r ) (i = 0, ..., N-1 , r = 0,..., R-1) are output (step S216). Each of the output distributed values T _i (α _r ) (i = 0,..., N−1, r = 0,..., R−1) is a distributed data converter 220-i (i = Provided for each of 0, ..., N-1). For example, the distributed value T _i (α _r ) is transmitted to the corresponding distributed data conversion device 220-i (FIG. 3) via a network or the like. The distributed value distributed value T _i (α _r ) provided to each of the distributed data converters 220-i (i = 0,..., N−1) is input to the input unit 121-i and is stored in the storage unit 123b−. stored in i.

<Distributed data conversion processing / distributed value output processing>
A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 220-i (i = 0,..., N−1) will be described. These processes may be executed by all the distributed data converters 220-i (i = 0,..., N-1), or K (K ≦ N) of the distributed data converters. 220-k (kε {0,..., N−1}) may be executed only.
As illustrated in FIG. 8, when each of the distributed data converters 220-i (i = 0,..., N−1) outputs a distributed value without converting the distributed value, the control unit 224- i instructs the storage unit 123b-i to read the dispersion value T _i (α _r ) without performing the conversion of the dispersion value (step S221-i). Receiving this instruction, the storage unit 123b-i reads and outputs the stored dispersion value T _i (α _r ). The variance value T _i (α _r ) is sent to the output unit 122-i, and the output unit 122-i outputs the variance value T _i (α _r ) (step S222-i). The output variance value T _i (α _r ) is provided to the data restoration device 230. For example, the variance value T _i (α _r ) is transmitted to the data restoration device 230 via a network or the like. When the distributed data conversion device 220-i (i = 0,..., N-1) outputs the distributed value without converting the distributed value, the distributed data conversion process and the distributed value output process are executed. All the distributed data converters 220-i (i = 0,..., N-1) output the distributed values without converting the distributed values.

On the other hand, when each of the distributed data converters 220-i (i = 0,..., N-1) performs the conversion of the variance value, the control unit 224-i performs the variance value conversion in order to convert the variance value. The storage unit 123b-i is instructed to read T _i (α _r ) (step S221-i). Receiving this instruction, the storage unit 123b-i reads the variance value T _i (α _r ).
Construct the read variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) Of the elements, v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} (r′∈ {0, ..., R-1}) Is input to the conversion unit 225-i. Construct the read variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) The element is v _r (i, q _{i, r} ) = a _r (M-1) (q _{i, r} ∈ {0, ..., N _{i, r} -1}, n _{i, r} ≠ q _{i, r} ) and is _{a r (i, q i,} r) = v r (i, q i, r) if ∈T _i containing (alpha _r), the _{a r (i, q i,} r) is converted variance The data is input to the generation unit 226-i.

The conversion unit 225-i converts the input value v _{r ′} (i, n _{i, r ′} ) (r′∈ {0, ..., R−1}) to a _r (i, n _{i, r} ). = P (z (r, v _{r '} (i, n _{i, r'} ))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1) is calculated, and the value a _r (i, n _{i, r} ) is output (step S223-i).

The conversion variance value generation unit 226-i includes the value a _r (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} −1) obtained by the conversion unit 225-i. }, r = 0, ..., R-1) and v _r (i, q _{i, r} ) = a _r (i, q _{i, r} ) = a _r read from the storage unit 123b-i (M-1) (q _{i, r} ∈ {0, ..., N _{i, r} -1}, n _{i, r} ≠ q _{i, r} ) and (if any) are input. The transform variance value generation unit 226-i converts the transform variance value S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} −1) composed of the input values. )} Is generated (step S224-i), and the transformed variance value S _i (α _r ) is stored in the storage unit 123c-i (step S225-i).
For example, in the example of Expression (2), the transform variance value S _i (α _r ) (i = 0, 1, 2, r = 0,..., R−1) is as follows.
S _i (α ₀ ) = (a ₀ (i mod 3), a ₀ (i + 1 mod 3)) (i = 0,1,2),
S ₀ (α _θ ) = φ, S ₁ (α _θ ) = S ₂ (α _θ ) = a _θ (2) (θ = 1, ..., R-1) ... (3)

The secret calculation unit 227-i receives the transform variance value S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N) stored in the storage unit 123c-i at a predetermined opportunity. _{i, r} -1)} is read, and the secret calculation is performed with the transformed variance value S _i (α _r ) as an input, and the variance value E _{i, r} = {e _r (i, 0), ..., e _r (i, N _{i, r} -1)} are output. The variance value E _{i, r} is output from the output unit 122-i and provided to the data restoration device 230. For example, the distributed value E _{i, r} is transmitted to the data restoration device 230 via a network or the like.

<Data restoration processing>
As illustrated in FIG. 9, the input unit 131 of the data restoration device 230 (FIG. 2B) receives any K dispersion values T _k (α _r ) (k∈ {0,. N-1}), or any of K dispersion values _{E k, r = {e r} (k, 0), ..., e r (k, N k -1)} (k∈ {0, ..., N-1}) is input (step S231). The control unit 234 determines whether the variance value T _k (α _r ) is input or the variance value E _{k, r} is input (step S232).

If it is determined in step S232 that the variance value T _k (α _r ) has been input, for each r, any K variance values T _k (α _r ) (k∈ {0,..., N− 1}, r = 0,..., R−1) are input to the conversion unit 235. The conversion unit 235 uses M−1 values a _r (m) for each of r using at least part of the variance values T _i (α _r ) (i = 0,..., N−1). ) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2) and the value a _r (m) ( r = 0,..., R-1, m = 0,..., M-2) are output (step S233). For example, when the variance values T ₀ (α _r ), T ₁ (α _r ) (r = 0,..., R−1) in Expression (2) are input to the conversion unit 235, the conversion unit 235 Using v (0), v (1) included in T ₀ (α ₀ ) = (v (0), v (1)), two values a _r (m) = P for each of _r (z (r, v (m))) (r = 0, ..., R-1, m = 0,1) is calculated.
The restoration unit 236 includes M−1 values a _r (m) (r = 0,..., R−1, m = 0,..., M−2) for each r, and an input unit. A value a _r (M−1) (r = 0,..., R−1) included in any of the variance values T _k (α _r ) input to 131 is input. The restoration unit 236 calculates α _r = f (a _r (0),..., A _r (M−1)) using these, and the obtained value α _r (r = 0,. , R-1) is output (step S234). For example, in the case of the variance value T _k (α _r ) in equation (2), the restoration unit 236 calculates α _r = a _r (0) + a _r (1) + a (2) (mod μ) The value α _r (r = 0, ..., R-1) obtained by is output.
The values α _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values α _r (r = 0,..., R−1) to generate a value αεG, and outputs the value α (step S235). For example, in the above-described dividing unit 211, the values α ₀ , α ₁ ,..., Α _R satisfying the value α satisfying α = α ₀ + μ · α ₁ + ... + μ ^R-1 · α _{R-1 -1} ∈ {0,1, ..., μ-1}, the coupling unit 237 determines that the value α _r (r = 0, ..., R-1) = α ₀ + μ · α ₁ + ... + μ ^R−1 · α _R−1 is calculated. The value α is input to the output unit 132, and the output unit 132 outputs the value α (step S236).

On the other hand, when it is determined in step S232 that the variance value E _{k, r} is input, K variance values E _{k, r} (k∈ {0,..., N−1}) are _{obtained for each r.} The data is input to the restoration unit 236. The restoration unit 236 uses the variance value E _{k, r} = { _er (k, 0), ..., _er (k, N _{k, r} -1)} (r = 0, ... for each r. , R-1, k∈ {0, ..., N-1}) M values e _r (0), ..., e _r (M-1) are obtained, and ε _r = _{f (e r (0),} ..., e r (M-1)) calculated and the result _{ε r (r = 0, ...} , R-1) outputs a (step S237).
R values ε _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values ε _r (r = 0,..., R−1) to generate a value εεG, and outputs the value ε (step S238). For example, in the above-described dividing unit 211, the values α ₀ , α ₁ ,..., Α _R satisfying the value α satisfying α = α ₀ + μ · α ₁ + ... + μ ^R-1 · α _{R-1 −1} ∈ {0,1, ..., μ-1}, the coupling unit 237 determines that the R value ε _r (r = 0, ..., R-1) to the value ε = ε ₀ + μ · ε ₁ + ... + μ ^R−1 · ε _R−1 is calculated. The value ε is input to the output unit 132, and the output unit 132 outputs the value ε (step S239).

<Features of this embodiment>
Also in this embodiment, the data amount of the distributed value can be greatly reduced as compared with the conventional secret sharing scheme.
That is, the variance value T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) of this embodiment is configured. At least one of the elements v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1) is v (m) (m = 0, ... ., M-2). Therefore, the data amount of the variance value can be reduced as compared with the conventional variance value including only the elements of the set G. As described in the first embodiment, how much the data amount of the variance value can be reduced depends on the difference between the data amount of v (m) and the data amount of elements of the set G.

For example, in the additive secret sharing described in Non-Patent Document 2, when data is distributed, the data distribution apparatus uses S _i (a _r ) = (a _i , a _{i + 1 mod 3} ) (i = 0, 1, 2) is generated and transmitted to the distributed data converter i, and the distributed data converter i stores S _i (a _r ). At the time of data restoration, the data restoration device receives a ₀ , a ₁ , and a ₂ together from any two distributed data conversion devices. In this case, for each r, the amount of communication data and the amount of stored data when data is distributed is 6 × L, and the amount of communication data when data is restored is 3 × L.
On the other hand, in this embodiment, M = N = 3, K = 2, _{Ni, r} = 2, G = {0,1, ..., μ-1} (environment equivalent to Non-Patent Document 2), value If the data amount of v (0) and v (1) can be ignored, the amount of communication data and the amount of stored data at the time of data distribution is 2 × L for each r, and the amount of data is less than the above additive secret sharing You can see that it is reduced to 1/3. It can be seen that the communication data amount at the time of data restoration of this embodiment in a similar environment is L, and the data amount is reduced to about 1/3 compared to the above-mentioned additive secret sharing.

Further, in this embodiment, R values a _r (m) = P (z (r, v (m))) (r = 0, ..., R-1) are generated from each value v (m). Therefore, it is possible to further reduce the amount of data when performing secret sharing of a plurality of values α _r (r = 0,..., R−1). Also, the distributed data conversion process in the distributed data conversion device can be used as an input for the secret calculation without restoring the original α and α _r from the distributed value obtained by the data distribution device. Can be generated and a secret calculation can be performed.

[Third Embodiment]
Next, a third embodiment of the present invention will be described. This embodiment is a modification of the first embodiment, and the data value of the distributed value is further reduced by diverting the same value v (n) to a plurality of secret shares. Below, it demonstrates centering on difference with embodiment mentioned above. The same reference numerals as those in the above-described embodiment are used for processing units and steps that are common to the above-described embodiment, and the description will be simplified.

In the third embodiment, N, R is an integer of 2 or _{more, N i (i = 0,} ..., N-1) is 1 or more N-1 an integer, G is a certain set Yes, P (x) is a mapping that moves the value corresponding to x to an element of set G, and y = f (y (0), ..., y (N-1)) is an element of set G A subset (y (0), ..., y (N-1)) of N values y (0), ..., y (N-1) is changed to a value y that is an element of the set G. G (y, y (0), ..., y (N-2)) satisfying y = f (y (0), ..., y (N-1)) A subset (y, y (0), ..., y (N-2)) consisting of N elements y, y (0), ..., y (N-2) This is the mapping to (N-1). Specific examples of the set G and mapping P (x) in the present embodiment are the same as the specific examples of the set G and mapping P (x) described in the first embodiment. Specific examples of the mapping y = f (y (0), ..., y (N-1)) and g (y, y (0), ..., y (N-2)) in this embodiment are as follows: It is as follows. For example, if the set G is an additive group, y = y (0) + ... + y (N-1) ∈G, y = -y (0) -...- y (N-1) ∈G , Y = y (0) -y (1) + y (2) -... + y (N-1) ∈G and so on map y = f (y (0), ..., y (N- 1)). For example, if the set G is an additive group consisting of representatives of residue classes modulo μ, for example, y = y (0) + ... + y (N-1) (mod μ) f (y (0), ..., y (N-1)). If the set G is a multiplicative group, for example, y = y (0) ···· y (N-1) ∈G, y = {y (0)} ^-1 ···· y {(N- 1)} ^-1 ∈G, y = y (0) ・ {y (1)} ^-1・ y (2) ・ {y (3)} ^-1・ ... ・ y (N-1) etc. The map y = f (y (0), ..., y (N-1)). The map g (y, y (0), ..., y (N-2)) has the above relationship to the map y = f (y (0), ..., y (N-1)). Fulfill. For example, if the map y = f (y (0), ..., y (N-1)) is y = y (0) + ... + y (N-1) (mod μ), then the map g (y, y (0), ..., y (N-2)) is y (N-1) = yy (0) -y (1) ...- y (N-2) (mod μ ). N ≦ R may be satisfied, or N ≧ R may be satisfied.

The secret sharing system according to the third embodiment includes a data distribution device, a data restoration device, and N distributed data conversion devices.
The data distribution apparatus of the present embodiment selects N-1 values v (n) (n = 0, ..., N-2), and sets values corresponding to r and value v (n) to z ( r, v (n)), and N-1 values for each r a _r (n) = P (z (r, v (n))) (r = 0, ..., R- 1, n = 0, ..., N-2) and the value a _r (N-1) for the value α _r (r = 0, ..., R-1) which is an element of the set G = g (α _r , a _r (0), ..., a _r (N-2)) and the value v (n) is the variance T _n (β) (n = 0, ..., N -2), and the value a _r (N-1) is the variance value T _N-1 (α _r ). The same “r and v (n) combination (r, v (n))” corresponds to the same z (r, v (n)). z (r, v (n)) and “a combination of r and v (n) (r, v (n))” may or may not correspond one-to-one. An example of z (r, v (n)) is a bit combination value of r and value v (n). The variance value T _n (β) (n = 0, ..., N-2) is provided to each of N-1 distributed data converters, for example, and the variance value T _N-1 (α _r ) is For example, it is provided to one distributed data converter.

The data restoration apparatus of the present embodiment uses a variance value T _n (β) (n = 0, ..., N-2), and N−1 values a _r (n) = P (z (r, v (n))) (r = 0, ..., R-1, n = 0, ..., N-2) and get the value a _r (n) (n = 0 , ..., N-2) and variance T _N-1 (α _r ) = a _r (N-1) and α _r = f (a _r (0), ..., a _r ( N-1)) (r = 0, ..., R-1) is obtained.

The distributed data conversion apparatus of the present embodiment provided with any one of the distributed values T _n (β) (n = 0,..., N−2) has the distributed value T _n (β) = v provided to itself. The value a _r (n) = P (z (r, v (n))) (r = 0,..., R−1) is obtained as the transformed variance value S _n (α _r ) from ( _n ). The transform variance value S _n (α _r ) thus obtained can be used as an input value for secret calculation. On the other hand, the dispersion value T _N-1 (α _r) is provided, distributed data conversion apparatus, the dispersion value T _N-1 (α _r) directly converting variance _{S N-1 (α r)} = T N-1 _Let (α _r ). The transform variance value S _i (α _r ) (i = 0,..., N−1) obtained in this way is used as an input value for secret calculation.

<Configuration>
As illustrated in FIG. 1, the secret sharing system 3 according to the third embodiment includes a data distribution device 310, N distributed data conversion devices 320-i (i = 0,..., N−1), and data. A restoration device 330 is included. The data distribution device 310 can provide information to the N distributed data conversion devices 320-i (i = 0,..., N-1) via a network or a portable recording medium. is there. Each of the N distributed data conversion devices 320-i (i = 0,..., N-1) can provide information to the data restoration device 330 via a network or a portable recording medium. Is possible.

  As illustrated in FIG. 10A, the data distribution apparatus 310 of this embodiment includes an input unit 111, a division unit 211, an output unit 112, a memory 113, a control unit 314, a selection unit 315, a conversion unit 316, a calculation unit 317, and a distribution. A value generation unit 318 is included. The data distribution apparatus 310 of this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data distribution apparatus 310 according to the present embodiment executes each process under the control of the control unit 314. Data input to the input unit 111 and data obtained in each process are stored in the memory 113, and the data stored in the memory 113 is read as necessary and used for other processes.

  As illustrated in FIG. 10B, the data restoration device 330 according to the present exemplary embodiment includes an input unit 131, an output unit 132, a memory 133, a control unit 334, a conversion unit 335, a restoration unit 336, and a combining unit 237. The data restoration device 330 of this embodiment is a special device configured by reading a special program into a known or dedicated computer, for example. Although not described below, the data restoration device 330 according to the present embodiment executes each process under the control of the control unit 334. Data input to the input unit 131 and data obtained in each process are stored in the memory 133, and the data stored in the memory 133 is read as necessary and used for other processes.

  As illustrated in FIG. 11A, the distributed data conversion apparatus 320-n (n = 0,..., N-2) of this embodiment includes an input unit 121-n, an output unit 122-n, memories 123a-n, The storage units 323b-i and 323c-n, the control unit 324-n, the transform variance value generation unit 326-n, and the secret calculation unit 327-n are included. As illustrated in FIG. 11B, the distributed data conversion apparatus 320- (N-1) of this embodiment includes an input unit 121- (N-1), an output unit 122- (N-1), and a memory 123a- (N- 1), a storage unit 323b- (N-1), a control unit 324- (N-1), and a secret calculation unit 327- (N-1). The distributed data conversion apparatus 320-i (i = 0,..., N−1) of this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the distributed data conversion apparatus 320-i according to the present embodiment executes each process under the control of the control unit 324-i. Data input to the input unit 121-i and data obtained in each process are stored in the memory 123a-i and the storage unit 323b-i, and data stored in the memory 123a-i and the storage unit 323b-i are necessary. Is read out and used for other processing.

<Data distribution processing>
As illustrated in FIG. 12, the value α to be secretly shared is input to the input unit 111 of the data distribution device 310 (FIG. 10A) (step S111).

The value α is input to the dividing unit 211. The dividing unit 211 divides the value α into R values α _r ∈G (r = 0,..., R-1) that are elements of the set G, and R values α _r ∈G (r = 0,..., R-1) are output (step S211).

  The selection unit 315 selects N−2 values v (n) (n = 0,..., N−2) and selects values v (n) (n = 0,..., N−2). Is output (step S312). The selection unit 315 may select N−2 values v (n) (n = 0,..., N−2) randomly at a time, or a plurality of values generated in advance and stored in the memory. N-2 values v (n) (n = 0,..., N-2) may be selected from the values according to a predetermined rule. For example, the data amount of each of the selected values v (n) (n = 0,..., N−2) is smaller than the data amount of the elements (one element) of the set G. It is desirable that the data amount of each of the values v (n) (n = 0,..., N−2) is sufficiently smaller than the data amount of the elements of the set G. In consideration of safety, the value v (n) is a value that makes it difficult to specify the value v (n) from the value a (n) and P (x) generated from the value v (n) ( Considering the attack by exhaustive search and the performance of the current computer, the value v (n) is preferably a random number of about 80 bits or more.

The value v (n) (n = 0,..., N−2) is input to the conversion unit 316. The conversion unit 316 sets the value corresponding to r and the value v (n) to z (r, v (n)), and N−1 values a _r (n) = P (z for each of _r. (r, v (n))) (r = 0, ..., R-1, n = 0, ..., N-2) and R × (N-1) The values a _r (n) (r = 0,..., R−1, n = 0,..., N−2) are output (step S313). When P (x) is a pseudorandom number generation function, the value a _r (n) is a pseudorandom number.

R values α _r εG (r = 0,..., R−1) output from the dividing unit 211 and R × (N−1) values a _r (n) output from the converting unit 316. ) (r = 0,..., R-1, n = 0,..., N-2) are input to the calculation unit 317. From these values α _r , a _r (n) (r = 0, ..., R-1, n = 0, ..., N-2), the calculation unit 317 calculates R values a _r ( N-1) = g (α _r , a _r (0), ..., a _r (N-2)) ∈G (r = 0, ..., R-1) _r (N-1) (r = 0,..., R-1) is output (step S314). For example, the map g (y, y (0), ..., y (N-2)) is y (N-1) = yy (0) -y (1) ...- y (N-2) In the case of (mod μ), the calculation unit 317 calculates a _r (N−1) = α _r −a _r (0) −a _r (1) ...− a _r (N−2) (mod μ) And a value a _r (N−1) (r = 0,..., R−1) obtained thereby is output.

N−1 values v (n) (n = 0,..., N−2) output from the selection unit 315 and values a _r (M−1) (r = 0) output from the calculation unit 317 ,..., R−1) are input to the variance value generation unit 318. The variance value generation unit 318 uses these values a _r (N−1), v (n) (n = 0,..., N−2), and uses the value v (n) as the variance value T _n (β ) (n = 0, ..., N-2) and the value a _r (N-1) is the variance T _N-1 (α _r ) (r = 0, ..., R-1) . β represents a set β = {α ₀ ,..., α _R-1 }, and the variance value generation unit 318 of the present embodiment sets a set β of values α _r (r = 0,..., R-1). N−1 dispersion values T _n (β) (n = 0, ..., N-2) are obtained for {{α ₀ , ..., α _R-1 }. The variance value generation unit 318 includes variance values T _n (β) = v (n) (n = 0,..., N−2), T _N−1 (α _r ) = a _r (N−1) ( r = 0,..., R-1) are output (step S315).

The variance T _n (β) (n = 0, ..., N-2), T _N-1 (α _r ) (r = 0, ..., R-1) is input to the output unit 112, The output unit 112 outputs variance values T _n (β) (n = 0, ..., N-2), T _N-1 (α _r ) (r = 0, ..., R-1) ( Step S316). Each of the output distributed values T _n (β) (n = 0,..., N-2) is assigned to each of the distributed data converters 320-n (n = 0,..., N-2). Provided. The output T _N-1 (α _r ) (r = 0,..., R-1) is provided to the distributed data converter 320- (N−1). For example, each distributed value is transmitted to the corresponding distributed data conversion device 320-i (FIGS. 11A and 11B) via a network or the like. The distributed value T _n (β) provided to each of the distributed data converters 320-n (n = 0,..., N-2) is input to the input unit 221-n and stored in the storage unit 323b-n. Is done. The distributed value T _N-1 (α _r ) provided to the distributed data converter 320-(N−1) is input to the input unit 221-(N−1) and stored in the storage unit 323 b-(N−1). Is done.

<Distributed data conversion processing / distributed value output processing>
A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 320-n (n = 0,..., N-2) will be described. These processes are executed by all the distributed data converters 320-n (n = 0,..., N−1).
As illustrated in FIG. 13, when each of the distributed data conversion devices 320-n (n = 0,..., N−2) outputs a distributed value without converting the distributed value, the control unit 324- n (FIG. 11A) instructs the storage unit 323b-n to read the dispersion value T _n (β) without converting the dispersion value (step S321-n). Receiving this instruction, the storage unit 323b-n reads and outputs the stored dispersion value T _n (β). The variance value T _n (β) is sent to the output unit 122-n, and the output unit 122-n provides the variance value T _n (β) to the data restoration device 330 (step S322-n). For example, the output unit 122-n is transmitted to the data restoration device 330 via a network or the like. When each of the distributed data converters 320-n (n = 0,..., N-2) outputs a distributed value without converting the distributed value, the distributed data conversion process and the distributed value output process are performed. All the distributed data converters 320-n (n = 0,..., N-2) to execute output the distributed values without performing the conversion of the distributed values.

On the other hand, when each of the distributed data converters 320-n (n = 0,..., N-2) performs the conversion of the distributed value, the control unit 324-n performs the distributed value in order to convert the distributed value. The storage unit 323b-n is instructed to read T _n (β) (step S321-n). Receiving this instruction, the storage unit 323b-n reads the stored dispersion value T _n (β). The variance value T _n (β) is input to the transformed variance value generation unit 326-n.

The transform variance value generation unit 326-n converts the variance value T _n (β) = v (n) to the value a _r (n) = P (z (r, v (n))) (r = 0,. , R-1) and R values a _r (n) (r = 0, ..., R-1) obtained thereby are converted into the variance value S _n (α _r ) (r = 0 ,..., R-1) (step S323-n). The transform variance value generation unit 326-n stores the transform variance value S _n (α _r ) = a _r (n) (r = 0,..., R−1) in the storage unit 323c-n (step S325— n).

The secret calculation unit 327-n obtains the transform variance value S _n (α _r ) = a _r (n) (r = 0,..., R−1) stored in the storage unit 323c-n at a predetermined opportunity. Reading, executing the secret calculation with the converted variance value S _n (α _r ) as input, and outputting the variance value E _{n, r} as the result of the calculation. The variance value En _{, r} is output from the output unit 122-n and provided to the data restoration device 330 via a network or the like. An example of a simple secret calculation is scalar multiplication in the additive group G of the transformation variance S _n (α _r ) = a _r (n), in this case E _{i, r} = υ · S _n (α _r ).

A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 320- (N-1) will be described.
When each of the distributed data converters 320-n (n = 0,..., N-2) outputs a distributed value without converting the distributed value, the distributed data converter 320- (N-1) ( The control unit 324- (N-1) of FIG. 11B reads the dispersion value T _N-1 (α _r ) (r = 0,..., R-1) from the storage unit 323b- (N-1). To the output unit 122- (N-1). The output unit 122- (N−1) outputs the dispersion value T _N-1 (α _r ) (r = 0,..., R−1). The variance value T _N-1 (α _r ) (r = 0,..., R-1) is provided to the data restoration device 330 via a network or the like.
On the other hand, even if each of the distributed data converters 320-n (n = 0,..., N-2) performs the conversion of the distributed values, the distributed data converter 320- (N-1) Do not change the value T _N-1 (α _r ) (r = 0, ..., R-1). The secret calculation unit 327- (N−1) receives the variance T _N−1 (α _r ) (r = 0,..., R−) stored in the storage unit 323b- (N−1) at a predetermined opportunity. 1) is read, a secret calculation is performed with the variance value T _N-1 (α _r ) as an input, and the variance value E _{N−1, r} , which is the calculation result, is output. The variance value E _{N−1, r} is output from the output unit 122- (N−1) and provided to the data restoration device 330 via a network or the like. In an example of a simple secret calculation, the variance value E _{N−1, r} = υ · T _N−1 (α _r ) (r = 0,..., R−1) is assumed.

<Data restoration processing>
As illustrated in FIG. 14, the input unit 131 of the data restoration device 330 (FIG. 10B) receives the variance values T _n (β) (n = 0,..., N−2), T _N−1 (α _r ) (r = 0, ..., R-1) or variance E _{i, r} (i = 0, ..., N-1, r = 0, ..., R-1) is input Is done. (Step S331). The control unit 334 determines whether the variance value T _n (β), T _N-1 (α _r ) is input or the variance value E _{i, r} is input (step S332).

If it is determined in step S332 that the variance value T _n (β), T _N-1 (α _r ) has been input, the variance value T _n (β) (n = 0,..., N-2) is The data is input to the conversion unit 335. The conversion unit 335 uses the variance value T _n (β) = v (n) (n = 0,..., N−2), and N−1 values a _r (n ) = P (z (r, v (n))) (r = 0, ..., R-1, n = 0, ..., N-2) and the value a _r (n) = P (z (r, v (n))) (r = 0,..., R-1, n = 0,..., N-2) is output (step S333).
The restoration unit 336 includes R × (N−1) values a _r (n) = P (z (r, v (n))) (r = 0,..., R−1, n = 0. , ..., N-2) and R T _N-1 (α _r ) = a _r (N-1) (r = 0, ..., R-1) input to the input unit 131 Are entered. The restoration unit 336 uses the value a _r (n) (n = 0,..., N−2) and the variance value T _N−1 (α _r ) = a _r (N−1) to obtain α _r = f (a _r (0), ..., a _r (N-1)) (r = 0, ..., R-1) and R values α _r (r = 0,..., R-1) is output (step S334). For example, the map y = f (y (0), ..., y (N-1)) is y = y (0) + y (1) ... + y (N-1) (mod μ) If there is, the restoration unit 336 calculates α _r = a _r (0) + a _r (1) + ... + a _r (N−1) (mod μ) and obtains the value α _r ( r = 0, ..., R-1) is output. R values α _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values α _r (r = 0,..., R−1) to generate a value α∈G, and outputs the value α (step S335). For example, in the above-described dividing unit 211, the values α ₀ , α ₁ ,..., Α _R satisfying the value α satisfying α = α ₀ + μ · α ₁ + ... + μ ^R-1 · α _{R-1 -1} ∈ {0,1, ..., μ-1}, the coupling unit 237 determines that the value α _r (r = 0, ..., R-1) = α ₀ + μ · α ₁ + ... + μ ^R−1 · α _R−1 is calculated. The value α is input to the output unit 132, and the output unit 132 outputs the value α (step S135).

On the other hand, if it is determined in step S332 that the variance value E _{i, r} is input, the variance value E _{i, r} (i = 0, ..., N-1, r = 0, ..., R- 1) is input to the restoration unit 336. The restoration unit 336 uses the variance values E _{i, r} (i = 0, ..., N-1, r = 0, ..., R-1) to ε _r = f (E _{0, r,.} .., E _{N-1, r} ) (r = 0, ..., R-1) and R values ε _r (r = 0, ..., R-1) ) Is output (step S336). For example, the map y = f (y (0), ..., y (N-1)) is y = y (0) + y (1) ... + y (N-1) (mod μ) In some cases, the restoration unit 336 calculates ε _r = E _{0, r} + E _{1, r} + ... + E _{N−1, r} (mod μ) and obtains the value ε _r (r = 0 , ..., R-1).
R values ε _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values ε _r (r = 0,..., R−1) to generate a value εεG, and outputs the value ε (step S337). For example, in the above-described dividing unit 211, the values α ₀ , α ₁ ,..., Α _R satisfying the value α satisfying α = α ₀ + μ · α ₁ + ... + μ ^R-1 · α _{R-1 −1} ∈ {0,1, ..., μ-1}, the coupling unit 237 determines that the R value ε _r (r = 0, ..., R-1) to the value ε = ε ₀ + μ · ε ₁ + ... + μ ^R−1 · ε _R−1 is calculated. The value ε is input to the output unit 132, and the output unit 132 outputs the value ε (step S137).

<Features of this embodiment>
In this embodiment, compared to the conventional secret sharing scheme, the data amount of the distributed value can be greatly reduced.
For comparison, assume the following simple additive secret sharing: In this simple additive secret sharing, R values a _r ∈G (r = 0,1, ..., R-1) are divided into N distributed values S (r, i ) ∈G (r = 0,1,…, R-1, i = 0, ..., N-1), and the secret is distributed to R distributed values S (0, i), ... , S (R-1, i) are transmitted to the i-th distributed data converter, and each distributed data converter stores them. At the time of data restoration, the data restoration device receives the distributed value S (r, i) ∈G (r = 0,1, ..., R-1, i = 0, ..., N-1) from all the distributed data conversion devices. And restore R values a _r ∈ G (r = 0, 1,..., R−1). If the data amount of the elements of the set G is L, the communication data amount and storage data amount at the time of data distribution and the communication data amount at the time of data restoration are all N × R × L.

On the other hand, in this embodiment, during data distribution, the data distribution device 310 uses the distribution values T _n (β) = v (n) (n = 0,..., N−2) and T _N−1 (α _r ). = a _r (N-1) is generated, the distributed value T _n (β) = v (n) is transmitted to the distributed data converter 320-n, and the distributed value is transmitted to the distributed data converter 320- (N−1). Transmit T _N-1 (α _r ) = a _r (N-1). The distributed data converter 320-n stores the distributed value T _n (β) = v (n), and the distributed data converter 320- (N−1) stores the distributed value T _N-1 (α _r ) = a _r ( N-1) is stored. At the time of data restoration, the data restoration device 330 uses the variance values T _n (β) = v (n) (n = 0,..., N−2) and T _N−1 (α _r ) = a _r (N− 1) is received, and R values a _r ∈ G (r = 0, 1,..., R−1) are restored. If the data amount of the value v (n) is set to ν and the data amount of the elements of the set G is set to L, the communication data amount and the storage data amount at the time of data distribution and the communication data amount at the time of data restoration are all (N -1) × ν + R × L. Therefore, if (N-1) × ν + R × L <N × R × L, that is, N−1 variance values T _n (β) (n = 0, ..., N-2) If the total amount of data (N-1) x ν is smaller than the total amount of data of the elements of R × (N-1) sets G, the amount of communication data and the amount of stored data in this form Is smaller than the simple additive secret sharing communication data amount and stored data amount described above. For example, if the data amount of each value v (n) is smaller than the data amount of the elements of the set G, the communication data amount and the storage data amount of the present embodiment are the simple additive secret sharing communication data amount described above. Or smaller than the amount of stored data. For example, if the amount of data for each value v (n) is negligible relative to the amount of data for the value a _r ∈G, the amount of communication data and the amount of stored data in the form can be This is about 1 / N of the amount of secret sharing communication data and stored data.
Further, the distributed data conversion processing in the distributed data conversion device can be used to obtain a converted distributed value that can be used as an input for the secret calculation without restoring the original value α _r from the distributed value obtained by the data distribution device. It can also generate and perform secret computations.

In this embodiment, at the time of data distribution, the data distribution device 310 transmits the distribution value T _n (β) = v (n) to the distributed data conversion device 320-n, and the distributed data conversion device 320- (N−1). The variance value T _N-1 (α _r ) = a _r (N-1) is transmitted. However, at the time of data distribution, the data distribution apparatus 310 may further transmit parameters such as R values and r = 0,..., R−1 to the distributed data conversion apparatus 320-n. In this embodiment, R is 2 or more, but R = 1 may be used. The configuration in that case can be obtained by setting N _i = 0 in the first embodiment.
[Fourth Embodiment]
Next, a fourth embodiment of the present invention will be described. This embodiment is a modification of the first embodiment, in which the elements of the set G included in the variance value of the first embodiment are further secretly shared to further reduce the data amount of the variance value. Below, it demonstrates centering on difference with the above-mentioned embodiment. The same reference numerals as those in the above-described embodiment are used for processing units and steps that are the same as those in the above-described embodiment, and the description will be simplified.

In this embodiment, M, N, K are integers of 2 or more, K ≦ N, _Ni (i = 0, ..., N-1) is an integer of 1 to M-1, G is a set, P (x) is a mapping that moves values corresponding to x to elements of the set G, and y = f (y (0), ..., y (M-1)) is A subset (y (0), ..., y (M-1)) consisting of M values y (0), ..., y (M-1) that are elements of the set G This is a mapping to the element value y, and g (y, y (0), ..., y (M-2)) is y = f (y (0), ..., y (M-1 )), A subset (y, y (0), ..., y (M- This is a mapping that moves 2)) to the value y (M-1). Set G of this form, map P (x), y = f (y (0), ..., y (N-1)) and g (y, y (0), ..., y (N- Specific examples of 2)) include the set G, the mapping P (x), y = f (y (0), ..., y (N-1)) and g (y, y) described in the first embodiment. (0), ..., y (N-2)) is the same as the specific example. M ≦ N or M ≧ N may be satisfied. M ≧ R or M ≦ R may be satisfied. N ≧ R or N ≦ R may be satisfied. K <N may be sufficient and K = N may be sufficient.

The secret sharing system according to the fourth embodiment includes a data sharing device, a data restoration device, and N distributed data conversion devices.
The data distribution apparatus of this embodiment selects M-1 values v (m) (m = 0, ..., M-2) and M-1 values a (m) = P (v ( m)) (m = 0, ..., M-2) and the value a (M-1) = g (α, a (0), ... , a (M-2)) and secretly distribute the value a (M-1) according to the (K, N) threshold secret sharing method U, and N distributed values U _i (a (M-1)) ( i = 0, ..., N-1), and the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N) _i -1), U _i (a (M-1))) (i = 0, ..., N-1).

However, a subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., a n-1), which is _{a (i, n i) ≠} a (M-1) (i, n i) (n i ∈ {0 ,. .., v corresponding to n _i -1}) is _(i, n i) are ^{P -1 (a (i, n} i)), in _{a (i, q i) =} a (M-1) V (i, q _i ) corresponding to a certain (i, q _i ) (q _i ∈ {0, ..., N _i -1}) is an empty value. In addition, any method may be used as the (K, N) threshold secret sharing method U, but the data amount of one distributed value U _i (a (M−1)) is one in the set G. It is desirable to use a method that is smaller than the data amount of the element. For example, the method described in Reference 1 “H. Krawczyk,“ Secret sharing made short, ”CRYPTO'93, pp.136-146, 1993.” is used as the (K, N) threshold secret sharing scheme U. Desirable (details will be described later). In the case of the method of Reference Document 1, the data amount of one variance value U _i (a (M−1)) is about 1 / K of the data amount of one element of the set G.

The data restoration apparatus according to the present embodiment uses M−1 values a (m) = P (v (v ()) using at least a part of the variance values T _i (α) (i = 0,..., N−1). m)) (m = 0, ..., M-2), and K different variance values U _k included in the variance T _i (α) (i = 0, ..., N-1) The value a (M-1) is obtained from (a (M-1)) (k∈ {0, ..., N-1}) and the value a (m) (m = 0, ... , M-2) and the value a (M-1) to obtain α = f (a (0), ..., a (M-1)).

Each of the distributed data conversion apparatuses of the present embodiment has a distributed value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1))) (i = 0, ..., N-1), (i, n _i ) (i, n _i ) (n _the value a (i, n _i ) = P (v (i, n _i ) for v (i, n _i ) ∈T _i (α) corresponding to _i ∈ {0, ..., N _i -1}) ), And K different variance values U _k (a (M-1)) (k∈ {0, .N) included in the variance values T _i (α) (i = 0, ..., N-1). . ,, N-1}) to obtain a value a (M-1), and S _i (α) including at least one of the obtained value a (i, n _i ) and value a (M-1) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., N-1) is obtained as a transformation variance value. Such a transformed variance value S _i (α) is used as an input value for secret calculation.

In this embodiment, preferably, the data amount of N _i −1 v (i, j) and U _i (a (M−M−) with respect to (i, j) where a (i, j) ≠ a (M−1). total value of the data amount of 1)) is less than the sum of the data amount of the elements N _i number of set G. More preferably, the data amount of each value v (m) is smaller than the data amount of the element (one element) of the set G, and the data amount of each variance value U _i (a (M-1)) is It is smaller than the data amount of the elements of the set G (one element).

<Configuration>
As illustrated in FIG. 15, the secret sharing system 4 of the fourth embodiment includes a data sharing device 410, N distributed data conversion devices 420-i (i = 0,..., N−1), and data. A restoration device 430 is included. The data distribution device 410 can provide information to the N distributed data conversion devices 420-i (i = 0,..., N-1) via a network or a portable recording medium. is there. Each of the N distributed data conversion devices 420-i (i = 0,..., N-1) can provide information to the data restoration device 430 via a network, a portable recording medium, or the like. Is possible. Each of the distributed data conversion apparatuses 420-i (i = 0,..., N−1) is connected to another distributed data conversion apparatus 420-i ′ (i ′ =) via a network or a portable recording medium. i, i'∈ {0, ..., N-1}).

  As illustrated in FIG. 16A, the data distribution apparatus 410 according to the present embodiment includes an input unit 111, an output unit 112, a memory 113, a control unit 414, a selection unit 115, a conversion unit 116, a calculation unit 117, an internal distribution unit 418, and A variance value generation unit 418 is included. The data distribution apparatus 410 of this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data distribution apparatus 410 according to the present embodiment executes each process under the control of the control unit 414. Data input to the input unit 111 and data obtained in each process are stored in the memory 113, and the data stored in the memory 113 is read as necessary and used for other processes.

  As illustrated in FIG. 16B, the data restoration device 430 of this embodiment includes an input unit 131, an output unit 132, a memory 133, a control unit 434, a conversion unit 135, a restoration unit 136, and an internal restoration unit 437. The data restoration device 430 of this embodiment is a special device configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data restoration device 430 according to the present embodiment executes each process under the control of the control unit 434. Data input to the input unit 131 and data obtained in each process are stored in the memory 133, and the data stored in the memory 133 is read as necessary and used for other processes.

  As illustrated in FIG. 17, the distributed data conversion apparatus 420-i (i = 0,..., N−1) according to the present embodiment includes an input unit 121-i, an output unit 122-i, a memory 123a-i, The storage units 123b-i and 123c-i, the control unit 424-i, the conversion unit 125-i, the conversion variance value generation unit 426-i, the internal restoration unit 427-i, and the secret calculation unit 127-i. The distributed data conversion apparatus 420-i of this embodiment is a special apparatus configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the distributed data conversion apparatus 420-i according to the present embodiment executes each process under the control of the control unit 424-i. Data input to the input unit 121-i and data obtained by each process are stored in the memory 123a-i and storage units 123b-i and 123c-i, and the memory 123a-i and storage units 123b-i and 123c-i are stored. The data stored in i is read as necessary and used for other processing.

<Data distribution processing>
As illustrated in FIG. 18, the value αεG to be secretly shared is input to the input unit 111 of the data distribution device 410 (FIG. 16A) (step S111). The selection unit 115 selects M-1 values v (m) (m = 0, ..., M-2), and values v (m) (m = 0, ..., M-2). Is output (step S112). The conversion unit 116 converts the input value v (m) (m = 0,..., M-2) to M−1 values a (m) = P (v (m)) (m = 0, .., M-2) are calculated, and the M-1 values a (m) (m = 0,..., M-2) are output (step S113). The value α input to the input unit 111 and the M−1 values a (m) (m = 0,..., M−2) output from the conversion unit 116 are input to the calculation unit 117. The calculation unit 117 calculates the value a (M-1) = g (α, a (0), ..., a from these values α, a (m) (m = 0, ..., M-2). (M-2)) εG is calculated, and the value a (M-1) is output (step S114).

The value a (M−1) output from the calculation unit 117 is input to the internal dispersion unit 418. The internal distribution unit 418 secretly distributes the value a (M−1) according to the (K, N) threshold value secret distribution method U and N distributed values U _i (a (M−1)) (i = 0,. .., N−1) and N generated dispersion values U _i (a (M−1)) (i = 0,..., N−1) are output (step S415). The internal dispersion unit 418 generates the dispersion value U _i (a (M−1)) using, for example, the method described in Reference Document 1. Illustrated is a method in which the internal distribution unit 418 generates secret N values U _i (τ) by secretly distributing the value τ = a (M−1) ∈G according to the (K, N) threshold secret sharing method U. To do.

[Example of (K, N) threshold secret sharing method U]
The internal distribution unit 418 selects random values d, d (0),..., D (N−2) ∈ {0, 1} ^ζ of ζ bits (for example, 128 bits), and d is a common key encryption The common key of the scheme is d (N-1) = dd (0) -...- d (N-2) mod 2 ^ζ . The internal distribution unit 418 encrypts the value τ using the common key d, and generates a ciphertext C (d, τ) in the common key cryptosystem. The internal distribution unit 418 converts the ciphertext C (d, τ) into C (0), C satisfying C (d, τ) = C (0) | C (1) | ... | C (K−1). Divide into (1), ..., C (K-1). However, C (0) | C (1) | ... | C (K-1) represents a bit combination of C (0), C (1), ..., C (K-1). The internal dispersion unit 418 has a K−1 order expression γ (x) = Σ _{k = 0} ^K−1 C (k) where C (k) (k = 0,..., K−1) is a kth order coefficient. ) · X ^k is determined, and N function values γ (i) mod q (i = 0,..., N−1) of the K−1 linear expression γ (x) are obtained. Here, q is a prime number larger than C (0), C (1),..., C (K-1). The internal dispersion unit 418 includes dispersion values U _i (τ) = (d (i mod N),..., D (i + N−2 (mod N)), γ (i) mod q) (i = 0 , ..., N-1). For example, when N = 3 and K = 2, the variance U _i (τ) in this example is U ₀ (τ) = (d (0), d (1), γ (0) mod q), U ₁ (τ) = (d (1), d (2), γ (1) mod q), U ₂ (τ) = (d (2), d (0), γ (2) mod q) . When N = 3 and K = 2, U ₀ (τ) = (d (0), d (1), C (0)), U ₁ (τ) = (d (1), d (2 ), C (1)), U ₂ (τ) = (d (2), d (0), C (0) (+) C (1)). However, C (0) (+) C (1) is an exclusive OR of C (0) and C (1) ([Example of (K, N) threshold secret sharing method U] end).

The M−1 values v (m) (m = 0,..., M−2) output from the selection unit 115 and the N dispersion values U _i (a ( M−1)) (i = 0,..., N−1) is input to the variance value generation unit 418. The variance value generation unit 418 uses these values v (m), U _i (a (M-1)) (m = 0, ..., M-2, i = 0, ..., N-1). N variance values T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1))) Generate (i = 0, ..., N-1) and output. However, a subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., a n-1), which is _{a (i, n i) ≠} a (M-1) (i, n i) (n i ∈ {0 ,. .., N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )), and a (i, q _i ) = a (M-1) V (i, q _i ) corresponding to a certain (i, q _i ) (q _i ε {0,..., N _i −1}) is a null value (step S416).
For example, the variance value generation unit 418 sets M = N and N _i = N−1, and generates the variance value T _i (α) (i = 0,..., N−1) as follows. To do.
T ₀ (α) = (v (1), v (2), ..., v (M-2), U ₀ (a (M-1))),
T ₁ (α) = (v (0), v (2), ..., v (M-2), U ₁ (a (M-1))), ...,
T _N-2 (α) = (v (0), v (1), ..., v (M-3), U _M-2 (a (M-1))),
T _M-1 (α) = (v (0), v (1), ..., v (M-3), v (M-2), U _M-1 (a (M-1))) ...(Four)

N variance values T _i (α) (i = 0,..., N−1) are input to the output unit 112, and the output unit 112 outputs N variance values T _i (α) (i = 0, ..., N-1) are output (step S416). Each of the output distributed values T _i (α) (i = 0,..., N−1) is respectively assigned to each of the distributed data converters 420-i (i = 0,..., N−1). Provided. For example, the distributed value T _i (α) is transmitted to the corresponding distributed data conversion apparatus 420-i (FIG. 17) via a network or the like. The distributed value T _i (α) provided to each of the distributed data converters 420-i (i = 0,..., N−1) is input to the input unit 421-i and stored in the storage unit 123b-i. Is done.

<Distributed data conversion processing / distributed value output processing>
A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 420-i (i = 0,..., N−1) will be described. These processes may be executed by all the distributed data converters 420-i (i = 0,..., N-1), or K (K ≦ N) distributed data converters among them. It may be executed only by 420-k (kε {0,..., N−1}). Further, the processing in step S424-i may be executed by all the distributed data conversion devices 420-i (i = 0,..., N-1), or some of the distributed data conversion devices. May be executed only.
As illustrated in FIG. 19, when each of the distributed data converters 420-i (i = 0,..., N−1) outputs a distributed value without converting the distributed value, the control unit 424- i instructs the storage unit 123b-i to read the dispersion value T _i (α) without performing the conversion of the dispersion value (step S421-i). Receiving this instruction, the storage unit 123b-i reads and outputs the stored dispersion value T _i (α). The variance value T _i (α) is sent to the output unit 122-i, and the output unit 122-i outputs the variance value T _i (α) (step S422-i). The output variance value T _i (α) is provided to the data restoration device 430. For example, the variance value T _i (α) is transmitted to the data restoration device 430 via a network or the like. When the distributed data converter 420-i (i = 0,..., N-1) outputs a distributed value without converting the distributed value, a distributed data conversion process and a distributed value output process are executed. All the distributed data converters 420-i (i = 0,..., N−1) output the distributed values without performing the conversion of the distributed values.

On the other hand, when each of the distributed data converters 420-i (i = 0,..., N−1) performs the conversion of the distributed value, the control unit 424-i uses the distributed value to convert the distributed value. T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1))) The storage unit 123b-i is instructed. Receiving this instruction, the storage unit 123b-i reads the variance value T _i (α). Read variance T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1) )) Corresponds to (i, n _i ) (n _i ∈ {0, ..., N _i -1}) where a (i, n _i ) ≠ a (M-1) The value v (i, n _i ) εT _i (α) (n _i ε {0,..., N _i −1}) is input to the conversion unit 125-i. Read variance T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1) U _i (a (M−1)) included in)) is input to the internal restoration unit 427-i.
Conversion unit 125-i is input value v _(i, n i) from the values _{a (i, n i) =} P (v (i, n i)) is calculated, and the value a (i, n _i ) Is output (step S123-i).

In addition to the distributed value T _i (α) read from the storage unit 123b-i, the internal restoration unit 427-i includes another distributed data conversion device 420-i ′ (i ′ ≠ i, i′∈ {0 ,..., N−1}) is also inputted as a variance value T _{i ′} (α) transmitted via the network (NW) or the like. The internal restoration unit 427-i calculates the value a (M) from the K different variance values U _k (a (M−1)) (k∈ {0,... -1) is restored, and the obtained value a (M-1) is output (step S424-i). For example, when the variance value U _k (a (M−1)) is generated by the method described in [Example of (K, N) threshold secret sharing method U], the internal restoration unit 427-i U _k (a (M-1)) = (d (k mod N), ..., d (k + N-2 (mod N)), γ (k)) contains K γ (k) K-1 order γ (x) = Σ _{k = 0} ^K-1 C (k) · x ^k coefficient C modulo q using (k∈ {0, ..., N-1}) Find (0), C (1), ..., C (K-1) and use ciphertext C (d, a (M-1)) = C (0) | C (1) | ... | Generate C (K-1). The coefficients C (0), C (1), ..., C (K-1) are (x, γ (x)) = (k, γ (k)) It is obtained by solving the equation obtained by substituting N = 3, K = 2, U ₀ (τ) = (d (0), d (1), C (0)), U ₁ (τ) = (d (1), d (2), C (1)), U ₂ (τ) = (d (2), d (0), C (0) (+) C (1)), C (0), C (1) , C (0) (+) C (1), C (0), C (1) can be obtained from any two of them. The internal restoration unit 427-i generates K variance values U _k (a (M−1)) = (d (k mod N),... (k)) contains d (k mod N), ..., d (k + N-2 (mod N)) and the common key d = d (0) + ... + d (N-1) mod 2 ^ζ is calculated, and the value a (M−1) is restored by decrypting the ciphertext C (d, a (M−1)) using the common key d.

The conversion variance value generation unit 426-i includes a value a (i, n _i ) (n _i ε {0, ..., N _i -1}) obtained by the conversion unit 125-i, and an internal restoration unit. The value a (M-1) obtained at 427-i and (if present) are input. The transformed variance generation unit 426-i includes S _i (α) = {a (i, 0), including at least one of the obtained value a (i, n _i ) and value a (M−1), ..., a (i, N _i -1)} is generated as a transformed variance value (step S424-i), and the transformed variance value S _i (α) is stored in the storage unit 123c-i (step S425-). i). An example of the transformed variance value S _i (α) corresponding to the variance value T _i (α) in equation (4) is as follows.
S ₀ (α) = (a (1), a (2), ..., a (M-2), a (M-1)),
S ₁ (α) = (a (0), a (2), ..., a (M-2), a (M-1)), ...,
S _N-2 (α) = (a (0), a (1), ..., a (M-3), a (M-1)),
S _M-1 (α) = (a (0), a (1), ..., a (M-3), a (M-2))

The secret calculation unit 127-i receives the transformation variance value S _i (α) = {a (i, 0), ..., a (i, N _i −1) stored in the storage unit 123c-i at a predetermined opportunity. )}, A secret calculation (for example, a linear operation) with the transformed variance value S _i (α) as an input is executed, and the variance value E _i = {e (i, 0),. e (i, N _i -1)} is output. The variance value E _i is output from the output unit 122-i and provided to the data restoration device 430.

<Data restoration processing>
As illustrated in FIG. 20, any K variance values T _k (α) (k∈ {0,..., N−1}) are input to the input unit 131 of the data restoration device 430 (FIG. 16B). Or, any K variance values E _k = {e (k, 0), ..., e (k, N _k -1)} (k∈ {0, ..., N-1}) Input (step S431). The control unit 434 determines whether the variance value T _k (α) is input or the variance value E _k is input (step S432).

If it is determined in step S432 that the variance value T _k (α) has been input, any K variance values T _k (α) (k∈ {0,..., N−1}) are converted into the conversion unit. 135 and the input to the internal restoration unit 437, the conversion unit 135 uses M−1 pieces using at least a part of the K dispersion values T _k (α) (k∈ {0,..., N−1}). The value a (m) = P (v (m)) (m = 0, ..., M-2) and the value a (m) (m = 0, ..., M-2) Output (step S133). The internal restoration unit 437 uses the K different variance values U _k (a (M−1)) (k∈ {0,..., N−1}) included in the K variance values T _k (α). The value a (M-1) is restored, and the value a (M-1) is output (step S433). M−1 values a (m) = P (v (m)) (m = 0,..., M−2) and a value a (M−1) are input to the restoration unit 136. . The restoration unit 136 calculates α = f (a (0),..., A (M−1)) using these, and outputs the obtained value α (step S134). The value α is input to and output from the output unit 132 (step S135).

On the other hand, if it is determined in step S432 that the variance value E _k has been input, K variance values E _k (kε {0,..., N−1}) are input to the restoration unit 136. The restoration unit 136 uses K variance values E _k = {e (k, 0), ..., e (k, N _k -1)} (k∈ {0, ..., N-1}). Obtain M values e (0), ..., e (M-1) consisting of the elements of, and calculate ε = f (e (0), ..., e (M-1)) As a result, ε is output (step S136). The result ε is input to the output unit 132 and is output therefrom (step S137).

<Features of this embodiment>
In this embodiment, compared to the conventional secret sharing scheme, the data amount of the distributed value can be greatly reduced. That is, the element v (i, n) that constitutes the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1)) of the present embodiment. 0), v (i, 1), ..., v (i, N _i -1) is at least one of v (m) (m = 0, ..., M-2) . Therefore, the data amount of the variance value can be reduced as compared with the conventional variance value including only the elements of the set G. Furthermore, the variance value T _i (α) of this embodiment includes the secret sharing value U _i (a (M−1)) instead of a (M−1) that is an element of the set G. Therefore, if each data amount of the secret sharing value U _i (a (M−1)) is smaller than the data amount of the elements (one element) of the set G, the data amount is set to be larger than that of the first embodiment. Can be reduced.

For example, the data amount of the elements of the set G is L, N = M = 3, K = 2, and the variance value in the first embodiment is T ₀ (α) = (v (1), a (M−1)) , T ₁ (α) = (v (0), a (M-1)), T ₂ (α) = (v (0), v (1)), the values v (0), v ( If the data amount of 1) can be ignored, the communication data amount and the storage data amount at the time of data distribution are 2 × L, and the communication data amount at the time of data restoration is L. On the other hand, the data amount of the elements of the set G is L, N = M = 3, K = 2, and the variance value in the fourth embodiment is T ₀ (α) = (v (1), U ₀ (a (M− 1))), T ₁ (α) = (v (0), U ₁ (a (M-1))), T ₂ (α) = (v (0), v (1), U ₂ (a (M-1))), if the data volume of values v (0) and v (1) can be ignored, the amount of communication data and the amount of stored data at the time of data distribution will be 1.5 × L, and data restoration The amount of communication data at that time is L. Therefore, it can be seen that the amount of communication data and the amount of stored data when data is distributed are further reduced to 3/4.

  Furthermore, the distributed data conversion process in the distributed data conversion device generates a converted distributed value that can be used as an input for the secret calculation without restoring the original value α from the distributed value obtained by the data distribution device. It is also possible to execute a secret calculation.

[Fifth Embodiment]
Next, a fifth embodiment of the present invention will be described. The present embodiment is a modification of the second and fourth embodiments. In the fourth embodiment, the same value v (m) is diverted to a plurality of secret shares to further reduce the data amount of the distributed values. Below, it demonstrates centering on difference with the above-mentioned embodiment. The same reference numerals as those in the above-described embodiment are used for processing units and steps that are the same as those in the above-described embodiment, and the description will be simplified.
In the fifth embodiment, M, N, K, and R are integers greater than or equal to 2, K ≦ N, and N _{i, r} (i = 0, ..., N-1, r = 0,... ., R-1) is an integer greater than or equal to 1 and less than or equal to M-1, G is a set, P (x) is a mapping that transfers a value corresponding to x to an element of set G, and y = f A subset (y (0), ..., y (M-1)) of M values y (0), ..., y (M-1) where (y (0), ..., y (M-1)) is an element of the set G 0), ..., y (M-1)) to a value y that is an element of the set G, and g (y, y (0), ..., y (M-2)) Consists of M y, y (0), ..., y (M-2) elements of set G satisfying y = f (y (0), ..., y (M-1)) This is a mapping that transfers the subset (y, y (0), ..., y (M-2)) to the value y (M-1). Set G of this form, map P (x), y = f (y (0), ..., y (N-1)) and g (y, y (0), ..., y (N- Specific examples of 2)) include the set G, the mapping P (x), y = f (y (0), ..., y (N-1)) and g (y, y) described in the first embodiment. (0), ..., y (N-2)) is the same as the specific example. M ≦ N or M ≧ N may be satisfied. M ≧ R or M ≦ R may be satisfied. N ≧ R or N ≦ R may be satisfied. K <N may be sufficient and K = N may be sufficient.

The secret sharing system according to the fifth embodiment includes a data sharing device, a data restoration device, and N distributed data conversion devices.
The data distribution apparatus of this embodiment selects M-1 values v (m) (m = 0, ..., M-2), and sets values corresponding to r and value v (m) to z ( r, v (m)) and M-1 values for each r a _r (m) = P (z (r, v (m))) (r = 0, ..., R- 1, m = 0, ..., M-2) and the value a _r (M-1) for the value α _r (r = 0, ..., R-1) which is an element of the set G = g (α _r , a _r (0), ..., a _r (M-2)) and secretly distribute the value a _r (M-1) according to the (K, N) threshold secret sharing method U For each r, N dispersion values U _i (a _r (M-1)) (i = 0, ..., N-1) are obtained, and the dispersion values T _i (α _r ) = (v _r ( i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1), U _i (a _r (M-1))) (i = 0, ... , N-1, r = 0, ..., R-1). Where a subset of the set A _r = {a _r (0), ..., a _r (M-1)} is S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1) and a _r (i, n _{i, r} ) ≠ a _r (M-1) (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1 ) Corresponding to R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) (preferably R v ₀ ( i, n _{i, 0} ), ..., v _R-1 (only _{one of} i, n _{i, R-1} )) is a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (r′∈ {0, ..., R-1}) satisfying v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} and a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r} ) (q _{i, r} ∈ {0 , ..., N _{i, r} −1}, n _{i, r} ≠ q _{i, r} ), v _r (i, q _{i, r} ) is null.

The data restoration apparatus of the present embodiment uses M−1 values a for each of r using at least a part of the variance values T _i (α _r ) (i = 0,..., N−1). _r (m) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2) and the variance T _i ( α _r ) (i = 0, ..., N-1) K different variances U _k (a _r (M-1)) (k∈ {0, ..., N-1} ) To obtain the value a _r (M-1), the value a _r (m) (m = 0, ..., M-2) obtained by the second conversion unit and the first internal restoration unit. Using the value a _r (M-1), α _r = f (a _r (0), ..., a _r (M-1)) is obtained.

Each of the distributed data conversion apparatuses of the present embodiment includes v _{r ′} (i, n _{i, r ′} ) (r ′ included in the distributed value T _i (α _r ) (r = 0,. ∈ {0, ..., R-1}) value a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} )))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}), and K different variances included in the variance T _i (α _r ) (i = 0, ..., N-1) A value a _r (M-1) is obtained from U _k (a _r (M-1)) (k∈ {0, ..., N-1}), and the value a _r ( i, n _{i, r} ) and the value a _r (M−1) obtained by the second internal restoration unit include S _i (α _r ) = {a _r (i, 0),. ., a _r (i, N _{i, r} −1)} (i = 0,..., N−1) are obtained as transformation variance values. The transform variance value S _i (α _r ) thus obtained is used as an input value for secret calculation.

Preferably, in this embodiment, the data amount of N _{i, r} −1 v _r (i, j) and U _{i for} (i, j) where a _r (i, j) ≠ a _r (M−1). The total value of the data amount of (a _r (M−1)) is smaller than the total value of the data amount of the elements of N _{i, r} sets G. More preferably, the data amount of each value v (m) is smaller than the data amount of the element (one element) of the set G, and the data amount of each variance value U _i (a _r (M-1)) Is smaller than the data amount of the elements of set G. Even more preferably, the data amount of each value v (m) is negligible with respect to the data amount of the elements of the set G (for example, (data amount of each of v (m)) / (set G The amount of data in the element) ≦ 80/10 ⁶ ).

<Configuration>
As illustrated in FIG. 15, the secret sharing system 5 of the fifth embodiment includes a data distribution device 510, N distributed data conversion devices 520-i (i = 0,..., N−1), and data. A restoration device 530 is included. The data distribution device 510 can provide information to the N distributed data conversion devices 520-i (i = 0,..., N-1) via a network, a portable recording medium, or the like. is there. Each of the N distributed data conversion devices 520-i (i = 0,..., N-1) can provide information to the data restoration device 530 via a network, a portable recording medium, or the like. Is possible. Each of the distributed data conversion devices 520-i (i = 0,..., N−1) is connected to another distributed data conversion device 520-i ′ (i ′ =) via a network or a portable recording medium. i, i'∈ {0, ..., N-1}).

  As illustrated in FIG. 16A, the data distribution apparatus 510 of this embodiment includes an input unit 111, an output unit 112, a memory 113, a division unit 211, a control unit 514, a selection unit 115, a conversion unit 216, a calculation unit 217, a distribution value. A generation unit 518 and an internal dispersion unit 518 are included. The data distribution apparatus 510 of this embodiment is a special apparatus configured by reading a special program into a known or dedicated computer, for example. Although not described below, the data distribution apparatus 510 of the present embodiment executes each process under the control of the control unit 514. Data input to the input unit 111 and data obtained in each process are stored in the memory 113, and the data stored in the memory 113 is read as necessary and used for other processes.

  As illustrated in FIG. 16B, the data restoration device 530 of this embodiment includes an input unit 131, an output unit 132, a memory 133, a control unit 234, a conversion unit 235, a restoration unit 236, a combining unit 237, and an internal restoration unit 537. . The data restoration device 530 of this embodiment is a special device configured by, for example, reading a special program into a known or dedicated computer. Although not described below, the data restoration device 530 according to this embodiment executes each process under the control of the control unit 534. Data input to the input unit 131 and data obtained in each process are stored in the memory 133, and the data stored in the memory 133 is read as necessary and used for other processes.

  As illustrated in FIG. 17, the distributed data conversion apparatus 520-i (i = 0,..., N−1) of this embodiment includes an input unit 121-i, an output unit 122-i, a memory 123a-i, The storage units 123b-i and 123c-i, the control unit 524-i, the conversion unit 225-i, the conversion variance value generation unit 526-i, the internal restoration unit 527-i, and the secret calculation unit 227-i. The distributed data conversion apparatus 520-i of this embodiment is a special apparatus configured by reading a special program into a known or dedicated computer, for example. Although not described below, the distributed data conversion apparatus 520-i according to the present embodiment executes each process under the control of the control unit 524-i. Data input to the input unit 121-i and data obtained in each process are stored in the memory 123a-i, and the data stored in the memory 123a-i is read as necessary and used for other processes. Is done.

<Data distribution processing>
As illustrated in FIG. 21, the value α to be secretly shared is input to the input unit 111 of the data distribution device 510 (FIG. 16A) (step S111). The value α is input to the dividing unit 211. The dividing unit 211 divides the value α into R values α _r ∈G (r = 0,..., R-1) that are elements of the set G, and R values α _r ∈G (r = 0,..., R-1) are output (step S211). The selection unit 115 selects M-1 values v (m) (m = 0, ..., M-2), and values v (m) (m = 0, ..., M-2). Is output (step S112). The value v (m) (m = 0,..., M−2) is input to the conversion unit 216. The conversion unit 216 sets a value corresponding to r and the value v (m) to z (r, v (m)), and M−1 values a _r (m) = P (z for each r. (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2), and (M-1) x R values a _r (m) = P (z (r, v (m))) (r = 0,..., R-1, m = 0,..., M-2) is output (step S213). R values α _r ∈G (r = 0,..., R−1) output from the dividing unit 211 and (M−1) × R values a _r (output from the converting unit 216. m) = P (z (r, v (m))) (r = 0,..., R-1, m = 0,..., M-2) is input to the calculation unit 217. The calculation unit 217 calculates the values α _r and a _r (m) (r = 0,..., R−1, m = 0,..., M−2) from the values α _r . Generates the value a _r (M-1) = g (α _r , a _r (0), ..., a _r (M-2)), and R a _r (M-1) (r = 0,..., R-1) are output (step S214).

The value a _r (M−1) output from the calculation unit 217 is input to the internal dispersion unit 518. The internal distribution unit 518 secretly distributes the value a _r (M−1) according to the (K, N) threshold value secret distribution method U, and N distributed values U _i (a _r (M−1)) for each of _r. (i = 0, ..., N-1, r = 0, ..., R-1), and the generated N × R variance values U _i (a _r (M-1)) ( i = 0,..., N-1, r = 0,..., R-1) are output (step S515). The internal distribution unit 518 executes the above-described [exemplification of (K, N) threshold secret sharing method U], for example, with τ = a _r (M−1).

M−1 values v (m) (m = 0,..., M−2) output from the selection unit 115 and N × R distribution values U _i ( a _r (M−1)) (i = 0,..., N−1, r = 0,..., R−1) are input to the variance value generation unit 518. The variance value generation unit 518 outputs these values v (m), U _i ( _ar (M-1)) (m = 0, ..., M-2, i = 0, ..., N-1). , r = 0, ..., R-1) and the variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i , N _{i, r} -1), U _i (a _r (M-1))) (i = 0, ..., N-1, r = 0, ..., R-1) Output. Where a subset of the set A _r = {a _r (0), ..., a _r (M-1)} is S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1) and a _r (i, n _{i, r} ) ≠ a _r (M-1) (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1 ) Corresponding to R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) (preferably R v ₀ ( i, n _{i, 0} ), ..., v _R-1 (only _{one of} i, n _{i, R-1} )) is a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (r′∈ {0, ..., R-1}) satisfying v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} and a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r} ) (q _{i, r} ∈ {0 _{, ..., n i, r -1} }, n i, r ≠ q i, v r (i corresponding to _r), q _{i, r)} is empty value (step S516). For example, a ₀ (i, n _{i, 0} ) ≠ a ₀ (M-1) (i, n _{i, 0} ) (n _{i, 0} ∈ {0, ..., N _{i, 0} -1} ) corresponding to _{v 0 (i, n i,} 0) _{is, a r (i, n i} , r) = P (z (r, v 0 (i, n i, 0))) satisfy v ₀ ( i, n _{i, 0} ) ∈ {v (0), ..., v (M-2)}. It is _{a r (i, n i,} r) ≠ a r (M-1) (i, n i, r) v 0 corresponding to the _{(i, n i, 0)} , ..., v R-1 Of (i, n _{i, R-1} ), values other than v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} are, for example, empty It may be a value or a parameter such as r or R.
For example, the variance value generation unit 518 sets M = N and N _i = N−1, and sets the variance values T _i (α _r ) (i = 0,..., N−1) as follows. Generate.
T ₀ (α ₀ ) = (v (1), v (2), ..., v (M-2), U ₀ (a ₀ (M-1))), T ₀ (α ₁ ) = ( U ₀ (a ₁ (M-1))), ..., T ₀ (α _R-1 ) = (U ₀ (a _R-1 (M-1))), ..., T _M-1 (α ₀ ) = (v (0), v (1), ..., v (M-3), v (M-2), U _M-1 (a ₀ (M-1))) ,. .., T _M-1 (α _R-1 ) = (U _M-1 (a _R-1 (M-1))
...(Five)

Variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1), U _i (a _r (M -1))) (i = 0, ..., N-1, r = 0, ..., R-1) are input to the output unit 112, which outputs the variance T _i (α _r ) (i = 0,..., N-1, r = 0,..., R-1) are output (step S516). Each of the output distributed values T _i (α _r ) (i = 0,..., N−1, r = 0,..., R−1) is a distributed data converter 520-i (i = Provided for each of 0, ..., N-1). For example, the distributed value T _i (α _r ) is transmitted to the corresponding distributed data conversion device 520-i (FIG. 17) via a network or the like. The distributed value distributed value T _i (α _r ) provided to each of the distributed data converters 520-i (i = 0,..., N−1) is input to the input unit 121-i and is stored in the storage unit 123b−. stored in i.

<Distributed data conversion processing / distributed value output processing>
A distributed data conversion process and a distributed value output process executed by the distributed data conversion apparatus 520-i (i = 0,..., N−1) will be described. These processes may be executed by all the distributed data converters 520-i (i = 0,..., N-1), or K (K ≦ N) distributed data converters among them. It may be executed only with 520-k (kε {0,..., N−1}). Further, the processing in step S524-i may be executed by all the distributed data conversion devices 520-i (i = 0,..., N-1), or some of the distributed data conversion devices. May be executed only.
As illustrated in FIG. 22, when each of the distributed data converters 520-i (i = 0,..., N−1) outputs a distributed value without converting the distributed value, the control unit 524- i instructs the storage unit 123b-i to read the dispersion value T _i (α _r ) without performing the conversion of the dispersion value (step S521-i). Receiving this instruction, the storage unit 523b-i reads and outputs the stored dispersion value T _i (α _r ). The variance value T _i (α _r ) is sent to the output unit 122-i, and the output unit 122-i outputs the variance value T _i (α _r ) (step S522-i). The output variance value T _i (α _r ) is provided to the data restoration device 530. For example, the variance value T _i (α _r ) is transmitted to the data restoration device 530 via a network or the like. When the distributed data converter 520-i (i = 0,..., N-1) outputs a distributed value without converting the distributed value, a distributed data conversion process and a distributed value output process are executed. All the distributed data converters 520-i (i = 0,..., N−1) output the distributed values without performing the conversion of the distributed values.

On the other hand, when each of the distributed data conversion devices 520-i (i = 0,..., N-1) performs the conversion of the distributed value, the control unit 524-i The storage unit 123b-i is instructed to read T _i (α _r ) (step S521-i). Receiving this instruction, the storage unit 123b-i reads the variance value T _i (α _r ).
Read variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1), U _i ( a _r (M-1))), v _{r ′} (i, n _{i, r ′} ) ∈ {v (0), ..., v (M-2)} (r′∈ {0, ..., R-1}) is input to the conversion unit 225-i. Read variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _i -1), U _i (a _r U _i ( _ar (M−1)) included in (M−1))) is input to the internal restoration unit 527-i.

The conversion unit 225-i converts the input value v _{r ′} (i, n _{i, r ′} ) (r′∈ {0, ..., R−1}) to a _r (i, n _{i, r} ). = P (z (r, v _{r '} (i, n _{i, r'} ))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1) is calculated, and the value a _r (i, n _{i, r} ) is output (step S223-i).

In addition to the distributed value T _i (α _r ) read from the storage unit 123b-i, the internal restoration unit 527-i has another distributed data conversion device 520-i ′ (i ′ ≠ i, i′∈ { 0,..., N−1}) is also inputted as a variance value T _{i ′} (α _r ) transmitted via the network (NW) or the like. Internal restorer 527-i, the dispersion value K different for each of the _{r U k (a r (M} -1)) (k∈ {0, ..., N-1}) from the value a _r (M -1) (r = 0, ..., R-1) is restored, and the obtained value a _r (M-1) (r = 0, ..., R-1) is output (step S524). -I)

The transformation variance value generation unit 526-i includes the value a _r (i, n _i ) (n _i ε {0, ..., N _i -1}) obtained by the transformation unit 125-i and internal restoration. The value a _r (M−1) obtained in the part 527-i and (if present) are input. The transformed variance generation unit 526-i includes S _i (α _r ) = {a _r (including at least one of the value a _r (i, n _i ) and the value a _r (M−1) for each _r. i, 0), ..., a _r (i, N _i -1)} are generated as transform variance values (step S524-i), and the transform variance value S _i (α _r ) is stored in the storage unit 123c-i. (Step S525-i). An example of the transformed variance value S _i (α _r ) corresponding to the variance value T _i (α _r ) in Equation (5) is as follows.
S ₀ (α ₀ ) = (a ₀ (1), a ₀ (2), ..., a ₀ (M-2), a ₀ (M-1)), S ₀ (α ₁ ) = (a ₁ (1), a ₁ (2), ..., a ₁ (M-2), a ₁ (M-1)), ..., S _M-1 (α _R-1 ) = (a _{R -1} (0), a _R-1 (1), ..., a _R-1 (M-2))

The secret calculation unit 227-i receives the transform variance value S _i (α _r ) = {a _r (i, 0), ..., a _r (i, N) stored in the storage unit 123c-i at a predetermined opportunity. _i -1)} is read, and a secret calculation is performed with the transformation variance S _i (α _r ) as input, and the variance _{Ei, r} = {e _r (i, 0),. ., e _r (i, N _i -1)} is output. The variance value E _{i, r} is output from the output unit 122-i and provided to the data restoration device 530.

<Data restoration processing>
As illustrated in FIG. 23, any K distributed values T _k (α _r ) (k∈ {0,..., For each of r are input to the input unit 131 of the data restoration device 530 (FIG. 16B). N-1}), or any of K dispersion values _{E k, r = {e r} (k, 0), ..., e r (k, N k -1)} (k∈ {0, ..., N-1}) is input (step S531). The control unit 534 determines whether the variance value T _k (α _r ) has been input or the variance value E _{k, r} has been input (step S532).

When it is determined in step S532 that the variance value T _k (α _r ) has been input, for each r, any K variance values T _k (α _r ) (k∈ {0,..., N− 1}, r = 0,..., R−1) are input to the conversion unit 235. The conversion unit 235 uses M−1 values a _r (m) for each of r using at least part of the variance values T _i (α _r ) (i = 0,..., N−1). ) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2) and the value a _r (m) ( r = 0,..., R-1, m = 0,..., M-2) are output (step S233). For example, when the variance values T ₀ (α _r ), T _M−1 (α _r ) (r = 0,..., R−1) of Expression (5) are input to the conversion unit 235, the conversion unit 235 Is the variance T _M-1 (α ₀ ) = (v (0), v (1), ..., v (M-3), v (M-2), U _M-1 (a ₀ ( M-1))) contains values v (0), v (1), ..., v (M-3), v (M-2), and M-1 Calculate the value a _r (m) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2). For each r, the internal restoration unit 537 calculates the value a _r from the K different variance values U _k (a _r (M−1)) (k∈ {0,..., N−1}) input. (M-1) (r = 0, ..., R-1) is restored, and the value a _r (M-1) (r = 0, ..., R-1) is output (step S533). ).
The restoration unit 236 stores M−1 values a _r (m) (r = 0,..., R−1, m = 0,..., M−2) and values a _r for each _r. (M-1) (r = 0, ..., R-1) is input. The restoration unit 236 calculates α _r = f (a _r (0),..., A _r (M−1)) using these, and the obtained value α _r (r = 0,. , R-1) is output (step S234). The values α _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values α _r (r = 0,..., R−1) to generate a value αεG, and outputs the value α (step S235). The value α is input to the output unit 132, and the output unit 132 outputs the value α (step S236).

On the other hand, if it is determined in step S532 that the variance value E _{k, r} is input, K variance values E _{k, r} (k∈ {0,..., N−1}) are _{obtained for each r.} The data is input to the restoration unit 236. The restoration unit 236 uses the variance value E _{k, r} = { _er (k, 0), ..., _er (k, N _{k, r} -1)} (r = 0, ... for each r. , R-1, k∈ {0, ..., N-1}) M values e _r (0), ..., e _r (M-1) are obtained, and ε _r = _{f (e r (0),} ..., e r (M-1)) calculated and the result _{ε r (r = 0, ...} , R-1) outputs a (step S237). R values ε _r (r = 0,..., R−1) are input to the coupling unit 237. The combining unit 237 combines the R values ε _r (r = 0,..., R−1) to generate a value εεG, and outputs the value ε (step S238). The value ε is input to the output unit 132, and the output unit 132 outputs the value ε (step S239).

<Features of this embodiment>
Also in this embodiment, the data amount of the distributed value can be greatly reduced as compared with the conventional secret sharing scheme. In this embodiment, to generate R values a _r (m) = P (z (r, v (m))) (r = 0, ..., R-1) from each value v (m) Further, it is possible to further reduce the data amount when performing secret sharing of a plurality of values α _r (r = 0,..., R−1). Furthermore, since the variance value T _i (α _r ) of this embodiment includes the secret sharing value U _i (a _r (M-1)) instead of a _r (M-1) that is an element of the set G, data The amount can be further reduced. Also, the distributed data conversion process in the distributed data conversion device can be used as an input for the secret calculation without restoring the original α and α _r from the distributed value obtained by the data distribution device. Can be generated and a secret calculation can be performed.

<Modifications>
The present invention is not limited to the embodiment described above. For example, in the second, third, and fifth embodiments, the value α is divided to generate R values α _r (r = 0,..., R−1), but the value α is R values. Data consisting of α _r may also be used. For example, the value α may be table data, and α _r may be an element constituting the table data. In addition, the R values α _r may not be divided from the value α, but may be independent data.

The data distribution apparatus may output further information (for example, parameters such as r and R, value v (m), etc.) as the second distribution value in addition to the distribution value of the above-described embodiment. For example, in the second and fifth embodiments, T _i (α _r ), r including (T _i (α _r ), r) (i = 0, ..., N-1, r = 0, ... , R-1) may be output from the data distribution apparatus. Other, in the third embodiment includes a T _N-1 (α _r) and _{r (T N-1 (α} r), r) (r = 0, ..., R-1) from the data distribution apparatus It may be output. In this case, the data restoration device may perform data restoration using the second variance value in addition to the variance value of the above-described embodiment, and the distributed data conversion device may add to the variance value of the above-described embodiment. Further, the converted variance value may be generated using the second variance value. Alternatively, r is not transmitted as a variance value, but is stored in the storage area and the position and order of T _i (α _r ) and T _N-1 (α _r ) in the transmitted bitstream associate r in T _i (α _r) and T _N-1 information such as the address of the (alpha _r), the corresponding r is identified from the information T _i (α _r) and T _N-1 (α _r) May be. Similarly, in the second, third, and fifth embodiments, r corresponding to the transformed variance value may be input in addition to the transformed variance value as an input value for the secret calculation, or the transformed variance value is handled by other methods. r may be specified.

  At least a part of the processing units of the devices described in the above embodiments may be included in the same device. For example, the data distribution device and the data restoration device may be configured using the same computer. Further, some processing units included in the apparatus described in the above-described embodiment may be included in another apparatus. For example, a secret calculation unit may be provided in a secret calculation device outside the distributed data conversion device, and the secret calculation device may perform a secret calculation using a conversion distribution value provided from the distributed data conversion device. In addition, the distributed value may be stored in a storage device outside the distributed data conversion apparatus. In this case, the distributed data conversion apparatus may not exist. Providing information from device A to device B may be transmitting information from device A to device B, storing information output from device A in a portable recording medium, and device B Alternatively, the information may be read from the portable recording medium. The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program on the computer.
The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads the program stored in its own recording device and executes the process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

1-5 Secret sharing system 110-510 Data distribution device 120-520 Distributed data conversion device 130-530 Data restoration device

Claims (19)

M and N are integers greater than or equal to 2, _Ni (i = 0, ..., N-1) is an integer greater than or equal to 1 and less than or equal to M-1, G is a set, and P (x) Is a mapping that moves values corresponding to x to elements of the set G, and y = f (y (0), ..., y (M-1)) are M values that are elements of the set G A mapping that transfers a subset (y (0), ..., y (M-1)) consisting of y (0), ..., y (M-1) to a value y that is an element of the set G And g (y, y (0), ..., y (M-2)) satisfies y = f (y (0), ..., y (M-1)) A subset (y, y (0), ..., y (M-2)) consisting of M pieces of y, y (0), ..., y (M-2) is the value y ( M-1)
A selector for selecting M-1 values v (m) (m = 0, ..., M-2);
A first conversion unit for obtaining M-1 values a (m) = P (v (m)) (m = 0,..., M-2);
A first calculation unit that obtains a value a (M−1) = g (α, a (0),..., A (M−2)) for a value α that is an element of the set G;
A subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1 )} (i = 0, ..., N-1) and (i, n _i ) (n _i ∈ {0, ...) where a (i, n _i ) ≠ a (M-1) , N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )) and a (i, q _i ) = a (M-1) ( i, q _i ) (q _i ∈ {0, ..., N _i -1}) corresponding to v (i, q _i ) is a (i, q _i ), and the variance T of the value α _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1)) (i = 0, ..., N-1) A value generator,
A data distribution apparatus. With claim 1 of the dispersion values obtained by the data distribution apparatus _{T i (α), a (} i, n i) ≠ is a (M-1) (i , n i) (n i ∈ {0, ..., N _i -1}) to obtain the value a (i, n _i ) = P (v (i, n _i )) for v (i, n _i ) ∈T _i (α) A conversion unit;
The values a (i, n _i ) and v (i, q _i ) = a (M−1) (q _i ∈ {0,..., N _i −1}, n _i ≠ q _i ), including a (i, q _i ) = v (i, q _i ) ∈T _i (α) and S _i (α) = (a (i, 0), ..., a (i, N _i -1)} as a transformation variance value,
A distributed data conversion apparatus. M-1 values a (m) = P using at least a part of the distribution values T _i (α) (i = 0,..., N−1) obtained by the data distribution apparatus according to claim 1. a second converter that obtains (v (m)) (m = 0, ..., M-2);
The value a (m) (m = 0,..., M−2) obtained by the second conversion unit and the value a (M−1) included in any one of the variance values T _i (α) A restoration unit that obtains α = f (a (0), ..., a (M-1)) using
A data restoration apparatus having M, N, and R are integers greater than or equal to 2, and N _{i, r} (i = 0, ..., N-1, r = 0, ..., R-1) is greater than or equal to 1 and less than or equal to M-1 An integer, G is a set, and P (x) is a mapping that moves a value corresponding to x to an element of the set G, y = f (y (0), ..., y (M -1)) is a subset (y (0), ..., y (M-1) consisting of M values y (0), ..., y (M-1), which are elements of the set G )) To a value y that is an element of the set G, and g (y, y (0), ..., y (M-2)) is y = f (y (0), ... ., y (M-1)) satisfying a subset (y, y (0), ..., y (M-2)) to the value y (M-1),
A selector for selecting M-1 values v (m) (m = 0, ..., M-2);
The value corresponding to r and the value v (m) is z (r, v (m)), and M−1 values a _r (m) = P (z (r, v ( m))) a first converter that obtains (r = 0, ..., R-1, m = 0, ..., M-2);
A first calculation for obtaining a value a _r (M−1) = g (α _r , a _r (0),..., A _r (M−2)) for a value α _r that is an element of the set G And
A subset of the set A _r = {a _r (0), ..., a _r (M-1)} is S _i (α _r ) = {a _r (i, 0), ..., a _r ( i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1) and a _r (i, n _{i, r} ) ≠ a _r (M-1) is (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1) At least one of the corresponding R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) is a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (v _{r ′} (i, n _{i, r ′} ) satisfying (r′∈ {0, ..., R-1}) ∈ {v (0), ..., v (M-2)} and a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r} ) ( _{q i, r ∈ {0,} ..., n i, r -1}, n i, r ≠ q i, v r (i corresponding to _r), q _{i, r)} is a _r (i, q _{i, r} ) = a _r (M-1) and variance T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1)) (i = 0, ..., N-1, r = 0, ..., R-1)
A data distribution apparatus. V _{r ′} (i, n _{i, r ′} ) (r′∈ {0,..., R−1}) included in the dispersion value T _i (α _r ) obtained by the data distribution apparatus according to claim 4. Value a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}), and a third conversion unit
The values a _r (i, n _{i, r} ) (n _{i, r} ε {0, ..., N _{i, r} -1}) and v _r (i, q _i ) obtained by the third conversion unit _{, r} ) = a _r (M-1) (q _{i, r} ∈ {0, ..., N _{i, r} -1}, n _{i, r} ≠ q _{i, r} ) a _r (i, q _{i, r} ) = v _r (i, q _{i, r} ) ∈T _i (α _r ) and at least one of S _i (α _r ) = (a _r (i, 0), ..., a _r (i, N _{i, r} −1)} as a transformation variance value,
A distributed data conversion apparatus. Using at least a part of the distribution values T _i (α _r ) (i = 0, ..., N-1) obtained by the data distribution apparatus of claim 4, M-1 items for each of r The second transformation to obtain the value a _r (m) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2) And
The value a _r (M−) included in one of the value a _r (m) (m = 0,..., M−2) obtained by the second conversion unit and the variance value T _i (α _r ). 1) and a restoration unit that obtains α _r = f (a _r (0), ..., a _r (M-1)),
A data restoration apparatus having N and R are integers greater than or equal to 2, _Ni (i = 0, ..., N-1) is an integer greater than or equal to 1 and less than or equal to N-1, G is a set, and P (x) Is a map that transfers values corresponding to x to elements of the set G, and N values where y = f (y (0), ..., y (N-1)) are elements of the set G A mapping that transfers a subset (y (0), ..., y (N-1)) consisting of y (0), ..., y (N-1) to a value y that is an element of the set G And g (y, y (0), ..., y (N-2)) satisfies y = f (y (0), ..., y (N-1)) A subset (y, y (0), ..., y (N-2)) consisting of N y, y (0), ..., y (N-2) is the value y ( N-1)
A selection section for selecting N-1 values v (n) (n = 0, ..., N-2);
The value corresponding to r and the value v (n) is z (r, v (n)), and N-1 values a _r (n) = P (z (r, v ( n))) a first converter that obtains (r = 0, ..., R-1, n = 0, ..., N-2);
The value a _r (N-1) = g (α _r , a _r (0), ..., for the value α _r (r = 0, ..., R-1) which is an element of the set G a _r (N-2)) to obtain a first calculation unit;
The value v (n) is a variance value T _n (β) (n = 0, ..., N-2 , β = {α ₀ , ..., α _R-1 } ), and the value a _r ( (N-1) as a variance value T _N-1 (α _r ),
A data distribution apparatus. Data distribution variance obtained in device _{T n (β) = v (} n) from the values _{a r (n) = P (} z (r, v (n))) of claim 7 (r = 0, .. ., R-1) is a distributed data conversion apparatus having a conversion variance value generation unit that obtains a conversion variance value. The distribution value T _n (β) (n = 0,..., N−2) obtained by the data distribution apparatus according to claim 7 is used, and N−1 values a _r ( n) = P (z (r, v (n))) (r = 0, ..., R-1, n = 0, ..., N-2)
The value a _r (n) (n = 0,..., N−2) obtained by the second conversion unit and the variance value T _N−1 (α _r ) = a _r (N−1) A reconstruction unit that obtains α _r = f (a _r (0), ..., a _r (N-1)) (r = 0, ..., R-1) using
A data restoration apparatus having M, N, K are integers of 2 or more, K ≦ N, _Ni (i = 0, ..., N-1) is an integer of 1 to M-1, and G is Is a set, and P (x) is a mapping that transfers a value corresponding to x to an element of the set G, and y = f (y (0), ..., y (M-1)) is the set G A subset (y (0), ..., y (M-1)) consisting of M values y (0), ..., y (M-1) that are elements of Y (f (y (0), ..., y (M-1)), where g (y, y (0), ..., y (M-2)) ) Satisfying the subset (y, y (0), ..., y (M- 2)) is a mapping that moves to the value y (M-1),
A selector for selecting M-1 values v (m) (m = 0, ..., M-2);
A first conversion unit for obtaining M-1 values a (m) = P (v (m)) (m = 0,..., M-2);
A first calculation unit that obtains a value a (M−1) = g (α, a (0),..., A (M−2)) for a value α that is an element of the set G;
The value a (M-1) is secretly distributed according to the (K, N) threshold secret sharing method U, and N distributed values U _i (a (M-1)) (i = 0, ..., N- 1) obtain internal dispersion part,
A subset of the set A = {a (0), ..., a (M-1)} is S _i (α) = {a (i, 0), ..., a (i, N _i -1 )} (i = 0, ..., N-1) and (i, n _i ) (n _i ∈ {0, ...) where a (i, n _i ) ≠ a (M-1) , N _i -1}) is V (i, n _i ) is P ^-1 (a (i, n _i )) and a (i, q _i ) = a (M-1) ( i, q _i ) (q _i ∈ {0, ..., N _i -1}) corresponding to v (i, q _i ) is a null value, and the variance value T _i (α) = (v (i, 0), v (i, 1), ..., v (i, N _i -1), U _i (a (M-1))) (i = 0, ..., N -1) to obtain a variance value generation unit,
A data distribution apparatus. The distribution value T _i (α) (i = 0,..., N−1) obtained by the data distribution apparatus according to claim 10 is used, and a (i, n _i ) ≠ a (M−1). The value a (i, n _i ) = P for v (i, n _i ) ∈T _i (α) corresponding to (i, n _i ) (n _i ∈ {0, ..., N _i -1}) a third conversion unit for obtaining (v (i, n _i ));
K different variance values U _k (a (M-1)) (k∈ {0, ...,) included in the variance values T _i (α) (i = 0, ..., N-1) N-1}) to obtain the value a (M-1) from the second internal restoration unit;
S _i (α) = including at least one of the value a (i, n _i ) obtained by the third conversion unit and the value a (M−1) obtained by the second internal restoration unit {a (i, 0), ..., a (i, N _i -1)} (i = 0, ..., N-1), a transform variance value generation unit that obtains transform variance values;
A distributed data conversion apparatus. 11. M−1 values a (m) = P using at least a part of the dispersion values T _i (α) (i = 0,..., N−1) obtained by the data distribution apparatus according to claim 10. a second converter that obtains (v (m)) (m = 0, ..., M-2);
K different variance values U _k (a (M-1)) (k∈ {0, ...,) included in the variance values T _i (α) (i = 0, ..., N-1) N-1}) from which a value a (M-1) is obtained,
Using the value a (m) (m = 0,..., M−2) obtained by the second conversion unit and the value a (M−1) obtained by the first internal restoration unit A restoring unit for obtaining α = f (a (0), ..., a (M-1))
A data restoration apparatus having M, N, K, R are integers greater than or equal to 2, K ≦ N, and N _{i, r} (i = 0, ..., N-1, r = 0, ..., R-1) Is an integer greater than or equal to 1 and less than or equal to M−1, G is a certain set, P (x) is a mapping that transfers a value corresponding to x to an element of the set G, and y = f (y (0) , ..., y (M-1)) is a subset (y (0), ...) consisting of M values y (0), ..., y (M-1), whose elements are the set G. .., y (M-1)) to a value y that is an element of the set G, and g (y, y (0), ..., y (M-2)) is y = f A subset of M y, y (0), ..., y (M-2) that are elements of the set G satisfying (y (0), ..., y (M-1)) (y, y (0), ..., y (M-2)) is a mapping that moves to the value y (M-1),
A selector for selecting M-1 values v (m) (m = 0, ..., M-2);
The value corresponding to r and the value v (m) is z (r, v (m)), and M−1 values a _r (m) = P (z (r, v ( m))) a first converter that obtains (r = 0, ..., R-1, m = 0, ..., M-2);
For a value α _r (r = 0, ..., R-1) which is an element of the set G, a value a _r (M-1) = g (α _r , a _r (0), ..., a _r (M-2)) to obtain a first calculation unit;
(K, N) The value a _r (M-1) is secretly distributed according to the threshold secret sharing method U, and N distributed values U _i (a _r (M-1)) (i = 0, ..., N-1)
A subset of the set A _r = {a _r (0), ..., a _r (M-1)} is S _i (α _r ) = {a _r (i, 0), ..., a _r ( i, N _{i, r} -1)} (i = 0, ..., N-1, r = 0, ..., R-1) and a _r (i, n _{i, r} ) ≠ a _r (M-1) is (i, n _{i, r} ) (n _{i, r} ∈ {0, ..., N _{i, r} -1}, r = 0, ..., R-1) At least one of the corresponding R v ₀ (i, n _{i, 0} ), ..., v _R-1 (i, n _{i, R-1} ) is a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} ))) (v _{r ′} (i, n _{i, r ′} ) satisfying (r′∈ {0, ..., R-1}) ∈ {v (0), ..., v (M-2)} and a _r (i, q _{i, r} ) = a _r (M-1) (i, q _{i, r} ) ( _{q i, r ∈ {0,} ..., n i, r -1}, n i, r ≠ q i, v r (i corresponding to _r), q _{i, r)} is empty value, variance Value T _i (α _r ) = (v _r (i, 0), v _r (i, 1), ..., v _r (i, N _{i, r} -1), U _i (a _r (M- 1))) A variance generator that obtains (i = 0, ..., N-1, r = 0, ..., R-1),
A data distribution apparatus. V _{r ′} (i, n _{i, r ′} ) (r ′ included in the dispersion value T _i (α _r ) (r = 0,..., R−1) obtained by the data distribution apparatus according to claim 13. ∈ {0, ..., R-1}) value a _r (i, n _{i, r} ) = P (z (r, v _{r ′} (i, n _{i, r ′} )))) (n _{i, r} ∈ {0, ..., N _{i, r} -1}),
K different dispersion values U _k (a _r (M-1)) (k∈ {0,...) Included in the dispersion values T _i (α _r ) (i = 0, ..., N-1). ., N-1}) from the second internal restoration unit for obtaining the value a _r (M-1)
S _i including at least one of the value a _r (i, n _{i, r} ) obtained by the third conversion unit and the value a _r (M−1) obtained by the second internal restoration unit (α _r ) = {a _r (i, 0), ..., a _r (i, N _{i, r} -1)} (i = 0, ..., N-1) is obtained as the transformation variance A transform variance value generation unit;
A distributed data conversion apparatus. 14. At least part of the dispersion values T _i (α ₀ ) (i = 0,..., N−1) obtained by the data distribution apparatus according to claim 13, M−1 pieces for each of r The second transformation to obtain the value a _r (m) = P (z (r, v (m))) (r = 0, ..., R-1, m = 0, ..., M-2) And
K different dispersion values U _k (a _r (M-1)) (k∈ {0,...) Included in the dispersion values T _i (α _r ) (i = 0, ..., N-1). ., N−1}) from the first internal restoration unit for obtaining the value a _r (M−1),
The value a _r (m) (m = 0,..., M−2) obtained by the second conversion unit and the value a _r (M−1) obtained by the first internal restoration unit A restoration unit that obtains α _r = f (a _r (0), ..., a _r (M-1)) using
A data restoration apparatus having The data distribution apparatus according to claim 1, wherein
The total value of the data amount of the M-1 values v (m) (m = 0, ..., M-2) is larger than the total value of the data amount of the elements of the M-1 sets G. A small data distribution device. The data distribution apparatus according to claim 7 , wherein
The total value of the data amount of the N−1 variance values T _n (β) (n = 0,..., N−2) is R × (N−1) element G data. A data distribution device that is smaller than the total amount. The data distribution apparatus according to claim 10 , wherein
N _i -1 v (i, j) data amount and U _i (a (M-1)) data amount for (i, j) where a (i, j) ≠ a (M-1) Is a data distribution device that is smaller than the total value of the data amounts of the elements of the N _i sets G. 14. The data distribution device of claim 13 , wherein
The data amount of N _{i, r} -1 v _r (i, j) and U _i (a _r (M--) for (i, j) where a _r (i, j) ≠ a _r (M-1) A data distribution device in which the total value of the data amount in 1)) is smaller than the total value of the data amounts of the elements of the N _{i, r} sets G.

Images