[ont.events] Theoretical Aspects Sem./"Constructive & Provably Fair Coin Flips..."

eas@utcsrgv.UUCP (Ann Struthers) (01/21/85)

		      THEORETICAL ASPECTS SEMINAR

		      Thursday, Janurary 31, 1985

		          4:00 P.M. SF 1105


		      Professor Shafi Goldwasser
		                M.I.T.
		      Lab. For Computer Science

     "Constructive and Provably Fair Coin Flips in Byzantine Networks"


Abstract:

We present a constructive cryptographic protocol for flippling a fair coin
in unreliable distributed environment under the assumption that a trapdoor
function exists. Our solution is the first one to exhibit a rigorours proof
of correctness.

Randomization is both a powerful tool for efficient computation, and the
best weapon against adversaries. Thus, coin flipping is a fundamental 
primitive for designing protocols in an unreliable network. Our solution
has been used by Bracha to achieve Byzantine agreement in a synchronous
of size n in expected logn time, and in an asynchronous network in polylogn
time.

This is joint with Baruch Awerbuch, Benny Chor and Silvio Micali.