一种基于不经意传输协议的安全多方数据排序方法

1.本发明涉及计算机科学与技术领域，尤其涉及一种基于不经意传输协议的安全多方数据排序方法。


背景技术：

2.随着大数据的快速发展，个人的数据量也不断激增。数以亿万计的数据为基于大数据的商业应用提供了重要的支撑，同时也引发了大量的数据安全问题。为了保护数据的安全和隐私，安全多方计算技术(securemultipartycomputation,smc)得到了广泛的应用。安全多方计算是指分别拥有隐私数据x1,x2,
…
,xn的n个实体共同参与计算函数f(x1,x2,
…
,xn)的输出，计算完成之后，每个参与者除了得到f(x1,x2,
…
,xn)的输出之外，得不到其他任何关于隐私数据x1,x2,
…
,xn的信息。安全多方计算是一种交互式协议，用于计算参与方之间的某些功能。根据参与方的不同，安全多方计算可以分为两方计算和多方计算。比如，隐私集合求交、隐私信息的检索、秘密共享以及安全多方多数据排序。其中，安全多方多数据排序是安全多方计算中的最重要的功能需求之一。对于一个数据序列a，排序是指将a中的所有数据按照从小到大的顺序排成一个序列，进而确定a中所有数据x在整个序列中的位置。公开数据的排序算法目前已经发展得非常成熟了，然而，对私有数据得排序目前仍在发展当中，相关成果和研究较少。
3.1983年，ajtai等人[16]提出了一种渐近运算时间排序网络，称为aks排序网络，它支持多个数据的排序，比较复杂度为o(m
·
logm)，其中，m是输入份额的数目。然而，由于该算法的常数因子很高，因此并不实用。goodrich[17]提出的支持多数据排序的不经意排序，被调用的shell排序.类似于排序网络，数据-不经意排序也被有效地应用于smc协议.虽然随机shell排序返回一个高概率的正确输出，但它需要o(m)轮交互和o(mlogm)比较，这将显著增加通信和计算开销.同时,广告信息可能会在多个交叉口被泄露。在2020年，li等人[18]设计了一种安全的多方多数据排序方案。在它们的协议中，所有的参与者都应该构造一个n
×
m密文矩阵，其中，n是数据域，m是参与者的数目。协议o(n
·
m)的通信开销对参与者来说是相当繁重的。
[0004]
除了理论研究外，相关研究人员还对smc的性能进行了评估。wang等人[1]对一些已有的排序算法的实验结果发表了报告，它们的实现基于fairplaysmc系统[2]。batcher的归并排序[3]和随机希尔排序[4]在256个输入值下的运行时间分别约为3000和6200秒。jonsson等人[5]研究了一种隐藏排序协议输入值数目的通用技术。它们的实现采用了一种称为矢量化的技术进行了优化，并在210秒内实现了向矢量化的batcher归并排序中心16384个秘密共享值。除了效率低下的特点外，上述这些方案存在的另一个问题是安全性较差，即，只有数据拥有者的身份是混淆的，数据本身的隐私并没有得到保护。
[0005]
综合以上分析，设计出高效的、隐私保护的多方多数据排序方案是十分有必要的。


技术实现要素：

