Paper 2013/678 Original: eprint.iacr.org/2013/678 ↗
Universally composable privacy preserving finite automata execution with low online and offline complexity
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2013-11-18: last updated
- 2013-10-24: published
- Short URL
- https://ia.cr/2013/678
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}