JP7691400B2 - Encryption device, encryption method, and encryption program - Google Patents

Description

The present invention relates to a fully homomorphic computation system using lattice cryptography with multiple distributed keys.

Threshold Fully Homomorphic Encryption (ThFHE) is an extended version of FHE for use by multiple users. The configuration of ThFHE is described in, for example, Non-Patent Documents 1 and 2.
Here, the LWE encryption is a basic encryption method for constructing ThFHE, and can be configured as both a common key encryption and a public key encryption.

Gilad Asharov, Abhishek Jain, Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. "Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE". In: EUROCRYPT 2012. Springer, 2012, pp. 483-501. Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. "Threshold Cryptosystems from Threshold Fully Homomorphic Encryption". In: CRYPTO 2018. Springer, 2018, pp. 565-596.

Although LWE encryption can be configured as either a symmetric key encryption or a public key encryption, public key encryption has a larger noise in the ciphertext than symmetric key encryption, so it is necessary to set the ciphertext size (modulus q) relatively large. For this reason, in FHE, since the user who is the data sender has a private key, it is common to use a lighter symmetric key encryption type encryption algorithm.
On the other hand, ThFHE, due to its configuration, can only use public key encryption algorithms, and therefore has the problem that the ciphertext size is larger than that of common key encryption algorithms.

The present invention aims to provide an encryption device, encryption method, and encryption program that can reduce the size of ciphertext in a fully homomorphic computation system based on lattice cryptography using multiple distributed keys.

The encryption device according to the present invention includes a key generation unit that generates an encryption key by removing random components and noise components corresponding to the distributed private keys held by the device from a master public key in a lattice cryptography corresponding to a plurality of distributed private keys, and a ciphertext generation unit that generates a ciphertext by adding random components and noise components of a common key cryptography type based on the distributed private keys held by the device to a public key cryptography type ciphertext based on the encryption key.

The lattice cryptography may be a threshold fully homomorphic encryption method.

The encryption method according to the present invention executes a key generation step in which an encryption device generates an encryption key by removing random components and noise components corresponding to the distributed private keys held by the device from a master public key in a lattice cryptography corresponding to a plurality of distributed private keys, and a ciphertext generation step in which a ciphertext is generated by adding random components and noise components of a common key cryptography type based on the distributed private keys held by the device to a public key cryptography type ciphertext based on the encryption key.

The encryption program according to the present invention is for causing a computer to function as the encryption device.

According to the present invention, it is possible to reduce the size of ciphertext in a fully homomorphic computation system based on lattice cryptography using multiple distributed keys.

FIG. 2 is a diagram illustrating a functional configuration of an encryption device according to an embodiment. FIG. 11 is a diagram showing the magnitude of noise on a ciphertext in the embodiment in comparison with a conventional method. FIG. 1 is a diagram showing the configuration of a secure computation system in which multiple users participate, using a conventional ThFHE.

An example of an embodiment of the present invention will now be described.
In the encryption method of this embodiment, ThFHE is improved as an example of a fully homomorphic encryption method, but the method is not limited to this and can also be applied to other encryption algorithms that use lattice cryptography to configure a fully homomorphic computing system.

[ThFHE algorithm]
First, for comparison with this embodiment, the configuration of a secure computation system using ThFHE will be described.

FIG. 3 is a diagram showing the configuration of a conventional secure computation system using ThFHE in which multiple users participate.
In ThFHE, it is possible to set various decryption methods, for example, it is possible to set it so that decryption is possible with only the shared private keys of t people (threshold) out of N people (t-out-of-N). Here, we will show an example of the configuration for N-out-of-N.

Each user (party 1 to N) has its own unique private key (distributed private key) sk _i and encrypts data m _i (including sensitive information) with a master public key jpk:=(pk ₁ +...+pk _N ) calculated from public keys pk _i corresponding to the private keys sk _i of all users (1).

The evaluator performs homomorphic operation f(m ₁ + . . . +m _{N )} using the operation key evk generated by all users and the master public key jpk, with the ciphertexts received from all users as input (2).
The operator transmits the ciphertext ct after the operation to all users (3).

Each user performs partial decryption (PartDec) using his/her own private key sk _i and transmits the partially decrypted text to all users (4).
Each user combines the partially decrypted texts obtained by all users to obtain the plain text as the result of the calculation (FinDec) (5).

Here, the encryption method LWE on which ThFHE is based is defined as follows.
・params=(1 ^λ , q, m, n, χ _LWE , χ _rand ):
params is a set of parameters that are implicitly used in all the following cryptographic algorithms. ^{1 λ} is a security parameter, q = q(λ) is a modulus, m = m(λ), n = n(λ) are dimensions, χ _LWE = χ _LWE (λ), χ _rand = χ _rand (λ) are probability distributions on _Zq .
Gaussian noise is often used for χ _LWE , and U({0,1}) or the same Gaussian noise as χ _LWE is used for the encryption noise χ _rand of the public key cryptosystem.

