BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Changyu Dong (Newcastle University) DTSTART:20210609T140000Z DTEND:20210609T150000Z DTSTAMP:20260423T053016Z UID:UK-SPS/2 DESCRIPTION:Title: H ow to Make Private Distributed Cardinality Estimation Practical\, and Get Differential Privacy for Free\nby Changyu Dong (Newcastle University) as part of UK Security and Privacy Seminar Series\n\n\nAbstract\nSecure co mputation is a promising privacy enhancing technology\, but it is often no t scalable enough for data intensive applications. On the other hand\, the use of sketches has gained popularity in data mining\, because sketches o ften 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 ge t security\, we can get scalability\, and somewhat unexpectedly\, we can a lso 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) proble m\, which is a fundamental problem with applications ranging from crowd tr acking to network monitoring. The state of art protocol for PDCE is comput ationally expensive and not scalable enough to cope with big data applicat ions\, which prompted us to design a better protocol. Our further analysis revealed that if the cardinality to be estimated is large enough\, our pr otocol can achieve (\\epsilon\,\\delta)-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 diffe rential 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 diffe rential privacy to hold is only 10^2−10^4 for typical parameters.\n LOCATION:https://researchseminars.org/talk/UK-SPS/2/ END:VEVENT END:VCALENDAR