SECURE RANDOM NUMBER GENERATION SYSTEM, SECURE COMPUTATION APPARATUS, SECURE RANDOM NUMBER GENERATION METHOD, AND PROGRAM

Abstract

A secure random number that follows a binomial distribution is generated without performing successive communication. A secure computation apparatus (1.sub.i) generates a share [r].sub.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.sub.A and a polynomial f.sub.A. A pseudorandom number generating unit (11) obtains a pseudorandom number p.sub.A for each of the keys k.sub.A by computing the pseudorandom function PRF(k.sub.A, a) using the keys k.sub.A. A bit counting unit (12) counts the number r.sub.A of 1s included in each pseudorandom number p.sub.A. A random number share generating unit (13) obtains the sum of products of the number r.sub.A of 1s and an output of the polynomial f.sub.A(i) corresponding to the number r.sub.A of 1s as the share [r].sub.i of the random number r.

Claims

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.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0010] FIG. 1 is a diagram illustrating a functional configuration of a secure random number generation system.

[0011] FIG. 2 is a diagram illustrating a functional configuration of a secure computation apparatus.

[0012] FIG. 3 is a diagram illustrating a processing procedure of a secure random number generation method.

[0013] FIG. 4 is a diagram illustrating a functional configuration of a computer.

DESCRIPTION OF EMBODIMENTS

[0014] In this specification, “_” (underscore) in a subscript represents that a character on the right side is added to a character on the left side as a subscript. That is, “a.sub.b_c” represents that b.sub.c is added to a as a subscript.

[0015] First, the existing technologies on which the present invention is premised will be described.

[0016] Shamir's secret sharing method

[0017] Shamir's secret sharing method is a method in which a secret value s is broken up into n fragments by a random polynomial f, and the secret value s is restored from any t fragments (refer to Reference Literature 1, for example). Hereinafter, one fragment obtained by breaking up a certain value is called as a “share”, and a set of all shares is called as a “concealed value”. The concealed value of a certain value ⋅ is represented by [⋅], and the i.sup.th share of the concealed value [⋅] is represented by [⋅].sub.i. Note that n is an integer of 3 or more, and t is an integer that satisfies n≥2t−1.

[0018] [Reference Literature 1] A. Shamir, “How to share a secret,” Communications of the ACM, Vol. 22, No. 11, pp. 612-613, 1979.

[0019] In the Shamir's secret sharing method, first, with respect to a secret s on a finite field Z.sub.p with order p, a t-1.sup.th order polynomial f(x)=r.sub.t−1x.sup.t−1+ . . . +r.sub.1x.sup.1+s on the finite field Z.sub.p is selected. Note that r.sub.i is a random value on the finite field Z.sub.p. Here, each of shares [s].sub.1, . . . , [s].sub.n of the secret s is obtained as [s].sub.i=f(i), for example. When the secret s is restored, the constant term s of the polynomial f(x) is obtained by performing polynomial interpolation using any t or more shares that do not duplicate.

Pseudorandom Secret Sharing

[0020] The pseudorandom secret sharing is a method for generating a share of a uniform random number using a pseudorandom function without performing communication (refer to Reference Literature 2, for example).

Reference Literature 2

[0021] R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation,” Theory of Cryptography, LNCS 3378, pp. 342-362, 2005.

[0022] A pseudorandom function PRF: K×{0, 1}.sup.α.fwdarw.Z.sub.p is a function for outputting a random number on an (approximately) uniform finite field Z.sub.p by receiving a private key and a bit stream of length α. Here, K represents a keyspace. Also, consider a case where shares in the Shamir's secret sharing method are retained by n parties P.sub.1, . . . , P.sub.n in a broken up manner. Here, the shares [r].sub.1, . . . , [r].sub.n of a random number r are retained by n parties in a manner described below.

[0023] 1. First, the key of the pseudorandom function is shared by some parties, in advance. Specifically, a set A is defined as a set constituted by n−t+1 parties selected from the n parties, and the key k.sub.A∈K is shared by all of the n−t+1 parties included in the set A. Conversely, t−1 parties that are not included in the set A do not obtain information regarding the key k.sub.A. Similarly, with respect to each set A that can be envisioned, all parties included in the envisioned set A shares a different key k.sub.A. Also, separately, with respect to each of all of the sets A, a t.sup.th order polynomial f.sub.A corresponding to the set A is shared. Here, assume that a condition that f.sub.A(0)=1 and f.sub.A(i)=0 (if P.sub.i is not included in set A) is satisfied.

