Portal de Periódicos da CAPES

Reducibility and Completeness in Private Computations

2000; Society for Industrial and Applied Mathematics; Volume: 29; Issue: 4 Linguagem: Inglês

10.1137/s0097539797321742

1095-7111

Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky,

Internet Traffic Analysis and Secure E-voting

We define the notions of reducibility and completeness in (two-party and multiparty) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n honest-but-curious players can compute the function fn -privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for private computations) if every function f is reducible to g. In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black box available). Namely, for n-argument boolean functions, the notions of completeness and n-privacy are complementary. This characterization provides a huge collection of complete functions any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary.