{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:21:52Z","timestamp":1775794912829,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T00:00:00Z","timestamp":1509321600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00145-017-9270-z","type":"journal-article","created":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T16:55:01Z","timestamp":1509382501000},"page":"774-797","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Asymptotically Efficient Lattice-Based Digital Signatures"],"prefix":"10.1007","volume":"31","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[]},{"given":"Daniele","family":"Micciancio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,30]]},"reference":[{"key":"9270_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99\u2013108, 1996.","DOI":"10.1145\/237814.237838"},{"key":"9270_CR2","doi-asserted-by":"crossref","unstructured":"J.N. Bos and D. Chaum. Provably unforgeable signatures. In CRYPTO, pages 1\u201314, 1992.","DOI":"10.1007\/3-540-48071-4_1"},{"key":"9270_CR3","doi-asserted-by":"crossref","unstructured":"S. Bai and S.D. Galbraith. An improved compression technique for signatures based on learning with errors. In CT-RSA, pages 28\u201347, 2014.","DOI":"10.1007\/978-3-319-04852-9_2"},{"key":"9270_CR4","doi-asserted-by":"crossref","unstructured":"A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506\u2013519, 2003. Prelim. version in STOC 2000.","DOI":"10.1145\/792538.792543"},{"key":"9270_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850\u2013864, 1984. Prelim. version in FOCS 1982.","DOI":"10.1137\/0213053"},{"key":"9270_CR6","doi-asserted-by":"crossref","unstructured":"D. Bleichenbacher and U.M. Maurer. On the efficiency of one-time digital signatures. In ASIACRYPT, pages 145\u2013158, 1996.","DOI":"10.1007\/BFb0034843"},{"key":"9270_CR7","doi-asserted-by":"crossref","unstructured":"N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliece-based digital signature scheme. In ASIACRYPT, pages 157\u2013174, 2001.","DOI":"10.1007\/3-540-45682-1_10"},{"key":"9270_CR8","doi-asserted-by":"crossref","unstructured":"L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40\u201356, 2013.","DOI":"10.1007\/978-3-642-40041-4_3"},{"issue":"6","key":"9270_CR9","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644\u2013654, 1976.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9270_CR10","unstructured":"L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehl\u00e9. CRYSTALS - dilithium: Digital signatures from module lattices. \n                    http:\/\/eprint.iacr.org\/2017\/633\n                    \n                  , 2017."},{"key":"9270_CR11","doi-asserted-by":"crossref","unstructured":"S. Even, O. Goldreich, and S. Micali. On-line\/off-line digital signatures. J. Cryptology, 9(1):35\u201367, 1996. Prelim. version in CRYPTO 1989.","DOI":"10.1007\/BF02254791"},{"key":"9270_CR12","doi-asserted-by":"crossref","unstructured":"R. Gennaro, Y. Gertner, J. Katz, and L. Trevisan. Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput., 35(1):217\u2013246, 2005. Prelim. versions in FOCS 2000 and STOC 2003.","DOI":"10.1137\/S0097539704443276"},{"issue":"2","key":"9270_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S Goldwasser","year":"1988","unstructured":"S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281\u2013308, 1988.","journal-title":"SIAM J. Comput."},{"key":"9270_CR14","doi-asserted-by":"crossref","unstructured":"C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197\u2013206, 2008.","DOI":"10.1145\/1374376.1374407"},{"key":"9270_CR15","doi-asserted-by":"crossref","unstructured":"A. Hevia and D. Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In ASIACRYPT, pages 379\u2013396, 2002.","DOI":"10.1007\/3-540-36178-2_24"},{"issue":"4","key":"9270_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R Impagliazzo","year":"1996","unstructured":"R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199\u2013216, 1996.","journal-title":"J. Cryptology"},{"key":"9270_CR17","first-page":"144","volume":"2","author":"V Lyubashevsky","year":"2006","unstructured":"V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144\u2013155, 2006.","journal-title":"ICALP"},{"key":"9270_CR18","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky and D. Micciancio. Asymptotically efficient lattice-based digital signatures. In TCC, pages 37\u201354, 2008.","DOI":"10.1007\/978-3-540-78524-8_3"},{"key":"9270_CR19","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. J. ACM, 60(6):43:1\u201343:35, 2013. Prelim. version in Eurocrypt 2010.","DOI":"10.1145\/2535925"},{"key":"9270_CR20","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for Ring-LWE cryptography. In EUROCRYPT, pages 35\u201354, 2013.","DOI":"10.1007\/978-3-642-38348-9_3"},{"key":"9270_CR21","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In APPROX-RANDOM, pages 378\u2013389, 2005.","DOI":"10.1007\/11538462_32"},{"key":"9270_CR22","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky. Lattice-based identification schemes secure under active attacks. In Public Key Cryptography, pages 162\u2013179, 2008.","DOI":"10.1007\/978-3-540-78440-1_10"},{"key":"9270_CR23","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In ASIACRYPT, pages 598\u2013616, 2009.","DOI":"10.1007\/978-3-642-10366-7_35"},{"key":"9270_CR24","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, pages 738\u2013755, 2012.","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"9270_CR25","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky. Digital signatures based on the hardness of ideal lattice problems in all rings. In ASIACRYPT, pages 196\u2013214, 2016.","DOI":"10.1007\/978-3-662-53890-6_7"},{"key":"9270_CR26","doi-asserted-by":"crossref","unstructured":"C.A. Melchor, S. Bettaieb, X. Boyen, L. Fousse, and P. Gaborit. Adapting Lyubashevsky\u2019s signature schemes to the ring signature setting. In AFRICACRYPT, pages 1\u201325, 2013.","DOI":"10.1007\/978-3-642-38553-7_1"},{"key":"9270_CR27","doi-asserted-by":"crossref","unstructured":"R.C. Merkle. A digital signature based on a conventional encryption function. In CRYPTO, pages 369\u2013378, 1987.","DOI":"10.1007\/3-540-48184-2_32"},{"key":"9270_CR28","doi-asserted-by":"crossref","unstructured":"R.C. Merkle. A certified digital signature. In CRYPTO, pages 218\u2013238, 1989.","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9270_CR29","doi-asserted-by":"crossref","unstructured":"D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365\u2013411, 2007. Prelim. version in FOCS 2002.","DOI":"10.1007\/s00037-007-0234-9"},{"key":"9270_CR30","doi-asserted-by":"crossref","unstructured":"D. Micciancio and C. Peikert. Hardness of SIS and LWE with small parameters. In CRYPTO (1), pages 21\u201339, 2013.","DOI":"10.1007\/978-3-642-40041-4_2"},{"key":"9270_CR31","doi-asserted-by":"crossref","unstructured":"D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267\u2013302, 2007. Prelim. version in FOCS 2004.","DOI":"10.1137\/S0097539705447360"},{"key":"9270_CR32","doi-asserted-by":"publisher","unstructured":"NIST. SHA-3 standard: Permutation-based hash and extendable-output functions. Technical report, 2015. Available at \n                    https:\/\/doi.org\/10.6028\/NIST.FIPS.202\n                    \n                  .","DOI":"10.6028\/NIST.FIPS.202"},{"key":"9270_CR33","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In STOC, pages 33\u201343, 1989.","DOI":"10.1145\/73007.73011"},{"key":"9270_CR34","doi-asserted-by":"crossref","unstructured":"C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pages 145\u2013166, 2006.","DOI":"10.1007\/11681878_8"},{"key":"9270_CR35","doi-asserted-by":"crossref","unstructured":"C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. In STOC, pages 478\u2013487, 2007.","DOI":"10.1145\/1250790.1250860"},{"key":"9270_CR36","doi-asserted-by":"crossref","unstructured":"J. Rompel. One-way functions are necessary and sufficient for secure signatures. In STOC, pages 387\u2013394, 1990.","DOI":"10.1145\/100216.100269"},{"key":"9270_CR37","doi-asserted-by":"crossref","unstructured":"M. R\u00fcckert. Lattice-based blind signatures. In ASIACRYPT, pages 413\u2013430, 2010.","DOI":"10.1007\/978-3-642-17373-8_24"},{"key":"9270_CR38","doi-asserted-by":"crossref","unstructured":"M. Szydlo. Merkle tree traversal in log space and time. In EUROCRYPT, pages 541\u2013554, 2004.","DOI":"10.1007\/978-3-540-24676-3_32"},{"key":"9270_CR39","doi-asserted-by":"crossref","unstructured":"D. Wagner. A generalized birthday problem. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 288\u2013303. Springer, 2002.","DOI":"10.1007\/3-540-45708-9_19"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-017-9270-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9270-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9270-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:07:52Z","timestamp":1586333272000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-017-9270-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,30]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9270"],"URL":"https:\/\/doi.org\/10.1007\/s00145-017-9270-z","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,30]]},"assertion":[{"value":"26 November 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}