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

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

Постановка

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

$f_a(x)=g^{a_0\cdot a_1^{x_1}{a}_2^{x_2}...a_n^{x_n}}\in {𝔽}_p$

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

Пример

Пусть $p=7$ и $l=3$. В качестве $g\in {𝔽}_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 {𝔽}_7$

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

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

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

Для Шаблон:Iw данной функции было показано, что существует такой полином $p(x)$, что для любого $a=(a_0,a_1,...,a_n)\in ({𝔽}_l{)}^{n+1}$, $f_a(x)$ может быть реализована схемой из пороговых элементов глубины $d$ и размера, не превышающего $p(n)$. Это означает, что функции Наора — Рейнгольда принадлежит Шаблон:Iw в терминах Шаблон:Iw.

Применение

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

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

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

Безопасность

Псевдослучайная функция Наора — Рейнгольда имеет высокую криптографическую стойкость. Пусть злоумышленнику известны значения функции в нескольких точках: $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}}$, злоумышленнику необходимо решить Шаблон:Iw для $f_a(1)=g^{a_0{a}_1}$ и $f_a(k)=g^{a_0{a}_2^{x_2}...a_n^{x_n}}$. Но по Шаблон:Iw не существует эффективного алгоритма, способного решить данную задачу.

Поток чисел, генерируемый псевдослучайной функцией, также должен быть непредсказуемым, то есть, он должен быть неотличим от совершенно случайного набора чисел. Пусть ${𝒜}^f$ обозначает алгоритм, имеющий доступ к оракулу, который вычисляет $f_a(x)$. Предположим, что Шаблон:Iw выполняется для ${𝔽}_p$. Тогда для любого вероятностного полиномиального алгоритма $𝒜$ и достаточно большого $n$ выполнено:

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

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

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

Одним из естественных показателей того, насколько последовательность может быть полезной для криптографических целей, является её линейная сложность. Линейная сложность $n$-элементной последовательности $W(x),x=0,\dots ,n-1$, над кольцом $ℛ$ — это длина $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 ℛ$. Для функции Наора — Рейнгольда было показано, что существуют такие $\gamma >0$ и $n⩾(1+\gamma )\log l$, что для любого $\delta >0$ и достаточно большого $l$ линейная сложность $L_a$ последовательности $f_a(x)$, $0\le x<2^n$, удовлетворяет следующему неравенству:

$L_a⩾\{\begin{array}{cc}{l}^{1-\delta }& \text{, если }\gamma ⩾2\\ l^{\left(\frac{\gamma }{2-\delta }\right)}& \text{, если }\gamma <2\end{array}$

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

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

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

пусть ${𝐃}_a$ — Шаблон:Iw множества $\{f_a(x)|0\le x<2^n\}$ или, другими словами, отклонение распределения значений псевдослучайной функции от равномерного распределения. Было показано, что если $n=\log p$ — это битовая длина $p$, тогда для всех векторов $a$ ∈ $({𝔽}_l{)}^{n+1}$ справедливо неравенство ${𝐃}_a\le \mathrm{\Delta }(l,p)$, где:

$\mathrm{\Delta }(l,p)=\{\begin{array}{cc}{p}^{\left(\frac{1-\gamma }{2}\right)}{l}^{\left(\frac{-1}{2}\right)}{\log }^{2}p& \text{ если }l⩾p^{\gamma }\\ p^{\left(\frac{1}{2}\right)}{l}^{-1}{\log }^{2}p& \text{ если }{p}^{\gamma }>l⩾p^{\left(\frac{2}{3}\right)}\\ p^{\left(\frac{1}{4}\right)}{l}^{\left(\frac{-5}{8}\right)}{\log }^{2}p& \text{ если }{p}^{\left(\frac{2}{3}\right)}>l⩾p^{\left(\frac{1}{2}\right)}\\ p^{\left(\frac{1}{8}\right)}{l}^{\left(\frac{-3}{8}\right)}{\log }^{2}p& \text{ если }{p}^{\left(\frac{1}{2}\right)}>l⩾p^{\left(\frac{1}{3}\right)}\end{array}$

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

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

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

Анализ этой функции на эллиптической кривой позволяет улучшить криптографическую стойкость соответствующей системы. Пусть $p>3$ — простое число и $E$ — эллиптическая кривая над ${𝔽}_p$. Тогда любой вектор $a=(a_0,a_1,\dots ,a_n)\in ({𝔽}_l^{*}{)}^{n+1}$ определяет конечную последовательность $f_a(x)=(a_0{a}_1^{x_1}{a}_2^{x_2}\dots a_n^{x_n})G\in {𝔽}_p^2$ в циклической группе $⟨G⟩$, где $x=x_1\dots x_n$ — битовое представление $x,0\le x<2^n$, $G\in {𝔽}_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}$ относительно групповой операции в абелевой группе ${𝔽}_p$-рациональных точек эллиптической кривой. В таких обозначениях последовательность Наора — Рейнгольда на эллиптической кривой определяется как $u_k=X(f_a(k))$, где $X(P)$ обозначает абсциссу точки $P\in E$.

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

$L_a⩾\min (l^{\frac{1}{3}-\delta },\frac{l^{(\gamma -3\delta )}}{{\log }^{2}l})$

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

См. также

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