Calculation device, calculation method, and program

Abstract

A first calculation unit is capable of calculating f(x).sup.bx.sub.1 and sets a calculation result of f(x).sup.bx.sub.1 to u, and a second calculation unit is capable of calculating f(x).sup.ax.sub.2, and sets a calculation result of f(x).sup.ax.sub.2 to v. A final calculation unit outputs (u.sup.b′v.sup.a′).sup.1/d for d=a′a+b′b when the calculation result u and the calculation result v satisfy u.sup.a=v.sup.b. Here, G and H are groups, f is a function for mapping an element x of the group H to the group G, X.sub.1 and X.sub.2 are random variables values of which are in the group G, a realization of the random variable X.sub.1 is x.sub.1, a realization of the random variable X.sub.2 is x.sub.2, and a, b, a′, and b′ are integers.

Claims

1. A calculation device comprising: processing circuitry configured to select integers a, b, a′, and b′ at random; calculate f(x).sup.bx.sub.1 and set a calculation result of f(x).sup.bx.sub.1 to u; calculate f(x).sup.ax.sub.2 and set a calculation result of f(x).sup.ax.sub.2 to v; calculate d=a′a+b′b with the integers a, b, a′ and b′ when the calculation result u and the calculation result v satisfy u.sup.a=v.sup.b; calculate (u.sup.b′v.sup.a′).sup.1/d for the calculated d when d≠0 is satisfied; and output (u.sup.b′v.sup.a′).sup.1/d for d=a′a+b′b when (u.sup.b′v.sup.a′).sup.1/d is calculated; wherein G and H are groups, f is a function for mapping an element x of the group H to the group G, X.sub.1 and X.sub.2 are random variables values of which are in the group G, a realization of the random variable X.sub.1 is x.sub.1, a realization of the random variable X.sub.2 is x.sub.2, and when the processing circuitry determines that the calculation result u and the calculation result v fail to satisfy u.sup.a=v.sup.b after a predetermined number of iterations, the processing circuitry terminates the calculations and outputs a determination result that indicates that the calculation device cannot perform the calculations within a predetermined standard of reliability.

2. The calculation device according to claim 1, wherein d≠1 is satisfied.

3. A non-transitory computer-readable recording medium in which a program for making a computer function as the calculation device according to claim 1 or 2 is recorded.

4. A calculation method, implemented by a calculation device, comprising: selecting integers a, b, a′, and b′ at random; setting a calculation result of f(x).sup.bx.sub.1 to u in which f(x).sup.bx.sub.1 is calculable; setting a calculation result of f(x).sup.ax.sub.2 to v in which f(x).sup.ax.sub.2 is calculable; calculating d=a′a+b′b with the integers a, b, a′ and b′ when the calculation result u and the calculation result v satisfy u.sup.a=v.sup.b; calculating (u.sup.b′v.sup.a′).sup.1/d for the calculated d when d≠0 is satisfied; and outputting (u.sup.b′v.sup.a′).sup.1/d is calculated; wherein G and H are groups, f is a function for mapping an element x of the group H to the group G, X.sub.1 and X.sub.2 are random variables values of which are in the group G, a realization of the random variable X.sub.1 is x.sub.1, a realization of the random variable X.sub.2 is x.sub.2, and when determining that the calculation result u and the calculation result v fail to satisfy u.sup.a=v.sup.b after a predetermined number of iterations, terminating the calculations and outputting a determination result that indicates that the calculation device cannot perform the calculations within a predetermined standard of reliability.

5. The calculation method according to claim 4, wherein d≠1 is satisfied.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating the configuration of a calculation device which executes a self-correcting technique of a first embodiment.

(2) FIG. 2 is a flow diagram illustrating a self-correcting method of the first embodiment.

(3) FIG. 3 is a block diagram illustrating the configuration of a calculation system which executes a self-correcting technique of a second embodiment.

(4) FIG. 4 is a block diagram illustrating the configuration of a calculation device of FIG. 3.

(5) FIG. 5 is a block diagram illustrating the configuration of a capability provision device of FIG. 3,

(6) FIG. 6 is a flow diagram illustrating processing of the calculation device of the second embodiment.

(7) FIG. 7 is a flow diagram illustrating processing of the capability provision device of the second embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(8) Embodiments of the present invention will be described below with reference to the accompanying drawings.

