{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T10:35:16Z","timestamp":1742380516086},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642219689"},{"type":"electronic","value":"9783642219696"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21969-6_3","type":"book-chapter","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T15:41:28Z","timestamp":1309275688000},"page":"41-58","source":"Crossref","is-referenced-by-count":23,"title":["Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform"],"prefix":"10.1007","author":[{"given":"Damien","family":"Vergnaud","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/3-540-36178-2_13","volume-title":"Advances in Cryptology - ASIACRYPT 2002","author":"M. Abe","year":"2002","unstructured":"Abe, M., Cramer, R., Fehr, S.: Non-interactive distributed-verifier proofs and proving relations among commitments. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol.\u00a02501, pp. 206\u2013223. Springer, Heidelberg (2002)"},{"issue":"6","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K.R. Abrahamson","year":"1987","unstructured":"Abrahamson, K.R.: Generalized String Matching. SIAM J. Comput.\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R. Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology\u00a013(1), 143\u2013202 (2000)","journal-title":"J. Cryptology"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-48071-4_7","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"D. Chaum","year":"1993","unstructured":"Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol.\u00a0740, pp. 89\u2013105. Springer, Heidelberg (1993)"},{"key":"3_CR5","unstructured":"Cheon, J.H., Jarecki, S., Seo, J.H.: Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity. IACR ePrint Archive, Report 2010\/512 (2010)"},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","volume":"101","author":"P. Clifford","year":"2007","unstructured":"Clifford, P., Clifford, R.: Simple Deterministic Wildcard Matching. Inf. Process. Lett.\u00a0101(2), 53\u201354 (2007)","journal-title":"Inf. Process. Lett."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"J.W. Cooley","year":"1965","unstructured":"Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comp.\u00a019, 297\u2013301 (1965)","journal-title":"Math. Comp."},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"3_CR9","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1142\/4838","volume-title":"Jewels of Stringology","author":"M. Crochemore","year":"2002","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology, p. 310. World Scientific Publishing, Hong-Kong (2002)"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. ElGamal","year":"1985","unstructured":"ElGamal, T.: A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms. IEEE Trans. Inf. Theory\u00a031, 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3_CR11","first-page":"113","volume-title":"Complexity of Computation, SIAM-AMS","author":"M. Fischer","year":"1974","unstructured":"Fischer, M., Paterson, M.: Paterson, M.: String Matching and Other Products. Complexity of Computation. In: Karp, R. (ed.) Complexity of Computation, SIAM-AMS, vol.\u00a07, pp. 113\u2013125. American Mathematical Society, Providence (1974)"},{"key":"3_CR12","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":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-36288-6_11","volume-title":"Public Key Cryptography - PKC 2003","author":"J. Groth","year":"2002","unstructured":"Groth, J.: A verifiable secret shuffle of homomorphic encryptions. In: Desmedt, Y. (ed.) PKC 2003. LNCS, vol.\u00a02567, pp. 145\u2013160. Springer, Heidelberg (2002)"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-540-78967-3_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"J. Groth","year":"2008","unstructured":"Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 415\u2013432. Springer, Heidelberg (2008)"},{"issue":"3","key":"3_CR15","doi-asserted-by":"publisher","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. Cryptology\u00a023(3), 422\u2013456 (2010)","journal-title":"J. Cryptology"},{"key":"3_CR16","volume-title":"Information Security and Cryptography","author":"C. Hazay","year":"2010","unstructured":"Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols. In: Information Security and Cryptography. Springer, Heidelberg (2010)"},{"key":"3_CR17","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":"3_CR18","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)"},{"issue":"2","key":"3_CR19","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":"3_CR20","series-title":"Lecture Notes in Computer Science","first-page":"116","volume-title":"SOFSEM 2007: Theory and Practice of Computer Science","author":"M.S. Rahman","year":"2007","unstructured":"Rahman, M.S., Iliopoulos, C.S.: Pattern Matching Algorithms with Don\u2019t Cares. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plasil, F., Bielikov\u00e1, M. (eds.) SOFSEM 2007. LNCS, vol.\u00a04362, pp. 116\u2013126. Springer, Heidelberg (2007)"},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","volume":"4","author":"C.-P. Schnorr","year":"1991","unstructured":"Schnorr, C.-P.: Efficient Signature Generation by Smart Cards. J. Cryptology\u00a04(3), 161\u2013174 (1991)","journal-title":"J. Cryptology"},{"issue":"2","key":"3_CR22","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.jalgor.2005.01.001","volume":"57","author":"T. Schoenmeyr","year":"2005","unstructured":"Schoenmeyr, T., Zhang, D.Y.: FFT-based algorithms for the string matching with mismatches problem. J. Algorithms\u00a057(2), 130\u2013139 (2005)","journal-title":"J. Algorithms"},{"key":"3_CR23","first-page":"519","volume-title":"ACM CCS 2007: 14th Conference on Computer and Communications Security","author":"J.R. Troncoso-Pastoriza","year":"2007","unstructured":"Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient dna searching through oblivious automata. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM CCS 2007: 14th Conference on Computer and Communications Security, pp. 519\u2013528. ACM Press, New York (2007)"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0054019","volume-title":"Public Key Cryptography","author":"Y. Tsiounis","year":"1998","unstructured":"Tsiounis, Y., Yung, M.: On the security of elGamal based encryption. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol.\u00a01431, pp. 117\u2013134. Springer, Heidelberg (1998)"},{"key":"3_CR25","first-page":"160","volume-title":"23rd Annual Symposium on Foundations of Computer Science","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: Protocols for Secure Computations. In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160\u2013164. IEEE Computer Society Press, Los Alamitos (1982)"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology \u2013 AFRICACRYPT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21969-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T01:16:14Z","timestamp":1539306974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21969-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642219689","9783642219696"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21969-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}