End-to-end encryption is necessary for anything you wouldn’t want to be seen by your ISP or used against you in a court of law. Encrypted messaging services work by giving every user of an app a public key and a private key.
While these services hide message content, malicious users can often use network metadata to infer other information, such as the identity of users exchanging messages, when they are communicating, where their messages are sent, and how much data is transferred between them.
To ensure even greater security, scientists from the University of Washington and Carnegie Mellon University have developed a new messaging system called Talek. This unique messenger hides both messages’ content and general communication patterns between users, including their identity.
To achieve its security goals without coordination between clients, Talek relies on the information-theoretic private information retrieval (PIR) technique. To achieve good performance and minimize server-side storage, Talek introduces new techniques and optimizations that may be of independent interest, e.g., novel use of blocked cuckoo hashing and support for private notifications.
Raymond Cheng, one of the researchers who carried out the study, said, “More and more of our communications online are encrypted, which makes it harder for adversaries to see the contents of what we say. Talek takes this a step further, making it harder for those same adversaries to learn who is talking with whom.”
The messaging system allows users to communicate with one another without sharing their identities with the server. It achieves this by hiding requests for information within random-looking requests.
A key advantage of Talek is that while acknowledging it might be computationally costly, it very well may be done proficiently on GPUs. Likewise, its novel structure permits clients to shroud ongoing conversations and communication patterns.
Cheng said, “Prior work aimed at developing new messaging systems either offered strong security guarantees with prohibitive computational costs or weaker security guarantees with practical performance. Our work strives to provide a middle ground, bringing strong security guarantees (i.e., a security goal where any two access patterns between users are indistinguishable to the server), with a performance that would satisfy many real messaging workloads.
Alongside PIR, Talek employs a new component called the ‘oblivious log,’ as PIR was insufficient to create a fully functioning messaging service.
Scientists have already built a working prototype of Talek with three servers and shown that it can be scaled to support real messaging workloads, achieving a throughput of 9,433 messages per second with 32,000 active users and an end-to-end latency of 1.7 seconds.
Cheng said, “We are excited by the prospect of being able to provide a messaging service with strong security goals based on indistinguishability of access patterns, with sufficient performance to handle real-world messaging workloads. We hope that these ideas can be directly applied to messaging services to improve user privacy.”
Additional features of the messaging system include:
- Users can then store the messages they write to others according to this sequence of addresses. On the other hand, those receiving the messages can read them privately and securely using PIR.
- It allows users to learn when their private logs and conversations have new messages without polling.
Cheng said, “Privacy-preserving technology has come a long way, but there remain several difficult technical challenges to bringing strong security guarantees to the multitude of applications that we depend on a daily basis. We look forward to continuing our research into privacy-preserving technologies.”
This new messaging system is presented in a paper pre-published on arXiv.
