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

Article

Keyword search and oblivious pseudorandom functions

Authors:

Michael J. Freedman,

Omer ReingoldAuthors Info & Claims

TCC'05: Proceedings of the Second international conference on Theory of Cryptography

Pages 303 - 324

https://doi.org/10.1007/978-3-540-30576-7_17

Published: 10 February 2005 Publication History

Abstract

We study the problem of privacy-preserving access to a database. Particularly, we consider the problem of privacy-preserving keyword search (KS), where records in the database are accessed according to their associated keywords and where we care for the privacy of both the client and the server. We provide efficient solutions for various settings of KS, based either on specific assumptions or on general primitives (mainly oblivious transfer). Our general solutions rely on a new connection between KS and the oblivious evaluation of pseudorandom functions (OPRFs). We therefore study both the definition and construction of OPRFs and, as a corollary, give improved constructions of OPRFs that may be of independent interest.

References

[1]

Bill Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In EUROCRYPT, Innsbruck, Austria, May 2001.

Digital Library

[2]

Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the servers' computation in private information retrieval: Pir with preprocessing. In CRYPTO, Santa Barbara, CA, August 2000.

Digital Library

[3]

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public key encryption with keyword search. In EUROCRYPT, Interlaken, Switzerland, May 2004.

[4]

Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In EUROCRYPT, Prague, Czech Republic, May 1999.

Digital Library

[5]

Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, 2000.

Digital Library

[6]

Yan-Cheng Chang. Single database private information retrieval with logarithmic communication. In Proc. 9th ACISP, Sydney, Australia, July 2004.

[7]

Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. Technical Report TR-CS0917, Dept. of Computer Science, Technion, 1997.

[8]

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Proc. 36th FOCS, Milwaukee, WI, 23-25 October 1995.

Digital Library

[9]

Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637-647, 1985.

Digital Library

[10]

Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In EUROCRYPT, Interlaken, Switzerland, May 2004.

[11]

Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In Proc. 30th ACM STOC, Dallas, TX, May 1998.

Digital Library

[12]

Niv Gilboa. Topics in Private Information Retrieval. PhD thesis, Technion - Israel Institute of Technology, 2000.

[13]

Oded Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001.

Digital Library

[14]

Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, October 1986.

Digital Library

[15]

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999.

Digital Library

[16]

Russell Impagliazzo and Michael Luby. One-way functions are essential for complexity based cryptography. In Proc. 30th FOCS, Research Triangle Park, NC, October-November 1989.

Digital Library

[17]

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In CRYPTO, Santa Barbara, CA, August 2003.

[18]

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Batch codes and their applications. In Proc. 36th ACM STOC, Chicago, IL, June 2004.

Digital Library

[19]

Joe Kilian. Founding cryptography on oblivious transfer. In Proc. 20th ACM STOC, Chicago, IL, May 1988.

Digital Library

[20]

Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Proc. 38th FOCS, Miami Beach, FL, October 1997.

Digital Library

[21]

Helger Lipmaa. An oblivious transfer protocol with log-squared communication. Crypto ePrint Archive, Report 2004/063, 2004.

[22]

Silvio Micali, Michael Rabin, and Joe Kilian. Zero-knowledge sets. In Proc. 44th FOCS, Cambridge, MA, October 2003.

Digital Library

[23]

Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proc. 31st ACM STOC, Atlanta, GA, May 1999.

Digital Library

[24]

Moni Naor and Benny Pinkas. Oblivious transfer with adaptive queries. In CRYPTO, Santa Barbara, CA, August 1999.

Digital Library

[25]

Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In Proc. 12th SIAM SODA, Washington, DC, January 2001.

Digital Library

[26]

Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudorandom functions. In Proc. 38th FOCS, Miami Beach, FL, October 1997.

Digital Library

[27]

Wakaha Ogata and Kaoru Kurosawa. Oblivious keyword search. Crypto ePrint Archive, Report 2002/182, 2002.

[28]

Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, Prague, Czech Republic, May 1999.

Digital Library

[29]

