Lehrstuhl Mathematik & InformatikRandomized Response Schemes, Privacy and Usefulness
Abstract. We define the notions of weak and strong usefulness and investigate the question whether a randomized response scheme can combine two conflicting goals, namely being weakly (or even strongly) useful and, at the same time, providing epsilon-differential privacy. We prove the following results. First, if F cannot be weakly SQ-learned under the uniform distribution, then epsilon-differential privacy rules out weak usefulness. This extends a result from Dwork et al. (2006) that was concerned with the class of parities. Second, for a broad variety of classes F that actually can be weakly SQ-learned under the uniform distribution, we design a randomized response scheme that provides epsilon-differential privacy and strong usefulness.