(9) [First Embodiment]

(10) <Configuration>

(11) As illustrated in FIG. 1, a calculation device 1 according to a first embodiment includes an integer selection unit 112, a first power calculation unit 113, a first list storage unit 114, a determination unit 115, a second power calculation unit 116, a second list storage unit 117, a control unit 118, a final calculation unit 119, a first randomizable sampler 121, and a second randomizable sampler 122. In the first embodiment, the first randomizable sampler 121 and the second randomizable sampler 122 correspond to a “first calculation unit” and a “second calculation unit” respectively. It is assumed that G and H are groups (for example, finite commutative groups such as a cyclic group), function ƒ:H.fwdarw.G is a function for mapping an element x of the group H to the group G, generators of the groups G and H are μ.sub.g and μ.sub.h respectively, X.sub.1 and X.sub.2 are random variables values of which are in the group G, a realization of the random variable X.sub.1 is x.sub.1, and a realization of the random variable X.sub.2 is x.sub.x. The calculation device 1 is a device which is configured when a general-purpose or special-purpose computer, which is provided with a processor (hardware processor) such as a central processing unit (CPU), a memory such as a random-access memory (RAM) and a read-only memory (ROM), and the like, executes a predetermined program, for example. The computer may include a single piece of processor and a single piece of memory or include a plurality of processors and a plurality of memories.

(12) This program may be installed on the computer or may be recorded in a ROM or the like in advance. Further, a part or all processing units may be constituted by using an electronic circuit which independently realizes the processing configuration instead of an electronic circuit (circuitry), which realizes the functional configuration when a program is read in, such as a CPU. Furthermore, an electronic circuit constituting a single piece of device may include a plurality of CPUs.

(13) <Processing>

(14) As illustrated in FIG. 2, the integer selection unit 112 selects integers a, b, a′, and b′ at random (step S 101). The integers a, b, a′, and b′ may be selected from any range. a and b may be coprime and do not have to be coprime. For example, a and b are positive integers. However, at least one of a and b may be 0 or a negative integer. Information about the integers a and b is transmitted to the first power calculation unit 113, the second power calculation unit 116, the first randomizable sampler 121, and the second randomizable sampler 122. Information about the integers a, b, a′, and b′ is transmitted to the final calculation unit 119.

(15) The control unit 118 sets t=1 (step S102).

(16) The first randomizable sampler 121 is capable of calculating f(x).sup.bx.sub.1. The first randomizable sampler 121 performs calculation by using x and b and sets the calculation result to u (step S103). A specific example of the calculation result u will be described later. The calculation result u is transmitted to the first power calculation unit 113. In this application, the expression “capable of calculating” represents that calculation can be correctly performed with a probability which is equal to or larger than a non-negligible probability. The non-negligible probability represents a probability which is equal to or larger than 1/F(k) when a polynomial which is a broadly monotonic function for a security parameter k (here, k is a positive natural number) is set to a polynomial F(k). An example of the broadly monotonic function is a monotonically non-decreasing function (non-decreasing function). Here, to calculate f(x).sup.bx.sub.1 represents to obtain a value of a formula which is defined as f(x).sup.bx.sub.1. As long as a value of the formula f(x).sup.bx.sub.1 can be finally obtained, a calculation method does not matter. The same goes for calculation of other formulas which will appear in this application. Further, in this application, calculation which is defined by a group is expressed in a multiplicative manner.

(17) The first power calculation unit 113 calculates u′=u.sup.a (step S104). A pair (u,u′) of the calculation result u and u′ which is obtained by calculation based on the calculation result u is stored in the first list storage unit 114.

(18) The determination unit 115 determines whether or not there is a pair which satisfies u′=v′ among pairs (u,u′) which are stored in the first list storage unit 114 and pairs (v,v′) which are stored in the second list storage unit 117 (step S105). If pairs (v,v′) are not stored in the second list storage unit 117, processing of following step S106 is performed without performing the processing of step S105. When there is a pair which satisfies u′=v′, the process goes to step S112. When there is not a pair which satisfies u′=v′, the process goes to step S106.

(19) The second randomizable sampler 122 is capable of calculating f(x).sup.ax.sub.2. The second randomizable sampler 122 performs calculation by using x and a and sets the calculation result to v (step S106). A specific example of the calculation result v will be described later. The calculation result v is transmitted to the second power calculation unit 116. The second power calculation unit 116 calculates v′=v.sup.b (step S107). A pair (v,v′) of the calculation result v and v′ which is obtained by calculation based on the calculation result v is stored in the second list storage unit 117.

