秘密分散系统、分散装置、分散管理装置、取得装置、秘密分散方法、程序及记录介质的制作方法
专利名称：秘密分散系统、分散装置、分散管理装置、取得装置、秘密分散方法、程序及记录介质的制作方法
技术领域：
本发明涉及秘密分散技术。
背景技术：
在保管秘密信息的情况下，有秘密信息的丢失或破坏的危险和被盗的危险。丢失或破坏的危险可通过事先保管多个秘密信息来降低。但是，在该情况下，被盗的危险增加。作为同时解决这些危险的方法之一，具有秘密分散法(SSS :Secret Sharing Scheme)(例如，参照非专利文献1、2)。秘密分散法是如下方式，S卩，利用秘密信息MSK生成多个共享信息SH (I),…，SH(N)，并使这些信息分散到多个分散管理装置PA (I),…，PA (N)中而进行管理，并且，仅在 能够得到这些共享信息SH (I),…，SH (N)中规定数以上的共享信息的情况下，可恢复秘密信息MSK。下面,表不秘密分散法代表性的方式。(N, N)阈值秘密分散方式在(N，N)阈值秘密分散方式(有时也称为“N-out-of-N分散方式”或“N-out_of-N阈值分散方式”))中，只要提供所有的共享信息SH (I),…,SH (N),就可恢复秘密信息MSK,但即使提供任意N-1个共享信息SH (φιSH ( ((Jn.!)，也不能完全得到秘密信息MSK的信息。下面，表不(N, N)阈值秘密分散方式的一个例子。·随机选择 SH1,…，SH1^1。·进行 SHn=MSK- (SH1+…+SHim)的计算。·使各共享信息SH1,…，SHn分散到多个管理装置PA (I),…，PA (N)中而进行管理。·只要提供所有的共享信息SH1,…，SHn,就可通过+SHn的恢复处理，恢复秘密信息MSK。另外，用于从共享信息SH1,…，SHdii密信息MSK的运算MSK=SH1+…+SHn是线性的。因此，在以各共享信息SH (I),…，SH (N)和值σ为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SH’ (I),…，SH’(N)，进行恢复处理的情况下，得到以秘密信息MSK和值σ为被运算符进行该线性运算CALC的结果。例如，在以SH’
(1)= σ -SH (I),.. ,SH' (Ν) = σ *SH (N)为各共享信息 SH’ (I),…，SH’(N)执行恢复处理的情况下，得到下面的值。O · SH (1)+... + 0 · SH (N)=σ · (SH (I) +...+SH (N))=σ . MSK... (I)另一方面，在以各共享信息SH (I),…，SH (N)和相互独立的值σ (1)，…，σ(N)为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SH’Cl),…，SH’(N)，执行恢复处理的情况下，通常，不能得到以秘密信息MSK为被运算符的运算结果。例如，在以 SH’ (1) = σ (I) · SH (1)，· ·，SH’ (Ν) = σ (N) · SH (N)为各共享信息SH’ (I),…，SH’(N)，执行恢复处理的情况下，得到下面的值。σ (I) · SH (1)+— + σ (N) · SH (N)…(2)(Kt, N)阈值秘密分散方式在(Kt，N)阈值秘密分散方式(有时也称为“Kt-out_of-N分散方式”或“Kt-0Ut-0f-N阈值分散方式”)中，只要提供任意不同的Kt个共享信息SH (φι),…，SH ((pKt)，就可恢复秘密信息MSK ，但即使提供任意Kt-1个共享信息SH (φι), SH ( φΚΜ ),也不能完全得到秘密信息MSK的信息。下标的Kt表示Kt。下面，表不(Kt, N)阈值秘密分散方式的一个例子。·随机挑选满足 f (O)=MSK 的 Kt-1 次的多项式 f (χ) = ξ0+ξ1 * χ+ξ2 * χ2+···+ ξΚΗ · χΚΗ。即，设为Ici=MSK,随机挑选ξ1；…，ξΚΗ。将共享信息设为SHp= ( P , f(P )) ( P =1,…，N)。 在得到任意不同的Kt个共享信息SHitp1),…，SH(<pKt) ((Cp1, ···, <pKt)C ( I, N))的情况下，例如，使用拉格朗日(Lagrange)内插公式，通过下面那样的恢复处理，可恢复秘密信息MSK。
MSK=f ( O ) =λι· ( φι) +.·.+λο' ((ptct)... ( 3 )[数I]
P
(χ-^,)···ν···(χ-^κ ),.、
1 Ρ1 ^Fq …(4)
ΚΦ -病)··.▽··’(#,,-么丨)另外，意思是不存在从开头到第P个被运算符〔分母的要素(φρ-φρ),分子
的要素(χ-φΡ)〕。即，式(4)的分母如下。
((Pp-(P1) .··.· ( φρ-φρ-1) · ( φΡ-φΡ+ι) ··.·· ( φΡ-φΚι)式(4)的分子如下。
(X-(Pl) ·.·■· ( X-Cpp-1 ) · ( X-ψρ+ι ) ·...· ( X-CpKt )它们的关系即使在域上也成立。式(3)的运算是线性的。因此，以各共享信息SH ((pi )，…，SH ((pKt)和值σ为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SFT(Cp1), SH' (φΚ )恢复的值与以秘密信息MSK和值。为被运算符进行线性运算CALC的结果相等。另一方面，在以各共享信息SH( Φ!)，…，SH (φκι)和相互独立的值σ ( φι), ..., σ (cpKt)为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息φι )，…，SH' (φκι),执行恢复处理的情况下，通常，不能得到以秘密信息MSK为被运算符的运算结果。
现有技术文献非专利文献非专利文献1:黑泽馨、尾形t力、(S、“現代暗号O基礎数理(電子情報通信 > 夕千弋 V 'J 一文')，，、；！口 f 社、2004 年 3 月、p. 116-119非专利文献2 :A. Shamir, 〃How to Share a Secret", Communications of theACM，Novemberl979, Volume22，NumberlI, pp. 612-613.
发明内容
发明要解决的课题假定满足下面的条件的方式。(条件I)分散装置对秘密信息MSK进行秘密分散，生成多个共享信息SH(I),…，SH (N)，并将这些共享信息分散到多个分散管理装置PA (I),…，PA (N)中而进行管理。(条件2)各分散管理装置PA(1)，…，PA (N)分别执行一些运算。(条件3)取得装置虽然不能得到秘密信息MSK，但在提供由规定数以上的分散管理装置生成的运算结果的情况下，能够得到与被运算符中包含秘密信息MSK和任意值σ的运算结果对应的生成信息。但是，实现这种方式是不容易的。即，若各分散管理装置PA (I),…，PA (N)分别使用相互独立的值σ (1)，…，σ (N)执行运算的话，取得装置不能正确地执行以各分散管理装置的运算结果为共享信息的恢复处理，得不到希望的生成信息。另一方面，值σ可以成为用于推测生成信息的信息，因此所有的分散管理装置PA (I),…，PA (N)共享值σ其本身，从安全性的观点来看，不优选。本发明就是鉴于这种点而提出的，其目的在于，安全地实现满足上述条件I 3的方式。用于解决课题的手段在本发明中，通过分散装置、Σα=> (α)个分散管理装置PA ( a , h ( α ))(α=1，…，L，L芎2，h ( α )=1，…，H ( α )，Η ( α )芎2)和取得装置，执行秘密分散处理。分散装置将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，···，Ψ4^η(Ψ)设为I以上的整数、将ζ ( Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 Θ ( ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1, ···, η ( ψ ) + ζ (ψ),η(ψ)芎 I,ζ ( ψ )兰I)的巡回群G2的η ( ψ ) + ζ ( Ψ )个元为要素的η ( ψ ) + ζ (Ψ)维的基底向量设为 ν(ψ)=(θ ( ψ , i, I) · g2, ···, θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2) e 62η(ψ)+ζ (ψ)的情况下的基底向量Vi ( Ψ)的各要素θ ( ψ，i，β ) · &相应的值，通过规定的秘密分散方式，分别独立地秘密分散到 每个由H ( α )个分散管理装置PA ( α，1)，…，PA ( α，H(α ))构成的子集合SUB ( α )中，生成各要素θ ( ψ，i，β ) · g2相应的值的共享信息SH(ψ , i, β , α , h ( α )) (h ( α ) =1，...，H ( α ))。分散管理装置 PA ( α , h ( α ))相对于每个子集合SUB ( α )所共享的共同信息和共享信息SH ( Ψ，i，β，α , h ( α )) (h ( α )=1，…，H (α))，在每个子集合SUB (α)进行共同的共同运算，生成分散秘密值DSH (ψ,a，h ( α ))。取得装置使用与相同子集合SUB ( α )对应的多个分散秘密值DSH ( Ψ，a，h(α ))，通过每个根据所述秘密分散方式的子集合SUB ( α )的恢复处理，生成每个该子集合SUB ( α )的秘密恢复值SUBSK ( Ψ，α )，使用秘密恢复值SUBSK ( Ψ，α )，生成生成信息D*(Ψ )。在本发明中，在每个子集合SUB ( α )中独立地对秘密信息即基底向量( Ψ)进行秘密分散，使用每个子集合SUB ( α )所共享的共同信息，生成分散秘密值DSH ( Ψ，a，h(α ))。在该情况下，以子集合SUB ( α )为单位，能够正确地执行以分散秘密值DSH ( Ψ，α，h ( α ))为共享信息的恢复处理。共同信息在每个子集合SUB ( α )中共享，未在所有的分散管理装置PA ( a，h ( α ))中共享，因此，安全性高。发明效果如上，本发明能够安全地实现满足上述条件I 3的方式。
图1是用于说明第一实施方式的秘密分散系统的整体构成的方框图。图2是用于说明图1的分散装置的构成的方框图。图3A是用于说明第一实施方式的分散管理装置的构成的方框图，图3B是用于说明第一实施方式的共享值生成装置的构成的方框图。图4是用于说明第一实施方式的取得装置的构成的方框图。图5A是用于说明图2的秘密分散部的详情的方框图，图5B是用于说明图3A的分散秘密值生成部的详情的方框图。图6是用于说明图4的恢复部的详情的方框图。图7是用于说明第一实施方式的秘密分散处理的整体的图。图8A是用于示例第一实施方式的分散装置的处理的图，图SB是用于示例步骤S112的处理详情的图。图9A是用于示例第一实施方式的分散管理装置的处理的图，图9B是用于示例步骤S124的处理详情的图。图1OA是用于示例第一实施方式的取得装置的处理的图，图1OB是是用于示例步骤S134的处理的图。图1lA是用于说明第一实施方式的变形例I的秘密分散部的构成的图，图1lB是用于说明第一实施方式的变形例I的分散秘密值生成部的构成的图。图12A是用于说明第一实施方式的变形例2的分散秘密值生成部的构成的图，图12B是用于说明第一实施方式的变形例2的恢复部的构成的图。图13A是用于说明第一实施方式的变形例3的秘密分散部的构成的图，图13B是用于说明第一实施方式的变形例3的分散秘密值生成部的构成的图，图13C是用于说明第一实施方式的变形例3的恢复部的构成的图。图14A是用于说明第一实施方式的变形例4的秘密分散部的构成的图，图14B是用于说明第一实施方式的变形例4的分散秘密值生成部的构成的图，图14C是用于说明第一实施方式的变形例4的恢复部的构成的图。图15是示例表示标准型逻辑式的树结构数据的图。图16是示例表示标准型逻辑式的树结构数据的图。图17是用于说明第二实施方式的秘密分散系统的整体构成的方框图。
图18是用于说明第二实施方式的分散装置的构成的方框图。图19A是用于说明第二实施方式的共享值生成装置的构成的方框图，图19B是用于说明第二实施方式的共享值生成装置的构成的方框图。图20是是用于说明第二实施方式的分散管理装置的构成的方框图。图21是用于说明第二实施方式的取得装置的构成的方框图。图22是用于说明第二实施方式的秘密分散处理的整体的图。图23是用于说明第二实施方式的秘密分散处理的整体的图。
图24是用于示例第二实施方式的分散装置的处理的图。图25是用于示例第二实施方式的分散管理装置的处理的图。图26是用于示例第二实施方式的取得装置的处理的图。图27是用于示例第二实施方式的变形例I的分散管理装置的处理的图。图28是用于示例第二实施方式的变形例I的分散管理装置的处理的图。
具体实施例方式下面，参照附图对本发明的实施方式进行说明。〔第一实施方式〕首先，说明本发明的第一实施方式。〔定义〕定义本方式中使用的用语及记号。Fq=Fq表示位数q的有限域。位数q为I以上的整数，例如，将质数或质数的幂乘值设为位数q。即，有限域Fq的例子是质数域或将其作为基础域的扩展域。有限域Fq为质数域时的运算可通过例如以位数q为除数的余数运算容易地构成。有限域Fq为扩展域时的运算可通过例如以不可约多项式为除数的余数运算容易地构成。有限域Fq的具体的构成方法，例如公开于参考文献 I “IS0/IEC18033-2 information technoIogy-Securitytechniques-Encryption algorithms-Part2 Asymmetric ciphers，，。0F 0f表示有限域Fq的加法单位元。If 1f表示有限域Fq的乘法单位元。 E E表示在有限域Fq上定义的椭圆曲线。椭圆曲线E是包含由满足下面表示的仿射(affine)坐标上的Weierstrass方程式的χ, y e Fq构成的点(x,y)的集合和称为无限远点的特别的点O的集合。J2+Sl1 · χ · y+a3 · y=x3+a2 · x2+a4 · x+a6其中，满足a1; a2, a3, a4, a6 e Fq。对椭圆曲线E上的任意两点定义称为椭圆加算的二项运算+，对椭圆曲线E上的任意I点定义称为逆元运算的单项运算一。由椭圆曲线E上的有理点构成的有限集合关于椭圆加算而组成群、使用椭圆加算可定义称为椭圆标量倍算的运算及计算机上的椭圆加算等椭圆运算的具体的运算方法被众所周知(例如，参照参考文献1、参考文献2 “RFC5091 :1dentity-Based Cryptography Standard (IBCS) #1 Supersingular CurveImplementations of the BF and BBl Cryptosystems，，、参考文献 3 “ 彳了 · F · 7' 7m'入工卟 七口 7 ->，于4夕二卟· ρ · ζ —卜=著，“楕円曲線暗号”，出版=匕。Ty 'y ·工〒'工夕一夕 3 'y，ISBN4-89471-431-0” 等)。由椭圆曲线E上的有理点构成的有限集合具有位数ρ (ρ ^ I)的子群。例如，在将由椭圆曲线E上的有理点构成的有限集合的主要质数设为# E、将ρ设为除尽#E的大的质数的情况下，由椭圆曲线E的ρ等分点构成的有限集合E [ρ]构成由椭圆曲线E上的有理点构成的有限集合的子群。椭圆曲线E的ρ等分点意思是椭圆曲线E上的点A中，椭圆曲线E上的椭圆标量倍算值ρ · A满足ρ · A = O的点。G G表示巡回群。巡回群G的具体例是，由椭圆曲线E的ρ等分点构成的有限集·合E[p]、其子群、余数群等。在本方式中，用加法表示在巡回群G上定义的运算。S卩，对于
意思是对Ω e G1实施X次在巡回群G定义的运算，对Ω2 e G的e G意思是以Q1 e G和Ω2 e G为被运算符，进行在巡回群G定义的运算。g :g表示巡回群G的生成元。<整体构成>图1是用于说明第一实施方式的秘密分散系统的整体构成的方框图。如图1所不例,本方式的秘密分散系统I具有分散装置110、Σ α = ^h ( α )个分散管理装置〔PA(a，h(a))(a=l，···, L, L ^ 2,h ( a ) =1, ...，H(a)，H(a)芎 2)〕120 - a - h ( a )、取得装置130、共享值生成装置140 — I L，它们可以通过网络150进行通信。为了简化说明，在本方式中，示例各存在一个分散装置110及取得装置130的构成，但也可以存在两个以上的分散装置110及/或取得装置130。根据同样的理由，在本方式中，示例只存在一个由Σ a jh ( a )个分散管理装置〔PA ( a，h ( a ))〕120 — a — h(a )构成的集合的构成，但也可以存在多个这种集合。如图1所示例，由Sa=^h ( a )个分散管理装置〔PA ( a，h ( a ))) 120 — a —h ( a )构成的集合区分为由H ( a )个分散管理装置PA ( a，1)，…，PA ( a，H ( a ))构成的多个子集合SUB ( a )各个。生成各子集合SUB ( a )所共享的共享值σ ( a )的共享值生成装置140 - α分别与各子集合SUB ( a )对应。<分散装置110>图2是用于说明图1的分散装置110的构成的方框图。图5A是用于说明图2的秘密分散部114 一 α的详情的方框图。如图2所示例，本方式的分散装置110具有临时存储部111、存储部112、控制部113、秘密分散部114 一 a ( a =1,…,L)、发送部115。如图5A所不例,本方式的秘密分散部114 一 α具有函数选择部114a — α、索引生成部114b — α、分散处理部114c 一 α。本方式的分散装置110是,例如包含具备CPU (Central Processing Unit)、RAM(Random Access Memory)>ROM (Read-Only Memory)等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部111及存储部112是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部113及秘密分散部114 一 α ( α=1,…，L)是，例如通过CPU执行规定的程序而构成的处理部。控制部113及秘密分散部114 一 α ( α =1，…，L)的至少一部分也可以是特别的集成电路。发送部115是例如调制解调器、LAN (Local Area Network)卡等通信装置。
分散装置110在控制部113的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部111或存储部112。存储于临时存储部111或存储部112的数据根据需要取出，并输入于各处理部，而利用于该处理中。<分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α ) >图3Α是用于说明第一实施方式的分散管理装置〔PA ( α，h ( α ))〕120 — α -h ( α )的构成的方框图。图5B是用于说明图3A的分散秘密值生成部124 — α — h ( α )的详情的方框图。 如图3Α所示例,本方式的分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )具有临时存储部121 — α - h ( α )、存储部122 — α — h ( α )、控制部123 — α — h(α )、分散秘密值生成部124 — α — h ( α )、发送部125 — α — h ( α )、接收部126 —α - h ( α )0如图5Β所示例，分散秘密值生成部124 — a -h ( α )具有线性运算部124a — α — h ( α )和分散秘密值合成部124b — α — h ( α )。分散管理装置〔PA ( a，h ( α ))〕120 — α — h ( α )是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部121 -a -h ( α )及存储部122 — α — h ( α )是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部123 - α 一 h ( α )及分散秘密值生成部124 — α 一 h ( α )是例如通过CPU执行规定的程序而构成的处理部。另外，控制部123 — α — h ( α )及分散秘密值生成部124 — α — h(α )的至少一部分也可以是特别的集成电路。发送部125 — α — h ( α )及接收部126 —a -h (α)是例如调制解调器、LAN卡等通信装置。分散管理装置〔PA( α，h ( α ))〕120 — α — h ( α )在控制部 123 — α — h(α )的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部121 — α — h ( α )或存储部122 — α — h ( α )。存储于临时存储部121 — α —h ( α )或存储部122 — α — h ( α )的数据根据需要取出，并输入于各处理部，而利用于该处理中。<共享值生成装置140 — α >图3Β是用于说明第一实施方式的共享值生成装置140 - α的构成的方框图。如图3Β所示例，本方式的共享值生成装置140-α具有随机数生成部141-α及发送部142-α。本方式的共享值生成装置140-α是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置，但随机数生成部141 一 α也可以是特别的集成电路。<取得装置130 >图4是用于说明第一实施方式的取得装置130的构成的方框图。图6是用于说明图4的恢复部134 - α的详情的方框图。如图4所示例，本方式的取得装置13具有临时存储部131 ;存储部132 ;控制部133 ;恢复部134 — α ( α =1，…，L);合成部137 ;发送部135 ;接收部136。如图6所示例，恢复部134 - α具有系数算出部134a — α和多项式运算部134b — α。本方式的取得装置130是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部131及存储部132是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部133、恢复部134 — α ( α =1，…，L)及合成部137是例如通过CPU执行规定的程序而构成的处理部。控制部133、恢复部134 — α ( α =1，…，L)及合成部137的至少一部分也可以是特别的集成电路。发送部135和接收部136是例如调制解调器、LAN卡等通信装置。取得装置130在控制部133的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部131或存储部132。存储于临时存储部131或存储部132的数据根据需要读出，并输入于各处理部，而利用于该处理中。
<秘密分散处理>对本方式的秘密分散处理进行说明。[事前处理]作为本方式的秘密分散处理的事前处理，在分散装置110的存储部112中存储用于确定秘密信息Θ · g e G的信息Θ e F,。[秘密分散处理的整体]图7是用于说明第一实施方式的秘密分散处理的整体的图。下面，使用图7，对本方式的秘密分散处理的整体进行说明。在本方式中，首先，分散装置110 (图1)按各子集合SUB (α)独立地对秘密信息Θ · g e G进行秘密分散，生成共享信息SH ( α，h ( a )) (h ( a )=1,…，H ( α ))，输出该共享信息SH ( a，h ( α ))(步骤S11)。各共享信息SH ( a，h ( α ))分别经由网络150，分散发送到各分散管理装置〔PA ( a , h (α))〕120 — α — h ( α )。发送各共享信息SH ( α，h ( α ))的各分散管理装置〔PA ( α，h ( α ))〕120 —α - h ( α )分别使用该共享信息SH ( a，h ( α ))和包含子集合SUB ( α )所共享的共享值σ ( α )的共同信息，进行规定的共同运算，从而生成分散秘密值DSH (a, h (α ))，输出该分散秘密值DSH ( α，h ( α ))(步骤S12)。在本方式的情况下，在相互不同的子集合SUB ( α )中分别共享的共享值σ ( α )是相互独立的。属于相同子集合SUB ( α )的分散管理装置〔PA (a,h (a )))120- a -h (α)分别使用的“共同信息”相互相同。特别是，本方式中示例的“共同信息”包含共享值σ ( a )和由取得装置130提供的在所有的分散管理装置PA ( a，h ( a ))120 — a — h(a )中共同的提供信息V。属于相同子集合SUB ( a )的分散管理装置〔PA ( a，h ( a ))〕120 - a - h (a)分别进行的“共同运算”相互相同。在本方式中，设为所有的“共同运算”相同。本方式的“共同运算”是具有线性性的运算。从各分散管理装置〔PA ( a , h (a ))) 120 — a — h ( a )输出的各分散秘密值DSH (a,h (a ))分别经由网络150，发送到取得装置130。取得装置130使用与相同子集合SUB ( a )对应的多个分散秘密值DSH ( a，h ( a ))，通过每个子集合SUB ( a )的恢复处理，生成秘密恢复值SUBSK ( a )(步骤S13)。接着，取得装置130使用对各子集合SUB( a )分别生成的秘密恢复值SUBSK( a )，生成生成信息SK，并输出该生成信息SK(步骤S14)。另外，在本方式中，取得装置130对秘密恢复值SUBSK ( a )进行线性结合，生成信息SK。[分散装置的处理(步骤Sll)]
图8A是用于示例第一实施方式的分散装置的处理的图，图SB是用于示例步骤S112的处理的详情的图。下面，使用这些图，对分散装置110的处理的详情进行说明。首先，分散装置110 (图2)的控制部113设定α =1，并将该设定内容存储于临时存储部111 (步骤S111)。接着，从存储部112读出用于确定秘密信息Θ *geG的信息θ e Fq,并输入到秘密分散部114-α。秘密分散部114-α根据规定的秘密分散方式,使用信息Θ e Fq,对秘密信息Θ · g或信息Θ进行秘密分散,生成输出对于子集合SUB (α)的 H ( α )个共享信息 SH ( α，1)，…，SH ( α，H ( α ))(步骤 S112)。《步骤SI12的详情》本方式的秘密分散部114 一 α对各子集合SUB ( α )，使用(R ( α )，H ( α ))阈值秘密分散方式(其中，R (α)是满足2 = R (α)<Η ( α )的常数)，生成对秘密信息进行秘密分散而得到的共享信息SH ( α，h ( a )) (h ( α ) =1，…，H ( α ))。
如图SB所示例，首先，秘密分散部114 一 α (图5Α)的函数选择部114a — α随机选择f ( α，X) e Fq来输出对于预先确定的有限域Fq的元ω e Fq满足f ( α，ω) = θ的R ( α )-1次的多项式(步骤S112a)。另外，χ是由有限域Fq的元构成的变量，元ω e Fq的一个例子为Of。接着，索引生成部114b — α生成输出与各h ( α )=1，…，H ( α )对应的索引φ ( h (a)) EFq(步骤sil2b)。另外,在设为索引φ ( H ( a )) =h (a)EFq的情况下及在已经得到索引φ (h (a)) eFq的情况下，也可以省略步骤S112的处理。接着，分散处理部114c 一 α使用多项式f ( a，χ) e Fq和索引φ ( h ( a ) )￡ F,p
生成下面的共享信息SH ( a，h ( a )) (h ( a ) =1，…，H ( a ))。
SH ( a, h ( a )) = ((p ( h ( a )), f ( α, φ ( h ( a ))) -g￡G ) ... ( 5 )分散处理部114c — a输出共享信息SH ( a，h ( a ))(步骤S112c /《步骤S112的详情》的说明结束)。接着，控制部113判定存储于临时存储部111的α是否为L (步骤S113)。在此，在判定为不是a =L的情况下，控制部113将a +1设为新的α，将其设定内容存储在临时存储部111 (步骤S114)，并通过新的α执行步骤S112的处理。另一方面，在步骤S113中判定为a =L的情况下，从各秘密分散部114— α输出的各共享信息SH ( a , h ( a ))(a=l,…，L)发送到发送部115。发送部115分别经由网络150将各共享信息SH ( a，h(a )) ( a =1，…，L),发送到分散管理装置〔PA ( a，h ( α ))〕120 — a — h ( a ) ( a =1, ···,L)(步骤S115)。即，共享信息SH (1，I)发送到分散管理装置〔PA (1,1)) 120 — I — 1，共享信息SH (1，2)发送到分散管理装置〔PA (1,2)) 120 -1 - 2，…共享信息SH (L，H(L))发送到分散管理装置〔PA (L, H (L))) 120-L-H (L)0[共享值生成装置的处理]各共享值生成装置140 — α (图3B)生成在构成与自身对应的子集合SUB ( a )的各分散管理装置〔PA ( a，h ( a ))) 120 — a — h ( a )中共享的共享值σ ( α )。在本方式中，将随机数生成部141 - α生成的随机数设为共享值σ ( a )，发送部142 — α将共享值σ ( a )发送到构成子集合SUB ( a )的各分散管理装置〔PA ( a，h ( a ))) 120 -α — h ( α )。[分散管理装置的处理(步骤S12)]图9Α是用于示例第一实施方式的分散管理装置〔PA ( a，h ( α ))) 120 — α — h(α )的处理的图，图9Β是用于示例步骤S124的处理的详情的图。下面，使用这些图，对本方式的分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )的处理进行说明。首先，分散管理装置〔PA( a，h( α ))〕120 — α — h ( α )(图3Α)的接收部126 —α - h ( α )接收发送的共享信息SH ( α，h ( α ))，并将其存储在存储部122 — α — h(α )(步骤S121)。另外，如果过去执行步骤S121的处理，共享信息SH ( α，h ( α ))已经存储于分散管理装置〔PA ( a ,h ( a )))120 - α - h ( α )的存储部122 — α — h ( α )，则也可以省略步骤S121的处理。分散管理装置〔PA( α，h ( α ))〕120 — α — h ( α )的接收部 126 — α — h(α )接收从共享值生成装置140 - α发送的共享值σ ( α )，并将其存储于存储部122 —α — h ( α )(步骤 S122)。在本方式中，从取得装置130(图4)的存储部132读出的提供信息V经由网络150，从发送部135发送到各分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )。该提供信息V在所有的分散管理装置PA ( α，h ( α )) 120 — α — h ( α )中是共同的。提供信息V由分散管理装置〔PA ( a，h ( α ))〕120 — α — h ( α )(图3Α)的接收部126 — α — h(α )接收，并存储在存储部122 — α — h ( α )(步骤S123)。接着，分散秘密值生成部124 — α — h ( α )从存储部122 — α — h ( α )读入共享信息SH ( a，h ( α ))、共享值σ ( α )和提供信息V。分散秘密值生成部124 — α 一 h(α )使用包含共享值σ ( α )和提供信息V的共同信息、共享信息SH ( α，h ( α )),进行共同运算FNCl，生成分散秘密值DSH ( a，h ( α ))，并输出该分散秘密值DSH ( a，h ( α ))(步骤 S124)。《步骤S124的详情》属于相同子集合SUB ( α )的分散管理装置PA ( a，h ( α )) 120-a -h ( α )的分散秘密值生成部124 — α 一 h U )分别使用的共同信息是相互相同的，属于相同子集合SUB ( α )的分散管理装置PA ( a，h ( a ))120 — α — h ( α )的分散秘密值生成部124 —α 一 h (α)分别进行的共同运算是相互相同的。本方式的共享信息如式(5)所示。如图9Β所示例，首先，对本方式的分散秘密值生成部124 — α - h ( α )的线性运算部124a — α 一 h (α)，输入共享值σ ( α )、提供信息ν和共享信息SH ( a, h ( α )) = ( φ ( h ( α ) )，f α； φ ( h ( α ))) -g )的 f ( α，φ ( h ( α ))) -g,
线性运算部124a— α — h( α )进行下面的运算，并输出其运算结果dsh ( α, φ( h (α)))(步骤 S124a)。
dsh ( α, φ ( H ( α ))) =σ U/; ·ν· ( α, ο (H ( α ))) -g... ι 6 ;输出的运算结果 dsh (α，φ (h ( α)))输入于分散秘密值合成部124b —a - h (α)0对分散秘密值合成部124b — a -h ( α )，进一步输入共享信息SH ( CUh ( α)) = ( φ ( h (a)), f ( α, φ ( h ( α))) -g )的索引 φ ( h (α))，分散秘密值合成部124b - a -h ( α )通过下面的运算，生成分散秘密值DSH ( α，h ( α ))。
DSH ( a, h ( α)) = ( φ (h ( α )), dsh ( α, φ ( h ( α)))) ... (J )分散秘密值合成部124b — α — h ( α )输出分散秘密值DSH ( a，h ( α ))(步骤S124b /《步骤S124的详情》的说明结束)。生成的分散秘密值DSH (a,h (α))发送到发送部125 — α — h ( α )。发送部125 — a — h ( a )将分散秘密 值DSH ( a，h ( a ))经由网络150，发送到取得装置130 (步骤 S125)。[取得装置的处理(步骤S13、S14)]图1OA是用于示例第一实施方式的取得装置的处理的图，图1OB是用于示例步骤S134的处理的图。从各分散管理装置PA ( a , h ( a )) 120 — a — h ( a )发送的分散秘密值DSH(a，h (α))由取得装置130 (图4)的接收部136接收，并存储于存储部132 (步骤S131)。接着，控制部133判定在存储部132中是否存储有需要数以上的分散秘密值DSH(a，h ( a ))(步骤S132)。在本方式的情况下，对各a =1，…，L，分别判定在存储部132中是否存储有不同的R ( a ) (2 ^ R ( a X H ( a ))个以上的分散秘密值DSH ( a，h ( α ))。在此，在判定为在存储部132中未存储有需要数以上的分散秘密值DSH ( a , h ( a ))的情况下，返回步骤S131的处理。另一方面，在判定为在存储部132中存储有需要数以上的分散秘密值DSH ( a，h ( a ))的情况下，控制部133设定为a =1，并将其设定内容存储于临时存储部131 (步骤S133)。接着，从存储部132读出与子集合SUB( a )对应的需要数量的分散秘密值DSH( a，h ( a )),并输入到恢复部134 — α中。恢复部134 — α使用输入的分散秘密值DSH ( a，h ( a ))，通过根据在上述步骤S112中使用的秘密分散方式的每个子集合SUB ( a )的恢复处理，生成秘密恢复值SUBSK ( a )，并输出该每个子集合SUB ( a )的秘密恢复值SUBSK(a )(步骤 S134)。《步骤S134的详情》本方式的分散秘密值DSH ( a，h ( a ))如式(7)所示。对恢复部134 — α (图6)对于每个α各输入R ( a )个不同的分散秘密值DSH ( a，h ( α ))。下面中，如下表示与输入于恢复部134 — α的各α对应的分散秘密值DSH ( a，h ( α ))。
DSH ( α，φι ( a )) = ( φι ( a ), dshι ( a)))
… ...(8 )
DSH ( a.，Oi )( )) = ( (pR i u ι ( a .)，dsliR ；■ u) ( a))其中，满足下面。
(φι ( a), ..., 9r(α) ( a)) □ ( φ ( I ), ···， φ (H ( a))) ... ( 9 )( dsh ι ( a), dshR:u) ( a )) □ ( dsh ( α, φ ( I ) )，} dsh ( a·,
权利要求
1.一种秘密分散系统,其中，具有 分散装置；Σ α = A ( α )个分散管理装置PA ( a，h ( a )) ( α =1，…，L, L兰2, h(α ) =1，…，H ( α )，H ( α )芎 2);取得装置， 所述分散装置包含如下秘密分散部，即， 将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，…，Ψ、将η ( Ψ)设为I以上的整数、将ζ ( Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于Θ ( ψ , i, β ) (i=l, ...，η(ψ) + ζ (ψ)，β=1， ···, η ( ψ ) + ζ ( ψ ), η ( ψ ) ^ I, ζ(ψ)兰I)的所述巡回群G2的11 ( Ψ) + ζ ( Ψ)个元为要素的η ( Ψ)+ ζ (Ψ)维的基底向量设为 ( ψ ) = ( θ ( ψ , i, I) · g2, ···, θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2) e 62η(ψ)+ζ(Ψ)的情况下，将与所述基底向量b# ( Ψ)的各要素Θ ( ψ，i，β ) · g2相应的值通过规定的秘密分散方式，分别独立地秘密分散到每个由H (α)个分散管理装置PA (α,Ι),…，PA ( α ,H ( α ))构成的子集合SUB ( α )中，生成与各要素θ ( ψ, , β ) · g2相应的值的共享信息 SH ( V，i，β，a，h ( a )) (h ( α )=1，...，Η ( α ))， 所述分散管理装置PA ( α，h ( α ))包含如下分散秘密值生成部，即， 对按每个所述子集合SUB ( α )所共享的共同信息和所述共享信息SH ( Ψ，i，β，α，h ( α (h ( α )=1,…，H ( α ))，按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH ( Ψ , α，h ( α ))， 所述取得装置包含 使用与相同的所述子集合SUB ( α )对应的多个所述分散秘密值DSH ( ψ，a，h ( α ))，通过根据所述秘密分散方式的每个子集合SUB ( α )的恢复处理，生成每个该子集合SUB(α )的秘密恢复值SUBSK ( Ψ，α )的恢复部；以及 使用所述秘密恢复值SUBSK ( Ψ，α )，生成生成信息D* ( Ψ )的合成部。
2.如权利要求1的秘密分散系统，其中， 在相互不同的所述子集合SUB ( α )分别共享的所述共同信息是相互独立的。
3.如权利要求1的秘密分散系统，其中， 所述共同运算是具有线性性的运算。
4.如权利要求2的秘密分散系统，其中， 所述共同运算是具有线性性的运算。
5.如权利要求1的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D*(Ψ )。
6.如权利要求2的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α )进行线性结合，生成所述生成信息D*(Ψ )。
7.如权利要求3的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D*(Ψ )。
8.如权利要求4的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α )进行线性结合，生成所述生成信息D*(Ψ )。
9.如权利要求1 8中任一项所述的秘密分散系统，其中， 与所述基底向量匕* ( Ψ)的各要素θ ( Ψ，i，β ) · g2相应的值为Θ ( ψ, i, β ),所述共同信息包含将λ设为I以上Ψ下面的整数λ=1，…，Ψ的情况下的coef I(O, a ), coef ( λ , α ), coef ι ( λ , α ), SE ( α ), share ( λ , α ), 作为与ν=ο对应的所述分散秘密值，所述分散秘密值生成部生成设为 SHbi* (O, α，h ( a )) = (SH (0，i，1，α，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的 DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) · g2+Z t = ^coefl (O, α ) · SHbl* (O, α，h(α )) · g2， 另外，作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α，h ( α )))，并将V ( λ ) —(V1 ( λ )，-, νη(λ) ( λ ))设为η ( λ )维向量的情况下的DSH ( λ，α，h ( α )) =(share ( λ，α ) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) · g2 + Σ =2η ( λ ) coef ( λ , α ) · V, (λ)· SHb , * (λ, a , h ( α )) · g2 + Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 或， DSH ( λ，a，h ( a ))=Share ( λ，α ) · Σ l=1nU)vt ( λ ) · SHb1* ( λ，α，h ( α )) · g2+Z ι=η ⑴+1η ⑴+ ζu) Coefl (λ,α)· SHb , * (λ, a,h (a))*g2。
10.如权利要求1 8中任一项所述的秘密分散系统，其中， 与所述基底向量匕* (Ψ)的各要素Θ (V，i，β)·&相应的值为θ (ψ, , β)·δ2,所述共同信息包含将λ设为I以上Ψ下面的整数λ=1，…，Ψ的情况下的coef I(O, a ), coef ( λ , a ), coef ι ( λ , a ), SE ( a ), share ( λ , α ), 作为与ν=ο对应的所述分散秘密值，所述分散秘密值生成部生成设为 SHbi* (O, α，h ( a )) = (SH (0，i，1，α，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的 DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) +Σ ^21Coefl (O, α ) · SHb , * (O, α，h ( α ))，另外，作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α，h ( α )))， 并将V (λ)-= (Vl (λ(λ))设为η (λ)维向量的情况下的 DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) + Σ , = 2η ( λ ) coef (λ,α)”，(λ)· SHb , * (λ, a,h ( α ))+ Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α ))或，DSH ( λ，α，h ( α ))=Share ( λ，α ) · Σ , =1η (λ)ν, ( λ ) · SHb1* ( λ，α，h ( α ))+Σ , =η (λ)+1η (λ) + ζ (λ)coef, (λ,α)· SHb , * (λ, a,h (α))。
11.如权利要求9的秘密分散系统，其中， 作为与Ψ=0对应的所述秘密恢复值，所述恢复部生成SUBSK (O, a ) =-SE ( a ) · b# (0) +Σ ^21Coefl (0，a ) · bt* (0)， 作为与各λ对应的所述秘密恢复值，生成 SUBSK ( λ，a ) = (share ( λ，α ) +coef (λ，(λ))· Id1* ( λ ) + Σ , =2η ( λ ) coef (λ,α)”，(A)^bl* (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (A)0
12.如权利要求10的秘密分散系统，其中， 作为与Ψ=0对应的所述秘密恢复值，所述恢复部生成SUBSK (O, a ) =-SE ( a ) · b# (0) +Σ ^21Coefl (0，a ) · bt* (0)， 作为与各λ对应的所述秘密恢复值，生成SUBSK (入，a ) = (share (λ,α) +coef (入，α ) · V1 (入))· Id1* (入)+ Σ t =2n ( λ ) coef ( λ , α ) · V t ( λ ) · h ^ (λ)+ Σ, .nU)+1n(A) + 5(A)coefl (λ, α)+* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ )+ Σ, .η(λ)+1η(λ) + ζ U)coeft (λ, a).b丨* (A)0
13.一种分散装置，将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，…，Ψ、将η (HO设为I以上的整数、将ζ (Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 θ ( Ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1,…，η(ψ) + ζ ( ψ ), η(Ψ )= I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ )+ζ ( Ψ )个元为要素的η ( ψ )+ζ (ψ)维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2)eG2n(v)〃(ν)的情况下，将与所述基底向量(HO的各要素θ (ψ, , β)·&相应的值通过规定的秘密分散方式分别独立地秘密分散到每个由H( a )( a=l,...,L, L = 2,h(a)=1，···，Η(α)，Η(α) ^ 2)个分散管理装置PA ( α,Ι),…，PA ( a ,H ( a ))构成的子集合SUB ( a )中，生成与各要素Θ ( ψ, , β ) · g2相应的值的共享信息SH ( Ψ，i，β，a，h ( a )) (h ( a ) =1,…，H ( a ))。
14.一种分散管理装置，其对按H ( a ) ( a=l，…，L，L兰2，h ( a ) =1，...，H(a)，H ( a ) ^ 2)个分散管理装置PA (α,Ι),…，PA ( a，H ( a ))构成的每个子集合SUB(a )所共享的共同信息、以及将Ψ设为I以上的整数、将V设为O以上Ψ以下的整数Ψ=0,…，Ψ、将η (Ψ)设为I以上的整数、将ζ (HO设为O以上的整数、将所述巡回群G2 的生成元设为 g2、将以相对于 Θ ( Ψ，i，β ) (i=l，…，η ( ψ ) + ζ ( Ψ ), β =1, ···, η(ψ) + ζ ( ψ ), η ( ψ ) ^ I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ ) + ζ ( Ψ )个元为要素的 η ( ψ ) + ζ ( ψ )维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η(Ψ) + ζ (￥))*g2) e 62η(ψ)+ζ 的情况下的、将与所述基底向量(Ψ)的各要素Θ(Ψ, , β )*g2相应的值分别独立地秘密分散到每个所述子集合SUB ( α )中而得到的与各要素Θ ( Ψ，i，β ) · g2相应的值的共享信息SH ( Ψ , i, β , α，h ( α )) (h ( α ) =1，…，H ( α ))，按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH (ψ,α,h ( α ))。
15.一种取得装置，其具有 恢复部，其使用将Ψ设为I以上的整数，将Ψ设为O以上Ψ下面的整数Ψ=0，…，Ψ，将由 H ( α ) ( α=1, ...，L，L 芎 2，h ( a )=1, -,H ( α )，H ( α )芎 2)个分散管理装置PA ( α，1)，…，PA ( α ,H ( α ))构成的子集合设为SUB ( α )的情况下的与相同的所述子集合SUB ( α )对应的多个所述分散秘密值DSH ( Ψ，α，h ( α ))，通过根据规定的秘密分散方式的每个子集合SUB ( α )的恢复处理，生成每个该子集合SUB ( α )的秘密恢复值SUBSK ( Ψ，α )；以及 合成部，其使用所述秘密恢复值SUBSK (Ψ，α)，生成生成信息D* (Ψ)。
16.一种秘密分散方法，通过分散装置、Σ ( α )个分散管理装置PA ( a，h ( α ))(α=1，…，L，L芎2，h ( α )=1，…，H ( α )，H ( α )芎2)和取得装置进行，其具有 (A)所述分散装置将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，···，Ψ、将η (HO设为I以上的整数、将ζ (Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 θ ( Ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1,…，η(ψ) + ζ ( ψ ), η(Ψ )= I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ )+ζ ( Ψ )个元为要素的η ( ψ )+ζ (ψ)维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2)eG2n(v)+“v)的情况下，将与所述基底向量(HO的各要素Θ (V，i，3)*&相应的值按照规定的秘密分散方式分别独立地秘密分散到每个由H ( α )个分散管理装置PA ( α，1)，-,PA ( α , H ( α ))构成的子集合SUB (α)中，生成与各要素Θ (v，i，@)*&相应的值的共享信息SH ( V，i，β，a，h ( a )) (h ( α )=1，…，H ( α ))的步骤； (B)所述分散管理装置PA( a，h ( α ))对按每个所述子集合SUB ( α )所共享的共同信息和所述共享信息SH ( Ψ , , β , a , h ( α )) (h ( α ) =1，…，H ( α )),按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH ( Ψ，α，h ( α ))的步骤； (C)所述取得装置使用相同的所述子集合SUB( α )所对应的多个所述分散秘密值DSH(Ψ, a,h (α ))，通过按照所述秘密分散方式的每个子集合SUB ( a )的恢复处理，生成每个该子集合SUB ( a )的秘密恢复值SUBSK ( Ψ，a )的步骤；以及 (D)所述取得装置使用所述秘密恢复值SUBSK( Ψ，a )，生成生成信息D* ( Ψ )的步骤。
17.如权利要求16的秘密分散方法，其中， 在相互不同的所述子集合SUB ( a )中分别共享的所述共同信息是相互独立的。
18.如权利要求16的秘密分散方法，其中， 所述共同运算是具有线性性的运算。
19.如权利要求17的秘密分散方法，其中，所述共同运算是具有线性性的运算。
20.如权利要求16的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
21.如权利要求17的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
22.如权利要求18的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
23.如权利要求19的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
24.如权利要求16 23中任一项所述的秘密分散方法，其中， 与所述基底向量\* ( Ψ)的各要素θ ( Ψ，i，β ) · g2相应的值为Θ ( ψ, i, β ),所述共同信息包含将λ设为I以上Ψ下面的整数入=1，…，Ψ的情况下的coef ι(O, a ), coef ( λ , α ), coef ι ( λ , α ), SE ( α ), share ( λ , α ), 所述步骤(B)包含 (B-1)作为与Ψ=0对应的所述分散秘密值，生成设为SHbi* (O, a，h ( a ))= (SH (O,i，l，a，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的DSH (0，α，h ( α ))=-SE ( α VSHb1* (0，α，h ( α )).g2+Z ^21Coefl (0，α ).SHbt * (0，α，h ( α )).g2的步骤；以及 (B-2)作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α ,h (α)))，并将V (λ)—= (Vl (λ)，…，νη(；0(λ))设为η (λ)维向量的情况下的DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) · g2 + Σ =2η ( λ ) coef ( λ , α ) · V, (λ)· SHb , * (λ, a , h ( α )) · g2 + Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 或， DSH ( λ，a，h ( a )) =share(λ)· SHb1* (λ, a,h ( α )) · g2+ Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 的步骤。
25.如权利要求16 23中任一项所述的秘密分散方法，其中， 与所述基底向量匕* (Ψ)的各要素Θ (V，i，β)·&相应的值为θ (ψ, , β)·δ2,所述共同信息包含将λ设为I以上Ψ下面的整数入=1，…，Ψ的情况下的coef ι(O, a ), coef ( λ , a ), coef ι ( λ , a ), SE ( a ), share ( λ , α ), 所述步骤(B)包含(B-1)作为与Ψ =O对应的所述分散秘密值，生成设为SHbi* (O, a，h ( a ))= (SH (O,i，l，a，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) +Σ ^21Coefl (O, α ) · SHb , * (O, α，h ( α ))的步骤；以及 (Β-2)作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，α，h ( a )) = (SH(λ , ,Ι, α , h ( α )), ···, SH ( λ , , η (λ) + ζ (λ), α , h ( α ))),并将 ν ( λ ) — (Vi(λ)，…，νη(λ)(λ))设为η (λ)维向量的情况下的， DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) + Σ , = 2η ( λ ) coef (λ,α)”，(λ)· SHb , * (λ, a,h ( α ))+ Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) 或， DSH ( λ，a，h ( α )) =share(λ)· SHb1* (λ, a,h ( α ))+ Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α ))的步骤。
26.如权利要求24的秘密分散方法，其中， 所述步骤(C)包含 (C-1)作为与Ψ=0对应的所述秘密恢复值，生成SUBSK (O, a ) =-SE ( a ) · (O)+ Σ ^21Coefl (0，a ) · b，(O)的步骤；以及 (C-2)作为与各λ对应的所述秘密恢复值，生成SUBSK ( λ，a )= (share (λ,α)+coef (入，α ) · V1 (入))· Id1* (入)+ Σ ι=2η (入)coef ( λ , α ) · V t ( λ ) · h ^ (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + st.nU)+1nU)+5 uWfl (λ，O.b丨* (λ)的步骤。
27.如权利要求25的秘密分散方法，其中， 所述步骤(C)包含 (C-1)作为与Ψ=0对应的所述秘密恢复值，生成SUBSK (O, a ) =-SE ( α ) · (O)+ Σ ^21Coefl (0，α ) · b，(O)的步骤；以及 (C-2)作为与各λ对应的所述秘密恢复值，生成SUBSK ( λ，a )= (share (λ,α)+coef (入，α ) · V1 (入))· Id1* (入)+ Σ ι=2η (入)coef ( λ , α ) · V t ( λ ) · h ^ (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + st.nU)+1nU)+5 uWfl (λ，O.b丨* (λ)的步骤。
28.—种程序，用于使计算机作为权利要求13的分散装置而发挥作用。
29.—种程序，用于使计算机作为权利要求14的分散管理装置而发挥作用。
30.一种程序，用于使计算机作为权利要求15的取得装置而发挥作用。
31.一种计算机可读取的记录介质，其存储了用于使计算机作为权利要求13的分散装置而发挥作用的的程序。
32.—种计算机可读取的记录介质，其存储了用于使计算机作为权利要求14的分散管理装置而发挥作用的的程序。
33.一种计算机可读取的记录介质，其存储了用于使计算机作为权利要求15的取得装置而发挥作用的的程序。
全文摘要
分散装置将与基底向量bi*(ψ)的各要素θ(ψ，i，β)·g2相应的值分别独立地秘密分散到由H(α)个分散管理装置PA(α，1)，…，PA(α，H(α))构成的每个子集合SUB(α)中，生成与各要素θ(ψ，i，β)·g2相应的值的共享信息SH(ψ，i，β，α，h(α))。分散管理装置PA(α，h(α))对按每个子集合SUB(α)所共享的共同信息和共享信息SH(ψ，i，β，α，h(α))，进行按每个子集合SUB(α)的共同运算，生成分散秘密值DSH(ψ，α，h(α))。取得装置通过每个子集合SUB(α)的恢复处理，生成秘密恢复值SUBSK(ψ，α)，使用秘密恢复值SUBSK(ψ，α)，生成生成信息D*(ψ)。
文档编号G09C1/00GK103003857SQ20118003531
公开日2013年3月27日 申请日期2011年7月22日 优先权日2010年7月23日
发明者西卷陵, 铃木幸太郎 申请人:日本电信电话株式会社
技术领域：
本发明涉及秘密分散技术。
背景技术：
在保管秘密信息的情况下，有秘密信息的丢失或破坏的危险和被盗的危险。丢失或破坏的危险可通过事先保管多个秘密信息来降低。但是，在该情况下，被盗的危险增加。作为同时解决这些危险的方法之一，具有秘密分散法(SSS :Secret Sharing Scheme)(例如，参照非专利文献1、2)。秘密分散法是如下方式，S卩，利用秘密信息MSK生成多个共享信息SH (I),…，SH(N)，并使这些信息分散到多个分散管理装置PA (I),…，PA (N)中而进行管理，并且，仅在 能够得到这些共享信息SH (I),…，SH (N)中规定数以上的共享信息的情况下，可恢复秘密信息MSK。下面,表不秘密分散法代表性的方式。(N, N)阈值秘密分散方式在(N，N)阈值秘密分散方式(有时也称为“N-out-of-N分散方式”或“N-out_of-N阈值分散方式”))中，只要提供所有的共享信息SH (I),…,SH (N),就可恢复秘密信息MSK,但即使提供任意N-1个共享信息SH (φιSH ( ((Jn.!)，也不能完全得到秘密信息MSK的信息。下面，表不(N, N)阈值秘密分散方式的一个例子。·随机选择 SH1,…，SH1^1。·进行 SHn=MSK- (SH1+…+SHim)的计算。·使各共享信息SH1,…，SHn分散到多个管理装置PA (I),…，PA (N)中而进行管理。·只要提供所有的共享信息SH1,…，SHn,就可通过+SHn的恢复处理，恢复秘密信息MSK。另外，用于从共享信息SH1,…，SHdii密信息MSK的运算MSK=SH1+…+SHn是线性的。因此，在以各共享信息SH (I),…，SH (N)和值σ为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SH’ (I),…，SH’(N)，进行恢复处理的情况下，得到以秘密信息MSK和值σ为被运算符进行该线性运算CALC的结果。例如，在以SH’
(1)= σ -SH (I),.. ,SH' (Ν) = σ *SH (N)为各共享信息 SH’ (I),…，SH’(N)执行恢复处理的情况下，得到下面的值。O · SH (1)+... + 0 · SH (N)=σ · (SH (I) +...+SH (N))=σ . MSK... (I)另一方面，在以各共享信息SH (I),…，SH (N)和相互独立的值σ (1)，…，σ(N)为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SH’Cl),…，SH’(N)，执行恢复处理的情况下，通常，不能得到以秘密信息MSK为被运算符的运算结果。例如，在以 SH’ (1) = σ (I) · SH (1)，· ·，SH’ (Ν) = σ (N) · SH (N)为各共享信息SH’ (I),…，SH’(N)，执行恢复处理的情况下，得到下面的值。σ (I) · SH (1)+— + σ (N) · SH (N)…(2)(Kt, N)阈值秘密分散方式在(Kt，N)阈值秘密分散方式(有时也称为“Kt-out_of-N分散方式”或“Kt-0Ut-0f-N阈值分散方式”)中，只要提供任意不同的Kt个共享信息SH (φι),…，SH ((pKt)，就可恢复秘密信息MSK ，但即使提供任意Kt-1个共享信息SH (φι), SH ( φΚΜ ),也不能完全得到秘密信息MSK的信息。下标的Kt表示Kt。下面，表不(Kt, N)阈值秘密分散方式的一个例子。·随机挑选满足 f (O)=MSK 的 Kt-1 次的多项式 f (χ) = ξ0+ξ1 * χ+ξ2 * χ2+···+ ξΚΗ · χΚΗ。即，设为Ici=MSK,随机挑选ξ1；…，ξΚΗ。将共享信息设为SHp= ( P , f(P )) ( P =1,…，N)。 在得到任意不同的Kt个共享信息SHitp1),…，SH(<pKt) ((Cp1, ···, <pKt)C ( I, N))的情况下，例如，使用拉格朗日(Lagrange)内插公式，通过下面那样的恢复处理，可恢复秘密信息MSK。
MSK=f ( O ) =λι· ( φι) +.·.+λο' ((ptct)... ( 3 )[数I]
P
(χ-^,)···ν···(χ-^κ ),.、
1 Ρ1 ^Fq …(4)
ΚΦ -病)··.▽··’(#,,-么丨)另外，意思是不存在从开头到第P个被运算符〔分母的要素(φρ-φρ),分子
的要素(χ-φΡ)〕。即，式(4)的分母如下。
((Pp-(P1) .··.· ( φρ-φρ-1) · ( φΡ-φΡ+ι) ··.·· ( φΡ-φΚι)式(4)的分子如下。
(X-(Pl) ·.·■· ( X-Cpp-1 ) · ( X-ψρ+ι ) ·...· ( X-CpKt )它们的关系即使在域上也成立。式(3)的运算是线性的。因此，以各共享信息SH ((pi )，…，SH ((pKt)和值σ为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息SFT(Cp1), SH' (φΚ )恢复的值与以秘密信息MSK和值。为被运算符进行线性运算CALC的结果相等。另一方面，在以各共享信息SH( Φ!)，…，SH (φκι)和相互独立的值σ ( φι), ..., σ (cpKt)为被运算符，且将每个共享信息进行相同线性运算CALC的结果作为各共享信息φι )，…，SH' (φκι),执行恢复处理的情况下，通常，不能得到以秘密信息MSK为被运算符的运算结果。
现有技术文献非专利文献非专利文献1:黑泽馨、尾形t力、(S、“現代暗号O基礎数理(電子情報通信 > 夕千弋 V 'J 一文')，，、；！口 f 社、2004 年 3 月、p. 116-119非专利文献2 :A. Shamir, 〃How to Share a Secret", Communications of theACM，Novemberl979, Volume22，NumberlI, pp. 612-613.
发明内容
发明要解决的课题假定满足下面的条件的方式。(条件I)分散装置对秘密信息MSK进行秘密分散，生成多个共享信息SH(I),…，SH (N)，并将这些共享信息分散到多个分散管理装置PA (I),…，PA (N)中而进行管理。(条件2)各分散管理装置PA(1)，…，PA (N)分别执行一些运算。(条件3)取得装置虽然不能得到秘密信息MSK，但在提供由规定数以上的分散管理装置生成的运算结果的情况下，能够得到与被运算符中包含秘密信息MSK和任意值σ的运算结果对应的生成信息。但是，实现这种方式是不容易的。即，若各分散管理装置PA (I),…，PA (N)分别使用相互独立的值σ (1)，…，σ (N)执行运算的话，取得装置不能正确地执行以各分散管理装置的运算结果为共享信息的恢复处理，得不到希望的生成信息。另一方面，值σ可以成为用于推测生成信息的信息，因此所有的分散管理装置PA (I),…，PA (N)共享值σ其本身，从安全性的观点来看，不优选。本发明就是鉴于这种点而提出的，其目的在于，安全地实现满足上述条件I 3的方式。用于解决课题的手段在本发明中，通过分散装置、Σα=> (α)个分散管理装置PA ( a , h ( α ))(α=1，…，L，L芎2，h ( α )=1，…，H ( α )，Η ( α )芎2)和取得装置，执行秘密分散处理。分散装置将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，···，Ψ4^η(Ψ)设为I以上的整数、将ζ ( Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 Θ ( ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1, ···, η ( ψ ) + ζ (ψ),η(ψ)芎 I,ζ ( ψ )兰I)的巡回群G2的η ( ψ ) + ζ ( Ψ )个元为要素的η ( ψ ) + ζ (Ψ)维的基底向量设为 ν(ψ)=(θ ( ψ , i, I) · g2, ···, θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2) e 62η(ψ)+ζ (ψ)的情况下的基底向量Vi ( Ψ)的各要素θ ( ψ，i，β ) · &相应的值，通过规定的秘密分散方式，分别独立地秘密分散到 每个由H ( α )个分散管理装置PA ( α，1)，…，PA ( α，H(α ))构成的子集合SUB ( α )中，生成各要素θ ( ψ，i，β ) · g2相应的值的共享信息SH(ψ , i, β , α , h ( α )) (h ( α ) =1，...，H ( α ))。分散管理装置 PA ( α , h ( α ))相对于每个子集合SUB ( α )所共享的共同信息和共享信息SH ( Ψ，i，β，α , h ( α )) (h ( α )=1，…，H (α))，在每个子集合SUB (α)进行共同的共同运算，生成分散秘密值DSH (ψ,a，h ( α ))。取得装置使用与相同子集合SUB ( α )对应的多个分散秘密值DSH ( Ψ，a，h(α ))，通过每个根据所述秘密分散方式的子集合SUB ( α )的恢复处理，生成每个该子集合SUB ( α )的秘密恢复值SUBSK ( Ψ，α )，使用秘密恢复值SUBSK ( Ψ，α )，生成生成信息D*(Ψ )。在本发明中，在每个子集合SUB ( α )中独立地对秘密信息即基底向量( Ψ)进行秘密分散，使用每个子集合SUB ( α )所共享的共同信息，生成分散秘密值DSH ( Ψ，a，h(α ))。在该情况下，以子集合SUB ( α )为单位，能够正确地执行以分散秘密值DSH ( Ψ，α，h ( α ))为共享信息的恢复处理。共同信息在每个子集合SUB ( α )中共享，未在所有的分散管理装置PA ( a，h ( α ))中共享，因此，安全性高。发明效果如上，本发明能够安全地实现满足上述条件I 3的方式。
图1是用于说明第一实施方式的秘密分散系统的整体构成的方框图。图2是用于说明图1的分散装置的构成的方框图。图3A是用于说明第一实施方式的分散管理装置的构成的方框图，图3B是用于说明第一实施方式的共享值生成装置的构成的方框图。图4是用于说明第一实施方式的取得装置的构成的方框图。图5A是用于说明图2的秘密分散部的详情的方框图，图5B是用于说明图3A的分散秘密值生成部的详情的方框图。图6是用于说明图4的恢复部的详情的方框图。图7是用于说明第一实施方式的秘密分散处理的整体的图。图8A是用于示例第一实施方式的分散装置的处理的图，图SB是用于示例步骤S112的处理详情的图。图9A是用于示例第一实施方式的分散管理装置的处理的图，图9B是用于示例步骤S124的处理详情的图。图1OA是用于示例第一实施方式的取得装置的处理的图，图1OB是是用于示例步骤S134的处理的图。图1lA是用于说明第一实施方式的变形例I的秘密分散部的构成的图，图1lB是用于说明第一实施方式的变形例I的分散秘密值生成部的构成的图。图12A是用于说明第一实施方式的变形例2的分散秘密值生成部的构成的图，图12B是用于说明第一实施方式的变形例2的恢复部的构成的图。图13A是用于说明第一实施方式的变形例3的秘密分散部的构成的图，图13B是用于说明第一实施方式的变形例3的分散秘密值生成部的构成的图，图13C是用于说明第一实施方式的变形例3的恢复部的构成的图。图14A是用于说明第一实施方式的变形例4的秘密分散部的构成的图，图14B是用于说明第一实施方式的变形例4的分散秘密值生成部的构成的图，图14C是用于说明第一实施方式的变形例4的恢复部的构成的图。图15是示例表示标准型逻辑式的树结构数据的图。图16是示例表示标准型逻辑式的树结构数据的图。图17是用于说明第二实施方式的秘密分散系统的整体构成的方框图。
图18是用于说明第二实施方式的分散装置的构成的方框图。图19A是用于说明第二实施方式的共享值生成装置的构成的方框图，图19B是用于说明第二实施方式的共享值生成装置的构成的方框图。图20是是用于说明第二实施方式的分散管理装置的构成的方框图。图21是用于说明第二实施方式的取得装置的构成的方框图。图22是用于说明第二实施方式的秘密分散处理的整体的图。图23是用于说明第二实施方式的秘密分散处理的整体的图。
图24是用于示例第二实施方式的分散装置的处理的图。图25是用于示例第二实施方式的分散管理装置的处理的图。图26是用于示例第二实施方式的取得装置的处理的图。图27是用于示例第二实施方式的变形例I的分散管理装置的处理的图。图28是用于示例第二实施方式的变形例I的分散管理装置的处理的图。
具体实施例方式下面，参照附图对本发明的实施方式进行说明。〔第一实施方式〕首先，说明本发明的第一实施方式。〔定义〕定义本方式中使用的用语及记号。Fq=Fq表示位数q的有限域。位数q为I以上的整数，例如，将质数或质数的幂乘值设为位数q。即，有限域Fq的例子是质数域或将其作为基础域的扩展域。有限域Fq为质数域时的运算可通过例如以位数q为除数的余数运算容易地构成。有限域Fq为扩展域时的运算可通过例如以不可约多项式为除数的余数运算容易地构成。有限域Fq的具体的构成方法，例如公开于参考文献 I “IS0/IEC18033-2 information technoIogy-Securitytechniques-Encryption algorithms-Part2 Asymmetric ciphers，，。0F 0f表示有限域Fq的加法单位元。If 1f表示有限域Fq的乘法单位元。 E E表示在有限域Fq上定义的椭圆曲线。椭圆曲线E是包含由满足下面表示的仿射(affine)坐标上的Weierstrass方程式的χ, y e Fq构成的点(x,y)的集合和称为无限远点的特别的点O的集合。J2+Sl1 · χ · y+a3 · y=x3+a2 · x2+a4 · x+a6其中，满足a1; a2, a3, a4, a6 e Fq。对椭圆曲线E上的任意两点定义称为椭圆加算的二项运算+，对椭圆曲线E上的任意I点定义称为逆元运算的单项运算一。由椭圆曲线E上的有理点构成的有限集合关于椭圆加算而组成群、使用椭圆加算可定义称为椭圆标量倍算的运算及计算机上的椭圆加算等椭圆运算的具体的运算方法被众所周知(例如，参照参考文献1、参考文献2 “RFC5091 :1dentity-Based Cryptography Standard (IBCS) #1 Supersingular CurveImplementations of the BF and BBl Cryptosystems，，、参考文献 3 “ 彳了 · F · 7' 7m'入工卟 七口 7 ->，于4夕二卟· ρ · ζ —卜=著，“楕円曲線暗号”，出版=匕。Ty 'y ·工〒'工夕一夕 3 'y，ISBN4-89471-431-0” 等)。由椭圆曲线E上的有理点构成的有限集合具有位数ρ (ρ ^ I)的子群。例如，在将由椭圆曲线E上的有理点构成的有限集合的主要质数设为# E、将ρ设为除尽#E的大的质数的情况下，由椭圆曲线E的ρ等分点构成的有限集合E [ρ]构成由椭圆曲线E上的有理点构成的有限集合的子群。椭圆曲线E的ρ等分点意思是椭圆曲线E上的点A中，椭圆曲线E上的椭圆标量倍算值ρ · A满足ρ · A = O的点。G G表示巡回群。巡回群G的具体例是，由椭圆曲线E的ρ等分点构成的有限集·合E[p]、其子群、余数群等。在本方式中，用加法表示在巡回群G上定义的运算。S卩，对于
意思是对Ω e G1实施X次在巡回群G定义的运算，对Ω2 e G的e G意思是以Q1 e G和Ω2 e G为被运算符，进行在巡回群G定义的运算。g :g表示巡回群G的生成元。<整体构成>图1是用于说明第一实施方式的秘密分散系统的整体构成的方框图。如图1所不例,本方式的秘密分散系统I具有分散装置110、Σ α = ^h ( α )个分散管理装置〔PA(a，h(a))(a=l，···, L, L ^ 2,h ( a ) =1, ...，H(a)，H(a)芎 2)〕120 - a - h ( a )、取得装置130、共享值生成装置140 — I L，它们可以通过网络150进行通信。为了简化说明，在本方式中，示例各存在一个分散装置110及取得装置130的构成，但也可以存在两个以上的分散装置110及/或取得装置130。根据同样的理由，在本方式中，示例只存在一个由Σ a jh ( a )个分散管理装置〔PA ( a，h ( a ))〕120 — a — h(a )构成的集合的构成，但也可以存在多个这种集合。如图1所示例，由Sa=^h ( a )个分散管理装置〔PA ( a，h ( a ))) 120 — a —h ( a )构成的集合区分为由H ( a )个分散管理装置PA ( a，1)，…，PA ( a，H ( a ))构成的多个子集合SUB ( a )各个。生成各子集合SUB ( a )所共享的共享值σ ( a )的共享值生成装置140 - α分别与各子集合SUB ( a )对应。<分散装置110>图2是用于说明图1的分散装置110的构成的方框图。图5A是用于说明图2的秘密分散部114 一 α的详情的方框图。如图2所示例，本方式的分散装置110具有临时存储部111、存储部112、控制部113、秘密分散部114 一 a ( a =1,…,L)、发送部115。如图5A所不例,本方式的秘密分散部114 一 α具有函数选择部114a — α、索引生成部114b — α、分散处理部114c 一 α。本方式的分散装置110是,例如包含具备CPU (Central Processing Unit)、RAM(Random Access Memory)>ROM (Read-Only Memory)等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部111及存储部112是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部113及秘密分散部114 一 α ( α=1,…，L)是，例如通过CPU执行规定的程序而构成的处理部。控制部113及秘密分散部114 一 α ( α =1，…，L)的至少一部分也可以是特别的集成电路。发送部115是例如调制解调器、LAN (Local Area Network)卡等通信装置。
分散装置110在控制部113的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部111或存储部112。存储于临时存储部111或存储部112的数据根据需要取出，并输入于各处理部，而利用于该处理中。<分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α ) >图3Α是用于说明第一实施方式的分散管理装置〔PA ( α，h ( α ))〕120 — α -h ( α )的构成的方框图。图5B是用于说明图3A的分散秘密值生成部124 — α — h ( α )的详情的方框图。 如图3Α所示例,本方式的分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )具有临时存储部121 — α - h ( α )、存储部122 — α — h ( α )、控制部123 — α — h(α )、分散秘密值生成部124 — α — h ( α )、发送部125 — α — h ( α )、接收部126 —α - h ( α )0如图5Β所示例，分散秘密值生成部124 — a -h ( α )具有线性运算部124a — α — h ( α )和分散秘密值合成部124b — α — h ( α )。分散管理装置〔PA ( a，h ( α ))〕120 — α — h ( α )是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部121 -a -h ( α )及存储部122 — α — h ( α )是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部123 - α 一 h ( α )及分散秘密值生成部124 — α 一 h ( α )是例如通过CPU执行规定的程序而构成的处理部。另外，控制部123 — α — h ( α )及分散秘密值生成部124 — α — h(α )的至少一部分也可以是特别的集成电路。发送部125 — α — h ( α )及接收部126 —a -h (α)是例如调制解调器、LAN卡等通信装置。分散管理装置〔PA( α，h ( α ))〕120 — α — h ( α )在控制部 123 — α — h(α )的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部121 — α — h ( α )或存储部122 — α — h ( α )。存储于临时存储部121 — α —h ( α )或存储部122 — α — h ( α )的数据根据需要取出，并输入于各处理部，而利用于该处理中。<共享值生成装置140 — α >图3Β是用于说明第一实施方式的共享值生成装置140 - α的构成的方框图。如图3Β所示例，本方式的共享值生成装置140-α具有随机数生成部141-α及发送部142-α。本方式的共享值生成装置140-α是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置，但随机数生成部141 一 α也可以是特别的集成电路。<取得装置130 >图4是用于说明第一实施方式的取得装置130的构成的方框图。图6是用于说明图4的恢复部134 - α的详情的方框图。如图4所示例，本方式的取得装置13具有临时存储部131 ;存储部132 ;控制部133 ;恢复部134 — α ( α =1，…，L);合成部137 ;发送部135 ;接收部136。如图6所示例，恢复部134 - α具有系数算出部134a — α和多项式运算部134b — α。本方式的取得装置130是，例如包含具备CPU、RAM、ROM等的公知或专用的计算机和特别的程序的特别的装置。具体地讲，临时存储部131及存储部132是，例如由RAM、寄存器、高速缓冲存储器、集成电路内的元件或硬盘等辅助存储装置或它们的至少一部分的结合构成的存储区域。控制部133、恢复部134 — α ( α =1，…，L)及合成部137是例如通过CPU执行规定的程序而构成的处理部。控制部133、恢复部134 — α ( α =1，…，L)及合成部137的至少一部分也可以是特别的集成电路。发送部135和接收部136是例如调制解调器、LAN卡等通信装置。取得装置130在控制部133的控制下执行各处理。下面，虽然简化说明，但从各处理部输出的数据逐一存储于临时存储部131或存储部132。存储于临时存储部131或存储部132的数据根据需要读出，并输入于各处理部，而利用于该处理中。
<秘密分散处理>对本方式的秘密分散处理进行说明。[事前处理]作为本方式的秘密分散处理的事前处理，在分散装置110的存储部112中存储用于确定秘密信息Θ · g e G的信息Θ e F,。[秘密分散处理的整体]图7是用于说明第一实施方式的秘密分散处理的整体的图。下面，使用图7，对本方式的秘密分散处理的整体进行说明。在本方式中，首先，分散装置110 (图1)按各子集合SUB (α)独立地对秘密信息Θ · g e G进行秘密分散，生成共享信息SH ( α，h ( a )) (h ( a )=1,…，H ( α ))，输出该共享信息SH ( a，h ( α ))(步骤S11)。各共享信息SH ( a，h ( α ))分别经由网络150，分散发送到各分散管理装置〔PA ( a , h (α))〕120 — α — h ( α )。发送各共享信息SH ( α，h ( α ))的各分散管理装置〔PA ( α，h ( α ))〕120 —α - h ( α )分别使用该共享信息SH ( a，h ( α ))和包含子集合SUB ( α )所共享的共享值σ ( α )的共同信息，进行规定的共同运算，从而生成分散秘密值DSH (a, h (α ))，输出该分散秘密值DSH ( α，h ( α ))(步骤S12)。在本方式的情况下，在相互不同的子集合SUB ( α )中分别共享的共享值σ ( α )是相互独立的。属于相同子集合SUB ( α )的分散管理装置〔PA (a,h (a )))120- a -h (α)分别使用的“共同信息”相互相同。特别是，本方式中示例的“共同信息”包含共享值σ ( a )和由取得装置130提供的在所有的分散管理装置PA ( a，h ( a ))120 — a — h(a )中共同的提供信息V。属于相同子集合SUB ( a )的分散管理装置〔PA ( a，h ( a ))〕120 - a - h (a)分别进行的“共同运算”相互相同。在本方式中，设为所有的“共同运算”相同。本方式的“共同运算”是具有线性性的运算。从各分散管理装置〔PA ( a , h (a ))) 120 — a — h ( a )输出的各分散秘密值DSH (a,h (a ))分别经由网络150，发送到取得装置130。取得装置130使用与相同子集合SUB ( a )对应的多个分散秘密值DSH ( a，h ( a ))，通过每个子集合SUB ( a )的恢复处理，生成秘密恢复值SUBSK ( a )(步骤S13)。接着，取得装置130使用对各子集合SUB( a )分别生成的秘密恢复值SUBSK( a )，生成生成信息SK，并输出该生成信息SK(步骤S14)。另外，在本方式中，取得装置130对秘密恢复值SUBSK ( a )进行线性结合，生成信息SK。[分散装置的处理(步骤Sll)]
图8A是用于示例第一实施方式的分散装置的处理的图，图SB是用于示例步骤S112的处理的详情的图。下面，使用这些图，对分散装置110的处理的详情进行说明。首先，分散装置110 (图2)的控制部113设定α =1，并将该设定内容存储于临时存储部111 (步骤S111)。接着，从存储部112读出用于确定秘密信息Θ *geG的信息θ e Fq,并输入到秘密分散部114-α。秘密分散部114-α根据规定的秘密分散方式,使用信息Θ e Fq,对秘密信息Θ · g或信息Θ进行秘密分散,生成输出对于子集合SUB (α)的 H ( α )个共享信息 SH ( α，1)，…，SH ( α，H ( α ))(步骤 S112)。《步骤SI12的详情》本方式的秘密分散部114 一 α对各子集合SUB ( α )，使用(R ( α )，H ( α ))阈值秘密分散方式(其中，R (α)是满足2 = R (α)<Η ( α )的常数)，生成对秘密信息进行秘密分散而得到的共享信息SH ( α，h ( a )) (h ( α ) =1，…，H ( α ))。
如图SB所示例，首先，秘密分散部114 一 α (图5Α)的函数选择部114a — α随机选择f ( α，X) e Fq来输出对于预先确定的有限域Fq的元ω e Fq满足f ( α，ω) = θ的R ( α )-1次的多项式(步骤S112a)。另外，χ是由有限域Fq的元构成的变量，元ω e Fq的一个例子为Of。接着，索引生成部114b — α生成输出与各h ( α )=1，…，H ( α )对应的索引φ ( h (a)) EFq(步骤sil2b)。另外,在设为索引φ ( H ( a )) =h (a)EFq的情况下及在已经得到索引φ (h (a)) eFq的情况下，也可以省略步骤S112的处理。接着，分散处理部114c 一 α使用多项式f ( a，χ) e Fq和索引φ ( h ( a ) )￡ F,p
生成下面的共享信息SH ( a，h ( a )) (h ( a ) =1，…，H ( a ))。
SH ( a, h ( a )) = ((p ( h ( a )), f ( α, φ ( h ( a ))) -g￡G ) ... ( 5 )分散处理部114c — a输出共享信息SH ( a，h ( a ))(步骤S112c /《步骤S112的详情》的说明结束)。接着，控制部113判定存储于临时存储部111的α是否为L (步骤S113)。在此，在判定为不是a =L的情况下，控制部113将a +1设为新的α，将其设定内容存储在临时存储部111 (步骤S114)，并通过新的α执行步骤S112的处理。另一方面，在步骤S113中判定为a =L的情况下，从各秘密分散部114— α输出的各共享信息SH ( a , h ( a ))(a=l,…，L)发送到发送部115。发送部115分别经由网络150将各共享信息SH ( a，h(a )) ( a =1，…，L),发送到分散管理装置〔PA ( a，h ( α ))〕120 — a — h ( a ) ( a =1, ···,L)(步骤S115)。即，共享信息SH (1，I)发送到分散管理装置〔PA (1,1)) 120 — I — 1，共享信息SH (1，2)发送到分散管理装置〔PA (1,2)) 120 -1 - 2，…共享信息SH (L，H(L))发送到分散管理装置〔PA (L, H (L))) 120-L-H (L)0[共享值生成装置的处理]各共享值生成装置140 — α (图3B)生成在构成与自身对应的子集合SUB ( a )的各分散管理装置〔PA ( a，h ( a ))) 120 — a — h ( a )中共享的共享值σ ( α )。在本方式中，将随机数生成部141 - α生成的随机数设为共享值σ ( a )，发送部142 — α将共享值σ ( a )发送到构成子集合SUB ( a )的各分散管理装置〔PA ( a，h ( a ))) 120 -α — h ( α )。[分散管理装置的处理(步骤S12)]图9Α是用于示例第一实施方式的分散管理装置〔PA ( a，h ( α ))) 120 — α — h(α )的处理的图，图9Β是用于示例步骤S124的处理的详情的图。下面，使用这些图，对本方式的分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )的处理进行说明。首先，分散管理装置〔PA( a，h( α ))〕120 — α — h ( α )(图3Α)的接收部126 —α - h ( α )接收发送的共享信息SH ( α，h ( α ))，并将其存储在存储部122 — α — h(α )(步骤S121)。另外，如果过去执行步骤S121的处理，共享信息SH ( α，h ( α ))已经存储于分散管理装置〔PA ( a ,h ( a )))120 - α - h ( α )的存储部122 — α — h ( α )，则也可以省略步骤S121的处理。分散管理装置〔PA( α，h ( α ))〕120 — α — h ( α )的接收部 126 — α — h(α )接收从共享值生成装置140 - α发送的共享值σ ( α )，并将其存储于存储部122 —α — h ( α )(步骤 S122)。在本方式中，从取得装置130(图4)的存储部132读出的提供信息V经由网络150，从发送部135发送到各分散管理装置〔PA ( α，h ( α ))〕120 — α — h ( α )。该提供信息V在所有的分散管理装置PA ( α，h ( α )) 120 — α — h ( α )中是共同的。提供信息V由分散管理装置〔PA ( a，h ( α ))〕120 — α — h ( α )(图3Α)的接收部126 — α — h(α )接收，并存储在存储部122 — α — h ( α )(步骤S123)。接着，分散秘密值生成部124 — α — h ( α )从存储部122 — α — h ( α )读入共享信息SH ( a，h ( α ))、共享值σ ( α )和提供信息V。分散秘密值生成部124 — α 一 h(α )使用包含共享值σ ( α )和提供信息V的共同信息、共享信息SH ( α，h ( α )),进行共同运算FNCl，生成分散秘密值DSH ( a，h ( α ))，并输出该分散秘密值DSH ( a，h ( α ))(步骤 S124)。《步骤S124的详情》属于相同子集合SUB ( α )的分散管理装置PA ( a，h ( α )) 120-a -h ( α )的分散秘密值生成部124 — α 一 h U )分别使用的共同信息是相互相同的，属于相同子集合SUB ( α )的分散管理装置PA ( a，h ( a ))120 — α — h ( α )的分散秘密值生成部124 —α 一 h (α)分别进行的共同运算是相互相同的。本方式的共享信息如式(5)所示。如图9Β所示例，首先，对本方式的分散秘密值生成部124 — α - h ( α )的线性运算部124a — α 一 h (α)，输入共享值σ ( α )、提供信息ν和共享信息SH ( a, h ( α )) = ( φ ( h ( α ) )，f α； φ ( h ( α ))) -g )的 f ( α，φ ( h ( α ))) -g,
线性运算部124a— α — h( α )进行下面的运算，并输出其运算结果dsh ( α, φ( h (α)))(步骤 S124a)。
dsh ( α, φ ( H ( α ))) =σ U/; ·ν· ( α, ο (H ( α ))) -g... ι 6 ;输出的运算结果 dsh (α，φ (h ( α)))输入于分散秘密值合成部124b —a - h (α)0对分散秘密值合成部124b — a -h ( α )，进一步输入共享信息SH ( CUh ( α)) = ( φ ( h (a)), f ( α, φ ( h ( α))) -g )的索引 φ ( h (α))，分散秘密值合成部124b - a -h ( α )通过下面的运算，生成分散秘密值DSH ( α，h ( α ))。
DSH ( a, h ( α)) = ( φ (h ( α )), dsh ( α, φ ( h ( α)))) ... (J )分散秘密值合成部124b — α — h ( α )输出分散秘密值DSH ( a，h ( α ))(步骤S124b /《步骤S124的详情》的说明结束)。生成的分散秘密值DSH (a,h (α))发送到发送部125 — α — h ( α )。发送部125 — a — h ( a )将分散秘密 值DSH ( a，h ( a ))经由网络150，发送到取得装置130 (步骤 S125)。[取得装置的处理(步骤S13、S14)]图1OA是用于示例第一实施方式的取得装置的处理的图，图1OB是用于示例步骤S134的处理的图。从各分散管理装置PA ( a , h ( a )) 120 — a — h ( a )发送的分散秘密值DSH(a，h (α))由取得装置130 (图4)的接收部136接收，并存储于存储部132 (步骤S131)。接着，控制部133判定在存储部132中是否存储有需要数以上的分散秘密值DSH(a，h ( a ))(步骤S132)。在本方式的情况下，对各a =1，…，L，分别判定在存储部132中是否存储有不同的R ( a ) (2 ^ R ( a X H ( a ))个以上的分散秘密值DSH ( a，h ( α ))。在此，在判定为在存储部132中未存储有需要数以上的分散秘密值DSH ( a , h ( a ))的情况下，返回步骤S131的处理。另一方面，在判定为在存储部132中存储有需要数以上的分散秘密值DSH ( a，h ( a ))的情况下，控制部133设定为a =1，并将其设定内容存储于临时存储部131 (步骤S133)。接着，从存储部132读出与子集合SUB( a )对应的需要数量的分散秘密值DSH( a，h ( a )),并输入到恢复部134 — α中。恢复部134 — α使用输入的分散秘密值DSH ( a，h ( a ))，通过根据在上述步骤S112中使用的秘密分散方式的每个子集合SUB ( a )的恢复处理，生成秘密恢复值SUBSK ( a )，并输出该每个子集合SUB ( a )的秘密恢复值SUBSK(a )(步骤 S134)。《步骤S134的详情》本方式的分散秘密值DSH ( a，h ( a ))如式(7)所示。对恢复部134 — α (图6)对于每个α各输入R ( a )个不同的分散秘密值DSH ( a，h ( α ))。下面中，如下表示与输入于恢复部134 — α的各α对应的分散秘密值DSH ( a，h ( α ))。
DSH ( α，φι ( a )) = ( φι ( a ), dshι ( a)))
… ...(8 )
DSH ( a.，Oi )( )) = ( (pR i u ι ( a .)，dsliR ；■ u) ( a))其中，满足下面。
(φι ( a), ..., 9r(α) ( a)) □ ( φ ( I ), ···， φ (H ( a))) ... ( 9 )( dsh ι ( a), dshR:u) ( a )) □ ( dsh ( α, φ ( I ) )，} dsh ( a·,
权利要求
1.一种秘密分散系统,其中，具有 分散装置；Σ α = A ( α )个分散管理装置PA ( a，h ( a )) ( α =1，…，L, L兰2, h(α ) =1，…，H ( α )，H ( α )芎 2);取得装置， 所述分散装置包含如下秘密分散部，即， 将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，…，Ψ、将η ( Ψ)设为I以上的整数、将ζ ( Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于Θ ( ψ , i, β ) (i=l, ...，η(ψ) + ζ (ψ)，β=1， ···, η ( ψ ) + ζ ( ψ ), η ( ψ ) ^ I, ζ(ψ)兰I)的所述巡回群G2的11 ( Ψ) + ζ ( Ψ)个元为要素的η ( Ψ)+ ζ (Ψ)维的基底向量设为 ( ψ ) = ( θ ( ψ , i, I) · g2, ···, θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2) e 62η(ψ)+ζ(Ψ)的情况下，将与所述基底向量b# ( Ψ)的各要素Θ ( ψ，i，β ) · g2相应的值通过规定的秘密分散方式，分别独立地秘密分散到每个由H (α)个分散管理装置PA (α,Ι),…，PA ( α ,H ( α ))构成的子集合SUB ( α )中，生成与各要素θ ( ψ, , β ) · g2相应的值的共享信息 SH ( V，i，β，a，h ( a )) (h ( α )=1，...，Η ( α ))， 所述分散管理装置PA ( α，h ( α ))包含如下分散秘密值生成部，即， 对按每个所述子集合SUB ( α )所共享的共同信息和所述共享信息SH ( Ψ，i，β，α，h ( α (h ( α )=1,…，H ( α ))，按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH ( Ψ , α，h ( α ))， 所述取得装置包含 使用与相同的所述子集合SUB ( α )对应的多个所述分散秘密值DSH ( ψ，a，h ( α ))，通过根据所述秘密分散方式的每个子集合SUB ( α )的恢复处理，生成每个该子集合SUB(α )的秘密恢复值SUBSK ( Ψ，α )的恢复部；以及 使用所述秘密恢复值SUBSK ( Ψ，α )，生成生成信息D* ( Ψ )的合成部。
2.如权利要求1的秘密分散系统，其中， 在相互不同的所述子集合SUB ( α )分别共享的所述共同信息是相互独立的。
3.如权利要求1的秘密分散系统，其中， 所述共同运算是具有线性性的运算。
4.如权利要求2的秘密分散系统，其中， 所述共同运算是具有线性性的运算。
5.如权利要求1的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D*(Ψ )。
6.如权利要求2的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α )进行线性结合，生成所述生成信息D*(Ψ )。
7.如权利要求3的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D*(Ψ )。
8.如权利要求4的秘密分散系统，其中， 所述合成部对所述秘密恢复值SUBSK (Ψ, α )进行线性结合，生成所述生成信息D*(Ψ )。
9.如权利要求1 8中任一项所述的秘密分散系统，其中， 与所述基底向量匕* ( Ψ)的各要素θ ( Ψ，i，β ) · g2相应的值为Θ ( ψ, i, β ),所述共同信息包含将λ设为I以上Ψ下面的整数λ=1，…，Ψ的情况下的coef I(O, a ), coef ( λ , α ), coef ι ( λ , α ), SE ( α ), share ( λ , α ), 作为与ν=ο对应的所述分散秘密值，所述分散秘密值生成部生成设为 SHbi* (O, α，h ( a )) = (SH (0，i，1，α，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的 DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) · g2+Z t = ^coefl (O, α ) · SHbl* (O, α，h(α )) · g2， 另外，作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α，h ( α )))，并将V ( λ ) —(V1 ( λ )，-, νη(λ) ( λ ))设为η ( λ )维向量的情况下的DSH ( λ，α，h ( α )) =(share ( λ，α ) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) · g2 + Σ =2η ( λ ) coef ( λ , α ) · V, (λ)· SHb , * (λ, a , h ( α )) · g2 + Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 或， DSH ( λ，a，h ( a ))=Share ( λ，α ) · Σ l=1nU)vt ( λ ) · SHb1* ( λ，α，h ( α )) · g2+Z ι=η ⑴+1η ⑴+ ζu) Coefl (λ,α)· SHb , * (λ, a,h (a))*g2。
10.如权利要求1 8中任一项所述的秘密分散系统，其中， 与所述基底向量匕* (Ψ)的各要素Θ (V，i，β)·&相应的值为θ (ψ, , β)·δ2,所述共同信息包含将λ设为I以上Ψ下面的整数λ=1，…，Ψ的情况下的coef I(O, a ), coef ( λ , a ), coef ι ( λ , a ), SE ( a ), share ( λ , α ), 作为与ν=ο对应的所述分散秘密值，所述分散秘密值生成部生成设为 SHbi* (O, α，h ( a )) = (SH (0，i，1，α，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的 DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) +Σ ^21Coefl (O, α ) · SHb , * (O, α，h ( α ))，另外，作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α，h ( α )))， 并将V (λ)-= (Vl (λ(λ))设为η (λ)维向量的情况下的 DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) + Σ , = 2η ( λ ) coef (λ,α)”，(λ)· SHb , * (λ, a,h ( α ))+ Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α ))或，DSH ( λ，α，h ( α ))=Share ( λ，α ) · Σ , =1η (λ)ν, ( λ ) · SHb1* ( λ，α，h ( α ))+Σ , =η (λ)+1η (λ) + ζ (λ)coef, (λ,α)· SHb , * (λ, a,h (α))。
11.如权利要求9的秘密分散系统，其中， 作为与Ψ=0对应的所述秘密恢复值，所述恢复部生成SUBSK (O, a ) =-SE ( a ) · b# (0) +Σ ^21Coefl (0，a ) · bt* (0)， 作为与各λ对应的所述秘密恢复值，生成 SUBSK ( λ，a ) = (share ( λ，α ) +coef (λ，(λ))· Id1* ( λ ) + Σ , =2η ( λ ) coef (λ,α)”，(A)^bl* (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (A)0
12.如权利要求10的秘密分散系统，其中， 作为与Ψ=0对应的所述秘密恢复值，所述恢复部生成SUBSK (O, a ) =-SE ( a ) · b# (0) +Σ ^21Coefl (0，a ) · bt* (0)， 作为与各λ对应的所述秘密恢复值，生成SUBSK (入，a ) = (share (λ,α) +coef (入，α ) · V1 (入))· Id1* (入)+ Σ t =2n ( λ ) coef ( λ , α ) · V t ( λ ) · h ^ (λ)+ Σ, .nU)+1n(A) + 5(A)coefl (λ, α)+* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ )+ Σ, .η(λ)+1η(λ) + ζ U)coeft (λ, a).b丨* (A)0
13.一种分散装置，将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，…，Ψ、将η (HO设为I以上的整数、将ζ (Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 θ ( Ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1,…，η(ψ) + ζ ( ψ ), η(Ψ )= I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ )+ζ ( Ψ )个元为要素的η ( ψ )+ζ (ψ)维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2)eG2n(v)〃(ν)的情况下，将与所述基底向量(HO的各要素θ (ψ, , β)·&相应的值通过规定的秘密分散方式分别独立地秘密分散到每个由H( a )( a=l,...,L, L = 2,h(a)=1，···，Η(α)，Η(α) ^ 2)个分散管理装置PA ( α,Ι),…，PA ( a ,H ( a ))构成的子集合SUB ( a )中，生成与各要素Θ ( ψ, , β ) · g2相应的值的共享信息SH ( Ψ，i，β，a，h ( a )) (h ( a ) =1,…，H ( a ))。
14.一种分散管理装置，其对按H ( a ) ( a=l，…，L，L兰2，h ( a ) =1，...，H(a)，H ( a ) ^ 2)个分散管理装置PA (α,Ι),…，PA ( a，H ( a ))构成的每个子集合SUB(a )所共享的共同信息、以及将Ψ设为I以上的整数、将V设为O以上Ψ以下的整数Ψ=0,…，Ψ、将η (Ψ)设为I以上的整数、将ζ (HO设为O以上的整数、将所述巡回群G2 的生成元设为 g2、将以相对于 Θ ( Ψ，i，β ) (i=l，…，η ( ψ ) + ζ ( Ψ ), β =1, ···, η(ψ) + ζ ( ψ ), η ( ψ ) ^ I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ ) + ζ ( Ψ )个元为要素的 η ( ψ ) + ζ ( ψ )维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η(Ψ) + ζ (￥))*g2) e 62η(ψ)+ζ 的情况下的、将与所述基底向量(Ψ)的各要素Θ(Ψ, , β )*g2相应的值分别独立地秘密分散到每个所述子集合SUB ( α )中而得到的与各要素Θ ( Ψ，i，β ) · g2相应的值的共享信息SH ( Ψ , i, β , α，h ( α )) (h ( α ) =1，…，H ( α ))，按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH (ψ,α,h ( α ))。
15.一种取得装置，其具有 恢复部，其使用将Ψ设为I以上的整数，将Ψ设为O以上Ψ下面的整数Ψ=0，…，Ψ，将由 H ( α ) ( α=1, ...，L，L 芎 2，h ( a )=1, -,H ( α )，H ( α )芎 2)个分散管理装置PA ( α，1)，…，PA ( α ,H ( α ))构成的子集合设为SUB ( α )的情况下的与相同的所述子集合SUB ( α )对应的多个所述分散秘密值DSH ( Ψ，α，h ( α ))，通过根据规定的秘密分散方式的每个子集合SUB ( α )的恢复处理，生成每个该子集合SUB ( α )的秘密恢复值SUBSK ( Ψ，α )；以及 合成部，其使用所述秘密恢复值SUBSK (Ψ，α)，生成生成信息D* (Ψ)。
16.一种秘密分散方法，通过分散装置、Σ ( α )个分散管理装置PA ( a，h ( α ))(α=1，…，L，L芎2，h ( α )=1，…，H ( α )，H ( α )芎2)和取得装置进行，其具有 (A)所述分散装置将Ψ设为I以上的整数、将Ψ设为O以上Ψ以下的整数Ψ=0，···，Ψ、将η (HO设为I以上的整数、将ζ (Ψ)设为O以上的整数、将巡回群G2的生成元设为g2、将以相对于 θ ( Ψ , i, β ) (i=l, ···, η ( ψ ) + ζ ( ψ ), β =1,…，η(ψ) + ζ ( ψ ), η(Ψ )= I, ζ ( ψ )芎I)的所述巡回群G2的η ( ψ )+ζ ( Ψ )个元为要素的η ( ψ )+ζ (ψ)维的基底向量设为 bi* ( ψ ) = ( θ ( ψ , i, I) · g2, ..., θ ( ψ , , η ( ψ ) + ζ ( Ψ )) · g2)eG2n(v)+“v)的情况下，将与所述基底向量(HO的各要素Θ (V，i，3)*&相应的值按照规定的秘密分散方式分别独立地秘密分散到每个由H ( α )个分散管理装置PA ( α，1)，-,PA ( α , H ( α ))构成的子集合SUB (α)中，生成与各要素Θ (v，i，@)*&相应的值的共享信息SH ( V，i，β，a，h ( a )) (h ( α )=1，…，H ( α ))的步骤； (B)所述分散管理装置PA( a，h ( α ))对按每个所述子集合SUB ( α )所共享的共同信息和所述共享信息SH ( Ψ , , β , a , h ( α )) (h ( α ) =1，…，H ( α )),按每个所述子集合SUB ( α )进行共同的共同运算，生成分散秘密值DSH ( Ψ，α，h ( α ))的步骤； (C)所述取得装置使用相同的所述子集合SUB( α )所对应的多个所述分散秘密值DSH(Ψ, a,h (α ))，通过按照所述秘密分散方式的每个子集合SUB ( a )的恢复处理，生成每个该子集合SUB ( a )的秘密恢复值SUBSK ( Ψ，a )的步骤；以及 (D)所述取得装置使用所述秘密恢复值SUBSK( Ψ，a )，生成生成信息D* ( Ψ )的步骤。
17.如权利要求16的秘密分散方法，其中， 在相互不同的所述子集合SUB ( a )中分别共享的所述共同信息是相互独立的。
18.如权利要求16的秘密分散方法，其中， 所述共同运算是具有线性性的运算。
19.如权利要求17的秘密分散方法，其中，所述共同运算是具有线性性的运算。
20.如权利要求16的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
21.如权利要求17的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
22.如权利要求18的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
23.如权利要求19的秘密分散方法，其中， 所述步骤(D)包含对所述秘密恢复值SUBSK (Ψ, α)进行线性结合，生成所述生成信息D* ( Ψ )的步骤。
24.如权利要求16 23中任一项所述的秘密分散方法，其中， 与所述基底向量\* ( Ψ)的各要素θ ( Ψ，i，β ) · g2相应的值为Θ ( ψ, i, β ),所述共同信息包含将λ设为I以上Ψ下面的整数入=1，…，Ψ的情况下的coef ι(O, a ), coef ( λ , α ), coef ι ( λ , α ), SE ( α ), share ( λ , α ), 所述步骤(B)包含 (B-1)作为与Ψ=0对应的所述分散秘密值，生成设为SHbi* (O, a，h ( a ))= (SH (O,i，l，a，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的DSH (0，α，h ( α ))=-SE ( α VSHb1* (0，α，h ( α )).g2+Z ^21Coefl (0，α ).SHbt * (0，α，h ( α )).g2的步骤；以及 (B-2)作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，a，h ( a ))= (SH ( λ，i，l，a，h ( α ))，…，SH ( λ，i，n ( λ ) + ζ ( λ )，α ,h (α)))，并将V (λ)—= (Vl (λ)，…，νη(；0(λ))设为η (λ)维向量的情况下的DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) · g2 + Σ =2η ( λ ) coef ( λ , α ) · V, (λ)· SHb , * (λ, a , h ( α )) · g2 + Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 或， DSH ( λ，a，h ( a )) =share(λ)· SHb1* (λ, a,h ( α )) · g2+ Σ ι=η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) · g2 的步骤。
25.如权利要求16 23中任一项所述的秘密分散方法，其中， 与所述基底向量匕* (Ψ)的各要素Θ (V，i，β)·&相应的值为θ (ψ, , β)·δ2,所述共同信息包含将λ设为I以上Ψ下面的整数入=1，…，Ψ的情况下的coef ι(O, a ), coef ( λ , a ), coef ι ( λ , a ), SE ( a ), share ( λ , α ), 所述步骤(B)包含(B-1)作为与Ψ =O对应的所述分散秘密值，生成设为SHbi* (O, a，h ( a ))= (SH (O,i，l，a，h ( α ))，…，SH (0，i，I，α，h ( α )))的情况下的DSH (0，α，h ( α ))=-SE ( α ) · SHb1* (O, α，h ( α )) +Σ ^21Coefl (O, α ) · SHb , * (O, α，h ( α ))的步骤；以及 (Β-2)作为与各λ对应的所述分散秘密值，生成设为SHbi* ( λ，α，h ( a )) = (SH(λ , ,Ι, α , h ( α )), ···, SH ( λ , , η (λ) + ζ (λ), α , h ( α ))),并将 ν ( λ ) — (Vi(λ)，…，νη(λ)(λ))设为η (λ)维向量的情况下的， DSH ( λ，α，h ( α )) =(share (λ,α) +coef (λ，(λ))· SHb1* (λ，a，h ( α )) + Σ , = 2η ( λ ) coef (λ,α)”，(λ)· SHb , * (λ, a,h ( α ))+ Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α )) 或， DSH ( λ，a，h ( α )) =share(λ)· SHb1* (λ, a,h ( α ))+ Σ , =η(λ)+1η(λ) + ζ c^coefl ( λ，α ) · SHbl* ( λ，a，h ( α ))的步骤。
26.如权利要求24的秘密分散方法，其中， 所述步骤(C)包含 (C-1)作为与Ψ=0对应的所述秘密恢复值，生成SUBSK (O, a ) =-SE ( a ) · (O)+ Σ ^21Coefl (0，a ) · b，(O)的步骤；以及 (C-2)作为与各λ对应的所述秘密恢复值，生成SUBSK ( λ，a )= (share (λ,α)+coef (入，α ) · V1 (入))· Id1* (入)+ Σ ι=2η (入)coef ( λ , α ) · V t ( λ ) · h ^ (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + st.nU)+1nU)+5 uWfl (λ，O.b丨* (λ)的步骤。
27.如权利要求25的秘密分散方法，其中， 所述步骤(C)包含 (C-1)作为与Ψ=0对应的所述秘密恢复值，生成SUBSK (O, a ) =-SE ( α ) · (O)+ Σ ^21Coefl (0，α ) · b，(O)的步骤；以及 (C-2)作为与各λ对应的所述秘密恢复值，生成SUBSK ( λ，a )= (share (λ,α)+coef (入，α ) · V1 (入))· Id1* (入)+ Σ ι=2η (入)coef ( λ , α ) · V t ( λ ) · h ^ (λ) + St.nU)+1nU) + 5 uWfl (λ, a).bt* (λ) 或， SUBSK (λ,α) =share (λ, Ο.Σκη"、，(λ)· Id1* ( λ ) + st.nU)+1nU)+5 uWfl (λ，O.b丨* (λ)的步骤。
28.—种程序，用于使计算机作为权利要求13的分散装置而发挥作用。
29.—种程序，用于使计算机作为权利要求14的分散管理装置而发挥作用。
30.一种程序，用于使计算机作为权利要求15的取得装置而发挥作用。
31.一种计算机可读取的记录介质，其存储了用于使计算机作为权利要求13的分散装置而发挥作用的的程序。
32.—种计算机可读取的记录介质，其存储了用于使计算机作为权利要求14的分散管理装置而发挥作用的的程序。
33.一种计算机可读取的记录介质，其存储了用于使计算机作为权利要求15的取得装置而发挥作用的的程序。
全文摘要
分散装置将与基底向量bi*(ψ)的各要素θ(ψ，i，β)·g2相应的值分别独立地秘密分散到由H(α)个分散管理装置PA(α，1)，…，PA(α，H(α))构成的每个子集合SUB(α)中，生成与各要素θ(ψ，i，β)·g2相应的值的共享信息SH(ψ，i，β，α，h(α))。分散管理装置PA(α，h(α))对按每个子集合SUB(α)所共享的共同信息和共享信息SH(ψ，i，β，α，h(α))，进行按每个子集合SUB(α)的共同运算，生成分散秘密值DSH(ψ，α，h(α))。取得装置通过每个子集合SUB(α)的恢复处理，生成秘密恢复值SUBSK(ψ，α)，使用秘密恢复值SUBSK(ψ，α)，生成生成信息D*(ψ)。
文档编号G09C1/00GK103003857SQ20118003531
公开日2013年3月27日 申请日期2011年7月22日 优先权日2010年7月23日
发明者西卷陵, 铃木幸太郎 申请人:日本电信电话株式会社
最新回复(0)