. 1
( 2)



>>

Chapter 5

Combining Issuing and
Showing Protocols

In this chapter we show how to seamlessly combine the showing protocol techniques
of Chapter 3 with the issuing protocol techniques of Chapter 4, without adding com-
plexity and without compromising security or privacy. We develop additional privacy
techniques, for both certi¬cate holders and certi¬cate veri¬ers, and design limited-
show certi¬cates that reveal all the encoded attributes in case of fraud. We also design
software-only techniques that enable the CA to discourage a variety of frauds.


5.1 Integration
Consider a PKI with one CA, many certi¬cate holders (provers), and many veri¬ers.
To gain access to a secure “service” provided by a veri¬er V, P must demonstrate
to V its possession of a certi¬cate of the CA on attributes that meet certain criteria.
The CA will issue a certi¬cate to P only after the latter has authenticated itself or
proved its right to obtain such a certi¬cate. Clearly, the CA can non-interactively
issue an ordinary digital signature on a public key h of P constructed as described in
Chapter 3, but this does not offer any privacy with respect to the CA. In this section
we show how to combine the showing protocol techniques of Chapter 3 with the
issuing protocol techniques of Chapter 4.

5.1.1 Making the match
The case of DLREP-based scheme I or II or the immunization in Section 4.4.1
Suppose that the CA (playing the role of P 0 ) uses DLREP-based scheme I or II, or
their immunization described in Section 4.4.1. P (playing the role of V 0 ) obtains a
182 COMBINING ISSUING AND SHOWING PROTOCOLS


certi¬cate of the CA on a public key h of the form

g1 1 · · · gl l g0 1 ,
x x±


where x1 , . . . , xl ∈ Zq are the encoded attributes and ± 1 ∈ Zq is a random number
chosen by P. P can subsequently demonstrate to V a property about the encoded
attributes, in the manner described in Chapter 3. The perfect ¬t of the issuing and
showing protocols is illustrated by the dual role now played by the blinding factor ± 1 :
it ensures that h is uncorrelated to the view of the CA in the issuing protocol, and also
that P in the showing protocol does not reveal anything about the encoded attributes
beyond the validity of the formula it demonstrates (see Proposition 3.6.1(c)).
It is not hard to prove the following generalization of Proposition 4.3.4.
Proposition 5.1.1. Suppose that P follows the issuing protocol and uses the result-
ing certi¬ed key pair in a showing protocol execution in which it demonstrates some
property of the encoded attributes. The view that V can obtain could have originated
(with uniform probability) from any one of the issuing protocol executions in which
P0 encoded attributes that P0 knows satisfy this particular property.
This result applies even when P0 and V conspire throughout, and applies also to
the other protocol combinations considered in this section.

The case of the other DLREP-based schemes in Chapter 4
The match between the showing protocol techniques and the other DLREP-based
issuing protocols described in Chapter 4 seems more problematic at ¬rst. P obtains
a certi¬cate on a public key h of the form

(g1 1 · · · gl l h0 )±1 ,
x
x



where ±1 ∈ Zq is a random number chosen by P. The blinding factor this time
spreads across all exponents. This does not limit the applicability of our showing
protocol techniques in any way, though. There are two approaches:
• If ±1 = 0 mod q (which is required) then

h’1 = g1 1 · · · gl l (h )’1/±1 ,
x x
0

and so P can demonstrate Boolean formulae for the DL-representation that
it knows of h’1 with respect to (g1 , . . . , gl , h ). Although h is not a ¬xed
0
generator speci¬ed by the CA, the security properties are not adversely af-
fected. Namely, the ability to prove knowledge of a DL-representation of h ’1 0
with respect to (g1 , . . . , gl , h ) implies the ability to prove knowledge of a DL-
representation of h with respect to (g1 , . . . , gl , h0 ). Proposition 3.6.1(b) is
easily seen to apply. The showing protocol techniques and results in Chapter 3
5.1 INTEGRATION 183


apply without change, because the distribution of ’1/± 1 mod q is statistically
indistinguishable from the uniform distribution over Z q . Note that P™s abil-
ity to demonstrate a Boolean formula, and thus to prove knowledge of a DL-
representation of h ’1 with respect to (g1 , . . . , gl , h ), implicitly demonstrates
0
that ±1 = 0 mod q (much as in Section 3.4.1).
• The above twist of considering DL-representations of h ’1 with respect to
0
(g1 , . . . , gl , h ) is not necessary. Consider h = g1 1 ±1 · · · gl l ±l h±1 . Let z0 :=
x
x
0
±1 , and let zi denote xi ±1 mod q, for all i ∈ {1, . . . , l}. V can verify that
±1 = 0 mod q by checking that h = 1, and so demonstrating that x 1 =
βx2 +γ mod q, say, is equivalent to demonstrating that z 1 = βz2 +γz0 mod q.
This we can handle by using our demonstration technique for linear relations.
It is easy to see that any Boolean formula can be handled in this manner.
As will be shown in Section 5.1.2, both approaches have unique security implications
with respect to the delegation strategy in case they are combined with a secret-key
certi¬cate issuing protocol that admits arbitrary parallelization.
The second approach results exactly in the ¬rst approach if we have P in addition
demonstrate that z 0 = 0, as part of the formula it is to demonstrate. In the example,
the formula would become (z 1 = βz2 + γz0 ) AND NOT(z0 = 0). Of course, V in
that case need no longer check that h = 1.
Since P0 in the issuing protocol in Section 4.5.2 need not know the attributes it
encodes, certi¬cate holders can enjoy even greater privacy.

The case of RSAREP-based scheme I or II or the immunization in Section 4.4.1
To encode attributes x 1 , . . . , xl ∈ Zv into a certi¬ed key pair for P, the CA and P
engage in RSAREP-based scheme I or II or their immunization described in Sec-
tion 4.4.1. P obtains a certi¬cate of the CA on a public key h of the form
g1 1 · · · gl l ±v ,
x x
1

where ±1 ∈ Zn is a random number chosen by P, playing the same dual role as in
the case of the DLREP-based schemes. The rest is clear.

The case of the immunized RSAREP-based scheme II in Section 4.4.2
Finally, in the second immunization of RSAREP-based scheme II, described in Sec-
tion 4.4.2, P obtains a certi¬cate on a public key h of the form
g1 1 β · · · gl l β hβ ±v .
x x
01

In the showing protocol, P must demonstrate that β = 0 mod v. If β = 0 mod v,
then the RSA-representation P knows of h ’1 with respect to ((h )’1 , g1 , . . . , gl , v)
0
is
(e mod v, x1 , . . . , xl , z),
184 COMBINING ISSUING AND SHOWING PROTOCOLS


where e, f ∈ Z satisfy eβ +f v = 1, and z is the product of ± e and the powers of l+2
1
junk factors resulting from normalization. It is easy to see that proving knowledge
of an RSA-representation of h ’1 with respect to ((h )’1 , g1 , . . . , gl , v) suf¬ces to
0
demonstrate β = 0 mod v; this is a simple application of the technique described in
Section 3.4.2. Therefore, according to the equivalent of Proposition 3.6.1(b) for the
RSAREP function, P demonstrates β = 0 mod v as a by-product of demonstrating
any Boolean formula for the RSA-representation it knows of h ’1 with respect to
0
((h )’1 , g1 , . . . , gl , v). Alternatively, and more ef¬ciently, P simply demonstrates
that β = 1 mod v as part of the formula it is demonstrating; there is no need to hide
β.

Remarks
In many PKIs, only the ability to demonstrate Boolean formulae involving the at-
tributes (i.e., not the more general form of linear relations) is required. In these PKIs
the CA can encode attributes that contain more than |q| or |v| bits of information,
such as digitally encoded photographs. Consider by way of example a certi¬cate on
a DLREP-based public key of the form
Fq,gl (x1 ) Fq,g (xl’1 ) xl
· · · gl’1 l
g1 gl .

