TY - GEN
T1 - Bounds on the leakage of the input's distribution in information-Hiding protocols
AU - Bhowmick, Abhishek
AU - Palamidessi, Catuscia
PY - 2009/7/17
Y1 - 2009/7/17
N2 - In information-hiding, an adversary that tries to infer the secret information has a higher probability of success if it knows the distribution on the secrets. We show that if the system leaks probabilistically some information about the secrets, (that is, if there is a probabilistic correlation between the secrets and some observables) then the adversary can approximate such distribution by repeating the observations. More precisely, it can approximate the distribution on the observables by computing their frequencies, and then derive the distribution on the secrets by using the correlation in the inverse direction. We illustrate this method, and then we study the bounds on the approximation error associated with it, for various natural notions of error. As a case study, we apply our results to Crowds, a protocol for anonymous communication.
AB - In information-hiding, an adversary that tries to infer the secret information has a higher probability of success if it knows the distribution on the secrets. We show that if the system leaks probabilistically some information about the secrets, (that is, if there is a probabilistic correlation between the secrets and some observables) then the adversary can approximate such distribution by repeating the observations. More precisely, it can approximate the distribution on the observables by computing their frequencies, and then derive the distribution on the secrets by using the correlation in the inverse direction. We illustrate this method, and then we study the bounds on the approximation error associated with it, for various natural notions of error. As a case study, we apply our results to Crowds, a protocol for anonymous communication.
U2 - 10.1007/978-3-642-00945-7_3
DO - 10.1007/978-3-642-00945-7_3
M3 - Conference contribution
AN - SCOPUS:67650283503
SN - 3642009441
SN - 9783642009440
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 36
EP - 51
BT - Trustworthy Global Computing - 4th International Symposium, TGC 2008, Revised Selected Papers
T2 - 4th International Symposium on Trustworthy Global Computing, TGC 2008
Y2 - 3 November 2008 through 4 November 2008
ER -