Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA
Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA
复制标题
DOI：
10.1007/978-3-031-09234-3_30
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kittiphop Phalakarn;Nuttapong Attrapadung;Kanta Matsuura
中科院分区：
文献类型：
--
作者：
Kittiphop Phalakarn;Nuttapong Attrapadung;Kanta Matsuura
在不经意有限自动机求值中，一方持有私有自动机，另一方持有私有字符串。目标是让各方知道字符串是否被自动机接受，同时保持他们的输入秘密。应用程序包括DNA搜索，模式匹配等。以往的研究大多是基于非对称密码原语，如同态加密和不经意传输。这些原语比对称原语慢得多。此外，一些协议还需要几轮交互。作为我们的主要贡献，我们使用一个（可能是恶意的）外包服务器，通过条件秘密披露（CDS）提出了一个不经意的有限自动机评估协议。这导致了一个恒定回合的协议，并且不需要沉重的非对称密钥原语。我们的协议是基于一个积木称为“一个不经意的CDS计划确定性有限自动机”，我们也提出了在本文中。此外，我们提出了一个标准的CDS计划的确定性有限自动机作为一个独立的利益。
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.