ATTRIBUTES IN CRYPTOGRAPHIC CREDENTIALS

• US 20100115281A1
• Filed: 08/27/2009
• Published: 05/06/2010
• Est. Priority Date: 08/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Camenisch, Jan Leonhard, Gross, Thomas R.
• Granted Patent: US 8,281,131 B2
• Time in Patent Office: Days
• US Class Current: 713/175
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

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.

Claims

1. A computer implemented method for generating a cryptographic credential for use in certifying a plurality of user attributes, the method comprising the steps of:

encoding, in said computer, each attribute as a prime number in accordance with a predetermined mapping of attributes to prime numbers;

calculating, in said computer, the product of the prime numbers encoding the attributes; and

generating, in said computer, an encoding of said product, thus producing the cryptographic credential for use in said certification.

2. A method according to claim 1 wherein the step of generating comprises encoding said product as an exponent in a discrete logarithm representation.

3. A method according to claim 1 wherein the step of generating includes producing a cryptographic signature on a message encoding said product.

4. A method according to claim 1 further comprising the step of transmitting the cryptographic credential to a receiving module via a data communications channel.

5. A method according to claim 1 further comprising the step of recording the cryptographic credential on an information storage medium.

6. A computer readable medium tangibly embodying computer executable program instructions for causing a computer to perform a method for generating a cryptographic credential certifying a plurality of user attributes according to claim 1.

7. A computer implemented method for determining, in a verifying module of a data processing system, whether a cryptographic credential associated with a proving module of the system certifies a specified user attribute, said cryptographic credential encoding the product E of a plurality of prime numbers each encoding a respective user attribute in accordance with a predetermined mapping of attributes to prime numbers, the method comprising the steps of:

communicating with the verifying module to demonstrate possession of a cryptographic credential encoding said product E; and

determining whether a prime number e encoding said specified attribute in accordance with said mapping divides the value E encoded in the credential, thus certifying the specified user attribute.

8. A method according to claim 7 for proving that the cryptographic credential does certify the specified attribute, the method including:

demonstrating possession of said credential without revealing said value to the verifying module; and

communicating with the verifying module to prove knowledge of a secret number α

such that α

*e=E.

9. A method according to claim 7 for proving that the cryptographic credential does not certify the specified attribute, the method including:

demonstrating possession of said credential without revealing said value to the verifying module; and

communicating with the verifying module to prove knowledge of secret numbers b and c such that b*E+c*e=1.

10. A method according to claim 7 including the further step of determining, in said computer, whether the product x of respective prime numbers encoding said plurality of attributes in accordance with said mapping divides the value E encoded in the credential.

11. A computer readable medium tangibly embodying computer executable program instructions for causing the computer to perform the steps of a process according to claim 7.

12. A computer implemented method for proving to a verifying module of a data processing system that a cryptographic credential associated with a proving module of the system certifies at least one of a predetermined set of user attributes, said cryptographic credential encoding the product E of a plurality of prime numbers each prime number encoding a respective user attribute in accordance with a predetermined mapping of attributes to prime numbers, the method comprising the steps of:

demonstrating to the verifying module possession of a cryptographic credential encoding E; and

communicating with the verifying module to prove possession of a secret number d which divides both the value E encoded in the credential and a value Q that is the product of respective prime numbers encoding the attributes in said set in accordance with said predetermined mapping of attributes to prime numbers, thus proving said certification.

13. Apparatus for generating a cryptographic credential certifying a plurality of user attributes, the apparatus comprising control logic adapted for:

encoding each attribute as a prime number in accordance with a predetermined mapping of attributes to prime numbers;

calculating the product of the prime numbers encoding the attributes; and

generating a cryptographic credential encoding said product.

14. Apparatus according to claim 13 wherein the control logic includes means adapted for generating the cryptographic credential by encoding said product as an exponent in a discrete logarithm representation.

15. A computer implemented method for determining in a verifying module of a data processing system whether a user attribute encoded in a cryptographic credential associated with a proving module of the system is a member of a predetermined set of user attributes, the cryptographic credential encoding said user attribute as a prime number E in accordance with a predetermined mapping of attributes to prime numbers, the method comprising the steps of:

determining, in said computer, a product value Q which is the product of respective prime numbers corresponding to the attributes in said set in accordance with said predetermined mapping of attributes to prime numbers;

communicating with the verifying module to demonstrate possession of a cryptographic credential encoding a secret value that is said prime number E; and

demonstrating to the verifying module that said secret value divides the product value Q, thus demonstrating that said user attribute is a member of said set.

16. A method according to claim 15 for proving that said user attribute is a member of said predetermined set, the method further including the step of communicating with the verifying module to prove knowledge of a secret number α

such that α

*E=Q.

17. A method according to claim 15 for proving that said user attribute is not a member of said predetermined set, the method including the further step of communicating with the verifying module to prove knowledge of secret numbers b and c such that b*E+c*Q=1.

18. A method according to claim 15 for proving that a plurality of user attributes, encoded in the cryptographic credential as respective prime numbers in accordance with said predetermined mapping, are each members of said set, the method including:

communicating with the verifying module to demonstrate possession of a cryptographic credential encoding respective secret values that are said prime numbers encoding the plurality of user attributes;

calculating an attribute product X that is the product of the prime numbers encoding said plurality of user attributes; and

communicating with the verifying module to prove knowledge of a secret number α

such that α

*X=Q.

19. A computer readable medium tangibly embodying computer executable program instructions for causing the computer to perform the steps of a process according to claim 15.

20. A computer implemented method for verifying at a verifying module of a data processing system whether a user attribute encoded in a cryptographic credential associated with a proving module of the system is a member of a predetermined set of user attributes, the cryptographic credential encoding said user attribute as a prime number E in accordance with a predetermined mapping of attributes to prime numbers, the method comprising the steps of:

communicating with the proving module to verify possession by the proving module of a cryptographic credential encoding a secret value E; and

communicating with the proving module to determine whether said secret value divides a product value Q that is the product of respective prime numbers corresponding to the attributes in said set in accordance with said predetermined mapping of attributes to prime numbers.

21. A method according to claim 20 for verifying that said user attribute is a member of said predetermined set, the method including communicating with the proving module to verify knowledge by the proving module of a secret number α

such that α

*E=Q.

22. A proving module of a data processing system for proving to a verifying module of the system whether a user attribute encoded in a cryptographic credential associated with the proving module is a member of a predetermined set of user attributes, the cryptographic credential encoding said user attribute as a prime number E in accordance with a predetermined mapping of attributes to prime numbers, the proving module comprising (i) a communications interface for communicating with the verifying module and (ii) control logic adapted to:

determine a product value Q that is the product of respective prime numbers corresponding to the attributes in said set in accordance with said predetermined mapping of attributes to prime numbers;

communicate with the verifying module via said communications interface to demonstrate possession of a cryptographic credential encoding a secret value that is said prime number E; and

communicate with the verifying module via said communications interface to prove whether said secret value divides the product value Q.

23. A proving module according to claim 22 wherein:

the control logic is adapted to communicate with the verifying module to prove knowledge of a secret number α

such that α

*E=Q.

24. A proving module according to claim 22 for proving that a plurality of user attributes, encoded in the cryptographic credential as respective prime numbers in accordance with said predetermined mapping, are each members of said set, the control logic being further adapted to:

communicate with the verifying module to demonstrate possession of a cryptographic credential encoding respective secret values that are said prime numbers encoding the plurality of user attributes;

calculate an attribute product X that is the product of the prime numbers encoding said plurality of user attributes; and

communicate with the verifying module to prove knowledge of a secret number α

such that α

*X=Q.