Patent Publication Number: US-9842086-B2

Title: Calculation device, calculation method, and program

Description:
TECHNICAL FIELD 
     The present invention relates to a cryptographic technique, particularly to a self-correcting technique. 
     BACKGROUND ART 
     A self-correcting technique is one of cryptographic techniques (refer to Patent Literature 1 and Patent Literature 2, for example). The self-correcting technique is a technique for performing correct calculation at all time by using a calculator or a system which does not always output a correct calculation result (when a calculator which outputs a correct calculation result is used, a correct calculation result is outputted, and when a calculator which does not always output a correct result is used, a correct calculation result is obtained or a result representing that the calculation is impossible is obtained). For example, in a cloud-key management type decryption technique employing the self-correcting technique, a decryption capability provision device which holds a decryption key provides a decryption device only with information, by which the decryption device decrypts a cipher text, without providing the decryption device with the decryption key. The decryption device can always perform correct decryption calculation with this information. 
     PRIOR ART LITERATURE 
     Patent Literature 
     Patent literature 1: International Publication No. WO/2011/086992 
     Patent literature 2: International Publication No. WO/2012/057134 
     SUMMARY OF THE. INVENTION 
     Problems to be Solved by the Invention 
     However, in the self-correcting technique described on Patent Literature 1 and Patent Literature 2, two natural numbers a and b which are coprime are used and u b′ v a′  for integers a′ and b′ which satisfy the relation of a′a+b′b=1 is obtained. When a and b is not coprime or a′ and b′ do not satisfy the relation of a′a+b′b=1, this self-correcting technique is not available. 
     In view of such problem, an object of the present invention is to provide a self-correcting technique exhibiting high flexibility in setting. 
     Means to Solve the Problems 
     In the present invention, f(x) b x 1  is calculable, a calculation result of f(x) b x 1  is denoted as u, f(x) a x 2  is calculable, a calculation result of f(x) a x 2  is denoted as v, and (u b′ v a′ ) 1/d  for d=a′a+b′b is outputted in a case where the calculation results u and v satisfy u a =v b . 
     Effects of the Invention 
     The self-correcting technique of the present invention is available in such cases where a and b is not coprime and a′ and b′ do not satisfy the relation of a′a+b′b=1 because (u b′ v a′ ) 1/d  for d=a′a+b′b is obtained. Thus, the self-correcting technique of the present invention exhibits high flexibility in setting. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram illustrating the configuration of a calculation device which executes a self-correcting technique of a first embodiment. 
         FIG. 2  is a flow diagram illustrating a self-correcting method of the first embodiment. 
         FIG. 3  is a block diagram illustrating the configuration of a calculation system which executes a self-correcting technique of a second embodiment. 
         FIG. 4  is a block diagram illustrating the configuration of a calculation device of  FIG. 3 . 
         FIG. 5  is a block diagram illustrating the configuration of a capability provision device of  FIG. 3 , 
         FIG. 6  is a flow diagram illustrating processing of the calculation device of the second embodiment. 
         FIG. 7  is a flow diagram illustrating processing of the capability provision device of the second embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Embodiments of the present invention will be described below with reference to the accompanying drawings. 
     [First Embodiment] 
     &lt;Configuration&gt; 
     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→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 μ g  and μ h  respectively, X 1  and X 2  are random variables values of which are in the group G, a realization of the random variable X 1  is x 1 , and a realization of the random variable X 2  is x 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. 
     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. 
     &lt;Processing&gt; 
     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 . 
     The control unit  118  sets t=1 (step S 102 ). 
     The first randomizable sampler  121  is capable of calculating f(x) b x 1 . The first randomizable sampler  121  performs calculation by using x and b and sets the calculation result to u (step S 103 ). 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) b x 1  represents to obtain a value of a formula which is defined as f(x) b x 1 . As long as a value of the formula f(x) b x 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. 
     The first power calculation unit  113  calculates u′=u a  (step S 104 ). 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 . 
     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 S 105 ). If pairs (v,v′) are not stored in the second list storage unit  117 , processing of following step S 106  is performed without performing the processing of step S 105 . When there is a pair which satisfies u′=v′, the process goes to step S 112 . When there is not a pair which satisfies u′=v′, the process goes to step S 106 . 
     The second randomizable sampler  122  is capable of calculating f(x) a x 2 . The second randomizable sampler  122  performs calculation by using x and a and sets the calculation result to v (step S 106 ). 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 b  (step S 107 ). 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 . 
     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 S 108 ). When there is a pair which satisfies u′=v′, the process goes to step S 112 . When there is not a pair which satisfies u′=v′, the process goes to step S 110 . 
     The control unit  118  determines whether or not t=T is satisfied (step S 110 ). 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 S 111 ) 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 S 109 ) and the process returns to step S 103 . 
     When it is determined that u′=v′ is satisfied, the final calculation unit  119  calculates d=a′a+b′b (step S 112 ) and calculates (u b′ v a′ ) 1/d  by using u and v which correspond to u′ and v′, and a′, b′, and d so as to output u b′ v a′ ) 1/d  (step S 113 ). That is, the final calculation unit  119  obtains d=a′a+b′b and outputs (u b′ v a′ ) 1/d  for d. The outputted (u b′ v a′ ) 1/d  satisfies (u b′ v a′ ) 1/d =f(x). The reason will be described below. 
     &lt;&lt;Reason Why (u b′ v a′ ) 1/d =f(x) is satisfied&gt;&gt; 
     As disclosed in Patent Literature 1 and Patent Literature 2, if u′=v′ holds, that is, if u a =v b  holds, it is highly probable that the first randomizable sampler has correctly computed u=f(x) b , the second randomizable sampler has correctly computed v=f(x) a , and x 1  and x 2  are identity elements e g  of the group G. When the first randomizable sampler  121  correctly calculates u=f(x) b x 1 , further, the second randomizable sampler  122  correctly calculates v=f(x) a x 2 , and x 1  and x 2  are identity elements e g  of the group G, u b′ v a′ =(f(x) b x 1 ) b′ (f(x) a x 2 ) a′ =(f(x) b e g ) b′ (f(x) a e g ) a′ =f(x) bb′ e g   b′ f(x) aa′ e g   a′ =f(x) (a′a+b′b)  is satisfied. Here, u b′ v a′ =f(x) d  is satisfied when d=a′a+b′b. Therefore, (u b′ v a′ ) 1/d =f(x) is satisfied. 
     &lt;&lt;Specific Examples of u and v&gt;&gt; 
     Examples of u and v include u and v which are disclosed in Patent Literature 1 and Patent Literature 2. For example, u=z 1 ν −r1  and v=z 2 ν −r2  are held. Here, the group H is a cyclic group, a generator of the cyclic group H is μ h , r1 and r2 are random natural numbers which are 0 or larger, ν=f(μ h ) is satisfied, τ 1 =μ h   r1 x b  is satisfied, τ 2 =μ h   r2 x a  is satisfied, further, z 1 =f(τ 1 ) is satisfied with a probability larger than a certain probability, and z 2 =f(τ 2 ) is satisfied with a probability larger than a certain probability. That is, z 1 =f(τ 1 ) may be satisfied or z 1 ≠f(τ 1 ) may be satisfied. Further, z 2 =f(τ 2 ) may be satisfied or z 2 ≠f(τ 2 ) may be satisfied. Namely, z 1  and z 2  are respectively calculation results f(τ 1 ) and f(τ 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. 
     Alternatively, u=z 1 Y −r4 μ g   −r5  and v=z 2 Y −r6 μ g   −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 μ g , x=(c 1 ,c 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, τ 1 (c 2   b W −r4 ,c 1   b V r4 μ g   r5 ) is satisfied, τ 2 =(c 2   a W r6 ,c 1   a V r6 μ g   r7 ) is satisfied, z 1 =f(τ 1 ) is satisfied with a probability larger than a certain probability, and z 2 =f(τ 2 )is satisfied with a probability larger than a certain probability. 
     [Modification of First Embodiment] 
     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 S 101  is unnecessary and v′=ν is obtained. Therefore, the second power calculation unit  116  and step S 107  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 S 101 , and whereby the processing of step S 112  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 S 101 . Alternatively, the integer selection unit  112  may calculate d=a′a+b′b at any time after step S 102  and before step S 113 . In these cases, the processing of step S 112  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 b′ v a′ ) 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 S 101  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. 
     [Second Embodiment] 
     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. 
     &lt;Configuration&gt; 
     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. 
     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. 
     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. 
     &lt;Processing&gt; 
     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 μ g  and μ h  respectively, X 1  and X 2  are random variables values of which are in the group G, a realization of the random variable X 1  is x 1 , and a realization of the random variable X 2  is x 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 . 
     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 S 2101 ). 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 . 
     The control unit  2113  sets t=1 (step S 2102 ). 
     The input information provision unit  2104  generates and outputs first input information τ 1  and second input information τ 2  which respectively correspond to the inputted cipher text x and are elements of the group H (step S 2103 ). Preferably, each of the first input information τ 1  and the second input information τ 2  is information obtained by perturbing a relation with the cipher text x. For example, the first input information τ 1  and the second input information τ 2  respectively correspond to the cipher text x, but it is hard to obtain the cipher text x only from the first input information τ 1  and the second input information τ 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 τ 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 τ 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 τ 1  and τ 2  are same as those illustrated in the first embodiment. 
     As illustrated in  FIG. 7 , the first input information τ 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 τ 2  is inputted into the second output information calculation unit  2202  (step S 2200 ). 
     The first output information calculation unit  2201  correctly calculates f(τ 1 ) with a probability larger than a certain probability by using the first input information τ 1  and the decryption key s stored in the key storage unit  2204  and sets the obtained calculation result to first output information z 1  (step S 2201 ). The second output information calculation unit  2202  correctly calculates f(τ 2 ) with a probability larger than a certain probability by using the second input information τ 2  and the decryption key s stored in the key storage unit  2204  and sets the obtained calculation result to second output information z 2  (step S 2202 ). 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(τ l ), and the result of the computation by the second output information calculation unit  2202  may or may not be f(τ 2 ). 
     The first output information calculation unit  2201  outputs the first output information z 1  and the second output information calculation unit  2202  outputs the second output information z 2  (step S 2203 ). 
     Referring back to  FIG. 6 , the first output information z 1  is inputted into the first calculation unit  2105  of the calculation device  21  ( FIG. 4 ) and the second output information z 2  is inputted into the second calculation unit  2108 . The first output information z 1  and the second output information z 2  correspond to decryption capability which is provided from the capability provision device  22  to the calculation device  21  (step S 2104 ). 
     The first calculation unit  2105  generates a calculation result u=f(x) b x 1  from the first output information z 1 . z 1 =f(τ 1 ) may or may not be satisfied. The first calculation unit  2105  is capable of generating the calculation result u=f(x) b x 1 . A specific example of a method for generating u from z 1  is described in the first embodiment. For example, u=z 1 ν −r1  is satisfied for τ 1 =μ h   r1 x b , u=z 1 Y −r4 μ g   −r5  is satisfied for τ 1 =(c 2   b W r4 ,c 1   b V r4 μ g   r5 ). The calculation result u is transmitted to the first power calculation unit  2106  (step S 2105 ). 
     The first power calculation unit  2106  calculates u′=u 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 S 2106 ). 
     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 S 2107 ). If pairs (v,v′) are not stored in the second list storage unit  2110 , processing of following step S 2108  is performed without performing the processing of step S 2107 . When there is a pair which satisfies u′=v′, the process goes to step S 2114 . When there is not a pair which satisfies the process goes to step S 2108 . 
     In step S 2108 , the second calculation unit  2108  generates a calculation result v=f(x) a x 2  from the second output information z 2 . z 2 =f(τ 2 ) may or may not be satisfied. The second calculation unit  2108  is capable of generating the calculation result v=f(x) a x 2 . A specific example of a method for generating v from z 2  is described in the first embodiment. For example, v=z 2 ν −r2  is satisfied for τ 2 =μ h   r2 x a , and ν=z 2 Y −r6 μ g   −r7  is satisfied for τ 2 =(c 2   a W r6 ,c 1   a V r6 μ g   r7 ). The calculation result v is transmitted to the second power calculation unit  2109  (step S 2108 ). 
     The second power calculation unit  2109  calculates v′=v 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 S 2109 ). 
     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 S 2110 ). When there is a pair which satisfies u′=v′, the process goes to step S 2114 . When there is not a pair which satisfies u′=v′, the process goes to step S 2111 . 
     In step S 2111 , the control unit  2113  determines t=T max  is satisfied (step S 2111 ). T max  is a predetermined natural number. When t=T max  is satisfied, the control unit  2113  outputs information representing that the calculation is impossible, for example, outputs a symbol “⊥” (step S 2113 ) and the processing is ended. When t=T max  is not satisfied, the control unit  2113  increments t by 1, that is, sets as t=t+1 (step S 2112 ) and the process returns to step S 2103 . 
     In step S 2114 , the final output unit  2112  calculates d=a′a+b′b (step S 2114 ) and calculates (u b′ v a′ ) 1/d  by using u and v which correspond to u′ and v′, and a′, b′, and d so as to output (u b′ v a′ ) 1/d  (step S 2115 ). That is, the final output unit  2112  obtains d=a′a+b′b and outputs (u b′ v a′   1/d  for d. The outputted (u b′ v a′ ) 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 S 2115  may be set to a decryption result. 
     [Modification of Second Embodiment] 
     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 S 2101  is unnecessary and v′=v is obtained. Therefore, the second power calculation unit  2109  and step S 2109  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 S 2101 , and whereby the processing of step S 2114  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 S 2101 . Alternatively, the integer selection unit  2102  may calculate d=a′a+b′b at any time after step S 2102  and before step S 2115 . In these cases, the processing of step S 2114  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 b′ v a′ ) 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 S 2101  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. 
     [Other Modifications] 
     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. 
     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 1  and the second output information z 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 1  and the second output information z 2  are outputted, in accordance with the decryption control command. 
     In the second embodiment, the calculation system may further include a decryption control device, G ι  and H ι  may be groups, ω may be an integer which is 2 or larger, ι=1, . . . , ω, f ι (λ ι ) may be a decryption function by which a cipher text λ ι  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 ι , X ι,1  and X ι,2  may be random variables values of which are in the group G ι , x ι,1  may be a realization of the random variable X ι,1 , x ι,2  may be a realization of the random variable X ι,2 , a(ι), b(ι), a′(ι), and b′(ι) may be integers, the group G may be a group G 1 , the group H may be a group H 1 , the cipher text x may be a cipher text λ 1 , the decryption function f(x) may be a decryption function f 1 (λ 1 ), the random variable X 1  may be a random variable X 1,1 , the random variable X 2  may be a random variable X 1,2 , the realization x 1  may be a realization x 1,1 , the realization x 2  may be a realization x 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 τ ι,1  and second input information τ ι,2  which correspond to the cipher text λ ι  and are elements of the group H ι , and the capability provision device correctly calculates f ι (τ ι,1 ) with a probability larger than a certain probability by using the first input information τ ι,1  so as to output the obtained arithmetic result as first output information z ι,1  and the capability provision device correctly calculates f ι (τ ι,2 ) with a probability larger than a certain probability by using the second input information τ ι,2  so as to output the obtained arithmetic result as second output information z ι,2 . The calculation device generates an arithmetic result u ι =f ι (λ ι ) b(ι) x ι,1  based on the first output information z ι,1  and generates an arithmetic result v ι =f ι (λ ι ) a(ι) x ι,2  based on the second output information z ι,2 . When the arithmetic results u ι  and v ι  satisfy u ι   a(ι) =v ι   b(ι) , the calculation device obtains a′(ι)a(ι)+b′(ι)b(ι)=d(ι), for example, so as to output (u ι   b′(ι) v ι   a′(ι) ) 1/d(ι)  for d(ι). 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 ι,1  and the second output information z ι,2  are outputted from the first output information calculation unit and the second output information calculation unit, in accordance with the decryption control command. 
     Further, in this case, the decryption control command may correspond to any decryption function f ι  and the capability provision device may control presence/absence of outputs of both of the first output information z ι,1  and the second output information z ι,2  which correspond to the decryption function ƒ ι  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 λ ι  for respective ι=1, . . . , ω with the decryption key s ι  are obtained, by using (u ι   b′(ι) v ι   a′(ι) ) 1/d(ι)  for respective ι=1, . . . , ω which are outputted from the final output unit. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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. 
     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 
       1 ,  21 : calculation device 
       2 : proxy calculation system