Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Specifications and improvements of LPN solving algorithms

Specifications and improvements of LPN solving algorithms

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)
Add to cart

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.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Received 22/08/2018, Accepted 01/10/2019, Revised 20/08/2019, Published 12/11/2019

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)
      • 1. Esser, A., Kübler, R., May, A.: ‘LPN decoded’. Annual Int. Cryptology Conf. CRYPTO 2017, Santa Barbara, USA, 2017, pp. 486–514.
    2. 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. 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. 4)
      • 35. Peterson, W.W., Weldon, E.J.: ‘Error correcting codes’ (Wiley-IEEE Press, Hoboken, NJ, USA, 1961), pp. 69–94.
    5. 5)
      • 44. https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform.
    6. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 16)
      • 38. Wagner, T.J.: ‘Some additional quasi-perfect codes’, Inf. Control, 1967, 10, (3), pp. 334–334.
    17. 17)
      • 42. Zhang, B., Gong, X.: ‘New algorithms for solving LPN’. IACR Cryptology ePrint Archive, 2017.
    18. 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. 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. 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. 21)
      • 37. Wagner, T.J.: ‘A search technique for quasi-perfect codes’, Inf. Control, 1966, 9, (1), pp. 94–99.
    22. 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. 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)
      • 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. 25)
      • 6. Pietrzak, K.: ‘Subspace LWE’. Int. Conf. on Theory of Cryptography, Sicily, Italy, 2012, pp. 548–563.
    26. 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. 27)
      • 23. Kirchner, P.: ‘Improved generalized birthday attack’. IACR Cryptology Eprint Archive, 2011.
    28. 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. 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. 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. 31)
      • 43. Bogos, S., Vaudenay, S.: ‘Observations on the LPN solving algorithm from EUROCRYPT'16’, IACR Cryptology ePrint Archive, 2016.
    32. 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. 33)
      • 22. Levieil, É., Fouque P, A.: ‘An improved LPN algorithm’. Lect. Notes Comput. Sci., 2006, 4116, pp. 348–359.
    34. 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. 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. 36)
      • 31. Etzion, T., Mounits, B.: ‘Quasi-perfect codes with small distance’, IEEE Trans. Inf. Theory, 2005, 51, (11), pp. 3938–3946.
    37. 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. 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. 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. 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. 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. 42)
      • 34. Lint, J.H.V.: ‘Introduction to coding theory’, Mathematics, 1999, 86, (480), pp. 5–11.
    43. 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. 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. 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. 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.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2018.5448
Loading

Related content

content/journals/10.1049/iet-ifs.2018.5448
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address