[0006]
本发明的目的是要提供一种基于不经意传输协议的安全多方数据排序方法。并基于该算法和改进的k-out-of-n不经意传输协议设计了高效的隐私保护的多方多数据排序方案。
[0007]
为达到上述目的，本发明是按照以下技术方案实施的：
[0008]
本发明包括以下步骤：
[0009]
s1：初始化：各参与方在离线阶段生成系统参数；
[0010]
s2：排序请求生成：各参与方执行隐私保护的多方排序生成排序请求；
[0011]
s3：加密多项式聚合：云服务器收到来自各参与方的排序请求，执行加密多项式的聚合；
[0012]
s4：排序结果恢复：参与方收到来自云服务器的密文，恢复参与方的私有数据集相对应的排序结果。
[0013]
本发明的有益效果是：
[0014]
本发明是一种基于不经意传输协议的安全多方数据排序方法，与现有技术相比，本发明设计了一种基于多项式的编码方法。这种编码算法可以将一个数据集编码成一个多项式，具体来讲，多项式的每个项的指数部分表示数据本身，而该项的系数则表示数据出现的个数。因此，多个数据集可以通过相应的多项式加法实现对不同数据集的排序。
[0015]
根据所设计的基于多项式的编码方法，提出了一种保护隐私的多方多数据排序方案。每个参与者都可以以隐私保护的方式得到其数据的排序后果，即，每个参与方的数据以及对应的排序结果无法被其他实体得到，同时，用户的恶意行为也可以被检测到。
[0016]
各参与方的数据及相应的排序结果不受其他各方的保护。此外，可以检测到任何参与者的恶意行为。该方案实现了有效的通信。以及计算。在沟通方面，每个只发送一个三元组信息给云服务器，它的成本非常小-传输带宽。在计算中方面，每个方面参与者只执行轻量级计算，例如，多项式构造与异或运算。
附图说明
[0017]
图1是本发明的系统模型图；
[0018]
图2是本发明的多项式加密算法；
[0019]
图3是本发明的解密多项式生成算法实例；
[0020]
图4是本发明的实验数据图。
具体实施方式
[0021]
下面结合附图以及具体实施例对本发明作进一步描述，在此发明的示意性实施例以及说明用来解释本发明，但并不作为对本发明的限定。
[0022]
如图1-3所示：本发明基于多项式的编码算法包括四个子算法，分别为1)基本编码算法；2)多项式加密算法；3)排序多项式生成算法和4)解密多项式生成算法。
[0023]
基本编码算法：
[0024]
基本编码算法以一个大小为k的数据集d为输入，输出是一个n阶多项式p。此算法的目的是将数据集d中的k个数据映射到n阶多项式p中。其中，n为数据集d中数据的取值范
围上限。具体算法细节如下所示：
[0025]
输入：一个数据集d，基数r以及数据域[1,n]。
[0026]
输出：一个多项式p(实际上是多项式评估结果)。
[0027]
(1)根据数据集d，按照如下方式生成一个长度为n的比特向量v：
[0028][0029]
其中，i∈[1,n]。
[0030]
(2)以r为多项式的基数、v[i]作为多项式第i阶的项的系数，即多项式中第i阶的项为v[i]
·ri
。最后得到多项式p为其中,v是多项式p的系数向量。
[0031]
需要注意的是，在生成多项式时，最直接的方法时先计算每个项，然后再对所有项求和。但是，这种直接的方法往往效率非常低。因此，此算法根据霍纳规则
[1]
来加速多项式生成过程，以提升算法的计算效率。霍纳规则是目前计算多项式值得最高效得算法。根据霍纳规则，一个单变量的n阶多项式的计算转化为n个线性表达式的和。具体过程如下所示：
[0032]
多项式f(x)＝anxn+a
n-1
x
n-1
+...+a1x+a0[0033]
可以转化为：f(x)＝(((
…
(anx+a
n-1
)x+
…
+a3)x+a2)x+a1)x+a0.
[0034]
因此，多项式f(x)在x0处的评估值f(x0)可以通过以下序列得到：
[0035]
r1＝anx0+a
n-1.
[0036]
r2＝r1x0+a
n-2
.
[0037]
……
[0038]rn
＝r
n-1
x0+a0.
[0039]rn
即为f(x0)的值。
[0040]
以上过程可以大大降低多项式评估值的计算开销。
[0041]
多项式加密算法：
[0042]
多项式可以表示为一个三元组(r，n，v)，r是多项式基数，n是多项式的阶数，v是系数向量。对于一个多项式，r和n通常是公开的参数，因此，可以通过对多项式p系数向量进行加密来实现对多项式的加密。
[0043]
输入：多项式p。
[0044]
输出：伪随机函数f的输出值fk(r)和多项式p的密文ep＝{r,n,ev}。
[0045]
(1)将多项式p表示为{r,n,v}，即p＝v[1]
·
r1+v[2]
·
r2+v[3]r3+...+v[n]
·rn
。
[0046]
(2)选择为随机函数f，生成随机值k∈{0，1}n，以k,v和一个随机值r∈{0，1}n为f的输入，f输出伪随机比特向量bv＝fk(r)。然后，通过bv对多项式p的系数向量进行加密，得到加密系数向量ev，即
[0047]
(3)根据上述得到的加密系数向量ev来生成多项式p的密文ep＝ev[1]
·
r1+ev[2]
·
r2+
…
+ev[n]
·rn
。
[0048]
注意，上述的多项式加密方案基于文献[2]中的构造方案3.28，相关证明表明该方案能够达到cpa-secure的安全级别。
[0049]
排序多项式生成算法：
[0050]
当把数据集d编码到多项式排序多项式生成算法可以根据p进一步生成相对应的排序多项式sp。在排序多项式中，第i阶的项ri的系数即为数据i的排序结果。同时需要注意的是，以多项式p的密文ep为输入，排序多项式算法可以根据ep进一步生成加密的排序多项式esp。排序多项式生成算法具体过程如下：
[0051]
输入：一个多项式p＝v[1]
·
r1+v[2]
·
r2+v[3]r3+
…
+v[n]
·rn
或加密多项式ep。
[0052]
输出：排序多项式sp或加密的排序多项式esp。
[0053]
(1)基于{r，n，v}，可以根据以下算法生成排序多项式sp的系数向量sr：
[0054][0055]
(2)按照如下算法生成多项式p对应的排序多项式sp：
[0056][0057]
类似地，根据{r，n，v}和加密多项式ep，可按照以下算法生成相应的加密排序多项式esp：
[0058][0059]
解密多项式生成算法：
[0060]
以加密多项式ep为输入，上述的排序多项式生成算法将会输出加密的排序多项式esp。然而，为了对加密的排序多项式esp进行解密，解密多项式生成算法根据多项式p的系数向量v和加密多项式的系数向量ev生成解密多项式dp。具体过程如下所示：
[0061]
输入：多项式p的系数向量v和加密多项式的系数向量ev。
[0062]
输出：解密多项式dp。
[0063]
(1)根据v和ev，一个n
×
n的矩阵m可按照以下算法生成：
[0064][0065]
(2)根据以下算法生成排序多项式的dp的系数向量dv：
[0066][0067]
(3)根据dv，解密多项式同时，dp还可以表示为{r,n,dv}。
[0068]
方发明具体执行过程如下：
[0069]
(1)初始化阶段：为了建立整个系统，各参与方在离线阶段按照以下步骤生成系统参数：
[0070]
step1：云服务器s选择一个安全参数λ，并根据λ生成双线性映射e：g
×g→gt
，g中的两个生成元g和h。之后，s随机选择作为系统密钥，并计算
[0071]
同时，选择一个hash函数h：g
t
→
{0，1}1，生成she同态加密算法的私钥sks＝{p，l}。选择r＞m。
[0072]
step2：参与者u1，u2，
…
，um分别随机选择γ[i]构造之后，所有参与者合作生成γ的秘密共享，参与者ui获得γ的秘密份额ri，满足
[0073]
step3：云服务器s发布公共系统参数sp＝{e,g,h,g1，g2，...，gn,h1,h2,
…
，hn,h,r}；
[0074]
(2)排序请求生成：m个参与方ui想要执行隐私保护的多方排序，通过以下算法生成排序请求：
[0075]
step1：ui以自己的私有数据集di＝{d
i1
,d
i2
,
…
，d
ik
}作为选择集。基于di,系统参数sp，ui选择随机数计算：
[0076][0077][0078]
step2：以di，r，n为输入，参与者ui调用基本编码算法生成多项式pi。然后，以pi为输入，ui调用多项式加密算法生成加密多项式epi＝{r,n,bvi}。
[0079]
step3：根据多项式pi的系数向量vi和加密多项式epi的系数向量evi，ui调用解密多项式生成算法得到一个解密多项式dpi。之后，通过she同态加密算法，ui加密dpi得到密文e(dpi)，为了保护隐私，ui利用she同态特性加上混淆ri，得到e(dp
*i
)＝e(dpi+ri)。
[0080]
step4：ui将生成的排序请求发送至云服务器s。
[0081]
(3)加密多项式聚合：当收到来自m个参与者的排序请求t＝{t1，t2，...，tm}，其中，云服务器s执行以下步骤进行加密多项式的聚合：
[0082]
step1：基于t，系统参数sp，s执行不经意传输协议(ot)的验证算法检查是否成立，若成立，则验证通过；否则，验证失败，协议终止。
[0083]
step2：s聚合加密多项式epi和she密文e(dp
*i
)，即和之后，以ep作为输入，云服务器s调用排序多项式生成算法生成相应的排序多项式esp。
[0084]
step3：云服务器s使用she的私钥sks＝{p，l}解密e(dp
*
)，即e(dp+γ)，得到解密多项式dp
*
＝dp+γ。之后，s解构dp
*
为{r,n,dv}：
[0085]
dp
*
＝dv
*
[1]
·
r1+dv
*
[2]
·
r2+...+dv
*
[n]
·rn
[0086]
step4：云服务器s选择随机数并按如下算法计算密文c
0i
：
[0087][0088]
step5:云服务器s分别发送ci＝{c
i0
，c
ij
es
p
}给ui。
[0089]
(4)排序结果恢复：当收到来自云服务器s的ci＝{c
i0
，c
ij
，es
p
}ui恢复数据即di相对应的排序结果sri。具体过程如下所示：
[0090]
step1:ui重构esp＝sr*[1]
·
r1+sr*[2]
·
r2+...+sr*[n]
·rn
。
[0091]
step2:根据密文c
i0
,c
ij
，选择集di，密钥si和sp，ui根据以下过程计算混淆的解密向量dv*：
[0092][0093]
step3：最终，ui重构出排序结果sri通过以下过程：
[0094]
sr
ij
＝sr[d
ij
]＝sr
*
[d
ij
]+dv*[d
ij
]-γ[d
ij
]，
[0095]
where 1≤i≤m and 1≤j≤k.
[0096]
基于所提出的基于多项式的编码方法，本发明提出了一种高效的隐私保护多方多数据排序方方法，该方方法允许多方以隐私保护的方式对他们拥有的多个数据进行排序。安全分析证明此方案是隐私保护的，即数据集和相应的排序结果不能被除数据集所有者之外的任何一方透露。此外，还进行了广泛的实验来评估和比较此方案和其他相关工作的性能。结果表明，本文提出的高效的隐私保护多方多数据排序方案确实具有高效的通信和计算性能。本发明的实验表现如图4所示，其中包含了方案的通信和计算开销。
[0097]
本发明的技术方案不限于上述具体实施例的限制，凡是根据本发明的技术方案做出的技术变形，均落入本发明的保护范围之内。
[0098]
参考文献：
[0099]
[1]wang g，luo t，goodrich m t，et a1.bureaucratic protocols for secure two-party sorting，selection，and permuting[c]//proceedings of the 5th acm symposium on information，computer and communications security.2010：226-237.
[0100]
[2]malkhi d，nisan n，pinkas b，et al.fairplay-secure two-party computation system[c]//usenix security symposium.2004，4：9.
[0101]
[3]batcher k e.sorting networks and their applications[c]//proceedings of the april 30
‑‑
may 2，1968，springjoint computer conference.1968：307-314.
[0102]
[4]batcher k e.sorting networks and their applications[c]//proceedings of the april 30
‑‑
may 2，1968，springjoint computer conference.1968：307-314.
[0103]
[5]k v，kreitz g，uddin m.secure multi-party sorting and applications[j].cryptologyeprint archive，2011。

