Hatalarla öğrenme tabanlı torus tam homomorfik şifreleme şemasının kalan sayılar sistemi varyantı
Residue number system variant of learning with errors based torus fully homomorphi̇c encryption scheme
Yazar: SERRA SAZOĞLU
Danışman: PROF. DR. MEHMET ÖZEN
Sakarya Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı / Cebir ve Sayılar Teorisi Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Matematik = Mathematics

Özet:
Homomorfik şifreleme, şifrelenmiş veriler üzerinde şifre çözmeden homomorfik işlemler gerçekleştirilmesine olanak tanıyan ve veri güvenliğini sağlayan özel bir şifreleme türüdür. Bulut sistemi kullanılarak tüm sektörler adına müşteri ve/veya hasta gizliliği için geliştirilmesi gereken en önemli sistemlerden biridir. Bulut platformlarında, veri güvenliğini sağlamak için literatürde birçok şifreleme algoritması geliştirilmiştir.  Sunucu tarafında veriler üzerinde işlem yapılabilmesi için verilerin çözülmesine ihtiyaç bulunmaktadır. Bu sebeple veri gizliliğinin sağlanması konusunda tehditler oluşmaktadır. Ayrıca IoT sistemlerinin kullanımının artmasıyla birlikte bu sistemlerin kullanıldığı alanlardaki en büyük sorun yine veri koruma ve veri gizliliği olmuştur. Dahası yapay zeka uygulamalarının pek çoğunda güvenliği sağlamak için de homomorfik şifreleme son zamanların en çok tercih edilen şifreleme yöntemlerinden birisi haline gelmiştir. Homomorfik şifreleme sayesinde şifreli veriler üzerinde işlem yapılabilmekte ve verinin çözülmesine ihtiyaç kalmamaktadır. Fakat şifreleme süreleri ve kaynak kullanımı noktasında dezavantajları bulunmaktadır.  Homomorfik şifrelemeden kaynaklanan uzun şifreleme süresi şemanın pratikte kullanımına engel teşkil etmektedir. Bu nedenle, homomorfik şemaları geliştirmeyi ve iyileştirmeyi amaçlayan çalışmalar büyük önem taşımaktadır. Ancak şifreleme şemalarının oluşturulması, bu şemaların maliyeti ve hesaplama boyutu nedeniyle teoride kalmıştır. Bu nedenle şifreleme şemalarını hızlandırmak ve maliyetleri düşürmek için birçok çalışma yürütülmektedir. 
Bu tezde, diğer birçok homomorfik şifreleme şemasına uygulanarak şemaları geliştiren Kalan Sayı Sistemi (RNS) varyantını, yakın zamanda büyük bir atılım gerçekleştiren TFHE (Torus Tam Homomorfik Şifreleme) şemasına uygulayarak homomorfik şifrelemeye katkıda bulunulması amaçlanmaktadır. Bu kapsamda Torus Tam Homomorfik Şifreleme (TFHE) algoritması üzerinde hesaplama yükünün azaltılması ve işlem sürelerinin kısaltılması, kaynak kullanımının azaltılması hedeflenmektedir. Tez kapsamındaki bilimsel çalışmalarımızda homomorfik şifrelemenin dezavantajlarını gidermek için Çin Kalan Teoremi (CRT), literatürdeki çalışmalardan farklı olarak TFHE şemasına uygulanacaktır ve şifreleme süresi açısından iyileştirme sağlanacaktır. Kullanılacak olan CRT ile TFHE bileşenlerinin ve çalıştığı uzayın farklılığı, diğer homomorfik şifreleme şemalarından ayrılmaktadır. Çin Kalan Teoremi (CRT) yöntemi, şemaya RNS uygulamak için kullanılacaktır. Şemaya RNS uygulayarak, şemanın şifreleme ve deşifreleme sürelerinde yaklaşık 2 kat daha fazla gelişme sağlanmıştır.

Abstract:
Homomorphic encryption is a special type of encryption that allows performing homomorphic operations on encrypted data without decrypting and provides data security. Using the cloud system is one of the most important systems that needs to be developed for customer and/or patient confidentiality on behalf of all sectors. In cloud platforms, many encryption algorithms have been developed in the literature to ensure data security.  There is a need to decode the data in order to process the data on the server side. For this reason, there are threats to ensuring data privacy. In addition, with the increasing use of IoT systems, the biggest problem in the areas where these systems are used has again been data protection and data privacy. Moreover, homomorphic encryption has become one of the most preferred encryption methods in recent times to ensure security in many of the artificial intelligence applications. 
Thanks to homomorphic encryption, operations can be performed on encrypted data and there is no need to decrypt the data. However, there are disadvantages in terms of encryption times and resource usage.  The long encryption time caused by homomorphic encryption is an obstacle to the practical use of the scheme. Therefore, studies aimed at developing and improving homomorphic schemes are of great importance. However, the creation of encryption schemes has remained theoretical due to the cost and computational size of these schemes. For this reason, many studies are being carried out to speed up encryption schemes and reduce costs. 
Homomorphic encryption schemes are divided into three classes according to the allowed operations. If a cryptographic scheme allows for an unlimited number of only one operation (multiplication or addition), this scheme is called a partially homomorphic cryptographic (PHE) scheme. If an encryption scheme allows an unlimited number of one operation and allows a limited number of other operations, this scheme is called a somewhat homomorphic encryption (SwHE) scheme. If an encryption scheme allows an unlimited number of multiplication and addition operations, this scheme is called a fully homomorphic encryption (FHE) scheme (Özdemir and Koç, 2022).
FHE schemes can be divided into four basic categories based on problems. The first is the ideal lattice-based FHE scheme, presented by Gentry in 2009 (Gentry, 2009). In later years, Gentry's invention inspired other researchers and schemes based on the ideal lattice problem were developed. Secondly, it is a FHE scheme on integers that proposed by Van Djik et al. (Van Djik et al., 2010). Thirdly, it is a FHE scheme which based on learning with errors (LWE) problem offered by Oded Regev (Regev, 2010). Later, this problem was developed and ring learning with errors (RLWE) based schemes were also obtained (Lyubashevsky et al., 2013). Finally, FHE schemes based on NTRU were created and developed (Hoffstein et al., 2006). 

