Privacy and Security in Distributed Control: Differentially Private Consensus

ABSTRACT

Towards understanding the limits and the performance costs of privacy and security in database-driven control systems, we study the problem of achieving consensus in a group while preserving privacy of individuals. The iterative consensus problem requires a set of processes or agents with different initial values, to interact and update their states to eventually converge to a common value. Protocols solving iterative consensus serve as building blocks in a variety of systems where distributed coordination is required for load balancing, data aggregation, sensor fusion, filtering, and synchronization. In this paper, we introduce the private iterative consensus problem where agents are required to converge while protecting the privacy of their initial values from honest but curious adversaries. Protecting the initial states, in many applications, suffice to protect all subsequent states of the individual participants.

We adapt the notion of differential privacy in this setting of iterative computation. Next, we present a server-based and a completely distributed randomized mechanism for solving differentially private iterative consensus with adversaries who can observe the messages as well as the internal states of the server and a subset of the clients. Our analysis establishes the tradeoff between privacy and the accuracy in iterative consensus: for given epsilon, b >0, the epsilon-differentially private mechanism for N agents, is guaranteed to convergence to a value within O(1/(epsilon.sqr(bN)) of the average of the initial values, with probability at least (1-b).

Sayan Mitra is an Assistant Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign and is affiliated with the Department of Computer Science, the Coordinated Science Lab, and the Information Trust Institute at Illinois. His research is on foundations of distributed and cyber-physical systems. He has authored more than 60 articles in international journals and conference proceedings and his work has led to the creation of several mathematical, algorithmic, and software tools for verification and synthesis. Sayan graduated from MIT in 2007 and spent one year as a post-doctoral researcher at the Center for Mathematics of Information of CalTech. Earlier, he completed MSc from the Indian Institute of Science, Bangalore and undergraduate degree in EE from Jadavpur University, Kolkata. He recently received the National Science Foundation's CAREER award (2011), AFOSR Young Investigator Research Program Award (2012), a Samsung GRO award (2012), and a best paper award at the IFIP International Conference on Formal Techniques for Distributed Systems (FMOODS/FORTE ‘12).