Paper 2023/1169

Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA

Kittiphop Phalakarn, The University of Tokyo, Tokyo, Japan
Nuttapong Attrapadung, National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
Kanta Matsuura, The University of Tokyo, Tokyo, Japan

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.

Available format(s)
Publication info
Published elsewhere. Major revision. ACNS 2022
Finite automataConditional disclosure of secretsMulti-client verifiable computationSecure multi-party computation
Contact author(s)
kittiphop phalakarn @ gmail com
2023-08-03: revised
2023-07-29: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.