SECURE DIVISION SYSTEM, SECURE COMPUTATION APPARATUS, SECURE DIVISION METHOD, AND PROGRAM

Abstract

Division is realized with a small number of processing stages. A secure computation apparatus (1) obtains a secret value representing a result of divided N by D using a secret value [N] of a real number N and a secret value [D] of a natural number D. An initialization unit (12) sets a secret value [P.sub.L1] of a partial remainder P.sub.L1 to 0. A parallel comparison unit (13) computes secret values [E.sub.1], . . . , [E.sub.R−1] of comparison results E.sub.1, . . . , E.sub.R−1 of comparing a secret value [n] of a partial divisor n=P.sub.j+1R+N.sub.j with [D]×g for each integer g not less than 1 and less than R in parallel. An update unit (14) computes a secret value [Q.sub.j] of a quotient Q.sub.j and a secret value [P.sub.j] of a partial remainder P.sub.j that satisfy n=DQ.sub.j+P.sub.j using the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1. An iterative control unit (15) executes the parallel comparison unit (13) and the update unit (14) for each integer j from L.sub.1−1 to −L.sub.0.

Claims

1. A secure division system comprising a plurality of secure computation apparatuses and for obtaining a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L.sub.0 and L.sub.1 are non-negative integers, N is a real number not less than 0 and less than R.sup.L1, D is a natural number, N.sub.−L0, . . . , N.sub.L1−1 are values of respective digits from an L.sub.0th digit after the decimal point to an L.sub.1th digit of an integer part in R notation of N, and j is each integer from L.sub.1−1 to −L.sub.0, each secure computation apparatus comprising processing circuitry configured to: set a secret value [P.sub.L1] of a partial remainder P.sub.L1 to 0; compute secret values [E.sub.1], . . . , [E.sub.R−1] of comparison results E.sub.1, . . . , E.sub.R−1 of comparing a secret value [n] of a partial divisor n=P.sub.j+1R+N.sub.j with [D]×g for each integer g not less than 1 and less than R in parallel; and compute a secret value [Q.sub.j] of a quotient Q.sub.j and a secret value [P.sub.j] of a partial remainder P.sub.j that satisfy n=DQ.sub.j+P.sub.j using the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1.

2. The secure division system according to claim 1, wherein the processing circuitry is configured to compute a secret value [E.sub.g] of a comparison result E.sub.g for g by the following formula: $\begin{array}{cc}\left[E_g\right]=\left(\left[D\right]\times g\stackrel{?}{\le }\left[n\right]\right).& \left[\mathrm{Math}.7\right]\end{array}$

3. The secure division system according to claim 1, wherein the processing circuitry is configured to compute the secret value [Q.sub.j] of the quotient Q.sub.j by the following formula: $\begin{array}{cc}\left[Q_j\right]:=\left[E_1\right]+\mathrm{.Math.}+\left[E_{R-1}\right]& \left[\mathrm{Math}.8\right]\end{array}$ and compute the secret value [P.sub.j] of the partial remainder P.sub.j by the following formula: $\begin{array}{cc}\left[P_j\right]:=\left[n\right]-\left[D\right]\times \left[Q_j\right].& \left[\mathrm{Math}.9\right]\end{array}$

4. A secure computation apparatus for use in a secure division system that obtains a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L.sub.0 and L.sub.1 are non-negative integers, N is a real number not less than 0 and less than R.sup.L1, D is a natural number, N.sub.−L0, . . . , N.sub.L1−1 are values of respective digits from an L.sub.0th digit after the decimal point to an L.sub.1th digit of an integer part in R notation of N, and j is each integer from L.sub.1−1 to −L.sub.0, the apparatus comprising processing circuitry configured to: set a secret value [P.sub.L1] of a partial remainder P.sub.L1 to 0; compute secret values [E.sub.1], . . . , [E.sub.R−1] of comparison results E.sub.1, . . . , E.sub.R−1 of comparing a secret value [n] of a partial divisor n=P.sub.j+1R+N.sub.j with [D]×g for each integer g not less than 1 and less than R in parallel; and compute a secret value [Q.sub.j] of a quotient Q.sub.j and a secret value [P.sub.j] of a partial remainder P.sub.j that satisfy n=DQ.sub.j+P.sub.j using the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1.

