Secure computation system, secure computation apparatus, secure computation method, and program

1. A secure computation system for efficient rotation by secure computation, the secure computation system comprising:

n secure computation apparatuses PA(0), . . . , PA(n−1), wherein

n and k are integers of 2 or more; n>k; N= n C k ; PA is a set of the n secure computation apparatuses PA(0), . . . , PA(n−1); SP(i) is a set of k secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)) selected from PA; i=0, . . . , N−1; SP(0), . . . , SP(N−1) hold |SP(i′)∩/SP(i+1) c |=1 for i′=0, . . . , N−2;

P is an integer of 1 or more; p is the number of bits of the integer P; a is an element of a residue class ring Z P modulo P; share <a> (SP(i)) is k shares, according to additive secret sharing scheme, held by the set SP(i); share <a> (SP(0)) is a share obtained by secret sharing of a according to additive secret sharing scheme; <a> (PA(θ)∈SP(i)) is a share held by the secure computation apparatus PA(θ) ∈ SP(i) of the share <a> (SP(i) ;

ρ is an element of a residue class ring Z p modulo p; sub-shares of n shares <<ρ>>0, . . . , <<ρ>>n−1 obtained by the secret sharing of p according to a replicated secret sharing scheme are ρ 0 , . . . , ρ N−1 ∈ Z p , ρ (SP(i)) is a sub-share corresponding to the set SP(i) among the sub-shares ρ 0 , . . . , ρ N−1 ;

PA(φ(i′, 0)) is a secure computation apparatus, which is included in the set SP(i′) but not included in the set SP(i′+1); PA(φ(i′+1, k)) is a secure computation apparatus, which is not included in the set SP(i′) but included in the set SP(i′+1); PA(φ(i′, j)) for j=1, . . . , k−1 is a secure computation apparatus, which is included in both the set SP(i′) and the set SP(i+1);

secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)) include processing circuitry configured to execute efficient unit rotation calculating 2 ρ(SP(i)) <a> (SP(i)) ∈ Z p to obtain a new share <a> (SP(i)) ; and

the secure computation apparatus PA(φ(i′, 0)) includes processing circuitry configured to obtain a share <a> (PA(k)∈SP(i′+1)) using a share <a> (PA(0)∈SP(i′)) and random numbers r(i′, 1), . . . , r(i′, k−1)), the random numbers r(i′, 1), . . . , r(i′, k−1)) being shared by the secure computation apparatus PA(φ(i′, 0)) and the secure computation apparatuses PA(φ(i′, 1)) . . . , PA(φ(i′,k−1)), and then transmit the share <a> (PA(k)∈SP(i′+I)) to the secure computation apparatus PA(φ(i′+1, k) via a network, each of the secure computation apparatuses PA(φ(i′, j)) includes processing circuitry configured to perform redistribution to obtain a share <a> (PA(j)∈SP(i′+1)) using a share <a> (PA(j)∈SP(i′)) and the random number r(i′, j) for j=1, . . . , k−1.

2. The secure computation system according to claim 1 , wherein in the redistribution,

the secure computation apparatus PA(φ(i′, 0)) obtains the share <a> (PA(k)∈SP(i′+1)) according to the following equation

〈

a

〉

(

PA

⁡

(

k

)

∈

SP

⁡

(

i

′

+

1

)

)

=

〈

a

〉

(

PA

⁡

(

0

)

∈

SP

⁡

(

i

′

)

)

-

∑

1

≤

j

<

k

r

⁡

(

i

′

,

j

)

;

and

the each secure computation apparatus PA(φ(i′, j)) obtains the share <a> (PA(j)∈SP (i′+1)) by the following equation

< a> PA(j)∈SP(i′+1)) =<a> (PA(j)∈SP(i′)) +r ( i′,j ).

3. The secure computation system according to claim 1 , wherein

SP(0), . . . , SP(N−1) are different from each other; and

the set SP(i) executes the redistribution for i=0 to i=N−2, respectively followed by the unit rotation, and the set SP(i) executes the unit rotation for i=N−1.

4. The secure computation system according to claim 1 , wherein

k=2, n=3, N=3, i=0, 1, 2,

SP(0)=(PA(0), PA(1)), SP(1)=(PA(1), PA(2)), SP(2)=(PA(0), PA(2)),

share< a >( SP (0)) is a 0 and a 1 ,a=a 0 +a 1 ∈Z p ,

