Efficient hardware implementations for lattice-based cryptography primitives

Abstract

Kafes-tabanlı kriptografi, iki ana nedenden dolayı son yıllarda büyük ilgi görmektedir: $(i)$ kuantum bilgisayarlar tarafından gerçekleştirilecek saldırılara karşı dirençli olduğunun öngörülmesi ve $(ii)$ şifrelenmiş veriler üzerinde aritmetik operasyonlar yapılmasına izin veren homomorfik şifrelemeyi mümkün kılması. Sunduğu teorik avantajlara rağmen, özellikle homomorfik şifreleme bağlamında sahip olduğu yüksek hesaplama karmaşıklığı nedeniyle kafes-tabanlı kriptografik şemaların verimli ve pratik uygulamalarının eksikliği görülmektedir. Bu tezde temel amacımız, kafes-tabanlı kriptografi sistemleri için yüksek performanslı donanım çözümleri tasarlama ve gerçeklemektir.Bu amaçla, kafes-tabanlı homomorfik şifreleme ve kuantum sonrası kriptografi şemaları için verimli ve esnek donanım hızlandırıcılarını içeren çalışmaları sunmaktayız. İlk olarak, kafes-tabanlı kriptografinin temel yapı taşlarından biri olan Sayılar Teorisi Dönüşümü (NTT) için çeşitli optimizasyonlar içeren iki farklı donanım mimarisi sunuyoruz. Önerilen mimariler, Brakerski/Fan-Vercauteren (BFV) homomorfik şifreleme şemasının şifreleme ve şifre çözme operasyonlarını hızlandırmak için PCI Express bağlantısı ile hızlı iletişim sağlayan bir CPU-FPGA çerçevesinde kullanılmıştır. İkinci olarak, kafes-tabanlı kriptografi sistemlerinde sıklıkla kullanılan bir dizi algoritma parametresini destekleyen ve çalışma-zamanı yapılandırılabilir NTT tabanlı bir polinom çarpıcısı mimarisi sunulmuştur. Üçüncü çalışma olarak, BFV şemasının tam kalıntı sayı sistemi varyantındaki homomorfik çarpma ve yeniden doğrusallaştırma işlemlerini gerçekleştiren yüksek performanslı bir donanım mimarisin tasarımı ve gerçeklemesi sunulmuştur. Önerilen donanım mimarisi, son derece optimize edilmiş Microsoft SEAL homomorfik şifreleme kütüphanesi ile kıyaslandığında on kattan daha fazla performans iyileştirmesi göstermektedir. Dördüncü olarak, NIST tarafından başlatılan kuantum sonrası kriptografi standartlaştırma sürecinin finalistlerinden olan CRYSTALS-KYBER kuantum sonrası kriptografi şemasının polinom çarpıcısı mimarisinin FPGA platformu için ilk örneklerinden biri sunulmuştur. Son olarak, kapsamlı bir analizle birlikte esnek NTT donanımı oluşturmak için iki farklı tasarım yöntemini inceledik. İlk yöntem, derleme-zamanında yapılandırılabilir parametrik NTT donanım üretecini kullanırken, ikinci yöntem yüksek düzey sentez tabanlı tasarım yaklaşımını kullanmaktadır.

Lattice-based cryptography has gained a tremendous amount of attention in the last decade due to two main reasons: $(i)$ being projected to be resistant against the attacks by quantum computers and $(ii)$ enabling homomorphic encryption (HE) which allows arithmetic operations on the encrypted data. Despite its theoretical advantages, it lacks efficient and practical implementations due to its high computational complexity, especially in the context of HE. In this dissertation, our main objective is to design and implement high-performance and efficient hardware solutions for lattice-based cryptosystems.To that end, we propose a collection of efficient and flexible hardware accelerators for lattice-based HE and post-quantum cryptography (PQC) schemes. Firstly, we present two different hardware architectures for Number Theoretic Transform (NTT) which is one of the most fundamental building blocks of lattice-based cryptography with several optimizations. The proposed architectures are used in a CPU-FPGA framework providing fast communication via PCI Express link to accelerate the encryption and decryption operations of the Brakerski/Fan-Vercauteren (BFV) HE scheme. Secondly, we present a run-time configurable NTT-based polynomial multiplication architecture that supports a set of algorithm parameters frequently used in lattice-based cryptosystems. Thirdly, we design and implement a high-performance hardware architecture that performs the homomorphic multiplication and relinearization operations for the full RNS variant of the BFV HE scheme on FPGA. The proposed architecture outperforms the highly-optimized Microsoft SEAL HE library by more than an order of magnitude. Fourthly, we design and implement one of the earliest polynomial multiplication architectures of the CRYSTALS-Kyber PQC scheme, which is one of the finalists in NIST's PQC standardization process, for the FPGA platform in the literature. Finally, we investigate two different design methodologies for generating flexible NTT hardware along with a comprehensive analysis. The first method uses a compile-time configurable parametric NTT hardware generator while the second method presents the high-level synthesis approach.