Abstract
Secure wildcard pattern matching (SWPM) involves both sender and receiver entities, where the sender holds long text and the receiver holds short pattern containing wildcard characters. The receiver only learns the position information which the short pattern string appears in the long text string, and does not disclose any information to either party other than the input length. However, standard SWPM considers single kind of wildcard which is not suitable in many scenarios, e.g., normal genes mutate into different kinds of mutated genes in the gene matching scenario.
In our study, to better address the above problem, we construct an extended SWPM variant called secure multiple types wildcard pattern matching (SMTWM). In SMTWM functionality, the pattern contains multiple types of wildcard characters, such as (*, #). Besides, wildcards of each type can match special and different characters in the text. Considering the DNA sequence which contains ‘AGCT’ as example, the wildcard ‘*’ can match A and G, and the whidcard ‘#’ can match C and T. We propose a SMTWM protocol based on the oblivious transfer (OT) and the private equality test (PEQT) protocol in semi-honest model. Furthermore, the protocol simply needs a few number of public key operations and some fast symmetric key primitive using OT extension technique. Our experiments have shown that when the length of pattern is \(2^{8}\) and the length of text is \(2^{16}\), the running time is less than 0.4 and 2.5 s in the LAN and WAN.
This work was supported by the China Postdoctoral Science Foundation (2018M632712), the National Natural Science Foundation of China for Young Scientists (61802235) and the National Natural Science Foundation of China (62071280).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kim, M., Lee, H.T., Ling, S., Tan, B.H.M., Wang, H.: Private compound wildcard queries using fully homomorphic encryption. IEEE Trans. Dependable Secur. Comput. 16(5), 743–756 (2019)
Chase, M., Shen, E.: Substring-searchable symmetric encryption. Proc. Priv. Enhancing Technol. 2015(2), 263–281 (2015)
Faber, S., Jarecki, S., Krawczyk, H., Nguyen, Q., Rosu, M., Steiner, M.: Rich queries on encrypted data: beyond exact matches. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015, Part II. LNCS, vol. 9327, pp. 123–145. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24177-7_7
Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Secure pattern matching using somewhat homomorphic encryption. In: Juels, A., Parno, B. (eds.) CCSW 2013, Proceedings of the 2013 ACM Cloud Computing Security Workshop, Co-located with CCS 2013, Berlin, Germany, 4 November 2013, pp. 65–76. ACM (2013)
Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Privacy-preserving wildcards pattern matching using symmetric somewhat homomorphic encryption. In: Susilo, W., Mu, Y. (eds.) ACISP 2014. LNCS, vol. 8544, pp. 338–353. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08344-5_22
Frikken, K.B.: Practical private DNA string searching and matching through efficient oblivious automata evaluation. In: Gudes, E., Vaidya, J. (eds.) DBSec 2009. LNCS, vol. 5645, pp. 81–94. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03007-9_6
Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.U.: Privacy preserving error resilient DNA searching through oblivious automata. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, 28–31 October 2007, pp. 519–528. ACM (2007)
Blanton, M., Aliasgari, M.: Secure outsourcing of DNA searching via finite automata. In: Foresti, S., Jajodia, S. (eds.) DBSec 2010. LNCS, vol. 6166, pp. 49–64. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13739-6_4
Katz, J., Malka, L.: Secure text processing with applications to private DNA matching. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, 4–8 October 2010, pp. 485–492. ACM (2010)
Baron, J., El Defrawy, K., Minkovich, K., Ostrovsky, R., Tressler, E.: 5PM: secure pattern matching. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 222–240. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32928-9_13
Beck, M., Kerschbaum, F.: Approximate two-party privacy-preserving string matching with linear complexity. In: IEEE International Congress on Big Data, BigData Congress 2013, Santa Clara, CA, USA, 27 June 2013–2 July 2013, pp. 31–37. IEEE Computer Society (2013)
Defrawy, K.E., Faber, S.: Blindfolded data search via secure pattern matching. Computer 46(12), 68–75 (2013)
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–212. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_12
Naehrig, M., Lauter, K.E., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Cachin, C., Ristenpart, T. (eds.) Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, 21 October 2011, pp. 113–124. ACM (2011)
Hazay, C., Toft, T.: Computationally secure pattern matching in the presence of malicious adversaries. J. Cryptol. 27(2), 358–395 (2014)
Kolesnikov, V., Rosulek, M., Trieu, N.: SWiM: secure wildcard pattern matching from OT extension. In: Meiklejohn, S., Sako, K. (eds.) FC 2018. LNCS, vol. 10957, pp. 222–240. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-58387-6_12
Wei, X., Xu, L., Zhao, M., Wang, H.: Secure extended wildcard pattern matching protocol from cut-and-choose oblivious transfer. Inf. Sci. 529, 132–140 (2020)
Saha, T.K., Rathee, D., Koshiba, T.: Effcient protocols for private wildcards pattern matching. J. Inf. Secur. Appl. 55, 102609 (2020)
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–124. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01957-9_7
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–58. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21969-6_3
Wei, X., Zhao, M., Xu, Q.: Efficient and secure outsourced approximate pattern matching protocol. Soft. Comput. 22(4), 1175–1187 (2018)
Liu, N., Xie, F., Wu, X.: Suffx array for multi-pattern matching with variable length wildcards. Intell. Data Anal. 25(2), 283–303 (2021)
Vaiwsri, S., Ranbaduge, T., Christen, P., Ng, K.S.: Accurate and efficient suffix tree based privacy-preserving string matching, CoRR abs/2104.03018 (2021). arXiv:2104.03018
Faust, S., Hazay, C., Venturi, D.: Outsourced pattern matching. Int. J. Inf. Secur. 17(3), 327–346 (2018)
Li, D., Dong, X., Cao, Z.: Secure and privacy-preserving pattern matching in outsourced computing. Secur. Commun. Netw. 9(16), 3444–3451 (2016)
Zhang, T., Wang, X., Chow, S.S.M.: Privacy-preserving multi-pattern matching. In: Deng, R., Weng, J., Ren, K., Yegneswaran, V. (eds.) SecureComm 2016. LNICST, vol. 198, pp. 199–218. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59608-2_11
Zhou, J., Choo, K.R., Cao, Z., Dong, X.: PVOPM: verifiable privacy-preserving pattern matching with efficient outsourcing in the malicious setting. IEEE Trans. Dependable Secur. Comput. 18(5), 2253–2270 (2021)
Rabin, M.O.: How to exchange secrets with oblivious transfer. IACR Cryptology ePrint Archive 450/187 (2005)
Goldreich, O.: The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, USA, pp. 218–229. ACM, New York (1987)
Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. J. Cryptol. 23(3), 422–456 (2010)
Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9
Kolesnikov, V., Kumaresan, R., Rosulek, M.: Efficient batched oblivious PRF with application to private set intersection. In: Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security, pp. 818–829. ACM, New York (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 Springer Nature Switzerland AG
About this paper
Cite this paper
Ding, S., Wei, X., Xu, L., Wang, H. (2023). SMTWM: Secure Multiple Types Wildcard Pattern Matching Protocol from Oblivious Transfer. In: Meng, W., Lu, R., Min, G., Vaidya, J. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2022. Lecture Notes in Computer Science, vol 13777. Springer, Cham. https://doi.org/10.1007/978-3-031-22677-9_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-22677-9_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22676-2
Online ISBN: 978-3-031-22677-9
eBook Packages: Computer ScienceComputer Science (R0)