Improved non-malleable extractors, non-malleable codes and independent source extractors
Improved non-malleable extractors, non-malleable codes and independent source extractors
复制标题
DOI：
10.1145/3055399.3055486
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Xin Li
中科院分区：
文献类型：
--
作者：
Xin Li
在本文中，我们给出了随机性提取和防篡改密码学文献中几个中心对象的改进构造。我们的主要结果是：(1)一个具有误差ε和种子长度d=O(Logn)+O(log(1/ε)loglog(1/ε))的显式种子不可延展抽取器，它支持最小熵k=Ω(D)并输出Ω(K)比特。结合Dodis和Wichs的协议，给出了一个两轮隐私放大协议，该协议在存在活跃敌手的情况下，对于所有的安全参数Ω(k/logk)都具有最优的熵损失，其中k是共享弱随机源的最小熵。以前最著名的种子不可延展性提取算法需要种子长度和最小熵O(Logn)+Log(1/ε)2O√loglog(1/ε)，并且只给出了两轮保密放大协议，安全参数高达k/2O(√logk)时具有最优的熵损失。(2)用于最小熵k≥(1-Υ)n，某个常数Υ>；0的显式不可延展两源抽取器，其输出错误为2-Ω(n/logn)的Ω(K)比特。我们进一步证明，我们可以有效地从任何抽取器输出的前像中进行均匀采样。结合切拉基和古鲁斯瓦米发现的联系，这给出了具有相对速率Ω(1/logn)的两分裂状态模型中的不可延展码。这成倍地改进了以前的结构，所有这些结构都只达到了n-Ω(1)的速率。(3)结合Ben-Aroya et.Al，我们的不可延展抽取器给出了最小熵O(Logn LoglogN)的双源抽取器，这也意味着N个顶点上的K-Ramsey图，K=(Logn)O(LoglogN)。以前最著名的双源萃取器由Ben-Aroya et.AL需要最小熵logN2O(√logN)，这给出了一个K=(LogN)2O(√loglogN)的Ramsey图。我们进一步给出了一种方法，将构造种子不可延展性萃取器的问题简化为构造不可延展性的独立源萃取器的问题。利用Chattopadhyay和Zuckerman提出的具有最优误差的不可延展10源抽取器，我们给出了最小熵O(LogN)的10源抽取器。以前，Cohen和Schulman最著名的最小熵提取程序需要O(Loglogn)源。与我们的工作无关，Cohen得到了类似于(1)和双源抽取器的结果，除了对ε的依赖是log(1/ε)Polyloglog(1/ε)和双源抽取器需要最小熵logn Polylogn。
In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are: (1) An explicit seeded non-malleable extractor with error ε and seed length d=O(logn)+O(log(1/ε)loglog(1/ε)), that supports min-entropy k=Ω(d) and outputs Ω(k) bits. Combined with the protocol by Dodis and Wichs, this gives a two round privacy amplification protocol with optimal entropy loss in the presence of an active adversary, for all security parameters up to Ω(k/logk), where k is the min-entropy of the shared weak random source. Previously, the best known seeded non-malleable extractors require seed length and min-entropy O(logn)+log(1/ε)2O√loglog(1/ε), and only give two round privacy amplification protocols with optimal entropy loss for security parameter up to k/2O(√logk). (2) An explicit non-malleable two-source extractor for min entropy k ≥ (1 - Υ)n, some constant Υ>0, that outputs Ω(k) bits with error 2-Ω(n/logn). We further show that we can efficiently uniformly sample from the pre-image of any output of the extractor. Combined with the connection found by Cheraghchi and Guruswami this gives a non-malleable code in the two-split-state model with relative rate Ω(1/logn). This exponentially improves previous constructions, all of which only achieve rate n-Ω(1). (3) Combined with the techniques by Ben-Aroya et. al, our non-malleable extractors give a two-source extractor for min-entropy O(logn loglogn), which also implies a K-Ramsey graph on N vertices with K=(logN)O(logloglogN). Previously the best known two-source extractor by Ben-Aroya et. al requires min-entropy logn 2O(√logn), which gives a Ramsey graph with K=(logN)2O(√logloglogN). We further show a way to reduce the problem of constructing seeded non-malleable extractors to the problem of constructing non-malleable independent source extractors. Using the non-malleable 10-source extractor with optimal error by Chattopadhyay and Zuckerman, we give a 10-source extractor for min-entropy O(logn). Previously the best known extractor for such min-entropy by Cohen and Schulman requires O(loglogn) sources. Independent of our work, Cohen obtained similar results to (1) and the two-source extractor, except the dependence on ε is log(1/ε)poly loglog(1/ε) and the two-source extractor requires min-entropy logn poly loglogn.