ρ=ρ 01 +ρ 12 +ρ 20 ∈Z p ,ρ( SP (0)=( SP (1)=( SP (1)=ρ 01 ,β 12 ,ρ 20 ,

PA(φ(0, 0))=PA(0), PA(φ(1, 2))=PA(2), PA((0, 1))=PA(1),

PA(φ(1, 0))=PA(1), PA(φ(2, 2))=PA(0), PA(φ(1, 1))=PA(2),

r(0, 1)=r 01 , r(1, 1)=r 12 ,

a secure computation apparatus PA(0) obtains

B 0 =2 ρ01 a 0 −r 01

by using ρ 01 , a 0 , r 01 and transmits B 0 to the secure computation apparatus PA(2),

a secure computation apparatus PA(1) obtains

B 1 =2 ρ12 (2 ρ01 a 1 +r 01 )− r 12

by using ρ 01 , ρ 12 , a 1 , r 01 , r 12 and transmits Bi to the secure computation apparatus PA(0),

the secure computation apparatus PA(0) obtains

2 ρ20 B 1

by using ρ 20 and B 1 ,

the secure computation apparatus PA(2) obtains

2 ρ20 (2 ρ12 B 0 +r 12 )

by using ρ 20 , ρ 12 , B 0 , and r 12 .

5. The secure computation system according to claim 1 , wherein

k=3, n=5, N=10, i=0, 1, . . . , 9,

SP(0)=(PA(0), PA(1), PA(2)), SP(1)=(PA(1), PA(2), PA(3)), SP(2)=(PA(2), PA(3), PA(4)), SP(3)=(PA(0), PA(3), PA(4)), SP(4)=(PA(0), PA(1), PA(4)), SP(5)=(PA(1), PA(3), PA(4)), SP(6)=(PA(0), PA(1), PA(3)), SP(7)=(PA(0), PA(2), PA(3)), SP(8)=(PA(0), PA(2), PA(4)), SP(9)=(PA(1), PA(2), PA(4)).

6. A secure computation system for efficient rotation by secure computation, the secure computation system comprising:

n secure computation apparatuses PA(0), . . . , PA(n−1), wherein

N and k are integers of 2 or more; n >k; N= n C k ; PA is a set of the n secure computation apparatuses PA(0), . . . , PA(n−1); SP(i) is a set of k secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)) selected from PA; i=0, . . . , N−1, i′=0, . . . , N−2;

P is an integer of 1 or more; p is the number of bits of the integer P; a is an element of a residue class ring Z P modulo P; share <a>( SP(i) is k shares, according to additive secret sharing scheme, held by the set SP(i); share <a> (SP(0)) is a share obtained by secret sharing of a according to additive secret sharing scheme; <a> (PA(θ)∈SP(i) is a share held by the secure computation apparatus PA(θ)∈SP(i) of the share <a> (SP(1) ;

ρ is an element of a residue class ring Z p modulo p; sub-shares of n shares <<ρ>>0, . . . , <<ρ>> n−1 obtained by the secret sharing of p according to a replicated secret sharing scheme are ρ 0 , . . . , β N−1 ∈ Z p ; ρ(SP(i)) is a sub-share corresponding to the set SP(i) among the sub-shares ρ 0 , . . . , β N−1 ,

secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)) include processing circuitry configured to execute efficient unit rotation calculating 2 ρ(SP(i)) <a> (SP(i)) ∈Z p to obtain a new share <a> (SP(i)) ;

the secure computation apparatus PA(φ(i′, 0)) includes processing circuitry configured to obtain a share <a> (PA(k)∈SP(+1)) using a share <a> (PA(0)∈SP(i′)) , and then transmit the share <a> (PA(K)∈SP(i+1)) to the secure computation apparatus PA(φ(i′+1, k)) via a network, each of the secure computation apparatuses PA(φ(i′, j)) includes processing circuitry configured to perform redistribution to obtain a share <a> (PA(j)∈SP(i+1)) using a share <a> (PA)j)∈SP(i′)) for j=1, . . . , k−1.

7. A secure computation apparatus of the secure computation system according to claim 1 .

8. A secure computation method for efficient rotation by secure computation by n secure computation apparatuses PA(0), . . . , PA(n−1), wherein

n and k are integers of 2 or more; n >k; N= n C k ; PA is a set of the n secure computation apparatuses PA(0), . . . , PA(n−1); SP(i) is a set of k secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1) selected from PA; i=0, . . . , N−1; SP(0), . . . , SP(N−1) hold |SP(i′) n SP(i′+1) c |=1 for i′=0, . . . , N−2;

