暗号化転置インデックステーブルに対するｋ−匿名性更新のための方法および装置
【課題】 暗号化された転置インデックステーブルに対するｋ−匿名性更新のための方式と装置を提案する。
【解決手段】 この方法は、外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）。
【解決手段】 この方法は、外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報アップデート技術の分野に関し、特に、暗号化転置インデックステーブルに対するｋ−匿名（k-anonymity）更新のための方法および装置に関する。ｎ行のデータがあると仮定すると、各行はそれぞれ１つ以上の暗号化された項目と共にインデックスとして暗号化されたキーワードを有する。ｎ行のうち１つが更新しようとする目標行として選択されていると仮定する。すなわち、新たな暗号化された項目を該当する行に追加し、あるいは、暗号化された項目を該当する行から削除しようとする場合である。本発明の目的は、ｋ−匿名性を実現することにある。すなわち、更新の前と後にｎ行を観察する好奇心が強いが誠実な攻撃者（curious but honest attacker：不正に情報を入手しようとする攻撃者）は、どの行が目標行かを多くても確率１／ｋで見分けることができる。ここで、ｋは予め定義されたセキュリティパラメータである。
【背景技術】
【０００２】
現在、２つの増加傾向が出現している。すなわち、個人のプライバシーの保護に対する普遍的な関心と、ストレージサーバに対して外部委託する個人データである。ストレージサーバに対して個人データを外部委託する利用において、外部委託したドキュメントとそれらについて構築された転置インデックスの両方とも、機密保持とプライバシー上の理由のために暗号化形式が採用される。暗号化転置インデックステーブル（Ｅｎｃｒｙｐｔｅｄ Ｉｎｖｅｒｔｅｄ Ｉｎｄｅｘ Ｔａｂｌｅ：以下、「ＥＩＩＴ」と称する）は、様々な長さの多くの無関係な行から構成される代表的なデータ構造を有し、完全には信頼できないストレージサーバ（semi-trusted storage server）が検索者のために指定の暗号化キーワードの整合結果を見つけ出すことを可能にする機能を提供する。専用の暗号化キーワードでマーク付けされた各暗号化行は、そのキーワードに関する全ての暗号化ファイル情報を含む。暗号化キーワードの値は「行識別子」と呼ばれ、行内の暗号化されたファイル情報は「データ項目」と呼ばれる。
【０００３】
同じ出願人による２つの特許出願、「高速検索可能な暗号化のための方法、装置及びシステム」の名称の中国特許出願２００８１００９８３５９．１（特許文献１）と中国特許出願２００８１０１４５０８３．８（特許文献２）が暗号化された転置インデックステーブル（ＥＩＩＴ）を構築する方法を開示している。ＥＩＩＴは何千もの行を有する場合がある。上述したｎ行は、ＥＩＩＴから取り出された一部あるいはＥＩＩＴの全行である。
【０００４】
ドキュメントが更新され、新たなキーワードがドキュメントに追加される場合（あるいは、キーワードがドキュメントから削除される場合）、唯一の行、すなわち、ＥＩＩＴの目標行を更新する必要がある。
【０００５】
しかしながら、単にＥＩＩＴの目標行を更新することは、信頼されていない当事者（すなわち、ＥＩＩＴを格納するストレージサーバ）に対して、キーワードとドキュメント間の関連を露呈することになる。図１は、この問題を直感的な方法で示している。
【０００６】
中国特許出願２００８１００９８３５９．１（特許文献１）と中国特許出願２００８１０１４５０８３．８（特許文献２）には、「高速検索可能な暗号化方式」（Ｆａｓｔ Ｓｅａｒｃｈａｂｌｅ Ｅｎｃｒｙｐｔｉｏｎ Ｍｅｔｈｏｄ（ＦＳＥ）と呼ばれるいくつかの技術的解決法が存在する。図２、図３を参照してその方法を概説する。図２はＦＳＥ方式および装置について説明する概略図である。また、図３は、ＦＳＥ方式および装置が暗号化された行をどのように更新するかを示す概略図である。
（１）データ所有者は、まず、暗号化されたターゲットドキュメント（ＥＴＤ）について実行される更新に従ってストレージサーバから希望の暗号化された行をすべて取得し、取得した行を出力する。
（２）暗号化された行について、データ所有者は、マスターキーを使用して、その行内のデータ所有者に知られている所定の位置に位置する特別項目Ｅ（マスターキー，行キー）の復号を実行し、行キーを取得する。その後、データ所有者は、行キーを使用して項目のプレーンテキスト形式を取得することができる。
（３）削除すべきオリジナルのプレーンテキスト項目について、データ所有者はこの行からそれを除去する。また、追加すべき新たなプレーンテキスト項目について、データ所有者はその行にそれを追加する。
（４）データ所有者は、すべての更新行のプレーンテキスト形式と暗号キーを入力とし、暗号キーで更新行のプレーンテキストを一つずつ暗号化し、特別項目を形成するために、マスターキーで暗号キーに対応する復号キー（新たな行キー）を暗号化し、それらの暗号化形式を出力し、ストレージサーバにそれらをアップロードする。
【０００７】
この更新ルーチンの明白な欠点は、それらは両方とも暗号化された形式であるけれども、ストレージサーバがＥＩＩＴとＥＴＤ内の更新行間の引用関係を知っていることである。
最も関する技術分野においては、修正済（項目が追加されまたは削除された）ドキュメントと暗号化された索引テーブルの行間の関連は、インデックステーブルが暗号化されていても、更新の前と更新の後の行の長さを比較することにより露呈することができる。それはセキュリティとプライバシーの観点からすると危険である。
【０００８】
その危険性は更新回数が増加するに従って激化するであろう。また、プライバシーはひどく危険にさらされるだろう。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】中国特許出願２００８１００９８３５９．１
【特許文献２】中国特許出願２００８１０１４５０８３．８
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したように、特許文献１及び特許文献２に記載される更新ルーチンの明白な欠点は、それらは両方とも暗号化された形式であるけれども、ストレージサーバがＥＩＩＴとＥＴＤ内の更新行間の引用関係を知っていることである。最も関する技術分野においては、修正済（項目が追加されまたは削除された）ドキュメントと暗号化された索引テーブルの行間の関連は、インデックステーブルが暗号化されていても、更新の前と更新の後の行の長さを比較することにより露呈することができる。それはセキュリティとプライバシーの観点からすると危険である。また、その危険性は更新回数が増加するに従って激化する。また、プライバシーはひどく危険にさらされることになる。
【課題を解決するための手段】
【００１１】
ｎ行（以下、ｎ行の集合を「ｎサイズ行集合」と称し、略して「ＲＳ」と称する）の一行が最初の更新のための目標行として選択されると仮定する。すなわち、１つの新たな暗号化された項目が目標行に追加され、あるいは、１つの暗号化された項目が目標行から削除される場合に、更新の前と後にｎ行を観察する好奇心が強いが誠実な攻撃者（curious but honest attacker）がどの行が目標行かを多くても確率１／ｋで見分けるという可能性を保証する。ここで、ｋは予め定義されたセキュリティパラメータである。
【００１２】
端的に言えば、更新を実行する時各行にダミーを導入することにより上記の目的を達成する。
【００１３】
本発明の第１の態様によれば、暗号化された転置インデックステーブルに対するｋ−匿名性更新方法であって、外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とする。
【００１４】
好ましい態様では、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行に１つの新たな復号したデータ項目を追加し、復号したデータ項目の残るｎ−１行の各行に１つのダミーに追加することを特徴とする。
【００１５】
好ましい態様では、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする。
【００１６】
好ましい態様では、復号ステップの前に、暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、暗号化されたデータ項目のｎ行がすべて初期化された行であれば、復号ステップを実行するステップを含み、目標行更新と疑似演算実行ステップが、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを決定し、目標行の内に少なくとも１つのダミーがあれば、更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、ｎは
【数１】
として決定されることを特徴とする。さらに、目標行の内にダミーがなければ、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持する。
【００１７】
好ましい態様では、復号ステップの前に、暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、暗号化されたデータ項目のｎ行がすべて初期化された行ならば、復号ステップを実行するステップとを含み、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする。
【００１８】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、復号ステップを実行し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００１９】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする。
【００２０】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする。
【００２１】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさない場合、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００２２】
好ましい態様では、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする。
【００２３】
好ましい態様では、初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする。
【００２４】
好ましい態様では、暗号化ステップの前に、更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除することを特徴とする。
【００２５】
本発明の第１の態様によれば、暗号化された転置インデックステーブルに対するｋ−匿名更新のための装置であって、外部記憶装置から暗号化されたデータ項目のｎ行を取得する取得ユニットと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号する復号ユニットと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成する更新ユニットと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化する暗号化ユニットと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするアップロードユニットとを備え、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とする。
【００２６】
好ましい態様では、更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行に１つの新たな復号データ項目を追加し、復号されたデータ項目の残るｎ−１行の各行に１つのダミーを追加することを特徴とする。
【００２７】
好ましい態様では、更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする。
【００２８】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、前記更新ユニットは、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを判定し、目標行の内に少なくとも１つのダミーがあれば、更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、ｎは
【数２】
として決定されることを特徴とする。また、目標行の内にダミーがなければ、前記更新ユニットは、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持する。
【００２９】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする。
【００３０】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記初期化ユニットは、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００３１】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記取得ユニットは、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする。
【００３２】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする。
【００３３】
好ましい態様では、初期化ユニットが、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさないと判定すると、前記初期化ユニットは、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００３４】
好ましい態様では、初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする。
【００３５】
好ましい態様では、初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする。
【００３６】
好ましい態様では、更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除する調整ユニットをさらに備えることを特徴とする。
【００３７】
本発明の方法では、目標行に１つの新たな項目を追加する場合、同時に他のｎ−１のダミー行のそれぞれに対してダミー項目を追加する。これにより、全てのｎ行の暗号化データが変更されるが、全てのｎ行の長さが「１」だけ増加する。目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。他のｎ−１のダミー行の長さは、そのままである。このように、暗号化されたデータはすべてのｎ行において変更されるが、全てのｎ行の長さは不変である。これにより、ｎがｎ≧ｋとしてセットされる場合、ＲＳのｎ行のうちの目標行は、好奇心が強いが誠実な攻撃者によって最大限でも確率１／ｋで識別されることになる。
【００３８】
本発明の他の方法では、目標行に１つの新たな項目を追加する場合、目標行内に少なくとも１つのダミーが存在する場合、このダミーを新たな項目に置き換え、ＲＳ内の任意の行に他のダミーを追加する。他方、目標行がダミーを有しない場合は、単に目標行に新たな項目を追加し、付加的なダミーを他のｎ−１行に追加しない。このように、更新済みＲＳの内では、暗号化データはすべてのｎ行において変更されるが、目標行は、１項目だけ増加し（目標行内にダミーが無い場合）、あるいはｎ−１個の他の行の１行が１項目だけ増加する（目標行内に少なくとも１つのダミーがある場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、次に、選択した行から１つのダミーを削除する。取得したｎ行内にダミーが全く存在しない最悪の削除状況では、置き換えステップで目標行に１つの新たなダミーを導入する。すなわち、この処理中、少なくとも１つのダミーを有する行を必ず見つけ出すことができる。このように、暗号化データはすべてのｎ行において変更されるが、更新済みＲＳの内では、目標行が、１項目だけ減少し（選択した行が目標行である場合）、あるいは他のｎ−１行の１行が１項目だけ減少する（選択した行が目標行でない場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００３９】
これにより、追加の場合、ｎが
【数３】
としてセットされ、削除の場合、ｎがn ≧kとしてセットされると、ＲＳのｎ行のうちの目標行は、好奇心が強いが誠実な攻撃者によって最大限でも確率１／ｋで識別されることになる。更に、より少ないダミーが、同じセキュリティの強度の維持しつつスペース効率を向上させるために導入されるだろう。すなわち、本発明の他の方法によれば、１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、ダミーの数は固定的で変わらない。
【００４０】
本発明のさらに他の方法では、一定の条件が満たせば、スペース効率をさらに向上することができる。具体的には、ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。もし、s-1≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、各行からＳ−１個のダミーが削除される。これにより、より少ないダミーが同じセキュリティの強度の維持しつつ導入される。
【発明の効果】
【００４１】
本発明は、所定のセキュリティパラメータｋに対して、好奇心が強いが誠実な攻撃者が更新された行集合から目標行を識別する確率を多くても１／ｋとすることを可能にする。
【図面の簡単な説明】
【００４２】
本発明の前述した目的、特徴及び効果と他の目的、特徴及び効果は、添附の図面を参照した本発明の限定されない実施の形態に関する以下の説明からより明らかになるであろう。
【図１】好奇心が強いが誠実な攻撃者が修正済の行をどのように見つけ出すかを示す概略図である。
【図２】ＦＳＥ方式および装置について説明する概略図である。
【図３】ＦＳＥ方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図４】本発明の第１の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図５】本発明の第１の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図６】本発明の第１の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図７】本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図８】本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図９】本発明の第２の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図１０】本発明の第３の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図１１】本発明の第３の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図１２】本発明の第３の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【発明を実施するための形態】
【００４３】
以下、図面を参照して本発明について説明する。以下の説明において、幾つかの特定の実施の形態は説明のみの目的で使用される。これらの実施の形態はあくまで例示であり、本発明を限定するものとして理解してはならない。また、本発明の理解が多少曖昧になる可能性はあるが、従来技術の構成・構造の説明は省略する。
【００４４】
ｋ−匿名性更新の場合、二人の当事者（すなわちデータ所有者と好奇心が強いが誠実な観察者）が関与する。ストレージサーバは明らかに好奇心が強いが誠実な観察者（curious
but honest observer）である。具体的な工程を説明する前に、いくつかの特殊記号および略語を以下に定義する。
ｋ：予め定義されたセキュリティパラメータ、定数
ｎ：パラメータｎは、ｋ−匿名性更新を満たす毎に取得された行の合計数である。また、ｎは行集合ＲＳの大きさである。
好奇心が強いが誠実な攻撃者：攻撃者は予め定められた工程を遵守するが、保護された情報を探りたい。
ＡＩＭ：ｋ−匿名方式に基づいてデータ項目を追加する方法。
ＤＩＭ：ｋ−匿名方式に基づいてデータ項目を削除する方法。
ＥＩＩＴ：暗号化転置インデックステーブル（Ｉｎｖｅｒｔｅｄ Ｉｎｄｅｘ Ｔａｂｌｅ）。より具体的には、ＥＩＩＴはｍ行から成る。各行は、指定されたキーワードに関する暗号化ファイル情報とおよび（または）１つ以上の乱数（ダミー）を含んでおり、キーワードとマスターキーから導き出した任意の値でマーク付けされる。
ＲＳ：ｎサイズの行集合、１つの目標行とｎ−１個のダミー行を含んでいる。
【００４５】
本発明は３つの実施の形態を含んでいる。以下に、本発明の詳細な説明を記載する。
【００４６】
（第１の実施の形態）
第１の実施の形態に関して、行集合（＝ｎ）のサイズが所定のセキュリティパラメータｋに対してｎ≧ｋとしてセットされる場合（ｎとｋは正の整数）、好奇心が強いが誠実な攻撃者が更新された行集合から目標行を識別する確率は最大で１／ｋである。
【００４７】
図４および図５は、本発明の第１の実施の形態によるｋ−匿名更新方法および装置を説明する概略図である。追加する場合のブロック図を図４に示し、削除する場合のブロック図を図５に示す。
【００４８】
（第１の実施の形態におけるＡＩＭ）
目標行に１つの新たな項目を追加する場合、同時に他のｎ−１のダミー行のそれぞれに対してダミー項目を追加する。これにより、全てのｎ行の暗号化データが変更されるが、全てのｎ行の長さが「１」だけ増加する。
【００４９】
第１の実施の形態における１つの新たな項目の追加に関する構成要素を図４を参照して以下に説明する。
（１）ＲＳ取得ユニットは、外部記憶装置（信頼できない記憶装置−外部ＥＩＩＴユニット）から、暗号化された形式でｎサイズのＲＳを取得する。
ｎは所定の値ｋから計算される。
ここで、所定の値ｋは、ＲＳ取得ユニットに予め設定されるか、あるいは利用者によって入力される。
（２）キー記憶ユニットは、ＲＳ内のデータ項目を暗号化し、復号するために使用するマスターキーを格納する。
（３）前処理ユニットは、取得した暗号化ＲＳおよびマスターキーを入力として、ＲＳ内の暗号化された項目をすべて復号し、もとのＲＳのプレーンテキスト形式を出力する。
この復号において、まず、マスターキー（master key）が行キーを得るための復号を実行するのに使用される。次に、行鍵キーがもとのＲＳのプレーンテキスト形式を得るための復号を実行するのに使用される。
（４）入力項目記憶ユニットは、追加する新たな項目を格納する。
（５）入力ＲＳ記憶ユニットは、前処理ユニットの出力を格納する。
（６）項目挿入ユニットは、追加する項目およびＲＳのプレーンテキスト形式を入力とし、目標行に項目を追加し、目標行に追加された入力項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（７）第１レベルＲＳ記憶ユニットは、項目挿入ユニットの出力を格納する。
（８）ダミー挿入ユニットは、更新済みＲＳを入力とし、他のｎ−１のダミー行のそれぞれに対してダミー項目を追加し、また目標行に追加された入力項目と、他のｎ−１のダミー行のそれぞれに追加されたダミー項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（９）第２レベルＲＳ記憶ユニットは、ダミー挿入ユニットの出力を格納する。
（１０）後処理ユニットは、更新済みＲＳのプレーンテキスト形式およびマスターキーを入力とし、更新済みＲＳ内の項目を一行づつすべて再暗号化し、更新済みＲＳの暗号化形式を出力する。
この暗号化において、１つの暗号キーあるいは複数の暗号キーが更新済みＲＳ内のそれぞれの行における項目を再暗号化するために使用される。また、マスターキーは、特別項目を形成するためにそれぞれの行について使用された暗号キーに対応する解読キーあるいは暗号キー（新たな行キー（row key））を暗号化するために使用される。それにより、更新済みＲＳの暗号化形式が生成される。
（１１）更新ＲＳ記憶ユニットは、後処理ユニットの出力を格納する。
（１２）ＲＳアップロードユニットは、暗号化形式のｎサイズの更新済みＲＳを入力とし、外部記憶装置にｎサイズの更新済みＲＳをアップロードし、アップロード状態によって「真」か「偽」の何れかを出力する（すなわち、アップロードが成功すれば、「真」を返却し、そうでなければ、「偽」を返却する）。
【００５０】
ここで、マスターキーおよび／または行キーとしては、対称暗号化スキーム（symmetric cryptography scheme）において使用される対称キー、ペアワイズ暗号化スキームにおいて使用されるペアの公開キーと秘密キー、あるいは周知の暗号化スキームにおいて使用される他のキーを利用することが可能である。本発明において、暗号化／復号スキームは特に限定されない。
【００５１】
（第１の実施の形態におけるＤＩＭ）
目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。他のｎ−１のダミー行の長さは、そのままである。このように、暗号化されたデータはすべてのｎ行において変更されるが、全てのｎ行の長さは不変である。
【００５２】
第１の実施の形態における１つの無用な項目の削除に関する構成要素を図５を参照して以下に説明する。
（１）ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力ＲＳ記憶ユニット、第１レベルＲＳ記憶ユニット、後処理ユニット、更新ＲＳ記憶ユニットとＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＡＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）入力項目記憶ユニットは、削除項目を格納する。
（３）項目置換ユニットは、削除項目およびＲＳのプレーンテキスト形式を入力とし、削除する項目の位置を特定し、目標行内のその項目をダミーで置き換え、ダミーと置き換えられた削除項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
【００５３】
（第１の実施の形態の具体例）
図６は、本発明の第１の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第１の実施の形態による新たな１項目を追加する場合と１項目を削除する場合を、直感的に理解できるであろう。
【００５４】
最も関連する技術と比較して、行集合（＝ｎ）のサイズが所定のセキュリティパラメータｋに対してｎ≧ｋとしてセットされる場合（ｎとｋは正の整数）、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率は最大で１／ｋである。
【００５５】
（第２の実施の形態）
１つの新たな項目を追加する場合、第１の実施の形態においては、ｎ−１個のダミーが追加される。また、１つの暗号化項目を削除する場合、第１の実施の形態においては、１個のダミーが追加される。空間効率を向上させるためには、同じセキュリティの強度を保持しながら、より少数のダミーを導入すべきである。
【００５６】
第２の実施の形態においては、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率が最大で１／ｋであるという要求を満たすために、ＲＳ（＝ｎ）のサイズが、所定のセキュリティパラメータｋに対して、追加の場合、
【数４】
としてセットされ、削除の場合、n ≧kとしてセットされる。ここで、ｎとｋは正の整数である、ｅは、数学的な定数（「オイラーの数」、ｅ≒２．７１８２８として知られている）である。また、
【数５】
は上位の整関数であり、
【数６】
は、Ｘより大きいか或いは等しい最も小さな整数を示している。
【００５７】
図７および図８は、本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。追加する場合のブロック図を図７に示し、削除する場合のブロック図を図８に示す。
【００５８】
（第２の実施の形態におけるＡＭＩ）
目標行に１つの新たな項目を追加する場合、目標行内に少なくとも１つのダミーが存在する場合、このダミーを新たな項目に置き換え、ＲＳ内の任意の行に他のダミーを追加する。他方、目標行がダミーを有しない場合は、単に目標行に新たな項目を追加し、付加的なダミーを他のｎ−１行に追加しない。このように、更新済みＲＳの内では、暗号化データはすべてのｎ行において変更されるが、目標行は、１項目だけ増加し（目標行内にダミーが無い場合）、あるいはｎ−１個の他の行の１行が１項目だけ増加する（目標行内に少なくとも１つのダミーがある場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００５９】
第２の実施の形態における１つの新たな項目の追加に関する構成要素を図７を参照して以下に説明する。
（１）ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力項目記憶ユニット、入力ＲＳ記憶ユニット、第１レベルＲＳ記憶ユニット、更新ＲＳ記憶ユニット、後処理ユニット、ＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＡＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）項目挿入ユニットは、追加する項目およびＲＳのプレーンテキスト形式を入力とし、目標行内に少なくとも１つのダミーがあれば、目標行内のダミーを入力項目と置き換え、そうでなければ目標行に直接入力項目を追加する。
項目挿入ユニットは、置き換えによって目標行に追加した新たな項目あるいは目標行に直接追加した新たな項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（３）ダミー挿入制御ユニットは、項目挿入ユニットにおいて置き換えが生じるかどうかを記録し、その状態によって「真」か「偽」の何れかを出力する（すなわち、置き換えが生じれば、「真」を返却し、そうでなければ、「偽」を出力する）。
（４）ダミー挿入ユニットは、更新済ＲＳのプレーンテキスト形式を入力とし、ＲＳから１行を任意に選択し、置き換えが生じると（すなわち、ダミー挿入制御ユニットが「真」を出力すると）、選択した行に１つのダミーを追加する。そうでなければ（すなわち、ダミー挿入制御ユニットが「偽」を出力すると）、ダミー挿入ユニットは、項目挿入ユニットから出力される更新済みＲＳのプレーンテキスト形式に対して何も行わない。ダミー挿入ユニットは、追加した別のダミーを有する更新済みＲＳのプレーンテキスト形式を出力する。
（５）第２レベルＲＳ記憶ユニットは、ダミー挿入ユニットの出力を格納する。
【００６０】
（第２の実施の形態におけるＤＩＭ）
目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、次に、選択した行から１つのダミーを削除する。
取得したｎ行内にダミーが全く存在しない最悪の削除状況では、最初のステップで取得したオリジナルのｎ行の１つに１つの新たなダミーを導入する。
すなわち、この処理中、少なくとも１つのダミーを有する行を必ず見つけ出すことができる。
このように、暗号化データはすべてのｎ行において変更されるが、更新済みＲＳの内では、目標行は、１項目だけ減少し（選択した行が目標行である場合）、あるいはｎ−１個の他の行の１行が１項目だけ減少する（選択した行が目標行でない場合）。
すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００６１】
第２の実施の形態における１つの無用な項目の削除に関する構成要素を図８を参照して以下に説明する。
（１） ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力項目記憶ユニット、入力ＲＳ記憶ユニット、項目置換ユニット、第１レベルＲＳ記憶ユニット、更新ＲＳ記憶ユニット、後処理ユニットとＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＤＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）ダミー削除ユニットは、更新済ＲＳのプレーンテキスト形式を入力とし、ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、選択した行から１つのダミーを削除する。
ダミー削除ユニットは、１つのダミーと置き換えられて削除される項目及び任意に選択したＲＳの行から削除された別のダミー（ただ１つのダミー）を有する更新済ＲＳのプレーンテキスト形式を出力する。
（３）第２レベルＲＳ記憶ユニットは、ダミー削除ユニットの出力を格納する。
【００６２】
（第２の実施の形態の具体例）
図９は、本発明の第２の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第２の実施の形態による新たな１項目を追加する場合と１項目を削除する場合を、直感的に理解できるであろう。
【００６３】
第１の実施の形態と比較して、第２の実施の形態においてはスペース効率が向上する。
１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、追加ダミーの数は「０」である。すなわち、固定的で変わらない。
さらに、ＲＳ（＝ｎ）のサイズが、所定のセキュリティパラメータｋに対して、追加の場合、
【数７】
としてセットされ、削除の場合、n ≧kとしてセットされる場合、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率が最大で１／ｋである。
【数８】
は、Ｘより大きいか或いは等しい最も小さな整数を示している。
【００６４】
更に、第２の実施の形態のＡＩＭあるいはＤＩＭにおいては、各行の長さが最初の初期化の後に２以上であること、また、取得したＲＳ（ｎ行）内の全ての行が初期化されることを保証するために初期化処理が導入される、
【００６５】
（初期化処理）
各行において、特別項目Ｅ（master
key、row key）が、初期化処理がその行に対して実行されているかどうかを識別するために使用される。
例えば、Ｅ（master key、row
key）は、専用のシンボル「＄」を導入することによってＥ（master key、row key｜｜＄）へ拡張される。
項目Ｅ（master key、row
key）は、その行が初期化されていない行であることを示し、一方、項目Ｅ（master key、row key｜｜＄）は、その行が初期化された行であることを示している。
ＥＩＩＴ中に合計でｍ行存在すると仮定した場合、初期化処理は以下の説明のように実行される。
（１）所定のセキュリティパラメータｋについて、
【数９】
を計算する。
ｍ≧ｎであれば、（２）に進み、そうでなければ初期化処理を中止する。
（２）取得したｎ行について、初期化された行であるかどうかを一行ずつ全ての行をチェックする。
初期化されていない行である場合は、少なくとも１つのダミーを追加し、Ｅ（master key, row key）をＥ（master key, row key||$）に変更する。そうでなければ、その行をそのままとする。
（３）ｎサイズのＲＳの全ての行が（２）に従って処理されると、第２の実施の形態のＡＩＭあるいはＤＩＭを起動する。
【００６６】
最初の第２の実施の形態のＡＩＭあるいはＤＩＭの実行において、上記のステップ（１）−（３）が実行される。しかし、２回目及びそれ以降の第２の実施の形態のＡＩＭあるいはＤＩＭの実行においては、上記のステップ（１）を省略することが可能である。
【００６７】
すなわち、第２の実施の形態のＡＩＭあるいはＤＩＭにおいて、まず、ｎ行（暗号化された行）が取得される。その後、ｎ行（暗号化された）がすべて初期化された行かどうかを判定する。すべて初期化されていれば、第２の実施の形態のＡＩＭあるいはＤＩＭが開始する。
そうでなければ、初期化されていない各行に対して、少なくとも１つのダミーが行（復号された行）に追加される。また、追加されたダミーを有する行（すぐにあるいは後で）再び暗号化され）は、初期化された行としてマーク付けされる。
これにより、第２の実施の形態のＡＩＭあるいはＤＩＭが開始する時、すべての取得したｎ行はすべて初期化された行となる。
一方、取得したｎ行がすべて初期化された行でない場合、すぐに初期化処理を実行する代わりに、他のｎ行（それらは先に取得したｎ行とは部分的に異なることがある）を新たに取得してもよい。
連続的な取得が絶え間なく続くのを防ぐため、回数（例えば、３回または５回）を予め定義し、新しく取得した他のｎ行が、ｎ行全てが初期化された行であるという条件を予め定義した回数連続して満たさない場合、初期化処理を実行するようにする。
【００６８】
従って、上記初期化処理の後、各行の長さは「２」以上となり、また、取得したＲＳ（ｎ行）内の全ての行が初期化される。
初めてのＡＩＭあるいはＤＩＭの実行では、全てのｎ行（各行は少なくとも１つのデータ項目を有する）は、ダミーを全く有しない。従って、初期化処理が各行について実行され、それにより、ｎ行が初期化され、各行が最初の初期化後に２以上の長さを有するようになる。
第２の実施の形態におけるＡＩＭあるいはＤＩＭの以後の動作については、上記の条件が満たされるように、まず各未初期化行が初期化される。
【００６９】
（第３の実施の形態）
第２の実施の形態において、１つの新たな項目を追加するかあるいは１つの暗号化項目を削除するかどうかに関係なく、ダミーの数は固定的である。
一定の条件が満たせば、スペース効率をさらに向上することができる。
第３の実施の形態における主要な特徴は、以下の追加の調整工程を除き、第２の実施の形態と同じである。
【００７０】
（調整工程）
ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。
もし、s-1≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、各行からＳ−１個のダミーが削除される。
【００７１】
調整工程の後、その行が目標行であるための最大で１／ｋの確率をなお保持する。
【００７２】
図１０および図１１は、本発明の第３の実施の形態によるｋ−匿名更新方式と装置について説明する概略図である。追加する場合のブロック図を図１０に示し、削除する場合のブロック図を図１１に示す。
【００７３】
図７および８と比較して、２つのブロックだけが調整工程を実行するために図１０および１１にそれぞれ追加される。すなわち、調整ユニットと第３レベルＲＳ記憶ユニットである。
従って、これら２つのブロックについて詳細に説明する。その他のブロックについては、第２の実施の形態におけるブロックと同じであり、それらの詳細な説明は説明を分かり易くするために省略する。
（１）調整ユニットは、更新済みＲＳのプレーンテキスト形式を入力とし、以下の動作を実行する。
ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。
もし、s-11≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、調整ユニットは、各行からＳ−１個のダミーを削除する。
調整ユニットは、調整した更新済みＲＳのプレーンテキスト形式を出力する。
（２）第３レベルＲＳ記憶ユニットは、調整した更新済みのＲＳのプレーンテキスト形式を格納する。
【００７４】
（第３の実施の形態の具体例）
図１２は、本発明の第３の実施の形態に従ってｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第３の実施の形態に従って１つの新たな項目を追加する場合と１つの項目を削除する場合における調整工程を、直感的に理解できるであろう。
【００７５】
第２の実施の形態と比較して、第３の実施の形態におけるスペース効率はさらに向上する。
１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、しかも不変に保持することなく、追加ダミーの数は最大でも「０」である。
【００７６】
上述したユニットは、図面において個別のブロックとして示しているけれども、どのユニットも１つの構成要素として他のものと組み合わせることが可能あるし、さらにいくつかの構成要素に分けることも可能である。
上記説明において複数のユニットを示したが、本発明は、その機能を実行することができれば、１ユニットを幾つかのユニットに分割し、あるいは１ユニットに幾つかのユニットを組み合わせることでも実現可能である。
【００７７】
以上の説明は、本発明の好ましい実施の形態のみを提示するものであり、本発明に対していかなる限定も加えるものではない。従って、本発明の精神及び原則内においてなされた任意の変形、置き換え、改良などは本発明の範囲に含まれるものである。
【技術分野】
【０００１】
本発明は、情報アップデート技術の分野に関し、特に、暗号化転置インデックステーブルに対するｋ−匿名（k-anonymity）更新のための方法および装置に関する。ｎ行のデータがあると仮定すると、各行はそれぞれ１つ以上の暗号化された項目と共にインデックスとして暗号化されたキーワードを有する。ｎ行のうち１つが更新しようとする目標行として選択されていると仮定する。すなわち、新たな暗号化された項目を該当する行に追加し、あるいは、暗号化された項目を該当する行から削除しようとする場合である。本発明の目的は、ｋ−匿名性を実現することにある。すなわち、更新の前と後にｎ行を観察する好奇心が強いが誠実な攻撃者（curious but honest attacker：不正に情報を入手しようとする攻撃者）は、どの行が目標行かを多くても確率１／ｋで見分けることができる。ここで、ｋは予め定義されたセキュリティパラメータである。
【背景技術】
【０００２】
現在、２つの増加傾向が出現している。すなわち、個人のプライバシーの保護に対する普遍的な関心と、ストレージサーバに対して外部委託する個人データである。ストレージサーバに対して個人データを外部委託する利用において、外部委託したドキュメントとそれらについて構築された転置インデックスの両方とも、機密保持とプライバシー上の理由のために暗号化形式が採用される。暗号化転置インデックステーブル（Ｅｎｃｒｙｐｔｅｄ Ｉｎｖｅｒｔｅｄ Ｉｎｄｅｘ Ｔａｂｌｅ：以下、「ＥＩＩＴ」と称する）は、様々な長さの多くの無関係な行から構成される代表的なデータ構造を有し、完全には信頼できないストレージサーバ（semi-trusted storage server）が検索者のために指定の暗号化キーワードの整合結果を見つけ出すことを可能にする機能を提供する。専用の暗号化キーワードでマーク付けされた各暗号化行は、そのキーワードに関する全ての暗号化ファイル情報を含む。暗号化キーワードの値は「行識別子」と呼ばれ、行内の暗号化されたファイル情報は「データ項目」と呼ばれる。
【０００３】
同じ出願人による２つの特許出願、「高速検索可能な暗号化のための方法、装置及びシステム」の名称の中国特許出願２００８１００９８３５９．１（特許文献１）と中国特許出願２００８１０１４５０８３．８（特許文献２）が暗号化された転置インデックステーブル（ＥＩＩＴ）を構築する方法を開示している。ＥＩＩＴは何千もの行を有する場合がある。上述したｎ行は、ＥＩＩＴから取り出された一部あるいはＥＩＩＴの全行である。
【０００４】
ドキュメントが更新され、新たなキーワードがドキュメントに追加される場合（あるいは、キーワードがドキュメントから削除される場合）、唯一の行、すなわち、ＥＩＩＴの目標行を更新する必要がある。
【０００５】
しかしながら、単にＥＩＩＴの目標行を更新することは、信頼されていない当事者（すなわち、ＥＩＩＴを格納するストレージサーバ）に対して、キーワードとドキュメント間の関連を露呈することになる。図１は、この問題を直感的な方法で示している。
【０００６】
中国特許出願２００８１００９８３５９．１（特許文献１）と中国特許出願２００８１０１４５０８３．８（特許文献２）には、「高速検索可能な暗号化方式」（Ｆａｓｔ Ｓｅａｒｃｈａｂｌｅ Ｅｎｃｒｙｐｔｉｏｎ Ｍｅｔｈｏｄ（ＦＳＥ）と呼ばれるいくつかの技術的解決法が存在する。図２、図３を参照してその方法を概説する。図２はＦＳＥ方式および装置について説明する概略図である。また、図３は、ＦＳＥ方式および装置が暗号化された行をどのように更新するかを示す概略図である。
（１）データ所有者は、まず、暗号化されたターゲットドキュメント（ＥＴＤ）について実行される更新に従ってストレージサーバから希望の暗号化された行をすべて取得し、取得した行を出力する。
（２）暗号化された行について、データ所有者は、マスターキーを使用して、その行内のデータ所有者に知られている所定の位置に位置する特別項目Ｅ（マスターキー，行キー）の復号を実行し、行キーを取得する。その後、データ所有者は、行キーを使用して項目のプレーンテキスト形式を取得することができる。
（３）削除すべきオリジナルのプレーンテキスト項目について、データ所有者はこの行からそれを除去する。また、追加すべき新たなプレーンテキスト項目について、データ所有者はその行にそれを追加する。
（４）データ所有者は、すべての更新行のプレーンテキスト形式と暗号キーを入力とし、暗号キーで更新行のプレーンテキストを一つずつ暗号化し、特別項目を形成するために、マスターキーで暗号キーに対応する復号キー（新たな行キー）を暗号化し、それらの暗号化形式を出力し、ストレージサーバにそれらをアップロードする。
【０００７】
この更新ルーチンの明白な欠点は、それらは両方とも暗号化された形式であるけれども、ストレージサーバがＥＩＩＴとＥＴＤ内の更新行間の引用関係を知っていることである。
最も関する技術分野においては、修正済（項目が追加されまたは削除された）ドキュメントと暗号化された索引テーブルの行間の関連は、インデックステーブルが暗号化されていても、更新の前と更新の後の行の長さを比較することにより露呈することができる。それはセキュリティとプライバシーの観点からすると危険である。
【０００８】
その危険性は更新回数が増加するに従って激化するであろう。また、プライバシーはひどく危険にさらされるだろう。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】中国特許出願２００８１００９８３５９．１
【特許文献２】中国特許出願２００８１０１４５０８３．８
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したように、特許文献１及び特許文献２に記載される更新ルーチンの明白な欠点は、それらは両方とも暗号化された形式であるけれども、ストレージサーバがＥＩＩＴとＥＴＤ内の更新行間の引用関係を知っていることである。最も関する技術分野においては、修正済（項目が追加されまたは削除された）ドキュメントと暗号化された索引テーブルの行間の関連は、インデックステーブルが暗号化されていても、更新の前と更新の後の行の長さを比較することにより露呈することができる。それはセキュリティとプライバシーの観点からすると危険である。また、その危険性は更新回数が増加するに従って激化する。また、プライバシーはひどく危険にさらされることになる。
【課題を解決するための手段】
【００１１】
ｎ行（以下、ｎ行の集合を「ｎサイズ行集合」と称し、略して「ＲＳ」と称する）の一行が最初の更新のための目標行として選択されると仮定する。すなわち、１つの新たな暗号化された項目が目標行に追加され、あるいは、１つの暗号化された項目が目標行から削除される場合に、更新の前と後にｎ行を観察する好奇心が強いが誠実な攻撃者（curious but honest attacker）がどの行が目標行かを多くても確率１／ｋで見分けるという可能性を保証する。ここで、ｋは予め定義されたセキュリティパラメータである。
【００１２】
端的に言えば、更新を実行する時各行にダミーを導入することにより上記の目的を達成する。
【００１３】
本発明の第１の態様によれば、暗号化された転置インデックステーブルに対するｋ−匿名性更新方法であって、外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とする。
【００１４】
好ましい態様では、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行に１つの新たな復号したデータ項目を追加し、復号したデータ項目の残るｎ−１行の各行に１つのダミーに追加することを特徴とする。
【００１５】
好ましい態様では、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする。
【００１６】
好ましい態様では、復号ステップの前に、暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、暗号化されたデータ項目のｎ行がすべて初期化された行であれば、復号ステップを実行するステップを含み、目標行更新と疑似演算実行ステップが、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを決定し、目標行の内に少なくとも１つのダミーがあれば、更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、ｎは
【数１】
として決定されることを特徴とする。さらに、目標行の内にダミーがなければ、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持する。
【００１７】
好ましい態様では、復号ステップの前に、暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、暗号化されたデータ項目のｎ行がすべて初期化された行ならば、復号ステップを実行するステップとを含み、目標行更新と疑似演算実行ステップが、更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする。
【００１８】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、復号ステップを実行し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００１９】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする。
【００２０】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする。
【００２１】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさない場合、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００２２】
好ましい態様では、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする。
【００２３】
好ましい態様では、初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする。
【００２４】
好ましい態様では、暗号化ステップの前に、更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除することを特徴とする。
【００２５】
本発明の第１の態様によれば、暗号化された転置インデックステーブルに対するｋ−匿名更新のための装置であって、外部記憶装置から暗号化されたデータ項目のｎ行を取得する取得ユニットと、前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号する復号ユニットと、復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成する更新ユニットと、更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化する暗号化ユニットと、前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするアップロードユニットとを備え、ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とする。
【００２６】
好ましい態様では、更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行に１つの新たな復号データ項目を追加し、復号されたデータ項目の残るｎ−１行の各行に１つのダミーを追加することを特徴とする。
【００２７】
好ましい態様では、更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする。
【００２８】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、前記更新ユニットは、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを判定し、目標行の内に少なくとも１つのダミーがあれば、更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、ｎは
【数２】
として決定されることを特徴とする。また、目標行の内にダミーがなければ、前記更新ユニットは、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持する。
【００２９】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする。
【００３０】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記初期化ユニットは、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００３１】
好ましい態様では、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記取得ユニットは、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする。
【００３２】
好ましい態様では、新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする。
【００３３】
好ましい態様では、初期化ユニットが、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさないと判定すると、前記初期化ユニットは、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする。
【００３４】
好ましい態様では、初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする。
【００３５】
好ましい態様では、初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする。
【００３６】
好ましい態様では、更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除する調整ユニットをさらに備えることを特徴とする。
【００３７】
本発明の方法では、目標行に１つの新たな項目を追加する場合、同時に他のｎ−１のダミー行のそれぞれに対してダミー項目を追加する。これにより、全てのｎ行の暗号化データが変更されるが、全てのｎ行の長さが「１」だけ増加する。目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。他のｎ−１のダミー行の長さは、そのままである。このように、暗号化されたデータはすべてのｎ行において変更されるが、全てのｎ行の長さは不変である。これにより、ｎがｎ≧ｋとしてセットされる場合、ＲＳのｎ行のうちの目標行は、好奇心が強いが誠実な攻撃者によって最大限でも確率１／ｋで識別されることになる。
【００３８】
本発明の他の方法では、目標行に１つの新たな項目を追加する場合、目標行内に少なくとも１つのダミーが存在する場合、このダミーを新たな項目に置き換え、ＲＳ内の任意の行に他のダミーを追加する。他方、目標行がダミーを有しない場合は、単に目標行に新たな項目を追加し、付加的なダミーを他のｎ−１行に追加しない。このように、更新済みＲＳの内では、暗号化データはすべてのｎ行において変更されるが、目標行は、１項目だけ増加し（目標行内にダミーが無い場合）、あるいはｎ−１個の他の行の１行が１項目だけ増加する（目標行内に少なくとも１つのダミーがある場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、次に、選択した行から１つのダミーを削除する。取得したｎ行内にダミーが全く存在しない最悪の削除状況では、置き換えステップで目標行に１つの新たなダミーを導入する。すなわち、この処理中、少なくとも１つのダミーを有する行を必ず見つけ出すことができる。このように、暗号化データはすべてのｎ行において変更されるが、更新済みＲＳの内では、目標行が、１項目だけ減少し（選択した行が目標行である場合）、あるいは他のｎ−１行の１行が１項目だけ減少する（選択した行が目標行でない場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００３９】
これにより、追加の場合、ｎが
【数３】
としてセットされ、削除の場合、ｎがn ≧kとしてセットされると、ＲＳのｎ行のうちの目標行は、好奇心が強いが誠実な攻撃者によって最大限でも確率１／ｋで識別されることになる。更に、より少ないダミーが、同じセキュリティの強度の維持しつつスペース効率を向上させるために導入されるだろう。すなわち、本発明の他の方法によれば、１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、ダミーの数は固定的で変わらない。
【００４０】
本発明のさらに他の方法では、一定の条件が満たせば、スペース効率をさらに向上することができる。具体的には、ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。もし、s-1≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、各行からＳ−１個のダミーが削除される。これにより、より少ないダミーが同じセキュリティの強度の維持しつつ導入される。
【発明の効果】
【００４１】
本発明は、所定のセキュリティパラメータｋに対して、好奇心が強いが誠実な攻撃者が更新された行集合から目標行を識別する確率を多くても１／ｋとすることを可能にする。
【図面の簡単な説明】
【００４２】
本発明の前述した目的、特徴及び効果と他の目的、特徴及び効果は、添附の図面を参照した本発明の限定されない実施の形態に関する以下の説明からより明らかになるであろう。
【図１】好奇心が強いが誠実な攻撃者が修正済の行をどのように見つけ出すかを示す概略図である。
【図２】ＦＳＥ方式および装置について説明する概略図である。
【図３】ＦＳＥ方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図４】本発明の第１の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図５】本発明の第１の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図６】本発明の第１の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図７】本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図８】本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図９】本発明の第２の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【図１０】本発明の第３の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図１１】本発明の第３の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。
【図１２】本発明の第３の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。
【発明を実施するための形態】
【００４３】
以下、図面を参照して本発明について説明する。以下の説明において、幾つかの特定の実施の形態は説明のみの目的で使用される。これらの実施の形態はあくまで例示であり、本発明を限定するものとして理解してはならない。また、本発明の理解が多少曖昧になる可能性はあるが、従来技術の構成・構造の説明は省略する。
【００４４】
ｋ−匿名性更新の場合、二人の当事者（すなわちデータ所有者と好奇心が強いが誠実な観察者）が関与する。ストレージサーバは明らかに好奇心が強いが誠実な観察者（curious
but honest observer）である。具体的な工程を説明する前に、いくつかの特殊記号および略語を以下に定義する。
ｋ：予め定義されたセキュリティパラメータ、定数
ｎ：パラメータｎは、ｋ−匿名性更新を満たす毎に取得された行の合計数である。また、ｎは行集合ＲＳの大きさである。
好奇心が強いが誠実な攻撃者：攻撃者は予め定められた工程を遵守するが、保護された情報を探りたい。
ＡＩＭ：ｋ−匿名方式に基づいてデータ項目を追加する方法。
ＤＩＭ：ｋ−匿名方式に基づいてデータ項目を削除する方法。
ＥＩＩＴ：暗号化転置インデックステーブル（Ｉｎｖｅｒｔｅｄ Ｉｎｄｅｘ Ｔａｂｌｅ）。より具体的には、ＥＩＩＴはｍ行から成る。各行は、指定されたキーワードに関する暗号化ファイル情報とおよび（または）１つ以上の乱数（ダミー）を含んでおり、キーワードとマスターキーから導き出した任意の値でマーク付けされる。
ＲＳ：ｎサイズの行集合、１つの目標行とｎ−１個のダミー行を含んでいる。
【００４５】
本発明は３つの実施の形態を含んでいる。以下に、本発明の詳細な説明を記載する。
【００４６】
（第１の実施の形態）
第１の実施の形態に関して、行集合（＝ｎ）のサイズが所定のセキュリティパラメータｋに対してｎ≧ｋとしてセットされる場合（ｎとｋは正の整数）、好奇心が強いが誠実な攻撃者が更新された行集合から目標行を識別する確率は最大で１／ｋである。
【００４７】
図４および図５は、本発明の第１の実施の形態によるｋ−匿名更新方法および装置を説明する概略図である。追加する場合のブロック図を図４に示し、削除する場合のブロック図を図５に示す。
【００４８】
（第１の実施の形態におけるＡＩＭ）
目標行に１つの新たな項目を追加する場合、同時に他のｎ−１のダミー行のそれぞれに対してダミー項目を追加する。これにより、全てのｎ行の暗号化データが変更されるが、全てのｎ行の長さが「１」だけ増加する。
【００４９】
第１の実施の形態における１つの新たな項目の追加に関する構成要素を図４を参照して以下に説明する。
（１）ＲＳ取得ユニットは、外部記憶装置（信頼できない記憶装置−外部ＥＩＩＴユニット）から、暗号化された形式でｎサイズのＲＳを取得する。
ｎは所定の値ｋから計算される。
ここで、所定の値ｋは、ＲＳ取得ユニットに予め設定されるか、あるいは利用者によって入力される。
（２）キー記憶ユニットは、ＲＳ内のデータ項目を暗号化し、復号するために使用するマスターキーを格納する。
（３）前処理ユニットは、取得した暗号化ＲＳおよびマスターキーを入力として、ＲＳ内の暗号化された項目をすべて復号し、もとのＲＳのプレーンテキスト形式を出力する。
この復号において、まず、マスターキー（master key）が行キーを得るための復号を実行するのに使用される。次に、行鍵キーがもとのＲＳのプレーンテキスト形式を得るための復号を実行するのに使用される。
（４）入力項目記憶ユニットは、追加する新たな項目を格納する。
（５）入力ＲＳ記憶ユニットは、前処理ユニットの出力を格納する。
（６）項目挿入ユニットは、追加する項目およびＲＳのプレーンテキスト形式を入力とし、目標行に項目を追加し、目標行に追加された入力項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（７）第１レベルＲＳ記憶ユニットは、項目挿入ユニットの出力を格納する。
（８）ダミー挿入ユニットは、更新済みＲＳを入力とし、他のｎ−１のダミー行のそれぞれに対してダミー項目を追加し、また目標行に追加された入力項目と、他のｎ−１のダミー行のそれぞれに追加されたダミー項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（９）第２レベルＲＳ記憶ユニットは、ダミー挿入ユニットの出力を格納する。
（１０）後処理ユニットは、更新済みＲＳのプレーンテキスト形式およびマスターキーを入力とし、更新済みＲＳ内の項目を一行づつすべて再暗号化し、更新済みＲＳの暗号化形式を出力する。
この暗号化において、１つの暗号キーあるいは複数の暗号キーが更新済みＲＳ内のそれぞれの行における項目を再暗号化するために使用される。また、マスターキーは、特別項目を形成するためにそれぞれの行について使用された暗号キーに対応する解読キーあるいは暗号キー（新たな行キー（row key））を暗号化するために使用される。それにより、更新済みＲＳの暗号化形式が生成される。
（１１）更新ＲＳ記憶ユニットは、後処理ユニットの出力を格納する。
（１２）ＲＳアップロードユニットは、暗号化形式のｎサイズの更新済みＲＳを入力とし、外部記憶装置にｎサイズの更新済みＲＳをアップロードし、アップロード状態によって「真」か「偽」の何れかを出力する（すなわち、アップロードが成功すれば、「真」を返却し、そうでなければ、「偽」を返却する）。
【００５０】
ここで、マスターキーおよび／または行キーとしては、対称暗号化スキーム（symmetric cryptography scheme）において使用される対称キー、ペアワイズ暗号化スキームにおいて使用されるペアの公開キーと秘密キー、あるいは周知の暗号化スキームにおいて使用される他のキーを利用することが可能である。本発明において、暗号化／復号スキームは特に限定されない。
【００５１】
（第１の実施の形態におけるＤＩＭ）
目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。他のｎ−１のダミー行の長さは、そのままである。このように、暗号化されたデータはすべてのｎ行において変更されるが、全てのｎ行の長さは不変である。
【００５２】
第１の実施の形態における１つの無用な項目の削除に関する構成要素を図５を参照して以下に説明する。
（１）ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力ＲＳ記憶ユニット、第１レベルＲＳ記憶ユニット、後処理ユニット、更新ＲＳ記憶ユニットとＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＡＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）入力項目記憶ユニットは、削除項目を格納する。
（３）項目置換ユニットは、削除項目およびＲＳのプレーンテキスト形式を入力とし、削除する項目の位置を特定し、目標行内のその項目をダミーで置き換え、ダミーと置き換えられた削除項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
【００５３】
（第１の実施の形態の具体例）
図６は、本発明の第１の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第１の実施の形態による新たな１項目を追加する場合と１項目を削除する場合を、直感的に理解できるであろう。
【００５４】
最も関連する技術と比較して、行集合（＝ｎ）のサイズが所定のセキュリティパラメータｋに対してｎ≧ｋとしてセットされる場合（ｎとｋは正の整数）、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率は最大で１／ｋである。
【００５５】
（第２の実施の形態）
１つの新たな項目を追加する場合、第１の実施の形態においては、ｎ−１個のダミーが追加される。また、１つの暗号化項目を削除する場合、第１の実施の形態においては、１個のダミーが追加される。空間効率を向上させるためには、同じセキュリティの強度を保持しながら、より少数のダミーを導入すべきである。
【００５６】
第２の実施の形態においては、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率が最大で１／ｋであるという要求を満たすために、ＲＳ（＝ｎ）のサイズが、所定のセキュリティパラメータｋに対して、追加の場合、
【数４】
としてセットされ、削除の場合、n ≧kとしてセットされる。ここで、ｎとｋは正の整数である、ｅは、数学的な定数（「オイラーの数」、ｅ≒２．７１８２８として知られている）である。また、
【数５】
は上位の整関数であり、
【数６】
は、Ｘより大きいか或いは等しい最も小さな整数を示している。
【００５７】
図７および図８は、本発明の第２の実施の形態によるｋ−匿名更新方式および装置について説明する概略図である。追加する場合のブロック図を図７に示し、削除する場合のブロック図を図８に示す。
【００５８】
（第２の実施の形態におけるＡＭＩ）
目標行に１つの新たな項目を追加する場合、目標行内に少なくとも１つのダミーが存在する場合、このダミーを新たな項目に置き換え、ＲＳ内の任意の行に他のダミーを追加する。他方、目標行がダミーを有しない場合は、単に目標行に新たな項目を追加し、付加的なダミーを他のｎ−１行に追加しない。このように、更新済みＲＳの内では、暗号化データはすべてのｎ行において変更されるが、目標行は、１項目だけ増加し（目標行内にダミーが無い場合）、あるいはｎ−１個の他の行の１行が１項目だけ増加する（目標行内に少なくとも１つのダミーがある場合）。すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００５９】
第２の実施の形態における１つの新たな項目の追加に関する構成要素を図７を参照して以下に説明する。
（１）ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力項目記憶ユニット、入力ＲＳ記憶ユニット、第１レベルＲＳ記憶ユニット、更新ＲＳ記憶ユニット、後処理ユニット、ＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＡＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）項目挿入ユニットは、追加する項目およびＲＳのプレーンテキスト形式を入力とし、目標行内に少なくとも１つのダミーがあれば、目標行内のダミーを入力項目と置き換え、そうでなければ目標行に直接入力項目を追加する。
項目挿入ユニットは、置き換えによって目標行に追加した新たな項目あるいは目標行に直接追加した新たな項目を有する更新済みＲＳのプレーンテキスト形式を出力する。
（３）ダミー挿入制御ユニットは、項目挿入ユニットにおいて置き換えが生じるかどうかを記録し、その状態によって「真」か「偽」の何れかを出力する（すなわち、置き換えが生じれば、「真」を返却し、そうでなければ、「偽」を出力する）。
（４）ダミー挿入ユニットは、更新済ＲＳのプレーンテキスト形式を入力とし、ＲＳから１行を任意に選択し、置き換えが生じると（すなわち、ダミー挿入制御ユニットが「真」を出力すると）、選択した行に１つのダミーを追加する。そうでなければ（すなわち、ダミー挿入制御ユニットが「偽」を出力すると）、ダミー挿入ユニットは、項目挿入ユニットから出力される更新済みＲＳのプレーンテキスト形式に対して何も行わない。ダミー挿入ユニットは、追加した別のダミーを有する更新済みＲＳのプレーンテキスト形式を出力する。
（５）第２レベルＲＳ記憶ユニットは、ダミー挿入ユニットの出力を格納する。
【００６０】
（第２の実施の形態におけるＤＩＭ）
目標行から１つの暗号化された項目を削除する場合、目標行内の暗号化された項目をダミーで置き換える。ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、次に、選択した行から１つのダミーを削除する。
取得したｎ行内にダミーが全く存在しない最悪の削除状況では、最初のステップで取得したオリジナルのｎ行の１つに１つの新たなダミーを導入する。
すなわち、この処理中、少なくとも１つのダミーを有する行を必ず見つけ出すことができる。
このように、暗号化データはすべてのｎ行において変更されるが、更新済みＲＳの内では、目標行は、１項目だけ減少し（選択した行が目標行である場合）、あるいはｎ−１個の他の行の１行が１項目だけ減少する（選択した行が目標行でない場合）。
すなわち、目標行は、更新済みＲＳ内の行長さの変動と何ら関係を有しない。
【００６１】
第２の実施の形態における１つの無用な項目の削除に関する構成要素を図８を参照して以下に説明する。
（１） ＲＳ取得ユニット、キー記憶ユニット、前処理ユニット、入力項目記憶ユニット、入力ＲＳ記憶ユニット、項目置換ユニット、第１レベルＲＳ記憶ユニット、更新ＲＳ記憶ユニット、後処理ユニットとＲＳアップロードユニットは、第１の実施の形態における１つの新たな項目を追加する場合と同じように動作する。これらについては、既に第１の実施の形態におけるＤＩＭで説明した通りであり、それらの詳細な説明は説明を分かり易くするために省略する。
（２）ダミー削除ユニットは、更新済ＲＳのプレーンテキスト形式を入力とし、ＲＳから少なくとも１つのダミーを有する１つの行を任意に選択し、選択した行から１つのダミーを削除する。
ダミー削除ユニットは、１つのダミーと置き換えられて削除される項目及び任意に選択したＲＳの行から削除された別のダミー（ただ１つのダミー）を有する更新済ＲＳのプレーンテキスト形式を出力する。
（３）第２レベルＲＳ記憶ユニットは、ダミー削除ユニットの出力を格納する。
【００６２】
（第２の実施の形態の具体例）
図９は、本発明の第２の実施の形態によるｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第２の実施の形態による新たな１項目を追加する場合と１項目を削除する場合を、直感的に理解できるであろう。
【００６３】
第１の実施の形態と比較して、第２の実施の形態においてはスペース効率が向上する。
１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、追加ダミーの数は「０」である。すなわち、固定的で変わらない。
さらに、ＲＳ（＝ｎ）のサイズが、所定のセキュリティパラメータｋに対して、追加の場合、
【数７】
としてセットされ、削除の場合、n ≧kとしてセットされる場合、好奇心が強いが誠実な攻撃者が更新済みＲＳから目標行を識別する確率が最大で１／ｋである。
【数８】
は、Ｘより大きいか或いは等しい最も小さな整数を示している。
【００６４】
更に、第２の実施の形態のＡＩＭあるいはＤＩＭにおいては、各行の長さが最初の初期化の後に２以上であること、また、取得したＲＳ（ｎ行）内の全ての行が初期化されることを保証するために初期化処理が導入される、
【００６５】
（初期化処理）
各行において、特別項目Ｅ（master
key、row key）が、初期化処理がその行に対して実行されているかどうかを識別するために使用される。
例えば、Ｅ（master key、row
key）は、専用のシンボル「＄」を導入することによってＥ（master key、row key｜｜＄）へ拡張される。
項目Ｅ（master key、row
key）は、その行が初期化されていない行であることを示し、一方、項目Ｅ（master key、row key｜｜＄）は、その行が初期化された行であることを示している。
ＥＩＩＴ中に合計でｍ行存在すると仮定した場合、初期化処理は以下の説明のように実行される。
（１）所定のセキュリティパラメータｋについて、
【数９】
を計算する。
ｍ≧ｎであれば、（２）に進み、そうでなければ初期化処理を中止する。
（２）取得したｎ行について、初期化された行であるかどうかを一行ずつ全ての行をチェックする。
初期化されていない行である場合は、少なくとも１つのダミーを追加し、Ｅ（master key, row key）をＥ（master key, row key||$）に変更する。そうでなければ、その行をそのままとする。
（３）ｎサイズのＲＳの全ての行が（２）に従って処理されると、第２の実施の形態のＡＩＭあるいはＤＩＭを起動する。
【００６６】
最初の第２の実施の形態のＡＩＭあるいはＤＩＭの実行において、上記のステップ（１）−（３）が実行される。しかし、２回目及びそれ以降の第２の実施の形態のＡＩＭあるいはＤＩＭの実行においては、上記のステップ（１）を省略することが可能である。
【００６７】
すなわち、第２の実施の形態のＡＩＭあるいはＤＩＭにおいて、まず、ｎ行（暗号化された行）が取得される。その後、ｎ行（暗号化された）がすべて初期化された行かどうかを判定する。すべて初期化されていれば、第２の実施の形態のＡＩＭあるいはＤＩＭが開始する。
そうでなければ、初期化されていない各行に対して、少なくとも１つのダミーが行（復号された行）に追加される。また、追加されたダミーを有する行（すぐにあるいは後で）再び暗号化され）は、初期化された行としてマーク付けされる。
これにより、第２の実施の形態のＡＩＭあるいはＤＩＭが開始する時、すべての取得したｎ行はすべて初期化された行となる。
一方、取得したｎ行がすべて初期化された行でない場合、すぐに初期化処理を実行する代わりに、他のｎ行（それらは先に取得したｎ行とは部分的に異なることがある）を新たに取得してもよい。
連続的な取得が絶え間なく続くのを防ぐため、回数（例えば、３回または５回）を予め定義し、新しく取得した他のｎ行が、ｎ行全てが初期化された行であるという条件を予め定義した回数連続して満たさない場合、初期化処理を実行するようにする。
【００６８】
従って、上記初期化処理の後、各行の長さは「２」以上となり、また、取得したＲＳ（ｎ行）内の全ての行が初期化される。
初めてのＡＩＭあるいはＤＩＭの実行では、全てのｎ行（各行は少なくとも１つのデータ項目を有する）は、ダミーを全く有しない。従って、初期化処理が各行について実行され、それにより、ｎ行が初期化され、各行が最初の初期化後に２以上の長さを有するようになる。
第２の実施の形態におけるＡＩＭあるいはＤＩＭの以後の動作については、上記の条件が満たされるように、まず各未初期化行が初期化される。
【００６９】
（第３の実施の形態）
第２の実施の形態において、１つの新たな項目を追加するかあるいは１つの暗号化項目を削除するかどうかに関係なく、ダミーの数は固定的である。
一定の条件が満たせば、スペース効率をさらに向上することができる。
第３の実施の形態における主要な特徴は、以下の追加の調整工程を除き、第２の実施の形態と同じである。
【００７０】
（調整工程）
ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。
もし、s-1≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、各行からＳ−１個のダミーが削除される。
【００７１】
調整工程の後、その行が目標行であるための最大で１／ｋの確率をなお保持する。
【００７２】
図１０および図１１は、本発明の第３の実施の形態によるｋ−匿名更新方式と装置について説明する概略図である。追加する場合のブロック図を図１０に示し、削除する場合のブロック図を図１１に示す。
【００７３】
図７および８と比較して、２つのブロックだけが調整工程を実行するために図１０および１１にそれぞれ追加される。すなわち、調整ユニットと第３レベルＲＳ記憶ユニットである。
従って、これら２つのブロックについて詳細に説明する。その他のブロックについては、第２の実施の形態におけるブロックと同じであり、それらの詳細な説明は説明を分かり易くするために省略する。
（１）調整ユニットは、更新済みＲＳのプレーンテキスト形式を入力とし、以下の動作を実行する。
ｓを現在の全てのｎ行におけるダミーの共有数（common number）であると仮定する。すなわち、全ての行は、少なくともｓ個のダミーを含んでいる。
もし、s-11≧1でかつ各行の現在の長さが少なくともｓ＋１ならば、調整ユニットは、各行からＳ−１個のダミーを削除する。
調整ユニットは、調整した更新済みＲＳのプレーンテキスト形式を出力する。
（２）第３レベルＲＳ記憶ユニットは、調整した更新済みのＲＳのプレーンテキスト形式を格納する。
【００７４】
（第３の実施の形態の具体例）
図１２は、本発明の第３の実施の形態に従ってｋ−匿名更新方式および装置が暗号化された行をどのように更新するかを示す概略図である。これにより、第３の実施の形態に従って１つの新たな項目を追加する場合と１つの項目を削除する場合における調整工程を、直感的に理解できるであろう。
【００７５】
第２の実施の形態と比較して、第３の実施の形態におけるスペース効率はさらに向上する。
１つの新たな項目を追加するか、暗号化された項目を削除するかに関係なく、しかも不変に保持することなく、追加ダミーの数は最大でも「０」である。
【００７６】
上述したユニットは、図面において個別のブロックとして示しているけれども、どのユニットも１つの構成要素として他のものと組み合わせることが可能あるし、さらにいくつかの構成要素に分けることも可能である。
上記説明において複数のユニットを示したが、本発明は、その機能を実行することができれば、１ユニットを幾つかのユニットに分割し、あるいは１ユニットに幾つかのユニットを組み合わせることでも実現可能である。
【００７７】
以上の説明は、本発明の好ましい実施の形態のみを提示するものであり、本発明に対していかなる限定も加えるものではない。従って、本発明の精神及び原則内においてなされた任意の変形、置き換え、改良などは本発明の範囲に含まれるものである。
【特許請求の範囲】
【請求項１】
暗号化された転置インデックステーブルに対するｋ−匿名性更新方法であって、
外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、
前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、
復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、
更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、
前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、
ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とするｋ−匿名性更新方法。
【請求項２】
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行に１つの新たな復号したデータ項目を追加し、復号したデータ項目の残るｎ−１行の各行に１つのダミーに追加することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項３】
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項４】
前記復号ステップの前に、
暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、
暗号化されたデータ項目のｎ行がすべて初期化された行であれば、復号ステップを実行するステップを含み、
前記目標行更新と疑似演算実行ステップが、
少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを決定し、
目標行の内に少なくとも１つのダミーがあれば、
更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、
ｎは
【数１０】
として決定されることを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項５】
目標行の内にダミーがなければ、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項４に記載のｋ−匿名性更新方法。
【請求項６】
前記復号ステップの前に、
暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、
暗号化されたデータ項目のｎ行がすべて初期化された行ならば、復号ステップを実行するステップとを含み、
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、
復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項７】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、
復号ステップを実行し、各初期化されていない行について、
初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項４から請求項６の何れかに記載のｋ−匿名性更新方法。
【請求項８】
暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項７に記載のｋ−匿名性更新方法。
【請求項９】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項８に記載のｋ−匿名性更新方法。
【請求項１０】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする請求項４から請求項６の何れかに記載のｋ−匿名性更新方法。
【請求項１１】
新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする請求項１０に記載のｋ−匿名性更新方法。
【請求項１２】
新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさない場合、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項１０又は請求項１１に記載のｋ−匿名性更新方法。
【請求項１３】
暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項１２に記載のｋ−匿名性更新方法。
【請求項１４】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項１３に記載のｋ−匿名性更新方法。
【請求項１５】
前記暗号化ステップの前に、
更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除することを特徴とする請求項４から請求項１４の何れかに記載のｋ−匿名性更新方法。
【請求項１６】
暗号化された転置インデックステーブルに対するｋ−匿名更新のための装置であって、
外部記憶装置から暗号化されたデータ項目のｎ行を取得する取得ユニットと、
前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号する復号ユニットと、
復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成する更新ユニットと、
更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化する暗号化ユニットと、
前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするアップロードユニットとを備え、
ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とするｋ−匿名更新のための装置。
【請求項１７】
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行に１つの新たな復号データ項目を追加し、復号されたデータ項目の残るｎ−１行の各行に１つのダミーを追加することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項１８】
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項１９】
暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、
前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、
前記更新ユニットは、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを判定し、目標行の内に少なくとも１つのダミーがあれば、
更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、
ｎは
【数１１】
として決定される
ことを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項２０】
目標行の内にダミーがなければ、前記更新ユニットは、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１９に記載のｋ−匿名更新のための装置。
【請求項２１】
暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、
前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項２２】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記初期化ユニットは、
各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項１９から請求項２１の何れかに記載のｋ−匿名更新のための装置。
【請求項２３】
前記初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項２１に記載のｋ−匿名更新のための装置。
【請求項２４】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項２３に記載のｋ−匿名更新のための装置。
【請求項２５】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記取得ユニットは、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする請求項１９から請求項２１の何れかに記載のｋ−匿名更新のための装置。
【請求項２６】
新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする請求項２５に記載のｋ−匿名更新のための装置。
【請求項２７】
前記初期化ユニットが、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさないと判定すると、
前記初期化ユニットは、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項２５又は請求項２６に記載のｋ−匿名更新のための装置。
【請求項２８】
前記初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項２７に記載のｋ−匿名更新のための装置。
【請求項２９】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項２８に記載のｋ−匿名更新のための装置。
【請求項３０】
更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除する調整ユニットをさらに備えることを特徴とする請求項１９から請求項２９の何れかに記載のｋ−匿名更新のための装置。
【請求項１】
暗号化された転置インデックステーブルに対するｋ−匿名性更新方法であって、
外部記憶装置から暗号化されたデータ項目のｎ行を取得するステップと、
前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号するステップと、
復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成するステップと、
更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化するステップと、
前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするステップとを含み、
ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とするｋ−匿名性更新方法。
【請求項２】
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行に１つの新たな復号したデータ項目を追加し、復号したデータ項目の残るｎ−１行の各行に１つのダミーに追加することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項３】
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項４】
前記復号ステップの前に、
暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、
暗号化されたデータ項目のｎ行がすべて初期化された行であれば、復号ステップを実行するステップを含み、
前記目標行更新と疑似演算実行ステップが、
少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを決定し、
目標行の内に少なくとも１つのダミーがあれば、
更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、
ｎは
【数１０】
として決定されることを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項５】
目標行の内にダミーがなければ、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項４に記載のｋ−匿名性更新方法。
【請求項６】
前記復号ステップの前に、
暗号化されたデータ項目のｎ行がすべて初期化された行かどうかを決定するステップと、
暗号化されたデータ項目のｎ行がすべて初期化された行ならば、復号ステップを実行するステップとを含み、
前記目標行更新と疑似演算実行ステップが、
更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、
復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする請求項１に記載のｋ−匿名性更新方法。
【請求項７】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、
復号ステップを実行し、各初期化されていない行について、
初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項４から請求項６の何れかに記載のｋ−匿名性更新方法。
【請求項８】
暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項７に記載のｋ−匿名性更新方法。
【請求項９】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項８に記載のｋ−匿名性更新方法。
【請求項１０】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする請求項４から請求項６の何れかに記載のｋ−匿名性更新方法。
【請求項１１】
新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする請求項１０に記載のｋ−匿名性更新方法。
【請求項１２】
新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさない場合、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項１０又は請求項１１に記載のｋ−匿名性更新方法。
【請求項１３】
暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項１２に記載のｋ−匿名性更新方法。
【請求項１４】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項１３に記載のｋ−匿名性更新方法。
【請求項１５】
前記暗号化ステップの前に、
更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除することを特徴とする請求項４から請求項１４の何れかに記載のｋ−匿名性更新方法。
【請求項１６】
暗号化された転置インデックステーブルに対するｋ−匿名更新のための装置であって、
外部記憶装置から暗号化されたデータ項目のｎ行を取得する取得ユニットと、
前記暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号する復号ユニットと、
復号されたデータ項目のｎ行の中の１つの目標行を更新し、復号されたデータ項目の残るｎ−１行の各行に疑似演算を実行して、更新済みデータ項目のｎ行を形成する更新ユニットと、
更新済みデータ項目のｎ行を更新済み暗号化データ項目のｎ行として暗号化する暗号化ユニットと、
前記外部記憶装置に更新済み暗号化データ項目のｎ行をアップロードするアップロードユニットとを備え、
ｎは所定のセキュリティパラメータｋによってｎ≧ｋとして決定される（ｎとｋは正の整数）ことを特徴とするｋ−匿名更新のための装置。
【請求項１７】
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行に１つの新たな復号データ項目を追加し、復号されたデータ項目の残るｎ−１行の各行に１つのダミーを追加することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項１８】
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号したデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号したデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項１９】
暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、
前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、
前記更新ユニットは、少なくとも１つのダミーが復号されたデータ項目のｎ行の中の目標行の内にあるかどうかを判定し、目標行の内に少なくとも１つのダミーがあれば、
更新済みのデータ項目のｎ行を形成するために、目標行内の１つのダミーを、１つの新たな復号されたデータ項目で置き換え、復号されたデータ項目のｎ行から任意に選択された１つの行に１つのダミーに追加し、
ｎは
【数１１】
として決定される
ことを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項２０】
目標行の内にダミーがなければ、前記更新ユニットは、更新済みのデータ項目のｎ行を形成するために、目標行に１つの新たな復号されたデータ項目を追加し、復号されたデータ項目の残るｎ−１行を不変に保持することを特徴とする請求項１９に記載のｋ−匿名更新のための装置。
【請求項２１】
暗号化されたデータ項目のｎ行がすべて初期化された行かどうか決定するのための初期化ユニットを備え、
前記初期化ユニットは、暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、初期化処理を実行し、そうでなければ、初期化処理を実行せず、
前記更新ユニットは、目標行更新および疑似演算を完了して更新済みのデータ項目のｎ行を形成するために、復号されたデータ項目のｎ行の中の目標行内の１つの復号されたデータ項目を１つのダミーで置き換え、復号されたデータ項目のｎ行から任意に選択された少なくとも１つのダミーを有する１つの行から１つのダミーを削除することを特徴とする請求項１６に記載のｋ−匿名更新のための装置。
【請求項２２】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記初期化ユニットは、
各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項１９から請求項２１の何れかに記載のｋ−匿名更新のための装置。
【請求項２３】
前記初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項２１に記載のｋ−匿名更新のための装置。
【請求項２４】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項２３に記載のｋ−匿名更新のための装置。
【請求項２５】
暗号化されたデータ項目のｎ行がすべて初期化された行でなければ、前記取得ユニットは、暗号化されたデータ項目の他のｎ行を、外部記憶装置から新たに取得することを特徴とする請求項１９から請求項２１の何れかに記載のｋ−匿名更新のための装置。
【請求項２６】
新たに取得した暗号化されたデータ項目の他のｎ行と先に取得した暗号化されたデータ項目のｎ行は、部分的に異なることを特徴とする請求項２５に記載のｋ−匿名更新のための装置。
【請求項２７】
前記初期化ユニットが、新たに取得した暗号化されたデータ項目の他のｎ行が、暗号化されたデータ項目のｎ行が全てが初期化された行であるという条件を所定回数連続して満たさないと判定すると、
前記初期化ユニットは、暗号化されたデータ項目のｎ行を復号されたデータ項目のｎ行として復号し、各初期化されていない行について、初期化されていない行から復号された、復号されたデータ項目の１つの行に少なくとも１つのダミーを追加し、初期化された行の中に初期化されていない行をマーク付けする初期化処理を実行することを特徴とする請求項２５又は請求項２６に記載のｋ−匿名更新のための装置。
【請求項２８】
前記初期化ユニットは、暗号化されたデータ項目の１つの行が初期化された行かどうかを、暗号化されたデータ項目の１つの行の所定の位置にある専用項目を識別することにより決定することを特徴とする請求項２７に記載のｋ−匿名更新のための装置。
【請求項２９】
初期化されていない行を識別する専用項目が、Ｅ（master key, row key）であり、初期化された行を識別する専用項目が、E(master key, row key||$)であり、シンボル”＄”が初期化されていない行と初期化された行を区別するための専用のシンボルであることを特徴とする請求項２８に記載のｋ−匿名更新のための装置。
【請求項３０】
更新済みのデータ項目のｎ行の各行が少なくともｓ個のダミーを有する場合の最大の整数ｓを決定し、
以下の２つの条件１）および２）を満たすかどうか決定し、
１） ｓ−１≧１
２）更新済みのデータ項目のｎ行の各行における更新済みのデータ項目の数≧ｓ＋１
２つの条件１）と２）を満たせば、更新済みのデータ項目のｎ行の各行からｓ−１個のダミーを削除する調整ユニットをさらに備えることを特徴とする請求項１９から請求項２９の何れかに記載のｋ−匿名更新のための装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１８６１６３（Ｐ２０１０−１８６１６３Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−２７８１８５（Ｐ２００９−２７８１８５）
【出願日】平成２１年１２月８日（２００９．１２．８）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２００９−２７８１８５（Ｐ２００９−２７８１８５）
【出願日】平成２１年１２月８日（２００９．１２．８）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]