{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T15:54:42Z","timestamp":1788450882837,"version":"build-2803163510"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>\n            In this work we design new searchable encryption schemes whose goal is to minimize the\n            <jats:italic>number of cryptographic operations<\/jats:italic>\n            required to retrieve the result---a dimension mostly overlooked by previous works, yet very important in practice. Our main idea is to utilize compression so as to reduce the size of the plaintext indexes before producing the encrypted searchable indices. Our solution can use any existing Searchable Encryption (SE) scheme as a black-box and any combination of lossless compression algorithms, without compromising security.\n          <\/jats:p>\n          <jats:p>The efficiency of our schemes varies based on the leakage exposed by the underlying application. For instance, for private keyword search (more leakage), we demonstrate up to 188\u00d7 savings in search time, while for database search (less leakage) our savings are up to 62\u00d7.<\/jats:p>\n          <jats:p>The power of our approach is better manifested when combined with more secure, yet less practical, cryptographic tools, such as Oblivious Random Access Memory (ORAM). In particular while ORAM is known to be prohibitively expensive for large-scale applications, we show that our compress-first-ORAM-next approach allows significant more efficient index search time, reducing the time for executing a query with result of size more than one million tuples from approximately 21 hours to 20 minutes.<\/jats:p>","DOI":"10.14778\/3236187.3236218","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1729-1741","source":"Crossref","is-referenced-by-count":21,"title":["Efficient searchable encryption through compression"],"prefix":"10.14778","volume":"11","author":[{"given":"Ioannis","family":"Demertzis","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajdeep","family":"Talapatra","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Bouncy castle. http:\/\/www.bouncycastle.org.  Bouncy castle. http:\/\/www.bouncycastle.org."},{"key":"e_1_2_1_2_1","unstructured":"Crimes 2001 to present (city of chicago). https:\/\/data.cityofchicago.org\/public-safety\/crimes-2001-to-present\/ijzp-q8t2.  Crimes 2001 to present (city of chicago). https:\/\/data.cityofchicago.org\/public-safety\/crimes-2001-to-present\/ijzp-q8t2."},{"key":"e_1_2_1_3_1","unstructured":"Enron email dataset. https:\/\/www.cs.cmu.edu\/enron\/.  Enron email dataset. https:\/\/www.cs.cmu.edu\/enron\/."},{"key":"e_1_2_1_4_1","volume-title":"CIDR","author":"Arasu A.","year":"2013","unstructured":"A. Arasu , S. Blanas , K. Eguro , R. Kaushik , D. Kossmann , R. Ramamurthy , and R. Venkatesan . Orthogonal security with cipherbase . In CIDR , 2013 . A. Arasu, S. Blanas, K. Eguro, R. Kaushik, D. Kossmann, R. Ramamurthy, and R. Venkatesan. Orthogonal security with cipherbase. In CIDR, 2013."},{"key":"e_1_2_1_5_1","volume-title":"Oblivious computation with data locality. ePrint IACR","author":"Asharov G.","year":"2017","unstructured":"G. Asharov , T. H. Chan , K. Nayak , R. Pass , L. Ren , and E. Shi . Oblivious computation with data locality. ePrint IACR , 2017 . G. Asharov, T. H. Chan, K. Nayak, R. Pass, L. Ren, and E. Shi. Oblivious computation with data locality. ePrint IACR, 2017."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897562"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989346"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978303"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2014.23264"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_20"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994528"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2590701.2590705"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/96749.98245"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_13"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882911"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167971"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064057"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24177-7_7"},{"key":"e_1_2_1_23_1","volume-title":"Stanford University","author":"Gentry C.","year":"2009","unstructured":"C. Gentry . A Fully Homomorphic Encryption Scheme. PhD thesis , Stanford University , 2009 . C. Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1666420.1666444"},{"key":"e_1_2_1_25_1","volume-title":"Secure Indexes. IACR Cryptology ePrint Archive","author":"Goh E.-J.","year":"2003","unstructured":"E.-J. Goh Secure Indexes. IACR Cryptology ePrint Archive , 2003 . E.-J. Goh et al. Secure Indexes. IACR Cryptology ePrint Archive, 2003."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027282"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56617-7_4"},{"key":"e_1_2_1_30_1","volume-title":"FC","author":"Kamara S.","year":"2013","unstructured":"S. Kamara and C. Papamanthou . Parallel and Dynamic Searchable Symmetric Encryption . In FC , 2013 . S. Kamara and C. Papamanthou. Parallel and Dynamic Searchable Symmetric Encryption. In FC, 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382298"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","DOI":"10.1201\/b17668","volume-title":"Introduction to modern cryptography","author":"Katz J.","year":"2014","unstructured":"J. Katz and Y. Lindell . Introduction to modern cryptography . CRC press , 2014 . J. Katz and Y. Lindell. Introduction to modern cryptography. CRC press, 2014."},{"key":"e_1_2_1_33_1","volume-title":"Secure compression: Theory and practice. IACR Cryptology ePrint Archive","author":"Kelley J.","year":"2014","unstructured":"J. Kelley and R. Tamassia . Secure compression: Theory and practice. IACR Cryptology ePrint Archive , 2014 , 2014. J. Kelley and R. Tamassia. Secure compression: Theory and practice. IACR Cryptology ePrint Archive, 2014, 2014."},{"key":"e_1_2_1_34_1","volume-title":"FC","author":"Kurosawa K.","year":"2012","unstructured":"K. Kurosawa and Y. Ohtaki . UC-Secure Searchable Symmetric Encryption . In FC , 2012 . K. Kurosawa and Y. Ohtaki. UC-Secure Searchable Symmetric Encryption. In FC, 2012."},{"key":"e_1_2_1_35_1","volume-title":"On the (in) security of hash-based oblivious ram and a new balancing scheme","author":"Kushilevitz E.","year":"2012","unstructured":"E. Kushilevitz , S. Lu , and R. Ostrovsky . On the (in) security of hash-based oblivious ram and a new balancing scheme . In SIAM , 2012 . E. Kushilevitz, S. Lu, and R. Ostrovsky. On the (in) security of hash-based oblivious ram and a new balancing scheme. In SIAM, 2012."},{"key":"e_1_2_1_36_1","volume-title":"Dec","year":"2016","unstructured":"Lemire. javaewah , Dec 2016 . Lemire. javaewah, Dec 2016."},{"key":"e_1_2_1_37_1","unstructured":"Lemire. Javafastpfor Apr 2017.  Lemire. Javafastpfor Apr 2017."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2203"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.08.006"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2017.23394"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00045"},{"key":"e_1_2_1_42_1","volume-title":"CRYPTO.","author":"Pinkas B.","year":"2010","unstructured":"B. Pinkas and T. Reinman . Oblivious RAM Revisited . In CRYPTO. 2010 . B. Pinkas and T. Reinman. Oblivious RAM Revisited. In CRYPTO. 2010."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1108\/eb046814"},{"key":"e_1_2_1_45_1","volume-title":"Enclavedb: A secure database using sgx. SP","author":"Priebe C.","year":"2018","unstructured":"C. Priebe , K. Vaswani , and M. Costa . Enclavedb: A secure database using sgx. SP , 2018 . C. Priebe, K. Vaswani, and M. Costa. Enclavedb: A secure database using sgx. SP, 2018."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"e_1_2_1_47_1","volume-title":"SP","author":"Song D. X.","year":"2000","unstructured":"D. X. Song , D. Wagner , and A. Perrig . Practical Techniques for Searches on Encrypted Data . In SP , 2000 . D. X. Song, D. Wagner, and A. Perrig. Practical Techniques for Searches on Encrypted Data. In SP, 2000."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2014.23298"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488336"},{"key":"e_1_2_1_51_1","volume-title":"SDM.","author":"Van Liesdonk P.","year":"2010","unstructured":"P. Van Liesdonk , S. Sedghi , J. Doumen , P. Hartel , and W. Jonker . Computationally Efficient Searchable Symmetric Encryption . In SDM. 2010 . P. Van Liesdonk, S. Sedghi, J. Doumen, P. Hartel, and W. Jonker. Computationally Efficient Searchable Symmetric Encryption. In SDM. 2010."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064007"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813634"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660365"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660314"},{"key":"e_1_2_1_57_1","volume-title":"NSDI","author":"Zheng W.","year":"2017","unstructured":"W. Zheng , A. Dave , J. G. Beekman , R. A. Popa , J. E. Gonzalez , and I. Stoica . Opaque: An oblivious and encrypted distributed analytics platform . In NSDI , 2017 . W. Zheng, A. Dave, J. G. Beekman, R. A. Popa, J. E. Gonzalez, and I. Stoica. Opaque: An oblivious and encrypted distributed analytics platform. In NSDI, 2017."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.150"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:39:14Z","timestamp":1672220354000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":57,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236218"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236218","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}