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

Download
2016
Yüce Tok, Zaliha
Lattice-based cryptography, a quantum-resistant public key alternative, has received a lot of attention due to the asymptotic efficiency. However, there is a bottleneck 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 focus 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 polynomial multiplication and its sliding window version for efficient implementations. We show that with the proposed algorithms we significantly improve the performance 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. 

Suggestions

An approach for decentralized process modeling
Turetken, Oktay; Demirörs, Onur (2007-05-20)
This paper describes a method for organizations to perform process modeling in a decentralized and concurrent manner. The approach is based on the idea that modeling organizations' processes can be performed by individuals actually performing the processes. Instead of having a central and devoted group of people to analyze, understand, model and improve processes, real performers are held responsible to model and improve their own processes concurrently. The paper also summarizes the lessons learned by appl...
On some cryptographic properties of Rijndael
Kavut, S; Yucel, MD (2001-01-01)
We examine diffusion properties of Rijndael which has been selected by US National Institute of Standards and Technology (NIST) for the proposed Advanced Encryption Standard (AES). Since the s-box of Rijndael applies a nonlinear transformation operating on each byte of the intermediate cipher result independently, its characteristics have significant effects on the strength of the entire system. The characteristics of Rijndael's s-box are investigated for the criteria of avalanche, strict avalanche, bit ind...
An integrated approach to computational vision - The edge strength function and the nested symmetries
Tarı, Zehra Sibel (1999-01-01)
A new development in local symmetry extraction and its connections to segmentation functionals and the fronts propagating with curvature-dependent speed are examined. The basic tool is a new distance function that attains its maximum value at the shape boundary and decays rapidly away from there. It is shown that the Hessian of the distance function captures perceptual information that can be extracted easily, efficiently, and robustly in the form of nested local shape symmetries at multiple scales. The mos...
On lattice based digital signature schemes
Javani, Farid; Akyıldız, Ersan; Department of Cryptography (2014)
Lattice based cryptography is one of the few hopes for secure public key cryptography in post quantum era since there is no known polynomial time quantum algorithm that can solve hard lattice problems. But despite this precious property, for a cryptographic construction which is designed based on a hard lattice problem, to be secure, required time and space is not efficient. This has led to introduction of structured lattices that need less time and space; indeed the only existing standard on lattice based ...
Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat; Department of Cryptography (2022-2-28)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptography (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type {Z}_{q}[x] / f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC S...
Citation Formats
Z. Yüce Tok, “On the efficiency of lattice-based cryptographic schemes on graphical processing unit,” Ph.D. - Doctoral Program, Middle East Technical University, 2016.