1707:. It is often necessary to generate secret and random keys from sources that are semi-secret or which may be compromised to some degree. By taking a single, short (and secret) random key as a source, an extractor can be used to generate a longer pseudo-random key, which then can be used for public key encryption. More specifically, when a strong extractor is used its output will appear be uniformly random, even to someone who sees part (but not all) of the source. For example, if the source is known but the seed is not known (or vice versa). This property of extractors is particularly useful in what is commonly called
69:, as they take the randomness from a so-called "biased" source and output a distribution that appears unbiased. The weakly random source will always be longer than the extractor's output, but an efficient extractor is one that lowers this ratio of lengths as much as possible, while simultaneously keeping the seed length low. Intuitively, this means that as much randomness as possible has been "extracted" from the source.
4262:. From the input stream, his extractor took bits, two at a time (first and second, then third and fourth, and so on). If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no
4519:. Input bits are pushed to the machine, evolving orbits and trajectories in multiple dynamical systems. Thus, small differences in the input produce very different outputs. Such a machine has a uniform output even if the distribution of input bits is not uniform or has serious flaws, and can therefore use weak
80:, one can think of the weakly random source as a set of truth tables of such predicates and prove that the output is statistically close to uniform.) However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be
58:; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (
4538:
Note that while true chaotic systems are mathematically sound for 'amplifying' entropy, this is predicated on the availability of real numbers with an infinite precision. When implemented in digital computers with finite precision number representation, as in chaos machines using
76:(PRG), but the two concepts are not identical. Both are functions that take as input a small, uniformly random seed and produce a longer output that "looks" uniformly random. Some pseudorandom generators are, in fact, also extractors. (When a PRG is based on the existence of
1439:
1058:
4214:
1593:
4502:
Iterations upon the Von
Neumann extractor include the Elias and Peres extractor, the latter of which reuses bits in order to produce larger output streams than the Von Neumann extractor given the same size input stream.
3521:
2014:
The goal is to construct an adaptive ERF whose output is highly random and uniformly distributed. But a stronger condition is often needed in which every output occurs with almost uniform probability. For this purpose
1978:
619:
1676:
4104:
3018:
3827:
4497:
4052:
3189:
2802:
2528:
2290:
1715:(ERF). Exposure-Resilient cryptography takes into account that the fact that it is difficult to keep secret the initial exchange of data which often takes place during the initialization of an
1272:)-extractor, i.e. that the construction is possible. However, it is usually not enough merely to show that an extractor exists. An explicit construction is needed, which is given as follows:
1170:
4853:
Ma, Xiongfeng; Xu, Feihu; Xu, He; Tan, Xiaoqing; Qi, Bing; Lo, Hoi-Kwong (June 2013). "Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction".
2919:
420:
3905:
3623:
2730:
43:
4379:
3997:
3254:
2871:
2682:
2640:
2456:
3410:
3293:
371:
225:
154:
3550:
3348:
957:
3713:
3119:
2958:
2593:
2343:
2009:
814:
728:
3064:
1217:
332:
1250:
4720:
Jesse Kamp and David
Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography., SIAM J. Comput., Vol. 36, No. 5, pp. 1231–1247.
4309:
3319:
2060:
4238:
2562:
1197:
1093:
845:
772:
702:
651:
503:
2185:
2110:
1322:
4127:
3948:
3928:
3850:
3756:
3733:
3683:
3663:
3643:
3590:
3570:
3433:
3368:
3209:
3084:
3038:
2824:
2390:
2366:
2312:
2207:
2154:
2132:
2082:
1854:
1832:
1810:
1788:
1766:
1113:
907:
887:
792:
671:
471:
447:
305:
285:
265:
245:
174:
118:
4581:
function is applied to a high-entropy, but non-uniform source, such as disk drive timing information or keyboard delays, to yield a uniformly random result.
965:
4135:
1507:
4934:
4523:. Additionally, this scheme allows for increased complexity, quality, and security of the output stream, controlled by specifying three parameters:
65:
Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called
4588:
developments, for example, distilling the raw output from a quantum random number generators into a shorter, secure and uniformly random output.
4381:, while for an exchangeable sequence the probability may be more complicated, but both are equally likely. To put it simply, because the bits are
3441:
4499:. Hence, if pairs of 01 and 10 are mapped onto bits 0 and 1 and pairs 00 and 11 are discarded, then the output will be a uniform distribution.
1861:
527:
1604:
1719:
application e.g., the sender of encrypted information has to provide the receivers with information which is required for decryption.
4944:
4939:
4653:
4060:
85:
2963:
4565:
hash family and states that if the amount of entropy input is twice the number of bits output from them, that output will exhibit
4820:"Analyzing Logistic Map Pseudorandom Number Generators for Periodicity Induced by Finite Precision Floating-Point Representation"
4613:
2600:
This lemma is proved by Kamp and
Zuckerman. The lemma is proved by examining the distance from uniform of the output, which in a
59:
4819:
4592:
62:); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.
47:
3764:
4732:
Jesse Kamp and David
Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. P. 1242.
4392:
4005:
4312:
3124:
2737:
2463:
2214:
4552:
1118:
2878:
376:
4741:
John von
Neumann. Various techniques used in connection with random digits. Applied Math Series, 12:36–38, 1951.
3858:
3595:
2702:
4322:
3956:
855:
3214:
2831:
4382:
4643:
73:
4596:
4562:
2645:
2603:
2419:
3376:
3259:
4840:
4764:
4753:"Numerical and Non-Asymptotic Analysis of Elias's and Peres's Extractors with Finite Input Sequences"
4585:
4386:
1261:
337:
179:
123:
4520:
3529:
3327:
2928:
930:
81:
77:
3688:
3089:
2934:
2569:
2319:
1985:
1722:
The following paragraphs define and establish an important relationship between two kinds of ERF--
797:
711:
4862:
4578:
4270:
4253:
4689:
3049:
1202:
310:
34:, often simply called an "extractor", is a function, which being applied to output from a weak
4800:
4782:
4649:
4618:
4555:
as a randomness extractor. However, not every hashing algorithm is suitable for this purpose.
4543:, the periodicity has been shown to fall far short of the full space for a given bit length.
51:
4888:
1222:
4872:
4841:
Recommendation for the
Entropy Sources Used for Random Bit Generation (draft) NIST SP800-90B
4790:
4772:
4280:
4259:
3298:
2030:
4919:
Tossing a Biased Coin (and the optimality of advanced multi-level strategy) (lecture notes)
4894:
4223:
2535:
1434:{\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}}
1175:
1066:
921:
the seed with the extractor's output yields a distribution that is still close to uniform.
823:
745:
680:
624:
476:
4623:
4516:
2161:
1461:
2089:
4918:
4768:
4795:
4752:
4220:
which proves that there exists an explicit k-APRF extractor with the given properties.
4112:
3933:
3913:
3835:
3741:
3718:
3668:
3648:
3628:
3575:
3555:
3418:
3353:
3194:
3069:
3023:
2809:
2375:
2351:
2297:
2192:
2139:
2117:
2067:
1839:
1817:
1795:
1773:
1751:
1704:
1098:
892:
872:
777:
656:
456:
432:
290:
270:
250:
230:
159:
103:
35:
3350:, as well as the fact that it is computable in linear computing time on the length of
4928:
4608:
4512:
918:
55:
17:
4913:
Deterministic
Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography
4566:
1700:
1053:{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,}
4912:
4711:
Ronen
Shaltiel. Recent developments in explicit construction of extractors. P. 5.
4561:
Special
Publication 800-90B (draft) recommends several extractors, including the
4209:{\displaystyle k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}}
4263:
1588:{\displaystyle d=\log {(n-k)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)}
909:
as possible (i.e. to get out as many close-to-random bits of output as we can).
97:
4900:
4876:
4577:
Randomness extractors are used widely in cryptographic applications, whereby a
4901:
Randomness
Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes
2687:
The lemma leads to the following theorem, stating that there in fact exists a
1716:
4786:
4515:
applied to the input stream. This approach generally relies on properties of
3516:{\displaystyle m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })}
3373:
That this extractor fulfills the criteria of the lemma is trivially true as
3370:
can be found in the paper by Jesse Kamp and David Zuckerman (p. 1240).
1688:
4804:
287:
is to take its most likely value, giving a worst-case bound on how random
4540:
1973:{\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}
614:{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}
4751:
Prasitsupparote, Amonrat; Konno, Norio; Shikata, Junji (October 2018).
3758:
is calculated by using the definition of the extractor, where we know:
1671:{\displaystyle m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)}
4906:
4777:
889:(i.e. to use as little uniform randomness as possible) and as high an
39:
4277:
not necessarily equal to 1/2, and outputs a Bernoulli sequence with
2348:
Kamp and Zuckerman have proved a theorem stating that if a function
1687:
A variant of the randomness extractor with weaker properties is the
869:-bit output that looks uniformly random. The aim is to have a low
38:, together with a short, uniformly random seed, generates a highly
4867:
1493:
By the probabilistic method, it can be shown that there exists a (
2400:
extractor having sufficiently small error and taking as input an
4678:/LCS/TM-371, Massachusetts Institute of Technology, August 1988.
4558:
4889:
Randomness Extractors for Independent Sources and Applications
4675:
4099:{\displaystyle \Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}}
865:-bit input and a short, uniformly random seed and produces an
4315:—it only relies on the fact that for any pair, 01 and 10 are
3950:
is on its lower bound. Now by algebraic calculations we get:
3013:{\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}
2408:-ERF. A more specific extractor is expressed in this lemma:
4895:
Recent developments in explicit constructions of extractors
2805:, computable in a linear number of arithmetic operations on
2019:(APRF) are used. The definition of an APRF is as follows:
1711:
cryptography in which the desired extractor is used as an
4584:
Randomness extractors have played a major role in recent
4319:
likely: for independent trials, these have probabilities
2404:, bit-fixing source is also an APRF and therefore also a
1736:--which are useful in Exposure-Resilient cryptography.
3822:{\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}
2927:
In the proof of this theorem, we need a definition of a
4591:
Randomness extraction is also used in some branches of
4492:{\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}
4728:
4726:
4047:{\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}}
4395:
4325:
4283:
4226:
4138:
4115:
4063:
4008:
3959:
3936:
3916:
3861:
3838:
3767:
3744:
3721:
3691:
3671:
3651:
3631:
3598:
3578:
3558:
3532:
3444:
3421:
3379:
3356:
3330:
3301:
3262:
3217:
3197:
3127:
3092:
3072:
3052:
3026:
2966:
2937:
2881:
2834:
2812:
2740:
2705:
2648:
2606:
2572:
2538:
2466:
2422:
2378:
2354:
2322:
2300:
2217:
2195:
2164:
2142:
2120:
2092:
2070:
2033:
1988:
1864:
1842:
1820:
1798:
1776:
1754:
1607:
1510:
1325:
1225:
1205:
1178:
1121:
1101:
1069:
968:
933:
895:
875:
826:
800:
780:
748:
714:
683:
659:
627:
530:
479:
459:
435:
379:
340:
313:
293:
273:
253:
233:
182:
162:
126:
106:
72:
An extractor has some conceptual similarities with a
3184:{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}
2797:{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}
2523:{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}
2285:{\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}
4645:
Extracting randomness from sampleable distributions
621:be a function that takes as input a sample from an
4491:
4373:
4303:
4232:
4208:
4121:
4098:
4046:
3991:
3942:
3922:
3899:
3844:
3821:
3750:
3727:
3707:
3677:
3657:
3637:
3617:
3584:
3564:
3544:
3515:
3427:
3404:
3362:
3342:
3313:
3287:
3248:
3203:
3183:
3113:
3078:
3058:
3032:
3012:
2952:
2913:
2865:
2818:
2796:
2724:
2676:
2634:
2587:
2556:
2522:
2450:
2384:
2360:
2337:
2306:
2284:
2201:
2179:
2148:
2126:
2104:
2076:
2054:
2003:
1972:
1848:
1826:
1804:
1782:
1760:
1670:
1587:
1433:
1244:
1211:
1191:
1164:
1107:
1087:
1052:
951:
901:
881:
839:
808:
786:
766:
722:
696:
665:
645:
613:
497:
465:
441:
414:
365:
326:
299:
279:
259:
239:
219:
168:
148:
112:
4648:. Portal.acm.org. 12 November 2000. p. 32.
1916:
1870:
1165:{\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}
861:Intuitively, an extractor takes a weakly random
183:
4843:, Barker and Kelsey, August 2012, Section 6.4.2
84:to uniform, in a PRG it is only required to be
3324:The proof of this extractor's existence with
2684:, which satisfies the condition of the APRF.
50:. Examples of weakly random sources include
8:
3172:
3159:
3147:
3134:
2914:{\displaystyle k=n^{{\frac {1}{2}}+\gamma }}
2785:
2772:
2760:
2747:
2511:
2498:
2486:
2473:
1947:
1919:
1910:
1873:
1791:, when a computationally unbounded adversary
1413:
1400:
1379:
1366:
1354:
1341:
1040:
1027:
1015:
1002:
990:
977:
602:
589:
577:
564:
552:
539:
415:{\displaystyle H_{\infty }(U_{\ell })=\ell }
354:
341:
4511:Another approach is to use the output of a
3900:{\displaystyle m=\delta ^{2}n=n^{2\gamma }}
2135:to any fixed values, the probability vector
4674:David K. Gifford, Natural Random Numbers,
4595:and in the construction of list-decodable
3618:{\displaystyle \gamma \leq {\frac {1}{2}}}
2725:{\displaystyle \gamma \leq {\frac {1}{2}}}
4866:
4794:
4776:
4394:
4374:{\displaystyle p\cdot (1-p)=(1-p)\cdot p}
4324:
4293:
4282:
4225:
4194:
4187:
4165:
4158:
4137:
4114:
4084:
4077:
4062:
4029:
4016:
4007:
3992:{\displaystyle \delta ^{2}n=n^{2\gamma }}
3980:
3964:
3958:
3935:
3915:
3888:
3872:
3860:
3837:
3766:
3743:
3720:
3696:
3690:
3670:
3650:
3630:
3605:
3597:
3577:
3557:
3531:
3501:
3461:
3443:
3420:
3390:
3378:
3355:
3329:
3300:
3273:
3261:
3234:
3216:
3196:
3175:
3150:
3126:
3091:
3071:
3051:
3025:
2998:
2989:
2965:
2936:
2893:
2892:
2880:
2851:
2833:
2811:
2788:
2763:
2739:
2712:
2704:
2653:
2647:
2611:
2605:
2571:
2537:
2514:
2489:
2465:
2427:
2421:
2377:
2353:
2321:
2299:
2261:
2249:
2240:
2227:
2218:
2216:
2194:
2163:
2141:
2119:
2091:
2069:
2032:
1987:
1950:
1926:
1880:
1865:
1863:
1841:
1819:
1797:
1775:
1753:
1639:
1606:
1556:
1523:
1509:
1416:
1382:
1357:
1332:
1327:
1324:
1230:
1224:
1204:
1183:
1177:
1153:
1135:
1126:
1120:
1100:
1068:
1049:
1043:
1018:
993:
969:
967:
932:
894:
874:
831:
825:
801:
799:
779:
747:
715:
713:
688:
682:
658:
626:
605:
580:
555:
531:
529:
478:
458:
434:
397:
384:
378:
357:
339:
318:
312:
292:
272:
252:
232:
208:
181:
161:
131:
125:
105:
88:from uniform, a somewhat weaker concept.
4907:Key Derivation and Randomness Extraction
4690:"Extractors and Pseudorandom Generators"
4389:of multiplication, it would follow that
3592:. In the last step we use the fact that
4635:
4258:Perhaps the earliest example is due to
3249:{\displaystyle m=\Omega (\delta ^{2}n)}
2866:{\displaystyle m=\Omega (n^{2\gamma })}
1264:, it can be shown that there exists a (
267:. In essence, this measures how likely
1219:-close to the uniform distribution on
3930:we account for the worst case, where
1699:One of the most important aspects of
1695:Randomness extractors in cryptography
334:denote the uniform distribution over
7:
1464:(in its input length) and for every
1199:denote the same random variable) is
4818:Persohn, Kyle; Povinelli, Richard.
3685:is a positive integer we know that
2960:is defined as being negligible if
2565:oblivious bit-fixing sources, where
4311:More generally, it applies to any
3491:
3476:
3451:
3224:
2841:
2677:{\displaystyle 2^{-m}\epsilon (n)}
2635:{\displaystyle 2^{-m}\epsilon (n)}
2451:{\displaystyle 2^{-m}\epsilon (n)}
2017:Almost-Perfect Resilient Functions
385:
132:
25:
4915:, Jesse Kamp and David Zuckerman
3405:{\displaystyle \epsilon =2^{-cm}}
3288:{\displaystyle \epsilon =2^{-cm}}
2925:Definition (negligible function):
2733:, there exists an explicit k-APRF
86:computationally indistinguishable
4614:Hardware random number generator
2642:-extractor obviously is at most
2596:is negligible, is also a k-APRF.
2315:and for some negligible function
1276:Definition (Explicit Extractor):
959:-strong extractor is a function
4935:Computational complexity theory
4593:computational complexity theory
4109:Which inserted in the value of
3086:is an extractor for the set of
2188:over the random choices for the
1747:An adaptive k-ERF is a function
1310:) a family Ext = {Ext
366:{\displaystyle \{0,1\}^{\ell }}
92:Formal definition of extractors
4486:
4474:
4465:
4459:
4453:
4447:
4438:
4432:
4426:
4420:
4411:
4399:
4362:
4350:
4344:
4332:
4064:
4009:
3804:
3801:
3786:
3780:
3768:
3625:which means that the power of
3510:
3494:
3485:
3479:
3470:
3454:
3243:
3227:
3156:
3108:
3093:
2976:
2970:
2947:
2941:
2860:
2844:
2769:
2671:
2665:
2629:
2623:
2582:
2576:
2551:
2539:
2495:
2445:
2439:
2332:
2326:
2279:
2273:
2250:
2219:
2174:
2168:
2049:
2043:
1998:
1992:
1967:
1961:
1951:
1938:
1932:
1901:
1898:
1892:
1886:
1866:
1665:
1659:
1582:
1576:
1536:
1524:
1426:
1420:
1397:
1392:
1386:
1159:
1140:
1082:
1070:
1024:
946:
934:
925:Definition (Strong Extractor):
761:
749:
640:
628:
586:
492:
480:
403:
390:
220:{\displaystyle \Pr\leq 2^{-k}}
198:
186:
156:), is the largest real number
149:{\displaystyle H_{\infty }(X)}
143:
137:
1:
4551:It is also possible to use a
3545:{\displaystyle \delta \leq 1}
3343:{\displaystyle \delta \leq 1}
3121:oblivious bit-fixing source:
2691:-APRF function as described:
1501:)-extractor with seed length
952:{\displaystyle (k,\epsilon )}
794:, the output distribution of
3708:{\displaystyle n^{2\gamma }}
3114:{\displaystyle (n,\delta n)}
2953:{\displaystyle \epsilon (n)}
2588:{\displaystyle \epsilon (n)}
2338:{\displaystyle \epsilon (n)}
2004:{\displaystyle \epsilon (n)}
1981:for some negligible function
809:{\displaystyle {\text{Ext}}}
723:{\displaystyle {\text{Ext}}}
4553:cryptographic hash function
4547:Cryptographic hash function
1713:Exposure-Resilient Function
4961:
4909:, Olivier Chevassut et al.
4877:10.1103/PhysRevA.87.062327
4269:Thus, it takes as input a
4251:
3832:and by using the value of
3412:is a negligible function.
1813:can adaptively read all of
917:An extractor is strong if
850:In the above definition,
4383:statistically independent
4266:between successive bits.
3066:-extractor: The function
3059:{\displaystyle \epsilon }
2698:For any positive constant
2396:-ERF. More specifically,
2085:where, for any setting of
1769:where, for a random input
1212:{\displaystyle \epsilon }
327:{\displaystyle U_{\ell }}
4945:Random number generation
4940:Cryptographic algorithms
3552:then the lower bound on
2210:remaining bits satisfies
4903:, Yevgeniy Dodis et al.
4541:IEEE 754 Floating-Point
3046:Consider the following
1245:{\displaystyle U_{m+d}}
509:Definition (Extractor):
4921:, Michael Mitzenmacher
4822:. Marquette University
4597:error correcting codes
4493:
4375:
4305:
4304:{\displaystyle p=1/2.}
4234:
4210:
4123:
4100:
4048:
3993:
3944:
3924:
3901:
3846:
3823:
3752:
3729:
3709:
3679:
3659:
3639:
3619:
3586:
3566:
3546:
3517:
3429:
3406:
3364:
3344:
3315:
3314:{\displaystyle c>1}
3289:
3250:
3205:
3185:
3115:
3080:
3060:
3034:
3014:
2954:
2915:
2867:
2820:
2798:
2726:
2678:
2636:
2589:
2558:
2524:
2452:
2386:
2362:
2339:
2308:
2286:
2203:
2181:
2150:
2128:
2106:
2078:
2056:
2055:{\displaystyle k=k(n)}
2005:
1974:
1850:
1828:
1806:
1784:
1762:
1672:
1589:
1435:
1246:
1213:
1193:
1166:
1109:
1089:
1054:
953:
903:
883:
841:
810:
788:
768:
724:
698:
667:
647:
615:
499:
467:
443:
416:
367:
328:
301:
281:
261:
241:
221:
170:
150:
114:
74:pseudorandom generator
4494:
4376:
4313:exchangeable sequence
4306:
4252:Further information:
4248:Von Neumann extractor
4235:
4233:{\displaystyle \Box }
4211:
4124:
4101:
4049:
3994:
3945:
3925:
3902:
3847:
3824:
3753:
3730:
3710:
3680:
3660:
3640:
3620:
3587:
3567:
3547:
3518:
3430:
3407:
3365:
3345:
3316:
3290:
3251:
3206:
3186:
3116:
3081:
3061:
3035:
3015:
2955:
2916:
2868:
2821:
2799:
2727:
2679:
2637:
2590:
2559:
2557:{\displaystyle (n,k)}
2525:
2453:
2387:
2363:
2340:
2309:
2287:
2204:
2182:
2151:
2129:
2107:
2079:
2057:
2006:
1975:
1851:
1829:
1807:
1785:
1763:
1673:
1590:
1460:) can be computed in
1436:
1247:
1214:
1194:
1192:{\displaystyle U_{d}}
1167:
1110:
1090:
1088:{\displaystyle (n,k)}
1055:
954:
904:
884:
842:
840:{\displaystyle U_{m}}
811:
789:
769:
767:{\displaystyle (n,k)}
725:
699:
697:{\displaystyle U_{d}}
668:
648:
646:{\displaystyle (n,k)}
616:
500:
498:{\displaystyle (n,k)}
468:
444:
417:
368:
329:
302:
282:
262:
242:
222:
171:
151:
115:
48:uniformly distributed
18:Von Neumann extractor
4586:quantum cryptography
4393:
4387:commutative property
4323:
4281:
4224:
4136:
4113:
4061:
4006:
3957:
3934:
3914:
3910:Using this value of
3859:
3836:
3765:
3742:
3719:
3689:
3669:
3649:
3629:
3596:
3576:
3556:
3530:
3442:
3419:
3377:
3354:
3328:
3299:
3260:
3215:
3195:
3125:
3090:
3070:
3050:
3024:
2964:
2935:
2879:
2832:
2810:
2738:
2703:
2695:Theorem (existence):
2646:
2604:
2570:
2536:
2464:
2420:
2376:
2352:
2320:
2298:
2215:
2193:
2180:{\displaystyle f(r)}
2162:
2140:
2118:
2090:
2068:
2031:
2023:Definition (k-APRF):
1986:
1862:
1840:
1818:
1796:
1774:
1752:
1605:
1508:
1452:)-extractor, if Ext(
1323:
1262:probabilistic method
1223:
1203:
1176:
1119:
1099:
1067:
1063:such that for every
966:
931:
893:
873:
856:statistical distance
824:
798:
778:
746:
712:
681:
657:
625:
528:
477:
457:
433:
377:
338:
311:
291:
271:
251:
231:
180:
160:
124:
104:
78:hard-core predicates
67:unbiasing algorithms
46:from the source and
42:output that appears
32:randomness extractor
4769:2018Entrp..20..729P
2929:negligible function
2105:{\displaystyle n-k}
1256:Explicit extractors
1172:(the two copies of
82:statistically close
4579:cryptographic hash
4489:
4371:
4301:
4271:Bernoulli sequence
4254:Bernoulli sequence
4230:
4206:
4119:
4096:
4044:
3989:
3940:
3920:
3897:
3842:
3819:
3748:
3725:
3705:
3675:
3655:
3635:
3615:
3582:
3562:
3542:
3513:
3425:
3402:
3360:
3340:
3311:
3285:
3246:
3201:
3181:
3111:
3076:
3056:
3030:
3020:for all constants
3010:
2950:
2911:
2863:
2827:-bit strings, with
2816:
2794:
2722:
2674:
2632:
2585:
2554:
2520:
2448:
2382:
2358:
2335:
2304:
2282:
2199:
2177:
2146:
2124:
2102:
2074:
2063:APRF is a function
2052:
2001:
1970:
1846:
1824:
1802:
1780:
1758:
1709:Exposure-Resilient
1668:
1598:and output length
1585:
1431:
1242:
1209:
1189:
1162:
1105:
1085:
1050:
949:
899:
879:
837:
806:
784:
764:
720:
694:
663:
643:
611:
495:
463:
439:
429:-bit distribution
412:
363:
324:
307:appears. Letting
297:
277:
257:
237:
217:
166:
146:
110:
100:of a distribution
4855:Physical Review A
4778:10.3390/e20100729
4619:Randomness merger
4202:
4173:
4122:{\displaystyle k}
4092:
3943:{\displaystyle k}
3923:{\displaystyle m}
3845:{\displaystyle m}
3751:{\displaystyle k}
3728:{\displaystyle n}
3678:{\displaystyle n}
3658:{\displaystyle 1}
3638:{\displaystyle n}
3613:
3585:{\displaystyle n}
3565:{\displaystyle m}
3428:{\displaystyle m}
3363:{\displaystyle m}
3204:{\displaystyle f}
3079:{\displaystyle f}
3033:{\displaystyle c}
3004:
2901:
2819:{\displaystyle m}
2720:
2385:{\displaystyle f}
2361:{\displaystyle f}
2307:{\displaystyle i}
2202:{\displaystyle k}
2149:{\displaystyle p}
2127:{\displaystyle r}
2113:bits of the input
2077:{\displaystyle f}
2011:(defined below).
1849:{\displaystyle k}
1827:{\displaystyle r}
1805:{\displaystyle A}
1783:{\displaystyle r}
1761:{\displaystyle f}
1647:
1564:
1330:
1138:
1115:the distribution
1108:{\displaystyle X}
972:
913:Strong extractors
902:{\displaystyle m}
882:{\displaystyle d}
854:-close refers to
804:
787:{\displaystyle X}
718:
704:, and outputs an
666:{\displaystyle X}
534:
466:{\displaystyle X}
449:with min-entropy
442:{\displaystyle X}
300:{\displaystyle X}
280:{\displaystyle X}
260:{\displaystyle X}
240:{\displaystyle x}
169:{\displaystyle k}
113:{\displaystyle X}
52:radioactive decay
16:(Redirected from
4952:
4897:, Ronen Shaltiel
4881:
4880:
4870:
4850:
4844:
4838:
4832:
4831:
4829:
4827:
4815:
4809:
4808:
4798:
4780:
4748:
4742:
4739:
4733:
4730:
4721:
4718:
4712:
4709:
4703:
4702:
4700:
4699:
4694:
4685:
4679:
4672:
4666:
4665:
4663:
4662:
4640:
4498:
4496:
4495:
4490:
4385:and due to the
4380:
4378:
4377:
4372:
4310:
4308:
4307:
4302:
4297:
4276:
4260:John von Neumann
4239:
4237:
4236:
4231:
4215:
4213:
4212:
4207:
4205:
4204:
4203:
4195:
4176:
4175:
4174:
4166:
4128:
4126:
4125:
4120:
4105:
4103:
4102:
4097:
4095:
4094:
4093:
4085:
4053:
4051:
4050:
4045:
4043:
4042:
4021:
4020:
3998:
3996:
3995:
3990:
3988:
3987:
3969:
3968:
3949:
3947:
3946:
3941:
3929:
3927:
3926:
3921:
3906:
3904:
3903:
3898:
3896:
3895:
3877:
3876:
3851:
3849:
3848:
3843:
3828:
3826:
3825:
3820:
3757:
3755:
3754:
3749:
3734:
3732:
3731:
3726:
3714:
3712:
3711:
3706:
3704:
3703:
3684:
3682:
3681:
3676:
3664:
3662:
3661:
3656:
3644:
3642:
3641:
3636:
3624:
3622:
3621:
3616:
3614:
3606:
3591:
3589:
3588:
3583:
3572:is dominated by
3571:
3569:
3568:
3563:
3551:
3549:
3548:
3543:
3522:
3520:
3519:
3514:
3509:
3508:
3466:
3465:
3434:
3432:
3431:
3426:
3411:
3409:
3408:
3403:
3401:
3400:
3369:
3367:
3366:
3361:
3349:
3347:
3346:
3341:
3320:
3318:
3317:
3312:
3294:
3292:
3291:
3286:
3284:
3283:
3255:
3253:
3252:
3247:
3239:
3238:
3210:
3208:
3207:
3202:
3190:
3188:
3187:
3182:
3180:
3179:
3155:
3154:
3120:
3118:
3117:
3112:
3085:
3083:
3082:
3077:
3065:
3063:
3062:
3057:
3039:
3037:
3036:
3031:
3019:
3017:
3016:
3011:
3009:
3005:
3003:
3002:
2990:
2959:
2957:
2956:
2951:
2920:
2918:
2917:
2912:
2910:
2909:
2902:
2894:
2872:
2870:
2869:
2864:
2859:
2858:
2825:
2823:
2822:
2817:
2803:
2801:
2800:
2795:
2793:
2792:
2768:
2767:
2731:
2729:
2728:
2723:
2721:
2713:
2683:
2681:
2680:
2675:
2661:
2660:
2641:
2639:
2638:
2633:
2619:
2618:
2594:
2592:
2591:
2586:
2563:
2561:
2560:
2555:
2529:
2527:
2526:
2521:
2519:
2518:
2494:
2493:
2457:
2455:
2454:
2449:
2435:
2434:
2391:
2389:
2388:
2383:
2367:
2365:
2364:
2359:
2344:
2342:
2341:
2336:
2313:
2311:
2310:
2305:
2291:
2289:
2288:
2283:
2269:
2268:
2253:
2248:
2247:
2232:
2231:
2222:
2208:
2206:
2205:
2200:
2186:
2184:
2183:
2178:
2155:
2153:
2152:
2147:
2133:
2131:
2130:
2125:
2111:
2109:
2108:
2103:
2083:
2081:
2080:
2075:
2061:
2059:
2058:
2053:
2010:
2008:
2007:
2002:
1979:
1977:
1976:
1971:
1954:
1931:
1930:
1885:
1884:
1869:
1855:
1853:
1852:
1847:
1833:
1831:
1830:
1825:
1811:
1809:
1808:
1803:
1789:
1787:
1786:
1781:
1767:
1765:
1764:
1759:
1677:
1675:
1674:
1669:
1652:
1648:
1640:
1594:
1592:
1591:
1586:
1569:
1565:
1557:
1539:
1444:is an explicit (
1440:
1438:
1437:
1432:
1430:
1429:
1396:
1395:
1362:
1361:
1337:
1336:
1331:
1328:
1251:
1249:
1248:
1243:
1241:
1240:
1218:
1216:
1215:
1210:
1198:
1196:
1195:
1190:
1188:
1187:
1171:
1169:
1168:
1163:
1158:
1157:
1139:
1136:
1131:
1130:
1114:
1112:
1111:
1106:
1094:
1092:
1091:
1086:
1059:
1057:
1056:
1051:
1048:
1047:
1023:
1022:
998:
997:
973:
970:
958:
956:
955:
950:
908:
906:
905:
900:
888:
886:
885:
880:
846:
844:
843:
838:
836:
835:
815:
813:
812:
807:
805:
802:
793:
791:
790:
785:
773:
771:
770:
765:
729:
727:
726:
721:
719:
716:
703:
701:
700:
695:
693:
692:
672:
670:
669:
664:
652:
650:
649:
644:
620:
618:
617:
612:
610:
609:
585:
584:
560:
559:
535:
532:
504:
502:
501:
496:
472:
470:
469:
464:
448:
446:
445:
440:
421:
419:
418:
413:
402:
401:
389:
388:
372:
370:
369:
364:
362:
361:
333:
331:
330:
325:
323:
322:
306:
304:
303:
298:
286:
284:
283:
278:
266:
264:
263:
258:
247:in the range of
246:
244:
243:
238:
226:
224:
223:
218:
216:
215:
175:
173:
172:
167:
155:
153:
152:
147:
136:
135:
119:
117:
116:
111:
21:
4960:
4959:
4955:
4954:
4953:
4951:
4950:
4949:
4925:
4924:
4885:
4884:
4852:
4851:
4847:
4839:
4835:
4825:
4823:
4817:
4816:
4812:
4750:
4749:
4745:
4740:
4736:
4731:
4724:
4719:
4715:
4710:
4706:
4697:
4695:
4692:
4688:Luca Trevisan.
4687:
4686:
4682:
4673:
4669:
4660:
4658:
4656:
4642:
4641:
4637:
4632:
4624:Fuzzy extractor
4605:
4575:
4549:
4529:memory required
4521:entropy sources
4517:chaotic systems
4509:
4391:
4390:
4321:
4320:
4279:
4278:
4274:
4256:
4250:
4245:
4222:
4221:
4183:
4154:
4134:
4133:
4111:
4110:
4073:
4059:
4058:
4025:
4012:
4004:
4003:
3976:
3960:
3955:
3954:
3932:
3931:
3912:
3911:
3884:
3868:
3857:
3856:
3834:
3833:
3763:
3762:
3740:
3739:
3717:
3716:
3692:
3687:
3686:
3667:
3666:
3647:
3646:
3627:
3626:
3594:
3593:
3574:
3573:
3554:
3553:
3528:
3527:
3497:
3457:
3440:
3439:
3417:
3416:
3386:
3375:
3374:
3352:
3351:
3326:
3325:
3297:
3296:
3269:
3258:
3257:
3230:
3213:
3212:
3193:
3192:
3171:
3146:
3123:
3122:
3088:
3087:
3068:
3067:
3048:
3047:
3022:
3021:
2994:
2985:
2962:
2961:
2933:
2932:
2888:
2877:
2876:
2847:
2830:
2829:
2808:
2807:
2784:
2759:
2736:
2735:
2701:
2700:
2649:
2644:
2643:
2607:
2602:
2601:
2568:
2567:
2534:
2533:
2510:
2485:
2462:
2461:
2423:
2418:
2417:
2374:
2373:
2350:
2349:
2318:
2317:
2296:
2295:
2257:
2236:
2223:
2213:
2212:
2191:
2190:
2160:
2159:
2138:
2137:
2116:
2115:
2088:
2087:
2066:
2065:
2029:
2028:
1984:
1983:
1922:
1876:
1860:
1859:
1838:
1837:
1816:
1815:
1794:
1793:
1772:
1771:
1750:
1749:
1697:
1685:
1635:
1603:
1602:
1552:
1506:
1505:
1473:
1462:polynomial time
1412:
1378:
1353:
1326:
1321:
1320:
1316:} of functions
1315:
1258:
1226:
1221:
1220:
1201:
1200:
1179:
1174:
1173:
1149:
1122:
1117:
1116:
1097:
1096:
1065:
1064:
1039:
1014:
989:
964:
963:
929:
928:
915:
891:
890:
871:
870:
827:
822:
821:
796:
795:
776:
775:
744:
743:
710:
709:
684:
679:
678:
677:-bit seed from
655:
654:
623:
622:
601:
576:
551:
526:
525:
475:
474:
455:
454:
431:
430:
393:
380:
375:
374:
353:
336:
335:
314:
309:
308:
289:
288:
269:
268:
249:
248:
229:
228:
204:
178:
177:
158:
157:
127:
122:
121:
102:
101:
94:
28:
27:Physics concept
23:
22:
15:
12:
11:
5:
4958:
4956:
4948:
4947:
4942:
4937:
4927:
4926:
4923:
4922:
4916:
4910:
4904:
4898:
4892:
4883:
4882:
4845:
4833:
4810:
4743:
4734:
4722:
4713:
4704:
4680:
4667:
4654:
4634:
4633:
4631:
4628:
4627:
4626:
4621:
4616:
4611:
4604:
4601:
4574:
4571:
4548:
4545:
4508:
4505:
4488:
4485:
4482:
4479:
4476:
4473:
4470:
4467:
4464:
4461:
4458:
4455:
4452:
4449:
4446:
4443:
4440:
4437:
4434:
4431:
4428:
4425:
4422:
4419:
4416:
4413:
4410:
4407:
4404:
4401:
4398:
4370:
4367:
4364:
4361:
4358:
4355:
4352:
4349:
4346:
4343:
4340:
4337:
4334:
4331:
4328:
4300:
4296:
4292:
4289:
4286:
4249:
4246:
4244:
4241:
4229:
4218:
4217:
4201:
4198:
4193:
4190:
4186:
4182:
4179:
4172:
4169:
4164:
4161:
4157:
4153:
4150:
4147:
4144:
4141:
4118:
4107:
4106:
4091:
4088:
4083:
4080:
4076:
4072:
4069:
4066:
4055:
4054:
4041:
4038:
4035:
4032:
4028:
4024:
4019:
4015:
4011:
4000:
3999:
3986:
3983:
3979:
3975:
3972:
3967:
3963:
3939:
3919:
3908:
3907:
3894:
3891:
3887:
3883:
3880:
3875:
3871:
3867:
3864:
3841:
3830:
3829:
3818:
3815:
3812:
3809:
3806:
3803:
3800:
3797:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3773:
3770:
3747:
3724:
3702:
3699:
3695:
3674:
3654:
3634:
3612:
3609:
3604:
3601:
3581:
3561:
3541:
3538:
3535:
3526:Since we know
3524:
3523:
3512:
3507:
3504:
3500:
3496:
3493:
3490:
3487:
3484:
3481:
3478:
3475:
3472:
3469:
3464:
3460:
3456:
3453:
3450:
3447:
3424:
3399:
3396:
3393:
3389:
3385:
3382:
3359:
3339:
3336:
3333:
3310:
3307:
3304:
3282:
3279:
3276:
3272:
3268:
3265:
3245:
3242:
3237:
3233:
3229:
3226:
3223:
3220:
3200:
3178:
3174:
3170:
3167:
3164:
3161:
3158:
3153:
3149:
3145:
3142:
3139:
3136:
3133:
3130:
3110:
3107:
3104:
3101:
3098:
3095:
3075:
3055:
3029:
3008:
3001:
2997:
2993:
2988:
2984:
2981:
2978:
2975:
2972:
2969:
2949:
2946:
2943:
2940:
2908:
2905:
2900:
2897:
2891:
2887:
2884:
2862:
2857:
2854:
2850:
2846:
2843:
2840:
2837:
2815:
2791:
2787:
2783:
2780:
2777:
2774:
2771:
2766:
2762:
2758:
2755:
2752:
2749:
2746:
2743:
2719:
2716:
2711:
2708:
2673:
2670:
2667:
2664:
2659:
2656:
2652:
2631:
2628:
2625:
2622:
2617:
2614:
2610:
2584:
2581:
2578:
2575:
2553:
2550:
2547:
2544:
2541:
2531:for the set of
2517:
2513:
2509:
2506:
2503:
2500:
2497:
2492:
2488:
2484:
2481:
2478:
2475:
2472:
2469:
2447:
2444:
2441:
2438:
2433:
2430:
2426:
2381:
2357:
2334:
2331:
2328:
2325:
2303:
2281:
2278:
2275:
2272:
2267:
2264:
2260:
2256:
2252:
2246:
2243:
2239:
2235:
2230:
2226:
2221:
2198:
2176:
2173:
2170:
2167:
2145:
2123:
2101:
2098:
2095:
2073:
2051:
2048:
2045:
2042:
2039:
2036:
2000:
1997:
1994:
1991:
1969:
1966:
1963:
1960:
1957:
1953:
1949:
1946:
1943:
1940:
1937:
1934:
1929:
1925:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1883:
1879:
1875:
1872:
1868:
1845:
1823:
1801:
1779:
1757:
1705:key generation
1696:
1693:
1684:
1681:
1680:
1679:
1667:
1664:
1661:
1658:
1655:
1651:
1646:
1643:
1638:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1596:
1595:
1584:
1581:
1578:
1575:
1572:
1568:
1563:
1560:
1555:
1551:
1548:
1545:
1542:
1538:
1535:
1532:
1529:
1526:
1522:
1519:
1516:
1513:
1490:))-extractor.
1469:
1442:
1441:
1428:
1425:
1422:
1419:
1415:
1411:
1408:
1405:
1402:
1399:
1394:
1391:
1388:
1385:
1381:
1377:
1374:
1371:
1368:
1365:
1360:
1356:
1352:
1349:
1346:
1343:
1340:
1335:
1311:
1278:For functions
1257:
1254:
1239:
1236:
1233:
1229:
1208:
1186:
1182:
1161:
1156:
1152:
1148:
1145:
1142:
1134:
1129:
1125:
1104:
1084:
1081:
1078:
1075:
1072:
1061:
1060:
1046:
1042:
1038:
1035:
1032:
1029:
1026:
1021:
1017:
1013:
1010:
1007:
1004:
1001:
996:
992:
988:
985:
982:
979:
976:
948:
945:
942:
939:
936:
914:
911:
898:
878:
834:
830:
783:
774:distributions
763:
760:
757:
754:
751:
691:
687:
662:
642:
639:
636:
633:
630:
608:
604:
600:
597:
594:
591:
588:
583:
579:
575:
572:
569:
566:
563:
558:
554:
550:
547:
544:
541:
538:
505:distribution.
494:
491:
488:
485:
482:
462:
453:, we say that
438:
411:
408:
405:
400:
396:
392:
387:
383:
360:
356:
352:
349:
346:
343:
321:
317:
296:
276:
256:
236:
214:
211:
207:
203:
200:
197:
194:
191:
188:
185:
165:
145:
142:
139:
134:
130:
109:
93:
90:
36:entropy source
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4957:
4946:
4943:
4941:
4938:
4936:
4933:
4932:
4930:
4920:
4917:
4914:
4911:
4908:
4905:
4902:
4899:
4896:
4893:
4890:
4887:
4886:
4878:
4874:
4869:
4864:
4860:
4856:
4849:
4846:
4842:
4837:
4834:
4821:
4814:
4811:
4806:
4802:
4797:
4792:
4788:
4784:
4779:
4774:
4770:
4766:
4762:
4758:
4754:
4747:
4744:
4738:
4735:
4729:
4727:
4723:
4717:
4714:
4708:
4705:
4691:
4684:
4681:
4677:
4671:
4668:
4657:
4655:9780769508504
4651:
4647:
4646:
4639:
4636:
4629:
4625:
4622:
4620:
4617:
4615:
4612:
4610:
4609:Decorrelation
4607:
4606:
4602:
4600:
4598:
4594:
4589:
4587:
4582:
4580:
4572:
4570:
4568:
4564:
4560:
4556:
4554:
4546:
4544:
4542:
4536:
4534:
4530:
4526:
4522:
4518:
4514:
4513:chaos machine
4507:Chaos machine
4506:
4504:
4500:
4483:
4480:
4477:
4471:
4468:
4462:
4456:
4450:
4444:
4441:
4435:
4429:
4423:
4417:
4414:
4408:
4405:
4402:
4396:
4388:
4384:
4368:
4365:
4359:
4356:
4353:
4347:
4341:
4338:
4335:
4329:
4326:
4318:
4314:
4298:
4294:
4290:
4287:
4284:
4272:
4267:
4265:
4261:
4255:
4247:
4242:
4240:
4227:
4199:
4196:
4191:
4188:
4184:
4180:
4177:
4170:
4167:
4162:
4159:
4155:
4151:
4148:
4145:
4142:
4139:
4132:
4131:
4130:
4116:
4089:
4086:
4081:
4078:
4074:
4070:
4067:
4057:
4056:
4039:
4036:
4033:
4030:
4026:
4022:
4017:
4013:
4002:
4001:
3984:
3981:
3977:
3973:
3970:
3965:
3961:
3953:
3952:
3951:
3937:
3917:
3892:
3889:
3885:
3881:
3878:
3873:
3869:
3865:
3862:
3855:
3854:
3853:
3839:
3816:
3813:
3810:
3807:
3798:
3795:
3792:
3789:
3783:
3777:
3774:
3771:
3761:
3760:
3759:
3745:
3738:The value of
3736:
3722:
3700:
3697:
3693:
3672:
3652:
3632:
3610:
3607:
3602:
3599:
3579:
3559:
3539:
3536:
3533:
3505:
3502:
3498:
3488:
3482:
3473:
3467:
3462:
3458:
3448:
3445:
3438:
3437:
3436:
3422:
3413:
3397:
3394:
3391:
3387:
3383:
3380:
3371:
3357:
3337:
3334:
3331:
3322:
3308:
3305:
3302:
3280:
3277:
3274:
3270:
3266:
3263:
3240:
3235:
3231:
3221:
3218:
3198:
3176:
3168:
3165:
3162:
3151:
3143:
3140:
3137:
3131:
3128:
3105:
3102:
3099:
3096:
3073:
3053:
3045:
3041:
3027:
3006:
2999:
2995:
2991:
2986:
2982:
2979:
2973:
2967:
2944:
2938:
2931:. A function
2930:
2926:
2922:
2906:
2903:
2898:
2895:
2889:
2885:
2882:
2875:
2855:
2852:
2848:
2838:
2835:
2828:
2813:
2806:
2789:
2781:
2778:
2775:
2764:
2756:
2753:
2750:
2744:
2741:
2734:
2717:
2714:
2709:
2706:
2699:
2696:
2692:
2690:
2685:
2668:
2662:
2657:
2654:
2650:
2626:
2620:
2615:
2612:
2608:
2598:
2597:
2579:
2573:
2566:
2548:
2545:
2542:
2532:
2515:
2507:
2504:
2501:
2490:
2482:
2479:
2476:
2470:
2467:
2460:
2442:
2436:
2431:
2428:
2424:
2416:
2413:
2409:
2407:
2403:
2399:
2395:
2379:
2371:
2355:
2346:
2329:
2323:
2316:
2301:
2294:
2276:
2270:
2265:
2262:
2258:
2254:
2244:
2241:
2237:
2233:
2228:
2224:
2211:
2196:
2189:
2171:
2165:
2158:
2157:of the output
2143:
2136:
2121:
2114:
2099:
2096:
2093:
2086:
2071:
2064:
2046:
2040:
2037:
2034:
2027:
2024:
2020:
2018:
2012:
1995:
1989:
1982:
1964:
1958:
1955:
1944:
1941:
1935:
1927:
1923:
1913:
1907:
1904:
1895:
1889:
1881:
1877:
1858:
1843:
1836:
1821:
1814:
1799:
1792:
1777:
1770:
1755:
1748:
1745:
1743:
1737:
1735:
1733:
1728:
1726:
1720:
1718:
1714:
1710:
1706:
1702:
1694:
1692:
1690:
1682:
1662:
1656:
1653:
1649:
1644:
1641:
1636:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1601:
1600:
1599:
1579:
1573:
1570:
1566:
1561:
1558:
1553:
1549:
1546:
1543:
1540:
1533:
1530:
1527:
1520:
1517:
1514:
1511:
1504:
1503:
1502:
1500:
1496:
1491:
1489:
1485:
1481:
1477:
1472:
1467:
1463:
1459:
1455:
1451:
1447:
1423:
1417:
1409:
1406:
1403:
1389:
1383:
1375:
1372:
1369:
1363:
1358:
1350:
1347:
1344:
1338:
1333:
1319:
1318:
1317:
1314:
1309:
1305:
1301:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1271:
1267:
1263:
1255:
1253:
1237:
1234:
1231:
1227:
1206:
1184:
1180:
1154:
1150:
1146:
1143:
1132:
1127:
1123:
1102:
1095:distribution
1079:
1076:
1073:
1044:
1036:
1033:
1030:
1019:
1011:
1008:
1005:
999:
994:
986:
983:
980:
974:
962:
961:
960:
943:
940:
937:
926:
922:
920:
919:concatenating
912:
910:
896:
876:
868:
864:
859:
857:
853:
848:
832:
828:
819:
781:
758:
755:
752:
742:, if for all
741:
739:
735:
708:-bit string.
707:
689:
685:
676:
660:
653:distribution
637:
634:
631:
606:
598:
595:
592:
581:
573:
570:
567:
561:
556:
548:
545:
542:
536:
522:
521:
519:
515:
510:
506:
489:
486:
483:
460:
452:
436:
428:
423:
409:
406:
398:
394:
381:
358:
350:
347:
344:
319:
315:
294:
274:
254:
234:
212:
209:
205:
201:
195:
192:
189:
163:
140:
128:
107:
99:
91:
89:
87:
83:
79:
75:
70:
68:
63:
61:
57:
56:thermal noise
53:
49:
45:
41:
37:
33:
19:
4858:
4854:
4848:
4836:
4824:. Retrieved
4813:
4760:
4756:
4746:
4737:
4716:
4707:
4696:. Retrieved
4683:
4670:
4659:. Retrieved
4644:
4638:
4590:
4583:
4576:
4573:Applications
4567:full entropy
4557:
4550:
4537:
4532:
4528:
4524:
4510:
4501:
4316:
4268:
4257:
4219:
4108:
3909:
3831:
3737:
3665:. And since
3525:
3415:The size of
3414:
3372:
3323:
3043:
3042:
2924:
2923:
2873:
2826:
2804:
2732:
2697:
2694:
2693:
2688:
2686:
2599:
2595:
2564:
2530:
2458:
2414:
2411:
2410:
2405:
2401:
2397:
2393:
2372:-APRF, then
2369:
2347:
2314:
2292:
2209:
2187:
2156:
2134:
2112:
2084:
2062:
2025:
2022:
2021:
2016:
2013:
1980:
1856:
1834:
1812:
1790:
1768:
1746:
1741:
1740:Definition (
1739:
1738:
1731:
1730:
1724:
1723:
1721:
1712:
1708:
1701:cryptography
1698:
1686:
1597:
1498:
1494:
1492:
1487:
1483:
1479:
1475:
1470:
1465:
1457:
1453:
1449:
1445:
1443:
1312:
1307:
1303:
1299:
1295:
1291:
1287:
1283:
1279:
1275:
1274:
1269:
1265:
1259:
1062:
924:
923:
916:
866:
862:
860:
851:
849:
817:
737:
733:
731:
705:
674:
523:
517:
513:
511:
508:
507:
450:
426:
424:
95:
71:
66:
64:
31:
29:
4763:(10): 729.
4264:correlation
3715:is at most
3645:is at most
740:)-extractor
520:)-extractor
373:, clearly
98:min-entropy
44:independent
4929:Categories
4891:, Anup Rao
4698:2013-10-21
4661:2012-06-12
4630:References
4533:secret key
2459:-extractor
2392:is also a
1835:except for
1717:encryption
1703:is random
1683:Dispersers
1260:Using the
820:-close to
227:for every
176:such that
4868:1207.1473
4826:3 January
4787:1099-4300
4525:time cost
4481:∩
4406:∩
4366:⋅
4357:−
4339:−
4330:⋅
4228:◻
4189:γ
4163:−
4160:γ
4146:δ
4082:−
4079:γ
4068:δ
4065:⇒
4037:−
4034:γ
4014:δ
4010:⇒
3985:γ
3962:δ
3893:γ
3870:δ
3852:we have:
3814:δ
3805:⇒
3796:δ
3701:γ
3603:≤
3600:γ
3537:≤
3534:δ
3506:γ
3492:Ω
3489:≥
3477:Ω
3459:δ
3452:Ω
3392:−
3381:ϵ
3335:≤
3332:δ
3275:−
3264:ϵ
3232:δ
3225:Ω
3157:→
3103:δ
3054:ϵ
2968:ϵ
2939:ϵ
2907:γ
2856:γ
2842:Ω
2770:→
2710:≤
2707:γ
2663:ϵ
2655:−
2621:ϵ
2613:−
2574:ϵ
2496:→
2437:ϵ
2429:−
2402:oblivious
2324:ϵ
2271:ϵ
2263:−
2242:−
2234:−
2097:−
1990:ϵ
1959:ϵ
1956:≤
1914:−
1689:disperser
1654:−
1645:ε
1633:
1624:−
1562:ε
1550:
1531:−
1521:
1398:→
1364:×
1207:ϵ
1133:∘
1025:→
1000:×
944:ϵ
587:→
562:×
410:ℓ
399:ℓ
386:∞
359:ℓ
320:ℓ
210:−
202:≤
133:∞
120:(denoted
4805:33265818
4603:See also
4243:Examples
1482:),
4796:7512292
4765:Bibcode
4757:Entropy
4317:equally
2293:for all
1497:,
1456:,
1448:,
1268:,
736:,
516:,
425:For an
4803:
4793:
4785:
4652:
4531:, and
4129:gives
3044:Proof:
2412:Lemma:
1744:-ERF):
1474:is a (
673:and a
473:is an
40:random
4863:arXiv
4861:(6).
4693:(PDF)
4273:with
2368:is a
1857:bits,
1734:-APRF
1468:, Ext
730:is a
4828:2024
4801:PMID
4783:ISSN
4650:ISBN
4559:NIST
3435:is:
3306:>
3295:and
3211:has
2255:<
1729:and
1727:-ERF
524:Let
96:The
60:TRNG
4873:doi
4791:PMC
4773:doi
4676:MIT
4563:SHA
2874:and
2415:Any
2398:any
1630:log
1547:log
1518:log
1329:Ext
1302:),
1294:),
1286:),
1137:Ext
971:Ext
816:is
803:Ext
717:Ext
533:Ext
54:or
4931::
4871:.
4859:87
4857:.
4799:.
4789:.
4781:.
4771:.
4761:20
4759:.
4755:.
4725:^
4599:.
4569:.
4535:.
4527:,
4299:2.
3735:.
3321:.
3256:,
3191:.
3040:.
2921:.
2345:.
1917:Pr
1871:Pr
1691:.
1252:.
927:A
858:.
847:.
422:.
184:Pr
30:A
4879:.
4875::
4865::
4830:.
4807:.
4775::
4767::
4701:.
4664:.
4487:)
4484:A
4478:B
4475:(
4472:P
4469:=
4466:)
4463:A
4460:(
4457:P
4454:)
4451:B
4448:(
4445:P
4442:=
4439:)
4436:B
4433:(
4430:P
4427:)
4424:A
4421:(
4418:P
4415:=
4412:)
4409:B
4403:A
4400:(
4397:P
4369:p
4363:)
4360:p
4354:1
4351:(
4348:=
4345:)
4342:p
4336:1
4333:(
4327:p
4295:/
4291:1
4288:=
4285:p
4275:p
4216:,
4200:2
4197:1
4192:+
4185:n
4181:=
4178:n
4171:2
4168:1
4156:n
4152:=
4149:n
4143:=
4140:k
4117:k
4090:2
4087:1
4075:n
4071:=
4040:1
4031:2
4027:n
4023:=
4018:2
3982:2
3978:n
3974:=
3971:n
3966:2
3938:k
3918:m
3890:2
3886:n
3882:=
3879:n
3874:2
3866:=
3863:m
3840:m
3817:n
3811:=
3808:k
3802:)
3799:n
3793:,
3790:n
3787:(
3784:=
3781:)
3778:k
3775:,
3772:n
3769:(
3746:k
3723:n
3698:2
3694:n
3673:n
3653:1
3633:n
3611:2
3608:1
3580:n
3560:m
3540:1
3511:)
3503:2
3499:n
3495:(
3486:)
3483:n
3480:(
3474:=
3471:)
3468:n
3463:2
3455:(
3449:=
3446:m
3423:m
3398:m
3395:c
3388:2
3384:=
3358:m
3338:1
3309:1
3303:c
3281:m
3278:c
3271:2
3267:=
3244:)
3241:n
3236:2
3228:(
3222:=
3219:m
3199:f
3177:m
3173:}
3169:1
3166:,
3163:0
3160:{
3152:n
3148:}
3144:1
3141:,
3138:0
3135:{
3132::
3129:f
3109:)
3106:n
3100:,
3097:n
3094:(
3074:f
3028:c
3007:)
3000:c
2996:n
2992:1
2987:(
2983:O
2980:=
2977:)
2974:n
2971:(
2948:)
2945:n
2942:(
2904:+
2899:2
2896:1
2890:n
2886:=
2883:k
2861:)
2853:2
2849:n
2845:(
2839:=
2836:m
2814:m
2790:m
2786:}
2782:1
2779:,
2776:0
2773:{
2765:n
2761:}
2757:1
2754:,
2751:0
2748:{
2745::
2742:f
2718:2
2715:1
2689:k
2672:)
2669:n
2666:(
2658:m
2651:2
2630:)
2627:n
2624:(
2616:m
2609:2
2583:)
2580:n
2577:(
2552:)
2549:k
2546:,
2543:n
2540:(
2516:m
2512:}
2508:1
2505:,
2502:0
2499:{
2491:n
2487:}
2483:1
2480:,
2477:0
2474:{
2471::
2468:f
2446:)
2443:n
2440:(
2432:m
2425:2
2406:k
2394:k
2380:f
2370:k
2356:f
2333:)
2330:n
2327:(
2302:i
2280:)
2277:n
2274:(
2266:m
2259:2
2251:|
2245:m
2238:2
2229:i
2225:p
2220:|
2197:k
2175:)
2172:r
2169:(
2166:f
2144:p
2122:r
2100:k
2094:n
2072:f
2050:)
2047:n
2044:(
2041:k
2038:=
2035:k
2026:A
1999:)
1996:n
1993:(
1968:)
1965:n
1962:(
1952:|
1948:}
1945:1
1942:=
1939:)
1936:R
1933:(
1928:r
1924:A
1920:{
1911:}
1908:1
1905:=
1902:)
1899:)
1896:r
1893:(
1890:f
1887:(
1882:r
1878:A
1874:{
1867:|
1844:k
1822:r
1800:A
1778:r
1756:f
1742:k
1732:k
1725:k
1678:.
1666:)
1663:1
1660:(
1657:O
1650:)
1642:1
1637:(
1627:2
1621:d
1618:+
1615:k
1612:=
1609:m
1583:)
1580:1
1577:(
1574:O
1571:+
1567:)
1559:1
1554:(
1544:2
1541:+
1537:)
1534:k
1528:n
1525:(
1515:=
1512:d
1499:ε
1495:k
1488:n
1486:(
1484:ε
1480:n
1478:(
1476:k
1471:n
1466:n
1458:y
1454:x
1450:ε
1446:k
1427:)
1424:n
1421:(
1418:m
1414:}
1410:1
1407:,
1404:0
1401:{
1393:)
1390:n
1387:(
1384:d
1380:}
1376:1
1373:,
1370:0
1367:{
1359:n
1355:}
1351:1
1348:,
1345:0
1342:{
1339::
1334:n
1313:n
1308:n
1306:(
1304:m
1300:n
1298:(
1296:d
1292:n
1290:(
1288:ε
1284:n
1282:(
1280:k
1270:ε
1266:k
1238:d
1235:+
1232:m
1228:U
1185:d
1181:U
1160:)
1155:d
1151:U
1147:,
1144:X
1141:(
1128:d
1124:U
1103:X
1083:)
1080:k
1077:,
1074:n
1071:(
1045:m
1041:}
1037:1
1034:,
1031:0
1028:{
1020:d
1016:}
1012:1
1009:,
1006:0
1003:{
995:n
991:}
987:1
984:,
981:0
978:{
975::
947:)
941:,
938:k
935:(
897:m
877:d
867:m
863:n
852:ε
833:m
829:U
818:ε
782:X
762:)
759:k
756:,
753:n
750:(
738:ε
734:k
732:(
706:m
690:d
686:U
675:d
661:X
641:)
638:k
635:,
632:n
629:(
607:m
603:}
599:1
596:,
593:0
590:{
582:d
578:}
574:1
571:,
568:0
565:{
557:n
553:}
549:1
546:,
543:0
540:{
537::
518:ε
514:k
512:(
493:)
490:k
487:,
484:n
481:(
461:X
451:k
437:X
427:n
407:=
404:)
395:U
391:(
382:H
355:}
351:1
348:,
345:0
342:{
316:U
295:X
275:X
255:X
235:x
213:k
206:2
199:]
196:x
193:=
190:X
187:[
164:k
144:)
141:X
138:(
129:H
108:X
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.