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


Односторонние функции и функции-ловушки


Центральным понятием в теории асимметричных криптогра­фических систем является понятие односторонней функции.

Неформально под односторонней функцией

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

Под функцией мы будем понимать семейство отображений {fn}, где fn: Sn

® Sm, m = m(n). Для простоты предположим, что n пробегает натуральный ряд, а отображения fn определены всюду. Функция f

называется честной, если $ полином q(x), такой что " n q(m(n)) і n.

Формально понятие односторонней функции описывается следующим образом:

Определение 3.1. Четная функция f называется односторонней, если

1.         Существует полиномиальный алгоритм, который для всякого x вычисляет f(x);

2.         Для любой полиномиальной вероятностной машины Тьюринга A выполнено следующее. Пусть строка x выбрана случайным образом из множества Sn. Тогда для любого полинома p и всех достаточно больших n

P{f(A(f(x))) = f(x)} < 1/p(n).

Второе условие качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга A может по данному y

найти x из уравнения f(x) = y лишь с пренебрежимо малой вероятностью.

Заметим, что требование честности опустить нельзя. Поскольку длина входного слова f(x) машины A равна m, ей может не хватить полиномиального от m времени просто на выписывание строки x.

Существование односторонних функций является необходимым условием стойкости многих криптосистем. Вернемся к примеру, приведенному в п. 3.1. Рассмотрим функцию f, такую, что f(r) = k1. Она вычислима с помощью алгоритма G за полиномиальное время. Покажем, что если f – не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм A, обращающий f

с вероятностью по крайней мере 1/p(n) для некоторого полинома p. Злоумышленник может подать на вход алгоритма значение ключа k1




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



Книжный магазин