Application of fast Fourier transform for solving of the LPN problem over finite frobenius rings

Authors

  • Антон Миколайович Олексійчук National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»
  • Сергій Михайлович Ігнатенко National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

DOI:

https://doi.org/10.18372/2410-7840.19.12109

Keywords:

cryptology, provable security, LPN problem, system of linear equations corrupted by noise, fast Fourier transform, finite Frobenius ring

Abstract

The LPN problem is one of the most famous hard computational problems. In the most general formulation, it consists in solving a system of linear equations corrupted by noise over an arbitrary finite ring and includes, as a special case, the problem of decoding a random linear code over a finite field. Numerous (both symmetric and asymmetric) cryptosystems and protocols, which resistance relies on the complexity of solving the LPN problem are known. Therefore, the development of more efficient algorithms for solving this problem, in comparison with known algorithms, is an actual direction of modern cryptology. The most reliable (and most time-consuming) method for solving the LPN problem is the maximum likelihood method. It is well known that for systems of linear equations corrupted by noise over a finite field or a residue ring modulo power of two the complexity of this method can be reduced by applying algorithms for the fast Fourier transform. At the same time the question of how wide is the class of finite rings with this property remains open. In this paper we show that this is the class of finite Frobenius rings. This class is very extensive and includes, in particular, any (left or right) principal ideal ring. The obtained results indicate that it is possible to apply algorithms for the fast Fourier transform, well known for the case of a finite field or a residue ring modulo power of two, to the solving the LPN problem over an arbitrary finite Frobenius ring. This makes to significantly reduce the complexity of solving this problem by the maximum likelihood method.

Author Biographies

Антон Миколайович Олексійчук, National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Doctor of Technical Sciences, Assistant professor, Professor of The Institute of Special Communication and Information Protection of National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Сергій Михайлович Ігнатенко, National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

postgraduate of The Institute of Special Communication and Information Protection of National technical university of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

References

А. Алексейчук, С. Игнатенко, "Нижняя граница вероятности восстановления истинного решения системы линейных уравнений с искаженной правой частью над кольцом вычетов по модулю ", Захист інформації, № 4, С. 6-12, 2006.

А. Алексейчук, С. Игнатенко, "Оценки эффективности универсальных методов восстановления искаженных линейных рекуррент над кольцом вычетов по модулю ", Збірник наукових праць ІПМЕ НАН України, Вып. 20, С. 40-48, 2003.

Г. Балакин, "Введение в теорию случайных систем уравнений", Труды по дискретной математике, М.: ТВП, Т. 1, С. 1-18, 1997.

Р. Блейхут, Быстрые алгоритмы цифровой обработки сигналов Пер. с англ. М.: Мир, 1989, 448 с.

С. Игнатенко, "Модификация метода максимума правдоподобия решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю ", Захист інформації, № 1, С. 63-72, 2007.

А. Левитская, "Системы случайных уравнений над конечными алгебраическими структурами", Кибернетика и системный анализ, Т. 41, № 1, С. 82-116, 2005.

Р. Лидл, Г. Нидеррайтер, Конечные поля, пер. с англ, М.: Мир, 1988, 818 с.

С. Чечёта, Введение в дискретную теорию информации и кодирования: учебное издание, М.: МЦНМО, 2011, 224 с.

M. Albrecht, C. Cid, J. Faugere, R. Fitzpatric, L. Per-ret, "Algebraic algorithms for LWE problems", Cryptology ePrint Archive, Report 2014/1018. [Electronic resource]. Access: http://eprint.iacr.org/2014/1018.

E. Berlekamp, R. McElice, H. van Tilborg, "On the inherent intractability of certain coding problems", IEEE Trans. Inform. Theory, vol. 24, no. 3, pp. 384-386, 1978.

A. Blum, A. Kalai, H. Wasserman, "Noise-tolerant learning, the parity problem, and the statistical query model", J. ACM, vol. 50, no. 3, pp. 506-519, 2003..

A. Blum, M. Furst, M. Kearns, R. Lipton, "Cryptographic primitives based on hard learning problems", Crypto’93, LNCS 773, Springer-Verlag, pp. 278–291.

H. Gilbert, J. Mattew, M.J. Robshaw, Y. Seurin, "How to Encrypt with the LPN Problem", ICALP, Proceedings, Springer Verlag, pp. 679-690, 2008.

J. Golić, G. Morgari, "Vectorial fast correlation attacks", Cryptology ePrint Archive, Report 2004/247. [Electronic resource]. Access: http://eprint.iacr.org/ 2004/247.

F. Jönsson, T. Johansson, "Correlation attacks on stream ciphers over ", The 2001 International Symposium on Information Theory. ISIT’2001, Proceedings. Springer Verlag, pp. 140, 2001.

A. Juels, S. Weis, "Authenticating pervasive devices with Human protocols", Crypto’95. LNCS 3126. Springer-Verlag, pp. 293-308, 1995.

E. Kiltz, D. Masny, K. Pietrsak, "Simple chosen-ciphertext security from low-noise LPN", Public Key Cryptography. PKC 2014. Springer-Verlag, pp. 1-18, 2014.

A. Maximov, T. Johansson, "Fast computation for large distribution and its cryptographic application" Advanced in Cryptology. ASIACRYPT 2005. LNCS 3788. Springer-Verlag, pp. 313- 332.

O. Regev, "On lattices, learning with errors and ran-dom linear codes, and Cryptography", STOC 2005, Proceedings, Springer Verlag, pp. 84-93, 2005.

J. Wood, "Duality for modules over finite rings and application to coding theory", Amer. J. Math, vol. 121, pp. 555-575, 1999.

J. Wood, "A coding-theoretic characterization of finite Frobenius rings", [Electronic resource]. Access: https://www.semanticshol.org/paper/2006.

B. Zhang, C. Xu, W. Meier, "Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0", Cryptology ePrint Archive, Report 2016/311. [Electronic resource]. Access: http://eprint.iacr.org/2016/311.

Downloads

Published

2017-12-11

Issue

Vol. 19 No. 4 (2017)

Section

Articles

License

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).