%0 Conference Proceedings
%T Towards Relations Between the Hitting-Set Attack and the Statistical Disclosure Attack
%+ Universität Regensburg (UR)
%A Pham, Dang, Vinh
%A Kesdogan, Dogan
%Z Part 1: Privacy
%< avec comité de lecture
%( IFIP Advances in Information and Communication Technology
%B 30th IFIP International Information Security Conference (SEC)
%C Hamburg, Germany
%Y Hannes Federrath
%Y Dieter Gollmann
%3 ICT Systems Security and Privacy Protection
%V AICT-455
%P 35-50
%8 2015-05-26
%D 2015
%R 10.1007/978-3-319-18467-8_3
%Z Computer Science [cs]Conference papers
%X The Minimal-Hitting-Set attack (HS-attack) is a well-known, provably optimal exact attack against the anonymity provided by Chaumian Mixes (Threshold-Mixes). This attack allows an attacker to identify the fixed set of communication partners of a given user by observing all messages sent and received by a Chaum Mix. In contrast to this, the Statistical Disclosure attack (SDA) provides a guess of that user’s contacts, based on statistical analyses of the observed message exchanges.We contribute the first closed formula that shows the influence of traffic distributions on the least number of observations of the Mix to complete the HS-attack. This measures when the Mix fails to hide a user’s partners, such that the user cannot plausibly deny the identified contacts. It reveals that the HS-attack requires asymptotically less observations to identify a user’s partners than the SDA, which guesses them with a given bias. This number of observations is <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>O</mi> <mo stretchy="false">(</mo> <mfrac> <mn>1</mn> <mi>p</mi> </mfrac> <mo stretchy="false">)</mo></math> for the HS-attack and <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>O</mi> <mo stretchy="false">(</mo> <mfrac> <mn>1</mn> <msup> <mi>p</mi> <mn>2</mn> </msup> </mfrac> <mo stretchy="false">)</mo></math> for the SDA, where <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>p</mi></math> the probability that the attacked user contacts his least frequent partner.
%G English
%Z TC 11
%2 https://inria.hal.science/hal-01345094/document
%2 https://inria.hal.science/hal-01345094/file/337885_1_En_3_Chapter.pdf
%L hal-01345094
%U https://inria.hal.science/hal-01345094
%~ IFIP
%~ IFIP-AICT
%~ IFIP-TC
%~ IFIP-TC11
%~ IFIP-AICT-455
%~ IFIP-SEC