Secure computation system, secure computation device, secure computation method, and program

A secure computation technique of calculating a polynomial in a shorter calculation time is provided. A secure computation system generates concealed text [[u]] of u, which is the result of magnitude comparison between a value x and a random number r, from concealed text [[x]] by using concealed text [[r]]; generates concealed text [[c]] of a mask c from the concealed text [[x]], [[r]], and [[u]]; reconstructs the mask c from the concealed text [[c]]; calculates, for i=0, . . . , n, a coefficient bi from an order n, coefficients a0, a1, . . . , an, and the mask c; generates, for i=1, . . . , n, concealed text [[si]] of a selected value si, which is determined in accordance with the result u of magnitude comparison, from the concealed text; [[u]]; and calculates a linear combination b0+b1[[s1]]+ . . . +bn[[sn]] of the coefficient bi and the concealed text [[si]] as concealed text [[a0+a1x1+ . . . +anxn]].

TECHNICAL FIELD

The present invention relates to secure computation techniques and, in particular, relates to a secure computation technique of calculating a polynomial with an input value kept secret.

BACKGROUND ART

As a method of obtaining the computation result of a designated computation without reconstructing the encrypted numerical values, there is a method called secure computation (see, for example, Non-patent Literature 1). With the method of Non-patent Literature 1, it is possible to perform encryption by which a plurality of pieces of information (shares of a numerical value), whose numerical values can be reconstructed, are distributed over three secure computation devices and make the three secure computation devices hold the results of addition and subtraction, constant addition, multiplication, constant multiplication, logical operations (a NOT, an AND, an OR, and an XOR), and data format conversion (an integer or a binary) with the results being distributed over these secure computation devices, that is, in an encrypted state, without reconstructing the numerical values. In general, the number of secure computation devices over which the information is distributed is not limited to 3 and can be set at W (W is a predetermined constant greater than or equal to 2), and a protocol that implements secure computation by cooperative computations by W secure computation devices is called a multi-party protocol.

It is to be noted that a secure computation method which is performed when the number of secure computation devices over which the information is distributed is 2 is disclosed in Non-patent Literature 2, for example.

As a method that implements calculation of a polynomial by secure computation, there is a method of Non-patent Literature 3. In the method of Non-patent Literature 3, calculation of x1, x2, . . . , xnis implemented by repeatedly and concurrently performing processing by which each of x1, x2, . . . , x2{circumflex over ( )}kis multiplied by x2{circumflex over ( )}k(k=0, 1, . . . ) when calculation of a polynomial in a variable x is performed (it is to be noted that {circumflex over ( )} (caret) represents a superscript; for example, xy{circumflex over ( )}zindicates that yzis a superscript for x).

PRIOR ART LITERATURE

SUMMARY OF THE INVENTION

Problems to be Solved by the Invention

However, in the method of Non-patent Literature 3, 2n−1 (ceiling(log2n)+1 stage) multiplication and n addition have to be executed when a polynomial a0+a1x1+ . . . +anxnis calculated, which makes a calculation time undesirably long.

Therefore, an object of the present invention is to provide a secure computation technique of calculating a polynomial in a shorter calculation time.

Means to Solve the Problems

