Private Verification in Multi-stakeholder Environment and its Application to Stable Matching

This paper provides a solution to mitigate mistrust that arises from untransparency in a multi-stakeholder environment. This work is related to a kind of verifiable computation. When considering the multi-stakeholder environment, not only the participants’ requirements but also the assignee’s intention should be respected. That is, the assignee should be given the discretion to select a result that is the best for the assignee among all the choices. However, there is a possibility that if the assignee is malicious, he/she may falsify and provide an inadequate result for participants to maximize his/her benefit by ignoring the participants’ requirements. It is difficult for the participants to detect this if they want to keep their preference orders secret from others. This paper proposes a solution to determine whether the received result is adequate for the participants while keeping their preference orders secret. The proposed solution is based on fully homomorphic encryption (FHE) and assumes the use of a semi-honest third-party server. This paper first describes a general solution that is not limited to specific requirements from participants. Next, this paper shows a way to apply to stable matching problem as a specific implementation. More specifically, a transformation of a standard stability checking algorithm into an algorithm that can be implemented by FHE with the computational complexity \(O(n^2)\) $O(n^2)$ . Finally, this paper gives an example of an implementation and its performance with HElib, which is an FHE library that provides BGV.