Welcome to the resource topic for 2025/104
Title:
Additive Randomized Encodings from Public Key Encryption
Authors: Nir Bitansky, Saroja Erabelli, Rachit Garg
Abstract:Introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), Additive randomized encodings (ARE) reduce the computation of a k-party function f(x_1,\dots,x_k) to locally computing encodings \hat x_i of each input x_i and then adding them together over some Abelian group into an output encoding \hat y = \sum \hat x_i, which reveals nothing but the result. The appeal of ARE comes from the simplicity of the non-local computation, involving only addition. This gives rise for instance to non-interactive secure function evaluation in the shuffle model where messages from different parties are anonymously shuffled before reaching their destination. Halevi, Ishai, Kushilevitz, and Rabin constructed ARE based on Diffie-Hellman type assumptions in bilinear groups.
We construct ARE assuming public-key encryption. The key insight behind our construction is that one-sided ARE, which only guarantees privacy for one of the parties, are relatively easy to construct, and yet can be lifted to full-fledged ARE. We also give a more efficient black-box construction from the CDH assumption.
ePrint: https://eprint.iacr.org/2025/104
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 .