基于同态加密机制的隐私可保护信息安全计算实现方法

摘要

一种基于同态加密机制的隐私可保护信息安全计算实现方法，通过所涉及的安全计算协议，可有效的保护用户隐私信息。该机制可以保证在引入较低计算开销和通信开销的前提下，实现较高的频谱利用率。本发明基于BCP同态加密技术，实现直接对密文的操作，并在分配机制中引入第三方实体来协同频谱分配者共同完成频谱重分配任务。在该方案中，用户提交的所有信息均为密文，频谱分配者与第三方实体按照本发明安全协议对密文进行计算，选出获胜者并计算出获胜者所需付出的代价。本方案在确保频谱重分配真实可信的同时，实现了对用户隐私信息的有效保护。

说明书

技术领域

本发明涉及的是一种信息安全领域的安全计算技术，具体是一种基于同态加密机制的隐私可保护频谱资源安全分配方法。

背景技术

随着无线网络技术的高速发展，无线设备及相关服务对频谱资源的需求越来越大，导致频谱成为一种稀缺资源。另外，由于政府机构所采用的静态、长期的频谱分配策略，使得频谱利用率十分低下。例如，美国联邦通信委员会和中国无线电管理局都把信道资源分成多个波段并将其授权给某一个地域、特定组织或者无线应用来使用。博弈理论被广泛认为是解决动态频谱资源按需分配的有效手段之一，目前，已出现多种频谱分配机制用于确保频谱资源重新进行真实高效的分配。为了实现最优化分配，需要收集各个用户所需的频谱信息以及其真实价值。然而，不同用户对不同频谱的需求以及真实价值是用户的隐私信息。当直接将其透露给频谱分配者无疑会泄露用户的隐私信息，从而损害其利益。该问题主要面临三个难点：一是频谱的空间重用性特征使得现有的隐私保护分配机制不适用于频谱分配；二是不同用户对不同频谱的需求及价值都是用户的隐私信息，不能泄露给频谱分配者；三是用户的计算和通信能力有限，无法直接采用现有的可信多方计算方法。

基于以上的观察，本发明结合同态加密技术提出了一个隐私可保护的频谱资源安全分配机制，该机制可以有效的保护用户的隐私信息，包括用户对不同频谱的需求以及频谱的真实价值；同时，该机制可以保证在引入较低的计算开销和通信开销的前提下，实现较高的频谱利用率。本发明隐私可保护频谱动态重分配机制基于BCP同态加密方案，可实现直接对密文的操作，并在分配机制中引入了第三方实体(第二实体)来协同频谱分配者(第一实体)共同完成频谱重分配任务。在该方案中，用户提交的所有信息都是经过加密后的密文，第一实体和第二实体按照本发明安全协议对密文进行计算，从而选出获胜者并计算出其所需付出的代价。该方案在确保频谱重分配真实可信的同时，实现了对用户所需频谱以及频谱价值等隐私信息的有效保护。

发明内容

本发明针对现有技术存在的上述不足，提出一种基于同态加密机制的隐私可保护信息安全计算实现方法，可有效的保护用户隐私信息，包括用户对不同频谱的需求以及对频谱的真实估价；该机制可以保证在引入较低计算开销和通信开销的前提下，实现较高的频谱利用率。本发明基于BCP同态加密技术，实现直接对密文的操作，在分配机制中引入两个实体(即第一实 体、第二实体)共同完成频谱重分配任务。在该方案中，用户提交的所有信息均为密文，第一实体和第二实体按照本发明安全协议对密文进行计算，选出获胜者并计算出获胜者所需付出的代价。本方案在确保频谱重分配真实可信的同时，实现了对用户隐私信息的有效保护。

本发明通过以下技术方案实现：

本发明包括以下步骤：

第一步，系统初始化，建立加密系统并分发初始公钥，具体步骤为：

1.1由第二实体初始化BCP加密系统产生公共参数及主密钥，并根据公共参数生产自己的公钥私钥对，将公共参数和公钥分发给第一实体以及所有用户；

1.2第一实体收到第二实体发送的公共参数，根据公共参数生成自己的公钥私钥对，并将公钥发送给所有用户；

1.3用户收到第一实体及第二实体的公钥，进行乘法运算，得到两个公钥之乘积Prod.pk，作为自己的公钥。