P is an integer of 1 or more; p is the number of bits of the integer P; a is an element of a residue class ring Z p modulo P; share <a> (SP(i)) is k shares, according to additive secret sharing scheme, held by the set SP(i); share <a> (SP(i)) is a share obtained by secret sharing of a according to additive secret sharing scheme; <a> (PA(θ)∈SP(i)) is a share held by the secure computation apparatus PA(θ) ∈SP(i) of the share <a> (SP(i) ;

ρ is an element of a residue class ring Z p modulo p; sub-shares of n shares <<ρ>> 0 , . . . <<ρ>> n−1 obtained by the secret sharing of p according to a replicated secret sharing scheme are ρ 0 , . . . , β N−1 ∈Z p ; ρ (SP(i)) is a sub-share corresponding to the set SP(i) among the sub-shares ρ 0 , . . . , β N−1 ;

PA(φ(i′, 0)) is a secure computation apparatus, which is included in the set SP(i′) but not included in the set SP(i′+1); PA(φ(i′+1, k)) is a secure computation apparatus, which is not included in the set SP(i′) but included in the set SP(i′+1); PA(φ(i′, j)) for j=1, . . . , k−1 is a secure computation apparatus, which is included in both the set SP(i′) and the set SP(i′+1);

the secure computation method comprises:

efficient rotating by calculating 2 ρ(SP(i)) <a> (SP(i)) ∈Z p to obtain a new share <a> (SP(i)) by secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)); and

obtaining a share <a> (PA(K)∈SP(1+1) using a share <a> (PA(0)∈SP (i′)) and random numbers r(i′, 1), . . . , r(i′, k−1)) by the secure computation apparatus PA(φ(i′, 0)), the random numbers r(i′, 1), . . . , r(i′, k−1) being shared by the secure computation apparatus PA(φ(i′, 0)) and the secure computation apparatuses PA(φ(i′, 1)) . . . , PA(φ(i′,k−1)), then transmitting the share <a> (PA(k)∈SP(1′+1)) to the secure computation apparatus PA(φ(i′+1, k)) via a network, and obtaining a share <a> (PA(j)∈SP(i′+1)) using a share <a> (PA(j)∈SP(i′)) and the random number r(i′, j) by each of the secure computation apparatuses PA(φ(i′, j)) for j=1, . . . , k−1.

9. A secure computation method by a secure computation system for efficient rotation by secure computation, the secure computation system including n secure computation apparatuses PA(0), . . . , PA(n−1), wherein

n and k are integers of 2 or more; n >k; N= n C k ; PA is a set of the n secure computation apparatuses PA(0), . . . , PA(n−1);SP(i) is a set of k secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)) selected from PA; i=0, . . . , N−1; i′=0, . . . , N−2;

P is an integer of 1 or more; p is the number of bits of the integer P; a is an element of a residue class ring Z p modulo P; share <a> (SP(i)) is k shares, according to additive secret sharing scheme, held by the set SP(i); share <a> (SP(0)) is a share obtained by secret sharing of a according to additive secret sharing scheme; <a> (PA(θ)∈SP(i)) is a share held by the secure computation apparatus PA(θ)∈SP(i) of the share <a> (SP(i) ;

ρ is an element of a residue class ring Z p modulo p,

sub-shares of n shares <<ρ>>0, . . . , <<p>> n−1 obtained by the secret sharing of ρ according to a replicated secret sharing scheme are ρ 0 , . . . , β N−1 ∈Z p ;

ρ (SP(i)) is a sub-share corresponding to the set SP(i) among the sub-shares ρ 0 , . . . , β N−1 ;

the secure computation method comprises:

efficient rotating by calculating 2ρ (SP(i)) <a> (SP(i)) ∈Z p to obtain a new share <a> (SP(i)) by secure computation apparatuses PA(φ(i, 0)), . . . , PA(φ(i, k−1)); and

obtaining a share <a> (PA(k)∈SP(i′+1)) using a share <a> (PA(0)∈SP(i)) by the secure computation apparatus PA(φ(i′, 0)), and then transmitting the share <a> (PA(k)ESP(1′+1)) to the secure computation apparatus PA(φ(i′+1, k)) via a network, performing redistribution to obtain a share <a> (PA(j)∈SP(i′+1)) using a share <a> (PA(j)∈SP(i′)) by each of the secure computation apparatuses PA(φ(i′, j)) for j=1, . . . , k−1.

10. A non-transitory computer-readable recording medium storing a program for causing a computer to function as the secure computation apparatus according to claim 7 .

11. A secure computation apparatus of the secure computation system according to claim 6 .

12. A non-transitory computer-readable recording medium storing a program for causing a computer to function as the secure computation apparatus according to claim 11 .