Výpočetní nerozeznatelnost - Computational indistinguishability - Wikipedia

v výpočetní složitost a kryptografie, dvě rodiny distribucí jsou výpočetně k nerozeznání pokud žádný efektivní algoritmus nerozpozná rozdíl mezi nimi, kromě malé pravděpodobnosti.

Formální definice

Nechat ${ displaystyle scriptstyle {D_ {n} } _ {n in mathbb {N}}}$ a ${ displaystyle scriptstyle {E_ {n} } _ {n in mathbb {N}}}$ být dva distribuční soubory indexováno a bezpečnostní parametr n (což obvykle odkazuje na délku vstupu); říkáme, že jsou výpočetně k nerozeznání, pokud vůbec nejednotný pravděpodobnostní polynomiální čas algoritmus A, následující množství je a zanedbatelná funkce v n:

{ displaystyle delta (n) = vlevo | Pr _ {x dostane D_ {n}} [A (x) = 1] - Pr _ {x dostane E_ {n}} [A (x) = 1] vpravo |.}

označeno ${ displaystyle D_ {n} přibližně E_ {n}}$ .^[1] Jinými slovy, každý efektivní algoritmus A'Chování se významně nemění, pokud jsou dané vzorky podle D_n nebo E_n v limitu jako ${ displaystyle n to infty}$ . Další interpretace výpočetní nerozeznatelnosti spočívá v tom, že algoritmy polynomiálního času, které se aktivně pokoušejí rozlišovat mezi těmito dvěma soubory, to nemohou udělat: že jakýkoli takový algoritmus bude fungovat jen zanedbatelně lépe, než kdyby se dalo jen hádat.

Související pojmy

Implicitní v definici je podmínka, že algoritmus, ${ displaystyle A}$ , se musí rozhodnout na základě jediného vzorku z jedné z distribucí. Lze si představit situaci, ve které by algoritmus, který se pokouší rozlišit mezi dvěma distribucemi, mohl přistupovat k tolika vzorkům, kolik potřeboval. Proto jsou považovány dva soubory, které nelze rozlišit pomocí algoritmů polynomiálního času při pohledu na více vzorků nerozeznatelné vzorkováním v polynomiálním čase.^[2]^:107 Pokud může algoritmus polynomiálního času generovat vzorky v polynomiálním čase nebo má přístup k náhodný věštec který pro něj generuje vzorky, pak nerozeznatelnost vzorkováním v polynomiálním čase je ekvivalentní výpočetní nerozeznatelnosti.^[2]^:108

Reference

^ Přednáška 4 - Výpočetní nerozeznatelnost, pseudonáhodné generátory
^ ^A ^b Goldreich, O. (2003). Základy kryptografie. Cambridge, Velká Británie: Cambridge University Press.

externí odkazy

Yehuda Lindell. Úvod do kryptografie
Donald Beaver a Silvio Micali a Phillip Rogaway „The Round Complexity of Secure Protocols (Extended Abstract), 1990, s. 503–513
Shafi Goldwasser a Silvio Micali. Pravděpodobnostní šifrování. JCSS, 28 (2): 270–299, 1984
Oded Goldreich. Základy kryptografie: Svazek 2 - Základní aplikace. Cambridge University Press, 2004.
Jonathan Katz, Yehuda Lindell „Úvod do moderní kryptografie: principy a protokoly,“ Chapman & Hall / CRC, 2007

Tento článek včlení materiál od výpočetně k nerozeznání na PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.

[1] Přednáška 4 - Výpočetní nerozeznatelnost, pseudonáhodné generátory

[Goldreich-2] A ^b Goldreich, O. (2003). Základy kryptografie. Cambridge, Velká Británie: Cambridge University Press.

[1]

[2]