Analysis and Development of Ciphers Homomorphic on Addition and Multiplication

In this thesis, various additive and multiplicative homomorphic ciphers are analyzed and developed. New homomorphic encryption (HE) ciphers classification is proposed. The new classification of homomorphic ciphers is introduced allowing having a separate class for the newly developed herein HE cipher. It extends the previously used two criteria to five. In addition to the symmetric homomorphic scheme, HE1N, the asymmetric homomorphic schemes RSA, NTRU, RLWE-NCM-CSCM from the literature are considered. A new ciphertext-only attack finds RSA encrypted messages as the shortest vector in a 2-dimensional lattice is designed. For RSA not to be susceptible to the attack proposed, new settings for RSA public keys are presented. NTRU and HE1N are two homomorphic cryptosystems, encrypting the message by adding to it noise and then applying modulo operation. It is found that in both of them, the modulo operation may not have an effect because the sum is less than the modulus. NTRU modulo p flaw attack against NTRU using IEEE standard parameters with non-negligible success probability is designed. To make the success probability negligible, parameter setting is recommended in the thesis. Two attacks against HE1N are designed, and new settings for HE1N parameters are recommended to mitigate these attacks. The random congruential public-key cryptosystem (RCPKC) is developed, an NTRU variant using integers and immune against lattice basis reduction attacks (LBRA). RCPKC specifies a range from which the random numbers shall be selected to counter LBRA. Compared to NTRU, RCPKC is more efficient and it reduces energy consumption, which allows increasing the lifetime of unattended wireless sensor networks. Ring learning with errors (RLWE)-based cryptosystem using ciphertexts size control mechanism (CSCM), called RLWE-CSCM is developed, advancing RLWE-NCM CSCM proposed by Brakerski and Vaikuntanathan in 2011. RLWE-CSCM is the first fully homomorphic with respect both to addition and multiplication scheme not affected by the growth of noise. The size of RLWE-CSCM ciphertext grows with each homomorphic multiplication operation. Therefore, two CSCMs are proposed in this thesis. RLWE-CSCM can be involved in a wide range of applications such as applying images filters homomorphically, homomorphic voting systems.