Нижні межі інформаційної складності кореляційних атак на потокові шифри над полями порядку 2^r
DOI:
https://doi.org/10.18372/2410-7840.19.11435Ключові слова:
потоковий шифр, кореляційна атака, система рівнянь зі спотворениеми правими частинами над скінченним полем, інформаційна складністьАнотація
Коряляційні атаки відносяться до найбільш потужних атак на потокові шифри, а методи побудови таких атак та обґрунтування стійкості потокових шифрів відносно них утворюють розвинутий напрям сучасної криптології. Протягом останніх років у зв’язку з появою словоорієнтованих потокових шифрів спостерігається розвиток методів побудови кореляційних атак, що базуються на розв’язанні систем лінійних рівнянь зі спотвореними правими частинами над скінченними полями або кільцями лишків порядку q>=2. В даній статті досліджується два таких способи, першій з яких полягає у розв’язанні зазначених систем рівнянь над полями порядку 2r, де r>=2, а другий – у розв’язанні аналогічних систем рівнянь над полем з двох елементів. Отримано неасимптотичні нижні межі інформаційної складності зазначених атак, які уточнюють раніше відому евристичну оцінку. Отримані результати можуть бути використані при обґрунтуванні стійкості словоорієнтованих потокових шифрів відносно сучасних кореляційних атак.
Посилання
А. Алексейчук, С. Игнатенко, "Метод оптимиза-ции алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю ", Реєстрація, зберігання і обробка даних, Т. 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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:- Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
- Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
- Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
