TY - GEN
T1 - How to Compress Encrypted Data
AU - Fleischhacker, Nils
AU - Larsen, Kasper Green
AU - Simkin, Mark
PY - 2023/4
Y1 - 2023/4
N2 - We study the task of obliviously compressing a vector comprised of n ciphertexts of size ξ 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 O(tξ) bits. Compression can be performed homomorphically by performing O(nlog n) homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of Ω(n). Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability 1 - 2
-
κ. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into O(ξκt/ log t) bits, where κ≥ log t. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by O(nκ/ log t) homomorphic additions and multiplications by constants. The decompression complexity is dominated by O(κt/ log t) decryption operations and equally many inversions of a pseudorandom permutation.
AB - We study the task of obliviously compressing a vector comprised of n ciphertexts of size ξ 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 O(tξ) bits. Compression can be performed homomorphically by performing O(nlog n) homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of Ω(n). Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability 1 - 2
-
κ. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into O(ξκt/ log t) bits, where κ≥ log t. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by O(nκ/ log t) homomorphic additions and multiplications by constants. The decompression complexity is dominated by O(κt/ log t) decryption operations and equally many inversions of a pseudorandom permutation.
UR - http://www.scopus.com/inward/record.url?scp=85161408288&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-30545-0_19
DO - 10.1007/978-3-031-30545-0_19
M3 - Article in proceedings
SN - 978-3-031-30544-3
T3 - Lecture Notes in Computer Science
SP - 551
EP - 577
BT - Advances in Cryptology – EUROCRYPT 2023
A2 - Hazay, Carmit
A2 - Stam, Martijn
PB - Springer
CY - Cham
ER -