SECURE COMPUTATION SYSTEM, SECURE COMPUTATION APPARATUS, SECURE COMPUTATION METHOD, AND PROGRAM
A secure computation apparatus obtains a sequence ρ∘f obtained by rotating elements f p-1 , . . . , f 0 of a sequence f by ρ elements by secure computation using share of random number ρ and share of the sequence f without obtaining the random number p and the sequence f, obtains the value b′ϵ{0, . . . , p−1} representing the position of the element cf b′ whose value is α among the elements cf p-1 , . . . , cf 0 in the sequence ρ∘f, and obtains the share of the value b by secure computation using the share of the random number ρ and the value b′. Here, p is an integer of 2 or more, f is a sequence of p elements f p-1 , . . . , f 0 , a value of one element f b among the elements f p-1 , . . . , f 0 is α, a value of an element other than the element f b is other than α, and β is a random integer.
1 . A secure computation system in which n is an integer of 2 or more, j=0, . . . , n−1, p is an integer of 2 or more, f is a sequence of p elements f p-1 , . . . , f 0 , a value of one element f b among elements f p-1 , . . . , f 0 is α, a value of an element other than the element f b is other than α, a value representing a position of the element f b is be {0, . . . , p−1}, ρ is a random number represented by an integer, the system comprising:
n secure computation apparatuses PA( 0 ), . . . , PA(n−1),
wherein the secure computation apparatus PA(j) includes processing circuitry configured to:
obtain a sequence ρ∘f by rotating the elements f p-1 , . . . , f 0 of the sequence f by ρ elements by secure computation using a share of the random number ρ and a share of the sequence f without obtaining the random number ρ and the sequence f,
obtain a value b′E {0, . . . , p−1} representing a position of an element cf b′ whose value is α among the elements cf p-1 , . . . , cf 0 in the sequence ρ∘f, and
obtain the share of the value b by secure computation using the share of the random number ρ and the value b′.
2 . A secure computation apparatus in which p is an integer of 2 or more, f is a sequence of p elements f p-1 , . . . , f 0 , a value of one element f b among elements f p-1 , . . . , f 0 is α, a value of an element other than the element f b is a value other than α, a value representing a position of the element f b is be{0, . . . , p−1}, ρ is a random number represented by an integer, the secure computation apparatus comprising processing circuitry configured to:
obtain the sequence ρ∘f by rotating the elements f p-1 , . . . , f 0 in the sequence f by ρ elements by secure computation using share of the random number ρ and share of the sequence f without obtaining the random number ρ and the sequence f,
obtain a value b′ϵ{0, . . . , p−1} representing a position of an element cf b′ in which the value is α among the elements cf p-1 , . . . , Cf 0 in the sequence ρ∘f, and
obtain the share of the value b by secure computation using the share of the random number ρ and the value b′.
3 . The secure computation apparatus according to claim 2 , wherein
all values of the elements f p-1 , . . . , f 0 other than the element f b are β and β≠α is satisfied.
4 . The secure computation apparatus according to claim 3 , wherein
iϵ{0, . . . , p−1} is satisfied, a sequence f is a bit string, a value of each element f i of the elements f p-1 , . . . , f 0 is 0 or 1, (α, β)=(1,0) or (α, β)=(0,1) is satisfied, the random number ρ is an element of a quotient ring Z p modulo p, the share of the random number ρ is a share sha(ρ) j obtained by secretly sharing ρϵZ p ,
the processing circuitry obtains the sequence ρ∘f, which is a bit string obtained by bit-rotating the elements f p-1 , . . . , f 0 in the sequence f by ρ bits,
the sha(ρ) j and the sha(b) j are shares obtained by secret sharing according to an additive secret sharing method or a duplicate secret sharing method, and
the processing circuitry obtains b′-sha(ρ) j ϵZ p as the share sha(b) j of the value b.
5 . The secure computation apparatus according to claim 2 , wherein the random number ρ is a uniform random number.
6 . A secure computation method, in which p is an integer of 2 or more, f is a sequence of p elements f p-1 , . . . , f 0 , a value of one element f b among elements f p-1 , . . . , f 0 is α, a value of an element other than the element f b is a value other than α, a value representing a position of the element f b is be {0, . . . , p−1}, ρ is a random number represented by an integer, the secure computation method comprising:
obtaining a sequence ρ∘f by rotating the elements f p-1 , . . . , f 0 in the sequence f by ρ elements by secure computation using share of the random number ρ and share of the sequence f without obtaining the random number ρ and the sequence f;
obtaining a value be {0, . . . , p−1} representing a position of an element cf b′ whose value is α among the elements cf p-1 , . . . , cf 0 in the sequence ρ∘f; and
obtaining the share of the value b by secure computation using the share of the random number ρ and the value b′.
7 . A non-transitory computer-readable recording medium storing a program for operating a computer as the secure computation apparatus according to claim 2 .