research-article

Practical and Secure Substring Search

Authors:

Florian KerschbaumAuthors Info & Claims

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Pages 163 - 176

https://doi.org/10.1145/3183713.3183754

Published: 27 May 2018 Publication History

Abstract

In this paper we address the problem of outsourcing sensitive strings while still providing the functionality of substring searches. While security is one important aspect that requires careful system design, the practical application of the solution depends on feasible processing time and integration efforts into existing systems. That is, searchable symmetric encryption (SSE) allows queries on encrypted data but makes common indexing techniques used in database management systems for fast query processing impossible. As a result, the overhead for deploying such functional and secure encryption schemes into database systems while maintaining acceptable processing time requires carefully designed special purpose index structures. Such structures are not available on common database systems but require individual modifications depending on the deployed SSE scheme.

Our technique transforms the problem of secure substring search into range queries that can be answered efficiently and in a privacy-preserving way on common database systems without further modifications using frequency-hiding order-preserving encryption. We evaluated our prototype implementation deployed in a real-world scenario, including the consideration of network latency, we demonstrate the practicability of our scheme with 98.3 ms search time for 10,000 indexed emails. Further, we provide a practical security evaluation of this transformation based on the bucketing attack that is the best known published attack against this kind of property-preserving encryption.

References

[1]

The enron email dataset. https://www.cs.cmu.edu/~./enron/.

[2]

R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order preserving encryption for numeric data. In Proceedings of the ACM International Conference on Management of Data, SIGMOD, 2004.

Digital Library

[3]

M. Bellare, A. Boldyreva, and A. O'Neill. Deterministic and efficiently searchable encryption. In Proceedings of the 27th International Conference on Advances in Cryptology, CRYPTO, 2007.

Digital Library

[4]

M. Bellare, M. Fischlin, A. O'Neill, and T. Ristenpart. Deterministic encryption: Definitional equivalences and constructions without random oracles. Lecture Notes in Computer Science, 2008.

Digital Library

[5]

A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving symmetric encryption. In Proceedings of the 28th International Conference on Advances in Cryptology, EUROCRYPT, 2009.

[6]

A. Boldyreva, N. Chenette, and A. O'Neill. Order-preserving encryption revisited: improved security analysis and alternative solutions. In Proceedings of the 31st International Conference on Advances in Cryptology, CRYPTO, 2011.

Digital Library

[7]

D. Boneh, K. Lewi, M. Raykova, A. Sahai, M. Zhandry, and J. Zimmerman. Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT, 2015.

[8]

D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In Proceedings of the 4th Theory of Cryptography Conference, TCC, 2007.

Digital Library

[9]

D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner. Dynamic searchable encryption in very large databases: Data structures and implementation. In Proc. of NDSS, volume~14, 2014.

[10]

D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Roşu, and M. Steiner. Highly-scalable searchable symmetric encryption with support for boolean queries. In Advances in Cryptology, CRYPTO, 2013.

[11]

M. Chase and E. Shen. Substring-searchable symmetric encryption. Proceedings on Privacy Enhancing Technologies, 2015.

[12]

N. Chenette, K. Lewi, S. A. Weis, and D. J. Wu. Practical order-revealing encryption with limited leakage. In Proceedings of International Conference on Fast Software Encryption, pages 474--493. Springer, 2016.

Digital Library

[13]

R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS, 2006.

Digital Library

[14]

S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M. Rosu, and M. Steiner. Rich queries on encrypted data: Beyond exact matches. In "Computer Security -- ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II", ESORICS.

[15]

E.-J. Goh. Secure indexes. IACR Cryptology ePrint Archive, (216), 2003.

[16]

P. Grubbs, K. Sekniqi, V. Bindschaedler, M. Naveed, and T. Ristenpart. Leakage-abuse attacks against order-revealing encryption. Cryptology ePrint Archive, Report 2016/895, 2016. http://eprint.iacr.org/2016/895.

[17]

H. Hacigümücs, B. Iyer, C. Li, and S. Mehrotra. Executing sql over encrypted data in the database-service-provider model. In Proceedings of the ACM SIGMOD Conference on Management of Data, SIGMOD. ACM, 2002.

Digital Library

[18]