An aspect of the present invention is a secure computation system in which a0+a1x1+ . . . +anxnis assumed to be an n-th order polynomial (n is the order of the polynomial and a0, a1, . . . , anare coefficients of the polynomial) in a variable x, x is assumed to be a value which is substituted into the n-th order polynomial, k is assumed to be an integer which satisfies k≤x<k+1, r is assumed to be a random number which satisfies k≤r<k+1, and [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are assumed to be concealed text of a power of the random number r and a power of r−1, the secure computation system which is configured with two or more secure computation devices and calculates, from concealed text [[x]] of the value x, concealed text [[a0+a1x1+ . . . +anxn]] of the values of the n-th order polynomial a0+a1x1+ . . . +anxnin which the value x is substituted. The secure computation system includes: a comparing means that generates concealed text [[u]] of u (u=1 if x≤r holds and u=0 if x≤r does not hold), which is the result of magnitude comparison between the value x and the random number r, from the concealed text [[x]] by using the concealed text [[r]]; a mask means that generates concealed text [[c]] of a mask c as [[c]]=[[x]]−[[r]]+[[u]] from the concealed text [[x]], the concealed text [[r]], and the concealed text [[u]]; a reconstructing means that reconstructs the mask c from the concealed text [[c]]; a coefficient calculating means that calculates, for i=0, . . . , n, a coefficient biby the formula below from the order n, the coefficients a0, a1, . . . , an, and the mask c;

a selecting means that generates, for i=1, . . . , n, concealed text [[si]] of a selected value si(si=(r−1)iif u=1 and si=riif u=0), which is determined in accordance with the result u of magnitude comparison, from the concealed text [[u]]; and a linear combination means that calculates a linear combination b0+b1[[s1]]+ . . . +bn[[sn]] of the coefficient bi(i=0, . . . , n) and the concealed text [[si]] (i=1, . . . , n) as the concealed text [[a0+a1x1+ . . . +anxn]].

An aspect of the present invention is a secure computation system in which a0+a1x1+ . . . +anxnis assumed to be an n-th order polynomial (n is the order of the polynomial and a0, a1, . . . , anare coefficients of the polynomial) in a variable x, x is assumed to be a value which is substituted into the n-th order polynomial, r is assumed to be a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are assumed to be concealed text of a power of the random number r and a power of r−1, and the reciprocal 1/x of the value x is assumed to be expressed as 1/x=a0+a1x1+ . . . +anxn, the secure computation system which is configured with two or more secure computation devices and calculates concealed text [[1/x]] of the reciprocal 1/x from concealed text [[x]] of the value x. The secure computation system includes: an input value decomposing means that generates, from the concealed text [[x]], concealed text [[s]], [[e]], and [[f]] of s, e, and f which satisfy x=s×2e×f (s ∈ {−1, 1}, e is an integer, and 1≤f<2); a comparing means that generates concealed text [[u]] of u (u=1 if f≤r holds and u=0 if f≤r does not hold), which is the result of magnitude comparison between the f and the random number r, from the concealed text [[f]] by using the concealed text [[r]]; a mask means that generates concealed text [[c]] of a mask c as [[c]]=[[f]]−[[r]]+[[u]] from the concealed text [[f]], the concealed text [[r]], and the concealed text [[u]]; a reconstructing means that reconstructs the mask c from the concealed text [[c]]; a coefficient calculating means that calculates, for i=0, . . . , n, a coefficient biby the formula below from the order n, the coefficients a0, a1, . . . , an, and the mask c;

a selecting means that generates, for i=1, . . . , n, concealed text [[si]] of a selected value si(si=(r−1)iif u=1 and si=riif u=0), which is determined in accordance with the result u of magnitude comparison, from the concealed text [[u]]; a linear combination means that calculates a linear combination b0+b1[[s1]]+ . . . +bn[[sn]] of the coefficient bi(i=0, . . . , n) and the concealed text [[si]] (i=1, . . . , n) as concealed text [[1/f]] of the reciprocal 1/f of the f; and a reciprocal calculating means that calculates [[s]]×([[1/f]]<<[[−e]]) (where [[1/f]]<<[[−e]] is a value obtained by shifting 1/f to the left by −e bit) as the concealed text [[1/x]] from the concealed text [[s]], the concealed text [[e]], and the concealed text [[1/f]].

An aspect of the present invention is a secure computation system in which a0+a1x1+ . . . +anxnis assumed to be an n-th order polynomial (n is the order of the polynomial and a0, a1, . . . , anare coefficients of the polynomial) in a variable x, x is assumed to be a value which is substituted into the n-th order polynomial, r is assumed to be a random number which satisfies 1≤r<2, [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] are assumed to be concealed text of a power of the random number r and a power of r−1, and the logarithm log x of the value x is assumed to be expressed as log x=a0+a1x1+ . . . +anxn, the secure computation system which is configured with two or more secure computation devices and calculates concealed text [[log x]] of the logarithm log x from concealed text [[x]] of the value x. The secure computation system includes: an input value decomposing means that generates, from the concealed text [[x]], concealed text [[e]] and [[f]] of e and f which satisfy x=2e×f (e is an integer and 1≤f<2); a comparing means that generates concealed text [[u]] of u (u=1 if f≤r holds and u=0 if f≤r does not hold), which is the result of magnitude comparison between the f and the random number r, from the concealed text [[f]] by using the concealed text [[r]]; a mask means that generates concealed text [[c]] of a mask c as [[c]]=[[f]]−[[r]]+[[u]] from the concealed text [[f]], the concealed text [[r]], and the concealed text [[u]]; a reconstructing means that reconstructs the mask c from the concealed text [[c]]; a coefficient calculating means that calculates, for i=0, . . . , n, a coefficient biby the formula below from the order n, the coefficients a0, a1, . . . , an, and the mask c;

a selecting means that generates, for i=1, . . . , n, concealed text [[si]] of a selected value si(si=(r−1)iif u=1 and si=riif u=0), which is determined in accordance with the result u of magnitude comparison, from the concealed text [[u]]; a linear combination means that calculates a linear combination b0+b1[[s1]]+ . . . +bn[[sn]] of the coefficient bi(i=0, . . . , n) and the concealed text [[si]] (i=1, . . . , n) as concealed text [[log f]] of the logarithm log f of the f; and a logarithm calculating means that calculates [[log f]]+[[e]], which is a value obtained by adding e to the logarithm log f, as the concealed text [[log x]] from the concealed text [[e]] and the concealed text [[log f]].

Effects of the Invention

According to the present invention, by performing 1 stage multiplication as a multiplication necessary for calculation of a polynomial, it is possible to reduce the calculation time necessary for secure computation of the polynomial.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Hereinafter, embodiments of the present invention will be described in detail. It is to be noted that constituent units having the same function will be identified with the same reference character and overlapping explanations will be omitted.

A secure computation algorithm, which will be described later, is constructed by combining computations on the existing secure computation. The computations required by the secure computation algorithm are concealment and reconstruction, addition, subtraction, multiplication, comparison, selection, and left shift. First, definition, notation, and the like of each computation will be described.

It is assumed that a value obtained by concealing a value a by encryption, secret sharing, or the like is referred to as concealed text of a and expressed as [[a]]. It is assumed that, when the concealed text [[a]] of a is generated by secret sharing, a set of shares of secret sharing, which the secure computation devices hold, is referred to based on [[a]].

Moreover, it is assumed that processing by which a is obtained by reconstructing the concealed text [[a]] of a is expressed as a←Open([[a]]).

As a method of concealment and reconstruction, specifically, there is a technique of Reference Non-patent Literature 1.

In Reference Non-patent Literature 1, floating-point operations are disclosed. Fixed-point or integer operations can be implemented by combining type conversions from a floating-point type to a fixed-point or integer type disclosed in Reference Non-patent Literature 1.

Addition, subtraction, and multiplication calculate concealed text [[c1]], [[c2]], and [[c3]] of a sum c1, a difference c2, and a product c3, which are the calculation results of a+b, a−b, and ab, respectively, by using concealed text [[a]] and [[b]] of two values a and b as input. It is assumed that processing by which [[c1]] is obtained, processing by which [[c2]] is obtained, and processing by which [[c3]] is obtained are respectively expressed as [[c1]]←Add([[a]], [[b]]), [[c2]]←Sub([[a]], [[b]]), and [[c3]]←Mul([[a]], [[b]]). When there is no possibility of misunderstanding, Add([[a]], [[b]]), Sub([[a]], [[b]]), and Mul([[a]], [[b]]) are sometimes abbreviated as [[a]]+[[b]], [[a]]−[[b]], and [[a]]×[[b]], respectively.

As a method of addition, subtraction, and multiplication, specifically, there is the technique of Reference Non-patent Literature 1. In Reference Non-patent Literature 1, floating-point operations are disclosed. Fixed-point or integer operations can be implemented by combining type conversions from a floating-point type to a fixed-point or integer type disclosed in Reference Non-patent Literature 1.

It is assumed that processing by which, for concealed text [[a]] of a and concealed text [[b]] of b, concealed text [[c]] of the result c of magnitude comparison between a and b, which makes c=1 hold if a≤b holds and c=0 hold if a≤b does not hold, is calculated is expressed as [[c]]←([[a]]≤?[[b]]).

As a method of comparison, specifically, there is the technique of Reference Non-patent Literature 1. In Reference Non-patent Literature 1, floating-point operations are disclosed. Fixed-point or integer operations can be implemented by combining type conversions from a floating-point type to a fixed-point or integer type disclosed in Reference Non-patent Literature 1.

It is assumed that processing by which, for concealed text [[a]] of a ∈ {0, 1} and concealed text [[t]] and [[f]] of two values t and f, concealed text [[b]] of a selected value b, which makes b=t hold if a=1 and b=f hold if a=0, is calculated is expressed as [[b]]←IfElse([[a]], [[t]], [[f]]). This selection processing can be implemented by using multiplication and addition as follows: IfElse([[a]], [[t]], [[f]]):=[[a]]×[[t]]+[[a]]×[[f]].

It is assumed that processing by which concealed text [[c]] of a left shift value c (=a×2b), which is a value obtained by shifting a to the left by b bit (that is, a value obtained by multiplying a by 2b), is calculated from concealed text [[a]] of a and concealed text [[b]] of b is expressed as [[c]]←[[a]]<<[[b]].

As for floating-point operations, it is only necessary to add a shift amount (y of x<<y) to an exponent part. Moreover, as for fixed-point or integer operations, it is only necessary to combine interconversion between a fixed-point number and a floating-point number of Reference Non-patent Literature 1 and the above-described shifting of a floating-point number to the left.

First Embodiment

Hereinafter, input and output and procedures of a secure computation algorithm of a first embodiment and a secure computation system that implements the secure computation algorithm of the first embodiment will be described.

Input and output of the secure computation algorithm of the first embodiment shown inFIG. 1will be described.

Input is the order n and coefficients a0, a1, . . . , anof a polynomial a0+a1x1+ . . . +anxnand concealed text [[x]] of a value x which is substituted into the polynomial. Moreover, concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of a random number r, which satisfies k≤r<k+1 (where k is assumed to be an integer which satisfies k≤x<k+1), and a power of r−1 is also input.

Output is concealed text [[a0+a1x1+ . . . +anxn]] of the values of the polynomial a0+a1x1+ . . . +anxnin which x is substituted.

The procedures of the secure computation algorithm of the first embodiment depicted inFIG. 1will be described. In so doing, expressions such as Step 1 and Step 2 are adopted by using the numerals on the left end ofFIG. 1.

In Step 1, concealed text [[u]]←([[x]]≤?[[r]]) of u, which is the result of magnitude comparison between x and the random number r, is generated from the input concealed text [[x]] and [[r]]. [[u]] is concealed text of u which makes u=1 hold if x≤r holds and u=0 hold if x≤r does not hold.

In Step 2, concealed text [[c]] of a mask c is generated as [[c]]=[[x]]−[[r]]+[[u]] from the concealed text [[x]] and [[r]] and the concealed text [[u]] generated in Step 1. The mask c satisfies 0<c≤1.

In Step 3, the mask c is reconstructed from the concealed text [[c]] generated in Step 2.

In Step 4, a coefficient biis calculated for i=0, . . . , n by the formula below from the order n, the coefficients a0, a1, . . . , an, and c reconstructed in Step 3.

In Step 5, concealed text [[si]]=IfElse([[u]], [[(r−1)i]], [[ri]]) of a selected value si, which is determined in accordance with the result u of magnitude comparison, is generated for i=1, . . . , n from the concealed text [[u]] generated in Step 1. [[si]] is concealed text which makes si=(r−1)ihold if u=1 and si=rihold if u=0. That is, [[si]]=[[(r−1)i]] holds if [[u]]=[[1]] and [[si]]=[[ri]] holds if [[u]]=[[0]].

Hereinafter, a secure computation system10of the first embodiment will be described with reference toFIGS. 2 to 4.FIG. 2is a block diagram depicting the configuration of the secure computation system10. The secure computation system10includes W (W is a predetermined integer greater than or equal to 2) secure computation devices1001, . . . ,100W. The secure computation devices1001, . . . ,100Ware connected to a network800and can communicate with each other. The network800may be, for example, a communications network such as the Internet or a broadcast communication channel.FIG. 3is a block diagram depicting the configuration of a secure computation device100i(1≤i≤W).FIG. 4is a flowchart showing an operation of the secure computation system10.

As depicted inFIG. 3, the secure computation device100iincludes a random number generating unit110i, a comparison unit120i, a mask unit130i, a reconstruction unit140i, a coefficient calculation unit150i, a selection unit160i, a linear combination unit170i, and a recording unit190i. Apart from the recording unit190i, the constituent units of the secure computation device100iare configured so as to be capable of executing, of computations which are required in the secure computation algorithm, that is, at least concealment, reconstruction, addition, subtraction, multiplication, comparison, and selection, computations which are required to implement the functions of the constituent units. In the present invention, as specific functional configurations for implementing individual computations, configurations that can execute the algorithms in, for example, Non-patent Literatures disclosed as Prior Art Literature and Reference Non-patent Literature disclosed in <Definitions, notation, etc.> serve the purpose, and their detailed explanations will be omitted because they are the existing configurations. Moreover, the recording unit190iis a constituent unit that records information which is necessary for processing of the secure computation device100i. For instance, the order n and the coefficients a0, a1, . . . , anare recorded thereon.

By cooperative computations which are performed by the W secure computation devices100i, the secure computation system10implements the secure computation algorithm which is a multi-party protocol. Thus, a random number generating means110(which is not depicted in the drawing) of the secure computation system10is configured with the random number generating units1101, . . . ,110W, a comparing means120(which is not depicted in the drawing) is configured with the comparison units1201, . . . ,120W, a mask means130(which is not depicted in the drawing) is configured with the mask units1301, . . . ,130W, a reconstructing means140(which is not depicted in the drawing) is configured with the reconstruction units1401, . . . ,140W, a coefficient calculating means150(which is not depicted in the drawing) is configured with the coefficient calculation units1501, . . . ,150W, a selecting means160(which is not depicted in the drawing) is configured with the selection units1601, . . . ,160W, and a linear combination means170(which is not depicted in the drawing) is configured with the linear combination units1701, . . . ,170W.

By using concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of the previously generated random number r (k≤r<k+1, where k is an integer which satisfies k≤x<k+1) and a power of r−1, the secure computation system10calculates, from concealed text [[x]] of a value x which is substituted into a polynomial, concealed text [[a0+a1x1+ . . . +anxn]] of the values of a polynomial a0+a1x1+ . . . +anxnin which x is substituted. Hereinafter, an operation of the secure computation system10will be described in accordance withFIG. 4.

By using the concealed text [[r]] generated before input of the concealed text [[x]], the comparing means120generates concealed text [[u]]←([[x]]≤?[[r]]) of u, which is the result of magnitude comparison between a value x and the random number r, from the concealed text [[x]] (S120). This corresponds to Step 1 of the secure computation algorithm ofFIG. 1.

The mask means130generates concealed text [[c]] of a mask c as [[c]]=[[x]]−[[r]]+[[u]] from the concealed text [[x]] and [[r]] and the concealed text [[u]] generated in S120(S130). This corresponds to Step 2 of the secure computation algorithm ofFIG. 1.

The reconstructing means140reconstructs the mask c from the concealed text [[c]] generated in S130(S140). This corresponds to Step 3 of the secure computation algorithm ofFIG. 1.

The coefficient calculating means150calculates, for i=0, . . . , n, a coefficient biby the formula below from the order n and the coefficients a0, a1, . . . , anof the polynomial and the mask c reconstructed in S140(S150). This corresponds to Step 4 of the secure computation algorithm ofFIG. 1.

The selecting means160generates, for i=1, . . . , n, concealed text [[si]] of a selected value si(si=(r−1)iif u=1 and si=riif u=0), which is determined in accordance with the result u of magnitude comparison, from the concealed text [[u]] generated in S120(S160). This corresponds to Step 5 of the secure computation algorithm ofFIG. 1.

According to the invention of the present embodiment, since calculation of the polynomial a0+a1x1+ . . . +anxncan be implemented by n addition, n (1 stage) multiplication, one comparison, and one reconstruction operation, calculation cost is reduced. In particular, in a case where additions can be ignored, such as calculation in fixed-point calculation, the calculation time is effectively reduced. Specifically, processing which has required about 2n−1 (ceiling(log2n)+1 stage) bit decomposition operation can be implemented by n+1 (2 stage) processing operations. Moreover, by using the fact that the range of the value x which is substituted into the polynomial is limited to k≤x<k+1, processing by which the output value [[a0+a1x1+ . . . +anxn]] is calculated from the input value [[x]] is reduced to processing by which calculation is performed by using x−r+u and the concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]] . . . [[(r−1)n]] of a power of the previously generated random number r and a power of r−1. In general, information leaks when x−r+u is reconstructed; however, by adjusting x−r+u so as to be uniform random values greater than 0 and smaller than or equal to 1, it is possible to securely execute calculation of a0+a1x1+ . . . +anxn.

