Shuffling Is Universal: Statistical Additive Randomized Encodings for All Functions

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 local model and the little-privacy, high-utility central curator model.