On the Bayes Risk in Information-Hiding Protocols

Abstract : 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 Aposteriori 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.
Type de document :
Article dans une revue
Journal of Computer Security, IOS Press, 2008, 16 (5), pp.531--571. 〈10.3233/JCS-2008-0333〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00349224
Contributeur : Catuscia Palamidessi <>
Soumis le : jeudi 25 décembre 2008 - 02:29:02
Dernière modification le : mercredi 14 novembre 2018 - 16:10:03
Document(s) archivé(s) le : jeudi 11 octobre 2012 - 14:50:36

Fichier

full.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden. On the Bayes Risk in Information-Hiding Protocols. Journal of Computer Security, IOS Press, 2008, 16 (5), pp.531--571. 〈10.3233/JCS-2008-0333〉. 〈inria-00349224〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

194