Basic concepts of homomorphic encryption

So called homomorphic encryption （HE,homomorphic encryption） Refer to ： The clear m encryption , Get the ciphertext c, Satisfy f yes f(m) The ciphertext of , among f Is any family of functions F Function of , Plaintext can be a single plaintext , It can also be a plaintext vector , Corresponding to a single ciphertext and a ciphertext vector . And the corresponding function family F Is a family of homomorphic functions of this scheme , That is, the set of all functions that can be homomorphically computed supported by the homomorphic encryption scheme . such as f(x)=x+2, We want to encrypt c In plain text m The ciphertext of . be f=c+2, yes m+2 The ciphertext of .

A simple classification of homomorphic functions

According to the encryption scheme, the supported function families are different , Homomorphic encryption can be divided into several types .

The more popular homomorphic schemes are additive homomorphism 、 Multiplicative homomorphism 、 Partial homomorphism and homomorphism .

Additive homomorphism ： The homomorphic function family supported by the encryption scheme is all functions that can be realized only by addition . At present, it is widely used paillier Additive homomorphism .

Multiplicative homomorphism ： The homomorphic function family supported by the encryption scheme is all functions that can be realized only by multiplication . Like the classic RSA Encryption scheme .

Partial homomorphism （partially fully homomorphic encryption, somewhat homomorphic encryption or leveled fully homomorphic encryption）： The homomorphic function family supported by this scheme is the function that can be realized by finite addition and finite multiplication .

Holomorphism ： This scheme can support all the functions that can be realized by addition and multiplication of homomorphic function family . such as BGV、BFV、CKKS.

Homomorphic encryption is generally asymmetric encryption , Of course, there are homomorphic schemes of symmetric encryption .

The following description uses asymmetric encryption , That is, the term description of public key system . Symmetric encryption is a symmetric encryption in which the public key and the private key are equal .

Formal definition

A complete homomorphic scheme consists of a key generation algorithm , encryption algorithm , Decryption algorithm and homomorphic computing algorithm 4 Part of the form .

1、 Key generation algorithm （HE.KeyGen） Its input is safety parameter And other common parameters that describe other requirements , Output an encryption key pk（ Public key ）, A decryption key sk（ Private key ） And a homomorphic computation key evk.

2、 encryption algorithm （HE.Encrypt） Enter plaintext m And encryption keys pk, Output m The ciphertext of c.

3、 Decryption algorithm （HE.Decrypt） Enter ciphertext c And decrypt the key , Output clear m.

4、 Homomorphic computing algorithm （HE.Evaluate） Enter ciphertext , Homomorphic computing key evk And the function f, Output . It is worth noting that , there c It is not necessarily a ciphertext that can participate in the calculation again , He just needs to be able to decrypt it correctly . All possible functions f Form a family of homomorphic functions F.

Correctness of homomorphic encryption

The correctness of homomorphic encryption includes two aspects . First , It is the same as the general encryption scheme , Ciphertext can be decrypted correctly , That is to say m=HE.Decrypt(HE.Encrypt(m,pk),sk). secondly , Homomorphic calculation must be correct .

When , among when ：