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

A computing apparatus comprising:

• processing circuitry configured to implement an input information providing unit outputting first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of the set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, Mx2 is a realization of the random variable MX2, and aM is an element of the set HM;
• wherein the processing circuitry is configured to output the first input information Mτ1 and the second input information Mτ2 to a capability providing apparatus, wherein the capability providing apparatus is configured to implement:
• a first output information computing unit using the first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and setting an obtained result of the computation as first output information Mz1;
• and
• a second output information computing unit using the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and setting an obtained result of the computation as second output information Mz2,
• the processing circuitry of the computing apparatus is further configured to implement:
• a first computing unit configured to generate a computation result uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• a second computing unit configured to generate a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• a determining unit configured to determine whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• a final output unit configured to output uM when the computation results uM and vM satisfy uM′=vM,
• wherein the determining unit determines that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A proxy computing method implemented by a proxy computing system including a computing apparatus and a capability providing apparatus, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of a set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, Mx2 is a realization of the random variable MX2, and aM is an element of the set HM, the method comprising:

• by processing circuitry of the computing apparatus, outputting first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM;
• by processing circuitry of the capability providing apparatus:
• using the first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and setting an obtained result of the computation as first output information Mz1;
• and
• using the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and setting an obtained result of the computation as second output information Mz2;
• by the processing circuitry of the computing apparatus:
• generating a computation result uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• generating a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• determining whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• outputting uM when the computation results uM and vM satisfy uM′=vM,
• wherein the method further includes determining, by the computing apparatus, that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A computing method, implemented by a computing apparatus, comprising the steps of:

• generating first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of the set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, Mx2 is a realization of the random variable MX2, and aM is an element of the set HM;
• outputting the first input information Mτ1 and the second input information Mτ2 to a capability providing apparatus, wherein the capability providing apparatus is configured to perform:
• using the first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and setting an obtained result of the computation as first output information Mz1;
• and
• using the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and setting an obtained result of the computation as second output information Mz2,
• the method further including, by the computing apparatus,
• generating a computation result uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• generating a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• determining whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• outputting uM when the computation results uM and vM satisfy uM′=vM,
• wherein the method further includes determining, by the computing apparatus, that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A capability providing apparatus comprising:

• processing circuitry configured to implement a first output information computing unit and a second output information computing unit, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of the set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, Mx2 is a realization of the random variable MX2, and aM is an element of the set HM;
• wherein the processing circuitry receives, from a computing apparatus, first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM,
• the first output information computing unit being configured to use first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and set an obtained result of the computation as first output information Mz1;
• and
• the second output information computing unit being configured to use the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and set an obtained result of the computation as second output information Mz2,
• wherein the processing circuitry transmits the first output information Mz1 and the second output information Mz2 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 uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• a second computing unit configured to generate a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• a determining unit configured to determine whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• a final output unit configured to output uM when the computation results uM and vM satisfy uM′=vM,
• wherein the determining unit determines that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.

A capability providing method, implemented by a capability providing apparatus, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of the set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, MX2 is a realization of the random variable MX2, and aM is an element of the set HM, the method comprising:

• receiving, from a computing apparatus, first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM,
• using first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and set an obtained result of the computation as first output information Mz1;
• using the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and set an obtained result of the computation as second output information Mz2, and
• transmitting the first output information Mz1 and the second output information Mz2 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 uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• a second computing unit configured to generate a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• a determining unit configured to determine whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• a final output unit configured to output uM when the computation results uM and vM satisfy uM′=vM,
• wherein the determining unit determines that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) 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 computing apparatus to perform a method comprising:

• generating first input information Mτ1 and second input information Mτ2 that correspond to the ciphertext xM and are elements of the set HM, wherein GM and HM are sets of matrices, fM(xM) is a decryption function for decrypting a ciphertext xM which is an element of the set HM with a particular decryption key to obtain an element of the set GM, MX1, and MX2 are random variables having values in the set GM, Mx1 is a realization of the random variable MX1, Mx2 is a realization of the random variable MX2, and aM is an element of the set HM;
• outputting the first input information Mτ1 and the second input information Mτ2 to a capability providing apparatus, wherein the capability providing apparatus is configured to perform:
• using the first input information Mτ1 to correctly compute fM(Mτ1) with a probability greater than a certain provability and setting an obtained result of the computation as first output information Mz1;
• and
• using the second input information Mτ2 to correctly compute fM(Mτ2) with a probability greater than a certain provability and setting an obtained result of the computation as second output information Mz2,
• the method further including, by the computing apparatus,
• generating a computation result uM=fM(xM)+Mx1 from the first output information Mz1 and generate a computation result uM′=uM·aM;
• generating a computation result vM=fM(xM)aM+Mx2 from the second output information Mz2;
• determining whether or not there are values of uM′ and vM that satisfy uM′=vM after every calculation of uM′ and vM for no more than a predetermined number of iterations of receiving newly calculated values of uM and vM;
• and
• outputting uM when the computation results uM and vM satisfy uM′=vM,
• wherein the method further includes determining, by the computing apparatus, that calculation of uM is impossible based on a calculation reliability of the capability providing apparatus being lower than a reference value when there are no values of uM′ and vM that satisfy uM′=vM after the predetermined number of iterations are completed, and 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 fM(xM) when the calculation reliability of the capability providing apparatus is verified to be above a predetermined level.