For a given function of user data, a querier must recover with at least a prescribed probability, the value of the function based on a user-provided query response. Subject to this requirement, the user forms the query response so as to minimize the likelihood of the querier guessing a list of prescribed size to which the data value belongs based on the query response. We obtain a general converse upper bound for maximum list privacy. This bound is shown to be tight for the case of a binary-valued function through an explicit achievability scheme that involves an add-noise query response.

In the article[1], in the proof of Lemma 2, the sentence after (10) “For a fixed$Q^{(n)}$, since$(P_{X}W)^{n}(z^{n})$is the same for all$z^{n}\in \mathcal {T}_{Q^{(n)}}$, if$\widehat {P}_{n}(z^{n})$were to vary across$z^{n}\in \mathcal {T}_{Q^{(n)}}$, the querier can pick that$\tilde {z^{n}}$, say, in$\mathcal {T}_{Q^{(n)}}$for which$D\left ({P_{X}\big |\big |\widehat {P}_{n}\left ({\tilde {z^{n}}}\right)}\right)$is smallest over$\mathcal {T}_{Q^{(n)}}$and use$\widehat {P}_{n}\left ({\tilde {z^{n}}}\right)$as the estimate of$P_{X}$for all$z^{n}\in \mathcal {T}_{Q^{(n)}}$, denoting it by$\widehat {P}_{n}\left ({Q^{(n)}}\right)$; this will only serve to decrease the right-side of (10), bearing in mind the$\inf $with respect to$\widehat {P}_{n}$in the left-side of (5)” is incorrect.

A user’s data is represented by a Gaussian random variable. Given a linear function of the data, a querier is required to recover, with at least a prescribed accuracy level, the function value based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Recoverability and privacy are both measured by ℓ2-distance criteria. An exact characterization is provided of maximum user data privacy under the recoverability condition. An explicit achievability scheme for the user is given and its privacy compared with a converse upper bound.

A user generates$n$independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of$n$independent and identically distributed query responses upon eliciting them from the user. The user chooses the data probability mass function and devises the random query responses to maximize distribution privacy as gauged by the (Kullback-Leibler) divergence between the former and the querier’s best estimate of it based on the$n$query responses. Considering an arbitrary function, a basic achievable lower bound for distribution privacy is provided that does not depend on$n$and corresponds to worst-case privacy. Worst-case privacy equals the logsum cardinalities of inverse atoms under the given function, with the number of summands decreasing as the querier recovers the function with improving accuracy. Next, upper (converse) and lower (achievability) bounds for distribution privacy, dependent on$n$, are developed. The former improves upon worst-case privacy and the latter does so under suitable assumptions; both converge to it as$n$grows. The converse and achievability proofs identify explicit strategies for the user and the querier.

A user generates$n$independent and identically distributed data rvs with a pmf that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of$n$independent and identically distributed user-devised query responses. The user chooses the data pmf and the random query responses to maximize distribution privacy as gauged by the divergence between the pmf and the querier's best estimate of it based on the$n$query responses. Considering an arbitrary function, a basic achievable lower bound, that does not depend on n, is provided for distribution privacy. Next, upper (converse) and lower (achievable) bounds, dependent on n, are developed that converge to said basic bound as$n$grows. Explicit strategies for the user and the querier are identified.

A user generates n independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of n independent and identically distributed user-devised query responses. The user chooses the data pmf and the random query responses to maximize distribution privacy as gauged by the divergence between the pmf and the querier's best estimate of it based on the n query responses. A general lower bound is provided for distribution privacy; and, for the case of binaryvalued functions, upper and lower bounds that converge to said bound as n grows. Explicit strategies for the user and querier are identified.

For a given function of user data, a querier must recover with at least a prescribed probability, the value of the function based on a user-provided query response. Subject to this requirement, the user forms its query response so as to maximize probability of error-based predicate privacy or list privacy of the data from the querier. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacies compared with converse upper bounds.

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, which provide maximum privacy to the user. In the former setting, we also consider privacy for a predicate of the user's data. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.

A user's data is represented by a finite-valued random variable. Given a function of the data, a querier is required to recover, with at least a prescribed probability, the value of the function based on a query response provided by the user. The user devises the query response, subject to the recoverability requirement, so as to maximize privacy of the data from the querier. Privacy is measured by the probability of error incurred by the querier in estimating the data from the query response. We analyze single and multiple independent query responses, with each response satisfying the recoverability requirement, that provide maximum privacy to the user. Achievability schemes with explicit randomization mechanisms for query responses are given and their privacy compared with converse upper bounds.