JP7540599B2 - Secure computation system, secure computation device, secure computation method, and program - Google Patents

Description

The present invention relates to a secure computation system, a secure computation device, a secure computation method, and a program.

When two parties each have data, and they are considering an exchange to obtain some kind of calculation result from those two pieces of data, there are many well-researched techniques to minimize the information that each party obtains other than the calculation result, and these are called two-party secret computations.

を持っており（Ａ_１，Ａ_２，Ｂ_１，Ｂ_２は任意の集合）、それらの数値集合から計算される計算結果（関数値）ｆ_１，・・・，ｆ_ｎをＡのみが得て、それ以外の数値集合に関する情報を相手方にほとんど漏らさないような２パーティ秘密計算を考える。ただし、それらの関数値は、

(A ₁ , A ₂ , B ₁ , B ₂ are arbitrary sets), and only A can obtain the calculation results (function values) f ₁ , ..., f _n calculated from these numerical sets, and little information about the other numerical sets is leaked to the other party. However, these function values are

に対して、

In contrast,

と書けるものとする。このような計算ができると、例えば、パーティＡ、Ｂの両者が持っているデータベースを等結合して、それに付随するデータのクロス集計表を計算すること等が可能となる。

If such calculations can be performed, it will be possible to, for example, equally combine the databases held by parties A and B and calculate a cross-tabulation table of the associated data.

In order to realize the above-mentioned calculations, two patterns are known in the prior art: performing the calculations in a general circuit manner using secret circuits or fully homomorphic encryption (for example, Non-Patent Document 1), or using fully homomorphic encryption to utilize a protocol specialized for such applications (for example, Non-Patent Document 2).

Andrew Chi-Chih Yao: How to Generate and Exchange Secrets. FOCS 1986 Gentaro Katayama, Yutaka Yoshiura: Realization and Performance Comparison of Two-Party Private Cross-Tabulation with Anonymization Using Fully Homomorphic Encryption. Transactions of Information Processing Society of Japan, vol.61, No.6, 1175-1189 (June 2020)

However, calculations using general circuits are naturally very inefficient, and even specialized protocols are inefficient because they contain inefficient processing such as fully homomorphic calculations (i.e., homomorphic calculations that use both addition and multiplication).

One embodiment of the present invention has been made in consideration of the above points and aims to efficiently perform a specific two-party secure computation.

