Non-stochastic hypothesis testing for privacy

Abstract

In this paper, we consider privacy against hypothesis testing adversaries within a non-stochastic framework. We develop a theory of non-stochastic hypothesis testing by borrowing the notion of uncertain variables from non-stochastic information theory. We define tests as binary-valued mappings on uncertain variables and prove a fundamental bound on the best performance of tests in non-stochastic hypothesis testing. We provide parallels between stochastic and non-stochastic hypothesis-testing frameworks. We use the performance bound in non-stochastic hypothesis testing to develop a measure of privacy. We then construct reporting policies with prescribed privacy and utility guarantees. The utility of a reporting policy is measured by the distance between the reported and original values. Finally, we present the notion of indistinguishability as a measure of privacy by extending identifiability from the privacy literature to the non-stochastic framework. We prove that linear quantizers can indeed achieve identifiability for responding to linear queries on private datasets.