5. A secure division method for execution by a secure division system comprising a plurality of secure computation apparatuses and for obtaining a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L.sub.0 and L.sub.1 are non-negative integers, N is a real number not less than 0 and less than R.sup.L1, D is a natural number, N.sub.−L0, . . . , N.sub.L1−1 are values of respective digits from an L.sub.0th digit after the decimal point to an L.sub.1th digit of an integer part in R notation of N, and j is each integer from L.sub.1−1 to −L.sub.0, the secure division method comprising: setting a secret value [P.sub.L1] of a partial remainder P.sub.L1 to 0 with processing circuitry of each secure computation apparatus; computing secret values [E.sub.1], . . . , [E.sub.R−1] of comparison results E.sub.1, . . . , E.sub.R−1 of comparing a secret value [n] of a partial divisor n=P.sub.j+1R+N.sub.j with [D]×g for each integer g not less than 1 and less than R in parallel with the processing circuitry of each secure computation apparatus; and computing a secret value [Q.sub.j] of a quotient Q.sub.j and a secret value [P.sub.j] of a partial remainder P.sub.j that satisfy n=DQ.sub.j+P.sub.j using the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1 with the processing circuitry of each secure computation apparatus.

6. A non-transitory computer-readable recording medium on which a program is recorded for causing a computer to function as the secure computation apparatus according to claim 4.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0010] FIG. 1 is a diagram illustrating a functional configuration of a secure division 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 division method.

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

DESCRIPTION OF EMBODIMENTS

[0014] Firstly, the notation method and a definition of terminology in this specification will be described.

[0015] <Notation Method>

[0016] A value obtained by securing a given value a through encryption, secret sharing or the like will be called a secret value of a, and will be notated as [a]. In the case of the value a being secured through secret sharing, a set of fragments of secret sharing that are held by secure computation apparatuses will be referenced by [a].

[0017] [a,b] (square brackets) in the definition range of variables represents a closed interval, and (a,b) (round brackets) represents an open interval. For example, i∈[a,b] represents i taking a value not less than a and not more than b. Also, i∈[a,b) represents i taking a value not less than a and less than b.

[0018] <Addition, Subtraction, Multiplication>

[0019] Addition, subtraction and multiplication operations on a secure sentence compute secret values [c.sub.1], [c.sub.2] and [c.sub.3] of the respective computation results c.sub.1, c.sub.2 and c.sub.3 of a+b, a−b and ab, with secret values [a] and [b] of the two values a and b as inputs. Execution of these operations is respectively described as in the following formulas.

[00001]$\begin{array}{cc}\left[c_1\right]\leftarrow \mathrm{Add}\left(\left[a\right],\left[b\right]\right),\left[c_2\right]\leftarrow \mathrm{Sub}\left(\left[a\right],\left[b\right]\right),\left[c_3\right]\leftarrow \mathrm{Mul}\left(\left[a\right],\left[b\right]\right)& \left[\mathrm{Math}.1\right]\end{array}$

[0020] If there is no risk of misunderstanding, Add([a],[b]), Sub([a],[b]) and Mul([a],[b]) may be respectively abbreviated to [a]+[b], [a]−[b] and [a]×[b].

[0021] <Comparison>

[0022] A comparison operation computes a secret value [c] of a Boolean value c∈{0,1}, with secret values [a] and [b] of the two values a and b as inputs, where alb. The Boolean value takes 1 when true and 0 when false. Execution of this operation is described as in the following formula.

[00002]$\begin{array}{cc}\left[c\right]\leftarrow \left(\left[a\right]\stackrel{?}{\le }\left[b\right]\right)& \left[\mathrm{Math}.2\right]\end{array}$

