Abstract
We present an overview of quantum-safe cryptography (QSC) with a focus on post-quantum cryptography (PQC) and information-theoretic security. From a cryptographic point of view, lattice and code-based schemes are among the most promising PQC solutions. Both approaches are based on the hardness of decoding problems of linear codes with different metrics. From an information-theoretic point of view, lattices and linear codes can be constructed to achieve certain secrecy quantities for wiretap channels as is intrinsically classical- and quantum-safe. Historically, coding theory and cryptography are intimately connected since Shannon’s pioneering studies but have somehow diverged later. QSC offers an opportunity to rebuild the synergy of the two areas, hopefully leading to further development beyond the NIST PQC standardization process. In this paper, we provide a survey of lattice and code designs that are believed to be quantum-safe in the area of cryptography or coding theory. The interplay and similarities between the two areas are discussed. We also conclude our understandings and prospects of future research after NIST PQC standardisation.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, New York, 2005. 84–93
Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. J ACM, 2013, 60: 43
Lyubashevsky V, Peikert C, Regev O. A toolkit for ring-lwe cryptography. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2013. 35–54
Peikert C. Lattice cryptography for the Internet. In: Proceedings of International Workshop on Post-quantum Cryptography, 2014. 197–219
D’Anvers J P, Guo Q, Johansson T, et al. Decryption failure attacks on ind-cca secure lattice-based schemes. In: Proceedings of IACR International Workshop on Public Key Cryptography, 2019. 565–598
D’Anvers J P, Rossi M, Virdia F. (One) failure is not an option: bootstrapping the search for failures in lattice-based encryption schemes. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2020. 3–33
Guo Q, Johansson T, Yang J. A novel CCA attack using decryption errors against LAC. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2019. 82–111
Fritzmann T, Pöppelmann T, Sepulveda J. Analysis of error-correcting codes for lattice-based key exchange. In: Proceedings of International Conference on Selected Areas in Cryptography, 2019. 369–390
D’Anvers J P, Vercauteren F, Verbauwhede I. The impact of error dependencies on ring/mod-LWE/LWR based schemes. In: Proceedings of International Conference on Post-Quantum Cryptography, 2019. 103–115
Wang J B, Ling C. Polar coding for ring-LWE-based public key encryption. 2021. https://eprint.iacr.org/2021/619.pdf
Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008. 197–206
Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2012. 700–718
Wang Z, Ling C. On the geometric ergodicity of metropolis-hastings algorithms for lattice gaussian sampling. IEEE Trans Inform Theor, 2018, 64: 738–751
Wang Z, Ling C. Lattice Gaussian sampling by Markov Chain Monte Carlo: bounded distance decoding and trapdoor sampling. IEEE Trans Inform Theor, 2019, 65: 3630–3645
Lyubashevsky V. Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2009. 598–616
Lyubashevsky V. Lattice signatures without trapdoors. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2012. 738–755
Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal gaussians. In: Proceedings of Annual Cryptology Conference, 2013. 40–56
Peikert C. An efficient and parallel Gaussian sampler for lattices. In: Proceedings of Annual Cryptology Conference, 2010. 80–97
Ducas L, Prest T. Fast fourier orthogonalization. In: Proceedings of ACM on International Symposium on Symbolic and Algebraic Computation, New York, 2016. 191–198
Micciancio D, Walter M. Gaussian sampling over the integers: efficient, generic, constant-time. In: Proceedings of Annual International Cryptology Conference, 2017. 455–485
Zhao R K, Steinfeld R, Sakzad A. FACCT: fast, compact, and constant-time discrete Gaussian sampler over integers. IEEE Trans Comput, 2020, 69: 126–137
Wang J B, Ling C. Polar sampler: discrete gaussian sampling over the integers using polar codes. 2019. https://eprint.iacr.org/2019/674.pdf
McEliece R J. A Public-key Cryptosystem Based on Algebraic Coding Theory. The Deep Space Network Progress Report, 1978. 114–116
Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory. Prob Control Inf Theory, 1986, 15: 159–166
Berlekamp E, McEliece R, van Tilborg H. On the inherent intractability of certain coding problems (Corresp.). IEEE Trans Inform Theor, 1978, 24: 384–386
Gaborit P. Shorter keys for code based cryptography. In: Proceedings of International Workshop on Coding and Cryptography (WCC), 2005. 81–91
Misoczki R, Tillich J P, Sendrier N, et al. MDPC-mceliece: new mceliece variants from moderate density parity-check codes. In: Proceedings of IEEE International Symposium on Information Theory, 2013. 2069–2073
Guo Q, Johansson T, Stankovski P. A key recovery attack on MDPC with CCA security using decoding errors. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2016. 789–815
Gaborit P, Zémor G. On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans Inform Theor, 2016, 62: 7245–7252
Bardet M, Bros M, Cabarcas D, et al. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2020. 507–536
Courtois N T, Finiasz M, Sendrier N. How to achieve a mceliece-based digital signature scheme. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2001. 157–174
Debris-Alazard T, Sendrier N, Tillich J P. Wave: a new family of trapdoor one-way preimage sampleable functions based on codes. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2019. 21–51
Gaborit P, Ruatta O, Schrek J, et al. New results for rank-based cryptography. In: Proceedings of International Conference on Cryptology in Africa, 2014. 1–12
Faugère J C, Gauthier-Umaña V, Otmani A, et al. A distinguisher for high rate mceliece cryptosystems. In: Proceedings of IEEE Information Theory Workshop, 2011. 282–286
Debris-Alazard T, Tillich J P. Two attacks on rank metric code-based schemes: ranksign and an IBE scheme. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2018. 62–92
Persichetti E. Efficient one-time signatures from quasi-cyclic codes: a full treatment. Cryptography, 2018, 2: 30
Deneuville J C, Gaborit P. Cryptanalysis of a code-based one-time signature. Des Codes Cryptogr, 2020, 88: 1857–1866
Fukushima K, Sarathi Roy P, Xu R, et al. Racoss: random code-based signature scheme. 2017. https://csrc.nist.gov/Projects/post-quantum-cryptography/Round-1-Submissions
Aragon N, Blazy O, Gaborit P, et al. Durandal: a rank metric based signature scheme. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2019. 728–758
Micciancio D, Goldwasser S. Complexity of Lattice Problems. Berlin: Springer, 2002
Nguyen P Q, Vallée B. The LLL Algorithm: Survey and Applications. Belin: Springer, 2010
Feng C, Silva D, Kschischang F R. An algebraic approach to physical-layer network coding. IEEE Trans Inform Theor, 2013, 59: 7576–7596
Wubben D, Seethaler D, Jalden J, et al. Lattice reduction. IEEE Signal Process Mag, 2011, 28: 70–91
Lenstra A K, Lenstra Jr H W, Lovász L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515–534
Schnorr C P, Euchner M. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math Program, 1994, 66: 181–199
Chang X W, Yang X, Zhou T. MLAMBDA: a modified LAMBDA method for integer least-squares estimation. J Geodesy, 2005, 79: 552–565
Lyu S, Ling C. Boosted KZ and LLL algorithms. IEEE Trans Signal Process, 2017, 65: 4784–4796
Chen Y M, Nguyen P Q. BKZ 2.0: better lattice security estimates. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2011. 1–20
Lagarias J C, Lenstra Jr H W, Schnorr C P. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 1990, 10: 333–348
Minkowski H. Diskontinuitätsbereich für arithmetische.äquivalenz. Journal für die reine und angewandte Mathematik, 1905, 129: 220–224
Li J W, Nguyen P Q. A complete analysis of the BKZ lattice reduction algorithm. 2020. https://eprint.iacr.org/2020/1237.pdf
Aggarwal D, Li J W, Nguyen P Q, et al. Slide reduction, revisited — filling the gaps in SVP approximation. In: Proceedings of Annual International Cryptology Conference, 201
Lyu S, Porter C, Ling C. Lattice reduction over imaginary quadratic fields. IEEE Trans Signal Process, 2020, 68: 6380–6393
Gan Y H, Ling C, Mow W H. Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection. IEEE Trans Signal Process, 2009, 57: 2701–2710
Tunali N E, Huang Y C, Boutros J J, et al. Lattices over eisenstein integers for compute-and-forward. IEEE Trans Inform Theor, 2015, 61: 5306–5321
Huang Y C, Narayanan K R, Wang P C. Lattices over algebraic integers with an application to compute-and-forward. IEEE Trans Inform Theor, 2018, 64: 6863–6877
Stern S, Fischer R F H. Lattice-reduction-aided precoding for coded modulation over algebraic signal constellations. In: Proceedings of the 20th International ITG Workshop on Smart Antennas, Munich, 2016. 1–8
Napias H. A generalization of the LLL-algorithm over euclidean rings or orders. J de Théorie des Nombres de Bordeaux, 1996, 8: 387–396
Fieker C, Pohst M. On lattices over number fields. In: Proceedings of Algorithmic Number Theory, Second International Symposium, 1996. 133–139
Kim T, Lee C. Lattice reductions over Euclidean rings with applications to cryptanalysis. In: Proceedings of IMA International Conference on Cryptography and Coding, 2017. 371–391
Lee C, Pellet-Mary A, Stehlé D, et al. An LLL algorithm for module lattices. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2019. 59–90
Mukherjee T, Stephens-Davidowitz N. Lattice reduction for modules, or how to reduce moduleSVP to moduleSVP. In: Proceedings of Annual International Cryptology Conference, 2020. 213–242
Wyner A D. The wire-tap channel. Bell Syst Technical J, 1975, 54: 1355–1387
Csiszár I. Almost independence and secrecy capacity. Probl Inform Transm, 1996, 32: 48–57
Erez U, Zamir R. Achieving 1/2 log (1+SNR) on the AWGN channel with lattice encoding and decoding. IEEE Trans Inform Theor, 2004, 50: 2293–2314
Ling C, Luzzi L, Belfiore J C, et al. Semantically secure lattice codes for the Gaussian wiretap channel. IEEE Trans Inform Theor, 2014, 60: 6399–6416
Liu L, Yan Y F, Ling C. Achieving secrecy capacity of the gaussian wiretap channel with polar lattices. IEEE Trans Inform Theor, 2018, 64: 1647–1665
Loeliger H A. Averaging bounds for lattices and linear codes. IEEE Trans Inform Theor, 1997, 43: 1767–1773
Forney G D, Trott M D, Chung S Y. Sphere-bound-achieving coset codes and multilevel coset codes. IEEE Trans Inform Theor, 2000, 46: 820–850
Arikan E. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans Inform Theor, 2009, 55: 3051–3073
Sadeghi M R, Banihashemi A H, Panario D. Low-density parity-check lattices: construction and decoding analysis. IEEE Trans Inform Theor, 2006, 52: 4481–4495
Suresh A T, Subramanian A, Thangaraj A, et al. Strong secrecy for erasure wiretap channels. In: Proceedings of Information Theory Workshop (ITW), 2010. 1–5
Thangaraj A, Dihidar S, Calderbank A R, et al. Applications of LDPC codes to the wiretap channel. IEEE Trans Inform Theor, 2007, 53: 2933–2945
Bloch M, Barros J. Physical-Layer Security: From Information Theory to Security Engineering. Cambridge: Cambridge University Press, 2011
Rathi V, Andersson M, Thobaben R, et al. Performance analysis and design of two edge-type LDPC codes for the BEC wiretap channel. IEEE Trans Inform Theor, 2013, 59: 1048–1064
Rathi V, Urbanke R, Andersson M, et al. Rate-equivocation optimal spatially coupled LDPC codes for the BEC wiretap channel. In: Proceedings of Information Theory Proceedings (ISIT), 2011. 2393–2397
Andersson M, Rathi V, Thobaben R, et al. Nested polar codes for wiretap and relay channels. IEEE Commun Lett, 2010, 14: 752–754
Mahdavifar H, Vardy A. Achieving the secrecy capacity of wiretap channels using polar codes. IEEE Trans Inform Theor, 2011, 57: 6428–6443
Sasoglu E, Vardy A. A new polar coding scheme for strong security on wiretap channels. In: Proceedings of Information Theory Proceedings (ISIT), 2013. 1117–1121
Renes J M, Renner R, Sutter D. Efficient one-way secret-key agreement and private channel coding via polarization. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2013. 194–213
Hussami N, Korada S B, Urbanke R. Polar codes for channel and source coding. 2009. ArXiv:0901.2370
Klinc D, Ha J, McLaughlin S W, et al. LDPC codes for the Gaussian wiretap channel. IEEE Trans Inform Forensic Secur, 2011, 6: 532–540
Baldi M, Bianchi M, Chiaraluce F. Coding with scrambling, concatenation, and HARQ for the AWGN wire-tap channel: a security gap analysis. IEEE Trans Inform Forensic Secur, 2012, 7: 883–894
Yin L G, Hao W T. Code-hopping based transmission scheme for wireless physical-layer security. Wirel Commun Mobile Comput, 2018, 2018: 1–12
Chen Z, Yin L G, Pei Y K, et al. CodeHop: physical layer error correction and encryption with LDPC-based code hopping. Sci China Inf Sci, 2016, 59: 102309
Acknowledgements
This work was supported by U.K. Engineering and Physical Sciences Research Council (Grant No. EP/S021-043/1) and National Natural Science Foundation of China (Grant Nos. 61871257, 61902149).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Wang, J., Liu, L., Lyu, S. et al. Quantum-safe cryptography: crossroads of coding theory and cryptography. Sci. China Inf. Sci. 65, 111301 (2022). https://doi.org/10.1007/s11432-021-3354-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-021-3354-7