×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[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., Lȯ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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.