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

A capability providing apparatus comprising:

• processing circuitry configured to implement a first output information computing unit and a second output information computing unit, wherein φ=1, . . . , Φ, Φ is an integer greater than or equal to 2, Gφ and Hφ are groups, fφ is a function that maps an element of the group Hφ to an element of the group Gφ, a(φ) and b(φ) are natural numbers that are relatively prime to each other, a class CLφ(Mφ) corresponding to an element Mφ of the group Hφ is a set whose members are elements fφ(Mφ)a(φ)b(φ) of the group Gφ, Xφ,1 and Xφ,2 are random variables having values in the group Gφ, xφ,1 is a realization of the random variable Xφ,1, and xφ,2 is a realization of the random variable Xφ,2;
• wherein the processing circuitry receives, from a computing apparatus, first input information τφ,1 and second input information τφ,2 that correspond to an element xφ of the group Hφ and are elements of the group Hφ;
• the first output information computing unit being configured to use 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 zφ,1;
• and
• the second output information computing unit being configured to use the second input information τφ,2 to correctly compute fφ(τφ,2) with a probability greater than a certain probability and set an obtained result of the computation as second output information zφ,2,
• wherein the processing circuitry transmits the first output information zφ,1 and the second output information zφ,2 to the computing apparatus, and the computing apparatus includes processing circuitry further configured to implement:
• a first computing unit configured to generate a computation result uφ=fφ(xφ)b(φ)xφ,1 from the first output information zφ,1, and to generate and store a computation result uφ′=uφa(φ);
• a determining unit configured to determine whether or not there is a pair of uφ′ and vφ′ from a previously stored pair (vφ,vφ′), that are in a same class, and when there is not a pair of uφ′ and vφ′ that are in a same class, a second computing unit is configured to generate and store a computation result of new vφ=fφ(xφ)xa(φ)xφ,2 and new vφ′=vφb(φ) from the second output information Zφ,2;
• a final output unit configured to output, when there is a pair of uφ′ and vφ′ determined to be in the same class, a value uφb′(φ)vφa′(φ) for the computation results uφ and vφ where a value uφa(φ) for the computation result uφ and a value vφb(φ) for the computation result vφ belong to a class CLφ(Mφ) corresponding to the same element Mφ and for integers a′(φ) and b′(φ) that satisfy a′(φ)a(φ)+b′(φ)b(φ)=1,
• wherein the determining unit determines that calculation of uφb′(φ)vφa′(φ) 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 are determined to be in the same class after the predetermined number of iterations are completed, such that the capability providing apparatus provides a computing capability to the computing apparatuses, without leaking secret information, and the computing apparatus is configured to utilize the computing capability, via the capability providing apparatus, to obtain a computing result fφ(xφ) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A proxy computing method comprising:

• an input information providing step outputting, on each of a number Φ of computing apparatuses φ, first input information τφ,1 and second input information τφ,2 that correspond to an element xφ of the group Hφ and are elements of the group Hφ;
• a first output information computing step using, on a capability providing apparatus, the first input information τφ,1 to correctly compute fφ(τφ,1) with a probability greater than a certain probability and setting an obtained result of the computation as first output information zφ,1;
• a second output information computing step of using, on the capability providing apparatus, the second input information τφ,2 to correctly compute fφ(τφ,2) with a probability greater than a certain probability and setting an obtained result of the computation as second output information zφ,2;
• a first computing step of generating, on each of the computing apparatuses φ, a computation result uφ=fφ(xφ)b(φ)xφ,1 from the first output information zφ,1, and generating and storing a computation result uφ′=uφa(φ);
• a determining step of determining whether or not there is a pair of uφ′ and vφ′ from a previously stored pair (vφ, vφ′), that are in a same class, and when there is not a pair of uφ′ and vφ′ that are in a same class, performing a second computing step of generating and storing a computation result of new vφ=fφ(xφ)a(φ)xφ,2 and new vφ′=vφb(φ) from the second output information zφ,2;
• and
• a final output step of outputting, when there is a pair of uφ′ and vφ′ determined to be in the same class, on each of the computing apparatuses φ, a value uφb′(φ)vφa′(φ) for the computation results uφ and vφ when a value uφa(φ) for the computation result uφ and a value vφb(φ) for the computation result vφ belong to a class CLφ(Mφ) corresponding to the same element Mφ and for integers a′(φ) and b′(φ) that satisfy a′(φ)a(φ)+b′(φ)b(φ)=1,
• wherein the method includes determining that calculation of uφb′(φ)vφa′(φ) 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 are determined to be in the same class after the predetermined number of iterations are completed, such that the capability providing apparatus provides a computing capability to each of the computing apparatuses, without leaking secret information, and each of the computing apparatuses is configured to utilize the computing capability, via the capability providing apparatus, to obtain a computing result fφ(xφ) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level, and
• wherein φ=1, . . . , Φ, Φ is an integer greater than or equal to 2, Gφ is a group, fφ is a function that maps an element of the group Hφ to an element of the group Gφ, a(φ) and b(φ) are natural numbers that are relatively prime to each other, the class CLφ(Mφ) corresponding to an element Mφ of the group Hφ is a set whose members are elements fφ(Mφ)a(φ)b(φ) of the group Gφ, Xφ,1 and Xφ,2 are random variables having values in the group Gφ, xφ,1 is a realization of the random variable Xφ,1, and xφ,2 is a realization of the random variable Xφ,2.

