法律状态公告日
法律状态信息
法律状态
2017-11-17
授权
授权
2014-06-04
实质审查的生效 IPC(主分类):H04L9/30 申请日:20131029
实质审查的生效
2014-04-30
公开
公开
技术领域
本发明涉及安全多方计算技术领域,具体涉及一种基于多项式插 值算法的保护任意用户群数据隐私安全的和与积计算方法。
背景技术
任意用户的和与积的安全计算具有非常广泛的应用价值。随着网 络技术的发展,个人数据经常被用于统计信息的计算或者基于数据挖 掘的应用。比如智能电网中的电量调度利用各家户的用电信息;在社 交网络中的数据挖掘牵涉到个人信息;众包(Crowd Sourcing)应用 中的服务提供基于大众用户提供的个人信息。然而用户的数据具有敏 感性,用户不愿意公开自己的数据,因此需要在不暴露单个数据的条 件下完成应用中需要的计算。大部分此类应用中需要的计算都能够用 多个和、积计算来实现(例如:线性回归分析,支持向量分类,方差 计算,平均值计算等),而和与积的各个变量来自互不信任的参与者, 即每一方都不愿意公开自己的隐私数据。
随着市场要求,在应用密码学领域中已有大量的研究提出了针对 多方多项式计算的解决方案。这些方法往往侧重于理论上的隐私保护, 而没有考虑到实际应用场景的环境因而缺少实用性。在实际应用场景 的环境中,参与计算的用户群往往动态地变化,因此不能固定某一个 用户群;参与计算的用户可能成千上万,而且个人计算平台的计算能 力与存储能力有限,计算复杂度和通信复杂度不能太大;很多应用对 计算结果的要求比较高,因此不能利用近似结果代替最终计算结果; 可信第三方或可信中心在实际应用场景下难以存在,因此计算不能依 赖这些客体。将这些环境因素考虑进去后,现有技术中的大多数方法 (例如安全多方计算,同态加密算法以及其他同领域内的研究结果) 都无法在现实生活中得到应用。尤其是在无可信信道的环境中需要得 出正确结果的算法中,至今为止的相关技术都需要对每个组合的用户 都生成一组密钥,导致每个用户需要保存个2n密钥,空间复杂度过高。 因此,需要一种切合实际的方法来安全地计算多用户提供的数据的和 与积。
发明内容
(一)要解决的技术问题
本发明的目的在于提供一种灵活、快速并且安全的保护任意用户 群数据隐私安全的和与积计算方法;使得任意组合的参与者都能够快 速并且安全的共同计算出他们的隐私数据的和与积,并且保证合适的 空间复杂度。
(二)技术方案
本发明技术方案如下:
一种基于多项式插值算法的保护任意用户群数据隐私安全的和与 积计算方法,包括步骤:
S1.系统初始化:指定安全参数κ,根据所述安全参数κ生成相 应的整数群以及系统公钥;
S2.生成用户私钥:用户群中参与者各自独立地计算私钥,使得 这些私钥的乘积在取模操作后等价于一;
S3.密钥生成:结合所述系统公钥和用户私钥为参与者生成用于 加密数据的和密钥以及积密钥;
S4.和加密:在和计算时,参与者利用得到的密钥对和计算进行 加密,并把得到的和密文发给用户群中的其他参与者;
S5.积加密:在积计算时,参与者利用得到的密钥对积计算进行 加密,并把得到的积密文发给用户群中的其他参与者;
S6.和解密:用户群中的参与者将收到的密文组合得到最终的和;
S7.积解密:用户群中的参与者将收到的密文组合得到最终的积。
优选的,所述步骤S1包括:
S11.指定安全参数κ后生成长度为κ的质数p;
S12.随机选择在中找到一个与p2(p-1)2互质的 随机数
S13.公布系统公钥<p,g,g1>。
优选的,所述步骤S2包括:
S21.用户群中任意参与者i独立地随机选取
S22.所述参与者i将发送给参与者i-1和参与者i+1;
S23.所述参与者i计算以下参数作为自己的私钥
并且,
优选的,所有参与者的数量为n,所述步骤S22中:
当i=1时,参与者i-1为参与者n;
当i=n时,参与者i+1为参与者1。
优选的,所述步骤S3包括:
S31.参与者i独立随机选取以下随机数作为自己的秘密参数:
…
其中,nmin是参与和、积计算的最少人数要求;
S32.所述参与者i与其他任意参与者j共同参与以下密钥算法:
参与者j本地计算自己的秘密多项式:
计算公开参数:
参与者j将计算得到的公开参数发给所述参与者i;
S33.所述参与者i本地计算以下参数:
并且计算以下多项式:
其中,上文公式模型是a除b得到的整数商再用p 取模,而不是a乘上b在整数域中的逆,即在公式
中a代表
S34.所述参与者i得到密钥参数
S35.对所有k=nmin,…,n,反复所述步骤S32-S34;所述参与者i得 到加密密钥
优选的,所述nmin最小为3。
优选的,所述步骤S4包括:
在进行和计算时,所有参与者计算xi的和密文:
并发给所有参与者组成的集合中的所有参与者。
优选的,所述步骤S5包括:
在进行和计算时,所有参与者计算xi的积密文:
并发给所有参与者组成的集合中的所有参与者。
优选的,所述步骤S6包括:
所有参与者根据收到的其他参与者发送的和密文计算:
优选的,所述步骤S7包括:
所有参与者根据收到的其他参与者发送的积密文计算:
(三)有益效果
本发明实施例所提供的保护任意用户群数据隐私安全的和与积计 算方法,提供了计算任意用户群的数据和与积的方法,可以让任意组 合的参与者安全地计算他们隐私数据的和与积;而且,所有数据使用 加密密钥加密,保证了数据的隐私;同时,密钥生成不需要安全的通 信信道,对窃听攻击具有鲁棒性;此外,本发明的方法不依赖可信第 三方,完全采用无中心的分布式计算;最后,本发明的方法使用简单 的加密,计算消耗与通信消耗非常小,可在计算资源受限的平台上实 现。
附图说明
图1是本发明实施例中的保护任意用户群数据隐私安全的和与积 计算方法的流程示意图。
具体实施方式
下面结合附图和实施例,对本发明的具体实施方式做进一步描述。 以下实施例仅用于说明本发明,但不用来限制本发明的范围。
如图1中所示,本实施例中所提供的基于多项式插值算法的保护 任意用户群数据隐私安全的和与积计算方法主要包括步骤:
S1.系统初始化:指定安全参数κ,根据所述安全参数κ生成相 应的整数群以及系统公钥;
S2.生成用户私钥:用户群中参与者各自独立地计算私钥,使得 这些私钥的乘积在取模操作后等价于一;
S3.密钥生成:结合所述系统公钥和用户私钥为参与者生成用于 加密数据的和密钥以及积密钥,和密钥用于和加密,积密钥用于积加 密;
S4.和加密:在和计算时,参与者利用得到的密钥对和计算进行 加密,并把得到的和密文发给用户群中的其他参与者;
S5.积加密:在积计算时,参与者利用得到的密钥对积计算进行 加密,并把得到的积密文发给用户群中的其他参与者;
S6.和解密:用户群中的参与者将收到的密文组合得到最终的和;
S7.积解密:用户群中的参与者将收到的密文组合得到最终的积。
示例性的,本实施例中还提供了一种上述保护任意用户群数据隐 私安全的和与积计算方法各步骤的具体实现方式,通过利用多项式插 值算法的特性,实现使得任意组合的用户群能够快速、安全地完成以 下和与积的计算:
其中xi为参与者i提供的隐私数据,为所有参与计算的参与者 组成的集合,只有属于集合的参与者才能够得到计算结果,并且参 与者i之外,其他人不能得到关于隐私数据xi的任何信息。
本实施例中,所述步骤S1进一步包括:
S11.指定安全参数κ后生成长度为κ的质数p;
S12.随机选择在中找到一个与p2(p-1)2互质的 随机数
S13.公布系统公钥<p,g,g1>。
本实施例中,该步骤基于离散对数完成,具体的,该步骤进一步 包括:
S21.用户群中任意参与者i在中独立地随机选取随机数
S22.所述参与者i将发送给参与者i-1和参与者i+1;
所有参与者的数量为n,在该步骤中:
当i=1时,参与者i-1为参与者n;
当i=n时,参与者i+1为参与者1。
S23.所述参与者i计算以下参数作为自己的私钥
并且,满足以下特性:
由于离散对数在大整数域内很难求解,因此,虽然所有通信信道 都是公开的,但是只有参与者i能够计算出
本实施例中,所述步骤S3进一步包括:
S31.参与者i独立随机选取以下(k-1)(n-nmin)个随机数作为自 己的秘密参数:
…
其中,nmin是参与和、积计算的最少人数要求;优选的,所述nmin最小要求为3;如果参与者总人数少于3,则参与计算的参与者可能能 够猜出其他参与者的数据。根据应用实际需求,不同的系统可以有不 同的最低人数要求(例如,在数据挖掘或众包应用中,为了得到更普 遍的结果,可能需要保证一定的样本大小)。
S32.所述参与者i与其他任意参与者j共同参与以下密钥算法:
输入:p,g,g1以及
参与者j本地计算自己的秘密多项式:
计算公开参数:
参与者j将计算得到的公开参数发给所述参与者i;
S33.所述参与者i本地计算以下参数:
并且计算以下多项式:
S34.所述参与者i得到密钥参数
S35.对所有k=nmin,…,n,反复所述步骤S32-S34;
S36.输出所述参与者i得到的加密密钥:
本实施例中,所述步骤S4进一步包括:
在进行和计算时,所有参与者计算xi的和密文:
并发给所有参与者组成的集合中的所有参与者。
本实施例中,所述步骤S5进一步包括:
在进行和计算时,所有参与者计算xi的积密文:
并发给所有参与者组成的集合中的所有参与者。
本实施例中,所述步骤S6进一步包括:
所有参与者根据收到的其他参与者发送的和密文计算:
本实施例中,所述步骤S7进一步包括:
所有参与者根据收到的其他参与者发送的积密文计算:
本实施例中所提供的保护任意用户群数据隐私安全的和与积计算 方法,起始于无中心、无可信第三方、无可信信道的环境,为互不信 任的用户提供高效、灵活并且保护隐私的和、积计算方法。该方法中 的步骤S2与步骤S3生成系统中所有用户的密钥,步骤S4与步骤S6 提供了计算任意用户群的数据和的方法,步骤S5和步骤S7步提供了 计算任意用户群数据积的方法。本实施例中所提供的保护任意用户群 数据隐私安全的和与积计算方法法可以让n名参与者中的任意子集参 与者计算他们数据的和与积,而除数据拥有者外其他人得不到其他有 关个人数据的信息。该方法的和加密涉及一次乘积和一次加法运算, 积加密涉及两次乘积和一次指数运算,因而加密的计算消耗非常低。 和解密需要次加法运算,积解密需要次乘法运算,计算消 耗也非常低。并且,每个用户只需要保存n个密钥,具有线性的空间 复杂度。
以上实施方式仅用于说明本发明,而并非对本发明的限制,有关 技术领域的普通技术人员,在不脱离本发明的精神和范围的情况下, 还可以做出各种变化和变型,因此所有等同的技术方案也属于本发明 的保护范畴。
机译: 用于任意表格数据访问的数据保护策略的动态执行,对矩形数据集的语音
机译: 使用不同级别的备用电源的数据保护系统,可在任意时间段内将数据保存在易失性存储器中
机译: 发送数据流的循环冗余码计算方法,以受保护数据帧为输入序列,计算循环冗余码