Paper 2020/066

Talek: Private Group Messaging with Hidden Access Patterns

Raymond Cheng, William Scott, Elisaweta Masserova, Irene Zhang, Vipul Goyal, Thomas Anderson, Arvind Krishnamurthy, and Bryan Parno


Talek is a private group messaging system that sends messages through potentially untrustworthy servers, while hiding both data content and the communication patterns among its users. Talek explores a new point in the design space of private messaging; it guarantees access sequence indistinguishability, which is among the strongest guarantees in the space, while assuming an anytrust threat model, which is only slightly weaker than the strongest threat model currently found in related work. Our results suggest that this is a pragmatic point in the design space, since it supports strong privacy and good performance: we demonstrate a 3-server Talek cluster that achieves throughput of 9,433 messages/second for 32,000 active users with 1.7-second end-to-end latency. To achieve its security goals without coordination between clients, Talek relies on information-theoretic private information retrieval. To achieve good performance and minimize server-side storage, Talek intro- duces new techniques and optimizations that may be of independent interest, e.g., a novel use of blocked cuckoo hashing and support for private notifications. The latter provide a private, efficient mechanism for users to learn, without polling, which logs have new messages.

Available format(s)
Publication info
Published elsewhere. ACSAC 2020
Contact author(s)
me @ raymondcheng net
2020-12-16: last of 2 revisions
2020-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Raymond Cheng and William Scott and Elisaweta Masserova and Irene Zhang and Vipul Goyal and Thomas Anderson and Arvind Krishnamurthy and Bryan Parno},
      title = {Talek: Private Group Messaging with Hidden Access Patterns},
      howpublished = {Cryptology ePrint Archive, Paper 2020/066},
      year = {2020},
      doi = {10.1145/3427228.3427231},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.