You are looking at a specific version 20030811:154029 of this paper. See the latest version.

Paper 2003/059

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.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Published elsewhere. new report
Contact author(s)
huafei @ i2r a-star edu sg
History
2003-08-11: withdrawn
2003-04-03: received
See all versions
Short URL
https://ia.cr/2003/059
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.