Нижні межі інформаційної складності кореляційних атак на потокові шифри над полями порядку 2^r

Антон Миколайович Олексійчук, Михайло Васильович Поремський

Анотація


Коряляційні атаки відносяться до найбільш потужних атак на потокові шифри, а методи побудови таких атак та обґрунтування стійкості потокових шифрів відносно них утворюють розвинутий напрям сучасної криптології. Протягом останніх років у зв’язку з появою словоорієнтованих потокових шифрів спостерігається розвиток методів побудови кореляційних атак, що базуються на розв’язанні систем лінійних рівнянь зі спотвореними правими частинами над скінченними полями або кільцями лишків порядку 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.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN 2410-7840 (Online), ISSN 2221-5212 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory

Ulrich's Periodicals Directory