[0024] 2. When a random number needs to be generated, each party generates a pseudorandom number with a value a such as a time stamp that is used in common. Specifically, when parties P.sub.i are included in a set A.sub.j and retain a key set {k.sub.A_j}, each party P.sub.i computes [r].sub.i←Σ.sub.jPRF(k.sub.A_j, a).Math.f.sub.A_j(i). Here, J is the number of sets A to which the party P.sub.i belongs, and j indicates an integer from 1 to j.

[0025] The share [r].sub.i to be obtained by the party P.sub.i with the processing described above is a share of a pseudorandom number r=Σ.sub.APRF(k.sub.A, a).

Binomial Distribution

[0026] The number of 1s included in L-bit uniform random number r∈{0, 1}.sup.L is known to be a random number that follows a binomial distribution Bin(L, ½). If a pseudorandom function PRF: K×{0, 1}.sup.α.fwdarw.{0, 1}.sup.L has sufficient uniformity, the number of ls included in the pseudorandom number PRF(k, a) can also be said to similarly follow the binomial distribution Bin(L, ½).

EMBODIMENT

[0027] Here, an embodiment of the present invention will be described in detail. Note that the same reference numerals are added to constituent units that have the same function, in the drawings, and redundant description will be omitted.

[0028] In the secure random number generation system of the embodiment, N (≥3) secure computation apparatus computes, in a cooperated manner, a concealed value of a random value that follows the binomial distribution. In the present embodiment, it is premised on that a multi-party computation based on the Shamir's secret sharing method is used.

[0029] A secure random number generation system 100 of the embodiment includes n (≥3) secure computation apparatuses 1.sub.1, . . . , 1.sub.n, as shown in FIG. 1, for example. In the present embodiment, the secure computation apparatuses 1.sub.l, . . . , 1.sub.n are connected to a communication network 9. The communication network 9 is a communication network of a circuit switching system or a packet exchange system that is configured such that connected apparatuses can communicate to each other, and the Internet, LAN (Local Area Network), WAN (Wide Area Network), or the like can be used. Note that the apparatuses need not communicate on-line via the communication network 9. For example, the configuration may be such that information to be input to the secure computation apparatuses 1.sub.l, . . . , 1.sub.n is stored in a portable recording medium such as a magnetic tape or a USB memory, and the information is input off-line from the portable recording medium to the secure computation apparatuses 1.sub.l, . . . , 1.sub.n, for example.

[0030] The secure computation apparatus 1.sub.i (i=1, . . . , n) included in the secure random number generation system 100 of the embodiment includes a parameter storage unit 10, a pseudorandom number generating unit 11, a bit counting unit 12, a random number share generating unit 13, and an output unit 14, as shown in FIG. 2, for example. The secure random number generation method of the present embodiment is realized by the secure computation apparatus 1.sub.i (i=1, . . . , n) performing the processing in the steps to be described later while cooperating with another secure computation apparatus 1.sub.j (j=1, . . . , n, where i≠j).

[0031] The secure computation apparatus 1.sub.i is a special apparatus that is configured by a special program being read in a known or dedicated computer including a central processing unit (CPU), a main storage device (RAM: Random Access Memory), and the like, for example. The secure computation apparatus 1.sub.i executes the processing under the control of the central processing unit, for example. The data input to the secure computation apparatus 1.sub.i and the data obtained by the processing are stored in the main storage device, for example, and the data stored in the main storage device is read out to the central processing unit as necessary and is used for another processing. At least some of the processing units of the secure computation apparatus 1.sub.i may be configured by hardware such as an integrated circuit. The storage units included in the secure computation apparatus 1.sub.i can be configured by a main storage device such as RAM (Random Access Memory), an auxiliary storage device such as a hard disk, an optical disk, or a semiconductor memory device such as a flash memory, or middleware such as a relational database or key-value store, for example.

[0032] In the following, the processing procedure of the secure random number generation method to be executed by the secure random number generation system 100 of the embodiment will be described with reference to FIG. 3.

[0033] The parameter storage unit 10 stores the pseudorandom function PRF: K×{0, 1}.sup.α.fwdarw.{0, 1}.sup.L, J keys {k.sub.A_1, . . . , k.sub.A_J}, and k polynomials {f.sub.A_1 (x), . . . , f.sub.A_J(x)}.

[0034] In step S11, the pseudorandom number generating unit 11 computes, for each integer j of 1 or more and J or less, a pseudorandom function PRF(k.sub.A_j, a) using a key k.sub.A_j and a parameter a that are stored in the parameter storage unit 10. The parameter a is a parameter, such as a time stamp, that can be used in common between all the secure computation apparatuses 1.sub.l. . . , 1.sub.n. The pseudorandom number generating unit 11 outputs pseudorandom numbers p.sub.A_j calculated from keys k.sub.A_j to the bit counting unit 12.

