Improving efficiency and security of Camenisch–Lysyanskaya signatures for anonymous credential systems

Camenisch–Lysyanskaya signature scheme with randomizability, namely CL signatures, at CRYPTO'04 has been well adopted for many privacy-preserving constructions, especially in the context of anonymous credential systems. Unfortunately, CL signatures suffer from linear size drawbacks. The signature size grows linearly based on the signing messages, which decreases the interest in practice, as each user may have multiple attributes (messages). Its standard EUF-CMA security was first proven under an interactive assumption. While the interactive assumption is not desirable in cryptography, Fuchsbauer et al. revisited its security at CRYPTO'18 by proving the scheme under the discrete logarithm (Dlog) assumption in the algebraic group model (AGM) that idealizes the adversary's computation to be algebraic, yet the reduction loss is non-tight. In this work, we propose a new variant of CL signatures, namely CL+ signatures, that improves efficiency and security. The proposed CL+ signatures possess randomizability without the linear size drawback, such that signature size is a constant of three group elements. Besides, we prove the security of CL+ signatures can be tightly reduced to the DLog problem in AGM with only a loss factor of 3. Lastly, we show how CL+ signatures can also be instantiated to anonymous credential systems.