[0023] Hereinafter, embodiments of this invention will be described in detail. Note that, in the drawings, constituent elements having the same function will be given the same numerals, and redundant description thereof will be omitted.

Embodiments

[0024] A secure division system of an embodiment computes and outputs secret values [Q.sub.−L0], . . . , [Q.sub.L1−1] of values Q.sub.−L0, . . . , Q.sub.L1−1 of respective digits from an L.sub.0th digit after the decimal point to an L.sub.1th digit of an integer part in R notation of N/D, with a secret value [N] of a dividend N and a secret value [D] of a divisor D as inputs. Here, R is an integer not less than 3, L.sub.0 and L.sub.1 are non-negative integers, N is a real number not less than 0 and less than R.sup.L1, and D is a natural number. Note that [N.sub.−L0], . . . , [N.sub.−L0+1], . . . , [N.sub.L1−2], [N.sub.L1−1] that are used throughout the embodiment are secret values of N.sub.−L0, N.sub.−L0+1, . . . , N.sub.L1−2, N.sub.L1−1 representing R decomposition of N such as in the following formula.

[00003]$\begin{array}{cc}{N}_{-L_0},N_{-L_0+1},\mathrm{.Math.},N_{L_1-2},N_{L_{1-1}}s.t.N={.Math.}_{j\in \left[-L_0,L_1\right)}{N}_j{R}^j+r,0\le r<R^{-L_0},N_j\in \left[0,R\right)& \left[\mathrm{Math}.3\right]\end{array}$

[0025] An example configuration of the secure division system of the embodiment will be described, with reference to FIG. 1. A secure division system 100 includes, for example, K (≥2) secure computation apparatuses 1.sub.1, . . . , 1.sub.K, as shown in FIG. 1. In the present embodiment, the secure computation apparatuses 1.sub.1, . . . , 1.sub.K are each connected to a communication network 9. The communication network 9 is a circuit switching or packet switching communication network configured such that connected apparatuses can communicate with each other, and the Internet, a LAN (Local Area Network), a WAN (Wide Area Network) or other such networks can be used, for example. Note that it is not necessarily required for the apparatuses to be able to communicate online via the communication network 9. For example, a configuration may be adopted in which information to be input to the secure computation apparatuses 1.sub.1, . . . , 1.sub.K is stored on a portable recording medium such as magnetic tape or a USB memory, and is input offline to the secure computation apparatuses 1.sub.1, . . . , 1.sub.K from the portable recording medium.

[0026] An example configuration of a secure computation apparatus 1.sub.k (k=1, . . . , K) included in the secure division system 100 of the embodiment will be described, with reference to FIG. 2. The secure computation apparatus 1.sub.k includes, for example, an input unit 11, an initialization unit 12, a parallel comparison unit 13, an update unit 14, an iterative control unit 15 and an output unit 16, as shown in FIG. 2. A secure division method of the present embodiment is realized by this secure computation apparatus 1.sub.k (k=1, . . . , K) performing the processing of steps described later in cooperation with another secure computation apparatus 1.sub.k. (k′=1, . . . , K, where k≠k′).

[0027] The secure computation apparatus 1.sub.k is a special apparatus constituted by a special program being loaded on a known or dedicated computer having a central processing unit (CPU), a main storage device (RAM: Random Access Memory) and other such constituent elements. The secure computation apparatus 1.sub.k executes various processing under the control of the central processing unit, for example. Data input to the secure computation apparatus 1.sub.k and data obtained by the various processing is, for example, stored on the main storage device, and the data stored on the main storage device is read out to the central processing unit as needed and utilized in other processing. At least some of the processing units of the secure computation apparatus 1.sub.k may be constituted by hardware such as an integrated circuit.

[0028] A processing procedure of the secure division method that is executed by the secure division system 100 of the embodiment will be described, with reference to FIG. 3.

