Cryptology ePrint Archive: Report 2013/678

Universally composable privacy preserving finite automata execution with low online and offline complexity

Peeter Laud and Jan Willemson

Abstract: In this paper, we propose efficient protocols to obliviously execute non-deterministic and deterministic finite 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. Additionally, the complexity of our protocols is largely offline. 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.

Category / Keywords: cryptographic protocols / Finite automata, secure multiparty computation, arithmetic black box

Date: received 23 Oct 2013, last revised 18 Nov 2013

Contact author: peeter laud at cyber ee

Available format(s): PDF | BibTeX Citation

Note: Updated the DFA execution algorithm for Shamir's secret sharing based ABBs

Version: 20131118:094300 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]