Paper 2026/1937

Robust Additive Randomized Encodings With Transparent Setup

Abstract

Additive randomized encodings (AREs) reduce the computation of an m-party function f(x1, . . . , xm) to independently encoding each input and adding the resulting encodings in an Abelian group, so that their sum reveals nothing but the output. Robust AREs (RAREs) additionally protect against collusions between the evaluator and some of the parties, guaranteeing that even if some of the input encodings are completely controlled by the adversary, the partial sum of the remaining (honest) input encodings leaks no more than the residual function f(x_H, ·) obtained by fixing the honest inputs x_H. Much of the appeal of RAREs come from the fact that they imply robust non-interactive secure computation in the shuffle model, where parties send messages to the evaluator through anonymous communication channels. Existing constructions of general-purpose RARE either assume ideal obfuscation or rely on structured public parameters generated using secret randomness that must remain hidden. We construct general-purpose RARE with transparent setup. Assuming indistinguishability obfuscation (which is necessary) and LWE, both with subexponential security, we show that every efficient function admits an efficient RARE in the common random string model. We also show how to eliminate public parameters altogether in the honest-majority setting. The main technical observation behind our construction is that non-robust ARE, which exist assuming only one-way functions, can be leveraged to protect from spoofing of honest party encodings.