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

Issue

Vol. 19 No. 2 (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).