Cyclotomic Polynomials in Ring-LWE Homomorphic Encryption Schemes

Homomorphic Encryption has been considered the \u27Holy Grail of Cryptography\u27 since the discovery of secure public key cryptography in the 1970s. In 2009, a long-standing question about whether fully homomorphic encryption is theoretically plausible was affirmatively answered by Craig Gentry and his bootstrapping construction. Gentry\u27s breakthrough has initiated a surge of new research in this area, one of the most promising ideas being the Learning With Errors (LWE) problem posed by Oded Regev\u27s. Although this problem has proved to be versatile as a basis for homomorphic encryption schemes, the large key sizes result in a quadratic overhead making this inefficient for practical purposes. In order to address this efficiency issue, Oded Regev, Chris Peikert and Vadim Lyubashevsky ported the LWE problem to a ring setting, thus calling it the Ring Learning with Errors (Ring-LWE) problem. The underlying ring structure of the Ring-LWE problem is $\mathbb{Z}[x]/\Phi_m(x)$ where $\Phi_m(x)$ is the $m$th cyclotomic polynomial. The hardness of this problem is based on special properties of cyclotomic number fields. In this thesis, we explore the properties of lattices and algebraic number fields, in particular, cyclotomic number fields which make them a good choice to be used in the Ring-LWE problem setting. The biggest crutch in homomorphic encryption schemes till date is performing homomorphic multiplication. As the noise term in the resulting ciphertext grows multiplicatively, it is very hard to recover the original ciphertext after a certain number of multiplications without compromising on efficiency. We investigate the efficiency of an implemented cryptosystem based on the Ring-LWE hardness and measure the performance of homomorphic multiplication by varying different parameters such as the cipherspace cyclotomic index and the underlying ring $\mathbb{Z}_p$