H. Hacigumus, B. Iyer, and S. Mehrotra. Providing database as a service. In Proceedings of the 18th International Conference on Data Engineering, ICDE. IEEE, 2002.

Digital Library

[19]

F. Hahn and F. Kerschbaum. Poly-logarithmic range queries on encrypted data with small leakage. In 8th ACM Cloud Computing Security Workshop, CCSW, 2016.

Digital Library

[20]

S. Kamara, C. Papamanthou, and T. Roeder. Dynamic searchable symmetric encryption. In Proceedings of the 19th ACM Conference on Computer and Communications Security, CCS, 2012.

Digital Library

[21]

F. Kerschbaum. Frequency-hiding order-preserving encryption. In Proceedings of the 22nd ACM Conference on Computer and Communications Security, CCS, 2015.

Digital Library

[22]

F. Kerschbaum and A. Schröpfer. Optimal average-complexity ideal-security order-preserving encryption. In Proceedings of the 21st ACM SIGSAC Conference on Computer and Communications Security, CCS, 2014.

Digital Library

[23]

K. Lewi and D. J. Wu. Order-revealing encryption: New constructions, applications, and lower bounds. In Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security, CCS, 2016.

Digital Library

[24]

Y. Lu. Privacy-preserving logarithmic-time search on encrypted data in cloud. In Proceedings of the 19th Network and Distributed System Security Symposium, NDSS, 2012.

[25]

C. Mavroforakis, N. Chenette, A. O'Neill, G. Kollios, and R. Canetti. Modular order-preserving encryption, revisited. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD, 2015.

Digital Library

[26]

M. Naveed, S. Kamara, and C. V. Wright. Inference attacks on property-preserving encrypted databases. In Proceedings of the 22nd ACM Conference on Computer and Communications Security, CCS, 2015.

Digital Library

[27]

M. Naveed, M. Prabhakaran, and C. A. Gunter. Dynamic searchable encryption via blind storage. In Proceedings of the 35th Symposium on Security and Privacy, S&P, 2014.

Digital Library

[28]

R. A. Popa, F. H. Li, and N. Zeldovich. An ideal-security protocol for order-preserving encoding. In Proceedings of the 2013 Symposium on Security and Privacy, S &P, 2013.

Digital Library

[29]

R. A. Popa, C. Redfield, N. Zeldovich, and H. Balakrishnan. CryptDB: protecting confidentiality with encrypted query processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP. ACM, 2011.

Digital Library

[30]

D. S. Roche, D. Apon, S. G. Choi, and A. Yerukhimovich. Pope: Partial order preserving encoding. In Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security, CCS, 2016.

Digital Library

[31]

E. Shi, J. Bethencourt, H. T.-H. Chan, D. X. Song, and A. Perrig. Multi-dimensional range query over encrypted data. In Proceedings of the 2007 Symposium on Security and Privacy, S&P, 2007.

Digital Library

[32]

D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In Proceedings of the 21st IEEE Symposium on Security and Privacy, S&P, 2000.

Digital Library

[33]

E. Stefanov, C. Papamanthou, and E. Shi. Practical dynamic searchable encryption with small leakage. 2013, 2013.

Cited By

Hoang NNguyen T(2024)Build Feature Vector for String Supporting Pattern Matching on Encrypted Character DataProceedings of the International Conference on Intelligent Systems and Networks10.1007/978-981-97-5504-2_41(345-354)Online publication date: 1-Sep-2024
https://doi.org/10.1007/978-981-97-5504-2_41
Cao XLiu JShen YYe XRen K(2023)Frequency-Revealing Attacks against Frequency-Hiding Order-Preserving EncryptionProceedings of the VLDB Endowment10.14778/3611479.361151316:11(3124-3136)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611513
Li FMa JMiao YLiu XNing JDeng R(2023)A Survey on Searchable Symmetric EncryptionACM Computing Surveys10.1145/361799156:5(1-42)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3617991
Show More Cited By

Index Terms

Practical and Secure Substring Search
1. Security and privacy
  1. Database and storage security
    1. Management and querying of encrypted data
2. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic protocols
  2. Theory and algorithms for application domains
    1. Database theory
      1. Theory of database privacy and security

Recommendations

Practical forward secure group signature schemes
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

