Prev. Page Next Chapter

CHAPTER 5 ................................................. 101

Advanced Protocols ................................ 101

ZERO-KNOWLEDGE PROOFS ............. 101

Basic Zero-Knowledge Protocol .................. 102

Graph Zsomorphism .................................... 104

Hamiltonian Cycles ...................................... 105

Parallel Zero-Knowledge Proofs .................. 106

Noninteractive Zero-Knowledge Proofs ....... 106

Generalities ................................................. 108

ZERO-KNOWLEDGE PROOFS OF ........ 109

The Chess Grandmaster Problem ............... 109

The Mafia Fraud .......................................... 110

The Terrorist Fraud ...................................... 110

Suggested Solutions .................................... 110

The Multiple Identity Fraud .......................... 111

Renting Passports ....................................... 111

Proofs Membership ..................................... 111

BLIND SIGNATURES ............................. 112

Completely Blind Signatures ....................... 112

Blind Signatures .......................................... 113

Pa tents ....................................................... 115

PUBLIC-KEY CRYPTOGRAPHY ................ 115

IDENTITY-BASED .................................. 115

TABLE 5.1 Chaums Blind Signature .......... 115

OBLIVIOUS TRANSFER ........................ 116

OBLIVIOUS SIGNATURES .................... 117

SIMULTANEOUS CONTRACT SIGNIN .. 118

Contract Signing with an Arbitrator .............. 118

Simultaneous Contract Signing without an ... 118

Simultaneous Contract Signing without an ... 119

Simultaneous Contract Signing without an ... 120

DIGITAL CERTIFIED .............................. 122

SIMULTANEOUS EXCHANGE OF ......... 123

Page 101

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Advanced Protocols

5.1 ZERO-KNOWLEDGE PROOFS

Hereâ€™s another story:

ALICE: â€śI know the password to the Federal Reserve System computer, the ingredients

in McDonaldâ€™s secret sauce, and the contents of Volume 4 of Knuth.â€ť

BOB: â€śNo, you donâ€™t.â€ť

ALICE: â€śYes, I do.â€ť

BOB: â€śDo not!â€ť

ALICE: â€śDo too!â€ť

BOB: â€śProve it!â€ť

ALICE: â€śAll right. Iâ€™ll tell you.â€ť She whispers in Bobâ€™s ear.

The Washington

BOB: â€śThatâ€™s interesting. Now I know it, too. Iâ€™m going to tell

Post.â€ť

ALICE: â€śOops.â€ť

Unfortunately, the usual way for Alice to prove something to Bob is for Alice to

tell him. But then he knows it, too. Bob can then tell anyone else he wants to and

Alice can do nothing about it. (In the literature, different characters are often used

in these protocols. Peggy is usually cast as the prover and Victor is the verifier.

These names appear in the upcoming examples, instead of Alice and Bob.)

Using one-way functions, Peggy could perform a zero-knowledge proof [626]. This

protocol proves to Victor that Peggy does have a piece of information, but it does not

give Victor any way to know what the information is.

These proofs take the form of interactive protocols. Victor asks Peggy a series of

questions. If Peggy knows the secret, she can answer all the questions correctly. If

she does not, she has some chance-50 percent in the following examples-of

answering correctly. After 10 or so questions, Victor will be convinced that Peggy

knows the secret. Yet none of the questions or answers gives Victor any information

about Peggyâ€™s information-only about her knowledge of it.

Page 102

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

Basic Zero-Knowledge Protocol

Jean-Jacques Quisquater and Louis Guillou explain zero-knowledge with a story

