Частично односторонние функции

Часто в приложениях бывает так, что нельзя сделать так, чтобы функция была везде определена. (Например, функция, определенная только на произведении двух больших чисел.) Часто бывает нужно выбрать случайный элемент из области определения.

Определение

Пусть $\mu_n$ - случайная величина со значениями в $\{0, 1\}^{k(n)}$. Будем говорить, что $\mu_n$ - полиномиально вычислимая, если существует такой полиномиальный вероятностный алгоритм $S$ с пустым входом, что $\forall x \in \{0, 1\}^{k(n)}\ Pr\{S(\varepsilon) = x\} = Pr\{\mu_n = x\}$

Определение

Статистическое расстояние: $dist(\mu_n, \nu_n) = max_{T \subset \{0, 1\}^{k(n)}} |Pr\{\mu_n \ in T \} - Pr\{\nu_n \in T \}| = \sum_{x \ in \{0, 1\}^{k(n)}} \frac{1}{2}|Pr\{\mu_n = x \} - Pr\{\nu_n = x \}|$

Определение

Случайная величина $\mu_n$ доступна, если $$\exists \nu_n\ \forall p(\cdot)\ \exists N\ \forall n > N dist(\mu_n, \nu_n) < \frac{1}{p(n)}$$
где $\nu_n$ -- некоторая полиномиально вычислимая случайная величина.

Определение

Функция $f \colon D \rightarrow \{0, 1\}^n$ называется частичной односторонней, если:

• Равномерная случайная величина на $D$ доступна
• $f$ вычислима за полиномиальное время
• $\forall R_n\ \forall p(\cdot)\ \exists N\ \forall n > N\ Pr_{x \in D}\{R_n(f(x)) \in D, f(R_n(f(x))) = f(x)\} < \frac{1}{p(n)}$

Предположительно частично односторонние функции:

• Функция Рабина: $(x, y) \rightarrow (x^2\ mod\ y, y)$, где
  $y = p \cdot q$,
  $p_n, q$ - простые вида $4k + 3$, а
  $x$ - квадратичный вычет.

• Функция RSA: $(x, y, z) \rightarrow (x^z\ mod\ y, y, z)$ - извлечение корня степени $z$
  $y = p \cdot q$
  $x$ - вычет, взаимно простый с $y$
  $z$ - взаимно просто с $\phi(p\cdot q) = (p - 1)(q - 1)$

• Дискретная экспонента $(x, y, z) \rightarrow (x, y, x^z)$ - логарифм по основанию $x$.