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

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

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

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

Определение

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

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

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

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

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

История

Развитие односторонних функций с потайным входом

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

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

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

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

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

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

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

Развитие односторонних функций с потайным входом, допускающих потери

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

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

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

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

Односторонние функции с потайным входом «All-but-one»

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

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

Односторонние функции с потайным входом «All-but-N»

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

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

Односторонние функции с потайным входом «All-but-many»

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

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

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

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

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

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

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

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

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

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

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

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

Построение функций с потайным ходом «All-but-one»

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

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

RSA

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

Функция Рабина

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

Схема Эль-Гамаля

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

Алгоритм

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

Криптосистема Polly Cracker

Алгоритм

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