Name
Abstract | ||
|---|---|---|
The Minimal-Hitting-Set attack (HS-attack) [10] is a well-known passive intersection attack againstMix-based anonymity systems, applicable in cases where communication behaviour is non-uniform and unknown. The attack allows an observer to identify uniquely the fixed set of communication partners of a particular user by observing the messages of all senders and receivers using a Mix. Whilst the attack makes use of a provably minimal number of observations, it also requires solving an NP-complete problem. No prior research, to our knowledge, analyses the average complexity of this attack as opposed to its worst case. We choose to explore the HS-attack, as opposed to statistical attacks, to provide a baseline metric and a practical attack for unambiguously identifying anonymous users. We show that the average complexity of the HS-attack can vary between a worst-case exponential complexity and a linear-time complexity according to the Mix parameters. We provide a closed formula for this relationship, giving a precise measure of the resistance of Mixes against the HS-attack in practice, and allowing adjustment of their parameters to reach a desired level of strength. |
Year | Venue | Keywords |
|---|---|---|
2011 | ESORICS | mix parameter,average complexity,well-known passive intersection attack,practical complexity-theoretic analysis,linear-time complexity,minimal-hitting-set attack,practical attack,mix system,communication partner,communication behaviour,statistical attack,worst-case exponential complexity |
Field | DocType | Volume |
Attack model,Computer security,Computer science,Exponential complexity,Anonymity,Observer (quantum physics) | Conference | 6879 |
ISSN | Citations | PageRank |
0302-9743 | 6 | 0.47 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dang Vinh Pham | 1 | 11 | 1.56 |
| Joss Wright | 2 | 39 | 6.42 |
| Dogan Kesdogan | 3 | 355 | 42.53 |