System and method for establishing trust without revealing identity

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.

What is claimed is: 
     
       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.