Second Embodiment

When the reciprocal 1/x of x can be expressed as 1/x=a0+a1x1+ . . . +anxnby using a polynomial, concealed text [[1/x]] of the reciprocal 1/x can be efficiently calculated from concealed text [[x]] of x by using the secure computation algorithm of the first embodiment.

Hereinafter, input and output and procedures of a secure computation algorithm of a second embodiment and a secure computation system that implements the secure computation algorithm of the second embodiment will be described.

Input and output of the secure computation algorithm of the second embodiment shown inFIG. 5will be described.

Input is the order n and coefficients a0, a1, . . . , anof a polynomial a0+a1x1+ . . . +anxnand concealed text [[x]] of a value x whose reciprocal is subjected to calculation of the value. Moreover, concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of a random number r, which satisfies 1≤r<2, and a power of r−1 is also input.

Output is concealed text [[1/x]] of the reciprocal 1/x of x.

The procedures of the secure computation algorithm of the second embodiment depicted inFIG. 5will be described. In so doing, expressions such as Step 1 and Step 2 are adopted by using the numerals on the left end ofFIG. 5.

In Step 1, for the input concealed text [[x]], concealed text [[s]], [[e]], and [[f]] of s, e, and f which satisfy x=s×2e×f (s ∈ {−1, 1}, e is an integer, and 1≤f<2) is generated. By using operations of Reference Non-patent Literature 1 to determine floating-point representation of [[x]], the concealed text [[s]], [[e]], and [[f]] can be generated.

