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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ITCS 2020
- DOI
- 10.4230/LIPIcs.ITCS.2020.81
- Keywords
- compressioninformation lossone-way functionscollision-resistant hash functions
- Contact author(s)
-
prashantv91 @ gmail com
marshallball @ gmail com
alon rosen @ idc ac il - History
- 2020-06-02: revised
- 2020-04-09: 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} }