TY - JOUR

T1 - On the Bayes risk in information-hiding protocols

AU - Chatzikokolakis, K.

AU - Palamidessi, C.

AU - Panangaden, P.

PY - 2008

Y1 - 2008

N2 - Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a hypothesis-testing problem. We consider the Bayesian approach to the problem, and investigate the probability of error associated to the MAP (maximum a posteriori probability) inference rule. Our main result is a constructive characterization of a convex base of the probability of error, which allows us to compute its maximum value (over all possible input distributions), and to identify upper bounds for it in terms of simple functions. As a side result, we are able to improve the Hellman–Raviv and the Santhi–Vardy bounds expressed in terms of conditional entropy. We then discuss an application of our methodology to the Crowds protocol, and in particular we show how to compute the bounds on the probability that an adversary break anonymity.

AB - Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a hypothesis-testing problem. We consider the Bayesian approach to the problem, and investigate the probability of error associated to the MAP (maximum a posteriori probability) inference rule. Our main result is a constructive characterization of a convex base of the probability of error, which allows us to compute its maximum value (over all possible input distributions), and to identify upper bounds for it in terms of simple functions. As a side result, we are able to improve the Hellman–Raviv and the Santhi–Vardy bounds expressed in terms of conditional entropy. We then discuss an application of our methodology to the Crowds protocol, and in particular we show how to compute the bounds on the probability that an adversary break anonymity.

U2 - 10.3233/JCS-2008-0333

DO - 10.3233/JCS-2008-0333

M3 - Article

SN - 0926-227X

VL - 16

SP - 531

EP - 571

JO - Journal of Computer Security

JF - Journal of Computer Security

IS - 5

ER -