第二步，数据加密提交：用户利用第一步中计算得到的乘积密钥Prod.pk对自己所提交的信息进行加密，并将加密信息提交给第一实体。

第三步，频谱分配，安全计算协议选出获胜者，具体步骤为：

3.1根据用户出价信息与所申请频谱的个数之比，对所有用户进行降序排序。由于所有信息都是加密后的密文，所以该排序工作需要第一实体和第二实体根据本发明安全排序协议进行协同运算完成。

所述的协同运算具体包括：

3.1.1第一实体选取一个随机数，用Prod.pk对这个随机数进行加密，然后与每一个用户加密后的信息相乘，得到n个更新后的数据值(n表示用户的数目)；

3.1.2第一实体选取另外n个随机数，并对每个随机数进行加密，然后将该n个随机数的密文与前一步产生的n个更新后的数据值密文混合，将这2n个密文同时发送给第二实体；

3.1.3第二实体收到该2n个密文之后，首先用自己的主密钥MK进行解密，得到该2n个密文相对应的明文，然后按照降序进行排列，得到2n个数据的降序序列，并将其序列号发送给第一实体；

3.1.4第一实体收到该降序序列后，将其中n个添加的随机数移除，得到只有n个数据值的降序序列，至此完成了协同运算。第一实体得到了n个用户按照其申请信息的降序序列，同时，并没有将真实的隐私数据值泄露给第一实体和第二实体。

3.2根据降序排列结果，按照贪心算法对用户进行逐一筛选，直到所有频谱资源分配完毕，选择出获胜者。

这里的筛选过程需要考虑频谱资源的空间可重用性，即同一个频谱资源可被两个或多个地域的用户公用(只要距离足够远不产生冲突即可)。具体为：根据安全排序协议的排序结果，针对该降序序列中的每个用户，逐个检查其所申请的频谱是否已经被分配出去，当没有被分配出去，则该用户是获胜者，并将其加入获胜者集合；当该用户申请的频谱已经被分配出去，则需要检查现有的获胜者集合，查看是否在空间上冲突，当其余所有获胜者均不冲突，该用户也是获胜者，将其加入获胜者集合。

3.3构建密文加法及乘法协议。由于所提交隐私信息都是以密文形式存在，所以该筛选工作也需要第一实体和第二实体根据本发明安全筛选协议进行协同运行完成，为构建安全筛选协议，首先需要构建密文的加法和乘法协议，该协议实现两个密文的加法和乘法操作。由于本发明采用的BCP加密技术本身具有同态加的特性，即其满足方程：

$\left(\begin{array}{c}\mathrm{Add}\left(\mathrm{Enc}\right(m_1),\mathrm{Enc}\left(m_2\right))\\ =\mathrm{Enc}\left(m_1\right)\mathrm{Enc}\left(m_2\right)\\ =(A_1,B_1)(A_2,B_2)\\ =(A_1{A}_2\mathrm{mod}{N}^2,B_1{B}_2\mathrm{mod}{N}^2)\\ =(g^{r_1+r_2}\mathrm{mod}{N}^2,h^{r_1+r_2}(1+(m_1+m_2)N\left)\mathrm{mod}{N}^2\right)\\ =\mathrm{Enc}(m_1+m_2)\end{array}\right)$

其中：Enc()是加密函数，Enc(m₁),Enc(m₂)表示m₁,m₂的密文，由下列加密公式计算而来Enc(m)＝(A,B)＝(g^rmodN²,h^r(1+mN)modN²)，即密文的加法Add协议满足Enc(m₁+m₂)＝Add(Enc(m₁),Enc(m₂))。

这里只需要构建密文乘法协议即可，其具体步骤包括：

3.3.1给定两个密文$\mathrm{Enc}\left(m_1\right)=(A_1,B_1)=(g^{r_1}\mathrm{mod}{N}^2,h^{r_1}(1+m_{1}N)\mathrm{mod}{N}^2)$和Enc(m₂)＝(A₂,B₂)＝(g^r2modN²,h^r2(1+m₂N)modN²)，其中公钥pk＝h。第一实体首先利用密文同态加Add将这两个密文加噪音：

(A₁',B₁')＝Add(Enc(m₁,Enc(-τ₁))),(A₂',B₂')＝Add(Enc(m₂,Enc(-τ₂)))然后将加噪音后的密文发送给第二实体。

3.3.2第二实体收到加噪音后的密文之后，利用主密钥MK进行解密：

