Signature Schemes and Anonymous Credentials from Bilinear Maps

We propose a new signatures scheme that is provably secure without assuming random oracles. Our scheme is the first efficient signature scheme whose security relies on an assumption related to the discrete logarithm assumption. More precisely, our scheme is based on an assumption put forth by Lysyanskaya, Rivest, Sahai, and Wolf, who also show that it holds for generic groups. Furthermore, we show how our scheme can be used to construct efficient group signature and identity escrow schemes as well as anonymous credential systems. To this end, we provide efficient protocols that allow one to prove in zero-knowledge the possession of a signature on a committed message and to obtain a signature on a committed message.