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

research-article

Private search in the real world

Authors:

Vasilis Pappas,

Mariana Raykova,

Steven M. Bellovin,

Tal MalkinAuthors Info & Claims

ACSAC '11: Proceedings of the 27th Annual Computer Security Applications Conference

Pages 83 - 92

https://doi.org/10.1145/2076732.2076744

Published: 05 December 2011 Publication History

Abstract

Encrypted search --- performing queries on protected data --- has been explored in the past; however, its inherent inefficiency has raised questions of practicality. Here, we focus on improving the performance and extending its functionality enough to make it practical. We do this by optimizing the system, and by stepping back from the goal of achieving maximal privacy guarantees in an encrypted search scenario and consider efficiency and functionality as priorities.

We design and analyze the privacy implications of two practical extensions applicable to any keyword-based private search system. We evaluate their efficiency by building them on top of a private search system, called SADS. Additionally, we improve SADS' performance, privacy guaranties and functionality. The extended SADS system offers improved efficiency parameters that meet practical usability requirements in a relaxed adversarial model. We present the experimental results and evaluate the performance of the system. We also demonstrate analytically that our scheme can meet the basic needs of a major hospital complex's admissions records. Overall, we achieve performance comparable to a simply configured MySQL database system.

References

[1]

William Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Proceedings of EUROCRYPT'01, London, UK, 2001.

Digital Library

[2]

John Bethencourt, Amit Sahai, and Brent Waters. Ciphertext-policy attribute-based encryption. In Proceedings of S&P'07, Washington, DC, USA, 2007.

Digital Library

[3]

Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970.

Digital Library

[4]

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public key encryption with keyword search. In Proceedings of EUROCRYPT'04, 2004.

[5]

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, and William E. Skeith III. Public key encryption that allows PIR queries. In Proceedings of CRYPTO'07, 2007.

Digital Library

[6]

Dan Boneh and Brent Waters. Conjunctive, subset, and range queries on encrypted data. In Proceedings of TCC. Springer, 2006.

Digital Library

[7]

Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13, 2000.

[8]

Yan cheng Chang and Michael Mitzenmacher. Privacy preserving keyword searches on remote encrypted data. In Proceedings of ACNS, volume 3531, 2005.

Digital Library

[9]

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

[10]

Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. J. ACM, 45(6):965--981, 1998.

Digital Library

[11]

Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky. Single database private information retrieval implies oblivious transfer. In EUROCRYPT, pages 122--138, 2000.

Digital Library

[12]

Emiliano De Cristofaro, Yanbin Lu, and Gene Tsudik. Efficient techniques for privacy-preserving sharing of sensitive information. In TRUST, 2011.

Digital Library

[13]

Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of CCS'06. ACM, 2006.

Digital Library

[14]

Emiliano De Cristofaro, Stanislaw Jarecki, Jihye Kim, and Gene Tsudik. Privacy-preserving policy-based information transfer. In Proceedings of PETS, 2009.

Digital Library

[15]

Craig Gentry and Zulfikar Ramzan. Single-database private information retrieval with constant communication rate. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, 2005.

Digital Library

[16]

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences, 60(3):592--629, 2000.

Digital Library

[17]

Eu-Jin Goh. Secure indexes. Cryptology ePrint Archive, Report 2003/216, 2004. http://eprint.iacr.org/2003/216/.

[18]

Ian Goldberg. Improving the robustness of private information retrieval. In Proceedings of the IEEE Symposium on Security and Privacy, 2007.

Digital Library

[19]

Vipul Goyal, Abhishek Jain, Omkant Pandey, and Amit Sahai. Bounded ciphertext policy attribute based encryption. In Proceedings of ICALP '08, Berlin, Heidelberg, 2008.

Digital Library

[20]

F. Allan Hubbell, Elizabeth B. Frye, Barbara V. Akin, and Lloyd Rucker. Routine admission laboratory testing for general medical patients. Medical Care, 26(6), 1988.

[21]

Intel. Threading building blocks 2.2. http://www.threadingbuildingblocks.org/, 2009.

[22]

J. Katz, A. Sahai, and B. Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In Proceedings of EUROCRYPT. Springer, 2008.

Digital Library

[23]

Brian W. Kernighan and Rob Pike. The Practice of Programming. Addison-Wesley, 1999.

Digital Library

[24]

Brian W. Kernighan and P. J. Plauger. The Elements of Programming Style. McGraw-Hill, 1974.

Digital Library

[25]

A. Boldyareva M. Bellare and A. O'Neill. Deterministic and efficiently searchable encryption. In Proceedings of CRYPTO'07, 2007.

Digital Library

[26]

Michael Mitzenmacher and Salil Vadhan. Why simple hash functions work: Exploiting the entropy in a data stream. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 746--755, 2008.

Digital Library

[27]

Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 448--457, Philadelphia, PA, USA, 2001.

Digital Library

[28]

Femi Olumofin and Ian Goldberg. Privacy-preserving queries over relational databases. In Proceedings of PETS, pages 75--92, 2010.

Digital Library

[29]

Femi Olumofin and Ian Goldberg. Revisiting the computational practicality of private information retrieval. In Financial Cryptography, 2011.

Digital Library

[30]

Mariana Raykova, Binh Vo, Steven Bellovin, and Tal Malkin. Secure anonymous database search. In CCSW 2009., 2009.

Digital Library

[31]

Jitesh Shetty and Jafar Adibi. The enron email dataset database schema and brief statistical report. Technical report, USC, 2004.

