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.

Suppose a user wants to broadcast an encrypted message to K recipients. With public-key encryption, the sender would construct K different ciphertexts, one for each recipient. The size of the broadcasted message then scales linearly with K. A natural question is whether the sender can encrypt the message with a ciphertext whose size scales \em sublinearly with the number of recipients.