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

Abstract

A secure computation apparatus (1.sub.i) generates a concealed value [r] of a random number r following a discrete Laplace distribution with parameter α. A bit stream generating unit (11) generates a concealed value stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] that is constituted by a concealed value [b.sub.0] of a random number bit bo following a Bernoulli distribution with probability (1−α)/(1+α) and concealed values [b.sub.1], . . . , [b.sub.N] of random number bits b.sub.1, . . . , b.sub.N each following a Bernoulli distribution with probability (1−α). An absolute value determining unit (12) obtains a concealed value [L] of a position L at which 1 is first set from the head of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N. A sign determining unit (13) obtains a result [L.Math.s] obtained by multiplying the concealed value [L] by a concealed value [s] of a random sign s, as a concealed value [r] 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 [r] of a random number r, the random number r following a discrete Laplace distribution with parameter α, wherein, α is a number that is larger than 0 and smaller than 1, and N is an integer of 2 or more, the secure computation apparatuses each comprise: processing circuitry configured to: generate a concealed value stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] that is constituted by a concealed value [b.sub.0] of a random number bit b.sub.0 that follows a Bernoulli distribution with probability (1−α)/(1+α) and concealed values [b.sub.0], . . . , [b.sub.N] of random number bits b.sub.1, . . . , b.sub.N that each follow a Bernoulli distribution with probability (1−α); obtain a concealed value [L] of a position L at which 1 is first set from the head of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N; and obtain a result [L.Math.s] obtained by multiplying the concealed value [L] by a concealed value [s] of a random sign s, as a concealed value [r] of the random number r.

2. The secure random number generation system according to claim 1, wherein, Z.sub.p is a finite field of order p and i is each of integers from 0 to N, the processor circuitry is further configured to: set a section I in which |I|/p is close to the probability of the Bernoulli distribution; generate a concealed value [r.sub.i] of a random number r.sub.i on the finite field Z.sub.p, for each integer i; and generate a result obtained by judging whether or not the random number r.sub.i is included in the section I using the concealed value [r.sub.i], for each integer i, as the concealed value [b.sub.i].

3. The secure random number generation system according to claim 2, wherein the processor circuitry is further configured to: generate a concealed value stream [c.sub.0], [c.sub.1], . . . , [c.sub.N], the result of computing [b.sub.0] OR . . . OR [b.sub.i] for each integer i being a concealed value [c.sub.i]; and generate a result of computing Σ.sub.i(1−[c.sub.i]) as the concealed value [L].

4. 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 [r] of a random number r.sub.s the random number r following a discrete Laplace distribution with parameter α, wherein, α is a number that is larger than 0 and smaller than 1, and N is an integer of 2 or more, the secure computation apparatus comprises: processor circuitry configured to: generate a concealed value stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] that is constituted by a concealed value [b.sub.0] of a random number bit b.sub.0 that follows a Bernoulli distribution with probability (1−α)/(1+α) and concealed values [b.sub.1], . . . , [b.sub.N] of random number bits b.sub.1, . . . , b.sub.N that each follow a Bernoulli distribution with probability (1−α); obtain a concealed value [L] of a position L at which 1 is first set from the head of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N; and obtain a result [L.Math.s] obtained by multiplying the concealed value [L] by a concealed value [s] of a random sign s, as a concealed value [r] of the random number r.

5. A secure random number generation method being 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 [r] of a random number r, the random number r following a discrete Laplace distribution with parameter α, wherein, α is a number that is larger than 0 and smaller than 1 and N is an integer of 2 or more, the secure random number generation method comprising: generating, by processor circuitry of each of the secure computation apparatuses, a concealed value stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] that is constituted by a concealed value [b.sub.0] of a random number bit b.sub.0 that follows a Bernoulli distribution with probability (1−α)/(1+α) and concealed values [b.sub.1], . . . , [b.sub.N] of random number bits b.sub.1, . . . , b.sub.N that each follow a Bernoulli distribution with probability (1−α); obtaining, by the processor circuitry, a concealed value [L] of a position L at which 1 is first set from the head of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N; and obtaining, by the processor circuitry, a result [L.Math.s] obtained by multiplying the concealed value [L] by a concealed value [s] of a random sign s, as a concealed value [r] of the random number r.

6. A non-transitory computer recording medium on which a program for causing a computer to operate as the secure computation apparatus according to claim 4 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] First, the existing technologies on which the present invention is premised will be described.

[0015] Secure Computation

[0016] The secure computation is a technique for performing computation in a state in which numerical values are encrypted or concealed (see NPL 1, for example). In the following, a value obtained by concealing a certain value .Math. is called as a “concealed value”, and is represented by [.Math.]. In the secure computation, an addition [a+b], a subtraction [a−b], and a multiplication [a.Math.b] of concealed values [a] and [b] can be computed. Also, when a and b are truth values (1-bit value), in particular, an exclusive OR [a XOR b], a logical product [a AND b] and a logical sum [a OR b] can be computed.

