
Statistical Quadratic Randomized Encodings for All Functions
Benny Applebaum of Tel Aviv University presents this Institute for Advanced Study Computer Science and Discrete Mathematics seminar on randomized encodings, a cryptographic tool that represents a function by a simpler randomized function whose output reveals only the original value and nothing more. Applebaum opens with the 2000 result by Ishai and Kushilevitz showing every function has a degree-3 encoding with perfect correctness and privacy, and the open question of whether degree-2 encodings are possible if a negligible statistical error is allowed. He then presents his own resolution: every function admits a degree-2, 3-local encoding with negligible statistical error, efficient for NC1 and some log-space classes, and extends to computational privacy for all polynomial-time functions given one-way functions in NC1. He walks through the construction, a quadratic gadget combined with privacy amplification via Reed-Muller codes, and closes on implications for secure computation. Technical and aimed at researchers in theoretical cryptography.