SECRET RANDOM NUMBER SYNTHESIZING DEVICE, SECRET RANDOM NUMBER SYNTHESIZING METHOD, AND PROGRAM

Abstract

A combination of secure texts of values a, b and c having a relationship c=ab is efficiently generated. A secure text generation part 12 generates secure texts [x.sub.i] of x.sub.i satisfying x.sub.i=f(k.sub.i), and secure texts [y.sub.i] of y.sub.i satisfying y.sub.i=g(k.sub.i), for i=0, . . . , m. A fragment generation part 13 generates .sub.i decrypted from [x.sub.i][a.sub.i] and .sub.i decrypted from [y.sub.i][b.sub.i], for i=1, . . . , m, and calculates [c.sub.i]+.sub.i[b.sub.i]+.sub.i[a.sub.i]+.sub.i.sub.i and generates secure texts [z.sub.1], . . . , [z.sub.m]; and A random number synthesizing part 14 generates a secure text [z.sub.0] using different values k.sub.0, . . . , k.sub.m and secure texts [z.sub.1], . . . , [z.sub.m].

Claims

1. A secret random number synthesizing device, assuming that t is an integer of zero or more, m=2t+1, i is any of integers ranging from one to m, inclusive, [a.sub.i], [b.sub.i] and [c.sub.i] are secure texts of a.sub.i, b.sub.i and c.sub.i whose numbers are each m, k.sub.0, . . . , k.sub.m are (m+1) different values, and f(x) and g(x) are random t-th order polynomials, comprising: circuitry configured to: generate secure texts [x.sub.i] of x.sub.i satisfying x.sub.i=f(k.sub.i), and secure texts [y.sub.i] of y.sub.i satisfying y.sub.i=g(k.sub.i), for i=0, . . . , m; generate .sub.i decrypted from [x.sub.i][a.sub.i] and .sub.i decrypted from [y.sub.i][b.sub.i], for i=1, . . . , m, and calculates [c.sub.i]+.sub.i[b.sub.i]+.sub.i[a.sub.i].sub.i.sub.i and generates secure texts [z.sub.1], . . . , [z.sub.m]; and generate a secure text [z.sub.0] by calculating a following formula, $\left[z_0\right]\underset{j=1}{\overset{2.Math.t+1}{.Math.}}.Math..Math.{}_j\left(k_0\right)\left[z_j\right]$ $\mathrm{where}$ ${}_j\left(x\right)=\underset{1i2.Math.t+1,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}.$

2. The secret random number synthesizing device according to claim 1, wherein the circuitry configured to generate secure texts [x.sub.i] and [y.sub.i] of random values, for i=0, . . . , t, and generates secure texts [x.sub.i] and [y.sub.i] for i=t+1, . . . , m by calculating a following formula, $\left[x_i\right]\underset{j=0}{\overset{t}{.Math.}}.Math..Math.{}_j^{}\left(k_i\right)\left[x_j\right],.Math.\left[y_i\right]\underset{j=0}{\overset{t}{.Math.}}.Math..Math.{}_j^{}\left(k_i\right)\left[y_j\right]$ $\mathrm{where}$ ${}_j^{}\left(x\right)=\underset{0it,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}.$

3. The secret random number synthesizing device according to claim 2, wherein [a.sub.i], [b.sub.i], [c.sub.i], [x.sub.i], [y.sub.i] and [z.sub.i] are secure texts through additive secret sharing, and for i=0, . . . , t, the circuitry configured to generate random values and adopts the random values as shares of the secure texts [x.sub.i], and generates random values and adopts the random values as shares of the secure texts [y.sub.i].

4. A secret random number synthesizing method, assuming that t is an integer of zero or more, m=2t+1, i is any of integers ranging from one to m, inclusive, [a.sub.i], [b.sub.i] and [c.sub.i] are secure texts of a.sub.i, b.sub.i and c.sub.i whose numbers are each m, k.sub.0, . . . , k.sub.m are (m+1) different values, and f(x) and g(x) are random t-th order polynomials, comprising: generating secure texts [x.sub.i] of x.sub.i satisfying x.sub.i=f(k.sub.i), and secure texts [y.sub.i] of y.sub.i satisfying y.sub.i=g(k.sub.i), for i=0, . . . , m, by circuitry of a secret random number synthesizing device; generating .sub.i decrypted from [x.sub.i][a.sub.i] and .sub.i decrypted from [y.sub.i][b.sub.i], for i=1, . . . , m, and calculating [c.sub.i]+.sub.i[b.sub.i]+.sub.i[a.sub.i]+.sub.i.sub.i and generating secure texts [z.sub.i], . . . , [z.sub.m] by the circuitry of the secret random number synthesizing device; and generating a secure text [z.sub.0] by calculating a following formula by the circuitry of the secret random number synthesizing device, $\left[z_0\right]\underset{j=1}{\overset{2.Math.t+1}{.Math.}}.Math..Math.{}_j\left(k_0\right)\left[z_j\right]$ $\mathrm{where}$ ${}_j\left(x\right)=\underset{1i2.Math.t+1,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}.$

