All reports by Author Yanyi Liu:

__
TR23-152
| 14th October 2023
__

Yanyi Liu, Rafael Pass#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

__
TR23-103
| 12th July 2023
__

Yanyi Liu, Rafael Pass#### On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

Revisions: 1

__
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

Yanyi Liu, Rafael Pass

Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- ...
more >>>

Yanyi Liu, Rafael Pass

Whether one-way functions (OWF) exist is arguably the most important

problem in Cryptography, and beyond. While lots of candidate

constructions of one-way functions are known, and recently also

problems whose average-case hardness characterize the existence of

OWFs have been demonstrated, the question of

whether there exists some \emph{worst-case hard problem} ...
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. 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 >>>