Extractable Common Randomness From Gaussian Trees: Topological and Algebraic Perspectives
Extractable Common Randomness From Gaussian Trees: Topological and Algebraic Perspectives
复制标题
从高斯树中提取常见的随机性：拓扑和代数的视角
DOI：
--
复制
发表时间：
2016
影响因子：
6.8
通讯作者：
Jing Deng
中科院分区：
文献类型：
--
作者：
A. Moharrer;Shuangqing Wei;G. Amariucai;Jing Deng
在本文中，我们研究无根高斯树的拓扑和代数性质，以表征其安全性能。这种性能是通过从给定树中提取公共随机性的相应潜力来衡量的，该潜力进一步由 max-min 和 min-max 条件互信息 (CMI) 值确定，分别取决于合法节点 Alice 和 Bob 以及窃听者 Eve 从树中选择变量的顺序。提出了一种新的操作，将高斯树转换为另一种高斯树，并对不同的高斯树进行排序。通过这样的操作我们构造了几个等价的高斯树类。每个类都包含多个高斯树，这些高斯树可以根据相关的最大-最小或最小-最大 CMI 度量进行部分排序，因此，我们可以在每个部分排序集（偏序集）中找到最安全和最不安全的树。所有偏序集的并集生成给定数量的变量的所有可能的非同构树。然后，我们为每个高斯树分配一个特定的多项式，并表明该多项式可以确定高斯树相对于同一类中的其他树的相对安全性能。最后，基于广义整数划分方法，我们提出了一种有效枚举所有偏序集最安全结构的新方法。
In this paper, we study both topological and algebraic properties of unrooted Gaussian trees in order to characterize their security performance. Such performance is measured by the corresponding potential in extracting common randomness from a given tree, which is further determined by max-min and min-max conditional mutual information (CMI) values, subject to the order of selecting variables from the tree by legitimate nodes Alice and Bob, and an eavesdropper Eve, respectively. A new operation is proposed to transform a Gaussian tree into another, and also to order different Gaussian trees. Through such operation we construct several equivalent classes of Gaussian trees. Each class includes multiple Gaussian trees that can be partially ordered based on the associated max-min or min-max CMI metric, and thus, we can find the most secure and the least secure trees in each partially ordered set (poset). The union of all posets generates all possible non-isomorphic trees of the given number of variables. Then, we assign a particular polynomial to each Gaussian tree, and show that such polynomial can determine the relative security performance of the Gaussian tree with respect to other trees within the same class. In the end, based on a generalized integer partition method, we propose a novel approach to efficiently enumerate the most secure structures of all posets.