(57)【要約】【課題】オートマトンが文脈自由文法を満たすかを判定する。【解決手段】オートマトンを保持するクライアントと接続可能な、文脈自由文法を保持するサーバであって、クライアントにより保持された前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、文脈自由文法の生成規則の被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値とを、クライアントに対して暗号化文字列値を秘匿して比較し、暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともにクライアントに送信するサーバを提供する。【選択図】図３
2013246294.tif 000002
【特許請求の範囲】
【請求項１】
オートマトンを保持するクライアントと接続可能な、文脈自由文法を保持するサーバであって、
前記クライアントにより保持された前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、前記文脈自由文法の生成規則の被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値とを、前記クライアントに対して前記暗号化文字列値を秘匿して比較し、
前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記クライアントに送信する
サーバ。
【請求項２】
当該サーバは、
前記文脈自由文法における複数の生成規則のそれぞれを複数の遷移パターンに対応して複数に展開し、展開したそれぞれの生成規則に含まれる非終端文字に対して対応する遷移パターンに応じた前状態および後状態を割り当てる展開部と、
展開後の複数の生成規則のそれぞれについて、割り当てられた前状態及び後状態に対応付けて置換記号を暗号化した暗号化値を生成する左辺処理部と、
前記展開後の複数の生成規則のそれぞれについて、被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値を生成する右辺処理部と、
前記クライアントにより保持された前記エッジペアと、前記展開後の複数の生成規則のそれぞれに対応する前記暗号化文字列値とを、前記クライアントに対して前記暗号化文字列値を秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記クライアントに送信する送信部と、
を備える請求項１に記載のサーバ。
【請求項３】
前記クライアントは、
前記オートマトンにおける状態遷移を表す複数のエッジを含むエッジ集合を記憶するエッジ集合記憶部と、
前記エッジ集合から連続遷移可能な複数のエッジを選択し、選択した複数のエッジに含まれる暗号化値の列を表すエッジペアを生成するエッジペア生成部と、
前記エッジペアと前記展開後の複数の生成規則のそれぞれに対応する前記暗号化文字列値とを、前記サーバに対して前記エッジペアを秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信する受信部と、
受信した前記前状態、前記後状態および前記暗号化値の組を新たなエッジとして前記エッジ集合に追加する追加部と、
を備える請求項２に記載のサーバ。
【請求項４】
前記展開部は、前記文脈自由文法における複数の生成規則のうち被置換記号列が空文字である生成規則を抽出し、抽出した生成規則を前記オートマトンの各状態に対応して展開し、展開したそれぞれの生成規則の置換記号に対して同一の前状態および後状態を割り当て、
前記受信部は、被置換記号列が空文字である生成規則の置換記号を暗号化した前記暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信し、
前記追加部は、受信した前記前状態、前記後状態および前記暗号化値の組を新たなエッジとして前記エッジ集合に追加する
請求項３に記載のサーバ。
【請求項５】
前記エッジ集合記憶部は、前記オートマトンにおける複数の状態遷移のそれぞれに対応して、前状態、後状態および入力文字の組を表す初期エッジを予め記憶し、
前記展開部は、前記文脈自由文法における複数の生成規則のうち被置換記号列が終端文字である生成規則を抽出し、抽出した生成規則を前記オートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開し、展開したそれぞれの生成規則の置換記号に対して対応する遷移パターンに応じた前状態および後状態を割り当て、
前記受信部は、前記終端文字が何れかの前記初期エッジに含まれる前記入力文字に一致し、且つ、前記置換記号に割り当てられた前記前状態および前記後状態が当該初期エッジに含まれる前状態および後状態に一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信し、
前記追加部は、受信した前状態、後状態および前記暗号化値の組を新たなエッジとして前記エッジ集合に追加する
請求項４に記載のサーバ。
【請求項６】
当該サーバは、生成規則がチョムスキー標準型で表された文脈自由文法を保持する
請求項５に記載のサーバ。
【請求項７】
前記展開部は、前記文脈自由文法における複数の生成規則のうち被置換記号列が２つの非終端文字の列である生成規則を抽出し、抽出した生成規則を前記オートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開し、展開したそれぞれの生成規則に含まれる非終端文字のそれぞれに対して対応する遷移パターンに応じた前状態および後状態を割り当て、
前記右辺処理部は、前記展開後の複数の生成規則のそれぞれの被置換記号列に含まれる２つの非終端文字のそれぞれを暗号化して、前記暗号化文字列値を生成する
請求項６に記載のサーバ。
【請求項８】
エッジペア生成部は、前記エッジ集合から連続遷移可能な２つのエッジを選択し、選択した２つのエッジのそれぞれに含まれる暗号化値を関数に代入してスカラー値化して前記エッジペアを生成し、
前記右辺処理部は、被置換記号列が２つの非終端文字の列である生成規則について、前記２つの非終端文字のそれぞれの暗号化値を前記関数に代入してスカラー値化して前記暗号化文字列値を生成する
請求項７に記載のサーバ。
【請求項９】
前記受信部は、
前記追加部が新たなエッジを追加した場合、再度、前記エッジペアと前記展開後の複数の生成規則のそれぞれに対応する暗号化文字列値とを比較して、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、前記サーバから受信する
請求項７に記載のサーバ。
【請求項１０】
前記展開部は、前記文脈自由文法における開始文字を抽出し、抽出した開始文字を前記オートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開し、展開したそれぞれの開始文字に対して対応する遷移パターンに応じた前状態および後状態を割り当て、
前記サーバは、展開後の複数の開始文字のそれぞれを、割り当てられた前状態及び後状態に対応付けて前記開始文字を暗号化した暗号化開始文字を生成する開始文字処理部を更に備え、
前記クライアントは、前記エッジ集合に含まれる複数のエッジのうち前記オートマトンにおける開始状態から終了状態への遷移を表すエッジを、終了エッジとして抽出する終了エッジ抽出部を更に備え、
前記送信部および前記受信部は、前記サーバに対して前記終了エッジを秘匿し、且つ、前記クライアントに対して前記暗号化開始文字を秘匿した状態で、前記終了エッジに含まれる暗号化値と前記暗号化開始文字とを比較し、
前記受信部は、前記終了エッジに含まれる暗号化値と前記暗号化開始文字とが一致した場合に、前記オートマトンが前記文脈自由文法を満たすと判定する
請求項９に記載のサーバ。
【請求項１１】
前記送信部および前記受信部は、秘匿共通集合計算プロトコルにより前記クライアントに対して前記暗号化文字列値を秘匿し且つ前記サーバに対して前記エッジペアを秘匿して、前記エッジペアと前記展開後の複数の生成規則のそれぞれに対応する前記暗号化文字列値とを比較する
請求項３に記載のサーバ。
【請求項１２】
前記クライアントは、文字列を入力して、入力した文字列を表すオートマトンを生成するオートマトン生成部を更に備える
請求項３に記載のサーバ。
【請求項１３】
請求項１に記載のサーバと接続可能な、オートマトンを保持するクライアントであって、
前記エッジペアと前記暗号化文字列値とを、前記サーバに対して前記エッジペアを秘匿して比較し、
前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信する
クライアント。
【請求項１４】
請求項２に記載のサーバと接続可能な、オートマトンを保持するクライアントであって、
当該クライアントは、
前記オートマトンにおける状態遷移を表す複数のエッジを含むエッジ集合を記憶するエッジ集合記憶部と、
前記エッジ集合から連続遷移可能な複数のエッジを選択し、選択した複数のエッジに含まれる暗号化値の列を表すエッジペアを生成するエッジペア生成部と、
前記エッジペアと前記展開後の複数の生成規則のそれぞれに対応する前記暗号化文字列値とを、前記サーバに対して前記エッジペアを秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信する受信部と、
受信した前記前状態、前記後状態および前記暗号化値の組を新たなエッジとして前記エッジ集合に追加する追加部と、
を備えるクライアント。
【請求項１５】
コンピュータを請求項１に記載のサーバとして機能させるためのプログラム。
【請求項１６】
コンピュータを請求項１３に記載のクライアントとして機能させるためのプログラム。
【請求項１７】
オートマトンを保持する第１コンピュータと文脈自由文法を保持する第２コンピュータとにより、前記オートマトンが前記文脈自由文法を満たすかを判定する方法であって、
前記第１コンピュータにより保持された前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、前記文脈自由文法の生成規則の被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値とを、前記第２コンピュータに対して前記暗号化文字列値を秘匿して比較し且つ前記第２コンピュータに対して前記エッジペアを秘匿して比較し、
前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに、前記第１コンピュータから前記第２コンピュータへと送信する
方法。
【請求項１８】
前記第２コンピュータにおいて実行され、前記文脈自由文法における複数の生成規則のそれぞれを複数の遷移パターンに対応して複数に展開し、展開したそれぞれの生成規則に含まれる非終端文字に対して対応する遷移パターンに応じた前状態および後状態を割り当てる展開ステップと、
前記第２コンピュータにおいて実行され、展開後の複数の生成規則のそれぞれについて、割り当てられた前状態及び後状態に対応付けて置換記号を暗号化した暗号化値を生成する左辺処理ステップと、
前記第２コンピュータにおいて実行され、前記展開後の複数の生成規則のそれぞれについて、被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値を生成する右辺処理ステップと、
前記第１コンピュータにおいて実行され、前記オートマトンにおける状態遷移を表す複数のエッジを含むエッジ集合を記憶するエッジ集合記憶ステップと、
前記第１コンピュータにおいて実行され、前記エッジ集合から連続遷移可能な複数のエッジを選択し、選択した複数のエッジに含まれる暗号化値の列を表すエッジペアを生成するエッジペア生成ステップと、
前記第１コンピュータおよび前記第２コンピュータにおいて実行され、前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、前記展開後の複数の生成規則のそれぞれに対応する前記暗号化文字列値とを、前記第２コンピュータに対して前記暗号化文字列値を秘匿して比較し且つ前記第２コンピュータに対して前記エッジペアを秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともに、前記第２コンピュータから第１コンピュータへと送信する送信ステップと、
受信した前記前状態、前記後状態および前記暗号化値の組を新たなエッジとして前記エッジ集合に追加する追加ステップと、
を備える請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オートマトンが文脈自由文法を満たすか否かを判定するサーバ、クライアント、方法およびプログラムに関する。
【背景技術】
【０００２】
クライアントが保有する文字列が、サーバが保有するオートマトンに受理されるか否かを認証するシステムが知られている（例えば、特許文献１参照。）。
［先行技術文献］
［特許文献］
特許文献１  特開２００９−１５１７５７号公報
［非特許文献］
非特許文献１  Michael J. Freedman, Kobbi Nissim and Benny Pinkas、 "Efficient Private Matching and Set Intersection"、 Advances in Cryptology EUROCRYPT 2004、Lecture Notes in Computer Science、２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、クライアントがオートマトンを保持し、サーバが文脈自由文法を保持している場合において、オートマトンをサーバに対して秘匿し且つ文脈自由文法をクライアントに対して秘匿した状態で、オートマトンが文脈自由文法を満たすか否かを判定することは非常に難しかった。
【課題を解決するための手段】
【０００４】
本発明の第１の態様においては、オートマトンを保持するクライアントと接続可能な、文脈自由文法を保持するサーバであって、前記クライアントにより保持された前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、前記文脈自由文法の生成規則の被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値とを、前記クライアントに対して前記暗号化文字列値を秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記クライアントに送信するサーバ、および、このようなサーバとしてコンピュータを機能させるためのプログラムを提供する。
【０００５】
本発明の第２の態様においては、第１態様のサーバと接続可能な、オートマトンを保持するクライアントであって、前記エッジペアと前記暗号化文字列値とを、前記サーバに対して前記エッジペアを秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに前記サーバから受信するクライアント、および、このようなクライアントとしてコンピュータを機能させるためのプログラムを提供する。
【０００６】
本発明の第３の態様においては、オートマトンを保持する第１コンピュータと文脈自由文法を保持する第２コンピュータとにより、前記オートマトンが前記文脈自由文法を満たすかを判定する方法であって、前記第１コンピュータにより保持された前状態及び後状態に対応付けて非終端文字を暗号化した暗号化値の列を表すエッジペアと、前記文脈自由文法の生成規則の被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値とを、前記第２コンピュータに対して前記暗号化文字列値を秘匿して比較し且つ前記第２コンピュータに対して前記エッジペアを秘匿して比較し、前記暗号化文字列値がエッジペアと一致した生成規則の置換記号を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を、割り当てられた前状態および後状態とともに、前記第１コンピュータから前記第２コンピュータへと送信する方法を提供する。
【０００７】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【０００８】
【図１】図１は、本実施形態に係る認証システム１０の構成を示す。
【図２】図２は、サーバ２０が保持する文脈自由文法の生成規則の一例を示す。
【図３】図３は、本実施形態に係るサーバ２０の機能ブロック構成およびクライアント３０の機能ブロック構成を示す。
【図４】図４は、本実施形態に係る認証システム１０の全体処理フローを示す。
【図５】図５は、事前処理（Ｓ１０）のフローを示す。
【図６】図６は、文字列"０１０"を入力した場合に生成されるオートマトンの一例を示す。
【図７】図７は、初期エッジの一例を示す。
【図８】図８は、空文字処理（Ｓ２０）のフローを示す。
【図９】図９は、ステップＳ２１において抽出される、被置換記号列が空文字である生成規則の一例を示す。
【図１０】図１０は、ステップＳ２２において展開された被置換記号列が空文字である生成規則の置換記号の一例、および、ステップＳ２３において生成された暗号化値の一例を示す。
【図１１】図１１は、ステップＳ２４においてサーバ２０からクライアント３０へと送信される、暗号化値、前状態および後状態の一例を示す。
【図１２】図１２は、ステップＳ２５においてエッジが追加されたエッジ集合に追加されたエッジの一例を示す。
【図１３】図１３は、終端文字処理（Ｓ３０）のフローを示す。
【図１４】図１４は、ステップＳ３１において抽出される、被置換記号列が終端文字の生成規則の一例を示す。
【図１５】図１５は、ステップＳ３２において展開された被置換記号列が終端文字の生成規則の置換記号の一例、および、ステップＳ３３において生成された暗号化値の一例を示す。
【図１６】図１６は、初期エッジに含まれる前状態、後状態および入力文字と一致する、展開後の生成規則の置換記号の一例を示す。
【図１７】図１７は、ステップＳ３４においてサーバ２０からクライアント３０へと送信される、暗号化値、前状態および後状態の一例を示す。
【図１８】図１８は、ステップＳ３５においてエッジ集合に追加されたエッジの一例を示す。
【図１９】図１９は、非終端文字処理（Ｓ４０）のフローを示す。
【図２０】図２０は、ステップＳ４１において抽出される、被置換記号列が非終端文字の列である生成規則の一例を示す。
【図２１】図２１は、ステップＳ４２において展開された、被置換記号列が非終端文字の列である生成規則の一例を示す。
【図２２】図２２は、ステップＳ４４においてスカラー値化された暗号化文字列値の一例を示す。
【図２３】図２３は、ステップＳ４５において選択されるエッジペアの一例を示す。
【図２４】図２４は、ステップＳ４５においてスカラー値化されたエッジペアの一例を示す。
【図２５】図２５は、１回目のループのステップＳ３５においてエッジ集合に追加されたエッジの一例を示す。
【図２６】図２６は、２回目のループのステップＳ３５においてエッジ集合に追加されたエッジの一例を示す。
【図２７】図２７は、３回目のループのステップＳ３５においてエッジ集合に追加されたエッジの一例を示す。
【図２８】図２８は、判定処理（Ｓ５０）のフローを示す。
【図２９】図２９は、ステップＳ５２において展開された開始文字の一例、および、ステップＳ５３において生成された暗号化開始文字の一例を示す。
【図３０】図３０は、終了エッジに含まれる暗号化値と一致する、暗号化開始文字の一例を示す。
【図３１】図３１は、本発明の実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【発明を実施するための形態】
【０００９】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１０】
図１は、本実施形態に係る認証システム１０の構成を示す。本実施形態に係る認証システム１０は、サーバ２０と、クライアント３０とを備える。サーバ２０とクライアント３０とは互いにネットワークを介して接続可能とされている。
【００１１】
サーバ２０は、文脈自由文法を保持する。クライアント３０は、オートマトンを保持する。クライアント３０は、一例として、外部から入力した文字列を表すオートマトンを保持する。
【００１２】
認証システム１０は、クライアント３０が保持するオートマトンが、サーバ２０が保持する文脈自由文法を満たすか否かを判定する。即ち、認証システム１０は、クライアント３０が保持するオートマトンにより表される各文字列が、サーバ２０が保持する文脈自由文法により生成することができるか否かを判定する。
【００１３】
オートマトンは、状態の集合Ｑ、入力文字の集合Σ、開始状態Ｓ０、終了状態の集合Ｆ、及び、状態遷移（状態遷移図又は状態遷移表等）により定義される。
【００１４】
本実施形態においては、クライアント３０が、文字列"０１０"を表すオートマトンを保持する場合を例として説明する。即ち、本例において、クライアント３０が保持するオートマトンは、状態の集合がＱ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝であり、入力文字の集合がΣ＝｛０，１｝であり、開始状態がＳ０＝ｑ０であり、終了状態の集合がＦ＝｛ｑ３｝である。また、このオートマトンは、状態ｑ０において"０"を入力した場合に状態ｑ１に遷移し、状態ｑ０において"１"を入力した場合に状態ｑ２に遷移し、状態ｑ２において"０"を入力した場合に状態ｑ３に遷移する。
【００１５】
なお、ｑ０，ｑ１，ｑ２，ｑ３は、オートマトンの状態を識別するためのインデックスである。ｑ０，ｑ１，ｑ２，ｑ３は、一例として、状態毎に固有の数値である。
【００１６】
文脈自由文法は、非終端文字の集合Γ、終端文字の集合Σ、開始文字ｓ、および、複数の生成規則により定義される。
【００１７】
本実施形態においては、サーバ２０が、図１に示されるような文脈自由文法を保持する場合を例として説明する。即ち、本例において、サーバ２０が保持する文脈自由文法は、非終端文字の集合がΓ＝｛Ｓ，Ａ，Ｂ，Ｃ，Ｄ｝であり、終端文字の集合がΣ＝｛０，１｝であり、開始文字がｓ＝Ｓである。また、この文脈自由文法は、生成規則が、Ｓ→ＡＢ、Ｓ→ＢＡ、Ａ→ＣＢ、Ｂ→ＤＣ、Ｃ→０、Ｄ→１、Ａ→ε、Ｂ→εである。なお、εは、空文字（即ち、何ら文字が存在しないこと）を表す。
【００１８】
図２は、サーバ２０が保持する文脈自由文法の生成規則の一例を示す。文脈自由文法における生成規則は、矢印の左側の記号（左辺）が置換記号を表し、矢印の右側の記号（右辺）が被置換記号列を表す。すなわち、文脈自由文法における生成規則は、左辺の置換記号により示された文字が、右辺の被置換記号列により示された文字列に置き換えられることを示す。
【００１９】
本実施形態においては、サーバ２０は、生成規則がチョムスキー標準型で表された文脈自由文法を保持する。即ち、本実施形態においては、空文字εを含まない生成規則は、Ｘ→ＹＺまたはＸ→ａという形式に変換されている。ここで、Ｘ，Ｙ，Ｚは、任意の非終端文字を表し、ａは任意の終端文字を表す。なお、サーバ２０は、生成規則がチョムスキー標準型ではない文脈自由文法を取得した場合には、生成規則をチョムスキー標準型に変換してもよい。
【００２０】
図３は、本実施形態に係るサーバ２０の機能ブロック構成およびクライアント３０の機能ブロック構成を示す。サーバ２０は、状態受信部４２と、文脈自由文法記憶部４４と、展開部４６と、左辺処理部４８と、右辺処理部５０と、開始文字処理部５２と、送信部５４とを備える。クライアント３０は、オートマトン生成部６２と、オートマトン記憶部６４と、状態送信部６６と、初期エッジ生成部６８と、エッジ集合記憶部７０と、エッジペア生成部７２と、終了エッジ抽出部７４と、受信部７６と、追加部７８とを備える。
【００２１】
オートマトン生成部６２は、外部から文字列を入力する。オートマトン生成部６２は、入力した文字列を表すオートマトンを生成する。なお、オートマトン生成部６２は、文字列に代えて、オートマトンを直接入力してもよい。オートマトン記憶部６４は、オートマトン生成部６２により生成されたオートマトンを記憶する。
【００２２】
状態送信部６６は、オートマトン記憶部６４により記憶されたオートマトンの各状態を、サーバ２０の状態受信部４２に送信する。なお、ここで、状態を送信するとは、状態を識別するためのインデックスを送信することをいう。状態送信部６６は、当該クライアント３０が文字列を表すオートマトン（一直線のオートマトン）を保持する場合には、オートマトンの状態数を送信してもよい。
【００２３】
初期エッジ生成部６８は、オートマトン記憶部６４により記憶されたオートマトンにおける複数の状態遷移のそれぞれに対応して、前状態、後状態および入力文字の組を表す初期エッジを生成する。
【００２４】
エッジ集合記憶部７０は、オートマトンにおける状態遷移を表す複数のエッジを含むエッジ集合を記憶する。なお、エッジ集合は、初期エッジ生成部６８により生成された複数の初期エッジを予め含む。また、エッジ集合には、前状態、後状態および暗号化値の組を表す新たなエッジが追加部７８により追加される。なお、暗号化値は、前状態及び後状態に対応付けて非終端文字を暗号化した値であり、サーバ２０により生成される。
【００２５】
エッジペア生成部７２は、エッジ集合記憶部７０に記憶されたエッジ集合から連続遷移可能な複数のエッジを選択する。そして、エッジペア生成部７２は、抽出した複数のエッジのそれぞれに含まれる暗号化値の列を表すエッジペアを生成する。エッジペアは、一例として、２つの暗号化値を関数に代入して算出されたスカラー値である。
【００２６】
終了エッジ抽出部７４は、エッジ集合記憶部７０に記憶されたエッジ集合に含まれる複数のエッジのうち、オートマトンにおける開始状態から終了状態への遷移を表すエッジを、終了エッジとして抽出する。
【００２７】
状態受信部４２は、クライアント３０が保持するオートマトンの状態を状態送信部６６から受信する。状態受信部４２は、当該クライアント３０が文字列を表す一直線のオートマトンを保持する場合、オートマトンの状態数を受信してもよい。状態受信部４２は、オートマトンの状態数を受信した場合には、状態数からオートマトンの各状態を識別するためのインデックス値を生成する。
【００２８】
文脈自由文法記憶部４４は、文脈自由文法を記憶する。文脈自由文法記憶部４４は、外部から文脈自由文法を取り込んでもよい。
【００２９】
展開部４６は、文脈自由文法における複数の生成規則のそれぞれを、オートマトンの複数の状態に基づき定まる遷移パターンに対応して複数に展開する。そして、展開部４６は、展開したそれぞれの生成規則に含まれる非終端文字に対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。
【００３０】
さらに、展開部４６は、文脈自由文法における開始文字を抽出し、抽出した開始文字をオートマトンの状態に基づき定まる複数の遷移パターンに応じて複数に展開する。そして、展開部４６は、展開したそれぞれの開始文字に対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。
【００３１】
左辺処理部４８は、展開部４６により展開後の複数の生成規則のそれぞれについて、割り当てられた前状態及び後状態に対応付けて置換記号（非終端文字）を、予め定められた方式で暗号化した暗号化値を生成する。なお、左辺処理部４８は、同一の前状態、同一の後状態および同一の置換記号（非終端文字）を入力した場合には、同一の暗号化値を出力する方式により暗号化処理を実行する。左辺処理部４８は、一例として、前状態、後状態および置換記号（非終端文字）を、予め定められた一方向関数の変数に代入して、暗号化値を生成する。
【００３２】
右辺処理部５０は、展開部４６により展開後の複数の生成規則のそれぞれについて、被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値を生成する。なお、右辺処理部５０は、左辺処理部４８と同一の方式で、非終端文字を暗号化する。なお、暗号化文字列値は、一例として、２つの暗号化値を関数に代入して算出されたスカラー値である。
【００３３】
開始文字処理部５２は、展開部４６により展開後の複数の開始文字（非終端文字）のそれぞれを、割り当てられた前状態及び後状態に対応付けて開始文字を暗号化した暗号化開始文字を生成する。なお、開始文字処理部５２は、左辺処理部４８及び右辺処理部５０と同一の方式で、非終端文字である開始文字を暗号化する。
【００３４】
送信部５４および受信部７６は、ネットワークを介した通信を実行する。送信部５４および受信部７６は、エッジペア生成部７２により生成された少なくとも１つのエッジペアと、右辺処理部５０により生成された複数の暗号化文字列値のそれぞれとを比較する。そして、送信部５４および受信部７６は、暗号化文字列値がエッジペアと一致する展開後の生成規則を検出する。
【００３５】
この場合において、送信部５４および受信部７６は、秘匿共通集合計算プロトコルにより、クライアント３０に対して複数の暗号化文字列値を秘匿し、且つ、サーバ２０に対してエッジペアを秘匿した状態で比較を実行する。秘匿共通集合計算プロトコルについては、例えば、非特許文献１に記載がある。
【００３６】
送信部５４は、暗号化文字列値がエッジペアと一致する展開後の生成規則を検出した場合、暗号化文字列値がエッジペアと一致した展開後の生成規則の置換記号を暗号化した暗号化値（即ち、左辺処理部４８により生成された暗号化値）を、当該置換記号に割り当てられた前状態および後状態とともにクライアント３０に送信する。
【００３７】
受信部７６は、暗号化文字列値がエッジペアと一致する展開後の生成規則を検出した場合、サーバ２０から送信された暗号化値を、前状態および後状態とともに受信する。追加部７８は、受信部７６が受信した前状態、後状態および暗号化値の組を、新たなエッジとしてエッジ集合記憶部７０に記憶されたエッジ集合に追加する。
【００３８】
また、エッジペア生成部７２は、追加部７８が新たなエッジをエッジ集合に追加した場合、再度、追加された新たなエッジを含んだ連続遷移可能な複数のエッジを選択する。そして、エッジペア生成部７２は、選択した複数のエッジに含まれる暗号化値の列を表す新たなエッジペアを生成する。
【００３９】
送信部５４および受信部７６は、追加部７８が新たなエッジをエッジ集合に追加した場合、再度、新たなエッジペアと展開後の複数の生成規則のそれぞれに対応する暗号化文字列値とを比較して、暗号化文字列値が新たなエッジペアと一致する展開後の生成規則を検出する。この場合にも、送信部５４および受信部７６は、秘匿共通集合計算プロトコルにより、新たなエッジペアと複数の暗号化文字列値とを比較する。
【００４０】
送信部５４は、再度、暗号化文字列値が新たなエッジペアと一致する展開後の生成規則を検出した場合には、暗号化文字列値が新たなエッジペアと一致した展開後の生成規則の置換記号を暗号化した暗号化値を、当該置換記号に割り当てられた前状態および後状態とともにクライアント３０に送信する。
【００４１】
受信部７６は、暗号化文字列値が新たなエッジペアと一致する展開後の生成規則を検出した場合、サーバ２０から送信された暗号化値を、前状態および後状態とともに受信する。追加部７８は、サーバ２０から受信した前状態、後状態および暗号化値の組を、新たなエッジとしてエッジ集合記憶部７０に記憶されたエッジ集合に追加する。そして、送信部５４および受信部７６は、エッジ集合に追加すべき新たなエッジが無くなるまで、新たなエッジペアと複数の暗号化文字列値との比較を繰り返す。
【００４２】
エッジ集合に追加すべき新たなエッジが無くなった場合、送信部５４および受信部７６は、終了エッジ抽出部７４により抽出された終了エッジに含まれる暗号化値と、開始文字処理部５２により生成された複数の暗号化開始文字のそれぞれとを比較する。この場合においても、送信部５４および受信部７６は、秘匿共通集合計算プロトコルにより、クライアント３０に対して複数の暗号化開始文字を秘匿し、且つ、サーバ２０に対して終了エッジに含まれる暗号化値を秘匿した状態で比較を実行する。
【００４３】
そして、受信部７６は、終了エッジに含まれる暗号化値と暗号化開始文字とが一致した場合に、オートマトンが文脈自由文法を満たすと判定する。また、受信部７６は、終了エッジに含まれる暗号化値と暗号化開始文字とが一致しなかった場合に、オートマトンが文脈自由文法を満たさない判定する。
【００４４】
以上のような構成により、認証システム１０は、サーバ２０により保持される文脈自由文法をクライアント３０に対して秘匿し且つクライアント３０により保持されるオートマトンをサーバ２０に対して秘匿した状態で、オートマトンが文脈自由文法を満たすか否かを判定することができる。
【００４５】
図４は、本実施形態に係る認証システム１０の全体処理フローを示す。認証システム１０は、以下のステップＳ１０からステップＳ５０の処理を順次に実行する。
【００４６】
まず、ステップＳ１０において、認証システム１０は、事前処理を実行する。より具体的には、認証システム１０は、オートマトンの生成、文脈自由文法の取得、および、初期エッジの生成等を実行する。事前処理については、図５〜図７を参照して詳細を後述する。
【００４７】
続いて、ステップＳ２０において、認証システム１０は、空文字処理を実行する。より具体的には、認証システム１０は、被置換記号列が空文字である生成規則に対応するエッジを生成し、生成したエッジをエッジ集合に追加する。空文字処理については、図８〜図１２を参照して詳細を後述する。
【００４８】
続いて、ステップＳ３０において、認証システム１０は、終端文字処理を実行する。より具体的には、認証システム１０は、被置換記号列が終端文字である生成規則に対応するエッジを生成し、生成したエッジを初期エッジに対応した遷移としてエッジ集合に追加する。終端文字処理については、図１３〜図１８を参照して詳細を後述する。
【００４９】
続いて、ステップＳ４０において、認証システム１０は、非終端文字処理を実行する。より具体的には、認証システム１０は、被置換記号列が複数の非終端文字の列である複数の生成規則のそれぞれについて、被置換記号列に含まれる非終端文字を暗号化した複数の暗号化値の列を表す値（暗号化文字列値）を、置換記号（非終端文字）を暗号化した暗号化値に置換する置換ルールを生成する。
【００５０】
更にステップＳ４０において、認証システム１０は、エッジ集合から抽出した複数のエッジに含まれる暗号化値の列（エッジペア）が、何れかの置換ルールにおける暗号化文字列値に一致するか否かを、秘匿共通集合計算プロトコルにより判定する。認証システム１０は、エッジ集合から抽出した複数のエッジに含まれる暗号化値の列を表す値（エッジペア）が、何れかの置換ルールにおける暗号化文字列値に一致する場合には、当該置換ルールの置換記号（非終端文字）を暗号化した暗号化値を、新たなエッジとしてエッジ集合に追加する。
【００５１】
そして、認証システム１０は、新たなエッジをエッジ集合に追加する処理を、新たなエッジが追加されなくなるまで繰り返して実行する。なお、非終端文字処理については、図１９〜図２７を参照して詳細を後述する。
【００５２】
続いて、ステップＳ５０において、認証システム１０は、判定処理を実行する。より具体的には、認証システム１０は、オートマトンの複数の状態に基づき定まる遷移パターンに対応付けて開始文字を暗号化した暗号化開始文字を生成する。次に、認証システム１０は、エッジ集合から抽出した終了エッジ（開始状態から終了状態への遷移を表すエッジ）に含まれる暗号化値が、暗号化開始文字に一致するか否かを、秘匿共通集合計算プロトコルにより判定する。
【００５３】
そして、認証システム１０は、終了エッジに含まれる暗号化値が暗号化開始文字に一致する場合には、オートマトンが文脈自由文法を満たすと判定する。なお、判定処理については、図２８〜図３０を参照して詳細を後述する。
【００５４】
図５は、事前処理（Ｓ１０）のフローを示す。図６は、文字列"０１０"を入力した場合に生成されるオートマトンの一例を示す。図７は、初期エッジの一例を示す。
【００５５】
認証システム１０は、事前処理（Ｓ１０）において、以下のステップＳ１１からステップＳ１５の処理を実行する。まず、ステップＳ１１において、サーバ２０は、文脈自由文法を取得する。
【００５６】
続いて、ステップＳ１２において、クライアント３０は、文字列を入力する。続いて、ステップＳ１３において、クライアント３０は、入力した文字列をオートマトンに変換する。本例においては、クライアント３０は、文字列"０１０"を入力して、図６に示されるような一直線の状態遷移図で表されるオートマトンを生成する。なお、クライアント３０は、文字列に代えて、オートマトンを直接入力してもよい。
【００５７】
続いて、ステップＳ１４において、クライアント３０は、オートマトンの各状態遷移に対応した初期エッジを生成する。初期エッジは、オートマトンの状態遷移における、前状態、後状態および入力文字の組を表す。本例においては、クライアント３０は、図７に示されるような、３個の初期エッジを生成する。
【００５８】
続いて、ステップＳ１５において、クライアント３０は、オートマトンの複数の状態のそれぞれをサーバ２０に送信する。この場合において、クライアント３０は、各状態を識別するためのインデックスをサーバ２０に送信する。本例においては、クライアント３０は、インデックスとしてｑ０，ｑ１，ｑ２，ｑ３を送信する。
【００５９】
なお、文字列をオートマトンに変換した場合には一直線のオートマトンとなるので、クライアント３０は、オートマトンの状態を識別するためのインデックスに代えて、オートマトンの状態の個数を送信してもよい。この場合、サーバ２０は、受信したオートマトンの状態の個数に基づき、オートマトンの各状態を識別するインデックスを生成する。
【００６０】
図８は、空文字処理（Ｓ２０）のフローを示す。図９は、ステップＳ２１の処理一例を示す。図１０は、ステップＳ２２およびステップＳ２３の処理の一例を示す。図１１は、ステップＳ２４の処理の一例を示す。図１２は、ステップＳ２５においてエッジ集合に追加されたエッジの一例を示す。
【００６１】
認証システム１０は、空文字処理（Ｓ２０）として、以下のステップＳ２１からステップＳ２５の処理を実行する。
【００６２】
まず、ステップＳ２１において、サーバ２０は、文脈自由文法における複数の生成規則のうち、被置換記号列が空文字である生成規則を抽出する。本例においては、図９に示されるように、文脈自由文法における生成規則の集合から"Ａ→ε"及び"Ｂ→ε"を抽出する。
【００６３】
続いて、ステップＳ２２において、サーバ２０は、抽出した生成規則（被置換記号列が空文字である生成規則）をオートマトンの各状態に対応して展開する。ここで、生成規則を展開するとは、抽出した生成規則をコピーして複数個生成することに相当する。従って、ステップＳ２２では、サーバ２０は、オートマトンの複数の状態のそれぞれに対応して、生成規則をコピーする。
【００６４】
さらに、サーバ２０は、展開したそれぞれの生成規則の置換記号（即ち、非終端文字）対して、同一の前状態および後状態を割り当てる。即ち、サーバ２０は、展開したそれぞれの生成記号の置換記号（即ち、非終端文字）に対して、前状態として対応する状態を割り当てて、後状態として前状態と同一の状態を割り当てる。
【００６５】
なお、置換記号（または非終端文字）に対して状態を割り当てるとは、オートマトンの状態を識別するためのインデックスを、その置換記号（または非終端文字）に関連付けることをいう。従って、サーバ２０は、置換記号（または非終端文字）に対して前状態および後状態を割り当てることにより、前状態、後状態および置換記号（または非終端文字）の組を生成することができる。
【００６６】
本例においては、図１０に示されるように、サーバ２０は、"Ａ→ε"及び"Ｂ→ε"のそれぞれを、オートマトンの４つの状態のそれぞれに対応して展開する。そして、サーバ２０は、４つの"Ａ→ε"及び４の"Ｂ→ε"のそれぞれに、（ｑ０、ｑ０）、（ｑ１、ｑ１）、（ｑ２、ｑ２）、（ｑ３、ｑ３）の前状態及び後状態の組を割り当てる。
【００６７】
続いて、ステップＳ２３において、サーバ２０は、展開した生成規則（被置換記号列が空文字である生成規則）の置換記号（非終端文字）を、割り当てられた前状態および後状態に対応付けて予め定められた暗号化方式で暗号化する。なお、任意の前状態ｑｉ、任意の後状態ｑｊ、及び、任意の非終端文字Ｘを暗号化した暗号化値は、下記のように示される。
【数１】
2013246294.tif 000003
【００６８】
この暗号化方式は、同一の前状態、同一の後状態および同一の置換記号（非終端文字）を入力した場合には、同一の暗号化値を出力する方式である。本実施形態においては、サーバ２０は、予め定められた一方向関数の変数に、前状態を識別するインデックス、後状態を識別するインデックス、および、非終端文字を入力することにより暗号化値を生成する。本例においては、図１０に示されるように、サーバ２０は、Ａ→ε"の置換記号（非終端文字Ａ）およびＢ→ε"の置換記号（非終端文字Ｂ）のそれぞれを、割り当てられた前状態および後状態に対応付けて暗号化する。
【００６９】
続いて、ステップＳ２４において、サーバ２０は、被置換記号列が空文字である生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともにクライアント３０に送信する。そして、クライアント３０は、サーバ２０から送信された、前状態、後状態および暗号化値の組を受信する。本例においては、図１１に示されるように、サーバ２０は、８個分の前状態、後状態および暗号化値の組をクライアント３０へと送信する。
【００７０】
続いて、ステップＳ２５において、クライアント３０は、受信した前状態、後状態および暗号化値の組を新たなエッジとしてエッジ集合に追加する。本例においては、図１２に示されるように、クライアント３０は、３つの初期エッジを予め含むエッジ集合に対して、８個分の前状態、後状態および暗号化値の組を新たなエッジとして追加する。
【００７１】
以上のステップＳ２１からステップＳ２５の処理を実行することにより、認証システム１０は、被置換記号列が空文字である生成規則に対応するエッジを生成し、生成したエッジをエッジ集合に追加することができる。
【００７２】
図１３は、終端文字処理（Ｓ３０）のフローを示す。図１４は、ステップＳ３１の処理の一例を示す。図１５は、ステップＳ３２およびステップＳ３３の処理の一例を示す。図１６は、ステップＳ３４の比較処理の一例を示す。図１７は、ステップＳ３４の送信処理の一例を示す。図１８は、ステップＳ３５においてエッジ集合に追加されたエッジの一例を示す。
【００７３】
認証システム１０は、終端文字処理（Ｓ３０）として、以下のステップＳ３１からステップＳ３５の処理を実行する。
【００７４】
まず、ステップＳ３１において、サーバ２０は、文脈自由文法における複数の生成規則のうち被置換記号列が終端文字である生成規則を抽出する。本例においては、図１４に示されるように、文脈自由文法における生成規則の集合から"Ｃ→０"及び"Ｄ→１"を抽出する。
【００７５】
続いて、ステップＳ３２において、サーバ２０は、抽出した生成規則（被置換記号列が終端文字である生成規則）をオートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開する。例えばＮ個（Ｎは２以上の自然数）の状態を含むオートマトンに対してある任意の文字が入力された場合、そのオートマトンにおける状態遷移の遷移パターンは、Ｎ×Ｎ個分存在する。そこで、オートマトンがＮ個の状態を有する場合には、サーバ２０は、抽出した複数の生成規則のそれぞれを、Ｎ×Ｎ個の遷移パターンのそれぞれに対応させて展開する。
【００７６】
さらに、サーバ２０は、展開したそれぞれの生成規則の置換記号（即ち、非終端文字）対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。即ち、サーバ２０は、展開したそれぞれの生成記号の置換記号（即ち、非終端文字）に対して、前状態として、対応する遷移パターンの遷移元の状態を割り当て、後状態として、対応する遷移パターンの遷移先の状態を割り当てる。
【００７７】
本例においては、図１５に示されるように、サーバ２０は、"Ｃ→０"の生成規則の置換記号（非終端文字Ｃ）を１６個に展開して、展開後の１６個の生成規則のそれぞれに遷移パターンに従った前状態および後状態を割り当てる。なお、サーバ２０は、他の生成規則（例えば"Ｄ→１"）についても展開処理および前状態および後状態の割り当て処理を実行するが図示は省略する。
【００７８】
続いて、ステップＳ３３において、サーバ２０は、展開した生成規則（被置換記号列が非終端文字である生成規則）の置換記号（非終端文字）を、割り当てられた前状態および後状態に対応付けて予め定められた暗号化方式で暗号化する。なお、ここでは、サーバ２０は、ステップＳ２３で実行した暗号化方式と同一の暗号化方式で、置換記号（非終端文字）を暗号化して暗号化値を生成する。
【００７９】
本例においては、図１５に示されるように、サーバ２０は、"Ｃ→０"の置換記号（非終端文字Ｃ）を、割り当てられた前状態および後状態に対応付けて暗号化する。なお、サーバ２０は、他の生成規則（例えば"Ｄ→１"）についても暗号化処理を実行するが図示は省略する。
【００８０】
続いて、ステップＳ３４において、サーバ２０およびクライアント３０は、サーバ２０が記憶する展開後の生成規則（被置換記号列が終端文字の生成規則）と、クライアント３０が記憶するエッジ集合に含まれる初期エッジとを、秘匿共通集合計算プロトコルにより相互に通信をして比較する。
【００８１】
より具体的には、サーバ２０およびクライアント３０は、初期エッジに含まれる入力文字と展開後の生成規則の終端文字とが一致するか否かを判定する。これとともに、サーバ２０およびクライアント３０は、初期エッジに含まれる前状態及び後状態と、展開後の生成規則の置換記号に割り当てられた前状態及び後状態とが一致するか否かを判定する。本例においては、図１６に示されるように、サーバ２０およびクライアント３０は、初期エッジに含まれる前状態、後状態および入力状態の組と、展開後の生成規則の前状態、後状態および非終端文字の組とが完全に一致するか否かを判定する。
【００８２】
そして、サーバ２０は、終端文字が何れかの初期エッジに含まれる入力文字に一致し、且つ、置換記号に割り当てられた前状態および後状態が当該初期エッジに含まれる前状態および後状態に一致した生成規則の置換記号を暗号化した暗号化値（即ち、ステップＳ３３で生成した暗号化値）を、割り当てられた前状態および後状態とともにクライアント３０に送信する。そして、クライアント３０は、サーバ２０から送信された、前状態、後状態および暗号化値の組を受信する。本例においては、図１７に示されるように、サーバ２０は、３つの初期エッジのそれぞれに一致する、前状態、後状態および暗号化値の組をクライアント３０へと送信する。
【００８３】
なお、この場合において、サーバ２０およびクライアント３０は、初期エッジをサーバ２０に対して秘匿して比較および暗号化値等の受け渡しを行う。本実施形態においては、サーバ２０およびクライアント３０は、秘匿共通集合計算プロトコルを利用して秘匿化して通信を行う。
【００８４】
続いて、ステップＳ３５において、クライアント３０は、受信した前状態、後状態および暗号化値の組を新たなエッジとしてエッジ集合に追加する。本例においては、図１８に示されるように、クライアント３０は、３つの初期エッジおよび空文字に対応するエッジを含むエッジ集合に対して、３つの新たなエッジを追加する。
【００８５】
以上のステップＳ３１からステップＳ３５の処理を実行することにより、認証システム１０は、被置換記号列が終端文字である生成規則に対応するエッジを生成し、生成したエッジを初期エッジに対応した遷移としてエッジ集合に追加することができる。
【００８６】
図１９は、非終端文字処理（Ｓ４０）のフローを示す。図２０は、ステップＳ４１の処理の一例を示す。図２１は、ステップＳ４２の処理の一例を示す。図２２は、ステップＳ４４の処理の一例を示す。図２３は、ステップ４５の選択処理の一例を示す。図２４は、ステップＳ４５のスカラー値化の処理の一例を示す。図２５、図２６及び図２７は、エッジ集合に追加されたエッジの一例を示す。
【００８７】
認証システム１０は、非終端文字処理（Ｓ４０）として、以下のステップＳ４１からステップＳ４８の処理を実行する。
【００８８】
まず、ステップＳ４１において、サーバ２０は、文脈自由文法における複数の生成規則のうち被置換記号列が２つの非終端文字の列である生成規則を抽出する。本例においては、図２０に示されるように、文脈自由文法における生成規則の集合から、"Ｓ→ＡＢ"、"Ｓ→ＢＡ"、"Ａ→ＣＢ"及び"Ｂ→ＤＣ"を抽出する。
【００８９】
続いて、ステップＳ４２において、サーバ２０は、抽出した生成規則をオートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開する。さらに、サーバ２０は、展開したそれぞれの生成規則に含まれる非終端文字のそれぞれに対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。
【００９０】
ここで、サーバ２０は、生成規則の置換記号（左辺）と被置換記号列（右辺）とを矛盾無く相互に置き換えることができるような遷移パターンを対応付ける。例えば、サーバ２０は、"Ｘ→ＹＺ"という生成規則の各非終端文字に対して、下式に示されるように前状態および後状態を割り当てる。なお、Ｘ，Ｙ，Ｚは、任意の非終端文字を表す。
【数２】
2013246294.tif 000004
【００９１】
即ち、サーバ２０は、置換記号（非終端文字Ｘ）の前状態と、被置換記号列の１番目の非終端文字Ｙの前状態とを同一とするような遷移パターンを対応付ける。更に、サーバ２０は、置換記号（非終端文字Ｘ）の後状態と、被置換記号列の２番目の非終端文字Ｚの後状態とを同一とするような遷移パターンを対応付ける。また、更に、サーバ２０は、被置換記号列の１番目の非終端文字Ｙの後状態と、被置換記号列の２番目の非終端文字Ｚの前状態とを同一とするような遷移パターンを対応付ける。
【００９２】
サーバ２０は、オートマトンの複数の状態に基づき、このような遷移パターンを全てに対応させて各生成規則を展開する。そして、サーバ２０は、置換記号、被置換記号列の１番目の非終端文字、および、被置換記号列の２番目の非終端文字のそれぞれに対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。
【００９３】
本例においては、図２１に示されるように、サーバ２０は、"Ｂ→ＤＣ"の生成規則の置換記号に対しては、２４個の生成規則に展開して、３つの非終端文字のそれぞれに前状態および後状態を割り当てる。なお、サーバ２０は、他の生成規則についても展開処理および前状態および後状態の割り当て処理を実行するが図示は省略する。
【００９４】
続いて、ステップＳ４３において、サーバ２０は、展開した生成規則（被置換記号列が２つの非終端文字の列である生成規則）の置換記号（非終端文字）を、割り当てられた前状態および後状態に対応付けて予め定められた暗号化方式で暗号化する。なお、ここでは、サーバ２０は、ステップＳ２３およびステップＳ３３で実行した暗号化方式と同一の暗号化方式で暗号化して、暗号化値を生成する。
【００９５】
続いて、ステップＳ４４において、サーバ２０は、展開した生成規則（被置換記号列が２つの非終端文字の列である生成規則）の被置換記号列の２つの非終端文字のそれぞれを、割り当てられた前状態および後状態に対応付けて暗号化する。なお、ここでは、サーバ２０は、それぞれの非終端文字を、ステップＳ４３で実行した暗号化方式と同一の暗号化方式で暗号化して、暗号化値を生成する。
【００９６】
さらに、サーバ２０は、展開後の複数の生成規則のそれぞれについて、被置換記号列に含まれる複数の非終端文字のそれぞれを割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値の列を表す暗号化文字列値を生成する。暗号化文字列値は、一例として、２つの非終端文字のそれぞれの暗号化値を関数に代入して算出されたスカラー値である。
【００９７】
例えば、サーバ２０は、５つの変数ｑｉ，ｑｋ，ｑｊ，Ｙ［ｑｉ，ｑｋ］，Ｚ［ｑｋ，ｑｊ］に基づき、下記の式（１１）に示されるような関数Ｄｇ（）により、スカラー値化した暗号化文字列値を生成する。
【数３】
2013246294.tif 000005
【００９８】
なお、ここで、ｑｉは、被置換記号列の１番目の非終端文字に割り当てられた前状態のインデックスを表す。ｑｋは、被置換記号列の１番目の非終端文字に割り当てられた後状態のインデックス（即ち、２番目の非終端文字に割り当てられた前状態のインデックス）を表す。ｑｊは、被置換記号列の２番目の非終端文字に割り当てられた後状態のインデックスを表す。
【００９９】
Ｙ［ｑｉ，ｑｋ］は、被置換記号列の１番目の非終端文字を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を表す。Ｚ［ｑｋ，ｑｊ］は、被置換記号列の２番目の非終端文字を割り当てられた前状態及び後状態に対応付けて暗号化した暗号化値を表す。
【０１００】
本例においては、図２２に示されるように、サーバ２０は、"Ｂ→ＤＣ"の生成規則の置換記号に対しては、２４個の展開後の生成規則のそれぞれに対応して、関数Ｄ＿ｇ（）を用いて暗号化文字列値を生成する。なお、サーバ２０は、他の生成規則についても展開処理および前状態および後状態の割り当て処理を実行するが図示は省略する。
【０１０１】
続いて、ステップＳ４５において、クライアント３０は、エッジ集合に含まれる複数のエッジから、連続遷移可能な２つのエッジを選択する。即ち、クライアント３０は、先頭のエッジの後状態と後方のエッジの前状態とが一致するような２つのエッジを選択する。なお、この場合において、クライアント３０は、エッジ集合に含まれる初期エッジを除いてエッジを選択する。
【０１０２】
そして、クライアント３０は、選択した２つのエッジのそれぞれに含まれる暗号化値の列を表すエッジペアを生成する。本例においては、図２３に示されるように、クライアント３０は、終端文字処理（Ｓ３０）が終了した段階のエッジ集合から、２０個のエッジペアを生成する。
【０１０３】
エッジペアは、一例として、選択した２つのエッジのそれぞれに含まれる暗号化値を関数に代入して算出したスカラー値である。例えば、クライアント３０は、５つの変数ｑｉ，ｑｋ，ｑｊ，Ｙ［ｑｉ，ｑｋ］，Ｚ［ｑｋ，ｑｊ］に基づき、下記の式（１２）に示されるような関数Ｄ＿ａ（）により、エッジペアを生成する。
【０１０４】
【数４】
2013246294.tif 000006
【０１０５】
なお、ここで、式（１２）に示される関数Ｄ＿ａ（）は、式（１１）において示した関数Ｄ＿ｇ（）と同一である。また、式（１２）においては、ｑｉは、選択した２つのエッジのうち先頭のエッジに含まれる前状態のインデックスを表す。ｑｋは、選択した２つのエッジのうち先頭のエッジに含まれる後状態のインデックス（即ち、選択した２つのエッジのうち後方のエッジの前状態のインデックス）を表す。ｑｊは、選択した２つのエッジのうち後方のエッジの後状態のインデックスを表す。
【０１０６】
また、Ｙ［ｑｉ，ｑｋ］は、選択した２つのエッジのうち先頭のエッジに含まれる暗号化値を表す。Ｚ［ｑｋ，ｑｊ］は、選択した２つのエッジのうち後方のエッジに含まれる暗号化値を表す。本例においては、図２４に示されるように、クライアント３０は、３つの状態および２つの暗号化値から、スカラー値化したエッジペアを生成する。
【０１０７】
続いて、ステップＳ４６において、サーバ２０およびクライアント３０は、サーバ２０が記憶する複数の暗号化文字列値のそれぞれとクライアント３０が記憶する複数のエッジペアのそれぞれとを、秘匿共通集合計算プロトコルを利用して通信を行って比較する。即ち、サーバ２０およびクライアント３０は、複数の暗号化文字列値をクライアント３０に対して秘匿し且つ複数のエッジペアをサーバ２０に対して秘匿した状態で、複数の暗号化文字列値のそれぞれと複数のエッジペアのそれぞれとを比較する。
【０１０８】
そして、サーバ２０は、暗号化文字列値が何れかのエッジペアと一致した生成規則が存在する場合、暗号化文字列値が何れかのエッジペアと一致した生成規則の置換記号を暗号化した暗号化値（即ち、ステップＳ４３で生成した暗号化値）を、割り当てられた前状態および後状態とともにクライアント３０に送信する。また、クライアント３０は、サーバ２０から送信された、前状態、後状態および暗号化値の組を受信する。
【０１０９】
続いて、ステップＳ４７において、クライアント３０は、何れかの暗号化文字列値が何れかのエッジペアと一致したか否かを判定する。何れの暗号化文字列値も何れのエッジペアと一致しなかった場合（ステップＳ４７のＮｏ）、クライアント３０は、非終端文字処理（Ｓ４０）を終了する。
【０１１０】
クライアント３０は、何れかの暗号化文字列値が何れかのエッジペアと一致した場合（ステップＳ４７のＹｅｓ）、処理をステップＳ４８に進める。続いて、ステップＳ４８において、クライアント３０は、受信した前状態、後状態および暗号化値の組を新たなエッジとしてエッジ集合に追加する。
【０１１１】
続いて、クライアント３０は、処理をステップＳ４５に戻す。クライアント３０は、処理が戻させると、ステップＳ４５において、再度、追加された新たなエッジを含んだ連続遷移可能な複数のエッジを選択する。そして、クライアント３０は、選択した複数のエッジに含まれる暗号化値の列を表す新たなエッジペアを生成する。
【０１１２】
続いて、ステップＳ４６において、サーバ２０およびクライアント３０は、再度、新たなエッジペアと複数の暗号化文字列値のそれぞれとを、秘匿共通集合計算プロトコルを利用して通信を行って比較する。サーバ２０は、暗号化文字列値が新たなエッジペアと一致した生成規則が存在する場合、暗号化文字列値が何れかのエッジペアと一致した生成規則の置換記号を暗号化した暗号化値を、割り当てられた前状態および後状態とともにクライアント３０に送信する。そして、サーバ２０およびクライアント３０は、エッジ集合に追加すべき新たなエッジが無くなるまで、ステップＳ４５〜ステップＳ４８のループ処理を繰り返す。
【０１１３】
本例においては、図２５に示されるように、１回目のループ処理において、クライアント３０は、エッジペア（Ｄ［ｑ１，ｑ２］Ｃ［ｑ２，ｑ３］）に対応する暗号化値Ｂ［ｑ１，ｑ３］をサーバ２０から受信して、新たなエッジとして追加する。次に、図２６に示されるように、２回目のループ処理において、クライアント３０は、エッジペア（Ｃ［ｑ０，ｑ１］Ｂ［ｑ１，ｑ３］）に対応する暗号化値Ａ［ｑ０，ｑ３］をサーバ２０から受信して、新たなエッジとして追加する。最後に、図２７に示されるように、３回目のループ処理において、クライアント３０は、エッジペア（Ｂ［ｑ０，ｑ０］Ａ［ｑ０，ｑ３］）に対応する暗号化値Ｓ［ｑ０，ｑ３］をサーバ２０から受信して、新たなエッジとして追加する。
【０１１４】
そして、本例において、サーバ２０およびクライアント３０は、３回目のループ処理が終了した時点で追加すべきエッジが無くなる。従って、サーバ２０およびクライアント３０は、３回目のループ処理が終了した後に、当該非終端文字処理（Ｓ４０）を終了する。
【０１１５】
以上のステップＳ４１からステップＳ４８の処理を実行することにより、認証システム１０は、被置換記号列が複数の非終端文字の列である複数の生成規則のそれぞれについて、暗号化文字列値を暗号化値に置換する置換ルールを生成する。そして、認証システム１０は、秘匿共通集合計算プロトコルにより、エッジペアが何れかの置換ルールにおける暗号化文字列値に一致すると判定する場合には、当該置換ルールの置換記号を暗号化した暗号化値を、新たなエッジとしてエッジ集合に追加することができる。
【０１１６】
図２８は、判定処理（Ｓ５０）のフローを示す。図２９は、ステップＳ５２およびステップＳ５３の処理の一例を示す。図３０は、ステップＳ５６の判定処理の一例を示す。
【０１１７】
認証システム１０は、判定処理（Ｓ５０）として、以下のステップＳ５１からステップＳ５６の処理を実行する。
【０１１８】
まず、ステップＳ５１において、サーバ２０は、文脈自由文法における開始文字を抽出する。本例においては、文脈自由文法から"Ｓ"を開始文字として抽出する。
【０１１９】
続いて、ステップＳ５２において、サーバ２０は、抽出した開始文字をオートマトンの複数の状態に基づき定まる複数の遷移パターンに対応させて展開する。さらに、サーバ２０は、展開したそれぞれの開始文字に対して、対応する遷移パターンに応じた前状態および後状態を割り当てる。即ち、サーバ２０は、展開したそれぞれの開始文字に対して、前状態として、対応する遷移パターンの遷移元の状態を割り当て、後状態として、対応する遷移パターンの遷移先の状態を割り当てる。本例においては、図２９に示されるように、サーバ２０は、"Ｓ"の開始文字に対して１２個の生成規則に展開して前状態および後状態を割り当てる。
【０１２０】
続いて、ステップＳ５３において、サーバ２０は、展開した開始文字を、割り当てられた前状態および後状態に対応付けて予め定められた暗号化方式で暗号化した暗号化開始文字を生成する。なお、ここでは、サーバ２０は、ステップＳ２３およびステップＳ３３等で実行した暗号化方式と同一の暗号化方式で暗号化して、暗号化値を生成する。本例においては、図２９に示されるように、サーバ２０は、開始文字Ｓを、割り当てられた前状態および後状態に対応付けて暗号化する。
【０１２１】
続いて、ステップＳ５４において、クライアント３０は、エッジ集合に含まれる複数のエッジのうちオートマトンにおける開始状態から終了状態への遷移を表すエッジを、終了エッジとして抽出する。本例においては、開始状態がｑ０、終了状態がｑ３であるので、クライアント３０は、終了エッジとして、（ｑ０，ｑ３，Ｓ［ｑ０，ｑ３］）および（ｑ０，ｑ３，Ａ［ｑ０，ｑ３］）を抽出する。
【０１２２】
続いて、ステップＳ５５において、サーバ２０およびクライアント３０は、サーバ２０が記憶する終了エッジに含まれる暗号化値と、クライアント３０が記憶する複数の暗号化開始文字のそれぞれとを、秘匿共通集合計算プロトコルを利用して通信を行って比較する。即ち、サーバ２０およびクライアント３０は、複数の暗号化開始文字をクライアント３０に対して秘匿し且つ終了エッジに含まれる暗号化値をサーバ２０に対して秘匿した状態で、終了エッジに含まれる暗号化値と複数の暗号化開始文字のそれぞれとを比較する。
【０１２３】
続いて、ステップＳ５６において、クライアント３０は、終了エッジに含まれる暗号化値が何れかの暗号化開始文字と一致した場合には（真）、オートマトンが文脈自由文法を満たすと判定する。また、クライアント３０は、終了エッジに含まれる暗号化値が何れの暗号化開始文字とも一致しなかった場合には（偽）、オートマトンが文脈自由文法を満たさないと判定する。本例においては、図３０に示されるように、クライアント３０は、暗号化値Ｓ［ｑ０，ｑ３］が一致するので、オートマトンが文脈自由文法を満たすと判定する。
【０１２４】
以上のような処理により、認証システム１０は、サーバ２０により保持される文脈自由文法をクライアント３０に対して秘匿し且つクライアント３０により保持されるオートマトンをサーバ２０に対して秘匿した状態で、オートマトンが文脈自由文法を満たすか否かを判定することができる。
【０１２５】
図３１は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【０１２６】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【０１２７】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【０１２８】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、及び／又は、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。
【０１２９】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【０１３０】
コンピュータ１９００にインストールされ、コンピュータ１９００を、サーバ２０として機能させるプログラムは、状態受信モジュールと、文脈自由文法記憶モジュールと、展開モジュールと、左辺処理モジュールと、右辺処理モジュールと、開始文字処理モジュールと、送信モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、状態受信部４２、文脈自由文法記憶部４４、展開部４６、左辺処理部４８、右辺処理部５０、開始文字処理部５２および送信部５４としてそれぞれ機能させる。
【０１３１】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である状態受信部４２、文脈自由文法記憶部４４、展開部４６、左辺処理部４８、右辺処理部５０、開始文字処理部５２および送信部５４として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のサーバ２０が構築される。
【０１３２】
コンピュータ１９００にインストールされ、コンピュータ１９００を、クライアント３０として機能させるプログラムは、オートマトン生成モジュールと、オートマトン記憶モジュールと、状態送信モジュールと、初期エッジ生成モジュールと、エッジ集合記憶モジュールと、エッジペア生成モジュールと、終了エッジ抽出モジュールと、受信モジュールと、追加モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、オートマトン生成部６２、オートマトン記憶部６４、状態送信部６６、初期エッジ生成部６８、エッジ集合記憶部７０、エッジペア生成部７２、終了エッジ抽出部７４、受信部７６および追加部７８としてそれぞれ機能させる。
【０１３３】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、オートマトン生成部６２、オートマトン記憶部６４、状態送信部６６、初期エッジ生成部６８、エッジ集合記憶部７０、エッジペア生成部７２、終了エッジ抽出部７４、受信部７６および追加部７８として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のクライアント３０が構築される。
【０１３４】
一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、又はＣＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置又は通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。
【０１３５】
また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０（ＣＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、及び／又は記憶装置に含まれるものとする。
【０１３６】
また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合（又は不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。
【０１３７】
また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。
【０１３８】
以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤ又はＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１３９】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０１４０】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【０１４１】
１０  認証システム
２０  サーバ
３０  クライアント
４２  状態受信部
４４  文脈自由文法記憶部
４６  展開部
４８  左辺処理部
５０  右辺処理部
５２  開始文字処理部
５４  送信部
６２  オートマトン生成部
６４  オートマトン記憶部
６６  状態送信部
６８  初期エッジ生成部
７０  エッジ集合記憶部
７２  エッジペア生成部
７４  終了エッジ抽出部
７６  受信部
７８  追加部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2013246294.tif 000007
【図２】
2013246294.tif 000008
【図３】
2013246294.tif 000009
【図４】
2013246294.tif 000010
【図５】
2013246294.tif 000011
【図６】
2013246294.tif 000012
【図７】
2013246294.tif 000013
【図８】
2013246294.tif 000014
【図９】
2013246294.tif 000015
【図１０】
2013246294.tif 000016
【図１１】
2013246294.tif 000017
【図１２】
2013246294.tif 000018
【図１３】
2013246294.tif 000019
【図１４】
2013246294.tif 000020
【図１５】
2013246294.tif 000021
【図１６】
2013246294.tif 000022
【図１７】
2013246294.tif 000023
【図１８】
2013246294.tif 000024
【図１９】
2013246294.tif 000025
【図２０】
2013246294.tif 000026
【図２１】
2013246294.tif 000027
【図２２】
2013246294.tif 000028
【図２３】
2013246294.tif 000029
【図２４】
2013246294.tif 000030
【図２５】
2013246294.tif 000031
【図２６】
2013246294.tif 000032
【図２７】
2013246294.tif 000033
【図２８】
2013246294.tif 000034
【図２９】
2013246294.tif 000035
【図３０】
2013246294.tif 000036
【図３１】
2013246294.tif 000037