Welcome to the resource topic for 2022/1413
Title:
How to Compress Encrypted Data
Authors: Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
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 dependency on t in the 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) homomorphic additions and multiplications by constants.
The decompression complexity is dominated by \mathcal{O}(\xi\kappa t /\log t) decryption operations and equally many inversions of a pseudorandom permutation.
ePrint: https://eprint.iacr.org/2022/1413
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .