Generic construction of fair exchange scheme with semi-trusted adjudicator

A fair exchange of digital signatures has been considered as a fundamental problem in cryptography. The most widely adopted approach to ensure the fairness of exchanging signatures is to resort to a trusted third party (TTP) whenever required. The TTP is assumed to be entirely honest and neutral, hence never colludes with the other parties in the system. In practice, such a TTP may not be available. To overcome this difficulty, Shao introduced a new idea of building fair exchange schemes with a semi-trusted adjudicator that only needs to be trusted by one party (the signer). These new fair exchange schemes are more practical than previous ones since there is no necessity for two mutually distrusted parties to commonly trust the same adjudicator. In the new approach, an adjudicator is also trusted unilaterally. Nevertheless, the two schemes that Shao proposed in 2008 and 2010, respectively, are both only provably secure in the random oracle model. In this paper, we revisited the schemes proposed by Shao and revealed that some subtle issues might have been overlooked. In particular, the number of interactions between the signer and the adjudicator is more involved than it is anticipated. Our investigation leads to a refined definition of this kind of fair exchange scheme with a semi-trusted adjudicator (FESTA). We proposed a generic construction in our model based on pseudo-random functions, collision-resistant hash functions and any digital signature schemes that are existentially unforgeable against adaptive chosen message attacks. Based on our generic construction, FESTA in the standard model can be realized. We provide such instantiations to demonstrate the practicability of our generic construction.