通用可重组安全的多方求解Top-k协议设计

Universally Composable Secure Multi-party Computation of the Top-k Element

对于一个定点数多重集合S,第k小元素(又称Top-k元素) x∈S是指当集合中元素按照递增顺序排列时,刚好位于第k位置的元素.两方或多方安全求解它们输入的公共集合X的Top-k元素,是安全多方计算应用领域的经典案例.它能够使互不信任的多个数据持有方在不泄露自身数据的前提下,获取更大样本集合上的统计信息,从而实现隐私保护决策.本文提出了一种两方或多方分布式持有定点数数据的场景下,不依赖可信第三方,安全求解它们数据集合X中Top-k元素的协议,证明了其通用可重组(UC)安全性.协议使用了基于秘密分享的比较及加法安全多方计算协议作为构造模块,巧妙地从高到低按位依次确定并公布Top-k元素的p进制定点数表示.协议实现了O(logpM)的通信轮次复杂度,其中M为p进制数的最大取值, p为约定的定点数基数.实验证明,对于常见网络环境(包括局域网和广域网),当p=2^(i)(i=2,···, 8)时,协议的通信时间和总运行时间均显著优于其他现有的Top-k求解协议.

The kth-minimum element(i.e. Top-k element) in a multiset S of fixed-point numbers is the kth element when the elements in S are sorted in increasing order. One of the classic cases of secure multi-party computation(MPC) application is safely evaluating the Top-k element of the union set X of two or multi parties’ secret set, which enables multiple data owners who do not trust each other to obtain statistical information on a larger set without disclosing their own data, realizing the privacy protecting decision. This paper proposes a protocol to evaluate the Top-k element of their union set X secretly without a trusted third party when each party holds a multiset of fixed-point numbers, and its universally composable(UC) security has been proved. The protocol is based on secret sharing,constructing with the comparison and addition secure computing blocks, and skillfully evaluates the base-p representation of the Top-k element from high position to low position while disclosing them one by one. Its communication round complexity is O(logpM), where M is the maximum value of any number of base p, and p is such the base. Experiments show that, for a common network setting(LAN or WAN), when p = 2^(i)(i = 2, · · ·, 8), the communicating and total running time of the proposed protocol are significantly better than other existing Top-k protocols.