**A Transitive Signature Scheme Provably Secure Against Adaptive Chosen-message Attack**

*Huafei Zhu and Bao Feng and Robert H. Deng*

**Abstract: **All node certificate based transitive signature schemes available in the literature make use of any digital
signature scheme which is assumed to be provably secure against adaptive chosen-message attack, as a building
block to produce node certificates in a graph. Consequently the algebraic structures to represent nodes in the
graph are independent of the algebraic structure of signature scheme employed. This inconsistence of
representation structures of the signature scheme, nodes and edges in the graph could increase the cost to manage
those public data. For example, the transitive signature schemes presented by Micali and Rivest \cite{MR} and
Bellare and Neven (the node certificate based version FBTS-1, in \cite{BN}), both heavily rely on the standard
provably secure signature scheme (say Goldwasser-Micali-Rivest's signature scheme \cite{GMR}). Consequently, a
core problem related to transitive signature schemes is {\it how to construct transitive signature schemes so that
the representation structures of signature schemes, nodes and edges in a graph can be implemented compactly?}

\vskip 2mm

Bellare and Neven's hash-based modification, FBTS-2, achieving shorter signatures by eliminating the need for node certificates and provable under the same factoring assumption in the random oracle model, is actually the first solution to the above question. Our approach to attack the problem mentioned above, is different from Bellare and Neven's. We attack the problem by first carefully defining algebraic structure to represent vertices and edges in an undirected graph, then we construct a signature scheme so that its algebraic structure is coincident with that of vertices and edges in the graph. Finally, we present a practical realization of a transitive signature scheme that is proven transitively unforgeable under adaptive chosen message attack in the standard intractability paradigm. To the best knowledge of authors, this approach has NOT been reported in the literature.

**Category / Keywords: **public-key cryptography /

**Publication Info: **new report

**Date: **received 3 Apr 2003, withdrawn 11 Aug 2003

**Contact author: **huafei at i2r a-star edu sg

**Available format(s): **(-- withdrawn --)

**Version: **20030811:154029 (All versions of this report)

**Short URL: **ia.cr/2003/059

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]