{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:01:01Z","timestamp":1777964461347,"version":"3.51.4"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T00:00:00Z","timestamp":1481241600000},"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":[[2017,10]]},"DOI":"10.1007\/s00145-016-9247-3","type":"journal-article","created":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T20:03:04Z","timestamp":1481313784000},"page":"1238-1275","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient Authentication from Hard Learning Problems"],"prefix":"10.1007","volume":"30","author":[{"given":"Eike","family":"Kiltz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Pietrzak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Venturi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Cash","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhishek","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,9]]},"reference":[{"key":"9247_CR1","doi-asserted-by":"crossref","unstructured":"S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in EUROCRYPT 2010, volume 6110 of LNCS, ed. by H. Gilbert (Springer, May 2010), pp. 553\u2013572","DOI":"10.1007\/978-3-642-13190-5_28"},{"key":"9247_CR2","doi-asserted-by":"crossref","unstructured":"Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van\u00a0der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (SIAM, Philadelphia, 2000)","DOI":"10.1137\/1.9780898719581"},{"issue":"3","key":"9247_CR3","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E Berlekamp","year":"1978","unstructured":"E. Berlekamp, R. McEliece, H. van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory, 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9247_CR4","doi-asserted-by":"crossref","unstructured":"O. Blazy, E. Kiltz, J. Pan, (Hierarchical) identity-based encryption from affine message authentication, in In CRYPTO 2014, volume 8616 of LNCS, ed. by J.A. Garay, R. Gennaro (Springer, Aug 2014), pp. 408\u2013425","DOI":"10.1007\/978-3-662-44371-2_23"},{"key":"9247_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, M.L. Furst, M.J. Kearns, R.J. Lipton, Cryptographic primitives based on hard learning problems, in CRYPTO\u201993, volume 773 of LNCS, ed. by D.R. Stinson (Springer, Aug 1994), pp. 278\u2013291","DOI":"10.1007\/3-540-48329-2_24"},{"issue":"4","key":"9247_CR6","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"Avrim Blum","year":"2003","unstructured":"A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"9247_CR7","doi-asserted-by":"crossref","unstructured":"S. Bogos, F. Tram\u00e8r, S. Vaudenay, On solving LPN using BKW and variants\u2014implementation and analysis. Cryptogr. Commun. 8(3), 331\u2013369 (2016)","DOI":"10.1007\/s12095-015-0149-2"},{"key":"9247_CR8","unstructured":"S. Bogos, S. Vaudenay, Observations on the LPN solving algorithm from Eurocrypt\u201916. Cryptology ePrint Archive, Report 2016\/437 (2016). http:\/\/eprint.iacr.org\/2016\/437"},{"key":"9247_CR9","unstructured":"S. Bogos, S. Vaudenay, Optimization of LPN solving algorithms. Cryptology ePrint Archive, Report 2016\/288 (2016). http:\/\/eprint.iacr.org\/2016\/288"},{"key":"9247_CR10","doi-asserted-by":"crossref","unstructured":"X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in PKC 2010, volume 6056 of LNCS, ed. by P.Q. Nguyen, D. Pointcheval (Springer, May 2010), pp. 499\u2013517","DOI":"10.1007\/978-3-642-13013-7_29"},{"key":"9247_CR11","doi-asserted-by":"crossref","unstructured":"J. Bringer, H. Chabanne, E. Dottax, $${\\sf HB}^{++}$$ HB + + : a lightweight authentication protocol secure against some attacks, in SecPerU 2006 (IEEE Computer Society, June 2006), pp. 28\u201333","DOI":"10.1109\/SECPERU.2006.10"},{"key":"9247_CR12","doi-asserted-by":"crossref","unstructured":"D. Cash, E. Kiltz, S. Tessaro, Two-round man-in-the-middle security from LPN, in TCC 2016-A, volume 9562 of LNCS, ed. by E. Kushilevitz, T. Malkin (Springer, Jan 2016), pp. 225\u2013248","DOI":"10.1007\/978-3-662-49096-9_10"},{"key":"9247_CR13","doi-asserted-by":"crossref","unstructured":"J. Chen, H. Wee, Fully, (almost) tightly secure IBE and dual system groups, in CRYPTO 2013, volume 8043 of LNCS, ed. by R. Canetti, J.A. Garay (Springer, Aug 2013), pp. 435\u2013460","DOI":"10.1007\/978-3-642-40084-1_25"},{"key":"9247_CR14","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, On the amortized complexity of zero-knowledge protocols, in CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Aug 2009), pp. 177\u2013191","DOI":"10.1007\/978-3-642-03356-8_11"},{"key":"9247_CR15","doi-asserted-by":"crossref","unstructured":"Y. Dodis, E. Kiltz, K. Pietrzak, D. Wichs, Message authentication, revisited, in EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer, April 2012), pp. 355\u2013374","DOI":"10.1007\/978-3-642-29011-4_22"},{"key":"9247_CR16","unstructured":"D.N. Duc, K. Kim, Securing $${\\sf HB}^{+}$$ HB + against GRS man-in-the-middle attack, in 2007 symposium on cryptography and information security, Jan 2007"},{"key":"9247_CR17","doi-asserted-by":"crossref","unstructured":"J.-B. Fischer, J. Stern, An efficient pseudo-random generator provably as secure as syndrome decoding, in EUROCRYPT\u201996, volume 1070 of LNCS, ed. by U.M. Maurer (Springer, May 1996), pp. 245\u2013255","DOI":"10.1007\/3-540-68339-9_22"},{"key":"9247_CR18","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer, Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","DOI":"10.1137\/070711761"},{"key":"9247_CR19","doi-asserted-by":"crossref","unstructured":"L. Gaspar, G. Leurent, F.-X. Standaert, Hardware implementation and side-channel analysis of Lapin, in CT-RSA 2014, LNCS (Springer, 2014), pp. 206\u2013226","DOI":"10.1007\/978-3-319-04852-9_11"},{"key":"9247_CR20","unstructured":"H. Gilbert, M. Robshaw, H. Sibert, An active attack against $${\\sf HB}^{+}$$ HB + \u2014a provably secure lightweight authentication protocol. Cryptology ePrint Archive, Report 2005\/237 (2005). http:\/\/eprint.iacr.org\/"},{"key":"9247_CR21","doi-asserted-by":"crossref","unstructured":"H. Gilbert, M.J.B. Robshaw, Y. Seurin, Good variants of HB+ are hard to find, in FC 2008, volume 5143 of LNCS, ed. by G. Tsudik (Springer, Jan 2008), pp. 156\u2013170","DOI":"10.1007\/978-3-540-85230-8_12"},{"key":"9247_CR22","doi-asserted-by":"crossref","unstructured":"H. Gilbert, M.J.B. Robshaw, Y. Seurin, HB $$^\\sharp $$ \u266f : increasing the security and efficiency of HB $$^+$$ + , in EUROCRYPT 2008, volume 4965 of LNCS, ed. by N.P. Smart (Springer, April 2008), pp. 361\u2013378","DOI":"10.1007\/978-3-540-78967-3_21"},{"issue":"4","key":"9247_CR23","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"9247_CR24","doi-asserted-by":"crossref","unstructured":"Q. Guo, T. Johansson, C. L\u00f6ndahl, Solving LPN using covering codes, in ASIACRYPT 2014, volume 8873 of LNCS, ed. by P. Sarkar, T. Iwata (Springer, Dec 2014), pp. 1\u201320","DOI":"10.1007\/978-3-662-45611-8_1"},{"key":"9247_CR25","doi-asserted-by":"crossref","unstructured":"S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K. Pietrzak, Lapin: an efficient authentication protocol based on Ring-LPN, in FSE 2012, volume 7549 of LNCS, ed. by A. Canteaut (Springer, March 2012), pp. 346\u2013365","DOI":"10.1007\/978-3-642-34047-5_20"},{"key":"9247_CR26","doi-asserted-by":"crossref","unstructured":"W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","DOI":"10.1080\/01621459.1963.10500830"},{"key":"9247_CR27","doi-asserted-by":"crossref","unstructured":"N.J. Hopper, M. Blum, Secure human identification protocols, in ASIACRYPT 2001, volume 2248 of LNCS, ed. by C. Boyd (Springer, Dec 2001), pp. 52\u201366","DOI":"10.1007\/3-540-45682-1_4"},{"key":"9247_CR28","doi-asserted-by":"crossref","unstructured":"A. Juels, S.A. Weis, Authenticating pervasive devices with human protocols, inCRYPTO 2005, volume 3621 of LNCS, ed. by V. Shoup (Springer, Aug 2005), pp. 293\u2013308","DOI":"10.1007\/11535218_18"},{"key":"9247_CR29","doi-asserted-by":"crossref","unstructured":"T. Kailath, A.H. Sayed, Fast Reliable Algorithms for Matrices with Structure (SIAM, Philadelphia, 1999)","DOI":"10.1137\/1.9781611971354"},{"key":"9247_CR30","doi-asserted-by":"crossref","unstructured":"J. Katz, J.S. Shin, Parallel and concurrent security of the HB and HB+ protocols, in EUROCRYPT 2006, volume 4004 of LNCS, ed. by S. Vaudenay (Springer, May\/June 2006), pp. 73\u201387","DOI":"10.1007\/11761679_6"},{"key":"9247_CR31","doi-asserted-by":"crossref","unstructured":"J. Katz, J.S. Shin, A. Smith, Parallel and concurrent security of the HB and HB+ protocols. J. Cryptol. 23(3), 402\u2013421 (2010)","DOI":"10.1007\/s00145-010-9061-2"},{"key":"9247_CR32","doi-asserted-by":"crossref","unstructured":"M.J. Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983\u20131006 (1998)","DOI":"10.1145\/293347.293351"},{"key":"9247_CR33","doi-asserted-by":"crossref","unstructured":"E. Kiltz, K. Pietrzak, D. Cash, A. Jain, D. Venturi, Efficient authentication from hard learning problems, in EUROCRYPT 2011, volume 6632 of LNCS, ed. by K.G. Paterson (Springer, May 2011), pp. 7\u201326.","DOI":"10.1007\/978-3-642-20465-4_3"},{"key":"9247_CR34","doi-asserted-by":"crossref","unstructured":"\u00c9. Levieil, P.-A. Fouque, An improved LPN algorithm, in SCN 06, volume 4116 of LNCS, ed. by R.\u00a0De Prisco, M. Yung (Springer, Sept 2006), pp. 348\u2013359","DOI":"10.1007\/11832072_24"},{"key":"9247_CR35","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, D. Masny, Man-in-the-middle secure authentication schemes from LPN and weak PRFs, in CRYPTO 2013, volume 8043 of LNCS, ed. by R. Canetti, J.A. Garay (Springer, Aug 2013), pp. 308\u2013325","DOI":"10.1007\/978-3-642-40084-1_18"},{"key":"9247_CR36","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in EUROCRYPT 2010, volume 6110 of LNCS, ed. by H. Gilbert (Springer, June 2010), pp. 1\u201323","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"9247_CR37","unstructured":"J. Munilla, A. Peinado, $${\\sf HB\\sf -\\sf MP}$$ HB - MP : a further step in the HB-family of lightweight authentication protocols. Comput. Netw. 51(9), 2262\u20132267 (2007)"},{"key":"9247_CR38","doi-asserted-by":"crossref","unstructured":"K. Ouafi, R. Overbeck, S. Vaudenay, On the security of HB# against a man-in-the-middle attack, in ASIACRYPT 2008, volume 5350 of LNCS, ed. by J. Pieprzyk (Springer, Dec 2008), pp. 108\u2013124","DOI":"10.1007\/978-3-540-89255-7_8"},{"key":"9247_CR39","doi-asserted-by":"crossref","unstructured":"C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, in 41st ACM STOC, ed. by M. Mitzenmacher (ACM Press, May\/June 2009), pp. 333\u2013342","DOI":"10.1145\/1536414.1536461"},{"key":"9247_CR40","doi-asserted-by":"crossref","unstructured":"K. Pietrzak, Subspace LWE, in TCC 2012, volume 7194 of LNCS, ed. by R. Cramer (Springer, March 2012), pp. 548\u2013563","DOI":"10.1007\/978-3-642-28914-9_31"},{"key":"9247_CR41","doi-asserted-by":"crossref","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in 37th ACM STOC, ed. by H.N. Gabow, R. Fagin (ACM Press, May 2005), pp. 84\u201393","DOI":"10.1145\/1060590.1060603"},{"key":"9247_CR42","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nhage, V. Strassen, Schnelle multiplikation grosser zahlen. Computing 7, 281\u2013292 (1971)","DOI":"10.1007\/BF02242355"},{"key":"9247_CR43","unstructured":"J. Van De\u00a0Graaf, Towards a formal definition of security for quantum protocols. PhD thesis, Universite de Montreal, Monreal, P.Q., Canada, Canada, AAINQ35648, 1998"},{"key":"9247_CR44","doi-asserted-by":"crossref","unstructured":"B.R. Waters, Efficient identity-based encryption without random oracles, in EUROCRYPT 2005, volume 3494 of LNCS, ed. by R. Cramer (Springer, May 2005), pp. 114\u2013127","DOI":"10.1007\/11426639_7"},{"key":"9247_CR45","doi-asserted-by":"crossref","unstructured":"J. Watrous, Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25\u201358 (2009)","DOI":"10.1137\/060670997"},{"key":"9247_CR46","doi-asserted-by":"crossref","unstructured":"B. Zhang, L. Jiao, M. Wang, Faster algorithms for solving LPN, in EUROCRYPT 2016, volume 9665 of LNCS, ed. by M. Fischlin, J.-S. Coron (Springer, May 2016), pp. 168\u2013195","DOI":"10.1007\/978-3-662-49890-3_7"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9247-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9247-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9247-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T12:01:26Z","timestamp":1749816086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9247-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,9]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9247"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9247-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,9]]},"assertion":[{"value":"25 August 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2016","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"}]}}