Implement Lattice-Based Cryptography: from LWE to FHE

[aidevnn]

In this project, we have successfully experimented with leveled homomorphic encryption using the BGV scheme. To further enhance the project, implementing a minimalist version of a Full Homomorphic Encryption with examples will be a useful improvement. This addition will provide valuable insights and broaden the scope of the project in the domain of lattice-based cryptography.

[aidevnn]

FastGoat/FastGoat/UserGroup/Lattice/Regev.cs

Lines 30 to 35 in 4712053

	// 1) m = (1+ε)*n*log2(n) ε=1
	var m = (int)(2 * n * double.Log2(n));
	// 2) lim a(n)*log2(n)*√n = lim 1 / (4*log10(n)) = 0
	var a = 1.0 / (4 * double.Log10(n) * double.Log2(n) * double.Sqrt(n));

The parameters m and q do not match those in Reg24 and can be adjusted. This is also an excellent opportunity to delve deeper into system security.

[aidevnn]

The toy implementation of the Regev LWE scheme has been completed according to the testing parameters outlined in the original paper. This implementation can be used to gain a better understanding of system security.

Additionally, homomorphic logic gates have been implemented based on Shai Halevi's paper. Moving forward, studying the growth of errors would be a valuable next step.

[aidevnn]

Taking modulus ciphertext multiple of modulus plaintext is invalid because public key can be factorized.

[aidevnn]

The main concepts of the BGV scheme were thoroughly explored, including relinearization, moduli switching, and key switching, as well as the progression from somewhat to leveled and bootstrapping. These explorations were conducted using weak parameters without a focus on computational efficiency, resulting in an insecure setting.

This topic is hot.

[aidevnn]

Bootstrapping methods have been successfully added to scale the modulus from level 0 to level L-1, allowing for homomorphic addition with carry on 32-bits. However, these operations currently use insecure parameters because the implementation of Blind Rotate remains highly inefficient.

The exploration of Homomorphic Encryption is largely complete. The next significant challenge will be to achieve post-quantum level security with recommended parameters.

[aidevnn]

The parameters of the [Reg24] examples work well with the RLWE implementation and scale effectively with Leveled BGV and Bootstrapping. We have successfully achieved an educational example of LWE to FHE. Our next step for the FastGoat project will be to delve deeper into lattice-based cryptography.