A capability providing method implemented by a capability providing apparatus, wherein φ=1, . . . , Φ, Φ is an integer greater than or equal to 2, Gφ is a group, fφ is a function that maps an element of the group Hφ to an element of the group Gφ, a(φ) and b(φ) are natural numbers that are relatively prime to each other, the class CLφ(Mφ) corresponding to an element Mφ of the group Hφ is a set whose members are elements fφ(Mφ)a(φ)b(φ) of the group Gφ, Xφ,1 and Xφ,2 are random variables having values in the group Gφ, xφ,1 is a realization of the random variable Xφ,1, and xφ,2 is a realization of the random variable Xφ,2, the method comprising the steps of:

• receiving, from a computing apparatus, first input information τφ,1 and second input information τφ,2 that correspond to an element xφ of the group Hφ and are elements of the group Hφ;
• by a first output information computing unit, using first input information τφ,1 to correctly compute fφ(τφ,1) with a probability greater than a certain probability and setting an obtained result of the computation as first output information zφ,1;
• by a second output information computing unit, using the second input information τφ,2 to correctly compute fφ(τφ,2) with a probability greater than a certain probability and setting an obtained result of the computation as second output information zφ,2;
• transmitting the first output information zφ,1 and the second output information zφ,2 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φ)b(φ)xφ,1 from the first output information zφ,1, and to generate and store a computation result uφ′=uφa(φ);
• a determining unit configured to determine whether or not there is a pair of uφ′ and vφ′ from a previously stored pair (vφ, vφ′), that are in a same class, and when there is not a air of uφ′ and vφ′ that are in a same class, a second computing unit is configured to generate and store a computation result of new vφ=fφ(xφ)a(φ)xφ,2 and new vφ′=vφb(φ) from the second output information zφ,2;
• a final output unit configured to output, when there is a pair of uφ′ and vφ′ determined to be in the same class, a value uφb′(φ)vφa′(φ) for the computation results uφ and vφ where a value uφa(φ) for the computation result uφ and a value vφb(φ) for the computation result vφ belong to a class CLφ(Mφ) corresponding to the same element Mφ and for integers a′(φ) and b′(φ) that satisfy a′(φ)a(φ)+b′(φ)b(φ)=1,
• wherein the determining unit determines that calculation of uφb′(φ)vφa′(φ) 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 are determined to be in the same class after the predetermined number of iterations are completed, such that the capability providing apparatus provides a computing capability to the computing apparatus, without leaking secret information, and the computing apparatus is configured to utilize the computing capability, via the capability providing apparatus, to obtain a computing result fφ(xφ) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A non-transitory computer-readable recording medium storing a program for causing a computer to perform a proxy computing method comprising:

• a receiving step of receiving, on a capability providing apparatus, from a computing apparatus, first input information τφ,1 and second input information τφ,2 that correspond to an element xφ of the group Hφ and are elements of the group Hφ;
• a first output information computing step of using, on the capability providing apparatus, the first input information τφ,1 to correctly compute fφ(τφ,1) with a probability greater than a certain probability and setting an obtained result of the computation as first output information zφ,1;
• a second output information computing step of using, on the capability providing apparatus, the second input information τφ,2 to correctly compute fφ(τφ,2) with a probability greater than a certain probability and setting an obtained result of the computation as second output information zφ,2;
• a transmitting step of transmitting, on the capability providing apparatus, the first output information zφ,1 and the second output information zφ,2 to the computing apparatus, and the computing apparatus includes processing circuitry further configured to implement:
• a first computing unit configured to generate a computation result uφ=fφ(xφ)b(φ)xφ,1 from the first output information zφ,1, and to generate and store a computation result uφ′=uφa(φ);
• a determining unit configured to determine whether or not there is a pair of uφ′ and vφ′ from a previously stored pair (vφ, vφ′), that are in a same class, and when there is not a pair of uφ′ and vφ′ that are in a same class, a second computing unit is configured to generate and store a computation result of new vφ=fφ(xφ)a(φ)xφ,2 and new vφ′=vφb(φ) from the second output information zφ,2;
• a final output unit configured to output, when there is a pair of uφ′ and vφ′ determined to be in the same class, a value uφb′(φ)vφa′(φ) for the computation results uφ and vφ where a value uφa(φ) for the computation result uφ and a value vφb(φ) for the computation result vφ belong to a class CLφ(Mφ) corresponding to the same element Mφ and for integers a′(φ) and b′(φ) that satisfy a′(φ)a(φ)+b′(φ)b(φ)=1,
• wherein the determining unit determines that calculation of uφb′(φ)vφa′(φ) 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 are determined to be in the same class after the predetermined number of iterations are completed, such that the capability providing apparatus provides a computing capability to the computing apparatus, without leaking secret information, and the computing apparatus is configured to utilize the computing capability, via the capability providing apparatus, to obtain a computing result fφ(xφ) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.