Apparatus and method for proving the denial of a direct proof signature

• US 7,490,070 B2
• Filed: 06/10/2004
• Issued: 02/10/2009
• Est. Priority Date: 06/10/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernest F.
• Primary Examiner(s): Elisca; Pierre E
• Application Number:
  US10/866,252
• Publication Number:
  US 20060010079A1
• Time in Patent Office: 1,706 Days
• Field of Search: 705/75, 705/50, 705/51, 713/176
• US Class Current: 705/75
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853

Abstract

In some embodiments, a method and apparatus for proving the denial of a direct proof signature are described. In one embodiment, a trusted hardware device convinces a verifier that the trusted hardware device possesses cryptographic information without revealing unique, device identification information of the trusted hardware device or the cryptographic information. Once the verifier is convinced that the hardware device possesses the cryptographic information, the verifier may issue a denial of signature request to the trusted hardware device, including at least one compromised direct proof signature. In response, the trusted hardware device issues a denial of the compromised direct proof signature by proving to the verifier that a cryptographic key held by the trusted hardware device was not used to form the at least one compromised direct proof signature. Other embodiments are described and claims.

Claims

1. A method comprising:

convincing a verifier that an anonymous hardware device possesses cryptographic information without disclosure of the cryptographic information to the verifier;

receiving a denial of signature request, including a base value B₀ and a pseudonym value K₀ of a suspect signature from the verifier;

convincing the verifier that a cryptographic key, F, stored within the anonymous hardware device and used to construct a pseudonym, K, does not match an unknown, suspect key F₀ used to form the suspect signature, to prove to the verifier that the cryptographic key, F, stored within the anonymous hardware device is uncompromised without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier.

2. The method of claim 1, wherein convincing the verifier that the hardware device possesses the cryptographic information comprises:

performing a direct proof by the hardware device to prove that the cryptographic key is stored within the hardware device, the direct proof comprising a plurality of exponentiations, at least one being conducted using the cryptographic key of the hardware device as an exponent without exposing the cryptographic key.

3. The method of claim 1, wherein convincing a verifier that a hardware device possesses cryptographic information comprises:

using the cryptographic information to compute a pseudonym, K; and

providing the pseudonym, K, to the verifier.

4. The method of claim 1, wherein convincing the verifier that the cryptographic key is uncompromised comprises:

selecting a random exponent value R;

transmitting one or more computed values to the verifier according to a suspect-base value B₀ and a suspect pseudonym value K₀ received from the verifier, a modulus value P of the hardware device and a random exponent value R selected by the hardware device in response to;

performing a proof by the hardware device to deny that a cryptographic key F stored within the hardware device was used to create a suspect direct proof signature, the proof comprising a plurality of exponentiations, each being conducted using one of the cryptographic key, F, the random exponent value R and other random exponent values as an exponent without exposing the cryptographic key, F, the random exponent value R and the other random exponent values.

5. The method of claim 4, wherein performing the proof comprises:

convincing the verifier that the value R exists such that;

S=B₀^R mod P and T=K₀^R mod P,

without revealing any useful information about R; and

convincing the verifier that a value F exists such that;

U=S^F mod P and K=B^F mod P,

without revealing any useful information about F.

6. The method of claim 4, wherein the verifier is convinced that the cryptographic key F stored within the hardware device was not used to create the suspect direct proof signature if U≈

T mod P.

7. The method of claim 1, wherein convincing the verifier that the cryptographic key is uncompromised comprises:

receiving a denial of signature request, including a suspect base value B₀ and a suspect pseudonym value K₀ of a suspect signature from the verifier;

receiving a revocation identifier associated with the suspect signature as a suspect revocation identifier; and

performing a direct proof by the hardware device to deny that the cryptographic key F stored within the hardware device matches the unknown suspect key F₀ if the suspect revocation identifier matches a revocation identifier received with a signature request from the verifier.

8. The method of claim 1, wherein convincing the verifier that the cryptographic key is uncompromised comprises:

(a) receiving a denial of signature request from the verifier, including at least one suspect direct proof signature;

