
Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions
Nir Bitansky of New York University presents a result in theoretical cryptography, delivered as part of a Computer Science/Discrete Mathematics seminar. He takes up the shuffle model, where n parties send private messages that arrive at an evaluator in random order, letting the evaluator compute a joint function while ideally learning nothing else. The open question is which functions admit statistically secure computation in this model, long conjectured to exclude even simple functions. Bitansky refutes that conjecture, showing every function can be computed with statistical security, and that any differentially private mechanism from the central curator model transfers to the shuffle model with the same utility. The construction rests on a statistically secure additive randomized encoding, which maps inputs to group elements whose sum reveals only the output. The talk works through the construction and its implications for differential privacy and non-interactive secure computation.