<div dir="ltr">This week&#39;s BUsec seminar talk will be given by George Kellaris who recently joint BU/Harvard as a postdoc. George will talk about his research on practical differential privacy. <div><br><div><br></div><div>***Note the <b>unusual location</b> this week: talk will be at room <b>MCS 148</b>***</div><div><br></div><div><br></div><div><br></div><div><div>BUsec Calendar:  <a href="http://www.bu.edu/cs/busec/">http://www.bu.edu/cs/busec/</a></div><div><br></div><div>BUsec Mailing list: <a href="http://cs-mailman.bu.edu/mailman/listinfo/busec">http://cs-mailman.bu.edu/mailman/listinfo/busec</a></div><div><br></div><div>The busec seminar gratefully acknowledges the support of BU&#39;s Center for Reliable Information Systems and Cyber Security (RISCS). </div><div><br></div><div><br></div><div>**********************</div><div><br></div><div>Practical Differential Privacy</div><div>Speaker: George Kellaris</div><div>Wednesday Oct. 14th, 2015  10-11am</div><div>Room, MCS148</div><div><br></div><div>Abstract: We focus on publishing statistics on a private database with epsilon-differential privacy. We target at three scenarios; (i) when the statistics are computed over a static database with high sensitivity, (ii) when the statistics are published continuously over data that are updated by a stream, and (iii) when we wish to publish 1-dimensional histograms.</div><div>For the first scenario, we address one-time publishing of non-overlapping counts computed over highly sensitive data. These statistics are useful in a wide and important range of applications, including transactional, traffic and medical data analysis. Prior work on epsilon-differential privacy publishes such statistics with prohibitively low utility in several practical scenarios. Towards this end, we present GS, a method that pre-processes the counts by elaborately grouping and smoothing them via averaging. This step acts as a form of preliminary perturbation that diminishes sensitivity, and enables GS to achieve epsilon-differential privacy through low Laplace noise injection. The grouping strategy is dictated by a sampling mechanism, which minimizes the smoothing perturbation. We demonstrate the superiority of GS over its competitors, and confirm its practicality, via extensive experiments on real datasets.</div><div>For the second scenario, we address continuously publishing of non-overlapping counts. Numerous applications require continuous publication of statistics for monitoring purposes, such as real-time traffic analysis, timely disease outbreak discovery, and social trends observation. These statistics may be derived from sensitive user data and, hence, necessitate privacy preservation. Although epsilon-differential privacy is a notable paradigm for offering strong privacy guarantees in statistics publishing, there is limited literature that adapts this concept to settings where the statistics are computed over an infinite stream of “events&quot; (i.e., data items generated by the users), and published periodically. These works aim at hiding a single event over the entire stream. We argue that, in most practical scenarios, sensitive information is revealed from multiple events occurring at contiguous time instances. Towards this end, we put forth the novel notion of w-event privacy over infinite streams, which protects an event sequence occurring in w successive time instants. We first formulate our privacy concept, motivate its importance, and introduce a methodology for achieving it. We next design two instantiations, whose utility is independent of the stream length. Finally, we confirm the practicality of our solutions experimenting with real data.</div><div>For the third scenario, we focus on the problem of differentially private histogram publication, for range-sum query answering. Specifically, we derive an 1-dimensional histogram from a given dataset, such that (i) it satisfies epsilon-differential privacy, and (ii) it achieves high utility for queries that request the sum of contiguous histogram bins. Existing schemes are distinguished into two categories: &quot;data-aware&quot; and &quot;data-oblivious&quot;. Data-aware methods exploit data characteristic to increase utility. However, they have superquadratic running time, and their error increases with the query range. On the other hand, data-oblivious methods are fast but may yield lower utility for datasets commonly found in practice, especially for short ranges. We propose schemes that combine and improve characteristics of both approaches, with emphasis on both efficiency and utility. Towards this goal, we formulate a principled approach, which defines a small set of simple modules, based on which we can devise a variety of more complex schemes. We first express the state-of-the-art methods in terms of these modules, which allows us to identify the performance bottlenecks. Next, we design novel efficient and effective schemes based on non-trivial module combinations. We experimentally evaluate all mechanisms on three real datasets with diverse characteristics, and demonstrate the benefits of our proposals over previous work.</div></div><div><br></div><div><br></div></div></div>