PRIVACY PRESERVING PATTERN MATCHING ON SEQUENCES OF EVENTS

Authors

  • Vladimir A. Oleshchuk

DOI:

https://doi.org/10.47839/ijc.4.3.367

Keywords:

Pattern matching, string matching, privacy preserving, sensor networks

Abstract

We propose to use pattern matching on data streams from sensors in order to monitor and detect events of interest. We study a privacy preserving pattern matching problem where patterns are specified as sequences of constraints on input elements. We propose a new privacy preserving pattern matching algorithm over an infinite alphabet A where a pattern P is given as a sequence { pi , pi ,..., pim } 1 2 of predicates pi j defined on A . The algorithm addresses the following problem: given a pattern P and an input sequence t, find privately all positions i in t where P matches t. The privacy preserving in the context of this paper means that sensor measurements will be evaluated as predicates ( ) pi ej privately, that is, sensors will not need to disclose the measurements ( ) ( ) ( j )

References

M. Crochemore and W. Rytter, Text Algorithms, Oxford, University Press, 1994.

M. Crochemore and C. Hancart, Pattern Matching in Strings. In Handbook of Algorithms and Theory of Computation, M. Atallah, ed., CRC Press, Boca Raton, 1996.

M. Crochemore and T. Lecroq, “Pattern Matching and Text Compression Algorithms,” In The Computer Science and Engineering Handbook, A. B. Tucker, ed., CRC Press, 1997.

W. Du and M. J. Atallah, “Secure Multi-Party Computation Problems and Their Applications: A review and Open Problems,” Proc. of New Security Paradigms Workshop, 2001, pp. 13-22.

W. Du and Z. Zhan, “A practical Approach to Solve Secure Multi-Party Computation Problems,” Proc. of New security paradigms, 2002, pp. 127-135.

R. Gwadera, M. Atallah and W. Szpankowski, “Reliable Detection of Episodes in Events Sequences,” Proc. of the Third IEEE Intern. Conf. on Data Mining (ICDM'03), 2003.

D. E. Knuth, J. Morris, and V. Pratt, “Fast Pattern Matching in Strings,” SIAM Journ. on Comp., vol. 6, 1977, pp. 323-350.

J.P. Morrill, “Distributed Recognition of Patterns in Time Series Data,” Comm. of the ACM, vol. 41, 1998, pp. 45-51.

V. A. Oleshchuk, “On-line Constraint-based Pattern Matching on Sequences,” In Sequences and Their Applications – Proc. of SETA '98. C. Ding, T. Helleseth, H. Niederreiter, Eds., Springer-Verlag, 1999, pp. 330-342.

V. A. Oleshchuk, “On-line Fuzzy Pattern Matching on Sequences.,” In Advances in Fuzzy Systems and Evolutionary Computation. N.E. Mastorakis, Ed., 2001, pp. 144-149.

D. Wagner, “Resilient aggregation in sensor networks,” SASN '04: Proc. of the 2nd ACM workshop on Security of ad hoc and sensor networks, 2004, pp. 78-87.

D. Naccache and J. Stern, “A New Cryptosystem Based on Higher Residues,” In Proceedings of the 5th ACM Conf. on Computer and Communication Security, 1998, pp.59-66.

T. Okamoto and S. Uchiyama, “An Efficient Public-Key Cryptosystem as Secure as Factoring,” In Advanced in Cryptography - EUROCRYPT'98, LNCS 1403, pp. 308-318, 1998.

P. Paillier. “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” In EUROCRYPT'99, LNCS 1592, 1999, pp. 223-238.

A.C. Yao, “Protocols for Secure Computations,” In Proc. of the 23th IEEE Symp. on Foundations of Computer Science, 1982.

Downloads

Published

2014-08-01

How to Cite

Oleshchuk, V. A. (2014). PRIVACY PRESERVING PATTERN MATCHING ON SEQUENCES OF EVENTS. International Journal of Computing, 4(3), 85-90. https://doi.org/10.47839/ijc.4.3.367

Issue

2005, Volume 4, Issue 3

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.