# zbMATH — the first resource for mathematics

On solving LPN using BKW and variants, Implementation and analysis. (English) Zbl 1338.94068
Summary: The Learning Parity with Noise problem ($$\mathsf {LPN}$$) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing $$\mathsf {LPN}$$ solving algorithms, both for the general case and for the sparse secret scenario. In practice, the $$\mathsf {LPN}$$-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of $$\mathsf {LPN}$$ solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms $$\mathsf {BKW}$$ and its variants. Following from our results, we further propose practical parameters for different security levels.

##### MSC:
 94A60 Cryptography
##### Keywords:
 [1] Albrecht, MR; Cid, C; Faugère, J; Fitzpatrick, R; Perret, L, On the complexity of the BKW algorithm on LWE, Des. Codes Crypt., 74, 325-354, (2015) · Zbl 1331.94051 [2] Albrecht, M.R., Faugère, 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-28, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8383, pp 429-445. Springer (2014), doi:10.1007/978-3-642-54631-0_25 · Zbl 1335.94025 [3] Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, pp 298-307. IEEE Computer Society, Cambridge (2003), doi:10.1109/SFCS.2003.1238204 [4] 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-20, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5677, pp 595-618. Springer (2009), doi:10.1007/978-3-642-03356-8_35 · Zbl 1252.94044 [5] 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-8, 2011, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6755, pp 403-415. Springer (2011). doi:10.1007/978-3-642-22006-7_34 · Zbl 1332.68099 [6] 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-3, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7739, pp 137-148. Springer (2012), doi:10.1007/978-3-642-36140-1_10 [7] 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-18, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841, pp 743-760. Springer (2011). doi:10.1007/978-3-642-22792-9_42 · Zbl 1287.94053 [8] 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 ’93, 13th Annual International Cryptology Conference, Santa Barbara, August 22-26, 1993. Proceedings, Lecture Notes in Computer Science, vol. 773, pp 278-291. Springer (1993). doi:10.1007/3-540-48329-2_24 · Zbl 0870.94021 [9] 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-23, 2000, Portland, pp 435-440. ACM (2000). doi:10.1145/335305.335355 [10] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC’13, Palo Alto, June 1-4, 2013, pp 575-584. ACM (2013). doi:10.1145/2488608.2488680 [11] 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-33. IEEE Computer Society (2006). doi:10.1109/SECPERU.2006.10 · Zbl 1201.94090 [12] Carrijo, J; Tonicelli, R; Imai, H; Nascimento, ACA, A novel probabilistic passive attack on the protocols HB and HB+, IEICE Transactions, 92-A, 658-662, (2009) [13] 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) [14] Cooley, JW; Tukey, JW, An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-301, (1965) · Zbl 0127.09002 [15] Damgård, I; Park, S, Is public-key encryption based on LPN practical, IACR Cryptology ePrint Archive, 2012, 699, (2012) [16] Döttling, N., Müller-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-6, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7658, pp 485-503. Springer (2012). doi:10.1007/978-3-642-34961-4_30 · Zbl 1292.94056 [17] Duc, A., Tramèr, 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-30, 2015, Proceedings, Part I, Lecture Notes in Computer Science, vol. 9056, pp 173-202. Springer (2015). doi:10.1007/978-3-662-46800-5_8 · Zbl 1365.94424 [18] 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-24, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7918, pp 107-126. Springer (2013). doi:10.1007/978-3-642-38553-7_6 · Zbl 1312.94047 [19] Fitzpatrick, R.: Some algorithms for learning with errors. Ph.D. thesis, Royal Holloway, University of London [20] 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-62. Springer (2006) · Zbl 1175.94078 [21] 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-17, 2008. Proceedings, Lecture Notes in Computer Science, vol. 4965, pp 361-378. Springer (2008). doi:10.1007/978-3-540-78967-3_21 · Zbl 1149.94334 [22] Grigorescu, E., Reyzin, L., Vempala, S.: On noise-tolerant learning of sparse parities and related problems. In: Kivinen, J., Szepesvári, C., Ukkonen, E., Zeugmann, T. (eds.) Algorithmic Learning Theory - 22nd International Conference, ALT 2011, Espoo, October 5-7, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6925, pp 413-424. Springer (2011). doi:10.1007/978-3-642-24412-4_32 · Zbl 1348.68194 [23] Guo, Q., Johansson, T., Lȯndahl, C.: A new algorithm for solving Ring-LPN with a reducible polynomial (2014). CoRR. arXiv:1409.0472 · Zbl 1359.94602 [24] Guo, Q., Johansson, T., Löndahl, 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-11, 2014. Proceedings, Part I, Lecture Notes in Computer Science, vol. 8873, pp 1-20. Springer (2014). doi:10.1007/978-3-662-45611-8_1 · Zbl 1306.94059 [25] 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-21, 2012. Revised Selected Papers, Lecture Notes in Computer Science, vol. 7549, pp 346-365. Springer (2012), 10.1007/978-3-642-34047-5_20 · Zbl 1282.94078 [26] Hoeffding, W, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 13-30, (1963) · Zbl 0127.10602 [27] 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-13, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2248, pp 52-66. Springer (2001). doi:10.1007/3-540-45682-1_4 · Zbl 1062.94549 [28] 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-18, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3621, pp 293-308. Springer (2005). doi:10.1007/11535218_18 · Zbl 1145.94470 [29] Katz, J; Shin, JS; Smith, A, Parallel and concurrent security of the HB and HB+ protocols, J. Cryptology, 23, 402-421, (2010) · Zbl 1201.94090 [30] 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-28 2014. Proceedings, Lecture Notes in Computer Science, vol. 8383, pp 1-18. Springer (2014). doi:10.1007/978-3-642-54631-0_1 · Zbl 1335.94059 [31] 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-19, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6632, pp 7-26. Springer (2011), doi:10.1007/978-3-642-20465-4_3 · Zbl 1281.94083 [32] Kirchner, P, Improved generalized birthday attack, IACR Cryptology ePrint Archive, 2011, 377, (2011) [33] Levieil, É., 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-8, 2006. Proceedings, Lecture Notes in Computer Science, vol. 4116, pp 348-359. Springer (2006). doi:10.1007/11832072_24 · Zbl 1152.94434 [34] 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-24, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3624, pp 378-389. Springer (2005). doi:10.1007/11538462_32 [35] 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-22, 2013. Proceedings, Part II, Lecture Notes in Computer Science, vol. 8043, pp 308-325. Springer (2013). doi:10.1007/978-3-642-40084-1_18 · Zbl 1316.94102 [36] May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $$\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-8, 2011. Proceedings, Lecture Notes in Computer Science, vol. 7073, pp 107-124. Springer (2011). doi:10.1007/978-3-642-25385-0_6 · Zbl 1227.94055 [37] 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-342 (2009). doi:10.1145/1536414.1536461 · Zbl 1304.94079 [38] 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-24, 2005. ACM, pp 84-93 (2005). doi:10.1145/1060590.1060603 · Zbl 1192.94106 [39] 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-4, 1988, Proceedings, Lecture Notes in Computer Science, vol. 388, pp 106-113. Springer (1988) · Zbl 1331.94051 [40] 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-23, 2012, pp 11-20. IEEE Computer Society (2012). doi:10.1109/FOCS.2012.27