Efficient implementation of lattice-based schemes

Download

12625778.pdf

Date

2020-10-14

Author

Bilgin, Yusuf Alper

Metadata

Show full item record

Item Usage Stats

482
views

571
downloads

Quantum computing and quantum computers have been discussed for almost three decades. However, they remain mainly in theory. Almost all big companies like Google, IBM, and Microsoft have put their effort to build the most scalable quantum computers in recent years. These computers can change the game in cryptography since the known hard problems such as integer factorization and discrete logarithms can be broken with a large-scale quantum computer. These computers would seriously jeopardize the confidentiality and integrity of all digital communications. The question of when large-scale quantum computers will be built is still an open question. There are some educated predictions that sufficiently large quantum computers will be built to break all public-key schemes currently in use within the next ten or so years. That is why the National Institute of Standards and Technology (NIST) has announced a standardization process in 2016 to prepare our information security systems to be able to resist in quantum computing. The first two rounds of this process have been completed, and there are seven on-going candidates and eight alternate candidates. Among these 15 schemes, seven of them are based on lattices. In this thesis, we study the efficient implementation of lattice-based schemes. We first propose an efficient and compact variant of NEWHOPE, one of the most efficient second-round candidates of the NIST post-quantum standardization project. The proposed algorithm NEWHOPE-COMPACT heavily uses recent advances on Number vii Theoretic Transform (NTT), so that transformation from one polynomial to another is easy. To make it possible, we changed the definition of a component in componentwise multiplication during polynomial multiplication and show that changing the security level only requires to change the size of the polynomial and the definition of a component. Then, we present various optimizations for lattice-based KEMs using the NTT on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of KYBER, one of the round three candidates in the NIST post-quantum project, NEWHOPE, and NEWHOPE-COMPACT.

Subject Keywords

Post-quantum cryptography, Lattice-based cryptography, Key encapsulation mechanism, Number theoretic transform, NTT, KEM, RLWE, MLWE, ARM Cortex-M4, KYBER, NEWHOPE, NEWHOPE-COMPACT

URI

https://hdl.handle.net/11511/69148

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

High performance number theoretic transforms in cryptography Ulu, Metin Evrim; Cenk, Murat; Department of Cryptography (2020) Theoretical advances in physics opened up a new window into quantum computation. This window rendered a number of mathematically hard problems unusable for cryptographic applications. For instance, Shor showed that it is possible factor integers by a quantum algorithm efficiently thus rendering the standard public-key encryption scheme RSA insecure. In February 2016, NIST launched a standardization process for post-quantum cryptography algorithms to study the effect of quantum computing on the current gener...
Quantum-resistant multivariate quadratic systems and digital signatures Altundağ, Esen; Cenk, Murat; Department of Cryptography (2019) In the light of technological advances, scientists expect that quantum computers will be generated and substitute with classical ones, then all symmetric and asymmetric (public-key) cryptosystems will be invalid in the near future. This causes the need for quantum-resistant algorithms all araund the world. That’s why, we have focused on multivariate public-key cryptosystems as a kind of post-quantum cryptography. In order to explain the root idea behind this kind of cryptosystems, as a starting point, the M...
Quantum safe digital signatures from symmetric key primitives Erbaş, Şeyma; Cenk, Murat; Department of Cryptography (2019) When powerful quantum computers are built, they will break most of the public key cryptography schemes due to Shor’s quantum algorithm. Therefore, public key cryptography algorithm schemes that is secure against classical and quantum computers are needed. In this thesis, we study Picnic algorithm, a post-quantum digital signature scheme. Picnic digital signature algorithm has the security of symmetric-key primitives that is considered to be secure against quantum attacks. In Picnic algorithm, zero knowledge...
Supporting Simulation Experiments with Megamodeling Cam, Sema; Dayibas, Orcun; Gorur, Bilge K.; Oğuztüzün, Mehmet Halit S.; Yilmaz, Levent; Chakladar, Sritika; Doud, Kyle; Smith, Alice E.; Teran-Somohano, Alejandro (SCITEPRESS, AV D MANUELL, 27A 2 ESQ, SETUBAL, 2910-595, PORTUGAL; 2018-01-01) Recent developments in computational science and engineering allow a great deal of experimental work to be conducted through computer simulation. In a simulation experiment, a model of the phenomena to be studied is run in a computing environment under varying model and environment settings. As models are adjusted to experimental procedures and execution environments, variations arise. Models also evolve in time. Thus, models must be managed. We propose to bring Global Model Management (GMM) to bear on simu...
Fast Algorithms for Digital Computation of Linear Canonical Transforms Koc, Aykut; Öktem, Sevinç Figen; Ozaktas, Haldun M.; Kutay, M. Alper (2016-01-01) Fast and accurate algorithms for digital computation of linear canonical transforms (LCTs) are discussed. Direct numerical integration takes O.N-2/time, where N is the number of samples. Designing fast and accurate algorithms that take O. N logN/time is of importance for practical utilization of LCTs. There are several approaches to designing fast algorithms. One approach is to decompose an arbitrary LCT into blocks, all of which have fast implementations, thus obtaining an overall fast algorithm. Another a...

Citation Formats

Y. A. Bilgin, “Efficient implementation of lattice-based schemes,” Ph.D. - Doctoral Program, Middle East Technical University, 2020.