We put forward a zero-knowledge based definition of privacy. Our notion is strictly stronger than the notion of differential privacy and is particularly attractive when modeling privacy in social networks. We furthermore demonstrate that it can be meaningfully achieved for tasks such as computing averages, fractions, histograms, and a variety of graph parameters and properties, such as average degree and distance to connectivity. Our results are obtained by establishing a connection between zero-knowledge privacy and sample complexity, and by leveraging recent sublinear time algorithms.
Gehrke, Lui, and Pass in REF present the notion of zero-knowledge privacy that is appealing for achieving privacy in social networks.
Towards Privacy for Social Networks: A Zero-Knowledge Based Definition of Privacy ∗
TCC
Computer Science