Cryptology ePrint Archive: Report 2021/044
Aloha: Metadata-private voice communication over fully untrusted infrastructure
Ishtiyaque Ahmad and Yuntian Yang and Divyakant Agrawal and Amr El Abbadi and Trinabh Gupta
Abstract: Metadata from voice calls, such as the knowledge of who is communicating with whom, contains rich information about people’s lives. Indeed, it is a prime target for powerful adversaries such as nation states. Existing systems that hide voice call metadata either require trusted intermediaries in the network or scale to only tens of users. This paper describes the design, implementation, and evaluation of Aloha, the first system for voice communication that hides metadata over
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.
Category / Keywords: applications / private information retrieval, metadata private, voice communication
Date: received 11 Jan 2021
Contact author: ishtiyaque at ucsb edu
Available format(s): PDF | BibTeX Citation
Version: 20210112:131609 (All versions of this report)
Short URL: ia.cr/2021/044
[ Cryptology ePrint archive ]