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

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

$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 ^{п -1} , с некоторыми дополнительными ведущими нулями, если необходимо.

Пример

Пусть p = 7 и l = 3; так что я | р -1. Выберите g = 4 ∈ ${\mathbb {F} _{7}}^{*}$ мультипликативного порядка 3 (поскольку 4 ³ = 64 ≡ 1 по модулю 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}$

Эффективность

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

Пример: Злоумышленник видит несколько результатов функции, например $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}$ обозначим алгоритм ${\mathcal {A}}$ с доступом к оракулу для оценки функции $f_{a}(x)$ . Предположим, что решающее предположение Диффи–Хеллмана справедливо для $\mathbb {F} _{p}$, Наор и Рейнгольд показывают, что для каждого вероятностного алгоритма с полиномиальным временем ${\mathcal {A}}$ и достаточно большое n

${\text{Pr }}[{\mathcal {A}}^{f_{a}(x)}(p,g)\to 1]-{\text{Pr }}[{\mathcal {A}}^{R}(p,g)\to 1]$ является ничтожно малым .

Первая вероятность берется за выбор начального числа 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 , линейная сложность последовательности $f_{a}(x)$,0 ≤ х ≤ 2 ^n-1 , обозначенный $L_{a}$ удовлетворяет

$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\cdots$

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

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

эллиптической кривой Представляет интерес также вариант этой функции в виде . В частности, это может помочь улучшить криптографическую безопасность соответствующей системы. Пусть 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))\;{\mbox{where }}X(P){\mbox{ is the abscissa of}}\;P\in E.$

Если решающее предположение Диффи-Хеллмана верно, индекса k недостаточно для вычисления $u_{k}$ за полиномиальное время, даже если злоумышленник выполняет полиномиальное количество запросов к случайному оракулу. https://en.wikipedia.org/wiki/Elliptic_curve

См. также

• Решающее предположение Диффи-Хеллмана
• Конечное поле
• Инверсивный конгруэнтный генератор
• Обобщенные инверсивные конгруэнтные псевдослучайные числа

Ссылки

• Наор, Мони; Рейнгольд, Омер (2004), «Теоретико-числовые конструкции эффективных псевдослучайных функций», Журнал Ассоциации вычислительной техники , 51 (2): 231–262, doi : 10.1145/972639.972643 , S2CID   8665271 .
• Шпарлинский, Игорь (2003), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность (первое издание), Birkhäuser Basel, ISBN  978-3-7643-6654-4
• Гольдрейх, Одед (1998), Современная криптография, вероятностные доказательства и псевдослучайность (первое издание), Springer, ISBN  978-3-540-64766-9