Coin flipping by telephone: a protocol for solving impossible problems

(1)

COIN F L I P P I N G BY T E L E P H O N E

A PROTOCOL FOR SOLVING I M P O S S I B L E PROBLEMS

Manuel Blt~* D e p a r t m e n t of E l e c t r i c a l E n g i n e e r i n g and C o m p u t e r Sciences C o m p u t e r S c i e n c e Division U n i v e r s i t y of C a l i f o r n i a at Berkeley N o v e m b e r 10, 1981 A b s t r a c t

Alice and Bob want to flip a coin by telephone. (They h a v e just divorced, live in d i f f e r e n t cities, want to d e c i d e who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes... I'm flipping the coin .... You lost!"

C o i n - f l i p p i n g in the S P E C I A L way done here has a serious purpose. Indeed, it should prove an I N D I S P E N S A B L E T O O L of the protocol designer. When- ever a protocol r e q u i r e s one of two adversaries, say Alice, to pick a s e q u e n c e of bits at random, and w h e n e v e r it serves Alice's i n t e r e s t s best NOT to pick her s e q u e n c e of bits at random, then coin- flipping (Bob flipping coins to Alice) as defined here achieves the d e s i r e d goal:

I. It G U A R A N T E E S to Bob that Alice will pick her s e q u e n c e of hits at random. Her bit is } if Bob flips h e a d s to her, 0 otherwise.

2. It G U A R A N T E E S to Alice that Bob will not k n o w W H A T s e q u e n c e of bits he flipped to her.

C o i n - f l i p p i n g has a l r e a d y proved useful in s o l v i n g a n u m b e r of p r o b l e m s once thought impossible: m e n t a l poker, c e r t i f i e d mail, and exchange of secrets. It will c e r t a i n l y prove a useful tool in solving ether problems as well.

I n t r o d u c t i o n

F l i p p i n g coins by telephone is EASY, as we show below, if one a s s u m e s the e x i s t e n c e of a C O M P L E T E L Y SECURE o n e - w a y function. A ( N O R M A L L Y SECURE) 0 R E - W A Y FUNCTION is an e f f i c i e n t l y c o m p u t a b l e f u n c t i o n of some set into itself whose inverse cannot he computed e f f i c i e n t l y except on a n e g l i g i b l e fraction of values. A C O M P L E T E L Y S E C U R E 0RE-WAY F U N C T I O N has the a d d i t i o n a l property that from a k n o w l e d g e of f(x), one cannot have more than a 50-50 chance to guess e f f i c i e n t l y if x has some n o n t r i v i a ! property, e.g., is even (lab : O) or odd (]sb = I).

To flip coins, Alice and Bob should agree on a c o m p l e t e l y secure I-I o n e - w a y function f. Alice then selects an i n t e g e r x u n k n o w n to Bob, computes f(x) and sends f(x) to Bob. Bob, who cannot d e t e r m i n e some n o n t r i v i a l p r o p e r t y of x from f(x), tells Alice w h e t h e r he thinks x is even or odd (this is where Bob flips a coin to Alice). At this point, Alice can tell if he guessed right or wrong. To c o n v i n c e Bob, she sends him x.

Such c o m p l e t e l y secure o n e - w a y functions, how- ever, m a y not only be hard to discover, they may not

* S u p p o r t e d in part by N S F grant MCS 7 9 - 0 3 7 6 7

even exist. We show how a n o r m a l l y secure one-way f u n c t i o n can be used to flip coins in a c o m p l e t e l y secure fashion. Our o n e - w a y function is 2-I, i.e., it raaps exactly two elements from its d o m a i n to each element of its range. A simple property, say even or oddness, will d i s t i n g u i s h the two elements x,y that map to the same element f(x) = f(y). If Alice selects x and sends f(x) to Bob, he A B S O L U T E L Y CAN- NOT D E T E R M I N E w h e t h e r she selected the x or the y, x y, such that f(x) = f(y). He g u e s s e s w h e t h e r she picked the even or odd number. His guess as told to Alice c o n s t i t u t e s his coin flip to her. Since f is one-way, Alice cannot cheat, i.e., cannot tell him y if in fact she selected x.

