Using Non-interactive Proofs to Achieve Independence Efficiently and Securely
Rosario Gennaro · DSpace@MIT (Massachusetts Institute of Technology) · 1994
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. Previous solutions were all O(log n) rounds. In the process we develop a new and stronger formal definition from 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 Introduction Independence is a fundamental tool to achieve security in fault tolerant distributed protocols. In this paper we present improved results based on a careful exploitation of the properties of non-interactive proofs [2]. In particular we will exhibit the first constant round protocol for the problem of simul...