(57)【要約】【課題】同一の公開鍵に対して複数の秘密鍵を用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法を実現する、情報処理装置を提供する。【解決手段】検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択部と、前記鍵選択部が選択した秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行部と、を備える、情報処理装置が提供される。かかる情報処理装置は、同一の公開鍵に対応する複数の秘密鍵の中から１つの秘密鍵を選択して用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法を実現する。【選択図】図１
2014052588.tif 000002
【特許請求の範囲】
【請求項１】
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択部と、
前記鍵選択部が選択した秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行部と、
を備える、情報処理装置。
【請求項２】
前記鍵選択部は、前記検証者との間の認証処理または電子署名生成処理の際に前記複数の秘密鍵のいずれかをランダムに選択する、請求項１に記載の情報処理装置。
【請求項３】
前記鍵選択部は、前記処理実行部が前記検証者との間で前記認証処理を繰り返すことで１回の認証を完了させる、または前記処理実行部が前記電子署名生成処理を繰り返すことで１回の電子署名の生成を完了させる場合に、前記認証処理または前記電子署名生成処理ごとに前記複数の秘密鍵のいずれかをランダムに選択する、請求項２に記載の情報処理装置。
【請求項４】
前記処理実行部は、前記複数の秘密鍵の内の第１の秘密鍵にハッシュ関数を適用して得られる第１のハッシュ値を前記検証者に登録する、請求項１に記載の情報処理装置。
【請求項５】
前記処理実行部は、前記公開鍵認証方式による検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理の際に使用した秘密鍵にハッシュ関数を適用し、前記第１のハッシュ値と比較される第２のハッシュ値を前記検証者に送信する、請求項４に記載の情報処理装置。
【請求項６】
前記検証者による前記公開鍵認証方式または前記電子署名方式を用いた検証処理の際に前記第１のハッシュ値と前記第２のハッシュ値とを比較し、比較の結果に応じて所定の通知処理を実行する比較処理部をさらに備える、請求項５に記載の情報処理装置。
【請求項７】
前記複数の秘密鍵の各々が異なる装置に登録され、
前記鍵選択部は、該登録された秘密鍵を選択する、請求項１に記載の情報処理装置。
【請求項８】
前記公開鍵認証方式または電子署名方式は、ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する公開鍵認証方式である、請求項１に記載の情報処理装置。
【請求項９】
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、
前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、
を備える、情報処理方法。
【請求項１０】
コンピュータに、
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、
前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、
を実行させる、コンピュータプログラム。
【請求項１１】
１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式において、証明者が前記複数の秘密鍵の内の第１の秘密鍵にハッシュ関数を適用して得られる第１のハッシュ値及び前記証明者が検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理の際に使用した秘密鍵にハッシュ関数を適用して得られる第２のハッシュ値を取得し、前記公開鍵認証方式または前記電子署名方式を用いた検証処理の際に前記第１のハッシュ値と前記第２のハッシュ値とを比較し、比較の結果に応じて前記証明者への所定の通知処理を実行する比較処理部を備える、情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、情報処理方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【０００３】
本人確認のためには、一般に公開鍵暗号技術が広く用いられている。公開鍵暗号方式は、ある人（証明者）が、公開鍵及び秘密鍵を利用して、他の人（検証者）に本人であることを納得させるための認証方式である。
【０００４】
この公開鍵暗号技術において、秘密鍵の漏洩は最も避けなければならない事象である。秘密鍵は、本人確認のための認証や署名等で必要になるので、証明者は、必要に応じてアクセスできるようにしておくことが望まれる。例えば、証明者は、パスワードのように秘密鍵を記憶したり、紙にメモして持ち歩いたり、またＩＣカードのようなデバイスに格納して携帯すること等が求められる。例えば、秘密鍵を備えたＩＣカードによる認証システムを開示した技術として特許文献１等がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−８７２８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
公開鍵暗号技術において、秘密鍵はパスワードのように覚えやすいものにはなっていないので、証明者が秘密鍵を頭で記憶するのは容易なことではない。また、秘密鍵を紙にメモすると、他者による覗き行為や盗撮等によってその秘密鍵の内容が他者に漏洩してしまう危険性が高い。従来は、公開鍵暗号技術において、１つの公開鍵に対応する１種類の秘密鍵を用いて認証が行われていたので、秘密鍵が漏洩してしまうと、本人が使用した秘密鍵か、他者による成りすましが実行されているかが分からない。秘密鍵が漏洩してしまうと、何らかの方法でその成りすましを検知しない限り、鍵漏洩時以降の成りすましを防ぐことが出来ない。
【０００７】
一方、秘密鍵をＩＣカードのようなデバイスに格納した場合、そのＩＣカードを紛失しない限りは他者による成りすましは困難である。ＩＣカードを紛失した場合は、ＩＣカードに格納した秘密鍵の利用を中止するようにすれば、他者による成りすましを防ぎ、被害の拡大を抑えることが出来る。しかし、ＩＣカードのようなデバイスにはサイドチャネル攻撃という解析手法が提案されており、そのサイドチャネル攻撃に対する対策を施さなければ、秘密鍵が漏洩してしまう。
【０００８】
また、複数サーバへの分散による認証や、複数ユーザによる署名等を実現したい場合には、署名生成や認証の権利を複数人で共有できれば良く、例えば署名生成の権利を複数人で共有するための技術として、グループ署名技術が提案されている。ただし、このグループ署名技術は，署名生成の権利を複数人で共有する用途に特化した、特定のいくつかの署名手法のみを指すものであり、任意の署名方式，認証方式において上記の目的を達成することができない。
【０００９】
署名生成や認証の権利を複数人で共有する目的を実現するための他の手法として、単純に、複数ユーザによる同一の秘密鍵の共有が考えられる。しかし、この秘密鍵を共有する手法では、鍵の管理がおろそかなユーザからの秘密鍵の漏洩により、他のユーザは損害を被ってしまう。また、漏洩した秘密鍵から、秘密鍵を漏洩させたユーザを捜そうとしても、同一の秘密鍵を複数ユーザで共有していることから、秘密鍵を漏洩させたユーザの特定が困難になる状況も考えらえる。
【００１０】
そこで、本開示は、上記問題に鑑みてなされたものであり、本開示の目的とするところは、同一の公開鍵に対して複数の秘密鍵を用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法を実現する、新規かつ改良された情報処理装置、情報処理方法及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本開示によれば、検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択部と、前記鍵選択部が選択した秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行部と、を備える、情報処理装置が提供される。
【００１２】
また本開示によれば、検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、を備える、情報処理方法が提供される。
【００１３】
また本開示によれば、コンピュータに、検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、を実行させる、コンピュータプログラムが提供される。
【００１４】
また本開示によれば、１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式において、証明者が前記複数の秘密鍵の内の第１の秘密鍵にハッシュ関数を適用して得られる第１のハッシュ値及び前記証明者が検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理の際に使用した秘密鍵にハッシュ関数を適用して得られる第２のハッシュ値を取得し、前記公開鍵認証方式または前記電子署名方式を用いた検証処理の際に前記第１のハッシュ値と前記第２のハッシュ値とを比較し、比較の結果に応じて前記証明者への所定の通知処理を実行する比較処理部を備える、情報処理装置が提供される。
【発明の効果】
【００１５】
以上説明したように本開示によれば、同一の公開鍵に対して複数の秘密鍵を用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法を実現する、新規かつ改良された情報処理装置、情報処理方法及びコンピュータプログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図２】電子署名方式に係るアルゴリズムの構成について説明するための説明図である。
【図３】ｎパスの公開鍵認証方式に係るアルゴリズムの構成について説明するための説明図である。
【図４】秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理の概要を示す説明図である。
【図５】秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理を示す流れ図である。
【図６Ａ】平均波形の差分波形の例を示す説明図である。
【図６Ｂ】平均波形の差分波形の例を示す説明図である。
【図７】本開示の第１の実施形態の動作を示す流れ図である。
【図８】秘密鍵が格納された認証処理デバイス１００ｂと、検証処理を実行する検証処理デバイス２００ｂとの間の認証処理の概要を示す説明図である。
【図９】秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理を示す流れ図である。
【図１０】本開示の第２の実施形態の動作を示す流れ図である。
【図１１】鍵生成者が共通の秘密鍵ｘを生成してそれぞれ異なるユーザに秘密鍵ｘを与える認証システムの概念を示す説明図である。
【図１２】本開示の第３の実施形態にかかる認証システムの概念を示す説明図である。
【図１３】本開示の第３の実施形態にかかる認証システムの概念を示す説明図である。
【図１４】本開示の第１の実施形態の変形例の動作を示す流れ図である。
【図１５】３パスの公開鍵認証方式に係る効率的なアルゴリズムについて説明するための説明図である。
【図１６】本開示の各実施形態に係るアルゴリズムを実行することが可能な情報処理装置のハードウェア構成例について説明するための説明図である。
【発明を実施するための形態】
【００１７】
以下に添付図面を参照しながら、本開示の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１８】
なお、説明は以下の順序で行うものとする。
＜１．公開鍵認証方式及び秘密鍵の説明＞
＜２．本開示の第１の実施形態＞
［概要］
［動作］
＜３．本開示の第２の実施形態＞
［概要］
［動作］
＜４．本開示の第３の実施形態＞
［概要］
＜５．変形例＞
＜６．ハードウェア構成例＞
＜７．まとめ＞
【００１９】
＜１．公開鍵認証方式及び秘密鍵の説明＞
本開示の好適な実施の形態について説明する前に、まず、公開鍵認証方式及び電子署名方式の概要を説明し、続いて、後述する本開示の各実施形態で用いられる秘密鍵について説明する。
【００２０】
公開鍵認証方式とは、ある人（証明者）が、公開鍵ｐｋ及び秘密鍵ｓｋを利用して、他の人（検証者）に本人であることを納得させるための認証方式である。例えば、証明者Ａの公開鍵ｐｋＡは、検証者に公開される。一方、証明者Ａの秘密鍵ｓｋＡは、証明者により秘密に管理される。公開鍵認証方式では、公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知る者が証明者Ａ本人であるとみなされる。
【００２１】
証明者Ａが検証者Ｂに対して本人であることを証明しようとする場合、証明者Ａは、検証者Ｂと対話プロトコルを実行して、自身が公開鍵ｐｋＡに対応する秘密鍵ｓｋＡを知っていることを証明すればよい。そして、対話プロトコルにより証明者Ａが秘密鍵ｓｋＡを知っていることが検証者Ｂにより証明された場合、証明者Ａの正当性（本人であること）が証明される。
【００２２】
なお、公開鍵認証方式の安全性を確保するには、次に示す２つの条件が求められる。
【００２３】
１つ目の条件は、対話プロトコルを実行した際に秘密鍵ｓｋを持たない偽証者により偽証が成立してしまう確率を限りなく小さくすることである。この１つ目の条件が成り立つことを「健全性」と呼ぶ。つまり、健全性を有する対話プロトコルにおいては、秘密鍵ｓｋを持たない偽証者により、無視できない確率で偽証が成立することはないと言い換えられる。２つ目の条件は、対話プロトコルを実行したとしても、証明者Ａが有する秘密鍵ｓｋＡの情報が検証者Ｂに一切漏れることがないようにすることである。この２つ目の条件が成り立つことを「零知識性」と呼ぶ。
【００２４】
上記の健全性と零知識性を有する対話プロトコルを利用することにより、公開鍵認証方式の安全性が確保される。
【００２５】
公開鍵認証方式のモデルには、図１に示すように、証明者と検証者という２つのエンティティが存在する。証明者は、鍵生成アルゴリズムＧｅｎを用いて、証明者固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成する。次いで、証明者は、鍵生成アルゴリズムＧｅｎを用いて生成した秘密鍵ｓｋと公開鍵ｐｋの組を利用して検証者と対話プロトコルを実行する。このとき、証明者は、証明者アルゴリズムＰを利用して対話プロトコルを実行する。上記の通り、対話プロトコルにおいて、証明者は、証明者アルゴリズムＰを利用して、秘密鍵ｓｋを保有していることを検証者に証明する。
【００２６】
一方、検証者は、検証者アルゴリズムＶを利用して対話プロトコルを実行し、証明者が公開している公開鍵に対応する秘密鍵を、その証明者が保有しているか否かを検証する。つまり、検証者は、証明者が公開鍵に対応する秘密鍵を保有しているか否かを検証するエンティティである。このように、公開鍵認証方式のモデルは、証明者と検証者という２つのエンティティ、及び、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶという３つのアルゴリズムにより構成される。
【００２７】
なお、以下の説明において、「証明者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰを実行する主体は、「証明者」のエンティティに対応する情報処理装置である。同様に、検証者アルゴリズムＶを実行する主体は、情報処理装置である。
【００２８】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、証明者により利用される。そして、鍵生成アルゴリズムＧｅｎは、証明者に固有の秘密鍵ｓｋと公開鍵ｐｋの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された公開鍵ｐｋは公開される。そして、公開された公開鍵ｐｋは、検証者により利用される。一方、鍵生成アルゴリズムＧｅｎにより生成された秘密鍵ｓｋは、証明者が秘密に管理する。そして、秘密に管理される秘密鍵ｓｋは、検証者に対して公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するために利用される。形式的に、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、秘密鍵ｓｋと公開鍵ｐｋを出力するアルゴリズムとして、下記の式（１）のように表現される。
【００２９】
【数１】
2014052588.tif 000003
【００３０】
（証明者アルゴリズムＰ）
証明者アルゴリズムＰは、証明者により利用される。そして、証明者アルゴリズムＰは、公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを証明するアルゴリズムである。証明者アルゴリズムＰは、証明者の秘密鍵ｓｋと公開鍵ｐｋを入力とし、検証者との対話プロトコルを実行するアルゴリズムとして定義される。
【００３１】
（検証者アルゴリズムＶ）
検証者アルゴリズムＶは、検証者により利用される。そして、検証者アルゴリズムＶは、対話プロトコルの中で、公開鍵ｐｋに対応する秘密鍵ｓｋを証明者が保有しているか否かを検証するアルゴリズムである。検証者アルゴリズムＶは、証明者の公開鍵ｐｋを入力とし、証明者との間で対話プロトコルを実行した後、０又は１（１ｂｉｔ）を出力するアルゴリズムとして定義される。なお、出力０の場合には証明者が不正なものであり、出力１の場合には証明者が正当なものであるとする。形式的に、検証者アルゴリズムＶは、下記の式（２）のように表現される。
【００３２】
【数２】
2014052588.tif 000004
【００３３】
上記の通り、公開鍵認証方式は、安全性を確保するため、健全性と零知識性という２つの条件を満たすことが求められる。しかし、証明者が秘密鍵ｓｋを保有していることを証明者に証明させるためには、証明者が秘密鍵ｓｋに依存した手続きを実行し、その結果を検証者に通知して、その通知内容に基づく検証を検証者に実行させる必要がある。秘密鍵ｓｋに依存した手続きを実行するのは、健全性を担保するために必要である。一方で、この手続きの結果を検証者に通知しても、秘密鍵ｓｋの情報が一切検証者に漏れないようにする必要がある。そのため、これらの要件を満たすように、上記の鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶが設計されることが必要になる。
【００３４】
次に、電子署名方式のアルゴリズムについて概要を説明する。図２は、電子署名方式のアルゴリズムについて概要を説明するための説明図である。
【００３５】
紙文書とは異なり、ある電子化されたデータに対して押印したり署名を記載したりすることはできない。そのため、電子化されたデータの作成者を証明するためには、紙文書に押印したり署名を記載したりするのと同等の効果が得られる電子的な仕組みを必要とする。この仕組みが電子署名である。電子署名とは、データの作成者しか知らない署名データをデータに関連付けて受領者に提供し、その署名データを受領者側で検証する仕組みのことを言う。
【００３６】
（モデル）
電子署名方式のモデルには、図２に示すように、署名者及び検証者という２つのエンティティが存在する。そして、電子署名方式のモデルは、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより構成される。
【００３７】
署名者は、鍵生成アルゴリズムＧｅｎを利用して署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成する。また、署名者は、署名生成アルゴリズムＳｉｇを利用して文書Ｍに付与する電子署名σを生成する。つまり、署名者は、文書Ｍに電子署名を付与するエンティティである。一方、検証者は、署名検証アルゴリズムＶｅｒを利用して文書Ｍに付与された電子署名σを検証する。つまり、検証者は、文書Ｍの作成者が署名者であるか否かを確認するために、電子署名σを検証するエンティティである。
【００３８】
なお、以下の説明において、「署名者」「検証者」という表現を用いるが、これらの表現はあくまでもエンティティを意味するものである。従って、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇを実行する主体は、「署名者」のエンティティに対応する情報処理装置である。同様に、署名検証アルゴリズムＶｅｒを実行する主体は、情報処理装置である。
【００３９】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、署名者により利用される。鍵生成アルゴリズムＧｅｎは、署名者固有の署名鍵ｓｋと検証鍵ｐｋとの組を生成するアルゴリズムである。鍵生成アルゴリズムＧｅｎにより生成された検証鍵ｐｋは公開される。一方、鍵生成アルゴリズムＧｅｎにより生成された署名鍵ｓｋは、署名者により秘密に管理される。そして、署名鍵ｓｋは、文書Ｍに付与される電子署名σの生成に利用される。例えば、鍵生成アルゴリズムＧｅｎは、セキュリティパラメータ１λ（λは０以上の整数）を入力とし、署名鍵ｓｋ及び公開鍵ｐｋを出力する。この場合、鍵生成アルゴリズムＧｅｎは、形式的に、下記の式（３）のように表現することができる。
【００４０】
【数３】
2014052588.tif 000005
【００４１】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、署名者により利用される。署名生成アルゴリズムＳｉｇは、文書Ｍに付与される電子署名σを生成するアルゴリズムである。署名生成アルゴリズムＳｉｇは、署名鍵ｓｋと文書Ｍとを入力とし、電子署名σを出力するアルゴリズムである。この署名生成アルゴリズムＳｉｇは、形式的に、下記の式（４）のように表現することができる。
【００４２】
【数４】
2014052588.tif 000006
【００４３】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証者により利用される。署名検証アルゴリズムＶｅｒは、電子署名σが文書Ｍに対する正当な電子署名であるか否かを検証するアルゴリズムである。署名検証アルゴリズムＶｅｒは、署名者の検証鍵ｐｋ、文書Ｍ、電子署名σを入力とし、０又は１（１ｂｉｔ）を出力するアルゴリズムである。この署名検証アルゴリズムＶｅｒは、形式的に、下記の式（５）のように表現することができる。なお、検証者は、署名検証アルゴリズムＶｅｒが０を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを拒否する場合）に電子署名σが不当であると判断し、１を出力した場合（公開鍵ｐｋが文書Ｍと電子署名σを受理する場合）に電子署名σが正当であると判断する。
【００４４】
【数５】
2014052588.tif 000007
【００４５】
（ｎパスの公開鍵認証方式）
次に、図３を参照しながら、ｎパスの公開鍵認証方式について説明する。図３は、ｎパスの公開鍵認証方式について説明するための説明図である。
【００４６】
上記の通り、公開鍵認証方式は、対話プロトコルの中で、証明者が公開鍵ｐｋに対応する秘密鍵ｓｋを保有していることを検証者に証明する認証方式である。また、対話プロトコルは、健全性及び零知識性という２つの条件を満たす必要がある。そのため、対話プロトコルの中では、図３に示すように、証明者及び検証者の双方がそれぞれ処理を実行しながらｎ回の情報交換を行う。
【００４７】
ｎパスの公開鍵認証方式の場合、証明者アルゴリズムＰを用いて証明者により処理（工程＃１）が実行され、情報Ｔ１が検証者に送信される。次いで、検証者アルゴリズムＶを用いて検証者により処理（工程＃２）が実行され、情報Ｔ２が証明者に送信される。さらに、ｋ＝３〜ｎについて処理の実行及び情報Ｔｋの送信が順次行われ、最後に処理（工程＃ｎ＋１）が実行される。このように、情報がｎ回送受信される方式のことを「ｎパス」の公開鍵認証方式と呼ぶ。
【００４８】
以上、ｎパスの公開鍵認証方式について説明した。
【００４９】
上述した、鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶの設計の際の要件を満たすものとして、例えば特開２０１２−９８６９０号公報等で開示されている、多次多変数連立方程式に対する求解問題の困難性に安全性の根拠をおく公開鍵認証方式及び電子署名方式がある。上記文献で用いられる関数は、ｍ本のｎ変数の２次多項式（ｍ、ｎはいずれも２以上の整数）で構成される関数であるが、この関数を用いることで、上記文献による公開鍵認証方式は１つの公開鍵から複数の秘密鍵を生成することができる。上記文献で用いられる、ｍ本のｎ変数多次多項式で構成される関数を、ＭＱ（Ｍｕｌｔｉｖａｒｉａｔｅ  Ｑｕａｄｒａｔｉｃ）関数と称する。
【００５０】
まず、上記文献による公開鍵認証方式の鍵生成アルゴリズムを説明する。ここでは、公開鍵ｐｋの一部として２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を利用する場合について考える。但し、２次多項式ｆｉ（ｘ）は、下記の式（６）のように表現されるものとする。また、ベクトル（ｘ１，…，ｘｎ）をｘと表記し、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））を多変数多項式Ｆ（ｘ）と表記することにする。
【００５１】
【数３】
2014052588.tif 000008
【００５２】
また、２次多項式の組（ｆ１（ｘ），…，ｆｍ（ｘ））は、下記の式（７）のように表現することができる。また、Ａ１，…，Ａｍは、ｎ×ｎ行列である。さらに、ｂ１，…，ｂｍはそれぞれｎ×１ベクトルである。
【００５３】
【数４】
2014052588.tif 000009
【００５４】
この表現を用いると、多変数多項式Ｆは、下記の式（８）及び式（９）のように表現することができる。この表現が成り立つことは、下記の式（１０）から容易に確認することができる。
【００５５】
【数８】
2014052588.tif 000010
【００５６】
このようにＦ（ｘ＋ｙ）をｘに依存する第１の部分と、ｙに依存する第２の部分と、ｘ及びｙの両方に依存する第３の部分とに分けたとき、第３の部分に対応する項Ｇ（ｘ，ｙ）は、ｘ及びｙについて双線形になる。以下、項Ｇ（ｘ，ｙ）を双線形項と呼ぶ場合がある。この性質を利用すると、効率的なアルゴリズムを構築することが可能になる。
【００５７】
例えば、ベクトルｔ０∈Ｋｎ、ｅ０∈Ｋｍを用いて、多変数多項式Ｆ（ｘ＋ｒ）のマスクに利用する多変数多項式Ｆ１（ｘ）をＦ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０と表現する。この場合、多変数多項式Ｆ（ｘ＋ｒ０）とＦ１（ｘ）との和は、下記の式（１１）のように表現される。ここで、ｔ１＝ｒ０＋ｔ０、ｅ１＝Ｆ（ｒ０）＋ｅ０とおけば、多変数多項式Ｆ２（ｘ）＝Ｆ（ｘ＋ｒ０）＋Ｆ１（ｘ）は、ベクトルｔ１∈Ｋｎ、ｅ１∈Ｋｍにより表現することができる。そのため、Ｆ１（ｘ）＝Ｇ（ｘ，ｔ０）＋ｅ０に設定すれば、Ｋｎ上のベクトル及びＫｍ上のベクトルを用いてＦ１及びＦ２を表現できるようになり、通信に必要なデータサイズの少ない効率的なアルゴリズムを実現することが可能になる。
【００５８】
【数９】
2014052588.tif 000011
【００５９】
なお、Ｆ２（或いはＦ１）からｒ０に関する情報が一切漏れることはない。例えば、ｅ１及びｔ１（或いはｅ０及びｔ０）を与えられても、ｅ０及びｔ０（或いはｅ１及びｔ１）を知らない限り、ｒ０の情報を一切知ることはできない。従って、零知識性が担保される。
【００６０】
ここでＭＱ関数は、ｍ＝ｎの場合に、Ｆ（ｘ１）＝Ｆ（ｘ２）となるｘ１、ｘ２を求めることができる。具体的な導出方法は以下の通りである。
【００６１】
ｎ＝ｍとした際に、ＭＱ関数に対して、Δ∈ＧＦ（２ｎ）を与えられた時に、ｘ（ｓ．ｔ．  Ｆ（ｘ）＝Ｆ（ｘ＋Δ））を出力するというアルゴリズムが存在する。なぜなら、以下の関係が成り立つからである。
Ｆ（ｘ）＝Ｆ（ｘ＋Δ）⇔Ｆ（Δ）＋Ｇ（ｘ，Δ）＝０
【００６２】
上述の関係は、ｘ＝（ｘ１，…，ｘｎ），ｘｉ＝ＧＦ（２）に関する一次の連立方程式となる。変数ｘｉ（ｉ＝１，２，・・・，ｎ）の個数と、式の本数ｍとが一致しているので、上記の連立一次方程式から解ｘを導出することができる。
【００６３】
また、ｎ＝ｃｍ（ｃは２以上の整数）とした際に、ＭＱ関数に対して、Δ１，・・・，Δｃ∈ＧＦ（２ｎ）を与えられた時に、ｘ（ｓ．ｔ．  Ｆ（ｘ）＝Ｆ（ｘ＋Δ１）＝・・・＝Ｆ（ｘ＋Δｃ））を出力するというアルゴリズムが存在する。なぜなら、以下の関係が成り立つからである。
Ｆ（ｘ）＝Ｆ（ｘ＋Δ１）⇔Ｆ（Δ１）＋Ｇ（ｘ，Δ１）＝０
・・・
Ｆ（ｘ）＝Ｆ（ｘ＋Δｃ）⇔Ｆ（Δｃ）＋Ｇ（ｘ，Δｃ）＝０
【００６４】
上述のそれぞれの方程式は、ｘ＝（ｘ１，…，ｘｎ），ｘｉ＝ＧＦ（２）に関する一次の連立方程式となる。上述のそれぞれの方程式を組み合わせると、変数ｘｉ（ｉ＝１，２，・・・，ｎ）に対して、式の本数がｃｍの連立一次方程式となる。そのため、ｎ＝ｍの場合と同様に、上記の連立一次方程式から解ｘを導出することができる。
【００６５】
このように、１つの公開鍵から複数の秘密鍵を生成することができる公開鍵認証方式を用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法が実現できる。以下では、１つの公開鍵から複数の秘密鍵を生成することができる公開鍵認証方式の適用例について詳細に説明する。
【００６６】
＜２．本開示の第１の実施形態＞
［概要］
まず、本開示の第１の実施形態に概要について説明する。本開示の第１の実施形態は、ＩＣカードのようなデバイスに秘密鍵を格納し、本人確認のために、当該デバイスで認証処理を実行する場合に適用可能な技術である。
【００６７】
図４は、秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理の概要を示す説明図である。認証処理デバイス１００ａには、上述の鍵生成アルゴリズムＧｅｎによって生成される秘密鍵ｘが認証処理に先立って格納される。また検証処理デバイス２００ａには、上述の鍵生成アルゴリズムＧｅｎによって生成される公開鍵Ｆ（ｘ）が認証処理に先立って格納される。認証処理デバイス１００ａは、例えばＩＣカードであり、検証処理デバイス２００ａは、例えばサーバ装置、金融機関のＡＴＭ（自動現金預け払い機）等である。そして認証処理デバイス１００ａがリーダライタにかざされたことを契機に、認証処理デバイス１００ａと検証処理デバイス２００ａとの間の認証プロトコルが実行されるものとする。
【００６８】
図５は、秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理を示す流れ図である。
【００６９】
本人であることを認証してもらいたいユーザは、予め上述の鍵生成アルゴリズムＧｅｎによって秘密鍵ｘ及び公開鍵Ｆ（ｘ）を生成する（ステップＳ１１）。この秘密鍵ｘ及び公開鍵Ｆ（ｘ）の生成は、鍵生成アルゴリズムＧｅｎを実行することが可能な情報処理装置で行われる。
【００７０】
ユーザは、秘密鍵ｘ及び公開鍵Ｆ（ｘ）を生成すると、秘密鍵ｘは秘密を保ったまま認証処理デバイス１００ａに登録し（ステップＳ１２）、公開鍵Ｆ（ｘ）は検証処理デバイス２００ａに登録する（ステップＳ１３）。そしてユーザが認証処理デバイス１００ａに対して認証実行を指示すると（ステップＳ１４）、認証処理デバイス１００ａで証明者アルゴリズムＰが実行され、検証処理デバイス２００ａで検証者アルゴリズムＶが実行されることで、認証処理デバイス１００ａと検証処理デバイス２００ａとの間で認証処理が実行される（ステップＳ１５）。
【００７１】
ＩＣカードのようなデバイスに秘密鍵ｘを格納しておけば、そのデバイスを紛失しない限り秘密鍵ｘの内容が第三者に漏洩することは無いはずである。しかし、上述したように、ＩＣカードのようなデバイスにはサイドチャネル攻撃という解析手法が提案されている。そのサイドチャネル攻撃の中に、電力解析攻撃がある。電力解析攻撃は、暗号アルゴリズムが実装されたデバイスの消費電力から、そのデバイスに格納されている秘密鍵を抽出する攻撃手法である。
【００７２】
ＩＣカードのようなデバイスの消費電力は、入力に依存して変化することが知られている。そのため、デバイスに格納された秘密鍵の値に依存した消費電力の変化を観測することで、秘密鍵の値を解析することが出来る場合がある。基本的には、消費電力にはノイズが混じっているので、電力解析攻撃では、複数の波形を統計処理することで、ノイズの影響を小さくして秘密鍵を抽出する。その一手法として、Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  （ＤＰＡ）が提案されている（Ｐａｕｌ  Ｋｏｃｈｅｒ，  Ｊｏｓｈｕａ  Ｊａｆｆｅ，  Ｂｅｎｊａｍｉｎ  Ｊｕｎ，  “Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ”，  ＣＲＹＰＴＯ’９９）。
【００７３】
ここで、ＭＱ関数を用いた署名方式（ＭＱ署名方式）に対する１ｂｉｔ  ＤＰＡの例を説明する。ＭＱ署名方式では，秘密鍵ｘに対して，乱数ｒ０との排他的論理和演算を行い、その後，乱数ｒ０は確率的に署名内の要素として出力される。この演算を利用することで、秘密鍵ｘのｉ番目のビットｘｉを解析することが出来る。具体的には以下のようにして１ｂｉｔ  ＤＰＡによりｘｉを解析することができる。
【００７４】
まず、複数回の署名生成後に、乱数ｒ０が出力される署名を集める。次に、乱数ｒ０のｉ番目のビットｒ０，ｉの値に応じて、集めた署名を２つのグループに分ける。そして、グループごとに平均波形を計算し、その２つの平均波形の差分波形を計算する。この差分波形のピークの出方によって、秘密鍵ｘのｉ番目のビットｘｉを解析することが出来る。
【００７５】
図６Ａ及び図６Ｂは、平均波形の差分波形の例を示す説明図である。図６Ａは、秘密鍵ｘのｉ番目のビットｘｉが０の時に期待できる平均波形の差分波形の例であり、図６Ｂは、秘密鍵ｘのｉ番目のビットｘｉが１の時に期待できる平均波形の差分波形の例である。ｘｉが０の時は、乱数ｒ０の値と、乱数ｒ０と秘密鍵ｘ０との排他的論理和の値（ｒ０＋ｘ０）とが一致する。そのため、それぞれの値のロード時とストア時の消費電力が類似し、図６Ａに示すように、平均波形の２つのピークの正負が同じになる。一方、ｘｉが１の時は、乱数ｒ０の値と、乱数ｒ０と秘密鍵ｘ０との排他的論理和の値（ｒ０＋ｘ０）とが異なる。そのため、それぞれの値のロード時とストア時の消費電力が大きく異なり、図６Ｂに示すように、平均波形の２つのピークの正負が異なる。これを秘密鍵ｘの全てのビットに対して解析を試みることで、秘密鍵ｘの内容が電力解析攻撃によって抽出されてしまう。
【００７６】
これはＭＱ署名方式の際の１ｂｉｔ  ＤＰＡの例であるが、ＭＱ認証方式でも同様の処理が存在する。従って、ＭＱ署名方式の１ｂｉｔ  ＤＰＡをＭＱ認証方式の１ｂｉｔ  ＤＰＡに容易に拡張することができる。
【００７７】
そこで本開示の第１の実施形態では、電力解析攻撃によって得られる平均波形の差分波形からビットの値を推定できないようにする。具体的には、上述したような、１つの公開鍵に対応する複数の秘密鍵を生成し、認証処理の際に、認証処理デバイス１００ａは、その複数の秘密鍵の中から１つの秘密鍵をランダムに選択する。このように、複数の秘密鍵の中から１つの秘密鍵をランダムに選択して認証処理を実行することで、認証処理デバイス１００ａは、電力解析攻撃によって秘密鍵が抽出されるのを防ぐことができる。
【００７８】
［動作］
図７は、本開示の第１の実施形態にかかる、秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理を示す流れ図である。図７に示した流れ図は、本人であることを認証してもらいたいユーザが、公開鍵及びその公開鍵に対応する２つの秘密鍵を生成する場合の認証処理について示したものである。
【００７９】
本人であることを認証してもらいたいユーザは、予め上述の鍵生成アルゴリズムＧｅｎによって秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成する（ステップＳ１０１）。ここで、公開鍵Ｆ（ｘ１）は、Ｆ（ｘ１）＝Ｆ（ｘ２）を満たすものである。この秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）の生成は、鍵生成アルゴリズムＧｅｎを実行することが可能な情報処理装置で行われる。
【００８０】
ユーザは、秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成すると、秘密鍵ｘ１、ｘ２を秘密を保ったまま認証処理デバイス１００ａに登録し（ステップＳ１０２）、公開鍵Ｆ（ｘ１）を検証処理デバイス２００ａに登録する（ステップＳ１０３）。そしてユーザが認証処理デバイス１００ａに対して認証実行を指示すると（ステップＳ１０４）、認証処理デバイス１００ａは、まずｉ∈｛１，２｝をランダムに選択する（ステップＳ１０５）。そして、認証処理デバイス１００ａと検証処理デバイス２００ａとの間で、上記ステップＳ１０５で選択されたｉに対応する秘密鍵ｘｉを用いた、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理が実行される（ステップＳ１０６）。
【００８１】
このように、認証処理の際に、認証処理デバイス１００ａが２つの秘密鍵の中から１つの秘密鍵をランダムに選択することで、電力解析攻撃による１ｂｉｔ  ＤＰＡが困難になる。秘密鍵ｘ１のｉ番目のビットｘ１ｉと、秘密鍵ｘ２のｉ番目のビットｘ２ｉとが異なっていると、統計処理が正確に実施できなくなるからである。上述した１ｂｉｔ  ＤＰＡは、平均波形の差分波形を計算することであるビットの値を推測するものであるが、あるビットの値が処理毎に異なると、平均波形の差分波形を計算してもピークが現れなくなるので、そのビットの値を推測することが極めて困難になる。
【００８２】
一方、認証処理デバイス１００ａは、認証実行時に２つの秘密鍵の中から１つの秘密鍵を選択するだけなので、電力解析攻撃の対策のために余計な回路を組み込んだり、余計な処理を実行したりする必要がない。従って、認証処理デバイス１００ａは、速度の低下や消費電力の増加がほとんど無く、電力解析攻撃の対策を低コストで実現することができる。
【００８３】
＜３．本開示の第２の実施形態＞
［概要］
次に、本開示の第２の実施形態に概要について説明する。本開示の第２の実施形態は、本人確認のために、ユーザが予め生成した秘密鍵の内容を認証時にデバイスに入力する場合に適用可能な技術である。
【００８４】
図８は、認証処理を実行する認証処理デバイス１００ｂと、検証処理を実行する検証処理デバイス２００ｂとの間の認証処理の概要を示す説明図である。認証処理デバイス１００ｂには、上述の鍵生成アルゴリズムＧｅｎによって生成される秘密鍵ｘが、本人確認を受けたいユーザによって入力される。また検証処理デバイス２００ｂには、上述の鍵生成アルゴリズムＧｅｎによって生成される公開鍵Ｆ（ｘ）が、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理に先立って格納される。
【００８５】
認証処理デバイス１００ｂは、例えばフロントエンドの装置であり、例えばパーソナルコンピュータ、スマートフォン、タブレット等の情報処理装置の他、金融機関のＡＴＭ（自動現金預け払い機）等であってもよい。検証処理デバイス２００ｂは、例えばバックエンドの装置であり、サーバ装置等である。そして認証処理デバイス１００ｂは、ユーザからの秘密鍵の入力を契機に、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる、認証処理デバイス１００ｂと検証処理デバイス２００ｂとの間の認証プロトコルが実行されるものとする。
【００８６】
図９は、認証処理を実行する認証処理デバイス１００ｂと、検証処理を実行する検証処理デバイス２００ｂとの間の、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理を示す流れ図である。
【００８７】
本人であることを認証してもらいたいユーザは、予め上述の鍵生成アルゴリズムＧｅｎによって秘密鍵ｘ及び公開鍵Ｆ（ｘ）を生成する（ステップＳ２１）。この秘密鍵ｘ及び公開鍵Ｆ（ｘ）の生成は、鍵生成アルゴリズムＧｅｎを実行することが可能な情報処理装置で行われる。
【００８８】
ユーザは、秘密鍵ｘ及び公開鍵Ｆ（ｘ）を生成すると、公開鍵Ｆ（ｘ）を検証処理デバイス２００ｂに登録する（ステップＳ２２）。秘密鍵ｘは秘密を保ったまま、かつユーザがいつでもアクセスできる状態にする。秘密鍵の漏洩を防ぐならば、ユーザは秘密鍵ｘの内容を頭に記憶することが望ましいが、秘密鍵ｘはパスワードのように覚えやすいものにはなっていないので、忘れた時のために紙などにメモしておくことを想定する。そしてユーザは、認証処理デバイス１００ｂと検証処理デバイス２００ｂとで認証処理を実行させるために、秘密鍵ｘを認証処理デバイス１００ｂに入力する（ステップＳ２３）。秘密鍵ｘが認証処理デバイス１００ｂに入力されると、認証処理デバイス１００ｂと検証処理デバイス２００ｂとの間で、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理が実行される（ステップＳ２４）。
【００８９】
秘密鍵を頭で記憶している状況に比べ、秘密鍵を紙などにメモしておいた場合は、他者によるメモの覗き行為や盗撮等によって、その秘密鍵の内容が他者に漏洩してしまう危険性が高い。このように、認証処理デバイス１００ｂに秘密鍵ｘが外部から直接入力されて、認証処理デバイス１００ｂと検証処理デバイス２００ｂとの間で証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理が実行される場合、その秘密鍵ｘが他者に漏洩してしまうと、その他者は、秘密鍵ｘを用いて正規の認証が実行可能になってしまう。その際に、検証処理デバイス２００ｂは、秘密鍵ｘを入力したのが、正規のユーザなのか、他者なのかを区別することができなくなってしまう。
【００９０】
そこで本開示の第２の実施形態では、上述したような、１つの公開鍵に対応する複数の秘密鍵を生成し、１つは通常に使われる秘密鍵としてユーザが記憶して、もう１つは、秘密鍵の内容を忘れた時のための臨時用として、例えば紙などにユーザがメモしておく。そして検証処理デバイス２００ｂは、認証処理時に、認証処理デバイス１００ｂに入力された秘密鍵がどちらの秘密鍵かを判断し、通常に使われる秘密鍵でない臨時用の秘密鍵、すなわちユーザが紙などにメモした秘密鍵が使われたかどうかを判定する。認証処理時に、臨時用の秘密鍵が使われたことを検証処理デバイス２００ｂで判断するとともに、臨時用の秘密鍵が使われると、臨時用の秘密鍵が使われた旨をユーザに通知することで、ユーザによる意図的な臨時用の秘密鍵の使用なのか、臨時用の秘密鍵の漏洩があったのかをユーザに気付かせることができる。
【００９１】
［動作］
図１０は、本開示の第２の実施形態にかかる、秘密鍵が入力される認証処理デバイス１００ｂと、検証処理を実行する検証処理デバイス２００ｂとの間の認証処理を示す流れ図である。図１０に示した流れ図は、本人であることを認証してもらいたいユーザが、公開鍵及びその公開鍵に対応する２つの秘密鍵を生成する場合の認証処理について示したものである。
【００９２】
本人であることを認証してもらいたいユーザは、予め上述の鍵生成アルゴリズムＧｅｎによって秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成するとともに、秘密鍵ｘ１、ｘ２に対してハッシュ関数ｈを適用し、ハッシュ値ｚ２＝ｈ（ｘ２）を生成する（ステップＳ２０１）。ここで、公開鍵Ｆ（ｘ１）は、Ｆ（ｘ１）＝Ｆ（ｘ２）を満たすものである。この秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）の生成は、鍵生成アルゴリズムＧｅｎを実行することが可能な情報処理装置で行われる。例えば、ユーザは秘密鍵ｘ１を通常使用時の秘密鍵として、頭に記憶するか紙などにメモして他者に見られないように厳重に保管し、秘密鍵ｘ２を臨時用の秘密鍵として紙媒体などにメモして常時携帯する。
【００９３】
ユーザは、鍵生成アルゴリズムＧｅｎを実行して秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成し、さらに秘密鍵ｘ２にハッシュ関数を適用してハッシュ値ｚ２を生成すると、公開鍵Ｆ（ｘ１）と、ハッシュ値ｚ２とを検証処理デバイス２００ｂに登録する（ステップＳ２０２）。そしてユーザは、認証処理デバイス１００ｂと検証処理デバイス２００ｂとの間で証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理を実行させるために、秘密鍵ｘ１、ｘ２の中からいずれか１つの秘密鍵ｘを認証処理デバイス１００ｂに入力する（ステップＳ２０３）。
【００９４】
ユーザから秘密鍵が入力されると、認証処理デバイス１００ｂは、入力された秘密鍵にハッシュ関数ｈを適用してハッシュ値ｚを計算し、そのハッシュ値ｚを検証処理デバイス２００ｂに送信する（ステップＳ２０４）。検証処理デバイス２００ｂは、認証処理デバイス１００ｂから送信されたハッシュ値ｚが、予めユーザから登録されたハッシュ値ｚ２と一致するかどうか比較する。
【００９５】
ハッシュ値ｚがｚ２と一致していなければ、検証処理デバイス２００ｂは特に何も処理をしないが、ハッシュ値ｚがｚ２と一致していれば、検証処理デバイス２００ｂはユーザに対し、臨時用の秘密鍵ｘ２が認証処理デバイス１００ｂに入力された旨を、メール等の何らかの方法で通知する（ステップＳ２０５）。
【００９６】
そして、認証処理デバイス１００ｂと検証処理デバイス２００ｂとの間で、上記ステップＳ２０３で入力された秘密鍵ｘを用いた、証明者アルゴリズムＰおよび検証者アルゴリズムＶによる認証処理が実行される（ステップＳ２０６）。そしてユーザは、検証処理デバイス２００ｂから通知を受けていれば、臨時用の秘密鍵ｘ２の身に覚えのない利用かどうかを判断することで、鍵の漏洩を検知することができる（ステップＳ２０７）。
【００９７】
上述したように、本実施形態では、ユーザは秘密鍵ｘ２を臨時用の秘密鍵として紙媒体などにメモして常時携帯することを想定している。従って、この秘密鍵ｘ２は、上記紙媒体などの紛失など、何らかの理由で他者にアクセスされる可能性が高い情報である。
【００９８】
しかし、このように、秘密鍵ｘ２から生成したハッシュ値を、公開鍵とともに検証処理デバイス２００ｂに登録しておくことで、ユーザは、認証処理時に使用された秘密鍵ｘ２が、ユーザ自身が入力したのか、他者が入力したのかを、検証処理デバイス２００ｂからの通知で知ることが出来る。検証処理デバイス２００ｂからの通知により、秘密鍵ｘ１、ｘ２を使用するユーザは臨時用の秘密鍵の漏洩があったかどうかを検知でき、漏洩があった場合は、検証処理デバイス２００ｂに登録した公開鍵を無効化することで被害の拡大を防ぐことができる。
【００９９】
なお上述の説明では、ハッシュ値ｚがｚ２と一致していなければ、検証処理デバイス２００ｂは特に何も処理をしないとしたが、本開示は係る例に限定されるものではない。ハッシュ値ｚがｚ２と一致していないということは、通常使用時の秘密鍵ｘ１が使用されたことになるので、検証処理デバイス２００ｂは、通常使用時の秘密鍵ｘ１が使用されたことを、メール等の何らかの方法でユーザに通知するようにしても良い。
【０１００】
＜４．本開示の第３の実施形態＞
［概要］
次に、本開示の第３の実施形態に概要について説明する。本開示の第３の実施形態は、２以上の秘密鍵をそれぞれ異なるユーザに与えて認証の権利を該ユーザ間で共有する場合に適用可能な技術である。
【０１０１】
図１１は、鍵生成者が共通の秘密鍵ｘを生成してそれぞれ異なるユーザに秘密鍵ｘを与える認証システムの概念を示す説明図である。鍵生成者は、公開鍵ｙ＝Ｆ（ｘ）及び秘密鍵ｘを生成し、生成した秘密鍵をユーザ１、２に配送する。鍵生成者から秘密鍵ｘが配送されたユーザ１、２は、その秘密鍵ｘを使用した認証を実行する。つまり、共通の秘密鍵ｘをユーザ１、２で共有する。
【０１０２】
しかし、このように同じ秘密鍵を複数のユーザに与えると、秘密鍵がインターネット上のＷｅｂサイトに掲載されるなど、秘密鍵が漏れたことが発覚した場合に、どのユーザが秘密鍵の内容を漏らしたのかを検証することができない。そこで本開示の第３の実施形態では、秘密鍵が漏れたことが発覚した場合に、どのユーザが秘密鍵を漏らしたのかを容易に追跡可能な仕組みを開示する。
【０１０３】
上述してきたように、秘密鍵の生成にＭＱ関数を用いると、同一の公開鍵に対応する異なる複数の秘密鍵を生成することができる。従って、複数のユーザにそれぞれ異なる秘密鍵を配送することで、秘密鍵が漏れたことが発覚した場合にどのユーザが秘密鍵を漏らしたのかを容易に追跡できるので、秘密鍵の漏洩に対する抑止力となる。
【０１０４】
図１２は、本開示の第３の実施形態にかかる認証システムの概念を示す説明図である。図１２に示したのは、鍵生成者が異なる秘密鍵ｘ１，ｘ２を生成して、それぞれ異なるユーザに秘密鍵ｘ１，ｘ２を与える認証システムの概念である。
【０１０５】
鍵生成者は、上述の鍵生成アルゴリズムを用いて、同一の公開鍵ｙに対応する異なる複数の秘密鍵ｘ１、ｘ２を生成し、ユーザ１には秘密鍵ｘ１を、ユーザ２には秘密鍵ｘ２をそれぞれ配送する。また鍵生成者は、どのユーザにどの秘密鍵を配送したかを管理しておく。そして、ユーザ１は秘密鍵ｘ１を用いて、ユーザ２は秘密鍵ｘ２を用いて、検証者との間でそれぞれ認証処理や署名生成処理を実行する。
【０１０６】
このように、同一の公開鍵に対応する異なる複数の秘密鍵を生成し、各ユーザに異なる秘密鍵を配送して、どのユーザにどの秘密鍵を配送したかを管理しておくことで、秘密鍵が漏れたことが発覚した場合にどのユーザが秘密鍵を漏らしたのかを容易に追跡できるとともに、秘密鍵の漏洩に対する抑止力となる。
【０１０７】
なお、上述の例では、同一の公開鍵に対応する異なる複数の秘密鍵を生成し、各ユーザに異なる秘密鍵を配送する場合を説明したが、複数のサーバで秘密鍵による認証処理を実行する際に、同一の公開鍵に対応する異なる複数の秘密鍵を生成し、各サーバに異なる秘密鍵を配送する場合にも、本開示の第３の実施形態は同様に適用可能である。
【０１０８】
図１３は、本開示の第３の実施形態にかかる認証システムの概念を示す説明図である。図１３に示したのは、鍵生成者が異なる秘密鍵ｘ１，ｘ２を生成して、それぞれ異なるサーバに秘密鍵ｘ１，ｘ２を与える認証システムの概念である。このように、鍵生成者は、それぞれ異なるサーバに秘密鍵ｘ１，ｘ２を与え、どのサーバにどの秘密鍵を配送したかを管理しておく。そして、各サーバが証明者や署名者となり、検証者との間でそれぞれ認証処理や署名生成処理を実行すると、秘密鍵が漏れたことが発覚した場合にどのサーバから秘密鍵が漏洩したのかを容易に追跡できる。
【０１０９】
＜５．変形例＞
上述の説明では、ＭＱ関数を用いて１つの公開鍵に対して２つの秘密鍵を生成する場合を示したが、上述したように、ｍ本のｎ変数多次多項式で構成されるＭＱ関数のｎの値をｍのｃ倍（ｃは２以上の整数）とすることで、１つの公開鍵に対してｃ個の秘密鍵を生成することができる。
【０１１０】
そして、上述した第１の実施形態の変形例として、１つの公開鍵に対して生成したｃ個の秘密鍵をすべて認証処理デバイス１００ａに組み込み、認証処理の際に、ｃ個の秘密鍵の中から１つの秘密鍵をランダムに選択することで、電力解析攻撃による秘密鍵の漏洩を防ぐようにしても良い。
【０１１１】
また、上述した第２の実施形態の変形例として、３種類以上の秘密鍵に対してそれぞれ別の役割を与えるようにしても良い。上述した第２の実施形態では、臨時用の秘密鍵が使われた場合には、検証処理デバイス２００ｂからメール等で臨時用の秘密鍵が使われたことをユーザに通知していたが、例えば、１つの公開鍵に対して３つの秘密鍵を生成し、その中の２つの秘密鍵を臨時用の秘密鍵としてもよく、その臨時用の秘密鍵のそれぞれに対して別々の役割を与えるようにしても良い。
【０１１２】
また、上述した第３の実施形態の変形例として、１つの公開鍵に対して生成したｃ個の秘密鍵をそれぞれ別のユーザに与えることで、三者間以上で権利を共有すると共に、秘密鍵が漏れたことが発覚した場合にどのユーザが秘密鍵を漏らしたのかを容易に追跡できるようにしてもよい。
【０１１３】
上述した、ＭＱ関数を用いて生成された秘密鍵による認証処理の際には、１回の認証処理を上述した第１の実施形態の変形例として、１回の認証処理において、上述したｎパスの公開鍵認証方式による認証処理を複数回（複数ラウンド）繰り返すことで、偽証が成功する確率を充分に小さくすることができることが知られている。そして、１つの公開鍵に対して複数の秘密鍵を生成できる場合は、ラウンドごとに異なる秘密鍵を用いても認証処理が可能となる。従って、上述した第１の実施形態の変形例として、認証処理デバイス１００ａは、１回の認証処理の際に、ラウンドごとに秘密鍵をランダムに選択してもよい。
【０１１４】
図１４は、本開示の第１の実施形態の変形例にかかる、秘密鍵が格納された認証処理デバイス１００ａと、検証処理を実行する検証処理デバイス２００ａとの間の認証処理を示す流れ図である。図１４に示した流れ図は、本人であることを認証してもらいたいユーザが、公開鍵及びその公開鍵に対応する２つの秘密鍵を生成する場合の認証処理について示したものである。
【０１１５】
本人であることを認証してもらいたいユーザは、予め上述の鍵生成アルゴリズムＧｅｎによって秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成する（ステップＳ１１１）。ここで、公開鍵Ｆ（ｘ１）は、Ｆ（ｘ１）＝Ｆ（ｘ２）を満たすものである。この秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）の生成は、鍵生成アルゴリズムＧｅｎを実行することが可能な情報処理装置で行われる。
【０１１６】
ユーザは、秘密鍵ｘ１、ｘ２及び公開鍵Ｆ（ｘ１）を生成すると、秘密鍵ｘ１、ｘ２を秘密を保ったまま認証処理デバイス１００ａに登録し（ステップＳ１１２）、公開鍵Ｆ（ｘ１）を検証処理デバイス２００ａに登録する（ステップＳ１１３）。そしてユーザが認証処理デバイス１００ａに対して認証実行を指示すると（ステップＳ１１４）、認証処理デバイス１００ａは、まず（ｉ１，ｉ２，…，ｉＮ）∈｛１，２｝をランダムに選択する（ステップＳ１１５）。ここで、Ｎは１回の認証処理におけるラウンド数を示す。従って上記ステップＳ１１５は、認証処理デバイス１００ａが、使用する秘密鍵をｘ１、ｘ２の中からラウンドごとにランダムに選択する処理である。
【０１１７】
そして、認証処理デバイス１００ａと検証処理デバイス２００ａとの間で、上記ステップＳ１１５で選択されたｉに対応する秘密鍵ｘｉｊを用いた認証処理が実行される（ステップＳ１１６）。なお、ｊは１からＮまでの間の整数である。
【０１１８】
このように、認証処理デバイス１００ａが１回の認証処理においてラウンドごとに使用する秘密鍵をランダムに選択することで、電力解析攻撃による１ｂｉｔ  ＤＰＡが困難になるという効果が期待できる。
【０１１９】
上述の実施形態ではＭＱ関数を用いた秘密鍵の生成の場合を例示したが、ＭＱ関数を用いた電子署名の場合にも、同様に適用可能であることは言うまでもない。また、上述の実施形態では、１つの公開鍵に対して複数の秘密鍵を生成する際にＭＱ関数を用いていたが、このように、１つの公開鍵に対して複数の秘密鍵を生成することができるアルゴリズムであれば、本開示はＭＱ関数を用いるものに限られないことは言うまでもない。
【０１２０】
ここで、上述した各実施形態で実行される認証処理のアルゴリズムの一例を説明する。ここでは３パス方式のアルゴリズムについて説明する。３パス方式のアルゴリズムは、以下のような鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶにより構成される。
【０１２１】
鍵生成アルゴリズムＧｅｎは、環Ｋ上で定義されるｍ本の多変数多項式ｆ１（ｘ１，…，ｘｎ），…，ｆｍ（ｘ１，…，ｘｎ）、及びベクトルｓ＝（ｓ１，…，ｓｎ）∈Ｋｎを生成する。次に、鍵生成アルゴリズムＧｅｎは、ｙ＝（ｙ１，…，ｙｍ）←（ｆ１（ｓ），…，ｆｍ（ｓ））を計算する。そして、鍵生成アルゴリズムＧｅｎは、（ｆ１（ｘ１，…，ｘｎ），…，ｆｍ（ｘ１，…，ｘｎ），ｙ）を公開鍵ｐｋに設定し、ｓを秘密鍵に設定する。
【０１２２】
以下、図１５を参照しながら、対話プロトコルの中で証明者アルゴリズムＰが実行する処理及び検証者アルゴリズムＶが実行する処理について説明する。この対話プロトコルの中で、証明者は、秘密鍵ｓの情報を検証者に一切漏らさずに、「自身がｙ＝Ｆ（ｓ）を満たすｓを知っていること」を検証者に示す。一方、検証者は、証明者がｙ＝Ｆ（ｓ）を満たすｓを知っているか否かを検証する。なお、公開鍵ｐｋは、検証者に公開されているものとする。また、秘密鍵ｓは、証明者により秘密に管理されているものとする。以下、図１５に示したフローチャートに沿って説明を進める。
【０１２３】
工程＃１：
図１５に示すように、まず、証明者アルゴリズムＰは、ランダムにベクトルｒ０，ｔ０∈Ｋｎ及びｅ０∈Ｋｍを生成する。次いで、証明者アルゴリズムＰは、ｒ１←ｓ−ｒ０を計算する。この計算は、秘密鍵ｓをベクトルｒ０によりマスクする操作に相当する。さらに、証明者アルゴリズムＰは、ｔ１←ｒ０−ｔ０を計算する。次いで、証明者アルゴリズムＰは、ｅ１←Ｆ（ｒ０）−ｅ０を計算する。
【０１２４】
工程＃１（続き）：
次いで、証明者アルゴリズムＰは、ｃ０←Ｈ（ｒ１，Ｇ（ｔ０，ｒ１）＋ｅ０）を計算する。次いで、証明者アルゴリズムＰは、ｃ１←Ｈ（ｔ０，ｅ０）を計算する。次いで、証明者アルゴリズムＰは、ｃ２←Ｈ（ｔ１，ｅ１）を計算する。工程＃１で生成されたメッセージ（ｃ０，ｃ１，ｃ２）は、検証者アルゴリズムＶに送られる。
【０１２５】
工程＃２：
メッセージ（ｃ０，ｃ１，ｃ２）を受け取った検証者アルゴリズムＶは、３つの検証パターンのうち、どの検証パターンを利用するかを選択する。例えば、検証者アルゴリズムＶは、検証パターンの種類を表す３つの数値｛０，１，２｝の中から１つの数値を選択し、選択した数値を要求Ｃｈに設定する。この要求Ｃｈは証明者アルゴリズムＰに送られる。
【０１２６】
工程＃３：
要求Ｃｈを受け取った証明者アルゴリズムＰは、受け取った要求Ｃｈに応じて検証者アルゴリズムＶに送る返答Ｒｓｐを生成する。Ｃｈ＝０の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ０，ｔ１，ｅ１）を生成する。Ｃｈ＝１の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ１，ｔ０，ｅ０）を生成する。Ｃｈ＝２の場合、証明者アルゴリズムＰは、返答Ｒｓｐ＝（ｒ１，ｔ１，ｅ１）を生成する。工程＃３で生成された返答Ｒｓｐは、検証者アルゴリズムＶに送られる。
【０１２７】
工程＃４：
返答Ｒｓｐを受け取った検証者アルゴリズムＶは、受け取った返答Ｒｓｐを利用して以下の検証処理を実行する。
【０１２８】
Ｃｈ＝０の場合、検証者アルゴリズムＶは、ｃ１＝Ｈ（ｒ０−ｔ１，Ｆ（ｒ０）−ｅ１）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ２＝Ｈ（ｔ１，ｅ１）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１２９】
Ｃｈ＝１の場合、検証者アルゴリズムＶは、ｃ０＝Ｈ（ｒ１，Ｇ（ｔ０，ｒ１）＋ｅ０）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ１＝Ｈ（ｔ０，ｅ０）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１３０】
Ｃｈ＝２の場合、検証者アルゴリズムＶは、ｃ０＝Ｈ（ｒ１，ｙ−Ｆ（ｒ１）−Ｇ（ｔ１，ｒ１）−ｅ１）の等号が成り立つか否かを検証する。さらに、検証者アルゴリズムＶは、ｃ２＝Ｈ（ｔ１，ｅ１）の等号が成り立つか否かを検証する。検証者アルゴリズムＶは、これらの検証が全て成功した場合に認証成功を示す値１を出力し、検証に失敗があった場合に認証失敗を示す値０を出力する。
【０１３１】
以上、３パス方式に係る効率的なアルゴリズムの構成例について説明した。もちろん、本開示における認証処理の際のアルゴリズムは係る例に限定されるものではなく、ｍ本の多変数多項式から公開鍵及びその公開鍵に対応する複数の秘密鍵を生成する場合の他のアルゴリズムも同様に認証処理に用いることができることは言うまでもない。
【０１３２】
＜６．ハードウェア構成例＞
上記の各アルゴリズムは、例えば、図１６に示す情報処理装置のハードウェア構成を用いて実行することが可能である。つまり、当該各アルゴリズムの処理は、コンピュータプログラムを用いて図１６に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０１３３】
図１６に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０１３４】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０１３５】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。
【０１３６】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０１３７】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０１３８】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０１３９】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０１４０】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０１４１】
＜７．まとめ＞
以上説明したように本開示によれば、ＭＱ関数を用いた鍵生成アルゴリズムのように、同一の公開鍵に対して複数の秘密鍵が生成できる公開鍵認証方式を用いることで、鍵漏洩の検知手法や、鍵漏洩の防止手法や、鍵漏洩の抑止手法を実現する。
【０１４２】
本開示の第１の実施形態では、秘密鍵が記録されたＩＣカードのような認証処理デバイスに対する電力解析攻撃対策として、同一の公開鍵に対して生成された複数の秘密鍵が認証処理デバイスに記録される。認証処理の際に、認証処理デバイスは、複数の秘密鍵の中から１つの秘密鍵をランダムに選択する。認証処理デバイスが認証処理の際に複数の秘密鍵の中から１つの秘密鍵をランダムに選択することで、電力解析攻撃による秘密鍵の抽出を困難にすることができる。
【０１４３】
本開示の第２の実施形態では、秘密鍵を認証処理デバイスに入力するような場合に、通常使用時の秘密鍵ではない臨時用の秘密鍵が認証処理デバイスに入力されると、検証処理デバイスを通じて、臨時用の秘密鍵が使用されたことをユーザに通知する。臨時用の秘密鍵が使用されたことが通知されることで、ユーザは、臨時用の秘密鍵が意図的に利用されたのか、また漏洩してしまったのかを判断することができる。
【０１４４】
本開示の第３の実施形態では、１つの公開鍵に対する複数の秘密鍵を、それぞれ異なるユーザに配送する。１つの公開鍵に対する複数の秘密鍵を、それぞれ異なるユーザに配送することで、仮にどれか１つの秘密鍵が漏洩してしまった場合に、誰がその秘密鍵を漏洩させたのかを容易に追跡することが出来るので、秘密鍵の漏洩に対する抑止力となり得る。
【０１４５】
なお、上述の各実施形態では、１つの公開鍵に対する複数の秘密鍵を生成できるものとして、ＭＱ関数を用いて生成された秘密鍵を例示して説明したが、本開示は係る例に限定されるものではない。１つの公開鍵に対する複数の秘密鍵を生成できるような公開鍵認証方式や電子署名方式であれば、上述した各実施形態へこれらの方式を同様に適用可能であることは言うまでもない。また、上記の各実施形態では、認証処理を実行する認証処理デバイスと、検証処理を実行する検証処理デバイスは別々の装置にそれぞれ設けられていても良いが、同一の装置に設けられていても良い。
【０１４６】
最後に、本技術の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、ＰＣ、携帯電話、ゲーム機、情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置に対して適用することができる。なお、以下で述べる情報処理装置の機能は、１台の情報処理装置を利用して実現することも可能であるし、複数台の情報処理装置を利用して実現することも可能である。また、以下で述べる情報処理装置が処理を実行する際に用いるデータ記憶手段及び演算処理手段は、当該情報処理装置に設けられたものであってもよいし、ネットワークを介して接続された機器に設けられたものであってもよい。
【０１４７】
なお、上記の鍵生成アルゴリズムＧｅｎ、証明者アルゴリズムＰ、検証者アルゴリズムＶ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒは、本開示の鍵選択部、処理実行部の一例である。
【０１４８】
以上、添付図面を参照しながら本開示の好適な実施形態について詳細に説明したが、本開示はかかる例に限定されない。本開示の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本開示の技術的範囲に属するものと了解される。
【０１４９】
なお、本技術は以下のような構成も取ることができる。
（１）
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択部と、
前記鍵選択部が選択した秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行部と、
を備える、情報処理装置。
（２）
前記鍵選択部は、前記検証者との間の認証処理または電子署名生成処理の際に前記複数の秘密鍵のいずれかをランダムに選択する、前記（１）に記載の情報処理装置。
（３）
前記鍵選択部は、前記処理実行部が前記検証者との間で前記認証処理を繰り返すことで１回の認証を完了させる、または前記処理実行部が前記電子署名生成処理を繰り返すことで１回の電子署名の生成を完了させる場合に、前記認証処理または前記電子署名生成処理ごとに前記複数の秘密鍵のいずれかをランダムに選択する、複数の秘密鍵のいずれかをランダムに選択する、前記（２）に記載の情報処理装置。
（４）
前記処理実行部は、前記複数の秘密鍵の内の第１の秘密鍵にハッシュ関数を適用して得られる第１のハッシュ値を前記検証者に登録する、前記（１）に記載の情報処理装置。
（５）
前記処理実行部は、前記公開鍵認証方式による検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理の際に使用した秘密鍵にハッシュ関数を適用し、前記第１のハッシュ値と比較される第２のハッシュ値を前記検証者に送信する、前記（４）に記載の情報処理装置。
（６）
前記検証者による前記公開鍵認証方式または前記電子署名方式を用いた検証処理の際に前記第１のハッシュ値と前記第２のハッシュ値とを比較し、比較の結果に応じて所定の通知処理を実行する比較処理部をさらに備える、前記（５）に記載の情報処理装置。
（７）
前記複数の秘密鍵の各々が異なる装置に登録され、
前記鍵選択部は、該登録された秘密鍵を選択する、前記（１）に記載の情報処理装置。
（８）
前記公開鍵認証方式または電子署名方式は、ｓ∈Ｋｎを秘密鍵に設定し、環Ｋ上の多次多項式ｆｉ（ｘ１，…，ｘｎ）（ｉ＝１〜ｍ）及びｙｉ＝ｆｉ（ｓ）を公開鍵に設定する公開鍵認証方式である、前記（１）に記載の情報処理装置。
（９）
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、
前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、
を備える、情報処理方法。
（１０）
コンピュータに、
検証者に登録される１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式における、前記複数の秘密鍵のいずれか１つを選択する鍵選択ステップと、
前記鍵選択ステップで選択された秘密鍵を用いて、前記公開鍵認証方式による前記検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理を実行する処理実行ステップと、
を実行させる、コンピュータプログラム。
（１１）
１つの公開鍵に対してそれぞれ異なる複数の秘密鍵が存在する公開鍵認証方式または電子署名方式において、証明者が前記複数の秘密鍵の内の第１の秘密鍵にハッシュ関数を適用して得られる第１のハッシュ値及び前記証明者が検証者との間の認証処理または前記電子署名方式による前記検証者への電子署名生成処理の際に使用した秘密鍵にハッシュ関数を適用して得られる第２のハッシュ値を取得し、前記公開鍵認証方式または前記電子署名方式を用いた検証処理の際に前記第１のハッシュ値と前記第２のハッシュ値とを比較し、比較の結果に応じて前記証明者への所定の通知処理を実行する比較処理部を備える、情報処理装置。
【符号の説明】
【０１５０】
Ｇｅｎ    鍵生成アルゴリズム
Ｐ        証明者アルゴリズム
Ｖ        検証者アルゴリズム
Ｓｉｇ    署名生成アルゴリズム
Ｖｅｒ    署名検証アルゴリズム
【図１】
2014052588.tif 000012
【図２】
2014052588.tif 000013
【図３】
2014052588.tif 000014
【図４】
2014052588.tif 000015
【図５】
2014052588.tif 000016
【図６Ａ】
2014052588.tif 000017
【図６Ｂ】
2014052588.tif 000018
【図７】
2014052588.tif 000019
【図８】
2014052588.tif 000020
【図９】
2014052588.tif 000021
【図１０】
2014052588.tif 000022
【図１１】
2014052588.tif 000023
【図１２】
2014052588.tif 000024
【図１３】
2014052588.tif 000025
【図１４】
2014052588.tif 000026
【図１５】
2014052588.tif 000027
【図１６】
2014052588.tif 000028