Список обозначений

Семейство функций Рабина

rabin collection of functions

Пусть $(\mathfrak Q_n\,|\, n\in\mathbb N)$ — полиномиально конструируемое семейство распределений вероятностей на множестве пар вида $(\{p,q\},a)$, где $p$ и $q$ — различные простые числа, а $a\in\mathbb Z^{\star}_{pq}$ является квадратичным невычетом как по модулю $p$, так и по модулю $q$. Например, если $p\equiv q\equiv3\pmod4$, то в качестве $a$ можно взять $pq-1$. Положим $I=\left\{\left.\operatorname{num}^{-1}(pq)\,\right|\, (\{p,q\},a)\in\mathop{\mathrm{supp}}\mathfrak Q_n,\, n\in\mathbb N\right\}$. Для каждого $n\in\mathbb N$ распределение вероятностей $\mathfrak G_n$ определяется как распределение на множестве всех пар $(pq,(\{p,q\},a))$, где $(\{p,q\},a)\leftarrow\mathfrak Q_n$.

Пусть $i\in I$. Определим функцию $\mathop{\mathrm{Rabin}}_i\colon\mathbb Z^{\star}_{\operatorname{num}(i)}\to\mathbb Z^{\star}_{\operatorname{num}(i)}$ равенством $\mathop{\mathrm{Rabin}}_i(x)=x^2\bmod\operatorname{num}(i)$ ($x\in\mathbb Z^{\star}_{\operatorname{num}(i)}$), а в качестве $\mathfrak X_i$ выберем равномерное распределение на $\mathbb Z^{\star}_{\operatorname{num}(i)}$. Тогда семейство $(\mathop{\mathrm{Rabin}}_i\,|\, i\in I)$ называется семейством функций Рабина. Основное свойство этого семейства состоит в том, что оно является семейством функций с секретом в предположении трудности задачи факторизации чисел $pq$, где $(\{p,q\},\cdot)\leftarrow\mathfrak Q_n$.

Теорема 1 см. также [1], [2], [3]
Предположим, что для любого полиномиального вероятностного алгоритма $\mathcal F$ величина $\Pr(\mathcal F(1^n,pq)=\{p,q\})$, где $(\{p,q\},\cdot)\leftarrow\mathfrak Q_n$, пренебрежимо мала как функция от $n\in\mathbb N$. Тогда $(\mathop{\mathrm{Rabin}}_i\,|\, i\in I)$ является семейством функций с секретом относительно семейств распределений вероятностей $(\mathfrak G_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_i\,|\, i\in I)$.

В этой конструкции $a\in\mathbb Z^{\star}_{\operatorname{num}(i)}$ ($i\in I$), удовлетворяющий вышеуказанному условию, нужен для того, чтобы можно было инвертировать функцию $\mathop{\mathrm{Rabin}}_i$ с помощью полиномиального детерминированного алгоритма. Полиномиальный детерминированный алгоритм, извлекающий квадратные корни в группе $\mathbb Z^{\star}_r$ (где $r$ — простое число) при наличии какого либо квадратичного невычета по модулю $r$, хорошо известен (см., например, [4], [5]).

В то же время если ограничить функции из семейства Рабина на элементы нечетного порядка, можно обойтись без элемента $a$. Другим преимуществом этой модификации приведенной выше конструкции является то, что функции становятся перестановками.

Пусть $(\mathfrak P_n\,|\, n\in\mathbb N)$ — полиномиально конструируемое семейство распределений вероятностей на множестве двухэлементных подмножеств простых чисел. Положим $J=\left\{\left.\operatorname{num}^{-1}(pq)\,\right|\, \{p,q\}\in\mathop{\mathrm{supp}}\mathfrak P_n,\, n\in\mathbb N\right\}$. Для каждого $n\in\mathbb N$ распределение вероятностей $\mathfrak H_n$ определяется как распределение на множестве всех пар $\left(\operatorname{num}^{-1}(pq),\{p,q\}\right)$, где $\{p,q\}\leftarrow\mathfrak P_n$.

Для произвольного $j\in J$ пусть $X_j$ обозначает множество всех элементов нечетного порядка группы $\mathbb Z^{\star}_{\operatorname{num}(j)}$, а $\mathfrak X_j$ — равномерное распределение на множестве $X_j$. Тогда функция $\mathop{\mathrm{Rabin}}_j$ (состоящая, как и выше, в возведении в квадрат по модулю $\operatorname{num}(j)$) биективно отображает $X_j$ на себя. Нетрудно доказать следующее утверждение, которое, возможно, известно специалистам, но автору не удалось найти его в литературе.

Теорема 2
Предположим, что для любого полиномиального вероятностного алгоритма $\mathcal F$ величина $\Pr(\mathcal F(1^n,pq)=\{p,q\})$, где $\{p,q\}\leftarrow\mathfrak P_n$, пренебрежимо мала как функция от $n\in\mathbb N$. Тогда $(\mathop{\mathrm{Rabin}}_j|_{X_j}\,|\, j\in J)$ является семейством перестановок с секретом относительно семейств распределений вероятностей $(\mathfrak H_n\,|\, n\in\mathbb N)$ и $(\mathfrak X_j\,|\, j\in J)$.
Таким образом, семейство перестановок с секретом можно построить в предположении трудности задачи факторизации целых чисел.

Литература

  • [1] Rabin, M. O. «Digitalized signatures and public key functions as intractable as factoring» 1979
  • [2] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [3] Luby, M. «Pseudorandomness and cryptographic applications» 1996
  • [4] Shoup, V. «A computational introduction to number theory and algebra» 2008
  • [5] Bach, E. and Shallit, J. «Algoritmic number theory. Volume 1 (Efficient algorithms)» 1996

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна