Patent Description:
Secure computation is a cryptographic technique of calculating an arbitrary function while data is concealed. Taking advantage of this feature, a data utilization form that does not leak data to both system operators and data users is expected. There are several methods for secure computation, and among them, it is known that ones that use secret sharing as a component have a small data processing unit and can perform high-speed processing.

Secret sharing is a method for converting confidential information into several fragments called shares. For example, there is secret sharing called a (k, n) threshold value method by which n shares are generated from confidential information, and secret can be restored from k or more shares, but the confidential information is not leaked from less than k shares. As specific configuration methods of secret sharing, methods such as Shamir secret sharing and duplicate secret sharing are known. In the present specification, one fragment of a value distributed by secret sharing is referred to as a "share. " Also, an entire set of all shares is referred to as a "value that has been distributed" or "distributed value.

Right shift computation is one of basic computations on a computer or the like, and is used at various situations. For example, right shift computation can be used as computation that reduces numerical accuracy. In addition, division when a divisor is powers of two can be achieved by right shift computation. Non-patent literature <NUM> discloses a method for performing shift computation on an integer ring whose order is powers of two in secure computation.

Non-patent literature <NUM>: <NPL>. Additional relevant prior art is disclosed in "<NPL>.

However, since the method disclosed in Non-patent literature <NUM> can be used only on an integer ring whose order is powers of two, there is a problem in which an overflow will occur and calculation cannot be performed if computation that increases numerical accuracy such as multiplication on the field is repeated.

An objective of the present invention is to provide a secure computation technique that achieves high-speed right shift computation and division in view of the above technical problems.