Assuming that Fq,gl (·) is a collision-intractable hash function with outputs smaller
than q, P can demonstrate that x i = β, for some β ∈ N, by demonstrating that
Fq,gl (xi ) = Fq,gl (β). Likewise, demonstrating that x i = β can be done by demon-
strating that Fq,gl (xi ) = Fq,gl (β). The usefulness of this variation is limited if the
CA sees the attributes it encodes, because attributes with large entropy are in effect
identi¬ers that facilitate tracing and linking when disclosed; however, as we will
show in Section 5.2.1, the CA can encode attributes without knowing their values.
In another variation, following Merkle [267] (see also Section 5.4.3), attributes
are incorporated in a hash tree. For example, with x 2 chosen at random from Z q ,
xx
the number x1 in g1 1 g2 2 , could be the root of a Merkle hash tree. To reveal some
of the attributes in the tree, P discloses node values from which the root value can
be reconstructed. This approach improves ef¬ciency (and enables limited selective
disclosure, assuming P hashes along a random salt for each attribute to prevent an
exhaustive search), but many of the techniques in this book no longer apply.
For ef¬ciency reasons, in practice V 0 may prefer to skip the veri¬cation of P 0 ™s
response(s) in the issuing protocol. P0 cannot leak more than a single bit of informa-
tion to V, owing to V0 ™s blinding operations. Because V cannot determine whether
P0 or V0 is the source of incorrect certi¬cate data supplied in the showing protocol,
it has no choice but to reject incorrect data. Therefore, if P 0 ™s response in the issuing
protocol is incorrect then V 0 will ¬nd out in the showing protocol.
From now on we will always assume that the public key h of the certi¬cate
holder is hashed along when determining V™s challenge c in a signed proof.
5.1 INTEGRATION 185


5.1.2 Coping with delegation
As noted in Section 2.6, care must be taken when the CA issues secret-key certi¬-
cates. P may be able to use a simulated certi¬ed public key in the showing protocol
and delegate part of the requested action to the CA in an execution of the issuing
protocol.

Example 5.1.2. Consider the immunized DLREP-based certi¬cate scheme I in Sec-
tion 4.4.2. To simulate a certi¬ed public key, P generates a number β ∈ Z q , sets
β
h := g0 , and computes a corresponding certi¬cate. To issue a signed proof of the
formula TRUE, say, P must be able to come up with a ∈ G q and r1 , . . . , rl+1 ∈ Zq
such that
l
r
and c = Hq,gl (h , a, . . .).
r
gi i h0l+1 = (h )c a
i=1

Hereto P engages in an execution of the certi¬cate issuing protocol with the CA, in
the following manner. Upon receiving a 0 , P sets a := a0 , c := Hq,gl (h , a, . . .),
and sends the challenge c 0 := ’βc mod q to the CA. Upon receiving r 0 from the
CA, P sets ri := xi r0 mod q, for all i ∈ {1, . . . , l}, and rl+1 := r0 . (Additional
blinding operations can be applied to a, c 0 , and r0 , . . . , rl+1 .) It is easy to verify that
the result convinces V. Note that this works also if the hash function in the showing
protocol is different from that used in the issuing protocol.

The delegation strategy in this example is without security consequences, be-
cause P demonstrates a formula that pertains to the attributes (x 1 , . . . , xl ) that the
CA “encodes” in the protocol execution to which P delegates the cryptographic ac-
tion. In effect, P simply follows a shortcut that circumvents the need to compute a
as a product of powers of g 1 , . . . , gl , h0 . In most circumstances this shortcut is not
preferable: it requires an online connection with the CA at the time of the showing
protocol execution; simulated certi¬ed public keys cannot be reused; and, for inter-
active showing protocols, timing of issuing and showing protocol executions would
reveal the link between them.
When using the certi¬cate issuing protocol in Section 4.5.2, the possibility of del-
egation simply does not arise, because public-key certi¬cates are issued. Whenever
delegation is harmless, though, there is no reason to prefer public-key certi¬cates. In
fact, secret-key certi¬cates are preferable for reason of their greater ef¬ciency, prov-
able security, and privacy. (The privacy bene¬ts will be clari¬ed in Section 5.2.2.)
In the remainder of this section we examine for all the secret-key certi¬cate issuing
protocols in Chapter 4 whether P can abuse delegation to demonstrate a formula that
does not apply to the attributes that the CA encodes in the issuing protocol execution
with P. We will show that in many situations the delegation strategy is not possi-
ble at all, and in those cases where it cannot be prevented it can easily be rendered
harmless.
186 COMBINING ISSUING AND SHOWING PROTOCOLS


The case of the four issuing schemes in Section 4.2
Assumption 5.1.3. For any of the four secret-key certi¬cate schemes in Section 4.2,
if V accepts a formula demonstration by P, then P must have engaged in an issu-
ing protocol execution in which the CA encoded an attribute tuple that satis¬es the
formula.
In other words, delegation may be feasible, but it does not enable P to pretend to
have attributes for which it cannot (at the same moment) obtain a certi¬cate from the
CA. We now argue why this should be true.
Consider ¬rst DLREP-based certi¬cate scheme I in Section 4.2.1. According to
the DL-based analogue to Assumption 4.3.9, the only way to simulate a certi¬ed pub-
lic key is to set h := h’1 g0 , for some β ∈ Zq . Assume for the moment that the CA
β
0
uses the same attribute tuple (x 1 , . . . , xl ) in all protocol executions. In the same man-
ner as in Proposition 4.3.10, the role of the CA in these protocol executions with P
can be simulated by generating a random γ ∈ Z q and setting h0 := h’1 g0 , on input γ

l+1 random numbers g 0 , . . . , gl ∈ Gq . Now, the demonstration of a Boolean formula
by means of the showing protocol techniques of Chapter 3 is a proof of knowledge
of a DL-representation (y 0 , . . . , yl ) of h with respect to (g0 , g1 , . . . , gl ); see Propo-
sition 3.6.1(b). (For signed proofs, the validity of Proposition 3.6.1(b) follows from
the DL-based analogue to Assumption 4.3.9.) From the four relations
= g1 1 · · · gl l
x x
h
= h’1 g0
β
h 0
= h’1 g0
γ
h0
yy y
= g0 0 g1 1 · · · gl l ,
h
we get
g0 g1 1 ’y1 · · · gl l ’yl = 1.
β’γ x x

Thus, a polynomial-time collision-¬nding algorithm for the DLREP function can
be constructed, unless β = γ mod q and y i = xi mod q, for all i ∈ {1, . . . , l}.
Therefore, any choice for β should result in P demonstrating a property for a DL-
representation
(β ’ γ mod q, x1 , . . . , xl )
of h with respect to (g0 , g1 , . . . , gl ). This is the same as what P can demonstrate by
simply following the issuing and the showing protocol.
When issuing protocol executions are run with respect to different attribute tuples,
the CA can no longer be simulated by setting h 0 := h’1 g0 . However, the fact
γ

that these protocol executions cannot be run in parallel is believed to ensure that the
security argument remains valid; the situation is reminiscent of that in Section 4.3.3.
The security argument can be easily generalized to the scenario considered by
Proposition 4.3.15, which provides a limited degree of parallelization of protocol
executions with respect to different attribute tuples.
5.1 INTEGRATION 187


Interestingly, DLREP-based certi¬cate scheme I seems to admit delegation only
when the challenge c 0 in the veri¬cation relation of the issuing protocol appears at the
same position as V™s challenge c in the veri¬cation relation of the showing protocol.
In particular, delegation is believed to be infeasible for atomic formulae without a
“NOT” connective: the veri¬cation relations for these formulae have V™s challenge
situated as an exponent of the “wrong” base number.
The same considerations apply to the other three secret-key certi¬cate schemes
in Section 4.2.

The case of the immunized DLREP-based scheme I in Section 4.4.2
In case all protocol executions involve the same attribute tuple, the security argument
for DLREP-based scheme I this time results in the relation
g0 0 γ g1 0 x1 ’y1 · · · gl 0 xl ’yl = 1.
β’y y y


Consequently, any choice for β should result in P demonstrating a property for a
DL-representation
((β/γ)x1 mod q, . . . , (β/γ)xl mod q, β/γ mod q)
of h with respect to (g1 , . . . , gl , h0 ); this is the same as what P can demonstrate by
simply following the issuing and the showing protocol. On the basis of this, it seems
that any delegation strategy with undesirable security consequences must exploit the
ability of P to engage in parallel in two (or more) issuing protocol executions with
respect to distinct attribute tuples.
Consider now the following parallel delegation strategy, involving two parallel
issuing protocol executions with respect to different tuples. The veri¬cation relation
in the i-th issuing protocol execution, for i ∈ {0, 1}, is
g00i = (h0 g1 1i · · · gl li )r0i a0i .
c x x


P can combine the information obtained in the two issuing protocol executions into
information that satis¬es the combined veri¬cation relation
l
’(γ r +γ r ) γ ’(γ0 xi0 r00 +γ1 xi1 r01 )
h0 0 00 1 01 g0 0 c00 +γ1 c01 = aγ 0 aγ 1 ,
gi 00 01
i=1

for some γ0 , γ1 ∈ Zq of its own choice. According to the DL-based analogue to
β
Assumption 4.3.9, the only way to simulate a certi¬ed public key is to set h := g0 ,
for some β ∈ Zq . According to Figure 3.1, the veri¬cation relation in the showing
protocol for an atomic formula without a “NOT” connective is of the form
l
hr0 (g0 )’c
β r
gi i = a.
0
i=1
188 COMBINING ISSUING AND SHOWING PROTOCOLS


