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

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


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

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

Нетрудно убедиться, что для существования псевдослучайных генераторов необходимо существование односторонних функций. В самом деле, сама функция должна быть односторонней. Доказательство этого простого факта мы оставляем читателю в качестве упражнения. Вопрос о том, является ли существование односторонних функций одновременно и достаточным условием, долгое время оставался открытым. В 1982 г. Яо [] построил псевдослучайный генератор, исходя из предположения о существовании односторонних перестановок, т.е. сохраняющих длину взаимнооднозначных односторонних функций. За этим последовала серия работ, в которых достаточное условие все более и более ослаблялось, пока наконец в 1989-1990 гг. Импальяццо, Левин и Луби [] и Хостад [] не получили следующий окончательный результат.

Теорема 1.   Псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции.

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

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

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




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


[an error occurred while processing this directive]