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

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. 


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...
A Hierarchical Architecture for Nonblocking Control of Discrete Event Systems
Schmidt, Klaus Verner; PERK, SEBASTIAN (2006-03-13)
This contribution investigates the hierarchical control of decentralized DES which are synchronized by shared events. A multi-level hierarchical control architecture providing hierarchical consistency is introduced. Moreover, it allows for composition of decentralized subsystems on the high-level of the hierarchy, and hence reduces the computational complexity of supervisory control synthesis for language inclusion specifications. In this context, a crucial issue is the nonblocking operation of the overall ...
Keskinkurt Paksoy, İrem; Cenk, Murat; Department of Cryptography (2022-7-28)
One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardizati...
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 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...
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.