CryptoDB
Robust Additive Randomized Encodings from IO and Pseudo Non-Linear Codes
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function f (x_1, . . . , x_k ) to locally computing encodings hat{x}_i of each input xi and then adding them together over some Abelian group into an output encoding hat{y} = ∑ hat{x}_i, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of hat{x}_i, reveals only the residual function obtained by restricting the corresponding inputs. The appeal of (R)ARE comes from the simplicity of the interactive part of the computation, involving only addition, which yields for instance non-interactive multi-party computation in the shuffle model where messages from different parties are anonymously shuffled. Halevi, Ishai, Kushilevitz, and Rabin constructed ARE from standard assumptions and RARE in the ideal obfuscation model, leaving open the question of whether RARE can be constructed in the plain model. We construct RARE in the plain model from indistinguishability obfuscation, which is necessary, and a new primitive that we call pseudo-non-linear codes. We provide two constructions of this primitive assuming either Learning with Errors or Decision Diffie Hellman. A bonus feature of our construction is that it is succinct. Specifically, encodings hat{x}_i can be decomposed to non-interactive parts hat{z}_i, generated in time proportional to the input size, and sent directly to the evaluator, and group parts hat{g}_i that are added together, and whose size depends only on the security parameter. |
BibTeX
@inproceedings{crypto-2024-34189,
title={Robust Additive Randomized Encodings from IO and Pseudo Non-Linear Codes},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68397-8_4},
author={Nir Bitansky and Sapir Freizeit},
year=2024
}