Семейство функций одностороннее
Пусть $I$ — подмножество $\{0,1\}^*$. Пусть также $(f_i\,|\, i\in I)$ — семейство функций, в котором для каждого индекса $i\in I$ функция $f_i$ определена на некотором непустом конечном множестве $X_i\subseteq\{0,1\}^*$ и принимает значения в $\{0,1\}^*$. Предположим, что для каждого $n\in\mathbb N$ задано распределение вероятностей $\mathfrak I_n$ на множестве $I$, а для каждого $i\in I$ — распределение вероятностей $\mathfrak X_i$ на множестве $X_i$, причем семейства распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$ полиномиально конструируемы. Смысл этих распределений состоит в том, что $\mathfrak I_n$ — распределение на множестве индексов, соответствующих параметру стойкости $n$, а $\mathfrak X_i$ — распределение на области определения функции $f_i$, по которому определяется трудность инвертирования этой функции в среднем.
- это семейство функций полиномиально вычислимо;
- для любого полиномиального вероятностного алгоритма $\mathcal A$ величина $\Pr\left(\mathcal A(1^n,i,f_i(x))\in f_i^{-1}(f_i(x))\right)$, где $i\leftarrow\mathfrak I_n$ и $x\leftarrow\mathfrak X_i$, пренебрежимо мала как функция от $n\in\mathbb N$.
Пусть $(f_i\,|\, i\in I)$ — одностороннее семейство функций относительно семейств распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$. Выберем полиномиальные детерминированные алгоритмы $\mathcal I$ и $\mathcal X$ такие, что случайная величина $\mathcal I(1^n)$ имеет распределение $\mathfrak I_n$ для любого $n\in\mathbb N$, а случайная величина $\mathcal X(i)$ — распределение $\mathfrak X_i$ для любого $i\in I$. Пусть также $k$ и $m$ — возрастающие полиномиальные параметры такие, что алгоритм $\mathcal I$ при вычислении на входе $1^n$ (где $n\in\mathbb N$) использует не более $k(n)$ случайных битов, а алгоритм $\mathcal X$ при вычислении на входе $i\in I$ — не более $m(\lvert{i}\rvert)$ случайных битов. Тогда легко видеть, что функция \[ (r,s)\mapsto\left(1^{\lvert{r}\rvert+\lvert{s}\rvert},i,f_i(\mathcal X(i;s))\right),\text{ где }i=\mathcal I(1^n;r), \] заданная так для всех $r\in\{0,1\}^{k(n)}$ и $s\in\{0,1\}^{m(n)}$ ($n\in\mathbb N$), является односторонней. Обратно, пусть $f\colon\{0,1\}^*\to\{0,1\}^*$ — односторонняя функция. Положим $I=\{1^n\,|\, n\in\mathbb N\}$, $X_i=\{0,1\}^{\lvert{i}\rvert}$, $f_i=f|_{X_i}$ ($i\in I$) и выберем в качестве $\mathfrak I_n$ распределение вероятностей, сосредоточенное на строке $1^n$ ($n\in\mathbb N$), а в качестве $\mathfrak X_i$ — равномерное распределение вероятностей на множестве $X_i$ ($i\in I$). Тогда семейство $(f_i\,|\, i\in I)$ является односторонним относительно (полиномиально конструируемых) семейств распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$.
Таким образом, всякое одностороннее семейство функций можно представить в виде односторонней функции, и наоборот. Поэтому понятие одностороннего семейства функций является всего лишь другой формой понятия односторонней функции, более удобной для представления некоторых функций, используемых в математической криптографии. См. также [1]
Приведем теперь несколько примеров семейств функций $(f_i\,|\, i\in I)$, которые гипотетически являются односторонними (при подходящем выборе параметров) и широко используются в математической криптографии. При этом мы будем также указывать соответствующие семейства распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$.
Пусть $i=\left(m,g_1,\dots,g_{k(m)}\right)\in I$. Положим $X_i=\{0,1\}^{k(m)}$. Определим функцию $f_i\colon X_i\to G_m$ равенством $f_i(x)=g_1^{x_{[1]}}\dots g_{k(m)}^{x_{[k(m)]}}$ ($x\in X_i$), а в качестве $\mathfrak X_i$ возьмем равномерное распределение на $X_i$. Очевидно, что если $S_x=\left\{j\in\{1,\dots,k(m)\}\,\left|\, x_{[j]}=1\right.\right\}$, то $f_i(x)=\prod_{j\in S_x}g_j$ для произвольного $x\in X_i$, где произведение $g_j$ берется в порядке возрастания индексов. По этой причине задача вычисления по $(1^n,i,f_i(x))$, где $n\in\mathbb N$, $i\in\mathop{\mathrm{supp}}\mathfrak I_n$ и $x\in X_i$, некоторого элемента множества $f^{-1}(f_i(x))$ называется задачей о произведении подмножества (для данных семейств $(G_m\,|\, m\in M)$, $(\mathfrak M_n\,|\, n\in\mathbb N)$, $(\mathfrak G_m\,|\, m\in M)$ и функции $k$). Другими словам, эта задача заключается в нахождении по $\left(1^n,m,g_1,\dots,g_{k(m)},h\right)$, где $n\in\mathbb N$, $m\in\mathop{\mathrm{supp}}\mathfrak M_n$, $g_1,\dots,g_{k(m)}\in\mathop{\mathrm{supp}}\mathfrak G_m$ и $h=g_1^{x_{[1]}}\dots g_{k(m)}^{x_{[k(m)]}}$ ($x\in\{0,1\}^{k(m)}$), некоторой строки $y\in\{0,1\}^{k(m)}$ такой, что $g_1^{y_{[1]}}\dots g_{k(m)}^{y_{[k(m)]}}=h$.
Чаще всего задача о произведении подмножества рассматривается в случае, когда все $G_m$ являются аддитивно записываемыми абелевыми группами. В этом случае задачу о произведении подмножества естественно называть задачей о сумме подмножества.Литература
- [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)