FEAC: A New Construction of Fast and Expressive Anonymous Credential for Cloud Service

Abstract

Anonymous credentials are an essential cryptography primitive to protect user privacy and provide fine-grained access control for proving ownership and rights of specific credentials. There are currently two roadmaps to designing anonymous credentials: one is signature credentials, which are constructed by signature with efficient protocols and non-interactive zero-knowledge proofs, and the other is functional credentials, which are transformed from predicate encryption schemes. However, none of the existing instances of anonymous credentials support$expressive$access policies expressed as conjunction, disjunction, or arbitrary Boolean formulas, which are particularly useful for cloud services. In this paper, we propose a new fast and expressive anonymous credential, called FEAC. It is constructed with the unique$dual$$randomness$$splitting$technique, which combines the most efficient anonymous key-policy attribute-based encryption (USENIX 24) and short randomizable signature (CT-RSA 18) to balance efficiency, expressiveness, and security, demonstrating a new way to instantiate anonymous credentials. Furthermore, our credential presentation protocol offloads most of the time-consuming computation to the cloud server (11 pairing) to reduce the computational burden on the user side (2 pairing). We propose formal definitions and formal security proofs of FEAC. We provide implementations and evaluate the performance of FEAC, comparing it to state-of-the-art work.