×

Breaking anonymity by learning a unique minimum hitting set. (English) Zbl 1248.94076

Frid, Anna (ed.) et al., Computer science – theory and applications. Fourth international computer science symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03350-6/pbk). Lecture Notes in Computer Science 5675, 299-309 (2009).
Summary: Anonymity protocols are not secure unless the communication structure is not learnable even in the case that the entire network traffic can be monitored by an adversary. When the true communication structure is cloaked under anonymity sets, the adversary may disclose the peers of a certain user by waiting for the observations to contain a unique minimum hitting set. This approach has been called the hitting set attack in the literature. We give the first mathematical analysis on the number of observations required to learn a unique minimum hitting set. Because this attack involves solving an NP-hard problem in each round, we propose two new learning algorithms, both of which are very efficient computationally. The first one breaks anonymity by combining the most suspicious elements into a hitting set. Because this algorithm is not capable of verifying its hypothesis, it is imperative to estimate the required number of observations. On the other hand, the second one is able to prove its hypothesis correct, but needs more observations.
For the entire collection see [Zbl 1169.68003].

MSC:

94A60 Cryptography
68Q32 Computational learning theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM 24(2), 84–88 (1981) · doi:10.1145/358549.358563
[2] Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology 1(1), 65–75 (1988) · Zbl 0654.94012 · doi:10.1007/BF00206326
[3] Danezis, G., Diaz, C.: A survey of anonymous communication channels. Technical Report MSR-TR-2008-35, Microsoft Research (January 2008)
[4] Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. EATCS Bulletin 87, 47–77 (2005) · Zbl 1169.68669
[5] Hansen, M., Pfitzmann, A.: Anonymity, unobservability, and pseudonymity: A consolidated proposal for terminology. Draft (July 2000)
[6] Kesdogan, D., Pimenidis, L.: The hitting set attack on anonymity protocols. In: Fridrich, J. (ed.) IH 2004. LNCS, vol. 3200, pp. 326–339. Springer, Heidelberg (2004) · doi:10.1007/978-3-540-30114-1_23
[7] Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995) · Zbl 0849.68039 · doi:10.1017/CBO9780511814075
[8] Pfitzmann, A., Köhntopp, M.: Anonymity, unobservability, and pseudonymity: A consolidated proposal for terminology. Draft, version 0.23 (July 2000); For date of the latest version, see the document itself
[9] Rossmanith, P., Zeugmann, T.: Stochastic finite learning of the pattern languages. Machine Learning 44(1/2), 67–91 (2001) · Zbl 0992.68117 · doi:10.1023/A:1010875913047
[10] Zeugmann, T.: Stochastic finite learning. In: Steinhöfel, K. (ed.) SAGA 2001. LNCS, vol. 2264, pp. 155–171. Springer, Heidelberg (2001) · Zbl 1054.68118 · doi:10.1007/3-540-45322-9_11
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.