Hamid Nejatollahi
Nikil Dutt
ABSTRACT
Advances in computing steadily erode computer security at its foundation, calling for fundamental innovations to strengthen the weakening cryptographic primitives and security protocols. At the same time, the emergence of new computing paradigms, such as Cloud Computing and Internet of Everything, demand that innovations in security extend beyond their foundational aspects, to the actual design and deployment of these primitives and protocols while satisfying emerging design constraints such as latency, compactness, energy efficiency, and agility. While many alternatives have been proposed for symmetric key cryptography and related protocols (e.g., lightweight ciphers and authenticated encryption), the alternatives for public key cryptography are limited to post-quantum cryptography primitives and their protocols. In particular, lattice-based cryptography is a promising candidate, both in terms of foundational properties, as well as its application to traditional security problems such as key exchange, digital signature, and encryption/decryption. We summarize trends in lattice-based cryptographic schemes, some fundamental recent proposals for the use of lattices in computer security, challenges for their implementation in software and hardware, and emerging needs.
- M. Ajtai. Generating Hard Instances of Lattice Problems. STOC '96.Google Scholar
- R. Avanzi. The QARMA Block Cipher Family. Almost MDS Matrices Over Rings With Zero Divisors, Nearly Symmetric Even-Mansour Constructions With Non-Involutory Central Rounds, and Search Heuristics for Low-Latency S-Boxes IACR Trans. Symmetric Cryptol. 2017.Google Scholar
- C. Gentry et al. Trapdoors for Hard Lattices and New Cryptographic constructions. STOC '08.Google Scholar
- D.J. Bernstein et al. Post-quantum RSA. Cryptology ePrint Archive, Report 2017/351.Google Scholar
- D. Micciancio et al. Lattice-based Cryptography. PQC '09.Google Scholar
- E. Alkim et al. Post-quantum Key Eexchange - a New Hope. Cryptology ePrint Archive, Report 2015/1092.Google Scholar
- H. Nejatollahi et al. Implementations of Lattice-based Cryptography: A Survey. UCICECS-TR-17--04.Google Scholar
- J. Buchmann et al. Discrete Ziggurat: A Time-Memory Trade-Off for Sampling from a Gaussian Distribution over the Integers. SAC '13.Google Scholar
- J. Bos et al. Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE. CCS '16.Google Scholar
- J. Borghoff et al. PRINCE - A Low-Latency Block Cipher for Pervasive Computing Applications. ASIACRYPT 2012. Google ScholarDigital Library
- J. Howe et al. Lattice-based Encryption Over Standard Lattices in Hardware. DAC '16.Google Scholar
- L. Ducas et al. Lattice Signatures and Bimodal Gaussians. Cryptology ePrint Archive, Report 2013/383.Google Scholar
- O. Garcia-Morchon et al. DTLS-HIMMO: Achieving DTLS Certificate Security with Symmetric Key Overhead. ESORICS 2015.Google Scholar
- T Oder et al. Lattice-based Cryptography: From Reconfigurable Hardware to ASIC. ISIC '16.Google Scholar
- T. Pöppelmann et al. Enhanced Lattice-based Signatures on Reconfigurable Hardware. CHES '14.Google Scholar
- V. Lyubashevsky et al. On Ideal Lattices and Learning With Errors Over Rings. EUROCRYPT '10.Google Scholar
- C. F. Gauss. Disquisitiones Arithmeticae. (English Translation) Springer 1986.Google Scholar
- L. K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. STOC '96.Google Scholar
- D. E. Knuth and A. C. Yao. The Complexity of Nonuniform Random Number Generation. Algorithms and Complexity 1976.Google Scholar
- H. Nussbaumer. Fast Polynomial Transform Algorithms for Digital Convolution. IEEE Trans. Acoust. Speech 1980.Google Scholar
- C. Peikert. A Decade of Lattice Cryptography. Cryptology ePrint Archive, Report 2015/939.Google Scholar
- C. Peikert. An efficient and Parallel Gaussian Sampler for Lattices. Cryptology ePrint Archive, Report 2010/088.Google Scholar
- O. Regev. On lattices, Learning With Errors, Random Linear Codes, and Cryptography. STOC '05.Google Scholar
- P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (October 1997). Google ScholarDigital Library
- V. Singh. A Practical Key Exchange for the Internet using Lattice Cryptography. Cryptology ePrint Archive, Report 2015/138.Google Scholar
- J. von Neumann. Various Techniques Used in Connection With Random Digits. J. Res. Nat. Bur. Stand. 1951.Google Scholar
Recommendations
Practical Lattice-Based Digital Signature Schemes
Special Issue on Embedded Platforms for Crypto and Regular PapersDigital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the ...
Post-Quantum Lattice-Based Cryptography Implementations: A Survey
The advent of quantum computing threatens to break many classical cryptographic schemes, leading to innovations in public key cryptography that focus on post-quantum cryptography primitives and protocols resistant to quantum computing threats. Lattice-...
Lattice-based certificateless encryption scheme
Certificateless public key cryptography (CL-PKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does ...
Comments