Paper 2021/1333 Original: eprint.iacr.org/2021/1333 ↗
Paradoxical Compression with Verifiable Delay Functions
Abstract
Lossless compression algorithms such as DEFLATE strive to reliably process arbitrary inputs, while achieving compressed sizes as low as possible for commonly encountered data inputs. It is well-known that it is mathematically impossible for a compression algorithm to simultaneously achieve non-trivial compression on some inputs (i.e. compress these inputs into strictly shorter outputs) and to never expand any other input (i.e. guaranteeing that all inputs will be compressed into an output which is no longer than the input); this is a direct application of the "pigeonhole principle". Despite their mathematical impossibility, we show in this paper how to build such paradoxical compression and decompression algorithms, with the aid of some tools from cryptography, notably verifiable delay functions, and, of course, by slightly cheating.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2021-10-05: last updated
- 2021-10-05: published
- Short URL
- https://ia.cr/2021/1333
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2021/1333,
author = {Thomas Pornin},
title = {Paradoxical Compression with Verifiable Delay Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1333},
year = {2021},
url = {https://eprint.iacr.org/2021/1333}
}