SECRET CHARACTER STRING CALCULATION SYSTEM, METHOD AND APPARATUS, AND NON-TRANSITORY RECORDING MEDIUM

• US 20180048625A1
• Filed: 03/18/2016
• Published: 02/15/2018
• Est. Priority Date: 03/19/2015
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: TERANISHI, Isamu
• Granted Patent: US 10,511,577 B2
• Time in Patent Office: Days
• CPC Class Codes: G09C 1/10 the connections being electrical
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068

Abstract

A registration apparatus generates shares by secret sharing of a character string with a plurality of modulus and sends the shares to a plurality of server apparatuses to be stored therein. A retrieval apparatus sends 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 execute a subroutine for shares of the each registration character string stored in a storage unit and for each of the plurality of modulus, reconstruct an execution result, and determine whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result. A retrieval apparatus reconstructs shares returned from the plurality of server apparatuses and obtains a retrieval result in which the retrieval character string hits, from the reconstructed result by the Chinese remainder theorem.

Claims

1. A secret character string calculation system comprising:

a registration apparatus;

a retrieval apparatus; and

a plurality of server apparatuses,

wherein the registration apparatus comprises

a registration character string share generation unit configured to generate shares by secret sharing of a registration character string, with a plurality of modulus, wherein the registration apparatus sends the shares generated by the registration character string share generation unit to the plurality of server apparatuses, respectively,

wherein the plurality of server apparatuses respectively store the received shares in storage units thereof,

wherein the retrieval apparatus further comprises

a retrieval character string share generation unit configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus, wherein the retrieval apparatus sends the shares generated by the retrieval character string share generation unit to the plurality of server apparatuses, respectively,

wherein the plurality of server apparatuses each comprise

a retrieval response calculation unit configured to execute 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, reconstruct the execution result of the operation processing, and determine, based on the 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, and

wherein the retrieval apparatus further comprises

a reconstruction unit 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.

2. The secret character string calculation system according to claim 1, wherein the registration character string is a=a[1]∥

. . . ∥

a[n], and the retrieval character string is b=b[1]∥

. . . ∥

b[m] (where i is a concatenation operator, m and n are respective number of words of b and a such that m<

n), wherein

the retrieval response calculation unit of the server apparatus, as the predetermined operation processing,

executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , n−

m) and for each k (k=1, . . . , m),

sums, for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each j (j=1, . . . , n−

m)

executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , n−

m),

subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

3. The secret character string calculation system according to claim 2, wherein, in the retrieval response calculation unit,

the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

4. 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 the execution result of the operation processing, and determine, based on the 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, the retrieval result from the reconstructed result.

5. The method according to claim 4, wherein the registration character string is a=a[1]∥

. . . ∥

a[n], the retrieval character string is b=b[1]∥

. . . ∥

b[m] (∥

is a concatenation operator, m and n are respective number of words of b and a such that m<

n), wherein

the subroutine called by the server apparatus for each j (j=1, . . . , n−

m) and for each k (k=1, . . . , m),

executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string for each j and each k,

sums for k=1 to m, the shares calculated by the first multiparty computation protocol for each j,

executes a second multiparty computation protocol to calculate shares of a value to be 0 or 1 depending on whether or not the summed share is 0, for each j (j=1, . . . , n−

m),

subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

6. The method according to claim 5, wherein in the subroutine, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

7. A server apparatus comprising:

a communication unit 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;

a storage unit configured to store the received share of the registration character string; and

a retrieval response calculation unit 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 the execution result and determine, based on the 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 communication unit 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, wherein

the communication unit 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.

8. The server apparatus according to claim 7, wherein the registration character string is a=a[1]∥

. . . ∥

a[n], the retrieval character string is b=b[1]∥

. . . ∥

b[m] (where ∥

is a concatenation operator, m and n are respective number of words of b and a such that m<

n), wherein

the retrieval response calculation unit, as the predetermined operation processing,

executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , n−

m) and for each k (k=1, . . . , m),

sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j,

executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0,

subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

9. The server apparatus according to claim 8,

wherein, in the retrieval response calculation unit, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

10. A non-transitory computer-readable recording medium storing therein a program causing a computer constituting a 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;

performing a retrieval response calculation including executing a predetermined operation processing for the share of the each registration character string stored in the storage unit and for each of the plurality of modulus, reconstructing the execution result of the operation processing, and determining, based on the 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; and

sending the shares of the retrieval result to the retrieval apparatus.

12. The non-transitory computer-readable recording medium according to claim 10, wherein the registration character string is a=a[1]∥

. . . ∥

a[n], the retrieval character string is b=b[1]∥

. . . ∥

b[m] (where ∥

is a concatenation operator, m and n are respective number of words of b and a such that m<

n), wherein

the retrieval response calculation processing, as the predetermined operation processing,

executes a first multiparty computation protocol to calculate shares of a value which is 1 or 0 depending on whether or not the share of the (j+k)th word of the registration character string matches the kth word of the retrieval character string, for each j (j=1, . . . , n−

m) and for each k (k=1, . . . , m),

sums for k=1 to m, the shares calculated by the first multiparty computation protocol with the modulus, for each the j,

executes a second multiparty computation protocol to calculate shares of a value which is 0 or 1 depending on whether or not the summed share is 0,

subtracts the number of words of the retrieval character string and a sum of the shares calculated by the second multiparty computation protocol from the number of words of the registration character string with the modulus, and

outputs a result obtained by multiplying the subtracted value by a share obtained by a random number generating multiparty computation protocol with the modulus.

13. The non-transitory computer-readable recording medium according to claim 12, wherein in the retrieval response calculation processing, the first multiparty computation protocol executes a multiparty computation protocol that the kth word of the retrieval character string subtracted from the share of the (j+k)th word of the registration character string with the modulus is modular exponentiated by the Carmichael function value of the modulus, and

the second multiparty computation protocol executes a multiparty computation protocol to modular-exponentiate the sum of shares by a Carmichael function value of the modulus.

11. A retrieval apparatus comprising:

a communication unit 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; and

a retrieval character string share generation configured to generate shares by secret sharing of a retrieval character string with the plurality of modulus,

wherein the communication unit sends the shares generated by the retrieval character string share generation unit 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 the execution result of the operation processing, and

determines, based on the 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 retrieval apparatus further comprises

a reconstruction unit 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.