System and method for establishing trust without revealing identity

• US 7,165,181 B2
• Filed: 11/27/2002
• Issued: 01/16/2007
• Est. Priority Date: 11/27/2002
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Brickell, Ernie F.
• Primary Examiner(s): Peeso; Thomas R.
• Application Number:
  US10/306,336
• Publication Number:
  US 20040103281A1
• Time in Patent Office: 1,511 Days
• Field of Search: 713/158, 713/161, 713/168, 713/175, 713/182, 713/200, 713/201
• US Class Current: 713/182
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

One aspect of an embodiment of the invention provides a method, system, and device to prove to a challenger that a prover device has a signature from a device manufacturer without revealing the signature to the challenger. According to one implementation, a challenger is provided with the result of a one-way function of a secret held by a prover device. An interactive proof is employed, between the prover device and the challenger, to prove to the challenger that the secret used in the one-way function has been signed by a device signature without revealing the secret or the device signature or the prover device'"'"'s identity to the challenger.

Claims

1. A method comprising:

receiving an authentication request from a challenger device; and

sending information to the challenger device from a prover device; and

convincing the challenger device that a valid signature that is not on a revocation list of compromised device signatures is known by the prover device without revealing the signature to the challenger device.

2. The method of claim 1 wherein the information sent to the challenger device includes a device certificate for the prover device.

3. The method of claim 1 further comprising:

generating a value k based on a one-way function; and

generating a private-public key pair in the prover device, the private-public key pair including a private key and a public key, wherein value k and the public key are included in the information sent to the challenger device.

4. The method of claim 3 wherein the value k is defined as

k=h^m mod P, where h is a unique number generated by the prover device, m is a randomly generated number, and P is a large prime number.

5. The method of claim 1 wherein convincing the challenger device that a valid signature is known by a prover device without revealing the signature to the challenger device includes

sending the challenger device an interactive proof that the prover device knows the signature without revealing the signature to the challenger device.

6. The method of claim 1 further comprising:

convincing the challenger device that the prover device knows the valid signature without revealing the identity of the prover device.

7. A method comprising:

convincing a challenger that a prover has a valid signature of a known entity without revealing the signature; and

convincing the challenger that the signature is not on a revocation list of compromised signatures without revealing the signature.

8. The method of claim 7 wherein convincing the challenger that the prover has a valid signature of a known entity without revealing the signature includes

generating a value k based on a one-way function;

and

generating a private-public key pair in the prover device, the private-public key pair including a private key and a public key, wherein value k and the public key are included in information sent to the challenger.

9. The method of claim 7 wherein convincing the challenger that the prover has a valid signature of a known entity without revealing the signature includes

sending the challenger an interactive proof that the prover knows the valid signature without revealing the signature to the challenger.

10. The method of claim 7 wherein convincing the challenger that the signature is not on a revocation list includes

maintaining a revocation list of information corresponding to one or more provers which are considered compromised, and

comparing the prover'"'"'s information to the information in the revocation list.

11. The method of claim 7 wherein convincing the challenger that a prover has a valid signature of a known entity means that it is probabilistically likely that the prover knows the signature, and not revealing the signature to the challenger means that it is computationally infeasible for the challenger to calculate the signature based on information revealed by the prover.

12. A method comprising:

convincing a first challenger device that a second device has a valid signature without disclosing the signature to the first device; and

convincing a third challenger device that the second device has a valid signature without disclosing the signature to the third device, wherein the information provided by the second device to the first challenger device and third challenger device is insufficient to permit the first challenger device and third challenger device to determine whether they are communicating with the same second device.

13. The method of claim 12 wherein convincing the first challenger that the second device has a valid signature without disclosing the signature includes

generating a value k based on a one-way function;

and

generating a private-public key pair in the prover device, the private-public key pair including a private key and a public key, wherein value k and the public key are included in information sent to the challenger.

14. The method of claim 12 wherein at least some of the information provided by the second device to the first challenger device is different from the information provided by the second device to the third challenger device.

15. A method comprising:

revealing to a first challenger platform the result of a one-way function of a secret held by a prover platform; and

proving to the first challenger platform that the secret has a valid signature without revealing the secret to the first challenger platform.

16. The method of claim 15, further comprising:

revealing to a second challenger platform the result of a one-way function of the secret held by the prover platform; and

proving to the second challenger platform that the secret has the valid signature without revealing the secret to the second challenger platform and such that the first challenger and second challenger cannot determine that they are communicating with the same prover platform.

17. The method of claim 15, further comprising:

sending the first challenger platform an interactive proof that the prover platform knows the valid signature without revealing the signature to the challenger.

18. The method of claim 15, further comprising:

convincing the first challenger platform that an unrevealed signature of the prover platform is not on a revocation list.

19. The method of claim 15 wherein proving to the first challenger platform that the secret has a valid signature means that it is probabilistically likely that the prover platform knows the secret, and proving this to the first challenger platform without revealing the secret to the first challenger platform means that it would be computationally infeasible for the first challenger platform to calculate the secret based on information revealed by the prover platform.

20. A method comprising:

convincing a challenger a first time that a prover has a valid signature of a known entity without revealing the signature; and

convincing the same challenger a second time that the prover has a valid signature of a known entity without revealing the signature, wherein the challenger is not able to determine that the same signature was used during the first and second times.

21. The method of claim 20, further comprising:

sending the challenger an interactive proof that the prover knows the valid signature without revealing the signature to the challenger.

22. The method of claim 20, further comprising:

convincing the challenger that the signature of the prover is not on a revocation list.

23. A method comprising:

generating a first signature key pair in a first device, the first signature key pair including a public signature key and a private signature key;

providing the first public signature key to a first challenger; and

proving to the first challenger that the first device has a signed secret without revealing a signature used to sign the secret or revealing the private signature key.

24. The method of claim 23, further comprising:

sending the first challenger an interactive proof that the first device knows the signed secret without revealing the signed secret to the first challenger.

25. The method of claim 23 wherein proving to the first challenger that the first device has the signature used to sign the secret means that it is probabilistically likely that the prover device knows the secret, and proving this to the first challenger without revealing the signature used to sign the secret or revealing the private signature key to the first challenger means that it would be computationally infeasible for the first challenger to calculate either the secret, the signature used to sign the secret, or the private key based on information revealed by the prover device.

26. The method of claim 23 further comprising:

proving to the first challenger that the first device has a signed secret without revealing the identity of the device.

27. A device comprising:

a communication port; and

a processing unit, the processing unit configured to

communicate with a challenger platform over the communication port, and

convince the challenger platform that it is probabilistically likely that the prover device knows a secret without revealing the identity of the device.

28. The device of claim 27 wherein convincing the challenger platform that the device knows the secret without revealing the identity of the device includes

proving to the challenger platform that it has a valid signature of a known entity without revealing the signature, and

tying a value correlated with the secret to the communication with the challenger platform so that a different value cannot be substituted without violating the proof.

29. A system comprising:

a challenger device; and

a prover device communicatively coupled to the challenger device, the prover device configured to

convince the challenger that the prover device has a valid signature of a known entity that is not on a revocation list of compromised signatures without revealing the signature.

30. The system of claim 29 wherein convincing the challenger device that the prover device has a valid signature of a known entity without revealing the signature includes

revealing to the challenger device the result of a one-way function of a secret held by the prover device, and

proving to the challenger device that the secret has a valid signature without revealing the secret to the challenger device.

31. The system of claim 29 wherein convincing the challenger device that the signature is not on a revocation list includes

maintaining a revocation list of information corresponding to one or more prover devices which are considered compromised, and

comparing the prover device'"'"'s information to the information in the revocation list.