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

Псевдослучайная функция Наора — Рейнгольда — псевдослучайная функция, введённая в 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$ умножений по модулю $l$ и одно возведение в степень по модулю $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}}}$, злоумышленнику необходимо решить задачу Диффи — Хеллмана для $f_{a}(1)=g^{a_{0}a_{1}}$ и $f_{a}(k)=g^{a_{0}a_{2}^{x_{2}}...a_{n}^{x_{n}}}$. Но по предположению о сложности Диффи — Хеллмана не существует эффективного алгоритма, способного решить данную задачу.

Поток чисел, генерируемый псевдослучайной функцией, также должен быть непредсказуемым, то есть, он должен быть неотличим от совершенно случайного набора чисел. Пусть ${\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\in \mathbb {F} _{p}^{2}$ в циклической группе $\langle G\rangle$, где $x=x_{1}\dots x_{n}$ — битовое представление $x,\;0\leq x<2^{n}$, $G\in \mathbb {F} _{p}^{2}$, — некоторый элемент на $E$ с мультипликативным порядком $l$, а $(a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G$ — это операция возведения элемента $G$ в степень $a_{0}a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}$ относительно групповой операции в абелевой группе $\mathbb {F} _{p}$-рациональных точек эллиптической кривой. В таких обозначениях последовательность Наора — Рейнгольда на эллиптической кривой определяется как $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}$.

См. также

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