Repudiative information retrieval

ABSTRACT

Privacy is preserved while retrieving an i-th record from the database of N records if no information is revealed about i, not even to the database server. Repudiation is preserved in the same model if no one can prove, even in cooperation with the server, that a record retrieved is or is not the j-th record for any 1 ≤ j ≤ N. The first problem is called PIR, and we call the second problem the RIR problem.State of the art PIR protocols with optimal query response time and optimal communication require heavy periodical preprocessing. O(N log N) I/O's are required for preprocessing before answering a query.In this paper, we reduce preprocessing complexity by weakening PIR to RIR. In particular, we propose a RIR protocol with optimal query response time and communication, and O (√N) preprocessing per query.

REFERENCES

• 1: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 2: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 3: Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Proceedings of EUROCRYPT'99, 1999.
• 4: Feng Bao , Robert H. Deng , Peirong Feng, An Efficient and Practical Scheme for Privacy Protection in the E-Commerce of Digital Goods, Proceedings of the Third International Conference on Information Security and Cryptology, p.162-170, December 08-09, 2000
• 5: Claus-Peter Schnorr , Markus Jakobsson, Security of Signed ElGamal Encryption, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.73-89, December 03-07, 2000
• 6: Sean W. Smith and Dave Safford. Practical private information retrieval with secure coprocessors. Technical report, IBM Research Division, T.J. Watson Research Center, July 2000.
• 7: S. W. Smith , D. Safford, Practical server privacy with secure coprocessors, IBM Systems Journal, v.40 n.3, p.683-695, March 2001
• 8: Aggelos Kiayias , Moti Yung, Secure Games with Polynomial Expressions, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.939-950, July 08-12, 2001
• 9: Dmitri Asonov and Johann-Christoph Freytag. Almost optimal private information retrieval. Technical Report HUB-IB-156, Humboldt University Berlin, November 2001.
• 10: Dmitri Asonov and Johann-Christoph Freytag. Almost optimal private information retrieval. In Proceedings of 2nd Workshop on Privacy Enhancing Technologies (PET2002), San Francisco, USA, April 2002.
• 11: Dmitri Asonov and Johann-Christoph Freytag. Private information retrieval, optimal for users and secure coprocessors. Technical Report HUB-IB-159, Humboldt University Berlin, May 2002.
• 12: Dmitri Asonov. Private information retrieval - an overview and current trends. In Proceedings of the ECDPvA Workshop, Informatik 2001, Vienna, Austria, September 2001.
• 13: Ran Canetti , Cynthia Dwork , Moni Naor , Rafail Ostrovsky, Deniable Encryption, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.90-104, August 17-21, 1997
• 14: Ronald L. Rivest. Chaffing and winnowing: Confidentiality without encryption. http://theory.lcs.mit.edu/~rivest/chaffing.txt, April 1998.
• 15: Vitaly Shmatikov and Dominic J.D. Hughes. Defining anonymity and privacy. In Proceedings of Workshop on Issues in the Theory of Security (WITS '02), January 2002.
• 16: Vitaly Shmatikov, Probabilistic Analysis of Anonymity, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.119, June 24-26, 2002
• 17: Paul F. Syverson , Stuart G. Stubblebine, Group Principals and the Formalization of Anonymity, Proceedings of the Wold Congress on Formal Methods in the Development of Computing Systems-Volume I, p.814-833, September 20-24, 1999
• 18: Andrei Serjantov and George Danezis. Towards an information theoretic metric for anonymity. In Proceedings of 2nd Workshop on Privacy Enhancing Technologies (PET2002), San Francisco, USA, April 2002.
• 19: Claudia Diaz, Stefaan Seys, Joris Claessens, and Bart Preneel. Towards measuring anonymity. In Proceedings of 2nd Workshop on Privacy Enhancing Technologies (PET2002), San Francisco, USA, April 2002.
• 20: Alison Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International Statistical Review, 70(3), December 2002.
• 21: Dmitri Asonov and Neil K. Daswani. Pesonal communication, November 2002.
• 22: Sean W. Smith , Elaine R. Palmer , Steve Weingart, Using a High-Performance, Programmable Secure Coprocessor, Proceedings of the Second International Conference on Financial Cryptography, p.73-89, February 23-25, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Security

Keywords:
privacy and anonymity in Web transactions, privacy enhancing technologies, privacy in the digital business