Probability of Error in Information-Hiding Protocols

Konstantinos Chatzikokolakis 1 Catuscia Palamidessi 1 Prakash Panangaden 2
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Randomized protocols for hiding private information can fruitfully 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 inference when the MAP (Maximum Aposteriori Probability) decision rule is adopted. 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 substantially 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 breaks anonymity.
Type de document :
Communication dans un congrès
20th IEEE Computer Security Foundations Symposium (CSF20), Jul 2007, Venice, Italy. IEEE Computer Society, pp.341-354, 2007, Proceedings of the 20th IEEE Computer Security Foundations Symposium (CSF20). 〈10.1109/CSF.2007.13〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00200957
Contributeur : Catuscia Palamidessi <>
Soumis le : samedi 22 décembre 2007 - 09:35:31
Dernière modification le : jeudi 10 mai 2018 - 02:06:48
Document(s) archivé(s) le : mardi 13 avril 2010 - 15:14:05

Fichier

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

Identifiants

Collections

Citation

Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden. Probability of Error in Information-Hiding Protocols. 20th IEEE Computer Security Foundations Symposium (CSF20), Jul 2007, Venice, Italy. IEEE Computer Society, pp.341-354, 2007, Proceedings of the 20th IEEE Computer Security Foundations Symposium (CSF20). 〈10.1109/CSF.2007.13〉. 〈inria-00200957〉

Partager

Métriques

Consultations de la notice

265

Téléchargements de fichiers

151