Measuring Information Leakage in Non-stochastic Brute-Force Guessing
This work addresses privacy formalization for scenarios with non-probabilistic uncertainty, which is incremental as it builds on existing guessing frameworks.
The paper tackles the problem of formalizing privacy against brute-force guessing adversaries in non-stochastic settings by proposing an operational measure of information leakage based on the ratio of worst-case guesses with and without outputs, showing relationships with existing measures like non-stochastic maximin information and stochastic maximal leakage.
We propose an operational measure of information leakage in a non-stochastic setting to formalize privacy against a brute-force guessing adversary. We use uncertain variables, non-probabilistic counterparts of random variables, to construct a guessing framework in which an adversary is interested in determining private information based on uncertain reports. We consider brute-force trial-and-error guessing in which an adversary can potentially check all the possibilities of the private information that are compatible with the available outputs to find the actual private realization. The ratio of the worst-case number of guesses for the adversary in the presence of the output and in the absence of it captures the reduction in the adversary's guessing complexity and is thus used as a measure of private information leakage. We investigate the relationship between the newly-developed measure of information leakage with the existing non-stochastic maximin information and stochastic maximal leakage that are shown arise in one-shot guessing.