Secret character string calculation system, method and apparatus, and non-transitory recording medium

A method for performing a secret character string calculation by a computer system including a plurality of server apparatuses, the method comprising:

• generating shares by secret sharing of a registration character string with a plurality of modulus and sending the shares to the plurality of server apparatuses, respectively, to have the shares stored in the plurality of server apparatuses;
• sending shares generated by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses;
• the plurality of server apparatuses each calling a subroutine for the stored shares of each registration character string and for each of the plurality of modulus, to execute an operation processing, reconstruct an execution result of the operation processing, and determine, based on a reconstruction result of the execution result, whether or not to return the stored shares of the registration character string as a retrieval result;
• and
• reconstructing the shares returned from the plurality of server apparatuses, and reconstructing, using the Chinese remainder theorem, a retrieval result from the reconstructed result of the shares.

A server apparatus comprising:

• a processor;
• a memory coupled to the processor and storing program instructions executable by the processor;
• a transceiver configured to receive shares sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus, to a plurality of server apparatuses;
• and
• a storage unit configured to store the received shares of the registration character string,
• wherein the processor is configured to execute a predetermined operation processing for the shares of each character string stored in the storage unit and for each of the plurality of modulus, reconstruct an execution result, and determine, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result, when the transceiver receives shares from a retrieval apparatus that sends the shares by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses, and
• wherein the transceiver sends the shares of the retrieval result to the retrieval apparatus that is operable to reconstruct, using the Chinese remainder theorem, a retrieval result from a reconstructed result of the shares returned from each of the server apparatuses.

A non-transitory computer-readable recording medium having stored thereon a program that, upon execution by a computer constituting a server apparatus, causes the server apparatus to execute processing comprising:

• receiving shares, and storing the shares in a storage unit, the shares being sent from a registration apparatus that generates the shares by secret sharing of a registration character string with a plurality of modulus and sends the shares to a plurality of server apparatuses;
• and
• performing a retrieval response calculation including executing a predetermined operation processing for the shares of the registration character string stored in the storage unit and for each of the plurality of modulus, reconstructing an execution result of the operation processing, and determining, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result,
• wherein the shares of the retrieval result, determined by said determining to be returned, are sent to a retrieval apparatus that is operable to reconstruct, using the Chinese remainder theorem, a retrieval result from a reconstructed result of the shares returned from each of the server apparatuses.

A retrieval apparatus comprising:

• a processor;
• a memory coupled to the processor and storing program instructions executable by the processor;
• and
• a transceiver configured to communicatively connect to a plurality of server apparatuses that receive from a registration apparatus that generates shares by secret sharing of a registration character string with a plurality of modulus,
• wherein the processor is configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus, and
• the transceiver sends the shares generated to the plurality of server apparatuses, respectively,
• wherein the plurality of server apparatuses each executes a predetermined operation processing for the shares of each character string stored in the each storage unit and for each of the plurality of modulus,
• reconstructs an execution result of the operation processing, and
• determines, based on a reconstruction result of the execution result, whether or not to return the shares of the registration character string stored in the storage unit, as a retrieval result,
• wherein the processor is further configured to reconstruct shares returned from the plurality of server apparatuses, and reconstruct, using the Chinese remainder theorem, a retrieval result from the reconstructed result of the shares.