{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T21:40:05Z","timestamp":1747604405311,"version":"3.40.5"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,12]],"date-time":"2015-02-12T00:00:00Z","timestamp":1423699200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00145-014-9193-x","type":"journal-article","created":{"date-parts":[[2015,2,11]],"date-time":"2015-02-11T16:46:35Z","timestamp":1423673195000},"page":"243-282","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Automata Evaluation and Text Search Protocols with Simulation-Based Security"],"prefix":"10.1007","volume":"29","author":[{"given":"Rosario","family":"Gennaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmit","family":"Hazay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey S.","family":"Sorensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,12]]},"reference":[{"key":"9193_CR1","doi-asserted-by":"crossref","unstructured":"C. Allauzen, M. Crochemore, M. Raffinot, Factor oracle: a new structure for pattern matching, in SOFSEM, pp. 295\u2013310 (1999)","DOI":"10.1007\/3-540-47849-3_18"},{"key":"9193_CR2","unstructured":"A. Amir, M. Lewenstein, E. Porat, Faster algorithms for string matching with k mismatches, in SODA, pp. 794\u2013803 (2000)"},{"key":"9193_CR3","doi-asserted-by":"crossref","unstructured":"J. Baron, K. El Defrawy, K. Minkovich, R. Ostrovsky, E. Tressler, 5 pm: secure pattern matching, in SCN, pp. 222\u2013240 (2012)","DOI":"10.1007\/978-3-642-32928-9_13"},{"key":"9193_CR4","doi-asserted-by":"crossref","unstructured":"D. Beaver, Foundations of secure interactive computing, in CRYPTO, pp. 377\u2013391 (1991)","DOI":"10.1007\/3-540-46766-1_31"},{"key":"9193_CR5","doi-asserted-by":"crossref","unstructured":"S. Bayer, J. Groth, Efficient zero-knowledge argument for correctness of a shuffle, in EUROCRYPT, pp. 263\u2013280 (2012)","DOI":"10.1007\/978-3-642-29011-4_17"},{"key":"9193_CR6","doi-asserted-by":"crossref","unstructured":"R.S. Boyer, J.S. Moore, A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","DOI":"10.1145\/359842.359859"},{"key":"9193_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti, Security and composition of multi-party cryptographic protocols. J. Cryptol. 13, 2000 (1998)","DOI":"10.1007\/s001459910006"},{"key":"9193_CR8","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in CRYPTO, pp. 174\u2013187 (1994)","DOI":"10.1007\/3-540-48658-5_19"},{"key":"9193_CR9","doi-asserted-by":"crossref","unstructured":"D. Chaum, T.P. Pedersen, Wallet databases with observers, in CRYPTO, pp. 89\u2013105 (1992)","DOI":"10.1007\/3-540-48071-4_7"},{"key":"9193_CR10","doi-asserted-by":"crossref","unstructured":"W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644\u2013654 (1976)","DOI":"10.1109\/TIT.1976.1055638"},{"key":"9193_CR11","doi-asserted-by":"crossref","unstructured":"T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in CRYPTO, pp. 10\u201318 (1984)","DOI":"10.1007\/3-540-39568-7_2"},{"key":"9193_CR12","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, L.A. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO, pp. 77\u201393 (1990)","DOI":"10.1007\/3-540-38424-3_6"},{"key":"9193_CR13","doi-asserted-by":"crossref","unstructured":"J. Groth, S. Lu, Verifiable shuffle of large size ciphertexts, in Public key cryptography, pp. 377\u2013392 (2007)","DOI":"10.1007\/978-3-540-71677-8_25"},{"key":"9193_CR14","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"9193_CR15","unstructured":"E.-J. Goh, Secure indexes. Cryptology ePrint Archive, Report 2003\/216, 2003. http:\/\/eprint.iacr.org\/2003\/216\/"},{"key":"9193_CR16","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Tools, vol. 1 (Cambridge University Press, New York, 2001)","DOI":"10.1017\/CBO9780511546891"},{"key":"9193_CR17","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications, vol. 2 (Cambridge University Press, New York, 2004)"},{"key":"9193_CR18","doi-asserted-by":"crossref","unstructured":"C. Hazay, Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, in TCC, pp. 155\u2013175 (2008)","DOI":"10.1007\/978-3-540-78524-8_10"},{"key":"9193_CR19","unstructured":"C. Hazay, Y. Lindell, Efficient oblivious polynomial evaluation with simulation-based security. IACR Cryptol. ePrint Arch. 2009, 459 (2009)"},{"key":"9193_CR20","doi-asserted-by":"crossref","unstructured":"C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols\u2014Techniques and Constructions (Springer, Berlin, 2010)","DOI":"10.1007\/978-3-642-14303-8"},{"key":"9193_CR21","doi-asserted-by":"crossref","unstructured":"C. Hazay, K. Nissim, Efficient set operations in the presence of malicious adversaries. J. Cryptol. 25(3), 383\u2013433 (2012)","DOI":"10.1007\/s00145-011-9098-x"},{"key":"9193_CR22","doi-asserted-by":"crossref","unstructured":"C. Hazay, T. Toft, 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":"9193_CR23","doi-asserted-by":"crossref","unstructured":"Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfers efficiently, in CRYPTO, pp. 145\u2013161 (2003)","DOI":"10.1007\/978-3-540-45146-4_9"},{"key":"9193_CR24","doi-asserted-by":"crossref","unstructured":"Y. Ishai, A. Paskin, Evaluating branching programs on encrypted data, in TCC, Lecture Notes in Computer Science, vol. 4392 (Springer, Berlin, 2007), pp. 575\u2013594","DOI":"10.1007\/978-3-540-70936-7_31"},{"key":"9193_CR25","doi-asserted-by":"crossref","unstructured":"A. Jarrous, B. Pinkas, Secure hamming distance based computation and its applications, in ANCS, vol. 5536, pp. 107\u2013124 (2009)","DOI":"10.1007\/978-3-642-01957-9_7"},{"key":"9193_CR26","doi-asserted-by":"crossref","unstructured":"J. Katz, L. Malka, Secure text processing with applications to private DNA matching, in ACM Conference on Computer and Communications Security, pp. 485\u2013492 (2010)","DOI":"10.1145\/1866307.1866361"},{"key":"9193_CR27","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, J.H. Morris, V.R. Pratt, Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","DOI":"10.1137\/0206024"},{"key":"9193_CR28","doi-asserted-by":"crossref","unstructured":"Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in CRYPTO (2), pp. 1\u201317 (2013)","DOI":"10.1007\/978-3-642-40084-1_1"},{"key":"9193_CR29","doi-asserted-by":"crossref","unstructured":"Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in TCC, pp. 329\u2013346 (2011)","DOI":"10.1007\/978-3-642-19571-6_20"},{"key":"9193_CR30","doi-asserted-by":"crossref","unstructured":"S. Micali, P. Rogaway, Secure computation (abstract), in CRYPTO, pp. 392\u2013404 (1991) (this is preliminary version of unpublished 1992 manuscript)","DOI":"10.1007\/3-540-46766-1_32"},{"key":"9193_CR31","doi-asserted-by":"crossref","unstructured":"G. Navarro, V. M\u00e4kinen, Compressed full-text indexes. ACM Comput. Surv. 39(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"9193_CR32","unstructured":"M.S. Rahman, C.S. Iliopoulos, Pattern matching algorithms with don\u2019t cares, in SOFSEM (2), pp. 116\u2013126 (2007)"},{"key":"9193_CR33","doi-asserted-by":"crossref","unstructured":"C.-P. Schnorr, Efficient identification and signatures for smart cards, in CRYPTO, pp. 239\u2013252 (1989)","DOI":"10.1007\/0-387-34805-0_22"},{"key":"9193_CR34","doi-asserted-by":"crossref","unstructured":"J.R. Troncoso-Pastoriza, S. Katzenbeisser, M.U. Celik, Privacy preserving error resilient dna searching through oblivious automata, in ACM Conference on Computer and Communications Security, pp. 519\u2013528 (2007)","DOI":"10.1145\/1315245.1315309"},{"key":"9193_CR35","doi-asserted-by":"crossref","unstructured":"D. Vergnaud, Efficient and secure generalized pattern matching via fast fourier transform, in AFRICACRYPT, pp. 41\u201358 (2011)","DOI":"10.1007\/978-3-642-21969-6_3"},{"key":"9193_CR36","doi-asserted-by":"crossref","unstructured":"A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in FOCS, pp. 162\u2013167 (1986)","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9193-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-014-9193-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9193-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9193-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T21:21:22Z","timestamp":1747603282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-014-9193-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,12]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9193"],"URL":"https:\/\/doi.org\/10.1007\/s00145-014-9193-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2015,2,12]]},"assertion":[{"value":"3 June 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2015","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}