基于离散对数的数据和与积的计算方法及装置

摘要

本发明提供一种基于离散对数的数据和与积的计算方法，包括：基于指定安全参数κ生成相应的有限整数群

说明书

技术领域

本发明涉及安全多方计算领域，尤其是基于离散对数的数据和与 积的计算方法及装置。

背景技术

n个用户的和与积的安全计算具有非常广泛的应用价值。随着网络 技术的发展，个人数据经常被用于统计信息的计算或者基于数据挖掘 的应用。比如智能电网中的电量调度利用各家户的用电信息；在社交 网络中的数据挖掘牵涉到个人信息；众包（Crowd Sourcing）应用中的 服务提供基于大众用户提供的个人信息。然而用户的数据具有敏感性， 用户不愿意公开自己的数据，因此需要在不暴露单个数据的条件下完 成应用中需要的计算。大部分此类应用中需要的计算都能够用多个和、 积计算来实现（例如：线性回归分析，支持向量分类，方差计算，平 均值计算等），而和与积的各个变量来自互不信任的设备，即每一方都 不愿意公开自己的隐私数据。

随着市场要求，在应用密码学领域中已有大量的研究提出了针对 和、积计算的解决方案。这些方法往往侧重于理论上的隐私保护，而 没有考虑到实际应用场景的环境因而缺少实用性。在实际应用环境中， 参与计算的用户可能成千上万，而且个人计算平台的计算能力与存储 能力有限，计算复杂度和通信复杂度不能太大；很多应用对计算结果 的要求比较高，因此不能近似结果代替最终计算结果；可信第三方或 可信中心在实际应用场景下难以存在，因此计算不能依赖这些客体。 将这些环境因素考虑进去后，大多数现有方法（安全多方计算，同态 加密算法以及其他同领域内的研究结果）都无法在现实生活中得到应 用。因此，需要一种切合实际的方法来安全地计算多变量多项式。。

发明内容

（一）要解决的技术问题

本发明提供一种基于离散对数的数据和与积的计算方法，使得n名 设备能够快速地并安全地共同计算出他们数据的和与积。

（二）技术方案

为解决上述技术问题，本发明提供一种基于离散对数的数据和与 积的计算方法，该方法用于互相通信的n方设备的安全多方计算领域， 包括：

基于指定安全参数κ生成相应的有限整数群并根据计算并公布使用的公钥，其中，p为比特长度为κ的质数；

对于n方设备中的设备i，基于所述及公钥，控制设备i计 算加密时使用的和密钥与积密钥其中，1<=i<=n且i为正整 数，n为设备的人数；

基于所述和密钥与积密钥控制设备i对数据分别进行和 加密计算与积加密计算，得到和密文C_i，∑和积密文C_i，∏，并将所述和密 文C_i，∑和积密文C_i，∏广播给他设备；

控制设备i接收其他设备的和密文与积密文，并对n方设备的和密 文总和进行解密得到最终数据和，以及对n方设备的积密文总 和进行解密得到最终数据积。

具体的，设备i通过以下步骤计算和密钥与积密钥

在所述与中选取两个随机数与分别生成 和密钥参数和积密钥参数

将所述和密钥参数和积密钥参数均向设备i-1与设备 i+1发送，并接收来自设备i-1的和密钥参数和积密钥参数 以及接收来自设备i+1的和密钥参数和积密钥参数

通过以下公式分别计算和密钥以及积密钥

其中，与满足以下条件：

具体的，设备i对数据通过以下公式分别进行和加密计算与积加密 计算：

其中，x_i为设备i的数据。

具体的，设备i通过以下公式分别计算最终数据和以及最终 数据积

$\underset{i=1}{\overset{n}{\Sigma }}{x}_i=\frac{x-1\mathrm{mod}{p}^2}{p}\mathrm{mod}p$

为解决上述问题，本发明还采用另一种技术方案：提供一种基于 离散对数的数据和与积的计算装置，该装置用于互相通信的n方设备 的安全多方计算领域，包括：

密钥计算模块，用于基于有限整数群及预设公钥，计算加 密时使用的和密钥与积密钥其中，1<=i<=n且i为正整数，n 为设备的人数，所述有限整数群基于指定安全参数k生成，预 设公钥基于所述生成；；

