On the efficiency of lattice-based cryptographic schemes on graphical processing unit

Abstract

Kuantum hesaplamaya dirençli açık anahtarlı sistemlere alternatif olan kafes tabanlı kriptografi asimptotik verimliliğinden dolayı büyük ilgi görmektedir. Bununla birlikte, pratikte bunu kullanabilmek için bazı engeller bulunmaktadır: şema tabanlı aritmetik işlemler ve platform tabanlı uygulamalar. Bu tez çalışmasında, kafes tabanlı kriptografik protokollerden NTRU ve GLP'nin CPU ve grafik işlem birimleri (GPU) üzerindeki zaman karmaşıklıklarını hesaplama açısından tartıştık. Burada, polinom çarpımının hem uygulama hem de teorik açıdan iyileştirilmesi üzerine durduk. İdeal kafesler için aralanmış Montgomery modüler çarpma algoritmasının güncellenmesi, seyrek polinomların çarpma algoritmasını ve bunun kayan pencere tekniğini verimli uygulamalar için önerdik. Önerilen algoritmalar ile kafes tabanlı kriptografik şemaların performans sonu ̧clarının iyileştirildiğini gösterdik. Ayrıca, ilkokul yöntemi, NTT gibi bilinen çarpma algoritmalarını paralel bir şekilde uyguladık ve seçilen kafes tabanlı kriptografik şemalar için GPU'da çalışan bir CUDA yazılım kütüphanesi oluşturduk.

Lattice-based cryptography, a quantum-resistant public key alternative, has re- ceived a lot of attention due to the asymptotic efficiency. However, there is a bot- tleneck to get this advantage on practice: scheme-based arithmetic operations and platform-based implementations. In this thesis, we discuss computational aspects of lattice-based cryptographic schemes focused on NTRU and GLP in view of the time complexity on both CPUs and Graphical Processing Units (GPU). We fo- cus on the optimization of polynomial multiplication methods both on theoretical and implementation point of view. We propose a modified version of interleaved Montgomery modular multiplication algorithm for ideal lattices, sparse polyno- mial multiplication and its sliding window version for efficient implementations. We show that with the proposed algorithms we significantly improve the perfor- mance results of lattice-based signature schemes. We also implement parallelized version of well known polynomial multiplication algorithms such as schoolbook method, NTT by using CUDA and provide a library for selected lattice-based signature schemes on a GPU.