All reports by Author Rafael Pass:

__
TR22-113
| 11th August 2022
__

Yanyi Liu, Rafael Pass#### Leakage-Resilient Hardness v.s. Randomness

Revisions: 2

__
TR22-084
| 2nd June 2022
__

Yanyi Liu, Rafael Pass#### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

__
TR21-092
| 28th June 2021
__

Yanyi Liu, Rafael Pass#### A Note on One-way Functions and Sparse Languages

Revisions: 1

__
TR21-059
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### On One-way Functions from NP-Complete Problems

Revisions: 2

__
TR21-056
| 22nd April 2021
__

Yanyi Liu, Rafael Pass#### On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

__
TR21-055
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity

__
TR20-052
| 14th April 2020
__

Yanyi Liu, Rafael Pass#### On One-way Functions and Kolmogorov Complexity

Revisions: 2

__
TR20-051
| 15th April 2020
__

Rafael Pass, Muthuramakrishnan Venkitasubramaniam#### Is it Easier to Prove Theorems that are Guaranteed to be True?

Yanyi Liu, Rafael Pass

A central open problem in complexity theory concerns the question of

whether all efficient randomized algorithms can be simulated by

efficient deterministic algorithms. The celebrated ``hardness

v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84),

Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness

assumptions under which $\prBPP = \prP$, but these hardness ...
more >>>

Yanyi Liu, Rafael Pass

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>

Yanyi Liu, Rafael Pass

We show equivalence between the existence of one-way

functions and the existence of a \emph{sparse} language that is

hard-on-average w.r.t. some efficiently samplable ``high-entropy''

distribution.

In more detail, the following are equivalent:

- The existentence of a $S(\cdot)$-sparse language $L$ that is

hard-on-average with respect to some samplable ...
more >>>

Yanyi Liu, Rafael Pass

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

Yanyi Liu, Rafael Pass

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

Yanyi Liu, Rafael Pass

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

Yanyi Liu, Rafael Pass

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

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

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