about a cave [ 12811. The cave, illustrated in Figure 5.1, has a secret. Someone who

knows the magic words can open the secret door between C and D. To everyone

else, both passages lead to dead ends.

Peggy knows the secret of the cave. She wants to prove her knowledge to Victor,

but she doesnâ€™t want to reveal the magic words. Hereâ€™s how she convinces him:

(1) Victor stands at point A.

(2) Peggy walks all the way into the cave, either to point C or point D.

(3) After Peggy has disappeared into the cave, Victor walks to point B.

(4) Victor shouts to Peggy, asking her either to:

(a) come out of the left passage or

(b) come out of the right passage.

(5) Peggy complies, using the magic words to open the secret door if she has to.

(6) Peggy and Victor repeat steps (1) through (5) n times.

Assume that Victor has a camcorder and records everything he sees. He records

Peggy disappearing into the cave, he records when he shouts out where he wants

Peggy to come out from, and he records Peggy coming out. He records all n trials. If

he showed this recording to Carol, would she believe that Peggy knew the magic

words to open the door? No. What if Peggy and Victor had agreed beforehand what

Victor would call out, and Peggy would make sure that she went into that path.

Then she could come out where Victor asked her every time, without knowing the

magic words. Or maybe they couldnâ€™t do that. Peggy would go into one of the pas-

sages and Victor would call out a random request. If Victor guessed right, great; if he

didnâ€™t, they would edit that trial out of the camcorder recording. Either way, Victor

Figure 5.1 The zero-knowledge cave.

Page 103

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

can get a recording showing exactly the same sequence of events as in a real proof

where Peggy knew the magic words.

This shows two things. One, it is impossible for Victor to convince a third party

of the proofâ€™s validity. And two, it proves that the protocol is zero-knowledge. In the

case where Peggy did not know the magic words, Victor will obviously not learn

anything from watching the recording. But since there is no way to distinguish a real

recording from a faked recording, Victor cannot learn anything from the real proof-

it must be zero knowledge.

The technique used in this protocol is called cut and choose, because of its simi-

larity to the classic protocol for dividing anything fairly:

(1) Alice cuts the thing in half.

(2) Bob chooses one of the halves for himself.

(3) Alice takes the remaining half.

It is in Aliceâ€™s best interest to divide fairly in step (l), because Bob will choose

whichever half he wants in step (2). Michael Rabin was the first person to use the

cut-and-choose technique in cryptography [1282]. The concepts of interactive pro-

tocol and zero-knowledge were formalized later [626,627].

The cut-and-choose protocol works because there is no way Peggy can repeat-

edly guess which side Victor will ask her to come out of. If Peggy doesnâ€™t know the

secret, she can only come out the way she came in. She has a 50 percent chance of

guessing which side Victor will ask in each round (sometimes called an accredita-

tion) of the protocol, so she has a 50 percent chance of fooling him. The chance of

her fooling him in two rounds is 25 percent, and the chance of her fooling him all

n times is 1 in 2â€ť. After 16 rounds, Peggy has a 1 in 65,536 chance of fooling Vic-

tor. Victor can safely assume that if all 16 of Peggyâ€™s proofs are valid, then she

must know the secret words to open the door between points C and D. (The cave

analogy isnâ€™t perfect. Peggy can simply walk in one side and out the other; thereâ€™s

no need for any cut-and-choose protocol. However, mathematical zero knowledge

requires it.)

Assume that Peggy knows some information, and furthermore that the informa-

tion is the solution to a hard problem. The basic zero-knowledge protocol consists

of several rounds.

(1) Peggy uses her information and a random number to transform the hard

problem into another hard problem, one that is isomorphic to the original

problem. She then uses her information and the random number to solve

this new instance of the hard problem.

(2) Peggy commits to the solution of the new instance, using a bit-commitment

scheme.

(3) Peggy reveals to Victor the new instance. Victor cannot use this new prob-

lem to get any information about the original instance or its solution.

Page 104

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

(4) Victor asks Peggy either to:

(a) prove to him that the old and new instances are isomorphic (i.e., two

different solutions to two related problems), or

(b) open the solution she committed to in step (2) and prove that it is a

solution to the new instance.

(5) Peggy complies.

(6) Peggy and Victor repeat steps (1) through (5) n times.

Remember the camcorder in the cave protocol? You can do the same thing here.

Victor can make a transcript of the exchange between him and Peggy. He cannot use

this transcript to convince Carol, because he can always collude with Peggy to build

a simulator that fakes Peggyâ€™s knowledge. This argument can be used to prove that

the proof is zero-knowledge.

The mathematics behind this type of proof is complicated. The problems and the

random transformation must be chosen carefully, so that Victor does not get any

information about the solution to the original problem, even after many iterations

of the protocol. Not all hard problems can be used for zero-knowledge proofs, but a

lot of them can.

Graph Zsomorphism

An example might go a long way to explain this concept; this one comes from

graph theory [619,622]. A graph is a network of lines connecting different points. If

two graphs are identical except for the names of the points, they are called isomor-

phic. For an extremely large graph, finding whether two graphs are isomorphic can

take centuries of computer time; itâ€™s one of those NP-complete problems discussed

in Section 11.1.

Assume that Peggy knows the isomorphism between the two graphs, G1 and Gz.

The following protocol will convince Victor of Peggyâ€™s knowledge:

(1) Peggy randomly permutes G1 to produce another graph, H, that is isomor-

phic to Gi. Because Peggy knows the isomorphism between H and G1, she

also knows the isomorphism between H and Gz. For anyone else, finding

an isomorphism between Gi and H or between Gz and H is just as hard as

finding an isomorphism between Gi and Gz.

(2) Peggy sends H to Victor.

(3) Victor asks Peggy either to:

(a) prove that H and Gi are isomorphic, or

(b) prove that H and Gz are isomorphic.

(4) Peggy complies. She either:

(a) proves that H and G1 are isomorphic, without proving that H and Gz

are isomorphic, or

(b) proves that H and Gz are isomorphic, without proving that H and G1

are isomorphic.

(5J Peggy and Victor repeat steps (1) through (4) n times.

Page 105

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5.1 Zero-Knowledge Proofs

If Peggy does not know an isomorphism between Gi and Gr, she cannot create

graph H which is isomorphic to both. She can create a graph that is either isomorphic

to G1 or one that is isomorphic to GZ. Like the previous example, she has only a 50

percent chance of guessing which proof Victor will ask her to perform in step (3).

This protocol doesnâ€™t give Victor any useful information to aid him in figuring out

an isomorphism between GI and GP.Because Peggy generates a new graph H for each

round of the protocol, he can get no information no matter how many rounds they

go through the protocol. He wonâ€™t be able to figure out an isomorphism between G,

and Gz from Peggyâ€™s answers.

In each round, Victor receives a new random permutation of H, along with an iso-

morphism between H and either G1 or G2. Victor could just as well have generated

this by himself. Because Victor can create a simulation of the protocol, it can be

proven to be zero-knowledge.

Hamiltonian Cycles

A variant of this example was first presented by Manuel Blum [ 1961.Peggy knows

a circular, continuous path along the lines of a graph that passes through each point

exactly once. This is called a Hamiltonian cycle. Finding a Hamiltonian cycle is

another hard problem. Peggy has this piece of information-she probably got it by

creating the graph with a certain Hamiltonian cycle-and this is what she wants to

convince Victor that she knows.

Peggy knows the Hamiltonian cycle of a graph, G. Victor knows G, but not the

Hamiltonian cycle. Peggy wants to prove to Victor that she knows this Hamiltonian

cycle without revealing it. This is how she does it:

( 1) Peggy randomly permutes G. She moves the points around and changes their

labels to make a new graph, H. Since G and H are topologically isomorphic

(i.e., the same graph), if she knows the Hamiltonian cycle of G then she can

easily find the Hamiltonian cycle of H. If she didnâ€™t create H herself, deter-

mining the isomorphism between two graphs would be another hard prob-

lem; it could also take centuries of computer time. She then encrypts H to

get Hâ€™. (This has to be a probabilistic encryption of each line in H, that is, an

encrypted 0 or an encrypted 1 for each line in H.)

(2) Peggy gives Victor a copy of IY.

(3) Victor asks Peggy either to:

(a) prove to him that Hâ€™ is an encryption of an isomorphic copy of G, or

(b) show him a Hamiltonian cycle for H.

(4) Peggy complies. She either:

(a) proves that Hâ€™ is an encryption of an isomorphic copy of G by revealing

the permutations and decrypting everything, without showing a

Hamiltonian cycle for either G or H, or

(b) shows a Hamiltonian cycle for H by decrypting only those lines that

constitute a Hamiltonian cycle, without proving that G and H are

topologically isomorphic.

(5) Peggy and Victor repeat steps (1) through (4) n times.

Page 106

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

If Peggy is honest, she can provide either proof in step (4) to Victor. However, if

she does not know a Hamiltonian cycle for G, she cannot create an encrypted graph

Hâ€˜ which can meet both challenges. The best she can do is to create a graph that is

either isomorphic to G or one that has the same number of points and lines and a

valid Hamiltonian cycle. While she has a 50 percent chance of guessing which proof

Victor will ask her to perform in step (3), Victor can repeat the protocol enough

times to convince himself that Peggy knows a Hamiltonian cycle for G.

Parallel Zero-Knowledge Proofs

The basic zero-knowledge protocol involves n exchanges between Peggy and Vic-

tor. Why not do them all in parallel:

(1) Peggy uses her information and n random numbers to transform the hard

problem into n different isomorphic problems. She then uses her informa-

tion and the random numbers to solve the n new hard problems.

(2) Peggy commits to the solution of the n new hard problems.

(3) Peggy reveals to Victor the n new hard problems. Victor cannot use these

new problems to get any information about the original problems or its

solutions.

(4) For each of the n new hard problems, Victor asks Peggy either to:

(a) prove to him that the old and new problems are isomorphic, or

(b) open the solution she committed to in step (2) and prove that it is a

solution to the new problem.

(5) Peggy complies for each of the n new hard problems.

Unfortunately, itâ€™s not that simple. This protocol does not have the same zero-

knowledge properties as the previous protocol. In step (4), Victor can choose the

challenges as a one-way hash of all the values committed to in the second step, thus

making the transcript nonsimulatable. It is still zero-knowledge, but of a different

sort. It seems to be secure in practice, but no one knows how to prove it. We do

know that in certain circumstances, certain protocols for certain problems can be

run in parallel while retaining their zero-knowledge property [247,106,546,616].

Noninteractive Zero-Knowledge Proofs

Carol canâ€™t be convinced because the protocol is interactive, and she is not involved

in the interaction. To convince Carol, and anyone else who may be interested, we

need a noninteractive protocol.

Protocols have been invented for noninteractive zero-knowledge proofs [477,

198,478,197]. These protocols do not require any interaction; Peggy could publish

them and thereby prove to anyone who takes the time to check that the proof

is valid.

The basic protocol is similar to the parallel zero-knowledge proof, but a one-way

hash function takes the place of Victor:

Page 107

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

(1) Peggy uses her information and n random numbers to transform the hard

problem into n different isomorphic problems. She then uses her informa-

tion and the random numbers to solve the n new hard problems.

(2) Peggy commits to the solution of the n new hard problems.

(3) Peggy uses all of these commitments together as a single input to a one-

way hash function. (After all, the commitments are nothing more than bit

strings.) She then saves the first n bits of the output of this one-way hash

function.

(4) Peggy takes the n bits generated in step (3). For each ith new hard problem

in turn, she takes the ith bit of those n bits and:

(a) if it is a 0, she proves that the old and new problems are isomorphic, or

(b) if it is a 1, she opens the solution she committed to in step (2) and

proves that it is a solution to the new problem.

(5) Peggy publishes all the commitments from step (2) as well as the solutions

in step (4).

(6) Victor or Carol or whoever else is interested, verifies that steps (1) through

(5) were executed properly.

This is amazing: Peggy can publish some data that contains no information about

her secret, but can be used to convince anyone of the secretâ€™s existence. The proto-

col can also be used for digital signature schemes, if the challenge is set as a one-way

hash of both the initial messages and the message to be signed.

This works because the one-way hash function acts as an unbiased random-bit

generator. For Peggy to cheat, she has to be able to predict the output of the one-way

hash function. (Remember, if she doesnâ€™t know the solution to the hard problem,

she can do either (a) or (b) of step (4), but not both.) If she somehow knew what the

one-way hash function would ask her to do, then she could cheat. However, there is

no way for Peggy to force the one-way function to produce certain bits or to guess

which bits it will produce. The one-way function is, in effect, Victorâ€™s surrogate in

the protocol-randomly choosing one of two proofs in step (4).

In a noninteractive protocol, there must be many more iterations of the chal-

lenge/reply sequence. Peggy, not Victor, picks the hard problems using random

numbers. She can pick different problems, hence different commitment vectors, till

the hash function produces something she likes. In an interactive protocol, 10 iter-

ations-a probability of 1 in 2â€™O(1 in 1024) that Peggy can cheat-may be fine. How-

ever, thatâ€™s not enough for noninteractive zero-knowledge proofs. Remember that

Mallory can always do either (a) or (b) of step (4). He can try to guess which he will

be asked to do, go through steps (1) through (3), and see if he guessed right. If he

didnâ€™t, he can try again-repeatedly. Making 1024 guesses is easy on a computer. To

prevent this brute-force attack, noninteractive protocols need 64 iterations, or even

128 iterations, to be valid.

This is the whole point of using a one-way hash function: Peggy cannot predict the

output of the hash function because she cannot predict its input. The commitments

which are used as the input are only known after she solves the new problems.

Page 108

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

Generalities

Blum proved that any mathematical theorem can be converted into a graph such

that the proof of that theorem is equivalent to proving a Hamiltonian cycle in the

graph. The general case that any NP statement has a zero-knowledge proof, assum-

ing one-way functions and therefore good encryption algorithms, was proved in

[620]. Any mathematical proof can be converted into a zero-knowledge proof. Using

this technique, a researcher can prove to the world that he knows the proof of a par-

ticular theorem without revealing what that solution is. Blum could have published

these results without revealing them.

There are also minimum-disclosure proofs [590]. In a minimum-disclosure proof,

the following properties hold:

1. Peggy cannot cheat Victor. If Peggy does not know the proof, her chances

of convincing Victor that she knows the proof are negligible.

2. Victor cannot cheat Peggy. He doesnâ€™t get the slightest hint of the proof,

apart from the fact that Peggy knows the proof. In particular, Victor cannot

demonstrate the proof to anyone else without proving it himself from

scratch.

Zero-knowledge proofs have an additional condition:

3. Victor learns nothing from Peggy that he could not learn by himself with-

out Peggy, apart from the fact that Peggy knows the proof.

There is considerable mathematical difference between proofs that are only

minimum-disclosure and those that are zero-knowledge. That distinction is be-

yond the scope of this book, but more sophisticated readers are welcome to peruse

the references. The concepts were introduced in [626,619,622]. Further elaboration

on their ideas, based on different mathematical assumptions, were developed in

[240,319,239].

There are also different kinds of zero-knowledge proofs:

- Perfect. There is a simulator that gives transcripts identically dis-

tributed to real transcripts (the Hamiltonian cycle and graph isomor-

phism examples).

- Statistical. There is a simulator that gives transcripts identically dis-

tributed to real transcripts, except for some constant number of

exceptions.

- Computational. There is a simulator that gives transcripts indistin-

guishable from real transcripts.

- No-use. A simulator may not exist, but we can prove that Victor will

not learn any polynomial amount of information from the proof (the

parallel example).

Page 109

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5.2 Zero-Knowledge Proofs of Identity

Over the years, extensive work, both theoretical and applied, has been done on

minimum-disclosure and zero-knowledge proofs. Mike Burmester and Yvo Desmedt

invented broadcast interactive proofs, where one prover can broadcast a zero-

knowledge interactive proof to a large group of verifiers [280]. Cryptographers proved

that everything that can be proven with an interactive proof can also be proven with

a zero-knowledge interactive proof [753,137].

A good survey article on the topic is [548]. For additional mathematical details,

variations, protocols, and applications, consult [590,619,240,319,620,113,241,1528,

660,238,591,617,510,592,214,104,216,832,97,939,622,482,615,618,215,476,71]. A lot

has been written on this subject.

5.2 ZERO-KNOWLEDGE PROOFS OF IDENTITY

In the real world, we often use physical tokens as proofs of identity: passports, driverâ€™s

licenses, credit cards, and so on. The token contains something that links it to a per-

son: a picture, usually, or a signature, but it could almost as easily be a thumbprint, a

retinal scan, or a dental x-ray. Wouldnâ€™t it be nice to do the same thing digitally?

Using zero-knowledge proofs as proofs of identity was first proposed by Uriel

Feige, Amos Fiat, and Adi Shamir [566,567]. Aliceâ€™s private key becomes a function

of her â€śidentity.â€ť Using a zero-knowledge proof, she proves that she knows her pri-

vate key and therefore proves her identity. Algorithms for this can be found in Sec-

tion 23.11.

This idea is quite powerful. It allows a person to prove his identity without any

physical token. However, itâ€™s not perfect. Here are some abuses.

The Chess Grandmaster Problem

Hereâ€™s how Alice, who doesnâ€™t even know the rules to chess, can defeat a grand-

master. (This is sometimes called the Chess Grandmaster Problem.) She challenges

both Gary Kasparov and Anatoly Karpov to a game, at the same time and place, but

in separate rooms. She plays white against Kasparov and black against Karpov. Nei-

ther grandmaster knows about the other.

Karpov, as white, makes his first move. Alice records the move and walks into the

room with Kasparov. Playing white, she makes the same move against Kasparov.

Kasparov makes his first move as black. Alice records the move, walks into the

room with Karpov, and makes the same move. This continues, until she wins one

game and loses the other, or both games end in a draw.

In reality, Kasparov is playing Karpov and Alice is simply acting as the middleman,

mimicking the moves of each grandmaster on the otherâ€™s board. However, if neither

Karpov nor Kasparov knows about the otherâ€™s presence, each will be impressed with

Aliceâ€™s play.

This kind of fraud can be used against zero-knowledge proofs of identity [485,120].

While Alice is proving her identity to Mallory, Mallory can simultaneously prove to

Bob that he is Alice.

Page 110

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

The Mafia Fraud

When discussing his zero-knowledge identification protocol, Adi Shamir [ 14241

said: â€śI could go to a Mafia-owned store a million successive times and they will

still not be able to misrepresent themselves as me.â€ť

Hereâ€™s how the Mafia can. Alice is eating at Bobâ€™s Diner, a Mafia-owned restau-

rant. Carol is shopping at Daveâ€™s Emporium, an expensive jewelry store. Bob and

Carol are both members of the Mafia and are communicating by a secret radio link.

Alice and Dave are unaware of the fraud.

At the end of Aliceâ€™s meal, when she is ready to pay and prove her identity to Bob,

Bob signals Carol that the fraud is ready to begin. Carol chooses some expensive dia-

monds and gets ready to prove her identity to Dave. Now, as Alice proves her iden-

tity to Bob, Bob radios Carol and Carol performs the same protocol with Dave.

When Dave asks a question in the protocol, Carol radios the question back to Bob,

and Bob asks it of Alice. When Alice answers, Bob radios the correct answer to

Carol. Actually, Alice is just proving her identity to Dave, and Bob and Carol are

simply sitting in the middle of the protocol passing messages back and forth. When

the protocol finishes, Alice has proved herself to Dave and has purchased some

expensive diamonds (which Carol disappears with).

The Terrorist Fraud

If Alice is willing to collaborate with Carol, they can also defraud Dave. In this pro-

tocol, Carol is a well-known terrorist. Alice is helping her enter the country. Dave is

the immigration officer. Alice and Carol are connected by a secret radio link.

When Dave asks Carol questions as part of the zero-knowledge protocol, Carol

radios them back to Alice, who answers them herself. Carol recites these answers to

Dave. In reality, Alice is proving her identity to Dave, with Carol acting as a com-

munications path. When the protocol finishes, Dave thinks that Carol is Alice and

lets her into the country. Three days later, Carol shows up at some government

building with a minivan full of explosives.

Suggested Solutions

Both the Mafia and Terrorist frauds are possible because the conspirators can

communicate via a secret radio. One way to prevent this requires all identifications

to take place inside Faraday cages, which block all electromagnetic radiation. In the

terrorist example, this assures immigration officer Dave that Carol was not receiv-

ing her answers from Alice. In the Mafia example, Bob could simply build a faulty

Faraday cage in his restaurant, but jeweler Dave would have a working one; Bob and

Carol would not be able to communicate. To solve the Chess Grandmaster Problem,

Alice should be forced to sit in her seat until the end of a game.

Thomas Beth and Yvo Desmedt proposed another solution, one using accurate

clocks [148]. If each step in the protocol must take place at a given time, no time

would be available for the conspirators to communicate. In the Chess Grandmaster

Problem, if every move in each game must be made as a clock strikes one minute,

then Alice will have no time to run from room to room. In the Mafia story, Bob and

Carol will have no time to pass questions and answers to one another.

Page 111

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5.2 Zero-Knowledge Proofs of Identity

The Multiple Identity Fraud

There are other possible abuses to zero-knowledge proofs of identity, also dis-

cussed in [485,120]. In some implementations, there is no check when an individual

registers a public key. Hence, Alice can have several private keys and, therefore, sev-

eral identities. This can be a great help if she wants to commit tax fraud. Alice can

also commit a crime and disappear. First, she creates and publishes several identi-

ties. One of them she doesnâ€™t use. Then, she uses that identity once and commits a

crime so that the person who identifies her is the witness. Then, she immediately

stops using that identity. The witness knows the identity of the person who com-

mitted the crime, but if Alice never uses that identity again-sheâ€™s untraceable.

To prevent this, there has to be some mechanism by which each person has only

one identity. In [ 1201the authors suggest the bizarre idea of tamperproof babies who

are impossible to clone and contain a unique number as part of their genetic code.

They also suggested having each baby apply for an identity at birth. (Actually, the

parents would have to do this as the baby would be otherwise occupied.) This could

easily be abused; parents could apply for multiple identities at the childâ€™s birth. In

the end, the uniqueness of an individual is based on trust.

Renting Passports

Alice wants to travel to Zaire, but that government wonâ€™t give her a visa. Carol

offers to rent her identity to Alice. (Bob offered first, but there were some obvious

problems.) Carol sells Alice her private key and Alice goes off to Zaire pretending to

be Carol.

Carol has not only been paid for her identity, but now she has a perfect alibi. She

commits a crime while Alice is in Zaire. â€śCarolâ€ť has proved her identity in Zaire;

how could she commit a crime back home?

Of course, Alice is free to commit crimes as well. She does so either before she

leaves or after she returns, near Carolâ€™s home. First she identifies herself as Carol

(she has Carolâ€™s private key, so she can easily do that), then she commits a crime and

runs away. The police will come looking for Carol. Carol will claim she rented her

identity to Alice, but who would believe such a nonsensical story?

The problem is that Alice isnâ€™t really proving her identity; she is proving that she

knows a piece of secret information. It is the link between that information and the

person it belongs to that is being abused. The tamperproof baby solution would pro-

tect against this type of fraud, as would a police state where all citizens would have

to prove their identity very frequently (at the end of each day, at each street corner,

etc.). Biometric methods-fingerprints, retinal scanning, voiceprints, and so on-

may help solve this problem.

of Membership

Proofs

Alice wants to prove to Bob that she is a member of some super-secret organiza-

tion, but she does not want to reveal her identity. This problem is similar but dif-

ferent to proving identity, and has also been studied [887,906,907,1201,1445]. Some

solutions are related to the problem of group signatures (see Section 4.6).

Page 112

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

5.3 BLIND SIGNATURES

An essential feature of digital signature protocols is that the signer knows what he

is signing. This is a good idea, except when we want the reverse.

We might want people to sign documents without ever seeing their contents.

There are ways that a signer can almost, but not exactly, know what he is signing.

But first things first.

Completely Blind Signatures

Bob is a notary public. Alice wants him to sign a document, but does not want him

to have any idea what he is signing. Bob doesnâ€™t care what the document says; he is

just certifying that he notarized it at a certain time. He is willing to go along with this.

(1) Alice takes the document and multiplies it by a random value. This ran-

dom value is called a blinding factor.

(2) Alice sends the blinded document to Bob.

(3) Bob signs the blinded document.

(4) Alice divides out the blinding factor, leaving the original document signed

by Bob.

This protocol only works if the signature function and multiplication are com-

mutative. If they are not, there are other ways to modify the document other than

by multiplying. Some relevant algorithms appear in Section 23.12. For now, assume

that the operation is multiplication and all the math works.

Can Bob cheat? Can he collect any information about the document that he is

signing? If the blinding factor is truly random and makes the blinded document

â€˜truly random, he cannot. The blinded document Bob signs in step (2) looks nothing

like the document Alice began with. The blinded document with Bobâ€™s signature on

it in step (3) looks nothing like the signed document at the end of step (4). Even if

Bob got his hands on the document, with his signature, after completing the proto-

col, he cannot prove (to himself or to anyone else) that he signed it in that particu-

lar protocol. He knows that his signature is valid. He can, like anyone else, verify his

signature. However, there is no way for him to correlate any information he

received during the signing protocol with the signed document. If he signed a mil-

lion documents using this protocol, he would have no way of knowing in which

instance he signed which document.

The properties of completely blind signatures are:

1. Bobâ€™s signature on the document is valid. The signature is a proof that Bob

signed the document. It will convince Bob that he signed the document if

it is ever shown to him. It also has all of the other properties of digital sig-

natures discussed in Section 2.6.

2. Bob cannot correlate the signed document with the act of signing the doc-

ument. Even if he keeps records of every blind signature he makes, he can-

not determine when he signed any given document.

Page 113

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Eve, who is in the middle, watching this protocol, has even less information

than Bob.

Blind Signatures

With the completely blind signature protocol, Alice can have Bob sign anything:

â€śBob owes Alice a million dollars, â€ť â€śBob owes Alice his first-born child,â€ť â€śBob owes

Alice a bag of chocolates.â€ť The possibilities are endless. This protocol isnâ€™t useful in

many applications.

However, there is a way that Bob can know what he is signing, while still main-

taining the useful properties of a blind signature. The heart of this protocol is the

cut-and-choose technique. Consider this example. Many people enter this country

every day, and the Department of Immigration wants to make sure they are not

smuggling cocaine. The officials could search everyone, but instead they use a

probabilistic solution. They will search one-tenth of the people coming in. One

person in ten has his belongings inspected; the other nine get through untouched.

Chronic smugglers will get away with their misdeeds most of the time, but they

have a 10 percent chance of getting caught. And if the court system is effective, the

penalty for getting caught once will more than wipe out the gains from the other

nine times.

If the Department of Immigration wants to increase the odds of catching smug-

glers, they have to search more people. If they want to decrease the odds, they have

to search fewer people. By manipulating the probabilities, they control how suc-

cessful the protocol is in catching smugglers.

The blind signature protocol works in a similar manner. Bob will be given a large

pile of different blinded documents. He will open, that is examine, all but one and

then sign the last.

Think of the blinded document as being in an envelope. The process of blinding

the document is putting the document in an envelope and the process of removing

the blinding factor is opening the envelope. When the document is in an envelope,

nobody can read it. The document is signed by having a piece of carbon paper in the

envelope: When the signer signs the envelope, his signature goes through the carbon

paper and signs the document as well.

This scenario involves a group of counterintelligence agents. Their identities

are secret; not even the counterintelligence agency knows who they are. The

agencyâ€™s director wants to give each agent a signed document stating: â€śThe bearer

of this signed document, (insert agentâ€™s cover name here), has full diplomatic

immunity.â€ť Each of the agents has his own list of cover names, so the agency canâ€™t

just hand out signed documents. The agents do not want to send their cover names

to the agency; the enemy might have corrupted the agencyâ€™s computer. On the

other hand, the agency doesnâ€™t want to blindly sign any document an agent gives

it. A clever agent might substitute a message like: â€śAgent (name) has retired and

collects a million-dollar-a-year pension. Signed, Mr. President.â€ť In this case, blind

signatures could be useful.

Assume that all the agents have 10 possible cover names, which they have chosen

themselves and which no one else knows. Also assume that the agents donâ€™t care

Page 114

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

under which cover name they are going to get diplomatic immunity. Also assume

that the agencyâ€™s computer is the Agencyâ€™s Large Intelligent Computing Engine, or

ALICE, and that our particular agent is the Bogota Operations Branch: BOB.

(1) BOB prepares n documents, each using a different cover name, giving him-

self diplomatic immunity.

(2) BOB blinds each of these documents with a different blinding factor.

(3) BOB sends the n blinded documents to ALICE.

(4) ALICE chooses n - 1 documents at random and asks BOB for the blinding

factors for each of those documents.

(5) BOB sends ALICE the appropriate blinding factors.

(6) ALICE opens (i.e., she removes the blinding factor) n - 1 documents and

makes sure they are correct-and not pension authorizations.

(7) ALICE signs the remaining document and sends it to BOB.

(8) Agent removes the blinding factor and reads his new cover name: â€śThe

Crimson Streak.â€ť The signed document gives him diplomatic immunity

under that name.

This protocol is secure against BOB cheating. For him to cheat, he would have to

predict accurately which document ALICE would not examine. The odds of him

doing this are 1 in n-not very good. ALICE knows this and feels confident signing

a document that she is not able to examine. with this one document, the protocol

is the same as the previous completely blinded signature protocol and maintains all

of its properties of anonymity.

There is a trick that makes BOBâ€™s chance of cheating even smaller. In step (4)

ALICE randomly chooses n/2 of the documents to challenge, and BOB sends her the

appropriate blinding factors in step (5). In step (7) ALICE multiplies together all of

the unchallenged documents and signs the mega-document. In step (8) BOB strips

off all the blinding factors. ALICEâ€™s signature is acceptable only if it is a valid signa-

ture of the product of n/2 identical documents. To cheat BOB has to be able to guess

exactly which subset ALICE will challenge; the odds are much smaller than the

odds of guessing which one document ALICE wonâ€™t challenge.

BOB has another way to cheat. He can generate two different documents, one that

ALICE is willing to sign and one that ALICE is not. Then he can find two different

blinding factors that transform each document into the same blinded document. That

way, if ALICE asks to examine the document, BOB gives her the blinding factor that

transforms it into the benign document. If ALICE doesnâ€™t ask to see the document and

signs it, he uses the blinding factor that transforms it into the malevolent document.

While this is theoretically possible, the mathematics of the particular algorithms

involved make the odds of BOBâ€™s being able to find such a pair negligibly small. In fact,

it can be made as small as the odds of Bob being able to produce the signature on an

arbitrary message himself. This issue is discussed further in Section 23.12.

Page 115

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5.4 Identity-Based Public-Key Cryptography

Pa tents

Chaum has patents for several flavors of blind signatures (see Table 5.1).

5.4 IDENTITY-BASED PUBLIC-KEY CRYPTOGRAPHY

Alice wants to send a secure message to Bob. She doesnâ€™t want to get his public key

from a key server; she doesnâ€™t want to verify some trusted third partyâ€™s signature on

his public-key certificate; and she doesnâ€™t even want to store Bobâ€™s public key on her

own computer. She just wants to send him a secure message.

Identity-based cryptosystems, sometimes called Non-Interactive Key Sharing

(NIKS) systems, solve this problem [ 14221.Bobâ€™s public key is based on his name and

network address (or telephone number, or physical street address, or whatever).

With normal public-key cryptography, Alice needs a signed certificate that associ-

ates Bobâ€™s public key with his identity. With identity-based cryptography, Bobâ€™s pub-

lic key is his identity. This is a really cool idea, and about as ideal as you can get for

a mail system: If Alice knows Bobâ€™s address, she can send him secure mail. It makes

the cryptography about as transparent as possible.

The system is based on Trent issuing private keys to users based on their identity.

If Aliceâ€™s private key is compromised, she has to change some aspect of her identity

to get another one. A serious problem is designing a system in such a way that a col-

lusion of dishonest users cannot forge a key.

A lot of work has been done on the mathematics of these sorts of schemes-most

of it in Japan-which turn out to be infuriatingly complicated to make secure. Many

of the proposed solutions involve Trent choosing a random number for each user-

in my opinion this defeats the real point of the system. Some of the algorithms

discussed in Chapters 19 and 20 can be identity-based. For details, algorithms,

and cryptanalysis, see [191,1422,891,1022,1515,1202,1196,908,692,674,1131,1023,

1516,1536,1544,63,1210,314,313,1545,1539,1543,933,1517,748,1228]. An algorithm

that does not rely on any random numbers is 110351. The system discussed in

[1546,1547,1507] is insecure against a chosen-public-key attack; so is the system

proposed as NIKS-TAS [ 1542,1540,1541,993,375,1538]. Honestly, nothing proposed

so far is both practical and secure.

TABLE 5.1

Chaumâ€™s Blind Signature Patents

U.S. PATENT # DATE TITLE

4,759,063 7119188 Blind Signature Systems 13231

4,759,064 7119188 Blind Unanticipated Signature Systems [324]

4,914,698 313190 One-Show Blind Signature Systems [326]

4,949,380 8/14/90 Returned-Value Blind Signature Systems [328]

4,991,210 215191 Unpredictable Blind Signature Systems [331]

Page 116

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5 Advanced Protocols

CHAPTER

5.5 OBLIVIOUS TRANSFER

Cryptographer Bob is desperately trying to factor a 500-bit number, n. He knows itâ€™s

the product of five IOO-bit numbers, but nothing more. (This is a problem. If he canâ€™t

recover the key heâ€™ll have to work overtime and heâ€™ll miss his weekly mental poker

game with Alice.)

What do you know? Here comes Alice now:

â€śI happen to know one factor of the number,â€ť she says, â€śand Iâ€™ll sell it to you for

$100. Thatâ€™s a dollar a bit.â€ť To show sheâ€™s serious, she uses a bit-commitment

scheme and commits to each bit individually.

Bob is interested, but has only $50. Alice is unwilling to lower her price and

offers to sell Bob half the bits for half the price. â€śItâ€™ll save you a considerable

amount of work,â€ť she says.

â€śBut how do I know that your number is actually a factor of n! If you show me

the number and let me verify that it is a factor, then I will agree to your terms,â€ť

says Bob.

They are at an impasse. Alice cannot convince Bob that her number is a factor

of n without revealing it, and Bob is unwilling to buy 50 bits of a number that

could very well be worthless.

This story, stolen from Joe Kilian [831], introduces the concept of oblivious trans-

fer. Alice transmits a group of messages to Bob. Bob receives some subset of those

messages, but Alice has no idea which ones he receives. This doesnâ€™t completely

solve the problem, however. After Bob has received a random half of the bits, Alice

has to convince him that the bits she sent are part of a factor of n, using a zero-

knowledge proof.

In the following protocol, Alice will send Bob one of two messages. Bob will

receive one, and Alice will not know which.

(1) Alice generates two public-key/private-key key pairs, or four keys in all.

She sends both public keys to Bob.

(2) Bob chooses a key in a symmetric algorithm (DES, for example). He chooses

one of Aliceâ€™s public keys and encrypts his DES key with it. He sends the

encrypted key to Alice without telling her which of her public keys he used

to encrypt it.

(3) Alice decrypts Bobâ€™s key twice, once with each of her private keys. In one of

the cases, she uses the correct key and successfully decrypts Bobâ€™s DES key.

In the other case, she uses the wrong key and only manages to generate a

meaningless pile of bits that nonetheless look like a random DES key. Since

she does not know the correct plaintext, she has no idea which is which.

(4) Alice encrypts both of her messages, each with a different one of the DES

keys she generated in the previous step (one real and one meaningless) and

sends both of them to Bob.

(5) Bob gets one of Aliceâ€™s messages encrypted with the proper DES key and

the other one encrypted with the gibberish DES key. When Bob decrypts

Page 117

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

each of them with his DES key, he can read one of them; the other just

looks like gibberish to him.

Bob now has one of the two messages from Alice and Alice does not know which

one he was able to read successfully. Unfortunately, if the protocol stopped here it

would be possible for Alice to cheat. Another step is necessary.

(6) After the protocol is complete and both possible results of the transfer are

known, Alice must give Bob her private keys so that he can verify that she

did not cheat. After all, she could have encrypted the same message with

both keys in step (4).

At this point, of course, Bob can figure out the second message.

The protocol is secure against an attack by Alice because she has no way of know-

ing which of the two DES keys is the real one. She encrypts them both, but Bob only

successfully recovers one of them-until step (6). It is secure against an attack by

Bob because, before step (6), he cannot get Aliceâ€™s private keys to determine the DES

key that the other message was encrypted in. This may still seem like nothing more

than a more complicated way to flip coins over a modem, but it has extensive impli-

cations when used in more complicated protocols.

Of course, nothing stops Alice from sending Bob two completely useless mes-

sages: â€śNyah Nyahâ€ť and â€śYou sucker.â€ť This protocol guarantees that Alice sends

Bob one of two messages; it does nothing to ensure that Bob wants to receive either

of them.

Other oblivious transfer protocols are found in the literature. Some of them are

noninteractive, meaning that Alice can publish her two messages and Bob can learn

only one of them. He can do this on his own; he doesnâ€™t have to communicate with

Alice [ 1051.

No one really cares about being able to do oblivious transfer in practice, but the

notion is an important building block for other protocols. Although there are many

types of oblivious transfer-I have two secrets and you get one; I have n secrets and

you get one; I have one secret which you get with probability l/2; and so on-they

are all equivalent [245,391,395].

5.6 OBLIVIOUS SIGNATURES

Honestly, I canâ€™t think of a good use for these, but there are two kinds [346]:

1. Alice has n different messages. Bob can choose one of the n messages for

Alice to sign, and Alice will have no way of knowing which one she signed.

2. Alice has one message. Bob can choose one of n keys for Alice to use in

signing the message, and Alice will have no way of knowing which key

she used.

Itâ€™s a neat idea; Iâ€™m sure it has a use somewhere.

Page 118

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

5.7 SIMULTANEOUS CONTRACT SIGNING

Contract Signing with an Arbitrator

Alice and Bob want to enter into a contract. Theyâ€™ve agreed on the wording, but

neither wishes to sign unless the other signs as well. Face to face, this is easy: Both

sign together. Over a distance, they could use an arbitrator.

(1) Alice signs a copy of the contract and sends it to Trent.

(2) Bob signs a copy of the contract and sends it to Trent.

(3) Trent sends a message to both Alice and Bob indicating that the other has

signed the contract.

(4) Alice signs two copies of the contract and sends them to Bob.

(5) Bob signs both copies of the contract, keeps one for himself, and sends the

other to Alice.

(6) Alice and Bob both inform Trent that they each have a copy of the contract

signed by both of them.

(7) Trent tears up his two copies of the contract with only one signature each.

This protocol works because Trent prevents either of the parties from cheating. If

Bob were to refuse to sign the contract in step (5), Alice could appeal to Trent for a

copy of the contract already signed by Bob. If Alice were to refuse to sign in step (4),

Bob could do the same. When Trent indicates that he received both contracts in step

(3), both Alice and Bob know that the other is bound by the contract. If Trent does

not receive both contracts in steps (1) and (2), he tears up the one he received and

neither party is bound.

Simultaneous Contract Signing without an Arbitrator (Face-to-Face)

If Alice and Bob were sitting face-to-face, they could sign the contract this way

[ 12441:

(1) Alice signs the first letter of her name and passes the contract to Bob.

(2) Bob signs the first letter of his name and passes the contract to Alice.

(3) Alice signs the second letter of her name and passes the contract to Bob.

(4) Bob signs the second letter of his name and passes the contract to Alice.

(5) This continues until both Alice and Bob have signed their entire names.

If you ignore the obvious problem with this protocol (Alice has a longer name

than Bob), it works just fine. After signing only one letter, Alice knows that no judge

will bind her to the terms of the contract. But the letter is an act of good faith, and

Bob responds with a similar act of good faith.

After each party has signed several letters, a judge could probably be convinced

that both parties had signed the contract. The details are murky, though. Surely

Page 119

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

5.7 Simultaneous Contract Signing

they are not bound after only the first letter; just as surely they are bound after they

sign their entire names. At what point in the protocol do they become bound? After

signing one-half of their names? Two-thirds of their names? Three-quarters?

Since neither Alice nor Bob is certain of the exact point at which she or he is

bound, each has at least some fear that she or he is bound throughout the protocol.

At no point can Bob say: â€śYou signed four letters and I only signed three. You are

bound but I am not.â€ť Bob has no reason not to continue with the protocol. Fur-

thermore, the longer they continue, the greater the probability that a judge will

rule that they are bound. Again, there is no reason not to continue with the proto-

col. After all, they both wanted to sign the contract; they just didnâ€™t want to sign

before the other one.

Simultaneous Contract Signing without an Arbitrator (Not Face-to-Face)

This protocol uses the same sort of uncertainty [ 1381.Alice and Bob alternate tak-

ing baby steps toward signing until both have signed.

In the protocol, Alice and Bob exchange a series of signed messages of the form: â€śI

agree that with probability p, I am bound by this contract.â€ť

The recipient of this message can take it to a judge and, with probability p, the

judge will consider the contract to be signed.

(1) Alice and Bob agree on a date by which the signing protocol should be com-

pleted.

(2) Alice and Bob decide on a probability difference that they are willing to

live with. For example, Alice might decide that she is not willing to be

bound with a greater probability than 2 percent over Bobâ€™s probability. Call

Aliceâ€™s difference a; call Bobâ€™s difference b.

(3) Alice sends Bob a signed message with p = a.

(4) Bob sends Alice a signed message with p = a + b.

(5) Let p be the probability of the message Alice received in the previous step

from Bob. Alice sends Bob a signed message with pâ€™ = p + a or 1, whichever

is smaller.

(6) Let p be the probability of the message Bob received in the previous step

from Alice. Bob sends Alice a signed message with pâ€™ = p + b or 1,

whichever is smaller.

(7) Alice and Bob continue alternating steps (5) and (6) until both have

received messages with p = 1 or until the date agreed to in step (1) has

passed.

As the protocol proceeds, both Alice and Bob agree to be bound to the contract

with a greater and greater probability. For example, Alice might define her a as 2

percent and Bob might define his b as 1 percent. (It would be nice if they had cho-

sen larger increments; we will be here for a while.) Aliceâ€™s first message might

state that she is bound with 2 percent probability. Bob might respond that he is

Page 120

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

bound with 3 percent probability. Aliceâ€™s next message might state that she is

bound with 5 percent probability and so on, until both are bound with 100 percent

probability.

If both Alice and Bob complete the protocol by the completion date, all is well.

Otherwise, either party can take the contract to the judge, along with the other

partyâ€™s last signed message. The judge then randomly chooses a value between 0 and

1 before seeing the contract. If the value is less than the probability the other party

signed, then both parties are bound. If the value is greater than the probability, then

both parties are not bound. (The judge then saves the value, in case he has to rule on

another matter regarding the same contract.) This is what is meant by being bound

to the contract with probability p.

Thatâ€™s the basic protocol, but it can have more complications. The judge can rule

in the absence of one of the parties. The judgeâ€™s ruling either binds both or neither

party; in no situation is one party bound and the other one not. Furthermore, as long

as one party is willing to have a slightly higher probability of being bound than the

other (no matter how small), the protocol will terminate.

Simultaneous Contract Signing without an Arbitrator

(Using Cryptography)

This cryptographic protocol uses the same baby-step approach [529]. DES is used

in the description, although any symmetric algorithm will do.

(1) Both Alice and Bob randomly select 2n DES keys, grouped in pairs. The

pairs are nothing special; they are just grouped that way for the protocol.

(2) Both Alice and Bob generate n pairs of messages, Li and Ri: â€śThis is the left

half of my ith signatureâ€ť and â€śThis is the right half of my ith signature,â€ť

for example. The identifier, i, runs from 1 to n. Each message will probably

also include a digital signature of the contract and a timestamp. The con-

tract is considered signed if the other party can produce both halves, Li and

Ri, of a single signature pair.

(3) Both Alice and Bob encrypt their message pairs in each of the DES key

pairs, the left message with the left key in the pair and the right message

with the right key in the pair.

(4) Alice and Bob send each other their pile of 2n encrypted messages, making

clear which messages are which halves of which pairs.

(5) Alice and Bob send each other every key pair using the oblivious transfer

protocol for each pair. That is, Alice sends Bob either the key used to

encrypt the left message or the key used to encrypt the right message, inde-

pendently, for each of the n pairs. Bob does the same. They can either alter-

nate sending halves or one can send 100 and then the other-it doesnâ€™t

matter. Now both Alice and Bob have one key in each key pair, but neither

knows which halves the other one has.

(6) Both Alice and Bob decrypt the message halves that they can, using the

keys they received. They make sure that the decrypted messages are valid.

Page 121

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

(7) Alice and Bob send each other the first bits of all 2n DES keys.

(8) Alice and Bob repeat step (7) for the second bits of all 2n DES keys, the

third bits, and so on, until all the bits of all the DES keys have been trans-

ferred.

(9) Alice and Bob decrypt the remaining halves of the message pairs and the

contract is signed.

(10) Alice and Bob exchange the private keys used during the oblivious transfer

protocol in step (5) and each verifies that the other did not cheat.

Why do Alice and Bob have to go through all this work? Letâ€™s assume Alice wants

to cheat and see what happens. In steps (4) and (5), Alice could disrupt the protocol

by sending Bob nonsense bit strings. Bob would catch this in step (6), when he tried

to decrypt whatever half he received. Bob could then stop safely, before Alice could

decrypt any of Bobâ€™s message pairs.

If Alice were very clever, she could only disrupt half the protocol. She could send

one half of each pair correctly, but send a gibberish string for the other half. Bob has

only a 50 percent chance of receiving the correct half, so half the time Alice could

cheat. However, this only works if there is one key pair. If there were only two pairs,

this sort of deception would succeed 2.5percent of the time. That is why n should be

large. Alice has to guess correctly the outcome of n oblivious transfer protocols; she

has a 1 in 2â€ť chance of doing this. If n = 10, Alice has a 1 in 1024 chance of deceiv-

ing Bob.

Alice could also send Bob random bits in step (8). Perhaps Bob wonâ€™t know that

she is sending him random bits until he receives the whole key and tries to decrypt

the message halves. But again, Bob has probability on his side. He has already

received half of the keys, and Alice does not know which half. If n is large enough,

Alice is sure to send him a nonsense bit to a key he has already received and he will

know immediately that she is trying to deceive him.

Maybe Alice will just go along with step (8) until she has enough bits of the keys to

mount a brute-force attack and then stop transmitting bits. DES has a 56-bit-long key.

If she receives 40 of the 56 bits, she only has to try 216,or 65,536, keys in order to read

the message-a task certainly within the realm of a computerâ€™s capabilities. But Bob

will have exactly the same number of bits of her keys (or, at worst, one bit less), so he

can do the same thing. Alice has no real choice but to continue the protocol.

The basic point is that Alice has to play fairly, because the odds of fooling Bob are

just too small. At the end of the protocol, both parties have n signed message pairs,

any one of which is sufficient for a valid signature.

There is one way Alice can cheat; she can send Bob identical messages in Step (5).

Bob canâ€™t detect this until after the protocol is finished, but he can use a transcript

of the protocol to convince a judge of Aliceâ€™s duplicity.

There are two weaknesses with protocols of this type [ 1381.First, itâ€™s a problem if

one of the parties has significantly more computing power than the other. If, for

example, Alice can mount a brute-force attack faster than Bob can, then she can stop

sending bits early in step (8), and figure out Bobâ€™s keys herself. Bob, who cannot do

the same in a reasonable amount of time, will not be happy.

Page 122

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

Second, itâ€™s a problem if one of the parties stops the protocol early. If Alice

abruptly stops the protocol, both face similar computational efforts, but Bob does

not have any real legal recourse. If, for example, the contract specifies that she do

something in a week, and Alice terminates the protocol at a point when Bob would

have to spend a yearâ€™s worth of computing power before she is really committed,

thatâ€™s a problem. The real difficulty here is the lack of a near-term deadline by

which the process cleanly terminates with either both or neither party bound.

These problems also apply to the protocols in Sections 5.8 and 5.9.

5.8 MAIL

DIGITAL CERTIFIED

The same simultaneous oblivious transfer protocol used for contract signing works,

with some modifications, for computer certified mail [529]. Suppose Alice wants to

send a message to Bob, but she does not want him to read it without signing a

receipt. Surly postal workers handle this process in real life, but the same thing can

be done with cryptography. Whitfield Diffie first discussed this problem in [490].

At first glance, the simultaneous contract-signing protocol can do this. Alice sim-

ply encrypts her message with a DES key. Her half of the protocol can be something

like: â€śThis is the left half of the DES key: 32f5,â€ť and Bobâ€™s half can be something

like: â€śThis is the left half of my receipt.â€ť Everything else stays the same.

To see why this wonâ€™t work, remember that the protocol hinges on the fact that

the oblivious transfer in step (5) keeps both parties honest. Both of them know that

they sent the other party a valid half, but neither knows which. They donâ€™t cheat in

step (8) because the odds of getting away with it are miniscule. If Alice is sending

Bob not a message but half of a DES key, Bob canâ€™t check the validity of the DES key

in step (6). Alice can still check the validity of Bobâ€™s receipt, so Bob is still forced to

be honest. Alice can freely send Bob some garbage DES key, and he wonâ€™t know the

difference until she has a valid receipt. Tough luck, Bob.

Getting around this problem requires some adjustment of the protocol:

(1) Alice encrypts her message using a random DES key, and sends the mes-

sage to Bob.

(2) Alice generates n pairs of DES keys. The first key of each pair is generated

at random; the second key of each pair is the XOR of the first key and the

message encryption key.

(3) Alice encrypts a dummy message with each of her 2n keys.

(4) Alice sends the whole pile of encrypted messages to Bob, making sure he

knows which messages are which halves of which pairs.

(5) Bob generates n pairs of random DES keys.

(6) Bob generates a pair of messages that indicates a valid receipt. â€śThis is the

left half of my receiptâ€ť and â€śthis is the right half of my receiptâ€ť are good

candidates, with the addition of some kind of random-bit string. He makes

n receipt pairs, each numbered. As with the previous protocol, the receipt

Page 123

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

is considered valid if Alice can produce both halves of a receipt (with the

same number) and all of her encryption keys.

Bob encrypts each of his message pairs with DES key pairs, the ith message

(7)

pair with the ith key pair, the left message with the left key in the pair, and

the right message with the right key in the pair.

Bob sends his pile of message pairs to Alice, making sure that Alice knows

(8)

which messages are which halves of which pairs.

(9) Alice and Bob send each other every key pair using the oblivious transfer

protocol. That is, Alice sends Bob either the key used to encrypt the left

message or the key used to encrypt the right message, for each of then pairs.

Bob does the same. They can either alternate sending halves or one can send

n and then the other-it doesnâ€™t matter. Now both Alice and Bob have one

key in each key pair, but neither knows which halves the other has.

(10) Both Alice and Bob decrypt the halves they can and make sure that the

decrypted messages are valid.

Alice and Bob send each other the first bits of all 2n DES keys. (If they are

(11)

worried about Eve being able to read these mail messages, then they should

encrypt their transmissions to each other.)

(12) Alice and Bob repeat step (11) for the second bits of all 2n DES keys, the

third bits, and so on, until all the bits of all the DES keys have been

transferred.

Alice and Bob decrypt the remaining halves of the message pairs. Alice has

(13)

a valid receipt from Bob, and Bob can XOR any key pair to get the original

message encryption key.

Alice and Bob exchange the private keys used during the oblivious transfer

(14)

protocol and each verifies that the other did not cheat.

Steps (5) through (8) for Bob, and steps (9) through (12) for both Alice and Bob, are

the same as the contract-signing protocol. The twist is all of Aliceâ€™s dummy mes-

sages. They give Bob some way of checking the validity of her oblivious transfer in

step (lo), which forces her to stay honest during steps (11) through (13). And, as with

the simultaneous contract-signing protocol, both a left and a right half of one of

Aliceâ€™s message pairs are required to complete the protocol.

5.9 SIMULTANEOUS EXCHANGE OF SECRETS

Alice knows secret A; Bob knows secret B. Alice is willing to tell Bob A, if Bob tells

her B. Bob is willing to tell Alice B, if Alice tells him A. This protocol, observed in

a schoolyard, does not work:

(1) Alice: â€śIâ€™ll tell if you tell me first.â€ť

(2) Bob: â€śIâ€™ll tell if you tell me first.â€ť

Page 124

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER Advanced Protocols

5

(3) Alice: â€śNo, you first.â€ť

(4) Bob: â€śOh, all right.â€ť Bob whispers.

Alice: â€śHa! I wonâ€™t tell you.â€ť

(5)

(6) Bob: â€śThatâ€™s not fair.â€ť

Cryptography can make it fair. The previous two protocols are implementations

of this more general protocol, one that lets Alice and Bob exchange secrets simulta-

neously [529]. Rather than repeat the whole protocol, Iâ€™ll sketch the modifications

to the certified mail protocol.

Alice performs steps (1) through (4) using A as the message. Bob goes through sim-

ilar steps using B as his message. Alice and Bob perform the oblivious transfer in

step (9) decrypt the halves they can in step (lo), and go through the iterations in

steps (11) and (12). If they are concerned about Eve, they should encrypt their mes-

sages. Finally, both Alice and Bob decrypt the remaining halves of the message pairs

and XOR any key pair to get the original message encryption key.

This protocol allows Alice and Bob to exchange secrets simultaneously, but says

nothing about the quality of the secrets exchanged. Alice could promise Bob the

solution to the Minotaurâ€™s labyrinth, but actually send him a map of Bostonâ€™s sub-

way system. Bob will get whatever secret Alice sends him. Other protocols are

[1286,195,991,1524,705,753,259,358,415].