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

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

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

куда Икс = Икс₁ … Икс_п это битовое представление целого числа Икс, 0 ≤ Икс ≤ 2^п−1, с некоторыми дополнительными ведущими нулями, если необходимо.^[1]

Пример

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

${\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 f_{a}(5)=4^{1\cdot 1^{1}2^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}}$

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

Оценка функции ${\displaystyle f_{a}(x)}$ в Наор – Рейнгольд строительство можно сделать очень качественно. Вычисление значения функции ${\displaystyle f_{a}(x)}$ в любой момент сравним с одним модульное возведение в степень и n-модульные умножения. Эта функция может быть вычислена параллельно пороговыми схемами ограниченной глубины и полиномиального размера.

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

Безопасность функции

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

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

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

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

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

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

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

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

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

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

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

Позволять ${\displaystyle {\mathbf {D} }_{a}}$ быть несоответствие из набора ${\displaystyle \{f_{a}(x)|0\leq x\leq 2^{n-1}\}}$. Таким образом, если ${\displaystyle n=\log p}$ это длина в битах п то для всех векторов a ∈ ${\displaystyle (\mathbb {F} _{l})^{n}}$ граница ${\displaystyle {\mathbf {D} }_{a}\leq \Delta (l,p)}$ держит, где

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

и

${\displaystyle \gamma =2.5-\log 3=0.9150\cdots }$

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

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

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

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

куда ${\displaystyle x=x_{1}\dots x_{n}}$ битовое представление целого числа ${\displaystyle x,0\leq x\leq 2^{n-1}}$. В Наор – Рейнгольд последовательность эллиптических кривых определяется как

${\displaystyle u_{k}=X(f_{a}(k))\;{\mbox{where }}X(P){\mbox{ is the abscissa of}}\;P\in E.}$^[5]

Если решающее предположение Диффи – Хеллмана верно, индекс k недостаточно для вычисления ${\displaystyle u_{k}}$ за полиномиальное время, даже если злоумышленник выполняет полиномиально много запросов к случайному оракулу.

Смотрите также

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

Примечания

1. Наор, М., Рейнгольд, О. "Теоретико-числовые конструкции эффективных псевдослучайных функций", Proc 38th IEEE Symp. на Основах Комп. Sci, (1997), 458–467.
2. Бонех, Дэн. «Решающая проблема Диффи – Хеллмана», ANTS-III: Труды Третьего Международного симпозиума по алгоритмической теории чисел, 1998, 48–63.
3. Шпарлинский Игорь Э. Линейная сложность псевдослучайной функции Наора – Рейнгольда, Информ. Process Lett, 76 (2000), 95–99.
4. Шпарлинский, Игорь Э. «О равномерности распределения псевдослучайной функции Наора – Рейнгольда», Конечные поля и их приложения, 7 (2001), 318–326
5. Круз, М., Гомес, Д., Садорнил, Д. «О линейной сложности последовательности Наора – Рейнгольда с эллиптическими кривыми», Конечные поля и их приложения, 16 (2010), 329–333

Рекомендации

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