Односторонняя функция с потайным входом

Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин[1]. Но первой системой, в которой были использованы такие идеи, считается система, изобретённая в 1973 году Клиффордом Коксом, работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года[2].

Статья описывала новый способ для минимизации необходимости передачи ключей по защищённым каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписи[3].

Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом и в устройстве цифровой подписи[4]. Криптосистема с открытым ключом — система, в которой открытый ключ передается по незащищённому каналу. Смысл цифровой подписи заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой.

Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищёнными[1].

Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально. Например, сначала предполагалось использовать функции, основанные на задаче о сумме подмножеств. Вскоре выяснилось, что этот способ неприемлем. Примером подобной реализации может служить ранцевая криптосистема Меркла — Хеллмана.

В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина [5]. Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.

В 2008 году были представлены односторонние функции с потайным входом, допускающие потерю информации о изначальном сообщении.

Данный тип функций (lossy trapdoor function), основывающийся на идее повреждения значительной части информации[6], был представлен Крисом Пейкертом и Брентом Уотерсом [7] в частности, как средство построения схемы шифрования с открытым ключом с выбранным-зашифрованным текстом.

Множество данных функций состоит из семейства двух функций:

1. Повторяют работу односторонней функции с потайным входом без потери части информации, то есть при наличии «лазейки» можно эффективно вычислить ${\displaystyle x}$ по значению ${\displaystyle f(x)}$.
2. Теряют часть информации о входе, тогда у выхода ${\displaystyle f(x)}$ существует много прообразов (то есть нет возможно однозначно обратить функцию).

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

Функция «All-but-one» (ABO) может быть построена из набора односторонних функций с потайным входом и с достаточной потерей информации.

Набор функций ABO связан с множеством ${\displaystyle B}$, элементы которого называются ветвями. Генератор функции ABO принимает дополнительный параметр ${\displaystyle b^{*}\in B}$, называемый ветвью с потерями, и выводит функцию ${\displaystyle g({\cdot },{\cdot })}$ и потайной ход t. Функция ${\displaystyle g}$ обладает тем свойством, что для любой ветви ${\displaystyle b\not =b^{*}}$ функция ${\displaystyle g(b,\cdot )}$ обладает потайным входом (и может быть инвертирована с ${\displaystyle t}$), но функция ${\displaystyle g(b^{*},\cdot )}$ — функция с потерями. Более того, ветвь с потерями скрыта (вычислительно) по описанию ${\displaystyle g}$.[8].

«All-but-N»(ABN) функции имеют ровно ${\displaystyle N}$ веток с потерями; все другие ветки обладают потайным входом. Это можно использовать для точного определения зашифрованных текстов с помощью веток с потерями — все другие зашифрованные тексты соответствуют функциям с лазейкой и могут быть дешифрованы. Обратите внимание, что ABN кодируют набор веток с потерями по их ключу. То есть вычислительно неограниченный противник всегда может использовать грубую силу, для поиска ветвей, приводящих к функции с потерями.

Следовательно, ABN функции имеют серьезный недостаток: а именно, пространственная сложность ключей линейна в ${\displaystyle N.}$[9]

«All-but-many»(ABM) функция имеет суперполиномиальное множество ветвей с потерями, которые требуют наличия специального потайного хода.

Самое важное отличие от ABN-функции: с ABN набор ветвей с потерями указывается первоначально, во время построения, а ABM функции имеют лазейку, позволяющую пробовать дешифровку «на лету» из большого пула ветвей с потерями. Без этого потайного хода и даже при произвольном известном множестве ветвей с потерями нет возможности найти другую ветвь, не принадлежащую известному множеству. Это, в частности, позволяет создавать экземпляры ABM с компактными ключами и изображениями, размер которых не зависит от количества ветвей с потерями.

Данные конструкции можно рассматривать как «замаскированные» варианты сигнальных схем Boneh-Boyen (BB). В частности, ветви с потерями соответствуют действительным сигнатурам. Тем не менее, чтобы метки потерь и метки потайных ходов казались неотличимыми, необходимо делать слепые подписи, путем их шифрования или путем умножения на случайный элемент подгруппы.[9]

Построение функций «All-but-one» с потайным входом несколько более общее. Каждая ветвь ${\displaystyle b}$ функции просто соответствует другой матрице ${\displaystyle M_{b}}$, шифрование которой может быть получено из публичного описания функции. Функция генерируется так, что ${\displaystyle M_{b}}$ является обратимой матрицей (и вычисляется с помощью потайного входа) для всех ветвей ${\displaystyle b}$, тогда как ${\displaystyle M_{b^{*}}=0}$ для ветвей с потерями ${\displaystyle b^{*}}$

Возьмём число ${\displaystyle n=p\cdot q}$, где ${\displaystyle p}$ и ${\displaystyle q}$ принадлежат множеству простых чисел. Считается, что для данного числа ${\displaystyle n}$ вычисление ${\displaystyle p}$ и ${\displaystyle q}$ является математически трудной задачей. Функция шифрования RSA — ${\displaystyle E(m)=m^{e}\mod n}$, где ${\displaystyle e}$ — взаимнопростое с ${\displaystyle (p-1)(q-1)}$. Числа ${\displaystyle p}$ и ${\displaystyle q}$ являются потайным входом, зная которые вычислить обратную функцию ${\displaystyle E^{-1}}$ легко. На сегодняшний день лучшей атакой на RSA является факторизация числа ${\displaystyle n}$[10][11].

Рассмотрим функцию ${\displaystyle F(x,n)=x^{2}mod(n)}$, где ${\displaystyle n=p\cdot q}$, а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию ${\displaystyle f^{-1}}$ легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей[12].

Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Она основывается на задаче дискретного логарифмирования[13].

Алгоритм

1. Алиса выбирает простое число p и произвольное число a.
2. Алиса вычисляет свой открытый ключ (а, b), где ${\displaystyle b=a^{c}}$, ${\displaystyle 1<c<p}$
3. Боб выбирает ${\displaystyle 1<d<p}$ и шифрует сообщение m: ${\displaystyle (m_{1},m_{2})=(a^{d},m\cdot b^{d})}$
4. Алиса расшифровывает сообщение ${\displaystyle m=m_{2}\cdot (m_{1}^{c})^{-1}.}$

Алгоритм[14]

1. Алиса случайным образом выбирает вектор в конечном поле.
2. Алиса строит полиномы, которые в точке, задаваемой этим вектором, обращаются в ноль.
3. Боб генерирует сумму ${\displaystyle p=\sum {q_{i}\cdot b_{i}}}$
4. Боб посылает ${\displaystyle p+m}$

Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы для «лазейки», например, вычислительная задача Диффи-Хеллмана (CDH) и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.