データ保全性検証方法、装置、およびシステム
【課題】長期アーカイブサービスの目的は、データの存在否認の防止、データ保全性、およびデータオリジンをサポートすることであり、長期アーカイブサービスは、データを受け入れた時からデータの保管期間の終了時まで、データの保全性を検証する方法を提供する。
【解決手段】最初にデータのフィンガープリントがクライアントで生成され、そのフィンガープリントがデータと共にアーカイブに送信され、続いて、必要が生じたときにクライアントがデータの保全性を判定するための「チャレンジデータ」をアーカイブに送信し、アーカイブが受信したフィンガープリントを使用してデータの保全性を証明し、最後に、クライアントが「チャレンジデータ」への応答として返されたアーカイブからの出力に基づいてデータの保全性を検証する、証明可能データ保全性（ＰＤＩ）検証方法を提供する。
【解決手段】最初にデータのフィンガープリントがクライアントで生成され、そのフィンガープリントがデータと共にアーカイブに送信され、続いて、必要が生じたときにクライアントがデータの保全性を判定するための「チャレンジデータ」をアーカイブに送信し、アーカイブが受信したフィンガープリントを使用してデータの保全性を証明し、最後に、クライアントが「チャレンジデータ」への応答として返されたアーカイブからの出力に基づいてデータの保全性を検証する、証明可能データ保全性（ＰＤＩ）検証方法を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージネットワークのセキュリティ分野に関し、特に、証明可能データの保全性（ＰＤＩ）検証方法、装置、およびシステムに関する。
【背景技術】
【０００２】
インターネットの世界では、これまでローカルストレージで行っていたデータの保管を、世界規模の固定ストレージサービスに外注する動きが急速に高まっている。Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ（Ａｍａｚｏｎ Ｓ３）（非特許文献１：Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ （Ａｍａｚｏｎ Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３）は、インターネット上のこうしたストレージシステムの１つである。Ａｍａｚｏｎ Ｓ３は、データの格納と取り出しに利用できるウェブサービスインターフェースを提供する。Ａｍａｚｏｎ Ｓ３は世界規模でビジネスクラスのサービスでありながら、その料金は非常に安価であり、利用料は記憶容量１ＧＢ当たり月額０．１５米ドル、全データの転送入力料は１ＧＢ当たり０．１０米ドル、データの転送出力料は最初の１０ ＴＢまで月額０．１８米ドルである。無料の世界規模ストレージサービスを希望する企業向けにも、いくつかのサービスが提供されている。ＭｅｄｉａＭａｘ（非特許文献２：ＭｅｄｉａＭａｘ Ｆｒｅｅ Ｏｎｌｉｎｅ Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ）が２５ ＧＢの無料オンラインストレージを提供しており、Ｇｍａｉｌ Ｆｉｌｅ Ｓｙｓｔｅｍ（非特許文献３：Ｇｍａｉｌ Ｄｒｉｖｅ Ｓｈｅｌｌ Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ）プロジェクトではフリーＧｍａｉｌアカウントが１つの連続した無料ネットワークストレージ領域に変換された。
【０００３】
これらの公的な記憶領域サービスを利用すれば、クライアントはローカルな記憶サブシステムを持たずに、インターネット上でいつでも、どこからでもデータを取り出すことが可能になる。この大きな魅力によって産業界での利用が進み、今ではストレージのアウトソーシングが必然的な流れとなっている。
【０００４】
ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧはこの動向を受けて標準化を取り組み、その結果として、ＲＦＣ ４８１０“Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ”（長期アーカイブサービス要件）がリリースされた（非特許文献４：ＲＦＣ ４８１０，Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ）。ＲＦＣ ４８１０は、長期間のデータ保管を目的とする長期アーカイブサービスに関する要件を定めている。長期アーカイブサービスの主な目的は、データの存在否認の防止、データ保全性、およびデータオリジンをサポートすることである。ＲＦＣ ４８１０で述べられているように、長期アーカイブサービスは、データを受け入れた時からデータの保管期間の終了時まで、データの保全性を実証する証拠を提供できなければならない。
【０００５】
クライアントストレージのデータの保管をアーカイブサービスに委託する場合は、データの送信とデータの取り込みという２つのステップが必要となる。データ保全性の検証を目的とする単純な解決策では、データはアーカイブから取り出される。しかし、リモートアーカイブからクライアント検証器までを高帯域で接続することは現時点では実用的ではなく、近い将来にも同様である。特にモバイルクライアントでは、快適な高帯域接続を実現することは困難である。さらに、ＲＦＣ ４８１０にもあるように、サードパーティ検証器がユーザデータの保全性を検査するケースもある。この場合は、ユーザデータのプライバシ侵害を防止するために、サードパーティ検証器がユーザデータにアクセスできないようにする必要がある。従来技術では、アーカイブから取り出さずにデータの保全性を検証するための方策として、図１に示す３つのステップから成る動作モデルが採用されている。説明の一般性を損なわず、かつ表記上の煩雑化を避けるため、以下では、クライアント（すなわち、データ所有者）がユーザのデータ保全性の検証器であるケースを例にとって説明する。しかし、前述したように、実際の検証器はデータ所有者以外のサードパーティのこともある。
【０００６】
ステップ０において、クライアントによってデータのデジタルフィンガープリントが生成され、データと共にアーカイブに送信される。アーカイブには、データそのものに加えて、データのフィンガープリントも格納する必要がある。ステップ１において、クライアントがアーカイブに、データ保全性に関するチャレンジデータを送信する。アーカイブは、データのコンテンツ、データのフィンガープリント、クライアントのチャレンジデータのすべてを利用して、データ保全性証明を計算する。計算結果はクライアントに送り返され、ステップ２の検証に利用される。ステップ１とステップ２は、データの保管期間が終了するまで複数回にわたって反復することができる。
【０００７】
上記の動作モデルを使用する場合に、証明可能データ保全性問題の技術的解決策において考慮すべき主な要因を以下に示す。
（Ｉ） クライアントがデータのフィンガープリントを生成する際の所要時間
（ＩＩ） データのフィンガープリントが消費するアーカイブ記憶領域のサイズ
（ＩＩＩ） 検証器がアーカイブに送信するチャレンジデータのサイズ
（ＩＶ） アーカイブがデータ保全性証明を計算する際の所要時間
（Ｖ） アーカイブが検証器に送信するデータ保全性証明のサイズ
（ＶＩ） 検証器がデータ保全性証明を検査する際の所要時間
【０００８】
データ保全性問題に一見対処しているように見える解決策はある。この解決策では、データ所有者がまずデータを複数の断片に分割し、各断片について、メッセージ認証コード（ＭＡＣ）を事前計算する。そして、検証器（データ所有者かサードパーティかを問わない）がデータ保全性証明を必要とするときには、アーカイブサービスから無作為に選択されたいくつかの断片を取り出し、各断片のＭＡＣを再計算して比較する。
【０００９】
Ｄｅｓｗａｒｔｅ ｅｔ ａｌ．（非特許文献５：Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ ｉｎｔｅｇｒｉｔｙ ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ Ｐｒｏｃ．ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｉｎｔｅｒｎａｌ ｃｏｎｔｒｏｌ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ（ＩＩＣＩＳ’０３），２００３）とＦｉｌｈｏ ｅｔ ａｌ．（非特許文献６：Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｎｄ Ｕｎｃｈｅａｔａｂｌｅ Ｄａｔａ Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ）では、ＲＳＡベースのハッシュ関数を使用して、アーカイブが格納するファイルの正確性を検証する方法が提案されている。
【００１０】
最も新しい例では、Ａｔｅｎｉｅｓｅ ｅｔ ａｌ．（参考文献７：Ｇ．Ａｔｅｎｉｅｓｅ，Ｒ．Ｂｕｒｎｓ，Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｈｅｒｒｉｎｇ，Ｌ．Ｋｉｓｓｎｅｒ，Ｚ．Ｐｅｔｅｒｓｏｎ，Ｄ．Ｓｏｎｇ，Ｐｒｏｖａｂｌｅ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｔ Ｕｎｔｒｕｓｔｅｄ Ｓｔｏｒｅｓ（信頼されない記憶装置における証明可能データの保有）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２０２．ｐｄｆ）において、ＲＳＡベースの証明可能データ保有スキームとして、Ｓ−ＰＤＰスキーム（Ｓは「サンプリング」の略）が提案されている。この提案における「サンプリング」とは、クライアントがデータの一部を無作為に選択し、アーカイブに対して、この無作為に選択されたデータが健全な状態にある（すなわち、選択されたデータのデータ保全性が保たれている）という証拠を示すよう要求することである。Ｓ−ＰＤＰスキームは、ファイル全体のべき乗を必要とせず、通信の複雑性が一定であるため、従来技術の中で最も効率的である。
【００１１】
単純な解決策の短所は、通信の複雑性がクエリー対象のデータサイズに線形に比例することである。さらに、サードパーティ検証器の場合には、データ所有者のプライバシ侵害防止の観点から、ユーザデータを検証器に送ることは禁じられる。アーカイブサービスからデータを取り出さないようにするための方策としては、複数の秘密鍵を選択し、データに対して複数キーのハッシュＭＡＣを事前に計算することで、単純な解決策を改良するという方法がある。これにより、検証器は秘密鍵をその都度アーカイブサービスに開示し、新たなキーを付加したハッシュＭＡＣを要求して比較することが可能になる。しかし、この方法では、各データを検証できる回数は、事前に設定された秘密鍵の個数によって制限される。そのため、キーを使い果たした場合は、新たなＭＡＣを計算するために、アーカイブサービスからデータを取り出すことが不可避となる。
【００１２】
また、参考文献５および６の提案には、アーカイブがファイル全体をべき乗しなければならないという短所がある。参考として２０４８ビットのＲＳＡ係数を例にとると、１つの指数を完全にべき乗するには、Ｉｎｔｅｌ Ｃｏｒｅ Ｄｕｏ ２．１６ＧＨｚプロセッサ上で６１．３２５ミリ秒を要する。そのため、べき乗の所要時間は１メガバイト当たり２５１．３秒となり、６４ＭＢのファイルの保全性をテストする場合には、アーカイブがクライアントにデータ保全性証明を送信できるまでに１６０８３．８秒もかかってしまうことになる。
【００１３】
Ｓ−ＰＤＰスキームは、その設計目標（サンプリング）がデータ所有者には無意味な場合があるという問題を抱える。Ｓ−ＰＤＰスキームは、サンプリングによって、高い検出確率において遭遇されるファイルブロックの破壊の問題に対処する。例えば、参考文献７では、ファイルブロックの破壊が１％の場合に９９％の検出確率を達成する方法が説明されている。しかし、１ビットのエラーも許容できないファイルタイプは多い。例えば、符号復号器の構成パラメータが格納されるメディアファイルの先頭部分が失われると、処理が困難になる。また、暗号化されたファイルに埋め込まれた（公開鍵で暗号化された）対称暗号キーが壊れると、誰も普通テキストを回復できない無意味な暗号文となってしまう。概してデータ所有者は１００％のデータ安全性を要求し、どんな理由があろうとも妥協は許容しない。Ｓ−ＰＤＰスキームにはもう一つ、サードパーティ検証（いわゆる、「公的検証可能性」）システムで採用するには、あまりにも効率が低すぎるという問題もある。Ｓ−ＰＤＰスキームを使用した公的検証を可能とするためには、１つのファイルブロックをＲＳＡ公開鍵ｅよりも小さくする必要がある。例えば、２０４８ビットのＲＳＡモジュールの場合、公開鍵ｅは１０２４ビット程度でしかない。そのため、公的検証が可能なＳ−ＰＤＰスキームによる解決策では、１つのファイルを複数の１０２４ビットファイルブロックに論理的に分割しなければならない。その結果生じるファイルブロックは膨大な数に上り、その一つひとつにタグを生成する必要がある。これにより、タグのサイズはファイルそのものの２倍となり、クライアントがファイルにタグ付けするための時間を考慮すると、とうてい実用に資するものとはいえない。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
従来技術における上記の問題点を解決するため、本発明は、最初にデータのフィンガープリントがクライアントで生成され、そのフィンガープリントがデータと共にアーカイブに送信され、続いて、必要が生じたときにクライアントまたはサードパーティ検証器がデータの保全性を判定するための「チャレンジデータ」をアーカイブに送信し、アーカイブが受信したフィンガープリントを使用してデータの保全性を証明し、最後に、クライアントが「チャレンジデータ」への応答として返されたアーカイブからの出力に基づいてデータの保全性を検証する、証明可能データ保全性（ＰＤＩ）検証方法を提案する。
【００１５】
本発明の第１の態様によれば、データへのフィンガープリント付加方法であって、データをN個のブロックMi（i=1,2,…,N）に分割するステップと、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するステップと、有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択するステップと、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するステップとを備えることを特徴とする、データへのフィンガープリント付加方法が提供される。
【００１６】
nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であるのが望ましい。
【００１７】
nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するのが望ましい。
【００１８】
k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成されるのが望ましい。
【数１】
ここで、zMはデータの識別子である。
【００１９】
k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値であるのがさらに望ましい。
【００２０】
k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成されるのが望ましい。
【数２】
【００２１】
k番目のスーパーブロックのロケータWkは、少なくともｋと、データの識別子zMとを入力とするハッシュ値であるのがさらに望ましい。
【００２２】
本発明の第２の態様によれば、本発明の第１の態様によるデータへのフィンガープリント付加方法によってフィンガープリントが付加されたデータのデータ保全性証明方法であって、少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信するステップと、Φ個のボックスを構築するステップと、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当てるステップと、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するステップと、第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成するステップと、変換済みスーパーブロックの知識証明を生成するステップとを備えることを特徴とする、データ保全性証明方法が提供される。
【００２３】
変換済みスーパーブロックの知識証明は、変換済みスーパーブロック自体であるのが望ましい。
【００２４】
変換済みスーパーブロックの知識証明は、公開鍵と変換済みスーパーブロックとに基づいて生成されるのが望ましい。
【００２５】
変換済みスーパーブロックの知識証明は、以下の式で表されるのがさらに望ましい。
【数３】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックである。
【００２６】
あるいは、変換済みスーパーブロックの知識証明Hは、以下の式でも表される。
【数４】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックであり、prf5(・)は疑似ランダム関数を表す。
【００２７】
チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対、(k3,Λ)をさらに備えるのが望ましい。
【００２８】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ボックス構築から知識証明生成までのステップがψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成される。
【００２９】
Φの数は2φと等しいのがさらに望ましい。ここで、φ=[l/ψ]+1であり、lはこの方法のセキュリティレベルを決定するセキュリティレベル因数である。
【００３０】
第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されるのが望ましい。
【００３１】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００３２】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００３３】
データ保全性証明方法は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信するステップをさらに備えるのが望ましい。
【００３４】
本発明の第３の態様によれば、本発明の第２の態様によるデータ保全性証明方法に関連する方法として、本発明の第１の態様によるデータへのフィンガープリント付加方法によってフィンガープリントが付加されたデータのデータ保全性検証方法であって、第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するステップと、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信するステップと、Φ個のボックスを構築するステップと、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当てるステップと、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するステップと、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換して、変換済みロケータを生成するステップと、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成するステップと、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較するステップと、比較結果が一致の場合に、データのデータ保全性を検証するステップとを備えることを特徴とする、データ保全性検証方法が提供される。
【００３５】
検証対象の変換済みスーパーブロックの知識証明は、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成されるのが望ましい。
【００３６】
検証対象の変換済みスーパーブロックの知識証明は、第１および第２の秘密鍵x、vにも基づいて生成されるのがさらに望ましい。
【００３７】
検証対象の変換済みスーパーブロックの知識証明は、以下の式で表されるのがさらに望ましい。
prf5=((T1/x・W)v)，
ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkと、データの識別子zMとを入力とするハッシュ値である。
【００３８】
あるいは、検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される。
prf5=((Tx+zM・W)v)，
ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。
【００３９】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成されるのがさらに望ましい。
e(T,Yv,g2vzM)・e(W,
g2v)
ここで、Yj=Yv、g2v=g2v、Y= g2v∈G2である。G2=<g2>は、G1=<g1>に加えてもう１つのグループG=<g>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。
検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される。
e(H,g2)=e(T,Yv・g2vzM)・e(W,g2v)
ここで、Hは変換済みスーパーブロックの知識証明である。
【００４０】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成されるのがさらに望ましい。
e(T,Yv)・e(W,g2v)
ここで、Yv=g2v/x、g2v=g2v、Y=g2v∈G2である。G2=<g2>は、G=<g>に加えてもう１つのグループG1=<g1>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkとデータの識別子zMを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される。
e(H,g2)=e(T,Yv)・e(W,g2v)
ここで、Hは変換済みスーパーブロックの知識証明である。
【００４１】
チャレンジデータは、全n個のロケータの代わりに、どのΛ個のロケータをデータ保全性検証のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００４２】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ボックス構築から知識証明生成と検証対象知識証明との比較までのステップがψ回反復され、すべての比較結果が一致の場合にのみ、データのデータ保全性が検証される。
【００４３】
第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されるのが望ましい。
【００４４】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００４５】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００４６】
本発明の第４の態様によれば、データへのフィンガープリント付加装置であって、データをN個のブロックMi（i=1,2,…,N）に分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段と、有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するフィンガープリント付加手段とを備えることを特徴とする、データへのフィンガープリント付加装置が提供される。
【００４７】
nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であるのが望ましい。
【００４８】
nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するのが望ましい。
【００４９】
本発明の第５の態様によれば、データ保全性証明装置であって、少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信する受信手段と、Φ個のボックスを構築し、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段と、第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段と、変換済みスーパーブロックの知識証明を生成する知識証明生成手段とを備えることを特徴とする、データ保全性証明装置が提供される。
【００５０】
知識証明生成手段は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成するのが望ましい。
【００５１】
知識証明生成手段は、変換済みスーパーブロックの知識証明を、公開鍵と変換済みスーパーブロックに基づいて生成するのが望ましい。
【００５２】
チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００５３】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、パッケージ化手段と、変換手段と、知識証明生成手段の動作がψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成される。
【００５４】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００５５】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００５６】
データ保全性証明装置は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段をさらに備えるのが望ましい。
【００５７】
本発明の第６の態様によれば、データ保全性検証装置であって、第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段と、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段と、Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段と、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段と、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器と、比較結果が一致の場合に、データ保全性を検証する検証装置とを備えることを特徴とする、データ保全性検証装置が提供される。
【００５８】
検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成するのが望ましい。
【００５９】
検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vにも基づいて生成するのがさらに望ましい。
【００６０】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータのうちどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００６１】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ロケータパッケージ化手段と、検証対象知識証明生成手段と、比較器の動作がψ回反復され、すべての比較結果が一致の場合にのみ、検証手段がデータ保全性を検証する。
【００６２】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００６３】
チャレンジデータ生成・送信手段は、デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定するのがさらに望ましい。
【００６４】
本発明の第７の態様によれば、データ保全性検証システムであって、本発明の第５の態様によるデータ保全性証明装置と、本発明の第６の態様によるデータ保全性検証装置とを備えることを特徴とするデータ保全性検証システムが提供される。
【００６５】
データ保全性検証システムは、本発明の第４の態様によるデータへのフィンガープリント付加装置をさらに備えるのが望ましい。
【００６６】
データへのフィンガープリント付加装置は、データ保全性検証装置としても使用されるのがさらに望ましい。
【００６７】
本発明のＰＤＩスキームにより、圧倒的に高い確率（例えば、1-2-64）でデータのデータ保全性を確保することができる。従来技術は（１）データ保全性がビット単位で保証される、（２）クライアントがアーカイブに送信するチャレンジデータのサイズが一定である、（３）アーカイブがクライアントに送信するデータ保全性証明のサイズが一定である、という効果を実現するのに対し、本発明のＰＤＩスキームは以下の４つの主要な利点を有する。
（Ｉ） クライアントがデータのフィンガープリントを生成する速度が最速である。
（ＩＩ） アーカイブがクライアントのチャレンジデータへの応答を生成する速度が最速である。
（ＩＩＩ） クライアントがアーカイブの応答を検証する速度が最速である。
（ＩＶ） 検証器はサードパーティ検証器であってもよく、上記３つの利点（Ｉ）〜（ＩＩＩ）のすべてが同様に実現される。しかも、フィンガープリントのサイズが最小である。
【００６８】
以下では、具体例として６４ＭＢのデータファイルについて説明する。セキュリティ強度は２０４８ビットのＲＳＡ署名相当に設定され、l=64である。クライアントは速度２．１６ＧＨｚのＩｎｔｅｌ Ｃｏｒｅ Ｄｕｏプロセッサ、アーカイブは速度２．６６ＧＨｚのＩｎｔｅｌ Ｑｘ６７００ Ｃｏｒｅ２ Ｑｕａｄプロセッサとすると、ＰＤＩスキームにおいては、クライアントがファイルへのフィンガープリントの付加に要する時間は１２．７秒間、アーカイブが変換済みフィンガープリントと変換済みスーパーブロックの知識証明の生成に要する時間は１．４秒間、クライアントが知識証明の検証に要する時間は約０．４秒間である。これらの時間値は、従来技術のＲＳＡベーススキームが達成可能な理論的下限よりもさらに低い。
【先行技術文献】
【非特許文献】
【００６９】
【非特許文献１】Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ （Ａｍａｚｏｎ Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３
【非特許文献２】ＭｅｄｉａＭａｘ Ｆｒｅｅ Ｏｎｌｉｎｅ Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ
【非特許文献３】Ｇｍａｉｌ Ｄｒｉｖｅ Ｓｈｅｌｌ Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ
【非特許文献４】ＲＦＣ ４８１０，Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ
【非特許文献５】Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ ｉｎｔｅｇｒｉｔｙ ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ Ｐｒｏｃ．ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｉｎｔｅｒｎａｌ ｃｏｎｔｒｏｌ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ（ＩＩＣＩＳ’０３），２００３
【非特許文献６】Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｎｄ Ｕｎｃｈｅａｔａｂｌｅ Ｄａｔａ Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ
【図面の簡単な説明】
【００７０】
本発明の上記および他の目的、特徴、利点は、本発明の非限定的な実施例に関する以下の説明と添付図面とを参照することにより、さらに明らかになるであろう。
【００７１】
【図１】データ保全性証明における動作モデルを示す。
【図２】本発明によるデータ保全性証明方法（アトミック証明手順）とデータ保全性検証方法（アトミック検証手順）のフローチャートを示す。
【図３】データの論理ビューである。
【図４】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図５】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図６】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図７】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図８】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図９】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１０】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１１】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１２】データ保全性証明における他の動作モデルを示す。
【図１３】データ保全性証明におけるさらに他の動作モデルを示す。
【図１４】本発明を実装したクライアント１４００のブロック図を示す。
【図１５】本発明を実装したアーカイブ１５００のブロック図を示す。
【図１６】本発明を実装した検証器１６００のブロック図を示す。
【発明を実施するための形態】
【００７２】
次に、図面を参照しながら本発明について説明する。以下の説明では、説明の便宜上いくつかの具体的な実施例を使用しているが、これらは本発明を限定するものではなく、例示にすぎない。また、本発明の理解が多少曖昧になる可能性はあるが、従来技術の構成・構造の説明は省略する。
（原理の説明）
【００７３】
本明細書において提示する証明可能データ保全性（ＰＤＩ）スキームは、従来技術が抱えるすべての問題を克服するのみならず、どの従来技術にも勝る性能を示す。
【００７４】
ＰＤＩスキームは、基本的には、図１に示す動作モデルに従った以下の３つのステップで構成される。
【００７５】
ステップ０’：
ＰＤＩスキームでは、有限循環グループG1=<g1>が必要とされるが、このG1は楕円曲線上の有限循環グループであるのが望ましい。本発明の開示では、その全体を通して、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。クライアントは、秘密鍵xとそれに対応する公開鍵とを有する。
【００７６】
クライアントは、データファイルをN個のブロックMi、i=1,2,…,Nに分割する。nB個のブロックは、それぞれ１つのスーパーブロックとして結合される。したがって、データはn={N/nB}個のスーパーブロックに分割される。データファイルの長さがｎ個のスーパーブロックに必要な長さに満たない場合は、データファイルはゼロを使用して論理的に埋められる。
【００７７】
クライアントは、各データファイルに関して、G1、i=1,2,…,nBのnB個の要素hjを作成する。好適なケースでは、クライアントは、hi=g1riとなるようにriを選択し、riを秘匿しておく。要素hiは、クライアントの公開鍵の一部とし、データファイルから独立させるのがさらに望ましい。
【００７８】
クライアントは自身の秘密鍵と上記nB個の要素hiを利用して、すべてのスーパーブロックのフィンガープリントを生成する。例えば、i番目のスーパーブロックのフィンガープリントは
【数５】
の形式をとる。ここで、ロケータWiは、少なくともiを入力とするハッシュ値である。また、データファイルのファイル名やバージョン番号などを入力として追加することもできる。zMは、データファイルに対して選択された固有な識別子である。例えば、あるデータファイル集合には識別子zM、別のデータファイル集合には別の識別子zM、というように選択する。あるいは、フィンガープリントを
【数６】
として計算することもできる。この場合、ロケータWiはiとzMを入力とする。好適なケースでは、クライアントは、riの値と、hi=griであるという知識を有する。したがって、
【数７】
を
【数８】
に置換することにより、クライアントはriの知識を利用してフィンガープリント処理を迅速化することができる。
【００７９】
ステップ０’の結果、クライアントは、n個のスーパーブロックに対してn個のフィンガープリントを取得する。クライアントは、データファイルとnB個の要素hjと共に、すべてのフィンガープリントをアーカイブに送信する。nB個の要素hiをクライアントの公開鍵の一部とする好適なケースでは、アーカイブはこれらの要素を公開鍵ディレクトリなどから事前に取得することもできる。その場合は、これらの要素をデータファイルと共に送信する必要はない。
【００８０】
ステップ１’：
クライアントは、データの保全性を判定するための「チャレンジデータ」をアーカイブに送信する。
【００８１】
アーカイブは、クライアントから受信したチャレンジデータに基づいて、アトミック証明手順を数回（例：ψ回）実行する必要がある。
【００８２】
アーカイブは、各アトミック証明手順において、まずΦ=2φ個のボックスを構築し、論理的かつ無作為にn個のフィンガープリントをこれらのボックスに割り当てる。個数Φと無作為性は、クライアントから受信した「チャレンジデータ」によって決まる。１つのフィンガープリントの配置先は、必ず１つのボックスに限定しなければならない。１つのフィンガープリントを１つのスーパーブロックに対応させることを念頭に全n個のフィンガープリントをボックスに配置すると、その結果として、各ボックスには１つの「割り当て済みスーパーブロック」と、そのボックスに割り当てられたフィンガープリントに基づいて生成された「割り当て済みスーパーブロック」の「割り当て済みフィンガープリント」とが存在することになる。例えば、λ番目のボックスに、η番目およびω番目のスーパーブロックに関連する２つのフィンガープリントのみが配置されるケースであれば、このボックスの「割り当て済みスーパーブロック」は
【数９】
を含み、「割り当て済みスーパーブロック」の「割り当て済みフィンガープリント」は
【数１０】
となる。
【００８３】
次に、アーカイブは、すべてのボックスの「割り当て済みスーパーブロック」と「割り当て済みフィンガープリント」に別の無作為性を適用することにより、１つの「変換済みスーパーブロック」と、その「変換済みスーパーブロック」の１つの「変換済みフィンガープリント」を生成する。この無作為性もまた、クライアントから受信した「チャレンジデータ」によって決定される。上記の例についてさらに説明すれば、「変換済みスーパーブロック」は
【数１１】
を含み、「変換済みスーパーブロック」の「変換済みフィンガープリント」は
【数１２】
（aλはクライアントの「チャレンジデータ」によって決定された乱数）となる。
【００８４】
最後に、アーカイブは、「変換済みスーパーブロックの知識証明」を生成する。これには「変換済みスーパーブロック」を直接使用することもできる。あるいは、標準的なゼロ知識証明技術（対話または非対話方式）による「変換済みスーパーブロック」のコンテンツの知識を使用してもよい。また、クライアントの「チャレンジデータ」がHi=hiv，i=1,2,…,nBを含む場合に、クライアントがチャレンジデータ毎に異なるvを選択し、vを秘匿しておくことも可能である。好適なケースでは、Hiはクライアントの公開鍵、vはクライアントの秘密鍵の一部である。アーカイブは、Hiを利用して、「変換済みスーパーブロックの知識証明」を
【数１３】
として計算する。
【００８５】
アーカイブは、「変換済みフィンガープリント」Tと「変換済みスーパーブロックの知識証明」Hとを、アトミック証明手順の出力としてクライアントに送信する。
【００８６】
アーカイブは、アトミック証明手順を全部でψ回反復する必要がある。ボックス数を決定する値としては、ψ=[l/ψ]+1を選択することができる。ここで、lはセキュリティレベルを決定する値であり、クライアントによって選択される。乱数aλのビット長としては、ψを選択する。アトミック手順をψ回反復すると、ＰＤＩスキームのセキュリティレベルは(n/ψ)・2-lとなる。これは、１つ以上のブロックが破壊されている場合に、アーカイブが検証器に正しい結果を返す確率は、最大
(n/ψ)・2-lであることを意味する。
【００８７】
上記の「個数Φと無作為性は、クライアントか受信したチャレンジデータによって決定される」と「aλは、クライアントのチャレンジデータによって決定される乱数である」の部分については、代替の実施例がある。例えば、φ=nを選択し、n個のフィンガープリントをn個のボックスに均等に配置し（すなわち、１つのボックスに必ず１つのフィンガープリントが含まれるようにする）、aλのビット長としてlを選択したとすると、この場合には、ψ=1を選択すると、n・2-lのセキュリティレベルが実現される。
【００８８】
ステップ２’：
クライアントは、アーカイブから、ψ回のアトミック証明手順の全出力を受信する。
【００８９】
クライアントは、１回のアトミック証明手順から得られた「変換済みスーパーブロック」の「変換済みフィンガープリント」と「変換済みスーパーブロックの知識証明」の各々を対象に、アトミック検証手順を実行する。
【００９０】
クライアントは、各アトミック検証手順において、まずΦ個のボックスを構築し、論理的かつ無作為にロケータWiをこれらのボックスに割り当てる。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブがフィンガープリントを割り当てる際に使用した無作為性と同一である。１つのロケータは、必ず１つのボックスに配置しなければならない。全n個のロケータがボックスに配置された後、各ボックス内には、ボックスに割り当てられたロケータに基づいて生成された「割り当て済みロケータ」が存在する。例えば、λ番目のボックスに２つのロケータWηおよびWωのみが配置されるケースであれば、このボックスの「割り当て済みロケータ」は
【数１４】
となる。
【００９１】
次に、クライアントは、別の無作為性をすべてのボックスの「割り当て済みロケータ」に適用することにより、１つの「変換済みロケータ」を生成する。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブが「変換済みフィンガープリント」を計算する際に使用した無作為性と同一である。「変換済みロケータ」は
【数１５】
となる。ここで、aλはクライアントの「チャレンジデータ」によって決定された乱数である。
【００９２】
最後に、アーカイブが「変換済みスーパーブロックの知識証明」を直接「変換済みスーパーブロック」として生成する場合には、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をH’=(Tx+zM/W)として計算し、
【数１６】
と比較する。アトミック検証手順は、一致した場合にのみ、「成功」を出力する。あるいは、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をH’=(Tx+zM/W)vとして計算し、アーカイブから受信した値Hと比較することもできる。アトミック検証手順は、H=H’の場合にのみ、「成功」を出力する。また、フィンガープリントが
【数１７】
として計算される場合には、「検証対象の変換済みスーパーブロックの知識証明」は(T1/x/W)vとして計算される。
【００９３】
クライアントは、アトミック検証手順が「成功」を出力した場合にのみ、アーカイブ側でデータ保全性が保たれていると判定する。アーカイブ側で１つ以上のブロックが破壊されているときにクライアントが誤判定する確率は、最大で2-lである。
（詳細な説明）
【００９４】
次に、図面を参照しながら本発明についてさらに詳細に説明する。
【００９５】
本発明の開示では、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。
【００９６】
G1=<g1>とG2=<g2>を２つの有限循環グループとし、G=<g>を追加のグループとする。|G1|=|G2|=|G|=p（pは大きな素数）である。双線形マップe: G1×G2→gは、以下の特性を有する関数である。
■ 双線形：すべてのh1∈G1，h2∈G2、すべてのa.b∈Zpにおいて、e(h1a,
h2b)= e(h1, h2)abである。
■ 非縮退：∃h1∈G1，∃h2∈G2は、e(h1, h2)≠I（Iはgの識別子）の関係を有する。
■ 計算可能：ｅを計算するための効率的なアルゴリズムが存在する。
【００９７】
入力セキュリティパラメータ1kに基づいて上記の双線形マップの設定を出力し、それを(p,G1,G2,g,g1,g2)←setup(1k)として記述するセットアップアルゴリズムsetup(・)が存在すると仮定する。
【００９８】
G1、G2、gは同一の素数位数pを有するので、双線形の特性と非縮退の特性から、e(g1,g2)=gであることは容易に理解できる。．
【００９９】
(p,G1,G2,g,g1,g2)←setup(1k)とし、５つの疑似ランダム関数prf1:{0,1}*←Zp,、prf2:{0,1}*←G1、prf3(φ):{0,1}*←Z2φ、prf4(φ):{0,1}*←Z2φ、およびprf5:G1→{0,1}160をシステムパラメータとする。
【０１００】
クライアントによるデータへのフィンガープリント付加
クライアントは、秘密鍵(x,v)←Zp2と公開鍵Y=g2x∈G2を有する。クライアントは、認証局からYの証明書を取得するのが望ましい。あるいは、クライアントの秘密鍵vを、例えばv=prf1(x,”second
private key”)として計算することもできる。
【０１０１】
さらに、クライアントは、(hi=g1prf1(i,x),Hi=hiv)∈G12，i=1,2,…,nBを計算して自身の公開鍵とする。
【０１０２】
データMを、各ビット長がlM（lM<logpが必須）のN個のブロックMi（i=1,2,…,N）に分割する。Mの修飾ファイル名をFNMとする。
【０１０３】
図３に、データMを論理的に分割してn個のスーパーブロックにする方法を示す。スーパーブロック数は、n=[N/nB]で表す。データMの長さがN・lMまたはn・(nB・lM)に満たない場合は、ゼロを使用して論理的に埋められる。
【０１０４】
クライアントは、以下を実行してデータにフィンガープリントを付加する。
ａ） クライアントは、識別子zM←Zpを選択し、ロケータWi=prf2(i,zM,FNM)∈G1、
【数１８】
を計算する。i番目のスーパーブロックのフィンガープリントを、Tiと命名する。
ｂ） 秘密鍵xを使用して(FNM,M,zM,{Ti})に署名して、署名Sを生成する。
ｃ） FNMに対してzMを保存する。
ｄ） FNM、M、zM∈Zp、{Ti}∈G1n、およびSをアーカイブに送信する。
ｅ） アーカイブは、FNM、M、zM、{Ti}、およびSを受信後、クライアントの公開鍵を使用して、Sが(FNM,M,zM,{Ti})の有効な署名であるか検証する。
アーカイブによるデータ保全性の証明
【０１０５】
アーカイブが（最大2-lの確率におけるエラー以外には）ゼロビットエラー率でFNMのコンテンツを保持しているか確認するため、クライアントがアーカイブにチャレンジデータを送り、アーカイブはそれに対して以下を応答する。
ｉ） クライアントは、反復因数
【数１９】
を選択する。
ｉｉ） クライアントは、(k1,k2)←Zp2を選択し、FNM，chal=(l,ψ, k1,k2)をアーカイブに送信する。
ｉｉｉ） アーカイブは、FNMとchal=(l,ψ, k1,k2)を受信後、まずφ=[l/ψ]+1を計算し、変換済みフィンガープリントTk=O∈G1，k=1,2,…,ψ（OはG1の識別子）を初期化する。その後、以下のアトミック証明手順を独自に全ψ回にわたって反復する。
ｉｉｉ−ａ． 割り当て済みフィンガープリント
【数２０】
、割り当て済みスーパーブロックevj=0、および変換済みスーパーブロックEj=0、v=0,1,…,Φ-1=2φ-1,j=1,2,…,nBを初期化する。
ｉｉｉ−ｂ． i=1,2,…,nの各々について、以下の計算を行う。
ｂ−ｉ． σ=prf3(I,k,k1)
ｂ−ｉｉ．
【数２１】
これはTiをσ番目のボックスの割り当て済みフィンガープリントに付加することを意味する。
ｂ−ｉｉｉ． j=1,2,…,nBの各々について、eσj+=M(i-1)*nB+jmodpを計算する。これはM(i-1)*nB+jをσ番目のボックスの割り当て済みスーパーブロックに付加することを意味する。
ｉｉｉ−ｃ． v=1,2,…,Φの各々について、以下の計算を行う。
ｃ−ｉ． av=prf4(v,k,k2)
ｃ−ｉｉ．
【数２２】
ｃ−ｉｉｉ． J=1,2,…,nBの各々について、Ej+=av・evjmodpを計算する。
ｉｉｉ−ｄ．
【数２３】
を計算し、変換済みスーパーブロックの知識証明とする。
ｉｖ） 保全性証明(Tk,Hk)，k=1,2,…,ψをクライアントに送信する。
【０１０６】
上記に代わる方法として、クライアントがk1←Zpを選択し、k2を例えばk2=prf1(k1,”second
randomness defining key”)として計算することもできる。そのため、k2の送信は省略することができる。
【０１０７】
クライアントによるデータ保全性の検証
クライアントは、(Tk,Hk)、k=1,2,…,ψの受信後、以下のアトミック検証手順を独自に全ψ回にわたって反復する。
Ｉ） 変換済みロケータWk=I∈G1、割り当て済みロケータWv=I∈G1、v=0,1,…,Φ-1=2φ-1を初期化する。
ＩＩ） i=1,2,…,nの各々について、σ=prf3(i,k,k1)およびWσ*=prf2(I,FNM)を計算する。
ＩＩＩ） v=1,2,…,Φの各々について、av=prf4(v,k,k2)およびWk*=-Wv-avを計算する。
ＩＶ） 計算によりHk=prf5((Tkx+zM・Wk)v)であるか検証し、この合同式が成り立つ場合にのみＴＲＵＥを出力する。
全てのアトミック検証手順でＴＲＵＥが出力された場合にのみ、クライアントはデータ保全性証明が正しいと判断する。
（具体例）
【０１０８】
図４〜７は、６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証結果を示す。当該技術分野に精通する当業者は、上記の説明の各ステップと図４〜７を参照することにより、本発明をきわめて明確に理解できるであろう。
（実際の実験）
【０１０９】
図８〜１１は、２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。図９〜１１には、参考文献７の結果も示す。これにより、本発明では参考文献７に比較して計算時間コストが大幅に改善されていることが分かる。
（他の実施例）
（代替スキーム１：）
【０１１０】
ＰＤＩ−２スキームは、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄと「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。これは、公的検証可能性をサポートするスキームである。
【０１１１】
クライアントは、Yv=Yvとg2v=
g2vを計算して自身の公開鍵とする。
【０１１２】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄ．
【数２４】
を計算し、変換済みスーパーブロックの知識証明とする。
【０１１３】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ’） 計算によりe(Hk,g2)=e(Tk,Yv,g2vzM)・e(Wk,
g2v)であることを検証する。
【０１１４】
ＰＤＩ−２スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム１．１：）
【０１１５】
ＰＤＩ−２スキームは、ＰＤＩ−２の「クライアントによるデータ保全性の検証」を一部変更したものである。
【０１１６】
「クライアントによるデータ保全性の検証」のステップＩＶ’）への変更：
ＩＶ−ｅ）k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数２５】
であることを検証する。
【０１１７】
加速化ＰＤＩ−２スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム２：）
【０１１８】
ＰＤＩ−３スキームは、「クライアントによるデータへのフィンガープリント付加」のステップａ）と「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。
【０１１９】
「クライアントによるデータへのフィンガープリント付加」のステップａ）への変更：
ａａ） クライアントは、識別子ZM←Zpを選択し、
【数２６】
を計算する。
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ”） 計算によりHk=prf5((Tk1/x・Wk)v)であることを検証する。
（代替スキーム３：）
【０１２０】
ＰＤＩ−４スキームは、上記の代替スキーム２に対し、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．と「クライアントによるデータ保全性の検証」のステップＩＶ）に一部変更を加えたものである。これもまた、公的検証可能性をサポートするスキームである。
【０１２１】
クライアントは、Yv=g2v/xとg2v=g2vを計算して自身の公開鍵とする。
【０１２２】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄｄ．
【数２７】
を計算し、変換済みスーパーブロックの知識証明とする。
【０１２３】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ’’’） 計算によりe(Hk,g2)=e(Tk,Yv)・e(Wk,g2v)であることを検証する。
【０１２４】
ＰＤＩ−４スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム３．１：）
【０１２５】
加速化ＰＤＩ−４は、ＰＤＩ−４の「クライアントによるデータ保全性の検証」を一部変更したものである。
【０１２６】
「クライアントによるデータ保全性の検証」のステップＩＶ’’’）への変更：
ＩＶ−ｆ）k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数２８】
であることを検証する。
【０１２７】
加速化ＰＤＩ−４スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム４：）
【０１２８】
上記のすべてのスキームに対し、システムパラメータ、「クライアントによるデータへのフィンガープリント付加」のステップ、および「クライアントによるデータ保全性の検証」のステップに一部変更を加えることで、サンプリングをサポートするスキームが得られる。
【０１２９】
サンプリングをサポートするには、システムパラメータprf6:{0,1}*→{1,2,…,n}を追加する必要がある。チャレンジデータchal=(l,ψ,k1,
k2)には、キーk3←Zpと正の数値Λが追加される。
【０１３０】
次に、「クライアントによるデータへのフィンガープリント付加」と「クライアントによるデータ保全性の検証」の全ステップにおいて、全てのi=1,2,…,nがi=prf6(k3,1),
prf6(k3,2),…, prf6(k3,Λ)に置換される。これにより、i=prf6(k3,1),
prf6(k3,2),…, prf6(k3,Λ)によって選択されたΛ個のスーパーブロックのみが処理対象となるため、サンプリングされたスーパーブロックデータのみのデータ保全性が検証される。
【０１３１】
したがって、代替スキーム４においては、アーカイブはすべてのスーパーブロックを使用しなくてもデータ保全性証明を生成することができる。アーカイブは、クライアントのチャレンジデータの情報をもとに、証明の生成において、どのスーパーブロックをいくつ選択すべきかを決定する。
（代替動作モデル：）
【０１３２】
非特許文献４（ＲＦＣ ４８１０）で提案されるタイムスタンプ局（ＴＳＡ）を導入することにより、図１２に示すように、チャレンジキー(k1,k2)←Zp2をＴＳＡから取得したデジタル署名付きタイムスタンプに置換することが可能になる。ここで、タイムスタンプをＴとすると、標準的なハッシュアルゴリズムＳＨＡ−１を使用して、k1＝ＳＨＡ−１（Ｔ，“１”）とk2＝ＳＨＡ−１（Ｔ，“２”）を得ることができる。こうした置換を行った場合のクライアントのチャレンジデータは、データがＴＳＡによるタイムスタンプ発行時間まで正常に保持されているかどうかの検証を求める内容となる。この事前計算により、アーカイブの応答(Tk,Hk)の利用が必須となるのはアトミック検証手順の最後のステップのみとなり、アーカイブとクライアントのいずれにおいても大幅に処理が簡素化される。
【０１３３】
さらに、図１３に示すように、検証器がサードパーティ検証器の場合には、ＴＳＡのタイムスタンプからk1とk2を推論することもできる。また、サンプリングが有効な場合には、k3はＴＳＡのタイムスタンプから、例えばk3＝ＳＨＡ−１（Ｔ，“３”）として推論することができる。
（ハードウェア実装：）
【０１３４】
当業者には明らかなように、本発明はハードウェア構造によって実装することもできる。以下では、限定ではなく参考として、いくつかの例について説明する。
クライアント
【０１３５】
図１４に、本発明を実装したクライアント１４００のブロック図を示す。この実装では、クライアント１４００はデータへのフィンガープリント付加装置として使用される。
【０１３６】
図１４に示すように、クライアント１４００は、データをN個のブロックMi，i=1,2,…,Nに分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段１４１０と、有限循環グループG1=<g1>からnB個の要素hj，j=1,2,…,nBを選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k=1,2,…,nであるk番目のスーパーブロックのフィンガープリントTkを生成するフィンガープリント付加手段１４２０とを含む。クライアント１４００は、さらに、生成されたスーパーブロック、有限循環グループ、生成されたフィンガープリント、ロケータ、秘密鍵などの、スーパーブロック生成手段１４１０とフィンガープリント付加手段１４２０によって利用または生成される情報を格納するメモリ１４３０を含む。ただし、メモリ１４３０は、上記のように独立した手段とすることも、あるいはスーパーブロック生成手段１４１０とフィンガープリント付加手段１４２０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１３７】
同様に、nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の部分とすることができる。また、nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するものとすることができる。さらに、公開鍵と秘密鍵もメモリ１４３０に格納することができる。
アーカイブ
【０１３８】
図１５に、本発明を実装したアーカイブ１５００のブロック図を示す。この実装では、アーカイブ１５００はデータ保全性証明装置として使用される。
【０１３９】
図１５に示すように、アーカイブ１５００は、少なくとも第１のランダム性定義キーk1と第２のランダム性定義キーk2とから成るチャレンジデータを受信する受信手段１５１０と、上記チャレンジデータが決定する数であるΦ個のボックスを構築し、第１のランダム性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段１５２０と、第２のランダム性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段１５３０と、変換済みスーパーブロックの知識証明を生成する知識証明生成手段１５４０とを含む。アーカイブ１５００はさらに、受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０によって使用または生成される情報を格納するメモリ１５５０を含む。ただし、メモリ１５５０は、上記のように独立した手段とすることも、あるいは受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１４０】
知識証明生成手段１５４０は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成することも、あるいは公開鍵と変換済みスーパーブロックに基づいて生成することもできる。
【０１４１】
チャレンジデータには、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段１５２０がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることができる。
【０１４２】
チャレンジデータは、反復因数ψをさらに備えることができる。これにより、パッケージ化手段１５２０と、変換手段１５３０と、知識証明生成手段１５４０の動作がψ回反復され、各反復毎に、１つの変換済みスーパーブロックの知識証明が生成される。これは、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明と呼ばれる。
【０１４３】
チャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含めることができる。
【０１４４】
さらに、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成される。
【０１４５】
また、アーカイブ１５００は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段１５６０をさらに備える。
検証器（クライアントまたはサードパーティ検証器）
【０１４６】
図１６に、本発明を実装した検証器１６００のブロック図を示す。この実装では、検証器１６００はデータ保全性検証装置として使用される。検証器１６００はクライアント１４００自体、あるいはサードパーティ検証器のいずれでもよいことは当業者には明かであろう。クライアント１４００自体を検証器１６００とする前者のケースでは、図１４のデータにフィンガープリントを付加するためのサブシステムと、図１６の検証データ保全性を検証するためのサブシステムはクライアント１４００に備えられる。一方、サードパーティ検証器を検証器１６００とする後者のケースでは、サードパーティ検証器は図１６の構造を備えることのみが必須となり、図１４の構造は任意である。
【０１４７】
図１６に示すように、検証器１６００は、第１のランダム性定義キーk1と第２のランダム性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段１６１０と、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段１６２０と、Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段１６３０と、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段１６４０と、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器１６５０と、比較結果が一致の場合に、データ保全性を検証する検証装置１６６０とを含む。検証器１６００はさらに、チャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０によって使用または生成される情報を格納するメモリ１６７０を含む。ただし、メモリ１６７０は、上記のように独立した手段とすることも、あるいはチャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１４８】
検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成することができる。
【０１４９】
また、検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vに基づいて生成することもできる。
【０１５０】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータの代わりにどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備える。
【０１５１】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、反復因数ψをさらに備える。これにより、ロケータパッケージ化手段１６３０と、検証対象知識証明生成手段１６４０と、比較器１６５０の動作がψ回反復され、すべての比較結果が一致の場合にのみ、検証手段１６６０がデータ保全性を検証する。
【０１５２】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得した、デジタル署名付きのタイムスタンプを含めることができる。
【０１５３】
チャレンジデータ生成・送信手段１６１０は、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定する。
【０１５４】
上記の説明は本発明の好適な実施例のみを示したものであり、いかなる形であれ本発明を限定することを意図するものではない。したがって、本発明の適用範囲には、本発明の精神および原則に則ったあらゆる変更、置換、改良等も内包される。
【符号の説明】
【０１５５】
１：チャレンジデータ？
２：データ保全性証明
１’：タイムスタンプ
２’：データ保全性証明
１４１０：スーパーブロック生成手段
１４２０：フィンガープリント付加手段
１４３０：メモリ
１５１０：受信手段
１５２０：パッケージ化手段
１５３０：変換手段
１５４０：知識証明生成手段
１５６０：送信手段
１５５０：メモリ
１６１０：チャレンジデータ生成・送信手段
１６２０：受信手段
１６３０：ロケータパッケージ化手段
１６４０：検査対象知識証明生成手段
１６５０：比較器
１６６０：検証手段
１６７０：メモリ
【技術分野】
【０００１】
本発明は、ストレージネットワークのセキュリティ分野に関し、特に、証明可能データの保全性（ＰＤＩ）検証方法、装置、およびシステムに関する。
【背景技術】
【０００２】
インターネットの世界では、これまでローカルストレージで行っていたデータの保管を、世界規模の固定ストレージサービスに外注する動きが急速に高まっている。Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ（Ａｍａｚｏｎ Ｓ３）（非特許文献１：Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ （Ａｍａｚｏｎ Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３）は、インターネット上のこうしたストレージシステムの１つである。Ａｍａｚｏｎ Ｓ３は、データの格納と取り出しに利用できるウェブサービスインターフェースを提供する。Ａｍａｚｏｎ Ｓ３は世界規模でビジネスクラスのサービスでありながら、その料金は非常に安価であり、利用料は記憶容量１ＧＢ当たり月額０．１５米ドル、全データの転送入力料は１ＧＢ当たり０．１０米ドル、データの転送出力料は最初の１０ ＴＢまで月額０．１８米ドルである。無料の世界規模ストレージサービスを希望する企業向けにも、いくつかのサービスが提供されている。ＭｅｄｉａＭａｘ（非特許文献２：ＭｅｄｉａＭａｘ Ｆｒｅｅ Ｏｎｌｉｎｅ Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ）が２５ ＧＢの無料オンラインストレージを提供しており、Ｇｍａｉｌ Ｆｉｌｅ Ｓｙｓｔｅｍ（非特許文献３：Ｇｍａｉｌ Ｄｒｉｖｅ Ｓｈｅｌｌ Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ）プロジェクトではフリーＧｍａｉｌアカウントが１つの連続した無料ネットワークストレージ領域に変換された。
【０００３】
これらの公的な記憶領域サービスを利用すれば、クライアントはローカルな記憶サブシステムを持たずに、インターネット上でいつでも、どこからでもデータを取り出すことが可能になる。この大きな魅力によって産業界での利用が進み、今ではストレージのアウトソーシングが必然的な流れとなっている。
【０００４】
ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧはこの動向を受けて標準化を取り組み、その結果として、ＲＦＣ ４８１０“Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ”（長期アーカイブサービス要件）がリリースされた（非特許文献４：ＲＦＣ ４８１０，Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ）。ＲＦＣ ４８１０は、長期間のデータ保管を目的とする長期アーカイブサービスに関する要件を定めている。長期アーカイブサービスの主な目的は、データの存在否認の防止、データ保全性、およびデータオリジンをサポートすることである。ＲＦＣ ４８１０で述べられているように、長期アーカイブサービスは、データを受け入れた時からデータの保管期間の終了時まで、データの保全性を実証する証拠を提供できなければならない。
【０００５】
クライアントストレージのデータの保管をアーカイブサービスに委託する場合は、データの送信とデータの取り込みという２つのステップが必要となる。データ保全性の検証を目的とする単純な解決策では、データはアーカイブから取り出される。しかし、リモートアーカイブからクライアント検証器までを高帯域で接続することは現時点では実用的ではなく、近い将来にも同様である。特にモバイルクライアントでは、快適な高帯域接続を実現することは困難である。さらに、ＲＦＣ ４８１０にもあるように、サードパーティ検証器がユーザデータの保全性を検査するケースもある。この場合は、ユーザデータのプライバシ侵害を防止するために、サードパーティ検証器がユーザデータにアクセスできないようにする必要がある。従来技術では、アーカイブから取り出さずにデータの保全性を検証するための方策として、図１に示す３つのステップから成る動作モデルが採用されている。説明の一般性を損なわず、かつ表記上の煩雑化を避けるため、以下では、クライアント（すなわち、データ所有者）がユーザのデータ保全性の検証器であるケースを例にとって説明する。しかし、前述したように、実際の検証器はデータ所有者以外のサードパーティのこともある。
【０００６】
ステップ０において、クライアントによってデータのデジタルフィンガープリントが生成され、データと共にアーカイブに送信される。アーカイブには、データそのものに加えて、データのフィンガープリントも格納する必要がある。ステップ１において、クライアントがアーカイブに、データ保全性に関するチャレンジデータを送信する。アーカイブは、データのコンテンツ、データのフィンガープリント、クライアントのチャレンジデータのすべてを利用して、データ保全性証明を計算する。計算結果はクライアントに送り返され、ステップ２の検証に利用される。ステップ１とステップ２は、データの保管期間が終了するまで複数回にわたって反復することができる。
【０００７】
上記の動作モデルを使用する場合に、証明可能データ保全性問題の技術的解決策において考慮すべき主な要因を以下に示す。
（Ｉ） クライアントがデータのフィンガープリントを生成する際の所要時間
（ＩＩ） データのフィンガープリントが消費するアーカイブ記憶領域のサイズ
（ＩＩＩ） 検証器がアーカイブに送信するチャレンジデータのサイズ
（ＩＶ） アーカイブがデータ保全性証明を計算する際の所要時間
（Ｖ） アーカイブが検証器に送信するデータ保全性証明のサイズ
（ＶＩ） 検証器がデータ保全性証明を検査する際の所要時間
【０００８】
データ保全性問題に一見対処しているように見える解決策はある。この解決策では、データ所有者がまずデータを複数の断片に分割し、各断片について、メッセージ認証コード（ＭＡＣ）を事前計算する。そして、検証器（データ所有者かサードパーティかを問わない）がデータ保全性証明を必要とするときには、アーカイブサービスから無作為に選択されたいくつかの断片を取り出し、各断片のＭＡＣを再計算して比較する。
【０００９】
Ｄｅｓｗａｒｔｅ ｅｔ ａｌ．（非特許文献５：Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ ｉｎｔｅｇｒｉｔｙ ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ Ｐｒｏｃ．ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｉｎｔｅｒｎａｌ ｃｏｎｔｒｏｌ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ（ＩＩＣＩＳ’０３），２００３）とＦｉｌｈｏ ｅｔ ａｌ．（非特許文献６：Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｎｄ Ｕｎｃｈｅａｔａｂｌｅ Ｄａｔａ Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ）では、ＲＳＡベースのハッシュ関数を使用して、アーカイブが格納するファイルの正確性を検証する方法が提案されている。
【００１０】
最も新しい例では、Ａｔｅｎｉｅｓｅ ｅｔ ａｌ．（参考文献７：Ｇ．Ａｔｅｎｉｅｓｅ，Ｒ．Ｂｕｒｎｓ，Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｈｅｒｒｉｎｇ，Ｌ．Ｋｉｓｓｎｅｒ，Ｚ．Ｐｅｔｅｒｓｏｎ，Ｄ．Ｓｏｎｇ，Ｐｒｏｖａｂｌｅ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｔ Ｕｎｔｒｕｓｔｅｄ Ｓｔｏｒｅｓ（信頼されない記憶装置における証明可能データの保有）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２０２．ｐｄｆ）において、ＲＳＡベースの証明可能データ保有スキームとして、Ｓ−ＰＤＰスキーム（Ｓは「サンプリング」の略）が提案されている。この提案における「サンプリング」とは、クライアントがデータの一部を無作為に選択し、アーカイブに対して、この無作為に選択されたデータが健全な状態にある（すなわち、選択されたデータのデータ保全性が保たれている）という証拠を示すよう要求することである。Ｓ−ＰＤＰスキームは、ファイル全体のべき乗を必要とせず、通信の複雑性が一定であるため、従来技術の中で最も効率的である。
【００１１】
単純な解決策の短所は、通信の複雑性がクエリー対象のデータサイズに線形に比例することである。さらに、サードパーティ検証器の場合には、データ所有者のプライバシ侵害防止の観点から、ユーザデータを検証器に送ることは禁じられる。アーカイブサービスからデータを取り出さないようにするための方策としては、複数の秘密鍵を選択し、データに対して複数キーのハッシュＭＡＣを事前に計算することで、単純な解決策を改良するという方法がある。これにより、検証器は秘密鍵をその都度アーカイブサービスに開示し、新たなキーを付加したハッシュＭＡＣを要求して比較することが可能になる。しかし、この方法では、各データを検証できる回数は、事前に設定された秘密鍵の個数によって制限される。そのため、キーを使い果たした場合は、新たなＭＡＣを計算するために、アーカイブサービスからデータを取り出すことが不可避となる。
【００１２】
また、参考文献５および６の提案には、アーカイブがファイル全体をべき乗しなければならないという短所がある。参考として２０４８ビットのＲＳＡ係数を例にとると、１つの指数を完全にべき乗するには、Ｉｎｔｅｌ Ｃｏｒｅ Ｄｕｏ ２．１６ＧＨｚプロセッサ上で６１．３２５ミリ秒を要する。そのため、べき乗の所要時間は１メガバイト当たり２５１．３秒となり、６４ＭＢのファイルの保全性をテストする場合には、アーカイブがクライアントにデータ保全性証明を送信できるまでに１６０８３．８秒もかかってしまうことになる。
【００１３】
Ｓ−ＰＤＰスキームは、その設計目標（サンプリング）がデータ所有者には無意味な場合があるという問題を抱える。Ｓ−ＰＤＰスキームは、サンプリングによって、高い検出確率において遭遇されるファイルブロックの破壊の問題に対処する。例えば、参考文献７では、ファイルブロックの破壊が１％の場合に９９％の検出確率を達成する方法が説明されている。しかし、１ビットのエラーも許容できないファイルタイプは多い。例えば、符号復号器の構成パラメータが格納されるメディアファイルの先頭部分が失われると、処理が困難になる。また、暗号化されたファイルに埋め込まれた（公開鍵で暗号化された）対称暗号キーが壊れると、誰も普通テキストを回復できない無意味な暗号文となってしまう。概してデータ所有者は１００％のデータ安全性を要求し、どんな理由があろうとも妥協は許容しない。Ｓ−ＰＤＰスキームにはもう一つ、サードパーティ検証（いわゆる、「公的検証可能性」）システムで採用するには、あまりにも効率が低すぎるという問題もある。Ｓ−ＰＤＰスキームを使用した公的検証を可能とするためには、１つのファイルブロックをＲＳＡ公開鍵ｅよりも小さくする必要がある。例えば、２０４８ビットのＲＳＡモジュールの場合、公開鍵ｅは１０２４ビット程度でしかない。そのため、公的検証が可能なＳ−ＰＤＰスキームによる解決策では、１つのファイルを複数の１０２４ビットファイルブロックに論理的に分割しなければならない。その結果生じるファイルブロックは膨大な数に上り、その一つひとつにタグを生成する必要がある。これにより、タグのサイズはファイルそのものの２倍となり、クライアントがファイルにタグ付けするための時間を考慮すると、とうてい実用に資するものとはいえない。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
従来技術における上記の問題点を解決するため、本発明は、最初にデータのフィンガープリントがクライアントで生成され、そのフィンガープリントがデータと共にアーカイブに送信され、続いて、必要が生じたときにクライアントまたはサードパーティ検証器がデータの保全性を判定するための「チャレンジデータ」をアーカイブに送信し、アーカイブが受信したフィンガープリントを使用してデータの保全性を証明し、最後に、クライアントが「チャレンジデータ」への応答として返されたアーカイブからの出力に基づいてデータの保全性を検証する、証明可能データ保全性（ＰＤＩ）検証方法を提案する。
【００１５】
本発明の第１の態様によれば、データへのフィンガープリント付加方法であって、データをN個のブロックMi（i=1,2,…,N）に分割するステップと、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するステップと、有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択するステップと、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するステップとを備えることを特徴とする、データへのフィンガープリント付加方法が提供される。
【００１６】
nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であるのが望ましい。
【００１７】
nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するのが望ましい。
【００１８】
k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成されるのが望ましい。
【数１】
ここで、zMはデータの識別子である。
【００１９】
k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値であるのがさらに望ましい。
【００２０】
k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成されるのが望ましい。
【数２】
【００２１】
k番目のスーパーブロックのロケータWkは、少なくともｋと、データの識別子zMとを入力とするハッシュ値であるのがさらに望ましい。
【００２２】
本発明の第２の態様によれば、本発明の第１の態様によるデータへのフィンガープリント付加方法によってフィンガープリントが付加されたデータのデータ保全性証明方法であって、少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信するステップと、Φ個のボックスを構築するステップと、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当てるステップと、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するステップと、第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成するステップと、変換済みスーパーブロックの知識証明を生成するステップとを備えることを特徴とする、データ保全性証明方法が提供される。
【００２３】
変換済みスーパーブロックの知識証明は、変換済みスーパーブロック自体であるのが望ましい。
【００２４】
変換済みスーパーブロックの知識証明は、公開鍵と変換済みスーパーブロックとに基づいて生成されるのが望ましい。
【００２５】
変換済みスーパーブロックの知識証明は、以下の式で表されるのがさらに望ましい。
【数３】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックである。
【００２６】
あるいは、変換済みスーパーブロックの知識証明Hは、以下の式でも表される。
【数４】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックであり、prf5(・)は疑似ランダム関数を表す。
【００２７】
チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対、(k3,Λ)をさらに備えるのが望ましい。
【００２８】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ボックス構築から知識証明生成までのステップがψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成される。
【００２９】
Φの数は2φと等しいのがさらに望ましい。ここで、φ=[l/ψ]+1であり、lはこの方法のセキュリティレベルを決定するセキュリティレベル因数である。
【００３０】
第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されるのが望ましい。
【００３１】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００３２】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００３３】
データ保全性証明方法は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信するステップをさらに備えるのが望ましい。
【００３４】
本発明の第３の態様によれば、本発明の第２の態様によるデータ保全性証明方法に関連する方法として、本発明の第１の態様によるデータへのフィンガープリント付加方法によってフィンガープリントが付加されたデータのデータ保全性検証方法であって、第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するステップと、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信するステップと、Φ個のボックスを構築するステップと、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当てるステップと、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するステップと、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換して、変換済みロケータを生成するステップと、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成するステップと、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較するステップと、比較結果が一致の場合に、データのデータ保全性を検証するステップとを備えることを特徴とする、データ保全性検証方法が提供される。
【００３５】
検証対象の変換済みスーパーブロックの知識証明は、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成されるのが望ましい。
【００３６】
検証対象の変換済みスーパーブロックの知識証明は、第１および第２の秘密鍵x、vにも基づいて生成されるのがさらに望ましい。
【００３７】
検証対象の変換済みスーパーブロックの知識証明は、以下の式で表されるのがさらに望ましい。
prf5=((T1/x・W)v)，
ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkと、データの識別子zMとを入力とするハッシュ値である。
【００３８】
あるいは、検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される。
prf5=((Tx+zM・W)v)，
ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。
【００３９】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成されるのがさらに望ましい。
e(T,Yv,g2vzM)・e(W,
g2v)
ここで、Yj=Yv、g2v=g2v、Y= g2v∈G2である。G2=<g2>は、G1=<g1>に加えてもう１つのグループG=<g>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。
検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される。
e(H,g2)=e(T,Yv・g2vzM)・e(W,g2v)
ここで、Hは変換済みスーパーブロックの知識証明である。
【００４０】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成されるのがさらに望ましい。
e(T,Yv)・e(W,g2v)
ここで、Yv=g2v/x、g2v=g2v、Y=g2v∈G2である。G2=<g2>は、G=<g>に加えてもう１つのグループG1=<g1>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkとデータの識別子zMを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される。
e(H,g2)=e(T,Yv)・e(W,g2v)
ここで、Hは変換済みスーパーブロックの知識証明である。
【００４１】
チャレンジデータは、全n個のロケータの代わりに、どのΛ個のロケータをデータ保全性検証のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００４２】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ボックス構築から知識証明生成と検証対象知識証明との比較までのステップがψ回反復され、すべての比較結果が一致の場合にのみ、データのデータ保全性が検証される。
【００４３】
第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されるのが望ましい。
【００４４】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００４５】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００４６】
本発明の第４の態様によれば、データへのフィンガープリント付加装置であって、データをN個のブロックMi（i=1,2,…,N）に分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段と、有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するフィンガープリント付加手段とを備えることを特徴とする、データへのフィンガープリント付加装置が提供される。
【００４７】
nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であるのが望ましい。
【００４８】
nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するのが望ましい。
【００４９】
本発明の第５の態様によれば、データ保全性証明装置であって、少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信する受信手段と、Φ個のボックスを構築し、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段と、第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段と、変換済みスーパーブロックの知識証明を生成する知識証明生成手段とを備えることを特徴とする、データ保全性証明装置が提供される。
【００５０】
知識証明生成手段は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成するのが望ましい。
【００５１】
知識証明生成手段は、変換済みスーパーブロックの知識証明を、公開鍵と変換済みスーパーブロックに基づいて生成するのが望ましい。
【００５２】
チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００５３】
チャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、パッケージ化手段と、変換手段と、知識証明生成手段の動作がψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成される。
【００５４】
チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００５５】
デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されるのがさらに望ましい。
【００５６】
データ保全性証明装置は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段をさらに備えるのが望ましい。
【００５７】
本発明の第６の態様によれば、データ保全性検証装置であって、第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段と、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段と、Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段と、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段と、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器と、比較結果が一致の場合に、データ保全性を検証する検証装置とを備えることを特徴とする、データ保全性検証装置が提供される。
【００５８】
検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成するのが望ましい。
【００５９】
検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vにも基づいて生成するのがさらに望ましい。
【００６０】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータのうちどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備えるのが望ましい。
【００６１】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、反復因数ψをさらに備えるのが望ましい。これにより、ロケータパッケージ化手段と、検証対象知識証明生成手段と、比較器の動作がψ回反復され、すべての比較結果が一致の場合にのみ、検証手段がデータ保全性を検証する。
【００６２】
チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むのが望ましい。
【００６３】
チャレンジデータ生成・送信手段は、デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定するのがさらに望ましい。
【００６４】
本発明の第７の態様によれば、データ保全性検証システムであって、本発明の第５の態様によるデータ保全性証明装置と、本発明の第６の態様によるデータ保全性検証装置とを備えることを特徴とするデータ保全性検証システムが提供される。
【００６５】
データ保全性検証システムは、本発明の第４の態様によるデータへのフィンガープリント付加装置をさらに備えるのが望ましい。
【００６６】
データへのフィンガープリント付加装置は、データ保全性検証装置としても使用されるのがさらに望ましい。
【００６７】
本発明のＰＤＩスキームにより、圧倒的に高い確率（例えば、1-2-64）でデータのデータ保全性を確保することができる。従来技術は（１）データ保全性がビット単位で保証される、（２）クライアントがアーカイブに送信するチャレンジデータのサイズが一定である、（３）アーカイブがクライアントに送信するデータ保全性証明のサイズが一定である、という効果を実現するのに対し、本発明のＰＤＩスキームは以下の４つの主要な利点を有する。
（Ｉ） クライアントがデータのフィンガープリントを生成する速度が最速である。
（ＩＩ） アーカイブがクライアントのチャレンジデータへの応答を生成する速度が最速である。
（ＩＩＩ） クライアントがアーカイブの応答を検証する速度が最速である。
（ＩＶ） 検証器はサードパーティ検証器であってもよく、上記３つの利点（Ｉ）〜（ＩＩＩ）のすべてが同様に実現される。しかも、フィンガープリントのサイズが最小である。
【００６８】
以下では、具体例として６４ＭＢのデータファイルについて説明する。セキュリティ強度は２０４８ビットのＲＳＡ署名相当に設定され、l=64である。クライアントは速度２．１６ＧＨｚのＩｎｔｅｌ Ｃｏｒｅ Ｄｕｏプロセッサ、アーカイブは速度２．６６ＧＨｚのＩｎｔｅｌ Ｑｘ６７００ Ｃｏｒｅ２ Ｑｕａｄプロセッサとすると、ＰＤＩスキームにおいては、クライアントがファイルへのフィンガープリントの付加に要する時間は１２．７秒間、アーカイブが変換済みフィンガープリントと変換済みスーパーブロックの知識証明の生成に要する時間は１．４秒間、クライアントが知識証明の検証に要する時間は約０．４秒間である。これらの時間値は、従来技術のＲＳＡベーススキームが達成可能な理論的下限よりもさらに低い。
【先行技術文献】
【非特許文献】
【００６９】
【非特許文献１】Ａｍａｚｏｎ Ｓｉｍｐｌｅ Ｓｔｏｒａｇｅ Ｓｅｒｖｉｃｅ （Ａｍａｚｏｎ Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３
【非特許文献２】ＭｅｄｉａＭａｘ Ｆｒｅｅ Ｏｎｌｉｎｅ Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ
【非特許文献３】Ｇｍａｉｌ Ｄｒｉｖｅ Ｓｈｅｌｌ Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ
【非特許文献４】ＲＦＣ ４８１０，Ｌｏｎｇ−Ｔｅｒｍ Ａｒｃｈｉｖｅ Ｓｅｒｖｉｃｅ Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ Ｎｅｔｗｏｒｋ ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ
【非特許文献５】Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ ｉｎｔｅｇｒｉｔｙ ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ Ｐｒｏｃ．ｏｆ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｉｎｔｅｒｎａｌ ｃｏｎｔｒｏｌ ｉｎ Ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ（ＩＩＣＩＳ’０３），２００３
【非特許文献６】Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ Ｄａｔａ Ｐｏｓｓｅｓｓｉｏｎ ａｎｄ Ｕｎｃｈｅａｔａｂｌｅ Ｄａｔａ Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ
【図面の簡単な説明】
【００７０】
本発明の上記および他の目的、特徴、利点は、本発明の非限定的な実施例に関する以下の説明と添付図面とを参照することにより、さらに明らかになるであろう。
【００７１】
【図１】データ保全性証明における動作モデルを示す。
【図２】本発明によるデータ保全性証明方法（アトミック証明手順）とデータ保全性検証方法（アトミック検証手順）のフローチャートを示す。
【図３】データの論理ビューである。
【図４】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図５】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図６】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図７】６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証を示す。
【図８】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図９】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１０】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１１】２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。
【図１２】データ保全性証明における他の動作モデルを示す。
【図１３】データ保全性証明におけるさらに他の動作モデルを示す。
【図１４】本発明を実装したクライアント１４００のブロック図を示す。
【図１５】本発明を実装したアーカイブ１５００のブロック図を示す。
【図１６】本発明を実装した検証器１６００のブロック図を示す。
【発明を実施するための形態】
【００７２】
次に、図面を参照しながら本発明について説明する。以下の説明では、説明の便宜上いくつかの具体的な実施例を使用しているが、これらは本発明を限定するものではなく、例示にすぎない。また、本発明の理解が多少曖昧になる可能性はあるが、従来技術の構成・構造の説明は省略する。
（原理の説明）
【００７３】
本明細書において提示する証明可能データ保全性（ＰＤＩ）スキームは、従来技術が抱えるすべての問題を克服するのみならず、どの従来技術にも勝る性能を示す。
【００７４】
ＰＤＩスキームは、基本的には、図１に示す動作モデルに従った以下の３つのステップで構成される。
【００７５】
ステップ０’：
ＰＤＩスキームでは、有限循環グループG1=<g1>が必要とされるが、このG1は楕円曲線上の有限循環グループであるのが望ましい。本発明の開示では、その全体を通して、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。クライアントは、秘密鍵xとそれに対応する公開鍵とを有する。
【００７６】
クライアントは、データファイルをN個のブロックMi、i=1,2,…,Nに分割する。nB個のブロックは、それぞれ１つのスーパーブロックとして結合される。したがって、データはn={N/nB}個のスーパーブロックに分割される。データファイルの長さがｎ個のスーパーブロックに必要な長さに満たない場合は、データファイルはゼロを使用して論理的に埋められる。
【００７７】
クライアントは、各データファイルに関して、G1、i=1,2,…,nBのnB個の要素hjを作成する。好適なケースでは、クライアントは、hi=g1riとなるようにriを選択し、riを秘匿しておく。要素hiは、クライアントの公開鍵の一部とし、データファイルから独立させるのがさらに望ましい。
【００７８】
クライアントは自身の秘密鍵と上記nB個の要素hiを利用して、すべてのスーパーブロックのフィンガープリントを生成する。例えば、i番目のスーパーブロックのフィンガープリントは
【数５】
の形式をとる。ここで、ロケータWiは、少なくともiを入力とするハッシュ値である。また、データファイルのファイル名やバージョン番号などを入力として追加することもできる。zMは、データファイルに対して選択された固有な識別子である。例えば、あるデータファイル集合には識別子zM、別のデータファイル集合には別の識別子zM、というように選択する。あるいは、フィンガープリントを
【数６】
として計算することもできる。この場合、ロケータWiはiとzMを入力とする。好適なケースでは、クライアントは、riの値と、hi=griであるという知識を有する。したがって、
【数７】
を
【数８】
に置換することにより、クライアントはriの知識を利用してフィンガープリント処理を迅速化することができる。
【００７９】
ステップ０’の結果、クライアントは、n個のスーパーブロックに対してn個のフィンガープリントを取得する。クライアントは、データファイルとnB個の要素hjと共に、すべてのフィンガープリントをアーカイブに送信する。nB個の要素hiをクライアントの公開鍵の一部とする好適なケースでは、アーカイブはこれらの要素を公開鍵ディレクトリなどから事前に取得することもできる。その場合は、これらの要素をデータファイルと共に送信する必要はない。
【００８０】
ステップ１’：
クライアントは、データの保全性を判定するための「チャレンジデータ」をアーカイブに送信する。
【００８１】
アーカイブは、クライアントから受信したチャレンジデータに基づいて、アトミック証明手順を数回（例：ψ回）実行する必要がある。
【００８２】
アーカイブは、各アトミック証明手順において、まずΦ=2φ個のボックスを構築し、論理的かつ無作為にn個のフィンガープリントをこれらのボックスに割り当てる。個数Φと無作為性は、クライアントから受信した「チャレンジデータ」によって決まる。１つのフィンガープリントの配置先は、必ず１つのボックスに限定しなければならない。１つのフィンガープリントを１つのスーパーブロックに対応させることを念頭に全n個のフィンガープリントをボックスに配置すると、その結果として、各ボックスには１つの「割り当て済みスーパーブロック」と、そのボックスに割り当てられたフィンガープリントに基づいて生成された「割り当て済みスーパーブロック」の「割り当て済みフィンガープリント」とが存在することになる。例えば、λ番目のボックスに、η番目およびω番目のスーパーブロックに関連する２つのフィンガープリントのみが配置されるケースであれば、このボックスの「割り当て済みスーパーブロック」は
【数９】
を含み、「割り当て済みスーパーブロック」の「割り当て済みフィンガープリント」は
【数１０】
となる。
【００８３】
次に、アーカイブは、すべてのボックスの「割り当て済みスーパーブロック」と「割り当て済みフィンガープリント」に別の無作為性を適用することにより、１つの「変換済みスーパーブロック」と、その「変換済みスーパーブロック」の１つの「変換済みフィンガープリント」を生成する。この無作為性もまた、クライアントから受信した「チャレンジデータ」によって決定される。上記の例についてさらに説明すれば、「変換済みスーパーブロック」は
【数１１】
を含み、「変換済みスーパーブロック」の「変換済みフィンガープリント」は
【数１２】
（aλはクライアントの「チャレンジデータ」によって決定された乱数）となる。
【００８４】
最後に、アーカイブは、「変換済みスーパーブロックの知識証明」を生成する。これには「変換済みスーパーブロック」を直接使用することもできる。あるいは、標準的なゼロ知識証明技術（対話または非対話方式）による「変換済みスーパーブロック」のコンテンツの知識を使用してもよい。また、クライアントの「チャレンジデータ」がHi=hiv，i=1,2,…,nBを含む場合に、クライアントがチャレンジデータ毎に異なるvを選択し、vを秘匿しておくことも可能である。好適なケースでは、Hiはクライアントの公開鍵、vはクライアントの秘密鍵の一部である。アーカイブは、Hiを利用して、「変換済みスーパーブロックの知識証明」を
【数１３】
として計算する。
【００８５】
アーカイブは、「変換済みフィンガープリント」Tと「変換済みスーパーブロックの知識証明」Hとを、アトミック証明手順の出力としてクライアントに送信する。
【００８６】
アーカイブは、アトミック証明手順を全部でψ回反復する必要がある。ボックス数を決定する値としては、ψ=[l/ψ]+1を選択することができる。ここで、lはセキュリティレベルを決定する値であり、クライアントによって選択される。乱数aλのビット長としては、ψを選択する。アトミック手順をψ回反復すると、ＰＤＩスキームのセキュリティレベルは(n/ψ)・2-lとなる。これは、１つ以上のブロックが破壊されている場合に、アーカイブが検証器に正しい結果を返す確率は、最大
(n/ψ)・2-lであることを意味する。
【００８７】
上記の「個数Φと無作為性は、クライアントか受信したチャレンジデータによって決定される」と「aλは、クライアントのチャレンジデータによって決定される乱数である」の部分については、代替の実施例がある。例えば、φ=nを選択し、n個のフィンガープリントをn個のボックスに均等に配置し（すなわち、１つのボックスに必ず１つのフィンガープリントが含まれるようにする）、aλのビット長としてlを選択したとすると、この場合には、ψ=1を選択すると、n・2-lのセキュリティレベルが実現される。
【００８８】
ステップ２’：
クライアントは、アーカイブから、ψ回のアトミック証明手順の全出力を受信する。
【００８９】
クライアントは、１回のアトミック証明手順から得られた「変換済みスーパーブロック」の「変換済みフィンガープリント」と「変換済みスーパーブロックの知識証明」の各々を対象に、アトミック検証手順を実行する。
【００９０】
クライアントは、各アトミック検証手順において、まずΦ個のボックスを構築し、論理的かつ無作為にロケータWiをこれらのボックスに割り当てる。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブがフィンガープリントを割り当てる際に使用した無作為性と同一である。１つのロケータは、必ず１つのボックスに配置しなければならない。全n個のロケータがボックスに配置された後、各ボックス内には、ボックスに割り当てられたロケータに基づいて生成された「割り当て済みロケータ」が存在する。例えば、λ番目のボックスに２つのロケータWηおよびWωのみが配置されるケースであれば、このボックスの「割り当て済みロケータ」は
【数１４】
となる。
【００９１】
次に、クライアントは、別の無作為性をすべてのボックスの「割り当て済みロケータ」に適用することにより、１つの「変換済みロケータ」を生成する。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブが「変換済みフィンガープリント」を計算する際に使用した無作為性と同一である。「変換済みロケータ」は
【数１５】
となる。ここで、aλはクライアントの「チャレンジデータ」によって決定された乱数である。
【００９２】
最後に、アーカイブが「変換済みスーパーブロックの知識証明」を直接「変換済みスーパーブロック」として生成する場合には、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をH’=(Tx+zM/W)として計算し、
【数１６】
と比較する。アトミック検証手順は、一致した場合にのみ、「成功」を出力する。あるいは、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をH’=(Tx+zM/W)vとして計算し、アーカイブから受信した値Hと比較することもできる。アトミック検証手順は、H=H’の場合にのみ、「成功」を出力する。また、フィンガープリントが
【数１７】
として計算される場合には、「検証対象の変換済みスーパーブロックの知識証明」は(T1/x/W)vとして計算される。
【００９３】
クライアントは、アトミック検証手順が「成功」を出力した場合にのみ、アーカイブ側でデータ保全性が保たれていると判定する。アーカイブ側で１つ以上のブロックが破壊されているときにクライアントが誤判定する確率は、最大で2-lである。
（詳細な説明）
【００９４】
次に、図面を参照しながら本発明についてさらに詳細に説明する。
【００９５】
本発明の開示では、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。
【００９６】
G1=<g1>とG2=<g2>を２つの有限循環グループとし、G=<g>を追加のグループとする。|G1|=|G2|=|G|=p（pは大きな素数）である。双線形マップe: G1×G2→gは、以下の特性を有する関数である。
■ 双線形：すべてのh1∈G1，h2∈G2、すべてのa.b∈Zpにおいて、e(h1a,
h2b)= e(h1, h2)abである。
■ 非縮退：∃h1∈G1，∃h2∈G2は、e(h1, h2)≠I（Iはgの識別子）の関係を有する。
■ 計算可能：ｅを計算するための効率的なアルゴリズムが存在する。
【００９７】
入力セキュリティパラメータ1kに基づいて上記の双線形マップの設定を出力し、それを(p,G1,G2,g,g1,g2)←setup(1k)として記述するセットアップアルゴリズムsetup(・)が存在すると仮定する。
【００９８】
G1、G2、gは同一の素数位数pを有するので、双線形の特性と非縮退の特性から、e(g1,g2)=gであることは容易に理解できる。．
【００９９】
(p,G1,G2,g,g1,g2)←setup(1k)とし、５つの疑似ランダム関数prf1:{0,1}*←Zp,、prf2:{0,1}*←G1、prf3(φ):{0,1}*←Z2φ、prf4(φ):{0,1}*←Z2φ、およびprf5:G1→{0,1}160をシステムパラメータとする。
【０１００】
クライアントによるデータへのフィンガープリント付加
クライアントは、秘密鍵(x,v)←Zp2と公開鍵Y=g2x∈G2を有する。クライアントは、認証局からYの証明書を取得するのが望ましい。あるいは、クライアントの秘密鍵vを、例えばv=prf1(x,”second
private key”)として計算することもできる。
【０１０１】
さらに、クライアントは、(hi=g1prf1(i,x),Hi=hiv)∈G12，i=1,2,…,nBを計算して自身の公開鍵とする。
【０１０２】
データMを、各ビット長がlM（lM<logpが必須）のN個のブロックMi（i=1,2,…,N）に分割する。Mの修飾ファイル名をFNMとする。
【０１０３】
図３に、データMを論理的に分割してn個のスーパーブロックにする方法を示す。スーパーブロック数は、n=[N/nB]で表す。データMの長さがN・lMまたはn・(nB・lM)に満たない場合は、ゼロを使用して論理的に埋められる。
【０１０４】
クライアントは、以下を実行してデータにフィンガープリントを付加する。
ａ） クライアントは、識別子zM←Zpを選択し、ロケータWi=prf2(i,zM,FNM)∈G1、
【数１８】
を計算する。i番目のスーパーブロックのフィンガープリントを、Tiと命名する。
ｂ） 秘密鍵xを使用して(FNM,M,zM,{Ti})に署名して、署名Sを生成する。
ｃ） FNMに対してzMを保存する。
ｄ） FNM、M、zM∈Zp、{Ti}∈G1n、およびSをアーカイブに送信する。
ｅ） アーカイブは、FNM、M、zM、{Ti}、およびSを受信後、クライアントの公開鍵を使用して、Sが(FNM,M,zM,{Ti})の有効な署名であるか検証する。
アーカイブによるデータ保全性の証明
【０１０５】
アーカイブが（最大2-lの確率におけるエラー以外には）ゼロビットエラー率でFNMのコンテンツを保持しているか確認するため、クライアントがアーカイブにチャレンジデータを送り、アーカイブはそれに対して以下を応答する。
ｉ） クライアントは、反復因数
【数１９】
を選択する。
ｉｉ） クライアントは、(k1,k2)←Zp2を選択し、FNM，chal=(l,ψ, k1,k2)をアーカイブに送信する。
ｉｉｉ） アーカイブは、FNMとchal=(l,ψ, k1,k2)を受信後、まずφ=[l/ψ]+1を計算し、変換済みフィンガープリントTk=O∈G1，k=1,2,…,ψ（OはG1の識別子）を初期化する。その後、以下のアトミック証明手順を独自に全ψ回にわたって反復する。
ｉｉｉ−ａ． 割り当て済みフィンガープリント
【数２０】
、割り当て済みスーパーブロックevj=0、および変換済みスーパーブロックEj=0、v=0,1,…,Φ-1=2φ-1,j=1,2,…,nBを初期化する。
ｉｉｉ−ｂ． i=1,2,…,nの各々について、以下の計算を行う。
ｂ−ｉ． σ=prf3(I,k,k1)
ｂ−ｉｉ．
【数２１】
これはTiをσ番目のボックスの割り当て済みフィンガープリントに付加することを意味する。
ｂ−ｉｉｉ． j=1,2,…,nBの各々について、eσj+=M(i-1)*nB+jmodpを計算する。これはM(i-1)*nB+jをσ番目のボックスの割り当て済みスーパーブロックに付加することを意味する。
ｉｉｉ−ｃ． v=1,2,…,Φの各々について、以下の計算を行う。
ｃ−ｉ． av=prf4(v,k,k2)
ｃ−ｉｉ．
【数２２】
ｃ−ｉｉｉ． J=1,2,…,nBの各々について、Ej+=av・evjmodpを計算する。
ｉｉｉ−ｄ．
【数２３】
を計算し、変換済みスーパーブロックの知識証明とする。
ｉｖ） 保全性証明(Tk,Hk)，k=1,2,…,ψをクライアントに送信する。
【０１０６】
上記に代わる方法として、クライアントがk1←Zpを選択し、k2を例えばk2=prf1(k1,”second
randomness defining key”)として計算することもできる。そのため、k2の送信は省略することができる。
【０１０７】
クライアントによるデータ保全性の検証
クライアントは、(Tk,Hk)、k=1,2,…,ψの受信後、以下のアトミック検証手順を独自に全ψ回にわたって反復する。
Ｉ） 変換済みロケータWk=I∈G1、割り当て済みロケータWv=I∈G1、v=0,1,…,Φ-1=2φ-1を初期化する。
ＩＩ） i=1,2,…,nの各々について、σ=prf3(i,k,k1)およびWσ*=prf2(I,FNM)を計算する。
ＩＩＩ） v=1,2,…,Φの各々について、av=prf4(v,k,k2)およびWk*=-Wv-avを計算する。
ＩＶ） 計算によりHk=prf5((Tkx+zM・Wk)v)であるか検証し、この合同式が成り立つ場合にのみＴＲＵＥを出力する。
全てのアトミック検証手順でＴＲＵＥが出力された場合にのみ、クライアントはデータ保全性証明が正しいと判断する。
（具体例）
【０１０８】
図４〜７は、６ブロックM1〜M6を使用し、nB=2として３つのスーパーブロックを形成した本発明の具体例と、その正確性の実証結果を示す。当該技術分野に精通する当業者は、上記の説明の各ステップと図４〜７を参照することにより、本発明をきわめて明確に理解できるであろう。
（実際の実験）
【０１０９】
図８〜１１は、２５６ブロック（１ブロックは２７バイト）を結合して１つのスーパーブロックにし、Φ=29=512ボックスを使用し、データファイルのサイズを６４ＭＢとした場合の、実際の実験結果を示す。図９〜１１には、参考文献７の結果も示す。これにより、本発明では参考文献７に比較して計算時間コストが大幅に改善されていることが分かる。
（他の実施例）
（代替スキーム１：）
【０１１０】
ＰＤＩ−２スキームは、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄと「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。これは、公的検証可能性をサポートするスキームである。
【０１１１】
クライアントは、Yv=Yvとg2v=
g2vを計算して自身の公開鍵とする。
【０１１２】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄ．
【数２４】
を計算し、変換済みスーパーブロックの知識証明とする。
【０１１３】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ’） 計算によりe(Hk,g2)=e(Tk,Yv,g2vzM)・e(Wk,
g2v)であることを検証する。
【０１１４】
ＰＤＩ−２スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム１．１：）
【０１１５】
ＰＤＩ−２スキームは、ＰＤＩ−２の「クライアントによるデータ保全性の検証」を一部変更したものである。
【０１１６】
「クライアントによるデータ保全性の検証」のステップＩＶ’）への変更：
ＩＶ−ｅ）k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数２５】
であることを検証する。
【０１１７】
加速化ＰＤＩ−２スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム２：）
【０１１８】
ＰＤＩ−３スキームは、「クライアントによるデータへのフィンガープリント付加」のステップａ）と「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。
【０１１９】
「クライアントによるデータへのフィンガープリント付加」のステップａ）への変更：
ａａ） クライアントは、識別子ZM←Zpを選択し、
【数２６】
を計算する。
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ”） 計算によりHk=prf5((Tk1/x・Wk)v)であることを検証する。
（代替スキーム３：）
【０１２０】
ＰＤＩ−４スキームは、上記の代替スキーム２に対し、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．と「クライアントによるデータ保全性の検証」のステップＩＶ）に一部変更を加えたものである。これもまた、公的検証可能性をサポートするスキームである。
【０１２１】
クライアントは、Yv=g2v/xとg2v=g2vを計算して自身の公開鍵とする。
【０１２２】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄｄ．
【数２７】
を計算し、変換済みスーパーブロックの知識証明とする。
【０１２３】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ’’’） 計算によりe(Hk,g2)=e(Tk,Yv)・e(Wk,g2v)であることを検証する。
【０１２４】
ＰＤＩ−４スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム３．１：）
【０１２５】
加速化ＰＤＩ−４は、ＰＤＩ−４の「クライアントによるデータ保全性の検証」を一部変更したものである。
【０１２６】
「クライアントによるデータ保全性の検証」のステップＩＶ’’’）への変更：
ＩＶ−ｆ）k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数２８】
であることを検証する。
【０１２７】
加速化ＰＤＩ−４スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム４：）
【０１２８】
上記のすべてのスキームに対し、システムパラメータ、「クライアントによるデータへのフィンガープリント付加」のステップ、および「クライアントによるデータ保全性の検証」のステップに一部変更を加えることで、サンプリングをサポートするスキームが得られる。
【０１２９】
サンプリングをサポートするには、システムパラメータprf6:{0,1}*→{1,2,…,n}を追加する必要がある。チャレンジデータchal=(l,ψ,k1,
k2)には、キーk3←Zpと正の数値Λが追加される。
【０１３０】
次に、「クライアントによるデータへのフィンガープリント付加」と「クライアントによるデータ保全性の検証」の全ステップにおいて、全てのi=1,2,…,nがi=prf6(k3,1),
prf6(k3,2),…, prf6(k3,Λ)に置換される。これにより、i=prf6(k3,1),
prf6(k3,2),…, prf6(k3,Λ)によって選択されたΛ個のスーパーブロックのみが処理対象となるため、サンプリングされたスーパーブロックデータのみのデータ保全性が検証される。
【０１３１】
したがって、代替スキーム４においては、アーカイブはすべてのスーパーブロックを使用しなくてもデータ保全性証明を生成することができる。アーカイブは、クライアントのチャレンジデータの情報をもとに、証明の生成において、どのスーパーブロックをいくつ選択すべきかを決定する。
（代替動作モデル：）
【０１３２】
非特許文献４（ＲＦＣ ４８１０）で提案されるタイムスタンプ局（ＴＳＡ）を導入することにより、図１２に示すように、チャレンジキー(k1,k2)←Zp2をＴＳＡから取得したデジタル署名付きタイムスタンプに置換することが可能になる。ここで、タイムスタンプをＴとすると、標準的なハッシュアルゴリズムＳＨＡ−１を使用して、k1＝ＳＨＡ−１（Ｔ，“１”）とk2＝ＳＨＡ−１（Ｔ，“２”）を得ることができる。こうした置換を行った場合のクライアントのチャレンジデータは、データがＴＳＡによるタイムスタンプ発行時間まで正常に保持されているかどうかの検証を求める内容となる。この事前計算により、アーカイブの応答(Tk,Hk)の利用が必須となるのはアトミック検証手順の最後のステップのみとなり、アーカイブとクライアントのいずれにおいても大幅に処理が簡素化される。
【０１３３】
さらに、図１３に示すように、検証器がサードパーティ検証器の場合には、ＴＳＡのタイムスタンプからk1とk2を推論することもできる。また、サンプリングが有効な場合には、k3はＴＳＡのタイムスタンプから、例えばk3＝ＳＨＡ−１（Ｔ，“３”）として推論することができる。
（ハードウェア実装：）
【０１３４】
当業者には明らかなように、本発明はハードウェア構造によって実装することもできる。以下では、限定ではなく参考として、いくつかの例について説明する。
クライアント
【０１３５】
図１４に、本発明を実装したクライアント１４００のブロック図を示す。この実装では、クライアント１４００はデータへのフィンガープリント付加装置として使用される。
【０１３６】
図１４に示すように、クライアント１４００は、データをN個のブロックMi，i=1,2,…,Nに分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段１４１０と、有限循環グループG1=<g1>からnB個の要素hj，j=1,2,…,nBを選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k=1,2,…,nであるk番目のスーパーブロックのフィンガープリントTkを生成するフィンガープリント付加手段１４２０とを含む。クライアント１４００は、さらに、生成されたスーパーブロック、有限循環グループ、生成されたフィンガープリント、ロケータ、秘密鍵などの、スーパーブロック生成手段１４１０とフィンガープリント付加手段１４２０によって利用または生成される情報を格納するメモリ１４３０を含む。ただし、メモリ１４３０は、上記のように独立した手段とすることも、あるいはスーパーブロック生成手段１４１０とフィンガープリント付加手段１４２０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１３７】
同様に、nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の部分とすることができる。また、nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足するものとすることができる。さらに、公開鍵と秘密鍵もメモリ１４３０に格納することができる。
アーカイブ
【０１３８】
図１５に、本発明を実装したアーカイブ１５００のブロック図を示す。この実装では、アーカイブ１５００はデータ保全性証明装置として使用される。
【０１３９】
図１５に示すように、アーカイブ１５００は、少なくとも第１のランダム性定義キーk1と第２のランダム性定義キーk2とから成るチャレンジデータを受信する受信手段１５１０と、上記チャレンジデータが決定する数であるΦ個のボックスを構築し、第１のランダム性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段１５２０と、第２のランダム性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段１５３０と、変換済みスーパーブロックの知識証明を生成する知識証明生成手段１５４０とを含む。アーカイブ１５００はさらに、受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０によって使用または生成される情報を格納するメモリ１５５０を含む。ただし、メモリ１５５０は、上記のように独立した手段とすることも、あるいは受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１４０】
知識証明生成手段１５４０は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成することも、あるいは公開鍵と変換済みスーパーブロックに基づいて生成することもできる。
【０１４１】
チャレンジデータには、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段１５２０がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることができる。
【０１４２】
チャレンジデータは、反復因数ψをさらに備えることができる。これにより、パッケージ化手段１５２０と、変換手段１５３０と、知識証明生成手段１５４０の動作がψ回反復され、各反復毎に、１つの変換済みスーパーブロックの知識証明が生成される。これは、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明と呼ばれる。
【０１４３】
チャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含めることができる。
【０１４４】
さらに、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成される。
【０１４５】
また、アーカイブ１５００は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段１５６０をさらに備える。
検証器（クライアントまたはサードパーティ検証器）
【０１４６】
図１６に、本発明を実装した検証器１６００のブロック図を示す。この実装では、検証器１６００はデータ保全性検証装置として使用される。検証器１６００はクライアント１４００自体、あるいはサードパーティ検証器のいずれでもよいことは当業者には明かであろう。クライアント１４００自体を検証器１６００とする前者のケースでは、図１４のデータにフィンガープリントを付加するためのサブシステムと、図１６の検証データ保全性を検証するためのサブシステムはクライアント１４００に備えられる。一方、サードパーティ検証器を検証器１６００とする後者のケースでは、サードパーティ検証器は図１６の構造を備えることのみが必須となり、図１４の構造は任意である。
【０１４７】
図１６に示すように、検証器１６００は、第１のランダム性定義キーk1と第２のランダム性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段１６１０と、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段１６２０と、Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段１６３０と、第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段１６４０と、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器１６５０と、比較結果が一致の場合に、データ保全性を検証する検証装置１６６０とを含む。検証器１６００はさらに、チャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０によって使用または生成される情報を格納するメモリ１６７０を含む。ただし、メモリ１６７０は、上記のように独立した手段とすることも、あるいはチャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１４８】
検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成することができる。
【０１４９】
また、検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vに基づいて生成することもできる。
【０１５０】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータの代わりにどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備える。
【０１５１】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、反復因数ψをさらに備える。これにより、ロケータパッケージ化手段１６３０と、検証対象知識証明生成手段１６４０と、比較器１６５０の動作がψ回反復され、すべての比較結果が一致の場合にのみ、検証手段１６６０がデータ保全性を検証する。
【０１５２】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得した、デジタル署名付きのタイムスタンプを含めることができる。
【０１５３】
チャレンジデータ生成・送信手段１６１０は、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定する。
【０１５４】
上記の説明は本発明の好適な実施例のみを示したものであり、いかなる形であれ本発明を限定することを意図するものではない。したがって、本発明の適用範囲には、本発明の精神および原則に則ったあらゆる変更、置換、改良等も内包される。
【符号の説明】
【０１５５】
１：チャレンジデータ？
２：データ保全性証明
１’：タイムスタンプ
２’：データ保全性証明
１４１０：スーパーブロック生成手段
１４２０：フィンガープリント付加手段
１４３０：メモリ
１５１０：受信手段
１５２０：パッケージ化手段
１５３０：変換手段
１５４０：知識証明生成手段
１５６０：送信手段
１５５０：メモリ
１６１０：チャレンジデータ生成・送信手段
１６２０：受信手段
１６３０：ロケータパッケージ化手段
１６４０：検査対象知識証明生成手段
１６５０：比較器
１６６０：検証手段
１６７０：メモリ
【特許請求の範囲】
【請求項１】
データへのフィンガープリント付加方法であって、
前記データをN個のブロックMi（i=1,2,…,N）に分割するステップと、
nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するステップと、
有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択するステップと、
k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するステップと
を有することを特徴とするデータへのフィンガープリント付加方法。
【請求項２】
前記nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であることを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項３】
前記nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足することを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項４】
前記k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成される、
【数２９】
ここで、zMはデータの識別子
ことを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項５】
前記k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値であることを特徴とする請求項４に記載のデータへのフィンガープリント付加方法。
【請求項６】
前記k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成される、
【数３０】
ことを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項７】
前記k番目のスーパーブロックのロケータWkは、少なくともｋと、データの識別子zMとを入力とするハッシュ値であることを特徴とする請求項６に記載のデータへのフィンガープリント付加方法。
【請求項８】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項５又は請求項７に記載のデータへのフィンガープリント付加方法。
【請求項９】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項４又は請求項７に記載のデータへのフィンガープリント付加方法。
【請求項１０】
請求項１から請求項９の何れかに記載のデータへのフィンガープリント付加方法によって、フィンガープリントが付加されたデータのデータ保全性証明方法であって、
少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信するステップと、
Φ個のボックスを構築するステップと、
前記第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当てるステップと、
前記n個のフィンガープリントの割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するステップと、
前記第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成するステップと、
変換済みスーパーブロックの知識証明を生成するステップと
を有することを特徴とするデータ保全性証明方法。
【請求項１１】
前記変換済みスーパーブロックの知識証明は、変換済みスーパーブロック自体であることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１２】
前記変換済みスーパーブロックの知識証明は、公開鍵と変換済みスーパーブロックとに基づいて生成されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１３】
前記変換済みスーパーブロックの知識証明Ｈは、以下の式で表される、
【数３１】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロック、
ことを特徴とする請求項１２に記載のデータ保全性証明方法。
【請求項１４】
前記変換済みスーパーブロックの知識証明Ｈは、以下の式で表される、
【数３２】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックであり、prf5(・)は疑似ランダム関数を表す、
ことを特徴とする請求項１２に記載のデータ保全性証明方法。
【請求項１５】
前記チャレンジデータは、全n個のスーパーブロックと、対応するフィンガープリントの代わりに、何れのΛ個のスーパーブロックと、対応するフィンガープリントとをデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１６】
前記チャレンジデータは、反復因数ψをさらに備え、
ボックス構築から知識証明生成までのステップがψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１７】
前記Φの数が、2φと等しい（ここで、φ=[l/ψ]+1であり、lはこの方法のセキュリティレベルを決定するセキュリティレベル因数）
ことを特徴とする請求項１６に記載のデータ保全性証明方法。
【請求項１８】
前記第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１９】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項２０】
前記デジタル署名付きタイムスタンプから、前記第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項１９に記載のデータ保全性証明方法。
【請求項２１】
前記変換済みフィンガープリントと、前記変換済みスーパーブロックの知識証明とを送信するステップをさらに備えることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項２２】
請求項１から請求項９の何れかに記載のデータへのフィンガープリント付加方法によって、フィンガープリントが付加されたデータのデータ保全性検証方法であって、
第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するステップと、
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信するステップと、
Φ個のボックスを構築するステップと、
第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当てるステップと、
n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するステップと、
第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換して、変換済みロケータを生成するステップと、
変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成するステップと、
検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較するステップと、
比較結果が一致の場合に、データのデータ保全性を検証するステップと
を有することを特徴とするデータ保全性検証方法。
【請求項２３】
前記検証対象の変換済みスーパーブロックの知識証明は、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項２４】
前記検証対象の変換済みスーパーブロックの知識証明は、第１および第２の秘密鍵x、vにも基づいて生成されることを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項２５】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される、
prf5=((T1/x・W)v)，
（ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkと、データの識別子zMとを入力とするハッシュ値である。）
ことを特徴とする請求項２４に記載のデータ保全性検証方法。
【請求項２６】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項２５に記載のデータ保全性検証方法。
【請求項２７】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項２８】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される、
prf5=((Tx+zM・W)v)，
（ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。）
ことを特徴とする請求項２４に記載のデータ保全性検証方法。
【請求項２９】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項２８に記載のデータ保全性検証方法。
【請求項３０】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成され、
e(T,Yv,g2vzM)・e(W,
g2v)
（ここで、Yj=Yv、g2v=g2v、Y= g2v∈G2である。G2=<g2>は、G1=<g1>に加えてもう１つのグループG=<g>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。）
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される、
e(H,g2)=e(T,Yv・g2vzM)・e(W,g2v)
（ここで、Hは変換済みスーパーブロックの知識証明である。）
ことを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項３１】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項３０に記載のデータ保全性検証方法。
【請求項３２】
前記チャレンジデータが、検証加速因数ψを含み、
k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数３３】
であることを検証することを特徴とする請求項３０に記載のデータ保全性検証方法。
【請求項３３】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成され、
e(T,Yv)・e(W,g2v)
（ここで、Yv=g2v/x、g2v=g2v、Y=g2v∈G2である。G2=<g2>は、G=<g>に加えてもう１つのグループG1=<g1>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkとデータの識別子zMを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。）
検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される、
e(H,g2)=e(T,Yv)・e(W,g2v)
（ここで、Hは変換済みスーパーブロックの知識証明である。）
ことを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項３４】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３５】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３６】
前記チャレンジデータが、検証加速因数ψを含み、
k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数３４】
であることを検証することを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３７】
前記チャレンジデータは、全n個のロケータの代わりに、何れのΛ個のロケータをデータ保全性検証のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項３８】
前記チャレンジデータは、反復因数ψをさらに備え、
ボックス構築から知識証明生成と検証対象知識証明との比較までのステップがψ回反復され、すべての比較結果が一致の場合にのみ、データのデータ保全性が検証されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項３９】
前記第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項４０】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項４１】
前記デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項４０に記載のデータ保全性検証方法。
【請求項４２】
データへのフィンガープリント付加装置であって、
データをN個のブロックMi（i=1,2,…,N）に分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段と、
有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するフィンガープリント付加手段と
を備えることを特徴とするデータへのフィンガープリント付加装置。
【請求項４３】
前記nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であることを特徴とする請求項４２に記載のデータへのフィンガープリント付加装置。
【請求項４４】
前記nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足することを特徴とする請求項４２に記載のデータへのフィンガープリント付加装置。
【請求項４５】
データ保全性証明装置であって、
少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信する受信手段と、
Φ個のボックスを構築し、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段と、
第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段と、
変換済みスーパーブロックの知識証明を生成する知識証明生成手段と
を備えることを特徴とするデータ保全性証明装置。
【請求項４６】
前記知識証明生成手段は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成することを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４７】
前記知識証明生成手段は、変換済みスーパーブロックの知識証明を、公開鍵と変換済みスーパーブロックに基づいて生成することを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４８】
前記チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４９】
前記チャレンジデータは、反復因数ψをさらに備え、
前記パッケージ化手段と、前記変換手段と、前記知識証明生成手段の動作がψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm（m=1,2,…,ψ）のm番目の知識証明として生成されることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５０】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５１】
前記デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項５０に記載のデータ保全性証明装置。
【請求項５２】
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段をさらに備えることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５３】
データ保全性検証装置であって、
第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段と、
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段と、
Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段と、
第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段と、
検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器と、
比較結果が一致の場合に、データ保全性を検証する検証装置と
を備えることを特徴とするデータ保全性検証装置。
【請求項５４】
前記検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５５】
前記検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vにも基づいて生成することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５６】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、前記ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータのうちどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５７】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、反復因数ψをさらに備え、
前記ロケータパッケージ化手段と、前記検証対象知識証明生成手段と、前記比較器の動作がψ回反復され、すべての比較結果が一致の場合にのみ、前記検証手段がデータ保全性を検証することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５８】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５９】
前記チャレンジデータ生成・送信手段は、デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項６０】
データ保全性検証システムであって、
請求項４５から請求項５２の何れかに記載のデータ保全性証明装置と、請求項５３から請求項５９の何れかに記載のデータ保全性検証装置とを備えることを特徴とするデータ保全性検証システム。
【請求項６１】
請求項４５から請求項５２の何れかに記載のデータへのフィンガープリント付加装置をさらに備えることを特徴とする請求項６０に記載のデータ保全性検証システム。
【請求項６２】
前記データへのフィンガープリント付加装置は、データ保全性検証装置としても使用されることを特徴とする請求項６１に記載のデータ保全性検証システム。
【請求項１】
データへのフィンガープリント付加方法であって、
前記データをN個のブロックMi（i=1,2,…,N）に分割するステップと、
nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するステップと、
有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択するステップと、
k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するステップと
を有することを特徴とするデータへのフィンガープリント付加方法。
【請求項２】
前記nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であることを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項３】
前記nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足することを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項４】
前記k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成される、
【数２９】
ここで、zMはデータの識別子
ことを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項５】
前記k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値であることを特徴とする請求項４に記載のデータへのフィンガープリント付加方法。
【請求項６】
前記k番目のスーパーブロックのフィンガープリントTkは、以下の式に従って生成される、
【数３０】
ことを特徴とする請求項１に記載のデータへのフィンガープリント付加方法。
【請求項７】
前記k番目のスーパーブロックのロケータWkは、少なくともｋと、データの識別子zMとを入力とするハッシュ値であることを特徴とする請求項６に記載のデータへのフィンガープリント付加方法。
【請求項８】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項５又は請求項７に記載のデータへのフィンガープリント付加方法。
【請求項９】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項４又は請求項７に記載のデータへのフィンガープリント付加方法。
【請求項１０】
請求項１から請求項９の何れかに記載のデータへのフィンガープリント付加方法によって、フィンガープリントが付加されたデータのデータ保全性証明方法であって、
少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信するステップと、
Φ個のボックスを構築するステップと、
前記第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当てるステップと、
前記n個のフィンガープリントの割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するステップと、
前記第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成するステップと、
変換済みスーパーブロックの知識証明を生成するステップと
を有することを特徴とするデータ保全性証明方法。
【請求項１１】
前記変換済みスーパーブロックの知識証明は、変換済みスーパーブロック自体であることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１２】
前記変換済みスーパーブロックの知識証明は、公開鍵と変換済みスーパーブロックとに基づいて生成されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１３】
前記変換済みスーパーブロックの知識証明Ｈは、以下の式で表される、
【数３１】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロック、
ことを特徴とする請求項１２に記載のデータ保全性証明方法。
【請求項１４】
前記変換済みスーパーブロックの知識証明Ｈは、以下の式で表される、
【数３２】
ここで、Hj=hjvであり、vは第２の秘密鍵、Ejは変換済みスーパーブロックであり、prf5(・)は疑似ランダム関数を表す、
ことを特徴とする請求項１２に記載のデータ保全性証明方法。
【請求項１５】
前記チャレンジデータは、全n個のスーパーブロックと、対応するフィンガープリントの代わりに、何れのΛ個のスーパーブロックと、対応するフィンガープリントとをデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１６】
前記チャレンジデータは、反復因数ψをさらに備え、
ボックス構築から知識証明生成までのステップがψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm，m=1,2,…,ψのm番目の知識証明として生成されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１７】
前記Φの数が、2φと等しい（ここで、φ=[l/ψ]+1であり、lはこの方法のセキュリティレベルを決定するセキュリティレベル因数）
ことを特徴とする請求項１６に記載のデータ保全性証明方法。
【請求項１８】
前記第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項１９】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項２０】
前記デジタル署名付きタイムスタンプから、前記第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項１９に記載のデータ保全性証明方法。
【請求項２１】
前記変換済みフィンガープリントと、前記変換済みスーパーブロックの知識証明とを送信するステップをさらに備えることを特徴とする請求項１０に記載のデータ保全性証明方法。
【請求項２２】
請求項１から請求項９の何れかに記載のデータへのフィンガープリント付加方法によって、フィンガープリントが付加されたデータのデータ保全性検証方法であって、
第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するステップと、
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信するステップと、
Φ個のボックスを構築するステップと、
第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当てるステップと、
n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するステップと、
第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換して、変換済みロケータを生成するステップと、
変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成するステップと、
検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較するステップと、
比較結果が一致の場合に、データのデータ保全性を検証するステップと
を有することを特徴とするデータ保全性検証方法。
【請求項２３】
前記検証対象の変換済みスーパーブロックの知識証明は、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項２４】
前記検証対象の変換済みスーパーブロックの知識証明は、第１および第２の秘密鍵x、vにも基づいて生成されることを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項２５】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される、
prf5=((T1/x・W)v)，
（ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkと、データの識別子zMとを入力とするハッシュ値である。）
ことを特徴とする請求項２４に記載のデータ保全性検証方法。
【請求項２６】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項２５に記載のデータ保全性検証方法。
【請求項２７】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項２８】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式で表される、
prf5=((Tx+zM・W)v)，
（ここで、Tは変換済みフィンガープリント、Wは変換済みロケータを表し、k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。）
ことを特徴とする請求項２４に記載のデータ保全性検証方法。
【請求項２９】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項２８に記載のデータ保全性検証方法。
【請求項３０】
検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成され、
e(T,Yv,g2vzM)・e(W,
g2v)
（ここで、Yj=Yv、g2v=g2v、Y= g2v∈G2である。G2=<g2>は、G1=<g1>に加えてもう１つのグループG=<g>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。）
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される、
e(H,g2)=e(T,Yv・g2vzM)・e(W,g2v)
（ここで、Hは変換済みスーパーブロックの知識証明である。）
ことを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項３１】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項３０に記載のデータ保全性検証方法。
【請求項３２】
前記チャレンジデータが、検証加速因数ψを含み、
k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数３３】
であることを検証することを特徴とする請求項３０に記載のデータ保全性検証方法。
【請求項３３】
前記検証対象の変換済みスーパーブロックの知識証明は、以下の式として生成され、
e(T,Yv)・e(W,g2v)
（ここで、Yv=g2v/x、g2v=g2v、Y=g2v∈G2である。G2=<g2>は、G=<g>に加えてもう１つのグループG1=<g1>を有する有限循環グループであり、|G1|=|G2|=|G|=p（pは大きな素数）となる。e:G1×G2→gは、双線形のマップ関数である。Tは変換済みフィンガープリントを表し、Wは変換済みロケータを表す。k番目のスーパーブロックのロケータWkは、少なくともkとデータの識別子zMを入力とするハッシュ値である。xとvは、第１および第２の秘密鍵である。）
検証対象の変換済みスーパーブロックの知識証明は、以下の式により、変換済みスーパーブロックの知識証明と比較される、
e(H,g2)=e(T,Yv)・e(W,g2v)
（ここで、Hは変換済みスーパーブロックの知識証明である。）
ことを特徴とする請求項２３に記載のデータ保全性検証方法。
【請求項３４】
前記k番目のスーパーブロックのロケータWkが、データのファイル名とバージョン番号の少なくとも一方を含むことを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３５】
前記データの識別子zMが、前記データに従って変わることを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３６】
前記チャレンジデータが、検証加速因数ψを含み、
k個の乱数rk∈Z⊆Zp（ただし、k=1,2,…,ψ）を選択し、計算により
【数３４】
であることを検証することを特徴とする請求項３３に記載のデータ保全性検証方法。
【請求項３７】
前記チャレンジデータは、全n個のロケータの代わりに、何れのΛ個のロケータをデータ保全性検証のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項３８】
前記チャレンジデータは、反復因数ψをさらに備え、
ボックス構築から知識証明生成と検証対象知識証明との比較までのステップがψ回反復され、すべての比較結果が一致の場合にのみ、データのデータ保全性が検証されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項３９】
前記第１および第２の無作為性定義キーk1、k2と、スーパーブロック選択キー対(k3,Λ)は、検証器によって選択されることを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項４０】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項２２に記載のデータ保全性検証方法。
【請求項４１】
前記デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項４０に記載のデータ保全性検証方法。
【請求項４２】
データへのフィンガープリント付加装置であって、
データをN個のブロックMi（i=1,2,…,N）に分割し、nB個のブロックの各々を１つのスーパーブロックに結合してn=[N/nB]個のスーパーブロックを取得するスーバーブロック生成手段と、
有限循環グループG1=<g1>からnB個の要素hj（j=1,2,…, nB）を選択し、k番目のスーパーブロックのロケータWkと、選択されたnB個の要素hjと、第１の秘密鍵xとを使用して、k番目のスーパーブロック（k=1,2,…,n）のフィンガープリントTkを生成するフィンガープリント付加手段と
を備えることを特徴とするデータへのフィンガープリント付加装置。
【請求項４３】
前記nB個の要素hjは、第１の秘密鍵xに対応する公開鍵の一部であることを特徴とする請求項４２に記載のデータへのフィンガープリント付加装置。
【請求項４４】
前記nB個の要素hjは、hj=g1rj（rjは秘密鍵）を満足することを特徴とする請求項４２に記載のデータへのフィンガープリント付加装置。
【請求項４５】
データ保全性証明装置であって、
少なくとも第１の無作為性定義キーk1と第２の無作為性定義キーk2とから成るチャレンジデータを受信する受信手段と、
Φ個のボックスを構築し、第１の無作為性定義キーk1によって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、n個のフィンガープリントをΦ個のボックスに無作為に割り当て、n個のフィンガープリントの上記割り当てに基づいて、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを生成するパッケージ化手段と、
第２の無作為性定義キーk2によって定義された第２の無作為方法に従って、Φ個の割り当て済みスーパーブロックと対応する割り当て済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段と、
変換済みスーパーブロックの知識証明を生成する知識証明生成手段と
を備えることを特徴とするデータ保全性証明装置。
【請求項４６】
前記知識証明生成手段は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成することを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４７】
前記知識証明生成手段は、変換済みスーパーブロックの知識証明を、公開鍵と変換済みスーパーブロックに基づいて生成することを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４８】
前記チャレンジデータは、全n個のスーパーブロックと対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックと対応するフィンガープリントとをパッケージ化手段がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項４９】
前記チャレンジデータは、反復因数ψをさらに備え、
前記パッケージ化手段と、前記変換手段と、前記知識証明生成手段の動作がψ回反復され、１回の反復毎に１つの変換済みスーパーブロックの知識証明が、変換済みスーパーブロックHm（m=1,2,…,ψ）のm番目の知識証明として生成されることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５０】
前記チャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５１】
前記デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とが生成されることを特徴とする請求項５０に記載のデータ保全性証明装置。
【請求項５２】
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段をさらに備えることを特徴とする請求項４５に記載のデータ保全性証明装置。
【請求項５３】
データ保全性検証装置であって、
第１の無作為性定義キーk1と第２の無作為性定義キーk2の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段と、
変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段と、
Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、n個のロケータWkをΦ個のボックスに無作為に割り当て、n個のロケータの上記割り当てに基づいて、Φ個の割り当て済みロケータを生成するロケータパッケージ化手段と、
第２の無作為方法に従って、Φ個の割り当て済みロケータを無作為に変換し、変換済みロケータを生成し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段と、
検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器と、
比較結果が一致の場合に、データ保全性を検証する検証装置と
を備えることを特徴とするデータ保全性検証装置。
【請求項５４】
前記検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子zMと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５５】
前記検証対象知識証明生成手段は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵x、vにも基づいて生成することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５６】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、前記ロケータパッケージ化手段がデータ保全性検証のために全n個のロケータのうちどのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対(k3,Λ)をさらに備えることを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５７】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、反復因数ψをさらに備え、
前記ロケータパッケージ化手段と、前記検証対象知識証明生成手段と、前記比較器の動作がψ回反復され、すべての比較結果が一致の場合にのみ、前記検証手段がデータ保全性を検証することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５８】
前記チャレンジデータ生成・送信手段によって生成されるチャレンジデータは、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含むことを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項５９】
前記チャレンジデータ生成・送信手段は、デジタル署名付きタイムスタンプから、第１および第２の無作為性定義キーk1、k2の少なくとも一方と、スーパーブロック選択キーk3とを決定することを特徴とする請求項５３に記載のデータ保全性検証装置。
【請求項６０】
データ保全性検証システムであって、
請求項４５から請求項５２の何れかに記載のデータ保全性証明装置と、請求項５３から請求項５９の何れかに記載のデータ保全性検証装置とを備えることを特徴とするデータ保全性検証システム。
【請求項６１】
請求項４５から請求項５２の何れかに記載のデータへのフィンガープリント付加装置をさらに備えることを特徴とする請求項６０に記載のデータ保全性検証システム。
【請求項６２】
前記データへのフィンガープリント付加装置は、データ保全性検証装置としても使用されることを特徴とする請求項６１に記載のデータ保全性検証システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００９−１８７５３７（Ｐ２００９−１８７５３７Ａ）
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−３２４０３９（Ｐ２００８−３２４０３９）
【出願日】平成２０年１２月１９日（２００８．１２．１９）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【出願番号】特願２００８−３２４０３９（Ｐ２００８−３２４０３９）
【出願日】平成２０年１２月１９日（２００８．１２．１９）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]