(57)【要約】【課題】代用検証者が生成する代用検証鍵の推定に十分な情報を署名者に知られずに署名者との対話の中で代用検証鍵を生成することが可能な情報処理装置を提供すること。【解決手段】第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供部と、他装置により第１部分情報及び第１署名鍵ＫＳを用いて生成され、第１署名鍵ＫＳを特定不可能であり、かつ、第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得部と、第１部分情報及び第２部分情報に基づいて第２検証鍵ＫＶ’を生成する第２検証鍵生成部とを備える情報処理装置が提供される。【選択図】図１４
2010278482.tif 000002
【特許請求の範囲】
【請求項１】
第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供部と、
前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得部と、
前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成部と、
を備える、情報処理装置。
【請求項２】
前記第１署名鍵ＫＳはＮ１個（Ｎ１≧２）のパラメータを含んで成り、
前記第２部分情報取得部は、前記第１部分情報を用いて生成されるパラメータ及び前記第１署名鍵ＫＳに含まれるＮ１個のパラメータを用いて生成され、当該第１署名鍵ＫＳに含まれる個々のパラメータを特定不可能な前記第２部分情報を取得する、請求項１に記載の情報処理装置。
【請求項３】
前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、
前記第１部分情報提供部は、前記第１部分情報として前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータを提供する、請求項２に記載の情報処理装置。
【請求項４】
前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、
前記第１部分情報提供部は、前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータ、及び当該Ｍ２個のパラメータを除く（Ｎ２−Ｍ２）個のパラメータのハッシュ値を前記第１部分情報として提供する、請求項２に記載の情報処理装置。
【請求項５】
前記第２部分情報が生成される際に前記第１部分情報に対して前記他装置が生成した乱数に基づく所定の演算処理が施されている場合、前記第２部分情報取得部は、前記第２部分情報と共に前記他装置が生成した乱数を取得し、
前記第２検証鍵生成部は、前記第１部分情報、前記第２部分情報、及び前記乱数に基づいて前記第２検証鍵ＫＶ’を生成する、請求項１に記載の情報処理装置。
【請求項６】
対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳが格納された記憶部と、
前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得部と、
前記第１部分情報取得部で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成部と、
前記第１部分情報を提供した他装置に対し、前記第２部分情報生成部で生成された第２部分情報を提供する第２部分情報提供部と、
を備える、情報処理装置。
【請求項７】
前記第１署名鍵ＫＳはＮ１個（Ｎ１≧２）のパラメータを含んで成り、
前記第２部分情報生成部は、前記第１部分情報を用いて生成されるパラメータ及び前記第１署名鍵ＫＳに含まれるＮ１個のパラメータを利用し、当該第１署名鍵ＫＳに含まれる個々のパラメータを特定不可能な前記第２部分情報を生成する、請求項６に記載の情報処理装置。
【請求項８】
前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、
前記第１部分情報取得部は、前記第１部分情報として前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータを取得する、請求項７に記載の情報処理装置。
【請求項９】
前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、
前記第１部分情報取得部は、前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータ、及び当該Ｍ２個のパラメータを除く（Ｎ２−Ｍ２）個のパラメータのハッシュ値を前記第１部分情報として取得する、請求項７に記載の情報処理装置。
【請求項１０】
乱数を発生させる乱数発生器と、
前記乱数発生器で発生させた乱数を用いて前記第１部分情報に所定の演算処理を施す演算処理部と、
をさらに備え、
前記第２部分情報生成部は、前記演算処理部で所定の演算処理が施された第１部分情報及び前記第１署名鍵ＫＳを利用して前記第２部分情報を生成し、
前記第２部分情報提供部は、前記第２部分情報と共に前記演算処理部で用いた乱数を前記他装置に提供する、請求項６に記載の情報処理装置。
【請求項１１】
対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳが格納された記憶部と、
前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を第２の情報処理装置から取得する第１部分情報取得部と、
前記第１部分情報取得部で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成部と、
前記第１部分情報を提供した前記第２の情報処理装置に対し、前記第２部分情報生成部で生成された第２部分情報を提供する第２部分情報提供部と、
を有する、第１の情報処理装置と；
前記第１の情報処理装置に対し、前記第１部分情報を提供する第１部分情報提供部と、
前記第２部分情報を取得する第２部分情報取得部と、
前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成部と、
を有する、第２の情報処理装置と；
を含む、電子署名生成システム。
【請求項１２】
第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供ステップと、
前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得ステップと、
前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成ステップと、
を含む、電子署名用の鍵生成方法。
【請求項１３】
対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得ステップと、
前記第１部分情報取得ステップで取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成ステップと、
前記第１部分情報を提供した他装置に対し、前記第２部分情報生成ステップで生成された第２部分情報を提供する第２部分情報提供ステップと、
を含む、情報処理方法。
【請求項１４】
第２の情報処理装置が、第１の情報処理装置に対し、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供ステップと、
第１の情報処理装置が、
前記第１部分情報を第２の情報処理装置から取得する第１部分情報取得ステップと、
前記第１部分情報取得ステップで取得した前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成ステップと、
前記第１部分情報を提供した第２の情報処理装置に対し、前記第２部分情報生成ステップで生成した第２部分情報を提供する第２部分情報提供ステップと、
前記第２の情報処理装置が、
前記第２部分情報を取得する第２部分情報取得ステップと、
前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成ステップと、
を含む、電子署名用の鍵生成方法。
【請求項１５】
第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供機能と、
前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得機能と、
前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成機能と、
をコンピュータに実現させるためのプログラム。
【請求項１６】
対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得機能と、
前記第１部分情報取得機能で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成機能と、
前記第１部分情報を提供した他装置に対し、前記第２部分情報生成機能で生成された第２部分情報を提供する第２部分情報提供機能と、
をコンピュータに実現させるためのプログラム。
【請求項１７】
前記他装置は認証局サーバであり、
自装置を特定するためのＩＤ情報を前記他装置に通知するＩＤ通知部をさらに備え、
前記第１部分情報提供部、前記第２部分情報取得部、及び前記第２検証鍵生成部を用い、前記ＩＤ通知部による通知を受けて前記他装置により生成された前記ＩＤ情報を含む電子文書ｍＩＤ、及び当該電子文書ｍＩＤに対して前記第１署名鍵ＫＳを用いて生成された電子署名σＩＤを受理する第２検証鍵ＫＶ’を生成し、前記第２検証鍵ＫＶ’の正当性を証明するための電子証明書として当該電子文書ｍＩＤ及び電子署名σＩＤを利用する、請求項１に記載の情報処理装置。
【請求項１８】
自装置は委任者の電子署名を代理する代理人が利用する代理人端末であり、
前記他装置は前記委任者が利用する委任者端末であり、
前記第１部分情報提供部、前記第２部分情報取得部、及び前記第２検証鍵生成部を用い、前記委任者が前記代理人に委譲する署名権限の内容を少なくとも含む電子文書ｍｗ、及び当該電子文書ｍｗに対して前記第１署名鍵ＫＳを用いて生成された電子署名σｗを受理する第２検証鍵ＫＶ’を生成し、前記第２検証鍵ＫＶ’が前記委任者に認められたものであることを証明するための証明書として当該電子文書ｍｗ及び電子署名σｗを利用する、請求項１に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、電子署名生成システム、電子署名用の鍵生成方法、情報処理方法、及びプログラムに関する。
【背景技術】
【０００２】
通常、文書の作成者を証明するためには、その文書に作成者が署名や捺印等（以下、署名）を施す。この署名は、署名した者が当該文書の記載内容に対して責任を負うことを明示するものである。紙文書の場合、文書の作成者が手で署名を行う。一方、電子文書の場合、電子データに印鑑を押したり、署名者が手書きで署名を行うことが難しい。そのため、電子署名と呼ばれるデータを電子文書に付し、その電子署名により署名者を一意に特定する方法が用いられる。近年、様々な文書が電子化されており、電子署名の重要性が増している。こうした状況の中で、電子署名の偽造に対する耐性が問題となることが多い。紙文書に付される署名の場合も同様であるが、電子データの方が容易に複製可能な分だけ注意が必要になるのである。
【０００３】
電子署名の仕組みとしては、例えば、ＥｌＧａｍａｌ署名方式が良く知られている。この方式は、離散対数問題の困難性に基づくものである。まず、署名者は、電子署名を生成するための署名鍵と、電子署名の正当性を検証するための検証鍵とを生成する。さらに、署名者は、検証鍵を公開する。そして、署名鍵及び電子文書を用いて電子署名を生成し、電子文書と共に電子署名を検証者に提供する。そのため、検証者は、公開されている検証鍵を用いて電子署名を検証することができる。ＥｌＧａｍａｌ署名方式の場合、検証鍵から署名鍵や電子署名を生成しようとすると、計算量的に解くことが困難な離散対数問題を解く必要が生じる。電子署名から署名鍵を生成しようとした場合についても同様である。これらの困難性が署名の偽造を防止している。
【０００４】
しかしながら、何らかの理由で署名鍵が第３者に露呈してしまうと、第３者が自由に電子署名を偽造できてしまう。従って、署名鍵が露呈した場合、露呈した署名鍵で生成された電子署名は、真の署名者のものであるか、第３者が偽造したものであるか区別できなくなる。紙文書に付された署名の場合、複製したものと原本とは比較的容易に判別できるが、電子データの場合には全く同じものであるために区別できない。そのため、署名鍵の露呈が発覚した段階で電子署名、署名鍵、及び検証鍵を無効にする対策が採られる。このとき、その電子署名が付された電子文書も実質的に無効になってしまう。
【０００５】
このような署名鍵の露呈に伴う被害を低減させるために様々な仕組みが考案されている。例えば、下記の特許文献１には、期間毎に署名鍵を設定し、各期間で生成された電子署名に対してのみ各署名鍵が有効になるようにする方法が開示されている（図２１を参照）。この方法を用いると、署名鍵が露呈した場合に、その署名鍵を廃止したとしても、その署名鍵に対応する期間の前期間及び後期間に対応する署名鍵が有効なまま維持できる。そのため、露呈した署名鍵に対応する期間を除く他の期間において生成した電子署名、及びその電子署名が付された電子文書を無効にせず済む。その結果、無効化される電子文書の数を低減することができるのである。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３６４０７８５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記文献に記載の技術を用いたとしても、露呈した署名鍵に対応する期間において生成された電子署名は全て無効となり、当該電子署名が付された電子文書が実質的に全て無効になってしまう。もちろん、署名鍵が露呈していなくても、その署名鍵を無効にすべき理由が生じた場合には同様に無効となる電子文書が発生してしまう。上記の通り、電子署名の役割は、紙文書に付される署名と同じである。従って、電子文書であっても、その種類によっては再度電子署名を付してもらうのが容易でないこともある。
【０００８】
そのため、署名鍵が露呈しないように厳重に管理し、電子署名を無効にしないようにすることが非常に重要になる。しかし、署名鍵が絶対に露呈しないという保証を与えることは難しい。そこで、ある電子署名の生成に用いた署名鍵が露呈した場合でも、その電子署名（及び電子文書）に対して有効な他の検証鍵を生成することができれば、その電子署名を無効にせずに済む。また、こうした理由以外の目的においても、ある電子署名及び電子文書に対して有効な複数の検証鍵を安全に生成することが可能な仕組みがあると便利な場合も考えられる。
【０００９】
上記のような仕組みに関し、例えば、作本・田中による次のような研究成果（以下、ＳＣ０８方式）の報告がある。ＳＣ０８方式：「Ｋｏｉｃｈｉ  Ｓａｋｕｍｏｔｏ  ａｎｄ  Ｋｅｉｓｕｋｅ  Ｔａｎａｋａ，“Ｋｅｙ−Ｓｕｂｓｔｉｔｕｔａｂｌｅ  Ｓｉｇｎａｔｕｒｅ．”，Ｔｈｅ  ２００８  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，  Ｍｉｙａｚａｋｉ，  Ｊａｐａｎ，  Ｊａｎ．２２−２５，  ２００８」。
【００１０】
ＳＣ０８方式は、署名者との対話を行うことが可能なエンティティ（以下、身代わり署名者）により、ある電子署名及び電子文書に対して有効な検証鍵（以下、代用検証鍵）を生成できるようにするというものである。ＳＣ０８方式では、署名者との対話の中で代用検証鍵を生成する仕組み（以下、対話アルゴリズム）を提供することで、身代わり署名者以外の第３者が自由に代用検証鍵を生成できてしまうことを防止している。しかし、ＳＣ０８方式では対話アルゴリズムの中で署名者が実質的に代用検証鍵を生成しており、代用検証鍵に対応する署名鍵を用いて身代わり署名者が生成した電子署名の安全性に不安が残る。
【００１１】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、より安全に対話アルゴリズムを用いて代用検証鍵を生成することが可能な、新規かつ改良された情報処理装置、電子署名生成システム、電子署名用の鍵生成方法、情報処理方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明のある観点によれば、第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供部と、前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得部と、前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成部と、を備える、情報処理装置が提供される。
【００１３】
また、前記第１署名鍵ＫＳはＮ１個（Ｎ１≧２）のパラメータを含んで成り、前記第２部分情報取得部は、前記第１部分情報を用いて生成されるパラメータ及び前記第１署名鍵ＫＳに含まれるＮ１個のパラメータを用いて生成され、当該第１署名鍵ＫＳに含まれる個々のパラメータを特定不可能な前記第２部分情報を取得するように構成されていてもよい。
【００１４】
また、前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、前記第１部分情報提供部は、前記第１部分情報として前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータを提供するように構成されていてもよい。
【００１５】
また、前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、前記第１部分情報提供部は、前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータ、及び当該Ｍ２個のパラメータを除く（Ｎ２−Ｍ２）個のパラメータのハッシュ値を前記第１部分情報として提供するように構成されていてもよい。
【００１６】
また、前記第２部分情報が生成される際に前記第１部分情報に対して前記他装置が生成した乱数に基づく所定の演算処理が施されている場合、前記第２部分情報取得部は、前記第２部分情報と共に前記他装置が生成した乱数を取得するように構成されていてもよい。この場合、前記第２検証鍵生成部は、前記第１部分情報、前記第２部分情報、及び前記乱数に基づいて前記第２検証鍵ＫＶ’を生成する。
【００１７】
また、上記課題を解決するために、本発明の別の観点によれば、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳが格納された記憶部と、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得部と、前記第１部分情報取得部で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成部と、前記第１部分情報を提供した他装置に対し、前記第２部分情報生成部で生成された第２部分情報を提供する第２部分情報提供部と、を備える、情報処理装置が提供される。
【００１８】
また、前記第１署名鍵ＫＳはＮ１個（Ｎ１≧２）のパラメータを含んで成り、前記第２部分情報生成部は、前記第１部分情報を用いて生成されるパラメータ及び前記第１署名鍵ＫＳに含まれるＮ１個のパラメータを利用し、当該第１署名鍵ＫＳに含まれる個々のパラメータを特定不可能な前記第２部分情報を生成するように構成されていてもよい。
【００１９】
また、前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、前記第１部分情報取得部は、前記第１部分情報として前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータを取得するように構成されていてもよい。
【００２０】
また、前記第２検証鍵ＫＶ’はＮ２個（Ｎ２≧２）のパラメータを含んで成り、前記第１部分情報取得部は、前記第２検証鍵ＫＶ’に含まれるＭ２個（Ｍ２＜Ｎ２）のパラメータ、及び当該Ｍ２個のパラメータを除く（Ｎ２−Ｍ２）個のパラメータのハッシュ値を前記第１部分情報として取得するように構成されていてもよい。
【００２１】
また、上記の情報処理装置は、乱数を発生させる乱数発生器と、前記乱数発生器で発生させた乱数を用いて前記第１部分情報に所定の演算処理を施す演算処理部と、をさらに備え、前記第２部分情報生成部は、前記演算処理部で所定の演算処理が施された第１部分情報及び前記第１署名鍵ＫＳを利用して前記第２部分情報を生成し、前記第２部分情報提供部は、前記第２部分情報と共に前記演算処理部で用いた乱数を前記他装置に提供するように構成されていてもよい。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳが格納された記憶部と、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を第２の情報処理装置から取得する第１部分情報取得部と、前記第１部分情報取得部で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成部と、前記第１部分情報を提供した前記第２の情報処理装置に対し、前記第２部分情報生成部で生成された第２部分情報を提供する第２部分情報提供部と、を有する、第１の情報処理装置と；前記第１の情報処理装置に対し、前記第１部分情報を提供する第１部分情報提供部と、前記第２部分情報を取得する第２部分情報取得部と、前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成部と、を有する、第２の情報処理装置と；を含む、電子署名生成システムが提供される。
【００２３】
また、上記課題を解決するために、本発明の別の観点によれば、第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供ステップと、前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得ステップと、前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成ステップと、を含む、電子署名用の鍵生成方法が提供される。
【００２４】
また、上記課題を解決するために、本発明の別の観点によれば、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得ステップと、前記第１部分情報取得ステップで取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成ステップと、前記第１部分情報を提供した他装置に対し、前記第２部分情報生成ステップで生成された第２部分情報を提供する第２部分情報提供ステップと、を含む、情報処理方法が提供される。
【００２５】
また、上記課題を解決するために、本発明の別の観点によれば、第２の情報処理装置が、第１の情報処理装置に対し、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供ステップと、第１の情報処理装置が、前記第１部分情報を第２の情報処理装置から取得する第１部分情報取得ステップと、前記第１部分情報取得ステップで取得した前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成ステップと、前記第１部分情報を提供した第２の情報処理装置に対し、前記第２部分情報生成ステップで生成した第２部分情報を提供する第２部分情報提供ステップと、前記第２の情報処理装置が、前記第２部分情報を取得する第２部分情報取得ステップと、前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成ステップと、を含む、電子署名用の鍵生成方法が提供される。
【００２６】
また、上記課題を解決するために、本発明の別の観点によれば、第１検証鍵ＫＶに対応する第１署名鍵ＫＳを保持する他装置に対し、当該第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を提供する第１部分情報提供機能と、前記他装置により前記第１部分情報及び前記第１署名鍵ＫＳを用いて生成され、前記第１署名鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を取得する第２部分情報取得機能と、前記第１部分情報及び前記第２部分情報に基づいて前記第２検証鍵ＫＶ’を生成する第２検証鍵生成機能と、をコンピュータに実現させるためのプログラムが提供される。
【００２７】
また、上記課題を解決するために、本発明の別の観点によれば、対を成す第１検証鍵ＫＶ及び第１署名鍵ＫＳのうち、前記第１署名鍵ＫＳを用いて生成された電子署名σを検証することが可能な第２検証鍵ＫＶ’（ＫＶ’≠ＫＶ）の一部を成し、かつ、前記第２検証鍵ＫＶ’を特定不可能な第１部分情報を取得する第１部分情報取得機能と、前記第１部分情報取得機能で取得された前記第１部分情報及び前記第１署名鍵ＫＳを利用し、前記第１検証鍵ＫＳを特定不可能であり、かつ、前記第１部分情報を除く第２検証鍵ＫＶ’の残り部分を生成するための第２部分情報を生成する第２部分情報生成機能と、前記第１部分情報を提供した他装置に対し、前記第２部分情報生成機能で生成された第２部分情報を提供する第２部分情報提供機能と、をコンピュータに実現させるためのプログラムが提供される。
【００２８】
上記の情報処理装置に関し、前記他装置は認証局サーバであってもよい。また、上記の情報処理装置は、自装置を特定するためのＩＤ情報を前記他装置に通知するＩＤ通知部をさらに備えていてもよい。そして、上記の情報処理装置は、前記第１部分情報提供部、前記第２部分情報取得部、及び前記第２検証鍵生成部を用い、前記ＩＤ通知部による通知を受けて前記他装置により生成された前記ＩＤ情報を含む電子文書ｍＩＤ、及び当該電子文書ｍＩＤに対して前記第１署名鍵ＫＳを用いて生成された電子署名σＩＤを受理する第２検証鍵ＫＶ’を生成し、前記第２検証鍵ＫＶ’の正当性を証明するための電子証明書として当該電子文書ｍＩＤ及び電子署名σＩＤを利用するように構成されていてもよい。
【００２９】
上記の情報処理装置に関し、自装置は委任者の電子署名を代理する代理人が利用する代理人端末であってもよい。さらに、前記他装置は前記委任者が利用する委任者端末であってもよい。そして、上記の情報処理装置は、前記第１部分情報提供部、前記第２部分情報取得部、及び前記第２検証鍵生成部を用い、前記委任者が前記代理人に委譲する署名権限の内容を少なくとも含む電子文書ｍｗ、及び当該電子文書ｍｗに対して前記第１署名鍵ＫＳを用いて生成された電子署名σｗを受理する第２検証鍵ＫＶ’を生成し、前記第２検証鍵ＫＶ’が前記委任者に認められたものであることを証明するための証明書として当該電子文書ｍｗ及び電子署名σｗを利用するように構成されていてもよい。
【００３０】
また、上記課題を解決するために、本発明の別の観点によれば、上記の電子署名生成システムが有する機能をコンピュータに実現させることが可能なプログラムが提供されうる。また、上記課題を解決するために、本発明の別の観点によれば、上記の各プログラムが記録されたコンピュータにより読み取り可能な記録媒体が提供されうる。
【発明の効果】
【００３１】
以上説明したように本発明によれば、より安全に対話アルゴリズムを用いて代用検証鍵を生成することが可能になる。
【図面の簡単な説明】
【００３２】
【図１】電子署名を生成するための署名鍵が露呈した場合に生じる問題を模式的に示した説明図である。
【図２】鍵代用可能電子署名方式の一例であるＳＣ０８方式に関してエンティティの一構成例を示した説明図である。
【図３】ＳＣ０８方式における代用鍵生成方法、電子署名の生成方法、及び電子署名の検証方法を示した説明図である。
【図４】代用検証鍵の特性を示した説明図である。
【図５】ＳＣ０８方式における代用鍵生成方法の流れを示す説明図である。
【図６】ＳＣ０８方式におけるシステムパラメータの生成方法を示す説明図である。
【図７】ＳＣ０８方式における電子署名の生成方法を示す説明図である。
【図８】ＳＣ０８方式における電子署名の検証方法を示す説明図である。
【図９】ＳＣ０８方式における代用鍵生成方法を詳細に示す説明図である。
【図１０】本発明の第１実施形態に係る代用鍵生成方法の流れを示す説明図である。
【図１１】同実施形態に係る電子署名の生成方法を示す説明図である。
【図１２】同実施形態に係る電子署名の検証方法を示す説明図である。
【図１３】同実施形態に係る代用鍵生成方法を詳細に示す説明図である。
【図１４】同実施形態に係る鍵更新システムの一構成例、署名者端末、検証者端末、及び代用鍵生成者端末の機能構成例を示す説明図である。
【図１５】本発明の第２実施形態に係る電子署名の生成方法を示す説明図である。
【図１６】同実施形態に係る電子署名の検証方法を示す説明図である。
【図１７】同実施形態に係る代用鍵生成方法を詳細に示す説明図である。
【図１８】本発明の第１及び第２実施形態の一変形例に係る代用鍵生成方法の流れを示す説明図である。
【図１９】本発明の第１及び第２実施形態に係る署名者端末及び検証者端末のハードウェア構成例を示す説明図である。
【図２０】期限付き電子署名方式に係る鍵更新方法を模式的に示した説明図である。
【図２１】本発明の第１及び第２実施形態に係る代用鍵生成方法をＰＫＩの認証局サーバとユーザ端末との間の鍵検証に応用する場合のシステム構成例を示す説明図である。
【図２２】本発明の第１及び第２実施形態に係る代用鍵生成方法をＰＫＩの認証局サーバとユーザ端末との間の鍵証明に応用する方法を示した説明図である。
【図２３】本発明の第１及び第２実施形態に係る代用鍵生成方法を代理人署名方式の代理人証明に応用する場合のシステム構成例を示す説明図である。
【図２４】本発明の第１及び第２実施形態に係る代用鍵生成方法を代理人署名方式の代理人証明に応用する方法を示した説明図である。
【発明を実施するための形態】
【００３３】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００３４】
［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１を参照しながら、電子署名方式において署名鍵が露呈した場合に生じる問題について簡単に説明する。さらに、図２１を併せて参照しながら、署名鍵の露呈に対する一般的な対策方法について簡単に説明し、その問題点について指摘する。
【００３５】
次いで、図２、図３を参照しながら、ＳＣ０８方式又は同実施形態に係る鍵代用可能電子署名方式のエンティティ構成、及び各エンティティが行う手続きについて説明する。次いで、図４を参照しながら、同実施形態に係る鍵更新方法にて用いる代用鍵の特性、及びその代用鍵に要求される条件について説明する。次いで、図５〜図９を参照しながら、ＳＣ０８方式の代用鍵生成方法について詳細に説明する。この中で、ＳＣ０８方式の問題点について言及する。
【００３６】
次いで、図１０〜図１４を参照しながら、本発明の第１実施形態に係る鍵代用可能電子署名方式（以下、本手法１）、及び鍵更新システムの構成について詳細に説明する。この中で、同実施形態に係る鍵代用可能電子署名方式の具体的なアルゴリズムについても詳細に説明する。また、同実施形態に係る鍵更新システムのシステム構成、署名者端末、検証者端末、代用鍵生成者端末の機能構成についても説明する。
【００３７】
次いで、図１５〜図１７を参照しながら、本発明の第２実施形態に係る鍵代用可能電子署名方式（以下、本手法２）、及び鍵更新システムの構成について詳細に説明する。この中で、同実施形態に係る鍵代用可能電子署名方式の具体的なアルゴリズムについても詳細に説明する。但し、同実施形態に係る鍵更新システムのシステム構成、署名者端末、検証者端末、代用鍵生成者端末の機能構成については上記の第１実施形態と実質的に同じであるため、説明を省略する。
【００３８】
次いで、図１８を参照しながら、上記の第１及び第２実施形態に係る代用鍵生成方法の一変形例について説明する。次いで、図２０を参照しながら、同実施形態に係る署名者端末及び検証者端末のハードウェア構成例について説明する。次いで、図２１、図２２を参照しながら、上記第１及び第２実施形態に係る代用鍵生成方法をＰＫＩへ応用する方法について説明する。次いで、図２３、図２４を参照しながら、上記第１及び第２実施形態に係る代用鍵生成方法を代理人署名方式へ応用する方法について説明する。次いで、上記第１及び第２実施形態に係る代用鍵生成方法を責任分担型の電子署名方式へ応用する方法について説明する。
【００３９】
（説明項目）
１：はじめに
１−１：署名鍵の露呈について
１−２：期限付き署名方式について
１−３：システム構成について
１−４：代用検証鍵の特性について
１−５：ＳＣ０８方式の代用鍵生成方法
１−６：ＳＣ０８方式のアルゴリズム
２：第１実施形態
２−１：代用鍵生成方法
２−２：アルゴリズム
２−３：端末の機能構成
３：第２実施形態
３−１：アルゴリズム
４：第１及び第２実施形態に係る変形例
４−１：代用鍵生成方法
５：各端末のハードウェア構成例
６：応用例
６−１：ＰＫＩへの応用
６−２：代理人署名方式への応用
６−３：責任分担型電子署名への応用
【００４０】
＜１：はじめに＞
はじめに、本発明に係る実施形態について詳細に説明するに先立ち、当該実施形態の技術的意義及び技術内容に関する理解を助けるべく、当該理解のために参考にすべき技術内容について簡単に説明する。この中で、同実施形態の技術を開発するに当たって基盤とされたＳＣ０８方式の代用鍵生成方法及びそのアルゴリズムについても詳細に説明する。
【００４１】
［１−１：署名鍵の露呈について］
まず、図１を参照しながら、署名鍵の露呈について簡単に説明する。図１には、電子文書ｍに付した電子署名σを生成するための署名鍵ｓｋが露呈した場合に生じる問題点が模式的に示されている。
【００４２】
図１に示すように、署名鍵ｓｋを用いて電子文書ｍに付された正当な電子署名σは、署名鍵ｓｋとペアを成す正当な検証鍵ｐｋを用いて検証することができる。なお、検証鍵ｐｋは公開されている。また、この検証には、所定の検証式が用いられる。つまり、検証者は、所定の検証式に対して電子文書ｍ、電子署名σ、及び検証鍵ｐｋの情報を入力し、所定の検証式の成否を判定することにより、電子署名σの正当性を検証する。このように、検証鍵ｐｋについて、電子文書ｍに対する電子署名σが正当なものであると判定される場合、「検証鍵ｐｋが電子署名σ及び電子文書ｍのペア（ｍ，σ）を受理する」と言う。
【００４３】
さて、署名鍵ｓｋは、署名者により秘密に管理され、通常、他人に知られることはない。もちろん、署名者は、検証者に対しても署名鍵ｓｋを知られないように管理する。しかし、署名鍵ｓｋが絶対に露呈しないということを保証することは難しい。例えば、署名者が利用する端末が攻撃を受け、その端末に保管していた署名鍵ｓｋの情報が漏れることも大いに考えられる。このように、何らかの理由で署名鍵ｓｋが他人（以下、攻撃者）に露呈した場合（Ｓ１）、攻撃者は、任意の電子文書に電子署名σを付すことが可能になる。つまり、電子署名σが偽造されてしまう。
【００４４】
例えば、露呈した署名鍵ｓｋを用いて攻撃者が電子文書ｍ１に電子署名σを付した場合について考えてみよう。この場合、電子文書ｍ１に付された電子署名σは、正当な署名鍵ｓｋで生成されたものであるため、検証鍵ｐｋにより受理される。つまり、攻撃者が生成した署名であるにも関わらず、正当な署名者の署名として受理されてしまうのである。例えば、電子文書ｍ１が不動産の売買契約書であった場合、正当な署名者は、知らないところで自分が所有する不動産を勝手に売却されてしまう危険性があるということになる。
【００４５】
そこで、正当な署名者は、署名鍵ｓｋの露呈が発覚すると、その署名鍵ｓｋを無効にする（Ｓ２）。署名鍵ｓｋが無効になると、その署名鍵ｓｋとペアを成す検証鍵ｐｋも無効になる。さらに、その署名鍵ｓｋで生成された電子署名σも無効になる。例えば、電子文書ｍが契約書であった場合、電子署名σが無効になると、電子文書ｍを用いて交わされた契約が無効になってしまう。電子文書ｍが重要度の低い社内文書のようなものであれば、新たに生成した署名鍵ｓｋ’を用いて再び電子署名σ’を付せば良いが、第３者との間で交わされた契約書のような重要文書の場合には簡単に再署名できないことが多い。
【００４６】
このような重要文書を多く扱っている場合、署名鍵ｓｋの露呈による被害は深刻である。なお、これまでも署名鍵ｓｋの露呈に伴って過去に生成された電子署名σが無効になってしまうという問題に対して様々な対策が考えられてきた。しかし、その多くは、署名鍵ｓｋの露呈に伴って電子署名σが無効になることによる影響を低減させるものであり、無効になる電子署名σを救済する手段ではない。そのような署名鍵ｓｋの露呈に対する対策の一例として、ここで、期限付き署名方式について紹介する。
【００４７】
［１−２：期限付き署名方式について］
期限付き署名方式とは、図２０に示すような方式である。この方式では、署名鍵ｓｋが所定期間毎に更新される。一方、検証鍵ｐｋは全期間で共通のものとする。例えば、期間１（Ｐｅｒｉｏｄ１）では署名鍵ｓｋ１が用いられ、期間１においてのみ有効な電子署名が生成される。時間が経過し、期間２に移ると、期間２においてのみ有効な署名鍵ｓｋ２が用いられ、期間２においてのみ有効な電子署名が生成される。この方式の場合、仮に期間２において署名鍵ｓｋ１による電子署名が生成されたとしても、その電子署名は検証鍵ｐｋで受理されない。
【００４８】
従って、図２０のステップＢに示すように署名鍵ｓｋ１、ｓｋ３、ｓｋ４が露呈し、ステップＣに示すように期間１、３、４の電子署名が無効化されても、期間２、５、…の電子署名は有効なまま維持される。そのため、期間２、５、…の期間に署名鍵ｓｋ２、ｓｋ５、…を用いて生成された電子署名が付属する電子文書は無効化されずに済む。しかしながら、期間１、３、４において生成された電子署名が付属する電子文書は無効になってしまうため、上記問題の根本的な解決には至らない。やはり、上記問題の解決には、露呈前に署名鍵ｓｋで生成された電子署名σを救済する手段が必要になるのである。
【００４９】
こうした理由に鑑み、本件発明者は、攻撃者が偽造した電子署名σは受理せず、正当な署名者が電子文書ｍに対して過去に付した電子署名σだけを受理するような他の検証鍵ｐｋ’を生成すればよいという考えに想到した。しかし、十分な安全性を確保しつつ、このような他の検証鍵ｐｋ’を生成することは容易ではない。但し、ＳＣ０８方式に言う代用鍵を用いれば、このような他の検証鍵ｐｋ’を実現できる可能性がある。そこで、ＳＣ０８方式に注目した。
【００５０】
なお、後述するＳＣ０８方式は必ずしも上記の目的に用いるために開発されたものではなく、ある電子署名及び電子文書の組に対して安全な複数の検証鍵を生成できるようにすることを目的に開発されたものである。つまり、ＳＣ０８方式は、その用途を限定して開発されたものではない。従って、ＳＣ０８方式は様々な用途に用いることができる点に注意されたい。また、後述する各実施形態の技術はＳＣ０８方式に更なる工夫を加えて安全性を高めたものであるが、これについても同様に広範な用途に適用できる点に注意されたい。
【００５１】
［１−３：システム構成］
ここで、ＳＣ０８方式及び後述する各実施形態で想定する方式に係る電子署名システムのモデルについて説明する。これらの方式では、電子署名システムのモデルとして、５つのエンティティが想定されている。ここで想定しているエンティティは、図２に示すように、システム管理者、署名者、検証者、認証局、及び身代わり署名者（以下、代用鍵生成者）の５つである。
【００５２】
システム管理者は、システムパラメータ生成アルゴリズム（ＳｅｔｕｐＫＳＳ）を用いてシステムパラメータｃｐを生成するエンティティである。署名者は、鍵生成アルゴリズム（ＧｅｎＫＳＳ）を用いて各署名者固有の署名鍵ｓｋ及び当該署名鍵ｓｋとペアを成す検証鍵ｐｋを生成するエンティティである。また、署名者は、署名生成アルゴリズム（ＳｉｇＫＳＳ）を用いて電子文書ｍに対する電子署名σを生成する。
【００５３】
検証者は、署名検証アルゴリズム（Ｖｅｒ）を用いて電子文書ｍに付された電子署名σの正当性を検証するエンティティである。代用鍵生成者は、代用鍵生成アルゴリズム＜ＯＲＧ（ｓｋ），ＳＵＢ＞を用いて代用署名鍵ｓｋ’及び当該代用署名鍵ｓｋ’とペアを成す代用検証鍵ｐｋ’を生成するエンティティである。但し、代用鍵生成者は、ある電子文書ｍ及びその電子文書ｍに付された電子署名σに対する代用鍵を生成する際、その電子文書ｍに付された電子署名σの生成者である署名者との間で対話を行いながら代用鍵を生成する。また、認証局は、署名者又は代用鍵生成者が生成した検証鍵又は代用検証鍵の正当性を保証するための証明書を発行するエンティティである。
【００５４】
これらのエンティティは、図３に示すような手続きを実行し、署名鍵ｓｋ及び検証鍵ｐｋの生成、電子署名σの生成、代用署名鍵ｓｋ’及び代用検証鍵ｐｋ’の生成、電子署名σの検証を行う。なお、システム管理者によりシステムパラメータ生成アルゴリズム（ＳｅｔｕｐＫＳＳ）を用いてシステムパラメータｃｐが既に生成されているものとする。なお、ＳｅｔｕｐＫＳＳを用いてｃｐを生成することを下記の式（１）のように表現する。但し、１λはセキュリティパラメータである。
【００５５】
【数１】
2010278482.tif 000003
【００５６】
（署名者による鍵生成工程）
まず、署名者が行う鍵生成手続きについて説明する。図３に示すように、署名者は、鍵生成工程において、システム管理者からシステムパラメータｃｐを取得する。次いで、署名者は、鍵生成アルゴリズム（ＧｅｎＫＳＳ）にシステムパラメータｃｐを入力し、署名鍵ｓｋと検証鍵ｐｋのペアを生成する。なお、ＧｅｎＫＳＳを用いて（ｓｋ，ｐｋ）を生成することを下記の式（２）のように表現する。鍵生成アルゴリズムＧｅｎＫＳＳを用いて署名鍵ｓｋ及び検証鍵ｐｋを生成すると、署名者は、生成した署名鍵ｓｋ及び検証鍵ｐｋをペアにして保管する。そして、署名者は、必要に応じて検証鍵ｐｋを自身の検証鍵として認証局に登録し、その証明書を受け取る。
【００５７】
【数２】
2010278482.tif 000004
【００５８】
（署名者による署名生成工程）
次に、署名者が行う署名生成手続きについて説明する。図３に示すように、署名者は、署名を付すべき電子文書ｍ、及び保管している署名鍵ｓｋを用意する。次いで、署名者は、署名生成アルゴリズム（ＳｉｇＫＳＳ）に署名鍵ｓｋ及び電子文書ｍを入力し、電子署名σを生成する。なお、ＳｉｇＫＳＳを用いてσを生成することを下記の式（３）のように表現する。次いで、署名者は、下記の式（３）で生成した電子署名σ（アルゴリズムの出力値）を電子文書ｍに対する電子署名σに設定する。
【００５９】
【数３】
2010278482.tif 000005
【００６０】
（署名者及び代用署名者による代用鍵生成工程）
次に、署名者及び代用署名者が協働して行う代用鍵生成手続きについて、その概要を説明する。なお、代用鍵生成方法の詳細については後述する。まず、署名者は、電子文書ｍ、電子署名σ、電子署名σの生成に用いた署名鍵ｓｋ、署名鍵ｓｋとペアを成す検証鍵ｐｋを用意する。次いで、署名者は、用意した電子文書ｍ、電子署名σ、検証鍵ｐｋを代用鍵生成者に提供する。このとき、代用鍵生成者は、署名者から電子文書ｍ、電子署名σ、検証鍵ｐｋを取得する。
【００６１】
次いで、署名者及び代用鍵生成者は、代用鍵生成アルゴリズム＜ＯＲＧ（ｓｋ），ＳＵＢ＞に共通パラメータとして検証鍵ｐｋ、電子文書ｍ、及び電子署名σを入力する。さらに、署名者は、代用鍵生成者との対話の中で、電子文書ｍ、電子署名σを受理する代用検証鍵ｐｋ’、及び当該代用検証鍵ｐｋ’とペアを成す代用署名鍵ｓｋ’を生成する。なお、後段において詳述するように、ＳＣ０８方式では「実質的に署名者が代用鍵を生成」するのに対し、後述する各実施形態の方式では「代用鍵生成者が代用鍵を生成」する点に注意が必要である。この点こそが両方式の安全性の違いを決める大きな相違点だからである。
【００６２】
また、＜ＯＲＧ（ｓｋ），ＳＵＢ＞を用いてｓｋ’、ｐｋ’を生成することを下記の式（４）のように表現する。ここで、ＯＲＧは署名者に対応し、ＳＵＢは代用鍵生成者に対応する。つまり、ＯＲＧ（ｓｋ）は、署名者が代用鍵生成アルゴリズムの中で署名鍵ｓｋを利用することを示すものである。但し、署名鍵ｓｋは、ＳＵＢである代用鍵生成者に開示されず、ＯＲＧである署名者側で閉じた演算に利用され、その演算結果のみが代用生成者に提供される。その詳細については後述する。下記の式（４）で代用署名鍵ｓｋ’及び代用検証鍵ｐｋ’を生成すると、代用鍵生成者は、必要に応じて代用検証鍵ｐｋ’を自身の検証鍵として認証局に登録し、その証明書を受け取る。
【００６３】
【数４】
2010278482.tif 000006
【００６４】
（検証者による署名検証工程）
次に、検証者が行う手続きについて説明する。まず、検証者は、署名者から電子署名σ、電子文書ｍ、及び検証鍵ｐｋを取得する。次いで、検証者は、必要に応じて、検証鍵ｐｋが本当に署名者の検証鍵であるか否かを認証局の証明書で確認する。次いで、検証者は、署名検証アルゴリズム（Ｖｅｒ）に検証鍵ｐｋ、電子文書ｍ、電子署名σを入力し、検証結果ｖｏｕｔ＝０（エラー）又は１（受理）を算出する。なお、Ｖｅｒによりｖｏｕｔを算出することを下記の式（５）のように表現する。次いで、検証者は、下記の式（５）で算出された検証結果ｖｏｕｔに応じてｖｏｕｔ＝１ならば（σ，ｍ）を受理し、ｖｏｕｔ＝０ならば拒否する。なお、代用検証鍵ｐｋ’を用いた検証手続きを行う場合についても同様である。
【００６５】
【数５】
2010278482.tif 000007
【００６６】
以上説明したように、これらの方式では、署名者と代用鍵生成者とが対話を行うことにより、署名鍵ｓｋで生成した電子文書ｍに対する電子署名σを受理する代用検証鍵ｐｋ’を生成している。先に述べた通り、これらの方式は、そもそも鍵更新方法を実現するために考案されたものではなく、署名者とは異なるエンティティ（代用鍵生成者）に代用鍵を安全に生成させるための技術である。従って、勝手に代用鍵を生成されないよう、真の署名者との対話を代用鍵生成の要件としている。そのため、代用鍵の生成工程に関しては、上記のように入力情報の種類に工夫を凝らした対話的な手法が用いられているのである。
【００６７】
［１−４：代用検証鍵の特性について］
ここで、図４を参照しながら、代用検証鍵ｐｋ’の特性について簡単に纏めておく。先に述べた通り、代用検証鍵ｐｋ’は、ある署名鍵ｓｋで生成された電子署名σ及び当該電子署名σが付された電子文書ｍを受理するものである。従って、代用検証鍵ｐｋ’は、電子文書ｍ及び電子署名σのペアに対して生成される。当然のことながら、代用検証鍵ｐｋ’は、署名鍵ｓｋとペアを成す検証鍵ｐｋとは異なるものである。
【００６８】
また、代用検証鍵ｐｋ’には少なくとも次のような条件が課される。条件（１）：代用検証鍵ｐｋ’は署名者との対話により生成可能であること。条件（２）：代用鍵生成者以外が勝手に代用検証鍵を生成不可能であること。これらの条件により、代用検証鍵ｐｋ’を生成することが可能なエンティティが署名者と対話可能なエンティティに制限される。逆に言えば、署名者と対話可能なエンティティに対し、代用鍵の生成可能性を与えることができる。
【００６９】
条件（３）：代用鍵生成者は署名者の電子署名を偽造不可能であること。つまり、代用鍵生成者が対話の中で取得する情報を用いても、署名者の電子署名を偽造できないようにすることが要件として課される。この条件により、署名者の電子署名に対する偽造不可能性が確保される。条件（４）：署名者は代用鍵生成者の電子署名を偽造不可能であること。つまり、対話の中で署名者が取得する情報を用いても、代用検証鍵ｐｋ’とペアを成す代用署名鍵ｓｋ’を用いて生成された電子署名σ’を偽造できないようにすることが要件として課される。この条件により、代用鍵生成者の電子署名に対する偽造不可能性が確保される。
【００７０】
以上説明した条件（１）〜条件（４）を満たすことで、代用鍵を用いた電子署名システムにおける安全性が確保されることになる。そこで、これらの条件を満たすＳＣ０８方式の代用鍵生成方法、及びその具体的なアルゴリズムについて以下で説明する。
【００７１】
［１−５：ＳＣ０８方式の代用鍵生成方法］
まず、図５を参照する。図５は、ＳＣ０８方式の代用鍵生成アルゴリズム＜ＯＲＧ（ｓｋ），ＳＵＢ＞における処理の大まかな流れを示した説明図である。図５に示すように、署名者及び代用鍵生成者の双方に共有情報として検証鍵ｐｋ、電子文書ｍ、電子署名σが入力されているものとする。また、署名者側では、署名鍵ｓｋも利用される。但し、代用鍵生成者が署名者の電子署名を偽造できないようにするため、署名鍵ｓｋが代用鍵生成者に直接提供されることはない。
【００７２】
まず、代用鍵生成者により代用署名鍵ｓｋ’が生成され、その代用署名鍵ｓｋ’の情報を用いて代用検証鍵ｐｋ’の一部情報が生成される。上記の通り、代用検証鍵ｐｋ’は、署名鍵ｓｋで生成された電子署名σを受理すべきものである。そのため、署名鍵ｓｋの情報を知らない代用鍵生成者は、署名鍵ｓｋの情報を知得せずに代用検証鍵ｐｋ’を生成することはできない。また、代用検証鍵ｐｋ’は、代用署名鍵ｓｋ’で生成された電子署名σ’（σ’≠σ）を受理すべきものである。そのため、代用検証鍵ｐｋ’に代用署名鍵ｓｋ’に関する情報が含まれている必要がある。そのため、上記のように代用検証鍵ｐｋ’に含める一部情報が代用鍵生成者により生成されるのである。
【００７３】
代用鍵生成者により生成された代用検証鍵ｐｋ’に含める一部情報は、代用鍵生成者から署名者に提供される（Ｓ１２）。次いで、代用検証鍵ｐｋ’の一部情報を取得すると、署名者は、乱数を発生させ、その乱数を代用鍵生成者に提供する（Ｓ１４）。署名者から乱数を取得すると、代用鍵生成者は、取得した乱数を利用し、代用検証鍵ｐｋ’の生成に必要な代用署名鍵ｓｋ’の情報を署名者に提供する（Ｓ１６）。上記の通り、代用検証鍵ｐｋ’は、代用署名鍵ｓｋ’で生成された電子署名σ’をも受理する必要がある。そのため、代用署名鍵ｓｋ’に関する情報を署名者に提供する必要が生じる。
【００７４】
しかし、代用署名鍵ｓｋ’が署名者に知られると、代用署名鍵ｓｋ’で生成される電子署名σ’が勝手に生成されてしまう。そこで、代用鍵生成者は、乱数を利用して代用署名鍵ｓｋ’が署名者に特定されず、かつ、代用検証鍵ｐｋ’を生成することが可能な形にして代用署名鍵ｓｋ’に関する情報を署名者に提供するのである。このような代用署名鍵ｓｋ’に関する情報を取得すると、署名者は、代用検証鍵ｐｋ’（実際には代用検証鍵ｐｋ’を決定するための情報）を生成する（Ｓ１８）。次いで、署名者は、生成した代用検証鍵ｐｋ’を代用鍵生成者に提供する。つまり、ＳＣ０８方式では、代用鍵生成者とは言うものの、実質的に署名者が代用検証鍵ｐｋ’を生成しているのである。
【００７５】
以上説明した方法により、代用署名鍵ｓｋ’及び代用検証鍵ｐｋ’が生成される。ここまで、図５を参照しながら、ＳＣ０８方式における代用鍵生成処理の大まかな流れについて説明してきた。しかし、上記説明の中では具体的な演算方法について説明していない。そこで、図５で示した各処理ステップの内容を実現するための具体的な演算アルゴリズムについて以下で詳細に説明する。但し、ここに示す具体的な演算式等は一例であり、種々の変形が可能である点については注意されたい。
【００７６】
［１−６：ＳＣ０８方式のアルゴリズム］
まず、代用鍵生成アルゴリズムの具体的な演算内容について説明するに先立ち、ＳＣ０８方式のシステムパラメータ生成アルゴリズム、鍵生成アルゴリズム、署名生成アルゴリズム、及び署名検証アルゴリズムについて順次説明する。これらのアルゴリズムは相互に関係するものであり、代用鍵生成アルゴリズムを実現するためのＳＣ０８方式に特徴的な構成を含んでいる。その後、代用鍵生成アルゴリズムについて説明する。
【００７７】
（システムパラメータ生成アルゴリズム）
まず、図６を参照しながら、上記の式（１）で示したシステムパラメータ生成アルゴリズムについて説明する。図６は、システムパラメータ生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、システムパラメータ生成アルゴリズムは、システム管理者により実行される。
【００７８】
システムパラメータ生成アルゴリズムにおいては、まず、素数ｑ＝３（ｍｏｄ  ４）に対し、下記の式（６）を満たすλビットの素数ｐが選択される（Ｓ３０）。次いで、位数ｐとなるＺｐ＊の元ｇが選択される（Ｓ３２）。但し、Ｚｐは素数ｐを法とする整数の有限体を意味し、Ｚｐ＊はその乗法群を意味する。次いで、素数ｐ、元ｇを含むシステムパラメータｃｐ＝（ｇ，ｐ）が設定される（Ｓ３４）。ここまでがシステムパラメータ生成アルゴリズムの内容である。このようにしてシステムパラメータｃｐを生成すると、システム管理者は、システムパラメータｃｐを各エンティティに提供する（Ｓ３６）。以下の説明においては各エンティティにシステムパラメータｃｐが提供されているものとする。
【００７９】
【数６】
2010278482.tif 000008
【００８０】
（鍵生成アルゴリズム、署名生成アルゴリズム）
次に、図７を参照しながら、上記の式（２）で示した鍵生成アルゴリズム、及び上記の式（３）に示した署名生成アルゴリズムについて説明する。図７は、鍵生成アルゴリズム及び署名生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、鍵生成アルゴリズム及び署名生成アルゴリズムは、署名者により実行される。
【００８１】
まず、鍵生成アルゴリズムについて説明する。鍵生成アルゴリズムにおいては、まず、ランダムにＺｑの元ｘ１、ｘ２が選択される（Ｓ４０）。次いで、選択されたｘ１、ｘ２を用いて、下記の式（７）及び式（８）に示すようにｙ１、ｙ２が算出される（Ｓ４２）。次いで、ランダムにＺｑ＊の元αが選択される（Ｓ４４）。次いで、ランダムに｛０，１｝λの元ｗが選択される（Ｓ４６）。なお、ステップＳ４４、Ｓ４６の処理順序は、適宜変更可能である。ここまでが鍵生成アルゴリズムの内容である。以上の演算により、下記の式（９）に示す検証鍵ｐｋ、及び下記の式（１０）に示す署名鍵ｓｋが生成される。
【００８２】
【数７】
2010278482.tif 000009
【００８３】
次に、署名生成アルゴリズムについて説明する。上記の式（３）に示した通り、署名生成アルゴリズムには、鍵生成アルゴリズムで生成された署名鍵ｓｋ、及び電子文書ｍが入力される。但し、検証鍵ｐｋも既に算出されていることから、検証鍵ｐｋを入力値に加えてもよい。このように入力値を変更すると、例えば、署名生成アルゴリズムに上記の式（７）又は式（８）で示されるｙ１、ｙ２と同じ演算式が含まれている場合、その演算処理を行わずに済む。以下の説明においては、上記の式（７）又は式（８）と同じ演算式が含まれている部分をそれぞれｙ１、ｙ２と表記することにする。
【００８４】
署名生成アルゴリズムにおいては、まず、ランダムにＺｑ＊の元ｋ１が選択される（Ｓ５０）。次に、選択されたｋ１を用いて下記の式（１１）に示すｒ１が算出される（Ｓ５２）。次いで、ｒ１、ｘ１、ｘ２を用いて下記の式（１２）に示すｋ２が算出される（Ｓ５４）。但し、ｈ３（…）は、ハッシュ関数である。ハッシュ関数とは、あるビット列ａ∈｛０，１｝＊から一定範囲の数値を生成する関数である。また、あるビット列をハッシュ関数に適用して得られる値をハッシュ値と呼ぶ。なお、下記の式（１２）において、パラメータとして与えられるｒ１、ｘ１、ｘ２は、例えば、連結してからハッシュ関数ｈ３に入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。
【００８５】
次いで、算出されたｋ２を用いて下記の式（１３）に示すｒ２が算出される（Ｓ５６）。次いで、電子署名σを付す電子文書ｍ、上記の演算により算出されたパラメータｒ１、ｒ２、及び検証鍵ｐｋに含まれるｙ１、ｙ２（但し、ｘ１、ｘ２から生成可能。）を用いて下記の式（１４）及び式（１５）に示すパラメータｃ、ｄが算出される（Ｓ５８）。但し、ｈ１（…）、ｈ２（…）はいずれもハッシュ関数である。また、パラメータｍ、ｒ１、ｒ２、ｙ１、ｙ２は、例えば、連結してから入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。
【００８６】
次いで、算出されたパラメータｃ、ｄを用いて下記の式（１６）及び式（１７）に示すｙ及びｒが算出される（Ｓ６０）。次いで、ステップＳ５０〜Ｓ６０において得られたパラメータを用いて下記の式（１８）を満たすＺｑの元ｓが算出される（Ｓ６２）。但し、Ｈ（…）はハッシュ関数である。また、パラメータｃ、ｒ、ｙは、例えば、連結してから入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。以上の演算により、下記の式（１９）に示す電子署名σが得られる。
【００８７】
【数８】
2010278482.tif 000010
【００８８】
（署名検証アルゴリズム）
次に、図８を参照しながら、上記の式（５）で示した署名検証アルゴリズムについて説明する。図８は、署名検証アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、署名検証アルゴリズムは、検証者により実行される。
【００８９】
まず、検証者は、公開されている検証鍵ｐｋ（式（９）を参照）を取得する（Ｓ７０）。さらに、検証者は、署名者から電子署名σ（式（１９）を参照）、及び電子文書ｍを取得する（Ｓ７２）。検証者は、これらの取得した情報を署名検証アルゴリズムに入力して電子署名σを検証する。なお、システムパラメータｃｐも予め取得しているものとする。
【００９０】
署名検証アルゴリズムにおいては、まず、上記の式（１４）、式（１５）、式（１６）、及び式（１７）に基づいてパラメータｃ、ｄ、ｙ、ｒが算出される（Ｓ７４）。次いで、算出したパラメータが下記の式（２０）に示す検証式Ａに代入され、検証式Ａの成否が確認される（Ｓ７６、Ｓ７８）。検証式Ａが成り立つ場合、その電子署名σが正当であるとみなし、「受理」を示す出力値ｖｏｕｔ＝１を出力して（Ｓ８０）一連の処理を終了する。一方、検証式Ａが不成立の場合、エラーを示す出力値ｖｏｕｔ＝０を出力して（Ｓ８２）一連の処理を終了する。以上の演算により、電子文書ｍに対する電子署名σの正当性が検証される。
【００９１】
【数９】
2010278482.tif 000011
【００９２】
（ＳＣ０８方式のアイデアについて）
さて、電子署名方式は検証式の形により決まると言っても過言ではない。ちなみに、上記の検証式Ａは、ＳＣ０８方式に特有のものである。この検証式Ａは、下記の式（２１）に示すＥｌＧａｍａｌ署名方式の検証式を改良して開発したものである。ＥｌＧａｍａｌ署名方式の場合、ｐ＝２＊ｑ＋１、かつ、ｑ＝３（ｍｏｄ４）となる素数ｑ、ｐについて、位数ｑとなるＺｐ＊の元ｇをシステムパラメータに用いると、電子文書ｍと電子署名σのペアを受理する検証鍵ｐｋは唯１つしか存在しない。そのため、ＥｌＧａｍａｌ署名方式の検証式に基づいて署名生成システムを構成しようとすると、代用鍵を生成することができない。つまり、上記の条件（１）を満たさない。そこで考案されたのが、上記の式（２０）に示したＳＣ０８方式の検証式Ａである。以下、ＳＣ０８方式のアイデアについて、もう少し詳しく説明する。
【００９３】
【数１０】
2010278482.tif 000012
【００９４】
まず、ＳＣ０８方式では、検証鍵ｐｋの要素を追加すると共に検証式を変形している。このとき、（１）正当な署名者との対話を行なえば代用鍵が生成できること、（２）正当な署名者との対話を行なわない限り、勝手に代用検証鍵を生成することができないことが考慮された。つまり、上記の条件（１）及び条件（２）を満たすように変形が施されているのである。
【００９５】
作本らは、まず、ＥｌＧａｍａｌ署名方式が「検証鍵を与えられても、検証式を満たすような電子署名を計算することはできない」という性質を持つことに着目した。そして、作本らは、このＥｌＧａｍａｌ署名方式が持つ性質と上記の式（２１）に示す検証式とを参照し、検証式中に現れる電子署名の要素ｒと検証鍵の要素ｙが対称的であれば「電子署名を与えられても検証式を満たすような検証鍵を計算することはできない」という性質を持つことに気づいた。ここで言う対称的とは、ａの肩（べき乗部分）にｂが、ｂの肩（べき乗部分）にａが乗るという形（ａｂ＊ｂａ）を意味する。
【００９６】
そこで、作本らは、このアイデアに基づき、下記の式（２２）のように検証鍵ｐｋにパラメータαを追加し、下記の式（２３）のように検証式を変形した。検証鍵ｐｋにパラメータαを追加したことで代用鍵の生成が可能になった。しかし、下記の式（２２）に示す検証鍵ｐｋに基づいて成立する下記の式（２３）の検証式を用いると、代用鍵生成者がオリジナルの署名鍵ｓｋを計算できてしまう。例えば、代用署名鍵ｓｋ’＝ｘ’、代用検証鍵ｐｋ’＝（ｙ’，α’）とすると、代用鍵生成者は、下記の式（２４）を知ることができるため、この式に基づいて署名者が秘密に保持すべきパラメータｋを算出することができてしまう。さらに、オリジナルの署名鍵ｓｋ＝ｘを用いて下記の式（２５）が成り立つことが分かっているため、パラメータｋを用いて下記の式（２５）から署名鍵ｓｋを算出することができてしまう。
【００９７】
【数１１】
2010278482.tif 000013
【００９８】
そこで、作本らは、上記の式（９）及び式（１０）に示すように、署名鍵ｓｋ及び検証鍵ｐｋに含まれるパラメータを二重化し、代用鍵生成者がオリジナルの署名鍵ｓｋを生成することができないようにした。もちろん、代用署名鍵ｓｋ’及び代用検証鍵ｐｋ’についても、それらに含まれるパラメータが二重化されている。なお、ＳＣ０８方式においては、代用鍵生成者が秘密に保持する代用署名鍵ｓｋ’を署名者が知得できないようにすること（上記の条件（４））も考慮されている。なお、代用鍵に関する上記の条件（３）、条件（４）に関しては、後述する代用鍵生成アルゴリズムにて実現される。以下、当該アイデアを具体化したＳＣ０８方式の代用鍵生成アルゴリズムについて説明する。
【００９９】
（代用鍵生成アルゴリズム）
図９を参照しながら、上記の式（４）で示した代用鍵生成アルゴリズムについて説明する。図９は、代用鍵生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、代用鍵生成アルゴリズムは対話プロトコルに基づくものであり、署名者と代用鍵生成者との対話を通じて実現されるものである。
【０１００】
代用鍵生成アルゴリズムにおいては、まず、署名者により署名鍵ｓｋが入力される（Ｓ１００）。但し、署名鍵ｓｋは代用鍵生成者に直接提供されない。また、代用鍵生成者によりランダムにＺｑの元ｘ１’，ｘ２’が選択され、下記の式（２６）及び式（２７）に示すｙ１’、ｙ２’が算出される（Ｓ１０２）。なお、ｘ１’、ｘ２’は、代用署名鍵ｓｋ’に含めるパラメータである。また、ｙ１’、ｙ２’は、代用検証鍵ｐｋ’に含めるパラメータである。次いで、代用鍵生成者から署名者にｙ１’、ｙ２’が提供される（Ｓ１０４）。次いで、署名者は、ランダムにＺｑの元ｗ’を選択する（Ｓ１０６）。次いで、署名者から代用鍵生成者にｗ’が提供される（Ｓ１０８）。
【０１０１】
ｗ’を取得すると、代用鍵生成者は、取得したｗ’を用いて下記の式（２８）に示すｃ’、及び下記の式（２９）に示すｚを算出する（Ｓ１１０）。次いで、代用鍵生成者から署名者にｚが提供される（Ｓ１１２）。このｚには代用署名鍵ｓｋ’の一部を成すパラメータｘ１’、ｘ２’が含まれているが、ｘ１’、ｘ２’を個々に特定できない形で署名者に提供されている点に注意されたい。次いで、ｚを取得すると、署名者は、上記の式（１４）、式（１５）、式（１６）、式（１７）に基づいてｃ、ｄ、ｙ、ｒを算出し、下記の式（３０）を満たすｋを算出する。署名者は、パラメータｋ１、ｋ２を保管していないことが多い。そのため、ここではパラメータｋ１、ｋ２を再計算しようとしているのである。
【０１０２】
もちろん、パラメータｋ１、ｋ２を保持している場合には、これらの演算を省略することができる。次いで、署名者は、上記の式（１２）を用いてｋ２を算出し、算出したｋ、ｋ２を下記の式（３１）に代入してｋ１を算出する。この段階でパラメータｋ１、ｋ２が得られたことになる。次いで、署名者は、下記の式（２８）に基づいてｃ’を算出する。さらに、署名者は、下記の式（３２）に基づいてｄ’を算出する。次いで、署名者は、下記の式（３３）、式（３４）に基づいてｙ’、ｒ’を算出する。さらに、署名者は、算出したｙ’を用いて式（３５）が成立するか否かを検証する。このとき、下記の式（３５）が不成立ならば署名者はエラーを出力して一連の処理を終了する。
【０１０３】
次いで、署名者は、下記の式（３６）を満たすα’を算出する（Ｓ１１４）。そして、署名者から代用鍵生成者にパラメータα’が提供される。このパラメータα’と、パラメータｙ１’、ｙ２’、ｗ’とを組み合わせることで代用検証鍵ｐｋ’が生成される。なお、代用署名鍵ｓｋ’にα’を含めることとすれば、この時点で代用署名鍵ｓｋ’も生成される。また、署名者が代用検証鍵ｐｋ’を生成し、代用署名者に提供するように構成されていてもよい。ＳＣ０８方式においては、以上説明した方法により、代用検証鍵ｐｋ’、及び代用署名鍵ｓｋ’が生成される。
【０１０４】
【数１２】
2010278482.tif 000014
【０１０５】
以上、ＳＣ０８方式について詳細に説明した。ここで注意すべき点は、代用鍵生成者が代用検証鍵ｐｋ’を手にする以前に、署名者が対話の中で代用検証鍵ｐｋ’を生成するための十分な情報を手に入れているという事実にある（図５を参照）。このことは、代用鍵生成者が代用検証鍵ｐｋ’により確定される前に、代用署名鍵ｓｋ’の一部情報が攻撃者に伝わる可能性を意味する。その結果、ＳＣ０８方式においては、代用鍵生成者が確定した代用検証鍵ｐｋ’に関する電子署名の偽造不可能性について安全性が保証されないということになる。
【０１０６】
この点について説明を補足する。ＳＣ０８方式に関する安全性の一部根拠を成すＥｌＧａｍａｌ署名方式で保証される安全性は次のような理想化された状況で保証される。ここで言う理想かされた状況とは、「まず、署名者が公開鍵ｐｋを生成し、次に署名者が攻撃者に公開鍵ｐｋを渡し、最後に攻撃者が公開鍵ｐｋの受理する電子署名を生成できたら攻撃者の勝ちとする」という状況である。この理想化された状況において攻撃者が勝つことができないという意味合いにおいてＥｌＣａｍａｌ署名方式の安全性は保証されている。逆に言えば、この制約を少しでも満たさない状況では安全性が保証されない。しかし、ＳＣ０８方式では、署名者が公開鍵を知る以前に、攻撃者が署名者の公開鍵を知ることができる構造を持つ。そのため、ＥｌＧａｍａｌ署名を基にした署名方式であっても、ＥｌＧａｍａｌ署名で保証されている安全性から保証されるものの対象外となってしまうのである。
【０１０７】
上記の問題を解決すべく、本件発明者は、ＳＣ０８方式に更なる工夫を加え、後述する各実施形態に係る代用鍵生成方法を考案した。当該各実施形態の技術は、上記の問題を解決すると共に、ＳＣ０８方式よりも効率的な代用鍵生成方法を提供するものである。以下、本発明の実施形態に係る代用鍵生成方法について詳細に説明していくことにする。
【０１０８】
＜２：第１実施形態＞
まず、本発明の第１実施形態について説明する。本実施形態は、上記のＳＣ０８方式が抱える安全性に関する問題点を解決し、「代用鍵生成者が代用検証鍵ｐｋ’の一部しか確定させていない段階で、その後に代用検証者が生成する代用検証鍵ｐｋ’の残りの部分を含めた全体を推定するに十分な情報が署名者に提供されないようにする」技術に関する。つまり、代用検証鍵ｐｋ’以外の代用検証鍵を生成することは署名者にも可能なので、代用鍵生成者が代用検証鍵ｐｋ’’を生成する際に代用検証鍵ｐｋ’の一部分だけを確定させた段階で、その残りの部分を含めた代用検証鍵ｐｋ’の全体を署名者が代用検証者よりも早く知ってしまうことがないようにするのである。以下、当該技術（本手法１）について詳細に説明する。
【０１０９】
［２−１：代用鍵生成方法］
まず、図１０を参照する。図１０は、本手法１の代用鍵生成アルゴリズム＜ＯＲＧ（ｓｋ），ＳＵＢ＞における処理の大まかな流れを示した説明図である。図１０に示すように、署名者及び代用鍵生成者の双方に共有情報として検証鍵ｐｋ、電子文書ｍ、電子署名σが入力されているものとする。また、署名者側では、署名鍵ｓｋも利用される。但し、代用鍵生成者が署名者の電子署名を偽造できないようにするため、署名鍵ｓｋが代用鍵生成者に直接提供されることはない。
【０１１０】
まず、代用鍵生成者により代用署名鍵ｓｋ’が生成され、その代用署名鍵ｓｋ’の情報を用いて代用検証鍵ｐｋ’の一部情報が生成される。そして、代用鍵生成者により生成された代用検証鍵ｐｋ’に含める一部情報は、代用鍵生成者から署名者に提供される（Ｓ１２２）。但し、このステップで提供される一部情報は、最終的にできる代用検証鍵ｐｋ’を推定するのには不十分な情報である。
【０１１１】
次いで、代用検証鍵ｐｋ’の一部情報を取得すると、署名者は、乱数を発生させ、その乱数と共に代用検証鍵ｐｋ’を生成するのに必要な署名鍵ｓｋに関する情報を代用鍵生成者に提供する（Ｓ１２４）。但し、このステップで提供される署名鍵ｓｋに関する情報は、代用鍵生成者が署名鍵ｓｋを推定するのに不十分な情報である。署名鍵ｓｋに関する情報を取得すると、代用鍵生成者は、代用検証鍵ｐｋ’を生成する（Ｓ１２６）。
【０１１２】
以上説明した方法により、代用署名鍵ｓｋ’及び代用検証鍵ｐｋ’が生成される。このように、本手法１においては代用検証鍵ｐｋ’が代用鍵生成者により生成される。また、代用鍵生成者が代用検証鍵ｐｋ’を確定する以前に、代用検証鍵ｐｋ’を生成するに十分な情報は署名者に与えられない。そのため、本手法１を用いることで、既に説明したＳＣ０８方式が抱える問題は解消される。但し、上記説明の中では具体的な演算方法について説明していない。そこで、図１０で示した各処理ステップの内容を実現するための具体的な演算アルゴリズムについて以下で詳細に説明する。但し、ここに示す具体的な演算式等は一例であり、種々の変形が可能である点については注意されたい。
【０１１３】
［２−２：アルゴリズム］
まず、代用鍵生成アルゴリズムの具体的な演算内容について説明するに先立ち、本手法１の鍵生成アルゴリズム、署名生成アルゴリズム、及び署名検証アルゴリズムについて順次説明する。なお、システムパラメータ生成アルゴリズムについてはＳＣ０８方式と実質的に同じであるため説明を省略する。また、これらのアルゴリズムは相互に関係するものであり、代用鍵生成アルゴリズムを実現するための本手法１に特徴的な構成を含んでいる。その後、代用鍵生成アルゴリズムについて説明する。
【０１１４】
（鍵生成アルゴリズム、署名生成アルゴリズム）
まず、図１１を参照しながら、上記の式（２）で示した鍵生成アルゴリズム、及び上記の式（３）に示した署名生成アルゴリズムについて説明する。図１１は、鍵生成アルゴリズム及び署名生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、鍵生成アルゴリズム及び署名生成アルゴリズムは、署名者により実行される。
【０１１５】
まず、鍵生成アルゴリズムについて説明する。鍵生成アルゴリズムにおいては、まず、ランダムにＺｑの元ｘ１、ｘ２が選択される（Ｓ１３０）。次いで、選択されたｘ１、ｘ２を用いて、下記の式（３７）及び式（３８）に示すようにｙ１、ｙ２が算出される（Ｓ１３２）。次いで、ランダムにＺｑ＊の元αが選択される（Ｓ１３４）。なお、ステップＳ１３４の処理順序は、適宜変更可能である。ここまでが鍵生成アルゴリズムの内容である。以上の演算により、下記の式（３９）に示す検証鍵ｐｋ、及び下記の式（４０）に示す署名鍵ｓｋが生成される。
【０１１６】
【数１３】
2010278482.tif 000015
【０１１７】
次に、署名生成アルゴリズムについて説明する。上記の式（３）に示した通り、署名生成アルゴリズムには、鍵生成アルゴリズムで生成された署名鍵ｓｋ、及び電子文書ｍが入力される。但し、検証鍵ｐｋも既に算出されていることから、検証鍵ｐｋを入力値に加えてもよい。このように入力値を変更すると、例えば、署名生成アルゴリズムに上記の式（３７）又は式（３８）で示されるｙ１、ｙ２と同じ演算式が含まれている場合、その演算処理を行わずに済む。以下の説明においては、上記の式（３７）又は式（３８）と同じ演算式が含まれている部分をそれぞれｙ１、ｙ２と表記することにする。
【０１１８】
署名生成アルゴリズムにおいては、まず、ランダムにＺｑ＊の元ｋ１が選択される（Ｓ１４０）。次に、選択されたｋ１を用いて下記の式（４１）に示すｒ１が算出される（Ｓ１４２）。次いで、ｒ１、ｘ１、ｘ２を用いて下記の式（４２）に示すｋ２が算出される（Ｓ１４４）。但し、ｈ３（…）は、ハッシュ関数である。なお、下記の式（４２）において、パラメータとして与えられるｒ１、ｘ１、ｘ２は、例えば、連結してからハッシュ関数ｈ３に入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。
【０１１９】
次いで、算出されたｋ２を用いて下記の式（４３）に示すｒ２が算出される（Ｓ１４６）。次いで、電子署名σを付す電子文書ｍ、上記の演算により算出されたパラメータｒ１、ｒ２、及び検証鍵ｐｋに含まれるｙ１、ｙ２（但し、ｘ１、ｘ２から生成可能。）を用いて下記の式（４４）及び式（４５）に示すパラメータｃ、ｄが算出される（Ｓ１４８）。但し、ｈ１（…）、ｈ２（…）はいずれもハッシュ関数である。また、パラメータｍ、ｒ１、ｒ２、ｙ１、ｙ２は、例えば、連結してから入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。
【０１２０】
次いで、算出されたパラメータｃ、ｄを用いて下記の式（４６）及び式（４７）に示すｙ及びｒが算出される（Ｓ１５０）。次いで、ステップＳ１３０〜Ｓ１５０において得られたパラメータを用いて下記の式（４８）を満たすＺｑの元ｓが算出される（Ｓ１５２）。但し、Ｈ（…）はハッシュ関数である。また、パラメータｃ、ｒ、ｙは、例えば、連結してから入力される。なお、パラメータの入力時に行う処理に関しては、連結に限定されない点に注意されたい。以上の演算により、下記の式（４９）に示す電子署名σが得られる。
【０１２１】
【数１４】
2010278482.tif 000016
【０１２２】
以上、本手法１の鍵生成アルゴリズム、及び署名生成アルゴリズムについて説明した。鍵生成アルゴリズムにおいては、生成される検証鍵ｐｋの構成がＳＣ０８方式から変更されている。一方、署名生成アルゴリズムにおいては、電子署名σの生成に用いるパラメータｃ、ｄの構成がＳＣ０８方式から変更されている。特に、パラメータｄを生成する際に、ハッシュ関数ｈ２に入力するパラメータの種類が変更されている点に注意されたい。この変更は、代用鍵生成者から署名者へと提供される情報がＳＣ０８方式よりも少ないことに起因する。逆に言えば、このような変更を行うことで、代用鍵生成者から署名者に提供される情報を低減させることができる。
【０１２３】
（署名検証アルゴリズム）
次に、図１２を参照しながら、上記の式（５）で示した署名検証アルゴリズムについて説明する。図１２は、署名検証アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、署名検証アルゴリズムは、検証者により実行される。
【０１２４】
まず、検証者は、公開されている検証鍵ｐｋ（式（３９）を参照）を取得する（Ｓ１６０）。さらに、検証者は、署名者から電子署名σ（式（４９）を参照）、及び電子文書ｍを取得する（Ｓ１６２）。検証者は、これらの取得した情報を署名検証アルゴリズムに入力して電子署名σを検証する。なお、システムパラメータｃｐも予め取得しているものとする。
【０１２５】
署名検証アルゴリズムにおいては、まず、上記の式（４４）、式（４５）、式（４６）、及び式（４７）に基づいてパラメータｃ、ｄ、ｙ、ｒが算出される（Ｓ１６４）。次いで、算出したパラメータが下記の式（５０）に示す検証式Ａに代入され、検証式Ａの成否が確認される（Ｓ１６６、Ｓ１６８）。検証式Ａが成り立つ場合、その電子署名σが正当であるとみなし、「受理」を示す出力値ｖｏｕｔ＝１を出力して（Ｓ１７０）一連の処理を終了する。一方、検証式Ａが不成立の場合、エラーを示す出力値ｖｏｕｔ＝０を出力して（Ｓ１７２）一連の処理を終了する。以上の演算により、電子文書ｍに対する電子署名σの正当性が検証される。なお、外見上、検証式Ａの形が本手法１とＳＣ０８方式とで同じである点に注意されたい。
【０１２６】
【数１５】
2010278482.tif 000017
【０１２７】
（代用鍵生成アルゴリズム）
次に、図１３を参照しながら、上記の式（４）で示した代用鍵生成アルゴリズムについて説明する。図１３は、代用鍵生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、代用鍵生成アルゴリズムは対話プロトコルに基づくものであり、署名者と代用鍵生成者との対話を通じて実現されるものである。但し、ＳＣ０８方式とは異なり、本手法１においては代用検証鍵を代用鍵生成者の側で生成する。
【０１２８】
代用鍵生成アルゴリズムにおいては、まず、署名者により署名鍵ｓｋが入力される（Ｓ１８０）。但し、署名鍵ｓｋは代用鍵生成者に直接提供されない。また、代用鍵生成者によりランダムにＺｑの元ｘ１’が選択され、下記の式（５１）に示すｙ１’が算出される（Ｓ１８２）。次いで、代用鍵生成者から署名者にｙ１’が提供される（Ｓ１８４）。ステップＳ１８４において署名者に提供されるパラメータｙ１’を用いても、署名者が代用検証鍵を生成できない点に注意されたい。次いで、署名者は、ランダムにＺｑの元ｗを選択する（Ｓ１８６）。
【０１２９】
次いで、署名者は、上記の式（４４）、式（４５）、式（４６）、式（４７）に基づいてｃ、ｄ、ｙ、ｒを算出し、下記の式（５２）を満たすｋを算出する。署名者は、パラメータｋ１、ｋ２を保管していないことが多い。そのため、ここではパラメータｋ１、ｋ２を再計算しようとしているのである。もちろん、パラメータｋ１、ｋ２を保持している場合には、これらの演算を省略することができる。
【０１３０】
次いで、署名者は、上記の式（４２）を用いてｋ２を算出し、算出したｋ、ｋ２を下記の式（５３）に代入してｋ１を算出する。この段階でパラメータｋ１、ｋ２が得られたことになる。次いで、署名者は、下記の式（５４）に基づいてｄ”を算出する。さらに、署名者は、下記の式（５５）に基づいてｋ”を算出し（Ｓ１８６）、乱数ｗと共に代用鍵生成者に提供する（Ｓ１８８）。この段階で署名者が保持する情報からは、代用鍵生成者が最終的に生成する代用検証鍵を推定できない点に注意されたい。
【０１３１】
署名者から乱数ｗ、及びパラメータｋ”を取得すると、代用鍵生成者は、ランダムにＺｑの元ｘ２”を選択する。次いで、代用鍵生成者は、署名者から取得した乱数ｗ、及び選択したパラメータｘ１’を用いて下記の式（５６）に示すパラメータｘ１”を算出する。さらに、代用鍵生成者は、下記の式（５７）、式（５８）に基づいてパラメータｙ１”、ｙ２”を算出する。このようにして得られたパラメータｘ１”、ｘ２”は、代用署名鍵ｓｋ”に含めるものである。また、パラメータｙ１”、ｙ２”は、代用検証鍵ｐｋ”に含めるものである。
【０１３２】
次いで、代用鍵生成者は、代用検証鍵ｐｋ”で受理されるべき電子署名σが付された電子文書ｍ、電子署名σに含まれるパラメータｒ１、ｒ２、代用検証鍵ｐｋ”に含めるべきパラメータｙ１”、ｙ２”を用いて、下記の式（５９）によりパラメータｃ”を算出する。さらに、代用鍵生成者は、下記の式（５４）に基づいてパラメータｄ”を算出する。このとき、ｙ１’ｗに代えてｙ１”をハッシュ関数ｈ２に代入するように構成されていてもよい。次いで、代用鍵生成者は、下記の式（６０）、式（６１）に基づいてパラメータｙ”、ｒ”を算出する。
【０１３３】
さらに、代用鍵生成者は、これまでに得られたパラメータｄ”を用いて下記の式（６１）が成り立つか否か、ｗ∈Ｚｑ＊であるか否かを検証する。いずれかの条件が満たされない場合、代用鍵生成アルゴリズムに係る一連の処理を終了する。両条件が満たされた場合、代用鍵生成者は、下記の式（６３）を満たすα”を算出し（Ｓ１９０）、下記の式（６４）、式（６５）に示す代用検証鍵ｐｋ”、代用署名鍵ｓｋ”を確定する。以上説明した方法により、代用検証鍵ｐｋ”、及び代用署名鍵ｓｋ”が生成される。
【０１３４】
上記の通り、本手法１においては、代用鍵生成者から署名者に提供される情報は、パラメータｙ１’だけである。そのため、署名者は、代用鍵生成者が代用検証鍵ｐｋ”を確定する以前に、代用検証鍵ｐｋ”を推定するに足りる十分な情報を得ることができない。そのため、代用検証鍵ｐｋ”の確定前に、代用鍵生成者以外の者が代用検証鍵ｐｋ”を推定できてしまうというＳＣ０８方式の問題は解決されている。
【０１３５】
また、本手法１の場合、対話の中で署名者と代用鍵生成者との間の通信回数及び通信量が低減されている。図９に示したＳＣ０８方式の代用鍵生成アルゴリズムの場合、２往復のインタラクションが発生している。また、セキュリティパラメータのデータサイズをａとすると、ＳＣ０８方式の場合、対話の中で送受信されるデータサイズは５＊ａである。その内訳は、代用鍵生成者から署名者に送信されるパラメータｙ１’、ｙ２’、ｚの３つと、署名者から代用鍵生成者に送信されるパラメータｗ’、α’の２つである。
【０１３６】
一方、図１３に示した本手法１の代用鍵生成アルゴリズムの場合、１往復のインタラクションしか発生していない。さらに、本手法１の場合、対話の中で送受信されるデータサイズは３＊ａで済んでいる。その内訳は、代用鍵生成者から署名者に送信されるパラメータｙ１’の１つと、署名者から代用鍵生成者に送信されるパラメータｗ、ｋ’の２つである。また、ＳＣ０８方式の代用検証鍵ｐｋ’と、本手法１の代用検証鍵ｐｋ”とを比較すると、代用検証鍵ｐｋ’のデータサイズが４＊ａであるのに対し、代用検証鍵ｐｋ”のデータサイズが３＊ａで済んでいる。
【０１３７】
このように本手法１はＳＣ０８方式に比べて効率化されており、通信負荷の観点や代用検証鍵のデータサイズの観点から見ても、ＳＣ０８方式に比べて本手法１の方が有利である。
【０１３８】
【数１６】
2010278482.tif 000018
2010278482.tif 000019
【０１３９】
［２−３：端末の機能構成］
ここで、図１４を参照しながら、上記の各アルゴリズムを実行可能な本手法１のシステム構成について簡単に説明する。図１４には、署名者が利用する署名者端末１００、検証者が利用する検証者端末２００、及び代用鍵生成者が利用する代用鍵生成者端末３００の機能構成が示されている。また、署名者端末１００、検証者端末２００、代用鍵生成者端末３００はネットワーク１０で接続されているものとする。なお、システム管理者及び認証局の端末については記載を省略した。
【０１４０】
（署名者端末１００）
まず、署名者端末１００の機能構成について説明する。図１４に示すように、署名者端末１００は、主に、記憶部１０２と、鍵生成部１０４と、署名生成部１０６と、通信部１０８と、署名鍵関連情報生成部１１０とを有する。
【０１４１】
記憶部１０２は、システムパラメータｃｐ、電子文書ｍ、及び各アルゴリズムを実行するためのプログラムを格納するための手段である。鍵生成部１０４は、記憶部１０２からシステムパラメータｃｐ、及び鍵生成アルゴリズムの実行プログラムを読み出し、署名鍵ｓｋ及び検証鍵ｐｋを生成する。鍵生成部１０４で生成された署名鍵ｓｋ及び検証鍵ｐｋは、署名生成部１０６に入力される。
【０１４２】
署名生成部１０６は、記憶部１０２からシステムパラメータｃｐ、及び署名生成アルゴリズムの実行プログラムを読み出し、入力された署名鍵ｓｋ（検証鍵ｐｋ）及び電子文書ｍを用いて当該電子文書ｍに付する電子署名σを生成する。署名生成部１０６で生成された電子署名σ及び電子文書ｍは、通信部１０８によりネットワーク１０を介して検証者端末２００に提供される。
【０１４３】
署名鍵関連情報生成部１１０は、代用鍵が生成される際に、乱数ｗを生成し、代用検証鍵ｐｋ”の生成に用いるパラメータｋ”を算出する手段である。まず、署名鍵関連情報生成部１１０は、代用鍵生成者端末３００（代用検証鍵生成部３０６）から代用検証鍵ｐｋ”に関連するパラメータｙ１’を取得し、そのパラメータｙ１’を利用してパラメータｋ”を生成する。そして、署名鍵関連情報生成部１１０は、パラメータｋ”、ｗを代用鍵生成者端末３００に提供する。
【０１４４】
このように、署名者端末１００には、本手法１に係る上記の署名者が実行すべき各アルゴリズムを実行する機能が搭載される。その結果、署名者端末１００を用いることで、本手法による鍵更新方法が実現される。
【０１４５】
（検証者端末２００）
次に、検証者端末２００の機能構成について説明する。図１４に示すように、検証者端末２００は、主に、通信部２０２と、パラメータ生成部２０４と、記憶部２０６と、検証処理部２０８とを有する。記憶部２０６には、システムパラメータｃｐの他、検証者が実行すべきアルゴリズムの実行プログラム等が格納される。
【０１４６】
通信部２０２によりネットワーク１０を介して署名者端末１００から電子文書ｍ及び電子署名σが取得されると、それら電子文書ｍ及び電子署名σは、パラメータ生成部２０４に入力される。パラメータ生成部２０４では、検証式に入力するために必要なパラメータが算出される。パラメータ生成部２０４で算出されたパラメータは、検証処理部２０８に入力される。検証処理部２０８では、パラメータ生成部２０４で算出されたパラメータ、検証鍵ｐｋ、電子文書ｍ、及び電子署名σを検証式に入力し、検証式の成否に基づいて電子署名σの受理／拒否を判断する。
【０１４７】
このように、検証者端末２００には、本手法に係る上記の検証者が実行すべき各アルゴリズムを実行する機能が搭載されている。その結果、検証者端末２００を用いることで、本手法による鍵更新方法が実現される。
【０１４８】
（代用鍵生成者端末３００）
次に、代用鍵生成者端末３００の機能構成について説明する。図１４に示すように、代用鍵生成者端末３００は、主に、記憶部３０２と、代用署名鍵生成部３０４と、代用検証鍵生成部３０６と、通信部３０８とを有する。記憶部３０２には、システムパラメータｃｐの他、代用鍵生成者が実行すべきアルゴリズムの実行プログラム等が格納される。
【０１４９】
代用署名鍵生成部３０４は、代用鍵を生成する際、記憶部３０２に格納されたシステムパラメータｃｐを読み出し、代用署名鍵ｓｋ”に関するパラメータｘ１’、ｘ２”を生成する。代用署名鍵生成部３０４により生成されたパラメータｘ１’、ｘ２”は、代用検証鍵生成部３０６に入力される。また、代用署名鍵生成部３０４は、代用検証鍵生成部３０６から代用署名鍵ｓｋ”の生成に十分な情報が入力された場合、その情報を用いて代用署名鍵ｓｋ”を生成する。
【０１５０】
代用署名鍵生成部３０４からパラメータｘ１’ｘ２”が入力されると、代用検証鍵生成部３０６は、代用検証鍵生成アルゴリズムに基づいて署名者端末１００（署名鍵関連情報生成部１１０）との間で対話を実行し、代用検証鍵ｐｋ”の生成に十分なパラメータｋ”、ｗを取得する。この対話の中で、代用検証鍵生成部３０６は、代用検証鍵ｐｋ”に関する情報としてパラメータｙ１’しか署名者端末１００に提供しない。そのため、署名者端末１００において、この後に確定される代用検証鍵ｐｋ”をこの段階で推定することはできない。
【０１５１】
署名者端末１００からパラメータｋ”、ｗを取得すると、代用検証鍵生成部３０６は、パラメータｋ”、ｗを用いて代用検証鍵ｐｋ”を生成する。この生成工程において算出される代用署名鍵ｓｋ”に含めるべきパラメータは、代用検証鍵生成部３０６から代用署名鍵生成部３０４に入力される。また、代用検証鍵生成部３０６で生成された代用検証鍵ｐｋ”は、通信部３０８によりネットワーク１０を介して検証者端末２００に提供される。なお、図１４には明示していないが、代用鍵生成者端末３００には、例えば、代用署名鍵ｓｋ”を用いて電子署名を生成する署名生成手段等が更に設けられていてもよい。
【０１５２】
以上、本手法１に係る代用鍵生成方法について説明した。本手法１を用いると、ＳＣ０８方式に比べて、より効率的で安全性の高い鍵代用可能電子署名システムが実現される。なお、上記説明の中で示した具体的な演算内容に関しては、本手法１のアイデアを承継可能な範囲内で任意に変更することが可能である。もちろん、その変更後の演算内容についても、本手法１の技術的範囲に属することは言うまでもない。
【０１５３】
＜３：第２実施形態＞
次に、本発明の第２実施形態について説明する。本実施形態は、上記の第１実施形態と同様に、ＳＣ０８方式が抱える安全性に関する問題点を解決し、「代用鍵生成者が代用検証鍵ｐｋ’の一部しか確定させていない段階で、その後に代用検証者が生成する代用検証鍵ｐｋ’の残りの部分を含めた全体を推定するに十分な情報が署名者に提供されないようにする」ことを実現するものである。
【０１５４】
但し、本実施形態の方法は、代用検証鍵ｐｋ”に関する情報を秘匿した形で代用鍵生成者から署名者に提供する点において異なるアイデアを含んでいる。以下、当該技術（本手法２）について詳細に説明する。なお、本手法２は、技術的思想の基本的な部分で本手法１と共通しており、図１０に示した代用鍵生成方法の大まかな流れや、本手法２に係る代用鍵生成方法を実現するための端末構成については上記の本手法１と実質的に同じである。従って、これらの重複部分については説明を省略する。
【０１５５】
［３−１：アルゴリズム］
まず、代用鍵生成アルゴリズムの具体的な演算内容について説明するに先立ち、本手法２の鍵生成アルゴリズム、署名生成アルゴリズム、及び署名検証アルゴリズムについて順次説明する。なお、システムパラメータ生成アルゴリズムについてはＳＣ０８方式と実質的に同じであるため説明を省略する。また、これらのアルゴリズムは相互に関係するものであり、代用鍵生成アルゴリズムを実現するための本手法２に特徴的な構成を含んでいる。その後、代用鍵生成アルゴリズムについて説明する。
【０１５６】
（鍵生成アルゴリズム、署名生成アルゴリズム）
まず、図１５を参照しながら、上記の式（２）で示した鍵生成アルゴリズム、及び上記の式（３）に示した署名生成アルゴリズムについて説明する。図１５は、鍵生成アルゴリズム及び署名生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、鍵生成アルゴリズム及び署名生成アルゴリズムは、署名者により実行される。
【０１５７】
まず、鍵生成アルゴリズムについて説明する。鍵生成アルゴリズムにおいては、まず、ランダムにＺｑの元ｘ１、ｘ２が選択される（Ｓ２００）。次いで、選択されたｘ１、ｘ２を用いて、上記の式（３７）及び式（３８）に示すようにｙ１、ｙ２が算出される（Ｓ２０２）。次いで、ランダムにＺｑ＊の元αが選択される（Ｓ２０４）。なお、ステップＳ２０４の処理順序は、適宜変更可能である。ここまでが鍵生成アルゴリズムの内容である。以上の演算により、下記の式（３９）に示す検証鍵ｐｋ、及び下記の式（４０）に示す署名鍵ｓｋが生成される。このように、本手法２の鍵生成アルゴリズムは本手法１のものと同じである。
【０１５８】
次に、署名生成アルゴリズムについて説明する。上記の式（３）に示した通り、署名生成アルゴリズムには、鍵生成アルゴリズムで生成された署名鍵ｓｋ、及び電子文書ｍが入力される。但し、検証鍵ｐｋも既に算出されていることから、検証鍵ｐｋを入力値に加えてもよい。このように入力値を変更すると、例えば、署名生成アルゴリズムに上記の式（３７）又は式（３８）で示されるｙ１、ｙ２と同じ演算式が含まれている場合、その演算処理を行わずに済む。以下の説明においては、上記の式（３７）又は式（３８）と同じ演算式が含まれている部分をそれぞれｙ１、ｙ２と表記することにする。
【０１５９】
署名生成アルゴリズムにおいては、まず、ランダムにＺｑ＊の元ｋ１が選択される（Ｓ２１０）。次に、選択されたｋ１を用いて上記の式（４１）に示すｒ１が算出される（Ｓ２１２）。次いで、ｒ１、ｘ１、ｘ２を用いて上記の式（４２）に示すｋ２が算出される（Ｓ２１４）。次いで、算出されたｋ２を用いて上記の式（４３）に示すｒ２が算出される（Ｓ２１６）。ここまでの処理ステップは本手法１のものと同じである。
【０１６０】
次いで、パラメータｙ２を用いて下記の式（６６）に示すＹを算出すると共に、電子署名σを付す電子文書ｍ、上記の演算により算出されたパラメータｒ１、ｒ２、及び検証鍵ｐｋに含まれるｙ１、ｙ２（但し、ｘ１、ｘ２から生成可能。）を用いて上記の式（４４）及び下記の式（６７）に示すパラメータｃ、ｄが算出される（Ｓ２１８）。但し、ｈ４（…）はハッシュ関数である。このように、本手法２においては新たなパラメータＹが導入される。
【０１６１】
次いで、算出されたパラメータｃ、ｄを用いて上記の式（４６）及び式（４７）に示すｙ及びｒが算出される（Ｓ２２０）。次いで、ステップＳ２００〜Ｓ２２０において得られたパラメータを用いて上記の式（４８）を満たすＺｑの元ｓが算出される（Ｓ２２２）。以上の演算により、上記の式（４９）に示す電子署名σが得られる。
【０１６２】
【数１７】
2010278482.tif 000020
【０１６３】
以上、本手法１の鍵生成アルゴリズム、及び署名生成アルゴリズムについて説明した。上記の通り、本手法２においては、パラメータｄを生成する際に新たなパラメータＹが導入されている。このパラメータＹは、上記の式（６６）に示すように代用検証鍵ｐｋ”に関する情報である。但し、ハッシュ値に変換されている点に注意されたい。なお、ハッシュ値に変換する理由については代用鍵生成アルゴリズムの説明の中で述べる。
【０１６４】
また、上記の式（４８）から理解される通り、パラメータｄは、署名者が秘匿すべきパラメータｋ１、ｋ２を特定されないようにするものである。本手法１においては、パラメータｄを生成する際に、代用検証鍵ｐｋ”に関する情報としてパラメータｙ１のみが用いられていた。一方、本手法２においては、パラメータｙ１に加え、パラメータｙ２に関連するパラメータＹが追加されている。そのため、本手法２を用いることで、パラメータｄを特定するために知るべき情報が増えた分だけ、パラメータｋ１、ｋ２に対する安全性が高まる。
【０１６５】
（署名検証アルゴリズム）
次に、図１６を参照しながら、上記の式（５）で示した署名検証アルゴリズムについて説明する。図１６は、署名検証アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、署名検証アルゴリズムは、検証者により実行される。
【０１６６】
まず、検証者は、公開されている検証鍵ｐｋ（式（３９）を参照）を取得する（Ｓ２３０）。さらに、検証者は、署名者から電子署名σ（式（４９）を参照）、及び電子文書ｍを取得する（Ｓ２３２）。検証者は、これらの取得した情報を署名検証アルゴリズムに入力して電子署名σを検証する。なお、システムパラメータｃｐも予め取得しているものとする。
【０１６７】
署名検証アルゴリズムにおいては、まず、上記の式（４４）、式（６６）及び式（６７）に基づいてパラメータｃ、Ｙ、ｄが算出され、さらに、上記の式（４６）、及び式（４７）に基づいてパラメータｙ、ｒが算出される（Ｓ２３４）。次いで、算出したパラメータが上記の式（５０）に示す検証式Ａに代入され、検証式Ａの成否が確認される（Ｓ２３６、Ｓ２３８）。なお、本手法２においても、上記の本手法１と同じ検証式Ａが用いられている点に注意されたい。
【０１６８】
検証式Ａが成り立つ場合、その電子署名σが正当であるとみなし、「受理」を示す出力値ｖｏｕｔ＝１を出力して（Ｓ２４０）一連の処理を終了する。一方、検証式Ａが不成立の場合、エラーを示す出力値ｖｏｕｔ＝０を出力して（Ｓ２４２）一連の処理を終了する。以上の演算により、電子文書ｍに対する電子署名σの正当性が検証される。
【０１６９】
（代用鍵生成アルゴリズム）
次に、図１７を参照しながら、上記の式（４）で示した代用鍵生成アルゴリズムについて説明する。図１７は、代用鍵生成アルゴリズムの具体的な演算内容について、その一例を示す説明図である。なお、代用鍵生成アルゴリズムは対話プロトコルに基づくものであり、署名者と代用鍵生成者との対話を通じて実現されるものである。なお、本手法２においても、本手法１と同様に、代用検証鍵を代用鍵生成者の側で生成する。
【０１７０】
代用鍵生成アルゴリズムにおいては、まず、署名者により署名鍵ｓｋが入力される（Ｓ２５０）。但し、署名鍵ｓｋは代用鍵生成者に直接提供されない。また、代用鍵生成者によりランダムにＺｑの元ｘ１’、ｘ２”が選択され、下記の式（６８）、式（６９）に示すパラメータｙ１’、ｙ２”が算出される。さらに、下記の式（７０）に基づいてパラメータＹ”が算出される（Ｓ２５２）。次いで、代用鍵生成者から署名者にパラメータｙ１’、Ｙ”が提供される（Ｓ２５４）。
【０１７１】
本手法２においては、本手法１とは異なり、ステップＳ２５４において代用検証鍵ｐｋ”に含める２つのパラメータｙ１’、ｙ２”に関する情報が署名者に提供される。代用検証鍵ｐｋ”に含まれるパラメータｙ１”は、署名者が提供するパラメータｗにより生成可能である。そのため、一見するとＳＣ０８方式と同じ２つのパラメータｙ１”、ｙ２”が署名者の手に渡っているように見える。しかし、パラメータｙ２”はハッシュ値Ｙ”に変換されているため、ハッシュ値Ｙ”とパラメータｙ１”から署名者が代用検証鍵ｐｋ”を生成することはできない。つまり、本手法１と同等の安全性が確保されている。
【０１７２】
さて、パラメータｙ１’、Ｙ”を取得すると、署名者は、ランダムにＺｑの元ｗを選択する。次いで、署名者は、上記の式（４４）、式（６６）、式（６７）、式（４６）、式（４７）に基づいてｃ、Ｙ、ｄ、ｙ、ｒを算出し、上記の式（５２）を満たすｋを算出する。署名者は、パラメータｋ１、ｋ２を保管していないことが多い。そのため、ここではパラメータｋ１、ｋ２を再計算しようとしているのである。もちろん、パラメータｋ１、ｋ２を保持している場合には、これらの演算を省略することができる。
【０１７３】
次いで、署名者は、上記の式（４２）を用いてｋ２を算出し、算出したｋ、ｋ２を上記の式（５３）に代入してｋ１を算出する。この段階でパラメータｋ１、ｋ２が得られたことになる。次いで、署名者は、下記の式（７１）に基づいてｄ”を算出する。さらに、署名者は、上記の式（５５）に基づいてｋ”を算出し（Ｓ２５６）、乱数ｗと共に代用鍵生成者に提供する（Ｓ２５８）。この段階で署名者が保持する情報からは、代用鍵生成者が最終的に生成する代用検証鍵を推定できない点に注意されたい。
【０１７４】
署名者から乱数ｗ、及びパラメータｋ”を取得すると、代用鍵生成者は、取得した乱数ｗ、及び選択したパラメータｘ１’を用いて上記の式（５６）に示すパラメータｘ１”を算出する。さらに、代用鍵生成者は、上記の式（５７）、式（５８）に基づいてパラメータｙ１”、ｙ２”を算出する。このようにして得られたパラメータｘ１”、ｘ２”は、代用署名鍵ｓｋ”に含めるものである。また、パラメータｙ１”、ｙ２”は、代用検証鍵ｐｋ”に含めるものである。
【０１７５】
次いで、代用鍵生成者は、代用検証鍵ｐｋ”で受理されるべき電子署名σが付された電子文書ｍ、電子署名σに含まれるパラメータｒ１、ｒ２、代用検証鍵ｐｋ”に含めるべきパラメータｙ１”、ｙ２”を用いて、上記の式（５９）によりパラメータｃ”を算出する。さらに、代用鍵生成者は、上記の式（７１）に基づいてパラメータｄ”を算出する。このとき、ｙ１’ｗに代えてｙ１”をハッシュ関数ｈ２に代入するように構成されていてもよい。次いで、代用鍵生成者は、上記の式（６０）、式（６１）に基づいてパラメータｙ”、ｒ”を算出する。
【０１７６】
さらに、代用鍵生成者は、これまでに得られたパラメータｄ”を用いて上記の式（６１）が成り立つか否か、ｗ∈Ｚｑ＊であるか否かを検証する。いずれかの条件が満たされない場合、代用鍵生成アルゴリズムに係る一連の処理を終了する。両条件が満たされた場合、代用鍵生成者は、上記の式（６３）を満たすα”を算出し（Ｓ２６０）、上記の式（６４）、式（６５）に示す代用検証鍵ｐｋ”、代用署名鍵ｓｋ”を確定する。以上説明した方法により、代用検証鍵ｐｋ”、及び代用署名鍵ｓｋ”が生成される。
【０１７７】
上記の通り、本手法２において、代用鍵生成者から署名者に提供される情報は、パラメータｙ１’、Ｙ”である。しかし、パラメータＹ”は、代用検証鍵ｐｋ”に関する情報ｙ２”のハッシュ値である。そのため、署名者は、代用鍵生成者が代用検証鍵ｐｋ”を確定する以前に、代用検証鍵ｐｋ”を推定するに足りる十分な情報を得ることができない。そのため、代用検証鍵ｐｋ”の確定前に、代用鍵生成者以外の者が代用検証鍵ｐｋ”を推定できてしまうというＳＣ０８方式の問題は解決されている。また、本手法２もＳＣ０８方式に比べて効率化されている。
【０１７８】
【数１８】
2010278482.tif 000021
【０１７９】
＜４：第１及び第２実施形態に係る変形例＞
これまで、本発明の第１及び第２実施形態に係る代用鍵生成方法について述べてきた。しかし、上記説明においては署名者側で用意した電子文書及び電子署名の組を受理する代用鍵の生成方法についてしか言及されていない。そこで、上記の第１及び第２実施形態に係る代用鍵生成方法を用いて、代用鍵生成者が用意した電子文書及びその電子文書に付される電子署名の組を受理する代用鍵の生成方法（以下、本変形例）について簡単に述べる。
【０１８０】
［４−１：代用鍵生成方法］
以下、図１８を参照しながら、本変形例に係る代用鍵生成方法について簡単に説明する。図１８に示すように、代用鍵生成者は、電子署名を付したい電子文書ｍを用意する。このとき、署名者も署名鍵ｓｋを用意する。まず、代用鍵生成者は、電子文書ｍ、代用検証鍵ｐｋ’に含める一部情報を署名者に提供する（Ｓ２７２）。このとき提供される情報は、上記の本手法１、２と同様である。これら情報を取得した署名者は、自身の署名鍵ｓｋを用いて電子文書ｍに対する電子署名σを生成する（Ｓ２７４）。
【０１８１】
さらに、署名者は、代用鍵生成者から取得した代用検証鍵ｐｋ’に関する情報、及び署名鍵ｓｋに関する情報を用いて、代用検証鍵ｐｋ’を生成するのに必要な情報を算出し、電子署名σと共に代用鍵生成者に提供する（Ｓ２７６）。これら情報及び電子署名σを取得した代用鍵生成者は、代用検証鍵ｐｋ’を生成する（Ｓ２７８）。これらの処理を実行することにより、代用鍵生成者は、電子文書ｍに対する電子署名σ、当該電子文書ｍ及び電子署名σを受理する代用検証鍵ｐｋ’、及び当該代用検証鍵ｐｋ’とペアを成す代用署名鍵ｓｋ’を得ることができる。
【０１８２】
このような構成にすることで、代用鍵生成者の側で用意した電子文書ｍに対する電子署名σについても代用鍵を生成することができる。こうした変形は実施の態様に応じて適宜行うことができる。また、当該変形例からも理解される通り、上記の本手法１、２で提案した技術的特徴を踏襲する範囲においては上記の本手法１、２と同等の効果が得られる。従って、こうした変形についても、本発明に係る第１及び第２実施形態の技術的範囲に属すると言える。
【０１８３】
＜５：端末のハードウェア構成＞
上記の署名者端末１００、検証者端末２００、代用鍵生成者端末３００が有する各構成要素の機能は、例えば、図１９に示す情報処理装置のハードウェア構成を用いて実現することが可能である。つまり、当該各構成要素の機能は、コンピュータプログラムを用いて図１９に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０１８４】
図１９に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０１８５】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０１８６】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラが用いられることもある。
【０１８７】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等が用いられる。つまり、出力部９１８は、取得した情報を利用者に対して視覚的又は聴覚的に通知する手段である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０１８８】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０１８９】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０１９０】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０１９１】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は各種通信用のモデム等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０１９２】
＜６：応用例＞
ここで、上記の第１及び第２実施形態に係る代用鍵生成方法の応用例について述べる。当該代用鍵生成方法は、ある電子文書ｍに対し、ある署名鍵ｓｋと検証鍵ｐｋとのペアを用いて生成された電子署名σを受理する代用検証鍵ｐｋ”の生成方法に関する。電子文書ｍ、電子署名σの組（ｍ，σ）を受理する代用検証鍵ｐｋ”の利用方法としては、例えば、署名鍵ｓｋが露呈した場合に、その署名鍵ｓｋ及び検証鍵ｐｋを代用検証鍵ｐｋ”及び代用署名鍵ｓｋ”に置き換える鍵更新方法が考えられる。
【０１９３】
さらに、代用検証鍵ｐｋ”の特性を生かして、当該代用鍵生成方法を後述するＰＫＩや代理人署名方式等に応用する方法が考えられる。もちろん、当該代用鍵生成方法の応用範囲はこれらの例に限定されるものではないが、当該代用鍵生成方法の適用範囲を拡充するための一助とすべく、ここでは具体例としてＰＫＩへの応用、代理人署名方式への応用、責任分担型電子署名への応用について紹介する。なお、ここで紹介する応用例には、上記の第１及び第２実施形態に係る代用鍵生成方法の技術がいずれも適用可能である。
【０１９４】
［６−１：ＰＫＩへの応用］
まず、図２１、図２２を参照しながら、上記の第１及び第２実施形態に係る代用鍵生成方法をＰＫＩへ応用する方法（以下、応用例１）について説明する。図２１は、この応用例１に係る方法を実現することが可能なＰＫＩシステムの一例を示す説明図である。また、図２２は、この応用例１に係る全体的な処理の流れを示す説明図である。但し、応用例１は、認証局による公開鍵（検証鍵に相当）の証明方法に上記代用鍵生成方法を応用するものである。
【０１９５】
ＰＫＩ（Ｐｕｂｌｉｃ  Ｋｅｙ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）とは、ある公開鍵ｐｋを所有するユーザのＩＤ（Ｉｄｅｎｔｉｔｙ）について、認証局（ＣＡ）が審査を行い、ユーザのＩＤと公開鍵ｐｋとをひも付けする仕組みのことを言う。なお、ＣＡは、Ｃｅｒｔｉｆｉｃａｔｉｏｎ  Ａｕｔｈｏｒｉｔｙの略である。応用例１におけるＰＫＩの仕組みは、例えば、次のような６つのアルゴリズムの組で表現される。
【０１９６】
（Ａ１）システムパラメータ生成アルゴリズム
（Ａ２）ＣＡ鍵生成アルゴリズム
（Ａ３）鍵登録アルゴリズム（対話プロトコル）
（Ａ４）署名生成アルゴリズム
（Ａ５）署名検証アルゴリズム
（Ａ６）検証鍵検証アルゴリズム
【０１９７】
（Ａ１）のシステムパラメータ生成アルゴリズムは、システム管理者により用いられるものであり、上記のＳＣ０８方式におけるシステムパラメータ生成アルゴリズムＳｅｔｕｐＫＳＳ（図６を参照）に相当する。
【０１９８】
（Ａ２）のＣＡ鍵生成アルゴリズムは、認証局により用いられるものであり、認証局が利用する認証局固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成するアルゴリズムである。ＣＡ鍵生成アルゴリズムで生成された公開鍵ｐｋは公開され、認証局が発行する証明書を検証するために用いられる。ＣＡ鍵生成アルゴリズムで生成された秘密鍵ｓｋは、認証局において秘密に管理される。
【０１９９】
また、認証局において秘密に管理される秘密鍵ｓｋは、後述するユーザ検証鍵ｐｋ”を生成する際に用いられる。なお、認証局が発行する証明書は、ユーザ検証鍵ｐｋ”とユーザＩＤとがひも付けられていることを証明するものである。また、ＣＡ鍵生成アルゴリズムは、上記の第１及び第２実施形態に係る鍵生成アルゴリズムＧｅｎＫＳＳ（図１１、図１５を参照）に相当するものである。但し、先の説明における署名者ではなく認証局が用いる点に注意されたい。
【０２００】
（Ａ３）の鍵登録アルゴリズムは、ユーザが利用するユーザ署名鍵ｓｋ”及びユーザ検証鍵ｐｋ”を生成すると共に、当該ユーザ検証鍵ｐｋ”の正当性を証明するための証明書を生成するアルゴリズムである。鍵登録アルゴリズムは、対話プロトコルに基づいて認証局とユーザとの間で実行される。鍵登録アルゴリズムで生成されたユーザ検証鍵ｐｋ”は公開され、ユーザ署名鍵ｓｋ”を用いて生成される電子署名の検証に用いられる。
【０２０１】
また、ユーザ署名鍵ｓｋ”は、ユーザにより秘密に管理される。なお、鍵登録アルゴリズムは、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズム（図１３、図１７を参照）に相当するものである。但し、先の説明における署名者と代用署名者との間で利用されるのではなく、認証局とユーザとの間で利用される点に注意されたい。
【０２０２】
（Ａ４）の署名生成アルゴリズムは、ユーザがユーザ署名鍵ｓｋ”を用いて電子文書ｍに対する電子署名σを生成するためのアルゴリズムである。なお、署名生成アルゴリズムは、上記の第１及び第２実施形態に係る署名生成アルゴリズムＳｉｇＫＳＳ（図１１、図１５を参照）に相当する。但し、ユーザ（代用鍵生成者に相当）が利用する点に注意されたい。
【０２０３】
（Ａ５）の署名検証アルゴリズムは、ユーザの電子署名σが電子文書ｍに対する正当な電子署名であるか否かを検証するためのアルゴリズムである。署名検証アルゴリズムは、ユーザの電子署名σを検証する検証者により利用される。なお、ここで言う署名検証アルゴリズムは、上記の第１及び第２実施形態に係る署名検証アルゴリズムＶｅｒ（図１２、図１６を参照）に相当する。
【０２０４】
（Ａ６）の検証鍵検証アルゴリズムは、認証局が発行した証明書が正当な証明書であるか否かを検証すると共に、その証明書を用いてユーザ検証鍵ｐｋ”が正当な検証鍵であるか否かを検証するためのアルゴリズムである。ここで、（Ａ６）の検証鍵検証アルゴリズムについて、より詳細に説明する。
【０２０５】
先に述べた通り、上記の第１及び第２実施形態に係る代用鍵生成方法は、ある電子文書ｍに対し、ある署名鍵ｓｋと検証鍵ｐｋとのペアを用いて生成された電子署名σを受理する代用検証鍵ｐｋ”を生成する方法である。応用例１においては、署名鍵ｓｋ及び検証鍵ｐｋが、認証局により生成される秘密鍵ｓｋ及び公開鍵ｐｋに対応する。また、応用例１においては、電子文書ｍとして、ユーザＩＤが記載された電子文書ｍＩＤが用いられる。さらに、電子署名σとしては、電子文書ｍＩＤに対し、秘密鍵ｓｋに基づいて生成された電子署名σＩＤが用いられる。
【０２０６】
但し、この電子署名σＩＤは、認証局が発行するユーザ検証鍵ｐｋ”に対する証明書として用いられる。このユーザ検証鍵ｐｋ”は、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムで生成された代用検証鍵ｐｋ”に対応する。つまり、正しいユーザ検証鍵ｐｋ”は、電子文書ｍＩＤに対して生成された証明書σＩＤを受理する。逆に言えば、ユーザ検証鍵ｐｋ”が（ｍＩＤ，σＩＤ）の組を受理するか否かを検証することにより、ユーザ検証鍵ｐｋ”の正当性を確認することができるのである。
【０２０７】
また、証明書σＩＤの正当性についても、認証局により発行された公開鍵ｐｋが（ｍＩＤ，σＩＤ）の組を受理するか否かを検証することにより確認することができる。このように、（Ａ６）の検証鍵検証アルゴリズムは、認証局が生成した公開鍵ｐｋが（ｍＩＤ，σＩＤ）を受理し、かつ、対話プロトコルに基づいて生成されたユーザ検証鍵ｐｋ”が（ｍＩＤ，σＩＤ）を受理することを検証することにより、認証局が発行する証明書σＩＤの正当性、及びユーザ検証鍵ｐｋ”を検証するのである。
【０２０８】
以下、応用例１に係るシステム構成、及び具体的な処理の流れについて説明する。
【０２０９】
（システム構成）
ここで、図２１を参照する。図２１に示すように、応用例１のシステムには、認証局に設けられる認証局サーバ１３０、検証者が利用する検証者端末２３０、及びユーザが利用するユーザ端末３３０が含まれる。また、認証局サーバ１３０、検証者端末２３０、ユーザ端末３３０は、ネットワーク１０で接続されている。なお、システム管理者に関する構成は省略した。
【０２１０】
（認証局サーバ１３０）
まず、認証局サーバ１３０の機能構成について説明する。図２１に示すように、認証局サーバ１３０は、主に、記憶部１３２と、鍵生成部１３４と、署名生成部１３６と、通信部１３８と、秘密鍵関連情報生成部１４０とを有する。
【０２１１】
記憶部１３２は、システムパラメータｃｐ、電子文書ｍ、及び各アルゴリズムを実行するためのプログラムを格納するための手段である。鍵生成部１３４は、記憶部１３２からシステムパラメータｃｐ、及びＣＡ鍵生成アルゴリズムの実行プログラムを読み出し、秘密鍵ｓｋ及び公開鍵ｐｋを生成する。鍵生成部１３４で生成された秘密鍵ｓｋ及び公開鍵ｐｋは、署名生成部１３６に入力される。また、公開鍵ｐｋは、通信部１３８を介して公開され、検証者端末２３０に入力される。もちろん、ユーザ端末３３０も公開鍵ｐｋを取得することが可能である。
【０２１２】
また、署名生成部１３６には、ユーザを特定するためのユーザＩＤが含まれた電子文書ｍＩＤが入力される。なお、秘密鍵ｓｋ及び公開鍵ｐｋは、上記の第１及び第２実施形態において真の署名者が生成する署名鍵ｓｋ及び検証鍵ｐｋに対応する。署名生成部１３６は、記憶部１３２からシステムパラメータｃｐ、及び署名生成アルゴリズムの実行プログラムを読み出し、入力された秘密鍵ｓｋ及び電子文書ｍＩＤを用いて当該電子文書ｍＩＤに付する電子署名σＩＤを生成する。
【０２１３】
そして、署名生成部１３６で生成された電子署名σＩＤ及び電子文書ｍＩＤは、通信部１３８によりネットワーク１０を介して検証者端末２３０に提供される。この電子文書ｍＩＤ及び電子署名σＩＤの組が後述するユーザ検証鍵ｐｋ”の証明書（ｍＩＤ，σＩＤ）となる。そのため、検証者端末２３０には、公開鍵ｐｋ及び証明書（ｍＩＤ，σＩＤ）が認証局サーバ１３０から提供されることになる。
【０２１４】
秘密鍵関連情報生成部１４０は、上記の鍵登録アルゴリズムを用いてユーザ検証鍵ｐｋ”を生成する際に必要となる秘密鍵ｓｋに関連する情報を生成する手段である。先に述べた通り、鍵登録アルゴリズムは上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムに相当する対話プロトコルである。そのため、秘密鍵関連情報生成部１４０は、ユーザ端末３３０（ユーザ検証鍵生成部３３６）から、秘密鍵ｓｋに関連する情報を生成するのに必要な情報を取得し、取得した情報を用いて秘密鍵ｓｋに関連する情報を生成する。
【０２１５】
例えば、上記の第１実施形態に係る代用鍵生成アルゴリズム（図１３を参照）に相当する対話プロトコルを用いる場合、秘密鍵関連情報生成部１４０は、乱数ｗを生成し、代用検証鍵ｐｋ”の生成に用いるパラメータｋ”を算出する。さらに、秘密鍵関連情報生成部１４０は、ユーザ端末３３０（ユーザ検証鍵生成部３３６）からユーザ検証鍵ｐｋ”に関連するパラメータｙ１’を取得し、そのパラメータｙ１’を利用してパラメータｋ”を生成する。
【０２１６】
このようにして生成されたパラメータｋ”、ｗは、秘密鍵関連情報生成部１４０からユーザ端末３３０に提供される。このように、対話プロトコルである鍵登録アルゴリズムの中で、認証局サーバ１３０からユーザ端末３３０にユーザ検証鍵ｐｋ”の生成に必要な情報が提供される。
【０２１７】
（検証者端末２３０）
次に、検証者端末２３０の機能構成について説明する。図２１に示すように、検証者端末２３０は、主に、通信部２０２と、パラメータ生成部２０４と、記憶部２０６と、検証処理部２３２とを有する。記憶部２０６には、システムパラメータｃｐの他、検証者が実行すべきアルゴリズムの実行プログラム等が格納される。なお、ここでは認証局が公開した公開鍵ｐｋも記憶部２０６に予め格納されているものとする。
【０２１８】
まず、通信部２０２によりネットワーク１０を介して認証局サーバ１３０から証明書（ｍＩＤ，σＩＤ）が取得され、パラメータ生成部２０４に入力される。パラメータ生成部２０４では、署名検証アルゴリズム及び検証鍵検証アルゴリズムの実行に必要なパラメータが算出される。パラメータ生成部２０４で算出されたパラメータは、検証処理部２３２に入力される。
【０２１９】
検証処理部２３２は、まず、パラメータ生成部２０４で算出されたパラメータ、ユーザ検証鍵ｐｋ”、公開鍵ｐｋ、及び証明書（ｍＩＤ，σＩＤ）を検証鍵検証アルゴリズムに入力して証明書の正当性、及びユーザ検証鍵ｐｋ”の正当性を検証する。これらの正当性が確認された場合、検証処理部２３２は、パラメータ生成部２０４で算出されたパラメータ、ユーザ検証鍵ｐｋ”、ユーザが生成した電子文書ｍ及び電子署名σを署名検証アルゴリズムに入力して電子署名σの正当性を検証する。
【０２２０】
このようにして、検証者端末２３０では、証明書及びユーザ検証鍵の検証が行われる。その結果、ＰＫＩにおけるユーザの公開鍵に相当するユーザ検証鍵と、ユーザＩＤに相当する電子文書ｍＩＤとの間のひも付けを確認することができる。そして、ひも付けが確認された場合に、そのユーザ検証鍵を用いて電子署名の検証が行われる。
【０２２１】
（ユーザ端末３３０）
次に、ユーザ端末３３０の機能構成について説明する。図２１に示すように、ユーザ端末３３０は、主に、記憶部３３２と、ユーザ署名鍵生成部３３４と、ユーザ検証鍵生成部３３６と、通信部３３８と、署名生成部３４０とを有する。記憶部３３２には、システムパラメータｃｐの他、ユーザが実行すべきアルゴリズムの実行プログラム等が格納される。
【０２２２】
ユーザ署名鍵生成部３３４は、ユーザ署名鍵ｓｋ”を生成する手段である。例えば、上記の第１実施形態に係る鍵生成アルゴリズム（図１１を参照）と同様のアルゴリズムを用いる場合、ユーザ署名鍵生成部３３４は、記憶部３３２に格納されたシステムパラメータｃｐを読み出し、ユーザ署名鍵ｓｋ”に関するパラメータｘ１’、ｘ２”を生成する。
【０２２３】
そして、ユーザ署名鍵生成部３３４は、パラメータｘ１’、ｘ２”をユーザ検証鍵生成部３３６に入力する。さらに、ユーザ署名鍵生成部３３４は、ユーザ検証鍵生成部３３６から代用署名鍵ｓｋ”の生成に必要な情報が入力された場合、その情報を加えて代用署名鍵ｓｋ”を生成する。ユーザ署名鍵生成部３３４で生成されたユーザ署名鍵は、署名生成部３４０に入力される。
【０２２４】
ユーザ署名鍵生成部３３４からパラメータｘ１’ｘ２”が入力されると、ユーザ検証鍵生成部３３６は、認証局サーバ１３０（秘密鍵関連情報生成部１４０）との間で対話を実行し、代用検証鍵ｐｋ”の生成に必要なパラメータｋ”、ｗを取得する。この対話は、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムに相当する鍵登録アルゴリズムに基づいて実行される。例えば、上記の第１実施形態に係る代用鍵生成アルゴリズムに相当する鍵登録アルゴリズムを用いる場合、ユーザ検証鍵生成部３３６は、代用検証鍵ｐｋ”に関する情報としてパラメータｙ１’を認証局サーバ１３０に提供する。
【０２２５】
上記の通り、パラメータｙ１’の提供を受けると、認証局サーバ１３０の秘密鍵関連情報生成部１４０は、パラメータｙ１’に基づいてユーザ検証鍵ｐｋ”の生成に必要な情報（例えば、ｋ”、ｗ）をユーザ検証鍵生成部３３６に提供する。この段階では、認証局サーバ１３０において、この後に確定されるユーザ検証鍵ｐｋ”を推定することができない点に注意されたい。認証局サーバ１３０からパラメータｋ”、ｗを取得すると、ユーザ検証鍵生成部３３６は、パラメータｋ”、ｗを用いてユーザ検証鍵ｐｋ”を生成する。ユーザ検証鍵生成部３３６で生成されたユーザ検証鍵ｐｋ”は、通信部３３８によりネットワーク１０を介して検証者端末２３０に提供される。
【０２２６】
このようなユーザ検証鍵ｐｋ”の生成工程において算出されるパラメータの一部をユーザ署名鍵ｓｋ”に含めてもよい。その場合、ユーザ署名鍵ｓｋ”に含めるべきパラメータは、この段階でユーザ検証鍵生成部３３６からユーザ署名鍵生成部３３４に入力される。上記の通り、ユーザ署名鍵生成部３３４は、入力されたパラメータを用いてユーザ署名鍵ｓｋ”を生成する。そして、ユーザ署名鍵生成部３３４で生成されたユーザ署名鍵ｓｋ”は、署名生成部３４０に入力される。
【０２２７】
署名生成部３４０は、ユーザ署名鍵生成部３３４から入力されたユーザ署名鍵ｓｋ”を用いてユーザの電子署名σを生成する手段である。署名生成部３４０は、上記の署名生成アルゴリズムを用いて、ある電子文書ｍに対する電子署名σを生成する。ここで生成された電子文書ｍ及び電子署名σは、ユーザ検証鍵生成部３３６で生成されたユーザ検証鍵ｐｋ”により受理されるものである。署名生成部３４０で生成された電子文書ｍと電子署名σとの組は、通信部３３８を介して検証者端末２３０に提供される。
【０２２８】
以上、応用例１に係るシステム構成について説明した。次に、図２２を参照しながら、応用例１に係る公開鍵証明方法に関し、その全体的な処理の流れについて簡単に説明する。
【０２２９】
（公開鍵の証明方法について）
図２２を参照する。先に述べた通り、応用例１において登場するエンティティは、主に、システム管理者、認証局、ユーザ、検証者の４者である。図２２には、システム管理者を除く、認証局、ユーザ、検証者の行う手続きが記載されている。この手続きについて説明する。
【０２３０】
（認証局の手続き：鍵生成工程）
まず、認証局による鍵生成処理について説明する。認証局は、まず、システム管理者からシステムパラメータｃｐを取得する。次いで、取得したシステムパラメータｃｐをＣＡ鍵生成アルゴリズムに入力し、秘密鍵ｓｋ及び公開鍵ｐｋのペアを生成する。次いで、認証局は、秘密鍵ｓｋと公開鍵ｐｋのペアを保管する。
【０２３１】
（認証局及びユーザの手続き：ユーザ鍵生成工程）
次に、認証局及びユーザによるユーザ鍵生成処理について説明する。まず、ユーザは、自身のユーザＩＤを認証局に提供する。次いで、認証局は、鍵生成工程で生成した秘密鍵ｓｋ、公開鍵ｐｋ、及びユーザＩＤを含む電子文書ｍＩＤを用意する。次いで、認証局は、秘密鍵ｓｋを用いて電子文書ｍＩＤに対する電子署名σＩＤを生成する。次いで、認証局は、電子文書ｍＩＤ、電子署名σＩＤ、公開鍵ｐｋをユーザに提供する。
【０２３２】
次いで、ユーザは、認証局から電子文書ｍＩＤ、電子署名σＩＤ、公開鍵ｐｋを受領する。このようにして電子文書ｍＩＤ、電子署名σＩＤ、公開鍵ｐｋが共有されると、認証局及びユーザは、上記の第１及び第２実施形態の代用鍵生成アルゴリズムに相当する鍵登録アルゴリズムに電子文書ｍＩＤ、電子署名σＩＤ、公開鍵ｐｋを入力し、対話形式でユーザ検証鍵ｐｋ”、及びユーザ署名鍵ｓｋ”を生成する。なお、この対話の中で、認証局は、秘密鍵ｓｋをユーザに特定されないようにしつつ、秘密鍵ｓｋに関する情報をユーザに提供する。
【０２３３】
（検証者の手続き：署名検証工程）
次に、検証者による署名検証処理について説明する。検証者は、ユーザから電子文書ｍ、電子署名σ、ユーザ検証鍵ｐｋ”を取得する。ここで取得される電子署名σは、電子文書ｍに対し、ユーザ署名鍵ｓｋ”を用いて生成されたものである。次いで、検証者は、必要に応じてユーザ検証鍵ｐｋ”の正当性を確認する。このとき、検証者は、検証鍵検証アルゴリズムを利用し、認証局から取得した証明書（ｍＩＤ，σＩＤ）を用いてユーザ検証鍵ｐｋ”の正当性を検証する。ユーザ検証鍵ｐｋ”の正当性が確認された場合、検証者は、署名検証アルゴリズムにユーザ検証鍵ｐｋ”、電子文書ｍ、電子署名σを入力して電子署名σの検証を実施し、電子署名σの正当性を確認する。
【０２３４】
（検証者の手続き：検証鍵検証工程）
次に、検証者による検証鍵の検証処理について説明する。上記の署名検証工程の中で、検証者は、検証鍵検証アルゴリズムを利用してユーザ検証鍵ｐｋ”の正当性を検証していた。ここで説明する検証鍵検証工程は、この検証処理に関するものである。まず、検証者は、認証局から公開鍵ｐｋを取得すると共に、ユーザ検証鍵ｐｋ”、証明書（ｍＩＤ，σＩＤ）を用意する。次いで、検証者は、検証鍵検証アルゴリズムにユーザ検証鍵ｐｋ”、証明書（ｍＩＤ，σＩＤ）を入力してユーザ鍵ｐｋ”及び証明書（ｍＩＤ，σＩＤ）の正当性を検証する。
【０２３５】
なお、検証鍵検証アルゴリズムは、上記の第１及び第２実施形態に係る署名検証アルゴリズムを応用することにより実現される。まず、証明書（ｍＩＤ，σＩＤ）の正当性を検証するには、認証局の公開鍵ｐｋ、証明書（ｍＩＤ，σＩＤ）を署名検証アルゴリズムに入力し、検証式が成り立つか否かを確認すればよい。同様に、ユーザ検証鍵ｐｋ”の正当性を検証するには、ユーザ検証鍵ｐｋ”、証明書（ｍＩＤ，σＩＤ）を署名検証アルゴリズムに入力し、検証式が成り立つか否かを確認すればよい。つまり、これらの処理を実行するのが検証鍵検証アルゴリズムである。上記２通りの入力に対して検証式が成り立つ場合にユーザ検証鍵ｐｋ”を受理する。
【０２３６】
以上、応用例１に係る公開鍵証明方法について説明した。このように、上記の第１及び第２実施形態に係る代用鍵の特性はＰＫＩにおける公開鍵（ユーザ検証鍵）の認証に応用することができる。
【０２３７】
［６−２：代理人署名方式への応用］
次に、図２３、図２４を参照しながら、上記の第１及び第２実施形態に係る代用鍵生成方法を代理人署名方式へ応用する方法（以下、応用例２）について説明する。図２３は、この応用例２に係る方法を実現することが可能な代理人署名システムの一例を示す説明図である。また、図２４は、この応用例２に係る全体的な処理の流れを示す説明図である。
【０２３８】
代理人署名方式とは、委任者が代理人に対し、自身の署名生成権限の一部を委譲することを可能にする電子署名方式のことを言う。代理人署名方式は、例えば、次のような６つのアルゴリズムの組で表現される。
【０２３９】
（Ａ１）システムパラメータ生成アルゴリズム
（Ａ２）鍵生成アルゴリズム
（Ａ３）代理人鍵生成アルゴリズム
（Ａ４）署名生成アルゴリズム
（Ａ５）署名検証アルゴリズム
（Ａ６）代理人検証アルゴリズム
【０２４０】
（Ａ１）のシステムパラメータ生成アルゴリズムは、システム管理者により用いられるものであり、上記のＳＣ０８方式におけるシステムパラメータ生成アルゴリズムＳｅｔｕｐＫＳＳ（図６を参照）に相当する。
【０２４１】
（Ａ２）の鍵生成アルゴリズムは、委任者により用いられるものであり、委任者が利用する委任者固有の署名鍵ｓｋと検証鍵ｐｋの組を生成するアルゴリズムである。鍵生成アルゴリズムで生成された検証鍵ｐｋは公開され、署名鍵ｓｋを用いて生成された電子署名σを検証するために用いられる。鍵生成アルゴリズムで生成された署名鍵ｓｋは、委任者において秘密に管理される。
【０２４２】
また、委任者において秘密に管理される署名鍵ｓｋは、後述する代用検証鍵ｐｋ”を生成する際に用いられる。また、鍵生成アルゴリズムは、上記の第１及び第２実施形態に係る鍵生成アルゴリズムＧｅｎＫＳＳ（図１１、図１５を参照）に相当するものである。但し、署名者ではなく委任者が用いる点に注意されたい。
【０２４３】
（Ａ３）の代理人鍵生成アルゴリズムは、代理人が利用する代用署名鍵ｓｋ”及び代用検証鍵ｐｋ”を生成すると共に、委任者により代理人の正当性を証明するための証明書を生成するアルゴリズムである。代理人鍵生成アルゴリズムは、対話プロトコルに基づいて委任者と代理人との間で実行される。代理人鍵生成アルゴリズムで生成された代用検証鍵ｐｋ”は公開され、代用署名鍵ｓｋ”を用いて生成される電子署名の検証に用いられる。
【０２４４】
また、代用署名鍵ｓｋ”は、代理人により秘密に管理される。なお、代理人鍵生成アルゴリズムは、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズム（図１３、図１７を参照）に相当するものである。また、署名者と代用署名者との間で利用されるのではなく、委任者と代理人との間で利用される。そして、委任者の証明書は、代理人の代用検証鍵が委任者によって認められたものであることを証明するものである。
【０２４５】
（Ａ４）の署名生成アルゴリズムは、代理人が代用署名鍵ｓｋ”を用いて電子文書ｍに対する電子署名σを生成するためのアルゴリズムである。なお、署名生成アルゴリズムは、上記の第１及び第２実施形態に係る署名生成アルゴリズムＳｉｇＫＳＳ（図１１、図１５を参照）に相当する。但し、委任者及び代理人の双方が利用する点に注意されたい。
【０２４６】
（Ａ５）の署名検証アルゴリズムは、電子署名σが電子文書ｍに対する正当な電子署名であるか否かを検証するためのアルゴリズムである。署名検証アルゴリズムは、委任者又は代理人の電子署名σを検証する検証者により利用される。なお、ここで言う署名検証アルゴリズムは、上記の第１及び第２実施形態に係る署名検証アルゴリズムＶｅｒ（図１２、図１６を参照）に相当する。
【０２４７】
（Ａ６）の代理人検証アルゴリズムは、代理人が委任者により認められた正当な代理人であるか否かを検証するためのアルゴリズムである。代理人の正当性を検証するために、代理人検証アルゴリズムは、委任者が発行した証明書が正当な証明書であるか否かを検証すると共に、その証明書を用いて代用検証鍵ｐｋ”が正当な検証鍵であるか否かを検証する。ここで、（Ａ６）の代理人検証アルゴリズムについて、より詳細に説明する。
【０２４８】
先に述べた通り、上記の第１及び第２実施形態に係る代用鍵生成方法は、ある電子文書ｍに対し、ある署名鍵ｓｋと検証鍵ｐｋとのペアを用いて生成された電子署名σを受理する代用検証鍵ｐｋ”を生成する方法である。応用例２においては、署名鍵ｓｋ及び検証鍵ｐｋが、委任者により生成される署名鍵ｓｋ及び検証鍵ｐｋに対応する。また、応用例２においては、電子文書ｍとして、委譲する権限の範囲や有効期限等を含む電子文書ｍｗが用いられる。さらに、電子署名σとしては、電子文書ｍｗに対し、署名鍵ｓｋに基づいて生成された電子署名σｗが用いられる。
【０２４９】
但し、この電子署名σｗは、委任者が発行する代用検証鍵ｐｋ”に対する証明書として用いられる。この代用検証鍵ｐｋ”は、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムで生成された代用検証鍵ｐｋ”に対応する。つまり、正しい代用検証鍵ｐｋ”は、電子文書ｍｗに対して生成された証明書σｗを受理する。逆に言えば、代用検証鍵ｐｋ”が（ｍｗ，σｗ）の組を受理するか否かを検証することにより、代理人の代用検証鍵ｐｋ”が委任者により認められたものであるか否かを確認することができるのである。
【０２５０】
また、証明書σｗの正当性についても、委任者により発行された検証鍵ｐｋが（ｍｗ，σｗ）の組を受理するか否かを検証することにより確認することができる。このように、（Ａ６）の代理人検証アルゴリズムは、委任者が生成した検証鍵ｐｋが（ｍｗ，σｗ）を受理し、かつ、対話プロトコルに基づいて生成された代用検証鍵ｐｋ”が（ｍｗ，σｗ）を受理することを検証することにより、委任者が発行する証明書σｗの正当性、及び代用検証鍵ｐｋ”を検証するのである。
【０２５１】
以下、応用例２に係るシステム構成、及び具体的な処理の流れについて説明する。
【０２５２】
（システム構成）
ここで、図２３を参照する。図２３に示すように、応用例２のシステムには、委任者が利用する委任者端末１５０、検証者が利用する検証者端末２５０、及び代理人が利用する代理人端末３５０が含まれる。また、委任者端末１５０、検証者端末２５０、代理人端末３５０は、ネットワーク１０で接続されている。なお、システム管理者に関する構成は省略した。
【０２５３】
（委任者端末１５０）
まず、委任者端末１５０の機能構成について説明する。図２３に示すように、委任者端末１５０は、主に、記憶部１５２と、鍵生成部１５４と、署名生成部１５６と、通信部１５８と、署名鍵関連情報生成部１６０とを有する。
【０２５４】
記憶部１５２は、システムパラメータｃｐ、電子文書ｍ、及び各アルゴリズムを実行するためのプログラムを格納するための手段である。鍵生成部１５４は、記憶部１５２からシステムパラメータｃｐ、及び鍵生成アルゴリズムの実行プログラムを読み出し、署名鍵ｓｋ及び検証鍵ｐｋを生成する。鍵生成部１５４で生成された署名鍵ｓｋ及び検証鍵ｐｋは、署名生成部１５６に入力される。また、検証鍵ｐｋは、通信部１５８を介して公開され、検証者端末２５０に入力される。もちろん、代理人端末３５０も検証鍵ｐｋを取得することが可能である。
【０２５５】
また、署名生成部１５６には、委譲する権限の範囲や有効期限等が含まれた電子文書ｍｗが入力される。なお、委任者の署名鍵ｓｋ及び検証鍵ｐｋは、上記の第１及び第２実施形態において真の署名者が生成する署名鍵ｓｋ及び検証鍵ｐｋに対応する。署名生成部１５６は、記憶部１５２からシステムパラメータｃｐ、及び署名生成アルゴリズムの実行プログラムを読み出し、入力された署名鍵ｓｋ及び電子文書ｍｗを用いて当該電子文書ｍｗに付する電子署名σｗを生成する。
【０２５６】
そして、署名生成部１５６で生成された電子署名σｗ及び電子文書ｍｗは、通信部１５８によりネットワーク１０を介して検証者端末２５０に提供される。この電子文書ｍｗ及び電子署名σｗの組が委任者により認められた代用検証鍵ｐｋ”であることを証明するための証明書（ｍｗ，σｗ）となる。そのため、検証者端末２５０には、検証鍵ｐｋ及び証明書（ｍｗ，σｗ）が委任者端末１５０から提供されることになる。
【０２５７】
署名鍵関連情報生成部１６０は、上記の代理人鍵生成アルゴリズムを用いて代用検証鍵ｐｋ”を生成する際に必要となる署名鍵ｓｋに関連する情報を生成する手段である。先に述べた通り、代理人鍵生成アルゴリズムは上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムに相当する対話プロトコルである。そのため、署名鍵関連情報生成部１６０は、代理人端末３５０（代用検証鍵生成部３５６）から、署名鍵ｓｋに関連する情報を生成するのに必要な情報を取得し、取得した情報を用いて署名鍵ｓｋに関連する情報を生成する。
【０２５８】
例えば、上記の第１実施形態に係る代用鍵生成アルゴリズム（図１３を参照）に相当する対話プロトコルを用いる場合、署名鍵関連情報生成部１６０は、乱数ｗを生成し、代用検証鍵ｐｋ”の生成に用いるパラメータｋ”を算出する。さらに、署名鍵関連情報生成部１６０は、代理人端末３５０（代用検証鍵生成部３５６）から代用検証鍵ｐｋ”に関連するパラメータｙ１’を取得し、そのパラメータｙ１’を利用してパラメータｋ”を生成する。
【０２５９】
このようにして生成されたパラメータｋ”、ｗは、署名鍵関連情報生成部１６０から代理人端末３５０に提供される。このように、対話プロトコルである代理人鍵生成アルゴリズムの中で、委任者端末１５０から代理人端末３５０に代用検証鍵ｐｋ”の生成に必要な情報が提供される。
【０２６０】
（検証者端末２５０）
次に、検証者端末２５０の機能構成について説明する。図２３に示すように、検証者端末２５０は、主に、通信部２０２と、パラメータ生成部２０４と、記憶部２０６と、検証処理部２５２とを有する。記憶部２０６には、システムパラメータｃｐの他、検証者が実行すべきアルゴリズムの実行プログラム等が格納される。なお、ここでは委任者から提供された検証鍵ｐｋが記憶部２０６に予め格納されているものとする。
【０２６１】
まず、通信部２０２によりネットワーク１０を介して委任者端末１５０から証明書（ｍｗ，σｗ）が取得され、パラメータ生成部２０４に入力される。パラメータ生成部２０４では、署名検証アルゴリズム及び代理人検証アルゴリズムの実行に必要なパラメータが算出される。パラメータ生成部２０４で算出されたパラメータは、検証処理部２５２に入力される。
【０２６２】
検証処理部２５２は、まず、パラメータ生成部２０４で算出されたパラメータ、代用検証鍵ｐｋ”、検証鍵ｐｋ、及び証明書（ｍｗ，σｗ）を代理人検証アルゴリズムに入力して代理人の正当性、及び代用検証鍵ｐｋ”の正当性を検証する。これらの正当性が確認された場合、検証処理部２５２は、パラメータ生成部２０４で算出されたパラメータ、代用検証鍵ｐｋ”、ユーザが生成した電子文書ｍ及び電子署名σを署名検証アルゴリズムに入力して電子署名σの正当性を検証する。このようにして、検証者端末２５０では、代理人及び電子署名の検証が行われる。
【０２６３】
（代理人端末３５０）
次に、代理人端末３５０の機能構成について説明する。図２３に示すように、代理人端末３５０は、主に、記憶部３５２と、代用署名鍵生成部３５４と、代用検証鍵生成部３５６と、通信部３５８と、署名生成部３６０とを有する。記憶部３５２には、システムパラメータｃｐの他、ユーザが実行すべきアルゴリズムの実行プログラム等が格納される。
【０２６４】
代用署名鍵生成部３５４は、代用署名鍵ｓｋ”を生成する手段である。例えば、上記の第１実施形態に係る鍵生成アルゴリズム（図１１を参照）と同様のアルゴリズムを用いる場合、代用署名鍵生成部３５４は、記憶部３５２に格納されたシステムパラメータｃｐを読み出し、代用署名鍵ｓｋ”に関するパラメータｘ１’、ｘ２”を生成する。
【０２６５】
そして、代用署名鍵生成部３５４は、パラメータｘ１’、ｘ２”を代用検証鍵生成部３５６に入力する。さらに、代用署名鍵生成部３５４は、代用検証鍵生成部３５６から代用署名鍵ｓｋ”の生成に必要な情報が入力された場合、その情報を加えて代用署名鍵ｓｋ”を生成する。代用署名鍵生成部３５４で生成された代用署名鍵は、署名生成部３６０に入力される。
【０２６６】
代用署名鍵生成部３５４からパラメータｘ１’ｘ２”が入力されると、代用検証鍵生成部３５６は、委任者端末１５０（署名鍵関連情報生成部１６０）との間で対話を実行し、代用検証鍵ｐｋ”の生成に必要なパラメータｋ”、ｗを取得する。この対話は、上記の第１及び第２実施形態に係る代用鍵生成アルゴリズムに相当する代理人鍵生成アルゴリズムに基づいて実行される。例えば、上記の第１実施形態に係る代用鍵生成アルゴリズムに相当する代理人鍵生成アルゴリズムを用いる場合、代用検証鍵生成部３５６は、代用検証鍵ｐｋ”に関する情報としてパラメータｙ１’を委任者端末１５０に提供する。
【０２６７】
上記の通り、パラメータｙ１’の提供を受けると、委任者端末１５０の署名鍵関連情報生成部１６０は、パラメータｙ１’に基づいて代用検証鍵ｐｋ”の生成に必要な情報（例えば、ｋ”、ｗ）を代用検証鍵生成部３５６に提供する。この段階では、委任者端末１５０において、この後に確定される代用検証鍵ｐｋ”を推定することができない点に注意されたい。委任者端末１５０からパラメータｋ”、ｗを取得すると、代用検証鍵生成部３５６は、パラメータｋ”、ｗを用いて代用検証鍵ｐｋ”を生成する。代用検証鍵生成部３５６で生成された代用検証鍵ｐｋ”は、通信部３５８によりネットワーク１０を介して検証者端末２５０に提供される。
【０２６８】
このような代用検証鍵ｐｋ”の生成工程において算出されるパラメータの一部を代用署名鍵ｓｋ”に含めてもよい。その場合、代用署名鍵ｓｋ”に含めるべきパラメータは、この段階で代用検証鍵生成部３５６から代用署名鍵生成部３５４に入力される。上記の通り、代用署名鍵生成部３５４は、入力されたパラメータを用いて代用署名鍵ｓｋ”を生成する。そして、代用署名鍵生成部３５４で生成された代用署名鍵ｓｋ”は、署名生成部３６０に入力される。
【０２６９】
署名生成部３６０は、代用署名鍵生成部３５４から入力された代用署名鍵ｓｋ”を用いて代理人の電子署名σを生成する手段である。署名生成部３６０は、上記の署名生成アルゴリズムを用いて、ある電子文書ｍに対する電子署名σを生成する。ここで生成された電子文書ｍ及び電子署名σは、代用検証鍵生成部３５６で生成された代用検証鍵ｐｋ”により受理されるものである。署名生成部３６０で生成された電子文書ｍと電子署名σとの組は、通信部３５８を介して検証者端末２５０に提供される。
【０２７０】
以上、応用例２に係るシステム構成について説明した。次に、図２４を参照しながら、応用例２に係る代理権の証明方法に関し、その全体的な処理の流れについて簡単に説明する。
【０２７１】
（代理権の証明方法について）
図２４を参照する。先に述べた通り、応用例２において登場するエンティティは、主に、システム管理者、委任者、代理人、検証者の４者である。図２４には、システム管理者を除く、委任者、代理人、検証者の行う手続きが記載されている。この手続きについて説明する。
【０２７２】
（委任者の手続き：鍵生成工程）
まず、委任者による鍵生成処理について説明する。委任者は、まず、システム管理者からシステムパラメータｃｐを取得する。次いで、取得したシステムパラメータｃｐを鍵生成アルゴリズムに入力し、署名鍵ｓｋ及び検証鍵ｐｋのペアを生成する。次いで、委任者は、署名鍵ｓｋと検証鍵ｐｋのペアを保管する。
【０２７３】
（委任者及び代理人の手続き：代用鍵生成工程）
次に、委任者及び代理人による代用鍵生成処理について説明する。まず、委任者は、鍵生成工程で生成した署名鍵ｓｋ、検証鍵ｐｋ、及び委譲する代理権の範囲や有効期限等が含まれた電子文書ｍｗを用意する。次いで、委任者は、署名鍵ｓｋを用いて電子文書ｍｗに対する電子署名σｗを生成する。次いで、委任者は、電子文書ｍｗ、電子署名σｗ、検証鍵ｐｋを代理人に提供する。
【０２７４】
次いで、代理人は、委任者から電子文書ｍｗ、電子署名σｗ、検証鍵ｐｋを受領する。このようにして電子文書ｍｗ、電子署名σｗ、検証鍵ｐｋが共有されると、委任者及び代理人は、上記の第１及び第２実施形態の代用鍵生成アルゴリズムに相当する代理人鍵生成アルゴリズムに電子文書ｍｗ、電子署名σｗ、検証鍵ｐｋを入力し、対話形式で代用検証鍵ｐｋ”、及び代用署名鍵ｓｋ”を生成する。なお、この対話の中で、委任者は、署名鍵ｓｋを代理人に特定されないようにしつつ、署名鍵ｓｋに関する情報を代理人に提供する。
【０２７５】
（検証者の手続き：署名検証工程）
次に、検証者による署名検証処理について説明する。検証者は、代理人から電子文書ｍ、電子署名σ、代用検証鍵ｐｋ”を取得する。ここで取得される電子署名σは、電子文書ｍに対し、代理人が代用署名鍵ｓｋ”を用いて生成したものである。次いで、検証者は、必要に応じて代用検証鍵ｐｋ”の正当性（代理人の正当性）を確認する。このとき、検証者は、代理人検証アルゴリズムを利用し、委任者から取得した証明書（ｍｗ，σｗ）を用いて代用検証鍵ｐｋ”の正当性を検証する。代用検証鍵ｐｋ”の正当性が確認された場合、検証者は、署名検証アルゴリズムに代用検証鍵ｐｋ”、電子文書ｍ、電子署名σを入力して電子署名σの検証を実施し、電子署名σの正当性を確認する。
【０２７６】
（検証者の手続き：代理人検証工程）
次に、検証者による代理人の検証処理について説明する。上記の署名検証工程の中で、検証者は、代理人検証アルゴリズムを利用して代用検証鍵ｐｋ”の正当性を検証していた。ここで説明する代理人検証工程は、この検証処理に関するものである。まず、検証者は、委任者から検証鍵ｐｋを取得すると共に、代用検証鍵ｐｋ”、証明書（ｍｗ，σｗ）を用意する。次いで、検証者は、代理人検証アルゴリズムに代用検証鍵ｐｋ”、証明書（ｍｗ，σｗ）を入力して代理人鍵ｐｋ”及び証明書（ｍｗ，σｗ）の正当性を検証する。
【０２７７】
なお、代理人検証アルゴリズムは、上記の第１及び第２実施形態に係る署名検証アルゴリズムを応用することにより実現される。まず、証明書（ｍｗ，σｗ）の正当性を検証するには、委任者の検証鍵ｐｋ、証明書（ｍｗ，σｗ）を署名検証アルゴリズムに入力し、検証式が成り立つか否かを確認すればよい。同様に、代用検証鍵ｐｋ”の正当性を検証するには、代用検証鍵ｐｋ”、証明書（ｍｗ，σｗ）を署名検証アルゴリズムに入力し、検証式が成り立つか否かを確認すればよい。つまり、これらの処理を実行するのが代理人検証アルゴリズムである。上記２通りの入力に対して検証式が成り立つ場合に代用検証鍵ｐｋ”を受理し、代理人の正当性を認める。
【０２７８】
以上、応用例２に係る公開鍵証明方法について説明した。このように、上記の第１及び第２実施形態に係る代用鍵の特性は代理人署名方式に応用することができる。
【０２７９】
［６−３：責任分担型電子署名への応用］
次に、責任分担型電子署名への応用について簡単に説明する。通常の電子署名方式においては、１つの電子文書と電子署名との組を受理する検証鍵は１つである。そのため、ある電子文書と電子署名との組に対する責任は１人のユーザが持つことになる。しかし、上記の第１及び第２実施形態に係る代用鍵生成方法を利用すれば、１つの電子文書と電子署名との組を受理する新たな検証鍵（代用検証鍵）及び署名鍵（代用署名鍵）の組を生成することが可能になる。そのため、代用検証鍵と代用署名鍵との組を他のユーザに生成してもらえば、ある電子文書と電子署名との組に対する責任を他のユーザに分担してもらうことが可能になる。このように、上記の第１及び第２実施形態に係る代用鍵生成方法を用いることで責任分担型の電子署名方式が実現される。
【０２８０】
なお、責任分担型ではないが、署名者を特定されないようにする技術については、ＲＯＮＡＬＤ  Ｌ．ＲＩＶＥＳＴらによる報告（ＲＯＮＡＬＤ  Ｌ．ＲＩＶＥＳＴ  ＡＮＤ  ＡＤＩ  ＳＨＡＭＩＲ  ＡＮＤ  ＹＡＥＬ  ＴＡＵＭＡＮ，”Ｈｏｗ  ｔｏ  Ｌｅａｄｋ  ａ  Ｓｅｃｒｅｔ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ，ＡＳＩＡＣＲＹＰＴ  ２００１，７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，Ｇｏｌｄ  Ｃｏａｓｔ，Ａｕｓｔｒａｌｉａ，Ｄｅｃｅｍｂｅｒ  ９−１３，２００１，Ｐｒｏｃｅｅｄｉｎｇｓ，Ｓｐｒｉｎｇｅｒ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｖｏｌｕｍｅ  ２２４８；以下、リング署名方式と呼ぶ。）がある。
【０２８１】
上記のリング署名方式は、選択された複数の検証鍵の所有者のうち、誰が本当の署名者であるかを特定されないようにする技術に関する。そのため、内部告発等への利用が検討されている。リング署名方式を用いると、「あらかじめ最初に」複数の検証鍵を選択し、その選択した複数の検証鍵が受理するような電子署名（以下、リング署名）を生成することが可能になる。リング署名の検証は、選択した検証鍵の各々を用いて個別に行うのではなく、選択した複数の検証鍵の組がリング署名を受理するか否かを確認することで行われる。つまり、リング署名方式は、複数の検証鍵が受理するようなリング署名を生成可能な特殊な署名アルゴリズムと、そのリング署名を複数の検証鍵の組により検証する特殊な検証アルゴリズムとにより構成されるのである。
【０２８２】
一方で、上記の第１及び第２実施形態に係る代用鍵生成方法の場合、署名生成アルゴリズムは、１つの検証鍵が受理する電子署名を生成するアルゴリズムである。また、検証アルゴリズムは、電子署名を１つの検証鍵が受理することを検証するためのアルゴリズムである。そして、当該代用鍵生成方法は、「署名生成後に後付で」その電子署名を受理するような新たな検証鍵を生成するものである。従って、一度電子署名を生成した後に、その電子署名に対する責任を他のユーザに分担してもらうことが可能になるのである。このような責任分担は、上記のリング署名方式を如何に変形しても実現されないものである。ここでは参考までに上記の第１及び第２実施形態に係る代用鍵生成方法とリング署名方式との相違について述べ、同実施形態に係る技術の優位性について説明した。以上説明したように、上記の第１及び第２実施形態に係る代用鍵生成方法は様々な応用が可能である。
【０２８３】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０２８４】
１０    ネットワーク
１００、１３０、１５０    署名者端末
１０２、１３２、１５２    記憶部
１０４、１３４、１５４    鍵生成部
１０６、１３６、１５６    署名生成部
１０８、１３８、１５８    通信部
１１０、１４０、１６０    代用鍵生成部
２００、２３０、２５０    検証者端末
２０２    通信部
２０４    パラメータ生成部
２０６    記憶部
２０８、２３２、２５２    検証処理部
３００、３３０、３５０    代用鍵生成者端末
３０２、３３２、３５２    記憶部
３０４、３３４、３５４    代用署名鍵生成部
３０６、３３６、３５６    代用検証鍵生成部
３０８、３３８、３５８    通信部
３４０、３６０    署名生成部
【図１】
2010278482.tif 000022
【図２】
2010278482.tif 000023
【図３】
2010278482.tif 000024
【図４】
2010278482.tif 000025
【図５】
2010278482.tif 000026
【図６】
2010278482.tif 000027
【図７】
2010278482.tif 000028
【図８】
2010278482.tif 000029
【図９】
2010278482.tif 000030
【図１０】
2010278482.tif 000031
【図１１】
2010278482.tif 000032
【図１２】
2010278482.tif 000033
【図１３】
2010278482.tif 000034
【図１４】
2010278482.tif 000035
【図１５】
2010278482.tif 000036
【図１６】
2010278482.tif 000037
【図１７】
2010278482.tif 000038
【図１８】
2010278482.tif 000039
【図１９】
2010278482.tif 000040
【図２０】
2010278482.tif 000041
【図２１】
2010278482.tif 000042
【図２２】
2010278482.tif 000043
【図２３】
2010278482.tif 000044
【図２４】
2010278482.tif 000045