(57)【要約】【課題】  加重された秘密分散及び復元方法を提供する。【解決手段】  秘密情報を所定コードで符号化する段階と、エラーベクトルのエラー位置によってエラーを加重する重みとなるボイスを生成する段階と、エラーベクトルを利用してコードを暗号化して複数の参加者に配布する段階と、を含むことを特徴とする秘密分散方法。これにより、均等でないエラー訂正能力を持つエラー訂正コードを使用することによって、秘密分散をウェイトの大きさに頼らない方式で実現できる。また、加重秘密分散方式のための構成が従来技術に比べて比較的簡単である。【選択図】      図２
2005117670.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報を所定コードで符号化する段階と、
エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成する段階と、
前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布する段階と、
を含むことを特徴とする秘密分散方法。
【請求項２】
前記コードは、
前記コードの生成多項式から決定される相異なる長さのコードブロックが連接した形態に配列されるコードワードを持つことを特徴とする請求項１に記載の秘密分散方法。
【請求項３】
前記ボイスは、
前記エラーベクトルで前記コードブロック別に対応するエラー値に対して相異なって加重されるように設定されることを特徴とする請求項２に記載の秘密分散方法。
【請求項４】
秘密情報を所定コードで符号化し、エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成し、前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布された秘密情報を復元する方法において、
全体ボイスのうち前記コードの復号化に必要なボイス数を設定する段階と、
前記設定されたボイス数による参加者を決定する段階と、
決定された参加者から配布された秘密情報を回収する段階と、
前記秘密情報を復号化し、エラー訂正復号化して復元する段階と、を含むことを特徴とする秘密復元方法。
【請求項５】
前記設定されたボイス数は、
前記生成されたボイスを持つ参加者の数と該当ボイスの積との和であることを特徴とする請求項４に記載の秘密復元方法。
【請求項６】
前記エラー訂正復号化は、前記復号化後に残っているエラーと各エラーに対応するボイスの積とを合せたものより大きいか、または同じ数のエラーを訂正することを特徴とする請求項４に記載の秘密復元方法。
【請求項７】
秘密情報を所定コードで符号化する段階と、
エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成する段階と、
前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布する段階と、
全体ボイスのうち前記コードの復号化に必要なボイス数を設定する段階と、
前記設定されたボイス数による参加者を決定する段階と、
決定された参加者から配布された秘密情報を回収する段階と、
前記秘密情報を復号化し、エラー訂正復号化して復元する段階と、を含むことを特徴とする秘密分散及び復元方法。
【請求項８】
前記コードは、
前記コードの生成多項式から決定される相異なる長さのコードブロックが連接した形態に配列されるコードワードを持つことを特徴とする請求項７に記載の秘密分散及び復元方法。
【請求項９】
前記ボイスは、
前記エラーベクトルで前記コードブロック別に対応するエラーに対して相異なって加重されるように設定されることを特徴とする請求項８に記載の秘密分散及び復元方法。
【請求項１０】
前記設定されたボイス数は、
前記コードブロックに対応して生成されたボイスと該当ボイスを持つ参加者の数の積との和であることを特徴とする請求項９に記載の秘密分散及び復元方法。
【請求項１１】
前記全体ボイス数は、
前記コードブロックが持つウェイトと前記コードブロックに対応するボイスの積との和であることを特徴とする請求項８に記載の秘密分散及び復元方法。
【請求項１２】
前記エラー訂正復号化は、前記復号化後に残っているエラーと各エラーに対応するボイスの積とを合せたものより大きいか、または同じ数のエラーを訂正することを特徴とする請求項７に記載の秘密分散及び復元方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は加重された秘密分散及び復元方法に係り、特に加重されたエラーベクトルを利用して秘密（秘密情報）を分散（共有）及び復元する方法に関する。
【背景技術】
【０００２】
Ｎ人の参加者からなるセット（集合）Ｒと、参加者のサブセット（部分集合）からなるセットＬとがある時、しきい値秘密分散法は、各参加者に秘密（秘密情報）の分散された情報であるシェア（分散情報）を分配した後、データの復元時に参加者のサブセットがＬに含まれていれば秘密を復元でき、参加者のサブセットがＬに含まれていなければ秘密を復元できない方式（方法）である。
【０００３】
理想的なしきい値秘密分散法の特性は次の通りである。各参加者はセットＲの鍵共有に参加する。すべての参加者はセットＲのマスター秘密鍵を知らない。少なくとも予め定められた数（しきい値）の参加者がマスター秘密鍵により暗号化されたメッセージの復号化過程に参加する。少なくとも予め定められた数（しきい値）の参加者がマスター秘密鍵によるメッセージの署名過程に参加する。これらの過程による設定を行った後は、Ｌに含まれるサブセットに含まれる参加者による復号化または署名過程は相互に関連しない。新たな参加者がセットＲに発生した場合にもマスター秘密鍵及び公開鍵は変更されてはならない。セットＲに含まれた参加者が離脱する場合にもマスター秘密鍵及び公開鍵は変更されてはならない。
【０００４】
しきい値秘密分散法の他の例として、（ｋ，Ｎ）しきい値秘密分散法がある。この方法によれば、Ｎ個の秘密のシェアのうちｋ個の分散されたシェアを収集すれば秘密を復元できる。図１は、（ｋ，Ｎ）しきい値秘密分散法を示す概念図である。図示されたように、秘密（秘密情報）１０はＮ人（ここでは５人）の参加者１１に同じ重要度で分配される。秘密の復元時にはＮ人の参加者のうち少なくともｋ人（ここでは３人）から分配された秘密のシェアを受けて結合する（結合１２）ことによって秘密（秘密情報）１３を復元する。
【０００５】
しかし、（ｋ，Ｎ）しきい値秘密分散法は、Ｎ人の参加者に同じ重要度を持つ秘密を分配するため秘密の復元には必ずｋ個の秘密のシェアが必要であり、（ｋ−１）個のシェアが結合された場合、秘密を完全に復元できないという問題が生じる。
また階層的なしきい値方式、すなわち、マルチレベルからなる構造に対して秘密を各レベルに共有する方式の場合、マルチレベルの構造にアクセスしようとする参加者に階層的な権限を付与することを考慮せねばならない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとする技術的課題は、秘密を分散する時に参加者の加重値を相異ならせて（ｋ−１）個の分散された秘密のシェアを結合するだけで、秘密を完全に復元できる加重された秘密分散及び復元方法を提供するところにある。
【課題を解決するための手段】
【０００７】
前記技術的課題を解決するための、本発明の秘密分散方法は、秘密情報を所定コードで符号化する段階と、エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成する段階と、前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布する段階と、を含むことを特徴とする。
【０００８】
前記技術的課題を解決するための、本発明の秘密復元方法は、秘密情報を所定コードで符号化し、エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成し、前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布された秘密情報（分散情報）を復元するものであって、全体ボイスのうち前記コードの復号化に必要なボイス数を設定する段階と、前記設定されたボイス数による参加者を決定する段階と、決定された参加者から配布された秘密情報（分散情報）を回収する段階と、前記秘密情報を復号化し、エラー訂正復号化して復元する段階と、を含むことを特徴とする。
【０００９】
前記技術的課題を解決するための、本発明の秘密分散及び復元方法は、秘密情報を所定コードで符号化する段階と、エラーベクトルのエラー位置によってエラー値を加重する重みとなるボイスを生成する段階と、前記エラーベクトルを利用して前記コードを暗号化して複数の参加者に配布する段階と、全体ボイスのうち前記コードの復号化に必要なボイス数を設定する段階と、前記設定されたボイス数による参加者を決定する段階と、決定された参加者から配布された秘密情報を回収する段階と、前記秘密情報を復号化し、エラー訂正復号化して復元する段階と、を含むことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、均等でないエラー訂正能力を持つエラー訂正コードを使用することによって、秘密分散をウェイトの大きさに頼らない方式で実現できる。また、加重秘密分散方式のための構成が従来技術に比べて簡単である。
【発明を実施するための最良の形態】
【００１１】
以下、添付された図面を参照して本発明をより詳細に説明する。
図２は、本発明による秘密分散法である（ｋ，Ｎ）しきい値秘密分散法を示す概念図である。図示されたように、秘密（秘密情報；以下単に秘密という）２０はＮ人の参加者２１にそれぞれ相異なる加重値を置いて分配される。秘密の復元時にはＮ人の参加者のうち加重された秘密のシェア（分散情報）を持つ参加者１人を含む２人から分配された秘密を受けて結合するか、または加重された秘密のシェアを持っていない参加者３人から分配された秘密を受けて結合する（結合２２）ことによって秘密（秘密情報）２３を復元する。
【００１２】
これをより詳細に説明すれば次の通りである。
秘密Ｓに対するＮ個の秘密のシェアが、チャンネル（ある伝達経路）を通じて内部的に連結されているＮ人の参加者にそれぞれ分配される。秘密ＳはＭｃＥｌｉｅｃｅ方式によってエラーベクトルｅを使用して暗号化されて分配される。
あらゆる参加者は秘密Ｓにアクセスできる。エラーベクトルの各位置ｉに対して各秘密のシェアｓi（ｉ＝１，…，Ｎ）は次の（１）式のようなウェイト（重み）ｗｔ τiを持つ。
【００１３】
【数１】
2005117670.tif 000003
【００１４】
ここで、Ｔはエラーベクトル全体が持つウェイト（重み）である。
この方式によれば、秘密のシェア受信者のうち１人が秘密を復元しようとする場合、自身の秘密のシェアと（ｋ−１）個の秘密のシェアとを使用して復元するようになり、その時のウェイトは次の（２）式のように表現される。
【００１５】
【数２】
2005117670.tif 000004
【００１６】
ここで、ｋは秘密復元のために必要な最小の秘密のシェアである。
秘密復元過程は次の通りである。まず、ある参加者が他の（ｋ−１）人の参加者から公開通信チャンネルを利用して（ｋ−１）個の符号化された秘密のシェアを回収する。回収された秘密のシェアと自分の秘密のシェアとを結合しかつ復号化して秘密を復元する。
秘密の符号化及び復号化のために、本発明では一般化されたゴッパ（Ｇｏｐｐａ）コードを使用する。
長さｎのｑ進（ｑ−ａｒｙ）一般化されたゴッパコードはｎタイプベクトルａ＝（ａ1ａ2…ａn）で次の（３）式のように定義される。
【００１７】
【数３】
2005117670.tif 000005
【００１８】
ここで、ａi∈ＧＦ（ｑ）である。Ｖi（ｘ）、Ｕi（ｘ）がＧＦ（ｑm）上の多項式である時にロケータセットＬは次の（４）式で表現される。
【００１９】
【数４】
2005117670.tif 000006
【００２０】
この時、ＧＣＤ（（Ｕi（ｘ），Ｖi（ｘ））＝１，ｄｅｇＶi（ｘ）＜ｄｅｇＵi（ｘ），ＧＣＤ（（Ｕi（ｘ），Ｕj（ｘ））＝１（ｉ≠ｊ）である。ＧＣＤは最大公約数であり、ｄｅｇは該当多項式の最高次数である。ｇ（ｘ）はあらゆるｉに対してＧＣＤ（（Ｕi（ｘ），ｇ（ｘ））＝１を満足するＧＦ（ｑm）上のゴッパ多項式である。
一般化された（Ｌ，ｇ）ゴッパコードはｄが次の（５）式
【００２１】
【数５】
2005117670.tif 000007
【００２２】
を満足する時に最小距離ｄ0≧ｄを持つ。
エラーを訂正できる一般化されたゴッパコードは次のように説明されうる。ゴッパ多項式Ｇ（ｘ）に対してロケータセットＬは次の（６）式のように決定される。
【００２３】
【数６】
2005117670.tif 000008
【００２４】
ここで、Ｒi(j)は有理関数であって次の（７）式のように表現される。
【００２５】
【数７】
2005117670.tif 000009
【００２６】
ここで、ｄｅｇ Ｖi(j)（ｘ）＝ｒi，ｄｅｇ Ｕi(j)（ｘ）＝τiであり、任意のｉ、ｒ、ｋ、ｊに対して（Ｖi(j)（ｘ），Ｕr(k)（ｘ））＝１である。
また、以下の（８）式に示すベクトルａが、長さｎ＝ｎ1＋ｎ2＋…＋ｎlである一般化された（Ｌ，ｇ）ゴッパコードのコードワードであれば、これに対するゴッパ多項式ｇ（ｘ）及びロケータセットＬが以下の（９）式を満足せねばならない。
【００２７】
【数８】
2005117670.tif 000010
【００２８】
【数９】
2005117670.tif 000011
【００２９】
このようなコードに対して最小距離を推定することが可能である。ゴッパ多項式ｇ（ｘ）、ロケータセットＬを持つ一般化されたゴッパコードは各コードブロック
【００３０】
【数１０】
2005117670.tif 000012
【００３１】
に対して次の（１０）式のような条件を満足する任意のエラーセットＴ＝｛ｔ1，ｔ2，…，ｔl｝を訂正できる。
【００３２】
【数１１】
2005117670.tif 000013
【００３３】
ここで、ｔ1，ｔ2，…，ｔlはそれぞれコードブロックの長さｎ1，ｎ2，…，ｎlのコードに含まれたエラー数である。
２進一般化されたゴッパコードの場合、（１０）式の（ｄｅｇ ｇ（ｘ））／２は（２ｄｅｇ ｇ（ｘ））／２に変換される。
例えば、ｎ1＝８、ｎ2＝２８であり、ゴッパ多項式がｇ（ｘ）＝ｘ6＋ｘ＋α3（但し、α∈ＧＦ（２3））である（３６，１８，７）の一般化されたゴッパコードを仮定する。
長さｎ1に対して次の（１１）式のような１次関数を使用する。
【００３４】
【数１２】
2005117670.tif 000014
【００３５】
長さｎ2に対して係数がＧＦ（２3）に属し、ＧＦ（２3）下では既約的な次のような２次多項式をいずれも使用する。
【００３６】
【数１３】
2005117670.tif 000015
【００３７】
前記（５）式によりｄ≧７であり、このコードは（２ｄｅｇ ｇ（ｘ））／２≧ｔ1＋２ｔ2を満足するＴ＝｛ｔ1，ｔ2｝のエラーを訂正できる。ｔ1及びｔ2の範囲は次の表の通りである。
【００３８】
【表１】
2005117670.tif 000016
【００３９】
３次多項式のロケータセットを持つ場合、長さがｎ＝ｎ1＋ｎ2＋ｎ3である一般化されたゴッパコードは同じく（２ｄｅｇ ｇ（ｘ））／２≧ｔ1＋２ｔ2＋３ｔ3を満足するエラーセットＴ＝｛ｔ1，ｔ2，ｔ3｝を訂正できる。
このようなゴッパコードを使用して公開鍵方式を利用したしきい値秘密分散法を具現できる。参加者はすべて公開されたエラーベクトルｅを知っている。コードパラメータを適当に選択してＮ＝ｗｔ（ｅ）の（ｋ，Ｎ）しきい値秘密分散法を具現できる。また、エラー訂正コードは（ｄ−１）より小さいか、または同じ数のエラーを訂正できる。したがって、参加者はｗｔ（ｅ）−ｋ≦（ｄ−１）／２、すなわち２ｋ≧２ｗｔ（ｅ）−ｄ＋１を満足する少なくともｋ人が秘密の復号化に参加せねばならない。ここで、ゴッパコードを利用する場合に最小距離ｄはｄ≦ｄｅｇ ｇ（ｘ）＋１であり、分離可能なゴッパ多項式ｇ（ｘ）を持つ２進ゴッパコードに対してｄはｄ≦２（ｄｅｇ ｇ（ｘ））＋１となる。
【００４０】
一般的に、秘密復元過程に参加する参加者のうち自分が持っている秘密のシェアに対して誤った値を与える場合がありうる。例えば、ｋ1の参加者は正しい値を与え、ｋ2の参加者が誤った値を与えた場合、次の（１３）式が成立する。
【００４１】
【数１４】
2005117670.tif 000017
【００４２】
このようなシステムは参加者が相異なる数のボイスを持っている場合に一般化できる。この時、ボイスはシェアとは異なる概念であって一つのシェアは複数のボイスを含みうる。
例えば、エラー訂正可能な一般化されたゴッパコードを使用するならば、各参加者に対応するボイスはロケータの次数として決定されうる。ここでロケータ次数は、エラーベクトルのエラー位置ｊに対応して使われるものとして参加者に知られる値である。この場合、次のような条件によって（ｋ，Ｔ）または（Ｋ，Ｎ）のような加重秘密分散法を具現できる。
【００４３】
Ｔはシステムで全体におけるボイス数を示すものであって、エラーベクトルの加重されたウェイトと同様である。すなわち、Ｔ＝ｔ1τ1＋ｔ2τ2＋…ｔlτlである。ここでｔiはτ1の次数を持つロケータ多項式の位置に対応するエラーベクトルｅのノンゼロ値（エラー値）の数である。Ｎは参加者の数であって、Ｎ＝ｔ1＋ｔ2＋…ｔlである。ｋは秘密復元過程に参加せねばならないボイスの数であって、ｋ＝ｋ1τ1＋ｋ2τ2＋…ｋlτlである。ここでｋiはτ1のボイスを持つ参加者の数であり、ｋ≧Ｔ−（ｄｅｇ ｇ（ｘ））／２を満足する値である。分離可能なゴッパ多項式を持つ２進ゴッパコードの場合にｋはｋ≧Ｔ−（ｄｅｇ ｇ（ｘ））である。Ｋは秘密復元過程に参加せねばならない参加者数であって、Ｋ＝ｋ1＋ｋ2＋…＋ｋlである。
【００４４】
したがって、本発明では秘密を復元するためにｋ個の秘密のシェアではないｋ個のボイスが必要であり、参加者は相異なる数のボイスを持つことができる。秘密のシェアの大きさはウェイトまたはボイスの数とは関係がない。
【００４５】
図３は、本発明による秘密分散及び復元方法を示すフローチャートである。図示されたように、秘密はエラー訂正コード、望ましくは一般化されたゴッパコードで符号化される（３０段階）。生成されたコードは、一般化されたゴッパコードでロケータセットにより決定されるコードブロックのように相異なる長さの複数のコードブロックが連接されている形態になる。生成された各コードブロックに対応してエラーベクトルのエラー位置によるボイスを生成する（３１段階）。エラーベクトルは、３０段階で生成されたコードブロックに対応するエラー位置によって相異なるボイスを持つ。例えば、３０段階で生成されたコードの長さがｎ＝ｎ1＋ｎ2であれば、エラーベクトルでｎ1に該当するエラーにはボイスが１、その次のｎ2に該当するエラーにはボイスが２に与えられる。エラーベクトルに対するボイスが生成されれば、３０段階で生成されたコードにエラーベクトルを加えて暗号化し、Ｎ＝ｗｔ（ｅ）人の参加者に配布する（３２段階）。
【００４６】
秘密の復元過程は次の通りである。まず、全体ボイスのうち復号化に必要なボイス数、すなわち（ｋ，Ｔ）を設定する（３３段階）。設定されたボイス数による参加者ｋiを決定する（３４段階）。例えば、（ｋ＝５，Ｔ＝１１）ならば、Ｎ＝９に対してｔ1＝７、ｔ2＝２であり、それにより（ｋ1，ｋ2）はｋ1＋２ｋ2＝ｋにより（１，２）、（３，１）、（５，０）の組合わせになりうる。この組合わせはそれぞれ（Ｋ＝３，Ｎ＝９）、（Ｋ＝４，Ｎ＝９）、（Ｋ＝５，Ｎ＝９）の方式である。すなわち、参加者数が異なってもボイスを利用して復元するため同じ復元結果を得られる。
参加者が決定されれば該当参加者から秘密を回収し（３５段階）、回収された秘密に対して復号化し、エラー訂正復号化して秘密を復元する（３６段階）。
【００４７】
図４ないし図７は、本発明による加重秘密分散による秘密復元過程を示した図面である。
図４は、エラー訂正可能な総ウェイトが３である時に秘密の符号化を説明する図面である。図示された左側コードブロックはボイスが１であり、右側コードブロックはボイスが２であると仮定する。ａは符号化された秘密、ｅはエラーベクトル、ｂは暗号化された結果である。
【００４８】
図５は、ボイスが１である３人の参加者から秘密を回収して復元する過程を示した図面である。図示されたように、３人の参加者により復号化された結果であるｃは、ボイスが１であるコードブロックにエラーを１つ、ボイスが２であるコードブロックにエラーを１つ持っている。これをエラー訂正復号化アルゴリズムを利用して復号化すれば秘密を復元できる。
【００４９】
図６は、ボイスがそれぞれ１と２である２人の参加者から秘密を回収して復元する過程を示した図面である。図示されたように、２人の参加者により復号化された結果であるｃはボイスが１であるコードブロックにエラーセットを含んでいる。したがって、ｃをエラー訂正復号化アルゴリズムを利用して復号化すれば秘密を復元できる。
【００５０】
図７は、ボイスが１である２人の参加者から秘密を回収して復元する過程を示した図面である。図示されたように、２人の参加者により復号化された結果であるｃはボイスが１であるコードブロックにエラーを２つ、ボイスが２であるコードブロックにエラーを１つ含んでいる。これは訂正可能なウェイトである３を超過するものであるため、エラー訂正復号化アルゴリズムにより復元されないことが分かる。すなわち、訂正可能なエラーの数はボイスが反映されたエラー数より大きいか、または同じ場合に復元できることが分かる。
【産業上の利用可能性】
【００５１】
本発明はデジタル署名のようなデータ保護のための暗号化システムに適用できる。
【図面の簡単な説明】
【００５２】
【図１】（ｋ，Ｎ）しきい値秘密分散法を示す概念図である。
【図２】本発明による（ｋ，Ｎ）しきい値秘密分散法を示す概念図である。
【図３】本発明による秘密分散及び復元方法を示すフローチャートである。
【図４】エラーの訂正可能な総ウェイトが３である時の秘密の符号化を説明する図面である。
【図５】ボイスが１である３人の参加者から秘密を回収して復元する過程を示す図面である。
【図６】ボイスがそれぞれ１と２である２人の参加者から秘密を回収して復元する過程を示す図面である。
【図７】ボイスが１である２人の参加者から秘密を回収して復元する過程を示す図面である。
【符号の説明】
【００５３】
２０、２３  秘密（情報）
２１        参加者
２２        結合
【図１】
2005117670.tif 000018
【図２】
2005117670.tif 000019
【図３】
2005117670.tif 000020
【図４】
2005117670.tif 000021
【図５】
2005117670.tif 000022
【図６】
2005117670.tif 000023
【図７】
2005117670.tif 000024