Skip to main content
SpringerLink
Log in

On solving L P N using B K W and variants

Implementation and analysis

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

The Learning Parity with Noise problem (L P N) 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 L P N solving algorithms, both for the general case and for the sparse secret scenario. In practice, the L P N-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 L P N solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms B K W and its variants. Following from our results, we further propose practical parameters for different security levels.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. Definition 2 of [33] assumes independence of samples but Lemma 2 of [33] shows the reduction without proving independence.

  2. The term (a−1)2b is not included in Theorem 1 from [33]. This factor represents the number of queries lost during the reduction phase and it is the dominant one for all the algorithms except B K W ∗.

  3. The term b2b in the time complexity is missing in [33]. While in general kan is the dominant term, in the special case where a=1 (thus we apply no reduction step) a complexity of \(\mathcal {O}(kan)\) would be wrong since, in this case, we apply the Walsh-Hadamard transform on the whole secret and the term k2k dominates the final complexity.

  4. For the computation of n the authors of [24] use the term \(4 \ln \left (2^{\ell }\right )\) instead of \(8 \ln \left (\frac {2^{\ell }}{\theta }\right )\). If we use our formula, we obtain that we need more than 3⋅2b queries and obtain a complexity of t = 280.08.

  5. This n corresponds to covering code reduction using L F 1. For L F 2 reduction steps we need to have \(n = 3 \cdot 2^{b} + k \geq 8 \ln \left (\frac {2^{\ell }}{\theta }\right )\frac {1}{\delta ^{2^{a+1}} \varepsilon _{\mathsf {set}}^{2}}\).

  6. Given that we receive uniformly distributed vectors from the L P N oracle, from n+2 vectors v we expect to have n linearly independent ones.

  7. http://openmp.org/wp

  8. http://m4ri.sagemath.org/

References

  1. Albrecht, M.R., Cid, C., Faugère, J., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74(2), 325–354 (2015). doi:10.1007/s10623-013-9864-x

    Article  MathSciNet  MATH  Google Scholar 

  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

  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

  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

  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

  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

  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

  12. 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–662 (2009)

    Article  Google Scholar 

  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, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comput. 19(90), 297–301 (1965) http://www.jstor.org/stable/ 2003354

    Article  MathSciNet  MATH  Google Scholar 

  15. Damgård, I., Park, S.: Is public-key encryption based on LPN practical IACR Cryptology ePrint Archive 2012, 699 (2012)

    Google Scholar 

  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

  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

  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

  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)

  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

  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

  23. Guo, Q., Johansson, T., Lȯndahl, C.: A new algorithm for solving Ring-LPN with a reducible polynomial (2014). CoRR. arXiv:1409.0472

  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

  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

  26. Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963) http://www.jstor.org/stable/2282952?

    Article  MathSciNet  MATH  Google Scholar 

  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

  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

  29. Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB+ protocols . J. Cryptology 23(3), 402–421 (2010). doi:10.1007/s00145-010-9061-2

    Article  MathSciNet  MATH  Google Scholar 

  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

  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

  32. Kirchner, P.: Improved generalized birthday attack. IACR Cryptology ePrint Archive 2011, 377 (2011) http://eprint.iacr.org/2011/377

    Google Scholar 

  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

  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

  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

  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

  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

  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)

  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

Download references

Acknowledgments

We would like to thank Thomas Johansson and all the authors of [24] for their help in providing us with their paper and for their useful discussions. We further congratulate them for receiving the Best Paper Award of Asiacrypt 2014.

Author information

Authors and Affiliations

  1. EPFL, CH-1015, Lausanne, Switzerland

    Sonia Bogos, Florian Tramèr & Serge Vaudenay

Authors
  1. Sonia Bogos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Florian Tramèr
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Serge Vaudenay
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sonia Bogos.

Additional information

Supported by a grant of the Swiss National Science Foundation, 200021_143899/1.

Appendices

Appendix A: Hoeffding’s bounds

Theorem 12

[26] Let X 1 ,X 2 ,…,X n be n independent variables. We are given that \(\Pr [X_{i} \in [\alpha _{i},\beta _{i} ]] = 1\) for 1≤i≤n. We define X=X 1 +…+X n and E[X] is the expected value of X. We have that

$$\Pr[X-E[X] \geq \lambda] \leq e^{- \frac{2\lambda^{2}}{{\sum}_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}} $$

and

$$\Pr[X-E[X] \leq - \lambda] \leq e^{- \frac{2\lambda^{2}}{{\sum}_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}}, $$

for any λ>0.

Appendix B: L F 1 - full recovery of the secret

We provide here an example of the L F 1 algorithm, for the L P N 512,0.125 instance, where we recover the full secret. We provide the values of a, b, n and time complexity to show that indeed the number of queries for the first iteration, dominates the number of queries needed later on. Also, this shows that the time complexity of recovering the first block dominates the total time complexity. For L P N 512,0.125, we obtain the following values (See Table 24).

Table 24 Full secret recovery for the instance L P N 512,0.125
Full size table

The way one can interpret this table is the following: L F 1 recovers first 74 bits by taking a = 7 and requiring 276.59 queries. The total complexity of this step, i.e. the reduction, solving and updating operation, is of 288.43 bit operations. Next, L F 1 solves L P N 438,0.125 and continues this process until it recovers the whole secret.

We can easily see that indeed the number of queries and the time complexity of the first block dominate the other values.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bogos, S., Tramèr, F. & Vaudenay, S. On solving L P N using B K W and variants. Cryptogr. Commun. 8, 331–369 (2016). https://doi.org/10.1007/s12095-015-0149-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-015-0149-2

Keywords

Mathematics Subject Classification (2010)

Search

Navigation