Paper 2022/1413

How to Compress Encrypted Data

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

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in EUROCRYPT 2023
Keywords
CompressionOutsourced StorageHomomorphic Encryption
Contact author(s)
mail @ nilsfleischhacker de
larsen @ cs au dk
mark simkin @ ethereum org
History
2023-02-23: revised
2022-10-18: received
See all versions
Short URL
https://ia.cr/2022/1413
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1413,
      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},
      url = {https://eprint.iacr.org/2022/1413}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.