密文计算模块，用于基于所述和密钥与积密钥对数据分 别进行和加密计算与积加密计算，得到和密文C_i，∑和积密文C_i，∏，并将 所述和密文C_i，∑和积密文C_i，∏广播给他设备；

数据和与数据积计算模块，用于接收其他设备的和密文与积密文， 并对n方设备的和密文总和进行解密得到最终数据和，以及对 n方设备的积密文总和进行解密得到最终数据积。

具体的，所述密钥计算模块包括：密钥参数生成单元、密钥参数 接收单元以及密钥计算单元。

密钥参数生成单元，用于在所述与中选取两个随机数 与分别生成和密钥参数和积密钥参数

密钥参数接收单元，用于将所述和密钥参数和积密钥参数均向设备i-1与设备i+1发送，并接收来自设备i-1的和密钥参数 和积密钥参数以及接收来自设备i+1的和密钥参数和积密钥参数

密钥计算单元，用于通过以下公式分别计算和密钥以及积密钥

其中，与满足以下条件：

具体的，所述密文计算模块对数据通过以下公式分别进行和加密 计算与积加密计算：

其中，x_i为设备i的数据。

具体的，所述数据和与数据积计算模块通过以下公式分别计算最 终数据和以及最终数据积

$\underset{i=1}{\overset{n}{\Sigma }}{x}_i=\frac{x-1\mathrm{mod}{p}^2}{p}\mathrm{mod}p$

（三）有益效果

区别于背景技术，本发明所有数据使用加密密钥加密，进一步保 证了数据的隐私；密钥生成不需要安全的通信信道，对窃听攻击具有 鲁棒性；整个协议不依赖可信第三方，完全采用无中心的分布式计算， 实现方案更为简单，计算消耗与通信消耗非常小，可在计算资源受限 的平台上有效实现，使得n名设备能够快速地并安全地共同计算出他们 数据的和与积。

附图说明

图1是本发明一实施方式中基于离散对数的数据和与积的计算方 法流程示意图；

图2是图1所示实施方式某些具体实施例中和密钥与积密钥的计 算过程示意图；

图3是本发明一实施方式中基于离散对数的数据和与积的计算系 统模块图；

图4是图3所示实施方式某些具体实施例中密钥计算模块的结构 模块图。

具体实施方式

为使本发明的目的、内容、和优点更加清楚，下面结合附图和实 施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于 说明本发明，但不用来限制本发明的范围。

请参阅图1及图2，本实施方式提供了一种基于离散对数的数据和 与积的计算方法，该方法用于互相通信的n方设备的安全多方计算领 域。该方法起始于步骤101，基于指定安全参数κ生成相应的有限整数 群并根据计算并公布使用的公钥，其中，p为比特长度 为κ的质数，有限整数群的大小由κ决定。具体的，公钥的计算 过程如下：在有限整数域中随机选择有限整数域中随机 选择其中，g₂满足gcd(g₂，p²)＝１，即g₂与p²互质；随后， 计算并公布以下公钥：

对于n方设备中每台设备，均会进行如下操作。为方便理解，选 取设备i进行说明。

在步骤102，对于n方设备中的设备i，基于所述及公钥， 控制设备i计算加密时使用的和密钥与积密钥其中，1<=i<=n 且i为正整数，n为设备的人数。具体的，设备i通过步骤1021-1023 计算和密钥与积密钥

在步骤1021，在在所述与中选取两个随机数与 分别生成和密钥参数和积密钥参数

在步骤1022，将所述和密钥参数和积密钥参数均向设备 i-1与设备i+1发送，并接收来自设备i-1的和密钥参数和积密 钥参数以及接收来自设备i+1的和密钥参数和积密钥参数 其中，当i=1时，第一个设备发给第二个设备与第n个设备； 当i=n时，第n个设备发给第n-1个设备与第一个设备。

在步骤1023，通过以下公式分别计算和密钥以及积密钥

其中，与满足以下条件：

，得到的用于和加密后计算数据和，用于积加密后计算数据积。

