Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Marshall Ball:

TR23-169 | 14th November 2023
Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja

Extracting Randomness from Samplable Distributions, Revisited

Randomness extractors provide a generic way of converting sources of randomness that are
merely unpredictable into almost uniformly random bits. While in general, deterministic randomness
extraction is impossible, it is possible if the source has some structural constraints.
While much of the literature on deterministic extraction has focused on sources ... more >>>

TR23-167 | 13th November 2023
Marshall Ball, Ronen Shaltiel, Jad Silbak

Non-malleable codes with optimal rate for poly-size circuits

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss (CRYPTO 2022) which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same ... more >>>

TR22-010 | 18th January 2022
Marshall Ball, Dana Dachman-Soled, Julian Loss

(Nondeterministic) Hardness vs. Non-Malleability

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ... more >>>

ISSN 1433-8092 | Imprint