Additive randomized encodings
One group element per party, their sum reveals the output, and nothing else
Motivation
Non-interactive secure computation in the shuffle model is the one corner of MPC whose information-theoretic feasibility was, until recently, wide open. The model is austere: \(n\) parties each send anonymous messages to a server, the server should learn \(f\) of their inputs and essentially nothing more, and there is no setup, no correlated randomness, no interaction. Its algebraic heart is additive randomized encodings, because shuffling is enough for secure addition — so any function with an ARE can be securely computed in the shuffle model.
An ARE asks each party to compress its input into a single group element such that the sum of all of them is a randomized encoding of the output. How much accuracy the simulation must have turns out to change the answer completely: perfect security admits almost nothing, computational security admits everything efficient, and the statistical middle was believed empty.
Provenance and history
Halevi, Ishai, Kushilevitz and Rabin introduced ARE (CRYPTO 2023) along with a robust variant, showed every efficient function has a computationally secure ARE under a Diffie–Hellman-type assumption in bilinear groups, and showed perfect security admits only degenerate functions. They also conjectured, strongly, that statistical AREs do not exist — even for equality over small domains — a conjecture implied by the conjecture that shuffle privacy is weaker than central privacy, and so viewed as a possible stepping stone to separating those models. Bitansky, Erabelli and Garg reduced the computational construction to any public-key encryption; Hiwatashi (ACNS 2025) ruled out \(\ell_2\)-norm variants.
Bitansky, Erabelli, Garg and Ishai, Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions (IACR ePrint 2025/1442), refute the conjecture: every finite function has an ARE with statistical correctness and security errors as small as desired. They also tie ARE size to garbling size, giving efficient statistical AREs for \(NL/\mathrm{poly}\) and computational ones for \(P/\mathrm{poly}\) from any one-way function, used only as a black box. What their constructions do not give is perfect correctness. Nor do they give robustness: HIKR23’s main open question covered the robust and non-robust notions together and conjectured both impossible, and only the non-robust half has fallen. The robust half is re-posed in the later paper’s own open-questions list, restricted to finite functions because robust ARE for general functions over large domains implies obfuscation.
Parameter lattice
Two axes. First, security accuracy against correctness accuracy, for the non-robust notion.
| Perfect correctness | Statistical correctness | |
|---|---|---|
| Perfect security | only degenerate functions (OR/XOR with local pre- and post-processing) | same |
| Statistical security | c/0073 — open; Las Vegas correctness (never wrong, may fail) is achieved | every finite function, Theorem 1.1 |
| Computational security | every efficient function, from any public-key encryption | same |
Second, robustness — whether the evaluator may collude with some parties and so see the sum over the honest ones alone, conceding the residual function to the simulator.
| Non-robust | Robust | |
|---|---|---|
| Perfect security | degenerate functions only | degenerate functions only |
| Statistical security, finite \(f\) | every finite function (Bitansky–Erabelli–Garg–Ishai, refuting HIKR23’s conjecture) | c/0083 — open |
| Statistical security, general \(f\) | not the question: the constructions and the refutation are for finite domains | implies obfuscation, so not an information-theoretic question |
| Computational security | from any public-key encryption | from resettable MPC; from iO plus standard assumptions rather than ideal obfuscation is open |