Информационная система "Конференции"

Вычислительные и информационные технологии в науке, технике и образовании

Усть-Каменогорск, Казахстан, 11-14 сентября 2003 года

Тезисы докладов

Погружение задачи криптоанализа симметричных шифров в пропозициональную логику

Семенов А.А., Буранов Е.В.

Институт динамики систем и теории управления СО РАН (Иркутск)

Несмотря на успехи в развитии криптографии с открытыми ключами (несимметричной), интерес к аргументировано стойким системам симметричного шифрования не ослабевает. В первую очередь это связано с более высокой скоростью криптографических преобразований (по сравнению с несимметричными системами).

Одной из основных проблем современной криптографии является проблема получения содержательных оценок сложности вычислительных процедур, раскрывающих криптосистему. В несимметричной криптографии в основу криптосистемы пытаются заложить задачу, которая общепризнанно считается вычислительно сложной. Задача криптоанализа получаемой криптосистемы, как правило, сводится к некоторой задаче из NP. В ряде случаев удается доказать сводимость предположительно трудных задач к задачам криптоанализа несимметричных криптосистем (протокол и схема подписи Шнорра). Конечно, подобные результаты можно считать весьма условными, однако для симметричных шифров нет даже этого.

Аргументы в пользу общепринятых принципов симметричного шифрования базируются в основном на рассуждениях «правдоподобного» характера. Скажем, в качестве одного из обоснований принципа рассеивания и перемешивания К.Э. Шеннон приводит пример с раскатыванием теста. Требование «хорошего рассеивания и перемешивания» продолжает оставаться главным базовым принципом при построении симметричных криптосистем. В последнее время усилиями многих исследователей развивается новое направление, получившее название теории бент-функций. В основе концепции бент-функции также лежит «правдоподобное рассуждение», относительно максимально возможной нелинейности (по отношению к метрике Хэмминга) симметричного криптографического преобразования. На резонность данного тезиса можно возразить тем фактом, что, скажем, задача факторизации числа, являющегося произведением пары простых чисел, сводится к системе логических уравнений всего лишь второй степени, предположительно оставаясь вне класса P.

В предлагаемой работе описывается подход, позволяющий сводить задачи криптоанализа фактически произвольных симметричных шифров к задачам поиска выполняющих наборов простейших пропозициональных выражений (КНФ). Такая постановка проблемы позволяет рассматривать криптоанализ симметричных криптосистем с позиций единой «вычислительной модели», к тому же весьма перспективной в плане построения эвристических алгоритмов.

Основное утверждение работы представляет собой некий аналог теоремы Кука по отношению к вычислению булевых функций. Конструктивное доказательство этого утверждения дает способ кодирования полиномиальных по сложности шифрующих преобразований в пропозициональные выражения (КНФ). Результатом такого подхода является возможность качественного анализа сложности симметричных шифров. В частности, показано, что при некоторых (стандартных) условиях на возможности криптоаналитика, задача криптоанализа произвольного симметричного шифра с обратимым шифрующим преобразованием с вероятностью сколь угодно близкой к 1 находится в пересечении классов NP и coNP.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]