隐私保护整数点和区间关系判定问题

马敏耀，吴 恋，刘 卓，徐 艺

（1.贵州师范学院数学与大数据学院，贵阳 550018；2.贵州师范学院网络空间安全重点实验室，贵阳 550018）

（*通信作者电子邮箱minyaoma2006@163.com）

0 引言

安全多方计算研究如何使互不信任的多个参与方在不借助任何第三方的情况下实现保护隐私的协同计算。安全多方计算技术常用来解决各种隐私保护科学计算问题。只含两个参与方的安全多方计算称为安全两方计算，即参与方A1和A2分别拥有自己的秘密输入x1和x2，在不借助任何第三方的情况下联合计算某个二元函数（y1，y2）=f（x1，x2），协议结束后，参与方Ai得到本方的正确输出yi（正确性）且任何一方的输入都未泄露给其他人（安全性）。1982 年，姚期智在文献［1］中最先提出安全多方计算的思想。随后，文献［2-4］研究安全多方计算的可行性问题，即具体安全模型下安全多方计算协议的存在性问题，以及构造能够计算任意可计算函数的通用安全多方计算协议。由于通用协议的执行效率相对较低，因此大量的文献研究具体安全多方计算问题的解决方案，例如：隐私保护线性代数计算［5］、隐私保护DNA 序列汉明距离计算［6］、安全数据比较［7-9］、安全多方量子计算［8-10］、安全多方集合计算［10-15］、隐私保护机器学习［16］、保密区间计算［17-19］等。

点和区间关系的保密判定问题，是指在保护双方隐私的情况下，判断一方持有的点是否包含在另一方持有的区间中。此问题在保护隐私的范围查询或定位搜索中有着非常广泛的应用。文献［17-18］利用安全多方计算的思想研究了点和区间关系的隐私保护判定协议，并将数和区间放在有理数范围内考虑，文献［19］将点和区间关系的隐私保护判定问题推广到实数范围内。

文献［19］同时研究了整数点和整数区间关系的保护判定问题：即在隐私保护的前提下，协议双方如何判断一个整数点是否属于一个整数区间，其中整数区间［y1，y2］指的是从y1到y2的全部y2–y1+1个整数构成的集合。该文定义了一种0-1编码规则，基于此规则给出了整数点属于整数区间的一个判定规则，以此判定规则为基础，设计了一个解决方案。分析发现该文给出的判定规则存在缺陷，导致基于此判定规则设计的解决方案存在几个主要缺陷：一是协议可能输出错误的判定结果；二是协议可能导致整数点持有方的隐私泄露；三是协议的复杂度偏高。鉴于此，本文进一步研究隐私保护整数点和区间关系判定问题，主要工作如下：

1）定义新的0-1 编码规则，基于此编码规则，证明了整数点属于整数区间的一个充分必要条件，进而给出整数点是否属于整数区间的一个新的判定规则。

2）基于新的判定规则，以Goldwasser-Micali 加密体制［20］为主要密码学工具，设计了整数点是否属于整数区间的一个判定协议。

3）证明了提出的协议是正确的，即不会输出错误的结果；证明了协议在半诚实攻击者模型［21］下是安全的，即不会导致任何一方的隐私泄露；协议的复杂度在文献［19］的基础上整体降低了约一半。

1 知识准备

1.1 Goldwasser-Micali加密体制

N是正整数，定 义。称是模N的二次剩余，若x2≡amodN对某个x∈ZN成立；否则称a为模N的二次非剩余。判断a是否是模N的二次剩余的问题称为模N的二次剩余问题，当未知N的素因数分解时该问题是困难的，已知N的素因数分解时该问题是容易的。

对素数p和任意，x模p的勒让德符号定义为：

设合数N的素因子（可重复）分解为N=p1p2…pk，则称为x模N的雅可比符号，其中是x模pi的勒让德符号。

Goldwasser-Micali 加密体制［20］是基于模N的二次剩余问题困难性的公钥加密体制，其密钥生成算法、加密算法和解密算法描述如下。

1）密钥生成算法。随机生成两个大素数p和q，计算N=pq，选取模N的一个二次非剩余使其雅可比符号1。公钥是pk=(δ，N)，私钥是sk=(p，q)。

2）加密算法。对任意明文比特x∈{0，1}，选取秘密随机数，计算密文Epk(x)=r2δxmodN。