(b) determining whether the request for the denial of signature has been approved by a predetermined revocation authority according to one or more public keys of one or more revocation authorities stored within the hardware device; and

(c) performing a direct proof to deny that the cryptographic key stored within the hardware device was used in a direct proof with the verifier to form the suspect direct proof signature, if the request was signed by a predetermined revocation authority.

9. The method of claim 7, further comprising:

repeating (a)-(c) for a plurality of suspect direct proof signatures; and

if the plurality of suspect direct proof signatures exceeds a suspect direct proof signature limit value, notifying the verifier that the verifier has exceeded the suspect direct proof signature limit value.

10. A method, comprising:

verifying that an anonymous hardware device possesses cryptographic information without determining the cryptographic information of the hardware device; and

verifying that a cryptographic key of the hardware device was not used to generate at least one suspect signature held by a verifier to prove to the verifier that the cryptographic key of the anonymous hardware device is uncompromised, where a suspect key used to generate the suspect signature is unknown to the verifiers without determining the cryptographic key or any unique device identification information of the hardware device to enable the hardware device to remain anonymous to the verifier.

11. The method of claim 10, wherein prior to verifying that the hardware device possesses cryptographic information, the method comprises:

detecting compromised content of the verifier;

determining a base B₀ and a pseudonym K₀ of a suspect direct proof signature used to receive the compromised content; and

storing the B₀ and a pseudonym K₀ as a suspect direct proof signature generated with an unknown, suspect key F₀.

12. The method of claim 10, wherein verifying that the hardware device possesses cryptographic information comprises:

receiving a proof from the hardware device to verify that a cryptographic key is stored within the hardware device, the proof comprising a plurality of exponentiations, at least one being conducted using the cryptographic key as an exponent without exposing the cryptographic key.

13. The method of claim 10, wherein verifying the hardware device possesses cryptographic information comprises:

computing, by the hardware device, a pseudonym, K, using the cryptographic key; and

receiving the pseudonym, K, from the hardware device.

14. The method of claim 13, wherein verifying that the cryptographic key was not used to generate the suspect signature comprises:

providing the hardware device with a denial of signature request, including a base B₀ and a pseudonym K₀ of a suspect direct proof signature generated with an unknown, suspect key F₀, the base B₀ and pseudonym K₀ having an associated revocation identifier; and

receiving a direct proof from the hardware device to convince the verifier that a cryptographic key F of the hardware device used to construct the pseudonym, K, does not match the suspect compromised key F₀ if a revocation identifier provided to the hardware device during a digital signature request matches a revocation identifier associated with the suspect direct proof signature.

15. The method of claim 10, wherein verifying that the cryptographic key was not used to generate the suspect signature comprises:

(a) providing the hardware device with a denial of signature request including a base B₀ and a pseudonym K₀ of a suspect signature formed with an unknown suspect key F₀;

(b) verifying that a cryptographic key F of the hardware device does not match the suspect compromised key F₀ without identification of the cryptographic key F of the hardware device.

16. The method of claim 15, wherein verifying further comprises:

receiving a proof from the hardware device that a value R exists such that;

S=B₀^R mod P and T=K₀^R mod P,

without identification of any useful information about R;

receiving a proof from the hardware device that a value F exists such that;

U=S^F mod P and K=B^F mod P,

without identification of any useful information about F; and

identifying the cryptographic key F of the hardware device as uncompromised if U≈

T mod P.

17. The method of claim 16, further comprising:

identifying the cryptographic key F of the hardware device as compromised if U=T mod P.

18. The method of claim 15, further comprising:

repeating (a) and (b) for a predetermined number of suspect direct proof signatures; and

if the predetermined number exceeds a suspect direct proof signature limit value, rekeying hardware devices that are members of a platform family defined by a certifying manufacturer of the hardware device.

19. The method of claim 10, wherein verifying that the hardware device possesses cryptographic information comprises:

transmitting a signature request to the hardware device, including a revocation identifier of a verifier of the hardware device;

