Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Eldon Chung:

TR23-193 | 3rd December 2023
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

TR21-150 | 7th November 2021
Eldon Chung, Maciej Obremski, Divesh Aggarwal

Extractors: Low Entropy Requirements Colliding With Non-Malleability

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.
(2) Constructions where one source is uniform, and the other ... more >>>

TR21-090 | 14th June 2021
Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>>

ISSN 1433-8092 | Imprint