Information-Theoretic Pseudosignatures and Byzantine Agreement

        Byzantine agreement means achieving reliable broadcast on a point-to-point network of n processors, of which up to t may be maliciously faulty. A well-known result by Pease, Shostak, and Lamport says that perfect Byzantine agreement is only possible if t < n/3. In contrast, so-called authenticated protocols achieve Byzantine agreement for any t based on computational assumptions, typically the existence of a digital signature scheme, an assumption equivalent to the existence of one-way functions. The folklore belief based on these two results is that computational assumptions are necessary to achieve Byzantine agreement of t > n/3. We present a protocl that refutes this folklore belief, i.e., it achieves Byzantine agreement for any t in an information-theoretic setting. It does not, however, contradict the precise impossibility result: More that one difference exists between the model in that proof and the model of the existing authenticated protocols, and we only remove the computational assumption. Our protocol is based on a new information-theoretically secure authentication scheme with many of the properties of digital signatures; we call it pseudosignatures. Our construction of pseudosignatures generalizes a scheme by Chaum and Roijakkers.

By: B. Pfitzmann (Univ. Hildesheim, Germany) and M. Waidner

Published in: RZ2882 in 1996


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Questions about this service can be mailed to .