Optional features are defined by the dependent claims. In order to solve the above problems, a secure right shift computation system of a first aspect of the present invention is a secure right shift computation system comprising m secure computation apparatuses, taking an input of a distributed value [a] of a value "a" and a shift amount "b," and calculating a distributed value [a>>b] of a value obtained by shifting the value "a" by "b" bits toward right, wherein [·] is a distributed value obtained by distributing a value ". " by first secret sharing, <·> is a distributed value obtained by distributing the value ". " by additive secret sharing, {·} is a distributed value obtained by distributing a bit expression of the value "·," the distributed value [·] and the distributed value <·> can be mutually converted, "a" is an arbitrary value, "b" is a shift amount, "m" is a distribution number of three or more, "u" is an integer of log m or more, "<NUM>" is a bit number of the value "a," and >> is a right shift operator, and wherein the secure computation apparatuses each include: a public value multiplication part that calculates a distributed value [a']=[<NUM>ua] by using the distributed value [a]; a first conversion part that converts the distributed value [a'] into a distributed value <a'>=<a'><NUM>,. , <a'>m-<NUM> of the additive secret sharing; a right shift computation part that, for each integer i of <NUM> or more and less than m, generates a distributed value =<NUM>,. , m-<NUM> by calculating i=<a'>i>>b+u; a second conversion part that converts the distributed value  into a distributed value [s] of the first secret sharing; a first bit conversion part that converts lower u bits of a share <a'>i of the distributed value <a'> into a distributed value {a'i mod <NUM>u} of a bit expression for each integer i of <NUM> or more and less than m; a quotient transfer part that calculates lower u bits of - Σi<m{a'i mod <NUM>u} to obtain as a distributed value {q} of a bit expression by using the distributed value {a'i mod <NUM>u}; a third conversion part that converts the distributed value {q} into a distributed value [q] of the first secret sharing; and an output computation part that calculates [s]-[<NUM><NUM>-(b+u)q]+<NUM> to obtain as the distributed value [a>>b] by using the distributed values [s] and [q].

In order to solve the above problems, a secure division system of a second aspect of the present invention is a secure division system comprising three secure computation apparatuses, taking an input of a distributed value [a] of a dividend "a" and a divisor "d," and calculating a distributed value [a/d] of a division result a/d in which the dividend "a" is divided by the divisor "d" and a fractional part is truncated, wherein "p" is a prime number, [·] is a distributed value obtained by distributing a value ". " by first secret sharing with three shares, <·> is a distributed value obtained by distributing the value ". " by additive secret sharing with two shares, the distributed value [·] and the distributed value <·> can be mutually converted, "a" is a dividend, "d" is a divisor, and / is an operator that represents division in which a fractional part is truncated, and wherein the secure computation apparatuses each include: an input conversion part that converts the distributed value [a] into a distributed value <a>=<a><NUM>, <a><NUM> of the additive secret sharing; a public value multiplication part that calculates a distributed value <a'>=<2a> and a value d'=2d by using the distributed value [a] and the divisor "d"; a quotient transfer part that obtains a distributed value <q> of a quotient "q" where a value a' is divided by the prime number p, by using the distributed value <a'>; a public division part that obtains a quotient p' and a residual r' where the prime number p is divided by the value d'; an approximation part that calculates <b><NUM>=(<a'><NUM>+d'-<NUM>-r')/d' and <b><NUM>=<a'><NUM>/d', to generate a distributed value <b>=<b><NUM>, <b><NUM> by using the distributed value <a'>, the value d', and the residual r'; an output computation part that calculates <b>-(p'+<NUM>)<q>+<NUM> to obtain as a distributed value <a/d> of the division result a/d by using the distributed values <b> and <q> and the quotient p'; and an output conversion part that converts the distributed value <a/d> into the distributed value [a/d] of the first secret sharing.

In order to solve the above problems, a secure division system of a third aspect of the present invention is a secure division system comprising m secure computation apparatuses, taking an input of a distributed value [a] of a dividend "a" and a divisor "d," and calculating a distributed value [a/d] of a division result a/d in which the dividend "a" is divided by the divisor "d" and a fractional part is truncated, wherein p is a prime number, [·] is a distributed value obtained by distributing a value ". " by first secret sharing with m shares, <·> is a distributed value obtained by distributing the value ". " by additive secret sharing with m shares, the distributed value [·] and the distributed value <·> can be mutually converted, "a" is a dividend, "d" is a divisor, "m" is a distribution number of three or more, "u" is an integer of log m or more, and / is an operator that represents division in which a fractional part is truncated, and wherein the secure computation apparatuses each include: an input conversion part that converts the distributed value [a] into a distributed value <a>=<a><NUM>,. , <a>m-<NUM> of the additive secret sharing; a public value multiplication part that calculates a distributed value <a'>=<<NUM>ua> and a value d'=<NUM>ud by using the distributed value [a] and the divisor "d"; a quotient transfer part that obtains a distributed value <q> of a quotient "q" where a value a' is divided by the prime number p, by using the distributed value <a'>; a public division part that obtains a quotient p' and a residual r' where the prime number p is divided by the value d'; a flag setting part that obtains a flag z in which z=<NUM> is set if r'≥d'/<NUM>, and z=<NUM> is set if r'<d'/<NUM>; an approximation part that generates a distributed value <b>=<b><NUM>,. , <b>m-<NUM>, for each integer i of <NUM> or more and less than m, by calculating <b>i=(<a'>i+(d'-r')+(d'-r')/<NUM>)/d' if i=<NUM> and calculating <b>i=<a'>i/d' if i≠<NUM>; a rounding processing part that obtains a distributed value <b'>=<b'><NUM>,. , <b'>m-<NUM>, for each integer i of <NUM> or more and less than m, by calculating <b'>i=<p"> if a quotient p" and a residual r" obtained by dividing a share <b>i of the distributed value <b> by the value d' satisfy r"≤d'/<NUM>-<NUM> and calculating <b'>i=<p"+<NUM>> if r"≥d'/<NUM>; an output computation part that calculates <b'>-(p'+z)<q>-<NUM> to obtain as a distributed value <a/d> of the division result a/d by using the distributed values <b'> and <q>, the quotient p', and the flag z; and an output conversion part that converts the distributed value <a/d> into the distributed value [a/d] of the first secret sharing.

According to the secure computation technique of the present invention, it is possible to achieve high-speed right shift computation and division in secure computation.

In the drawings, configuration parts having the same functions are given the same numbers, and duplicate explanations are omitted. If a base of log is omitted in mathematical formulas and the like, the base is two.

A first embodiment of the present invention is a secure right shift computation system and method that shift a number to be shifted toward the right by a given shift amount and output the shifted number while concealing the number to be shifted, which is a right shift target. An outline of a right shift protocol executed by the secure right shift computation system of the first embodiment will be described below. This protocol is a protocol on a Mersenne prime field. The Mersenne prime field is an important structure used in secret sharing-based secure computation (see Reference literature <NUM>). [Reference literature <NUM>] <NPL>.

Right shift is integer division, but not a ring operation consisting of addition and multiplication. First, general integer division in Theorem <NUM> and right shift in its System <NUM> are expressed by a ring operation using a quotient "q" of additive secret sharing. The quotient "q" can be efficiently calculated by quotient transfer (see Reference literature <NUM>). [Reference literature <NUM>]<NPL>.