Consequently, P in the issuing protocol executions can choose c 00 and c01 subject
to γ0 c00 + γ1 c01 = ’βc mod q. With a := aγ0 aγ1 , P can use the responses in
00 01
the two issuing protocol executions to satisfy the veri¬cation relation in the show-
ing protocol, by setting r 0 := ’(γ0 r00 + γ1 r01 ) mod q and, for all i ∈ {1, . . . , l},
ri := ’(γ0 xi0 r00 + γ1 xi1 r01 ) mod q. Now, if the showing protocol execution is
to demonstrate the formula TRUE, P does not gain anything by this strategy. For
any other atomic formula without a “NOT” connective, the responses r 1 , . . . , rl must
satisfy at least one linear relation. Since the responses r 00 , r01 are outside of P™s
control, in the sense that they should be as unpredictable as two independent random
variables, P can satisfy this linear relation only if it may select the formula coef¬-
cients by itself. In that case, the parallel delegation strategy enables P to pretend to
have certi¬ed attributes that it in fact has never been issued.
Either of the following two measures is believed to suf¬ce to make the parallel
delegation strategy harmless:

• A description of the formula F is hashed along when forming V™s challenge
in the showing protocol. With c = H q,gl (g0 , aγ0 aγ1 , F, . . .), it should be in-
β
00 01
feasible to determine c as an algebraic function of β, γ 0 , γ1 and the formula
coef¬cients. (This is provably true in the random oracle model.) Therefore, it
seems that P, upon receiving (a 00 , a01 ), has no choice but to select (β, γ 0 , γ1 )
and the formula coef¬cients before forming c. The rest of the security argu-
ment is similar to that in Section 4.4.2 for the restrictive blinding property of
the immunized DLREP-based scheme I; the only workable choices seem to be
those that result in formulae that P can demonstrate by following the issuing
and showing protocols.

• All the matrix entries (coef¬cients) that specify the Boolean formulae are re-
stricted to sets V such that |V |/q is negligible in k. (The set V may differ
for each formula coef¬cient.) The idea is that it should be infeasible to come
up with (β, γ0 , γ1 ) and admissible formula coef¬cients (favorable to P) that
satisfy the linear relations. (Note that c = H q,gl (g0 , aγ0 aγ1 , . . .) must be sat-
β
00 01
is¬ed as well.) For security reasons, it is recommendable to apply this measure
in combination with the preceding measure.

These measures were also recommended in Chapter 3 to guarantee unmodi¬ability
of signed proofs for atomic formulae without a “NOT” connective. (Recall, though,
that they are not always necessary to guarantee unforgeability of signed proofs.)
For atomic formulae that contain one “NOT” connective, the delegation strat-
egy (be it the sequential or the parallel variant) is believed to be infeasible alto-
gether, without any additional measures; V™s challenge in the veri¬cation relations
for these formulae is an exponent of the wrong base numbers. As we have seen in
Section 5.1.1, in the showing protocol P must demonstrate anyway that ± 1 = 0; in
case it does so as part of the formula that it is demonstrating to V, the whole formula
5.2 PRIVACY IMPROVEMENTS FOR CERTIFICATE HOLDERS 189


demonstration will always include a “NOT” connective. In other words, the issue
of delegation can be circumvented altogether by requiring that P always demon-
strate Boolean formulae for the DL-representation it knows of h ’1 with respect to
0
(g1 , . . . , gl , h ), rather than having V check that h = 1 and having P demonstrate
formulae without “NOT” connectives.


The case of the remaining secret-key certi¬cate schemes
The observations with respect to the immunized DLREP-based scheme I in Sec-
tion 4.4.2 apply also to the immunized RSAREP-based scheme II in Section 4.4.2
and to the DSA-like scheme in Section 4.5.1.
Finally, in the case of the immunized issuing protocols described in Section 4.4.1,
the application of the function f (·) to the CA™s initial witness in the issuing protocol
is believed to make the delegation infeasible altogether.


5.2 Privacy improvements for certi¬cate holders
In this section we describe various techniques to improve privacy for certi¬cate hold-
ers.


5.2.1 Issuing protocol techniques
Users are free to obtain a single batch of certi¬cates from the CA and to thereafter
never again retrieve new ones. In effect, a certi¬ed public key is a digital pseudonym.
All communications and transactions conducted using the same pseudonym are link-
able. In applications such as online discussion groups, this allows certi¬cate holders
to build a reputation with respect to each of their pseudonyms. For reason of pri-
vacy, however, it will often be desirable to use each certi¬cate only a limited number
of times. In applications where there is no need to build a reputation, single use is
optimal. It also has advantages in other respects, as we have seen in Section 1.1.
Issuing many certi¬cates to each applicant does not signi¬cantly raise the burden
for the CA, if only identi¬ers and other attributes need not be veri¬ed out-of-band
each time. The following two methods facilitate the recurring issuance of certi¬cates
to the same certi¬cate applicant:

• (Account-based method) The certi¬cate applicant opens an account with the
CA, and registers under a person identi¬er (see Section 1.1.2) or a pseudonym.
The account holder uses an account key (or, if a digital pseudonym is used, the
secret key of the pseudonym) to authenticate its requests for new certi¬cates.
Standard authentication techniques can protect against replay and, if desired,
ensure non-repudiation.
190 COMBINING ISSUING AND SHOWING PROTOCOLS


If the attributes of each account holder are recorded in a database entry as-
sociated with the account, then the CA need not verify them more than once.
Account holders can minimize the information the CA can learn about their
certi¬cate showing behavior by retrieving certi¬cates in batches.
• (Account-less method) The certi¬cate holder proves the right to retrieve new
certi¬cates by showing to the CA a previously retrieved certi¬cate (not nec-
essarily of the same type or issued by the same CA). In this manner, the CA
can be assured of the authenticity of relevant attributes (identity or otherwise)
without needing to keep an account database.
This model does away with the account database by having each user port his
or her own database entries, digitally certi¬ed by the CA for security. At the
very least, the account-less method is natural for refreshing previously issued
certi¬cates. More generally, it ¬ts well with the philosophy behind digital
certi¬cates to minimize the reliance on central databases; see Section 1.1.3.
In many PKIs it is more ef¬cient to issue many short-lived certi¬cates than to issue
a few long-lived certi¬cates and apply online certi¬cate validation. By front-loading
the handling of certi¬cates and issuing certi¬cates in batches, the CA greatly reduces
the number of accesses to a central database. Also, certi¬cate issuing can easily be
scheduled, and in case of a communication or computation fault the same actions
can be repeated until successful. Note that even in a PKI with long-lived certi¬cates,
the CA must be prepared to reissue certi¬cates; certi¬cates may be lost, stolen, or
corrupted, and must be refreshed upon expiry.
The account-based method allows certi¬cate holders to remain anonymous in
the issuing protocol, by registering under a pseudonym and using an anonymous
channel to retrieve certi¬cates. Unlinkability of certi¬cate retrievals can be achieved
by opening multiple anonymous accounts. Full unlinkability, however, is feasible
only when using the account-less approach. Hereto certi¬cate applicants must be able
to obtain attribute certi¬cates that can be used to authenticate their right to retrieve
new certi¬cates.
The account-less approach also enables a certi¬cate holder to anonymously have
a previously issued certi¬cate recerti¬ed by the CA. Anonymous refreshing of a
certi¬cate can be accomplished using any of the RSAREP-based certi¬cate issuing
schemes or the DLREP-based scheme described in Section 4.5.2. Suppose in the
DLREP-based scheme that the CA is presented with h := (g1 1 · · · gl l h0 )±1 , a cer-
x x

ti¬cate on h , and (optionally) a signed proof (or another kind of proof) that discloses
some property of the attributes (to enable P 0 to certify unknown attributes that it
knows satisfy a certain property) or at least authenticates the request. If the CA
agrees to use h in the new issuing protocol execution (in the role of h 0 h), the certi¬-
cate holder can obtain a certi¬cate on (h )β = (h0 h)±1 β , for a random β = 0 mod q.
The associativity of raising numbers in G q to a power ensures that the encoded at-
tributes remain intact. Note that different CAs, each with their own signing key, can
5.2 PRIVACY IMPROVEMENTS FOR CERTIFICATE HOLDERS 191


perform different recerti¬cation stages, assuming they all operate in the same group
Gq .
The CA can update the attributes of anonymous certi¬cate holders before recerti-
fying them, without knowing the current attribute values. Consider hereto RSAREP-
based scheme I. V 0 receives a certi¬cate on a public key h of the form g 1 1 . . . gl l ±v ,
x
x
1

for a random ± 1 ∈ Zn . Before recerti¬cation, the CA multiplies h by i=1 gi ,
l ui

