(57)【特許請求の範囲】
【請求項１】
文字列を入力するクライアントと接続可能であり、前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバであって、
前記文字列中の各文字の位置を表すインデックス、文字および状態の組み合わせ毎に、当該状態に対応する鍵により当該状態から当該文字に応じて遷移する後状態に対応する次のインデックスの鍵を暗号化した鍵チェーンを生成する鍵チェーン生成部と、
前記クライアントと通信して、入力された文字が前記クライアントから秘匿された状態で、各インデックスについて前記鍵チェーンの集合のうち入力した各文字に対応する前記鍵チェーンを前記クライアントに提供する提供部と、
を有するサーバ。
【請求項２】
前記クライアントは、
前記提供部と通信して、各インデックスについて入力した文字に対応する複数の前記鍵チェーンを前記サーバから受け取る受取部と、
インデックスの順に、直前のインデックスに対応する復号処理において復号した鍵を用いて、受け取った前記複数の鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく復号部と
を有する
請求項１に記載のサーバ。
【請求項３】
前記提供部は、
入力した前記文字列の各文字についての、インデックス及び入力した文字の組を表すインデックス付き文字の集合を暗号化した送信暗号文を前記クライアントから受信し、
前記鍵チェーンの集合に含まれるそれぞれの鍵チェーンについて、前記送信暗号文に基づいて、対応するインデックス及び対応する文字の組を表すインデックス付き状態遷移値が前記インデックス付き文字の集合に含まれる場合には当該鍵チェーンとなり、前記インデックス付き状態遷移値が前記インデックス付き文字の集合に含まれない場合には当該鍵チェーンとならない値を暗号化した応答暗号文を生成して、前記クライアントに送信する  請求項２に記載のサーバ。
【請求項４】
前記受取部は、前記応答暗号文のそれぞれを復号処理して、複数の前記鍵チェーンを取得し、
前記復号部は、インデックスの順に、直前のインデックスに対応する復号処理おいて復号した鍵により前記複数の鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく
請求項３に記載のサーバ。
【請求項５】
前記提供部は、
前記インデックス付き文字が代入されると０となり、前記インデックス付き文字以外の値が代入されると非０となる多項式の各係数を、準同型性を有する暗号化方式により暗号化した前記送信暗号文を前記クライアントから受信し、
前記鍵チェーンの集合に含まれるそれぞれの鍵チェーンについて、前記インデックス付き状態遷移値を前記多項式に代入した値に乱数を乗じた値と当該鍵チェーンの値とを加算した合計値を、前記暗号化方式により暗号化した前記応答暗号文を生成して、前記クライアントに送信する
請求項４に記載のサーバ。
【請求項６】
前記提供部は、前記クライアントと通信して、インデックス毎の前記鍵チェーンの集合のうちから前記クライアントが入力した文字に対応する部分集合を、紛失通信により選択的に前記クライアントへと送信する請求項２に記載のサーバ。
【請求項７】
前記受取部は、前記提供部と通信して、前記インデックス毎に、入力した文字に対応する前記鍵チェーンの部分集合を、紛失通信により選択的に前記サーバから受け取り、
前記復号部は、インデックスの順に、直前のインデックスに対応する復号処理おいて復号した鍵を用いて、当該インデックスに対応して受け取った前記鍵チェーンの部分集合に含まれる各鍵チェーンに対して復号処理をして、次のインデックスに対応する鍵を復号していく
請求項６に記載のサーバ。
【請求項８】
前記提供部は、
インデックス毎に、前記鍵チェーンの集合における各文字に対応する複数の部分集合のそれぞれを、各文字に対応する暗号鍵により暗号化して予め前記クライアントに提供し、  インデックス毎に、前記クライアントと通信して、当該インデックスについて文字毎の暗号鍵の中から前記クライアントが入力した文字に対応する暗号鍵を、入力した文字が前記クライアントから秘匿された状態で前記クライアントに提供する
請求項７に記載のサーバ。
【請求項９】
前記クライアントは、予め受け取ったインデックス毎の前記複数の部分集合のうち、前記サーバから送信された、前記クライアントが入力した文字に対応する暗号鍵を用いて当該文字に対応する部分集合を復号する
請求項８に記載のサーバ。
【請求項１０】
前記提供部は、前記インデックス毎に、複数の前記鍵チェーンを並べ替えて送信する
請求項６に記載のサーバ。
【請求項１１】
前記鍵チェーン生成部は、
文字列の最後の文字に対応するインデックスにおいて、当該状態に対応する鍵により最後の遷移先の状態に対応する鍵を暗号化した鍵チェーンを生成し、
前記最後の遷移先の状態に対応する鍵により当該最後の遷移先の状態が、前記オートマトンにより定められた最終状態であるか否かを示す値を暗号化した最終状態情報を生成する
請求項１に記載のサーバ。
【請求項１２】
前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバに接続可能であり、文字列を入力するクライアントであって、
前記サーバと通信して、各インデックスについて入力した文字に対応する複数の鍵チェーンを前記サーバから受け取る受取部と、
インデックスの順に、直前のインデックスに対応する復号処理において復号した鍵を用いて、受け取った前記複数の鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく復号部と
を有するクライアント。
【請求項１３】
文字列を入力するクライアントと接続可能であり、前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバにおける情報処理の方法であって、
前記文字列中の各文字の位置を表すインデックス、文字および状態の組み合わせ毎に、当該状態に対応する鍵により当該状態から当該文字に応じて遷移する後状態に対応する次のインデックスの鍵を暗号化した鍵チェーンを生成し、
前記クライアントと通信して、入力された文字が前記クライアントから秘匿された状態で、各インデックスについて前記鍵チェーンの集合のうち入力した各文字に対応する前記鍵チェーンを前記クライアントに提供する
方法。
【請求項１４】
前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバに接続可能であり、文字列を入力するクライアントにおける情報処理の方法であって、
前記サーバと通信して、各インデックスについて入力した文字に対応する複数の鍵チェーンを前記サーバから受け取り、
インデックスの順に、直前のインデックスに対応する復号処理において復号した鍵を用いて、受け取った前記複数の鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく
方法。
【請求項１５】
コンピュータを請求項１に記載のサーバとして機能させるためのプログラム。
【請求項１６】
コンピュータを請求項１２に記載のクライアントとして機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列がオートマトンに受理されるか否かを認証するためのサーバ、クライアント、方法及びプログラムに関する。
【背景技術】
【０００２】
クライアントが保有する文字列が、サーバが保有するオートマトンに受理されるか否かを認証するシステムが知られている（例えば、特許文献１参照。）。
［先行技術文献］
［特許文献］
特許文献１  特開２００９−１５１７５７号公報
［非特許文献］
非特許文献１  Michael J. Freedman, Kobbi Nissim and Benny Pinkas、 "Efficient Private Matching and Set Intersection"、 Advances in Cryptology EUROCRYPT 2004、Lecture Notes in Computer Science、２００４年
非特許文献２  Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ところで、クライアントが保有する文字列をサーバに開示せず、且つ、サーバが保有するオートマトンをクライアントに開示せずに、文字列がオートマトンに受理されるか否かを認証することは非常に難しかった。
【課題を解決するための手段】
【０００４】
本発明の第１の態様においては、文字列を入力するクライアントと接続可能であり、前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバであって、前記文字列中の各文字の位置を表すインデックス、文字および状態の組み合わせ毎に、当該状態に対応する鍵により当該状態から当該文字に応じて遷移する後状態に対応する次のインデックスの鍵を暗号化した鍵チェーンを生成する鍵チェーン生成部と、前記クライアントと通信して、入力された文字が前記クライアントから秘匿された状態で、各インデックスについて前記鍵チェーンの集合のうち入力した各文字に対応する前記鍵チェーンを前記クライアントに提供する提供部と、を有するサーバ、並びに、このようなサーバにより実行される情報処理の方法およびプログラムを提供する。
本発明の第２の態様においては、前状態毎かつ文字毎に遷移させるべき後状態を定義したオートマトンを有するサーバに接続可能であり、文字列を入力するクライアントであって、前記サーバと通信して、各インデックスについて入力した文字に対応する複数の鍵チェーンを前記サーバから受け取る受取部と、インデックスの順に、直前のインデックスに対応する復号処理において復号した鍵を用いて、受け取った前記複数の鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく復号部とを有するクライアント、並びに、このようなクライアントにより実行される情報処理の方法およびプログラムを提供する。【０００５】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【０００６】
【図１】図１は、本実施形態に係る認証システム１０の構成を示す。
【図２】図２は、本実施形態に係るサーバ２０およびクライアント３０のそれぞれの機能ブロック構成を示す。
【図３】図３は、本実施形態に係るサーバ２０およびクライアント３０の処理のフローチャートを示す。
【図４】図４は、鍵チェーンの集合の生成処理のフローチャートを示す。
【図５】図５は、インデックス毎に発生される各状態の鍵の一例を示す。
【図６】図６は、オートマトンの遷移表の一例、および、１番目のインデックス、２番目のインデックスおよび３番目のインデックスにおける、各状態および各文字に対応する後状態の次のインデックスの鍵を割り当てた鍵表の一例を示す。
【図７】図７は、インデックス、文字および状態の組み合わせ毎に生成された鍵チェーンの集合の一例を示す。
【図８】図８は、最終状態情報の一例を示す。
【図９】図９は、"０"または"１"の２値の文字を入力する場合の、１番目のインデックスから３番目のインデックスまでのインデックス付き状態遷移値の一例を示す。
【図１０】図１０は、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合の一例を示す。
【図１１】図１１は、本実施形態に係る認証システム１０における、秘匿共通集合計算プロトコルによる通信処理の一例を示す。
【図１２】図１２は、本実施形態におけるクライアント３０により受信された複数の応答暗号文、および、複数の応答暗号文から復号された複数の鍵チェーンの一例を示す。
【図１３】図１３は、クライアント３０における、複数の鍵チェーンの順次の復号処理のフローチャートを示す。
【図１４】図１４は、クライアント３０による数の鍵チェーンの順次の復号処理において復号される鍵の一例を示す。
【図１５】図１５は、変形例に係る認証システム１０の構成を示す。
【図１６】図１６は、変形例に係るサーバ２０およびクライアント３０の処理のフローチャートを示す。
【図１７】図１７は、１番目のインデックスの鍵チェーンの集合の一例を示す。
【図１８】図１８は、２番目のインデックスの鍵チェーンの集合の一例を示す。
【図１９】図１９は、３番目のインデックスの鍵チェーンの集合の一例を示す。
【図２０】図２０は、インデックス毎の鍵チェーンの部分集合から順次に復号される鍵の一例を示す。
【図２１】図２１は、本変形例に係るサーバ２０とクライアント３０との間における鍵チェーンの部分集合の紛失通信による受け渡し処理のフローを示す。
【図２２】図２２は、図２１に続くフローを示す。
【図２３】図２３は、図２２に続くフローを示す。
【図２４】図２４は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【発明を実施するための形態】
【０００７】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００８】
図１は、本実施形態に係る認証システム１０の構成を示す。本実施形態に係る認証システム１０は、サーバ２０と、クライアント３０とを備える。サーバ２０とクライアント３０とは互いにネットワークを介して接続される。本実施形態に係る認証システム１０は、クライアント３０に入力された文字列によって、サーバ２０が保有するオートマトンが正しい最終状態に遷移するかを判定する。
【０００９】
クライアント３０は、外部から文字列を入力する。文字列に含まれる文字は、どのような文字であってもよい。例えば文字は、"０"、"１"の２値の文字であってもよいし、１バイトで表現される文字であってもよい。
【００１０】
サーバ２０は、受け取った文字に応じて状態が遷移するオートマトンを有する。オートマトンは、前状態毎かつ文字毎に遷移させるべき後状態を定義している。オートマトンが受け取る文字は、クライアント３０に入力される文字である。オートマトンは、予め登録された文字列の集合（文字列群）の正規表現を表す。オートマトンは、文字列に含まれる各文字を先頭から順次に受け取り、先頭の文字から１文字ずつ順次に状態を遷移させる。そして、オートマトンは、最後の文字を受け取って遷移した後に、正しい最終状態に遷移していれば"受理"を出力し、正しい最終状態に遷移していなければ"不受理"を出力する。
【００１１】
そして、このようなサーバ２０およびクライアント３０は、クライアント３０が入力した文字列をサーバ２０に対して秘匿し且つサーバ２０が保有するオートマトンをクライアント３０に対して秘匿して、クライアント３０に入力された文字列によってサーバ２０が保有するオートマトンが正しい最終状態に遷移するかを判定する。
【００１２】
図２は、本実施形態に係るサーバ２０およびクライアント３０のそれぞれの機能ブロック構成を示す。サーバ２０は、オートマトン記憶部４２と、鍵発生部４４と、鍵チェーン生成部４６と、インデックス付き状態遷移値生成部４８と、合成部５０と、提供部５２とを有する。また、クライアント３０は、入力部６０と、インデックス付き文字生成部６２と、受取部６４と、復号部６６とを有する。
【００１３】
クライアント３０の入力部６０は、文字列に含まれる各文字を１つずつ入力する。入力部６０は、入力した各文字をインデックス付き文字生成部６２に受け渡す。
【００１４】
インデックス付き文字生成部６２は、文字列に含まれる各文字について、インデックス付き文字を生成する。ここで、インデックスとは、文字列中における文字の位置、即ち、当該文字がオートマトンへと与えられる文字の順序を表す。
【００１５】
また、インデックス付き文字とは、当該文字とインデックスとの組を表す値であり、例えば文字を表す値およびインデックスを表す値を一方向性関数に代入して得られた値である。インデックス付き文字は、その値からは、文字およびインデックスを検出するのが困難なように秘匿化または暗号化された値であってもよい。インデックス付き文字生成部６２は、文字列に含まれる各文字について生成したインデックス付き文字のそれぞれを、受取部６４に受け渡す。
【００１６】
サーバ２０のオートマトン記憶部４２は、クライアント３０に入力された文字列を受理するか否かを判定するためのオートマトンを記憶する。オートマトン記憶部４２は、一例として、状態の遷移を表す遷移表、入力可能な文字群、状態群、初期状態および最終状態を含む。
【００１７】
ここで、オートマトンは、文字列に含まれる各文字を先頭から１文字ずつ与えられることに応じて、即ち、インデックス毎に、遷移表に従って状態が遷移する。また、１つの文字が与えられたことに対応してオートマトンが前状態から後状態へと遷移することを状態遷移と呼び、状態遷移における前状態、文字および後状態の組合せを状態遷移関係と呼ぶ。
【００１８】
サーバ２０の鍵発生部４４は、オートマトンに含まれる複数の状態のそれぞれに対応した鍵を、インデックス毎に発生する。さらに、鍵発生部４４は、最後の遷移先となる各状態（オートマトンが文字列の最後の文字まで受け取った結果遷移する最後の状態）に対応する鍵も発生する。鍵発生部４４により発生される鍵の一例については、図５等を参照して更に説明する。
【００１９】
サーバ２０の鍵チェーン生成部４６は、インデックス、文字および状態の組み合わせ毎に、当該状態に対応する鍵により当該状態から当該文字に応じて遷移する後状態に対応する次のインデックスの鍵を暗号化した鍵チェーンを生成する。なお、鍵チェーン生成部４６は、文字列の最後の文字に対応するインデックスにおいては、当該状態に対応する鍵により、当該状態から当該文字に応じて遷移する最後の遷移先の状態に対応する鍵を暗号化した鍵チェーンを生成する。なお、これらの鍵のそれぞれは、鍵発生部４４により発生される。
【００２０】
また、さらに、鍵チェーン生成部４６は、最後の遷移先の状態に対応する鍵により、当該最後の遷移先の状態が、オートマトンにより定められた最終状態であるか否かを示す値を暗号化した最終状態情報を生成する。なお、鍵チェーンの集合および最終状態情報の一例については、詳細を、図４、図７及び図８等を参照して更に説明する。
【００２１】
サーバ２０のインデックス付き状態遷移値生成部４８は、状態遷移関係毎に、インデックス付き状態遷移値を生成する。ここで、インデックス付き状態遷移値とは、オートマトンにおいて、各状態遷移が受け入れ可能な文字およびインデックスの組を表す値であり、例えば、文字を表す値およびインデックスを表す値を一方向性関数に代入して得られた値である。この場合において、一方向性関数は、インデックス文字を生成するために用いられる一方向性関数と同一である。また、インデックス付き状態遷移値は、その値からは、文字およびインデックスを検出するのが困難なように秘匿化または暗号化された値であってもよい。なお、インデックス付き状態遷移値の一例については、図９等を参照して更に説明する。
【００２２】
サーバ２０の合成部５０は、インデックス毎に、鍵チェーン生成部４６により生成された鍵チェーンの集合に含まれる各鍵チェーンのそれぞれに、インデックス付き状態遷移値生成部４８により生成されたインデックス付き状態遷移値を対応付ける。そして、合成部５０は、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合を生成する。なお、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合の一例については、図１０等を参照して更に説明する。
【００２３】
サーバ２０の提供部５２は、クライアント３０の受取部６４と通信する。また、クライアント３０の受取部６４は、サーバ２０の提供部５２と通信する。
【００２４】
より詳しくは、サーバ２０の提供部５２は、クライアント３０の受取部６４と通信して、入力された文字が秘匿された状態で、各インデックスについて、鍵チェーンの集合のうち入力した各文字列に対応する鍵チェーンをクライアント３０に提供する。即ち、提供部５２は、各インデックスについて、入力部６０が入力していない文字列に対応する鍵チェーンを受取部６４に提供せずに、入力部６０が入力した文字列に対応する鍵チェーンのみを受取部６４に提供する。
【００２５】
また、クライアント３０の受取部６４は、サーバ２０の提供部５２と通信して、オートマトンが秘匿された状態で、各インデックスについて、入力した文字列に対応する鍵チェーンをサーバ２０から受け取る。即ち、受取部６４は、各インデックスについて、入力部６０が入力していない文字列に対応する鍵チェーンを提供部５２から受け取らず、入力部６０が入力した文字列に対応する鍵チェーンのみを提供部５２から受け取る。
【００２６】
ここで、提供部５２および受取部６４は、互いの集合の要素を秘匿しつつ互いの集合間に共通の要素を含むかを検出する秘匿共通集合計算プロトコルを用いて、入力した文字列に対応する鍵チェーンの受け渡しを行う。これにより、提供部５２は、オートマトンをクライアント３０に対して秘匿化した状態で、入力した文字列に対応する鍵チェーンを受取部６４に提供することができる。また、受取部６４は、入力した文字列をサーバ２０に対して秘匿化した状態で、入力した文字に対応する鍵チェーンを提供部５２から受け取ることができる。
【００２７】
なお、秘匿共通集合計算プロトコルについては、例えば、上述の非特許文献１に記載がある。また、秘匿共通集合計算プロトコルの処理の一例については、図１１等を参照して更に説明する。
【００２８】
さらに、サーバ２０の提供部５２は、初期状態に対応する鍵（即ち、初期状態に対応する１番目のインデックスの鍵）、および、鍵チェーン生成部４６により生成された最終状態情報をクライアント３０の受取部６４に提供する。また、クライアント３０の受取部６４は、初期状態に対応する鍵、および、最終状態情報をサーバ２０の提供部５２から受け取る。
【００２９】
復号部６６は、インデックスの順に、直前のインデックスに対応する復号処理において復号した鍵を用いて、受取部６４が受け取った全ての鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく。なお、復号部６６は、１番目のインデックスの復号処理においては、別個にサーバ２０から取得した初期状態の鍵を用いて復号処理をする。さらに、復号部６６は、文字列の最後の文字に対応する最後のインデックスに対応する復号処理において、最後の遷移先の状態に対応する鍵を復号することができる。
【００３０】
さらに、復号部６６は、最後の遷移先の状態に対応する鍵を復号した後、復号した当該鍵により最終状態情報を復号する。復号部６６は、最終状態情報を復号した結果、最終状態を表す値を取得できた場合に正しい最終状態に遷移したと判断する。そして、復号部６６は、最終状態を表す値を取得できた場合には、文字列がオートマトンに受理されたことを示す情報を出力し、最終状態を表す値を取得できずに終了した場合には文字列がオートマトンに受理されなかったことを示す情報を出力する。
【００３１】
図３は、本実施形態に係るサーバ２０およびクライアント３０の処理のフローチャートを示す。
【００３２】
まず、ステップＳ１１において、クライアント３０は、文字列を入力する。クライアント３０は、予め定められた文字数の文字列を入力してもよいし、可変長の文字列を入力してもよい。可変長の文字列を入力する場合には、クライアント３０は、入力された文字数（即ち、インデックス数）をサーバ２０に通知する。
【００３３】
続いて、ステップＳ１２において、クライアント３０は、入力した文字列の各文字についての、インデックス及び入力した文字の組を表すインデックス付き文字を生成する。インデックス付き文字は、一例として、インデックスを表す値および入力した文字を表す値を一方向性関数に代入して得られた値である。一方向性関数の内容は、例えばサーバ２０およびクライアント３０との間で予め定められている。
【００３４】
例えば、クライアント３０は、下記数１に示されるように、Ｎ個（Ｎは２以上の整数）の文字を含む文字列を入力したとする。
【００３５】
【数１】
0005593458.tif 000002
【００３６】
この場合、クライアント３０は、下記の数２に示されるように、一例として、文字列に含まれる各文字について、当該文字のインデックス（即ち、文字列中における当該文字の先頭からの順序）および当該文字を表す値を一方向性関数ｇ（）に代入する。これにより、クライアント３０は、インデックス及び入力した文字の組を表す値（インデックス付き文字）を算出することができる。
【００３７】
【数２】
0005593458.tif 000003
【００３８】
クライアント３０は、このような演算を文字列に含まれる全ての文字について行って、下記数３に示されるような、インデックス付き文字の集合を生成する。そして、クライアント３０は、このようなインデックス付き文字の集合をメモリ等に記憶する。
【００３９】
【数３】
0005593458.tif 000004
【００４０】
一方、ステップＳ１３において、サーバ２０は、インデックス毎、文字毎および状態毎に、当該状態に対応する鍵により、当該状態から当該文字に応じて遷移する後状態に対応する次のインデックスの鍵を暗号化した鍵チェーンを生成する。また、サーバ２０は、文字列の最後の文字に対応するインデックスにおいては、当該状態に対応する鍵により、当該状態から当該文字に応じて遷移する最後の遷移先の状態に対応する鍵を暗号化した鍵チェーンを生成する。なお、鍵チェーンの生成処理については、詳細を図４のフローチャートを参照して説明する。
【００４１】
続いて、ステップＳ１４において、サーバ２０は、状態遷移関係毎に、インデックス付き状態遷移値を生成する。インデックス付き状態遷移値は、一例として、下記の数４に示されるように、インデックスを表す値および文字を表す値を一方向性関数に代入して得られた値である。これにより、サーバ２０は、インデックス及び文字の組を表す値（インデックス付き状態遷移値）を算出することができる。なお、インデックス付き状態遷移値を生成するための一方向性関数は、クライアント３０がインデックス付き文字を生成するために用いた一方向性関数と同一である。
【００４２】
【数４】
0005593458.tif 000005
【００４３】
このステップＳ１４において、サーバ２０は、下記数５に示されるように、各インデックスについて、オートマトンが入力可能な文字毎のインデックス付き状態遷移値を生成する。なお、下記の数５において、σは、オートマトンが入力可能な文字の数を表す。
【００４４】
【数５】
0005593458.tif 000006
【００４５】
続いて、ステップＳ１５において、サーバ２０は、生成した複数の鍵チェーンのそれぞれに、対応するインデックス付き状態遷移値を対応付ける。そして、サーバ２０は、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合を生成する。なお、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合の一例については、図１０等を参照して更に説明する。
【００４６】
続いて、ステップＳ１６において、サーバ２０およびクライアント３０は、秘匿共通集合計算プロトコルを用いて、入力した文字に対応する鍵チェーンの受け渡しを行う。
【００４７】
より具体的には、クライアント３０は、入力した文字列の各文字についてのインデックス付き文字の集合を暗号化した送信暗号文を、サーバ２０に送信する。続いて、サーバ２０は、送信暗号文に基づいて、鍵チェーンの集合に含まれるそれぞれの鍵チェーンについて、対応するインデックス付き状態遷移値がインデックス付き文字の集合に含まれる場合には当該鍵チェーンとなり、インデックス付き状態遷移値がインデックス付き文字の集合に含まれない場合には当該鍵チェーンとならない値を暗号化した応答暗号文を生成して、クライアント３０に送信する。
【００４８】
そして、クライアント３０は、サーバ２０から応答暗号文を受信して、受信した応答暗号文を復号する。これによりクライアント３０は、各インデックスについて、入力した文字に対応する鍵チェーンを受け取ることができる。
【００４９】
このような処理をすることにより、サーバ２０は、オートマトンをクライアント３０に対して秘匿化した状態で、入力した文字に対応する鍵チェーンをクライアント３０に提供することができる。また、クライアント３０は、入力した文字列をサーバ２０に対して秘匿化した状態で、入力した文字に対応する鍵チェーンをサーバ２０から受け取ることができる。なお、秘匿共通集合計算プロトコルの処理の一例については、図１１のフローチャート等を参照して更に説明する。
【００５０】
続いて、ステップＳ１７において、サーバ２０は、初期状態に対応する鍵（即ち、初期状態に対応する１番目のインデックスの鍵）および最終状態情報をクライアント３０へと送信する。
【００５１】
続いて、ステップＳ１８において、クライアント３０は、インデックスの順に、直前のインデックスに対応する復号処理おいて復号した鍵を用いて、サーバ２０から受け取った全ての鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を順次に復号していく。この場合において、クライアント３０は、１番目のインデックスに対応する処理おいては、サーバ２０から別個に受け取った初期状態の鍵を用いて復号処理をする。さらに、クライアント３０は、文字列の最後の文字に対応する最後のインデックスに対応する処理おいて、受取部６４が受け取った全ての鍵チェーンのそれぞれに対して復号処理をすることにより、最後の遷移先の状態に対応する鍵を復号することができる。
【００５２】
そして、クライアント３０は、最後の遷移先の状態に対応する鍵を復号した後、復号した当該鍵により最終状態情報を復号する。クライアント３０は、最終状態情報を復号した結果、最終状態を表す値を取得できた場合に正しい最終状態に遷移したと判断する。クライアント３０は、最終状態を表す値を取得できた場合には、文字列がオートマトンに受理されたことを示す情報を出力し、最終状態を表す値を取得できずに終了した場合には文字列がオートマトンに受理されなかったことを示す情報を出力する。
【００５３】
以上の処理により、サーバ２０およびクライアント３０は、クライアント３０が入力した文字列をサーバ２０に対して秘匿し且つサーバ２０が保有するオートマトンをクライアント３０に対して秘匿して、クライアント３０に入力された文字列によってサーバ２０が保有するオートマトンが正しい最終状態に遷移するかを判定することができる。
【００５４】
図４は、鍵チェーンの集合の生成処理のフローチャートを示す。図５は、インデックス毎に発生される各状態の鍵の一例を示す。図６は、オートマトンの遷移表の一例、および、１番目のインデックス、２番目のインデックスおよび３番目のインデックスにおける、各状態および各文字に対応する後状態の次のインデックスの鍵を割り当てた鍵表の一例を示す。
【００５５】
サーバ２０は、図３のステップＳ１３の鍵チェーンの集合の生成処理として、以下のステップＳ３１からステップＳ４２の処理を実行する。
【００５６】
まず、ステップＳ３１において、サーバ２０は、オートマトンに含まれる複数の状態のそれぞれに対応した鍵を、インデックス毎に発生する。さらに、サーバ２０は、最後の遷移先となる各状態に対応する鍵も発生する。
【００５７】
この場合において、サーバ２０は、それぞれが異なる値となる乱数を鍵として発生する。例えば、オートマトンが３つの状態（状態ａ、状態ｂ、状態ｃ）を有し、文字列に３つの文字が含まれる場合、サーバ２０は、図５に示されるような鍵を発生する。
【００５８】
即ち、図５に示されるように、サーバ２０は、１番目のインデックスに対応して、状態ａに対応した鍵としてｒａ０を発生し、状態ｂに対応した鍵としてｒｂ０を発生し、状態ｃに対応した鍵としてｒｃ０を発生する。また、サーバ２０は、２番目のインデックスにおいて、状態ａに対応した鍵としてｒａ１を発生し、状態ｂに対応した鍵としてｒｂ１を発生し、状態ｃに対応した鍵としてｒｃ１を発生する。また、サーバ２０は、３番目のインデックスにおいて、状態ａに対応した鍵としてｒａ２を発生し、状態ｂに対応した鍵としてｒｂ２を発生し、状態ｃに対応した鍵としてｒｃ２を発生する。さらに、サーバ２０は、最後の遷移先に対応して、状態ａに対応した鍵としてｒａ３を発生し、状態ｂに対応した鍵としてｒｂ３を発生し、状態ｃに対応した鍵としてｒｃ３を発生する。
【００５９】
続いて、ステップＳ３２からステップＳ４１のループ処理において、サーバ２０は、インデックス毎に、ステップＳ３３からステップＳ４０の処理を繰り返す。また、ステップＳ３３からステップＳ４０のループ処理において、サーバ２０は、文字毎に、ステップＳ３４からステップＳ３９の処理を繰り返す。また、ステップＳ３４からステップＳ３９のループ処理において、サーバ２０は、状態毎に、ステップＳ３５からステップＳ３８の処理を繰り返す。
【００６０】
即ち、サーバ２０は、インデックス毎、文字毎および状態毎に、ステップＳ３５〜ステップＳ３８の処理を繰り返して実行する。
【００６１】
ステップＳ３５において、サーバ２０は、ステップＳ３１で発生された鍵の中から、処理対象となっている当該インデックスおよび当該状態に対応する鍵を読み出す。
【００６２】
続いて、ステップＳ３６において、サーバ２０は、オートマトンの遷移表を読み出して、処理対象となっている当該状態において処理対象となっている当該文字が入力されたことに応じて遷移する後状態を特定する。
【００６３】
例えば、図６の遷移表の例においては、状態ａにおいて文字"０"が入力された場合には後状態は"ａ"となり、状態ａにおいて文字"１"が入力された場合には後状態は"ｂ"となる。また、状態ｂにおいて文字"０"が入力された場合には後状態は"ａ"となり、状態ｂにおいて文字"１"が入力された場合には後状態は"ｃ"となる。また、状態ｃにおいて文字"０"が入力された場合には後状態は"ｃ"となり、状態ｃにおいて文字"１"が入力された場合には後状態は"ｃ"となる。
【００６４】
続いて、ステップＳ３７において、サーバ２０は、ステップＳ３１で発生された鍵の中から、処理対象となっているインデックスの次のインデックスにおける、ステップＳ３６で特定した後状態に対応する鍵を読み出す。
【００６５】
例えば、サーバ２０は、１番目のインデックスに対しては、図６の（Ａ）の鍵表に示されるような鍵を読み出す。即ち、サーバ２０は、状態ａにおいて文字"０"が入力された場合には鍵"ｒａ１"、状態ａにおいて文字"１"が入力された場合には鍵"ｒｂ１"、状態ｂにおいて文字"０"が入力された場合には鍵"ｒａ１"、状態ｂにおいて文字"１"が入力された場合には鍵"ｒｃ１"、状態ｃにおいて文字"０"が入力された場合には鍵"ｒｃ１"、状態ｃにおいて文字"１"が入力された場合には鍵"ｒｃ１"を読み出す。
【００６６】
また、例えば、サーバ２０は、２番目のインデックスに対しては、図６の（Ｂ）の鍵表に示されるような鍵を読み出す。即ち、サーバ２０は、状態ａにおいて文字"０"が入力された場合には鍵"ｒａ２"、状態ａにおいて文字"１"が入力された場合には鍵"ｒｂ２"、状態ｂにおいて文字"０"が入力された場合には鍵"ｒａ２"、状態ｂにおいて文字"１"が入力された場合には鍵"ｒｃ２"、状態ｃにおいて文字"０"が入力された場合には鍵"ｒｃ２"、状態ｃにおいて文字"１"が入力された場合には鍵"ｒｃ２"を読み出す。
【００６７】
また、例えば、サーバ２０は、３番目のインデックスに対しては、図６の（Ｃ）の鍵表に示されるような鍵を読み出す。即ち、サーバ２０は、状態ｃにおいて文字"０"が入力された場合には鍵"ｒａ３"、状態ａにおいて文字"１"が入力された場合には鍵"ｒｂ３"、状態ｂにおいて文字"０"が入力された場合には鍵"ｒａ３"、状態ｂにおいて文字"１"が入力された場合には鍵"ｒｃ３"、状態ｃにおいて文字"０"が入力された場合には鍵"ｒｃ３"、状態ｃにおいて文字"１"が入力された場合には鍵"ｒｃ３"を読み出す。
【００６８】
続いて、ステップＳ３８において、サーバ２０は、ステップＳ３７で読み出した後状態に対応する次のインデックスの鍵を、ステップＳ３５で読み出した当該状態に対応する当該インデックスの鍵により暗号化した鍵チェーンを生成する。なお、鍵チェーンの暗号化方式は、例えば、メッセージ認証コード（ＭＡＣ）付きの秘密鍵暗号化方式等である、デフィー・ヘルマン暗号化方式であってよい。
【００６９】
そして、サーバ２０は、全てのインデックス、全ての文字および全ての状態について、ステップＳ３５からステップＳ３８の処理を実行して鍵チェーンを生成し終えると、処理をステップＳ４２に進める。
【００７０】
続いて、ステップＳ４２において、サーバ２０は、最後の遷移先の状態に対応する鍵により、当該最後の遷移先の状態が、オートマトンにより定められた最終状態であるか否かを示す値を暗号化した最終状態情報を生成する。そして、サーバ２０は、ステップＳ４２の処理を終えると、当該フローを抜けて処理を終了する。
【００７１】
図７は、インデックス、文字および状態の組み合わせ毎に生成された鍵チェーンの集合の一例を示す。サーバ２０は、図４のステップＳ３１からステップＳ４１の処理を実行した結果、鍵チェーンの集合を生成することができる。
【００７２】
例えば、図６に示されるようなオートマトンの遷移表および鍵が発生される場合、サーバ２０は、図７に示されるような、インデックス、文字および状態の組み合わせ毎に対応する鍵チェーンの集合を生成することができる。
【００７３】
なお、Ｅｎｃ（ｘ，ｙ）は、鍵ｘによりデータｙを共通鍵暗号化方式によって暗号化することを表す。共通鍵暗号化方式とは、暗号化と復号化に同一の鍵を用いる暗号化方式であり、例えば、ＤＥＳ（Data Encryption Standard）及びＡＥＳ（Advanced Encryption Standard）等である。
【００７４】
図８は、最終状態情報の一例を示す。サーバ２０は、図４のステップＳ４２の処理を実行した結果、最終状態情報を生成することができる。例えば、図６に示されるようなオートマトンの遷移表および鍵が発生される場合において、オートマトンにより定められた正しい最終状態が"ａ"である場合、サーバ２０は、図８に示されるような最終状態情報を生成することができる。
【００７５】
すなわち、サーバ２０は、最後の遷移先の状態"ａ"に対応する鍵"ｒａ３"により、正しい最終状態であることを示す値（本例においては、"１"）を暗号化した最終状態情報を生成する。また、最後の遷移先の状態"ｂ"に対応する鍵"ｒｂ３"により、正しい最終状態ではないことを示す値（本例においては、"０"）を暗号化した最終状態情報を生成する。また、最後の遷移先の状態"ｃ"に対応する鍵"ｒｃ３"により、正しい最終状態ではないことを示す値（本例においては、"０"）を暗号化した最終状態情報を生成する。
【００７６】
図９は、"０"または"１"の２値の文字を入力する場合の、１番目のインデックスから３番目のインデックスまでのインデックス付き状態遷移値の一例を示す。サーバ２０は、図３のステップＳ１４の処理を実行した結果、インデックス付き状態遷移値を生成することができる。
【００７７】
例えば、オートマトンが"０"または"１"の２値の文字を受け入れ可能であって、文字列に含まれる文字数が３である場合には、サーバ２０は、図９に示されるようなインデックス付き状態遷移値を生成する。即ち、サーバ２０は、１番目のインデックスから３番目のインデックスのそれぞれ毎、および、受け入れ可能な文字である"０"および"１"のそれぞれ毎に、インデックス付き状態遷移値を生成する。
【００７８】
図１０は、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合の一例を示す。サーバ２０は、図３のステップＳ１５の処理を実行した結果、インデックス、文字および状態の組み合わせ毎に生成した複数の鍵チェーンのそれぞれに対して、インデックス付き状態遷移値を対応付けることができる。
【００７９】
例えば、図１０に示されるように、サーバ２０は、１番目のインデックスの文字"０"に対応する各鍵チェーンのそれぞれに対して、１番目のインデックスおよび文字"０"の組を表すインデックス付き状態遷移値ｆ（１，０）を対応付ける。また、サーバ２０は、１番目のインデックスの文字"１"に対応する各鍵チェーンのそれぞれに対して、１番目のインデックスおよび文字"１"の組を表すインデックス付き状態遷移値ｆ（１，１）を対応付ける。
【００８０】
また、例えば、図１０に示されるように、サーバ２０は、２番目のインデックスの文字"０"に対応する各鍵チェーンのそれぞれに対して、２番目のインデックスおよび文字"０"の組を表すインデックス付き状態遷移値ｆ（２，０）を対応付ける。また、サーバ２０は、２番目のインデックスの文字"１"に対応する各鍵チェーンのそれぞれに対して、２番目のインデックスおよび文字"１"の組を表すインデックス付き状態遷移値ｆ（２，１）を対応付ける。
【００８１】
また、例えば、図１０に示されるように、サーバ２０は、３番目のインデックスの文字"０"に対応する各鍵チェーンのそれぞれに対して、３番目のインデックスおよび文字"０"の組を表すインデックス付き状態遷移値ｆ（３，０）を対応付ける。また、サーバ２０は、３番目のインデックスの文字"１"に対応する各鍵チェーンのそれぞれに対して、３番目のインデックスおよび文字"１"の組を表すインデックス付き状態遷移値ｆ（３，１）を対応付ける。
【００８２】
図１１は、本実施形態に係る認証システム１０における、秘匿共通集合計算プロトコルによる通信処理の一例を示す。サーバ２０およびクライアント３０は、生成した鍵チェーンの集合のうち、各インデックスにおいて入力された文字に対応する鍵チェーンを、以下のステップＳ５１からステップＳ５８に示す秘匿共通集合計算プロトコルにより、サーバ２０からクライアント３０へと受け渡す。
【００８３】
まず、ステップＳ５１において、クライアント３０は、インデックス付き文字の集合を取得する。例えば、本例においては、クライアント３０は、下記の数６に示されるように、１番目からＮ番目の文字Ｘ１〜ＸＮのそれぞれに対応するＮ個のインデックス付き文字の集合ｇ１〜ｇＮを取得する。
【００８４】
【数６】
0005593458.tif 000007
【００８５】
続いて、ステップＳ５２において、クライアント３０は、多項式Ｐ（ｘ）を生成する。多項式Ｐ（ｘ）は、変数ｘに、インデックス付き文字の集合ｇ１〜ｇＮに含まれる何れかのインデックス付き文字が代入されると０となり、インデックス付き文字以外の値が代入されると非０となる関数である。即ち、クライアント３０は、下記の数７に示されるような、インデックス付き文字の集合ｇ１〜ｇＮに含まれるインデックス付き文字を変数ｘの解とする多項式Ｐ（ｘ）を生成する。
【００８６】
【数７】
0005593458.tif 000008
【００８７】
続いて、ステップＳ５３において、クライアント３０は、下記の数８に示されるように、多項式Ｐ（ｘ）の全ての次数の係数ｌＮ，ｌＮ−１，…，ｌ０、および、予め定められた定数（例えば１）のそれぞれを、準同型性（例えば加法準同型性）を有する暗号化方式により暗号化した複数の送信暗号文を生成する。クライアント３０は、一例として、拡張エルガマル暗号により各係数および予め定められた定数を暗号化する。なお、Ｅ（ｍ）は、平文ｍを加法準同型性を有する暗号化方式により暗号化した暗号文を示す。
【００８８】
【数８】
0005593458.tif 000009
【００８９】
ここで、加法準同型性を有する暗号化方式により暗号化された暗号文は、下記の数９に示されるような特徴を有する。なお、ｍ１、ｍ２、ｍは、平文を表す。
【００９０】
【数９】
0005593458.tif 000010
【００９１】
即ち、加法準同型性を有する暗号化方式では、２つの暗号文Ｅ（ｍ１）、Ｅ（ｍ２）が与えられたときに、暗号文同士の加算結果（Ｅ（ｍ１）＋Ｅ（ｍ２））が、平文同士を加算した後に暗号化した暗号文（Ｅ（ｍ１＋ｍ２））と同一となる。また、暗号文をｋ回加算した結果（ｋ・Ｅ（ｍ））が、平文を任意の数値ｋで乗算した後に暗号化した暗号文（Ｅ（ｋ・ｍ））と同一となる。ここで、暗号文同士の加算と、平文同士の加算は異なるが、便宜上、同じ演算記号"＋"を用いて記述している。
【００９２】
続いて、ステップＳ５４において、クライアント３０は、生成した複数の送信暗号文をサーバ２０に送信する。この場合において、クライアント３０は、何れの次数の係数に対応するのかをサーバ２０が特定できるように、各送信暗号文を送信する。
【００９３】
一方、ステップＳ５５において、サーバ２０は、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合を取得する。本例においては、サーバ２０は、各インデックスのそれぞれについて、下記の数１０に示されるような、インデックス付き状態遷移値が対応付けられた鍵チェーンの集合を取得する。なお、ｊは、インデックスの値を示す。
【００９４】
【数１０】
0005593458.tif 000011
【００９５】
続いて、ステップＳ５６において、サーバ２０は、クライアント３０から送信された複数の送信暗号文に基づき、鍵チェーンの集合に含まれる鍵チェーン毎（即ち、インデックス毎、各文字及び各前状態毎に）に応答暗号文を生成する。より具体的には、サーバ２０は、鍵チェーンの集合に含まれるそれぞれの鍵チェーンについて、送信暗号文に基づいて、対応するインデックス付き状態遷移値がインデックス付き文字の集合に含まれる場合には当該鍵チェーンとなり、インデックス付き状態遷移値がインデックス付き文字の集合に含まれない場合には当該鍵チェーンとならない値（例えば乱数）を暗号化した応答暗号文を生成する。
【００９６】
即ち、サーバ２０は、ｊ番目のインデックス及び文字ｘσに対応するインデックス付き状態遷移値をｆとし、当該鍵チェーンをＳとした場合、準同型性の暗号文の特徴を利用して、下記の数１１に示す応答暗号文を生成する。ここで、数１１に示す応答暗号文は、多項式Ｐ（ｘ）の変数ｘにインデックス付き状態遷移値ｆを代入した結果を表す値Ｐ（ｆ）に対して乱数ｒを乗算した値と、鍵チェーンＳとを加算した値を、加法準同型性を有する暗号化方式で暗号化した暗号文Ｅである。
【００９７】
【数１１】
0005593458.tif 000012
【００９８】
このような応答暗号文は、Ｐ（ｆ）＝ｌＮ・ｆＮ＋ｌＮ―１・ｆＮ−１＋…＋ｌ０・ｆ０および関数Ｅ（）が準同型性を持つことから、Ｐ（ｆ）＝ｒ・｛Ｅ（ｌＮ）・ｆＮ＋Ｅ（ｌＮ−１）・ｆＮ−１＋…＋Ｅ（ｌ０）・ｆ０＋Ｅ（Ｓ）｝へと変形できる。すなわち、サーバ２０は、インデックス付き状態遷移値ｆに対して多項式Ｐ（ｘ）の変数ｘの次数のそれぞれを冪乗した値（ｆＮ，ｆＮ−１，…，ｆ１，ｆ０）を算出する。続いて、サーバ２０は、多項式の各係数を加法準同型性を有する暗号化方式で暗号化した送信暗号文（Ｅ（ｌＮ），Ｅ（ｌＮ−１）…，Ｅ（ｌ１），Ｅ（ｌ０））のそれぞれに、対応する次数が冪乗されたインデックス付き状態遷移値（ｆＮ，ｆＮ−１，…，ｆ１，ｆ０）の回数だけ（暗号文上において）加算した値を算出し、これらを加算合成する。さらに、サーバ２０は、加算合成した値を（暗号文上において）ｒ回加算した後、鍵チェーンＳを暗号化方式Ｅにより暗号化した暗号文Ｅ（Ｓ）を（暗号文上において）加算する。これにより、サーバ２０は、上述の数１１に示されるような応答暗号文を生成することができる。
【００９９】
サーバ２０は、このような応答暗号文を、鍵チェーンの集合に含まれ複数の鍵チェーンのそれぞれに対して生成する。例えば、サーバ２０は、数１０に示されるインデックス付き状態遷移値が対応付けられた鍵チェーンの集合に対応して応答暗号文を生成する場合には、各インデックスについて、下記の数１２に示すような、文字"０"に対応した３個の応答暗号文、および、文字"１"に対応した３個の応答暗号文を生成する。
【０１００】
【数１２】
0005593458.tif 000013
【０１０１】
続いて、ステップＳ５７において、サーバ２０は、生成した各応答暗号文をクライアント３０へと送信する。
【０１０２】
一方、ステップＳ５８において、クライアント３０は、複数の応答暗号文のそれぞれをステップＳ５３で用いた暗号鍵に応じた復号鍵で復号する。
【０１０３】
ここで、多項式Ｐ（ｘ）の解は、インデックス付き文字ｇ１、ｇ２、ｇ３、…、ｇＮである。従って、多項式Ｐ（ｘ）に代入したインデックス付き状態遷移値ｆが、インデックス付き文字ｇ１、ｇ２、ｇ３、…、ｇＮの何れかに一致している場合、多項式Ｐ（ｘ）の演算結果は０となる。よって、この場合、応答暗号文を復号した復号結果は、鍵チェーンＳとなる。
【０１０４】
反対に、多項式Ｐ（ｘ）に代入したインデックス付き状態遷移値ｆが、インデックス付き文字ｇ１、ｇ２、ｇ３、…、ｇＮの何れとも一致していなければ、多項式Ｐ（ｘ）の演算結果は非０の値（例えば乱数）となる。よって、この場合、応答暗号文を復号した復号結果は、鍵チェーンＳとはならない。これにより、クライアント３０は、複数の応答暗号文のそれぞれを復号することにより、それぞれのインデックスについて、入力した文字に対応する鍵チェーンを受け取ることができる。
【０１０５】
以上のようにサーバ２０およびクライアント３０は、秘匿共通集合計算プロトコルによる通信処理を実行することにより、文字列をサーバ２０に対して秘匿し、且つ、入力された文字以外の文字に対応する鍵チェーンをクライアント３０に対して秘匿しつつ、それぞれのインデックスについて、入力した文字に対応する鍵チェーンをサーバ２０からクライアント３０へと受け渡すことができる。
【０１０６】
図１２は、本実施形態におけるクライアント３０により受信された複数の応答暗号文、および、複数の応答暗号文から復号された複数の鍵チェーンの一例を示す。本例においては、クライアント３０は、サーバ２０から、例えば、図１２に示されるような複数の応答暗号文を受信する。
【０１０７】
この場合において、入力された文字列が"０１０"であれば、クライアント３０は、１番目のインデックスの文字"０"に対応する複数の応答暗号文、２番目のインデックスの文字"１"に対応する複数の応答暗号文、および、３番目のインデックスの文字"０"に対応する複数の応答暗号文のそれぞれを復号処理した結果、対応する鍵チェーンを取得することができる。しかし、クライアント３０は、他の応答暗号文を復号した結果、不明値（Ｘ）を取得する。
【０１０８】
クライアント３０は、複数の応答暗号文のそれぞれを復号した復号結果を、鍵チェーンであるか不明値であるのかの区別無く、例えばメモリに記憶する。
【０１０９】
図１３は、クライアント３０における、複数の鍵チェーンの順次の復号処理のフローチャートを示す。クライアント３０は、図３に示されるステップＳ１８の鍵チェーンの順次に復号処理として、以下のステップＳ６１からステップＳ６５の処理を実行する。
【０１１０】
まず、クライアント３０は、インデックスの順に、ステップＳ６２の処理を実行する（ステップＳ６１とステップＳ６３との間のループ処理）。
【０１１１】
より具体的には、ステップＳ６２において、クライアント３０は、直前のインデックスに対応する復号処理おいて復号した鍵を用いて、受取部６４が受け取った全ての鍵チェーンのそれぞれに対して復号処理をして、次のインデックスに対応する鍵を復号していく。この場合において、クライアント３０は、全てのインデックスについて、受取部６４が受け取った複数の応答暗号文の復号結果の全てに対して復号処理を実行してもよい。即ち、クライアント３０は、鍵チェーンおよび不明値を区別無く、全ての復号結果に対して復号処理を実行してもよい。
【０１１２】
また、ステップＳ６２において、クライアント３０は、１番目のインデックスに対応する復号処理おいては、初期状態の鍵を用いて、受取部６４が受け取った全ての鍵チェーンのそれぞれに対して復号処理をして、２番目のインデックスに対応する鍵を復号する。また、ステップＳ６２において、クライアント３０は、文字列の最後の文字に対応する最後のインデックスに対応する復号処理において、受取部６４が受け取った全ての鍵チェーンのそれぞれに対して復号処理をすることにより、最後の遷移先の状態に対応する鍵を復号することができる。
【０１１３】
このような復号処理をすることにより、クライアント３０は、各インデックスに対応する復号処理を実行する毎に、受取部６４が受け取った全ての鍵チェーンのうちの何れか１つの鍵チェーンから、次のインデックスの遷移先の状態に対応する１つの鍵を復号することができる。更に、次のインデックスに対応する復号処理においては、クライアント３０は、当該次のインデックスに対応する鍵により、更に次のインデックスの遷移先の状態に対応する１つの鍵を復号することができる。そして、クライアント３０は、文字列の最後のインデックスに対応する復号処理を実行することにより、最後の遷移先の状態に対応する１つの鍵を復号することができる。
【０１１４】
続いて、ステップＳ６４において、クライアント３０は、最後のインデックスに対応する復号処理を実行して得られた最後の遷移先の状態に対応する鍵により、最終状態情報を復号する。クライアント３０は、最終状態情報を復号した結果、最終状態であることを示す値、または、最終状態ではないことを示す値のいずれかを得ることができる。
【０１１５】
続いて、ステップＳ６５において、クライアント３０は、ステップＳ６４の処理の結果、最終状態であることを示す値が復号されたか否かを判断する。クライアント３０は、最終状態であることを示す値が復号された場合には、文字列がオートマトンにより受理されたことを出力して、当該フローチャートの処理を終了する。また、クライアント３０は、最終状態であることを示す値が復号されなかった場合には、文字列がオートマトンにより受理されなかったことを出力して、当該フローチャートの処理を終了する。
【０１１６】
図１４は、クライアント３０による数の鍵チェーンの順次の復号処理において復号される鍵の一例を示す。本例において、入力された文字列が"０１０"であれば、クライアント３０は、例えば、図１４に示されるように、各インデックスに対応する鍵チェーンの順次の復号処理において、複数の応答暗号文のそれぞれを復号処理した結果（鍵チェーンおよび不明値を含む結果）から、次のインデックスにおいて遷移する状態の鍵を取得することができる。
【０１１７】
即ち、クライアント３０は、１番目のインデックス（最初のインデックス）に対応する復号処理において、初期状態の鍵ｒａ０を用いて、複数の応答暗号文の復号結果（鍵チェーンおよび不定値を含む結果）のそれぞれに対して復号処理をする。これにより、クライアント３０は、複数の応答暗号文の復号結果のうち、２番目のインデックスでのオートマトンの状態（状態ａ）に対応する１つの応答暗号文Ｅｎｃ（ｒａ０，ｒａ１）から、２番目のインデックスに対応する鍵ｒａ１を取得することができる。
【０１１８】
続いて、クライアント３０は、２番目のインデックスに対応する復号処理において、直前のインデックスに対応する復号処理により復号された鍵ｒａ１を用いて、複数の応答暗号文の復号結果のそれぞれに対して復号処理をする。これにより、クライアント３０は、複数の応答暗号文の復号結果のうち、３番目のインデックスでのオートマトンの状態（状態ｂ）に対応する１つの応答暗号文Ｅｎｃ（ｒａ１，ｒｂ２）から、３番目のインデックスに対応する鍵ｒｂ２を取得することができる。
【０１１９】
続いて、クライアント３０は、３番目のインデックス（最後のインデックス）に対応する復号処理において、直前のインデックスに対応する復号処理により復号された鍵ｒｂ２を用いて、複数の応答暗号文の復号結果のそれぞれに対して復号処理をする。これにより、クライアント３０は、複数の応答暗号文の復号結果のうち、最後の遷移先の状態（状態ａ）に対応する１つの応答暗号文Ｅｎｃ（ｒｂ２，ｒａ３）から、最後の遷移先の状態に対応する鍵ｒａ３を取得することができる。
【０１２０】
続いて、クライアント３０は、３番目のインデックス（最後のインデックス）に対応する復号処理の後に、最後の遷移先の状態に対応する鍵ｒａ３を用いて、最終状態情報Ｅｎｃ（ｒａ３，１）を復号する。これにより、クライアント３０は、最終状態情報Ｅｎｃ（ｒａ３，１）から、正しい最終状態を示す値（例えば"１"）を取得することができる。
【０１２１】
図１５は、変形例に係る認証システム１０の構成を示す。本変形例に係る認証システム１０は、図１から図１４を参照して説明した本実施形態に係る認証システム１０と略同一の構成および機能を有する。従って、本変形例については、図１から図１４を参照して説明した認証システム１０が備える部材と略同一の機能および構成を有する部材については、相違点を除き説明を省略する。
【０１２２】
サーバ２０は、オートマトン記憶部４２と、鍵発生部４４と、鍵チェーン生成部４６と、提供部５２とを有する。クライアント３０は、入力部６０と、受取部６４と、復号部６６とを有する。
【０１２３】
サーバ２０の提供部５２は、クライアント３０と通信して、インデックス毎の鍵チェーンの集合のうちからクライアント３０が入力した文字に対応する部分集合を、紛失通信により選択的にクライアント３０へと送信する。また、クライアント３０の受取部６４は、サーバ２０の提供部５２と通信して、インデックス毎に、入力した文字列に対応する鍵チェーンの部分集合を、紛失通信により選択的にサーバ２０から受け取る。
【０１２４】
ここで、提供部５２および受取部６４は、紛失通信のプロトコルを用いて、入力した文字列に対応する鍵チェーンの部分集合の受け渡しを行う。紛失通信は、指定した識別番号以外のメッセージを受信側装置が取得できず且つ指定された識別番号を送信側装置に特定させずに、送信側装置が保有するＭ個のメッセージのうち受信側装置が指定した識別番号のメッセージを送信側装置から受信側装置へと送信するプロトコルである。紛失通信の一例は、例えば、上述した非特許文献２に記載がある。
【０１２５】
従って、提供部５２は、このような紛失通信を用いることにより、クライアント３０が入力した文字列以外の鍵チェーンの部分集合をクライアント３０に対して秘匿して、入力した文字に対応する鍵チェーンの部分集合をクライアント３０に提供することができる。また、受取部６４は、このような紛失通信を用いることにより、入力した文字をサーバ２０に対して秘匿して、入力した文字に対応する鍵チェーンの部分集合をサーバ２０から受け取ることができる。
【０１２６】
また、サーバ２０の提供部５２は、インデックス毎に、鍵チェーンの部分集合内の複数の鍵チェーンを並べ替えてクライアント３０に送信する。これにより、サーバ２０は、復号結果からオートマトンの状態を推定できなくすることができる。
【０１２７】
クライアント３０の復号部６６は、インデックスの順に、直前のインデックスに対応する復号処理おいて復号した鍵を用いて、当該インデックスに対応して受け取った鍵チェーンの部分集合に含まれる各鍵チェーンに対して復号処理をして、次のインデックスに対応する鍵を復号していく。
【０１２８】
図１６は、変形例に係るサーバ２０およびクライアント３０の処理のフローチャートを示す。
【０１２９】
まず、ステップＳ７１において、クライアント３０は、文字列を入力する。ステップＳ７１の処理は、図３に示したステップＳ１１の処理と同様である。
【０１３０】
一方、ステップＳ７２において、サーバ２０は、インデックス毎の鍵チェーンの集合を生成する。ステップＳ７２の処理は、図３に示したステップＳ１３の処理をインデックス毎に実行することにおいて異なるが、他の点は図３に示したステップＳ１３と同様である。
【０１３１】
続いて、ステップＳ７３〜ステップＳ７５のそれぞれにおいて、サーバ２０およびクライアント３０は、インデックス毎に、当該インデックスに対応して生成した鍵チェーンの集合のうち、当該インデックスにおいて入力された文字に対応する鍵チェーンの部分集合を、紛失通信のプロトコルによりサーバ２０からクライアント３０へと受け渡す。即ち、サーバ２０およびクライアント３０は、１番目のインデックスの処理（ステップＳ７３）においては、１番目のインデックスの鍵チェーンの集合に対応して生成した鍵チェーンの集合のうち、１番目のインデックスにおいて入力された文字（即ち、１番目の文字）に対応する鍵チェーンの部分集合を、紛失通信によりサーバ２０からクライアント３０へと受け渡す。
【０１３２】
また、サーバ２０およびクライアント３０は、２番目のインデックスの処理（ステップＳ７４）においては、２番目のインデックスの鍵チェーンの集合に対応して生成した鍵チェーンの集合のうち、２番目のインデックスにおいて入力された文字（即ち、２番目の文字）に対応する鍵チェーンの部分集合を、紛失通信によりサーバ２０からクライアント３０へと受け渡す。
【０１３３】
以後、サーバ２０およびクライアント３０は、３番目からＮ−１番目の各インデックスにおいて同様の処理を実行する。そして、サーバ２０およびクライアント３０は、Ｎ番目のインデックスの処理（ステップＳ７５）においては、Ｎ番目のインデックスの鍵チェーンの集合に対応して生成した鍵チェーンの集合のうち、Ｎ番目のインデックスにおいて入力された文字（即ち、Ｎ番目の文字）に対応する鍵チェーンの部分集合を、紛失通信によりサーバ２０からクライアント３０へと受け渡す。
【０１３４】
なお、入力された文字に対応する鍵チェーンの部分集合を、紛失通信によりサーバ２０からクライアント３０へと受け渡す処理の一例については、図２１〜図２３のフローチャートを参照して更に説明する。
【０１３５】
続いて、ステップＳ７６において、サーバ２０は、初期状態に対応する鍵および最終状態情報をクライアント３０へと送信する。
【０１３６】
続いて、ステップＳ７７において、クライアント３０は、インデックスの順に、直前のインデックスに対応する復号処理おいて復号した鍵を用いて、サーバ２０から受け取った当該インデックスにおいて入力された文字に対応する鍵チェーンの部分集合のそれぞれに対して復号処理をして、次のインデックスに対応する鍵を順次に復号していく。
【０１３７】
なお、ステップＳ７７の処理は、復号対象が当該インデックスにおいて入力された文字に対応する鍵チェーンの部分集合に含まれる複数の鍵チェーンであることにおいて、図３のステップＳ１８の処理と異なるが、他の点については図３のステップＳ１８の処理と同様である。
【０１３８】
以上の処理により、サーバ２０およびクライアント３０は、クライアント３０が入力した文字列をサーバ２０に対して秘匿し且つサーバ２０が保有するオートマトンをクライアント３０に対して秘匿して、クライアント３０に入力された文字列によってサーバ２０が保有するオートマトンが正しい最終状態に遷移するかを判定することができる。
【０１３９】
図１７は、１番目のインデックスの鍵チェーンの集合の一例を示す。図１８は、２番目のインデックスの鍵チェーンの集合の一例を示す。図１９は、３番目のインデックスの鍵チェーンの集合の一例を示す。
【０１４０】
サーバ２０は、図１６のステップＳ７２の処理を実行した結果、インデックス毎の鍵チェーンの集合を生成することができる。例えば、図５および図６に示されるようなオートマトンの遷移表およびインデックス毎の鍵が発生される場合、サーバ２０は、１番目のインデックスの鍵チェーンの集合を、例えば図１７に示されるように生成することができる。
【０１４１】
なお、Ｅｎｃ（ｘ，ｙ）は、鍵ｘによりデータｙを共通鍵暗号化方式によって暗号化することを表す。共通鍵暗号化方式とは、暗号化と復号化に同一の鍵を用いる暗号化方式であり、例えば、ＤＥＳ及びＡＥＳ等である。
【０１４２】
また、同様の場合、サーバ２０は、２番目のインデックスの鍵チェーンの集合を、例えば図１８に示されるように生成することができる。また、同様の場合、サーバ２０は、３番目のインデックスの鍵チェーンの集合を図１９に示されるように生成することができる。
【０１４３】
このようなインデックス毎の鍵チェーンの集合のそれぞれは、文字毎の部分集合に分割される。例えば、図１７、図１８および図１９に示すように、１番目のインデックス、２番目のインデックスおよび３番目のインデックスのそれぞれの鍵チェーンの集合は、文字"０"に対応する鍵チェーンの部分集合、および、文字"１"に対応する鍵チェーンの部分集合を含む。
【０１４４】
なお、サーバ２０は、クライアント３０への送信時においては、各部分集合内の鍵チェーンの並び順をインデックス毎にランダムに並べ替える。これにより、クライアント３０は、鍵チェーンの並び順からオートマトンにおける対応する状態を推定できなくすることができる。
【０１４５】
図２０は、インデックス毎の鍵チェーンの部分集合から順次に復号される鍵の一例を示す。クライアント３０は、紛失通信のプロトコルにより、各インデックスのそれぞれに対応して、当該インデックスにおいて入力された文字に対応する鍵チェーンの部分集合を選択的に受け取る。
【０１４６】
例えば、文字列として"０１０"の３個の文字が入力された場合においては、クライアント３０は、１番目のインデックスにおいては、１番目の文字"０"に対応する鍵チェーンの部分集合を受け取っており、他の文字に対応する鍵チェーンの部分集合は受け取っていない。また、クライアント３０は、２番目のインデックスにおいては、２番目の文字"１"に対応する鍵チェーンの部分集合を受け取っており、他の文字に対応する鍵チェーンの部分集合は受け取っていない。また、クライアント３０は、３番目のインデックスにおいては、３番目の文字"０"に対応する鍵チェーンの部分集合を受け取っており、他の文字に対応する鍵チェーンの部分集合は受け取っていない。
【０１４７】
そして、クライアント３０は、初期状態から順にインデックス毎に、当該インデックスにおいて受け取った、入力した文字に対応した鍵チェーンの部分集合に含まれる各鍵チェーンから、当該状態から遷移する状態に対応する次のインデックスの鍵を復号していく。
【０１４８】
まず、クライアント３０は、１番目のインデックスにおいては、入力した文字に対応した鍵チェーンの部分集合に含まれる複数の鍵チェーンのそれぞれを、初期状態に対応する鍵（初期状態に対応する１番目のインデックスの鍵）により復号処理をする。これにより、クライアント３０は、入力した文字に対応した鍵チェーンの部分集合のうち、初期状態に対応した１つの鍵チェーンから、１つの鍵を復号することができる。
【０１４９】
例えば、図２０に示す例においては、クライアント３０は、１番目のインデックスにおける文字"０"に対応した鍵チェーンの部分集合のそれぞれに対して、初期状態に対応する１番目のインデックスの鍵ｒａ０により復号処理を実行する。これにより、クライアント３０は、文字"０"の初期状態"ａ"に対応する１つの鍵チェーンＥｎｃ（ｒａｏ，ｒａ１）から、２番目のインデックスの鍵ｒａ１を復号することができる。
【０１５０】
また、クライアント３０は、２番目以降のインデックスにおいては、入力した文字に対応した鍵チェーンの部分集合に含まれる複数の鍵チェーンのそれぞれを、直前のインデックスに対応する復号処理において復号された鍵により復号処理をする。これにより、クライアント３０は、当該インデックスにおいてオートマトンが遷移した状態に対応する鍵チェーンから、次のインデックスの１つの鍵を復号することができる。
【０１５１】
例えば、図２０に示す例においては、クライアント３０は、２番目のインデックスにおける文字"１"に対応した鍵チェーンの部分集合のそれぞれに対して、１番目のインデックスに対応する復号処理において復号された鍵ｒａ１により、復号処理を実行する。これにより、クライアント３０は、文字"１"の状態"ａ"に対応する１つの鍵チェーンＥｎｃ（ｒａ１，ｒｂ２）から、３番目のインデックスの鍵ｒｂ２を復号することができる。
【０１５２】
また、例えば、図２０に示す例においては、クライアント３０は、３番目のインデックスにおける文字"０"に対応した鍵チェーンの部分集合のそれぞれに対して、２番目のインデックスの復号処理において復号された鍵ｒｂ２により、復号処理を実行する。これにより、クライアント３０は、文字"０"の状態"ｂ"に対応する１つの鍵チェーンＥｎｃ（ｒｂ２，ｒａ３）から、最後の遷移先の状態に対応する鍵ｒａ３を復号することができる。
【０１５３】
そして、クライアント３０は、最後の遷移先の状態に対応する鍵を復号した後、復号した当該鍵により最終状態情報を復号する。クライアント３０は、最終状態情報を復号した結果、最終状態を表す値を取得できた場合に正しい最終状態に遷移したと判断する。
【０１５４】
例えば、図２０に示す例においては、クライアント３０は、最終状態情報Ｅｎｃ（ｒａ３，１）に対して、３番目のインデックスにおいて復号された鍵ｒａ３により、復号処理を実行する。これにより、クライアント３０は、最終状態を表す値（例えば、１）を復号して、文字列がオートマトンに受理されたことを示す情報を出力することができる。
【０１５５】
以上のように本実施形態に係るサーバ２０およびクライアント３０によれば、クライアント３０が入力した文字列をサーバ２０に対して秘匿し、且つ、サーバ２０が保有するオートマトンをクライアント３０に対して秘匿して、文字列がオートマトンに受理されるか否かを判定することができる。
【０１５６】
図２１は、本変形例に係るサーバ２０とクライアント３０との間における鍵チェーンの部分集合の紛失通信による受け渡し処理のフローを示す。図２２は、図２１に続くフローを示す。図２３は、図２２に続くフローを示す。
【０１５７】
以下、図２１、図２２および図２３を参照して、ステップＳ７３〜ステップＳ７５のそれぞれのインデックスに対する処理において実行される紛失通信の通信処理の一例を説明する。なお、本実施形態において行われる紛失通信は、以下に説明する処理に限らず、他の処理により実現してもよい。
【０１５８】
なお、本例においては、オートマトンが受け取り可能な文字がＭ個（Ｍは、２以上の整数）存在するものとする。また、当該インデックスにおいてクライアント３０が入力した文字は、Ｍ個の文字のうちの識別番号ｉ（ｉ番目）の文字であるとする。
【０１５９】
まず、ステップＳ８１において、サーバ２０は、"ｒ"を生成する。続いて、ステップＳ８２において、サーバ２０は、"ｇ"に"ｒ"を冪乗して、"ｇｒ"を生成する。
【０１６０】
ここで、"ｇ"は、位数"ｑ"の生成元を表す。なお、"ｑ"は、任意の素数である。また、"ｇ"は、サーバ２０およびクライアント３０の両者で共通に定められた値である。
【０１６１】
また、"ｒ"は、位数"ｑ"の巡回群"Ｚｑ"からランダムに選択された値である。また、後述する"ｒ１"および"ｒ２"も、位数"ｑ"の巡回群Ｚｑからランダムに選択された値である。
【０１６２】
続いて、ステップＳ８３において、サーバ２０は、"Ｔ２，Ｔ３，Ｔ４，…，ＴＭ"を生成する。Ｔ２，Ｔ３，Ｔ４，…，ＴＭ"は、（Ｍ−１）個の任意の整数であり、２からＭまでの識別番号が付けられている。続いて、ステップＳ８４において、サーバ２０は、"ｇｒ"および"Ｔ２，Ｔ３，Ｔ４，…，ＴＭ"をクライアント３０へと送信する。
【０１６３】
なお、クライアント３０は、離散対数の性質から、"ｇｒ"から"ｒ"を算出することはきわめて困難である。従って、"ｒ"は、クライアント３０に対して秘匿されているといえる。
【０１６４】
続いて、ステップＳ８５において、クライアント３０は、Ｍ個の文字のうち、当該インデックスにおいて入力された文字を特定するための識別番号を受け取る。本例においては、クライアント３０は、識別番号として"ｉ"受け取る。ここで、"ｉ"は、１以上Ｍ以下の任意の整数である。
【０１６５】
続いて、ステップＳ８６において、クライアント３０は、"Ｔ２，Ｔ３，Ｔ４，…，ＴＭ"の中から、ｉ番目の識別番号に対応する"Ｔｉ"を選択する。なお、識別番号ｉが１の場合（ｉ＝１の場合）には、クライアント３０は、ステップＳ８６において値を選択しない。
【０１６６】
続いて、ステップＳ８７において、クライアント３０は、"ｒ２"を生成する。続いて、ステップＳ８８において、クライアント３０は、"ｇ"に"ｒ２"を冪乗して、"ｇｒ２"を生成する。
【０１６７】
続いて、ステップＳ８９において、クライアント３０は、"ＰＫ１"を算出する。具体的には、クライアント３０は、ｉ＝１の場合には、"ｇｒ２"を"ＰＫ１"とする（ＰＫ１＝ｇｒ２）。また、クライアント３０は、ｉ≠１の場合には、"Ｔｉ／ｇｒ２"を算出し、算出した"Ｔｉ／ｇｒ２"を"ＰＫ１"とする（ＰＫ１＝Ｔｉ／ｇｒ２）。
【０１６８】
続いて、ステップＳ９０において、クライアント３０は、"ＰＫ１"をサーバ２０へと送信する。なお、サーバ２０は、離散対数の性質から、"ｇｒ２"から"ｒ２"を算出することはきわめて困難である。従って、"ｒ２"は、サーバ２０に対して秘匿されているといえる。
【０１６９】
続いて、ステップＳ９１において、サーバ２０は、"ｒ"および"Ｔ２，Ｔ３，Ｔ４，…，ＴＭ"、並びに、受信した"ＰＫ１"に基づき、下記の式（１１）のように、（ＰＫ１）ｒ、（ＰＫ２）ｒ、…、（ＰＫｉ）ｒ、…、（ＰＫＭ）ｒを算出する。
【０１７０】
【数１３】
0005593458.tif 000014
【０１７１】
なお、ここで、（ＰＫｉ）ｒは、下記の式（１２）のように、ｇ（ｒ２・ｒ）となる。
【０１７２】
【数１４】
0005593458.tif 000015
【０１７３】
続いて、ステップＳ９２において、サーバ２０は、"ｒ１"を生成する。
【０１７４】
続いて、ステップＳ９３において、サーバ２０は、下記の式（１３）に示すように、Ｍ個の暗号鍵"Ｓ１，Ｓ２，…，Ｓｉ，…，ＳＭ"を生成する。なお、下記の式（１３）において、Ｈ（ｘ，ｙ，ｚ）は、ｘ、ｙ、ｚを変数としたハッシュ関数を表す。
【０１７５】
【数１５】
0005593458.tif 000016
【０１７６】
続いて、ステップＳ９４において、サーバ２０は、当該インデックスにおける、Ｍ個の鍵チェーンの部分集合"Ｙ１，Ｙ２，…，ＹＭ"を入力する。即ち、サーバ２０は、当該インデックスに対応する、識別番号ｉ＝１に対応する文字の部分集合Ｙ１から識別番号ｉ＝Ｍに対応する文字の部分集合ＹＭまでを入力する。
【０１７７】
続いて、ステップＳ９５において、サーバ２０は、Ｍ個の鍵チェーンの部分集合"Ｙ１，Ｙ２，…，ＹＭ"のそれぞれを、ステップＳ９３で生成したＭ個の暗号鍵"Ｓ１，Ｓ２，…，Ｓｉ，…，ＳＭ"のそれぞれにより暗号化する。即ち、サーバ２０は、当該インデックスの１番目の文字に対応する鍵チェーンの部分集合Ｙ１を、１番目の暗号鍵"Ｓ１"により暗号化する。
【０１７８】
また、サーバ２０は、当該インデックスの２番目の文字に対応する鍵チェーンの部分集合Ｙ２を、２番目の暗号鍵"Ｓ２"により暗号化する。また、サーバ２０は、当該インデックスのｉ番目の文字に対応する鍵チェーンの部分集合Ｙｉを、ｉ番目の暗号鍵"Ｓｉ"により暗号化する。また、サーバ２０は、当該インデックスのＭ番目の文字に対応する鍵チェーンの部分集合ＹＭを、Ｍ番目の暗号鍵"ＳＭ"により暗号化する。これにより、サーバ２０は、下記の式（１４）に示すようなＭ個の暗号文を生成することができる。
【０１７９】
【数１６】
0005593458.tif 000017
【０１８０】
続いて、ステップＳ９６において、サーバ２０は、生成したＭ個の暗号文をクライアント３０へと送信する。続いて、ステップＳ９７において、サーバ２０は、"ｒ１"をクライアント３０へと送信する。
【０１８１】
一方、ステップＳ９８において、クライアント３０は、"ｇｒ"に"ｒ２"を冪乗した"（ｇｒ）ｒ２"を算出する。ここで、（ＰＫｉ）ｒは、式（１２）で示したように、ｇ（ｒ２・ｒ）となる。即ち、ステップＳ９８でクライアント３０が算出した"（ｇｒ）ｒ２"は、"（ＰＫｉ）ｒ"を表す。
【０１８２】
続いて、ステップＳ９９において、クライアント３０は、"（ＰＫｉ）ｒ"、"ｒ１"及び"ｉ"を用いて、識別番号ｉに対応した暗号鍵"Ｓｉ"を生成する。なお、クライアント３０は、（ＰＫｉ）ｒ以外の値（例えば（ＰＫ１）ｒ、（ＰＫ２）ｒ、及び（ＰＫＭ）ｒ等）を生成することはできないので、識別番号ｉに対応した暗号鍵"Ｓｉ"以外の暗号鍵を生成することはできない。従って、クライアント３０は、識別番号ｉの文字に対応した鍵チェーンの部分集合Ｙｊ以外の鍵チェーンの部分集合を取得することはできない。
【０１８３】
続いて、ステップＳ１００において、クライアント３０は、暗号文Ｅ（Ｓｉ，Ｙｊ）から、ステップＳ９９で生成した暗号鍵"Ｓｉ"を用いて鍵チェーンの部分集合Ｙｊを復号する。これにより、クライアント３０は、識別番号ｉの文字に対応した鍵チェーンの部分集合Ｙｊを取得することができる。
【０１８４】
以上のように、サーバ２０およびクライアント３０は、当該インデックスにおいて入力された識別番号ｉの文字に対応する鍵チェーンの部分集合Ｙｊ以外の鍵チェーンの部分集合をクライアント３０が取得できず且つ識別番号ｉの文字をサーバ２０に特定させずに、識別番号ｉの文字に対応する鍵チェーンの部分集合Ｙｊを受け渡すことができる。
【０１８５】
図２４は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【０１８６】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【０１８７】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【０１８８】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、及び／又は、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。
【０１８９】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【０１９０】
コンピュータ１９００にインストールされ、コンピュータ１９００を、サーバ２０として機能させるプログラムは、オートマトン記憶モジュールと、鍵発生モジュールと、鍵チェーン生成モジュールと、インデックス付き状態遷移値生成モジュールと、合成モジュールと、提供モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、オートマトン記憶部４２、鍵発生部４４、鍵チェーン生成部４６、インデックス付き状態遷移値生成部４８、合成部５０および提供部５２としてそれぞれ機能させる。
【０１９１】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、オートマトン記憶部４２、鍵発生部４４、鍵チェーン生成部４６、インデックス付き状態遷移値生成部４８、合成部５０および提供部５２として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のサーバ２０が構築される。
【０１９２】
コンピュータ１９００にインストールされ、コンピュータ１９００を、クライアント３０として機能させるプログラムは、入力モジュールと、インデックス付き文字生成モジュールと、受取モジュールと、復号モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、入力部６０、インデックス付き文字生成部６２、受取部６４および復号部６６としてそれぞれ機能させる。
【０１９３】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、入力部６０、インデックス付き文字生成部６２、受取部６４および復号部６６として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のクライアント３０が構築される。
【０１９４】
一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、又はＣＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置又は通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。
【０１９５】
また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０（ＣＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、及び／又は記憶装置に含まれるものとする。
【０１９６】
また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合（又は不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。
【０１９７】
また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。
【０１９８】
以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤ又はＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１９９】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０２００】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【０２０１】
１０  認証システム
２０  サーバ
３０  クライアント
４２  オートマトン記憶部
４４  鍵発生部
４６  鍵チェーン生成部
４８  インデックス付き状態遷移値生成部
５０  合成部
５２  提供部
６０  入力部
６２  インデックス付き文字生成部
６４  受取部
６６  復号部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
0005593458.tif 000018
【図２】
0005593458.tif 000019
【図３】
0005593458.tif 000020
【図４】
0005593458.tif 000021
【図５】
0005593458.tif 000022
【図６】
0005593458.tif 000023
【図７】
0005593458.tif 000024
【図８】
0005593458.tif 000025
【図９】
0005593458.tif 000026
【図１０】
0005593458.tif 000027
【図１１】
0005593458.tif 000028
【図１２】
0005593458.tif 000029
【図１３】
0005593458.tif 000030
【図１４】
0005593458.tif 000031
【図１５】
0005593458.tif 000032
【図１６】
0005593458.tif 000033
【図１７】
0005593458.tif 000034
【図１８】
0005593458.tif 000035
【図１９】
0005593458.tif 000036
【図２０】
0005593458.tif 000037
【図２１】
0005593458.tif 000038
【図２２】
0005593458.tif 000039
【図２３】
0005593458.tif 000040
【図２４】
0005593458.tif 000041