Universally composable privacy preserving finite automata execution with low online and offline complexity.
Peeter Laud, Jan Willemson · IACR Cryptology ePrint Archive · 2013
In this paper, we propose ecient protocols to obliviously execute non-deterministic and deterministic nite automata (NFA and DFA) in the arithmetic black box (ABB) model. In contrast to previous approaches, our protocols do not use expensive public-key operations, relying instead only on computation with secret-shared values. Addi- tionally, the complexity of our protocols is largely oine. In particular, if the DFA is available during the precomputation phase, then the online complexity of evaluating it on an input string requires a small constant number of operations per character. This makes our protocols highly suitable for certain outsourcing applications. Keywords. Finite automata, secure multiparty computation, arithmetic black box