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

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

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

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

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

${\displaystyle 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}}$

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

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

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

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

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

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