Verifiable dynamic searchable encryption

Using regular encryption schemes to protect the privacy of the outsourced data implies that the client shouldsacrifice functionality for security. Searchable symmetric encryption (SSE) schemes encrypt the data in a way that theclient can later search and selectively retrieve the required data. Many SSE schemes have been proposed, starting withstatic constructions, and then dynamic and adaptively secure constructions but usually in the honest-but-curious model.We propose a verifiable dynamic SSE scheme that is adaptively secure against malicious adversaries. Our schemesupports file modification, which is essential for efficiently working with large files, in addition to the ability to add/deletefiles. While our main construction is proven secure in the random oracle model (ROM), we also present a solution securein the standard model with full security proof. Our experiments show that our scheme in the ROM performs a searchwithin a few milliseconds, verifies the result in another few milliseconds, and has a proof overhead of 0.01% only. Ourstandard model solution, while being asymptotically slower, is still practical, requiring only a small client memory (e.g.,≃488 KB) even for a large file collection (e.g., ≃10 GB), and necessitates small tokens (e.g., ≃156 KB for search and≃362 KB for file operations).

PDF

___

[1] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions. In: ACM CCS’06; Alexandria, VA, USA; 2006. pp. 79-88.
[2] Chase M, Kamara S. Structured encryption and controlled disclosure. In: ASIACRYPT’10; Singapore; 2010. pp. 577-594.
[3] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: ACM CCS’12; Alexandria, VA, USA; 2012. pp. 965-976.
[4] Naveed M, Prabhakaran M, Gunter CA. Dynamic searchable encryption via blind storage. In: IEEE Security and Privacy (SP’14); San Jose, CA, USA; 2014. pp. 639-654.
[5] Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption. In: Financial Cryptography and Data Security (FC’13); Okinawa, Japan; 2013. pp. 258-274.
[6] Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage. In: NDSS’14; San Diego, CA, USA; 2014. pp. 72-75.
[7] Pappas V, Krell F, Vo B, Kolesnikov V, Malkin T et al. Blind seer: A scalable private dbms. In: IEEE Symposium on Security and Privacy (SP’14); San Jose, CA, USA; 2014. pp. 359-374.
[8] Wang C, Cao N, Li J, Ren K, Lou W. Secure ranked keyword search over encrypted cloud data. In: IEEE ICDCS’10; Genova, Italy; 2010. pp. 253-262.
[9] Liu C, Zhu L, Chen J. Efficient searchable symmetric encryption for storing multiple source dynamic social data on cloud. Journal of Network and Computer Applications 2017; 86:3-14.
[10] Etemad M, Küpçü A, Papamanthou C, Evans D. Efficient dynamic searchable encryption with forward privacy. Proceedings on Privacy Enhancing Technologies 2018; 2018 (1): 5-20.
[11] Ateniese G, Burns R, Curtmola R, Herring J, Kissner L et al. Provable data possession at untrusted stores. In: ACM CCS’07; Alexandria, VA, USA; 2007. pp. 598-609.
[12] Juels A, Kaliski BS. Pors: Proofs of retrievability for large files. In: ACM CCS’07; Alexandria, VA, USA; 2007. pp. 584-597.
[13] Erway C, Küpçü A, Papamanthou C, Tamassia R. Dynamic provable data possession. In: ACM CCS’09; Alexandria, VA, USA; 2009. pp. 213-222.
[14] Etemad M, Küpçü A. Transparent, distributed, and replicated dynamic provable data possession. In: ACNS’13; Banff, Alberta, Canada; 2013. pp. 1-18.
[15] Küpçü A. Official arbitration with secure cloud storage application. The Computer Journal 2015; 58 (4): 831-852.
[16] Cash D, Küpçü A, Wichs D. Dynamic proofs of retrievability via oblivious ram. In: EUROCRYPT’13; Athens, Greece; 2013. pp. 279-295.
[17] Esiner E, Kachkeev A, Braunfeld S, Küpçü A, Özkasap Ö. Flexdpdp: Flexlist-based optimized dynamic provable data possession. ACM Transactions on Storage 2016; 12 (4): 1-44.
[18] Etemad M, Küpçü A. Generic efficient dynamic proofs of retrievability. In: ACM CCSW’16; Alexandria, VA, USA; 2016. pp. 85-96.
[19] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious rams. Journal of the ACM 1996; 43 (3): 431-473.
[20] Naveed M. The fallacy of composition of oblivious ram and searchable encryption. Cryptology ePrint Archive, Report 2015/668, 2015.
[21] Goh EJ. Secure indexes. Cryptology ePrint Archive, Report 2003/216, 2003.
[22] Chang YC, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data. In: ACNS’05; New York, NY, USA; 2005. pp. 442-455.
[23] Cash D, Jaeger J, Jarecki S, Jutla C, Krawczyk H et al. Dynamic searchable encryption in very-large databases: Data structures and implementation. In: NDSS’14; San Diego, CA, USA; 2014. pp. 23-26.
[24] Cash D, Jarecki S, Jutla CS, Krawczyk H, Rosu M et al. Highly-scalable searchable symmetric encryption with support for boolean queries. In: CRYPTO’13; Santa Barbara, CA, USA; 2013. pp. 353-373.
[25] Moataz T, Shikfa A. Boolean symmetric searchable encryption. In: ACM CCS’13; Alexandria, VA, USA; 2013. pp. 265-276.
[26] Kurosawa K, Ohtaki Y. Uc-secure searchable symmetric encryption. In: Financial Cryptography and Data Security (FC’12); Bonaire; 2012. pp. 285-298.
[27] Bost R, Fouque PA, Pointcheval D. Verifiable dynamic symmetric searchable encryption: Optimality and forward security. Cryptology ePrint Archive, Report 2016/062, 2016.
[28] Ferreira B, Portela B, Oliveira T, Borges G, Domingos H et al. Bisen: Efficient boolean searchable symmetric encryption with verifiability and minimal leakage. Cryptology ePrint Archive, Report 2018/588, 2018.
29] Zhu J, Li Q, Wang C, Yuan X, Wang Q et al. Enabling generic, verifiable, and secure data search in cloud services. IEEE Transactions on Parallel and Distributed Systems 2018; 29 (8): 1721-1735.
[30] Zheng Q, Xu S, Ateniese G. Vabks: Verifiable attribute-based keyword search over outsourced encrypted data. In: IEEE INFOCOM’14; Toronto, Canada; 2014. pp. 522-530.
[31] Katz J, Lindell Y. Introduction to Modern Cryptography. London, UK: CRC Press, 2008.
[32] Tamassia R. Authenticated data structures. In: ESA’03; Budapest, Hungary; 2003. pp. 2-5.
[33] Pugh W. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM 1990; 33 (6): 668-676.
[34] Goodrich MT, Tamassia R, Triandopoulos N. Efficient authenticated data structures for graph connectivity and geometric search problems. Algorithmica 2011; 60 (3): 505-552.
[35] Merkle RC. A certified digital signature. In: CRYPTO’89; Santa Barbara, CA, USA; 1989. pp. 218-238.
[36] Etemad M, Küpçü A. Database outsourcing with hierarchical authenticated data structures. In: ICISC’13; Seoul, Korea; 2013. pp. 381-399.
[37] Etemad M, Küpçü A. Verifiable database outsourcing supporting join. Journal of Network and Computer Applications 2018; 115: 1-19.
[38] Naor M, Nissim K. Certificate revocation and certificate update. IEEE Journal on Selected Areas in Communications 2000; 18 (4): 561-570.
[39] Canetti R, Dwork C, Naor M, Ostrovsky R. Deniable encryption. In: CRYPTO’97; Santa Barbara, CA, USA; 1997. pp. 90-104.
[40] Choi SG, Dachman-Soled D, Malkin T, Wee H. Improved non-committing encryption with applications to adaptively secure protocols. In: ASIACRYPT’09; Tokyo, Japan; 2009. pp. 287-302.
[41] Esiner E, Küpçü A, Özkasap Ö. Analysis and optimizations on flexdpdp: A practical solution for dynamic provable data possession. In: ICC’14; Muscat, Oman; 2014. pp. 65-83.
[42] Örencik C, Savaş E. An efficient privacy-preserving multi-keyword search over encrypted cloud data with ranking. Distributed and Parallel Databases 2014; 32 (1): 119-160.