[0017] A method is known for realizing more complex processing by the secure computation utilizing the above properties. Processing, among such processing, that will be used in the present invention will be shown as following.

[0018] Prefix logical sum (Prefix-OR)

[0019] By using logical sum computation, concealed values ([b.sub.1]=[a.sub.1], [b.sub.2]=[a.sub.1 OR a.sub.2], . . . , [b.sub.n]=[a.sub.1 OR a.sub.2 OR . . . OR a.sub.n]) of a bit stream (b.sub.1, . . . , b.sub.n) can be obtained with respect to concealed values ([a.sub.1], . . . , [a.sub.n]) of a bit stream (a.sub.1, . . . , a.sub.n). Here, with respect to any bit stream (a.sub.1, . . . , a.sub.n) in which a.sub.i=1 is first achieved at certain i and a.sub.1, . . . , a.sub.i−1 before a.sub.i are all 0, the bit stream (b.sub.1, . . . , b.sub.n) satisfies a condition that b.sub.1, . . . , b.sub.i−1=0 and b.sub.1, . . . , b.sub.n=1.

[0020] Uniform Random Number Generation

[0021] According to Reference Literatures 1 and 2, a concealed value [r] of a uniform random number r can be generated without knowing an original random number value r. [0022] [Reference Literature 1] 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. [0023] [Reference Literature 2] J. Bar-Ilan and D. Beaver, “Non-cryptographic fault-tolerant computing in constant number of rounds of interaction,” Proceedings of the 8th annual ACM Symposium on Principles of Distributed Computing, 1989, pp. 201-209.

[0024] Interval Test

[0025] According to Reference Literature 3, with respect to a concealed value [a] of a certain value a, a concealed value [b] of a concealed bit obtained by judging whether or not the value a is contained in a certain range I can be obtained. Here, if a∈I, then b=1, and if not, then b=0. [0026] [Reference Literature 3] T. Nishide and K. Ohta, “Multiparty computation for interval, equality, and comparison without bit-decomposition protocol,” Public Key Cryptography, LNCS 4450, pp. 343-360, 2007.

[0027] Bernoulli Distribution

[0028] The Bernoulli distribution Ber(β) is a distribution for generating 1 with probability β, and 0 with probability 1−β.

[0029] Discrete Laplace Distribution

[0030] Assume that probability variables B.sub.0, B.sub.1, . . . that are independently tried satisfy B.sub.0˜Ber((1−α)/(1+α)) and B.sub.j≥.sub.1˜Ber(1−α). Here, ˜ indicates to follow the distribution. That is, assume that the probability variable Bo follows the Bernoulli distribution with probability (1−α)/(1+α), and the probability variables B.sub.1, B.sub.2, . . . follow the Bernoulli distribution with probability (1−α). Here, with respect to a position L at which B.sub.L=1 is first achieved from the head (that is, L that satisfies B.sub.0, . . . , B.sub.L−1=0 and B.sub.L=1), a value .sup.˜L=L or −L obtained by inverting the sign with probability ½ follows a discrete Laplace distribution DL(α) with parameter α.

Embodiment

[0031] 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.

[0032] In a secure random number generation system of the embodiment, n (≥2) secure computation apparatuses compute a concealed value of a random value that follows the discrete Laplace distribution in a cooperated manner. In the present embodiment, a secure computation on a finite field Z.sub.p with order p is envisioned, but there is no limitation thereto, and the present invention can be similarly applied to a secure computation on another finite field.

[0033] A secure random number generation system 100 of the embodiment includes n (≥2) secure computation apparatuses 11, . . . , 1.sub.n, as shown in FIG. 1, for example. In the present embodiment, the secure computation apparatuses 1.sub.1, . . . , 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.1, . . . , 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.1, . . . , 1.sub.n, for example.

[0034] 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 bit stream generating unit 11, an absolute value determining unit 12, a sign determining unit 13, and an output unit 14, as shown in FIG. 2, for example. The bit stream generating unit 11 includes a section setting unit 111, a random number generating unit 112, and an interval test unit 113. The absolute value determining unit 12 includes a prefix logical sum unit 121 and a bit inversion total sum unit 122. The sign determining unit 13 includes a sign generating unit 131 and a sign multiplying unit 132. 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).

[0035] 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.

[0036] 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.

[0037] The parameter storage unit 10 stores a parameter a of a predetermined discrete Laplace distribution DL(α) and a sufficiently large natural number N. Note that α is a number that is larger than 0 and smaller than 1.

