5PM: Secure Pattern Matching

详细信息    查看全文

• 作者：Joshua Baron (17)
  Karim El Defrawy (18)
  Kirill Minkovich (18)
  Rafail Ostrovsky (17)
  Eric Tressler (18)
  
• 关键词：Secure pattern matching ; wildcard pattern matching ; substring pattern matching ; non ; binary Hamming distance ; secure two ; party computation ; malicious adversary ; full simulation ; homomorphic encryption ; threshold encryption
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7485
• 期：1
• 页码：241-263
• 全文大小：299KB
• 参考文献：1. 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-52 (2002)
  2. Namjoshi, K., Narlikar, G.: Robust and fast pattern matching for intrusion detection. In: INFOCOM 2010, pp. 740-48. IEEE Press (2010)
  3. Osadchy, M., Pinkas, B., Jarrous, A., Moskovich, B.: Scifi - a system for secure face identification. In: IEEE S&P 2010, pp. 239-54. IEEE Computer Society (2010)
  4. Tumeo, A., Villa, O.: Accelerating dna analysis applications on gpu clusters. In: SASP 2010, pp. 71-6. IEEE Computer Society (2010)
  5. Betel, D., Hogue, C.: Kangaroo - a pattern-matching program for biological sequences. BMC Bioinformatics?3(1), 20 (2002) CrossRef
  6. Tsai, T.H.: Average case analysis of the Boyer-Moore algorithm. Random Struct. Algorithms?28, 481-98 (2006) CrossRef
  7. Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM?18(6), 333-40 (1975) CrossRef
  8. Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.?6(2), 323-50 (1977) CrossRef
  9. Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev.?31, 249-60 (1987) CrossRef
  10. 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-02. ACM (2011)
  11. Katz, J., Malka, L.: Secure text processing with applications to private DNA matching. In: CCS 2010, pp. 485-92. ACM (2010)
  12. Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient DNA searching through oblivious automata. In: CCS 2007, pp. 519-28. ACM (2007)
  13. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword Search and Oblivious Pseudorandom Functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.?3378, pp. 303-24. Springer, Heidelberg (2005) CrossRef
  14. Vergnaud, D.: Efficient and Secure Generalized Pattern Matching via Fast Fourier Transform. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol.?6737, pp. 41-8. Springer, Heidelberg (2011) CrossRef
  15. 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.?5536, pp. 107-24. Springer, Heidelberg (2009) CrossRef
  16. Hazay, C., Toft, T.: Computationally Secure Pattern Matching in the Presence of Malicious Adversaries. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.?6477, pp. 195-12. Springer, Heidelberg (2010) CrossRef
  17. Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC 1992, pp. 723-32. ACM (1992)
  18. Micali, S.: Cs proofs. In: FOCS 1994, pp. 436-53. IEEE Computer Society (1994)
  19. 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.?36(4), 889-74 (2006) CrossRef
  20. 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.?5645, pp. 81-4. Springer, Heidelberg (2009) CrossRef
  21. 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.?4948, pp. 155-75. Springer, Heidelberg (2008) CrossRef
  22. 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.?6056, pp. 332-50. Springer, Heidelberg (2010) CrossRef
  23. Mohassel, P., Niksefat, S., Sadeghian, S., Sadeghiyan, B.: An efficient protocol for oblivious dfa evaluation and applications (2012)
  24. Yao, A.C.C.: How to generate and exchange secrets. In: FOCS 1986, pp. 162-67. IEEE Computer Society (1986)
  25. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC 1987, pp. 218-29. ACM (1987)
  26. Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer -Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.?5157, pp. 572-91. Springer, Heidelberg (2008)
  27. Damg?rd, I., Orlandi, C.: Multiparty Computation for Dishonest Majority: From Passive to Active Security at Low Cost. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 558-76. Springer, Heidelberg (2010)
  28. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169-78. ACM (2009)
  29. Hoffmann, H., Howard, M.D., Daily, M.J.: Fast pattern matching with time-delay neural networks. In: IJCNN 2011, pp. 2424-429 (2011)
  30. Cramer, R., Gennaro, R., Schoenmakers, B.: A Secure and Optimally Efficient Multi-authority Election Scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol.?1233, pp. 103-18. Springer, Heidelberg (1997)
  31. Desmedt, Y.G., Frankel, Y.: Threshold Cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.?435, pp. 307-15. Springer, Heidelberg (1990)
  32. Brandt, F.: Efficient Cryptographic Protocol Design Based on Distributed El Gamal Encryption. In: Won, D., Kim, S. (eds.) ICISC 2005. LNCS, vol.?3935, pp. 32-7. Springer, Heidelberg (2006) CrossRef
  33. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, New York (2000)
  34. Pedersen, T.P.: Non-interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.?576, pp. 129-40. Springer, Heidelberg (1992)
  35. Damg?rd, I.: On Σ protocols, www.daimi.au.dk/~ivan/Sigma.pdf
  36. Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.?1592, pp. 223-38. Springer, Heidelberg (1999)
  
• 作者单位：Joshua Baron (17)
  Karim El Defrawy (18)
  Kirill Minkovich (18)
  Rafail Ostrovsky (17)
  Eric Tressler (18)
  
  17. UCLA, Los Angeles, CA, USA, 90095
  18. HRL Laboratories, LLC, Malibu, CA, USA, 90265
  

文摘

In this paper we consider the problem of secure pattern matching that allows single character wildcards and substring matching in the malicious (stand-alone) setting. Our protocol, called 5PM, is executed between two parties: Server, holding a text of length n, and Client, holding a pattern of length m to be matched against the text, where our notion of matching is more general and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching. 5PM is the first protocol with communication complexity sub-linear in circuit size to compute non-binary substring matching in the malicious model (general MPC has communication complexity which is at least linear in the circuit size). 5PM is also the first sublinear protocol to compute non-binary Hamming distance in the malicious model. Additionally, in the honest-but-curious (semi-honest) model, 5PM is asymptotically more efficient than the best known scheme when amortized for applications that require single charcter wildcards or substring pattern matching. 5PM in the malicious model requires O((m--em class="a-plus-plus">n)k 2) bandwidth and O(m--em class="a-plus-plus">n) encryptions, where m is the pattern length and n is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth. Finally, 5PM requires only 2 rounds of communication in the honest-but-curious model and 8 rounds in the malicious model. Our techniques reduce pattern matching and generalized Hamming distance problem to a novel linear algebra formulation that allows for generic solutions based on any additively homomorphic encryption. We believe our efficient algebraic techniques are of independent interest.