On the complexity of differentially private data release: efficient algorithms and hardness results

ABSTRACT

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. The sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. In either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

For the task of sanitizing with a synthetic dataset output, we map the boundary between computational feasibility and infeasibility with respect to a variety of utility measures. For the (potentially easier) task of sanitizing with unrestricted output format, we show a tight qualitative and quantitative connection between hardness of sanitizing and the existence of traitor tracing schemes.

REFERENCES

• 1: Avrim Blum , Katrina Ligett , Aaron Roth, A learning theory approach to non-interactive database privacy, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374464]
• 2: Dan Boneh , Moni Naor, Traitor tracing with constant size ciphertext, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455834]
• 3: D. Boneh, A. Sahai, and B. Waters. Fully collusion resistant traitor tracing with short ciphertexts and private keys. In EUROCRYPT, pages 573--592, 2006.
• 4: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 5: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 6: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevy and T. Rabin, editors, First Theory of Cryptography Conference (TCC), volume 3876, pages 265--284. Springer-Verlag, 2006.
• 7: Cynthia Dwork , Frank McSherry , Kunal Talwar, The price of privacy and the limits of LP decoding, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250804]
• 8: C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO, pages 528--544, 2004.
• 9: Cynthia Dwork , Sergey Yekhanin, New Efficient Attacks on Statistical Disclosure Control Mechanisms, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_26]
• 10: Dan Feldman , Amos Fiat , Haim Kaplan , Kobbi Nissim, Private coresets, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536465]
• 11: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 12: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 13: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, 1984.
• 14: Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets , Avi Wigderson, Uniform direct product theorems: simplified, optimized, and derandomized, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374460]
• 15: Shiva Prasad Kasiviswanathan , Homin K. Lee , Kobbi Nissim , Sofya Raskhodnikova , Adam Smith, What Can We Learn Privately?, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.531-540, October 25-28, 2008 [doi>10.1109/FOCS.2008.27]
• 16: Aggelos Kiayias , Moti Yung, Self Protecting Pirates and Black-Box Traitor Tracing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.63-79, August 19-23, 2001
• 17: Frank McSherry , Kunal Talwar, Mechanism Design via Differential Privacy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.94-103, October 21-23, 2007 [doi>10.1109/FOCS.2007.41]
• 18: Michael Saks , Shiyu Zhou, BPH SPACE(S) ⊆ DSPACE(S3/2), Journal of Computer and System Sciences, v.58 n.2, p.376-403, April 1999 [doi>10.1006/jcss.1998.1616]
• 19: Robert E. Schapire, Theoretical Views of Boosting and Applications, Proceedings of the 10th International Conference on Algorithmic Learning Theory, p.13-25, December 06-08, 1999
• 20: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Security, Theory

Keywords:
cryptography, differential privacy, exponential mechanism, privacy, traitor tracing