m₁'＝mDec((A₁',B₁')),m₂'＝mDec((A₂',B₂')),其中：m₁'＝m₁-τ₁,m₂'＝m₂-τ₂，mDec()是解密函数。第二实体直接将m₁',m₂'相乘，并用随机数r进行加密，得到(Z₁,Z₂)＝Enc(m₁',m₂')＝(g^rmodN²,h^r(1+m₁'m₂'N)modN²)，并将结果发送给第一实体。

3.3.3第一实体收到(Z₁,Z₂)后，首先计算出(T₁,T₂)＝Enc(-τ₁,-τ₂)，然后通过公式

可以计算出需要的结果，即就是m1m2在某一随机数下的加密形式。也就是说，密文的乘法协议满足

Enc(m₁×m₂)＝Mult(Enc(m₁),Enc(m₂))。

证明过程如下：

$\left(\begin{array}{c}\bar{A}=Z_1{A}_1^{{\tau }_2}{A}_2^{{\tau }_1}{T}_1\mathrm{mod}{N}^2\\ =\left(g^r\right)\left(g^{r_1+r_2}\right)\left(g^{r_2{r}_1}\right)\left(g^{r\prime }\right)\mathrm{mod}{N}^2\\ =g^{r+r_1{r}_2+r_2{r}_1+r^{\prime }}\mathrm{mod}{N}^2\end{array}\right),$

$\left(\begin{array}{c}\bar{B}=Z_2{A}_2^{{\tau }_1}{A}_1^{{\tau }_2}{T}_2\mathrm{mod}{N}^2\\ =\left[h^r(1+m_1^{\prime }{m}_2^{\prime }N)\right]\left[h^{r_1{r}_2}(1+m_{1}N)\right]\left[h^{r_2{r}_1}(1+m_{2}N)\right]\left[h^{r^{\prime }}(1-{\tau }_1{\tau }_{2}N)\right]\mathrm{mod}{N}^2\\ =h^{r+r_1{r}_2+r_2{r}_1+r^{\prime }}\left[(1+m_1^{\prime }{m}_2^{\prime }N)(1+m_{1}N)(1+m_{2}N)(1-{\tau }_1{\tau }_{2}N)\right]\mathrm{mod}{N}^2\\ =h^{r+r_1{r}_2+r_2{r}_1+r^{\prime }}(m_1^{\prime }{m}_2^{\prime }+{\tau }_2{m}_1+{\tau }_1{m}_2-{\tau }_1{\tau }_2)\mathrm{mod}{N}^2\\ =h^{r+r_1{r}_2+r_2{r}_1+r^{\prime }}\left(m_1{m}_2\right)\mathrm{mod}{N}^2\end{array}\right)$

所以，就是m₁×m₂在随机数r+r₁r₂+r₂r₁+r'下的加密形式，证毕。

至此，已经成功构建了密文的乘法协议，其满足：Enc(m₁m₂)＝Mult(Enc(m₁),Enc(m₂))。

接下来，就可以通过密文的加法协议和乘法协议来构建安全筛选协议。

第四步，安全计算获胜者所需要付出的代价，具体步骤为：

4.1针对每一个获胜者，需要计算出其应该付出的相对应于其所申请频谱的代价，理论上，该代价不会大于其提交的数值大小。

4.2为计算每个获胜者所需付出的代价，为此，首先需要找到该用户的关键邻居节点。某个获胜者的关键邻居节点是指排在该获胜者后面的某个用户，当该获胜者没有获胜，则该邻居节点会成为获胜者。寻找获胜者的关键邻居节点的具体操操作为：首先将该获胜者从降序序列中移除，然后利用步骤三中的获胜者选择方法，找到的第一个位于该获胜者之后的获胜者(实为非获胜者)即为关键邻居节点。

4.3找到每个获胜者的关键邻居节点，利用该关键邻居节点所申请的频谱数目信息(密文形式)结合该获胜者自己所提交的密文信息，可计算出获胜者所需付出的代价。由于所提交隐私信息都是以密文形式存在，而且关键邻居节点是非获胜者，其信息内容为隐私信息，所以该计算工作也需要第一实体和第二实体根据本发明所提出的代价安全计算协议进行协同运算完成。

所述的代价安全计算协议，同样由密文加法协议和密文乘法协议来构建。

技术效果

