Псевдослучайная функция Наора — Рейнгольда

Псевдослучайная функция Наора — Рейнгольда — псевдослучайная функция, введённая в 1997 году Мони Наором и Омером Рейнгольдом для построения различных криптографических примитивов в симметричном шифровании и криптографии с открытым ключом. Отличительными особенностями данной псевдослучайной функции являются низкая [[вычислительная сложность|вычислительная сложность]] и высокая криптографичекая стойкость. Данные свойства вместе с тем фактом, что распределение значений данной функции близко к равномерному, позволяют использовать ее в качестве основы для многих криптографических схем.

Постановка

В криптографии под семейством псевдослучайных функций понимают набор функций (которые могут быть эффективно вычислены за полиномиальное время), обладающих следующим свойством: злоумышленник не может эффективно найти какое-либо существенное различие между поведением функции из данного семейства и истинной случайной функции. Пусть $p$ — это $n$-битное простое число, $l$ — простое число, являющееся делителем $p-1$, а $g\in {\mathbb {F} }_{p}^{*}$, — некоторый элемент с мультипликативным порядком $l$ по модулю $p$. Тогда функция Наора — Рейнгольда $f_{a}(x)$ определяется некоторым $(n+1)$-мерным вектором $a=(a_{0},a_{1},...,a_{n})\in ({\mathbb {F} }_{l})^{n+1}$ над полем $\mathbb {F} _{l}$ и равна:

$f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}$

где $x=x_{1},...,x_{n}$ — это двоичное представление целого числа $x,$ $0\leq x<2^{n}$, с добавлением ведущих нулей, если это необходимо.

Пример

Пусть $p=7$ и $l=3$. В качестве $g\in \mathbb {F} _{7}^{*}$ с мультипликативным порядком $3$ можно выбрать $g=4$. Тогда при $n=3$, $a=(1,1,3,1)$ и $x=5$ функция $f_{a}(5)$ вычисляется как

$f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}=4^{1\cdot 1^{1}3^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}$

Так как двоичное представление числа $5$ — это $(1,0,1)$.

Вычислительная сложность

Построение псевдослучайной функции Наора — Рейнгольда требует $n$ умножений по модулю $p$ и одно возведение в степень также по модулю $p$, которое может быть сделано за $O\left({\frac {n}{\log n}}\right)$.

Для схемной сложности данной функции было показано, что существует такой полином $p(x)$, что для любого $a=(a_{0},a_{1},...,a_{n})\in ({\mathbb {F} }_{l})^{n+1}$, $f_{a}(x)$ может быть реализована схемой из пороговых элементов глубины $d$ и размера, не превышающего $p(n)$. Это означает, что функции Наора — Рейнгольда принадлежит классу TC⁰ в терминах булевых схем.

Применение псевдослучайной функции

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

Также было показано, что данная функция может быть использована в:

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

Безопасность псевдослучайной функции

Псевдослучайная функция Наора — Рейнгольда имеет высокую криптографичекую стойкость. Пусть злоумышленнику известны значения функции в нескольких точках: $f_{a}(1)=g^{a_{0}a_{1}},f_{a}(2)=g^{a_{0}a_{2}},\dots ,f_{a}(k)=g^{a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}$и ему необходимо вычислить $f_{a}(k+1)$. Если $x_{1}=0$, то чтобы получить $f_{a}(k+1)=g^{a_{0}a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}$, злоумышленнику необходимо решить Шаблон:Iw5 для $f_{a}(1)=g^{a_{0}a_{1}}$ и $f_{a}(k)=g^{a_{0}a_{2}^{x_{2}}...a_{n}^{x_{n}}}$. Но по Шаблон:Iw5 не существует эффективного алгоритма, способного решить данную задачу.

Поток чисел генерируемый псевдослучайной функцией также должен быть непредсказуемым, то есть, он должен быть неотличим от совершенно случайного набора чисел. Пусть ${\mathcal {A}}^{f}$ обозначает алгоритм, который имеет доступ к оракулу, который вычисляет $f_{a}(x)$. Предположим, что предположение Диффи — Хеллмана выполняется для $\mathbb {F} _{p}$. Тогда для любого вероятностного полиномиального алгоритма ${\mathcal {A}}$ и достаточно большого $n$ выполнено:

$|{\text{Pr }}[{\mathcal {A}}^{f_{a}(x)}(p,g)=1]-{\text{Pr }}[{\mathcal {A}}^{R}(p,g)=1]|<\epsilon$, где $\epsilon (n)$ — пренебрежимо мало.

Первая вероятность равна доле наборов $s=(p,g,a)$, на которых алгоритм выдаёт единицу, а вторая получается из случайного выбора пары $(p,g)$ и функции $R_{a}(x)$ среди множества всех функций $\{0,1\}^{n}\to {\mathbb {F} }_{p}$.

Линейная сложность

