Extracting Randomness from Extractor-Dependent Sources
© International Association for Cryptologic Research 2020. We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. H...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137257 |
| _version_ | 1826203618860072960 |
|---|---|
| author | Dodis, Yevgeniy Vaikuntanathan, Vinod Wichs, Daniel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Dodis, Yevgeniy Vaikuntanathan, Vinod Wichs, Daniel |
| author_sort | Dodis, Yevgeniy |
| collection | MIT |
| description | © International Association for Cryptologic Research 2020. We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the source can make arbitrary oracle queries to the extractor with the given seed before outputting a sample. We require that the sample has entropy and differs from any of the previously queried values. The extracted output should look uniform even to a distinguisher that gets the seed. We consider two variants of the problem, depending on whether the source only outputs the sample, or whether it can also output some correlated public auxiliary information that preserves the sample’s entropy. Our results are: Without Auxiliary Information: We show that every pseudo-random function (PRF) with a sufficiently high security level is a good extractor in this setting, even if the distinguisher is computationally unbounded. We further show that the source necessarily needs to be computationally bounded and that such extractors imply one-way functions. With Auxiliary Information: We construct secure extractors in this setting, as long as both the source and the distinguisher are computationally bounded. We give several constructions based on different intermediate primitives, yielding instantiations based on the DDH, DLIN, LWE or DCR assumptions. On the negative side, we show that one cannot prove security against computationally unbounded distinguishers in this setting under any standard assumption via a black-box reduction. Furthermore, even when restricting to computationally bounded distinguishers, we show that there exist PRFs that are insecure as extractors in this setting and that a large class of constructions cannot be proven secure via a black-box reduction from standard assumptions. |
| first_indexed | 2024-09-23T12:40:09Z |
| format | Article |
| id | mit-1721.1/137257 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:40:09Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1372572023-12-08T18:20:33Z Extracting Randomness from Extractor-Dependent Sources Dodis, Yevgeniy Vaikuntanathan, Vinod Wichs, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © International Association for Cryptologic Research 2020. We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the source can make arbitrary oracle queries to the extractor with the given seed before outputting a sample. We require that the sample has entropy and differs from any of the previously queried values. The extracted output should look uniform even to a distinguisher that gets the seed. We consider two variants of the problem, depending on whether the source only outputs the sample, or whether it can also output some correlated public auxiliary information that preserves the sample’s entropy. Our results are: Without Auxiliary Information: We show that every pseudo-random function (PRF) with a sufficiently high security level is a good extractor in this setting, even if the distinguisher is computationally unbounded. We further show that the source necessarily needs to be computationally bounded and that such extractors imply one-way functions. With Auxiliary Information: We construct secure extractors in this setting, as long as both the source and the distinguisher are computationally bounded. We give several constructions based on different intermediate primitives, yielding instantiations based on the DDH, DLIN, LWE or DCR assumptions. On the negative side, we show that one cannot prove security against computationally unbounded distinguishers in this setting under any standard assumption via a black-box reduction. Furthermore, even when restricting to computationally bounded distinguishers, we show that there exist PRFs that are insecure as extractors in this setting and that a large class of constructions cannot be proven secure via a black-box reduction from standard assumptions. 2021-11-03T17:34:21Z 2021-11-03T17:34:21Z 2020 2021-04-08T14:40:44Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137257 Dodis, Yevgeniy, Vaikuntanathan, Vinod and Wichs, Daniel. 2020. "Extracting Randomness from Extractor-Dependent Sources." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12105 LNCS. en 10.1007/978-3-030-45721-1_12 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing Other repository |
| spellingShingle | Dodis, Yevgeniy Vaikuntanathan, Vinod Wichs, Daniel Extracting Randomness from Extractor-Dependent Sources |
| title | Extracting Randomness from Extractor-Dependent Sources |
| title_full | Extracting Randomness from Extractor-Dependent Sources |
| title_fullStr | Extracting Randomness from Extractor-Dependent Sources |
| title_full_unstemmed | Extracting Randomness from Extractor-Dependent Sources |
| title_short | Extracting Randomness from Extractor-Dependent Sources |
| title_sort | extracting randomness from extractor dependent sources |
| url | https://hdl.handle.net/1721.1/137257 |
| work_keys_str_mv | AT dodisyevgeniy extractingrandomnessfromextractordependentsources AT vaikuntanathanvinod extractingrandomnessfromextractordependentsources AT wichsdaniel extractingrandomnessfromextractordependentsources |