(20) The determination unit 115 determines whether or not there is a pair which satisfies u′=v′ among pairs (u,u′) which are stored in the first list storage unit 114 and pairs (v,v′) which are stored in the second list storage unit 117 (step S108). When there is a pair which satisfies u′=v′, the process goes to step S112. When there is not a pair which satisfies u′=v′, the process goes to step S110.

(21) The control unit 118 determines whether or not t=T is satisfied (step S110). T denotes a predetermined positive natural number. When t=T is satisfied, the control unit 118 outputs information representing that calculation is impossible, for example, outputs a symbol “⊥” (step S111) and the processing is ended. The information representing that calculation is impossible (the symbol “⊥” in this example) represents that reliability of performance of correct calculation is below a reference which is defined by T. In other words, the information represents that calculation has not been able to be correctly performed in T-time repetitions. When t=T is not satisfied, the control unit 118 increments t by 1, that is, sets as t=t+1 (step S109) and the process returns to step S103.

(22) When it is determined that u′=v′ is satisfied, the final calculation unit 119 calculates d=a′a+b′b (step S112) and calculates (u.sup.b′v.sup.a′).sup.1/d by using u and v which correspond to u′ and v′, and a′, b′, and d so as to output u.sup.b′v.sup.a′).sup.1/d (step S113). That is, the final calculation unit 119 obtains d=a′a+b′b and outputs (u.sup.b′v.sup.a′).sup.1/d for d. The outputted (u.sup.b′v.sup.a′).sup.1/d satisfies (u.sup.b′v.sup.a′).sup.1/d=f(x). The reason will be described below.

(23) <<Reason Why (u.sup.b′v.sup.a′).sup.1/d=f(x) is satisfied>>

(24) As disclosed in Patent Literature 1 and Patent Literature 2, if u′=v′ holds, that is, if u.sup.a=v.sup.b holds, it is highly probable that the first randomizable sampler has correctly computed u=f(x).sup.b, the second randomizable sampler has correctly computed v=f(x).sup.a, and x.sub.1 and x.sub.2 are identity elements e.sub.g of the group G. When the first randomizable sampler 121 correctly calculates u=f(x).sup.bx.sub.1, further, the second randomizable sampler 122 correctly calculates v=f(x).sup.ax.sub.2, and x.sub.1 and x.sub.2 are identity elements e.sub.g of the group G, u.sup.b′v.sup.a′=(f(x).sup.bx.sub.1).sup.b′(f(x).sup.ax.sub.2).sup.a′=(f(x).sup.be.sub.g).sup.b′(f(x).sup.ae.sub.g).sup.a′=f(x).sup.bb′e.sub.g.sup.b′f(x).sup.aa′e.sub.g.sup.a′=f(x).sup.(a′a+b′b) is satisfied. Here, u.sup.b′v.sup.a′=f(x).sup.d is satisfied when d=a′a+b′b. Therefore, (u.sup.b′v.sup.a′).sup.1/d=f(x) is satisfied.

(25) <<Specific Examples of u and v>>

(26) Examples of u and v include u and v which are disclosed in Patent Literature 1 and Patent Literature 2. For example, u=z.sub.1ν.sup.−r1 and v=z.sub.2ν.sup.−r2 are held. Here, the group H is a cyclic group, a generator of the cyclic group H is μ.sub.h, r1 and r2 are random natural numbers which are 0 or larger, ν=f(μ.sub.h) is satisfied, τ.sub.1=μ.sub.h.sup.r1x.sup.b is satisfied, τ.sub.2=μ.sub.h.sup.r2x.sup.a is satisfied, further, z.sub.1=f(τ.sub.1) is satisfied with a probability larger than a certain probability, and z.sub.2=f(τ.sub.2) is satisfied with a probability larger than a certain probability. That is, z.sub.1=f(τ.sub.1) may be satisfied or z.sub.1≠f(τ.sub.1) may be satisfied. Further, z.sub.2=f(τ.sub.2) may be satisfied or z.sub.2≠f(τ.sub.2) may be satisfied. Namely, z.sub.1 and z.sub.2 are respectively calculation results f(τ.sub.1) and f(τ.sub.2) which include an intended or unintended error. “A certain probability” is a probability which is smaller than 100% and equal to or larger than 0%. An example of “a certain probability” is a non-negligible probability.

