Paper 2006/123

Designated Confirmer Signatures Revisited

Douglas Wikström

Abstract

Previous definitions of designated confirmer signatures in the literature are incomplete, and the proposed security definitions fail to capture key security properties, such as unforgeability against malicious confirmers and non-transferability. We propose new definitions. Previous schemes rely on the random oracle model or set-up assumptions, or are secure with respect to relaxed security definitions. We construct a practical scheme that is provably secure with respect to our security definition under the strong RSA-assumption, the decision composite residuosity assumption, and the decision Diffie-Hellman assumption. To achieve our results we introduce several new relaxations of standard notions. We expect these techniques to be useful in the construction and analysis of other efficient cryptographic schemes.

Note: Unfortunately, Protocol 5.5 is flawed. It does not guarantee that h is in the subgroup generated by g. Specifically, Proposition 5.10 is wrong. The problem is that if N is chosen maliciously, then Z_N^* may contain small subgroups and h could be of the form g*a, where a is a generator of a small subgroup. The verifier accepts such an input with probability roughly 1/t, where t is the order of a. The flaw in the proof appears on Page 29, lines 22-23: "...we must have c=c' or (c-c') does not divide (d-d')." The analysis does not deal with the situation where c-c' divides d-d' (as integers) and the order of a (where h=g*a) divides c-c'. The main protocol remains secure provided that Protocol 5.5 is not used to establish a set of mutually trusted commitment parameters. Thus, they must be provided as part of set-up assumption or by doing costly cut-and-choose proofs. In other words, the flaw reduces the practicality of the scheme, but it does not nullify the main results, which is why the paper is not withdrawn. Feel free to contact the author if the above is not clear.