Research On Fairness In Rational Secure Two-Party Computation

Secure multi-party computation (SMPC) is one of important research fields in mod-ern cryptography and is a building block for many cryptographic protocols. It is not only one part of basic cryptographic research studying the basic principle and method of securely computing in distributed situations, but also is an important basis for some practical cryptographic protocols, such as, contract signing, electronic voting, electronic auction and electronic signature. SMPC can be described as follows:some independent parties who have respective private inputs, hoping to compute a conventional function-ality using these inputs. Their basic target is to correctly get the outputs of the function while do not reveal their respective private inputs. Assume that a third trusted party (TTP) exists in the ideal model and there is a secure communication channel between each party and TTP. Each party sends his input to TTP through the secure channel. Then TTP com-putes the conventional function using the inputs and finally sends the outputs to parties. Consequently, the computation is completed and the basic target can be achieved in the presence of TTP. The above model is called ideal model in SMPC.The aim of SMPC for cryptographic protocols in the real world is to realize the basic target as the ideal model. Furthermore, the basic target can be described as the following properties:privacy, correctness, independence and fairness. Fairness means that corrupt-ed parties should receive their output if and only if honest parties do. Cleve (STOC1986) proved that fairness is impossible in the presence of honest minority for SMPC. Thus SMPC, especially STPC, protocols often ignore the achievement of fairness. However, fairness is an important property in SMPC and STPC, especially in electronic voting and auction. Previous research works presented many SMPC protocols to realize fairness. For example, some protocols realized non-cooperation computation (NCC) functions, some achieved fairness through physical envelopes and ballot. Additionally, some other weak notions about fairness is put forward like partial fairness.Recently, rational secure multi-party computation (RSMPC) is considered as a new method to realize fairness. RSMPC mean SMPC in the presence of rational parties. The most difference between RSMPC and SMPC lies in that rational parties decide whether to follow the protocol according to their utilities. While honest parties, semi-honest par-ties and malicious adversaries in SMPC have no utilities. Rational parties are similar to covert adversaries mentioned in Aumann and Lindell (JOC2010) since both of them have incentives to deviate from protocols. The idea of RSMPC derives from game theory, so the security proof adopts the same idea from game theory. More specifically, the first step is to assign utilities for each. Note that, here utilities are not assigned arbitrarily, but designed according to some classical games. For example, most utilities derive from prisoner’s dilemma (PD) game. The second step is to designing protocols such that they satisfy the above four properties. Finally, prove that the strategy of following protocols is an equilibrium and no one has incentives to deviate from protocols. In other words, every party can maximize their utilities by following protocols, otherwise, they may obtain an inferior utility. Toward a game theory view, the main task of RSMPC is to design proper protocols such that each party cooperates with others instead of defecting from others. If cooperation is a dominating strategy for each party, then fairness can be achieved trivially.In this paper, we mainly discuss the achievement of fairness in Rational STPC. That is how to boost cooperation among parties.1. To solve these problems, we introduce tit-for-tat (TFT) strategy in this paper, which is often used in iterated PD games to boost cooperation. Rational parties will at least cooperate in the first several rounds, then they can reconstruct the output by enough shares. Reputation is considered as a frighten factor in utility definition when introducing TFT strategy.2. Another work is to define new utility by adding reputation as a new part. New rational parties are redefined according to the new utility. We also prove that given proper parameters, mutual cooperation is Nash equilibrium. Therefore, the new rational secure two-party computation (RSTPC) protocol only has one round and efficiency is greatly improved.3. The last work in this paper is to present a more complex but practical RSTPC pro-tocol, where parties have private types under incomplete information. Here, the utility is defines on the basis of another famous game-store chain game. Further-more, under incomplete information, we achieve fairness by stronger sequential equilibrium instead of Nash equilibrium.The above three problems study how to efficiently achieve fairness between two par-ties. Given different strategies and utility definitions, fairness can be achieved in rational two-party computation protocols. This conclusion is different with previous works about STPC, where fairness is impossible. The difference derives from the intuition of utility, which makes some impossibility become possible.As a new field, there are still some open problems in RSMPC. For example, how to design proper strategies such that parties cooperate with each other; how to design more practical utility functions; if there exist some other utility definitions according to new games other than PD game; are there any other properties other than utility etc.