技术特征：
1.一种基于不经意传输协议的安全多方数据排序方法，其特征在于，包括以下步骤：s1：初始化：各参与方在离线阶段生成系统参数；s2：排序请求生成：各参与方执行隐私保护的多方排序生成排序请求；s3：加密多项式聚合：云服务器收到来自各参与方的排序请求，执行加密多项式的聚合；s4：排序结果恢复：参与方收到来自云服务器的密文，恢复参与方的私有数据集相对应的排序结果。2.根据权利要求1所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述步骤s1具体包括以下步骤：s1.1:云服务器s选择一个安全参数λ，并根据λ生成双线性映射e:g
×
g
→
g
t
，g中的两个生成元g和h；之后，s随机选择作为系统密钥并计算同时，选择一个hash函数h:g
t
→
{0,1}
l
，生成she同态加密算法的私钥sk
s
＝{p,l}；选择r>m；s1.2:参与方u1，u2，
…
，u
m
分别随机选择γ[i]构造之后，所有参与方合作生成γ的秘密共享，参与方u
i
获得γ的秘密份额r
i
，满足m表示参与方个数，u
i
表示第i个参与方；s1.3:云服务器s发布公共系统参数sp＝{e,g,h,g1,g2,
…
,g
n
,h1,h2,
…
,h
n
,h,r}。3.根据权利要求2所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述步骤s2具体包括以下步骤：s2.1：u
i
以自己的私有数据集d
i
＝{d
i1
,d
i2
,
…
,d
ik
}作为选择集；基于d
i
,系统参数sp，u
i
选择随机数计算：计算：s2.2：以d
i
正整数r，n为输入，参与者u
i
调用基本编码算法生成多项式pi；然后，以pi为输入，u
i
调用多项式加密算法生成加密多项式ep
i
＝{r,n,bv
i
}；s2.3：根据多项式p
i
的系数向量v
i
和加密多项式ep
i
的系数向量ev
i
，u
i
调用解密多项式生成算法得到一个解密多项式dp
i
；之后，通过she同态加密算法，u
i
加密dp
i
得到密文e(dp
i
)，为了保护隐私，u
i
利用she同态特性加上混淆ri，得到e(dp
*i
)＝e(dp
i
+r
i
)。s2.4：u
i
将生成的排序请求发送至云服务器s。4.根据权利要求3所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述步骤s3具体包括以下步骤：当收到来自m个参与者的排序请求t＝{t1,t2,
…
,t
m
},其中，},其中，云服务器s执行以下步骤进行加密多项式的聚合：s3.1：基于t,系统参数sp,s执行不经意传输协议(ot)的验证算法检查
是否成立，若成立，则验证通过；否则，验证失败，协议终止；s3.2：s聚合加密多项式epi和she密文e(dp
*i
)，即和之后，以ep作为输入，云服务器s调用排序多项式生成算法生成相应的排序多项式esp；s3.3：云服务器s使用she的私钥sk
s
＝{p,l}解密e(dp
*
),即e(dp+γ),得到解密多项式dp
*
＝dp+γ；之后，s解构dp
*
为{r,n,dv}：dp
*
＝dv
*
[1]
·
r1+dv
*
[2]
·
r2+
…
+dv
*
[n]
·
r
n
s3.4：云服务器s选择随机数并按如下算法计算密文c
0i
：s3.5：云服务器s分别发送c
i
＝{c
i0
，c
ij
，es
p
}给u
i
。5.根据权利要求4所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述步骤s4具体包括以下步骤：当收到来自云服务器s的c
i
＝{c
i0
，c
ij
，es
p
},u
i
恢复数据即d
i
相对应的排序结果sr
i
；d
i
是参与方ui的私有数据集，具体过程如下：s4.1：u
i
重构esp＝sr*[1]
·
r1+sr*[2]
·
r2+...+sr*[n]
·
r
n
；s4.2：根据密文c
i0
,c
ij
，选择集d
i
，密钥s
i
和sp，u
i
根据以下过程计算混淆的解密向量dv*：where d
it
∈d
i
，1≤t≤k.s4.3：最终，u
i
重构出排序结果sr
i
通过以下过程：sr
ij
＝sr[d
ij
]＝sr*[d
ij
]+dv
*
[d
ij
]-γ[d
ij
]，where 1≤i≤m and 1≤j≤k。6.根据权利要求3所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述基本编码算法为：以一个大小为k的数据集d为输入，输出是一个n阶多项式p，目的是将数据集d中的k个数据映射到n阶多项式p中，其中，n为数据集d中数据的取值范围上限；具体算法细节如下：输入：一个数据集d，基数r以及数据域[1,n]；输出：一个多项式p；根据数据集d，按照如下方式生成一个长度为n的比特向量v：
其中，i∈[1,n]。以r为多项式的基数、v[i]作为多项式第i阶的项的系数，即多项式中第i阶的项为v[i]
·
r
i
。最后得到多项式p为其中,v是多项式p的系数向量；一个单变量的n阶多项式的计算转化为n个线性表达式的和；具体过程如下：多项式f(x)＝a
n
x
n
+a
n-1
x
n-1
+
…
+a1x+a0可以转化为：f(x)＝(((
…
(a
n
x+a
n-1
)x+
…
+a3)x+a2)x+a1)x+a0.因此，多项式f(x)在x0处的评估值f(x0)可以通过以下序列得到：r1＝a
n
x0+a
n-1
.r2＝r1x0+a
n-2
.
……
r
n
＝r
n-1
x0+a0.r
n
即为f(x0)的值。7.根据权利要求3所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述多项式加密算法为：多项式表示为一个三元组(r,n,v),r是多项式基数,n是多项式的阶数，v是系数向量，对于一个多项式，r和n通常是公开的参数，因此，通过对多项式p系数向量进行加密来实现对多项式的加密；输入：多项式p。输出：伪随机函数f的输出值f
k
(r)和多项式p的密文ep＝{r,n,ev}；将多项式p表示为{r,n,v},即dp＝v[1]
·
r1+v[2]
·
r2+v[3]r3+
…
+v[n]
·
r
n
选择为随机函数f，生成随机值k∈{0,1}
n
,以k,v和一个随机值r∈{0,1}
n
为f的输入，f输出伪随机比特向量bv＝f
k
(r)，然后，通过bv对多项式p的系数向量进行加密，得到加密系数向量ev，即根据上述得到的加密系数向量ev生成多项式p的密文ep＝ev[1]
·
r1+ev[2]
·
r2+
…
+ev[n]
·
r
n
。8.根据权利要求3所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述解密多项式生成算法为：以加密多项式ep为输入，排序多项式生成算法将会输出加密的排序多项式esp；为了对加密的排序多项式esp进行解密，解密多项式生成算法根据多项式p的系数向量v和加密多项式的系数向量ev生成解密多项式dp，具体过程如下：输入：多项式p的系数向量v和加密多项式的系数向量ev；输出：解密多项式dp；根据v和ev，一个n
×
n的矩阵m可按照以下算法生成：根据以下算法生成排序多项式的dp的系数向量dv：
根据dv，解密多项式同时，dp还可以表示为{r,n,dv}。9.根据权利要求8所述的基于不经意传输协议的安全多方数据排序方法，其特征在于：所述排序多项式生成算法为：当把数据集d编码到多项式排序多项式生成算法根据p进一步生成相对应的排序多项式sp，在排序多项式中，第i阶的项r
i
的系数即为数据i的排序结果，同时，以多项式p的密文ep为输入，排序多项式算法可以根据ep进一步生成加密的排序多项式esp，排序多项式生成算法具体过程如下：输入：一个多项式p＝v[1]
·
r1+v[2]
·
r2+v[3]r3+
…
+v[n]
·
r
n
或加密多项式ep；输出：排序多项式sp或加密的排序多项式esp；基于{r,n,v},可以根据以下算法生成排序多项式sp的系数向量sr:按照如下算法生成多项式p对应的排序多项式sp：根据{r,n,v}和加密多项式ep,可按照以下算法生成相应的加密排序多项式esp：

技术总结
本发明公开了一种基于不经意传输协议的安全多方数据排序方法，首先，各参与方在离线阶段生成系统参数；其次，各参与方执行隐私保护的多方排序生成排序请求；而后，云服务器收到来自各参与方的排序请求，执行加密多项式的聚合；最后，参与方收到来自云服务器的密文，恢复参与方的私有数据集相对应的排序结果。本发明编码算法可以将一个数据集编码成一个多项式，实现对不同数据集的排序。根据编码方法提出了保护隐私的多方多数据排序方案。每个参与者都可以以隐私保护的方式得到其数据的排序后果，各参与方的数据及相应的排序结果不受其他各方的保护，实现了有效的通信以及计算。实现了有效的通信以及计算。实现了有效的通信以及计算。


技术研发人员：李雄 商帅 王保锦 易珂来 汪小芬 杨浩淼 张小松
受保护的技术使用者：电子科技大学
技术研发日：2023.03.22
技术公布日：2023/7/25