[32]

Elaine Shi, John Bethencourt, T-H. Hubert Chan, Dawn Song, and Adrian Perrig. Multi-dimensional range query over encrypted data. In Proceedings of S&P'07, pages 350--364, Washington, DC, USA, 2007.

Digital Library

[33]

Dawn Xiaodong Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Proceedings of S&P'00, Washington, DC, USA, 2000.

Digital Library

[34]

Peter Williams and Radu Sion. Usable PIR. In NDSS, 2008.

Cited By

Dauterman EFeng ELuo EPopa RStoica ILu SHowell J(2020)DORYProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488828(1101-1119)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488828
Kim MLee HLing SRen STan BWang H(2019)Search Condition-Hiding Query Evaluation on Encrypted DatabasesIEEE Access10.1109/ACCESS.2019.2951695(1-1)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2951695
Handa RKrishna CAggarwal N(2019)Searchable encryption: A survey on privacy‐preserving search schemes on encrypted outsourced dataConcurrency and Computation: Practice and Experience10.1002/cpe.520131:17Online publication date: 2-Apr-2019
https://doi.org/10.1002/cpe.5201
Show More Cited By

Index Terms

Private search in the real world

Recommendations

Secure and private search protocols for RFID systems

In many real world applications, there is a need to search for RFID tagged items. In this paper, we propose a set of protocols for secure and private search for tags based on their identities or certain criteria they must satisfy. When RFID enabled ...
Private web search
WPES '07: Proceedings of the 2007 ACM workshop on Privacy in electronic society

Web search is currently a source of growing concern about personal privacy. It is an essential and central part of most users' activity online and therefore one through which a significant amount of personal information may be revealed.To help users ...
Real-World Identification: Towards a Privacy-Aware Mobile eID for Physical and Offline Verification
MoMM '16: Proceedings of the 14th International Conference on Advances in Mobile Computing and Multi Media

There are many systems that provide users with an electronic identity (eID) to sign documents or authenticate to online services (e.g. governmental eIDs, OpenID). However, current solutions lack in providing proper techniques to use them as regular ID ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ACSAC '11: Proceedings of the 27th Annual Computer Security Applications Conference

December 2011

432 pages

ISBN:9781450306720

DOI:10.1145/2076732

Conference Chair:
Robert H'obbes' Zakon
Zakon Group LLC
,
Program Chairs:
John McDermott
Naval Research Lab
,
Michael Locasto
University of Calgary

Copyright © 2011 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

ACSA: Applied Computing Security Assoc

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 December 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Air Force Office of Scientific Research

Conference

ACSAC '11

Sponsor:

ACSA

ACSAC '11: Annual Computer Security Applications Conference

December 5 - 9, 2011

Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 104 of 497 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
298
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dauterman EFeng ELuo EPopa RStoica ILu SHowell J(2020)DORYProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488828(1101-1119)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488828
Kim MLee HLing SRen STan BWang H(2019)Search Condition-Hiding Query Evaluation on Encrypted DatabasesIEEE Access10.1109/ACCESS.2019.2951695(1-1)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2951695
Handa RKrishna CAggarwal N(2019)Searchable encryption: A survey on privacy‐preserving search schemes on encrypted outsourced dataConcurrency and Computation: Practice and Experience10.1002/cpe.520131:17Online publication date: 2-Apr-2019
https://doi.org/10.1002/cpe.5201
Poh GChin JYau WChoo KMohamad M(2017)Searchable Symmetric EncryptionACM Computing Surveys10.1145/306400550:3(1-37)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3064005
Krell FCiocarlie GGehani ARaykova M(2017)Low-Leakage Secure Search for Boolean ExpressionsTopics in Cryptology – CT-RSA 201710.1007/978-3-319-52153-4_23(397-413)Online publication date: 10-Jan-2017
https://doi.org/10.1007/978-3-319-52153-4_23
Pouliot DWright CWeippl EKatzenbeisser SKruegel CMyers AHalevi S(2016)The Shadow NemesisProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security10.1145/2976749.2978401(1341-1352)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2976749.2978401
Gentry CHalevi SJutla CRaykova M(2016)Private Database Access with HE-over-ORAM ArchitectureApplied Cryptography and Network Security10.1007/978-3-319-28166-7_9(172-191)Online publication date: 9-Jan-2016
https://doi.org/10.1007/978-3-319-28166-7_9
Zhu H(2015)Distributed Multi-user, Multi-key Searchable Encryptions Resilient Fault ToleranceRevised Selected Papers of the 7th International Conference on Trusted Systems - Volume 956510.1007/978-3-319-31550-8_2(17-31)Online publication date: 7-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-31550-8_2
Pappas VKrell FVo BKolesnikov VMalkin TChoi SGeorge WKeromytis ABellovin S(2014)Blind SeerProceedings of the 2014 IEEE Symposium on Security and Privacy10.1109/SP.2014.30(359-374)Online publication date: 18-May-2014
https://dl.acm.org/doi/10.1109/SP.2014.30
Wang EYe YYiu SHui L(2013)Privacy-Preserving P2P Information Sharing Protocol for Mobile Social NetworksInternational Journal of Computer and Communication Engineering10.7763/IJCCE.2013.V2.200(338-342)Online publication date: 2013
https://doi.org/10.7763/IJCCE.2013.V2.200
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.

Figures

Tables

Media

View Table of Conten