Method and apparatus for generating cryptographic credentials certifying user attributes and making cryptographic proofs about attributes encoded in such credentials. Attributes are encoded as prime numbers E in accordance with a predetermined mapping and a cryptographic credential is generated encoding E. To prove that an attribute encoded in a cryptographic credential associated with a proving module of the system is a member of a predetermined set of user attributes, without revealing the attribute in question, the proving module determines the product Q of respective prime numbers corresponding to the attributes in the set in accordance with the predetermined mapping of attributes to prime numbers. The proving module demonstrates to the receiving module possession of a cryptographic credential encoding a secret value that is the prime number E, and then whether this secret value divides the product value Q.