(57)【要約】【課題】属性データの取り得る値のバリエーションが限られているような場合でも、秘匿検索における頻度分析をより困難にし、安全性を高めることを目的とする。【解決手段】入力データの取り得る値の数に応じた数のダミーデータを生成し、生成した各ダミーデータに所定の確率を割り当て、選択される確率が割り当てた確率になるように、生成したダミーデータから所定の数のダミーデータを選択する。入力データに対して所定の計算をして入力タグを生成するとともに、選択したダミーデータに対して前記所定の計算をしてダミータグを生成する。そして、入力データを暗号化した暗号化データに、入力タグとダミータグとを関連付けて記憶させる。【選択図】図１
2012248940.tif 000002
【特許請求の範囲】
【請求項１】
入力データを入力する入力部と、
前記入力部が入力した入力データを暗号化して暗号化データを生成する暗号化部と、
前記入力データの取り得る値の数を要素数として計測する要素数計測部と、
前記要素数計測部が計測した要素数に応じた数のダミーデータを生成するダミーデータ生成部と、
前記ダミーデータ生成部が生成したダミーデータから予め定められたｎ個（ｎは１以上の整数）のダミーデータを選択するダミーデータ選択部と、
前記入力データに対して所定の計算をして入力タグを生成するとともに、前記ダミーデータ選択部が選択したダミーデータに対して前記所定の計算をしてダミータグを生成する登録タグ生成部と、
前記登録タグ生成部が生成した入力タグとダミータグとを、前記暗号化部が生成した暗号化データに関連付けて記憶装置に記憶させる記憶部と
を備えることを特徴とするデータ生成装置。
【請求項２】
前記ダミーデータ生成部は、ダミーデータを生成するとともに、生成した各ダミーデータに所定の確率を割り当て、
前記ダミーデータ選択部は、選択される確率が前記ダミーデータ生成部が割り当てた確率になるように、前記ダミーデータ生成部が生成したダミーデータから予め定められたｎ個のダミーデータを選択する
ことを特徴とする請求項１に記載のデータ生成装置。
【請求項３】
前記ダミーデータ生成部は、前記ｎと、前記要素数計測部が計測した要素数ｙと、予め定められた値αとに基づき、ｋ＝（ｙ＋α）×ｎで計算されるｋ個のダミーデータを生成するとともに、ｉ＝１，．．．，ｋのｋ個のダミーデータが選択される確率ｐ（ｉ）を、Σｉ＝１ｋｐ（ｉ）＝１となるようにランダムに割り当て、
前記ダミーデータ選択部は、前記ダミーデータ生成部が生成したダミーデータからｎ個のダミーデータを選択する
ことを特徴とする請求項２に記載のデータ生成装置。
【請求項４】
前記記憶部は、前記入力タグと前記ダミーデータとをランダムな順に並べて、前記暗号化データに関連付けて記憶装置へ送信して記憶させる
ことを特徴とする請求項１から３までのいずれかに記載のデータ生成装置。
【請求項５】
前記データ生成装置は、さらに、
検索キーを入力する検索キー入力部と、
前記検索キー入力部が入力した検索キーに対して前記所定の計算をして検索タグを生成する検索タグ生成部と、
前記検索タグ生成部が生成した検索タグが関連付けられた暗号化データを、前記記憶装置から取得する取得部と
を備えることを特徴とする請求項１から４までのいずれかに記載のデータ生成装置。
【請求項６】
前記ダミーデータ選択部は、前記ダミーデータ生成部が生成したダミーデータから予め定められたｎ’個（ｎ’は１以上の整数）のダミーデータを選択し、
前記検索タグ生成部は、前記検索タグを生成するとともに、前記ダミーデータ選択部が選択したｎ’個のダミーデータに対して前記所定の計算をしてダミータグを生成し、
前記取得部は、前記検索タグと前記ダミータグとを前記記憶装置へ送信し、前記検索タグと前記ダミーデータとのいずれかが関連付けられた暗号化データを前記記憶装置から取得し、
前記データ生成装置は、さらに、
前記取得部が取得した暗号化データから前記検索タグが関連付けられた暗号化データを抽出する抽出部
を備えることを特徴とする請求項１から５までのいずれかに記載のデータ生成装置。
【請求項７】
前記ダミーデータ生成部は、前記検索タグと前記ダミーデータとをランダムな順に並べて前記記憶装置へ送信する
ことを特徴とする請求項６に記載のデータ生成装置。
【請求項８】
入力装置が、入力データを入力する入力工程と、
処理装置が、前記入力工程で入力した入力データを暗号化して暗号化データを生成する暗号化工程と、
処理装置が、前記入力データの取り得る値の数を要素数として計測する要素数計測工程と、
処理装置が、前記要素数計測工程で計測した要素数に応じた数のダミーデータを生成するダミーデータ生成工程と、
処理装置が、前記ダミーデータ生成工程で生成したダミーデータから予め定められたｎ個（ｎは１以上の整数）のダミーデータを選択するダミーデータ選択工程と、
処理装置が、前記入力データに対して所定の計算をして入力タグを生成するとともに、前記ダミーデータ選択工程で選択したダミーデータに対して前記所定の計算をしてダミータグを生成する登録タグ生成工程と、
処理装置が、前記登録タグ生成工程で生成した入力タグとダミータグとを、前記暗号化工程で生成した暗号化データに関連付けて記憶装置に記憶させる記憶工程と
を備えることを特徴とするデータ生成方法。
【請求項９】
入力データを入力する入力処理と、
前記入力処理で入力した入力データを暗号化して暗号化データを生成する暗号化処理と、
前記入力データの取り得る値の数を要素数として計測する要素数計測処理と、
前記要素数計測処理で計測した要素数に応じた数のダミーデータを生成するダミーデータ生成処理と、
前記ダミーデータ生成処理で生成したダミーデータから予め定められたｎ個のダミーデータを選択するダミーデータ選択処理と、
前記入力データに対して所定の計算をして入力タグを生成するとともに、前記ダミーデータ選択処理で選択したダミーデータに対して前記所定の計算をしてダミータグを生成する登録タグ生成処理と、
前記登録タグ生成処理で生成した入力タグとダミータグとを、前記暗号化処理で生成した暗号化データに関連付けて記憶装置に記憶させる記憶処理と
をコンピュータに実行させることを特徴とするデータ生成プログラム。
【請求項１０】
データを生成するデータ生成装置と、前記データ生成装置が生成したデータを記憶するデータベースサーバとを備えるデータベースシステムであり、
前記データ生成装置は、
入力データを入力する入力部と、
前記入力部が入力した入力データを暗号化して暗号化データを生成する暗号化部と、
前記入力データの取り得る値の数を要素数として計測する要素数計測部と、
前記要素数計測部が計測した要素数に応じた数のダミーデータを生成するダミーデータ生成部と、
前記ダミーデータ生成部が生成したダミーデータから所定の数のダミーデータを選択するダミーデータ選択部と、
前記入力データに対して所定の計算をして入力タグを生成するとともに、前記ダミーデータ選択部が選択したダミーデータに対して前記所定の計算をしてダミータグを生成する登録タグ生成部と、
前記登録タグ生成部が生成した入力タグ及びダミータグと、前記暗号化部が生成した暗号化データとを前記データベースサーバへ送信する記憶部と
を備え、
前記データベースサーバは、
前記記憶部が送信した入力タグとダミーデータと暗号化データとを関連付けて、データベースに登録する登録部
を備えることを特徴とするデータベースシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを暗号化したまま検索可能とする秘匿検索技術に関する。特に、頻度分析を困難にし、安全性を高めた秘匿検索技術に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングと呼ばれるコンピュータの利用形態が普及してきている。クラウドコンピューティングにおいては、利用者はデータの保管や管理などのコンピュータ処理をネットワーク経由でサービスとして利用することができる。
このような形態においては、データの所有者であるサービス利用者とデータの管理者であるサービス提供者とが異なる。そのため、サービス利用者の機密情報がサービス提供者に漏えいすることを防ぐために、サービス利用者が保存するデータを暗号化することが一般的になりつつある。データを暗号化したまま所望するデータを検索することができる秘匿検索のサービスが実現できれば、利用者の利便性が大きく向上する。
【０００３】
データを暗号化したまま検索する方法として、確定的暗号やハッシュを用いる方法がある。確定的暗号やハッシュでは、入力データに対する暗号化データが一意に決定されるため、暗号化されたままでも照合が可能となり、逐次検索やインデックスを用いた検索が実現できる。
特許文献１では、暗号化データと関連付けられたハッシュ値を用いることにより検索時の絞込みを高速化する方法について開示されている。このような確定的暗号やハッシュ値を用いる方法では、入力データの内容が直接漏えいすることはないが、データの出現頻度の分析が可能であるため、秘匿性が低下するという課題がある。
この課題に対して、特許文献２では、ハッシュ値にダミーデータを混入することにより、データの出現頻度をかく乱する方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２４２７４０公報
【特許文献２】特開２００５−７２９１７公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献２では、全文検索システムにおける単語等の検索対象文字列の出現頻度のかく乱を目的としている。特許文献２では、検索に用いられない文字列（句読点など）を、入力文書の文字列の出現頻度に近似した偏りを持つ文字列に置き換えている。したがって、特許文献２では、入力データの取り得る値のバリエーションが多く、かつ、不特定多数のデータが１レコード（１文書）に関連付けられるという特徴がある。
【０００６】
属性データ（例えば住所の都道府県名や市町村名等）のような取り得る値のバリエーションが限られており、１レコードで取れる値が排他的（１つのみ）であるようなデータベースがある。このようなデータベースに特許文献２に記載された発明を適用する場合には、以下の（１）（２）のような課題がある。
（１）追加するデータ（ダミーデータ）の出現頻度を元データの出現頻度に合わせると、取り得る値のバリエーションが限られることから、頻度分析が可能となり秘匿性が低下する。
（２）入力データの中の検索に用いられないデータをダミーデータに置き換えることはできず、ダミーデータを新たに追加する必要がある。
【０００７】
この発明は、属性データの取り得る値のバリエーションが限られているような場合でも、秘匿検索における頻度分析をより困難にし、安全性を高めることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係るデータ生成装置は、
入力データを入力する入力部と、
前記入力部が入力した入力データを暗号化して暗号化データを生成する暗号化部と、
前記入力データの取り得る値の数を要素数として計測する要素数計測部と、
前記要素数計測部が計測した要素数に応じた数のダミーデータを生成するとともに、生成した各ダミーデータに所定の確率を割り当てるダミーデータ生成部と、
選択される確率が前記ダミーデータ生成部が割り当てた確率になるように、前記ダミーデータ生成部が生成したダミーデータから所定の数のダミーデータを選択するダミーデータ選択部と、
前記入力データに含まれるデータに対して所定の計算をして入力タグを生成するとともに、前記ダミーデータ選択部が選択したダミーデータに対して前記所定の計算をしてダミータグを生成する登録タグ生成部と、
前記登録タグ生成部が生成した入力タグとダミータグとを、前記暗号化部が生成した暗号化データに関連付けて記憶装置に記憶させる記憶部と
を備えることを特徴とする。
【発明の効果】
【０００９】
この発明に係るデータ生成装置では、取り得る値の数（要素数）に応じてダミーデータ数を決定し、各ダミーデータが選択される頻度を任意に決定している。そのため、元データに近いデータの偏りを再現しながら、出現頻度をランダムとすることができ、秘匿検索における頻度分析をより困難にし、安全性を高めることができる。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１に係る秘匿化データベースシステム１００の構成の一例を示す図。
【図２】実施の形態１に係る秘匿化データベースシステム１００のデータ登録時の動作を示すフローチャート。
【図３】実施の形態１に係る秘匿化データベースシステム１００のデータ検索時の動作を示すフローチャート。
【図４】実施の形態１に係るダミー生成部２３０の構成の一例を示す図。
【図５】実施の形態１に係るダミー生成部２３０のデータ登録時の動作を示すフローチャート。
【図６】実施の形態１に係る秘匿化データベース３３０の表の構成の一例を示す図。
【図７】実施の形態１に係る秘匿化データベース３３０の表の構成の図６とは異なる一例を示す図。
【図８】実施の形態２に係る秘匿化データベースシステム１００の構成の一例を示す図。
【図９】実施の形態２に係る秘匿化データベースシステム１００のデータ検索時の動作を示すフローチャート。
【図１０】実施の形態２に係るダミー生成部２３０のデータ検索時の動作を示すフローチャート。
【図１１】クライアント２００とサーバ３００とのハードウェア構成の一例を示す図。
【発明を実施するための形態】
【００１１】
実施の形態１．
図１は、実施の形態１に係る秘匿化データベースシステム１００の構成の一例を示す図である。
秘匿化データベースシステム１００は、クライアント２００（データ生成装置）と、サーバ３００（データベースサーバ）とを備える。クライアント２００とサーバ３００とは、ネットワーク４００で接続される。ネットワーク４００はインターネットやイントラネット、ＬＡＮ、電話回線網などにより構成される。クライアント２００とサーバ３００とが１台のコンピュータに同居し、コンピュータ内部のバスやメモリ階層をネットワーク４００とする構成としてもよい。
入力データ５００は、サーバ３００へ登録されるデータであり、登録時にクライアント２００へ入力される。検索キー６００は、検索のキーとして利用されるデータであり、検索時にクライアント２００に入力される。検索結果データ７００は、検索キー６００により検索された結果、クライアント２００から出力されるデータである。
【００１２】
クライアント２００は、暗号化部２１０、登録データハッシュ部２２０（登録タグ生成部）、ダミー生成部２３０、検索キーハッシュ部２４０（検索タグ生成部）、照合部２５０（抽出部）、復号部２６０、ユーザインタフェース部２７０（入力部）、クライアント通信部２８０（記憶部）を備える。
サーバ３００は、登録部３１０、検索部３２０、秘匿化データベース３３０、サーバ通信部３４０を備える。秘匿化データベース３３０には、ハッシュデータフィールド３３１、暗号化データフィールド３３２の領域が設けられている。
【００１３】
図２は、実施の形態１に係る秘匿化データベースシステム１００のデータ登録時の動作を示すフローチャートである。
まず、クライアント２００側で処理が実行される。
（Ｓ１０１）にて、ユーザインタフェース部２７０は、入力データ５００を入力装置により入力する。（Ｓ１０２）にて、暗号化部２１０は、入力データ５００を処理装置により暗号化し、暗号化データを生成する。（Ｓ１０３）にて、ダミー生成部２３０は、入力データ５００に基づき処理装置によりダミーデータを生成する。（Ｓ１０４）にて、登録データハッシュ部２２０は、入力データ５００をハッシュしたハッシュデータ（入力タグ）と、ダミーデータをハッシュした追加ダミーデータ（ダミータグ）とを処理装置により生成する。（Ｓ１０５）にて、クライアント通信部２８０は、暗号化データとハッシュデータと追加ダミーデータとを、ネットワーク４００を経由してサーバ通信部３４０へ送信する。その際、ハッシュデータと追加ダミーデータの順序をランダムに並び替えて送信する。これにより、ハッシュデータと追加ダミーデータとが混合され、区別がつかないようになり、セキュリティ強度を高めることができる。
【００１４】
続いて、サーバ３００側で処理が実行される。
（Ｓ１０６）にて、登録部３１０は、暗号化データとハッシュデータと追加ダミーデータとを秘匿化データベース３３０に登録する。このとき、暗号化部２１０が生成した暗号化データは暗号化データフィールド３３２に登録され、登録データハッシュ部２２０が生成したデータ（ハッシュデータと追加ダミーデータ）は対応する暗号化データと関連付けられてハッシュデータフィールド３３１に登録される。
【００１５】
図３は、実施の形態１に係る秘匿化データベースシステム１００のデータ検索時の動作を示すフローチャートである。
まず、クライアント２００側で処理が実行される。
（Ｓ２０１）にて、ユーザインタフェース部２７０は、検索キー６００を入力装置により入力する。（Ｓ２０２）にて、検索キーハッシュ部２４０は、検索キー６００をハッシュしたハッシュデータ（検索タグ）を処理装置により生成する。なお、Ｓ１０４とＳ２０２とでは、同じハッシュ関数が用いられる。（Ｓ２０３）にて、クライアント通信部２８０は、検索キーのハッシュデータをネットワーク４００を経由してサーバ通信部３４０へ送信する。
【００１６】
続いて、サーバ３００側で処理が実行される。
（Ｓ２０４）にて、検索部３２０は、検索キーのハッシュデータをキーとしてハッシュデータフィールド３３１の検索を処理装置により行う。（Ｓ２０５）にて、検索部３２０は、検索ヒットするハッシュデータがあったどうかを処理装置により判定する。ヒットしなかった場合（Ｓ２０５でＮＯ）には、（Ｓ２０６）にて、サーバ通信部３４０は、検索結果（ヒット件数０）をクライアント通信部２８０へ送信する。一方、ヒットした場合（Ｓ２０５でＹＥＳ）には、（Ｓ２０７）にて、検索部３２０は、ヒットしたハッシュデータに関連付けられた暗号化データを暗号化データフィールド３３２から処理装置により抽出する。（Ｓ２０８）にて、サーバ通信部３４０は、検索結果の暗号化データをネットワーク４００を経由してクライアント通信部２８０へ送信する。
【００１７】
再び、クライアント２００側で処理が実行される。
（Ｓ２０９）にて、復号部２６０は、暗号化データを処理装置により復号する。（Ｓ２１０）にて、照合部２５０は、復号されたデータを検索キー６００と処理装置により照合し、合致するデータを検索結果とする。（Ｓ２１１）にて、ユーザインタフェース部２７０は、Ｓ２０６の検索結果又はＳ２１０の検索結果を検索結果データ７００として出力する。
【００１８】
以上に述べたように、秘匿化データベースシステム１００では、データの暗号化、復号、およびハッシュはクライアント２００側にて実行される。そのため、サーバ３００側へ入力データ５００や検索キー６００が元のまま（暗号化されない状態で）送られることはなく、サーバ３００側での盗聴に対して秘匿性が保たれる。
また、追加ダミーデータがハッシュデータに混合されるため、ハッシュデータフィールドの頻度分析の攻撃に対してセキュリティ強度を高めることができる。
【００１９】
図４は、実施の形態１に係るダミー生成部２３０の構成の一例を示す図である。
ダミー生成部２３０は、要素数計測部２３１、要素表２３２、ダミーデータ生成部２３３、ダミーデータ表２３４、追加ダミーデータ数設定部２３５、ダミーデータ選択部２３６を備える。
【００２０】
図５は、実施の形態１に係るダミー生成部２３０のデータ登録時の動作を示すフローチャートである。
（Ｓ３０１）にて、要素数計測部２３１は、ダミー生成部２３０に入力データ５００が入力される度に、入力データ５００が登録されるフィールドに出現するユニークな要素数を、要素表２３２を参照して計測する。例えば、要素数計測部２３１は、入力データ５００が県名を登録する県名フィールドに登録される場合には、県名フィールドに登録されている県の数をカウントする。要素数計測部２３１は、入力データ５００が要素表２３２における該当のフィールドに対応する欄に存在するかどうか確認し、存在しない場合には新たに要素表に追加する。要素数計測部２３１は、その上で要素表のその欄のエントリ数を要素数ｙとする。
（Ｓ３０２）にて、要素数計測部２３１は、要素数ｙに変更があるかどうかを処理装置により判定する。変更がある場合（Ｓ３０２でＹＥＳ）にはＳ３０３へ処理を進めてＳ３０３〜Ｓ３０６を実行し、変更がない場合（Ｓ３０２でＮＯ）にはＳ３０３〜Ｓ３０６を省略してＳ３０７へ処理を進める。
【００２１】
（Ｓ３０３）にて、ダミーデータ生成部２３３は、使用ダミーデータ数ｋを式（１）を用いて処理装置により計算する。
＜式（１）＞
ｋ＝（ｙ＋α）×ｎ
ここで、αは０以上の整数であり定数である。αは通常は０としてよい。しかし、要素数ｙが小さい（例えば１０以下などの）場合には、αを１以上の値とすることで使用ダミーデータのバリエーションを増やし、セキュリティ強度を高める。ｎは追加ダミーデータ数設定部２３５により設定された追加ダミーデータ数である。追加ダミーデータ数設定部２３５は、追加ダミーデータ数を、入力装置を介してユーザにより設定させ、データベースの表定義時に表毎、あるいは列毎に決定させる。追加ダミーデータ数が大きいほどセキュリティ強度を高めることができるが、検索対象となるハッシュデータフィールドのサイズが大きくなるため、ユーザの要件に応じて設定可能とする。
（Ｓ３０４）にて、ダミーデータ生成部２３３は、不足する使用ダミーデータを処理装置により生成する。使用ダミーデータは、入力データに対して特定の演算（例えば定数加算など）を行うことで生成してもよいし、擬似乱数を用いてランダムに生成してもよい。
（Ｓ３０５）にて、ダミーデータ生成部２３３は、ｉ＝１，．．．，ｋのｋ個の使用ダミーデータｘ（ｉ）の出現確率ｐ（ｉ）を、Σｉ＝１ｋｐ（ｉ）＝１となるように、処理装置によりランダムに割り当てる。なお、出現確率ｐ（ｉ）とは、使用ダミーデータｘ（ｉ）がダミーデータ選択部２３６により選択され、使用される確率である。
（Ｓ３０６）にて、ダミーデータ生成部２３３は、ダミーデータ表２３４を更新する。すなわち、ダミーデータ生成部２３３は、Ｓ３０４で新たに生成した使用ダミーデータのエントリを追加し、全エントリの出現確率ｐ（ｉ）をＳ３０５で生成した値に更新する。ダミーデータ表２３４は、使用ダミーデータｘ（ｉ）と出現確率ｐ（ｉ）とを対応付けて保存した表であり、簡単には２次元配列構造にて実現できるが、他のデータ構造としてもよい。
【００２２】
（Ｓ３０７）にて、ダミーデータ選択部２３６は、ダミーデータ表２３４を参照し、出現確率ｐ（ｉ）に基づいてｋ個の使用ダミーデータｘ（ｉ）の中からｎ個の使用ダミーデータｘ（ｉ）を選択して出力する。つまり、ダミーデータ選択部２３６は、使用ダミーデータｘ（ｉ）の選択される確率が出現確率ｐ（ｉ）となるように、ｋ個の使用ダミーデータｘ（ｉ）の中からｎ個の使用ダミーデータｘ（ｉ）を選択する。
【００２３】
以上述べたように、ダミー生成部２３０は、使用ダミーデータｘ（ｉ）の数を要素数に応じて決定する。これにより、使用ダミーデータｘ（ｉ）の偏りが元データに近い偏りになる。そして、使用ダミーデータｘ（ｉ）の出現確率ｐ（ｉ）をランダムに割り当てることで、ハッシュデータフィールド３３１に対する頻度分析をより困難にすることができ、セキュリティ強度が向上する。
【００２４】
図６は、実施の形態１に係る秘匿化データベース３３０の表の構成の一例を示す図である。図６（ａ）はユーザ表５１０を示す図であり、図６（ｂ）は秘匿化表３３３を示す図である。
ユーザ表５１０は、クライアント２００を用いてデータベースにアクセスするユーザから見た表の一例である。秘匿化表３３３は、ユーザ表５１０に対応して秘匿化データベース３３０に格納された表の一例である。秘匿化表３３３では暗号化データおよびハッシュデータの例を英数字の文字列で示しているが、任意のバイナリデータであってよい。
ユーザ表５１０中の列５２０を暗号化したデータが、秘匿化表３３３の暗号化データフィールド３３２に登録される。秘匿化表３３３には、列５２０に関連するハッシュデータフィールド３３１が追加されている。ハッシュデータフィールド３３１は、追加ダミーデータ数ｎに対して、入力データ５００をハッシュしたハッシュデータを登録する１列を加えたｎ＋１列で構成される。暗号化の有無およびハッシュデータの有無はユーザ表の列毎に設定することが可能である。ｒ列に対してハッシュデータを追加する場合にはｒ×（ｎ＋１）列が秘匿化表３３３に追加される。
ユーザ表５１０にＩＤ＝０００１のレコードがユーザインタフェース部２７０を通じて追加される場合、例えば入力データ５００は暗号化されて暗号化データ５０１となり、それに対応してハッシュデータ５０２，５０３として生成される（ｎ＝１の場合の例）。ハッシュデータ５０２，５０３は、一方が追加ダミーデータであり、他方が入力データ５００のハッシュデータである。しかし、前述の通り順序がランダム化されるため、どちらが追加ダミーデータであるかはわからない。したがって、ｎの値を増加させるにつれてセキュリティ強度を向上できる。
【００２５】
なお、秘匿化表３３３の列名も秘匿化することで更に頻度解析を行いにくくできる。また、ユーザ表５１０の列名と、秘匿化表３３３の列名との対応関係はユーザインタフェース部２７０にて管理され、ユーザからのアクセス時に適切に相互変換される。秘匿化表３３３は広く用いられているＲＤＢ（Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ）により実装できるが、その他のオブジェクト指向データベースや列指向データベースなどによる実装としてもよい。ＲＤＢであれば、ハッシュデータフィールド３３１に対してインデックスを生成することで高速な検索が可能となる。
【００２６】
図７は、実施の形態１に係る秘匿化データベース３３０の表の構成の図６とは異なる一例を示す図である。図７（ａ）はユーザ表５１０を示す図であり、図７（ｂ）は秘匿化表３３３の暗号化データフィールド３３２部分の表を示す図であり、図７（ｃ）は秘匿化表３３３のハッシュデータフィールド３３１部分の表を示す図である。
図６との違いは、秘匿化表３３３の暗号化フィールドと、ハッシュフィールドとが別の表で実装される点である。列５２０に関連するハッシュデータフィールド３３１が秘匿化表３３３の暗号化フィールドとは別の表に実装され、ユーザ表５１０の１列に対してハッシュデータフィールドも１列（Ｈ００１の列）となり、関連付けのためにＩＤをＨ００２に保持する。従って、追加ダミーデータ数ｎに対してｎ＋１行が１レコード分に対応する。ハッシュデータ５０２，５０３の順序がランダム化されるのは前述と同様である。検索時には２つの表を連携させる（ＪＯＩＮさせる）ことによりハッシュデータの検索結果から暗号化データの抽出が可能である。
【００２７】
ユーザインタフェース部２７０は、一般に用いられるデータベースのインタフェースを実装することで、ユーザの利便性を向上することができる。例えば、ユーザインタフェース部２７０は、標準ＳＱＬインタフェースに準拠した実装とすることができる。
図６に示した表を検索する場合の例では、ユーザが以下のような問合せ文を作成して検索を実行する。
＜ユーザにより入力される問合せ文＞
ＳＥＬＥＣＴ  ＊  ＦＲＯＭ  “ユーザ表５１０”  ＷＨＥＲＥ  “住所（県）”＝“神奈川”；
すると、秘匿化データベース３３０に対しては以下のような問合せに変換される。
＜変換された後の問合せ文＞
ＳＥＬＥＣＴ  ＊  ＦＲＯＭ  “秘匿化表３３３”  ＷＨＥＲＥ  “Ｃ０２０”＝“８ｄｆｋ３ｅ３”  ＯＲ  “Ｃ０２１”＝“８ｄｆｋ３ｅ３”；
つまり、「住所（県）」という列名は検索用のハッシュデータフィールドを指すＣ０２０、Ｃ０２１という列名に変換され、「神奈川」という検索キーはハッシュされて「８ｄｆｋ３ｅ３」に変換される。ハッシュフィールドは複数の列から成るため、複数の条件のＯＲ条件に変換される。検索結果を返す際にはＣ０２０以降の列データは検索専用であるため捨てられ、暗号化データが復号されて出力される。このような変換を行うことにより、ユーザは秘匿化データベースへトランスペアレントな（透過的な）アクセスが可能となる。
【００２８】
登録データハッシュ部２２０および検索キーハッシュ部２４０は、一般に用いられている任意のハッシュ関数を用いることができる。ハッシュデータの照合による検索を行うために、元データが決まれば一意にハッシュデータが決まるような関数であればよい。望ましくは、ＭＤ５やＳＨＡ−１などの暗号学的ハッシュ関数を用いることでセキュリティ強度を高めることができる。また、元データから暗号化データを一意に特定できる確定的暗号を用いることも可能である。
元データとハッシュデータとは１対１に対応するハッシュ関数を用いると、ハッシュデータの衝突が発生しないため、１つの検索キーに対する検索結果が一意に特定できる。その結果、照合部２５０での照合を省略することができるため、検索速度を向上させることができる。元データとハッシュデータとがｎ対１に対応するようなハッシュ関数を用いる場合には、ハッシュデータの頻度分析に対するセキュリティ強度が向上する。しかし、検索時に過剰検出が発生するため、照合部２５０にて復号データと検索キーとの照合を行う必要がある。
【００２９】
暗号化部２１０および復号部２６０は、一般に用いられている任意の暗号アルゴリズムを用いることができる。ＤＥＳやＡＥＳ，ＭＩＳＴＹ（登録商標）などの共通鍵暗号でもよいし、ＲＳＡ暗号のような公開鍵暗号を用いてもよい。但し元データから暗号化データを一意に特定できないようにした確率的暗号を用いる必要がある。暗号鍵は暗号化部２１０および復号部２６０で管理するか、またはクライアントから参照可能な鍵管理サーバにて管理することができる。暗号鍵はユーザ単位、データベース単位、表単位、カラム単位など、任意の単位で設定するようにしてもよい。
【００３０】
実施の形態２．
図８は、実施の形態２に係る秘匿化データベースシステム１００の構成の一例を示す図である。
図８に示す秘匿化データベースシステム１００と、図１に示す秘匿化データベースシステム１００との違いは、検索時にもダミーデータを用いる点である。図８では、ダミー生成部２３０から検索キーハッシュ部２４０への矢印が追加されている。
【００３１】
図９は、実施の形態２に係る秘匿化データベースシステム１００のデータ検索時の動作を示すフローチャートである。
図３を用いて説明した動作との違いを説明する。図９に示すＳ４０１は図３に示すＳ２０１と同様であり、図９に示すＳ４０６−Ｓ４１２は、図３に示すＳ２０５〜Ｓ２１１と同様である。
（Ｓ４０２）にて、ダミー生成部２３０は、ダミーデータを処理装置により生成する。（Ｓ４０３）にて、検索キーハッシュ部２４０は、検索キー６００をハッシュしたハッシュデータ（検索タグ）と、Ｓ４０２で生成されたダミーデータをハッシュした追加ダミーデータ（ダミータグ）とを処理装置により生成する。（Ｓ４０４）にて、クライアント通信部２８０は、検索キーのハッシュデータと追加ダミーデータとを、順序をランダム化することにより混合してサーバ通信部３４０へ送信する。（Ｓ４０５）にて、検索部３２０は、検索キーのハッシュデータと追加ダミーデータとをキーとして、いずれかにヒットすることを条件としてハッシュデータフィールド３３１の検索を行う。
なお、ダミーデータのハッシュデータによる検索で検索結果に追加される過剰検出は、Ｓ４１１において除去され、検索結果は正しい結果となる。
【００３２】
図１０は、実施の形態２に係るダミー生成部２３０のデータ検索時の動作を示すフローチャートである。
図５に示すデータ登録時とは異なり、データ検索時にはダミーデータ表２３４の更新を行わない。そのため、単に、（Ｓ５０１）にて、ダミーデータ選択部２３６は、ダミーデータ表２３４を参照し、出現確率ｐ（ｉ）に基づいてｋ個の使用ダミーデータｘ（ｉ）の中からｎ個の使用ダミーデータｘ（ｉ）を選択して出力する。なお、ｎは登録時に用いる変数とは異なるｎ’を検索専用に設定することにしてもよい。
【００３３】
以上述べたように、実施の形態２に係る秘匿化データベースシステム１００では、検索時にもダミーデータを用いることにより、検索条件中の検索キーの頻度解析に対してもセキュリティ強度を高めることができる。
【００３４】
図１１は、クライアント２００とサーバ３００とのハードウェア構成の一例を示す図である。
図１１に示すように、クライアント２００とサーバ３００とは、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【００３５】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【００３６】
プログラム群９２３には、上記の説明において「暗号化部２１０」、「登録データハッシュ部２２０」、「ダミー生成部２３０」、「検索キーハッシュ部２４０」、「照合部２５０」、「復号部２６０」、「ユーザインタフェース部２７０」、「クライアント通信部２８０」、「登録部３１０」、「検索部３２０」、「秘匿化データベース３３０」、「サーバ通信部３４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「入力データ５００」、「検索キー６００」、「検索結果データ７００」、「ハッシュデータ」、「追加ダミーデータ」、「仕様ダミーデータ」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００３７】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【００３８】
１００  秘匿化データベースシステム、２００  クライアント、２１０  暗号化部、２２０  登録データハッシュ部、２３０  ダミー生成部、２３１  要素数計測部、２３２  要素表、２３３  ダミーデータ生成部、２３４  ダミーデータ表、２３５  追加ダミーデータ数設定部、２３６  ダミーデータ選択部、２４０  検索キーハッシュ部、２５０  照合部、２６０  復号部、２７０  ユーザインタフェース部、２８０  クライアント通信部、３００  サーバ、３１０  登録部、３２０  検索部、３３０  秘匿化データベース、３３１  ハッシュデータフィールド、３３２  暗号化データフィールド、３３３  秘匿化表、３４０  サーバ通信部、４００  ネットワーク、５００  入力データ、５１０  ユーザ表、６００  検索キー、７００  検索結果データ。
【図１】
2012248940.tif 000003
【図２】
2012248940.tif 000004
【図３】
2012248940.tif 000005
【図４】
2012248940.tif 000006
【図５】
2012248940.tif 000007
【図６】
2012248940.tif 000008
【図７】
2012248940.tif 000009
【図８】
2012248940.tif 000010
【図９】
2012248940.tif 000011
【図１０】
2012248940.tif 000012
【図１１】
2012248940.tif 000013