{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T14:40:03Z","timestamp":1744036803721,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642329272"},{"type":"electronic","value":"9783642329289"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32928-9_13","type":"book-chapter","created":{"date-parts":[[2012,8,30]],"date-time":"2012-08-30T06:38:30Z","timestamp":1346308710000},"page":"222-240","source":"Crossref","is-referenced-by-count":36,"title":["5PM: Secure Pattern Matching"],"prefix":"10.1007","author":[{"given":"Joshua","family":"Baron","sequence":"first","affiliation":[]},{"given":"Karim","family":"El Defrawy","sequence":"additional","affiliation":[]},{"given":"Kirill","family":"Minkovich","sequence":"additional","affiliation":[]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[]},{"given":"Eric","family":"Tressler","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Al-Khalifa, S., Jagadish, H.V., Patel, J.M., Wu, Y., Koudas, N., Srivastava, D.: Structural joins: A primitive for efficient xml query pattern matching. In: ICDE 2002, pp. 141\u2013152 (2002)","DOI":"10.1109\/ICDE.2002.994704"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Namjoshi, K., Narlikar, G.: Robust and fast pattern matching for intrusion detection. In: INFOCOM 2010, pp. 740\u2013748. IEEE Press (2010)","DOI":"10.1109\/INFCOM.2010.5462149"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Osadchy, M., Pinkas, B., Jarrous, A., Moskovich, B.: Scifi - a system for secure face identification. In: IEEE S&P 2010, pp. 239\u2013254. IEEE Computer Society (2010)","DOI":"10.1109\/SP.2010.39"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Tumeo, A., Villa, O.: Accelerating dna analysis applications on gpu clusters. In: SASP 2010, pp. 71\u201376. IEEE Computer Society (2010)","DOI":"10.1109\/SASP.2010.5521145"},{"issue":"1","key":"13_CR5","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/1471-2105-3-20","volume":"3","author":"D. Betel","year":"2002","unstructured":"Betel, D., Hogue, C.: Kangaroo - a pattern-matching program for biological sequences. BMC Bioinformatics\u00a03(1), 20 (2002)","journal-title":"BMC Bioinformatics"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1002\/rsa.20111","volume":"28","author":"T.H. Tsai","year":"2006","unstructured":"Tsai, T.H.: Average case analysis of the Boyer-Moore algorithm. Random Struct. Algorithms\u00a028, 481\u2013498 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"13_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev.\u00a031, 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Baldi, P., Baronio, R., De Cristofaro, E., Gasti, P., Tsudik, G.: Countering gattaca: efficient and secure testing of fully-sequenced human genomes. In: CCS 2011, pp. 691\u2013702. ACM (2011)","DOI":"10.1145\/2046707.2046785"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Katz, J., Malka, L.: Secure text processing with applications to private DNA matching. In: CCS 2010, pp. 485\u2013492. ACM (2010)","DOI":"10.1145\/1866307.1866361"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient DNA searching through oblivious automata. In: CCS 2007, pp. 519\u2013528. ACM (2007)","DOI":"10.1145\/1315245.1315309"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-30576-7_17","volume-title":"Theory of Cryptography","author":"M.J. Freedman","year":"2005","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword Search and Oblivious Pseudorandom Functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 303\u2013324. Springer, Heidelberg (2005)"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-21969-6_3","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2011","author":"D. Vergnaud","year":"2011","unstructured":"Vergnaud, D.: Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol.\u00a06737, pp. 41\u201358. Springer, Heidelberg (2011)"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-01957-9_7","volume-title":"Applied Cryptography and Network Security","author":"A. Jarrous","year":"2009","unstructured":"Jarrous, A., Pinkas, B.: Secure Hamming Distance Based Computation and Its Applications. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol.\u00a05536, pp. 107\u2013124. Springer, Heidelberg (2009)"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-17373-8_12","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"C. Hazay","year":"2010","unstructured":"Hazay, C., Toft, T.: Computationally Secure Pattern Matching in the Presence of Malicious Adversaries. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.\u00a06477, pp. 195\u2013212. Springer, Heidelberg (2010)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC 1992, pp. 723\u2013732. ACM (1992)","DOI":"10.1145\/129712.129782"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Micali, S.: Cs proofs. In: FOCS 1994, pp. 436\u2013453. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"4","key":"13_CR19","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput.\u00a036(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-03007-9_6","volume-title":"Data and Applications Security XXIII","author":"K.B. Frikken","year":"2009","unstructured":"Frikken, K.B.: Practical Private DNA String Searching and Matching through Efficient Oblivious Automata Evaluation. In: Gudes, E., Vaidya, J. (eds.) Data and Applications Security XXIII. LNCS, vol.\u00a05645, pp. 81\u201394. Springer, Heidelberg (2009)"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-540-78524-8_10","volume-title":"Theory of Cryptography","author":"C. Hazay","year":"2008","unstructured":"Hazay, C., Lindell, Y.: Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 155\u2013175. Springer, Heidelberg (2008)"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-642-13013-7_20","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"R. Gennaro","year":"2010","unstructured":"Gennaro, R., Hazay, C., Sorensen, J.S.: Text Search Protocols with Simulation Based Security. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol.\u00a06056, pp. 332\u2013350. Springer, Heidelberg (2010)"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Mohassel, P., Niksefat, S., Sadeghian, S., Sadeghiyan, B.: An efficient protocol for oblivious dfa evaluation and applications (2012)","DOI":"10.1007\/978-3-642-27954-6_25"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: How to generate and exchange secrets. In: FOCS 1986, pp. 162\u2013167. IEEE Computer Society (1986)","DOI":"10.1109\/SFCS.1986.25"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC 1987, pp. 218\u2013229. ACM (1987)","DOI":"10.1145\/28395.28420"},{"key":"13_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1007\/978-3-540-85174-5_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"Y. Ishai","year":"2008","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer \u2013 Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"13_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/978-3-642-14623-7_30","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"I. Damg\u00e5rd","year":"2010","unstructured":"Damg\u00e5rd, I., Orlandi, C.: Multiparty Computation for Dishonest Majority: From Passive to Active Security at Low Cost. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 558\u2013576. Springer, Heidelberg (2010)"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169\u2013178. ACM (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Hoffmann, H., Howard, M.D., Daily, M.J.: Fast pattern matching with time-delay neural networks. In: IJCNN 2011, pp. 2424\u20132429 (2011)","DOI":"10.1109\/IJCNN.2011.6033533"},{"key":"13_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/3-540-69053-0_9","volume-title":"Advances in Cryptology - EUROCRYPT \u201997","author":"R. Cramer","year":"1997","unstructured":"Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally Efficient Multi-authority Election Scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol.\u00a01233, pp. 103\u2013118. Springer, Heidelberg (1997)"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/0-387-34805-0_28","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"Y.G. Desmedt","year":"1990","unstructured":"Desmedt, Y.G., Frankel, Y.: Threshold Cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 307\u2013315. Springer, Heidelberg (1990)"},{"key":"13_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/11734727_5","volume-title":"Information Security and Cryptology - ICISC 2005","author":"F. Brandt","year":"2006","unstructured":"Brandt, F.: Efficient Cryptographic Protocol Design Based on Distributed El Gamal Encryption. In: Won, D., Kim, S. (eds.) ICISC 2005. LNCS, vol.\u00a03935, pp. 32\u201347. Springer, Heidelberg (2006)"},{"key":"13_CR33","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, New York (2000)"},{"key":"13_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/3-540-46766-1_9","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"T.P. Pedersen","year":"1992","unstructured":"Pedersen, T.P.: Non-interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 129\u2013140. Springer, Heidelberg (1992)"},{"key":"13_CR35","unstructured":"Damg\u00e5rd, I.: On \u03a3 protocols, www.daimi.au.dk\/~ivan\/Sigma.pdf"},{"key":"13_CR36","series-title":"Lecture Notes in Computer Science","first-page":"223","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"P. Paillier","year":"1999","unstructured":"Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 223\u2013238. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Security and Cryptography for Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32928-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T14:14:31Z","timestamp":1744035271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32928-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642329272","9783642329289"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32928-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}