在步骤103，基于所述和密钥与积密钥控制设备i对数 据分别进行和加密计算与积加密计算，得到和密文C_i，∑和积密文C_i，∏， 并将所述和密文C_i，∑和积密文C_i，∏广播给他设备。具体的，设备i对数据 通过以下公式分别进行和加密计算与积加密计算：

其中，x_i为设备i的隐私数据，除数据拥有者（即设备i）之外其 他人不能得到关于隐私数据的任何信息。该过程中所有通信信道都是 公开的，因此攻击者能得到与然而由于离散对数 在大整数域的难解性，任何受限于多项式时间的攻击者无法得到r_i-1，∑、 r_i，∑或r_i+1，∑，也得不到同理，该攻击者也得不到

在步骤104，控制设备i接收其他设备的和密文与积密文，并对n 方设备的和密文总和进行解密得到最终数据和，以及对n方设 备的积密文总和进行解密得到最终数据积。具体的，设备i收 到所有其他设备的和密文C_i，∑（n-1个和密文）和所有其他设备的积密 文C_i，∏（n-1个积密文）之后通过以下公式分别计算最终数据以 及最终数据积

$\underset{i=1}{\overset{n}{\Sigma }}{x}_i=\frac{x-1\mathrm{mod}{p}^2}{p}\mathrm{mod}p$

其中，上文公式模型是a除b得到的整数商再用p取模，而 不是a乘上b在整数域中的逆，即在公式

$\underset{i=1}{\overset{n}{\Sigma }}{x}_i=\frac{x-1\mathrm{mod}{p}^2}{p}\mathrm{mod}p$

中a代表中分子的“x-1  mod  p²”，b代表中分 母的“p”。

通过上述过程，可得出如下结论：本技术方案可让n名设备在无可 信信道或可信第三方的环境下起始整个协议，使得各个设备只能够得 到n个数据的和或积，而得不到任何有关他人隐私数据的信息。本方法 的和加密涉及一次指数运算与一次乘积运算，积加密涉及一次成绩运 算，因而计算消耗非常低。和解密涉及n-1次乘积与一次整除运算， 积解密涉及n-1次乘积运算，计算消耗也非常低。密钥生成也只需要 常数次的参数交换，通信复杂度也很低。然而，由于本方法使用的密 钥利用离散对数的难解性得到，第三方无法区分密文与整数群中随机 抽取的数，因此保证了各个数据的隐私。本方法使用简单的加密，计 算消耗与通信消耗非常小，可在计算资源受限的平台上实现，极大地 解决了背景技术中提到的诸多不足。

然而，为了得到计算的安全性与正确性，本方法需要假设用户之 间互不共谋，并且所有计算结果均小于有限整数域大小p。即在上述某 些实施例中，为了保证计算的隐私性与正确性，该方案具有以下假设 条件：

（1）所有设备互不共谋：“互不共谋”意味着所有设备不与其他 设备共享自己的隐私数据或者自己的私；否则两名邻接的共谋者i-1 与共谋者i+1可以计算出第i名设备的密钥，因而无法保证数据的隐私 性。

（2）数据的和或积不超过最终的模数p：如果和或积超过p，由于 取模操作最终结果不等于真实的和或积，因而无法保证计算的正确性。

通过上述限制，本方法可以让n名互不共谋的设备安全地计算各自 隐私数据的和与积；所有数据使用加密密钥加密，进一步保证了数据 的隐私；密钥生成不需要安全的通信信道，对窃听攻击具有鲁棒性； 整个协议不依赖可信第三方，完全采用无中心的分布式计算，实现方 案更为简单，计算消耗与通信消耗非常小，可在计算资源受限的平台 上有效实现。

请参阅图3及图4，本实施方式提供了一种基于离散对数的数据和 与积的计算系统，包括整数生成模块301以及基于离散对数的数据和 与积的计算装置，基于离散对数的数据和与积的计算装置包括：密钥 计算模块302、密文计算模块303以及数据和与数据积计算模块304， 该装置用于互相通信的n方设备的安全多方计算领域。在本实施方式 中，该装置设置在设备i上，各模块的工作原理具体如下。

整数群生成模块301，用于基于指定安全参数κ生成相应的有限整 数群并根据计算并公布使用的公钥，其中，p为比特长 度为κ的质数。

