Список обозначений
Непредсказуемость следующего бита
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]
Иногда под условием непредсказуемости следующего бита понимают условие 3 этой теоремы (см. [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$. Тогда следующие условия эквивалентны:
- семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ псевдослучайно;
- семейство $(\widetilde x_n\,|\, n\in\mathbb N)$ удовлетворяет условию непредсказуемости следующего бита;
- для $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$.
Литература