Next

__
TR21-084
| 21st June 2021
__

Liron Bronfman, Ron Rothblum#### PCPs and Instance Compression from a Cryptographic Lens

__
TR21-083
| 21st June 2021
__

Mark Braverman, Sumegha Garg, Or Zamir#### Tight Space Complexity of the Coin Problem

__
TR21-082
| 16th June 2021
__

Rahul Ilango, Hanlin Ren, Rahul Santhanam#### Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

Next

Liron Bronfman, Ron Rothblum

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic ... more >>>

Mark Braverman, Sumegha Garg, Or Zamir

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

Rahul Ilango, Hanlin Ren, Rahul Santhanam

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Next