ńņš. 1 |

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)

IĪ±

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 |