## CryptoDB

### Yanyi Liu

#### Publications

**Year**

**Venue**

**Title**

2024

EUROCRYPT

A Direct PRF Construction from Kolmogorov Complexity
Abstract

While classic results in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.
Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem $\mktp[s]$, where given a threshold, $s(\cdot)$, and a polynomial time-bound, $t(\cdot)$, $\mktp[s]$ denotes the language consisting of strings $x$ with $t$-bounded Kolmogorov complexity, $K^t(x)$, bounded by $s(|x|)$.
In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of $\mktp[2^{O(\sqrt{\log n})}]$ w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be
equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (quasi-polynomially secure) PRFs.
Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.

2024

TCC

On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity, and Computational Depth
Abstract

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} that characterizes
the existence of one-way functions has remained open since their
introduction in 1976.
In this work, we present the first ``OWF-complete'' promise
problem---a promise problem whose worst-case hardness w.r.t. $\BPP$
(resp. $\Ppoly$) is \emph{equivalent} to the existence of OWFs secure
against $\PPT$ (resp. $\nuPPT$) algorithms. The problem is a
variant of the Minimum Time-bounded Kolmogorov Complexity
problem ($\mktp[s]$ with a threshold $s$), where we condition on
instances having small ``computational depth''.
We furthermore show that depending on the choice of the
threshold $s$, this problem characterizes either ``standard''
(polynomially-hard) OWFs, or quasi polynomially- or
subexponentially-hard OWFs. Additionally, when the threshold is
sufficiently small (e.g., $2^{O(\sqrt{n})}$ or $\poly\log n$) then
\emph{sublinear} hardness of this problem suffices to characterize
quasi-polynomial/sub-exponential OWFs.
While our constructions are black-box, our analysis is \emph{non-
black box}; we additionally demonstrate that fully black-box constructions
of OWF from the worst-case hardness of this problem are impossible.
We finally show that, under Rudich's conjecture, and standard derandomization
assumptions, our problem is not inside $\coAM$; as such, it
yields the first candidate problem believed to be outside of $\AM \cap \coAM$,
or even ${\bf SZK}$, whose worst case hardness implies the existence of OWFs.

2023

CRYPTO

One-way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Abstract

Consider the recently introduced notion of \emph{probabilistic
time-bounded Kolmogorov Complexity}, $pK^t$ (Goldberg et al,
CCC'22), and let $\mpktp$ denote the language of pairs $(x,t)$ such that $pK^t(x) \leq t$.
We show the equivalence of the following:
\BI
\item $\mpkpolyp$ is (mildly) hard-on-average w.r.t. \emph{any} samplable
distribution $\D$;
\item $\mpkpolyp$ is (mildly) hard-on-average w.r.t. the
\emph{uniform} distribution;
\item existence of one-way functions.
\EI
As far as we know, this yields the first natural class of problems where
hardness with respect to any samplable distribution is equivalent
to hardness with respect to the uniform distribution.
Under standard derandomization assumptions, we can show the same result
also w.r.t. the standard notion of time-bounded Kolmogorov
complexity, $K^t$.

2023

TCC

On One-way Functions and Sparse Languages
Abstract

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 existence of a $S(\cdot)$-sparse language $L$ that is
hard-on-average with respect to some samplable distribution with
Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq 4\log n$;
- The existence of a $S(\cdot)$-sparse language $L \in
\NP$, that is
hard-on-average with respect to some samplable distribution with
Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq n/3$;
- The existence of one-way functions.
Our results are inspired by, and generalize, results from the elegant
recent paper by Ilango, Ren and Santhanam (IRS, STOC'22), which presents
similar connections for \emph{specific} sparse languages.

2021

CRYPTO

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

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the
existence of one-way
functions 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 related to the problem of whether $\EXP \neq
\BPP$. In more detail, let $Kt(x)$ denote the Levin-Kolmogorov Complexity of the string $x$;
that is, $Kt(x) = \min_{\desc \in \bitset^*, t \in \N}\{|\desc| +
\lceil \log t \rceil: U(\desc, 1^t) = x\}$, where $U$ is a universal
Turing machine, and let $\mktp$ denote the language of pairs $(x,k)$ having
the property that $Kt(x) \leq k$.
We demonstrate that:
- $\mktp$ is \emph{two-sided error} mildly average-case hard (i.e., $\mktp
\notin \HeurpBPP$) iff infinititely-often one-way
functions exist.
- $\mktp$ is \emph{errorless} mildly average-case hard (i.e., $\mktp
\notin \AvgpBPP$) iff $\EXP \neq \BPP$.
Thus, the only ``gap'' towards getting (infinitely-often) one-way
functions from the assumption that $\EXP \neq \BPP$ is the
seemingly ``minor'' technical gap
between two-sided error and errorless average-case hardness of the
$\mktp$ problem.
As a corollary of this result, we additionally demonstrate that
any reduction from errorless to two-sided error average-case
hardness for $\mktp$ implies (unconditionally) that $\NP \neq \P$.
We finally consider other alternative notions of Kolmogorov
complexity---including space-bounded Kolmogorov complexity and
conditional Kolmogorov complexity---and show how average-case
hardness of problems related to them characterize log-space
computable one-way functions, or one-way functions in $\NC^0$.

2020

TCC

Secure Massively Parallel Computation for Dishonest Majority
📺
Abstract

This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the types of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS ’20) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt.
We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors
(LWE) problem, and works for any MPC protocol with “short” output—that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE.

2019

CRYPTO

Communication-Efficient Unconditional MPC with Guaranteed Output Delivery
📺
Abstract

We study the communication complexity of unconditionally secure MPC with guaranteed output delivery over point-to-point channels for corruption threshold
$$t < n/3$$
. We ask the question: “is it possible to construct MPC in this setting s.t. the communication complexity per multiplication gate is linear in the number of parties?” While a number of works have focused on reducing the communication complexity in this setting, the answer to the above question has remained elusive for over a decade.We resolve the above question in the affirmative by providing an MPC with communication complexity
$$O(Cn\kappa + n^3\kappa )$$
where
$$\kappa $$
is the size of an element in the field, C is the size of the (arithmetic) circuit, and, n is the number of parties. This represents a strict improvement over the previously best known communication complexity of
$$O(Cn\kappa +D_Mn^2\kappa +n^3\kappa )$$
where
$$D_M$$
is the multiplicative depth of the circuit. To obtain this result, we introduce a novel technique called 4-consistent tuples of sharings which we believe to be of independent interest.

#### Coauthors

- Rex Fernando (1)
- Vipul Goyal (1)
- Ilan Komargodski (1)
- Yanyi Liu (7)
- Rafael Pass (5)
- Elaine Shi (1)
- Yifan Song (1)