Односторонняя функция с потайным входом (англ. trapdoor function, TDF) — это односторонняя функция ${\displaystyle f}$ из множества ${\displaystyle X}$ в множество ${\displaystyle Y}$, обладающая свойством (потайным входом, лазейкой), благодаря которому становится возможным найти для любого ${\displaystyle y\in Im{f},x\in X}$ такое, что ${\displaystyle f(x)=y}$, то есть обратить функцию.

Односторонние функции с потайным входом широко используются в асимметричных методах шифрования (шифрование с открытым ключом) таких как: RSA, функция Рабина, схемы Эль-Гамаля, криптосистема McEliece, криптографическая система NTRUEncrypt, Polly Cracker, а также в менее популярной, из-за своей криптографической нестойкости, ранцевой криптосистеме Меркла — Хеллмана.

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

Функция ${\displaystyle f:\{0,1\}^{l(n)}\times \{0,1\}^{n}{\xrightarrow[{}]{}}\{0,1\}^{m(n)}}$, где

${\displaystyle \{0,1\}^{l(n)}}$ — множество открытых ключей,

${\displaystyle \{0,1\}^{m(n)}}$ — отображаемый элемент, состоящий из n битов,

называется односторонней с потайным входом, если

1. Она является односторонней;
2. Существует эффективный алгоритм, который при заданных открытом ключе ${\displaystyle Y}$, сообщении ${\displaystyle M}$ и значении функции вычисляет ${\displaystyle M'}$ такое, что ${\displaystyle f(M)=f(M')}$ для некоторого ключа ${\displaystyle Z}$;
3. Для данного сообщения ${\displaystyle M}$ и функции ${\displaystyle f(M)}$ трудно найти сообщение ${\displaystyle M'\neq M}$ такое, что ${\displaystyle f(M)=f(M')}$.

Понятие односторонней функции с потайным входом было введено в середине 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]

Чтобы отметить основные принципы, предположим, что общая криптосистема с поддержкой CPA имеет несколько специальных (но неформально описанных) свойств.

Первое свойство предполагает, что лежащая в основе криптосистема аддитивно-гомоморфна. Функция ${\displaystyle f}$ (односторонняя функция с лазейкой или функция с потерями) на ${\displaystyle \{0,1\}^{n}}$ определяется путем шифрования поэлементно квадратной матрицы ${\displaystyle M}$.

Для оценки ${\displaystyle f(x)}$, подаем вход ${\displaystyle x\in \{0,1\}^{n}}$ — n-мерный бинарный вектор и вычислим (поэтапно) шифрование линейного произведения ${\displaystyle x*M}$, применяя гомоморфные операции к зашифрованным записям ${\displaystyle M}$.

Для функции с потайным входом зашифрованная матрица ${\displaystyle M}$ является единичной матрицей ${\displaystyle I}$, а лазейка является ключом дешифрования для криптосистемы. Функция ${\displaystyle f}$ обратима с помощью потайного входа, потому что ${\displaystyle f(x)}$ — это входное шифрование ${\displaystyle x*I=x}$, которое может быть дешифровано до значения каждого бита ${\displaystyle x}$.

Для функции с потерями зашифрованная матрица ${\displaystyle M}$ является матрицей, состоящей из нулей: ${\displaystyle M=0}$. Тогда, для каждого входного сообщения ${\displaystyle x}$, значение ${\displaystyle f(x)}$ является поэлементным шифрованием нулевого-вектора, поэтому ${\displaystyle f}$ "теряет" информацию о ${\displaystyle x}$ . Однако этого недостаточно для обеспечения полной потери, поскольку выходные зашифрованные сообщения по-прежнему несут некоторую внутреннюю случайную информацию, которая может служить источником данных о входном сообщении. Поэтому необходим дополнительный контроль за их поведением. Для этого существуют специальные свойства криптосистемы:

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

С этими двумя свойствами зашифровываем матрицу ${\displaystyle M}$ особым образом. Каждый столбец ${\displaystyle j}$ матрицы связан с другим ключом ${\displaystyle p_{kj}}$, а лазейка — это набор соответствующих ключей расшифровки. Через каждую строку ${\displaystyle i}$ шифруем запись ${\displaystyle m_{i,j}}$ под ключ ${\displaystyle p_{kj}}$ и ту же случайность ${\displaystyle r_{i}}$ (используя новую случайность для каждой строки). По условию, повторно использовать случайность в паре с ключом ${\displaystyle p_{kj}}$ безопасно, поэтому матрица ${\displaystyle M}$ является вычислительно скрытой. Кроме того, поскольку гомоморфизм изолирует случайность, все зашифрованные тексты в конечном векторе ${\displaystyle f(x)}$ также зашифровываются под такую же случайность ${\displaystyle R}$ (которая зависит только от ${\displaystyle (r_{1},r_{2}...r_{m})}$.

Когда ${\displaystyle M=I}$, мы все ещё можем инвертировать функцию (с помощью лазейки), расшифровывая каждую зашифрованную запись ${\displaystyle f(x)}$. С другой стороны, когда матрица нулевая ${\displaystyle M=0}$, выход функции всегда является вектором зашифрованных нулевых сообщений, где каждая запись зашифровывается по одной и той же случайности (но под разными фиксированными ключами). Поэтому число возможных выходов ${\displaystyle f}$ ограничено числом возможных случайных строк, которые могут возникнуть. Выбирая размерность ${\displaystyle n}$ так, что количество входов ${\displaystyle 2^{n}}$ является значительно больше, чем число случайных строк, мы можем гарантировать, что функция содержит потею информации.

Построение функций «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)^[англ.] и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.

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

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

• Xavier Boyen, Xiaofeng Chen. General Construction of Chameleon All-But-One Trapdoor Functions // Provable Security: 5th International Conference (англ.). — Springer, 2011. — P. 257—261. — ISBN 9783642243158.
• Giuseppe Longo. Section 4.2: Cryptographic functions // Secure digital communications (неопр.). — 1983. — С. 29—30. — ISBN 0-387-81784-0.
• Chris Peikert, Brent Waters. Lossy Trapdoor Functions and Their Applications (англ.). — 2008. — ISBN 978-1-60558-047-0.
• Julien Cathalo, Christophe Petit. One-time trapdoor one-way functions (англ.). — Springer, 2011. — ISBN 9783642181771.
• Ronald C. Mullin, Gary L. Mullen. Finite fields : theory, applications, and algorithms : Fourth International Conference on Finite Fields: Theory, Applications, and Algorithms (англ.). — Providence, R.I. : American Mathematical Society, 1998. — ISBN 0821808176.
• Neal Koblitz. Algebraic aspects of cryptography. — Springer. — 1998. — ISBN 3540634460.
• Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638