(27) Alternatively, u=z.sub.1Y.sup.−r4μ.sub.g.sup.−r5 and v=z.sub.2Y.sup.−r6μ.sub.g.sup.−r7 may be satisfied. Here, the group H is a direct product group G×G of the group G, the group G is a cyclic group, a generator of the cyclic group G is μ.sub.g, x=(c.sub.1,c.sub.2), (V,W) is an element of the group H, f(V,W)=Y, r4 to r7 are random numbers of natural numbers which are 0 or larger, τ.sub.1(c.sub.2.sup.bW.sup.−r4,c.sub.1.sup.bV.sup.r4μ.sub.g.sup.r5) is satisfied, τ.sub.2=(c.sub.2.sup.aW.sup.r6,c.sub.1.sup.aV.sup.r6μ.sub.g.sup.r7) is satisfied, z.sub.1=f(τ.sub.1) is satisfied with a probability larger than a certain probability, and z.sub.2=f(τ.sub.2)is satisfied with a probability larger than a certain probability.

(28) [Modification of First Embodiment]

(29) One of the integers a and b may be a constant such as 1 and at least one of the integers a′ and b′ may be a constant. A part of the integers a, b, a′, and b′ may be a constant and a part of processing units and steps may be omitted. For example, when b is a constant which is 1, selection of the integer b in step S101 is unnecessary and v′=ν is obtained. Therefore, the second power calculation unit 116 and step S107 are unnecessary. Alternatively, d may be set to a constant or a random number which is other than 1, the integers a, b, a′, and b′ which satisfy d=a′a+b′b may be selected in step S101, and whereby the processing of step S112 may be omitted. Alternatively, the integer selection unit 112 may perform selection of the integers a, b, a′, and b′ and calculation of d=a′a+b′b in step S101. Alternatively, the integer selection unit 112 may calculate d=a′a+b′b at any time after step S102 and before step S113. In these cases, the processing of step S112 is omitted and the final calculation unit 119 obtains d from the integer selection unit 112. Further, the final calculation unit 119 may output (u.sup.b′v.sup.a′).sup.1/d in a case of d≠0. In a case of d=0, error termination may be performed. Alternatively, in a case of d=0, at least a part of the integers a, b, a′, and b′ may be reselected in step S101 and the processing may be done again. Further, a′ and b′ may be selected at any time as long as the selection is performed before a′ and b′ become necessary for calculation.

(30) [Second Embodiment]

(31) A second embodiment shows the configuration in which the first embodiment is applied to a cloud type key management system. Differences with the first embodiment will be chiefly described below and description of points common to the first embodiment will be omitted.

(32) <Configuration>

(33) As illustrated in FIG. 3, a proxy calculation system 2 according to the second embodiment includes a calculation device 21 which does not hold a decryption key and a capability provision device 22 which holds the decryption key, for example. The calculation device 21 requests the capability provision device 22 to provide capability of decryption of a cipher text and decrypts the cipher text by using the decryption capability which is provided from the capability provision device 22. The calculation device 21 and the capability provision device 22 are configured to be able to exchange information. For example, the calculation device 21 and the capability provision device 22 are enabled to exchange information via a transmission line, a network, a portable recording medium, or the like.

(34) As illustrated in FIG. 4, the calculation device 21 according to the second embodiment includes an integer selection unit 2102, an input information provision unit 2104, a first calculation unit 2105, a first power calculation unit 2106, a first list storage unit 2107, a second calculation unit 2108, a second power calculation unit 2109, a second list storage unit 2110, a determination unit 2111, a final output unit 2112, and a control unit 2113. Examples of the calculation device 21 include equipment, which is provided with a calculating function and a storing function, such as a card reader/writer device and a mobile telephone, a computer, on which a special program is loaded, such as the above-described computer, and the like. Further, a part or all processing units may be constituted by using an electronic circuit which independently realizes the processing function instead of an electronic circuit, which realizes the functional configuration when a program is read in, such as a CPU.

