All reports by Author Dana Dachman-Soled:

__
TR23-205
| 21st December 2023
__

Marshall Ball, Dana Dachman-Soled#### (Inefficient Prover) ZAPs from Hard-to-Invert Functions

__
TR23-169
| 14th November 2023
__

Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja#### Extracting Randomness from Samplable Distributions, Revisited

__
TR22-010
| 18th January 2022
__

Marshall Ball, Dana Dachman-Soled, Julian Loss#### (Nondeterministic) Hardness vs. Non-Malleability

__
TR18-040
| 21st February 2018
__

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan#### Non-Malleable Codes for Small-Depth Circuits

Marshall Ball, Dana Dachman-Soled

A ZAP is a witness-indistinguishable two-message public-coin interactive proof with the following simple structure: the verifier sends a uniformly random string, the prover responds, and the verifier decides in polynomial time whether to accept or reject.

We show that one-way functions imply the existence of ...
more >>>

Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja

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 >>>

Marshall Ball, Dana Dachman-Soled, Julian Loss

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 >>>

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>