Paper 2006/226

The Fairness of Perfect Concurrent Signatures

Guilin Wang, Feng Bao, and Jianying Zhou

Abstract

At Eurocrypt 2004, Chen, Kudla and Paterson introduced the concept of {\it concurrent signatures}, which allows two parties to produce two ambiguous signatures until an extra piece of information (called {\it keystone}) is released by the initial signer. Once the keystone is released publicly, both signatures are binding to their true signers {\it concurrently}. At ICICS 2004, Susilo, Mu and Zhang further proposed {\it perfect concurrent signatures} to strengthen the ambiguity of concurrent signatures. That is, even the both signers are known having issued one of the two ambiguous signatures, any third party is still unable to deduce who signed which signature, different from Chen et al.'s scheme. However, this paper points out that Susilo et al.'s two perfect concurrent signatures are actually {\it not} concurrent signatures. Specifically, we identify an attack that enables the initial signer to release a carefully prepared keystone that binds the matching signer's signature, but not the initial signer's. Therefore, both of their two schemes are {\it unfair} for the matching signer. Moreover, we present a simple but effective way to avoid this attack such that the improved schemes are truly perfect concurrent signatures.