[0029] In step S11, the secret value [N] of the dividend N and the secret value [D] of the divisor D are input to the input unit 11 of each secure computation apparatus 1.sub.k. Secret values [N.sub.−L0], . . . , [N.sub.L1−1] of N.sub.−L0 N.sub.−L0+1, . . . , N.sub.L1−2, N.sub.L1−1 representing R decomposition of the dividend N may be input to the input unit 11, instead of the secret value [N] of the dividend N. In the case where the secret value [N] of the dividend N is input to the input unit 11, the input unit 11 generates the secret values [N.sub.−L0], . . . , [N.sub.L1−1] of N.sub.−L0, N.sub.−L0+1, . . . , N.sub.L1−2, N.sub.L1−1 representing R decomposition of the dividend N from the secret value [N] of the dividend N. The input unit 11 outputs the secret values [N.sub.−L0], . . . , [N.sub.L1−1] of N.sub.−L0, N.sub.−L0+1, . . . , N.sub.L1−2, N.sub.L1−1 representing R decomposition of the dividend N and the secret value [D] of the divisor D to the parallel comparison unit 13.

[0030] In step S12, the initialization unit 12 of each secure computation apparatus 1.sub.k initializes a secret value [P.sub.L1] of a partial remainder P.sub.L1 to [P.sub.L1]=0. Also, an index j of iterative processing is initialized to j=L.sub.1−1. The initialization unit 12 outputs the secret value [P.sub.L1] of the partial remainder P.sub.L1 to the parallel comparison unit 13. Also, the index j is output to the iterative control unit 15.

[0031] In step S13, the parallel comparison unit 13 of each secure computation apparatus 1.sub.k computes a secret value [E.sub.g] (g∈[1,R)) of a result of comparing a secret value [n] of a partial devisor n where n=P.sub.j+1R+N.sub.j with each [D]×g where g∈[1,R) in parallel. Specifically, the parallel comparison unit 13 computes the secret value [E.sub.g] of the comparison result E.sub.g for each integer g not less than 1 and less than R by the following formula. The parallel comparison unit 13 outputs the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1 to the update unit 14.

[00004]$\begin{array}{cc}\left[E_g\right]=\left(\left[D\right]\times g\stackrel{?}{\le }\left[n\right]\right)\mathrm{for}g\in \left[1,R\right)& \left[\mathrm{Math}.4\right]\end{array}$

[0032] In step S14, the update unit 14 of each secure computation apparatus 1.sub.k computes a secret value [Q.sub.j] of a quotient Q.sub.j and a secret value [P.sub.j] of a partial remainder P.sub.j, using the secret values [E.sub.1], . . . , [E.sub.R−1] of the comparison results E.sub.1, . . . , E.sub.R−1. Note that Q.sub.j and P.sub.j satisfy n=DQ.sub.j+P.sub.j, Q.sub.j∈[0,R) and P.sub.j∈[0,R). Specifically, the update unit 14 computes the secret value [Q.sub.j] of the quotient Q.sub.j and the secret value [P.sub.j] of the partial remainder P.sub.j by the following formula. The update unit 14 outputs the secret value [Q.sub.j] of the quotient Q.sub.j and the secret value [P.sub.j] of the partial remainder P.sub.j to the output unit 16.

[00005]$\begin{array}{cc}\left[Q_j\right]:=\left[E_1\right]+\mathrm{.Math.}+\left[E_{R-1}\right],\left[P_j\right]:=\left[n\right]-\left[D\right]\times \left[Q_j\right]& \left[\mathrm{Math}.5\right]\end{array}$

[0033] In step S15-1, the iterative control unit 15 of each secure computation unit 1.sub.k determines whether j is not more than −L.sub.0, that is, the truth of j≤−L.sub.0. If j≤−L.sub.0 is false, that is, if j>−L.sub.0, the processing is advanced to step S15-2. If j≤−L.sub.0 is true, the processing is advanced to step S16. In step S15-2, the iterative control unit 15 of each secure computation apparatus 1.sub.k decrements j, that is, computes j=j−1, and returns the processing to step S13. In other words, the iterative control unit 15 performs control for repeatedly executing the parallel comparison unit 13 and the update unit 14 for each j where j=L.sub.1−1, . . . , −L.sub.0.

