Additive Randomized Encodings from Public Key Encryption

ePrint Report: Additive Randomized Encodings from Public Key Encryption
Nir Bitansky, Saroja Erabelli, Rachit Garg

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.

Go to Source