In Step 3, [[s]]×([[1/f]]<<[[−e]]) is calculated from the concealed text [[s]] and [[e]] generated in Step 1 and the concealed text [[1/f]] calculated in Step 2. Here, [[s]]×([[1/f]]<<[[−e]])=[[1/x]] holds.

Hereinafter, a secure computation system20of the second embodiment will be described with reference toFIGS. 6 and 7. The secure computation system20differs from the secure computation system10in that the secure computation system20includes W (W is a predetermined integer greater than or equal to 2) secure computation devices2001, . . . ,200Winstead of including W secure computation devices1001, . . . ,100W.FIG. 6is a block diagram depicting the configuration of a secure computation device200i(1≤i≤W).FIG. 7is a flowchart showing an operation of the secure computation system20.

As depicted inFIG. 6, the secure computation device200idiffers from the secure computation device100iin that the secure computation device200ifurther includes an input value decomposition unit210iand a reciprocal calculation unit220i. The input value decomposition unit210iand the reciprocal calculation unit220iare also configured so as to be capable of executing, of computations which are required in the secure computation algorithm, computations which are required to implement the functions thereof.

An input value decomposing means210of the secure computation system20is configured with the input value decomposition units2101, . . . ,210W, and a reciprocal calculating means220is configured with the reciprocal calculation units2201, . . . ,220W.

