Privacy-preserving path-inclusion protocol through oblivious automata

This paper focuses on path-inclusion secure two-party computation problem, and an efficient protocol for securely computing the path-inclusion problem is proposed. This problem is defined in the two parties setting, where Alice and Bob both have a path. The goal of Bob is to learn whether his path is included by the path Alice holds, without revealing it to Alice or learning anything else about Alice´s path. Our construction is based on an automata evaluation sub-protocol. In our protocol, each path is coded into a string which reserves all information about the original path. Then both parties are involved in the automata evaluation sub-protocol. Finally one of them can learn whether one path includes the other one.