Short Group Signatures Without Random Oracles

We propose \em short group signature (GS) schemes which are provablysecure \em without random oracles. Our basic scheme is about 14 timesshorter than the Boyen-Waters GS scheme at Eurocrypt 2006, and 42\%shorter than the recent GS schemes due to Ateniese \em et al. Thesecurity proofs are provided in the Universally Composable model, whichallows the proofs of security valid not only when our scheme is executedin isolation, but also in composition with other secure cryptographicprimitives. We also present several new computational assumptionsand justify them in the generic group model. These assumptions areuseful in the design of high-level protocols and may be ofindependent interest.