receiving a digital signature of the hardware device, including the revocation identifier; and

authenticating the digital signature of the hardware device according to a public key of a manufacturer of the hardware device.

20. An anonymous hardware device, comprising:

a flash memory to store cryptographic information from a certifying manufacturer; and

a trusted platform module to convince a verifier that the anonymous hardware device possesses cryptographic information from a certifying manufacturer without disclosure of the cryptographic information to the verifier, and to convince the verifier that a cryptographic key, stored within the flash memory, is uncompromised without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier; and

denial of signature logic to receive a denial of sinnature request, including a base value B₀ and a pseudonym value K₀ of a suspect signature from the verifier and to convince the verifier that the cryptographic key stored within the hardware device and used to construct a pseudonym. K, does not match an unknown, suspect key F₀ used to form the suspect signature.

21. The anonymous hardware device of claim 20, wherein the trusted platform module comprises:

authentication logic to prove that the cryptographic key is stored within the hardware device according to a direct proof comprising a plurality of exponentiations, at least one being conducted using the cryptographic key as an exponent without exposing the cryptographic key.

22. The anonymous hardware device of claim 20, wherein the trusted platform module comprises:

key logic to receive a unique secret pair (c,F) from a certifying manufacturer of the apparatus where F is a signature key of the hardware device of the form c^e mod P, where the pair (e, P) is a public key of the certifying manufacturer.

23. The anonymous hardware device of claim 22, wherein the trusted platform module comprises:

a flash memory to store the unique, secret pair (c,F).

24. A system, comprising:

a verifier platform coupled to a network; and

an anonymous prover platform coupled to the network, comprising;

a bus,

a processor coupled to the bus,

a chipset coupled to the bus, including a trusted platform module, in response to a challenge received over the network, the trusted platform module to convince the verifier platform that the anonymous prover platform device possesses cryptographic information without disclosure of the cryptographic information to the verifier platform and to convince the verifier that a cryptographic key stored within the anonymous prover platform is uncompromised without disclosure of the cryptographic key or any unique device identification information of the anonymous prover platform to the verifier to enable the prover platform to remain anonymous to the verifier platform, and

denial of signature logic to receive a denial of signature reiuest, including a base value B₀ and a pseudonym value K₀ of a suspect signature from the verifier platform, and to convince the verifier platform that a cryptographic key F stored within the anonymous prover platform used to compute a pseudonym, K, does not match an unknown, suspect key F₀ used to form the suspect signature.

25. The system of claim 24, wherein the chipset comprises a graphics controller.

26. The system of claim 24, wherein the network comprises a wide area network work.

27. The system of claim 24, wherein the trusted platform module comprises:

key logic to receive a unique secret pair (c,F) from a certifying manufacturer of the apparatus where F is a signature key of the hardware device of the form c^e mod P, where the pair (e, P) is a public key of the certifying manufacturer; and

a flash memory to store the unique, secret pair (c,F).

28. An article of manufacture including a machine readable medium having stored thereon instructions which use to program a system to perform a method, comprising:

convincing a verifier that an anonymous hardware device possesses cryptographic information without disclosure of the cryptographic information to the verifier;

receiving a denial of signature reciuest, including a base value B₀ and a pseudonym value K₀ of a suspect signature from the verifier;

convincing the verifier that a cryptographic key, F, stored within the hardware device and used to construct a pseudonym, K, does not match an unknown, suspect key F₀ used to form the suspect signature, to prove to the verifier that the cryptographic key, F, stored within the anonymous hardware device is uncompromised without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier.

29. The article of manufacture of claim 28, wherein convincing a verifier that a hardware device possesses cryptographic information comprises:

using the cryptographic information to compute a pseudonym, K; and

providing that pseudonym, K, to the verifier.

30. The article of manufacture of claim 28, wherein convincing the verifier that the cryptographic key does not match the unknown, compromised key F₀ comprises:

selecting a random exponent value R;

transmitting one or more computed values to the verifier according to the suspect-base value B₀ and the suspect pseudonym value K₀ received from the verifier, a modulus value P of the hardware device and the random exponent value R;