(35) As illustrated in FIG. 5, the capability provision device 22 of the second embodiment includes a first output information calculation unit 2201, a second output information calculation unit 2202, a key storage unit 2204, and a control unit 2205, for example. Examples of the capability provision device 22 include a tamper resistant module such as an IC card and an IC chip, equipment, which is provided with a calculating function and a storing function, such as a mobile telephone, a computer, on which a special program is loaded, such as the above-described computer, and the like.

(36) <Processing>

(37) Processing of the present embodiment is now described. As premises for the processing, G and H are groups (for example, finite commutative groups such as a cyclic group), f(x) is a decryption function by which a cipher text x which is an element of the group H is decrypted by a specific decryption key s so as to obtain an element of the group G, generators of the groups G and H are μ.sub.g and μ.sub.h respectively, X.sub.1 and X.sub.2 are random variables values of which are in the group G, a realization of the random variable X.sub.1 is x.sub.1, and a realization of the random variable X.sub.2 is x.sub.2. Each processing of the calculation device 21 is executed in the control of the control unit 2113 and each processing of the capability provision device 22 is executed in the control of the control unit 2205.

(38) As illustrated in FIG. 6, the integer selection unit 2102 of the calculation device 21 (FIG. 4) selects integers a, b, a′, and b′ at random (step S2101). At least a part of information of the integers a and b is transmitted to the input information provision unit 2104, the first power calculation unit 2106, and the second power calculation unit 2109. Information of the integers a, b, a′, and b′ is transmitted to the final output unit 2112.

(39) The control unit 2113 sets t=1 (step S2102).

(40) The input information provision unit 2104 generates and outputs first input information τ.sub.1 and second input information τ.sub.2 which respectively correspond to the inputted cipher text x and are elements of the group H (step S2103). Preferably, each of the first input information τ.sub.1 and the second input information τ.sub.2 is information obtained by perturbing a relation with the cipher text x. For example, the first input information τ.sub.1 and the second input information τ.sub.2 respectively correspond to the cipher text x, but it is hard to obtain the cipher text x only from the first input information τ.sub.1 and the second input information τ.sub.2. The expression “hard to obtain the cipher text x” represents that it is impossible to obtain the cipher text x within polynomial time, for example. Accordingly, the calculation device 21 can conceal the cipher text x from the capability provision device 22. Preferably, the first input information τ.sub.1 of the present embodiment further corresponds to the integer b which is selected by the integer selection unit 2102 and the second input information τ.sub.2 further corresponds to the integer a which is selected by the integer selection unit 2102. Accordingly, the calculation device 21 is enabled to evaluate the decryption capability provided from the capability provision device 22 with high precision. Specific examples of τ.sub.1 and τ.sub.2 are same as those illustrated in the first embodiment.

(41) As illustrated in FIG. 7, the first input information τ.sub.1 is inputted is into the first output information calculation unit 2201 of the capability provision device 22 (FIG. 5) and the second input information τ.sub.2 is inputted into the second output information calculation unit 2202 (step S2200).

(42) The first output information calculation unit 2201 correctly calculates f(τ.sub.1) with a probability larger than a certain probability by using the first input information τ.sub.1 and the decryption key s stored in the key storage unit 2204 and sets the obtained calculation result to first output information z.sub.1 (step S2201). The second output information calculation unit 2202 correctly calculates f(τ.sub.2) with a probability larger than a certain probability by using the second input information τ.sub.2 and the decryption key s stored in the key storage unit 2204 and sets the obtained calculation result to second output information z.sub.2 (step S2202). Namely, the first output information calculation unit 2201 and the second output information calculation unit 2202 output calculation results which include an intended or unintended error. In other words, the result of the computation by the first output information calculation unit 2201 may or may not be f(τ.sub.l), and the result of the computation by the second output information calculation unit 2202 may or may not be f(τ.sub.2).

(43) The first output information calculation unit 2201 outputs the first output information z.sub.1 and the second output information calculation unit 2202 outputs the second output information z.sub.2 (step S2203).

(44) Referring back to FIG. 6, the first output information z.sub.1 is inputted into the first calculation unit 2105 of the calculation device 21 (FIG. 4) and the second output information z.sub.2 is inputted into the second calculation unit 2108. The first output information z.sub.1 and the second output information z.sub.2 correspond to decryption capability which is provided from the capability provision device 22 to the calculation device 21 (step S2104).

