Area-time product efficient RNS polynomial base extension on FPGA
Alan-zaman faktörü açısından verimli RNS polinom taban genişletme FPGA donanımı
- Tez No: 967856
- Danışmanlar: PROF. DR. ERKAY SAVAŞ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 71
Özet
Homomorfik Şifreleme (HE), şifreli metinler üzerinde hesaplama yaparak verilerin gizliliğini koruyan işlemler gerçekleştirmemizi sağlar. HE kullanımı, daha ölçeklenebilir hesaplama gücüne sahip üçüncü taraflara hesaplamayı devretmek için gereken güveni ortadan kaldırabilir. HE'nin daha pratik veri işlemlerinde benimsenmesinin önündeki engel, doğasında bulunan hesaplama karmaşıklığıdır. Brakerski-Fan-Vercauteren (BFV) gibi mevcut HE şemaları, daha fazla uygulamanın başarım gereksinimlerini karşılamak için gevşek bağlı hızlandırıcı cihazlar aracılığıyla hızlandırılabilir. HE için bir hızlandırıcı geliştirmek, Sayı Kuramsal Dönüşüm (NTT) gibi düzensiz bellek erişimlerine sahip algoritmaların gerçeklenmesini gerektirir. NTT algoritması hızlandırıldıktan sonra bile, ana bilgisayar ve cihaz arasındaki iletişim yükü bu hızlandırmanın bazı avantajlarını ortadan kaldırır. Daha fazla başarım artışı elde etmek için daha geniş bir aritmetik işlemler kümesinin hızlandırıcıda gerçeklenmesi gerekir. Bu tür işlemlerden biri de büyük tamsayılarla verimli işlemler gerçekleştirilmesi gerektiğinde kullanılan Kalıntı Sayı Sistemi (RNS) için taban genişletmedir. Örneğin, şifre metni için kullanılan modül $Q$, halka boyutu $N = 2^{16}$ ile 128 bit güvenlik seviyesini karşılamak için 1747-bit olarak seçilir. RNS kullanarak, gerekli parametreleri karşılamak için $28\times64$-bit asal sayı veya $55\times32$-bit asal sayı seçebiliriz. Homomorfik çarpma sırasında, sonuçlarımız mevcut RNS tabanının sağladığı aralığa sığmayabilir. Bu durumda, temsil aralığını artırmak için işlemden önce taban genişletmesi gerekir. Kapsamlı bir HE hızlandırıcısında, NTT birimi, hızlandırıcı cihazda homomorfik çarpma işlemlerini hesaplamak için taban genişletme birimi tarafından tüketilecek kalıntılar üretir ve bunun tersi de geçerlidir. Ana bilgisayara geri iletişim kurmayarak, veri taşıma ek yükleri önlenir. Taban genişletme gerçeklememiz, cihazın programlanabilir mantık alanı için rekabet eden birden fazla birime sahip HE hızlandırıcıları için Alan-Zaman Faktörü (ATP) ölçütü açısından eniyilenmiştir. Cihazda bulunan bellek bant genişliği parametrelerini kullanarak hatasız taban genişletme için derleme zamanında yapılandırılabilir bir donanım üreteci sunuyoruz. Tasarım, başarımı taban genişletme aritmetiğinden ayıran ölçeklenebilir bir mimariye sahiptir. Derleme zamanında ayarlanabilir bir iş hacmi parametresi, ek mantık alanı pahasına işlemin başarımını artırır. $2^{12}$ ile $2^{16}$ arasındaki halka boyutları için FPGA kullanım sonuçlarımızı sunuyoruz. Taban genişletme mimarimizi literatürde bulunan mimarilerle karşılaştırıyoruz. En son teknolojiye sahip açık kaynaklı HE yazılım kütüphanesi OpenFHE ile FPGA gerçeklememizi karşılaştırıyoruz ve gerçeklememizin yazılım gerçeklemesine göre $\times 10-17$ hız artışı sağladığını gösteriyoruz.
Özet (Çeviri)
Homomorphic Encryption (HE) allows us to perform privacy-preserving processing of data by computing on ciphertexts. Using HE can eliminate the trust required to offload computation to third parties that have more scalable computational power. A barrier to adopting HE in more practical processing of data is its inherent computational complexity. Current HE schemes such as Brakerski-Fan-Vercauteren (BFV) can be accelerated through loosely coupled accelerator devices to accommodate the performance requirements of even more applications. Developing an accelerator for HE requires implementation of algorithms that have irregular memory accesses, such as Number Theoretic Transform (NTT). Even after accelerating the NTT algorithm, the communication overhead between the host and the device offsets some of the benefits of this acceleration. To achieve further performance gains, the implementation of a larger set of arithmetic operations is required. One such operation is base extension, needed when the Residue Number System (RNS) is utilized to perform efficient arithmetic of larger integers. For example, the modulus used for the ciphertext $Q$ is chosen as 1747-bits to satisfy the 128-bit security level with ring dimension $N = 2^{16}$. Utilizing RNS, we can choose $28\times64$-bit primes or $55\times32$-bit primes to satisfy the required parameters. During homomorphic multiplication, our results may not fit within the range afforded by the current RNS base. Then, a base extension is required before the operation to increase the representation range. In a complete HE accelerator, the NTT unit produces residues that will be consumed by the base extension unit and vice versa to compute homomorphic multiplication operations on the accelerator device. By not communicating back to the host, the data movement overheads will be avoided. Our base extension implementation is optimized for its Area-Time Product (ATP) metric for HE accelerators that have multiple units competing for device programmable logic area. We present a compile-time configurable hardware generator for exact base extension with parameters for the available memory bandwidth on the device. The design features a scalable architecture that decouples performance from the underlying base extension arithmetic. A compile-time tunable throughput parameter can increase the performance of the operation at the cost of additional logic area. We provide our FPGA utilization results for ring sizes from $2^{12}$ to $2^{16}$. We compare our base extension architecture to architectures available in the literature. We demonstrate comparisons with the state-of-the-art open source HE software library OpenFHE against our FPGA implementation and show that our implementation achieves a $\times 10-17$ speedup over the software implementation.
Benzer Tezler
- An efficient hardware implementation of the tate pairing in characteristic three
Karakteristik üç üzerınde ?tate pairing? protokolunu uygulayan güçlü bır donanım tasarımı
GİRAY KÖMÜRCÜ
Yüksek Lisans
İngilizce
2008
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. ERKAY SAVAŞ
PROF. DR. GÜNHAN DÜNDAR
- Fast, compact and secure implementation of RSA on dedicated hardware
RSA algoritmasının donanım üzerine hızlı, az alan kaplayan ve güvenli uygulaması
ERSİN ÖKSÜZOĞLU
Yüksek Lisans
İngilizce
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
DOÇ. DR. ERKAY SAVAŞ
- Meme kanserinin ftır ve kemometri tekniği kullanımı ile erken teşhisi
Early diagnosis of breast cancer using ftir and chemometry technique
HİDAYET BENGİSU GEDİKLİ
Yüksek Lisans
Türkçe
2018
Kimya Mühendisliğiİstanbul Teknik ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ RAMAZAN KIZIL
- Development of mid-infrared coherent sources based on novel nonlinear devices
Doğrusal olmayan yöntemler kullanılarak kızılaltı bölgesinde çalışan laser kaynaklarının geliştirilmesi
MELİSA NATALİ ÇİZMECİYAN SÖZÜDOĞRU
Doktora
İngilizce
2014
Fizik ve Fizik MühendisliğiKoç ÜniversitesiMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
PROF. DR. ALPHAN SENNAROĞLU
- Yangın kompartımanlarının yalıtımında kullanılacak yangın durdurucuların seçimi için yöntem önerisi
A fire stopping product selection method for fire insulation of compartment barriers
İDİL TABAK
Yüksek Lisans
Türkçe
2015
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. NİHAL ARIOĞLU