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

one-way collection of functions

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

Связанные статьи: семейство функций сильно одностороннее (справочник)

Пусть $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$, по которому определяется трудность инвертирования этой функции в среднем.

Определение 1 одностороннее семейство функций; см. также [1]

Вышеуказанное семейство $(f_i\,|\, i\in I)$ называется односторонним относительно семейств распределений вероятностей $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in 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)$.

Пример 2

Пусть $(G_m\,|\, m\in M)$, где $M\subseteq\{0,1\}^*$, — полиномиально вычислимое семейство конечных групп. Пусть также $(\mathfrak M_n\,|\, n\in\mathbb N)$ и $(\mathfrak G_m\,|\, m\in M)$ — полиномиально конструируемые семейства распределений вероятностей такие, что $\mathop{\mathrm{supp}}\mathfrak M_n\subseteq M$ для всех $n\in\mathbb N$ и $\mathop{\mathrm{supp}}\mathfrak G_m\subseteq G_m$ для всех $m\in M$. В качестве $I$ выберем множество всех пар $(m,g)$, где $m\in M$ и $g\in G_m$, а в качестве $\mathfrak I_n$ — распределение вероятностей на множестве всех таких пар $(m,g)$, где $m\leftarrow\mathfrak M_n$ и $g\leftarrow\mathfrak G_m$ ($n\in\mathbb N$). Кроме того, предположим, что определены полиномиально вычислимые функции $\alpha,\beta\colon I\to\mathbb Z$ такие, что $\alpha(i)\leqslant\beta(i)$ для всех $i\in I$. Пусть $(m,g)\in I$. Положим $X_{m,g}=\{\alpha(m,g),\dots,\beta(m,g)\}$. Определим функцию $f_{m,g}\colon X_{m,g}\to G_m$ равенством $f_{m,g}(x)=g^x$ ($x\in X_{m,g}$), а в качестве $\mathfrak X_{m,g}$ возьмем равномерное распределение на $X_{m,g}$. Задача вычисления по $(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)$ и функций $\alpha,\beta$). Другими словам, эта задача заключается в нахождении по $(1^n,m,g,g^x)$, где $n\in\mathbb N$, $m\in\mathop{\mathrm{supp}}\mathfrak M_n$, $g\in\mathop{\mathrm{supp}}\mathfrak G_m$ и $x\in\{\alpha(m,g),\dots,\beta(m,g)\}$, некоторого числа $y\in\{\alpha(m,g),\dots,\beta(m,g)\}$ такого, что $g^y=g^x$.

Пример 3

Пусть $(G_m\,|\, m\in M)$, $(\mathfrak M_n\,|\, n\in\mathbb N)$ и $(\mathfrak G_m\,|\, m\in M)$ — те же, что в примере 2, а $k$ — функция из $M$ в $\mathbb N$ такая, что функция $m\mapsto1^{k(m)}$ ($m\in M$) полиномиально вычислима. В качестве $I$ выберем множество всех наборов $\left(m,g_1,\dots,g_{k(m)}\right)$, где $m\in M$ и $g_1,\dots,g_{k(m)}\in G_m$, а в качестве $\mathfrak I_n$ — распределение вероятностей на множестве всех таких наборов $\left(m,g_1,\dots,g_{k(m)}\right)$, где $m\leftarrow\mathfrak M_n$ и $g_1,\dots,g_{k(m)}\leftarrow\mathfrak G_m$ ($n\in\mathbb N$).

Пусть $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$ являются аддитивно записываемыми абелевыми группами. В этом случае задачу о произведении подмножества естественно называть задачей о сумме подмножества.

Пример 4

Пусть $(\mathfrak P_n\,|\, n\in\mathbb N)$ — полиномиально конструируемое семейство распределений вероятностей на множестве двухэлементных подмножеств простых чисел. В качестве $I$ выберем множество $\{1^n\,|\, n\in\mathbb N\}$, а в качестве $\mathfrak I_n$ — распределение, сосредоточенное на $1^n$ ($n\in\mathbb N$). Пусть $1^n\in I$. Положим $X_{1^n}=\mathop{\mathrm{supp}}\mathfrak P_n$. Определим функцию $f_{1^n}\colon X_{1^n}\to\mathbb N$ равенством $f_{1^n}(\{p,q\})=pq$ ($\{p,q\}\in X_{1^n}$), а в качестве $\mathfrak X_{1^n}$ возьмем распределение $\mathfrak P_n$ на $X_{1^n}$. Задача вычисления по $(i,f_i(x))$, где $i=1^n\in\mathop{\mathrm{supp}}\mathfrak I_n$ ($n\in\mathbb N$) и $x\in X_i$, некоторого элемента множества $f^{-1}(f_i(x))$ называется задачей факторизации целых чисел (для данного семейства $(\mathfrak P_n\,|\, n\in\mathbb N)$; здесь из входных данных исключена строка $1^n$, так как она совпадает с $i$). Другими словами, эта задача заключается в нахождении по $(1^n,pq)$, где $n\in\mathbb N$ и $\{p,q\}\in\mathop{\mathrm{supp}}\mathfrak P_n$, множества $\{p,q\}$ (или, что эквивалентно, одного из его элементов).

Литература

[1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Математическая криптография

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

Литература