Oblivious DFA evaluation on joint input and its applications

Abstract Oblivious deterministic finite automata (DFA) evaluation is a powerful two-party primitive that has been widely used in cryptographic protocols. It enables two mutually distrusted participants to obliviously evaluate a DFA (provided by one party) on an input string (provided by the other party), while preserving the privacy of each party from the other one. However, this primitive is not flexible and powerful enough, in the sense that it only supports evaluation on input string that is provided by one participant. In this paper, we propose oblivious DFA evaluation on joint input (denoted as F ODFA JI ), a variant that extends the functionality of traditional oblivious DFA evaluation protocols. The new primitive enables two participants to collaboratively evaluate a DFA on a joint input, where the input is a combination of two input strings provided by both of the participants. To enable modularized instantiation, we first propose and instantiate F OT JC – oblivious transfer with joint choice – a functionality as modified oblivious transfer (OT), and then provide an efficient instantiation for F ODFA JI in F OT JC -hybrid model. Security proof demonstrates that the proposed protocol is secure under semi-honest model, and theoretical performance analysis shows that it achieves satisfactory efficiency and scalability. F ODFA JI is a basic as well as an important building block for high-level secure outsourced computing tasks. In this paper, we use secure outsourced pattern matching as a case study and show how it can be applied to construct such high-level protocols.