(45) The first calculation unit 2105 generates a calculation result u=f(x).sup.bx.sub.1 from the first output information z.sub.1. z.sub.1=f(τ.sub.1) may or may not be satisfied. The first calculation unit 2105 is capable of generating the calculation result u=f(x).sup.bx.sub.1. A specific example of a method for generating u from z.sub.1 is described in the first embodiment. For example, u=z.sub.1ν.sup.−r1 is satisfied for τ.sub.1=μ.sub.h.sup.r1x.sup.b, u=z.sub.1Y.sup.−r4μ.sub.g.sup.−r5 is satisfied for τ.sub.1=(c.sub.2.sup.bW.sup.r4,c.sub.1.sup.bV.sup.r4μ.sub.g.sup.r5). The calculation result u is transmitted to the first power calculation unit 2106 (step S2105).

(46) The first power calculation unit 2106 calculates u′=u.sup.a. A pair (u,u′) of the calculation result u and u′ which is obtained by calculation based on the calculation result u is stored in the first list storage unit 2107 (step S2106).

(47) The determination unit 2111 determines whether or not there is a pair which satisfies u′=v′ among pairs (u,u′) which are stored in the first list storage unit 2107 and pairs (v,v′) which are stored in the second list storage unit 2110 (step S2107). If pairs (v,v′) are not stored in the second list storage unit 2110, processing of following step S2108 is performed without performing the processing of step S2107. When there is a pair which satisfies u′=v′, the process goes to step S2114. When there is not a pair which satisfies the process goes to step S2108.

(48) In step S2108, the second calculation unit 2108 generates a calculation result v=f(x).sup.ax.sub.2 from the second output information z.sub.2. z.sub.2=f(τ.sub.2) may or may not be satisfied. The second calculation unit 2108 is capable of generating the calculation result v=f(x).sup.ax.sub.2. A specific example of a method for generating v from z.sub.2 is described in the first embodiment. For example, v=z.sub.2ν.sup.−r2 is satisfied for τ.sub.2=μ.sub.h.sup.r2x.sup.a, and ν=z.sub.2Y.sup.−r6μ.sub.g.sup.−r7 is satisfied for τ.sub.2=(c.sub.2.sup.aW.sup.r6,c.sub.1.sup.aV.sup.r6μ.sub.g.sup.r7). The calculation result v is transmitted to the second power calculation unit 2109 (step S2108).

(49) The second power calculation unit 2109 calculates v′=v.sup.b. A pair (v,v′) of the calculation result v and v′ which is obtained by calculation based on the calculation result v is stored in the second list storage unit 2110 (step S2109).

(50) The determination unit 2111 determines whether or not there is a pair which satisfies u′=v′ among pairs (u,u′) which are stored in the first list storage unit 2107 and pairs (v,v′) which are stored in the second list storage unit 2110 (step S2110). When there is a pair which satisfies u′=v′, the process goes to step S2114. When there is not a pair which satisfies u′=v′, the process goes to step S2111.

(51) In step S2111, the control unit 2113 determines t=T.sub.max is satisfied (step S2111). T.sub.max is a predetermined natural number. When t=T.sub.max is satisfied, the control unit 2113 outputs information representing that the calculation is impossible, for example, outputs a symbol “⊥” (step S2113) and the processing is ended. When t=T.sub.max is not satisfied, the control unit 2113 increments t by 1, that is, sets as t=t+1 (step S2112) and the process returns to step S2103.

