Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions - Nir Bitansky @videosfromIAS
Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions - Nir Bitansky  @videosfromIAS
Uploaded May 2026 | Updated November 2026, 1 day ago
Computer Science/Discrete Mathematics Seminar I
11:00am|West Lecture Hall and Remote Access
Topic: Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions
Speaker: Nir Bitansky
Affiliation: New York University
Date: May 18, 2026

The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows n parties holding private inputs x1,…,xn to simultaneously send messages to an evaluator, so that the messages are received in a random order. The evaluator can then compute a joint function f(x1,…,xn), ideally while learning nothing else about the private inputs. The model has become increasingly popular both in cryptography, as an alternative to non-interactive secure computation in trusted setup models, and even more so in differential privacy, as an intermediate between the high-privacy, little-utility {\em local model} and the little-privacy, high-utility {\em central curator model}.

The main open question in this context is which functions f can be computed in the shuffle model with {\em statistical security.} While general feasibility results were obtained using public-key cryptography, the question of statistical security has remained elusive. The common conjecture has been that even relatively simple functions cannot be computed with statistical security in the shuffle model.

We refute this conjecture, showing that {\em all} functions can be computed in the shuffle model with statistical security. In particular, any differentially private mechanism in the central curator model can also be realized in the shuffle model with essentially the same utility, and while the evaluator learns nothing beyond the central model result.

This feasibility result is obtained by constructing a statistically secure {\em additive randomized encoding} (ARE) for any function. An ARE randomly maps individual inputs to group elements whose sum only reveals the function output.
Similarly to other types of randomized encoding of functions, our statistical ARE is efficient for functions in NC1 or NL. Alternatively, we get computationally secure ARE for all polynomial-time functions using a one-way function. More generally, we can convert any (information-theoretic or computational) ``garbling scheme'' to an ARE with a constant-factor size overhead.

Joint work with Saroja Erabelli, Rachit Garg, and Yuval Ishai.
Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions - Nir BitanskyLagrangian Hofer-Zehnder Capacities and Energy-Capacity Inequalities - Sam LisiInvariants of Legendrian Knots in Thickened Convex Surfaces - Nancy EaglesRock n roll in the Solar system and beyond: Interstellar seeds, snowmen and.... - Hagai PeretsThe Ultra-Relativistic Limit of Black Hole Collisions - Frans PretoriusC0-rigidity in contact topology via microlocal sheaf theory. - Wenyuan LiLorentzian Conformal Field Theory - Part 4 - Simon Caron-HuotWhat is Universality in AdS/CFT? - Eric PerlmutterWave dark matter (and black holes) - Lam Huide Sitter Quantum Cosmology - Part 2 - Jordan CotlerTitle Kupka-Smale Genericity in Analytic Convex Billiards - Inmaculada Concepcion Baldomá BarracaGeometry and Dynamics of Domains in the Cotangent Bundles of Tori - Jun
Institute for Advanced Study |

Shuffling is Universal: Statistical Additive Randomized Encodings for All Functions - Nir Bitansky

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER