A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption
Preprint
Abstract
Why study Lattice-based Cryptography? There are a few ways to answer this question. 1. It is useful to have cryptosystems that are based on a variety of hard computational problems so the different cryptosystems are not all vulnerable in the same way. 2. The computational aspects of lattice-based cryptosystem are usually simple to understand and fairly easy to implement in practice. 3. Lattice-based cryptosystems have lower encryption/decryption computational complexities compared to popular cryptosystems that are based on the integer factorisation or the discrete logarithm problems. 4. Lattice-based cryptosystems enjoy strong worst-case hardness security proofs based on approximate versions of known NP-hard lattice problems. 5. Lattice-based cryptosystems are believed to be good candidates for post-quantum cryptography, since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best-known classical (non-quantum) algorithms, unlike for integer factorisation and (elliptic curve) discrete logarithm problems. 6. Last but not least, interesting structures in lattice problems have led to significant advances in Homomorphic Encryption, a new research area with wide-ranging applications.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Homomorphic Encryption for Machine Learning in Medicine and BioinformaticsACM Computing Surveys, 2020
- (Leveled) Fully Homomorphic Encryption without BootstrappingACM Transactions on Computation Theory, 2014
- Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$SIAM Journal on Computing, 2014
- The Learning with Errors Problem (Invited Survey)2010
- Computing arbitrary functions of encrypted dataCommunications of the ACM, 2010
- On lattices, learning with errors, random linear codes, and cryptographyJournal of the ACM, 2009
- Worst‐Case to Average‐Case Reductions Based on Gaussian MeasuresSIAM Journal on Computing, 2007
- Hardness of approximating the shortest vector problem in latticesJournal of the ACM, 2005
- Introductory Algebraic Number Theory2003
- Sur les formes quadratiquesMathematische Annalen, 1873