Automata Evaluation and Text Search Protocols with Simulation-Based Security

详细信息    查看全文

• 作者：Rosario Gennaro ; Carmit Hazay ; Jeffrey S. Sorensen
• 关键词：Text search ; Oblivious automata evaluation ; Simulation ; based security
• 刊名：Journal of Cryptology
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：29
• 期：2
• 页码：243-282
• 全文大小：874 KB
• 参考文献：1.C. Allauzen, M. Crochemore, M. Raffinot, Factor oracle: a new structure for pattern matching, in SOFSEM, pp. 295–310 (1999)
  2.A. Amir, M. Lewenstein, E. Porat, Faster algorithms for string matching with k mismatches, in SODA, pp. 794–803 (2000)
  3.J. Baron, K. El Defrawy, K. Minkovich, R. Ostrovsky, E. Tressler, 5 pm: secure pattern matching, in SCN, pp. 222–240 (2012)
  4.D. Beaver, Foundations of secure interactive computing, in CRYPTO, pp. 377–391 (1991)
  5.S. Bayer, J. Groth, Efficient zero-knowledge argument for correctness of a shuffle, in EUROCRYPT, pp. 263–280 (2012)
  6.R.S. Boyer, J.S. Moore, A fast string searching algorithm. Commun. ACM 20(10), 762–772 (1977)
  7.R. Canetti, Security and composition of multi-party cryptographic protocols. J. Cryptol. 13, 2000 (1998)
  8.R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in CRYPTO, pp. 174–187 (1994)
  9.D. Chaum, T.P. Pedersen, Wallet databases with observers, in CRYPTO, pp. 89–105 (1992)
  10.W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)
  11.T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in CRYPTO, pp. 10–18 (1984)
  12.S. Goldwasser, L.A. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO, pp. 77–93 (1990)
  13.J. Groth, S. Lu, Verifiable shuffle of large size ciphertexts, in Public key cryptography, pp. 377–392 (2007)
  14.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–229 (1987)
  15.E.-J. Goh, Secure indexes. Cryptology ePrint Archive, Report 2003/216, 2003. http://​eprint.​iacr.​org/​2003/​216/​
  16.O. Goldreich, Foundations of Cryptography: Basic Tools, vol. 1 (Cambridge University Press, New York, 2001)
  17.O. Goldreich, Foundations of Cryptography: Basic Applications, vol. 2 (Cambridge University Press, New York, 2004)
  18.C. Hazay, Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, in TCC, pp. 155–175 (2008)
  19.C. Hazay, Y. Lindell, Efficient oblivious polynomial evaluation with simulation-based security. IACR Cryptol. ePrint Arch. 2009, 459 (2009)
  20.C. Hazay, Y. Lindell, Efficient Secure Two-Party Protocols—Techniques and Constructions (Springer, Berlin, 2010)
  21.C. Hazay, K. Nissim, Efficient set operations in the presence of malicious adversaries. J. Cryptol. 25(3), 383–433 (2012)
  22.C. Hazay, T. Toft, Computationally secure pattern matching in the presence of malicious adversaries, in ASIACRYPT, pp. 195–212 (2010)
  23.Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending oblivious transfers efficiently, in CRYPTO, pp. 145–161 (2003)
  24.Y. Ishai, A. Paskin, Evaluating branching programs on encrypted data, in TCC, Lecture Notes in Computer Science, vol. 4392 (Springer, Berlin, 2007), pp. 575–594
  25.A. Jarrous, B. Pinkas, Secure hamming distance based computation and its applications, in ANCS, vol. 5536, pp. 107–124 (2009)
  26.J. Katz, L. Malka, Secure text processing with applications to private DNA matching, in ACM Conference on Computer and Communications Security, pp. 485–492 (2010)
  27.D.E. Knuth, J.H. Morris, V.R. Pratt, Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)
  28.Y. Lindell, Fast cut-and-choose based protocols for malicious and covert adversaries, in CRYPTO (2), pp. 1–17 (2013)
  29.Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in TCC, pp. 329–346 (2011)
  30.S. Micali, P. Rogaway, Secure computation (abstract), in CRYPTO, pp. 392–404 (1991) (this is preliminary version of unpublished 1992 manuscript)
  31.G. Navarro, V. Mäkinen, Compressed full-text indexes. ACM Comput. Surv. 39(1) (2007)
  32.M.S. Rahman, C.S. Iliopoulos, Pattern matching algorithms with don’t cares, in SOFSEM (2), pp. 116–126 (2007)
  33.C.-P. Schnorr, Efficient identification and signatures for smart cards, in CRYPTO, pp. 239–252 (1989)
  34.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–528 (2007)
  35.D. Vergnaud, Efficient and secure generalized pattern matching via fast fourier transform, in AFRICACRYPT, pp. 41–58 (2011)
  36.A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in FOCS, pp. 162–167 (1986)
  
• 作者单位：Rosario Gennaro (1)
  Carmit Hazay (2)
  Jeffrey S. Sorensen (3)
  
  1. City College of New York, New York City, NY, USA
  2. Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel
  3. Google, New York, NY, USA
  
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory
  Computational Mathematics and Numerical Analysis
  Combinatorics
  Probability Theory and Stochastic Processes
  Communications Engineering and Networks
  
• 出版者：Springer New York
• ISSN：1432-1378

文摘

This paper presents efficient protocols for securely computing the following two problems: (1) The fundamental problem of pattern matching. This problem is defined in the two-party setting, where party \(P_1\) holds a pattern and party \(P_2\) holds a text. The goal of \(P_1\) is to learn where the pattern appears in the text, without revealing it to \(P_2\) or learning anything else about \(P_2\)’s text. This problem has been widely studied for decades due to its broad applicability. We present several protocols for several notions of security. We further generalize one of our solutions to solve additional pattern matching-related problems of interest. (2) Our construction from above, in the malicious case, is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem, party \(P_1\) holds an automaton and party \(P_2\) holds an input string, and they need to decide whether the automaton accepts the input, without learning anything else. Our protocol obtains full security in the face of malicious adversaries.