(57)【要約】【課題】複数の被検証端末のそれぞれが主張する公開鍵を、複数の被検証端末のそれぞれが互いに信用し合うことができるか否かを判断する公開鍵の正当性判断方法を提供する。【解決手段】被検証端末Ａ，Ｂのそれぞれが、第１の分散情報ｓＡ，ｓＢから第２の分散情報ｓＡ１，ｓＡ２及び第２の分散情報ｓＢ１，ｓＢ２を生成し（ＳＴ１１）、被検証端末のそれぞれに配布し（ＳＴ１２）、第２の分散情報ｓＡ１，ｓＢ２及び他の被検証端末から自分自身が受け取った第２の分散情報ｓＢ１，ｓＡ２を用いた分散計算により、グループ認証情報Ｇを再構成するための中間計算結果ｓＡ´，ｓＢ´を生成する（ＳＴ１３）。検証端末３０ａが、中間計算結果を受信し（ＳＴ１４）、秘密再構成方法に従ってグループ認証情報Ｇが再構成できるか否かを検証する（ＳＴ１５）再構成できたという結果である場合に、被検証端末Ａ，Ｂがそれぞれ主張する公開鍵を互いに信用する。【選択図】        図６  
2005328123.tif 000002
【特許請求の範囲】
【請求項１】
秘密分散法を用いてグループ認証情報からｎ個の第１の分散情報を生成し、上記ｎ個の第１の分散情報をｎ台（２≦ｎ）の端末のそれぞれに配布している場合に、上記ｎ台の端末のうちのｔ（２≦ｔ≦ｎ）台の端末が集まって、上記グループ認証情報を再構成する秘密再構成方法を用いて、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用することができるものであるか否かを判断する公開鍵の正当性判断方法であって、
上記共に信頼できる端末が検証端末となり、上記検証端末が、上記ｔ台の端末との秘密通信路及び送信元端末の特定を実現する工程と、
上記ｔ台の端末が互いに、公開鍵暗号方式を利用して情報をやり取りしたい相手端末との秘密通信路及び送信元端末の特定を実現する工程と、
上記ｔ台の端末のそれぞれが、秘密分散法を用いて、自分自身が保持する第１の分散情報からｔ個の第２の分散情報を生成し、上記ｔ台の端末のそれぞれに配布する工程と、
上記ｔ台の端末のそれぞれが、自分自身が生成した第２の分散情報及び他の端末から自分自身が受け取った（ｔ−１）個の第２の分散情報を用いた分散計算により、上記もとの秘密情報を再構成するための中間計算結果を生成する工程と、
上記検証端末が、上記ｔ個の中間計算結果を受信し、上記ｔ台の端末による秘密の再構成方法に従って上記グループ認証情報が再構成できるか否かを検証する工程と、
上記検証端末が、上記検証の結果を上記ｔ台の端末に通知する工程と、
上記検証の結果が上記グループ認証情報が再構成できたという結果である場合に、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用する工程と
を有し、
上記ｔ台の端末の中のある端末が生成した上記中間計算結果は、上記ある端末自身が生成した第２の分散情報及び上記ある端末自身が受け取った（ｔ−１）個の第２の分散情報を、上記ある端末の端末ＩＤ情報に基づく係数を用いて線形結合計算することによって得る
ことを特徴とする公開鍵の正当性判断方法。
【請求項２】
上記ｔ台の端末のそれぞれが、共に信頼できる端末に上記グループ認証情報の再構成を依頼する工程をさらに有することを特徴とする請求項１に記載の公開鍵の正当性判断方法。
【請求項３】
秘密分散法を用いてグループ認証情報からｎ個の第１の分散情報を生成し、上記ｎ個の第１の分散情報をｎ台（２≦ｎ）の端末のそれぞれに配布している場合に、上記ｎ台の端末のうちのｔ（２≦ｔ≦ｎ）台の端末が集まって、上記グループ認証情報を再構成する秘密再構成方法を用いて、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用することができるものであるか否かを判断する公開鍵の正当性判断方法において、分散計算を行うｔ台の端末の内の１台の端末である検証される側の通信端末装置であって、
上記１台の端末が保有する第１の分散情報を秘密分散法を用いて分散し、第２の分散情報として前記ｔ台の端末の中の他の端末に配布する秘密分散手段と、
上記秘密分散手段からの出力と、上記他の端末から受け取った第２の分散情報を用いて、上記グループ認証情報を再構成するための中間計算結果を、分散計算により算出する分散秘密再構成計算手段と、
上記分散秘密再構成計算手段の出力である上記中間計算結果を検証する側の端末に送信する送信手段と、
自身のＩＤ情報、公開鍵、グループ認証情報、及びグループ認証情報の再構成方法を管理する自端末情報管理手段と、
端末の公開鍵情報を管理する手段と、
上記グループ認証情報の再構成を依頼する検証依頼情報生成手段と、
自身の情報が検証する側の端末に届けられるまでに改ざんされていないかを検出する改ざん検出手段と、
検証する側の端末との秘密通信路及び送信元端末の特定を実現する手段と、
公開鍵暗号方式を利用して他の検証される側の端末との秘密通信路及び送信元端末の特定を実現する手段と
を有することを特徴とする通信端末装置。
【請求項４】
上記端末の公開鍵情報を管理する手段は、端末のＩＤ情報、公開鍵、公開鍵の正当性、及び端末の信頼情報を判別及び変更できることを特徴とする請求項３に記載の通信端末装置。
【請求項５】
自身の公開鍵と秘密鍵のペアを更新する手段と、
公開鍵に有効期限情報を持たせる手段と
を有することを特徴とする請求項３又は４のいずれかに記載の通信端末装置。
【請求項６】
秘密分散法を用いてグループ認証情報からｎ個の第１の分散情報を生成し、上記ｎ個の第１の分散情報をｎ台（２≦ｎ）の端末のそれぞれに配布している場合に、上記ｎ台の端末のうちのｔ（２≦ｔ≦ｎ）台の端末が集まって、上記グループ認証情報を再構成する秘密再構成方法を用いて、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用することができるものであるか否かを判断する公開鍵の正当性判断方法において、分散計算を行うｔ台の検証される側の端末が信頼する端末である検証する側の通信端末装置であって、
自身がグループ認証情報が再構成されるかどうかを検証する端末となることを決定する手段と、
上記検証される側の端末との秘密通信路及び送信元端末の特定を実現する手段と、
上記検証される側の端末による秘密の再構成方法に従ってグループ認証情報が再構成されるかどうかを検証する手段と、
上記検証結果を上記検証される側の端末に伝達する手段と
を有することを特徴とする通信端末装置。
【請求項７】
上記秘密通信路及び送信元端末の特定を実現する手段は、公開鍵暗号方式による暗号通信とディジタル署名を用いることより秘密通信路及び送信元端末の特定を実現することを特徴とする請求項３又は６のいずれかに記載の通信端末装置。
【請求項８】
上記秘密通信路及び送信元端末の特定を実現する手段は、公開鍵暗号方式と共通鍵暗号方式を組み合わせたハイブリッド暗号化方式による暗号通信と、公開鍵暗号方式によるディジタル署名を用いることより秘密通信路及び送信元端末の特定を実現することを特徴とする請求項３又は６のいずれかに記載の通信端末装置。
【請求項９】
上記秘密通信路及び送信元端末の特定を実現する手段は、公開鍵暗号方式に基づく鍵共有方法を用いて相手端末と対称鍵を共有することにより秘密通信路及び送信元端末の特定を実現することを特徴とする請求項３又は６のいずれかに記載の通信端末装置。
【請求項１０】
上記請求項２、３、４、５、７、８、９のいずれかに記載の検証される側の端末の構成と、
上記請求項６、７、８、９のいずれかに記載の検証する側の端末の構成と
を有することを特徴とする通信端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の同じグループに属する複数の通信端末装置（「端末」、「メンバ」、又は「メンバ端末」とも言う。）が、共通に信頼できる端末を利用して、互いの主張する公開鍵を信用し合うことができるか否かを判断する公開鍵の正当性判断方法に関するものである。ここで、「同じグループに属する端末」とは、そのグループの管理者によって事前に配布されたなんらかの情報を有する端末である。また、「信頼できる端末」とは、その端末の正しい公開鍵が既知であり、その端末は不正行為をしないと想定できる端末である。なお、本発明は、例えば、膨大な数の端末から構成されるアドホックネットワークにおいて、複数の端末が、互いの主張する公開鍵を信用し合うことができるか否かを判断する際に用いることができる。
【背景技術】
【０００２】
図１は、端末００１，００２，…，００７からなるアドホックネットワークを表す図である。図１に示されるように、端末００２，００３，…，００６は、信頼グループＲＧ１を形成している。信頼グループＲＧ１内のそれぞれの端末００２，００３，…，００６は、信頼グループＲＧ１内の他の端末の正当な公開鍵を保持しており、正当でない公開鍵は保持していない。なお、図及び以下の説明においては、００１，００２，…，００７は、各端末に固有のＩＤ情報を示す。
【０００３】
ここで、図１に示されるように、信頼グループＲＧ１を形成している端末００２，００３，…，００６と同じグループに属するが、信頼グループＲＧ１を形成していない端末００１が存在する場合を考える。端末００１は信頼グループＲＧ１に加入したいと考えている。端末００１が信頼グループＲＧ１に加入するためには、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６が互いの公開鍵を信用しなければならない。ただし、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６とは、互いを正確に特定できるような情報を有していない。
【０００４】
端末とその端末の正しい公開鍵の組を知ることは、なりすまし攻撃を防ぐための重要な課題である。公開鍵の正当性判断には次の２つの方法が考えられる。
【０００５】
第１の方法は、信頼できる第三者機関（ＴＴＰ：Ｔｒｕｓｔｅｄ  Ｔｈｉｒｄ  Ｐａｒｔｙ）を利用する方法であり、端末はＴＴＰによって署名されたデータを信頼する方法である。すなわち、今日のいわゆる公開鍵基盤（ＰＫＩ：Ｐｕｂｌｉｃ  Ｋｅｙ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）における証明書がこれに当てはまる。端末は、自身を特定する情報と自身の公開鍵の組に対して、ＴＴＰから署名をもらい、保持しておく。端末は、ＴＴＰの署名が付いている端末の公開鍵を信用する。図１において、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６とが、自身の公開鍵に対してＴＴＰにより署名してもらうことで、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６とが互いの公開鍵を信用することができる（例えば、非特許文献１参照）。
【０００６】
第２の方法は、ＴＴＰを利用しない方法であり、信用の輪（ｗｅｂ  ｏｆ  ｔｒｕｓｔ）を利用する方法である。すなわち、フィル・ジマーマン（Ｐｈｉｌ  Ｚｉｍｍｅｒｍａｎｎ）によって開発されたＰＧＰ（Ｐｒｅｔｔｙ  Ｇｏｏｄ  Ｐｒｉｖａｃｙ：プリティ  グッド  プライバシー）における概念がこれに当てはまる。なお、本発明はＴＴＰを必要としない方法である。
【０００７】
信用の輪を利用する方法では、ＴＴＰのような機関は存在せず、信頼できる媒体は端末によって違うことを想定している。端末は、自身が信頼できる端末の署名が付いている公開鍵を信用する。図１において、端末００１と、信頼グループＲＧ１を形成する端末００２，００３，…，００６の内の少なくとも１端末（ここでは、端末００２とする。）とが、共通に信頼できる端末００７が存在し、端末００７は端末００１と端末００２の正しい公開鍵を知っているとする。この場合、端末００１と端末００２のそれぞれの公開鍵に端末００７の署名があることにより、端末００１と端末００２が互いの公開鍵を信用することができる。そして、このように端末００１と端末００２が互いの公開鍵を信用できると、端末００１と、端末００２が既に正しい公開鍵を知っている信頼グループＲＧ１を形成する端末００３，００４，…，００６との間で、互いの公開鍵を信用する機会を作ることができる（例えば、非特許文献１参照）。
【０００８】
【非特許文献１】結城浩著、「暗号技術入門−秘密の国のアリス」、ｐｐ．２３８−２４１（証明書）、ｐｐ．３３７−３４２（公開鍵の正当性）（ソフトバンク  パブリッシング株式会社）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、信用の輪を用いた公開鍵の正当性判断の場合には、例えば、図１において端末００７は、端末００１と端末００２の正しい公開鍵を知っており、端末００１と端末００２の公開鍵に自身の署名を付加する必要がある。このため、端末００１と端末００２が共通に信頼できる端末００７が存在したとしても、端末００７が端末００１と端末００２の公開鍵を信用していない場合には、端末００７の署名が付加されず、端末００１と端末００２が互いの公開鍵を信用することができないという問題があった。
【００１０】
また、本出願人による先行出願（特願２００３−０６７８３４号）には、秘密分散法とマルチパーティプロトコルを用いた秘密再構成方法が説明されている。この方法によると、もとの秘密を再構成するために集まったメンバ端末の持つ分散情報を、他のメンバ端末に公開せずに、もとの秘密を再構成することができる。同じグループではない端末、すなわち、あらかじめもとの秘密の分散情報を持たない端末が、再構成に参加しようとしても、もとの秘密の再構成に失敗することから、集まった複数の端末のすべてが正当メンバであるか、又は、正当メンバではない端末が混在するかということを認証する機能がある。
【００１１】
ただし、上記先行出願に記載の秘密再構成方法においては、認証に参加する複数の端末間には、どの２つの端末間にも、その２つの端末以外には通信内容を秘密とすることができる秘密通信路が存在するという前提条件が必要である。
【００１２】
本発明の目的は、複数の被検証端末が共通に信頼できる端末が存在する場合に、この端末を利用して、複数の被検証端末のそれぞれが主張する公開鍵を、複数の被検証端末のそれぞれが互いに信用し合うことができるか否かを判断する公開鍵の正当性判断方法及びこの方法を実施するための通信端末装置を提供することにある。
【課題を解決するための手段】
【００１３】
本発明の公開鍵の正当性判断方法は、秘密分散法を用いてグループ認証情報からｎ個の第１の分散情報を生成し、上記ｎ個の第１の分散情報をｎ台（２≦ｎ）の端末のそれぞれに配布している場合に、上記ｎ台の端末のうちのｔ（２≦ｔ≦ｎ）台の端末が集まって、上記グループ認証情報を再構成する秘密再構成方法を用いて、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用することができるものであるか否かを判断する方法であって、上記共に信頼できる端末が検証端末となり、上記検証端末が、上記ｔ台の端末との秘密通信路及び送信元端末の特定を実現する工程と、上記ｔ台の端末が互いに、公開鍵暗号方式を利用して情報をやり取りしたい相手端末との秘密通信路及び送信元端末の特定を実現する工程と、上記ｔ台の端末のそれぞれが、秘密分散法を用いて、自分自身が保持する第１の分散情報からｔ個の第２の分散情報を生成し、上記ｔ台の端末のそれぞれに配布する工程と、上記ｔ台の端末のそれぞれが、自分自身が生成した第２の分散情報及び他の端末から自分自身が受け取った（ｔ−１）個の第２の分散情報を用いた分散計算により、上記もとの秘密情報を再構成するための中間計算結果を生成する工程と、上記検証端末が、上記ｔ個の中間計算結果を受信し、上記ｔ台の端末による秘密の再構成方法に従って上記グループ認証情報が再構成できるか否かを検証する工程と、上記検証端末が、上記検証の結果を上記ｔ台の端末に通知する工程と、上記検証の結果が上記グループ認証情報が再構成できたという結果である場合に、上記ｔ台の端末がそれぞれ主張する公開鍵を互いに信用する工程とを有し、上記ｔ台の端末の中のある端末が生成した上記中間計算結果は、上記ある端末自身が生成した第２の分散情報及び上記ある端末自身が受け取った（ｔ−１）個の第２の分散情報を、上記ある端末の端末ＩＤ情報に基づく係数を用いて線形結合計算することによって得ることを特徴とするものである。
【発明の効果】
【００１４】
本発明によれば、複数の被検証端末が共通に信頼できる端末が存在する場合に、この共通に信頼できる端末が複数の被検証端末を信頼していない場合であっても、この共通に信頼できる端末を利用して、複数の被検証端末のそれぞれが主張する公開鍵を、複数の被検証端末のそれぞれが互いに信用し合うことができるか否かを判断することができるという効果を得ることができる。
【発明を実施するための最良の形態】
【００１５】
［１．本発明において利用される分散秘密再構成方法の説明］
［１−１．分散秘密再構成方法の概要］
本発明において利用される分散秘密再構成方法は、本出願人による上記先行出願に（先行の第２の実施形態として）記載されている。この分散秘密再構成方法においては、もとの秘密情報Ｓを再構成する際に、もとの秘密情報Ｓを再構成するために集まったメンバ（端末）が保有する分散情報を用いてマルチパーティプロトコルを実行することにより、各メンバが保有する分散情報を公開せずに、もとの秘密情報Ｓの再構成を行う。したがって、同じグループではない端末、すなわち、あらかじめもとの秘密情報の分散情報を持たない端末が、再構成に参加しようとしても、もとの秘密情報の再構成に失敗することから、集まった複数のメンバのすべてが正当メンバであるか、又は、正当メンバではない端末が混在するかということを認証する機能がある。なお、この秘密再構成方法は、秘密再構成システムにより実施される。また、秘密再構成システムは、各メンバ（端末）である分散秘密再構成装置（後述する分散秘密再構成計算部６０１）と、メンバのいずれかに又はメンバとは別のセンターに備えられた演算装置（後述する秘密再構成計算部６０２）とを主要な構成としている。
【００１６】
［１−２．マルチパーティプロトコルの説明］
マルチパーティプロトコルとは、ある関数への入力値を公開せずに、その関数の計算を集まったメンバで協力して行う方式であり、「分散計算」とも呼ばれる。ここでは、有限体要素の計算（加算と乗算の計算）を用いるマルチパーティプロトコルについて説明する。マルチパーティプロトコルを実行するメンバがｎ人いる場合を想定する。メンバのそれぞれが、メンバＩＤとしてｍｊ（ｊ＝１，２，…，ｎ）と、そのメンバ固有の秘密情報Ｘｍｊ（ｊ＝１，２，…，ｎ）を所有しており、次式（１）に示される関数値Ｙをマルチパーティプロトコルで計算する場合を考える。
Ｙ＝ｆ（Ｘｍ１，Ｘｍ２，…，Ｘｍｎ）                      （１）
ここで、各メンバのメンバＩＤであるｍｊ及び秘密情報Ｘｍｊ（ｊ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）（ｑは素数又は素数のべき乗）上の値であるものとする。また、上記式（１）の関数ｆにおける演算は、有限体ＧＦ（ｑ）上の演算であるものとし、したがって、得られる関数値Ｙも、有限体ＧＦ（ｑ）上の値となる。
【００１７】
各メンバ固有の秘密情報Ｘｍｊ（ｊ＝１，２，…，ｎ）を、他のメンバに公開しないまま、関数値Ｙを計算するために、マルチパーティプロトコルでは、まず、各メンバ固有の秘密情報Ｘｍｊ（ｊ＝１，２，…，ｎ）を、（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散し、各メンバに配布する。メンバＩＤがｍｊであるメンバの秘密情報がＸｍｊであるとすると、このメンバは、次式（２）のｋ−１（ｋ≦ｎ）次多項式ｆｍｊ（ｘ）を作る。
【数１】
2005328123.tif 000003
ここで、Ｒｍｊ,１，Ｒｍｊ,２，…，Ｒｍｊ,ｋ−１は、有限体ＧＦ（ｑ）上の値から選ばれたｋ−１個の乱数である。
【００１８】
秘密情報Ｘｍｊを秘密分散法により分散し、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに対して配布される分散情報をＸｍｊ,ｐと表記する場合に、分散情報Ｘｍｊ,ｐは、上記式（２）を用いて、次式（３）のよう計算できる。
【数２】
2005328123.tif 000004
なお、分散情報Ｘｍｊ,ｐは、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバ以外には秘密となるよう、秘密通信路を用いて、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する。
【００１９】
上記式（２）及び（３）における足し算及び掛け算は、有限体ＧＦ（ｑ）上における加算及び乗算であるものとする。したがって、得られる分散情報Ｘｍｊ,ｐ（ｊ＝１，２，…，ｎ；ｐ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）上の値である。なお、以下の説明においては、断りがない限り、演算は有限体ＧＦ（ｑ）上で行われるものとする。
【００２０】
以上の処理によって、各メンバは、他の各メンバの秘密情報Ｘｍｊの分散情報Ｘｍｊ,ｐを持っている状態になる。メンバＩＤがｍｊであるメンバは、他のメンバから配布された分散情報（及び自分自身の秘密情報の分散情報）Ｘｍ１，ｊ，Ｘｍ２，ｊ，…，Ｘｍｎ，ｊのｎ個の分散情報を持っていることになる。
【００２１】
ここで、マルチパーティプロトコルにおける分散加算（足し算計算）を行う。上記式（１）の関数が、例えば、次式（４）に示されるような、ある２つの入力ＸｍＡ及びＸｍＢの足し算となっている場合、
Ｙ＝ｆ（Ｘｍ１，Ｘｍ２，…，Ｘｍｎ）＝ＸｍＡ＋ＸｍＢ      （４）
マルチパーティプロトコルでは、各メンバは、入力ＸｍＡ及びＸｍＢの分散情報同士の足し算を行うことで、計算結果Ｙの分散情報Ｙｍｊ（ｊ＝１，２，…，ｎ）を得ることができる。例えば、メンバＩＤがｍｊであるメンバは、入力ＸｍＡ及びＸｍＢの分散情報として、それぞれＸｍＡ,ｊ及びＸｍＢ,ｊを持っているので、次式（５）のような計算を行い、計算結果Ｙの分散情報Ｙｍｊを得る。
Ｙｍｊ＝ＸｍＡ,ｊ＋ＸｍＢ,ｊ                            （５）
【００２２】
次に、マルチパーティプロトコルにおける分散乗算（掛け算計算）を説明する。上記式（１）の関数が、例えば、次式（６）のような、ある２つの入力ＸｍＡ及びＸｍＢの掛け算となっている場合、
Ｙ＝ｆ（Ｘｍ１，Ｘｍ２，…，Ｘｍｎ）＝ＸｍＡ×ＸｍＢ      （６）
マルチパーティプロトコルでは、各メンバは、次のようなステップＳＴ１０１〜ＳＴ１０３の処理を行う。ステップＳＴ１０１においては、入力ＸｍＡ及びＸｍＢの分散情報同士の掛け算を行い、ステップＳＴ１０２においては、その掛け算結果をさらに、他のメンバに秘密分散して配布し、ステップＳＴ１０３においては、受け取った側でそれらの再構成を行うことで、計算結果Ｙの分散情報Ｙｍｊ（ｊ＝１，２，…，ｎ）を得ることができる。ただし、マルチパーティプロトコルの分散乗算では、秘密分散のしきい値ｋは、次式（７）となっている必要がある。
ｋ≦（ｎ＋１）／２                                        （７）
ここで、上記式（７）の演算は、有限体ＧＦ（ｑ）上の演算ではなく、通常の実数、整数演算である。
【００２３】
具体的に説明すると、例えば、メンバＩＤがｍｊであるメンバは、入力ＸｍＡ及びＸｍＢの分散情報として、それぞれＸｍＡ,ｊ及びＸｍＢ,ｊを持っているので、まず、次式（８）のような計算を行い、途中計算結果Ｙ’ｍｊを得る（上記ステップＳＴ１０１）。
Ｙ’ｍｊ＝ＸｍＡ,ｊ×ＸｍＢ,ｊ                          （８）
【００２４】
次に、この途中計算結果Ｙ’ｍｊを次式（９）のような多項式で秘密分散を行う（上記ステップＳＴ１０２）。
【数３】
2005328123.tif 000005
ここで、Ｒ’ｍｊ,１，Ｒ’ｍｊ,２，…，Ｒ’ｍｊ,ｋ−１は、乱数として有限体ＧＦ（ｑ）上の値をｋ−１個選ぶことによって得られる。
【００２５】
次に、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに対して配布する自分の途中計算結果Ｙ’ｍｊの分散情報Ｙ’ｍｊ,ｐを、上記式（９）を用いて、次式（１０）のように計算する。
【数４】
2005328123.tif 000006
なお、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバ以外には秘密となるよう、秘密通信路を用いてメンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する。上記式（１０）のような計算で分散した結果、メンバＩＤがｍｊであるメンバは、Ｙ’ｍ１，ｊ，Ｙ’ｍ２，ｊ，…，Ｙ’ｍｎ，ｊのｎ個の分散情報を受け取る。
【００２６】
メンバＩＤがｍｊであるメンバは、これら分散情報Ｙ’ｍ１，ｊ，Ｙ’ｍ２，ｊ，…，Ｙ’ｍｎ，ｊから、掛け算結果の分散情報Ｙｍｊを次式（１１）及び（１２）のように計算する。
【数５】
2005328123.tif 000007
この計算は、秘密情報の再構成時の計算と同様のものである（上記ステップＳＴ１０３）。
【００２７】
上記のように、マルチパーティプロトコルを用いれば、各メンバ同士が秘密通信を行って計算処理をすることにより、入力値を公開せずに、与えられた関数の計算を行うことができる。
【００２８】
［１−３．分散秘密再構成方法を実施する構成］
以下の説明においては、複数のメンバ（演算記憶装置）からなるあるグループで、もとの秘密情報Ｓを、（ｋ，ｎ）しきい値秘密分散法を用いて分散し、各メンバに分散情報が秘密裏に配布されている状態を前提とする。この場合には、必ずしもメンバ全員（すなわち、ｎ人のメンバ）が集まらなくとも、ｋ人（ｋ≦ｎ）のメンバが集まれば、もとの秘密情報Ｓを再構成することができる。
【００２９】
このグループにはｎ人のメンバがいるものとし、各メンバに秘密情報Ｓを分散させるときに用いたメンバＩＤをｍ１，ｍ２，…，ｍｎとする。メンバＩＤがｍｊ（ｊ＝１，２，…，ｎ）であるメンバに配布した、秘密情報Ｓの分散情報をＸｍｊ（ｊ＝１，２，…，ｎ）とする。もとの秘密情報Ｓを再構成させたいときに、集まったメンバがｔ人（ｔ≧ｋ）で、各メンバの持つ分散情報を持ち寄ったとする。このとき集まったメンバのメンバＩＤをｍ’１，ｍ’２，…，ｍ’ｔとし、集まったメンバが持つ分散情報をＸｍ’１，Ｘｍ’２，…，Ｘｍ’ｔとする。また、集まったメンバのうち、どの２人のメンバ間にも、その２人のメンバ以外には通信内容を秘密とすることができる秘密通信路が確立されているものとする。
【００３０】
図２は、各メンバ間の通信に用いる秘密通信路３０３を示す図である。図２はおいて、四角形で示されるブロックは集まったメンバを示し、ｍ’１，ｍ’２，…，ｍ’ｊ，…，ｍ’ｔは、メンバＩＤを示し、両方向の矢印は、それぞれ対応するメンバ以外には通信内容を秘密とする秘密通信路３０３を示している。さらに、集まったｔ人のメンバに与えられたメンバＩＤ＿ｍ’１，ｍ’２，…，ｍ’ｔは公開された値であるものとする。
【００３１】
図３は、秘密再構成方法を実施する構成（秘密再構成システム）を示すブロック図である。図３を用いて、秘密再構成方法を説明する。図３に示されるように、もとの秘密情報Ｓを再構成しようとする際に集まったメンバＩＤがｍ’１，ｍ’２，…，ｍ’ｔであるｔ人のメンバ（すなわち、ｔ台の演算記憶装置）は、それぞれ、分散計算により秘密情報を再構成する手段である分散秘密再構成計算部（すなわち、分散秘密再構成装置）６０１（６０１−１，６０１−２，…，６０１−ｔ）が備えられている。分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）における処理は、メンバＩＤがｍ’ｊであるメンバが行う。各メンバの分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）は、それぞれ他のメンバの分散秘密再構成計算部６０１とは、図２で示された秘密通信路３０３で接続されている。また、各メンバの分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）からの出力は、秘密再構成計算部６０２へ入力される。
【００３２】
秘密再構成計算部６０２は、各メンバの分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）からの出力を受け取り、それら受け取ったｔ個の値を、ｔ個の分散情報としたときの秘密情報の再構成を行う計算をし、その再構成された秘密情報を出力する。各メンバの分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）から出力される値をＳｍ’ｊ（ｊ＝１，２，…，ｔ）とすると、次式（１３）及び（１４）を用いて計算し、もとの秘密情報Ｓを出力する。
【数６】
2005328123.tif 000008
上記式（１３）における各演算は有限体ＧＦ（ｑ）上で行う。以降の説明においては、断りがない限り、演算は、有限体ＧＦ（ｑ）上で行われるものとする。
【００３３】
各メンバの分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）における処理は、各メンバが、それぞれ他のメンバにはその処理の内容が分からないように行う。秘密再構成計算部６０２における処理は、処理を統合するセンター（メンバとは別の演算装置）のようなものが行ってもよいし、集まったメンバ（演算記憶装置）のうち、だれか１人、又は、複数人で行ってもよい。ただし、秘密情報Ｓを必要としているメンバが行うのが望ましい。
【００３４】
図４は、図３の分散秘密再構成計算部６０１−ｊ（ｊ＝１，２，…，ｔ）の構成を示すブロック図である。図４を用いて分散秘密再構成計算部６０１−ｊを説明する。図４に示されるように、分散秘密再構成計算部６０１−ｊは、秘密分散計算部７０１−ｊと、線形結合計算部７０２−ｊとを有する。秘密分散計算部７０１−ｊからの出力が線形結合計算部７０２−ｊへ入力され、線形結合計算部７０２−ｊからの出力が、分散秘密再構成計算部７０１−ｊの出力となる。
【００３５】
秘密分散計算部７０１−ｊへは、メンバＩＤがｍ’ｊであるメンバが持つもとの秘密情報Ｓの分散情報Ｘｍ’ｊが入力される。秘密分散計算部７０１−ｊは、入力された分散情報Ｘｍ’ｊを（ｋ’，ｔ）しきい値秘密分散法（ｋ’≦ｔ）を用いて分散し、他のメンバと通信する秘密通信路３０３を経由して配布する。分散するときの計算においては、上記式（２）のｍｊがｍ’ｊに置き換わり、ｋがｋ’に置き換わったｋ’−１次多項式である次式（１５）を作る。
【数７】
2005328123.tif 000009
ここで、Ｒｍ’ｊ,１，Ｒｍ’ｊ,２，…，Ｒｍ’ｊ,ｋ’−１は、乱数として選ばれた有限体ＧＦ（ｑ）上のｋ’−１個の値である。
【００３６】
そして、メンバＩＤがｍ’ｐ（ｐ＝１，２，…，ｔ）であるメンバに対して配布する分散情報Ｘｍ’ｊ,ｐを、上記式（１５）を用いて次式（１６）のように計算する（上記式（３）参照）。
【数８】
2005328123.tif 000010
【００３７】
自分自身に対する分散情報Ｘｍ’ｊ,ｊは、線形結合計算部７０２−ｊへ出力し、その他の分散情報Ｘｍ’ｊ,ｐ（ｐ＝１，２，…，ｔであり、ｐ≠ｊであるもの）を秘密通信路３０３を通して各メンバに配布する。
【００３８】
線形結合計算部７０２−ｊは、秘密分散計算部７０１−ｊから、もとの秘密情報Ｓの分散情報Ｘｍ’ｊの分散情報Ｘｍ’ｊ,ｊを受け取る。さらに、秘密通信路３０３を経由して、他のメンバから配布された、もとの秘密情報Ｓの分散情報Ｘｍ’ｊの分散情報Ｘｍ’１，ｊ，…，Ｘｍ’ｊ−１，ｊ，Ｘｍ’ｊ＋１，ｊ，…，Ｘｍ’ｔ，ｊを受け取る。これらｔ個ある、もとの秘密情報Ｓの分散情報Ｘｍ’ｊの分散情報Ｘｍ’ｐ，ｊ（ｐ＝１，２，…，ｔ）、から、もとの秘密情報Ｓの分散情報Ｓｍ’ｊ（秘密情報Ｓの再構成時に得られる秘密情報Ｓの分散情報Ｓｍ’ｊと、秘密情報Ｓの分散時に得られる秘密情報Ｓの分散情報Ｘｍ’ｊとは異なるものである）を計算し出力する。線形結合計算部７０２−ｊは、次式（１７）及び（１８）のような計算を行う。
【数９】
2005328123.tif 000011
ここで、各メンバＩＤ＿ｍ’１，ｍ’２，…，ｍ’ｔは公開された値であるので、上記式（１８）のｒｍ’ｐを計算することができる。
【００３９】
［１−４．分散秘密再構成方法］
図５は、本発明において利用される秘密再構成方法における動作を示すフローチャートである。ここで、もとの秘密情報Ｓを再構成するために集まったｔ人のメンバのメンバＩＤをｍ’１，ｍ’２，…，ｍ’ｔとし、各メンバが持つ分散情報をＸｍ’１，Ｘｍ’２，…，Ｘｍ’ｔとする。この秘密再構成方法においては、図５に示されるように、まず、各メンバが持つ分散情報を（ｋ’，ｔ）しきい値秘密分散法を用いて分散し、他のメンバに配布する（ステップＳＴ２０１）。ステップＳＴ２０１は、図４の秘密分散計算部７０１−ｊにおける動作を示しており、メンバＩＤがｍ’ｊ（ｊ＝１，２，…，ｔ）であるメンバの持つ分散情報Ｘｍ’ｊを上記式（１５）を用いて分散し、メンバＩＤがｍ’ｐ（ｐ＝１，２，…，ｔ）であるメンバに対し、上記式（２４）で計算されるＸｍ’ｊ,ｐを配布する。
【００４０】
次に、各メンバは、公開されている集まったメンバのメンバＩＤ、自分自身の分散情報Ｘｍ’ｊの分散情報及び他のメンバから配布された分散情報、すなわち、分散情報Ｘｍ’ｐ，ｊ（ｐ＝１，２，…，ｔ）を用いて演算を施し、もとの秘密情報Ｓの分散情報Ｓｍ’ｊである値を求める（ステップＳＴ２０２）。ステップＳＴ２０２は、図４の線形結合計算部７０２−ｊにおける動作を示しており、メンバＩＤがｍ’ｊ（ｊ＝１，２，…，ｔ）であるメンバは、他のメンバから配布された分散情報Ｘｍ’ｐ，ｊ（ｐ＝１，２，…，ｔ）（自分自身の分散情報Ｘｍ’ｊの分散情報Ｘｍ’ｊ,ｊが含まれている）、及び公開されているメンバＩＤ＿ｍ’ｐ（ｐ＝１，２，…，ｔ）から、上記式（２５）を用いて計算する。その計算結果Ｓｍ’ｊは、もとの秘密情報Ｓの分散情報となっている。
【００４１】
次に、ステップＳＴ２０２で、各メンバが計算した分散情報からもとの秘密情報Ｓを再構成する（ステップＳＴ２０３）。ステップＳＴ２０３は、図１０の秘密再構成計算部６０２における動作を示しており、メンバＩＤがｍ’ｊ（ｊ＝１，２，…，ｔ）であるメンバがステップＳＴ２０２で計算した結果Ｓｍ’ｊ（ｊ＝１，２，…，ｔ）から、上記式（１３）を用いて計算し、もとの秘密情報Ｓを得ることができる。
【００４２】
この秘密再構成方法によれば、もとの秘密情報Ｓを再構成するために集まったメンバの持つ分散情報を、他のメンバに公開せずに、もとの秘密情報Ｓを再構成することができる。したがって、各メンバが持つ分散情報を、次回の秘密再構成の際に再利用することができる。しかも、秘密再構成を行う第三者的なセンターのようなものを設けなくても、上記の効果を達成することができる。
【００４３】
また、この秘密再構成方法の場合、必ずしもメンバ全員、すなわちｎ人のメンバが集まらなくとも、ｋ人（ｋ≦ｎ）以上のメンバが集まれば、もとの秘密情報Ｓを再構成することができる。
【００４４】
この秘密再構成方法においては、集まったメンバのメンバＩＤを公開するので、集まったメンバを匿名にすることはできないが（少なくとも、もとの秘密情報Ｓを秘密分散させるときのメンバＩＤは分かってしまうが）、秘密再構成の際のメンバ間の相互通信は、最初の分散情報を分散配布するための１回のみで済むため、通信量及び計算量の両方とも少なく、しかも、必ずしもメンバ全員、すなわちｎ人が集まらなくとも、ｋ人（ｋ≦ｎ）が集まれば、もとの秘密情報Ｓを再構成することができる。
【００４５】
さらに、この秘密再構成方法においては、予め秘密情報Ｓの分散情報を持たない人（演算記憶装置）が、この再構成に参加しようとしても、秘密情報Ｓの再構成に失敗することから、集まった複数人数からなるグループ全員が正当メンバ（予め秘密情報Ｓの分散情報を配布されたメンバ）か、そうでない人（演算記憶装置）が混在するか、ということを認証するような機能が備わる。さらにまた、上記形態においては、前述のように分散情報を再利用可能なので、この認証機能は、秘密情報Ｓの分散情報を更新せずとも何度も利用できる。また、この認証機能は、集まったメンバから他へ送信される情報は、認証（秘密情報Ｓの再構成）のたびに異なるので、盗聴による“なりすまし”に非常に強い。このような認証機能は、秘密分散法の秘密再構成の性質と、マルチパーティプロトコルによる分散計算の性質との単なる組み合わせによって得られる機能ではなく、新しい機能である。なお、上記認証機能は、「もとの秘密情報Ｓ」を照合秘密情報Ｓ（予め登録されている情報で、認証が成立するか否かを、再構成結果と照らし合わせる情報）として用いる利用形態であるので、もとの秘密情報Ｓを各メンバに秘密にしない場合であっても、実現できる。
【００４６】
［２．本発明の実施形態の説明］
［２−１．公開鍵の正当性判断方法の概要］
本実施形態の公開鍵の正当性判断方法においては、上記（ｋ，ｎ）閾値秘密分散法（集まった各メンバは自分の保持する秘密情報を加算分散法で秘密分散する）を用いて、端末が主張する公開鍵に基づいて秘密通信路を構築する。本実施形態の公開鍵の正当性判断方法においては、図１において、端末００１と端末００２が共通に信頼できる端末００７が、端末００１と端末００２が同じグループに属するかどうかを確かめ、その結果を端末００１と端末００２に教えることにより、端末００１と端末００２が互いの公開鍵を信用できるようになる。
【００４７】
本実施形態の公開鍵の正当性判断方法においては、秘密分散法を用いてグループ認証情報からｎ個の第１の分散情報を生成し、ｎ個の第１の分散情報をｎ台（２≦ｎ）の端末のそれぞれに配布している場合に、ｎ台の端末のうちのｔ（２≦ｔ≦ｎ）台の端末が集まって、グループ認証情報を再構成する秘密再構成方法を用いて、ｔ台の端末がそれぞれ主張する公開鍵を互いに信用することができるものであるか否かを判断する。以下に、ｔ＝２の場合を説明する。
【００４８】
図６に示されるように、本実施形態の公開鍵の正当性判断方法は、被検証端末Ａ（１０ａ）及び被検証端末Ｂ（１０ｂ）のそれぞれが、共に信頼できる端末にグループ認証情報Ｇの再構成を依頼する工程と、共に信頼できる端末が検証端末３０ａとなり、検証端末３０ａが、公開鍵暗号方式を利用して２台の端末との秘密通信路及び送信元端末の特定を実現する工程と、被検証端末Ａ及び被検証端末Ｂが互いに、公開鍵暗号方式を利用して情報をやり取りしたい相手端末との秘密通信路及び送信元端末の特定を実現する工程とを有する。さらに、図６に示されるように、本実施形態の公開鍵の正当性判断方法は、被検証端末Ａ及び被検証端末Ｂのそれぞれが、秘密分散法を用いて、自分自身が保持する分散情報ｓＡ（第１の分散情報）及び分散情報ｓＢ（第１の分散情報）から分散情報ｓＡ１，ｓＡ２（第２の分散情報）及び分散情報ｓＢ１，ｓＢ２（第２の分散情報）を生成し（ステップＳＴ１１）、分散情報ｓＡ２及び分散情報ｓＢ１を相手被検証端末に配布する（ステップＳＴ１２）工程と、被検証端末Ａ及び被検証端末Ｂのそれぞれが、自分自身が生成した分散情報ｓＡ１，ｓＢ２及び他の被検証端末から自分自身が受け取った分散情報ｓＢ１，ｓＡ２を用いた分散計算により、グループ認証情報Ｇ（もとの秘密情報）を再構成するための中間計算結果ｓＡ´，ｓＢ´を生成する（ステップＳＴ１３）工程と、検証端末３０ａが、中間計算結果ｓＡ´，ｓＢ´を受信し（ステップＳＴ１４）、被検証端末による秘密の再構成方法に従ってグループ認証情報Ｇが再構成できるか否かを検証する工程（ステップＳＴ１５）と、検証端末３０ａが、検証の結果を被検証端末Ａ及び被検証端末Ｂに通知する工程と、検証の結果がグループ認証情報Ｇが再構成できたという結果である場合に、被検証端末Ａ及び被検証端末Ｂがそれぞれ主張する公開鍵を互いに信用する工程とを有する。
【００４９】
また、図６及び図７に示されるように、中間計算結果ｓＡ´，ｓＢ´は、被検証端末Ａ及び被検証端末Ｂ自身が生成した分散情報ｓＡ１，ｓＢ２、並びに、被検証端末Ａ及び被検証端末Ｂ自身が受け取った分散情報ｓＢ１，ｓＡ２を、被検証端末Ａ及び被検証端末Ｂの端末ＩＤ情報に基づく係数ｍＡ及び係数ｍＢを用いて線形結合計算することによって得る。
【００５０】
［２−２．公開鍵の正当性判断方法を実施するための構成］
本実施形態の公開鍵の正当性判断方法を実施するための構成には、検証される側の端末（図８の符号１０）と、検証する側の端末（図９の符号３０）とが含まれる。検証される側の端末（図８の符号１０）は、図１及び図１３〜１５における端末００１，００２、及び、図３における分散秘密再構成計算部６０１に対応する。また、検証する側の端末（図９の符号３０）は、図１及び図１３〜１５における端末００７、及び、図３における秘密再構成計算部６０２に対応する。
【００５１】
本実施形態の公開鍵の正当性判断方法は、（ｋ，ｎ）閾値秘密分散法を利用する。本実施形態の公開鍵の正当性判断方法においては、（ｋ，ｎ）閾値秘密分散法を用いておおもとの秘密Ｓ（以下「グループ認証情報」と呼ぶ。）を再構成できる端末数の閾値を２に設定する。すなわち、グループ認証情報を分散するのに用いる秘密曲線は１次曲線であり、端末ＩＤ情報とその端末の分散秘密情報（「端末の分散秘密情報」は、グループ認証情報の分散情報であって各端末が保持しているものであり、「第１の分散情報」とも言う。）は１対１の対応関係となる。本実施形態の公開鍵の正当性判断方法においては、端末ＩＤ情報とグループ認証情報を公開する。また、前提となっている秘密通信路は、端末が主張する公開鍵に基づいて構築する。
【００５２】
［２−２−１．検証される側の端末］
図８は、本実施形態の公開鍵の正当性判断方法が適用される検証される側の端末（被検証端末）の構成を示すブロック図である。図８に示されるように、検証される側の端末１０は、自端末情報管理部１１と、正当公開鍵情報管理部１２と、検証依頼情報生成部１３と、署名検証部１４と、改ざん検出部１５と、公開鍵情報管理部１６と、検証端末情報管理部１７と、秘密情報管理部１８と、受信部１９と、送信部２０とを有する。また、秘密情報管理部１８は、分散秘密情報管理部２１と、乱数生成部２２と、暗号化部２３と、秘密鍵情報管理部２４と、署名生成部２５と、復号部２６と、分散計算部２７とを有する。
【００５３】
＜自端末情報管理部１１＞
自端末情報管理部１１は、自端末のＩＤ情報、自端末の公開鍵情報、グループ認証情報、及びグループ認証情報の検証方法に関する情報を管理している。自端末情報管理部１１は、管理している全情報を検証依頼情報生成部１３及び改ざん検出部１５に与える。また、自端末情報管理部１１は、自端末のＩＤ情報を分散計算部２７に与える。ここで、「自端末のＩＤ情報」とは、グループ認証情報を分散するのに用いる端末固有の値である。自端末のＩＤ情報としては、例えば、端末固有の製造番号やＩＰアドレスが用いられる。また、「グループ認証情報」とは、予めグループ管理者によって決定される情報である。本実施形態におけるグループ認証情報は、２つのグループメンバ端末が集まることによって再構成される情報である。また、「グループ認証情報の検証方法に関する情報」とは、グループ認証情報の検証方法を知らない端末が、グループメンバ端末より受け取った情報をどのように処理し、どのように検証するかを表す情報である。グループ認証情報の検証方法に関する情報は、例えば、受信した情報を加算してグループ認証情報と一致するかどうかを確かめるというような検証方法を実行させる情報である。
【００５４】
＜正当公開鍵情報管理部１２＞
正当公開鍵情報管理部１２は、自端末以外の端末のＩＤ情報、その端末の正しい公開鍵、及びその端末の信頼情報を保持する。ここで、「端末の信頼情報」とは、その端末がどれだけ信頼できるかを示す情報である。正当公開鍵情報管理部１２は、信頼が高い端末のＩＤ情報及びその端末の公開鍵を検証依頼情報生成部１３へ与える。正当公開鍵情報管理部１２は、署名検証部１４よりＩＤ情報を与えられ、そのＩＤ情報に対応する公開鍵を署名検証部１４へ与える。正当公開鍵情報管理部１２は、改ざん検出部１５よりＩＤ情報を与えられ、そのＩＤ情報及びそれに対応する公開鍵を検証端末情報管理部１７へ与える。正当公開鍵情報管理部１２は、公開鍵情報管理部１６より端末のＩＤ情報と公開鍵を与えられ、与えられたＩＤ情報と公開鍵の情報を保持する。ここで、信頼情報をどのように設定するかは任意であるが、できるだけ信頼を低く設定することを奨励する。
【００５５】
＜検証依頼情報生成部１３＞
検証依頼情報生成部１３は、自端末情報管理部１１から受けた自端末に関する情報と、正当公開鍵情報管理部１２より受けた端末のＩＤ情報と公開鍵より、検証依頼情報を生成し、生成した情報を送信部２０へ与える。検証依頼情報は、自端末のＩＤ情報、自端末の公開鍵、グループ認証情報、グループ認証情報の検証方法に関する情報、信頼が高い端末のＩＤ情報、及びこの信頼が高い端末の公開鍵から構成される。
【００５６】
＜署名検証部１４＞
署名検証部１４は、受信部１９より与えられる情報が、送信元端末だと想定される端末が生成したものかどうかを検証する。検証方式としては、例えば、与えられた情報から署名を取り除いた情報をハッシュ関数に通した出力と、送信元端末だと想定される端末の公開鍵で署名を復号した情報とが一致するかどうかによって検証するというような、一般的なディジタル署名方式を用いることができる。署名検証部１４は、１つ又は複数のディジタル署名生成アルゴリズムを有する。ここで用いるディジタル署名方式は、特に限定されず、署名生成者の用いた方式と同じであればよい。
【００５７】
署名検証部１４は、検証端末情報、暗号化分散情報、及び検証結果情報を受信部１９より与えられる。ここで、「検証端末情報」とは、複数の検証をされる側の端末（すなわち、検証を受ける端末）に関する情報（ＩＤ情報、公開鍵、グループ認証情報、及びグループ認証情報の検証方法に関する情報）と、検証をする側の端末の情報（ＩＤ情報及び公開鍵）とから構成される。また、「暗号化分散情報」とは、検証を受ける相手端末（公開鍵が信用できるかどうかを知りたい端末）から与えられ、検証を受ける相手端末の分散秘密情報を分散したものを暗号化した情報である。また、「検証結果情報」とは、複数の検証を受けた端末のＩＤ情報とその端末の公開鍵、及び、検証が成功したか又は失敗したかの情報から構成される。また、「検証が成功したか又は失敗したかの情報」は、グループ認証情報の検証方法に関する情報に指定されており、例えば、フラグによって表される。
【００５８】
署名検証部１４は、受信部１９より検証端末情報を与えられる。署名検証部１４は、検証端末情報の中に含まれる検証をする側の端末のＩＤ情報を正当公開鍵情報管理部１２へ与え、そのＩＤ情報に対応する公開鍵を受け取る。署名検証部１４は、与えられた公開鍵で署名を検証し、署名が確かめられた場合は、検証端末情報を改ざん検出部１５へ与える。
【００５９】
署名検証部１４は、受信部１９より暗号分散化情報を与えられて、公開鍵情報管理部１６へなんらかの信号を与え、公開鍵を受け取る。署名検証部１４は、与えられた公開鍵で署名を検証し、署名が確かめられた場合には、暗号化分散情報を復号部２６へ与え、検証端末情報管理部１７へなんらかの信号を与える。署名検証部１４は、受信部１９より検証結果情報を与えられて、検証端末情報管理部１７へなんらかの信号を与え、公開鍵を受け取る。署名検証部１４は、与えられた公開鍵で署名を検証し、署名が確かめられた場合には、検証結果情報を公開鍵情報管理部１６へ与える。署名検証部１４は、署名の検証がうまくいかなかったことを受けて、その情報を破棄する。
【００６０】
＜改ざん検出部１５＞
改ざん検出部１５は、署名検証部１４より与えられた検証端末情報の中で、自端末に関する情報（ＩＤ情報、公開鍵、グループ認証情報、及びグループ認証情報の検証方法に関する情報）が、自端末情報管理部１１より与えられた情報と一致するかどうかを確かめる。改ざん検出部１５は、自端末に関する情報が自端末情報管理部１１より与えられた情報と一致しているときに、検証する端末のＩＤ情報を正当公開鍵情報管理部１２へ与え、自端末以外の検証を受ける端末のＩＤ情報と公開鍵を公開鍵情報管理部１６へ与え、なんらかの信号を分散秘密情報管理部２１へ与える。
【００６１】
＜公開鍵情報管理部１６＞
公開鍵情報管理部１６は、公開鍵を信用したい相手端末のＩＤ情報と公開鍵を一時的に保持する。公開鍵情報管理部１６は、改ざん検出部１５より、端末のＩＤ情報と公開鍵を与えられることで、その情報を保持し、そのＩＤ情報を分散計算部２７へ、公開鍵を暗号化部２３へ与える。公開鍵情報管理部１６は、署名検証部１４よりなんらかの信号を受けて、署名検証部１４へ保持する公開鍵を与える。公開鍵情報管理部１６は、署名検証部１４より、端末のＩＤ情報と公開鍵、及び検証が成功したか又は失敗したかの情報を与えられる。公開鍵情報管理部１６は、検証が成功した場合には、保持する情報の中で署名検証部１４より与えられた情報と一致する端末ＩＤ情報と公開鍵を、正当公開鍵情報管理部１２へ与える。公開鍵情報管理部１６は、検証が失敗した場合には、保持する情報の中で署名検証部１４より与えられた情報と一致する端末ＩＤ情報と公開鍵を、破棄する。
【００６２】
＜検証端末情報管理部１７＞
検証端末情報管理部１７は、検証する側の端末のＩＤ情報と公開鍵を一時的に保持する。検証端末情報管理部１７は、正当公開鍵情報管理部１２より与えられるＩＤ情報と公開鍵を保持する。検証端末情報管理部１７は、署名検証部１４よりなんらかの信号を受けて、保持する公開鍵を署名検証部１４と暗号化部２３へ与える。
【００６３】
＜秘密情報管理部１８＞
秘密情報管理部１８は、既に説明したように、分散秘密情報管理部２１と、乱数生成部２２と、暗号化部２３と、秘密鍵情報管理部２４と、署名生成部２５と、復号部２６と、分散計算部２７とから構成される。秘密情報管理部１８内で管理される情報とやり取りされる情報は、外部に秘密であり、端末は、自分自身でもその情報を特定することができないように構成されている。
【００６４】
＜分散秘密情報管理部２１＞
分散秘密情報管理部２１は、グループ認証情報の分散情報を秘密に管理するものであり、改ざん検出部１５よりなんらかの信号を受けて、管理している分散秘密情報（第１の分散情報）をさらに分散し、分散した情報（第２の分散情報）を暗号化部２３と分散計算部２７へ与える。分散秘密情報管理部２１より出力される情報は、その都度異なる。分散秘密情報の分散は、例えば、加算分散法によって２つの情報に分散される。
【００６５】
＜乱数生成部２２＞
乱数生成部２２は、暗号化部２３よりなんらかのタイミング信号を受けることにより、擬似乱数情報を生成するものであり、生成した乱数情報を暗号化部２３へ返す。乱数生成部２２で生成される乱数情報は、その都度異なる。
【００６６】
＜暗号化部２３＞
暗号化部２３は、分散秘密情報管理部２１又は分散計算部２７より情報を受け取ることによりその情報を暗号化する。暗号化部２３は、分散秘密情報管理部２１又は分散計算部２７より情報を受け取ることにより、乱数生成部２２へなんらかの信号を与え、乱数生成部２２より乱数情報を受け取る。暗号化部２３は、乱数生成部２２より与えられた乱数情報を一時的な暗号化鍵として共通鍵暗号化方式を用いて、分散秘密情報管理部２１又は分散計算部２７より与えられた情報を暗号化する。暗号化部２３は、公開鍵情報管理部１６より与えられる公開鍵を用いて、一時的な暗号化鍵を暗号化し、分散秘密情報管理部２１より与えられた情報を暗号化したものとセットにして暗号化分散情報を生成し、生成した暗号化分散情報を署名生成部２５へ与える。
【００６７】
暗号化部２３は、検証端末情報管理部２４より与えられる公開鍵を用いて、一時的な暗号化鍵を暗号化し、分散計算部２７より与えられた情報を暗号化したものとセットにして暗号化分散計算結果を生成し、生成した暗号化分散計算結果を署名生成部２５へ与える。暗号化部２３は、１つ又は複数の共通鍵暗号方式を有する。共通鍵暗号方式としては、例えば、ＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）やｔｒｉｐｌｅＤＥＳ（Ｔｒｉｐｌｅ  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）などの暗号方式を想定するが、特に限定されるものではない。
【００６８】
＜秘密鍵情報管理部２４＞
秘密鍵情報管理部２４は、公開鍵暗号方式において自端末の公開鍵の対となる秘密鍵を管理するものであり、管理する秘密鍵を署名生成部２５と復号部２６へ与える。
【００６９】
＜署名生成部２５＞
署名生成部２５は、暗号化部２３より与えられた情報に対して自身の秘密鍵を用いて署名を生成し付加するものであり、生成した署名を元の情報に付加したものを送信部２０へ与える。署名生成部２５は、１つ又は複数のディジタル署名生成アルゴリズムを有する。署名生成アルゴリズムとしては、例えば、ハッシュ関数にＭＤ５（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  ５）などが想定され、公開鍵暗号方式にＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）などが想定されるが、特にこれらに限定されるものではない。
【００７０】
＜復号部２６＞
復号部２６は、署名検証部１４より与えられた暗号化情報を、秘密鍵情報管理部２４より与えられる自端末の秘密鍵を用いて復号し、この復号した情報を分散計算部２７へ与える。復号部２６は、１つ又は複数の共通鍵暗号方式を有する。ここで用いる共通鍵暗号方式は、特定の方式に限定されるものではなく、暗号化情報生成者の用いた方式と同じであればよい。
【００７１】
＜分散計算部２７＞
分散計算部２７は、復号部２６より情報を与えられることによって、その情報と自端末情報管理部１１より与えられる自端末のＩＤ情報と、公開鍵情報管理部１６より与えられる端末のＩＤ情報と公開鍵と、分散秘密情報管理部２１より与えられる自端末の分散秘密情報の分散情報を用いて分散計算を行うものであり、求められた計算結果を暗号化部２３に与える。
【００７２】
＜送信部２０＞
送信部２０は、端末１０内の構成から与えられた情報を送信する。
【００７３】
＜受信部１９＞
受信部１９は、受信した情報を端末１０内の任意の構成に与える。
【００７４】
［２−２−２．検証する側の端末］
図９は、本発明の実施形態の公開鍵の正当性判断方法が適用される検証する側の端末（検証端末）の構成を示すブロック図である。図９に示されるように、検証する側の端末３０は、自端末情報管理部３１と、自端末情報確認部３２と、検証端末情報管理部３３と、検証端末情報生成部３４と、秘密情報管理部３５と、署名検証部３６と、秘密情報再構成部３７と、認証情報検証部３８と、送信部３９と、受信部４０とを有する。また、秘密情報管理部３５は、秘密鍵情報管理部４１と、署名生成部４２と、復号部４３とを有する。
【００７５】
＜自端末情報管理部３１＞
自端末情報管理部３１は、自端末のＩＤ情報及び自端末の公開鍵情報を管理する。自端末情報管理部３１は、管理している情報を自端末情報確認部３２と検証端末情報生成部３４へ与える。
【００７６】
＜自端末情報確認部３２＞
自端末情報確認部３２は、受信部４０より検証依頼情報を与えられ、自端末情報管理部３１より自端末のＩＤ情報及び自端末の公開鍵を与えられる。自端末情報確認部３２は、検証依頼情報の中に、自端末のＩＤ情報と自端末の公開鍵が含まれているかどうかを確認する。自端末情報確認部３２は、検証依頼情報の中に自端末に関する正しい情報が含まれているときには、検証依頼をした端末のＩＤ情報、公開鍵、グループ認証情報、及びグループ認証情報の検証方法に関する情報を、検証端末情報管理部３３へ与える。
【００７７】
＜検証端末情報管理部３３＞
検証端末情報管理部３３は、検証依頼をした端末の情報を管理する。検証端末情報管理部３３は、自端末情報確認部３２より、検証依頼をした端末のＩＤ情報、公開鍵、グループ認証情報、及びグループ認証情報の検証方法に関する情報を受け、それらを保持する。検証端末情報管理部３３は、グループ認証情報の検証方法に関する情報における条件を満たす端末が存在するときに、それら端末のＩＤ情報と公開鍵、グループ認証情報、及びグループ認証情報の検証方法に関する情報を検証端末情報生成部３４へ、それら端末のグループ認証情報の検証方法に関する情報を秘密情報再構成部３７へ、それら端末のグループ認証情報を認証情報検証部３８へ与える。ここで、グループ認証情報の検証方法に関する情報における条件とは、例えば、同じグループ認証情報を持つ端末で、同じ検証方法を持つ端末が存在する等の条件である。また、検証端末情報管理部３３は、署名検証部３６より端末のＩＤ情報を与えられて、そのＩＤ情報に対応する公開鍵を署名検証部３６に返す。
【００７８】
＜検証端末情報生成部３４＞
検証端末情報生成部３４は、検証端末情報管理部３３より与えられる検証する側の端末１０のＩＤ情報と公開鍵、グループ認証情報、グループ認証情報の検証方法に関する情報、及び自端末情報管理部３１より与えられる自端末のＩＤ情報と公開鍵より、検証端末情報を生成し、生成した検証端末情報を署名生成部４２へ与える。
【００７９】
＜秘密情報管理部３５＞
秘密情報管理部３５は、秘密鍵情報管理部４１と、署名生成部４２と、復号部４３とから構成され、その内部で管理される情報とやり取りされる情報は外部に秘密であり、端末３０は、自分自身でもその情報を特定することができないものとする。
【００８０】
＜秘密鍵情報管理部４１＞
秘密鍵情報管理部４１は、公開鍵暗号方式において自端末の公開鍵の対となる秘密鍵を管理し、管理する秘密鍵を署名生成部４２と復号部４３へ与える。
【００８１】
＜署名生成部４２＞
署名生成部４２は、検証端末情報生成部３４と認証情報検証部３８より与えられた情報に対して、自身の秘密鍵を用いて署名を生成し付加するものであり、生成した署名を元の情報に付加したものを送信部３９へ与える。署名生成部４２は、１つ又は複数のディジタル署名生成アルゴリズムを有する。このディジタル署名生成アルゴリズムとしては、例えば、ハッシュ関数にＭＤ５などが想定され、公開鍵暗号方式にＲＳＡなどが想定されるが、特に、これらに限定されるものではない。
【００８２】
＜復号部４３＞
復号部４３は、署名検証部３６より与えられた暗号化情報を秘密鍵情報管理部４１より与えられる自端末の秘密鍵を用いて復号し、復号した情報を秘密情報再構成部３７へ与える。復号部４３は、１つ又は複数の共通鍵暗号方式を有する。ここで用いる共通鍵暗号方式は、特に限定されず、暗号化情報生成者の用いた方式と同じであればよい。
【００８３】
＜署名検証部３６＞
署名検証部３６は、受信部４０より与えられる情報が、送信元端末だと想定される端末が生成したものかどうかを検証する。例えば、与えられた情報から署名を取り除いた情報をハッシュ関数に通した出力と、送信元端末だと想定される端末の公開鍵で署名を復号した情報が一致するかどうかによって検証するというような、一般的なディジタル署名方式を想定している。署名検証部３６は、１つ又は複数のディジタル署名生成アルゴリズムを有する。ここで用いるディジタル署名方式は、特に限定されず、署名生成者の用いた方式と同じであればよい。署名検証部３６は、受信部４０より暗号化分散計算結果を与えられて、その送信元端末だと想定される端末のＩＤ情報を検証端末情報管理部３３へ与え、公開鍵を受ける。署名検証部３６は、与えられた公開鍵で署名を検証し、署名が確かめられた場合には、暗号化分散計算結果を復号部４３へ与える。署名検証部３６は、署名の検証がうまくいかなかった場合には、その情報を破棄する。
【００８４】
＜秘密情機再構成部３７＞
秘密情機再構成部３７は、復号部４３より与えられる分散計算結果を、検証端末情報管理部３３より与えられるグループ認証情報の再構成方法によって、グループ認証情報を再構成する。秘密情機再構成部３７は、再構成した情報を認証情報検証部３８へ与える。
【００８５】
＜認証情報検証部３８＞
認証情報検証部３８は、検証端末情報管理部３３より、検証する端末のＩＤ情報と公開鍵とグループ認証情報が与えられ、グループ認証情報と秘密情報再構成部３７より与えられる秘密再構成情報とが一致するかどうかを検証する。認証情報検証部３８は、一致する、又は、異なることにより、検証した端末のＩＤ情報と公開鍵と成功した、又は、失敗したという情報を付け足し、生成した情報を署名生成部４２へ与える。
【００８６】
＜送信部３９＞
送信部３９は、端末３０内の構成から与えられた情報を送信する。
【００８７】
＜受信部４０＞
受信部４０は、受信した情報を端末３０内の任意の構成に与える。
【００８８】
［２−３．公開鍵の正当性判断方法における処理内容］
図１０は、本発明の実施形態の公開鍵の正当性判断方法において検証端末を決定するための処理を示す説明図である。また、図１１及び図１２は、本発明の実施形態の公開鍵の正当性判断方法において検証結果を得るための処理を示す説明図（その１及びその２）である。なお、検証する側の端末（すなわち、検証を行う端末を「検証端末」、検証を行う端末となる可能性のある端末を「検証端末候補」と呼ぶ。また、検証される側の端末（すなわち、検証を受ける端末）を「被検証端末」、検証を受ける端末が互いの端末を「相手被検証端末」と呼ぶ。
【００８９】
＜検証端末を決定するまでの処理＞（図１０参照）
（ステップＳＴ１）
被検証端末１０ａ，１０ｂ（図８の符号１０）のそれぞれは、検証依頼情報生成部（図８の符号１３）において検証依頼情報を生成し、生成した検証依頼情報を送信部（図８の符号２０）から検証端末候補３０ａ（図９の符号３０）に送信する。
【００９０】
（ステップＳＴ２）
検証端末候補３０ａは、被検証端末１０ａ，１０ｂのそれぞれから送信された検証依頼情報を受信し、自端末情報確認部（図９の符号４０）によって受信した検証依頼情報に自端末のＩＤ情報と公開鍵が含まれていることを確認する。検証端末候補３０ａの検証端末情報管理部（図９の符号３３）は、検証依頼情報に含まれる端末の情報を保持する。検証端末候補３０ａの検証端末情報管理部（図９の符号３３）において、保持する端末の中から被検証端末が選出され検証端末情報生成部（図９の符号３４）へ与えられる。検証端末候補３０ａは、検証端末情報生成部（図９の符号３４）において検証端末情報を生成し、署名生成部（図９の符号４２）によって自身の署名を付加して、自身の署名が付加された検証端末情報を送信部（図９の符号３９）から被検証端末１０ａ，１０ｂに送信する。
【００９１】
（ステップＳＴ３）
被検証端末１０ａ，１０ｂのそれぞれは、検証端末候補３０ａより検証端末情報を受信し、署名検証部（図８の符号１４）においてその情報の送信元端末が信頼が高い端末かどうかを確認する。確認された検証端末情報は改ざん検出部（図８の符号１５）へ与えられ、改ざん検出部（図８の符号１５）において検証端末情報に含まれる自端末に関する情報が改ざんされていないことを確認する。被検証端末１０ａ，１０ｂのそれぞれは、検証端末情報に含まれる相手被検証端末のＩＤ情報と信用したい公開鍵を公開鍵情報管理部（図８の符号１６）で保持する。また、被検証端末１０ａ，１０ｂのそれぞれは、検証端末情報を送信した信頼が高い端末のＩＤ情報と公開鍵を正当公開鍵情報管理部（図８の符号１６）を経由して検証端末情報管理部（図８の符号１７）で保持する。また、被検証端末１０ａ，１０ｂのそれぞれは、改ざん検出部（図８の符号１５）においてなんらかの信号を生成し、分散秘密情報管理部（図８の符号２１）へ与える。公開鍵情報管理部（図８の符号１６）において保持する相手被検証端末のＩＤ情報は分散計算部（図８の符号２７）へ与えられ、公開鍵は暗号化部（図８の符号２３）へ与えられる。以上のステップＳＴ３の動作がすべての被検証端末（本実施形態においては、２台の被検証端末１０ａ，１０ｂ）において行われることで、検証端末が決定する（例えば、検証候補端末３０ａが検証端末になる。）。
【００９２】
＜認証を実行し検証結果を得るまでの処理＞（図１１及び図１２参照）
（ステップＳＴ１１）
被検証端末１０ａ，１０ｂの分散秘密情報管理部（図８の符号２１）において、分散秘密情報がさらに分散され、一方が暗号化部（図８の符号２３）へ、もう一方が分散計算部（図８の符号２７）へ与えられる。暗号化部（図８の符号２３）において、分散情報と相手被検証端末の公開鍵により暗号化分散情報が生成され、暗号化分散情報を署名生成部（図８の符号２５）へ与える。
【００９３】
（ステップＳＴ１２）
署名生成部（図８の符号２５）は、暗号化分散情報に自身の署名を付加して、相手被検証端末へ送信する。
【００９４】
（ステップＳＴ１３）
被検証端末１０ａ，１０ｂのそれぞれは、相手被検証端末から暗号化分散情報を受信し、署名検証部（図８の符号１４）において、その情報の送信元端末が公開鍵情報管理部（図８の符号１６）に記憶している相手被検証端末であることを確認する。確認された暗号化分散情報は復号部（図８の符号２６）へ与えられ、復号部（図８の符号２６）において暗号化分散情報を復号し、分散計算部（図８の符号２７）へ与える。分散計算部（図８の符号２７）において、自端末のＩＤ情報と、分散秘密情報管理部（図８の符号２１）により与えられた情報と、相手被検証端末のＩＤ情報と、復号部（図８の符号２６）より与えられた情報より分散計算が実行され、生成した分散計算結果を暗号化部（図８の符号２３）へ与える。暗号化部（図８の符号２３）において、分散計算結果と検証端末の公開鍵により暗号化分散計算結果が生成され、生成された暗号化分散計算結果を署名生成部（図８の符号２５）へ与える。
【００９５】
（ステップＳＴ１４）
被検証端末１０ａ，１０ｂのそれぞれは、署名生成部（図８の符号２５）において生成された暗号化分散計算結果に自身の署名を付加して検証端末３０ａへ送信する。
【００９６】
（ステップＳＴ１５）
検証端末３０ａは被検証端末１０ａ，１０ｂのそれぞれから暗号化分散計算結果を受信し、署名検証部（図９の符号３６）において、その情報の送信元端末が被検証端末１０ａ，１０ｂであることを確認する。確認された暗号化分散計算結果は、復号部（図９の符号４３）へ与えられ、復号部（図９の符号４３）において暗号化分散計算結果を復号し、秘密情報再構成部（図９の符号３７）へ与える。秘密情報再構成部（図９の符号３７）において、被検証端末１０ａ，１０ｂの指定する再構成方法で用いて情報を再構成し、再構成した情報を認証情報検証部（図９の符号３８）へ与える。認証情報検証部（図９の符号３８）において、検証され検証結果情報が生成される。
【００９７】
（ステップＳＴ１６）
検証端末３０ａは、署名生成部（図９の符号４２）において、検証結果情報に自身の署名を付加して被検証端末１０ａ，１０ｂへ送信する。
【００９８】
（ステップＳＴ１７）
被検証端末１０ａ，１０ｂのそれぞれは、検証端末３０ａから検証結果情報を受信し、署名検証部（図８の符号１４）において、その情報の送信元端末が検証端末３０ａであることを確認する。被検証端末１０ａ，１０ｂのそれぞれは、確認された検証結果情報を公開鍵情報管理部（図８の符号１６）へ与え、公開鍵情報管理部（図８の符号１６）において、保持されている相手被検証端末の公開鍵を信用するかどうかを判断する。被検証端末１０ａ，１０ｂのそれぞれは、検証結果情報が成功の場合は、相手被検証端末のＩＤ情報と公開鍵を信用し、それら情報を正当公開鍵情報管理部（図８の符号１２）へ与える。失敗の場合は、相手被検証端末のＩＤ情報と公開鍵を破棄する。以上の動作によって相手被検証端末のＩＤ情報と公開鍵を信用するかどうか（すなわち、相手被検証端末の正当性）を判断する。
【００９９】
［２−４．公開鍵の正当性判断方法の効果］
本実施形態の公開鍵の正当性判断方法においては、グループメンバ端末である被検証端末は、自身の正しい端末ＩＤ情報を主張しないと、検証端末においてグループ認証情報が再構成されず、認証に失敗するため、被検証端末は、自身のＩＤ情報を偽ることはできない。すなわち、他のメンバ端末へのなりすましは不可能である。また、本実施形態の公開鍵の正当性判断方法においては、グループメンバ端末である被検証端末は、自身の保持する秘密鍵に対応した公開鍵を主張しないと、秘密通信路が確立せず、検証端末において認証に失敗するため、被検証端末は、自身の公開鍵を偽ることはできない。以上より、検証端末によって認証成功の検証結果をもらうことは、相手被検証端末のＩＤ情報と公開鍵に偽りがないことを意味する。
【０１００】
したがって、本実施形態の公開鍵の正当性判断方法を用いれば、被検証端末は、ネットワーク内に共通に信頼できる端末が存在することで、互いの公開鍵を信用することが可能となる。ここで、被検証端末が共通に信頼できる端末は、被検証端末の公開鍵を信用する必要はなく、また、検証に必要なグループ認証情報とその検証方法も公開できるため、事前情報を持つ必要がないという利点がある。すなわち、被検証端末が共通に信頼でき、秘密再構成手段を持つ端末であれば、ネットワーク内に存在するいずれの端末も検証端末になり得る。
【０１０１】
以上の効果は、上記秘密再構成方法（項目１において説明）において秘密を再構成できる端末数の閾値を２としてメンバＩＤ情報とグループ認証情報を公開することと、被検証端末が主張する公開鍵を利用して秘密通信路を構築することによって生まれる効果である。
【０１０２】
例えば、図１において、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６が互いの公開鍵を信用したいが、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６は、互いを正確に特定できるような情報を有していない場合を検討する。ここで、端末００１と端末００２が共通に信頼できる端末００７が存在するものとする。しかし、端末００７は端末００１と端末００２の公開鍵を信用していない（図１３）。そこで、端末００１と端末００２は、端末００７に検証端末となってもらい、互いの公開鍵が信用できるかどうかを判断する（図１４）。端末００１と端末００２が互いに正しい公開鍵を知ることにより、端末００１は信頼グループＲＧ１に加入できる。ここで、端末００２が信頼グループＲＧ１に属する他の端末（この場合は端末００３）と互いの公開鍵を信用しているとすると、信用の輪の概念によって端末００１と端末００３が互いの公開鍵を信用することが可能になる（図１５）。
【０１０３】
このようにして、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６が互いを正確に特定できるような情報を有していなくても、端末００１と信頼グループＲＧ１の端末が共通に信頼できる端末がネットワーク内に存在することで、端末００１と信頼グループＲＧ１を形成する端末００２，００３，…，００６が互いの公開鍵を信用することが可能となる。
【０１０４】
［３．本発明の他の利用形態の説明］
上記説明においては、互いの公開鍵を信用したい端末が２台存在する場合を説明したが、本発明は互いの公開鍵を信用したい端末が２台の場合に限定されない。本発明は、互いの公開鍵を信用したい端末（被検証端末）が３台以上存在する場合であっても、互いの公開鍵を信用したい３台以上の端末が共通に信頼できる端末（検証端末）が存在する場合には適用可能である。
【０１０５】
また、上記説明においては、公開鍵暗号方式と共通鍵暗号方式を組み合わせたハイブリッド暗号化方式と、公開鍵暗号方式によるディジタル署名を用いることより秘密通信と送信元端末の特定を実現している場合を説明したが、本発明はこのような方式に限定されない。本発明においては、公開鍵暗号方式のみを用いた暗号化通信とディジタル署名により、秘密通信と送信元端末の特定を実現してもよい。
【０１０６】
また、本発明においては、公開鍵暗号方式に基づく鍵共有方法を用いて相手端末と対称鍵を共有することにより、秘密通信と送信元端末の特定を実現してもよい。例えば、エルガマル（Ｅｌｇａｍａｌ）暗号のように離散対数問題の難しさに基づく公開鍵暗号方式を用いている場合は、ディフィ・ヘルマン（Ｄｉｆｆｉｅｅ−Ｈｅｌｌｍａｎ）法によって相手端末との対称鍵を生成し、その対称鍵で情報を暗号化してもよい。この場合、生成した対称鍵で暗号化することは、同じ対称鍵をもつ相手端末との間の秘密通信と送信元端末の特定が実現できるため、暗号化情報に付加する自身の署名を省くことができる。
【０１０７】
さらにまた、上記各端末が、公開鍵と秘密鍵のペアを更新する装置を内部に有しており、その公開鍵に有効期限を設けることで、現在のネットワーク内のみ、又は、限られた有効期限までの期間のみ有効な一時的な公開鍵を主張してもよい。
【０１０８】
また、上記説明においては、検証される側の端末１０と検証する側の端末３０とが異なる構成の端末である場合を説明した。しかし、各端末が、図８に示される検証される側の端末１０の構成及び図９に示される検証する側の端末３０の構成の両方を備えることにより、ネットワーク内の各端末が、検証される側の端末１０としての機能と検証する側の端末３０としての機能を併せ持つように構成してもよい。
【図面の簡単な説明】
【０１０９】
【図１】複数の端末からなるアドホックネットワークを示す図である。
【図２】秘密分散法を実施するための端末及び秘密通信路を示す図である。
【図３】秘密再構成方法の概要を説明するための図である。
【図４】図３の分散秘密再構成計算部の構成を示すブロック図である。
【図５】秘密再構成方法を示すフローチャートである。
【図６】本発明の実施形態の公開鍵の正当性判断方法の概要を説明するための図である。
【図７】本発明の実施形態の公開鍵の正当性判断方法において利用される秘密再構成方法を説明するための図である。
【図８】本発明の実施形態の公開鍵の正当性判断方法が適用される検証される側の端末（被検証端末）の構成を示すブロック図である。
【図９】本発明の実施形態の公開鍵の正当性判断方法が適用される検証する側の端末（検証端末）の構成を示すブロック図である。
【図１０】本発明の実施形態の公開鍵の正当性判断方法において検証端末を決定するための処理を示す説明図である。
【図１１】本発明の実施形態の公開鍵の正当性判断方法において検証結果を得るまでの処理を示す説明図（その１）である。
【図１２】本発明の実施形態の公開鍵の正当性判断方法において検証結果を得るまでの処理を示す説明図（その２）である。
【図１３】本発明の実施形態の公開鍵の正当性判断方法による効果を説明するための図（その１）である。
【図１４】本発明の実施形態の公開鍵の正当性判断方法による効果を説明するための図（その２）である。
【図１５】本発明の実施形態の公開鍵の正当性判断方法による効果を説明するための図（その３）である。
【符号の説明】
【０１１０】
１０，１０ａ，１０ｂ  検証される側の端末（検証を受ける端末、被検証端末、又は、相手被検証端末）、
１１  自端末情報管理部、
１２  正当公開鍵情報管理部、
１３  検証依頼情報生成部、
１４  署名検証部、
１５  改ざん検出部、
１６  公開鍵情報管理部、
１７  検証端末情報管理部、
１８  秘密情報管理部、
１９  受信部、
２０  送信部、
２１  分散秘密情報管理部、
２２  乱数生成部、
２３  暗号化部、
２４  秘密鍵情報管理部、
２５  署名生成部、
２６  復号部、
２７  分散計算部、
３０，３０ａ  検証する側の端末（検証を行う端末、又は、検証端末）、
３１  自端末情報管理部、
３２  自端末情報確認部、
３３  検証端末情報管理部、
３４  検証端末情報生成部、
３５  秘密情報管理部、
３６  署名検証部、
３７  秘密情報再構成部、
３８  認証情報検証部、
３９  送信部、
４０  受信部、
４１  秘密鍵情報管理部、
４２  署名生成部、
４３  復号部、
３０３  秘密通信路、
６０１  メンバの分散秘密再構成計算部（分散秘密再構成装置）、
６０１−ｊ  メンバＩＤがｍｊであるメンバの分散秘密再構成計算部、
６０２  秘密再構成装置の秘密再構成計算部、
７０１−ｊ  メンバＩＤがｍｊであるメンバの秘密分散計算部、
７０２−ｊ  メンバＩＤがｍｊであるメンバの線形結合計算部、
Ｓ  もとの秘密情報、
ｍ１，ｍ２，…，ｍｎ  メンバＩＤ、
ｍ’１，ｍ’２，…，ｍ’ｔ  集まったメンバのメンバＩＤ、
Ｘｍｊ  メンバＩＤがｍｊであるメンバに配布される分散情報、
Ｘｍｊ,ｐ  メンバＩＤがｍｊであるメンバからメンバＩＤがｍｐであるメンバｐに対して配布する分散情報、
Ｓｊ  メンバｊが分散再構成した分散情報。
【図１】
2005328123.tif 000012
【図２】
2005328123.tif 000013
【図３】
2005328123.tif 000014
【図４】
2005328123.tif 000015
【図５】
2005328123.tif 000016
【図６】
2005328123.tif 000017
【図７】
2005328123.tif 000018
【図８】
2005328123.tif 000019
【図９】
2005328123.tif 000020
【図１０】
2005328123.tif 000021
【図１１】
2005328123.tif 000022
【図１２】
2005328123.tif 000023
【図１３】
2005328123.tif 000024
【図１４】
2005328123.tif 000025
【図１５】
2005328123.tif 000026