By using concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of the previously generated random number r (1≤r<2) and a power of r−1, the secure computation system20calculates concealed text [[1/x]] of the reciprocal 1/x of x from concealed text [[x]] of the value x which is substituted into a polynomial. Hereinafter, an operation of the secure computation system20will be described in accordance withFIG. 7.

The input value decomposing means210generates, from the concealed text [[x]], concealed text [[s]], [[e]], and [[f]] of s, e, and f which satisfy x=s×2e×f (s ∈ {−1, 1}, e is an integer, and 1≤f<2) (S210). This corresponds to Step 1 of the secure computation algorithm ofFIG. 5.

The comparing means120, the mask means130, the reconstructing means140, the coefficient calculating means150, the selecting means160, and the linear combination means170calculate [[a0+a1f1+ . . . +anfn]] (=[[1/f]]) from the order n and the coefficients a0, a1, . . . , anof the polynomial, the concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] generated before input of [[x]], and the concealed text [[f]] generated in S210(S120to S170). This corresponds to Step 2 of the secure computation algorithm ofFIG. 5(Steps 1 to 6 of the secure computation algorithm ofFIG. 1).

The reciprocal calculating means220calculates [[s]]×([[1/f]]<<[[−e]]) as concealed text [[1/x]] of the reciprocal 1/x from the concealed text [[s]] and [[e]] generated in S210and the concealed text [[1/f]] calculated in S120to S170(S220). This corresponds to Step 3 of the secure computation algorithm ofFIG. 5.

