{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:21:53Z","timestamp":1775794913202,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540785231","type":"print"},{"value":"9783540785248","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78524-8_3","type":"book-chapter","created":{"date-parts":[[2008,2,25]],"date-time":"2008-02-25T09:18:12Z","timestamp":1203931092000},"page":"37-54","source":"Crossref","is-referenced-by-count":106,"title":["Asymptotically Efficient Lattice-Based Digital Signatures"],"prefix":"10.1007","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[]},{"given":"Daniele","family":"Micciancio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"3_CR1","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D. Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP \u2229 coNP. Journal of the ACM\u00a052(5), 749\u2013765 (2005)","journal-title":"Journal of the ACM"},{"key":"3_CR2","first-page":"1","volume":"13","author":"M. Ajtai","year":"2004","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica\u00a013, 1\u201332 (2004) (Preliminary version in STOC 1996)","journal-title":"Complexity of Computations and Proofs, Quaderni di Matematica"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BFb0034843","volume-title":"Advances in Cryptology - ASIACRYPT 1996","author":"D. Bleichenbacher","year":"1996","unstructured":"Bleichenbacher, D., Maurer, U.: On the efficiency of one-time digital signatures. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol.\u00a01163, pp. 145\u2013158. Springer, Heidelberg (1996)"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","first-page":"363","volume-title":"STACS 96","author":"D. Bleichenbacher","year":"1996","unstructured":"Bleichenbacher, D., Maurer, U.: Optimal tree-based one-time digital signature schemes. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 363\u2013374. Springer, Heidelberg (1996)"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput.\u00a013(4), 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Advances in Cryptology 1981 - 1997","author":"J. Bos","year":"1999","unstructured":"Bos, J., Chaum, D.: Provably unforgeable signatures. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol.\u00a01440, pp. 1\u201314. Springer, Heidelberg (1999)"},{"issue":"3","key":"3_CR8","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/357830.357847","volume":"3","author":"R. Cramer","year":"2000","unstructured":"Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur.\u00a03(3), 161\u2013185 (2000)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"issue":"6","key":"3_CR9","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"IT-22","author":"W. Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions on Information Theory\u00a0IT-22(6), 644\u2013654 (1976)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(01)00290-0","volume":"285","author":"I. Dinur","year":"2002","unstructured":"Dinur, I.: Approximating SVP\n                  \u2009\u221e\u2009 to within almost-polynomial factors is NP-hard. Theor. Comput. Sci.\u00a0285(1), 55\u201371 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02254791","volume":"9","author":"S. Even","year":"1996","unstructured":"Even, S., Goldreich, O., Micali, S.: On-line\/off-line digital signatures. J. Cryptology\u00a09(1), 35\u201367 (1996)","journal-title":"J. Cryptology"},{"issue":"1","key":"3_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-48910-X_9","volume-title":"Advances in Cryptology - EUROCRYPT 1999","author":"R. Gennaro","year":"1999","unstructured":"Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 123\u2013139. Springer, Heidelberg (1999)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci.\u00a060(3) (2000)","DOI":"10.1006\/jcss.1999.1686"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S. Goldwasser","year":"1988","unstructured":"Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput.\u00a017(2), 281\u2013308 (1988)","journal-title":"SIAM J. Comput."},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/3-540-36178-2_24","volume-title":"Advances in Cryptology - ASIACRYPT 2002","author":"A. Hevia","year":"2002","unstructured":"Hevia, A., Micciancio, D.: The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol.\u00a02501, pp. 379\u2013396. Springer, Heidelberg (2002)"},{"issue":"3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/S0895480100379981","volume":"16","author":"R. Kumar","year":"2003","unstructured":"Kumar, R., Sivakumar, D.: On polynomial-factor approximations to the shortest lattice vector length. SIAM J. Discrete Math.\u00a016(3), 422\u2013425 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11787006_13","volume-title":"Automata, Languages and Programming","author":"V. Lyubashevsky","year":"2006","unstructured":"Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 144\u2013155. Springer, Heidelberg (2006)"},{"key":"3_CR19","unstructured":"Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, R.: Provably secure FFT hashing. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","first-page":"369","volume-title":"Advances in Cryptology 1981 - 1997","author":"R. Merkle","year":"1999","unstructured":"Merkle, R.: A digital signature based on a conventional encryption function. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol.\u00a01440, pp. 369\u2013378. Springer, Heidelberg (1999)"},{"key":"3_CR21","series-title":"Lecture Notes in Computer Science","first-page":"218","volume-title":"Advances in Cryptology 1981 - 1997","author":"R. Merkle","year":"1999","unstructured":"Merkle, R.: A certified digital signature. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol.\u00a01440, pp. 218\u2013238. Springer, Heidelberg (1999)"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity (2007) (Special issue on worst-case versus average-case complexity, in print. Available on-line as doi:10.1007\/s00037-007-0234-9. Preliminary version in FOCS 2002)","DOI":"10.1007\/s00037-007-0234-9"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC, pp. 33\u201343 (1989)","DOI":"10.1145\/73007.73011"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/S009753979324557X","volume":"26","author":"T. Pedersen","year":"1997","unstructured":"Pedersen, T., Pfitzmann, B.: Fail-stop signatures. SIAM J. Comput.\u00a026(2), 291\u2013330 (1997)","journal-title":"SIAM J. Comput."},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"C. Peikert","year":"2006","unstructured":"Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, Springer, Heidelberg (2006)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: STOC (2007)","DOI":"10.1145\/1250790.1250860"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387\u2013394 (1990)","DOI":"10.1145\/100216.100269"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/978-3-540-24676-3_32","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"M. Szydlo","year":"2004","unstructured":"Szydlo, M.: Merkle tree traversal in log space and time. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 541\u2013554. Springer, Heidelberg (2004)"},{"key":"3_CR29","unstructured":"van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam (1981), \n                    \n                      http:\/\/turing.wins.uva.nl\/~peter\/"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78524-8_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:12:08Z","timestamp":1619521928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78524-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540785231","9783540785248"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78524-8_3","relation":{},"subject":[]}}