Proxy computing system, computing apparatus, capability providing apparatus, proxy computing method, capability providing method, program, and recording medium

A method implemented by a capability providing apparatus,

• wherein G and H are groups, f(x) is a decryption function for decrypting a ciphertext x which is an element of the group H with a particular decryption key to obtain an element of the group G, X1 and X2 are random variables having values in the group G, x1 is a realization of the random variable X1, x2 is a realization of the random variable X2, a and b are natural numbers that are relatively prime to each other, the method comprising:
• receiving, from a computing apparatus, first input information τ1 and second input information τ2 that correspond to the ciphertext x and are elements of the group H,
• using the first input information τ1 to correctly compute f(τ1) with a probability greater than a certain probability and set an obtained result of the computation as first output information z1;
• using the second input information τ2 to correctly compute f(τ2) with a probability greater than a certain probability and sets an obtained result of the computation as second output information z2,
• transmitting the first output information z1 and the second output information z2 to the computing apparatus, wherein the computing apparatus includes processing circuitry further configured to implement:
• a first computing unit configured to generate a computation result u=f(x)bx1 from the first output information z1, and generate a computation result u′=ua;
• a second computing unit configured to generate a computation result v=f(x)ax2 from the second output information z2, and generate a computation result v′=vb;
• a determining unit configured to 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;
• and
• a final output unit configured to output ub′va′ for integers a′ and b′ that satisfy a′a+b′b=1 when the computation results u and v satisfy u′=v′ and thus ua=vb,
• wherein the determining unit determines that calculation of ub′va′ is impossible based on a calculation reliability of the capability providing apparatus 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.

A non-transitory computer-readable recording medium storing a program for causing a capability providing apparatus to perform a method, wherein G and H are groups, f(x) is a decryption function for decrypting a ciphertext x which is an element of the group H with a particular decryption key to obtain an element of the group G, X1 and X2 are random variables having values in the group G, x1 is a realization of the random variable X1, x2 is a realization of the random variable X2, a and b are natural numbers that are relatively prime to each other, the method comprising:

• receiving, from a computing apparatus, first input information τ1 and second input information τ2 that correspond to the ciphertext x and are elements of the group H,
• using the first input information τ1 to correctly compute f(τ1) with a probability greater than a certain probability and set an obtained result of the computation as first output information z1;
• using the second input information τ2 to correctly compute f(τ2) with a probability greater than a certain probability and sets an obtained result of the computation as second output information z2,
• transmitting the first output information z1 and the second output information z2 to the computing apparatus, wherein the computing apparatus includes processing circuitry further configured to implement:
• a first computing unit configured to generate a computation result u=f(x)bx1 from the first output information z1, and generate a computation result u′=ua;
• a second computing unit configured to generate a computation result v=f(x)ax2 from the second output information z2, and generate a computation result v′=vb;
• a determining unit configured to 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;
• and
• a final output unit configured to output ub′va′ for integers a′ and b′ that satisfy a′a+b′b=1 when the computation results u and v satisfy u′=v′ and thus ua=vb,
• wherein the determining unit determines that calculation of ub′va′ is impossible based on a calculation reliability of the capability providing apparatus 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.