5. (canceled)

6. A non-transitory computer readable medium including computer executable instructions that make a secret random number synthesizing device, assuming that t is an integer of zero or more, m=2t+1, i is any of integers ranging from one to m, inclusive, [a.sub.i], [b.sub.i] and [c.sub.i] are secure texts of a.sub.i, b.sub.i and c.sub.i whose numbers are each m, k.sub.0, . . . , k.sub.m are (m+1) different values, and f(x) and g(x) are random t-th order polynomials, perform a method comprising: generating secure texts [x.sub.i] of x.sub.i satisfying x.sub.i=f(k.sub.i), and secure texts [y.sub.i] of y.sub.i satisfying y.sub.i=g(k.sub.i), for i=0, . . . , m; generating .sub.i decrypted from [x.sub.i][a.sub.i] and .sub.i decrypted from [y.sub.i][b.sub.i], for i=1 . . . , m, and calculating [c.sub.i]+.sub.i[b.sub.i]+.sub.i[a.sub.i]+.sub.i.sub.i and generating secure texts [z.sub.1], . . . , [z.sub.m], and generating a secure text [z.sub.0] by calculating a following formula, $\left[z_0\right]\underset{j=1}{\overset{2.Math.t+1}{.Math.}}.Math..Math.{}_j\left(k_0\right)\left[z_j\right]$ $\mathrm{where}$ ${}_j\left(x\right)=\underset{1i2.Math.t+1,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}.$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0010] FIG. 1 is a diagram exemplifying a functional configuration of a secret random number synthesizing system;

[0011] FIG. 2 is a diagram exemplifying a functional configuration of a secret random number synthesizing device; and

[0012] FIG. 3 is a diagram exemplifying a process flow of a secret random number synthesizing method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0013] Prior to the description of embodiments, the representation method and definition of terms in this Description are described.

[0014] <Representation Method>

[0015] A value secreted by applying encryption or secret sharing to a certain value a is called a secure text of the a and is represented as [a]. The a is called the plain text of [a]. In a case where the secreting is secret sharing, a set of the secret sharing fragments held by each party owing to [a] is referred to. A share held by an i-th party P.sub.i in the secure text [a] is referred to using [a].sub.i. The share is a fragment obtained by secret sharing. The party is each participant who cooperatively performs secret calculation.

[0016] <Decryption>

[0017] A process of calculation the plain text a from the secure text [a] is called decryption, and is described as in the following formula.

aReveal([a])

[0018] <Addition, Subtraction, and Constant Multiplication>

[0019] Addition and subtraction that are each applied to the secure text adopt secure texts [a] and [b] of two values a and b as inputs, and calculate the secure texts [d.sub.1] and [d.sub.2] of the calculation results d.sub.1 and d.sub.2 of a+b and a-b. The constant multiplication operation to the secure text adopts the secure text [a] of the value a, and the plain text c as inputs, and calculates the secure text [d.sub.3] of the calculation result d.sub.3 of ca.

[0020] Execution of such operation is described as in the following formula.

[d.sub.1]Add([a],[b]),

[d.sub.2]Sub([a],[b]),

[d.sub.3]CMul(c,[a])

[0021] Note that in a case without any fear of causing misunderstanding, Add([a], [b]), Sub([a], [b]), and CMul(c, [a]) are abbreviated as [a]+[b], [a][b], and c[a], respectively.

[0022] <Generation of Random Secure Text>

[0023] A process of generating a secure text [r] of a random value r unknown to anybody is described as in the following formula.

[r]Rand( )

[0024] Embodiments of the present invention are hereinafter described in detail. In the diagrams, configuration parts having the same functions are assigned the same numerals, and redundant description is omitted.

First Embodiment

[0025] A secret random number synthesizing system of a first embodiment comprises n (2) secret random number synthesizing devices 1.sub.1, . . . , 1.sub.n, as exemplified in FIG. 1. In this embodiment, the secret random number synthesizing devices 1.sub.1, . . . , 1.sub.n are each connected to a communication network 2. The communication network 2 is a communication network that is of a circuit switching scheme or a packet switching scheme and is configured to be capable of communicating with each of the secret random number synthesizing devices 1.sub.1, . . . , 1.sub.n. For example, the Internet, LAN (Local Area Network), WAN (Wide Area Network) or the like may be used. Each device is not necessarily capable of communicating online via the communication network 2. For example, it may be configured such that information to be input into the secret random number synthesizing devices 1.sub.i (i{0, . . . , n1}) may be stored in a portable recording medium, such as magnetic tape or a USB memory, and input may be made offline from the portable recording medium.

