(57)【特許請求の範囲】
【請求項１】
秘密情報に対応するチェック用データを生成するチェック用データ生成装置と、
前記秘密情報を線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化する秘密情報分散装置と、
前記秘密情報を分散符号化したアクセス構造と同一のアクセス構造を示すアクセス構造データにしたがって前記チェック用データを分散符号化するチェック用データ分散装置と、
を有し、
前記チェック用データ生成装置は、
秘密情報データ集合Ｓの元ｓを入力とし、
Ｈ＿ｋ（ｘ）＝ｙとなるような関数集合Ｈの元を一意に指定する関数指定データｋをランダムに選び、出力する装置であり、
前記関数集合Ｈが、
前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）とすると、
任意の相異なる前記秘密情報データ集合Ｓの元のｘ＿１及びｘ＿２と、前記関数集合Ｈの任意の関数指定データｃに対し、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜＜δである分散情報生成装置。
【請求項２】
前記チェック用データ生成装置は、
Ｎを正数、ｐを素数としたとき、秘密情報データ集合Ｓとして（Ｚ／ｐＺ）＾Ｎを用い、
前記秘密情報データ集合Ｓの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）に対し、
ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｘ＿｛Ｎ｝＊ｅ＿１＾｛Ｎ＋１｝）＝０を満たすＺ／ｐＺの元ｅ＿０及びｅ＿１をランダムに選び、前記チェック用データとして出力する請求項１記載の分散情報生成装置。
【請求項３】
線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化された秘密情報及び前記秘密情報に対応して生成されたチェック用データの分散符号化されたデータが格納される記憶装置と、
前記アクセス構造のアクセスセットに対応する前記記憶装置から分散符号化された秘密情報を読み出し、前記アクセス構造データにしたがって前記秘密情報を復元する秘密情報復元装置と、
前記アクセス構造のアクセスセットに対応する前記記憶装置から分散符号化されたチェック用データを読み出し、前記アクセス構造データにしたがって前記チェック用データを復元するチェック用データ復元装置と、
前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応している場合は復元した秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知装置と、
を有し、
前記不正検知装置は、
前記秘密情報として入力される入力集合Ｓの任意の相異なる元をｘ＿１及びｘ＿２とし、関数集合Ｈの元を一意に指定するデータである任意の関数指定データをｃとし、前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）としたとき、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるようなＨにおいて、
復元したチェック用データである前記関数指定データｋと復元した秘密情報ｘとがＨ＿ｋ（ｘ）＝ｙを満たすとき、前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応していると判定する復元装置。
【請求項４】
前記不正検知装置は、
Ｎを整数、ｐを素数としたとき、
復元したチェック用データであり、Ｚ／ｐＺの元である前記関数指定データｅ＿０，ｅ＿１と、復元した秘密情報であり、（Ｚ／ｐＺ）＾Ｎの元である（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）とが、ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｘ＿Ｎ＊ｅ＿１＾｛Ｎ＋１｝）＝０を満たすとき、前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応していると判定する請求項３記載の復元装置。
【請求項５】
請求項１記載の分散情報生成装置と、
請求項３記載の復元装置と、
を有する秘密情報分散システム。
【請求項６】
請求項２記載の分散情報生成装置と、
請求項４記載の復元装置と、
を有する秘密情報分散システム。
【請求項７】
コンピュータが、
秘密情報に対応するチェック用データを生成し、
前記秘密情報を線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化して記憶装置に格納し、
前記秘密情報を分散符号化したアクセス構造と同一のアクセス構造を示すアクセス構造データにしたがって前記チェック用データを分散符号化して記憶装置に格納するためのプログラムであり、
秘密情報データ集合Ｓの元ｓを入力とし、
Ｈ＿ｋ（ｘ）＝ｙとなるような関数集合Ｈの元を一意に指定する関数指定データｋをランダムに選び、前記チェック用データとして出力させる、
関数集合Ｈが、
前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）とすると、
任意の相異なる前記秘密情報データ集合Ｓの元のｘ＿１及びｘ＿２と、前記関数集合Ｈの任意の関数指定データｃに対し、
｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるプログラム。
【請求項８】
Ｎを正数、ｐを素数としたとき、秘密情報データ集合Ｓとして（Ｚ／ｐＺ）＾Ｎを用い、
Ｓの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）に対し、
ｅ＿０−（ｘ＿１＊＿１＋ｘ＿２＊ｅ−１＾２＋・・・＋ｘ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｘ＿Ｎ＊ｅ＿１＾｛Ｎ＋１｝）＝０を満たすＺ／ｐＺの元ｅ＿０及びｅ＿１をランダムに選び、前記チェック用データとして出力するための請求項７記載のプログラム。
【請求項９】
コンピュータが、
線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化された秘密情報が格納された記憶装置から前記アクセス構造のアクセスセットに対応する分散符号化された秘密情報を読み出し、前記アクセス構造データにしたがって前記秘密情報を復元し、
前記秘密情報に対応して生成されたチェック用データの分散符号化されたデータが格納された記憶装置から前記アクセス構造のアクセスセットに対応する分散符号化されたチェック用データを読み出し、前記アクセス構造データにしたがって前記チェック用データを復元し、
前記復元されたチェック用データが前記復元された秘密情報に対応している場合は復元した秘密情報を出力し、対応していない場合は不正を示す信号を出力するためのプログラムであり、
前記秘密情報として入力される入力集合Ｓの任意の異なる元をｘ＿１及びｘ＿２とし、関数集合Ｈの元を一意に指定するデータである任意の関数指定データをｃとし、前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）としたとき、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるようなＨにおいて、
復元したチェック用データである前記関数指定データｋと復元した秘密情報ｘとがＨ＿ｋ（ｘ）＝ｙを満たすとき、前記復元されたチェック用データが前記復元された秘密情報に対応していると判定するためのプログラム。
【請求項１０】
Ｎを正数、ｐを素数としたとき、
復元したチェック用データであり、Ｚ／ｐＺの元である前記関数指定データｅ＿０，ｅ＿１と、復元した秘密情報であり、（Ｚ／ｐＺ）＾Ｎの元である（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）とが、ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｘ＿Ｎ＊ｅ＿１＾｛Ｎ＋１｝）＝０を満たすとき、前記復元されたチェック用データが前記復元された秘密情報に対応していると判定する請求項９記載のプログラム。
【請求項１１】
請求項７に記載のプログラムと、
請求項９に記載のプログラムと、
を有するプログラム。
【請求項１２】
請求項８に記載のプログラムと、
請求項１０に記載のプログラムと、
を有するプログラム。
【請求項１３】
秘密情報に対応するチェック用データを生成するチェック用データ生成装置と、
前記秘密情報を線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化する秘密情報分散装置と、
前記秘密情報を分散符号化したアクセス構造と同一のアクセス構造を示すアクセス構造データにしたがって前記チェック用データを分散符号化するチェック用データ分散装置と、
を有し、
前記チェック用データ生成装置は、
秘密情報データ集合Ｓの元ｓを入力とし、
Ｈ＿ｋ（ｘ）＝ｙとなるような関数集合Ｈの元を一意に指定する関数指定データｋをランダムに選び、出力する装置であり、
前記関数集合Ｈが、
前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）とすると、
任意の相異なる前記秘密情報データ集合Ｓの元のｘ＿１及びｘ＿２と、任意の正整数をａとし、前記関数集合Ｈの任意の関数指定データｃに対し、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ａ＊ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δである分散情報生成装置。
【請求項１４】
前記チェック用データ生成装置は、
Ｎを正数、ｐを素数としたとき、秘密情報データ集合Ｓとして（Ｚ／ｐＺ）＾Ｎを用い、
前記秘密情報データ集合Ｓの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）に対し、
ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾（Ｎ＋１）＋ｅ＿１＾（Ｎ＋２）＋ｅ＿１＾（Ｎ＋４））＝０を満たすＺ／ｐＺの元ｅ＿０及びｅ＿１をランダムに選び、前記チェック用データとして出力する請求項１記載の分散情報生成装置。
【請求項１５】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造を用いる請求項１３または１４記載の分散情報生成装置。
【請求項１６】
線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化された秘密情報及び前記秘密情報に対応して生成されたチェック用データの分散符号化されたデータが格納される記憶装置と、
前記アクセス構造のアクセスセットに対応する前記記憶装置から分散符号化された秘密情報を読み出し、前記アクセス構造データにしたがって前記秘密情報を復元する秘密情報復元装置と、
前記アクセス構造のアクセスセットに対応する前記記憶装置から分散符号化されたチェック用データを読み出し、前記アクセス構造データにしたがって前記チェック用データを復元するチェック用データ復元装置と、
前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応している場合は復元した秘密情報を出力し、対応していない場合は不正を示す信号を出力する不正検知装置と、
を有し、
前記不正検知装置は、
前記秘密情報として入力される入力集合Ｓの任意の相異なる元をｘ＿１及びｘ＿２とし、任意の正整数をａとし、関数集合Ｈの元を一意に指定するデータである任意の関数指定データをｃとし、前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）としたとき、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ａ＊ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるようなＨにおいて、
復元したチェック用データである前記関数指定データｋと復元した秘密情報ｘとがＨ＿ｋ（ｘ）＝ｙを満たすとき、前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応していると判定する復元装置。
【請求項１７】
前記不正検知装置は、
Ｎを整数、ｐを素数としたとき、
復元したチェック用データであり、Ｚ／ｐＺの元である前記関数指定データｅ＿０，ｅ＿１と、復元した秘密情報であり、（Ｚ／ｐＺ）＾Ｎの元である（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）とが、ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾（Ｎ＋１）＋ｅ＿１＾（Ｎ＋２）＋ｅ＿１＾（Ｎ＋４））＝０を満たすとき、前記チェック用データ復元装置で復元されたチェック用データが前記秘密情報復元装置で復元された秘密情報に対応していると判定する請求項３記載の復元装置。
【請求項１８】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造を用いる請求項１６または１７記載の復元装置。
【請求項１９】
請求項１３記載の分散情報生成装置と、
請求項１６記載の復元装置と、
を有する秘密情報分散システム。
【請求項２０】
請求項１４記載の分散情報生成装置と、
請求項１７記載の復元装置と、
を有する秘密情報分散システム。
【請求項２１】
請求項１５記載の分散情報生成装置と、
請求項１８記載の復元装置と、
を有する秘密情報分散システム。
【請求項２２】
コンピュータが、
秘密情報に対応するチェック用データを生成し、
前記秘密情報を線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化して記憶装置に格納し、
前記秘密情報を分散符号化したアクセス構造と同一のアクセス構造を示すアクセス構造データにしたがって前記チェック用データを分散符号化して記憶装置に格納するためのプログラムであり、
秘密情報データ集合Ｓの元ｓを入力とし、
Ｈ＿ｋ（ｘ）＝ｙとなるような関数集合Ｈの元を一意に指定する関数指定データｋをランダムに選び、前記チェック用データとして出力させる、
関数集合Ｈが、
前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）とすると、
任意の相異なる前記秘密情報データ集合Ｓの元のｘ＿１及びｘ＿２と、任意の正整数ａと、前記関数集合Ｈの任意の関数指定データｃに対し、
｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ａ＊ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるプログラム。
【請求項２３】
Ｎを正数、ｐを素数としたとき、秘密情報データ集合Ｓとして（Ｚ／ｐＺ）＾Ｎを用い、
Ｓの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）に対し、
ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾｛Ｎ＋１｝＋ｅ＿１＾｛Ｎ＋２｝＋ｅ＿１＾｛Ｎ＋４｝）＝０を満たすＺ／ｐＺの元ｅ＿０及びｅ＿１をランダムに選び、前記チェック用データとして出力する出力するための請求項７記載のプログラム。
【請求項２４】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造を用いる請求項２２または２３記載のプログラム。
【請求項２５】
コンピュータが、
線形秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化された秘密情報が格納された記憶装置から前記アクセス構造のアクセスセットに対応する分散符号化された秘密情報を読み出し、前記アクセス構造データにしたがって前記秘密情報を復元し、
前記秘密情報に対応して生成されたチェック用データの分散符号化されたデータが格納された記憶装置から前記アクセス構造のアクセスセットに対応する分散符号化されたチェック用データを読み出し、前記アクセス構造データにしたがって前記チェック用データを復元し、
前記復元されたチェック用データが前記復元された秘密情報に対応している場合は復元した秘密情報を出力し、対応していない場合は不正を示す信号を出力するためのプログラムであり、
前記秘密情報として入力される入力集合Ｓの任意の異なる元をｘ＿１及びｘ＿２とし、任意の正整数をａとし、関数集合Ｈの元を一意に指定するデータである任意の関数指定データをｃとし、前記関数指定データの集合をＫとし、不正の検出確率を（１−δ）としたとき、｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ａ＊ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δであるようなＨにおいて、
復元したチェック用データである前記関数指定データｋと復元した秘密情報ｘとがＨ＿ｋ（ｘ）＝ｙを満たすとき、前記復元されたチェック用データが前記復元された秘密情報に対応していると判定するプログラム。
【請求項２６】
Ｎを正数、ｐを素数としたとき、
復元したチェック用データであり、Ｚ／ｐＺの元である前記関数指定データｅ＿０，ｅ＿１と、復元した秘密情報であり、（Ｚ／ｐＺ）＾Ｎの元である（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）とが、ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾｛Ｎ＋１｝＋ｅ＿１＾｛Ｎ＋２｝＋ｅ＿１＾｛Ｎ＋４｝）＝０を満たすとき、前記復元されたチェック用データが前記復元された秘密情報に対応していると判定する請求項９記載のプログラム。
【請求項２７】
前記秘密分散法のアクセス構造として、（ｋ，ｎ）しきい法のアクセス構造を用いる請求項２５または２６記載のプログラム。
【請求項２８】
請求項２２に記載のプログラムと、
請求項２５に記載のプログラムと、
を有するプログラム。
【請求項２９】
請求項２３に記載のプログラムと、
請求項２６に記載のプログラムと、
を有するプログラム。
【請求項３０】
請求項２４に記載のプログラムと、
請求項２７に記載のプログラムと、
を有するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、２００６年６月３０日に出願された特願２００６−１８１４３３号、２００６年９月０５日に出願された特願２００６−２４０２３６号及び２００７年２月０５日に出願された特願２００７−０２５４８２号を基礎とする優先権を主張し、その開示の全てをここに取り込む。【０００２】
本発明は秘密情報を分散して安全に保管するための分散情報生成装置及び保管された秘密情報を復元する復元装置に関する。
【背景技術】
【０００３】
秘密情報(例えば暗号化に用いる秘密鍵)を保管する場合、紛失や破壊の脅威と盗難の脅威とがある。前者の脅威に対しては秘密情報のコピーを作成すれば有効であるが、コピーを作成することで後者の盗難に対する脅威が増してしまう。このような問題を解決するための情報セキュリティ技術の一つとして秘密分散法がある。【０００４】
秘密分散法の一つである（ｋ，ｎ）しきい値法は、保護対象である秘密情報をｎ個の情報に分散符号化し、そのうちの任意のｋ個以上の分散情報を集めれば秘密情報を復元できるが、ｋ−１個までの分散情報では秘密に関する情報を全く得られないという特徴を持つ。したがって、ｋ−１個までの分散情報が盗難にあっても秘密情報は漏れず、ｎ−ｋ個までの分散情報が破壊されても秘密情報を復元できる。この（ｋ，ｎ）しきい値法については、例えば非特許文献１（Adi  Shamir,  "How  to  share  a  secret",  Comm.  ACM,  22(11),  612-613(1979)）に詳細に記載されている。【０００５】
以下、通常の（ｋ，ｎ）しきい値法にしたがって分散情報の作成や配付が正しく行われている状況において、秘密情報を復元する際の問題点について考える。【０００６】
秘密情報を復元する場合、分散情報を保持する他のものから分散情報を集める必要がある。このとき、分散情報の被要求側が配付された値を改竄することなく復元者へ渡すとは限らない。なお、ここで言う「改竄」とは、意図的なものだけでなく、装置故障や単なるミス等の意図しない変更も含むものとする。【０００７】
改竄された分散情報を用いて秘密情報を復元すると、その値は秘密情報と異なる値になってしまうことがある。そのため、秘密分散法には復元に用いる分散情報に改竄された値が存在することを高い確率で検知できる手法が望まれる。また、運用形態によって分散情報が選択される手段は様々であり、分散情報がどのような確率分布にしたがって選択されても改竄された値の検知率が高いことが望まれる。【０００８】
これらの問題を解決するための一つの技術として非特許文献２（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.）には、分散情報が一様な確率分布にしたがって選択されることを条件に不正を（１−ε）の確率で検知できる（ｋ，ｎ）しきい値法について記載されている。非特許文献３に記載された方法では、秘密情報を要素数ｓの集合とするとき、分散情報は要素数（１＋（ｓ−１）／ε）の集合になる。【００１１】
しかしながら上記したような従来の秘密分散法では、分散情報が秘密情報に比べて大きなデータになってしまう問題がある。
【発明の開示】
【００１２】
そこで、本発明は、秘密情報がどのような確率分布に従って選ばれても不正の検知が可能であり、従来の技術に比べて分散情報のデータサイズが小さい分散情報生成装置及び復元装置を提供することを目的とする。
【００１３】
上記目的を達成するため本発明では、分散する秘密情報に対応するチェック用データを生成し、秘密情報とチェック用データとをそれぞれを分散符号化する。秘密情報を復元する場合、秘密情報及びチェック用データをそれぞれ復元し、復元したチェック用データが復元した秘密情報に対応したデータであるか否かを判定する。対応している場合は復元した秘密情報が正しいと判断してそれを出力し、対応していない場合は不正（改竄された分散情報がある）と判断して不正を検出したことを示す記号を出力する。
【００１４】
このように復元されたチェック用データが復元された秘密情報に対応しているか否かを判定すれば、不正の検知が可能であり、チェック用データとして要素数の少ないデータ集合を用いることで従来の秘密分散方法に比べて秘密情報に対する分散情報のデータサイズを小さくできる。
【００１５】
また、チェック用データを一様にランダムに選ぶことができるため、秘密情報がどのような確率分布にしたがって選ばれても、高い不正の検知率が保証される。
【図面の簡単な説明】
【００１６】
【図１】図１は本発明の分散情報生成装置の一構成例を示すブロック図である。
【図２】図２は本発明の復元装置の一構成例を示すブロック図である。
【図３】図３は分散情報生成装置及び復元装置をコンピュータで実現する例を示すブロック図である。
【図４】図４は本発明の分散情報生成装置の動作を示すフローチャートである。
【図５】図５は本発明の復元装置の動作を示すフローチャートである。
【発明を実施するための最良の形態】
【００１７】
次に本発明について図面を用いて説明する。【００１８】
最初に本明細書で使用する用語について簡単に説明する。【００１９】
アクセス構造：秘密分散法における秘密情報が復元可能な条件を指す。本明細書ではアクセス構造を示すデータをアクセス構造データと称す。【００２０】
アクセスセット：秘密分散法における秘密情報が復元可能な分散情報の集合を指す。【００２１】
線形秘密分散法：秘密情報をＳとし、ｋ−１個の独立な乱数をＲ＿１，Ｒ＿２，…，Ｒ＿｛ｋ−１｝とし、ベクトル（Ｓ，Ｒ＿１，Ｒ＿２，…，Ｒ＿｛ｋ−１｝)をＵで表すとき、分散情報Ｗ＝（Ｗ＿１，Ｗ＿２，…，Ｗ＿ｎ）をｋ＊ｎ行列Ｇを用いてＷ＝Ｕ＊Ｇの計算式で生成できる秘密分散法を指す。本明細書ではアクセス構造として線形秘密分散法を例にして説明する。【００２２】
関数指定データ：関数集合Ｈの元（要素）を一意に指定するデータを指す。本明細書では、関数集合Ｈの元であり、関数指定データｋによって一意に指定される関数をＨ＿ｋと記す。【００２３】
秘密情報データ集合Ｓ：保管対象となる秘密情報ｓの集合を指す。【００２４】
分散秘密情報データ集合ＢＳ：秘密情報ｓを分散符号化したデータ（分散情報）の集合を指す。【００２５】
分散チェック用データ集合ＢＣ：秘密情報ｓに対応して生成したチェック用データの集合を指す。【００２６】
本発明の秘密情報分散システムは、秘密情報を保管する場合、秘密情報に対応するチェック用データを生成し、秘密情報及びチェック用データをそれぞれ秘密分散法のアクセス構造を示すアクセス構造データにしたがって分散符号化し、それらを記憶装置に格納する。【００２７】
また、秘密情報を復元する場合、アクセス構造のアクセスセットに対応する複数の記憶装置から分散符号化された秘密情報及び分散符号化されたチェック用データを読み出し、秘密情報及びチェック用データを復元する。そして、復元後のチェック用データが秘密情報に対応したものであるかを判定し、対応している場合は復元した秘密情報が正しいと判断し、対応していない場合は不正（改竄されている）と判断する。【００２８】
本発明の秘密情報分散システムは、分散情報生成装置１０２、復元装置２００及び複数の記憶装置３０１＿１〜３０１＿ｎを有する構成である。記憶装置３０１＿１〜３０１＿ｎは、分散秘密情報データ集合ＢＳの元が格納される分散秘密情報記憶装置３０２＿１〜３０２＿ｎ及び分散チェック用データ集合ＢＣの元が格納される分散チェック用データ記憶装置３０３＿１〜３０３＿ｎを備えている。【００２９】
まず、分散情報生成装置１０２の構成について図１を用いて説明する。【００３０】
図１は分散情報生成装置１０２の一構成例を示すブロック図である。【００３１】
図１に示すように、分散情報生成装置１０２は、チェック用データ生成装置１０４、秘密情報分散装置１０３及びチェック用データ分散装置１０５を備えている。【００３２】
分散情報生成装置１０２には秘密情報データ集合Ｓの元（要素）である秘密情報ｓ及び線形秘密分散法によるアクセス構造を示すアクセス構造データが入力される。分散情報生成装置１０２は、アクセス構造データで指定される記憶装置３０１の分散秘密情報記憶装置３０２に分散秘密情報データ集合ＢＳの元である分散情報を格納する。また、アクセス構造データで指定される記憶装置３０１の分散チェック用データ記憶装置３０３に分散チェック用データ集合ＢＣの元であるチェック用データを格納する。【００３３】
チェック用データ生成装置１０４には秘密情報データ集合Ｓの元ｓが入力される。チェック用データ生成装置１０４は、秘密情報データ集合Ｓを入力集合とし、出力集合をＢとする関数集合をＨとしたとき、出力集合Ｂの任意の元ｙと入力集合Ｓの任意の元ｘとがＨ＿ａ（ｘ）＝ｙとなる関数指定データａを効率的にかつランダムに選択することが可能である。【００３４】
本実施形態では、入力集合Ｓの任意の異なる元をｘ＿１及びｘ＿２とし、任意の関数指定データをｃ、該ｃを含む関数指定データｋの集合をＫとし、不正の検出確率を（１−δ）とし、｜｛ｂ｜ｂ｝∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ，Ｈ＿｛ｂ＋ｃ｝（ｘ＿２）＝ｙ｝｜／｜｛ｂ｜ｂ∈Ｋ，Ｈ＿ｂ（ｘ＿１）＝ｙ｝｜≦δである関数集合をＨとしたとき、Ｈ＿ｋ（ｘ）＝ｙとなる関数指定データｋをランダムに選択し、その選択した関数指定データｋをｘ＿１及びｘ＿２に対応するチェック用データとして出力する。【００３５】
秘密情報分散装置１０３には秘密情報データ集合Ｓの元ｓ及びアクセス構造データが入力される。秘密情報分散装置１０３は、アクセス構造データで指定される記憶装置３０１の分散秘密情報記憶装置３０２に分散秘密情報データ集合ＢＳの元を格納する。【００３６】
チェック用データ分散装置１０５には入力集合Ｋの元及びアクセス構造データが入力される。チェック用データ分散装置１０５はアクセス構造データで指定される記憶装置３０１の分散チェック用データ記憶装置３０３に分散チェック用データ集合ＢＣの元を格納する。【００３７】
次に復元装置２００の構成について図２を用いて説明する。【００３８】
図２は復元装置２００の一構成例を示すブロック図である。【００３９】
図２に示すように、復元装置２００は、秘密情報復元装置２０１、チェック用データ復元装置２０２及び不正検出装置２０３を備えている。【００４０】
復元装置２００には線形秘密分散法によるアクセス構造を示すアクセス構造データが入力される。復元装置２００は、記憶装置３０１＿１〜３０１＿ｎが備える分散秘密情報記憶装置３０２＿１〜３０２＿ｎから分散秘密情報データ集合ＢＳの元を読み出して復元し、分散チェック用データ記憶装置３０３＿１〜３０３＿ｎから分散チェック用データ集合ＢＣの元を読み出して復元し、復元した秘密情報データ集合Ｓの元、または不正なシェア（分散情報）を検出したことを示す記号を出力する。【００４１】
秘密情報復元装置２０１にはアクセス構造データが入力される。秘密情報復元装置２０１は、記憶装置３０１が備える分散秘密情報記憶装置３０２から分散秘密情報データ集合ＢＳの元を読み出し、復元した秘密情報データ集合Ｓの元を出力する。【００４２】
チェック用データ復元装置２０２にはアクセス構造データが入力される。チェック用データ復元装置２０２は、記憶装置３０１が備える分散チェック用データ記憶装置３０３から分散チェック用データ集合ＢＣの元を読み出し、復元した関数指定データ集合Ｋの元を出力する。【００４３】
不正検出装置２０３は、秘密情報復元装置２０１で復元された秘密情報データ集合Ｓの元及びチェック用データ復元装置２０２で復元された関数指定データ集合Ｋの元を入力とし、Ｈ＿ｋ（ｓ）＝ｙを満たしているときは復元した秘密情報データ集合Ｓの元を出力し、満たしていないときは不正なシェアを検出したことを示す記号を出力する。【００４４】
図１及び図２に示した分散情報生成装置１０２及び復元装置２００は、例えば論理回路等から構成されるＬＳＩ（Large  Scale  Integration）やＤＳＰ（Digital  Signal  Processor）等の半導体集積回路によって実現される。【００４５】
また、分散情報生成装置１０２及び復元装置２００は、図３に示すように、プログラムにしたがって所定の処理を実行する処理装置１０と、処理装置１０に対してコマンドや情報等を入力するための入力装置２０と、処理装置１０の処理結果をモニタするための出力装置３０とを備えたコンピュータによって実現してもよい。【００４６】
図３に示す処理装置１０は、ＣＰＵ１１と、ＣＰＵ１１の処理に必要な情報を一時的に記憶する主記憶装置１２と、ＣＰＵ１１に後述する分散情報生成装置１０２または復元装置２００としての処理を実行させるためのプログラムが記録された記録媒体１３と、秘密情報やアクセス構造データが格納されるデータ蓄積装置１４と、主記憶装置１２、記録媒体１３及びデータ蓄積装置１４とのデータ転送を制御するメモリ制御インタフェース部１５と、入力装置２０及び出力装置３０とのインタフェース装置であるＩ／Ｏインタフェース部１６とを有し、それらがバス１８を介して接続された構成である。なお、データ蓄積装置１４は、処理装置１０内にある必要はなく、処理装置１０から独立して備えていてもよい。また、データ蓄積装置１４は、無難秘密情報記憶装置３０２及び分散チェック用データ記憶装置３０３を備える記憶装置３０１として用いてもよい。【００４７】
処理装置１０は、記録媒体１３に記録されたプログラムにしたがって後述する分散情報生成装置１０２または復元装置２００としての機能を実現する。記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。【００４８】
次に本発明の秘密情報分散システムの動作について図４及び図５を用いて説明する。【００４９】
図４は分散情報生成装置の動作を示すフローチャートであり、図５は復元装置２００の動作を示すフローチャートである。【００５０】
図４に示すように、分散情報生成装置１０２には、例えば線形秘密分散法のアクセス構造を示すデータであるアクセス構造データ及び秘密情報データ集合Ｓの元である秘密情報ｓが入力される(ステップＡ１)。【００５１】
分散情報生成装置１０２は、秘密情報分散装置１０３にアクセス構造データ及び秘密情報ｓが入力されると、秘密情報ｓをアクセス構造データに対応したアクセス構造に分散符号化し、記憶装置３０１の分散秘密情報記憶装置３０２に格納する（ステップＡ２）。【００５２】
また、分散情報生成装置１０２は、チェック用データ生成装置１０４により、秘密情報ｓを基に、上記Ｈ＿ｋ（ｓ）＝ｙとなる関数指定データｋをランダムに生成する（ステップＡ３）。【００５３】
分散情報生成装置１０２は、チェック用データ分散装置１０４により、アクセス構造データ及び関数指定データｋを基に、関数指定データｋをアクセス構造データに対応したアクセス構造に分散符号化し、記憶装置３０１の分散チェック用データ記憶装置３０３に格納する（ステップＡ４）。【００５４】
図５に示すように、復元装置２００には線形秘密分散法のアクセス構造を示すアクセス構造データが入力される（ステップＢ１）。復元装置２００は、アクセス構造データが示すアクセスセットに対応する記憶装置３０１に格納されたデータを読み出す（ステップＢ２)。【００５５】
復元装置２００は、記憶装置３０１の分散秘密情報記憶装置３０２から読み出したデータとアクセス構造データとを基に、秘密情報復元装置２０１により秘密情報分散装置１０３で用いた分散符号化方法に対応する復元方法を用いて秘密情報データ集合Ｓの元ｓ’を復元する（ステップＢ３）。【００５６】
また、復元装置２００は、記憶装置３０１の分散チェック用データ記憶装置３０３から読み出したデータとアクセス構造データとを基に、チェック用データ復元装置２０２によりチェック用データ分散装置１０５で用いた分散符号化方法に対応する復元方法を用いて関数指定データ集合Ｋの元ｋ’を復元する（ステップＢ４）。【００５７】
次に、復元装置２００は、秘密情報復元装置２０１で復元された秘密情報データ集合Ｓの元ｓ’とチェック用データ復元装置２０２で復元された関数指定データ集合Ｋの元ｋ'とを用いて、不正検知装置２０３によりＨ＿ｋ’（ｓ’）＝ｙが成立するか否かをチェックし、ｓ’がｋ’に対応するデータであるか否かを判定する（ステップＢ５）。ｓ’がｋ’に対応するデータである場合はｓ’を出力し（ステップＢ６）、ｓ’がｋ’に対応するデータでない場合は不正検出を示す記号を出力する（ステップＢ７）。【００５８】
本発明によれば、復元されたチェック用データが復元された秘密情報に対応しているか否かを判定することで、不正の検知が可能であり、チェック用データとして要素数の少ないデータ集合を用いれば分散情報のデータサイズを小さくできる。また、チェック用データを一様にランダムに選ぶことができるため、秘密情報がどのような分布にしたがって選ばれても高い不正の検知率が保証できる。そのため、秘密情報がどのような分布にしたがって選ばれても不正を検知可能であり、かつ従来の秘密分散方法に比べて秘密情報に対する分散情報のデータサイズが小さくなる。【００５９】
(第１実施例)
第１実施例の秘密情報分散システムは、秘密情報のデータ集合にＺ／ｐＺを用い、関数指定データをＺ／ｐＺの元の組ｅ＿０，ｅ＿１とし、入力集合をＺ／ｐＺの元ｘとしたとき、関数集合ＨとしてＨ＿｛ｅ＿０，ｅ＿１｝（ｘ）＝ｅ＿０−ｘ＊ｅ＿１を用い、線形秘密分散法のアクセス構造データとして（ｋ，ｎ）しきい値法のアクセス構造を示すデータを用いる例である。なお、Ｚ／ｐＺは素数ｐに対する有限体であり、有限体上の加算を＋、減算を−、乗算を＊、除算を／で表す。【００６０】
第１実施例のチェック用データ生成装置１０４では、Ｚ／ｐＺの任意の元ｘに対して、Ｈ＿｛ａ＿１，ａ＿２｝（ｘ）＝０となる関数指定データａ＿１、ａ＿２をチェック用データとしてランダムに選択できる。【００６１】
ここで、Ｚ／ｐＺの任意の異なる元ｘ＿１、ｘ＿２と、任意の関数指定データｃ＿１、ｃ＿２に対し、Ｈの関数指定データ集合をＫとすると、｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０，Ｈ＿｛（ｂ＿１＋ｃ＿１），（ｂ＿２＋ｃ＿２）｝（ｘ＿２）＝０｝｜／｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０｝｜＝１／ｐである。【００６２】
（ｋ，ｎ）しきい値法のアクセス構造を示すデータは、具体的には正の整数であるｋ，ｎと、Ｚ／ｐＺの元の集合である｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝とによって構成される。但し、ｋ、ｎ、ｐは、ｋ≦ｎ≦ｐ−１を満たすものとする。【００６３】
なお、秘密情報分散装置１０３及びチェック用データ分散装置１０４は、非特許文献１に記載された（ｋ，ｎ）しきい値法を用いて秘密情報及びチェック用データを分散符号化し、秘密情報復元装置２０１及びチェック用データ復元装置２０２は、その（ｋ，ｎ）しきい値法に対応する復元方法を用いて秘密情報及びチェック用データを復元するものとする。【００６４】
次に第１実施例の分散情報生成装置１０２及び復元装置２００について説明する。【００６５】
第１実施例の分散情報生成装置１０２には、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝、及び秘密情報ｓが入力される。【００６６】
分散情報生成装置１０２は、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及び秘密情報ｓが入力されると、秘密情報分散装置１０３によりＺ／ｐＺ上の定数項がｓであるｋ−１次多項式をランダムに生成する。このｋ−１次多項式をｆ＿ｓ（ｘ）と記す。【００６７】
秘密情報分散装置１０３は、ｆ＿ｓ（ｉ＿１），ｆ＿ｓ（ｉ＿２），・・・，ｆ＿ｓ（ｉ＿ｎ）を計算し、その計算結果を記憶装置３０１＿｛ｉ＿１｝の分散秘密情報記憶装置３０２＿｛ｉ＿１｝、記憶装置３０１＿｛ｉ＿２｝の分散秘密情報記憶装置３０２＿｛ｉ＿２｝，・・・，記憶装置３０１＿｛ｉ＿ｎ｝の分散秘密情報記憶装置３０２＿｛ｉ＿ｎ｝に格納する。【００６８】
チェック用データ生成装置１０４は、秘密情報ｓを基にｅ＿０−ｓ＊ｅ＿１＝０を満たすｅ＿０及びｅ＿１をランダムに生成する。【００６９】
チェック用データ分散装置１０４は、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及びｅ＿０，ｅ＿１を基に、Ｚ／ｐＺ上の定数項がｅ＿０であるｋ−１次多項式と、Ｚ／ｐＺ上の定数項がｅ＿１であるｋ−１次多項式とをランダムに生成する。これらをf＿{ｅ＿０}（ｘ）、ｆ＿｛ｅ＿１｝（ｘ）と記す。【００７０】
チェック用データ分散装置１０４は、ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿０｝（ｉ＿２），・・・，ｆ＿｛ｅ＿０｝（ｉ＿ｎ）、及びｆ＿｛ｅ＿１｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿２），・・・，ｆ＿｛ｅ＿１｝（ｉ＿ｎ）を計算し、記憶装置３０１＿｛ｉ＿１｝の分散チェック用データ記憶装置３０３＿｛ｉ＿１｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、記憶装置３０１＿｛ｉ＿２｝の分散チェック用データ記憶装置３０３＿｛ｉ＿２｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、・・・、記憶装置３０１＿｛ｉ＿ｎ｝の分散チェック用データ記憶装置３０３＿｛ｉ＿ｎ｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納する。【００７１】
一方、第１実施例の復元装置２００にはアクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝が入力される。【００７２】
復元装置２００は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の各分散秘密情報記憶装置３０２からデータを読み出す。これらのデータをｂｓ＿｛ｊ＿１｝，ｂｓ＿｛ｊ＿２｝，・・・，ｂｓ＿｛ｊ＿ｋ｝と記す。【００７３】
秘密情報復元装置２０１は、（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｓ（ｘ）のｇ＿ｓ（０）を生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｓ（０）を計算する。【００７４】
また、復元装置２００は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の各分散チェック用データ記憶装置３０３からデータを読み出す。これらのデータを（ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）と記す。【００７５】
チェック用データ復元装置２０２は、（ｊ＿１，ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｅ０＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ０（ｘ）のｇ＿ｅ０（０）と、座標（ｊ＿１，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ１＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ１（ｘ）のｇ＿ｅ１（０）とを生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｅ０（０）及びｇ＿ｅ１（０）を計算する。【００７６】
不正検知装置２０３は、ｇ＿ｅ０（ｘ）、ｇ＿ｓ（０）、ｇ＿ｅ１（０）を入力とし、ｇ＿ｅ０（ｘ）、ｇ＿ｓ（０）、ｇ＿ｅ１（０）が、ｇ＿ｅ０（ｘ）＋ｇ＿ｓ（０）＊ｇ＿ｅ１（０）＝０を満たしているか否かを判定する。満たしている場合はｇ＿ｓ（０）を出力し、満たしていない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【００７７】
第１実施例の秘密情報分散システムでは、秘密情報のサイズはｐであり、分散情報のサイズはｐ＾３であり、不正の検出率は（１−１／ｐ）である。【００７８】
ここで、秘密情報のサイズをｓ、不正の検出率を（１−ε）と記すと、分散情報のサイズはｓ＊（１／ε）＾２で表せる。【００７９】
上述した非特許文献２に記載された秘密分散法の分散情報のサイズは（（ｓ−１）（ｋ−１）／ε＋ｋ）＾２である。例えば、ｋ＝２、ｐ＝２＾８０、ε＝１／２＾８０とすると、第１実施例の分散情報のサイズは約２＾２４０であり、非特許文献２に記載された方法では、分散情報のサイズが約２＾３２０となる。【００８０】
したがって、第１実施例の秘密情報分散システムは、不正を検出することが可能であり、かつ従来の方法に比べて分散情報のサイズが小さいことがわかる。【００８１】
（第２実施例）
第２実施例は、秘密情報のデータ集合に（Ｚ／ｐＺ）＾Ｎを用い、関数指定データをＺ／ｐＺの元の組ｅ＿０，ｅ＿１とし、入力集合を（Ｚ／ｐＺ）＾Ｎの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）としたとき、関数集合ＨとしてＨ＿｛ｅ＿０，ｅ＿１｝（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）＝ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｘ＿Ｎ＊ｅ＿１＾｛Ｎ＋１｝）を用い、線形秘密分散法のアクセス構造データとして（ｋ，ｎ）しきい値法のアクセス構造を示すデータを用いる例である。なお、（Ｚ／ｐＺ）＾Ｎは素数ｐに対する有限体のＮ（Ｎは正の整数）次拡大体であり、拡大体上の加算を＋、減算を−、乗算を＊、除算を／で表す。【００８２】
第２実施例のチェック用データ生成装置１０４では、任意の（Ｚ／ｐＺ）＾Ｎの元ｘに対してＨ＿｛ａ＿１，ａ＿２｝（ｘ）＝０となる関数指定データａ＿１、ａ＿２をチェック用データとしてランダムに選択できる。【００８３】
ここで、（Ｚ／ｐＺ）＾Ｎの任意の異なる元をｘ＿１，ｘ＿２とし、任意の関数指定データをｃ＿１、ｃ＿２とし、Ｈの関数指定データ集合をＫとすると、｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０，Ｈ＿｛（ｂ＿１＋ｃ＿１），（ｂ＿２＋ｃ＿２）｝（ｘ＿２）＝０｝｜／｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０｝｜＝（Ｎ＋１）／ｐとなる。【００８４】
（ｋ，ｎ）しきい値法のアクセス構造を表すデータは、具体的には正の整数であるｋ、ｎと、Ｚ／ｐＺの元の集合である｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝とによって構成される。但し、ｋ、ｎ、ｐは、ｋ≦ｎ≦ｐ−１を満たすものとする。【００８５】
なお、秘密情報分散装置１０３及びチェック用データ分散装置１０４は、非特許文献１に記載された（ｋ，ｎ）しきい値法を用いて秘密情報及びチェック用データを分散符号化し、秘密情報復元装置２０１及びチェック用データ復元装置２０２は、その（ｋ，ｎ）しきい値法に対応する復元方法を用いて秘密情報及びチェック用データを復元するものとする。【００８６】
次に第２実施例の分散情報生成装置１０２及び復元装置２００について説明する。【００８７】
第２実施例の分散情報生成装置１０２には、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝、及び秘密情報ｓ＝（ｓ＿１，ｓ＿２，・・・，ｓ＿Ｎ）が入力される。【００８８】
分散情報生成装置１０２は、秘密情報分散装置１０３により、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及び秘密情報ｓを基に、ＧＦ（ｐ＾Ｎ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。これをｆ＿ｓ（ｘ）と記す。【００８９】
秘密情報分散装置１０３は、ｆ＿ｓ（ｉ＿１），ｆ＿ｓ（ｉ＿２），・・・，ｆ＿ｓ（ｉ＿ｎ）を計算し、その計算結果を記憶装置３０１＿｛ｉ＿１｝の分散秘密情報記憶装置３０３＿｛ｉ＿１｝、記憶装置３０１＿｛ｉ＿２｝の分散秘密情報記憶装置３０３＿｛ｉ＿２｝,・・・，記憶装置３０１＿｛ｉ＿ｎ｝の分散秘密情報記憶装置３０３＿｛ｉ＿ｎ｝に格納する。【００９０】
チェック用データ生成装置１０４は、秘密情報ｓ＝（ｓ＿１，ｓ＿２，・・・，ｓ＿Ｎ）を入力とし、ｅ＿０−（ｓ＿１＊ｅ＿１＋ｓ＿２＊ｅ＿１＾２＋，・・・，＋ｓ＿｛Ｎ−１｝＊ｅ＿１＾｛Ｎ−１｝＋ｓ＿Ｎ＊ｅ＿１＾｛Ｎ＋１｝）＝０を満たすｅ＿０，ｅ＿１をランダムに生成する。【００９１】
チェック用データ分散装置１０５は、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及びチェック用データ生成装置１０４で生成されたｅ＿０，ｅ＿１を入力とし、Ｚ／ｐＺ上の定数項がｅ＿０であるｋ−１次多項式と、Ｚ／ｐＺ上の定数項がｅ＿１であるｋ−１次多項式とをランダムに生成する。これらをｆ＿｛ｅ＿０｝（ｘ）、ｆ＿｛ｅ＿１｝（ｘ）と記す。【００９２】
チェック用データ分散装置１０５は、ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿０｝（ｉ＿２），・・・，ｆ＿｛ｅ＿０｝（ｉ＿ｎ）、及びｆ＿｛ｅ＿１｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿２），・・・，ｆ＿｛ｅ＿１｝（ｉ＿ｎ）を計算し、記憶装置３０１＿｛ｉ＿１｝の分散チェック用データ記憶装置３０２＿｛ｉ＿１｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、記憶装置３０１＿｛ｉ＿２｝の分散チェック用データ記憶装置３０２＿｛ｉ＿２｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、・・・，記憶装置３０１＿｛ｉ＿ｎ｝の分散チェック用データ記憶装置３０２＿｛ｉ＿ｎ｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納する。【００９３】
一方、第２実施例の復元装置２００にはアクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝が入力される。【００９４】
秘密情報復元装置２０１は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の各分散秘密情報記憶装置３０２からデータを読み出す。これらをｂｓ＿｛ｊ＿１｝，ｂｓ＿｛ｊ＿２｝，・・・，ｂｓ＿｛ｊ＿ｋ｝と記す。【００９５】
秘密情報復元装置２０１は、分散秘密情報記憶装置３０２から読み出した（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を通るＧＦ（ｐ＾Ｎ）上のｋ−１次多項式ｇ＿ｓ（ｘ）のｇ＿ｓ（０）を生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｓ（０）を計算する。ここでは、このｇ＿ｓ（０）を（Ｚ／ｐＺ）＾Ｎの元とみなし、（ｇｓ１，ｇｓ２，・・・，ｇｓＮ）と記す。【００９６】
チェック用データ復元装置２０２は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の分散チェック用データ記憶装置３０３からデータを読み出す。これらを（ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）と記す。【００９７】
チェック用データ復元装置２０２は、分散チェック用データ記憶装置３０３から読み出した（ｊ＿１，ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｅ０＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ０（ｘ）のｇ＿ｅ０（０）と、座標（ｊ＿１，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ１＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ１（ｘ）のｇ＿ｅ１（０）とを生成する。【００９８】
具体的には連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｅ０（ｘ）及びｇ＿ｅ１（ｘ）を計算する。【００９９】
次に、不正検知装置２０３は、ｇ＿ｓ（０）、ｇ＿ｅ０（０）、ｇ＿ｅ１（０）を入力とし、ｇ＿ｓ（０）、ｇ＿ｅ０（０）、ｇ＿ｅ１（０）が、ｇ＿ｅ０（０）−（ｇｓ１＊ｇ＿ｅ１（０）＋ｇｓ２＊ｇ＿ｅ１（０）＾２＋，・・・，＋ｇｓ｛Ｎ−１｝＊ｇ＿ｅ１（０）＾｛Ｎ−１｝＋ｇｓＮ＊ｇ＿ｅ１（０）＾｛Ｎ＋１｝）＝０を満たすか否かを判定する。満たしている場合はｇ＿ｓ（０）を出力し、満たしていない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【０１００】
第２実施例の秘密情報分散システムでは、秘密情報のサイズはp＾Ｎであり、分散情報のサイズはp＾（Ｎ＋２）であり、不正の検出率は（１−(Ｎ＋１)／ｐ）である。【０１０１】
ここで、秘密情報のサイズをｓ、不正の検出率を（１−ε）と記すと、分散情報のサイズはｓ＊（１／ε）＾２＊（１＋ｌｏｇ＿ｐｓ）＾２で表すことができる。【０１０２】
非特許文献２に記載された秘密分散法の分散情報のサイズは（（ｓ−１）（ｋ−１）／ε＋ｋ）＾２である。例えば、ｋ＝２、ｐ＝２＾９０、Ｎ＝１０００、ε＝１／２＾８０とすると、第２実施例の分散情報のサイズは約２＾９０１８０であり、非特許文献２に記載された秘密分散法の分散情報のサイズは約２＾１８０１６０である。【０１０３】
したがって、第２実施例の秘密情報分散システムでも不正を検出することが可能であり、かつ従来の方法に比べて分散情報のサイズが小さいことがわかる。【０１０４】
（第３実施例）
第３実施例は、秘密情報のデータ集合に（Ｚ／ｐＺ）＾Ｎを用い、関数指定データをＺ／ｐＺの元の組ｅ＿０，ｅ＿１とし、入力集合を（Ｚ／ｐＺ）＾Ｎの元（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）としたとき、関数集合ＨとしてＨ＿｛ｅ＿０，ｅ＿１｝（ｘ＿１，ｘ＿２，・・・，ｘ＿Ｎ）＝ｅ＿０−（ｘ＿１＊ｅ＿１＋ｘ＿２＊ｅ＿１＾２＋・・・＋ｘ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾（Ｎ＋１）＋ｅ＿１＾（Ｎ＋２）＋ｅ＿１＾（Ｎ＋４））を用い、線形秘密分散法のアクセス構造データとして（ｋ，ｎ）しきい値法のアクセス構造を示すデータを用いる例である。なお、第２実施例と同様（Ｚ／ｐＺ）＾Ｎは素数ｐに対する有限体のＮ（Ｎは正の整数）次拡大体であり、拡大体上の加算を＋、減算を−、乗算を＊、除算を／で表す。【０１０５】
第３実施例のチェック用データ生成装置１０４では、任意の（Ｚ／ｐＺ）＾Ｎの元ｘに対してＨ＿｛ａ＿１，ａ＿２｝（ｘ）＝０となる関数指定データａ＿１、ａ＿２をチェック用データとしてランダムに選択できる。【０１０６】
ここで、（Ｚ／ｐＺ）＾Ｎの任意の異なる元をｘ＿１，ｘ＿２とし、任意の正整数をａとし、任意の関数指定データをｃ＿１、ｃ＿２とし、Ｈの関数指定データ集合をＫとすると、｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０，Ｈ＿｛（ａ＊ｂ＿１＋ｃ＿１），（ａ＊ｂ＿２＋ｃ＿２）｝（ｘ＿２）＝０｝｜／｜｛ｂ＿１，ｂ＿２｜ｂ＿１，ｂ＿２∈Ｚ／ｐＺ，Ｈ＿｛ｂ＿１，ｂ＿２｝（ｘ＿１）＝０｝｜＝Ｎ／ｐである。【０１０７】
（ｋ，ｎ）しきい値法のアクセス構造を表すデータは、具体的には正の整数であるｋ、ｎと、Ｚ／ｐＺの元の集合である｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝とによって構成される。但し、ｋ、ｎ、ｐは、ｋ≦ｎ≦ｐ−１を満たすものとする。【０１０８】
なお、秘密情報分散装置１０３及びチェック用データ分散装置１０４は、非特許文献１に記載された（ｋ，ｎ）しきい値法を用いて秘密情報及びチェック用データを分散符号化し、秘密情報復元装置２０１及びチェック用データ復元装置２０２は、その（ｋ，ｎ）しきい値法に対応する復元方法を用いて秘密情報及びチェック用データを復元するものとする。【０１０９】
次に第３実施例の分散情報生成装置１０２及び復元装置２００について説明する。【０１１０】
第３実施例の分散情報生成装置１０２には、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，…，ｉ＿ｎ｝、及び秘密情報ｓ＝（ｓ＿１，ｓ＿２，・・・，ｓ＿Ｎ）が入力される。【０１１１】
分散情報生成装置１０２は、秘密情報分散装置１０３により、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及び秘密情報ｓを基に、ＧＦ（ｐ＾Ｎ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。これをｆ＿ｓ（ｘ）と記す。【０１１２】
秘密情報分散装置１０３は、ｆ＿ｓ（ｉ＿１），ｆ＿ｓ（ｉ＿２），・・・，ｆ＿ｓ（ｉ＿ｎ）を計算し、その計算結果を記憶装置３０１＿｛ｉ＿１｝の分散秘密情報記憶装置３０３＿｛ｉ＿１｝，記憶装置３０１＿｛ｉ＿２｝の分散秘密情報記憶装置３０３＿｛ｉ＿２｝，・・・，記憶装置３０１＿｛ｉ＿ｎ｝の分散秘密情報記憶装置３０３＿｛ｉ＿ｎ｝に格納する。【０１１３】
チェック用データ生成装置１０４は、秘密情報ｓ＝（ｓ＿１，ｓ＿２，・・・，ｓ＿Ｎ）を入力とし、ｅ＿０−(ｓ＿１＊ｅ＿１＋ｓ＿２＊ｅ＿１＾２＋・・・＋ｓ＿Ｎ＊ｅ＿１＾Ｎ＋ｅ＿１＾（Ｎ＋１）＋ｅ＿１^（Ｎ＋２）＋ｅ＿１＾（Ｎ＋４）)＝０を満たすＺ／ｐＺの元ｅ＿０，ｅ＿１をランダムに生成する。【０１１４】
チェック用データ分散装置１０５は、アクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝及びチェック用データ生成装置１０４で生成されたｅ＿０，ｅ＿１を入力とし、Ｚ／ｐＺ上の定数項がｅ＿０であるｋ−１次多項式と、Ｚ／ｐＺ上の定数項がｅ＿１であるｋ−１次多項式をランダムに生成する。これらをｆ＿｛ｅ＿０｝（ｘ）、ｆ＿｛ｅ＿１｝（ｘ）と記す。【０１１５】
チェック用データ分散装置１０５は、ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿０｝（ｉ＿２），・・・，ｆ＿｛ｅ＿０｝（ｉ＿ｎ）、及びｆ＿｛ｅ＿１｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿２），・・・，ｆ＿｛ｅ＿１｝（ｉ＿ｎ）を計算し、記憶装置３０１＿｛ｉ＿１｝の分散チェック用データ記憶装置３０２＿｛ｉ＿１｝に（ｆ＿{ｅ＿０}(ｉ＿１)，ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、記憶装置３０１＿｛ｉ＿２｝の分散チェック用データ記憶装置３０２＿｛ｉ＿２｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納し、・・・，記憶装置３０１＿｛ｉ＿ｎ｝の分散チェック用データ記憶装置３０２＿｛ｉ＿ｎ｝に（ｆ＿｛ｅ＿０｝（ｉ＿１），ｆ＿｛ｅ＿１｝（ｉ＿１））を格納する。【０１１６】
一方、第３実施例の復元装置２００にはアクセス構造データｋ，ｎ，｛ｉ＿１，ｉ＿２，・・・，ｉ＿ｎ｝が入力される。【０１１７】
秘密情報復元装置２０１は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の各分散秘密情報記憶装置３０２からデータを読み出す。これらをｂｓ＿｛ｊ＿１｝，ｂｓ＿｛ｊ＿２｝，・・・，ｂｓ＿｛ｊ＿ｋ｝と記す。【０１１８】
秘密情報復元装置２０１は、分散秘密情報記憶装置３０２から読み出した（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｓ＿｛ｊ＿１｝），（ｊ＿２，ｂｓ＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｓ＿｛ｊ＿ｋ｝）を通るＧＦ（ｐ＾Ｎ）上のｋ−１次多項式ｇ＿ｓ（ｘ）のｇ＿ｓ（０）を生成する。具体的には、連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｓ（０）を計算する。ここでは、このｇ＿ｓ（０）を（Ｚ／ｐＺ）＾Ｎの元とみなし、（ｇｓ１，ｇｓ２，・・・，ｇｓＮ）と記す。【０１１９】
チェック用データ復元装置２０２は、記憶装置３０１＿｛ｊ＿１｝，３０１＿｛ｊ＿２｝，・・・，３０１＿｛ｊ＿ｋ｝の分散チェック用データ記憶装置３０３からデータを読み出す。これらを（ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）と記す。【０１２０】
チェック用データ復元装置２０２は、分散チェック用データ記憶装置３０３から読み出した（ｊ＿１，ｂｅ０＿｛ｊ＿１｝，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝，ｂｅ１＿｛ｊ＿ｋ｝）を入力とし、座標（ｊ＿１，ｂｅ０＿｛ｊ＿１｝），（ｊ＿２，ｂｅ０＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ０＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ０（ｘ）のｇ＿ｅ０（０）と、座標（ｊ＿１，ｂｅ１＿｛ｊ＿１｝），（ｊ＿２，ｂｅ１＿｛ｊ＿２｝），・・・，（ｊ＿ｋ，ｂｅ１＿｛ｊ＿ｋ｝）を通るＺ／ｐＺ上のｋ−１次多項式ｇ＿ｅ１（ｘ）のｇ＿ｅ１（０）とを生成する。【０１２１】
具体的には連立方程式を解く方法やラグランジュ補間を用いる方法などによりｇ＿ｅ０（ｘ）及びｇ＿ｅ１（ｘ）を計算する。【０１２２】
次に、不正検知装置２０３は、ｇ＿ｓ（０）、ｇ＿ｅ０（０）、ｇ＿ｅ１（０）を入力とし、ｇ＿ｓ（０）、ｇ＿ｅ０（０）、ｇ＿ｅ１（０）が、ｇ＿ｅ０（０）−（ｇｓ１＊ｇ＿ｅ１（０）＋ｇｓ２＊ｇ＿ｅ１（０）＾２＋・・・＋ｇｓＮ＊ｇ＿ｅ１（０）^Ｎ＋ｇ＿ｅ１（０）＾（Ｎ＋１）＋ｇ＿ｅ１（０）＾(Ｎ＋２)＋ｇ＿ｅ１（０）＾(Ｎ＋４)）＝０を満たすか否かを判定する。満たしている場合はｇ＿ｓ（０）を出力し、満たしていない場合は不正を検知したことを示す記号として、例えば⊥を出力する。【０１２３】
第３実施例の秘密情報分散システムでは、秘密情報のサイズはｐ＾Ｎであり、分散情報のサイズはｐ＾(Ｎ＋２)であり、不正の検出率は（１−（Ｎ＋３）／ｐ）である。【０１２４】
第３実施例の秘密情報分散システムでは、第１実施例及び第２実施例では想定していない不正を検出することができる。具体的には、第１実施例及び第２実施例では、分散チェック記憶データ装置３０３に格納された情報（ｊ，ｂｅ０＿｛ｊ｝，ｂｅ１＿｛ｊ｝）のうち、ｂｅ０＿｛ｊ｝及びｂｅ１＿｛ｊ｝の改竄を検出可能であり、ｊの改竄は想定していなかった。ｊは記憶装置３０１＿ｊに対応するデータであり、記憶装置の識別子に相当するものであるため、ｊの改竄は記憶装置のなりすましに対応する不正と考えることができる。第３実施例は上記ｊの改竄も検出可能な特徴を有し、第３実施例によりなりすましに対しても不正の検出が可能なシステムを構築できる。
【図１】
0005136412.tif 000002
【図２】
0005136412.tif 000003
【図３】
0005136412.tif 000004
【図４】
0005136412.tif 000005
【図５】
0005136412.tif 000006