(57)【要約】  本発明は、不正者が閾値数個以上の分散情報を持っていても分散情報の改竄を高い確率で検知可能であって、秘密情報に対する分散情報のデータサイズが小さい分散情報生成装置、復元装置、復元結果検証装置、秘密情報分散システム、プログラムおよび方法を提供することを目的とする。分散情報生成装置は、秘密情報ｓを埋め込んだ多項式Ｆを生成して分散秘密情報を出力し、多項式Ｆに固定値ｔを入力したときの出力を秘密情報として埋め込んだ多項式Ｇを生成して分散分散秘密情報を生成する。復元装置は、ｋ組の分散秘密情報を入力して多項式Ｆ’を生成し、ｋ組の分散分散秘密情報を入力して多項式Ｇ’を生成する。また、多項式Ｇ’に秘密情報として埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、埋め込まれた値を出力し、等しくない場合に、不正検出を示す情報を出力する。
2008093690.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報を分散する分散情報生成装置であって、
秘密情報分散装置と、
分散秘密情報分散装置と、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力手段とを備え、
前記秘密情報分散装置は、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成装置と、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成装置と、  多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力装置とを含み、
前記分散秘密情報分散装置は、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成装置と、
前記分散情報出力装置の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成装置と、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力装置とを含む  ことを特徴とする分散情報生成装置。
【請求項２】
前記分散入力手段は、ｋ−１以下のパラメータＬを入力し、
前記第１分散多項式生成装置は、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記第２分散多項式生成装置は、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する
請求項１記載の分散情報生成装置。
【請求項３】
前記第１分散多項式生成装置は、秘密情報ｓを定数項とする多項式Ｆを生成する請求項２記載の分散情報生成装置。
【請求項４】
前記第１乱数生成装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、前記第２乱数生成装置は、第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項１から請求項３のうちのいずれか１項に記載の分散情報生成装置。
【請求項５】
前記第１乱数生成装置が出力した第１の乱数と、前記分散情報出力装置が出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成装置が出力した第２の乱数と、前記分散分散情報出力装置が出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えた請求項１から請求項４のうちのいずれか１項に記載の分散情報生成装置。
【請求項６】
秘密情報を分散する分散情報生成装置の出力に基づいて秘密情報を復元する復元装置であって、
請求項１記載の分散情報生成装置の出力を格納する記憶装置と、
閾値ｋおよび所定の固定値ｔを入力する復元入力手段と、
前記記憶装置から、請求項１記載の秘密情報分散装置が出力した第１の乱数と、第１の乱数を請求項１記載の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元装置と、
前記記憶装置から、請求項１記載の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を請求項１記載の分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元装置と、
多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置と
を備えたことを特徴とする復元装置。
【請求項７】
前記記憶装置は、請求項２記載の分散情報生成装置の出力を格納し、
前記復元入力手段は、ｋ−１以下のパラメータＬを入力し、
前記多項式復元装置は、前記記憶装置から、請求項２記載の秘密情報分散装置が出力した第１の乱数と、第１の乱数を請求項２記載の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、請求項２記載の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を請求項２記載の分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項６記載の復元装置。
【請求項８】
前記記憶装置は、請求項３記載の分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、請求項３記載の秘密情報分散装置が出力した第１の乱数と、第１の乱数を請求項３記載の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項７記載の復元装置。
【請求項９】
記憶装置は、請求項４記載の分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、請求項４記載の秘密情報分散装置が出力した第１の乱数と、第１の乱数を請求項４記載の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、請求項４記載の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を請求項４記載の分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記多項式復元装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力し、または、前記分散秘密情報復元装置は、第２の乱数として、互いに異なるｎ個の定数を入力する
請求項６から請求項８のうちのいずれか１項に記載の復元装置。
【請求項１０】
前記不正検出装置は、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項６から請求項９のうちのいずれか１項に記載の復元装置。
【請求項１１】
秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、
前記復元装置が出力した（ｋ−１）次多項式ｆを入力し、請求項１から請求項５のうちのいずれか１項に記載の分散情報生成装置の出力を格納する記憶装置から、請求項１から請求項５のうちのいずれか１項に記載の秘密情報分散装置が出力した第１の乱数ｒと、請求項１から請求項５のうちのいずれか１項に記載の秘密情報分散装置が生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証装置。
【請求項１２】
請求項１から請求項５のうちのいずれか１項に記載の分散情報生成装置と、
請求項６から請求項１０のうちのいずれか１項に記載の復元装置と
を備えたことを特徴とする秘密情報分散システム。
【請求項１３】
請求項１１記載の復元結果検証装置を備えた請求項１２記載の秘密情報分散システム。
【請求項１４】
秘密情報を分散する分散情報生成方法であって、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力ステップと、
秘密情報分散ステップと、
分散秘密情報分散ステップとを含み、
前記秘密情報分散ステップは、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成ステップと、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成ステップと、
多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力ステップとを有し、
前記分散秘密情報分散ステップは、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成ステップと、
前記分散情報出力ステップの出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成ステップと、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力ステップとを有する
ことを特徴とする分散情報生成方法。
【請求項１５】
前記分散入力ステップで、ｋ−１以下のパラメータＬを入力し、
前記第１分散多項式生成ステップで、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記第２分散多項式生成ステップで、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する
請求項１４記載の分散情報生成方法。
【請求項１６】
前記第１分散多項式生成ステップで、秘密情報ｓを定数項とする多項式Ｆを生成する請求項１５記載の分散情報生成方法。
【請求項１７】
前記第１乱数生成ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、前記第２乱数生成ステップで、第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項１４から請求項１６のうちのいずれか１項に記載の分散情報生成方法。
【請求項１８】
前記第１乱数生成ステップで出力した第１の乱数と、分散情報出力ステップで出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成ステップで出力した第２の乱数と、前記分散分散情報出力ステップで出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる請求項１４から請求項１７のうちのいずれか１項に記載の分散情報生成方法。
【請求項１９】
秘密情報を復元するための復元方法であって、
閾値ｋおよび所定の固定値ｔを入力する復元入力ステップと、
請求項１４記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１４記載の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を請求項１４記載の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元ステップと、
前記記憶装置から、請求項１４記載の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を請求項１４記載の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元ステップと、
多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出ステップと
を含むことを特徴とする復元方法。
【請求項２０】
前記復元入力ステップで、ｋ−１以下のパラメータＬを入力し、
前記多項式復元ステップで、請求項１５記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１５記載の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を請求項１５記載の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元ステップで、前記記憶装置から、請求項１５記載の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を請求項１５記載の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項１９記載の復元方法。
【請求項２１】
前記多項式復元ステップで、請求項１６記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１６記載の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を請求項１６記載の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項２０記載の復元方法。
【請求項２２】
前記多項式復元ステップで、請求項１７記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１７記載の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を請求項１７記載の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元ステップで、前記記憶装置から、請求項１７記載の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を請求項１７記載の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記多項式復元ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力し、または、分散秘密情報復元ステップで、第２の乱数として、互いに異なるｎ個の定数を入力する
請求項１９から請求項２１のうちのいずれか１項に記載の復元方法。
【請求項２３】
前記不正検出ステップで、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項１９から請求項２１のうちのいずれか１項に記載の復元方法。
【請求項２４】
復元された秘密情報を検証するための復元結果検証方法であって、
復元された秘密情報として（ｋ−１）次多項式ｆを入力し、請求項１４から請求項１８のうちのいずれか１項に記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１４から請求項１８のうちのいずれか１項に記載の秘密情報分散ステップで出力した第１の乱数ｒと、請求項１４から請求項１８のうちのいずれか１項に記載の秘密情報分散ステップで生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証方法。
【請求項２５】
請求項１４から請求項１８のうちのいずれか１項に記載の分散情報生成方法と、
請求項１９から請求項２３のうちのいずれか１項に記載の復元方法と
を含むことを特徴とする秘密情報分散方法。
【請求項２６】
請求項２４記載の復元結果検証方法を含む請求項２５記載の秘密情報分散方法。
【請求項２７】
秘密情報を分散するための分散情報生成プログラムであって、
コンピュータに、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力処理と、
秘密情報分散処理と、
分散秘密情報分散処理とを実行させ、
前記秘密情報分散処理で、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成処理と、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成処理と、
多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力処理とを実行させ、
前記分散秘密情報分散処理で、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成処理と、
前記分散情報出力処理の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成処理と、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力処理とを実行させる
ための分散情報生成プログラム。
【請求項２８】
コンピュータに、
前記分散入力処理で、ｋ−１以下のパラメータＬを入力する処理を実行させ、
前記第１分散多項式生成処理で、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成する処理を実行させ、
前記第２分散多項式生成処理で、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する処理を実行させる
請求項２７記載の分散情報生成プログラム。
【請求項２９】
コンピュータに、
前記第１分散多項式生成処理で、秘密情報ｓを定数項とする多項式Ｆを生成する処理を実行させる
請求項２８記載の分散情報生成プログラム。
【請求項３０】
コンピュータに、
前記第１乱数生成処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する処理を実行させ、または、前記第２乱数生成処理で、第２の乱数として、互いに異なるｎ個の定数を生成して出力する処理を実行させる
請求項２７から請求項２９のうちのいずれか１項に記載の分散情報生成プログラム。
【請求項３１】
コンピュータに、
前記第１乱数生成処理で出力した第１の乱数と、分散情報出力処理で出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成処理で出力した第２の乱数と、前記分散分散情報出力処理で出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる処理を実行させる
請求項２７から請求項３０のうちのいずれか１項に記載の分散情報生成プログラム。
【請求項３２】
秘密情報を復元するための復元プログラムであって、
コンピュータに、
閾値ｋおよび所定の固定値ｔを入力する復元入力処理と、
請求項２７記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項２７記載の秘密情報分散処理で出力した第１の乱数と、第１の乱数を請求項２７記載の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元処理と、
前記記憶装置から、請求項２７記載の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を請求項２７記載の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元処理と、
多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出処理と
を実行させるための復元プログラム。
【請求項３３】
コンピュータに、
前記復元入力処理で、ｋ−１以下のパラメータＬを入力し、
前記多項式復元処理で、請求項２８記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項２８記載の秘密情報分散処理で出力した第１の乱数と、第１の乱数を請求項２８記載の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、
前記分散秘密情報復元処理で、前記記憶装置から、請求項２８記載の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を請求項２８記載の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成する処理を実行させ、
前記不正検出処理で、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させる  請求項３２記載の復元プログラム。
【請求項３４】
コンピュータに、
前記多項式復元処理で、請求項２９記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項２９記載の秘密情報分散処理で出力した第１の乱数と、第１の乱数を請求項２９記載の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、
前記不正検出処理で、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させる
請求項３３記載の復元プログラム。
【請求項３５】
コンピュータに、
前記多項式復元処理で、請求項３０記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項３０記載の秘密情報分散処理で出力した第１の乱数と、第１の乱数を請求項３０記載の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、
前記分散秘密情報復元処理で、前記記憶装置から、請求項３０記載の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を請求項３０記載の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成する処理を実行させ、
前記多項式復元処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力する処理を実行させ、または、分散秘密情報復元処理で、第２の乱数として、互いに異なるｎ個の定数を入力する処理を実行させる
請求項３２から請求項３４のうちのいずれか１項に記載の復元プログラム。
【請求項３６】
コンピュータに、
前記不正検出処理で、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する処理を実行させる
請求項３２から請求項３５のうちのいずれか１項に記載の復元プログラム。
【請求項３７】
復元された秘密情報を検証するための復元結果検証プログラムであって、
コンピュータに、
復元された秘密情報として（ｋ−１）次多項式ｆを入力し、請求項２７から請求項３１のうちのいずれか１項に記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項２７から請求項３１のうちのいずれか１項に記載の秘密情報分散処理で出力した第１の乱数ｒと、請求項２７から請求項３１のうちのいずれか１項に記載の秘密情報分散処理で生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させるための復元結果検証プログラム。
【請求項３８】
請求項２７から請求項３１のうちのいずれか１項に記載の分散情報生成プログラムと、
請求項３２から請求項３６のうちのいずれか１項に記載の復元プログラムと
を含む秘密情報分散プログラム。
【請求項３９】
請求項２７から請求項３１のうちのいずれか１項に記載の分散情報生成プログラムと、
請求項３２から請求項３６のうちのいずれか１項に記載の復元プログラムと、
請求項３７記載の復元結果検証プログラムと
を含む秘密情報分散プログラム。
【請求項４０】
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力し、前記固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力し、前記秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成し、前記多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、前記多項式Ｆに前記固定値ｔを入力して値を出力する秘密情報分散装置と、
互いに異なるｎ個の第２の乱数を生成して出力し、前記秘密情報分散装置の出力であって、前記多項式Ｆに前記固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成し、前記多項式Ｇに前記第２の乱数をそれぞれ入力して値を出力する分散秘密情報分散装置と、
を含むことを特徴とする分散情報生成装置。
【請求項４１】
前記秘密情報分散装置は、ｋ−１以下のパラメータＬを入力し、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記分散秘密情報分散装置は、前記多項式Ｆに固定値ｔを入力したときの出力を定数項とする前記多項式Ｇを生成する
請求項４０記載の分散情報生成装置。
【請求項４２】
前記秘密情報分散装置は、前記秘密情報ｓを定数項とする多項式Ｆを生成する請求項４１記載の分散情報生成装置。
【請求項４３】
前記秘密情報分散装置は、前記第１の乱数として、前記固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する請求項４０から請求項４２のうちのいずれか１項に記載の分散情報生成装置。
【請求項４４】
前記分散秘密情報分散装置は、前記第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項４０から請求項４２のうちのいずれか１項に記載の分散情報生成装置。
【請求項４５】
前記秘密情報分散装置から出力される前記第１の乱数と、前記多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記分散秘密情報分散装置から出力される、前記第２の乱数と、前記多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えた請求項４０から請求項４４のうちのいずれか１項に記載の分散情報生成装置。
【請求項４６】
秘密情報を分散する分散情報生成装置の出力に基づいて秘密情報を復元する復元装置であって、
請求項４０記載の前記秘密情報分散装置の出力を格納する記憶装置と、
閾値ｋおよび所定の固定値ｔを入力し、
前記記憶装置から、請求項４０記載の分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した前記第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを前記多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元装置と、
前記記憶装置から、請求項１記載の分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した前記第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを前記多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元装置と、
前記多項式Ｇ’に埋め込まれた値と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、前記多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置と
を備えたことを特徴とする復元装置。
【請求項４７】
前記記憶装置は、請求項４１記載の分散情報生成装置の出力を格納し、
前記復元装置は、ｋ−１以下のパラメータＬを入力し、
前記多項式復元装置は、前記記憶装置から、請求項４１記載の分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、請求項４１記載の分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記不正検出装置は、前記多項式Ｇ’の定数項と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、前記多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項４６記載の復元装置。
【請求項４８】
前記記憶装置は、請求項４２記載の分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、請求項４２記載の分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記不正検出装置は、前記多項式Ｇ’の定数項と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項４７記載の復元装置。
【請求項４９】
記憶装置は、請求項４３記載の分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、請求項４３記載の分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、請求項４３記載の分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記多項式復元装置は、前記第１の乱数として、前記固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力するか、または、前記分散秘密情報復元装置は、前記第２の乱数として、互いに異なるｎ個の定数を入力する
請求項４６から請求項４８のうちのいずれか１項に記載の復元装置。
【請求項５０】
前記不正検出装置は、前記多項式Ｇ’に埋め込まれた値と、前記多項式Ｆ’に前記固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項４６から請求項４９のうちのいずれか１項に記載の復元装置。
【請求項５１】
秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、
前記復元装置が出力した（ｋ−１）次多項式ｆを入力し、請求項４０から請求項４４のうちのいずれか１項に記載の分散情報生成装置の出力を格納する記憶装置から、前記分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数ｒと、前記秘密情報分散装置が生成した前記多項式Ｆに前記第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）本願は、先の日本特許出願２００７−０２３９０７号（２００７年２月２日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は、秘密情報を分散し復元するための分散情報生成装置、復元装置、復元結果検証装置、秘密情報分散システム、分散情報生成方法、復元方法、復元結果検証方法、秘密情報分散方法、分散情報生成プログラム、復元プログラム、復元結果検証プログラムおよび秘密情報分散プログラムに関する。
【背景技術】
【０００２】
秘密の情報（以下、秘密情報と表記する。）を保管する場合、紛失、破壊の脅威と、盗難の脅威がある。紛失、破壊の脅威に対しては秘密情報のコピーを作成することが有効である。しかし、コピーを作成すると、盗難に対する脅威は増してしまう。【０００３】
このような問題を解決する手段の１つとして、秘密分散法がある。秘密分散法の１つである（ｋ，ｎ）閾値法は、秘密情報をｎ個の分散情報に符号化し、そのうち任意のｋ個以上の分散情報を集めれば、秘密情報を完全に復元できるが、ｋ−１個までの分散情報を集めただけでは、秘密情報に関する情報をまったく得られないという特徴を持つ。したがって、ｋ−１個までの分散情報が盗難にあったとしても秘密情報は漏れない。また、ｎ−ｋ個までの分散情報が破壊されても、秘密情報を復元できる。【０００４】
非特許文献１には、（ｋ，ｎ）閾値法として、ｋ−１次多項式を用いることが記載されている。非特許文献１に記載された方式は、素数または素数のべき乗ｐに対する有限体ＧＦ（ｐ）を秘密情報のデータ集合として用い、秘密情報ｓを定数項に持つＧＦ（ｐ）上のランダムなｋ−１次多項式ｆ（ｘ）上の点、（ｘ１，ｆ（ｘ１）），・・・，（ｘｎ，ｆ（ｘｎ））を分散情報とする方式である。ｋ個の分散情報からｋ−１次の多項式を一意に復元することができ、ｆ（０）である秘密情報ｓを復元することができる。また、ｋ−１個以下の分散情報からはｆ（０）を定めることはできず、ｓに関する情報は一切漏れない。 【０００５】
非特許文献２に記載された方式は、非特許文献１に記載された方式と同様に、ＧＦ（ｐ）上のランダムなｋ−１次多項式ｆ（ｘ）上の点、（ｘ１，ｆ（ｘ１）），・・・，（ｘｎ，ｆ（ｘｎ））を分散情報とする方式であり、秘密情報をｋ−１次多項式の定数項以外の部分、例えば１次以上の係数などにも埋め込むことで、分散情報のサイズを小さくおさえることができる方式である。しかし、ｋ−１以下の分散情報からも秘密情報に関する情報が漏れるという弱点がある。なお、分散情報のサイズとは、分散情報の集合の要素数である。【０００６】
非特許文献１，２に記載された方式に共通する性質として、ｘｉ（ｉ＝１，・・・，ｎ）に、分散情報を保管する機器に割り振られた番号などを用いることができることが挙げられる。以下、ｘｉに対するｆ（ｘｉ）をｘｉに対する分散情報と呼ぶ。【０００７】
非特許文献３に記載された方式は、非特許文献１，２に記載された（ｋ，ｎ）閾値法において、不正を検知する方式である。（１−ε）を不正を検知できる確率とすると、秘密情報が要素数ｓの集合から選ばれるとき、分散情報は、要素数が（（ｓ−１）（ｋ−１）／ε＋ｋ）２の集合の要素になる。この方式は、復元する際に用いるｋ個の分散情報のうち、最大ｋ−１個が改竄されても不正を検知できる方式である。【０００８】
非特許文献４には、非特許文献３に記載された方式よりも、分散情報のサイズが小さく、最大ｋ−１個が改竄されても不正を検知できることが記載されている。【０００９】
【非特許文献１】Adi Shamir, "How to share a secret", Comm.ACM, 1979, 22(11), 612-613
【非特許文献２】G R Blakley, Catherine Meadows, "Security of Ramp schemes", Proc. of Cryptology, 1993, Vol.6, No.3, p.157-167
【非特許文献３】Martin Tompa, Heather Woll, "How to Share a Secret with Cheaters", In Journal of Cryptology, 1988, vol.1, p.133-138
【非特許文献４】Wakaha Ogata, Kaoru Kurosawa, Douglas R Stinson, "Optimum Secret Sharing Scheme Secure Against Cheating", SIAM J.Discrete Math, 2006, vol.20, no1, p.79-95
【発明の開示】
【発明が解決しようとする課題】
【００１０】
以上の非特許文献１〜４の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。
ここで、例えば、非特許文献１，２に記載されている通常の（ｋ，ｎ）閾値法において、分散情報の作成、配付が正しく行われている状況を考える。秘密情報を復元しようとする者は、他の分散情報を保持する者から分散情報を集めようとする。しかし、分散情報を要求された側が、配付された値を改竄することなく渡すとは限らない。改竄された分散情報を用いて復元された値は、秘密情報と異なる値になってしまうことがある。例えば、遺言状を分散したデータを子孫に渡しておいた場合に、分散したデータが改竄され、一部の子孫にとって都合の良い内容に書き換えられては困る。【００１１】
そのため、分散した秘密情報と復元結果とが異なる値になってしまうように改竄された値が復元に用いられた分散情報のなかに存在することが、高い確率で検知できるような方式が望まれる。以下、改竄した分散情報を渡す秘密分散法への参加者を不正者と呼ぶ。【００１２】
これらの問題を解決している方式として、非特許文献３や非特許文献４に記されている方式が知られている。しかし、非特許文献３に記載された方式では、分散情報のサイズが、かなり大きくなってしまうという問題がある。また、非特許文献４に記載された方式では、ｋ−１個の分散情報を作る不正者は、ｋ−１個以下の分散情報しか知らない、という条件が必要となり、この条件を満たさない場合には不正を検知できないという問題がある。【００１３】
また、非特許文献３，４に記載された方式は、復元処理に用いられた分散情報のなかに、少なくとも１つは正しく作られた分散情報が含まれていることを条件に不正を検出できる方式である。しかし、正しい分散情報であることが保障できるのは、自分自身に配られた分散情報だけである。つまり、自分自身が参加しなかった復元処理については、その復元処理に用いられた分散情報の中に正しく作られた分散情報が含まれているかどうか判断できないため、その復元処理の結果を信頼することはできない。【００１４】
すなわち、ｋ個以上の分散情報を知る不正者によって分散情報がｋ−１個まで改竄された場合であっても、高い確率で不正を検知可能な方式では、分散情報が秘密情報に比べてかなり大きなデータになってしまうという問題がある。また、自分が復元処理に参加しなかった場合、復元処理に用いられた分散情報のなかに改竄された値があったかどうか判らないという問題がある。【００１５】
そこで、本発明は、不正者が閾値数個以上の分散情報を持っていても分散情報の改竄を検知する確率を高めることを可能とし、従来と比較して秘密情報に対する分散情報のサイズを縮減する分散情報生成装置、復元装置、復元結果検証装置、秘密情報分散システム、分散情報生成方法、復元方法、復元結果検証方法、秘密情報分散方法、分散情報生成プログラム、復元プログラム、復元結果検証プログラムおよび秘密情報分散プログラムを提供することを目的とする。
本発明は、自分が復元処理に参加しなかった場合でも、復元処理結果を検証できる復元結果検証装置、秘密情報分散システム、復元結果検証方法、秘密情報分散方法、復元結果検証プログラムおよび秘密情報分散プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の第１の側面による分散情報生成装置においては、秘密情報を分散する分散情報生成装置であって、秘密情報分散装置と、分散秘密情報分散装置と、秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力手段とを備え、秘密情報分散装置は、固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成装置と、秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成装置と、多項式Ｆに各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力装置とを含み、分散秘密情報分散装置は、互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成装置と、分散情報出力装置の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成装置と、多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力装置とを含む。【００１７】
本発明の第２の側面によれば、前記第１の側面に係る分散情報生成装置において、前記分散入力手段は、ｋ−１以下のパラメータＬを入力し、第１分散多項式生成装置は、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、第２分散多項式生成装置は、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００１８】
本発明の第３の側面によれば、前記第１の側面に係る分散情報生成装置において、前記第１分散多項式生成装置は、秘密情報ｓを定数項とする多項式Ｆを生成してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００１９】
本発明の第４の側面によれば、前記第１の側面に係る分散情報生成装置において、前記第１乱数生成装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、第２乱数生成装置は、第２の乱数として、互いに異なるｎ個の定数を生成して出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００２０】
本発明の第５の側面によれば、前記第１乃至第４のいずれか１の側面に係る分散情報生成装置において、前記第１乱数生成装置が出力した第１の乱数と、分散情報出力装置が出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成装置が出力した第２の乱数と、分散分散情報出力装置が出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えてもよい。そのような構成によれば、分散情報生成装置の出力を記憶装置に記憶させることができる。【００２１】
本発明の第６の側面による復元装置においては、秘密情報を分散する分散情報生成装置の出力に基づいて秘密情報を復元する復元装置であって、第１の側面に係る分散情報生成装置の出力を格納する記憶装置と、閾値ｋおよび所定の固定値ｔを入力する復元入力手段と、記憶装置から、前記第１の側面に係る分散情報生成装置における秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元装置と、記憶装置から、第１の側面に係る分散情報生成装置における分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元装置と、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置とを備える。【００２２】
本発明の第７の側面によれば、前記第６の側面の復元装置において、前記記憶装置は、前記第２の側面の分散情報生成装置の出力を格納し、前記復元入力手段は、ｋ−１以下のパラメータＬを入力し、前記多項式復元装置は、記憶装置から、前記第２の側面の分散情報生成装置の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元装置は、記憶装置から、前記第２の側面の分散情報生成装置の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。  【００２３】
本発明の第８の側面によれば、前記第７の側面に係る復元装置において、前記記憶装置は、前記第３の側面の分散情報生成装置の出力を格納し、多項式復元装置は、記憶装置から、前記第３の側面の分散情報生成装置の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００２４】
本発明の第９の側面によれば、前記第６乃至８のいずれか１の側面に係る復元装置において、前記記憶装置は、前記第４の側面の分散情報生成装置の出力を格納し、多項式復元装置は、記憶装置から、前記第４の側面の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記第４の側面の分散情報生成装置の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元装置は、記憶装置から、前記第４の側面のの分散情報生成装置の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、多項式復元装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力し、または、分散秘密情報復元装置は、第２の乱数として、互いに異なるｎ個の定数を入力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００２５】
本発明の第１０の側面によれば、前記第６乃至第９のいずれか１の側面に係る復元装置において、前記不正検出装置は、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力することが望ましい。そのような構成によれば、復元装置が出力した値を検証することができる。【００２６】
本発明の第１１の側面による復元結果検証装置においては、秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、復元装置が出力した（ｋ−１）次多項式ｆを入力し、前記第１の側面から第５の側面のうちのいずれかの分散情報生成装置の出力を格納する記憶装置から、前記第１の側面から前記第５の側面のうちのいずれか１の秘密情報分散装置が出力した第１の乱数ｒと、前記第１の側面から前記第５の側面のうちのいずれかに記載の秘密情報分散装置が生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する。【００２７】
本発明の第１２の側面による秘密情報分散システムにおいては、前記第１の側面から前記第５の側面のうちのいずれか１の分散情報生成装置と、前記第６の側面から前記第１０の側面のうちのいずれか１の復元装置とを備える。【００２８】
本発明の第１３の側面の秘密情報分散システムによれば、前記第１１の側面の復元結果検証装置を備えることが望ましい。そのような構成によれば、復元装置が出力した値を検証することができる。【００２９】
本発明の第１４の側面による分散情報生成方法においては、秘密情報を分散する分散情報生成方法であって、秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力ステップと、秘密情報分散ステップと、分散秘密情報分散ステップとを含み、秘密情報分散ステップは、固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成ステップと、秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成ステップと、多項式Ｆに各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力ステップとを有し、分散秘密情報分散ステップは、互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成ステップと、分散情報出力ステップの出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成ステップと、多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力ステップとを有する  【００３０】
本発明の第１５の側面によれば、前記第１４の側面における前記分散入力ステップで、ｋ−１以下のパラメータＬを入力し、第１分散多項式生成ステップで、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、第２分散多項式生成ステップで、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００３１】
本発明の第１６の側面によれば、前記第１５の側面における前記第１分散多項式生成ステップで、秘密情報ｓを定数項とする多項式Ｆを生成してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００３２】
本発明の第１７の側面によれば、前記第１４乃至第１６のいずれか１の側面における前記第１乱数生成ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、第２乱数生成ステップで、第２の乱数として、互いに異なるｎ個の定数を生成して出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００３３】
本発明の第１８の側面によれば、前記第１４乃至第１７のいずれか１の側面における前記第１乱数生成ステップで出力した第１の乱数と、分散情報出力ステップで出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、第２乱数生成ステップで出力した第２の乱数と、分散分散情報出力ステップで出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させてもよい。そのような構成によれば、分散情報生成方法における出力を記憶装置に記憶させることができる。【００３４】
本発明の第１９の側面による復元方法においては、秘密情報を復元するための復元方法であって、閾値ｋおよび所定の固定値ｔを入力する復元入力ステップと、前記第１４の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１４の側面の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１４の側面の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元ステップと、記憶装置から、前記第１４の側面の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を前記第１４の側面の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元ステップと、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出ステップとを含む。【００３５】
本発明の第２０の側面によれば、前記第１９の側面における前記復元入力ステップで、ｋ−１以下のパラメータＬを入力し、多項式復元ステップで、前記第１５の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１５の側面の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１５の側面の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元ステップで、記憶装置から、前記第１５の側面の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を前記第１５の側面の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００３６】
本発明の第２１の側面によれば、前記第２０の側面における前記多項式復元ステップで、前記第１６の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１６の側面の前記秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１６の側面の前記秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００３７】
本発明の第２２の側面によれば、前記第１９乃至２１のいずれか１の側面における前記多項式復元ステップで、前記第１７の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１７の側面の前記秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元ステップで、記憶装置から、前記第１７の側面の前記分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を前記第１７の側面の前記散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、多項式復元ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力し、または、分散秘密情報復元ステップで、第２の乱数として、互いに異なるｎ個の定数を入力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００３８】
本発明の第２３の側面によれば、前記第１９乃至２１のいずれか１の側面における前記不正検出ステップで、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力することが望ましい。そのような構成によれば、復元方法において出力した値を検証することができる。【００３９】
本発明の第２４の側面による復元結果検証方法においては、復元された秘密情報を検証するための復元結果検証方法であって、復元された秘密情報として（ｋ−１）次多項式ｆを入力し、第１４の側面から第１８の側面のうちのいずれか１の分散情報生成方法で出力した内容を格納する記憶装置から、第１４の側面から第１８の側面のうちのいずれか１の秘密情報分散ステップで出力した第１の乱数ｒと、第１４の側面から第１８の側面のうちのいずれか１の秘密情報分散ステップで生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する復元結果検証方法が提供される。【００４０】
本発明の第２５の側面による秘密情報分散方法においては、第１４の側面から第１８の側面のうちのいずれか１の分散情報生成方法と、第１９の側面から第２３の側面のうちのいずれか１の復元方法とを含む。【００４１】
本発明の第２６の側面によれば、第２５の側面に係る秘密情報分散方法において、第２４の側面の復元結果検証方法を含むことが望ましい。そのような構成によれば、復元方法において出力した値を検証することができる。【００４２】
本発明の第２７の側面による分散情報生成プログラムにおいては、秘密情報を分散するための分散情報生成プログラムであって、コンピュータに、秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力処理と、秘密情報分散処理と、分散秘密情報分散処理とを実行させ、秘密情報分散処理で、固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成処理と、秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成処理と、多項式Ｆに各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力処理とを実行させ、分散秘密情報分散処理で、互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成処理と、分散情報出力処理の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成処理と、多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力処理とを実行させる。【００４３】
本発明の第２８の側面によれば、前記第２７の側面に係るプログラムにおいて、コンピュータに、前記分散入力処理で、ｋ−１以下のパラメータＬを入力する処理を実行させ、前記第１分散多項式生成処理で、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成する処理を実行させ、前記第２分散多項式生成処理で、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００４４】
本発明の第２９の側面によれば、前記第２８の側面に係るプログラムにおいて、コンピュータに、前記第１分散多項式生成処理で、秘密情報ｓを定数項とする多項式Ｆを生成する処理を実行させてもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００４５】
本発明の第３０の側面によれば、前記第２７乃至第２９のいずれか１の側面に係るプログラムにおいて、コンピュータに、第１乱数生成処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する処理を実行させ、または、第２乱数生成処理で、第２の乱数として、互いに異なるｎ個の定数を生成して出力する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００４６】
本発明の第３１の側面によれば、前記第２７乃至第３０のいずれか１の側面に係るプログラムにおいて、コンピュータに、第１乱数生成処理で出力した第１の乱数と、分散情報出力処理で出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、第２乱数生成処理で出力した第２の乱数と、分散分散情報出力処理で出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる処理を実行させてもよい。そのような構成によれば、分散情報生成プログラム実行時の出力を記憶装置に記憶させることができる。【００４７】
本発明の第３２の側面による復元プログラムにおいては、秘密情報を復元するための復元プログラムであって、コンピュータに、閾値ｋおよび所定の固定値ｔを入力する復元入力処理と、第２７の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、第２７の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱数を第２７の側面の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元処理と、記憶装置から、第２７の側面の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を第２７の側面の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元処理と、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出処理とを実行させる。【００４８】
本発明の第３３の側面によれば、前記第３２の側面に係るプログラムにおいて、コンピュータに、前記復元入力処理で、ｋ−１以下のパラメータＬを入力し、多項式復元処理で、前記第２８の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、前記第２８の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱数を前記第２８の側面の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、分散秘密情報復元処理で、記憶装置から、前記第２８の側面の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を前記第２８の側面の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成する処理を実行させ、不正検出処理で、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００４９】
本発明の第３４の側面によれば、前記第３３の側面に係るプログラムにおいて、コンピュータに、前記多項式復元処理で、前記第２９の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、前記第２９の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱数を前記第２９の側面の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、不正検出処理で、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させてもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。【００５０】
本発明の第３５の側面によれば、前記第３２乃至第３４のいずれか１の側面に係るプログラムにおいて、コンピュータに、前記多項式復元処理で、前記第３０の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、前記第３０の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱数を前記第３０の側面の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成する処理を実行させ、前記分散秘密情報復元処理で、記憶装置から、前記第３０の側面の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を前記第３０の側面の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成する処理を実行させ、前記多項式復元処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力する処理を実行させ、または、前記分散秘密情報復元処理で、第２の乱数として、互いに異なるｎ個の定数を入力する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。【００５１】
本発明の第３６の側面によれば、前記第３２乃至第３５のいずれか１の側面に係るプログラムにおいて、コンピュータに、前記不正検出処理で、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する処理を実行させることが望ましい。そのような構成によれば、復元プログラム実行時に出力した値を検証することができる。【００５２】
本発明の第３６の側面による復元結果検証プログラムにおいては、復元された秘密情報を検証するための復元結果検証プログラムであって、コンピュータに、復元された秘密情報として（ｋ−１）次多項式ｆを入力し、前記第２７の側面から前記第３１の側面のうちのいずれか１の分散情報生成プログラムで出力した内容を格納する記憶装置から、前記第２７の側面から前記第３１の側面のうちのいずれか１の秘密情報分散処理で出力した第１の乱数ｒと、前記第２７の側面から前記第３１の側面のうちのいずれか１の秘密情報分散処理で生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させる。【００５３】
本発明の第３６の側面による秘密情報分散プログラムにおいては、前記第２７の側面から前記第３１の側面のうちのいずれか１の分散情報生成プログラムと、前記第３２の側面から前記第３６の側面のうちのいずれか１の復元プログラムとを含む秘密情報分散プログラムが提供される。【００５４】
本発明の第３７の側面による秘密情報分散プログラムにおいては、前記第２７の側面から前記第３１の側面のうちのいずれか１の分散情報生成プログラムと、前記第３２の側面から前記第３６の側面のうちのいずれか１の復元プログラムと、前記第３７の側面の復元結果検証プログラムとを含む秘密情報分散プログラムが提供される。【００５５】
本発明による秘密情報分散システムにおいては、例えば、（ｋ，ｎ）閾値法として、にｋ−１次多項式を用いた方式（非特許文献１、非特許文献２参照）を用いてもよい。【００５６】
本発明による秘密情報分散システムにおいては、例えば、分散情報生成装置と、復元装置と、復元情報検証装置と、複数の記憶装置からなる秘密情報分散システムであって、秘密情報ｓと、閾値ｋと、分散情報数ｎを入力として、ある固定の値（以降、「Ｔ」と呼ぶ）と異なり、且つ互いに異なる分散情報数個の乱数の組（以降、「乱数セットＡ」と呼ぶ）と、互いに異なる分散情報数個の乱数の組（以降、「乱数セットＢ」と呼ぶ）を生成し、乱数セットＡの各要素とＴに対する秘密情報の分散情報を秘密情報を、ランダムな（ｋ−１）次多項式ｆを用いて生成し、対応する乱数セットＡの要素を記憶する記憶装置に記憶させ、乱数セットＢの各要素に対するｆ（Ｔ）の分散情報をｋ−１次多項式を用いて生成し、対応する乱数セットＢの要素を記憶する記憶装置に記憶させる分散情報生成装置と、ｋ機の記憶装置から、それぞれの記憶する乱数セットＡの要素と、乱数セットＢの要素と、乱数セットＡに対する秘密情報の分散情報と、乱数セットＢに対するｆ（Ｔ）の分散情報を読み出し、閾値個の乱数セットＢに対するｆ（Ｔ）の分散情報から復元したｆ（Ｔ）を復元し（以降、復元した値を「ｆＴ’」と呼ぶ）、閾値個の乱数セットＡに対する秘密情報の分散情報よりｆを復元し（以降、復元した多項式を「ｆ’」と呼ぶ）、（Ｔ，ｆＴ’）が復元したｆ’上の点であるかをチェックし、（Ｔ，ｆＴ’）が復元したｆ’上の点であったとき、ｆ（０）を秘密情報として、多項式ｆをチェック用データとして出力し、それ以外の場合、不正の検出を表す記号を出力する復元装置と、秘密情報のデータ集合上の多項式ｆとを入力として、１機の記憶装置の記憶する乱数セットＡの要素ｒと、乱数セットＡの要素に対する秘密情報の分散情報ｖｒを読みだし、ｆ（ｒ）＝ｖｒを満たしているとき、ｆ（０）を出力し、それ以外の場合不正の検出を表す記号を出力する復元情報検証装置と、乱数セットＡ用データ集合の要素と、乱数セットＢ用データ集合の要素と、乱数セットＡの要素に対する秘密情報の分散情報と、乱数セットＢの要素に対する固定値に対する秘密情報の分散情報の分散情報とを記憶する装置を持つ記憶装置を備えることを特徴とする。このような構成を採用し、乱数セットＡ，Ｂ用のデータ集合のサイズを適切に選ぶことで、本発明の目的を達成することができる。
【発明の効果】
【００５７】
本発明によれば、不正者が閾値数個以上の分散情報を持っていても分散情報の改竄を検知する確率を高めることを可能とし、従来と比較して秘密情報に対する分散情報のサイズを縮減することができる。また、本発明によれば、自分が復元処理に参加しなかった場合でも、復元処理結果を検証できる。
【図面の簡単な説明】
【００５８】
【図１】本発明による秘密情報分散システムの一実施の形態を示すブロック図である。
【図２】分散情報生成装置および記憶装置の構成例を示すブロック図である。
【図３】復元装置および記憶装置の構成例を示すブロック図である。
【図４】復元結果検証装置および記憶装置の構成例を示すブロック図である。
【図５】コンピュータの構成例を示すブロック図である。
【図６】本発明の一実施の形態における分散情報生成装置の動作を示すフローチャートである。
【図７】本発明の一実施の形態における復元装置動作を示すフローチャートである。
【図８】本発明の一実施の形態における復元結果検証装置の動作を示すフローチャートである。
【符号の説明】
【００５９】
１００          分散情報生成装置
１０１          秘密情報分散装置
１０２          分散秘密情報分散装置
２００          復元装置
２０１          多項式秘密情報復元装置
２０２          分散秘密情報復元装置
２０３          不正検出装置
３００＿１〜ｎ  記憶装置
３０１＿１〜ｎ  第１乱数記憶装置
３０２＿１〜ｎ  分散秘密情報記憶装置
３０３＿１〜ｎ  第２乱数記憶装置
３０４＿１〜ｎ  分散分散秘密情報記憶装置
４００          復元結果検証装置
【発明を実施するための最良の形態】
【００６０】
次に、本発明を実施するための最良の形態について図面を参照して説明する。まず、ｋ−１人の不正者が、ある参加者をだますという不正、すなわち、ｋ−１個の分散情報の改竄を検知する場合について説明する。図１は、本発明による秘密情報分散システムの構成の一実施形態を示すブロック図である。図１を参照すると、本実施形態の秘密情報分散システムは、分散情報生成装置１００と、復元装置２００と、記憶装置３００−１〜３００−ｎとを備える。【００６１】
分散情報生成装置１００は、秘密情報を分散する多項式ｆを生成して、第１の乱数に対する分散情報（以下、「分散秘密情報」と表記する。）を生成する。また、分散情報生成装置１００は、生成した多項式ｆに予め定められた固定値ｔを入力した値ｆ（ｔ）を分散する多項式ｇを生成して、第２の乱数に対する分散情報（以下、「分散分散秘密情報」と表記する。）を生成する。【００６２】
記憶装置３００−１〜３００−ｎは、分散情報生成装置１００が生成した分散秘密情報および分散分散秘密情報を記憶する。例えば、分散情報生成装置１００が生成したｎ個の分散秘密情報およびｎ個の分散分散秘密情報は、それぞれ記憶装置３００−１〜３００−ｎに記憶される。記憶装置３００−１〜３００−ｎは、例えば、サーバ装置のハードディスク装置や、ＵＳＢメモリ等の記憶装置で実現される。【００６３】
復元装置２００は、記憶装置３００−１〜３００−ｎのうちｋ個の記憶装置が記憶する分散秘密情報に基づいて、多項式ｆを復元する。また、復元装置２００は、記憶装置３００−１〜３００−ｎのうちｋ個の記憶装置が記憶する分散分散秘密情報に基づいて、ｆ（ｔ）を復元する。以下、復元した多項式ｆをｆ’と表記し、復元したｆ（ｔ）をｆ’（ｔ）と表記する場合がある。【００６４】
復元装置２００は、復元したｆ’（ｔ）と、多項式ｆ’に固定値ｔを入力した値とが等しくなる場合には、秘密情報を復元し、等しくならない場合には、不正があったと判断してその旨を示す情報を出力する。【００６５】
分散情報生成装置１００と記憶装置３００−１〜３００−ｎ、および記憶装置３００−１〜３００−ｎと復元装置２００は、例えば、記憶装置３００−１〜３００−ｎがサーバ装置のハードディスク装置である場合には、通信ネットワークを介して接続されてもよい。また、例えば、記憶装置３００−１〜３００−ｎがＵＳＢメモリである場合には、ＵＳＢ接続される。【００６６】
図２は、図１の分散情報生成装置１００および記憶装置３００−１〜３００−ｎの構成例を示すブロック図である。分散情報生成装置１００の構成例について、図２を用いて説明を行う。分散情報生成装置１００は、秘密情報分散装置１０１と、分散秘密情報分散装置１０２とを含む。【００６７】
分散情報生成装置１００は、秘密情報用データ集合Ｓの元である秘密情報ｓ、閾値を表すｋ、固定値ｔおよび分散情報数を表すｎを入力し、分散秘密情報として分散秘密情報用データ集合ＢＳの元を生成し、分散分散秘密情報として分散分散秘密情報用データ集合ＢＢＳの元を生成する。そして、記憶装置３００−１〜３００−ｎに対し、固定値ｔと異なり、且つ、互いに異なる第１乱数用データ集合ＲＡの元と、互いに異なる第２乱数用データ集合ＲＢの元と、分散秘密情報用データ集合ＢＳの元と、分散分散秘密情報用データ集合ＢＢＳの元とを記憶させる。【００６８】
なお、第１乱数用データ集合ＲＡには、分散秘密情報用データ集合ＢＳの部分集合を用い、第２乱数用データ集合ＲＢには、分散分散秘密情報用データ集合ＢＢＳの部分集合を用いる。また、秘密情報ｓ、閾値ｋ、固定値ｔおよび分散情報数ｎは、例えば、ユーザ等によって入力装置から入力される。【００６９】
秘密情報分散装置１０１は、集合Ｓの元ｓ、閾値ｋ、固定値ｔおよび分散情報数を表すｎを入力する。また、秘密情報分散装置１０１は、記憶装置３００−１〜３００−ｎに対し、固定値tと異なり、且つ、互いに異なる第１乱数用データ集合ＲＡの元を記憶させる。ここで、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）が記憶する第１乱数用データ集合ＲＡの元をｒｉとする。【００７０】
秘密情報分散装置１０１は、例えば、非特許文献１または非特許文献２に記載されている（ｋ，ｎ＋１）閾値法を用いて、ｓを分散する分散秘密情報用データ集合ＢＳ上の多項式ｆを生成する。そして、多項式ｆに第１乱数用データ集合ＲＡの元ｒｉを入力し、記憶装置３００−ｉに分散秘密情報用データ集合ＢＳの元ｆ（ｒｉ）を記憶させる。例えば、記憶装置３００−１に対し、元ｆ（ｒ１）を記憶させ、記憶装置３００−２に対し、元ｆ（ｒ２）を記憶させ、記憶装置３００−ｎに対し、元ｆ（ｒｎ）を記憶させる。また、秘密情報分散装置１０１は、分散秘密情報分散装置１０２にｆ（ｔ）を出力する。【００７１】
なお、秘密情報分散装置１０１は、（ｋ−１）次多項式ｆとして、例えば、係数や定数項に秘密情報ｓが埋め込まれた多項式ｆを生成する。【００７２】
分散秘密情報分散装置１０２は、秘密情報分散装置１０１の出力ｆ（ｔ）、閾値ｋおよび分散情報数ｎを入力する。また、分散秘密情報分散装置１０２は、記憶装置３００−１〜３００−ｎに対し、互いに異なる第２乱数用データ集合ＲＢの元を生成して記憶させる。ここで、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）が記憶する第２乱数用データ集合ＲＢの元をｘｉとする。【００７３】
分散秘密情報分散装置１０２は、例えば、非特許文献１または非特許文献２に記載されている（ｋ，ｎ＋１）閾値法を用いて、分散秘密情報用データ集合ＢＳの元であるｆ（ｔ）を分散する分散分散秘密情報用データ集合ＢＢＳ上の多項式ｇを生成する。そして、多項式ｇに第２乱数用データ集合ＲＢの元ｘｉを入力し、記憶装置３００−ｉに分散分散秘密情報用データ集合ＢＢＳの元ｇ（ｘｉ）を記憶させる。例えば、記憶装置３００−１に対し、元ｇ（ｘ１）を記憶させ、記憶装置３００−２に対し、元ｇ（ｘ２）を記憶させ、記憶装置３００−ｎに対し、元ｇ（ｘｎ）を記憶させる。【００７４】
図３は、復元装置２００および記憶装置３００−１〜３００−ｎの構成例を示すブロック図である。復元装置２００の構成例について、図３を用いて説明を行う。復元装置２００は、多項式復元装置２０１と、分散秘密情報復元装置２０２と、不正検出装置２０３とを含む。【００７５】
復元装置２００は、固定値ｔおよび閾値ｋを入力する。また、記憶装置３００−１〜３００−ｎのうちのｋ機の記憶装置から、それぞれの記憶する第１乱数用データ集合ＲＡの元と、第２乱数用データ集合ＲＢの元と、分散秘密情報用データ集合ＢＳの元と、分散分散秘密情報用データ集合ＢＢＳの元とを読み出す。そして、秘密情報用データ集合Ｓの元と分散秘密情報用データ集合ＢＳ上のｋ−１次多項式ｆ、もしくは不正の検出を表す記号を出力する。【００７６】
多項式復元装置２０１は、閾値ｋを入力し、記憶装置３００−１〜３００−ｎのうちのｋ機の記憶装置から、それぞれの記憶する第１乱数用データ集合ＲＡの元と、分散秘密情報用データ集合ＢＳの元とを読み出し、多項式用データ集合Ｖの元を出力する。【００７７】
例えば、多項式復元装置２０１は、各記憶装置の第１乱数用データ集合ＲＡの元および分散秘密情報用データ集合ＢＳの元を代入したｋ個の連立方程式を生成して解を算出するなどの方法により、ｋ−１次多項式ｆを求めて出力する。【００７８】
分散秘密情報復元装置２０２は、閾値ｋを入力し、記憶装置３００−１〜３００−ｎのうちのｋ機の記憶装置から、第２乱数用データ集合ＲＢの元と、分散分散秘密情報用データ集合ＢＢＳの元とを読み出し、分散秘密情報用データ集合ＢＳの元を出力する。【００７９】
例えば、分散秘密情報復元装置２０２は、各記憶装置の第２乱数用データ集合ＲＢの元および分散分散秘密情報用データ集合ＢＢＳの元を代入したｋ個の連立方程式を解くなどの方法により、ｋ−１次多項式ｇを求めて、分散秘密情報用データ集合ＢＳの元を出力する。【００８０】
ここで、分散秘密情報復元装置２０２が出力した分散秘密情報用データ集合ＢＳの元をｃとすると、第２乱数用データ集合ＲＢの元および分散分散秘密情報用データ集合ＢＢＳの元が改竄されていない場合には、ｃは、秘密情報分散装置１０１が出力したｆ（ｔ）と等しくなる。また、第１乱数用データ集合ＲＡの元および分散秘密情報用データ集合ＢＳの元が改竄されていない場合には、多項式復元装置２０１が出力した多項式ｆは、秘密情報分散装置１０１が生成した多項式ｆと等しくなる。したがって、第１乱数用データ集合ＲＡの元、分散秘密情報用データ集合ＢＳの元、第２乱数用データ集合ＲＢの元および分散分散秘密情報用データ集合ＢＢＳの元が改竄されていない場合には、多項式復元装置２０１が出力した多項式ｆに固定値ｔを入力した値と、分散秘密情報復元装置２０２が出力した分散秘密情報用データ集合ＢＳの元ｃとは、等しくなる。【００８１】
不正検出装置２０３は、固定値ｔと、多項式復元装置２０１が出力した多項式用データ集合Ｖの元ｆと、分散秘密情報復元装置２０２が出力した分散秘密情報用データ集合ＢＳの元ｃを入力する。そして、不正検出装置２０３は、ｆ（ｔ）＝ｃを満たしているとき、秘密情報ｓとしてｆ（０）を出力し、チェック用データとしてｆを出力する。また、ｆ（ｔ）＝ｃを満たしていないとき、不正検出装置２０３は、不正の検出を表す記号を出力する。【００８２】
なお、上記に示す実施の形態の構成は、以下に示すような復元装置２００の構成を示している。多項式復元装置２０１は、秘密情報分散装置１０１が出力した第１の乱数と、第１の乱数を秘密情報分散装置１０１が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する。分散秘密情報復元装置２０２は、分散秘密情報分散装置１０２が出力した第２の乱数と、第２の乱数を分散秘密情報分散装置１０２が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する。【００８３】
記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）は、第１乱数用データ集合ＲＡの元を記憶する第１乱数記憶装置３０１−ｉと、分散秘密情報データ集合ＢＳの元を記憶する分散秘密情報記憶装置３０２−ｉと、第２乱数用データ集合ＲＢの元を記憶する第２乱数記憶装置３０３−ｉと、分散分散秘密情報データ集合ＢＢＳの元を記憶する分散分散秘密情報記憶装置３０４−ｉとを備える。なお、図２および図３には、ｎ機の記憶装置３００−１〜３００−ｎを示す。【００８４】
本発明の一実施の形態において、復元結果検証装置は、ある分散情報を持っている参加者が、自分が参加しなかった復元処理の正しさを検証するために用いられる装置である。例えば、復元結果検証装置を用いて、ｋ人の不正者が、自分たちの分散情報を使って復元処理を行い、復元結果を偽るという不正の有無を検証することができる。【００８５】
図４は、復元結果検証装置４００および記憶装置３００の構成例を示すブロック図である。復元結果検証装置４００は、例えば、ある分散情報を持っている参加者が、自分が参加しなかった復元処理の正しさを検証しようとする場合に使用される。復元結果検証装置４００は、既に行われた復元処理における復元装置２００の出力（図３の不正検出装置２０３からの出力データ１）と、その復元処理に用いられなかった分散秘密情報とを入力して、検証を行う。【００８６】
以下の説明では、記憶装置３００が、復元処理に用いられなかった分散情報を記憶している場合を例にして説明する。記憶装置３００は、第１乱数用データ集合ＲＡの元ｒを記憶する第１乱数記憶装置３０１と、分散秘密情報データ集合ＢＳの元Ｖｒを記憶する分散秘密情報記憶装置３０２と、第２乱数用データ集合ＲＢの元を記憶する第２乱数記憶装置３０３と、分散分散秘密情報データ集合ＢＢＳの元を記憶する分散分散秘密情報記憶装置３０４とを備える。【００８７】
復元結果検証装置４００は、記憶装置３００から、第１乱数用データ集合ＲＡの元ｒと、分散秘密情報用データ集合ＢＳの元Ｖｒとを読み出す。また、復元結果検証装置４００は、復元装置２００が出力した多項式用データ集合Ｖの元ｆと、秘密情報用データ集合の元ｓとを入力する。【００８８】
ここで、多項式用データ集合Ｖの元ｆは、例えば、ある分散情報を持っている参加者が参加しなかった復元処理における出力である。また、例えば、記憶装置３００から読み出す第１乱数用データ集合ＲＡの元ｒおよび分散秘密情報用データ集合ＢＳの元Ｖｒは、当該参加者が持っている分散情報であって、改竄されていない情報である。したがって、復元装置２００から入力した多項式用データ集合Ｖの元ｆが正しければ、ｆ（ｒ）＝Ｖｒを満たす。【００８９】
復元結果検証装置４００は、ｆ（ｒ）＝Ｖｒを満たしているとき、秘密情報用データ集合の元ｓを出力し、満たしていないとき不正の検出を表す記号を出力する。【００９０】
なお、図２〜図４に示した分散情報生成装置１００、復元装置２００および復元結果検証装置４００は、例えば、論理回路などから構成されるＬＳＩ(large scale integration )やＤＳＰ(digital signal processor)等の半導体集積回路によって実現してもよい。【００９１】
また、分散情報生成装置１００、復元装置２００および復元結果検証装置４００は、コンピュータ（例えば、パーソナルコンピュータ）によって実現してもよい。図５は、コンピュータの構成例を示すブロック図である。図５に示すコンピュータは、プログラムにしたがって所定の処理を実行する処理装置１０と、処理装置に対してコマンドや情報などを入力するための入力装置２０と、処理装置１０の処理結果をモニタするための出力装置３０とを備える。【００９２】
図５に示す処理装置１０は、ＣＰＵ１１と、主記憶装置１２と、記録媒体１３と、データ蓄積装置１４と、メモリ制御インターフェース部１５と、Ｉ／Ｏインターフェース部１６とを有し、それぞれがバス１８を介して接続される。【００９３】
主記憶装置１２は、ＣＰＵ１１の処理に必要な情報を一時的に記憶する。記録媒体１３は、後述する分散情報生成装置１００、復元装置２００、復元結果検証装置４００としての処理をＣＰＵ１１に実行させるためのプログラムを記録する。データ蓄積装置１４は、秘密情報や、閾値、分散情報数、固定値などを格納する。メモリ制御インターフェース部１５は、主記憶装置１２、記録媒体１３及びデータ蓄積装置１４のデータ転送を制御する。Ｉ／Ｏインターフェース部１６は、入力装置２０及び出力装置３０とのインターフェース装置である。【００９４】
なお、データ蓄積装置１４は、処理装置１０内にある必要はなく、処理装置１０から独立して備えられてもよい。また、データ蓄積装置１４は、第１乱数記憶装置３０１、分散秘密情報記憶装置３０２、第２乱数記憶装置３０３および分散分散秘密情報記憶装置３０４を備える記憶装置３００としてもよい。【００９５】
処理装置１０は、記録媒体１３に記録されたプログラムにしたがって、後述する分散情報生成装置１００または復元装置２００としての機能を実現する。記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。【００９６】
次に、本発明の実施の形態の動作を、図６、図７、図８に示すフローチャートに従って説明する。【００９７】
まず、分散情報生成装置１００の動作について説明する。図６は、本実施の形態における分散情報生成装置１００の動作を示すフローチャートである。【００９８】
はじめに、分散情報生成装置１００は、秘密情報用データ集合Ｓの元である秘密情報ｓと、閾値を表すｋと、固定値ｔと、分散情報数を表すｎとを入力する（ステップＳ１１）。【００９９】
次に、分散情報生成装置１００は、秘密情報分散装置１０１に、閾値ｋと、分散情報数ｎと、秘密情報ｓと、固定値ｔとを入力し、記憶装置３００−１〜３００−ｎの第１乱数記憶装置３０１−１〜３０１−ｎに対し、互いに異なる第１乱数用データ集合ＲＡの元を記憶させる（ステップＳ１２）。【０１００】
次に、秘密情報分散装置１０１は、ｋを閾値として、第１乱数記憶装置３０１−１〜３０１−ｎが記憶するデータ（第１の乱数）に対する秘密情報ｓの分散情報（分散秘密情報）と、固定値ｔに対する秘密情報ｓの分散情報とを生成する。秘密情報分散装置１０１は、第１乱数記憶装置３０１−１〜３０１−ｎが記憶するデータに対する秘密情報ｓの分散情報を、記憶装置３００−１〜３００−ｎの分散秘密情報記憶装置３０２−１〜３０２−ｎに記憶させる。また、秘密情報分散装置１０１は、固定値ｔに対する秘密情報ｓの分散情報ｃを分散秘密情報分散装置１０２に出力する（ステップＳ１３）。【０１０１】
次に、分散情報生成装置１００は、分散秘密情報分散装置１０２に、閾値ｋと、分散情報数ｎと、分散情報ｃとを入力し、記憶装置３００−１〜３００−ｎの第２乱数記憶装置３０３−１〜３０３−ｎに対し、互いに異なる第２乱数用データ集合ＲＢの元を記憶させる（ステップＳ１４）。【０１０２】
次に、分散秘密情報分散装置１０２は、ｋを閾値として、第２乱数記憶装置３０３−１〜３０３−ｎが記憶するデータ（第２の乱数）に対するｃの分散情報（分散分散秘密情報）を生成する。分散秘密情報分散装置１０２は、第２乱数記憶装置３０３−１〜３０３−ｎが記憶するデータに対する分散情報ｃの分散情報を、記憶装置３００−１〜３００−ｎの分散分散秘密情報記憶装置３０４−１〜３０４−ｎに記憶させ（ステップＳ１５）、処理を終了する。【０１０３】
次に、復元装置２００の動作について説明する。図７は、本実施の形態における復元装置２００の動作を示すフローチャートである。【０１０４】
復元装置２００に、閾値を表すｋと、固定値ｔとが入力される（ステップＳ２１）。【０１０５】
復元装置２００は、ｋ機の記憶装置３００−ｉ１〜３００−ｉｋの記憶するデータを読み出す（ステップＳ２２）。なお、記憶装置３００−ｉ１〜３００−ｉｋは、例えば、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）のうちのｋ機を示す。【０１０６】
次に、復元装置２００は、多項式復元装置２０１に、データを読み出した記憶装置３００−ｉ１〜３００−ｉｋの第１乱数記憶装置３０１−ｉ１〜３０１−ｉｋに記憶されていたデータと、データを読み出した記憶装置３００−ｉ１〜３００−ｉｋの分散秘密情報記憶装置３０２−ｉ１〜３０２−ｉｋに記憶されていたデータと、閾値ｋとを入力する（ステップＳ２３）。【０１０７】
次に、多項式復元装置２０１は、秘密情報分散装置１０１の分散符号化方法に対応する復元方法を用いて、多項式用データ集合Ｖの元ｆを復元し、出力する（ステップＳ２４）。【０１０８】
次に、復元装置２００は、分散秘密情報復元装置２０２に、データを読み出した記憶装置３００−ｉ１〜３００−ｉｋの第２乱数記憶装置３０３−ｉ１〜３０３−ｉｋに記憶されていたデータと、データを読み出した記憶装置３００−ｉ１〜３００−ｉｋの分散分散秘密情報記憶装置３０４−ｉ１〜３０４−ｉｋに記憶されていたデータと、閾値ｋとを入力する（ステップＳ２５）。【０１０９】
次に、分散秘密情報復元装置２０２は、分散秘密情報分散装置１０２の分散符号化方法に対応する復元方法を用い、復元計算を行い、分散秘密情報用データ集合ＢＳの元ｃを復元し、出力する（ステップＳ２６）。【０１１０】
次に、復元装置２００は、不正検出装置２０３に、多項式用データ集合Ｖの元ｆ、分散秘密情報用データ集合ＢＳの元ｃおよび固定値ｔを入力し（ステップＳ２７）、ｆ（ｔ）＝ｃを満たすか否かをチェックする（ステップＳ２８）。ｆ（ｔ）＝ｃが成立していれば（ステップＳ２８のＹＥＳ分岐）、不正検出装置２０３は、ｆ（０）とｆとを出力し（ステップＳ２９）、ｆ（ｔ）＝ｃが成立していない場合（ステップＳ２８のＮＯ分岐）、不正の検出を表す記号を出力して（ステップＳ３０）、処理を終了する。【０１１１】
次に、復元結果検証装置４００の動作について説明する。図８は、本実施の形態における復元結果検証装置４００の動作を示すフローチャートである。【０１１２】
最初に、復元結果検証装置４００に、多項式用データ集合Ｖの元ｆが入力される（ステップＳ３１）。【０１１３】
次に、復元結果検証装置４００は、１機の記憶装置３００が記憶するデータを読み出す（ステップＳ３２）。例えば、復元結果検証装置４００は、第１乱数記憶装置３０１が記憶する第１乱数用データ集合ＲＡの元ｒと、分散秘密情報記憶装置３０２が記憶する分散秘密情報用データ集合ＢＳの元Ｖｒとを読み出す。【０１１４】
次に、復元結果検証装置４００は、データを読み出した記憶装置３００の第１乱数記憶装置３０１に記憶されていたデータｒと、データを読み出した記憶装置３００の分散秘密情報記憶装置３０２に記憶されていたデータＶｒが、ｆ（ｒ）＝Ｖｒを満たしているかチェックする（ステップＳ３３）。ｆ（ｒ）＝Ｖｒが成立していれば（ステップＳ３３のＹＥＳ分岐）、復元結果検証装置４００は、ｆ（０）を出力し（ステップＳ３４）、ｆ（ｒ）＝Ｖｒが成立していない場合（ステップＳ３３のＮＯ分岐）、不正の検出を表す記号を出力して（ステップＳ３５）、処理を終了する。【０１１５】
ここで、既存の方式に比べ、本発明の実施の形態の方が、より効率的である根拠を説明する。秘密情報は、０，・・・，ｐ−１のうちいずれかの値であるものとする。非特許文献３に記載された方式は、第１に、秘密情報を定数項に持つｍｏｄ  ｑ（ｑ＞ｐ）上のｋ−１次多項式ｆを生成し、第２に、分散情報ごとにランダムな値を割り振り（ｒ１，・・・，ｒｎとする）、第３に、（ｒ１，ｆ（ｒ１）），・・・，（ｒｎ，ｆ（ｒｎ））を分散情報とする方式である。非特許文献３に記載された方式では、ｋ個以上の分散情報よりｆを復元し、ｆの定数項が、０，・・・，ｐ−１のうちのいずれかであれば、不正はなかったものとする。【０１１６】
非特許文献３に記載された方式において、（ｒ１，ｆ（ｒ１）），・・・，（ｒｎ−１，ｆ（ｒｎ−１））を知っている不正者たちが、（ｒｎ，ｆ（ｒｎ））を持っている人をだまそうとしている（不正者たちは、（ｒｎ，ｆ（ｒｎ））がわからない）状況を考える。【０１１７】
ここで、不正者たちが、
（ｒ１，ｆ（ｒ１）），・・・，（ｒｋ−１，ｆ（ｒｋ−１））を、
（ｒ１’，ｆ１’），・・・，（ｒｋ−１’，ｆｋ−１’）
に改竄して復元装置に入力した場合を考える。
（ｒ１’，ｆ１’），・・・，（ｒｋ−１’，ｆｋ−１’），（ｒｎ，ｆ（ｒｎ））より復元された多項式の定数項が、分散された秘密情報以外の０，・・・，ｐ−１のいずれかであれば、不正は成功である。【０１１８】
ある秘密情報と異なる０，・・・，ｐ−１のいずれかの値をｓ’とし、（ｒ１’，ｆ１’），・・・，（ｒｋ−１’，ｆｋ−１’），（０，ｓ’）より復元された多項式をｆ’とする。ｆ’は、ｆとは異なるｋ−１次多項式であるので、ｆとｆ’との交点は、高々ｋ−１点である。（ｒｎ，ｆ（ｒｎ））がこのｆ’上の点であれば、（ｒｎ，ｆ（ｒｎ））を持っている人が、（ｒ１’，ｆ１’），・・・，（ｒｋ−１’，ｆｋ−１’），（ｒｎ，ｆ（ｒｎ））を用いて秘密情報を復元すると、ｓ’が復元される。【０１１９】
本来の秘密情報以外の値はｐ−１種類あり、それぞれの値についてｆ’が定まるので、ｐ−１種類のｆ’が定まる。不正者は、すべてのｆ’とｆとの交点がすべて異なるように（ｒ１’，ｆ１’），・・・，（ｒｋ−１’，ｆｋ−１’）を生成すると、ｒｎが（ｐ−１）（ｋ−１）通りの値のうちのどれかである場合に、不正は成功してしまう。【０１２０】
ｒｎが０，・・・，Ｒから選ばれるものとすると、ｒｎが一様にランダムに選ばれているとき、（ｐ−１）（ｋ−１）／Ｒが不正の成功する確率である。つまり、この値が十分小さくなるような大きなＲを選ばなくてはならない。不正の成功率をε程度にしたい場合、Ｒを（（ｐ−１）（ｋ−１））／ε程度に設定する必要がある。【０１２１】
Ｒを（（ｐ−１）（ｋ−１））／ε以上に設定するためには、ｑを（（ｐ−１）（ｋ−１））／ε以上に設定する必要がある。ここで、ｒｎとｆ（ｒｎ）が分散情報であって、ｒｎおよびｆ（ｒｎ）のサイズはそれぞれｑである。したがって、分散情報のサイズは、（（ｐ−１）（ｋ−１）／ε）２となる。【０１２２】
これに対して、本発明の実施の形態では、乱数の一方を定数にした方式は、
第１に、秘密情報を定数項に持つＧＦ（ｐ）上のｋ−１次多項式ｆを生成し、
第２に、分散情報ごとにランダムな値を割り振り（ｒ１，・・・，ｒｎとし、ｔとは異なるものとする）、
第３に、ｆ（ｔ）を定数項としたＧＦ（ｐ）上のｋ−１次多項式ｇを生成し、
第４に、（ｒ１，ｆ（ｒ１），ｇ（１）），・・・，（ｒｎ，ｆ（ｒｎ），ｇ（ｎ））を分散情報とする方式である。この方式は、ｋ個以上の分散情報よりｆとｇとを復元し、ｆ（ｔ）＝ｇ（０）を満たすかをチェックし、満たされていれば不正はなかったものとする。【０１２３】
この方式において、（ｒ１，ｆ（ｒ１），ｇ（１）），・・・，（ｒｎ−１，ｆ（ｒｎ−１），ｇ（ｎ−１））を知っている不正者たちが、（ｒｎ，ｆ（ｒｎ），ｇ（ｎ））を持っている人をだまそうとしている状況を考える。ｇ不正者たちは、ｒｎ，ｆ（ｒｎ）はわからないが、ｇ（１），・・・，ｇ（ｋ）などからｇが得られ、ｇへの入力もわかっているため、ｇ（ｎ）はわかっている。【０１２４】
不正者たちが、
（ｒｉ＿１，ｆ（ｒｉ＿１），ｇ（ｉ１）），・・・，（ｒｉ＿（ｋ−１），ｆ（ｒｉ＿（ｋ−１）），ｇ（ｉｋ−１））を、
（ｒｉ＿１’，ｆｉ＿１’，ｇｉ＿１’），・・・，（ｒｉ＿（ｋ−１）’，ｆｉ＿（ｋ−１）’，ｇｉ＿（ｋ−１）’）
に改ざんして復元装置に入力した場合を考える。【０１２５】
（ｒｉ＿１’，ｆｉ＿１’），・・・，（ｒｉ＿（ｋ−１）’，ｆｉ＿（ｋ−１）’），（ｒｎ，ｆ（ｒｎ））よりｆ’を復元し、
（ｉ１，ｇ（ｉ１）’），・・・，（ｉｋ−１，ｇ（ｉｋ−１）’），（ｎ，ｇ（ｎ））よりｇ’を復元し、
ｆ’（ｔ）＝ｇ’（０）であれば不正は成功である。【０１２６】
このチェックは、
（ｒｉ＿１’，ｆｉ＿１’），・・・，（ｒｉ＿（ｋ−１）’，ｆｉ＿（ｋ−１）’），（ｔ，ｇ’（０）），（ｒｎ，ｆ（ｒｎ））がすべて同じ多項式上の点であるか否かをチェックしているに他ならない。
ｆ’は、（ｒｉ＿１’，ｆｉ＿１’），・・・，（ｒｉ＿（ｋ−１）’，ｆｉ＿（ｋ−１）’），（ｔ，ｇ’（０））から復元される１種類の多項式とみなすことができる。また、ｆ’（０）は、秘密情報ｆ（０）と異なる値なので、ｆ（０）とｆ（０）’とは異なる。よって、ｆとｆ’とは、常に違う多項式である。そのため、ｆとｆ’とは、高々ｋ−１点しか交点を持たない。よって、ｒｎが０，・・・，Ｒから選ばれるものとすると、（ｋ−１）／Ｒが不正の成功する確率となる。【０１２７】
ε＝（ｋ−１）／Ｒとすると、（ｒｉ，ｆ（ｒｉ），ｇ（ｉ））が分散情報であって、ｒｉのサイズがＲであり、ｆ（ｒｉ）およびｇ（ｉ）のサイズがｐであることから、分散情報のサイズは、おおよそｐ２／εとなる。よって、本発明の実施の形態では、従来と比較して、εだけ分散情報のサイズを小さくすることができる。【０１２８】
不正者が閾値数個以上の分散情報を持っていても不正の検出が可能可能な既存の方式では、１つの多項式を用いた方式が知られていた。この方式では、一つの多項式で秘密の分散と不正の検出の機能をまかなうため、非常に大きい有限体を用意する必要があった。本発明の一実施の形態では、秘密情報に関する２つの多項式を用意し、お互いをチェックしあう方法を採用して、それぞれ有限体のサイズを抑え、既存の方式に比べて分散情報のサイズの小さな方式を構成している。なお、本発明の一実施の形態の方式を用いれば、自身が復元処理に参加しなかった場合でも、復元処理結果を検証することもできる。【０１２９】
なお、本実施の形態では、（ｋ，ｎ）閾値法を例示して説明したが、線形秘密分散法であれば、（ｋ，ｎ）閾値法に限られない。
【実施例１】
【０１３０】
以下、図２、図３、図４を参照して、本の第１の実施例について説明する。
以下、秘密情報分散装置１０１が、定数項が秘密情報ｓである（ｋ−１）次多項式を生成する場合について説明する。実施例１では、前記実施の形態における秘密情報のデータ集合にＧＦ（ｐ）を用いる。【０１３１】
ＧＦ（ｐ）は、素数または素数のべき乗ｐに対する有限体であり、有限体上の加算を＋、減算を−、除算を／、べき乗算を＾で表す。なお、閾値ｋ、分散情報数ｎおよび素数または素数のべき乗ｐは、ｋ≦ｎ≦ｐ−１を満足するものとする。また、固定値ｔとして、０≦ｔ≦ｐ−１を満たす値を用いる。【０１３２】
なお、秘密情報分散装置１０１および分散秘密情報分散装置１０２が、非特許文献１記載の（ｋ，ｎ）閾値法を用いて、秘密情報を分散符号化する場合を例にして説明する。また、多項式復元装置２０１および分散秘密情報復元装置２０２が、非特許文献１記載の（ｋ，ｎ）閾値法を用いて、秘密情報を復元する場合を例にして説明する。【０１３３】
まず、分散情報生成装置１００の第１の実施例について説明する。【０１３４】
分散情報生成装置１００には、閾値ｋ、分散情報数ｎおよび秘密情報ｓが入力される。【０１３５】
はじめに、分散情報生成装置１００は、秘密情報分散装置１０１に、閾値ｋ、分散情報数ｎ、秘密情報ｓおよび固定値ｔを入力する。【０１３６】
秘密情報分散装置１０１は、ｔと異なり且つ互いに異なるｒ１，ｒ２，・・・，ｒｎを、１，２，・・・，Ｒ１（Ｒ１≦ｐ−１）からランダムに選び、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の第１乱数記憶装置３０１−ｉにｒｉを記憶させる。例えば、
記憶装置３００−１の第１乱数記憶装置３０１−１にｒ１を記憶させ、
記憶装置３００−２の第１乱数記憶装置３０１−２にｒ２を記憶させ、
記憶装置３００−ｎの第１乱数記憶装置３０１−ｎにｒｎを記憶させる。そして、ＧＦ（ｐ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。これを、ｆ１（ｘ）と記す。なお、ｆ１（ｘ）は、本発明の実施の形態における多項式ｆに相当する。【０１３７】
秘密情報分散装置１０１は、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の分散秘密情報記憶装置３０２−ｉにｆ１（ｒｉ）を記憶させる。例えば、
記憶装置３００−１の分散秘密情報記憶装置３０２−１にｆ１（ｒ１）を記憶させ、
記憶装置３００−２の分散秘密情報記憶装置３０２−２にｆ１（ｒ２）を記憶させ、
記憶装置３００−ｎの分散秘密情報記憶装置３０２−ｎにｆ１（ｒｎ）を記憶させる。また、秘密情報分散装置１０１は、ｃ＝ｆ１（ｔ）を出力する。【０１３８】
次に、分散情報生成装置１００は、分散秘密情報分散装置１０２に、閾値ｋ、分散情報数ｎおよび秘密情報分散装置１０１の出力ｃを入力する。【０１３９】
分散秘密情報分散装置１０２は、互いに異なるｘ１，ｘ２，・・・，ｘｎを、１，２，・・・，Ｒ２（Ｒ２≦ｐ−１）からランダムに選び、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の第２乱数記憶装置３０３−ｉにｘｉを記憶させる。例えば、
記憶装置３００−１の第２乱数記憶装置３０３−１にｘ１を記憶させ、
記憶装置３００−２の第２乱数記憶装置３０３−２にｘ２を記憶させ、
記憶装置３００−ｎの第２乱数記憶装置３０３−ｎにｘｎを記憶させる。秘密情報分散装置１０２は、ＧＦ（ｐ）上の定数項がｃであるｋ−１次多項式をランダムに生成する。これを、ｆ２（ｘ）と記す。なお、ｆ２（ｘ）は、前記実施の形態における多項式ｇに相当する。【０１４０】
秘密情報分散装置１０２は、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の分散分散秘密情報記憶装置３０４−ｉにｆ２（ｘｉ）を記憶させる。
例えば、記憶装置３００−１の分散分散秘密情報記憶装置３０４−１にｆ２（ｘ１）を記憶させ、
記憶装置３００−２の分散分散秘密情報記憶装置３０４−２にｆ２（ｘ２）を記憶させ、
記憶装置３００−ｎの分散分散秘密情報記憶装置３０４−ｎにｆ２（ｘｎ）を記憶させる。【０１４１】
次に、復元装置２００の実施例について説明する。【０１４２】
復元装置２００には、閾値ｋおよび固定値ｔが入力される。復元装置２００は、多項式復元装置２０１に閾値ｋを入力する。【０１４３】
多項式復元装置２０１は、記憶装置３００−１〜３００−ｎのうちのｋ機の記憶装置３００−ｊ１，記憶装置３００−ｊ２，・・・，記憶装置３００−ｊｋから、それぞれの分散秘密情報記憶装置３０２−ｊ１，３０２−ｊ２，・・・，３０２−ｊｋが記憶する値を読み出す。ここで、分散秘密情報記憶装置３０２−ｊ１，３０２−ｊ２，・・・，３０２−ｊｋが記憶する値を、それぞれｂｓ１ｊ＿１，ｂｓ１ｊ＿２，・・・，ｂｓ１ｊ＿ｋと記す。【０１４４】
次に、多項式復元装置２０１は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの第１乱数記憶装置３０１−ｊ１，３０１−ｊ２，・・・，３０１−ｊｋの記憶する値を読み出す。ここで、第１乱数記憶装置３０１−ｊ１，３０１−ｊ２，・・・，３０１−ｊｋが記憶する値を、それぞれｒｊ＿１，ｒｊ＿２，・・・，ｒｊ＿ｋと記す。【０１４５】
次に、多項式復元装置２０１は、座標（ｒｊ＿１，ｂｓ１ｊ＿１），（ｒｊ＿２，ｂｓ１ｊ＿２），・・・，（ｒｊ＿ｋ，ｂｓ１ｊ＿ｋ）を通るＧＦ（ｐ）上のｋ−１次の多項式ｇｓ＿１（ｘ）を出力する。具体的には、連立方程式を解くなどの方法によりｇｓ＿１（ｘ）を計算する。なお、ｇｓ＿１（ｘ）は、実施の形態における多項式用データ集合Ｖの元ｆまたは多項式ｆ’に相当する。【０１４６】
次に、復元装置２００は、分散秘密情報復元装置２０２に閾値ｋを入力する。【０１４７】
分散秘密情報復元装置２０２は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの分散分散秘密情報記憶装置３０４−ｊ１，３０４−ｊ２，・・・，３０４−ｊｋが記憶する値を読み出す。ここで、分散分散秘密情報記憶装置３０４−ｊ１，３０４−ｊ２，・・・，３０４−ｊｋが記憶する値を、それぞれｂｓ２ｊ＿１，ｂｓ２ｊ＿２，・・・，ｂｓ２ｊ＿ｋと記す。【０１４８】
次に、分散秘密情報復元装置２０２は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの第２乱数記憶装置３０３−ｊ１，３０３−ｊ２，・・・，３０３−ｊｋが記憶する値を読み出す。ここで、第２乱数記憶装置３０３−ｊ１，３０３−ｊ２，・・・，３０３−ｊｋが記憶する値を、それぞれｘｊ＿１，ｘｊ＿２，・・・，ｘｊ＿ｋと記す。【０１４９】
次に、分散秘密情報復元装置２０２は、座標（ｘｊ＿１，ｂｓ２ｊ＿１），（ｘｊ＿２，ｂｓ２ｊ２），・・・，（ｘｊ＿ｋ，ｂｓ２ｊ＿ｋ）を通るＧＦ（ｐ）上のｋ−１次の多項式ｇｓ＿２（ｘ）の、ｇｓ＿２（０）を出力する。具体的には、連立方程式を解く、ラグランジュ補間を用いるなどの方法によりｇｓ＿２（０）を計算する。なお、ｇｓ＿２（ｘ）は、実施の形態における多項式ｇまたはｇ’に相当する。【０１５０】
次に、復元装置２００は、不正検出装置２０３に、ｇｓ＿１（ｘ）およびｇｓ＿２（０）を入力する。不正検出装置２０３は、ｇｓ＿１（ｔ）＝ｇｓ＿２（０）を満足するかをチェックする。満足している場合、ｇｓ＿１（０）およびｇｓ＿１（ｘ）を出力する。満足していない場合、不正を検知したことを示す記号として⊥を出力する。【０１５１】
次に、復元結果検証装置４００の実施例について説明する。【０１５２】
復元結果検証装置４００には、ＧＦ（ｐ）上のｋ−１次の多項式ｇ（ｘ）が入力される。ここで、多項式ｇ（ｘ）は、例えば、ある復元処理における出力である。【０１５３】
復元結果検証装置４００は、記憶装置３００−ｉより、第１乱数記憶装置３０１−ｉの記憶する値ｒと、分散秘密情報記憶装置３０２−ｉが記憶する値Ｖｒを読み出す。次に、ｇ（ｒ）＝Ｖｒを満たすかチェックし、満たしている場合、ｇ（０）を出力し、満たしていない場合、不正の検出を表す記号を出力する。なお、記憶装置３００−ｉは、例えば、記憶装置３００−１〜３００−ｎのうち、復元処理に用いられなかった分散情報が記憶されている１台の記憶装置である。【０１５４】
実施例１において、不正者が知る記憶装置３００が記憶するデータの数をａ、秘密情報のサイズをｐとすると、分散情報のサイズはｐ２×Ｒ１×Ｒ２になり、不正の検出率は１−（ｋ−１）／（Ｒ１−ａ）になる。【０１５５】
秘密情報のサイズをｓ、不正の検出率を（１−ε）と記すと、分散情報のサイズは、ｓ２×（（ｋ−１）／ε＋ｔ）×Ｒ２と表すことができる。【０１５６】
非特許文献３に記載された方式の分散情報のサイズは、（（ｓ−１）（ｋ−１）／ε＋ｋ）２である。ｋ＝２、ｔ＝２、ｐ＝２８０、ε＝１／２８０、Ｒ２＝２１０として、比較する。【０１５７】
実施例１における分散情報のサイズは、およそ、２２５０であって、非特許文献１に記載された方式の分散情報のサイズは、およそ、２３２０である。実施例１における分散情報のサイズが、非特許文献１に記載された方式に比べ、分散情報のサイズが小さいことがわかる。【０１５８】
また、運用の形態によっては、自身が参加していない復元処理結果の検証を必要としないケースも考えられる。この場合、復元結果検証装置４００と、復元装置２００の出力する多項式ｆを取り除くことで、自身が参加している復元処理の中に不正なシェアがなかったかどうかを判定するための秘密情報分散システムを構成できる。また、Ｒ２のサイズは安全性には関係しない。そこで、運用の形態によっては記憶装置に振られたＩＤ番号を用いることができ、その場合、Ｒ２の分の分散情報のサイズを小さくできる。
【実施例２】
【０１５９】
以下、図２、図３、図４を参照して、本実施の形態の第２の実施例について説明する。以下、秘密情報分散装置１０１が、秘密情報ｓを定数項からＬ−１次までの係数を連結した値に埋め込んだ（ｋ−１）次多項式を生成する場合について説明する。実施例２では、実施の形態における秘密情報のデータ集合にＧＦ（ｐＬ）を用いる。【０１６０】
ＧＦ（ｐＬ）は、素数または素数のべき乗ｐＬに対する有限体であり、有限体上の加算を＋、減算を−、除算を／、べき乗算を＾で表す。ＧＦ（ｐＬ）の要素ｓは、ＧＦ（ｐ）の要素のＬ個組で、（ｓ０，ｓ１，ｓ２，・・・，ｓＬ−１）とあらわすことができる。
なお、閾値ｋ、分散情報数ｎおよび素数または素数のべき乗ｐは、ｋ≦ｎ≦ｐ−１を満足するものとする。また、固定値ｔとして、０≦ｔ≦ｐ−１を満たす値を用いる。【０１６１】
なお、秘密情報分散装置１０１および分散秘密情報分散装置１０２が、非特許文献１，２記載の（ｋ，ｎ）閾値法を用いて、秘密情報を分散符号化する場合を例にして説明する。また、多項式復元装置２０１および分散秘密情報復元装置２０２が、非特許文献１，２記載の（ｋ，ｎ）閾値法を用いて、秘密情報を復元する場合を例にして説明する。【０１６２】
まず、分散情報生成装置１００の第２の実施例について説明する。【０１６３】
分散情報生成装置１００には、閾値ｋ、分散情報数ｎおよび秘密情報ｓが入力される。【０１６４】
はじめに、分散情報生成装置１００は、秘密情報分散装置１０１に、閾値ｋ、分散情報数ｎ、秘密情報ｓおよび固定値ｔを入力する。ここで、秘密情報分散装置１０１は、ｋ−１以下であるパラメータＬを入力してもよい。【０１６５】
秘密情報分散装置１０１は、ｔと異なり且つ互いに異なるｒ１，ｒ２，・・・，ｒｎを、１，２，・・・，Ｒ１（Ｒ１≦ｐ−１）からランダムに選び、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の第１乱数記憶装置３０１−ｉにｒｉを記憶させる。例えば、記憶装置３００−１の第１乱数記憶装置３０１−１にｒ１を記憶させ、記憶装置３００−２の第１乱数記憶装置３０１−２にｒ２を記憶させ、記憶装置３００−ｎの第１乱数記憶装置３０１−ｎにｒｎを記憶させる。そして、ｓを（ｓ０，・・・，ｓＬ−１）として、ＧＦ（ｐ）上の多項式の係数に以下のように埋め込んだｋ−１次多項式ｆ１をランダムに生成する。【０１６６】
ｆ１（ｘ）＝ｓ０＋ｓ１×ｘ＋・・・＋ｓＬ−１×ｘ（Ｌ−１）＋ａＬ×ｘＬ＋・・・＋ａｋ−１×ｘ（ｋ−１）・・・式（１）【０１６７】
式（１）を、ｆ１（ｘ）と記す。【０１６８】
秘密情報分散装置１０１は、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の分散秘密情報記憶装置３０２−ｉにｆ１（ｒｉ）を記憶させる。例えば、記憶装置３００−１の分散秘密情報記憶装置３０２−１にｆ１（ｒ１）を記憶させ、記憶装置３００−２の分散秘密情報記憶装置３０２−２にｆ１（ｒ２）を記憶させ、記憶装置３００−ｎの分散秘密情報記憶装置３０２−ｎにｆ１（ｒｎ）を記憶させる。また、秘密情報分散装置１０１は、ｃ＝ｆ１（ｔ）を出力する。【０１６９】
次に、分散情報生成装置１００は、分散秘密情報分散装置１０２に、閾値ｋ、分散情報数ｎおよび秘密情報分散装置１０１の出力ｃを入力する。【０１７０】
分散秘密情報分散装置１０２は、互いに異なるｘ１，ｘ２，・・・，ｘｎを、１，２，・・・，Ｒ２（Ｒ２≦ｐ−１）からランダムに選び、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の第２乱数記憶装置３０３−ｉにｘｉを記憶させる。例えば、記憶装置３００−１の第２乱数記憶装置３０３−１にｘ１を記憶させ、記憶装置３００−２の第２乱数記憶装置３０３−２にｘ２を記憶させ、記憶装置３００−ｎの第２乱数記憶装置３０３−ｎにｘｎを記憶させる。【０１７１】
第２秘密情報分散装置１０２は、ＧＦ（ｐ）上の定数項がｃであるｋ−１次多項式をランダムに生成する。これを、ｆ２（ｘ）と記す。そして、第２秘密情報分散装置１０２は、記憶装置３００−ｉ（ｉ＝１，・・・，ｎ）の分散分散秘密情報記憶装置３０４−ｉにｆ２（ｘｉ）を記憶させる。例えば、
記憶装置３００−１の分散分散秘密情報記憶装置３０４−１にｆ２（ｘ１）を記憶させ、
記憶装置３００−２の分散分散秘密情報記憶装置３０４−２にｆ２（ｘ２）を記憶させ、
記憶装置３００−ｎの分散分散秘密情報記憶装置３０４−ｎにｆ２（ｘｎ）を記憶させる。【０１７２】
次に、復元装置２００の実施例について説明する。【０１７３】
復元装置２００には、閾値ｋおよび固定値ｔが入力される。復元装置２００は、多項式復元装置２０１に閾値ｋを入力する。【０１７４】
多項式復元装置２０１は、記憶装置３００−１〜３００−ｎのうちのｋ機の記憶装置３０１−ｊ１，記憶装置３０１−ｊ２，・・・，記憶装置３００−ｊｋから、それぞれの分散秘密情報記憶装置３０２−ｊ１，３０２−ｊ２，・・・，３０２−ｊｋが記憶する値を読み出す。ここで、分散秘密情報記憶装置３０２−ｊ１，３０２−ｊ２，・・・，３０２−ｊｋが記憶する値を、ｂｓ１ｊ＿１，ｂｓ１ｊ＿２，・・・，ｂｓ１ｊ＿ｋと記す。【０１７５】
次に、多項式復元装置２０１は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの第１乱数記憶装置３０１−ｊ１，３０１−ｊ２，・・・，３０１−ｊｋの記憶する値を読み出す。ここで、第１乱数記憶装置３０１−ｊ１，３０１−ｊ２，・・・，３０１−ｊｋが記憶する値を、それぞれｒｊ＿１，ｒｊ＿２，・・・，ｒｊ＿ｋと記す。【０１７６】
次に、多項式復元装置２０１は、座標（ｒｊ＿１，ｂｓ１ｊ＿１），（ｒｊ＿２，ｂｓ１ｊ＿２），・・・，（ｒｊ＿ｋ，ｂｓ１ｊ＿ｋ）を通るＧＦ（ｐ）上のｋ−１次の多項式ｇｓ＿１（ｘ）を出力する。具体的には、連立方程式を解くなどの方法によりｇｓ＿１（ｘ）を計算する。【０１７７】
次に、復元装置２００は、分散秘密情報復元装置２０２に閾値ｋを入力する。【０１７８】
分散秘密情報復元装置２０２は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの分散分散秘密情報記憶装置３０４−ｊ１，３０４−ｊ２，・・・，３０４−ｊｋが記憶する値を読み出す。ここで、分散分散秘密情報記憶装置３０４−ｊ１，３０４−ｊ２，・・・，３０４−ｊｋが記憶する値を、それぞれｂｓ２ｊ＿１，ｂｓ２ｊ＿２，・・・，ｂｓ２ｊ＿ｋと記す。【０１７９】
次に、分散秘密情報復元装置２０２は、記憶装置３００−ｊ１，３００−ｊ２，・・・，３００−ｊｋから、それぞれの第２乱数記憶装置３０３−ｊ１，３０３−ｊ２，・・・，３０３−ｊｋが記憶する値を読み出す。ここで、第２乱数記憶装置３０３−ｊ１，３０３−ｊ２，・・・，３０３−ｊｋが記憶する値を、それぞれｘｊ＿１，ｘｊ＿２，・・・，ｘｊ＿ｋと記す。【０１８０】
次に、分散秘密情報復元装置２０２は、座標（ｘｊ＿１，ｂｓ２ｊ＿１），（ｘｊ＿２，ｂｓ２ｊ＿２），・・・，（ｘｊ＿ｋ，ｂｓ２ｊ＿ｋ）を通るＧＦ（ｐ）上のｋ−１次の多項式ｇｓ＿２（ｘ）の、ｇｓ＿２（０）を出力する。具体的には、連立方程式を解く、ラグランジュ補間を用いるなどの方法によりｇｓ＿２（０）を計算する。【０１８１】
次に、復元装置２００は、不正検知装置２０３に、ｇｓ＿１（ｘ）およびｇｓ＿２（０）を入力する。不正検出装置２０３は、ｇｓ＿１（ｔ）＝ｇｓ＿２（０）を満足するかをチェックする。満足している場合、ｇｓ＿１の定数項からＬ−１次の項までの係数（ｓ０，・・・，ｓＬ−１）と、ｇｓ＿１（ｘ）とを出力する。満足していない場合、不正を検知したことを示す記号として⊥を出力する。【０１８２】
次に、復元結果検証装置４００の実施例について説明する。【０１８３】
復元結果検証装置４００には、ＧＦ（ｐ）上のｋ−１次の多項式ｇ（ｘ）が入力される。ここで、多項式ｇ（ｘ）は、例えば、ある復元処理における出力である。【０１８４】
復元結果検証装置４００は、記憶装置３００−ｉより、第１乱数記憶装置３０１−ｉの記憶する値ｒと、分散秘密情報記憶装置３０２−ｉの記憶する値Ｖｒを読み出す。次に、ｇ（ｒ）＝Ｖｒを満たすかチェックし、満たしている場合、ｇの定数項からＬ−１次の項までの係数（ｓ０，・・・，ｓＬ−１）を出力し、満たしていない場合、不正の検出を表す記号を出力する。【０１８５】
実施例２において、不正者が知る記憶装置３００が記憶するデータの数をａ、秘密情報のサイズをｐＬとすると、分散情報のサイズはｐ２×Ｒ１×Ｒ２になり、不正の検出率は１−（ｋ−１）／（Ｒ１−ａ）になる。【０１８６】
ｋ＝２、ｔ＝２、ｐ＝２８０、ε＝１／２８０、Ｒ２＝２１０とすると、実施例１における分散情報のサイズは、およそ、２２５０である。【０１８７】
実施例２において、ｋ＝２、ｔ＝２、ｐ＝２１６０、ε＝１／２８０、Ｒ２＝２１０，Ｌ＝２とすると、およそ、２２５０である。実施例１および非特許文献１に記載された方式に比べ、分散情報のサイズが小さいことがわかる。【０１８８】
しかし、閾値に満たない分散情報から秘密情報に関する情報が漏れるという性質がある。実施例２においても、運用の形態によっては、自身が参加していない復元処理結果の検証を必要としないケースも考えられる。この場合、復元結果検証装置４００と、復元装置２００の出力する多項式ｆを取り除くことで、自身が参加している復元処理の中に不正なシェアがなかったかどうかを判定するための秘密情報分散システムを構成できる。また、Ｒ２のサイズは安全性には関係しない。そこで、運用の形態によっては記憶装置に振られたＩＤ番号を用いることができ、その場合、Ｒ２の分の分散情報のサイズを小さくすることができる。
【産業上の利用可能性】
【０１８９】
秘密鍵などの機密情報の分散管理に利用できる。例えば、個人のコンピュータで作成した分散情報の一部をサーバなどにアップロードし、一部をＵＳＢメモリに入れて持ち歩く状況を考える。サーバの情報だけが盗難されても、ＵＳＢメモリに入った情報だけが盗難されても、一切秘密鍵に関する情報を漏洩しないように分散することができるので、機密情報を安全に管理しながら利用することができる。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。
【図１】
2008093690.tif 000003
【図２】
2008093690.tif 000004
【図３】
2008093690.tif 000005
【図４】
2008093690.tif 000006
【図５】
2008093690.tif 000007
【図６】
2008093690.tif 000008
【図７】
2008093690.tif 000009
【図８】
2008093690.tif 000010
【手続補正書】
【提出日】平成20年11月28日(2008.11.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
秘密情報を分散する分散情報生成装置であって、
秘密情報分散装置と、
分散秘密情報分散装置と、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力手段とを備え、
前記秘密情報分散装置は、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成装置と、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成装置と、多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力装置とを含み、
前記分散秘密情報分散装置は、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成装置と、
前記分散情報出力装置の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成装置と、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力装置とを含む  ことを特徴とする分散情報生成装置。
【請求項２】
前記分散入力手段は、ｋ−１以下のパラメータＬを入力し、
前記第１分散多項式生成装置は、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記第２分散多項式生成装置は、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する
請求項１記載の分散情報生成装置。
【請求項３】
前記第１分散多項式生成装置は、前記パラメータＬが１の場合に、秘密情報ｓを定数項にだけ埋め込んで多項式Ｆを生成する請求項２記載の分散情報生成装置。
【請求項４】
前記第１乱数生成装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、前記第２乱数生成装置は、第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項１から請求項３のうちのいずれか１項に記載の分散情報生成装置。
【請求項５】
前記第１乱数生成装置が出力した第１の乱数と、前記分散情報出力装置が出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成装置が出力した第２の乱数と、前記分散分散情報出力装置が出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えた請求項１から請求項４のうちのいずれか１項に記載の分散情報生成装置。
【請求項６】
（削除）
【請求項７】
（削除）
【請求項８】
（削除）
【請求項９】
（削除）
【請求項１０】
（削除）
【請求項１１】
秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、
前記復元装置が出力した（ｋ−１）次多項式ｆを入力し、請求項１から請求項５のうちのいずれか１項に記載の分散情報生成装置の出力を格納する記憶装置から、請求項１から請求項５のうちのいずれか１項に記載の秘密情報分散装置が出力した第１の乱数ｒと、請求項１から請求項５のうちのいずれか１項に記載の秘密情報分散装置が生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証装置。
【請求項１２】
（削除）
【請求項１３】
（削除）
【請求項１４】
秘密情報を分散する分散情報生成方法であって、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力ステップと、
秘密情報分散ステップと、
分散秘密情報分散ステップとを含み、
前記秘密情報分散ステップは、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成ステップと、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成ステップと、
多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力ステップとを有し、
前記分散秘密情報分散ステップは、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成ステップと、
前記分散情報出力ステップの出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成ステップと、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力ステップとを有する
ことを特徴とする分散情報生成方法。
【請求項１５】
前記分散入力ステップで、ｋ−１以下のパラメータＬを入力し、
前記第１分散多項式生成ステップで、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記第２分散多項式生成ステップで、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する
請求項１４記載の分散情報生成方法。
【請求項１６】
前記第１分散多項式生成ステップで、前記パラメータＬが１の場合に、秘密情報ｓを定数項にだけ埋め込んで多項式Ｆを生成する請求項１５記載の分散情報生成方法。
【請求項１７】
前記第１乱数生成ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、前記第２乱数生成ステップで、第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項１４から請求項１６のうちのいずれか１項に記載の分散情報生成方法。
【請求項１８】
前記第１乱数生成ステップで出力した第１の乱数と、分散情報出力ステップで出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成ステップで出力した第２の乱数と、前記分散分散情報出力ステップで出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる請求項１４から請求項１７のうちのいずれか１項に記載の分散情報生成方法。
【請求項１９】
（削除）
【請求項２０】
（削除）
【請求項２１】
（削除）
【請求項２２】
（削除）
【請求項２３】
（削除）
【請求項２４】
復元された秘密情報を検証するための復元結果検証方法であって、
復元された秘密情報として（ｋ−１）次多項式ｆを入力し、請求項１４から請求項１８のうちのいずれか１項に記載の分散情報生成方法で出力した内容を格納する記憶装置から、請求項１４から請求項１８のうちのいずれか１項に記載の秘密情報分散ステップで出力した第１の乱数ｒと、請求項１４から請求項１８のうちのいずれか１項に記載の秘密情報分散ステップで生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証方法。
【請求項２５】
（削除）
【請求項２６】
（削除）
【請求項２７】
秘密情報を分散するための分散情報生成プログラムであって、
コンピュータに、
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力処理と、
秘密情報分散処理と、
分散秘密情報分散処理とを実行させ、
前記秘密情報分散処理で、
固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成処理と、
秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成処理と、
多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力処理とを実行させ、
前記分散秘密情報分散処理で、
互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成処理と、
前記分散情報出力処理の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成処理と、
多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力処理とを実行させる
ための分散情報生成プログラム。
【請求項２８】
コンピュータに、
前記分散入力処理で、ｋ−１以下のパラメータＬを入力する処理を実行させ、
前記第１分散多項式生成処理で、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成する処理を実行させ、
前記第２分散多項式生成処理で、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する処理を実行させる
請求項２７記載の分散情報生成プログラム。
【請求項２９】
コンピュータに、
前記第１分散多項式生成処理で、前記パラメータＬが１の場合に、秘密情報ｓを定数項にだけ埋め込んで多項式Ｆを生成する処理を実行させる
請求項２８記載の分散情報生成プログラム。
【請求項３０】
コンピュータに、
前記第１乱数生成処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する処理を実行させ、または、前記第２乱数生成処理で、第２の乱数として、互いに異なるｎ個の定数を生成して出力する処理を実行させる
請求項２７から請求項２９のうちのいずれか１項に記載の分散情報生成プログラム。
【請求項３１】
コンピュータに、
前記第１乱数生成処理で出力した第１の乱数と、分散情報出力処理で出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成処理で出力した第２の乱数と、前記分散分散情報出力処理で出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる処理を実行させる
請求項２７から請求項３０のうちのいずれか１項に記載の分散情報生成プログラム。
【請求項３２】
（削除）
【請求項３３】
（削除）
【請求項３４】
（削除）
【請求項３５】
（削除）
【請求項３６】
（削除）
【請求項３７】
復元された秘密情報を検証するための復元結果検証プログラムであって、
コンピュータに、
復元された秘密情報として（ｋ−１）次多項式ｆを入力し、請求項２７から請求項３１のうちのいずれか１項に記載の分散情報生成プログラムで出力した内容を格納する記憶装置から、請求項２７から請求項３１のうちのいずれか１項に記載の秘密情報分散処理で出力した第１の乱数ｒと、請求項２７から請求項３１のうちのいずれか１項に記載の秘密情報分散処理で生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する処理を実行させるための復元結果検証プログラム。
【請求項３８】
（削除）
【請求項３９】
（削除）
【請求項４０】
秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力し、前記固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力し、前記秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成し、前記多項式Ｆに前記各第１の乱数をそれぞれ入力して値を出力するとともに、前記多項式Ｆに前記固定値ｔを入力して値を出力する秘密情報分散装置と、
互いに異なるｎ個の第２の乱数を生成して出力し、前記秘密情報分散装置の出力であって、前記多項式Ｆに前記固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成し、前記多項式Ｇに前記第２の乱数をそれぞれ入力して値を出力する分散秘密情報分散装置と、
を含むことを特徴とする分散情報生成装置。
【請求項４１】
前記秘密情報分散装置は、ｋ−１以下のパラメータＬを入力し、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、
前記分散秘密情報分散装置は、前記多項式Ｆに固定値ｔを入力したときの出力を定数項とする前記多項式Ｇを生成する
請求項４０記載の分散情報生成装置。
【請求項４２】
前記秘密情報分散装置は、前記パラメータＬが１の場合、前記秘密情報ｓを定数項にだけ埋め込んで多項式Ｆを生成する請求項４１記載の分散情報生成装置。
【請求項４３】
前記秘密情報分散装置は、前記第１の乱数として、前記固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する請求項４０から請求項４２のうちのいずれか１項に記載の分散情報生成装置。
【請求項４４】
前記分散秘密情報分散装置は、前記第２の乱数として、互いに異なるｎ個の定数を生成して出力する請求項４０から請求項４２のうちのいずれか１項に記載の分散情報生成装置。
【請求項４５】
前記秘密情報分散装置から出力される前記第１の乱数と、前記多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記分散秘密情報分散装置から出力される、前記第２の乱数と、前記多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えた請求項４０から請求項４４のうちのいずれか１項に記載の分散情報生成装置。
【請求項４６】
秘密情報を分散する分散情報生成装置の出力に基づいて秘密情報を復元する復元装置であって、
請求項４０記載の分散情報生成装置の前記秘密情報分散装置の出力を格納する記憶装置と、
閾値ｋおよび所定の固定値ｔを入力し、
前記記憶装置から、請求項４０記載の分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した前記第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを前記多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元装置と、
前記記憶装置から、請求項４０記載の分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した前記第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを前記多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元装置と、
前記多項式Ｇ’に埋め込まれた値と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、前記多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置と
を備えたことを特徴とする復元装置。
【請求項４７】
前記分散情報生成装置の前記秘密情報分散装置は、ｋ−１以下のパラメータＬを入力し、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、前記分散情報生成装置の前記分散秘密情報分散装置は、前記多項式Ｆに固定値ｔを入力したときの出力を定数項とする前記多項式Ｇを生成し、前記記憶装置は、前記分散情報生成装置の出力を格納し、
前記復元装置は、ｋ−１以下のパラメータＬを入力し、
前記多項式復元装置は、前記記憶装置から、前記分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、前記分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記不正検出装置は、前記多項式Ｇ’の定数項と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、前記多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項４６記載の復元装置。
【請求項４８】
前記分散情報生成装置の前記秘密情報分散装置は、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成する代わりに、前記秘密情報ｓを定数項だけに埋め込んで多項式Ｆを生成し、
前記記憶装置は、前記分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、前記分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記不正検出装置は、前記多項式Ｇ’の定数項と前記多項式Ｆ’に前記固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する
請求項４７記載の復元装置。
【請求項４９】
前記分散情報生成装置の前記秘密情報分散装置は、前記第１の乱数として、前記固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、
前記記憶装置は、前記分散情報生成装置の出力を格納し、
前記多項式復元装置は、前記記憶装置から、前記分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数と、前記第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、
前記分散秘密情報復元装置は、前記記憶装置から、前記分散情報生成装置の前記分散秘密情報分散装置が出力した前記第２の乱数と、前記第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、
前記多項式復元装置は、前記第１の乱数として、前記固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力するか、または、前記分散秘密情報復元装置は、前記第２の乱数として、互いに異なるｎ個の定数を入力する
請求項４６から請求項４８のうちのいずれか１項に記載の復元装置。
【請求項５０】
前記不正検出装置は、前記多項式Ｇ’に埋め込まれた値と、前記多項式Ｆ’に前記固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項４６から請求項４９のうちのいずれか１項に記載の復元装置。
【請求項５１】
秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、
前記復元装置が出力した（ｋ−１）次多項式ｆを入力し、請求項４０から請求項４４のうちのいずれか１項に記載の分散情報生成装置の出力を格納する記憶装置から、前記分散情報生成装置の前記秘密情報分散装置が出力した前記第１の乱数ｒと、前記秘密情報分散装置が生成した前記多項式Ｆに前記第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する
ことを特徴とする復元結果検証装置。
【請求項５２】
閾値ｋと固定値ｔを入力する復元入力手段と、
ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力する多項式復元装置と、
ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力する分散秘密情報復元装置と、
多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置と、
を備えたことを特徴とする復元装置。
【請求項５３】
前記復元入力手段は、ｋ−１以下のパラメータＬを入力し、
前記不正検出装置は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる請求項５２に記載の復元装置。
【請求項５４】
前記不正検出装置は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項を用いる請求項５２に記載の復元装置。
【請求項５５】
前記不正検出装置は、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項５２から請求項５４のうちのいずれか１項に記載の復元装置。
【請求項５６】
ｋ−１次多項式ｆとパラメータｒ、ｖを入力とし、
多項式ｆにｒを入力したときの値がｖと等しい場合に不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力することを特徴とする復元結果検証装置。
【請求項５７】
秘密情報を復元するための復元方法であって、
閾値ｋと固定値ｔを入力し、
ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力し、
ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力し、
多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する、ことを特徴とする復元方法。
【請求項５８】
ｋ−１以下のパラメータＬを入力し、
前記多項式Ｆ’に埋め込まれた値を秘密情報として出力するにあたり、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる請求項５７記載の復元方法。
【請求項５９】
前記多項式Ｆ’に埋め込まれた値を秘密情報として出力するにあたり、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項を用いる請求項５７に記載の復元方法。
【請求項６０】
前記不正検出ステップで、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する請求項５７から請求項５９のうちのいずれか１項に記載の復元方法。
【請求項６１】
ｋ−１次多項式ｆとパラメータｒ、ｖを入力とし、
多項式ｆにｒを入力したときの値がｖと等しい場合に不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する、ことを特徴とする復元結果検証方法。
【請求項６２】
秘密情報を復元するための復元プログラムであって、
コンピュータに、
閾値ｋおよび所定の固定値ｔを入力する復元入力処理と、
ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力する多項式復元処理と、
ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力する分散秘密情報復元処理と、
多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出処理と、
を実行させるための復元プログラム。
【請求項６３】
前記復元入力処理で、ｋ−１以下のパラメータＬを入力し、
前記不正検出処理は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる請求項６２記載の復元プログラム。
【請求項６４】
前記不正検出処理は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項を用いる請求項６２記載の復元プログラム。
【請求項６５】
コンピュータに、
前記不正検出処理で、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力する処理を実行させる請求項６２から請求項６４のうちのいずれか１項に記載の復元プログラム。
【請求項６６】
復元された秘密情報を検証するための復元結果検証プログラムであって、
コンピュータに、
ｋ−１次多項式ｆとパラメータｒ、ｖを入力する処理と、
多項式ｆにｒを入力したときの値がｖと等しい場合に不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する処理と、を実行させるための復元結果検証プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
置は、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、第２分散多項式生成装置は、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００１８］
本発明の第３の側面によれば、前記第１の側面に係る分散情報生成装置において、前記第１分散多項式生成装置は、例えばパラメータＬが１の場合、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成するかわりに、秘密情報ｓを定数項とする多項式Ｆを生成してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。
［００１９］
本発明の第４の側面によれば、前記第１の側面に係る分散情報生成装置において、前記第１乱数生成装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、第２乱数生成装置は、第２の乱数として、互いに異なるｎ個の定数を生成して出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００２０］
本発明の第５の側面によれば、前記第１乃至第４のいずれか１の側面に係る分散情報生成装置において、前記第１乱数生成装置が出力した第１の乱数と、分散情報出力装置が出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、前記第２乱数生成装置が出力した第２の乱数と、分散分散情報出力装置が出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶する記憶装置を備えてもよい。そのような構成によれば、分散情報生成装置の出力を記憶装置に記憶させることができる。
［００２１］
本発明の第６の側面による復元装置においては、閾値ｋと固定値ｔを入力する復元入力手段と、ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力する多項式復元装置と、ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力する分散秘密情報復元装置と、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置とを備えた復元装置が提供される。より詳細には、秘密情報を分散する分散情報生成装置の出力に基づいて秘密情報を復元する復元装置であって、第１の側面に係る分散情報生成装置の出力を格納する記憶装置と、閾値ｋおよび所定の固定値ｔを入力する復元入力手段と、記憶装置から、前記第１の側面に係る分散情報生成装置における秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
次多項式Ｆ’を生成する多項式復元装置と、記憶装置から、第１の側面に係る分散情報生成装置における分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元装置と、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出装置とを備える。
［００２２］
本発明の第７の側面によれば、前記第６の側面の復元装置において、前記復元入力手段は、ｋ−１以下のパラメータＬを入力し、前記不正検出装置は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる。より詳細には、前記記憶装置は、前記第２の側面の分散情報生成装置の出力を格納し、前記復元入力手段は、ｋ−１以下のパラメータＬを入力し、前記多項式復元装置は、記憶装置から、前記第２の側面の分散情報生成装置の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元装置は、記憶装置から、前記第２の側面の分散情報生成装置の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００２３］
本発明の第８の側面によれば、前記第６の側面に係る復元装置において、前記不正検出装置は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項を用いる。より詳細には、前記記憶装置は、前記第３の側面の分散情報生成装置の出力を格納し、多項式復元装置は、記憶装置から、前記第３の側面の分散情報生成装置の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、不正検出装置は、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。
［００２４］
本発明の第９の側面によれば、前記第６乃至８のいずれか１の側面に係る復元装置において、前記記憶装置は、前記第４の側面の分散情報生成装置の出力を格納し、多項式復元装置は、記憶装置から、前記第４の側面の秘密情報分散装置が出力した第１の乱数と、第１の乱数を前記第４の側面の分散情報生成装置の秘密情報分散装置が生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元装置は、記憶装置から、前記第４の側面のの分散情報生成装置の分散秘密情報分散装置が出力した第２の乱数と、第２の乱数を前記分散秘密情報分散装置が生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、多項式復元装置は、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を入力し、または、分散秘密情報復元装置は、第２の乱数として、互いに異なるｎ個の定数を入力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００２５］
本発明の第１０の側面によれば、前記第６乃至第９のいずれか１の側面に係る復元装置において、前記不正検出装置は、多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力内容とが等しい場合に、それぞれの出力内容に加えて多項式Ｆ’を出力することが望ましい。そのような構成によれば、復元装置が出力した値を検証することができる。
［００２６］
本発明の第１１の側面による復元結果検証装置においては、ｋ−１次多項式ｆとパラメータｒ、ｖを入力とし、多項式ｆにｒを入力したときの値がｖと等しい場合に不正が検出されなかったことを示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する。より詳細には、秘密情報を復元する復元装置が出力した値を検証する復元結果検証装置であって、復元装置が出力した（ｋ−１）次多項式ｆを入力し、前記第１の側面から第５の側面のうちのいずれかの分散情報生成装置の出力を格納する記憶装置から、前記第１の側面から前記第５の側面のうちのいずれか１の秘密情報分散装置が出力した第１の乱数ｒと、前記第１の側面から前記第５の側面のうちのいずれかに記載の秘密情報分散装置が生成した多項式Ｆに第１の乱数ｒを入力したときの出力ｖとの対を入力し、多項式ｆに第１の乱数ｒを入力したときの出力と入力した値ｖとが等しい場合に、不正が検出されなかったこと
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
を示す情報を出力し、等しくない場合に、不正の検出を示す情報を出力する。
［００２７］
本発明の第１２の側面による秘密情報分散システムにおいては、前記第１の側面から前記第５の側面のうちのいずれか１の分散情報生成装置と、前記第６の側面から前記第１０の側面のうちのいずれか１の復元装置とを備える。
［００２８］
本発明の第１３の側面の秘密情報分散システムによれば、前記第１１の側面の復元結果検証装置を備えることが望ましい。そのような構成によれば、復元装置が出力した値を検証することができる。
［００２９］
本発明の第１４の側面による分散情報生成方法においては、秘密情報を分散する分散情報生成方法であって、秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力ステップと、秘密情報分散ステップと、分散秘密情報分散ステップとを含み、秘密情報分散ステップは、固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成ステップと、秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成ステップと、多項式Ｆに各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力ステップとを有し、分散秘密情報分散ステップは、互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成ステップと、分散情報出力ステップの出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成ステップと、多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力ステップとを有する
［００３０］
本発明の第１５の側面によれば、前記第１４の側面における前記分散入力ステップで、ｋ−１以下のパラメータＬを入力し、第１分散多項式生成ステップで、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成し、第２分散多項式生成ステップで、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００３１］
本発明の第１６の側面によれば、前記第１５の側面における前記第１分散多項式生成ステップで、例えばパラメータＬが１の場合、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成するかわりに、秘密情報ｓを定数項とする多項式Ｆを生成してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
［００３２］
本発明の第１７の側面によれば、前記第１４乃至第１６のいずれか１の側面における前記第１乱数生成ステップで、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力し、または、第２乱数生成ステップで、第２の乱数として、互いに異なるｎ個の定数を生成して出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００３３］
本発明の第１８の側面によれば、前記第１４乃至第１７のいずれか１の側面における前記第１乱数生成ステップで出力した第１の乱数と、分散情報出力ステップで出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、第２乱数生成ステップで出力した第２の乱数と、分散分散情報出力ステップで出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させてもよい。そのような構成によれば、分散情報生成方法における出力を記憶装置に記憶させることができる。
［００３４］
本発明の第１９の側面による復元方法においては、秘密情報を復元するための復元方法であって、閾値ｋと固定値ｔを入力し、
ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力し、
ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力し、
多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する。より詳細には、閾値ｋおよび所定の固定値ｔを入力する復元入力ステップと、前記第１４の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１４の側面の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１４の側面の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数ｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元ステップと、記憶装置から、前記第１４の側面の分散秘密情報分散ステッ
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
プで出力した第２の乱数と、第２の乱数を前記第１４の側面の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元ステップと、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出ステップとを含む。
［００３５］
本発明の第２０の側面によれば、前記第１９の側面における前記復元入力ステップで、前記復元入力ステップは、ｋ−１以下のパラメータＬを入力し、前記不正検出ステップは、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる。より詳細には、ｋ−１以下のパラメータＬを入力し、多項式復元ステップで、前記第１５の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１５の側面の秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１５の側面の秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散秘密情報復元ステップで、記憶装置から、前記第１５の側面の分散秘密情報分散ステップで出力した第２の乱数と、第２の乱数を前記第１５の側面の分散秘密情報分散ステップで生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｇ’を生成し、不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００３６］
本発明の第２１の側面によれば、前記第１９の側面における前記多項式復元ステップで、前記不正検出ステップは、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項を用いる。より詳細には、前記第１６の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１６の側面の前記秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記第１６の側面の前記秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、不正検出ステップで、多項式Ｇ’の定数項と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’の定数項を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力してもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。
［００３７］
本発明の第２２の側面によれば、前記第１９乃至２１のいずれか１の側面における前記多項式復元ステップで、前記第１７の側面の分散情報生成方法で出力した内容を格納する記憶装置から、前記第１７の側面の前記秘密情報分散ステップで出力した第１の乱数と、第１の乱数を前記秘密情報分散ステップで生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力して、（ｋ−１）次多項式Ｆ’を生成し、分散
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
［００４２］
本発明の第２７の側面による分散情報生成プログラムにおいては、秘密情報を分散するための分散情報生成プログラムであって、コンピュータに、秘密情報ｓ、閾値ｋ、分散情報数ｎおよび所定の固定値ｔを入力する分散入力処理と、秘密情報分散処理と、分散秘密情報分散処理とを実行させ、秘密情報分散処理で、固定値ｔと異なり、かつ互いに異なるｎ個の第１の乱数を生成して出力する第１乱数生成処理と、秘密情報ｓを埋め込んで（ｋ−１）次多項式Ｆを生成する第１分散多項式生成処理と、多項式Ｆに各第１の乱数をそれぞれ入力して値を出力するとともに、多項式Ｆに固定値ｔを入力して値を出力する分散情報出力処理とを実行させ、分散秘密情報分散処理で、互いに異なるｎ個の第２の乱数を生成して出力する第２乱数生成処理と、分散情報出力処理の出力であって、多項式Ｆに固定値ｔを入力したときの出力を埋め込んで（ｋ−１）次多項式Ｇを生成する第２分散多項式生成処理と、多項式Ｇに第２の乱数をそれぞれ入力して値を出力する分散分散情報出力処理とを実行させる。
［００４３］
本発明の第２８の側面によれば、前記第２７の側面に係るプログラムにおいて、コンピュータに、前記分散入力処理で、ｋ−１以下のパラメータＬを入力する処理を実行させ、前記第１分散多項式生成処理で、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成する処理を実行させ、前記第２分散多項式生成処理で、多項式Ｆに固定値ｔを入力したときの出力を定数項とする多項式Ｇを生成する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小さくすることができる。
［００４４］
本発明の第２９の側面によれば、前記第２８の側面に係るプログラムにおいて、コンピュータに、前記第１分散多項式生成処理で、例えばパラメータＬが１の場合、秘密情報ｓを定数項から（Ｌ−１）次までの係数を連結した値に埋め込んで多項式Ｆを生成するかわりに、秘密情報ｓを定数項とする多項式Ｆを生成する処理を実行させてもよい。そのような構成によれば、ｋ−１個以下の分散情報からは秘密情報に関する情報が漏れない。
［００４５］
本発明の第３０の側面によれば、前記第２７乃至第２９のいずれか１の側面に係るプログラムにおいて、コンピュータに、第１乱数生成処理で、第１の乱数として、固定値ｔと異なり、かつ互いに異なるｎ個の定数を生成して出力する処理を実行させ、または、第２乱数生成処理で、第２の乱数として、互いに異なるｎ個の定数を生成して出力する処理を実行させてもよい。そのような構成によれば、さらに分散情報のサイズを小
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
さくすることができる。
［００４６］
本発明の第３１の側面によれば、前記第２７乃至第３０のいずれか１の側面に係るプログラムにおいて、コンピュータに、第１乱数生成処理で出力した第１の乱数と、分散情報出力処理で出力した値であって多項式Ｆに第１の乱数を入力したときの出力とを対応付けて記憶するとともに、第２乱数生成処理で出力した第２の乱数と、分散分散情報出力処理で出力した値であって多項式Ｇに第２の乱数を入力したときの出力とを対応付けて記憶装置に記憶させる処理を実行させてもよい。そのような構成によれば、分散情報生成プログラム実行時の出力を記憶装置に記憶させることができる。
［００４７］
本発明の第３２の側面による復元プログラムにおいては、秘密情報を復元するための復元プログラムであって、コンピュータに、閾値ｋおよび所定の固定値ｔを入力する復元入力処理と、
ｖ１乃至ｖｋと、互いに異なる値ｒ１乃至ｒｋを入力として、ｒ１乃至ｒｋを入力した出力が、ｖ１乃至ｖｋであるような、（ｋ−１）次多項式Ｆ’を出力する多項式復元処理と、
ｗ１乃至ｗｋと、互いに異なる値ｘ１乃至ｘｋを入力として、ｘ１乃至ｘｋを入力した出力が、ｗ１乃至ｗｋであるような（ｋ−１）次多項式Ｇ’を出力する分散秘密情報復元処理と、
多項式Ｇ’に埋め込まれた値と、多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出処理と、を実行させる。より詳細には、閾値ｋおよび所定の固定値ｔを入力する復元入力処理と、第２７の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、第２７の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱数を第２７の側面の秘密情報分散処理で生成した（ｋ−１）次多項式Ｆに入力したときの出力との対をｋ組分入力し、入力した第１の乱数をｒ１ないしｒｋとし、ｒ１ないしｒｋを多項式Ｆに入力した出力をそれぞれｖ１ないしｖｋとして、ｒ１ないしｒｋが入力されたときそれぞれｖ１ないしｖｋを出力する（ｋ−１）次多項式Ｆ’を生成する多項式復元処理と、記憶装置から、第２７の側面の分散秘密情報分散処理で出力した第２の乱数と、第２の乱数を第２７の側面の分散秘密情報分散処理で生成した（ｋ−１）次多項式Ｇに入力したときの出力との対をｋ組分入力し、入力した第２の乱数をｘ１ないしｘｋとし、ｘ１ないしｘｋを多項式Ｇに入力した出力をそれぞれｗ１ないしｗｋとして、ｘ１ないしｘｋが入力されたときそれぞれｗ１ないしｗｋを出力する（ｋ−１）次多項式Ｇ’を生成する分散秘密情報復元処理と、多項式Ｇ’に埋め込まれた値と多項式Ｆ’に固定値ｔを入力したときの出力とが等しい場合に、多項式Ｆ’に埋め込まれた値を秘密情報として出力し、等しくない場合に、不正の検出を示す情報を出力する不正検出処理とを実行させる。
［００４８］
本発明の第３３の側面によれば、前記第３２の側面に係るプログラムにおいて、コンピュータに、前記復元入力処理は、ｋ−１以下のパラメータＬを入力し、前記不正検出処理は、多項式Ｇ’に埋め込まれた値として多項式Ｇ’の定数項を用い、秘密情報として多項式Ｆ’の定数項から（Ｌ−１）次までの係数を連結した値を用いる。より詳細には、前記復元入力処理で、ｋ−１以下のパラメータＬを入力し、多項式復元処理で、前記第２８の側面の分散情報生成プログラムで出力した内容を格納する記憶装置から、前記第２８の側面の秘密情報分散処理で出力した第１の乱数と、第１の乱
【国際調査報告】
2008093690.tif 000011
2008093690.tif 000012
2008093690.tif 000013
2008093690.tif 000014
2008093690.tif 000015
2008093690.tif 000016