US-12621160-B2 - Secure computation system, secure computation server apparatus, secure computation method, and secure computation program

US12621160B2US 12621160 B2US12621160 B2US 12621160B2US-12621160-B2

Abstract

A secure computation server apparatus in a secure computation system includes: a table storage part that stores a table of secret shares of the product of a first value and a second value for combinations of shares of possible values of the first value and shares of possible values of the second value; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

Inventors

Hikaru TSUCHIDA

Assignees

NEC CORPORATION

Dates

Publication Date: 20260505
Application Date: 20210210

Claims (16)

1 . A secure computation system, comprising a plurality of secure computation server apparatuses connected to each other via a network and performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein each of the secure computation server apparatuses includes: a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value, wherein the secret sharing is achieved by using an (N−3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.
2 . The secure computation system according to claim 1 , wherein the comparative verification part accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.
3 . The secure computation system according to claim 1 , wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.
4 . The secure computation system according to claim 1 , wherein the shuffling is a composition of N C t sequences of the mini-shuffles with N C t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.
5 . The secure computation system according to claim 1 , wherein the comparative verification part verifies that the received value is a correct value by verifying that hash values of the plurality of received data are identical.
6 . A secure computation server apparatus out of a plurality of secure computation server apparatuses connected to each other via a network to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation server apparatus including: a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value, wherein the secret sharing is achieved by using an (N−3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.
7 . A secure computation method, with a plurality of secure computation server apparatuses connected to each other via a network, performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein each of the secure computation server apparatuses: stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value, wherein the secret sharing is achieved by using an (N−3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which permutation of shares fort apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses; shuffles indices of possible values of the first value and indices of possible values of the second value in the table; selects an element in the table whose indices in the shuffled table match the first and the second values; and accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.
8 . A non-transient computer readable medium storing a secure computation program causing a plurality of secure computation server apparatuses connected to each other via a network to execute processing to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation program: stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value, wherein the secret sharing is achieved by using an (N−3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which permutation of shares fort apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses; shuffles indices of possible values of the first value and indices of possible values of the second value in the table; selects an element in the table whose indices in the shuffled table match the first and the second values; and accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.
9 . The secure computation server apparatus according to claim 6 , wherein the comparative verification part accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.
10 . The secure computation server apparatus according to claim 6 , wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.
11 . The secure computation server apparatus according to claim 6 , wherein the shuffling is a composition of N C t sequences of the mini-shuffles with N C t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.
12 . The secure computation method according to claim 7 , wherein each of the secure computation server apparatuses accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.
13 . The secure computation server method according to claim 7 , wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.
14 . The secure computation server method according to claim 7 , wherein the shuffling is a composition of N C t sequences of the mini-shuffles with N C t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.
15 . The non-transient computer readable medium storing the secure computation program according to claim 8 , wherein the secure computation program accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.
16 . The non-transient computer readable medium storing the secure computation program according to claim 8 , wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

Description

This application is a National Stage Entry of PCT/JP2021/004893 filed on Feb. 10, 2021, the contents of all of which are incorporated herein by reference, in their entirety. FIELD The present invention relates to a secure computation system, secure computation server apparatus, secure computation method, and secure computation program. BACKGROUND In recent years, the research and developments of a technology called secure computation are active. Secure computation is a technique that executes a predetermined process while keeping the computation process and the results thereof secret from a third party. Multi-party computation is one of the representative techniques of secure computation. In multi-party computation, confidential data is distributed to a plurality of servers (secure computation server apparatuses), and arbitrary computations are executed on the data while secrecy is maintained. Further, the data distributed to each secure computation server apparatus is called a “share.” Hereinafter, the term “secure computation” as used herein refers to multi-party computation, unless otherwise specified. Even among the techniques generally called secure computations, there are different levels of security achieved. For instance, let's assume that an adversary is among the participants of a multi-party group that performs secure computation. In this case, between a secure computation technique that can detect the presence of the adversary and interrupt the process, and one that can obtain the correct computation results without interrupting the process despite the presence of the adversary, the latter is more secure than the former. Further, secure computation that satisfies the security of the latter is called Guaranteed Output Delivery (GOD), and an example of secure computation that achieves this is known (for instance, refer to Non-Patent Literature 1). Non-Patent Literature 1 Byali, M., Chaudhari, H., Patra, A., & Suresh, A., “FLASH: Fast and Robust Framework for Privacy-preserving Machine Learning,” Proceedings on Privacy Enhancing Technologies, 2020 (2): 459-480. SUMMARY The disclosure of each literature in Citation List above is incorporated herein in its entirety by reference thereto. The following analysis is given by the present inventor. In evaluating the security of secure computation, not only the achievable security effects but also premises are important. A typical premise is provided by the random oracle model or random oracle hypothesis for a hash function. A hash function returns a unique output for an input, but is configured so that it is difficult to infer the input from the output. Here, being difficult to do so does not guarantee that it is absolutely impossible. Therefore, security is evaluated on the premise that the hash function used has no vulnerability. The security provided by this premise is described as “being secure in the random oracle model” or “being secure under the random oracle hypothesis.” The secure computation described in Non-Patent Literature 1 is “secure in the random oracle model.” Meanwhile, the opposite of “being secure in the random oracle model” is “being secure in the standard model.” In other words, even if the input can be inferred from the output of a hash function, this itself does not become a vulnerability of the secure computation scheme. It goes without saying that, with the same level of achievable security, being secure in the standard model is able to achieve a higher level of security than being secure in the random oracle model. Further, the number of participants in the secure computation described in Non-Patent Literature 1 is limited to four, and this further limits applicable scenarios. Therefore, flexibility in terms of the number of participants is also desired. In view of the problem above, it is an object of the present invention to provide a secure computation system, secure computation server apparatus, secure computation method, and secure computation program that contribute to improving security and flexibility. According to a first aspect of the present invention, there is provided a secure computation system comprising a plurality of secure computation server apparatuses connected to each other via a network and performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein each of the secure computation server apparatuses includes a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match