According to the invention of the present embodiment, by performing calculation of the polynomial a0+a1x1+ . . . +anxnby using the secure computation algorithm of the first embodiment, it is possible to reduce the cost of calculating the concealed text [[1/x]] of the reciprocal 1/x from the concealed text [[x]]. Moreover, by using the fact that the range of f, which is obtained by decomposing x, is limited to 1≤f<2, processing by which the output value [[a0+a1f1+ . . . +anfn]] is calculated from the input value [[f]] is reduced to processing by which calculation is performed by using f−r+u and the concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of the previously generated random number r and a power of r−1. In general, information leaks when f−r+u is reconstructed; however, by adjusting f−r+u so as to be uniform random values greater than 0 and smaller than or equal to 1, it is possible to securely execute calculation of a0+a1f1+ . . . +anfn.

Third Embodiment

When the logarithm log x of x can be expressed as log x=a0+a1x1+ . . . +anxnby using a polynomial, concealed text [[log x]] of the logarithm log x can be efficiently calculated from concealed text [[x]] of x by using the secure computation algorithm of the first embodiment.

Hereinafter, input and output and procedures of a secure computation algorithm of a third embodiment and a secure computation system that implements the secure computation algorithm of the third embodiment will be described.

Input and output of the secure computation algorithm of the third embodiment shown inFIG. 8will be described.

