RISC Seminars (Research on Information Security and Cryptology)
Archives: [2024] [2023] [2022] [2021] [2020] [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers](To receive information about upcoming seminars, register for the RISC mailing list.)
[print]
RISC Seminar
| Date: | March 1 |
| Location: | CWI, Room M280 |
| Schedule: | |
| 16:00-17:00 | Vinod Vaikuntanathan (MIT): Random Selection and Byzantine Agreement in the Full-Information Model Abstract: Random Selection -- one of the most basic protocol problems in
cryptography and distributed computing -- asks for mutually distrusting
parties to jointly generate a random string. Feige (FOCS 99) and Russell
and Zuckerman (FOCS 98) construct elegant random selection protocols
that run in log* n rounds, in the full-information model. These
protocols, however, assume a *built-in reliable broadcast channel*. We
construct random selection protocols that run in O(log n) rounds in the
plain model, namely, *without* reliable broadcast channels. One of the
consequences of this result is an O(log n)-round randomized Byzantine
Agreement protocol, improving on the previous best result of (n/log n)
rounds (Chor-Coan '85).
Based on joint work with Shafi Goldwasser and Elan Pavlov (FOCS 06). |
0.05083s