Список обозначений

Семейство функций с секретом

collection of trapdoor functions
Синонимы: семейство функций с секретом одностороннее, семейство функций с секретом сильно одностороннее

Пусть $I$ — подмножество $\{0,1\}^*$. Пусть также $(f_i\,|\, i\in I)$ — семейство функций, в котором для каждого индекса $i\in I$ функция $f_i$ определена на некотором непустом конечном множестве $X_i\subseteq\{0,1\}^*$ и принимает значения в $\{0,1\}^*$. Говоря неформально, это семейство называется семейством функций с секретом, если оно полиномиально вычислимо, причем можно эффективно генерировать пары $(i,s)$ (где $i\in I$, а $s$ — некоторая информация, которая называется секретом для $f_i$) таким образом, что задача инвертирования функции $f_i$ без знания $s$ трудна, а со знанием $s$ легка. Чтобы формализовать последнее условие, предположим, что для каждого $n\in\mathbb N$ задано распределение вероятностей $\mathfrak G_n$ на множестве $I\times\{0,1\}^*$, а для каждого $i\in I$ — распределение вероятностей $\mathfrak X_i$ на множестве $X_i$, причем семейства распределений вероятностей $(\mathfrak G_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$ полиномиально конструируемы. Смысл этих распределений состоит в том, что $\mathfrak G_n$ — распределение на множестве вышеуказанных пар $(i,s)$, соответствующих параметру стойкости $n$, а $\mathfrak X_i$ — распределение на области определения функции $f_i$, по которому определяется трудность инвертирования этой функции в среднем. Обозначим через $\mathfrak I_n$, где $n\in\mathbb N$, распределение на индексах $i$, если $(i,\cdot)\leftarrow\mathfrak G_n$.

Определение 1 семейство функций с секретом
Вышеуказанное семейство $(f_i\,|\, i\in I)$ называется семейством функций с секретом относительно семейств распределений вероятностей $(\mathfrak G_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$, если
  1. это семейство является односторонним относительно семейств распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$;
  2. существует полиномиальный детерминированный алгоритм $\mathcal M$ такой, что $\mathcal M(1^n,i,s,y)\in f_i^{-1}(y)$ для любых $n\in\mathbb N$, $(i,s)\in\mathop{\mathrm{supp}}\mathfrak G_n$ и $y\in f_i(X_i)$.

Пусть $(f_i\,|\, i\in I)$ — семейство функций с секретом относительно семейств распределений вероятностей $(\mathfrak G_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$. Выберем полиномиальный вероятностный алгоритм $\mathcal G$ такой, что $\mathcal G(1^n)$ имеет распределение $\mathfrak G_n$ для любого $n\in\mathbb N$. Такой алгоритм $\mathcal G$ иногда называется генератором функций с секретом, соответствующим данному семейству функций. Пусть также $k$ — полиномиальный параметр, значение которого на $n$ ограничивает сверху число случайных битов, используемое алгоритмом $\mathcal G$ при вычислении на входе $1^n$ ($n\in\mathbb N$). Тогда во многих случаях вместо алгоритма $\mathcal G$ можно рассматривать алгоритм $\mathcal G’$, который на входе $1^n$ ($n\in\mathbb N$) выбирает $r\in_{\mathfrak U}\{0,1\}^{k(n)}$, вычисляет $(i,s)=G(1^n;r)$ и возвращает $(i,r)$. Таким образом, здесь секрет $r$ выбирается случайно и равновероятно из множества $\{0,1\}^{k(n)}$, а соответствующий индекс $i$ вычисляется по $(1^n,r)$ детерминированным образом за полиномиальное время.

Важность семейств функций с секретом подчеркивается тем, что этот криптографический примитив был неформально определен еще в пионерской работе [1] в связи с системами шифрования с открытым ключом. Действительно, очевидна аналогия между семействами функций с секретом и системами шифрования с открытым ключом: если $(i,s)\leftarrow\mathcal G(1^n)$, то $s$ соответствует секретному ключу, $i$ — открытому ключу, а $f_i(x)$ — шифртексту для сообщения $x\in X_i$.

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

Теорема 2
Имеется оракул, относительно которого существуют односторонние перестановки, но не существует семейств функций с секретом.

Литература

  • [1] Diffie, W. and Hellman, M. E. «New directions in cryptography» 1976
  • [2] Impagliazzo, R. and Rudich, S. «Limits on the provable consequences of one-way permutations» 1989

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна