Paper 2022/1413

How to Compress Encrypted Data

Nils Fleischhacker, Ruhr University Bochum
Kasper Green Larsen, Aarhus University
Mark Simkin, Ethereum Foundation

We study the task of obliviously compressing a vector comprised of $n$ ciphertexts of size $\xi$ bits each, where at most $t$ of the corresponding plaintexts are non-zero. This problem commonly features in applications involving encrypted outsourced storages, such as searchable encryption or oblivious message retrieval. We present two new algorithms with provable worst-case guarantees, solving this problem by using only homomorphic additions and multiplications by constants. Both of our new constructions improve upon the state of the art asymptotically and concretely. Our first construction, based on sparse polynomials, is perfectly correct and the first to achieve an asymptotically optimal compression rate by compressing the input vector into $\mathcal{O}(t \xi)$ bits. Compression can be performed homomorphically by performing $\mathcal{O}(n \log n)$ homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of $\Omega(\sqrt{n})$. Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability $1-2^{-\kappa}$. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into $\mathcal{O}(\xi\kappa t /\log t)$ bits, where $\kappa \geq \log t$. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by $\mathcal{O}(n \kappa/\log t)$ homomorphic additions and multiplications by constants. The decompression complexity is dominated by $\mathcal{O}(\kappa t /\log t)$ decryption operations and equally many inversions of a pseudorandom permutation.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2023
CompressionOutsourced StorageHomomorphic Encryption
Contact author(s)
mail @ nilsfleischhacker de
larsen @ cs au dk
mark simkin @ ethereum org
2023-02-23: revised
2022-10-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Kasper Green Larsen and Mark Simkin},
      title = {How to Compress Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1413},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.