一种高效率安全多方计算方法转让专利
申请号 : CN202110443101.6
文献号 : CN112861166B
文献日 : 2021-07-27
发明人 : 张金琳 , 俞学劢
申请人 : 浙江数秦科技有限公司
摘要 :
权利要求 :
1.一种高效率安全多方计算方法,用于具有发起方和多个参与方的多方计算,其特征在于,包括以下步骤:
所述发起方将待计算函数转换为布尔电路,而后将布尔电路的门作为门计算任务,分派给多个参与方,参与方将收到其门计算任务;
由所述发起方生成输入输出标签映射表,所述输入输出标签映射表记为真值表,布尔电路由此转化为多张真值表,多张所述真值表根据门计算任务分派情况,发送给多个参与方;
每个所述参与方分别与所述发起方通过OT传输获得其数据输入相应的标签,若被分派的门计算任务的输入数据包含其他参与方的标签,则向对应参与方索要标签,参与方通过查真值表获得门计算任务的输出标签;
布尔电路全部门均得出输出标签后,布尔电路将输出结果标签,所述发起方将所述结果标签转换为真值,即为多方计算的结果;
参与方通过OT传输获得其数据输入相应的标签的方法包括以下步骤:参与方将真值表标识发送给发起方并声明请求获取标签;
所述发起方列举所述参与方发送的真值表标识对应的真值表中输入的全部可取值及其标签,所述发起方为每个可取值生成一个标示随机数,将标示随机数和可取值关联后发送给所述参与方;
所述参与方生成隐码,所述隐码为随机数,所述参与方获得与其数据输入相等的可取值对应的标示随机数,使用标示随机数对隐码进行对称加密,获得加密隐码,所述参与方将加密隐码发送给所述发起方;
所述发起方收到加密隐码后,使用全部可取值对应的标示随机数进行解密,获得与可取值数量相等的解密后的复原隐码,复原隐码中将存在且仅存在一个与原始的隐码相同,分别使用复原隐码对称加密标签,获得加密标签,将全部加密标签发送给所述参与方;
所述参与方尝试使用隐码解密每个加密标签,将能且仅能成功解密一个加密标签,获得的标签即为其数据输入相应的标签。
2.根据权利要求1所述的一种高效率安全多方计算方法,其特征在于,将门计算任务分派给多个参与方的方法包括以下步骤:首先,将仅使用参与方输入标签的门计算任务分派给对应的参与方;
而后,对于使用第一参与方和第二参与方输入标签的门计算任务,比较第一参与方和第二参与方的已分派的门计算任务数量,将门计算任务分派给已分派门计算任务数量较少的参与方,若第一参与方和第二参与方已被分派的门计算任务数量相等,则分派给第一参与方;
最后,对于使用已分派给第一参与方和第二参与方的门计算任务的输出标签的门计算任务,比较第一参与方和第二参与方的已分派的门计算任务数量,将门计算任务分派给已分派门计算任务数量较少的参与方,若第一参与方和第二参与方已被分派的门计算任务数量相等,则分派给第一参与方。
3.根据权利要求1所述的一种高效率安全多方计算方法,其特征在于,将门计算任务分派给多个参与方的方法包括以下步骤:排序后遍历参与方,将使用当前被遍历参与方以及排序在所述被遍历参与方前的参与方标签的门计算任务分配给所述被遍历参与方,即完成门计算任务分派;
由所述发起方生成输入输出标签映射表的方法包括:将布尔电路的门计算任务排序并编号,依照排序对每个门计算任务执行以下步骤:列举门计算任务的输入及输出的可取值,将每个可取值使用预设长度的随机码代替;
穷举门计算任务的输入组合,获得每个所述输入组合对应的输出,将所述输出用相应的随机码表示,将表示输入组合的随机码组合以及表示输出的随机码分别作为输入输出标签映射表的第一列和第二列,所述输入输出标签映射表即真值表,真值表的标识同相应的门计算任务的编号。
4.根据权利要求1所述的一种高效率安全多方计算方法,其特征在于,使用标示随机数对隐码进行对称加密的加密方法为:按位读取标示随机数,若被读取的标示随机数的位值为1,则按位取出隐码的位值作为加密隐码的位值,若隐码的位值被取完,则将填补数作为加密隐码的位值,所述填补数由隐码的最后一位取反获得,若被读取的标示随机数的位值为0,则随机生成0或1作为加密隐码的位值,直到遍历标示随机数,其中,所述发起方运行有检查机制,确保标示随机数中具有多于隐码长度的位值1;
相应的,在所述发起方收到加密隐码后,使用全部标示随机数进行解密的方法为:对每个标示随机数按位读取,若被读取的标示随机数的位值为1,则将加密隐码中相应位置的位值保留,若被读取的标示随机数的位值为0,则将加密隐码中相应位置的位删除,按位读取完标示随机数后,加密隐码保留下来的位值将是复原隐码以及填补数,找到与所述填补数不同的最后一位即为复原隐码的最后一位,即获得复原隐码。
5.根据权利要求1所述的一种高效率安全多方计算方法,其特征在于,使用复原隐码加密标签的方法为:
按位读取复原隐码,若被读取的复原隐码的位值为1,则按位取出标签的位值作为加密标签的位值,若标签的位值被取完,则将填补数作为加密标签的位值,所述填补数由标签的最后一位取反获得,若被读取的复原隐码的位值为0,则随机生成0或1作为加密标签的位值,直到遍历复原隐码;
相应的,所述参与方使用隐码解密加密标签的方法为:按位读取隐码,若被读取的隐码的位值为1,则将加密标签中相应位置的位值保留,若被读取的隐码的位值为0,则将加密标签中相应位置的位删除,按位读取完隐码后,加密标签保留下来的位值将是标签及填补数,找到与填补数不同的最后一位即为标签的最后一位,只有长度与约定值相同的标签为正确标签,若未得到长度正确标签或长度正确标签数量多于1个,则通知发起方,并更换标示随机数和隐码后重新尝试获取标签。
6.根据权利要求1至3任一项所述的一种高效率安全多方计算方法,其特征在于,若被分派的门计算任务的输入数据包含其他参与方的标签,则向对应参与方索要标签,参与方通过查真值表获得门计算任务的输出标签,具体包括:所述参与方向发起方发送对应真值表的标识,所述发起方根据真值表的分派结果向对应参与方索要相应的输出,当所述的对应参与方返回所述输出时,所述发起方将所述输出复原为真值,将复原得到的所述真值在所述参与方发送的真值表标识对应的真值表的标签发送给所述参与方。
说明书 :
一种高效率安全多方计算方法
技术领域
背景技术
与方原数据才能完成的约定函数的计算。使得安全多方计算具有输入隐私性、计算正确性
以及去中心化特征,能使数据既保持隐私又能被使用,从而释放隐私数据分享,隐私数据分
析,隐私数据挖掘的巨大价值。安全多方计算是电子选举、门限签名以及电子拍卖等诸多应
用得以实施的密码学基础。数据公开共享是区块链采用的分布式账本技术的特征之一,使
得数据隐私在区块链上面临考验。结合安全多方计算,使得区块链领域能够即保证数据的
隐私性,又能够保证计算的正确可信。因而在隐私智能合约、密钥管理、随机数生成等技术
中发挥着重要作用。但目前的安全多方计算方法存在效率较低的技术问题。
并在系统中广播加密输入值;生成其他参与方对应的加密集合,并向其他参与方发送;接收
其他参与方广播的加密输入值和加密集合;基于加密输入值及加密集合,计算得到反馈值;
以其他参与方的公钥对反馈值加密,并向该参与方发送加密后反馈值;接收其他参与方发
送的加密后反馈值,并基于加密后反馈值和系统中每个参与方的ID,完成目标计算任务。其
多次进行广播加密集合且使用了同态加密技术,导致运算量较大,降低了计算效率。
发明内容
待计算函数转换为布尔电路,而后将布尔电路的门作为门计算任务,分派给多个参与方,参
与方将收到其门计算任务;由所述发起方生成输入输出标签映射表,所述输入输出标签映
射表记为真值表,布尔电路由此转化为多张真值表,多张所述真值表根据门计算任务分派
情况,发送给多个参与方;每个所述参与方分别与所述发起方通过OT传输获得其数据输入
相应的标签,若被分派的门计算任务的输入数据包含其他参与方的标签,则向对应参与方
索要标签,参与方通过查真值表获得门计算任务的输出标签;布尔电路全部门均得出输出
标签后,布尔电路将输出结果标签,所述发起方将所述结果标签转换为真值,即为多方计算
的结果。理论上,任何函数都可以转换为布尔电路,即布尔电路能够实现复杂函数的计算。
将布尔电路 的门转换为真值表,并分派给不同参与方进行计算,分散了计算任务,能够缩
短安全多方计算所需要的时间,提高安全多方计算的效率。
输入标签的门计算任务,比较发起方和第二参与方的已分派的门计算任务数量,将门计算
任务分派给已分派门计算任务数量较少的参与方,若发起方和第二参与方已被分派的门计
算任务数量相等,则分派给发起方;最后,对于使用已分派给发起方和第二参与方的门计算
任务的输出标签的门计算任务,比较发起方和第二参与方的已分派的门计算任务数量,将
门计算任务分派给已分派门计算任务数量较少的参与方,若发起方和第二参与方已被分派
的门计算任务数量相等,则分派给发起方。
输入标签的门计算任务,将门计算任务分派给已分派门计算任务数量较少的参与方,若发
起方和第二参与方已被分派的门计算任务数量相等,则发起方和第二参与方已被分派的门
计算任务的并行指数,所述并行指数计算方法为:统计已被分派的门计算任务中的次级门
计算任务,所述次级门计算任务指输入中包括其他门计算任务的输出的门计算任务,将已
被分派的门计算任务的数量与次级门计算任务的数量的商作为并行指数。
务分配给所述被遍历参与方,即完成门计算任务分派。本优选方案能够均衡每个参与方被
分派到的计算量,有助于提高安全多方计算的效率。
及输出的可取值,将每个可取值使用预设长度的随机码代替;穷举门计算任务的输入组合,
获得每个所述输入组合对应的输出,将所述输出用相应的随机码表示,将表示输入组合的
随机码组合以及表示输出的随机码分别作为输入输出标签映射表的第一列和第二列,所述
输入输出标签映射表即真值表,真值表的标识同相应的门计算任务的编号。本优选技术方
案能够通过门的编号标识快速索引每张真值表,方便参与方之间进行标签传输。
的真值表标识对应的真值表中输入的全部可取值及其标签,所述发起方为每个可取值生成
一个标示随机数,将标示随机数和可取值关联后发送给所述参与方;所述参与方生成隐码,
所述隐码为随机数,所述参与方获得与其数据输入相等的可取值对应的标示随机数,使用
标示随机数对隐码进行对称加密,获得加密隐码,所述参与方将加密隐码发送给所述发起
方;所述发起方收到加密隐码后,使用全部可取值对应的标示随机数进行解密,获得与可取
值数量相等的解密后的复原隐码,复原隐码中将存在且仅存在一个与原始的隐码相同,分
别使用复原隐码对称加密标签,获得加密标签,将全部加密标签发送给所述参与方;所述参
与方尝试使用隐码解密每个加密标签,将能且仅能成功解密一个加密标签,获得的标签即
为其数据输入相应的标签。本方案提供的OT传输方法能够在两个参与方之间完成,不需要
广播数据,减少了通信量需求。参与方不能存储加密隐码,当参与方将加密隐码发送给发起
方后,参与方应销毁加密隐码。
隐码的位值被取完,则将填补数作为加密隐码的位值,所述填补数由隐码的最后一位取反
获得,若被读取的标示随机数的位值为0,则随机生成0或1作为加密隐码的位值,直到遍历
标示随机数,其中,所述发起方运行有检查机制,确保标示随机数中具有多于隐码长度的位
值1;相应的,在所述发起方收到加密隐码后,使用全部标示随机数进行解密的方法为:对每
个标示随机数按位读取,若被读取的标示随机数的位值为1,则将加密隐码中相应位置的位
值保留,若被读取的标示随机数的位值为0,则将加密隐码中相应位置的位删除,按位读取
完标示随机数后,加密隐码保留下来的位值将是复原隐码以及填补数,找到与所述填补数
不同的最后一位即为复原隐码的最后一位,即获得复原隐码。隐码的位数不需要提前约定,
即减少了通信次数,也提高了加密的安全性,本方案提供的加密方案具有计算不复杂,计算
快速的优点,能够进一步提高安全多方计算的效率。
填补数作为加密标签的位值,所述填补数由标签的最后一位取反获得,若被读取的复原隐
码的位值为0,则随机生成0或1作为加密标签的位值,直到遍历复原隐码;相应的,所述参与
方使用隐码解密加密标签的方法为:按位读取隐码,若被读取的隐码的位值为1,则将加密
标签中相应位置的位值保留,若被读取的隐码的位值为0,则将加密标签中相应位置的位删
除,按位读取完隐码后,加密标签保留下来的位值将是标签及填补数,找到与填补数不同的
最后一位即为标签的最后一位,只有长度与约定值相同的标签为正确标签,若未得到长度
正确标签或长度正确标签数量多于1个,则通知发起方,并更换标示随机数和隐码后重新尝
试获取标签。标签的位数为全部参与方均知晓的约定值。
对应参与方返回所述输出时,所述发起方将所述输出复原为真值,将复原得到的所述真值
在所述参与方发送的真值表标识对应的真值表的标签发送给所述参与方。
率;2)通过OT传输在参与方和发起方之间传递标签,能够有效保护参与方输入数据的隐私,
保证各个参与方的数据安全;3)通过使用标示随机数和隐码进行对称加密传递标签,避免
使用复杂的加密算法,能够提高标签传递的效率。
附图说明
具体实施方式
候选人的布尔值输入布尔电路 ,最终布尔电路 将输出当前候选人是否成功被选上的结
果布尔值。也可以将求和函数转换为布尔电路,各参与方将自身的销售额转换为标签输入
布尔电路 后,布尔电路 最终会得出代表行业销售总额的标签组合,即布尔值组合,也即
一个二进制数。用于不记名电子拍卖时,各参与方将自己的出价输入,布尔电路 将比较各
参与方出价的大小,并输出出价最高的参与方,即为拍卖中标方。
输出,布尔电路 被表示为M张真值表,M为布尔电路 中门的数量。使用输入输出标签映射
表,即真值表,各参与方将不需要暴露自己的输入数据,当用于求行业销售总额时,各参与
方不需要暴露自己的销售额。同时,也使得各参与方无法操控每个门的输出,因为参与方无
法知晓真值表中每个标签的真实含义,如强行作恶,可能会得出对自己不利的结果标签,因
而不会作恶。
签,参与方 获得被分派的门的输入标签后,通过查真值表获得门的输出标签。向对应参与
方索要输出标签的方法为:参与方 向发起方索要 ,发起方根据真值表 的分派结果向
对应参与方 索要相应的输出 ,表示输出与 连接的真值表下标,当参与方 返回输出
时,发起方将 复原为真值,将复原得到的真值对应的标签发送给参与方 。
的门为“与”门,也不知晓 对应真值表T21中的哪个输入标签,因而无法直接获得门的
输出。请参阅表2,表2为方便理解本技术方案而列出的表格,在实际应用中并不会有这样表
被传递。
E2 门的第一个输入的第二个可取值,即1 01000101
F1 门的第二个输入的第一个可取值,即0 01011001
F2 门的第二个输入的第二个可取值,即1 11110010
G1 门的第一个可能输出值,即0 11010101
G2 门的第一个可能输出值,即1 01010100
,查表1所示的真值表,可得输入对应为第三行,第三行的输出为11010101,
参与方 不知晓11010101的含义,因而不能知晓结果,使得参与方 无法操纵门的结果,避免
其作恶。因为真值表T21的第5行和第6行,为两个干扰行,无论参与方 的输入是什么,发起
方永远都不会返回第5行和第6行所表示的组合,使得参与方 不知晓 以外的输入,对
应的标签是什么,保护了真值表的隐秘性,进一步避免参与方 操纵真值表作恶。
为真值表,并分派给不同参与方进行计算,分散了计算任务,能够缩短安全多方计算所需要
的时间,提高安全多方计算的效率。
和参与方 的输入标签可计算的门记为 ,比较参与方 和参与方 已被分派的门的数
量,将门 分派给已分派门数量较少的参与方,若参与方 和参与方 已被分派门的数量
相等,则分派给参与方 ,其中 。步骤A3)使用已分派给参与方 和参与方 的门的输
出标签可计算的门记为 ,比较参与方 和参与方 已被分派的门的数量,将门 分派给
已分派门数量较少的参与方,若参与方 和参与方 已被分派门的数量相等,则分派给参
与方 ,其中 。
步骤B2)列举门的输入及输出的可取值,将每个可取值使用预设长度的随机码代替;步骤
B3)穷举门的输入组合及相对应的输出,用相应的随机码表示,分别作为真值表的第一列和
第二列,将真值表关联门的编号。能够通过门的编号标识快速索引每张真值表,方便参与方
之间进行标签传输。
值表中输入 的全部可取值 及其标签 ,为可取值的下标,发起方为每个可取值 生
成一个标示随机数 ,将标示随机数 和 关联后发送给参与方 ;步骤C3)参与方 收到
标示随机数 及关联的 后,生成隐码 ,获得与 相等的 对应的标示随机数 ,
使用标示随机数 对隐码 进行加密,获得加密隐码 ,参与方 将加密隐码 发送
给发起方;步骤C4)发起方收到加密隐码 后,使用全部可取值 对应的标示随机数 进
行解密,获得与可取值 数量相等的解密后的复原隐码 ,复原隐码 中有且仅有一个
与隐码 相同,分别使用复原隐码 加密 对应的标签 ,获得加密标签 ,将全部加
密标签 发送给参与方 ;步骤C5)参与方 尝试使用隐码 解密每个加密标签 ,将能且
仅能成功解密一个标签 ,即与 相等的 对应的标签 ,即标签 。本方案提供的OT
传输方法能够在两个参与方之间完成,不需要广播数据,减少了通信量需求。参与方 不能
存储加密隐码 ,当参与方 将加密隐码 发送给发起方后,参与方 应销毁加密隐码 。
码 的位值作为加密隐码 的位值,若隐码 的位值被取完,则将填补数作为加密隐码 的
位值,填补数由隐码 的最后一位取反获得,若标示随机数 位值为0,则步骤C33)随
机生成0或1作为加密隐码 的位值,直到遍历标示随机数 ,其中,发起方运行有检
查机制,确保标示随机数 中具有多于隐码 长度的位值1;步骤C4)中,发起方收到
加密隐码 后,使用全部可取值 对应的标示随机数 进行解密的方法为:步骤C41)对每
个标示随机数 按位读取,若标示随机数数 的位值为1,则步骤C42)将加密隐码 中相
应位置的位值保留,若标示随机数 的位值为0,则步骤C43)将加密隐码 中相应位置的
位删除,步骤C44)按位读取完标示随机数 后,加密隐码 保留下来的位值将是隐码 及
若干个填补数,找到与填补数不同的最后一位即为隐码 的最后一位。表3记载了本实施例
中,获取真值表T21的第一个输入E取值为0时的标签过程中,发起方和参与方i执行的操作
和生成的变量的值。其中,为避免错误解密值bn’中的取值为1的位值数量不足,应当使标签
具有较多的位数,本实施例中标签 具有25位,若使用具有255位长度的标签 则效
果更佳。
值,若标签 的位值被取完,则将填补数作为加密标签 的位值,填补数由标签 的最
后一位取反获得,若复原隐码 位值为0,则随机生成0或1作为加密标签 的位值,直到
遍历复原隐码 ;参与方 尝试使用隐码 解密加密标签 的方法为:按位读取隐码 ,
若隐码 的位值为1,则将加密标签 中相应位置的位值保留,若隐码 的位值为0,则将加
密标签 中相应位置的位删除,按位读取完隐码 后,加密标签 保留下来的位值将是标
签 及若干个填补数,找到与填补数不同的最后一位即为标签 的最后一位,只有长度
与约定值相同的标签 为正确标签,若得到的正确标签数量为0或者大于1,则通知第一约
定方,并从步骤C1)重新尝试获取标签。其中,参与方 运行有检查机制,使加密隐码 经任
一标示随机数 解密后,所具有的位值1数量大于标签 的位数,标签 的位数为全部
参与方均知晓的约定值。
隐码 删除。本实施例中,则采用了另外的实施方式,提高了确保参与方 不保存加密隐码
的可信度。本实施例中,参与方 生成加密隐码 后,将加密隐码 以及对应的标示随机
数 发送给参与方 ,参与方 根据标示随机数 ,将标示随机数 中位值取0对应的加
密隐码 位值进行随机改动,而对标示随机数 中位值取1对应的加密隐码 位值不做操
作,将改动后的加密隐码 发送给发起方。由于参与方 并不知道更多信息,因而无法得知
任何有用信息,且仅对标示随机数 中位值取0对应的加密隐码 位值进行随机改动,不
会影响后续步骤的解密。改动不需要针对每个取值为0的位值,随机改动若干个即可,如表4
中所示意的改动。为实现事后验证,参与方 生成加密隐码 后,将加密隐码 以及对应的
标示随机数 加密后上链存储,发起方收到改动后的加密隐码 后,将所收到的加密隐码
加密后上链存储,上链存储前的加密采用各自的私钥进行加密。
标签以及参与方 的输入和输出标签能够计算的门分配给参与方 ,其中 ,当
时,不考虑参与方 ,循环自加1,直到布尔电路 的全部门被分派。