Paper 2020/395
Cryptography from Information Loss
Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan
Abstract
Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input instance. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into ``useful'' hardness, namely cryptography. Our first, conceptual, contribution is a definition of lossy reductions in the language of mutual information. Roughly speaking, our definition says that a reduction $\mathsf{C}$ is $t$lossy if, for any distribution $X$ over its inputs, the mutual information $I(X;\mathsf{C}(X)) \leq t$. Our treatment generalizes a variety of seemingly related but distinct notions such as worstcase to averagecase reductions, randomized encodings (Ishai and Kushilevitz, FOCS 2000), homomorphic computations (Gentry, STOC 2009), and instance compression (Harnik and Naor, FOCS 2006). We then proceed to show several consequences of lossy reductions: 1. We say that a language $L$ has an $f$reduction to a language $L'$ for a Boolean function $f$ if there is a (randomized) polynomialtime algorithm $\mathsf{C}$ that takes an $m$tuple of strings $X = (x_1,\ldots,x_m)$, with each $x_i\in\{0,1\}^n$, and outputs a string $z$ such that with high probability, \begin{align*} L'(z) = f(L(x_1),L(x_2),\ldots,L(x_m)) \end{align*} 2. Suppose a language $L$ has an $f$reduction $\mathsf{C}$ to $L'$ that is $t$lossy. Our first result is that oneway functions exist if $L$ is worstcase hard and one of the following conditions holds:  $f$ is the OR function, $t \leq m/100$, and $L'$ is the same as $L$  $f$ is the Majority function, and $t \leq m/100$  $f$ is the OR function, $t \leq O(m\log{n})$, and the reduction has no error This improves on the implications that follow from combining (Drucker, FOCS 2012) with (Ostrovsky and Wigderson, ISTCS 1993) that result in {\em auxiliaryinput} oneway functions. 3. Our second result is about the stronger notion of $t$compressing $f$reductions  reductions that only output $t$ bits. We show that if there is an averagecase hard language $L$ that has a $t$compressing Majority reduction to some language for $t=m/100$, then there exist collisionresistant hash functions. This improves on the result of (Harnik and Naor, STOC 2006), whose starting point is a cryptographic primitive (namely, oneway functions) rather than averagecase hardness, and whose assumption is a compressing ORreduction of SAT (which is now known to be false unless the polynomial hierarchy collapses). Along the way, we define a nonstandard onesided notion of averagecase hardness, which is the notion of hardness used in the second result above, that may be of independent interest.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. ITCS 2020
 DOI
 10.4230/LIPIcs.ITCS.2020.81
 Keywords
 compressioninformation lossoneway functionscollisionresistant hash functions
 Contact author(s)

prashantv91 @ gmail com
marshallball @ gmail com
alon rosen @ idc ac il  History
 20200602: revised
 20200409: received
 See all versions
 Short URL
 https://ia.cr/2020/395
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/395, author = {Marshall Ball and Elette Boyle and Akshay Degwekar and Apoorvaa Deshpande and Alon Rosen and Vinod Vaikuntanathan and Prashant Nalini Vasudevan}, title = {Cryptography from Information Loss}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/395}, year = {2020}, doi = {10.4230/LIPIcs.ITCS.2020.81}, url = {https://eprint.iacr.org/2020/395} }