Welcome to the resource topic for 2023/946
Title:
Compressing Encrypted Data Over Small Fields
Authors: Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
Abstract:\newcommand{\gen}{\mathsf{Gen}}\newcommand{\enc}{\mathsf{Enc}}\newcommand{\dec}{\mathsf{Dec}}
A recent work of Fleischhacker, Larsen, and Simkin (Eurocrypt 2023) shows how to efficiently compress encrypted sparse vectors.
Subsequently, Fleischhacker, Larsen, Obremski, and Simkin (Eprint 2023) improve upon their work and provide more efficient constructions solving the same problem.
Being able to efficiently compress such vectors is very useful in a variety of applications, such as private information retrieval, searchable encryption, and oblivious message retrieval.
Concretely, assume one is given a vector (m_1, \dots, m_n) with at most t distinct indices i \in [n], such that m_i \neq 0 and assume (\gen,\enc, \dec) is an additively homomorphic encryption scheme.
The authors show that one can compress (\enc(k, m_1), \dots, \enc(k, m_n)), without knowing the secret key k, into a digest with size dependent on the upper bound on the sparsity t, but not on the total vector length n.
Unfortunately, all existing constructions either only work for encryption schemes that have sufficiently large plaintext spaces or require additional encrypted auxiliary information about the plaintext vector.
In this work, we show how to generalize the results of Fleischhacker, Larsen, and Simkin to encryption schemes with arbitrarily small plaintext spaces.
Our construction follows the same general ideas laid out in previous works but modifies them in a way that allows compressing the encrypted vectors correctly with high probability, independently of the size of the plaintext space.
ePrint: https://eprint.iacr.org/2023/946
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 .