|
|||||
|
|
| 通用可重组安全的多方求解Top-k协议设计 | |
| 作者姓名： | 栾明学 张秉晟 杨国正 臧铖 陈嘉俊 李泽昊 吴泽成 任奎 |
| 作者单位： | 1. 浙江大学网络空间安全研究中心;2. 浙商银行金融科技部;3. 浙商银行区块链技术应用研究院 |
| 基金项目： | 国家重点研发计划(2021YFB3101601)；;国家自然科学基金(62032021,61772236)；;浙江省重点研发计划(2019C03133)； |
| 摘 要： | 对于一个定点数多重集合S,第k小元素(又称Top-k元素) x∈S是指当集合中元素按照递增顺序排列时,刚好位于第k位置的元素.两方或多方安全求解它们输入的公共集合X的Top-k元素,是安全多方计算应用领域的经典案例.它能够使互不信任的多个数据持有方在不泄露自身数据的前提下,获取更大样本集合上的统计信息,从而实现隐私保护决策.本文提出了一种两方或多方分布式持有定点数数据的场景下,不依赖可信第三方,安全求解它们数据集合X中Top-k元素的协议,证明了其通用可重组(UC)安全性.协议使用了基于秘密分享的比较及加法安全多方计算协议作为构造模块,巧妙地从高到低按位依次确定并公布Top-k元素的p进制定点数表示.协议实现了O(logpM)的通信轮次复杂度,其中M为p进制数的最大取值, p为约定的定点数基数.实验证明,对于常见网络环境(包括局域网和广域网),当p=2i(i=2,···, 8)时,协议的通信时间和总运行时间均显著优于其他现有的Top-k求解协议. |
| 关 键 词： | 安全多方计算 中位数 Top-k元素 通用可重组(UC)安全 |