Skip navigation

Utility-Privacy Tradeoff in Differential Privacy via Ehrhart Theory

Event Date: November 28, 2017
Speaker: Dr. Arun Padakandla
Speaker Affiliation: Purdue University
Center for Science of Information (CSoI)
Type: CNSIP Research Area Seminar
Time: 2:30pm
Location: MSEE 239
Contact Name: Professor Xiaojun Lin
Contact Phone: 765-49-40626
Contact Email:
Priority: No
School or Program: Electrical and Computer Engineering
College Calendar: Show

Modern day databases containing fine-grained and high-dimensional information about preferences/characteristics of subjects (individuals in the population) is being increasingly mined for socio, economic and scientific benefits. In particular, the high-dimensional nature of these databases has encouraged unrestrained and continuous querying. An adversary who has access to all or many of the query responses can decipher specific entries in the database resulting in catastrophic privacy loss. The goal of my work is to design and study an architecture that permits for (i) unrestrained querying of databases, (ii) provides accurate statistical information while being (iii) impermeable to privacy attacks. In this talk, we propose an architecture wherein the original database is sanitized via a differentially private (DP) sanitizing mechanism. The original database is discarded and all further querying is performed on the sanitized database. My work is aimed at characterizing the fundamental utility-privacy trade-off that governs the performance of this architecture. The characterization of this tradeoff leads to an important open problem in differential privacy. In this talk, I will provide a complete solution to this open problem using rich tools from discrete geometry, combinatorics, analytic methods. In particular, I will prove that the utility-privacy tradeoff is a Ehrhart series of a convex polytope. Using analytic methods, I will provide a simple closed form computable expression to this power series thereby providing a solution to the open problem mentioned above. This is joint work with Prof. P. R. Kumar and Prof. Wojciech Szpankowski.

Dr. Padakandlais a National Science Foundation Postdoctoral Research Fellow with the Center for Science of Information (CSoI) at Purdue University, mentored by Prof. P R Kumar (Texas A & M Univ) and Prof. Wojciech Szpankowski(Purdue Univ). His research interests are in Privacy, data science, information theory and communication networks. Prior to joining CSoI, he worked as a Research Engineer at Ericsson Research, San Jose. He secured his PhD in Elec. Eng and Comp. Sci in 2014 and a Masters in Mathematics in 2013, both from the Univ. of Michigan, Ann Arbor.