More Web Proxy on the site http://driver.im/

Article

Repudiative information retrieval

Authors:

Johann-Christoph FreytagAuthors Info & Claims

WPES '02: Proceedings of the 2002 ACM workshop on Privacy in the Electronic Society

Pages 32 - 40

https://doi.org/10.1145/644527.644531

Published: 21 November 2002 Publication History

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]

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Proceedings of 36th FOCS, 1995.]]

Digital Library

[2]

Eyal Kushilevitz and Rafail Ostrovsky. Replication is NOT needed: Single-database computationally private information retrieval. In Proceedings of 38th FOCS, 1997.]]

Digital Library

[3]

Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Proceedings of EUROCRYPT'99, 1999.]]

Digital Library

[4]

Feng Bao, Robert H. Deng, and Peirong Feng. An efficient and practical scheme for privacy protection in the e-commerce of digital goods. In Proceedings of the 3rd International Conference on Information Security and Cryptology, December 2000.]]

Digital Library

[5]

Claus Peter Schnorr and Markus Jakobsson. Security of signed elgamal encryption. In Proceedings of ASIACRYPT'00, LNCS 1976, December 2000.]]

Digital Library

[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]

Sean W. Smith and Dave Safford. Practical server privacy with secure coprocessors. IBM Systems Journal, 40(3), September 2001.]]

Digital Library

[8]

Aggelos Kiayias and Moti Yung. Secure games with polynomial expressions. In Proceedings of 28th ICALP, 2001.]]

Digital Library

[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.]]

Digital Library

[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, and Rafail Ostrovsky. Deniable encryption. In Proceedings of Advances in Cryptology, (CRYPTO-97), June 1997.]]

Digital Library

[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. In Proceedings of 15th IEEE Computer Security Foundations Workshop (CSFW), June 2002.]]

Digital Library

[17]

Paul F. Syverson and Stuart G. Stubblebine. Group principals and the formalization of anonymity. In Proceedings of World Congress on Formal Methods, September 1999.]]

Digital Library

[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, and Steve H. Weingart. Using a high-performance, programmable secure coprocessor. In Proceedings of the 2nd International Conference on Financial Cryptography, February 1998.]]

Digital Library

Cited By

Huang YZhao WZhou RTian C(2024)Weakly Private Information Retrieval from Heterogeneously Trusted Servers2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619321(2862-2867)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619321
Lin HKumar SRosnes EGraell i Amat AYaakobi E(2022)Multi-Server Weakly-Private Information RetrievalIEEE Transactions on Information Theory10.1109/TIT.2021.312686568:2(1197-1219)Online publication date: Feb-2022
https://doi.org/10.1109/TIT.2021.3126865
Ulukus SAvestimehr SGastpar MJafar STandon RTian C(2022)Private Retrieval, Computing, and Learning: Recent Progress and Future ChallengesIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.314235840:3(729-748)Online publication date: Mar-2022
https://doi.org/10.1109/JSAC.2022.3142358
Show More Cited By

Index Terms

Repudiative information retrieval
1. Theory of computation

Recommendations

Outsourced private information retrieval
WPES '13: Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society

We propose a scheme for outsourcing Private Information Retrieval (PIR) to untrusted servers while protecting the privacy of the database owner as well as that of the database clients. We observe that by layering PIR on top of an Oblivious RAM (ORAM) ...
Robust information-theoretic private information retrieval
SCN'02: Proceedings of the 3rd international conference on Security in communication networks

A Private Information Retrieval (PIR) protocol allows a user to retrieve a data item of its choice from a database, such that the servers storing the database do not gain information on the identity of the item being retrieved. PIR protocols were ...
Robust Information-Theoretic Private Information Retrieval

An information-theoretic private information retrieval (PIR) protocol allows a user to retrieve a data item of its choice from a database replicated amongst several servers, such that each server gains absolutely no information on the identity of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WPES '02: Proceedings of the 2002 ACM workshop on Privacy in the Electronic Society

November 2002

115 pages

ISBN:1581136331

DOI:10.1145/644527

General Chair:
Sushil Jajodia
George Mason University
,
Program Chair:
Pierangela Samarati
University of Milan

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS02

Sponsor:

SIGSAC

CCS02: ACM Conference on Computer and Communications Security

November 21, 2002

DC, Washington

Acceptance Rates

Overall Acceptance Rate 106 of 355 submissions, 30%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang YZhao WZhou RTian C(2024)Weakly Private Information Retrieval from Heterogeneously Trusted Servers2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619321(2862-2867)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619321
Lin HKumar SRosnes EGraell i Amat AYaakobi E(2022)Multi-Server Weakly-Private Information RetrievalIEEE Transactions on Information Theory10.1109/TIT.2021.312686568:2(1197-1219)Online publication date: Feb-2022
https://doi.org/10.1109/TIT.2021.3126865
Ulukus SAvestimehr SGastpar MJafar STandon RTian C(2022)Private Retrieval, Computing, and Learning: Recent Progress and Future ChallengesIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.314235840:3(729-748)Online publication date: Mar-2022
https://doi.org/10.1109/JSAC.2022.3142358
Qian CZhou RTian CLiu T(2022)Improved Weakly Private Information Retrieval Codes2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834396(2827-2832)Online publication date: 26-Jun-2022
https://doi.org/10.1109/ISIT50566.2022.9834396
Samy IAttia MTandon RLazos L(2021)Asymmetric Leaky Private Information RetrievalIEEE Transactions on Information Theory10.1109/TIT.2021.308536367:8(5352-5369)Online publication date: Aug-2021
https://doi.org/10.1109/TIT.2021.3085363
Lin HKumar SRosnes EGraell i Amat AYaakobi E(2021)The Capacity of Single-Server Weakly-Private Information RetrievalIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2021.30563272:1(415-427)Online publication date: Mar-2021
https://doi.org/10.1109/JSAIT.2021.3056327
Sun HJafar S(2020)On the Capacity of Locally Decodable CodesIEEE Transactions on Information Theory10.1109/TIT.2020.301497366:10(6566-6579)Online publication date: Oct-2020
https://doi.org/10.1109/TIT.2020.3014973
Li LMilitzer MDatta A(2016)rPIR: ramp secret sharing-based communication-efficient private information retrievalInternational Journal of Information Security10.1007/s10207-016-0347-816:6(603-625)Online publication date: 2-Sep-2016
https://doi.org/10.1007/s10207-016-0347-8
Li LDatta A(2016)Write-only oblivious RAM-based privacy-preserved access of outsourced dataInternational Journal of Information Security10.1007/s10207-016-0329-x16:1(23-42)Online publication date: 15-Apr-2016
https://doi.org/10.1007/s10207-016-0329-x
Devet CGoldberg I(2014)The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication EfficiencyPrivacy Enhancing Technologies10.1007/978-3-319-08506-7_4(63-82)Online publication date: 2014
https://doi.org/10.1007/978-3-319-08506-7_4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents