Anonymous credentials: Secret-free and quantum-safe

An anonymous credential mechanism is a set of protocols that allows users to obtain credentials from an organization and demonstrate ownership of these credentials without compromising users' privacy. In this work, we construct the first secret-free and quantum-safe credential mechanism. The scheme is secret-free in the sense that an organization does not need to guard a secret key. The scheme is also lightweight in construction. Security of the scheme relies on the ability of the organization to maintain the integrity of a publicly known data structure-namely, a Merkle tree-that utilizes a quantum-safe, partially homomorphic hash function as a foundational primitive. We also construct a simple, quantum-safe, zero-knowledge argument of knowledge of membership in the Merkle tree. Additionally, we explore a concrete instantiation of the scheme and show it to be practically efficient for the core functions of enrollment and verification.