Granted Patent B2

US 12,335,376 · App. 18/035,867 · Granted Jun 17, 2025

Inventors: Hikaru Tsuchida (Tokyo, JP); Takashi Nishide (Ibaraki, JP)

Assignees: NEC CORPORATION; UNIVERSITY OF TSUKUBA

H04L9/085G06F21/57

Abstract

Claims (54)

1. A secure computation system comprising at least three secure computation server apparatuses connected to each other via a network and referring to shares of an array element corresponding to an index in an array of shares for an input of shares representing the index, wherein

each of the secure computation server apparatuses comprises:

a memory storing instructions;

a processor, which based on executing the instructions, is configured to:

compute discriminant shares configured so that the index relating to the input corresponds to a specific value from the shares representing the index relating to the input and possible combinations of index shares of the array;

configure a combination of shares of an element in the array and the discriminant shares for all possible combinations of indices of the array;

shuffle the combinations;

reconstruct the discriminant shares in the shuffled combinations; and

select shares of an element in the array in the combinations where the reconstructed value is the specific value.

2. The secure computation system according to claim 1 , wherein the processor is further configured to compute the discriminant shares after converting the shares representing the index relating to the input and possible index shares into binary shares.

3. The secure computation system according to claim 2 , wherein the processor is further configured to compute the discriminant shares using exclusive OR on the shares representing the index relating to the input and possible index shares, which have been converted into binary shares.

4. The secure computation system according to claim 2 comprising N secure computation server apparatuses and performing secure computation using a (t+1, N)-additive secret sharing scheme.

5. The secure computation system according to claim 1 , wherein the processor is further configured to compute the discriminant shares using the arithmetic difference between the shares representing the index relating to the input and possible index shares.

6. The secure computation system according to claim 5 , wherein the processor is further configured to compute the discriminant shares by multiplying the arithmetic difference by a non-zero random number.

7. The secure computation system according to claim 5 comprising N secure computation server apparatuses and performing secure computation using a (t+1, N)-Shamir's secret sharing scheme.

8. A secure computation server apparatus out of at least three secure computation server apparatuses connected to each other via a network in order to refer to shares of an array element corresponding to an index in an array of shares for an input of shares representing the index, the secure computation server apparatus including:

a memory storing instructions; and

a processor, which based on executing the instruction, is configured to:

compute discriminant shares configured so that the index relating to the input corresponds to a specific value from the shares representing the index relating to the input and possible combinations of index shares of the array;

configure a combination of shares of an element in the array and the discriminant shares for all possible combinations of indices of the array;

shuffle the combinations;

reconstruct the discriminant shares in the shuffled combinations; and

select shares of an element in the array in the combinations where the reconstructed value is the specific value.

9. The secure computation server apparatus according to claim 8 , wherein the processor is further configured to compute the discriminant shares after converting the shares representing the index relating to the input and possible index shares into binary shares.

10. The secure computation server apparatus according to claim 9 , wherein the processor is further configured to compute the discriminant shares using exclusive OR on the shares representing the index relating to the input and possible index shares, which have been converted into binary shares.

11. The secure computation server apparatus according to claim 9 , wherein the secure computation server apparatus is one of N secure computation server apparatuses and performs secure computation using a (t+1, N)-additive secret sharing scheme.

12. The secure computation server apparatus according to claim 8 , wherein the processor is further configured to compute the discriminant shares using the arithmetic difference between the shares representing the index relating to the input and possible index shares.

13. The secure computation server apparatus according to claim 12 , wherein the processor is further configured to compute the discriminant shares by multiplying the arithmetic difference by a non-zero random number.

14. The secure computation server apparatus according to claim 12 , wherein the secure computation server apparatus is one of N secure computation server apparatuses and performs secure computation using a (t+1, N)-Shamir's secret sharing scheme.

15. A secure computation method comprising at least three secure computation server apparatuses connected to each other via a network and referring to shares of an array element corresponding to an index in an array of shares for an input of shares representing the index, wherein

each of the secure computation server apparatuses performs:

computing discriminant shares configured so that the index relating to the input corresponds to a specific value from the shares representing the index relating to the input and possible combinations of index shares of the array;

configuring a combination of shares of an element in the array and the discriminant shares for all possible combinations of indices of the array;

shuffling the combinations;

reconstructing the discriminant shares in the shuffled combinations; and

selecting shares of an element in the array in the combinations where the reconstructed value is the specific value.

16. The secure computation method according to claim 15 , wherein

each of the secure computation server apparatuses performs:

computing the discriminant shares after converting the shares representing the index relating to the input and possible index shares into binary shares.

17. The secure computation method according to claim 16 , wherein

each of the secure computation server apparatuses performs:

computing the discriminant shares using exclusive OR on the shares representing the index relating to the input and possible index shares, which have been converted into binary shares.

18. The secure computation method according to claim 15 , wherein

each of the secure computation server apparatuses performs:

computing the discriminant shares using the arithmetic difference between the shares representing the index relating to the input and possible index shares.

19. The secure computation method according to claim 18 , wherein

each of the secure computation server apparatuses performs:

computing the discriminant shares by multiplying the arithmetic difference by a non-zero random number.

20. A non-transient computer readable medium storing a secure computation program causing at least three secure computation server apparatuses connected to each other via a network to refer to shares of an array element corresponding to an index in an array of shares for an input of shares representing the index, the secure computation program including processes of:

computing discriminant shares configured so that the index relating to the input corresponds to a specific value from the shares representing the index relating to the input and possible combinations of index shares of the array;

configuring a combination of shares of an element in the array and the discriminant shares for all possible combinations of indices of the array;

shuffling the combinations;

reconstructing the discriminant shares in the shuffled combinations; and

selecting shares of an element in the array in the combinations where the reconstructed value is the specific value.

Assignments (1)

Continuity (1)

References Cited (20)