CryptoDB
Additive Randomized Encodings from Public Key Encryption
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), {\em 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 {\em 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 {\em 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. |
BibTeX
@inproceedings{crypto-2025-35597,
title={Additive Randomized Encodings from Public Key Encryption},
publisher={Springer-Verlag},
author={Nir Bitansky and Saroja Erabelli and Rachit Garg},
year=2025
}