2021/07/02 by Ni Ding, Farhad Farokhi, Ding, Ni +1
Computer Science · Mathematics · #Adversarial Robustness in Machine Learning #Adversary #Brute force #Computer science #Computer security #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #Information leakage #Leakage (economics) #Mathematical optimization #Mathematics #Minimax #Privacy-Preserving Technologies in Data #Statistics #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2107.01113
published in arXiv (Cornell University) (Cornell University) · 11 pages, 4 figures
arxiv created 2021/07/02 · openalex publication_date 2021/07/02 · arxiv updated 2021/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper proposes an operational measure of non-stochastic information leakage to formalize privacy against a brute-force guessing adversary. The information is measured by non-probabilistic uncertainty of uncertain variables, the non-stochastic counterparts of random variables. For X that is related to released data Y, the non-stochastic brute-force leakage is measured by the complexity of exhaustively checking all the possibilities of the private attribute U of X by an adversary. The complexity refers to the number of trials to successfully guess U. Maximizing this leakage over all possible private attributes U gives rise to the maximal (i.e., worst-case) non-stochastic brute-force guessing leakage. This is proved to be fully determined by the minimal non-stochastic uncertainty of X given Y, which also determines the worst-case attribute U indicating the highest privacy risk if Y is disclosed. The maximal non-stochastic brute-force guessing leakage is shown to be proportional to the non-stochastic identifiability of X given Y and upper bounds the existing maximin information. The latter quantifies the information leakage when an adversary must perfectly guess U in one-shot via Y. Experiments are used to demonstrate the tradeoff between the maximal non-stochastic brute-force guessing leakage and the data utility (measured by the maximum quantization error) and to illustrate the relationship between maximin information and stochastic one-shot maximal leakage.