[0026] As exemplified in FIG. 2, the secret random number synthesizing device 1 comprises an input part 11, a secure text generation part 12, a fragment generation part 13, a random number synthesizing part 14, and an output part 15. The secret random number synthesizing device 1 performs the process of each step exemplified in FIG. 3, thereby achieving a secret random number synthesizing method according to the first embodiment.

[0027] The secret random number synthesizing device 1 is a specific device configured to comprise a publicly known or dedicated computer which comprises a central processing unit (CPU) and a main memory (RAM: Random Access Memory) and in which a special program is installed. The secret random number synthesizing device 1 executes each process under control by the central processing unit, for example. Data items input into the secret random number synthesizing device 1 and data items obtained by each process are stored in the main memory, for example. The data items stored in the main memory are read by the central processing unit as required, and are used for another process. At least a part or some of the processing parts of the secret random number synthesizing device 1 may comprise hardware, such as an integrated circuit.

[0028] Referring to FIG. 3, the processing procedures of the secret random number synthesizing method according to the first embodiment are described.

[0029] In step S11, in triples of secure texts ([a.sub.i], [b.sub.i] and [c.sub.i]) of values a.sub.i, b.sub.i and c.sub.i, and (m+1) values k.sub.0, . . . , k.sub.m are input into the input part 11. Here, m=2t+1. t is an integer of zero or more. i is any of integers ranging from one to m, inclusive. The values k.sub.0, . . . , k.sub.m are freely selected different values, and preliminarily shared by all the secret random number synthesizing devices 1.sub.1, . . . , 1.sub.n. The values k.sub.0, . . . , k.sub.m are transmitted to the secure text generation part 12. The secure texts ([a.sub.i], [b.sub.i] and [c.sub.i]) are transmitted to the fragment generation part 13.

[0030] In step S121, the secure text generation part 12 generates the secure text [x.sub.i] of x.sub.i that satisfies x.sub.i=f(k.sub.i) for i=0, . . . , m, where f(x) is a random t-th order polynomial unknown to anyone. The random t-th order polynomial is a t-th order polynomial that has terms with randomly selected coefficients. The secure texts [x.sub.1], . . . , [x.sub.m] are transmitted to the fragment generation part 13. The secure text [x.sub.0] is transmitted to the output part 15.

[0031] More specifically, the secure text generation part 12 generates secure texts [x.sub.0], . . . , [x.sub.m], as follows. First, Formula (1) is calculated for i=0, . . . , t, and generates the secure texts [x.sub.0], . . . , [x.sub.t].

[x.sub.i]Rand( )(1)

[0032] Next, Formula (2) is calculated for i=t+1, . . . , m, and generates the secure texts [x.sub.t+1], . . . , [x.sub.m].

[00002]$\begin{array}{cc}\left[x_i\right]\underset{j=0}{\overset{t}{.Math.}}.Math..Math.{}_j^{}\left(k_i\right)\left[x_j\right].Math..Math.\mathrm{where}.Math..Math.{}_j^{}\left(x\right)=\underset{0it,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}& .Math..Math.\left(2\right)\end{array}$

[0033] In step S122, the secure text generation part 12 generates secure texts [y.sub.i] of y.sub.i that satisfies y.sub.i=g(k.sub.i) for i=0, . . . , m, as a random t-th order polynomial unknown to anyone. A method of generating secure texts [y.sub.0], . . . , [y.sub.m] may be performed in a manner analogous to that for secure texts [x.sub.0], . . . , [x.sub.m]. The secure texts [y.sub.1], . . . , [y.sub.m] are transmitted to the fragment generation part 13. The secure text [y.sub.0] is transmitted to the output part 15.

[0034] In step S131, the fragment generation part 13 calculates Formula (3) for i=1, . . . , m, and generates values .sub.i.

.sub.iReveal([x.sub.i][a.sub.i])(3)

[0035] In step S132, the fragment generation part 13 calculates Formula (4) for i=1, . . . , m, and generates values .sub.i.

.sub.iReveal([y.sub.i][b.sub.i])(4)

[0036] In step S133, the fragment generation part 13 calculates Formula (5) for i=1, . . . , m, and generates secure texts [z.sub.i]. The secure texts [z.sub.i], . . . , [z.sub.m] are transmitted to the random number synthesizing part 14.

