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

Псевдослучайные генераторы - часть 3


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

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

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

как подпрограмму, подавая ей на вход строку . Получив от пару , проверяет, действительно ли и если да, то выдает 1, в противном случае - 0, и останавливается. Легко видеть, что работает за полиномиальное (от ) время. Убедимся, что алгоритм

отличает псевдослучайные строки, порожденные генератором , от случайных строк длины . В самом деле, если строки , поступающие на вход , являются случайными, то - криптограмма шифра Вернама и, согласно теореме Шеннона, . Если строки порождены генератором , то криптограммы имеют такое же распределение вероятностей, как в криптосистеме , и, согласно предположению, для бесконечно многих . Полученное противоречие с определением псевдослучайного генератора доказывает утверждение о стойкости криптосистемы .

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

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

Next: 2.5. Доказательства с нулевым

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

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

Contents:




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


[an error occurred while processing this directive]