在未知私钥（即未知大整数N的因数分解）的情况下，模N的二次剩余问题是困难的，故解密是困难的；反之，已知私钥（即知道N的因数分解）时，模N的二次剩余问题是容易的，故解密是容易的。该密码系统具有如下特性。

1）概率加密特性：每次加密都有随机数r参与运算。

2）异或同态性：Epk(x1)和Epk(x2)分别是x1和x2的密文，则(Epk(x1)⋅Epk(x2)) modN是x1⊕x2的密文，即(Epk(x1)⋅Epk(x2)) modN=Epk(x1⊕x2)。

1.2 半诚实攻击模型下的安全两方计算模型

记f：{0，1}*×{0，1}*→{0，1}*×{0，1}*是任意一个概率多项式时间二元函数，其中f(X，Y)=(f1(X，X)，f2(X，X))，记Π 是计算函数f的一个两方协议。两个参与方P1和P2分别以X和Y作为输入，他们执行结束协议Π 之后，参与方P1的view记为，参与方P2的view记为，其中ri表示Pi的内部随机带的输出，mij表示Pi收到的第j条信息，Pi的output记为。称Π 是半诚实攻击模型下计算二元函数f=(f1，f2)的安全两方计算协议，如果存在概率多项式时间算法S1和S2，使得下面两个关系式成立，其中≡c表示随机变量簇是计算不可区分的：

1.3 整数点与整数区间属于关系判定问题

符号约定 本文所指的全集U={x1，x2，…，xn}都是由n个连续整数构成的集合，即xi=xi-1+1，2 ≤i≤n。整数区间[y1，y2]指由两整数y1和y2之间的y2-y1+1个连续整数构成的集合，即[y1，y2]={y1，y1+1，y1+2，…，y2}。例如全集U=｛1，2，3，4，5，6，7｝，整数区间［3，6］=｛3，4，5，6｝。用符号“||”表示两个0-1 串的级联，如x=100，y=1100，则x||y=1001100。用符号“⇔”表示等价关系“当且仅当”。

定义1设全集U={x1，x2，…，xn}是由n个连续整数构成的公开集合，整数点与整数区间属于关系判定问题被定义为：Alice 和Bob 分别拥有整数点x∈U和整数区间[y1，y2]⊆U，在保证各自的输入信息不被泄露的情况下，Alice和Bob如何正确地判断x∈[y1，y2]或x∉[y1，y2]。

定义2比特串s=s1s2…sn∈{0，1}m中所含“1”的个数称 为s的重量，记 为N(s，1)，即。例如若s=001110010，则N(s，1)=4。

2 已有工作回顾与分析

为了解决整数点与整数区间属于关系判定问题，文献［19］设计了一个协议（文献［19］协议1）。下面先简单回顾该文的判定规则，然后指出其判定规则存在缺陷。

编码规则1［19］Alice 和Bob 根据自己的输入按如下规则进行0-1编码：

1）Alice 将点x编码成长度为n的0-1 码a=a1a2…an：若xi=x则ai=1；否则ai=0。

2）Bob 将区间[y1，y2]的左端点y1编码成长度为n的0-1码b=b1b2…bn：若xi≥y1则bi=1；否则bi=0。将右端点y2编码为长度为n的0-1码c=c1c2…cn：若xi≥y2则ci=1；否则ci=0。

该文基于此0-1编码规则，得出如下判定规则。

判定规则1［19］若N((b||c)⊕(a||a)，1)=N(b||c，1)，则x∈[y1，y2]；否则x∉[y1，y2]。即若(b||c)⊕(a||a)和b||c中“1”的个数相同，则x∈[y1，y2]；否则x∉[y1，y2]。

基于此判定规则，该文设计了解决整数点与整数区间属于关系判定问题的一个协议。然而，分析发现，基于判定规则1来设计协议，存在下面几个主要缺陷：

1）会输出错误结果。当x=y2时，应该输出x∈[y1，y2]，但按上述判定规则和该文的协议描述，最终将输出x∉[y1，y2]，即双方将输出错误的结果。

2）会导致Alice 的隐私泄露。当x∉[y1，y2]时，Bob 能够得到有关x的更多信息，即知道x＜y1或x＞y2。因为当x＜y1时，(b||c)⊕(a||a)中“1”的个数比b||c中“1”的个数大2；当x＞y2时，(b||c)⊕(a||a)中“1”的个数比b||c中“1”的个数少2。在该文的协议中，Bob 能够准确地知道属于哪一种情形，因此他能准确地判断x＜y1或x＞y2。

