{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:55:00Z","timestamp":1778604900036,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T00:00:00Z","timestamp":1438300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021_143899\/1"],"award-info":[{"award-number":["200021_143899\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s12095-015-0149-2","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T02:49:41Z","timestamp":1438224581000},"page":"331-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["On solving L P N using B K W and variants"],"prefix":"10.1007","volume":"8","author":[{"given":"Sonia","family":"Bogos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Tram\u00e8r","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Vaudenay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,31]]},"reference":[{"issue":"2","key":"149_CR1","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","volume":"74","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74(2), 325\u2013354 (2015). doi: 10.1007\/s10623-013-9864-x","journal-title":"Des. Codes Crypt."},{"key":"149_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Faug\u00e8re, J., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the BKW algorithm on LWE. In: Krawczyk, H. (ed.) Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, March 26\u201328, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8383, pp 429\u2013445. Springer (2014), doi: 10.1007\/978-3-642-54631-0_25","DOI":"10.1007\/978-3-642-54631-0_25"},{"key":"149_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 11\u201314 October 2003, pp 298\u2013307. IEEE Computer Society, Cambridge (2003), doi: 10.1109\/SFCS.2003.1238204","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"149_CR4","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, August 16\u201320, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5677, pp 595\u2013618. Springer (2009), doi: 10.1007\/978-3-642-03356-8_35","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"149_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, July 4\u20138, 2011, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6755, pp 403\u2013415. Springer (2011). doi: 10.1007\/978-3-642-22006-7_34","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"149_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T.: Never trust a bunny. In: Hoepman, J., Verbauwhede, I. (eds.) Radio Frequency Identification. Security and Privacy Issues - 8th International Workshop, RFIDSec 2012, Nijmegen, July 2\u20133, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7739, pp 137\u2013148. Springer (2012), doi: 10.1007\/978-3-642-36140-1_10","DOI":"10.1007\/978-3-642-36140-1_10"},{"key":"149_CR7","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Rogaway, P. (ed.) Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, August 14\u201318, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841, pp 743\u2013760. Springer (2011). doi: 10.1007\/978-3-642-22792-9_42","DOI":"10.1007\/978-3-642-22792-9_42"},{"key":"149_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) Advances in Cryptology - CRYPTO \u201993, 13th Annual International Cryptology Conference, Santa Barbara, August 22\u201326, 1993. Proceedings, Lecture Notes in Computer Science, vol. 773, pp 278\u2013291. Springer (1993). doi: 10.1007\/3-540-48329-2_24","DOI":"10.1007\/3-540-48329-2_24"},{"key":"149_CR9","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Yao, F.F., Luks, E.M. (eds.) Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, May 21\u201323, 2000, Portland, pp 435\u2013440. ACM (2000). doi: 10.1145\/335305.335355","DOI":"10.1145\/335305.335355"},{"key":"149_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, June 1\u20134, 2013, pp 575\u2013584. ACM (2013). doi: 10.1145\/2488608.2488680","DOI":"10.1145\/2488608.2488680"},{"key":"149_CR11","doi-asserted-by":"crossref","unstructured":"Bringer, J., Chabanne, H., Dottax, E.: HB++: a lightweight authentication protocol secure against some attacks. In: 2nd International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2006), 29 June 2006, Lyon, pp 28\u201333. IEEE Computer Society (2006). doi: 10.1109\/SECPERU.2006.10","DOI":"10.1109\/SECPERU.2006.10"},{"issue":"2","key":"149_CR12","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1587\/transfun.E92.A.658","volume":"92-A","author":"J Carrijo","year":"2009","unstructured":"Carrijo, J., Tonicelli, R., Imai, H., Nascimento, A.C.A.: A Novel Probabilistic Passive Attack on the Protocols HB and HB+. IEICE Transactions 92-A(2), 658\u2013662 (2009)","journal-title":"IEICE Transactions"},{"key":"149_CR13","doi-asserted-by":"crossref","unstructured":"Chernoff, H.: A Measure of the Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observables. doi: 10.1214\/aoms\/1177729330 (1952)","DOI":"10.1214\/aoms\/1177729330"},{"issue":"90","key":"149_CR14","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comput. 19(90), 297\u2013301 (1965) http:\/\/www.jstor.org\/stable\/ 2003354","journal-title":"Math. Comput."},{"key":"149_CR15","first-page":"699","volume":"2012","author":"I Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., Park, S.: Is public-key encryption based on LPN practical IACR Cryptology ePrint Archive 2012, 699 (2012)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"149_CR16","doi-asserted-by":"crossref","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J., Nascimento, A.C.A.: IND-CCA secure cryptography based on a variant of the LPN problem. In: Wang, X., Sako, K. (eds.) Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, December 2\u20136, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7658, pp 485\u2013503. Springer (2012). doi: 10.1007\/978-3-642-34961-4_30","DOI":"10.1007\/978-3-642-34961-4_30"},{"key":"149_CR17","doi-asserted-by":"crossref","unstructured":"Duc, A., Tram\u00e8r, F., Vaudenay, S.: Better algorithms for LWE and LWR. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, April 26\u201330, 2015, Proceedings, Part I, Lecture Notes in Computer Science, vol. 9056, pp 173\u2013202. Springer (2015). doi: 10.1007\/978-3-662-46800-5_8","DOI":"10.1007\/978-3-662-46800-5_8"},{"key":"149_CR18","doi-asserted-by":"crossref","unstructured":"Duc, A., Vaudenay, S.: HELEN: a public-key cryptosystem based on the LPN and the decisional minimal distance problems. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) Progress in Cryptology - AFRICACRYPT 2013, 6th International Conference on Cryptology in Africa, Cairo, June 22\u201324, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7918, pp 107\u2013126. Springer (2013). doi: 10.1007\/978-3-642-38553-7_6","DOI":"10.1007\/978-3-642-38553-7_6"},{"key":"149_CR19","unstructured":"Fitzpatrick, R.: Some algorithms for learning with errors. Ph.D. thesis, Royal Holloway, University of London"},{"key":"149_CR20","doi-asserted-by":"crossref","unstructured":"Fossorier, M.P.C., Mihaljevic, M.J., Imai, H., Cui, Y., Matsuura, K.: An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication. In: Barua, R., Lange, T. (eds.) INDOCRYPT, Lecture Notes in Computer Science, vol. 4329, pp 48\u201362. Springer (2006)","DOI":"10.1007\/11941378_5"},{"key":"149_CR21","doi-asserted-by":"crossref","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: increasing the security and efficiency of HB+. In: Smart, N.P. (ed.) Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, April 13\u201317, 2008. Proceedings, Lecture Notes in Computer Science, vol. 4965, pp 361\u2013378. Springer (2008). doi: 10.1007\/978-3-540-78967-3_21","DOI":"10.1007\/978-3-540-78967-3_21"},{"key":"149_CR22","doi-asserted-by":"crossref","unstructured":"Grigorescu, E., Reyzin, L., Vempala, S.: On noise-tolerant learning of sparse parities and related problems. In: Kivinen, J., Szepesv\u00e1ri, C., Ukkonen, E., Zeugmann, T. (eds.) Algorithmic Learning Theory - 22nd International Conference, ALT 2011, Espoo, October 5\u20137, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6925, pp 413\u2013424. Springer (2011). doi: 10.1007\/978-3-642-24412-4_32","DOI":"10.1007\/978-3-642-24412-4_32"},{"key":"149_CR23","unstructured":"Guo, Q., Johansson, T., Lo\u0307ndahl, C.: A new algorithm for solving Ring-LPN with a reducible polynomial (2014). CoRR. arXiv: 1409.0472"},{"key":"149_CR24","doi-asserted-by":"crossref","unstructured":"Guo, Q., Johansson, T., L\u00f6ndahl, C.: Solving LPN using covering codes. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, December 7\u201311, 2014. Proceedings, Part I, Lecture Notes in Computer Science, vol. 8873, pp 1\u201320. Springer (2014). doi: 10.1007\/978-3-662-45611-8_1","DOI":"10.1007\/978-3-662-45611-8_1"},{"key":"149_CR25","doi-asserted-by":"crossref","unstructured":"Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: an efficient authentication protocol based on Ring-LPN. In: Canteaut, A. (ed.) Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, March 19\u201321, 2012. Revised Selected Papers, Lecture Notes in Computer Science, vol. 7549, pp 346\u2013365. Springer (2012), 10.1007\/978-3-642-34047-5_20","DOI":"10.1007\/978-3-642-34047-5_20"},{"issue":"301","key":"149_CR26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963) http:\/\/www.jstor.org\/stable\/2282952?","journal-title":"J. Am. Stat. Assoc."},{"key":"149_CR27","doi-asserted-by":"crossref","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, December 9\u201313, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2248, pp 52\u201366. Springer (2001). doi: 10.1007\/3-540-45682-1_4","DOI":"10.1007\/3-540-45682-1_4"},{"key":"149_CR28","doi-asserted-by":"crossref","unstructured":"Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, August 14\u201318, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3621, pp 293\u2013308. Springer (2005). doi: 10.1007\/11535218_18","DOI":"10.1007\/11535218_18"},{"issue":"3","key":"149_CR29","doi-asserted-by":"crossref","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 . J. Cryptology 23(3), 402\u2013421 (2010). doi: 10.1007\/s00145-010-9061-2","journal-title":"J. Cryptology"},{"key":"149_CR30","doi-asserted-by":"crossref","unstructured":"Kiltz, E., Masny, D., Pietrzak, K.: Simple chosen-ciphertext security from low-noise LPN. In: Krawczyk, H. (ed.) Public-key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-key Cryptography, Buenos Aires, March 26\u201328 2014. Proceedings, Lecture Notes in Computer Science, vol. 8383, pp 1\u201318. Springer (2014). doi: 10.1007\/978-3-642-54631-0_1","DOI":"10.1007\/978-3-642-54631-0_1"},{"key":"149_CR31","doi-asserted-by":"crossref","unstructured":"Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, May 15\u201319, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6632, pp 7\u201326. Springer (2011), doi: 10.1007\/978-3-642-20465-4_3","DOI":"10.1007\/978-3-642-20465-4_3"},{"key":"149_CR32","first-page":"377","volume":"2011","author":"P Kirchner","year":"2011","unstructured":"Kirchner, P.: Improved generalized birthday attack. IACR Cryptology ePrint Archive 2011, 377 (2011) http:\/\/eprint.iacr.org\/2011\/377","journal-title":"IACR Cryptology ePrint Archive"},{"key":"149_CR33","doi-asserted-by":"crossref","unstructured":"Levieil, \u00c9., Fouque, P.: An improved LPN algorithm. In: Prisco, R.D., Yung, M. (eds.) Security and Cryptography for Networks, 5th International Conference, SCN 2006, Maiori, September 6\u20138, 2006. Proceedings, Lecture Notes in Computer Science, vol. 4116, pp 348\u2013359. Springer (2006). doi: 10.1007\/11832072_24","DOI":"10.1007\/11832072_24"},{"key":"149_CR34","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th InternationalWorkshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, August 22\u201324, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3624, pp 378\u2013389. Springer (2005). doi: 10.1007\/11538462_32","DOI":"10.1007\/11538462_32"},{"key":"149_CR35","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Masny, D.: Man-in-the-Middle secure authentication schemes from LPN and weak PRFs. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, August 18\u201322, 2013. Proceedings, Part II, Lecture Notes in Computer Science, vol. 8043, pp 308\u2013325. Springer (2013). doi: 10.1007\/978-3-642-40084-1_18","DOI":"10.1007\/978-3-642-40084-1_18"},{"key":"149_CR36","doi-asserted-by":"crossref","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \ud835\udcaa ~ ( 2 0.054 n ) $\\tilde {\\mathcal {O}}(2^{0.054n})$ . In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, December 4\u20138, 2011. Proceedings, Lecture Notes in Computer Science, vol. 7073, pp 107\u2013124. Springer (2011). doi: 10.1007\/978-3-642-25385-0_6","DOI":"10.1007\/978-3-642-25385-0_6"},{"key":"149_CR37","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, May 31 - June 2, 2009. ACM, pp 333\u2013342 (2009). doi: 10.1145\/1536414.1536461","DOI":"10.1145\/1536414.1536461"},{"key":"149_CR38","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, May 22\u201324, 2005. ACM, pp 84\u201393 (2005). doi: 10.1145\/1060590.1060603","DOI":"10.1145\/1060590.1060603"},{"key":"149_CR39","doi-asserted-by":"crossref","unstructured":"Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory and Applications, 3rd International Colloquium, Toulon, November 2\u20134, 1988, Proceedings, Lecture Notes in Computer Science, vol. 388, pp 106\u2013113. Springer (1988)","DOI":"10.1007\/BFb0019850"},{"key":"149_CR40","doi-asserted-by":"crossref","unstructured":"Valiant, G.: Finding correlations in subquadratic time, with applications to learning Parities and Juntas. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, October 20\u201323, 2012, pp 11\u201320. IEEE Computer Society (2012). doi: 10.1109\/FOCS.2012.27","DOI":"10.1109\/FOCS.2012.27"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-015-0149-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12095-015-0149-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-015-0149-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T18:06:14Z","timestamp":1567015574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12095-015-0149-2"}},"subtitle":["Implementation and analysis"],"short-title":[],"issued":{"date-parts":[[2015,7,31]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s12095-015-0149-2","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,31]]}}}