有理数域上集合成员关系的保密判定协议

本文通过将有理数按位编码为矩阵，并结合ElGamal同态加密算法，设计了有理数域上集合成员关系的保密判定协议，其中点集成员关系的保密判定协议可适用于()2n n ≥维有理点。其次，应用模拟范例的方法严格证明了协议的安全性，同时协议能够保护集合的势。最后，比较分析表明当参与者的有理数满足一定条件时，本文设计的协议是高效的。

隐私集合计算是安全多方计算[1] [2]领域中的一类重要问题， 集合成员关系的保密判定问题是其中的一个基本问题，要求判定一个元素是否属于一个集合，而不泄露该元素和集合的具体信息。集合成员关系的保密判定问题在可搜索加密[3]、访问控制[4]、可撤销访问结构[5]等问题中有重要的应用。

集合成员关系保密判定可通过数据相等比较[1] [6] [7]、两方集合交集或交集的势[8] [9] [10] [11] [12]、集合包含关系[13] [14] [15] [16]的保密计算协议间接地来实现。上述方法或者需要将元素与集合中元素进行一一比较、或者不需要协议的全部计算功能，会使协议的效率欠佳或导致参与方拥有的信息泄露。文献[17]利用可交换加密方案提出了数集成员关系保密判定协议。文献[18]利用全同态加密，结合范德蒙行列式的性质，设计了集合成员判定关系的相关协议。上述协议均仅适用于整数集上的集合成员关系判定。

文献[19]首次设计了有理数域上集合成员关系保密判定协议， 并在数集成员关系保密判定协议的基础上，利用哥德尔编码将有理点编码为有理数，设计了点集成员关系的保密判定协议，但该协议只适用于2 维有理点。

由于信息技术的快速发展，与坐标定位相关的应用软件得到了广泛应用，使用户的位置信息的私密性成为需要关注的问题。因此，设计有理点的相关保密计算协议有重要的实用价值。本文借助文献[20]中提出的按位编码思想，结合ElGamal 同态加密算法，针对有理数集合成员关系和有理点集成员关系的判定问题设计了保密计算协议。

2. 预备知识 2.1. 安全多方计算模型 安全多方计算中通常使用半诚实模型和恶意模型。半诚实模型下的参与者会忠实地执行协议，但同时他们会保留执行协议中收到的中间信息，并试图推断其它参与者的输入。恶意模型下的参与者不按要求执行协议，可能有拒绝参加协议、提供错误的输入或者中间计算结果以及随时终止协议等行为。本文考虑半诚实模型下协议的安全性。

2.2. 半诚实模型下的安全性定义 设()1,2iP i =拥有私密信息iX ，利用协议π 合作计算函数()()()()12112212, , , , fXXfXXfXX=，其中() ()12, 1,2ifXXi =是iP 收到的输出。将参与者()1,2iP i =收到的信息序列记为 ()()()1212, , , , , , , iiiiiiliVIEWXXX r m mmfXπ=， 其中iX 是iP 的输入，ir 是iP 产生的随机数，()1,2, , itmtl=