On the structure of the privacy hierarchy |
| |
Authors: | Benny Chor Mihály Geréb-Graus Eyal Kushilevitz |
| |
Affiliation: | (1) Department of Computer Science, Technion, 32000 Haifa, Israel;(2) Department of Computer Science, Tufts University, 02155 Medford, MA, USA;(3) Department of Computer Science, Technion, 32000 Haifa, Israel;(4) Present address: Aiken Computation Laboratory, Harvard University, 02138 Cambridge, MA, USA |
| |
Abstract: | An N argument function f(x
1,...,x
N
) is called t-private if a protocol for computing f exists so that no coalition of at most t parties can infer any additional information from the execution, other than the value of the function. The motivation of this work is to understand what levels of privacy are attainable. So far, only two levels of privacy are known for N argument functions which are defined over finite domains: functions that are N-private and functions that are (N – 1)/2 -private but not N/2 -private.In this work we show that the privacy hierarchy for N-argument functions which are defined over finite domains, has exactly (N + 1)/2 levels. We prove this by constructing, for any N/2 t N – 2, an N-argument function which is t-private but not (t + 1)-private.This research was supported by US-Israel Binational Science Foundation Grant 88-00282. |
| |
Keywords: | Private functions Privacy hierarchy Distributed computing |
本文献已被 SpringerLink 等数据库收录! |
|