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 , 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
• 2: 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]
• 3: Andris Ambainis, Markus Jakobsson, and Helger Lipmaa. Cryptographic randomized response techniques. In Public Key Cryptography---PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 425--438, 2004.
• 4: Alexandra Boldyreva and Markus Jakobsson. Theft-protected proprietary certificates. In Digital Rights Management Workshop---DRM 2002, volume 2696 of Lecture Notes in Computer Science, pages 208--220, 2003.
• 5: Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory, 44(5):1897--1905, 1998.
• 6: Benny Chor, Amos Fiat, Moni Naor, and Benny Pinkas. Tracing traitors. IEEE Transactions on Information Theory, 46(3):893--910, 2000.
• 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: Jan Camenisch and Markus Stadler. Proof systems for general statements about discrete logarithms. Technical Report 260, Dept. of Computer Science, ETH Zurich, March 1997.
• 10: 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]
• 11: Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 265--284, 2006.
• 12: Cynthia Dwork. Differential privacy. Invited talk. In ICALP 2006, Part II, volume 4052 of Lecture Notes in Computer Science, pages 1--12, 2006.
• 13: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 14: 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
• 15: 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
• 16: 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]
• 17: 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]
• 18: 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]
• 19: 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
• 20: John M. Pollard. Monte Carlo methods for index computation (mod p). Mathematics of Computation, 32:918--924, 1978.
• 21: Birgit Pfitzmann and Matthias Schunter. Asymmetric fingerprinting (extended abstract). In Advances in Cryptology---EUROCRYPT'96, volume 1070 of Lecture Notes in Computer Science, pages 84--95, 1996.
• 22: Claus-Peter Schnorr. Efficient signature generation by smart cards. J. Cryptology, 4(3):161--174, 1991.
• 23: Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. The American Statistical Association, 60(309):63--69, March 1965.
• 24: Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 160--164, Chicago, Illinois, 3--5 November 1982. IEEE.

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