・A←U(Z _q ^m×n ):
This is a random public matrix that is fixed to the scheme and is generated and fixed before key generation.

・sk←LWE. SymKeyGen( ^1λ ):
Generate a uniformly random secret key sk:=s←U(Z _q ⁿ ).

・pk←LWE. PubKeyGen(sk):
The noise e←χ _LWE ^m is sampled to calculate t=As+e, and the public key pk:=(A, t) is output.

・ct←LWE. SymEnc(sk, m∈{0,1}):
a←U(Z _q ⁿ ), e←χ _LWE is sampled, and the following ciphertext of the common key encryption type is output.

・ct←LWE. PubEnc(pk, m∈{0,1}):
Sample r←χ _rand ^m and output the following public key cryptography ciphertext.

・m←LWE. Dec(sk, ct):
Print the following plaintext:

Based on such LWE encryption, the key generation, encryption, and decryption algorithms of ThFHE can be described as follows.
Here, the number of users is assumed to be N, and each user is represented as (P ₁ , . . . , P _N ).

・(Key generation)
(sk ₁ ,..., sk _N , jpk)←ThFHE. KeyGen( ^1λ ):
Each user P _i generates a unique secret key sk _i .
sk _i ←LWE. SymKeyGen( ^1λ )
Then, each user P _i samples e _i ←χ _LWE ^m and uses sk _i to generate a “partial” public key pk _i as follows:
pk _i :=(A, t _i :=As _i +e _i )←LWE. PubKeyGen( _ski )
Then, a master public key jpk (joint public key) is generated as follows.

なお、

が成り立つ。 ・(Encryption)
ct:=(a,b)←ThFHE. Enc(jpk:=(A,t ^* ),m∈{0,1}):
This algorithm is the same as the above-mentioned LWE.PubEnc(jpk,m∈{0,1}). That is, we sample r←χ _rand ^m and output the public key cryptography ciphertext as follows:

In addition,

holds true.

を計算し出力する。なお、

が成り立つ。 - (Decryption)
m←ThFHE. Dec(ct:=(a,b), sk ₁ ,..., sk _N ):
(PartDec): Each user P _i broadcasts a partial decrypted text p _i =a ^T s _i +e _i ' to all users, where e _i '←χ _LWE .
(FinDec): From the obtained partial decrypted texts p ₁ , . . . , p _N of all users,

Calculate and output.

holds true.

[Improved encryption algorithm]
In this embodiment, the encryption algorithm ThFHE.Enc in the conventional ThFHE is replaced with the following ThFHE.HybridEnc, thereby making the noise level of the ciphertext smaller than in the conventional case, and as a result, the size of the ciphertext is also reduced.

Note that a user who has a secret key sk _j with a subscript j ∈ [N] is denoted as P _j .
Also assume that _Pj holds a "partial" public key _pkj , which is an intermediate product of ThFHE.KeyGen.

を生成する。
なお、鍵生成の際などにＰ_ｊがこの暗号化用の鍵を生成し保持しておくことで、暗号化処理の際は、このステップは省略可能である。 ・ct←ThFHE. HybridEnc(jpk:=(A,t ^* ), _pkj :=(A, _tj ), _skj := _sj ,m∈{0,1}):
Preparation:
User P _j uses the following key for its own encryption instead of the master public key:

Generate.
It should be noted that this step can be omitted during encryption processing if _Pj generates and holds this encryption key during key generation or the like.

を出力する。ここで、

が成り立つ。
なお、復号のアルゴリズムに変更は必要なく、ＴｈＦＨＥ．Ｄｅｃにより実行可能である。 Encryption:
User _Pj samples r←χ _LWE ^m , ^e ←χ _LWE and obtains the ciphertext

where:

holds true.
The decoding algorithm does not need to be changed and can be executed by ThFHE.Dec.

FIG. 1 is a diagram showing the functional configuration of an encryption device 1 according to the present embodiment.
The encryption device 1 is a terminal used by each of multiple users in a secret computing system who encrypts and provides data including sensitive information and entrusts homomorphic computations to an operator, and is an information processing device (computer) that is equipped with a control unit 10 and a memory unit 20, as well as various input/output and communication interfaces.

The control unit 10 is a part that controls the entire encryption device 1, and realizes each function in this embodiment by appropriately reading and executing various programs stored in the storage unit 20. The control unit 10 may be a CPU.

The storage unit 20 is a storage area for various programs for causing the hardware group to function as the encryption device 1, various data, and the like, and may be a ROM, a RAM, a flash memory, or a hard disk drive (HDD), for example.
Specifically, the memory unit 20 stores a program (encryption program) for causing the control unit 10 to execute each function of this embodiment, as well as user data to be encrypted, various key data for encryption and decryption, and the like.

