Paper 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.

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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Finite automatasecure multiparty computationarithmetic black box
Contact author(s)
peeter laud @ cyber ee
History
2013-11-18: revised
2013-10-24: received
See all versions
Short URL
https://ia.cr/2013/678
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/678,
      author = {Peeter Laud and Jan Willemson},
      title = {Universally composable privacy preserving finite automata execution with low online and offline complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2013/678},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/678}},
      url = {https://eprint.iacr.org/2013/678}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.