LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Statistical Quadratic Randomized Encodings for All Functions
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Statistical Quadratic Randomized Encodings for All Functions

63 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 3 m
Compared with MathematicsShorter than 75%
Source channelInstitute for Advanced Study (YouTube)