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

Непредсказуемость следующего бита

next bit unpredictability
Определение 1 непредсказуемость следующего бита
Пусть $(\widetilde x_n\,|\, n\in\mathbb N)$ — семейство случайных величин, принимающих значения в множестве $\{0,1\}^*$. Для произвольной строки $x\in\{0,1\}^*$ обозначим через $B_x$ оракул, возвращающий при своем $i$-м вызове бит $x_{[i]}$ ($i\in\{1,\dots,\lvert{x}\rvert\}$). Тогда вышеуказанное семейство случайных величин удовлетворяет условию непредсказуемости следующего бита, если для $x\leftarrow\widetilde x_n$, для любого полиномиального вероятностного алгоритма $\mathcal A$, делающего при вычислении на входе $\left(1^n,1^{\lvert{x}\rvert}\right)$ строго меньше $\lvert{x}\rvert$ запросов к оракулу $B_x$ (обозначим число таких запросов через $k$), и для любого полинома $p$ неравенство \[ \Pr\left(\mathcal A^{B_x}\left(1^n,1^{\lvert{x}\rvert}\right) =x_{[k+1]}\right)\leqslant\frac12+\frac1{p(n)} \] выполняется при всех достаточно больших $n\in\mathbb N$.

См также [1]. Неформально условие непредсказуемости следующего бита означает, что по данному префиксу строки $x\leftarrow\widetilde x_n$ невозможно предсказать следующий за этим префиксом бит указанной строки за полиномиальное время с вероятностью, существенно большей $1/2$.

Теорема 2 см. [1], [2]
Пусть $(\widetilde x_n\,|\, n\in\mathbb N)$ — семейство случайных величин, принимающих значения в множестве $\{0,1\}^*$. Предположим, что существуют полином $p$ и функция $m\colon\mathbb N\to\mathbb N$ такие, что $m(n)\leqslant p(n)$ для всех $n\in\mathbb N$ и величина $\Pr(\lvert{\widetilde x_n}\rvert\ne m(n))$ пренебрежимо мала как функция от $n\in\mathbb N$. Тогда следующие условия эквивалентны:
  1. семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ псевдослучайно;
  2. семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ удовлетворяет условию непредсказуемости следующего бита;
  3. для $x\leftarrow\widetilde x_n$, $i\in_{\mathfrak U}\{1,\dots,\lvert{x}\rvert\}$, для любого полиномиального вероятностного алгоритма $\mathcal A$ и для любого полинома $p$ неравенство \[ \Pr\left(\mathcal A\left(1^n,1^{\lvert{x}\rvert},x_{[1,\dots,i-1]}\right) =x_{[i]}\right)\leqslant\frac12+\frac1{p(n)} \] выполняется при всех достаточно больших $n\in\mathbb N$.
Иногда под условием непредсказуемости следующего бита понимают условие 3 этой теоремы (см. [2]).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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