12-04-2014, 11:46 AM
Cryptanalysis of a Generalized Ring Signature Scheme
Generalized Ring Signature .pdf (Size: 79.39 KB / Downloads: 15)
Abstract
The concept of ring signature was first introduced by Rivest et al. in
2001. In a ring signature, instead of revealing the actual identity of the message
signer, it specifies a set of possible signers. The verifier can be convinced that
the signature was indeed generated by one of the ring members; however, the
verifier is unable to tell which member actually produced the signature. A
convertible ring signature scheme allows the real signer to convert a ring signature
into an ordinary signature by revealing secret information about the ring signature.
Thus, the real signer can prove the ownership of a ring signature if necessary, and
the the other members in the ring cannot prove the ownership of a ring signature.
Based on the original ElGamal signature scheme, a generalized ring signature
scheme was proposed for the first time in 2008. The proposed ring signature can
achieve unconditional signer ambiguity and is secure against adaptive chosen-
message attack in the random oracle model. By comparing to ring signatures
based on RSA algorithm, the authors claimed that the proposed generalized ring
signature scheme is convertible. It enables the actual message signer to prove to
a verifier that only she is capable of generating the ring signature. Through
cryptanalysis, we show that the convertibility of the generalized ring signature
scheme cannot be satisfied. Everyone in the ring signature has the ability to claim
that she generates the generalized ring signature
INTRODUCTION
THE concept of ring signature was first introduced by Rivest et al.
in 2001 [1] to provide anonymity for the message signer. After
that, many ring signature schemes and their extensions have been
proposed [2], [3], [4], [5], [6], [7]. Ring signature is a group-
oriented signature with privacy concerns: any user can anon-
ymously sign a message on behalf of a group of spontaneously
conscripted users including the actual signer. Any verifier can be
convinced that the message has been signed by one of the
members in this group, but the actual signer remains unknown.
Sometimes, an actual signer may possibly want to expose herself
if, in doing so, he will acquire an enormous benefit. Then, a
convertible ring signature scheme was proposed [8]. A con-
vertible ring signature scheme allows the real signer to convert a
ring signature into an ordinary signature by revealing secret
information about the ring signature. Thus, the real signer can
prove the ownership of a ring signature if necessary. Because of
broad applications, many ring signature schemes with the similar
properties are also proposed [9], [10]
CRYPTANALYSIS OF THE GENERALIZED RING
SIGNATURE SCHEME
In this section, we propose an attack on Ren-Harn’s generalized
ring signature scheme. We show that anyone can impersonate the
real signer to convert a ring signature into an ordinary signature by
revealing secret information about the ring signature successfully.
This means that the scheme is totally broken.
Proposed that the received ring signature ðS; i0 ; vi0 ; m1 ;
m2 ; . . . ; mn ; 1 ; 1 ; . . . ; n ; n Þ of a message m for a ring of
n individuals A1 ; A2 ; Á Á Á ; An can pass the verification process,
where the signer Alice is As , 1 s n. Each Ai 2 S is called a ring
member. The public key of Ai is Pi and the corresponding private
key is Si . S will also be used to denote the set of public keys of all
ring members. Consider the scenario in which the the verifier
captures their quarry, due to real signer’s information, and would
like to give the leaker a big reward. Naturally, everyone in the
ring is eager to claim to be the signer of the ring signature. In this
situation, the convertible ring signature scheme can be used. For
the Ren-Harn’s generalized ring signature scheme, we show that
any member in the signers set has the ability to convert a ring
signature into an ordinary signature by revealing secret informa-
tion about the ring signature.
CONCLUSION
Generalized ring signature scheme is a new and very useful
cryptographic primitive. In this paper, we propose an attack on
Ren-Harn’s generalized ring signature scheme based on ElGamal
signature. We show that anyone can impersonate a real signer to
perform the convertibility successfully. The original generalized
ring signature scheme cannot satisfy the convertibility. This means
that the scheme is broken.