Efficient Threshold Signer-Ambiguous Signatures from Variety of Keys

Masayuki ABE  Miyako OHKUBO  Koutarou SUZUKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.2   pp.471-479
Publication Date: 2004/02/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
signer ambiguity,  ring signature,  threshold signature,  group signature,  

Full Text: PDF(218.4KB)>>
Buy this Article

This paper presents an efficient and generic solution in the following scenario: There are n independent people using variety of signature schemes such as DSS, RSA, Schnorr, and so on, and a subset of them attempts to sign a document without being identified which subset they are. This is a generalized scenario of the Ring Signatures by Rivest, Shamir and Tauman, whose original scenario limits the subset to be a single person and the base signature scheme to be RSA/Rabin schemes. Our scheme allows any signature schemes based on sigma-protocols and claw-free permutations. It also offers shorter signatures and less computation compared to known generic construction. The security is argued in the random oracle model as well as previous schemes and shows that our scheme achieves reduction cost linear in the number of hash queries while it is square for previous generic constructions.