A zero-one law for Boolean privacy

ABSTRACT

A Boolean function ƒ: A1 X A2 X … X An → {0,1} is t - private if there exists a protocol for computing ƒ so that no coalition of size ≤ t can infer any additional information from the execution, other than the value of the function. We show that ƒ is ⌈n/2⌉ - private if and only if it can be represented as ƒ (x1, x2, …, xn) = ƒ (x1) ⊕ ƒ2(x2) ⊕ … ⊕ ƒn (xn, where the ƒi are arbitrary Boolean functions. It follows that if ƒ is ⌈n/2⌉ - private, then it is also n - private. Combining this with a result of Ben-Or, Goldwasser, and Wigderson, we derive an interesting “zero-one” law for private distributed computation of Boolean functions: Every Boolean function defined over a finite domain is either n - private, or it is ⌈n-1/2⌉ - private but not ⌈n/2⌉ - private. We also investigate a weaker notion of privacy, where (a) coalitions are allowed to infer a limited amount of additional information, and (b) there is a probability of error in the final output of the protocol. We show that the same characterization of ⌈n/2⌉ - private Boolean functions holds, even under these weaker requirements. In particular, this implies that for Boolean functions, the strong and the weak notions of privacy are equivalent.

REFERENCES

• Bh: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• BGW: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• CCD: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• GMW: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• PS: Paturi, R., and J. Simon, "Probabilistic communication complexity", Proc. of ~5th FOC$, 1984, pp. 118-126.
• Ya: Yao, A. C., "How to Generate and Exchange Secrets", Proc. of 27th FO CS, 1986, pp. 162-167.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Design, Security, Theory