[0035] In step S12, the bit counting unit 12 obtains the number r.sub.A_j of 1s included in the pseudorandom number p.sub.A_j for each integer j of 1 or more and J or less. The bit counting unit 12 output the numbers r.sub.A_j of 1s obtained from the pseudorandom numbers p.sub.A_j to the random number share generating unit 13.

[0036] In step S13, the random number share generating unit 13 computes a sum of products [r].sub.i←Σ.sub.jr.sub.A_j.Math.f.sub.A_j(i) of the numbers r.sub.A_j of 1s and the outputs of polynomial f.sub.A_j (i). Here, i is the number of the secure computation apparatus. This [r].sub.i is a share of the random number r=Σ.sub.Ar.sub.A. The random number share generating unit 13 outputs the share [r].sub.i of a random number r to the output unit 14.

[0037] In step S14, the output unit 14 outputs the share [r].sub.i of the random number r.

[0038] The number r.sub.A of 1s included in an L-bit pseudorandom number p.sub.A, which is an output of the pseudorandom function PRF(k.sub.A, a), follows a binomial distribution Bin(L, ½). Similarly, the number r of 1s included in a total N=(nCn−t+1)×L-bit random number computed by all the keys k.sub.A that are shared by the parties follows the binomial distribution Bin(N, ½). Here, nCn−t+1 represents the number of combinations of selecting different n−t+1 pieces from different n pieces. This number r of 1s satisfies r=Σ.sub.Ar.sub.A. Also, these computations can be locally performed, and therefore communication between parties is not needed. The present invention provides a technique in which, by utilizing this property, each party obtains the share [r].sub.i of a random number that follows a binomial distribution Bin(N, ½) without the parties communicating to each other, and the concealed value [r] of a random number r is generated as an entire system.

[0039] In the present invention, the need of successive communication is eliminated when a secure random number is generated, based on the pseudorandom secret sharing method. Here, as a result of changing the pseudorandom secret sharing method for generating a uniform random number such that a random number that follows a binomial distribution can be generated, the communication amount is largely reduced relative to that of a known method. As described above, according to the present invention, a secure random number that follows a binomial distribution and can be used for output privacy protection of a secure computation result and the like can be generated without performing successive communication. In the known method, communication of an amount that is in proportion to a noise range N is needed every time a secure random number is generated.

[0040] Although an embodiment of the present invention have been described above, a specific configuration is not limited to the embodiment, and even if a design change or the like is made without departing from the spirit of the present invention, when necessary, such a change is included in the scope of the present invention as a matter of course. The various kinds of processing described in the embodiment are not necessarily executed in chronological order according to the order of descriptions, and may be parallelly or individually executed depending on the processing capabilities of the device that executes the processing or according to the need.

Program and Recording Medium

[0041] When the various processing functions of the devices described in the above embodiment are realized using a computer, the functions that the devices need to have are to be described in the form of a program. Then, this program is read in a storage unit 1020 of a computer shown in FIG. 4, and a control unit 1010, an input unit 1030, an output unit 1040 are caused to operate, and as a result, the various processing functions of the above devices are realized on the computer.

[0042] The program that describes the contents of such processing can be recorded in a computer-readable recording medium. Any kind of computer-readable recording medium may be employed, such as a magnetic recording device, an optical disc, a magneto-optical recording medium, or a semiconductor memory.

[0043] The program is distributed by, for example, selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. Furthermore, it is possible to employ a configuration in which the program is stored in a storage device of a server computer, and the program is distributed by the server computer transferring the program to other computers via a network.

[0044] A computer that executes such a program first stores, in a storage device thereof, the program that is recorded on a portable recording medium or that has been transferred from a server computer. Thereafter, when executing processing, the computer reads the program stored in the storage device thereof, and executes processing according to the program thus read. In another mode of execution of the program, the computer may read the program directly from a portable recording medium and execute processing according to the program. In addition, the computer may sequentially execute processing according to the received program every time the computer receives the program transferred from a server computer. Also, it is possible to employ a configuration for executing the above-described processing by using a so-called ASP (Application Service Provider) type service, which does not transfer a program from the server computer to the computer, but realizes processing functions by only making instructions to execute the program and acquiring the results. The program according to the embodiments may be information that is used by an electronic computer to perform processing, and that is similar to a program (e.g. data that is not a direct command to the computer, but has the property of defining computer processing).

[0045] Also, although the device is formed by running a predetermined program on a computer in the embodiment, at least part of the content of the above processing may be realized using hardware.