[z.sub.i][c.sub.i]+.sub.i[b.sub.i]+.sub.i[a.sub.i]+.sub.i.sub.i(5)

[0037] In step S14, the random number synthesizing part 14 calculates Formula (6), and generates a secure text [z.sub.0]. The secure text [z.sub.0] is transmitted to the output part 15.

[00003]$\begin{array}{cc}\left[z_0\right]\underset{j=1}{\overset{2.Math.t+1}{.Math.}}.Math..Math.{}_j\left(k_0\right)\left[z_j\right].Math..Math.\mathrm{where}.Math..Math.{}_j\left(x\right)=\underset{1i2.Math.t+1,ij}{.Math.}.Math..Math.\frac{x-k_i}{k_j-k_i}& .Math..Math.\left(6\right)\end{array}$

[0038] In step S15, the output part 15 outputs the combination of secure text ([x.sub.0], [y.sub.0] and [z.sub.0]).

Second Embodiment

[0039] A secret random number synthesizing method according to a second embodiment is a method of generating a combination of secure texts of values a, b and c having a relationship c=ab in a case of secrecy through additive secret sharing. In this embodiment, secure texts [a.sub.i], [b.sub.i] and [c.sub.i] to be input, and secure texts [x.sub.i], [y.sub.i] and [z.sub.i] to be generated are secure texts through additive secret sharing. The additive secret sharing is described in Non-patent literature 2, for example.

[0040] In step S121, when the secure text generation part 12 of the second embodiment generates the secure texts [x.sub.i] for i=0, . . . , t, each party generates a random value, and adopts the random value as a share of the secure texts [x.sub.i]. In step S122, when the secure texts [y.sub.i] are generated for i=0, . . . , t, each party generates a random value, and adopts the random value as a share of the secure texts [y.sub.i].

[0041] According to the configuration as described above, the secret random number synthesizing technique of the present invention can create the secure texts ([x], [y] and [z]) of the combination of random values (x, y and z) that satisfy z=xy unknown to anyone even in a case where any t combinations among the secure texts ([a.sub.i], [b.sub.i] and [c.sub.i]) of the m(=2t+1) combinations of random values (a.sub.i, b.sub.i and c.sub.i) that satisfy c.sub.i=a.sub.ib.sub.i, have been leaked and are not expected to be known to anyone.

[0042] The point of the present invention is that multiplication of the secure texts of random values x.sub.0 and y.sub.0 are separated into (2t+1) multiplications. At this time, [x] and [y] are shared into (2t+1) secure texts using (t+1, 2t+1) threshold secret sharing. Accordingly, even if t combinations of pieces of information among (2t+1) combinations of secure texts have been leaked, none of x nor y can be revealed. As a result, the secure texts of combinations of random values unknown to anyone can be created.

[0043] The present invention is not limited to the embodiments described above. It is a matter of course that modification can be appropriately made in a scope without departing from the spirit of the present invention. The various types of processes described in the aforementioned embodiments can be executed in a time-series manner according to the order of description. Alternatively, such execution may be made in parallel or individually according to the processing capability of the device that executes the processes, as required.

[0044] [Program and Recording Medium]

[0045] In cases where the various processing functions in each device described in the above embodiments are implemented by a computer, the processing details of the functions to be included in each device are described as a program. The program is executed by the computer, thereby achieving the various processing functions in each device described above on the computer.

[0046] The program that describes the processing details can be recorded in a computer-readable recording medium. The computer-readable recording medium may be, for example, any recording medium, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory.

[0047] The program is distributed by, for example, selling, transferring, or lending a portable recording medium, such as DVD or CD-ROM, where the program is recorded. Alternatively, the program may be stored in a storing device of a server computer, and the program may be transferred from the server computer to another computer via a network, thereby distributing the program.

[0048] For example, the computer for executing such a program, first, stores the program recorded in the portable recording medium or transferred from the server computer, temporarily in its storing device. In execution of the process, the computer reads the program recorded in its recording medium, and executes the process according to the read program. According to another execution mode of this program, the computer may directly read the program from the portable recording medium, and execute the process according to the program. Further alternatively, every time the program is transferred to this computer from the server computer, the computer may successively execute the process according to the received program. Another configuration may be adopted that executes the process described above through a service of what is called an ASP (Application Service Provider) according to which the program is not transferred to this computer from the server computer, and the processing function is achieved only by an execution instruction therefor and acquisition of the result. The program according to this embodiment encompasses information that is provided for the process by the computer and conforms to the program (data and the like that are not direct instructions to the computer but have characteristics that define the process of the computer).

[0049] In this mode, this device is configured by executing a predetermined program on the computer. Alternatively, at least some of these processing details may be achieved as hardware.