Name
Abstract | ||
|---|---|---|
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 f n-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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1137/S0097539797321742 | SIAM J. Comput. |
Keywords | Field | DocType |
n-argument boolean function,nonboolean function,function g,boolean function g,black box,nonprivate boolean function,n-argument function,complete boolean function,private computations,complete function,private computation,oblivious transfer,completeness | Boolean function,Black box (phreaking),Discrete mathematics,Combinatorics,Parity function,If and only if,Game theory,Completeness (statistics),Mathematics,Oblivious transfer,Computation | Journal |
Volume | Issue | ISSN |
29 | 4 | 0097-5397 |
Citations | PageRank | References |
37 | 2.92 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Kilian | 1 | 37 | 2.92 |
| Eyal Kushilevitz | 2 | 5525 | 478.96 |
| Silvio Micali | 3 | 11434 | 2581.31 |
| Rafail Ostrovsky | 4 | 8743 | 588.15 |