A key concept in the development of the first fully homomorphic scheme is Gentry’s bootstrapping technique. Schemes based on Gentry’s blueprint are noise-based, which implies that the plaintext is hidden by noise which can be eliminated by decryption. However, this noise grows with every homomorphic evaluation, and once it surpasses a specific threshold, decryption will fail.
To overcome this problem, Gentry introduced the notion of recryption which works by encrypting a ciphertext anew (so that it becomes doubly encrypted) and then removing the inner encryption by homomorphically evaluating the doubly encrypted plaintext and the encrypted decryption key using the decryption circuit. As long as the evaluation algorithm can deal with the decryption process in addition to one more gate, progress can be made in assessing the circuit of interest.
DEFINITION – A C–evaluation scheme is called bootstrappable if it is able to homomorphically evaluate its own decryption circuit plus one additional NAND gate.
FHE WITH BOOTSTRAPPING
In Gentry’s scheme, to go from a somewhat homomorphic encryption scheme to a fully homomorphic encryption scheme, bootstrapping is used. When a ciphertext becomes too large or too noisy, it increases unacceptably. The encoder can use the somewhat homomorphic encryption scheme to evaluate the decryption function on the ciphertext, using the encrypted private key that is part of the public key. So this re-encryption process encrypts plaintext again, that is less noisy and more compact. In order to remain an effective scheme, it is necessary homomorphic scheme could securely encrypt private key and verify the correctness of the decryption function. For this to be effective, the somewhat homomorphic cryptosystem has to securely encrypt its private key and capable of evaluating the decrypt function. Also, Gentry uses squashing of the decryption that allows getting the decrypt function as a function that somewhat cryptosystem can homomorphically evaluate. The disadvantages of Gentry’s fully homomorphic encryption scheme is impractical (it implements slowly and, keys and ciphertexts are large), the fact it is based on new and relatively untested cryptographic primitives.
One year after the creation of the first fully homomorphic encryption scheme Dijk, Gentry, Halevi, Vaikuntanathan proposed fully homomorphic encryption scheme using elementary modular arithmetics (it works over the Integers) and use Gentry’s techniques to convert somewhat homomorphic cryptosystem to fully homomorphic encryption scheme. The security of this scheme to finding an approximate greatest common divisor, given a list of integers that are near multiples of a hidden integer, output that hidden integer.
Somewhat homomorphic encryption scheme’s public key and private key are two large integers (one of them is shared by both keys), the ciphertext consists of one large integer. So, the new encryption scheme gives smaller ciphertext expansion and the key length is shorter than the Gentry’s original scheme. It also allows SIMD style to encrypt data in multiple finite fields of characteristic two at the same time. Three aspects of security were analyzed for this scheme by researchers. Key recovering and onewayness of the encryptions are related to the well-studied problem – Small Principal Ideal Problem in number theory. The semantic security of somewhat homomorphic encryption scheme based on Polynomial over ideal lattices.
FHE WITHOUT BOOTSTRAPPING
Developing fully homomorphic encryption schemes that singly encrypt each bit and using the principles of the Gentry schemes, a class of fully homomorphic schemes has been extended. These cryptosystems based on a problem in machine learning as LWE-problem (Learning with errors (LWE) problem), which was formulated Regev in 2005. LWE-problem is as difficult to solve as many worst-case lattice problems.
The new scheme based on somewhat encryption scheme, allowed to perform any number of additions, but only one multiplication for the plain data. The main advantage of this scheme is encryption of the m⨯ m size bit matrix at a time.
The LWE-based fully homomorphic encryption scheme does not use squashing and introduces a new dimension-modulus reduction technique, which shortens the ciphertexts and reduces the decryption complexity, without introducing additional assumptions. Following this scheme development, other LWE-based and RLWE-based fully homomorphic encryption schemes began to develop.
It is the latest schemes without using noise reduction techniques. The non-associative octonion ring over finite field fully homomorphic encryption scheme’s cryptographic robustness is based on the complexity of multivariate algebraic equations with high degree.
Liu’s symmetric fully homomorphic encryption scheme provides an arbitrary number of additions and multiplications, and the correct decryption in contempt of the amount of noises accumulation. Moreover, this cryptosystem doesn’t use noise reduction mechanisms and based on the Approximate-GCD complexity.