Основы современной криптографии


Общие положения - часть 5


В вероятностных машинах новое состояние может зависеть еще и от случайной величины, ко­торая принимает значения 0 и 1 с вероятностью 1/2 каждое. Можно считать, что вероятностная машина Тьюринга имеет дополнитель­ную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и пе­реход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

Рассмотрим теперь следующий естественный вопрос: не является ли гипотеза PNP необходимым и достаточным условием для существо­вания стойких криптографических схем?

В самом деле, необходимость во многих случаях почти очевидна. Вернемся к рассмотренному выше примеру. Определим следующий язык:

L = {(k1,d,i)| $ сообщение т:

 и mi = 1}.

Ясно, что L О NP: можно просто угадать открытый текст т и про­верить за полиномиаль­ное время, что

 и i-й бит т равен 1. Если да, то входное слово (k1,d,i) принимается, в противном случае – отвергается.

В предположении P = NP

существует детерминированный полино­ми­альный алгоритм, распознающий язык L.

Зная k1 и d, с помощью это­го алгоритма можно последовательно, по биту, вычислить открытый текст т. Тем самым доказано, что криптосистема нестойкая.

Что же касается вопроса о достаточности предположения P

NP, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т. е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели.

Результатом всех этих попыток стало осознание сле­дующего факта: даже если PNP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательно­сти входных слов. Иными словами, в определение класса NP заложе­на мера сложности «в худшем случае». Для стойкости же криптогра­фической схемы необходимо, чтобы задача противника была сложной «почти всюду». Таким образом, стало ясно, что для криптографиче­ской стойкости необходимо существенно более сильное предположение, чем P

NP. А именно, предположение о существовании односторонних функций.




- Начало -  - Назад -  - Вперед -