Tilfældighedsudtrækker

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. december 2019; checks kræver 7 redigeringer .

Tilfældighedsekstraktoren er en funktion, der anvendes på outputtet fra en svagt tilfældig entropikilde , sammen med et kort ensartet fordelt tilfældig frø (engelsk frø) og genererer et tilfældigt output, der ser uafhængigt af kilden og er ensartet fordelt [1] .

Selvom en ekstraktor deler nogle konceptuelle ligheder med en pseudo-tilfældig talgenerator , er de forskellige begreber. Begge algoritmer tager som input et lille ensartet tilfældigt frø og producerer et større tilfældigt tal, der "ser" ensartet tilfældigt ud. Nogle pseudo-tilfældige generatorer er også ekstraktorer. (Når en pseudo-tilfældig talgenerator er baseret på eksistensen af hårde bits , kan man betragte en svagt tilfældig kilde som et sæt sandhedstabeller af sådanne prædikater og bevise, at outputtet er statistisk tæt på ensartet [2] ). Selvom den formelle definition af en pseudo-tilfældig generator ikke specificerer, at en svagt tilfældig kilde skal bruges, og i tilfælde af en ekstraktor, skal outputtet være statistisk tæt på ensartethed, er det i PRG'en kun påkrævet, at de er beregningsmæssigt umulige at skelne uniform, hvilket er et svagere krav.

Beskrivelse

I tidligere litteratur kaldes nogle ekstraktorer objektive algoritmer [3] , fordi de tager tilfældighed fra en kilde med en skæv fordeling (nogle gange bruges udtrykket "bias" til at betegne en svagt tilfældig kildes afvigelse fra homogenitet) og udsender en fordeling, der bliver uforskudt. Værdierne af en svagt tilfældig kilde vil altid være større end outputtet fra udtrækkeren, men en effektiv udtrækker er en, der reducerer dette forhold mellem værdier så meget som muligt, mens startværdien holdes lille. Det betyder med andre ord, at der er udtrukket så mange tilfældigheder som muligt fra kilden.

Eksempler på svagt tilfældige kilder ville være radioaktivt henfald eller termisk støj . Den eneste begrænsning for de mulige kilder er, at der ikke skal være nogen måde, de kan kontrolleres fuldstændigt, beregnes eller forudsige på en sådan måde, at en nedre grænse kan placeres på deres entropiniveau. For en given kilde kan en tilfældighedsekstraktor endda betragtes som en ægte tilfældig talgenerator , men der er ingen enkelt ekstraktor, der har vist sig at producere et virkelig tilfældigt output fra nogen form for svagt tilfældig kilde.

NIST Special Publication 800-90B anbefaler adskillige ekstraktorer, inklusive SHA -familien af hashes , og angiver, at hvis antallet af input-bits fra en entropikilde er det dobbelte af antallet af bit-output, kan output betragtes som næsten fuldstændig tilfældigt. [fire]

Formel definition

Min-entropien af en fordeling (betegnet som ) er det største reelle tal , således at for nogen af . I bund og grund betyder dette, hvad der er sandsynligheden for, at det vil tage sin mest sandsynlige værdi under den dårligste fordeling. Betegn som en ensartet fordeling på , eller . $x$ $H_{\infty }(X)$ $k$ ${\displaystyle \Pr[X=x]\leq 2^{-k))$ $x$ $x$ $x$ ${\displaystyle U_{\ell ))$ ${\displaystyle \{0,1\}^{\ell ))$ $H_{\infty }(U_{\ell })=\ell$

For en n - bit fordeling med min entropi siges k at være en fordeling. $x$ $x$ $(n,k)$

Definition (Extractor): ( k , ε ) - extractor

