Anonymous Messaging - July 2017

Public Audience
Purpose: To highlight project progress. Information is generally at a higher level which is accessible to the interested public. All information contained in the report (regions 1-3) is a Government Deliverable/CDRL.

PI(s): Pramod Viswanath

Co-PI(s): Carl Gunter and Nikita Borisov

Researchers: Giulia Fanti, Jiaqi Mu, Ashok Vardhan Makkuva, Hyun Bin Lee, and Vincent Bindschaedler

HARD PROBLEM(S) ADDRESSED
This refers to Hard Problems, released November 2012.

Hard problem: Scalability and Composability

Anonymity is a basic right and a core aspect of Internet. Recently, there has been tremendous interest in anonymity and privacy in social networks, motivated by the natural desire to share one's opinions without the fear of judgment or personal reprisal (by parents, authorities, and the public).

In the first thread of this project, we propose to study the fundamental questions associated with building such a semi-distributed, anonymous messaging platform, which aims to keep anonymous the identity of the source who initially posted a message as well as the identity of the relays who approved and propagated the message.

Analyzing large datasets containing social networks or other potentially sensitive data often leads to privacy or anonymity concerns. In the second thread, we propose to explore the privacy risks associated with analyzing anonymized datasets. In particular, we focus on the privacy threats that stem from the use of different visualization techniques. We develop formal models of privacy protection measure on various visualization products created from large datasets.

PUBLICATIONS
Papers published in this quarter as a result of this research. Include title, author(s), venue published/presented, and a short description or abstract. Identify which hard problem(s) the publication addressed. Papers that have not yet been published should be reported in region 2 below.

[1] G. Fanti, S. Venkatakrishnan and P. Viswanath, "Dandelion: Redesigning BitCoin Networking for Anonymity", ACM Sigmetrics 2017, Urbana, IL, June 5-9, 2017.

Abstract: Bitcoin and other cryptocurrencies have surged in popularity over the last decade. Although Bitcoin does not claim to provide anonymity for its users, it enjoys a public perception of being a `privacy-preserving' financial system. In reality, cryptocurrencies publish users' entire transaction histories in plaintext, albeit under a pseudonym; this is required for transaction validation. Therefore, if a user's pseudonym can be linked to their human identity, the privacy fallout can be significant. Recently, researchers have demonstrated deanonymization attacks that exploit weaknesses in the Bitcoin network's peer-to-peer (P2P) networking protocols. In particular, the P2P network currently forwards content in astructured way that allows observers to deanonymize users. In this work, we redesign the P2P network from first principles with the goal of providing strong, provable anonymity guarantees. We propose a simple networking policy called Dandelion, which achieves nearly-optimal anonymity guarantees at minimal cost to the network's utility. We also provide a practical implementation of Dandelion for deployment.

[2] G. Fanti and P. Viswanath, "Anonymity properties of the Bitcoin p2p network", submitted, Neural Information Processing Systems (NIPS 2017).

Abstract: Bitcoin is a popular alternative to fiat money, widely used for its perceived anonymity properties. However, recent attacks on Bitcoin's peer-to-peer (P2P) network demonstrated that its gossip-based flooding protocols, which are used to ensure global network consistency, may enable user deanonymization---the linkage of a user's IP address with her pseudonym in the Bitcoin network. In 2015, the Bitcoin community responded to these attacks by changing the network's flooding mechanism to a different protocol, known as diffusion. However, no systematic justification was provided for the change, and it is unclear if diffusion actually improves the system's anonymity. In this paper, we model the Bitcoin networking stack and analyze its anonymity properties, both pre- and post-2015. In doing so, we consider new adversarial models and spreading mechanisms that have not been previously studied in the source-finding literature. We theoretically prove that Bitcoin's networking protocols (both pre- and post-2015) offer poor anonymity properties on networks with a regular-tree topology. We validate this claim in simulation on a 2015 snapshot of the real Bitcoin P2P network topology.

ACCOMPLISHMENT HIGHLIGHTS

• Fundamental limits to spreading and hiding of in the BitCoin P2P networking stack.
• In this quarter our study of anonymity of the BitCoin networking stack has progressed smoothly, with significant research progress.