L13-PALLADIUM.pdf 데이터시트 (총 7 페이지) - 파일 다운로드 L13-PALLADIUM 데이타시트 다운로드

No Preview Available !

6.857 Computer and Network Security
October 22, 2002
Lecture Notes 13 : Palladium, Zero Knowledge
Lecturer: Ron Rivest
Scribe: Baratz/Gavacs/Sen/Sudan
[These are the initial scribe notes. The final version will appear with updated figures. Namely, the
figures will have larger fonts.]
1 Outline
- Palladium discussion
- Zero Knowledge Proofs
2 Palladium discussion
Prof. Rivest: What did people like / dislike about Palladium?
Student: I think it’s interesting to think about the various other organizations that are affecting
Palladium, like Hollywood, etc.
Student: I don’t think Palladium is going to fly. They haven’t really come up with a killer-app and
the cost is going to be too high. What is the killer app? Movie and music distribution?
Prof. Rivest: Could movie distribution be the killer app? That really seems to be their driving
motivation.
Student: It seems as though the only way they can justify this initiative is if they envision PCs
becoming the center of a home theater system. Using PCs to control DVD players, TVs, etc.
Prof. Rivest: A very useful way of thinking about it is as a virtual embedded set top box.
Student: How can they use this system for DRM if it isn’t physically tamper-resistant? Maybe due
to the DMCA it would be illegal to install dual-ported memory. Hardware attacks could probably
be carried out for hundreds of dollars or less. A movie could be extracted and then distributed.
Prof. Rivest: Besides DRM, what could this be used for?
Student: Possibly subscription services, software licensing, or piracy control.
Student: The whole TCPA framework provides a lot of functionality to enterprises.
Student: It seems as though the right-hand side of Palladium won’t really be used that much and
isn’t robust enough to run complete applications like Word, etc.
Prof. Rivest: This reminds me of how we drew the distinction between user and kernel space, and
then with Microsoft operating systems and plug-and-play people have been able to insert drivers,
etc. into kernel space. Now all they’ve done is draw another line and are daring outsiders to cross
that line. After a while all sorts of code will have found its way into the Palladium zone and then
what do we do? Draw another line and make Palladium 2?
0May be freely reproduced for educational or personal use.
1

No Preview Available !

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.

No Preview Available !

3.1 The General Set-up
3.1 The General Set-up
3
P = Prover
wants to prove he knows m
V = Verifier
wants to learn if P knows m
−−−−−−−−−w=witness −−−−−−→
←−−−x=random−−challenge−−−−
−−−−−−−−y=response−−−−−−→
test (c, w, x, y).
Accept if OK, reject otherwise.
We want the protocol to satisfy the following properties:
1. If P does know m, then V always accepts. (Completeness)
2. If P does not know m, then P is unlikely to convince V . (Soundness)
Soundness may be shown by demonstrating that if P is prepared to respond to several different
challenges (for the same witness), then in fact P must know (or must be able to easily compute) m.
We would also like to have that the protocol be zero-knowledge: the Verifier learns nothing (zero),
aside from the fact that P knows m.
3.2 3-Colorability Example
We have an undirected graph with 5 vertices. Can we color the vertices with three colors so that no
two adjacent vertices have the same color?
A given graph may have many possible colorings, only one coloring, or no colorings at all. Suppose
I have a graph with a million vertices and I tell you I know how to color it using 3 colors. I want to
convince you that the graph is 3-colorable without telling you what the coloring is. Is there some
way I can convince a remote computer, the skeptic, that I know how to do the coloring without
saying what the coloring is?
Consider the following exchange between the Prover (you, the person who knows the 3-coloring) and
the Verifier (the remote computer you are trying to convince):
For a given graph coloring, there are 6 different permutations of the coloring possible: RGB, RBG,
BRG, BGR, GBR, GRB. That is, you take one coloring and just permute the color assignments
(e.g. from RGB to RBG, all vertices that are R are still R, all vertices that are G are now B, etc.).
Again, this is just for one coloring that the Prover picks. We can represent each permutation as a
sheet of paper with the graph and coloring on it (see Figure 4 below).
[Figure 4: Representation of the 6 permutations of a given graph 3-coloring]
Do t times: Prover: picks a sheet (graph with a coloring permutation) from a random pile (Verifier
doesn’t know which pile Prover picks) and puts it on the table covering up vertices with little stickies