A zero-one law for Boolean privacy
A zero-one law for Boolean privacy
复制标题
布尔隐私的零一法则
DOI：
10.1145/73007.73013
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
E. Kushilevitz
中科院分区：
文献类型：
--
作者：
B. Chor;E. Kushilevitz
一个布尔函数<$：A<subscrpt>1</subscrpt> X A<subscrpt>2</subscrpt> X... X<subscrpt><italic>An</italic></subscrpt> → {0，1}是<italic>t</italic>-私有的，如果存在一个计算<$的协议，使得没有大小≤<italic>t的</italic>联盟可以从执行中推断出任何额外的信息，除了函数的值。我们证明了它是<$<italic>n</italic>/2 <$-私有的当且仅当它可以表示为<$i（<italic>x</italic><subscrpt>1</subscrpt>，<italic>x</italic><subscrpt>2</subscrpt>，.，<italic>xn</italic>）=<$i（<italic>x</italic><subscrpt>1</subscrpt>）<$i <$2（<italic>x</italic><subscrpt>2</subscrpt>）<$..<<italic>$i <$</italic><subscrpt><italic>n</italic></subscrpt>（xn<subscrpt><italic>）</italic></subscrpt>，其中<$<subscrpt><italic>i</italic></subscrpt>是任意布尔函数。<subscrpt></subscrpt><subscrpt><italic></italic></subscrpt>因此，如果它是<italic>n</italic>/2 n- private，那么它也是<italic>n</italic>- private。结合Ben-Or、Goldwasser和Wigderson的结果，我们得到了布尔函数私有分布计算的一个有趣的“0 - 1”定律：定义在有限域上的每个布尔函数要么是<italic>n</italic>-私有的，要么是<italic>n</italic>-1/2 n-私有的，但不是<italic>n</italic>-2 n-私有的。
我们还研究了一个较弱的隐私概念，其中（a）联盟被允许推断出有限数量的额外信息，（B）在协议的最终输出中存在错误的概率。我们表明，相同的表征的<italic>n</italic>/2的n-私人布尔函数持有，即使在这些较弱的要求。特别是，这意味着对于布尔函数，强隐私和弱隐私的概念是等价的。
A Boolean function ƒ: A<subscrpt>1</subscrpt> X A<subscrpt>2</subscrpt> X … X A<subscrpt><italic>n</italic></subscrpt> → {0,1} is <italic>t</italic> - private if there exists a protocol for computing ƒ so that no coalition of size ≤ <italic>t</italic> can infer any additional information from the execution, other than the value of the function. We show that ƒ is ⌈<italic>n</italic>/2⌉ - private if and only if it can be represented as ƒ (<italic>x</italic><subscrpt>1</subscrpt>, <italic>x</italic><subscrpt>2</subscrpt>, …, <italic>x</italic><subscrpt><italic>n</italic></subscrpt>) = ƒ (<italic>x</italic><subscrpt>1</subscrpt>) ⊕ ƒ<subscrpt>2</subscrpt>(<italic>x</italic><subscrpt>2</subscrpt>) ⊕ … ⊕ ƒ<subscrpt><italic>n</italic></subscrpt> (<italic>x</italic><subscrpt><italic>n</italic></subscrpt>, where the ƒ<subscrpt><italic>i</italic></subscrpt> are arbitrary Boolean functions. It follows that if ƒ is ⌈<italic>n</italic>/2⌉ - private, then it is also <italic>n</italic> - 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 <italic>n</italic> - private, or it is ⌈<italic>n</italic>-1/2⌉ - private but not ⌈<italic>n</italic>/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 ⌈<italic>n</italic>/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.