Statistical Quadratic Randomized Encodings for All Functions
A randomized encoding represents a function by a simpler randomized
function whose output reveals the original function’s value and nothing
else. In their seminal FOCS’00 paper, Ishai and Kushilevitz showed that
every function admits a degree-3 randomized encoding with perfect
correctness and privacy, whereas degree 2 is not universal with perfect
privacy. They asked whether this barrier can be bypassed by allowing
negligible statistical error. The question has since become a central open
problem in information-theoretic cryptography and remained open even for
computationally private encodings.
In this talk, I will present a positive resolution of this question: every
function admits a degree-2, 3-local randomized encoding with negligible
correctness and statistical privacy errors. The encoding is efficient for
functions in NC¹ and certain log-space classes. Moreover, assuming one-way
functions in NC¹, every polynomial-time computable function admits an
efficient degree-2 encoding with computational privacy.
I will describe the main ideas behind the construction, which combines a
simple quadratic gadget with privacy amplification based on Reed–Muller
codes, and discuss some of its implications for cryptography and secure
computation.