Research Of Path-Inclusion Secure Computation And Multiset Operations Problems

As of today, secure multiparty computation has been a hot area of research for decades in cryptology. It enables a set of untrusting parties to compute any function of their private inputs while revealing nothing but the result of the function. Secure multiparty computation has extended to many areas, has also been extensively studied. Nevertheless, as new research directions in secure multiparty computation, secure multiparty computation graph theory, there are still many issues unresolved, and the path-inclusion problem is one of them. The path-inclusion problem is a secure two-party computation problem where Alice holds a path and Bob has another one, and they want to know whether his/her path is included by the other path.This paper first introduces some basic knowledge of secure multiparty computation, including the attacker model, the definition of security. Take the privacy-preserving set operations, secure pattern matching and privacy-preserving computational geometry for examples, we discuss the research status and existing research results in secure multiparty computation field. And we briefly describe some cryptography tools which are often used to construct secure multiparty computation protocols, such as:the homomorphic cryptosystem, oblivious transfer protocol, secret commitment scheme and zero-knowledge proof.Then we focus on path-inclusion secure two-party computation problem. With regards to the problem, the paper presents two efficient protocols for securely computing the path-inclusion problem. In the first protocol the paths are coded to establish a correspondence between paths and sets. Then both parties are engaged in computing the set-inclusion problem. They can learn whether one path includes the other one from the output of set-inclusion subprotocol. The other of our constructions 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.Furthermore, we also consider several multiset operations in secure two-party setting:Alice and Bob hold two multisets of elements those belong to a universe. They want to perform private computations over the two multisets and no one would learn more information than what can be deduced from the result. We consider one ways to deal with multiple sets and multiple sets of related operations:characteristic bitstrings. And then we propose some privacy-preserving multiset operations protocols in the semi-honest model to solve the multisets operation problems, including inclusion-relation, over-threshold multiset-union, threshold multiset-union, multiset-intersection and cardinality multiset-intersection. In addition, we consider their extension to the malicious setting.