Degree-2 Statistical Randomized Encodings for Every Finite Function
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
A randomized encoding replaces \(f(x)\) by a randomized \(\hat f(x;r)\) whose output determines \(f(x)\) and reveals nothing else. The point is that \(\hat f\) can be far simpler than \(f\), and the standard measure of simplicity is algebraic degree in the indeterminates \((x,r)\) jointly. Every finite function has an encoding of degree 3 — that is classical, and it is why so much of secure computation reduces to degree-3 objects. Degree 2 is a different matter: with perfect privacy it is known impossible for some functions, and with a small privacy error allowed nobody has known the answer since the question was posed in 2000. The harvested paper shows one thing a positive answer would buy: a complete 3-party functionality for two-round black-box MPC, where today only a 4-party one is known.
View PDF · LaTeX source · Formal statement — not yet formalized
The object. Let \(f : \{0,1\}^n \to \{0,1\}^m\) be a finite function. A randomized \(\hat f : \{0,1\}^n \times \{0,1\}^\rho \to \{0,1\}^s\) is an \(\varepsilon\)-statistically private randomized encoding of \(f\) if
- Correctness: there is a decoder with \(\mathrm{Dec}(\hat f(x;r)) = f(x)\) for every \(x\) and every \(r\); and
- Privacy: there is a simulator with \(\mathrm{SD}(\hat f(x;r), \mathrm{Sim}(f(x))) \le \varepsilon\) for every \(x\), over uniform \(r\).
It has degree \(d\) if every output coordinate of \(\hat f\), as a polynomial over \(\mathbb{F}_2\) in the indeterminates \((x,r)\), has total degree at most \(d\). Privacy is perfect when \(\varepsilon = 0\).
Conjecture. Every finite function \(f\) admits a degree-2 statistical randomized encoding: for every \(\varepsilon > 0\) there is an \(\varepsilon\)-statistically private randomized encoding of \(f\) of degree 2.
How the harvested paper states it. Question 1.6: “Does every finite function admit a degree-2 statistical randomized encoding?” It adds that the question “has been put forward as a barrier for solving other questions”, and a second paper in the same harvest batch — Halevi, Ishai, Kushilevitz and Rabin on additive randomized encodings — independently calls it “[t]he main open question about RE … open for over 20 years”.
Attribution. This is not the harvested paper’s own question. It is Question 1.6 there, attributed to Ishai and Kushilevitz and to Applebaum, Ishai and Kushilevitz, and described as open “for almost 20 years”. What the harvested paper contributes is Proposition 1.7 and the two barrier observations in its open-problems list. A resolution belongs to the older question.
The new consequence (the harvested paper’s Proposition 1.7). For \(d \le p\), let \((d,p)\text{-}\mathrm{MULTPlus}\) be the \(p\)-party functionality in which each of the first \(d\) parties holds \((x_i, z_i)\) and the product-sum \(\prod_i x_i + \sum_i z_i\) over \(\mathbb{F}_2\) is delivered to all \(p\) parties; standard 2-party OT is equivalent to \((2,2)\text{-}\mathrm{MULTPlus}\) under strict round-preserving black-box (RPBB) reductions. The paper’s Theorem 1.5 shows \((3,4)\text{-}\mathrm{MULTPlus}\) is MPC-complete under strict RPBB reductions, and its main negative result rules out any 2-party functionality playing that role. Proposition 1.7: “A positive answer to Question 1.6 would imply that Theorem 1.5 holds with \((2,3)\text{-}\mathrm{MULTPlus}\) instead of \((3,4)\text{-}\mathrm{MULTPlus}\). In particular, it would imply that there is a complete 3-party functionality with respect to strict RPBB reductions.”
Sources
- Applebaum, Brakerski, Garg, Ishai and Srinivasan. Separating Two-Round Secure Computation from Oblivious Transfer. IACR ePrint 2020/116. The harvested paper. Question 1.6 and Proposition 1.7 are on pages 5–6, Theorem 1.5 and the \((d,p)\text{-}\mathrm{MULTPlus}\) definition on page 5, and the open-problems list in Section 1.3, pages 9–10.
- Ishai and Kushilevitz. Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. FOCS 2000. Where the question was first posed, and the source of the negative results for perfectly private degree-2 encodings.
- Applebaum, Ishai and Kushilevitz. Cryptography in NC⁰. FOCS 2004. The other work the harvested paper attributes Question 1.6 to.
- Halevi, Ishai, Kushilevitz and Rabin. Additive Randomized Encodings and Their Applications. IACR ePrint 2023/870. Independently flags this as the main open question about randomized encodings, and explains why the ARE and degree-2 RE classes are incomparable. Also the source of c/0083.
- Garg, Ishai and Srinivasan. Two-Round MPC: Information-Theoretic and Black-Box. TCC 2018. Gives black-box 2-round protocols from group-based primitives with a PKI setup, and the non-black-box construction of client-server 2-round MPC that the harvested paper asks to make black-box.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open in both directions for twenty-six years, with no candidate technique publicly on either side.
Why perfect and statistical part company here. Negative results are known for perfectly private degree-2 encodings. That does not settle the conjecture, and the gap between the two is the whole content of the question: allowing a small privacy error is exactly what the known impossibility arguments do not survive. Anyone attacking the negative direction should expect to need a technique that tolerates error; anyone attacking the positive direction should not expect perfect correctness to be the obstacle, since the definition above asks for perfect correctness and only statistical privacy, matching the question as posed.
Both directions have named consequences. A positive answer gives a complete 3-party functionality for two-round black-box MPC. A negative answer is what would be required to extend the harvested paper’s 2-round impossibility to 3-round protocols, and to rule out a 3-party complete functionality — so two of that paper’s own remaining open problems are blocked on the negative direction specifically. It is unusual for a question this old to have both answers pay.
Checked against the literature, 2026-08-27. No resolution found, and two papers dated 2020 and 2023 both describe it as open. Targeted check on the randomized-encoding line, not an exhaustive sweep.
Why degree 2 is the boundary that matters. Degree-3 encodings are what make so many secure-computation results possible at all, and each drop in degree translates into a simpler complete functionality, a shorter protocol, or a weaker assumption. Degree 2 over \(\mathbb{F}_2\) is the last non-trivial level: degree 1 encodings are affine and cannot hide anything interesting.
The neighbouring ARE question is a different question. Halevi, Ishai, Kushilevitz and Rabin note that the class of functions admitting statistical degree-2 encodings seems incomparable to the class admitting statistical additive randomized encodings, even restricting ARE to one input bit per party: the mod-2 inner product trivially has a degree-2 encoding but was conjectured to have no ARE, while capped sum has a statistical ARE. So this is not a reformulation of any ARE question, and progress on one does not automatically transfer.
What a reviewer should be suspicious of, in order. First, the degree convention: total degree in \((x,r)\) jointly, not degree in \(x\) with \(r\) treated as coefficients — the latter is a much weaker requirement and encodings meeting it are routine. Second, whether the privacy is statistical and the correctness perfect, in that combination; a construction with correctness error is answering a different question. Third, whether the functions covered are all finite functions or a class, since partial classes have been known for decades.