Paper 2023/1169
Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA
Abstract
In oblivious finite automata evaluation, one party holds a private automaton, and the other party holds a private string of characters. The objective is to let the parties know whether the string is accepted by the automaton or not, while keeping their inputs secret. The applications include DNA searching, pattern matching, and more. Most of the previous works are based on asymmetric cryptographic primitives, such as homomorphic encryption and oblivious transfer. These primitives are significantly slower than symmetric ones. Moreover, some protocols also require several rounds of interaction. As our main contribution, we propose an oblivious finite automata evaluation protocol via conditional disclosure of secrets (CDS), using one (potentially malicious) outsourcing server. This results in a constant-round protocol, and no heavy asymmetric-key primitives are needed. Our protocol is based on a building block called "an oblivious CDS scheme for deterministic finite automata'' which we also propose in this paper. In addition, we propose a standard CDS scheme for deterministic finite automata as an independent interest.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Major revision. ACNS 2022
- DOI
- 10.1007/978-3-031-09234-3_30
- Keywords
- Finite automataConditional disclosure of secretsMulti-client verifiable computationSecure multi-party computation
- Contact author(s)
- kittiphop phalakarn @ gmail com
- History
- 2023-08-03: revised
- 2023-07-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1169
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1169,
author = {Kittiphop Phalakarn and Nuttapong Attrapadung and Kanta Matsuura},
title = {Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for {DFA}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1169},
year = {2023},
doi = {10.1007/978-3-031-09234-3_30},
url = {https://eprint.iacr.org/2023/1169}
}