[0038] In step S11, the bit stream generating unit 11 generates a stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] of concealed values of random number bits b.sub.0, b.sub.1, . . . , b.sub.N that follow a Bernoulli distribution. Here, assume that the conditions of b.sub.0.Math.Ber((1−α)/(1+α)) and b.sub.1, . . . , b.sub.N˜Ber (1−α) are satisfied. That is, the random number bit bo follows a Bernoulli distribution with probability (1−α)/(1+α), and the random number bits b.sub.1, . . . , b.sub.N follow a Bernoulli distribution with probability (1−α). The concealed value [b.sub.i] (i=0, . . . , N) of a random number bit b.sub.i (i=0,0 . . . , N) is generated by executing the following steps S111 to S113 for each integer i.

[0039] In step S111, the section setting unit 111 selects a section I=[γ.sub.1, γ.sub.2] on the finite field Z.sub.p such that β≈|I|/p. Here, β is probability of the Bernoulli distribution. That is, if i=0, then β=(1−α)/(1+α), and if i≥1, then β=(1−α). The section setting unit 111 outputs the selected section I to the interval test unit 113.

[0040] In step S112, the random number generating unit 112 generates a concealed value [r.sub.i] of a random number ri on the finite field Z.sub.p. The random number generating unit 112 outputs the generated concealed value [r.sub.i] of the random number r.sub.i to the interval test unit 113.

[0041] In step S113, the interval test unit 113 judges r.sub.i∈I by an interval test. That is, a concealed value [b] of a result b that is obtained by judging whether or not the random number r.sub.i is included in the section I is generated, using the concealed value [r.sub.i] of the random number ri. This judgment result b follows a Bernoulli distribution Ber(β) with probability β. That is, b˜Ber(β) is satisfied. The interval test unit 113 outputs the concealed value [b] of the judgment result b as the concealed value [b.sub.i] of the random number bit b.sub.i.

[0042] In step S12, the absolute value determining unit 12 obtains a concealed value [L] of a position L at which 1 is first set from the head out of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N. The concealed value [L] of the position L can be obtained by executing the following steps 5121 to 5122.

[0043] In step 5121, the prefix logical sum unit 121 obtains the result of executing Prefix-OR on a concealed value stream [b.sub.0], [b.sub.1], . . . , [b.sub.N] as a concealed value stream [c.sub.0], [c.sub.1], . . . , [c.sub.N]Specifically, the prefix logical sum unit 121 obtains [c.sub.0]=[b.sub.0], [c.sub.1]=[b.sub.0] OR [b.sub.1], . . . , [c.sub.N]=[b.sub.0] OR . . . OR [b.sub.N], in which the result of computing [b.sub.0] OR . . . OR [b.sub.i] for each integer i is the concealed value [c.sub.i]. The prefix logical sum unit 121 outputs the concealed value stream [c.sub.0], [c.sub.1], . . . , [c.sub.N] to the bit inversion total sum unit 122.

[0044] In step S122, the bit inversion total sum unit 122 computes [L]=Σ.sub.i(1−[c.sub.i]). L indicates the position L at which b.sub.L=1 is first achieved from the head, out of the random number bits b.sub.0, b.sub.1, . . . , b.sub.N. The bit inversion total sum unit 122 outputs the computed concealed value [L] of the position L.

[0045] In step S13, the sign determining unit 13 obtains a result [L.Math.s] that is a result of multiplying the concealed value [L] of the position L by a concealed value [s] of a random sign s. The multiplication result [L.Math.s] can be obtained by executing the following steps S131 and S132.

[0046] In step S131, the sign generating unit 131 generates the concealed value [s] of the random sign s by computing [s]←R{−1, 1}. Here, ←R represents an operation for randomly selecting an element of a set. The sign generating unit 131 outputs the generated concealed value [s] of the sign s to the sign multiplying unit 132.

[0047] In step S132, the sign multiplying unit 132 multiplies the concealed value [L] of the position L by the concealed value [s] of the sign s. The concealed value [L.Math.s] of this multiplication result is a concealed value of a random number that follows a discrete Laplace distribution DL(α). The sign multiplying unit 132 outputs the concealed value [L.Math.s] of the multiplication result.

[0048] In step S14, the output unit 14 outputs the concealed value [L.Math.s] of the multiplication result as the concealed value [r] of a random number r that follows a discrete Laplace distribution DL(α) with parameter α.

[0049] In the present invention, the secure computation of a random number that follows a discrete Laplace distribution is realized by performing secure computation on a random number bit that follows the Bernoulli distribution. Here, in the present invention, as a result of directly generating a random number that follows a discrete Laplace distribution without performing approximation by a geometric distribution, the reduction in privacy protection strength that occurs due to approximation is avoided. In this way, according to the present invention, secure random numbers, which follow the discrete Laplace distribution, that can be used for output privacy protection of secure computation results and the like can be generated without performing approximation. In the known methods, approximation by a geometric distribution was needed.

[0050] 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.

[0051] Program and Recording Medium

[0052] 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.

[0053] 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.

[0054] 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.

[0055] 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).

[0056] 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.