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

Next: 2.4. Псевдослучайные генераторы Up: 2. Криптография и теория Previous: 2.2. Криптография и гипотеза Contents: Содержание

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

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

Поскольку понятие односторонней функции - центральное в математической криптографии, ниже мы даем его формальное определение.

Пусть $\Sigma ^n=\{ 0,1\} ^n$ - множество всех двоичных строк длины . Под функцией мы понимаем семейство $\{ f_n\}$ , где $f_n\colon\Sigma ^n\to \Sigma ^m$ , . Для простоты изложения мы предполагаем, что пробегает весь натуральный ряд и что каждая из функций всюду определена.

Функция называется честной, если существует полином такой, что $n\leq q(m(n))$ для всех .

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

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

2. Для любой полиномиальной вероятностной машины Тьюринга выполнено следующее. Пусть строка выбрана наудачу из множества $\Sigma^n$ (обозначается $x\in _R\Sigma^n$ ). Тогда для любого полинома и всех достаточно больших

$\begin{displaymath}Pr\{ f(A(f(x)))=f(x)\} <1/p(n).\end{displaymath}$

Вероятность здесь определяется случайным выбором строки

и случайными величинами, которые

использует в своей работе.

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

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

Ясно, что из предположения о существовании односторонних функций следует, что P $\neq$ NP. Однако, не исключена следующая ситуация: P $\neq$ NP, но односторонних функций нет.

Существование односторонних функций является необходимым условием для стойкости многих типов криптографических схем. В некоторых случаях этот факт устанавливается достаточно просто. Обратимся опять к примеру 1. Рассмотрим функцию такую, что . Она вычислима с помощью алгоритма за полиномиальное время. Покажем, что если - не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм , который инвертирует с вероятностью по крайней мере для некоторого полинома . Здесь - длина ключа . Противник может подать на вход алгоритму ключ и получить с указанной вероятностью некоторое значение из прообраза. Далее противник подает на вход алгоритма и получает пару ключей . Хотя не обязательно совпадает с , тем не менее, по определению криптосистемы $D_{K_2'}(E_{K_1}(m))=m$ для любого открытого текста . Поскольку найден с вероятностью по крайней мере , которая в криптографии не считается пренебрежимо малой, криптосистема нестойкая.

Для других криптографических схем подобный результат доказывается не столь просто. В работе Импальяццо и Луби [7] доказана необходимость односторонних функций для существования целого ряда стойких криптографических схем.

Из всего сказанного следует, что предположение о существовании односторонних функций является самым слабым криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем различных типов. На выяснение того, является ли это условие и в самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односторонних функций можно пояснить на следующем примере. Пусть - односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ - секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования и дешифрования оба зависят от этого секретного ключа и таковы, что для любого открытого текста . Ясно, что если криптограмму сообщения вычислять как , то противник, перехвативший , может вычислить лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет восстановить сообщение из криптограммы законный получатель? Во-вторых, из того, что функция односторонняя следует лишь, что противник не может вычислить все сообщение целиком. А это - весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму , не мог вычислить ни одного бита открытого текста.

На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для существования стойких криптосистем с секретным ключом, а также стойких криптографических протоколов нескольких типов, включая протоколы электронной подписи. С другой стороны, имеется результат Импальяццо и Рудиха [9], который является достаточно сильным аргументом в пользу того, что для некоторых типов криптографических схем (включая протоколы распределения ключей типа Диффи-Хеллмана) требуются более сильные предположения, чем предположение о существовании односторонних функций. К сожалению, этот результат слишком сложный, чтобы его можно было разъяснить в настоящей главе.