与现有技术相比，本发明能够有效的保护参与动态频谱资源分配的用户对无线频谱资源的需求隐私以及频谱资源的价值隐私，防范来自第一实体、第二实体以及其他用户的隐私窃取攻击；同时在引入较低通信开销和计算开销的前提下，实现频谱资源的高效利用。

附图说明

图1为本发明整体框架示意图。

图2为本发明中密钥系统初始化流程图。

图3为本发明中同态加密机制的工作流程图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例1

如图1所示，本发明在传统频谱分配机制中引入了第二实体，协同第一实体共同完成频谱重分配任务。在该方案中，用户提交的所有信息都是经过加密后的密文(如图1步骤(1))，第一实体和第二实体按照本发明安全协议对密文进行安全计算，从而选出获胜者并计算出获胜者所需付出的代价(如图1步骤(2)(3))，最后向所有用户公布此次运算结果(如图1步骤(4))。该方案基于BCP同态加密技术，在确保频谱重分配真实可信的同时，实现了对用户所需频谱以及频谱价值等隐私信息的有效保护。

如图3所示，本实施例包括以下步骤：

第一步，系统初始化。

1.1第二实体初始化BCP加密系统：选取大素数N＝pq，其中p＝2p'+1,q＝2q'+1，另外选取随机数使得对所有的k∈[1,N-1]，公式g^p'^q'modN²＝1+kN均成立，这里PP＝(N,k,g)称为公共参数，及MK＝(p',q')称为主密钥。随后根据公共参数PP生产自己的公钥私钥对其中${\mathrm{pk}}_{A_i}=h=g^a\mathrm{mod}{N}^2,{\mathrm{sk}}_{A_i}=a.$然后，将公共参数PP和公钥分发给第一实体以及所有用户；

1.2第一实体收到第二实体发送的公共参数PP＝(N,k,g)，根据公共参数生成自己的公钥私钥对并将公钥发送给所有用户；

1.3用户收到第一实体及第二实体的公钥，进行乘法运算，得到两个公钥之乘积Prod.pk， 作为自己的公钥，即$\mathrm{Prod}.\mathrm{pk}={\mathrm{pk}}_{A_u}\times {\mathrm{pk}}_{A_i}.$

第二步，用户信息加密提交。

2.1用户利用第一步中计算得到的乘积密钥Prod.pk对自己所提交信息进行加密。考虑n个用户B＝{1,2,...,n}，m个待分配频谱C＝{c₁,c₂,...,c_m}，用户i所申请的频谱集合为S_i，对S_i的真实代价为b_i。

