CSCI 762 - An analysis of LAC, a lattice based post quantum encryption scheme.
The threat of quantum computing is steadily becoming bigger and bigger. NIST have recognized this and are holding a competition to find the best cryptographic schemes most resilient towards attacks from quantum computers. For the first round of this competition they have 69 entries to check and test. This paper analyzes and discusses an entry in this competition, LAC, which has four Lattice based cryptosystem schemes which promise a high resistance to most known attacks while also providing high flexibility in parameters.
In particular this paper focuses on looking at all four of LACs sub-cryptosystems titled as LAC.CPA, LAC.CCA, LAC.KE, and LAC.AKE. LAC.CPA is a Public Key encryption scheme and LAC.KE, a passively secure key exchange protocol directly converted from LAC.CPA. LAC.CCA is a secure key encapsulation method that is based on LAC.CPA. LAC.AKE is an authenticated key exchange protocol based on LAC.CPA & LAC.CCA. This paper mainly covers the public key schema, followed by a brief discussion on all of the subsystems in how they’re designed, with their inputs and outputs. The correctness of the algorithms, and how well they perform compared to other, more current non-quantum safe algorithms. After describing the subsystems the Quantum resistance of the algorithms will be discussed, along with LACs advantages and disadvantages, followed by the Conclusion.
- NIST: National Institute of Standards and Technology, a unit of the U.S. Commerce Department. Formerly known as the National Bureau of Standards, NIST promotes and maintains measurement standards.
- Polynomial Rings: Let R be a ring, then R[x] is a ring of polynomials in x with coefficients in R. More Formally R[x] consists of all polynomials.
- Basis: A set of n independent vectors is a basis of a vector space.
- Lattice: A lattice is the linear combination of independent vectors (basis vectors). It is a subset of the vector space with the operations of addition, subtraction, and multiplication by an integer.
- Rings: A ring is a set R under two binary operations, addition and multiplication. In order to be considered a Ring, the set must be an abelian group under addition and a monoid under multiplication
- Shortest Vector Problem: Given a basis of a lattice, the goal is to find the shortest non-zero vector in the lattice
- Learning With Errors (LWE): Given a basis B, and a linear combination of B plus some small noise, the Learning With Errors problem attempts to distinguish the resulting linear combination + noise from a completely random vector. This is an extension of the Learning From Parity with Errors
- Ring Learning With Errors (RLWE): Ring Learning With Errors is an extension of the Learning With Errors problem, where you treat the vectors as polynomials mod nthcyclotomic polynomial where n is a power of 2, and the polynomials are all elements of a Polynomial Ring.
Table of Contents (paper)
- NIST Competition
- Introduction to LAC
- Lattices: definitions and problems
- Shortest Vector Problem
- Learning with Errors
- Ring Learning with Errors
- LAC Cryptosystems
- Design Rationale
- Key Generation
- Public Key Scheme
- ECC Encoding/Decoding
- Other LAC Schemes
- Key Encapsulation Method
- Passivly Secure key authentication protocol
- Authenticated key exchange protocol
- Error Correcting Codes
- Quantum Resistance of LAC
- Advantages and Disadvantages
Link to paper(s)/References