A Perfectly Correct Statistically Secure Additive Randomized Encoding

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Additive Randomized EncodingsShuffle Model

In an additive randomized encoding, each of \(k\) parties locally encodes its input as one element of an abelian group; the group sum of the encodings must reveal the value of a fixed function on the inputs and nothing else. The prevailing belief was that statistically secure such encodings do not exist even for equality on a small domain — the source refutes that belief and builds them for every finite function. Its encodings are only statistically correct: with small probability the evaluator gets the wrong answer, or in the sharper variant announces failure. In the computational setting perfect correctness is known. Whether it can be had statistically is the question.

View PDF · LaTeX source · Formal statement — not yet formalized

The object (the source’s Definition 2.1, after Halevi–Ishai–Kushilevitz–Rabin). For a \(k\)-party \(f : (\{0,1\}^n)^k \to \{0,1\}^m\), an ARE over an abelian group \((\mathbb{G},+)\) is a pair \((\mathsf{Enc}, \mathsf{Dec})\) with \(\hat x_i \leftarrow \mathsf{Enc}(x_i, i) \in \mathbb{G}\) randomized and \(\mathsf{Dec}\) deterministic, such that

  • \(\varepsilon\)-correctness: \(\Pr[\mathsf{Dec}(\sum_{i} \mathsf{Enc}(x_i,i)) = f(x_1,\dots,x_k)] \ge 1 - \varepsilon\) for all inputs; and
  • \(\delta\)-security: some simulator has \(\sum_i \mathsf{Enc}(x_i,i) \approx_\delta \mathsf{Sim}(f(x_1,\dots,x_k))\) for all inputs.

It is perfectly correct if \(\varepsilon = 0\). The group is assumed efficient: representation size \(c\log|\mathbb{G}|\) and operations in time \(|\mathbb{G}|^c\).

What is proved (the source’s Theorem 1.1). For any multi-party \(f : D^k \to D\) over a finite domain and any \(\varepsilon > 0\) there is an ARE for \(f\) with statistical correctness and security errors at most \(\varepsilon\).

Conjecture. For every \(k\), every finite \(D\), every \(f : D^k \to D\) and every \(\delta > 0\) there is an efficient abelian group and an ARE for \(f\) over it that is perfectly correct and \(\delta\)-secure.

How the source states it. The first item of Section 1.4 (“Open Questions”), page 7: “Perfect correctness. Does every \(f\) admit a perfectly correct and statistically secure ARE? For computationally secure ARE, perfect correctness is possible [HIKR23, BEG25]. For ARE with statistical security, we are only able to achieve a relaxed ‘Las Vegas’ notion of correctness, where the evaluator is never wrong but may declare failure with a small probability (see Appendix A).”

Las Vegas correctness is not perfect correctness. A decoder that may output a distinguished failure symbol, however rarely, is \(\varepsilon\)-correct under the definition above and does not settle this statement. That is exactly what the source’s Appendix A achieves, and exactly what stands between it and the question.

Efficiency is not part of the question. This is a feasibility statement over finite domains, matching Theorem 1.1, with no bound on ARE size beyond the group being efficient. The source’s separate size question — how close the ARE size of \(f\) can come to its garbling size, and whether efficient information-theoretic AREs extend from \(NL/\mathrm{poly}\) to all of \(P/\mathrm{poly}\), which it notes would settle a long-standing problem of Feige, Kilian and Naor — is different.

Sources

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open, and unusually close to something already achieved.

Toward the construction. The source’s Appendix A already gives a decoder that is never wrong, only sometimes silent. Removing the silence means either making the failure event impossible by construction — identifying what the decoder cannot distinguish and enlarging the group or the encoding so that it can — or supplying a default answer on failure whose (small) probability of being wrong the security proof can absorb without breaking simulation. The second move converts perfect correctness into a correctness error, so it only works if the default is provably right, which is the crux.

Toward an impossibility. Equality over a small domain is the natural candidate, since it is the function the earlier conjecture of Halevi, Ishai, Kushilevitz and Rabin singled out as unlikely to have a statistical ARE at all. Note that a negative answer is not excluded by the source’s Theorem 1.1: that theorem gives statistical correctness, and the whole content here is whether the error can be driven to exactly zero.

Checked against the literature, 2026-08-25. No proof, refutation or improvement found. Targeted check on a recent ePrint, not an exhaustive sweep.

Why the perfect/statistical/computational split is so sharp here. With computational security every efficient function has an ARE, under a Diffie–Hellman-type assumption in bilinear groups and later from any public-key encryption. With perfect security AREs exist only for degenerate functions — essentially OR and XOR with local pre- and post-processing. The statistical middle was expected to be empty, and the expectation had a reason: the conjecture that statistical AREs do not exist is implied by the (still open) conjecture that shuffle privacy is weaker than central privacy, so it was viewed as a possible stepping stone to separating those two models. The source’s refutation therefore also removes that route to the separation.

Two other questions in the same list. The source also asks whether information-theoretic feasibility extends to the robust ARE notion for finite functions — a positive answer even for finite \(3\)-party functions would settle the main open question on multi-party randomized encodings, and for all finite functions the main open question on best-possible information-theoretic MPC — and whether a two-party PSM protocol for \(f\) implies an ARE for \(f\) of similar cost on longer inputs. Neither is this statement.

What a reviewer should be suspicious of, in order. First, whether a claimed construction’s decoder can output anything other than a value of \(f\) — a failure symbol disqualifies it. Second, whether “perfectly correct” is being read as correctness for all inputs and all randomness, which is what \(\varepsilon = 0\) means here. Third, whether the group is efficient in the source’s sense, since an inefficient group would make the statement uninteresting rather than false.