Anonymity from Public Key Encryption to Undeniable Signatures

Anonymity or “key privacy” was introduced in [1] as a new security notion a cryptosystem must fulfill, in some settings, in addition to the traditional indistinguishability property. It requires an adversary not be able to distinguish pairs of ciphertexts based on the keys under which they are created. Anonymity for undeniable signatures is defined along the same lines, and is considered a relevant requirement for such signatures.

Our results in this paper are twofold. First, we show that anonymity and indistinguishability are not as orthogonal to each other (i.e., independent) as previously believed. In fact, they are equivalent under certain circumstances. Consequently, we confirm the results of [1] on the anonymity of ElGamal’s and of Cramer-Shoup’s schemes, based on existing work about their indistinguishability. Next, we constructively use anonymous encryption together with secure digital signature schemes to build anonymous convertible undeniable signatures. In this context, we revisit a well known undeniable signature scheme, whose security remained an open problem for over than a decade, and prove that it is not anonymous. Moreover, we repair this scheme so that it provides the anonymity feature and analyze its security in our proposed framework. Finally, we analyze an efficient undeniable signature scheme, which was proposed recently, in our framework; we confirm its security results and show that it also enjoys the selective conversion feature.