高效的隐私保护多方多数据排序

安全多方计算允许具有私密输入的多个参与方联合计算一个多输入函数而不泄露各参与方私有输入的任何信息,因此近年来受到广泛关注.作为安全多方计算中的一个基础问题,隐私保护排序允许多个参与方在不泄露数据集隐私的前提下计算多个数据集的排序结果,广泛应用于产品定价、拍卖等场景.现有的隐私保护排序协议大多只支持两个参与方.而已有的多方多数据排序协议通信开销大、计算复杂度高,整体效率较低.现有隐私保护排序协议均未考虑恶意参与者的穷举攻击,因此安全保护不足.对此,本文提出一个高效的隐私保护多方多数据排序协议.多个参与方仅需O(1)轮交互即可以隐私保护的方式获得其持有的多个数据的排序结果.具体来讲,本文设计一种基于多项式的编码方法,将参与方的数据集编码为一个多项式,其每项的指数和系数分别代表数据和该数据的个数.通过多项式加法可实现多个参与方数据集的排序.同时,本文设计了多项式加密、聚合多项式生成和解密多项式生成算法,在保证计算正确性的同时实现多项式的隐私保护.最后,各参与方通过不经意传输技术获得排序结果.本文定义了不合谋参与方穷举攻击下的恶意安全.安全性分析表明本文协议不仅实现了半诚实安全性,而且达到了不合谋恶意用户穷举攻击的恶意安全性.此外,大量实验表明本文提出的协议在通信和计算方面都十分高效.如当参与方数量为15、每个参与方持有20000个数据、数据上界为500000时,本文协议的通信和计算开销分别为898.44 MB和69.76 s,仅为LDYW协议的12.08%和76.85%;而相对于AHM+方案,本文协议在通信开销仅增加约4倍的情况下使计算效率提升了约20倍.