Shangqi Lai
ABSTRACT
The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking 'partial' database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes 'Keyword Pair Result Pattern' (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a 'lightweight' HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.
Supplemental Material
- Apache. 2015. Hadoop. https://hadoop.apache.org{online}. (2015).Google Scholar
- Apache. 2015. HBase. https://hbase.apache.org{online}. (2015).Google Scholar
- S. Blake-Wilson, N. Bolyard, V.Gupta, C. Hawk, and B. Moeller. 2006. RFC4492: Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS). RFC4492, Internet Engineering Task Force (2006).Google Scholar
- B.H. Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM Vol. 13, 7 (1970), 422--426. Google ScholarDigital Library
- D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. 2004. Public Key Encryption with Keyword Search. In EUROCRYPT 2004. 506--522.Google Scholar
- D. Boneh and B. Waters. 2007. Conjunctive, Subset, and Range Queries on Encrypted Data TCC'07. 535--554. Google ScholarDigital Library
- R. Bost, B. Minaud, and O. Ohrimenko. 2017. Forward and backward private searchable encryption from constrained cryptographic primitives ACM CCS'17. 1465--1482. Google ScholarDigital Library
- A. Broder and M. Mitzenmacher. 2004. Network Applications of Bloom Filters: A survey. Internet mathematics Vol. 1, 4 (2004), 485--509.Google Scholar
- A. De Caro and V. Iovino. 2011. JPBC: Java Pairing Based Cryptography. In IEEE SCC 2011. 850--855. Google ScholarDigital Library
- D. Cash, P. Grubbs, J. Perry, and T. Ristenpart. 2015. Leakage-Abuse Attacks Against Searchable Encryption ACM CCS'15. 668--679. Google ScholarDigital Library
- D. Cash, J. Jaeger, S. Jarecki, C.S. Jutla, H. Krawczyk, M-C. Rosu, and M. Steiner. 2014. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In NDSS'14.Google Scholar
- D. Cash, S. Jarecki, C.S. Jutla, H. Krawczyk, M-C. Rosu, and M. Steiner. 2013. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In CRYPTO'13. 353--373.Google Scholar
- C-K. Chu, W.T. Zhu, J. Han, J.K. Liu, J. Xu, and J. Zhou. 2013. Security Concerns in Popular Cloud Storage Services. IEEE Pervasive Computing Vol. 12, 4 (2013), 50--57. Google ScholarDigital Library
- Cloudera. 2018. CDH Overview. https://www.cloudera.com/documentation/enterprise/5--2-x/topics/cdh_intro.html{online}. (2018).Google Scholar
- R. Cramer and V. Shoup. 1999. Signature Schemes Based on the Strong RSA Assumption ACM CCS'99. 46--51. Google ScholarDigital Library
- R. Curtmola, J.A. Garay, S. Kamara, and R. Ostrovsky. 2006. Searchable symmetric encryption: improved definitions and efficient constructions ACM CCS'06. 79--88. Google ScholarDigital Library
- J. Dean and S. Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM Vol. 51, 1 (2008), 107--113. Google ScholarDigital Library
- I. Demertzis, S. Papadopoulos, O. Papapetrou, A. Deligiannakis, and M.N. Garofalakis. 2016. Practical Private Range Search Revisited. In ACM SIGMOD'16. 185--198. Google ScholarDigital Library
- S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M-C. Rosu, and M. Steiner. 2015. Rich Queries on Encrypted Data: Beyond Exact Matches ESORICS 2015. 123--145.Google Scholar
- Wikimedia Foundation. 2017. Wikimedia Downloads. https://dumps.wikimedia.org{online}. (2017).Google Scholar
- L. George. 2011. Advanced HBase Schema Design. Technical Report. In Hadoop World 2011.Google Scholar
- E. Goh. 2003. Secure Indexes. IACR Cryptology ePrint Archive Vol. 2003 (2003), 216.Google Scholar
- IBTA. 2017. InfiniBand Specification. http://www.infinibandta.org/{online}. (2017).Google Scholar
- V. Iovino and G. Persiano. 2008. Hidden-Vector Encryption with Groups of Prime Order Pairing 2008. 75--88. Google ScholarDigital Library
- M.S. Islam, M. Kuzu, and M. Kantarcioglu. 2012. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In NDSS'12.Google Scholar
- J. Katz and Y. Lindell. 2007. Introduction to Modern Cryptography. Chapman and Hall/CRC Press. Google ScholarDigital Library
- J. Katz, A. Sahai, and B. Waters. 2013. Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. J. Cryptology Vol. 26, 2 (2013), 191--224. Google ScholarDigital Library
- K. Liang, C. Su, J. Chen, and J.K. Liu. 2016. Efficient Multi-Function Data Sharing and Searching Mechanism for Cloud-Based Encrypted Data. In ASIACCS'16. 83--94. Google ScholarDigital Library
- J.K. Liu, M.H. Au, W. Susilo, K. Liang, R. Lu, and B. Srinivasan. 2015. Secure Sharing and Searching for Real-time Video Data in Mobile Cloud. IEEE Network Vol. 29, 2 (2015), 46--50.Google ScholarDigital Library
- M. Naveed, S. Kamara, and C.V. Wright. 2015. Inference Attacks on Property-Preserving Encrypted Databases ACM CCS'15. 644--655. Google ScholarDigital Library
- A. Nikitin. 2016. Bloom Filter Scala. https://alexandrnikitin.github.io/blog/bloom-filter-for-scala/{online}. (2016).Google Scholar
- T. Okamoto and K. Takashima. 2012. Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption EUROCRYPT 2012. 591--608. Google ScholarDigital Library
- R.A. Popa, C.M.S. Redfield, N. Zeldovich, and H. Balakrishnan. 2011. CryptDB: protecting confidentiality with encrypted query processing ACM SOSP'11. 85--100. Google ScholarDigital Library
- K. Shvachko, H. Kuang, S. Radia, and R. Chansler. 2010. The Hadoop Distributed File System. In IEEE MSST'10. 1--10. Google ScholarDigital Library
- D.X. Song, D. Wagner, and A. Perrig. 2000. Practical Techniques for Searches on Encrypted Data IEEE S&P 2000. 44--55. Google ScholarDigital Library
- S. Sun, J.K. Liu, A. Sakzad, R. Steinfeld, and T.H. Yuen. 2016. An Efficient Non-interactive Multi-client Searchable Encryption with Support for Boolean Queries. In ESORICS 2016. 154--172.Google Scholar
- The Legion of the Bouncy Castle. 2007. Bouncy Castle Crypto APIs. https://www.bouncycastle.org{online}. (2007).Google Scholar
- M. Zaharia, M. Chowdhury, M.J. Franklin, S. Shenker, and I. Stoica. 2010. Spark: Cluster Computing with Working Sets. In HotCloud'10. Google ScholarDigital Library
- Y. Zhang, J. Katz, and C. Papamanthou. 2016. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption. In USENIX Security 16. 707--720. Google ScholarDigital Library
Index Terms
- Result Pattern Hiding Searchable Encryption for Conjunctive Queries
Recommendations
Integrity-verifiable conjunctive keyword searchable encryption in cloud storage
Conjunctive searchable encryption is an efficient way to perform multi-keyword search over encrypted data in cloud storage. However, most existing methods do not take into account the integrity verification of the search result. Moreover, existing ...
Mis-operation Resistant Searchable Homomorphic Encryption
ASIA CCS '17: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications SecurityLet us consider a scenario that a data holder (e.g., a hospital) encrypts a data (e.g., a medical record) which relates a keyword (e.g., a disease name), and sends its ciphertext to a server. We here suppose not only the data but also the keyword should ...
Transforming Hidden Vector Encryption Schemes from Composite to Prime Order Groups
ICISC 2016: Proceedings of the 19th International Conference on Information Security and Cryptology - Volume 10157Predicate encryption is a new type of public key encryption that enables searches on encrypted data. By using predicate encryption, we can search keywords or attributes on encrypted data without decrypting ciphertexts. Hidden vector encryption HVE is a ...
Comments