(57)【要約】  分散情報生成装置（１００）は、秘密情報及び乱数に対応するチェック用データを生成し、秘密情報及び乱数を予め定められたアクセス構造にしたがって分散符号化し、それらを記憶装置（３００＿１〜３００＿ｎ）に格納する。復元装置（２００）は、アクセス構造のいずれかの元に対応する複数の記憶装置から、分散符号化された秘密情報及び乱数を読み出し、それらを復元する。そして、チェック用データが復元された秘密情報及び乱数に対応している場合には復元された秘密情報が正しいと判断し、対応していない場合には不正と判断する。これにより、秘密情報がどのような分布に従って選ばれても、n-1個の分散情報を参照し、そのうちのいくつかを改竄する不正を検知することが可能となる。
2009075353.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段と
を備える分散情報生成装置。
【請求項２】
前記分散符号化された秘密情報と、前記分散符号化された乱数情報と、前記チェック用データとをそれぞれ格納する記憶手段をさらに備える請求項１記載の分散情報生成装置。
【請求項３】
前記チェック用データ生成手段は、要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、予め定められた定数 c に対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすn個のGF(p)^2の元(e_[10],e_[11]),(e_[20],e_[21]),...,(e_[n0],e_[n1])をランダムに選ぶ請求項１記載の分散情報生成装置。
【請求項４】
前記秘密情報分散手段は、前記秘密分散法のアクセス構造として、(k,n)しきい法のアクセス構造を用いる請求項３記載の分散情報生成装置。
【請求項５】
前記秘密情報分散手段は、前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う(n,n)しきい法を用いる請求項３記載の分散情報生成装置。
【請求項６】
秘密分散法のアクセス構造に対応する記憶手段から分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元手段と、
前記秘密分散法のアクセス構造に対応する前記記憶手段から分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元手段と、
前記秘密分散法のアクセス構造に対応する全ての前記記憶手段から、前記秘密情報と前記乱数情報に対応して生成されたチェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元手段で復元された秘密情報と前記乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段と
を備える復元装置。
【請求項７】
前記不正検知手段は、前記チェック用データ全てが復元された秘密情報と復元された乱数情報に対応している場合、復元された秘密情報に加えて、復元された乱数を出力する請求項６記載の復元装置。
【請求項８】
前記記憶手段をさらに備え、
前記記憶手段は、前記秘密分散法のアクセス構造にしたがって分散符号化された秘密情報と、前記秘密分散法のアクセス構造にしたがって分散符号化された乱数情報と、前記チェック用データと、を格納する請求項６記載の復元装置。
【請求項９】
前記不正検知手段は、
要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記秘密分散法のアクセス構造に対応するチェック用データ
(e_[i_10],e_[i_11],(e_[i_20],e_[i_21],...,(e_[i_m0],e_[i_m1]と、を入力とし、
予め定められた定数cと、任意のj=1,2,...,mに対し、
e_[i_j0]+s_1*e_[i_j1]+s_2*e_[i_j1]^2+...+s_N*e_[i_j1]^N+r_1*e_[i_j1]^[N+1]+r_2*e_[i_j1]^[N+2]+...+r_[k-1]*e_[i_j1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定する請求項８記載の復元装置。
【請求項１０】
前記秘密分散法のアクセス構造として、(k,n)しきい法のアクセス構造が用いられる請求項９記載の復元装置。
【請求項１１】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う(n,n)しきい法が用いられる請求項９記載の復元装置。
【請求項１２】
秘密情報と、乱数情報と、前記秘密情報と前記乱数情報に対応して生成されたチェック用データと、を取得し、前記チェック用データが前記秘密情報と前記乱数情報に対応している場合は、秘密情報の非改竄性が検証されたことを示す信号を出力し、対応していない場合は不正を示す信号を出力する検証装置。
【請求項１３】
要素数p^Nの元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記チェック用データ(e_[i_10],e_[i_11]と、を入力とし、
予め定められた定数 c に対し、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報に対応していると判定する請求項１２記載の検証装置。
【請求項１４】
分散情報生成装置と、記憶装置と、復元装置とを備え、
前記分散情報生成装置は、
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備え、
前記記憶装置は、前記分散符号化された秘密情報と、前記分散符号化された乱数情報と、前記チェック用データと格納し、
前記復元装置は、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元手段と、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元手段と、
前記アクセス構造に対応する全ての前記記憶装置から前記チェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元手段で復元された秘密情報と前記乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備える
秘密情報分散システム。
【請求項１５】
前記チェック用データ生成手段は、要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、予め定められた定数 c に対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすn個のGF(p)^2の元(e_[10],e_[11]),(e_[20],e_[21]),...,(e_[n0],e_[n1])をランダムに選び、
前記不正検知手段は、
要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記秘密分散法のアクセス構造に対応するチェック用データ
(e_[i_10],e_[i_11],(e_[i_20],e_[i_21],...,(e_[i_m0],e_[i_m1]と、を入力とし、
予め定められた定数cと、任意のj=1,2,...,mに対し、
e_[i_j0]+s_1*e_[i_j1]+s_2*e_[i_j1]^2+...+s_N*e_[i_j1]^N+r_1*e_[i_j1]^[N+1]+r_2*e_[i_j1]^[N+2]+...+r_[k-1]*e_[i_j1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定する
請求項１４記載の秘密情報分散システム。
【請求項１６】
前記秘密分散法のアクセス構造として、(k,n)しきい法のアクセス構造が用いられる請求項１５記載の秘密情報分散システム。
【請求項１７】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う(n,n)しきい法が用いられる請求項１５記載の秘密情報分散システム。
【請求項１８】
前記不正検知手段は、前記チェック用データが復元された秘密情報と復元された乱数情報に対応している場合、復元された秘密情報に加えて、復元された乱数を出力する請求項１４記載の秘密情報分散システム。
【請求項１９】
前記秘密情報復元手段で復元された秘密情報と、前記乱数情報復元手段で復元された乱数情報と、前記記憶装置に格納されているチェック用データと、を取得し、前記チェック用データが前記秘密情報と前記乱数情報に対応している場合は、秘密情報の非改竄性が検証されたことを示す信号を出力し、対応していない場合は不正を示す信号を出力する検証装置をさらに備える請求項１８記載の秘密情報分散システム。
【請求項２０】
前記チェック用データ生成手段は、要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、予め定められた定数 c に対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすn個のGF(p)^2の元(e_[10],e_[11]),(e_[20],e_[21]),...,(e_[n0],e_[n1])をランダムに選び、
前記不正検知手段は、
要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記秘密分散法のアクセス構造に対応するチェック用データ
(e_[i_10],e_[i_11],(e_[i_20],e_[i_21],...,(e_[i_m0],e_[i_m1]と、を入力とし、
予め定められた定数cと、任意のj=1,2,...,mに対し、
e_[i_j0]+s_1*e_[i_j1]+s_2*e_[i_j1]^2+...+s_N*e_[i_j1]^N+r_1*e_[i_j1]^[N+1]+r_2*e_[i_j1]^[N+2]+...+r_[k-1]*e_[i_j1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定し、
前記検証装置は、
要素数p^Nの元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記チェック用データ(e_[i_10],e_[i_11]と、を入力とし、
予め定められた定数 c に対し、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報に対応していると判定する
請求項１９記載の秘密情報分散システム。
【請求項２１】
前記秘密分散法のアクセス構造として、(k,n)しきい法のアクセス構造が用いられる請求項２０記載の秘密情報分散システム。
【請求項２２】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う(n,n)しきい法が用いられる請求項２０記載の秘密情報分散システム。
【請求項２３】
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散処理と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散処理と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成処理と
をコンピュータに実行させる分散情報生成プログラム。
【請求項２４】
前記分散符号化された秘密情報と、前記分散符号化された乱数情報と、前記チェック用データとをそれぞれ格納する記憶処理をさらにコンピュータに実行させる請求項２３記載の分散情報生成プログラム。
【請求項２５】
前記チェック用データ生成処理は、要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、予め定められた定数 c に対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすn個のGF(p)^2の元(e_[10],e_[11]),(e_[20],e_[21]),...,(e_[n0],e_[n1])をランダムに選ぶ請求項２３記載の分散情報生成プログラム。
【請求項２６】
秘密分散法のアクセス構造に対応する記憶手段から分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元処理と、
前記秘密分散法のアクセス構造に対応する前記記憶手段から分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元処理と、
前記秘密分散法のアクセス構造に対応する全ての前記記憶手段から、前記秘密情報と前記乱数情報に対応して生成されたチェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元処理で復元された秘密情報と前記乱数情報復元処理で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知処理と
をコンピュータに実行させる復元プログラム。
【請求項２７】
前記不正検知処理は、前記チェック用データ全てが復元された秘密情報と復元された乱数情報に対応している場合、復元された秘密情報に加えて、復元された乱数を出力する請求項２６記載の復元装置プログラム。
【請求項２８】
前記秘密分散法のアクセス構造にしたがって分散符号化された秘密情報と、前記秘密分散法のアクセス構造にしたがって分散符号化された乱数情報と、前記チェック用データと、を前記記憶手段に格納する記憶処理をさらにコンピュータに実行させる請求項２６記載の復元装置プログラム。
【請求項２９】
前記不正検知処理は、
要素数p^Nの体の元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の体の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記秘密分散法のアクセス構造に対応するチェック用データ
(e_[i_10],e_[i_11],(e_[i_20],e_[i_21],...,(e_[i_m0],e_[i_m1]と、を入力とし、
予め定められた定数cと、任意のj=1,2,...,mに対し、
e_[i_j0]+s_1*e_[i_j1]+s_2*e_[i_j1]^2+...+s_N*e_[i_j1]^N+r_1*e_[i_j1]^[N+1]+r_2*e_[i_j1]^[N+2]+...+r_[k-1]*e_[i_j1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元処理で復元された秘密情報に対応していると判定する請求項２８記載の復元装置プログラム。
【請求項３０】
秘密情報と、乱数情報と、前記秘密情報と前記乱数情報に対応して生成されたチェック用データと、を取得する処理と、
前記チェック用データが前記秘密情報と前記乱数情報に対応している場合に、秘密情報の非改竄性が検証されたことを示す信号を出力する処理と、
前記チェック用データが前記秘密情報と前記乱数情報に対応していない場合に、不正を示す信号を出力する処理と
をコンピュータに実行させる検証プログラム。
【請求項３１】
要素数p^Nの元である秘密情報s=(s_1,s_2,...,s_N)と、
要素数p^[k-1]の元である乱数情報r=(r_1,r_2,...,r_[k-1])と、
前記チェック用データ(e_[i_10],e_[i_11]と、を入力とし、
予め定められた定数 c に対し、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
（なお、pは素数であり、kは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報に対応していると判定する処理をさらにコンピュータに実行させる検証プログラム。
【請求項３２】
請求項２３から３１のいずれか１項記載のプログラムを記録するコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報を分散して安全に保管する分散情報生成装置、復元装置、検証装置及び秘密情報分散システムに関する。
【背景技術】
【０００２】
秘密情報（例えば暗号化に用いる秘密鍵）を保管する場合、紛失や破壊の脅威と盗難の脅威とがある。前者の脅威に対しては秘密情報のコピーを作成すれば有効であるが、コピーを作成することで後者の盗難に対する脅威が増してしまう。このような問題を解決するための情報セキュリティ技術の1つとして秘密分散法がある。【０００３】
秘密分散法は、秘密情報を複数の分散情報に分散し、予め定められた分散情報を集めると秘密を一意に復元可能であるが、それ以外の分散情報を集めても秘密に関する情報を全く漏らさないという特徴を持つ。本明細書では、分散情報の数を n とし、各分散情報を 1 から n で識別する。秘密分散法では、秘密を復元できる分散情報の集合をアクセス構造という分散情報の集合族 Γ で定義することが可能である。アクセス構造 Γ は、秘密を復元できる最小の分散情報の識別子の集合を要素として持つ集合族であり、アクセス構造Γを持つ秘密分散法において、分散情報の集合 ｗ が秘密を復元可能であるとは、ｗ に対応する分散情報の識別子集合 Ｗ に対して、V∈Γ かつ V⊆W となるような Ｖ が存在することを意味する。また、前記のような性質を満たす分散情報識別子の集合ＷをΓのアクセス集合と定義する。【０００４】
例えば、(k,n)閾値法と呼ばれる、（１）n個の分散情報のうち、k個未満の分散情報では秘密に関する情報は全く得られない、（２）k個以上の分散情報からは秘密は一意に復元されるという特徴を持つ秘密分散法に置けるアクセス構造 Γ は Γ=[V | V⊆[1,...,n] かつ V の要素数は k] という集合族によって定義される。以下、秘密分散法において、秘密情報を復元する際の問題点について考える。【０００５】
秘密情報を復元する場合、分散情報を保持する他のものから分散情報を集める必要がある。このとき、分散情報の被要求側が配付された値を改竄することなく復元者へ渡すとは限らない。なお、ここで言う「改竄」とは、意図的なものだけでなく、装置故障や単なるミス等の意図しない変更も含むものとする。【０００６】
改竄された分散情報を用いて秘密情報を復元すると、その値は秘密情報と異なる値になってしまうことがある。そのため、秘密分散法には復元に用いる分散情報に改竄された値が存在することを高い確率で検知できる手法が望まれる。また、運用形態によって分散情報が選択される手段は様々であり、分散情報がどのような確率分布にしたがって選択されても改竄された値の検知率が高いことが望まれる。これらの問題を解決するための一つの技術として文献２（Martin Tompa, Heather Woll, "How to Share a Secret with Cheaters", Journal of Cryptology, vol.1, pages 133-138, 1988）、文献３（Wakaha Ogata, Kaoru Kurosawa, Douglas R. Stinson, "Optimum Secret Sharing Scheme Secure Against Cheating", SIAM Journal on Discrete Mathematics, vol.20, no1, pages 79-95, 2006）、文献５（Satoshi Obana and Toshinori Araki, "Almost Optimum Secret Sharing Schemes Secure Against Cheating for Arbitrary Secret Distribution",Advances in Cryptology -- Asiacrypt 2006, Lecture Notes in Computer Science 4284, pp. 364--379, 2006）、文献６（Toshinori Araki, "Efficient (k,n) Threshold Secret Sharing Schemes Secure Against Cheating from n-1 Cheaters", Proceedings of ACISP 2007, Lecture Notes in Computer Science 4586, pp. 133--142,2007）の方法が知られている。【０００７】
文献２には、秘密情報がどのような確率分布にしたがって選択されても、n-1個の分散情報を参照し、そのうち高々k-1個の分散情報に対して改竄を行う不正を(1-ε)の確率で検知できる(k,n)しきい値法について記載されている。文献１（Adi Shamir, "How to share a secret", Comm. ACM, 22(11), 612-613(1979)）に記載された方法では、秘密情報を要素数sの集合とするとき、分散情報は要素数((s-1)(k-1)/ε+k)^2の集合となる。【０００８】
文献３には、秘密情報が一様な確率分布にしたがって選択されることを条件にk-1個の分散情報を参照し、そのうち高々k-1個の分散情報の改竄を行う不正を(1-ε)の確率で検知できる(k,n)しきい値法について記載されている。文献３に記載された方法では、秘密情報を要素数sの集合とするとき、分散情報は要素数(1+(s-1)/ε)の集合になる。文献４（J. Benaloh and J. Leichter, Generalized secret sharing and monotone functions, in "Advances in Cryptology -- CRYPTO '88", S. Goldwasser, ed., Lecture Notes in Computer Science 403, pages 27-35, 1989）には、(n,n)しきい値型の秘密分散法が記載されている。【０００９】
文献５には、秘密情報がどのような確率分布にしたがって選択されても、k-1個の分散情報を参照し、そのうち高々k-1個の分散情報に対して改竄を行う不正を(1-ε)の確率で検知できる秘密分散法について記載されている。文献５に記載された方法では、秘密情報を要素数sの集合とするとき、分散情報は要素数 s/(ε^2)の集合となる。【００１０】
文献６には、分散情報がどのような確率分布にしたがって選択されても、n-1個の分散情報を参照し、そのうち高々k-1個の分散情報に対して改竄を行う不正を(1-ε)の確率で検知できる(k,n)しきい値法について記載されている。文献１に記載された方法では、秘密情報を要素数sの集合とし、s が s≦1/εとなる時、s^2/εの集合となる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上述の技術で、秘密情報がどのような確率で選択されていも、n-1個の分散情報を参照し、そのうち高々k-1個の分散情報を改竄する不正に対して安全な技術は、文献３および文献６だけである。しかしながら、文献３および文献６は(k,n)しきい値法についてしか方式を提案しておらず、しきい値法以外の秘密分散法で、n-1個の分散情報を参照して、そのうちの一つまたは複数の分散情報を改竄する不正に対して安全な秘密分散法は提案されていない。【００１２】
本発明はこのような状況に鑑みてなされたものであり、秘密情報がどのような分布に従って選ばれても不正の検知が可能であり、かつ分散情報数nに対し、n-1個の分散情報を参照し、そのうちの一つまたは複数の分散情報を改竄する不正に対して安全な秘密分散法であって、任意の秘密分散法にも適用可能とすることを目的とする。【００１３】
また本発明は、n-1個の分散情報を参照し、そのうちの一つまたは複数の分散情報を改竄する不正に対して安全な(k,n)しきい値法で、よりサイズの小さい分散情報を有することも目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するため、本発明の分散情報生成装置は、秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、乱数情報を秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、秘密情報と乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備える。【００１５】
本発明の復元装置は、秘密分散法のアクセス構造に対応する記憶手段から分散符号化された秘密情報を読み出し、アクセス構造にしたがって秘密情報を復元する秘密情報復元手段と、秘密分散法のアクセス構造に対応する記憶手段から分散符号化された乱数情報を読み出し、アクセス構造にしたがって乱数情報を復元する乱数情報復元手段と、秘密分散法のアクセス構造に対応する全ての記憶手段から、秘密情報と乱数情報に対応して生成されたチェック用データを読み出し、読み出されたチェック用データ全てが秘密情報復元手段で復元された秘密情報と乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備える。【００１６】
本発明の検証装置は、秘密情報と、乱数情報と、秘密情報と乱数情報に対応して生成されたチェック用データと、を取得し、チェック用データが秘密情報と乱数情報に対応している場合は、秘密情報の非改竄性が検証されたことを示す信号を出力し、対応していない場合は不正を示す信号を出力する。【００１７】
本発明の秘密情報分散システムは、分散情報生成装置と、記憶装置と、復元装置とを備える。分散情報生成装置は、秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、乱数情報を秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、秘密情報と乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備える。記憶装置は、分散符号化された秘密情報と、分散符号化された乱数情報と、チェック用データと格納する。復元装置は、アクセス構造に対応する記憶装置から分散符号化された秘密情報を読み出し、アクセス構造にしたがって秘密情報を復元する秘密情報復元手段と、アクセス構造に対応する記憶装置から分散符号化された乱数情報を読み出し、アクセス構造にしたがって乱数情報を復元する乱数情報復元手段と、アクセス構造に対応する全ての記憶装置からチェック用データを読み出し、読み出されたチェック用データ全てが秘密情報復元手段で復元された秘密情報と乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備える。
【発明の効果】
【００１８】
本発明によれば、秘密情報がどのような分布に従って選ばれても、n-1個の分散情報を参照し、そのうちのいくつかを改竄する不正を検知可能であり、かつ任意の秘密分散法にも適用可能である。【００１９】
また、復元されたチェック用データが復元された秘密情報に対応しているか否かを判定することで不正の検知が可能であり、チェック用データとして要素数の少ないデータ集合を用いれば分散情報のデータサイズを小さくできる。【００２０】
また、チェック用データを一様にランダムに選ぶことができるため、秘密情報がどのような分布にしたがって選ばれ、n-1個の分散情報が参照された場合でも高い不正の検知率が保証できる。【００２１】
さらに本発明のチェック用データおよび非改竄性のチェック方法は、適用する秘密分散法に非依存のものであるため、本発明は任意の秘密分散法に適用可能である。
【図面の簡単な説明】
【００２２】
【図１】図１は、本発明の第１の実施形態に係る分散情報生成装置の構成ブロック図である。
【図２】図２は、本発明の第１の実施形態に係る復元装置の構成ブロック図である。
【図３】図３は、本発明の第２の実施形態に係る検証装置の構成ブロック図である。
【図４】図４は、本発明の第１の実施形態に係る分散情報生成装置及び復元装置が行う処理を実行する処理装置の構成ブロック図である。
【図５】図５は、本発明の第１の実施形態に係る分散情報生成装置の動作処理を示すフローチャートである。
【図６】図６は、本発明の第１の実施形態に係る復元装置の動作処理を示すフローチャートである。
【発明を実施するための最良の形態】
【００２３】
以下に、本発明の実施形態について図面を用いて詳細に説明する。なお、以下に述べる実施の形態は、本発明の好適な実施の形態であるから、技術的に好ましい種々の限定が付されているが、本発明の範囲は、以下の説明において特に本発明を限定する旨の記載がない限り、これらの態様に限られるものではない。【００２４】
最初に本明細書で使用する用語について簡単に説明する。
アクセス構造、アクセス集合：アクセス構造とは秘密分散法において秘密情報を復元可能な最小の分散情報の集合を要素としてもつ集合族である。また、アクセス構造Γに対し、Ｖ∈ΓかつＶ⊆ＷとなるようなＶが存在するような集合ＷをΓのアクセス集合と定義する。アクセス集合 Ｗ に対応する秘密の分散情報を集めると、秘密の復元が可能となる。
秘密情報データ集合Ｓ：保管対象となる秘密情報ｓの集合を指す。
乱数データ集合Ｒ：分散される乱数rの集合を指す。
分散秘密情報データ集合VS_1,VS_2,...,VS_n：秘密情報ｓ∈Ｓを分散符号化したデータ（分散情報）の集合を指す。VS_i は第i番目の分散情報の集合を表している。
乱数分散情報データ集合VR_1,VR_2,...,VR_n：乱数ｒ∈Ｒを分散符号化したデータ（分散情報）の集合を指す。VR_i は第i番目の分散情報の集合を表している。
チェック用データ集合Ｅ：秘密情報ｓ∈Ｓと乱数ｒ∈Ｒに対応して生成したチェック用データの集合を指す。
演算子：本明細書において、+、-、*、^の記号をそれぞれ、和、差、積、冪乗演算子として用いる。【００２５】
本発明の実施形態に係る秘密情報分散システムは、秘密情報を保管する場合、秘密情報及び乱数に対応するチェック用データを生成し、秘密情報及び乱数をそれぞれ予め定められたアクセス構造にしたがって分散符号化し、それらを記憶装置に格納する。【００２６】
また、秘密情報を復元する場合、アクセス構造のいずれかの元に対応する複数の記憶装置から分散符号化された秘密情報及び分散符号化された乱数を読み出し、秘密情報及び乱数を復元する。【００２７】
そして、チェック用データが復元された秘密情報及び乱数に対応したものであるかを判定し、対応している場合は復元された秘密情報が正しいと判断し、対応していない場合は不正（改竄されている）と判断する。【００２８】
本発明の第１の実施形態に係る秘密情報分散システムは、図１に示すように、分散情報生成装置１００、復元装置２００及び複数の記憶装置３００＿１〜３００＿ｎを有する構成である。【００２９】
記憶装置３００＿１〜３００＿ｎは、分散秘密情報データ集合VS_1〜VS_nの元が格納される分散秘密情報記憶部３０１＿１〜３０１＿ｎと、乱数分散情報データ集合VR_1〜VS_nの元が格納される乱数分散情報記憶部３０２＿１〜３０２＿ｎと、チェック用データ集合Ｅの元が格納されるチェック用データ記憶部３０３＿１〜３０３＿ｎとを備えている。【００３０】
まず、分散情報生成装置１００の構成について図１を用いて説明する。図１は分散情報生成装置１００の構成ブロック図である。図１に示すように、分散情報生成装置１００は、秘密情報分散部１０１、乱数情報分散部１０２、チェック用データ生成装置１０３を備えている。【００３１】
秘密情報分散部１０１は、秘密情報ｓ（２）を入力とし、秘密情報ｓ（２）を予め定められたアクセス構造Γにしたがって分散符号化したn個のデータ（分散秘密情報） vs_1,vs_2,...,vs_n (vs_i∈VS)を出力する。【００３２】
乱数情報分散部１０２は、内部で乱数r∈Rを生成し、生成した前記乱数rと、前記乱数rを前記アクセス構造Γにしたがって分散符号化したn個のデータ（乱数分散情報） vr_1,vr_2,...,vr_n とを出力する。【００３３】
チェック用データ生成部１０３は、秘密情報s=(s_1,s_2,...,s_N)と、乱数情報分散部１０２の出力である乱数r=(r_1,r_2,...,r_[k-1])∈Rとを入力とし、n個の分散情報毎に独立にチェック用データe_1,e_2,...,e_n (ただし e_i=(e_[i0],e_[i1])∈E)を生成し、出力する。【００３４】
本実施形態では、各チェック用データ (e_[i0],e_[i1])∈Eは、予め定められた定数cに対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
を満足するデータとする。ただし、上記のkは、アクセス構造Γの元のなかで要素数が最大となる集合の要素数を表しているものとする。【００３５】
分散情報生成装置１００は秘密情報データ集合Ｓの元(要素)である秘密情報ｓを入力とし、記憶装置３００＿１〜３００＿ｎ内の分散秘密情報記憶部３０１＿１〜３０１＿ｎに秘密情報分散部の出力であるＶＳの元vs_1〜vs_nを、乱数分散情報記憶部３０２＿１〜３０２＿ｎに乱数分散装置１０２の出力である乱数分散情報ＶＲの元vr_1〜vr_nを、チェック用データ記憶部３０３＿１〜３０３＿ｎにチェック用データ集合Ｅの元であるチェック用データe_1〜e_nをそれぞれ格納する。【００３６】
次に復元装置２００の構成について図２を用いて説明する。図２は復元装置２００の構成ブロック図である。図２に示すように、復元装置２００は、秘密情報復元部２０１、乱数情報復元部２０２及び不正検出部２０３を備えている。【００３７】
秘密情報復元部２０１は予め定められたアクセス構造Γの任意のアクセス集合Ｗに対応する複数の記憶装置３００が備える分散秘密情報記憶部３０１に格納されたデータを読み出し、復元した秘密情報データｓ∈Ｓを出力する。【００３８】
乱数情報復元部２０２は前記アクセス構造Γと前記アクセス集合Ｗに対し、Ｗに対応する複数の記憶装置３００が備える乱数分散情報記憶部３０２に格納されたデータを読み出し、復元した乱数r∈Rを出力する。【００３９】
不正検出部２０３は、秘密情報復元部２０１で復元された秘密情報データs=(s_1,s_2,...,s_N)∈Sと乱数情報復元部２０２で復元された乱数r=(r_1,r_2,...,r_[k-1])∈Rと前記 Ｗ に対応する複数の記憶装置３００が備えるチェック用データ記憶部３０３に格納されたチェック用データを読み出し、読み出された全てのチェック用データ e_i=(e_[i0],e_[i1])∈Eに対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
が成立するかどうかを判定し、成立する時は復元した秘密情報s∈Sを出力し、成立しない時は不正を検知したことを示す記号を出力する。【００４０】
図１及び図２に示した分散情報生成装置１００及び復元装置２００は、例えば論理回路等から構成されるＬＳＩ（Large Scale Integration）やＤＳＰ（Digital Signal Processor）等の半導体集積回路によって実現される。【００４１】
また、分散情報生成装置１００及び復元装置２００は、図４に示すように、プログラムにしたがって所定の処理を実行する処理装置１０と、処理装置１０に対してコマンドや情報等を入力するための入力装置２０と、処理装置１０の処理結果をモニタするための出力装置３０とを備えたコンピュータによって実現してもよい。【００４２】
図４に示す処理装置１０は、ＣＰＵ１１と、ＣＰＵ１１の処理に必要な情報を一時的に記憶する主記憶部１２と、ＣＰＵ１１に後述する分散情報生成部１０２または復元装置２００としての処理を実行させるためのプログラムが記録された記録媒体１３と、秘密情報やアクセス構造データが格納されるデータ蓄積部１４と、主記憶部１２、記録媒体１３及びデータ蓄積装置１４とのデータ転送を制御するメモリ制御インタフェース部１５と、入力装置２０及び出力装置３０とのインタフェース部であるＩ／Ｏインタフェース部１６とを有し、それらがバス１８を介して接続された構成である。なお、データ蓄積部１４は、処理装置１０内にある必要はなく、処理装置１０から独立して備えていてもよい。また、データ蓄積部１４は、分散秘密情報記憶部３０１、乱数分散情報記憶部３０２及びチェック用データ記憶部３０３を備える記憶装置３００として用いてもよい。【００４３】
処理装置１０は、記録媒体１３に記録されたプログラムにしたがって後述する分散情報生成部１０２または復元装置２００としての機能を実現する。記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。【００４４】
次に本実施形態の秘密情報分散システムの動作について図５及び図６を用いて説明する。図５は分散情報生成装置１００の動作を示すフローチャートであり、図６は復元装置２００動作を示すフローチャートである。【００４５】
図５に示すように、分散情報生成部１０２には、秘密情報データ集合Ｓの元である秘密情報ｓ（２）が入力される（ステップＳ１）。【００４６】
分散情報生成装置１００は、秘密情報分散部１０１に秘密情報ｓが入力されると、秘密情報ｓを予め定められたアクセス構造Γに応じて分散符号化し、記憶装置３００の分散秘密情報記憶部３０１に格納する（ステップＳ２）。【００４７】
また、分散情報生成装置１００は、乱数情報分散部１０２により、乱数rを生成し、生成したrを前記アクセス構造Γに応じて分散符号化し、記憶装置３００の乱数分散情報記憶部３０２に格納する（ステップＳ３）。【００４８】
分散情報生成装置１００は、チェック用データ生成部１０３により、秘密情報ｓ、ステップＳ３で生成した乱数rに対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
を満足する n 個のe_i=(e_[i0],e_[i1]) (i=1,2,...,n)をランダムに生成し、記憶装置３００のチェック用データ記憶部３０３に格納する（ステップＳ４）。【００４９】
図６に示すように、復元装置２００は、前記アクセス構造Γの任意のアクセス集合Ｗに対応する複数の記憶装置３００の分散秘密情報記憶部３０１から読み出したデータを秘密情報復元部２０１に入力し、秘密情報データ集合Ｓの元ｓを復元する（ステップＳ５）。【００５０】
また、復元装置２００は、前記アクセス集合Ｗに対応する複数の前記記憶装置３００の乱数分散情報記憶部３０２から読み出したデータを乱数情報復元部２０２に入力し、乱数情報集合Ｒの元ｒを復元する（ステップＳ６）。【００５１】
次に、復元装置２００は、ステップＳ５で復元された秘密情報データ集合Ｓの元ｓとステップＳ６で復元されたｒと、前記アクセス集合Ｗに対応する複数の前記記憶装置３００のチェック用データ記憶部３０３から読み出した全てのデータ e_i=(e_[i0],e_[i1]) に対して、
c_i=e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]
を計算する（ステップＳ７）。【００５２】
ステップＳ７で計算された全ての c_i に対して c_i=c が成立する場合（ステップＳ８／Ｙｅｓ）、復元装置２００はｓを出力して終了する（ステップＳ１０）。いずれかの c_i に対して c_i=c が成立しない場合（ステップＳ８／Ｎｏ）、復元装置２００は、不正検出を表す記号を出力して終了する（ステップＳ９）。【００５３】
本実施形態によれば、復元されたチェック用データが復元された秘密情報に対応しているか否かを判定することで不正の検知が可能であり、チェック用データとして要素数の少ないデータ集合を用いれば分散情報のデータサイズを小さくできる。【００５４】
また、チェック用データを一様にランダムに選ぶことができるため、秘密情報がどのような分布にしたがって選ばれても高い不正の検知率が保証できる。【００５５】
また、不正検知のチェックを復元された後の秘密情報で行っていることにより、利用する秘密分散の方式に関わらず不正の検知が可能であるという特徴を有している。【００５６】
次に本発明の第２の実施形態について説明する。本実施形態における秘密情報分散システムは、分散情報生成装置１００、復元装置２００、検証装置４００、及び複数の記憶装置３００＿１〜３００＿ｎを有する構成である。記憶装置３００＿１〜３００＿ｎは、分散秘密情報データ集合VS_1〜VS_nの元が格納される分散秘密情報記憶部３０１＿１〜３０１＿ｎと、乱数分散情報データ集合VR_1〜VS_nの元が格納される乱数分散情報記憶部３０２＿１〜３０２＿ｎと、チェック用データ集合Ｅの元が格納されるチェック用データ記憶部３０３＿１〜３０３＿ｎとを備えている。【００５７】
本実施形態における、分散情報生成装置１００の構成は、図１に示す通りである。【００５８】
次に本実施形態に係る復元装置２００の構成は、図２に示す通りである。復元装置２００は、秘密情報復元部２０１、乱数情報復元部２０２及び不正検出部２０３を備えている。【００５９】
本実施形態に係る秘密情報復元部２０１及び乱数情報復元部２０２は第１の実施形態と同様である。【００６０】
不正検出部２０３は、秘密情報復元部２０１で復元された秘密情報データs=(s_1,s_2,...,s_N)∈Sと乱数情報復元部２０２で復元された乱数r=(r_1,r_2,...,r_[k-1])∈Rと前記 Ｗ に対応する複数の記憶装置３００が備えるチェック用データ記憶部３０３に格納されたチェック用データを読み出し、読み出された全てのチェック用データ e_i=(e_[i0],e_[i1])∈Eに対して、e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=cが成立するかどうかを判定し、成立する時は復元した秘密情報ｓ∈Ｓおよび復元した乱数ｒ∈Ｒを出力し、成立しない時は不正を検知したことを示す記号を出力する。【００６１】
第１の実施形態と比較すると、本実施形態に係る不正検出部２０３は、秘密情報だけでなく乱数も出力する点で異なる。【００６２】
次に、本実施形態に係る検証装置４００について図３を用いて説明する。検証装置４００は、秘密情報復元部２０１で復元された秘密情報データs=(s_1,s_2,...,s_N)∈Sと乱数情報復元部２０２で復元された乱数r=(r_1,r_2,...,r_[k-1])∈Rと記憶装置３００＿ｉが備えるチェック用データ記憶部３０２＿ｉに格納されたチェック用データを読み出し、読み出されたチェック用データ e_i=(e_[i0],e_[i1])∈Eに対して、
e_[i0]+s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]=c
が成立するかどうかを判定し、成立する時は復元した秘密情報が正しいことを表す記号を出力し、成立しない時は不正を検知したことを示す記号を出力する。【００６３】
本実施形態では、記憶装置３００＿ｉが秘密復元時にデータを提供しなかった場合でも、秘密が復元された後に、復元装置２００から出力された秘密情報ｓおよび乱数情報ｒと、前記記憶装置３００＿ｉに格納されているチェック用データを検証装置４００に入力することにより、復元されたｓの非改竄性を検証することが可能であるという特徴を有している。【００６４】
次に、本発明の実施例について説明する。
［第１実施例］
本実施例に係る秘密情報分散システムは、秘密情報 s=(s_1,s_2,...,s_N) のデータ集合にGF(p^N) (p: 素数, GF:ガロア体)を、乱数データ r=(r_1,r_2,...,r_[k-1])として、GF(p^[k-1]) の元を、チェック用データ e=(e_0,e_1) として GF(p)^2 として用いる。また本実施例では、有限体上の加算を+、減算を-、乗算を*、除算を/、冪乗算を^で表す。【００６５】
また、本実施例では、秘密分散のアクセス構造を (k,n)しきい値型のアクセス構造とし、秘密情報分散部１０１及び乱数情報分散部１０２は、文献１に記載された(k,n)しきい値法を用いて分散符号化し、秘密情報復元部２０１及び乱数情報復元部２０２は、その(k,n)しきい値法に対応する復元方法を用いて秘密情報及び乱数情報を復元することが可能である。【００６６】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。本実施例に係る分散情報生成装置１００には、秘密情報s=(s_1,s_2,...,s_N)∈GF(p^N) (各 s_i∈GF(p))が入力される。【００６７】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１によりGF(p^N)上の定数項がｓであるk-1次多項式をランダムに生成する。このk-1次多項式をf_s(x)と記す。【００６８】
秘密情報分散部１０１は、相異なる i_1,i_2,...,i_n に対して、 f_s(i_1),f_s(i_2), …,f_s(i_n)を計算し、その計算結果を記憶装置３００＿１の分散秘密情報記憶部３０１＿１、記憶装置３００＿２の分散秘密情報記憶部３０１＿２,…,記憶装置３００＿ｎの分散秘密情報記憶部３０１＿ｎにそれぞれ格納する。【００６９】
乱数情報分散部１０２は、GF(p^[k-1])の元である乱数 r を生成し、GF(p^[k-1])上の定数項がrであるk-1次多項式をランダムに生成する。このk-1次多項式をf_r(x)と記す。【００７０】
次に、乱数情報分散部１０２は、前記 i_1,i_2,...,i_n に対して f_r(i_1),f_r(i_2), …,f_r(i_n)を計算し、その計算結果を記憶装置３００＿１の乱数分散情報記憶部３０２＿１、記憶装置３００＿２の乱数分散情報記憶部３０２＿２,…,記憶装置３００＿ｎの乱数分散情報記憶部３０２＿ｎにそれぞれ格納する。【００７１】
チェック用データ生成部１０３は、i=1,2,...,n に対して, e_[i1] を GF(p) 上からランダムに選び、次に、e_[i0] (i=1,2,...,n)を
e_[i0]=-(s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[k-1]*e_[i1]^[N+k-1]) 
にしたがって計算し、得られた(e_[i0],e_[i1]) (i=1,2,...,n)を記憶装置３００＿ｉのチェック用データ記憶部３０３＿ｉに格納する。【００７２】
一方、本実施例に係る復元装置２００は、記憶装置300_[i_1],300_[i_2], …,300_[i_k]の各分散秘密情報記憶部３０１からデータを読み出す。これらのデータをvs_[i_1], vs_[i_2], …,vs_[i_k]と記す。【００７３】
秘密情報復元部201は、(i_1,vs_[i_1]),(i_2,vs_[i_2]),…,(i_k,vs_[i_k])を入力とし、座標(i_1,vs_[j_1]),(i_2,vs_[i_2]),…,(i_k,vs_[i_k])を通る GF(p^N) 上のk-1次多項式g_s(x)のg_s(0)生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりs'=g_s(0)を計算する。【００７４】
また、復元装置２００は、記憶装置300_[i_1],300_[i_2],…,300_[i_k]の各乱数分散情報記憶部302からデータを読み出す。これらのデータを vr_[i_1],vr_[i_2],...,vr_[i_k]と記す。【００７５】
乱数情報復元部２０２は、(i_1,vr_[j_1]),(i_2,vr_[i_2]),…,(i_k,vr_[i_k])を入力とし、座標(i_1,vr_[i_1]),(i_2,vr_[i_2]),…,(i_k,vr_[i_k])を通る GF(p^[k-1])のk-1次多項式g_r(x)のg_r(0)を生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりr'=g_r(0)を計算する。【００７６】
次に、復元装置２００は、記憶装置300_[i_1],300_[i_2],…,300_[i_k]の各チェック用データ記憶部303からデータを読み出す。これらのデータをe_[i_1],e_[i_2],...,e_[i_k]と記す（各 e_[i_j]=(e_[i_j0],e_[i_j1])）。【００７７】
不正検知装置203は、s'=(s'_1,s'_2,...,s'_N), r'=(r'_1,r'_2,...,r'_[k-1]), e_[i_1]=(e_[i_10],e_[i_11]),e_[i_2]=(e_[i_20],e_[i_21]),...,e_[i_k]=(e_[i_k0],e_[i_k1])を入力とし、j=1,2,...,k について
e_[i_j0]+(s'_1*e_[i_j1]+s'_2*e_[i_j1]^2+...+s'_N*e_[i_j1]^N+r'_1*e_[i_j1]^[N+1]+r'_2*e_[i_j1]^[N+2]+...+r'_[k-1]*e_[i_j1]^[N+k-1])=0
が成立するか否かをチェックする。成立する場合は、s' を秘密情報として出力し、成立していない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【００７８】
本実施例に係る秘密情報分散システムでは、秘密情報のサイズはp^Nであり、分散情報のサイズはp^[N+k+1]であり、不正の検出率は(1-(N+k+1)/p)である。【００７９】
ここで、秘密情報のサイズをs、不正の検出率を(1-ε)と記すと、分散情報のサイズはほぼs*((log s)/ε)^[k+1]で表せる。【００８０】
上述した文献２に記載された秘密分散法の分散情報のサイズは ((s-1)(k-1) / ε+k)^2、文献６の分散情報のサイズは s^2/ε である。そのため s が大きく k が小さい場合は、本実施例の分散情報のサイズの方が両方式より小さくなることが分かる。【００８１】
［第２実施例］
本実施例の秘密情報分散システムも、秘密情報 s=(s_1,s_2,...,s_N) のデータ集合にGF(p^N) (p: 素数, GF:ガロア体)を、乱数データ r = (r_1,r_2,...,r_[k-1])として、GF(p^[k-1]) の元を、チェック用データ e = (e_0,e_1) として GF(p)^2 として用いる。また本実施例では、有限体上の加算を+、減算を-、乗算を*、除算を/、冪乗算を^で表す。【００８２】
また、秘密分散のアクセス構造を (n,n)しきい値型のアクセス構造とし、秘密情報分散部１０１及び乱数情報分散部１０２は、文献４に記載された(n,n)しきい値法を用いて分散符号化し、秘密情報復元部２０１及び乱数情報復元部２０２は、その(n,n)しきい値法に対応する復元方法を用いて秘密情報及び乱数情報を復元するものとする。【００８３】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。分散情報生成装置１００には、秘密情報s=(s_1,s_2,...,s_N)∈GF(p^N) (各 s_i∈GF(p))が入力される。【００８４】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１により、 vs_1+vs_2+...+vs_n=s となる GF(p^N) の元 vs_1,vs_2,...,vs_nをランダムに選び、各vs_i (i=1,2,...,n)を記憶装置３００＿ｉの分散秘密情報記憶部３０１＿ｉに格納する。【００８５】
乱数情報分散部102は、GF(p^[n-1])の元である乱数 r を生成し、vr_1+vr_2+...+vr_n=r となる GF(p^[n-1]) の元 vr_1,vr_2,...,vr_nをランダムに選び、各vr_i (i=1,2,...,n)を記憶装置３００＿ｉの分散乱数情報記憶部３０２＿ｉに格納する。【００８６】
チェック用データ生成部１０３は、i=1,2,...,n に対して, e_[i1] を GF(p) 上からランダムに選び、次に、e_[i0] (i=1,2,...,n)を
e_[i0]=-(s_1*e_[i1]+s_2*e_[i1]^2+...+s_N*e_[i1]^N+r_1*e_[i1]^[N+1]+r_2*e_[i1]^[N+2]+...+r_[n-1]*e_[i1]^[N+n-1]) 
にしたがって計算し、得られた(e_[i0],e_[i1]) (i=1,2,...,n)を記憶装置３００＿ｉのチェック用データ記憶部３０３＿ｉに格納する。【００８７】
復元装置２００は、記憶装置３００＿１、３００＿２、・・・３００＿ｎの各分散秘密情報記憶部３０１からデータを読み出す。これらのデータをvs_1,vs_2,…,vs_nと記す。【００８８】
秘密情報復元部２０１は、s'をs'=vs_1+vs_2+...+vs_n により計算する。【００８９】
また、復元装置２００は、記憶装置３００＿１、３００＿２、・・・３００＿nの各乱数分散情報記憶部３０２からデータを読み出す。これらのデータを vr_1,vr_2,...,vr_nと記す。【００９０】
乱数情報復元部２０２は、r'をr'=vr_1+vr_2+...+vr_n により計算する。【００９１】
次に、復元装置２００は、記憶装置３００＿１、３００＿２、・・・３００＿nの各チェック用データ記憶部３０３からデータを読み出す。これらのデータを e_1,e_2,...,e_nと記す（各 e_i=(e_[i0],e_[i1])）。【００９２】
不正検知装置２０３は、s'=(s'_1,s'_2,...,s'_N), r'=(r'_1,r'_2,...,r'_[k-1]), e_I = (e_[i0],e_[i1]) (i=1,2,...,n)を入力とし、i=1,2,...,n について
e_[i0]+(s'_1*e_[i1]+s'_2*e_[i1]^2+...+s'_N*e_[i1]^N+r'_1*e_[i1]^[N+1]+r'_2*e_[i1]^[N+2]+...+r'_[n-1]*e_[i1]^[N+n-1])=0
が成立するか否かをチェックする。成立する場合は、s'を秘密情報として出力し、成立していない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【００９３】
上記第１実施例の秘密情報分散システムでは、秘密情報のサイズはp^Nであり、分散情報のサイズはp^[N+k+1]であり、不正の検出率は(1-(N+n+1)/p)である。ここで、本実施例では、秘密情報のサイズをｓ、不正の検出率を(1-ε)と記すと、分散情報のサイズはほぼs*((log s)/ε)^[n+1]で表せる。【００９４】
本実施例によれば、(n,n)しきい値秘密分散法をベースに方式を構成することが可能であり、また、n-1個の分散情報の改竄を防止可能である。【００９５】
［第３実施例］
本実施例に係る秘密分散システムは、上記不正検出部２０３が秘密情報だけでなく乱数も出力する実施形態に関する実施例である。本実施例では、秘密情報 s=(s_1,s_2,...,s_N) のデータ集合にGF(p^N) (p: 素数, GF:ガロア体)を、乱数データ r=(r_1,r_2,...,r_[k-1])として、GF(p^[k-1]) の元を、チェック用データ e=(e_0,e_1) として GF(p)^2 として用いる。また本実施例では、有限体上の加算を+、減算を-、乗算を*、除算を/、冪乗算を^で表す。【００９６】
第３実施例では、第１実施例と同様に秘密分散のアクセス構造を (k,n)しきい値型のアクセス構造とし、秘密情報分散部１０１及び乱数情報分散部１０２は、文献１に記載された(k,n)しきい値法を用いて分散符号化する。秘密情報復元部２０１及び乱数情報復元部２０２は、その(k,n)しきい値法に対応する復元方法を用いて秘密情報及び乱数情報を復元するものとする。【００９７】
次に第３実施例に係る分散情報生成装置１００及び復元装置２００について説明する。分散情報生成装置１００は、第１実施例に係る分散情報生成装置１００と同一である。一方、復元装置２００は、記憶装置300_[i_1],300_[i_2],…,300_[i_k]の各分散秘密情報記憶部３０１からデータを読み出す。これらのデータをvs_[i_1],vs_[i_2],…,vs_[i_k]と記す。【００９８】
第３実施例に係る秘密情報復元部２０１、乱数情報復元部２０２は、第１実施例に係る秘密情報復元部２０１、乱数情報復元部２０２と同一である。【００９９】
不正検知装置２０３は、記憶装置300_[i_1],300_[i_2],…,300_[i_k]の各チェック用データ記憶部３０３に格納されているデータ e_[i_1],e_[i_2],...,e_[i_k] (各 e_[i_j] =(e_[i_j0],e_[i_j1]))と、秘密情報復元部２０１の出力s'=(s'_1,s'_2,...,s'_N)と、乱数情報復元部 r'=(r'_1,r'_2,...,r'_[k-1])を入力とし、j=1,2,...,k について
e_[i_j0]+(s'_1*e_[i_j1]+s'_2*e_[i_j1]^2+...+s'_N*e_[i_j1]^N+r'_1*e_[i_j1]^[N+1]+r'_2*e_[i_j1]^[N+2]+...+r'_[k-1]*e_[i_j1]^[N+k-1])=0
が成立するか否かをチェックする。成立する場合は、s' を秘密情報、r' を乱数情報として出力し、成立していない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【０１００】
第３実施例に係る検証装置４００は、記憶装置３００＿ｉの各チェック用データ記憶部３０３＿ｉから読み出たチェック用データ e_i=(e_[i0],e_[i1])と、秘密情報s' = (s'_1,s'_2,...,s'_N)と、乱数情報 r'=(r'_1,r'_2,...,r'_[k-1])を入力とし、
e_[i0]+(s'_1*e_[i1]+s'_2*e_[i1]^2+...+s'_N*e_[i1]^N+r'_1*e_[i1]^[N+1]+r'_2*e_[i1]^[N+2]+...+r'_[k-1]*e_[i1]^[N+k-1])=0
が成立するかどうかを判定し、成立する時は復元した秘密情報が正しいことを表す記号を出力し、成立しない時は不正を検知したことを示す記号を出力する。【０１０１】
検証装置４００を用いることにより、秘密の復元時に分散情報を復元部に入力しなかった記憶装置３００＿ｉも、秘密復元後に、記憶装置３００＿ｉのチェック用データ記憶部３０３＿ｉに格納されているチェック用データと、復元された秘密情報s'と、復元された乱数情報r'とから、復元された秘密情報s'の非改竄性を検証することが可能となる。【０１０２】
なお、フローチャートに示す処理を、ＣＰＵが実行するためのプログラムは本発明によるプログラムを構成する。このプログラムを記録する記録媒体としては、半導体記憶部や光学的及び／又は磁気的な記憶部等を用いることができる。このようなプログラム及び記録媒体を、前述した各実施形態、実施例とは異なる構成のシステム等で用い、そこのＣＰＵで上記プログラムを実行させることにより、本発明と実質的に同じ効果を得ることができる。【０１０３】
以上、本発明を好適な実施形態、実施例に基づき具体的に説明したが、本発明は上記のものに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。例えば、図１及び図２では記憶装置３００＿１〜３００＿ｎを分散情報生成装置１００及び復元装置２００から独立した構成にしているが、記憶装置３００＿１〜３００＿ｎを分散情報生成装置または復元装置２００に内蔵させ、分散情報生成装置または復元装置２００の構成要素にしてもよい。【０１０４】
この出願は、２００７年１２月１２日に出願された日本出願特願２００７−３２０８３０号を基礎とする優先権を主張し、その開示のすべてをここに取り込む。
【図１】
2009075353.tif 000003
【図２】
2009075353.tif 000004
【図３】
2009075353.tif 000005
【図４】
2009075353.tif 000006
【図５】
2009075353.tif 000007
【図６】
2009075353.tif 000008
【手続補正書】
【提出日】平成21年5月11日(2009.5.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
（削除）
【請求項３】
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備え、
前記チェック用データ生成手段は、要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、予め定められた定数ｃに対して、
ｅ＿［ｉ０］＋ｓ＿１＊ｅ＿［ｉ１］＋ｓ＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすｎ個のＧＦ（ｐ）＾２の元（ｅ＿［１０］，ｅ＿［１１］），（ｅ＿［２０］，ｅ＿［２１］），．．．，（ｅ＿［ｎ０］，ｅ＿［ｎ１］）をランダムに選ぶ分散情報生成装置。
【請求項４】
前記秘密情報分散手段は、前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造を用いる請求項３記載の分散情報生成装置。
【請求項５】
前記秘密情報分散手段は、前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う（ｎ，ｎ）しきい法を用いる請求項３記載の分散情報生成装置。
【請求項６】
（削除）
【請求項７】
（削除）
【請求項８】
（削除）
【請求項９】
秘密分散法のアクセス構造にしたがって分散符号化された秘密情報と、前記秘密分散法のアクセス構造にしたがって分散符号化された乱数情報と、前記秘密情報と前記乱数情報に対応して生成されたチェック用データと、を格納する記憶手段と、
前記秘密分散法のアクセス構造に対応する前記記憶手段から分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元手段と、
前記秘密分散法のアクセス構造に対応する前記記憶手段から分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元手段と、
前記秘密分散法のアクセス構造に対応する全ての前記記憶手段からチェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元手段で復元された秘密情報と前記乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備え、
前記不正検知手段は、
要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、
要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、
前記秘密分散法のアクセス構造に対応するチェック用データ
（ｅ＿［ｉ＿１０］，ｅ＿［ｉ＿１１］，（ｅ＿［ｉ＿２０］，ｅ＿［ｉ＿２１］，．．．，（ｅ＿［ｉ＿ｍ０］，ｅ＿［ｉ＿ｍ１］と、を入力とし、
予め定められた定数ｃと、任意のｊ＝１，２，．．．，ｍに対し、
ｅ＿［ｉ＿ｊ０］＋ｓ＿１＊ｅ＿［ｉ＿ｊ１］＋ｓ＿２＊ｅ＿［ｉ＿ｊ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ＿ｊ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定する復元装置。
【請求項１０】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造が用いられる請求項９記載の復元装置。
【請求項１１】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う（ｎ，ｎ）しきい法が用いられる請求項９記載の復元装置。
【請求項１２】
（削除）
【請求項１３】
要素数ｐ＾Ｎの元である秘密情報ｓ’＝（ｓ’＿１，ｓ’＿２，．．．，ｓ’＿Ｎ）と、
要素数ｐ＾［ｋ−１］の元である乱数情報ｒ’＝（ｒ’＿１，ｒ’＿２，．．．，ｒ’＿［ｋ−１］）と、
分散情報生成装置によって生成されたチェック用データ（ｅ＿［ｉ＿１０］，ｅ＿［ｉ＿１１］）と、を入力とし、
予め定められた定数ｃに対し、
ｅ＿［ｉ０］＋ｓ’＿１＊ｅ＿［ｉ１］＋ｓ’＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ’＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ’＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ’＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ’＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記秘密情報ｓ’が改竄されていないと判定し、
前記秘密情報ｓ’が改竄されていないと判定した場合は、秘密情報の非改竄性が検証されたことを示す信号を出力し、改竄されていると判定した場合は、不正を示す信号を出力し、
前記分散情報生成装置は、
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備え、
前記チェック用データ生成手段は、要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、予め定められた定数ｃに対して、
ｅ＿［ｉ０］＋ｓ＿１＊ｅ＿［ｉ１］＋ｓ＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすｎ個のＧＦ（ｐ）＾２の元（ｅ＿［１０］，ｅ＿［１１］），（ｅ＿［２０］，ｅ＿［２１］），．．．，（ｅ＿［ｎ０］，ｅ＿［ｎ１］）をランダムに選ぶ検証装置。
【請求項１４】
（削除）
【請求項１５】
分散情報生成装置と、記憶装置と、復元装置とを備え、
前記分散情報生成装置は、
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備え、
前記記憶装置は、前記分散符号化された秘密情報と、前記分散符号化された乱数情報と、前記チェック用データと格納し、
前記復元装置は、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元手段と、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元手段と、
前記アクセス構造に対応する全ての前記記憶装置から前記チェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元手段で復元された秘密情報と前記乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備え、
前記チェック用データ生成手段は、要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、予め定められた定数ｃに対して、
ｅ＿［ｉ０］＋ｓ＿１＊ｅ＿［ｉ１］＋ｓ＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすｎ個のＧＦ（ｐ）＾２の元（ｅ＿［１０］，ｅ＿［１１］），（ｅ＿［２０］，ｅ＿［２１］），．．．，（ｅ＿［ｎ０］，ｅ＿［ｎ１］）をランダムに選び、
前記不正検知手段は、
要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、
要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、
前記秘密分散法のアクセス構造に対応するチェック用データ
（ｅ＿［ｉ＿１０］，ｅ＿［ｉ＿１１］，（ｅ＿［ｉ＿２０］，ｅ＿［ｉ＿２１］，．．．，（ｅ＿［ｉ＿ｍ０］，ｅ＿［ｉ＿ｍ１］と、を入力とし、
予め定められた定数ｃと、任意のｊ＝１，２，．．．，ｍに対し、
ｅ＿［ｉ＿ｊ０］＋ｓ＿１＊ｅ＿［ｉ＿ｊ１］＋ｓ＿２＊ｅ＿［ｉ＿ｊ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ＿ｊ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定する秘密情報分散システム。
【請求項１６】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造が用いられる請求項１５記載の秘密情報分散システム。
【請求項１７】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う（ｎ，ｎ）しきい法が用いられる請求項１５記載の秘密情報分散システム。
【請求項１８】
（削除）
【請求項１９】
（削除）
【請求項２０】
分散情報生成装置と、記憶装置と、復元装置と、検証装置とを備え、
前記分散情報生成装置は、
秘密情報を秘密分散法のアクセス構造にしたがって分散符号化する秘密情報分散手段と、
乱数情報を前記秘密分散法のアクセス構造にしたがって分散符号化する乱数情報分散手段と、
前記秘密情報と前記乱数情報に対応するチェック用データを生成するチェック用データ生成手段とを備え、
前記記憶装置は、前記分散符号化された秘密情報と、前記分散符号化された乱数情報と、前記チェック用データと格納し、
前記復元装置は、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された秘密情報を読み出し、前記アクセス構造にしたがって前記秘密情報を復元する秘密情報復元手段と、
前記アクセス構造に対応する前記記憶装置から前記分散符号化された乱数情報を読み出し、前記アクセス構造にしたがって前記乱数情報を復元する乱数情報復元手段と、
前記アクセス構造に対応する全ての前記記憶装置から前記チェック用データを読み出し、読み出された前記チェック用データ全てが前記秘密情報復元手段で復元された秘密情報と前記乱数情報復元手段で復元された乱数情報に対応している場合は復元された秘密情報及び復元された乱数を出力し、対応していない場合は不正を示す信号を出力する不正検知手段とを備え、
前記検証装置は、前記秘密情報復元手段で復元された秘密情報と、前記乱数情報復元手段で復元された乱数情報と、前記記憶装置に格納されているチェック用データと、を取得し、前記秘密情報が改竄されていないと判定した場合は、秘密情報の非改竄性が検証されたことを示す信号を出力し、改竄されていると判定した場合は、不正を示す信号を出力し、
前記チェック用データ生成手段は、要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、予め定められた定数ｃに対して、
ｅ＿［ｉ０］＋ｓ＿１＊ｅ＿［ｉ１］＋ｓ＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすｎ個のＧＦ（ｐ）＾２の元（ｅ＿［１０］，ｅ＿［１１］），（ｅ＿［２０］，ｅ＿［２１］），．．．，（ｅ＿［ｎ０］，ｅ＿［ｎ１］）をランダムに選び、
前記不正検知手段は、
要素数ｐ＾Ｎの体の元である秘密情報ｓ＝（ｓ＿１，ｓ＿２，．．．，ｓ＿Ｎ）と、
要素数ｐ＾［ｋ−１］の体の元である乱数情報ｒ＝（ｒ＿１，ｒ＿２，．．．，ｒ＿［ｋ−１］）と、
前記秘密分散法のアクセス構造に対応するチェック用データ
（ｅ＿［ｉ＿１０］，ｅ＿［ｉ＿１１］，（ｅ＿［ｉ−２０］，ｅ＿［ｉ＿２１］，．．．，（ｅ＿［ｉ＿ｍ０］，ｅ＿［ｉ＿ｍ１］と、を入力とし、
予め定められた定数ｃと、任意のｊ＝１，２，．．．，ｍに対し、
ｅ＿［ｉ＿ｊ０］＋ｓ＿１＊ｅ＿［ｉ＿ｊ１］＋ｓ＿２＊ｅ＿［ｉ＿ｊ１］＾２＋．．．＋ｓ＿Ｎ＊ｅ＿［ｉ＿ｊ１］＾Ｎ＋ｒ＿１＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋１］＋ｒ＿２＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋２］＋．．．＋ｒ＿［ｋ−１］＊ｅ＿［ｉ＿ｊ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記チェック用データが前記秘密情報復元手段で復元された秘密情報に対応していると判定し、
前記検証装置は、
要素数ｐ＾Ｎの元である秘密情報ｓ’＝（ｓ’＿１，ｓ’＿２，．．．，ｓ’＿Ｎ）と、
要素数ｐ＾［ｋ−１］の元である乱数情報ｒ’＝（ｒ’＿１，ｒ’＿２，．．．，ｒ’＿［ｋ−１］）と、
前記チェック用データ（ｅ＿［ｉ＿１０］，ｅ＿［ｉ＿１１］）と、を入力とし、
予め定められた定数ｃに対し、
ｅ＿［ｉ０］＋ｓ’＿１＊ｅ＿［ｉ１］＋ｓ’＿２＊ｅ＿［ｉ１］＾２＋．．．＋ｓ’＿Ｎ＊ｅ＿［ｉ１］＾Ｎ＋ｒ’＿１＊ｅ＿［ｉ１］＾［Ｎ＋１］＋ｒ’＿２＊ｅ＿［ｉ１］＾［Ｎ＋２］＋．．．＋ｒ’＿［ｋ−１］＊ｅ＿［ｉ１］＾［Ｎ＋ｋ−１］＝ｃ
（なお、ｐは素数であり、ｋは秘密を復元するのに必要な分散情報の最大数）
を満たすとき、前記秘密情報ｓ’が改竄されていないと判定する秘密情報分散システム。
【請求項２１】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造が用いられる請求項２０記載の秘密情報分散システム。
【請求項２２】
前記秘密分散法として、秘密の復元を全分散情報の和を取ることによって行う（ｎ，ｎ）しきい法が用いられる請求項２０記載の秘密情報分散システム。
【請求項２３】
（削除）
【請求項２４】
（削除）
【請求項２５】
（削除）
【請求項２６】
（削除）
【請求項２７】
（削除）
【請求項２８】
（削除）
【請求項２９】
（削除）
【請求項３０】
（削除）
【請求項３１】
（削除）
【請求項３２】
（削除）
【国際調査報告】
2009075353.tif 000009
2009075353.tif 000010
2009075353.tif 000011
2009075353.tif 000012
2009075353.tif 000013
2009075353.tif 000014
2009075353.tif 000015
2009075353.tif 000016