A group signature scheme allows a group member to sign messages anonymously on behalf of the group, while in case of a dispute, a designated entity can reveal the identity of a signature's originator. Group signature schemes can be used as a basic ...
Toward Practical Anonymous Rerandomizable RCCA Secure Encryptions
Information and Communications Security
Abstract
Replayable adaptively chosen ciphertext attack (RCCA) security is a relaxation of popular adaptively chosen ciphertext attack (CCA) security for public key encryption system. Unlike CCA security, RCCA security allows modifying a ciphertext into a ...
Secure and practical threshold RSA
SIN '13: Proceedings of the 6th International Conference on Security of Information and Networks

This article describes a scheme that outputs RSA signatures using a threshold mechanism in which each share has a bitlength close to the bitlength of the RSA modulus. The scheme is proven unforgeable under the standard RSA assumption against an honest ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

May 2018

1874 pages

ISBN:9781450347037

DOI:10.1145/3183713

General Chairs:
Gautam Das
University of Texas at Arlington, USA
,
Christopher Jermaine
Rice University, USA
,
Philip Bernstein
Microsoft Research, USA

Copyright © 2018 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 the author(s) 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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Horizon 2020

Conference

SIGMOD/PODS '18

Sponsor:

SIGMOD

SIGMOD/PODS '18: International Conference on Management of Data

June 10 - 15, 2018

TX, Houston, USA

Acceptance Rates

SIGMOD '18 Paper Acceptance Rate 90 of 461 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
565
Total Downloads

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

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hoang NNguyen T(2024)Build Feature Vector for String Supporting Pattern Matching on Encrypted Character DataProceedings of the International Conference on Intelligent Systems and Networks10.1007/978-981-97-5504-2_41(345-354)Online publication date: 1-Sep-2024
https://doi.org/10.1007/978-981-97-5504-2_41
Cao XLiu JShen YYe XRen K(2023)Frequency-Revealing Attacks against Frequency-Hiding Order-Preserving EncryptionProceedings of the VLDB Endowment10.14778/3611479.361151316:11(3124-3136)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611513
Li FMa JMiao YLiu XNing JDeng R(2023)A Survey on Searchable Symmetric EncryptionACM Computing Surveys10.1145/361799156:5(1-42)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3617991
Zhang SRay SLu RGuan YZheng YShao J(2023)SecBerg: Secure and Practical Iceberg Queries in CloudIEEE Transactions on Services Computing10.1109/TSC.2023.326471016:5(3696-3710)Online publication date: Sep-2023
https://doi.org/10.1109/TSC.2023.3264710
Deng MZhang KWu PWen MNing J(2023)DCDPI: Dynamic and Continuous Deep Packet Inspection in Secure Outsourced MiddleboxesIEEE Transactions on Cloud Computing10.1109/TCC.2023.329313411:4(3510-3524)Online publication date: Oct-2023
https://doi.org/10.1109/TCC.2023.3293134
Fan KChen QSu RZhang KWang HLi HYang Y(2023)MSIAP: A Dynamic Searchable Encryption for Privacy-Protection on Smart Grid With Cloud-Edge-EndIEEE Transactions on Cloud Computing10.1109/TCC.2021.313401511:2(1170-1181)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2021.3134015
Ngoc Hoang CHieu Nguyen MThu Thi Nguyen TQuang Vu H(2023)A novel method for designing indexes to support efficient substring queries on encrypted databasesJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2023.02.00835:3(20-36)Online publication date: Mar-2023
https://doi.org/10.1016/j.jksuci.2023.02.008
YAMAMOTO HODA RWACHI YFUJIWARA H(2022)Substring Searchable Symmetric Encryption Based on an Improved DAWGIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021EAP1122E105.A:12(1578-1590)Online publication date: 1-Dec-2022
https://doi.org/10.1587/transfun.2021EAP1122
Liu QPeng YPei SWu JPeng TWang G(2022)Prime Inner Product Encoding for Effective Wildcard-Based Multi-Keyword Fuzzy SearchIEEE Transactions on Services Computing10.1109/TSC.2020.302068815:4(1799-1812)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TSC.2020.3020688
Wang SZheng YJia XYi X(2022)PeGraph: A System for Privacy-Preserving and Efficient Search Over Encrypted Social GraphsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.320139217(3179-3194)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3201392
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