(57)【特許請求の範囲】
【請求項１】
ｐｉが第ｉデータ要素の識別部分を構成し、ｓｉが前記第ｉデータ要素の関連の機密情報部分を構成する、複数の前記データ要素（ｐｉ，ｓｉ）を含むデータストリームのデータ要素（ｐｉ，ｓｉ）を、少なくとも１つの処理デバイスによって受信するステップと、
ｔ個の領域Ｓ１、Ｓ２、．．．、Ｓｔを含む、分割された空間Ｓを、少なくとも１つの処理デバイスによって得るステップと、
前記識別部分ｐｉを、前記領域のうちの選択された１つに、少なくとも１つの処理デバイスによって割り当てるステップと、
前記関連の機密情報部分ｓｉを、ｅ（ｓｉ）として、少なくとも１つの処理デバイスによって暗号化するステップと、
メモリデバイス内の前記暗号化された関連の機密情報部分ｅ（ｓｉ）を、前記選択された領域に関連するリストに、少なくとも１つの処理デバイスによって格納するが、前記関連の識別部分ｐｉを使用して、前記関連の識別部分ｐｉを前記選択された領域に割り当てた後には、前記関連の識別部分ｐｉを、前記リストに格納しないステップと
を含む、方法。
【請求項２】
パーミュテーション関数およびハッシュ表のうちの１つまたは複数を使用して、前記選択された領域に関連する前記リストを、前記メモリデバイスの記憶位置に、少なくとも１つの処理デバイスによってマッピングするステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記分割された空間Ｓ内の領域Ｓ１、Ｓ２、．．．、Ｓｔに対応する、いくつかの中心点Ｃ１、Ｃ２、．．．、Ｃｔを、少なくとも１つの処理デバイスによって得るステップと、
ｐｉに最も近い中心を、少なくとも１つの処理デバイスによって計算するステップと
をさらに含み、
前記リストが、前記計算された最も近い中心に関連する、請求項１に記載の方法。
【請求項４】
所定のリストから、所定のリストの識別子および復号された機密データ値を、１つまたは複数の予め定義された匿名性基準が前記所定のリストによって満たされるという条件で、少なくとも１つの処理デバイスによって出力するステップをさらに含む、請求項１に記載の方法。
【請求項５】
ダミーエントリを、１つまたは複数のリストに、少なくとも１つの処理デバイスによって加えるステップ、
１つまたは複数のリストから、エントリを、少なくとも１つの処理デバイスによって削除するステップ、および
出力された１つまたは複数のリスト内に、１つまたは複数のエントリを、少なくとも１つの処理デバイスによって維持するステップ
のうちの１つまたは複数をさらに含む、請求項１に記載の方法。
【請求項６】
メモリと、
メモリに接続された少なくとも１つのハードウェア処理デバイスと
を備えたシステムであって、
ハードウェア処理デバイスが、
ｐｉが第ｉデータ要素の識別部分を構成し、ｓｉが前記第ｉデータ要素の関連の機密情報部分を構成する、複数の前記データ要素（ｐｉ，ｓｉ）を含むデータストリームのデータ要素を受信し、
ｔ個の領域Ｓ１、Ｓ２、．．．、Ｓｔを含む分割された空間Ｓを、少なくとも１つの処理デバイスによって得て、
前記識別部分ｐｉを、前記領域のうちの選択された１つに、少なくとも１つの処理デバイスによって割り当て、
前記関連の機密情報部分ｓｉを、ｅ（ｓｉ）として、少なくとも１つの処理デバイスによって暗号化し、
メモリデバイス内の前記暗号化された関連の機密情報部分ｅ（ｓｉ）を、前記選択された領域に関連するリストに、少なくとも１つの処理デバイスによって格納するが、前記関連の識別部分ｐｉを使用して、前記関連の識別部分ｐｉを前記選択された領域に割り当てた後には、前記関連の識別部分ｐｉを、前記リストに格納しない
ように動作する、システム。
【請求項７】
前記少なくとも１つのハードウェア処理デバイスが、パーミュテーション関数およびハッシュ表のうちの１つまたは複数を使用して、前記選択された領域に関連する前記リストを、前記メモリデバイスの記憶位置にマッピングするようにさらに構成される、請求項６に記載のシステム。
【請求項８】
前記少なくとも１つのハードウェア処理デバイスが、
領域Ｓ１、Ｓ２、．．．、Ｓｔを含む前記分割された空間Ｓ内のいくつかの中心点Ｃ１、Ｃ２、．．．、Ｃｔを得て、
ｐｉに最も近い中心を計算する
ようにさらに構成され、
前記リストが、前記計算された最も近い中心に関連する、請求項６に記載のシステム。
【請求項９】
前記少なくとも１つのハードウェア処理デバイスが、所定のリストから、所定のリストの識別子および復号された機密データ値を、１つまたは複数の予め定義された匿名性基準が前記所定のリストによって満たされるという条件で、出力するようにさらに構成される、請求項６に記載のシステム。
【請求項１０】
プロセッサを、メモリからプログラム命令を受信するように構成するステップと、
前記プログラム命令を、前記メモリに記憶するステップと
を含む、処理システムを構成するための方法であって、
前記プログラム命令が、前記プロセッサによって読み取られた場合、前記プロセッサを、
ｐｉが第ｉデータ要素の識別部分を構成し、ｓｉが前記第ｉデータ要素の関連の機密情報部分を構成する、複数の前記データ要素（ｐｉ，ｓｉ）を含むデータストリームのデータ要素を受信し、
ｔ個の領域Ｓ１、Ｓ２、．．．、Ｓｔを含む、分割された空間Ｓを得て、
前記識別部分ｐｉを、前記領域のうちの選択された１つに割り当て、
前記関連の機密情報部分ｓｉを、ｅ（ｓｉ）として暗号化し、
前記暗号化された関連の機密情報部分ｅ（ｓｉ）を、前記選択された領域に関連するリストに格納するが、前記関連の識別部分ｐｉを使用して、前記関連の識別部分ｐｉを前記選択された領域に割り当てた後には、前記関連の識別部分ｐｉを、前記リストに格納しない
ように構成する、処理システムを構成するための方法。
【請求項１１】
前記プログラム命令が、プロセッサを、パーミュテーション関数およびハッシュ表のうちの１つまたは複数を使用して、前記選択された領域に関連する前記リストを、記憶位置にマッピングするようにさらに構成する、請求項１０に記載の方法。
【請求項１２】
前記パーミュテーション関数が、無作為に選択された［１，ｔ］上のパーミュテーション関数を含む、請求項１１に記載の方法。
【請求項１３】
前記プログラム命令が、プロセッサを、
前記分割された空間Ｓ内の領域Ｓ１、Ｓ２、．．．、Ｓｔに対応する、いくつかの中心点Ｃ１、Ｃ２、．．．、Ｃｔを得て、
ｐｉに最も近い中心を計算する
ようにさらに構成し、
前記リストが、前記計算された最も近い中心に関連する、請求項１０に記載の方法。
【請求項１４】
前記プログラム命令が、プロセッサを、所定のリストから、所定のリストの識別子および復号された機密データ値を、１つまたは複数の予め定義された匿名性基準が前記所定のリストによって満たされるという条件で、出力するようにさらに構成する、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データを匿名化するための技法、装置およびシステムに関する。
【背景技術】
【０００２】
本項では、本発明のよりよい理解を容易にするのに役立つ可能性のある態様を紹介する。従って、本項の記述は、この観点で読まれるべきであり、何が先行技術であるか、または何が先行技術ではないかに関する自認として理解されるべきではない。
【０００３】
変換されたデータが、いずれの個人のデータのプライバシも損なうことなく分析され得るように、機密データのストリームを変換し、前処理し、格納することが望ましい場合がよくある。ストリームデータ内のそれぞれのデータ項目は、通常、個人を識別する名前または住所などの第１の要素と、その個人が抱える病気などの個人に関するいくつかの個人および／または機密情報を含む第２の要素とを含む。個人のプライバシを維持しつつデータが分析されることを可能にする方法で、処理されたストリームがその後の分析のために保存され得るように、データの識別部分は変換されるべきである。一般的に、変換されたデータおよび関連の機密データを調べる研究者および／または分析者は、いずれの特定の個人の機密情報も識別できない状態で、データを分析し、データに関する合理的な（おおよそではあるが）結果を得ることができなければならない。例えば、研究者は、特定の地区における病気の調査を望む場合がある。
【０００４】
データ匿名化技法は、プライバシ問題に対処し、適用可能な法的要件の順守を手助けすることができる。変換されたデータが確実に特定の特性を有するようにすることによって様々なプライバシ目標を達成する、いくつかのデータ匿名化技法が提案または示唆されてきた。例えば、ｋ匿名性技法は、データセット内の各個人がｋ−１個の他の個人から区別不能でなければならないことを必要とする。また、ｌ多様性技法は、個人に関連する機密情報において十分な多様性を提供する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｂｅｎ  Ｍｏｒｒｉｓ、Ｐｈｉｌｌｉｐ  Ｒｏｇａｗａｙ、「Ｓｏｍｅｔｉｍｅｓ−Ｒｅｃｕｒｓｅ  Ｓｈｕｆｆｌｅ：Ａｌｍｏｓｔ−Ｒａｎｄｏｍ  Ｐｅｒｍｕｔａｔｉｏｎｓ  ｉｎ  Ｌｏｇａｒｉｔｈｍｉｃ  Ｅｘｐｅｃｔｅｄ  Ｔｉｍｅ」（未発表原稿、２０１３年８月）、例えば、ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１３／５６０．ｐｄｆを参照
【非特許文献２】Ｒａｓｍｕｓ  Ｐａｇｈ他、「Ｃｕｃｋｏｏ  Ｈａｓｈｉｎｇ」Ａｌｇｏｒｉｔｈｍｓ−ＥＳＡ２００１、Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ２１６１の講義ノート、１２１−１３３頁（２００１年）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
データの一部が公表され、他の人々と共有され得るように、効果的にデータを匿名化するための改善された技法が依然として必要とされている。
【課題を解決するための手段】
【０００７】
概して、データストリーム内のデータを匿名化するための方法および装置が提供される。一実施形態によれば、データストリーム内のデータは、ｐｉが識別部分を構成し、ｓｉが関連の機密情報を構成する、データストリームのデータ要素（ｐｉ，ｓｉ）を受信し、識別部分ｐｉを分割された空間Ｓの領域Ｓｉに割り当て、関連の機密情報ｓｉをｅ（ｓｉ）として暗号化し、暗号化された関連の機密情報ｅ（ｓｉ）を、割り当てられた領域Ｓｉに関連するリストに格納することによって、匿名化される。
【０００８】
さらなる実施形態によれば、パーミュテーション（ｐｅｒｍｕｔａｔｉｏｎ）関数πが、任意選択で、分割された空間Ｓ内の領域Ｓ１、Ｓ２、．．．、Ｓｔが格納される順番をランダム化して、相手が、データが特定の領域に格納されるのを観察することによって情報を得るということができないようにする。このように、領域Ｓｉに関連するリストは、パーミュテーション関数およびハッシュ表のうちの１つまたは複数を使用して、記憶場所に任意選択でマップされる。
【０００９】
例示的な一実施形態では、空間Ｓは、対応する中心点Ｃ１、Ｃ２、．．．、Ｃｔを有する領域Ｓ１、Ｓ２、．．．、Ｓｔに分割されて、ｐｉに最も近い中心Ｃｉが計算され、暗号化された関連の機密情報ｅ（ｓｉ）は、計算された最も近い中心Ｃｉに関連するリストに格納される。別の実施形態は、固定距離ｄに対して、十分な中心点Ｃ１、Ｃ２、．．．、Ｃｔがあるような、ユーザ規定の距離パラメータｄを提供し、それによってＳ内の任意の点ｐに対して、ある中心Ｃｉがあるようにし、それによってｐがＣｉまでの距離ｄ以下であるようにする。距離ｄは、一般的に、変換された識別情報が、それぞれのデータ要素に対する識別部分とどのように異なる必要があるかについての制限である。
【００１０】
本開示のより完全な理解とともに様々な実施形態のさらなる特徴および利点は、以下の発明を実施するための形態および図面を参照することによって得られるであろう。
【図面の簡単な説明】
【００１１】
【図１】様々な実施形態のプロセスを実施することができる、例示的なストリーミングデータ匿名化システムのブロック図である。
【図２】例示的な地理的地域に対応し、それぞれが対応する中心Ｃ１、Ｃ２、．．．、Ｃｔを有する複数の例示的な領域Ｓ１、Ｓ２、．．．、Ｓｔに分割された、例示的な空間Ｓを示す図である。
【図３】本発明の態様を具体化するストリーミングデータ匿名化プロセスの例示的な実施態様を示すフローチャートである。
【発明を実施するための形態】
【００１２】
本明細書に説明された実施形態は、ストリーミングデータを匿名化するための方法、装置およびシステムを提供する。図１は、例示的なストリーミングデータ匿名化システム１００、例えば、本開示の範囲内のプロセスの実施形態を実施することができるコンピュータシステムを示す。例示的なシステム１００は、様々な実施形態に従って、機密データを含むデータストリームを処理する。ストリームデータ内のそれぞれのデータ項目（ｐ，ｓ）は、通常、個人を識別する住所などの第１の要素ｐと、その個人が抱える病気などの個人に関するいくつかの個人および／または機密情報を含む第２の要素ｓを含む。様々な実施形態は、データの保護を確実にすることが技術的により難しくなっていることから、非保護の機密データが一時的にでもディスクに書き込まれるべきではないという認識を反映する。これは、いくつかの重要な適用の際の法的要件であり得ることが重要である。
【００１３】
図１に示されるように、メモリ１３０は、本明細書に開示されたストリーミングデータ匿名化の方法、ステップ、および機能（図１において、集合的に１５０として示され、図３に関連して以下にさらに述べられる）を実施するためのプロセッサ１２０を構成する。メモリ１３０は、分散型であってもローカル型であってもよく、プロセッサ１２０は、分散型であっても単体型であってもよい。メモリ１３０は、電気的メモリ、磁気メモリもしくは光メモリ、またはそれらもしくは他のタイプの記憶デバイスの任意の組合せとして、実装されてよい。プロセッサ１２０を構成するそれぞれの分散型プロセッサは、一般的に、それ自身のアドレス指定可能なメモリ空間を含むということに留意されたい。システム１００のいくつかまたは全ては、パーソナルコンピュータ、ラップトップコンピュータ、ハンドヘルドコンピューティングデバイス、特定用途向け回路または汎用集積回路に組み込まれ得るということにも留意されたい。
【００１４】
関連の機密データｓを伴う変換された識別データｐ’は、その全てが同じ変換された識別部分ｐ’を有するような１組のデータの一部として書き込まれ、個人の機密データｓが識別され得ないという特性（例えば、いわゆるｋ匿名性要件）の場合のみ、格納または送信され得るという場合を考えてみる。この目標は、未変換のデータ（ｐ，ｓ）が格納され得る固定サイズのＲＡＭバッファがあるという制約の下で達成され得る。さらなる実施形態によれば、変換された識別情報ｐ’が各個人の真の識別データｐとどのように異なる必要があるかに関して、制限が任意選択で定められる。この方法では、近似の変換データ（ｐ’，ｓ）は、真のデータ（ｐ，ｓ）の適切な表示であり得る。
【００１５】
以下で述べられるように、例示的な実施形態は、意味的にセキュアな暗号化、（無作為に選択された）パーミュテーション関数πまたはハッシュ表、およびクラスタリングヒューリスティックの組合せを使用する。様々な実施形態は、この中間機密データが暗号化される限り、このデータが記憶ディスク、フラッシュメモリデバイスまたはネットワーク記憶デバイスなどの記憶デバイスに記憶され得る、またはネットワークを介して送信され得るという認識を反映する。例示的なシステム１００は、図３に関連して以下にさらに述べられるように、分割された空間Ｓ内の特定のサブ領域Ｓｉに関連する特定のリストＬ（π（ｉ））に、変換された識別データｐ’および暗号化された機密データｅ（ｓ）を記憶するために、１つまたは複数の記憶ディスク１７０におけるディスク空き容量を、ＲＡＭのセキュアな拡張部として使用する。
【００１６】
図３に関連してさらに以下で述べられるように、例示的な一実施形態において、リストＬ（ｊ）などの特定のリストが、予め定義された匿名性基準を満たすと（例えば、リストが少なくともｋ個の要素を有する）、リストの要素は、復号され、以下の値がディスク１７０（または、別の記憶もしくは送信デバイス）に出力される：リストの中心Ｃｊ、リストからの復号された機密データ値。他の変形形態では、リストまたは領域の任意の識別子が提供され得る。
【００１７】
例示的な実施形態が、分割された空間Ｓ内の領域の最も近い中心Ｃｊを見つけるということで、本明細書に示されるが、当業者であれば明らかであるように、領域への任意の分割でも、使用され得る。別の例示的な変形形態では、空間Ｓは、グリッドに分割されることが可能で、未変換データ（ｐ，ｓ）がシステム１００に入ると、このデータは、例えば、グリッドセルのｘおよびｙ範囲に基づいて、空間Ｓの特定の領域Ｓｉに分類され得る。
【００１８】
例示的な実施形態は、データｐの識別部分が、ユークリッド空間などの、距離が定義される空間から来ると想定する。これによって、例えば、データは、位置データ、またはタプルのそれぞれの構成要素が距離尺度を有する任意のその他のタプルである可能性がある（以後、タプル間の距離は、Ｌ１、Ｌ２（ユークリッドメトリック）、．．．、またはＬ−無限大などの任意の多次元メトリックによって定義され得る）。全ての可能な識別データの空間をＳとする。
【００１９】
上に示されるように、変換されたデータ（ｐ’，ｓ）が、いずれの個人のデータのプライバシも損なうことなく分析され得るように、機密データのストリームを変換し、前処理し、格納することが望ましい場合がよくある。一般的に、変換された識別データｐ’および関連の機密データｓを調べる研究者および／または分析者は、いずれの特定の個人の機密情報ｐも識別できない状態で、データｓを調べ、データに関する合理的な（おおよそではあるが）結果を得ることができなければならない。例えば、研究者は、特定の地区における病気の調査を望む場合がある。
【００２０】
いくつかの実施形態は、機密データｓを、それが例示的なディスク１７０などのディスクに書き込まれる前に暗号化する。さらなる実施形態は、特定の領域Ｓｉ内の点の全てが、少なくとも、いずれのその他の中心に対してと同じくらい、領域Ｓｉの中心Ｃｉに近くなるように、空間Ｓを複数の領域Ｓ１、Ｓ２、．．．、Ｓｔに分割する。図２は、例示的な地理的地域に対応し、それぞれが対応する中心Ｃ１、Ｃ２、．．．、Ｃｔを有する複数の例示的な四角形領域Ｓ１、Ｓ２、．．．、Ｓｔに分割された（ｔは、図２の例示的な実施形態における９と同じである）、例示的な空間Ｓ２００を示す。図２の例示的な実施形態におけるそれぞれのデータ項目（ｐ，ｓ）の識別部分ｐは、住所に対応し、機密データｓは、その個人が抱える病気に対応する。
【００２１】
図２の例示的な実施形態では、それぞれの四角形領域Ｓｉは、地理的地域Ｓ２００の異なるサブ領域に対応する。ストリームデータ内のそれぞれのデータ項目（ｐ，ｓ）が処理される際、要素ｐに対応する住所は、データ項目（ｐ，ｓ）を、住所が示す特定のサブ領域Ｓ１、Ｓ２、．．．、Ｓｔに分類するために使用される。機密データｓの暗号化されたバージョンｅ（ｓ）は、適切なサブ領域内のディスクに記憶される。以下に述べられるように、所定のサブ領域Ｓｉ内の変換されたデータ項目の数が、規定の閾値を超える場合、サブ領域Ｓｉ内のそれらのデータ項目は、復号され、復号された機密データ値は、さらなる調査および／または分析のために出力され得る。
【００２２】
図３は、様々な実施形態に一致する、ストリーミングデータ匿名化プロセス３００の例示的な実施態様を示すフローチャートである。図３に示されるように、例示的なストリーミングデータ匿名化プロセス３００は、最初に、ステップ３１０において、領域Ｓｉ内の全ての点が、少なくとも、あらゆるその他の中心に対するのと同じように、Ｃｉに近くなるように、空間Ｓ内のいくつかの点Ｃ１、Ｃ２、．．．、Ｃｔ（中心と呼ばれる）を選び、空間Ｓの領域Ｓ１、Ｓ２、．．．、Ｓｔへの分割を定める（すなわち、ボロノイ図）。調整可能なパラメータであり得る固定距離ｄに対して、十分に多い好位置の中心が選択され、それによってＳ内の任意の点ｐに対して、ある中心Ｃｉがあり、それによってｐがＣｉまでの距離ｄ以下であるようにする（例えば、十分に細かいグリッド）。
【００２３】
ｐがデータの識別部分であり、ｓが関連の機密情報である、ストリームのデータ点（ｐ，ｓ）を考えてみる。その後、ステップ３２０において、（ｐ，ｓ）がシステム１００に入ると、ｐに最も近い中心Ｃｉと、値π（ｉ）が計算される（ここでπは無作為に選択された［１，ｔ］上のパーミュテーション関数である）。ディスク１７０において、暗号化されたデータのｔ個のリストＬ（１）、Ｌ（２）、．．．、Ｌ（ｔ）が以下のように作成される。機密データｓは、ｅ（ｓ）として暗号化され、ステップ３３０において、ｅ（ｓ）は、ディスク１７０におけるリストＬ（π（ｉ））に加えられる。暗号化は、任意の意味的にセキュアな暗号化であり得る（すなわち、２つの暗号化が同じ値を暗号化するかどうか、相手は見分けることができない）。意味的にセキュアな暗号化の例には、Ｅｎｃ＿ｋ（ｘ）＝ＡＥＳ＿ｋ（ｘ，ｒ）があり、ここでは、ｒは、無作為に選択された値である。
【００２４】
一般的に、パーミュテーション関数πは、相手が、データが特定の領域に格納されるのを観察することによって情報を得るということができないように、領域がＳ１、Ｓ２、．．．、Ｓｔで格納される順番をランダム化する。言い換えれば、パーミュテーション関数πは、中心Ｃｉを、ディスク位置にマッピングする。
【００２５】
この方法では、相手は、データをストリームに注入し、更新されたディスクの部分をモニタし、それによって、ディスクのどの部分が、その特定の領域についてのデータを含むかを知るということができない。また、ダミーデータ点を追加／削除し、全ての領域の成長／収縮を無作為に維持することによって、タイミングアタックを任意選択で軽減し、それによって、相手が、実際のデータがどこに行くのか、またはどこから書き込まれるかを決定することができないようにする。
【００２６】
パーミュテーション関数は、任意の無作為に選択されたパーミュテーション関数として具体化され得る。Ｓｉの小さな組では、パーミュテーションは、全体マップπ（１）、π（２）などを列挙することによって、生成され、ＲＡＭに記憶され得る。より大きな組では、記憶されるには鍵のみが必要で、マッピングは、記憶された鍵から生成され得る。任意のサイズのドメインにおいて、擬似ランダム置換を生成するための例示的な技法の論述に関しては、例えば、Ｂｅｎ  Ｍｏｒｒｉｓ、Ｐｈｉｌｌｉｐ  Ｒｏｇａｗａｙ、「Ｓｏｍｅｔｉｍｅｓ−Ｒｅｃｕｒｓｅ  Ｓｈｕｆｆｌｅ：Ａｌｍｏｓｔ−Ｒａｎｄｏｍ  Ｐｅｒｍｕｔａｔｉｏｎｓ  ｉｎ  Ｌｏｇａｒｉｔｈｍｉｃ  Ｅｘｐｅｃｔｅｄ  Ｔｉｍｅ」（未発表原稿、２０１３年８月）、例えば、ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１３／５６０．ｐｄｆ）を参照、を参照されたい。
【００２７】
ハッシュ表の実施態様は、カッコウハッシュなどの標準ハッシュ表データ構造を使用することができる。例えば、Ｒａｓｍｕｓ  Ｐａｇｈ他、「Ｃｕｃｋｏｏ  Ｈａｓｈｉｎｇ」Ａｌｇｏｒｉｔｈｍｓ−ＥＳＡ２００１、Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ２１６１の講義ノート、１２１−１３３頁（２００１年）を参照されたい。
【００２８】
最後に、ステップ３４０において、いずれの時点でも、リストＬ（ｊ）などの、リストのうちの１つが使用される予め定義された匿名化基準を満たすということ（例えば、リストが、少なくともｋ個の要素を有する）が検出されると、ステップ３５０において、リストの要素は、復号され、以下の値がディスク１７０に出力される（またはネットワークを介して送信される）：リストの中心Ｃｊ、リストからの復号された機密データの値。
【００２９】
例示的な一実施形態では、暗号化されたデータのリストＬ（１）、Ｌ（２）、．．．、Ｌ（ｔ）は、任意選択で、ダミーエントリを１つまたは複数のリストに追加し、１つまたは複数のリストからエントリを削除し、またすでにディスクに書き込まれたいくつかのエントリを維持することによって、ほぼ等しいサイズで保持される。この方法では、タイミング技法を使用した、機密情報の漏洩が低減される。
【００３０】
パーミュテーションによる、中心Ｃｉのディスク位置へのマッピングは、点Ｃｉの数が比較的少なければ、効率的である。このような中心が多くあり得るが（例えば、ディスク記憶位置よりも多い）、Ｃｉの全てがポピュレートされるわけではない場合では、ハッシュ表は、Ｃｉのディスク位置マッピングの実施態様として、使用され得る。一般的に、ハッシュ表は、ディスクアドレスからＣｉを明らかにすることができるので、Ｃｉは、Ｃｉを位置に対するハッシュ関数鍵として使用する前に、確定的に暗号化される。確率的暗号化が、特定のＣｉに対して、一貫して同じディスク位置を割り振ることを可能にしない可能性がある際に、確定的暗号化が必要とされる。
【００３１】
最後に、ハッシュ表をディスク位置のための機構として使用することは、Ｃｉ情報を記憶するために使用されるディスク位置の簡単な更新／再ランダム化を可能にする。確かに、カウンタと連結されたＣｉを簡単に暗号化することは、Ｃｉに対する新しいリンク対象外の位置の割り振りを可能にする（（Ｃｉ）毎の現在のカウンタが、ＲＡＭに記憶される必要がある）。
【００３２】
例
ｐが、通信（例えば、テキストメッセージ、通話）の地理的エンドポイントを含み、ｓが、通信の種類および持続時間である場合のデータ（ｐ，ｓ）の供給を考えてみる。データのこのストリームは、サービスプロバイダ（ＳＰ：Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）によって、１つのコンピュータ（または複数のコンピュータ）の実行に加わる。多くの地理的地域において、ＳＰは、この供給からデータ点を記録することが法的に許されない。すなわち、ＳＰは、（ｐ，ｓ）をディスクに書き込むことができない。ＳＰは、例えば、ネットワーク構成を最適化するため、よりよい価格設定計画を立てるため、またはチャーン（ｃｈｕｒｎ）を防ぐために、このデータにおいて、いくつかの分析的計算を行うことを望む。コンピュータは、限られたメモリ（すなわち、限られたバッファサイズ）を有する。様々な実施形態において、ＳＰは、ディスクに、後の分析のために使用される「匿名化された」データを書き込むことができる。例えば、ＳＰは、実際のｋ個の（またはより多くの）通信エンドポイントペアのおおよその位置を表す値を、これらのｋ個の（またはより多くの）通信ペアについての付随する機密データを伴って、印刷出力することができる。このような点の組は、限られたメモリが一杯になると、定期的にディスクに書き込まれる
可能性がある。
【００３３】
例示的な方法の独自の特徴は、この方法が、ユーザが識別データの近似値における上限を規定することを可能にするということである。すなわち、ユーザは、（ｐ１，ｓ１）、（ｐ２，ｓ２）、．．．、（ｐｋ，ｓｋ）などのデータが、ディスクに｛Ｃｉ，ｓ１，ｓ２，．．．，ｓｋ）の形式で書き込まれる時はいつでも、任意のｐｊとＣｉとの間の最大距離は、ある距離ｄであると言うことができる。すなわち、近似値の品質はユーザによって規定され得る。これによって、いくつかの利益の中でも特に、開示された方法は、ユーザが、受け入れられる近似値の程度を規定することを可能にする。
【００３４】
また、暗号化されたデータを慎重にディスクに記憶することによって、信頼されるバッファ（すなわち、ＲＡＭの）有限サイズは、もはや制限とはならない。
【００３５】
システムおよび製造品の詳細
図３は、例示的な一連のステップを示すが、様々な実施形態において、順序が変更される場合がある。代替えの実施形態として、アルゴリズムの様々なパーミュテーションが考えられる。
【００３６】
本発明の様々な実施形態が、当業者には明らかであるように、ソフトウェアプログラムにおける処理ステップに関して説明されたが、様々な機能は、ソフトウェアプログラム内の処理ステップとしてのデジタルドメインにおいて、回路要素またはステートマシンによるハードウェアにおいて、またはソフトウェアとハードウェアの両方の組合せにおいて、実施され得る。このようなソフトウェアは、例えば、デジタルシグナルプロセッサ、特定用途向け集積回路、マイクロコントローラ、または汎用コンピュータにおいて使用され得る。このようなハードウェアおよびソフトウェアは、集積回路内で実装される回路内で具体化され得る。
【００３７】
このように、本発明の機能は、これらの方法を実施するための方法および装置の形態で、具体化され得る。本発明の１つまたは複数の態様は、例えば、記憶媒体に記憶される、マシン内にロードされる、および／またはマシンによって実行される、またはいくつかの伝送媒体を介して送信されるかどうかのプログラムコードの形態において具体化され得て、この場合、プログラムコードがコンピュータなどのマシン内にロードされ、そのマシンによって実行されると、マシンは、本発明の１つまたは複数の実施形態に従って構成された装置になる。汎用プロセッサにおいて実施される場合、プログラムコードセグメントは、プロセッサと組み合わさり、特定の論理回路に類似して動作するデバイスを提供する。実施形態は、集積回路、デジタルシグナルプロセッサ、マイクロプロセッサ、およびマイクロコントローラのうちの１つまたは複数においても実施され得る。
【００３８】
当技術分野において知られているように、本明細書に述べられた方法および装置は、それ自体が、コンピュータ可読コード手段をその上に具体化した有形のコンピュータ可読記録可能媒体を含む、製造品として配給され得る。コンピュータ可読プログラムコード手段は、コンピュータシステムと連動して、本明細書に述べられた方法を行う、または装置を作り出すためのステップの全てまたはいくつかを実行するように、動作可能である。コンピュータ可読媒体は、記録可能媒体（例えば、フロッピーディスク、ハードドライブ、コンパクトディスク、メモリカード、半導体デバイス、チップ、特定用途向け集積回路（ＡＳＩＣ：Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ））であってもよく、または伝送媒体（例えば、光ファイバを含むネットワーク、ワールドワイドウェブ、ケーブル、または時分割多元接続、符号分割多元接続、もしくはその他の無線周波数チャネルを使用した無線チャネル）であってもよい。コンピュータシステムで使用するのに適した、情報を格納することができる、知られている、または開発された媒体であれば、使用され得る。コンピュータ可読コード手段は、磁気媒体における磁気変化またはコンパクトディスクの表面上の高さ変動などの、コンピュータが命令およびデータを読み取ることを可能にするための任意の機構である。
【００３９】
本明細書に記載されたコンピュータシステムおよびサーバはそれぞれ、本明細書に開示された方法、ステップ、および機能を実施するための関連のプロセッサを構成することとなるメモリを含む。メモリは、分散型またはローカル型である可能性があり、プロセッサは、分散型またはただ１つである可能性がある。メモリは、電気的メモリ、磁気メモリもしくは光メモリ、またはこれらもしくはその他のタイプの記憶デバイスの任意の組合せとして、実装される可能性がある。また、「メモリ」という用語は、関連のプロセッサによってアクセスされる、アドレス指定可能な空間内のアドレスから読み取る、またはそのアドレスに書き込むことができるあらゆる情報を包含するとして、十分に広く解釈されるべきである。この定義では、関連のプロセッサがネットワークから情報を取得することができるので、ネットワーク上の情報は、依然としてメモリ内にある。
【００４０】
本発明は、他の特定の装置および／または方法において具体化され得る。記載された実施形態は、あらゆる点で単なる例示にすぎず、限定的に解釈されてはならない。特に、本発明の範囲は、添付の特許請求の範囲によって示されるものであって、本明細書の説明および図面にはなんら拘束されない。特許請求の範囲の均等の意味および範囲に属する変更は、全て本発明に含まれるものである。
【図１】
0006352441.tif 000002
【図２】
0006352441.tif 000003
【図３】
0006352441.tif 000004