Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Learning Resources:
Fully Homomorphic Encryption I: Theory and Foundations (Professor Yu Yu from Shanghai Jiao Tong University)
Fully Homomorphic Encryption II: Theory and Construction of Fully Homomorphic Encryption (Teacher Xiang Xie)

---

Now the second-generation (such as BGV and BFV) and third-generation fully homomorphic encryption schemes are all based on LWE. Now advanced fully homomorphic schemes are also based on LWE, so this article summarizes the basic knowledge of LWE.
First, we want to encrypt a number.$s$, now with a series of$a_i$right$s$Encrypt and get$a_{i}s$In fact, by solving the greatest common divisor GCD, we can find$s$However, if we add a random noise$e_i$,get$a_{i}s+e_i$, then it will be difficult to solve$s$This process is my simple understanding of LWE. The so-called error is a noise.

The calculation process of fully homomorphic encryption is divided into three steps: key generation KeyGen, encryption Enc, homomorphic calculation Eval, and decryption Dec.

KeyGen：

First, construct the above equation,$s\cdot A+e=sA+e$, and then get the public key pk ($-A$and$sA+e$splicing), and the private key sk ($s$and 1). So the result of multiplying pk and sk is random noise e (close to 0).

Enc：

The public key pk used for encryption, r is a random vector containing only 0 or 1, and m is the information to be encrypted (placed in the lowest bit of the vector).

Dec：

The private key sk used for decryption is used to calculate the inner product with ct and then mod 2 to get the decrypted result.

Proof of correctness:

Multiplying sk and pk gives 2e (the condition satisfied in KeyGen), and then doing the inner product with r gives a very small even noise. The final result is m + very small even noise, so the noise can be eliminated by mod 2 to get the decrypted result m. ​​This is why the constructed noise is 2e, not e. My understanding is that by constructing even random noise, it is convenient to eliminate the noise by mod 2 during decryption.

Safety Proof:

When pk is pseudo-random and r has high enough entropy (i.e. very random?), pk and pk multiplied by r are both pseudo-random. After adding the vector with m, the encrypted result is also pseudo-random.

The following is a formulaic description by Xiang Xie:
Encryption formula: ciphertext c = public key pk ✖️ random r + plaintext m
Decryption formula: Plaintext m = <ciphertext sk, private key sk> mod q mod 2

On this basis, the value of plaintext m can be decrypted by modulo 2. As long as the noise is small enough, the correctness can be guaranteed.
There is one thing that needs to be distinguished here:$PK=(A,b=A{s}^{\prime }+2e)$is the BGV scheme, while BFV is$PK=(A,b=A{s}^{\prime }+e)$The difference is that BGV encodes information in the low bits, while BFV encodes messages in the high bits (this will be explained when learning BFV).

Eval (additive homomorphism and multiplicative homomorphism):

Note that homomorphic addition or multiplication will lead to significant noise accumulation, and multiplication grows quadratically.
Next, let's talk about how to decrypt the result of homomorphic multiplication. From the following formula, we can see that multiplying two ciphertexts is equivalent to first taking the tensor product of the ciphertext and the private key, and then taking the inner product. Therefore, it is obvious that the size of the ciphertext and the private key has doubled. Example is a proof of equivalence.

So the question is, how to restore the size of the ciphertext and the size of the private key after homomorphic multiplication? This is the problem that Key Switching solves.

Here is a description from teacher Xiang Xie:

Key Switching

The goal is to restore the size of the ciphertext and private key to linear size.

Now find the multiplication of ciphertext c1 and c2:

The above process is based on the concept of bit decomposition:

Here is a description from teacher Xiang Xie:

The goal of Key Switching is to transfer the private key$\tilde{s}$Next$\tilde{c}$ Convert to private key$s$Next$c$,and$\tilde{c}$and$c$They are all the same plaintext encrypted.
A core concept here is Key Switching Key (KSK), which is to use private key$s$To encrypt$\tilde{s}$。

Through the Key Switching process, the private key can be derived from$s\otimes s$Becomes linear$s$, while the ciphertext from$\tilde{c}$Becomes linear$c$And from the last line of the formula, we can see that after Key Switching$⟨c,s⟩$and the original$⟨\tilde{c},s\otimes s⟩$There is a noise difference between$2{\tilde{c}}^T\tilde{e}$, this part can be very large! So here we still can't implement Key Switching.

A Gadget matrix G is introduced here:

Therefore, the Key Switching process becomes as follows:

At this point, the added error is very small.
To sum up, through Key Switching, the original private key$\tilde{s}=s\otimes s$Next$\tilde{c}=c\otimes c$, converted into a private key$s$Next$c$, note that after Key Switching$s,c$They are no longer the original values ​​(double check).

For BGV, the noise of addition increases linearly, and the noise of multiplication increases quadratically. Although Key Switching can support multiplication (limiting sk to become very large), the noise is actually a small noise added to the original multiplication noise, and the overall noise is also very large. Therefore, it is necessary to further reduce this noise.

Modulus Reduction

So far, LWE has been used to implement homomorphic multiplication and addition calculations of very small depth, and key switching uses new keys for each layer. However, as the calculation depth increases, the expansion of noise is explosive, so it is not yet a levelled FHE (FHE that can calculate a specified depth).
Now we hope to implement an FHE that can calculate a certain depth without the help of bootstrapping, which requires the use of modular transformation.

I don't quite understand the process in the middle, but in short, it transforms the ciphertext c from the domain of modulo q to the domain of modulo p (p<
Here is a concrete example:
If Modulus Reduction is not performed, the noise will increase in a double exponential trend as the depth increases, and decryption errors will occur after level >= 3.

If Modulus Reduction is performed on each level, the noise will be maintained within an absolute value range, but the cost is that the modulus will continue to decrease.

So to achieve a levelled FHE, you can set a modulus$B^d$, then we can calculate a depth of$d$The circuit (where$B$is the noise upper bound of the refreshed ciphertext).$d$After the depth, the modulus should be reduced to$B$, to ensure that decryption does not go wrong at this time. BGV is a levelled FHE.