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

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


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

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

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

Функция называется честной, если существует полином такой, что для всех .

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

если

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

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

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

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

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

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

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




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


[an error occurred while processing this directive]