This paper presents a fully homomorphic encryption (FHE) scheme with relatively small key and ciphertext sizes. The scheme is based on Gentry's approach, which constructs a fully homomorphic scheme from a "somewhat" homomorphic scheme. The proposed scheme uses algebraic number fields and avoids the need for lattices in its encryption and decryption operations, although its security is based on lattice-related problems.
The scheme is parametrized by an integer N, and the public key consists of a prime p and an integer α modulo p. The private key consists of either an integer z (for encrypting bits) or a polynomial Z(x) of degree N-1 (for encrypting binary polynomials). Encryption involves encoding the message as a binary polynomial, adding a small random polynomial, and evaluating the resulting polynomial at α modulo p. Decryption involves multiplying the ciphertext by z or Z(x), dividing by p, and rounding the result to recover the plaintext.
The scheme allows efficient fully homomorphic encryption over any field of characteristic two. The analysis shows that the scheme is correct for certain parameter sets and determines how many homomorphic operations can be performed before decryption fails. The security of the scheme is based on the difficulty of solving the small principal ideal problem and the decisional version of the sparse subset-sum problem.
The paper also discusses the extension of the scheme to support larger message spaces and provides implementation results for practical parameter choices. The scheme is shown to have smaller key and ciphertext sizes compared to Gentry's original scheme, and it can be used for fully homomorphic encryption over any field of characteristic two. The implementation results indicate that the scheme can achieve a certain depth of decryption circuits, although it is not yet fully homomorphic at practical key sizes. The paper concludes that the scheme is a specialisation and optimization of Gentry's scheme, with potential for further improvements in parameter choices and performance.This paper presents a fully homomorphic encryption (FHE) scheme with relatively small key and ciphertext sizes. The scheme is based on Gentry's approach, which constructs a fully homomorphic scheme from a "somewhat" homomorphic scheme. The proposed scheme uses algebraic number fields and avoids the need for lattices in its encryption and decryption operations, although its security is based on lattice-related problems.
The scheme is parametrized by an integer N, and the public key consists of a prime p and an integer α modulo p. The private key consists of either an integer z (for encrypting bits) or a polynomial Z(x) of degree N-1 (for encrypting binary polynomials). Encryption involves encoding the message as a binary polynomial, adding a small random polynomial, and evaluating the resulting polynomial at α modulo p. Decryption involves multiplying the ciphertext by z or Z(x), dividing by p, and rounding the result to recover the plaintext.
The scheme allows efficient fully homomorphic encryption over any field of characteristic two. The analysis shows that the scheme is correct for certain parameter sets and determines how many homomorphic operations can be performed before decryption fails. The security of the scheme is based on the difficulty of solving the small principal ideal problem and the decisional version of the sparse subset-sum problem.
The paper also discusses the extension of the scheme to support larger message spaces and provides implementation results for practical parameter choices. The scheme is shown to have smaller key and ciphertext sizes compared to Gentry's original scheme, and it can be used for fully homomorphic encryption over any field of characteristic two. The implementation results indicate that the scheme can achieve a certain depth of decryption circuits, although it is not yet fully homomorphic at practical key sizes. The paper concludes that the scheme is a specialisation and optimization of Gentry's scheme, with potential for further improvements in parameter choices and performance.