fully untrusted infrastructure and scales to tens of thousands of users. At a high level, Aloha follows a template in which
callers and callees deposit and retrieve messages from private mailboxes hosted at an untrusted server. However, Aloha improves message latency in this architecture, which is a key performance metric for voice calls. First, it enables a caller to push a message to a callee in two hops, using a new way of assigning mailboxes to users that resembles how a post office assigns PO boxes to its customers. Second, it innovates on the underlying cryptographic machinery and constructs a
new private information retrieval (PIR) scheme, QuickPIR, that reduces the time to process oblivious access requests for mailboxes. An evaluation of Aloha on a cluster of eighty machines on AWS demonstrates that it can serve 32K users with a 99-th percentile message latency of 726 ms–a 7× improvement over prior work in the same threat model.