All reports by Author Marshall Ball:

__
TR20-023
| 10th February 2020
__

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan#### Non-Malleability against Polynomial Tampering

__
TR19-183
| 21st December 2019
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

__
TR18-040
| 21st February 2018
__

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

__
TR17-039
| 28th February 2017
__

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan#### Average-Case Fine-Grained Hardness

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.

Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.

Going from the more restricted model ...
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 >>>

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>>