A Note on the Invisibility and Anonymity of Undeniable Signature Schemes

Undeniable signature is a special featured digital signature which can only be verified with the help of the signer. Undeniable signature should satisfy invisibility which implies the inability of a user to determine the validity of a message and signature pair as introduced by Chaum et al. Galbraith and Mao later proposed the notion of anonymity which implies the infeasibility to determine which user has issued the signature. They also proved that the notions of invisibility and anonymity are equivalent when the signers possess the same signature space, such that if an undeniable signature possesses invisibility, then it also possesses anonymity, and vice versa. In this paper, we show that in contradiction to the equivalency result established by Galbraith and Mao, there exist some undeniable signature schemes that possess invisibility but not anonymity. This motivates us to find out whether there is a limitation on Galbraith and Mao’s equivalency result or the schemes are actually flawed. Our analysis shows that the anonymity property requires all signers to possess the same signature space but the invisibility property does not. This conforms to the equivalency result and implies that an undeniable signature scheme can be invisible but not anonymous if the signers possess the different signature spaces. Our result invalidates two past cryptanalysis on undeniable signature schemes.