Evaluating Multiple Guesses by an Adversary via a Tunable Loss Function
share
We consider a problem of guessing, wherein an adversary is interested in knowing the value of the realization of a discrete random variable X on observing another correlated random variable Y. The adversary can make multiple (say, k) guesses. The adversary's guessing strategy is assumed to minimize α-loss, a class of tunable loss functions parameterized by α. It has been shown before that this loss function captures well known loss functions including the exponential loss (α=1/2), the log-loss (α=1) and the 0-1 loss (α=∞). We completely characterize the optimal adversarial strategy and the resulting expected α-loss, thereby recovering known results for α=∞. We define an information leakage measure from the k-guesses setup and derive a condition under which the leakage is unchanged from a single guess.
READ FULL TEXT