### Sketch of EPID Scheme

We have developed two EPID schemes, one from the strong RSA assumption [7] and the other from bilinear maps [6]. In this article, we briefly sketch the EPID scheme from bilinear maps. (The full scheme can be found in [6]).

Let us first review some background on bilinear maps. Let **G1** and **G2** be two multiplicative cyclic groups of prime order p. Let g1 be a generator of **G1**, and **g _{2}** be a generator of

**G2**. We say

**e: G1 x G2 → GT**is an admissible bilinear map function, if it satisfies the following properties:

For all **u ∈ G1, v ∈ G2**, and for all integers **a, b**, equation **e(u ^{a}, v^{b}) = e(u, v)^{ab}** holds. The result of

**e(g**is a generator of

_{1}g_{2})**GT**. There exists an efficient algorithm for computing

**e(u, v)**for any

**u ∈ G1, v ∈ G2**.

Our EPID scheme is derived from Boneh, Boyen, and Shacham's group signatures scheme [2] and has the following operations:

**Setup**: The issuer does the following:

- Chooses G1 and G2 of prime order p and a bilinear map function e : G1 x G2 → GT.
- Chooses a group G3 of prime order p with generator g
_{3}. - Chooses at random g
_{1}h_{1}, h_{2}∈ G1 and g_{2}∈ G2. - Chooses a random r ∈ [1, p-1] and computes w = g
_{2}^{r}. The public key is (g_{1}, g_{2}, g_{3}, h_{1}, h_{2}, w) and the issuing private key is r.

**Join**: The join protocol is an interactive protocol between the issuer and a member as follows:

- The member chooses at random f and y' from [0, p-1] and computes
- The member sends T to the issuer and performs the following proof of knowledge to the issuer:
The issuer chooses at random x and y" from [0, p-1] and computes

