Enhanced privacy id: a direct anonymous attestation scheme with enhanced revocation capabilities

ABSTRACT

Direct Anonymous Attestation (DAA) is a scheme that enables the remote authentication of a Trusted Platform Module (TPM) while preserving the user's privacy. A TPM can prove to a remote party that it is a valid TPM without revealing its identity and without linkability. In the DAA scheme, a TPM can be revoked only if the DAA private key in the hardware has been extracted and published widely so that verifiers obtain the corrupted private key. If the unlinkability requirement is relaxed, a TPM suspected of being compromised can be revoked even if the private key is not known. However, with the full unlinkability requirement intact, if a TPM has been compromised but its private key has not been distributed to verifiers, the TPM cannot be revoked. Furthermore, a TPM cannot be revoked from the issuer, if the TPM is found to be compromised after the DAA issuing has occurred. In this paper, we present a new DAA scheme called Enhanced Privacy ID (EPID) scheme that addresses the above limitations. While still providing unlinkability, our scheme provides a method to revoke a TPM even if the TPM private key is unknown. This expanded revocation property makes the scheme useful for other applications such as for driver's license. Our EPID scheme is efficient and secure in the same security model as DAA, i.e. in the random oracle model under the strong RSA assumption and the decisional Diffie-Hellman assumption.

REFERENCES

• 1: Giuseppe Ateniese , Jan Camenisch , Marc Joye , Gene Tsudik, A Practical and Provably Secure Coalition-Resistant Group Signature Scheme, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.255-270, August 20-24, 2000
• 2: G. Ateniese, D. X. Song, and G. Tsudik. Quasi-efficient revocation in group signatures. In Proceedings of the 6th International Conference on Financial Cryptography, volume 2357 of LNCS, pages 183-¿197. Springer, 2002.
• 3: M. Bellare, J. A. Garay, and T. Rabin. Fast batch verification for modular exponentiation and digital signatures. In Advances in Cryptology ¿ EUROCRYPT ¿98, volume 1403 of LNCS, pages 236-¿250. Springer, 1998.
• 4: D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In Advances in Cryptology ¿ CRYPTO ¿04, volume 3152 of LNCS, pages 41¿-55. Springer, 2004. 29
• 5: Dan Boneh , Hovav Shacham, Group signatures with verifier-local revocation, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030106]
• 6: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 7: Emmanuel Bresson , Jacques Stern, Efficient Revocation in Group Signatures, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.190-206, February 13-15, 2001
• 8: Ernie Brickell , Jan Camenisch , Liqun Chen, Direct anonymous attestation, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030103]
• 9: E. Brickell and J. Li. Enhanced Privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities. Cryptology ePrint Archive, Report 2007/194, 2007. http://eprint.iacr.org/.
• 10: Ernest F. Brickell , David Chaum , Ivan Damgård , Jeroen van de Graaf, Gradual and Verifiable Release of a Secret, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.156-166, August 16-20, 1987
• 11: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 12: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 13: J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In Proceedings of the 3rd Conference on Security in Communication Networks, volume 2576 of LNCS, pages 268¿-289. Springer, 2002.
• 14: J. Camenisch and M. Michels. Proving in zero-knowledge that a number is the product of two safe primes. In In Advances in Cryptology ¿ EUROCRYPT ¿99, volume 1592 of LNCS, pages 106-¿121. Springer, 1999.
• 15: Jan Camenisch , Markus Michels, Separability and Efficiency for Generic Group Signature Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.413-430, August 15-19, 1999
• 16: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 17: R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Weizmann Institute of Science, Rehovot, Israel, 1995.
• 18: R. Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143¿-202, 2000.
• 19: David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
• 20: David Chaum, Zero-knowledge undeniable signatures (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.458-464, February 1991, Aarhus, Denmark
• 21: D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In Advances in Cryptology ¿ EUROCRYPT ¿87, volume 304 of LNCS, pages 127¿-141. Springer, 1987.
• 22: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 23: D. Chaum and E. van Heyst. Group signatures. In Advances in Cryptology ¿ EUROCRYPT ¿91, volume 547 of LNCS, pages 257¿-265. Springer, 1991.
• 24: I. Damgård and E. Fujisaki. An integer commitment scheme based on groups with hidden order. In Advances in Cryptology ¿ ASIACRYPT ¿02, volume 2501 of LNCS, pages 125-¿142. Springer, Dec. 2002.
• 25: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 26: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 27: Joe Kilian , Erez Petrank, Identity Escrow, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.169-185, August 23-27, 1998
• 28: A. K. Lenstra and E. R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology, 14(4):255¿-293, 2001.
• 29: Birgit Pfitzmann , Michael Waidner, Composition and integrity preservation of secure reactive systems, Proceedings of the 7th ACM conference on Computer and communications security, p.245-254, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352639]
• 30: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 31: D. Pointcheval and J. Stern. Security proofs for signature schemes. In Advances in Cryptology ¿ EUROCRYPT ¿96, volume 1070 of LNCS, pages 387¿-398. Springer, 1996
• 32: C. P. Schnorr. Efficient identification and signatures for smart cards. Journal of Cryptology, 4(3):161-¿174, 1991.
• 33: Dawn Xiaodong Song, Practical forward secure group signature schemes, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502015]
• 34: Trusted Computing Group. TCG TPM specification 1.2, 2003. Available at http://www.trustedcomputinggroup.org.
• 35: Trusted Computing Group website. http://www.trustedcomputinggroup.org.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Security

Keywords:
anonymity, cryptographic protocols, privacy, trusted computing