eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2021/044

Addra: Metadata-private voice communication over fully untrusted infrastructure

Ishtiyaque Ahmad, Yuntian Yang, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta


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 Addra, 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, Addra follows a template in which callers and callees deposit and retrieve messages from private mailboxes hosted at an untrusted server. However, Addra 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 scheme, FastPIR, that reduces the time to process oblivious access requests for mailboxes. An evaluation of Addra on a cluster of 80 machines on AWS demonstrates that it can serve 32K users with a 99-th percentile message latency of 726 ms—a 7× improvement over a prior system for text messaging in the same threat model.

Available format(s)
Publication info
Published elsewhere. Minor revision. OSDI 2021
private information retrievalmetadata privatevoice communication
Contact author(s)
ishtiyaque @ ucsb edu
2021-05-25: revised
2021-01-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ishtiyaque Ahmad and Yuntian Yang and Divyakant Agrawal and Amr El Abbadi and Trinabh Gupta},
      title = {Addra: Metadata-private voice communication over fully untrusted infrastructure},
      howpublished = {Cryptology ePrint Archive, Paper 2021/044},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/044}},
      url = {https://eprint.iacr.org/2021/044}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.