- The issuer sends (A, x, y" ) to the member.
- The member computes y = y' + y"(mod p). The member's private key is (A, x, y, f ).

Note that given a valid private key (A, x, y, f ), the following equation satisfies:

**Sign**: Let (A, x, y, f ) be the member's private key. The member does the following:

- If the random base option is used, the member chooses B at random from G3.
- If the name base option is used, the member computes B = Hash (verifier's basename).
Computes K = B

^{f}Computes the following zero-knowledge proof

This essentially proves that the member has a valid EPID private key issued by the issuer.

- Computes the following zero-knowledge proof
for each (B', K') pair in SIG-RL. This step proves that the member has not been revoked in SIR-RL; that is, the member did not create those (B', K') pairs in SIG-RL

- Converts all the above zero-knowledge proofs into a signature by using the Fiat-Shamir heuristic [9].

**Verify**: Given the public key, PRIV-RL, SIG-RL, and an EPID signature, the verifier does the following:

- If the random base option is used, the verifier verifies that B is an element in G3.
- If the name base option is used, the verifier verifies that B = Hash (verifier's basename).
- Verifies that K is an element in G3.
- Verifies the following proof
This step verifies that the member has a valid EPID private key.

- Verifies that K ≠ B
^{f'}for each f' in PRIV-RL. This step verifies that the member has not been revoked in PRIV-RL. - Verifies the following zero-knowledge proof
for each (B', K') pair in SIG-RL. This step verifies that the member has not been revoked in SIG-RL.

### Comparison with Other Techniques

There are other techniques to remotely authenticate hardware, and in this section we review these techniques and compare them with our EPID scheme.

**Public Key Infrastructure (PKI)**. Each hardware device has a unique public and private key pair as well as a device certificate. To authenticate hardware by using PKI, the device simply shows its certificate to the verifier along with a signature created by using the device's private key. As mentioned previously, this PKI approach does not satisfy the privacy requirement.**Direct Anonymous Attestation (DAA)**. DAA was designed for anonymous attestation of TPM [4, 5]. DAA satisfies all the design requirements of remote hardware authentication; however, it has limited revocation capabilities compared to those of EPID. In the DAA scheme, there are two options for a balance between linkability and revocation. If the random base option is used, that is, a different base is used every time a DAA signature is performed, then any two signatures by a device are unlinkable, but revocation only works if the corrupted device private key has been revealed to the public. If a device has been compromised, but its private key has not been distributed to the verifiers (for example, if the corrupted device's private key is still under the control of the adversary), the corrupted TPM cannot be revoked. If the name base option is used, then any two signatures produced by a device, using the same base, are linkable. Thus, if the verifier determines that a device private key, used in a signature, has been compromised, that verifier can revoke that key locally; that is, the verifier can reject all future signatures generated by that private key, without knowledge of the compromised private key. However, the verifier cannot tell if a different verifier uses a different name base to revoke that private key, because when a different name is used, the revoked key cannot be identified. Furthermore, the name-based option does not safeguard privacy, because the verifier can link the transactions.**Group Signatures (GS)**. A group signature scheme [1, 2] has similar properties to those of the EPID scheme. In a group signature scheme, an issuer creates a group public key and issues unique private keys to each group member. Each group member can use the private key to sign a message, and the resulting signature is called a group signature. The verifier can verify a group signature by using the group public key. Unlike EPID, group signature schemes have an additional property called traceability. This property enables the issuer to open any group signature and identify the actual group member who created the signature. In other words, a group signature is anonymous to the verifiers but not to the issuer. Again, as compared to this scheme, EPID keeps the identity of the group member from the issuer.**Pseudonym System (PS)**. The pseudonym system [3], designed by Brands, can also be used for remote hardware authentication. In the pseudonym system, the display of a credential is anonymous by virtue of the fact that efficient zero-knowledge proof techniques are used for proving relations among committed values. To use the pseudonym system for hardware authentication, each hardware device obtains a credential from the issuer and uses the pseudonym credential for proof of membership. However, a credential in that system is linkable for multiple displays. To be unlinkable, a hardware device has to get multiple credentials from the issuer and use one credential at a time. This approach has limited application for hardware authentication, as the hardware device may never be able connect back to the issuer (the device manufacturer) once it has been produced. Thus, it cannot maintain the unlinkable property by continuing to get new credentials from the issuer.### Summary

In Table 1, we summarize a comparison between different approaches to the remote hardware authentication problem. The EPID scheme is the only scheme that satisfies all the design requirements mentioned earlier.

### References

[1] G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. “A practical and provably secure coalition-resistant group signature scheme.” In Advances in Cryptology -- Crypto, Volume 1880 of Lecture Notes in Computer Science, pages 255–270, 2000.

[2] D. Boneh, X. Boyen, and H. Shacham. “Short group signatures.” In Advances in Cryptology -- Crypto, Volume 3152 of Lecture Notes in Computer Science, pages 41–55, 2004.

[3] S. Brands. Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT Press, Cambridge, MA, 2000.

[4] E. Brickell, J. Camenisch, and L. Chen. “Direct Anonymous Attestation.” In Proceedings of the 11th ACM Conference on Computer and Communications Security, pages 132–145, 2004.

[5] E. Brickell, L. Chen, and J. Li. “A New Direct Anonymous Attestation Scheme from Bilinear Maps.” In Proceedings of 1st International Conference on Trusted Computing, Volume 4968 of Lecture Notes in Computer Science, pages 166–178, 2008.

[6] E. Brickell and J. Li. “Enhanced Privacy ID from Bilinear Pairing.” Cryptology ePrint Archive, Report 2009/095, 2009.

[7] E. Brickell and J. Li. “Enhanced Privacy ID: a Direct Anonymous Attestation Scheme with Enhanced Revocation Capabilities.” In Proceedings of the 6th ACM Workshop on Privacy in the Electronic Society, pages 21–30, 2007.

[8] J. Camenisch and V. Shoup. “Practical Verifiable Encryption and Decryption of Discrete Logarithms.” In Advances in Cryptology -- Crypto, Volume 2729 of Lecture Notes in Computer Science, pages 126–144, 2003.

[9] A. Fiat and A. Shamir. “How to Prove Yourself: Practical Solutions to Identification and Signature Problems.” In Advances in Cryptology -- Crypto, Volume 263 of Lecture Notes in Computer Science, pages 186–194, 1987.

[10] O. Goldreich, S. Micali, and A. Wigderson. “Proofs that Yield Nothing but their Validity.” Journal of the ACM, Volume 38(3), pages 690-728, 1991.

[11] Trusted Computing Group. “TCG TPM Specification 1.2,” 2003, http://www.trustedcomputinggroup.org

*This article and more on similar subjects may be found in the Intel Technology Journal, June 2009 Edition, "Advances in Internet Security*.