{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T11:43:52Z","timestamp":1781005432518,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642204647","type":"print"},{"value":"9783642204654","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20465-4_3","type":"book-chapter","created":{"date-parts":[[2011,5,2]],"date-time":"2011-05-02T14:42:47Z","timestamp":1304347367000},"page":"7-26","source":"Crossref","is-referenced-by-count":59,"title":["Efficient Authentication from Hard Learning Problems"],"prefix":"10.1007","author":[{"given":"Eike","family":"Kiltz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Pietrzak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Cash","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Jain","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Venturi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"The full version of this paper will be posted on the Cryptology ePrint Archive, http:\/\/eprint.iacr.org\/"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-642-13190-5_28","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"S. Agrawal","year":"2010","unstructured":"Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 553\u2013572. Springer, Heidelberg (2010)"},{"issue":"3","key":"3_CR3","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E. Berlekamp","year":"1978","unstructured":"Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory\u00a024(3), 384\u2013386 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"A. Blum","year":"1994","unstructured":"Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 278\u2013291. Springer, Heidelberg (1994)"},{"key":"3_CR5","first-page":"435","volume-title":"32nd ACM STOC","author":"A. Blum","year":"2000","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435\u2013440. ACM Press, New York (May 2000)"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-540-24676-3_14","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"D. Boneh","year":"2004","unstructured":"Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 223\u2013238. Springer, Heidelberg (2004)"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-13013-7_29","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"X. Boyen","year":"2010","unstructured":"Boyen, X.: Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol.\u00a06056, pp. 499\u2013517. Springer, Heidelberg (2010)"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Bringer, J., Chabanne, H., Dottax, E.: HB\u2009+\u2009+\u2009: a lightweight authentication protocol secure against some attacks. In: SecPerU, pp. 28\u201333 (2006)","DOI":"10.1109\/SECPERU.2006.10"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-03356-8_11","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"R. Cramer","year":"2009","unstructured":"Cramer, R., Damgard, I.: On the amortized complexity of zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 177\u2013191. Springer, Heidelberg (2009)"},{"key":"3_CR11","unstructured":"Duc, D.N., Kim, K.: Securing HB+ against GRS man-in-the-middle attack. In: SCIS (2007)"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/3-540-68339-9_22","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"J.-B. Fischer","year":"1996","unstructured":"Fischer, J.-B., Stern, J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 245\u2013255. Springer, Heidelberg (1996)"},{"issue":"3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M. F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput.\u00a039(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Gilbert, H., Robshaw, M., Sibert, H.: An active attack against HB+ - a provably secure lightweight authentication protocol. Cryptology ePrint Archive, Report 2005\/237 (2005), http:\/\/eprint.iacr.org\/","DOI":"10.1049\/el:20052622"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-540-85230-8_12","volume-title":"Financial Cryptography and Data Security","author":"H. Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: Good variants of hB\u2009+\u2009 are hard to find. In: Tsudik, G. (ed.) FC 2008. LNCS, vol.\u00a05143, pp. 156\u2013170. Springer, Heidelberg (2008)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-78967-3_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"H. Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: Increasing the security and efficiency of HB\u2009+\u2009. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 361\u2013378. Springer, Heidelberg (2008)"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM\u00a033, 792\u2013807 (1986)","journal-title":"Journal of the ACM"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"N.J. Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol.\u00a02248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/11535218_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"A. Juels","year":"2005","unstructured":"Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 293\u2013308. Springer, Heidelberg (2005)"},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/11761679_6","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"J. Katz","year":"2006","unstructured":"Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB\u2009+\u2009 protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 73\u201387. Springer, Heidelberg (2006)"},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00145-010-9061-2","volume":"23","author":"J. Katz","year":"2010","unstructured":"Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB+ protocols. Journal of Cryptology\u00a023(3), 402\u2013421 (2010)","journal-title":"Journal of Cryptology"},{"issue":"6","key":"3_CR22","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M.J. Kearns","year":"1998","unstructured":"Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. J. ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11832072_24","volume-title":"Security and Cryptography for Networks","author":"\u00c9. Levieil","year":"2006","unstructured":"Levieil, \u00c9., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol.\u00a04116, pp. 348\u2013359. Springer, Heidelberg (2006)"},{"issue":"9","key":"3_CR24","doi-asserted-by":"publisher","first-page":"2262","DOI":"10.1016\/j.comnet.2007.01.011","volume":"51","author":"J. Munilla","year":"2007","unstructured":"Munilla, J., Peinado, A.: HB-MP: A further step in the HB-family of lightweight authentication protocols. Computer Networks\u00a051(9), 2262\u20132267 (2007)","journal-title":"Computer Networks"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-89255-7_8","volume-title":"Advances in Cryptology - ASIACRYPT 2008","author":"K. Ouafi","year":"2008","unstructured":"Ouafi, K., Overbeck, R., Vaudenay, S.: On the security of hB# against a man-in-the-middle attack. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol.\u00a05350, pp. 108\u2013124. Springer, Heidelberg (2008)"},{"key":"3_CR26","unstructured":"Pietrzak, K.: Subspace LWE (2010) (manuscript) http:\/\/homepages.cwi.nl\/~pietrzak\/publications\/SLWE.pdf"},{"key":"3_CR27","first-page":"84","volume-title":"37th ACM STOC","author":"O. Regev","year":"2005","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84\u201393. ACM Press, New York (2005)"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7 (1971)","DOI":"10.1007\/BF02242355"},{"key":"3_CR29","unstructured":"Van De Graaf, J.: Towards a formal definition of security for quantum protocols. PhD thesis, Monreal, P.Q., Canada, AAINQ35648 (1998)"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/11426639_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"B.R. Waters","year":"2005","unstructured":"Waters, B.R.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 114\u2013127. Springer, Heidelberg (2005)"},{"issue":"1","key":"3_CR31","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/060670997","volume":"39","author":"J. Watrous","year":"2009","unstructured":"Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput.\u00a039(1), 25\u201358 (2009)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20465-4_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T10:05:49Z","timestamp":1741169149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20465-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642204647","9783642204654"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20465-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}