A c o i n - f l i p p i n g protocol with the right properties, of which the one p r e s e n t e d here is an example, has numerous applications, eg., to the e x c h a n g e of Isecret) keys [B'81], to the c e r t i f i e d mail problem |BR '81] and to the s o l u t i o n of mental poker [SRA'78] W I T H O U T c o m m u t a t i v e locks [MG'81]. The RIGHT P R O P E R T I E S are:

~. If either p a r t i c i p a n t f o l l o w i n g protocol does not catch the other cheating, he or she can be sure that the coins each have exactly 50-50 i n d e p e n d e n t chance to come up heads (provable u n d e r the r e a s o n a b l e a s s u m p t i o n that factoring is hard ~ .

2. If either p a r t i c i p a n t catches the other cheating, he or she can prove it to a judge (this assumes that all m e s s a g e s are sent signed). 3- After Bob flips coins to Alice, she knows which

coins came up heads, w h i c h tails. He should have a b s o l u t e l y NO idea how they came up (not even a good guess).

4. A f t e r the s e q u e n c e of coin flips, Alice should be able to prove to Bob w h i c h coins came up heads, w h i c h tails.

A COIiI-PI,IPP[}/C P R O T O C O L WITH THESE P R O P E R T I E S CAN BE USED [~ ANY PROTOCOL THAT REQUIRES ONE OF TWO ADVERSARIES, SAY ALICE, TO G E N E R A T E AND USE A RANDOM NUMBER, x, W I T H O U T R E V E A L I N G IT TO HER OPPO~[ENT, BOB. EVEN IF IT IS TO HER A D V A N T A G E TO SELECT A PAR- T I C U L A R N O N R A N D O M x, SHE WILL NOT BE A B L E TO DO SO. BOB FORCES ALICE TO CHOOSE x AT R A N D O M BY FLIPPING C O I N S TO HER.

THE R E S U L T I N G S E Q U E N C E OF BITS IS C O M P L E T E L Y UNKNOWN TO BOB AND, P R O V I D E D BOB FOLLOWS PROTOCOL, COM- P L E T E L Y RANDOM. ALICE USES THE S E Q U E N C E AS THE R E Q U I R E D RANDOM NUMBER, x. LATER, SHE PROVES TO BOB T H A T HE F L I P P E D THE S E Q U E N C E x TO HER, THUS A S S U R I N G HIM IT WAS C H O S E N AT RANDOM.

(2)

In a d d i t i o n to the above properties, the coin- flipping protocol presented here h a s the following useful properties:

I. Each participant K N O W S at each step a l o n g the way if the o t h e r cheated. He or she does not require later p r o o f (e.g., a f t e r Alice has revealed the result of the c o i n - f l i p s to Bob) to d e t e r m i n e this. The c o u r t is needed only to provide justice, to give i n d e p e n d e n t p r o o f o f w r o n g (or right) doing, or to force an adver- sary to c o m p l e t e the protocol.

2. Bob can use his publlc-key, n, provided it is constructed correctly, to flip coins.

3. Bob does not h a v e to create n e w primes for each coin-flip. E a c h c o i n - f l i p o n l y requires compu- tation time of the order the time required to compute a Jacobi symbol, (x/n), for 0 < x < n and n = a 1SO-digit number. The Jacobi symbol, (x/n), can be computed quickly, in the same order of time required to c o m p u t e the g r e a t e s t c o m m o n divisor, gcd (x,y).

ASSUMPTIONS:

I. Factorization: We a s s u m e that no p r o c e d u r e can e f f i c i e n t l y factor a n u m b e r n that is a product of two large primes, except for a n e g l i g i b l e fraction of such n u m b e r s n. In 1980 technology, this means that a p r o d u c t of two 8 0 - d i g i t primes cannot be factored in r e a s o n a b l e time (not even 5 years) using the most advanced available technology (1000 C R A Y - I ' s w o r k i n g in parallel) on any but a n e g l i g i b l e fraction (one in Avogadro's number) of such numbers. A c o i n - f l i p p i n g pTotocol based on the intracta- b i l i t y of the d i s c r e t e l o g a r i t h m rather than f a c t o r i z a t i o n appears in iBM'S1].

2. R a n d o m Number Generation: We a s s u m e that Bob a n d Alice each have their own true random n u m b e r generators. The c o i n - f l i p p i n g protocol shows hot the random m nber g e n e r a t o r s enable Bob to generate and flip random bits to Alice. Signatures: Some o f the m e s s a g e s in the protocol below are required to be signed. We assume the existence of a secure s i g n a t u r e scheme of the sort first s u g g e s t e d by D i f f i e and H e l l m a n in 1976 [DH'79], and as i m p l e m e n t e d by Rivest, Shamir, and Adleman [RSA'78] and Rabin [R'79]. Signed messages are placed in q u o t e s and terminated with the s i g n e r ' s name. It is expected that each p a r t i c i p a n t k n o w s (from the protocol) if the m e s s a g e h e or she r e c e i v e s is supposed to be signed and refuses to continue the exchange unless the received m e s s a g e IS prop- erly signed.

3.

T H E JACOBI SYMBOL:

The Jaeobi symbol (x/n) is defined for odd p o s i t i v e integers n and a r b i t r a r y ( p o s i t i v e and negative) integers x. It has values O, +I, or -I. As pointed out earlier, the c o m p u t a t i o n of (x/n) is s i m i l a r to the c o m p u t a t i o n of ~cd(x~n) and takes the same order of time to compute [A'78J. An a l g o r i t h m for comput- ing (x/n) can easily be c o n s t r u c t e d from the following of its properties:

x, xl, x2, ... are a r b i t r a r y (positive o r negative) integers, n, nl, n2, ... are positive odd integers:

1. ( x / n ) = o i f gcd ( ~ , n ) / I 2. (I/n) = 1 3. ( ( x l * x 2 ) / n ) = ( x l / n ) * ( x 2 / n ) 4. (xl(n1*n2)) = (xlnl)W(x/n2) 5. (xl/n) = (x2/n) if xl = x2 mod n 6. (-I/n) = +I if n = I mod 4 -I i f n = 3 rood 4 7. (2/n) = +I if n = I or 7 mod 8 -I if n = 3 or 5 rood 8 8 . ( n t l n 2 ) = ( n 2 / n l ) i f gcd ( n l , n 2 ) = 1 and [nl or n2 = 1 mod 4 ] - ( n 2 / n l ) i f ged ( n l , n 2 ) = 1

and [nl and n2 = 3 mod 4] EXAMPLE: ( 2 3 / 5 9 ) = - ( 5 9 / 2 3 ) = - ( 1 3 / 2 3 ) =

- ( 2 3 / 1 3 ) = - ( 1 0 / 1 3 ) =

- ( 2 / 1 3 ) * ( 5 / 1 3 ) = ( 5 / 1 3 ) = ( 1 3 / 5 ) = ( 3 1 5 ) = ( 5 1 3 ) = ( 2 1 3 ) ~ -I.

T H E G R O U P Zn*

For n a positive i n t e g e r g r e a t e r than I, define Zn* to be the g r o u p of positive integers less than n that are r e l a t i v e l y p r i m e to n, the group o p e r a t i o n b e i n g m u l t i p l i c a t i o n mod n.

LEMMA

Let n = pl el * • * pk sk , where k is an integer g r e a t e r than I; p ] , . . . , p k are distinct odd primes; and e l , . . . , e k are p o s i t i v e integers. Let a in Zn* be a q u a d r a t i c residue (square of an integer) mod n. T h e n every s o l u t i o n in Zn* of x 2 = a mod n is of the form

EQ I: x [ ~ ( x | * v 1 * p 2 e 2 * "'" * pkek) ! (x2*v2*plel ~ ... * pkek) ~ ... ~ (xk*vk*pl el • . . . * p ( k - 1 ) e ( k - 1 ) ) ] mod n,

where vl is any i n t e g e r such that (v1*p2 e2 * ... * pk ek) mod pl e l = I [ f o o t n o t e lJ. v 2 , . . . , v k are d e f i n e d similarly.

P R O O F

See LeVeque [L'77], T h e o r e m s 3.21 & 5,2. iii

111 T H E O R E M 7

If n is any odd p o s i t i v e integer, so n = pl el * . . . * p k ek is d e f i n e d as in the statement of the lemma except that k = I is also permitted, then I, 2, 3 are equivalent:

I. there exist x,y in Zn* such that x 2 = y2 mod n a n d ( x / n ) / ( y / n ) .

2. pi ei = 3 mod 4 for some i.

3. Let a in Zn* be a quadratic residue mod n. Then e x a c t l y h a l f the roots in Zn* of the equa- tion a = x 2 mod n have Jacobi symbol (x/n) = +I (the other h a l f h a v e (x/n) = -I).

P R O O F

[ f o o t n o t e I]: vl is easily generated by the Eu- c l i d e a n a l g o r i t h m 2 which, when aoolied to the en- tries in gcd (pl el, p2e2 . ... ,~kek) = I, yields integers ul, vl such that u1*pl e] + v1*p2 e2 * ... • pk eK = I ) .

(3)

I => 2: S u p p o s e to the c o n t r a r y that pi ei = I mod 4 for all i. Let a in Zn* be a n y q u a d r a t i c residue mod n. If k = I, then a = x 2 mod n has e x a c t l y two roots, x and -x [footnote 2]. These s a t i s f y

( x / n ) = (x/n)*(-I/n) since (-I/n) =

+i when n = i mod 4 = ( - x / n ) .

This c o n t r a d i c t s I for k = I.

If k > I, then by the lemma, x s a t i s f i e s equa- tion I. Therefore,

(x/p~e~) = (x1/p~el)

(-xl/pl el) since (-I/pi el) = ÷I. Therefore, a n y two s o l u t i o n s x,y s a t i s f y (x/pl el)

(y/plel). Similarly, (x/p2 e2) =

( y / p 2 e 2 ) , . . . , ( x / p k ek) = (y/pkek). T h e r e f o r e (x/n) = (y/u). This c o n t r a d i c t s 9.

2 => 3: E q u a t i o n I gives all roots of a = x 2 mod n. Let the root y be obtained from x by c h a n g i n g the sign of xi, where pi ei = 3 mod 4. T h e n (x/n) = ( x / p ~ e ~ ) * . . . * ( x / p k e k ) = _ ( y / p l e l ) * . . . * ( y / p k eK)

-(y/n).

3 => 1 : I m m e d i a t e . i [ i

P U B L [ C A T I O N DATE OF n

In the first m e s s a g e of the following protocol, Bob reveals a n u m b e r n together with its P U B L I C A T I O N DATE defined to be the date on w h i c h it was first published. A s t a t u t e of l i m i t a t i o n s p r o h i b i t s either party from b r i n g i n g the other to court, say, 5 years a f t e r that p u b l i c a t i o n date. This limita- tion is needed for several reasons:

I. Bob cannot expect the prime f a c t o r i z a t i o n of his n u m b e r n to remain h i d d e n for m o r e than 5 years, and once it is out, Alice can fool the judge (but this problem can be avoided w i t h o u t a s t a t u t e of limitations by h a v i n g Alice sign an a d d i t i o n a l m e s s a g e below).

2. It is u n r e a s o n a b l e to demand that Alice and Bob k e e p their c o r r e s p o n d e n c e for longer than some fixed l e n g t h of time (5 years).

We assume that each of the parties is a w a r e of this l i m i t a t i o n and do not m e n t i o n it further.

THE PROTOCOL: BOB FLIPS COINS TO ALICE I. BOB SELECTS n [footnote 3]:

[footnote 2]: By ~buse of notation, we a s s i g n to x a dual use as v a r i a b l e (in the e q u a t i o n a = x 2 mod n) and as c o n s t a n t (a p a r t i c u l a r s o l u t i o n of a = x 2 mod n).

[footnote 3]: A T R U S T E D INTERMEDIARY may be used to select n. }{e must c h o o s e n at random a c c o r d i n g to the rules given Bob. If the i n t e r m e d i a r y is trusted by the entire world (trusted to select n a c c o r d i n g to the rules and not to give away the primes), then everyone can use n to flip coins to everyone else. It is not n e c e s s a r y for either Bob or Alice to k n o w the prime factors of n in order for Bob to flip coins to Alice. In fact, Alice - or whoever is re- ceiving the flipped coin - should NOT know the prime f a c t o r i z a t i o n of n, else she can cheat Bob.

Bob selects a t r a n d o m two d i s t i n c t (exactly) 80- digit primes pl, p2, both c o n g r u e n t to 3 mod 4; i.e., he r e p e a t e d l y s e l e c t s 8 0 - d i g i t n u m b e r s at random and tests each until he o b t a i n s two primes b o t h c o n g r u e n t to 5 mod 4 [footnote 4]. He m u l t i p l i e s these together to get n = p1*p2.

B => A: Bob sends A l i c e "My c o i n - f l i p p i n g m ~ b e r is n. Its p u b l i c a t i o n d a t e is M a y 27, ~980. - signed Bob."

II. ALICE TESTS n:

If Alice trusts that n is a 1 6 e - d i g i t p r o d u c t of two primes, both c o n g r u e n t to 3 mod 4, then this part o f the protocol m a y be skipped. Otherwise, A l i c e c h e c k s that n has the f o l l o w i n g two p r o p e r t i e s [ f o o t n o t e 5]:

a) Alice checks that n is a 160-digit n u m b e r and that u = I mod 4. The latter implies that n is odd and (-I/n) = +I.

b) Alice checks that for S O M ~ x there is almost s u r e l y a y such that x 2 = y ~ mod n and (x/n) (y/n), as follows:

B => A: Bob selects 80 (distinct) numbers x 1 , . . . , x 8 0 c h o s e n at random from Zn* (it is in HIS i n t e r e s t to s e l e c t these numbers at random). H e sends xl 2 mod n , . . . , x 8 0 2 mod n to Alice [ f o o t n o t e 6].

B => B: Alice sends Bob a s e q u e n c e of 80 randomly chosen bits, bl,...,b80, where each bi = +I or -1 .

B => A: Let xi 2 = yi 2 mod n where (xi/n) = +I, • (yi/n) = -I. (By T h e o r e m I, two such r o o t s must exist for every i.) Bob sends Alice a particular s e q u e n c e of 80 numbers: for each i, from i = I to i = SO~ he sends Alice xi if bi = +I, or yi if bi = -I.

This convinces Alice that c o n d i t i o n J of Theorem I h o l d s (it fails with p r o b a b i l i t y I/280 < ]/Avo~adro's number) [ f o o t n o t e 7].

From this point on, the number n has b e e n tested and Alice does not have to retest it.

[footnote 4]: P R I M A L I T Y TEST A l i c e and Bob can test if an 8 0 - d i g i t n u m b e r is prime u s i n g one of the ef- ficient algorithms for p r i m a l i t y of Gary M i l l e r [M'76], S t r a s s e n and S o l o v a y [SS'77], or R a b i n [R'80]. A p p r o x i m a t e l y h a l f o f all the 8 0 - d i g i t primes are c o n g r u e n t to 3 mod 4.

[ f o o t n o t e 5]: The two p r o p e r t i e s do not prove that n is a product of two d i s t i n c t primes b o t h c o n g r u e n t to 3 nod a (it m i g h t for example be a product of three d i s t i n c t primes, two of the~ congruent to 3 nod 4), but they s u f f i c e to prove that (with ex- tremely high p r o b a b i l i t y ) the p r o t o c o l is trustworthy.

[footnote 6]: Alice d o e s not have to check if the n u m b e r s she receives a r e d i s t i n c t or quadratic resi- dues mod n r e l a t i v e l y p r i m e to n. This c h e c k is au- t o m a t i c a l l y part of the following B => A message. [footnote 7]: Alice h a s NOT proved that n is a product of just two primes - she has just "proved" that n satisfies s t a t e m e n t I of T h e o r e m I, which is all she n e e d s to know. It will a c t u a l l y be in Bob's in- terest to make n a product of just two primes to prevent Alice from

factoring

n within the 5 - y e a r statute of limitations.

(4)

III. BOB PLIPS COINS TO ALICE:

For this protocol to hold in court, messages exchanged in this part (as in I but not If) are signed before delivery. Alice checks that the publication date is within an acceptable tolerance, e.g., within I year of the current date, else aborts. If she accepts the publication date, then Bob and Alice can flip 80 (or any number of) coins as follows:

A => B: Alice selects 80 numbers xl,...,xSO in Zn* at random. She sends Bob "n, ~ublication date of n, xl 2 mod n,..., xSO L mod n - signed Alice."

The purpose in sending n is for the court to know which of perhaps several transactions this is.

This is a delicate point in the negotiations for Alice. The delicacy has to do with the publication date. If Bob does not respond to the above message, he could nevertheless take Alice to court, saying he sent her his guess (+ I) and she didn't pursue the matter (he claims sue probably lost the coin-toss). With the judge's protocol given here, the court would then enforce completion of the protocol. If Bob does not wish to continue, it would be a courtesy for him to tell her so in a signed message. The protocol could then stop here. It can stop here anyway provided Alice understands that she may be forced to continue the protocol in court. If this is inconvenient, she should take Bob to court and get a letter from the judge terminating this protocol.

At this point, Bob should check that Alice sent him the correct n and the correct publication date (if not, he should ask her to stop fooling around). Bob cannot tell if (xi/n) = +I or -I since by 3 of Theorem I, xi 2 mod n has as many roots with (xi/n) = +I as it has with (xi/n) = -I (this is true even if Bob did not choose n to be a product of two primes). B => A: Bob sends Alice "n, xl 2 mod n,..., xSO 2 mod

n, b1,...,beO .- sig~ed Bob" [footnote 8]. Alice should check that n, xl 2 mod n,..., x802 mod n have not been altered (if so, she asks Bob to stop fooling around). Alice now determines her sequence of random bits: her ith random bit is ri = +I if Bob guessed right about xi; -I if he guessed wrong.

At this point in the protocol, Alice knows what Bob flipped to her; Bob has absolutely no idea. Whenever she wants to prove to Bob what sequence rl,...,rSO of random bits was flipped to her, she sends the confirmation message:

A => B: Alice sends xi,...,×80 to Bob.

This message need nut be signed, but in that case Bob must make sure his factorization of n will not be given away during the next 5 years. If Alice DOES sign this message, then the statute of limitations need NOT apply.

To guard against Alice cheating, Bob computes xl 2 mod n,..., x802 mod n and compares them with what Alice sent him: if they do not agree, then Alice cheated. If they do agree, he computes (xl/n),...,(xSO/n) and thereby determines rl,...,rSO

[footnote ~]: The extra information, i.e., n, xl 2 mod n,..., xSO 2 mod n, enables the courts to know which of perhaps several transactions this is.

[footnote

9].

If Bob should need to flip more coins to Alice, the two can continue to use the same n, skipping parts I and II of the above protocol.

END OF PROTOCOL THE JUDGE'S PROTOCOL

An iron-clad judge's protocol is one that can be programmed and thereby save needless expense. In what follows, the judge should be viewed as a com- puter.

In case of a dispute, the judge proceeds as follows:

I. Subpoena all signed messages that have been exchanged. Check that the statute of limitations has not been exceeded (5 years past the publication date on the number n). If so, throw the case out of Court.

2. If one of the participants, say Alice, produced a signed-by-Bob message that refers back to a previ- ously signed-by-Alice message (she sent Bob), then Bob must produce the message he received or be found guilty of cheating.

5. Check that n is a 160-digit number that passes the test in II [footnote 10]. If not, Bob is found guilty of cheating.

4. If no messages have provably been exchanged in Ill, i.e., neither party has produced a message of III signed by the ether, then give each of the participants a dated letter asserting that this protocol is declared terminated. (even if Alice sent xl 2 mod n to Bob, who decided not to pursue the matter and threw out her signed message). Otherwise, enforce completion of the protocol (if it has not already been completed) [footnote 11].

5. Check that the xl 2 mod n,... in the signed-by- Alice message received by Bob is the square mod n of the numbers xl,.., in the signed-by-Alice message later received by Bob. If not, Alice is found guilty of cheating.

6. Determine the sequence of random bits that Bob flipped to Alice. Give each of the participants a (dated) paper asserting the court's findings (this is necessary because the case cannot be brought to

[footnote 9]: Alice cannot cheat since, first, (xi/n) = (-xi/n) so Alice cannot change the Jacobi symbol of xi by changing the sign of xi, and second, Alice cannot compute yi such that yi ~ xi mod n and yi 2 = xi 2 mod n (under the assumption that she cannot factor n) since gcd (xi ~ yi) = pl or p2.

[footnote 10]: The judge might, instead of testing n, subpoena the prime factors of n, check there are just two 80-digit primes congruent to 3 mod 4, else find Bob guilty of cheating. This requires, howev- er, that the judge be trusted not to divulge the primes, which Bob might be using in other transactions.

[footnote 11]: This is necessary to guard against the possibility that Alice sent xl 2 mod n,... to Bob, that Bob responded with +I, -I,... and that Alice decided she did not like the result (she might argue that Bob never sent her the required bits). Or perhaps Alice liked the result, responded to Bob by sending him xl,.., and Bob decided he did not like the result (he might argue that Alice never sent him xl,...).

(5)

court again once the statute of limitations is

exceeded not to mention the waste of duplicated

proceedings). END OF PROTOCOL

References

[A'78] D. Angluin, "The Complexity of Some Prob-

lems in N1~ber Theory," Lecture Notes

available from author, Dept. of Comp. Sci- ence, Yale U. (1978).

[~'81]

M. Blum, "Row to Sxohange (Secret) Keys,"

to appear.

[BM'81] M. Blum and S. Mieali, "Coin-Flipping into a Well," to appear.

[BR'81] M. Blum and M.O. Rabin, "Mail Certification by Randomization," to appear.

[DH'79] W. Diffie and M.E. Hellman, "Privacy and Authentication: An Introduction to Cryptog-

raphy," Prec. IEEE, vol. 67 no. 3 (March

1979), 597-427.

[L'77] W.J. LeVeque, "Fundamentals of Number

Theory," Addison-Wesley Pub., 1977.

[M'76] G.L. Miller, "Riemann's Hypothesis and a

Test for Primality," J. Comput. and System Sci. vol. 13 (1976), 300-317.

[MG'81] S. Micali and S. Coldwasser, "Mental Poker

Without Commutative Locks," to appear.

[R'79] M.O. Rabin, "Digital Signatures and Public

Key Systems as Intractable as Faetoriza- tion," MIT LCS TM 1979.

[R'80] M.O. Rabin, "Probabilistic Algorithm for

Testing Primality," J. Number Theory, vel.

12 (1980), 128-138.

[RSA'78] R.L. Rivest, A. Shamir, and L.L. Adleman, "A Method for Obtaining Digital Signatures

and Public-Key Cryptosystems," Commun.

ACM, vol. 21 (1978), 120-126.

[SRA'78] A. Shamir, R.L. Rivest, and L.M. Adle.lian,

"Mental Poker," in The Mathematical

Gardner, ed. D.A. Klarner, pub. by Wads- worth Intrntl (1981), 37-43.

[SS'77] R. So!ovay and V. Strassen, "A Fast Monte-

Carlo Test for Primality," SIAM J. Comput. vol. 6 (1977), 84-85.