It is assumed that there are shares a<NUM>,. , am-<NUM> that satisfy a=Σi<mai mod p, where an arbitrary distribution number m∈N, a prime number p∈N, a divisor d∈N, and a dividend aeR. Here, for each i, non-negative integers aiQ and aiR are a quotient and a residual where ai is divided by d, respectively, non-negative integers pQ and pR are a quotient and a residual where p is divided by d, respectively, a non-negative integer q is a quotient where Σi<mai is divided by p, and zQ is a quotient where Σi<maiR+q(d-pR) is divided by d. Then, a quotient aQ where "a" is divided by d is expressed by the following Formula (<NUM>).

From the assumption a=Σi<mai mod p, "a" is a residual where Σi<mai is divided by p. From the assumption "q is a quotient where Σi<mai is divided by p," Σi<mai=qp+a. Since ai=aiQd+aiR and p=pQd+pR from the assumption, <MAT> Further assuming that yQ is a quotient where Σi<maiR-qpR is divided by d, then <MAT> On the other hand, since zQ is a quotient where Σi<maiR+q(d-pR) is divided by d, yQ=zQ-q.

In Theorem <NUM>, it is assumed that a prime bit length leN is arbitrary and a shift bit number beN is b≤l, and the prime number p=<NUM><NUM>-<NUM> and the divisor d=<NUM>b. Then, z'Q is a quotient where Σi<maiR+q is divided by <NUM>b, and aQ is expressed by the following Formula (<NUM>).

It only needs to substitute p=<NUM><NUM>-<NUM> and d=<NUM>b in Formula (<NUM>).

It is assumed that, for an arbitrary distribution number m∈N and a Mersenne prime p, u∈N satisfies log m≤u, and a<NUM>,. , am-<NUM> ∈Zp satisfies Σi<mai mod <NUM>u=<NUM>. At this time, if q is a quotient where Σi<mai is divided by p, q is expressed by the following Formula (<NUM>).

A right shift protocol executed in the embodiment is shown below. The protocol is calculated according to Formula (<NUM>) in System <NUM>. Here, the following notation is used.

In duplicate secret sharing, a share held by each party is composed of a plurality of elements called "sub-shares" and elements having the same values are shared by a plurality of parties. The sub-shares are also handled as shares.

All of the mutual conversion of additive secret sharing including linear secret sharing and duplicate secret sharing used in the above protocol, the bit composition, and the sharing of each bit of duplicate secret sharing are described in Reference literature <NUM> above.

A secure right shift computation system <NUM> of the first embodiment executes the above-described Algorithm <NUM>: right shift protocol on integer ring Zp. The secure right shift computation system <NUM> includes m (≥<NUM>) secure computation apparatuses <NUM><NUM>,. , <NUM>m as shown in <FIG>. In the embodiment, the secure computation apparatuses <NUM><NUM>,. , <NUM>m are each connected to a communication network <NUM>. The communication network <NUM> is a circuitswitched or packet-switched communication network configured so that connected apparatuses can communicate with each other, and, for example, the Internet, a LAN (Local Area Network), and a WAN (Wide Area Network) can be used. Note that each apparatus does not necessarily need to be able to communicate online via the communication network <NUM>. For example, information to be input into the secure computation apparatus <NUM>i (i=<NUM>,. , m) may be stored on a portable recording medium, such as a magnetic tape or a USB memory, and may be input from the portable recording medium into the secure computation apparatus <NUM>i offline.

The secure computation apparatus <NUM>i (i=<NUM>,. , m) included in the secure right shift computation system of the first embodiment includes, for example, as shown in <FIG>, a public value multiplication part <NUM>, a first conversion part <NUM>, a right shift computation part <NUM>, a second conversion part <NUM>, a first bit conversion part <NUM>, a quotient transfer part <NUM>, a second bit conversion part <NUM>, an addition part <NUM>, a third conversion part <NUM>, and an output computation part <NUM>. The secure computation apparatus <NUM>i performs processing of below-described steps while cooperating with another secure computation apparatus <NUM>i' (i'=<NUM>,. , m, however, i≠i'), and thereby the secure right shift computation method of the first embodiment is implemented.

The secure computation apparatus <NUM>i is a special apparatus configured by loading a special program into a known or dedicated computer including, for example, a central processing unit (CPU) and a main memory (RAM: Random Access Memory). The secure computation apparatus <NUM>i performs each process, for example, under control of the central processing unit. Data input into the secure computation apparatus <NUM>i and data obtained in each process are stored, for example, in the main memory, and the data stored in the main memory is read out to the central processing unit as needed and used for another process. Each processing part of the secure computation apparatus <NUM>i may be at least partially composed of hardware such as integrated circuits.

A processing procedure of the secure right shift computation method executed by the secure right shift computation system <NUM> of the first embodiment will be described with reference to <FIG>.

