(57)【特許請求の範囲】
【請求項１】
分散認証サーバを構成する装置群を含む複数の装置を有する通信システムにおいて、
認証者側装置に認証されることを求める証明者側装置が、分散認証サーバを構成する各装置に、証明者及び認証者の識別子を含む認証要求メッセージを送信し、
前記分散認証サーバを構成する各装置が共同して、前記認証要求メッセージに基づいて、認証者に関する秘密鍵で暗号化された認証子を生成し、該認証子を証明者に関する秘密鍵で暗号化して認証メッセージを生成し、
前記分散認証サーバを構成する各装置が、前記認証メッセージを前記証明者側装置に送信し、
前記認証メッセージを受信した前記証明者側装置が、当該認証メッセージを復号し、得られた認証子を前記認証者側装置に送信し、
前記認証子を受信した前記認証者側装置が、該認証子を復号して証明者を認証することを特徴とする認証方法。
【請求項２】
前記分散認証サーバを構成する各装置が共同して、前記証明者側装置及び前記認証者側装置に、当該両装置間の暗号通信に利用する共通鍵を送信することを特徴とする請求項１に記載の認証方法。
【請求項３】
前記分散認証サーバを構成する各装置が、前記証明者側装置に、前記共通鍵を前記認証メッセージに含めて送信することを特徴とする請求項２に記載の認証方法。
【請求項４】
前記分散認証サーバを構成する各装置が、前記認証者側装置に、前記共通鍵を前記認証子に含めて送信することを特徴とする請求項２に記載の認証方法。
【請求項５】
前記証明者側装置及び前記認証者側装置間の暗号通信に利用する共通鍵を、確認可能な秘密分散処理を利用して、分散された疑似乱数として、分散認証サーバを構成する各装置が共同して生成することを特徴とする請求項１に記載の認証方法。
【請求項６】
前記分散認証サーバを構成する各装置において、秘密鍵による暗号化を、暗号化すべきデータを複数のブロックに分割し、分割された各ブロックに、それぞれ異なる秘密鍵を所定の有限体上で加算することで実行することを特徴とする請求項１に記載の認証方法。
【請求項７】
前記分散認証サーバを構成する各装置において、秘密鍵による暗号化を、暗号化すべきデータを複数のブロックに分割し、分割された各ブロックに、それぞれ異なる秘密鍵を所定の有限体上で乗じ、各乗算結果に更にそれぞれ異なる秘密鍵を加算することで実行することを特徴とする請求項１に記載の認証方法。
【請求項８】
通信システムを構成する各装置が、当該装置に関する秘密鍵を、前記分散認証サーバを構成する各装置に、秘密分散処理により分散配布することを特徴とする請求項１に記載の認証方法。
【請求項９】
前記証明者側装置が、前記認証子を前記認証者側装置に送信する際に、当該認証子をタイムスタンプと共に、当該証明者側装置と認証者側装置とで共通する共通鍵を用いて暗号化して送信し、
前記認証者側装置が、前記証明者側装置からの受信情報を前記共通鍵を用いて復号してタイムスタンプを確認することを特徴とする請求項１に記載の認証方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、通信路によって複数の装置が接続された通信システムに関し、特に、認証を複数の装置で分散して行う通信システムにおける認証方法に関するものである。
【０００２】
【従来の技術】
従来、多くの通信システムでは、情報をパケットと呼ばれるデータブロック単位で伝達する。パケットは、指定した宛先に伝達した場合でも、通信システムを構成する全ての装置（のユーザ）がそのパケットを受信することができる。また、複数の装置が同じ通信路を介して接続されているために、パケットの送信元を特定することは困難である。このため、このような通信システムでは、別の宛先に対するパケットを不正に入手する「盗聴」と、ある装置を別の装置に見せかける「なりすまし」という攻撃にさらされやすい。
【０００３】
この盗聴となりすましの脅威を和らげるために、公開鍵暗号方式（池野、小山：  ”現代暗号理論”  、電子通信学会、１９８６  参照）と呼ばれる暗号技術を用いた手法が知られている。公開鍵暗号方式の中には、ＲＳＡ暗号のように、暗号化機能の他に「ディジタル署名」と呼ばれる認証機能を持つものがあり、これを用いて署名付きで暗号通信を行うことで、盗聴やなりすましを防止することができる。
【０００４】
また、盗聴となりすましの脅威を和らげる他の対策として、計算量の少ない共通鍵暗号方式によるケルベロス（ｋｅｒｂｅｒｏｓ：Ｓ．Ｇａｒｆｉｎｋｅｌ  ａｎｄ  Ｇ．Ｓｐａｆｆｏｒｄ共著／山口英  監訳：  ”ＵＮＩＸセキュリティ”  、アスキー、ｐｐ．３４９−３５７，ｐｐ．５３５−５４２，  １９９３  参照）と呼ばれるネットワークにおける認証方式がよく知られている。
【０００５】
以下に、Ｎｅｅｄｈａｍ  とＳｃｈｒｏｅｄｅｒ  の認証プロトコル（Ｒ．Ｎ．Ｎｅｅｄｈａｍ  ａｎｄ  Ｍ．Ｄ．Ｓｃｈｒｏｅｄｅｒ：  ”Ｕｓｉｎｇ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｉｎ  Ｌａｒｇｅ  Ｎｅｔｗｏｒｋ  ｏｆ  Ｃｏｍｐｕｔｅｒｓ”，ＣＡＣＭ  ２１，  １２，  ｐｐ．９９３−９９９．  Ｄｅｃ．  １９７８  参照）とＢｉｒｒｅｌｌ  のＳｅｃｕｒｅ  ＲＰＣ（Ｒｅｍｏｔｅ  Ｐｒｏｃｅｄｕｒｅ  Ｃａｌｌ）  プロトコル（Ａ．Ｄ．Ｂｉｒｒｅｌｌ：  ”Ｓｅｃｕｒｅ  Ｃｏｍｕｎｉｃａｔｉｏｎｓ  Ｕｓｉｎｇ  Ｒｅｍｏｔｅ  Ｐｒｏｃｅｄｕｒｅ  Ｃａｌｌｓ”，  ＡＣＭ  Ｔｒａｎｓ．ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ，  Ｖｏｌ．３．  Ｎｏ．１，  ｐｐ．１−１４，Ｆｅｂ．  １９８５    参照）に基づく具体的なケルベロスの認証プロトコルを説明する。
【０００６】
通常、ケルベロスには、その通信システムの全装置の秘密情報（秘密鍵に相当する）を管理する認証サーバが存在する。まず、認証サーバは、図１６の（ａ）  に示すように、各装置ｉと秘密鍵ｐｋｉを共有する。以下、証明を求めるものを証明者、証明者を認証するものを認証者と呼ぶものとする。
【０００７】
図１６の（ｂ）  に示すように、証明者Ａが認証者Ｂに証明を求める場合、Ａは｛Ａ，Ｂ，Ｒ｝のような形式のデータ１６１を認証サーバに送る。但し、ＡとＢは装置またはユーザネームのような証明者Ａと認証者Ｂを特定するための公開識別情報であり、  Ｒはランダムに選ばれた数である。
【０００８】
これに対し、認証サーバは、｛認証子，Ｒ，Ｂ，ＣＫ｝＾ｐｋＡというデータ１６２をＡに返す。但し、｛Ｍ｝＾ｋは、メッセージＭを鍵ｋで暗号化したデータであることを示し、認証子は、タイムスタンプＴを用いて｛Ｔ，Ａ，ＣＫ｝＾ｐｋＢのように構成されているデータ１６３であり、ＣＫは、以降のＡ、Ｂ間の共通鍵暗号通信に用いる認証サーバによって生成された共通鍵である。
【０００９】
以後、証明者と認証者の間で共通鍵暗号通信を行う時の秘密の共通鍵を会話鍵と呼ぶことにする。従って、認証サーバは、会話鍵の配送サーバとしての役割も果たす。最後に、証明者Ａは前述した認証子１６３を認証者Ｂに送り、Ｂは認証子を自分の秘密のマスター鍵ｐｋＢで複合することにより、Ａを認証し、その後の後、共通の会話鍵ＣＫを用いて暗号通信を行う。
【００１０】
以上のようにして、ケルベロスを用いた認証プロトコルにより盗聴やなりすましの脅威を和らげることができる。
【００１１】
【発明が解決しようとしている課題】
しかしながら、公開鍵暗号方式では、５１２ビット以上の大きな整数のべき乗剰余演算を行う必要があり、計算量が膨大になるという問題点がある。
【００１２】
また、共通鍵方式におけるケルベロスのようなプロトコルでは、認証サーバが通信システムを構成する全ての装置の秘密情報を管理するために、物理的な意味も含めて、完全に信頼できる認証サーバを必要とするという問題がある（同様に、公開鍵暗号方式の場合も、全ての公開鍵を管理する集中管理センタが必要であり、同じ問題点を持つ）。よって、セキュリティを万全のものとするためには、認証サーバを許可のない人間が勝手に入り込めない施錠された部屋などで厳重に管理する必要があった。また、その認証サーバが故障や犯罪などによって信頼できなくなった場合には、そのシステム全体の安全性が崩壊するといったフォールトトレランスが弱いという問題点があった。
【００１３】
そこで、このような認証サーバの信頼性の問題を解決するために、本発明では、複数の装置によって、秘密情報を分散管理する分散認証サーバを提案する。
【００１４】
この分散認証サーバに対する要求は、以下のようなものである。
（１）  証明者や認証者に対して、分散認証プロトコルは、従来の集中管理による認証プロトコルと同一の認証機能を実現する。
（２）  証明者や認証者に対して、分散認証プロトコルは、従来の集中管理による認証プロトコルと同じインターフェース（データ形式）を保証する。
（３）  証明者や認証者に対して、分散認証プロトコルは、従来の集中管理による認証プロトコルと同じ計算量で実現される。
（４）  分散認証サーバを構成する装置の過半数が信頼できない場合を除いて、上記の要求が満足される。
【００１５】
【課題を解決するための手段】
上述の課題を解決するために、本発明の認証方法によれば、分散認証サーバを構成する装置群を含む複数の装置を有する通信システムにおいて、
認証者側装置に認証されることを求める証明者側装置が、分散認証サーバを構成する各装置に、証明者及び認証者の識別子を含む認証要求メッセージを送信し、
前記分散認証サーバを構成する各装置が共同して、前記認証要求メッセージに基づいて、認証者に関する秘密鍵で暗号化された認証子を生成し、該認証子を証明者に関する秘密鍵で暗号化して認証メッセージを生成し、
前記分散認証サーバを構成する各装置が、前記認証メッセージを前記証明者側装置に送信し、
前記認証メッセージを受信した前記証明者側装置が、当該認証メッセージを復号し、得られた認証子を前記認証者側装置に送信し、
前記認証子を受信した前記認証者側装置が、該認証子を復号して証明者を認証する。
【００１６】
【実施例】
以下、図面を参照して本発明の実施例を詳細に説明する。
【００１７】
［実施例１］
図１は、本発明の１実施例である、分散した情報処理装置を有する情報処理システムを示す図である。
【００１８】
同図において、１４は、分散認証サーバを構成する装置（以後、メンバと呼ぶ）ＡＳ（１），…，  ＡＳ（ｋ）  である。１１は、各装置間で（他の通信路からアクセスできない様に設計されているなど）物理的に安全に秘密の通信を行うことができる秘密通信路であり、１２は、全てのメンバを情報を公開することができるように相互接続する放送型通信路である。ここで、メンバの数は、効率の面から２０以下程度の比較的少ない数であるとする。
【００１９】
通信システムを構成する全装置の数は、メンバに比べてかなり多くてもよく、メンバと秘密通信路１１を介して接続される。また、各装置間は、通常の（安全でない）通信路１３によって通信する。以後、１つの装置が他の装置にあるサービス（例えば、ファイル転送、リモートプロシージャーコール等）の要求を送った場合、要求した装置を「クライアント」、この要求を受けサービスを提供する装置を「サーバ」と呼ぶこととする。図１において、１５は、このようなクライアントやサーバとなる装置Ｃ／Ｓ（１），…，  Ｃ／Ｓ（ｎ）  を示している。但し、メンバがクライアントやサーバとなる場合もある。
【００２０】
本実施例では、このようなクライアントやサーバに、互いの認証や通信内容の認証を実現する。また、クライアントとサーバの間に秘密通信を行うための秘密鍵の共有も実現する。更に、秘密情報をメンバ間で分散して管理・計算するために、従来の印象サーバに比べて安全であるという利点も得られる。以下では、クライアントがサーバにサービスを要求するために、自分を識別する認証を求めた時に、認証を求めるクライアントを「証明者」、認証を与えるサーバを「認証者」と呼ぶ。
【００２１】
図２は、メンバとなる装置のブロック構成を示す図である。同図において、２１は、秘密通信路１２または放送型通信路１３により、他の装置と通信を行なうための通信部である。２２は、演算処理部であり、記憶部２４のプログラムに従って、後述する一方向性ハッシュ関数などの各種演算や判定の処理を行なうとともに、装置各部を制御する。２３は、例えば疑似乱数発生器のような乱数発生部であり、ランダムな値を生成するために利用される。２４は、演算処理部２２が実行すべきプログラムや、処理の過程で生成される演算結果等の情報や、他の装置から受信した情報、各種パラメータなどを記憶するための記憶部である。また、通信システムのメンバ以外の装置も、メンバと同様のハードウェア構成をとるものとする。
【００２２】
分散認証プロトコルの基本部分は、以下に説明するＶＳＳ（ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ：確認可能な秘密分散）  プロトコルである。ＶＳＳによれば、１つの秘密情報を、その過半数未満では元の秘密情報を推測できず、過半数の情報が正しければ元の秘密情報を復元できるような複数の秘密部分に分散する技術である。
【００２３】
［ＶＳＳプロトコル］
与えられた有限体Ｆ上の秘密を確認可能に分散する手順を以下に説明する。
【００２４】
図３は、秘密ｓ  と部分行列Ｓ  との関係を示す図である。
【００２５】
本実施例において、ある秘密の元ｓ  に対する部分行列Ｓ＝［ｓ（ｉ，ｊ）］（ｉ，ｊ＝１，．．．，ｎ）とは、各行ベクトルＳ＿ｒ（ｉ）＝［ｓ（ｉ，１），．．．，ｓ（ｉ，ｎ）］（ｉ＝１，．．．，ｎ）の各要素が、ある秘密ｓ＿ｒ（ｉ）を定数項とするｔ次の多項式ｆｉのｎ個の異なる値ｉｌ，．．．，ｉｎ  に対する値ｆｉ（ｉｌ），．．．，ｆｉ（ｉｎ）  となり、各列ベクトルＳ＿ｃ（ｊ）＝［ｓ（１，ｊ），．．．，ｓ（ｎ，ｊ）］（ｊ＝１，．．．，ｎ）が、ある秘密ｓ＿ｃ（ｊ）を定数項とするｔ次の多項式ｇｉのｎ個の異なる値ｉｌ，．．．，ｉｎ  に対する値ｇｉ（ｉｌ），．．．，ｇｉ（ｉｎ）  になり、更に、ベクトル［ｓ＿ｒ（１），．．．，ｓ＿ｒ（ｎ）］  及び［ｓ＿ｃ（１），．．．，ｓ＿ｃ（ｎ）］  の両方は、元の秘密ｓ  を定数項とするｔ次の多項式ｆ  及びｇ  の値ｆ（ｉｌ，．．．，ｉｎ）及びｇ（ｉｌ，．．．，ｉｎ）になっているものである。
話型確認可能な秘密分散方式に用いられている部分行列に、以下に説明するように、更に条件が付けられた秘密部分のｎ  ×ｎ  行列Ｓ＝［ｓ（ｉ，ｊ）］（ｉ，ｊ＝１，．．．，ｎ）である。
【００２６】
まず、各行ベクトルＳ＿ｒ（ｉ）＝［ｓ（ｉ，１），．．．，ｓ（ｉ，ｎ）］（ｉ＝１，．．．，ｎ）が、ある秘密ｓ＿ｒ（ｉ）に対する秘密部分ベクトル（ベクトルの要素ｊ  がある秘密分散方式における加入者ｊ  の秘密部分であるベクトル）になり、各列ベクトルＳ＿ｃ（ｊ）＝［ｓ（１，ｊ），．．．，ｓ（ｎ，ｊ）］（ｊ＝１，．．．，ｎ）が、ある秘密ｓ＿ｃ（ｊ）に対する秘密部分ベクトルになる。
【００２７】
ただし、前述の秘密ｓ＿ｒ（ｉ）及びｓ＿ｃ（ｊ）よりなるベクトル［ｓ＿ｒ（１），．．．，ｓ＿ｒ（ｎ）］  及び［ｓ＿ｃ（１），．．．，ｓ＿ｃ（ｎ）］  の両方は、元の秘密ｓ  に対する秘密部分ベクトルになる。秘密分散処理のときに、このように構成された部分行列の列ベクトルｉ  （ｉ＝１，．．．，ｎ  ）及び秘密ｓ＿ｒ（ｉ）を、加入者ｉ  の秘密部分情報として各加入者ｉ  に送信することによって、秘密復元処理のときに、部分情報を配った加入者が不正をしなければ、各加入者によって放送された部分情報が正しいかどうかを非常に高い確率で確認できる。
【００２８】
また、本実施例では、元の秘密情報を持ち、秘密部分情報を配った加入者が不正をした場合でも秘密復元処理のとき放送される部分情報が正しいかどうかを確認するために、秘密部分情報を配る上で各加入者ｉ  （ｉ＝１，．．．，ｎ  ）に対応する秘密ｓ＿ｒ（ｉ）の認証子のような役割を果たす値を一方向性ハッシュ関数（池野、小山：”現代暗号理論”、ｐｐ．２２４−２２５、電子情報通信学会、１９８６、参照）によって生成する。
【００２９】
次に、この一方向性ハッシュ関数について説明する。
【００３０】
一方向性ハッシュ関数とは、データ圧縮型スクランブルを行う関数であり、入力値から出力値を求める演算は容易であるが、出力値から入力値を求める逆演算は困難である関数である。ただし、本実施例では、従来の非対話型確認可能な秘密分散方式に用いられる一方向性関数に比べると、特殊な代数学的な性質を持たなくてもよく、計算処理の高速な一方向性ハッシュ関数を利用できる。
【００３１】
一方向性ハッシュ関数の具体例として、Ｒ．  Ｍｅｒｋｌｅ  （”Ｏｎｅ  Ｗａｙ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ＤＥＳ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −Ｃｒｙｐｔｏ’８９，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．  ４３５，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９０  ）によってＤＥＳ  （Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）のようなブロック暗号を用いた一方向性ハッシュ関数を提案されている。
【００３２】
図８は、一方向性ハッシュ関数の具体的な構成を説明する図である。
【００３３】
同図において、（ａ）  は、ＤＥＳ  によるブロック暗号化を示しており、８１は、６４ビットの入力及び５６ビットの鍵から６４ビットの出力が得られる暗号化回路（図８では、ＤＥＳ  をＥ  で表している）である。
【００３４】
（ｂ）  は、このＤＥＳ  を部分処理として利用し、入力の長さが１１９  ビットで出力の長さが１１２  ビットとなる関数Ｆ  の処理を示しており、８２は、関数演算回路である。この処理は、次のように定義される。
【００３５】
まず、入力を二つの部分ｋ，ｘ  に分ける（ただし、その一つの部分ｋ  長さを５５ビットとし、残りの部分ｘ  の長さを６４ビットとする）。次に、その部分ｘ  をＤＥＳ  の入力とし、残りの部分ｋ  と’０’  を連続した値’０’，ｋ  を５６ビットの鍵として得られた出力とｘ  とのＸＯＲ  を計算した結果を、関数Ｆ  の出力における左側の６４ビットとする。同様に、同じ部分ｘ  を入力とし、残りの部分ｋ  と’１’  を連続した値’１’，ｋ  を鍵として得られた出力とｘ  とのＸＯＲ  を計算した結果（６４ビット）より４８ビットを関数Ｆ  の残りの部分（右側の４８ビット）とする。これによって得られた二つの出力を連続した結果が１１２  ビットのＦ  関数の出力となる。
【００３６】
（ｃ）  は、与えられたメッセージを入力として、一方向性ハッシュ関数のハッシュ値を出力とする処理を示しており、８３は、ハッシュ関数処理部である。この処理は、次のように実行される。
【００３７】
まず、与えられたメッセージの最初の１１９  ビットを上述の関数Ｆ  の入力として、最初の１１２  ビットの出力を得る。次に、その出力を再び入力の１１２  ビット分とし、以後メッセージから残りの７  ビット分を連続して繰り返し関数Ｆ  に入力する。最後に、全メッセージを入力したときに（メッセージの最後の７  ビットを入力するために足りないビットがあれば適当に’０’  を加える）得られた１１２  ビットの出力をメッセージに対するハッシュ値とする。
【００３８】
前述のように計算されたハッシュ関数の一方向性（１つのハッシュ値が与えられたとき、同じハッシュ値が得られるような異なる入力のメッセージを求めることが極めて困難であること）は、用いられるＤＥＳ  のようなブロック暗号の安全性（入力が与えられたとき出力は鍵によるランダムな変数になり、出力が与えられたとき入力は鍵によるランダムな変数になる）によって与えられることが、Ｒ．  Ｍｅｒｋｌｅ  より示されている（前述の論文参照）。
【００３９】
更に、同じ論文では前述のハッシュ関数より効率のよい一方向性ハッシュ関数も提案されており、ブロック暗号を利用しない効率的な一方向性ハッシュ関数がＲ．Ｒｉｖｅｓｔ（”Ｔｈｅ  ＭＤ４  ｍｅｓｓａｇｅ  ｄｉｇｅｓｔ  ａｌｇｏｒｉｔｈｍ”，  Ａｄｖａｎｃｅｓ  ｉｎ  ＣｒｙｐｔｏｌｏｇｙーＣｒｙｐｔｏ’９０，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｖｏｌ．  ５３７，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９１．  ＮＩＳＴ  Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｈａｓｈ，  Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  Ｘ９．３０−１９９ｘ）によって提案されている。
【００４０】
次に、本実施例におけるＣｕｔ  ａｎｄ  Ｃｈｏｏｓｅ処理を説明する。
【００４１】
従来の対話型確認可能な秘密分散方式で行われるＣｕｔ  ａｎｄ  Ｃｈｏｏｓｅのように、秘密分散処理のとき全ての加入者が受け取った秘密部分情報が、確認可能に分散された秘密の部分情報となるかどうかを確認するために、元の秘密ｓ  に対する部分行列及びハッシュ値を分配すると同時にｋ  個のランダムに選ばれた秘密ｌ１，．．．，ｌｋ  に対する部分行列及びハッシュ値を分配し、全加入者によってランダムに決められたｋ／２  の秘密（ｌｉ（１），．．．，ｌｉ（ｋ／２）  ）に関する全ての秘密情報を放送し、残りのｋ／２  の秘密（ｌｊ（１），．．．，ｌｊ（ｋ／２）  ）に対してｌｊ（１）＋ｓ，．．．，ｌｊ（ｋ／２）＋ｓ  に関する全ての秘密情報を放送し、全ての放送された情報の中には誤りを持つ部分の数がｔ  より多ければ、秘密分散処理が正しくないと判断される。
【００４２】
以上によって、従来の確認可能な秘密分散方式の条件（ｃ），（ｄ）  の代わりに、次の条件（ｃ’），（ｄ’）  を満たす秘密分散方式が実現でき、それを用いて安全に分散計算を実行する方式及び通信システムが実現できる。
【００４３】
（ｃ’）不正な部分情報が正しい部分情報と混在したとき、ｔ＋１  個の正しい部分情報があっても元の秘密情報を復元できない場合が存在するが、不正をした加入者の識別は可能である。
【００４４】
（ｄ’）全ての加入者がその秘密の部分情報を受け取ったとき、その部分情報がある秘密情報ｘ  を復元するための正しい情報でなければ、復元処理のときに不正をした加入者の識別が可能である。
【００４５】
これらの条件は、従来方式のように不正な加入者があっても秘密を復元、すなわち誤り訂正は行えないが、不正な加入者は識別、すなわち誤り検出は可能にするものである。条件（ｃ），（ｄ）  があれば不正な加入者がいても正しく分散演算が実行できる（正当性に対するフォールトトレランスを実現できる）が、条件（ｃ’），（ｄ’）  に変更しても不正な加入者は検出できるので警告などを行い再実行することによって正しい出力を得ることができ、正当性に対するフォールトトレランスを実現することができる。
【００４６】
よって、本実施例では、分散された秘密を復元するとき不正な加入者があった場合には、復元できないこともありえるが不正を行った加入者の識別は可能であるような確認可能な秘密分散方式を提案する。これによって、前述の対話的な方式（１）  及び暗号的な方式（２）  の中間に位置する必要な計算量と通信量の両方が実用的なオーダーになる確認可能な秘密分散方式が実現できる。
【００４７】
以下、与えられた有限体Ｆ  上の秘密の確認可能な分散を実現する方法を、具体的に説明する。
【００４８】
まず、秘密ｓ  に対する部分行列Ｓ  を、具体的に説明する。
【００４９】
ある与えられた有限体上の秘密の元ｓ  に対する部分行列Ｓ＝［ｓ（ｉ，ｊ）］（ｉ，ｊ＝１，．．．，ｎ）  とは、各行ベクトルＳ＿ｒ（ｉ）＝［ｓ（ｉ，１），．．．，ｓ（ｉ，ｎ）］（ｉ＝１，．．．，ｎ）の要素が、ｓ＿ｒ（ｉ）を定数項とするｔ  次の多項式ｆｉのｎ  個の異なる値ｉ１，．．．，ｉｎ  に対する値ｆｉ（ｉ１），．．．，ｆｉ（ｉｎ）  になり、各列ベクトルＳ＿ｃ（ｊ）＝［ｓ（１，ｊ），．．．，ｓ（ｎ，ｊ）］（ｊ＝１，．．．，ｎ）の要素が、ｓ＿ｃ（ｊ）を定数項とするｔ  次の多項式ｇｊのｎ  個の異なる値ｊ１，．．．，ｊｎ  に対する値ｇｊ（ｊ１），．．．，ｇｊ（ｊｎ）  になり、更に、前述の値のベクトル［ｓ＿ｒ（１），．．．，ｓ＿ｒ（ｎ）］  及び［ｓ＿ｃ（１），．．．，ｓ＿ｃ（ｎ）］  の両方は、元の秘密ｓ  を定数項とするｔ  次の多項式ｆ  及びｇ  の値ｆ（ｉ１，．．．，ｉｎ）及びｇ（ｊ１，．．．，ｊｎ）になっているものである。
【００５０】
次に、本実施例の処理を、与えられた有限体上の秘密を全ての加入者間で秘密に分散保持されるように秘密部分を分配する秘密分散処理と、全ての加入者に分散された秘密または（不正があった場合に）不正をした加入者を明らかにする秘密復元処理の二つの処理に分けて説明する。
【００５１】
（１）  秘密分散処理
秘密分散処理とは、秘密の元ｓ  を持っている加入者ｄ  がｓ  に対する秘密部分を分配する処理である。図５に、その処理手順を示す。同図において、処理Ｒｊ，ｉ  は、ラウンドｊにおける加入者ｉの実行する処理である。
【００５２】
以下において、ｈ  は効率的な（高速な計算方式のある）一方向性ハッシュ関数を表す。例えば高速なブロック暗号化関数によって構成されたハッシュ関数（前出の”現代暗号理論”参照）が用いられる。安全性パラメータｋ  はある定数ｋ’に対してｋ＝ｎｋ’  を満たす。この場合、秘密分散処理の確認が誤る確率は、Ｃｕｔ  ａｎｄ  Ｃｈｏｏｓｅ処理によって、２＾（−ｋ’（ｔ＋１））になる（Ｔ．  Ｒａｂｉｎ，  Ｍ．  Ｂｅｎ−Ｏｒ  ”Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  ａｎｄ  Ｍｕｌｔｉｐａｒｔｙ  Ｐｒｏｔｏｃｏｌｓ  ｗｉｔｈ  Ｈｏｎｅｓｔ  Ｍａｊｏｒｉｔｙ”  参照）。
【００５３】
（ラウンド１）加入者ｄ  は、乱数発生部２３を用いて、元の秘密ｓ  及び与えられた有限体上のランダムに選ばれた秘密の元ｌ１，．．．，ｌｋ  に対する部分行列Ｓ，Ｌ１，．．．，Ｌｋ  を生成する。そして、図４に示すように、秘密値ｓ＿ｒ（１），．．．，ｓ＿ｒ（ｎ），ｌ１＿ｒ（１），．．．，ｌ１＿ｒ（ｎ），．．．，ｌｋ＿ｒ（１），．．．，ｌｋ＿ｒ（ｎ）  に対する一方向性ハッシュ関数の値ｓ＊を、演算処理部２２により計算する。
【００５４】
加入者ｄ  は、各加入者ｉ  （ｉ＝１，．．．，ｎ  、但し自分は除く）に対して、生成した各部分行列の各列ベクトルＳ＿ｃ（ｉ），Ｌ１＿ｃ（ｉ），．．．，Ｌｋ＿ｃ（ｉ）及び秘密ｓ＿ｒ（ｉ），ｌ１＿ｒ（ｉ），．．．，ｌｋ＿ｒ（ｉ）（情報Ｂ１．ｉ）を、秘密通信路１１を用いて送信し、全加入者間でハッシュ値ｓ＊（情報Ｂ１．ｄ）を、放送通信路１２を用いて放送する（処理Ｒ１．ｄ）。
【００５５】
（ラウンド２）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は乱数発生部２３を用いて、ｋ’個のランダムに選択されたビット（情報Ｂ２．ｉ）を放送する（処理Ｒ２．ｉ）。それらのランダムに選ばれたｋ’個のビットをＢｉ＿１，．．，Ｂｉ＿ｋ’  、ｎ  人の全ての加入者に対する全ビットをＢ１，．．．，Ｂｋ  と呼ぶ。
【００５６】
（ラウンド３）加入者ｄ  は、ラウンド２で放送された各ビットＢｊ（ｊ＝１，．．．，ｋ  ）に対して、Ｂｊが１  であればラウンド１で加入者ｄ  が生成した部分行列Ｌｊを放送し、Ｂｊが０  であればラウンド１で加入者ｄ  が生成した部分行列Ｓ  とＬｊの要素毎の有限体上の加算結果（Ｓ＋Ｌｊと書く）を放送する（処理Ｒ３．ｄ）。加入者ｄ  が放送した情報は、図５でＢ３．ｄと表わされている。
【００５７】
（ラウンド４）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、ラウンド１で秘密に受信した情報Ｂ１．ｉの中で、各値ｊ  （ｊ＝１，．．．，ｋ  ）に対して、列ベクトルＬｊ＿ｃ（ｉ）  及びｌｊ＿ｒ（ｉ）  （ラウンド２で放送されたビットＢｊが１  の場合）あるいは  Ｌｊ＿ｃ（ｉ）＋Ｓ＿ｃ（ｉ）  及びｌｊ＿ｒ（ｉ）＋ｓ＿ｒ（ｉ）（Ｂｊが０  の場合）が、ラウンド３で放送された部分行列に対応する列ベクトル及び秘密値と等しいかどうかを確認し、ある値ｊ  に対して等しくなければ、加入者ｄ  の判定メッセージ（情報Ｂ４．ｉ）を放送する（処理Ｒ４．ｉ）。
【００５８】
（ラウンド５）加入者ｄ  は、ラウンド４で判定メッセージ（情報Ｂ４．ｉ）が放送された場合に、判定メッセージを放送した各加入者ｊ  に関するラウンド１で加入者ｄ  が秘密に送信した情報Ｂ１．ｊ（ここでは、情報Ｂ５．ｄ）を放送する（処理Ｒ５．ｄ）。
【００５９】
（後処理）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、ラウンド５で放送された情報が正しくなければ、あるいはラウンド４に放送された判定メッセージの数がしきい値ｔ  より多ければ、加入者ｄ  が不正をしたと判断する（処理Ｐｉ）。
【００６０】
以上のラウンド１から５までで各加入者ｉ  が受信した全ての情報を、ｓ＿ｉ  とする。
【００６１】
（２）  秘密復元処理
秘密復元処理とは、上述の秘密分散処理により各加入者が持っている情報ｓ＿ｉ  から、全ての加入者によって元の秘密ｓ  を計算するための処理である。図６にその手順を示す。
【００６２】
（ラウンド１）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、部分情報ｓ＿ｉ  含まれている秘密値ｓ＿ｃ（ｉ）及びｓ＿ｒ（ｉ）（情報Ｂ１．ｉ）を放送する（処理Ｒ１．ｉ）。
【００６３】
（ラウンド２）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、ラウンド１で放送された値の内ｔ＋１  個の値ｓ＿ｃ（ｉ，１），．．．，ｓ＿ｃ（ｉ，ｔ＋１）  及びｓ＿ｒ（ｉ，１），．．．，ｓ＿ｒ（ｉ，ｔ＋１）  を選び、多項式補間処理の結果ｓ（ｃ）及びｓ（ｒ）を求め、両方が等しくなり、かつ残りの放送された値がその値ｓ（ｃ）＝ｓ（ｒ）  に対応する同じ多項式の正しい値になるかどうかを確認する。全ての値が正しければ、元の秘密ｓ  はｓ（ｃ）＝ｓ（ｒ）  と等しいと判断し復元処理が終わる。一方、同じ多項式に対応しない値が放送された場合には、部分情報ｓ＿ｉ  に含まれている列ベクトルＳ＿ｃ（ｉ）（情報Ｂ２．ｉ）を放送する（以上、処理Ｒ２．ｉ）。
【００６４】
（ラウンド３）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、ラウンド２で放送された列ベクトルＳ＿ｃ（ｊ）（ｊ＝１，．．．，ｎ  ）から部分行列Ｓ’を生成し、１，．．．，ｎ  から異なるｔ＋１  個の値を含む全ての集合ｔ１，．．．，ｔｍ  （全部でｍ＝ｎＣｔ＋１＝ｎ！／（（ｔ＋１）！（ｎ−ｔ−１）！）  個の集合がある）に対する列ベクトルの集合Ｔ１，．．．，Ｔｍ  を選び、それぞれの行と列に対する多項式補間処理の結果ｓ’＿ｒ（１），．．．，ｓ’＿ｒ（ｎ）  及びｓ’＿ｃ（１），．．．，ｓ’＿ｃ（ｎ）  を求め、更にこれらの値の多項式補間処理の結果ｓ’（ｒ）  及びｓ’（ｃ）  を求め、両方が等しくなり、かつそれらの列ベクトルの全ての要素がそれぞれの値ｓ’＿ｃ（１），．．．，ｓ’＿ｃ（ｎ）  及びｓ’＿ｒ（１），．．，ｓ’＿ｒ（ｎ）に対応する同じ多項式の正しい値になるかどうかを確認する。
【００６５】
このように確認されたｔ＋１  個の列ベクトルを含む集合Ｔ１，．．，Ｔｍの内に異なる正しい部分行列に対応する集合の数が最大でｔ＋１  個になり、それらの部分行列をＳ＿１，．．．，Ｓ＿Ｔ  （ただし、Ｔ＜ｔ＋１  ）と呼ぶ。正しい部分行列が一個しかなければ（Ｔ＝１  ）、その行列に対する秘密ｓ  が元の秘密と等しいと判断し、対応しない列ベクトルが不正をした加入者を表す。正しい部分行列が二つ以上があれば、各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は持っている全ての部分情報ｓ＿ｉ  （情報Ｂ３．ｉ）を放送する（以上、処理Ｒ３．ｉ）。
【００６６】
（後処理）各加入者ｉ  （ｉ＝１，．．．，ｎ  ）は、ラウンド３で放送された情報ｓ＿ｊ  （ｊ＝１，．．．，ｎ  ）を用いて、ラウンド４で計算した正しい部分行列Ｓ＿１，．．．，Ｓ＿Ｔ  （ただし、Ｔ＜ｔ＋１  ）に対して、上述の秘密分散処理と同一の一方向性ハッシュ関数を計算し、全ての放送された情報が正しく、分散処理のラウンド１で放送された値ｓ＊に対応するかどうかを確認する。これらの確認に対して正しい（最大一つしかありえない）部分行列に対応する秘密ｓ’は元の秘密ｓ  と等しいと判断する。それに対して前述の確認に対して正しい部分行列がなかったならば、秘密を分散加入者ｄ  が不正したと判断する（処理Ｐｉ）。
【００６７】
［分散された秘密の線形結合処理］
上述の確認可能な秘密分散処理によって、与えられた有限体上の元｛１，．．．，ｐ−１｝  の内にある２つの秘密の元ｘ  とｙ  が分散されたとき（このとき、各加入者ｉ  が秘密の元ｘ  とｙ  に対応する秘密部分ｘ＿ｉ  及びｙ＿ｉ  を持つ）、通信を行わずに、与えられた有限体上の和ｘ＋ｙ  に対応する秘密部分（ｘ＋ｙ）＿ｉ  を、次のように計算する。
【００６８】
まず、各加入者が持っている部分行列の列ベクトルＸ＿ｃ（ｉ）及びＹ＿ｃ（ｉ）かつ秘密値ｘ＿ｒ（ｉ）及びｙ＿ｒ（ｉ）を要素毎に加算すると、その加算結果Ｘ＿ｃ（ｉ）＋Ｙ＿ｃ（ｉ）  及びｘ＿ｒ（ｉ）＋ｙ＿ｒ（ｉ）  が、ｘ＋ｙ  に対する部分行列の列ベクトル及び秘密値になることは、部分行列の定義（行と列の要素が多項式の値となる）から明らかである。
【００６９】
また、秘密復元処理において部分情報を確認するために用いられる一方向性ハッシュ関数の値ｘ＊及びｙ＊は、両方を記憶し、加算の結果ｘ＋ｙ  を復元処理のときに、必要であれば両方を用いることによって、秘密ｘ＋ｙ  に対応する部分行列Ｘ＋Ｙ  を確認する。
【００７０】
また、分散された１つの秘密の元ｘと公開の元ａとの乗算を分散して計算するために、各加入者が持っている部分行列の各要素とａとの乗算を行った結果がｘ＊ａに対する部分行列の要素となる。よって、上述の処理により、図７に示すように、分散された２つの秘密の元ｘとｙ、及び公開の元ａ、ｂを用いた線形結合ａ＊ｘ＋ｂ＊ｙ  は、そのグループに参加する各加入者間で、対話せずに分散して計算できる。
【００７１】
以上のようにして、確認可能な方法で、秘密をメンバ間で分散することができる。
【００７２】
次に、メンバ間で疑似乱数を分散して生成する分散疑似乱数生成（Ｓｈａｒｅｄ  ｐｓｅｕｄｏ−ｒａｎｄｏｍ  Ｓｅｃｒｅｔ  Ｇｅｎｅｒａｔｉｏｎ）  プロトコルについて説明する。
【００７３】
［分散疑似乱数生成プロトコル］
分散認証サーバを構成するメンバＡＳ（１），…，  ＡＳ（ｋ）  は、分散疑似乱数ｒを制せするために、メンバＡＳ（ｉ）  に対してｒの秘密部分ｒ（ｉ）（ｉ＝１，  …，ｋ）  を出力する。このプロトコルは、図８に示すようにして実現される。
【００７４】
各メンバＡＳ（ｉ）  は、有限体上の元として表現される秘密の疑似乱数ｒｉを生成する（処理８１）。
【００７５】
各メンバＡＳ（ｉ）  は、前述した確認可能な秘密分散処理を用いて秘密の疑似乱数ｒｉを秘密に分散する。これを各メンバが行うことにより、各メンバＡＳ（ｊ）（ｊ＝１，…，ｋ）  は、各メンバの秘密部分ｒ１（ｊ），…，ｒｍ（ｊ）を持つことになる。但し、ｍ（≦ｋ）は、正しく秘密分散を行ったことが確認されたメンバの数である（処理８２）。
【００７６】
各メンバＡＳ（ｊ）  は、上述の秘密部分を加え合わせ、秘密の疑似乱数ｒ  のＡＳ（ｊ）  に対する秘密部分となるｒ（ｊ）＝ｒ１（ｊ）＋  …＋ｒｍ（ｊ）を生成する（処理８３）。
【００７７】
この秘密の疑似乱数ｒ  は、メンバの過半数が共謀しない限り、誰も知ることができない数である。以上の様にして、疑似乱数を分散して生成し、この疑似乱数を証明者と認証者間の会話鍵とすることができる。
【００７８】
次に、メンバ間で秘密鍵暗号処理を分散して実行するプロトコルを示す。これは、秘密鍵暗号化されるデータが、分散された秘密データである場合と、公開されたデータである場合とで、処理は異なる。
【００７９】
［分散秘密データの分散秘密鍵暗号化／復号］
図９の（ａ）は、このプロトコルを説明する図である。長さＬのＮ個のブロックｍ１，  …，ｍＮ  で構成されるメッセージをｍとする。但しＶＳＳプロトコルは、有限体ＧＦ（２Ｌ）上で実行される。メンバＡＳ（ｉ）  には、各々の秘密部分ｍ１（ｉ），…，ｍＮ（ｉ）が秘密に分散されているものとする。また、メッセージｍと同じ長さを持つ秘密鍵ｐｋもまた長さＬのＮ個のブロックｐｋ１，…，ｐｋＮに分割され、同じメンバ間で秘密に分散され、メンバＡＳ（ｉ）  は、各々の秘密部分ｐｋ１（ｉ），…，ｐｋＮ（ｉ）  を持つ。
【００８０】
秘密鍵ｐｋを用いたメッセージｍの秘密鍵暗号処理を行うために、各メンバＡＳ（ｉ）  は与えられた有限体上での加算をブロック毎に以下のように行なう。
【００８１】
ｃ１（ｉ）＝ｍ１（ｉ）＋ｐｋ１（ｉ），  …，  ｃＮ（ｉ）＝ｍＮ（ｉ）＋ｐｋＮ（ｉ）
ＶＳＳプロトコルは、準同形であるので、ｃ１（ｉ），…，ｃＮ（ｉ）は、暗号文ｃを長さＬ毎にＮ個のブロックに分割したｃ１，  …，ｃＮ  の秘密部分をに相当する。従って、前述の秘密復元処理を実行することによって、暗号文ｃが復元され、公開される。
【００８２】
これにより、秘密鍵ｐｋを持つ通信システム内の装置は、公開された暗号文ｃから元のメッセージｍを復号することができる。但し、秘密鍵ｐｋは使い捨てであり、再度使用されることはない。
【００８３】
［公開データの分散秘密鍵暗号化／復号］
メッセージｍが公開されている場合には、上述の暗号プロトコルでは、公開された暗号ｃからメッセージｍを引くことにより、秘密鍵ｐｋが知られてしますという問題が生じる。そこで、公開データについては、図９の（ｂ）  に示すようなプロトコルを用いる。
【００８４】
前記の場合と同様、メッセージｍは、長さＬのＮ個のブロックｍ１，  …，ｍＮ  で構成されているものとする。但し、その内容は、メンバには既知の公開データであるとする。また、秘密鍵ｐｋはメッセージｍの２倍の長さを持ち、長さＬの２Ｎ個のブロックｐｋ１ １，ｐｋ１ ２，…ｐｋＮ １，ｐｋＮ ２  に分割される。このｐｋは各メンバ間で秘密に分散され、メンバＡＳ（ｉ）  は、各々の秘密部分ｐｋ１ １（ｉ），ｐｋ１ ２（ｉ），…ｐｋＮ １（ｉ），ｐｋＮ ２（ｉ）  を持つ。
【００８５】
秘密鍵ｐｋｐｋを用いたメッセージｍの秘密鍵ｐｋ暗号処理を実現するために、各メンバＡＳ（ｉ）  は、与えられた  有限体上の次の演算をブロック毎に行う。但し、下記の式では、・は乗算、＋は加算を表している。
【００８６】
ｃ１（ｉ）＝ｍ１・ｐｋ１ １（ｉ）＋ｐｋ１ ２（ｉ），  …，  ｃＮ（ｉ）＝ｍＮ・ｐｋＮ １（ｉ）＋ｐｋＮ ２（ｉ）ＶＳＳプロトコルは、線形結合に対しても、準同形であるので、ｃ１（ｉ），…，ｃＮ（ｉ）は、暗号文ｃを長さＬ毎にＮ個のブロックに分割したｃ１，  …，ｃＮ  の秘密部分をに相当する。従って、前述の秘密復元処理を実行することによって、暗号文ｃが復元され、公開される。
【００８７】
以上の様に、本プロトコルは、ｐｋｊ １  とｐｋｊ ２  （ｊ＝１，  …，Ｎ）  の２種類の鍵を用いるので、メッセージｍが公開のデータであっても、秘密鍵ｐｋは知られる個とがない。ここで、長さＬは短い方が暗号化の演算が簡単となるが、改竄者が暗号文ｃを偽の暗号文ｃ’に変更して、偽のメッセージｍ’を得させることができる確率は、２−Ｌ  であるので、安全面からはＬを余り小さくすることはできない。よって、Ｌは、３２程度が適当である。
【００８８】
復号に関しては、秘密鍵ｐｋを共有する通信システム内の装置は、秘密鍵ｐｋと暗号文ｃを長さＬ毎に分解して、ｐｋｊ １  ，ｐｋｊ ２  とｃｊ（ｃｊ−ｐｋｊ ２）／ｐｋｊ １の演算を実行することにより、ｍｊを得ることができる。これにより、元のメッセージｍを復号することができる。但し、この場合も、秘密鍵ｐｋは使い捨てであり、再度使用されることはない。
【００８９】
［認証プロトコル］
以上のプロトコルを用いて、共通鍵を用いた認証が従来の集中認証サーバに代わり、分散認証サーバにより、以下のようにして実現される。
【００９０】
認証プロトコルは、証明者が分散認証サーバから認証メッセージを受け取るための通信と、証明者が認証社に認証データを示すための通信とを含む。これを「オンライン処理」と呼ぶ。
ところで、このオンライン処理を行う前提として、分散認証サーバと証明者や認証者となる装置との間の秘密鍵の共有処理や、分散認証サーバによる会話鍵の生成処理を必要とする。これを「オフライン処理」と呼ぶ。このオフライン処理は、オンライン処理中に秘密鍵や会話鍵が必要となる度に実行してもよいが、それではオンライン処理の処理時間や通信時間が長くなってしまう。
【００９１】
そこで、オフライン処理をオンライン処理に先立って実行しておくことで、オンライン処理を効率よく行うことができる。以下に、図１０の（ａ）  につき「オフライン処理」を、（ｂ）  につき「オンライン処理」を説明する。
【００９２】
［オフライン処理］
分散認証サーバを構成するメンバ間であらかじめ共有される必要のある情報は、全装置の秘密鍵に関する情報である。しかしながら、分散秘密鍵暗号化／復号プロトコルにつき説明したように、証明者と分散認証サーバ間で用いられる秘密鍵はメッセージ後とに使い捨てであるので、非常に多くの鍵を生成する必要がある。この処理は、以下の秘密鍵配送処理により実行される。また、証明者と認証者との間の会話鍵として用いられる分散疑似乱数の生成処理も、以下のようにオフラインで実行される。
【００９３】
［秘密鍵配送処理］
通信システム内で、認証を受けたい装置ｊは、予め、前述の秘密分散処理によって任意に選んだ十分大きな個数Ｍの疑似乱数ｐｋｊ １，…，ｐｋｊ Ｍ    を各メンバに分散する。これにより、メンバＡＳ（ｉ）  はその疑似乱数の秘密部分ｐｋｊ １（ｉ），  …，ｐｋｊ Ｍ（ｉ）  を受け取る。但し、ｊが正しく秘密を分散していなければ、ｊは自分の秘密鍵ｐｋｊを用いて認証サービスを受けられなくなるだけなので、分散された情報が正しいかどうかを確認する後処理は、この場合は省略してもよい。また、ｊとメンバ間に、ｊが嘘をついていないことを全員で確認するための放送型通信路がなくても構わない。
【００９４】
この処理では、ｊは十分大きな数の秘密鍵ｐｋｊ ｉ  （ｉ＝１，  …，Ｍ）  を、各メンバｈ（ｈ＝１，  …，ｋ）  は、その秘密部分であるｐｋｊ ｉ（ｈ）（ｉ＝１，  …，Ｍ）  を、リストとして保持する。前述したように、秘密鍵は使い捨てであるので、ｊと各メンバｈとは、それぞれ、次に利用する鍵のリスト上の位置を示すインデックスｐｋｊ  、ｐｋｊ（ｈ）を保持しておく。そして、ｊは処理に余裕がある時に秘密鍵を生成し、通信システムが空いている時にこの秘密を分散するようにして、更新を続ける。
【００９５】
［疑似乱数生成処理］
図１１に示すように、秘密鍵配送処理と同様に、証明者と認証者との間で用いられる会話鍵である分散疑似乱数ｒ１，  …，ｒＱ  も、オフライン処理によって生成あれ、リストとして保持される。分散疑似乱数の生成は、前述の分散疑似乱数生成プロトコルで述べたように、全てのメンバが疑似乱数の分散処理を行う必要があるが、全てのメンバが同時に実行する必要はないので、各メンバは処理と通信システムに余裕がある場合に、この処理を実行し、他のメンバに分散しておけば良い。これにより、各メンバは分散された疑似乱数ｒ１（ｊ），…，ｒＱ（ｊ）をリストとして、その使用位置を示すインデックスと共に保持する。
【００９６】
［オンライン処理］
通信システム内のクライアントＰ（証明者）がサーバＶ（認証者）に送るための認証子を分散認証サーバから得るためのオンライン認証プロトコルは、以下のステップＳ１〜４により行われる。
【００９７】
（ステップＳ１）クライアントＰは、通常の通信路を用いてＡＵＴＨ ＲＥＱＵＥＳＴとして示される情報｛ｉｄ Ｐ，ｉｄ Ｖ，ｓ｝を含む要求メッセージ１０１を分散認証サーバを構成するメンバに送る。但し、ｉｄ ＰはクライアントＰを、ｉｄ ＶはサーバＶを特定するデータであり、ｓ  は任意に選ばれた乱数である。
【００９８】
（ステップＳ２）ＡＵＴＨ ＲＥＱＵＥＳＴを受け取ったメンバは、次の処理ステップＳ２１〜２６を行う。
【００９９】
（ステップＳ２１）現在の時刻を示すタイムスタンプを放送し、共通の時刻を確認する。
【０１００】
（ステップＳ２２）分散秘密データの分散秘密鍵暗号化プロトコルを利用して、証明者と認証者との間の会話鍵ｃｋ１，…，ｃｋａとして用いる分散疑似乱数ｒｚ，  …，ｒｚ＋ａ−１  をｐｋＶ ｘ，…，ｐｋＶ ｘ＋ａ−１を秘密の暗号鍵として暗号化する。但し、ａ  は疑似乱数の数を表し、ｚ  とｘ  は、それぞれ疑似乱数リスト及び秘密鍵ｐｋリストの始まりを表すインデックスである。このとき、ｚ  とｘ  は、それぞれｚ＝ｚ＋ａ，ｘ＝ｘ＋ａ  と更新される。このようにして暗号化された結果をＣＴ １，  …，  ＣＴ ａとする。
【０１０１】
（ステップＳ２３）公開データの分散秘密鍵暗号化プロトコルを利用して、公開のタイムスタンプと証明者の識別子であるｉｄ ＰをステップＳ２２と同じ秘密鍵ｐｋリストから２ｂ個の秘密鍵ｐｋＶ ｘ，…，ｐｋＶ ｘ＋２ｂ  によって暗号化する。そしてｘ＝ｘ＋２ｂ＋１と更新する。この暗号化の結果をＣＴ ａ＋１，  …，  ＣＴ ａ＋ｂとし、ステップＳ２２の結果と併せてＣＴ １，  …，  ＣＴ ａ＋ｂとし、ステップＳ２２で更新前のインデックスｘと併せて認証子とする。
【０１０２】
（ステップＳ２４）分散秘密データの分散秘密鍵暗号化プロトコルを利用して、ステップＳ２３で得られた認証者用の暗号文ＣＴ １，  …，  ＣＴ ａ＋ｂと、ステップＳ２２で用いた共通鍵ｃｋ１，…，ｃｋａを２ａ＋ｂ個の秘密鍵ｐｋＰ ｙ，…，ｐｋＰ ｙ＋２ａ＋ｂ  を暗号鍵として暗号化する。但し、ｙ  は証明者との秘密鍵リストの始まりを示すインデックスであり、ｙ＝ｙ＋２ａ＋ｂ＋１と更新される。このようにして暗号化された結果をＣＣＴ １，  …，  ＣＣＴ ２ａ＋ｂ  とする。
【０１０３】
（ステップＳ２５）公開データの分散秘密鍵暗号化プロトコルを利用して、ステップＳ１で公開された疑似乱数ｓ  と認証者の識別子であるｉｄ ＶをステップＳ２４と同じ秘密鍵リストから２ｃ個の秘密鍵ｐｋＰ ｙ，…，ｐｋＰ ｙ＋２ｃ  によって暗号化する。そして、ｙ＝ｙ＋２ｃ＋１と更新される。このようにして暗号化された結果をＣＣＴ ２ａ＋ｂ＋１，…，  ＣＣＴ ２ａ＋ｂ＋ｃ  とし、ステップＳ２４の結果と併せてＣＣＴ １，  …，  ＣＣＴ ２ａ＋ｂ＋ｃ  とする。
【０１０４】
（ステップＳ２６）秘密復元処理を用いて、秘密に分散されたＣＣＴ １，  …，  ＣＣＴ ２ａ＋ｂ＋ｃ  が復元され、証明者であるクライアントＰに、ステップＳ２４で更新される前のインデックスｙ  と併せて、認証メッセージ１０２として、通常の通信路を用いて送信する。
【０１０５】
（ステップＳ３）証明者Ｐは、受け取ったインデックスｙ  と、自分の秘密鍵リストからの秘密鍵ｐｋＰ ｙ，…，ｐｋＰ ｙ＋２ａ＋ｂ＋２ｃによって、受け取ったデータＣＣＴ １，  …，  ＣＣＴ ２ａ＋ｂ＋ｃ  から、公開データの分散秘密鍵復号プロトコルを利用して、疑似乱数ｃｋを復号する。そして、復号されたｓとｉｄ Ｖが正しいことを確認する。正しいことが確認されれば、復号された疑似乱数ｃｋを認証者との共通鍵として記憶し、復号された認証子１０３を認証者Ｖに送信する。
【０１０６】
（ステップＳ４）認証者Ｖは、認証子に含まれ得るインデックスｘと自分の秘密鍵リストからのｐｋＶ ｘ，…，ｐｋＶ ｘ＋ａ＋２ｂ  とによって、受け取った認証子から、公開データの分散秘密鍵復号プロトコルを利用して、タイムスタンプと証明者の識別子ｉｄ Ｐとを復号し、分散秘密データの分散秘密鍵復号プロトコルを利用して、疑似乱数ｃｋを復号する。そして、復号されたタイムスタンプと識別子ｉｄ Ｐとが正しいことを確認する。正しいことが確認されれば、証明者Ｐを認証し、復号された疑似乱数ｃｋを認証者との共通鍵として記憶する。
【０１０７】
［実施例２］
上述の実施例１では、証明者が認証者に送る認証子を攻撃者が盗聴し、記憶しておけば、攻撃者は、その認証子を認証者に示すことによって、証明者が意図しないサービスを認証者に要求することができ、証明者を混乱させることができる。この攻撃は、リプレイ攻撃と呼ばれている。
【０１０８】
そこで、本実施例では、このリプレイ攻撃を和らげるために、実施例１のオンライン処理のステップＳ３において証明者が認証者に送る認証子に、交信された時間情報を更に付加する。この手順を図１５に示す。本実施例は、実施例１とオンライン処理のステップＳ３と４に加えて、ステップＳ３’と４’を行う点でだけ異なり、他は同じであるので、このステップＳ３’と４’についてだけ説明する。
【０１０９】
（ステップＳ３’）証明者は、実施例１のステップＳ３を実行した後で、得られた会話鍵ｃｋを用いて新しいタイムスタンプＴ２と証明者の識別子ｉｄ Ｐを暗号化した｛Ｔ２，ｉｄ Ｐ｝＾ｃｋを認証子とあわせて認証者に送る。
【０１１０】
（ステップＳ４’）認証者は、実施例１のステップＳ４を実行して認証子を複合した後で、得られた会話鍵ｃｋを用いて付属メッセージ｛Ｔ２，ｉｄ Ｐ｝＾ｃｋを復号し、タイムスタンプＴ２と証明者の識別子ｉｄ Ｐを確かめ、Ｔ２が古ければ、サービス要求を受けつけない。
【０１１１】
【発明の効果】
以上説明したように、本発明によれば、従来の集中管理型の認証サーバに比して、サーバの信頼性、安全性に優れ、分散認証サーバを構成する過半数の装置が信頼できれば、以下のような効果を得ることができる。
【０１１２】
分散認証プロトコルによって、証明者や認証者に対して従来の集中管理による認証プロトコルと同一の認証機能を果たし、かつ、高いフォールトトレランスを実現する。
【０１１３】
証明者や認証者に対して、分散認証プロトコルのオンライン処理は、従来の認証プロトコルと同一のインタフェース（データ形式）を保証するので、従来の認証サーバと簡単に置き換えることができる。
【０１１４】
証明者や認証者に対して、分散認証プロトコルのオンライン処理は、従来の認証プロトコルと同一の計算量で実現される。
【図面の簡単な説明】
【図１】本発明の１実施例における通信システムのブロック構成を示す図である。
【図２】システムの各装置のブロック構成を示す図である。
【図３】秘密と部分行列との関係を示す図である。
【図４】一方向性ハッシュ関数による処理を示す図である。
【図５】秘密分散処理の手順を示す図である。
【図６】秘密復元処理の手順を示す図である。
【図７】分散された秘密の線形結合処理を説明する図である。
【図８】疑似乱数の分散生成処理の手順を示す図である。
【図９】分散秘密鍵暗号処理の手順を示す図である。
【図１０】分散認証プロトコルの手順を示す図である。
【図１１】オフラインの疑似乱数生成処理の手順を示す図である。
【図１２】オフラインの秘密鍵配送処理の手順を示す図である。
【図１３】分散認証プロトコルの手順を示す図である。
【図１４】分散認証プロトコルの手順を示す図である。
【図１５】実施例２の分散認証プロトコルの手順を示す図である。
【図１６】従来の認証プロトコルの手順を示す図である。
【符号の説明】
１１  秘密通信路
１２  放送通信路
１３  通常の通信路
１４  分散認証サーバを構成する装置
１５  クライアントやサーバとなる装置
２１  通信部
２２  演算処理部
２３  乱数発生部
２４  記憶部
１０１  要求メッセージ
１０２  認証メッセージ
１０３  認証子
１６１  証明者
１６２  認証者
１６３  認証センタ
１６４、１６５、１６６  データ
【図１】
0003610106.tif 000002
【図２】
0003610106.tif 000003
【図３】
0003610106.tif 000004
【図４】
0003610106.tif 000005
【図５】
0003610106.tif 000006
【図６】
0003610106.tif 000007
【図７】
0003610106.tif 000008
【図８】
0003610106.tif 000009
【図９】
0003610106.tif 000010
【図１０】
0003610106.tif 000011
【図１１】
0003610106.tif 000012
【図１２】
0003610106.tif 000013
【図１３】
0003610106.tif 000014
【図１４】
0003610106.tif 000015
【図１５】
0003610106.tif 000016
【図１６】
0003610106.tif 000017