42digest首页
冷凝和提取对抗在线对抗

Condensing and Extracting Against Online Adversaries

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco Servedio

arXiv
2024年11月6日

我们研究从在线非遗忘符号修复(oNOSF)源进行确定性压缩和提取的任务,这是一种有缺陷的随机性的自然模型,在许多参数机制中不可能提取[AORSV, EUROCRYPT'20]。 (g,l)-oNOSF源是l块的序列,其中至少g块是好的(独立的,有最小熵),剩下的坏块由在线对手控制,并且可以任意与先前的块相关。 以前,[CGR,FOCS'24]证明不可能在g≤0.5 l时凝结超过速率1/2,并且显示当g≥0.51l和n在l中呈指数时,冷凝器的存在。 在这项工作中,我们不仅构建了第一个与[CGR,FOCS'24]的存在结果相匹配的显式冷凝器,而且当g≥0.51l和n在l中仅多对数时,我们通过处理情况进行双指数改进。 我们还获得了改进的显式结构,用于将低熵oNOSF源转换为均匀的oNOSF源。 接下来,我们通过显示冷凝器的存在来解决oNOSF源冷凝器的存在问题,即使n是一个足够大的常数并且l正在增长(前提是g≥0.51l)。 我们将冷凝器应用于集体硬币翻转和集体采样,广泛研究容错分布式计算中的问题,并为它们提供非常简单的协议。 最后,我们研究从oNOSF来源提取的可能性。 对于下界,我们引入了在线影响的概念——扩展了布尔函数的影响概念——并建立了严格的界限,这意味着提取下限。 我们还通过领导者选举协议构建显式提取器,这些协议击败了标准弹性函数[AL,Combinatorica'93]。

We study the tasks of deterministically condensing and extracting from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective randomness where extraction is impossible in many parameter regimes [AORSV, EUROCRYPT'20]. A (g,ℓ)-oNOSF source is a sequence of ℓ blocks where at least g blocks are good (independent, with min-entropy) and the remaining bad blocks are controlled by an online adversary and can be arbitrarily correlated with prior blocks. Previously, [CGR, FOCS'24...