In step S11, the public value multiplication part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a] of a number to be shifted "a" input into the secure computation apparatus <NUM>i, and calculates [a']=[<NUM>ua] by public value multiplication. Here, "u" is an integer of log m or more, and "m" is a distribution number of additive secret sharing. The "u" and "m" are parameters given beforehand. The public value multiplication part <NUM> inputs the calculated distributed value [a'] into the first conversion part <NUM>.

In step S12, the first conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a'] from the public value multiplication part <NUM>, and converts the distributed value [a'] into a distributed value <a'>=<a'><NUM>,. , <a'>m-<NUM> of additive secret sharing. The first conversion part <NUM> inputs the converted distributed value <a'> into the right shift computation part <NUM>, the first bit conversion part <NUM>, and the second bit conversion part <NUM>.

In step S13, the right shift computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> from the first conversion part <NUM>, calculates i=<a'>i>>b+u, and obtains a distributed value . Here, >> is a right shift operator. The right shift computation part <NUM> inputs the calculated distributed value  into the second conversion part <NUM>.

In step S14, the second conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value  from the right shift computation part <NUM>, and converts the distributed value  into linear secret sharing. The second conversion part <NUM> inputs the converted distributed value [s] into the output computation part <NUM>.

In step S15, the first bit conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> from the first conversion part <NUM>, distributes lower u bits of the share <a'>i of the distributed value <a'>, and obtains a distributed value {a'i mod <NUM>u}, which is a bit expression of <a'>i mod <NUM>u. The first bit conversion part <NUM> inputs the distributed value {a'i mod <NUM>u} into the quotient transfer part <NUM>.

In step S16, the quotient transfer part <NUM> of each secure computation apparatus <NUM>i receives the distributed value {a'i mod <NUM>u} from the first bit conversion part <NUM>, and calculates lower u bits of -Σi<m{a'i mod <NUM>u} by the addition circuit and the sign inversion circuit. A bit sequence of a calculation result is set as a distributed value {q} of a quotient "q. " The quotient transfer part <NUM> inputs the distributed value {q} into the addition part <NUM> and the third conversion part <NUM>.

In step S17, the second bit conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> from the first conversion part <NUM>, distributes lower b+u bits of the share <a'>i of the distributed value <a'>, and obtains a distributed value {a'iR}, which is a bit expression of <a'>i mod <NUM>b+u. The second bit conversion part <NUM> inputs the distributed value {a'iR} into the addition part <NUM>.

In step S18, the addition part <NUM> of each secure computation apparatus <NUM>i receives the distributed value {q} from the quotient transfer part <NUM> and the distributed value {a'iR} from the second bit conversion part <NUM>, and calculates {z}=Σi<m{a'iR}+{q} by the addition circuit. A bit sequence of a (b+u)-th bit (<NUM> start) and after of the bit sequence {z} of a calculation result is set as a distributed value {zQ}. The addition part <NUM> inputs the distributed value {zQ} into the third conversion part <NUM>.

In step S19, the third conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value {q} from the quotient transfer part <NUM> and the distributed value {zQ} from the addition part <NUM>, and converts {q} and {zQ} into linear secret sharing by bit composition. The third conversion part <NUM> inputs the converted distributed values [q] and [zQ] into the output computation part <NUM>.

In step S20, the output computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [s] from the second conversion part <NUM> and the distributed values [q] and [zQ] from the third conversion part <NUM>, calculates [s]-[<NUM><NUM>-(b+u)q]+[zQ], and outputs as a distributed value [a>>b] of a value a»b, which is obtained by shifting the number to be shifted "a" by the "b" bits toward the right.

Communication traffic and the number of rounds of the right shift protocol are evaluated. A coefficient is considered but a constant term is ignored. Since the value of "u" is assumed to be as small as one for passive and two for even active, evaluation is performed regarding "u" as a constant.

The communication traffic is as follows. The number of transmission bits per party is used as units. The conversion from linear secret sharing into additive secret sharing requires <NUM>, the conversion from additive secret sharing into linear secret sharing requires "I," the distribution of lower b+u bits requires "b," the addition circuit requires "b," the sign inversion circuit requires <NUM>, the bit composition requires "<NUM>" twice per one time, and the total is expressed as <NUM>+2b using the prime bit length "<NUM>" and the shift amount "b.

The number of rounds is as follows. The addition circuit requires b rounds, others are constant rounds, and the total is b rounds.

In the secure right shift computation system of the first embodiment, the second bit conversion part <NUM> and the addition part <NUM> have performed processing of approximating an error of the lower bits generated by right shift computation. However, the error that can be approximated is an error in a range that can be ignored in numerical calculation. Since a computation amount of the addition circuit is large in secure computation, by ignoring the error (that is, omitting the approximation processing), faster right shift computation can be achieved. A right shift protocol executed in a second embodiment is shown below.

A secure right shift computation system <NUM> of the second embodiment executes the above-described Algorithm <NUM>: high-speed right shift protocol. A secure computation apparatus <NUM>i (i=<NUM>,. , m) included in the secure right shift computation system <NUM> of the second embodiment includes, for example, as shown in <FIG>, a public value multiplication part <NUM>, a first conversion part <NUM>, a right shift computation part <NUM>, a second conversion part <NUM>, a first bit conversion part <NUM>, a quotient transfer part <NUM>, a third conversion part <NUM>, and an output computation part <NUM>. That is, the second bit conversion part <NUM> and the addition part <NUM> included in the secure computation apparatus <NUM>i (i=<NUM>,. , m) of the first embodiment are not included. The secure computation apparatus <NUM>i performs processing of below-described steps while cooperating with another secure computation apparatus <NUM>i' (i'=<NUM>,. , m, however, i≠i'), and thereby a secure right shift computation method of the second embodiment is implemented.

A processing procedure of the secure right shift computation method executed by the secure right shift computation system <NUM> of the second embodiment will be described with reference to <FIG>.

In step S11, the public value multiplication part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a] of a number to be shifted "a" input into the secure computation apparatus <NUM>i, and calculates [a']=[<NUM>ua] by public value multiplication. The public value multiplication part <NUM> inputs the calculated distributed value [a'] into the first conversion part <NUM>.

In step S12, the first conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a'] from the public value multiplication part <NUM>, and converts the distributed value [a'] into a distributed value <a'>=<a'><NUM>,. , <a'>m-<NUM> of additive secret sharing. The first conversion part <NUM> inputs the converted distributed value <a'> into the right shift computation part <NUM> and the first bit conversion part <NUM>.

In step S13, the right shift computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> from the first conversion part <NUM>, calculates i=<a'>i>>b+u, and obtains a distributed value . The right shift computation part <NUM> inputs the calculated distributed value  into the second conversion part <NUM>.

In step S15, the first bit conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> from the first conversion part <NUM>, distributes lower u bits of a share <a'>i of the distributed value <a'>, and obtains a distributed value {a'i mod <NUM>u}, which is a bit expression of <a'>i mod <NUM>u. The first bit conversion part <NUM> inputs the distributed value {a'i mod <NUM>u} into the quotient transfer part <NUM>.

In step S16, the quotient transfer part <NUM> of each secure computation apparatus <NUM>i receives the distributed value {a'i mod <NUM>u} from the first bit conversion part <NUM>, and calculates lower u bits of -Σi<m{a'i mod <NUM>u} by the addition circuit and the sign inversion circuit. A bit sequence of a calculation result is set as a distributed value {q} of a quotient "q. " The quotient transfer part <NUM> inputs the distributed value {q} into the third conversion part <NUM>.

In step S19, the third conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value {q} from the quotient transfer part <NUM>, and converts {q} into linear secret sharing by bit composition. The third conversion part <NUM> inputs the converted distributed value [q] into the output computation part <NUM>.

In step S20, the output computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [s] from the second conversion part <NUM> and the distributed value [q] from the third conversion part <NUM>, calculates [s]-[<NUM><NUM>-(b+u)q]+<NUM>, and outputs as a distributed value [a>>b] of a value a»b, which is obtained by shifting the number to be shifted "a" by the "b" bits toward the right.

Right shift computation can be regarded as division by powers of two. Therefore, in a third embodiment, extension to division by other than powers of two is considered. In the same manner as the shift amount is public in the right shift computation, a divisor is made a public value. In the third embodiment, it is assumed to use additive secret sharing in which the number of shares is two. That is, additive secret sharing used in internal processing is (<NUM>, <NUM>) additive secret sharing, and secret sharing that is a form of input/output is (<NUM>, <NUM>) linear secret sharing. A divisor public division protocol executed in the embodiment is shown below.

A secure division system <NUM> of the third embodiment executes the above-described Algorithm <NUM>: divisor public division protocol. The secure division system <NUM> includes three secure computation apparatuses <NUM><NUM>, <NUM><NUM>, and <NUM><NUM> as shown in <FIG>. In the embodiment, the secure computation apparatuses <NUM><NUM>, <NUM><NUM>, and <NUM><NUM> are each connected to a communication network <NUM>.

The secure computation apparatus <NUM>i (i=<NUM>,. , <NUM>) included in the secure division system <NUM> of the third embodiment includes, for example, as shown in <FIG>, an input conversion part <NUM>, a public value multiplication part <NUM>, a quotient transfer part <NUM>, a public division part <NUM>, an approximation part <NUM>, an output computation part <NUM>, and an output conversion part <NUM>. The secure computation apparatus <NUM>i performs processing of below-described steps while cooperating with another secure computation apparatus <NUM>i' (i'=<NUM>,. , <NUM>, however, i≠i'), and thereby a secure division method of the third embodiment is implemented.

A processing procedure of the secure division method executed by the secure division system <NUM> of the third embodiment will be described with reference to <FIG>.

In step S31, the input conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a] of a dividend "a" input into the secure computation apparatus <NUM>i, and converts the distributed value [a] into a distributed value <a>=<a><NUM>, <a><NUM> of (<NUM>, <NUM>) additive secret sharing. The input conversion part <NUM> inputs the converted distributed value <a> into the public value multiplication part <NUM>.

In step S32, the public value multiplication part <NUM> of each secure computation apparatus <NUM>i receives the divisor d input into the secure computation apparatus <NUM>i and the distributed value <a> input from the input conversion part <NUM>, and calculates <a'>=<2a> and d'=2d by public value multiplication. The public value multiplication part <NUM> inputs the calculated distributed value <a'> and value d' into the quotient transfer part <NUM> and the approximation part <NUM>. Also, the public value multiplication part <NUM> inputs the value d' into the public division part <NUM>.

In step S33, the quotient transfer part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> and the value d' from the public value multiplication part <NUM>, and obtains a distributed value <q> of a quotient "q" where the value a' is divided by a modulus "p" by quotient transfer or the like. Specifically, the processing performed by the first bit conversion part <NUM>, the quotient transfer part <NUM>, and the third conversion part <NUM> of the first embodiment should be executed. That is, the quotient transfer part <NUM> distributes lower u bits of the share <a'>i of the distributed value <a'>, obtains a distributed value {a'i mod <NUM>u}, which is a bit expression of <a'>i mod <NUM>u, calculates lower u bits of -Σi<m{a'i mod <NUM>u} by an addition circuit and a sign inversion circuit, sets a bit sequence of a calculation result as a distributed value {q} of the quotient "q," and converts {q} into the distributed value <q> by bit composition. The quotient transfer part <NUM> inputs the distributed value <q> into the output computation part <NUM>.

In step S34, the public division part <NUM> of each secure computation apparatus <NUM>i receives the value d' from the public value multiplication part <NUM> and obtains a quotient p' and a residual r' where the modulus "p" is divided by the value d'. The public division part <NUM> inputs the residual r' into the approximation part <NUM>. Also, the public division part <NUM> inputs the quotient p' into the output computation part <NUM>.

In step S35, the approximation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> and the value d' from the public value multiplication part <NUM> and the residual r' from the public division part <NUM>, and calculates the following formula. <MAT> That is, if i=<NUM>, <b>i=(<a'>i+d'-<NUM>-r')/d' is calculated, and otherwise, <b>i=<a'>i/d' is calculated, and a distributed value <b> is obtained. The approximation part <NUM> inputs the distributed value <b> into the output computation part <NUM>.

In step S36, the output computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <q> from the quotient transfer part <NUM>, the quotient p' from the public division part <NUM>, and the distributed value <b> from the approximation part <NUM>, and calculates <b>-(p'+<NUM>)<q>+<NUM>. The output computation part <NUM> inputs a calculation result as a distributed value <a/d> of a/d into the output conversion part <NUM>.

In step S37, the output conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a/d> from the output computation part <NUM> and converts the distributed value <a/d> into (<NUM>, <NUM>) linear secret sharing. The output conversion part <NUM> outputs the converted distributed value [a/d].

Algorithm <NUM> satisfies the following three properties. This is ideal as integer division for fixed-point numbers for numerical calculation with stochastic output. Note that / and ÷ are both operators representing division, but / is division in which the fractional part is truncated, whereas ÷ is real number division.

Algorithm <NUM>: Communication traffic and the number of rounds of divisor public division protocol are evaluated. The communication traffic is <NUM>/<NUM>(|p|+<NUM>) bits. The number of rounds is two rounds. Divisor public division that satisfies both communication traffic O(|p|) and the number of rounds O(<NUM>) has not existed until now. A constant coefficient is as extremely small as two or less, and it can be said it is especially effective in applications that process a large volume of right shift (that is, division of powers of two) for repeating operations, for example, machine learning.

In the third embodiment, it has been assumed that the additive secret sharing with two shares is used. In a fourth embodiment, it is generalized to additive secret sharing with three or more shares or duplicate secret sharing. A divisor public division protocol executed in the embodiment is shown below.

A secure division system <NUM> of the fourth embodiment executes the above-described Algorithm <NUM>: divisor public division protocol. The secure division system <NUM> includes m (≥<NUM>) secure computation apparatuses <NUM><NUM>,. , <NUM>m as shown in <FIG>. In the embodiment, the secure computation apparatuses <NUM><NUM>,. , <NUM>m are each connected to a communication network <NUM>.

The secure computation apparatus <NUM>i (i=<NUM>,. , m) included in the secure division system <NUM> of the fourth embodiment includes, for example, as shown in <FIG>, an input conversion part <NUM>, a public value multiplication part <NUM>, a quotient transfer part <NUM>, a public division part <NUM>, an approximation part <NUM>, an output computation part <NUM>, an output conversion part <NUM>, a flag setting part <NUM>, and a rounding processing part <NUM>. That is, in addition to the processing parts included in the secure computation apparatus <NUM>i (i=<NUM>,. , <NUM>) of the third embodiment, the flag setting part <NUM> and the rounding processing part <NUM> are further included. The secure computation apparatus <NUM>i performs processing of below-described steps while cooperating with another secure computation apparatus <NUM>i' (i'=<NUM>,. , m, however, i≠i'), and thereby a secure division method of the fourth embodiment is implemented.

A processing procedure of the secure division method executed by the secure division system <NUM> of the fourth embodiment will be described focusing on differences from the third embodiment with reference to <FIG>.

In step S31, the input conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value [a] of a dividend "a" input into the secure computation apparatus <NUM>i, and converts the distributed value [a] into a distributed value <a>=<a><NUM>,. , <a>m-<NUM> of the additive secret sharing with m shares or the duplicate secret sharing. The input conversion part <NUM> inputs the converted distributed value <a> into the public value multiplication part <NUM>.

In step S32, the public value multiplication part <NUM> of each secure computation apparatus <NUM>i receives the divisor d input into the secure computation apparatus <NUM>i and the distributed value <a> input from the input conversion part <NUM>, and calculates <a'>=<<NUM>ua> and d'=<NUM>ud by public value multiplication. The public value multiplication part <NUM> inputs the calculated distributed value <a'> and value d' into the quotient transfer part <NUM> and the approximation part <NUM>. Also, the public value multiplication part <NUM> inputs the value d' into the public division part <NUM> and the rounding processing part <NUM>.

In step S38, the flag setting part <NUM> of each secure computation apparatus <NUM>i receives the residual r' from the public division part <NUM>, and sets z=<NUM> if r'≥d'/<NUM> and z=<NUM> otherwise. The flag setting part <NUM> inputs the set flag z into the output computation part <NUM>.

In step S35, the approximation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a'> and the value d' from the public value multiplication part <NUM> and the residual r' from the public division part <NUM>, and calculates the following formula. <MAT> That is, if i=<NUM>, <b>i=(<a'>i+(d'-r')+(d'-r')/<NUM>)/d' is calculated, and otherwise, <b>i=<a'>i/d' is calculated, and a distributed value <b> is obtained. The approximation part <NUM> inputs the distributed value <b> into the rounding processing part <NUM>.

In step S39, the rounding processing part <NUM> of each secure computation apparatus <NUM>i receives the value d' from the public value multiplication part <NUM> and the distributed value <b> from the approximation part <NUM>, calculates <b'>i=<p"> if a quotient p" and a residual r" obtained by dividing <b>i by d' satisfy r"≤d'/<NUM>-<NUM>, and calculates <b'>i=<p"+<NUM>> if r"≥d'/<NUM> to obtain <b'>. The rounding processing part <NUM> inputs the distributed value <b'> into the output computation part <NUM>.

In step S36, the output computation part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <q> from the quotient transfer part <NUM>, the quotient p' from the public division part <NUM>, the flag z from the flag setting part <NUM>, and the distributed value <b'> from the rounding processing part <NUM>, and calculates <b'>-(p'+z)<q>-<NUM>. The output computation part <NUM> inputs a calculation result as a distributed value <a/d> of a/d to the output conversion part <NUM>.

In step S37, the output conversion part <NUM> of each secure computation apparatus <NUM>i receives the distributed value <a/d> from the output computation part <NUM> and converts the distributed value <a/d> into linear secret sharing with m shares. The output conversion part <NUM> outputs the converted distributed value [a/d].

In the third embodiment and the fourth embodiment, it has been assumed that a general integer without a sign is used for the divisor d. In a fifth embodiment, it is assumed that the divisor d is an integer with a sign. A division protocol executed in the embodiment is shown below.

A secure division system of the fifth embodiment executes the above-described Algorithm <NUM>: divisor public division protocol. The secure division system of the fifth embodiment includes a plurality of secure computation apparatuses in the same manner as the third embodiment or the fourth embodiment, and each secure computation apparatus includes the same processing parts as those of the third embodiment or the fourth embodiment.

The input conversion part <NUM> of each secure computation apparatus receives the divisor d input into the secure computation apparatus, divides <NUM>|p|-<NUM> by d, and rounds up to obtain a number "w. " The distributed value [a] of the dividend "a" input into the secure computation apparatus is updated with [wd+a]. Then, the updated distributed value [a] is converted into the distributed value <a> of predetermined additive secret sharing. The input conversion part <NUM> inputs the converted distributed value <a> into the public value multiplication part <NUM>.

The output conversion part <NUM> of each secure computation apparatus receives a distributed value <a/d> from the output computation part <NUM> and converts the distributed value <a/d> into predetermined linear secret sharing. Since the input conversion part <NUM> has updated [a] with [wd+a], the distributed value [a/d] is actually [(wd+a)/d] (=[w+a/d]). Therefore, the output conversion part <NUM> subtracts "w" from the converted distributed value [a/d]. The output conversion part <NUM> outputs the subtracted distributed value [a/d].

The embodiments of the present invention have been described above, but specific configurations are not limited to those embodiments, and it goes without saying that even if there is a change or the like in design as appropriate without departing from the scope of the present invention, they are included in the present invention. The various processes described in the embodiments may be performed not only in chronological order according to the described order, but also in parallel or individually according to processing capacity of apparatuses that execute the processes or as needed.

When various processing functions in each apparatus described in the embodiments are implemented by a computer, processing contents of functions which each apparatus should have are described by a program. Then, the program is executed by the computer, and thereby the various processing functions in each apparatus are implemented on the computer.

The program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any recording medium, for example, a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory.

Distribution of this program is carried out, for example, by selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. Furthermore, the program may be stored in a storage device of a server computer, transferred from the server computer to another computer via a network, and thereby distributed.

A computer that executes such a program, for example, first stores the program recorded on the portable recording medium or the program transferred from the server computer temporarily in its own storage device. Then, when executing processing, the computer reads the program stored in its own storage device and performs the processing according to the read program. As another execution form of the program, the computer may directly read the program from the portable recording medium and perform the processing according to the program, or further may sequentially perform processing according to a received program every time the program is transferred from the server computer to the computer. In addition, the program is not transferred from the server computer to the computer, and the above-described processing may be executed by a so-called ASP (Application Service Provider) type service that implements a processing function only by execution instructions and result acquisition. Note that the program in this form includes information which is used for processing by the computer and is similar to the program (data or the like that is not a direct command to the computer but has properties that define processing of the computer).

Claim 1:
A secure division system comprising three secure computation apparatuses, taking an input of a distributed value [a] of a dividend "a" and a divisor "d," and calculating a distributed value [a/d] of a division result a/d in which the dividend "a" is divided by the divisor "d" and a fractional part is truncated,
wherein "p" is a prime number, [·] is a distributed value obtained by distributing a value "." by first secret sharing with three shares, <·> is a distributed value obtained by distributing the value "-" by additive secret sharing with two shares, the distributed value [·] and the distributed value <·> can be mutually converted, "a" is a dividend, "d" is a divisor, and / is an operator that represents division in which a fractional part is truncated, and
wherein the secure computation apparatuses each include:
an input conversion part that converts the distributed value [a] into a distributed value <a>=<a><NUM>, <a><NUM> of the additive secret sharing;
a public value multiplication part that calculates a distributed value <a'>=<2a> and a value d'=2d by using the distributed value [a] and the divisor "d";
a quotient transfer part that obtains a distributed value <q> of a quotient "q" where a value a' is divided by the prime number p, by using the distributed value <a'>;
a public division part that obtains a quotient p' and a residual r' where the prime number p is divided by the value d';
an approximation part that calculates <b><NUM>=(<a'><NUM>+d'-<NUM>-r')/d' and <b><NUM>=<a'><NUM>/d', to generate a distributed value <b>=<b><NUM>, <b><NUM> by using the distributed value <a'>, the value d', and the residual r';
an output computation part that calculates <b>-(p'+<NUM>)<q>+<NUM> to obtain as a distributed value <a/d> of the division result a/d by using the distributed values <b> and <q> and the quotient p'; and
an output conversion part that converts the distributed value <a/d> into the distributed value [a/d] of the first secret sharing.