Paper 2019/790

Simple and Efficient Approach for Achieving End-to-End Anonymous Communication

Wei Jiang, Adam Bowers, and Dan Lin

Abstract

Anonymous communication, that is secure end-to-end and unlinkable, plays a critical role in protecting user privacy by preventing service providers from using message metadata to discover communication links between any two users. Techniques, such as Mix-net, DC-net, time delay, cover traffic, Secure Multiparty Computation and Private Information Retrieval techniques, can be used to achieve anonymous communication. However, the existing solutions are very complex and difficult to implement in practice. More importantly, they do not offer security against malicious adversaries who can arbitrarily deviate from normal protocol execution, e.g., refusing to participate and modifying messages exchanged in the protocol. In this paper, we propose a simple and novel approach to establishing anonymous communication, easily implementable with servers having only communication and storage related capabilities. Our approach offers stronger security guarantee against malicious adversaries without incurring a great deal of extra computation and communication costs. We formally prove the security guarantee of the proposed solution and analyze its pros and cons comparing to the existing work.