可同时求解最大最小值的安全保密计算协议

摘要

安全多方计算因其具有去中心化、输入隐私性、公平性等特点，对于研究数据隐私保护问题具有重要的价值，其中一个最基本的问题就是保密计算多个数据的最值。本文针对现有方案不能一次性保密计算最大值和最小值、效率低下、计算结果由特定解密密钥持有者获取等问题，提出一种无需可信第三方的可同时求解最大值、最小值的安全高效保密计算方案。本文方案首先给出一个可同时求解最大值和最小值的编码方法，其基本思想是给定一个势为l的有序数全集（l≥参与者个数n），各参与者据其所持数据在全集中的位置编码得到长度为l的数组（数值所在位置编为随机数，其他位置编为1），各数组按位相乘后的最左和最右非1数值所在位置即为最大值和最小值在全集中的位置。在上述基础上，结合ElGamal同态加密算法保证所有参与者数据的安全性，并利用最大门限解密使得每个参与者都持有部分解密密钥，进而解决保密计算结果由唯一的指定解密密钥持有者获取的安全性瓶颈问题。接着，基于理想–现实模拟范例方法证明所提方案在半诚实模型下的安全性，结果表明所提方案可以抵抗任意参与者的合谋攻击。最后，选取同类最大（小）值方案进行效率分析和性能对比。理论分析和仿真验证表明所提协议在满足更高安全性的前提下，计算复杂度和通信复杂度较已有方案具有一定的优势。

关键词

安全多方计算 / 最大值最小值 / ElGamal同态加密 / 门限解密 / 模拟范例