Robust Additive Randomized Encodings from IO and Pseudo-Non-linear Codes

Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function f(x₁,⋯,x_k) to locally computing encodings x^_i of each input x_i and then adding them together over some Abelian group into an output encoding y^=∑x^_i, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of 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 x^_i can be decomposed to non-interactive parts z^_i, generated in time proportional to the input size, and sent directly to the evaluator, and group parts g^_i that are added together, and whose size depends only on the security parameter.