Basically, homomorphic encryption is a special type of encryption in which the ciphertext resulting from operations on ciphertext and the ciphertext resulting from the encryption of the result of the same operations performed on plaintexts are equal. From a historical point of view, the special homomorphisms used until 1978 paved the way for the use of partial homomorphic encryption for 30 years, but the most important development in this area was with the full homomorphic scheme developed by Gentry in 2009 (Gentry, 2009). Later, the DGHV (Djik-Gentry-Halevi-Vaikuntanathan) scheme (Van Djik et al., 2010) developed on integers in 2009, the BGV (Brakerski-Gentry-Vaikuntanathan) scheme based on learning problems developed in 2011 (Brakerski et al., 2014), the BFV (Brakerski-Fan-Vercauteren) (Fan and Vercauteren, 2012) study published in 2012 together with the GSW (Gentry-Sahai-Waters) scheme (Gentry et al., 2013) published in 2013, the FHEW (Fastest Homomorphic Encryption in the West ) (Ducas and Micciancio, 2015) scheme introduced in 2014, the CKKS (Cheon-Kim-Kim Song) (Cheon et al., 2017) and TFHE (Torus Fully Homomorphic Encryption) (Chillotti et al., 2016) studies also introduced in 2016 have made great contributions to this field.
Recently, the full homomorphic encryption scheme based on torus, called TFHE, which proposed by Ilaria et al. (Chillotti et al., 2020), also holds promise for homomorphic encryption. Although many studies have been carried out to improve the scheme, we aim to minimize speed, time and memory problems by making the RNS variant of the scheme in this study. It has been observed that the RNS-CKKS scheme (Cheon at al., 2019), of which RNS variants were previously made, speeds up decoding, constant multiplication and homomorphic multiplication operations 17.3, 6.4, and 8.3 times faster, respectively, compared to the original scheme. Again, it has been obtained that the RNS-FV (Bajard et al., 2017) scheme increases from x5 speed to x20 speed for decryption operation and from x2 speed to x4 speed for multiplication operation between the dimensions   and  compared to the original FV (Fan-Vercauteren) scheme. Also RNS-BFV was studied (Halevi et al., 2017) which is RNS variant of the BFV scheme and good results were obtained.
With the CRT (Chinese Remainder Theorem) we used to create the RNS variant, we ensure that the torus structure used in the scheme is reduced to smaller modules. Even if   reduction was performed for   in the study of discretized torus (Joye, 2021) which conducted to develop the scheme, this reduction alone is not sufficient to apply CRT. We are planning to contribute to the shortcomings of the TFHE scheme in terms of speed, time and memory by working on the   structure in this thesis by reducing the ciphertexts of the TFHE scheme based on learning with errors (LWE) with the help of CRT.
In cryptology, homomorphic encryption (HE) is an encryption scheme that allows a cloud service provider to do special computional operations over data when it's encrypted (Chauhan et al., 2015). A user can not do operations on data in cloud. To do operations, firstly the data should be downloaded and decrypted. Else, private key should be shared with service provider which is not safe. Generally, while encryption schemes can't carry out operations firstly without decrypting the ciphertext, homomorphic encryption allows carrying out operations on the ciphertext (Özdemir and Koç, 2022).
In this thesis, it is aimed to contribute to homomorphic encryption by applying the Residue Number System (RNS) variant, which improves schemes by applying it to many other homomorphic encryption schemes, to the TFHE (Torus Full Homomorphic Encryption) scheme, which has recently made a major breakthrough. In this context, it is aimed to reduce the computational load on the Torus Full Homomorphic Encryption (TFHE) algorithm, shorten processing times, and reduce resource usage. 
In order to eliminate the disadvantages of homomorphic encryption in our scientific studies within the scope of the thesis, the Chinese Remainder Theorem (CRT) will be applied to the TFHE scheme, unlike the studies in the literature, and improvement will be provided in terms of encryption time. The difference between the CRT to be used and the TFHE components and the space in which it works distinguishes it from other homomorphic encryption schemes. The Chinese Remainder Theorem (CRT) method will be used to apply RNS to the scheme. By applying RNS to the scheme, about 2 times more improvement has been achieved in the encryption and decryption times of the scheme.