Modular lattice signatures, revisited. (English) Zbl 1448.94239

Summary: In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. The fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits. We show that this problem is equivalent to the short integer solution (SIS) problem over the corresponding lattice. In addition, we show that by replacing the uniform sampling in pqNTRUSign with a bimodal Gaussian sampling, we can further reduce the size of a signature. An important new contribution, enabled by this Gaussian sampling version of pqNTRUSign, is that we can now perform batch verification of messages signed by the same public key, which allows the verifier to check approximately 24 signatures in a single verification process.


94A62 Authentication, digital signatures and secret sharing
Full Text: DOI


[1] Akleylek S., Alkim E., Barreto P.S.L.M., Bindel N., Buchmann J., Eaton E., Gutoski G., Krämer J., Longa P., Polat H., Ricardini J.E., Zanon G.: qTESLA: efficient and post-quantum secure lattice-based signature scheme. https://qtesla.org.
[2] Albrecht M.R., Bai S., Ducas L.: A subfield lattice attack on overstretched NTRU assumptions-cryptanalysis of some FHE and graded encoding schemes. In: Advances in Cryptology-CRYPTO 2016-36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, pp. 153-178 (2016). · Zbl 1351.94019
[3] Alkim E., Ducas L., Pöppelmann T., Schwabe P.: Post-quantum key exchange: a new hope. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016. pp. 327-343 (2016).
[4] Bai, S.; Laarhoven, T.; Stehlé, D., Tuple lattice sieving, IACR Cryptol. ePrint Arch., 2016, 713 (2016) · Zbl 1404.11140
[5] Bernstein D.J.: A subfield-logarithm attack against ideal lattices (2014). https://blog.cr.yp.to/20140213-ideal.html.
[6] Chen L., Jordan S., Liu Y.-K., Moody D., Peralta R., Perlner R., Smith-Tone D.: Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report, vol. 8105 (2016).
[7] Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: Advances in Cryptology—ASIACRYPT 2011—17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, pp. 1-20 (2011). · Zbl 1227.94037
[8] Coppersmith D., Shamir, A.: Lattice attacks on NTRU. In: Advances in Cryptology-EUROCRYPT’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, 1997, Proceeding, pp. 52-61 (1997).
[9] Daniele, M.; Regev, O., Worst-case to average-case reductions based on gaussian measures, SIAM J. Comput., 37, 1, 267-302 (2007) · Zbl 1142.68037
[10] Ding, J., A simple provably secure key exchange scheme based on the learning with errors problem, IACR Cryptol. ePrint Arch., 2012, 688 (2012)
[11] Ducas, Léo; Lyubashevsky, Vadim; Prest, Thomas, Efficient Identity-Based Encryption over NTRU Lattices, Lecture Notes in Computer Science, 22-41 (2014), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1317.94103
[12] Ducas L., Nguyen, P.Q.: Learning a zonotope and more: cryptanalysis of ntrusign countermeasures. In: Advances in Cryptology-ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, pp. 433-450 (2012). · Zbl 1292.94059
[13] Ducas, L.; Durmus, A.; Lepoint, T.; Lyubashevsky, V., Lattice signatures and bimodal gaussians, CRYPTO, 2013, 40-56 (2013) · Zbl 1310.94141
[14] Ducas, L.; Kiltz, E.; Lepoint, T.; Lyubashevsky, V.; Schwabe, Peter; Seiler, Gregor; Stehlé, Damien, Crystals-dilithium: a lattice-based digital signature scheme, IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018, 1, 238-268 (2018)
[15] Fouque P.-A., Hoffstein J., Kirchner P., Lyubashevsky V., Pornin T., Prest T., Ricosset T., Seiler G., Whyte W., Zhang Z.: Falcon: fast-Fourier lattice-based compact signatures over NTRU. https://falcon-sign.info/.
[16] Gama N., Nguyen P.Q., Regev O.: Lattice enumeration using extreme pruning. In: Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco/French Riviera, May 30-June 3, 2010. Proceedings, pp. 257-278 (2010). · Zbl 1280.94056
[17] Gama N., Nguyen P.Q.: Predicting lattice reduction. In: Advances in Cryptology-EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings pp. 31-51 (2008). · Zbl 1149.94314
[18] 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, STOC ’08, pp. 197-206, New York, USA (2008). ACM. · Zbl 1231.68124
[19] Goldreich O., Goldwasser S., Halevi S.: Public-key cryptosystems from lattice reduction problems. In: Advances in Cryptology—CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pp. 112-131 (1997). · Zbl 0889.94011
[20] Göpfert F., van Vredendaal C., Wunderer T.: A hybrid lattice basis reduction and quantum search attack on LWE. In: Post-quantum Cryptography—8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings, pp.184-202 (2017). · Zbl 1437.94067
[21] Grover L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pp. 212-219 (1996). · Zbl 0922.68044
[22] Hoffstein J., Cong C., Whyte W., Zhang Z.: pqNTRUSign.
[23] Hoffstein J., Howgrave-Graham N., Pipher J., Silverman J.H., Whyte W.: NTRUSIGN: digital signatures using the NTRU lattice. In: Topics in Cryptology—CT-RSA 2003, The Cryptographers’ Track at the RSA Conference 2003, San Francisco, CA, USA, April 13-17, 2003, Proceedings, pp. 122-140 (2003). · Zbl 1039.94525
[24] Hoffstein J., Pipher J., Schanck J.M., Silverman J.H., Whyte W., Zhang Z.: Choosing parameters for ntruencrypt. In: Topics in Cryptology-CT-RSA 2017—The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14-17, 2017, Proceedings, pp. 3-18 (2017). · Zbl 1383.94022
[25] Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H., NTRU: A ring-based public key cryptosystem, Lecture Notes in Computer Science, 267-288 (1998), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1067.94538
[26] Hoffstein J., Pipher J., Whyte W., Zhang Z.: A signature scheme from learning with truncation. Cryptology ePrint Archive, Report 2017/995 (2017). https://eprint.iacr.org/2017/995.
[27] Hoffstein J., Silverman J.H.: Meet-in-the-middle attack on an NTRU private key (2006). http://www.ntru.com.
[28] Hoffstein, J.; Pipher, J.; Schanck, Jm; Silverman, Jh; Whyte, W., Transcript secure signatures based on modular lattices, PQCrypto, 2014, 142-159 (2014) · Zbl 1380.94099
[29] Howgrave-Graham N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Advances in Cryptology-CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, pp. 150-169 (2007). · Zbl 1215.94053
[30] Lyubashevsky V.: Lattice signatures without trapdoors. In: Advances in Cryptology-EUROCRYPT 2012—31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, pp. 738-755 (2012). · Zbl 1295.94111
[31] Lyubashevsky, V., Fiat-Shamir with aborts: applications to lattice and factoring-based signatures, ASIACRYPT 2009, 598-616 (2009), Berlin: Springer, Berlin · Zbl 1267.94125
[32] Micciancio D., Peikert C.: Hardness of SIS and LWE with small parameters. In: Advances in Cryptology-CRYPTO 2013—33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pp. 21-39 (2013). · Zbl 1310.94161
[33] Nguyen, Pq; Regev, O., Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures, J. Cryptol., 22, 2, 139-160 (2009) · Zbl 1159.94369
[34] NIST. Post-quantum cryptography-round 1 submissions. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions.
[35] NSA Suite B Cryptography-NSA/CSS.
[36] NTRU OpenSource Project. https://github.com/NTRUOpenSourceProject/ntru-crypto.
[37] Peikert C.: Lattice cryptography for the internet. In: Post-Quantum Cryptography—6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings, pp. 197-219 (2014). · Zbl 1383.94037
[38] Schanck J.: Estimator: scripts for estimating the security of lattice based cryptosystems. https://github.com/jschanck/estimator.
[39] Shor P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 124-134 (1994).
[40] The number of atoms in the World (2014). http://www.fnal.gov/pub/science/inquiring/questions/atoms.html.
[41] What is the world’s data storage capacity? (2011). http://www.zdnet.com/article/what-is-the-worlds-data-storage-capacity/.
[42] Wunderer, T., Revisiting the hybrid attack: improved analysis and refined security estimates, IACR Cryptol. ePrint Arch., 2016, 733 (2016)
[43] Wunderer, T., A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack, J. Math. Cryptol., 13, 1, 1-26 (2019) · Zbl 1415.94466
[44] Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür, Authenticated Key Exchange from Ideal Lattices, Advances in Cryptology - EUROCRYPT 2015, 719-751 (2015), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1375.94164
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.