Geri Dön

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ı

PDF İndir

  1. Tez No: 853976
  2. Yazar: ALİ ŞAH ÖZCAN
  3. Danışmanlar: PROF. DR. ERKAY SAVAŞ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Mühendislik ve Doğa Bilimleri Ana Bilim Dalı
  12. Bilim Dalı: Elektrik Bilim Dalı
  13. 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

  1. Tez No

    853975

    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

    İngilizce

    2023

    Elektrik ve Elektronik MühendisliğiSabancı Üniversitesi

    Mühendislik ve Doğa Bilimleri Ana Bilim Dalı

    PROF. DR. ERKAY SAVAŞ

  2. Tez No

    449254

    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

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Kriptografi Ana Bilim Dalı

    PROF. DR. ERSAN AKYILDIZ

    YRD. DOÇ. DR. SEDAT AKLEYLEK

  3. Tez No

    573362

    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

    Türkçe

    2019

    Elektrik ve Elektronik MühendisliğiHarran Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHMET EMİN TENEKECİ

  4. Tez No

    270166

    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

    Türkçe

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. KAYHAN İMRE

  5. Tez No

    384807

    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

    İngilizce

    2012

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    PROF. DR. FIRAT OĞUZ EDİS

Geri Dön