Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA

Kittiphop Phalakarn; Nuttapong Attrapadung; Kanta Matsuura

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

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 automata Conditional disclosure of secrets Multi-client verifiable computation Secure 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}
}