Paper 2021/1679
Incompressible Cryptography
Jiaxin Guan, Daniel Wichs, and Mark Zhandry
Abstract
Incompressible encryption allows us to make the ciphertext size flexibly large and ensures that an adversary learns nothing about the encrypted data, even if the decryption key later leaks, unless she stores essentially the entire ciphertext. Incompressible signatures can be made arbitrarily large and ensure that an adversary cannot produce a signature on any message, even one she has seen signed before, unless she stores one of the signatures essentially in its entirety. In this work, we give simple constructions of both incompressible public-key encryption and signatures under minimal assumptions. Furthermore, large incompressible ciphertexts (resp. signatures) can be decrypted (resp. verified) in a streaming manner with low storage. In particular, these notions strengthen the related concepts of disappearing encryption and signatures, recently introduced by Guan and Zhandry (TCC 2021), whose previous constructions relied on sophisticated techniques and strong, non-standard assumptions. We extend our constructions to achieve an optimal "rate", meaning the large ciphertexts (resp. signatures) can contain almost equally large messages, at the cost of stronger assumptions.
Note: Update Definition 7, and other small edits.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2022
- Keywords
- digital signaturespublic-key cryptographyfoundationsindistinguishability obfuscationincompressible encoding
- Contact author(s)
-
jiaxin @ guan io
danwichs @ gmail com
mzhandry @ gmail com - History
- 2022-05-12: last of 2 revisions
- 2021-12-22: received
- See all versions
- Short URL
- https://ia.cr/2021/1679
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1679,
author = {Jiaxin Guan and Daniel Wichs and Mark Zhandry},
title = {Incompressible Cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2021/1679},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1679}},
url = {https://eprint.iacr.org/2021/1679}
}
