Degree-2 randomized encodings
Degree 3 is classical, degree 1 is useless, and the level between has been open since 2000
Motivation
A randomized encoding replaces a function \(f(x)\) by a randomized \(\hat f(x;r)\) whose output determines \(f(x)\) and is simulatable from it. Its value is that \(\hat f\) can be structurally much simpler than \(f\): a protocol for the complicated function can be replaced by a protocol for the simple one. Algebraic degree, in the indeterminates \((x,r)\) jointly, is the standard measure of that simplicity, and it is the measure that translates most directly into protocol structure — a degree-\(d\) encoding is what lets a \(d\)-wise interaction pattern suffice.
The classical fact is that every finite function admits a degree-3 encoding, and a great deal of secure computation is built on exactly that. Degree 1 is affine and hides nothing. So the whole question is degree 2, and it splits sharply on the privacy notion: with perfect privacy some functions provably have no degree-2 encoding, while with a small privacy error permitted, nobody knows.
Provenance and history
Ishai and Kushilevitz introduced randomizing polynomials at FOCS 2000, proved the negative results for perfectly private degree 2, and posed the statistical question. Applebaum, Ishai and Kushilevitz developed the notion in Cryptography in NC⁰. The question has stood since.
Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai and Akshayaram Srinivasan, Separating Two-Round Secure Computation from Oblivious Transfer (IACR ePrint 2020/116), record it as their Question 1.6, attribute it to those two papers, describe it as open for almost 20 years, and note it “has been put forward as a barrier for solving other questions”. What they add is a consequence. Writing \((d,p)\text{-}\mathrm{MULTPlus}\) for the \(p\)-party functionality in which each of the first \(d\) parties holds \((x_i,z_i)\) and \(\prod_i x_i + \sum_i z_i\) over \(\mathbb{F}_2\) goes to all \(p\) parties, their Theorem 1.5 shows \((3,4)\text{-}\mathrm{MULTPlus}\) is MPC-complete under strict round-preserving black-box reductions, while their main negative result rules out any 2-party functionality in that role. Their Proposition 1.7: a positive answer to Question 1.6 would let \((2,3)\text{-}\mathrm{MULTPlus}\) replace it, giving a complete 3-party functionality.
The barrier appears twice more in their open problems, and there it is the negative answer that is needed: extending their 2-round impossibility to 3-round protocols, and ruling out a 3-party complete functionality, each require Question 1.6 to fail.
Halevi, Ishai, Kushilevitz and Rabin, in the additive-randomized-encodings paper of 2023, independently call this “[t]he main open question about RE … open for over 20 years”, and note that the class of functions with statistical degree-2 encodings appears incomparable to the class with statistical additive randomized encodings: mod-2 inner product has a trivial degree-2 encoding but was conjectured to have no ARE, while capped sum has a statistical ARE. Progress on one does not transfer to the other, which is why this hub is separate from additive randomized encodings.
Parameter lattice
Degree against privacy notion, for finite functions.
| Degree | Perfect privacy | Statistical privacy |
|---|---|---|
| 1 (affine) | impossible for anything non-trivial | same |
| 2 | impossible for some functions (Ishai–Kushilevitz) | c/0088 — open since 2000 |
| 3 | known for every finite function | known for every finite function |
What each answer to the degree-2 statistical question would settle:
| Answer | Consequence |
|---|---|
| Positive | \((2,3)\text{-}\mathrm{MULTPlus}\) is MPC-complete under strict RPBB reductions — a complete 3-party functionality, where only a 4-party one is known |
| Negative | unblocks extending the 2-round impossibility to 3 rounds, and ruling out a 3-party complete functionality |