ECCC-Report TR16-036https://eccc.weizmann.ac.il/report/2016/036Comments and Revisions published for TR16-036en-usSun, 11 Jun 2017 23:54:26 +0300
Revision 3
| Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols |
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2016/036#revision3We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).
For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li [CGL16] , and by Cohen [Coh16a,Coh16b] all require seed length and min-entropy at least $\log^2 (1/\epsilon)$, where $\epsilon$ is the error of the extractor. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve 2 rounds of communication and optimal entropy loss in [Li15c,CGL16], can only handle security parameter up to $s=\Omega(\sqrt{k})$, where $k$ is the min-entropy of the shared secret weak random source. For larger $s$ the best known protocol with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of communication.
In this paper we give an explicit non-malleable extractor that only requires seed length and min-entropy $\log^{1+o(1)} (n/\epsilon)$, which also yields a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=k^{1-\alpha}$ for any constant $\alpha>0$.
For the third problem, previously the best known extractor which supports the smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+\delta} n$ and uses $O(1/\delta)$ sources, for any constant $\delta>0$. A very recent result by Cohen and Schulman [CS16] improves this, and constructed explicit extractors that use $O(1/\delta)$ sources for min-entropy $\log^{1+\delta} n$, any constant $\delta>0$. In this paper we further improve their result, and give an explicit extractor that uses $O(1)$ (an absolute constant) sources for min-entropy $\log^{1+o(1)} n$.
The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced in [CS16], which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of [CS16], and may be of independent interest.Sun, 11 Jun 2017 23:54:26 +0300https://eccc.weizmann.ac.il/report/2016/036#revision3
Revision 2
| Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols |
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2016/036#revision2We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).
For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li [CGL16] , and by Cohen [Coh16a,Coh16b] all require seed length and min-entropy at least $\log^2 (1/\epsilon)$, where $\epsilon$ is the error of the extractor. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve 2 rounds of communication and optimal entropy loss in [Li15c,CGL16], can only handle security parameter up to $s=\Omega(\sqrt{k})$, where $k$ is the min-entropy of the shared secret weak random source. For larger $s$ the best known protocol with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of communication.
In this paper we give an explicit non-malleable extractor that only requires seed length and min-entropy $\log^{1+o(1)} (n/\epsilon)$, which also yields a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=k^{1-\alpha}$ for any constant $\alpha>0$.
For the third problem, previously the best known extractor which supports the smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+\delta} n$ and uses $O(1/\delta)$ sources, for any constant $\delta>0$. A very recent result by Cohen and Schulman [CS16] improves this, and constructed explicit extractors that use $O(1/\delta)$ sources for min-entropy $\log^{1+\delta} n$, any constant $\delta>0$. In this paper we further improve their result, and give an explicit extractor that uses $O(1)$ (an absolute constant) sources for min-entropy $\log^{1+o(1)} n$.
The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced in [CS16], which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of [CS16], and may be of independent interest.Sun, 03 Apr 2016 20:59:16 +0300https://eccc.weizmann.ac.il/report/2016/036#revision2
Revision 1
| Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols |
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2016/036#revision1We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).
For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li [CGL16] , and by Cohen [Coh16a,Coh16b] all require seed length and min-entropy at least $\log^2 (1/\epsilon)$, where $\epsilon$ is the error of the extractor. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve 2 rounds of communication and optimal entropy loss in [Li15c,CGL16], can only handle security parameter up to $s=\Omega(\sqrt{k})$, where $k$ is the min-entropy of the shared secret weak random source. For larger $s$ the best known protocol with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of communication.
In this paper we give an explicit non-malleable extractor that only requires seed length and min-entropy $\log^{1+o(1)} (n/\epsilon)$, which also yields a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=k^{1-\alpha}$ for any constant $\alpha>0$.
For the third problem, previously the best known extractor which supports the smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+\delta} n$ and uses $O(1/\delta)$ sources, for any constant $\delta>0$. A very recent result by Cohen and Schulman [CS16] improves this, and constructed explicit extractors that use $O(1/\delta)$ sources for min-entropy $\log^{1+\delta} n$, any constant $\delta>0$. In this paper we further improve their result, and give an explicit extractor that uses $O(1)$ (an absolute constant) sources for min-entropy $\log^{1+o(1)} n$.
The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced in [CS16], which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of [CS16], and may be of independent interest.Tue, 15 Mar 2016 03:25:47 +0200https://eccc.weizmann.ac.il/report/2016/036#revision1
Paper TR16-036
| Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols |
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2016/036We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).
For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li [CGL16] , and by Cohen [Coh16a,Coh16b] all require seed length and min-entropy at least $\log^2 (1/\epsilon)$, where $\epsilon$ is the error of the extractor. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve 2 rounds of communication and optimal entropy loss in [Li15c,CGL16], can only handle security parameter up to $s=\Omega(\sqrt{k})$, where $k$ is the min-entropy of the shared secret weak random source. For larger $s$ the best known protocol with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of communication.
In this paper we give an explicit non-malleable extractor that only requires seed length and min-entropy $\log^{1+o(1)} (n/\epsilon)$, which also yields a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=k^{1-\alpha}$ for any constant $\alpha>0$.
For the third problem, previously the best known extractor which supports the smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+\delta} n$ and uses $O(1/\delta)$ sources, for any constant $\delta>0$. A very recent result by Cohen and Schulman [CS16] improves this, and constructed explicit extractors that use $O(1/\delta)$ sources for min-entropy $\log^{1+\delta} n$, any constant $\delta>0$. In this paper we further improve their result, and give an explicit extractor that uses $O(1)$ (an absolute constant) sources for min-entropy $\log^{1+o(1)} n$.
The key ingredient in all our constructions is a generalized, and much more efficient version of the independence preserving merger introduced in [CS16], which we call non-malleable independence preserving merger. Our construction of the merger also simplifies that of [CS16], and may be of independent interest.Sun, 13 Mar 2016 18:19:51 +0200https://eccc.weizmann.ac.il/report/2016/036