Lade være en funktion, der tager som input en prøve fra fordelingen , en d -bit begyndelsesværdi fra og returnerer en m -bit streng. vil være en (k , ε) -ekstraktor, hvis outputfordelingen for alle distributioner ikke er længere fra end ved ε. ${\text{Ext}}:\{0,1\}^{n}\ gange \{0,1\}^{d}\to \{0,1\}^{m}$ $(n,k)$ $x$ ${\displaystyle U_{d))$ ${\text{Ext))$ $(n,k)$ $x$ ${\displaystyle U_{m))$

I ovenstående definition er den statistiske afstand underforstået .

Så ekstraktoren tager et svagt tilfældigt n-bit input, en kort ensartet tilfældig initial størrelse og producerer et m - bit output, der ser ensartet tilfældigt ud. Målet er at gøre d lille (det vil sige bruge så lidt ensartet tilfældighed som muligt) og m så stor som muligt (det vil sige at komme så tæt på tilfældige bits af output som muligt).

Stærke udtrækkere

En ekstraktor er stærk, hvis sammenkædning af startværdien med udtrækkets output resulterer i en fordeling, der stadig er tæt på ensartet.

Definition (stærk ekstraktor): ( k , ε ) er en ekstraktor: A er en stærk udtrækker, dette er en funktion $(k,\epsilon )$

{\text{Ext}}:\{0,1\}^{n}\ gange \{0,1\}^{d}\højrepil \{0,1\}^{m}\,

sådan at fordelingen for hver fordeling ( to betyder den samme stokastiske variabel) ikke er mere end ε væk fra den ensartede fordeling i . $(n,k)$ $x$ $U_{d}\circ {\text{Ext))(X,U_{d})$ ${\displaystyle U_{d))$ ${\displaystyle U_{m+d))$

Eksplicitte udtrækker

Ved hjælp af den probabilistiske metode kan man vise, at der er en (k, ε)-ekstraktor, dvs. at konstruktionen er mulig. Det er dog normalt ikke nok blot at vise, at der findes en udtrækker. Der kræves en eksplicit konstruktion, som ser sådan ud:

Definition (eksplicit ekstraktor): for funktioner k(n), ε(n), d(n), m(n ), familien Ext = {Ext n } af funktioner

${\text{Ext}}_{n}:\{0,1\}^{n}\ gange \{0,1\}^{d(n)}\højrepil \{0,1\ }^{m(n)}$

er en eksplicit ( k , ε )-ekstraktor, hvis Ext( x , y ) kan beregnes i polynomisk tid (over længden af dens input) og for hver n er Ext n a ( k ( n ), ε ( n ) )-ekstraktor .

Det kan påvises ved en probabilistisk metode, at der eksisterer en ( k , ε )-ekstraktor med startværdi

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

og indgangslængde

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

. [5]

Disperser

En variant af tilfældighedsekstraktoren med svagere egenskaber er dispergeringsmidlet .

Tilfældige ekstraktorer i kryptografi

Et af de vigtigste aspekter af kryptografi er generering af tilfældige nøgler. [6] Det er ofte nødvendigt at generere hemmelige tilfældige nøgler fra semi-hemmelige kilder, der kan kompromitteres til en vis grad. Ved at tage en enkelt kort (og hemmelig) tilfældig nøgle som kilde, kan udtrækkeren bruges til at generere en længere pseudo-tilfældig nøgle, som derefter kan bruges til offentlig nøglekryptering. Især når en stærk udtrækker bruges, vil dens output fremstå ensartet tilfældigt selv for en person, der ser noget (men ikke hele) kilden. For eksempel, hvis kilden er kendt, men frøet er ukendt (eller omvendt). Denne egenskab ved ekstraktorer er især nyttig i såkaldt slagfast kryptografi, hvor den nødvendige udtrækker bruges som en slagfast funktion ( ERF). Slagfast kryptografi tager højde for, at det er vanskeligt at holde den indledende kommunikation hemmelig, hvilket ofte sker under krypteringsinitialisering , for eksempel skal afsenderen af krypteret information give modtagerne den nødvendige information til at dekryptere.

