Overview of EPID

In our EPID scheme, there are three types of entities: issuer, members, and verifiers. There are two revocation lists: a list of corrupted private keys, denoted as PRIV-RL, and a list of signatures made from suspected extracted keys, denoted as SIG-RL. An EPID scheme has the following operations:

• Setup. The issuer creates a public key and an issuing private key. The issuer publishes and distributes the public key to everyone (that is, to every member and every verifier).
• Join. This is an interactive protocol between an issuer and a member, the result of which is that the member obtains a unique private key.
• Sign. Given a message m and a SIG-RL, a member creates an EPID signature on m by using its private key.
• Verify. The verifier verifies the correctness of an EPID signature by using the public key. The verifier also checks that the key used to generate the signature has not been revoked in PRIV-RL or SIG-RL.

Figure 2 depicts the interaction flows between the issuer, a member, and a verifier.

Figure 2: Basic EPID Scheme (Source: Intel Corporation, 2009)

Zero-knowledge Proofs. In our EPID scheme, we use zero-knowledge proofs of knowledge [10] extensively. In a zero-knowledge proof system, a prover proves the knowledge of some secret information to a verifier such that (1) the verifier is convinced of the proof and yet (2) the proof does not leak any information about the secret to the verifier. In this article, we use the following notation for proof of knowledge of discrete logarithms. For example,

denotes a proof of knowledge of integer x such that y₁ = g₁^x and y₂ = g₂^x hold, where x is known only to the prover, and g₁, y₁, g₂, y₂ are known to both the prover and verifier. In the above equation, PK stands for proof of knowledge and ∧ stands for logical conjunction.

Proof of knowledge protocols can be turned into signature schemes by using the Fiat-Shamir heuristic [9]. In our EPID scheme, we develop several efficient zero-knowledge proof protocols for proving the knowledge of a valid EPID private key. In addition, we use an efficient zero-knowledge proof protocol developed by Camenisch and Shoup [8] for proving the inequality of discrete logarithms of two group elements y₁, y₂ to base z₁, and z₂, respectively, denoted as

Overview of Our Construction

We begin with a high-level overview of our construction. In our scheme, each member chooses a unique membership key f. The issuer then issues a membership credential on f in a blind fashion such that the issuer does not acquire knowledge of the membership key f. The membership key and the membership credential together form the private key of the member. To sign a signature, the member proves in zero-knowledge that it has a membership credential on f. To verify a group signature, the verifier verifies the zero-knowledge proof.

In addition, each member chooses a base value B and computes K = B^f. This (B, K) pair serves the purpose of a revocation check. We call B the base and K the pseudonym. To sign a signature, the member needs not only to prove that it has a valid membership credential, but also to prove that it constructs the (B, K) pair correctly, all in zero-knowledge.

In EPID, there are two options to compute the base B: the random base option and the name base option.

• Random base option. B is chosen randomly each time by the member. Under the decisional Diffie-Hellman assumption, no verifier can link two EPID signatures based on the (B, K) pairs in the signatures.
• Name base option. B is derived from the verifier's basename; for example, B = Hash (verifier's basename). Note that in this option, the value K becomes a pseudonym of the member with regard to the verifier's basename, as the member will always use the same K in the EPID signature to the verifier.

We first explain how membership can be revoked based on a compromised private key. Given a private key that has been revealed to the public, the issuer extracts the membership key f from the private key and inserts f into the private-key-based revocation list PRIV-RL. The issuer then distributes PRIV-RL to all the verifiers. Given an EPID signature, any verifier can check whether it was created with the corrupted private keys in PRIV-RL as follows:

Let (B, K) be the base-pseudonym pair in the EPID signature. The verifier can check that K ≠ B^f' for every f' in PRIV-RL. If there exists an f' in PRIV-RL, such that K = B^f', it means that the signature was created with a revoked private key. Therefore the verifier can reject the signature.

We now explain how membership is revoked, based on a transaction that a member was involved in. We call this kind of revocation signature-based revocation. Suppose a member's private key has been compromised by an attacker and has been used in some transaction. If the issuer has collected enough evidence to show that the private key used in the transaction was corrupted, the issuer can identify the EPID signature in the transaction and revoke the key, based on the signature. To do this, the issuer extracts the (B, K) pair from the signature and inserts the pair into the signature-based revocation list SIG-RL. The issuer then distributes the SIG-RL to all the verifiers. Before a member performs the membership proof, the verifier sends the latest SIG-RL to the member, so that the member can prove that it did not perform those transactions. More specifically, the member proves that it is not revoked in SIG-RL, by proving that, in zero-knowledge,

for each (B', K') pair in SIG-RL. If the zero-knowledge proof holds, the verifier is convinced that the member has not conducted those transactions and that membership has not been revoked.