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.