UK-SPS Seminar 9th June 2021 - Making PDCE Practical

Title: How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free [Usenix Security ’21]

Speaker: Changyu Dong (Newcastle)

Abstract: Secure computation is a promising privacy enhancing technology, but it is often not scalable enough for data intensive applications. On the other hand, the use of sketches has gained popularity in data mining, because sketches often give rise to highly efficient and scalable sub-linear algorithms. It is natural to ask: what if we put secure computation and sketches together? We investigated the question and the findings are interesting: we can get security, we can get scalability, and somewhat unexpectedly, we can also get differential privacy — for free. Our study started from building a secure computation protocol based on the Flajolet-Martin (FM) sketches, for solving the Private Distributed Cardinality Estimation (PDCE) problem, which is a fundamental problem with applications ranging from crowd tracking to network monitoring. The state of the art protocol for PDCE is computationally expensive and not scalable enough to cope with big data applications, which prompted us to design a better protocol. Our further analysis revealed that if the cardinality to be estimated is large enough, our protocol can achieve (ϵ,δ)-differential privacy automatically, without requiring any additional manipulation of the output. The result signifies a new approach for achieving differential privacy that departs from the mainstream approach (i.e. adding noise to the result). Free differential privacy can be achieved because of two reasons: secure computation minimizes information leakage, and the intrinsic estimation variance of the FM sketch makes the output of our protocol uncertain. We further show that the result is not just theoretical: the minimal cardinality for differential privacy to hold is only 102−104 for typical parameters.

Bio: Changyu Dong is a Senior Lecturer in Security at the School of Computing, Newcastle University. He obtained his PhD from Imperial College London, on trust management in large distributed systems. He has published more than 40 papers in major journals and conferences, including prestigious ACM CCS, USENIX Security, ESORICS and IEEE Transactions on Dependable and Secure Computing (TDSC) and IEEE Transactions on Information Forensics and Security (TIFS). Three of his papers were selected as best paper at international conferences. He has served on the program committees for many conferences and workshops (e.g. ESORICS, IEEE Trustcom) and is a regular invited reviewer for international journals. His research is motivated by security, privacy and trust issues in distributed systems, and aims to find practical solutions by combining tools from computer science, cryptography, formal methods, and game theory. He has extensive experience on privacy enhancing technologies, cryptographic protocol design and analysis, as well as secure computation.

Please feel free to forward to others who might be interested. 

UK-SPS is an inter-university seminar series on cyber security and privacy. Seminar details are also advertised on our website, calendar and Twitter, and recordings will be available on our YouTube channel afterwards. 

Last modified: Mon, 27 Sep 2021 10:20:10 BST