3）复杂度偏高。因为需要对2n长的0-1 串（如b||c和a||a）进行操作，其中n是全集U所含元素个数，因此协议的复杂度将偏高。与此相比，本文提出的协议只对n长的0-1串进行操作，计算复杂度和通信复杂度降低约一半。

下面通过实例1和实例2分别对1）和2）进行辅助说明。

实例1 全集U=｛1，2，3，4，5，6，7｝，Alice拥有整数x=6，Bob 拥有整数区间[y1，y2]=[3，6]，正确结果应该为x∈[y1，y2]。Alice 得到0-1 编码a=0000010，Bob 得到0-1 编码b=0011111和c=0000011。因此b||c=0011111||0000011且

可见(b||c)⊕(a||a)中“1”的个数为5，b||c中“1”的个数为7，即N((b||c)⊕(a||a)，1)≠N(b||c，1)，根据上述判定规则将输出x∉[y1，y2]的错误结果。

实例2 全集U=｛1，2，3，4，5，6，7｝，Alice拥有整数x=7，Bob 拥有整数区间[y1，y2]=[3，6]。Alice 得 到0-1 编 码a=0000001，Bob 得到0-1 编码b=0011111 和c=0000011。因此b||c=0011111||0000011且

可见(b||c)⊕(a||a)中“1”的个数为5，b||c中“1”的个数为7，即(b||c)⊕(a||a)中“1”的个数比b||c中“1”的个数少2，从而Bob得知x＞y2，特别，本例中Bob 完全得知x=7，Alice 的输入完全泄露。

3 整数点与整数区间属于关系判定协议

基于第2 章的分析，本章将重新研究整数点与整数区间属于关系判定问题的解决方案。定义新的0-1 编码规则，并给出新的判定规则，基于此规则在半诚实攻击者模型下给出一个协议，并对协议的安全性给出基于模拟器的证明。

3.1 0-1编码规则和判定规则

编码规则2 Alice和Bob按如下规则进行0-1编码：

1）整数x的编码规则。Alice 将自己的整数x编码成长度为n的0-1码a=a1a2…an，满足：若xi=x则ai=1，否则ai=0。

2）整数区间[y1，y2]的编码规则。Bob 将自己的区间[y1，y2]编码成长度为n的0-1 码b=b1b2…bn，满足：若y1≤xi≤y2则bi=1，否则bi=0。

下面给出实例3对新的0-1编码规则进行辅助说明。

实例3 全集U=｛1，2，3，4，5，6，7｝，Alice拥有整数x=6，Bob 拥有整数区间[y1，y2]=[3，6]。则Alice 拥有0-1 编码a=0000010，Bob拥有0-1编码b=0011110。

根据如上定义的0-1 编码规则，下面证明一个结论，本文将该结论用作判定整数点是否属于整数区间的判定规则。

定理1全集U={x1，x2，…，xn}是由n个连续整数构成的集合，对整数点x∈U和整数区间[y1，y2]⊆U，将x和[y1，y2]按编码规则2进行编码后得到0-1编码a和b，则

即x∈[y1，y2]当且仅当b⊕a中所含“1”的个数比b中所含“1”的个数少1。进一步有

证明 令x=xi，由整数x的编码规则知，即ai=1。令[y1，y2]=[xk，xj]，即y1=xk且y2=xj，由区间[y1，y2]的编码规则可知。

假设x∈[y1，y2]，即y1≤x≤y2，有xk≤xi≤xj，故有k≤i≤j，因此bi=1。由ai=1可知ai⊕bi=0，故b⊕a中“1”的个数至少比b中“1”的个数少1。由于a中只有一个“1”，故b⊕a能且只能引起b中的1 比特变化，因此可得N(b⊕a，1)-N(b，1)=-1。反 之，若N(b⊕a，1)-N(b，1)=-1，则 由b=可断定k≤i≤j，从而有xk≤xi≤xj，即y1≤x≤y2，因此x∈[y1，y2]。

综上有x∈[y1，y2]⇔N(b⊕a，1)-N(b，1)=-1。类 似地，可证x∉[y1，y2]⇔N(b⊕a，1)-N(b，1)=1。 证毕。

根据定理1的结论，得到如下判定规则。

判定规则 2 若N(b⊕a，1)-N(b，1)=-1，则x∈[y1，y2]；否则x∉[y1，y2]。

