(57)【特許請求の範囲】
【請求項１】
認証サービスを行う管理センタの認証装置と、上記管理センタと直接に契約した主契約者の装置と、上記主契約者と契約した複数ｎ人の副契約者の装置とで構成され、上記複数ｎ人の副契約者の中から複数ｋ人（ｋ≦ｎ）の協力者を選択してなる認証システムのための秘密分散法を利用した認証方法であって、
上記主契約者の装置は、秘密の（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）次元の正則行列Ｔを用いて秘密鍵及び公開鍵を生成し、所定の複数ｍ個の（（ｋ−１）ｍ＋１）次元のベクトルをデータとし上記正則行列Ｔを用いて上記秘密鍵の分散鍵をｍ個ずつ複数ｎ個生成し、上記公開鍵及び所定のハッシュ関数Ｈを上記管理センタの認証装置に送信し、上記秘密鍵の分散鍵をｍ個ずつ上記複数ｎ人の副契約者の装置に送信することにより秘密分散し、
ここで、上記主契約者の装置は、
秘密の（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）次元の正則行列Ｔと、上記ハッシュ関数Ｈを決め、ここで、ｐを素数とし、ＨはＺｐ−１に属する（ｋ−１）ｍ＋１次元ベクトルに変換する関数とし、
所定の契約名ｘＵを定め、上記ハッシュ関数Ｈにより
［数１］
Ｈ（ｘＵ）＝ｖＵ
である（ｋ−１）ｍ＋１次元ベクトルｖＵを求め、
上記正則行列Ｔ及び上記（ｋ−１）ｍ＋１次元ベクトルｖＵより、
［数２］
ｓＵ≡ＴｖＵ  （ｍｏｄ  ｐ−１）
である（ｋ−１）ｍ＋１次元ベクトルｓＵを求めて秘密鍵として生成し、
Ｚ＊ｐの元ｇを定め、
［数３］
ｙＵ≡ｇＳＵ  （ｍｏｄ  ｐ）
となる（ｋ−１）ｍ＋１次元ベクトルｙＵを求めて公開鍵として生成し、
次いで、上記選択された複数ｋ人の協力者の装置はそれぞれ、受信された秘密鍵のｍ個の分散鍵に基づいて公開鍵
［数４］
ｙｊ＝ｇＳｊ  （ｍｏｄ  ｐ）
（ｊ＝１，２，…，ｋ）を求めて上記管理センタの認証装置に送信し、
上記管理センタの認証装置は、上記複数ｋ人の協力者の装置からそれぞれ公開鍵を受信し、上記複数ｋ人のすべての協力者の装置が上記受信された公開鍵に対する秘密鍵の分散鍵を持っているかを離散対数の零知識対話型証明の手法を用いて検査し、当該検査に合格したならば、上記ハッシュ関数に基づいて求めた（ｋ−１）ｍ＋１次元ベクトルｖＵをｍ個連接することにより（（ｋ−１）ｍ＋１）×ｍ行列ｖｊ（ｊ＝１，２，…，ｋ）を求め、当該（（ｋ−１）ｍ＋１）×ｍ行列ｖｊをｋ個連接してなる（（ｋ−１）ｍ＋１）×ｋｍ行列
［数５］
Ｖ＝［ｖ１｜ｖ２｜…｜ｖｋ］
及び、
上記受信された公開鍵から公開鍵行列
［数６］
Ｙ＝［ｙ１｜ｙ２｜…｜ｙｋ］
を求め、
（（ｋ−１）ｍ＋１）×ｋｍ行列Ｖのランクが（ｋ−１）ｍ＋１となっていれば、
［数７］
ｖＵ≡Ｖｗ  （ｍｏｄ  ｐ−１）
である（ｋ−１）ｍ＋１次元ベクトルｗを求め、
上記公開鍵ｙｊの式より、
［数８］
Ｓ＝［ｓ１｜ｓ２｜…｜ｓｋ］
とすると、
［数９］
Ｙ≡ｇＳ  （ｍｏｄ  ｐ）
であるので、すべての秘密鍵ｓｊ及び公開鍵ｙｊ（ｊ＝１，２，…，ｋ）が正当ならば、行列Ｓは
［数１０］
ｓＵ≡Ｓｗ  （ｍｏｄ  ｐ−１）
を満たすことにより、上記管理センタの認証装置は、
［数１１］
ｙＵ≡Ｙｗ  （ｍｏｄ  ｐ）
を検査し、当該検査の式を満たせば、上記複数ｋ人のすべての協力者の集合は正当であると認証することを特徴とする秘密分散法を利用した認証方法。
【請求項２】
認証サービスを行う管理センタの認証装置と、上記管理センタと直接に契約した主契約者の装置と、上記主契約者と契約した複数ｎ人の副契約者の装置とで構成され、上記複数ｎ人の副契約者の中から複数ｋ人（ｋ≦ｎ）の協力者を選択してなる認証システムであって、
上記主契約者の装置は、秘密の（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）次元の正則行列Ｔを用いて秘密鍵及び公開鍵を生成し、所定の複数ｍ個の（（ｋ−１）ｍ＋１）次元のベクトルをデータとし上記正則行列Ｔを用いて上記秘密鍵の分散鍵をｍ個ずつ複数ｎ個生成し、上記公開鍵及び所定のハッシュ関数Ｈを上記管理センタの認証装置に送信し、上記秘密鍵の分散鍵をｍ個ずつ上記複数ｎ人の副契約者の装置に送信することにより秘密分散し、
ここで、上記主契約者の装置は、
秘密の（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）次元の正則行列Ｔと、上記ハッシュ関数Ｈを決め、ここで、ｐを素数とし、ＨはＺｐ−１に属する（ｋ−１）ｍ＋１次元ベクトルに変換する関数とし、
所定の契約名ｘＵを定め、上記ハッシュ関数Ｈにより
［数１２］
Ｈ（ｘＵ）＝ｖＵ
である（ｋ−１）ｍ＋１次元ベクトルｖＵを求め、
上記正則行列Ｔ及び上記（ｋ−１）ｍ＋１次元ベクトルｖＵより、
［数１３］
ｓＵ≡ＴｖＵ  （ｍｏｄ  ｐ−１）
である（ｋ−１）ｍ＋１次元ベクトルｓＵを求めて秘密鍵として生成し、
Ｚ＊ｐの元ｇを定め、
［数１４］
ｙＵ≡ｇＳＵ  （ｍｏｄ  ｐ）
となる（ｋ−１）ｍ＋１次元ベクトルｙＵを求めて公開鍵として生成し、
次いで、上記選択された複数ｋ人の協力者の装置はそれぞれ、受信された秘密鍵のｍ個の分散鍵に基づいて公開鍵
［数１５］
ｙｊ＝ｇＳｊ  （ｍｏｄ  ｐ）
（ｊ＝１，２，…，ｋ）を求めて上記管理センタの認証装置に送信し、
上記管理センタの認証装置は、上記複数ｋ人の協力者の装置からそれぞれ公開鍵を受信し、上記複数ｋ人のすべての協力者の装置が上記受信された公開鍵に対する秘密鍵の分散鍵を持っているかを離散対数の零知識対話型証明の手法を用いて検査し、当該検査に合格したならば、上記ハッシュ関数に基づいて求めた（ｋ−１）ｍ＋１次元ベクトルｖＵをｍ個連接することにより（（ｋ−１）ｍ＋１）×ｍ行列ｖｊ（ｊ＝１，２，…，ｋ）を求め、当該（（ｋ−１）ｍ＋１）×ｍ行列ｖｊをｋ個連接してなる（（ｋ−１）ｍ＋１）×ｋｍ行列
［数１６］
Ｖ＝［ｖ１｜ｖ２｜…｜ｖｋ］
及び、
上記受信された公開鍵から公開鍵行列
［数１７］
Ｙ＝［ｙ１｜ｙ２｜…｜ｙｋ］
を求め、
（（ｋ−１）ｍ＋１）×ｋｍ行列Ｖのランクが（ｋ−１）ｍ＋１となっていれば、
［数１８］
ｖＵ≡Ｖｗ  （ｍｏｄ  ｐ−１）
である（ｋ−１）ｍ＋１次元ベクトルｗを求め、
上記公開鍵ｙｊの式より、
［数１９］
Ｓ＝［ｓ１｜ｓ２｜…｜ｓｋ］
とすると、
［数２０］
Ｙ≡ｇＳ  （ｍｏｄ  ｐ）
であるので、すべての秘密鍵ｓｊ及び公開鍵ｙｊ（ｊ＝１，２，…，ｋ）が正当ならば、行列Ｓは
［数２１］
ｓＵ≡Ｓｗ  （ｍｏｄ  ｐ−１）
を満たすことにより、上記管理センタの認証装置は、
［数２２］
ｙＵ≡Ｙｗ  （ｍｏｄ  ｐ）
を検査し、当該検査の式を満たせば、上記複数ｋ人のすべての協力者の集合は正当であると認証することを特徴とする秘密分散法を利用した認証システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、秘密分散法を利用した認証方法、認証システム及び認証方式に関する。
【０００２】
【従来の技術】
近年、インターネットや電子商取引などの普及により、複数参加可能なシステムが求められている。複数参加型プロトコルの一例として、秘密を共有する方法（“How to Share a Secret”)と題する、シャミア（A. Shamir)により提案された秘密分散法［Secret Sharing:以下ＳＳと略記する：CACM, Vol.22, No. 11, PP.612-613 (1979)］がある。秘密分散法は、もともと、複数人で秘密を共有保管し、盗難や紛失、破壊の心配に対処する方法をいうが、このＳＳは一度復号を行なうと分散情報保持者に秘密が露呈してしまうため、ただ一度のみの復号を前提としている。このため、理論的には興味深いものの現実的には用途が著しく限定されてしまう。
【０００３】
【発明が解決しようとする課題】
上記のように、一回限りの復号を前提とした従来の秘密分散法の欠点を改良して秘密の分散情報を繰り返し利用することができる、秘密分散法を利用した認証方法、認証システム及び認証方式を提案するものである。
【０００４】
【課題を解決するための手段】
本発明は、秘密情報の分散情報を秘密分散し、秘密分散した分散情報のうちの所定数の分散情報が秘密情報を復元する能力を有するか否かを検証することにより認証を行う。
【０００５】
この分散情報の検証には、零知識対話型証明を用いることが秘密情報の漏洩に対する安全性を高めるうえで好ましい。
さらに、秘密分散する分散情報を複数個の情報の集合とすることが認証の確度を高めるうえで好ましい。
【０００６】
より具体的に、本発明の認証方法は、秘密のｋ×ｋ行列Ｔにより生成される秘密鍵ｓUを主契約者に秘密裡に配付するとともに、副契約者には秘密鍵の分散情報を秘密裡に配付し、センタは主契約者の秘密鍵ｓUもしくはｓUを生成する能力を有するｋ×ｋ行列Ｓを有することを検証することにより認証を行なう。
【０００７】
ここで、センタは銀行や計算機のホスト等サービスの提供者をいい、主契約者とは、センタと直接に契約している者、例えば、金庫の所有者等をいう。また、副契約者とは主契約者によりあらかじめ選ばれたｎ人をいう。
【０００８】
本発明の認証方法において、主契約者は正しい鍵を有していることを単純にセンタに証明することによりセンタにアクセスすることができる。副契約者の場合には、ｎ人中、ｋ人以上の協力により復号情報が主契約者の鍵と等しい価値を有すると認められた場合にのみセンタにアクセスすることができる。
【０００９】
この場合、主契約者の鍵そのものが露呈されることはないので、分散情報は繰り返し使用することができる。かかる意味で、本発明のＳＳ認証方法は、再利用可能（reusable）なＳＳ認証方法（ＲＳＳ認証方式と記す）である。
【００１０】
上記秘密鍵は、主契約者が生成することができる。この場合には、センタには秘密鍵も誰が副契約者であるかも知られることはない。
また、センタが秘密鍵を生成するようにしてもよい。この場合には、主契約者の死亡など、万一の場合に、センタは配付した秘密鍵を全く変更することなく副契約者の一人を主契約者に変更できるという利点がある。
【００１１】
【発明の実施の形態】
（実施の形態１）
図１に示すように、ＲＳＳ認証システムは、例えば、郵便局や銀行等の管理センタＢと、管理センタＢと直接に契約してサービスの提供を受ける主契約者Ｕと、主契約者Ｕによりあらかじめ選ばれた副契約者Ｐi（ｉ＝１，…，ｎ  但し、ｎは２以上の整数）のエンティティＰとにより構成される。
【００１２】
本発明にかかるＲＳＳ認証方法の基本プロトコルは以下の通りである。
秘密のｋ×ｋ行列Ｔにより生成される秘密鍵ｓUを主契約者Ｕに秘密裡に配付し、副契約者Ｐiには、秘密鍵ｓUの分散情報（Share）を秘密裡に配付する。この場合、行列Ｔは管理センタＢ又は主契約者Ｕが生成するものとし、管理センタＢは主契約者Ｕの秘密鍵ｓU又はｓUを生成する能力を有するｋ×ｋ行列Ｓを有することを検証することにより認証を行なう。
【００１３】
以下、ＲＳＳ認証方法を具体的に説明する。
【００１４】
≪準備≫
秘密生成者（主契約者Ｕ又は管理センタＢ）は以下の準備を行なう。
１．ｋ×ｋの正則行列Ｔ、ハッシュ関数Ｈを決める。ただし、ｐを素数とし、ＨはＺp-1に属するｋ次元ベクトルに変換する関数とする。
２．主契約者の契約名ｘUを定め、Ｈより
【数１】
Ｈ（ｘU）＝ｖU          （１）
であるｋ次元ベクトルｖUを求める。
３．Ｔ，ｖUより、
【数２】
ｓU≡ＴｖU  （ｍｏｄｐ−１）          （２）
であるｋ次元ベクトルｓUを求め秘密鍵とする。
４．Ｚpの原始元ｇ（公開）定め、
【数３】
0004070915.tif 000002
となるｙUを求め、公開鍵とする。
【００１５】
≪鍵の分散≫
秘密生成者は、以下のように鍵の分散を行なう。
１．ｎ人の副契約者Ｐ＝｛Ｐ1，Ｐ2，…，Ｐn｝を選び、各々の名前ｘi（ｉ＝１，２，…，ｎ）を決める。
２．ハッシュ関数Ｈおよびｘiより、
【数４】
Ｈ（ｘi）＝ｖi          （４）
であるｋ次元ベクトルｖi（ｉ＝１，２，…，ｎ）を求める。
３．行列Ｔ，ｖiより
【数５】
ｓi≡Ｔｖi  （ｍｏｄｐ−１）          （５）
であるｋ次元ベクトルｓi（ｉ＝１，２，…，ｎ）を求める。
４．Ｂに（ｘU、Ｈ，ｙU）を送る（秘密生成者がＵの場合）。
５．Ｐiに（ｘi，ｓi）を送る。
【００１６】
≪主契約者の認証プロトコル≫
主契約者Ｕは図２の上段に示すように、以下のプロトコルにより認証を行なう。
１．主契約者ＵはｘUを管理センタＢに送る。
２．管理センタＢはｘUの公開鍵ｙUに対する秘密鍵ｓUを正しく持っていることを離散対数のゼロ知識証明ＺＫＩＰ（後述）により検査する。
３．検査を満たせば、管理センタＢは主契約者Ｕが正当であることを認証する。
【００１７】
≪副契約者の認証プロトコル≫
ｋ人の副契約者は図２の下段に示すように、以下のプロトコルにより認証を行なう。
１．Ｐi（ｉ＝１，２，…，ｎ）のｋ人の集合、
【数６】
Ａk＝｛Ａ｜Ａ⊆Ｐ∧＃Ａ＝ｋ｝
を満たす集合Ａを得る。
２．集合Ａの各Ｐj（ｊ＝１，２，…，ｋ）は秘密鍵ｓjより
【数７】
0004070915.tif 000003
となる公開鍵ｙj（ｊ＝１，２，…，ｋ）を求める。
３．集合Ａの各々は（ｘj，ｙj）を管理センタＢに送る。
４．管理センタＢは各Ｐjについて公開鍵ｙjに対する秘密鍵ｓjを有することを離散対数のＺＫＩＰを用いて検査する。
５．ｋ人全員がＺＫＩＰに合格すれば、以下のように検証を行なう。
（ａ）管理センタＢは式（４）よりｖjを求め、ｋ個連接したｋ×ｋ行列
【数８】
Ｖ＝［ｖ1｜ｖ2｜…｜ｖk］          （７）
および、
【数９】
Ｙ＝［ｙ1｜ｙ2｜…｜ｙk］          （８）
を求める。
（ｂ）Ｖのランクがｋとなっていれば、
【数１０】
ｖU≡Ｖｗ  （ｍｏｄｐ−１）          （９）
であるｋ次元ベクトルωが求まる。
（ｃ）式（６）より、
【数１１】
Ｓ＝［ｓ1｜ｓ2｜…｜ｓk］          （１０）
とすると、
【数１２】
Ｙ≡ｇs  （ｍｏｄｐ）          （１１）
であるので、すべてのｓjおよびｙjが正当ならば、行列Ｓは
【数１３】
ｓU≡Ｓｗ  （ｍｏｄｐ−１）          （１２）
を満たすことにより、センタＢは
【数１４】
ｙU≡Ｙw  （ｍｏｄｐ）          （１３）
を検査する。
６．式（１３）の検査を満たせば、管理センタＢは副契約者集合Ａが正当であることを認証する。
【００１８】
なお、ゼロ知識証明（ＺＫＩＰ）を用いて、離散対数を知っていることを示す認証方式は以下の通りである（なお、岡本龍明、山本博資著：“現代暗号”、産業図書（１９９７）参照のこと）。
【００１９】
［離散対数のＺＫＩＰ］
証明者をＡ，検証者をＢとする。
１．センタ鍵生成  ｐを素数として、Ｚ*pの原始元ｇを選びｐ、ｇを公開する。
２．証明者鍵生成  証明者Ａは秘密鍵Ｓ∈Ｚ*Nを生成し、
【数１５】
Ｉ≡ｇS  （ｍｏｄｐ）
となるＩを公開鍵とする。
３．検証プロトコル  以下の手続きをｉ＝１，２，…，ｔについて繰り返すことにより、１−２-tの確率でなりすましを検出できる。ｔが十分大きいときには、この確率は１に非常に近い。
（ａ）Ａは乱数ｒi∈Ｚ*pを生成し、
【数１６】
0004070915.tif 000004
を求め、Ｂに送信する。
（ｂ）Ｂは乱数ｅi∈｛０，１｝を生成しＡに送信する。
（ｃ）証明者Ａは
【数１７】
ｙi≡ｒi＋ｅiＳ  （ｍｏｄｐ−１）
すなわち、
【数１８】
0004070915.tif 000005
を求め、Ｂに送信する。
（ｄ）検証者Ｂは
【数１９】
0004070915.tif 000006
すなわち、
【数２０】
0004070915.tif 000007
が成り立つことを検査する。
４．全ての検査に合格した場合、検証者Ｂは証明者Ａを受理する。
【００２０】
上に述べた実施の形態１の方式は、Ｚp-1上のランダムに選んだｋ次元ベクトルをｋ個連接して作ったｋ×ｋ行列のランクが高確率でｋとなるという事実を利用している。
【００２１】
本基本方式は、大きく二つの利用方法が考えられる。すなわち、
１．秘密鍵を主契約者が生成する場合
２．センタが生成する場合
である。前者は、センタには秘密鍵も、また、誰が副契約者であるかも知られることはないという利点を有し、後者は主契約者の死亡など、万一の場合にはセンタは配付した秘密鍵を全く変更することなく副契約者の一人を主契約者に変更できるという利点を有する。特に後者の特徴は、全ての契約者の鍵を同一の方法で生成するというＳＳの構成法によりもたらされるものである。
しかし、本方式には他の認証方式と異なり、式（４）および式（７）により求めた行列Ｖのランクが必ずｋとなる保証はないという問題点がある。
【００２２】
（実施の形態２）
上記実施の形態１では、ｎ人中ｋ人のベクトルｖjを連接したｋ×ｋ行列Ｖのランクが高確率でｋになるという事実を利用しているが、確実にｋとなる保証はない。
【００２３】
この実施の形態２では、上記の点を解決し、ｋ人でより確実に利用できる方式を提案する。
各Ｐiに与えるｖi，ｓiを各々ｍ個づつとし、（ｋ，ｎ）しきい値とする。
【００２４】
≪準備≫
秘密生成者（主契約者Ｕまたは管理センタＢ）は以下の準備を行なう。
１．（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）の正則行列Ｔ、ハッシュ関数Ｈを決める。ただし、ｐを素数とし、ＨはＺp-1に属する（ｋ−１）ｍ＋１次元ベクトルに変換する関数とする。
２．主契約者の契約名ｘUを定め、Ｈにより
【数２１】
Ｈ（ｘU）＝ｖU          （１４）
である（ｋ−１）ｍ＋１次元ベクトルｖUを求める。
３．Ｔ，ｖUより、
【数２２】
ｓU≡ＴｖU  （ｍｏｄｐ−１）          （１５）
である（ｋ−１）ｍ＋１次元ベクトルｓUを求め秘密鍵とする。
４．Ｚ*pの元ｇ（公開）定め、
【数２３】
0004070915.tif 000008
となる（ｋ−１）ｍ＋１次元ベクトルｙUを求め、公開鍵とする。
【００２５】
≪鍵の分散≫
秘密生成者は、以下のように鍵の分散を行なう。
１．ｎ人の副契約者Ｐ＝｛Ｐ1，Ｐ2，…，Ｐn｝を選び、その名前ｘi（ｉ＝１，２，…，ｎ）を各々ｍ個ずつ決める。
２．各Ｐiに対しハッシュ関数Ｈ（秘密）により、
【数２４】
0004070915.tif 000009
である（ｋ−１）ｍ＋１次元ベクトル
0004070915.tif 000010
を求め、連接し
【数２５】
0004070915.tif 000011
である（（ｋ−１）ｍ＋１）×ｍ行列ｖiを求める。
３．Ｔ，ｖiより
【数２６】
ｓi≡Ｔｖi  （ｍｏｄｐ−１）          （１９）
である（（ｋ−１）ｍ＋１）×ｍ行列ｓi（ｉ＝１，２，…，ｎ）を求めＰiの秘密鍵とする。
４．ＵはＢに（ｘU、Ｈ，ｙU）を送る。
５．Ｕは各Ｐiに（ｘi，ｓi）を送る。
【００２６】
≪主契約者の認証プロトコル≫
実施の形態１における主契約者Ｕの認証プロトコルと全く同様である。
【００２７】
≪副契約者の認証プロトコル≫
副契約者は以下のプロトコルにより認証を行なう。
１．Ｐi（ｉ＝１，２，…，ｎ）のｋ人の集合、
【数２７】
Ａk＝｛Ａ|Ａ⊆Ｐ∧＃Ａ＝ｋ｝
を満たす集合Ａを得る。
２．Ａの各メンバＰj（ｊ＝１，２，…，ｋ）は秘密鍵ｓjより
【数２８】
0004070915.tif 000012
である公開鍵ｙjを求める。
３．Ａの各々は（ｘj，ｙj）をＢに送る。
４．集合Ａの各Ｐiが公開鍵ｙiに対する秘密鍵ｓiをもっているかを離散対数のＺＫＩＰを用いて検査する。
５．ｋ人全員が検査に合格すれば、集合Ａに対する以下の検査を行なう。
（ａ）Ｂは式（１８）より（（ｋ−１）ｍ＋１）×ｍ行列ｖjを求め、ｋ個連接した（（ｋ−１）ｍ＋１）×ｋｍ行列
【数２９】
Ｖ＝［ｖ1|ｖ2|…|ｖk］          （２１）
および、
【数３０】
Ｙ＝［ｙ1|ｙ2|…|ｙk］          （２２）
を求める。
（ｂ）（（ｋ−１）ｍ＋１）×ｋｍ行列Ｖのランクが（ｋ−１）ｍ＋１となっていれば、
【数３１】
ｖU≡Ｖｗ  （ｍｏｄｐ−１）          （２３）
である（ｋ−１）ｍ＋１次元ベクトルｗを求める。
（ｃ）式（２０）より、
【数３２】
Ｓ＝［ｓ1|ｓ2|…|ｓk］          （２４）
とすると、
【数３３】
Ｙ≡ｇS  （ｍｏｄｐ）          （２５）
であるので、すべてのｓiおよびｙiが正当ならば、行列Ｓは
【数３４】
ｓU≡Ｓｗ  （ｍｏｄｐ−１）          （２６）
を満たすことにより、センタＢは
【数３５】
ｙU≡Ｙw  （ｍｏｄｐ）          （２７）
を検査する。
６．式（２７）の検査を満たせば、副契約者集合Ａは正当であると認証する。
【００２８】
実施の形態２は行列Ｖのサイズを（（ｋ−１）ｍ＋１）×ｋｍとし、そのランクが（ｋ−１）ｍ＋１となるｋ人の分散情報（ｓｈａｒｅ）であれば正当であると認証される。したがって、ｋ−１人では最大でも（ｋ−１）ｍのランクとなるＶしか生成できないが、ｋ人ではｋｍ個のベクトルのうち（ｋ−１）ｍ＋１個が一次独立であればよいので、候補がｍ−１個多く存在し、実施の形態１に比べてｋ人で規定のランクとなる確率はかなり高くなる。しかし、分散情報生成者が（（ｋ−１）ｍ＋１）×ｍ行列ｖのランクを調節できるため、分散情報の情報量に格差を作りやすいという問題点も有する。ただし、この問題点は主契約者が重み付きの分散を行なう場合には利点ともなる。
【００２９】
（実施の形態３）
実施の形態１および２では、副契約者の（（ｋ−１）ｍ＋１）×ｍ行列ｖの値やランクにより、意図的もしくは偶発的にそれぞれの分散情報（ｓｈａｒｅ）の価値に格差が生じることがあった。この格差をなくし、どの様なＰiの組においても公平に、ある程度高確率で（ｋ，ｎ）しきい値で成功させることを目的とする。
【００３０】
≪手順≫
１．秘密生成者はｋ×ｋの正則行列Ｔ、ハッシュ関数Ｈを各々ｍ個づつ決める。
２．主契約者Ｕは実施の形態１と同様の方法でｍ個のＨから、秘密鍵ｓUおよびｖUをｍ個つくり、連接したｋ×ｍ行列ｓU、ｖUを求める。すなわち、１つのｘUからｍ個の（ｓU，ｖU）の組が生成される。
３．秘密生成者Ｕは各副契約者Ｐiについても同様に鍵を生成し、（ｘi，ｓi）を秘密裡に送信する。
４．各Ｐiは、式（６）によりｋ×ｍ行列の公開鍵ｙUを求め公開する。
５．管理センタＢは（ｖi，ｓi）を各列ベクトルごとに分解し、基本方式と同様の検証をｍ個の列ベクトルについて各々行なう。
６．Ｐiによる検証時にはｍ個の列ベクトルの検証のうち、あるｌ（＜ｍ）回について検査を満たすとＲＳＳ認証に合格する。
７．ｌの値がｍに近い程安全性は高くなる。
【００３１】
実施の形態２の格差の作りやすさの要因はｘiが複数個選ばれることにあった。したがって、実施の形態３では、ｘiただ一つにし、そのｘiに関し基本方式の検証をＴ，Ｈを変え複数（ｍ）回行なう。Ｖのランクがｍ回全てｋとならない確率は非常に低いのでｍ回中ｌ（＜ｍ）回成功すれば、正当であると認証してよいと考えられる。
【００３２】
実施の形態３は、実施の形態１の方式を複数回行なうことに相当するため、正しいｋ人で認証される確率を高め、かつ、実施の形態２の問題であったｓｈａｒｅの情報量の格差を意図的に作れないようにしたものである。
【００３３】
本発明に係る再利用可能な認証方式（ＲＳＳ認証方式）の特徴を以下にまとめる。
・ＲＳＳ認証方式は、ただ一つの固有の鍵の有無を検証する。
提案方式では、“正しい鍵を持っているかどうか”という事実のみを検証する。すなわち、センターの認証マシンに鍵をどの様な形であれ鍵を保有していることを納得させた場合のみ、認証に合格する。
・副契約者が利用する場合には、そのグループの持つ（分散）鍵の組が主契約者の鍵を構成できるかどうかを検証する。
システムの構成法より、しきい値であるｋ人の協力で初めて認証に合格することが保証され、主契約者のしきい値に対する信頼性が高い。
上述した特徴より、提案方式には他の認証方式に比べ次のような利点がある。
・契約および認証に個人情報を用いない。
個人情報をデータバンクに登録せずに利用できるシステムでは、ネットワーク上での利用における安全性だけでなく、管理センタに対しても利用者の個人情報が保護される。
・主契約者は、副契約者を自由に選ぶことができ、かつ、センタへの登録は必要としない。
ＲＳＳ認証では鍵の有無のみが重要であり、個人認証を必要としないため副契約者をセンタに登録する必要がない。
・副契約者が何人協力しあっても主契約者の鍵を求めることはできず、主契約者は鍵を繰り返し安全に利用できる。
副契約者には主契約者の鍵ｓUと式（１０）で求められるＳ関係を表すパラメータｗが求められないため、ｓUが副契約者によって復号される恐れはない。
・秘密情報そのものを通信することがないのでネットワーク上で通信を行なっても安全である。
検証には離散対数のＺＫＩＰを用いて行なうため、秘密情報そのものを通信する必要はなく盗聴者に対して安全性が高い。また、センタは鍵の検証を行なうが、秘密そのものは復号できない。
【００３４】
なお、本願発明は以下の実施態様で実施することができる。
【００３５】
＜実施態様項１＞
秘密のｋ×ｋ次元の正則行列Ｔを用いて、秘密情報を生成するとともに、同じ行列Ｔを用いてｎ個（ｎ＞ｋ）の分散情報を生成して秘密分散し、秘密分散したｎ個の分散情報のうちのｋ個が秘密情報を復元する能力を有するか否かを検証することにより認証を行う認証方法。
【００３６】
＜実施態様項２＞
秘密情報はｋ次元ベクトルであり、分散情報もｋ次元ベクトルである、実施態様項１記載の認証方法。
【００３７】
＜実施態様項３＞
ｋ人の分散秘密情報所持者は、各々分散秘密情報に対応した公開情報を認証者に送り、認証者は離散対数の零知識対話型証明の手法を用いて、各分散秘密情報所持者が分散秘密情報を有することを検証する、実施態様項１又は２に記載の認証方法。
【００３８】
＜実施態様項４＞
秘密の（（ｋ−１）ｍ＋１）×（（ｋ−１）ｍ＋１）次元の正則行列Ｔを用いて秘密情報を生成するとともに、ｍ個の（（ｋ−１）ｍ＋１）次元のベクトルをデータとし上記行列Ｔを用いて分散情報をｎ個生成して秘密分散し、ｎ個の分散情報のうちのｋ個が上記秘密情報を復元する能力を有するか否かを検証することにより認証を行う認証方法。
【００３９】
＜実施態様項５＞
離散対数の零知識対話型証明の手法を用いて分散情報の検証を行う、実施態様項４に記載の認証方法。
【００４０】
＜実施態様項６＞
ｍ個の秘密のｋ×ｋの正則行列Ｔを用いてｍ個の単位情報からなる秘密情報を生成するとともに、同じｍ個の行列Ｔを用いてｍ個の単位情報からなる分散情報をｎ個生成し（ｎ＞ｋ）、ｎ個の秘密分散情報のうちのｋ個が秘密情報を復元する能力を有するか否かを検証することにより認証を行う認証方法。
【００４１】
＜実施態様項７＞
離散対数の零知識対話型証明の手法を用いて分散情報の検証を行う、実施態様項６に記載の認証方法。
【００４２】
＜実施態様項８＞
管理センタと、管理センタと契約した主契約者と、主契約者と契約したｎ人の副契約者とで構成され、主契約者には、秘密のｋ×ｋ行列Ｔにより生成される秘密鍵を秘密裡に配付するとともに、各副契約者には、秘密鍵の分散鍵を秘密裡に配付しておき、管理センタは主契約者が秘密鍵を有することが検証されるか、ｎ人中のｋ人の副契約者の分散鍵が上記秘密鍵を生成する能力を有することを検証することにより認証を行う認証システム。
【００４３】
＜実施態様項９＞
管理センタは、零知識対話型証明法を用いて秘密鍵、分散鍵の検証を行う、実施態様項８に記載の認証システム。
【００４４】
＜実施態様項１０＞
サービスの提供を行なうセンタと、センタと直接に契約した主契約者と、主契約者が選んだｎ人の副契約者（ｎは２以上の自然数）とで構成する認証方式であって、
秘密のｋ×ｋ行列Ｔにより秘密鍵ｓUを生成して主契約者に秘密裡に配付する秘密生成手段と、
各副契約者Ｐiについて上記行列Ｔを用いて秘密鍵ｓiを生成して各副契約者Ｐiに秘密鍵ｓiを秘密裡に配付する鍵の分散手段と、
各Ｐj（ｊ＝１，…，ｋ）について公開鍵ｙjに対する秘密鍵ｓjを有することを検証する第１検証手段と、
各Ｐjの契約名ｘjからハッシュ関数を用いて生成したｋ次元ベクトルｖjをｋ個連接してできるｋ×ｋの行列Ｖのランクがｋであるか否かを検証する第２検証手段と、
ｋ×ｋ行列Ｖのランクがｋであることが検証されると主契約者の秘密鍵ｓUを生成することができるｋ×ｋ行列Ｓが存在することを検証する第３検証手段とを備えた、秘密分散法を利用した認証方式。
【００４５】
＜実施態様項１１＞
秘密生成手段は、主契約者に所有されている、実施態様１０に記載の認証方式。
【００４６】
＜実施態様項１２＞
秘密生成手段は、センタに所有されている、実施態様１１に記載の認証方式。
【図面の簡単な説明】
【図１】  本発明に係るＲＳＳ認証方式のシステム構成図である。
【図２】  本発明に係るＲＳＳ認証方式のプロトコルを示す説明図である。
【符号の説明】
Ｕ  主契約者
Ｂ  管理センタ
Ｐ  副契約者集合
Ｐi  副契約者
【図１】
0004070915.tif 000013
【図２】
0004070915.tif 000014