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:

TR21-050 | 2nd April 2021
Marshall Ball, Alper Cakan, Tal Malkin

Linear Threshold Secret-Sharing with Binary Reconstruction

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

TR20-054 | 22nd April 2020
Marshall Ball, Oded Goldreich, Tal Malkin

Communication Complexity with Defective Randomness

Revisions: 2

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

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

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

TR20-023 | 10th February 2020
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

Non-Malleability against Polynomial Tampering

Revisions: 1

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

TR19-183 | 21st December 2019
Marshall Ball, Oded Goldreich, Tal Malkin

Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

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

TR18-040 | 21st February 2018
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

Non-Malleable Codes for Small-Depth Circuits

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

TR17-039 | 28th February 2017
Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

Average-Case Fine-Grained Hardness

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

ISSN 1433-8092 | Imprint