2

3

ZERO-KNOWLEDGE PROOFS

Prof. Rivest: Any other questions about Palladium or its applications. How many of you think

Palladium isn’t going to fly? A couple dozen people raise their hands. Why isn’t it going to fly?

Student: Not enough perceived benefit to the user. I don’t think the end user desire exists. Lack

of motivation. Maybe government agencies and enterprises will be interested.

Prof. Rivest: It will be interesting to see how this rolls out: So one of the things Palladium does

is burn in keys.

Figure 1: Palladium model. The keys shown here in the nexus are actually in a separate chip called

the SSC.

PK represents the machine’s identity. We don’t necessarily want to sign everything with PK, since

this will reveal machine-specific information that could compromise our privacy. One thing we could

do is generate a new PK1 and send PK, cert(PK), and PK1 to a certificate authority (CA). The

CA would then return cert(PK1). Basically the certificate says that the key belongs to a Palladium

machine, but doesn’t say which one. We have created an alias and provided anonymity.

The problem with this architecture is that the CA knows all the mappings from PK to PK1. This

may be what you want, but if not, what you might really be after is a way to convince the CA that

you have a Palladium machine with a PK/SK and a certificate, without actually revealing those

items.

How can this be done? Enter Zero-Knowledge (ZK) Proofs:

3

Zero-Knowledge Proofs

In a zero-knowledge (ZK) proof, you are basically trying to convince someone that you know some-

thing without telling them what it is, such as the message m corresponding to a known public

ciphertext c.