Input is the order n and coefficients a0, a1, . . . , anof a polynomial a0+a1x1+ . . . +anxnand concealed text [[x]] of a value x whose logarithm is subjected to calculation of the value. Moreover, concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of a random number r, which satisfies 1≤r<2, and a power of r−1 is also input.

Output is concealed text [[log x]] of the logarithm log x of x.

The procedures of the secure computation algorithm of the third embodiment depicted inFIG. 8will be described. In so doing, expressions such as Step 1 and Step 2 are adopted by using the numerals on the left end ofFIG. 8.

In Step 1, for the input concealed text [[x]], concealed text [[e]] and [[f]] of e and f which satisfy x=2e×f (e is an integer and 1≤f<2) is generated. By using operations of Reference Non-patent Literature 1 to determine floating-point representation of [[x]], the concealed text [[e]] and [[f]] can be generated.

In Step 3, [[log f]]+[[e]] is calculated from the concealed text [[e]] generated in Step 1 and the concealed text [[log f]] calculated in Step 2. Here, [[log f]]+[[e]]=[[log x]] holds.

Hereinafter, a secure computation system30of the third embodiment will be described with reference toFIGS. 9 and 10. The secure computation system30differs from the secure computation system10in that the secure computation system30includes W (W is a predetermined integer greater than or equal to 2) secure computation devices3001, . . . ,300Winstead of including W secure computation devices1001, . . . ,100W.FIG. 9is a block diagram depicting the configuration of a secure computation device300i(1≤i≤W).FIG. 10is a flowchart showing an operation of the secure computation system30.

As depicted inFIG. 9, the secure computation device300idiffers from the secure computation device100iin that the secure computation device300ifurther includes an input value decomposition unit310iand a logarithm calculation unit320i. The input value decomposition unit310iand the logarithm calculation unit320iare also configured so as to be capable of executing, of computations which are required in the secure computation algorithm, computations which are required to implement the functions thereof.

By using concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of the previously generated random number r (1≤r<2) and a power of r−1, the secure computation system30calculates concealed text [[log x]] of the logarithm log x of x from concealed text [[x]] of the value x which is substituted into a polynomial. Hereinafter, an operation of the secure computation system30will be described in accordance withFIG. 10.

The input value decomposing means310generates, from the concealed text [[x]], concealed text [[e]] and [[f]] of e and f which satisfy x=2e×f (e is an integer and 1≤f<2) (S310). This corresponds to Step 1 of the secure computation algorithm ofFIG. 8.

The comparing means120, the mask means130, the reconstructing means140, the coefficient calculating means150, the selecting means160, and the linear combination means170calculate [[a0+a1f1+ . . . +anfn]] (=[[log f]]) from the order n and the coefficients a0, a1, . . . , anof the polynomial, the concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] generated before input of [[x]], and the concealed text [[f]] generated in S310(S120to S170). This corresponds to Step 2 of the secure computation algorithm ofFIG. 8(Steps 1 to 6 of the secure computation algorithm ofFIG. 1).

The logarithm calculating means320calculates [[log f]]+[[e]] as concealed text [[log x]] of the logarithm log x from the concealed text [[e]] generated in S310and the concealed text [[log f]] calculated in S120to S170(S320). This corresponds to Step 3 of the secure computation algorithm ofFIG. 8.

