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
[ Cryptology ePrint archive ]