PRIVACY PRESERVING PATTERN MATCHING ON SEQUENCES OF EVENTS

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 )