Data Collection with Self-Enforcing Privacy

ABSTRACT

Consider a pollster who wishes to collect private, sensitive data from a number of distrustful individuals. How might the pollster convince the respondents that it is trustworthy? Alternately, what mechanism could the respondents insist upon to ensure that mismanagement of their data is detectable and publicly demonstrable?

We detail this problem, and provide simple data submission protocols with the properties that a) leakage of private data by the pollster results in evidence of the transgression and b) the evidence cannot be fabricated without breaking cryptographic assumptions. With such guarantees, a responsible pollster could post a “privacy-bond,” forfeited to anyone who can provide evidence of leakage. The respondents are assured that appropriate penalties are applied to a leaky pollster, while the protection from spurious indictment ensures that any honest pollster has no disincentive to participate in such a scheme.

REFERENCES

• 1: Rakesh Agrawal , Peter J. Haas , Jerry Kiernan, Watermarking relational data: framework, algorithms and analysis, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.157-169, August 2003 [doi>10.1007/s00778-003-0097-x]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 3: Ambainis, A., Jakobsson, M., and Lipmaa, H. 2004. Cryptographic randomized response techniques. In Proceedings of the Conference on Public Key Cryptography (PKC’04). F. Bao, R. H. Deng, and J. Zhou Eds. Lecture Notes in Computer Science, vol. 2947. Springer, 425--438.
• 4: Boldyreva, A. and Jakobsson, M. 2003. Theft-protected proprietary certificates. In Proceedings of the Conference on Security and Privacy in Digital Rights Management (DRM’02). J. Feigenbaum Ed. Lecture Notes in Computer Science, vol. 2696. Springer, 208--220.
• 5: Boneh, D. and Shaw, J. 1998. Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44, 5, 1897--1905.
• 6: Camenisch, J. and Stadler, M. 1997. Proof systems for general statements about discrete logarithms. Tech. rep. 260, Dept. of Computer Science, ETH Zurich.
• 7: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 8: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 9: Chor, B., Fiat, A., Naor, M., and Pinkas, B. 2000. Tracing traitors. IEEE Trans. Inf. Theory 46, 3, 893--910.
• 10: Dwork, C. 2006. Differential privacy. Invited talk. In Automata, Languages and Programming (ICALP2). M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener Eds. Lecture Notes in Computer Science, vol. 4052. Springer, 1--12.
• 11: Cynthia Dwork , Jeffrey Lotspiech , Moni Naor, Digital signets: self-enforcing protection of digital information (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.489-498, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237997]
• 12: Dwork, C., McSherry, F., Nissim, K., and Smith, A. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC’06). S. Halevi and T. Rabin Eds. Lecture Notes in Computer Science, vol. 3876. Springer, 265--284.
• 13: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 14: Philippe Golle , Frank McSherry , Ilya Mironov, Data collection with self-enforcing privacy, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180416]
• 15: Jens Groth, A Verifiable Secret Shuffle of Homomorphic Encryptions, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.145-160, January 06-08, 2003
• 16: Markus Jakobsson , Ari Juels , Phong Q. Nguyen, Proprietary Certificates, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.164-181, February 18-22, 2002
• 17: Krishnaram Kenthapadi , Nina Mishra , Kobbi Nissim, Simulatable auditing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065183]
• 18: N. Boris Margolin , Matthew K. Wright , Brian Neil Levine, Analysis of an incentives-based secrets protection system, Proceedings of the 4th ACM workshop on Digital rights management, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029146.1029153]
• 19: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 20: Wakaha Ogata , Kaoru Kurosawa , Kazue Sako , Kazunori Takatani, Fault tolerant anonymous channel, Proceedings of the First International Conference on Information and Communication Security, p.440-444, November 11-14, 1997
• 21: Pfitzmann, B. and Schunter, M. 1996. Asymmetric fingerprinting (extended abstract). In Advances in Cryptology (EUROCRYPT’96). U. M. Maurer Ed. Lecture Notes in Computer Science, vol. 1070. Springer, 84--95.
• 22: Pollard, J. M. 1978. Monte Carlo methods for index computation (mod p). Math. Comput. 32, 918--924.
• 23: Schnorr, C.-P. 1991. Efficient signature generation by smart cards. J. Cryptol. 4, 3, 161--174.
• 24: Warner, S. L. 1965. Randomized response: A survey technique for eliminating evasive answer bias. Amer. Stat. Assoc. 60, 309, 63--69.
• 25: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), p.160-164, November 03-05, 1982

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Security

Keywords:
data collection, privacy