(57)【要約】  本発明は、信頼できない環境において記憶装置にデータを記憶して読み出す方法に関し、これらのデータは、木構造のデータノードにそれぞれ対応付けられている。
2022500884.tif 000002
【特許請求の範囲】
【請求項１】
信頼できない環境において記憶装置にデータを記憶して読み出す方法であって、前記データは、木構造のデータノードにそれぞれ対応付けられており、
それぞれのデータノードは、前記データノードの兄弟データノードに対して前記データノードを一意に識別するデータノードフラグを有し、
それぞれのデータノードは、現行のデータノード鍵を有し、
好適にはアクセスデータからの計算により、少なくとも１つのデータノード鍵が手動であらかじめ設定されているルートデータノードが設けられており、
すべての子データノードにより、前記ルートデータノードから出発して、それぞれの現行の親データノード鍵を取り入れて、前記子データノードの現行データノード鍵を再帰的に計算し、
前記記憶装置に記憶する前に、データに属するデータノードの前記現行のデータノード鍵によって前記データを暗号化し、
前記記憶装置における読み出しの後、前記現行のデータノード鍵によって前記データを復号する、前記方法において、
データノード鍵生成ステップを定義し、前記データノード鍵生成ステップは、それぞれのデータノードにおいて時間的に依存せずに任意の回数だけ適用可能であり、かつ前記データノード鍵生成ステップでは、データノードに適用する際には、
前記データノードについて新たなデータノード鍵インデックスを生成し、
少なくとも前記データノードの前記データノードフラグと、前記新たなデータノード鍵インデックスと、前記親データノードの現時点での現行データノード鍵とに適用されるセキュアなハッシュ関数の結果にデータノード鍵が対応することにより、前記データノード鍵を計算して現行のデータノード鍵として設定し、
前記新たなデータノード鍵インデックスならびに前に計算した前記データノード鍵を一時的なリストの末尾に挿入しかつ前記前に計算した前記データノード鍵を現行のデータノード鍵にすることにより、データノード鍵インデックス列およびデータノード鍵列を含む一時的なデータノード鍵リストを作成もしくは拡張し、
非一時的なリストの末尾において、前記データノードの前記新たなデータノード鍵インデックスをデータノードインデックス列に挿入し、また前記親データノードの前記データノード鍵パラメータリストから現在の最後のデータノード鍵インデックスを親データノードインデックス列に挿入することにより、前記データノードインデックス列および前記親データノードインデックス列を含む、前記データノードについての非一時的なデータノード鍵パラメータリストを作成もしくは拡張し、これにより、複数の秘密鍵の代わりに、公開インデックスだけを前記鍵の代理として非一時的に記憶し、
データノードのデータを記憶する前に、
前記ルートデータノードから前記データノードまで、前記木構造におけるパスを特定し、
前記ルートデータノードの第１子からはじめて、特定した前記パスを１つのデータノードまた１つのデータノードとたどり、
データノードの前記非一時的なデータノード鍵パラメータリストのそれぞれ最後のエントリと、前記データノードの親データノードとを比較し、
データノードの前記親データノードインデックス列からの前記最後のエントリと、前記データノードの親データノードの前記データノード鍵パラメータリストからの前記データノードインデックス列における最後のエントリとが同じでない場合には、前記データノードおよび前記パスにおいて後続するデータノードに、
前に定義した前記データノード鍵生成ステップをそれぞれ適用し、
前記データに属する前記データノードの前記現行データノード鍵によって前記データノードのデータをそれぞれ暗号化し、前記データノードに対応付けられている前記非一時的なデータノード鍵パラメータリストを記憶する、ことを特徴とする、方法。
【請求項２】
前記非一時的なデータノード鍵パラメータリストの連続する行番号付けをデータノードについてのデータノード鍵インデックスとして使用し、現行の最後の行番号を１だけインクリメントすることにより、新たなデータノード鍵インデックスを計算し、
これにより、前記データノードインデックス列は、連続する番号付けによって得られるため、前記非一時的なデータノード鍵パラメータリストにおける前記データノードインデックス列の前記記憶が省略される、ことを特徴とする、請求項１記載の方法。
【請求項３】
前記データノード鍵パラメータリストを、圧縮されたデータノード鍵パラメータリストに変換し、前記圧縮されたデータノード鍵パラメータリストだけを非一時的な前記記憶装置に記憶し、同じエントリを有する複数の領域および連続する複数のエントリを有する複数の領域が、前記圧縮されたデータノード鍵パラメータリストにおける１つの値によってそれぞれ表されるように、前記データノード鍵パラメータリスト内の複数の領域をまとめる、ことを特徴とする、請求項２記載の方法。
【請求項４】
前記データノード鍵パラメータリストを、圧縮されたデータノード鍵パラメータリストに変換し、数０を現行の比較インデックスとして、前記データノード鍵パラメータリストにおける第１親データノードインデックスを次の比較インデックスとして、値１を現行の比較間隔として、かつ値０を現行の比較間隔カウントとして設定することにより、前記圧縮されたデータノード鍵パラメータリストだけを前記非一時的な記憶装置に記憶し、
それぞれの前記次の比較インデックスと、それぞれの前記現行の比較インデックスとの差分を計算する比較ステップを定義し、
計算した前記差分が、前記現行の比較間隔と等しい場合、前記現行の比較間隔カウンタを値１だけインクリメントし、
計算した前記差分が、前記現行の比較間隔と等しくなくかつ１よりも大きい場合、かつ前記現行の比較間隔カウンタが０よりも大きい場合、前記圧縮されたデータノード鍵パラメータリストの最後の位置に前記現行の比較間隔カウンタを付加し、
前記差分に負の符号を付して前記差分を前記圧縮されたデータノード鍵パラメータリストの末尾に付加し、ならびに
前記現行の比較間隔を値１に、前記現行の比較間隔カウントを０に設定し、
前記計算した差分が、前記現行の比較間隔に等しくなくかつ１以下の場合、
前記圧縮されたデータノード鍵パラメータリストの最後の位置に前記現行の比較間隔カウンタを付加し、
前記現行の比較間隔の値に依存して、前記現行の比較間隔を０もしくは１に変化させ、前記現行の比較間隔カウンタを１に設定し、
次いで、前の前記次の比較インデックスを前記現行の比較インデックスにし、前記現行の比較インデックスに続く前記親データノードインデックスを前記次の比較インデックスにし、
前記現行の比較インデックスが、最後の前記親データノードインデックスに等しくなるまで、それぞれの前記現行の比較インデックスおよび前記次の比較インデックスに前記比較ステップを適用し、最後に前記現行の比較間隔カウンタが０よりも大きい場合、前記圧縮されたデータノード鍵パラメータリストの最後の位置に前記現行の比較間隔カウンタを付加する、ことを特徴とする、請求項２または３記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明が目標とするのは、例えば、暗号化木構造におけるファイルまたは別のデータが、信頼できない環境に格納される暗号化ファイルシステム（ＣＦＳ：Crytographic File System）を実現するための性能最適化されたセキュアな階層型参照システムである。このシステムは、クライアント（ユーザ）側でデータが鍵によって暗号化される適応型暗号化アクセスコントロール（ＡＣＡＣ：Adaptive Cryptographic Access Control）によって動作する。ここでは（エントリ鍵を除く）すべての鍵を記憶せずに計算し、また参照システムにおける要素（例えば、ファイル、データセット、コメント）毎に専用の対称鍵を利用しようとしており、これにより、要素レベルにおいて、選択された第三者に読み出し資格および書き込み資格を許可し、また必要に応じて再度、アクティブに失効させることが可能である（シェアリング／リボケーション）。
【０００２】
この参照システムにより、古典的なアクセス方法および認証方法が置き換えられ、また個別要素ベースの対称鍵により、高性能かつエラー耐性を有するアクセスだけでなく、特に個々の要素のアクティブな失効も可能になる。
【０００３】
効率上の理由から、暗号化の際にはレイジーリボケーション(lazy revocation)アプローチが利用され、すなわち、新たな鍵の生成は、ユーザが失効された後に直ちに行われるのでなく、データを記憶する際にはじめて行われる。
【０００４】
従来技術
現在の従来技術によれば、上の目標をカバー可能な方法は存在しない。公知の複数の方法は、部分的に要件をカバーするが、現在の従来技術によれば、これらを互いに組み合わせることはできない。
【０００５】
鍵を「記憶しない」という目標は、鍵導出のための方法（ＫＤＡ：Key Derivation Algorithm）のようないわゆる依存鍵モデル（Depended Key Model）によって達成可能である。というのは、使用されるすべての鍵が計算されてランダムに生成されないからである。しかしながらこの方法は、性能最適化された参照システムという目標とは相反する。というのは、権限の失効の際には、参照されるすべてのデータ要素を完全に新たに暗号化する必要があるからである（アクティブリボケーション）。この性能問題は、レイジーリボケーションアプローチによって解決可能と思われる。レイジーリボケーションは、特に、ユーザグループが大量のデータを互いに共有する場合には、今日のクラウド記憶システムに対する重要な要件である。データの失効（リボケーション）の際に、クライアントベース暗号化方法では、まずすべてのデータをクライアントにダウンロードし、新たな鍵で暗号化し、新たに暗号化されたデータを再度、サーバにアップロードしなければならないアクティブリボケーション方法とは異なり、レイジーリボケーションでは、データはつねに、これが変更された場合、ひいてはいずれにせよ新たに暗号化しなければならない場合にのみ新たに暗号化される。
【０００６】
したがってレイジーリボケーションは、暗号化されたデータに対するアクセスを有していた人が、このデータが変更されない限り、このデータへのアクセスを引き続いて有するという妥協である。
【０００７】
レイジーリボケーションにおいてセキュリティは、変更されていないデータが、引き続いてそれまでの暗号化によって保護され、新たなまたは変更されたデータが新たな鍵によって暗号化され、これらの鍵が、アクセス権失効後も引き続いてこれらのデータについてのアクセス許可を有するユーザに分配されることによって保証される。
【０００８】
しかしながらレイジーリボケーション法は、現在の従来技術においてＫＤＡと相反する。というのは、これにより、エントリ鍵からはじまる鍵チェーンは、もはや連続しなくなってしまい得るからである（ＫＤＡでは、それぞれの下位の鍵は、その先行鍵を使用して計算されるが、レイジーリボケーションでは、１つの要素は、対応付けられている複数の鍵を有することがあり、これにより、鍵計算はもはや一意にならない）。したがってレイジーリボケーションアプローチでは、使用されるすべての鍵を記憶し、分配する必要があり（結果的に独立型鍵モデルになり）、このことは、鍵を記憶しないという目標と相反する。
【０００９】
従来技術における１つの妥協は、Atallah、FrikkenおよびBlantonの鍵管理方法（およびその変形形態）であり、ここでは、独立型鍵モデルにおいて、すべての権限保持者への鍵分配の必要性は、要素毎に公開補助値を導入することによって置き換えられ、これらの値は、ノード鍵の値を差し引いて親鍵のハッシュから計算可能である。同様にノード鍵は、親鍵のハッシュから補助鍵のハッシュを差し引くことによって計算される。しかしながらここでは要素毎に公開補助鍵を記憶しなければならず、したがって１つの補助鍵を失うことは、下位のすべてのノード鍵を失うことを意味する。このことは、セキュアかつエラー耐性を有する参照システムを実現するという目標に相反する。
【００１０】
レイジーリボケーションの別の大きな欠点は、持続的に計算が集中することと、鍵を記憶しなければならないことにより、オーバヘッド負荷が加わる鍵管理（鍵生成および分配）になってしまうこととである。個々のデータ要素毎に、独立して取り換え可能な鍵を使用できるようにするという本発明の目標を達成するために、レイジーリボケーションでは、それぞれの個別の鍵を記憶しなければならない。データが第３者とも共有されるようにしようとする場合、この鍵は、（例えば第３グループの公開ＲＳＡ鍵によって）暗号化して記憶しなければならないことにもなる。これにより、例えば、３つのグループとデータを共用する際には、暗号化された４つの鍵を記憶しなければならないことになる（１つは、固有の鍵によって、次に第３グループの公開鍵によってそれぞれ暗号化される）。多くのデータおよび利用者を有するシステムをベースにする場合、明らかになるのは、なぜ、鍵管理のオーバヘッドおよび複雑さに起因して、レイジーリボケーションが、個別要素ベースで実践的に適用されないかであり、そうでない場合には、データノードおよび利用者毎に上で説明したように特定の鍵を記憶し、分配し、これを利用者の追加および特に失効する都度に実行しなければならないことである。したがって要素毎の性能指向の参照システムという目標は、これによっては実現できない。
【００１１】
これを実践的に適用できるようにするためには、必要でありかつ記憶される鍵の個数を少なくしなければならない。これは、従来技術では、権限グループ（例えばディレクトリにおけるファイル）にデータをまとめることによって行われ、これにより、権限グループ内のすべてのデータは、同じ鍵で暗号化可能である。それぞれの権限グループは、別の権限グループの鍵とは独立して、その鍵を取り換えできなければならない。この独立性により、第３者の権限が失効された後、直ちに権限グループ内のデータを新たに暗号化する必要はもはやなくなり、その代わりに木の要素（例えばサブディレクトリおよびファイル）に対して再帰的にマーク（この技術分野の用語では「ダーティフラグ」（Dirty-Flag）と称される）をセットするので十分である。次にデータの記憶（変更、付加）の際にはじめて、このマークがセットされている（したがってこの権限グループについて新たな鍵を生成して権限が付与されたすべての第３者に分散しなければならない）か否か、または、（ダーティフラグがセットされていない場合）既存の鍵を使用するので十分であるか否かが検査される。新たな鍵によってデータが暗号化された後、この権限グループについての「ダーティフラグ」は除去される。
【００１２】
しかしながらここでは、個別のデータではなく、権限グループ（例えばディレクトリ、データ空間）だけに参照の可能性が得られるのと引き換えに分配問題（ごくわずかな鍵についてではあるが）が残る。さらに、このグループの（例えばファイルの）要素毎に、この要素について使用される鍵への参照を作成しなければならない。というのは、このような手法により、１つの権限グループに対して複数の鍵が存在する可能性があるからである。
【００１３】
これは、従来技術において、権限グループに対応付けられる２つのリストによって実現可能である。まずそれぞれの権限グループに使用されるすべての鍵が、暗号化されない形態で格納されている鍵リストと、この権限グループのすべての要素（ファイル）が、要素の暗号化に使用される鍵への参照指示と共に記憶されている第２参照リストとによって実現可能である。
【００１４】
最適化された記憶および計算のために、このような鍵リストは、従来技術では、例えば、暗号化リンクにより、すなわち、
Ａ）ハッシュリストによって実現可能であり、それぞれ現行鍵は、
新しい鍵＝セキュアハッシュ（以前の鍵"Salt"）
で計算される。
【００１５】
この場合、あらかじめ定められた個数の要素（鍵）を有するリストは、開始点から出発して、複数のハッシュをチェーンで結ぶことによって生成される。一般にこの計算はさらに、計算のエントロピーを増大させるために、ランダムに選択される文字列（「ソルト（Salt）」と称される）によって補足される。チェーンで結ばれたこのリストにより、特に可能になるのは、このリストの任意の要素（鍵）を、その位置を含めて分配することであり、ここから、後続の要素（鍵）を計算することである。しかしながら、開始点から、先行するこの鍵を計算することはできない。というのは、セキュアなハッシュ関数は、一方向性関数だからである。したがって、新たな鍵が要求される際には、十分に長いハッシュリストを計算した人が、現行の要素（鍵）に先行する要素（鍵）を転送しなければならない。
【００１６】
したがってこのようなリストにおいて、所有者にとっては、先行するすべての鍵を計算することが可能なリストの最後のエントリを記憶しなければならない（もしくはこれは、秘密の情報から到達可能でなければならない）。ここではリストにおける最後の要素は、第１鍵に対応し、最後から２番目の要素は、第２鍵に対応する、等々である。
【００１７】
すなわち、アクセスのためにただ１つの鍵だけを記憶すればよいという利点は、あらかじめ設定された長さが必要であることによって獲得される。これが、あまりに小さく選択されると、場合によっては十分な鍵は得られず、あまりに大きく選択されることになれば、長くかつ不要な計算時間が生じることになる。というのは、この計算は、最後の要素においてそれぞれ開始されるからである（例えば、現在３つの鍵だけが存在するが、百万の長さが選択されるとすると、百万番目のエントリからはじめて、下方に向かって第３の鍵まですべての鍵を計算しなければならないことになる）。このような理由から、この選択肢は、実践的に使用されることがない。
【００１８】
Ｂ）鍵リストとして実現され、それぞれの現行鍵は、ハッシュ関数を介してではなく、対称または非対称の暗号化を介して
現行鍵＝AES_decrypt（現行鍵、後継鍵）
のように計算される（例えば、米国特許第７２０３３１７号明細書を参照されたい）。
【００１９】
この場合、リストの長さは、はじめからあらかじめ設定されているのではなく、任意に拡張可能である。ここでは、それぞれの現行鍵は、その後継鍵によって暗号化され、これにより、それぞれの鍵は、ユーザによって自由に選択されていてよい。しかしながらハッシュリストとは異なり、ノード毎に１つのエントリ（自由に選択される後継鍵）を記憶しなければならない。
【００２０】
これにより、まず同じデータについて複数の現行鍵が存在することがあり、そのベース鍵をそれぞれ記憶しなければならないことになる。さらにノードおよびアクセス権限が与えられたグループ毎に、利用されるすべての鍵が存在することを保証しなければならず、これにより、エラー耐性の際に問題が発生する。
【００２１】
さらに、どのデータももはやこの鍵によって暗号化されないことが保証される場合に、鍵ははじめて廃棄可能である。これに対応して、鍵の記憶および鍵の分配のためのオーバヘッドおよび複雑さも増大する。
【００２２】
したがって上で説明した問題および欠点を解消するため、冒頭に説明した目標を達成する新たな方法が必要であった。ここでは既存の方法から複数の着想が取り上げられ、最適化され、新たな方法ステップが補足された。このことが本発明に結び付いている。
【００２３】
本発明の方法の流れ
鍵管理を簡略化し、レイジーリボケーションにおける鍵の記憶を最小化するために、本発明では、特に、親データノードのデータノード鍵からデータノード鍵を導出する。しかしながらレイジーリボケーションでは、子ノードが、親ノードよりも古い鍵を有することがあり得るため、親鍵のどのバージョンが、現在、現行であるかを覚えておく必要がある。
【００２４】
親データノード鍵は、独立して変化し得るため、それぞれのデータノードにおいて暫定的な（一時的な）データノード鍵リストが保持されることは本発明の重要な構成部分であり、このデータノード鍵リストには、それぞれの鍵に対応付けられる鍵インデックスが書き留められる。このリスト内では、データノードに対応付けられている鍵が、番号付けされたリストに格納され、このリストの最後のエントリが、現行鍵に対応する。
【００２５】
付加的には、それぞれの鍵に対し、データノード毎に、どの親データノード鍵を利用して鍵が生成されたかを書き留める必要がある。これは、本発明では、子鍵および親鍵のインデックスがリンクされている（非一時的な、すなわち記憶される）データノード鍵パラメータリストによって実現される。これにより、子データノード毎に、記憶された親インデックスに属する鍵を見つけ出すことができる（これにより、ここでも子ノードの鍵を計算するために、使用される秘密を利用可能である）。
【００２６】
これらの２つのリストの組み合わせによってのみ可能になるのは、アクティブリボケーションの利点を利用して拡張すること（持続的に記憶される鍵を必要とする代わりの、暗号化および復号のためにデータノード毎に計算される現行のデータノード鍵）と、レイジーリボケーションの利点（データはつねに、データが記憶される場合にのみ新たに暗号化される）とを組み合わせることである。これにより、今日の一般的な鍵記憶および鍵分配が、一貫した鍵計算によって置き換えられる。この組み合わせは、従来技術において公知ではなく、また当業者にとって明白でもない。
【００２７】
データノード鍵には、生成のために少なくとも前に使用された親データノードの複数のデータノード鍵のうちの１つが含まれているため、必要であるのは、ルートから、記憶を行うデータノードまで木のパスをたどり、親データノードが、現行のデータノード鍵の鍵生成についてのベースとして使用された親データノード鍵よりもより新しいデータノード鍵をどの箇所に有するかを検査し、鍵およびインデックスを場合によって更新し、ならびにデータを新たな鍵によって暗号化することである。これによって保証されるのは、データノードに対応付けられるデータを記憶する際に、パスに沿って、すべての親データノードのすべての鍵およびインデックスが前もって更新されていることであり、ひいてはデータが、有効な（除外されたユーザが有しない）現行鍵によって暗号化されることである。
【００２８】
本発明の方法の付加価値
ＫＤＡ（すべての鍵を記憶する代わりの、親ノードの鍵を使用した鍵計算）と、レイジーリボケーション（変更されたデータだけが暗号化されることによる効率改善）との利点の組み合わせ。これは、従来技術において関連する複数の欠点を回避して行われる。
・（アクティブ）リボケーションにおけるすべてのデータノードの新たな暗号化の必要性は、レイジーリボケーションアプローチによって置き換えられる。
・レイジーリボケーションの場合のように１つのノードについて複数の鍵が必要とされる（１つのノードは複数の要素を含み得る）のではなく、ただ１つの現行の計算される鍵だけが存在する。
・今日の従来技術において一般的な「ダーティフラグ」は、現行の親鍵が非一時的なリストに書き留められている親鍵と同一であるかの比較によって置き換えられる。同一でないインデックスは、セットされたダーティフラグに対応する。
・本発明による方法により、ただ１つのエントリ鍵を木に記憶すればよい（かつすべての鍵を記憶する必要がない）という特徴と共に、レイジーリボケーションに課されるすべての要件が達成される。さらにこの方法によって可能になるのは、木のノード毎に固有の鍵を得ることであり、すなわち例えばそれぞれのファイルは、別の鍵によって暗号化される。
・今日の一般的なレイジーリボケーション法とは異なり、データのプログラミングおよびオーバヘッドは簡素化される。というのは、「ダーティフラグ」は、権限の失効に該当するすべてのデータノード（ディレクトリ／ファイル／…）を通して再帰的にセットされず、また、復号のために設けられているデータノードのリストから、具体的なデータノード鍵を選択する必要がないからである。
【００２９】
これによって可能になる簡素化および効率改善により、鍵が持続的に記憶されずかつ鍵管理が大いに簡素化される、個別要素ベースでの暗号化に対するスケーラブルな解決手段が得られる。これにより、個別要素ベースでのアクティブな権利失効も可能になる。
【図面の簡単な説明】
【００３０】
【図１】従来技術においてレイジーリボケーションに使用される鍵リストおよび参照リストの一実施例を示す図である。
【図２】プリアンブルにおいて定義される、請求項１による中核コンポーネントを示す図である。
【図３】請求項１による鍵管理のために、一時的なデータノード鍵リストが拡張される適用例を示す図である。
【図４】請求項１にしたがい、参照のために非一時的なデータノード鍵パラメータリストが拡張された適用例と、インデックスおよび鍵の新たな計算とを示す図である。
【図５】請求項１にしたがって定められる生成ステップを実行する適用例を示す図である。
【図６】請求項４にしたがい、データノードパラメータリストを圧縮記憶する方法を説明する図である。
【図７】図６についての凡例を説明する図である。
【図８】請求項４にしたがい、一適用例を説明する図である。
【図１】
2022500884.tif 000003
【図２】
2022500884.tif 000004
【図３】
2022500884.tif 000005
【図４】
2022500884.tif 000006
【図５】
2022500884.tif 000007
【図６】
2022500884.tif 000008
【図７】
2022500884.tif 000009
【図８】
2022500884.tif 000010
【国際調査報告】
2022500884.tif 000011
2022500884.tif 000012
2022500884.tif 000013
2022500884.tif 000014
2022500884.tif 000015
2022500884.tif 000016