performing a proof by the hardware device to deny that the cryptographic key F stored within the hardware device was used to create a direct proof suspect signature, the proof comprising a plurality of exponentiations, each being conducted using one of the cryptographic key, F, the random exponent value R and other exponent values as an exponent without exposing the cryptographic key, the random exponent value R and the other exponent values.

31. The article of manufacture of claim 30, wherein performing the proof comprises:

convincing the verifier that the value R exists such that;

S=B₀^R mod P and T=K₀^R mod P,

without revealing any useful information about R; and

convincing the verifier that a value F exists such that;

U=S^F mod P and K=B^F mod P,

without revealing any useful information about F.

32. The article of manufacture of claim 31, wherein the verifier is convinced that the cryptographic key F stored within the hardware device was not used to create the suspect direct proof signature if U≠

T mod P.

33. An article of manufacture including a machine readable medium having stored thereon instructions which use to program a system to perform a method, comprising:

verifying that an anonymous hardware device possesses cryptographic information without determining the cryptographic information of the hardware device; and

verifying that a cryptographic key of the hardware device was not used to generate at least one suspect signature held by a verifier, to prove that the cryptographic key of the verifier is uncompromised, where a suspect key used to generate the suspect signature is unknown to the verifier, without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier.

34. The article of manufacture of claim 33, wherein verifying that the hardware device possesses cryptographic information comprises:

receiving a proof from the hardware device to verify that a cryptographic key is stored within the hardware device, the proof comprising a plurality of exponentiations, at least one being conducted using the cryptographic key as an exponent without exposing the cryptographic key.

35. The article of manufacture of claim 33, wherein verifying that the cryptographic key was not used to generate the suspect signature comprises:

(a) providing the hardware device with a denial of signature request including a base B₀ and a pseudonym K₀ of a suspect direct proof signature formed with an unknown suspect key F₀;

(b) verifying that a cryptographic key F of the hardware device does not match the suspect compromised key F₀ without identification of the cryptographic key F of the hardware device.

36. The article of manufacture of claim 35, wherein verifying further comprises:

receiving a direct proof from the hardware device that a value R exists such that;

S=B₀^R mod P and T=K₀^R mod P,

without identification of any useful information about R;

receiving a direct proof from the hardware device that a value F exists such that;

U=S^F mod P and K=B^F mod P,

without identification of any useful information about F; and

identifying the cryptographic key of the hardware device as uncompromised if U≠

T mod P.

37. The article of manufacture of claim 36, further comprising:

identifying the cryptographic key F of the hardware device as compromised if U=T mod P.

38. A method comprising:

convincing a verifier that an anonymous hardware devices possesses cryptographic information without disclosure of the cryptographic information the verifier; and

convincing a verifier that a cryptographic key of the anonymous hardware device was not used to generate at least one suspect signature held by a verifier, where a suspect key used to generate the suspect signature is unknown to the verifier, to prove to the verifier that the cryptographic key is uncompromised, without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier.

39. A method comprising:

convincing a verifier that an anonymous hardware device possesses cryptographic information without disclosure of the cryptographic information to the verifier;

transmitting one or more computed values to the verifier according to a suspect-base value B₀ and a suspect pseudonym value K₀ received from the verifier, a modulus value P of the hardware device and a random exponent value R selected by the hardware device in response to a denial of signature request, including the base value B₀ and the pseudonym value K₀ of the suspect signature from the verifier; and

performing a proof by the hardware device to deny that a cryptographic key, F, stored within the hardware device was used to create a suspect direct proof signature prove to the verifier that the cryptographic key stored within the anonymous hardware device is uncompromised, without disclosure of the cryptographic key or any unique device identification information of the hardware device to the verifier to enable the hardware device to remain anonymous to the verifier, the proof comprising a plurality of exponentiations, each being conducted using one of the cryptographic key, F, the random exponent value R and other random exponent values as an exponent without exposing the cryptographic key, F, the random exponent value R and the other random exponent values.