Worst- and average-case privacy breaches in randomization mechanisms

In a variety of contexts, randomization is regarded as an effective technique to conceal sensitive information. Viewing randomization mechanisms as information-theoretic channels, we start from a semantic notion of security, which expresses absence of any privacy breach above a given level of seriou...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2015-09, Vol.597, p.40-61
Main Authors: Boreale, Michele, Paolini, Michela
Format: Article
Language:English
Subjects:
Channels
Computer information security
Differential privacy
Foundations of security
Information theory
Mathematical analysis
Privacy
Quantitative information flow
Randomization
Semantics
Two dimensional
Utilities
Utility
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a variety of contexts, randomization is regarded as an effective technique to conceal sensitive information. Viewing randomization mechanisms as information-theoretic channels, we start from a semantic notion of security, which expresses absence of any privacy breach above a given level of seriousness ϵ, irrespective of any background information, represented as a prior probability on the secret inputs. We first examine this notion according to two dimensions: worst vs. average case, single vs. repeated observations. In each case, we characterize the security level achievable by a mechanism in a simple fashion that only depends on the channel matrix, and specifically on certain measures of “distance” between its rows, like norm-1 distance and Chernoff Information. We next clarify the relation between our worst-case security notion and differential privacy (dp): we show that, while the former is in general stronger, the two coincide if one confines to background information that can be factorized into the product of independent priors over individuals. We finally turn our attention to expected utility, in the sense of Ghosh et al., in the case of repeated independent observations. We characterize the exponential growth rate of any reasonable utility function. In the particular case the mechanism provides ϵ-dp, we study the relation of the utility rate with ϵ: we offer either exact expressions or upper-bounds for utility rate that apply to practically interesting cases, such as the (truncated) geometric mechanism.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.07.010