SECURE RANDOM NUMBER GENERATION SYSTEM, SECURE COMPUTATION APPARATUS, SECURE RANDOM NUMBER GENERATION METHOD, AND PROGRAM
A secure random number that follows a binomial distribution is generated without performing successive communication. A secure computation apparatus ( 1 i ) generates a share [r] i of a random number r that follows a binomial distribution. A parameter storage unit ( 10 ) stores a pseudorandom function PRF, at least one set of a key k A and a polynomial f A . A pseudorandom number generating unit ( 11 ) obtains a pseudorandom number p A for each of the keys k A by computing the pseudorandom function PRF(k A , a) using the keys k A . A bit counting unit ( 12 ) counts the number r A of 1s included in each pseudorandom number p A . A random number share generating unit ( 13 ) obtains the sum of products of the number r A of 1s and an output of the polynomial f A (i) corresponding to the number r A of 1s as the share [r] i of the random number r.
1 . A secure random number generation system comprising a plurality of secure computation apparatuses and generating a concealed value of a random number, the random number following a binomial distribution,
the secure computation apparatuses each comprising:
processing circuitry configured to:
store a pseudorandom function and at least one set of a key and a polynomial;
obtain a pseudorandom number for each of the keys by computing the pseudorandom function using the key;
count the number of 1s included in each pseudorandom number; and
obtain the sum of products of the number of 1s and an output of the polynomial corresponding to the number of 1s as the share of the random number.
2 . A secure computation apparatus being to be used in a secure random number generation system, the secure random number generation system generating a concealed value of a random number, the random number following a binomial distribution, the secure computation apparatus comprising:
processing circuitry configured to:
store a pseudorandom function and at least one set of a key and a polynomial;
obtain a pseudorandom number for each of the keys by computing the pseudorandom function using the key;
count the number of 1s included in each pseudorandom number; and
obtain the sum of products of the number of 1s and an output of the polynomial corresponding to the number of 1s as the share of the random number.
3 . A secure random number generation method to be executed by a secure random number generation system comprising a plurality of secure computation apparatuses, the secure random number generation system generating a concealed value of a random number, the random number following a binomial distribution,
wherein a pseudorandom function and at least one set of a key and a polynomial are stored in a storage unit,
the secure random number generation method comprises:
obtaining, by processing circuitry of each of the secure computation apparatuses, a pseudorandom number for each of the keys by computing the pseudorandom function using the key;
counting, by the processing circuitry, the number of 1s included in each pseudorandom number; and
obtaining, by the processing circuitry, the sum of products of the number of 1s and an output of the polynomial corresponding to the number of 1s as the share of the random number.
4 . A non-transitory computer recording medium on which a program for causing a computer to operate as the secure computation apparatus according to claim 2 is recorded.