Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rafael Pass:

TR21-059 | 20th April 2021
Yanyi Liu, Rafael Pass

On One-way Functions from NP-Complete Problems

Revisions: 1

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. The problem, which originated in the 1960s, is ... more >>>

TR21-056 | 22nd April 2021
Yanyi Liu, Rafael Pass

On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely ... more >>>

TR21-055 | 20th April 2021
Yanyi Liu, Rafael Pass

Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity

Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class ... more >>>

TR20-052 | 14th April 2020
Yanyi Liu, Rafael Pass

On One-way Functions and Kolmogorov Complexity

Revisions: 2

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ... more >>>

TR20-051 | 15th April 2020
Rafael Pass, Muthuramakrishnan Venkitasubramaniam

Is it Easier to Prove Theorems that are Guaranteed to be True?

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in $\NP$ imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>>

ISSN 1433-8092 | Imprint