Completeness Theorems for Adaptively Secure Broadcast

Martin Hirt, Vassilis Zikas

Ran Cohen, Juan A. Garay, Vassilis Zikas

Duong Hieu Phan, David Pointcheval, Mario Strefler

Juan A. Garay, Jonathan I. Katz, Ranjit Kumaresan +1 more

We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes-simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num-ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine. 1

Joe Kilian

We consider the power of cryptographic primitives, denoted f-cryptogates, defined as follows: Alice and Bob have inputs x and y, respectively.Given a possibly probabilistic function, f(x,y), the f-cryptogate computes z +--f(x,y) and either broadcasts z to both parties (the symmetric case) or sends z exclusively to Bob (the asymmetric case); neither party learns more than what is provided by the fcryptogate.We say that an f-cryptogate is complete if, using information-theoretic notions of reductions, security and privacy, one can use the cryptogate to perform secure two-party computation.We give a number of characterizations of the complete fcryptogates, depending on the adversary model, whether the output of f is probabilistic or deterministic, and whether the cryptogate is symmetric or asymmetric.For active adversaries, who may violate the protocol, we characterize the complete asymmetric f-cryptogates for deterministic f.For passive adversaries, who always follow the protocol, we characterize the complete symmetric and asymmetric f-cryptogates for all deterministic and probabilistic f.Our characterizations for asymmetric cryptogates generalizes a recent theorem of Beimel, Malkin and Micali.abilistic) function f(x, y), the goal of secure function evaluation is to provide Bob with the value of z +--f(x, y) (for

Sanjam Garg, Aarushi Goel, Abhishek Jain