(57)【要約】      （修正有）【課題】ＩＣカードを利用して電子署名を生成する際に、処理負荷を最小限に抑える。【解決手段】端末２は、電子署名アルゴリズムにおいて、電子署名が付されるメッセージに依存しないメッセージ非依存情報を保管するカード３００から、メッセージ依存情報を生成するための生成用情報を受信する生成用情報受信部と、電子署名が付加されるメッセージを生成するメッセージ生成部２０２と、前記生成用情報と前記メッセージとから生成されたメッセージ依存情報をカード３００へ送信するメッセージ依存情報送信部と、前記メッセージ依存情報に基づいてカード３００が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、を備える。【選択図】図９
2014048414.tif 000002
【特許請求の範囲】
【請求項１】
電子署名が付加されるメッセージを生成するメッセージ生成部と、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、
を備える、情報処理装置。
【請求項２】
前記メッセージ依存情報を生成するための生成用情報を受信する生成用情報受信部と、
前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成部と、
を更に備える、請求項１に記載の情報処理装置。
【請求項３】
前記生成用受信部が受信した前記生成用情報と、前記電子署名に関する情報とに基づいて電子署名を生成する電子署名生成部を更に備える、請求項２に記載の情報処理装置。
【請求項４】
前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成装置から前記メッセージ依存情報を受信するメッセージ依存情報受信部を備える、請求項１に記載の情報処理装置。
【請求項５】
前記生成用情報受信部は、前記生成用情報をハッシュ値として受信し、
前記メッセージ依存情報生成部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として前記メッセージ依存情報を生成する、請求項２に記載の情報処理装置。
【請求項６】
前記他装置はＩＣカードである、請求項１に記載の情報処理装置。
【請求項７】
前記電子署名は、ＭＱプロトコルによる電子署名である、請求項１に記載の情報処理装置。
【請求項８】
電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持する情報保持部と、
前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信するメッセージ依存情報受信部と、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、
を備える、情報処理装置。
【請求項９】
前記メッセージ非依存情報送信部は、前記メッセージ非依存情報のうち、メッセージ依存情報を生成するための生成用情報を送信する生成用情報送信部を含み、
前記メッセージ依存情報受信部は、前記生成用情報と前記メッセージとから生成された前記メッセージ依存情報を受信する、請求項８に記載の情報処理装置。
【請求項１０】
前記電子署名情報送信部は、前記メッセージ非依存情報から抽出して得た前記電子署名に関する情報から、前記生成用情報を除いた部分を送信する、請求項９に記載の情報処理装置。
【請求項１１】
前記生成用情報送信部は、前記生成用情報の代わりに、前記生成用情報に対応する識別番号を送信し、
前記メッセージ依存情報受信部は、メッセージ依存情報生成装置が前記識別番号に対応して保管する前記生成用情報と前記メッセージとから生成したメッセージ依存情報を受信する、請求項９に記載の情報処理装置。
【請求項１２】
前記情報保持部は、前記メッセージ非依存情報のうち前記電子署名アルゴリズムの秘密鍵に関連する情報を保持するセキュア領域と、前記メッセージ非依存情報のうち前記秘密鍵に関連しない情報を保持する非セキュア領域と、を有する、請求項８に記載の情報処理装置。
【請求項１３】
前記生成用情報送信部は、前記生成用情報をハッシュ値として送信し、
前記メッセージ依存情報受信部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として生成された前記メッセージ依存情報を受信する、請求項９に記載の情報処理装置。
【請求項１４】
電子署名が付加されるメッセージを生成するメッセージ生成部と、他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、を備える、情報処理装置と、
前記メッセージ非依存情報を保持する情報保持部と、前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、前記メッセージ非依存情報と前記メッセージとから生成された前記メッセージ依存情報を受信するメッセージ依存情報受信部と、前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、を備える、ＩＣカードと、
を備える、情報処理システム。
【請求項１５】
電子署名が付加されるメッセージを生成することと、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信することと、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信することと、
を備える、情報処理方法。
【請求項１６】
電子署名が付加されるメッセージを生成する手段、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信する手段、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する手段、
としてコンピュータを機能させるためのプログラム。
【請求項１７】
電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持することと、
前記メッセージ非依存情報の少なくとも一部を送信することと、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信することと、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信することと、
を備える、情報処理方法。
【請求項１８】
電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持する手段、
前記メッセージ非依存情報の少なくとも一部を送信する手段、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信する手段、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する手段、
としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、情報処理システム、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
近時では、文書やメッセージ等に電子署名を付ける技術が広く用いられている。ユーザが外部端末を利用して署名を付ける場合、電子署名の秘密鍵を外部端末に入れないように、ＩＣカードが使われる場合がある。例えば、下記の特許文献１に記載されているように、ＲＳＡなどの公開鍵暗号関数を用いて、電子署名をＩＣカード内で生成する技術が知られている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許２９０２０８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、電子署名処理は公開鍵暗号系の演算を用いるものであり、一般的に公開鍵暗号関数の処理は負荷が高いことが知られているため、処理能力の低いＩＣカードが行うことには困難が伴う。このため、ＩＣカード内で処理を行う場合、性能の良いＣＰＵを搭載する必要があり、製造コストが上昇する問題がある。また、ＩＣカード内で電子署名を生成する場合、その処理負荷の高さに起因して、署名生成に必要な時間が長くなるという問題も生じる。
【０００５】
そこで、ＩＣカードを利用して電子署名を生成する際に、処理負荷を最小限に抑えることが望まれていた。
【課題を解決するための手段】
【０００６】
本開示によれば、電子署名が付加されるメッセージを生成するメッセージ生成部と、他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、を備える、情報処理装置が提供される。
【０００７】
前記メッセージ依存情報を生成するための生成用情報を受信する生成用情報受信部と、前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成部と、を更に備えるものであっても良い。
【０００８】
また、前記生成用受信部が受信した前記生成用情報と、前記電子署名に関する情報とに基づいて電子署名を生成する電子署名生成部を更に備えるものであっても良い。
【０００９】
また、前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成装置から前記メッセージ依存情報を受信するメッセージ依存情報受信部を備えるものであっても良い。
【００１０】
また、前記生成用情報受信部は、前記生成用情報をハッシュ値として受信し、前記メッセージ依存情報生成部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として前記メッセージ依存情報を生成するものであっても良い。
【００１１】
また、前記他装置はＩＣカードであっても良い。また、前記電子署名は、ＭＱプロトコルによる電子署名であっても良い。
【００１２】
また、本開示によれば、電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持する情報保持部と、前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信するメッセージ依存情報受信部と、前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、を備える、情報処理装置が提供される。
【００１３】
また、本開示によれば、前記メッセージ非依存情報送信部は、前記メッセージ非依存情報のうち、メッセージ依存情報を生成するための生成用情報を送信する生成用情報送信部を含み、前記メッセージ依存情報受信部は、前記生成用情報と前記メッセージとから生成された前記メッセージ依存情報を受信するものであっても良い。
また、前記電子署名情報送信部は、前記メッセージ非依存情報から抽出して得た前記電子署名に関する情報から、前記生成用情報を除いた部分を送信するものであっても良い。
【００１４】
また、前記生成用情報送信部は、前記生成用情報の代わりに、前記生成用情報に対応する識別番号を送信し、前記メッセージ依存情報受信部は、メッセージ依存情報生成装置が前記識別番号に対応して保管する前記生成用情報と前記メッセージとから生成したメッセージ依存情報を受信するものであっても良い。
【００１５】
また、前記情報保持部は、前記メッセージ非依存情報のうち前記電子署名アルゴリズムの秘密鍵に関連する情報を保持するセキュア領域と、前記メッセージ非依存情報のうち前記秘密鍵に関連しない情報を保持する非セキュア領域と、を有するものであっても良い。
【００１６】
また、前記生成用情報送信部は、前記生成用情報をハッシュ値として送信し、前記メッセージ依存情報受信部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として生成された前記メッセージ依存情報を受信するものであっても良い。
【００１７】
また、本開示によれば、電子署名が付加されるメッセージを生成するメッセージ生成部と、他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、を備える、情報処理装置と、前記メッセージ非依存情報を保持する情報保持部と、前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、前記メッセージ非依存情報と前記メッセージとから生成された前記メッセージ依存情報を受信するメッセージ依存情報受信部と、前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、を備える、ＩＣカードと、を備える、情報処理システムが提供される。
【発明の効果】
【００１８】
本開示によれば、ＩＣカードを利用して電子署名を生成する際に、処理負荷を最小限に抑えることが可能となる。
【図面の簡単な説明】
【００１９】
【図１】公開鍵認証方式のアルゴリズムについて概要を説明するための模式図である。
【図２】電子署名方式のアルゴリズムについて概要を説明するための模式図である。
【図３】ｎパスの公開鍵認証方式について説明するための説明図である。
【図４】３パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。
【図５】図４に示した３パス方式のアルゴリズムを並列化する方法について説明するための模式図である。
【図６】３パスの公開鍵認証方式から電子署名方式への変形を説明するための模式図である。
【図７】第１の実施形態のシステムの概要を示す模式図である。
【図８】メッセージ依存部分の情報を生成する処理を示すシーケンス図である。
【図９】第１の実施形態の構成を示す機能ブロック図である。
【図１０】第２の実施形態のシステムの概要を示す模式図である。
【図１１】第２の実施形態の処理を示すシーケンス図である。
【図１２】第２の実施形態の構成を示す機能ブロック図である。
【図１３】第１の実施形態の変形例を示す模式図である。
【図１４】第３の実施形態の構成を示す機能ブロック図である。
【図１５】ＭＤ型（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  ｃｏｎｓｔｒｕｃｔｉｏｎ）ハッシュ関数を示す模式図である。
【図１６】第４の実施形態の処理を示すシーケンス図である。
【図１７】情報処理装置のハードウェア構成を示す模式図である。
【発明を実施するための形態】
【００２０】
以下に添付図面を参照しながら、本開示の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２１】
［説明の流れについて］
ここで、以下に記載する本技術の実施形態に関する説明の流れについて簡単に述べる。まず、図１を参照しながら、公開鍵認証方式のアルゴリズム構成について説明する。次いで、図２を参照しながら、電子署名方式のアルゴリズム構成について説明する。次いで、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。
【００２２】
次いで、図４〜図５を参照しながら、３パスの公開鍵認証方式に係るアルゴリズムの構成例について説明する。次いで、図７〜図１６を参照しながら、本開示の第１〜第４の実施形態について説明する。次いで、図１７を参照しながら、本技術の実施形態に係る各アルゴリズムを実現することが可能な情報処理装置のハードウェア構成例について説明する。
【００２３】
（説明項目）
１：はじめに
１−１：公開鍵認証方式のアルゴリズム
１−２：電子署名方式のアルゴリズム
１−３：ｎパスの公開鍵認証方式
２：３パスの公開鍵認証方式に係るアルゴリズムの構成
２−１：具体的なアルゴリズムの構成例
２−２：並列化アルゴリズムの構成例
３：電子署名方式への変形
３−１：３パスの公開鍵認証方式から電子署名方式への変形
４：第１の実施形態
４−１：第１の実施形態に係るシステムの概要
４−２：第１の実施形態に係るシステムの処理
４−３：第１の実施形態に係るシステム構成例
５：第２の実施形態
５−１：第２の実施形態に係るシステムの概要
５−２：第２の実施形態に係るシステムの処理
５−３：第２の実施形態に係るシステム構成例
６：第３の実施形態
６−１：第３の実施形態に係るシステムの概要
６−２：第３の実施形態に係るシステム構成例
７：第４の実施形態
７−１：第４の実施形態に係るシステムの概要
７−２：第４の実施形態に係るシステムの処理
７−３：第４の実施形態に係るシステム構成例
８：認証プロトコルについて
９：ハードウェア構成例
【００２４】
＜１：はじめに＞
本実施形態は、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式に関する。但し、本実施形態は、ＨＦＥ電子署名方式などの従来手法とは異なり、効率的に解く手段（トラップドア）を持たない多次多変数連立方程式を利用する公開鍵認証方式及び電子署名方式に関する。まず、公開鍵認証方式のアルゴリズム、電子署名方式のアルゴリズム、及びｎパスの公開鍵認証方式について、その概要を簡単に説明する。
【００２５】
［１−１：公開鍵認証方式のアルゴリズム］
まず、図１を参照しながら、公開鍵認証方式のアルゴリズムについて概要を説明する。図１は、公開鍵認証方式のアルゴリズムについて概要を説明するための説明図である。
【００２６】
公開鍵認証は、ある人（証明者）が、公開鍵ｐｋ及び秘密鍵ｓｋを利用して、他の人（検証者）に本人であることを納得させるために利用される。例えば、証明者Ａの公開鍵ｐｋＡは、検証者Ｂに公開される。一方、証明者Ａの秘密鍵ｓｋＡは、証明者Ａにより秘密に管理される。公開鍵認証の仕組みにおいては、公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知る者が証明者Ａ本人であるとみなされる。
【００２７】
公開鍵認証の仕組みを利用して証明者Ａが証明者Ａ本人であることを検証者Ｂに証明するには、対話プロトコルを介して、証明者Ａが公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知っているという証拠を検証者Ｂに提示すればよい。そして、証明者Ａが秘密鍵ｓｋＡを知っているという証拠が検証者Ｂに提示され、その証拠を検証者Ｂが確認し終えた場合、証明者Ａの正当性（本人であること）が証明されたことになる。
【００２８】
但し、公開鍵認証の仕組みには、安全性を担保するために以下の条件が求められる。
【００２９】
１つ目の条件は、「対話プロトコルを実行した際に秘密鍵ｓｋを持たない偽証者により偽証が成立してしまう確率を限りなく小さくする」ことである。この１つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性とは、「秘密鍵ｓｋを持たない偽証者により、対話プロトコルの実行中に無視できない確率で偽証が成立することはないこと」と言い換えられる。２つ目の条件は、「対話プロトコルを実行したとしても、証明者Ａが有する秘密鍵ｓｋＡの情報が検証者Ｂに一切漏れることがない」ことである。この２つ目の条件が成り立つことを「零知識性」と呼ぶ。
【００３０】
安全に公開鍵認証を行うには、健全性及び零知識性を有する対話プロトコルを利用する必要がある。仮に、健全性及び零知識性を有しない対話プロトコルを用いて認証処理を行った場合には、偽証された可能性及び秘密鍵の情報が漏れてしまった可能性が否定できないため、処理自体が成功裡に完了しても証明者の正当性を証明したことにはならない。従って、対話プロトコルの健全性及び零知識性を如何に保証するかが重要になる。
【００３１】
（モデル）
公開鍵認証方式のモデルには、図１に示すように、証明者と検証者という２つのエンティティが存在する。証明者は、鍵生成アルゴリズムＧｅｎを用いて、証明者固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成する。次いで、証明者は、鍵生成アルゴリズムＧｅｎを用いて生成した秘密鍵ｓｋと公開鍵ｐｋの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムＰを利用して対話プロトコルを実行する。上記の通り、証明者は、証明者アルゴリズムＰを利用し、対話プロトコルの中で秘密鍵ｓｋを保有している証拠を検証者に提示する。
【００３２】
一方、検証者は、検証者アルゴリズムＶを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という２つのエンティティ、及び、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶという３つのアルゴリズムにより構成される。
【００３３】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムＶを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図１７に示した通りである。つまり、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶは、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、リムーバブル記録媒体９２８などに記録されたプログラムに基づいてＣＰＵ９０２などにより実行される。
【００３４】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、証明者により利用される。鍵生成アルゴリズムＧｅｎは、証明者に固有の秘密鍵ｓｋと公開鍵ｐｋとの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは公開される。そして、公開された公開鍵ｐｋは、検証者により利用される。一方、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者が秘密に管理する。そして、証明者により秘密に管理される秘密鍵ｓｋは、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有していることを検証者に対して証明するために利用される。形式的に、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、秘密鍵ｓｋと公開鍵ｐｋを出力するアルゴリズムとして、下記の式（１）のように表現される。
【００３５】
【数１】
2014048414.tif 000003
【００３６】
（証明者アルゴリズムＰ）
証明者アルゴリズムＰは、証明者により利用される。証明者アルゴリズムＰは、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有していることを検証者に対して証明するためのアルゴリズムである。つまり、証明者アルゴリズムＰは、秘密鍵ｓｋと公開鍵ｐｋとを入力とし、対話プロトコルを実行するアルゴリズムである。
【００３７】
（検証者アルゴリズムＶ）
検証者アルゴリズムＶは、検証者により利用される。検証者アルゴリズムＶは、対話プロトコルの中で、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムＶは、公開鍵ｐｋを入力とし、対話プロトコルの実行結果に応じて０又は１（１ｂｉｔ）を出力するアルゴリズムである。なお、検証者は、検証者アルゴリズムＶが０を出力した場合には証明者が不正なものであると判断し、１を出力した場合には証明者が正当なものであると判断する。形式的に、検証者アルゴリズムＶは、下記の式（２）のように表現される。
【００３８】
【数２】
2014048414.tif 000004
【００３９】
上記の通り、意味のある公開鍵認証を実現するには、対話プロトコルが健全性及び零知識性という２つの条件を満たしている必要がある。しかし、証明者が秘密鍵ｓｋを保有していることを証明するためには、証明者が秘密鍵ｓｋに依存した手続きを実行し、その結果を検証者に通知した上で、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵ｓｋに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、秘密鍵ｓｋの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶを巧妙に設計する必要がある。
【００４０】
以上、公開鍵認証方式のアルゴリズムについて、その概要を説明した。
【００４１】
［１−２：電子署名方式のアルゴリズム］
次に、図２を参照しながら、電子署名方式のアルゴリズムについて概要を説明する。図２は、電子署名方式のアルゴリズムについて概要を説明するための説明図である。
【００４２】
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果が得られる電子的な仕組みを必要とする。この仕組みが電子署名である。電子署名とは、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを言う。
【００４３】
（モデル）
電子署名方式のモデルには、図２に示すように、署名者及び検証者という２つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより構成される。
【００４４】
署名者は、鍵生成アルゴリズムＧｅｎを利用して署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成する。また、署名者は、署名生成アルゴリズムＳｉｇを利用して文書Ｍに付与する電子署名σを生成する。つまり、署名者は、文書Ｍに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムＶｅｒを利用して文書Ｍに付与された電子署名σを検証する。つまり、検証者は、文書Ｍの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。
【００４５】
なお、以下の説明において、「署名者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇを実行する主体は、「署名者」のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムＶｅｒを実行する主体は、情報処理装置である。これら情報処理装置のハードウェア構成は、例えば、図１７に示した通りである。つまり、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒは、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、リムーバブル記録媒体９２８などに記録されたプログラムに基づいてＣＰＵ９０２などにより実行される。
【００４６】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、署名者により利用される。鍵生成アルゴリズムＧｅｎは、署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された検証鍵ｐｋは公開される。一方、鍵生成アルゴリズムＧｅｎにより生成された署名鍵ｓｋは、署名者により秘密に管理される。そして、署名鍵ｓｋは、文書Ｍに付与される電子署名σの生成に利用される。例えば、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、署名鍵ｓｋ及び公開鍵ｐｋを出力する。この場合、鍵生成アルゴリズムＧｅｎは、形式的に、下記の式（３）のように表現することができる。
【００４７】
【数３】
2014048414.tif 000005
【００４８】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、署名者により利用される。署名生成アルゴリズムＳｉｇは、文書Ｍに付与される電子署名σを生成するアルゴリズムである。署名生成アルゴリズムＳｉｇは、署名鍵ｓｋと文書Ｍとを入力とし、電子署名σを出力するアルゴリズムである。この署名生成アルゴリズムＳｉｇは、形式的に、下記の式（４）のように表現することができる。
【００４９】
【数４】
2014048414.tif 000006
【００５０】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証者により利用される。署名検証アルゴリズムＶｅｒは、電子署名σが文書Ｍに対する正当な電子署名であるか否かを検証するアルゴリズムである。署名検証アルゴリズムＶｅｒは、署名者の検証鍵ｐｋ、文書Ｍ、電子署名σを入力とし、０又は１（１ｂｉｔ）を出力するアルゴリズムである。この署名検証アルゴリズムＶｅｒは、形式的に、下記の式（５）のように表現することができる。なお、検証者は、署名検証アルゴリズムＶｅｒが０を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを拒否する場合）に電子署名σが不当であると判断し、１を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを受理する場合）に電子署名σが正当であると判断する。
【００５１】
【数５】
2014048414.tif 000007
【００５２】
以上、電子署名方式のアルゴリズムについて、その概要を説明した。
【００５３】
［１−３：ｎパスの公開鍵認証方式］
次に、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。図３は、ｎパスの公開鍵認証方式について説明するための説明図である。
【００５４】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを検証者に証明する認証方式である。また、対話プロトコルは、健全性及び零知識性という２つの条件を満たす必要がある。そのため、対話プロトコルの中では、図３に示すように、証明者及び検証者の双方がそれぞれ処理を実行しながらｎ回の情報交換を行う。
【００５５】
ｎパスの公開鍵認証方式の場合、証明者アルゴリズムＰを用いて証明者により処理（工程＃１）が実行され、情報Ｔ１が検証者に送信される。次いで、検証者アルゴリズムＶを用いて検証者により処理（工程＃２）が実行され、情報Ｔ２が証明者に送信される。さらに、ｋ＝３〜ｎについて処理の実行及び情報Ｔｋの送信が順次行われ、最後に処理（工程＃ｎ＋１）が実行される。このように、情報がｎ回送受信される方式のことを「ｎパス」の公開鍵認証方式と呼ぶ。
【００５６】
以上、ｎパスの公開鍵認証方式について説明した。
【００５７】
＜２：３パスの公開鍵認証方式に係るアルゴリズムの構成＞
以下、３パスの公開鍵認証方式に係るアルゴリズムについて説明する。なお、以下の説明において、３パスの公開鍵認証方式のことを「３パス方式」と呼ぶ場合がある。
【００５８】
［２−１：具体的なアルゴリズムの構成例（図４）］
まず、図４を参照しながら、３パス方式に係る具体的なアルゴリズムの構成例について紹介する。図４は、３パス方式に係る具体的なアルゴリズムの構成について説明するための説明図である。ここでは、公開鍵ｐｋの一部として２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を利用する場合について考える。但し、２次多項式ｆｉ（ｘ）は、下記の式（６）のように表現されるものとする。また、ベクトル（ｘ１，…，ｘｎ）をｘと表記し、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を多変数多項式Ｆ（ｘ）と表記することにする。
【００５９】
【数６】
2014048414.tif 000008
【００６０】
また、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））は、下記の式（７）のように表現することができる。また、Ａ１，…，Ａｍは、ｎ×ｎ行列である。さらに、ｂ１，…，ｂｍはそれぞれｎ×１ベクトルである。
【００６１】
【数７】
2014048414.tif 000009
【００６２】
この表現を用いると、多変数多項式Ｆは、下記の式（８）及び式（９）のように表現することができる。この表現が成り立つことは、下記の式（１０）から容易に確認することができる。
【００６３】
【数８】
2014048414.tif 000010
【００６４】
このようにＦ（ｘ＋ｙ）をｘに依存する第１の部分と、ｙに依存する第２の部分と、ｘ及びｙの両方に依存する第３の部分とに分けたとき、第３の部分に対応する項Ｇ（ｘ，ｙ）は、ｘ及びｙについて双線形になる。以下、項Ｇ（ｘ，ｙ）を双線形項と呼ぶ場合がある。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。
【００６５】
例えば、ベクトルｔ０∈Ｋｎ、ｅ０∈Ｋｍを用いて、多変数多項式Ｆ（ｘ＋ｒ）のマスクに利用する多変数多項式Ｆ１（ｘ）をＦ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０と表現する。この場合、多変数多項式Ｆ（ｘ＋ｒ０）とＧ（ｘ）との和は、下記の式（１１）のように表現される。ここで、ｔ１＝ｒ０＋ｔ０、ｅ１＝Ｆ（ｒ０）＋ｅ０とおけば、多変数多項式Ｆ２（ｘ）＝Ｆ（ｘ＋ｒ０）＋Ｆ１（ｘ）は、ベクトルｔ１∈Ｋｎ、ｅ１∈Ｋｍにより表現することができる。そのため、Ｆ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０に設定すれば、Ｋｎ上のベクトル及びＫｍ上のベクトルを用いてＦ１及びＦ２を表現できるようになり、通信に必要なデータサイズの少ない効率的なアルゴリズムを実現することが可能になる。
【００６６】
【数９】
2014048414.tif 000011
【００６７】
なお、Ｆ２（或いはＦ１）からｒ０に関する情報が一切漏れることはない。例えば、ｅ１及びｔ１（或いはｅ０及びｔ０）を与えられても、ｅ０及びｔ０（或いはｅ１及びｔ１）を知らない限り、ｒ０の情報を一切知ることはできない。従って、零知識性が担保される。以下、上記の論理に基づいて構築された３パス方式のアルゴリズムについて説明する。ここで説明する３パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶにより構成される。
【００６８】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｍ本の多変数多項式ｆ１（ｘ１，…，ｘｎ），…，ｆｍ（ｘ１，…，ｘｎ）、及びベクトルｓ＝（ｓ１，…，ｓｎ）∈Ｋｎを生成する。次に、鍵生成アルゴリズムＧｅｎは、ｙ＝（ｙ１，…，ｙｍ）←（ｆ１（ｓ），…，ｆｍ（ｓ））を計算する。そして、鍵生成アルゴリズムＧｅｎは、（ｆ１（ｘ１，…，ｘｎ），…，ｆｍ（ｘ１，…，ｘｎ），ｙ）を公開鍵ｐｋに設定し、ｓを秘密鍵に設定する。
【００６９】
（証明者アルゴリズムＰ、検証者アルゴリズムＶ）
以下、図４を参照しながら、対話プロトコルの中で証明者アルゴリズムＰが実行する処理及び検証者アルゴリズムＶが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵ｓの情報を検証者に一切漏らさずに、「自身がｙ＝Ｆ（ｓ）を満たすｓを知っていること」を検証者に示す。一方、検証者は、証明者がｙ＝Ｆ（ｓ）を満たすｓを知っているか否かを検証する。なお、公開鍵ｐｋは、検証者に公開されているものとする。また、秘密鍵ｓは、証明者により秘密に管理されているものとする。以下、図４に示したフローチャートに沿って説明を進める。
【００７０】
工程＃１：
図４に示すように、まず、証明者アルゴリズムＰは、ランダムにベクトルｒ０，ｔ０∈Ｋｎ及びｅ０∈Ｋｍを生成する。次いで、証明者アルゴリズムＰは、ｒ１←ｓ−ｒ０を計算する。この計算は、秘密鍵ｓをベクトルｒ０によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｔ１←ｒ０−ｔ０を計算する。次いで、証明者アルゴリズムＰは、ｅ１←Ｆ（ｒ０）−ｅ０を計算する。
【００７１】
工程＃１（続き）：
次いで、証明者アルゴリズムＰは、ｃ０←Ｈ（ｒ１，Ｇ（ｔ０，ｒ１）＋ｅ０）を計算する。次いで、証明者アルゴリズムＰは、ｃ１←Ｈ（ｔ０，ｅ０）を計算する。次いで、証明者アルゴリズムＰは、ｃ２←Ｈ（ｔ１，ｅ１）を計算する。工程＃１で生成されたメッセージ（ｃ０，ｃ１，ｃ２）は、検証者アルゴリズムＶに送られる。
【００７２】
工程＃２：
メッセージ（ｃ０，ｃ１，ｃ２）を受け取った検証者アルゴリズムＶは、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムＶは、検証パターンの種類を表す３つの数値｛０，１，２｝の中から１つの数値を選択し、選択した数値を要求Ｃｈに設定する。この要求Ｃｈは証明者アルゴリズムＰに送られる。
【００７３】
工程＃３：
要求Ｃｈを受け取った証明者アルゴリズムＰは、受け取った要求Ｃｈに応じて検証者アルゴリズムＶに送る返答Ｒｓｐを生成する。Ｃｈ＝０の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ０，ｔ１，ｅ１）を生成する。Ｃｈ＝１の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ１，ｔ０，ｅ０）を生成する。Ｃｈ＝２の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ１，ｔ１，ｅ１）を生成する。工程＃３で生成された返答Ｒｓｐは、検証者アルゴリズムＶに送られる。
【００７４】
工程＃４：
返答Ｒｓｐを受け取った検証者アルゴリズムＶは、受け取った返答Ｒｓｐを利用して以下の検証処理を実行する。
【００７５】
Ｃｈ＝０の場合、検証者アルゴリズムＶは、ｃ１＝Ｈ（ｒ０−ｔ１，Ｆ（ｒ０）−ｅ１）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ２＝Ｈ（ｔ１，ｅ１）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【００７６】
Ｃｈ＝１の場合、検証者アルゴリズムＶは、ｃ０＝Ｈ（ｒ１，Ｇ（ｔ０，ｒ１）＋ｅ０）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ１＝Ｈ（ｔ０，ｅ０）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【００７７】
Ｃｈ＝２の場合、検証者アルゴリズムＶは、ｃ０＝Ｈ（ｒ１，ｙ−Ｆ（ｒ１）−Ｇ（ｔ１，ｒ１）−ｅ１）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ２＝Ｈ（ｔ１，ｅ１）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【００７８】
以上、３パス方式に係る効率的なアルゴリズムの構成例について説明した。
【００７９】
［２−２：並列化アルゴリズムの構成例（図５）］
次に、図５を参照しながら、図４に示した３パス方式のアルゴリズムを並列化する方法について説明する。なお、鍵生成アルゴリズムＧｅｎの構成については説明を省略する。
【００８０】
さて、上記の対話プロトコルを適用すれば、偽証が成功する確率を２／３以下に抑制することができる。従って、この対話プロトコルを２回実行すれば、偽証が成功する確率を（２／３）２以下に抑制することができる。さらに、この対話プロトコルをＮ回実行すると、偽証が成功する確率は（２／３）Ｎとなり、Ｎを十分に大きい数（例えば、Ｎ＝１４０）にすれば、偽証が成功する確率は無視できる程度に小さくなる。
【００８１】
対話プロトコルを複数回実行する方法としては、例えば、メッセージ、要求、返答のやり取りを逐次的に複数回繰り返す直列的な方法と、１回分のやり取りで複数回分のメッセージ、要求、返答のやり取りを行う並列的な方法とが考えられる。さらに、直列的な方法と並列的な方法とを組み合わせたハイブリッド型の方法も考えられる。ここでは、図５を参照しながら、３パス方式に係る上記の対話プロトコルを並列的に実行するアルゴリズム（以下、並列化アルゴリズム）について説明する。
【００８２】
工程＃１：
図５に示すように、まず、証明者アルゴリズムＰは、ｉ＝１〜Ｎについて以下の処理（１）〜処理（６）を実行する。
処理（１）：証明者アルゴリズムＰは、ランダムにベクトルｒ０ｉ，ｔ０ｉ∈Ｋｎ及びｅ０ｉ∈Ｋｍを生成する。
処理（２）：証明者アルゴリズムＰは、ｒ１ｉ←ｓ−ｒ０ｉを計算する。この計算は、秘密鍵ｓをベクトルｒ０ｉによりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｔ１ｉ←ｒ０ｉ＋ｔ０ｉを計算する。
処理（３）：証明者アルゴリズムＰは、ｅ１ｉ←Ｆ（ｒ０ｉ）−ｅ０ｉを計算する。
処理（４）：証明者アルゴリズムＰは、ｃ０ｉ←Ｈ（ｒ１ｉ，Ｇ（ｒ１ｉ，ｔ０ｉ）＋ｅ０ｉ）を計算する。
処理（５）：証明者アルゴリズムＰは、ｃ１ｉ←Ｈ（ｔ０ｉ，ｅ０ｉ）を計算する。
処理（６）：証明者アルゴリズムＰは、ｃ２ｉ←Ｈ（ｔ１ｉ，ｅ１ｉ）を計算する。
【００８３】
工程＃１（続き）
ｉ＝１〜Ｎについて上記の処理（１）〜処理（６）を実行した後、証明者アルゴリズムＰは、Ｃｍｔ←Ｈ（ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）を計算する。工程＃１で生成されたハッシュ値Ｃｍｔは、検証者アルゴリズムＶに送られる。このように、メッセージ（ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）をハッシュ値に変換してから検証者アルゴリズムＶに送ることで、通信量を削減することが可能になる。なお、証明者アルゴリズムＰは、（ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）を検証者アルゴリズムＶに送っても良い。
【００８４】
工程＃２：
ハッシュ値Ｃｍｔを受け取った検証者アルゴリズムＶは、ｉ＝１〜Ｎのそれぞれについて、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムＶは、ｉ＝１〜Ｎのそれぞれについて、検証パターンの種類を表す３つの数値｛０，１，２｝の中から１つの数値を選択し、選択した数値を要求Ｃｈｉに設定する。要求Ｃｈ１，…，ＣｈＮは、証明者アルゴリズムＰに送られる。
【００８５】
工程＃３：
要求Ｃｈ１，…，ＣｈＮを受け取った証明者アルゴリズムＰは、受け取った要求Ｃｈ１，…，ＣｈＮのそれぞれ応じて検証者アルゴリズムＶに送る返答Ｒｓｐ１，…，ＲｓｐＮを生成する。Ｃｈｉ＝０の場合、証明者アルゴリズムＰは、Ｒｓｐｉ＝（ｒ０ｉ，ｔ１ｉ，ｅ１ｉ，ｃ０ｉ）を生成する。Ｃｈｉ＝１の場合、証明者アルゴリズムＰは、Ｒｓｐｉ＝（ｒ１ｉ，ｔ０ｉ，ｅ０ｉ，ｃ２ｉ）を生成する。Ｃｈｉ＝２の場合、証明者アルゴリズムＰは、Ｒｓｐｉ＝（ｒ１ｉ，ｔ１ｉ，ｅ１ｉ，ｃ１ｉ）を生成する。
【００８６】
工程＃３で生成された返答Ｒｓｐ１，…，ＲｓｐＮは、検証者アルゴリズムＶに送られる。
【００８７】
工程＃４：
返答Ｒｓｐ１，…，ＲｓｐＮを受け取った検証者アルゴリズムＶは、受け取った返答Ｒｓｐ１，…，ＲｓｐＮを利用して以下の処理（１）〜処理（３）をｉ＝１〜Ｎについて実行する。但し、検証者アルゴリズムＶは、Ｃｈｉ＝０の場合に処理（１）を実行し、Ｃｈｉ＝１の場合に処理（２）を実行し、Ｃｈｉ＝２の場合に処理（３）を実行する。
【００８８】
処理（１）：Ｃｈｉ＝０の場合、検証者アルゴリズムＶは、Ｒｓｐｉから（ｒ０ｉ，ｔ１ｉ，ｅ１ｉ，ｃ０ｉ）を取り出す。次いで、検証者アルゴリズムＶは、ｃ１ｉ＝Ｈ（ｒ０ｉ−ｔ１ｉ，Ｆ（ｒ０ｉ）−ｅ１ｉ）を計算する。さらに、検証者アルゴリズムＶは、ｃ２ｉ＝Ｈ（ｔ１ｉ，ｅ１ｉ）を計算する。そして、検証者アルゴリズムＶは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【００８９】
処理（２）：Ｃｈｉ＝１の場合、検証者アルゴリズムＶは、Ｒｓｐｉから（ｒ１ｉ，ｔ０ｉ，ｅ０ｉ，ｃ２ｉ）を取り出す。次いで、検証者アルゴリズムＶは、ｃ０ｉ＝Ｈ（ｒ１ｉ，Ｇ（ｔ０ｉ，ｒ１ｉ）＋ｅ０ｉ）を計算する。さらに、検証者アルゴリズムＶは、ｃ１ｉ＝Ｈ（ｔ０ｉ，ｅ０ｉ）を計算する。そして、検証者アルゴリズムＶは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【００９０】
処理（３）：Ｃｈｉ＝２の場合、検証者アルゴリズムＶは、Ｒｓｐｉから（ｒ１ｉ，ｔ１ｉ，ｅ１ｉ，ｃ１ｉ）を取り出す。次いで、検証者アルゴリズムＶは、ｃ０ｉ＝Ｈ（ｒ１ｉ，ｙ−Ｆ（ｒ１ｉ）−Ｇ（ｔ１ｉ，ｒ１ｉ）−ｅ１ｉ）を計算する。さらに、検証者アルゴリズムＶは、ｃ２ｉ＝Ｈ（ｔ１ｉ，ｅ１ｉ）を計算する。そして、検証者アルゴリズムＶは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【００９１】
処理（１）〜処理（３）をｉ＝１〜Ｎについて実行した後、検証者アルゴリズムＶは、Ｃｍｔ＝Ｈ（ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗した場合に認証失敗を示す値０を出力する。
【００９２】
以上、３パス方式に係る効率的な並列化アルゴリズムの構成例について説明した。
【００９３】
＜３：電子署名方式への変形＞
次に、上記の公開鍵認証方式を電子署名方式へと変形する方法を紹介する。
【００９４】
公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させると、証明者のみが検証者を納得させられるという点において、電子署名方式のモデルと近似していることが容易に理解されよう。こうした考えに基づき、上述した公開鍵認証方式を電子署名方式へと変形する方法について説明する。
【００９５】
［３−１：３パスの公開鍵認証方式から電子署名方式への変形（図６）］
まず、３パスの公開鍵認証方式から電子署名方式への変形について説明する。図６に示すように、３パスの公開鍵認証方式から電子署名方式へ変形したアルゴリズムは、図５で説明した３パス方式のアルゴリズムを並列化したアルゴリズムの一部と同様に構成されている。図５の工程＃１〜工程＃４で表現される公開鍵認証方式のアルゴリズムは、図６に示すような署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒに変形される。
【００９６】
工程＃１：
図６に示すように、工程＃１は図５の工程＃１と同様である。
【００９７】
工程＃２：
次の工程＃２では、図５で検証者アルゴリズムＶに送ったＣｍｔ←Ｈ（ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）を署名検証アルゴリズムＶｅｒには送らずに、署名生成アルゴリズムＳｉｇは、Ｃｍｔと署名を付けたメッセージＭのハッシュ値Ｈ（Ｍ，ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）を計算して（Ｃｈ１，・・・，ＣｈＮ）とする。すなわち、署名生成アルゴリズムＳｉｇは、（Ｃｈ１，・・・，ＣｈＮ）←Ｈ（Ｍ，ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）を計算する。
【００９８】
工程＃３：
図６に示すように、工程＃３は図５の工程＃３と同様である。署名生成アルゴリズムＳｉｇは、Ｃｈ１，…，ＣｈＮのそれぞれ応じて署名検証アルゴリズムＶｅｒに送るσｉを生成する。Ｃｈｉ＝０の場合、署名生成アルゴリズムＳｉｇは、σｉ＝（ｒ０ｉ，ｔ１ｉ，ｅ１ｉ，ｃ０ｉ）を生成する。Ｃｈｉ＝１の場合、署名生成アルゴリズムＳｉｇは、σｉ＝（ｒ１ｉ，ｔ０ｉ，ｅ０ｉ，ｃ２ｉ）を生成する。Ｃｈｉ＝２の場合、署名生成アルゴリズムＳｉｇは、σｉ＝（ｒ１ｉ，ｔ１ｉ，ｅ１ｉ，ｃ１ｉ）を生成する。
【００９９】
工程＃３で生成されたＣｈ１，…，ＣｈＮ及びσ１，…，σＮは、署名検証アルゴリズムＶｅｒに送られる。また、同時に、署名を付けたメッセージＭも署名検証アルゴリズムＶｅｒに送られる。
【０１００】
工程＃４：
図６に示すように、工程＃４は基本的に図５の工程＃４と同様である。返答σ１，…，σＮを受け取った署名検証アルゴリズムＶｅｒは、受け取った返答σ１，…，σＮを利用して以下の処理（１）〜処理（３）をｉ＝１〜Ｎについて実行する。但し、署名検証アルゴリズムＶｅｒは、Ｃｈｉ＝０の場合に処理（１）を実行し、Ｃｈｉ＝１の場合に処理（２）を実行し、Ｃｈｉ＝２の場合に処理（３）を実行する。
【０１０１】
処理（１）：Ｃｈｉ＝０の場合、署名検証アルゴリズムＶｅｒは、σｉから（ｒ０ｉ，ｔ１ｉ，ｅ１ｉ，ｃ０ｉ）を取り出す。次いで、署名検証アルゴリズムＶｅｒは、ｃ１ｉ＝Ｈ（ｒ０ｉ−ｔ１ｉ，Ｆ（ｒ０ｉ）−ｅ１ｉ）を計算する。さらに、署名検証アルゴリズムＶｅｒは、ｃ２ｉ＝Ｈ（ｔ１ｉ，ｅ１ｉ）を計算する。そして、検証者アルゴリズムＶは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【０１０２】
処理（２）：Ｃｈｉ＝１の場合、署名検証アルゴリズムＶｅｒは、σｉから（ｒ１ｉ，ｔ０ｉ，ｅ０ｉ，ｃ２ｉ）を取り出す。次いで、署名検証アルゴリズムＶｅｒは、ｃ０ｉ＝Ｈ（ｒ１ｉ，Ｇ（ｔ０ｉ，ｒ１ｉ）＋ｅ０ｉ）を計算する。さらに、署名検証アルゴリズムＶｅｒは、ｃ１ｉ＝Ｈ（ｔ０ｉ，ｅ０ｉ）を計算する。そして、署名検証アルゴリズムＶｅｒは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【０１０３】
処理（３）：Ｃｈｉ＝２の場合、署名検証アルゴリズムＶｅｒは、σｉから（ｒ１ｉ，ｔ１ｉ，ｅ１ｉ，ｃ１ｉ）を取り出す。次いで、署名検証アルゴリズムＶｅｒは、ｃ０ｉ＝Ｈ（ｒ１ｉ，ｙ−Ｆ（ｒ１ｉ）−Ｇ（ｔ１ｉ，ｒ１ｉ）−ｅ１ｉ）を計算する。さらに、署名検証アルゴリズムＶｅｒは、ｃ２ｉ＝Ｈ（ｔ１ｉ，ｅ１ｉ）を計算する。そして、署名検証アルゴリズムＶｅｒは、（ｃ０ｉ，ｃ１ｉ，ｃ２ｉ）を保持する。
【０１０４】
処理（１）〜処理（３）をｉ＝１〜Ｎについて実行した後、署名検証アルゴリズムＶｅｒは、（Ｃｈ１，・・・，ＣｈＮ）＝Ｈ（Ｍ，ｃ０１，ｃ１１，ｃ２１，…，ｃ０Ｎ，ｃ１Ｎ，ｃ２Ｎ）の等号が成り立つか否かを検証する。署名検証アルゴリズムＶｅｒは、この検証が成功した場合に認証成功を示す値１を出力し、検証に失敗した場合に認証失敗を示す値０を出力する。
【０１０５】
以上説明したように、公開鍵認証方式のモデルにおける証明者を電子署名方式における署名者に対応させることで、公開鍵認証方式のアルゴリズムを電子署名方式のアルゴリズムへと変形することが可能になる。
【０１０６】
＜４．第１の実施形態＞
［４−１：第１の実施形態に係るシステムの概要］
図７は、第１の実施形態のシステムの概要を示す模式図である。まず、図７を参照して、本実施形態のシステムの概要について説明する。図７に示すように、本実施形態のシステムは、第１の情報処理装置１００及び第２の情報処理装置２００を有して構成されている。第１の情報処理装置１００は、例えばこのシステムを利用するユーザ自身が保有する装置である。また、第２の情報処理装置２００は、例えばユーザが保有していない外部の装置である。
【０１０７】
上述した電子署名方式による認証を行うために、本実施形態では、ＩＣカード３００に電子署名生成機能を持たせ、ユーザが持ち運ぶことにより、外部の第２の情報処理装置２００を使用する場合においても、安全に電子署名を生成できるようにする。ＩＣカード３００と第１の情報処理装置１００または第２の情報処理装置２００との情報のやり取りはフェリカポート、ＮＦＣデバイス等を使用する。
【０１０８】
図７に示す構成において、ユーザは、署名生成機能を持つＩＣカード３００を外部へ持ち運び、外部端末である第２の情報処理装置２００と連携して署名生成をすることができる。この際、計算の大部分を予め自分の端末である第１の情報処理装置１００で行い、所定の情報をＩＣカード３００に保存する。この際、メッセージに依存せず、セキュリティ上で問題のない演算は第１の情報処理装置１００側で行う。ＩＣカード３００に関連する処理は、ＩＣカード３００からのデータの読み取りのみとすることで、ＩＣカード３００で行う演算量を最小限に抑えることができる。従って、ＩＣカード３００の処理負荷を低減することができ、処理の高速化を達成することができる。
【０１０９】
［４−２：第１の実施形態に係るシステムの処理］
第１の実施形態では、図６に示したメッセージ（Ｍｓｇ）に依存しない部分（メッセージ非依存部分）のアルゴリズムを第１の情報処理装置１００で行う。図７に基づいて第１の情報処理装置１００で行う処理を説明すると、先ず、第１の情報処理装置１００では、秘密鍵ｘ∈Ｋｎを生成し、第１の情報処理装置１００内のメモリに保存する。次に、電子署名生成のために使用する情報を生成する。ここでは、図６で説明したｒ１,ｉ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２，ｉ（ｉ＝１,…,Ｎ）を生成する。生成した情報ｒ１,ｉ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２，ｉ（ｉ＝１,…,Ｎ）は、第１の情報処理装置１００とＩＣカード３００とがフェリカポート、ＮＦＣデバイス等を使用した近接通信を行うことにより、第１の情報処理装置１００からＩＣカード３００に転送される。なお、情報ｒ１,ｉ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２，ｉ（ｉ＝１,…,Ｎ）は、電子署名を生成する毎に更新される。
【０１１０】
このように、第１の情報処理装置１００で予めメッセージ非依存部分(メッセージ非依存部分の乱数生成、ＭＱ関数計算、ハッシュ値計算)を計算することで、ＩＣカード３００側でこれらを計算することが不要となる。従って、ＩＣカード３００を利用して電子署名を生成する場合においても、ＩＣカード３００の処理能力を増やす必要がなく、ＩＣカード３００の製造コストを抑えることが可能となる。更に、電子署名生成のための全体の処理時間に対して、メッセージ非依存部分生成の占める割合が殆どであるため、第１の情報処理装置１００側で予め演算を行なっておくことで、署名生成にかかる全体の時間も大幅に高速化することができる。
【０１１１】
次に、第２の情報処理装置２００とＩＣカード３００が通信を行うことにより、図６に示したメッセージＨに依存する部分（メッセージ依存部分）の情報を生成する。図８は、メッセージ依存部分の情報を生成する処理を示すシーケンス図である。このシーケンスにより、第２の情報処理装置２００では最終的に電子署名を生成する。
【０１１２】
先ず、ステップＳ１０において、第２の情報処理装置２００上でメッセージＭが生成される。次に、ステップＳ１２において、メッセージＭの署名生成開始命令が第２の情報処理装置２００からＩＣカード３００へ送信される。次のステップＳ１４では、署名生成に必要な情報ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）がＩＣカード３００から第２の情報処理装置２００へ転送される。
【０１１３】
次のステップＳ１６では、第２の情報処理装置２００が、署名生成用の情報Ｃｈ１，…，ＣｈＮを生成する。情報Ｃｈ１，…，ＣｈＮは、ハッシュ値Ｈ（Ｍ,ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）として生成される。次のステップＳ１８では、第２の情報処理装置２００が、署名生成用の情報Ｃｈ１，…，ＣｈＮをＩＣカード３００へ転送する。
【０１１４】
次のステップＳ２０では、ＩＣカード３００が、送信された情報Ｃｈ１，…，ＣｈＮをもとにＩＣカード３００内の値σｉを読み取る。次のステップＳ２２では、ＩＣカード３００が、ステップＳ２０で読み取った情報σｉを第２の情報処理装置２００へ転送する。次のステップＳ２４では、第２の情報処理装置２００が、電子署名σ１，・・・，σＮを入手する。ステップＳ２０，Ｓ２２において、ＩＣカード３００は、ｉ＝１，・・・，Ｎについて、Ｃｈｉのａ値に応じて、σｉ←（ｒ０,ｉ,ｔ１,ｉ,ｅ１,ｉ,ｃ０,ｉ），σｉ←（ｒ１，ｉ,ｔ１，ｉ,ｅ１，ｉ,c１，ｉ)，σｉ←（ｒ１,ｉ,ｔ０,ｉ,ｅ０,ｉ,ｃ２,ｉ）のいずれかを選択し、第２の情報処理装置２００へ送る。電子署名を取得した第２の情報処理装置２００は、メッセージＭとともに電子署名σ１，・・・，σＮ及びＣｈｉ，・・・，ＣｈＮを検証者の端末へ送ることで、図６で説明したように検証を受けることができる。
【０１１５】
なお、ＩＣカード３００の紛失時の対策として、カード使用限度を決め、毎回、ＩＣカード３００内のメモリから電子署名生成の１回分に相当する情報を消去するようにしても良い。または、電子署名生成の回数を記憶し、所定回数に到達した時点でＩＣカード３００内の情報を消去するようにしても良い。
【０１１６】
以上の処理によれば、ＩＣカード３００は、外部端末（第２の情報処理装置２００）側と連携して署名を生成するため、ＩＣカード３００側の計算負荷を抑えることができる。ＩＣカード３００側では、基本的にはデータ読み取り処理を行うのみで、ハッシュ値計算は外部端末（第１の情報処理装置１００）が代替的に行う。従って、ＩＣカード３００の処理負荷を最小限に抑えることができる。
【０１１７】
［４−３：第１の実施形態に係るシステム構成例］
図９は、第１の実施形態の構成を示す機能ブロック図である。図９に示すように、第２の情報処理装置２００は、メッセージ生成部２０２、ハッシュ値生成部２０４、情報保管部２０６、送受信部２０８を有して構成されている。また、ＩＣカード３００は、情報保管部（情報保持部）３０２、送受信部３０４を有して構成されている。なお、図９に示す構成は、回路（ハードウェア）、またはＣＰＵなどの中央演算処理装置とこれを機能させるためのプログラム（ソフトウェア）から構成することができる。図１２、図１４においても同様である。
【０１１８】
メッセージ生成部２０２は、図８のステップＳ１０において、メッセージＭを生成する。ハッシュ値生成部２０４は、図８のステップＳ１６において、署名生成用のハッシュ値を生成する。情報保管部２０６は、メッセージＭ、署名生成に必要な情報ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）、電子署名σ１，・・・，σＮ等を保管する情報記録部である。送受信部２０８は、図８のステップＳ１２において、署名生成命令をＩＣカード３００へ送信する。また、送受信部２０８は、ステップＳ１４において、署名生成に必要な情報ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）を受信する。また、送受信部２０８は、ステップＳ１８において、ハッシュ値Ｃｈ１，…，ＣｈＮをＩＣカード３００へ送信する。また、送受信部２０８は、ステップＳ２２において、電子署名σ１，・・・，σＮをＩＣカード３００から受信する。
【０１１９】
また、ＩＣカード３００の情報保管部３０２は、第１の情報処理装置１００によって生成されたメッセージ非依存部分の情報を保管（保持）する。送受信部３０４は、図８のステップＳ１４において、情報保管部３０２に保管された情報の中から、署名生成に必要な情報ｃ０,ｉ,  ｃ１,ｉ
,  ｃ２,ｉ  （ｉ＝１,…,Ｎ）を第２の情報処理装置２００へ送信する。また、送受信部３０４は、ステップＳ２０において、第２の情報処理装置２００から送信された情報に基づいて情報保管部３０２から読み取った情報σｉを、第２の情報処理装置２００へ送信する。
【０１２０】
［４−４：第１の実施形態の変形例］
図８に示す例では、ステップＳ２２において、σｉの一部としてｃｊ，ｉを第２の情報処理装置２００へ送信している。すなわち、ステップＳ２０において、σｉとして以下の値が読み取られている。
Ｆｏｒ  ｉ＝１,…,Ｎ
Ｉｆ  Ｃｈｉ＝０  ｔｈｅｎ  σｉ→（ｒ０,ｉ,ｔ１,ｉ,ｅ１,ｉ,ｃ０,ｉ）
Ｉｆ  Ｃｈｉ＝１  ｔｈｅｎ  σｉ→（ｒ１,ｉ,ｔ１,ｉ,ｅ１,ｉ,ｃ１,ｉ）
Ｉｆ  Ｃｈｉ＝２  ｔｈｅｎ  σｉ→（ｒ１,ｉ,ｔ０,ｉ,ｅ０,ｉ,ｃ２,ｉ）
【０１２１】
ここで、ｃｊ，ｉは、ステップＳ１４で第２の情報処理装置２００へ既に送っているため、ステップＳ２２ではｃｊ，ｉの送信を省略することもできる。
【０１２２】
このため図１３では、図８のステップＳ２２の代わりにステップＳ２６を設けている。ステップＳ２６では、σｉからｃｊ，ｉを除いたσｉ’＝σ１’，・・・，σＮ’をＩＣカード３００から第２の情報処理装置２００へ送信する。すなわち、ステップＳ２０では、以下の値が読み取られる。
Ｆｏｒ  ｉ＝１,…,Ｎ
Ｉｆ  Ｃｈｉ＝０  ｔｈｅｎ  σｉ→（ｒ０,ｉ,ｔ１,ｉ,ｅ１,ｉ）
Ｉｆ  Ｃｈｉ＝１  ｔｈｅｎ  σｉ→（ｒ１,ｉ,ｔ１,ｉ,ｅ１,ｉ）
Ｉｆ  Ｃｈｉ＝２  ｔｈｅｎ  σｉ→（ｒ１,ｉ,ｔ０,ｉ,ｅ０,ｉ）
【０１２３】
これにより、ステップＳ２６では、σｉ＝σ１，・・・，σＮを送信する図８のステップＳ２２よりも通信量を削減することができる。
【０１２４】
ステップＳ２６の処理によりσｉ’＝σ１’，・・・，σＮ’を受信した第２の情報処理装置２００は、ステップＳ２８においてσ１’，・・・，σＮ’のそれぞれにｃｊ，ｉを付加して電子署名σ１，・・・，σＮを生成する。ｃｊ，ｉは、ステップＳ１４でＩＣカード３００から受信した後、ステップＳ１５で情報保管部２０４に保管しておく。これにより、第２の情報処理装置２００は、ステップＳ２８で電子署名σ１，・・・，σＮを生成することができる。電子署名σ１，・・・，σＮの生成は、図９に示す電子署名生成部２１０にて行われる。
【０１２５】
以上説明したように第１の実施形態によれば、メッセージ非依存部分をユーザ自身の端末（第１の情報処理装置１００）で生成し、ＩＣカード３００へ転送することで、外部の端末（第２の情報処理装置２００）を用いて電子署名を生成することが可能となる。
【０１２６】
＜５．第２の実施形態＞
［５−１：第２の実施形態に係るシステムの概要］
次に、本開示の第２の実施形態について説明する。第１の実施形態では、第２の情報処理装置２００にてハッシュ値Ｃｈ１，…，ＣｈＮを生成していた（図８のステップＳ１６、図９のハッシュ値生成部２０４）。第２の実施形態は、第２の情報処理装置２００がハッシュ値生成機能を備えていない場合は、ハッシュ値生成機能を備えた他の装置でハッシュ値を代理計算することにより生成する。
【０１２７】
図１０は、第２の実施形態のシステムの概要を示す模式図である。まず、図１０を参照して、第２の実施形態のシステムの概要について説明する。図１０に示すように、第２の実施形態のシステムは、第１の情報処理装置１００及び第２の情報処理装置２００に加えて、サーバ４００を有して構成されている。第１の情報処理装置１００及び第２の情報処理装置２００の基本的な構成は第１の実施形態と同様であるが、第２の情報処理装置２００はハッシュ値生成機能を有していないものとする。
【０１２８】
第２の実施形態においても、第１の実施形態と同様に、図６に示したメッセージ（Ｍｓｇ）に依存しない部分（メッセージ非依存部分）のアルゴリズムを第１の情報処理装置１００で行う。第１の情報処理装置１００では、秘密鍵ｘ∈Ｋｎを生成し、第１の情報処理装置１００内のメモリに保存する。次に、電子署名生成のために使用する情報を生成する。生成した情報ｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０，ｉ,ｅ１，ｉ,ｅ０，ｉ,ｃ０，ｉ,ｃ１，ｉ,c２，ｉ(i＝１,…,Ｎ)は、第１の情報処理装置１００とＩＣカード３００とが近接通信を行うことにより、第１の情報処理装置１００からＩＣカード３００に転送される。
【０１２９】
また、第１の情報処理装置１００は、ハッシュ値を計算するための情報をサーバ４００へ送信する。具体的には、第１の情報処理装置１００は、ハッシュ値を計算するための情報として、ＩＤ番号とｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）をサーバ４００へ送信する。ＩＤ番号とｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）はサーバ４００内に保存される。ここで、ＩＤ番号は、ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）に対応した値であり、サーバ４００はＩＤ番号に基づいて、対応するｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）を抽出することができる。
【０１３０】
第２の情報処理装置２００は、サーバ４００と協働してメッセージ非依存部分を作成する。この際、ＩＣカード３００内に保存された情報に基づいて、第２の情報処理装置２００が作成した文書・データ等（メッセージＭ）への署名を、第２の情報処理装置２００とサーバ４００が連携して生成する。以下、詳細に説明する。
【０１３１】
［５−２：第２の実施形態に係るシステムの処理］
図１１に基づいて、第２の実施形態の処理について説明する。図１１は、第２の実施形態の処理を示すシーケンス図であって、メッセージ依存部分の情報を生成する処理を示すシーケンス図である。先ず、ステップＳ３０では、第２の情報処理装置２００上でメッセージＭが生成される。次に、ステップＳ３２において、メッセージＭの署名生成開始命令が第２の情報処理装置２００からＩＣカード３００へ送信される。
【０１３２】
次のステップＳ３４では、ＩＣカード３００から第２の情報処理装置２００へ署名生成用ＩＤ番号が送付される。署名生成用ＩＤ番号は、ｃ０，１，・・・，ｃ２，ｎを識別するために送付される。次のステップＳ３６では、ＩＤ番号が第２の情報処理装置２００からサーバ４００へ送信される。
【０１３３】
上述したように、サーバ４００は、第１の情報処理装置１００から送信されたＩＤ番号と、情報ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）を既に保管している。
【０１３４】
次のステップＳ３８では、サーバ４００が第２の情報処理装置２００から受信したＩＤ番号を確認する。次のステップＳ４０では、メッセージの送付命令がサーバ４００から第２の情報処理装置２００へ送信される。次のステップＳ４２では、メッセージＭが第２の情報処理装置２００からサーバ４００へ送信される。
【０１３５】
次のステップＳ４４では、サーバ４００が署名生成用の情報（ハッシュ値Ｃｈ１，…，ＣｈＮ）を生成する。ここで、サーバ４００はステップＳ３８で確認したＩＤ番号に対応するｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）をメモリから抽出し、Ｃｈ１，…，ＣｈＮとしてハッシュ値Ｈ（Ｍ,ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）を求める。次のステップＳ４６では、サーバ４００が、署名生成用の情報Ｃｈ１，…，ＣｈＮを第２の情報処理装置２００へ送信する。次のステップＳ４８では、第２の情報処理装置２００が署名生成用の情報Ｃｈ１，…，ＣｈＮをＩＣカード３００へ転送する。
【０１３６】
次のステップＳ５０では、ＩＣカード３００が、送信された情報Ｃｈ１，…，ＣｈＮをもとに内部に記録された値を読み取る。次のステップＳ５２では、ＩＣカード３００が、読み取った情報（電子署名σ１，・・・，σＮ）を第２の情報処理装置２００へ転送する。ステップＳ５０，Ｓ５２において、ＩＣカード３００は、ｉ＝１，・・・，Ｎについて、Ｃｈｉのａ値に応じて、σｉ←（ｒ０,ｉ,ｔ１,ｉ,ｅ１,ｉ,ｃ０,ｉ），σｉ←（ｒ１，ｉ,ｔ１，ｉ,ｅ１，ｉ,c１，ｉ)，σｉ←（ｒ１,ｉ,ｔ０,ｉ,ｅ０,ｉ,ｃ２,ｉ）のいずれかを選択し、第２の情報処理装置２００へ送る。次のステップＳ５４では、第２の情報処理装置２００が、電子署名σ１，・・・，σＮを入手する。電子署名を取得した第２の情報処理装置２００は、メッセージＭとともに電子署名σ１，・・・，σＮ及びＣｈｉ，・・・，ＣｈＮを検証者の端末へ送ることで、検証を受けることができる。
【０１３７】
［５−３：第２の実施形態に係るシステム構成例］
図１２は、第２の実施形態の構成を示す機能ブロック図である。図１２に示すように、第２の情報処理装置２００は、メッセージ生成部２０２、情報保管部２０６、送受信部２０８を有して構成されている。また、ＩＣカード３００は、情報保管部３０２、送受信部３０４を有して構成されている。また、サーバ４００は、ＩＤ番号確認部４０２、ハッシュ値生成４０４、情報保管部４０６、送受信部４０８を有して構成されている。
【０１３８】
図１２のメッセージ生成部２０２は、図１１のステップＳ３０において、メッセージＭを生成する。情報保管部２０６は、メッセージＭ、署名生成に必要な情報Ｃｈ１，…，ＣｈＮ、及び電子署名σ１，・・・，σＮ等を保管する。送受信部２０８は、図１１のステップＳ３２において、署名生成命令をＩＣカード３００へ送信する。また、送受信部２０８は、ステップＳ３４においてＩＤ番号を受信し、ステップＳ３６においてＩＤ番号を送信する。また、送受信部２０８は、ステップＳ４０においてメッセージ送付命令を受信し、ステップＳ４２においてメッセージＭを送信する。また、送受信部２０８は、ステップＳ４６において、署名生成用の情報Ｃｈ１，…，ＣｈＮを受信し、ステップＳ４８において署名生成用の情報Ｃｈ１，…，ＣｈＮをＩＣカード３００へ送信する。また、送受信部２０８は、ステップＳ５２において、電子署名σ１，・・・，σＮを受信する。
【０１３９】
以上説明したように第２の実施形態によれば、第２の情報処理装置２００がハッシュ値生成機能を備えていない場合は、サーバ４００にてハッシュ値を生成することができる。従って、外部の端末である第２の情報処理装置２００が特別な機能を有していない場合であっても、電子署名を入手することが可能となる。
【０１４０】
＜６．第３の実施形態＞
［６−１：第３の実施形態に係るシステムの概要］
次に、本開示の第３の実施形態について説明する。第３の実施形態の基本的なシステム構成は、図７に示した第１の実施形態と同様である。第３の実施形態は、第１の実施形態の第１の情報処理装置１００がＩＣカード３００に保存する情報について、全ての情報をセキュア領域に保存せず、秘密鍵に関する情報のみセキュア領域に保存して保護する。これにより、セキュアなメモリ領域のサイズを限定することができ、ＩＣカード３００の製造コストを削減することができる。
【０１４１】
第３の実施形態においても、図６に示したメッセージ（Ｍｓｇ）に依存しない部分（メッセージ非依存部分）のアルゴリズムを第１の情報処理装置１００で行う。生成した情報ｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０，ｉ,ｅ１，ｉ,ｅ０，ｉ,ｃ０，ｉ,ｃ１，ｉ,c２，ｉ(i＝１,…,Ｎ)は、第１の情報処理装置１００とＩＣカード３００とが近接通信を行うことにより、第１の情報処理装置１００からＩＣカード３００に転送される。
【０１４２】
第１の実施形態では、情報ｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０，ｉ,ｅ１，ｉ,ｅ０，ｉ,ｃ０，ｉ,ｃ１，ｉ,c２，ｉ(i＝１,…,Ｎ)の全てが情報保管部３０２のセキュア領域に保管される。一方、第３の実施形態では、情報ｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０，ｉ,ｅ１，ｉ,ｅ０，ｉ,ｃ０，ｉ,ｃ１，ｉ,c２，ｉ(i＝１,…,Ｎ)のうち、秘密鍵に関係のあるｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０(i＝１,…,Ｎ)のみをセキュア領域に保管する。
【０１４３】
［６−２：第３の実施形態に係るシステムの構成例］
図１４は、第３の実施形態の構成を示す機能ブロック図である。図９の構成と比較すると、ＩＣカード３００の情報保管部３０２が２つに分割され、ＩＣカード３００は情報保管部（セキュア領域）３０２ａと情報保管部（非セキュア領域）３０２ｂを備えている。非セキュア領域２０６ｂが通常のメモリ領域であるのに対し、セキュア領域３０２ａは、外部からの攻撃や侵入、盗聴、改ざんなどの要因から保護された領域である。情報ｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０，ｉ,ｅ１，ｉ,ｅ０，ｉ,ｃ０，ｉ,ｃ１，ｉ,c２，ｉ(i＝１,…,Ｎ)のうち、秘密鍵に関係のあるｒ１，ｉ,ｒ０，ｉ,ｔ１，ｉ,ｔ０(i＝１,…,Ｎ)のみが情報保管部（セキュア領域）３０２ａに保管される。他の情報は、情報保管部（非セキュア領域）３０２ｂに保管される。これにより、秘密鍵の漏洩を確実に抑止するとともに、セキュアなメモリ領域のサイズを最小限に抑えることができる。
【０１４４】
以上説明したように第３の実施形態によれば、ＩＣカード３００が備えるメモリ領域のうち、セキュアな領域を最小限に抑えることができる。従って、ＩＣカード３００の製造コストを低減することが可能となる。
【０１４５】
＜７．第４の実施形態＞
［７−１：第４の実施形態に係るシステムの概要］
次に、本開示の第４の実施形態について説明する。第１の実施形態では、図８のステップＳ１４において、ＩＣカード３００から第２の情報処理装置２００へｃｉ，ｊ＝ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）＝ｃ０，１，ｃ１，１，ｃ２，１，・・・，ｃ０，Ｎ，ｃ１，Ｎ，ｃ２，Ｎを送信する。そして、ステップＳ１６では、第２の情報処理装置２００が、ｃｉ，ｊに基づいてハッシュ値を計算している。第４の実施形態では、ＭＤ型ハッシュ関数の特徴を利用して、ｃｉ，ｊについて予め圧縮した情報を送ることで、ステップＳ１４における通信量を削減し、且つ、ステップＳ１６の計算量を削減する。
【０１４６】
図１５は、ＭＤ型（Ｍｅｒｋｌｅ−Ｄａｍｇａｒｄ  ｃｏｎｓｔｒｕｃｔｉｏｎ）ハッシュ関数を示す模式図である。図１５に示すハッシュ関数は、例えばＦＩＰＳ（Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ Ｓｔａｎｄａｒｄ（ｓ）：連邦情報処理規格）のＰｕｂｌｉｃａｔｉｏｎ  １８０−３によるＳＨＡ−１／２２４／２５６／３８４／５１２等に相当するものである。このタイプのハッシュ関数は、入力メッセージ（任意長のデータｍ）に対し、先頭から逐次的に圧縮していく特徴を有している。図８のステップＳ１６で算出されるハッシュ値を変形すると、以下の式で表すことができる。
Ｈ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ,Ｍ）＝ｇ（ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）,Ｍ）
【０１４７】
上式の右辺において、ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）は、ｃｉ，ｊ＝ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）に関するハッシュ値であり、メッセージＭを入手していない状態であっても予め計算することができる。このため、第４の実施形態では、ｃｉ，ｊに関するｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ ）を第１の情報処理装置１００で予め圧縮計算しておく。そして、第２の情報処理装置２００において、メッセージＭと合わせた最終的なハッシュ値ｇ（ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ ）,Ｍ）を計算する。これにより、ステップＳ１６の計算量を大幅に削減することができる。
【０１４８】
第４の実施形態のシステムの概要は、図７に示した第１の実施形態と同様である。第４の実施形態では、図６に示したメッセージＨに依存しない部分（メッセージ非依存部分）のアルゴリズムを第１の情報処理装置１００で行い、第１の実施形態と同様に情報ｒ１,ｉ ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ(ｉ＝１,…,Ｎ)を生成する。
【０１４９】
第１の実施形態では、生成した情報ｒ１,ｉ ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ(ｉ＝１,…,Ｎ)をＩＣカード３００へ転送した。これに対し、第４の実施形態では、第１の情報処理装置１００は、ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ（ｉ＝１,…,Ｎ）を元に、情報ｋ（ｃ０，１,…,ｃ２,Ｎ）を生成する。そして、第１の情報処理装置１００が生成した情報ｒ１,ｉ ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ(ｉ＝１,…,Ｎ)、及びｋ（ｃ０，１,…,ｃ２,Ｎ）は、第１の情報処理装置１００とＩＣカード３００とが近接通信を行うことにより、第１の情報処理装置１００からＩＣカード３００に転送される。
【０１５０】
図１６は、第４の実施形態の処理を示すシーケンス図であって、メッセージ依存部分の情報を生成する処理を示している。第１の実施形態の図８と比較すると、ＩＣカード３００には、情報ｒ１,ｉ ,ｒ０,ｉ,ｔ１,ｉ,ｔ０,ｉ,ｅ１,ｉ,ｅ０,ｉ,ｃ０,ｉ,ｃ１,ｉ,ｃ２,ｉ(ｉ＝１,…,Ｎ)に加えて、更に情報ｋ（ｃ０，１,…,ｃ２,Ｎ）が予め保存されている。
【０１５１】
また、図１６では、図８のステップＳ１４の代わりにステップＳ１５の処理が行われる。ステップＳ１５では、署名生成に必要な情報としてｋ（ｃ０，１,…,ｃ２,Ｎ）が、ＩＣカード３００から第２の情報処理装置２００へ送信される。これにより、ｃ０，１, …,ｃ２,Ｎを送信する図８のステップＳ１４に比べて通信量を大幅に削減することができる。
【０１５２】
また、図１６では、図８のステップＳ１６の代わりにステップＳ１７を設けている。ステップＳ１７では、ｇ（ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ ）,Ｍ）を計算することにより、ハッシュ値Ｈ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ,Ｍ）を求める。これにより、ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）はステップＳ１５でＩＣカード３００から第２の情報処理装置２００へ転送されているため、ハッシュ値Ｈ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ,Ｍ）を求める際のステップＳ１７の計算量を、図８のステップＳ１６の計算量よりも削減することが可能である。
【０１５３】
以上説明したように第４の実施形態によれば、ｃｉ，ｊに関するハッシュ値Ｈを途中まで第１の情報処理装置１００で実行しておき、ｋ（ｃ０，１,ｃ１，１,ｃ２，１,…,ｃ０,Ｎ,ｃ１,Ｎ,ｃ２,Ｎ）としてＩＣカード３００に保存しておく。これにより、ＩＣカード３００から第２の情報処理装置２００へ署名生成に必要な情報を送る際の通信量を削減することができ、また第２の情報処理装置２００の計算量を削減することが可能となる。
【０１５４】
＜８：認証プロトコルについて＞
本実施形態では、上述したように、ユーザ認証の方式として、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式を例に挙げて説明した。ユーザ認証プロトコルとしては、これに限定されるものではなく、図６に例示したような、メッセージＭに依存しない部分と、メッセージに依存する部分とに分離される認証プロトコルであれば、他のプロトコルも広く使用可能である。なお、認証プロトコルとは、上述したように、公開鍵ｖに対応する秘密鍵ｓを持っていることを、秘密鍵ｓを明かすことなく証明する暗号技術である。従って、事前に公開鍵ｖをサーバ２００に登録しておくことで、サーバ２００がユーザを認証する際に利用することができる。
【０１５５】
他の認証プロトコルとしては、例えばＥＣＤＳＡを使用することができる。また、他の認証プロトコルとして、Ｓｙｎｄｒｏｍｅ  ｄｅｃｏｄｉｎｇ  ｐｒｏｂｌｅｍに基づく認証プロトコルも使用することができる（Ａ  ｎｅｗ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｐｕｂｌｉｃ  ｋｅｙ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ.  ＣＲＹＰＴＯ １９９３,  ＩＥＥＥ  Ｔｒａｎｓ.  ｏｎ  ＩＴ  １９９６)。これらの認証プロトコルにおいても、メッセージＭに依存しない部分と、メッセージに依存する部分とが分離されるため、上記と同様に電子署名を生成することが可能である。
【０１５６】
＜９：ハードウェア構成例（図１７）＞
上記の各アルゴリズムは、例えば、図１７に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図１７に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０１５７】
図１７に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０１５８】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０１５９】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。
【０１６０】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０１６１】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０１６２】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０１６３】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０１６４】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０１６５】
以上で述べた技術内容は、例えば、ＰＣ、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、１台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。
【０１６６】
以上、添付図面を参照しながら本開示の好適な実施形態について詳細に説明したが、本開示の技術的範囲はかかる例に限定されない。本開示の技術分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本開示の技術的範囲に属するものと了解される。
【０１６７】
なお、以下のような構成も本開示の技術的範囲に属する。
（１）電子署名が付加されるメッセージを生成するメッセージ生成部と、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、
を備える、情報処理装置。
（２）前記メッセージ依存情報を生成するための生成用情報を受信する生成用情報受信部と、
前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成部と、
を更に備える、前記（１）に記載の情報処理装置。
（３）前記生成用受信部が受信した前記生成用情報と、前記電子署名に関する情報とに基づいて電子署名を生成する電子署名生成部を更に備える、前記（２）に記載の情報処理装置。
（４）前記生成用情報と前記メッセージとから前記メッセージ依存情報を生成するメッセージ依存情報生成装置から前記メッセージ依存情報を受信するメッセージ依存情報受信部を備える、前記（１）に記載の情報処理装置。
（５）前記生成用情報受信部は、前記生成用情報をハッシュ値として受信し、
前記メッセージ依存情報生成部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として前記メッセージ依存情報を生成する、前記（２）に記載の情報処理装置。
（６）前記他装置はＩＣカードである、前記（１）〜（５）に記載の情報処理装置。
（７）前記電子署名は、ＭＱプロトコルによる電子署名である、前記（１）〜（６）に記載の情報処理装置。
（８）電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持する情報保持部と、
前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信するメッセージ依存情報受信部と、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、
を備える、情報処理装置。
（９）前記メッセージ非依存情報送信部は、前記メッセージ非依存情報のうち、メッセージ依存情報を生成するための生成用情報を送信する生成用情報送信部を含み、
前記メッセージ依存情報受信部は、前記生成用情報と前記メッセージとから生成された前記メッセージ依存情報を受信する、前記（８）に記載の情報処理装置。
（１０）前記電子署名情報送信部は、前記メッセージ非依存情報から抽出して得た前記電子署名に関する情報から、前記生成用情報を除いた部分を送信する、前記（９）に記載の情報処理装置。
（１１）前記生成用情報送信部は、前記生成用情報の代わりに、前記生成用情報に対応する識別番号を送信し、
前記メッセージ依存情報受信部は、メッセージ依存情報生成装置が前記識別番号に対応して保管する前記生成用情報と前記メッセージとから生成したメッセージ依存情報を受信する、前記（９）に記載の情報処理装置。
（１２）前記情報保持部は、前記メッセージ非依存情報のうち前記電子署名のアルゴリズムの秘密鍵に関連する情報を保持するセキュア領域と、前記メッセージ非依存情報のうち前記秘密鍵に関連しない情報を保持する非セキュア領域と、を有する、前記（８）〜（１１）に記載の情報処理装置。
（１３）前記生成用情報送信部は、前記生成用情報をハッシュ値として送信し、
前記メッセージ依存情報受信部は、前記生成用情報の前記ハッシュ値と前記メッセージとのハッシュ値として生成された前記メッセージ依存情報を受信する、前記（９）に記載の情報処理装置。
（１４）電子署名が付加されるメッセージを生成するメッセージ生成部と、他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信するメッセージ依存情報送信部と、前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する電子署名情報受信部と、を備える、情報処理装置と、
前記メッセージ非依存情報を保持する情報保持部と、前記メッセージ非依存情報の少なくとも一部を送信するメッセージ非依存情報送信部と、前記メッセージ非依存情報と前記メッセージとから生成された前記メッセージ依存情報を受信するメッセージ依存情報受信部と、前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する電子署名情報送信部と、を備える、ＩＣカードと、
を備える、情報処理システム。
（１５）電子署名が付加されるメッセージを生成することと、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信することと、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信することと、
を備える、情報処理方法。
（１６）電子署名が付加されるメッセージを生成する手段、
他装置から受信したメッセージ非依存情報の少なくとも一部と前記メッセージとから生成されたメッセージ依存情報を前記他装置へ送信する手段、
前記メッセージ依存情報に基づいて前記他装置が前記メッセージ非依存情報から抽出して得た電子署名に関する情報を受信する手段、
としてコンピュータを機能させるためのプログラム。
（１７）電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持することと、
前記メッセージ非依存情報の少なくとも一部を送信することと、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信することと、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信することと、
を備える、情報処理方法。
（１８）電子署名が付加されるメッセージに依存しないメッセージ非依存情報を保持する手段、
前記メッセージ非依存情報の少なくとも一部を送信する手段、
前記メッセージ非依存情報と前記メッセージとから生成されたメッセージ依存情報を受信する手段、
前記メッセージ依存情報に基づいて前記メッセージ非依存情報から抽出して得た電子署名に関する情報を送信する手段、
としてコンピュータを機能させるためのプログラム。
【符号の説明】
【０１６８】
２００    第２の情報処理装置
２０２    メッセージ生成部
２０４    ハッシュ値生成部
２０８    送受信部
３００    ＩＣカード
３０２    情報保管部（情報保持部）
３０４    送受信部
３０２ａ    セキュア領域
３０２ｂ    非セキュア領域
４００    サーバ
【図１】
2014048414.tif 000012
【図２】
2014048414.tif 000013
【図３】
2014048414.tif 000014
【図４】
2014048414.tif 000015
【図５】
2014048414.tif 000016
【図６】
2014048414.tif 000017
【図７】
2014048414.tif 000018
【図８】
2014048414.tif 000019
【図９】
2014048414.tif 000020
【図１０】
2014048414.tif 000021
【図１１】
2014048414.tif 000022
【図１２】
2014048414.tif 000023
【図１３】
2014048414.tif 000024
【図１４】
2014048414.tif 000025
【図１５】
2014048414.tif 000026
【図１６】
2014048414.tif 000027
【図１７】
2014048414.tif 000028