All reports by Author Marshall Ball:

__
TR21-050
| 2nd April 2021
__

Marshall Ball, Alper Cakan, Tal Malkin#### Linear Threshold Secret-Sharing with Binary Reconstruction

__
TR20-054
| 22nd April 2020
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Communication Complexity with Defective Randomness

Revisions: 2

__
TR20-044
| 8th April 2020
__

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan#### Cryptography from Information Loss

Revisions: 1

__
TR20-023
| 10th February 2020
__

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

Revisions: 1

__
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, Alper Cakan, Tal Malkin

Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`$t$-out-of-$n$') secret-sharing where the linear reconstruction function is restricted to coefficients in $\{0,1\}$. We prove upper and lower bounds on the share size of such schemes. One ramification of our results is ... more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.

Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ...
more >>>

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input ... more >>>

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