Eksempler

Von Neumann udtrækker

Yderligere information: Bernoulli-sekvens

Et tidligt eksempel på tilfældighedsudtrækkere blev foreslået af John von Neumann . Princippet for dets drift var som følger: det tager par af på hinanden følgende (ikke-overlappende) bits fra inputstrømmen. Hvis de to bit matcher, genereres der ikke noget output. Hvis bits er forskellige, udlæses værdien af den første bit. En von Neumann-ekstraktor kan påvises at producere et ensartet output, selvom fordelingen af inputbits ikke er ensartet, hvis hver bit har samme sandsynlighed for at være én, og der ikke er nogen korrelation mellem successive bit. [7]

Så den tager som input en Bernoulli-sekvens med p ikke nødvendigvis lig med 1/2, og udsender en Bernoulli-sekvens med I en mere generel forstand gælder dette for enhver erstatningssekvens - det er kun baseret på det faktum, at for ethvert par af lige store sandsynligt 01 og 10: for uafhængige forsøg har de sandsynligheder, mens for en erstatningssekvens kan sandsynligheden være mere komplekse, men begge er lige sandsynlige. $p=1/2.$ $p\cdot (1-p)=(1-p)\cdot p$

Ansøgninger

Tilfældige taludtrækkere bruges i vid udstrækning i kryptografiske applikationer, hvor en kryptografisk hashfunktion [8] anvendes på en højentropi, men ikke ensartet distribueret kilde, såsom drevtiming eller tastaturforsinkelsesinformation, for at producere et ensartet tilfældigt resultat.

Tilfældighedsekstraktorer har spillet en rolle i den seneste udvikling inden for kvantekryptografi , hvor fotoner bruges af en tilfældighedsekstraktor til at generere sikre tilfældige bits. [9]

Tilfældighedsudtrækkere bruges også i nogle grene af beregningsmæssig kompleksitetsteori . [otte]

Noter

↑ L. Trevisan, S. Vadhan. Uddrag af tilfældigheder fra samplingsbare distributioner // Proceedings of the 41st Annual Symposium on Foundations of Computer Science. - Washington, DC, USA: IEEE Computer Society, 2000. - S. 32- . — ISBN 978-0-7695-0850-4 .
↑ Luca Trevisan. Extractors and Pseudorandom Generators (engelsk) // Journal of the ACM (JACM): Journal. - 2013. - 21. oktober. - S. 8 .
↑ David K. Gifford, Natural Random Numbers, MIT /LCS/TM-371, Massachusetts Institute of Technology, august 1988.
↑ Elaine Barker, John Kelsey. Anbefaling for de entropikilder, der bruges til generering af tilfældig bit (NIST DRAFT Special Publication 800-90B ) // NIST. - 2012. - August. - S. 18 .
↑ Ronen Shaltiel. Seneste udvikling inden for eksplicit konstruktion af udsugningsanlæg. S.5.
↑ Jesse Kamp og David Zuckerman. Deterministiske ekstraktorer til bitfiksende kilder og eksponeringsstabil kryptografi., SIAM J. Comput., Vol. 36, nr. 5, s. 1231-1247.
↑ John von Neumann. Forskellige teknikker brugt i forbindelse med tilfældige cifre. Applied Math Series, 12:36-38, 1951.
↑ 1 2 hn M. Hitchcock, A. Pavan, NV Vinodchandran. Kolmogorov Complexity in Randomness Extraction (engelsk) // Electronic Colloquium on Computational Complexity. - 2009. - Nr. 71 . - S. 1 . — ISSN 1433-8092 .
↑ Ziyong Zheng, Yichen Zhang, Song Yu, Hong Guo. Eksperimentel demonstration af Gaussisk distribueret kvantetilfældig talgenerator // SPIE Proceedings Vol. 10733 : log. - 2018. - 11. september. - S. 4-5 .