[0034] In step S16, the output unit 16 of each secure computation apparatus 1.sub.k outputs the secret values [Q.sub.−L0], . . . , [Q.sub.L1−1] of the quotients Q.sub.−L0, . . . , Q.sub.L1−1.

[0035] An algorithm that is executed in the abovementioned embodiment is shown below.

[00006]$\begin{array}{cc}1.\left[P_{L_1}\right]=02.\mathrm{for}j=L_{1-1}\mathrm{to}-L_0\mathrm{do}\left(a\right)\left[n\right]:=\left[P_{j+1}\right]\times R+\left[N_j\right]\left(b\right)\left[E_g\right]=\left(\left[D\right]\times g\stackrel{?}{\le }\left[n\right]\right)\mathrm{for}g\in \left[1,R\right)\left(c\right)\left[Q_j\right]:=\left[E_1\right]+\mathrm{.Math.}+\left[E_{R-1}\right],\left[P_j\right]:=\left[n\right]-\left[D\right]\times \left[Q_j\right]& \left[\mathrm{Math}.6\right]\end{array}$

[0036] With the configuration of the abovementioned embodiment, division can be realized by comparison of L.sub.0+L.sub.1 stages. Since one division requires a small number of stages, execution time is shortened, particularly when repeatedly executing division in series.

[0037] The case where R=2 in the abovementioned embodiment is equivalent to computing division in bit units. Division that is computed in bit units requires a large number of stages of comparison. In the abovementioned embodiment, even though the number of comparisons increases by approximately (R−1)/(log.sub.2R) times compared with division that is computed in bit units, the number of stages can be reduced by approximately 1/(log.sub.2R) times.

[0038] Although embodiments of this invention have been described above, the specific configuration is not limited to these embodiments, and appropriate design modifications or other such changes that do not depart from the spirit of this invention are intended to be included in the invention. The various types of processing described in the embodiments may be executed not only chronologically in the order of description but in parallel or individually according to the processing capacity of the apparatus that executes the processing or as needed.

[0039] [Program, Recording Medium]

[0040] In the case where the various types of processing functions in the apparatuses described in the abovementioned embodiments are executed by a computer, the processing contents of the functions that would be provided in the respective apparatuses will be described with a program. By loading this program on a storage unit 1020 of the computer shown in FIG. 4 and operating a control unit 1010, an input unit 1030, an output unit 1040 and other such constituent elements, the various types of processing functions of the abovementioned apparatuses will be realized on the computer.

[0041] This program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may, for example, be a magnetic recording device, an optical disc, a magneto-optical recording medium, a semiconductor memory or other such medium.

[0042] Also, distribution of this program is carried out by a portable recording medium such as DVD, CD-ROM or other such medium on which the program is recorded being sold, transferred, rented and the like. Furthermore, a configuration may also be adopted in which this program is distributed by storing the program on a storage device of a server computer, and transferring the program to other computers from the server computer via a network.

[0043] The computer that executes such a program first initially stores the program recorded on the portable recording medium or the program transferred from the server computer on a storage device thereof, for example. At the time of executing processing, this computer reads the program stored on the storage device thereof, and executes processing in accordance with the read program. Also, as other execution modes of this program, a configuration may be adopted in which the computer reads the program directly from the portable recording medium and executes processing in accordance with the read program, and, furthermore, whenever a program is transferred to this computer from the server computer, sequentially executes processing in accordance with the received program. Also, a configuration may be adopted in which the abovementioned processing is executed by a so-called ASP (Application Service Provider) service that realizes the processing functions with only an execution instruction and result acquisition from the server computer, without a program being transferred to the computer. Note that a computer program in the present embodiment is assumed to include any information that is to be processed by an electronic computer equivalent to a computer program (data, etc. that is not a direct set of instructions given to a computer but has the quality of defining processing by a computer).

[0044] Also, in this embodiment, the apparatus is configured by executing a prescribed program on a computer, but at least part of the processing contents thereof may be realized in a hardware manner.