Channels ▼


Enhanced Privacy ID

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 y1 = g1x and y2 = g2x hold, where x is known only to the prover, and g1, y1, g2, y2 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 y1, y2 to base z1, and z2, 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 = Bf. 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 ≠ Bf' for every f' in PRIV-RL. If there exists an f' in PRIV-RL, such that K = Bf', 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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.