Post quantum cryptography: homomorphic encryption

Abstract

This thesis presents a comprehensive analysis of Fully Homomorphic Encryption (FHE), a transformative advancement in contemporary cryptography. The exponential growth in digital data, coupled with the escalating demand for remote data processing, has elevated the importance of robust information security and privacy mechanisms. Homomorphic Encryption (HE) schemes facilitate the outsourcing of computations to untrusted third parties without exposing the underlying sensitive information, significantly enhancing data privacy assurances. Traditional encryption methods effectively protect data at rest and in transit; however, they inherently lack the capability to perform operations directly on encrypted data. FHE addresses this fundamental shortcoming by enabling intricate computations to be conducted on encrypted data without the necessity of decryption. The thesis begins by outlining the historical development of encryption systems and fundamental cryptographic concepts. It details the progression from the "privacy homomorphism" concept introduced by Rivest, Adleman, and Dertouzos in 1978 to Craig Gentry's seminal work in 2009, which presented the first practical FHE scheme. The key milestones in the evolution of FHE and major contributions in the literature are presented from both theoretical and practical perspectives. Subsequently, the mathematical structures and concepts underlying FHE are discussed in depth. Topics such as lattices, rings and fields, polynomials, number fields, canonical embedding, and ideal structures are examined as the foundational building blocks ensuring the security of FHE. In particular, challenging problems provided by Lattice-Based Cryptography, such as Learning with Errors (LWE), serve as the mathematical basis for FHE's resistance to attacks. The thesis also analyzes the structure, functioning, and differences between modern FHE schemes (such as Brakerski, Gentry and Vaikuntanathan (BGV), Fan and Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS)). The practical applications, advantages, limitations, and recent optimization techniques of these schemes are thoroughly examined. Special attention is given to the opportunities FHE offers in sectors where data privacy is paramount, including healthcare, finance, and cloud computing. Key practical challenges such as high computational costs, large key and ciphertext sizes, and noise management are highlighted. Innovations to address these challenges, including hardware accelerators, software optimizations, and open-source libraries (like HELib and SEAL), are explored in detail. The thesis also covers contemporary research areas such as multi-key FHE, privacy-preserving computation in artificial intelligence, and post-quantum cryptography. In conclusion, this thesis presents a broad perspective on FHE, covering its mathematical foundations and practical application potential, while evaluating current developments, limitations, and future research directions. The wider and more efficient xxv adoption of FHE will open new possibilities for information security and privacy. In this context, the thesis aims to serve as a comprehensive resource for both academic and industrial communities. Keywords: Bootstrapping, Relinearization, Ring Learning with Errors, BGV, BFV, CKKS.Günümüzde dijital verinin hızla çoğalması ve uzaktan veri işleme ihtiyaçlarının artması, bilgi güvenliği ve gizliliğini korumayı kritik bir gereklilik haline getirmiştir. Klasik şifreleme teknikleri, verinin saklanması ve iletimi sırasında koruma sağlarken, şifreli veri üzerinde işlem yapmaya imkân tanımaz. Homomorfik şifreleme, şifrelenmiş veriler üzerinde çözme işlemi gerektirmeden, toplama veya çarpma işlemlerinin uygulanmasını mümkün kılarak veri gizliliği sağlayan bir şifreleme modelidir. Tam homomorfik şifreleme modeli ise hem toplama hem de çarpma işlemlerini destekleyerek şifreli metinler üzerinde karmaşık hesapların yapılmasını mümkün kılan ve tamsayılarla sınırlı kalmadan daha geniş sayı kümelerinin kullanılmasına imkan veren bir homomorfik şifreleme modelidir. Bu çalışmanın odak noktası, modern kriptografi alanında büyük bir yenilik olan Tam Homomorfik Şifreleme (FHE) yönteminin teorik temellerini ve pratik uygulamalarının kapsamlı bir şekilde incelenmesidir. Tez çalışması 5 ana bölümden oluşmaktadır. Birinci bölümde, şifreleme sistemlerinin tarihsel gelişimi ve temel kriptografik kavramlar açıklanmıştır. 1978'de Rivest, Adleman ve Dertouzos'un ortaya attığı "privacy homomorphism" kavramından, Craig Gentry'nin 2009'da sunduğu ilk pratik FHE şemasına kadar geçen süreç detaylandırılmıştır. FHE'nin gelişimindeki önemli kilometre taşları ve literatürdeki başlıca katkılar, hem teorik hem de uygulamalı yönleriyle sunulmuştur. İkinci bölümde, FHE'nin temelini oluşturan matematiksel yapılar ve kavramlar örnekleriyle verilmiştir. Üçüncü bölümde, Tam Homomorfik Şifreleme (FHE) yapılarının güvenliğini sağlayan matematiksel temeller ayrıntılı biçimde ele alınmıştır. Bu kapsamda, FHE'nin yapı taşlarını olan kafesler, halka ve alanlar, polinomlar, sayı alanları, kanonik gömme ve ideal yapıları gibi cebirsel kavramlar, ayrıntılı biçimde incelenmiştir. Ayrıca, Kafes Tabanlı Kriptografi'nin sunduğu Learning with Errors (LWE) ve Approximate GCD gibi çözülmesi zor problemler, FHE'nin saldırılara karşı dayanıklılığını sağlayan temel güvenlik varsayımları olarak sunulmuştur. Dördüncü bölümde bilinen Homomorfik şifreleme şemaları ve temel kavramları tanıtıldıktan sonra bunların karşılaştırmalı sınıflandırılmaları verilmiştir. xxvii Tezin son bölümünü oluşturan 5. Bölümde ise modern FHE şemalarının (BGV, BFV, CKKS vb.) yapısı, işleyişi ve aralarındaki farklar analiz edilmiştir. Bu şemaların uygulama alanları, avantajları, kısıtları ve güncel optimizasyon teknikleri ele alınmıştır. Özellikle sağlık, finans ve bulut bilişim gibi veri gizliliğinin ön planda olduğu sektörlerde FHE'nin sunduğu fırsatlar örneklerle açıklanmıştır. Pratikte karşılaşılan başlıca zorluklar arasında, yüksek hesaplama maliyetleri, büyük anahtar ve şifreleme boyutları ile gürültü yönetimi gibi unsurlar öne çıkmaktadır. Tezde, bu zorlukların üstesinden gelmek için geliştirilen donanım tabanlı hızlandırıcılar, yazılım optimizasyonları ve açık kaynak kütüphaneler (HELib, SEAL vb.) gibi yenilikler detaylı olarak incelenmiştir. Ayrıca, çok anahtarlı FHE, yapay zekâda mahremiyet koruyucu hesaplama ve kuantum sonrası kriptografi gibi güncel araştırma alanlarına da yer verilmiştir. Sonuç olarak, bu tez, FHE'nin matematiksel temelinden pratik uygulama potansiyeline kadar geniş bir perspektif sunmakta ve bu alandaki güncel gelişmeleri, mevcut sınırlamaları ve gelecekteki araştırma yönelimlerini değerlendirmektedir. FHE'nin daha yaygın ve verimli hale gelmesi, bilgi güvenliği ve mahremiyet açısından yeni olanaklar yaratacaktır. Bu bağlamda tez, akademik ve endüstriyel çevrelere kapsamlı bir kaynak olmayı hedeflemektedir. Anahtar Kelimeler: Bootstrapping, Relinerizasyon, Halka da Hata ile Ögrenme, BGV, BFV, CKKS.