{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T18:54:42Z","timestamp":1784228082296,"version":"3.55.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T00:00:00Z","timestamp":1634860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU Commission","award":["H2020 RIA), 826232"],"award-info":[{"award-number":["H2020 RIA), 826232"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Digital Threats"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>Providing a method to efficiently search into outsourced encrypted data, without forsaking strong privacy guarantees, is a pressing concern rising from the separation of data ownership and data management typical of cloud-based applications. While several existing solutions allow a client to look up the occurrences of a substring in an outsourced document collection, the practical application requirements in terms of privacy and efficiency call for the improvement of such solutions. In this work, we present a privacy-preserving substring search protocol with a polylogarithmic communication cost and a limited computational effort on the server side. The proposed protocol provides search pattern and access pattern privacy, for both exact string search and character-pattern search with wildcards. Its extension to a multi-user setting shows significant savings in terms of outsourced storage w.r.t. a baseline solution where the whole dataset is replicated. The performance figures of an optimized implementation of our protocol, searching into a remotely stored genomic dataset, validate the practicality of the approach exhibiting a data transfer of less than 50 kiB to execute a query over a document of 40 MiB, with execution times on client and server in the range of a few seconds and a few minutes, respectively.<\/jats:p>","DOI":"10.1145\/3462333","type":"journal-article","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T14:16:04Z","timestamp":1620137764000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Privacy-aware Character Pattern Matching over Outsourced Encrypted Data"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4866-2500","authenticated-orcid":false,"given":"Nicholas","family":"Mainardi","sequence":"first","affiliation":[{"name":"Politecnico di Milano \u2013 DEIB, Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0840-6358","authenticated-orcid":false,"given":"Alessandro","family":"Barenghi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano \u2013 DEIB, Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3812-5429","authenticated-orcid":false,"given":"Gerardo","family":"Pelosi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano \u2013 DEIB, Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"962","volume-title":"IEEE Symposium on Security and Privacy","author":"Angel Sebastian","year":"2018","unstructured":"Sebastian Angel, Hao Chen, Kim Laine, and Srinath T. V. Setty. 2018. PIR with compressed queries and amortized query processing. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 962\u2013979. DOI:https:\/\/doi.org\/10.1109\/SP.2018.00062"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2046707.2046785"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2636328"},{"key":"e_1_3_3_5_2","volume-title":"A Block-sorting Lossless Data Compression Algorithm","author":"Burrows Michael","year":"1994","unstructured":"Michael Burrows and David Wheeler. 1994. A Block-sorting Lossless Data Compression Algorithm. Technical Report. Digital Equipment Corporation. Retrieved from http:\/\/www.hpl.hp.com\/techreports\/Compaq-DEC\/SRC-RR-124.pdf."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813700"},{"issue":"2","key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1515\/popets-2015-0014","article-title":"Substring-searchable symmetric encryption","volume":"2015","author":"Chase Melissa","year":"2015","unstructured":"Melissa Chase and Emily Shen. 2015. Substring-searchable symmetric encryption. PoPETs 2015, 2 (2015), 263\u2013281. Retrieved from http:\/\/www.degruyter.com\/view\/j\/popets.2015.2015.issue-2\/popets-2015-0014\/popets-2015-0014.xml.","journal-title":"PoPETs"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkp1137"},{"key":"e_1_3_3_9_2","first-page":"86","article-title":"Intel SGX explained","volume":"2016","author":"Costan Victor","year":"2016","unstructured":"Victor Costan and Srinivas Devadas. 2016. Intel SGX explained. IACR Cryptology ePrint Archive 2016 (2016), 86. https:\/\/eprint.iacr.org\/2016\/086.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/648118.746742"},{"key":"e_1_3_3_12_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/978-3-319-24177-7_7","volume-title":"20th European Symposium on Research in Computer Security","author":"Faber Sky","year":"2015","unstructured":"Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel-Catalin Rosu, and Michael Steiner. 2015. Rich queries on encrypted data: Beyond exact matches. In 20th European Symposium on Research in Computer Security(Lecture Notes in Computer Science, Vol. 9327), G\u00fcnther Pernul, Peter Y. A. Ryan, and Edgar R. Weippl (Eds.). Springer, 123\u2013145. DOI:https:\/\/doi.org\/10.1007\/978-3-319-24177-7_7"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-017-0374-0"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868248"},{"key":"e_1_3_3_16_2","volume-title":"Ensembl Genome Browser","author":"al. Paul Flicek et","year":"2000","unstructured":"Paul Flicek et al.2000. Ensembl Genome Browser. Retrieved from www.ensembl.org\/."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_3_18_2","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library","author":"Granlund Torbj\u00f6rn","year":"2012","unstructured":"Torbj\u00f6rn Granlund and the GMP development team. 2012. GNU MP: The GNU Multiple Precision Arithmetic Library. Retrieved from http:\/\/gmplib.org\/."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183754"},{"key":"e_1_3_3_20_2","volume-title":"PCRE - Perl Compatible Regular Expressions","author":"Hazel Philip","year":"2015","unstructured":"Philip Hazel. 2015. PCRE - Perl Compatible Regular Expressions. Retrieved from https:\/\/www.pcre.org."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-191300"},{"key":"e_1_3_3_22_2","first-page":"1","volume-title":"IEEE International Conference on Smart Computing","author":"Ishimaki Yu","year":"2017","unstructured":"Yu Ishimaki, Hiroki Imabayashi, and Hayato Yamana. 2017. Private substring search on homomorphically encrypted data. In IEEE International Conference on Smart Computing. IEEE Computer Society, 1\u20136. DOI:https:\/\/doi.org\/10.1109\/SMARTCOMP.2017.7947038"},{"key":"e_1_3_3_23_2","volume-title":"OpenSSL\u2014Cryptography and SSL\/TLS Toolkit","author":"al. Ben Kaduk et","year":"2015","unstructured":"Ben Kaduk et al.2015. OpenSSL\u2014Cryptography and SSL\/TLS Toolkit. Retrieved from https:\/\/www.openssl.org."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3201595.3201598"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2016.2581316"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/11556992_23"},{"key":"e_1_3_3_27_2","volume-title":"Privacy Preserving Substring Search Protocol with Polylogarithmic Communication Cost\u2014Software implementation","author":"Mainardi Nicholas","year":"2019","unstructured":"Nicholas Mainardi. 2019. Privacy Preserving Substring Search Protocol with Polylogarithmic Communication Cost\u2014Software implementation. Retrieved from https:\/\/dx.doi.org\/10.5281\/zenodo.3384814"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3359789.3359842"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3427228.3427296"},{"issue":"2","key":"e_1_3_3_30_2","article-title":"XPIR: Private information retrieval for everyone","volume":"2016","author":"Melchor Carlos Aguilar","year":"2016","unstructured":"Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. 2016. XPIR: Private information retrieval for everyone. PoPETs 2016, 2 (2016). DOI:https:\/\/doi.org\/10.1515\/popets-2016-0010","journal-title":"PoPETs"},{"key":"e_1_3_3_31_2","first-page":"722","article-title":"Oblivious substring search with updates","volume":"2015","author":"Moataz Tarik","year":"2015","unstructured":"Tarik Moataz and Erik-Oliver Blass. 2015. Oblivious substring search with updates. IACR Cryptology ePrint Archive 2015 (2015), 722. Retrieved from http:\/\/eprint.iacr.org\/2015\/722.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1756123.1756146"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2980375"},{"issue":"3","key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1515\/popets-2017-0034","article-title":"A leakage-abuse attack against multi-user searchable encryption","volume":"2017","author":"Rompay C\u00e9dric Van","year":"2017","unstructured":"C\u00e9dric Van Rompay, Refik Molva, and Melek \u00d6nen. 2017. A leakage-abuse attack against multi-user searchable encryption. PoPETs 2017, 3 (2017), 168. DOI:https:\/\/doi.org\/10.1515\/popets-2017-0034","journal-title":"PoPETs"},{"issue":"11","key":"e_1_3_3_35_2","article-title":"Efficient privacy-preserving string search and an application in genomics","volume":"32","author":"Shimizu Kana","year":"2016","unstructured":"Kana Shimizu, Koji Nuida, and Gunnar R\u00e4tsch. 2016. Efficient privacy-preserving string search and an application in genomics. Bioinformatics 32, 11 (2016). DOI:https:\/\/doi.org\/10.1093\/bioinformatics\/btw050","journal-title":"Bioinformatics"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/882494.884426"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/647094.716710"},{"issue":"3","key":"e_1_3_3_39_2","article-title":"Substring position search over encrypted cloud data supporting efficient multi-user setup","volume":"8","author":"Strizhov Mikhail","year":"2016","unstructured":"Mikhail Strizhov, Zachary Osman, and Indrajit Ray. 2016. Substring position search over encrypted cloud data supporting efficient multi-user setup. Fut. Internet 8, 3 (2016). DOI:https:\/\/doi.org\/10.3390\/fi8030028","journal-title":"Fut. Internet"},{"key":"e_1_3_3_40_2","volume-title":"libhcs: A partially Homomorphic C library","author":"Tiehuis Marc","year":"2015","unstructured":"Marc Tiehuis. 2015. libhcs: A partially Homomorphic C library. Retrieved from https:\/\/github.com\/tiehuis\/libhcs\/tree\/master\/include\/libhcs."},{"key":"e_1_3_3_41_2","first-page":"1","volume-title":"IEEE Conference on Computer Communications","author":"Wang Bing","year":"2017","unstructured":"Bing Wang, Wei Song, Wenjing Lou, and Y. Thomas Hou. 2017. Privacy-preserving pattern matching over encrypted genetic data in cloud computing. In IEEE Conference on Computer Communications. IEEE, 1\u20139. DOI:https:\/\/doi.org\/10.1109\/INFOCOM.2017.8057178"},{"issue":"3","key":"e_1_3_3_42_2","first-page":"805","article-title":"Efficient regular language search for secure cloud storage","volume":"8","author":"Yang Yang","year":"2020","unstructured":"Yang Yang, Xianghan Zheng, Chunming Rong, and Wenzhong Guo. 2020. Efficient regular language search for secure cloud storage. IEEE Trans. Cloud Comput. 8, 3 (2020), 805\u2013818. DOI:https:\/\/doi.org\/10.1109\/TCC.2018.2814594","journal-title":"IEEE Trans. Cloud Comput."}],"container-title":["Digital Threats: Research and Practice"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3462333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:19:01Z","timestamp":1750191541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,22]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3462333"],"URL":"https:\/\/doi.org\/10.1145\/3462333","relation":{},"ISSN":["2692-1626","2576-5337"],"issn-type":[{"value":"2692-1626","type":"print"},{"value":"2576-5337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,22]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}