Achieving independence efficiently and securely
Rosario Gennaro · 1995
Independence or simultaneous broadcast is a fundamental tool to achieve security in fault tolerant distributed computing.It allows n players to commit to independently chosen values.In this paper we present a constant round protocol to perform this task under general complexity assumptions.Previous solutions were all O(log, n) rounds.In the process we develop a new and stronger formal definition for this problem.As an example of the importance of independence in distributed protocols, we show an attack on the Sako-Kilian election scheme presented at CRYPTO 94 made possible by the protocol failure on achieving independence.Using our techniques we will show how to modify the scheme to make it secure.1