Towards practical and fundamental limits of anonymity protection

URN zum Zitieren dieses Dokuments:: urn:nbn:de:bvb:355-epub-289446
DOI zum Zitieren dieses Dokuments:: 10.5283/epub.28944

Pham, Dang Vinh

Vorschau

Lizenz: Veröffentlichungsvertrag für Publikationen mit Print on Demand
PDF
(1MB)

Veröffentlichungsdatum dieses Volltextes: 21 Nov 2013 11:09

Details

Dokumentenart:	Hochschulschrift der Universität Regensburg (Dissertation)
Open Access Art:	Primärpublikation
Datum:	21 November 2013
Begutachter (Erstgutachter):	Prof. Dr. Dogan Kesdogan und Prof. RNDr., Vaclav Matyas
Tag der Prüfung:	15 November 2013
Institutionen:	Wirtschaftswissenschaften > Institut für Wirtschaftsinformatik > Lehrstuhl für Wirtschaftsinformatik IV (Prof. Dr. Doğan Kesdoğan) Informatik und Data Science > Lehrstuhl für Wirtschaftsinformatik IV (Prof. Dr. Doğan Kesdoğan)
Stichwörter / Keywords:	Privacy, anonymity set, Chaum Mix, combinatorial attack, hitting-set
Dewey-Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
Status:	Veröffentlicht
Begutachtet:	Ja, diese Version wurde begutachtet
An der Universität Regensburg entstanden:	Ja
Dokumenten-ID:	28944

Vorschau

Bibliographische Daten exportieren

Zusammenfassung (Englisch)

Zusammenfassung (Englisch)

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.

Übersetzung der Zusammenfassung (Deutsch)

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.

Nur für Besitzer und Autoren: Kontrollseite des Eintrags

Downloadstatistik

Weitere Literatur (mittels CORE)

Details

Vorschau

Bibliographische Daten exportieren

Zusammenfassung (Englisch)

Zusammenfassung (Englisch)

Übersetzung der Zusammenfassung (Deutsch)

Übersetzung der Zusammenfassung (Deutsch)

Downloadstatistik

Downloads

Weitere Literatur (mittels CORE)

Universitätsbibliothek