where u1 , . . . , ul ∈ Zv represent the update values. This technique applies also to
RSAREP-based scheme II and the immunized RSAREP-based schemes described in
Section 4.4. The updating technique does not work when a hash function F (·) is
applied to the attributes (as described at the end of Section 5.1.1), and does not work
for the DLREP-based schemes.
A special application of anonymous updating is to prevent the CA from learning
the entire set of attributes of a certi¬cate applicant. Attributes that can be assigned to
a certi¬cate applicant without requiring the applicant to disclose his or her identity
can be encoded in successive anonymous executions of the issuing protocol, in each
of which the certi¬cate issued in the previous protocol execution is updated. To
prevent linking by timing, there must be ample time between successive updates.
Having different CAs certify different attributes further improves privacy.


5.2.2 Showing protocol techniques
To limit the privacy-invading powers of parties who build pro¬les from lists of cer-
ti¬ed public keys (obtained from certi¬cate repositories or compiled by monitoring
network traf¬c), one can use secret-key certi¬cates and have certi¬cate holders per-
form only zero-knowledge proofs. In this manner, nobody is able to obtain digitally
signed evidence about the attributes of PKI participants.
Secret-key certi¬cates can also reduce the scope for discrimination on the basis
of (the lack of) one™s right to participate in a PKI. Certi¬ed public keys obtained from
a CA in one PKI can be combined with simulated certi¬ed public keys for other PKIs
in an execution of the showing protocol, to prove knowledge of a secret key (more
generally, an attribute property) for at least one of the certi¬ed public keys; the “OR”
technique of Cramer, Damg˚ rd, and Schoenmakers [123] applies straightforwardly
a
to our showing protocol techniques.
Instead of performing a zero-knowledge proof or issuing a signed proof, P in
the showing protocol can also issue a designated-veri¬er proof. This notion, due to
Chaum [102], guarantees that P™s proof is convincing only to a designated veri¬er;
this reduces the scope for privacy-invasive practices. (See Jakobsson, Sako, and Im-
pagliazzo [219] and Krawczyk and Rabin [241] for improved constructions.) The
idea is for P to perform its demonstration by proving knowledge of a secret key cor-
responding to its own public key or to one of the designated veri¬er, using a witness-
indistinguishable proof of knowledge. Hereto our showing protocol techniques can
be straightforwardly combined with the “OR” technique of Cramer, Damg˚ rd, and a
192 COMBINING ISSUING AND SHOWING PROTOCOLS


Schoenmakers [123]. The resulting protocol transcript does not convince anyone
but the veri¬er, because the veri¬er can generate transcripts with indistinguishable
probability distribution. An inherent drawback of designated-veri¬er proofs is that
V must be prevented from using a secret key that is known only to a group of ver-
i¬ers. To overcome this attack, veri¬ers must either make a physical appearance in
a Faraday cage (to have their public key certi¬ed) or a trusted party must securely
issue a secret key to each veri¬er (e.g., by providing a smartcard that stores the key);
both approaches have obvious drawbacks. In most PKIs either a signed proof or a
zero-knowledge proof will be the preferred choice.
Our showing protocol techniques enable certi¬cate holders to demonstrate prop-
erties of attributes that have been encoded into different certi¬ed key pairs. Limiting
the number of attributes per certi¬cate reduces the need to have attributes recerti¬ed
(attributes with clearly distinct lifetimes can be encoded into different certi¬ed key
pairs), improves ef¬ciency, 1 and improves privacy when attributes are certi¬ed by
different CAs. Any Boolean formula pertaining to the attributes in an arbitrary num-
ber of certi¬ed public keys can be demonstrated by applying our showing protocol
techniques to the appropriate product of powers of the public keys, provided that
the attributes speci¬ed in atomic formulae are all exponents of the same generator.
x—
For example, in the DLREP-based setting, with h = l gi i and h— = l gi i ,
x
i=1 i=1
demonstrating that ± 1 x1 + x— = ±2 mod q, say, can be done by proving knowledge
1
’±
of a DL-representation of h ±1 h— g1 2 with respect to (g2 , . . . , gl ). Depending on the
certi¬cate issuing scheme, for each public key an additional proof of knowledge of a
representation may need to be performed, for security reasons. To prove knowledge
of a representation of each of many public keys h 1 , . . . , ht , knowledge of a represen-
t
tation of the product h 1 i=2 h±i may be proved, for ± 2 , . . . , ±t generated at random
i
from a large set. Either the ± i ™s are generated by application of a suf¬ciently strong
one-way hash function to h 1 , . . . , ht and the initial witness of the prover, or the pro-
tocol is performed interactively and V generates the ± i ™s at random after receiving
the initial witness.
This technique can be applied not only by a single certi¬cate holder, but also
by multiple certi¬cate holders who wish to jointly demonstrate that their combined
attributes meet certain criteria, without pooling their attributes. It can even be applied
to certi¬cates issued by different CAs, assuming all CAs operate in the same group;
in DLREP-based scheme I, for instance, each CA may have its own x 0 , but Gq and
at least some of the generators should be the same.
The technique is less practical when P is to demonstrate a formula that involves
attributes that are exponents of different g i ™s in different certi¬ed key pairs. Auxiliary

1 Attributes that are rarely shown in combination are best encoded into different certi¬ed key pairs.
Other approaches to shorten certi¬cates include: use of elliptic curve implementations, removing infor-
mation from certi¬cates, using better data encoding rules, and ensuring that certi¬cate veri¬ers can derive
the certi¬cate holder™s public key from its identi¬er and the CA™s public key (Certicom™s applies this
approach in its “bullet” certi¬cates).
5.3 PRIVACY IMPROVEMENTS FOR CERTIFICATE VERIFIERS 193


commitments must then be spawned and additional relations must be proved, much
as described in Section 3.7. In many PKIs, though, only the ability to demonstrate
Boolean formulae involving the attributes (i.e., not the more general form of linear
relations) is of interest; for these formulae, our showing protocol techniques readily
apply to the attributes encoded into (arbitrarily many) different certi¬ed key pairs.
In some PKIs it is desirable that certi¬cate holders can anonymously prove to be
the originator of several showing protocol executions. This gives them the power to
control the degree to which their communications and transactions can be linked. If
the CA encodes into each certi¬ed key pair an attribute x 1 (possibly a random num-
x
ber) that is unique to the certi¬cate applicant (applicants may provide g 1 1 or other
suitable commitments to hide their x 1 from the CA), certi¬cate holders can provide
indisputable linking information for arbitrarily many public keys, h 1 , . . . , ht , as fol-
lows. After the initial witnesses have been ¬xed, V generates t numbers, ± 1 , . . . , ±t ,
at random from a set V ⊆ Z q , subject to the condition i=1 ±i = 0 mod q. It is
t

easy to show that if P can prove knowledge of a representation of t h±i with i=1 i
respect to a tuple that does not contain g 1 , then the probability of successful cheating
is at most 1/|V |. The ±i ™s may be generated as the output of a suf¬ciently strong
one-way hash function to P™s initial witnesses. The same technique applies to the
RSAREP-based protocols.
A special application of the latter technique are credential systems in which cer-
ti¬cate holders are to build pseudonymous reputations in the showing protocol. Using
our techniques, certi¬cate holders can establish digital pseudonyms with organiza-
tions; the pseudonyms can be thought of as anonymous accounts. To ensure that
certi¬cates can be shown only to organizations at which one has a pseudonym, we
have the CA (or different CAs) encode a key holder identi¬er (e.g., a random number)

into each pseudonym and attribute certi¬cate. With h = g 1 g0 , say, denoting a per-

son™s pseudonym at an organization, and h — = g1
l xi
I
i=2 gi an attribute certi¬cate,
Boolean formulae of h — /h with respect to tuples in which g 1 does not appear can be
demonstrated only if I = I — mod q. Separate proofs of knowledge of a representa-
tion of h— and h may be needed; for h this would naturally be done when registering
or when using the pseudonym with the organization.
Using our techniques it is also straightforward for several certi¬cate holders to
jointly demonstrate that their showing protocol executions did not all originate from
the same certi¬cate holder, or for one certi¬cate holder to show that he or she was
not involved in a fraudulent transaction; see Section 5.5.1 for details on the latter.


5.3 Privacy improvements for certi¬cate veri¬ers
In many PKIs, certi¬cate veri¬ers (must) submit their showing protocol transcripts to
the CA (or another central authority), either online or off-line. This enables the CA to
detect fraud with limited-show certi¬cates, to keep track of the number of customers
194 COMBINING ISSUING AND SHOWING PROTOCOLS


