International Association for Cryptologic Research

International Association
for Cryptologic Research


Yanyi Liu


On the Possibility of Basing Cryptography on $\EXP \neq \BPP$ 📺
Yanyi Liu Rafael Pass
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$.
Secure Massively Parallel Computation for Dishonest Majority 📺
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.
Communication-Efficient Unconditional MPC with Guaranteed Output Delivery 📺
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.