Proxy calculation system, proxy calculation method, proxy calculation requesting apparatus, and proxy calculation program and recording medium therefor

摘要

A function f(x) is calculated with a calculating apparatus that makes a correct calculation with a low probability. Provided that G and H are cyclic groups, f is a function that maps an element x of the group H into the group G, X1 and X2 are random variables whose values are elements of the group G, x1 is a realized value of the random variable X1, and x2 is a realized value of the random variable X2, an integer calculation part calculates integers a′ and b′ that satisfy a relation a′a+b′b=1 using two natural numbers a and b that are relatively prime. A first randomizable sampler is capable of calculating f(x)bx1 and designates the calculation result as u. A first exponentiation part calculates u′=ua. A second randomizable sampler is capable of calculating f(x)ax2 and designates the calculation result as v. A second exponentiation part calculates v′=vb. A determining part determines whether u′=v′ or not. A final calculation part calculates ub′va′ in a case where it is determined that u′=v′.

主权项

1. A proxy calculation system, comprising:
processing circuitry configured to calculate integers a′ and b′ that satisfy a relation a′a+b′b=1 using two natural numbers a and b that are relatively prime; a first randomizable sampler configured to calculate f(x)bx1 and designate the calculation result as u; and a second randomizable sampler configured to calculate f(x)ax2 and designate the calculation result as v, wherein the processing circuitry is further configured to
calculate u′=ua,calculate v′=vb,determine whether or not there are values of u′ and v′ that satisfy u′=v′ after every calculation of u′ and v′ for no more than a predetermined number of iterations of receiving newly calculated values of u and v from the calculating apparatus,calculate ub′va′ in a case where it is determined that u′=v′, anddetermine that calculation of ub′va′ is impossible based on a calculation reliability of an apparatus that includes the first randomizable sampler and the second randomizable sampler being lower than a reference value when there are no values of u′ and v′ that satisfy u′=v′ after the predetermined number of iterations are completed,where G and H are cyclic groups, f is a function that maps an element x of the group H into the group G, X1 and X2 are random variables whose values are elements of the group G, x1 is a realized value of the random variable X1, and x2 is a realized value of the random variable X2.