"文字列の入力を受けるクライアントに接続可能なサーバであって、受け取った文字に応じて状態が遷移するオートマトンを有し、前記オートマトンが前記文字列によって最終状態に遷移するかを判定するためのサーバであって、前記文字列に含まれる各文字について、前記文字に対応する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、前記文字に対応する要素以外の要素が前記第1暗号化方式により単位元を暗号化した値とされた暗号配列を前記クライアントから受信し、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して、前記暗号配列に基づいて前記第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化して前記クライアントに送信するサーバ。前記クライアントは、前記オートマトンの複数の前状態のそれぞれに対応した暗号化された複数の前記交換データを、前記サーバから受信し、暗号化された前記複数の交換データのそれぞれを、当該クライアントが記憶する前状態鍵および前記第1暗号化方式により復号し、復号できた1つの後状態鍵を、次の文字に対応して前記サーバから受信する交換データを復号するための前状態鍵として記憶する請求項1に記載のサーバ。前記第1暗号化方式は、同一の平文を暗号化した場合であっても暗号化処理毎に暗号文が異なる方式である請求項2に記載のサーバ。前記第1暗号化方式は、加法準同型性を有する暗号化方式である請求項3に記載のサーバ。前記第1暗号化方式は、拡張エルガマル方式である請求項4に記載のサーバ。前記第1暗号化方式は、乗法準同型性を有する暗号化方式である請求項3に記載のサーバ。前記後状態鍵は、前記オートマトンにおける複数の後状態のそれぞれに対応付けられた乱数である請求項3に記載のサーバ。前記サーバは、前記クライアントから前記暗号配列を受信する受信部と、前記オートマトンにおける複数の前状態のそれぞれに対応して、受信した前記暗号配列の各要素のそれぞれに、当該前状態から当該要素により特定される文字が入力されたことに応じて遷移する後状態に対応する前記後状態鍵を冪乗し、前記後状態鍵を冪乗した複数の要素を前記第1暗号化方式に対応する演算により結合することにより、前記第1暗号化方式により後状態鍵を暗号化した交換データを生成する交換データ生成部と、を有する請求項7に記載のサーバ。前記サーバは、前記文字列の各文字に対応して、前記オートマトンにおける複数の後状態のそれぞれに対応する後状態鍵を発生する鍵発生部と、複数の後状態のそれぞれに対応付けられた前記後状態鍵を、次の文字が入力された場合の複数の前状態のそれぞれに対応する複数の前状態鍵として記憶するサーバ側鍵記憶部と、前記オートマトンにおける複数の前状態のそれぞれに対応して生成された交換データのそれぞれを、対応する前状態鍵により暗号化する暗号化部と、を有する請求項8に記載のサーバ。前記クライアントは、復号した前記後状態鍵を、次の文字に対応して前記サーバから受信する前記複数の交換データを復号するための前記前状態鍵として記憶するクライアント側鍵記憶部を更に有する請求項8に記載のサーバ。前記交換データ生成部は、前状態から遷移した後の状態が前記オートマトンにおける正しい最終状態である場合、前記暗号配列の各要素のそれぞれに対して、前記後状態鍵に代えて受理を意味する値を冪乗し、前記クライアントは、前記交換データから前記受理を意味する値が復号された場合には、前記文字列によって前記オートマトンが正しい最終状態に遷移したと判定する判定部を更に有する請求項8に記載のサーバ。前記クライアントは、前記文字列に含まれる複数の文字のそれぞれに対応する複数の前記暗号配列を並列に前記サーバに送信する請求項1に記載のサーバ。前記サーバは、前記オートマトンの複数の前状態のそれぞれに対応した複数の交換データを、前記複数の文字のそれぞれについて並列に前記クライアントに送信し、前記クライアントは、前記複数の文字のそれぞれについての前記複数の交換データを、先頭の文字に対応する前記複数の交換データから順次に復号する請求項12に記載のサーバ。前記サーバは、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して暗号化した複数の交換データを、前記暗号配列毎に並べ替えて送信する請求項1に記載のサーバ。受け取った文字に応じて状態が遷移するオートマトンを有するサーバと接続可能であって、文字列の入力を受け付けて、前記オートマトンが前記文字列によって最終状態に遷移するかを判定するためのクライアントであって、前記文字列に含まれる各文字について、前記文字に対応する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、前記文字に対応する要素以外の要素が前記第1暗号化方式により単位元を暗号化した値とされた暗号配列を、前記サーバに送信し、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して、前記暗号配列に基づいて前記第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化した暗号文を、前記サーバから受信するクライアント。文字列の入力を受けるクライアントに接続可能なサーバであって、受け取った文字に応じて状態が遷移するオートマトンを有し、前記オートマトンが前記文字列によって最終状態に遷移するかを判定するためのサーバにおける情報処理の方法であって、前記文字列に含まれる各文字について、前記文字に対応する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、前記文字に対応する要素以外の要素が前記第1暗号化方式により単位元を暗号化した値とされた暗号配列を前記クライアントから受信し、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して、前記暗号配列に基づいて前記第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化して前記クライアントに送信する方法。コンピュータを請求項1に記載のサーバとして機能させるためのプログラム。コンピュータを請求項15に記載のクライアントとして機能させるためのプログラム。ところで、クライアントが保有する文字列をサーバに開示せず、且つ、サーバが保有するオートマトンをクライアントに開示せずに、文字列がオートマトンに受理されるか否かを認証することは非常に難しかった。本発明の第1の態様においては、文字列の入力を受けるクライアントに接続可能なサーバであって、受け取った文字に応じて状態が遷移するオートマトンを有し、前記オートマトンが前記文字列によって最終状態に遷移するかを判定するためのサーバであって、前記文字列に含まれる各文字について、前記文字に対応する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、前記文字に対応する要素以外の要素が前記第1暗号化方式により単位元を暗号化した値とされた暗号配列を前記クライアントから受信し、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して、前記暗号配列に基づいて前記第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化して前記クライアントに送信するサーバ、および、このようなサーバにおける情報処理の方法およびプログラムを提供する。本発明の第2の態様においては、受け取った文字に応じて状態が遷移するオートマトンを有するサーバと接続可能であって、文字列の入力を受け付けて、前記オートマトンが前記文字列によって最終状態に遷移するかを判定するためのクライアントであって、前記文字列に含まれる各文字について、前記文字に対応する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、前記文字に対応する要素以外の要素が前記第1暗号化方式により単位元を暗号化した値とされた暗号配列を、前記サーバに送信し、前記暗号配列を受信したことに応じて、前記オートマトンの複数の前状態のそれぞれに対応して、前記暗号配列に基づいて前記第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化した暗号文を、前記サーバから受信するクライアント、および、このようなクライアントにおけるプログラムを提供する。なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。図1は、本実施形態に係る認証システム10の構成を示す。本実施形態に係る認証システム10は、クライアント20と、サーバ30とを備える。本実施形態に係る認証システム10は、クライアント20に入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移するかを判定する。クライアント20は、外部から文字列を入力する。文字列に含まれる文字は、どのような文字であってもよい。例えば文字は、0、1の2値の文字であってもよいし、1バイトで表現される文字であってもよい。サーバ30は、受け取った文字に応じて状態が遷移するオートマトンを有する。オートマトンが受け取る文字は、クライアント20に入力される文字である。オートマトンは、予め登録された文字列の集合文字列群の正規表現を表す。オートマトンは、文字列に含まれる各文字を先頭から順次に受け取り、先頭の文字から1文字ずつ順次に状態を遷移させる。そして、オートマトンは、最後の文字を受け取って遷移した後に、正しい最終状態に遷移していれば受理を出力し、正しい最終状態に遷移していなければ不受理を出力する。クライアント20は、入力された文字列の文字毎に、入力された文字に対応する暗号配列を生成して、サーバ30へと送信する。なお、暗号配列の詳細は後述する。サーバ30は、クライアント20から暗号配列を受信したことに応じて、暗号化された複数の交換データを生成してクライアント20に返信する。なお、交換データの詳細は後述する。クライアント20およびサーバ30は、暗号配列および暗号化された複数の交換データのやり取りを、入力された文字列の文字数分繰り返す。そして、クライアント20は、複数の文字のそれぞれに対応して受信した暗号化された複数の交換データを、先頭の文字から順次に復号する。クライアント20は、最後の文字に対応する交換データまで復号でき且つ最後の文字に対応する交換データから受理を表す値を復号できた場合には、入力された文字列によってオートマトンが正しい最終状態まで遷移したと判定する。このように、本実施形態に係る認証システム10は、クライアント20に入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移するかを判定することができる。図2は、本実施形態に係るクライアント20およびサーバ30のそれぞれの機能ブロック構成を示す。クライアント20は、文字入力部32と、配列化部34と、第1暗号化部36と、クライアント側送信部38と、クライアント側受信部40と、クライアント側鍵記憶部42と、第2復号部44と、第1復号部46と、判定部48とを有する。また、サーバ30は、サーバ側受信部52と、オートマトン記憶部54と、鍵発生部56と、サーバ側鍵記憶部58と、交換データ生成部60と、第2暗号化部62と、サーバ側送信部64とを有する。文字入力部32は、文字列に含まれる各文字を先頭から1つずつ入力する。配列化部34は、文字入力部32が入力した文字に対応して、当該文字を特定する1つの要素が非単位元とされ、文字を特定する要素以外の要素が単位元とされた配列を生成する。なお、配列については詳細を図3等を参照して更に説明する。第1暗号化部36は、配列化部34により生成された配列に含まれる複数の要素のそれぞれを、準同型性を有する第1暗号化方式により暗号化して暗号配列を生成する。なお、第1暗号化方式および暗号配列については詳細を図3等を参照して更に説明する。クライアント側送信部38は、それぞれの文字に対応付けて、第1暗号化部36により生成された暗号配列をサーバ30に送信する。このように、クライアント20は、文字に対応して、文字を特定する要素が準同型性を有する第1暗号化方式により非単位元を暗号化した値とされ、文字を特定する要素以外の要素が第1暗号化方式により単位元を暗号化した値とされた暗号配列を、サーバ30に送信する。サーバ側受信部52は、暗号配列をクライアント20から受信する。オートマトン記憶部54は、クライアント20に入力された文字列を受理するか否かを判定するためのオートマトンを記憶する。鍵発生部56は、クライアント20に入力される文字列の各文字に対応して、オートマトンにおける複数の後状態のそれぞれに対応する後状態鍵を発生する。なお、後状態鍵については詳細を図5等を参照して更に説明する。サーバ側鍵記憶部58は、オートマトンにおける複数の後状態のそれぞれに対応付けられた後状態鍵を、次の文字が入力された場合の複数の前状態のそれぞれに対応する複数の前状態鍵として記憶する。なお、前状態鍵については詳細を図5等を参照して更に説明する。交換データ生成部60は、暗号配列を受信したことに応じて、オートマトンにおける複数の前状態のそれぞれに対応して、受信した暗号配列の各要素のそれぞれに、当該前状態から当該要素により特定される文字が入力されたことに応じて遷移する後状態に対応する後状態鍵を冪乗する。そして、交換データ生成部60は、後状態鍵を冪乗した複数の要素を第1暗号化方式に対応する演算により結合することにより、第1暗号化方式により後状態鍵を暗号化した交換データを生成する。さらに、交換データ生成部60は、オートマトンにおける複数の状態のそれぞれに対応して、当該状態が正しい最終状態である場合には受理を示す値、正しい最終状態でない場合には不受理を示す値を表す最終状態データを発生する。なお、交換データの生成方法については詳細を図9等を参照して更に説明する。第2暗号化部62は、オートマトンにおける複数の前状態のそれぞれに対応して生成された複数の交換データのそれぞれを、対応する前状態鍵により暗号化する。更に、第2暗号化部62は、オートマトンにおける複数の状態のそれぞれについて、文字列の最後の文字に対応した後状態鍵により最終状態データを暗号化する。なお、複数の交換データのそれぞれの暗号化処理については詳細を図5等を参照して更に説明する。サーバ側送信部64は、暗号配列の受信に応じて、暗号化された複数の交換データをクライアント20に送信する。このように、サーバ30は、暗号配列を受信したことに応じて、オートマトンの複数の前状態のそれぞれに対応して、暗号配列に基づいて第1暗号化方式により後状態鍵を暗号化した交換データを生成し、対応する前状態鍵で交換データを暗号化してクライアント20に送信する。クライアント側受信部40は、文字に対応する暗号配列を送信したことに応じて、サーバ30から暗号化された複数の交換データを受信する。また、クライアント側受信部40は、オートマトンにおける複数の状態のそれぞれについて、暗号化された最終状態データを受信する。クライアント側鍵記憶部42は、文字列の各文字に対応して、1つの前状態鍵を記憶している。より詳しくは、クライアント側鍵記憶部42は、文字列の先頭の文字に対応して予め1つの前状態鍵を取得して記憶する。また、クライアント側鍵記憶部42は、文字列の先頭以外の各文字のそれぞれに対応して、第1復号部46により復号された前の文字に対応する後状態鍵を、前状態鍵として記憶する。第2復号部44は、クライアント側受信部40により受信された暗号化された複数の交換データのそれぞれに対して、クライアント側鍵記憶部42に記憶された対応する文字の前状態鍵により復号処理を実行する。第2復号部44は、当該文字が正しい場合には、複数の交換データのうち1つの交換データを復号できる。第1復号部46は、複数の交換データのうち第2復号部44が復号できた1つの交換データから、第1暗号化方式により後状態鍵を復号する。即ち、第1復号部46は、第2復号部44が復号できた1つの交換データから、第1暗号化部36によって当該文字に対応する配列の各要素を第1暗号化方式で暗号化する場合に用いた暗号鍵に対応する復号鍵を用いて、後状態鍵を復号する。なお、第1復号部46は、文字列に含まれる最後の文字に対応する復号処理を実行した後において、復号した後状態鍵によって最終状態データを復号する。第1復号部46は、文字列のうち最後以外の文字に対応する復号処理を実行した場合には、復号した1つの後状態鍵を、次の文字の前状態鍵としてクライアント側鍵記憶部42に書き込む。第1復号部46は、最終状態データを復号して受理または不受理を示す値が復号できた場合には、受理を示す値または不受理を示す値を判定部48に受け渡す。判定部48は、文字列の途中の段階において第2復号部44が複数の交換データの何れも復号できなかった場合、または、第1復号部46が不受理を示す値を復号した場合には、入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移していないと判定する。また、判定部48は、第1復号部46が受理を示す値を復号した場合には、入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移したと判定する。このように、クライアント20は、複数の文字のそれぞれに対応して受信した暗号化された複数の交換データを、先頭の文字から順次に復号する。そして、クライアント20は、最後の文字に対応する交換データまで復号でき且つ受理を表すデータを受け取った場合には、入力された文字列に応じてオートマトンが正しい最終状態まで遷移したと判定する。これにより、認証システム10は、クライアント20に入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移するかを判定することができる。図3は、本実施形態に係るクライアント20の送信時の処理のフローチャートを示す。図4は、第1暗号化方式により生成される暗号文の一例を示す。クライアント20は、文字列が入力されると、入力された文字列に含まれる文字を1つずつ順次に選択し、それぞれの文字についてステップS11からステップS14の処理を実行する。まず、ステップS11において、クライアント20は、文字を入力する。本実施形態においては、入力可能な文字の集合Σのうちのσ番目インデックスσで特定される文字Xσを入力する。例えば、クライアント20は、1バイトで表現される文字であれば、0番目から255番目までの何れか1つの文字を入力する。続いて、ステップS12において、クライアント20は、入力した文字を配列V′に変換する。より具体的には、クライアント20は、入力可能な文字の集合Σに含まれる複数の文字の数|Σ|の要素を含む配列を準備する。例えば、1バイトで表現される文字を入力する場合には、256個の要素を含む配列を準備する。準備された配列は、複数の要素のそれぞれが、集合Σに含まれる複数の文字のそれぞれに一対一に対応する。例えば、1ビットで表現される文字0または1が表現する文字であれば、配列には、2つの要素が含まれ、一番目の要素が0に対応し、二番目の要素が1に対応する。そして、クライアント20は、準備した配列を用いて、文字入力部32が入力した文字に対応して、当該文字を特定する1つの要素が非単位元とされ、文字を特定する要素以外の要素が単位元とされた配列を生成する。ここで、単位元とは、後述する第1暗号化方式に対応する2項演算の単位元をいう。詳細は後述するが、第1暗号化方式が加法準同型性を有する暗号化方式であれば、この単位元は、加法演算の単位元である0となり、非単位元は0以外の予め定められた数値例えば、1となる。また、第1暗号化方式が乗法準同型性を有する暗号化方式であれば、この単位元は、乗法演算の単位元である1となり、非単位元は1以外の予め定められた数値となる。本実施形態においては、第1暗号化方式が加法準同型性を有する暗号化方式を採用する。そこで、クライアント20は、下記の式11に示されるように、文字Xσを特定する1つの要素インデックスσの要素bσが1とされ、文字を特定する要素以外の要素インデックスσ以外の要素が0とされた配列V ́を生成する。なお、bxは、配列に含まれるインデックスxの要素の値を表す。xは、0≦x≦|Σ|-1の範囲の整数である。また、σは、文字の集合Σにおける文字Xσを特定するインデックスであり、0≦σ≦|Σ|-1の範囲の整数である。続いて、ステップS13において、クライアント20は、配列化部34により生成された配列に含まれる複数の要素のそれぞれを第1暗号化方式により暗号化して暗号配列Vを生成する。これにより、クライアント20は、文字に対応して、当該文字を特定する要素が第1暗号化方式により非単位元を暗号化した値とされ、文字を特定する要素以外の要素が第1暗号化方式により単位元を暗号化した値とされた暗号配列を生成することができる。第1暗号化方式は、選択平文攻撃に対して識別困難性IND-CPAを満たし、且つ、準同型性加法準同型性または乗法準同型性を有する公開鍵暗号方式である。例えば、加法準同型性を有する暗号化方式の暗号文は、下記の式12に示される特徴を有する。なお、m1、m2、mは、平文を表す。即ち、加法準同型性を有する暗号化方式では、2つの暗号文Em1、Em2が与えられたときに、暗号文同士の加算結果Em1Em2が、平文同士を加算した後に暗号化した暗号文Em1m2と同一となる。また、暗号文を任意の数値kで冪乗した結果Emkが、平文を任意の数値kで乗算した後に暗号化した暗号文Ekmと同一となる。また、更に、第1暗号化方式は、例えば、図4に示されるように、同一の平文を暗号化した場合であっても暗号化処理毎に暗号文が異なる方式である。即ち、第1暗号化方式は、ある平文をある暗号鍵で1回目に暗号化した暗号文と、同一の平文を同一の暗号鍵で2回目に暗号化した暗号文とが異なるが、1回目と2回目の2つの暗号文のそれぞれから同一の平文を復号することができる。これにより、クライアント20は、配列内の各要素が、単位元を暗号化した暗号文であるか、非単位元を暗号化した暗号文であるかを判別できなくすることができる。このような特徴を有する暗号化方式として、拡張エルガマル暗号方式が知られている。本実施形態においては、クライアント20は、第1暗号化方式として拡張エルガマル暗号方式を用いて、下記の式13に示されるような暗号配列を生成する。即ち、本実施形態においては、クライアント20は、文字Xσを特定する1つの要素インデックスσの要素が1を拡張エルガマル方式で暗号化した暗号文とされ、文字を特定する要素以外の要素インデックスσ以外の要素が0を拡張エルガマル方式で暗号化した暗号文とされた暗号配列Vを生成する。続いて、ステップS14において、クライアント20は、生成した暗号配列をサーバ30へと送信する。この場合において、クライアント20は、文字列中における対応する文字の順番がわかるように、暗号配列を送信する。例えば、クライアント20は、各暗号配列を文字順序に従って送信する。また、クライアント20は、文字順序を示すインデックスとともに暗号配列を送信してもよい。図5は、本実施形態に係るサーバ30による処理のフローチャートを示す。図6は、本実施形態に係るサーバ30が有するオートマトンの遷移表の一例を示す。図7は、ある文字が入力された場合の複数の前状態のそれぞれに対応する前状態鍵の鍵表を示す。図8は、ある文字が入力された場合の複数の後状態のそれぞれに対応する後状態鍵の鍵表を示す。まず、ステップS21において、サーバ30は、クライアント20から複数の文字のそれぞれに対応した暗号配列を受信する。サーバ30は、受信した1つの暗号配列に対して、ステップS22からステップS30の処理を実行する。この場合において、サーバ30は、先頭の文字に対応する暗号配列から1文字ずつ順番に、ステップS22からステップS30の処理を実行する。例えば、サーバ30は、複数の暗号配列が文字順序にクライアント20から送信される場合には、受信順に、暗号配列に対するステップS22からS30の処理を実行する。また、サーバ30は、文字順序を示すインデックスとともに暗号配列がクライアント20から送信される場合には、インデックス順に暗号配列に対するステップS22からS30の処理を実行する。続いて、ステップS22において、サーバ30は、オートマトンを読み出す。オートマトンには、状態の遷移を表す遷移表、状態群、初期状態および正しい最終状態を含む。オートマトンにおける状態の遷移は、例えば、図6に示されるような遷移表により表させる。この遷移表を参照することにより、サーバ30は、任意の文字が与えられた場合において、現在の状態前状態から遷移する次の状態後状態を特定することができる。本実施形態において、オートマトンは、例えば、q0~q|Q|-1で表される|Q|個の状態を有する。また、本実施形態において、オートマトンは、x0からx|Σ|-1までの|Σ|個の文字を受け取ることができる。そして、本実施形態において、オートマトンは、i番目の前状態qiにおいて、σ番目の文字xσが与えられたことに応じて、j番目の後状態qjに遷移する。なお、i、jは、0から状態数|Q|-1までの間の整数である。続いて、ステップS23において、サーバ30は、複数の前状態のそれぞれに対応する複数の前状態鍵を読み出す。本実施形態においては、サーバ30は、図7に示されるように、複数の前状態q0~q|Q|-1のそれぞれに対応して前状態鍵S0~S|Q|-1を記憶しており、これらを読み出す。なお、これらの前状態鍵は、直前の文字に対応する後状態鍵と同一であり、文字を入力する毎に異なる値となる。また、最初の文字に対応する前状態鍵は、予め生成されている。本実施形態においては、サーバ30は、ある文字が入力された場合、i番目の前状態qiに対応して前状態鍵Sjを読み出す。続いて、ステップS24において、サーバ30は、複数の後状態のそれぞれに対応する複数の後状態鍵を発生する。ここで、後状態鍵は、オートマトンにおける複数の後状態のそれぞれに対応付けられた乱数である。本実施形態においては、サーバ30は、図8に示されるように、複数の後状態q0~q|Q|-1のそれぞれに対応した後状態鍵r0~r|Q|-1を発生する。なお、これらの後状態鍵は、文字を入力する毎に異なる値となる。本実施形態においては、例えば、サーバ30は、ある文字が入力された場合、j番目の後状態qjに対応して後状態鍵rjを読み出す。続いて、ステップS25からステップS28において、サーバ30は、前状態毎にループ処理を実行する。本実施形態においては、サーバ30は、複数の前状態q0~q|Q|-1のそれぞれ毎に、ステップS26およびステップS27の処理を実行する。ステップS26において、サーバ30は、当該前状態から、当該暗号配列に対応する文字が入力されたことに応じて遷移する後状態に対応する後状態鍵を、第1暗号化方式により暗号化した交換データを生成する。例えば、前状態がqiであり、受信した暗号配列に対応する文字がXσである即ち、受信した暗号配列が文字Xσから生成されたとする。この場合、前状態qiにおいて文字Xσが入力されたことに応じて遷移する後状態は、図6に示されるように、qjである。また、後状態qjに対応する後状態鍵は、図8に示されるように、rjである。従って、サーバ30は、下記の式14に示されるように、前状態がqiであり、受信した暗号配列に対応する文字がXσである場合には、rjを第1暗号化方式で暗号化した暗号文を、交換データCiとして生成する。なお、交換データの生成方法の詳細については図9を参照して更に説明する。続いて、ステップS27において、サーバ30は、生成した交換データを、対応する前状態鍵で暗号化する。この場合において、サーバ30は、メッセージ認証コードMAC付きの秘密鍵暗号化方式で、交換データを暗号化する。本実施形態においては、サーバ30は、一例として、ディフィーヘルマン鍵を用いて交換データを暗号化する。ステップS28において、サーバ30は、全ての前状態についてステップS26およびステップS27の処理を終了したと判定すると、ループを抜けて処理をステップS29に進める。続いて、サーバ30は、文字列の最後の文字に対応する暗号配列を受信した場合には、ステップS29の処理を実行する。なお、サーバ30は、文字列の最後の文字以外の文字に対応する暗号配列を受信した場合には、当該ステップS29の処理をスキップしてステップS30に処理を進める。ステップS29において、サーバ30は、文字列の最後の文字に対応する暗号配列を受信した場合には、オートマトンにおける複数の状態のそれぞれに対応して、当該状態が正しい最終状態である場合には受理を示す値、正しい最終状態でない場合には不受理を示す値を表す最終状態データを発生する。そして、サーバ30は、オートマトンにおける複数の状態のそれぞれに対応して発生した最終状態データを、文字列の最後の文字に対応して発生された対応する状態の後状態鍵により暗号化する。続いて、ステップS30において、サーバ30は、全ての前状態のそれぞれについて生成した暗号化した複数の交換データをクライアント20へと送信する。また、サーバ30は、最後の文字に対応する暗号配列を受け取った場合には、複数の状態のそれぞれについて生成した暗号化した最終状態データもクライアント20へと送信する。この場合において、サーバ30は、オートマトンの複数の前状態のそれぞれに対応して暗号化した複数の交換データを、暗号配列毎に、例えばランダムに並べ替えて送信する。また、この場合において、サーバ30は、受信した暗号配列に対応付けられている文字順序がわかるように、暗号化した複数の交換データをクライアント20へと送信する。サーバ30は、一例として、文字順序を示すインデックスまたは対応する暗号配列を特定する情報を付加して、暗号化した複数の交換データをクライアント20に送信する。本実施形態においては、前状態q0~q|Q|-1のそれぞれに対応して、複数の交換データC0~C|Q|-1が生成されるとする。この場合、サーバ30は、下記の式15に示すように、複数の交換データC0~C|Q|-1のそれぞれを、前状態鍵S0~S|Q|-1のそれぞれにより暗号化する。なお、Encx,yは、ディフィーヘルマン鍵xで、データyを暗号化することを表す。サーバ30は、文字列の最後の文字について処理を終えると、当該フローを終了する。文字列の最後の文字以外の文字について処理を終えた場合には、このステップS30において、サーバ30は、複数の後状態q0~q|Q|-1のそれぞれに対応した複数の後状態鍵r0~r|Q|-1を、次の文字に対応する複数の前状態鍵として、記憶する。そして、サーバ30は、処理を最初に戻し、次の文字に対応付けられた暗号配列に対する処理を実行する。図9は、本実施形態に係るサーバ30における、交換データの生成処理のフローチャートを示す。サーバ30は、図5のステップS26の交換データの生成処理として、以下のステップS31からステップS37の処理を実行する。まず、ステップS31からステップS36において、サーバ30は、受信した暗号配列に含まれる複数の要素のそれぞれ毎にループ処理を実行する。本実施形態においては、サーバ30は、0番目から|Σ|-1番目までの複数の要素のそれぞれについて、ステップS32からステップS35までの処理を実行する。ステップS32において、サーバ30は、処理対象となっている要素に対応する文字を特定する。例えば、1ビットで表現される文字が入力される場合、暗号配列内に2つの要素が含まれる。この場合、例えば、サーバ30は、暗号配列の一番目の要素について処理をする場合には、当該要素に対応する文字として0を特定し、二番目の要素について処理をする場合には、当該要素に対応する文字として1を特定する。ここでは、サーバ30は、σ番目の要素に対応する文字Xσを特定したとする。続いて、ステップS33において、サーバ30は、処理対象となっている前状態および特定した文字に基づき、当該前状態から当該要素により特定される文字が入力されたことに応じて遷移する後状態を、特定する。ここでは、サーバ30は、処理対象となっている前状態がqiであるとする。この場合、サーバ30は、前状態qiから文字Xσが入力されたことに応じて遷移する後状態として、オートマトンの遷移表例えば図6の遷移表を参照してqjを特定する。続いて、ステップS34において、サーバ30は、特定した後状態qjに対応する後状態鍵を、ステップS24において発生された複数の後状態鍵の中から選択する。ここでは、サーバ30は、後状態qjに対応する後状態鍵として、発生した複数の後状態鍵の表例えば図8の表の中からrjを選択する。続いて、ステップS35において、サーバ30は、対象の要素に対して、選択した後状態鍵rjを冪乗する。ここでは、サーバ30は、式16に示されるように、σ番目の要素Ebσに後状態鍵rjを冪乗する。この結果は、第1暗号化方式の特徴加法準同型性から、当該要素の第1暗号化方式により暗号化する前の値bσに後状態鍵rjを乗算した値bσ×rjに対して、第1暗号化方式により暗号化した暗号文と同一となる。続いて、ステップS36において、サーバ30は、暗号配列に含まれる全ての要素についてステップS32~ステップS35の処理を終了したと判定すると、ループを抜けて処理をステップS37に進める。ステップS37において、サーバ30は、後状態鍵を冪乗した要素のそれぞれを、第1暗号化方式に対応する演算により結合する。サーバ30は、このように結合した結果を、当該前状態に対応する交換データとする。本実施形態においては、第1暗号化方式が加法準同型性を有する暗号化方式であるので、サーバ30は、加法演算により後状態鍵を冪乗した要素のそれぞれを結合する。なお、サーバ30は、第1暗号化方式が乗法準同型性を有する暗号化方式であれば、乗法演算により結合する。ここでは、式17に示されるように、0番目から|Σ|-1番目までの各要素について、加法演算をして結合して交換データを生成する。なお、b0、b1、...、bσ、...、b|Σ|-1は、第1暗号化方式により暗号化する前の要素の値を表す。また、rΔqi、x0、rΔqi、x1、...、rΔqi、xσ、...、rΔqi、x|Σ|-1は、複数の要素のそれぞれに冪乗された後状態鍵を表す。ここで、暗号配列は、文字を特定する要素が第1暗号化方式により非単位元を暗号化した値とされ、文字を特定する要素以外の要素が第1暗号化方式により単位元を暗号化した値とされている。例えば、暗号配列Vは、下記の式18に示されるように、第1暗号化方式が加法準同型性を有し、文字Xσに対応する要素bσが加法演算の非単位元である1、文字Xσに対応する要素bσ以外の要素が加法演算の単位元である0とされている。従って、式17に式18の要素を代入すると、交換データは、下記の式19に示されるように変換される。即ち、文字Xσに対応する要素以外の要素は、全て0となり、文字Xσに対応する要素は、後状態鍵の値となる。この結果、交換データは、前状態qiから、暗号配列に対応する文字Xσが入力されたことに応じて遷移する後状態qjに対応する後状態鍵rjを、第1暗号化方式により暗号化した暗号文Erjとなる。以上のように、サーバ30は、ステップS31~ステップS37の処理を実行することにより、当該前状態から、当該暗号配列に対応する文字が入力されたことに応じて遷移する後状態に対応する後状態鍵を、第1暗号化方式により暗号化した交換データを生成することができる。図10は、本実施形態に係るクライアント20における復号処理のフローチャートを示す。まず、ステップS41において、クライアント20は、文字列に含まれる文字に対応した暗号配列を送信したことに応じて、サーバ30から暗号化された複数の交換データを受信する。また、クライアント20は、文字列に含まれる最後の文字に対応して暗号配列を送信した場合には、暗号化された複数の交換データとともに、暗号化された複数の最終状態データも受信する。クライアント20は、受信した暗号化された複数の交換データに対して、ステップS42からステップS51の処理を実行する。この場合において、クライアント20は、対応する文字の文字順序に従って、暗号化された複数の交換データに対する処理を実行する。続いて、ステップS42において、クライアント20は、対応する文字に対応付けて記憶されている1つの前状態鍵を読み出す。なお、クライアント20は、文字列の先頭の文字に対応して、例えばサーバ30から予め1つの前状態鍵を受信して記憶している。また、クライアント20は、文字列の先頭以外の各文字のそれぞれに対応して、前の文字に対応する1つの後状態鍵を、1つの前状態鍵として記憶している。続いて、ステップS43からステップS46において、クライアント20は、複数の交換データのそれぞれ毎に、ループ処理を実行する。ステップS44において、クライアント20は、処理対象の暗号化された交換データを、読み出した1つの前状態鍵によって復号処理を実行する。ここで、対応する文字が入力された場合にオートマトンが正しく他の状態に遷移できていれば、クライアント20は、暗号化された複数の交換データのうち何れか1つを復号することができる。また、対応する文字が入力された場合にオートマトンが正しく他の状態に遷移できない場合、クライアント20は、暗号化された複数の交換データの何れも復号することができない。続いて、ステップS45において、クライアント20は、交換データが復号できたか否かを判断するステップS45。クライアント20は、復号できた場合にはステップS45のYes、処理をステップS47に進める。クライアント20は、復号できなかった場合にはステップS45のNo、処理をステップS46に進める。ステップS46において、クライアント20は、複数の交換データの全てについて、ステップS44およびステップS45の処理が終了したか否かを判断する。クライアント20は、複数の交換データの何れかについて未だ処理が終了していない場合には、処理をステップS43に戻し、次の交換データについてステップS44およびステップS45の処理を実行する。クライアント20は、複数の交換データの全てについて処理が終了していれば、即ち、複数の交換データの何れも復号できなかった場合には、入力された文字列によってサーバ30が保有するオートマトンが正しい最終状態に遷移しなかった不受理と判定して、本フローを終了する。一方、交換データが復号できた場合ステップS45のYes、ステップS47において、クライアント20は、復号できた1つの交換データを第1暗号化方式で復号処理をして、後状態鍵を復号する。即ち、クライアント20は復号できた1つの交換データを、当該文字に対応する配列の各要素を第1暗号化方式で暗号化する場合に用いた暗号鍵に対応する復号鍵を用いて後状態鍵を復号する。続いて、ステップS48において、クライアント20は、最後の文字に対応する処理か否かを判断するステップS48。クライアント20は、最後の文字に対応する処理ではないと判断した場合ステップS48のNo、処理をステップS49に進める。ステップS49において、クライアント20は、復号した後状態鍵を、次の文字に対応する前状態鍵として保存する。そして、クライアント20は、ステップS49の処理を終えると、次の文字に対応する処理をするためにステップS41から処理を繰り返す。また、クライアント20は、最後の文字に対応する処理であると判断した場合ステップS49のYes、処理をステップS50に進める。ステップS50において、クライアント20は、復号した後状態鍵により、複数の最終状態データのそれぞれを復号する。この場合、クライアント20は、複数の最終状態データのうち何れか1つを復号することができる。続いて、ステップS51において、クライアント20は、復号できた最終状態データから受理を示す値が復号されたか否かを判定する。クライアント20は、受理を示す値が復号されていないと判定した場合にはステップS51のNo、入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移しなかった不受理と判定して、本フローを終了する。また、クライアント20は、受理を示す値が復号されたと判定した場合にはステップS51のYes、入力された文字列によって、サーバ30が保有するオートマトンが正しい最終状態に遷移した受理と判定して、当該フローを終了する。以上のように、本実施形態に係る認証システム10によれば、クライアント20に入力された文字列をサーバ30に開示せず、且つ、サーバ30が保有するオートマトンをクライアント20に開示せずに、文字列がオートマトンに受理されるか否かを認証することができる。従って、本実施形態に係る認証システム10によれば、例えばクライアント20に入力された情報パスワードおよび個人情報等をサーバ30に開示すること無く、サーバ30からクライアント20へと指定された情報のみを受け渡すことができる。図11は、複数の文字に対応する暗号配列を並列してクライアント20からサーバ30へと送信する場合におけるデータ伝達例を示す。クライアント20およびサーバ30は、送信処理および受信処理を、複数の文字のそれぞれについてまとめて実行してもよい。即ち、クライアント20は、入力された文字列に含まれる複数の文字例えばN個の文字のそれぞれに対応する複数の暗号配列例えばN個の暗号配列を、まとめて並列にサーバ30に送信する。サーバ30は、複数の暗号配列例えばN個の暗号配列を受信したことに応じて、複数の文字N個の文字に対応した暗号化された複数の交換データをまとめて生成する。サーバ30は、暗号化された複数の交換データを、複数の文字のそれぞれについてまとめて並列にクライアント20に送信する。そして、クライアント20は、複数の文字のそれぞれについての暗号化された複数の交換データを、先頭の文字に対応する暗号化された複数の交換データから順次に復号する。これにより、クライアント20およびサーバ30は、送信処理および受信処理を一括して実行することができる。図12は、クライアント20に入力される文字列、および、サーバ30が保有するオートマトンの一例を示す。以下、具体例を用いて、クライアント20およびサーバ30の動作を説明する。本例においては、クライアント20は、010の文字列長Nが3の文字列を入力する。また、サーバ30が保有するオートマトンは、a、b、cの3つの状態を有し、0または1の文字が入力される。また、オートマトンは、初期状態Q0がaであり、正しい終了状態がaである。また、本例において、オートマトンは、状態aにおいて文字0を入力すると状態aに遷移し、状態aにおいて文字1を入力すると状態bに遷移する。また、オートマトンは、状態bにおいて文字0を入力すると状態aに遷移し、状態bにおいて文字1を入力すると状態cに遷移する。また、オートマトンは、状態cにおいて文字0を入力すると状態cに遷移し、状態cにおいて文字1を入力すると状態cに遷移する。図13は、文字列010が入力された場合の暗号配列の一例を示す。クライアント20は、1文字目の文字0に応じて、1番目の要素に非単位元である予め定められた値の1を配置し、2番目の要素に単位元である0を配置した配列V1 ́を生成する。続いて、クライアント20は、この配列V1 ́の2つの要素のそれぞれを、拡張エルガマル暗号化方式により暗号化して暗号配列V1=[E1,E0]を生成する。また、クライアント20は、2文字目の文字1に応じて、1番目の要素に単位元である0を配置し、2番目の要素に非単位元である予め定められた値の1を配置した配列V2 ́を生成する。続いて、クライアント20は、この配列V2 ́の2つの要素のそれぞれを、拡張エルガマル暗号化方式により暗号化して暗号配列V2=[E0,E1]を生成する。クライアント20は、3文字目の文字0に応じて、1番目の要素に非単位元である予め定められた値の1を配置し、2番目の要素に単位元である0を配置した配列V3 ́を生成する。続いて、クライアント20は、この配列V3 ́の2つの要素のそれぞれを、拡張エルガマル暗号化方式により暗号化して暗号配列V3=[E1,E0]を生成する。図14は、オートマトンの遷移表の一例、および、1文字目、2文字目および3文字目の後状態鍵の表の一例を示す。サーバ30は、1文字目の後状態鍵として、図14のAに示されるように、状態aに対応した後状態鍵ra1、状態bに対応した後状態鍵rb1、状態cに対応した後状態鍵rc1を発生する。この結果、1文字目の後状態鍵をオートマトンの遷移表に割り当てた鍵表は、状態aにおいて文字0にはra1、状態aにおいて文字1にはrb1、状態bにおいて文字0にはra1、状態bにおいて文字1にはrc1、状態cにおいて文字0にはrc1、状態cにおいて文字1にはrc1がそれぞれ割り当てられる。また、サーバ30は、2文字目の後状態鍵として、図14のBに示されるように、状態aに対応した後状態鍵ra2、状態bに対応した後状態鍵rb2、状態cに対応した後状態鍵rc2を発生する。この結果、2文字目の後状態鍵をオートマトンの遷移表に割り当てた鍵表は、状態aにおいて文字0にはra2、状態aにおいて文字1にはrb2、状態bにおいて文字0にはra2、状態bにおいて文字1にはrc2、状態cにおいて文字0にはrc2、状態cにおいて文字1にはrc2がそれぞれ割り当てられる。また、サーバ30は、3文字目に対しては、図14のCに示されるように、状態aに対応した後状態鍵ra3、状態bに対応した後状態鍵rb3、状態cに対応した後状態鍵rc3を発生する。この結果、3文字目の受理および不受理をオートマトンの遷移表に割り当てた鍵表は、状態aにおいて文字0にはra3、状態aにおいて文字1にはrb3、状態bにおいて文字0にはra3、状態bにおいて文字1にはrc3、状態cにおいて文字0にはrc3、状態cにおいて文字1にはrc3がそれぞれ割り当てられる。図15は、1文字目の暗号配列から前状態毎の交換データを生成する処理例を示す。サーバ30は、1文字目の暗号配列から前状態毎の交換データを生成する場合、下記に示す処理を実行する。図15のAに示されるように、1文字目における前状態aの交換データを生成する場合、サーバ30は、1文字目の暗号配列V1の1番目の要素E1に対して、1文字目の鍵表における状態a及び文字0に割り当てられた後状態鍵ra1を冪乗する。また、サーバ30は、1文字目の暗号配列V1の2番目の要素E0に対して、1文字目の鍵表における状態a及び文字1に割り当てられた後状態鍵rb1を冪乗する。続いて、サーバ30は、後状態鍵が冪乗された要素同士を加法演算して合成する。これにより、サーバ30は、加法準同型性を有する暗号化方式の特質から、後状態鍵ra1を拡張エルガマル暗号化方式で暗号化した、前状態aに対応した交換データを生成することができる。図15のBに示されるように、1文字目における前状態bの交換データを生成する場合、サーバ30は、1文字目の暗号配列V1の1番目の要素E1に対して後状態鍵ra1を冪乗する。また、サーバ30は、1文字目の暗号配列V1の2番目の要素E0に対して後状態鍵rc1を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵ra1を拡張エルガマル暗号化方式で暗号化した、前状態bに対応した交換データを生成することができる。図15のCに示されるように、1文字目における前状態cの交換データを生成する場合、サーバ30は、1文字目の暗号配列V1の1番目の要素E1に対して後状態鍵rc1を冪乗する。また、サーバ30は、1文字目の暗号配列V1の2番目の要素E0に対して後状態鍵rc1を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵rc1を拡張エルガマル暗号化方式で暗号化した、前状態cに対応した交換データを生成することができる。なお、サーバ30は、1文字目における交換データは、初期状態aに対応した交換データのみを生成してもよい。図16は、2文字目の暗号配列から前状態毎の交換データを生成する処理例を示す。サーバ30は、2文字目の暗号配列から状態毎の交換データを生成する場合、下記に示す処理を実行する。図16のAに示されるように、2文字目における前状態aの交換データを生成する場合、サーバ30は、2文字目の暗号配列V2の1番目の要素E0に対して後状態鍵ra2を冪乗する。また、サーバ30は、2文字目の暗号配列V2の2番目の要素E1に対して後状態鍵rb2を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵rb2を拡張エルガマル暗号化方式で暗号化した、前状態aに対応した交換データを生成することができる。図16のBに示されるように、2文字目における前状態bの交換データを生成する場合、サーバ30は、2文字目の暗号配列V2の1番目の要素E0に対して後状態鍵ra2を冪乗する。また、サーバ30は、2文字目の暗号配列V2の2番目の要素E1に対して後状態鍵rc2を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵rc2を拡張エルガマル暗号化方式で暗号化した、前状態bに対応した交換データを生成することができる。図16のCに示されるように、2文字目における前状態cの交換データを生成する場合、サーバ30は、2文字目の暗号配列V2の1番目の要素E0に対して後状態鍵rc2を冪乗する。また、サーバ30は、2文字目の暗号配列V2の2番目の要素E1に対して後状態鍵rc2を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵rc2を拡張エルガマル暗号化方式で暗号化した、前状態cに対応した交換データを生成することができる。図17は、3文字目の暗号配列から前状態毎の交換データを生成する処理例を示す。サーバ30は、3文字目の暗号配列から状態毎の交換データを生成する場合、下記に示す処理を実行する。図17のAに示されるように、3文字目における前状態aの交換データを生成する場合、サーバ30は、3文字目の暗号配列V1の1番目の要素E1に対して後状態鍵ra3を冪乗する。また、サーバ30は、3文字目の暗号配列V1の2番目の要素E0に対して後状態鍵rb3を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵ra3を拡張エルガマル暗号化方式で暗号化した、前状態aに対応した交換データを生成することができる。図17のBに示されるように、3文字目における前状態bの交換データを生成する場合、サーバ30は、3文字目の暗号配列V1の1番目の要素E1に対して後状態鍵ra3を冪乗する。また、サーバ30は、3文字目の暗号配列V1の2番目の要素E0に対して後状態鍵rc3を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵ra3を拡張エルガマル暗号化方式で暗号化した、前状態bに対応した交換データを生成することができる。図17のCに示されるように、3文字目における前状態cの交換データを生成する場合、サーバ30は、3文字目の暗号配列V1の1番目の要素E1に対して後状態鍵rc3を冪乗する。また、サーバ30は、3文字目の暗号配列V1の2番目の要素E0に対して後状態鍵rc3を冪乗する。続いて、サーバ30は、これらを加法演算して合成する。これにより、サーバ30は、後状態鍵rc3を拡張エルガマル暗号化方式で暗号化した、前状態cに対応した交換データを生成することができる。図18は、サーバ30からクライアント20へと送信される1文字目から3文字目のそれぞれに対応した暗号化された交換データ、および、暗号化された最終状態データの一例を示す。サーバ30は、1文字目における前状態aの交換データを、1文字目の前状態aに対応する前状態鍵ra0により暗号化した暗号文Encra0,Era1を生成する。また、サーバ30は、1文字目における前状態bの交換データを、1文字目の前状態bに対応する前状態鍵rb0により暗号化した暗号文Encrb0,Era1を生成する。また、サーバ30は、1文字目における前状態cの交換データを、1文字目の前状態cに対応する前状態鍵rc0により暗号化した暗号文Encrc0,Erc1を生成する。そして、サーバ30は、このような暗号文をクライアント20へと送信する。この場合において、サーバ30は、各前状態に対応する暗号化された複数の交換データを例えばランダムに並び替えてクライアント20へと送信する。なお、サーバ30は、1文字目における前状態鍵ra0、rb0、rc0は、予め生成されている。また、サーバ30は、1文字目おける処理においては、初期状態aに対応した交換データのみを生成してもよい。サーバ30は、2文字目における前状態aの交換データを、2文字目の前状態aに対応する前状態鍵ra1により暗号化した暗号文Encra1,Erb2を生成する。また、サーバ30は、2文字目における前状態bの交換データを、2文字目の前状態bに対応する前状態鍵rb1により暗号化した暗号文Encrb1,Erc2を生成する。また、サーバ30は、2文字目における前状態cの交換データを、2文字目の前状態cに対応する前状態鍵rc1により暗号化した暗号文Encrc1,Erc2を生成する。そして、サーバ30は、このような暗号文をクライアント20へと送信する。この場合において、サーバ30は、各前状態に対応する暗号化された複数の交換データを例えばランダムに並び替えてクライアント20へと送信する。なお、サーバ30は、2文字目における前状態鍵ra1、rb1、rc1は、1文字目において発生された後状態鍵である。サーバ30は、3文字目における前状態aの交換データを、3文字目の前状態aに対応する前状態鍵ra2により暗号化した暗号文Encra2,Era3を生成する。また、サーバ30は、3文字目における前状態bの交換データを、3文字目の前状態bに対応する前状態鍵rb2により暗号化した暗号文Encrb2,Era3を生成する。また、サーバ30は、3文字目における前状態cの交換データを、3文字目の前状態cに対応する前状態鍵rc2により暗号化した暗号文Encrc2,Erc3を生成する。そして、サーバ30は、このような暗号文をクライアント20へと送信する。この場合において、サーバ30は、各前状態に対応する暗号化された複数の交換データを例えばランダムに並び替えてクライアント20へと送信する。なお、サーバ30は、3文字目における前状態鍵ra2、rb2、rc2は、2文字目において発生された後状態鍵である。また、サーバ30は、状態aが正しい最終状態であることを示す値acceptを、状態aに対応した3文字目の後状態鍵ra3により暗号化した暗号文Encra3,acceptを生成する。また、サーバ30は、状態bが正しい最終状態ではないことを示す値rejectを、状態bに対応した3文字目の後状態鍵rb3により暗号化した暗号文Encrb3,rejectを生成する。また、サーバ30は、状態cが正しい最終状態ではないことを示す値rejectを、状態cに対応した3文字目の後状態鍵rc3により暗号化した暗号文Encrc3,rejectを生成する。そして、サーバ30は、このような暗号文をクライアント20へと送信する。この場合において、サーバ30は、各状態に対応する暗号化された最終状態データを例えばランダムに並び替えてクライアント20へと送信する。図19は、クライアント20において実行される復号処理の順序の一例を示す。まず、クライアント20は、1文字目に対応する暗号化された複数の交換データのそれぞれを、1文字目に対応する前状態鍵により復号する。なお、クライアント20は、1文字目に対応する前状態鍵として、初期状態aに対応した1つの前状態鍵ra0をサーバ30から予め受け取っている。従って、クライアント20は、1文字目に対応する暗号化された複数の交換データのそれぞれに対して復号処理をすることにより、状態aに対応する交換データEra1を復号することができる。なお、クライアント20は、サーバ30から初期状態に対応する暗号化された交換データのみが送信されている場合には、この1つの交換データのみに対して復号処理を実行する。続いて、クライアント20は、復号できた交換データEra1を、1文字目の暗号配列の生成に用いた暗号鍵に応じた鍵により復号する。これにより、クライアント20は、初期状態aに文字0を入力した場合に遷移する後状態aに対応する後状態鍵ra1を復号することができる。続いて、クライアント20は、2文字目に対応する暗号化された複数の交換データのそれぞれを、2文字目に対応する前状態鍵により復号する。なお、2文字目に対応する前状態鍵は、1文字目の交換データから復号された後状態鍵ra1である。従って、クライアント20は、2文字目に対応する暗号化された複数の交換データのそれぞれに対して復号処理をすることにより、状態aに対応する交換データErb2を復号することができる。続いて、クライアント20は、復号できた交換データErb2を、2文字目の暗号配列の生成に用いた暗号鍵に応じた鍵により復号する。これにより、クライアント20は、2文字目において、状態aに文字1を入力した場合に遷移する後状態bに対応する後状態鍵rb2を復号することができる。続いて、クライアント20は、3文字目に対応する暗号化された複数の交換データのそれぞれを、3文字目に対応する前状態鍵により復号する。なお、3文字目に対応する前状態鍵は、2文字目の交換データから復号された後状態鍵rb2である。従って、クライアント20は、3文字目に対応する暗号化された複数の交換データのそれぞれに対して復号処理をすることにより、状態bに対応する交換データEra3を復号することができる。続いて、クライアント20は、復号できた交換データEra3を、3文字目の暗号配列の生成に用いた暗号鍵に応じた鍵により復号する。これにより、クライアント20は、3文字目において、状態bに文字0を入力した場合に遷移する後状態aに対応する後状態鍵ra3を復号することができる。続いて、クライアント20は、複数の状態のそれぞれに対応する暗号化された最終状態データのそれぞれを、3文字目に対応して復号された後状態鍵rc3により復号する。これにより、クライアント20は、状態aに対応する最終状態データから、受理を示す値acceptを復号することができる。クライアント20およびサーバ30は、以上のように処理を実行することにより、クライアント20に入力された文字列をサーバ30に開示せず、且つ、サーバ30が保有するオートマトンをクライアント20に開示せずに、文字列がオートマトンに受理されるか否かを認証することができる。図20は、本実施形態に係るコンピュータ1900のハードウェア構成の一例を示す。本実施形態に係るコンピュータ1900は、ホストコントローラ2082により相互に接続されるCPU2000、RAM2020、グラフィックコントローラ2075、及び表示装置2080を有するCPU周辺部と、入出力コントローラ2084によりホストコントローラ2082に接続される通信インターフェイス2030、ハードディスクドライブ2040、及びCD-ROMドライブ2060を有する入出力部と、入出力コントローラ2084に接続されるROM2010、フレキシブルディスクドライブ2050、及び入出力チップ2070を有するレガシー入出力部とを備える。ホストコントローラ2082は、RAM2020と、高い転送レートでRAM2020をアクセスするCPU2000及びグラフィックコントローラ2075とを接続する。CPU2000は、ROM2010及びRAM2020に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ2075は、CPU2000等がRAM2020内に設けたフレームバッファ上に生成する画像データを取得し、表示装置2080上に表示させる。これに代えて、グラフィックコントローラ2075は、CPU2000等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。入出力コントローラ2084は、ホストコントローラ2082と、比較的高速な入出力装置である通信インターフェイス2030、ハードディスクドライブ2040、CD-ROMドライブ2060を接続する。通信インターフェイス2030は、ネットワークを介して他の装置と通信する。ハードディスクドライブ2040は、コンピュータ1900内のCPU2000が使用するプログラム及びデータを格納する。CD-ROMドライブ2060は、CD-ROM2095からプログラム又はデータを読み取り、RAM2020を介してハードディスクドライブ2040に提供する。また、入出力コントローラ2084には、ROM2010と、フレキシブルディスクドライブ2050、及び入出力チップ2070の比較的低速な入出力装置とが接続される。ROM2010は、コンピュータ1900が起動時に実行するブートプログラム、及び/又は、コンピュータ1900のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ2050は、フレキシブルディスク2090からプログラム又はデータを読み取り、RAM2020を介してハードディスクドライブ2040に提供する。入出力チップ2070は、フレキシブルディスクドライブ2050を入出力コントローラ2084へと接続すると共に、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を入出力コントローラ2084へと接続する。RAM2020を介してハードディスクドライブ2040に提供されるプログラムは、フレキシブルディスク2090、CD-ROM2095、又はICカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、RAM2020を介してコンピュータ1900内のハードディスクドライブ2040にインストールされ、CPU2000において実行される。コンピュータ1900にインストールされ、コンピュータ1900を、クライアント20として機能させるプログラムは、文字入力モジュールと、文字入力モジュールと、配列化モジュールと、第1暗号化モジュールと、クライアント側送信モジュールと、クライアント側受信モジュールと、クライアント側鍵記憶モジュールと、第2復号モジュールと、第1復号モジュールと、判定モジュールとを備える。これらのプログラム又はモジュールは、CPU2000等に働きかけて、コンピュータ1900を、文字入力部32、配列化部34、第1暗号化部36、クライアント側送信部38、クライアント側受信部40、クライアント側鍵記憶部42、第2復号部44、第1復号部46、および、判定部48としてそれぞれ機能させる。これらのプログラムに記述された情報処理は、コンピュータ1900に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、文字入力部32、配列化部34、第1暗号化部36、クライアント側送信部38、クライアント側受信部40、クライアント側鍵記憶部42、第2復号部44、第1復号部46、および、判定部48として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ1900の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のクライアント20が構築される。コンピュータ1900にインストールされ、コンピュータ1900を、サーバ30として機能させるプログラムは、サーバ側受信モジュールと、オートマトン記憶モジュールと、鍵発生モジュールと、サーバ側鍵記憶モジュールと、交換データ生成モジュールと、第2暗号化モジュールと、サーバ側送信モジュールとを備える。これらのプログラム又はモジュールは、CPU2000等に働きかけて、コンピュータ1900を、サーバ側受信部52、オートマトン記憶部54、鍵発生部56、サーバ側鍵記憶部58、交換データ生成部60、第2暗号化部62、および、サーバ側送信部64としてそれぞれ機能させる。これらのプログラムに記述された情報処理は、コンピュータ1900に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、サーバ側受信部52、オートマトン記憶部54、鍵発生部56、サーバ側鍵記憶部58、交換データ生成部60、第2暗号化部62、および、サーバ側送信部64として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ1900の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のサーバ30が構築される。一例として、コンピュータ1900と外部の装置等との間で通信を行う場合には、CPU2000は、RAM2020上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス2030に対して通信処理を指示する。通信インターフェイス2030は、CPU2000の制御を受けて、RAM2020、ハードディスクドライブ2040、フレキシブルディスク2090、又はCD-ROM2095等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス2030は、DMAダイレクトメモリアクセス方式により記憶装置との間で送受信データを転送してもよく、これに代えて、CPU2000が転送元の記憶装置又は通信インターフェイス2030からデータを読み出し、転送先の通信インターフェイス2030又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。また、CPU2000は、ハードディスクドライブ2040、CD-ROMドライブ2060CD-ROM2095、フレキシブルディスクドライブ2050フレキシブルディスク2090等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をDMA転送等によりRAM2020へと読み込ませ、RAM2020上のデータに対して各種の処理を行う。そして、CPU2000は、処理を終えたデータを、DMA転送等により外部記憶装置へと書き戻す。このような処理において、RAM2020は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはRAM2020および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、CPU2000は、RAM2020の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはRAM2020の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもRAM2020、メモリ、及び/又は記憶装置に含まれるものとする。また、CPU2000は、RAM2020から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索置換等を含む各種の処理を行い、RAM2020へと書き戻す。例えば、CPU2000は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合又は不成立であった場合に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。また、CPU2000は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第1属性の属性値に対し第2属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、CPU2000は、記憶装置に格納されている複数のエントリの中から第1属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第2属性の属性値を読み出すことにより、所定の条件を満たす第1属性に対応付けられた第2属性の属性値を得ることができる。以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク2090、CD-ROM2095の他に、DVD又はCD等の光学記録媒体、MO等の光磁気記録媒体、テープ媒体、ICカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はRAM等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ1900に提供してもよい。以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段より前に、先立って等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上まず、、次に、等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。"