Введение в криптографию
[an error occurred while processing this directive]

Криптография и гипотеза PNP - часть 2


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

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

существует сообщение такое, что и его -ый бит равен 1.

Ясно, что : вместо описанного во введении полного перебора можно просто угадать открытый текст  и проверить за полиномиальное время, что и -ый бит равен 1. Если да, то входное слово принимается, в противном случае - отвергается.

В предположении P=NP существует детерминированный полиномиальный алгоритм, распознающий язык . Зная

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

Тот же подход: угадать секретный ключ и проверить (за полиномиальное время) правильность догадки, применим в принципе и к другим криптографическим схемам. Однако, в некоторых случаях возникают технические трудности, связанные с тем, что по информации, которая имеется у противника, искомая величина (открытый текст, секретный ключ и т.п.) восстанавливается неоднозначно.

Что же касается вопроса о достаточности предположения PNP, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т.е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание следующего факта: даже если PNP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входных слов. Иными словами, в определение класса NP заложена мера сложности ``в худшем случае''. Для стойкости же криптографической схемы необходимо, чтобы задача противника была сложной ``почти всюду''. Таким образом, стало ясно, что для криптографической стойкости необходимо существенно более сильное предположение, чем PNP. А именно, предположение о существовании односторонних функций.

Next: 2.3. Односторонние функции

Up: 2. Криптография и теория

Previous: 2.1. Введение

Contents:




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


[an error occurred while processing this directive]