Различители и предикторы следующего бита без равномерного распределения

Рассмотрим распределение вероятностей $Д$ над $n$ битовые строки. Обозначать $U$ быть равномерным распределением по $n$ битовые строки и $U_{n}$ быть равномерным распределением по целым числам $\{1, 2, \ldots, n\}$.

Рассмотрим следующие два эквивалентных утверждения (они эквивалентны по теореме Яо):

1. Не существует универсального предсказателя следующего бита за полиномиальное время $А$ такой, что $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq \frac{1} {2} + \frac{1}{\text{poly}(n)}. $$
2. Не существует единого полиномиального различителя времени $В$ такой, что $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim U}{\text{Pr}}[B(Y)=1]\ середина \geq \frac{1}{\text{poly}(n)}. $$

Я думал о центральной роли равномерного распределения в редукциях. Будет ли какая-либо форма этих утверждений работать, когда мы заменим равномерное распределение известным и эффективно выбираемым распределением? $D_2$? Допустим, мы также можем эффективно выбирать из каждого маргинала $D_2$.

Другими словами, рассмотрим утверждение 3 следующим образом.

Заявление 3: Не существует единого полиномиального различителя времени $В$ такой, что $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim D_2}{\text{Pr}}[B(Y)=1]\ середина \geq \frac{1}{\text{poly}(n)}. $$

Подразумевает ли это и/или подразумевается утверждением 4, подобным следующему (или некоторым вариантом этого утверждения)?

Утверждение 4. Не существует универсального предсказателя следующего бита за полиномиальное время. $А$ такой, что $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq c, $$ куда $с$ зависит от дистрибутива $D_2$ и отличительным преимуществом $В$.

Если да, то можем ли мы иметь явную форму для $с$?

Хороший вопрос!

Кажется, это обсуждалось на конференции. бумага так же доступно здесь Шрифтом и Шамиром в 1991 году:

А.В. Шрифт, А. Шамир, Об универсальности следующего битового теста, Конференция по теории и применению криптографии, 1990.

Более поздняя версия журнала также есть в Journal of Cryptology.

Подводя итог, они считают источником смещенные, но независимые биты и как разработать для него отличительный признак. Заметим, что без ограничения общности они предполагают вероятность $1$ бит $б\в (1/2,1)$ но назовите количество $б$ уклон что немного противоречит здравому смыслу по сравнению с традиционным использованием смещения для количества $b-\frac{1}{2}$.

В частности, они определяют взвешенную вероятность успеха любого непостоянного алгоритма PPTA. $$A:\{0,1\}^n\стрелка вправо \{0,1\}$$ в прогнозировании $ я ^ {й} $ немного предвзятый источник, как

Примечание: Обозначение $f<O(\nu(n))$ используется для любой функции, которая обращается в нуль быстрее, чем любой многочлен взаимная сила, т. е. любая исчезновение функция.

В статье предложены и другие альтернативные тесты.

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