According to the invention of the present embodiment, by performing calculation of the polynomial a0+a1x1+ . . . +anxnby using the secure computation algorithm of the first embodiment, it is possible to reduce the cost of calculating the concealed text [[log x]] of the logarithm log x from the concealed text [[x]]. Moreover, by using the fact that the range off, which is obtained by decomposing x, is limited to 1≤f<2, processing by which the output value [[a0+a1f1+ . . . +anfn]] is calculated from the input value [[f]] is reduced to processing by which calculation is performed by using f−r+u and the concealed text [[r]], [[r2]], . . . , [[rn]], [[r−1]], [[(r−1)2]], . . . , [[(r−1)n]] of a power of the previously generated random number r and a power of r−1. In general, information leaks when f−r+u is reconstructed; however, by adjusting f−r+u so as to be uniform random values greater than 0 and smaller than or equal to 1, it is possible to securely execute calculation of a0+a1f1+ . . . +anfn.

APPENDIX

Each device according to the present invention has, as a single hardware entity, for example, an input unit to which a keyboard or the like is connectable, an output unit to which a liquid crystal display or the like is connectable, a communication unit to which a communication device (for example, communication cable) capable of communication with the outside of the hardware entity is connectable, a central processing unit (CPU, which may include cache memory and/or registers), RAM or ROM as memories, an external storage device which is a hard disk, and a bus that connects the input unit, the output unit, the communication unit, the CPU, the RAM, the ROM, and the external storage device so that data can be exchanged between them. The hardware entity may also include, for example, a device (drive) capable of reading and writing a recording medium such as a CD-ROM as desired. A physical entity having such hardware resources may be a general-purpose computer, for example.

The external storage device of the hardware entity has stored therein programs necessary for embodying the aforementioned functions and data necessary in the processing of the programs (in addition to the external storage device, the programs may be prestored in ROM as a storage device exclusively for reading out, for example). Also, data or the like resulting from the processing of these programs are stored in the RAM and the external storage device as appropriate.

In the hardware entity, the programs and data necessary for processing of the programs stored in the external storage device (or ROM and the like) are read into memory as necessary to be interpreted and executed/processed as appropriate by the CPU. As a consequence, the CPU embodies predetermined functions (the components represented above as units, means, or the like).

The present invention is not limited to the above embodiments, but modifications may be made within the scope of the present invention. Also, the processes described in the embodiments may be executed not only in a chronological sequence in accordance with the order of their description but may be executed in parallel or separately according to the processing capability of the device executing the processing or any necessity.

As already mentioned, when the processing functions of the hardware entities described in the embodiments (the devices of the present invention) are to be embodied with a computer, the processing details of the functions to be provided by the hardware entities are described by a program. By the program then being executed on the computer, the processing functions of the hardware entity are embodied on the computer.

The program describing the processing details can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any kind, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. More specifically, a magnetic recording device may be a hard disk device, flexible disk, or magnetic tape; an optical disk may be a DVD (digital versatile disc), a DVD-RAM (random access memory), a CD-ROM (compact disc read only memory), or a CD-R (recordable)/RW (rewritable); a magneto-optical recording medium may be an MO (magneto-optical disc); and a semiconductor memory may be EEP-ROM (electronically erasable and programmable-read only memory), for example.

Also, the distribution of this program is performed by, for example, selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. Furthermore, a configuration may be adopted in which this program is distributed by storing the program in a storage device of a server computer and transferring the program to other computers from the server computer via a network.

The computer that executes such a program first, for example, temporarily stores the program recorded on the portable recording medium or the program transferred from the server computer in a storage device thereof. At the time of execution of processing, the computer then reads the program stored in the storage device thereof and executes the processing in accordance with the read program. Also, as another form of execution of this program, the computer may read the program directly from the portable recording medium and execute the processing in accordance with the program and, furthermore, every time the program is transferred to the computer from the server computer, the computer may sequentially execute the processing in accordance with the received program. Also, a configuration may be adopted in which the transfer of a program to the computer from the server computer is not performed and the above-described processing is executed by so-called application service provider (ASP)-type service by which the processing functions are implemented only by an instruction for execution thereof and result acquisition. Note that a program in this form shall encompass information that is used in processing by an electronic computer and acts like a program (such as data that is not a direct command to a computer but has properties prescribing computer processing).

Further, although the hardware entity was described as being configured via execution of a predetermined program on a computer in this form, at least some of these processing details may instead be embodied with hardware.