An official website of the United States government
A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show that an asymptotically optimal construction of one central object will lead to asymptotically optimal solutions to all the others. However, despite considerable effort, previous works can get close but still lack one final step to achieve truly asymptotically optimal constructions. In this paper we provide the last missing link, thus simultaneously achieving explicit, asymptotically optimal constructions and solutions for various well studied extractors and applications, that have been the subjects of long lines of research. Our results include: 1. Asymptotically optimal seeded non-malleable extractors, which in turn give two source extractors for asymptotically optimal min-entropy of $$O(\log n)$$, explicit constructions of $$K$$-Ramsey graphs on $$N$$ vertices with $$K=\log^{O(1)} N$$, and truly optimal privacy amplification protocols with an active adversary. 2. Two source non-malleable extractors and affine non-malleable extractors for some linear min-entropy with exponentially small error, which in turn give the first explicit construction of non-malleable codes against $$2$$-split state tampering and affine tampering with constant rate and \emph{exponentially} small error. 3. Explicit extractors for affine sources, sumset sources, interleaved sources, and small space sources that achieve asymptotically optimal min-entropy of $$O(\log n)$ or $$2s+O(\log n)$$ (for space $$s$$ sources). 4. An explicit function that requires strongly linear read once branching programs of size $$2^{n-O(\log n)}$$, which is optimal up to the constant in $$O(\cdot)$$. Previously, even for standard read once branching programs, the best known size lower bound for an explicit function is $$2^{n-O(\log^2 n)}$$.
more »
« less
Privacy Amplification from Non-Malleable Codes
Non-malleable Codes give us the following property: their codewords cannot be tampered into codewords of related messages. Privacy Amplification allows parties to convert their weak shared secret into a fully hidden, uniformly distributed secret key, while communicating on a fully tamperable public channel. In this work, we show how to construct a constant round privacy amplification protocol from any augmented split-state non-malleable code. Existentially, this gives us another primitive (in addition to optimal non-malleable extractors) whose optimal construction would solve the long-standing open problem of building constant round privacy amplification with optimal entropy loss. Instantiating our code with the current best known NMC gives us an 8-round privacy amplification protocol with entropy loss O(log(n)+κlog(κ)) and min-entropy requirement Ω(log(n)+κlog(κ)), where κ is the security parameter and n is the length of the shared weak secret. In fact, for our result, even the weaker primitive of Non-malleable Randomness Encoders suffice. We view our result as an exciting connection between two of the most fascinating and well-studied information theoretic primitives, non-malleable codes and privacy amplification.
more »
« less
- Award ID(s):
- 1849899
- PAR ID:
- 10136218
- Date Published:
- Journal Name:
- Lecture notes in computer science
- ISSN:
- 0302-9743
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)Non-malleable extractors are generalizations and strengthening of standard randomness extractors, that are resilient to adversarial tampering. Such extractors have wide applications in cryptography and have become important cornerstones in recent breakthroughs of explicit constructions of two-source extractors and affine extractors for small entropy. However, explicit constructions of non-malleable extractors appear to be much harder than standard extractors. Indeed, in the well-studied models of two-source and affine non-malleable extractors, the previous best constructions only work for entropy rate > 2/3 and 1-γ for some small constant γ > 0 respectively by Li (FOCS' 23). In this paper, we present explicit constructions of two-source and affine non-malleable extractors that match the state-of-the-art constructions of standard ones for small entropy. Our main results include: - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k ≥ log^C n and polynomially small error, matching the parameters of standard extractors by Chattopadhyay and Zuckerman (STOC' 16, Annals of Mathematics' 19) and Li (FOCS' 16). - Two-source and affine non-malleable extractors (over 𝖥₂) for sources on n bits with min-entropy k = O(log n) and constant error, matching the parameters of standard extractors by Li (FOCS' 23). Our constructions significantly improve previous results, and the parameters (entropy requirement and error) are the best possible without first improving the constructions of standard extractors. In addition, our improved affine non-malleable extractors give strong lower bounds for a certain kind of read-once linear branching programs, recently introduced by Gryaznov, Pudlák, and Talebanfard (CCC' 22) as a generalization of several well studied computational models. These bounds match the previously best-known average-case hardness results given by Chattopadhyay and Liao (CCC' 23) and Li (FOCS' 23), where the branching program size lower bounds are close to optimal, but the explicit functions we use here are different. Our results also suggest a possible deeper connection between non-malleable extractors and standard ones.more » « less
-
Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries. In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of an {\em agreement expander} then the local testability of the code follows from the local testability of the base code. Agreement expanders allow one to stitch together many mostly-consistent local functions into a single global function. High-dimensional expanders are known to yield agreement expanders with constant degree. This work unifies and generalizes the known results on testability of the Hadamard, Reed-Muller and lifted codes, all of which are proved via a single round of local self-correction: the corrected value at a vertex v depends on the values of all vertices that share a constraint with v. In the above codes this set includes all of the vertices. In contrast, in our setting the degree of a vertex might be a constant, so we cannot hope for one-round self-correction. We overcome this technical hurdle by performing iterative self correction with logarithmically many rounds and tightly controlling the error in each iteration using properties of the agreement expander. Given this result, the missing ingredient towards constructing a constant-query LTC with positive rate and constant relative distance is an instantiation of a base code and a constant-degree agreement expander that interact well with each other.more » « less
-
Asynchronous verifiable secret sharing (AVSS) protocols protect a secret that is distributed among N parties. Dual-threshold AVSS protocols guarantee consensus in the presence of T Byzantine failures and privacy if fewer than P parties attempt to reconstruct the secret. In this work, we construct a dual-threshold AVSS protocol that is optimal along several dimensions. First, it is a high-threshold AVSS scheme, meaning that it is a dual-threshold AVSS with optimal parameters T < N/3 and P < N - T. Second, it has O(N^2) message complexity, and for large secrets it achieves the optimal O(N) communication overhead, without the need for a public key infrastructure or trusted setup. While these properties have been achieved individually before, to our knowledge this is the first protocol that is achieves all of the above simultaneously. The core component of our construction is a high-threshold AVSS scheme for small secrets based on polynomial commitments that achieves O(N^2 log(N)) communication overhead, as compared to prior schemes that require O(N^3) overhead with Tmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
