Provable Unlinkability Against Traffic Analysis. Berman, R., Fiat, A., & Ta-Shma, A. February 2004. ![Provable Unlinkability Against Traffic Analysis [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex We consider unlinkability of communication problem: given n users, each sending a message to some destination, encode and route the messages so that an adversary analyzing the traffic in the communication network cannot link the senders with the recipients. A solution should have a small communication overhead, that is, the number of additional messages should be kept low. David Chaum introduced idea of mixes for solving this problem. His approach was developed further by Simon and Rackoff, and implemented later as the onion protocol. Even if the onion protocol is widely regarded as secure and used in practice, formal arguments supporting this claim are rare and far from being complete. On top of that, in certain scenarios very simple tricks suffice to break security without breaking the cryptographic primitives. It turns out that one source of difficulties in analyzing the onion protocols security is the adversary model. In a recent work, Berman, Fiat and Ta-Shma develop a new and more realistic model in which only a constant fraction of communication lines can be accessed by an adversary, the number of messages does not need to be high and the preferences of the users are taken into account. For this model they prove that with high probability a good level of unlinkability is obtained after steps of the onion protocol where n is the number of messages sent. In this paper we improve these results: we show that the same level of unlinkability (expressed as variation distance between certain probability distributions) is obtained with high probability already after steps of the onion protocol. Asymptotically, this is the best result possible, since obviously (log n) steps are necessary. On top of that, our analysis is much simpler. It is based on path coupling technique designed for showing rapid mixing of Markov chains.
@conference {berman-fc2004,
title = {Provable Unlinkability Against Traffic Analysis},
booktitle = {Proceedings of Financial Cryptography (FC {\textquoteright}04)},
year = {2004},
month = {February},
pages = {266{\textendash}280},
publisher = {Springer-Verlag, LNCS 3110},
organization = {Springer-Verlag, LNCS 3110},
abstract = {We consider unlinkability of communication problem: given n users, each sending a message to some destination, encode and route the messages so that an adversary analyzing the traffic in the communication network cannot link the senders with the recipients. A solution should have a small communication overhead, that is, the number of additional messages should be kept low.
David Chaum introduced idea of mixes for solving this problem. His approach was developed further by Simon and Rackoff, and implemented later as the onion protocol. Even if the onion protocol is widely regarded as secure and used in practice, formal arguments supporting this claim are rare and far from being complete. On top of that, in certain scenarios very simple tricks suffice to break security without breaking the cryptographic primitives. It turns out that one source of difficulties in analyzing the onion protocols security is the adversary model. In a recent work, Berman, Fiat and Ta-Shma develop a new and more realistic model in which only a constant fraction of communication lines can be accessed by an adversary, the number of messages does not need to be high and the preferences of the users are taken into account. For this model they prove that with high probability a good level of unlinkability is obtained after steps of the onion protocol where n is the number of messages sent.
In this paper we improve these results: we show that the same level of unlinkability (expressed as variation distance between certain probability distributions) is obtained with high probability already after steps of the onion protocol. Asymptotically, this is the best result possible, since obviously (log n) steps are necessary. On top of that, our analysis is much simpler. It is based on path coupling technique designed for showing rapid mixing of Markov chains.},
keywords = {anonymity, Markov chain, path coupling, rapid mixing, unlinkability},
isbn = {978-3-540-23208-7},
doi = {10.1007/b100936},
url = {http://www.springerlink.com/content/cknab9y9bpete2ha/},
author = {Ron Berman and Amos Fiat and Amnon Ta-Shma},
editor = {Ari Juels}
}
Downloads: 0
{"_id":"RPDLGKgbkaqcDoBsb","bibbaseid":"berman-fiat-tashma-provableunlinkabilityagainsttrafficanalysis-2004","downloads":0,"creationDate":"2018-07-03T04:50:29.023Z","title":"Provable Unlinkability Against Traffic Analysis","author_short":["Berman, R.","Fiat, A.","Ta-Shma, A."],"year":2004,"bibtype":"conference","biburl":"https://gnunet.org/bibliography/export/bibtex","bibdata":{"bibtype":"conference","type":"conference","title":"Provable Unlinkability Against Traffic Analysis","booktitle":"Proceedings of Financial Cryptography (FC \\textquoteright04)","year":"2004","month":"February","pages":"266\\textendash280","publisher":"Springer-Verlag, LNCS 3110","organization":"Springer-Verlag, LNCS 3110","abstract":"We consider unlinkability of communication problem: given n users, each sending a message to some destination, encode and route the messages so that an adversary analyzing the traffic in the communication network cannot link the senders with the recipients. A solution should have a small communication overhead, that is, the number of additional messages should be kept low. David Chaum introduced idea of mixes for solving this problem. His approach was developed further by Simon and Rackoff, and implemented later as the onion protocol. Even if the onion protocol is widely regarded as secure and used in practice, formal arguments supporting this claim are rare and far from being complete. On top of that, in certain scenarios very simple tricks suffice to break security without breaking the cryptographic primitives. It turns out that one source of difficulties in analyzing the onion protocols security is the adversary model. In a recent work, Berman, Fiat and Ta-Shma develop a new and more realistic model in which only a constant fraction of communication lines can be accessed by an adversary, the number of messages does not need to be high and the preferences of the users are taken into account. For this model they prove that with high probability a good level of unlinkability is obtained after steps of the onion protocol where n is the number of messages sent. In this paper we improve these results: we show that the same level of unlinkability (expressed as variation distance between certain probability distributions) is obtained with high probability already after steps of the onion protocol. Asymptotically, this is the best result possible, since obviously (log n) steps are necessary. On top of that, our analysis is much simpler. It is based on path coupling technique designed for showing rapid mixing of Markov chains.","keywords":"anonymity, Markov chain, path coupling, rapid mixing, unlinkability","isbn":"978-3-540-23208-7","doi":"10.1007/b100936","url":"http://www.springerlink.com/content/cknab9y9bpete2ha/","author":[{"firstnames":["Ron"],"propositions":[],"lastnames":["Berman"],"suffixes":[]},{"firstnames":["Amos"],"propositions":[],"lastnames":["Fiat"],"suffixes":[]},{"firstnames":["Amnon"],"propositions":[],"lastnames":["Ta-Shma"],"suffixes":[]}],"editor":[{"firstnames":["Ari"],"propositions":[],"lastnames":["Juels"],"suffixes":[]}],"bibtex":"@conference {berman-fc2004,\n\ttitle = {Provable Unlinkability Against Traffic Analysis},\n\tbooktitle = {Proceedings of Financial Cryptography (FC {\\textquoteright}04)},\n\tyear = {2004},\n\tmonth = {February},\n\tpages = {266{\\textendash}280},\n\tpublisher = {Springer-Verlag, LNCS 3110},\n\torganization = {Springer-Verlag, LNCS 3110},\n\tabstract = {We consider unlinkability of communication problem: given n users, each sending a message to some destination, encode and route the messages so that an adversary analyzing the traffic in the communication network cannot link the senders with the recipients. A solution should have a small communication overhead, that is, the number of additional messages should be kept low.\r\nDavid Chaum introduced idea of mixes for solving this problem. His approach was developed further by Simon and Rackoff, and implemented later as the onion protocol. Even if the onion protocol is widely regarded as secure and used in practice, formal arguments supporting this claim are rare and far from being complete. On top of that, in certain scenarios very simple tricks suffice to break security without breaking the cryptographic primitives. It turns out that one source of difficulties in analyzing the onion protocols security is the adversary model. In a recent work, Berman, Fiat and Ta-Shma develop a new and more realistic model in which only a constant fraction of communication lines can be accessed by an adversary, the number of messages does not need to be high and the preferences of the users are taken into account. For this model they prove that with high probability a good level of unlinkability is obtained after steps of the onion protocol where n is the number of messages sent.\r\nIn this paper we improve these results: we show that the same level of unlinkability (expressed as variation distance between certain probability distributions) is obtained with high probability already after steps of the onion protocol. Asymptotically, this is the best result possible, since obviously (log n) steps are necessary. On top of that, our analysis is much simpler. It is based on path coupling technique designed for showing rapid mixing of Markov chains.},\n\tkeywords = {anonymity, Markov chain, path coupling, rapid mixing, unlinkability},\n\tisbn = {978-3-540-23208-7},\n\tdoi = {10.1007/b100936},\n\turl = {http://www.springerlink.com/content/cknab9y9bpete2ha/},\n\tauthor = {Ron Berman and Amos Fiat and Amnon Ta-Shma},\n\teditor = {Ari Juels}\n}\n","author_short":["Berman, R.","Fiat, A.","Ta-Shma, A."],"editor_short":["Juels, A."],"key":"berman-fc2004","id":"berman-fc2004","bibbaseid":"berman-fiat-tashma-provableunlinkabilityagainsttrafficanalysis-2004","role":"author","urls":{"Paper":"http://www.springerlink.com/content/cknab9y9bpete2ha/"},"keyword":["anonymity","Markov chain","path coupling","rapid mixing","unlinkability"],"downloads":0},"search_terms":["provable","unlinkability","against","traffic","analysis","berman","fiat","ta-shma"],"keywords":["anonymity","markov chain","path coupling","rapid mixing","unlinkability"],"authorIDs":[],"dataSources":["FWsPTwsmjtrBtRS3B"]}