由于定理1 的两个结论都是充分必要条件，因此判定规则2 不存在判断错误的情况。又由于N(b⊕a，1)-N(b，1)的值只有1 和-1 两种情况，因此根据N(b⊕a，1)-N(b，1)的值只能得到x∈[y1，y2]或x∉[y1，y2]，除此之外推不出x＜y1或x＞y2及其他额外信息。可见，判定规则2很好地避免了判定规则1 存在的缺陷。此外，在下文中会发现，本文基于判定规则2设计的协议也有较高的执行效率。

下面给出实例4和实例5对判定规则进行辅助说明。

实例4 全集U=｛1，2，3，4，5，6，7｝，Alice拥有整数x=6，Bob 拥有整数区间[y1，y2]=[3，6]。则Alice 拥有0-1 编码a=0000010，Bob 拥有0-1 编码b=0011110。则b⊕a=0011100，故有N(b⊕a，1)-N(b，1)=-1，Alice 和Bob 得到正确的判断结果x∈[y1，y2]。

实例5 全集U=｛1，2，3，4，5，6，7｝，Alice拥有整数x=2，Bob 拥有整数区间[y1，y2]=[3，6]。则Alice 拥有0-1 编码a=0100000，Bob 拥有0-1 编码b=0011110。则b⊕a=0111110，故有N(b⊕a，1)-N(b，1)=1，Alice 和Bob 得到正确的判断结果x∉[y1，y2]。

3.2 协议描述

本节构造的协议基于Goldwasser-Micali 加密体制，主要利用其概率加密特性和异或同态性。在公私密钥对不变的情况下，有E(m1)⋅E(m2) modN=E(m1⊕m2)，其中N是加密运算的模数。协议开始之前，Bob 生成自己的公私钥对，并将公钥告知Alice。下文中的加密E(⋅) 都是指用Bob 的公钥进行加密，解密都是指用Bob的私钥进行解密。

协议1 整数点和整数区间属于关系判定协议。

输入：全集U={x1，x2，…，xn}是由n个连续整数构成的公开集合，用户Alice 拥有一个整数x∈U，用户Bob 拥有一个整数区间[y1，y2]⊆U。

输出：Alice和Bob都输出x∈[y1，y2]或x∉[y1，y2]。

Alice和Bob执行如下协议步骤：

1）Bob 按如上编码规则2 将整数区间[y1，y2]编码为n长的0-1编码b=b1b2…bn，并逐比特加密b，得到n个密文E(b)=(E(b1)，E(b2)，…，E(bn))，将这n个密文发送给Alice。

2）Alice 按如上编码规则2 将整数x编码为n长的0-1 编码a=a1a2…an，并逐比特加密a，得到n个密文E(a)=(E(a1)，E(a2)，…，E(an))。Alice 将这n个密文与Bob 传来的n个密文E(b)的对应项进行模N相乘，根据加密体制的异或同态性得到如下n个密文：

E(a⊕b)=(E(a1⊕b1)，E(a2⊕b2)，…，E(an⊕bn))

Alice 秘密选取{1，2，…，n}上的一个随机置换T，对这n个密文进行随机置换，将得到的如下n个密文发送给Bob：

3）Bob对收到的n个密文T(E(a⊕b))逐项解密后得到：

计 算D=N(T(a⊕b)，1)-N(b，1)，若D=-1，则x∈[y1，y2]，否则x∉[y1，y2]。

4）Bob将结果告诉Alice。

3.3 正确性和安全性分析

协议1 的正确性由定理1 即可保证。由于T是{1，2，…，n}上的置换，因此T(a⊕b)中所含“1”的个数与a⊕b所含“1”的个数相同，即N(T(a⊕b)，1)=N(a⊕b，1)，由定理1可得：

故协议1是正确的。

下面证明协议1的安全性。

定理2在半诚实攻击者模型下，协议1能够安全地判断整数点和整数区间的属于关系。

证明 在半诚实模型下，Alice 和Bob 都严格遵循协议步骤，他们可能记录自己在执行协议过程中的中间信息，并尝试去推测对方的秘密输入。下面根据第1.2 节中定义的安全模型，证明协议的安全性。

根据协议1 的描述，有f1(X，Y)=f2(X，Y)=“x∈[y1，y2]”或“x∉[y1，y2]”，即协议执行结束后，Alice和Bob的输出相同。下面只给出f1(X，Y)=f2(X，Y)=“x∈[y1，y2]”时的证明，类似地可给出f1(X，Y)=f2(X，Y)=“x∉[y1，y2]”时的证明。

