Ring Signatures of Constant Size Without Random Oracles

摘要

Ring signatures allow a signer to anonymously sign on behalf of a group of users, the so-called ring; the only condition is that the signer is a member of the ring. At PKC 2007, Shacham and Waters left an open problem, "obtain a ring signature secure without random oracles and its signature size is independent of the number of signers implicated in the ring", which has not been solved yet. In this paper, by using a powerful tool, indistinguishability obfuscator (iO), we construct a constant size ring signature scheme without random oracles and thus answer Shacham et al.'s open problem. Furthermore, we construct an identity-based ring signature scheme which also has constant signature size in the standard model. However, we stress that due to the low efficiency of the existing iO candidates, we mainly focus on the existence of the constant size ring signature schemes without random oracles, but do not care about their practicability. A shortcoming of our approach is that the ring unforge-ability merely is selective but not adaptive.