[freehaven-dev] Micali's Exchange protocol

[Ron Rivest <rivest@theory.lcs.mit.edu>]

I think Silvio Micali's exchange protocol is something like this:

A wants to send B a message M and get a receipt for the message.
(So here we are exchanging M for the receipt.)

We assume a trusted third party T .  T is not active unless there
is a dispute.

All parties have known public keys PK_A, PK_B, PK_T etc...

Step 1:

	A sends B:  E(PK_T,(A,B,M))
		    the value of the triple (A,B,M) encrypted with T's PK
		    (Let's call X this value E(PK_T,(A,B,M)))
Step 2:

	B sends A:
		    a receipt for the value X he received in step 1.
		    (E.g. a signed message saying "I acknowledge receipt of X".)

Step 3:

	A sends B:	
		    M
		    Then B checks that E(PK_T,(A,B,M)) = X 
		

If B refuses to execute step 2, then he doesn't have M and A doesn't
have a receipt.

If B executes step 2, but A doesn't execute step 3, then B can appeal
to T, and send to T the value X and also a copy of the receipt for X
that he (allegedly) sent in step 2. Then T checks that X is
well-formed, and that B's receipt is OK.  If so, then T sends M to B
and the receipt to A.

(Note that it is important that T send the receipt to A as well, otherwise B could
appeal to T without ever having sent A a receipt in step 2.)

If B finds in step 3 that the message M is not the one A encrypted in
step 1, then he can also appeal to T to get M.  (Otherwise A has a
receipt for a value that B never saw.)

Note that checking E(PK_T,(A,B,M)) = X requires that E be a
deterministic public-key encryption scheme, or that A must reveal the
randomness used in the encryption in step 3 as well as the message M.

A hybrid scheme where M is the key for an encrypted document isn't
quite enough, as both X and the receipt need to be commitments to the
document.

For the current application (freehaven), the protocol needs to be
extended to handle an exchange of message M1 for M2, and also needs to
identify suitable third parties.

It is easy to imagine one server acting as a TTP for the benefit of
two other servers who want to do an exchange.  Moreover, since the TTP
is not active except in the case of dispute, A and B can use *many*
other servers as a TTP for the exchange simultaneously.  (That is,
step 1 has as many X values as TTP's being used.  If a dispute arises,
any one of them can resolve it.)

I think that the above protocol, repeated once each way, is sufficient
for your application to exchange M1 for M2.  If someone who gives you
M1 fails to accept M2, then you can just refuse to deal with him
again.

Perhaps Silvio can correct any mistakes I have in the above, and/or
give you a citation or pointer to his paper...

	Cheers,
	Ron