{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T09:10:36Z","timestamp":1778922636986,"version":"3.51.4"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T00:00:00Z","timestamp":1493683200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["644666"],"award-info":[{"award-number":["644666"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int. J. Inf. Secur."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s10207-017-0374-0","type":"journal-article","created":{"date-parts":[[2017,5,2]],"date-time":"2017-05-02T05:25:50Z","timestamp":1493702750000},"page":"327-346","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Outsourced pattern matching"],"prefix":"10.1007","volume":"17","author":[{"given":"Sebastian","family":"Faust","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmit","family":"Hazay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Venturi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,2]]},"reference":[{"key":"374_CR1","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: Efficient verification via secure computation. In: ICALP, pp. 152\u2013163 (2010)","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"374_CR2","doi-asserted-by":"crossref","unstructured":"Asharov, G., Jain, A., L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: EUROCRYPT, pp. 483\u2013501 (2012)","DOI":"10.1007\/978-3-642-29011-4_29"},{"key":"374_CR3","doi-asserted-by":"crossref","unstructured":"Au, M.H., Tsang, P.P., Susilo, W., Mu, Y.: Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems. In: CT-RSA, pp. 295\u2013308 (2009)","DOI":"10.1007\/978-3-642-00862-7_20"},{"key":"374_CR4","doi-asserted-by":"crossref","unstructured":"Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: CRYPTO, pp. 111\u2013131 (2011)","DOI":"10.1007\/978-3-642-22792-9_7"},{"issue":"10","key":"374_CR5","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"374_CR6","doi-asserted-by":"crossref","unstructured":"Buldas, A., Laud, P., Lipmaa, H.: Accountable certificate management using undeniable attestations. In: CCS, pp. 9\u201317 (2000)","DOI":"10.1145\/352600.352604"},{"issue":"3","key":"374_CR7","doi-asserted-by":"crossref","first-page":"273","DOI":"10.3233\/JCS-2002-10304","volume":"10","author":"A Buldas","year":"2002","unstructured":"Buldas, A., Laud, P., Lipmaa, H.: Eliminating counterevidence with applications to accountable certificate management. J. Comput. Secur. 10(3), 273\u2013296 (2002)","journal-title":"J. Comput. Secur."},{"issue":"5","key":"374_CR8","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s10207-012-0169-2","volume":"11","author":"P Camacho","year":"2012","unstructured":"Camacho, P., Hevia, A., Kiwi, M.A., Opazo, R.: Strong accumulators from collision-resistant hashing. Int. J. Inf. Secur. 11(5), 349\u2013363 (2012)","journal-title":"Int. J. Inf. Secur."},{"key":"374_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multi-party cryptographic protocols. J. Cryptol. 13, 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"374_CR10","doi-asserted-by":"crossref","unstructured":"Catalano, D., Fiore, D.: Vector commitments and their applications. In: PKC, pp. 55\u201372 (2013)","DOI":"10.1007\/978-3-642-36362-7_5"},{"issue":"3","key":"374_CR11","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0885-064X(89)90025-3","volume":"5","author":"M Chaimovich","year":"1989","unstructured":"Chaimovich, M., Freiman, G., Galil, Z.: Solving dense subset-sum problems by using analytical number theory. J. Complex. 5(3), 271\u2013282 (1989)","journal-title":"J. Complex."},{"issue":"2","key":"374_CR12","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1515\/popets-2015-0014","volume":"2015","author":"M Chase","year":"2015","unstructured":"Chase, M., Shen, E.: Substring-searchable symmetric encryption. PoPETs 2015(2), 263\u2013281 (2015)","journal-title":"PoPETs"},{"key":"374_CR13","doi-asserted-by":"crossref","unstructured":"Chen, Y., Nguyen, P.Q.: Bkz 2.0: Better lattice security estimates. In: ASIACRYPT, pp. 1\u201320 (2011)","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"374_CR14","doi-asserted-by":"crossref","unstructured":"Choi, S.G., Katz, J., Kumaresan, R., Cid, C.: Multi-client non-interactive verifiable computation. In: TCC, pp. 499\u2013518 (2013)","DOI":"10.1007\/978-3-642-36594-2_28"},{"key":"374_CR15","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Kalai, Y.T., Vadhan, S.P.: Improved delegation of computation using fully homomorphic encryption. In: CRYPTO, pp. 483\u2013501 (2010)","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"374_CR16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"MJ Coster","year":"1992","unstructured":"Coster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.P., Stern, J.: Improved low-density subset sum algorithms. Comput. Complex. 2, 111\u2013128 (1992)","journal-title":"Comput. Complex."},{"issue":"5","key":"374_CR17","doi-asserted-by":"crossref","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895\u2013934 (2011)","journal-title":"J. Comput. Secur."},{"key":"374_CR18","unstructured":"Damg\u00e5rd, I., Triandopoulos, N.: Supporting non-membership proofs with bilinear-map accumulators. IACR Cryptol. ePrint Archive 2008, 538 (2008). URL http:\/\/eprint.iacr.org\/2008\/538"},{"key":"374_CR19","doi-asserted-by":"crossref","unstructured":"Derler, D., Hanser, C., Slamanig, D.: Revisiting cryptographic accumulators, additional properties and relations to other primitives. In: CT-RSA, pp. 127\u2013144 (2015)","DOI":"10.1007\/978-3-319-16715-2_7"},{"key":"374_CR20","doi-asserted-by":"crossref","unstructured":"Faust, S., Hazay, C., Venturi, D.: Outsourced pattern matching. In: ICALP, pp. 545\u2013556 (2013)","DOI":"10.1007\/978-3-642-39212-2_48"},{"key":"374_CR21","doi-asserted-by":"crossref","unstructured":"Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: CCS, pp. 844\u2013855 (2014)","DOI":"10.1145\/2660267.2660366"},{"key":"374_CR22","doi-asserted-by":"crossref","unstructured":"Flaxman, A., Przydatek, B.: Solving medium-density subset sum problems in expected polynomial time. In: STACS, pp. 305\u2013314 (2005)","DOI":"10.1007\/978-3-540-31856-9_25"},{"key":"374_CR23","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: TCC, pp. 303\u2013324 (2005)","DOI":"10.1007\/978-3-540-30576-7_17"},{"issue":"2","key":"374_CR24","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1137\/0215038","volume":"15","author":"AM Frieze","year":"1986","unstructured":"Frieze, A.M.: On the Lagarias\u2013Odlyzko algorithm for the subset sum problem. SIAM J. Comput. 15(2), 536\u2013539 (1986)","journal-title":"SIAM J. Comput."},{"key":"374_CR25","doi-asserted-by":"crossref","unstructured":"Galil, Z., Margalit, O.: An almost linear-time algorithm for the dense subset-sum problem. In: ICALP, pp. 719\u2013727 (1991)","DOI":"10.1007\/3-540-54233-7_177"},{"key":"374_CR26","doi-asserted-by":"crossref","unstructured":"Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: EUROCRYPT, pp. 31\u201351 (2008)","DOI":"10.1007\/978-3-540-78967-3_3"},{"key":"374_CR27","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In: CRYPTO, pp. 465\u2013482 (2010)","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"374_CR28","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Hazay, C., Sorensen, J.S.: Text search protocols with simulation based security. In: PKC, pp. 332\u2013350 (2010)","DOI":"10.1007\/978-3-642-13013-7_20"},{"key":"374_CR29","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"374_CR30","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., Katz, J., Liu, F., Shi, E., Zhou, H.: Multi-client verifiable computation with stronger security guarantees. In: TCC, pp. 144\u2013168 (2015)","DOI":"10.1007\/978-3-662-46497-7_6"},{"issue":"3","key":"374_CR31","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/s00145-008-9034-x","volume":"23","author":"C Hazay","year":"2010","unstructured":"Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. J. Cryptol. 23(3), 422\u2013456 (2010)","journal-title":"J. Cryptol."},{"key":"374_CR32","doi-asserted-by":"crossref","unstructured":"Hazay, C., Toft, T.: Computationally secure pattern matching in the presence of malicious adversaries. In: ASIACRYPT, pp. 195\u2013212 (2010)","DOI":"10.1007\/978-3-642-17373-8_12"},{"key":"374_CR33","doi-asserted-by":"crossref","unstructured":"Hazay, C., Zarosim, H.: The feasibility of outsourced database search in the plain model. In: SCN, pp. 313\u2013332 (2016)","DOI":"10.1007\/978-3-319-44618-9_17"},{"issue":"4","key":"374_CR34","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R Impagliazzo","year":"1996","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum. J. Cryptol. 9(4), 199\u2013216 (1996)","journal-title":"J. Cryptol."},{"key":"374_CR35","doi-asserted-by":"crossref","unstructured":"Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.C., Steiner, M.: Outsourced symmetric private information retrieval. In: CCS, pp. 875\u2013888 (2013)","DOI":"10.1145\/2508859.2516730"},{"key":"374_CR36","unstructured":"Kamara, S., Mohassel, P., Raykova, M.: Outsourcing multi-party computation. IACR Cryptol. ePrint Archive 2011, 272 (2011). URL http:\/\/eprint.iacr.org\/2011\/272"},{"key":"374_CR37","doi-asserted-by":"crossref","unstructured":"Kamara, S., Mohassel, P., Riva, B.: Salus: a system for server-aided secure function evaluation. In: CCS, pp. 797\u2013808 (2012)","DOI":"10.1145\/2382196.2382280"},{"key":"374_CR38","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Financial Cryptography, pp. 258\u2013274 (2013)","DOI":"10.1007\/978-3-642-39884-1_22"},{"key":"374_CR39","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: CCS, pp. 965\u2013976 (2012)","DOI":"10.1145\/2382196.2382298"},{"key":"374_CR40","doi-asserted-by":"crossref","unstructured":"Katz, J., Malka, L.: Secure text processing with applications to private DNA matching. In: CCS, pp. 485\u2013492 (2010)","DOI":"10.1145\/1866307.1866361"},{"issue":"2","key":"374_CR41","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H.J., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"374_CR42","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985)","journal-title":"J. ACM"},{"issue":"16","key":"374_CR43","doi-asserted-by":"crossref","first-page":"3444","DOI":"10.1002\/sec.1552","volume":"9","author":"D Li","year":"2016","unstructured":"Li, D., Dong, X., Cao, Z.: Secure and privacy-preserving pattern matching in outsourced computing. Secur. Commun. Netw. 9(16), 3444\u20133451 (2016)","journal-title":"Secur. Commun. Netw."},{"key":"374_CR44","doi-asserted-by":"crossref","unstructured":"Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: ACNS, pp. 253\u2013269 (2007)","DOI":"10.1007\/978-3-540-72738-5_17"},{"key":"374_CR45","doi-asserted-by":"crossref","unstructured":"L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: STOC, pp. 1219\u20131234 (2012)","DOI":"10.1145\/2213977.2214086"},{"key":"374_CR46","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: APPROX-RANDOM, pp. 378\u2013389 (2005)","DOI":"10.1007\/11538462_32"},{"key":"374_CR47","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: TCC, pp. 382\u2013400 (2010)","DOI":"10.1007\/978-3-642-11799-2_23"},{"key":"374_CR48","doi-asserted-by":"crossref","unstructured":"Merkle, R.C.: A certified digital signature. In: CRYPTO, pp. 218\u2013238 (1989)","DOI":"10.1007\/0-387-34805-0_21"},{"key":"374_CR49","unstructured":"Mohassel, P.: Efficient and secure delegation of linear algebra. IACR Cryptol. ePrint Archive 2011, 605 (2011). URL http:\/\/eprint.iacr.org\/2011\/605"},{"key":"374_CR50","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: FOCS, pp. 458\u2013467 (1997)","DOI":"10.1109\/SFCS.1997.646134"},{"key":"374_CR51","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: LLL on the average. In: ANTS, pp. 238\u2013256 (2006)","DOI":"10.1007\/11792086_18"},{"key":"374_CR52","doi-asserted-by":"crossref","unstructured":"Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: CRYPTO, pp. 91\u2013110 (2011)","DOI":"10.1007\/978-3-642-22792-9_6"},{"key":"374_CR53","doi-asserted-by":"crossref","unstructured":"Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: CRYPTO, pp. 554\u2013571 (2008)","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"374_CR54","doi-asserted-by":"crossref","unstructured":"Shallue, A.: An improved multi-set algorithm for the dense subset sum problem. In: ANTS, pp. 416\u2013429 (2008)","DOI":"10.1007\/978-3-540-79456-1_28"},{"key":"374_CR55","doi-asserted-by":"crossref","unstructured":"Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.U.: Privacy preserving error resilient DNA searching through oblivious automata. In: CCS, pp. 519\u2013528 (2007)","DOI":"10.1145\/1315245.1315309"},{"key":"374_CR56","doi-asserted-by":"crossref","unstructured":"Zhou, J., Cao, Z., Dong, X.: PPOPM: more efficient privacy preserving outsourced pattern matching. In: ESORICS, pp. 135\u2013153 (2016)","DOI":"10.1007\/978-3-319-45744-4_7"}],"container-title":["International Journal of Information Security"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10207-017-0374-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-017-0374-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-017-0374-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T03:09:37Z","timestamp":1658977777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10207-017-0374-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,2]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["374"],"URL":"https:\/\/doi.org\/10.1007\/s10207-017-0374-0","relation":{},"ISSN":["1615-5262","1615-5270"],"issn-type":[{"value":"1615-5262","type":"print"},{"value":"1615-5270","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,2]]}}}