served by V, to gather statistics on how often a certain attribute property is disclosed,
or to perform other administrative tasks.
For competitive or other reasons, V may want to hide from the CA all or part
of the formulae demonstrated. On the other hand, with the possible exception of
closed PKIs in which veri¬ers are tamper-resistant terminals representing the security
interests of the CA, the CA is unlikely to trust veri¬ers with truthfully submitting
summary indications of the required information. That is, V should not be able to
provide false information to the CA.
As an example application, consider an untraceable electronic coin system with
“earmarks.” Each electronic coin is a certi¬ed key pair encoding an attribute x 1 that
speci¬es (at least) the expiry date and the denomination of the coin, and attributes
x2 , . . . , xl that specify personal data (such as age, gender, hobbies, income, marital
status, and perhaps the identity of the coin holder). To make a payment, the payer
discloses x1 to the shop. Depending on the conditions, the payer may in addition de-
cide to disclose some of x 2 , . . . , xl , for example to get a discount. To get its account
credited, the shop deposits the coin to the bank. The shop is required to deposit a
signed proof (to enable the bank to detect and trace double-spending) that discloses
x1 (to enable the bank to determine the redeemable amount), but the personal data
that the shop acquired from the payer is none of the bank™s business.
We now show how V can obtain a signed proof that hides all or part of the formula
demonstrated by P, while V itself becomes convinced of the entire formula.
Consider ¬rst the case in which P interactively demonstrates to V an atomic for-
mula F of the form (3.2), in the manner depicted in Figure 3.1 and subject to the con-
ditions of Proposition 3.3.7. Let F — be any atomic formula obtained from F by prun-
ing “AND” connectives from F (i.e., by deleting rows from the left-hand side matrix
in (3.2)). We claim that V can obtain a signed proof that serves as self-authenticating
evidence that F — applies to P™s DL-representation but that unconditionally hides all
other information about F . The basic idea is for V to hash along a description of F —
instead of F when determining c, and to make it appear as if some of r l’t+1 , . . . , rl
were provided by P. For instance, the signed proof (c, (r 1 , . . . , rl’t+1 )) corresponds
to the formula F — that is the result of deleting the ¬rst row of the left-hand side matrix
in (3.2), assuming that a description of F — is hashed along instead of F when form-
ing c. This signed proof does not unconditionally hide all other information about
F , though, because r l+1 does not have an independent random distribution; for any
choice of l ’ t elements of the tuple (b 1 , ±11 , . . . , ±1,l’t ), the remaining element is
uniquely de¬ned. To take care of this aspect, V must randomize r l’t+1 by adding
a random element β ∈ Z q ; this must be compensated by hashing along ag π(l’t+1) β

instead of a when forming c.
More generally, with P demonstrating to V a formula F of the form (3.2), the
following protocol steps result:

Step 1. (This step is identical to Step 1 of the protocol in Section 3.3.) P generates
5.3 PRIVACY IMPROVEMENTS FOR CERTIFICATE VERIFIERS 195


at random l ’ t numbers, w 1 , . . . , wl’t ∈ Zq , and computes
l’t t l’t
’ ±ij wj
wi j=1
a := gπ(i) gπ(l’t+i) .
i=1 i=1

P then sends the initial witness a to V.
Step 2. V decides on F — by deleting rows from the left-hand side matrix in (3.2).
Without loss of generality, we assume that F — is the result of pruning the ¬rst
t— ¤ t rows.
V generates at random t — blinding factors β 1 , . . . , βt— ∈ Zq , and computes
t—
a— := a i=1 gπ(l’t+i) . V then forms c := Hq,gl (h, m, F — , a— ), for some
βi

(optional) message m, and sends c to P.
Step 3. (This step is identical to Step 2 of the protocol in Section 3.3.) P computes
a set of responses, responsive to V™s challenge c ∈ Z s , as follows:

∀i ∈ {1, . . . , l ’ t}.
ri := cxπ(i) + wi mod q

P then sends (r1 , . . . , rl’t ) to V.
As in the protocol in Section 3.3, V computes
l’t
rl’t+i := bi c ’ ∀i ∈ {1, . . . , t},
±ij rj mod q
j=1

and accepts the demonstration of F if and only if the veri¬cation relation
l
gπ(i) h’c = a
ri

i=1

holds. If V accepts, it computes r l’t+i := rl’t+i +βi mod q, for all i ∈ {1, . . . , t— },


and outputs the signed proof
— —
c, rπ’1 (1) , . . . , rπ’1 (l’t) , rπ’1 (l’t+1) , . . . , rπ’1 (l’t+t— ) .

The CA (or anyone else) accepts the signed proof if and only if
t—
l’t —
rπ’1 (i)
r ’1

