Cryptology ePrint Archive: Report 2021/1333

Paradoxical Compression with Verifiable Delay Functions

Thomas Pornin

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.

Category / Keywords: public-key cryptography / lossless compression, verifiable delay function, pigeons

Date: received 2 Oct 2021

Contact author: thomas pornin at nccgroup com

Available format(s): PDF | BibTeX Citation

Version: 20211005:154127 (All versions of this report)

Short URL: ia.cr/2021/1333