情形1 构造模拟器S1，使得下式成立：

模拟器S1以(X，f1(X，Y))=(x，“x∈[y1，y2]”)为输入，其中X=x，f1(X，Y)=“x∈[y1，y2]”，执行如下步骤：

1）S1随机选择满足。

2）S1将区间编码成n长的0-1 码：若则，否则。逐比特加密b*后得到n个密文。随后S1输出

其中R1是S1的内部随机带的输出。

此外，由协议描述可知协议执行结束后Alice 的view为。其中(E(b1)，E(b2)，…，E(bn))和“x∈[y1，y2]”分别是Bob 在第1）步和第4）步发送给Alice 的信息，x是Alice 的输入，r1是Alice的内部随机带的输出。

情形2 构造模拟器S2，使得下式成立：

模拟器S2以(Y，f2(X，Y))=([y1，y2]，“x∈[y1，y2]”)为输入，其中Y=[y1，y2]和f2(X，Y)=“x∈[y1，y2]”分别是Bob 的输入和输出，执行如下步骤：

1）S2随机选择x*∈U满足x*∈[y1，y2]。

2）S2将区间[y1，y2]编码成n长的0-1 码b=b1b2…bn：若y1≤xi≤y2则bi=1，否则bi=0。S2逐比特加密b后得到n个密文E(b)=(E(b1)，E(b2)，…，E(bn))。

3）S2将整数x*编码为n长的0-1 码：若xi=x*则，否则。逐比特加密a*后得到n个密文。S2将E(b)与E(a*)的对应项进行模N相乘，根据加密体制的异或同态性，得到n个密文。S2随机选取集合{1，2，…，n}上的一个置换T*，对E(a*⊕b)进行置换后得到：

随后S2输出

其中R2是S2的内部随机带的输出。

此外，由协议描述可知协议执行结束后Bob的view为

其中(E(aT(1)⊕bT(1))，E(aT(2)⊕bT(2))，…，E(aT(n)⊕bT(n))) 是Alice在第2）步发送给Bob的信息，[y1，y2]是Bob的隐私输入，r2是Bob的内部随机带的输出。

下面证明{S2(Y，f2(X，Y))}≡c{viewΠ2 (X，Y)}。首先，r2和R2分别是Bob 和S2的内部随机带的输出，有R2≡c r2。由于(E(a*1)，E(a*2)，…，E(a*n))与(E(a1)，E(a2)，…，E(an))的每个元素都是Goldwasser-Micali概率加密算法加密的结果，且T*和T是集合{1，2，…，n}上的随机置换，从而有：

4 效率分析与比较

本章将本文协议与文献［19］的协议1（简记为Chen 协议［19］）进行比较。首先，从整体上看，Chen 协议可能会导致判断错误，且可能会导致Alice 的隐私泄露，而本文协议克服了这些缺陷（如表1 所示）。其次，在协议复杂度方面，二者的轮复杂度相同，由于Chen 协议［19］对长度为2n的0-1 串进行操作，而本文协议只对长度为n的0-1 串进行处理，故本文协议的计算复杂度和通信复杂度分别降低约一半（如表2 所示，其中n是全集U的势，N是加密运算的模数）。

表1 整体性能对比Tab.1 Overall performance comparison

表2 复杂度对比Tab.2 Complexity comparison

5 结语

安全多方计算是当前密码学界研究的热点问题，隐私保护整数点和整数区间属于关系判断问题是一类具体的安全多方计算问题，隐私保护查询和搜索判断等一些实际问题可抽象为该问题。前人已经对此问题展开过研究，但已有的协议具有或多或少的不足，例如隐私保护的强度不够、协议效率偏低，甚至可能输出不正确结果等。得益于前人的研究基础和研究思路，本文进一步研究隐私保护整数点和整数区间属于关系判断问题，提出了解决该问题的一个协议，并对协议的正确性和半诚实模型下的安全性进行了证明，确保协议不会出现判断错误的情况，且在半诚实攻击者模型下很好地保护了两个参与者的数据隐私。与已有协议相比，本文协议在轮复杂度不变的情况下，计算复杂度和通信复杂度分别降低约一半。作为下一步的研究工作，可以继续探索该问题的更高效的安全方案。