Specifications and improvements of LPN solving algorithms
Specifications and improvements of LPN solving algorithms
- Author(s): Lin Jiao 1
- DOI: 10.1049/iet-ifs.2018.5448
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): Lin Jiao 1
-
-
View affiliations
-
Affiliations:
1:
State Key Laboratory of Cryptology , Beijing, 100878 , People's Republic of China
-
Affiliations:
1:
State Key Laboratory of Cryptology , Beijing, 100878 , People's Republic of China
- Source:
Volume 14, Issue 1,
January
2020,
p.
111 – 125
DOI: 10.1049/iet-ifs.2018.5448 , Print ISSN 1751-8709, Online ISSN 1751-8717
The hardness of LPN problems serves as security source of many primitives in lightweight and post-quantum cryptography, which enjoy extreme simplicity and efficiency for various applications. Accordingly there are several LPN solving algorithms proposed over past decade, and received quite a lot of attention recently. In this paper, we propose a new LPN solving algorithm using covering codes in the existing algorithmic framework with a new data structure of numerical value instead of vector quantity for convenience in table look-up, integrate the optimized procedures, and further presenting four main improvements. Firstly, we apply the technique of binary tree sum in Gaussian elimination and new BKW iterations. Secondly, we propose a global BKW collision optimization with tweakable reduction length, which is proved optimized. Thirdly, we extend the covering codes scope in service for lager bias and smaller data requirement with a bias estimation strategy. Finally, we propose a detailed parameter selection principle for given LPN instances. The best known classic results are given for the (512/532/592,1/8)-instances suggested in cryptographic schemes. Besides, we evaluate the performance on low-noise LPN and (k,1/4)-LPN instances, and further correct the lower length bounds of LPN instances with various bias for security levels of NIST's Post-Quantum Call.
Inspec keywords: data structures; public key cryptography; quantum cryptography; computational complexity; trees (mathematics)
Other keywords: LPN instances; post-quantum cryptography; LPN solving algorithm; comprehensive specifications; covering codes; algorithmic framework; optimised procedures; low-noise LPN; global BKW collision optimisation; learning parity with noise problems
Subjects: Combinatorial mathematics; Data security; Computational complexity; File organisation
References
-
-
1)
-
1. Esser, A., Kübler, R., May, A.: ‘LPN decoded’. Annual Int. Cryptology Conf. CRYPTO 2017, Santa Barbara, USA, 2017, pp. 486–514.
-
-
2)
-
9. Brakerski, Z., Langlois, A., Peikert, C., et al: ‘Classical hardness of learning with errors’. ACM Symp. on Theory of Computing, Palo Alto, CA, USA, 2013, pp. 575–584.
-
-
3)
-
10. Peikert, C.: ‘Public-key cryptosystems from the worst-case shortest vector problem: extended abstract’. ACM Symp. on Theory of Computing, Bethesda, MD, USA, 2009, pp. 333–342.
-
-
4)
-
35. Peterson, W.W., Weldon, E.J.: ‘Error correcting codes’ (Wiley-IEEE Press, Hoboken, NJ, USA, 1961), pp. 69–94.
-
-
5)
-
44. https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform.
-
-
6)
-
45. Wagner, D.: ‘A generalized birthday problem’. Annual Int. Cryptology Conf. (CRYPTO 2002), Santa Barbara, CA, USA, 2002 (LNCS, 2442), pp. 288–303.
-
-
7)
-
12. Applebaum, B., Cash, D., Peikert, C., et al: ‘Fast cryptographic primitives and circular-secure encryption based on hard learning problems’. Annual Int. Cryptology Conf. CRYPTO 2009, Santa Barbara, CA, USA, 2009, pp. 595–618.
-
-
8)
-
32. Gabidulin, E.M., Davydov, A.A., Tombak, L.M.: ‘Linear codes with covering radius 2 and other new covering codes’, IEEE Trans. Inf. Theory, 1991, 37, (1), pp. 219–224.
-
-
9)
-
2. Blum, A., Furst, M., Kearns, M., et al: ‘Cryptographic primitives based on hard learning problems’. Annual Int. Cryptology Conf. (CRYPTO 1993), Santa Barbara, CA, USA, 1993, pp. 278–291.
-
-
10)
-
13. Hopper, N.J., Blum, M.: ‘Secure human identification protocols’. Int. Conf. on Theory and Application of Cryptology and Information Security, ASIACRYPT 2001, Gold Coast, QLD, Australia, 2001, vol. 2248, pp. 52–66.
-
-
11)
-
41. Stern, J.: ‘A method for finding codewords of small weight’. Int. Colloquium on Coding Theory and Applications (Coding Theory 1988), Toulon, France, 1989, pp. 106–113.
-
-
12)
-
8. Lyubashevsky, V., Micciancio, D., Peikert, C., et al: ‘SWIFFT: a modest proposal for FFT hashing’. Int. Conf. on Fast Software Encryption, Lausanne, Switzerland, 2008, pp. 54–72.
-
-
13)
-
19. Stern, J.: ‘A new identification scheme based on syndrome decoding’. Annual Int. Cryptology Conf. (CRYPTO 1993), Santa Barbara, CA, USA, 1993, pp. 13–21.
-
-
14)
-
29. Baicheva, T., Bouyukliev, I., Dodunekov, S., et al: ‘Binary and ternary linear quasi-perfect codes with small dimensions’, IEEE Trans. Inf. Theory, 2007, 54, (9), pp. 4335–4339.
-
-
15)
-
33. Graham, R.L., Sloane, N.J.A.: ‘On the covering radius of codes’ IEEE Trans. Inf. Theory, 1985, 31, (3), pp. 385–401.
-
-
16)
-
38. Wagner, T.J.: ‘Some additional quasi-perfect codes’, Inf. Control, 1967, 10, (3), pp. 334–334.
-
-
17)
-
42. Zhang, B., Gong, X.: ‘New algorithms for solving LPN’. IACR Cryptology ePrint Archive, 2017.
-
-
18)
-
39. Lyubashevsky, V.: ‘The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem’ in Michel, G., Klaus, J., José, D.P., Rolim, L.T. (Eds.): ‘Approximation, randomization and combinatorial optimization. Algorithms and techniques’ (Springer-Verlag, Berlin, Germany, 2005), pp. 378–389.
-
-
19)
-
27. Bogos, S., Vaudenay, S.: ‘Optimization of LPN solving algorithms’. Int. Conf. on Theory and Application of Cryptology and Information Security (ASIACRYPT 2016), Hanoi, Vietnam, 2016.
-
-
20)
-
25. Guo, Q., Johansson, T., Löndahl, C.: ‘Solving LPN using covering codes’. Int. Conf. on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2014), Kaoshiung, Taiwan, 2014, pp. 1–20.
-
-
21)
-
37. Wagner, T.J.: ‘A search technique for quasi-perfect codes’, Inf. Control, 1966, 9, (1), pp. 94–99.
-
-
22)
-
7. Regev, O.: ‘On lattices, learning with errors, random linear codes, and cryptography’. ACM Symp. on Theory of Computing, Baltimore, MD, USA, 22–24 May 2005, pp. 84–93.
-
-
23)
-
21. Blum, A, Kalai, A, Wasserman, H.: ‘Noise-tolerant learning, the parity problem, and the statistical query model’, J. ACM, 2003, 50, (4), pp. 506–519.
-
-
24)
-
24. Bernstein, D.J., Lange, T.: ‘Never trust a bunny’. Int. Workshop on Radio Frequency Identification: Security and Privacy Issues (RFIDSec 2012), Nijmegen, The Netherlands, 2012, pp. 137–148.
-
-
25)
-
6. Pietrzak, K.: ‘Subspace LWE’. Int. Conf. on Theory of Cryptography, Sicily, Italy, 2012, pp. 548–563.
-
-
26)
-
40. May, A., Meurer, A., Thomae, E.: ‘Decoding random linear codes in O(20.054n)’. Int. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2011), Seoul, Republic of Korea, 2011, pp. 107–124.
-
-
27)
-
23. Kirchner, P.: ‘Improved generalized birthday attack’. IACR Cryptology Eprint Archive, 2011.
-
-
28)
-
18. Gilbert, H., Robshaw, M.J., Seurin, Y.: ‘How to encrypt with the LPN problem’. Int. Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, 2008, pp. 679–690.
-
-
29)
-
20. Jain, A., Krenn, S., Pietrzak, K., et al: ‘Commitments and efficient zero-knowledge proofs from learning parity with noise’. Int. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2012), Beijing, People's Republic of China, 2012, pp. 663–680.
-
-
30)
-
16. Kiltz, E., Pietrzak, K., Cash, D., et al: ‘Efficient authentication from hard learning problems’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2011, Tallinn, Estonia, 2011, pp. 7–26.
-
-
31)
-
43. Bogos, S., Vaudenay, S.: ‘Observations on the LPN solving algorithm from EUROCRYPT'16’, IACR Cryptology ePrint Archive, 2016.
-
-
32)
-
46. Regev, O.: ‘The learning with errors problem (invited survey)’. 2010 IEEE 25th Annual Conf. on Computational Complexity, Cambridge, MA, USA, 2010, pp. 191–204.
-
-
33)
-
22. Levieil, É., Fouque P, A.: ‘An improved LPN algorithm’. Lect. Notes Comput. Sci., 2006, 4116, pp. 348–359.
-
-
34)
-
30. Cohen, G., Karpovsky, M., Mattson, H., et al: ‘Covering radius-survey and recent results’, IEEE Trans. Inf. Theory, 2003, 31, (3), pp. 328–343.
-
-
35)
-
3. Katz, J., Ji, S.S.: ‘Parallel and concurrent security of the HB and HB+ protocols’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2006), St. Petersburg, Russia, 2006, pp. 73–87.
-
-
36)
-
31. Etzion, T., Mounits, B.: ‘Quasi-perfect codes with small distance’, IEEE Trans. Inf. Theory, 2005, 51, (11), pp. 3938–3946.
-
-
37)
-
15. Dodis, Y., Kiltz, E., Pietrzak, K., et al: ‘Message authentication, revisited’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2012, Cambridge, UK, 2012, pp. 355–374.
-
-
38)
-
28. Minder, L., Sinclair, A.: ‘The extended k-tree algorithm’. Twentieth ACM-SIAM Symp. on Discrete Algorithms, New York, NY, USA, 2009, pp. 586–595.
-
-
39)
-
14. Juels, A., Weis, S.A.: ‘Authenticating pervasive devices with human protocols’. Annual Int. Cryptology Conf. CRYPTO 2005, Santa Barbara, CA, USA, 2005, pp. 293–308.
-
-
40)
-
11. Pietrzak, K.: ‘Cryptography from learning parity with noise’. Int. Conf. on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic, 2012, pp. 99–114.
-
-
41)
-
26. Zhang, B., Jiao, L., Wang, M.: ‘Faster algorithms for solving LPN’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2016), Vienna, Austria, 2016, pp. 168–195.
-
-
42)
-
34. Lint, J.H.V.: ‘Introduction to coding theory’, Mathematics, 1999, 86, (480), pp. 5–11.
-
-
43)
-
36. Tokura, N., Taniguchi, K., Kasami, T.: ‘A search procedure for finding optimum group codes for the binary symmetric channel’, IEEE Trans. Inf. Theory, 1967, 13, (4), pp. 587–594.
-
-
44)
-
4. Gilbert, H., Robshaw, M.J.B., Seurin, Y.: ‘HB#: increasing the security and efficiency of HB+’. Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2008, Tel Aviv, Israel, 2008, pp. 361–378.
-
-
45)
-
17. Feldman, V., Gopalan, P., Khot, S., et al: ‘New results for learning noisy parities and halfspaces’. IEEE Symp. on Foundations of Computer Science, Berkeley, CA, USA, 2006, pp. 563–574.
-
-
46)
-
5. Heyse, S., Kiltz, E., Lyubashevsky, V., et al: ‘Lapin: an efficient authentication protocol based on ring-LPN’. Int. Workshop on FAST Software Encryption (FSE 2012), Washington, DC., USA, 2012, pp. 346–365.
-
-
1)

Related content