密钥计算模块302，用于基于所述及公钥，计算加密时使用 的和密钥与积密钥其中，1<=i<=n且i为正整数，n为设备的 人数。在具体如图4所示的某些实施例中，密钥计算模块302包括密 钥参数生成单元3021、密钥参数接收单元3022以及密钥计算单元3023， 各模块的功能如下所示。

密钥参数生成单元3021，用于在所述与中选取两个随机数 与分别生成和密钥参数和积密钥参数

密钥参数接收单元3022，用于将所述和密钥参数和积密钥参 数均向设备i-1与设备i+1发送，并接收来自设备i-1的和密钥 参数和积密钥参数以及接收来自设备i+1的和密钥参数 和积密钥参数

密钥计算单元3023，用于通过以下公式分别计算和密钥以及 积密钥

其中，与满足以下条件：

密文计算模块303，用于基于所述和密钥与积密钥对数 据分别进行和加密计算与积加密计算，得到和密文C_i，∑和积密文C_i，∏， 并将所述和密文C_i，∑和积密文C_i，∏广播给他设备。具体的，所述密文计 算模块对数据通过以下公式分别进行和加密计算与积加密计算：

其中，x_i为设备i的隐私数据，除数据拥有者（即设备i）之外其 他人不能得到关于隐私数据的任何信息。该过程中所有通信信道都是 公开的，因此攻击者能得到与然而由于离散对数在 大整数域的难解性，任何受限于多项式时间的攻击者无法得到r_i-1，∑、r_i，∑或r_i+1，∑，也得不到同理，该攻击者也得不到

数据和与数据积计算模块304，用于接收其他设备的和密文与积密 文，并对n方设备的和密文总和进行解密得到最终数据和，以 及对n方设备的积密文总和进行解密得到最终数据积。具体 的，所述数据和与数据积计算模块分别通过以下公式计算最终数据和 以及最终数据积

上文公式模型是a除b得到的整数商再用p取模，而不是a乘 上b在整数域中的逆，即在公式

$\underset{i=1}{\overset{n}{\Sigma }}{x}_i=\frac{x-1\mathrm{mod}{p}^2}{p}\mathrm{mod}p$

中a代表中分子的“x-1  mod  p²”，b代表中分 母的“p”。

通过上述过程，可得出如下结论：本装置可让n名设备在无可信信 道或可信第三方的环境下起始整个协议，使得各个设备只能够得到n个 数据的和或积，而得不到任何有关他人隐私数据的信息。本装置的和 加密涉及一次指数运算与一次乘积运算，积加密涉及一次成绩运算， 因而计算消耗非常低。和解密涉及n-1次乘积与一次整除运算，积解 密涉及n-1次乘积运算，计算消耗也非常低。密钥生成也只需要常数 次的参数交换，通信复杂度也很低。然而，由于本装置使用的密钥利 用离散对数的难解性得到，第三方无法区分密文与整数群中随机抽取 的数，因此保证了各个数据的隐私。本装置使用简单的加密，计算消 耗与通信消耗非常小，可在计算资源受限的平台上实现，极大地解决 了背景技术中提到的诸多不足。

然而，为了得到计算的安全性与正确性，本装置需要假设用户之 间互不共谋，并且所有计算结果均小于有限整数域大小p。即在上述某 些实施例中，为了保证计算的隐私性与正确性，该方案具有以下假设 条件：

（1）所有设备互不共谋：“互不共谋”意味着所有设备不与其他 设备共享自己的隐私数据或者自己的私；否则两名邻接的共谋者i-1 与共谋者i+1可以计算出第i名设备的密钥，因而无法保证数据的隐私 性。

（2）数据的和或积不超过最终的模数p：如果和或积超过p，由于 取模操作最终结果不等于真实的和或积，因而无法保证计算的正确性。

通过上述限制，本装置可以让n名互不共谋的设备安全地计算各自 隐私数据的和与积；所有数据使用加密密钥加密，进一步保证了数据 的隐私；密钥生成不需要安全的通信信道，对窃听攻击具有鲁棒性； 整个协议不依赖可信第三方，完全采用无中心的分布式计算，实现方 案更为简单，计算消耗与通信消耗非常小，可在计算资源受限的平台 上有效实现。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范围， 凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换， 或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专 利保护范围内。