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