Name
Abstract | ||
|---|---|---|
We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of private protocols is of interest both because random bits are considered a scarce resource and because of the relation between that complexity measure and other complexity measures of boolean functions such as the circuit size or the sensitivity of the function being computed [Kushilevitz, Ostrovsky, and Rosen, J. Comput. Syst. Sci., 58 (1999), pp. 129-136] and [Gal and Rosen, SIAM J. Comput., 31 (2002), pp. 1424-1437]. More concretely, we consider the randomness complexity of the basic Boolean function and, that serves as a building block in the design of many private protocols. We show that and cannot be privately computed using a single random bit, thus giving the first nontrivial lower bound on the 1-private randomness complexity of an explicit Boolean function, f : {0, 1}(n) -> {0, 1}. We further show that and, on any number of inputs n (one input bit per player), can be privately computed using 8 random bits (and 7 random bits in the special case of n = 3 players), improving the upper bound of 73 random bits implicit in [Kushilevitz, Ostrovsky, and Rosen, J. Comput. Syst. Sci., 58 (1999), pp. 129-136]. Together with our lower bound, we thus approach the exact determination of the randomness complexity of and. To the best of our knowledge, the exact randomness complexity of private computation is not known for any explicit function (except for xor, which is 1-random, and for several degenerate functions). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1314197 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
multiparty private computation, randomness, lower bounds | Journal | 35 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyal Kushilevitz | 1 | 5525 | 478.96 |
| Rafail Ostrovsky | 2 | 7 | 4.18 |
| Emmanuel Prouff | 3 | 1485 | 71.27 |
| Adi Rosen | 4 | 13 | 2.08 |
| Adrian Thillard | 5 | 101 | 5.77 |
| Damien Vergnaud | 6 | 7 | 3.55 |