Short Undeniable Signatures Based on Group Homomorphisms

This paper is devoted to the design and analysis of short undeniable signatures based on a random oracle. Exploiting their online property, we can achieve signatures with a fully scalable size depending on the security level. To this end, we develop a general framework based on the interpolation of group homomorphisms, leading to the design of a generic undeniable signature scheme called MOVA with batch verification and featuring non-transferability. By selecting group homomorphisms with a small group range, we obtain very short signatures. We also minimize the number of moves of the verification protocols by proposing some variants with only 2 moves in the random oracle model. We provide a formal security analysis of MOVA and assess the security in terms of the signature length. Under reasonable assumptions and with some carefully selected parameters, the MOVA scheme makes it possible to consider signatures of about 50 bits.

Short 2-Move Undeniable Signatures

Jean Monnerat, Serge Vaudenay

Attempting to reach a minimal number of moves in cryptographic protocols is a quite classical issue. Besides the theoretical interests, minimizing the number of moves can clearly facilitate practical implementations in environments with communication constraints. In this paper, we offer a solution to this problem in the context of undeniable signatures with interactive verification protocols by proposing a way to achieve these protocols in 2 moves. To this goal, we review a scheme we proposed at Asiacrypt 2004 whose property is the full scalability of the signature length against security. We slightly modify (to make it non-transferable) a 2-move version of this scheme which was mentioned in the original article without a proof of security. In the random oracle model, we prove the security of the modified version against an active adversary and precisely assess the security in terms of the signature length. To the best of our knowledge, this scheme is the first 2-move undeniable signature scheme with a security proof.

2006

Short undeniable signatures

Jean Monnerat

Digital signatures are one of the main achievements of public-key cryptography and constitute a fundamental tool to ensure data authentication. Although their universal verifiability has the advantage to facilitate their verification by the recipient, this property may have undesirable consequences when dealing with sensitive and private information. Motivated by such considerations, undeniable signatures, whose verification requires the cooperation of the signer in an interactive way, were invented. This thesis is mainly devoted to the design and analysis of short undeniable signatures. Exploiting their online property, we can achieve signatures with a fully scalable size depending on the security requirements. To this end, we develop a general framework based on the interpolation of group elements by a group homomorphism, leading to the design of a generic undeniable signature scheme. On the one hand, this paradigm allows to consider some previous undeniable signature schemes in a unified setting. On the other hand, by selecting group homomorphisms with a small group range, we obtain very short signatures. After providing theoretical results related to the interpolation of group homomorphisms, we develop some interactive proofs in which the prover convinces a verifier of the interpolation (resp. non-interpolation) of some given points by a group homomorphism which he keeps secret. Based on these protocols, we devise our new undeniable signature scheme and prove its security in a formal way. We theoretically analyze the special class of group characters on Z*n. After studying algorithmic aspects of the homomorphism evaluation, we compare the efficiency of different homomorphisms and show that the Legendre symbol leads to the fastest signature generation. We investigate potential applications based on the specific properties of our signature scheme. Finally, in a topic closely related to undeniable signatures, we revisit the designated confirmer signature of Chaum and formally prove the security of a generalized version.

EPFL2006

Short undeniable signatures

Jean Monnerat

EPFL2006