{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:40:59Z","timestamp":1759092059965,"version":"3.38.0"},"reference-count":28,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2017,9,20]],"date-time":"2017-09-20T00:00:00Z","timestamp":1505865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p> We propose a general solution to the problem of efficient substring search over encrypted data. The solution enhances existing \u201ckeyword\u201d searchable encryption schemes by allowing searching for any part of encrypted keywords without requiring one to store all possible combinations of substrings from a given dictionary. The proposed technique is based on the idea of letter orthogonalization that allows testing of string membership by performing efficient inner products. We first propose SED-1, the base protocol for substring search. We then identify some attacks on SED-1 that demonstrate the complexity of the substring search problem under different threat scenarios. This leads us to propose our second and main protocol SED-2. The protocol is also efficient in that the search complexity is linear in the size of the keyword dictionary. We run several experiments on a sizeable real world dataset to evaluate the performance of our protocol. <\/jats:p>","DOI":"10.3233\/jcs-14652","type":"journal-article","created":{"date-parts":[[2017,9,22]],"date-time":"2017-09-22T15:03:34Z","timestamp":1506092614000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":9,"title":["Substring search over encrypted data"],"prefix":"10.1177","volume":"26","author":[{"given":"Tarik","family":"Moataz","sequence":"first","affiliation":[{"name":"Department of Computer Science, Colorado State University, USA"},{"name":"Institut Mines-T\u00e9l\u00e9com Atlantique, France"}]},{"given":"Indrajit","family":"Ray","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado State University, USA"}]},{"given":"Indrakshi","family":"Ray","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado State University, USA"}]},{"given":"Abdullatif","family":"Shikfa","sequence":"additional","affiliation":[{"name":"Kindi Center for Computing Research, Qatar University, Qatar"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Cuppens","sequence":"additional","affiliation":[{"name":"Institut Mines-T\u00e9l\u00e9com Atlantique, France"}]},{"given":"Nora","family":"Cuppens","sequence":"additional","affiliation":[{"name":"Institut Mines-T\u00e9l\u00e9com Atlantique, France"}]}],"member":"179","published-online":{"date-parts":[[2017,9,20]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-007-9006-6"},{"key":"ref002","unstructured":"M.\u00a0Bellare, A.\u00a0Boldyreva and A.\u00a0O\u2019Neill, Deterministic and efficiently searchable encryption, in: Proceedings of the 27th Annual International Cryptology Conference, Santa Barbara, California, USA, 2007."},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567809"},{"key":"ref004","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, G.\u00a0Di Crescenzo, R.\u00a0Ostrovsky and G.\u00a0Persiano, Public key encryption with keyword search, in: Proceedings of the 24th International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2004.","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"ref005","unstructured":"D.\u00a0Boneh and B.\u00a0Waters, Conjunctive, subset, and range queries on encrypted data, in: Proceedings of the 4th Theory of Cryptography Conference, Amsterdam, The Netherlands, 2007."},{"key":"ref006","unstructured":"CALO Project, Enron Email Dataset, Available at http:\/\/www.cs.cmu.edu\/~enron\/, Last accessed 11\/11\/2013."},{"key":"ref007","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, P.\u00a0Grubbs, J.\u00a0Perry and T.\u00a0Ristenpart, Leakage-abuse attacks against searchable encryption, in: Proceeding of the 22th ACM Conference on Computer and Communications Security, Denver, CO, USA, 2015.","DOI":"10.1145\/2810103.2813700"},{"key":"ref008","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, J.\u00a0Jaeger, S.\u00a0Jarecki, C.\u00a0Jutla, H.\u00a0Krawczyk, M.\u00a0Rosu and M.\u00a0Steiner, Dynamic searchable encryption in very-large databases: Data structures and implementation, in: Network and Distributed System Security Symposium (NDSS\u201914), 2014.","DOI":"10.14722\/ndss.2014.23264"},{"key":"ref009","doi-asserted-by":"crossref","unstructured":"D.\u00a0Cash, S.\u00a0Jarecki, C.\u00a0Jutla, H.\u00a0Krawczyk, M.\u00a0Rosu and M.\u00a0Steiner, Highly-scalable searchable symmetric encryption with support for Boolean queries, in: Advances in Cryptology\u00a0\u2013 CRYPTO\u201913, Springer, 2013.","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"ref010","doi-asserted-by":"crossref","unstructured":"M.\u00a0Chase and S.\u00a0Kamara, Structured encryption and controlled disclosure, in: Advances in Cryptology\u00a0\u2013 ASIACRYPT\u201910, Lecture Notes in Computer Science, Vol.\u00a06477, Springer, 2010, pp.\u00a0577\u2013594.","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2015-0014"},{"key":"ref012","unstructured":"W.\u00a0Cheney and D.R.\u00a0Kincaid, Linear Algebra: Theory and Applications, Jones and Bartlett, 2009."},{"key":"ref013","doi-asserted-by":"crossref","unstructured":"R.\u00a0Curtmola, J.A.\u00a0Garay, S.\u00a0Kamara and R.\u00a0Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, in: Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, Virginia, USA, 2006.","DOI":"10.1145\/1180405.1180417"},{"key":"ref014","doi-asserted-by":"crossref","unstructured":"G.\u00a0Di Crescenzo and V.\u00a0Saraswat, Public key encryption with searchable keywords based on Jacobi symbols, in: Proceedings of the 8th International Conference on Cryptology in India, Chennai, India, 2007.","DOI":"10.1007\/978-3-540-77026-8_21"},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"S.\u00a0Faber, S.\u00a0Jarecki, H.\u00a0Krawczyk, Q.\u00a0Nguyen, M.\u00a0Rosu and M.\u00a0Steiner, Rich queries on encrypted data: Beyond exact matches, in: 20th European Symposium on Research in Computer Security ESORICS\u201915, Vienna, Austria, 2015, pp.\u00a021\u201325.","DOI":"10.1007\/978-3-319-24177-7_7"},{"key":"ref016","unstructured":"E.J.\u00a0Goh, Secure indexes, IACR Cryptology ePrint Archive 2003 (2003), 216."},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich and R.\u00a0Ostrovsky, Software protection and simulation on oblivious RAMs, J. ACM 1996.","DOI":"10.1145\/233551.233553"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320947"},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"S.\u00a0Jarecki, C.\u00a0Jutla, H.\u00a0Krawczyk, M.\u00a0Rosu and M.\u00a0Steiner, Outsourced symmetric private information retrieval, in: Proceeding of the 20th ACM Conference on Computer and Communications Security, Berlin, Germany, 2013.","DOI":"10.1145\/2508859.2516730"},{"key":"ref020","unstructured":"JSci \u2013 A Science API for Java, Available at http:\/\/jsci.sourceforge.net\/, Last accessed 12\/11\/2013."},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"S.\u00a0Kamara and C.\u00a0Papamanthou, Parallel and dynamic searchable symmetric encryption, in: Proceedings of the 17th International Conference Financial Cryptography and Data Security, Okinawa, Japan, 2013.","DOI":"10.1007\/978-3-642-39884-1_22"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"S.\u00a0Kamara, C.\u00a0Papamanthou and T.\u00a0Roeder, Dynamic searchable symmetric encryption, in: Proceedings of the ACM Conference on Computer and Communications Security, Raleigh, NC, USA, 2012.","DOI":"10.1145\/2382196.2382298"},{"key":"ref023","unstructured":"T.\u00a0Moataz and E.\u00a0Blass, Oblivious substring search with updates, IACR Cryptology ePrint Archive 2015 (2015), 722."},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"T.\u00a0Moataz and A.\u00a0Shikfa, Boolean symmetric searchable encryption, in: Proceedings of the 8th ACM Symposium on Information, Computer and Communications Security, Hangzhou, China, 2013.","DOI":"10.1145\/2484313.2484347"},{"key":"ref025","doi-asserted-by":"crossref","unstructured":"V.\u00a0Pappas, B.\u00a0Vo, F.\u00a0Krell, S.A.\u00a0Choi, V.\u00a0Kolesnikov, A.\u00a0Keromytis and T.\u00a0Malkin, Blind Seer: A Scalable Private DBMS, Manuscript, 2013.","DOI":"10.1109\/SP.2014.30"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"E.\u00a0Shi, J.\u00a0Bethencourt, H.T.H.\u00a0Chan, D.X.\u00a0Song and A.\u00a0Perrig, Multi-dimensional range query over encrypted data, in: Proceedings of the 28th IEEE Symposium on Security and Privacy, Berkley, California, USA, 2007, pp.\u00a0350\u2013364.","DOI":"10.1109\/SP.2007.29"},{"key":"ref027","unstructured":"D.X.\u00a0Song, D.\u00a0Wagner and A.\u00a0Perrig, Practical techniques for searches on encrypted data, in: Proceedings of the 21st IEEE Symposium on Security and Privacy, Berkeley, California, USA, 2000."},{"key":"ref028","doi-asserted-by":"crossref","unstructured":"E.\u00a0Stefanov, M.\u00a0van Dijk, E.\u00a0Shi, C.W.\u00a0Fletcher, L.\u00a0Ren, X.\u00a0Yu and S.\u00a0Devadas, Path ORAM: An extremely simple oblivious RAM protocol, in: Proceeding of the 20th ACM Conference on Computer and Communications Security, November, Berlin, Germany, 2013.","DOI":"10.1145\/2508859.2516660"}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-14652","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JCS-14652","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JCS-14652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T06:49:46Z","timestamp":1741675786000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JCS-14652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,20]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.3233\/JCS-14652"],"URL":"https:\/\/doi.org\/10.3233\/jcs-14652","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"type":"print","value":"0926-227X"},{"type":"electronic","value":"1875-8924"}],"subject":[],"published":{"date-parts":[[2017,9,20]]}}}