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

В 1997 году Мони Наор и Омер Рейнгольд описали эффективные конструкции для различных криптографических примитивов как для симметричного шифрования, так и для криптографии с открытым ключом. Результатом их работы является построение эффективной псевдослучайной функции. Пусть p и l простые числа, и l является делителем p−1. Возьмем элемент g ∈ ${\mathbb {F} _{p}}^{*}$, который является показателем числа l по модулю p. Тогда для каждого n+1 - мерного вектора a = (a₀,a₁, ..., a_n)∈ $(\mathbb {F} _{l})^{n}$ определена функция:

$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₁ … x_n - это двоичное представление целого числа x, 0 ≤ x ≤ 2ⁿ⁻¹, с добавлением ведущих нулей, если это необходимо. Данная функция называется псевдослучайной функцией Наора – Рейнгольда.

Пример

Пусть p = 7 и l = 3. Видно, что l является делителем p−1. g ∈ ${\mathbb {F} _{7}}^{*}$, показатель l по модулю p, равен 4 (т.к 4³ = 64 ≡ 1 mod 7). Возьмем n = 3, a = (1, 1, 2, 1) и x = 5 (двоичное представление 5 - 101), тогда $f_{a}(5)$ вычисляется следующим образом:

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

$f_{a}(5)=4^{1\cdot 1^{1}2^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}$

Сложность вычисления псевдослучайной функции

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

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

Предположим, что злоумышленник видит несколько выходов функции, например, $f_{a}(1)=g^{a_{1}},f_{a}(2)=g^{a_{2}},f_{a}(3)=g^{a_{1}a_{2}}$... $f_{a}(k)=g^{a_{1}^{x_{1}}a_{2}^{x_{2}}...a_{n}^{x_{n}}}$ и хочет вычислить $f_{a}(k+1)$. Предположим для простоты, что x₁ = 0, тогда, чтобы получить $f_{a}(k+1)=g^{a_{1}a_{2}^{x_{2}}\dots a_{n}^{x_{n}}}$, злоумышленник столкнется с так называемым вычислительным предположением Диффи – Хеллмана для $f_{a}(1)=g^{a_{1}}$ и $f_{a}(k)=g^{a_{2}^{x_{2}}...a_{n}^{x_{n}}}$, которое включает в себя проблему дискретного логарифмирования в циклических группах.

Как правило, переход от k к k + 1 изменяет битовую комбинацию $x_{1}x_{2}...x_{n}$, и если k + 1 не является степенью 2, можно разделить показатель степени на $f_{a}(k+1)$, для того, чтобы вычисление соответствовало бы вычислению ключа Диффи-Хеллмана между двумя сторонами. Таким образом, с проблемой взлома можно бороться работая в группах с более высокой криптографической стойкостью, которая в свою очередь определяется вычислительной сложностью задачи дискретного логарифмирования.

Пример: Предположим злоумышленник видит несколько выходов функции, например, $f_{a}(5)=4^{1^{1}2^{0}1^{1}}=4^{1}=4$, как в предыдущем примере, и $f_{a}(1)=4^{1^{0}2^{0}1^{1}}=4^{1}=4$ и хочет предсказать следующий элемент последовательности этой функции, $f_{a}(6)$. Однако для того, чтобы предсказать исход $f_{a}(6)$, зная $f_{a}(1)$ и $f_{a}(5)$, нужно, как было сказанно выше, решить задачу дискретного логарифмирования.

Также важно отметить, что так как пользователь ожидает получить случайные числа, поток чисел генерируемый псевдослучайной функцией должен быть непредсказуемым, более того, он должен быть неотличим от совершенно случайного набора чисел. Пусть ${\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 из ${\mathcal {I}}{\mathcal {G}}(n)$, и случайному выбору функции $R_{a}(x)$ среди множества всех функций $\{0,1\}^{n}\to \mathbb {F} _{p}$ функций.. Фактически, это означает то, что поток чисел генерируемых псевдослучайной функцией с высокой долей вероятности будет неотличим от совершенно случайного набора чисел.

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

Одним естественным показателем того, насколько последовательность может быть полезной для криптографических целей, является размер ее линейной сложности. Линейная сложность n - элементной последовательности W(x), x = 0,1,2,…, n – 1, над кольцом ${\mathcal {R}}$ – это длина l кратчайшего линейного рекуррентного соотношения W(x + l) = A_l−1 W(x +l−1) + … + A₀ W(x), x = 0,1,2,…, n – (l - 1), где A₀, …, A_l−1 ∈ ${\mathcal {R}}$.

В работе было показано, что существуют такие $\gamma$ > 0 и n ≥ (1+ $\gamma$) $\log l$, что для любого $\delta >0$ и достаточно большого l линейная сложность $L_{a}$ последовательности $f_{a}(x)$,0 ≤ x ≤ 2^n-1 удовлетворяет следующему неравенству:

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

для всех, кроме, возможно, максимум $3(l-1)^{n-\delta }$ векторов a ∈ $(\mathbb {F} _{l})^{n}$. Ограничения, использованные в данной теореме, не позволяют использовать ее для одного интересного случая, когда $\log p\approx \log n\approx {n.}$

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

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

Пусть ${\mathbf {D} }_{a}$ расхождение множества $\{f_{a}(x)|0\leq x\leq 2^{n-1}\}$ или, другими словами, отклонение распределения значений псевдослучайной функции от равномерного распределения. Таким образом, если $n=\log p$ – это битовая длина p, тогда для всех векторов a ∈ $(\mathbb {F} _{l})^{n}$ справедливо неравенство ${\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{ if }}l\geqslant p^{\gamma \,\!}\\p^{\left({\tfrac {1}{2}}\right)}l^{-1}\log ^{2}p&{\text{ if }}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{ if }}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{ if }}p^{\left({\tfrac {1}{2}}\right)}>l\geqslant p^{\left({\tfrac {1}{3}}\right)}\\\end{cases}}$

и

$\gamma =2.5-\log 3=0.9150...$

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

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

Эллиптическая кривая этой функции также представляет интерес, так как ее использование помогает улучшить криптографическую стойкость соответствующей системы. Пусть p > 3 простое и пускай E - эллиптическая кривая над $\mathbb {F} _{p}$, тогда каждый вектор a определяет конечную последовательность в подгруппе $\langle G\rangle$ как:

$f_{a}(x)=(a_{1}^{x_{1}}a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G$

где $x=x_{1}\dots x_{n}$ это битовое представление $x,0\leq x\leq 2^{n-1}$.

Тогда последовательность эллиптической кривой Наора – Рейнгольда определяется как:

$u_{k}=X(f_{a}(k))\;$, где $X(P)$ это абсцисса $P\in E.$

Если предположение Диффи – Хеллмана выполнено, то было показано, что индекса k не достаточно для вычисления $u_{k}$ за полиномиальное время.

См. также

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

Ссылки

• 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