(57)【特許請求の範囲】
【請求項１】
N, Kが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり
K-1個の値v(k) (k=1,...,K-1)を選択する選択部と、
K-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を得る第１変換部と、
n(0), n(1),...,n(K)が互いに異なる値であり、値n(1),...,n(K-1)と前記集合Gの要素である秘密分散対象の値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)であり、値f(n(K))を得る計算部と、
(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得る第１内部分散部と、
(K, N)閾値秘密分散法Uに従って、前記値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を得る第２内部分散部と、
N個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を得る分散値生成部と、
を有し、
前記分散値Ti(α)のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項２】
請求項１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る第２変換部と、
F(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを得る復元部と、
を有するデータ復元装置。
【請求項３】
請求項１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(α) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元する第２内部復元部と、
v(κ)から変換分散値P(v(κ)) (κ∈{1,...,K-1})を得る第１変換分散値生成部と、
を有する分散データ変換装置。
【請求項４】
請求項１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(α)が含むK個のUλ(f(n(K)))から、変換分散値f(n(K))を得る第２変換分散値生成部を有する分散データ変換装置をさらに有する、分散データ変換装置。
【請求項５】
請求項１のデータ分散装置で得られた、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=P(v(k)) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式がF(x)であり、n(μ) (μ=1,...,K)と異なるn(η)に対応するF(n(η)) (η∈{K+1,...,N})を得る第３変換分散値生成部を有する分散データ変換装置。
【請求項６】
N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり
K-1個の値v(k) (k=1,...,K-1)を選択する選択部と、
rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を得る第１変換部と、
同一のrに対応する値nr(0), nr(1),...,nr(K）が互いに異なり、値nr(1),...,nr(K-1)と前記集合Gの要素である秘密分散対象の値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式がfr(x)であり、値fr(nr(K))を得る計算部と、
(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得る第１内部分散部と、
rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、前記値fr(nr(K))を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を得る第２内部分散部と、
V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが前記分散値Vk,i(v(k))であり、r (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を得る分散値生成部と、
を有し、
前記分散値Ti(αr)のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項７】
r (r=1,...,R)のそれぞれについて、請求項６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る第２変換部と、
r (r=1,...,R)のそれぞれについて、Fr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る復元部と、
を有するデータ復元装置。
【請求項８】
請求項６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元する第２内部復元部と、
r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値P(z(r, v(κ)) (κ∈{1,...,K-1})を得る第１変換分散値生成部と、
を有する分散データ変換装置。
【請求項９】
請求項６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から、変換分散値fr(nr(K)) (r=1,...,R)を得る第２変換分散値生成部を有する分散データ変換装置。
【請求項１０】
請求項６のデータ分散装置で得られた、K個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=P(z(r,v(k))) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式がFr(x)であり、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N})を得る第３変換分散値生成部を有する分散データ変換装置。
【請求項１１】
N, Kが2以上の整数であり、K≦Nであり、Gが或る集合であり、
K-1個の値v(k) (k=1,...,K-1)を選択する選択部と、
n(0), n(1),...,n(K)が互いに異なる値であり、値n(1),...,n(K-1)と前記集合Gの要素である秘密分散対象の値αとについてf(n(k))=v(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)であり、値f(n(K))を得る計算部と、
(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得る第１内部分散部と、
(K, N)閾値秘密分散法Uに従って、前記値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を得る第２内部分散部と、
N個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を得る分散値生成部と、
を有し、
前記分散値Ti(α)のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項１２】
請求項１１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る変換部と、
F(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを得る復元部と、
を有するデータ復元装置。
【請求項１３】
請求項１１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(α) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、変換分散値f(n(κ))=v(κ) (κ∈{1,...,K-1})を生成する第１変換分散値生成部を有する分散データ変換装置。
【請求項１４】
請求項１１のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(α)が含むK個のUλ(f(n(K)))から、変換分散値f(n(K))を得る第２変換分散値生成部を有する分散データ変換装置。
【請求項１５】
請求項１１のデータ分散装置で得られた、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=v(k) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式がF(x)であり、n(μ) (μ=1,...,K)と異なるn(η)に対応するF(n(η)) (η∈{K+1,...,N})を得る第３変換分散値生成部を有する分散データ変換装置。
【請求項１６】
N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合であり、
K-1個の値v(k) (k=1,...,K-1)を選択する選択部と、
同一のrに対応する値nr(0), nr(1),...,nr(K)が互いに異なり、rと値v(k)とに対応する値がz(r, v(k))であり、値nr(1),...,nr(K-1)と前記集合Gの要素である秘密分散対象の値αr∈Gとについてfr(nr(k))=z(r, v(k)) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式がfr(x)であり、値fr(nr(K))を得る計算部と、
(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得る第１内部分散部と、
rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、前記値fr(nr(K))を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を得る第２内部分散部と、
V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが前記分散値Vk,i(v(k))であり、r (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を得る分散値生成部と、
を有し、
前記分散値Ti(αr)のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項１７】
r (r=1,...,R)のそれぞれについて、請求項１６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応するK個の前記分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る変換部と、
r (r=1,...,R)のそれぞれについて、Fr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る復元部と、
を有するデータ復元装置。
【請求項１８】
請求項１６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元する第２内部復元部と、
r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値z(r, v(κ)) (κ∈{1,...,K-1})を得る第１変換分散値生成部と、
を有する分散データ変換装置。
【請求項１９】
請求項１６のデータ分散装置で得られたK個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から、変換分散値fr(nr(K)) (r=1,...,R)を得る第２変換分散値生成部を有する分散データ変換装置。
【請求項２０】
請求項１６のデータ分散装置で得られた、K個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=z(r,v(k)) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する前記分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式がFr(x)であり、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N})を得る第３変換分散値生成部を有する分散データ変換装置。
【請求項２１】
請求項１又は１１のデータ分散装置であって、
前記分散値Ui(f(n(K)))のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項２２】
請求項１又は１１のデータ分散装置であって、
前記分散値Vk,i(v(k)) (k=1,...,K-1)それぞれのデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項２３】
請求項６又は１６のデータ分散装置であって、
前記分散値Ur,i(fr(nr(K)))のデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項２４】
請求項６又は１６のデータ分散装置であって、
前記分散値Vr,k,i(v(k))それぞれのデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【請求項２５】
請求項１，６，１１，１６の何れかのデータ分散装置であって、
前記値v(k)の何れかのデータ量は、前記集合Gの要素のデータ量よりも小さい、データ分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散技術に関する。
【背景技術】
【０００２】
秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。分散値の総数をN、復元に必要な分散値の最小数をK（≦N）としたとき、N, K の値に制限がない方式とある方式とがある。
【０００３】
秘密分散の代表的な方式として、Shamir秘密分散方式（例えば、非特許文献１参照）がある。この方式では、pを素数、GF(p)を位数pの有限体として、値a∈GF(p)に対してf(0)=aとなるような、xを変数とするK-1次式f(x)から、aの分散値Si(a)=(i,f(i))（i=1,…,N）を得る。n1,…,nKを互いに異なる1以上N以下の整数として以下の関係が成り立つため、任意の異なるK個の分散値からaを復元できる。
【数１】
0005458116.tif 000002
【０００４】
また、秘密分散を要素技術とした秘密計算（マルチパーティ計算）方式もいくつか提案されている（例えば、非特許文献２等参照）。このような秘密計算方式では、各主体が保有するデータの分散値を他の主体に送り、当該分散値を他の主体に明かすことなく意中の計算を実行させる。計算を行った各主体からは計算結果の分散値が得られる。このような分散値がK個以上得られれば計算結果を復元でき、得られなければ計算結果を復元できない。非特許文献２では、Shamir秘密分散方式に従って得られる分散値を用いた秘密計算方式が開示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】A. Shamir, “How to share a secret,” Commu. ACM 22(11), pp. 612-613, 1979.
【非特許文献２】M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract),” STOC 1988, pp. 1-10, 1988.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
Shamir秘密分散方式では、aおよびその各分散値のデータ量を一定とすると、分散値の総データ量がそれぞれaのデータ量のおよそN倍となる。復元に必要な分散値の総データ量はそれぞれaのデータ量のおよそK倍となる。分散値のデータ量の増加は通信時間や保存データの増大につながるため、できるだけ分散値のデータ量を抑えることが望ましい。
本発明はこのような点に鑑みてなされたものであり、秘密分散方式の分散値のデータ量を抑えることを目的とする。
【課題を解決するための手段】
【０００７】
データ分散時には、K-1個の値v(k) (k=1,...,K-1)を選択し、K-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を得、N個の分散値Tk(α)=v(k) (k=1,...,K-1), Tθ(α)=f(n(θ)) (θ=K,...,N)を得る。ただし、N, Kが2以上の整数、K≦N、Gが或る集合であり、n(0), n(1),...,n(N)が互いに異なる値であり、値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)である。
【０００８】
データ復元時には、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(α)から、K個の互いに異なる値n(λ) (λ∈{1,...,N})に対応するK個の値f(n(λ))を得、K個の値f(n(λ))に対してF(n(λ))=f(n(λ)) (λ∈{1,...,N})を満たすK-1次式F(x)の関数値F(n(0))=αを得る。
【発明の効果】
【０００９】
本発明では、秘密分散方式の分散値のデータ量を抑えることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、秘密分散システムの機能構成を例示するブロック図である。
【図２】図２Ａは、データ分散装置の機能構成を例示するブロック図であり、図２Ｂは、データ記憶装置の機能構成を例示するブロック図である。
【図３】図３Ａは、データ復元装置の機能構成を例示するブロック図であり、図３Ｂは、分散データ変換装置の機能構成を例示するブロック図である。
【図４】図４Ａは、データ分散装置の処理を例示するためのフローチャートであり、図４Ｂは、分散データ変換装置の処理を例示するためのフローチャートであり、図４Ｃは、データ復元装置の処理を例示するためのフローチャートである。
【図５】図５Ａは、データ分散装置の処理を例示するためのフローチャートであり、図５Ｂは、分散データ変換装置の処理を例示するためのフローチャートであり、図５Ｃは、データ復元装置の処理を例示するためのフローチャートである。
【図６】図６は、秘密分散システムの機能構成を例示するブロック図である。
【図７】図７Ａは、データ分散装置の機能構成を例示するブロック図であり、図７Ｂは、データ記憶装置の機能構成を例示するブロック図である。
【図８】図８は、データ復元装置の機能構成を例示するブロック図である。
【図９】図９Ａ及び９Ｂは、分散データ変換装置の機能構成を例示するブロック図である。
【図１０】図１０は、分散データ変換装置の機能構成を例示するブロック図である。
【図１１】図１１は、データ分散装置の処理を例示するためのフローチャートである。
【図１２】図１２Ａ〜１２Ｃは、分散データ変換装置の処理を例示するためのフローチャートである。
【図１３】図１３は、データ復元装置の処理を例示するためのフローチャートである。
【図１４】図１４は、データ分散装置の処理を例示するためのフローチャートである。
【図１５】図１５Ａ〜１５Ｃは、分散データ変換装置の処理を例示するためのフローチャートである。
【図１６】図１６は、データ復元装置の処理を例示するためのフローチャートである。
【図１７】図１７は、秘密分散システムの機能構成を例示するブロック図である。
【図１８】図１８Ａは、データ分散装置の機能構成を例示するブロック図であり、図１８Ｂは、データ記憶装置の機能構成を例示するブロック図であり、図１８Ｃは、データ復元装置の機能構成を例示するブロック図である。
【図１９】図１９Ａは、データ分散装置の処理を例示するためのフローチャートであり、図１９Ｂは、データ復元装置の処理を例示するためのフローチャートである。
【図２０】図２０は、分散データ変換装置の機能構成を例示するブロック図である。
【図２１】図２１Ａは、データ分散装置の処理を例示するためのフローチャートであり、図２１Ｂは、分散データ変換装置の処理を例示するためのフローチャートであり、図２１Ｃは、データ復元装置の処理を例示するためのフローチャートである。
【図２２】図２２は、データ分散装置の機能構成を例示するブロック図である。
【図２３】図２３は、データ分散装置の処理を例示するためのフローチャートである。
【図２４】図２４Ａ及び２４Ｂは、分散データ変換装置の処理を例示するためのフローチャートである。
【図２５】図２５は、データ分散装置の処理を例示するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
〔第１実施形態〕
まず、第１実施形態の概要を説明する。
第１実施形態では、N, Kが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像である。集合Gは演算が定義された集合であり、集合Gは下記の処理が実行可能であれば任意で良く、例えば非特許文献１のように有限体GF(p)である。写像P(x)は、入力された「xに対応する値」に対して集合Gの要素を出力するものである。同一の「xに対応する値」には同一の「P(x)」が対応する。すなわち、写像P(x)は入力が等しければ出力も等しくなる、確定的な写像である。「xに対応する値」と「P(x)」とは一対一で対応してもよいし、しなくてもよい。「xに対応する値」は、値xそのものであってもよいし、xとその他の値との組み合わせ値であってもよい。写像P(x)の例はxをシードとして集合Gの要素を返す擬似乱数生成関数である。また例えば、xを秘密鍵として固定の平文に対して集合Gに属する暗号文を出力する共通鍵暗号関数をP(x)として用いることができる。「写像」は関数であってもよいし、アルゴリズムであってもよい。K=Nであってもよいし、K＜Nであってもよい。
【００１２】
第１実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とK-1個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、K-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を得、N個の分散値Tk(α)=v(k) (k=1,...,K-1), Tθ(α)=f(n(θ)) (θ=K,...,N)を得る。ただし、n(0), n(1),...,n(N)が互いに異なる値であり、値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)である。データ分散装置で得られたN個の分散値Ti(α) (i=1,...,N)は、例えばN個のデータ記憶部装置のそれぞれに提供され、格納される。
【００１３】
本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(α)から、K個の互いに異なる値n(λ) (λ∈{1,...,N})に対応するK個の値f(n(λ))を得る。例えば、本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)に分散値Tκ(α)=v(κ) (κ∈{1,...,K-1})が含まれる場合にf(n(κ))=P(v(κ))とする。データ復元装置は、K個の値f(n(λ))に対してF(n(λ))=f(n(λ)) (λ∈{1,...,N})を満たすK-1次式F(x)の関数値F(n(0))=αを得る。
【００１４】
本形態のK-1個の分散データ変換装置のそれぞれは、分散値Tκ(α)=v(κ) (κ∈{1,...,K-1})から変換分散値Sκ(α)=P(v(κ))を得る。このように得られる変換分散値Sk(α) (k=1,...,K-1)及び前述の分散値Tθ(α)=f(n(θ)) (θ=K,...,N)は、秘密計算の入力値として用いられる。秘密計算の具体例は、例えば非特許文献２などに開示されたShamir秘密分散に基づく秘密計算である。秘密計算は単項演算であってもよいし、多項演算であってもよい。
【００１５】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００１６】
＜構成＞
図１に例示するように、第１実施形態の秘密分散システム１は、データ分散装置１１０、N個のデータ記憶装置１２０−ｉ（i=1,...,N）、K-1個の分散データ変換装置１４０−ｋ（k=1,...,K-1）、及びデータ復元装置１３０を有する。データ分散装置１１０は、ネットワークや可搬型記録媒体などを経由して、N個のデータ記憶装置１２０−ｉ（i=1,...,N）に対して情報の提供が可能である。N個のデータ記憶装置１２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、K-1個の分散データ変換装置１４０−ｋ（k=1,...,K-1）と情報のやり取りが可能である。さらに、N個のデータ記憶装置１２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置１３０に対して情報の提供が可能である。
【００１７】
図２Ａに例示するように、本形態のデータ分散装置１１０は、入力部１１１、出力部１１２、メモリ１１３、制御部１１４、選択部１１５、変換部１１６、及び分散値生成部１１７を有する。本形態のデータ分散装置１１０は、制御部１１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００１８】
図２Ｂに例示するように、データ記憶装置１２０−λ（λ∈{1,...,N}）は、入力部１２１−λ、出力部１２２−λ、メモリ１２３ａ−λ、記憶部１２３ｂ−λ、制御部１２４−λ、及び秘密計算部１２７−λを有する。本形態のデータ記憶装置１２０−λは、制御部１２４−λの制御のもとで各処理を実行する。入力部１２１−λに入力されたデータや各処理で得られたデータはメモリ１２３ａ−λや記憶部１２３ｂ−λに格納され、メモリ１２３ａ−λや記憶部１２３ｂ−λに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００１９】
図３Ａに例示するように、本形態のデータ復元装置１３０は、入力部１３１、出力部１３２、メモリ１３３、制御部１３４、変換部１３５、及び復元部１３６を有する。本形態のデータ復元装置１３０は、制御部１３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２０】
図３Ｂに例示するように、本形態の分散データ変換装置１４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部１４４−κ、及び変換分散値生成部１４６−κを有する。本形態の分散データ変換装置１４０−κは、制御部１４４−κの制御のもとで各処理を実行する。入力部１４１−κに入力されたデータや各処理で得られたデータはメモリ１４３ａ−κや記憶部１４３ｂ−κに格納され、メモリ１４３ａ−κや記憶部１４３ｂ−κに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２１】
＜データ分散処理＞
図４Ａに例示するように、データ分散装置１１０（図２Ａ）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。値αの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。値αのデータ量、すなわち集合Gの要素のデータ量は、例えば1メガバイト以上である。
【００２２】
選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。選択部１１５は、逐一、ランダムにK-1個の値v(k) (k=1,...,K-1)を選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってK-1個の値v(k) (k=1,...,K-1)を選択してもよい。例えば、選択される値v(k) (k=1,...,K-1)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さいことが望ましい。安全性を考慮すると、値v(k)は、値v(k)から生成される値a(k)やP(x)から値v(k)を特定することが困難となる程度の値（全数探索による攻撃や現在の計算機の性能を考慮すれば、値v(k)は80ビット程度かそれ以上の乱数）とするのが望ましい。
【００２３】
値v(k) (k=1,...,K-1)は変換部１１６に入力される。変換部１１６は、入力された値v(k) (k=1,...,K-1)からK-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を計算し、当該K-1個の値a(k)=P(v(k)) (k=1,...,K-1)を出力する（ステップＳ１１３）。P(x)が擬似乱数生成関数の場合、値a(k)は擬似乱数となる。
【００２４】
入力部１１１に入力された値αと変換部１１６から出力されたK-1個の値a(k)=P(v(k)) (k=1,...,K-1)とは分散値生成部１１７に入力される。分散値生成部１１７は、これらを用いてN個の分散値Tk(α)=v(k) (k=1,...,K-1), Tθ(α)=f(n(θ)) (θ=K,...,N)を生成し、N個の分散値Ti(α) (i=1,...,N)を出力する。ただし、f(x)は値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式である。n(0), n(1),...,n(N)は互いに異なる（ステップＳ１１４）。分散値生成部１１７は、例えば、f(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式f(x)の各係数を求め、それらによって特定されるK-1次式f(x)にn(θ) (θ=K,...,N)を代入することでTθ(α)=f(n(θ)) (θ=K,...,N)を生成する。n(0), n(1),...,n(N)は分散値生成部１１７によって逐一定められてもよいし、予め定められた定数であってもよい。n(0), n(1),...,n(N)の例は互いに異なる整数であり、例えばn(0), n(1),...,n(N)は互いに異なる0以上N以下の整数である。具体例を示すとn(0)=0, n(i)=i (i=1,...,N)である。本形態では、分散値Ti(α)からiの値を特定でき、n(0), n(1),...,n(N)が予め定められた定数であり、iに対応するn(i)が特定できる場合を例示する。
【００２５】
N個の分散値Ti(α) (i=1,...,N)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=1,...,N)を出力する（ステップＳ１１５）。出力されたTi(α) (i=1,...,N)のそれぞれは、データ記憶装置１２０−ｉ (i=1,...,N)のそれぞれに提供される。例えば、分散値Tλ(α) (λ∈{1,...,N})は、ネットワーク等を経由して、対応するデータ記憶装置１２０−λ（図２Ｂ）に送信される。データ記憶装置１２０−λに提供された分散値Tλ(α)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【００２６】
＜分散データ変換処理＞
図４Ｂを用い、分散データ変換装置１４０−κ (κ∈{1,...,K-1})が実行する分散データ変換処理を説明する。
データ記憶装置１２０−κ (κ∈{1,...,K-1})の記憶部１２３ｂ−κに格納された分散値Tκ(α)=v(κ)は出力部１２２−κに送られ、出力部１２２−κは分散値Tκ(α)=v(κ)を出力する。出力された分散値Tκ(α)=v(κ)は、ネットワーク等を経由して、対応する分散データ変換装置１４０−κ（図３Ｂ）に送信される。分散データ変換装置１４０−κに提供された分散値Tκ(α)は入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ１４１−κ）。
【００２７】
変換分散値生成部１４６−κは、記憶部１４３ｂ−κから読み出した分散値Tκ(α)=v(κ) (κ∈{1,...,K-1})から変換分散値Sκ(α)=P(v(κ))を生成し、当該変換分散値Sκ(α)を出力する（ステップＳ１４２−κ）。変換分散値Sκ(α)は出力部１４２−κに入力され、出力部１４２−κは変換分散値Sκ(α)を出力する（ステップＳ１４３−κ）。出力された変換分散値Sκ(α)は、ネットワーク等を経由して、対応するデータ記憶装置１２０−κ（図２Ｂ）に送信される。変換分散値Sκ(α)は、対応するデータ記憶装置１２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【００２８】
＜分散値提供・秘密計算＞
K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置１２０−λ（図２Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(α)を出力するか、又は、秘密計算を行ってその結果を表す分散値Eλを出力する。
【００２９】
分散値Tλ(α)が出力される場合、データ記憶装置１２０−λの出力部１２２−λは、記憶部１２３ｂ−λから読み出された分散値Tλ(α)を出力する。この場合、K個の互いに異なるλ∈{1,...,N}に対応するすべてのデータ記憶装置１２０−λが分散値Tλ(α)を出力する。出力されたK個の分散値Tλ(α)は、ネットワーク等を経由してデータ復元装置１３０に送られる。
【００３０】
分散値Eλが出力される場合、データ記憶装置１２０−λの秘密計算部１２７−λが、記憶部１２３ｂ−λから読み出された分散値Tλ(α)又は変換分散値Sλ(α)を用いて秘密計算（例えば非特許文献２の秘密計算）を実行し、出力部１２２−λがその演算結果を表す分散値Eλを出力する。秘密計算に分散値Tλ(α)が用いられるのか変換分散値Sλ(α)が用いられるのかは、λ∈{1,...,K-1}であるのかλ∈{K,...,N}であるのかによる。λ∈{1,...,K-1}である場合には変換分散値Sλ(α)を用いて秘密計算が行われ、λ∈{K,...,N}である場合には分散値Tλ(α)を用いて秘密計算が行われる。この場合、K個の互いに異なるλ∈{1,...,N}に対応するすべてのデータ記憶装置１２０−λが秘密計算を行って分散値Eλを出力する。出力されたK個の分散値Eλは、ネットワーク等を経由してデータ復元装置１３０に送られる。
【００３１】
＜データ復元処理＞
図４Ｃに例示するように、データ復元装置１３０（図３Ａ）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)又はK個の分散値Eλが入力される（ステップＳ１３１）。制御部１３４は、K個の分散値Tλ(α)が入力されたか、K個の分散値Eλが入力されたかを判定する（ステップＳ１３２）。
【００３２】
ステップＳ１３２で、K個の分散値Tλ(α)が入力されたと判定された場合、これらK個の分散値Tλ(α)が変換部１３５に入力される。変換部１３５は、これらK個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(α)から、K個の互いに異なる値n(λ) (λ∈{1,...,N})に対応するK個の値f(n(λ))を生成し、K個の値f(n(λ))を出力する（ステップＳ１３３）。例えば、変換部１３５は、当該K個の分散値Tλ(α)が含む分散値Tκ(α)=v(κ) (κ∈{1,...,K-1})に対してf(n(κ))=P(v(κ))を計算して値f(n(κ))を出力し、当該K個の分散値Tλ(α)が含む分散値Tζ(α) (ζ∈{K,...,N})に対して値f(n(ζ))=Tζ(α)を出力する。
【００３３】
K個の値f(n(λ))は復元部１３６に入力される。復元部１３６は、これらK個の値f(n(λ))に対してF(n(λ))=f(n(λ)) (λ∈{1,...,N})を満たすK-1次式F(x)の関数値F(n(0))=αを生成し、それによって得られた値αを出力する（ステップＳ１３４）。K個の互いに異なる値n(λ)に対応する値f(n(λ))からはK-1次式F(x)が一義的に定まり、値αも一義的に定まる。K個の値f(n(λ))から関数値F(n(0))=αを得るための計算方法に限定はない。この計算方法の一つにラグランジュ(Lagrange)補間法を用いる方法がある。例えば、n(0)=0であり、n(1),...,n(N)が互いに異なる1以上N以下の整数であり、K個の互いに異なる値n(λ)がn(1),...,n(K)であるとすると、以下のように関数値F(0)=αを計算できる。
【数２】
0005458116.tif 000003
値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。ただし上記は関数Fの補間であり、集合Gによっては正しくαが復元できない場合があるので、集合Gに応じて適切にαの導出式を用いる必要がある。なおG=GF(p)であればラグランジュ補間法により正しく復元できる。
【００３４】
一方、ステップＳ１３２で、分散値Eλが入力されたと判定された場合、K個の分散値Eλが復元部１３６に入力される。復元部１３６は、所定の復元方法（例えば非特許文献２の復元方法）に従ってK個の分散値Eλから計算結果εを復元し、当該計算結果εを出力する（ステップＳ１３６）。計算結果εは出力部１３２に入力され、そこから出力される（ステップＳ１３７）。
【００３５】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。すなわち、本形態のN個の分散値Ti(α) (i=1,...,N)のうち、K-1個の分散値Tk(α) (k=1,...,K-1)は分散値Tk(α)=v(k) (k=1,...,K-1)である。これに対して、値α∈GをShamir秘密分散方式に従って秘密分散して得られる分散値のデータ量は集合Gの要素（１個の要素）のデータ量以上である。従って、分散値Tk(α)=v(k)のそれぞれのデータ量は、値α∈GをShamir秘密分散方式に従って秘密分散して得られる分散値よりもデータ量が小さい。分散値のデータ量をどの程度削減できるかは、v(k)のデータ量と集合Gの要素のデータ量との違いに依存する。例えば、値v(k) (k=1,...,K-1)の合計データ量が、集合GのK-1個の要素の合計データ量よりも小さいのであれば、本形態の分散値の総データ量は、従来の秘密分散方式の分散値の総データ量よりも小さくなる。値v(k) (k=1,...,K-1)の合計データ量が集合GのK-1個の要素の合計データ量よりも小さくなるのは、例えば、値v(k)の何れかのデータ量が集合Gの要素のデータ量よりも小さい場合や、値v(k)それぞれのデータ量が集合Gの要素のデータ量よりも小さい場合などである。さらに、値v(k)それぞれのデータ量が集合Gの要素のデータ量に対して無視できる程度に小さいのであれば、N個の分散値Ti(α) (i=1,...,N)のうちK-1個の分散値Tk(α)=v(k) (k=1,...,K-1)のデータ量は無視でき、N個の分散値Ti(α) (i=1,...,N)の合計データ量は、集合Gの(N-K+1)個の要素の合計データ量と同程度となる。
【００３６】
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【００３７】
なお、本形態では、分散値生成部１１７が、N個の分散値Ti(α) (i=1,...,K), Tθ(α)=f(n(θ)) (θ=K,...,N)を出力することとした。しかしながら、分散値生成部が、[n(k), Tk(α)=v(k)] (k=1,...,K-1),[n(θ), Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、分散データ変換装置が[n(k), Tk(α)]から[n(k), Sk(α)=P(v(k))]を生成して出力し、データ復元装置が[n(k), Tk(α)] (k=1,...,K-1),[n(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[n(λ), Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。
【００３８】
或いは、分散値生成部１１７が、[k, n(k), Tk(α)=v(k)] (k=1,...,K-1),[θ, n(θ), Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、分散データ変換装置が[k, n(k), Tk(α)]から[k, n(k), Sk(α)=P(v(k))]を生成して出力し、データ復元装置が[k, n(k), Tk(α)] (k=1,...,K-1),[θ, n(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[θ, n(λ), Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。
【００３９】
或いは、分散値生成部１１７が、[k, Tk(α)=v(k)] (k=1,...,K-1),[θ, Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、分散データ変換装置が[k, Tk(α)]から[k, Sk(α)=P(v(k))]を生成して出力し、データ復元装置が[k, Tk(α)] (k=1,...,K-1),[θ, Tθ(α)] (θ=K,...,N)の何れかK個の[λ Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。その他、分散値生成部１１７がTi(α)に加え、その他の付加情報を分散値として出力してもよい。
【００４０】
i, n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量よりも小さい。好ましくは、i, n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量に対して無視できる程度である（例えば、（i, n(i)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００４１】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は第１実施形態の変形例であり、同一の値v(k)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では第１実施形態との相違点を中心に説明する。第１実施形態と共通する処理部やステップには第１実施形態と同じ参照符号を用い、説明を簡略化する。
第２実施形態では、N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像である。本形態の集合G、写像P(x)の具体例は、第１実施形態で説明した集合G、写像P(x)の具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【００４２】
第２実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とK-1個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を得、k(k=1,...,K-1)のそれぞれについてR個のTk(α1),...,Tk(αR)の少なくとも１個をv(k)とし、Tθ(αr)=fr(nr(θ)) (θ=K,...,N)とし、rのそれぞれについてN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を得る。ただし、fr(x)は、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(N)が互いに異なる。同一の「rとv(k)との組み合わせ」には同一の「z(r, v(k))」が対応する。z(r, v(k))と「rとv(k)との組み合わせ(r, v(k))」とは一対一で対応してもよいし、しなくてもよい。
【００４３】
本形態のデータ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なる値nr(λ) (λ∈{1,...,N})に対応する値fr(nr(λ))を得、r (r=1,...,R)のそれぞれについて、当該fr(nr(λ))に対してFr(nr(λ))=fr(nr(λ)) (λ∈{1,...,N})を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る。例えば、本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)にv(κ) (κ∈{1,...,K-1})が含まれる場合にfr(nr(κ))=P(z(r,v(κ))) (r=1,...,R)とする。
【００４４】
分散データ変換装置のそれぞれは、分散値Tκ(αr’)=v(κ) (κ∈{1,...,K-1}, r’∈{1,...,R})から変換分散値Sκ(αr)=P(z(r, v(κ)))を得る。このように得られた変換分散値Sκ(αr)は、秘密計算の入力値として用いられる。秘密計算の具体例は、例えば非特許文献２などに開示されたShamir秘密分散に基づく秘密計算である。秘密計算は単項演算であってもよいし、多項演算であってもよい。
【００４５】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００４６】
＜構成＞
図１に例示するように、第２実施形態の秘密分散システム２は、データ分散装置２１０、N個のデータ記憶装置２２０−ｉ（i=1,...,N）、K-1個の分散データ変換装置２４０−ｋ（k=1,...,K-1）、及びデータ復元装置２３０を有する。データ分散装置２１０は、ネットワークや可搬型記録媒体などを経由して、N個のデータ記憶装置２２０−ｉ（i=1,...,N）に対して情報の提供が可能である。N個のデータ記憶装置２２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、K-1個の分散データ変換装置２４０−ｋ（k=1,...,K-1）と情報のやり取りが可能である。さらに、N個のデータ記憶装置２２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置２３０に対して情報の提供が可能である。
【００４７】
図２Ａに例示するように、本形態のデータ分散装置２１０は、入力部１１１、分割部２１１、出力部１１２、メモリ１１３、制御部２１４、選択部１１５、変換部２１６、及び分散値生成部２１７を有する。本形態のデータ分散装置２１０は、制御部２１４の制御のもとで各処理を実行する。
【００４８】
図２Ｂに例示するように、データ記憶装置２２０−λ（λ∈{1,...,N }）は、入力部１２１−λ、出力部１２２−λ、メモリ１２３ａ−λ、記憶部１２３ｂ−λ、制御部２２４−λ、及び秘密計算部２２７−λを有する。本形態のデータ記憶装置２２０−λは、制御部２２４−λの制御のもとで各処理を実行する。
【００４９】
図３Ａに例示するように、本形態のデータ復元装置２３０は、入力部１３１、出力部１３２、メモリ１３３、制御部２３４、変換部２３５、復元部２３６、及び結合部２３７を有する。本形態のデータ復元装置２３０は、制御部２３４の制御のもとで各処理を実行する。
【００５０】
図３Ｂに例示するように、本形態の分散データ変換装置２４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部２４４−κ、及び変換分散値生成部２４６−κを有する。本形態の分散データ変換装置２４０−κは、制御部２４４−κの制御のもとで各処理を実行する。
【００５１】
＜データ分散処理＞
図５Ａに例示するように、データ分散装置２１０（図２Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=1,...,R)に分割し、R個の値αr (r=1,...,R)を出力する（ステップＳ２１１）。例えば、分割部２１１は、R個の値αr(r=1,...,R)のビット結合値が値αとなるように分割を行う。
【００５２】
選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。
【００５３】
値v(k) (k=1,...,K-1)は変換部２１６に入力される。変換部２１６は、rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を生成し、当該(K-1)×R個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を出力する（ステップＳ２１３）。P(x)が擬似乱数生成関数の場合、値ar(k)は擬似乱数となる。
【００５４】
分割部２１１から出力されたR個の値αr(r=1,...,R)と変換部２１６から出力された(K-1)×R個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)とは分散値生成部２１７に入力される。分散値生成部２１７は、k(k=1,...,K-1)のそれぞれについてR個のTk(α1),...,Tk(αR)の少なくとも１個をv(k)とし、Tθ(αr)=fr(nr(θ)) (θ=K,...,N)とし、rのそれぞれについてN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を生成する。ただし、fr(x)は、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(N)が互いに異なる（ステップＳ２１４）。例えば、分散値生成部２１７は、fr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式fr(x)の各係数を求め、それらによって特定されるK-1次式fr(x)にnr(θ) (θ=K,...,N)を代入することでTθ(αr)=fr(nr(θ)) (θ=K,...,N)を生成する。異なるrに対応するfr(x)が異なってもよいし、同一であってもよい。nr(0), nr(1),...,nr(N)は分散値生成部２１７によって逐一定められてもよいし、予め定められた定数であってもよい。本形態では、分散値Ti(αr)からi及びrの値を特定でき、nr(0), nr(1),...,nr(N)が予め定められた定数である場合を例示する。異なるrに対応するnr(0)が異なってもよいし、同一であってもよい。異なるrに対応するnr(i)が異なってもよいし、同一であってもよい。nr(0), nr(1),...,nr(N)の例は互いに異なる整数であり、例えば互いに異なる1以上N以下の整数である。具体例を示すとnr(0)=0, nr(i)=i (i=1,...,N)である。また、R個のTk(α1),...,Tk(αR)のすべてがv(k)であってもよいし、R個のTk(α1),...,Tk(αR)の何れかのみがv(k)であってもよい。Tk(α1),...,Tk(αR)のうちv(k)でないものは空値であってもよいし、rやRなどのパラメータであってもよい。Tk(α1),...,Tk(αR)の一例は、Tk(α1)=v(k), Tk(α2)=...=Tk(αR)=φである。ただしφは空値を示す。
【００５５】
R×N個の分散値Ti(αr) (i=1,...,N, r=1,...,R)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を出力する（ステップＳ２１５）。出力された分散値Ti(αr) (i=1,...,N, r=1,...,R)のそれぞれは、データ記憶装置２２０−ｉ(i=1,...,N)のそれぞれに提供される。例えば、分散値Tλ(αr) (λ∈{1,...,N}, r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置２２０−λ（図２Ｂ）に送信される。データ記憶装置２２０−λに提供された分散値Tλ(αr) (r=1,...,R)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【００５６】
＜分散データ変換処理＞
図５Ｂを用い、分散データ変換装置２４０−κ(κ∈{1,...,K-1})が実行する分散データ変換処理を説明する。
データ記憶装置２２０−κ(κ∈{1,...,K-1})の記憶部１２３ｂ−κに格納された分散値Tκ(αr) (r=1,...,R)は出力部１２２−κに送られ、出力部１２２−κは分散値Tκ(αr) (r=1,...,R)を出力する。出力された分散値Tκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応する分散データ変換装置２４０−κ (κ∈{1,...,K-1})（図３Ｂ）に送信される。分散データ変換装置２４０−κに提供された分散値Tκ(αr) (r=1,...,R)は入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ２４１−κ）。
【００５７】
変換分散値生成部２４６−κは、記憶部１４３ｂ−κから読み出したv(κ)である分散値Tκ(αr’)=v(κ) (κ∈{1,...,K-1}, r’∈{1,...,R})から変換分散値Sκ(αr)=P(z(r, v(κ)))を生成し、当該変換分散値Sκ(αr)を出力する（ステップＳ２４２−κ）。出力された変換分散値Sκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置２２０−κ(r=1,...,R)（図２Ｂ）に送信される。変換分散値Sκ(αr) (r=1,...,R)は、対応するデータ記憶装置２２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【００５８】
＜分散値提供・秘密計算＞
K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置２２０−λ（図２Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(αr) (r=1,...,R)を出力するか、又は、秘密計算を行ってその結果を表す分散値Eλ,r (r=1,...,R)を出力する。
【００５９】
分散値Tλ(αr) (r=1,...,R)が出力される場合、データ記憶装置２２０−λの出力部１２２−λは、記憶部１２３ｂ−λから読み出された分散値Tλ(αr) (r=1,...,R)を出力する。この場合、K個の互いに異なるλ∈{1,...,N}に対応するすべてのデータ記憶装置２２０−λが分散値Tλ(αr) (r=1,...,R)を出力する。出力されたK×R個の分散値Tλ(αr) (r=1,...,R)は、ネットワーク等を経由してデータ復元装置２３０に送られる。
【００６０】
分散値Eλ,r (r=1,...,R)が出力される場合、データ記憶装置２２０−λの秘密計算部２２７−λが、記憶部１２３ｂ−λから読み出された分散値Tλ(αr) (r=1,...,R)又は変換分散値Sλ(αr) (r=1,...,R)を用い、r(r=1,...,R)のそれぞれについて秘密計算を実行し、出力部１２２−λがその演算結果を表す分散値Eλ,rを出力する。秘密計算に分散値Tλ(αr)が用いられるのか変換分散値Sλ(αr)が用いられるのかは、λ∈{1,...,K-1}であるのかλ∈{K,...,N}であるのかによる。λ∈{1,...,K-1}である場合には変換分散値Sλ(αr)を用いて秘密計算が行われ、λ∈{K,...,N}である場合には分散値Tλ(αr)を用いて秘密計算が行われる。この場合、K個の互いに異なるλ∈{1,...,N}に対応するすべてのデータ記憶装置２２０−λが秘密計算を行って分散値Eλ,rを出力する。出力されたK×R個の分散値Eλ,rは、ネットワーク等を経由してデータ復元装置２３０に送られる。
【００６１】
＜データ復元処理＞
図５Ｃに例示するように、データ復元装置２３０（図３Ａ）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (r=1,...,R)又は分散値Eλ,r (r=1,...,R)が入力される（ステップＳ２３１）。制御部２３４は、分散値Tλ(α)が入力されたか、分散値Eλが入力されたかを判定する（ステップＳ２３２）。
【００６２】
ステップＳ２３２で、分散値Tλ(αr)が入力されたと判定された場合、これらK×R個の分散値Tλ(αr)が変換部２３５に入力される。変換部２３５は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なる値nr(λ) (λ∈{1,...,N})に対応する値fr(nr(λ))を生成し、K×R個の値fr(nr(λ)) (λ∈{1,...,N}, r=1,...,R)を出力する（ステップＳ２３３）。例えば、変換部２３５は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)にTκ(αr’)=v(κ) (κ∈{1,...,K-1}, r’∈{1,...,R})が含まれる場合にfr(nr(κ))=P(z(r,v(κ)))を計算して値fr(nr(κ))を出力し、当該K個の分散値Tλ(αr)が含む分散値Tζ(αr) (ζ∈{K,...,N})に対して値fr(nr(ζ))=Tζ(αr)を出力する。
【００６３】
K×R個の値fr(nr(λ)) (λ∈{1,...,N}, r=1,...,R)は復元部２３６に入力される。復元部２３６は、r (r=1,...,R)のそれぞれについて、当該値fr(nr(λ))に対してFr(nr(λ))=fr(nr(λ)) (λ∈{1,...,N})を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを生成し、それによって得られた値αrを出力する（ステップＳ２３４）。r (r=1,...,R)のそれぞれについて、K個の互いに異なる値nr(λ)に対応する値fr(nr(λ))からはK-1次式Fr(x)が一義的に定まり、値αrも一義的に定まる。値fr(nr(λ))から関数値F(nr(0))=αrを得るための計算方法に限定はない。例えば、nr(0)=0であり、nr(1),...,nr(N)が互いに異なる1以上N以下の整数であり、K個の互いに異なる値nr(λ)がnr(1),...,nr(K)であるとすると、以下のように関数値F(0)=αrを計算できる（ラグランジュ補間法）。
【数３】
0005458116.tif 000004
【００６４】
値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr (r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。結合部２３７は、例えば、αr (r=0,...,R-1)のビット結合値を値αとして出力する。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【００６５】
一方、ステップＳ２３２で、分散値Eλ, rが入力されたと判定された場合、分散値Eλ,rが復元部２３６に入力される。復元部２３６は、所定の復元方法（例えば非特許文献２の復元方法）に従ってK個の分散値Eλ,rから計算結果εr(r=0,...,R-1)を復元し、当該計算結果εr(r=0,...,R-1)を出力する（ステップＳ２３６）。計算結果εr(r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値εr(r=0,...,R-1)を結合して値ε∈Gを生成し、当該値εを出力する（ステップＳ２３７）。結合部２３７は、例えば、εr (r=0,...,R-1)のビット結合値を値εとして出力する。値εは出力部１３２に入力され、そこから出力される（ステップＳ１３７）。
【００６６】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。すなわち、本形態の分散値Ti(αr) (i=1,...,N)のうち、分散値Tk(αr) (k=1,...,K-1)はv(k) (k=1,...,K-1)である。これに対して、値αr∈GをShamir秘密分散方式に従って秘密分散して得られる分散値のデータ量は集合Gの要素（１個の要素）のデータ量以上である。従って、分散値Tk(α)=v(k)のそれぞれのデータ量は、値α∈GをShamir秘密分散方式に従って秘密分散して得られる分散値よりもデータ量が小さい。分散値のデータ量をどの程度削減できるかは、v(k)のデータ量と集合Gの要素のデータ量との違いに依存する。例えば、値v(k) (k=1,...,K-1)の合計データ量が、集合GのK-1個の要素の合計データ量よりも小さいのであれば、本形態の分散値の総データ量は、従来の秘密分散方式の分散値の総データ量よりも小さくなる。値v(k) (k=1,...,K-1)の合計データ量が集合GのK-1個の要素の合計データ量よりも小さくなるのは、例えば、値v(k)の何れかのデータ量が集合Gの要素のデータ量よりも小さい場合や、値v(k)それぞれのデータ量が集合Gの要素のデータ量よりも小さい場合などである。さらに、値v(k)それぞれのデータ量が集合Gの要素のデータ量に対して無視できる程度に小さいのであれば、N個の分散値Ti(αr) (i=1,...,N)のうち分散値Tk(αr)=v(k) (k=1,...,K-1)のデータ量は無視でき、分散値Ti(αr) (i=1,...,N, r=1,...,R)の合計データ量は、集合GのR×(N-K+1)個の要素の合計データ量と同程度となる。一方で値αr (r=1,...,R)をShamir秘密分散方式に従って秘密分散して得られる分散値の合計データ量は、集合GのR×N個の要素の合計データ量と同程度となる。従って、この場合の本形態の分散値Ti(αr) (i=1,...,N, r=1,...,R)の合計データ量は、Shamir秘密分散方式での分散値の合計データ量の(N-K+1)/N倍となる。N≧Kであるため、この場合の本形態の分散値Ti(αr) (i=1,...,N, r=1,...,R)の合計データ量は、Shamir秘密分散方式での分散値の合計データ量よりも小さい。
【００６７】
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【００６８】
なお、本形態では、分散値生成部２１７が、分散値Tk(αr) (k=1,...,K-1, r=1,...,R), Tθ(αr)=fr(nr(θ)) (θ=K,...,N, r=1,...,R)を出力することとした。しかしながら、分散値生成部が、[nr(k), Tk(αr)] (k=1,...,K-1, r=1,...,R),[nr(θ), Tθ(αr)] (θ=K,...,N, r=1,...,R)を出力してもよい。この場合、分散データ変換装置が[nr(k), Tk(αr)]から[nr(k), Sk(αr)]を生成して出力し、データ復元装置が[nr(k), Tk(αr)] (k=1,...,K-1),[nr(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[nr(λ), Tλ(αr)] (λ∈{1,...,N})から値αrを復元してもよい。
【００６９】
或いは、分散値生成部が、 [r, nr(k), Tk(αr)] (k=1,...,K-1, r=1,...,R),[r, nr(θ), Tθ(αr)] (θ=K,...,N, r=1,...,R)を出力してもよい。この場合、分散データ変換装置が[r, nr(k), Tk(αr)]から[r, nr(k), Sk(αr)]を生成して出力し、データ復元装置が[r, nr(k), Tk(αr)] (k=1,...,K-1),[r, nr(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[r, nr(λ), Tλ(αr)] (λ∈{1,...,N})から値αrを復元してもよい。
【００７０】
或いは、分散値生成部が、[r, Tk(αr)] (k=1,...,K-1, r=1,...,R),[r, Tθ(αr)] (θ=K,...,N, r=1,...,R)を出力してもよい。この場合、分散データ変換装置が[r, Tk(αr)]から[r, Sk(αr)]を生成して出力し、データ復元装置が[r, Tk(αr)] (k=1,...,K-1),[r, Tθ(α)] (θ=K,...,N)の何れかK個の[r, Tλ(αr)] (λ∈{1,...,N})から値αrを復元してもよい。
【００７１】
或いは、分散値生成部が、 [r, k, Tk(αr)] (k=1,...,K-1, r=1,...,R),[r, θ, Tθ(αr)] (θ=K,...,N, r=1,...,R)を出力してもよい。この場合、分散データ変換装置が[r, k, Tk(αr)]から[r, k, Sk(αr)]を生成して出力し、データ復元装置が[r, k, Tk(αr)] (k=1,...,K-1),[r, θ, Tθ(α)] (θ=K,...,N)の何れかK個の[r, λ, Tλ(αr)] (λ∈{1,...,N})から値αrを復元してもよい。その他、分散値生成部２１７がTi(α)に加え、その他の付加情報を分散値として出力してもよい。
【００７２】
i, n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量よりも小さい。好ましくは、i, r, nr(i) (i=1,...,N, r=1,...,R)のデータ量は、集合Gの要素のデータ量に対して無視できる程度である（例えば、（i, r, nr(i)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００７３】
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。本形態は第１実施形態の変形例であり、第１実施形態の分散値が含んでいた要素をさらに秘密分散し、データ量をさらに削減するものである。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第３実施形態では、N, Kが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像である。本形態の集合G、写像P(x)の具体例は、第１実施形態で説明した集合G、写像P(x)の具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【００７４】
第３実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、K-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を得、値f(n(K))を得る。ただし、f(x)は、値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)である。n(0), n(1),...,n(K)は互いに異なる。データ分散装置は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得、(K, N)閾値秘密分散法Uに従って、値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を得、N個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を得る。どのような方式が(K, N)閾値秘密分散法Vkや(K, N)閾値秘密分散法Uとして用いられてもよい。(K, N)閾値秘密分散法Uには、１個のUi(f(n(K)))のデータ量が集合Gの１個の要素のデータ量よりも小さい方式が用いられることの望ましい。例えば、参考文献１「H.Krawczyk, “Secret sharing made short,” CRYPTO’93, pp.136-146, 1993.」に記載された方式を(K, N)閾値秘密分散法Uとして用いることが望ましい（詳細は後述）。分散値Vk,i(v(k)) (k=1,...,K-1)それぞれのデータ量が集合Gの要素のデータ量よりも小さいことが望ましい。(K, N)閾値秘密分散法V1,...,VKは、互いに同一の方式であってもよいし、そうでなくてもよい。(K, N)閾値秘密分散法Vkの例は、参考文献１に記載された方式や参考文献１に記載された方式である。
【００７５】
本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。例えば、データ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、値f(n(K))及びv(k) (k=1,...,K-1)を復元し、f(n(k))=P(v(k)) (k=1,...,K-1)とし、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。データ復元装置は、F(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを得る。
【００７６】
本形態の1,...,K-1番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、v(κ)から変換分散値P(v(κ)) (κ∈{1,...,K-1})を得る。本形態のK番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)が含むK個のUλ(f(n(K)))から、変換分散値f(n(K))を得る。本形態のK+1,...,N番目の分散データ変換装置は、n(μ) (μ=1,...,K)と異なるn(η)に対応するF(n(η)) (η∈{K+1,...,N})を得る。ただし、F(x)は、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=P(v(k)) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式である。このように得られる変換分散値は、秘密計算の入力値として用いられる。秘密計算の具体例は、例えば非特許文献２などに開示されたShamir秘密分散に基づく秘密計算である。秘密計算は単項演算であってもよいし、多項演算であってもよい。
【００７７】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００７８】
＜構成＞
図６に例示するように、第３実施形態の秘密分散システム３は、データ分散装置３１０、N個のデータ記憶装置３２０−ｉ（i=1,...,N）、N個の分散データ変換装置３４０−ｉ（i=1,...,N）、及びデータ復元装置３３０を有する。データ分散装置３１０は、ネットワークや可搬型記録媒体などを経由して、N個のデータ記憶装置３２０−ｉ（i=1,...,N）に対して情報の提供が可能である。N個のデータ記憶装置３２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置３４０−ｉ（i=1,...,N）と情報のやり取りが可能である。N個の分散データ変換装置３４０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、互いに情報の提供が可能である。さらに、N個のデータ記憶装置３２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置３３０に対して情報の提供が可能である。
【００７９】
図７Ａに例示するように、本形態のデータ分散装置３１０は、入力部１１１、出力部１１２、メモリ１１３、制御部３１４、選択部１１５、変換部１１６、計算部３１６、内部分散部３１８，３１９、及び分散値生成部３１７を有する。本形態のデータ分散装置３１０は、制御部３１４の制御のもとで各処理を実行する。
【００８０】
図７Ｂに例示するように、データ記憶装置３２０−λ（λ∈{1,...,N}）は、入力部１２１−λ、出力部１２２−λ、メモリ１２３ａ−λ、記憶部１２３ｂ−λ、制御部３２４−λ、及び秘密計算部３２７−λを有する。本形態のデータ記憶装置３２０−λは、制御部３２４−λの制御のもとで各処理を実行する。
【００８１】
図８に例示するように、本形態のデータ復元装置３３０は、入力部１３１、出力部１３２、メモリ１３３、制御部３３４、変換部３３５、及び復元部３３６を有する。変換部３３５は、内部復元部３３５ａ，３３５ｂを有する。本形態のデータ復元装置３３０は、制御部３３４の制御のもとで各処理を実行する。
【００８２】
図９Ａに例示するように、本形態の分散データ変換装置３４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部３４４−κ、内部復元部３４５−κ、及び変換分散値生成部３４６−κを有する。図９Ｂに例示するように、本形態の分散データ変換装置３４０−Ｋは、入力部１４１−Ｋ、出力部１４２−Ｋ、メモリ１４３ａ−Ｋ、記憶部１４３ｂ−Ｋ、制御部３４４−Ｋ、及び変換分散値生成部３４６−Ｋを有する。図１０に例示するように、本形態の分散データ変換装置３４０−η(η∈{K+1,...,N})は、入力部１４１−η、出力部１４２−η、メモリ１４３ａ−η、記憶部１４３ｂ−η、制御部３４４−η、及び変換分散値生成部３４６−ηを有する。
本形態の分散データ変換装置３４０−λは、制御部３４０−λの制御のもとで各処理を実行する。入力部３４０−λに入力されたデータや各処理で得られたデータはメモリ１４３ａ−λや記憶部１４３ｂ−λに格納され、メモリ１４３ａ−λや記憶部１４３ｂ−λに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００８３】
＜データ分散処理＞
図１１Ａに例示するように、データ分散装置３１０（図７Ａ）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。値v(k) (k=1,...,K-1)は変換部１１６に入力される。変換部１１６は、入力された値v(k) (k=1,...,K-1)からK-1個の値a(k)=P(v(k))∈G (k=1,...,K-1)を計算し、当該K-1個の値a(k)=P(v(k)) (k=1,...,K-1)を出力する（ステップＳ１１３）。
【００８４】
入力部１１１に入力された値αと変換部１１６から出力されたK-1個の値a(k)=P(v(k)) (k=1,...,K-1)とは計算部３１６に入力される。計算部３１６は、これらを用いて値f(n(K))を生成し、得られた値f(n(K))を出力する。ただし、f(x)は値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式である。n(0), n(1),...,n(K)が互いに異なる（ステップＳ３１４）。例えば、分散値生成部３１７は、f(n(k))=a(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式f(x)の各係数を求め、それらによって特定されるK-1次式f(x)にn(K)を代入することでf(n(K))を生成する。n(0), n(1),...,n(K)は分散値生成部３１７によって逐一定められてもよいし、予め定められた定数であってもよい。n(0), n(1),...,n(K)の例は互いに異なる整数であり、例えば互いに異なる0以上K以下の整数である。具体例を示すとn(0)=0, n(μ)=μ (μ=1,...,K)である。本形態では、n(0), n(1),...,n(K)が予め定められた定数であり、μに対応するn(μ)が特定できる場合を例示する。
【００８５】
選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)は内部分散部３１８に入力され、計算部３１６から出力された値f(n(K))は内部分散部３１９に入力される。内部分散部３１８は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)のそれぞれを秘密分散し、kのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を生成し、分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)を出力する（ステップＳ３１５）。内部分散部３１８は、例えばShamir秘密分散方式（例えば、非特許文献1参照）に従って、分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)を生成する。内部分散部３１９は、(K, N)閾値秘密分散法Uに従って、値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を生成し、分散値Ui(f(n(K))) (i=1,...,N)を出力する（ステップＳ３１６）。内部分散部３１９は、例えば、参考文献１に記載された方式に従って、分散値Ui(f(n(K))) (i=1,...,N)を生成する。(K, N)閾値秘密分散法Uに従って、τ=f(n(K))∈Gを秘密分散してN個の分散値Ui(τ)を生成する方法を例示する。
【００８６】
［(K, N)閾値秘密分散法Uの例示１］
内部分散部３１８は、共通鍵暗号方式の共通鍵d（例えば128ビットのデータ）を選択し、共通鍵dを用いて値τを暗号化し、共通鍵暗号方式の暗号文C(d, τ)を生成する。内部分散部３１８は、暗号文C(d, τ)をC(d, τ)=C(0)|C(1)|...|C(K-1)を満たすC(0),C(1),...,C(K-1)に分割する。ただし、C(0)|C(1)|...|C(K-1)は、C(0),C(1),...,C(K-1)のビット結合を表す。内部分散部３１８は、C(k)(k=0,...,K-1)をk次の係数としたK次多項式γ(x)=Συ=0K-1 C(k)・xυを定め、K次多項式γ(x)のN個の関数値γ(i) mod q (i=0,...,N-1)を求める。ここでqは、C(0),C(1),...,C(K-1)よりも大きな素数である。内部分散部３１８は、Shamir秘密分散方式等の(K, N)閾値秘密分散法に従って共通鍵dを秘密分散してN個の分散値SH(1,d),...,SH(N,d)を生成し、分散値Ui(τ)=(γ(i) mod q, SH(i,d))(i=0,...,N-1)を生成する。
［(K, N)閾値秘密分散法Uの例示２］
内部分散部３１８は、ξビット（例えば128ビット）のランダムな値d,d(0),...,d(N-2)∈{0,1}ξを選択し、dを共通鍵暗号方式の共通鍵とし、d(N-1)=d-d(0)-...-d(N-2) mod 2ξとする。内部分散部３１８は、共通鍵dを用いて値τを暗号化し、共通鍵暗号方式の暗号文C(d, τ)を生成する。内部分散部３１８は、暗号文C(d, τ)をC(d, τ)=C(0)|C(1)|...|C(K-1)を満たすC(0),C(1),...,C(K-1)に分割する。内部分散部３１８は、C(k)(k=0,...,K-1)をk次の係数としたK次多項式γ(x)=Συ=0K-1 C(k)・xυを定め、K次多項式γ(x)のN個の関数値γ(i) mod q (i=0,...,N-1)を求める。内部分散部３１８は、分散値Ui(τ)=(d(i mod N),...,d(i+N-2 (mod N)), γ(i) mod q)(i=0,...,N-1)を生成する（［(K, N)閾値秘密分散法Uの例示］終わり）。
【００８７】
分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)、及び分散値Ui(f(n(K))) (i=1,...,N)は、分散値生成部３１７に入力される。分散値生成部３１７は、これらを用いてN個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を生成し、分散値Ti(α) (i=1,...,N)を出力する（ステップＳ３１７）。
【００８８】
N個の分散値Ti(α) (i=0,...,N-1)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=0,...,N-1)を出力する（ステップＳ３１５）。出力された分散値Ti(α) (i=0,...,N-1)のそれぞれは、データ記憶装置３２０−ｉ(i=1,...,N)のそれぞれに提供される。例えば、分散値Tλ(α) (λ∈{1,...,N})は、ネットワーク等を経由して、対応するデータ記憶装置３２０−λ（図２Ｂ）に送信される。データ記憶装置３２０−λに提供された分散値Tλ(α)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【００８９】
＜分散データ変換処理＞
図１２Ａ〜１２Ｃを用い、分散データ変換装置３４０−λ(λ∈{1,...,N})が実行する分散データ変換処理を説明する。
［分散データ変換装置３４０−κ(κ∈{1,...,K-1}）の処理（図１２Ａ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置３２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(α)が含むVκ,λ(v(κ))が出力される。K個の互いに異なるλ∈{1,...,N}に対応するK個のVκ,λ(v(κ))は、ネットワーク等を経由して、分散データ変換装置３４０−κ(κ∈{1,...,K-1})（図９Ａ）の入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ３４１−κ）。
【００９０】
内部復元部３４５−κは、記憶部１４３ｂ−κに格納された、K個の互いに異なるλ∈{1,...,N}に対応するK個のVκ,λ(v(κ))からv(κ)を復元し、得られたv(κ)を出力する（ステップＳ３４２−κ）。例えば、Vκ,λ(v(κ))がShamir秘密分散方式に従って生成された分散値であるなら、内部復元部３４５−κは、ラグランジュ補間法等によってK個のVκ,λ(v(κ))に対してVκ,λ(v(κ))=f(v(κ))を満たすK-1次式f(x)を求め、f(0)=v(κ)を生成する。
【００９１】
v(κ)は変換分散値生成部３４６−κに入力される。変換分散値生成部３４６−κは、v(κ)から変換分散値Sκ(α)=P(v(κ))を計算し、当該変換分散値Sκ(α)=P(v(κ))を出力する（ステップＳ３４３−κ）。変換分散値Sκ(α)は出力部１４２−κに入力され、出力部１４２−κは変換分散値Sκ(α)を出力する（ステップＳ３４４−κ）。変換分散値Sκ(α)は、ネットワーク等を経由して、対応するデータ記憶装置３２０−κ（図７Ｂ）に送信される。変換分散値Sκ(α)は、データ記憶装置３２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【００９２】
［分散データ変換装置３４０−Ｋの処理（図１２Ｂ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置３２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(α)が含むUλ(f(n(K)))が出力される。K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))は、ネットワーク等を経由して、分散データ変換装置３４０−Ｋ（図９Ｂ）の入力部１４１−Ｋに入力され、記憶部１４３ｂ−Ｋに格納される（ステップＳ３４１−Ｋ）。
【００９３】
変換分散値生成部３４６−Ｋは、記憶部１４３ｂ−Ｋに格納された、K個のUλ(f(n(K)))からf(n(K))を復元し、得られたf(n(K))を変換分散値SK(α)=f(n(K))として出力する（ステップＳ３４２−Ｋ）。以下に、K個のUλ(f(n(K)))からf(n(K))を復元する方法を例示する。
【００９４】
［f(n(K))の復元方法の例示１］
前述の［(K, N)閾値秘密分散法Uの例示１］に従ってUλ(f(n(K)))が生成されている場合、変換分散値生成部３４６−Ｋは、K個のUλ(f(n(K)))=(γ(λ), SH(λ,d))が含むK個のγ(λ)から、qを法としたK次多項式γ(x)=Συ=0K-1 C(υ)・xυの係数C(0) mod q,C(1) mod q,...,C(K-1) mod qを求め、暗号文C(d, f(n(K)))=C(0) mod q |C(1) mod q |...|C(K-1) mod qを生成する。なお、係数C(0) mod q,C(1) mod q,...,C(K-1) mod qは(x, γ(x))=(k, γ(k))をK次多項式γ(x)に代入して得られる方程式を解くことで得られる。変換分散値生成部３４６−Ｋは、K個のUλ(f(n(K)))=(γ(λ), SH(λ,d))が含むK個のSH(λ,d)から共通鍵ｄを復元し、共通鍵ｄを用いて暗号文C(d, f(n(K)))を復号することで値f(n(K))を復元する。
【００９５】
［f(n(K))の復元方法の例示２］
前述の［(K, N)閾値秘密分散法Uの例示２］に従ってUλ(f(n(K)))が生成されている場合、変換分散値生成部３４６−Ｋは、K個の分散値Uλ(f(n(K)))=(d(λ mod N),...,d(λ+N-2 (mod N)), γ(λ))が含むK個のγ(λ)から、qを法としたK次多項式γ(x)の係数C(0) mod q,C(1) mod q,...,C(K-1) mod qを求め、暗号文C(d, f(n(K)))=C(0) mod q |C(1) mod q |...|C(K-1) mod qを生成する。変換分散値生成部３４６−Ｋは、K個の分散値Uλ(f(n(K)))=(d(λ mod N),...,d(λ+N-2 (mod N)), γ(λ))が含むd(λ mod N),...,d(λ+N-2 (mod N))から共通鍵ｄ=d(0)+...+d(N-1) mod 2ζを計算し、共通鍵ｄを用いて暗号文C(d, f(n(K)))を復号することで値f(n(K))を復元する（［f(n(K))の復元方法の例示］終わり）。
【００９６】
変換分散値SK(α)は出力部１４２−Ｋに入力され、出力部１４２−Ｋは変換分散値SK(α)を出力する（ステップＳ３４３−Ｋ）。変換分散値SK(α)は、ネットワーク等を経由して、対応するデータ記憶装置３２０−Ｋ（図７Ｂ）に送信される。変換分散値SK(α)は、データ記憶装置３２０−Ｋの入力部１２１−Ｋに入力され、記憶部１２３ｂ−Ｋに格納される。
【００９７】
［分散データ変換装置３４０−η(η∈{K+1,...,N}）の処理（図１２Ｃ）］
分散データ変換装置３４０−η (η∈{K+1,...,N}）（図１０）の変換分散値生成部３４６−ηは、n(1),...,n(K)と異なるn(η)に対応するF(n(η))を生成し、F(n(η))を変換分散値Sη(α)=F(n(η))として出力する。ただし、F(x)は、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=P(v(k)) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式である。
【００９８】
単純な方法は、K個のUλ(f(n(K)))とk (k=1,...,K-1)のそれぞれについてK個のVk,λ(v(k))とが変換分散値生成部３４６−ηに入力され、変換分散値生成部３４６−ηが、これらからf(n(μ)) (μ=1,...,K)を復元し、これらを用いて変換分散値Sη(α)=F(n(η))を生成する方法である。或いは、変換分散値生成部３４６−１〜Ｋから出力されたS1(α),...,SK(α)が変換分散値生成部３４６−ηに入力され、変換分散値生成部３４６−ηが、これらを用いて変換分散値Sη(α)=F(n(η))を生成する方法である。しかしながら、安全性の観点からは、分散データ変換装置３４０−ηにf(n(μ)) (μ=1,...,K)が知られることなく、分散データ変換装置３４０−ηが変換分散値Sη(α)=F(n(η))を生成できる方式が望ましい。すなわち、分散データ変換装置３４０−ηがf(n(η))以外のf(n(μ))(μ≠η)を得てしまうと、K台未満の分散データ変換装置３４０−ηが所定の処理を行うことによって値αを復元でき、秘密分散の要件を満たさない場合が生じ得るからである。以下では、分散データ変換装置３４０−ηがf(n(μ)) (μ=1,...,K)を復元することなく、変換分散値Sη(α)=F(n(η))を生成する方法を例示する。
【００９９】
分散データ変換装置３４０−η(η∈{K+1,...,N})（図１０）の変換分散値生成部３４６−ηは、Rndη,1+…+Rndη,K=0となるRndη,1,…,Rndη,Kを所定の範囲からランダムに選び、これらを出力部１４２−ηに入力する。出力部１４２−ηはRndη,1,…,Rndη,Kを出力する（ステップＳ３４１−η）。出力されたRndη,κ (κ∈{1,...,K-1})は、ネットワーク等を経由して分散データ変換装置３４０−κ（図９Ａ）に提供され、分散データ変換装置３４０−κの入力部１４１−κに入力されて記憶部１４３ｂ−κに格納される。出力されたRndη,Kは、ネットワーク等を経由して分散データ変換装置３４０−Ｋ（図９Ｂ）に提供され、分散データ変換装置３４０−Ｋの入力部１４１−Ｋに入力されて記憶部１４３ｂ−Ｋに格納される。
【０１００】
分散データ変換装置３４０−κ(κ∈{1,...,K-1})の変換分散値生成部３４６−κは、Qκ,η=f(n(κ))・Lκ(η)+Rndκ(Rndκ=Rnd1,κ+...+RndK,κ, η∈{K+1,...,N})を計算し、得られたQκ,ηを出力する。ただし、f(n(κ))=P(v(κ))であり、Lκ(η)は以下を満たす。
【数４】
0005458116.tif 000005
Qκ,ηは出力部１４２−κから出力され、ネットワーク等を経由して分散データ変換装置３４０−ηに提供される。
【０１０１】
同様に、分散データ変換装置３４０−Ｋの変換分散値生成部３４６−Ｋは、QK,η=f(n(K))・LK(η)+RndK(RndK=Rnd1,K+...+RndK,K,η∈{K+1,...,N})を計算し、得られたQK,ηを出力する。ただし、LK(η)は以下を満たす。
【数５】
0005458116.tif 000006
QK,ηは出力部１４２−Ｋから出力され、ネットワーク等を経由して分散データ変換装置３４０−ηに提供される。
【０１０２】
Q1,η,...,QK,ηは、分散データ変換装置３４０−η(η∈{K+1,...,N})（図１０）の入力部１４１−ηに入力され、記憶部１４３ｂ−ηに格納される（ステップＳ３４２−η）。変換分散値生成部３４６−ηは、以下のように変換分散値Sη(α)=F(n(η))を生成し、生成した変換分散値Sη(α)を出力する（ステップＳ３４３−η）。
【数６】
0005458116.tif 000007
【０１０３】
上記処理において、変換分散値生成部３４６−１〜Ｋから変換分散値生成部３４６−ηに提供されたQ1,η,...,QK,ηは、ランダムな値Rndη,1,…,Rndη,Kによってf(n(κ))・Lκ(n(η)) (κ∈{1,...,K-1})及びf(n(K))・LK(n(η))の情報が秘匿されている。一方で、RndK=Rnd1,K+...+RndK,K，Rndη,1+…+Rndη,K=0であるから、以下が成り立つ。
【数７】
0005458116.tif 000008
【０１０４】
変換分散値Sη(α)は出力部１４２−ηに入力され、出力部１４２−ηは変換分散値Sη(α)を出力する（ステップＳ３４４−η）。変換分散値Sη(α)は、ネットワーク等を経由して、対応するデータ記憶装置３２０−η(η∈{K+1,...,N})（図７Ｂ）に送信される。変換分散値Sη(α)は、データ記憶装置３２０−ηの入力部１２１−ηに入力され、記憶部１２３ｂ−ηに格納される。
＜分散値提供・秘密計算＞
第１実施形態と同様、K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置３２０−λ（図７Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(α)を出力するか、又は、秘密計算部３２７−λで秘密計算を行ってその結果を表す分散値Eλを出力する。これらはネットワーク等を経由してデータ復元装置３３０に送られる。
【０１０５】
＜データ復元処理＞
図１３に例示するように、データ復元装置３３０（図８）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)又はK個の分散値Eλが入力される（ステップＳ３３１）。制御部１３４は、K個の分散値Tλ(α)が入力されたか、K個の分散値Eλが入力されたかを判定する（ステップＳ３３２）。
【０１０６】
ステップＳ３３２で、K個の分散値Tλ(α)が入力されたと判定された場合、これらK個の分散値Tλ(α)が変換部３３５に入力される。変換部３３５は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。まず、変換部３３５の内部復元部３３５ａが、入力されたK個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、値f(n(K))及びv(k) (k=1,...,K-1)を復元し、値f(n(K))及びv(k) (k=1,...,K-1)を出力する（ステップＳ３３３）。この処理の具体例は、ステップＳ３４２−κ及びステップＳ３４２−Ｋで説明した通りである。
【０１０７】
値f(n(K))及びv(k) (k=1,...,K-1)は座標復元部３３５ｂに入力される。座標復元部３３５ｂは、v(k) (k=1,...,K-1)からP(v(k)) (k=1,...,K-1)を計算し、それらをf(n(k))=P(v(k)) (k=1,...,K-1)とする。座標復元部３３５ｂは、入力された値f(n(K))及び計算によって得られたf(n(k)) (k=1,...,K-1)からなるK個の値f(n(μ)) (μ=1,...,K)を出力する（ステップＳ３３４）。
【０１０８】
K個の値f(n(μ)) (μ=1,...,K)は復元部３３６に入力される。復元部３３６は、これらK個の値f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを生成し、それによって得られた値αを出力する（ステップＳ３３５）。この処理の具体例は、ステップＳ１３４で説明した通りである。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【０１０９】
一方、ステップＳ３３２で、分散値Eλが入力されたと判定された場合、復元部３３６で、第１実施形態で説明したステップＳ１３６，Ｓ１３７の処理が実行される。
【０１１０】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。例えば、値v(k) (k=1,...,K-1)それぞれのデータ量が集合Gの要素のデータ量に対して十分小さい場合（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）、本形態の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K))))のデータ量はUi(f(n(K)))のデータ量とみなすことができる。分散値Ui(f(n(K)))のデータ量が集合Gの要素のデータ量よりも小さいとすると、本形態の分散値Ti(α)のデータ量は従来のShamir秘密分散の分散値のデータ量よりも小さくなる。例えば、参考文献１の方式で分散値Ui(f(n(K)))が生成される場合、共通鍵dの分散値のデータ量を無視すれば、分散値Ui(f(n(K)))のデータ量は、集合Gの要素のデータ量のおよそ1/K倍とみなすことができる。そのため、分散値の総データ量は元データαのおよそN/K倍、復元に必要な分散値の総データ量は元データαのデータ量とほぼ等しくなり、何れもShamir秘密分散と比べてデータ量をおよそ1/K倍に削減できる。
【０１１１】
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【０１１２】
なお、本形態では、分散値生成部３１７が、N個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を出力することとした。しかしながら、分散値生成部が[n(1),...,n(K), Ti(α)] (i=1,...,N)を出力してもよい。分散データ変換装置が[n(i), Si(α)]を生成して出力し、データ復元装置が何れかK個の[n(1),...,n(K), Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。その他、分散値生成部３１７がTi(α)に加え、その他の付加情報を分散値として出力してもよい。
【０１１３】
n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量よりも小さい。好ましくは、n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量に対して無視できる程度である（例えば、（n(i)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
〔第４実施形態〕
次に、本発明の第４実施形態を説明する。本形態は第３実施形態の変形例であり、同一の値v(k)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第４実施形態では、N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像である。本形態の集合G、写像P(x)の具体例は、第１実施形態で説明した集合G、写像P(x)の具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【０１１４】
第４実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を得、値fr(nr(K))を得る。ただし、同一のrに対応する値nr(0), nr(1),...,nr(K）が互いに異なり、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式がfr(x)である。データ分散装置は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得、rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、値fr(nr(K）)を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を得、r (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を得る。ただし、V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが分散値Vk,i(v(k))である。どのような方式が(K, N)閾値秘密分散法Urとして用いられてもよい。(K, N)閾値秘密分散法Urには、１個のUr,i(fr(nr(K)))のデータ量が集合Gの１個の要素のデータ量よりも小さい方式が用いられることの望ましい。例えば、参考文献１に記載された方式を(K, N)閾値秘密分散法Urとして用いることが望ましい。(K, N)閾値秘密分散法U1,...,URは、互いに同一の方式であってもよいし、そうでなくてもよい。
【０１１５】
本形態のデータ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得、r (r=1,...,R)のそれぞれについて、Fr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る。例えば、データ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)から、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を復元し、r (r=1,...,R)のそれぞれについて、fr(nr(k))=P(z(r,v(k))) (k=1,...,K-1)とし、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る。
【０１１６】
本形態の1,...,K-1番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値P(z(r, v(κ)) (κ∈{1,...,K-1})を得る。本形態のK番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から、変換分散値fr(nr(K)) (r=1,...,R)を得る。本形態のK+1,...,N番目の分散データ変換装置は、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N})を得る。ただし、Fr(x)は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=P(z(r,v(k))) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式である。このように得られる変換分散値は、秘密計算の入力値として用いられる。秘密計算の具体例は、例えば非特許文献２などに開示されたShamir秘密分散に基づく秘密計算である。秘密計算は単項演算であってもよいし、多項演算であってもよい。
【０１１７】
本形態において好ましくは、分散値Ur,i(fr(nr(K)))のデータ量は、集合Gの要素のデータ量よりも小さい。本形態において好ましくは、分散値Vr,k,i(v(k))それぞれのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１１８】
＜構成＞
図６に例示するように、第４実施形態の秘密分散システム４は、データ分散装置４１０、N個のデータ記憶装置４２０−ｉ（i=1,...,N）、N個の分散データ変換装置４４０−ｉ（i=1,...,N）、及びデータ復元装置４３０を有する。データ分散装置４１０は、ネットワークや可搬型記録媒体などを経由して、N個のデータ記憶装置４２０−ｉ（i=1,...,N）に対して情報の提供が可能である。N個のデータ記憶装置４２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置４４０−ｉ（i=1,...,N）と情報のやり取りが可能である。N個の分散データ変換装置４４０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、互いに情報の提供が可能である。さらに、N個のデータ記憶装置４２０−ｉ（i=1,...,N）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置４３０に対して情報の提供が可能である。
【０１１９】
図７Ａに例示するように、本形態のデータ分散装置４１０は、入力部１１１、出力部１１２、メモリ１１３、制御部３１４、選択部１１５、分割部２１１、変換部２１６、内部分散部３１８，４１９、及び分散値生成部４１７を有する。本形態のデータ分散装置４１０は、制御部４１４の制御のもとで各処理を実行する。
【０１２０】
図７Ｂに例示するように、データ記憶装置４２０−λ（λ∈{1,...,N}）は、入力部１２１−λ、出力部１２２−λ、メモリ１２３ａ−λ、記憶部１２３ｂ−λ、制御部３２４−λ、及び秘密計算部４２７−λを有する。本形態のデータ記憶装置４２０−λは、制御部４２４−λの制御のもとで各処理を実行する。
【０１２１】
図８に例示するように、本形態のデータ復元装置４３０は、入力部１３１、出力部１３２、メモリ１３３、制御部４３４、変換部４３５、復元部４３６、及び結合部２３７を有する。変換部４３５は、内部復元部４３５ａ，４３５ｂを有する。本形態のデータ復元装置４３０は、制御部４３４の制御のもとで各処理を実行する。
【０１２２】
図９Ａに例示するように、本形態の分散データ変換装置４４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部４４４−κ、内部復元部４４５−κ、及び変換分散値生成部４４６−κを有する。図９Ｂに例示するように、本形態の分散データ変換装置４４０−Ｋは、入力部１４１−Ｋ、出力部１４２−Ｋ、メモリ１４３ａ−Ｋ、記憶部１４３ｂ−Ｋ、制御部４４４−Ｋ、及び変換分散値生成部４４６−Ｋを有する。図１０に例示するように、本形態の分散データ変換装置４４０−η(η∈{K+1,...,N})は、入力部１４１−η、出力部１４２−η、メモリ１４３ａ−η、記憶部１４３ｂ−η、制御部４４４−η、及び変換分散値生成部４４６−ηを有する。
本形態の分散データ変換装置４４０−λは、制御部４４０−λの制御のもとで各処理を実行する。入力部４４０−λに入力されたデータや各処理で得られたデータはメモリ１４３ａ−λや記憶部１４３ｂ−λに格納され、メモリ１４３ａ−λや記憶部１４３ｂ−λに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１２３】
＜データ分散処理＞
図１４に例示するように、データ分散装置３１０（図７Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=1,...,R)に分割し、R個の値αr (r=1,...,R)を出力する（ステップＳ２１１）。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。値v(k) (k=1,...,K-1)は変換部２１６に入力される。変換部２１６は、rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を生成し、当該(K-1)×R個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)を出力する（ステップＳ２１３）。
【０１２４】
分割部２１１から出力された個の値αr (r=1,...,R)と変換部２１６から出力された(K-1)×R個の値ar(k)=P(z(r, v(k))) (r=1,...,R, k=1,...,K-1)とは計算部４１６に入力される。計算部４１６は、これらを用いて値fr(nr(K)) (r=1,...,R)を生成し、得られた値fr(nr(K)) (r=1,...,R)を出力する。ただし、fr(x)は値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(K）が互いに異なる（ステップＳ４１４）。例えば、分散値生成部４１７は、fr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式fr(x)の各係数を求め、それらによって特定されるK-1次式fr(x)にnr(K)を代入することでfr(nr(K))を生成する。nr(0), nr(1),...,nr(K)は分散値生成部４１７によって逐一定められてもよいし、予め定められた定数であってもよい。nr(0), nr(1),...,nr(K)の例は互いに異なる整数であり、例えば互いに異なる0以上K以下の整数である。具体例を示すとnr(0)=0, nr(μ)=μ (μ=1,...,K)である。本形態では、nr(0), nr(1),...,nr(K)が予め定められた定数であり、μに対応するnr(μ)が特定できる場合を例示する。
【０１２５】
選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)は内部分散部３１８に入力され、計算部４１６から出力された値fr(nr(K)) (r=1,...,R)は内部分散部４１９に入力される。内部分散部３１８は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)のそれぞれを秘密分散し、kのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を生成し、分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)を出力する（ステップＳ３１５）。内部分散部４１９は、rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、値fr(nr(K))を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を生成し、分散値Ur,i(fr(nr(K))) (i=1,...,N, r=1,...,R)を出力する（ステップＳ４１６）。ステップＳ４１６では、例えば、τ=fr(nr(K))とおいて前述の［(K, N)閾値秘密分散法Uの例示１，２］の処理が実行される。
【０１２６】
分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)及び分散値Ur,i(fr(nr(K))) (i=1,...,N)は、分散値生成部４１７に入力される。分散値生成部４１７は、これらを用いてr (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を生成し、R×N個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を出力する（ステップＳ４１７）。ただし、V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが分散値Vk,i(v(k))である。R個のV1,k,i(v(k)),...,VR,k,i(v(k))のすべてがVk,i(v(k))であってもよいし、R個のV1,k,i(v(k)),...,VR,k,i(v(k))の何れかのみがVk,i(v(k))であってもよい。V1,k,i(v(k)),...,VR,k,i(v(k))のうちVk,i(v(k))でないものは空値であってもよいし、rやRなどのパラメータであってもよい。V1,k,i(v(k)),...,VR,k,i(v(k))の一例は、V1,k,i(v(k))=Vk,i(v(k)), V2,k,i(v(k))=...=VR,k,i(v(k)=φである。ただしφは空値を示す。
【０１２７】
R×N個の分散値Ti(αr) (i=1,...,N, r=1,...,R)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を出力する（ステップＳ４１８）。出力された分散値Ti(αr) (i=1,...,N, r=1,...,R)のそれぞれは、データ記憶装置４２０−ｉ(i=1,...,N)のそれぞれに提供される。例えば、分散値Tλ(αr) (λ∈{1,...,N}, r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置４２０−λ（図７Ｂ）に送信される。データ記憶装置４２０−λに提供された分散値Tλ(αr) (r=1,...,R)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【０１２８】
＜分散データ変換処理＞
図１５Ａ〜１５Ｃを用い、分散データ変換装置４４０−λ(λ∈{1,...,N})が実行する分散データ変換処理を説明する。
［分散データ変換装置４４０−κ(κ∈{1,...,K-1}）の処理（図１５Ａ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置４２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(αr) (r=1,...,R)が含むVr,κ,λ(v(κ)) (r=1,...,R)が出力される。K個の互いに異なるλ∈{1,...,N}に対応するVr,κ,λ(v(κ)) (r=1,...,R)は、ネットワーク等を経由して、分散データ変換装置４４０−κ(κ∈{1,...,K-1})（図９Ａ）の入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ４４１−κ）。
【０１２９】
内部復元部３４５−κは、記憶部１４３ｂ−κに格納された、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N}, r=1,...,R)が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、得られたv(κ)を出力する（ステップＳ４４２−κ）。Vκ,λ(v(κ))からv(κ) (κ∈{1,...,K-1})を復元する方法の具体例は第３実施形態で説明した通りである。
【０１３０】
v(κ)は変換分散値生成部４４６−κに入力される。変換分散値生成部４４６−κは、r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値P(z(r, v(κ)) (κ∈{1,...,K-1})を計算し、当該変換分散値Sκ(αr)=P(z(r, v(κ)) (r=1,...,R)を出力する。当該変換分散値Sκ(αr) (r=1,...,R)は出力部１４２−κに入力され、出力部１４２−κは変換分散値Sκ(αr) (r=1,...,R)を出力する（ステップＳ４４４−κ）。変換分散値Sκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置４２０−κ（図７Ｂ）に送信される。変換分散値Sκ(αr) (r=1,...,R)は、データ記憶装置４２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【０１３１】
［分散データ変換装置３４０−Ｋの処理（図１５Ｂ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置４２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(αr)が含むUr,λ(fr(nr(K))) (r=1,...,R)が出力される。K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K))) (r=1,...,R)は、ネットワーク等を経由して、分散データ変換装置４４０−Ｋ（図９Ｂ）の入力部１４１−Ｋに入力され、記憶部１４３ｂ−Ｋに格納される（ステップＳ４４１−Ｋ）。
【０１３２】
変換分散値生成部４４６−Ｋは、記憶部１４３ｂ−Ｋに格納された、K個の互いに異なるλ∈{1,...,N}に対応するUr,λ(fr(nr(K))) (r=1,...,R)からfr(nr(K)) (r=1,...,R)を復元し、得られたfr(nr(K))を変換分散値SK (αr)=fr(nr(K)) (r=1,...,R)として出力する（ステップＳ４４２−Ｋ）。fr(nr(K))を復元する処理の具体例は、前述の［f(n(K))の復元方法の例示１，２］のUλ(f(n(K)))，f(n(K))をUλ(fr(nr(K)))，fr(nr(K))にそれぞれ置換した処理である。
【０１３３】
変換分散値SK(αr) (r=1,...,R)は出力部１４２−Ｋに入力され、出力部１４２−Ｋは変換分散値SK (αr) (r=1,...,R)を出力する（ステップＳ４４３−Ｋ）。変換分散値SK(αr) (r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置４２０−Ｋ（図７Ｂ）に送信される。変換分散値SK (αr) (r=1,...,R)は、データ記憶装置４２０−Ｋの入力部１２１−Ｋに入力され、記憶部１２３ｂ−Ｋに格納される。
【０１３４】
［分散データ変換装置４４０−η(η∈{K+1,...,N}）の処理（図１５Ｃ）］
分散データ変換装置４４０−η (η∈{K+1,...,N}）（図１０）の変換分散値生成部４４６−ηは、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N}, r=1,...,R)を生成し、当該Fr(nr(η)) (η∈{K+1,...,N}, r=1,...,R)を変換分散値Sη(αr)=Fr(nr(η)) (r=1,...,R)として出力する。ただし、Fr(x)は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=P(z(r,v(k))) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式である。
【０１３５】
第３実施形態で説明したのと同様、Fr(nr(η))の生成方法に限定はない。しかしながら、安全性の観点から、分散データ変換装置４４０−ηにfr(nr(μ)) (μ=1,...,K, r=1,...,R)が知られることなく、分散データ変換装置４４０−ηが変換分散値Sη(αr)=Fr(nr(η))を生成できる方式が望ましい。以下に、分散データ変換装置４４０−ηがfr(nr(μ)) (μ=1,...,K, r=1,...,R)を復元することなく、変換分散値Sη(αr)=Fr(nr(η))を生成する方法を例示する。
【０１３６】
分散データ変換装置４４０−η(η∈{K+1,...,N})（図１０）の変換分散値生成部４４６−ηは、Rndr,η,1+…+Rndr,η,K=0となるRndr,η,1,…,Rndr,η,Kを所定の範囲からランダムに選び、これらを出力部１４２−ηに入力する。出力部１４２−ηはRndr,η,1,…,Rndr,η,Kを出力する（ステップＳ４４１−η）。出力されたRndr,η,κ (κ∈{1,...,K-1}, r=1,...,R)は、ネットワーク等を経由して分散データ変換装置４４０−κ（図９Ａ）に提供され、分散データ変換装置４４０−κの入力部１４１−κに入力されて記憶部１４３ｂ−κに格納される。出力されたRndr,η,κ (κ∈{1,...,K-1}, r=1,...,R)は、ネットワーク等を経由して分散データ変換装置４４０−Ｋ（図９Ｂ）に提供され、分散データ変換装置４４０−Ｋの入力部１４１−Ｋに入力されて記憶部１４３ｂ−Ｋに格納される。
【０１３７】
分散データ変換装置４４０−κ(κ∈{1,...,K-1})の変換分散値生成部４４６−κは、Qr,κ,η=fr(nr(κ))・Lr,κ(η)+Rndr,κ(Rndr,κ=Rndr,1,κ+...+Rndr,K,κ, η∈{K+1,...,N})を計算し、得られたQr,κ,ηを出力する。ただし、fr(nr(κ))=P(z(r,v(κ)))であり、Lr,κ(η)は以下を満たす。
【数８】
0005458116.tif 000009
Qr,κ,ηは出力部１４２−κから出力され、ネットワーク等を経由して分散データ変換装置４４０−ηに提供される。
【０１３８】
同様に、分散データ変換装置４４０−Ｋの変換分散値生成部４４６−Ｋは、Qr,K,η=fr,(nr,(K))・Lr,K(η)+Rndr,K(Rndr,K=Rndr,1,K+...+Rndr,K,K,η∈{K+1,...,N})を計算し、得られたQr,K,ηを出力する。ただし、Lr,K(η)は以下を満たす。
【数９】
0005458116.tif 000010
Qr,K,ηは出力部１４２−Ｋから出力され、ネットワーク等を経由して分散データ変換装置４４０−ηに提供される。
【０１３９】
Qr,1,η,...,Qr,K,ηは、分散データ変換装置４４０−η(η∈{K+1,...,N})（図１０）の入力部１４１−ηに入力され、記憶部１４３ｂ−ηに格納される（ステップＳ４４２−η）。変換分散値生成部４４６−ηは、以下のように変換分散値Sη(αr)=Fr(nr(η))を生成し、生成した変換分散値Sη(αr)を出力する（ステップＳ４４３−η）。
【数１０】
0005458116.tif 000011
【０１４０】
変換分散値Sη(αr)は出力部１４２−ηに入力され、出力部１４２−ηは変換分散値Sη(αr)を出力する（ステップＳ４４４−η）。変換分散値Sη(αr)は、ネットワーク等を経由して、対応するデータ記憶装置４２０−η(η∈{K+1,...,N})（図７Ｂ）に送信される。変換分散値Sη(αr)は、データ記憶装置４２０−ηの入力部１２１−ηに入力され、記憶部１２３ｂ−ηに格納される。
【０１４１】
＜分散値提供・秘密計算＞
第２実施形態と同様、K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置４２０−λ（図７Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(αr) (r=1,...,R)を出力するか、又は、秘密計算部４２７−λで秘密計算を行ってその結果を表す分散値Eλ,r(r=1,...,R)を出力する。これらはネットワーク等を経由してデータ復元装置４３０に送られる。
＜データ復元処理＞
図１６に例示するように、データ復元装置４３０（図８）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)又は分散値Eλ,rが入力される（ステップＳ４３１）。制御部１３４は、K個の分散値Tλ(αr)が入力されたか、K個の分散値Eλ,rが入力されたかを判定する（ステップＳ４３２）。
【０１４２】
ステップＳ４３２で、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (r=1,...,R)が入力されたと判定された場合、これら分散値Tλ(αr) (r=1,...,R)が変換部４３５に入力される。変換部４３５は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る。まず、変換部４３５の内部復元部４３５ａが、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)から、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を復元し、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を出力する。この処理の具体例は、ステップＳ４４２−κ及びステップＳ４４２−Ｋで説明した通りである。
【０１４３】
値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)は座標復元部４３５ｂに入力される。座標復元部４３５ｂは、r (r=1,...,R)のそれぞれについて、v(k) (k=1,...,K-1)からP(z(r,v(k))) (k=1,...,K-1)を計算し、それらをfr(nr(k))=P(z(r,v(k)))とする。座標復元部４３５ｂは、入力された値fr(nr(K)) (r=1,...,R)及び計算によって得られたfr(nr(k)) (k=1,...,K-1, r=1,...,R)からなる値fr(nr(μ)) (μ=1,...,K, r=1,...,R)を出力する（ステップＳ４３４）。
【０１４４】
値fr(nr(μ)) (μ=1,...,K, r=1,...,R)は復元部４３６に入力される。復元部４３６は、r (r=1,...,R)のそれぞれについて、これらの値fr(nr(μ)) (μ=1,...,K, r=1,...,R)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを生成し、それによって得られた値αrを出力する（ステップＳ４３５）。この処理の具体例は、ステップＳ２３４で説明した通りである。
【０１４５】
値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr (r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【０１４６】
一方、ステップＳ２３２で、分散値Eλ, rが入力されたと判定された場合、復元部４３６で、第２実施形態で説明したステップＳ２３６，Ｓ２３７，Ｓ１３７の処理が実行される。
【０１４７】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。さらに同一の値v(k)を複数の値αr (r=0,...,R-1)の秘密分散に流用することで分散値のデータ量をさらに削減できる。さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【０１４８】
なお、本形態では、分散値生成部４１７が、N個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (i=1,...,N, r=1,...,R)を出力することとした。しかしながら、分散値生成部が[nr(1),...,nr(K), Ti(αr)] (i=1,...,N, r=1,...,R)を出力してもよい。分散データ変換装置が[nr(i), Si(αr)]を生成して出力し、データ復元装置が何れかK個の[nr(1),...,nr(K), Tλ(αr)] (λ∈{1,...,N})から値αrを復元してもよい。その他、分散値生成部４１７がTi(αr)に加え、その他の付加情報を分散値として出力してもよい。
【０１４９】
〔第５実施形態〕
本形態は第１実施形態の変形例である。以下では第１実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第５実施形態では、N, Kが2以上の整数であり、K≦Nであり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像である。本形態の集合G、写像P(x)の具体例は、第１実施形態で説明した集合G、写像P(x)の具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【０１５０】
第１実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、N個の分散値Tk(α)=v(k) (k=1,...,K-1), Tθ(α)=f(n(θ)) (θ=K,...,N)を得る。ただし、f(x)は集合Gの要素である値α∈Gついてf(n(k))=v(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式である。n(0), n(1),...,n(N)が互いに異なる。データ分散装置で得られたN個の分散値Ti(α) (i=1,...,N)は、例えばN個のデータ記憶部装置のそれぞれに提供され、格納される。
【０１５１】
本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(α)から得られるK個の値f(n(λ))に対してF(n(λ))=f(n(λ)) (λ∈{1,...,N})を満たすK-1次式F(x)の関数値F(n(0))=αを得る。
【０１５２】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１５３】
＜構成＞
図１７に例示するように、第５実施形態の秘密分散システム５は、データ分散装置５１０、N個のデータ記憶装置５２０−ｉ（i=1,...,N）、及びデータ復元装置５３０を有する。データ分散装置５１０は、ネットワークや可搬型記録媒体などを経由して、N個のデータ記憶装置５２０−ｉ（i=1,...,N）との情報のやり取りが可能である。
【０１５４】
図１８Ａに例示するように、本形態のデータ分散装置５１０は、入力部１１１、出力部１１２、メモリ１１３、制御部１１４、選択部１１５、及び分散値生成部５１７を有する。本形態のデータ分散装置５１０は、制御部５１４の制御のもとで各処理を実行する。
【０１５５】
図１８Ｂに例示するように、データ記憶装置５２０−λ（λ∈{1,...,N}）は、入力部１２１−λ、出力部１２２−λ、メモリ１２３ａ−λ、記憶部１２３ｂ−λ、及び制御部５２４−λを有する。本形態のデータ記憶装置５２０−λは、制御部５２４−λの制御のもとで各処理を実行する。
【０１５６】
図１８Ｃに例示するように、本形態のデータ復元装置５３０は、入力部１３１、出力部１３２、メモリ１３３、制御部５３４、及び復元部５３６を有する。本形態のデータ復元装置５３０は、制御部５３４の制御のもとで各処理を実行する。
【０１５７】
＜データ分散処理＞
図１９Ａに例示するように、データ分散装置５１０（図１８Ａ）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。値αのデータ量、すなわち集合Gの要素のデータ量は、例えば1メガバイト以上である。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。値v(k)は、ある関数値FNC(v(k))から全数探索等の攻撃によってv(k)が特定されない程度のサイズであることが望ましい。例えば、値v(k)は80ビット程度かそれ以上の乱数であることが望ましい。
【０１５８】
入力部１１１に入力された値αと選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)とは分散値生成部５１７に入力される。分散値生成部５１７は、これらを用いてN個の分散値Tk(α)=v(k) (k=1,...,K-1), Tθ(α)=f(n(θ)) (θ=K,...,N)を生成し、N個の分散値Ti(α) (i=1,...,N)を出力する。ただし、f(x)は値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=v(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式である。n(0), n(1),...,n(N)は互いに異なる（ステップＳ５１４）。n(0), n(1),...,n(N)の例は第１実施形態と同じであり、例えば、n(0)=0, n(i)=i (i=1,...,N))である。
【０１５９】
N個の分散値Ti(α) (i=1,...,N)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=1,...,N)を出力する（ステップＳ５１５）。出力されたTi(α) (i=1,...,N)のそれぞれは、データ記憶装置５２０−ｉ (i=1,...,N)のそれぞれに提供される。例えば、分散値Tλ(α) (λ∈{1,...,N})は、ネットワーク等を経由して、対応するデータ記憶装置５２０−λ（図１８Ｂ）に送信される。データ記憶装置５２０−λに提供された分散値Tλ(α)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【０１６０】
＜データ復元処理＞
図１９Ｂに例示するように、データ復元装置５３０（図１８Ｃ）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)が入力される（ステップＳ５３１）。これらの分散値Tλ(α)は復元部５３６に入力され、復元部５３６は、これらの分散値Tλ(α)から得られるK個の値f(n(λ))に対してF(n(λ))=f(n(λ)) (λ∈{1,...,N})を満たすK-1次式F(x)の関数値F(n(0))=αを生成し、それによって得られた値αを出力する（ステップＳ５３２）。なお、前述のように、f(n(k))=Tk(α)=v(k) (k=1,...,K-1)であり、Tθ(α)=f(n(θ)) (θ=K,...,N)である。関数値F(n(0))=αの計算方法の一例は、第１実施形態で説明したラグランジュ補間法を用いる方法である（式(1)）。値αは出力部１３２に入力され、そこから出力される（ステップＳ５３３）。
【０１６１】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。すなわち、本形態のN個の分散値Ti(α) (i=1,...,N)のうち、K-1個の分散値Tk(α) (k=1,...,K-1)は分散値Tk(α)=v(k) (k=1,...,K-1)である。これに対して、値α∈GをShamir秘密分散方式に従って秘密分散して得られる分散値のデータ量は集合Gの要素（１個の要素）のデータ量以上である。従って、分散値Tk(α)=v(k)のそれぞれのデータ量は、値α∈GをShamir秘密分散方式に従って秘密分散して得られる分散値よりもデータ量が小さい。分散値のデータ量をどの程度削減できるかは、v(k)のデータ量と集合Gの要素のデータ量との違いに依存する。例えば、値v(k) (k=1,...,K-1)の合計データ量が、集合GのK-1個の要素の合計データ量よりも小さいのであれば、本形態の分散値の総データ量は、従来の秘密分散方式の分散値の総データ量よりも小さくなる。値v(k) (k=1,...,K-1)の合計データ量が集合GのK-1個の要素の合計データ量よりも小さくなるのは、例えば、値v(k)の何れかのデータ量が集合Gの要素のデータ量よりも小さい場合や、値v(k)それぞれのデータ量が集合Gの要素のデータ量よりも小さい場合などである。
【０１６２】
値v(k)それぞれのデータ量が集合Gの要素のデータ量に対して無視できる程度に小さいのであれば、N個の分散値Ti(α) (i=1,...,N)のうちK-1個の分散値Tk(α)=v(k) (k=1,...,K-1)のデータ量は無視でき、N個の分散値Ti(α) (i=1,...,N)の合計データ量は、集合Gの(N-K+1)個の要素の合計データ量と同程度となる。したがって、本形態の分散値の合計データ量は、Shamir秘密分散方式における分散値の合計データ量の(N-K+1)/N倍程度となる。N≧Kであるため、本形態の分散値の合計データ量はShamir秘密分散方式における分散値の合計データ量よりも小さい。このデータ量の削減効果は、データ分散装置からデータ記憶装置に送信するデータ量、およびデータ記憶装置の記憶データ量に直接影響する。この場合にデータ復元装置の受信データ量について考えると、本形態ではデータ復元装置がT1(α),…,TK-1(α)を受信する場合の受信データ量が最小となる。もう一つの受信データをTK(α)とすると、データ復元装置の受信データ量は集合Gの１個の要素のデータ量と同程度とみなせる。一方で、Shamir秘密分散方式ではデータ復元装置がK個の異なるf(i)を受信する。従って、本形態のデータ復元装置の受信データ量は、Shamir秘密分散方式における受信データ量のおよそ1/K倍とみなすことができ、データ量は削減されていることが分かる。
【０１６３】
その他、本形態の分散値Ti(α) (i=1,...,N)は、Shamir秘密分散に基づく秘密計算（例えば、非特許文献２参照）の入力値とし、当該秘密計算を実行することもできる。
【０１６４】
なお、本形態では、分散値生成部５１７が、N個の分散値Ti(α) (i=1,...,K), Tθ(α)=f(n(θ)) (θ=K,...,N)を出力することとした。しかしながら、分散値生成部が、[n(k), Tk(α)=v(k)] (k=1,...,K-1),[n(θ), Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、データ復元装置が[n(k), Tk(α)] (k=1,...,K-1),[n(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[n(λ), Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。
【０１６５】
或いは、分散値生成部が、[k, n(k), Tk(α)=v(k)] (k=1,...,K-1),[θ, n(θ), Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、データ復元装置が[k, n(k), Tk(α)] (k=1,...,K-1),[θ, n(θ), Tθ(α)] (θ=K,...,N)の何れかK個の[θ, n(λ), Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。
【０１６６】
或いは、分散値生成部が、[k, Tk(α)=v(k)] (k=1,...,K-1),[θ, Tθ(α)=f(n(θ))] (θ=K,...,N)を出力してもよい。この場合、データ復元装置が[k, Tk(α)] (k=1,...,K-1),[θ, Tθ(α)] (θ=K,...,N)の何れかK個の[λ Tλ(α)] (λ∈{1,...,N})から値αを復元してもよい。その他、分散値生成部１１７がTi(α)に加え、その他の付加情報を分散値として出力してもよい。
【０１６７】
i, n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量よりも小さい。好ましくは、i, n(i) (i=1,...,N)のデータ量は、集合Gの要素のデータ量に対して無視できる程度である（例えば、（i, n(i)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１６８】
〔第６実施形態〕
次に、本発明の第６実施形態を説明する。本形態は第２，５実施形態の変形例であり、同一の値v(k)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第６実施形態では、N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合である。本形態の集合Gの具体例は、第１実施形態で説明した集合Gの具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【０１６９】
第６実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とK-1個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、rと値v(k)とに対応する値をz(r, v(k))とし、rのそれぞれに対してK-1個の値ar(k)=z(r, v(k)) (r=1,...,R, k=1,...,K-1)を得、k(k=1,...,K-1)のそれぞれについてR個のTk(α1),...,Tk(αR)の少なくとも１個をv(k)とし、Tθ(αr)=fr(nr(θ)) (θ=K,...,N)とし、rのそれぞれについてN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を得る。ただし、fr(x)は、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=ar(k) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(N)が互いに異なる。  
【０１７０】
本形態のデータ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なる値nr(λ) (λ∈{1,...,N})に対応する値fr(nr(λ))を得、r (r=1,...,R)のそれぞれについて、当該値fr(nr(λ))に対してFr(nr(λ))=fr(nr(λ)) (λ∈{1,...,N})を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る。例えば、本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)にv(κ) (κ∈{1,...,K-1})が含まれる場合にfr(nr(κ))=z(r,v(κ)) (r=1,...,R)とする。
【０１７１】
分散データ変換装置のそれぞれは、分散値Tκ(αr’)=v(κ) (κ∈{1,...,K-1}, r’∈{1,...,R})から変換分散値Sκ(αr)=z(r, v(κ))を得る。このように得られた変換分散値Sκ(αr)は、秘密計算の入力値として用いられる。
【０１７２】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１７３】
＜構成＞
図１に例示するように、第６実施形態の秘密分散システム６は、第２実施形態の秘密分散システム２が有するデータ分散装置２１０、K-1個の分散データ変換装置２４０−ｋ（k=1,...,K-1）及びデータ復元装置２３０が、データ分散装置６１０、K-1個の分散データ変換装置６４０−ｋ（k=1,...,K-1）及びデータ復元装置６３０にそれぞれ置換されたものである。
【０１７４】
図１８Ａに例示するように、本形態のデータ分散装置６１０は、入力部１１１、分割部２１１、出力部１１２、メモリ１１３、制御部６１４、選択部１１５、及び分散値生成部６１７を有する。本形態のデータ分散装置６１０は、本形態のデータ分散装置６１０は、制御部６１４の制御のもとで各処理を実行する。
【０１７５】
図１８Ａに例示するように、本形態のデータ復元装置６３０は、入力部１３１、出力部１３２、メモリ１３３、制御部６３４、復元部６３６、及び結合部６３７を有する。本形態のデータ復元装置６３０は、制御部６３４の制御のもとで各処理を実行する。
【０１７６】
図２０に例示するように、本形態の分散データ変換装置６４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部２４４−κ、及び変換分散値生成部６４６−κを有する。本形態の分散データ変換装置６４０−κは、制御部６４４−κの制御のもとで各処理を実行する。
【０１７７】
＜データ分散処理＞
図２１Ａに例示するように、データ分散装置６１０（図１８Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=1,...,R)に分割し、R個の値αr (r=1,...,R)を出力する（ステップＳ２１１）。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。
【０１７８】
分割部２１１から出力されたR個の値αr(r=1,...,R)と選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)とは分散値生成部６１７に入力される。分散値生成部６１７は、k(k=1,...,K-1)のそれぞれについてR個のTk(α1),...,Tk(αR)の少なくとも１個をv(k)とし、Tθ(αr)=fr(nr(θ)) (θ=K,...,N)とし、rのそれぞれについてN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を生成する。ただし、fr(x)は、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=z(r, v(k)) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(N)が互いに異なる（ステップＳ６１４）。
【０１７９】
R×N個の分散値Ti(αr) (i=1,...,N, r=1,...,R)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を出力する（ステップＳ６１５）。出力された分散値Ti(αr) (i=1,...,N, r=1,...,R)のそれぞれは、データ記憶装置２２０−ｉ(i=1,...,N)のそれぞれに提供される。データ記憶装置２２０−λに提供された分散値Tλ(αr) (r=1,...,R)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【０１８０】
＜分散データ変換処理＞
図２１Ｂを用い、分散データ変換装置６４０−κ(κ∈{1,...,K-1})が実行する分散データ変換処理を説明する。
データ記憶装置６４０−κ(κ∈{1,...,K-1})の記憶部１２３ｂ−κに格納された分散値Tκ(αr) (r=1,...,R)は出力部１２２−κに送られ、出力部１２２−κは分散値Tκ(αr) (r=1,...,R)を出力する。出力された分散値Tκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応する分散データ変換装置６４０−κ (κ∈{1,...,K-1})（図２０）に送信される。分散データ変換装置６４０−κに提供された分散値Tκ(αr) (r=1,...,R)は入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ６４１−κ）。
【０１８１】
変換分散値生成部６４６−κは、記憶部１４３ｂ−κから読み出したv(κ)である分散値Tκ(αr’)=v(κ) (κ∈{1,...,K-1}, r’∈{1,...,R})から変換分散値Sκ(αr)=z(r, v(κ))を生成し、当該変換分散値Sκ(αr)を出力する（ステップＳ６４２−κ）。出力された変換分散値Sκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置２２０−κ(r=1,...,R)（図２Ｂ）に送信される。変換分散値Sκ(αr) (r=1,...,R)は、対応するデータ記憶装置２２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【０１８２】
＜データ復元処理＞
図２１Ｃに例示するように、データ復元装置６３０（図１８Ａ）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (r=1,...,R)又は分散値Eλ,r (r=1,...,R)が入力される（ステップＳ６３１）。制御部６３４は、分散値Tλ(α)が入力されたか、分散値Eλが入力されたかを判定する（ステップＳ６３２）。
【０１８３】
ステップＳ６３２で、分散値Tλ(αr)が入力されたと判定された場合、これらK×R個の分散値Tλ(αr)が復元部６３６に入力される。復元部６３６は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なる値nr(λ) (λ∈{1,...,N})に対応するK個の値fr(nr(λ))を得る。この際、復元部６３６は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)にv(κ) (κ∈{1,...,K-1})が含まれる場合にfr(nr(κ))=z(r,v(κ)) (r=1,...,R)とする（ステップＳ６３３）。復元部６３６は、K個の値fr(nr(λ))に対してFr(nr(λ))=fr(nr(λ)) (λ∈{1,...,N})を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを生成し、値αr(r=1,...,R)を出力する（ステップＳ６３４）。関数値Fr(nr(0))=αrの生成には、例えば、ラグランジュ補間法等を用いる（式(2)）。値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr(r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。一方、ステップＳ６３２で、分散値Eλ, rが入力されたと判定された場合、第２実施形態で説明したステップＳ２３６、Ｓ２３７、Ｓ１３７の処理が実行される。
【０１８４】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。第２実施形態と同様、分散値生成部がTi(α)に加え、nr(i)，i，rその他の付加情報を分散値として出力してもよい。
〔第７実施形態〕
次に、本発明の第７実施形態を説明する。本形態は第３，５実施形態の変形例であり、第５実施形態の分散値が含んでいた要素をさらに秘密分散し、データ量をさらに削減するものである。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第７実施形態では、N, Kが2以上の整数であり、K≦Nであり、Gが或る集合である。本形態の集合Gの具体例は、第１実施形態で説明した具体例と同じである。K=Nであってもよいし、K＜Nであってもよい。
【０１８５】
第７実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、値f(n(K))を得る。ただし、f(x)は、値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=v(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式がf(x)である。n(0), n(1),...,n(K)は互いに異なる。データ分散装置は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得、(K, N)閾値秘密分散法Uに従って、値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を得、N個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を得る。(K, N)閾値秘密分散法Vkや(K, N)閾値秘密分散法Uの具体例は、第３実施形態で説明した通りである。
【０１８６】
本形態のデータ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。例えば、データ復元装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、値f(n(K))及びv(k) (k=1,...,K-1)を復元し、f(n(k))=v(k) (k=1,...,K-1)とし、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。データ復元装置は、F(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを得る。
【０１８７】
本形態の1,...,K-1番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、v(κ)から変換分散値P(v(κ)) (κ∈{1,...,K-1})を得る。本形態のK番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)が含むK個のUλ(f(n(K)))から、変換分散値f(n(K))を得る。本形態のK+1,...,N番目の分散データ変換装置は、n(μ) (μ=1,...,K)と異なるn(η)に対応するF(n(η)) (η∈{K+1,...,N})を得る。ただし、F(x)は、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=v(k) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式である。このように得られる変換分散値は、秘密計算の入力値として用いられる。
【０１８８】
本形態において好ましくは、値v(k) (k=1,...,K-1)の合計データ量は、集合GのK-1個の要素の合計データ量よりも小さい。本形態において好ましくは、値v(k)の何れかのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１８９】
＜構成＞
図６に例示するように、第７実施形態の秘密分散システム７は、第３実施形態の秘密分散システム３のデータ分散装置３１０、N個の分散データ変換装置３４０−ｉ（i=1,...,N）及びデータ復元装置３３０が、データ分散装置７１０、N個の分散データ変換装置７４０−ｉ（i=1,...,N）及びデータ復元装置７３０にそれぞれ置換されたものである。
【０１９０】
図２２に例示するように、本形態のデータ分散装置７１０は、入力部１１１、出力部１１２、メモリ１１３、制御部７１４、選択部１１５、内部分散部３１８，７１９、及び分散値生成部７１７を有する。本形態のデータ分散装置７１０は、制御部７１４の制御のもとで各処理を実行する。
【０１９１】
図８に例示するように、本形態のデータ復元装置７３０は、入力部１３１、出力部１３２、メモリ１３３、制御部７３４、変換部７３５、及び復元部７３６を有する。変換部７３５は、内部復元部７３５ａ，７３５ｂを有する。本形態のデータ復元装置７３０は、制御部７３４の制御のもとで各処理を実行する。
【０１９２】
図９Ａに例示するように、本形態の分散データ変換装置７４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部３４４−κ、内部復元部７４５−κ、及び変換分散値生成部７４６−κを有する。図９Ｂに例示するように、本形態の分散データ変換装置７４０−Ｋは、入力部１４１−Ｋ、出力部１４２−Ｋ、メモリ１４３ａ−Ｋ、記憶部１４３ｂ−Ｋ、制御部７４４−Ｋ、及び変換分散値生成部７４６−Ｋを有する。図１０に例示するように、本形態の分散データ変換装置７４０−η(η∈{K+1,...,N})は、入力部１４１−η、出力部１４２−η、メモリ１４３ａ−η、記憶部１４３ｂ−η、制御部７４４−η、及び変換分散値生成部７４６−ηを有する。本形態の分散データ変換装置３４０−λは、制御部３４０−λの制御のもとで各処理を実行する。
【０１９３】
＜データ分散処理＞
図２３に例示するように、データ分散装置７１０（図２２）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。
【０１９４】
入力部１１１に入力された値αと選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)とは計算部７１６に入力される。計算部７１６は、これらを用いて値f(n(K))を生成し、得られた値f(n(K))を出力する。ただし、f(x)は値n(1),...,n(K-1)と集合Gの要素である値α∈Gとについてf(n(k))=v(k) (k=1,...,K-1)及びf(n(0))=αを満たすK-1次式である。n(0), n(1),...,n(K)が互いに異なる（ステップＳ７１４）。
【０１９５】
選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)は内部分散部３１８に入力され、計算部７１６から出力された値f(n(K))は内部分散部７１９に入力される。内部分散部３１８は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)のそれぞれを秘密分散し、kのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を生成し、分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)を出力する（ステップＳ７１５）。内部分散部７１９は、(K, N)閾値秘密分散法Uに従って、値f(n(K))を秘密分散してN個の分散値Ui(f(n(K))) (i=1,...,N)を生成し、分散値Ui(f(n(K))) (i=1,...,N)を出力する（ステップＳ７１６）。内部分散部３１９は、例えば、参考文献１に記載された方式に従って、分散値Ui(f(n(K))) (i=1,...,N)を生成する（［(K, N)閾値秘密分散法Uの例示１，２］参照）。
【０１９６】
分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)、及び分散値Ui(f(n(K))) (i=1,...,N)は、分散値生成部７１７に入力される。分散値生成部７１７は、これらを用いてN個の分散値Ti(α)=(V1,i(v(1)),...,VK-1,i(v(K-1)), Ui(f(n(K)))) (i=1,...,N)を生成し、分散値Ti(α) (i=1,...,N)を出力する（ステップＳ７１７）。
【０１９７】
N個の分散値Ti(α) (i=0,...,N-1)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=0,...,N-1)を出力する（ステップＳ７１８）。出力された分散値Ti(α) (i=0,...,N-1)のそれぞれは、データ記憶装置３２０−ｉ(i=1,...,N)のそれぞれに提供される。データ記憶装置３２０−λに提供された分散値Tλ(α)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【０１９８】
＜分散データ変換処理＞
図２４Ａ，１２Ｂ，１２Ｃを用い、分散データ変換装置７４０−λ(λ∈{1,...,N})が実行する分散データ変換処理を説明する。
［分散データ変換装置３４０−κ(κ∈{1,...,K-1}）の処理（図２４Ａ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置３２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(α)が含むVκ,λ(v(κ))が出力される。K個の互いに異なるλ∈{1,...,N}に対応するK個のVκ,λ(v(κ))は、ネットワーク等を経由して、分散データ変換装置３４０−κ(κ∈{1,...,K-1})（図９Ａ）の入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ７４１−κ）。
【０１９９】
内部復元部７４５−κは、記憶部１４３ｂ−κに格納された、K個の互いに異なるλ∈{1,...,N}に対応するK個のVκ,λ(v(κ))からv(κ)を復元し、得られたv(κ)を出力する（ステップＳ７４２−κ）。v(κ)は変換分散値生成部７４６−κに入力される。変換分散値生成部７４６−κは、変換分散値Sκ(α)=v(κ)として出力する（ステップＳ７４３−κ）。変換分散値Sκ(α)は出力部１４２−κに入力され、出力部１４２−κは変換分散値Sκ(α)を出力する（ステップＳ７４４−κ）。変換分散値Sκ(α)は、ネットワーク等を経由して、対応するデータ記憶装置３２０−κ（図７Ｂ）に送信される。変換分散値Sκ(α)は、データ記憶装置３２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【０２００】
［分散データ変換装置７４０−Ｋの処理（図１２Ｂ）］
図１２Ｂに示すように、分散データ変換装置７４０−Ｋは、変換分散値生成部３４６−Ｋを変換分散値生成部７４６−ＫとしたステップＳ３４１−Ｋ，Ｓ３４２−Ｋ，Ｓ３４３−Ｋの処理を実行する。
【０２０１】
［分散データ変換装置３４０−η(η∈{K+1,...,N}）の処理（図１２Ｃ）］
分散データ変換装置３４０−η (η∈{K+1,...,N}）（図１０）の変換分散値生成部７４６−ηは、n(1),...,n(K)と異なるn(η)に対応するF(n(η))を生成し、F(n(η))を変換分散値Sη(α)=F(n(η))として出力する。ただし、F(x)は、K個の互いに異なるλ∈{1,...,N}に対応するK個のVk,λ(v(k))から復元されるv(k)から得られるf(n(k))=v(k) (k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応するK個のUλ(f(n(K)))から復元されるf(n(K))とからなる、f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式である。例えば、前述のステップＳ３４１−η〜Ｓ３４４−ηでの「f(n(κ))=P(v(κ))」を「f(n(κ))=v(κ)」に置換した処理（ステップＳ７４１−η〜Ｓ７４４−η）によって分散値Sη(α)=F(n(η))が生成される。
【０２０２】
＜分散値提供・秘密計算＞
K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置３２０−λ（図７Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(α)を出力するか、又は、秘密計算部３２７−λで秘密計算を行ってその結果を表す分散値Eλを出力する。これらはネットワーク等を経由してデータ復元装置７３０に送られる。
【０２０３】
＜データ復元処理＞
図１３に例示するように、データ復元装置７３０（図８）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)又はK個の分散値Eλが入力される（ステップＳ７３１）。制御部１３４は、K個の分散値Tλ(α)が入力されたか、K個の分散値Eλが入力されたかを判定する（ステップＳ７３２）。
【０２０４】
ステップＳ７３２で、K個の分散値Tλ(α)が入力されたと判定された場合、これらK個の分散値Tλ(α)が変換部７３５に入力される。変換部７３５は、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、K個の互いに異なるn(μ) (μ=1,...,K)に対応するK個の値f(n(μ)) (μ=1,...,K)を得る。まず、変換部７３５の内部復元部７３５ａが、入力されたK個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(α)から、値f(n(K))及びv(k) (k=1,...,K-1)を復元し、値f(n(K))及びv(k) (k=1,...,K-1)を出力する（ステップＳ７３３）。
【０２０５】
値f(n(K))及びv(k) (k=1,...,K-1)は座標復元部７３５ｂに入力される。座標復元部７３５ｂはf(n(k))=v(k) (k=1,...,K-1)とし、これらと値f(n(K))とからなるK個の値f(n(μ)) (μ=1,...,K)を出力する（ステップＳ７３４）。
【０２０６】
K個の値f(n(μ)) (μ=1,...,K)は復元部７３６に入力される。復元部７３６は、これらK個の値f(n(μ)) (μ=1,...,K)に対してF(n(μ))=f(n(μ)) (μ=1,...,K)を満たすK-1次式F(x)の関数値F(n(0))=αを生成し、それによって得られた値αを出力する（ステップＳ７３５）。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【０２０７】
一方、ステップＳ７３２で、分散値Eλが入力されたと判定された場合、復元部７３６で、第１実施形態で説明したステップＳ１３６，Ｓ１３７の処理が実行される。
【０２０８】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。第３実施形態と同様、本形態でも分散値生成部がTi(α)に加え、n(i)，iその他の付加情報を分散値として出力してもよい。
【０２０９】
〔第８実施形態〕
次に、本発明の第８実施形態を説明する。本形態は第４，７実施形態の変形例であり、同一の値v(k)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第７実施形態では、N, K, Rが2以上の整数であり、K≦Nであり、Gが或る集合である。本形態の集合Gの具体例は、第１実施形態で説明した集合Gと同じである。K=Nであってもよいし、K＜Nであってもよい。
【０２１０】
第８実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個のデータ記憶装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、K-1個の値v(k) (k=1,...,K-1)を選択し、rと値v(k)とに対応する値をz(r, v(k))とし、値fr(nr(K))を得る。ただし、同一のrに対応する値nr(0), nr(1),...,nr(K）が互いに異なり、値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=z(r, v(k)) (k=1,...,K-1)及びfr(nr(0))=αrを満たすK-1次式がfr(x)である。データ分散装置は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)を秘密分散してkのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を得、rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、値fr(nr(K))を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を得、r (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を得る。ただし、V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが分散値Vk,i(v(k))である。(K, N)閾値秘密分散法Urの例は、第４実施形態で説明した通りである。
【０２１１】
本形態のデータ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得、r (r=1,...,R)のそれぞれについて、Fr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを得る。例えば、データ復元装置は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)から、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を復元し、r (r=1,...,R)のそれぞれについて、fr(nr(k))=z(r,v(k)) (k=1,...,K-1)とし、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る。
【０２１２】
本形態の1,...,K-1番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値z(r, v(κ) (κ∈{1,...,K-1})を得る。本形態のK番目の分散データ変換装置は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から、変換分散値fr(nr(K)) (r=1,...,R)を得る。本形態のK+1,...,N番目の分散データ変換装置は、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N})を得る。ただし、Fr(x)は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=z(r,v(k)) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式である。このように得られる変換分散値は、秘密計算の入力値として用いられる。
【０２１３】
本形態において好ましくは、分散値Ur,i(fr(nr(K)))のデータ量は、集合Gの要素のデータ量よりも小さい。本形態において好ましくは、分散値Vr,k,i(v(k))それぞれのデータ量は、集合Gの要素のデータ量よりも小さい。本形態においてより好ましくは、値v(k)それぞれのデータ量は、集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０２１４】
＜構成＞
図６に例示するように、第８実施形態の秘密分散システム８は、第４実施形態の秘密分散システム４のデータ分散装置４１０、N個の分散データ変換装置４４０−ｉ（i=1,...,N）及びデータ復元装置４３０が、データ分散装置８１０、N個の分散データ変換装置８４０−ｉ（i=1,...,N）及びデータ復元装置８３０にそれぞれ置換されたものである。
【０２１５】
図２２に例示するように、本形態のデータ分散装置７１０は、入力部１１１、出力部１１２、メモリ１１３、制御部３１４、選択部１１５、分割部２１１、計算部７１６、内部分散部３１８，７１９、及び分散値生成部７１７を有する。本形態のデータ分散装置７１０は、制御部７１４の制御のもとで各処理を実行する。
【０２１６】
図８に例示するように、本形態のデータ復元装置８３０は、入力部１３１、出力部１３２、メモリ１３３、制御部８３４、変換部８３５、復元部８３６、及び結合部２３７を有する。変換部８３５は、内部復元部８３５ａ，８３５ｂを有する。本形態のデータ復元装置８３０は、制御部８３４の制御のもとで各処理を実行する。
【０２１７】
図９Ａに例示するように、本形態の分散データ変換装置８４０−κ (κ∈{1,...,K-1})は、入力部１４１−κ、出力部１４２−κ、メモリ１４３ａ−κ、記憶部１４３ｂ−κ、制御部８４４−κ、内部復元部８４５−κ、及び変換分散値生成部８４６−κを有する。図９Ｂに例示するように、本形態の分散データ変換装置８４０−Ｋは、入力部１４１−Ｋ、出力部１４２−Ｋ、メモリ１４３ａ−Ｋ、記憶部１４３ｂ−Ｋ、制御部８４４−Ｋ、及び変換分散値生成部４４６−Ｋを有する。図１０に例示するように、本形態の分散データ変換装置８４０−η(η∈{K+1,...,N})は、入力部１４１−η、出力部１４２−η、メモリ１４３ａ−η、記憶部１４３ｂ−η、制御部８４４−η、及び変換分散値生成部８４６−ηを有する。本形態の分散データ変換装置４４０−λは、制御部４４０−λの制御のもとで各処理を実行する。
【０２１８】
＜データ分散処理＞
図２５に例示するように、データ分散装置８１０（図２２）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=1,...,R)に分割し、R個の値αr (r=1,...,R)を出力する（ステップＳ２１１）。選択部１１５は、K-1個の値v(k) (k=1,...,K-1)を選択し、値v(k) (k=1,...,K-1)を出力する（ステップＳ１１２）。
【０２１９】
分割部２１１から出力された個の値αr (r=1,...,R)と選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)とは計算部８１６に入力される。計算部８１６は、これらを用いて値fr(nr(K)) (r=1,...,R)を生成し、得られた値fr(nr(K)) (r=1,...,R)を出力する。ただし、fr(x)は値nr(1),...,nr(K-1)と集合Gの要素である値αr∈Gとについてfr(nr(k))=z(r, v(k))及びfr(nr(0))=αrを満たすK-1次式である。同一のrに対応する値nr(0), nr(1),...,nr(K）が互いに異なる（ステップＳ８１４）。
【０２２０】
選択部１１５から出力されたK-1個の値v(k) (k=1,...,K-1)は内部分散部３１８に入力され、計算部８１６から出力された値fr(nr(K)) (r=1,...,R)は内部分散部８１９に入力される。内部分散部３１８は、(K, N)閾値秘密分散法Vkに従って、v(k) (k=1,...,K-1)のそれぞれを秘密分散し、kのそれぞれについてN個の分散値Vk,i(v(k)) (i=1,...,N)を生成し、分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)を出力する（ステップＳ８１５）。内部分散部８１９は、rのそれぞれについて、(K, N)閾値秘密分散法Urに従って、値fr(nr(K))を秘密分散してN個の分散値Ur,i(fr(nr(K))) (i=1,...,N)を生成し、分散値Ur,i(fr(nr(K))) (i=1,...,N, r=1,...,R)を出力する（ステップＳ８１６）。
【０２２１】
分散値Vk,i(v(k)) (i=1,...,N, k=1,...,K-1)及び分散値Ur,i(fr(nr(K))) (i=1,...,N)は、分散値生成部８１７に入力される。分散値生成部８１７は、これらを用いてr (r=1,...,R)のそれぞれについてN個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を生成し、R×N個の分散値Ti(αr)=(Vr,1,i(v(1)),...,Vr,K-1,i(v(K-1)), Ur,i(fr(nr(K)))) (r=1,...,R, i=1,...,N)を出力する（ステップＳ８１７）。ただし、V1,k,i(v(k)),...,VR,k,i(v(k))の少なくとも何れかが分散値Vk,i(v(k))である。
【０２２２】
R×N個の分散値Ti(αr) (i=1,...,N, r=1,...,R)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(αr) (i=1,...,N, r=1,...,R)を出力する（ステップＳ８１８）。出力された分散値Ti(αr) (i=1,...,N, r=1,...,R)のそれぞれは、データ記憶装置４２０−ｉ(i=1,...,N)のそれぞれに提供される。データ記憶装置４２０−λに提供された分散値Tλ(αr) (r=1,...,R)は入力部１２１−λに入力され、記憶部１２３ｂ−λに格納される。
【０２２３】
＜分散データ変換処理＞
図２４Ｂ，図１５Ｂ，１５Ｃを用い、分散データ変換装置８４０−λ(λ∈{1,...,N})が実行する分散データ変換処理を説明する。
［分散データ変換装置８４０−κ(κ∈{1,...,K-1}）の処理（図２４Ｂ）］
K個の互いに異なるλ∈{1,...,N}に対応するK個のデータ記憶装置４２０−λ（図７Ｂ）の出力部１２２−λから、記憶部１２３ｂ−λに格納された分散値Tλ(αr) (r=1,...,R)が含むVr,κ,λ(v(κ)) (r=1,...,R)が出力される。K個の互いに異なるλ∈{1,...,N}に対応するVr,κ,λ(v(κ)) (r=1,...,R)は、ネットワーク等を経由して、分散データ変換装置８４０−κ(κ∈{1,...,K-1})（図９Ａ）の入力部１４１−κに入力され、記憶部１４３ｂ−κに格納される（ステップＳ８４１−κ）。
【０２２４】
内部復元部８４５−κは、記憶部１４３ｂ−κに格納された、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N}, r=1,...,R)が含むVκ,λ(v(κ))から、v(κ) (κ∈{1,...,K-1})を復元し、得られたv(κ)を出力する（ステップＳ４４２−κ）。
【０２２５】
v(κ)は変換分散値生成部８４６−κに入力される。変換分散値生成部８４６−κは、r (r=1,...,R)のそれぞれについて、v(κ)から変換分散値z(r, v(κ) (κ∈{1,...,K-1})を計算し、当該変換分散値Sκ(αr)=z(r, v(κ)) (r=1,...,R)を出力する。当該変換分散値Sκ(αr) (r=1,...,R)は出力部１４２−κに入力され、出力部１４２−κは変換分散値Sκ(αr) (r=1,...,R)を出力する（ステップＳ８４４−κ）。変換分散値Sκ(αr) (r=1,...,R)は、ネットワーク等を経由して、対応するデータ記憶装置４２０−κ（図７Ｂ）に送信される。変換分散値Sκ(αr) (r=1,...,R)は、データ記憶装置４２０−κの入力部１２１−κに入力され、記憶部１２３ｂ−κに格納される。
【０２２６】
［分散データ変換装置８４０−Ｋの処理（図１５Ｂ）］
図１５Ｂに示すように、分散データ変換装置８４０−Ｋは、変換分散値生成部４４６−Ｋを変換分散値生成部８４６−ＫとしたステップＳ４４１−Ｋ，Ｓ４４２−Ｋ，Ｓ４４３−Ｋの処理を実行する。
【０２２７】
［分散データ変換装置８４０−η(η∈{K+1,...,N}）の処理（図１５Ｃ）］
分散データ変換装置８４０−η (η∈{K+1,...,N}）（図１０）の変換分散値生成部８４６−ηは、nr(μ) (μ=1,...,K)と異なるnr(η)に対応するFr(nr(η)) (η∈{K+1,...,N}, r=1,...,R)を生成し、当該Fr(nr(η)) (η∈{K+1,...,N}, r=1,...,R)を変換分散値Sη(αr)=Fr(nr(η)) (r=1,...,R)として出力する。ただし、Fr(x)は、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (λ∈{1,...,N})が含むVk,λ(v(k))から復元されるv(k)から得られるfr(nr(k))=z(r,v(k)) (r=1,...,R, k=1,...,K-1)と、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)が含むUr,λ(fr(nr(K)))から復元される変換分散値fr(nr(K)) (r=1,...,R)とからなる、fr(nr(μ)) (μ=1,...,K)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式である。例えば、前述のステップＳ４４１−η〜Ｓ４４４−ηでの「fr(nr(κ))=P(z(r,v(κ)))」を「fr(nr(κ))=z(r,v(κ))」に置換した処理（ステップＳ８４１−η〜Ｓ８４４−η）によって分散値Sη(αr)=Fr(nr(η))が生成される
【０２２８】
＜分散値提供・秘密計算＞
K個の互いに異なるλ∈{1,...,N}に対応するデータ記憶装置４２０−λ（図７Ｂ）は、記憶部１２３ｂ−λに格納された分散値Tλ(αr) (r=1,...,R)を出力するか、又は、秘密計算部４２７−λで秘密計算を行ってその結果を表す分散値Eλ,r(r=1,...,R)を出力する。これらはネットワーク等を経由してデータ復元装置８３０に送られる。
＜データ復元処理＞
図１６に例示するように、データ復元装置８３０（図８）の入力部１３１には、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)又は分散値Eλ,rが入力される（ステップＳ８３１）。制御部１３４は、K個の分散値Tλ(αr)が入力されたか、K個の分散値Eλ,rが入力されたかを判定する（ステップＳ８３２）。
【０２２９】
ステップＳ８３２で、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr) (r=1,...,R)が入力されたと判定された場合、これら分散値Tλ(αr) (r=1,...,R)が変換部８３５に入力される。変換部８３５は、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応するK個の分散値Tλ(αr)から、K個の互いに異なるnr(μ) (μ=1,...,K)に対応する値fr(nr(μ)) (μ=1,...,K)を得る。まず、変換部８３５の内部復元部８３５ａが、r (r=1,...,R)のそれぞれについて、K個の互いに異なるλ∈{1,...,N}に対応する分散値Tλ(αr)から、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を復元し、値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)を出力する。
【０２３０】
値fr(nr(K)) (r=1,...,R)及びv(k) (k=1,...,K-1)は座標復元部８３５ｂに入力される。座標復元部８３５ｂは、r (r=1,...,R)のそれぞれについてfr(nr(k))=z(r,v(k))とする。座標復元部８３５ｂは、それらと入力された値fr(nr(K)) (r=1,...,R)からなる値fr(nr(μ)) (μ=1,...,K, r=1,...,R)を出力する（ステップＳ８３４）。
【０２３１】
値fr(nr(μ)) (μ=1,...,K, r=1,...,R)は復元部８３６に入力される。復元部８３６は、r (r=1,...,R)のそれぞれについて、これらの値fr(nr(μ)) (μ=1,...,K, r=1,...,R)に対してFr(nr(μ))=fr(nr(μ)) (μ=1,...,K)を満たすK-1次式Fr(x)の関数値Fr(nr(0))=αrを生成し、それによって得られた値αrを出力する（ステップＳ８３５）。値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr(r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【０２３２】
一方、ステップＳ８３２で、分散値Eλ, rが入力されたと判定された場合、復元部８３６で、第２実施形態で説明したステップＳ２３６，Ｓ２３７，Ｓ１３７の処理が実行される。
【０２３３】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。さらに同一の値v(k)を複数の値αr (r=0,...,R-1)の秘密分散に流用することで分散値のデータ量をさらに削減できる。さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。第４実施形態と同様、本形態でも分散値生成部がTi(αr)に加え、n(i)，i，ｒその他の付加情報を分散値として出力してもよい。
【０２３４】
〔その他の変形例等〕
本発明は上述の実施の形態に限定されるものではない。例えば、第２，４，６，８実施形態では、値αを分割してR個の値αr(r=0,...,R-1)が生成されたが、値αがR個の値αrからなるデータであってもよい。例えば、値αが表データであり、αrが当該表データを構成する要素であってもよい。その他、R個の値αrが値αから分割されたものではなく、互いに独立したデータであってもよい。
【０２３５】
上述したように、データ分散装置が上述の実施形態の分散値に加え、さらに別の付加情報を出力してもよい。また、付加情報としてｒが送信されるのではなく、送信されるビットストリーム中の分散値の位置並びに順序、又は、記憶領域中に格納された分散値のアドレスなどの情報にrを関連付け、これらの情報から分散値に対応するrが特定されてもよい。
【０２３６】
上述の実施形態で説明した装置の少なくとも一部の処理部が同一の装置に含まれていてもよい。例えば、データ分散装置とデータ復元装置とが同一のコンピュータを用いて構成されてもよい。また、上述の実施形態で説明した装置に含まれる一部の処理部が別の装置に含まれていてもよい。例えば、データ記憶装置の外部の秘密計算装置に秘密計算部が設けられ、秘密計算装置がデータ記憶装置から提供された変換分散値を用いて秘密計算を行ってもよい。また、装置Ａから装置Ｂへ情報を提供するとは、装置Ａから装置Ｂへ情報を送信することであってもよいし、装置Ａから出力された情報を可搬型記録媒体に格納し、装置Ｂが当該可搬型記録媒体から当該情報を読み出すことであってもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２３７】
上述の各装置は、例えば、CPU(central processing unit)，RAM(random-access memory)等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。これらの装置がコンピュータによって実現される場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０２３８】
プログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２３９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。また、上述の各装置の処理機能の少なくとも一部がハードウェアで構成されてもよい。
【符号の説明】
【０２４０】
１〜８  秘密分散システム
１１０〜８１０  データ分散装置
１２０〜８２０  データ記憶装置
１３０〜８３０  データ復元装置
１４０〜８４０  分散データ変換装置
【図１】
0005458116.tif 000012
【図２】
0005458116.tif 000013
【図３】
0005458116.tif 000014
【図４】
0005458116.tif 000015
【図５】
0005458116.tif 000016
【図６】
0005458116.tif 000017
【図７】
0005458116.tif 000018
【図８】
0005458116.tif 000019
【図９】
0005458116.tif 000020
【図１０】
0005458116.tif 000021
【図１１】
0005458116.tif 000022
【図１２】
0005458116.tif 000023
【図１３】
0005458116.tif 000024
【図１４】
0005458116.tif 000025
【図１５】
0005458116.tif 000026
【図１６】
0005458116.tif 000027
【図１７】
0005458116.tif 000028
【図１８】
0005458116.tif 000029
【図１９】
0005458116.tif 000030
【図２０】
0005458116.tif 000031
【図２１】
0005458116.tif 000032
【図２２】
0005458116.tif 000033
【図２３】
0005458116.tif 000034
【図２４】
0005458116.tif 000035
【図２５】
0005458116.tif 000036