Extracting Randomness from Extractor-Dependent Sources
Extracting Randomness from Extractor-Dependent Sources
复制标题
从依赖于提取器的源中提取随机性
DOI：
10.1007/978-3-030-45721-1_12
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Wichs, Daniel
中科院分区：
文献类型：
--
作者：
Dodis, Yevgeniy;Vaikuntanathan, Vinod;Wichs, Daniel
我们重新研究的问题，提取几乎均匀的随机性从任意源足够的最小熵。强种子提取器通过依赖于公共随机种子来解决这个问题，这对于源是未知的。在这里，我们考虑一种设置，其中种子随着时间的推移而重用，并且源可能依赖于先前对具有相同种子的提取器的调用。我们还能提取出几乎一致的随机性吗？更详细地说，我们假设种子是随机选择的，但是源可以在输出样本之前使用给定的种子对提取器进行任意的oracle查询。我们要求样本具有熵，并且与之前查询的任何值都不同。提取的输出应该看起来均匀，即使是获得种子的机器人。我们考虑两个变量的问题，这取决于源是否只输出样本，或者它是否也可以输出一些相关的公共辅助信息，保持样本的熵。我们的研究结果是：没有辅助信息：我们表明，everyyprandom-random函数（PRF）具有足够高的安全级别是一个很好的提取器，在这种情况下，即使是计算上无界的随机数。我们进一步表明，源必须是计算上有界的，这样的提取器意味着单向functions.With辅助信息：我们构建安全的提取器在这种情况下，只要源和提取器是计算上有界的。我们给出了几种基于不同中间原语的构造，基于DDH，DLIN，LWE或DCR假设产生实例。在消极的一面，我们表明，一个不能证明安全对计算上无界的加密货币在此设置下，任何标准的假设，通过黑盒还原。此外，即使限制到计算有界的提取器，我们表明，存在的PRF是不安全的提取器在这种情况下，一个大类的建设不能被证明是安全的，通过从标准假设的黑盒减少。
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 andthe 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 publicauxiliary informationthat preserves the sample’s entropy. Our results are:Without Auxiliary Information: We show that everypseudo-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.
登录
查看更多内容
公共种子伪随机排列
DOI：
--
发表时间：
2017
期刊：
International Conference on the Theory and Application of Cryptographic Techniques
影响因子：
--
作者：
Pratik Soni;Stefano Tessaro
通讯作者：
Stefano Tessaro
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David
CRS 模型中误差可忽略不计的计算提取器
DOI：
--
发表时间：
2019
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
A. Garg;Y. Kalai;Dakshita Khurana
通讯作者：
Dakshita Khurana
小空间源的确定性提取器
DOI：
10.1145/1132516.1132613
发表时间：
2006
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Jesse Kamp;Anup Rao;S. Vadhan;David Zuckerman
通讯作者：
David Zuckerman
如何吃掉你的熵并拥有它：受损 RNG 的最佳恢复策略
影响因子：
1.1
作者：
Y. Dodis;A. Shamir;Noah Stephens;Daniel Wichs
通讯作者：
Daniel Wichs