Distingeri și predictori de biți următori fără distribuție uniformă

Luați în considerare o distribuție de probabilitate $D$ peste $n$ șiruri de biți. Denota $U$ să fie distribuţia uniformă peste $n$ biți șiruri și $U_{n}$ să fie distribuția uniformă între numere întregi $\{1, 2, \ldots, n\}$.

Luați în considerare următoarele două afirmații echivalente (sunt echivalente după teorema lui Yao):

1. Nu există un predictor de timp polinom uniform al următorului bit $A$ astfel încât $$ \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{poli}(n)}. $$
2. Nu există un deosebitor de timp polinomial uniform $B$ astfel încât $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim U}{\text{Pr}}[B(Y)=1]\ mijlocul \geq \frac{1}{\text{poli}(n)}. $$

Mă gândeam la centralitatea distribuției uniforme în reduceri. Va funcționa o anumită formă a acestor afirmații atunci când înlocuim distribuția uniformă cu o distribuție cunoscută și eșantionabilă eficient $D_2$? Să presupunem că putem eșantiona eficient din fiecare marginal de $D_2$.

Cu alte cuvinte, luați în considerare afirmația 3 după cum urmează.

Afirmația 3: Nu există un deosebitor de timp polinomial uniform $B$ astfel încât $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim D_2}{\text{Pr}}[B(Y)=1]\ mijlocul \geq \frac{1}{\text{poli}(n)}. $$

Acest lucru implică și/sau este subînțeles printr-o declarație 4 ca următoarea (sau o variantă a acestei declarații)?

Instrucțiunea 4: Nu există un predictor de timp polinom uniform al următorului bit $A$ astfel încât $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq c, $$ Unde $c$ depinde de distributie $D_2$ iar avantajul distinctiv al $B$.

Dacă da, putem avea o formă explicită pentru $c$?

Frumoasa intrebare!

Acest lucru pare să fi fost abordat într-o conferință hârtie deasemenea disponibil Aici de Schrift și Shamir în 1991:

A.W. Schrift, A. Shamir, Despre universalitatea testului următor pe biți, Conferință despre Teoria și Aplicația Criptografiei, 1990.

Există și o versiune ulterioară a jurnalului în Journal of Cryptology.

Pentru a rezuma, ei consideră o sursă de biți părtinitori, dar independenți și cum să creeze un deosebitor pentru acesta. Rețineți că, fără pierderea generalității, ei presupun probabilitatea a $1$ bit este $b\în (1/2,1)$ dar numiți cantitatea $b$ părtinirea ceea ce este puțin contraintuitiv, în comparație cu utilizarea tradițională a părtinirii pentru cantitate $b-\frac{1}{2}$.

În special, ele definesc o rată de succes ponderată a oricărui algoritm PPTA non-constant $$A:\{0,1\}^n\rightarrow \{0,1\}$$ în prezicerea $i^{th}$ sursă cam părtinitoare ca

Notă: Notația $f<O(\nu(n))$ este folosit pentru orice funcție care dispare mai repede decât orice polinom putere reciprocă, adică orice dispărând funcţie.

Există și alte teste alternative propuse în lucrare.

Această lucrare este citată destul de mult, dar mai ales de lucrări care o aplică la diverse surse. De fapt, se pare că aceiași autori au folosit deja această tehnică pentru a dovedi rezultatele privind duritatea fiecărui bit, inclusiv bitul cel mai semnificativ cu zero părtinire pentru jurnalele discrete modulo un număr compus.