Paul Feldman

STOC Conference 1988 Conference Paper

Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract)

• Manuel Blum 0001
• Paul Feldman
• Silvio Micali

STOC Conference 1988 Conference Paper

Optimal Algorithms for Byzantine Agreement

• Paul Feldman
• Silvio Micali

We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments.

FOCS Conference 1987 Conference Paper

A Practical Scheme for Non-interactive Verifiable Secret Sharing

• Paul Feldman

This paper presents an extremely efficient, non-interactive protocol for verifiable secret sharing. Verifiable secret sharing (VSS) is a way of bequeathing information to a set of processors such that a quorum of processors is needed to access the information. VSS is a fundamental tool of cryptography and distributed computing. Seemingly difficult problems such as secret bidding, fair voting, leader election, and flipping a fair coin have simple one-round reductions to VSS. There is a constant-round reduction from Byzantine Agreement to non-interactive VSS. Non-interactive VSS provides asynchronous networks with a constant-round simulation of simultaneous broadcast networks whenever even a bare majority of processors are good. VSS is constantly repeated in the simulation of fault-free protocols by faulty systems. As verifiable secret sharing is a bottleneck for so many results, it is essential to find efficient solutions.

STOC Conference 1986 Conference Paper

Non-Blocking Networks (Preliminary Version)

• Paul Feldman
• Joel Friedman
• Nicholas Pippenger

FOCS Conference 1985 Conference Paper

Byzantine Agreement in Constant Expected Time (and Trusting No One)

• Paul Feldman
• Silvio Micali

We present a novel cryptographic algorithm for Byzantine agreement in a network with l=O(n) faulty processors and in the most adversarial setting. Our algorithm requires, once and for all, O(t) rounds of preprocessing. Afterwards it allows us to reach each individual Byzantine agreement in constant expected time. Our solution does not make use of any trusted party.

STOC Conference 1985 Conference Paper

Fault Tolerance of Minimal Path Routings in a Network

• Paul Feldman