gl’t+i h’c ).
c = Hq,gl (h, m, F , gi π (i)
i=1 i=1

Note that if t— = t then the signed proof hides F in its entirety.
According to Proposition 3.6.3, if V™s challenge is formed by hashing at least h,
any initial witnesses, and a unique description of a formula F , then a signed proof
196 COMBINING ISSUING AND SHOWING PROTOCOLS


serves as self-authenticating evidence that P knows (knew) a representation of h, and
that P™s representation satis¬es the formula F . It follows that V can hide an arbitrary
part of the formula demonstrated, but cannot obtain a signed proof for a formula that
does not apply to P™s representation: F — is implied by the formula F demonstrated
by P in the showing protocol execution from which the signed proof resulted.
The same technique applies to atomic formulae of the form (3.4). Peculiarly,
though, V can only obtain signed proofs for formulae F — obtained by pruning linear
equalities from F — ; it is unclear how to prune the linear inequality.
More generally, if P interactively demonstrates an arbitrary formula F of the
form (3.7), then V can obtain a signed proof for any formula that is obtained by
pruning one or more of the j subformulae of F . Hereto V simply omits hashing
along the initial witness sets for those subformulae when forming c.
In sum, when P is interactively demonstrating to V a formula F of the form (3.7),
V can obtain a signed proof for any formula F — that is obtained from the formula F
demonstrated by P by pruning “AND” connectives. The signed proof uncondition-
ally hides all other information about F . How much V may hide in the signed proof
it deposits to the CA could depend on the policies set by the latter.
In case P wants to prevent V from obtaining a signed proof for a formula other
than the formula F it is demonstrating to V, it must form c itself by hashing along
a description of F . More generally, P can ensure that V obtains a signed proof
that convinces of a formula F — obtained from F by pruning “AND” connectives by
hashing along a description of F — itself (and possibly a — instead of a, for blinding
factors supplied by V).
In case of disputes, it may be desirable that V can “open up” the signed proof
to prove that P demonstrated F , not just F — . Hereto V should form c by hashing
along a commitment to (the hidden part of) F , and save the blinding factors it used in
Step 2 (in order to reconstruct those responses of P that it blinded). P has leverage
to settle disputes as well: it can always prove to the CA to be the originator of the
signed proof, by revealing h and proving knowledge of a corresponding secret key.
An ef¬ciency improvement is possible in case P demonstrates a formula F of
the form (3.6) containing only atomic subformulae of the form (3.2), and V wants to
obtain a signed proof that hides F entirely. Let s := q. With i=1 gπ(i) h’ct = at
l rit

denoting the veri¬cation relation for the t-th atomic subformula, for t ∈ {1, . . . , j},
we have
l t
t
rij
’c
j=1
gπ(i) h = ai .
i=1 i=1

Consequently, c together with the responses in this compound veri¬cation relation
form a signed proof for the formula TRUE. V must hash along a := t ai (instead
i=1
of all ai ™s) and a description of the formula TRUE when determining c. There is no
need for blinding factors or interaction.
Our techniques thus far do not enable V to obtain a signed proof for any formula
5.4 LIMITED-SHOW CERTIFICATES 197


F — implied by F . To get around this limitation, P should submit two proofs to V:
a signed proof that discloses the minimal information required by the CA (perhaps
just the formula TRUE) and a proof (not necessarily a signed proof) that discloses
the formula V is interested in. A drawback of this approach is increased computation
and communication complexity.
All the techniques in this section apply straightforwardly to the RSAREP-based
showing protocols.


5.4 Limited-show certi¬cates
In this section we show how to ensure that the CA (or another central party to which
showing protocol transcripts are submitted) can compute all the attributes encoded
into a certi¬ed key pair once the certi¬cate is shown more than a predetermined
number of times. Bene¬ts of this technique will be explained in Section 5.5.

5.4.1 Static one-show certi¬cates
Consider the setting in Chapter 3. Suppose that P engages in a showing protocol
execution, demonstrating a Boolean formula F for its DL-representation of h with
respect to (g1 , . . . , gl ). We do not care whether P gives a signed proof, a zero-
knowledge proof, or otherwise. We claim the following.

Proposition 5.4.1. Suppose that formulae are demonstrated using the showing pro-
tocol described in Section 3.6.1. If P demonstrates the same formula twice using the
same public key, responsive to any two different challenges of V but with respect to
the same initial witness (sets), then with overwhelming probability P™s secret key can
be ef¬ciently computed from the two accepting views of V.

Proof. To prove the claim, we consider the following four cases for the formula F
that is demonstrated:

Case 1. F is an atomic formula consisting of zero or more “AND” connectives and
no other connectives, in the form (3.3). Recall from Figure 3.1 that the veri¬-
cation relation in the protocol for demonstrating F is
l
gπ(i) h’c = a,
ri

i=1

where a is the initial witness. The veri¬cation relation with respect to a chal-
lenge c— = c mod s is
l
r— —
gπ(i) h’c = a.
i


i=1
198 COMBINING ISSUING AND SHOWING PROTOCOLS


Division of the two relations results in
r ’r —
r ’r —

hc’c = gπ(1) 1 · · · gπ(l) l ,
1 l




and from s ¤ q it follows that
(r ’rl )/(c’c— )

(r ’r1 )/(c’c— )

· · · gπ(l)
1 l
h = gπ(1) .

The DL-representation ((r 1 ’ r1 )/(c’ c—) mod q, . . . , (rl ’ rl )/(c’ c— ) mod
— —

q) can be ef¬ciently computed from the two views of V. With overwhelm-
ing probability, this DL-representation is P™s secret key, (x π(1) , . . . , xπ(l) ).
Namely, according to Corollary 3.3.2 P must know at least one secret key, and
if this is different then < P, V> is a collision-¬nding algorithm for the DLREP
function used to implement P™s commitment; according to Proposition 2.3.3
this contradicts the assumption that the underlying DL function is one-way.

Case 2. F is an atomic formula consisting of zero or more “AND” connectives, one
“NOT” connective, and no other connectives, in the form (3.4). Recall from
Figure 3.5 that the veri¬cation relation in the protocol for demonstrating F is

l
gπ(i) h’r0 = a.
ri

i=1

The veri¬cation relation with respect to a challenge c — = c mod s is

l
r— —
gπ(i) h’r0 = a.
i


i=1

Division of the two relations results in
r ’r —
r ’r —

hr0 ’r0 = gπ(1) 1 · · · gπ(l) l .
1 l





If r0 = r0 mod q, then
— —
(r1 ’ r1 mod q, . . . , rl ’ rl mod q)

is a DL-representation of 1 with respect to (g π(1) , . . . , gπ(l) ), and two cases
can be distinguished:

• If this is a non-trivial DL-representation of 1, then < P, V> has found a
DL-representation of 1 other than the trivial one. According to Proposi-
tion 2.3.3 this contradicts the assumption that the DL function is one-way.
5.4 LIMITED-SHOW CERTIFICATES 199


• If this is the trivial DL-representation, then r i = ri mod q for all i ∈
{1, . . . , l}. Recall that V computes (rl’t+1 , . . . , rl ) from (r0 , . . . , rl’t )
according to
l’t
rl’t+i := bi r0 ’ fi c ’ ∀i ∈ {1, . . . , t},
±ij rj mod q
j=1

where t ≥ 1. From the linearity of these t responses it follows that
fi (c ’ c— ) = 0 mod q, for all i ∈ {1, . . . , t}. From s ¤ q it follows
that c = c— mod q, and so f1 , . . . , ft are all zero. This contradicts the
presence of one “NOT” connective.

Therefore, with overwhelming probability r 0 = r0 mod q. It follows that
— — — —
((r1 ’ r1 )/(r0 ’ r0 ) mod q, . . . , (rl ’ rl )/(r0 ’ r0 ) mod q)

is a DL-representation of h with respect to (g π(1) , . . . , gπ(l) ). The same argu-
ment as in Case 1 completes the proof.

Case 3. F is a formula connecting atomic subformulae by zero or more “OR” con-
nectives and no other connectives, in the form (3.6). According to the protocol
j
in Section 3.5, V accepts if and only if c = i=1 ci mod s and the veri¬cation
relations for all the atomic subformulae hold. Let c — denote the challenge of V
in the second protocol execution involving the same initial witness (set), and
c— the challenge used by P for the i-th subformulae in that protocol execution.
i
We have t c— = c— mod s. From c— = c mod s it follows that there exists
i=0 i
at least one i such that c— = ci mod s. This index i corresponds to an atomic
i
subformula that P has demonstrated twice with respect to the same initial wit-
ness but different challenges. We are now in Case 1 or 2, and refer to these
cases for the completion of the proof.

Case 4. F is an arbitrary Boolean formula, in the form (3.7). According to the pro-
tocol in Section 3.6, V accepts if and only if it accepts P™s demonstration of
each of the j subformulae. We can therefore consider P™s demonstration of
any one of these subformulae, and apply the proof of Case 3.

This completes the proof.

The same result can be proved for the RSAREP-based showing protocols.
Based on Proposition 5.4.1 it is straightforward to construct a showing protocol
that protects P™s privacy if and only if P does not use the same certi¬ed public key
more than once. P must hereto commit already in the certi¬cate issuing protocol to
the initial witness (sets) that it will use in the showing protocol, so that the CA can
certify these along. Speci¬cally, for any of the restrictive blind certi¬cate issuing
200 COMBINING ISSUING AND SHOWING PROTOCOLS


protocols in Chapter 4, P (i.e., V 0 ) must hash along its initial witness (sets) for the
showing protocol when computing c 0 in Step 2 of the issuing protocol.
It is natural to think of h (or h , in the notation used in the issuing protocols in
Chapter 4) together with the initial witness (sets) of P as a one-time public key of
P. Any two showing protocol executions by P, with respect to the same one-time
public key but different challenges, reveal its secret key. In case P non-interactively
issues signed proofs, the use of different challenges can be forced by having P hash
along a unique message m when forming V™s challenge; if the hash function used to
form V™s challenge is collision-intractable, it is infeasible to compute two different
messages that are mapped to the same challenge, regardless of any additional inputs
to the hash function. Note that m need not be generated at random: Proposition 5.4.1
does not require V™s challenge to satisfy a particular probability distribution. In a
practical implementation, m could be the concatenation of an identi¬er for V (e.g., a
true name, a local name, a pseudonym, or a public key) and a nonce. 2
The limited-show technique applies even if the certi¬cate veri¬er uses the tech-
nique in Section 5.3 to hide (part of) the formulae demonstrated, regardless of the
strategy of P and V.
The proof of Proposition 5.4.1 makes use of the fact that < P, V> cannot com-
pute a collision for the DL function used to implement P™s commitment. When com-
bining the showing protocol with a certi¬cate issuing protocol, we must see to it that
this remains true. For the certi¬cate schemes in Section 4.2 and the immunization
in Section 4.4.1, P™s inability to learn a non-trivial representation of 1 follows from
Lemma 4.3.5. (Recall that we needed this property to prove blinding-invariance.)
For the public-key certi¬cate scheme in Section 4.5.2 the property follows from the
fact that the CA need not know a non-trivial DL-representation of 1 to perform the
issuing protocol. The other schemes in Chapter 4 are believed to meet the desired
property as well.
The delegation strategy is never an issue. P cannot use the delegation strategy to
show a number of certi¬cates that exceeds the number of issuing protocol executions
it would need to engage in; “forgery” is not possible. In fact, even if a secret-key cer-
ti¬cate issuing protocol is used that admits delegation, reuse of a simulated certi¬ed
public key is not possible because the CA uses an independent random initial witness
in each protocol execution.
The most obvious application of limited-show certi¬cates is to implement certi¬-
cates that by their very nature may be shown only a limited number of times, such
as food stamps, subway tokens, and electronic coins. In Section 5.5 we will see that
limited-show certi¬cates are advantageous also to prevent fraud with other types of
certi¬cates, such as personal certi¬cates.

nonce may be a sequence number, a random number provided by V, or a suf¬ciently accurate
2 The

estimate of the time and date of the demonstration; in the latter case the showing protocol can be non-
interactive, assuming P can determine the time without the assistance of V.
5.4 LIMITED-SHOW CERTIFICATES 201


In many PKIs, only one encoded attribute need be computable in case of fraud.
Of special interest is the case where one of the encoded attributes is an identi¬er
of P, which normally need not be shown but must be computable when a limited-
show certi¬cate is shown too many times. Instead of storing the entire protocol view,
in this case it is more ef¬cient to store those exponents that correspond, in the ex-
panded form of the veri¬cation relation, to h, g 1 , . . . , gl . For instance, to be able to
compute xπ(i) in case a formula of the form (3.3) is demonstrated twice, for some
i ∈ {1, . . . , l}, it suf¬ces to store (c, ri ) in each showing protocol execution. Accord-
ing to Subsections 2.2.2 and 2.2.3, 25-byte exponents suf¬ce for long-term security,
which makes our one-show certi¬cate technique highly practical.
In a typical PKI implementation, there will be many veri¬ers. To enable detec-
tion of reuse of a one-show certi¬cate, veri¬ers should deposit (relevant data of) the
transcripts of their showing protocol executions to the CA (or another central party),
in a timely fashion. (Either in real-time during certi¬cate validation or batched at
a convenient moment later on.) Veri¬ers that the CA trusts (such as tamper-proof
veri¬er devices issued by the CA) may accept zero-knowledge demonstrations and
deposit only the minimal data needed by the CA, but all others must receive and
deposit signed proofs on challenges for which a nonce has been hashed along. The
latter group of veri¬ers must be incited to perform the deposit. How to accomplish
this depends on the PKI at hand. Incentives may be either positive (e.g., a ¬nancial
reward for each deposited transcript) or negative (e.g., a penalty in case audits reveal
a discrepancy between the number of customers serviced and the number of tran-
scripts deposited). In some applications, it may be in the best interest of the veri¬ers
themselves to faithfully perform the deposit, for instance if a successful attack leads
to damages to their own organization.
By making use of its knowledge of y i = loggl gi , for all i ∈ {1, . . . , l ’ 1},
the CA can speed up the veri¬cation of transcripts of showing protocol executions.
Instead of verifying whether
l
gi i h’c = a,
r

i=1

say, the CA can simply verify whether
l’1
yi ri +rl ’c
gl i=1
h = a.

Also, the CA can apply batch-veri¬cation to verify one or multiple transcripts, as
described in Section 2.5.3.


5.4.2 Dynamic one-show certi¬cates
With the static one-show certi¬cate technique in Section 5.4.1, P must anticipate
in the certi¬cate issuing protocol which formula it will demonstrate in the showing
202 COMBINING ISSUING AND SHOWING PROTOCOLS


protocol. Depending on the application, this may or may not be a drawback. For
instance, the design of a privacy-protecting electronic coin system may be such that
each coin encodes two attributes, one to specify (at least) the coin expiry date and
the coin denomination and the other to specify the identity of the coin owner; the
formula for the showing protocol (payment) would always require the disclosure of
just the ¬rst attribute. In many PKIs, however, the requirement that the formula
must be anticipated is inconvenient or even unrealistic. Typically, the formula to be
demonstrated will depend on the veri¬er or its service, and P does not know in ad-
vance which service of which veri¬er it will want to get access to. In the case of
unlimited-show certi¬cates, P can postpone the moment of computing its initial wit-
ness (sets) until Step 1 of the showing protocol, but this cannot be accomplished for
limited-show certi¬cates. We now show how to get around this. Again, we assume
the setting of Chapter 3, and detail the technique only for the DLREP-based showing
protocols.

Atomic formulae without “NOT” connectives
Consider ¬rst the case that P is to demonstrate an atomic formula of the form (3.3),
using the showing protocol depicted in Figure 3.1. In Step 2 of the issuing protocol,
instead of generating the initial witness in a formula-dependent manner, P simply
computes a := i=1 gi i , for random w 1 , . . . , wl ∈ Zq . In the showing protocol, P
l w

in addition sends to V a set of t correction factors, e 1 , . . . , et , all in Zq . These serve
to adjust a, in such a manner that the DL-representation known to P of the adjusted
a is suitable to complete the demonstration in the same manner as in the original
protocol. Speci¬cally, the adjusted a is computed as
t
ei
a/ gπ(l’t+i) .
i=1

By applying the protocol of Figure 3.1 and expanding the resulting terms, the follow-
ing (generic) protocol steps result:
Step 1. P computes t correction factors, as follows:
l’t
∀i ∈ {1, . . . , t}.
ei := wπ(l’t+i) + ±ij wπ(j) mod q
j=1

P then sends its one-time public key (h, a) and (e 1 , . . . , et ) to V.
Z s , as
Step 2. P computes a set of responses, responsive to V™s challenge c ∈
follows:
ri := cxπ(i) + wπ(i) mod q ∀i ∈ {1, . . . , l ’ t}.
P then sends (r1 , . . . , rl’t ) to V.
5.4 LIMITED-SHOW CERTIFICATES 203


V computes
l’t
rl’t+i := ei + bi c ’ ∀i ∈ {1, . . . , t},
±ij rj mod q
j=1

and accepts if and only if
l
gπ(i) h’c = a.
ri

i=1
Assuming s is large and c is generated in a substantially random manner and after
the data in Step 1 has been sent, it is easy to prove that V is convinced if and only
if P™s attributes satisfy the formula (3.3). Furthermore, all the considerations in
Section 3.3.1 apply, with the obvious modi¬cations. Notably, assuming that all the
correction factors are hashed along as well when forming c, Propositions 3.3.6, 3.3.7,
and 3.3.8 all hold.
Suppose now that P reuses the one-time public key (h, a), demonstrating a for-
mula of the form (3.3) that need not be the same as in the ¬rst demonstration. Clearly,
the proof of Case 1 in Proposition 5.4.1 applies as is. Consequently, if the two demon-
strations are performed responsive to different challenges, then with overwhelming
probability all the attributes of P can be ef¬ciently computed from the two accepting
views of V.
V can limit the class of atomic formulae that P is able to demonstrate by imposing
restrictions on the number, the position, or the form of the correction factors that
P may use. Complete anticipation of the formula corresponds to the extreme case
where P is not allowed to use any correction factors; this is the case of static one-
show certi¬cates. The CA can encode restrictions on the correction factors into one
of the xi ™s (e.g., as part of a CA policy attribute), which P must then disclose to V in
the showing protocol as part of the formula it is demonstrating.
The technique in Section 5.3 can be applied as well. Only those correction factors
that correspond to F — should be hashed along when forming c. For dispute settle-
ment, V should in addition hash along a commitment to both the hidden part of F
and the remaining correction factors.

Arbitrary atomic formulae
The situation is slightly more complex in case P must be able to demonstrate any
atomic formula. This time, we have P in Step 2 of the issuing protocol hash along an
initial witness a := h’w0 i=1 gi i , for random w 0 , . . . , wl ∈ Zq . To demonstrate a
l w

formula of the form (3.4), P in Step 1 of the showing protocol of Figure 3.5 must be
allowed to reveal t correction factors, (e 1 , . . . , et ), to adjust a to
t
ei
a/ gπ(l’t+i) .
i=1
204 COMBINING ISSUING AND SHOWING PROTOCOLS


To demonstrate a formula of the form (3.3), P in Step 1 of the showing protocol
depicted in Figure 3.1 must this time be allowed to reveal t + 1 correction factors, to
adjust a to
t
ei
e0
a/h gπ(l’t+i) ,
i=1
because the exponent ’w 0 of h must be canceled as well. For both cases, it is easy
to describe the resulting protocol. This time, the proof of Case 1 in Proposition 5.4.1
does not apply, because V™s challenge in the veri¬cation relation for the demonstra-
tion of an atomic formula with a “NOT” connective does not appear as a power of h.
Speci¬cally, the veri¬cation relation for an atomic formula of the form (3.4) is
l’t t l’t
ei +bi r0 ’fi c’ ±ij rj
ri
= hr0 a
j=1
gπ(i) gπ(l’t+i)
i=1 i=1

and that for an atomic formula of the form (3.3) with matrix coef¬cients ± — is
ij

l’t— t— l’t—
e— +b— c— ’ ±— rj

— —
+e—
ri i i ij
= hc
j=1
gπ(i) gπ(l’t— +i) a.
0

i=1 i=1

If r0 = c— + e— mod q, and cancellation takes place also for the exponents to all
0
gi ™s (otherwise a non-trivial DL-representation of 1 is obtained; cf. Case 2 of Propo-
sition 5.4.1), then the DL-representation of h with respect to (g 1 , . . . , gl ) cannot be
computed even though c — may differ from c. Indeed, if P is allowed to select V™s
challenge in an arbitrary manner, subject only to the condition that it has to be unique
in each formula demonstration, it is not hard to construct a one-time public key (h, a),
two atomic formulae, two different challenge messages, and two protocol transcripts
for which total cancellation takes place.
We can get around this in a natural manner, by requiring V™s challenge message
to be a suf¬ciently strong hash of at least (h, a), a unique formula description, and the
correction factors (in a unique order). Under this condition, which is needed anyway
to prove the unforgeability and unmodi¬ability of signed proofs in the random oracle
model (see Section 3.4.1), the following holds: if any two atomic formula demon-
strations are performed responsive to different challenges, then with overwhelming
probability all the attributes of P can be ef¬ciently computed from the two accept-
ing views of V. Under the conditions of Proposition 3.3.6 and 3.3.7, respectively, this
can be proved in the random oracle model for both non-interactively and interactively
issued signed proofs.

Atomic formulae connected by “OR” connectives
Another treacherous aspect enters when P must be able to demonstrate any formula
of the form (3.6), in such a manner that any two demonstrations involving the same
5.4 LIMITED-SHOW CERTIFICATES 205


one-time public key disclose all the encoded attributes. The simplest approach is
for P to simulate all but one of the subformulae demonstrations, in the manner de-
scribed in Section 3.5.1, and to hash along in Step 2 of the issuing protocol an initial
witness formed in the same formula-independent manner as in the case of atomic
formulae. This fails, however, because V can infer from a single showing protocol
execution which subformula demonstration is genuine. Using the same a for each
subformula demonstration, and providing random correction factors for those sub-
formulae demonstrations that are simulated, does not work either: if j ≥ 2 then
V can compute P™s representation from a single execution of the showing proto-
col. Yet another ¬‚awed approach is for P to use a one-time public key of the form
(h, a1 , . . . , aj — ), where j — ≥ j: this requires P to know an upper bound on j, the
number of “OR” connectives in the formula to be demonstrated.
All these problems can be avoided by introducing an extra constraint in the show-
ing protocol described in Section 3.5.1. Let

l
’w0 w
a := h gi i
i=1

be the master initial witness that P in Step 2 of the issuing protocol incorporates into
its one-time public key, and let a i denote the initial witness used in the demonstration
of subformula F i , for all i ∈ {1, . . . , j}. For each of the j subformula demonstra-
tions, we have P reveal up to l correction factors to adjust the initial witness a i
for that subformula demonstration, as described previously. P could do without the
use of correction factors in the j ’ 1 subformula demonstrations that are simulated,
but they are needed to hide from V which subformula demonstration is genuine; the
zero-knowledge simulator must generate the required number of correction factors at
random (as many as would be needed in a genuine proof). The extra constraint is that
the product of the j adjusted initial witnesses must equal the master initial witness, a.
P can easily meet this constraint, since a i in each of the j ’ 1 simulated subformulae
demonstrations is generated in such a manner that P knows a DL-representation with
respect to (g1 , . . . , gl , h); therefore, P can determine the remaining set of correction
factors (for the subformula that requires a genuine proof) by comparing the represen-
tation it knows of a with that of the product of the j ’ 1 adjusted initial witnesses. V
must verify the extra constraint as part of its veri¬cation process.
To obtain a signed proof, V™s challenge should be formed by hashing at least
(h, a, F ) and all correction factors (in a unique order). Under the conditions of
Proposition 3.3.6 and 3.3.7, respectively, it can be proved in the random oracle model
that both non-interactively and interactively issued signed proofs are unforgeable and
unmodi¬able. If the CA does not trust V, the latter will need to relay the entire tran-
script of the showing protocol to the CA.
Why does this work? By aggregating the j veri¬cation relations (one for each
subformula demonstration), V can obtain a compound veri¬cation relation of the
206 COMBINING ISSUING AND SHOWING PROTOCOLS


form
l
y
gi i = hy0 a.
i=1

Each yi , for i ∈ {0, . . . , l}, is an arithmetic expression that involves subformulae co-
ef¬cients, responses (at most one from each subformula demonstration), and perhaps
correction factors and V™s challenge. Suppose now that P reuses its one-time public
key (h, a). This time, V obtains a compound veri¬cation relation
l
y— —
gi i = hy0 a.
i=1

From the two compound veri¬cation relations, the DL-representation that P knows
of h can be extracted, unless P has managed to perform its two protocol executions

in such a manner that y i = yi mod q for all i ∈ {0, . . . , l}. If V™s challenge is
formed by hashing at least (h, a, F ) and all correction factors, then it is infeasible to
effect this cancellation, assuming only that V™s challenge differs in the two showing
protocol executions; this result can be proved in the random oracle model.
An anomaly occurs in case none of the atomic subformulae involve a “NOT”
connective. In this case, V need not hash along a description of F and the correction
j
factors. If i=1 ci = c mod q, it follows from the constraint on the adjusted initial
witnesses that V can obtain a compound relation of the form
l
y
gi i = hc a.
i=1

With c being a suf¬ciently strong hash of at least (h, a), the unforgeability of this
compressed signed proof of knowledge of a DL-representation of h follows as in
the case of Propositions 3.3.6 and 3.3.7. By applying the technique described in
Section 5.3, V can unconditionally hide which formula F has been demonstrated
(from the space of all formulae that connect atomic subformula without “NOT” con-
nectives by zero or more “OR” connectives), yet V itself becomes convinced of F
during the showing protocol. In case (h, a) is reused in a showing protocol execution
involving a different c, the CA can extract P™s DL-representation of h. Sending only
(h, c, y1 , . . . , yl ) to the CA is preferable also for reason of ef¬ciency.

Arbitrary Boolean formulae
Finally, consider the case where P must be able to demonstrate any formula F of the
form (3.7). The one-show certi¬cate technique for formulae of the form (3.6) applies
here as well. This time, the product of all the adjusted initial witnesses, one for each
atomic subsubformula in F , must equal the master initial witness, a. Aggregation
5.4 LIMITED-SHOW CERTIFICATES 207


of all the veri¬cation relations, one for each subformula demonstration, results in a
compound veri¬cation relation of the form
l
y
gi i = hy0 a.
i=1

Assuming V™s challenge is formed by hashing at least (h, a, F ) and all correction
factors, reuse of (h, a) with respect to a different c enables the computation of P™s
DL-representation of h. Again, this result can be proved in the random oracle model.
Note that only (y 0 , yi ) needs to be stored to be able to compute x i from P™s
DL-representation upon reuse of (h, a), regardless of the formula demonstrated. To
be able to detect reuse, in addition the CA must store a hash of (h, a, cert(h, a)).
A hash function that is second-preimage resistant may be used (i.e., for a random
input, it is infeasible to ¬nd another input that maps to the same output). In practice,
simply storing the 10 most signi¬cant bytes of h, say, should be adequate, assuming
that it is agreed on that no certi¬cate applicant retrieves multiple certi¬cates on the
same public key. According to Section 2.2.2, 25-byte exponents should suf¬ce for
long-term security, which makes our technique for dynamic one-show certi¬cates
highly practical: per showing protocol transcript a mere 60 bytes need to be stored,
regardless of the formula demonstrated.
The dynamic one-show certi¬cate technique can be applied in a straightforward
manner to the RSAREP-based issuing and showing protocols. In this case, the CA
will be able to compute P™s attributes (x 1 , . . . , xl ) as well as xl+1 upon redemon-
stration of the same formula.


5.4.3 Increasing the threshold
There is nothing magical about a threshold value of 1. To ensure that P™s representa-
tion can be computed if and only if P performs more than t demonstrations using the
same certi¬ed public key, for a predetermined positive integer t, P™s t-time public
key should comprise t master initial witnesses. When performing the i-th execution
of the showing protocol, using the same t-time public key, P uses the i-th master
initial witness. Alternatively, to obscure in the current showing protocol execution
how many showing protocol executions have already been performed using the same
public key, P uses a master initial witness that it randomly chooses out of those not
yet used. The pigeon-hole principle ensures that any t + 1 demonstrations lead to the
reuse of a master initial witness. From the corresponding two views P™s representa-
tion can be computed.
For large thresholds, it is more ef¬cient to use Merkle™s tree authentication tech-
nique [267]. Hereto P builds a binary tree with the master initial witnesses in the
leaves. Each node value in the level just above the leaves is computed by compress-
ing the entries in the leaves below it, using a collision-intractable hash function. All
208 COMBINING ISSUING AND SHOWING PROTOCOLS


the other node values are computed by compressing the child node values. The value
of the root node together with h serves as the t-time public key; it must be hashed
along in Step 2 of the issuing protocol. In the showing protocol, P must reveal the
particular master initial witness it intends to use in the formula demonstration, to-
gether with 2 log t nodes to enable V to compute its way back to the root node and
verify the certi¬cate.
If V (or the CA) consents, t-show certi¬cates can be turned on the spot into i-
show certi¬cates for any i ∈ {1, . . . , t}, by ¬xing a subset of size i of master initial
witnesses that may be used in the showing protocol. Also, a t-show certi¬cate may be
converted into an unlimited-show certi¬cate, by allowing P in the showing protocol
to use initial witnesses other than those comprised in its t-time public key. By way of
example, consider the technique in Section 5.3 and suppose the CA is interested only
in being able to trace certi¬cate holders who show their certi¬cates too many times.
P supplies two proofs to V: a signed proof demonstrating the formula TRUE and a
proof demonstrating the formula V is interested in. The signed proof must use one

. 1
( 2)



>>