Další bitový test - Next-bit test

v kryptografie a teorie výpočtu, další bitový test^[1] je test proti generátory pseudonáhodných čísel. Říkáme, že posloupnost bitů projde dalším testem bitů na jakékoli pozici ${ displaystyle i}$ v pořadí, pokud existuje nějaký útočník, který zná ${ displaystyle i}$ první bity (ale ne semeno) nemohou předvídat ${ displaystyle (i + 1)}$s rozumnou výpočetní silou.

Přesné prohlášení

Nechat ${ displaystyle P}$ být polynomem a ${ displaystyle S = {S_ {k} }}$ být souborem sad takových, že ${ displaystyle S_ {k}}$ obsahuje ${ displaystyle P (k)}$-bit dlouhé sekvence. Navíc nechte ${ displaystyle mu _ {k}}$ být rozdělení pravděpodobnosti strun dovnitř ${ displaystyle S_ {k}}$.

Nyní definujeme další bitový test dvěma různými způsoby.

Booleovská formulace obvodu

Predikční kolekce^[2] ${ displaystyle C = {C_ {k} ^ {i} }}$ je sbírka booleovské obvody, takže každý obvod ${ displaystyle C_ {k} ^ {i}}$ má méně než ${ displaystyle P_ {C} (k)}$ brány a přesně ${ displaystyle i}$ vstupy. Nechat ${ displaystyle p_ {k, i} ^ {C}}$ je pravděpodobnost, že na vstupu ${ displaystyle i}$ první kousky ${ displaystyle s}$, řetězec náhodně vybraný v ${ displaystyle S_ {k}}$ s pravděpodobností ${ displaystyle mu _ {k}}$, obvod správně předpovídá ${ displaystyle s_ {i + 1}}$, tj. :

Nyní to říkáme ${ displaystyle {S_ {k} } _ {k}}$ projde dalším bitovým testem, pokud jde o jakoukoli predikční kolekci ${ displaystyle C}$, jakýkoli polynom ${ displaystyle Q}$ :

Pravděpodobnostní Turingovy stroje

Můžeme také definovat další bitový test z hlediska pravděpodobnostní Turingovy stroje, ačkoli tato definice je poněkud silnější (viz Adlemanova věta ). Nechat ${ displaystyle { mathcal {M}}}$ být pravděpodobným Turingovým strojem pracujícím v polynomiálním čase. Nechat ${ displaystyle p_ {k, i} ^ { mathcal {M}}}$ je pravděpodobnost, že ${ displaystyle { mathcal {M}}}$ předpovídá ${ displaystyle (i + 1)}$st bit správně, tj.

Říkáme tu sbírku ${ displaystyle S = {S_ {k} }}$ projde dalším bitovým testem, pokud pro všechny polynomy ${ displaystyle Q}$, pro všechny, ale konečně mnoho ${ displaystyle k}$, pro všechny ${ displaystyle 0$:

Úplnost testu Yao

Další bitový test je konkrétním případem Yaův test pro náhodné sekvence a jejich předání je tedy a nutná podmínka pro průchod Yaův test. Bylo však také prokázáno, že dostatečný stav podle Yao.^[1]

Nyní to dokazujeme u pravděpodobnostního Turingova stroje Adleman již v roce nahradil randomizaci nerovnoměrností jeho věta. Případ booleovských obvodů nelze z tohoto případu odvodit (protože zahrnuje rozhodování o potenciálně nerozhodnutelných problémech), ale důkaz Adlemanovy věty lze snadno přizpůsobit případu nejednotných rodin booleovských obvodů.

Nechat ${ displaystyle { mathcal {M}}}$ být rozlišovacím znakem pravděpodobnostní verze testu Yao, tj. pravděpodobnostní Turingův stroj běžící v polynomiálním čase, takže existuje polynom ${ displaystyle Q}$ takové, že pro nekonečně mnoho ${ displaystyle k}$

${ displaystyle | p_ {k, S} ^ { mathcal {M}} - p_ {k, U} ^ { mathcal {M}} | geq { frac {1} {Q (k)}}}$

Nechat ${ displaystyle R_ {k, i} = {s_ {1} ldots s_ {i} u_ {i + 1} ldots u_ {P (k)} | s in S_ {k}, u in {0,1 } ^ {P (k)} }}$. My máme: ${ displaystyle R_ {k, 0} = {0,1 } ^ {P (k)}}$ a ${ displaystyle R_ {k, P (k)} = S_ {k}}$. Pak si toho všimneme ${ displaystyle sum _ {i = 0} ^ {P (k)} | p_ {k, R_ {k, i + 1}} ^ { mathcal {M}} - p_ {k, R_ {k, i }} ^ { mathcal {M}} | geq | p_ {k, R_ {k, P (k)}} ^ { mathcal {M}} - p_ {k, R_ {k, 0}} ^ { mathcal {M}} | = | p_ {k, S} ^ { mathcal {M}} - p_ {k, U} ^ { mathcal {M}} | geq { frac {1} {Q ( k)}}}$. Proto alespoň jeden z ${ displaystyle | p_ {k, R_ {k, i + 1}} ^ { mathcal {M}} - p_ {k, R_ {k, i}} ^ { mathcal {M}} |}$ by neměla být menší než ${ displaystyle { frac {1} {Q (k) P (k)}}}$.

Dále uvažujeme rozdělení pravděpodobnosti ${ displaystyle mu _ {k, i}}$ a ${ displaystyle { overline { mu _ {k, i}}}}$ na ${ displaystyle R_ {k, i}}$. Rozdělení ${ displaystyle mu _ {k, i}}$ je rozdělení pravděpodobnosti výběru ${ displaystyle i}$ první bity dovnitř ${ displaystyle S_ {k}}$ s pravděpodobností danou ${ displaystyle mu _ {k}}$a ${ displaystyle P (k) -i}$ zbývající bity náhodně rovnoměrně. Máme tedy:

Máme tedy ${ displaystyle mu _ {k, i} = { frac {1} {2}} ( mu _ {k, i + 1} + { overline { mu _ {k, i + 1}}} )}$ (ukazuje to jednoduchý trik kalkulu), tedy distribuce ${ displaystyle mu _ {k, i + 1}}$ a ${ displaystyle { overline { mu _ {k, i + 1}}}}$ lze rozlišit podle ${ displaystyle { mathcal {M}}}$. Bez ztráty všeobecnosti to můžeme předpokládat ${ displaystyle p _ { mu _ {k, i + 1}} ^ { mathcal {M}} - p _ { overline { mu _ {k, i + 1}}} ^ { mathcal {M}} geq { frac {1} {2}} + { frac {1} {R (k)}}}$, s ${ displaystyle R}$ polynom.

To nám dává možnou konstrukci Turingova stroje řešícího test dalšího bitu: po obdržení ${ displaystyle i}$ první bity sekvence, ${ displaystyle { mathcal {N}}}$ vyplní tento vstup hádáním bitů ${ displaystyle l}$ a pak ${ displaystyle P (k) -i-1}$ náhodné bity, vybrané s jednotnou pravděpodobností. Pak to běží ${ displaystyle { mathcal {M}}}$a výstupy ${ displaystyle l}$ pokud je výsledek ${ displaystyle 1}$, a ${ displaystyle 1-l}$ jiný.

Reference