Practical and privacy-preserving information retrieval from a database table
Abstract
We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for a client’s query-based access. We propose a cryptographic model for the study of such protocols, by expanding previous well-studied models of keyword search and private information retrieval to incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table.
Our first result is a 2-party private database retrieval protocol. This is the first protocol that preserves query and data privacy on such a practical data model. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size.
Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal ‘access pattern’ information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol’s runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL. This is the first protocol that achieves privacy of database and query content with practical performance.
Finally, we show a second private database retrieval protocol in the 3-party model for which we can show that no unintended information is leaked to an adversary corrupting both clients and third parties, at an only constant additional performance overhead cost.
References
[1]
D. Beaver, Commodity-based cryptography (extended abstract), in: Proc. of ACM STOC, 1997, pp. 446–455.
[2]
D. Boneh, G. Di Crescenzo, R. Ostrovsky and G. Persiano, Public key encryption with keyword search, in: Proc. of EUROCRYPT, Springer, 2004, pp. 506–522.
[3]
B. Chor, N. Gilboa and M. Naor, Private information retrieval by keywords, IACR Cryptology ePrint Archive (1998).
[4]
B. Chor, E. Kushilevitz, O. Goldreich and M. Sudan, Private information retrieval, J. ACM 45(6) (1998), 965–981.
[5]
T.M. Cover and J.A. Thomas, Elements of Information Theory, 2nd edn, Wiley, 2006.
[6]
G. Di Crescenzo, D. Cook, A. McIntosh and E. Panagos, Practical private information retrieval from a time-varying, multi-attribute, and multiple-occurrence database, in: Proc. of IFIP DBSec, Springer, 2014.
[7]
G. Di Crescenzo, J. Feigenbaum, D. Gupta, E. Panagos, J. Perry and R.N. Wright, Practical and privacy-preserving policy compliance for outsourced data, in: Proc. of WAHC, Springer, 2014.
[8]
G. Di Crescenzo and A. Ghosh, Privacy-preserving range queries from keyword queries, in: Proc. of ACM DBSec, 2015.
[9]
G. Di Crescenzo, Y. Ishai and R. Ostrovsky, Universal service-providers for private information retrieval, J. Cryptology 14(1) (2001), 37–74.
[10]
G. Di Crescenzo and D. Shallcross, On minimizing the size of encrypted databases, in: Proc. of IFIP DBSec, Springer, 2014.
[11]
M.J. Freedman, Y. Ishai, B. Pinkas and O. Reingold, Keyword search and oblivious pseudorandom functions, in: Proc. of TCC, Springer, 2005, pp. 303–324.
[12]
O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, J. ACM 33(4) (1986), 792–807.
[13]
O. Goldreich, S. Micali and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in: Proc. of ACM STOC, 1987, pp. 218–229.
[14]
O. Goldreich and R. Ostrovsky, Software protection and simulation on oblivious RAMs, J. ACM 43(3) (1996), 431–473.
[15]
H. Hacigümüs, B.R. Iyer, C. Li and S. Mehrotra, Executing SQL over encrypted data in the database-service-provider model, in: Proc. of ACM SIGMOD, 2002, pp. 216–227.
[16]
M.S. Islam, M. Kuzu and M. Kantarcioglu, Access pattern disclosure on searchable encryption: Ramification, attack and mitigation, in: Proc. of NDSS, 2012.
[17]
S. Jarecki, C.S. Jutla, H. Krawczyk, M.-C. Rosu and M. Steiner, Outsourced symmetric private information retrieval, in: Proc. of ACM CCS, 2013, pp. 875–888.
[18]
S. Jarecki and X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in: Proc. of TCC, Springer, 2009, pp. 577–594.
[19]
E. Kushilevitz and R. Ostrovsky, Replication is not needed: Single database, computationally-private information retrieval, in: Proc. of IEEE FOCS, 1997, pp. 364–373.
[20]
M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Comput. 17(2) (1988), 373–386.
[21]
R. Ostrovsky and W. Skeith, A survey of single-database private information retrieval: Techniques and applications, in: Proc. of PKC, Springer, 2007, pp. 393–411.
[22]
V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S.G. Choi, W. George, A.D. Keromytis and S. Bellovin, Blind seer: A scalable private DBMS, in: Proc. of 2014 IEEE SOSP, 2014, pp. 359–374.
[23]
Project Gutenberg, http://www.gutenberg.org.
[24]
D.X. Song, D. Wagner and A. Perrig, Practical techniques for searches on encrypted data, in: Proc. of IEEE SOSP, 2000, pp. 44–55.
[25]
E. Stefanov, M. van Dijk, E. Shi, C.W. Fletcher, L. Ren, X. Yu and S. Devadas, Path ORAM: an extremely simple oblivious RAM protocol, in: Proc. of 2013 ACM CCS, 2013, pp. 299–310.
[26]
S. Wang, X. Ding, R.H. Deng and F. Bao, Private information retrieval using trusted hardware, in: Proc. of ESORICS, Springer, 2006, pp. 49–64.
[27]
A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in: Proc. of IEEE FOCS, 1986, pp. 162–167.
Index Terms
- Practical and privacy-preserving information retrieval from a database table
Index terms have been assigned to the content through auto-classification.
Recommendations
Privacy-preserving deletion to generalization-based anonymous database
CUBE '12: Proceedings of the CUBE International Information Technology ConferenceWhile creating an anonymous database it is assumed that all data is available at the time of creation. Once record is added to database, it is not deleted or if a user wants to delete person's record from database, it will be removed from it in its next ...
A Privacy-Preserving Access Control Protocol for Database as a Service
CSSS '12: Proceedings of the 2012 International Conference on Computer Science and Service SystemDatabase as a Service (DaaS) is a common service mode in Cloud Computing. Based on Feldman (t,n) VSS protocol and ElGamal homomorphism property, we proposed a privacy-preserving access control protocol for DaaS. Using Secret Sharing, we can protect the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
IOS Press and the authors. All rights reserved.
Publisher
IOS Press
Netherlands
Publication History
Published: 01 January 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in