Michael O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981.

[30]

Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Proc. IEEE Symposium on Security and Privacy, Berkeley, CA, May 2000.

Digital Library

Cited By

Wei ZSu YZhang XYang HQin JMa J(2025)Machine Learning Meets Encrypted SearchInternational Journal of Intelligent Systems10.1155/int/24295772025Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1155/int/2429577
Connell GFang VSchmidt RDauterman EPopa RGavrilovska ATerry D(2024)Secret key recovery in a global-scale end-to-end encryption systemProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691976(703-719)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691976
Chen LLi YTang QYung M(2024)End-to-Same-End Encryption: Modularly Augmenting an App with an Efficient, Portable, and Blind Cloud StorageACM Transactions on Privacy and Security10.1145/370746028:2(1-35)Online publication date: 6-Dec-2024
https://dl.acm.org/doi/10.1145/3707460
Show More Cited By

Keyword search and oblivious pseudorandom functions

Recommendations

Oblivious Pseudorandom Functions from Isogenies
Advances in Cryptology – ASIACRYPT 2020
Abstract
An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key k for a secure pseudorandom function F, and the client has an input x for the function. At the end of the protocol the client learns F(k, x), and ...
$_{^{}}$
Oblivious keyword search
Special issue on coding and cryptography

In this paper, we introduce a notion of oblivious keyword search (OKS). Let W be the set of possible keywords. In the commit phase, a database supplier I commits n data. In each transfer subphase, a user U can choose a keyword w∈W adaptively and find ...
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution
SP '12: Proceedings of the 2012 IEEE Symposium on Security and Privacy

Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TCC'05: Proceedings of the Second international conference on Theory of Cryptography

February 2005

620 pages

ISBN:3540245731

Editor:
Joe Kilian
Rutgers University, New Brunswick, NJ

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 February 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

137
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei ZSu YZhang XYang HQin JMa J(2025)Machine Learning Meets Encrypted SearchInternational Journal of Intelligent Systems10.1155/int/24295772025Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1155/int/2429577
Connell GFang VSchmidt RDauterman EPopa RGavrilovska ATerry D(2024)Secret key recovery in a global-scale end-to-end encryption systemProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691976(703-719)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.5555/3691938.3691976
Chen LLi YTang QYung M(2024)End-to-Same-End Encryption: Modularly Augmenting an App with an Efficient, Portable, and Blind Cloud StorageACM Transactions on Privacy and Security10.1145/370746028:2(1-35)Online publication date: 6-Dec-2024
https://dl.acm.org/doi/10.1145/3707460
Ma LWang HNiu ZLi ZWu LWei XSu Y(2024)Over-threshold multi-party private set operation protocols for lightweight clientsComputer Standards & Interfaces10.1016/j.csi.2023.10378188:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.csi.2023.103781
Albrecht MGur K(2024)Verifiable Oblivious Pseudorandom Functions from Lattices: Practical-Ish and ThresholdisableAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0894-2_7(205-237)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0894-2_7
Chen KLi YWang M(2024)An Efficient Toolkit for Computing Third-Party Private Set IntersectionProgress in Cryptology – INDOCRYPT 202410.1007/978-3-031-80308-6_12(258-281)Online publication date: 18-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-80308-6_12
Liu KLi XTakagi T(2024)Review the Cuckoo Hash-Based Unbalanced Private Set Union: Leakage, Fix, and OptimizationComputer Security – ESORICS 202410.1007/978-3-031-70890-9_17(331-352)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70890-9_17
Alamati NPolicharla GRaghuraman SRindal P(2024)Improved Alternating-Moduli PRFs and Post-quantum SignaturesAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_9(274-308)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_9
Backendal MDavis HGünther FHaller MPaterson K(2024)A Formal Treatment of End-to-End Encrypted Cloud StorageAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_2(40-74)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68379-4_2
Delpech de Saint Guilhem CPedersen R(2024)New Proof Systems and an OPRF from CSIDHPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_8(217-251)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_8
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten