Information-Theoretic Pseudosignatures and Byzantine Agreement for t ≥ n/3

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