Analysis and Development of Ciphers Homomorphic on Addition and Multiplication

Abstract

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.

ÖZ: Bu tezde, çeşitli toplamsal ve çarpımsal homomorfik şifreler analiz edilmiş ve geliştirilmiştir. Yeni homomorfik şifreleme (HE) şifreleme sınıflandırması önerilmiştir. Homomorfik şifrelerin yeni sınıflandırması, burada yeni geliştirilen HE şifresi için ayrı bir sınıfa izin vererek tanıtıldı. Daha önce kullanılan iki kriteri beşe kadar genişletir. Simetrik homomorfik şema HE1N'ye ek olarak, literatürden asimetrik homomorfik şemalar RSA, NTRU, RLWE-NCM-CSCM ele alınmaktadır. Yeni bir yalnızca şifreli metin saldırısı, 2 boyutlu bir kafesteki en kısa vektör tasarlandığından RSA şifreli mesajları bulur. RSA'nın önerilen saldırıya duyarlı olmaması için, RSA ortak anahtarları için yeni ayarlar sunulur. NTRU ve HE1N, mesajı gürültü ekleyerek ve ardından modulo işlemi uygulayarak şifreleyen iki homomorfik şifreleme sistemidir. Her ikisinde de toplamın modülden daha az olması nedeniyle modulo işleminin bir etkisi olmayabileceği bulundu. IEEE standart parametreleri kullanılarak NTRU'ya karşı NTRU modulo p kusur saldırısı ihmal edilemez başarı olasılığı ile tasarlanmıştır. Başarı olasılığının ihmal edilebilir olması için tezde parametre ayarı yapılması önerilir. HE1N'ye karşı iki saldırı tasarlanmıştır ve bu saldırıları azaltmak için HE1N parametreleri için yeni ayarlar önerilir. Rastgele uyumlu ortak anahtar şifreleme sistemi (RCPKC), tamsayılar kullanan ve kafes tabanlı azaltma saldırılarına (LBRA) karşı bağışık olan bir NTRU varyantı olarak geliştirildi. RCPKC, LBRA'ya karşı rasgele sayıların seçileceği bir aralığı belirtir. NTRU ile karşılaştırıldığında, RCPKC daha verimlidir ve enerji tüketimini azaltır, bu da gözetimsiz kablosuz sensör ağlarının ömrünün artmasına olanak tanır. 2011 yılında Brakerski ve Vaikuntanathan tarafından önerilen RLWE-NCM-CSCM'yi ilerleterek, RLWE-CSCM adı verilen şifreli metin boyut kontrol mekanizmasını (CSCM) kullanan hatalarla öğrenme (RLWE) tabanlı şifreleme sistemi geliştirildi. RLWE-CSCM, ilgili ilk tam homomorfiktir. hem toplama hem de çarpma şemasına gürültünün büyümesinden etkilenmez. RLWE-CSCM şifreli metninin boyutu, her homomorfik çarpma işlemi ile büyür. Bu nedenle, bu tezde iki CSCM önerilmiştir. RLWE-CSCM, homomorfik olarak görüntü filtreleri uygulamak, homomorfik oylama sistemleri gibi çok çeşitli uygulamalarda yer alabilir.