(57)【要約】  本発明の目的は（ｋ、ｎ）閾値秘密分散法において、従来よりも少ない情報量の分散情報に基づいて、分散情報に対して行われた不正を検出することができる方法を提供することである。秘密情報復元方法であって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信し（ステップＢ１〜Ｂ５）、受信した全ての対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定し（ステップＢ５、Ｂ６）、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する（ステップＢ７、Ｂ８）（図４）。
2009025220.tif 000002
【特許請求の範囲】
【請求項１】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元装置であって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定するように構成されたことを特徴とする秘密情報復元装置。
【請求項２】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信し、受信した全ての対について前記判定を行い、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力するように構成されたことを特徴とする、請求項１に記載の秘密情報復元装置。
【請求項３】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として、（ｋ＋α）個の対の受信、及び、受信した全ての対についての前記判定をｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返し、前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力するように構成されたことを特徴とする、請求項１に記載の秘密情報復元装置。
【請求項４】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散システムであって、
請求項１ないし３のいずれか１項に記載の秘密情報復元装置を備えるとともに、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成し、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力するように構成された分散情報生成装置をさらに備えたことを特徴とする秘密情報分散システム。
【請求項５】
メッセージを送信する送信装置とメッセージを受信する受信装置とを備えた伝送システムであって、
前記送信装置は、請求項４に記載の秘密情報分散システムにおける分散情報生成装置を備え、前記メッセージを前記秘密情報として送信するように構成され、
前記受信装置は、請求項１ないし３のいずれか１項に記載の秘密情報復元装置を備え、前記乱数及び前記分散情報から復元された秘密情報としてメッセージを受信し、又は、改ざんが行われたことを検出するように構成されたことを特徴とする伝送システム。
【請求項６】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元方法であって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する工程を含むことを特徴とする秘密情報復元方法。
【請求項７】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する工程と、
受信した全ての対についての前記判定工程と、
復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程と、を含むことを特徴とする、請求項６に記載の秘密情報復元方法。
【請求項８】
前記受信工程及び前記判定工程を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す工程をさらに含み、
前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程を含むことを特徴とする、請求項７に記載の秘密情報復元方法。
【請求項９】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散方法であって、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する工程と、
乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する工程と、を含み、
請求項７又は８に記載の秘密情報復元方法における前記受信工程、前記判定工程及び前記出力工程又は前記受信工程、前記判定工程、前記繰り返し工程及び前記出力工程を含むことを特徴とする秘密情報分散方法。
【請求項１０】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する処理をコンピュータに実行させる秘密情報復元プログラムであって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する処理をコンピュータに実行させることを特徴とする秘密情報復元プログラム。
【請求項１１】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する処理と、
受信した全ての対についての前記判定処理と、
復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理と、をコンピュータに実行させることを特徴とする、請求項１０に記載の秘密情報復元プログラム。
【請求項１２】
前記受信処理及び前記判定処理を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す処理をさらにコンピュータに実行させ、
前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理をコンピュータに実行させることを特徴とする、請求項１１に記載の秘密情報復元プログラム。
【請求項１３】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散プログラムであって、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する処理と、
乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する処理と、をコンピュータに実行させ、
請求項１１又は１２に記載の秘密情報復元プログラムにおける前記受信処理、前記判定処理及び前記出力処理又は前記受信処理、前記判定処理、前記繰り返し処理及び前記出力処理をコンピュータに実行させることを特徴とする秘密情報分散プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本願は、先の日本特許出願２００７−２１５５４１号（２００７年８月２２日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は秘密情報分散システム、方法及びプログラム、秘密情報復元装置、方法及びプログラム並びに伝送システムに関し、特に、閾値秘密分散法に基づく秘密情報分散システム、方法及びプログラム、秘密情報復元装置、方法及びプログラム並びに伝送システムに関する。
【背景技術】
【０００２】
パスワード、個人情報又は暗号鍵情報等の秘密情報を保管する場合、紛失又は破壊に対する脅威と、盗難に対する脅威とがある。秘密情報のコピーを作成する方法は、紛失に対して有効であるものの、盗難に対する脅威はむしろ増大してしまう。【０００３】
かかる問題を解決する方法として、Ｓｈａｍｉｒ（シャミア）によって提案された（ｋ、ｎ）閾値秘密分散法が注目されている（非特許文献３）。【０００４】
（ｋ、ｎ）閾値秘密分散法においては、秘密情報はｎ個の分散情報へと符号化される。ここで、ｋは閾値、ｎは分割数である。秘密情報は、ｎ個のうちｋ個以上の任意の分散情報によって復元することができるものの、（ｋ−１）個以下の分散情報からは復元することができないという特徴がある。【０００５】
非特許文献３の方法においては、素数又は素数のべき乗ｐに対する有限体ＧＦ（ｐ）を秘密情報のデータ集合として用い、秘密情報Ｓを定数項に含むＧＦ（ｐ）上の（ｋ−１）次多項式ｆ（ｘ）上のランダムな点（ｘ１、ｆ（ｘ１））、…、（ｘｎ、ｆ（ｘｎ））を分散情報として生成する。【０００６】
いま、ｋ個の分散情報が与えられたとすると、（ｋ−１）次の多項式ｆ（ｘ）を一意に復元することができる。このとき、ｆ（０）の値、すなわち関数ｆ（ｘ）の定数項の値として秘密情報Ｓを復元することができる。【０００７】
また、（ｋ−１）個以下の分散情報からは（ｋ−１）次多項式を一意に決定することができないため、秘密情報Ｓは漏洩しない。【０００８】
したがって、（ｋ、ｎ）閾値秘密分散法を用いた場合には、（ｋ−１）個以下の分散情報が盗難にあったときも、秘密情報は漏洩することがなく、（ｎ−ｋ）個までの分散情報が破壊されたときも、秘密情報は復元することができる。【０００９】
ここでは、（ｋ、ｎ）閾値秘密分散法において、分散情報の作成及び配付が正しく行われたものと想定する。このとき、秘密情報を復元しようとする者は、分散情報を保有する他者から分散情報を集めようとする。【００１０】
しかし、分散情報を要求された他者が、常に、保有する分散情報を改ざんすることなく送信するとは限らない（以下では、秘密分散法への参加者であって、改ざんした分散情報の送信者を不正者と呼ぶ。）。改ざんされた分散情報に基づいて復元された値は、秘密情報の本来の値とは異なる値となり得る。【００１１】
そこで、復元に使用された分散情報中において、復元された秘密情報が本来の値とは異なる値となるよう改ざんされた分散情報が存在することを、高い確率で検出できることが好ましい。【００１２】
そこで、非特許文献１及び２において、以下の方法が開示されている。【００１３】
非特許文献１の方法は、（ｋ、ｎ）閾値秘密分散法であって、不正を検出するこができる確率を（１−ε）とし、秘密情報が要素数ｓの集合から選ばれるものとすると、分散情報は要素数がほぼｓ／εである集合となる。【００１４】
この方法においては、秘密情報が一様な分布に従って選ばれることを条件として、安全性が保障される。この方法の不正の検出方法は、ｋ個の分散情報を入力とする方法で、（ｋ−１）個まで分散情報が改ざんされても前述の条件を満たす。【００１５】
しかし、現実には、秘密情報が一様な分布に従って選ばれるとは限らず、この条件を必要としない方法が望まれる。【００１６】
非特許文献２において、秘密情報がどのような分布に従って選ばれたとしても安全な方法が提案されている。この方法は（ｋ、ｎ）閾値秘密分散法であり、不正を検出することができる確率を（１−ε）とすると、分散情報は要素数がｓ／ε２の集合となる。【００１７】
また、不正の検出方法はｋ個の分散情報を入力とした方法で、（ｋ−１）個まで分散情報が改ざんされても前述の条件を満たす。【００１８】
非特許文献１及び２に開示された秘密分散法は、「不正検出可能な秘密分散法」と呼ばれている。前述の２つの方法は、不正を検出するために閾値とちょうど同じ数の分散情報を用いる方法である。【００１９】
非特許文献６において、閾値より多くの分散情報を用いて不正の検出を行う方法が開示されており、非常に効率的であることが知られている。しかし、この方法は、改ざんされた分散情報の個数をｕと表すと、（ｋ＋２ｕ）個の分散情報を要する。【００２０】
非特許文献６以外にも、ｋ個よりも多くの分散情報を用いて不正の検出を行う方法が提案されているが、これらは、改ざんされた分散情報を特定する等、単に不正の検出を行う以上の効果を得ることを目的としており、必ずしも効率の良い方法ではない。【００２１】
また、「不正検出可能な秘密分散法」を用いることでメッセージの伝送方法を構成することができることが知られている。【００２２】
ここで、メッセージの伝送方法とは、送信装置と受信装置との間にｎ本のチャンネルがある場合において、（ｋ−１）本までのチャンネルを流れる情報を改ざんし、かつ、知ることができる不正者が存在しても、（１）受信装置は圧倒的確率で送信装置の送ったメッセージを伝送でき、（２）送信装置の送ったメッセージ以外の値を受信装置が受信することはなく、（３）不正者は送信装置の送ったメッセージを一切推定することができない、伝送方法をいう。ここで、ｋを想定不正チャンネル数と呼ぶことにする。【００２３】
このようなメッセージ伝送方法はｋとｎとの値の関係によって構成が可能な場合と不可能な場合とがあり、様々な方法が提案されている。【００２４】
本発明では、送信装置から受信装置に向けて、一度だけｎ本のチャンネルを使ってデータを送信することができるという、１ラウンドの伝送方式を想定する。【００２５】
非特許文献５において、例えば、ｔ＝（ｋ−１）とし、ｎ≧３ｔ＋１である場合について、効率の良い伝送方法が開示されている。【００２６】
また、非特許文献４において、３ｔ＋１＞ｎ≧２ｔ＋１である場合に対する、伝送方法が開示されており、ｎ＝２ｔ＋１である場合には効率的である。【００２７】
さらに、ｎ≧３ｔ＋１である場合、非特許文献４の方法を用いることはできるものの、非特許文献５に開示された方法を用いた方が効率がよい。【００２８】
なお、非特許文献４において、２ｔ≧ｎである場合、メッセージ伝送方法を構成することができないことが示されている。【００２９】
非特許文献４において開示された、メッセージ伝送方法は次の通りである。【００３０】
送信装置は、「不正検出可能な秘密分散法」によって送信メッセージの分散情報を生成し、チャンネルを介して各分散情報を送信する。【００３１】
受信装置は、ｎ本のチャンネルのうち任意のｋ本のチャンネルを介して送信された分散情報を送信装置と同じ秘密分散法によって復元して、復元されたメッセージの値がすべて同じ値であれば、その値を送信装置の送ったメッセージとして出力する。【００３２】
つまり、それぞれのチャンネルを流れる情報量は、用いた「不正検出可能な秘密分散法」に依存する。【００３３】
ここでは、チャンネルを用いた場合の説明を行ったが、チャンネルを実現する手段は、送信装置の生成した複数のデータを分けて送信することができるものであればよい。【００３４】
【非特許文献１】Ｗ．  Ｏｇａｔａ、Ｋ．  Ｋｕｒｏｓａｗａ、Ｄ．  Ｒ．  Ｓｔｉｎｓｏｎ：”Ｏｐｔｉｍｕｍ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ｃｈｅａｔｉｎｇ”、ＳＩＡＭ  Ｊ．Ｄｉｓｃｒｅｔｅ  Ｍａｔｈ．、ｖｏｌ．２０、ｎｏ．１、ｐ．７９−９５（２０６）
【非特許文献２】Ｓ．  Ｏｂａｎａ、Ｔ．  Ａｒａｋｉ：”Ａｌｍｏｓｔ  Ｏｐｔｉｍｕｍ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅｓ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ｃｈｅａｔｉｎｇ  ｆｏｒ  Ａｒｂｉｔｒａｒｙ  Ｓｅｃｒｅｔ  Ｄｉｓｔｒｉｂｕｔｉｏｎ”、ＡＳＩＡＣＲＹＰＴ、ｐ．３６４−３７９（２０６）
【非特許文献３】Ａ．  Ｓｈａｍｉｒ：”Ｈｏｗ  ｔｏ  ｓｈａｒｅ  ａ  ｓｅｃｒｅｔ”、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ＡＣＭ、２２（１１）、ｐ．６１２−６１３（１９７９）
【非特許文献４】Ｋ．  Ｋｕｒｏｓａｗａ  ａｎｄ  Ｋ．  Ｓｕｚｕｋｉ、”Ａｌｍｏｓｔ  Ｓｅｃｕｒｅ  （１−Ｒｏｕｎｄ、ｎ−Ｃｈａｎｎｅｌ）  Ｍｅｓｓａｇｅ  Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｓｃｈｅｍｅ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ”、ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０７／０７６
【非特許文献５】Ｄ．Ｄｏｌｅｖ、Ｃ．Ｄｗｏｒｋ、Ｏ．Ｗａａｒｔｓ、Ｍ．Ｙｕｎｇ、”Ｐｅｒｆｅｃｔｌｙ  Ｓｅｃｕｒｅ  Ｍｅｓｓａｇｅ  Ｔｒａｎｓｍｉｓｓｉｏｎ”、Ｊ．ＡＣＭ  ４０（１）、ｐ．１７−４７（１９９３）
【非特許文献６】Ｒ．Ｊ．ＭｃＥｌｉｅｃｅ、Ｄ．Ｖ．Ｓａｒｗａｔｅ：”Ｏｎ  Ｓｈａｒｉｎｇ  Ｓｅｃｒｅｔｓ  ａｎｄ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  Ｃｏｄｅｓ”、Ｃｏｍｍ．ＡＣＭ、２４、ｐ．５８３−５８４（１９８１）
【発明の開示】
【発明が解決しようとする課題】
【００３５】
なお、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者によってなされたものである。【００３６】
従来の「不正検出可能な秘密分散法」は、不正を検出するために、多くの分散情報を処理する必要があり、効率が悪いという問題があった。【００３７】
そこで、（ｋ、ｎ）閾値秘密分散法において、分散情報に基づいて秘密情報を復元する際に、分散情報等に対して行われた不正を、少ない情報量の分散情報に基づいて効率よく検出する方法を提供することが課題となる。
【課題を解決するための手段】
【００３８】
本発明の第１の視点に係る秘密情報復元装置は、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元装置であって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定するように構成されたことを特徴とする。また、秘密情報復元装置は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信し、受信した全ての対について上記判定を行い、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力するように構成してもよい。【００３９】
本発明の第２の視点に係る秘密情報復元方法は、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元方法であって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する工程を含むことを特徴とする。また、秘密情報復元方法は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する工程と、受信した全ての対についての上記判定工程と、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程と、を含むようにしてもよい。【００４０】
本発明の第３の視点に係る秘密情報復元プログラムは、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する処理をコンピュータに実行させる秘密情報復元プログラムであって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する処理をコンピュータに実行させることを特徴とする。また、秘密情報復元プログラムは、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する処理と、受信した全ての対についての上記判定処理と、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理と、をコンピュータに実行させてもよい。【００４１】
第１の展開形態の秘密情報復元装置は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として、（ｋ＋α）個の対の受信、及び、受信した全ての対についての上記判定をｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返し、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力するように構成されることが好ましい。【００４２】
第２の展開形態の秘密情報分散システムは、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散システムであって、上記の秘密情報復元装置を備えるとともに、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成し、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力するように構成された分散情報生成装置をさらに備えることが好ましい。【００４３】
第３の展開形態の伝送システムは、メッセージを送信する送信装置とメッセージを受信する受信装置とを備えた伝送システムであって、上記送信装置は、上記の分散情報生成装置を備え、上記メッセージを上記秘密情報として送信するように構成され、上記受信装置は、上記の秘密情報復元装置を備え、上記乱数及び上記分散情報から復元された秘密情報としてメッセージを受信し、又は、改ざんが行われたことを検出するように構成されることが好ましい。【００４４】
第４の展開形態の秘密情報復元方法は、上記受信工程及び上記判定工程を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す工程をさらに含み、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程を含むことが好ましい。【００４５】
第５の展開形態の秘密情報分散方法は、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散方法であって、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する工程と、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する工程と、を含み、上記の秘密情報復元方法における上記受信工程、上記判定工程及び上記出力工程又は上記受信工程、上記判定工程、上記繰り返し工程及び上記出力工程を含むことが好ましい。【００４６】
第６の展開形態の秘密情報復元プログラムは、上記受信処理及び上記判定処理を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す処理をさらにコンピュータに実行させ、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理をコンピュータに実行させることが好ましい。【００４７】
第７の展開形態の秘密情報分散プログラムは、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散プログラムであって、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する処理と、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する処理と、をコンピュータに実行させ、上記の秘密情報復元プログラムにおける上記受信処理、上記判定処理及び上記出力処理又は上記受信処理、上記判定処理、上記繰り返し処理及び上記出力処理をコンピュータに実行させることが好ましい。
【発明の効果】
【００４８】
本発明の秘密情報復元方法においては、従来よりも少ない情報量の分散情報に基づいて、分散情報に対して行われた不正を検出することができる。
【図面の簡単な説明】
【００４９】
【図１】本発明の実施形態に係る分散情報生成システムのブロック図である。
【図２】本発明の他の実施形態に係る伝送システムのブロック図である。
【図３】本発明の実施形態に係る分散情報生成システムに備えた分散情報生成装置の動作を示すフローチャートである。
【図４】本発明の実施形態に係る分散情報生成システムに備えた秘密情報復元装置の動作を示すフローチャートである。
【図５】本発明の他の実施形態に係る伝送システムに備えた送信装置の動作を示すフローチャートである。
【図６】本発明の他の実施形態に係る伝送システムに備えたチャンネルの動作を示すフローチャートである。
【図７】本発明の他の実施形態に係る伝送システム備えた受信装置の動作を示すフローチャートである。
【図８】本発明の実施形態に係る分散情報生成システム又は他の実施形態に係る伝送システムに備えた処理装置のブロック図である。
【符号の説明】
【００５０】
１０  分散情報生成装置
１１  秘密情報分散装置
１２  乱数生成装置
２０  秘密情報復元装置
２１  多項式復元装置
２２  不正検出装置
３０−１〜３０−ｎ  記憶装置
４０  送信装置
４１  メッセージ分散装置
４２  乱数生成装置
５０  受信装置
５１  組合せ装置
５２  多項式復元装置
５３  不正検出装置
５４  メッセージ復元装置
６０−１〜６０−ｎ  チャンネル
７０  処理装置
７１  ＣＰＵ
７２  主記憶装置
７３  記録媒体
７４  データ蓄積装置
７５ａ、７５ｂ、７５ｃ  メモリ制御インタフェース部
７６ａ、７６ｂ  Ｉ／Ｏインタフェース部
７７  バス
８０  入力装置
９０  出力装置
【発明を実施するための最良の形態】
【００５１】
本発明の実施形態に係る秘密情報分散システムについて、図面を参照して詳細に説明する。【００５２】
本発明では、（ｋ、ｎ）閾値秘密分散法として、非特許文献３において開示された、（ｋ−１）次多項式に基づく方法を採用する。【００５３】
非特許文献３の方法においては、素数又は素数のべき乗ｐに対する有限体ＧＦ（ｐ）を秘密情報のデータ集合として用い、秘密情報Ｓを定数項に含むＧＦ（ｐ）上の（ｋ−１）次多項式ｆ（ｘ）上のランダムな点（ｘ１、ｆ（ｘ１））、…、（ｘｎ、ｆ（ｘｎ））を分散情報として生成する。【００５４】
以下では、分散情報を記憶及び保持する記憶装置の夫々に、各ｘｉ（ｉ＝１、…、ｎ）を個別に格納するものとする。【００５５】
また、ｘｉに対応するｆ（ｘｉ）をｘｉに対する分散情報と呼ぶ。【００５６】
図１は本発明の実施形態に係る秘密情報分散システムの構成を示すブロック図である。【００５７】
図１を参照すると、本発明の実施形態に係る秘密情報分散システムは、分散情報生成装置１０と、秘密情報復元装置２０と、複数の記憶装置３０−１〜３０−ｎとを備えるシステムである。【００５８】
分散情報生成装置１０は、秘密情報Ｓと、閾値ｋと、分割数ｎを入力として、互いに異なるｎ個の乱数の組（以降、乱数セットＡと呼ぶ）を生成して出力し、Ｓを定数項として含む、ランダム係数を備えた（ｋ−１）次多項式ｆを生成し、多項式ｆに乱数セットＡの各要素をそれぞれ入力して値を出力する。【００５９】
秘密情報復元装置２０は、分散情報生成装置１０の出力した乱数セットＡの要素と、乱数セットＡの要素に対する秘密情報Ｓの分散情報と、を記憶する（ｋ＋α）個の記憶装置のうちｋ個からそれぞれの記憶する乱数セットＡの要素ｒ１、…、ｒｋと、それぞれに対応する秘密情報の分散情報ｆ１、…、ｆｋを読み出し、（ｒ１、ｆ１）と、…、（ｒｋ、ｆｋ）を通る（ｋ−１）次多項式ｇ（ｋ）を計算し、残りα個の記憶装置に記録された乱数セットＡの要素をｒｋ＋１、…、ｒｋ＋α、それに対応する秘密情報の分散情報ｆｋ＋１、…、ｆｋ＋αとし、（ｒｋ＋１、ｆｋ＋１）、…、（ｒｋ＋α、ｆｋ＋α）が復元したｇ（ｘ）上の点である場合にはｇ（０）を秘密情報Ｓとして出力し、それ以外の場合には不正の検出を表す信号を出力する。【００６０】
以上の構成に基づいて、乱数セットＡのサイズを適切に選ぶことで、本発明の課題を解決することができる。【００６１】
分散情報生成装置１０は、秘密情報分散装置１１と、乱数生成装置１２とを備え、秘密情報用データ集合Ｓの元である秘密情報Ｓ、閾値ｋ、分割数ｎを入力とし、記憶装置３０−１〜３０−ｎへ相異なる乱数用データ集合ＲＡの元を出力するとともに、記憶装置３０−１〜３０−ｎへ分散情報用データ集合ＢＳの元を出力する。【００６２】
前記、乱数生成装置１２は、分割数を表すｎを入力し、記憶装置３０−１〜３０−ｎへ互いに異なる乱数用データ集合ＲＡの元（３０−ｉ（ｉ＝１、…、ｎ）の記憶するＲＡの元をｒｉとする。）を出力し、ｒ１、…、ｒｎを秘密情報分散装置１１へ出力する。【００６３】
秘密情報分散装置１１は、秘密情報Ｓと、閾値ｋと、分割数ｎと、乱数生成装置１２からｒ１、…、ｒｎを入力し、非特許文献３の（ｋ、ｎ）閾値秘密分散法を用いて、秘密情報Ｓから分散情報を生成するための（ｋ−１）次多項式ｆ（ｘ）を生成するとともに、記憶装置３０−１〜３０−ｎのそれぞれに対して、個別に、分散情報ｆ（ｒ１）〜ｆ（ｒｎ）を出力する。以下では、分散情報ｆ（ｒｉ）をｆｉと略記する。【００６４】
秘密情報復元装置２０は、多項式復元装置２１及び不正検出装置２２を備える。【００６５】
秘密情報復元装置２０は、閾値ｋ、パラメータαを入力し、ｋ＋α個の記憶装置３０から、それぞれの記憶する乱数用データ集合の元と、分散情報用データ集合ＢＳの元を入力し、秘密情報Ｓ又は不正の検出を表す信号を出力する。【００６６】
多項式復元装置２１は、閾値ｋを入力し、ｋ個の記憶装置３０から、それぞれの記憶する乱数用データ集合の元と、分散情報用データ集合ＢＳの元を読み出し、多項式用データ集合Ｖの元を出力する。【００６７】
不正検出装置２２は、多項式用データ集合Ｖの元ｆと、パラメータαを入力とし、記憶装置３０−１〜３０−ｎのうちα個から、それぞれの記憶する乱数用データ集合の元ｔ１、…ｔαと、分散情報用データ集合ＢＳの元ｇ１、…、ｇαとを読み出し、ｆ（ｔ１）＝ｇ１、…、ｆ（ｔα）＝ｇαがすべて満たされている場合にはｆ（０）を秘密情報Ｓとして出力し、満たされていない場合には不正の検出を表す信号を出力する。【００６８】
次に、本発明の他の実施形態に係る秘密情報分散システムについて、図面を参照して詳細に説明する。【００６９】
図２は、本発明の他の実施形態に係る伝送システムの構成を示すブロック図である。【００７０】
伝送システムは、図２を参照すると、ｎ本のチャンネル６０−１〜６０−ｎを介して接続された送信装置４０及び受信装置５０からなる。【００７１】
送信装置４０は、送信メッセージＳ、チャンネル数ｎ、想定不正チャンネル数ｋ（ｋ＝ｔ＋１として３ｔ＋１＞ｎ＞２ｔ＋１を満たしているものとする。）を入力する。また、送信装置４０は、本発明の秘密情報分散システムの分散情報生成装置１０にＳを秘密情報、ｎを分割数、ｋを閾値として入力し、分散情報生成装置１０の生成した乱数セットの要素と、その要素を分散情報生成装置が生成したＳを定数項に含む多項式に入力した出力とを組として、夫々チャンネル６０−１〜６０−ｎを介して、受信装置５０へ送信する。【００７２】
受信装置５０は、ｎ本のチャンネル６０−１〜６０−ｎを介して受信した情報を入力とする。また、受信装置５０は、ｎ本のチャンネルのうちの任意のｋ＋α本のチャンネルの組を通して送られてきた情報に基づいて復元されたメッセージの値がすべて同じ値であれば、その値を送信者の送ったメッセージとして出力する。【００７３】
図２においては、ｎ本のチャンネル６０−１〜６０−ｎを用いた場合を例示したが、送信装置４０の生成した複数のデータを個別に送信することができるものであればよく、チャンネルを実現する手段はｎ本である必要はない。【００７４】
想定不正チャンネル数ｋとは、送信装置が生成するｎ組の情報に対する改ざん、盗聴を許す最大の数を表す。【００７５】
以下ではｔ＝ｋ−１として、３ｔ＋１＞ｎ≧２ｔ＋１＋αなる関係を充たしているものとする。【００７６】
図２を参照して、送信装置４０の構成について説明する。【００７７】
送信装置４０は、メッセージ分散装置４１、乱数生成装置４２を備える。送信装置４０は、メッセージ用データ集合Ｍの元であるメッセージＳ、想定不正チャンネル数ｋ、チャンネル数ｎ、を入力し、チャンネル６０−１〜６０−ｎに対し、互いに異なる乱数用データ集合ＲＡの元を入力し、チャンネル６０−１〜６０−ｎに対し、分散メッセージ用データ集合ＢＳの元を入力する。【００７８】
乱数生成装置４２は、チャンネル数を表すｎを入力とし、チャンネル６０−１〜６０−ｎに対し、互いに異なる乱数用データ集合ＲＡの元を入力し（６０−ｉ（ｉ＝１、…、ｎ）に入力するＲＡの元をｒｉとする）、ｒ１、ｒ２、…、ｒｎをメッセージ分散装置４１へ出力する。【００７９】
メッセージ分散装置４１は、集合Ｍの元Ｓ、想定不正チャンネル数ｋ、チャンネル数ｎ、乱数生成装置４２から乱数ｒ１、ｒ２、…、ｒｎを入力する。メッセージ分散装置４１は、非特許文献３の（ｋ、ｎ）閾値秘密分散法によってメッセージＳに対する分散情報を生成するための多項式ｆを生成し、の夫々に対し、分散情報ｆ（ｒｉ）を夫々チャンネル６０−ｉへ出力する（ｉ＝１〜ｎ）。【００８０】
チャンネル６０−ｉは、送信装置４０からｒｉ、ｆ（ｒｉ）を入力するとともに、受信装置５０へ出力する。【００８１】
受信装置５０は、組合せ装置５１、多項式復元装置５２、不正検出装置５３、メッセージ復元装置５４を備える。【００８２】
受信装置５０は、想定不正チャンネル数ｋ、パラメータαを入力し、ｎ本のチャンネル６０−１〜６０−ｎ夫々から、乱数用データ集合の元と、分散メッセージ用データ集合ＢＳの元を入力して、メッセージ用データ集合Ｍの元、もしくは不正の検出を表す記号を出力する。【００８３】
組合せ装置５１は、ｎ本のチャンネル６０−１〜６０−のｎからの乱数及び分散メッセージ、想定不正チャンネル数ｋ、パラメータα、メッセージ復元装置５４からの次の組合せの入力を要請する信号を入力する。また、組合せ装置５１は、ｎ本のチャンネルから選択された（ｋ＋α）本の組合せの中、ｋ本のチャンネルの入力を多項式復元装置５２へ、残りα本のチャンネルの入力を不正検出装置５３へ出力する。さらに、組合せ装置５１は、ｎ本のチャンネルから（ｋ＋α）本を選ぶ、すべての組合せについての出力を完了した旨を表す信号をメッセージ復元装置５４へ出力する。【００８４】
前記多項式復元装置５２は、組合せ装置５１の出力を入力し、多項式用データ集合Ｖの元を出力する。【００８５】
不正検出装置５３は、組合せ装置５１の出力、多項式用データ集合Ｖの元ｆを入力する。不正検出装置５３は、組合せ装置５１からの入力を乱数用データ集合の元ｔ１〜ｔαとし、分散メッセージ用データ集合ＢＳの元をｇ１〜ｇαとしたとき、ｆ（ｔｉ）＝ｇｉがすべてのｉ（ｉ＝１〜α）について満たされている場合にはｆ（０）をメッセージ復元装置５４へ出力し、満たされていない場合には不正の検出を表す信号をメッセージ復元装置５４へ出力する。【００８６】
メッセージ復元装置５４は、不正検出装置５３からの入力と、組合せ装置５１からすべての組合せについての出力を完了した旨の信号を入力し、不正の検出を表す記号を除き、すべての入力が等しい場合にはその値を出力し、それ以外の場合には不正の検出を表す記号を出力する。【００８７】
図１における分散情報生成装置１０、秘密情報復元装置２０、図２における送信装置４０、受信装置５０は、一例として、論理回路から構成されるＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）やＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｏｃｅｓｓｏｒ）等の半導体集積回路によって実現することができる。【００８８】
一方、分散情報生成装置１０、秘密情報復元装置２０、送信装置４０、受信装置５０は図８に示すように、プログラムに従って、所定の処理を実行する処理装置７０と、処理装置７０に対してコマンドや情報などを入力するための入力装置８０と、処理装置７０の処理結果をモニタ画面へ表示する出力装置９０と、を備えたコンピュータによって実現することもできる。【００８９】
処理装置７０は、図８を参照すると、ＣＰＵ７１と、ＣＰＵ７１の処理に必要な情報を一時的に記憶する主記憶装置７２と、ＣＰＵ７１に分散情報生成装置１０、秘密情報復元装置２０、送信装置４０、受信装置５０としての処理を実行させるための後述のプログラムが記録された記録媒体７３と、秘密情報、閾値、分割数、定数等が格納されるデータ蓄積装置７４と、主記憶装置７２、記録媒体７３及びデータ蓄積装置７４とのデータ転送を制御するメモリ制御インタフェース部７５ａ〜７５ｃと、入力装置８０及び出力装置９０とのインタフェース装置であるＩ／Ｏインタフェース部７６ａ、７６ｂと、を備える。処理装置７０の各部はバス７７を介して互いに接続される。【００９０】
なお、データ蓄積装置７４は、処理装置７０の内部に備える必要はなく、処理装置７０とは独立に外部に備える構成としてもよい。【００９１】
処理装置７０は、記録媒体７３に記録されたプログラムにしたがって後述する分散情報生成装置１０、秘密情報復元装置２０、送信装置４０、受信装置５０としての機能を実現する。【００９２】
記録媒体７３は、磁気ディスク、半導体メモリ、光ディスクその他記録媒体であってもよい。【００９３】
チャンネル６０−１〜６０−ｎはデータを送信することができるものであればよく、光ファイバ、電話線等であってもよい。【００９４】
次に、本発明の実施形態に係る秘密分散システムの動作を、図３及び図４のフローチャートに基づいて説明する。【００９５】
図３は、本発明の実施の形態に係る秘密分散システムに備えた、分散情報生成装置１０の動作のフローチャートである。【００９６】
はじめに、分散情報生成装置１０に備えた秘密情報分散装置１１は、秘密情報用データ集合の元である秘密情報Ｓ、閾値ｋと、分割数ｎを入力する（ステップＡ１）。【００９７】
分散情報生成装置１０に備えた乱数生成装置１２は、分割数ｎを入力する（ステップＡ２）。【００９８】
乱数生成装置１２は、秘密情報分散装置１１及び記憶装置３０−１〜３０−ｎへ相異なる乱数からなる集合ＲＡの元ｒ１〜ｒｎを出力する（ステップＡ３）。【００９９】
秘密情報分散装置１１は、ｋを閾値として、乱数ｒ１〜ｒｎに基づいて、秘密情報Ｓに対する分散情報を生成し、記憶装置３０−１〜３０−ｎへ出力する（ステップＡ４）。【０１００】
図４は、本発明の実施の形態に係る秘密分散システムに備えた、秘密情報復元装置２０の動作のフローチャートである。【０１０１】
秘密情報復元装置２０は、閾値ｋ、パラメータαを入力する（ステップＢ１）。【０１０２】
多項式復元装置２１は、閾値ｋを入力する（ステップＢ２）。【０１０３】
多項式復元装置２１は、ｋ個の記憶装置から乱数及び分散情報を入力し、復元した（ｋ−１）次多項式ｇ（ｘ）を不正検出装置２２へ出力する（ステップＢ３）。【０１０４】
不正検出装置２２はパラメータαを入力する（ステップＢ４）。【０１０５】
不正検出装置２２は、ステップＢ３のｋ個の記憶装置を除くα個の記憶装置から乱数ｒｉと分散情報ｆｉとからなるα個の対を入力し、すべての対について、ｇ（ｒｉ）＝ｆｉなる関係が充たされているか否かを判定する（ステップＢ５）。【０１０６】
充たされていると判定された場合（ステップＢ６のＹｅｓ）には、ｇ（０）を復元された秘密情報として出力し（ステップＢ７）、充たされていないと判定した場合(ステップＢ６のＮｏ)には、不正(改ざん)を検出したことを表す信号を出力する（ステップＢ８）。【０１０７】
次に本発明の他の実施形態に係る伝送システムの動作を図５、図６及び図７のフローチャートに従って説明する。【０１０８】
図５は、本発明の他の実施形態に係る伝送システムに備えた送信装置４０の動作を示すフローチャートである。【０１０９】
はじめに、送信装置４０は、メッセージ用データ集合Ｍの元であるメッセージｍ、想定不正チャンネル数ｋ、チャンネル数ｎを入力する（ステップＣ１）。【０１１０】
メッセージ分散装置４１に備えた乱数生成装置４２は、チャンネル数ｎを入力する（ステップＣ２）。【０１１１】
乱数生成装置４２は、メッセージ分散装置４１及びチャンネル６０−１〜６０−ｎへ、相異なる乱数用データ集合ＲＡの元ｒ１〜ｒｎを出力する（ステップＣ３）。【０１１２】
メッセージ分散装置４１は、メッセージｍ、想定不正チャンネル数ｋ、チャンネル数ｎを入力する（ステップＣ４）。【０１１３】
メッセージ分散装置４１は、ｋを閾値とし、乱数ｒ１〜ｒｎに基づいて、メッセージｍに対する分散情報ｆ１〜ｆｎを生成し、夫々チャンネル６０−１〜６０−ｎへ出力する（ステップＣ５）。【０１１４】
図６は、本発明の他の実施形態に係る伝送システムに備えたチャンネル６０−ｉ（ｉ＝１〜ｎ）の動作を示すフローチャートである【０１１５】
チャンネル６０−ｉには、乱数ｒｉ及び分散情報ｆｉを入力し（ステップＤ１）、受信装置５０へ出力する（ステップＤ２）。【０１１６】
図７は、本発明の他の実施形態に係る伝送システム備えた受信装置５０の動作を示すフローチャートである。【０１１７】
受信装置５０に備えた組合せ装置５１は、想定不正チャンネル数ｋと、パラメータα、ｎ本のチャンネルから乱数ｒｉ、分散情報ｆｉ（ｉ＝１〜ｎ）を入力する（ステップＥ１）。【０１１８】
組合せ装置５１は、ｎ個の乱数と分散情報の対から、（ｋ＋α）個の対の組合せｒ１〜ｒｋ＋α、ｆ１〜ｆｋ＋αを抽出し、ｋ個の組ｒ１〜ｒｋ、ｆ１〜ｆｋを多項式復元装置５２へ出力し、α個の組ｒｋ＋１〜ｒｋ＋α、ｆｋ＋１〜ｆｋ＋αを不正検出装置５３へ出力する（ステップＥ２）。【０１１９】
多項式復元装置５２は、ｋ個の乱数と分散情報に基づいて、（ｋ−１）次多項式ｇ（ｘ）を復元して不正検出装置５３へ出力する（ステップＥ３）。【０１２０】
不正検出装置５３は、α個の乱数と分散情報のすべてについて、ｇ（ｒｉ）＝ｆｉ（ｉ＝ｋ＋ｊ；ｊ＝１〜α）なる関係が充たされるか否かを判定する（ステップＥ４）。【０１２１】
充たされている場合（ステップＥ５のＹｅｓ）には、ｇ（０）をメッセージ復元装置５４へ出力し（ステップＥ６）、充たされていない場合（ステップＥ５のＮｏ）には、不正の検出を表す信号をメッセージ復元装置５４へ出力する（ステップＥ７）。【０１２２】
メッセージ復元装置５４は、組合せ装置５１へ、次の組合せの入力を要求する信号を出力する（ステップＥ８）。【０１２３】
組合せ装置５１は、ｎ個の乱数及び分散情報の対から未選択のｋ＋α個の対の組合せがあるか否かを判定する（ステップＥ９）。【０１２４】
未選択の組合せがある場合（ステップＥ１０のＹｅｓ）、組合せ装置５１は、ｎ個の乱数及び分散情報の対から未選択のｋ＋α個の組み合わせを抽出し、ｋ個の対を多項式復元装置５２へ出力し、α個の対を不正検出装置５３へ出力した後（ステップＥ１１）、ステップＥ３へ戻る。【０１２５】
一方、未選択の組合せがない場合（ステップＥ１０のＮｏ）、組合せ装置５１は、すべての組合せを出力し終えたことを表す信号をメッセージ復元装置５４に出力する（ステップＥ１２）。【０１２６】
メッセージ復元装置５４は、不正の検出を表す記号を除き、すべての入力が等しいか否かを判定する（ステップＥ１３）。【０１２７】
等しい場合（ステップＥ１４のＹｅｓ）、その値をメッセージとして出力し（ステップＥ１５）、それ以外の場合には不正の検出を表す信号を出力する（ステップＥ１６）。
【実施例１】
【０１２８】
図１は、本発明の第１の実施例に係る秘密情報分散システムのブロック図である。【０１２９】
実施例１では、秘密情報のデータ集合に有限体ＧＦ（ｐ）を用いる。ＧＦ（ｐ）は素数又は素数のべき乗ｐに対する有限体である。【０１３０】
なお、閾値ｋと分割数ｎとｐはｋ≦ｎ≦ｐ−１を満足するものとする。【０１３１】
図１は、本発明の第１の実施例に係る分散情報生成システムのブロック図である。【０１３２】
図１を参照すると、分散情報生成装置１０は秘密情報Ｓ、閾値ｋ、分割数ｎを入力する。【０１３３】
分散情報生成装置１０に備えた乱数生成装置１２は分割数ｎを入力する。【０１３４】
乱数生成装置１２は、相異なるｒ１、…、ｒｎを１、…、Ｒ１（Ｒ１≦ｐ−１）からランダムに選び出し、秘密情報分散装置１１へ出力するとともに記憶装置３０−ｉへ乱数ｒｉを出力する（ｉ＝１、…、ｎ）。【０１３５】
分散情報生成装置１０に備えた秘密情報分散装置１１は、秘密情報Ｓ、閾値ｋ、分割数ｎを入力する。【０１３６】
秘密情報分散装置１１は、有限体ＧＦ（ｐ）上の定数項をＳとし、乱数によって生成された係数を備えた（ｋ−１）次多項式を生成する。これを、ｆ（ｘ）と記す。秘密情報分散装置１１は、記憶装置３０−ｉへｆ（ｒｉ）を出力する（ｉ＝１、…、ｎ）。【０１３７】
図１を参照すると、秘密情報復元装置２０は、閾値ｋ、パラメータαを入力する。【０１３８】
秘密情報復元装置２０に備えた多項式復元装置２１は閾値ｋを入力する。多項式復元装置２１は記憶装置３０−ｉのそれぞれに記録された、乱数ｒｉと分散情報ｆｉを入力する。多項式復元装置２１は、有限体ＧＦ（ｐ）上の（ｋ−１）次の多項式であって、座標（ｒｉ、ｆｉ）（ｉ＝１、…、ｋ）の各点を通るｇ（ｘ）を求め、求めたｇ（ｘ）を不正検出装置２２へ出力する。（ｋ−１）次の多項式の係数は、例えば、ｇ（ｒｉ）＝ｆｉ（ｉ＝１、…、ｋ）によって与えられるｋ本の方程式からなる線形連立方程式を解くことによって、一意に決定することができる。【０１３９】
秘密情報復元装置２０に備えた不正検出装置２２はパラメータαを入力する。不正検出装置２２は、さらに、記憶装置３０−（ｋ＋ｊ）（ｊ＝１、…、α）に記録された、乱数ｒｉと分散情報ｆｉ(ｉ＝ｋ＋１、…、ｋ＋α)を入力する。【０１４０】
不正検出装置２２は、上記の関数ｇ（ｘ）において、ｇ（ｒｉ）＝ｆｉ（ｉ＝ｋ＋１、…、ｋ＋α）が充たされるか否かを判定する。【０１４１】
すべてのｉ（＝ｋ＋１、…、ｋ＋α）について、上記の関係式が充たされている場合には、秘密情報として、ｇ（０）を出力する。一方、少なくともいずれかのｉ（＝ｋ＋１、…、ｋ＋α）について、上記の関係式が充たされない場合には不正を検出したことを表す信号を出力する。【０１４２】
実施例１において、秘密情報のサイズはｐ、分散情報のサイズはｐ＊Ｒ１、不正の検出率は１−（ｐ−１）（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ１−（ｋ−１））（Ｒ１−ｋ）…（Ｒ１−（ｋ＋α−１））となることが、以下において示される。【０１４３】
秘密情報は、０、…、ｐ−１のいずれかの値であるとする。【０１４４】
本発明の方法は、（１）秘密情報を定数項に持つｍｏｄ  ｐ上の（ｋ−１）次多項式ｆを生成し、（２）分散情報ごとにランダムな値を割り振り（ｒ１、…ｒｎとする）、（３）（ｒ１、ｆ（ｒ１））、…、（ｒｎ、ｆ（ｒｎ））を分散情報とする方法である。【０１４５】
この方法では、（ｋ＋α）個以上の分散情報を集め、秘密情報の復元及び復元された秘密情報の正しさの検証を以下の方法で行った後、ｋ個の分散情報によってｆを復元し、他のα個の分散情報がｆを通っていれば不正はなかったものとして、ｆの定数項を出力する。【０１４６】
この方法において、（ｒ１、ｆ（ｒ１））、…、（ｒｋ−１、ｆ（ｒｋ−１））を知っている不正者たちが、（ｒｋ、ｆ（ｒｋ））、（ｒｋ＋１、ｆ（ｒｋ＋１））、…、（ｒｋ＋α、ｆ（ｒｋ＋α））を所持している人をだまそうとしている状況を考える。なお、不正者たちは、（ｒｋ、ｆ（ｒｋ））、（ｒｋ＋１、ｆ（ｒｋ＋１））、…、（ｒｋ＋α、ｆ（ｒｋ＋α））を知らないものとする。【０１４７】
いま、不正者たちが、（ｒ１、ｆ（ｒ１））、…、（ｒｋ−１、ｆ（ｒｋ−１））を、改ざんして、（ｒ１’、ｆ１’）、…、（ｒｋ−１’、ｆｋー１’）を秘密情報復元装置２０へ入力した場合を考える。【０１４８】
点（ｒ１’、ｆ１’）、…、（ｒｋ−１’、ｆｋ−１’）及び（ｒｋ、ｆ（ｒｋ））によって復元された多項式が点（ｒｋ＋１、ｆ（ｒｋ＋１））、…、（ｒｋ＋α、ｆ（ｒｋ＋α））を通るとともに、ｆの定数項ｆ（０）が上記の秘密情報以外の０、…、ｐ−１のいずれかの値となった場合には、不正の成功となる。【０１４９】
秘密情報以外の０、…、ｐ−１のいずれかの値をｓ’とし、（ｒ１’、ｆ１’）、…、（ｒｋ−１’、ｆｋ−１’）及び（０、ｓ’）によって復元された多項式をｆ’とすると、ｆ’はｆとは異なる（ｋ−１）次多項式であるのでｆとｆ’の交点は高々（ｋ−１）個である。【０１５０】
よって、（ｒｋ、ｆ（ｒｋ））、（ｒｋ＋１、ｆ（ｒｋ＋１））、…、（ｒｋ＋α、ｆ（ｒｋ＋α））がすべてｆ’上の点であれば（ｒ１’、ｆ１’）、…、（ｒｋ−１’、ｆｋ−１’）、（ｒｋ、ｆ（ｒｋ））、（ｒｋ＋１、ｆ（ｒｋ＋１））、…、（ｒｋ＋α、ｆ（ｒｋ＋α））を用いて秘密情報を復元するとｓ’が復元される。【０１５１】
ここで、ｒｋ、ｒｋ＋１、…、ｒｋ＋αは、相異なる値がランダムに選ばれているので、ｒ１、ｒ２、…、ｒｋ＋αが、０、…、Ｒ１から選ばれるものとすると、ｓ’が復元される確率は高々（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ１−（ｋ−１））（Ｒ１−ｋ）…（Ｒ１−（ｋ＋α−１））となる。【０１５２】
ところで、秘密情報以外の値は（ｐ−１）通りあるので、結局、不正が成功する確率は、前述の式に（ｐ−１）をかけた（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ１−（ｋ−１））（Ｒ１−（ｋ））…（Ｒ１−（ｋ＋α−１））となる。【０１５３】
次に、本実施例に係る秘密情報復元方法と従来の方法とを比較する。【０１５４】
非特許文献１に開示された方法における分散情報のサイズは、秘密情報のサイズをｓとし、不正の検出率を（１−ε）とすると、ｓ／εである。【０１５５】
一方、非特許文献２に開示された方法における分散情報のサイズは、秘密情報のサイズをｓとし、不正の検出率を（１−ε）とすると、ｓ／ε２である。【０１５６】
ここで、ｋ＝２、α＝２、ｐ＝２４０、ε＝１／２８０とした場合について、具体的に検討する。【０１５７】
本実施例における分散情報のサイズは、α＝２の場合、およそ２８０となる。【０１５８】
一方、非特許文献１及び非特許文献２に開示された方法における分散情報のサイズは、それぞれ２１２０及び２２００となる。【０１５９】
したがって、本実施例に係る秘密情報復元方法における分散情報は、非特許文献１及び非特許文献２の方法における分散情報と比較してより少なく、効率良く不正を検出することができる。
【実施例２】
【０１６０】
本発明の第２の実施例に係る伝送システムについて、図面を参照して詳細に説明する。【０１６１】
第２の実施例においては、メッセージのデータ集合に対して有限体ＧＦ（ｐ）を用いる。ここで、ＧＦ（ｐ）は素数又は素数のべき乗ｐに対する有限体である。【０１６２】
なお、想定不正チャンネル数ｋとチャンネル数ｎとパラメータαとｐがｔ＝ｋ−１とすると２ｔ＋α＋１＝ｎとｎ≦ｐ−１を満足するものとする。【０１６３】
図２を参照すると、送信装置４０は、想定不正チャンネル数ｋ、チャンネル数ｎ、メッセージＳを入力する。【０１６４】
送信装置４０に備えた乱数生成装置４２は、チャンネル数ｎを入力する。乱数生成装置４２は、互いに異なるｒ１、ｒ２、…、ｒｎを、１、２、…、Ｒ１（Ｒ１≦ｐ−１）からランダムに選び出して、メッセージ分散装置４１及びチャンネル６０−ｉへｒｉ(ｉ＝１、…、ｎ)を出力する。【０１６５】
送信装置４０に備えたメッセージ分散装置４１は、メッセージＳ、想定不正チャンネル数ｋ、チャンネル数ｎを入力する。メッセージ分散装置４１は、有限体ＧＦ（ｐ）上の定数項をＳとする（ｋ−１）次多項式をランダムに生成する。これを、ｆ（ｘ）とする。メッセージ分散装置４１は、チャンネル６０−ｉへｆ（ｒｉ）（ｉ＝１、…、ｎ）を出力する。【０１６６】
チャンネル６０−ｉは、送信装置４０からの乱数ｒｉ、分散情報ｆ（ｒｉ）を入力するとともに、受信装置５０へ出力する（ｉ＝１、…、ｎ）。【０１６７】
受信装置５０には、想定不正チャンネル数ｋ、パラメータα、チャンネル６０−ｉからｒｉ、ｆ（ｒｉ）を入力する（ｉ＝１、…、ｎ）。【０１６８】
受信装置５０に備えた組合せ装置５１は、想定不正チャンネル数ｋ、パラメータα、乱数ｒｉ、分散情報ｆ（ｒｉ）を入力する（ｉ＝１、…、ｎ）。【０１６９】
組合せ装置５１は、１、…、ｎのｎ個の整数から成る集合から、（ｋ＋α）個を抽出した全ての組合せに対して、以下の処理を順番に実行する。【０１７０】
いま、注目する組合せは、（ｋ＋α）個の整数、ｉ（１）、…、ｉ（ｋ＋α）であるものとする。このとき、組合せ装置５１は、ｒｉ（１）、…、ｒｉ（ｋ）とｆｉ（１）、…、ｆｉ（ｋ）を多項式復元装置５２へ出力し、残りのｒｉ（ｋ＋１）、…、ｒｉ（ｋ＋α）とｆｉ（ｋ＋１）、…、ｆｉ（ｋ＋α）を不正検出装置５３へ出力する。【０１７１】
多項式復元装置５２は、座標（ｒｉ（１）、ｆｉ（１））、…、（ｒｉ（ｋ）、ｆｉ（ｋ））を通るＧＦ（ｐ）上の次数（ｋ−１）の多項式ｇ（ｘ）を求めて、不正検出装置５３へ出力する。【０１７２】
不正検出装置５３は、ｇ（ｒｉ（ｋ＋１））＝ｆｉ（ｋ＋１）、…、ｇ（ｒｉ（ｋ＋α））＝ｆｉ（ｋ＋α）が充たされるか否かを判定する。充たされている場合、不正検出装置５３は、ｇ（０）をメッセージ復元装置５４へ出力する。一方、充たされていない場合には、不正を検出したことを表す信号をメッセージ復元装置５４へ出力する。【０１７３】
メッセージ復元装置５４は、不正の検出を表す信号を除き、不正検出装置５３からの出力の値がすべて等しい場合には、その値を出力し、それ以外の場合には不正の検出を表す信号を出力する。【０１７４】
以下で示すように、実施例２におけるメッセージの情報のサイズはｐ＊Ｒ１、不正の検出率は１−（ｐ−１）（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ１−（ｋ−１））（Ｒ１−ｋ）…（Ｒ１−（ｋ＋α−１））となる。【０１７５】
秘密情報（すなわち、メッセージ）は、０、…、ｐ−１のうちいずれかの値であるものとする。【０１７６】
本実施例において、単位チャンネルごとに送られている情報は、上記の実施例１の秘密分散システムにおいて記憶装置に記憶されていた情報と等しく、情報のサイズはｐ＊Ｒ１となる。【０１７７】
不正者によって、情報を改ざんされ得るチャンネル数は、想定不正チャンネル数ｋから１を引いた数であるので、（ｋ−１）本である。【０１７８】
つまり、（α＋１）本分のチャンネルを流れる情報は改ざんされていないことになる。【０１７９】
受信装置の処理は、すべての（ｋ＋α）本のチャンネルの情報に対し、実施例１の秘密分散システムの復元処理を行うものに等しく、改ざんされていない（ｋ＋α）本のチャンネルからは正しいメッセージが復元される。【０１８０】
また、情報が改ざんされているチャンネルの混ざった（ｋ＋α）本のチャンネルでも少なくとも（α＋１）本の改ざんされていないチャンネルの情報が含まれている。【０１８１】
よって、不正を１−（ｐ−１）（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ＿１−（ｋ−１））（Ｒ１−ｋ）…（Ｒ１−（ｋ＋α−１））の確率で検出することができる。【０１８２】
改ざんされた情報を含むｋ＋α本のチャンネルの組の数をＡとすると、改ざんされた情報を含むｋ＋α本のチャンネルの組をすべて検出できる確率は１−Ａ（ｐ−１）（ｋ−１）（ｋ−２）…（ｋ−（１＋α））／（Ｒ１−（ｋ−１））（Ｒ１−ｋ）…（Ｒ１−（ｋ＋α−１））となる。【０１８３】
本実施例に係る伝送システムにおいては、仮に、改ざんされた情報を含む（ｋ＋α）本のチャンネルの一組を検出できず、その組から本来のメッセージとは異なる値が復元されたとしても、正しい値と異なる値も復元される上、複数の値が復元された場合には、メッセージ送信失敗とみなされるため、異なる復元値を正しい値と誤認することはない。【０１８４】
非特許文献１の方法を秘密情報のサイズをｓ、不正の検出率を（１−ε）として、非特許文献４の方法へ適用した場合、チャンネルごとに送られる情報のサイズはｓ／εとなる。【０１８５】
一方、非特許文献２の方法を秘密情報のサイズをｓ、不正の検出率を（１−ε）として、非特許文献４の方法へ適用した場合、チャンネルごとに送られる情報のサイズはｓ／ε２となる。【０１８６】
ここで、ｋ＝２、α＝２、ｐ＝２４０、ε＝１／２８０とすると、本実施例に係る伝送システムにおける分散情報のサイズは、およそ２８０となる。一方、非特許文献１及び非特許文献２に開示された方法において、チャンネルごとに送られる情報のサイズは、およそ２１２０及び２２００となる。【０１８７】
したがって、非特許文献１及び非特許文献２に開示された方法と比較して、本実施例に係る伝送システムにおける分散情報は少ないことが分かる。【０１８８】
また、上記の説明においては、複数のチャンネルを用いた場合を例として説明したが、チャンネルは複数である必要はなく、送信装置４０の生成した複数のデータを分割して、組合せ装置５１へ送信することができるものであればよい。【０１８９】
以上の記載は実施例に基づいて行ったが、本発明は、上記実施例に限定されるものではない。【０１９０】
以上、本発明を上記実施の形態に即して説明したが、本発明は、上記実施の形態の構成のみに限定されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2009025220.tif 000003
【図２】
2009025220.tif 000004
【図３】
2009025220.tif 000005
【図４】
2009025220.tif 000006
【図５】
2009025220.tif 000007
【図６】
2009025220.tif 000008
【図７】
2009025220.tif 000009
【図８】
2009025220.tif 000010
【手続補正書】
【提出日】平成21年4月28日(2009.4.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元装置であって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）を記憶する記憶部と、
αを自然数として（ｋ＋α）個の対（ｒｉ、ｆｉ）を前記記憶部から読み出し、読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する不正検出部と、を備えることを特徴とする秘密情報復元装置。
【請求項２】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を受信する受信部をさらに備え、
前記不正検出部は、受信した全ての対について前記判定を行い、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力することを特徴とする、請求項１に記載の秘密情報復元装置。
【請求項３】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として、（ｋ＋α）個の対の受信し、受信した全ての対についての前記判定をｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返し、前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力することを特徴とする、請求項１に記載の秘密情報復元装置。
【請求項４】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散システムであって、
請求項１ないし３のいずれか１項に記載の秘密情報復元装置を備えるとともに、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成し、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する分散情報生成装置をさらに備えたことを特徴とする秘密情報分散システム。
【請求項５】
メッセージを送信する送信装置とメッセージを受信する受信装置とを備えた伝送システムであって、
前記送信装置は、請求項４に記載の秘密情報分散システムにおける分散情報生成装置を備え、前記メッセージを前記秘密情報として送信し、
前記受信装置は、請求項１ないし３のいずれか１項に記載の秘密情報復元装置を備え、前記乱数及び前記分散情報から復元された秘密情報としてメッセージを受信し、又は、改ざんが行われたことを検出することを特徴とする伝送システム。
【請求項６】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元方法であって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を記憶装置から読み出す工程と、
読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する工程と、を含むことを特徴とする秘密情報復元方法。
【請求項７】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を受信する工程と、
受信した全ての対についての前記判定工程と、
復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程と、を含むことを特徴とする、請求項６に記載の秘密情報復元方法。
【請求項８】
前記受信工程及び前記判定工程を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す工程をさらに含み、
前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程を含むことを特徴とする、請求項７に記載の秘密情報復元方法。
【請求項９】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散方法であって、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する工程と、
乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する工程と、を含み、
請求項７又は８に記載の秘密情報復元方法における前記受信工程、前記判定工程及び前記出力工程又は前記受信工程、前記判定工程、前記繰り返し工程及び前記出力工程を含むことを特徴とする秘密情報分散方法。
【請求項１０】
（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する処理をコンピュータに実行させるプログラムであって、
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を記憶装置から読み出す処理と、
読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する処理と、をコンピュータに実行させることを特徴とするプログラム。
【請求項１１】
乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する処理と、
受信した全ての対についての前記判定処理と、
復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理と、をコンピュータに実行させることを特徴とする、請求項１０に記載のプログラム。
【請求項１２】
前記受信処理及び前記判定処理を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す処理をさらにコンピュータに実行させ、
前記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理をコンピュータに実行させることを特徴とする、請求項１１に記載のプログラム。
【請求項１３】
（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元するプログラムであって、
秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する処理と、
乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する処理と、をコンピュータに実行させ、
請求項１１又は１２に記載の秘密情報復元プログラムにおける前記受信処理、前記判定処理及び前記出力処理又は前記受信処理、前記判定処理、前記繰り返し処理及び前記出力処理をコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
乱数ｒｉと分散情報ｆｉからなる対（ｒｉ、ｆｉ）をαを自然数として（ｋ＋α）組受信し、ｆｉ＝ｇ（ｒｉ）を満たす（ｋ−１）次多項式ｇを復元できるか否かを判定し、復元できなかった場合には受信した対のいずれかが改ざんされた旨を出力する秘密情報復元装置。
【請求項１５】
前記分散情報ｆｉは、前記乱数ｒｉを利用して（ｋ、ｎ）閾値秘密分散法によって生成される、請求項１４記載の秘密情報復元装置。
【請求項１６】
前記判定を行い、復元できた場合にはｇ（０）を秘密情報を出力する、請求項１４又は１５に記載の秘密情報復元装置。
【請求項１７】
乱数ｒｉと分散情報ｆｉからなるｎ組の対（ｒｉ、ｆｉ）を受信し、αを自然数として、ｎ組以下の（ｋ＋α）組の対を選ぶすべての組み合わせについてｆｉ＝ｇ（ｒｉ）を満たす（ｋ−１）次多項式ｇを復元できるか否かを判定し、復元できた組み合わせすべてのｇ（０）が等しい場合にはｇ（０）を出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する秘密情報復元装置。
【請求項１８】
請求項１４乃至１６のいずれか１項に記載の秘密情報復元装置を備えるとともに、秘密情報を入力し、これを定数項として含む所定の（ｋ−１）次多項式ｆ（ｘ）を生成し、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する分散情報生成装置をさらに備える秘密情報分散システム。
【請求項１９】
メッセージを送信する送信装置とメッセージを受信する受信装置とを備えた伝送システムであって、
前記送信装置は、請求項１８に記載の分散情報生成装置を備え、前記メッセージを入力として出力である乱数ｒｉと分散情報ｆｉの組であるｒｉ、ｆｉをｎ組送信し、
前記受信装置は請求項１４乃至１７のいずれか１項に記載の秘密情報復元装置を備え、これに送信装置の出力であるｒｉとｆｉの組を入力とし、その出力が秘密情報であった場合にはそれをメッセージとして出力し、それ以外の場合には改ざんが行われたことを検出する伝送システム。
【請求項２０】
乱数ｒｉと分散情報ｆｉからなる対（ｒｉ、ｆｉ）をαを自然数として（ｋ＋α）組受信する工程と、
ｆｉ＝ｇ（ｒｉ）を満たす（ｋ−１）次多項式ｇを復元できるか否かを判定し、復元できなかった場合には受信した対のいずれかが改ざんされた旨を出力する工程と、を含む秘密情報復元方法。
【請求項２１】
乱数ｒｉと分散情報ｆｉからなる対（ｒｉ、ｆｉ）をαを自然数として（ｋ＋α）組受信する処理と、
ｆｉ＝ｇ（ｒｉ）を満たす（ｋ−１）次多項式ｇを復元できるか否かを判定し、復元できなかった場合には受信した対のいずれかが改ざんされた旨を出力する処理と、をコンピュータに実行させるプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  Ｃｏｄｅｓ”、Ｃｏｍｍ．ＡＣＭ、２４、ｐ．５８３−５８４（１９８１）
発明の開示
発明が解決しようとする課題
［００３５］
なお、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者によってなされたものである。
［００３６］
従来の「不正検出可能な秘密分散法」は、不正を検出するために、多くの分散情報を処理する必要があり、効率が悪いという問題があった。
［００３７］
そこで、（ｋ、ｎ）閾値秘密分散法において、分散情報に基づいて秘密情報を復元する際に、分散情報等に対して行われた不正を、少ない情報量の分散情報に基づいて効率よく検出する方法を提供することが課題となる。
課題を解決するための手段
［００３８］
本発明の第１の視点に係る秘密情報復元装置は、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元装置であって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）を記憶する記憶部と、αを自然数として（ｋ＋α）個の対（ｒｉ、ｆｉ）を前記記憶部から読み出し、読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する不正検出部と、を備えることを特徴とする。また、秘密情報復元装置は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を受信する受信部をさらに備え、不正検出部は、受信した全ての対について上記判定を行い、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力するようにしてもよい。
［００３９］
本発明の第２の視点に係る秘密情報復元方法は、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する秘密情報復元方法であって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を記憶装置から読み出す工程と、読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する工程と、を含むことを特徴とする。また、秘密情報復元方法は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する工程と、受信した全ての対につい
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
ての上記判定工程と、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程と、を含むようにしてもよい。
［００４０］
本発明の第３の視点に係るプログラムは、（ｋ、ｎ）閾値秘密分散法によって生成された分散情報に基づいて秘密情報を復元する処理をコンピュータに実行させるプログラムであって、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として（ｋ＋α）個の対を記憶装置から読み出す処理と、読み出した対についてｆｉ＝ｇ（ｒｉ）を充たす（ｋ−１）次多項式ｇ（ｘ）を復元することができるか否かを判定する処理と、をコンピュータに実行させることを特徴とする。また、プログラムは、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうち、αを自然数として（ｋ＋α）個の対を受信する処理と、受信した全ての対についての上記判定処理と、復元することができた場合にはｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理と、をコンピュータに実行させてもよい。
［００４１］
第１の展開形態の秘密情報復元装置は、乱数ｒｉと分散情報ｆｉとからなるｎ個の対（ｒｉ、ｆｉ）のうちのαを自然数として、（ｋ＋α）個の対の受信し、受信した全ての対についての上記判定をｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返し、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力することが好ましい。
［００４２］
第２の展開形態の秘密情報分散システムは、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散システムであって、上記の秘密情報復元装置を備えるとともに、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成し、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する分散情報生成装置をさらに備えることが好ましい。
［００４３］
第３の展開形態の伝送システムは、メッセージを送信する送信装置とメッセージを受信する受信装置とを備えた伝送システムであって、上記送信装置は、上記の分散情報生成装置を備え、上記メッセージを上記秘密情報として送信し、上記受信装置
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
は、上記の秘密情報復元装置を備え、上記乱数及び上記分散情報から復元された秘密情報としてメッセージを受信し、又は、改ざんが行われたことを検出することが好ましい。
［００４４］
第４の展開形態の秘密情報復元方法は、上記受信工程及び上記判定工程を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す工程をさらに含み、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する工程を含むことが好ましい。
［００４５］
第５の展開形態の秘密情報分散方法は、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元する秘密情報分散方法であって、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する工程と、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する工程と、を含み、上記の秘密情報復元方法における上記受信工程、上記判定工程及び上記出力工程又は上記受信工程、上記判定工程、上記繰り返し工程及び上記出力工程を含むことが好ましい。
［００４６］
第６の展開形態のプログラムは、上記受信処理及び上記判定処理を、ｎ個の対から（ｋ＋α）個の対を選ぶすべての組合せについて繰り返す処理をさらにコンピュータに実行させ、上記組合せのすべてにおいて復元されたｇ（０）の値が等しい場合に限り、ｇ（０）を秘密情報として出力し、それ以外の場合には受信した対のいずれかが改ざんされた旨を出力する処理をコンピュータに実行させることが好ましい。
［００４７］
第７の展開形態のプログラムは、（ｋ、ｎ）閾値秘密分散法によって分散情報を生成するとともに、分散情報に基づいて秘密情報を復元するプログラムであって、秘密情報を定数項として含む所定の（ｋ−１）次の多項式ｆ（ｘ）を生成する処理と、乱数ｒｉと分散情報ｆ（ｒｉ）とから成るｎ個の対（ｒｉ、ｆ（ｒｉ））を生成して出力する処理と、をコンピュータに実行させ、上記のプログラムにおける上記受信処理、上記判定処理及び上記出力処理又は上記受信処理、上記判定処理、上記繰り返し処理及び上記出力処理をコンピュータに実行させることが好ましい。
発明の効果
［００４８］
本発明の秘密情報復元方法においては、従来よりも少ない情報量の分散情報に
【国際調査報告】
2009025220.tif 000011
2009025220.tif 000012
2009025220.tif 000013
2009025220.tif 000014
2009025220.tif 000015
2009025220.tif 000016
2009025220.tif 000017
2009025220.tif 000018