Application of sequential method for constructing a statistical attack on the LPN-C cipher system over residue ring modulo 2N

Authors

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

DOI:

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

Keywords:

post-quantum cryptography, LPN-C cipher system, system of linear equations corrupted by noise, residue ring modulo 2N, sequential method, generalized BKW algorithm, fast statistical attack

Abstract

LPN-C is one of the first post-quantum symmetric cipher systems, which security relies on the complexity of solving the LPN problem. The original version of the cipher system is defined over the field of two elements, nevertheless it is naturally generalized to the case of an arbitrary finite ring. Usually such generalization associated with the complication of the algebraic structure of underlain object used for construction of a cipher system increases its security to known attacks, however, as shown below, the LPN-C cipher system over a residue ring modulo 2Nrepresents an exception to this rule. In this article, an attack on the LPN-C cipher system over the residue ring modulo 2Nis proposed. The attack is based on recovering the key by sequential solving N systems of linear equations corrupted by noise over the field of order two. It is shown that the proposed attack is significantly more effective in comparison with traditional attacks of the same type based on direct solving these systems using the generalized BKW algorithm. The obtained results indicate that the residue rings modulo 2N, N≥2, are not expedient for constructing LPN-C cipher systems, since this does not lead to significant increasing the security in comparison with 1N= case.

Author Biography

Сергій Михайлович Ігнатенко, 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

А. Алексейчук, С. Игнатенко, "Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2N", Реєстрація, зберігання і обробка даних, Т. 7, №1,С. 11-23, 2005.

Г. Балакин, Ю. Никольский, "Последовательное применение метода максимума правдоподобия к решению систем уравнений с мешающими параметрами", Обозрение прикл. промышл. матем, Т. 2, Вып. 3, С. 468-476, 1995.

М. Гаврилкевич, В. Солодовников, "Эффективные алгоритмы решения задач линейной алгебры над полем из двух элементов", Обозрение прикл. промышл. матем, Т. 2, Вып. 3, С. 400-437, 1995.

А. Олексійчук, С. Ігнатенко, М. Поремський, "Системи лінійних рівнянь зі спотвореними правими частинами над скінченними кільцями", Математичне та комп’ютерне моделювання. Серія: Технічні науки, вип. 15, С. 150-155, 2017.

M. Albrecht, C. Cid, J.-C. Faugere, R. Fitzpatric, L. Perret, "Algebraic algorithms for LWE problems", Cryptology ePrint Archive, Report 2014/1018. 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.

S. Bogos, F. Tramer, S. Vaudenay, "On solving LPN using BKW and variants. Implementation and Analysis", Cryptology ePrint Archive, Report 2015/049. http://eprint.iacr.org/2015/049.

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

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

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. http://eprint.iacr.org/2016/311.

Published

2018-09-28

Issue

Section

Articles