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 C is tlossy if, for any distribution X over its inputs, the mutual information I(X;C(X)) ≤ 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 freduction to a language L' for a Boolean function f if there is a (randomized) polynomialtime algorithm C that takes an mtuple of strings X = (x_1,…,x_m), with each x_i ∈ {0,1}^n, and outputs a string z such that with high probability, L'(z) = f(L(x_1),L(x_2),…,L(x_m)). Suppose a language L has an freduction C to L' that is tlossy. 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 ≤ m/100, and L' is the same as L
 f is the Majority function, and t ≤ m/100
 f is the OR function, t ≤ 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 auxiliaryinput oneway functions.
2. Our second result is about the stronger notion of tcompressing freductions  reductions that only output t bits. We show that if there is an averagecase hard language L that has a tcompressing 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.
BibTeX  Entry
@InProceedings{ball_et_al:LIPIcs:2020:11766,
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}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {81:181:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11766},
URN = {urn:nbn:de:0030drops117667},
doi = {10.4230/LIPIcs.ITCS.2020.81},
annote = {Keywords: Compression, Information Loss, OneWay Functions, Reductions, Generic Constructions}
}
Keywords: 

Compression, Information Loss, OneWay Functions, Reductions, Generic Constructions 
Collection: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

06.01.2020 