Randomness extractor (original) (raw)
A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; 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 (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.
| Property | Value |
|---|---|
| dbo:abstract | A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; 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 (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source. Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called unbiasing algorithms, 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. Note that an extractor has some conceptual similarities with a pseudorandom generator (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 hard-core predicates, 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 statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept. NIST Special Publication 800-90B (draft) recommends several extractors, including the SHA hash family and states that if the amount of entropy input is twice the number of bits output from them, that output can be considered essentially fully random. (en) Экстрактор случайности — функция, которая применяется к выходу из слабо случайного источника энтропии, вместе с коротким равномерно распределённым случайным начальным значением (англ. seed) и генерирует случайный выход, который выглядит независимым от источника и равномерно распределён. Несмотря на то, что экстрактор имеет некоторые концептуальные сходства с генератором псевдослучайных чисел, это различные понятия. Оба алгоритма принимают в качестве входных данных небольшое равномерно случайное начальное число и выдают более длинное случайное, которое «выглядит» равномерно случайным. Некоторые псевдослучайные генераторы также являются экстракторами. (Когда генератор псевдослучайных чисел основан на существовании трудных битов, можно считать слабо случайный источник набором таблиц истинности таких предикатов и доказать, что выходные данные статистически близки к однородным). Хотя в формальном определении псевдослучайного генератора не указывается, что должен использоваться слабо случайный источник, и в случае экстрактора выходные данные должны быть к однородным, в ГПЧ требуется только то, чтоб они были от равномерных, что является более слабым требованием. (ru) |
| dbo:wikiPageExternalLink | http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps http://people.csail.mit.edu/dodis/ps/hmac.ps http://www.cs.utexas.edu/users/diz/pubs/erf.pdf http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf http://newsroom.spie.org/x4741.xml%3Fhighlight=x535 http://eprint.iacr.org/2005/061.pdf http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf |
| dbo:wikiPageID | 18362292 (xsd:integer) |
| dbo:wikiPageLength | 17845 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 959313511 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_method dbr:Encryption dbr:Entropy_(computing) dbr:Randomness_merger dbr:Total_variation_distance dbr:John_von_Neumann dbr:Decorrelation dbr:Pseudorandom_generator dbc:Random_number_generation dbr:Computationally_indistinguishable dbr:Concatenation dbr:Correlation dbr:Cryptographic_hash_function dbr:Cryptography dbr:Fuzzy_extractor dbr:NIST dbr:Min-entropy dbr:Computational_complexity_theory dbr:Hardware_random_number_generator dbr:Key_generation dbr:Bernoulli_sequence dbr:Hard-core_predicate dbr:Quantum_cryptography dbr:Random dbc:Computational_complexity_theory dbr:Disperser dbc:Cryptographic_algorithms dbr:Polynomial_time dbr:Independent_and_identically_distributed_random_variables dbr:Radioactive_decay dbr:Chaos_machine dbr:Uniform_distribution_(discrete) dbr:Negligible_function dbr:Exchangeable_random_variables dbr:Secure_Hash_Algorithm dbr:Statistically_close dbr:Chaotic_systems dbr:Information_entropy dbr:Cryptographic_hash dbr:Thermal_noise |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Details dbt:Mvar dbt:Reflist |
| dct:subject | dbc:Random_number_generation dbc:Computational_complexity_theory dbc:Cryptographic_algorithms |
| gold:hypernym | dbr:Function |
| rdf:type | yago:WikicatCryptographicAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 |
| rdfs:comment | A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; 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 (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source. (en) Экстрактор случайности — функция, которая применяется к выходу из слабо случайного источника энтропии, вместе с коротким равномерно распределённым случайным начальным значением (англ. seed) и генерирует случайный выход, который выглядит независимым от источника и равномерно распределён. (ru) |
| rdfs:label | Randomness extractor (en) Экстрактор случайности (ru) |
| owl:sameAs | freebase:Randomness extractor yago-res:Randomness extractor wikidata:Randomness extractor dbpedia-ru:Randomness extractor https://global.dbpedia.org/id/4ts3H |
| prov:wasDerivedFrom | wikipedia-en:Randomness_extractor?oldid=959313511&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Randomness_extractor |
| is dbo:wikiPageDisambiguates of | dbr:Extractor |
| is dbo:wikiPageRedirects of | dbr:Von_Neumann_extractor |
| is dbo:wikiPageWikiLink of | dbr:Extractor dbr:Randomness_merger dbr:Hyper-encryption dbr:John_von_Neumann dbr:David_Zuckerman_(computer_scientist) dbr:Decorrelation dbr:Cryptographically_secure_pseudorandom_number_generator dbr:Rényi_entropy dbr:Salil_Vadhan dbr:Fuzzy_extractor dbr:Erdős–Szemerédi_theorem dbr:Bernoulli_process dbr:Hardware_random_number_generator dbr:SWIFFT dbr:Kakeya_set dbr:Leftover_hash_lemma dbr:Disperser dbr:Chaos_machine dbr:Extractor_(mathematics) dbr:Exchangeable_random_variables dbr:Random_number_generation dbr:Statistically_close dbr:Von_Neumann_extractor |
| is foaf:primaryTopic of | wikipedia-en:Randomness_extractor |