Research On Several Classes Of Homomorphic Encryption Schemes

Though great progress has been made in the direction of constructing efficient Fully homomorphic encryption(FHE) schemes, FHE is still rather expensive. The main reason for that, is that homomorphic operations on encrypted data require much more computation than handling the ones unencrypted. To address this problem within limit, this work devotes itself to constructing FHE, improving its efficiency, and enlarging its functions, by introducing several novel techniques, such as the evolutionary method for ciphertexts, the way of successive padding with a fixed bit, the probabilistic encoding with homomorphic property, and so on. The main results obtained are as follows.(1) A leveled FHE scheme based on the Ring learning with errors(RLWE) problem is presented by simultaneously applying both batch techniques. It therefore allows double packing many plaintext values into each ciphertext to support SIMD-type operations,which effectively reduces the ciphertext expansion ratio. An efficient evolutionary method for achieving arbitrary homomorphic permutation operations on a packed ciphertext is also provided by using several given key-switching hints.(2) A certificateless encryption scheme from lattices is provided by using preimage sampling algorithm to extract partial private keys and the learning with errors problem to generate secret values and public keys. It remains indistinguishably secure against chosen-plaintext and adaptive chosen-identity attacks, even against quantum-computing attacks, in the random oracle model by formally showing this construction can fight against two types of adversaries who can request secret values. Two methods for further improving its efficiency are used by enlarging its plaintext space according to both distinct approaches. Specially, an efficient method, named a way of successive padding with a fixed bit, is presented for obtaining multiple longer bit strings determined by a fixed-size bit string, which makes a valuable contribution towards building the multi-bit certificateless encryption scheme.(3) To lower the sizes of keys, a certificateless encryption scheme is formulated by using a trapdoor sampling algorithm over a selected Number theory research unit(NTRU) lattice to extract partial private keys and using the ring learning with errors problem to generate public keys. Its security is based on both assumptions of the decisional ring learning with errors problem and the decisional small polynomial ratio problem. To further improve efficiency, a certificateless parallel encryption scheme with more efficient algorithms only using arithmetic in integers is also given by respectively using the Chinese Remainder Theorem to decompose the enlarged plaintext space into the product of distinct prime ideals and to break down the ring, over which encryption operations work, for obtaining the Chinese remainder basis.(4) A certificateless fully homomorphic encryption(CLFHE) scheme based on the learning with errors problem is constructed by introducing a new technique called probabilistic encoding with homomorphic property. This technique can conveniently convert an intended message into two elements in a ring, which will be respectively encrypted under both public keys of a user in certificateless cryptosystem. Upon knowing both elements simultaneously, the original message can be easily recovered. Otherwise, it is hidden perfectly by the probabilistic property of encoding. This CLFHE removes evaluation keys by using the approximate eigenvector method given by Gentry et al., which makes it into a pure CLFHE.(5) Several special properties of Smart and Vercauteren’s encryption scheme(SV10scheme) are put forward. These properties not only show that the secret key is deduced from an N-dimensional vector into its any entry, but also produce the triplet(grade-i reduced plaintext space, grade-i reduced ciphertext space, grade-i reduced secret key) for each i, where grade-i reduced secret key can decrypt grade-i reduced ciphertexts.Furthermore, grade-(i+1) reduced secret key can be computed efficiently from grade-i reduced secret key one by one. But a sequential computation in the opposite direction is difficult except at most the first steps of such a sequential computation. Based on the properties given, this work then proposes a simple hierarchical encryption scheme with relatively small key and ciphertext sizes.(6) An additively homomorphic encryption scheme based heavily on Smart-Vercauteren encryption scheme is advanced, where both schemes work with two ideals I and J. As a contribution of independent interest, a two-element representation of the ideal I, by factoring prime numbers in a number field, is given. This two-element representation serves as the public key. The scheme allows working over much larger message space than that of the original scheme by selecting the ideal I with larger decryption radius to generate public/private key pair, instead of choosing the ideal J as done in the original scheme.