Lover bounsd for the data complexity of correlation attacks on stream ciphers over fields of order 2^r

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.11435

Keywords:

stream cipher, correlation attacks, system of linear equations corrupted by noise over finite field, data complexity

Abstract

Correlation attacks are one of the most powerful attacks on stream ciphers, and methods of building such kind of attacks and security proofs of stream ciphers against them form a developed direction of modern cryptography. Over the past few years in connection with emergence of world-oriented stream ciphers, methods for building correlation attacks based on solving systems of linear equations corrupted by noise over finite fields or residue rings of order  are developed. In this article we investigate two such methods, the first of them consists of solving these systems of equations over fields of order , where , and the second one – in solving analogous systems of equations over a field of two elements. The obtained results can be used in security proofs of word-oriented stream ciphers against modern correlation attacks.

Author Biographies

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

Doctor of Technical Sciences, Assistant professor, Head of Research and Development Department 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”

post-graduate student, Institute of Special Communication and Information Protection National technical university of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”

References

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

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

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

Г. Балакин, "Эффективно решаемые классы си-стем булевых уравнений", Обозрение прикл. промышл. Матем, Т. 2, № 3, С. 494 – 501, 1995.

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

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

О. Логачев, А. Сальников, В. Ященко, Булевы функ-ции в теории кодирования и криптологии. М.: МЦНМО, 2004, 470 с.

А. Олексійчук, "Субекспоненційні алгоритми розв’язання систем лінійних булевих рівнянь зі спотвореними правими частинами", Прикладная радиоэлектроника, Т. 11, № 2, С. 3-11, 2012.

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

S. Bogos, F. Tramer, S. Vaudenay, On solving LPN using BKW and variants. Implementation and analysis. Cryp-tology ePrint Archive.

A. Canteaut, "Fast correlation attacks against stream ciphers and related open problems", The 2005 IEEE Information Theory Workshop on Theory and Practice in In-formation-Theoretic Security, pp. 49-54, 2005.

W. Meier, "Fast correlation attacks: methods and countermeasures Lecture Notes in Computer Science", FSE’2011, Proceedings, pp. 55 – 67, 2011.

B. Zhang, C. Xu, W. Meier, Fast correlation attacks over extension fields, largeunit linear approximation and cryptanaly-sis of SNOW 2.0. Cryptology ePrint Archive.

Downloads

Published

2017-06-26

How to Cite

Олексійчук, А. М., & Поремський, М. В. (2017). Lover bounsd for the data complexity of correlation attacks on stream ciphers over fields of order 2^r. Ukrainian Information Security Research Journal, 19(2), 126–131. https://doi.org/10.18372/2410-7840.19.11435

Issue

Vol. 19 No. 2 (2017)

Section

Articles

License

The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.

All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.

Copyright

Authors who publish their works in the journal:

  • retain the copyright to their publications;

  • grant the journal the right of first publication of the article;

  • agree to the distribution of their materials under the CC BY 4.0 license;

  • have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.