秘密分散系统、分散装置、分散管理装置、取得装置、其处理方法、秘密分散方法、程序以及...的制作方法
专利名称：秘密分散系统、分散装置、分散管理装置、取得装置、其处理方法、秘密分散方法、程序以及 ...的制作方法
技术领域：
本发明涉及秘密分散技术。
背景技术：
在保管秘密信息时，存在秘密信息的遗失或破坏的风险和被盗的风险。能够通过保管多个秘密信息来降低遗失或破坏的风险。但是，这种情况下被盗的风险增加。作为一起解决这些风险的方法之一，存在秘密分散法(SSS=Secret Sharing Scheme)(例如，参照非专利文献1、2)。秘密分散法是如下的方式根据秘密信息MSK生成多个分散信息(share information) SH(I),..., SH(N)，并将这些分散信息分散到多个分散管理装置PA(1)，...， PA(N)而进行管理，并且仅在这些分散信息SH(I)，...，SH(N)中能够取得规定数目以上的分散信息的情况下，能够复原秘密信息MSK。以下，表示秘密分散法的代表性的方式。[ (N, N)阈值秘密分散法](N, N)阈值秘密分散法是如下的方式如果提供所有的分散信息 SH(I)，. . .，SH(N)，则能够复原秘密信息MSK，但是，即使提供任意的N-I个分散信息 SH(Cp1),...,SH(Cpigi),也无法完全得到秘密信息MSK的信息。以下，表示其一例。■随机选择 SH1，...，SHim。■进行 SK = MSK- (SH1+. . . +SHnJ 的计算。■将各分散信息3!11，...，3!1,分散到多个分散管理装置？4(1)，...，？八(幻而进行管理。■如果提供全部的分散信息SH1, · · ·，SHn,则能够通过MSK = SH1+. . . +SHn的复原处理来复原秘密信息MSK。另外，用于从分散信息SH1, ...，SHn复原秘密信息MSK的运算MSK = SH1+. · · +SHn 是线型的。因此，在将各分散信息SH(I)，...，SH (N)和值σ作为被运算符而对各个分散信息进行相同的线型运算CALC，并将该计算结果作为各分散信息SH' (1)，. . .，SH' (N)而进行了复原处理的情况下，得到将秘密信息MSK和值σ作为被运算符而进行了该线型运算 CALC的结果。例如，在将SH' (1) = σ · SH(I)SH' (N) = σ -SH(N)作为各分散信息SH' (1)，· · ·，SH' (N)而执行了复原处理的情况下，得到式(1)。σ · SH(I)+. . . + 0 · SH(N)= σ · (SH(I)+. . . +SH(N))= σ . MSK …(1)另一方面，在将各分散信息SH⑴，...，SH(N)和互相独立的值ο (1)，...，ο (N) 作为被运算符而对各个分散信息进行相同的线型运算CALC，并将其结果作为各分散信息 SH' (1)，...，SH' (N)而执行了复原处理的情况下，通常无法得到将秘密信息MSK作为被运算符的运算结果。例如，将SH' (1) = σ (1) . SH⑴，· ·，SH' (N) = σ (N) · SH(N)作为各分散信息SH' (1)，. . .，SH' (N)而执行了复原处理的情况下，得到式(2)。σ ⑴· SH(I)+. ··+ σ (N) · SH(N) . . . (2)[ (K，N)阈值秘密分散法](K，N)阈值秘密分散法是如下的方式如果提供不相同的任意K个分散信息 SH(Cp1),...,SH(cpK)，则能够复原秘密信息MSK，但是，即使提供任意的K-I个分散信息 SH(Cp1),...,SH(Cpigi),也无法完全得到秘密信息MSK的信息。以下，表示其一例。■随机选择满足f(0) = MSK的K-I次多项式f(x)= ξ ο+ ξ 1 · X+ ξ 2 · Χ2+· . . + I K-I · Χ1"。即，设为 I0 = MSK,并随机选择 ξι; ... , ξ H。将分散信息设为 SHp = (p,f(p))(p = 1，···，Ν)。■在得到了不相同的任意K个分散信息SHC91),...,SH(9k) ((φι,...,φκ) C(l,...,N))的情况下，例如使用Lagrange的内插公式，能够通过如下的复原处理来复原秘密信息MSK。
权利要求
1.一种秘密分散系统，具有分散装置、Σ。=141(^0个分散管理装置？々((1，11((1))、以及取得装置，其中 α = 1，···，L，L 彡 2，h(a) = 1, . . . , H( a ), H( a )彡 2，其中，所述分散装置包括秘密分散单元，按各个子集合SUB ( a )独立地对秘密信息进行秘密分散从而生成分散信息SH(a，h(a))，并且输出该分散信息SH(a，h(a))，其中，该子集合SUB(Ci)由H(a) 个分散管理装置PA ( a，1)，...，PA ( a，H ( a ))构成， 所述分散管理装置PA ( a，h ( a ))包括分散秘密值生成单元，使用包含由各个所述子集合SUB(Ci)共享的共享值σ (α)的共同信息、以及所述分散信息SH(a，h(a))，通过共同运算来生成分散秘密值DSH(a， 匕(0))，并且输出该分散秘密值05!1((1，11((1))，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同， 所述取得装置包括复原单元，使用与相同的所述子集合SUB(Ci)对应的多个所述分散秘密值DSH(a， h ( a ))，通过各个子集合SUB ( a )的复原处理来生成秘密复原值SUBSK (α),得到该各个子集合SUB ( a )的所述秘密复原值SUBSK ( a )；以及合成单元，使用所述秘密复原值SUBSK ( a )来生成生成信息SK，并且输出该生成信息SK。
2.如权利要求1所述的秘密分散系统，其中，在互相不同的所述子集合SUB( α)中分别共享的所述共享值σ (α)互相独立。
3.如权利要求1或2所述的秘密分散系统，其中，由所述分散管理装置PA(a，h(a))的所述分散秘密值生成单元分别进行的所述共同运算全部相同，其中a = 1, ... ,L0
4.如权利要求3所述的秘密分散系统，其中， 所述共同运算是具有线型性的运算，所述合成单元对所述秘密复原值SUBSK ( a )进行线型结合来生成所述生成信息SK。
5.如权利要求1所述的秘密分散系统，其中，所述共同信息包含所述共享值ο (α)、以及从所述取得装置提供的在所有的所述分散管理装置PA(a，h(a))中共同的提供信息。
6.如权利要求1所述的秘密分散系统，其中，所述合成单元对所述秘密复原值SUBSK ( a )进行线型结合来生成所述生成信息SK。
7.如权利要求1所述的秘密分散系统，其中， 所述共同运算是具有线型性的运算。
8.如权利要求1所述的秘密分散系统，其中，所述秘密分散单元对至少一部分所述子集合SUB(a)，使用(R(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息3对(1，11((1))，其中，2彡1 ((1) < H(a),所述复原单元使用与相同的所述子集合SUB ( α )对应的R( α )个以上的所述分散秘密值DSH ( α，h ( α ))，生成该各个子集合SUB ( α )的秘密复原值SUBSK ( α )。
9.如权利要求8所述的秘密分散系统，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ . geG,用于确定所述秘密信息的信息是θ e Fq,使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( α， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( α) 对应的索引设为cp(h(a))的情况下的、所述巡回群G的元f(a,cp(h(a))) · gEG。
10.如权利要求8所述的秘密分散系统，其中， 所述秘密信息包括有限域F,的元θ，使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( a) 对应的索引设为cp(h(a))的情况下的、所述有限域Ftl的元f(a,cp(h(a)))eFq。
11.如权利要求1所述的秘密分散系统，其中，所述秘密分散单元对至少一部分所述子集合SUB(a)，使用(H(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息SH( a，h ( a ))，所述复原单元使用与相同的所述子集合SUB(a)对应的H(a)个所述分散秘密值 DSH ( a，h ( a ))，生成该各个子集合SUB ( a )的秘密复原值SUBSK ( a )。
12.如权利要求11所述的秘密分散系统，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ - geG,使用(H(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a))是满足 SH(a，l)+SH(a，2)+...+SH(a，H(a)) = θ .g e G 的所述巡回群 G 的元。
13.如权利要求11所述的秘密分散系统，其中， 所述秘密信息包括有限域F,的元θ，使用(Η(α)，Η(α))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a))是满足 SH(a，l)+SH(a，2)+. ..+SH(a，Η(α)) = θ e Fq 的所述有限域 Fq 的元。
14.如权利要求5至13的任一项所述的秘密分散系统，其中，所述秘密信息是在将巡回群G的生成元设为g，将θ (i，β)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维基底向量设为b^= (Θ (i,l) -g,..., θ (i， η+ζ) · g) e 6η+ζ的情况下的、该基底向量V的集合(bA ...，bn+J)，其中i = 1，...， η+ζ，β = 1，…，η+ζ，η 彡 1，ζ 彡 1，所述秘密分散单元生成按各个所述子集合SUB ( a )独立地分别对各基底向量bj的元素θ (i，β) *geG进行了秘密分散的分散信息SH(i，β, a,h(a)) eG，所述分散信息 SH(a ,h(a))是所述分散信息SH(i，β, a,h(a)) e G的集合，所述提供信息是以所述有限域F,的元作为元素Wli的η维向量《一= (Wl,...,Wn)，其中μ = 1,…，η,所述分散秘密值生成单元使用所述分散信息SH (i，β, a，h(a))、所述共享值σ (a) 以及所述η维向量w —来生成所述分散秘密值DSH(a，h ( a ))，所述分散秘密值DSH( a， h(a))是对于以 η+ζ 个分散信息 SH(i，l，a，h(a))，...，SH (i, η+ζ , a，h(a))作为元素的 η+ζ 维的分散基底向量 SHbi*(a，h(a)) = (SH(i，l，a，h( a ))，. . .，SH(i，η+ζ， a , h(a)) e 6η+ζ 的、DSH(a，h(a)) = σ ( a ) · { Σ μ = · SHb/(a , h(a))}+ Σ μ .n+1n+'SHb/(a,h(a)) e Gn+S所述秘密复原值 SUB SK(a)是 SUB SK(a) = σ (a) · { Σ μ=1\μ -b/j+Σ μ =η+it * 厂η+ζ η+1 βμ 匕 b 。
15.如权利要求14所述的秘密分散系统，其中，所述合成单元计算所述生成信息SK= {(σ (1)+... + 0 (L))/L} · { Σ μ =InWll · b/}+ Σ μ =n+1n+ib/。
16.一种分散装置，具有秘密分散单元，将秘密信息作为输入，按各个子集合SUB(a )独立地对所述秘密信息进行秘密分散从而生成分散信息SH( a，h ( a ))，并且输出该分散信息SH( a，h ( a ))，其中，该子集合SUB(Ci)由H(a)个分散管理装置PA(a，l)，. . . , PA( a , H( a ))构成，其中 a = 1, . . . , L, L ^ 2, h(a ) = 1, . . . , H( a ), H( a ) >2。
17.如权利要求16所述的分散装置，其中，所述秘密分散单元对至少一部分所述子集合SUB( a)，使用(R(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息3对(1，11((1))，其中，2彡1 ((1) < H(a )。
18.如权利要求17所述的分散装置，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ . geG,用于确定所述秘密信息的信息是θ e Fq,使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( a) 对应的索引设为cp(h(a))的情况下的、所述巡回群G的元f(a,cp(h(a))) · gEG。
19.如权利要求16至18的任一项所述的分散装置，其中，所述秘密信息是在将巡回群G的生成元设为g，将θ (i，β)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维基底向量设为b^= (Θ (i,l) -g,..., θ (i， η+ζ) · g) e 6η+ζ的情况下的、该基底向量V的集合(bA ...，bn+J)，其中i = 1，...， η+ζ，β = 1，…，η+ζ，η 彡 1，ζ 彡 1，所述秘密分散单元生成按各个所述子集合SUB ( a )独立地分别对各基底向量bj的元素θ (i，β) *geG进行了秘密分散的分散信息SH(i，β, a,h(a)) eG，所述分散信息 SH(a ,h(a))是所述分散信息SH(i，β，a，h(a)) e G的集合。
20.一种分散管理装置，具有分散秘密值生成单元，使用包含由各个子集合SUB(Ci)共享的共享值σ (α)的共同信息、以及按各个所述子集合SUB ( α )独立地对秘密信息进行秘密分散而得到的分散信息 SH( α，h ( α ))，通过共同运算来生成分散秘密值DSH( α，h ( α ))，并且输出该分散秘密值 DSH(a，h(a))，其中，该子集合SUB(ci)由Η(α)个分散管理装置PA ( α，1)，...，PA ( α， Η(α))构成，其中 α = 1，···，L，L 彡 2，h(a) = 1, . . . ,H(a),H(a)彡 2，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同。
21.如权利要求20所述的分散管理装置，其中，在互相不同的所述子集合SUB( α)中分别共享的所述共享值σ (α)互相独立。
22.如权利要求20或21所述的分散管理装置，其中，由所述分散管理装置PA(a，h(a))的所述分散秘密值生成单元分别进行的所述共同运算全部相同，其中a = 1, ... ,L0
23.如权利要求20所述的分散管理装置，其中，所述共同信息包含所述共享值ο (α)、以及从取得装置提供的在所有的所述分散管理装置PA(a，h(a))中共同的提供信息。
24.如权利要求23所述的分散管理装置，其中，所述提供信息是以所述有限域F,的元作为元素Wli的η维向量《一= (Wl,...,Wn)，其中 μ = 1,…，η,所述分散秘密值生成单元使用所述分散信息SH (i，β, a，h(a))、所述共享值σ (a) 以及所述η维向量w —来生成所述分散秘密值DSH(a，h ( a ))，所述分散秘密值DSH( a， h(a))是对于以 η+ζ 个分散信息 SH(i，l，a，h(a))，...，SH (i, η+ζ , a，h(a))作为元素的 η+ζ 维的分散基底向量 SHbi*(a，h(a)) = (SH(i，l，a，h( a ))，. . .，SH(i，η+ζ， a , h(a)) e 6η+ζ 的、DSH(a，h(a)) = σ ( a ) · { Σ μ = · SHb/(a , h(a))}+ Σ μ .n+1n+'SHb/(a,h(a)) eGn+i，其中 ζ 彡 1。
25.一种取得装置，具有复原单元，使用在将由Η( α)个分散管理装置PA(a，l)，. . . , PA( a , H( a ))构成的子集合设为SUB(a)的情况下的、与相同的所述子集合SUB(a)对应的多个分散秘密值 DSH(a , h(a))，通过该各个子集合SUB(ci)的复原处理来生成秘密复原值SUBSK( a )，得到该各个子集合SUB(ci)的所述秘密复原值SUBSK(a)，其中a = 1，. . .，L，L彡2，h( a ) =1，···，H(a)，H(a)彡 2;以及合成单元，使用所述秘密复原值SUBSK(a )来生成生成信息SK，并且输出该生成信息SK。
26.如权利要求25所述的取得装置，还具有输出单元，输出以所述有限域Ftl的元作为元素Wli的η维向量w — = (Wl,...,Wn)，其中μIj ... J Π j所述秘密复原值SUBSK(a)是在将由各个所述子集合SUB(a)共享的共享值设为 σ (a )，将巡回群 G 的生成元设为 g，将 θ (i，β) (i = 1, ... , η+ζ , β = 1, ... , η+ζ , η彡1，ζ彡1)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维的基底向量设为 C= (Θ (i,l) -g,... , θ ( ,η+ζ) -g) e 6η+ζ 的情况下的、SUBSK( α )=ο (α) - {Σ μ=>μ ·Κ*}+Σ μ=η+1η+ζΚ*"η+ζ。
27.如权利要求沈所述的取得装置，其中，所述合成单元计算所述生成信息SK= {(σ (1)+... + 0 (L))/L} · { Σ μ =InWll · b/}+ Σ μ =n+1n+ib/。
28.一种秘密分散方法，具有步骤(a)，分散装置按各个子集合SUB(ci)独立地对秘密信息进行秘密分散从而生成分散信息SH(a，h(a))，并且输出该分散信息SH(a，h ( α ))，其中，该子集合SUB ( α )由属于由Σ α =>( α )个分散管理装置PA ( α，h ( α ))构成的集合的H ( α )个分散管理装置 ΡΑ(α，1)，…，ΡΑ(α，Η(α))构成，其中 α = 1，· · ·，L，L 彡 2，h (α ) = 1，· · ·，Η( α )， Η(α)彡 2-MR步骤(b)，所述分散管理装置PA ( α，h ( α ))使用所述分散信息SH ( α，h ( α ))、以及包含由各个所述子集合SUB(ci)共享的共享值σ (α)的共同信息，通过共同运算来生成分散秘密值DSH(a，h(a))，并且输出该分散秘密值DSH(a，h(a))；步骤(c)，取得装置使用与相同的所述子集合SUB(ci)对应的多个所述分散秘密值 DSH(a , h(a))，通过各个子集合SUB(ci)的复原处理来生成秘密复原值SUBI ( a )，得到该各个子集合SUB ( a )的所述秘密复原值SUBSK ( a )；以及步骤(d)，所述取得装置使用所述秘密复原值SUBSK( α)来生成生成信息SK，并且输出该生成信息SK，在所述步骤(b)中，由属于相同的所述子集合SUB(Ci)的所述分散管理装置PA(a， h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB(a)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同。
29.一种分散装置的处理方法，具有 将秘密信息输入到分散装置的步骤；所述分散装置的第一部件按各个子集合SUB( α)独立地对所述秘密信息进行秘密分散从而生成分散信息SH(a，h(a))的步骤，其中，该子集合SUB(a)由H(a)个分散管理装置 PA(a，1)，···，PA(a，H(a))构成，其中 a = 1，· · ·，L，L 彡 2，h ( a ) = 1，· · ·， H(a),H(a)彡 2 ；以及所述分散装置的第二部件输出所述分散信息SH(a，h(a ))的步骤。
30.一种分散管理装置的处理方法，具有所述分散管理装置的第一部件使用包含由各个子集合SUB( α)共享的共享值0(a) 的共同信息、以及按各个所述子集合SUB ( a )独立地对秘密信息进行秘密分散而得到的分散信息SH(a，h(a))，通过共同运算来生成分散秘密值DSH(a，h(a))的步骤，其中，该子集合SUB(Ci)由!1(0)个分散管理装置？六(0，1)，...，？六(0，！1(0))构成，其中a = 1, . . . , L, L ^ 2, h(a ) = ，···，Η(α)，Η(α) ^ 2 ；以及所述分散管理装置的第二部件输出所述分散秘密值DSH(a，h(a))的步骤， 由属于相同的所述子集合SUB(Ci)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a， h(a))分别进行的所述共同运算互相相同。
31.一种取得装置的处理方法，具有所述取得装置的第一部件使用在将由H ( α )个分散管理装置PA ( α，1)，. . .，PA ( α， Η(α))构成的子集合设为SUB(ci)的情况下的、与相同的所述子集合SUB(ci)对应的多个分散秘密值DSH ( α，h ( α ))，通过该各个子集合SUB ( α )的复原处理来生成秘密复原值 SUBSK(a)，得到该各个子集合SUB(ci)的所述秘密复原值SUBSK ( α )的步骤，其中α = 1, . . . , L, L ^ 2, h(a ) = ，···，Η(α)，Η(α) ^ 2 ；以及所述取得装置的第二部件使用所述秘密复原值SUBSK ( a )来生成生成信息SK，并且输出该生成信息SK。
32.—种程序，用于使计算机作为权利要求16至19的任一项所述的分散装置发挥作用。
33.一种程序，用于使计算机作为权利要求20至M的任一项所述的分散管理装置发挥作用。
34.一种程序，用于使计算机作为权利要求25至27的任一项所述的取得装置发挥作用。
35.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求16至19的任一项所述的分散装置发挥作用的程序。
36.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求20至M的任一项所述的分散管理装置发挥作用的程序。
37.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求25至27的任一项所述的取得装置发挥作用的程序。
全文摘要
实现安全的秘密分散方式。按各个子集合SUB(α)独立地对秘密信息进行秘密分散从而生成分散信息SH(α，h(α))，分散管理装置PA(α，h(α))使用包含由各个子集合SUB(α)共享的共享值σ(α)的共同信息和分散信息SH(α，h(α))，通过共同运算来生成分散秘密值DSH(α，h(α))，取得装置使用与相同的子集合SUB(α)对应的多个分散秘密值DSH(α，h(α))，通过各个子集合SUB(α)的复原处理来生成秘密复原值SUBSK(α)，使用秘密复原值SUBSK(α)来生成生成信息SK。
文档编号G09C1/00GK102396012SQ20108001659
公开日2012年3月28日 申请日期2010年4月23日 优先权日2009年4月24日
发明者西卷陵, 铃木幸太郎 申请人:日本电信电话株式会社
技术领域：
本发明涉及秘密分散技术。
背景技术：
在保管秘密信息时，存在秘密信息的遗失或破坏的风险和被盗的风险。能够通过保管多个秘密信息来降低遗失或破坏的风险。但是，这种情况下被盗的风险增加。作为一起解决这些风险的方法之一，存在秘密分散法(SSS=Secret Sharing Scheme)(例如，参照非专利文献1、2)。秘密分散法是如下的方式根据秘密信息MSK生成多个分散信息(share information) SH(I),..., SH(N)，并将这些分散信息分散到多个分散管理装置PA(1)，...， PA(N)而进行管理，并且仅在这些分散信息SH(I)，...，SH(N)中能够取得规定数目以上的分散信息的情况下，能够复原秘密信息MSK。以下，表示秘密分散法的代表性的方式。[ (N, N)阈值秘密分散法](N, N)阈值秘密分散法是如下的方式如果提供所有的分散信息 SH(I)，. . .，SH(N)，则能够复原秘密信息MSK，但是，即使提供任意的N-I个分散信息 SH(Cp1),...,SH(Cpigi),也无法完全得到秘密信息MSK的信息。以下，表示其一例。■随机选择 SH1，...，SHim。■进行 SK = MSK- (SH1+. . . +SHnJ 的计算。■将各分散信息3!11，...，3!1,分散到多个分散管理装置？4(1)，...，？八(幻而进行管理。■如果提供全部的分散信息SH1, · · ·，SHn,则能够通过MSK = SH1+. . . +SHn的复原处理来复原秘密信息MSK。另外，用于从分散信息SH1, ...，SHn复原秘密信息MSK的运算MSK = SH1+. · · +SHn 是线型的。因此，在将各分散信息SH(I)，...，SH (N)和值σ作为被运算符而对各个分散信息进行相同的线型运算CALC，并将该计算结果作为各分散信息SH' (1)，. . .，SH' (N)而进行了复原处理的情况下，得到将秘密信息MSK和值σ作为被运算符而进行了该线型运算 CALC的结果。例如，在将SH' (1) = σ · SH(I)SH' (N) = σ -SH(N)作为各分散信息SH' (1)，· · ·，SH' (N)而执行了复原处理的情况下，得到式(1)。σ · SH(I)+. . . + 0 · SH(N)= σ · (SH(I)+. . . +SH(N))= σ . MSK …(1)另一方面，在将各分散信息SH⑴，...，SH(N)和互相独立的值ο (1)，...，ο (N) 作为被运算符而对各个分散信息进行相同的线型运算CALC，并将其结果作为各分散信息 SH' (1)，...，SH' (N)而执行了复原处理的情况下，通常无法得到将秘密信息MSK作为被运算符的运算结果。例如，将SH' (1) = σ (1) . SH⑴，· ·，SH' (N) = σ (N) · SH(N)作为各分散信息SH' (1)，. . .，SH' (N)而执行了复原处理的情况下，得到式(2)。σ ⑴· SH(I)+. ··+ σ (N) · SH(N) . . . (2)[ (K，N)阈值秘密分散法](K，N)阈值秘密分散法是如下的方式如果提供不相同的任意K个分散信息 SH(Cp1),...,SH(cpK)，则能够复原秘密信息MSK，但是，即使提供任意的K-I个分散信息 SH(Cp1),...,SH(Cpigi),也无法完全得到秘密信息MSK的信息。以下，表示其一例。■随机选择满足f(0) = MSK的K-I次多项式f(x)= ξ ο+ ξ 1 · X+ ξ 2 · Χ2+· . . + I K-I · Χ1"。即，设为 I0 = MSK,并随机选择 ξι; ... , ξ H。将分散信息设为 SHp = (p,f(p))(p = 1，···，Ν)。■在得到了不相同的任意K个分散信息SHC91),...,SH(9k) ((φι,...,φκ) C(l,...,N))的情况下，例如使用Lagrange的内插公式，能够通过如下的复原处理来复原秘密信息MSK。
权利要求
1.一种秘密分散系统，具有分散装置、Σ。=141(^0个分散管理装置？々((1，11((1))、以及取得装置，其中 α = 1，···，L，L 彡 2，h(a) = 1, . . . , H( a ), H( a )彡 2，其中，所述分散装置包括秘密分散单元，按各个子集合SUB ( a )独立地对秘密信息进行秘密分散从而生成分散信息SH(a，h(a))，并且输出该分散信息SH(a，h(a))，其中，该子集合SUB(Ci)由H(a) 个分散管理装置PA ( a，1)，...，PA ( a，H ( a ))构成， 所述分散管理装置PA ( a，h ( a ))包括分散秘密值生成单元，使用包含由各个所述子集合SUB(Ci)共享的共享值σ (α)的共同信息、以及所述分散信息SH(a，h(a))，通过共同运算来生成分散秘密值DSH(a， 匕(0))，并且输出该分散秘密值05!1((1，11((1))，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同， 所述取得装置包括复原单元，使用与相同的所述子集合SUB(Ci)对应的多个所述分散秘密值DSH(a， h ( a ))，通过各个子集合SUB ( a )的复原处理来生成秘密复原值SUBSK (α),得到该各个子集合SUB ( a )的所述秘密复原值SUBSK ( a )；以及合成单元，使用所述秘密复原值SUBSK ( a )来生成生成信息SK，并且输出该生成信息SK。
2.如权利要求1所述的秘密分散系统，其中，在互相不同的所述子集合SUB( α)中分别共享的所述共享值σ (α)互相独立。
3.如权利要求1或2所述的秘密分散系统，其中，由所述分散管理装置PA(a，h(a))的所述分散秘密值生成单元分别进行的所述共同运算全部相同，其中a = 1, ... ,L0
4.如权利要求3所述的秘密分散系统，其中， 所述共同运算是具有线型性的运算，所述合成单元对所述秘密复原值SUBSK ( a )进行线型结合来生成所述生成信息SK。
5.如权利要求1所述的秘密分散系统，其中，所述共同信息包含所述共享值ο (α)、以及从所述取得装置提供的在所有的所述分散管理装置PA(a，h(a))中共同的提供信息。
6.如权利要求1所述的秘密分散系统，其中，所述合成单元对所述秘密复原值SUBSK ( a )进行线型结合来生成所述生成信息SK。
7.如权利要求1所述的秘密分散系统，其中， 所述共同运算是具有线型性的运算。
8.如权利要求1所述的秘密分散系统，其中，所述秘密分散单元对至少一部分所述子集合SUB(a)，使用(R(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息3对(1，11((1))，其中，2彡1 ((1) < H(a),所述复原单元使用与相同的所述子集合SUB ( α )对应的R( α )个以上的所述分散秘密值DSH ( α，h ( α ))，生成该各个子集合SUB ( α )的秘密复原值SUBSK ( α )。
9.如权利要求8所述的秘密分散系统，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ . geG,用于确定所述秘密信息的信息是θ e Fq,使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( α， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( α) 对应的索引设为cp(h(a))的情况下的、所述巡回群G的元f(a,cp(h(a))) · gEG。
10.如权利要求8所述的秘密分散系统，其中， 所述秘密信息包括有限域F,的元θ，使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( a) 对应的索引设为cp(h(a))的情况下的、所述有限域Ftl的元f(a,cp(h(a)))eFq。
11.如权利要求1所述的秘密分散系统，其中，所述秘密分散单元对至少一部分所述子集合SUB(a)，使用(H(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息SH( a，h ( a ))，所述复原单元使用与相同的所述子集合SUB(a)对应的H(a)个所述分散秘密值 DSH ( a，h ( a ))，生成该各个子集合SUB ( a )的秘密复原值SUBSK ( a )。
12.如权利要求11所述的秘密分散系统，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ - geG,使用(H(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a))是满足 SH(a，l)+SH(a，2)+...+SH(a，H(a)) = θ .g e G 的所述巡回群 G 的元。
13.如权利要求11所述的秘密分散系统，其中， 所述秘密信息包括有限域F,的元θ，使用(Η(α)，Η(α))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a))是满足 SH(a，l)+SH(a，2)+. ..+SH(a，Η(α)) = θ e Fq 的所述有限域 Fq 的元。
14.如权利要求5至13的任一项所述的秘密分散系统，其中，所述秘密信息是在将巡回群G的生成元设为g，将θ (i，β)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维基底向量设为b^= (Θ (i,l) -g,..., θ (i， η+ζ) · g) e 6η+ζ的情况下的、该基底向量V的集合(bA ...，bn+J)，其中i = 1，...， η+ζ，β = 1，…，η+ζ，η 彡 1，ζ 彡 1，所述秘密分散单元生成按各个所述子集合SUB ( a )独立地分别对各基底向量bj的元素θ (i，β) *geG进行了秘密分散的分散信息SH(i，β, a,h(a)) eG，所述分散信息 SH(a ,h(a))是所述分散信息SH(i，β, a,h(a)) e G的集合，所述提供信息是以所述有限域F,的元作为元素Wli的η维向量《一= (Wl,...,Wn)，其中μ = 1,…，η,所述分散秘密值生成单元使用所述分散信息SH (i，β, a，h(a))、所述共享值σ (a) 以及所述η维向量w —来生成所述分散秘密值DSH(a，h ( a ))，所述分散秘密值DSH( a， h(a))是对于以 η+ζ 个分散信息 SH(i，l，a，h(a))，...，SH (i, η+ζ , a，h(a))作为元素的 η+ζ 维的分散基底向量 SHbi*(a，h(a)) = (SH(i，l，a，h( a ))，. . .，SH(i，η+ζ， a , h(a)) e 6η+ζ 的、DSH(a，h(a)) = σ ( a ) · { Σ μ = · SHb/(a , h(a))}+ Σ μ .n+1n+'SHb/(a,h(a)) e Gn+S所述秘密复原值 SUB SK(a)是 SUB SK(a) = σ (a) · { Σ μ=1\μ -b/j+Σ μ =η+it * 厂η+ζ η+1 βμ 匕 b 。
15.如权利要求14所述的秘密分散系统，其中，所述合成单元计算所述生成信息SK= {(σ (1)+... + 0 (L))/L} · { Σ μ =InWll · b/}+ Σ μ =n+1n+ib/。
16.一种分散装置，具有秘密分散单元，将秘密信息作为输入，按各个子集合SUB(a )独立地对所述秘密信息进行秘密分散从而生成分散信息SH( a，h ( a ))，并且输出该分散信息SH( a，h ( a ))，其中，该子集合SUB(Ci)由H(a)个分散管理装置PA(a，l)，. . . , PA( a , H( a ))构成，其中 a = 1, . . . , L, L ^ 2, h(a ) = 1, . . . , H( a ), H( a ) >2。
17.如权利要求16所述的分散装置，其中，所述秘密分散单元对至少一部分所述子集合SUB( a)，使用(R(a)，H(a))阈值秘密分散法，生成对所述秘密信息进行了秘密分散的分散信息3对(1，11((1))，其中，2彡1 ((1) < H(a )。
18.如权利要求17所述的分散装置，其中，所述秘密信息包括在将g设为巡回群G的生成元，将θ设为有限域Ftl的元的情况下的、所述巡回群G的元θ . geG,用于确定所述秘密信息的信息是θ e Fq,使用(R(a)，H(a))阈值秘密分散法而进行了秘密分散后的所述分散信息SH( a， h(a ))包括在将由所述有限域F,的元构成的变量设为X，将对预先决定的所述有限域F, 的元ω e F,满足f(a，ω) = θ的R(a)_l次的多项式设为f(a，x) e Fq，将与h( a) 对应的索引设为cp(h(a))的情况下的、所述巡回群G的元f(a,cp(h(a))) · gEG。
19.如权利要求16至18的任一项所述的分散装置，其中，所述秘密信息是在将巡回群G的生成元设为g，将θ (i，β)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维基底向量设为b^= (Θ (i,l) -g,..., θ (i， η+ζ) · g) e 6η+ζ的情况下的、该基底向量V的集合(bA ...，bn+J)，其中i = 1，...， η+ζ，β = 1，…，η+ζ，η 彡 1，ζ 彡 1，所述秘密分散单元生成按各个所述子集合SUB ( a )独立地分别对各基底向量bj的元素θ (i，β) *geG进行了秘密分散的分散信息SH(i，β, a,h(a)) eG，所述分散信息 SH(a ,h(a))是所述分散信息SH(i，β，a，h(a)) e G的集合。
20.一种分散管理装置，具有分散秘密值生成单元，使用包含由各个子集合SUB(Ci)共享的共享值σ (α)的共同信息、以及按各个所述子集合SUB ( α )独立地对秘密信息进行秘密分散而得到的分散信息 SH( α，h ( α ))，通过共同运算来生成分散秘密值DSH( α，h ( α ))，并且输出该分散秘密值 DSH(a，h(a))，其中，该子集合SUB(ci)由Η(α)个分散管理装置PA ( α，1)，...，PA ( α， Η(α))构成，其中 α = 1，···，L，L 彡 2，h(a) = 1, . . . ,H(a),H(a)彡 2，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同。
21.如权利要求20所述的分散管理装置，其中，在互相不同的所述子集合SUB( α)中分别共享的所述共享值σ (α)互相独立。
22.如权利要求20或21所述的分散管理装置，其中，由所述分散管理装置PA(a，h(a))的所述分散秘密值生成单元分别进行的所述共同运算全部相同，其中a = 1, ... ,L0
23.如权利要求20所述的分散管理装置，其中，所述共同信息包含所述共享值ο (α)、以及从取得装置提供的在所有的所述分散管理装置PA(a，h(a))中共同的提供信息。
24.如权利要求23所述的分散管理装置，其中，所述提供信息是以所述有限域F,的元作为元素Wli的η维向量《一= (Wl,...,Wn)，其中 μ = 1,…，η,所述分散秘密值生成单元使用所述分散信息SH (i，β, a，h(a))、所述共享值σ (a) 以及所述η维向量w —来生成所述分散秘密值DSH(a，h ( a ))，所述分散秘密值DSH( a， h(a))是对于以 η+ζ 个分散信息 SH(i，l，a，h(a))，...，SH (i, η+ζ , a，h(a))作为元素的 η+ζ 维的分散基底向量 SHbi*(a，h(a)) = (SH(i，l，a，h( a ))，. . .，SH(i，η+ζ， a , h(a)) e 6η+ζ 的、DSH(a，h(a)) = σ ( a ) · { Σ μ = · SHb/(a , h(a))}+ Σ μ .n+1n+'SHb/(a,h(a)) eGn+i，其中 ζ 彡 1。
25.一种取得装置，具有复原单元，使用在将由Η( α)个分散管理装置PA(a，l)，. . . , PA( a , H( a ))构成的子集合设为SUB(a)的情况下的、与相同的所述子集合SUB(a)对应的多个分散秘密值 DSH(a , h(a))，通过该各个子集合SUB(ci)的复原处理来生成秘密复原值SUBSK( a )，得到该各个子集合SUB(ci)的所述秘密复原值SUBSK(a)，其中a = 1，. . .，L，L彡2，h( a ) =1，···，H(a)，H(a)彡 2;以及合成单元，使用所述秘密复原值SUBSK(a )来生成生成信息SK，并且输出该生成信息SK。
26.如权利要求25所述的取得装置，还具有输出单元，输出以所述有限域Ftl的元作为元素Wli的η维向量w — = (Wl,...,Wn)，其中μIj ... J Π j所述秘密复原值SUBSK(a)是在将由各个所述子集合SUB(a)共享的共享值设为 σ (a )，将巡回群 G 的生成元设为 g，将 θ (i，β) (i = 1, ... , η+ζ , β = 1, ... , η+ζ , η彡1，ζ彡1)设为有限域Ftl的元，将以所述巡回群G的η+ζ个元作为元素的η+ζ维的基底向量设为 C= (Θ (i,l) -g,... , θ ( ,η+ζ) -g) e 6η+ζ 的情况下的、SUBSK( α )=ο (α) - {Σ μ=>μ ·Κ*}+Σ μ=η+1η+ζΚ*"η+ζ。
27.如权利要求沈所述的取得装置，其中，所述合成单元计算所述生成信息SK= {(σ (1)+... + 0 (L))/L} · { Σ μ =InWll · b/}+ Σ μ =n+1n+ib/。
28.一种秘密分散方法，具有步骤(a)，分散装置按各个子集合SUB(ci)独立地对秘密信息进行秘密分散从而生成分散信息SH(a，h(a))，并且输出该分散信息SH(a，h ( α ))，其中，该子集合SUB ( α )由属于由Σ α =>( α )个分散管理装置PA ( α，h ( α ))构成的集合的H ( α )个分散管理装置 ΡΑ(α，1)，…，ΡΑ(α，Η(α))构成，其中 α = 1，· · ·，L，L 彡 2，h (α ) = 1，· · ·，Η( α )， Η(α)彡 2-MR步骤(b)，所述分散管理装置PA ( α，h ( α ))使用所述分散信息SH ( α，h ( α ))、以及包含由各个所述子集合SUB(ci)共享的共享值σ (α)的共同信息，通过共同运算来生成分散秘密值DSH(a，h(a))，并且输出该分散秘密值DSH(a，h(a))；步骤(c)，取得装置使用与相同的所述子集合SUB(ci)对应的多个所述分散秘密值 DSH(a , h(a))，通过各个子集合SUB(ci)的复原处理来生成秘密复原值SUBI ( a )，得到该各个子集合SUB ( a )的所述秘密复原值SUBSK ( a )；以及步骤(d)，所述取得装置使用所述秘密复原值SUBSK( α)来生成生成信息SK，并且输出该生成信息SK，在所述步骤(b)中，由属于相同的所述子集合SUB(Ci)的所述分散管理装置PA(a， h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB(a)的所述分散管理装置PA(a，h(a))分别进行的所述共同运算互相相同。
29.一种分散装置的处理方法，具有 将秘密信息输入到分散装置的步骤；所述分散装置的第一部件按各个子集合SUB( α)独立地对所述秘密信息进行秘密分散从而生成分散信息SH(a，h(a))的步骤，其中，该子集合SUB(a)由H(a)个分散管理装置 PA(a，1)，···，PA(a，H(a))构成，其中 a = 1，· · ·，L，L 彡 2，h ( a ) = 1，· · ·， H(a),H(a)彡 2 ；以及所述分散装置的第二部件输出所述分散信息SH(a，h(a ))的步骤。
30.一种分散管理装置的处理方法，具有所述分散管理装置的第一部件使用包含由各个子集合SUB( α)共享的共享值0(a) 的共同信息、以及按各个所述子集合SUB ( a )独立地对秘密信息进行秘密分散而得到的分散信息SH(a，h(a))，通过共同运算来生成分散秘密值DSH(a，h(a))的步骤，其中，该子集合SUB(Ci)由!1(0)个分散管理装置？六(0，1)，...，？六(0，！1(0))构成，其中a = 1, . . . , L, L ^ 2, h(a ) = ，···，Η(α)，Η(α) ^ 2 ；以及所述分散管理装置的第二部件输出所述分散秘密值DSH(a，h(a))的步骤， 由属于相同的所述子集合SUB(Ci)的所述分散管理装置PA(a，h(a))分别使用的所述共同信息互相相同，由属于相同的所述子集合SUB( α)的所述分散管理装置PA(a， h(a))分别进行的所述共同运算互相相同。
31.一种取得装置的处理方法，具有所述取得装置的第一部件使用在将由H ( α )个分散管理装置PA ( α，1)，. . .，PA ( α， Η(α))构成的子集合设为SUB(ci)的情况下的、与相同的所述子集合SUB(ci)对应的多个分散秘密值DSH ( α，h ( α ))，通过该各个子集合SUB ( α )的复原处理来生成秘密复原值 SUBSK(a)，得到该各个子集合SUB(ci)的所述秘密复原值SUBSK ( α )的步骤，其中α = 1, . . . , L, L ^ 2, h(a ) = ，···，Η(α)，Η(α) ^ 2 ；以及所述取得装置的第二部件使用所述秘密复原值SUBSK ( a )来生成生成信息SK，并且输出该生成信息SK。
32.—种程序，用于使计算机作为权利要求16至19的任一项所述的分散装置发挥作用。
33.一种程序，用于使计算机作为权利要求20至M的任一项所述的分散管理装置发挥作用。
34.一种程序，用于使计算机作为权利要求25至27的任一项所述的取得装置发挥作用。
35.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求16至19的任一项所述的分散装置发挥作用的程序。
36.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求20至M的任一项所述的分散管理装置发挥作用的程序。
37.一种计算机可读取的记录介质，存储了用于使计算机作为权利要求25至27的任一项所述的取得装置发挥作用的程序。
全文摘要
实现安全的秘密分散方式。按各个子集合SUB(α)独立地对秘密信息进行秘密分散从而生成分散信息SH(α，h(α))，分散管理装置PA(α，h(α))使用包含由各个子集合SUB(α)共享的共享值σ(α)的共同信息和分散信息SH(α，h(α))，通过共同运算来生成分散秘密值DSH(α，h(α))，取得装置使用与相同的子集合SUB(α)对应的多个分散秘密值DSH(α，h(α))，通过各个子集合SUB(α)的复原处理来生成秘密复原值SUBSK(α)，使用秘密复原值SUBSK(α)来生成生成信息SK。
文档编号G09C1/00GK102396012SQ20108001659
公开日2012年3月28日 申请日期2010年4月23日 优先权日2009年4月24日
发明者西卷陵, 铃木幸太郎 申请人:日本电信电话株式会社
最新回复(0)