A GPU library for BFV homomorphic encryption scheme via three different ntt algorithms
Üç farklı hızlandırılmış ntt algortıması kullanarak BFV homomorfık şıfreleme şeması ıçın bır GPU kütüphanesı gelıştırılmesı
- Tez No: 853976
- Danışmanlar: PROF. DR. ERKAY SAVAŞ
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Mühendislik ve Doğa Bilimleri Ana Bilim Dalı
- Bilim Dalı: Elektrik Bilim Dalı
- Sayfa Sayısı: 91
Özet
Homomorfik şifreleme (İngilizcesi, homomorphic encryption, HE), şifrelenmiş verilerin güvenli bir şekilde işlenmesini sağlayan bir şifreleme sistemidir. En popüler HE şe- malarından biri, sınırlı (İngilizcesi, somewhat homomorphic encryption, SWHE) ve tama- men homomorfik şifrelemeyi (İnglizcesi, fully homomorphic encryption, FHE) destekleyen Brakerski-Fan-Vercauteren (BFV) adı verilen şifreleme sistemidir. HE şemalarının kar- maşık aritmetik işlemleri eşzamanlı hesaplamaya uygun olduğundan, grafik işlemci (GPU) cihazları, üstün paralel işleme kapasiteleri sayesinde HE algoritmalarının gerçek dünya uygulamalarında pratik kullanımını kolaylaştırmada etkili olabilir. Bu tezde, BFV şemasını hızlandırmak için optimize edilmiş ve yüksek derecede par- alelleştirilmiş bir GPU kütüphanesi öneriyoruz. BFV şeması, kafes tabanlı kriptografik (İngilizcesi, lattice-based encryption) sistemlere dayalıdır ve çok sayıda, katsayıları çok büyük tamsayılar olan yüksek dereceli polinom çarpmalarını içerir. GPU gerçek- lemelerinde yüksek dereceli polinomları çarpmak için klasik polinom çarpma yöntemi kullanıldığında çok verimsiz olduğundan, klasik yöntem yerine GPU cihazları için eniy- ilenmiş ve bir çeşit hızlı Fourier dönüşümü olan ve tam sayılar üzerinde çalışan sayılar teorisi dönüşümünü (İngilizcesi, number theoretic transformation, NTT) kullanan yön- temler tercih edilir. NTT işlemini hızlı gerçekleyebilmek için temel olarak iki yöntem vardır: i) birleştirilmiş yinelemeli NTT ve ii) 4-adımlı NTT yöntemleri. Bu tezde, bu iki yöntemi GPU için uyarlayarak üç farklı algoritma sunuyoruz. Bu tezde de görüle- ceği üzere, bu üç algoritma içinde en iyisi, i) iş parçacığı senkronizasyonu için yavaş ana belleğe erişim sayısını eniyileyip ve ii) ana bellek erişimlerinde mekânsal yerellikten daha iyi yararlanan algoritmadır. Bahsi geçen NTT algoritması, GPU üzerinde genel amaçlı yazılımlar geliştirilmesine olanak sağlayan CUDA platformunda çekirdek sayısı, blok boyutu ve blok şekli gibi belirli parametreleri kontrol ederek NTT başarımını olumlu yönde etkileyebilmektedir. Bilgimiz dahilinde olduğu kadar, bu çalışma, verilen bir poli- nom derecesi için en iyi NTT performansını elde etmek için en elverişli CUDA paramet- relerini seçmek için bir izlek öneren benzersiz bir çalışmadır. Literatürde bilinen en iyi GPU uygulamaları ile karşılaştırıldığında, 2^12 ila 2^28 arasındaki ikinin kuvveti olan tüm polinom dereceleri için çeşitli GPU cihazlarından elde ettiğimiz gerçekleme sonuçlarımız, algoritmamızın üstün bir başarım sağladığını göstermektedir. Üstelik geliştirdiğimiz NTT algoritması, çok yüksek halka boyutlarıyla çalışabildiğinden homomorfik şifreleme dışında sıfır bilgi ispatı adı verilen kriptografik protokollerde de kullanılabilir. Geliştirdiğimiz GPU yazılım kütüphanesi, ayrıca BFV şemasının homomorfik işlemlerinin başarımının da arttırılmasını sağlamaktadır. Geliştirdiğimiz kütüphane bağımsız olarak kullanılabildiği gibi, BFV sisteminin yanısıra diğer HE sistemlerinin de yazılım gerçek- lemelerini içeren ve çok kullanınılan Microsoft SEAL kütüphanesiyle tamamen entegre bir şekilde de kullanılabilir. 2^14 halka boyutu ve 438 bit uzunluğunda bir modül boyutu kullanıldığında, GPU gerçeklememiz bir şifreli metin çarpımı için, üst düzey bir CPU üzerinde çalışan SEAL kütüphanesine göre 361, 6 kat hızlanma sağlar. Geliştirilen GPU Kütüphanesi, NTT ve BFV işlemleri karşılatırıldığında, literatürdeki benzer GPU gerçek- lemelerine göre daha hızlıdır. Son olarak, GPU gerçeklememizi tümör türlerinin tespiti için şifrelenmiş genom verilerini sınıflandıran bir uygulamada denedik. GPU uygulamamız, bir ve 16 iş parçacığı kullanan CPU uygulamalarına göre, sırasıyla, 237.88 ve 36.08'lık hız artışları sağlamıştır. Sonuçlarımız, GPU gerçeklemelerimiz yardımıyla, homomorfik şifreleme sistemlerinin gerçek dünyadaki mahremiyet korumalı uygulamaların kullanımının yolunun açılmasına yardımcı olacağını göstermektedir.
Özet (Çeviri)
Homomorphic encryption (HE) is a cryptosystem that allows the secure processing of encrypted data. One of the most popular HE schemes is the Brakerski-Fan-Vercauteren (BFV), which supports somewhat (SWHE) and fully homomorphic encryption (FHE). Since overly involved arithmetic operations of HE schemes are amenable to concurrent computation, GPU devices can be instrumental in facilitating the practical use of HE in real world applications thanks to their superior parallel processing capacity. We propose an optimized and highly parallelized GPU library to accelerate the BFV scheme. The BFV scheme is based on lattice-based cryptography and involves overly many polynomial multiplications of very high degrees and multiprecision coefficients. Since, schoolbook polynomial multiplication is inefficient for GPU at high degrees, firstly, we present three different Number Theoretic Transform (NTT) implementations based on Merge NTT and 4-Step NTT algorithms that are optimized for GPUs instead of using schoolbook multiplicaition. The best of these three implementations employs an approach i) to optimize the number of accesses to slow global memory for thread synchronization, and ii) to make better use of spatial locality in global memory accesses. It turns out that by controlling certain parameters in CUDA platform for general-purpose GPU computing (GPGPU) such as kernel count, block size and block shape, we can affect the performance of NTT. To the best of our knowledge, this work is unique for it suggests a recipe for selecting optimum CUDA parameters to obtain the best NTT performance for a given polynomial degree. Our implementation results on various GPU devices for all power- of-two polynomial degrees from 2^12 to 2^28 show that our algorithms compare favorably with the other state-of-the-art GPU implementations in the literature with the optimum selection of these three CUDA parameters. Furthermore, NTT can also be used in Zero- Knowledge systems apart from Homomorphic Encryption because it can work with high ring sizes. The library also improves the performance of the homomorphic operations of the BFV scheme. Although the library can be independently used, it is also fully integrated with the Microsoft SEAL library, which is a well-known HE library that also implements the BFV scheme. For one ciphertext multiplication, for the ring dimension 2^14 and the modulus bit size of 438, our GPU implementation offers 361.6 times speedup over the SEAL library running on a high-end CPU. The library compares favorably with other state-of-the-art GPU implementations of NTT and BFV operations. Finally, we implement a privacy-preserving application that classifies encrypted genome data for tumor types and achieves speedups of 237.88 and 36.08 over CPU implementa- tions using single and 16 threads, respectively. Our results indicate that GPU implementations can facilitate the deployment of homomorphic cryptographic libraries in real-world privacy-preserving applications.
Benzer Tezler
- An accelerated GPU library for efficient homomorphic encryption operations in the CKKS scheme
CKKS şemasının homomorfik şifreleme işlemleri için hızlandırılmış verimli GPU kütüphanesi
ENES RECEP TÜRKOĞLU
Yüksek Lisans
İngilizce
2023
Elektrik ve Elektronik MühendisliğiSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
PROF. DR. ERKAY SAVAŞ
- On the efficiency of lattice-based cryptographic schemes on graphical processing unit
Grafik işlemci birimleri üzerinde kafes tabanlı kriptografıik şemaların uygulamalarının iyileştirilmesi
ZALİHA YÜCE TOK
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. ERSAN AKYILDIZ
YRD. DOÇ. DR. SEDAT AKLEYLEK
- Apache spark ve GPU'nun büyük veri analizinde kullanılması
Using Apache spark and GPU on big data analysis
MEHMET TURAN
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik MühendisliğiHarran ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MEHMET EMİN TENEKECİ
- Bir grafik işlemci (GPU) için MPI (message passing ınterface) yazılım kitaplığının tasarımı ve gerçekleştirimi
A design and implementation of MPI (message passing interface) library for a graphical processing unit (GPU)
İBRAHİM TANRIVERDİ
Yüksek Lisans
Türkçe
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. KAYHAN İMRE
- Computational fluid dynamics analysis using a high-order compact scheme on a GPU
Gpu üzerinde yüksek-mertebe kompakt şema kullanılarak hesaplamalı akışkanlar dinamiği analizi
BÜLENT TUTKUN
Doktora
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. FIRAT OĞUZ EDİS