Progress in privacy-preserving parsing of regular languages
Kadri Tõldsepp

Collaboratively processing textual data or streams of events, while preserving the confidentiality of this data is a necessary task in many applications. Often, one has to find whether a text string belongs to a regular language (or, is matched by a regular expression). In UaESMC, we have made progress in privacy-preserving parsing of regular languages, by proposing new and efficient methods for obliviously executing private or public finite automata on private strings.

Our algorithms make use of certain, conceptually more complex operations that are comparatively efficient on existing Secure Multiparty Computation architectures. We represent the transfer functions of finite automata as polynomials; the main steps of our algorithms involve evaluating or composing these polynomials. Using certain representations of private data, these operations with polynomials require mostly simple local computations.