Pham, Dang Vinh
(2013)
Towards practical and fundamental limits of anonymity protection.
PhD, Universität Regensburg.
Date of publication of this fulltext: 21 Nov 2013 11:09
Abstract (English)
A common function of anonymity systems is the embedding of subjects that are associated to some attributes in a set of subjects, the anonymity set. Every subject within the anonymity set appears to be possibly associated to attributes of every other subject within it. The anonymity set covers the associations between the subjects and their attributes. The limit of anonymity protection basically ...
Abstract (English)
A common function of anonymity systems is the embedding of subjects that are associated to some attributes in a set of subjects, the anonymity set. Every subject within the anonymity set appears to be possibly associated to attributes of every other subject within it. The anonymity set covers the associations between the subjects and their attributes. The limit of anonymity protection basically depends on the hardness of disclosing those hidden associations from the anonymity sets. This thesis analyses the protection limit provided by anonymity sets by studying a practical and widely deployed anonymity system, the Chaum Mix. A Mix is an anonymous communication system that embeds senders of messages in an anonymity set to hide the association to their recipients (i.e., attributes), in each communication round. It is well known that traffic analyses can uniquely identify a user’s recipients by evaluating the sets of senders (i.e., the sender anonymity set) and recipients using the Mix in several rounds. The least number of rounds for that identification represents a fundamental limit of anonymity protection provided by the anonymity sets, similar to Shannon’s unicity-distance. That identification requires solving NP-complete problems and was believed to be computationally infeasible.
This thesis shows by a new and optimised algorithm that the unique identification of a user’s recipients is for many realistic Mix configurations computational feasible, in the average case. It contributes mathematical estimates of the mean least number of rounds and the mean time-complexity for that unique identification. These measure the fundamental, as well as the practical protection limit provided by the anonymity sets of a Mix. They can be applied to systematically identify Mix configurations that lead to a weak anonymity of a user’s recipients. To the best of our knowledge, this has not been addressed yet, due to the computational infeasibility of past algorithms. All before-mentioned algorithms and analyses can be adapted to deduce information about a user’s recipients, even in cases of incomplete knowledge about the anonymity sets, or a low number of observed anonymity sets.
Translation of the abstract (German)
Eine grundlegende Funktion von Anonymitätssystemen ist die Einbettung von Subjekten, denen sensible Attribute zugeordnet sind, in eine Anonymitätsmenge. Die Einbettung bewirkt eine Verdeckung der Zuordnung zwischen Subjekten innerhalb der Anonymitätsmenge und deren Attribute. Jede Kombination zwischen den Subjekten der Anonymitätsmenge und den Attributen wird dadurch scheinbar möglich. Die ...
Translation of the abstract (German)
Eine grundlegende Funktion von Anonymitätssystemen ist die Einbettung von Subjekten, denen sensible Attribute zugeordnet sind, in eine Anonymitätsmenge. Die Einbettung bewirkt eine Verdeckung der Zuordnung zwischen Subjekten innerhalb der Anonymitätsmenge und deren Attribute. Jede Kombination zwischen den Subjekten der Anonymitätsmenge und den Attributen wird dadurch scheinbar möglich. Die Schranke des Anonymitätsschutzes wird grundlegend durch die Schwierigkeit bestimmt, aus den beobachtbaren Anonymitätsmengen und Attributen die verdeckte Zuordnung zu rekonstruieren. Diese Arbeit analysiert die Schranke des Anonymitätsschutzes durch Anonymitätsmengen anhand eines weit verbreiteten Anonymitätssystems, welches Chaum Mix genannt wird. Ein Mix ist ein System zur anonymen Netzwerkkommunikation welches die Sender von Nachrichten in eine Anonymitätsmenge einbettet um die Zuordnung zu ihren Empfängern zu verdecken. Es ist bekannt, dass die Empfänger eines Senders eindeutig identifiziert werden können wenn eine Verkehrsanalyse auf die Anonymitätsmenge und Empfängermenge über genügend viele Kommunikationsrunden durchgeführt wird. Die minimale Anzahl an Runden, um die Identifizierung zu ermöglichen, stellt eine fundamentale Schranke für den Anonymitätsschutz dar. Dieser hat eine ähnliche Bedeutung wie die Shannon Unicity-Distance. Die Identifizierung erfordert dabei das Lösen von NP-vollständigen Problemen.
Diese Arbeit beweist durch einen verbesserten neuen Algorithmus, dass die eindeutige Identifizierung der Empfänger eines Nutzers für viele realistische Mix-Konfigurationen im Mittel effizient berechenbar ist. Es bietet eine mathematische Abschätzung der mittleren, minimalen Anzahl an Runden, sowie der mittleren Laufzeitkomplexität für die Identifizierung. Diese Abschätzungen messen sowohl den theoretischen, als auch den praktischen Schutz, der durch die Anonymitätsmengen des Mixes erzeugt wird. Dadurch werden Mix-Konfigurationen, die zu einem schwachen Schutz führen, analytisch erkennbar. Eine derartige Analyse wurde nach unserem Wissen wegen der exponentiellen Komplexität bestehender Algorithmen und der damit verbundenen Unzugänglichkeit des Problems noch nicht durchgeführt. Die hier erarbeiteten Algorithmen lassen sich erweitern um dann auch bei unvollständig beobachteten Anonymitätsmengen, Informationen über die Empfänger eines Nutzers zu gewinnen.
Export bibliographical data
Download Statistics