In order to achieve the above object, a secure computation system according to one embodiment includes a first secure computation device having a first numerical set X=(x _i,j ) (i∈A ₁ , j∈A ₂ ) and a second secure computation device having a second numerical set Y=(y _i,j ) (i∈B ₁ , j∈B ₂ ), in which the first secure computation device includes a first encryption unit that transmits a vector having elements which are ciphertexts obtained by encrypting elements of the A ₁ using commutative encryption to the second secure computation device, a second encryption unit that calculates a matrix T ₁ ' by permuting a matrix T ₁ having elements which are ciphertexts obtained by encrypting elements of the first numerical set X using additive homomorphic encryption based on the vector received from the second secure computation device, and transmits the matrix T ₁ ' to the second secure computation device, and a calculation result of the additive homomorphic computation received from the second secure computation device, and and a decryption unit that calculates a | _B2 |×| _A2 | matrix _whose (j', j) component is the sum of _i,j yi _,j' for _i∈A1∩B1 , and the second secure computing device has a third encryption unit that transmits a vector whose elements are ciphertexts obtained by encrypting the elements of _B1 using the commutative encryption to the first secure computing device, and a calculation unit that transmits to the first secure computing device a calculation result obtained by calculating, using the additive homomorphic calculation, the product of a transposed matrix of a matrix representing the second numerical set Y and a matrix Z obtained by replacing the rows of the matrix _T1 ' using a predetermined function.

It is possible to efficiently perform certain two-party secret computations.

1 is a diagram showing an example of the overall configuration of a secure computation system according to an embodiment of the present invention; FIG. 2 is a diagram illustrating an example of a hardware configuration of a secure computing device according to the present embodiment. FIG. 11 is a sequence diagram showing a two-party secure computation process in the first embodiment. FIG. 11 is a sequence diagram showing a two-party secure computation process in the second embodiment.

Hereinafter, one embodiment of the present invention will be described. In this embodiment, parties A and B each have a set of numerical values.

を持っており（Ａ_１，Ａ_２，Ｂ_１，Ｂ_２は任意の集合）、それらの数値集合から計算される計算結果（関数値）ｆ_１，・・・，ｆ_ｎをＡのみが得て、それ以外の数値集合に関する情報を相手方であるＢにほとんど漏らさないような２パーティ秘密計算を対象として、当該２パーティ秘密計算を効率的に実行することができる秘密計算システム１について説明する。ただし、それらの関数値は、

(A ₁ , A ₂ , B ₁ , B ₂ are arbitrary sets), and only A obtains the calculation results (function values) f ₁ , ..., f _n calculated from these numerical value sets, and information about other numerical value sets is hardly leaked to the other party B. The following describes a secure computation system 1 that can efficiently execute the two-party secure computation. However, these function values are

に対して、

In contrast,

と書けるものとする。なお、ｎは任意の自然数である。上述したように、このような計算ができると、例えば、パーティＡ、Ｂの両者が持っているデータベースを等結合して、それに付随するデータのクロス集計表を計算すること等が可能となる。

where n is any natural number. As mentioned above, if such calculations are possible, it will be possible to, for example, equally combine the databases held by parties A and B and calculate a cross-tabulation table of the associated data.

<Overall configuration of secure computation system 1>
The secure computation system 1 according to this embodiment includes a secure computation apparatus 10 and a secure computation apparatus 20. The secure computation apparatus 10 and the secure computation apparatus 20 are communicatively connected via a communication network N including, for example, the Internet.

The secure computing device 10 is a computer or computer system that functions as party A. For example, the secure computing device 10 is a database server or the like that functions as party A.

Here, the secure computing device 10 has a secure computing unit 101 and a communication unit 102. Each of these units is realized, for example, by a process in which one or more programs installed in the secure computing device 10 are executed by a processor such as a CPU (Central Processing Unit).

The secure computing device 10 also has a memory unit 103. The memory unit 103 is realized by an auxiliary storage device such as a hard disk drive (HDD) or a solid state drive (SSD).

The secure computation unit 101 performs two-party secure computation with the secure computation device 20, as described in the following embodiment 1 or 2, to obtain function values _f1 , ..., _fn . The communication unit 102 transmits and receives various information necessary for the two-party secure computation. The storage unit 103 stores a numerical value set X, and _A1 and _A2 .

The secure computing device 20 is a computer or computer system that functions as party B. For example, the secure computing device 20 is a database server or the like that functions as party B.

Here, the secure computing device 20 has a secure computing unit 201 and a communication unit 202. Each of these units is realized, for example, by a process in which one or more programs installed in the secure computing device 20 are executed by a processor such as a CPU.

The secure computing device 20 also has a memory unit 203. The memory unit 203 is realized, for example, by an auxiliary storage device such as a HDD or SSD.

The secure computation unit 201 performs two-party secure computation, which will be described in the following embodiment 1 or 2, with the secure computation device 10. The communication unit 202 transmits and receives various information necessary for the two-party secure computation. The storage unit 203 stores a set of numerical values Y, _B1 , and _B2 .

<Hardware Configuration of the Secure Computing Apparatuses 10 and 20>
The hardware configuration of the secure computing apparatuses 10 and 20 according to this embodiment is shown in Fig. 2. Note that since the secure computing apparatuses 10 and 20 can be realized with the same hardware configuration, the following mainly describes the hardware configuration of the secure computing apparatus 10.

2, the secure computing device 10 according to this embodiment is realized by the hardware configuration of a general computer or computer system, and has an input device 301, a display device 302, an external I/F 303, a communication I/F 304, a processor 305, and a memory device 306. Each of these pieces of hardware is connected to each other so as to be able to communicate with each other via a bus 307.

The input device 301 is, for example, a keyboard, a mouse, a touch panel, various physical buttons, etc. The display device 302 is, for example, a display, a display panel, etc. Note that the secure computing devices 10 and 20 may not have at least one of the input device 301 and the display device 302, for example.

The external I/F 303 is an interface with a recording medium 303a, etc. Examples of the recording medium 303a include a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 304 is an interface with the communication network N. The processor 305 is, for example, various arithmetic devices such as a CPU. The memory device 306 is, for example, various storage devices such as an HDD, SSD, flash memory, RAM (Random Access Memory), and ROM (Read Only Memory).

The secure computing devices 10 and 20 according to this embodiment have the hardware configuration shown in FIG. 2, and can realize various processes described below. Note that the hardware configuration shown in FIG. 2 is an example, and the secure computing devices 10 and 20 may have, for example, multiple processors 305, multiple memory devices 306, or various other hardware besides the hardware shown in FIG. 2. Also, while FIG. 2 describes a case where the hardware configurations of the secure computing device 10 and the secure computing device 20 are similar, the hardware configurations of the secure computing device 10 and the secure computing device 20 may be different.

Example 1
Example 1 will now be described.

<Preparation>
Let PK be the public key of additive homomorphic encryption and SK be the private key, aEnc(PK,·) be the encryption algorithm of additive homomorphic encryption, and aDec(SK,·) be the decryption algorithm of additive homomorphic encryption. In addition, additive homomorphic computation of ciphertexts _CT1 and _CT2 of additive homomorphic encryption is simply expressed additively as _CT1 + _CT2 .

Let s be the private key of the commutative encryption, and Enc(s,.) be the encryption algorithm of the commutative encryption. The commutative encryption is an encryption that has the following properties for any natural number k and k private keys s ₁ , ..., s _k . That is, the private key space is an Abelian group, and satisfies Enc(Πs _i ,m)=Enc(s _k ,Enc(s _k-1 ,...,Enc(s ₁ ,m))) (the right-hand side means that m is encrypted with s ₁ , which is then encrypted with s ₂ , which is then further encrypted with s ₃ , and this is repeated up to s _k ).

In the following, for any natural number k and plaintext set m = ( _m1 , ..., _mk ) ^T , the notation Enc(s, m) = (Enc(s, _m1 ), ..., Enc(s, _mk )) ^T is used. The same applies even if the plaintext set is a matrix. Note that T represents a transpose.

The i-th element of vector t is denoted as t[i].

<<Two-party secure computation process in the first embodiment>>
The two-party secure computation process in the first embodiment will be described with reference to FIG.

Step S101: The secure computing unit 101 of the secure computing device 10 randomly selects a private key a for the commutative encryption, and calculates t ₁ =Enc(a, A ₁ ).

Step S102: The communication unit 102 of the secure computing apparatus 10 transmits t ₁ to the secure computing apparatus 20.

Step S103: The secure computing unit 201 of the secure computing device 20 randomly selects a private key b of the commutative encryption, and calculates t ₂ =Enc(b, B ₁ ).

Step S104: The communication unit 202 of the secure computing apparatus 20 transmits t ₂ to the secure computing apparatus 10 .

Step S105: The secure computation unit 101 of the secure computation apparatus 10 calculates t ₃ =Enc(a, t ₂ ′) for t ₂ ′ obtained by randomly rearranging the elements of t ₂ .

Step S106: The communication unit 102 of the secure computing apparatus 10 transmits t ₃ to the secure computing apparatus 20.

Step S107: The secure computing unit 201 of the secure computing device 20 calculates _t4 = Enc(1/b, _t3 ) and sets _t5 = _t1 ∪ _t4 (at this time, the order of the elements of _t5 is such that the elements of _t1 arranged in order are concatenated with the elements of _t4 arranged in order excluding the elements that overlap with _t1 .) Next, the secure computing unit 201 of the secure computing device 20 randomly selects private keys c and d of the commutative cipher, and calculates _t6 = Enc(c, _t5 ) and _t7 = Enc(d, _B1 ).

Step S108: The communication unit 202 of the secure computing apparatus 20 transmits t ₆ and t ₇ to the secure computing apparatus 10.

Step S109: The secure computing unit 101 of the secure computing device 10 randomly selects a private key e for the commutative encryption and a public key and a private key (PK, SK) for the additive homomorphic encryption. Next, the secure computing unit 101 of the secure computing device 10 calculates t ₈ =Enc(e/a, t ₆ ) and obtains the following:

を計算する。ただし、Ｏはすべての成分が０である｜Ｂ_１＼Ａ_１｜×｜Ａ_２｜の行列とする。そして、秘密計算装置１０の秘密計算部１０１は、ｔ_８，Ｔ_１の行を共通のランダム置換で並べ替えたものをそれぞれｔ_８'，Ｔ_１'とする。また、秘密計算装置１０の秘密計算部１０１は、ｔ_９＝Ｅｎｃ（ｅ，ｔ_７）を計算する。

where O is a matrix of |B ₁ \ _{A 1} |×|A ₂ | with all components being 0. The secure computation unit 101 of the secure computation device 10 rearranges the rows of t ₈ and T ₁ by a common random permutation to obtain t ₈ ' and T ₁ ', respectively. The secure computation unit 101 of the secure computation device 10 also calculates t ₉ = Enc(e, t ₇ ).

Step S110: The communication unit 102 of the secure computing apparatus 10 transmits t ₈ ′, T ₁ ′, and t ₉ to the secure computing apparatus 20 .

Step S111: The secure computation unit 201 of the secure computation device 20 calculates v=Enc(1/c, _t8 ') and w=Enc(1/d, _t9 ). Next, the secure computation unit 201 of the secure computation device 20 sets φ to a function that satisfies w[i]=v[φ(i)], and sets Z to a matrix of | _B1 |×| _A2 |, the i-th row of which is the φ(i)-th row of _T1 '. Then, the secure computation unit 201 of the secure computation device 20 calculates _T2 = ^YTZ by additive homomorphic computation of additive homomorphic encryption.

Step S112: The communication unit 202 of the secure computing apparatus 20 transmits _T2 to the secure computing apparatus 10.

Step S113: The secure computing unit 101 of the secure computing device 10 decrypts aDec(SK, T ₂ ). The (j _B , j _A ) component of this decryption result is

に一致する。

Matches.

Example 2
Hereinafter, a description will be given of Example 2. Example 2 is an improved version of the protocol in Example 1, in which the amount of communication and the number of rounds are reduced.

<Preparation>
Let L = |B ₁ \A ₁ |. Although it is an abuse of notation, if a is included in an element of vector t, it is written as a∈t. Furthermore, let D be a set where D∩(A ₁ ∪B ₁ ) = φ (empty set). Note that for the rest, the same symbols and notations as in Example 1 are used.

<<Two-party secure computation process in the second embodiment>>
The two-party secure computation process in the second embodiment will be described with reference to FIG.

Step S201: The secure computing unit 101 of the secure computing device 10 randomly selects a private key a for the commutative encryption, and calculates t ₁ =Enc(a, A ₁ ).

Step S202: The communication unit 102 of the secure computing apparatus 10 transmits t ₁ to the secure computing apparatus 20 .

Step S203: The secure computation unit 201 of the secure computation device 20 randomly selects a private key b of the commutative cipher. Next, the secure computation unit 201 of the secure computation device 20 calculates _t2 = Enc(b, _t1 ') for _t1 ' obtained by randomly rearranging the elements of _t1 . In addition, the secure computation unit 201 of the secure computation device 20 calculates _t3 = Enc(b, _B1 ) and _t4 = Enc(b, D).

Step S204: The communication unit 202 of the secure computing apparatus 20 transmits t ₂ , t ₃ , and t ₄ to the secure computing apparatus 20 .

Step S205: The secure computing unit 101 of the secure computing apparatus 10 calculates t ₅ =Enc(1/a, t ₂ ), and calculates each element t ₆ [i] of t ₆ ={t ₆ [1], . . . , t ₆ [|B ₁ |]} as follows.

ただし、

however,

とする。次に、秘密計算装置１０の秘密計算部１０１は、可換暗号の秘密鍵ｃをランダムに選ぶと共に、加法準同型暗号の公開鍵、秘密鍵（ＰＫ，ＳＫ）をランダムに選ぶ。続いて、秘密計算装置１０の秘密計算部１０１は、ｔ_７＝Ｅｎｃ（ｃ，ｔ_６）とｔ_８＝Ｅｎｃ（ｃ，（Ａ_１，Ｄ［１］，・・・，Ｄ［Ｌ］））を計算すると共に、

Next, the secure computation unit 101 of the secure computation device 10 randomly selects a private key c for the commutative encryption and randomly selects a public key and a private key (PK, SK) for the additive homomorphic encryption. Next, the secure computation unit 101 of the secure computation device 10 calculates _t7 = Enc(c, _t6 ) and _t8 = Enc(c, ( _A1 , D[1], ..., D[L])), and

を計算する。ただし、Ｏはすべての成分が０である｜Ｂ_１＼Ａ_１｜×｜Ａ_２｜の行列とする。そして、秘密計算装置１０の秘密計算部１０１は、ｔ_８，Ｔ_１の行を共通のランダム置換で並べ替えたものをそれぞれｔ_８'，Ｔ_１'とする。

where O is a matrix |B ₁ \ _{A 1} |×|A ₂ | in which all components are 0. The secure computing unit 101 of the secure computing device 10 rearranges the rows of t ₈ and T ₁ by a common random permutation to obtain t ₈ ' and T ₁ ', respectively.

Step S206: The communication unit 102 of the secure computing apparatus 10 transmits t ₇ , t ₈ ′, and T ₁ ′ to the secure computing apparatus 20 .

Step S207: The secure computation unit 201 of the secure computation device 20 calculates v=t ₈ ' and w=Enc( ₁ /b, t ₇ ). Next, the secure computation unit 201 of the secure computation device 20 sets φ to a function that satisfies w[i]=v[φ(i)], and sets Z to a matrix of |B ₁ |×|A ₂ |, the i-th row of which is the φ(i)-th row of T 1 '. Then, the secure computation unit 201 of the secure computation device 20 calculates T ₂ =Y ^T Z by additive homomorphic computation of additive homomorphic encryption.

Step S208: The communication unit 202 of the secure computing apparatus 20 transmits _T2 to the secure computing apparatus 10.

Step S209: The secure computing unit 101 of the secure computing device 10 decrypts aDec(SK, T ₂ ). The (j _B , j _A ) component of this decryption result is

に一致する。

Matches.

<Summary>
As described above, in the secure computation system 1 in Examples 1 and 2, the function value shown in the above formula 6 (i.e., the function value representing an aggregate value between elements of the value set X and elements of the value set Y) is calculated by two-party secure computation from the value set X held by party A and the value set Y held by party B, and these function values can be obtained only by party A. Moreover, at this time, the function value is calculated using only additive homomorphic computation, which is an efficiently executable process, without using fully homomorphic computation, which is an inefficient process. This makes it possible to efficiently execute two-party secure computation for calculating the function value shown in the above formula 6.

As described above, if the function value shown in the above formula 6 can be calculated, it becomes possible, for example, to equally combine the databases held by both parties A and B and calculate a cross-tabulation table of the associated data. Therefore, the secure computing device 10 according to this embodiment may further calculate a cross-tabulation table and output it (including displaying, saving, transmitting to other devices, etc.).

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, variations, and combinations with known technologies are possible without departing from the scope of the claims.

REFERENCE SIGNS LIST 10 Secure computing device 20 Secure computing device 101 Secure computing unit 102 Communication unit 103 Storage unit 201 Secure computing unit 202 Communication unit 203 Storage unit 301 Input device 302 Display device 303 External I/F
303a Recording medium 304 Communication I/F
305 Processor 306 Memory device 307 Bus N Communication network

Claims (7)

A secure computation system including a first secure computation apparatus having a first set of numerical values X=(x _i,j ) (i∈A ₁ , j∈A ₂ ) and a second secure computation apparatus having a second set of numerical values Y=(y _i,j ) (i∈B ₁ , j∈B ₂ ),
The first secure computing device is
a first encryption unit that transmits a vector having elements that are ciphertexts obtained by encrypting elements of the _A1 using a commutative cipher to the second secure computing device;
a second encryption unit that calculates a matrix T 1 ′ by permuting a matrix T ₁ having elements that are ciphertexts obtained by encrypting elements of the first numerical set X by additive homomorphic encryption based on the vector received from the second secure computing device, and transmits the matrix T _{1 ′} to the second secure computing device;
a decryption unit which, upon receiving a calculation result of the additive homomorphic computation from the second secure computing device, decrypts the calculation result by the additive homomorphic encryption and calculates a |B ₂ |×|A ₂ | matrix having a (j',j) component that is the sum of x _i,j y _i,j' with respect to i∈A _{1 ∩B} 1,
The second secure computing device is
a third encryption unit that transmits a vector having elements that are ciphertexts obtained by encrypting elements of the _B1 using the commutative cipher to the first secure computing device;
a calculation unit that calculates, by the additive homomorphic calculation, a product of a transposed matrix of a matrix representing the second set of values Y and a matrix Z obtained by replacing rows of the matrix T ₁ ′ by a predetermined function, and transmits the result of the calculation to the first secure computing device;
A secure computing system having the above structure. The first encryption unit
A vector _t1 having elements that are ciphertexts obtained by encrypting the elements of _A1 using a commutative cipher is transmitted to the second secure computing device;
Upon receiving vector _t2 from the second secure computing device, calculate vector _t2 ' by rearranging elements of vector _t2 , and transmit vector _t3 having elements which are ciphertexts obtained by encrypting elements of vector _t2 ' by the commutative cipher to the second secure computing device;
The third encryption unit
A vector _t2 having elements that are ciphertexts obtained by encrypting the elements of _B1 using the commutative cipher is transmitted to the first secure computing device;
upon receiving vector _t3 from the first secure computing device, calculate vector t4 having elements which are ciphertext obtained by encrypting elements of vector _t3 using the commutative cipher, calculate vector _t5 having elements of vector _t1 and elements of vector _t4 , and transmit vector _t6 having elements which are ciphertext obtained by encrypting elements of vector _t5 using the commutative cipher and vector _t7 having elements which are ciphertext obtained by encrypting _elements of _B1 using the commutative cipher to the first secure computing device;
The second encryption unit
Upon receiving the vector _t6 and the vector _t7 from the second secure computing device, calculate a vector _t8 having elements which are ciphertext obtained by encrypting the elements of the vector _t6 using the commutative cipher, and the matrix _T1 , and transmit to the second secure computing device vector _t8 ' and matrix _T1 ' which are obtained by rearranging the rows of the vector _t8 and the matrix _T1 using a common random permutation, respectively, and vector _t9 having elements which are ciphertext obtained by encrypting the elements of the vector _t7 using the commutative cipher,
The calculation unit is
The secure computation system of claim 1, wherein, upon receiving the vector _t8 ', the matrix _T1 ', and the vector _t9 from the first secure computation device, a vector v having elements which are ciphertext obtained by encrypting the elements of the vector _t8 ' using the commutative encryption and a vector w having elements which are ciphertext obtained by encrypting the elements of the vector _t9 using the commutative encryption are calculated, the matrix Z whose i-th row becomes the φ(i)-th row of the matrix _T1 ' is calculated using a function φ that makes the i-th element v[i] of the vector v equal to the φ(i)-th element w[φ(i)] of the vector w, and the product of the transposed matrix and the matrix Z is calculated using the additive homomorphic computation. The first encryption unit
A vector _t1 having elements that are ciphertexts obtained by encrypting the elements of _A1 using a commutative cipher is transmitted to the second secure computing device;
The second encryption unit
upon receiving vector _t2 , vector _t3 , and vector _t4 from the second secure computing device, calculate vector t5 having elements which are ciphertexts obtained by encrypting elements of vector _t2 using the commutative encryption, calculate _{vector t6 from} vector _t3 and vector _t4 based on the relationship between vector t3 and vector _t5 , calculate vector _t7 having elements which are ciphertexts obtained by encrypting elements of vector _t6 using the commutative encryption, calculate vector _t8 having elements which are ciphertexts obtained by encrypting elements of _A1 and elements of set D which satisfies D∩( _A1∪B1 )=φ using the _commutative encryption, and calculate matrix _T1 , and transmit vector _t8 ' and matrix _T1 ' obtained by rearranging rows of vector _t8 and matrix _{T1 ,} respectively, using a common random permutation, and vector _t7 to the second secure computing device;
The third encryption unit
upon receiving the vector _t1 from the first secure computing device, calculate a vector _t1 ' by randomly rearranging the elements of the vector _t1 , and transmit to the first secure computing device a vector _t2 having elements which are ciphertexts obtained by encrypting the elements of the vector _t1 ' using the commutative cipher, a vector _t3 having elements which are ciphertexts obtained by encrypting the elements of the B1 using the commutative cipher, and a vector _t4 having elements which are ciphertexts obtained _by encrypting the elements of the D using the commutative cipher,
The calculation unit is
The secure computing system of claim 1, wherein when the vector _t8 ', the matrix _T1 ', and the vector _t7 are received from the first secure computing device, the vector _t8 ' is set as vector v, and a vector w whose elements are ciphertext obtained by encrypting the elements of the vector _t7 using the commutative encryption is calculated, the matrix Z whose i-th row becomes the φ(i)-th row of the matrix _T1 ' is calculated using a function φ that makes the i-th element v[i] of the vector v equal to the φ(i)-th element w[φ(i)] of the vector w, and the product of the transposed matrix and the matrix Z is calculated using the additive homomorphic computation. A secure computing device having a numerical value set X=(x i _,j )(i∈A ₁ , j∈A ₂ ) and connected to another secure computing device capable of communicating with the other secure computing device having a numerical value set Y=(y _i,j )(i∈B ₁ , j∈B ₂ ),
a first encryption unit that transmits a vector having elements that are ciphertexts obtained by encrypting elements of the _A1 using a commutative cipher to the other secure computing device;
a second encryption unit that calculates a matrix T ₁ ′ by replacing a matrix T ₁ having elements that are ciphertexts obtained by encrypting elements of the numerical set X by additive homomorphic encryption based on the vector received from the other secure computing device, and transmits the matrix T ₁ ′ to the other secure computing device;
and a decryption unit that, when receiving a calculation result of an additive homomorphic calculation from the other secure computing device, decrypts the calculation result by the additive homomorphic encryption and calculates a |B ₂ |×|A ₂ | matrix having a (j', j) component that is the sum of x _i,j y _i,j' with respect to i∈A ₁ ∩B ₁ . A secure computing device having a numerical value set Y=( _yi,j ) ( _i∈B1 , _j∈B2 ) and connected to another secure computing device capable of communicating with the other secure computing device having a numerical value set X=(xi _,j ) ( _i∈A1 , _j∈A2 ),
an encryption unit that transmits a vector having an element that is a ciphertext obtained by encrypting an element of the _B1 by a commutative cipher to the other secure computing device;
a calculation unit that, upon receiving a matrix _T1 ' obtained by permuting a matrix T1 having elements that are ciphertext obtained by encrypting elements of the value set X using additive homomorphic encryption, calculates the product of a transposed matrix of a matrix representing the value set Y and a matrix Z obtained by permuting rows of _the matrix _T1 ' using a predetermined function using additive homomorphic calculation of the additive homomorphic encryption;
A secure computing device having the above configuration. A secure computation method for use in a secure computation system including a first secure computation device having a first set of numerical values X=(x _i,j ) (i∈A ₁ , j∈A ₂ ) and a second secure computation device having a second set of numerical values Y=(y _i,j ) (i∈B ₁ , j∈B ₂ ),
The first secure computing device,
a first encryption step of transmitting a vector having elements each of which is a ciphertext obtained by encrypting elements of the _A1 using a commutative cipher to the second secure computing device;
a second encryption step of calculating a matrix T 1 ′ by replacing a matrix T ₁ having elements each of which is a ciphertext obtained by encrypting elements of the first numerical set X by additive homomorphic encryption based on the vector received from the second secure computing device, and transmitting the matrix T _{1 ′} to the second secure computing device;
a decryption step of receiving a calculation result of the additive homomorphic computation from the second secure computing device, decrypting the calculation result by the additive homomorphic encryption, and calculating a |B ₂ |×|A ₂ | matrix having a (j',j) component that is the sum of x _i,j y _i,j' with respect to i∈A ₁ ∩B ₁ ;
The second secure computing device,
a third encryption step of transmitting a vector having elements each of which is a ciphertext obtained by encrypting an element of the _B1 by the commutative cipher to the first secure computing device;
a calculation step of calculating, by the additive homomorphic calculation, a product of a transposed matrix of a matrix representing the second set of values Y and a matrix Z obtained by replacing rows of the matrix T ₁ ′ by a predetermined function, and transmitting the result of the calculation to the first secure computing device;
A secret computation method for performing A program that causes a computer to function as a first secure computing device or a second secure computing device included in the secure computing system described in any one of claims 1 to 3.

Images