Randomness Extractor

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. december 24-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A véletlenszerűség-kivonó egy olyan függvény, amelyet egy gyengén véletlenszerű entrópiaforrás kimenetére alkalmaznak egy rövid, egyenletes eloszlású véletlen maggal (angol seed) együtt, és egy véletlenszerű kimenetet generál, amely függetlennek tűnik a forrástól és egyenletesen eloszlik [1] .

Noha egy kivonónak van néhány fogalmi hasonlósága egy pszeudo-véletlenszám-generátorral , ezek különböző fogalmak. Mindkét algoritmus egy kicsi, egyenletesen véletlenszerű magot vesz be, és egy nagyobb véletlenszámot állít elő, amely egyenletesen véletlenszerűnek tűnik. Egyes pszeudo-véletlen generátorok is kivonók. (Ha egy pszeudo-véletlenszám-generátor kemény bitek létezésén alapul , akkor egy gyengén véletlenszerű forrást tekinthetünk ilyen predikátumok igazságtáblázatainak halmazának, és bebizonyíthatjuk, hogy a kimenet statisztikailag közel áll az egyenleteshez [2] ). Bár a pszeudo-véletlen generátor formális definíciója nem írja elő, hogy gyengén véletlenszerű forrást kell használni, és egy extraktor esetén a kimenetnek statisztikailag közel kell lennie egységeshez , a PRG -ben csak az szükséges, hogy számításilag megkülönböztethetetlenek [ az egységestől, ami gyengébb követelmény.

Leírás

A korábbi irodalomban egyes kivonatokat torzításmentes algoritmusoknak [3] neveznek, mert véletlenszerűséget vesznek egy torz eloszlású forrásból (néha a "bias" kifejezést egy gyengén véletlenszerű forrás homogenitástól való eltérésének jelölésére használják), és olyan eloszlást adnak ki, amely elmozdíthatatlanná válik. A gyengén véletlenszerű forrás értékei mindig nagyobbak lesznek, mint az elszívó kimenete, de a hatékony elszívó az, amely a lehető legnagyobb mértékben csökkenti ezt az értékarányt, miközben a kezdeti értéket kicsiben tartja. Más szóval ez azt jelenti, hogy a lehető legtöbb véletlenszerűséget kivonták a forrásból.

Gyengén véletlenszerű források például a radioaktív bomlás vagy a termikus zaj . A lehetséges források egyetlen megkötése az, hogy semmiképpen sem lehet őket teljesen ellenőrizni, kiszámítani vagy előre jelezni oly módon, hogy az entrópiaszintjükre alsó korlátot lehessen állítani. Egy adott forrás esetében a véletlenszám-kivonó akár valódi véletlenszám-generátornak is tekinthető , azonban nincs egyetlen olyan kivonó sem, amelyről bebizonyosodott, hogy valóban véletlenszerű kimenetet produkálna bármilyen gyengén véletlenszerű forrásból.

A NIST Special Publication 800-90B számos kivonatot ajánl, köztük az SHA hash családot , és kijelenti, hogy ha egy entrópiaforrásból származó bemeneti bitek száma kétszerese a kimeneti bitek számának, a kimenet szinte teljesen véletlenszerűnek tekinthető. [négy]

Formális definíció

Egy eloszlás min-entrópiája (jellel jelöljük ) a legnagyobb valós szám , amely bármelyik esetén . Ez lényegében azt jelenti, hogy mekkora a valószínűsége annak, hogy a legrosszabb eloszlásban veszi fel a legvalószínűbb értékét. Jelölje egyenletes eloszlásként a , vagy -on . $x$ $H_{\infty }(X)$ $k$ ${\displaystyle \Pr[X=x]\leq 2^{-k))$ $x$ $x$ $x$ ${\displaystyle U_{\ell ))$ $\{0,1\}^{\ell }$ $H_{\infty }(U_{\ell })=\ell$

Min entrópiájú n bites eloszlás esetén k-t eloszlásnak mondjuk . $x$ $x$ ${\megjelenítési stílus (n,k)}$

Definíció (Extractor): ( k , ε ) - extraktor

Legyen egy függvény, amely bemenetként vesz egy mintát a disztribúcióból , egy d bites kezdeti értéket az eloszlásból, és egy m bites karakterláncot ad vissza. akkor lesz (k , ε) -kivonó, ha az összes eloszlásnál a kimeneti eloszlás nem távolodik ettől, mint ε. ${\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}$ ${\megjelenítési stílus (n,k)}$ $x$ ${\displaystyle U_{d))$ ${\text{Ext))$ ${\megjelenítési stílus (n,k)}$ $x$ ${\displaystyle U_{m))$

A fenti definícióban a statisztikai távolság magában foglalja .

Tehát a kivonó gyengén véletlenszerű n-bites bemenetet vesz fel, egy rövid, egyenletesen véletlenszerű kezdeti méretet, és egy m bites kimenetet állít elő, amely egyenletesen véletlenszerűnek tűnik. A cél az, hogy d kicsi legyen (vagyis minél kevesebb egyenletes véletlenszerűséget használjunk), m pedig minél nagyobb legyen (vagyis minél közelebb kerüljünk a kimenet véletlenszerű bitjéhez).

Erős elszívók

Az extraktor akkor erős, ha a kezdeti érték és az extraktor kimenetének összefűzése még mindig közel egyenletes eloszlást eredményez.

Definíció (Erős kivonó): ( k , ε ) egy extraktor: A egy erős extraktor, ez egy függvény $(k,\epsilon )$

{\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,

úgy, hogy minden eloszlásnál az eloszlás (kettő ugyanazt a valószínűségi változót jelenti) legfeljebb ε távolságra legyen az egyenletes eloszlástól -ben . ${\megjelenítési stílus (n,k)}$ $x$ $U_{d}\circ {\text{Ext))(X,U_{d})$ ${\displaystyle U_{d))$ ${\displaystyle U_{m+d))$

Explicit kivonatok

Valószínűségi módszerrel kimutatható, hogy létezik (k, ε) -extraktor , azaz a konstrukció lehetséges. Általában azonban nem elég egyszerűen megmutatni, hogy létezik egy kivonó. Explicit konstrukcióra van szükség, amely így néz ki:

Definíció (explicit kivonó): a k(n), ε(n), d(n), m(n ) függvények esetében a függvénycsalád Ext = {Ext n }

${\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\jobbra \{0,1\ }^{m(n)}$

egy explicit ( k , ε )-kivonó, ha Ext( x , y ) polinomiális időben (a bemenete hosszában) kiszámítható, és minden n esetén Ext n a ( k ( n ), ε ( n ) )-elszívó .

Valószínűségi módszerrel kimutatható, hogy létezik kezdeti értékű ( k , ε )-kivonó

d=\log {(nk)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)

és a belépési hossz

m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)

. [5]

Diszpergáló

A véletlenszerűség-kivonó gyengébb tulajdonságokkal rendelkező változata a diszpergáló .

Véletlenszerű kivonatok a kriptográfiában

A kriptográfia egyik legfontosabb szempontja a véletlenszerű kulcsok generálása. [6] Gyakran szükséges titkos véletlenszerű kulcsokat előállítani féltitkos forrásokból, amelyek bizonyos mértékig kompromittálhatóak. Ha egyetlen rövid (és titkos) véletlenszerű kulcsot veszünk forrásként, a kivonat segítségével hosszabb pszeudo-véletlen kulcsot állíthatunk elő, amelyet aztán nyilvános kulcsú titkosításra használhatunk. Különösen, ha erős kivonatot használunk, annak kimenete egyenletesen véletlenszerűnek tűnik még annak is, aki látja a forrás egy részét (de nem az egészet). Például, ha a forrás ismert, de a mag ismeretlen (vagy fordítva). Az elszívók ezen tulajdonsága különösen hasznos az úgynevezett ütésálló kriptográfiában, ahol a szükséges extraktort ütésálló funkcióként ( ERF) használják. Az ütésálló kriptográfia figyelembe veszi azt a tényt, hogy a kezdeti kommunikációt nehéz titokban tartani, ami gyakran előfordul a titkosítás inicializálása során , például a titkosított információ küldőjének meg kell adnia a címzetteket a visszafejtéshez szükséges információkkal.

Példák

Von Neumann kivonó

További információ: Bernoulli szekvencia

Neumann János javasolta a véletlenszerűség-kivonók egyik korai példáját . Működésének elve a következő volt: egymást követő (nem átfedő) bitpárokat vesz a bemeneti folyamból. Ha a két bit egyezik, nem jön létre kimenet. Ha a bitek különböznek, akkor az első bit értéke kerül kiadásra. Egy Neumann-kivonóról kimutatható, hogy egyenletes kimenetet produkál még akkor is, ha a bemeneti bitek eloszlása nem egyenletes, ha minden bitnek azonos a valószínűsége, hogy egy, és nincs korreláció az egymást követő bitek között. [7]

Tehát bemenetként egy Bernoulli-szekvenciát vesz fel, amelynek p nem feltétlenül egyenlő 1/2-vel, és egy Bernoulli -szekvenciát ad ki a következővel . Általánosabb értelemben ez minden helyettesítő szekvenciára vonatkozik - ez csak azon a tényen alapul, hogy bármely egyenlő pár esetén valószínű 01 és 10: független kísérleteknél vannak valószínűségek , míg helyettesítő sorozatnál a valószínűségek összetettebbek lehetnek, de mindkettő egyformán valószínű. $p=1/2.$ $p\cdot (1-p)=(1-p)\cdot p$

Alkalmazások

A véletlenszám-kivonatokat széles körben használják kriptográfiai alkalmazásokban, ahol egy kriptográfiai hash függvényt [8] alkalmaznak egy nagy entrópiájú, de nem egyenletesen elosztott forrásra, például a meghajtó időzítésére vagy a billentyűzet késleltetésére, hogy egyenletesen véletlenszerű eredményt kapjanak.

A véletlenszerűség-kivonók szerepet játszottak a kvantumkriptográfia legújabb fejlesztéseiben , ahol a fotonokat véletlenszerűség-kivonó segítségével biztonságos véletlenszerű bitek generálására használják. [9]

A véletlenszerűség kivonóit a számítási komplexitáselmélet egyes ágaiban is használják . [nyolc]

Jegyzetek

↑ L. Trevisan, S. Vadhan. Véletlenszerűség kinyerése mintavételezhető eloszlásokból // Proceedings of the 41. Annual Symposium on Foundations of Computer Science. - Washington, DC, USA: IEEE Computer Society, 2000. - P. 32- . — ISBN 978-0-7695-0850-4 .
↑ Luca Trevisan. Extractors and Pseudorandom Generators (angol) // Journal of the ACM (JACM): Journal. - 2013. - október 21. - S. 8 .
↑ David K. Gifford, Natural Random Numbers, MIT /LCS/TM-371, Massachusetts Institute of Technology, 1988. augusztus.
↑ Elaine Barker, John Kelsey. Recommendation for the Entropy Sources Used for Random Bit Generation (NIST DRAFT Special Publication 800-90B ) // NIST. - 2012. - augusztus. - S. 18 .
↑ Ronen Shaltiel. Legutóbbi fejlemények az elszívók explicit felépítésében. P.5.
↑ Jesse Kamp és David Zuckerman. Determinisztikus kivonók bitrögzítő forrásokhoz és expozíciótűrő kriptográfiához.,SIAM J. Comput., Vol. 36. sz. 5, pp. 1231-1247.
↑ Neumann János. Különféle technikák a véletlen számjegyekkel kapcsolatban. Alkalmazott matematikai sorozat, 12:36-38, 1951.
↑ 1 2 hn M. Hitchcock, A. Pavan, NV Vinodchandran. Kolmogorov Complexity in Randomness Extraction (angol) // Elektronikus kollokvium a számítási komplexitásról. - 2009. - 71. sz . - S. 1 . — ISSN 1433-8092 .
↑ Ziyong Zheng, Yichen Zhang, Song Yu, Hong Guo. A Gauss-féle elosztott kvantum véletlenszám-generátor kísérleti demonstrációja // SPIE Proceedings Vol. 10733 : log. - 2018. - szeptember 11. - S. 4-5 .