Differential privacy aims at protecting the privacy of participants in statistical databases. Roughly, a mechanism satisfies differential privacy if the presence or value of a single individual in the database does not significantly change the likelihood of obtaining a certain answer to any statistical query posed by a data analyst. Differentially-private mechanisms are often oblivious: first the query is processed on the database to produce a true answer, and then this answer is adequately randomized before being reported to the data analyst. Ideally, a mechanism should minimize leakage – i.e., obfuscate as much as possible the link between reported answers and individuals’ data – while maximizing utility – i.e., report answers as similar as possible to the true ones. These two goals, however, are in conflict with each other, thus imposing a trade-off between privacy and utility.
In this paper we use quantitative information flow principles to analyze leakage and utility in oblivious differentially-private mechanisms. We introduce a technique that exploits graph symmetries of the adjacency relation on databases to derive bounds on the min-entropy leakage of the mechanism. We consider a notion of utility based on identity gain functions, which is closely related to min-entropy leakage, and we derive bounds for it. Finally, given some graph symmetries, we provide a mechanism that maximizes utility while preserving the required level of differential privacy.
M.S.Alvim, M.E.Andrés, K.Chatzikokolakis, P.Degano and C.Palamidessi, Differential privacy: On the trade-off between utility and information leakage, in: Post-Proceedings of the 8th International Workshop on Formal Aspects in Security and Trust (FAST), G.Barthe, A.Datta and S.Etalle, eds, Lecture Notes in Computer Science, Vol. 7140, Springer, Leuven, Belgium, 2011, pp. 39–54.
2.
M.S.Alvim, M.E.Andrés, K.Chatzikokolakis and C.Palamidessi, On the relation between differential privacy and quantitative information flow, in: 38th International Colloquium on Automata, Languages and Programming (ICALP), J.Sgall Luca Aceto and M.Henzinger, eds, Lecture Notes in Computer Science, Vol. 6756, Springer, Zürich, Switzerland, 2011, pp. 60–76.
3.
M.S.Alvim, K.Chatzikokolakis, P.Degano and C.Palamidessi, Differential privacy versus quantitative information flow, Technical report, INRIA and LIX, Ecole Polytechnique, 2010, available at: http://hal.archives-ouvertes.fr/hal-00548214/en/.
4.
M.S.Alvim, K.Chatzikokolakis, C.Palamidessi and G.Smith, Measuring information leakage using generalized gain functions, in: Proceedings of the 25th IEEE Computer Security Foundations Symposium (CSF), 2012, pp. 265–279.
5.
G.Barthe and B.Köpf, Information-theoretic bounds for differentially private mechanisms, in: Proceedings of the 24th IEEE Computer Security Foundations Symposium (CSF), IEEE Computer Society, 2011, pp. 191–204.
6.
J.M.Bernardo and A.F.M.Smith, Bayesian Theory, John Wiley & Sons, Inc., 1994.
7.
A.Blum, K.Ligett and A.Roth, A learning theory approach to non-interactive database privacy, in: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC’08, ACM, New York, NY, USA, 2008, pp. 609–618.
8.
C.Braun, K.Chatzikokolakis and C.Palamidessi, Compositional methods for information-hiding, in: Proceedings of the 11th International Conference on the Foundations of Software Science and Computation Structures (FOSSACS’08), R.Amadio, ed., Lecture Notes in Computer Science, Vol. 4962, Springer, 2008, pp. 443–457.
9.
C.Braun, K.Chatzikokolakis and C.Palamidessi, Quantitative notions of leakage for one-try attacks, in: Proceedings of the 25th Conference on Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science, Vol. 249, Elsevier B.V., 2009, pp. 75–91.
10.
A.E.Brouwer, A.M.Cohen and A.Neumaier, Distance Regular Graphs, Ergebnisse der Mathematik, Vol. 3, Springer, 1989.
11.
M.R.Clarkson and F.B.Schneider, Quantification of integrity, Mathematical Structures in Computer Science25(2) (2015), 207–258.
12.
C.Dwork, Differential privacy, in: 33rd International Colloquium on Automata, Languages and Programming (ICALP), M.Bugliesi, B.Preneel, V.Sassone and I.Wegener, eds, Lecture Notes in Computer Science, Vol. 4052, Springer, 2006, pp. 1–12.
13.
C.Dwork, Differential privacy in new settings, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), M.Charikar, ed., SIAM, 2010, pp. 174–183.
14.
C.Dwork, A firm foundation for private data analysis, Communications of the ACM54(1) (2011), 86–95.
15.
C.Dwork and J.Lei, Differential privacy and robust statistics, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA, 31 May–2 June 2009, M.Mitzenmacher, ed., ACM, 2009, pp. 371–380.
16.
B.Espinoza and G.Smith, Min-entropy leakage of channels in cascade, in: Proceedings of the International Workshop on Formal Aspects in Security and Trust (FAST), G.Barthe, A.Datta and S.Etalle, eds, Lecture Notes in Computer Science, Vol. 7140, Springer, 2011, pp. 70–84.
17.
A.Ghosh, T.Roughgarden and M.Sundararajan, Universally utility-maximizing privacy mechanisms, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, NY, USA, 2009, pp. 351–360.
18.
M.Hardt and G.N.Rothblum, A multiplicative weights mechanism for privacy-preserving data analysis, in: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS’10, IEEE Computer Society, Washington, DC, USA, 2010, pp. 61–70.
19.
J.Heusser and P.Malacaria, Applied quantitative information flow and statistical databases, in: Proceedings of the International Workshop on Formal Aspects in Security and Trust (FAST 2009), P.Degano and J.D.Guttman, eds, Lecture Notes in Computer Science, Vol. 5983, Springer, 2009, pp. 96–110.
20.
W.Imrich and S.Klavžar, Product Graphs, Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2000.
21.
Y.Kawamoto, K.Chatzikokolakis and C.Palamidessi, Compositionality results for quantitative information flow, in: Proceedings of the 11th International Conference on Quantitative Evaluation of Systems (QEST 2014), G.Norman and W.H.Sanders, eds, Lecture Notes in Computer Science, Vol. 8657, Springer, 2014, pp. 368–383, IDEX Digital Society project.
22.
D.Kifer and A.Machanavajjhala, No free lunch in data privacy, in: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD’11, ACM, New York, NY, USA, 2011, pp. 193–204.
23.
B.Köpf and D.A.Basin, An information-theoretic model for adaptive side-channel attacks, in: Proceedings of the 2007 ACM Conference on Computer and Communications Security (CCS 2007), P.Ning, S.De Capitani di Vimercati and P.F.Syverson, eds, ACM, 2007, pp. 286–296.
24.
F.McSherry and K.Talwar, Mechanism design via differential privacy, in: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), IEEE Computer Society, 2007, pp. 94–103.
25.
S.Prasad Kasiviswanathan and A.Smith, A note on differential privacy: Defining resistance to arbitrary side information, Report 2008/144, Cryptology ePrint Archive, 2008, available at: http://eprint.iacr.org/.
26.
A.Roth and T.Roughgarden, Interactive privacy via the median mechanism, in: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010, pp. 765–774.
27.
G.Smith, On the foundations of quantitative information flow, in: Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2009), L.de Alfaro, ed., Lecture Notes in Computer Science, Vol. 5504, Springer, York, UK, 2009, pp. 288–302.
28.
G.Smith, Quantifying information flow using min-entropy, in: Eighth International Conference on Quantitative Evaluation of Systems, QEST 2011, Aachen, Germany, 5–8 September 2011, IEEE Computer Society, 2011, pp. 159–167.
