Paper 2021/1333

Paradoxical Compression with Verifiable Delay Functions

Thomas Pornin


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
lossless compressionverifiable delay functionpigeons
Contact author(s)
thomas pornin @ nccgroup com
2021-10-05: received
Short URL
Creative Commons Attribution


      author = {Thomas Pornin},
      title = {Paradoxical Compression with Verifiable Delay Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1333},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.