skip to main content
research-article

Lattice-based Key-sharing Schemes: A Survey

Published: 02 January 2021 Publication History
  • Get Citation Alerts
  • Abstract

    Public-key cryptography is an indispensable component used in almost all of our present-day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large-scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global-level standardization process for quantum resistant public-key cryptographic primitives such as public-key encryption, digital signatures, and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this article, we survey the evolution of lattice-based key-sharing schemes (public-key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects, and physical attack security, with special focus on lattice-based key-sharing schemes competing in the NIST’s standardization process.

    Supplementary Material

    a9-ravi-supp.pdf (ravi.zip)
    Supplemental movie, appendix, image and software files for, Lattice-based Key-sharing Schemes: A Survey

    References

    [1]
    Eric Rescorla. 2015. The Transport Layer Security (TLS) Protocol Version 1.3 draft-ietf-tls-tls13-07. Retrieved from https://tools.ietf.org/html/draft-ietf-tls-tls13-07.
    [2]
    Eric Rescorla. 2016. The Transport Layer Security (TLS) Protocol Version 1.3 draft-ietf-tls-tls13-13. Retrieved from https://tools.ietf.org/html/draft-ietf-tls-tls13-13.
    [3]
    Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. 2015. Solving the shortest vector problem in 2 n time using discrete Gaussian sampling. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing. ACM, 733--742.
    [4]
    Miklós Ajtai. 1996. Generating hard instances of lattice problems. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 99--108.
    [5]
    Gorjan Alagic, Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta et al. 2019. Status Report on the First Round of the NIST Post-quantum Cryptography Standardization Process. U.S. Department of Commerce, National Institute of Standards and Technology.
    [6]
    Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. 2018. Estimate all the {LWE, NTRU} schemes! In Proceedings of the International Conference on Security and Cryptography for Networks. Springer, 351--367.
    [7]
    Erdem Alkim, Roberto Avanzi, Joppe W. Bos, Leo Ducas, Antonio de la Piedra, Thomas Poppelmann, Peter Schwabe, and Douglas Stebila [n.d.]. NewHope (Version 1.1): Algorithm specifications and supporting documentation. Retrieved from https://newhopecrypto.org/data/NewHope_2020_04_10.pdf.
    [8]
    Erdem Alkim, Joppe W. Bos, Leo Ducas, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila [n.d.]. Frodo: Algorithm specifications and supporting documentation. Retrieved from https://frodokem.org/files/FrodoKEM-specification-20200325.pdf.
    [9]
    Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. 2016. Newhope without reconciliation. IACR ePrint. Retrieved from https://eprint.iacr.org/2016/1157.
    [10]
    Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. 2016. Post-quantum key exchange—A new hope. In Proceedings of the USENIX Security Symposium. 327--343.
    [11]
    Erdem Alkim, Philipp Jakubeit, and Peter Schwabe. 2016. NewHope on ARM Cortex-M. In Proceedings of the International Conference on Security, Privacy, and Applied Cryptography Engineering. Springer, 332--349.
    [12]
    Roberto Avanzi, Joppe Bos, Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, John Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé [n.d.]. CRYSTALS-Kyber (version 2.0) - Algorithm specifications and supporting documentation. Retrieved from https://pq-crystals.org/kyber/data/kyber-specification-round2.pdf.
    [13]
    Aydin Aysu, Michael Orshansky, and Mohit Tiwari. 2018. Binary Ring-LWE hardware with power side-channel countermeasures. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE’18). IEEE, 1253--1258.
    [14]
    Aydin Aysu, Cameron Patterson, and Patrick Schaumont. 2013. Low-cost and area-efficient FPGA implementations of lattice-based cryptography. In Proceedings of the IEEE International Symposium on Hardware-Oriented Security and Trust (HOST’13).
    [15]
    Aydin Aysu, Youssef Tobah, Mohit Tiwari, Andreas Gerstlauer, and Michael Orshansky. 2018. Horizontal side-channel vulnerabilities of post-quantum key-exchange protocols. In Proceedings of the IEEE International Symposium on Hardware Oriented Security and Trust (HOST’18). IEEE, 81--88.
    [16]
    Hayo Baan, Sauvik Bhattacharya, Scott Fluhrer, Oscar Garcia-Morchon Garcia-Morchon, Thijs Laarhoven, Rachel Player, Ronald Rietman, Markku-Juhani O. Saarinen, Ludo Tolhuizen, Jos’e Luis Torre-Arce, and Zhenfei Zhang. [n.d.]. Round5: Algorithm specifications and supporting documentation. Retrieved from https://round5.org/doc/Round5_Submission042020.pdf.
    [17]
    Ciprian Băetu, F. Betül Durak, Loïs Huguenin-Dumittan, Abdullah Talayhan, and Serge Vaudenay. 2019. Misuse attacks on post-quantum cryptosystems. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 747--776.
    [18]
    Daniel V. Bailey, Daniel Coffin, Adam Elbirt, Joseph H. Silverman, and Adam D. Woodbury. 2001. NTRU in constrained devices. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems. Springer, 262--272.
    [19]
    Abhishek Banerjee, Chris Peikert, and Alon Rosen. 2012. Pseudorandom functions and lattices. In Proceedings of the Conference on Advances in Cryptology (EUROCRYPT’12). 719--737.
    [20]
    Utsav Banerjee, Tenzin S. Ukyab, and Anantha P. Chandrakasan. 2019. Sapphire: A configurable crypto-processor for post-quantum lattice-based protocols. Retrieved from https://arXiv:1910.07557.
    [21]
    Paul Barrett. 1986. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Proceedings of the Conference on the Theory and Application of Cryptographic Techniques. Springer, 311--323.
    [22]
    Kanad Basu, Deepraj Soni, Mohammed Nabeel, and Ramesh Karri. 2019. NIST post-quantum cryptography-A hardware evaluation study. IACR ePrint Archive. https://eprint.iacr.org/2019/047.
    [23]
    Aurélie Bauer, Henri Gilbert, Guénaël Renault, and Mélissa Rossi. 2019. Assessment of the key-reuse resilience of NewHope. In Proceedings of the Cryptographers’ Track at the RSA Conference. Springer, 272--292.
    [24]
    Daniel J. Bernstein. 2006. Curve25519: New Diffie-Hellman speed records. In Proceedings of the International Workshop on Public Key Cryptography. Springer, 207--228.
    [25]
    Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. [n.d.]. NTRU Prime: Algorithm specifications and supporting documentation. Retrieved from https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf.
    [26]
    Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. 2017. NTRU prime: Reducing attack surface at low cost. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 235--260.
    [27]
    Daniel J. Bernstein, Tanja Lange, and Dan Page. [n.d.]. eBATS. ECRYPT Benchmarking of Asymmetric Systems: Performing Benchmarks (technical report).
    [28]
    Daniel J. Bernstein and Edoardo Persichetti. 2018. Towards KEM unification. IACR ePrint Archive. https://eprint.iacr.org/2018/526.
    [29]
    Daniel J. Bernstein and Bo-Yin Yang. 2019. Fast constant-time gcd computation and modular inversion. IACR Trans. Cryptogr. Hardware Embed. Syst. 2019 (2019), 340--398. https://doi.org/10.13154/tches.v2019.i3.340-398.
    [30]
    Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. 2009. Keccak specifications. Submission to NIST (Round 2) (2009), 320--337.
    [31]
    Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, and Ludo Tolhuizen. 2017. spKEX: An optimized lattice-based key exchange. IACR EPrint Archive (2017). Retrieved from https://eprint.iacr.org/2017/709.
    [32]
    David Blackman and Sebastiano Vigna. 2018. Scrambled linear pseudorandom number generators. Retrieved from https://arXiv:1805.01407.
    [33]
    Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. 2016. Frodo: Take off the ring! practical, quantum-secure key exchange from LWE. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. ACM, 1006--1018.
    [34]
    Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. 2016. Frodo: Take off the ring! practical, quantum-secure key exchange from LWE. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. ACM, 1006--1018.
    [35]
    Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2018. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In Proceedings of the IEEE European Symposium on Security and Privacy (EuroS8P’18). IEEE, 353--367.
    [36]
    Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. 2015. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In Proceedings of the IEEE Symposium on Security and Privacy (SP’15). IEEE.
    [37]
    Joppe W. Bos, Simon Friedberger, Marco Martinoli, Elisabeth Oswald, and Martijn Stam. 2018. Assessing the feasibility of single trace power analysis of Frodo. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer.
    [38]
    Joppe W. Bos, Simon Friedberger, Marco Martinoli, Elisabeth Oswald, and Martijn Stam. 2018. Fly, you fool! Faster Frodo for the ARM Cortex-M4.IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2018/1116.
    [39]
    Leon Botros, Matthias J. Kannwischer, and Peter Schwabe. 2019. Memory-efficient high-speed implementation of Kyber on Cortex-M4. In Proceedings of the International Conference on Cryptology in Africa. Springer, 209--228.
    [40]
    Matt Braithwaite. 2016. Experimenting with post-quantum cryptography. Google Security Blog 7 (2016).
    [41]
    Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6, 3 (2014), 13.
    [42]
    Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. 2013. Classical hardness of learning with errors. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. ACM, 575--584.
    [43]
    Jacqueline Brendel, Marc Fischlin, Felix Günther, Christian Janson, and Douglas Stebila. 2019. Challenges in proving post-quantum key exchanges based on key encapsulation mechanisms.
    [44]
    Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. 2016. Flush, Gauss, and Reload–a cache attack on the BLISS lattice-based signature scheme. In Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems. Springer, 323--345.
    [45]
    Johannes Buchmann, Daniel Cabarcas, Florian Göpfert, Andreas Hülsing, and Patrick Weiden. 2013. Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 402--417.
    [46]
    Johannes Buchmann, Florian Göpfert, Tim Güneysu, Tobias Oder, and Thomas Pöppelmann. 2016. High-performance and lightweight lattice-based public-key encryption. In Proceedings of the 2nd ACM International Workshop on IoT Privacy, Trust, and Security. ACM, 2--9.
    [47]
    CESG. 2016. Quantum Key Distribution. Retrieved from https://www.cesg.gov.uk/white-papers/quantum-key-distribution.
    [48]
    Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas Hülsing, Joost Rijneveld, John M Schanck, Peter Schwabe, William Whyte, and Zhenfei Zhang. [n.d.]. NTRU: Algorithm specifications and supporting documentation. Retrieved from https://ntru.org/f/ntru-20190330.pdf.
    [49]
    Donald Donglong Chen, Nele Mentens, Frederik Vercauteren, Sujoy Sinha Roy, Ray C. C. Cheung, Derek Pao, and Ingrid Verbauwhede. 2015. High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. IEEE Trans. Circ. Syst. I: Reg. Papers 62, 1 (2015), 157--166.
    [50]
    Jung Hee Cheon, Kyoohyung Han, Jinsu Kim, Changmin Lee, and Yongha Son. 2016. A practical post-quantum public-key cryptosystem based on spLWE. In Proceedings of the International Conference on Information Security and Cryptology. Springer, 51--74.
    [51]
    Robert Chien. 1964. Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes. IEEE Trans. Info. Theory 10, 4 (1964), 357--363.
    [52]
    CNSS. 2015. Use of Public Standards for the Secure Sharing of Information Among National Security Systems. Committee on National Security Systems: CNSS Advisory Memorandum, Information Assurance 02-15.
    [53]
    James Cooley and John Tukey. 1965. An algorithm for the machine calculation of complex fourier series. Math. Comp. 19, 90 (1965), 297--301.
    [54]
    Don Coppersmith and Adi Shamir. 1997. Lattice attacks on NTRU. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 52--61.
    [55]
    Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. 2017. Short stickelberger class relations and application to Ideal-SVP. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer.
    [56]
    Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. [n.d.]. Saber: Algorithm specifications and supporting documentation (round 2). Retrieved from https://www.esat.kuleuven.be/cosic/pqcrypto/saber/resources.html.
    [57]
    Jan-Pieter D’Anvers, Frederik Vercauteren, and Ingrid Verbauwhede. 2018. On the impact of decryption failures on the security of LWE/LWR based schemes. IACR ePrint Archive (2018). Retrieved from https://eprint.iacr.org/2018/1089.
    [58]
    Ruan De Clercq, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2015. Efficient software implementation of Ring-LWE encryption. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE’15). IEEE.
    [59]
    Jintai Ding, Saed Alsayigh, R. V. Saraswathy, Scott Fluhrer, and Xiaodong Lin. 2017. Leakage of signal function with reused keys in RLWE key exchange. In Proceedings of the IEEE International Conference on Communications (ICC’17). IEEE, 1--6.
    [60]
    Jintai Ding, Chi Cheng, and Yue Qin. 2019. A simple key reuse attack on LWE and ring LWE encryption schemes as key encapsulation mechanisms (KEMs). IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2019/271.
    [61]
    Jintai Ding, Scott Fluhrer, and R. V. Saraswathy. 2018. Complete attack on RLWE key exchange with reused keys, without signal leakage. In Proceedings of the Australasian Conference on Information Security and Privacy. Springer, 467--486.
    [62]
    Jintai Ding, Xiang Xie, and Xiaodong Lin. 2012. A simple provably secure key-exchange scheme based on the learning with errors problem. IACR EPrint Archive. Retrieved from https://eprint.iacr.org/2012/688.
    [63]
    Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. 2013. Lattice signatures and bimodal Gaussians. In Proceedings of the Conference on Advances in Cryptology (CRYPTO’13). Springer, 40--56.
    [64]
    Jan-Pieter D’Anvers, Marcel Tiepelt, Frederik Vercauteren, and Ingrid Verbauwhede. 2019. Timing attacks on error correcting codes in post-quantum schemes. In Proceedings of the ACM Workshop on Theory of Implementation Security Workshop. ACM, 2--9.
    [65]
    Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. 2016. Loop abort faults on lattice-based Fiat-Shamir 8 Hash’n sign signatures. IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2016/449.
    [66]
    Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. 2017. Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security.
    [67]
    Viet Ba Dang, Farnoud Farahmand, Michal Andrzejczak, Kamyar Mohajerani, Duc Tri Nguyen, and Kris Gaj. 2008. Implementation and benchmarking of round 2 candidates in the NIST post-quantum cryptography standardization process using hardware and software/hardware Co-design approaches. IACR EPrint Archive (2008). Retrieved from https://eprint.iacr.org/2020/795/20200627:185511.
    [68]
    Farnoud Farahmand, Viet B. Dang, Duc Tri Nguyen, and Kris Gaj. 2019. Evaluating the potential for hardware acceleration of four NTRU-based key encapsulation mechanisms using software/hardware codesign. In Proceedings of the International Conference on Post-Quantum Cryptography. Springer, 23--43.
    [69]
    Scott R. Fluhrer. 2016. Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR ePrint Archive (2016). Retrieved from https://eprint.iacr.org/2016/085.
    [70]
    Tim Fritzmann, Thomas Pöppelmann, and Johanna Sepulveda. 2018. Analysis of error-correcting codes for lattice-based key exchange. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 369--390.
    [71]
    Tim Fritzmann and Johanna Sepúlveda. 2019. Efficient and flexible low-power NTT for lattice-based cryptography. In Proceedings of the IEEE International Symposium on Hardware Oriented Security and Trust (HOST’19).
    [72]
    Tim Fritzmann, Uzair Sharif, Daniel Müller-Gritschneder, Cezar Reinbrecht, Ulf Schlichtmann, and Johanna Sepulveda. 2019. Towards reliable and secure post-quantum co-processors based on RISC-V. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE’19). IEEE, 1148--1153.
    [73]
    Eiichiro Fujisaki and Tatsuaki Okamoto. 1999. Secure integration of asymmetric and symmetric encryption schemes. In Proceedings of the Annual International Cryptology Conference. Springer, 537--554.
    [74]
    Robert Gallager. 1962. Low-density parity-check codes. IRE Trans. Info. Theory 8, 1 (1962), 21--28.
    [75]
    Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, 197--206.
    [76]
    Chunsheng Gu. 2019. Integer version of ring-LWE and its applications. In Proceedings of the International Symposium on Security and Privacy in Social Networks and Big Data. Springer, 110--122.
    [77]
    Shay Gueron and Fabian Schlieker. 2016. Speeding up R-LWE post-quantum key exchange. In Proceedings of the Nordic Conference on Secure IT Systems. Springer, 187--198.
    [78]
    Mike Hamburg. [n.d.]. ThreeBears: Algorithm specifications and supporting documentation. Retrieved from https://www.shiftleft.org/papers/threebears/threebears-july2019.pdf.
    [79]
    Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman. 1998. NTRU: A ring-based public key cryptosystem. Algor. Number Theory (1998), 267--288.
    [80]
    James Howe, Ayesha Khalid, Marco Martinoli, Francesco Regazzoni, and Elisabeth Oswald. 2019. Fault attack countermeasures for error samplers in lattice-based cryptography. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’19). IEEE, 1--5.
    [81]
    James Howe, Ayesha Khalid, Ciara Rafferty, Francesco Regazzoni, and Máire O’Neill. 2016. On practical discrete Gaussian samplers for lattice-based cryptography. IEEE Trans. Comput. (2016).
    [82]
    James Howe, Ciara Moore, Máire O’Neill, Francesco Regazzoni, Tim Güneysu, and Kevin Beeden. 2016. Lattice-based encryption over standard lattices in hardware. In Proceedings of the 53rd Annual Design Automation Conference. ACM.
    [83]
    James Howe, Tobias Oder, Markus Krausz, and Tim Güneysu. 2018. Standard lattice-based key encapsulation on embedded devices. IACR Trans. Cryptogr. Hardware Embed. Syst. 2018, 3 (2018), 372--393. https://doi.org/10.13154/tches.v2018.i3.372-393
    [84]
    James Howe, Thomas Pöppelmann, Máire O’Neill, Elizabeth O’Sullivan, and Tim Güneysu. 2015. Practical lattice-based digital signature schemes. ACM Trans. Embed. Comput. Syst. 14, 3 (2015), 41.
    [85]
    Nick Howgrave-Graham. 2007. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In Proceedings of the Annual International Cryptology Conference. Springer, 150--169.
    [86]
    Nick Howgrave-Graham, Phong Q. Nguyen, David Pointcheval, John Proos, Joseph H. Silverman, Ari Singer, and William Whyte. 2003. The impact of decryption failures on the security of NTRU encryption. In Proceedings of the Annual International Cryptology Conference. Springer, 226--246.
    [87]
    Nick Howgrave-Graham, Joseph H. Silverman, Ari Singer, William Whyte, and NTRU Cryptosystems. 2003. NAEP: Provable security in the presence of decryption failures. IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2003/172.
    [88]
    Wei-Lun Huang, Jiun-Peng Chen, and Bo-Yin Yang. 2020. Power analysis on NTRU prime. IACR Trans. Cryptogr. Hardware Embed. Syst. 2020, 1 (2020), 123--151. https://doi.org/10.13154/tches.v2020.i1.123-151
    [89]
    Andreas Hülsing, Joost Rijneveld, John Schanck, and Peter Schwabe. 2017. High-speed key encapsulation from NTRU. In Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems. Springer, 232--252.
    [90]
    Arpan Jati, Naina Gupta, Somitra Kumar Sanadhya, and Anupam Chattopadhyay. 2019. SPQCop: Side-channel protected post-quantum cryptoprocessor. IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2019/765.
    [91]
    Éliane Jaulmes and Antoine Joux. 2000. A chosen-ciphertext attack against NTRU. In Proceedings of the Annual International Cryptology Conference. Springer, 20--35.
    [92]
    Burton S. Kaliski. 1995. The Montgomery inverse and its applications. IEEE Trans. Comput. 44, 8 (1995).
    [93]
    Abdel Alim Kamal and Amr Youssef. 2011. Fault analysis of the NTRUEncrypt cryptosystem. IEICE Trans. Fund. Electr. Commun. Comput. Sci. 94, 4 (2011), 1156--1158.
    [94]
    Abdel Alim Kamal and Amr M. Youssef. 2009. An FPGA implementation of the NTRUEncrypt cryptosystem. In Proceedings of the International Conference on Microelectronics (ICM’09). IEEE, 209--212.
    [95]
    Abdel Alim Kamal and Amr M. Youssef. 2013. Strengthening hardware implementations of NTRUEncrypt against fault analysis attacks. J. Cryptogr. Eng. 3, 4 (2013), 227--240.
    [96]
    Panos Kampanakis and Dimitrios Sikeridis. 2019. Two post-quantum signature use-cases: Non-issues, challenges and potential solutions. IACR ePrint Archive (2019). Retrieved from https://eprint.iacr.org/2019/1276.
    [97]
    Matthias J. Kannwischer, Joost Rijneveld, and Peter Schwabe. 2018. Faster multiplication in Z2m [x] on cortex-M4 to speed up NIST PQC candidates. IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2018/1018
    [98]
    Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. 2019. pqm4: Testing and benchmarking NIST PQC on ARM Cortex-M4. Retrieved from https://github.com/mupq/pqm4/tree/c32bcd017b202d418c9135e2df77be73a69044a0.
    [99]
    Anatolii Karatsuba. 1963. Multiplication of multidigit numbers on automata. In Sov. Phys. Dokl., Vol. 7. 595--596.
    [100]
    Angshuman Karmakar, Jose Maria Bermudo Mera, Sujoy Sinha Roy, and Ingrid Verbauwhede. 2018. Saber on ARM. CCA-secure module lattice-based key encapsulation on ARM. IACR Trans. Cryptogr. Hardware Embed. Syst. 2018, 3 (2018), 243--266. https://doi.org/10.13154/tches.v2018.i3.243-266
    [101]
    Paul Kirchner and Pierre-Alain Fouque. 2017. Revisiting lattice attacks on overstretched NTRU parameters. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 3--26.
    [102]
    Donald Ervin Knuth. 1998. The Art of Computer Programming: Sorting and Searching. Vol. 3. Pearson Education.
    [103]
    Donald E. Knuth and Andrew C. Yao. 1976. The complexity of nonuniform random number generation. In Algorithms and Complexity: New Directions and Recent Results. Academic Press, 357--428.
    [104]
    Po-Chun Kuo, Wen-Ding Li, Yu-Wei Chen, Yuan-Che Hsu, Bo-Yuan Peng, Chen-Mou Cheng, and Bo-Yin Yang. 2017. Post-quantum key exchange on FPGAs. IACR ePrint Archive (2017). Retrieved from https://eprint.iacr.org/2017/690.
    [105]
    Adam Langley. [n.d.]. Post-quantum confidentiality for TLS. Retrieved from https://www.imperialviolet.org/2018/04/11/pqconftls.html.
    [106]
    Adam Langley. [n.d.]. Real-world measurements of structured-lattices and supersingular isogenies in TLS. Retrieved from https://www.imperialviolet.org/.
    [107]
    Adeline Langlois and Damien Stehlé. 2015. Worst-case to average-case reductions for module lattices. Designs, Codes Cryptogr. 75, 3 (2015), 565--599.
    [108]
    Mun-Kyu Lee, Jung Woo Kim, Jeong Eun Song, and Kunsoo Park. 2007. Sliding window method for NTRU. In Applied Cryptography and Network Security. Springer, 432--442.
    [109]
    Mun-Kyu Lee, Jeong Eun Song, Dooho Choi, and Dong-Guk Han. 2010. Countermeasures against power analysis attacks for the NTRU public key cryptosystem. IEICE Trans. Fund. Electron. Commun. Comput. Sci. 93, 1 (2010), 153--163.
    [110]
    Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 4 (1982), 515--534.
    [111]
    Richard Lindner and Chris Peikert. 2011. Better key sizes (and attacks) for LWE-based encryption. In Proceedings of the Cryptographer’s Track at RSA Conference (CT-RSA’11).
    [112]
    Bingxin Liu and Huapeng Wu. 2015. Efficient architecture and implementation for NTRUEncrypt system. In Proceedings of the IEEE 58th International Midwest Symposium on Circuits and Systems (MWSCAS’15). IEEE, 1--4.
    [113]
    Bingxin Liu and Huapeng Wu. 2016. Efficient multiplication architecture over truncated polynomial ring for NTRUEncrypt system. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’16). IEEE, 1174--1177.
    [114]
    Zhe Liu and Johann Großschädl. 2014. New speed records for Montgomery modular multiplication on 8-bit AVR microcontrollers. In Proceedings of the International Conference on Cryptology in Africa. Springer, 215--234.
    [115]
    Xianhui Lu, Yamin Liu, Dingding Jia, Haiyang Xue, Jingnan He, Zhenfei Zhang, Zhe Liu, Hao Yang, Bao Li, and Kunpeng Wang. 2018. LAC: Practical ring-LWE based public-key encryption with byte-level modulus. IACR ePrint Archive (2018). Retrieved from https://eprint.iacr.org/2018/1009.
    [116]
    Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On ideal lattices and learning with errors over rings. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10). 1--23.
    [117]
    Vadim Lyubashevsky and Gregor Seiler. 2019. NTTRU: Truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardware Embed. Syst. 2019, 3 (2019), 180--201. https://doi.org/10.13154/tches.v2019.i3.180-201
    [118]
    Daniele Micciancio. 2010. Duality in lattice cryptography. In Public Key Cryptography. Springer, 2.
    [119]
    Masoud Mohseni, Peter Read, Hartmut Neven, Sergio Boixo, Vasil Denchev, Ryan Babbush, Austin Fowler, Vadim Smelyanskiy, and John Martinis. 2017. Commercialize quantum technologies in five years. Nature News 543, 7644 (2017), 171.
    [120]
    Peter L Montgomery. 1985. Modular multiplication without trial division. Math. Comput. 44, 170 (1985).
    [121]
    Michele Mosca and Douglas Stebila. 2017. Open quantum safe. Software for Prototyping Quantum-resistant Cryptography. Open Quantum Safe.
    [122]
    Hamid Nejatollahi, Nikil Dutt, Sandip Ray, Francesco Regazzoni, Indranil Banerjee, and Rosario Cammarota. 2019. Post-quantum lattice-based cryptography implementations: A survey. ACM Comput. Surveys 51, 6 (2019).
    [123]
    Phong Q. Nguyen and David Pointcheval. 2002. Analysis and improvements of NTRU encryption paddings. In Proceedings of the Annual International Cryptology Conference. Springer, 210--225.
    [124]
    NIST. 2016. Post-Quantum Crypto Project. Retrieved from http://csrc.nist.gov/groups/ST/post-quantum-crypto/.
    [125]
    Tobias Oder and Tim Güneysu. 2017. Implementing the NewHope-simple key exchange on low-cost FPGAs. In Proceedings of the Conference on Progress in Cryptology (LATINCRYPT’17).
    [126]
    Tobias Oder, Tobias Schneider, Thomas Pöppelmann, and Tim Güneysu. 2018. Practical CCA2-secure and masked ring-LWE implementation. IACR Trans. Cryptogr. Hardware Embed. Syst. 2018, 1 (2018), 142--174. https://doi.org/10.13154/tches.v2018.i1.142-174
    [127]
    Christian Paquin, Douglas Stebila, and Goutam Tamvada. 2019. Benchmarking post-quantum cryptography in TLS. IACR ePrint Archive (2019). Retrieved from https://eprint.iacr.org/2019/1447.
    [128]
    Judea Pearl. 1986. Fusion, propagation, and structuring in belief networks. Artific. Intell. 29, 3 (1986), 241--288.
    [129]
    Chris Peikert. 2008. Public-key cryptosystems from the worst-case shortest vector problem. Electr. Colloq. Comput. Complex. 15, 100 (2008).
    [130]
    Chris Peikert. 2010. An efficient and parallel Gaussian sampler for lattices. In Proceedings of the Annual Cryptology Conference. Springer.
    [131]
    Chris Peikert. 2014. Lattice cryptography for the Internet. In Proceedings of the International Workshop on Post-Quantum Cryptography. Springer, 197--219.
    [132]
    Peter Pessl and Robert Primas. 2019. More practical single-trace attacks on the number theoretic transform. In Proceedings of the International Conference on Cryptology and Information Security in Latin America. Springer, 130--149.
    [133]
    Thomas Pöppelmann and Tim Güneysu. 2012. Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In Proceedings of the International Conference on Cryptology and Information Security in Latin America. Springer.
    [134]
    Thomas Pöppelmann and Tim Güneysu. 2014. Area optimization of lightweight lattice-based encryption on reconfigurable hardware. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS’14). IEEE, 2796--2799.
    [135]
    Thomas Pöppelmann, Tobias Oder, and Tim Güneysu. 2015. High-performance ideal lattice-based cryptography on 8-Bit ATxmega microcontrollers. In Proceedings of the 4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT’15). 346--365.
    [136]
    Robert Primas, Peter Pessl, and Stefan Mangard. 2017. Single-trace side-channel attacks on masked lattice-based encryption. In Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems. Springer, 513--533.
    [137]
    Yue Qin, Chi Cheng, and Jintai Ding. 2019. A complete and optimized key mismatch attack on NIST candidate NewHope. IACR ePrint Archive (2019). Retrieved from https://eprint.iacr.org/2019/435.
    [138]
    Prasanna Ravi, Debapriya Basu Roy, Shivam Bhasin, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. 2019. Number ”not used” once-practical fault attack on pqm4 implementations of NIST candidates. In Proceedings of the International Workshop on Constructive Side-Channel Analysis and Secure Design. Springer, 232--250.
    [139]
    Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. 2019. Generic side-channel attacks on CCA-secure lattice-based PKE and KEM schemes. IACR ePrint Archive (2019). Retrieved from https://eprint.iacr.org/2019/948.
    [140]
    Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 6 (2009), 34.
    [141]
    Oscar Reparaz, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2016. Additively homomorphic ring-LWE masking. In Proceedings of the International Workshop on Post-Quantum Cryptography. Springer.
    [142]
    Oscar Reparaz, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2015. A masked ring-LWE implementation. In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems. Springer, 683--702.
    [143]
    Sujoy Sinha Roy, Oscar Reparaz, Frederik Vercauteren, and Ingrid Verbauwhede. 2014. Compact and side channel secure discrete Gaussian sampling. IACR ePrint Archive. Retrieved from https://eprint.iacr.org/2014/591.
    [144]
    Sujoy Sinha Roy, Frederik Vercauteren, Nele Mentens, Donald Donglong Chen, and Ingrid Verbauwhede. 2014. Compact ring-LWE cryptoprocessor. In International Workshop on Cryptographic Hardware and Embedded Systems. Springer, 371--391.
    [145]
    Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2013. High precision discrete Gaussian sampling on FPGAs. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 383--401.
    [146]
    Markku-Juhani O. Saarinen. 2019. Exploring NIST LWC/PQC Synergy R5Sneik: How SNEIK 1.1 algorithms were designed to support round5. IACR ePrint Archive (2019). Retrieved from https://eprint.iacr.org/2019/685.
    [147]
    Markku-Juhani O. Saarinen. 2016. Arithmetic coding and blinding countermeasures for ring-LWE. IACR ePrint Archive (2016). Retrieved from https://eprint.iacr.org/2016/276.
    [148]
    Markku-Juhani O. Saarinen. 2017. HILA5: On reliability, reconciliation, and error correction for Ring-LWE encryption. In Proceedings of the International Conference on Selected Areas in Cryptography. Springer, 192--212.
    [149]
    Markku-Juhani O. Saarinen, Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen, and Zhenfei Zhang. 2018. Shorter messages and faster post-quantum encryption with Round5 on Cortex M. In Proceedings of the International Conference on Smart Card Research and Advanced Applications. Springer, 95--110.
    [150]
    Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. 2018. Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 520--551.
    [151]
    Thomas Schamberger, Oliver Mischke, and Johanna Sepulveda. 2019. Practical evaluation of masking for NTRUEncrypt on ARM Cortex-M4. In Proceedings of the International Workshop on Constructive Side-Channel Analysis and Secure Design. Springer.
    [152]
    Claus-Peter Schnorr and Martin Euchner. 1994. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program. 66, 1–3 (1994), 181--199.
    [153]
    Gregor Seiler. 2018. Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography. IACR ePrint Archive (2018). Retrieved from https://eprint.iacr.org/2018/039.
    [154]
    Peter W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE, 124--134.
    [155]
    Joseph H. Silverman. 1999. Almost inverses and fast NTRU key creation. NTRU Cryptosyst. Technical Report #014. Retrieved from https://ntru.org/f/tr/tr014v1.pdf.
    [156]
    Shiming Song, Wei Tang, Thomas Chen, and Zhengya Zhang. 2018. LEIA: A 2.05 mm 2 140mW lattice encryption instruction accelerator in 40nm CMOS. In Proceedings of the IEEE Custom Integrated Circuits Conference (CICC’18). IEEE, 1--4.
    [157]
    Douglas Stebila, Michele Mosca, Christian Paquin, Dimitris Sikeridis, and Goutam Tamvada. [n.d.]. OQS-OpenSSL_1_1_1-Fork of OpenSSL by OpenOQS project. Retrieved from https://github.com/open-quantum-safe/openssl.
    [158]
    Damien Stehlé and Ron Steinfeld. 2011. Making NTRU as secure as worst-case problems over ideal lattices. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 27--47.
    [159]
    Ehsan Ebrahimi Targhi and Dominique Unruh. 2016. Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In Proceedings of the 14th International Conference on Theory of Cryptography (TCC’16-B). Springer, Berlin, 192--216.
    [160]
    Ludo Tolhuizen, Ronald Rietman, and Oscar Garcia-Morchon. 2017. Improved key-reconciliation method. IACR ePrint Archive (2017). Retrieved from https://eprint.iacr.org/2017/295.
    [161]
    Andrei L. Toom. 1963. The complexity of a scheme of functional elements realizing the multiplication of integers. In Soviet Mathematics Doklady, Vol. 3. 714--716.
    [162]
    Felipe Valencia, Tobias Oder, Tim Güneysu, and Francesco Regazzoni. 2018. Exploring the vulnerability of R-LWE encryption to fault attacks. In Proceedings of the 5th Workshop on Cryptography and Security in Computing Systems. ACM.
    [163]
    William Whyte, Nick Howgrave-Graham, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, and Philip S. Hirschhorn. 2008. IEEE P1363. 1 Draft 10: Draft standard for public key cryptographic techniques based on hard problems over lattices. IACR EPrint Archive (2008). Retrieved from https://eprint.iacr.org/2008/361.
    [164]
    Xuexin Zheng, An Wang, and Wei Wei. 2013. First-order collision attack on protected NTRU cryptosystem. Microprocess. Microsyst. 37, 6–7 (2013), 601--609.
    [165]
    Timo Zijlstra, Karim Bigou, and Arnaud Tisserand. 2019. FPGA implementation and comparison of protections against SCAs for RLWE. In Proceedings of the International Conference on Cryptology in India. Springer, 535--555.

    Cited By

    View all
    • (2024)Lattice-Based Threshold Secret Sharing Scheme and Its Applications: A SurveyElectronics10.3390/electronics1302028713:2(287)Online publication date: 8-Jan-2024
    • (2024)Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New ResultsACM Transactions on Embedded Computing Systems10.1145/360317023:2(1-54)Online publication date: 28-Mar-2024
    • (2024)Anonymous Lattice-Based Authentication Protocol for Vehicular CommunicationsVehicular Communications10.1016/j.vehcom.2024.100803(100803)Online publication date: May-2024
    • Show More Cited By

    Index Terms

    1. Lattice-based Key-sharing Schemes: A Survey

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Computing Surveys
      ACM Computing Surveys  Volume 54, Issue 1
      January 2022
      844 pages
      ISSN:0360-0300
      EISSN:1557-7341
      DOI:10.1145/3446641
      Issue’s Table of Contents
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 02 January 2021
      Accepted: 01 August 2020
      Revised: 01 June 2020
      Received: 01 January 2018
      Published in CSUR Volume 54, Issue 1

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Lattice-based cryptography
      2. key encapsulation mechanisms
      3. key-exchange schemes
      4. public-key encryption schemes

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Funding Sources

      • DSO

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)196
      • Downloads (Last 6 weeks)16

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Lattice-Based Threshold Secret Sharing Scheme and Its Applications: A SurveyElectronics10.3390/electronics1302028713:2(287)Online publication date: 8-Jan-2024
      • (2024)Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New ResultsACM Transactions on Embedded Computing Systems10.1145/360317023:2(1-54)Online publication date: 28-Mar-2024
      • (2024)Anonymous Lattice-Based Authentication Protocol for Vehicular CommunicationsVehicular Communications10.1016/j.vehcom.2024.100803(100803)Online publication date: May-2024
      • (2024)C-privacy: a social relationship-driven image customization sharing method in cyber-physical networksDigital Communications and Networks10.1016/j.dcan.2024.03.009Online publication date: Mar-2024
      • (2024)Designing quantum-secure attribute-based encryptionCluster Computing10.1007/s10586-024-04546-9Online publication date: 22-Jun-2024
      • (2023)Side Channel Security Oriented Evaluation and Protection on Hardware Implementations of KyberIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2023.328860070:12(5025-5035)Online publication date: Dec-2023
      • (2022)Attribute-Based Encryption in Securing Big Data from Post-Quantum Perspective: A SurveyCryptography10.3390/cryptography60300406:3(40)Online publication date: 5-Aug-2022
      • (2022)On Exploiting Message Leakage in (Few) NIST PQC Candidates for Practical Message Recovery AttacksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.313926817(684-699)Online publication date: 1-Jan-2022
      • (2022)Secured and Quantum Resistant Key Exchange Cryptography Methods – A Comparison2022 Interdisciplinary Research in Technology and Management (IRTM)10.1109/IRTM54583.2022.9791580(1-5)Online publication date: 24-Feb-2022
      • (2022)Vulnerable PQC against Side Channel Analysis - A Case Study on Kyber2022 Asian Hardware Oriented Security and Trust Symposium (AsianHOST)10.1109/AsianHOST56390.2022.10022165(1-6)Online publication date: 14-Dec-2022
      • Show More Cited By

      View Options

      Get Access

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      HTML Format

      View this article in HTML Format.

      HTML Format

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media