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
-
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},
url = {https://eprint.iacr.org/2013/678}
}