2.2每个用户首先本地计算利用乘积公钥Prod.pk对b_i'进行加密，表示为Enc(b_i')。同时将集合S_i表示成m比特长度的01序列，序列中第k位为1表示该用户申请了第k个频谱，否则表示没有申请该频谱，并对序列S_i按位加密，表示为Enc(S_i)。然后所有用户将加密后的信息Enc(b_i')和Enc(S_i)提交给第一实体。

第三步，安全排序协议。

3.1第一实体接收到所有用户所提交的隐私密文信息，首先将所有用户提交的信息的密文Enc(b')利用同态加法协议进行加噪音处理：

$\overline{\mathrm{Enc}\left(b_i^{\prime }\right)}=\mathrm{Add}(\mathrm{Enc}\left(b_i^{\prime }\right),\mathrm{Enc}\left(\eta \right)),\forall i\in B,$其中：η∈Z_N为一随机数。同时，另取n个随机数，将其用Prod.pk进行加密，密文与加噪音后的密文进行混合，混合后产生2n个密文，每个密文均有一个伪ID。将该2n个密文连同其伪ID同时发送给第二实体Auction>

3.2第二实体接收到该2n个密文之后，利用其主密钥PK将其全部解密，

$\overline{b_i^{\prime }}=\mathrm{mDec}\left(\overline{\mathrm{Enc}\left(b_i^{\prime }\right)}\mathrm{orEnc}\left({\tau }_i\right)\right),\forall i\in \mathrm{1,2},...,2n$

解密得到2n个相应的明文，然后按照降序对其进行排列，得到2n个明文的降序序列β'，并把该序列对应的伪ID发送给第一实体；

3.3第一实体收到该降序序列β'后，按照伪ID，将其中n个添加的随机数移除，得到只有原来n个数据值所对应的伪ID的降序序列β。至此，安全排序完成，第一实体得到了n个用户按照b_i'的降序序列，同时，由于b_i'始终是以密文的形式Enc(b_i')存在，故并没有将真实的隐私信息泄露给第一实体和第二实体。

第四步，安全计算协议筛选获胜者。

4.1由第二步可知，每个用户对频谱资源的需求可用m比特的布尔向量表示，记为S_i＝(S_i¹,S_i²,...,S_i^m)，其中S_i^k＝1表示用户i申请了第k个频谱，反之亦然。用户提交给第一实 体的频谱需求信息室对S_i按位加密后的结果，记Enc(S_i)＝(Enc(S_i¹),Enc(S_i²),...,Enc(S_i^m))。

4.2相似的，第一实体也用一个m比特的布尔向量来表示当前频谱资源的分配情况，记为其中表示第k个频谱已经被分配出去了，反之亦然。其按位加密形式记为

4.3第一实体和第二实体就可以根据第三步所得到的降序序列β，利用贪心算法，协同执行密文加密协议Add和密文乘法协议完成筛选获胜者的工作，同时保证用户提交的因素信息不外泄。下面来描述如何判断用户i∈β是否是获胜者。首先，执行如下运算来判断i所申请的频谱是否已经被分配：其中：乘积符号表示m个密文的乘积，是密文同态加法协议的另一种表示形式，其效果完全一样。

4.4第一实体Auctioneer将上述运算的结果发送给第二实体Auction Issuer解密，当解密结果为0，表示i所申请的频谱资源并没有被分配出去，所以用户i是获胜者，然后执行下列操作将用户i加入获胜者集合并更新当前频谱分配状态：

其中：公式表示两个密文向量相应位的同态加操作；当解密结果不是0，则表示至少有一个用户i所申请的频谱已经被分配给了其他用户(获胜者)，但是，这种情况下不能直接认定用户i已经是非获胜者，因为频谱有空间重用性(只要两个用户距离足够远，他们就可以同时使用同一个频谱)。

4.5这种情况下，第一实体需要结合各个用户相对于各个频谱的冲突关系，即冲突图，来判断i是否是获胜者。方法为：逐个检查已有获胜者，当i与所有获胜者在所申请的频谱上都不存在冲突关系，则用户i仍是获胜者，否则，i与某个获胜在在所申请的频谱上有冲突关系，则i为非获胜者。

第五步，安全计算获胜者最终应付代价。

5.1如前所述的，第一实体通过某个获胜者的关键邻居节点所提交的申请信息来确定该获胜者所应付出的具体代价数额，记为其中b'_π(i)表示获胜者i的关键邻居节点所提交的隐私信息。该安全计算协议，目的是在不泄露非获胜者隐私信息的前提下，找出获胜者的关键邻居节点，并计算出获胜者应付的代价，同时关键邻居节点的隐私信息b'_π(i)也不能泄露。

5.2为了找出获胜者i的关键邻居节点π(i)，第一实体首先将获胜者i从降序序列β中移除，并更新已分配频谱状态：其中：Enc(-S_i^k)＝Add(Enc(S_i^k),Enc(-1))。然后，对每一个用户j∈β{i}，第一实体将j所申请的频谱加入到已更新的频谱分配状态中：

第一实体运行第四步中的安全获胜者筛选协议，可以确定j是否是获胜者。当j是获胜者，则意味着j是i的关键邻居节点，获胜者i应付代价密文为：

其中：Enc(b'_j)是用户j提交的密文，也可以很容易得到(因为i是获胜者，获胜者所提交的信息是可以公开的)。至此，第一实体可计算得到所有获胜者实际应付的代价。

第六步，分配结果公布。

至此，频谱动态分配过程结束，第一实体将获胜者信息公开，每个用户将被告知其是否是获胜者以及应付出的实际代价。在整个频谱分配过程中，所有用户的隐私信息(包括出价信息和所申请频谱信息)均是以密文形式存在，第一实体和第二实体无法得到其相应的明文信息(只知道最后公开的获胜者信息，获胜者信息是必须要公开的，这是由频谱分配公正性的特点决定)。同时，每一个用户只知道自己是否是获胜者以及应付出的实际代价，而不会知道其他用户的隐私信息。结合这两方面，该发明实现了对频谱资源安全分配过程中所提交信息进行隐私保护的目的。