Одним из естественных показателей того, насколько последовательность может быть полезной для криптографических целей, является её линейная сложность. Линейная сложность $n$-элементной последовательности $W(x),\;x=0,\dots ,n-1$, над кольцом ${\mathcal {R}}$ — это длина $l$ кратчайшего линейного рекуррентного соотношения $W(x+l)=A_{l-1}W(x+l-1)+\dots +A_{0}W(x),\;x=0,\dots ,n-(l-1)$, где $A_{0},\dots ,A_{l-1}\in {\mathcal {R}}$. Для функции Наора — Рейнгольда было показано, что существуют такие $\gamma >0$ и $n\geqslant (1+\gamma )\log l$, что для любого $\delta >0$ и достаточно большого $l$ линейная сложность $L_{a}$ последовательности $f_{a}(x)$, $0\leq x<2^{n}$, удовлетворяет следующему неравенству:

$L_{a}\geqslant {\begin{cases}l^{1-\ \delta \,\!}&{\text{, если }}\gamma \,\!\geqslant 2\\l^{\left({\tfrac {\ \gamma \,\!}{2-\ \delta \,\!}}\right)}&{\text{, если }}\gamma \,\!<2\end{cases}}$

для всех, кроме не более чем $3(l-1)^{n-\delta }$ векторов $a\in (\mathbb {F} _{l})^{n+1}$.

Равномерность распределения

Статистическое распределение $f_{a}(x)$ экспоненциально близко к равномерному распределению почти для всех векторов $a\in ({\mathbb {F} }_{l})^{n+1}$:

пусть ${\mathbf {D} }_{a}$ — расхождение множества $\{f_{a}(x)|0\leq x<2^{n}\}$ или, другими словами, отклонение распределения значений псевдослучайной функции от равномерного распределения. Было показано, что если $n=\log p$ — это битовая длина $p$, тогда для всех векторов $a$ ∈ $(\mathbb {F} _{l})^{n+1}$ справедливо неравенство ${\mathbf {D} }_{a}\leq \Delta (l,p)$, где:

$\Delta (l,p)={\begin{cases}p^{\left({\tfrac {1-\ \gamma \,\!}{2}}\right)}l^{\left({\tfrac {-1}{2}}\right)}\log ^{2}p&{\text{ если }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ если }}p^{\gamma \,\!}>l\geqslant p^{\left({\tfrac {2}{3}}\right)}\\p^{\left({\tfrac {1}{4}}\right)}l^{\left({\tfrac {-5}{8}}\right)}\log ^{2}p&{\text{ если }}p^{\left({\tfrac {2}{3}}\right)}>l\geqslant p^{\left({\tfrac {1}{2}}\right)}\\p^{\left({\tfrac {1}{8}}\right)}l^{\left({\tfrac {-3}{8}}\right)}\log ^{2}p&{\text{ если }}p^{\left({\tfrac {1}{2}}\right)}>l\geqslant p^{\left({\tfrac {1}{3}}\right)}\\\end{cases}}$

и $\gamma =2,5-\log 3\approx 0,9150\dots$.

Это свойство не имеет непосредственного криптографического значения, но если бы оно не было выполнено, это могло бы повлечь катастрофические последствия для применения функции.

Последовательности на эллиптической кривой

Анализ эллиптической кривой этой функции позволяет улучшить криптографическую стойкость соответствующей системы. Пусть $p>3$ — простое число и $E$ — эллиптическая кривая над $\mathbb {F} _{p}$. Тогда любой вектор $a=(a_{0},a_{1},\dots ,a_{n})\in ({\mathbb {F} }_{l}^{*})^{n+1}$ определяет конечную последовательность $f_{a}(x)=(a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G$ в подгруппе $\langle G\rangle$, где $x=x_{1}\dots x_{n}$ — битовое представление $x,\;0\leq x<2^{n}$, а $G\in {\mathbb {F} }_{p}$, — некоторый элемент на $E$ с мультипликативным порядком $l$. В таких обозначениях последовательность эллиптической кривой Наора — Рейнгольда определяется как $u_{k}=X(f_{a}(k))\;$, где $X(P)$ — это абсцисса $P\in E$.

Если предположение Диффи — Хеллмана выполнено, то индекса $k$ не достаточно для вычисления $u_{k}$ за полиномиальное время. Для эллиптической кривой Наора — Рейнгольда было показано, что существуют такие $\gamma >0$ и $n\geqslant (1+\gamma )\log l$, что для любого $\delta >0$ и достаточно большого $l$ линейная сложность $L_{a}$ последовательности $(u_{k})_{k=0}^{2^{n}-1}$ удовлетворяет следующему неравенству:

$L_{a}\geqslant \min \left(l^{{\frac {1}{3}}-\delta },{\frac {l^{(\gamma -3\delta )}}{\log ^{2}l}}\right)$

для всех, кроме не более чем $O((l-1)^{n-\delta })$ векторов $a\in (\mathbb {F} _{l}^{*})^{n+1}$.

См. также

• Симметричные криптосистемы
• Конечное поле
• Инверсный конгруэнтный метод
• Криптосистема с открытым ключом

Литература

• Naor, Moni; Reingold, Omer (2004), "Number-theoretic constructions of efficient pseudo-random functions", Journal of the Association for Computing Machinery, 51: 231—262
• Shparlinski, Igor (2003), Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness (first ed.), Birkhäuser Basel, ISBN 978-3-7643-6654-4
• Goldreich, Oded (1998), Modern Cryptography, Probabilistic Proofs and Pseudorandomness (first ed.), Springer, ISBN 978-3-540-64766-9