  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 introduces 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.
