Hierarchical NTT architectures on FPGA
FPGA üzerinde hiyerarşik STD yapıları
- Tez No: 929707
- 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: 2024
- 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ı: 59
Özet
Tam Homomorfik Şifreleme (Fully Homomorphic Encryption - FHE), kriptografi alanında bir paradigma değişimini temsil ederek, verilerin gizliliğini koruyarak şifreli veriler üzerinde doğrudan işlem yapılmasını mümkün kılmaktadır. Ancak, özellikle polinom çarpımları olmak üzere FHE işlemlerinde yer alan yüksek hesaplama karmaşıklığı, pratik kullanım için önemli bir engel teşkil etmektedir. Bu tez, FHE'nin bu zorluklarını ele almayı amaçlayarak, yüksek performanslı ve donanım hızlandırmalı mimariler geliştirmeye odaklanmaktadır. Özellikle, negatif döngüsel Sayı Teorisi Dönüşümü (negacyclic Number Theoretic Transform - NTT) işlemlerinin optimize edilmesi üzerine yoğunlaşılmıştır. Bu çalışmanın önemli katkılarından biri, programlanabilir donanım aracı olan FPGA üzerinde uygulanmak üzere özelleştirilmiş, verimlilik odaklı, hiyerarşik bir 7-adımlı NTT algoritmasının tanıtılmasıdır. Bu yaklaşım, polinom işlemlerinin hiyerarşik olarak bölünmesinden yararlanarak, negatif döngüsel NTT prensiplerini temel almış ve hesaplama verimliliğini artırmıştır. 4-adımlı NTT tasarımlarıyla karşılaştırıldığında, önerilen mimari daha üstün ölçeklenebilirlik ve kaynak verimliliği sunmakta ve 2^10 ile 2^16 arasında değişen polinom boyutlarını desteklemektedir. Modüler ve ardışık işleme dayalı donanım mimarisi sayesinde, bellek erişim darboğazları aşılmış ve bilimsel literatürdeki en iyi uygulamalara kıyasla NTT verimliliğinde önemli bir iyileşme sağlanmıştır. Hiyerarşik tasarım, sütun bağımsızlığı ve açılmış (unrolled) NTT döngüleri gibi gelişmiş teknikler kullanarak verimliliği en üst düzeye çıkarırken gecikmeyi en aza indirmektedir. Ayrıca, modüler indirgeme işlemleri, farklı güvenlik seviyeleri ve FHE parametreleriyle uyumluluğu mümkün kılan Kelime Temelli Montgomery (Word-Level Montgomery - WLM) yöntemlerini kullanmaktadır. Elde edilen sonuçlar, negatif döngüsel NTT tabanlı hiyerarşik tasarımların yüksek verimli şifreleme uygulamalarının pratikliğini artırdığını ve bu tasarımların gizliliği koruyan makine öğrenimi, şifreli veri tabanı sorguları ve güvenli bulut bilişim gibi alanlarda güvenli veri işleme uygulamalarının yapılabilirliğini kolaylaştırdığını göstermektedir. Önerilen tasarımımız, NTT işlemleri için bilimsel literatürdeki en iyi uygulamalara kıyasla önemli performans iyileştirmeleri sağlamaktadır; yüksek performanslı FPGA'larda ortalama gecikmede 8.14x hızlanma ve Alan-Zaman Ürünü (ATP) metriklerinde 4.01x iyileşme sunmaktadır. Bilimsel literatürdeki önde gelen çözümlerle karşılaştırıldığında, yedi adımlı mimarimiz, çeşitli halka boyutlarında (n=2^10 ile n=2^16 arasında) üstün işlem hacmi ve ölçeklenebilirlik göstererek, kaynak verimliliğini korurken 7.96x daha düşük gecikme sağlamaktadır. Ayrıca, tasarımımız çalışma zamanında yapılandırılabilir parametreleri destekleyerek pratik bir çözüm sunmaktadır.
Özet (Çeviri)
Fully Homomorphic Encryption (FHE) represents a paradigm shift in cryptography, enabling computations directly on encrypted data while preserving privacy. However, the computational complexity inherent in FHE operations, particularly polynomial multiplications, presents a significant barrier to practical adoption. This thesis focuses on addressing these challenges by developing high-performance, hardware-accelerated architectures for FHE, with a particular emphasis on the optimization of negacyclic Number Theoretic Transform (NTT) operations. The key contribution of this work is the introduction of a high speed, throughput-optimized, hierarchical 7-step NTT algorithm tailored for FPGA implementation. This approach builds on the negacyclic NTT method to enhance computational efficiency by leveraging hierarchical partitioning of polynomial operations. Compared to conventional 4-step NTT designs, the proposed architecture achieves superior scalability and resource efficiency, supporting polynomial sizes ranging from 2^10 to 2^16. By utilizing a modular and pipelined hardware architecture, the design overcomes memory access bottlenecks, achieving significant improvement in NTT throughput compared to state-of-the-art software implementations. The hierarchical design employs advanced techniques, including column independence and unrolled NTT stages, to maximize throughput while minimizing latency. Additionally, the modular reduction operations utilize Word-Level Montgomery (WLM) methods, enabling compatibility with varying security levels and FHE parameters. The results highlight the practicality of negacyclic NTT-based hierarchical designs in high-throughput cryptographic applications, facilitating secure data processing in domains such as privacy-preserving machine learning, encrypted database queries, and secure cloud computing. Our proposed design achieves significant performance improvements over state-of-the-art implementations for NTT operations, with up to 8.14x speed-up in average latency and 4.01x better Area-Time-Product (ATP) for high-performance FPGAs. Compared to leading solutions, our seven-step architecture demonstrates superior throughput and scalability across various ring dimensions (n=2^10 to n=2^16), offering up to 7.96x lower latency while maintaining resource efficiency. Furthermore, our design supports runtime-configurable parameters, making it a practical solution.
Benzer Tezler
- Hierarchical representations for visual object tracking by detection
Tespit ile görsel nesne takibi için sıradüzensel betimlemeler
BERİL BEŞBINAR
Yüksek Lisans
İngilizce
2015
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ABDULLAH AYDIN ALATAN
- Hiyerarşik lineer modeller ve bir uygulama
Hierarchical linear models and an application
SERPİL KILIÇ
Yüksek Lisans
Türkçe
2008
İstatistikYıldız Teknik Üniversitesiİstatistik Ana Bilim Dalı
YRD. DOÇ. DR. İBRAHİM DEMİR
- Hierarchical management of an integral production-logistics system
Bütünsel bir üretim-lojistik sisteminin hiyerarşik yönetimi
DEMET ÖZGÜR
Yüksek Lisans
İngilizce
1997
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. GÜLAY BARBAROSOĞLU
- Hierarchical planning in a global supply chain model
Başlık çevirisi yok
MİNE TEZER
Yüksek Lisans
İngilizce
1997
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiDOÇ. DR. GÜLAY BARBAROSOĞLU
- Hierarchical porous metal-organic frameworks (mofs): Design, synthesis, and their application as gas adsorption materials
Hiyerarşik gözenekli metal kafesli yapıların tasarımı, üretimi ve gaz adsorpsiyon çalışmalarında adsorban malzemeler olarak kullanımı
AYSU YURDUŞEN
Doktora
İngilizce
2020
Kimya MühendisliğiSabancı ÜniversitesiMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
PROF. DR. SELMİYE ALKAN GÜRSEL
DR. ÖĞR. ÜYESİ ALP YÜRÜM