Fast and Unconditionally Secure Anonymous Channel
Juan Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov
Abstract:
In this paper we focus on sender−anonymous channels(a.k.a dining Cryptographers networks) and present a construction requiring a very low (constant) number of rounds of interaction while tolerating actively malicious behavior by some of the participants ( up to less than half of them). Our construction is unconditionally secure (meaning that no bounds are placed on the computational power of the adversary), makes black box use of a verifiable secret sharing(VSS) protocol, and is based on special−purpose secure multiparty computation protocol implementing the method of “throwing darts;” its round complexity equal to that of the VSS protocol .
In addition, since broadcast cannot be simulated in a point−to−point network when a third or more of the participants are corrupt, it is impossible to construct VSS ƚand , more generally, any other basic multiparty protocol) in this setting without using a “physical broadcast channel,”, and a recent line of reaserach has sought to minimize the use of this expensive resource. Our anonymous channel protocol‚s reduction to VSS is broadcast−round−preserving, thus making the fewest (known to date) calls to the broadcast channel while running in an overall constant number of rounds.
Finally, anonymous channels play an important role in the setup phase of an authentication technique known as pseudosignatures, which then may be used to simulate authenticated Byzantine agreement protocols in the information theoretic setting. Plugging in our anonymous channel translates into a fast ( and broadcast−efficient) pseudosignature construction.
comment: PODC 2014 PP: 313−321
Fetch PDF file of the paper
| Back to Publications List |