(52) In step S2114, the final output unit 2112 calculates d=a′a+b′b (step S2114) and calculates (u.sup.b′v.sup.a′).sup.1/d by using u and v which correspond to u′ and v′, and a′, b′, and d so as to output (u.sup.b′v.sup.a′).sup.1/d (step S2115). That is, the final output unit 2112 obtains d=a′a+b′b and outputs (u.sup.b′v.sup.a′.sup.1/d for d. The outputted (u.sup.b′v.sup.a′).sup.1/d is a decryption result f(x) of the cipher text x with high probability. Further, the above-described processing may be repeated several times and the most common value among values obtained in step S2115 may be set to a decryption result.

(53) [Modification of Second Embodiment]

(54) One of the integers a and b may be a constant such as 1 and at least one of the integers a′ and b′ may be a constant. A part of the integers a, b, a′, and b′ may be a constant and a part of processing units and steps may be omitted. For example, when b is a constant which is 1, selection of the integer b in step S2101 is unnecessary and v′=v is obtained. Therefore, the second power calculation unit 2109 and step S2109 are unnecessary. Alternatively, d may be set to a constant or a random number which is other than 1, the integers a, b, a′, and b′ which satisfy d=a′a+b′b may be selected in step S2101, and whereby the processing of step S2114 may be omitted. Alternatively, the integer selection unit 2102 may perform selection of the integers a, b, a′, and b′ and calculation of d=a′a+b′b in step S2101. Alternatively, the integer selection unit 2102 may calculate d=a′a+b′b at any time after step S2102 and before step S2115. In these cases, the processing of step S2114 is omitted and the final output unit 2112 obtains d from the integer selection unit 2102. Further, the final output unit 2112 may output (u.sup.b′v.sup.a′).sup.1/d when d≠0 is satisfied. The processing may terminate with error when d=0 is satisfied. Alternatively, when d=0 is satisfied, at least a part of the integers a, b, a′, and b′ may be reselected in step S2101 and the processing may be performed again. Further, a′ and b′ may be selected at any time as long as the selection is performed before a′ and b′ become necessary for calculation.

(55) [Other Modifications]

(56) The present invention is not limited to the above-described embodiments. For example, the self-correcting technique in each embodiment of Patent Literature 2, Japanese Patent Application Laid Open No. 2012-237881, Japanese Patent Application Laid Open No. 2012-220834, Japanese Patent Application Laid Open No. 2012-220814, Japanese Patent Application Laid Open No. 2012-151756, and the like may be used for the self-correcting technique of the present invention.

(57) For example, the calculation system may further include a decryption control device in the second embodiment. This decryption control device may output a decryption control command for controlling decryption processing of the calculation device to the capability provision device and the capability provision device may control whether or not both of the first output information z.sub.1 and the second output information z.sub.2 are outputted, in accordance with the decryption control command. Further, the calculation system may include a plurality of pieces of capability provision devices and output a decryption control command to any of the capability provision devices and each of the capability provision devices may control whether or not both of the first output information z.sub.1 and the second output information z.sub.2 are outputted, in accordance with the decryption control command.

(58) In the second embodiment, the calculation system may further include a decryption control device, G.sub..Math. and H.sub..Math. may be groups, ω may be an integer which is 2 or larger, .Math.=1, . . . , ω, f.sub..Math.(λ.sub..Math.) may be a decryption function by which a cipher text λ.sub..Math. which is an element of the group H.sub..Math. is decrypted by a specific decryption key s.sub..Math. so as to obtain an element of the group G.sub..Math., X.sub..Math.,1 and X.sub..Math.,2 may be random variables values of which are in the group G.sub..Math., x.sub..Math.,1 may be a realization of the random variable X.sub..Math.,1, x.sub..Math.,2 may be a realization of the random variable X.sub..Math.,2, a(.Math.), b(.Math.), a′(.Math.), and b′(.Math.) may be integers, the group G may be a group G.sub.1, the group H may be a group H.sub.1, the cipher text x may be a cipher text λ.sub.1, the decryption function f(x) may be a decryption function f.sub.1(λ.sub.1), the random variable X.sub.1 may be a random variable X.sub.1,1, the random variable X.sub.2 may be a random variable X.sub.1,2, the realization x.sub.1 may be a realization x.sub.1,1, the realization x.sub.2 may be a realization x.sub.1,2, the integer a may be an integer a(1), the integer b may be an integer b(1), the integer at may be an integer a′(1), and the integer b′ may be an integer b′(1). In this case, the calculation device outputs first input information τ.sub..Math.,1 and second input information τ.sub..Math.,2 which correspond to the cipher text λ.sub..Math. and are elements of the group H.sub..Math., and the capability provision device correctly calculates f.sub..Math.(τ.sub..Math.,1) with a probability larger than a certain probability by using the first input information τ.sub..Math.,1 so as to output the obtained arithmetic result as first output information z.sub..Math.,1 and the capability provision device correctly calculates f.sub..Math.(τ.sub..Math.,2) with a probability larger than a certain probability by using the second input information τ.sub..Math.,2 so as to output the obtained arithmetic result as second output information z.sub..Math.,2. The calculation device generates an arithmetic result u.sub..Math.=f.sub..Math.(λ.sub..Math.).sup.b(.Math.)x.sub..Math.,1 based on the first output information z.sub..Math.,1 and generates an arithmetic result v.sub..Math.=f.sub..Math.(λ.sub..Math.).sup.a(.Math.)x.sub..Math.,2 based on the second output information z.sub..Math.,2. When the arithmetic results u.sub..Math. and v.sub..Math. satisfy u.sub..Math..sup.a(.Math.)=v.sub..Math..sup.b(.Math.), the calculation device obtains a′(.Math.)a(.Math.)+b′(.Math.)b(.Math.)=d(.Math.), for example, so as to output (u.sub..Math..sup.b′(.Math.)v.sub..Math..sup.a′(.Math.)).sup.1/d(.Math.) for d(.Math.). The decryption control device Outputs a decryption control command for controlling decryption processing of the calculation device to the capability provision device and the capability provision device control whether or not both of the first output information z.sub..Math.,1 and the second output information z.sub..Math.,2 are outputted from the first output information calculation unit and the second output information calculation unit, in accordance with the decryption control command.

(59) Further, in this case, the decryption control command may correspond to any decryption function f.sub..Math. and the capability provision device may control presence/absence of outputs of both of the first output information z.sub..Math.,1 and the second output information z.sub..Math.,2 which correspond to the decryption function ƒ.sub..Math. corresponding to the decryption control command. Furthermore, the calculation device may generate a restored value which is restorable only when all decryption values which are obtained by decrypting the cipher texts λ.sub..Math. for respective .Math.=1, . . . , ω with the decryption key s.sub..Math. are obtained, by using (u.sub..Math..sup.b′(.Math.)v.sub..Math..sup.a′(.Math.)).sup.1/d(.Math.) for respective .Math.=1, . . . , ω which are outputted from the final output unit.

(60) Further, in the second embodiment, the calculation system may include a plurality of pieces of calculation devices and the calculation devices may obtain a decryption result by using one piece of capability provision device.

(61) In the second embodiment, f(x) is a decryption function by which the cipher text x which is an element of the group H is decrypted by the specific decryption key s to obtain an element of the group G. However, other functions for obtaining an element of the group G based on an input of an element x of the group H may be set as f(x) in the second embodiment. For example, f(x) may be an encryption function.

(62) Further, instead of exchanging information via a network by respective devices, at least part of pairs of the devices may exchange information via a portable recording medium. Alternatively, at least part of pairs of devices may exchange information via a non-portable recording medium. That is, a combination composed of part of these devices may be a single device. Alternatively, the calculation device may be composed of a plurality of devices and the capability provision device may be composed of a plurality of devices.

(63) The above-described various types of processing may be executed not only in a time-series manner in accordance with the description but also in a parallel manner or an independent manner, depending on processing capability of a device which executes the processing or as necessary. Further, it is indisputable that alterations can be arbitrarily made without departing from the intent of the present invention.

(64) In a case where the above-described configuration is realized by a computer, processing contents of functions which should be obtained by respective devices are described by a program. By executing this program by a computer, the above-described processing functions are realized on the computer. The program in which the processing contents are described can be recorded in a recording medium which is readable by a computer. An example of the recording medium which is readable by a computer is a is non-transitory recording medium. Examples of such recording medium include a magnetic recording device, an optical disk, a magnetooptical recording medium, a semiconductor memory, and the like.

(65) This program is distributed by selling, transferring, or lending a portable recording medium such as a DVD and a CD-ROM in which the program is recorded, for example. Further, this program may be distributed such that this program is stored in a storage device of a server computer and is transferred from the server computer to other computers through the network.

(66) A computer which executes such program once stores the program which is recorded in a portable recording medium or the program transferred from the server computer a storage device thereof, for example. In execution of processing, the computer reads the program which is stored in the storage device thereof and executes processing in accordance with the program which is read. As another executing configuration of this program, a computer may directly read the program from a portable recording medium so as to execute processing in accordance with the program, and further, the computer may sequentially execute processing in accordance with a received program whenever a program is transferred from the server computer to this computer. The above-described processing may be executed by a service of an application service provider (ASP) type in which a processing function is realized only by an executing instruction of processing and result acquisition, without transferring the program to the computer from the server computer.

(67) The processing functions of the present device are realized by executing a predetermined program on a computer in the above-described embodiment, but at least a part of these processing functions may be realized on hardware.

DESCRIPTION OF REFERENCE NUMERALS

(68) 1, 21: calculation device

(69) 2: proxy calculation system