Uniform avoidance coupling, design of anonymity systems and matching theory
Uniform avoidance coupling, design of anonymity systems and matching theory
复制标题
均匀回避耦合、匿名系统设计与匹配理论
DOI：
10.1349/ddlp.2158
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ewa J. Infeld
中科院分区：
文献类型：
--
作者：
Ewa J. Infeld
我们首先介绍马尔可夫链的回避耦合，并概述现有结果。然后我们引入并激发了一个新的概念，均匀耦合。我们证明了循环上唯一的马尔可夫回避耦合是这种类型的，而简单随机游动的均匀回避耦合在树上是不可能的，并证明了它在几类图上是可能的。我们还推导了图中顶点邻域的一个条件，该条件等价于承认简单随机漫步的均匀避免耦合的图，并给出了一个算法，该算法使用顶点数量的运行时间多项式来测试这一点。然后，我们讨论了树上不可能存在马尔可夫回避耦合的猜想，并提出了如何进行证明。在这项工作的后半部分，我们讨论了旨在保证用户匿名的在线通信系统的设计。一个流行的范例是k-匿名。我们注意到典型社会关系的稀缺性使得k-匿名容易受到流量分析的影响，并提出了一种利用这种稀缺性将效率成本降低到我们可能需要的覆盖流量的方法。然后，我们使用br<s:1> gman定理来证明，对于给定的基础设施成本，由二部图中的边数建模，k-匿名提供了用户和观察到的行为之间可能完美匹配的最大数量。
We start by introducing avoidance coupling of Markov chains, with an overview of existing results. We then introduce and motivate a new notion, uniform coupling. We show that the only Markovian avoidance coupling on a cycle is of this type, and that uniform avoidance coupling of simple random walks is impossible on trees, and prove that it is possible on several classes of graphs. We also derive a condition on the vertex neighborhoods in a graph equivalent to that graph admitting a uniform avoidance coupling of simple random walks, and an algorithm that tests this with run time polynomial in the number of vertices. We then discuss a conjecture that no Markovian avoidance coupling can be possible on a tree and propose how a proof might proceed. In the second half of this work, we talk about the design of online communication systems that aim to guarantee anonymity for their users. A popular paradigm is k-anonymity. We notice that the scarcity of a typical social relation makes k-anonymity vulnerable to traffic analysis, and propose a way to use this scarcity to reduce the efficiency cost to exactly the amount of cover traffic we might need. Then we use Brègman’s theorem to show that for a given infrastructure cost, modelled by the number of edges in a bipartite graph, k-anonymity offers the highest number of possible perfect matchings between users and observed behaviors.