公开/公告号CN105593919A
专利类型发明专利
公开/公告日2016-05-18
原文格式PDF
申请/专利权人 日本电信电话株式会社;
申请/专利号CN201480054555.2
申请日2014-10-03
分类号G09C1/00;
代理机构北京市柳沈律师事务所;
代理人胡金珑
地址 日本东京都
入库时间 2023-12-18 15:12:16
法律状态公告日
法律状态信息
法律状态
2018-01-30
授权
授权
2016-06-15
实质审查的生效 IPC(主分类):G09C1/00 申请日:20141003
实质审查的生效
2016-05-18
公开
公开
技术领域
本发明涉及通过秘密分散对数据进行保密且进行数据处理的秘密计算的 技术领域中的秘密商转移装置、秘密比特分解装置、秘密模数转换装置、秘 密商转移方法、秘密比特分解方法、秘密模数转换方法、程序。
背景技术
以往,在通过秘密分散对数据进行保密且进行数据处理的秘密计算的技 术领域中,已知求得将对被分散的小于任意的模p的数的串x0,……,xm-1相加后的值
【数1】
除以p所得的商q(即表现为aZ=a+qp的情况下的q,其中0≤a<p、0≤q< m)的技术(称为“份额(share)的商计算”)。在实现份额的商计算的技术中, 存在比特分解(非专利文献1)。
现有技术文献
非专利文献
非专利文献1:I.Damgard,M.Fitzi,E.Kiltz,J.B.Nielsen,andT. Toft.Unconditionallysecureconstant-roundsmulti-partycomputationfor equality,comparison,bitsandexponentiation.InS.HaleviandT.Rabineds., TCC,Vol.3876ofLectureNotesinComputerScience,pp.285{304.Springer, 2006.
发明内容
发明要解决的课题
在上述的现有技术中,在将|p|设为p的比特长的情况下,存在通信量 成为O(|p|2)比特而通信成本大的课题。因此在本发明中,其目的在于, 提供能够削减通信成本的秘密商转移装置。
用于解决课题的手段
本发明的秘密商转移装置中,将
【数2】
设为表示整数x和z以y为模(modulus)而同余(congruent)的记号,
设为u为自然数且表示边界值,将m设为满足m≤2u的整数,将i设为满 足i=0,1,……,m-1的整数,将明文a设为0以上且小于任意的模p且成 为
【数3】
的整数,设为a被表现为成为
【数4】
的m个子份额x0,……,xm-1的和,将子份额的合计值aZ设为
【数5】
而将q设为基于子份额的合计值aZ的p的商时,
将商q计算为
【数6】
发明效果
根据本发明的秘密商转移装置,能够削减通信成本。
附图说明
图1是表示实施例1的秘密商转移装置的结构的框图。
图2是表示实施例1的秘密商转移装置的动作的流程图。
图3是表示线性复制转换装置的结构的框图。
图4是表示线性复制转换装置的动作的流程图。
图5是表示实施例2的秘密比特分解装置的结构的框图。
图6是表示实施例2的秘密比特分解装置的动作的流程图。
图7是表示变形例1的秘密比特分解装置的结构的框图。
图8是表示实施例3的秘密模数转换装置的结构的框图。
图9是表示实施例3的秘密模数转换装置的动作的流程图。
图10是表示变形例2的秘密模数转换装置的结构的框图。
具体实施方式
以下,详细说明本发明的实施方式。另外,对具有相同的功能的构成部 分赋予相同的序号,省略重复说明。
【实施例1】
<用语的说明>
以下,说明在本说明书中使用的用语。
[semi-honest]
semi-honest是虽然攻击者对数据进行偷窥,但处理正确地进行的前提。
[malicious]
malicious是攻击者进行任意的非法的动作的前提。
<记法>
以下,说明在本说明书中共同使用的记法。
【数7】
表示整数x和z以y为模而同余。对于任意的命题P,〔P〕设为将P的真伪 转换为整数的运算符。典型地说若P为真则为1,若为伪则为0。
<前提>
在本发明中整体上设想为在小于p的数的数据型之中,实际上储存有存 在状况依赖的小于M的数。例如在通常的计算机中,也存在在32比特整数 之中储存“性别”这样的1比特(M=2)的数据的情况。将M的比特数记载为 l。在本发明中设想这样的情况,实现不依赖于|p|(关于|p|为O(1)) 的比特通信量下的非常高速的份额的商计算。份额的商计算的高速化导致比 特分解、模数转换等秘密计算的领域的大量处理的高速化。
<秘密商转移装置1>
以下,参照图1、图2说明实施例1的秘密商转移装置。图1是表示本 实施例的秘密商转移装置1的结构的框图。图2是表示本实施例的秘密商转 移装置1的动作的流程图。
设为u为自然数且表示边界值,将m设为满足m≤2u的整数,将i设为满 足i=0,1,……,m-1的整数,将明文a设为0以上且小于任意的模p(0≤a <p)且成为
【数8】
的整数,设为a被表现为成为
【数9】
的m个x0,……,xm-1的和。设为整数i=0,1,……,m-1,将各xi称为a 的子份额。此时将子份额的合计值aZ设为
【数10】
而将q设为aZ的基于p的商。设为从多个装置向本实施例的秘密商转移装置 1发送子份额。秘密商转移装置1将商q计算为
【数11】
并输出计算出的商q(S1)。即,秘密商转移装置1在得到各xi的比特表 现时,能够通过其各下位u比特的加法电路或减法电路来计算商。根据本实 施例的秘密商转移装置1,不需要与第u比特相比更上位比特的计算的点成 为要点。在本实施例中公开的秘密商转移装置1以及秘密商转移方法在对秘 密分散后的数据保有数据的保密性而进行处理的秘密计算中考虑大量的应 用。在以下的实施例2、实施例3中说明这些应用例。
为了说明以下的实施例,首先进行秘密分散的说明。
<(k,n)-线性秘密分散)>
(k,n)-秘密分散是将明文分散为n个份额,其中若收集k个份额则能 够复原明文,且即使收集k-1个以下的份额也完全不能得到明文的信息的数 据分散方式。
在此(k,n)-线性秘密分散如以下那样定义。函数
【数12】
为(k,n)-线性秘密分散设为对于任意的单射σ:{0,……,k-1}→{0,……, n-1}存在以下的复原用的系数串。σ表现从n个份额任意地选择k个份额。 其中R设为可换群,C设为定义了与R的积的集合。
<复原>
存在某系数串
【数13】
对任意的输入a
【数14】
将SHAREpr(a)称为a的线性秘密方差值,记载为[a]。此外,对于各 i∈{0,……,n-1},将SHAREpr(a)i记载为[a]i,称为第i个或小组(party) i的份额。Shamir的秘密分散为代表性的(k,n)-线性秘密分散。在Shamir 的秘密分散中系数串为Lagrange补充法中的Lagrange系数。此外,在本发明 中在线性秘密分散之中也特别设想利用以下的复制秘密分散。
<复制秘密分散>
复制秘密分散是如下的秘密分散。首先具有m=nCk-1个可换群R的元 a0,……,am-1而将明文a设为
【数15】
并且关于各k-1小组的组(将第i个k-1小组的组设为Pi),不属于Pi的 小组都具有ai。属于Pi的小组都不具有ai。若以上那样,对于任意的k-1小 组组,对存在不具有的ai至k-1小组为止的合伙是安全的。此外若收集k小 组,则无论哪个ai都一定由谁来持有,所以能够复原。因此成为(k,n)-秘 密分散。将各ai称为子份额。例如(2,3)-复制秘密分散设为a=a0+a1+a2, 各小组的份额成为(a0,a1)、(a1,a2)、(a2,a0)。
复制秘密分散的秘密方差值如{a}那样书写,第i个小组的份额如{a} i那样书写。此外,将j设为满足j=0,1,……,m-1的整数,第j个子份额 如{a}〈j〉那样书写。在本发明的semi-honest协议中使用(k,k)-复制秘 密分散。(k,k)-复制秘密分散中存在仅k人分别持有1个份额所以高效的 优点。此外,(k,k)-复制秘密分散还存在能够从任意的(k,n)-线性秘密 分散以离线的方式简单地进行转换的优点。即,任意地选择k小组(为了简 化而在本稿中书写为0,……,k-1的k小组但也可以是任意的k小组。),对 各i<k如以下那样乘以复原时的系数即可。
{a}i=λi[a]i
以下,参照图3、图4,说明使用在本发明中能够使用的基于对应于 Malicious的协议的(k,n)-复制秘密分散的线性复制转换装置2。图3是表 示线性复制转换装置2的结构的框图。图4是表示线性复制转换装置2的动 作的流程图。对线性复制转换装置2的输入、从线性复制转换装置2的输出 为以下。
输入:线性秘密方差值[a]Zp
输出:复制秘密方差值{a}Zp
如图2所示,线性复制转换装置2包含随机数生成部21、线性转换部22、 差分值计算部23、公开部24、和算部25。随机数生成部21生成复制秘密分 散后的随机数{r}Zp(S21)。线性转换部22取得复制秘密分散后的随机数{r} Zp,将该随机数转换为期望的线性秘密分散后的随机数[r]Zp(S22)。差分 值计算部23取得线性秘密方差值[a]Zp、线性秘密分散后的随机数[r]Zp, 计算差分值[a-r]Zp(S23)。公开部24将差分值[a-r]Zp以对应于malicious 的方式进行公开(例如,参照非专利文献1),取得差分值的解码值a-r(S24)。 和算部25取得复制秘密分散后的随机数{r}Zp和差分值的解码值a-r,通过 和算(a-r)+{r}Zp={a}Zp,取得复制秘密方差值{a}Zp(S25)。(k,n) -复制秘密分散与(k,k)-复制秘密分散相反,存在能够以离线的方式转换为 任意的(k,n)-线性秘密分散(细节参照参考非专利文献1)的优点。
(参考非专利文献1)R.Cramer,I.Damg_ard,andY.Ishai.Share conversion,pseudorandomsecret-sharingandapplicationstosecurecomputation. InJ.Kilianed.,TCC,Vol.3378ofLectureNotesinComputerScience,pp. 342{362.Springer,2005.
【实施例2】
<秘密比特分解装置>
以下,参照图5、图6,说明实施例2的秘密比特分解装置。图5是表示 本实施例的秘密比特分解装置3的结构的框图。图6是表示本实施例的秘密 比特分解装置3的动作的流程图。如图5所示,秘密比特分解装置3包含公 开值倍秘密计算部31、下位比特分散部32、上位比特分散部33、下位比特 加法部34、零判定部35、上位比特加法部36。
比特分解是将小于M的数a的秘密方差值[a]Zp转换为l个秘密方差值 的串
【数16】
的操作。其中各a0,……,al-1为将a以二进制来表现时的各比特(0为最下 位)。此外[·]Zp和[·]Z2也可以是相同的形式的秘密分散,也可以是不 同的形式的秘密分散。
【数17】
是长度为l的[·]Z2的形式的秘密分散的串。秘密计算以加法/乘法为基本 处理,所以算术运算是高速的,但算术运算的结果可能会成为超过1比特的 数值。另一方面,虽然低速但实现任意的处理的逻辑电路以1比特值为输入 输出。将两者搭桥,为了在对算术运算高速地进行了处理后进行任意的处理 而将数值转换为1比特值的串是比特分解,是在实用的秘密计算中不可缺少 的处理。
<实施例2的秘密比特分解方法>
以下,参照图6说明本实施例的秘密比特分解装置3执行的秘密比特分 解方法。将p设为梅森素数。也就是说p是成为2的幂-1的素数。将(x0,……, xm-1)设为0≤a<p的子份额。将边界值u设为┌logm┐,进而将各qi、ri分别 设为表现xi的第u比特以后以及u-1比特以前的数值,将qu、ru设为表现
【数18】
的第u比特以后以及u-1比特以前的数值。于是根据式(1)将l设为l+u≤| p|而以下的等式成立。
【数19】
若利用该情况,则导入对于复制秘密分散的本实施例的算法。本算法对 式(2)进行计算。通信量为|p|,关于l为O(l)比特且不依赖于p,是 高速的。
能够从任意的线性秘密分散向复制秘密分散进行转换(参考非专利文献 1),输入限定于复制秘密分散的形式不成为实际的利用上的限制。
对秘密比特分解装置3的输入、从秘密比特分散装置3的输出如以下所 示。
输入:{a}Zp,其中2ua<p
输出:比特的秘密方差值串
【数20】
另外,参数:子份额数m∈N、u=┌logm┐,设为素数p。
公开值倍秘密计算部31在2ua<p的条件下,取得复制秘密方差值{a} Zp,通过公开值倍的秘密计算来计算变形秘密方差值{a′}Zp:=2u×Zp{a}Zp(S31)。例如对于小于p的任意的整数b,复制秘密分散的公开值倍b×Zp{a} Zp通过对{a}的各子份额乘以b来实现。此外(k,n)-线性秘密分散的效果 值倍b×Zp[a]Zp通过对[a]的各份额乘以b来实现。另外,前述的运算记 号×等意味着按进行运算的每个代数结构区分而进行运算。以下的步骤S32、 S33、S34、S36关于满足i<m的全部i执行。下位比特分散部32将变形秘 密方差值的第j个子份额{a′}Zp〈j〉的第0比特起的u比特按每个比特进行 分散而取得下位比特方差值
【数21】
(S32)。上位比特分散部33将变形秘密方差值的第j个子份额{a′}Zp〈j〉 的第u比特起的l比特按每个比特进行分散而取得上位比特方差值
【数22】
(S33)。下位比特加法部34通过加法电路的秘密计算来计算下位比特加法值
【数23】
(S34)。以下,将下位比特加法值之中下位u比特设为
【数24】
将上位u比特设为
【数25】
零判定部35取得下位比特加法值的下位u比特,通过零判定电路的秘密 计算来计算零判定值[〔ru≠0〕]Z2(S35)。上位比特加法部36取得上位比特 加法值、下位比特加法值的上位u比特、零判定值,通过加法电路的秘密计 算来计算比特的秘密分散串
【数26】
并进行输出(S36)。
[变形例1]
以下,参照图7说明作为实施例2的秘密比特分解装置3的变形例的秘 密比特分解装置3A。图7是表示本变形例的秘密比特分解装置3A的结构的 框图。如图7所示,本变形例的秘密比特分解装置3A除了上述的结构之外, 还包含将上述的线性秘密方差值转换为复制秘密方差值的结构即线性复制转 换装置2。像这样,通过秘密比特分解装置3A包含线性复制转换装置2,即 使对装置的输入为线性秘密方差值,也能够执行秘密比特分解。另外,本变 形例的秘密比特分解装置3A也可以将(k,n)-线性秘密分散转换为(k,k) -复制秘密分散后执行秘密比特分解处理,也可以将(k,n)-线性秘密分散转 换为(k,n)-复制秘密分散后执行秘密比特分解处理。
【实施例3】
以下,参照图8、图9说明实施例3的秘密模数转换装置。图8是表示 本实施例的秘密模数转换装置4的结构的框图。图9是表示本实施例的秘密 模数转换装置4的动作的流程图。如图8所示,本实施例的秘密模数转换装 置4包含公开值倍秘密计算部41、模数下位比特分散部42、模数下位比特加 法部43、转换处理部44、再变形部45、模数差分部46。
模数转换是将小于模p的数的形式的秘密方差值转换为小于其他模p′的 数的形式的处理。相当于在通常的计算机中从32比特整数向64比特整数的 型转换等,这在实用的秘密计算中也是不可缺少的处理。
<实施例3的秘密模数转换方法>
以下,参照图9说明本实施例的秘密模数转换装置4执行的秘密模数转 换方法。利用式(1),导入对于复制秘密分散的本实施例的算法。通信量为| p|,关于|p′|为O(|p′|)比特且不依赖于p,是高速的。能够从任意的 线性秘密分散转换为复制秘密分散(细节参照线性复制转换装置2的记载), 输入限定于复制秘密分散的形式不成为实际的利用上的限制。以下,表示对 秘密模数转换装置4的输入、从秘密模数转换装置4的输出。
输入:modp复制秘密方差值{a}Zp,其中2ua<p、u=┌logm┐
输出:modp′复制秘密方差值{a}Zp′
公开值倍秘密计算部41在2ua<p、u=┌logm┐的条件下,取得modp复 制秘密方差值{a}Zp,通过公开值倍的秘密计算来计算变形秘密方差值{a′} Zp:=2u×Zp{a}Zp(S41)。以下的步骤S42、S43、S45、S46关于满足i<m 的全部i执行。模数下位比特分散部42将作为模数变形秘密方差值的第i个 小组的份额的
【数27】
的第0比特起的u比特进行分散,取得模数下位比特方差值
【数28】
(S42)。注意负号不在Zp上而是在Z2u上。模数下位比特加法部43通过加法 电路的秘密计算来计算下位比特加法值
【数29】
将计算结果设为商的线性秘密方差值
【数30】
(S43)。转换处理部44对商的线性秘密方差值实施mod2→modp′转换等规 定的转换处理,取得转换后的商的线性秘密方差值{q}Zp′(S44)。关于mod 2→modp′转换的具体的运算方法在以下详细叙述。
<mod2→modp′转换(步骤1~7)>
输入:{a}2
输出:{a}p′
步骤1:生成明文中具有随机数r的两种秘密方差值{r}2、{r}p′。
步骤2:也就是说,各第i个小组生成1比特的随机数ri,进而以{·} 2、{·}p′这两种形式进行秘密分散而得到{ri}2、{ri}p′。
步骤3:通过秘密计算来计算
【数31】
其中对○重叠+而显示的记号为XOR运算,n为小组数。
步骤4:计算
【数32】
并进行公开,得到
【数33】
步骤5:计算
【数34】
步骤6:也就是说,
【数35】
若则{a}p′:={r}p′。
步骤7:
【数36】
若则{a}p′:=1-{r}p′。
接着,再变形部45计算作为变形秘密方差值
【数37】
的modp′的再变形秘密方差值
【数38】
(S45)。另外,根据式(1)而成为
【数39】
模数差分部46取得再变形秘密方差值、转换后的商的线性秘密方差值, 使用加法以及公开值倍的秘密计算来计算差分计算
【数40】
并进行输出(S46)。
[变形例2]
以下,参照图10说明作为实施例3的秘密模数转换装置4的变形例的秘 密模数转换装置4A。图10是表示本变形例的秘密模数转换装置4A的结构的 框图。如图10所示,本变形例的秘密模数转换装置4A除了上述的结构之外, 还包含将上述的线性秘密方差值转换为复制秘密方差值的结构即线性复制转 换装置2。像这样,通过秘密模数转换装置4A包含线性复制转换装置2,即 使对装置的输入为线性秘密方差值,也能够执行模数秘密转换。另外,本变 形例的秘密模数转换装置4A也可以将(k,n)-线性秘密分散转换为(k,k) -复制秘密分散后执行秘密模数转换处理,也可以将(k,n)-线性秘密分散转 换为(k,n)-复制秘密分散后执行秘密模数转换处理。
<发明的要点>
本发明的要点是,比特分解、模数转换都处于与份额的商计算密切的关 系,在使用以往|p|比特的加法电路进行了计算时,考虑商转移这样的想法, 能够以不依赖于|p|的logm比特的电路来计算。商转移是将通常在加法结 果的上位比特上显现的商利用整数剩余的性质而进行移动以使其显现在加法 结果的下位比特中的、在本发明中考虑的新的技法。关于通信量,份额的商 计算、比特分解、模数转换都关于|p|成为O(|p|2)至O(1),飞跃性 地高效化。例如在|p|=31且l=2(即在31比特整数中储存2比特数据) 的状况下比以往的最快安装(参考非专利文献2,参照图“shiftR”)还要快2600 倍左右。
(参考非专利文献2)D.Bogdanov,M.Niitsoo,T.Toft,andJ. Willemson.High-performancesecuremulti-partycomputationfordatamining applications.Int.J.Inf.Sec.,11(6):403{418,2012.
上述的各种处理不仅按照记载而时序地执行,也可以根据执行处理的装 置的处理能力或根据需要而并行或单独执行。此外,在不脱离本发明的意旨 的范围内能够适当进行变更是不言而喻的。
此外,在通过计算机来实现上述的结构的情况下,各装置应具有的功能 的处理内容通过程序来记述。并且,通过在计算机中执行该程序,从而在计 算机上实现上述处理功能。
记述了该处理内容的程序能够记录在能够由计算机读取的记录介质中。 作为能够由计算机读取的记录介质,例如也可以是磁记录装置、光盘、光磁 记录介质、半导体存储器等任意记录介质。
此外,该程序的流通例如通过将记录了该程序的DVD、CD-ROM等可移 动记录介质进行销售、转让、借出等来进行。进而,也可以设为将该程序储 存至服务器计算机的存储装置,经由网络,从服务器计算机向其他计算机转 发该程序从而使该程序流通的结构。
执行这样的程序的计算机例如首先将在可移动记录介质中记录的程序或 者从服务器计算机转发的程序暂时储存在自己的存储装置中。并且,在执行 处理时,该计算机读取在自己的记录介质中储存的程序,执行按照所读取到 的程序的处理。此外,作为该程序的其他执行方式,也可以设为计算机从可 移动记录介质直接读取程序,执行按照该程序的处理,进而也可以在每次从 服务器计算机向该计算机转发程序时,逐次执行按照所接受到的程序的处理。 此外,也可以设为不进行从服务器计算机向该计算机的程序的转发,而是通 过仅通过其执行指示和结果取得而实现处理功能的所谓ASP(应用服务提供 商(ApplicationServiceProvider))型的服务,执行上述的处理的结构。另外, 设为在本方式中的程序中,包含供于基于电子计算机的处理用的信息且遵循 于程序的信息(不是对于计算机的直接的指令但具有规定计算机的处理的性 质的数据等)。
此外,在该方式中,设为通过在计算机上执行规定的程序而构成本装置, 但也可以将这些处理内容的至少一部分在硬件上实现。
机译: 秘密商转移装置,秘密位分解装置,秘密模数转换装置,秘密商转移方法,秘密位分解方法,秘密模数转换方法及其程序
机译: 秘密商转移装置,秘密位分解装置,秘密模数转换装置,秘密商转移方法,秘密位分解方法,秘密模数转换方法,程序
机译: 秘密商量传输设备,秘密位分解设备,秘密模量转换设备,秘密商量传输方法,秘密位分解方法,秘密模量转换方法及其程序