More general completeness theorems for secure two-party computation
Joe Kilian · 2000
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