(57)【特許請求の範囲】
【請求項１】
データを暗号により匿名化する匿名化装置であって、
前記データに含まれるＩＤを、当該ＩＤを構成する階層構造に基づいて複数の区間に分割する分割手段と、
前記複数の区間を、それぞれ互いに異なる暗号鍵を用いて暗号化して、データ利用者が検索するための暗号化検索キーを生成する第１暗号化手段と、を備え、
データ利用者に対して、前記ＩＤが複数の前記暗号化検索キーに置換されて秘匿化されたデータを、当該データ利用者ごとに許可された前記暗号化検索キーを生成するための前記暗号鍵の組み合わせと共に提供する匿名化装置。
【請求項２】
前記区間を前記階層構造に基づいて階層化した索引を作成する索引作成手段をさらに備え、
前記第１暗号化手段は、前記区間に対応する、前記索引の階層のノードを、前記暗号化検索キーに置換する、
請求項１に記載の匿名化装置。
【請求項３】
前記第１暗号化手段は、前記データが提供されるデータ利用者ごとに異なる暗号鍵を用いて暗号化する、
請求項１又は２に記載の匿名化装置。
【請求項４】
前記第１暗号化手段は、不可逆の暗号化を行う、請求項１から３のいずれか一項に記載の匿名化装置。
【請求項５】
請求項１から４のいずれか一項に記載の匿名化装置により匿名化されたデータを検索する検索装置であって、
前記複数の区間の少なくともいずれかを検索するために検索キーの入力を受け付ける入力手段と、
前記検索キーを、対応する区間の暗号鍵で暗号化し、前記暗号化検索キーを生成する第２暗号化手段と、
前記暗号化検索キーにより、前記データを検索する検索手段と、
を備える検索装置。
【請求項６】
請求項１に記載の匿名化装置が実行する方法であって、
前記分割手段が、前記データに含まれるＩＤを、当該ＩＤを構成する階層構造に基づいて複数の区間に分割する分割ステップと、
前記第１暗号化手段が、前記複数の区間を、それぞれ互いに異なる暗号鍵を用いて暗号化して、データ利用者が検索するための暗号化検索キーを生成する第１暗号化ステップと、
を備え、
データ利用者に対して、前記ＩＤが複数の前記暗号化検索キーに置換されて秘匿化されたデータを、当該データ利用者ごとに許可された前記暗号化検索キーを生成するための前記暗号鍵の組み合わせと共に提供する方法。
【請求項７】
コンピュータに、請求項６に記載の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、匿名化装置、検索装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、コンピュータを利用した様々なサービスが提供されている。多くのサービスにおいては、情報を秘匿するため、暗号が利用される。例えば、次のような暗号方式を開示する文献が知られている。
【０００３】
特許文献１の暗号方式は、Ｆｏｒｍａｔ  Ｐｒｅｓｅｒｖｉｎｇ  Ｅｎｃｒｙｐｔｉｏｎ（ＦＰＥ）と呼ばれ、与えられた文字列の進数や文字列の長さ等の形式を維持したまま、ブロック暗号を実施する。
非特許文献１の暗号方式は、Ａｔｔｒｉｂｕｔｅ  ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ（ＡＢＥ）と呼ばれ、全体情報のうち、解読する人が所属するグループに従い、権限が与えられた情報のみを解読可能にする。
非特許文献２の暗号方式は、Ｓｔｒｉｎｇ  Ｓｅａｒｃｈ  Ｅｎｃｒｙｐｔｉｏｎ（ＳＳＥ）と呼ばれ、文字列をストリーム暗号によりビット単位で暗号化する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第７８６４９５２号明細書
【非特許文献】
【０００５】
【非特許文献１】Ｇｏｙａｌ，Ｖｉｐｕｌ，ｅｔ  ａｌ．“Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｆｉｎｅ−ｇｒａｉｎｅｄ  ａｃｃｅｓｓ  ｃｏｎｔｒｏｌ  ｏｆ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ．”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １３ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ．  ＡＣＭ，２００６．
【非特許文献２】Ｄ．Ｘ．Ｓｏｎｇ，Ｄ．Ｗａｇｎｅｒ，Ａ．Ｐｅｒｒｉｇ．  “Ｐｒａｃｔｉｃａｌ  Ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  Ｓｅａｒｃｈｅｓ  ｏｎ  Ｅｎｃｒｙｐｔｅｄ  Ｄａｔａ”  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，ＩＥＥＥ，２０００．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１の暗号方式は、復号が全情報に対して一括でのみ行えるものであり、部分的な復号を許容しない。このため、同一のデータが異なる事業者に提供された場合、すべての事業者が同一の内容を復号できてしまう。
非特許文献１の暗号方式は、開示する範囲に合わせ、開示するグループの数だけ多重に暗号化をするため、計算量が多く、復号に時間がかかる。
非特許文献２の暗号方式は、暗号化と復号のときにバイトごとにＩｎｉｔｉａｌｉｚａｔｉｏｎ  Ｖｅｃｔｏｒ（ＩＶ）と呼ばれる乱数を使用するので、データ利用者による暗号データの検索を許可するためにＩＶを固定して使用する必要がある場合には、第三者にＩＶ及び鍵を特定されやすくなる。
【０００７】
本発明は、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とする匿名化装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
具体的には、以下のような解決手段を提供する。
（１）  データを匿名化する匿名化装置であって、前記データを複数の区間に分割する分割手段と、前記複数の区間を、それぞれ互いに異なる暗号鍵を用いて暗号化して、暗号化検索キーを生成する第１暗号化手段と、を備える匿名化装置。
【０００９】
（１）の匿名化装置は、ＩＤの区間を、互いに異なる暗号鍵を用いて、暗号化検索キーに置換する。
暗号鍵のいずれかを提供されたデータ利用者は、検索キーを暗号鍵で暗号化することによりＩＤが秘匿された状態のままＩＤの特定の区間を検索できる。
したがって、匿名化装置は、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とする。
【００１０】
（２）  前記区間を階層化した索引を作成する索引作成手段をさらに備え、前記第１暗号化手段は、前記区間に対応する、前記索引の階層のノードを、前記暗号化検索キーに置換する、（１）に記載の匿名化装置。
【００１１】
（２）の匿名化装置は、ＩＤの区間を階層化した索引を作成するので、区間の組を高速に検索できる。
【００１２】
（３）  前記第１暗号化手段は、前記データが提供されるデータ利用者ごとに異なる暗号鍵を用いて暗号化する、（１）又は（２）に記載の匿名化装置。
【００１３】
（３）の匿名化装置は、たとえ同一区間の検索が許可されるデータ利用者であっても異なる暗号鍵を用いるのでデータ利用者に提供した暗号化したＩＤを含むデータは、別のデータ利用者の暗号鍵によって、検索されない。
【００１４】
（４）  前記第１暗号化手段は、不可逆の暗号化を行う、（１）から（３）のいずれか一に記載の匿名化装置。
【００１５】
（４）の匿名化装置は、復号できない暗号化を行うので、秘匿性が高まる。
【００１６】
（５）  （１）から（４）のいずれか一に記載の匿名化装置により匿名化されたデータを検索する検索装置であって、前記複数の区間の少なくともいずれかを検索するために検索キーの入力を受け付ける入力手段と、前記検索キーを、対応する区間の暗号鍵で暗号化し、前記暗号化検索キーを生成する第２暗号化手段と、前記暗号化検索キーにより、前記データを検索する検索手段と、を備える検索装置。
【００１７】
（５）の検索装置は、受け付けた検索キーを暗号鍵で暗号化することにより、ＩＤが秘匿された状態のままＩＤの特定の区間を検索できる。
【００１８】
（６）  （１）に記載の匿名化装置が実行する方法であって、前記分割手段が、前記データを複数の区間に分割する分割ステップと、前記第１暗号化手段が、前記複数の区間を、それぞれ互いに異なる暗号鍵を用いて暗号化し、暗号化検索キーを生成する第１暗号化ステップと、を備える方法。
【００１９】
（６）の方法は、（１）と同様に、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とする。
【００２０】
（７）  コンピュータに、（６）に記載の各ステップを実行させるためのプログラム。
【００２１】
（７）のプログラムは、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とするように、コンピュータに機能させることができる。
【発明の効果】
【００２２】
本発明によれば、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とすることができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の一実施形態に係る匿名化装置の構成を示すブロック図である。
【図２】本発明の一実施形態に係る匿名化装置によって作成される索引の例を示す図である。
【図３】本発明の一実施形態に係る匿名化装置の暗号化処理の例を示すフローチャートである。
【図４】本発明の一実施形態に係る検索装置の構成を示すブロック図である。
【図５】本発明の一実施形態に係る検索装置の検索処理の例を示すフローチャートである。
【発明を実施するための形態】
【００２４】
以下、本発明の実施形態について、図を参照しながら説明する。
【００２５】
［匿名化装置］
図１は、本発明の一実施形態に係る匿名化装置１０の構成を示すブロック図である。
匿名化装置１０は、分割手段１１と、索引作成手段１２と、第１暗号化手段１３とを備え、データを匿名化する。
データは、例えば、車両や携帯機器から収集された、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）で測位された緯度経度を含む移動データや、ウェブでの購買履歴データ等であってよい。
個人から収集されるこのようなデータは、車両識別番号やクレジットカードの番号等の、個人を特定するＩＤを含む。
ＩＤは、任意の階層構造を有してよい。例えば、車両識別番号は、車種や世代、製造番号等から構成され、クレジットカード番号は、先頭４桁に発行会社の情報が含まれている。
【００２６】
分割手段１１は、データに含まれるＩＤをＩＤの階層構造に基づいて、複数の区間に分割する。例えば、車両識別番号は、検索キーとなりうる車種、世代、製造番号等の区間に分割される。
【００２７】
第１暗号化手段１３は、複数の区間を、それぞれ互いに異なる暗号鍵を用いて暗号化して、暗号化検索キーに置換する。
【００２８】
具体的には、ＩＤが区間Ａと、区間Ｂとから構成される場合、分割手段１１は、ＩＤを、区間Ａと区間Ｂとに分割し、第１暗号化手段１３は、区間Ａに暗号鍵ＫＡを用いて暗号化検索キーＥＫＡを生成し、区間Ｂに、暗号鍵ＫＡと異なる暗号鍵ＫＢを用いて暗号化検索キーＥＫＢを生成する。第１暗号化手段１３は、暗号鍵と区間とを対応付けるとしてよい。
第１暗号化手段１３は、データが提供されるデータ利用者ごとに異なる暗号鍵を用いて暗号化する。例えば上述の場合、第１暗号化手段１３は、データ利用者Ｕ１に提供するデータに対して、暗号鍵ＫＡ１と暗号鍵ＫＢ１とを用い、データ利用者Ｕ２に提供するデータに対して、暗号鍵ＫＡ２と暗号鍵ＫＢ２とを用いる。
【００２９】
暗号方式は、一般的なものであってよく、例えば、６４ｂｉｔのものであればＲＣ（Ｒｉｖｅｓｔ  Ｃｉｐｈｅｒ）５、１２８ｂｉｔのものであればＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）等であってよい。第１暗号化手段１３は、ブロック暗号に基づく、区間ごとに異なる暗号鍵による暗号を連鎖的に施す。
暗号方式は、不可逆暗号でもよい。第１暗号化手段１３は、複数の区間に対し、それぞれ互いに異なる鍵を用いた鍵つきハッシュ関数（Ｋｅｙｅｄ  ｈａｓｈ  ｆｕｎｃｔｉｏｎ）により、ハッシュ値を生成してもよい。
【００３０】
索引作成手段１２は、分割手段１１によって分割された区間を階層化した索引を作成する。具体的には、索引作成手段１２は、ＩＤの階層構造に基づいて、トライ木１００（図２参照）を作成する。第１暗号化手段１３は、複数の区間に対応する、トライ木１００の階層のノードを、暗号化検索キーに置換する。
【００３１】
図２は、本発明の一実施形態に係る匿名化装置１０によって作成される索引の例を示す図である。図２が示す例は、大量のデータに対しても高速に検索可能とするために、トライ木１００で索引を作成する例である。この例では、与えられたＩＤは文字単位に分割され、文字単位の索引が構築される。図２において、最上位ノードであるルートノード１０１の○は空の文字列を表し、「§」はリーフノードを表す。
【００３２】
ＩＤとして、「ＡＰＰＬＥ」、「ＡＰＲＯＮ」、「ＢＡＴ」、「ＢＡＧ」、「ＢＩＧ」の５つが与えられたとする。図２に示すように、匿名化装置１０は、「ＡＰＰＬＥ」を「Ａ」と、「Ｐ」と、「Ｐ」と、「Ｌ」と、「Ｅ」とに分割し、「ＡＰＲＯＮ」を「Ａ」と、「Ｐ」と、「Ｒ」と、「Ｏ」と、「Ｎ」とに、他のＩＤもそれぞれ同様に文字単位に分割する。この例の場合、文字列の始まりは、「Ａ」か「Ｂ」のいずれかであるため、索引のルートノード１０１の直下の階層ＨＡに「Ａ」と「Ｂ」とがノードとして登録される。
【００３３】
次に、ＩＤの２文字目は、１文字目が「Ａ」の場合は「Ｐ」のみ、「Ｂ」の場合は「Ａ」か「Ｉ」のいずれかであるため、匿名化装置１０は、「Ａ」の下には「Ｐ」、「Ｂ」の下には「Ａ」及び「Ｉ」を、次のノードとして階層ＨＢに登録する。以降、匿名化装置１０は、ＩＤそれぞれの全文字を処理し終えるまで下位階層（階層ＨＣ、階層ＨＤ、階層ＨＥ・・・）へのノードの登録を繰り返す。
なお、この処理方法では、文字列が長い場合にその長さ分だけの階層の木ができてしまい、処理上の効率が悪くなる。そこで、匿名化装置１０は、例えば、図２の例で「ＰＬＥ」や「ＲＯＮ」等のように、他の分岐が存在しない箇所についてはまとめて１つのノードとしてもよい。すなわち、匿名化装置１０は、Ａ−＞Ｐ−＞Ｐ−＞Ｌ−＞Ｅというノードの階層を、Ａ−＞Ｐ−＞ＰＬＥというノードの階層にしてもよい。
【００３４】
最後に、匿名化装置１０は、同一の階層にあるノードを同一の区間とみなして、各階層と各区間とを対応させる。すなわち、匿名化装置１０は、ルートノード１０１の直下の「Ａ」及び「Ｂ」を含む階層ＨＡを区間Ａに対応させ、次の「Ｐ」、「Ａ」及び「Ｉ」を含む階層ＨＢを区間Ｂに対応させる。同様にして、匿名化装置１０は、次の階層ＨＣを区間Ｃと対応させ、次の階層ＨＤを区間Ｄと対応させ、次の階層ＨＥを区間Ｅと対応させて、階層ＨＡから階層ＨＥを区間Ａから区間Ｅと対応させる。匿名化装置１０は、このようなトライ木１００を作成する。
【００３５】
匿名化装置１０は、階層ＨＡから階層ＨＥのそれぞれのノードを、階層ごとに異なる暗号鍵を用いて暗号化する。すなわち、匿名化装置１０は、階層ＨＡに対しては暗号鍵ＫＡで暗号化することで暗号化検索キーＥＡ１、ＥＢ１を生成し、階層ＨＢに対しては暗号鍵ＫＢで暗号化することで暗号化検索キーＥＰ２、ＥＡ２、ＥＩ２を生成して、各ノードの値を置換する。
【００３６】
このとき、暗号化検索キーＥＡ１の１や暗号化検索キーＥＰ２の２は、ＩＤが階層構造になっているため、最上位の階層から何番目の階層であるかを表す。匿名化装置１０は、暗号化に用いた暗号鍵を、階層の順序のとおりに記録保存する。
【００３７】
匿名化装置１０は、複数のデータ利用者に同じデータを渡す場合に、異なる暗号鍵で同じデータを暗号化する。すなわち、匿名化装置１０は、図２の例において同じデータを２人のデータ利用者へ提供する場合に、５つの暗号鍵の列を２つ、計１０個の暗号鍵を用いて暗号化する。
【００３８】
暗号化の後に、暗号化されたＩＤを含むデータは、データ利用者へ提供される。このとき、匿名化装置１０は、データ利用者がデータに含まれるＩＤの全区間を検索できるようにさせる場合、全区間の暗号鍵を提供し、ＩＤの一部のみの区間を検索できるようにする場合、一部の区間に該当する暗号鍵のみを提供する。例えば、図２の例では｜Ａ｜Ｂ｜Ｃ｜Ｄ｜Ｅ｜という区切りに対し、匿名化装置１０は、全区切りを検索させる場合に暗号鍵ＫＡ〜暗号鍵ＫＥを提供し、Ａ、Ｂ、Ｃの区間のみの検索を許可したい場合に暗号鍵ＫＡ、暗号鍵ＫＢ及び暗号鍵ＫＣを提供する。
匿名化装置１０は、このように、暗号鍵の提供を制限することにより、データ利用者の検索が可能な範囲を制限する。
【００３９】
図３は、本発明の一実施形態に係る匿名化装置１０の暗号化処理の例を示すフローチャートである。匿名化装置１０は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成され、以下の処理は、制御部（例えば、ＣＰＵ）が、ＯＳの下で所定のソフトウェアに従い実行する処理である。
【００４０】
ステップＳ１０１において、ＣＰＵ（分割手段１１）は、個人を特定するＩＤを含むデータを取得する。
【００４１】
ステップＳ１０２において、ＣＰＵ（分割手段１１）は、データに含まれるＩＤを階層構造に基づいて、区間１から区間ｎのｎ箇所に分割する。
【００４２】
ステップＳ１０３において、ＣＰＵ（索引作成手段１２）は、ステップＳ１０２において分割した区間１から区間ｎに対応する階層１から階層ｎのトライ木１００を生成する。
【００４３】
ステップＳ１０４において、ＣＰＵ（第１暗号化手段１３）は、ステップＳ１０３において生成したトライ木１００の各階層のノードを、ｎ個の暗号鍵で暗号化して、暗号化検索キーに置換する。より具体的には、ＣＰＵは、それぞれ互いに異なる暗号鍵１から暗号鍵ｎを、対応する階層１から階層ｎに用いて、トライ木１００の各階層のノードを暗号化し、暗号化検索キーをノードとするトライ木１００を生成する。その後、ＣＰＵは、処理を終了する。
【００４４】
［検索装置］
匿名化装置１０によって匿名化されたデータが提供される検索装置２０について説明する。
【００４５】
図４は、本発明の一実施形態に係る検索装置２０の構成を示すブロック図である。
検索装置２０は、入力手段２１と、第２暗号化手段２２と、検索手段２３とを備え、匿名化装置１０により匿名化されたデータを検索する。
【００４６】
入力手段２１は、複数の区間の少なくともいずれかを検索するために検索キーの入力を受け付ける。具体的には、入力手段２１は、ＩＤを構成する複数の区間のそれぞれと対応する文字列を、検索キーとして受け付ける。
【００４７】
第２暗号化手段２２は、検索キーを、対応する区間の暗号鍵で暗号化し、暗号化検索キーを生成する。具体的には、第２暗号化手段２２は、匿名化装置１０から提供された暗号鍵であって、入力手段２１によって受け付けられた検索キーに対応する区間に用いられた暗号鍵により、検索キーを暗号化し、暗号化検索キーを生成する。
【００４８】
検索手段２３は、暗号化検索キーにより、データを検索する。具体的には、検索手段２３は、第２暗号化手段２２によって生成された暗号化検索キーにより、提供されたデータに含まれる暗号化されたＩＤを構成する区間のうち、暗号鍵に対応する区間を、検索する。
検索手段２３は、ＩＤを構成する区間の最初の区間から検索しないで、検索キーに対応する区間のみを検索してもよい。
検索手段２３は、匿名化装置１０によって作成された、階層化した索引（例えば、トライ木１００）により検索してよい。匿名化装置１０は、トライ木１００により検索する場合、ＩＤの区間に対応する階層を検索する。
【００４９】
例えば、図２の例において、検索装置２０は、クエリとして「ＢＡＧ」という検索キーを受け付け、提供されている暗号鍵のうち階層に対応する暗号鍵で順に暗号化する。
すなわち、検索装置２０は、「Ｂ」を暗号鍵ＫＡ、「Ａ」を暗号鍵ＫＢ、「Ｇ」を暗号鍵ＫＣによって暗号化し、暗号化検索キーにより、匿名化装置１０によって作成されたトライ木１００（図２参照）の検索を行う。
次に、検索装置２０は、階層ＨＡでは「Ｂ」、階層ＨＢでは「Ａ」、階層ＨＣでは「Ｇ」と合致することを検出し、検索した結果をデータ利用者に返す。検索装置２０は、有るか否か（Ｂｏｏｌｅａｎ）を検索する場合は真（ＴＲＵＥ）／偽（ＦＡＬＳＥ）を返し、件数の場合は該当する箇所の件数を返す。
【００５０】
図５は、本発明の一実施形態に係る検索装置２０の検索処理の例を示すフローチャートである。検索装置２０は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成され、以下の処理は、制御部（例えば、ＣＰＵ）が、ＯＳの下で所定のソフトウェアに従い実行する処理である。
【００５１】
ステップＳ２０１において、ＣＰＵ（入力手段２１）は、検索キーを受け付ける。より具体的には、ＣＰＵは、ＩＤを構成する複数の区間のそれぞれと対応する文字列を、検索キーとして受け付ける。
【００５２】
ステップＳ２０２において、ＣＰＵ（第２暗号化手段２２）は、ステップＳ２０１において受け付けた検索キーを、暗号鍵で暗号化し、暗号化検索キーを生成する。より具体的には、ＣＰＵは、検索キーを、提供された暗号鍵であって検索キーに対応する区間に用いられた暗号鍵により、暗号化する。
【００５３】
ステップＳ２０３において、ＣＰＵ（検索手段２３）は、ステップＳ２０２において生成された暗号化検索キーにより、トライ木１００を検索する。より具体的には、ＣＰＵは、生成された暗号化検索キーにより、暗号化されたＩＤを構成する区間に対応する階層を、検索する。
【００５４】
ステップＳ２０４において、ＣＰＵ（検索手段２３）は、検索できたか否かを判断する。この判断がＹＥＳの場合、ＣＰＵは、処理をステップＳ２０５に移し、この判断がＮＯの場合、ＣＰＵは、処理をステップＳ２０６に移す。
【００５５】
ステップＳ２０５において、ＣＰＵ（検索手段２３）は、検索できたことを示す真（ＴＲＵＥ）を出力する。その後、ＣＰＵは、処理を終了する。
【００５６】
ステップＳ２０６において、ＣＰＵ（検索手段２３）は、検索できなかったことを示す偽（ＦＡＬＳＥ）を出力する。その後、ＣＰＵは、処理を終了する。
【００５７】
本実施形態によれば、匿名化装置１０は、ＩＤの区間を、互いに異なる暗号鍵を用いて、暗号化検索キーに置換する。暗号鍵のいずれかを提供されたデータ利用者は、検索キーを暗号鍵で暗号化することによりＩＤが秘匿された状態のままＩＤの特定の区間を検索できる。したがって、匿名化装置１０は、データに含まれる、個人に直接紐づくＩＤを秘匿しつつも、データ利用者ごとにＩＤの異なる区間の検索を可能とする。
さらに、匿名化装置１０は、ＩＤの区間を階層化した索引を作成するので、区間の組を高速に検索できる。
さらに、匿名化装置１０は、たとえ同一区間の検索が許可されるデータ利用者であっても異なる暗号鍵を用いるのでデータ利用者に提供した暗号化したＩＤを含むデータは、別のデータ利用者の暗号鍵によって、検索されない。
さらに、匿名化装置１０は、復号できない暗号化を行うので、秘匿性が高まる。
検索装置２０は、受け付けた検索キーを暗号鍵で暗号化することにより、ＩＤが秘匿された状態のままＩＤの特定の区間を検索できる。
【００５８】
さらに、匿名化装置１０は、例えば、あるデータ利用者に対しては先頭の一定区間のみの暗号鍵を提供し、別のデータ利用者には全区間の検索を可能にするために全区間の暗号鍵を提供するようにして、データ利用者のアクセスをコントロールする。
また、検索装置２０は、匿名化装置１０によって作成されたトライ木１００によって、検索したいＩＤの有無をＯ（ｌ）で高速に検索できる（Ｏはランダウの記号、ｌは検索キーの文字列の長さ）。
【００５９】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【００６０】
例えば、本実施形態において、ＩＤとして車両識別番号やクレジットカードの番号としたが、これに限られない。例えば、購買履歴データ等のデータに、販売店コードと時刻とを含むような場合、販売店コードと時刻とを連結させてＩＤとみなしてもよい。匿名化装置１０は、販売店コードと時刻とにより特定される個人を秘匿したまま、データ利用者による販売店の検索や、時刻の検索を可能とする。
【００６１】
匿名化装置１０による一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータ等にインストールされる。また、当該プログラムは、コンピュータ読み取り可能な記録媒体（例えば、ＣＤ−ＲＯＭのようなリムーバブルメディア等）に記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００６２】
１０    匿名化装置
１１    分割手段
１２    索引作成手段
１３    第１暗号化手段
２０    検索装置
２１    入力手段
２２    第２暗号化手段
２３    検索手段
【図１】
0006592301.tif 000002
【図２】
0006592301.tif 000003
【図３】
0006592301.tif 000004
【図４】
0006592301.tif 000005
【図５】
0006592301.tif 000006