The control unit 10 includes a key generation unit 11 and a ciphertext generation unit 12 .
The key generation unit 11 generates an encryption key jpk j by excluding a random component (As _j ) and a noise component (e j ) corresponding to a shared private key sk _j held by its own terminal from a master public key ^jpk in a lattice cryptography (e.g., _ThFHE ) corresponding to a plurality _of shared private keys.

に対して、自端末が保持する分散秘密鍵ｓｋ_ｊに基づく共通鍵暗号型のランダム成分（ａ^Ｔｓ_ｊ）及びノイズ成分（ｅ^￣）を加算した暗号文 The ciphertext generation unit 12 generates a ciphertext of a public key encryption type based on an encryption key by ThFHE.HybridEnc.

A ciphertext obtained by adding a random component (a ^T s _j ) and a noise component (e ^̂ ) of a common key cryptosystem based on a shared private key sk _j held by the terminal to the

を生成する。

Generate.

は、従来のＴｈＦＨＥの暗号文における

と比べて、公開鍵暗号型のノイズ成分の一部が共通鍵暗号型のノイズに変更される。 As a result,

is the ciphertext of the conventional ThFHE.

In comparison, part of the noise component of the public key cryptography is changed to noise of the common key cryptography.

であり、ユーザ数Ｎが小さいほど大きな削減効果が得られる。例えば、Ｎ＝２のとき、暗号文上のノイズの大きさは、従来と比較して約５０％に減少させることができる。 FIG. 2 is a diagram showing the magnitude of noise on the ciphertext in this embodiment in comparison with the conventional method.
Here, a comparison result of the magnitude of noise on the ciphertext between the conventional ThFHE.Enc and the ThFHE.HybridEnc of the present embodiment in a general setting of Var(χ _LWE ):=σ ² , Var(χ _rand )=O(1) is shown as an example.

When m is sufficiently large, the noise reduction effect ratio obtained is

The smaller the number of users N, the greater the reduction effect. For example, when N=2, the noise level in the ciphertext can be reduced to about 50% compared to the conventional case.

According to this embodiment, the encryption device 1 generates an encryption key from a master public key in a lattice cryptography system corresponding to multiple distributed private keys, excluding random components and noise components corresponding to the distributed private keys held by its own terminal, and generates a ciphertext by adding common key type random components and noise components based on its own distributed private keys to the public key type ciphertext based on this encryption key.
Therefore, while m-dimensional noise in a public key encryption type encryption algorithm increases as it accumulates depending on the number of users, the encryption device 1 reduces the overall noise level by replacing the noise component corresponding to its own private key with a scalar noise component in a common key encryption type encryption algorithm.
As a result, the encryption device 1 can reduce the size of the ciphertext in a fully homomorphic computation system based on lattice cryptography using a plurality of shared keys.

For example, in a secure computation system using a fully homomorphic encryption method using multiple keys such as ThFHE, by applying the encryption algorithm of this embodiment, which combines a common key encryption type encryption algorithm and a public key encryption type encryption algorithm, the size of the ciphertext can be reduced, especially as the number of users decreases.

As a result, for example, users who send data will be able to use encryption algorithms that are lighter than before, which will make it possible to contribute to Goal 9 of the United Nations-led Sustainable Development Goals (SDGs), which is to "build resilient infrastructure, promote sustainable industrialization and foster innovation."

Although the embodiments of the present invention have been described above, the present invention is not limited to the above-described embodiments. Furthermore, the effects described in the above-described embodiments are merely a list of the most favorable effects resulting from the present invention, and the effects of the present invention are not limited to those described in the embodiments.

The encryption method by the encryption device 1 is realized by software or hardware circuits. When realized by software, the programs constituting this software are installed in an information processing device (computer). These programs may be recorded on removable media such as CD-ROMs and distributed to users, or may be distributed by being downloaded to the user's computer via a network. Furthermore, these programs may be provided to the user's computer as a web service via a network without being downloaded.

Reference Signs List 1 Encryption device 10 Control unit 11 Key generation unit 12 Ciphertext generation unit 20 Storage unit

Claims (4)

a key generation unit that generates an encryption key by removing a random component and a noise component corresponding to a shared private key held by the device itself from a master public key in a lattice cryptography corresponding to a plurality of shared private keys;
an encryption device comprising: a ciphertext generation unit that generates a ciphertext by adding a random component and a noise component of a common key cryptography type based on a distributed private key held by the device to a ciphertext of a public key cryptography type based on the encryption key. The encryption device according to claim 1, wherein the lattice cryptography is a threshold fully homomorphic encryption method. The encryption device is
a key generation step of generating an encryption key by removing a random component and a noise component corresponding to a shared private key held by the device from a master public key in a lattice cryptography corresponding to a plurality of shared private keys;
and a ciphertext generation step of generating ciphertext by adding a random component and a noise component of a common key cryptography type based on a distributed private key held by the device to a public key cryptography type ciphertext based on the encryption key. An encryption program for causing a computer to function as the encryption device according to claim 1 or 2.

Images