Network Coding for Anonymous Broadcast by Ivan A. Sergeev AR~HNE$ S.B., Electrical Engineering and Computer Science, M.I.T., 2012 IASM r 1~ ~ r~c~v Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of Masters of Engineering in Electrical Engineering and Computer Science at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY May 2013 Copyright 2013 Ivan A. Sergeev. Al1 rights reserved. The author hereby grants to MIT permission to reproduce and to distribute publicly paper and electronic copies of this thesis document in whole or in part in any medium now known or hereafter created. A uth or ................................................. Department of Electrical Engineering and Computer Science May 24, 2013 Certified by ....... ............... Muriel Medard Professor of Electrical Engineering, Thesis Supervisor Accepted by ....................... ........... Prof. Dennis M. Freeman Chairman, Masters of Engineering Thesis Committee Network Coding for Anonymous Broadcast by Ivan A. Sergeev Submitted to the Department of Electrical Engineering and Computer Science on May 24, 2013, in partial fulfillment of the requirements for the degree of Masters of Engineering in Electrical Engineering and Computer Science Abstract This thesis explores the use of network coding for anonymous broadcast. Network coding, the technique of transmitting or storing mixtures of messages rather than individual messages, can provide anonymity with its mixing nature, efficiently dis- seminate content in multicast and broadcast networks, and resiliently deliver messages despite packet erasure and constrained network resources. While broadcast mediums guarantee receiver anonymity, they are thought to be difficult to emulate efficiently over unicast networks. This thesis introduces NCGAB, a decentralized peer-to-peer overlay network based on network coded gossip that provides a resilient, anonymous broadcast medium. Unlike most anonymous communication systems, NCGAB re- quires no cryptosystem, no infrastructure of trust, and no special nodes to operate. This thesis also introduces Melting Pad, an algebraic coding scheme with properties of information theoretic security and efficient decodability, designed to protect messages for wide dissemination and for hosting with diminished liability. Thesis Supervisor: Muriel Medard Title: Professor of Electrical Engineering 3 4 Acknowledgments I thank my advisor, Prof. Muriel Medard, for giving me the space to run off with my little ideas and network coding side projects, and for her trust in me that something would come of them. Through the guiding hand of her experience and her contagious curiosity, Muriel has revealed to me the joy of research. This work would not have been possible without her flexibility, insight, and support. I also thank my co-advisor, Prof. Jodo Barros of Universidade do Porto, for his direction, advice, and constant flow of ideas on these projects. I thank my mentor and friend, Kerim Fouli, for his uncanny capacity to be there at the right time for me. 5 6 Contents 1 Introduction 15 2 Network Coding 17 3 NCGAB 21 3.1 Introduction .......... 21 3.2 Related Work ......... 23 3.3 System Overview ........ 25 3.3.1 Anonymous . . . . . . 26 3.3.2 Decentralized . . . . . 26 3.3.3 Highly Available . . . 26 3.3.4 Resilient . . . . . . . . 27 3.4 Network Coding Tools . . 27 .r.c.ture 3.4.1 Network Coded Gossip Protocols 27 3.4.2 Homomorphic Hashes. 28 3.5 System Architecture 29 3.5.1 Gossip and Decoding Strategy 30 3.5.2 Ephemeral Message Wiudow 31 3.5.3 Amended Gossip Strat .g .. . . 32 3.5.4 Message and Packet St 33 3.5.5 Message Contribution by Application 35 3.5.6 System Parameters . . . . . . . . . . 35 3.5.7 System Pseudo-code . . . . . . . . . 36 7 3.6 Analysis of Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.6.1 Traffic Analysis by an Omniscient Adversary . . . . . . . . . . 38 3.6.2 Traffic Analysis by a Limited Adversary . . . . . . . . . . . . 39 3.7 Analysis of Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.7.1 Threat Model, Attack Vectors, and Goal of an Adversary . . . 41 3.7.2 Inactive Peer . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.7.3 Pollution with Invalid Gossip . . . . . . . . . . . . . . . . . . 43 3.7.4 Pollution with Old or Underdetermined Gossip . . . . . . . . . 43 3.7.5 Pollution with Decodable Gossip . . . . . . . . . . . . . . . . 44 3.7.6 Pollution with Colluded Decodable Gossip . . . . . . . . . . . 45 3.8 Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.8.1 ncgabsim Simulator . . . . . . . . . . . . . . . . . . . . . . . . 45 3.8.2 Availability and Delay . . . . . . . . . . . . . . . . . . . . . . 48 3.8.3 Cooperative Peer Simulations . . . . . . . . . . . . . . . . . . 48 3.8.4 Simulation of Uniform versus Weighted Item Selection . . . . 50 3.8.5 Simulation of an Inactive Peer . . . . . . . . . . . . . . . . . . 50 3.8.6 Simulation of Pollution with Underdetermined Gossip . . . . . 51 3.8.7 Simulation of Pollution with Decodable Gossip . . . . . . . . . 52 4 Melting Pad 55 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 Interference Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3 Melting Pad Coding and Decoding . . . . . . . . . . . . . . . . . . . 57 4.3.1 Exam ple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.3.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4 Confidentiality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.4.1 Maximal Security . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.4.2 Achievability of Maximal Security . . . . . . . . . . . . . . . . 62 4.5 A pplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8 4.5.1 Subscriber Content Delivery . . . . . . . . . . . . . . . . . . . 64 4.5.2 Secure Storage on Untrusted Servers . . . . . . . . . . . . . . 64 4.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.6.1 Grow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.6.2 Shrink . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.6.3 Onion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 Conclusion 69 5.1 NCGAB Conclusion and Future Wo rk . . . . . . . . . . . . . . . . . 69 5.2 Melting Pad Conclusion and Future Wo rk . . . . . . . . . . . . . . . 70 A ncgabsim Simulator Code 73 A. 1 ncgabsim.py . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 A.2 ff.py . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 88 A.3 stats-process.py . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 93 9 10