(57)【要約】      （修正有）【課題】増分的証明可能データ保全性（ＩＰＤＩ）検証方法を提供する。【解決手段】最初にデータのフィンガープリントがクライアントで生成され、そのフィンガープリントがデータと共にアーカイブに送信され、続いて、必要が生じたときにクライアントがデータの保全性を判定するための「チャレンジデータ」をアーカイブに送信し、アーカイブが受信したフィンガープリントを使用してデータの保全性を証明し、最後に、クライアントが「チャレンジデータ」への応答として返されたアーカイブからの出力に基づいてデータの保全性を検証する。さらに、ＩＰＤＩスキームでは、すでにフィンガープリントが付加され外注されたデータファイルに増分データを安全に追加することができる。【選択図】図２
2010166549.tif 000002
【特許請求の範囲】
【請求項１】
フィンガープリントデータ生成方法であって、
データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割するステップと、
ｎＢ個のブロックの各々と１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合して、ｎ＝｜Ｎ／ｎＢ｜個のスーパーブロックを取得するステップと、
有限循環グループＧ１＝＜ｇ１＞からｎＢ＋１個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択するステップと、
ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するステップと
を有することを特徴とするフィンガープリントデータ生成方法。
【請求項２】
ｎＢ＋１個の要素ｈｊは、第１の秘密鍵ｘに対応する公開鍵の一部であることを特徴とする請求項１に記載のフィンガープリントデータ生成方法。
【請求項３】
ｎＢ＋１個の要素ｈｊは、ｈｊ＝ｇ１ｒｊ（ｒｊは秘密鍵）を満足することを特徴とする請求項１に記載のフィンガープリントデータ生成方法。
【請求項４】
ｋ番目のスーパーブロックのフィンガープリントＴｋは、
【数２１】
2010166549.tif 000023
ｚＭはデータの識別子、
の式に従って生成されることを特徴とする請求項１に記載のフィンガープリントデータ生成方法。
【請求項５】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋを入力とするハッシュ値であることを特徴とする請求項４に記載のフィンガープリントデータ生成方法方法。
【請求項６】
ｋ番目のスーパーブロックのフィンガープリントＴｋは、
【数２２】
2010166549.tif 000024
の式に従って生成されることを特徴とする請求項１に記載のフィンガープリントデータ生成方法方法。
【請求項７】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋと、データの識別子ｚＭとを入力とするハッシュ値であることを特徴とする請求項６に記載のフィンガープリントデータ生成方法方法。
【請求項８】
既存のデータの最後尾に新たなデータが付加された際に、
新たなデータをＮＮＥＷ個のブロックＭｉＮＥＷ（ｉ＝Ｎ＋１，Ｎ＋２，．．．，Ｎ＋ＮＮＥＷ）に分割するステップと、
ｎＢ個のブロックの各々と１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合して、ｎＮＥＷ＝｜ＮＮＥＷ／ｎＢ｜個のスーパーブロックを取得するステップと、
ｋ番目（ｋ＝ｎ＋１，ｎ＋２，．．．，ｎ＋ｎＮＥＷ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するステップを有することを特徴とする請求項１に記載のフィンガープリントデータ生成方法方法。
【請求項９】
仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'が、
Ｍ（ｋ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＥＦ（ｋ，ｚＭ，ＦＮＭ），
ｚＭはデータの識別子、ＦＮＭはデータのファイル識別子、ｐｒｆＶＥＦ（・）は疑似ランダム関数
として生成されることを特徴とする請求項１から請求項８の何れかに記載のフィンガープリントデータ生成方法方法。
【請求項１０】
仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'が、
Ｍ（ｋ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＥＦ（ｋ，ｚＭ，ＦＮＭ，｛Ｍ（ｋ−１）・ｎＢ＋ｊ｝），  ｊ＝１，２，．．．，ｎＢ
ｚＭはデータの識別子、ＦＮＭはデータのファイル識別子、｛Ｍ（ｋ−１）・ｎＢ＋ｊ｝は、仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'と共に１つのスーパーブロックに結合されるｎＢ個のブロックのデータ集合、ｐｒｆＶＥＦ（・）は疑似ランダム関数
として生成されることを特徴とする請求項１から請求項８の何れかに記載のフィンガープリントデータ生成方法方法。
【請求項１１】
フィンガープリントデータ生成装置であって、
生成される各スーパーブロックにつき１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'を生成する仮想ファイルブロック生成手段と、
データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割し、ｎＢ個のブロックの各々と前記仮想ファイルブロック生成手段からの仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合してｎ＝｜Ｎ／ｎＢ｜スーパーブロックを取得するスーパーブロック生成手段と、
有限循環グループＧ１＝＜ｇ１＞からｎＢ＋１個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択し、ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するフィンガープリントデータ生成手段と
を備えることを特徴とするフィンガープリントデータ生成装置。
【請求項１２】
ｎＢ＋１個の要素ｈｊは、第１の秘密鍵ｘに対応する公開鍵の一部であることを特徴とする請求項１１に記載のフィンガープリントデータ生成装置。
【請求項１３】
ｎＢ＋１個の要素ｈｊは、ｈｊ＝ｇ１ｒｊ（ｒｊは秘密鍵）を満足することを特徴とする請求項１１に記載のフィンガープリントデータ生成装置。
【請求項１４】
前記フィンガープリントデータ生成手段は、
ｋ番目のスーパーブロックのフィンガープリントＴｋを、
【数２３】
2010166549.tif 000025
ｚＭはデータの識別子、
の式に従って生成することを特徴とする請求項１１に記載のフィンガープリントデータ生成装置。
【請求項１５】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋを入力とするハッシュ値であることを特徴とする請求項１４に記載のフィンガープリントデータ生成装置。
【請求項１６】
前記フィンガープリントデータ生成手段は、
ｋ番目のスーパーブロックのフィンガープリントＴｋを、
【数２４】
2010166549.tif 000026
の式に従って生成することを特徴とする請求項１１に記載のフィンガープリントデータ生成装置。
【請求項１７】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋと、データの識別子ｚＭとを入力とするハッシュ値であることを特徴とする請求項１６に記載のフィンガープリントデータ生成装置。
【請求項１８】
既存のデータの最後尾に新たなデータが付加された際に、
前記仮想ファイルブロック生成手段は、生成される各スーパーブロックにつき１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'を生成し、
前記スーパーブロック生成手段は、新たなデータをＮＮＥＷ個のブロックＭｉＮＥＷ（ｉ＝Ｎ＋１，Ｎ＋２，．．．，Ｎ＋ＮＮＥＷ）に分割し、
ｎＢ個のブロックの各々と１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合して、ｎＮＥＷ＝｜ＮＮＥＷ／ｎＢ｜個のスーパーブロックを取得し、
前記フィンガープリントデータ生成手段は、ｋ番目（ｋ＝ｎ＋１，ｎ＋２，．．．，ｎ＋ｎＮＥＷ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成することを特徴とする請求項１１に記載のフィンガープリントデータ生成装置。
【請求項１９】
前記フィンガープリントデータ生成手段は、
仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'を、
Ｍ（ｋ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＥＦ（ｋ，ｚＭ，ＦＮＭ），
ｚＭはデータの識別子、ＦＮＭはデータのファイル識別子、ｐｒｆＶＥＦ（・）は疑似ランダム関数
として生成することを特徴とする請求項１１又は請求項１８に記載のフィンガープリントデータ生成装置。
【請求項２０】
前記フィンガープリントデータ生成手段は、
仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'を、
Ｍ（ｋ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＥＦ（ｋ，ｚＭ，ＦＮＭ，｛Ｍ（ｋ−１）・ｎＢ＋ｊ｝），  ｊ＝１，２，．．．，ｎＢ
ｚＭはデータの識別子、ＦＮＭはデータのファイル識別子、｛Ｍ（ｋ−１）・ｎＢ＋ｊ｝は、仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'と共に１つのスーパーブロックに結合されるｎＢ個のブロックのデータ集合、ｐｒｆＶＥＦ（・）は疑似ランダム関数
として生成することを特徴とする請求項１１又は請求項１８に記載のフィンガープリントデータ生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージネットワークのセキュリティ分野に関し、特に、増分的証明可能データ保全性（ＩＰＤＩ）検証方法、装置、およびシステムに関する。
【背景技術】
【０００２】
インターネットの世界では、これまでローカルストレージで行っていたデータの保管を、世界規模の固定ストレージサービスに外注する動きが急速に高まっている。Ａｍａｚｏｎ  Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｉｃｅ（Ａｍａｚｏｎ  Ｓ３）（非特許文献１：Ａｍａｚｏｎ  Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｉｃｅ（Ａｍａｚｏｎ  Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３）は、インターネット上のこうしたストレージシステムの１つである。Ａｍａｚｏｎ  Ｓ３は、データの格納と取り出しに利用できるウェブサービスインターフェースを提供する。Ａｍａｚｏｎ  Ｓ３は世界規模でビジネスクラスのサービスでありながら、その料金は非常に安価であり、利用料は記憶容量１ＧＢ当たり月額０．１５米ドル、全データの転送入力料は１ＧＢ当たり０．１０米ドル、データの転送出力料は最初の１０  ＴＢまで１ＧＢ当たり月額０．１８米ドルである。無料の世界規模ストレージサービスを希望する企業向けにも、いくつかのサービスが提供されている。ＭｅｄｉａＭａｘ（非特許文献２：ＭｅｄｉａＭａｘ  Ｆｒｅｅ  Ｏｎｌｉｎｅ  Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ）が２５  ＧＢの無料オンラインストレージを提供しており、Ｇｍａｉｌ  Ｆｉｌｅ  Ｓｙｓｔｅｍ（非特許文献３：Ｇｍａｉｌ  Ｄｒｉｖｅ  Ｓｈｅｌｌ  Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ）プロジェクトではフリーＧｍａｉｌアカウントが１つの連続した無料ネットワークストレージ領域に変換された。
【０００３】
これらの公開された記憶領域サービスを利用すれば、クライアントはローカルな記憶サブシステムを持たずに、インターネット上でいつでも、どこからでもデータを取り出すことが可能になる。この大きな魅力によって産業界での利用が進み、今ではストレージのアウトソーシングが必然的な流れとなっている。
【０００４】
ＩＥＴＦ  Ｎｅｔｗｏｒｋ  ＷＧはこの動向を受けて標準化に取り組み、その結果として、ＲＦＣ  ４８１０  “Ｌｏｎｇ−Ｔｅｒｍ  Ａｒｃｈｉｖｅ  Ｓｅｒｖｉｃｅ  Ｒｅｑｕｉｒｅｍｅｎｔ”（長期アーカイブサービス要件）が発行された（非特許文献４：ＲＦＣ  ４８１０，Ｌｏｎｇ−Ｔｅｒｍ  Ａｒｃｈｉｖｅ  Ｓｅｒｖｉｃｅ  Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ  Ｎｅｔｗｏｒｋ  ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ）。ＲＦＣ  ４８１０は、長期間のデータ保管を目的とする長期アーカイブサービスに関する要件を定めている。長期アーカイブサービスの主な目的は、データの存在、保全性、および発信元の否認防止をサポートすることである。ＲＦＣ  ４８１０で述べられているように、長期アーカイブサービスは、データを受け入れた時点からデータ保管期間の終了時点まで、データ保全性の実証に使用できる証拠を提供できなければならない。
【０００５】
クライアントストレージのデータの保管をアーカイブサービスに委託する場合は、データの送信とデータの取り込みという２つのステップが必要となる。データ保全性の検証を目的とする単純な解決策では、データはアーカイブから取り出される。しかし、リモートアーカイブからクライアント検証器までを高帯域で接続することは現時点では実用的ではなく、近い将来にも同様である。特にモバイルクライアントでは、快適な高帯域接続を実現することは困難である。さらに、ＲＦＣ  ４８１０にもあるように、サードパーティ検証器がユーザデータの保全性を検査するケースもある。この場合は、ユーザデータのプライバシ侵害を防止するために、サードパーティ検証器がユーザデータにアクセスできないようにする必要がある。従来技術では、アーカイブから取り出さずにデータの保全性を検証するための方策として、図１に示す３つのステップから成る動作モデルが採用されている。説明の一般性を損なわず、かつ表記上の煩雑化を避けるため、以下では、クライアント（すなわち、データ所有者）がユーザデータ保全性の検証器であるケースを例にとって説明する。しかし、前述したように、実際の検証器はデータ所有者以外のサードパーティのこともある。
【０００６】
ステップ０において、クライアントによってデータのデジタルフィンガープリントが生成され、データと共にアーカイブに送信される。アーカイブには、データそのものに加えて、データのフィンガープリントも格納する必要がある。ステップ１において、クライアントがアーカイブに、データ保全性に関するチャレンジデータを送信する。アーカイブは、データのコンテンツ、データのフィンガープリント、クライアントのチャレンジデータのすべてを利用して、データ保全性証明を計算する。計算結果はクライアントに送り返され、ステップ２の検証に利用される。ステップ１とステップ２は、データの保管期間が終了するまで複数回にわたって反復することができる。
【０００７】
上記の動作モデルを使用する場合に、証明可能データ保全性問題の技術的解決策において考慮すべき主な要因を以下に示す。
（Ｉ）  クライアントがデータのフィンガープリントを生成する際の所要時間
（ＩＩ）  データのフィンガープリントが消費するアーカイブ記憶領域のサイズ
（ＩＩＩ）  検証器がアーカイブに送信するチャレンジデータのサイズ
（ＩＶ）  アーカイブがデータ保全性証明を計算する際の所要時間
（Ｖ）  アーカイブが検証器に送信するデータ保全性証明のサイズ
（ＶＩ）  検証器がデータ保全性証明を検査する際の所要時間
（ＶＩＩ）  データの増分的変化に対処する能力
【０００８】
データ保全性問題に一見対処しているように見える解決策はある。この解決策では、データ所有者がまずデータを複数の断片に分割し、各断片について、メッセージ認証コード（ＭＡＣ）を事前計算する。そして、検証器（データ所有者かサードパーティかを問わない）がデータ保全性証明を必要とするときには、アーカイブサービスから無作為に選択されたいくつかの断片を取り出し、各断片のＭＡＣを再計算して比較する。
【０００９】
Ｄｅｓｗａｒｔｅ  ｅｔ  ａｌ．（非特許文献５：Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ  ｉｎｔｅｇｒｉｔｙ  ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ  Ｐｒｏｃ．ｏｆ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｔｅｇｒｉｔｙ  ａｎｄ  Ｉｎｔｅｒｎａｌ  ｃｏｎｔｒｏｌ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ｓｙｓｔｅｍｓ（ＩＩＣＩＳ'０３），２００３）とＦｉｌｈｏ  ｅｔ  ａｌ．（非特許文献６：Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ  Ｄａｔａ  Ｐｏｓｓｅｓｓｉｏｎ  ａｎｄ  Ｕｎｃｈｅａｔａｂｌｅ  Ｄａｔａ  Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ）では、ＲＳＡベースのハッシュ関数を使用して、アーカイブが格納するファイルの正確性を検証する方法が提案されている。
【００１０】
ごく最近では、Ａｔｅｎｉｅｓｅ  ｅｔ  ａｌ．（非特許文献７：Ｇ．Ａｔｅｎｉｅｓｅ，Ｒ．Ｂｕｒｎｓ，Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｈｅｒｒｉｎｇ，Ｌ．Ｋｉｓｓｎｅｒ，Ｚ．Ｐｅｔｅｒｓｏｎ，Ｄ．Ｓｏｎｇ，Ｐｒｏｖａｂｌｅ  Ｄａｔａ  Ｐｏｓｓｅｓｓｉｏｎ  ａｔ  Ｕｎｔｒｕｓｔｅｄ  Ｓｔｏｒｅｓ（信頼されない記憶装置における証明可能データの保有）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２０２．ｐｄｆ）において、ＲＳＡベースの証明可能データ保有スキームとして、Ｓ−ＰＤＰスキーム（Ｓは「サンプリング」の略）が提案されている。この提案における「サンプリング」とは、クライアントがデータの一部を無作為に選択し、アーカイブに対して、この無作為に選択されたデータが健全な状態にある（すなわち、選択されたデータのデータ保全性が保たれている）という証拠を示すよう要求することである。Ｓ−ＰＤＰスキームは、ファイル全体のべき乗を必要とせず、通信の複雑性が一定であるため、従来技術の中で最も効率的である。
【００１１】
単純な解決策の短所は、通信の複雑性がクエリー対象のデータサイズに線形に比例することである。さらに、サードパーティ検証器の場合には、データ所有者のプライバシ侵害防止の観点から、ユーザデータを検証器に送ることは禁じられる。アーカイブサービスからデータを取り出さないようにするための方策としては、複数の秘密鍵を選択し、データに対して複数キーのハッシュＭＡＣを事前に計算することで、単純な解決策を改良するという方法がある。これにより、検証器は秘密鍵をアーカイブサービスに都度開示し、新たなキーを付加したハッシュＭＡＣを要求して比較することが可能になる。しかし、この方法では、各データを検証できる回数は、事前に設定された秘密鍵の個数によって制限される。そのため、キーを使い果たした場合は、新たなＭＡＣを計算するために、アーカイブサービスからデータを取り出すことが不可避となる。
【００１２】
また、非特許文献５および６の提案には、アーカイブがファイル全体をべき乗しなければならないという短所がある。参考として２０４８ビットのＲＳＡ係数を例にとると、１つの指数を完全にべき乗するには、Ｉｎｔｅｌ  Ｃｏｒｅ  Ｄｕｏ  ２．１６  ＧＨｚプロセッサ上で６１．３２５ミリ秒を要する。そのため、べき乗の所要時間は１メガバイト当たり２５１．３秒となり、６４ＭＢのファイルの保全性をテストする場合には、アーカイブがクライアントにデータ保全性証明を送信できるまでに１６０８３．８秒もかかってしまうことになる。
【００１３】
Ｓ−ＰＤＰスキームは、その設計目標（すなわち、サンプリング）がデータ所有者には無意味な場合があるという問題を抱える。Ｓ−ＰＤＰスキームは、サンプリングによって、高い検出確率において遭遇されるファイルブロックの破壊の問題に対処する。例えば、非特許文献７では、ファイルブロックの破壊が１％の場合に９９％の検出確率を達成する方法が説明されている。しかし、１ビットのエラーも許容できないファイルタイプは多い。例えば、符号復号器の構成パラメータが格納されるメディアファイルの先頭部分が失われると、処理が困難になる。また、暗号化されたファイルに埋め込まれた（公開鍵で暗号化された）対称暗号キーが壊れると、誰も普通テキストを回復できない無意味な暗号文となってしまう。概してデータ所有者は１００％のデータ安全性を要求し、どんな理由があろうとも妥協を許容しない。Ｓ−ＰＤＰスキームにはもう一つ、サードパーティ検証（いわゆる、「公的検証可能性」）システムで採用するには、あまりにも効率が低すぎるという問題もある。Ｓ−ＰＤＰスキームを使用した公的検証を可能とするためには、１つのファイルブロックをＲＳＡ公開鍵ｅよりも小さくする必要がある。例えば、２０４８ビットのＲＳＡ係数の場合、公開鍵ｅは１０２４ビット程度でしかない。そのため、公的検証が可能なＳ−ＰＤＰスキームによる解決策では、１つのファイルを複数の１０２４ビットファイルブロックに論理的に分割しなければならない。その結果生じるファイルブロックは膨大な数に上り、その一つひとつにタグを生成する必要がある。これにより、タグのサイズはファイルそのものの２倍となり、クライアントがファイルにタグ付けするための費用を考慮すると、とうてい実用に資するものとはいえない。
【００１４】
本願の出願人に付与された中国の先行出願（特許文献１（中国特許第２００８１０１６５８６４．３号））では、ペアリングベースの証明可能データ保全性（ＰＤＩ）スキームが提案されている。先行出願におけるこのＰＤＩスキームは上記の要件（Ｉ）〜（ＶＩ）を十分に満たしているが、要件（ＶＩＩ）は満たしていない。すなわち、このＰＤＩスキームは外注されたデータへの増分的変化に対応することができない。ここでいう増分的変化とは、データファイルに新たなデータセグメントが追加されることを意味する。このＰＤＩスキームでは、増分的変化を許容することはセキュリティ違反となる。つまり、一旦データファイルが前処理され（このＰＤＩスキームの場合は、フィンガープリントの付加）、外注され（すなわち、データの前処理に使用された鍵がサードパーティ検証器に開示される）た後に、このＰＤＩスキームがファイルへの新たなデータセグメントの追加を受け入れると、十分なセキュリティが確保できなくなるのである。
【００１５】
上記７つの要件（Ｉ）〜（ＶＩＩ）のすべてを満たすことのできる関連技術は存在しない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】中国特許第２００８１０１６５８６４．３号
【非特許文献】
【００１７】
【非特許文献１】Ａｍａｚｏｎ  Ｓｉｍｐｌｅ  Ｓｔｏｒａｇｅ  Ｓｅｒｖｉｃｅ（Ａｍａｚｏｎ  Ｓ３），ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｓ３
【非特許文献２】ＭｅｄｉａＭａｘ  Ｆｒｅｅ  Ｏｎｌｉｎｅ  Ｓｔｏｒａｇｅ，ｈｔｔｐ：／／ｗｗｗ．ｍｅｄｉａｍａｘ．ｃｏｍ
【非特許文献３】Ｇｍａｉｌ  Ｄｒｉｖｅ  Ｓｈｅｌｌ  Ｅｘｔｅｎｓｉｏｎ，ｈｔｔｐ：／／ｗｗｗ．ｖｉｋｓｏｅ．ｄｋ／ｃｏｄｅ／ｇｍａｉｌ．ｈｔｍ
【非特許文献４】ＲＦＣ  ４８１０，Ｌｏｎｇ−Ｔｅｒｍ  Ａｒｃｈｉｖｅ  Ｓｅｒｖｉｃｅ  Ｒｅｑｕｉｒｅｍｅｎｔ、ＩＥＴＦ  Ｎｅｔｗｏｒｋ  ＷＧ．ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４８１０．ｔｘｔ
【非特許文献５】Ｙ．Ｄｅｓｗａｒｔｅ，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ａ．Ｓａｉｄａｎｅ，Ｒｅｍｏｔｅ  ｉｎｔｅｇｒｉｔｙ  ｃｈｅｃｋｉｎｇ（リモート保全性検査），Ｉｎ  Ｐｒｏｃ．ｏｆ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｔｅｇｒｉｔｙ  ａｎｄ  Ｉｎｔｅｒｎａｌ  ｃｏｎｔｒｏｌ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ｓｙｓｔｅｍｓ（ＩＩＣＩＳ'０３），２００３
【非特許文献６】Ｄ．Ｌ．Ｇ．Ｆｉｌｈｏ、Ｐ．Ｓ．Ｌ．Ｍ．Ｂａｒｅｔｔｏ．Ｄｅｍｏｎｓｔｒａｔｉｎｇ  Ｄａｔａ  Ｐｏｓｓｅｓｓｉｏｎ  ａｎｄ  Ｕｎｃｈｅａｔａｂｌｅ  Ｄａｔａ  Ｔｒａｎｓｆｅｒ．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００６／１５０．ｐｄｆ
【非特許文献７】Ｇ．Ａｔｅｎｉｅｓｅ，Ｒ．Ｂｕｒｎｓ，Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｈｅｒｒｉｎｇ，Ｌ．Ｋｉｓｓｎｅｒ，Ｚ．Ｐｅｔｅｒｓｏｎ，Ｄ．Ｓｏｎｇ，Ｐｒｏｖａｂｌｅ  Ｄａｔａ  Ｐｏｓｓｅｓｓｉｏｎ  ａｔ  Ｕｎｔｒｕｓｔｅｄ  Ｓｔｏｒｅｓ（信頼されない記憶装置における証明可能データの保有）．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２０２．ｐｄｆ
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述した関連技術における短所を考慮して、本発明は、特許文献１（中国特許第２００８１０１６５８６４．３号（ここにその開示全体を援用する）に開示されたＰＤＩスキームをベースとし、関連技術（ＰＤＩスキームに限定されない）が抱える増分的変化の問題を克服する、増分的証明可能データ保全性（ＩＰＤＩ）検証方法を提案する。
【００１９】
先行出願で提案されたＰＤＩスキームによれば、フィンガープリントデータ生成方法方法であって、データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割するステップと、ｎＢ個のブロックの各々を１つのスーパーブロックに結合してｎ＝｜Ｎ／ｎＢ｜個のスーパーブロックを取得するステップと、有限循環グループＧ１＝＜ｇ１＞からｎＢ個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択するステップと、ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するステップとを備えることを特徴とする、フィンガープリントデータ生成方法方法が提供される。
【００２０】
新たに提案されるＩＰＤＩスキームは、主に「仮想ファイルブロック（ＶＦＢ）」と呼ばれる概念を導入した点で、ＰＤＩスキームと異なる。ＩＰＤＩスキームでは、ＶＦＢは「真」のファイルブロックとみなされ、ｎ＝｜Ｎ／ｎＢ｜個のスーパーブロックのうちの各スーパーブロックは、ｎＢ個のデータブロックと１個の仮想ファイルブロック（ＶＦＢ）とで構成される。
【００２１】
したがって、新たに提案されるＩＰＤＩスキームによれば、フィンガープリントデータ生成方法方法であって、データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割するステップと、ｎＢ個のブロックの各々と１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合してｎ＝｜Ｎ／ｎＢ｜個のスーパーブロックを取得するステップと、有限循環グループＧ１＝＜ｇ１＞からｎＢ＋１個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択するステップと、ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するステップとを備えることを特徴とする、フィンガープリントデータ生成方法方法が提供される。
【００２２】
ｎＢ＋１個の要素ｈｊは、第１の秘密鍵ｘに対応する公開鍵の一部であるのが望ましい。
【００２３】
ｎＢ＋１個の要素ｈｊは、ｈｊ＝ｇ１ｒｊ（ｒｊは秘密鍵）を満足するのが望ましい。
【００２４】
ｋ番目のスーパーブロックのフィンガープリントＴｋは、以下の式に従って生成されるのが望ましい。
【数１】
2010166549.tif 000003
ここで、ｚＭはデータの識別子である。
【００２５】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋを入力とするハッシュ値であるのがさらに望ましい。
【００２６】
ｋ番目のスーパーブロックのフィンガープリントＴｋは、以下の式に従って生成されるのが望ましい。
【数２】
2010166549.tif 000004
【００２７】
ｋ番目のスーパーブロックのロケータＷｋは、少なくともｋと、データの識別子ｚＭとを入力とするハッシュ値であるのがさらに望ましい。
【００２８】
本発明の第２の態様によれば、フィンガープリントデータ生成装置であって、生成される各スーパーブロックにつき１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'を生成する仮想ファイルブロック生成手段と、データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割し、ｎＢ個のブロックの各々と仮想ファイルブロック生成手段からの仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合してｎ＝｜Ｎ／ｎＢ｜スーパーブロックを取得するスーパーブロック生成手段と、有限循環グループＧ１＝＜ｇ１＞からｎＢ＋１個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択し、ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するフィンガープリントデータ生成手段とを備えることを特徴とするフィンガープリントデータ生成装置が提供される。
【００２９】
ｎＢ＋１個の要素ｈｊは、第１の秘密鍵ｘに対応する公開鍵の一部であるのが望ましい。
【００３０】
ｎＢ＋１個の要素ｈｊは、ｈｊ＝ｇ１ｒｊ（ｒｊは秘密鍵）を満足するのが望ましい。
【００３１】
先行出願で提案されたＰＤＩスキームにより、圧倒的に高い確率（例えば、１−２−６４）でデータ保全性を確保することができる。従来技術は（１）データ保全性がビット単位で保証される、（２）クライアントがアーカイブに送信するチャレンジデータのサイズが一定である、（３）アーカイブがクライアントに送信するデータ保全性証明のサイズが一定である、という効果を実現するのに対し、先願のＰＤＩスキームは以下の４つの主要な利点を有する。
（Ｉ）  クライアントがデータのフィンガープリントを生成する速度が最速である。
（ＩＩ）  アーカイブがクライアントのチャレンジデータへの応答を生成する速度が最速である。
（ＩＩＩ）  クライアントがアーカイブの応答を検証する速度が最速である。
（ＩＶ）  検証器はサードパーティ検証器であってもよく、上記３つの利点（Ｉ）〜（ＩＩＩ）のすべてが同様に実現される。しかも、フィンガープリントのサイズが最小である。
【００３２】
以下では、具体例として６４ＭＢのデータファイルについて説明する。セキュリティ強度は２０４８ビットのＲＳＡ署名相当に設定され、Ｉ＝６４である。クライアントはＩｎｔｅｌ  Ｃｏｒｅ  Ｄｕｏ  ２．１６ＧＨｚプロセッサ、アーカイブはＩｎｔｅｌ  Ｑｘ６７００  Ｃｏｒｅ２  Ｑｕａｄ  ２．６６  ＧＨｚプロセッサとすると、ＰＤＩスキームにおいては、クライアントがファイルへのフィンガープリントの付加に要する時間は１２．７秒間、アーカイブが変換済みフィンガープリントと変換済みスーパーブロックの知識証明の生成に要する時間は１．４秒間、クライアントが知識証明の検証に要する時間は約０．４秒間である。これらの時間値は、従来技術のＲＳＡベーススキームが達成可能な理論的下限よりもさらに低い。
【００３３】
新たに提案されるＩＰＤＩスキームは、すでにフィンガープリントが付加され外注されたデータファイルに増分データを安全に追加することを可能にするという利点を有する。ＩＰＤＩスキームは、記憶容量の消費量を増大させずに、全７つの要件（Ｉ）〜（ＶＩＩ）を満たすことができる。
【図面の簡単な説明】
【００３４】
本発明の上記および他の目的、特徴、利点は、本発明の非限定的な実施例に関する以下の説明と添付図面とを参照することにより、さらに明らかになるであろう。
【図１】データ保全性証明における動作モデルを示す。
【図２】本発明によるデータ保全性証明方法（アトミック証明手順）とデータ保全性検証方法（アトミック検証手順）のフローチャートを示す。
【図３】先願で提案されたＰＤＩスキームにおけるデータの論理ビューである。
【図３ａ】新たに提案されるＩＰＤＩスキームにおけるデータの論理ビューである。
【図４】データ保全性証明における他の動作モデルを示す。
【図５】データ保全性証明におけるさらに他の動作モデルを示す。
【図６】本発明を実装したクライアント１４００のブロック図を示す。
【図７】本発明を実装したアーカイブ１５００のブロック図を示す。
【図８】本発明を実装した検証器１６００のブロック図を示す。
【発明を実施するための形態】
【００３５】
次に、図面を参照しながら本発明について説明する。以下の説明では、説明の便宜上いくつかの具体的な実施例を使用しているが、これらは本発明を限定するものではなく、例示にすぎない。また、本発明の理解が多少曖昧になる可能性はあるが、従来技術の構成・構造の説明は省略する。
（原理の説明）
【００３６】
本明細書において提示する増分的証明可能データ保全性（ＩＰＤＩ）スキームは、従来技術が抱えるすべての問題を克服するのみならず、どの従来技術にも勝る性能を示す。
【００３７】
ＩＰＤＩスキームは、基本的には、図１に示す動作モデルに従った以下の３つのステップで構成される。
【００３８】
ステップ０'：
ＩＰＤＩスキームでは、有限循環グループＧ１＝＜ｇ１＞が必要とされるが、このＧ１は楕円曲線上の有限循環グループであるのが望ましい。本発明の開示では、その全体を通して、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。クライアントは、秘密鍵ｘとそれに対応する公開鍵とを有する。
【００３９】
クライアントは、データファイルをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割する。ｎＢ個の各ブロックと１個の仮想ファイルブロックＭ（ｋ−１）・ｎＢ＋'＋０'が１つのスーパーブロックに結合される。したがって、データはｎ＝｜Ｎ／ｎＢ｜個のスーパーブロックに分割される。データファイルの長さがｎ個のスーパーブロックに必要な長さに満たない場合は、データファイルはゼロを使用して論理的に埋められる。ここでは、論理的には、スーパーブロック内において仮想ファイルブロックはｎＢ個のブロックの前に配置される。しかし、仮想ファイルブロックはスーパーブロック内においてｎＢ個のブロックの後に配置することも、あるいはスーパーブロック内の他の位置を指定して配置することもできる。ここでは、下付文字「＋０」は、スーパーブロック内の最初の真のファイルブロックの直前のブロックを表すために使用されている。
【００４０】
クライアントは、各データファイルに関して、Ｇ１のｎＢ＋１個の要素ｈｉ（ｉ＝＋０，１，２，．．．，ｎＢ）を作成する。好適なケースでは、クライアントは、ｈｉ＝ｇ１ｒｉとなるようにｒｉを選択し、ｒｉを秘匿しておく。要素ｈｉは、クライアントの公開鍵の一部とし、データファイルから独立させるのがさらに望ましい。
【００４１】
クライアントは自身の秘密鍵と上記ｎＢ＋１個の要素ｈｉを利用して、すべてのスーパーブロックのフィンガープリントを生成する。例えば、ｉ番目のスーパーブロックのフィンガープリントは、以下のような形式をとる。
【数３】
2010166549.tif 000005
【００４２】
ここで、ロケータＷｉは、少なくともｉを入力とするハッシュ値である。また、データファイルのファイル名やバージョン番号などを入力として追加することもできる。ｚＭは、データファイルに対して選択された固有な識別子である。例えば、あるデータファイル集合には識別子ｚＭ、別のデータファイル集合には別の識別子ｚＭというように選択する。あるいは、フィンガープリントを以下の式で計算することもできる。
【数４】
2010166549.tif 000006
【００４３】
ここで、ロケータＷｉはｉとｚＭとを入力とする。好適なケースでは、クライアントは、ｒｉの値と、ｈｉ＝ｇ１ｒｉであるという知識を有する。したがって、
【数５】
2010166549.tif 000007
を
【数６】
2010166549.tif 000008
に置換することにより、クライアントはｒｉの知識を利用してフィンガープリント付加処理を迅速化することができる。
【００４４】
ステップ０'の結果、クライアントは、ｎ個のスーパーブロックに対してｎ個のフィンガープリントを取得する。クライアントは、データファイルとｎＢ個の要素ｈｉと共に、すべてのフィンガープリントをアーカイブに送信する。ｎＢ個の要素ｈｉをクライアントの公開鍵の一部とする好適なケースでは、アーカイブはこれらの要素を公開鍵ディレクトリなどから事前に取得することもできる。その場合は、これらの要素をデータファイルと共に送信する必要はない。
【００４５】
ステップ１'：
クライアントは、データの保全性を判定するための「チャレンジデータ」をアーカイブに送信する。
【００４６】
アーカイブは、クライアントから受信したチャレンジデータに基づいて、アトミック証明手順を数回（例：ψ回）実行する必要がある。
【００４７】
アーカイブは、各アトミック証明手順において、まずΦ＝２φ個のボックスを構築し、論理的かつ無作為にｎ個のフィンガープリントをこれらのボックスに割り当てる。個数Ｆと無作為性は、クライアントから受信した「チャレンジデータ」によって決まる。１つのフィンガープリントの配置先は、必ず１つのボックスに限定しなければならない。１つのフィンガープリントを１つのスーパーブロックに対応させることを念頭に全ｎ個のフィンガープリントをボックスに配置すると、その結果として、各ボックスには１つの「充てん済みスーパーブロック」と、そのボックスに割り当てられたフィンガープリントに基づいて生成された「充てん済みスーパーブロック」の「充てん済みフィンガープリント」とが存在することになる。例えば、λ番目のボックスに、η番目およびω番目のスーパーブロックに関連する２つのフィンガープリントのみが配置されるケースであれば、このボックスの「充てん済みスーパーブロック」はＭλｊ＝Ｍη＊ｎＢ＋ｊ＋Ｍω＊ｎＢ＋ｊ，（ｊ＝＋０，１，２，．．．，ｎＢ）を含み、「充てん済みスーパーブロック」の「充てん済みフィンガープリント」はＴλ＝Ｔη・Ｔωとなる。
【００４８】
次に、アーカイブは、すべてのボックスの「充てん済みスーパーブロック」と「充てん済みフィンガープリント」に別の無作為性を適用することにより、１つの「変換済みスーパーブロック」と、その「変換済みスーパーブロック」の１つの「変換済みフィンガープリント」を生成する。この無作為性もまた、クライアントから受信した「チャレンジデータ」によって決定される。上記の例を続けると、「変換済みスーパーブロック」には
【数７】
2010166549.tif 000009
（ｊ＝＋０，１，２，．．．，ｎＢ）が含まれ、「充てん済みスーパーブロック」の「充てん済みフィンガープリント」は以下のようになる。
【数８】
2010166549.tif 000010
【００４９】
ここで、ａλはクライアントの「チャレンジデータ」によって決定される乱数である。
【００５０】
最後に、アーカイブは、「変換済みスーパーブロックの知識証明」を生成する。これには「変換済みスーパーブロック」を直接使用することもできる。あるいは、標準的なゼロ知識証明技術（対話または非対話方式）による「変換済みスーパーブロック」のコンテンツの知識を使用してもよい。また、クライアントの「チャレンジデータ」がＨｉ＝ｈｉｖ（Ｉ＝＋０，１，２，．．．，ｎＢ）を含む場合に、クライアントがチャレンジデータ毎に異なるｖを選択し、ｖを秘匿しておくことも可能である。好適なケースでは、Ｈｉはクライアントの公開鍵、ｖはクライアントの秘密鍵の一部である。アーカイブは、Ｈｉを利用して、「変換済みスーパーブロックの知識証明」を以下の様に計算する。
【数９】
2010166549.tif 000011
【００５１】
アーカイブは、「変換済みフィンガープリント」Ｔと「変換済みスーパーブロックの知識証明」Ｈとを、アトミック証明手順の出力としてクライアントに送信する必要がある。
【００５２】
アーカイブは、アトミック証明手順を全部でψ回反復する必要がある。ボックス数を決定する値としては、φ＝｜ｌ／ψ｜＋１を選択することができる。ここで、ｌはセキュリティレベルを決定する値であり、クライアントによって選択される。乱数ａλのビット長としては、φを選択する。アトミック手順をψ回反復すると、ＰＤＩスキームのセキュリティレベルは（ｎ／ψ）・２−ｌとなる。これは、１つ以上のブロックが破壊されている場合に、アーカイブが検証器に正しい結果を返す確率は、最大（ｎ／ψ）・２−ｌであることを意味する。
【００５３】
上記の「個数Φと無作為性は、クライアントか受信したチャレンジデータによって決定される」と「ａλは、クライアントのチャレンジデータによって決定される乱数である」の部分については、代替の実施例がある。例えば、φ＝ｎを選択し、ｎ個のフィンガープリントをｎ個のボックスに均等に配置し（すなわち、１つのボックスに必ず１つのフィンガープリントが含まれるようにする）、ａλのビット長としてｌを選択したとすると、この場合には、ψ＝１を選択すると、ｎ・２−ｌのセキュリティレベルが実現される。
【００５４】
ステップ２'：
クライアントは、アーカイブから、全ψ回のアトミック証明手順の出力を受信する。
【００５５】
クライアントは、１回のアトミック証明手順から得られた「変換済みスーパーブロック」の「変換済みフィンガープリント」と「変換済みスーパーブロックの知識証明」の各々を対象に、アトミック検証手順を実行する。
【００５６】
クライアントは、各アトミック検証手順において、まずΦ個のボックスを構築し、論理的かつ無作為にロケータＷｉをこれらのボックスに割り当てる。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブがフィンガープリントを割り当てる際に使用した無作為性と同一である。１つのロケータは、必ず１つのボックスに配置しなければならない。全ｎ個のロケータがボックスに配置された後、各ボックス内には、ボックスに割り当てられたロケータに基づいて生成された「充てん済みロケータ」が存在する。例えば、λ番目のボックスに２つのロケータＷηおよびＷωのみが配置されるケースであれば、このボックスの「充てん済みロケータ」はＷλ＝Ｗη＋Ｗωとなる。
【００５７】
次に、クライアントは、別の無作為性をすべてのボックスの「充てん済みロケータ」に適用することにより、１つの「変換済みロケータ」を生成する。無作為性はクライアントが選択した「チャレンジデータ」によって決まるので、ここで使用される無作為性は、アーカイブが「変換済みフィンガープリント」を計算する際に使用した無作為性と同一である。「変換済みロケータ」は以下の式で表される。
【数１０】
2010166549.tif 000012
【００５８】
ここで、ａλはクライアントの「チャレンジデータ」によって決定される乱数である。
【００５９】
最後に、アーカイブが「変換済みスーパーブロックの知識証明」を直接「変換済みスーパーブロック」として生成する場合には、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をＨ'＝（Ｔｘ＋ｚＭ／Ｗ）として計算し、以下と比較する。
【数１１】
2010166549.tif 000013
【００６０】
アトミック検証手順は、一致した場合にのみ、「成功」を出力する。あるいは、クライアントは「検証対象の変換済みスーパーブロックの知識証明」をＨ'＝（Ｔｘ＋ｚＭ／Ｗ）θとして計算し、アーカイブから受信した値Ｈと比較することもできる。アトミック検証手順は、Ｈ＝Ｈ'の場合にのみ、「成功」を出力する。また、フィンガープリントが以下の様に計算される場合には、「検証対象の変換済みスーパーブロックの知識証明」は（Ｔ１／ｘ／Ｗ）θとして計算される。
【数１２】
2010166549.tif 000014
【００６１】
クライアントは、アトミック検証手順が「成功」を出力した場合にのみ、アーカイブ側でデータ保全性が保たれていると判定する。アーカイブ側で１つ以上のブロックが破壊されているときにクライアントが誤判定する確率は、最大で２−ｌである。
（詳細な説明）
【００６２】
以下、本発明についてさらに詳細に説明する。
【００６３】
本発明の開示では、楕円曲線に関連して頻用される加算表記ではなく、従来の乗法群表記を使用する。
【００６４】
Ｇ１＝＜ｇ１＞とＧ２＝＜ｇ２＞とを加群ｇ＝＜ｇ＞を伴う２つの有限循環グループとして、｜Ｇ１｜＝｜Ｇ２｜＝｜ｇ｜＝ｐとなるとする。ここでｐは任意の大きな素数である。双線形マップｅ：Ｇ１×Ｇ２→ｇは、以下の特性を有する関数である。
■  双線形：すべてのｈｉ∈Ｇ１においてｈ２∈Ｇ２であり、すべてのａ，ｂ∈Ｚｐにおいてｅ（ｈ１ａ，ｈ２ｂ）＝ｅ（ｈ１，ｈ２）ａｂである。
■  非縮退：∃ｈ１∈Ｇ１、∃ｈ２∈Ｇ２、よってｅ（ｈ１，ｈ２）≠Ｉ（Ｉはｇの本人情報）である。
■  計算可能：ｃを計算するための効率的なアルゴリズムが存在する。
【００６５】
入力セキュリティパラメータ１ｋに基づいて上記の双線形マップの設定を出力し、それを（ｐ，Ｇ１，Ｇ２，ｇ，ｇ１，ｇ２，ｅ）←Ｓｅｔｕｐ（１ｋ）として記述するセットアップアルゴリズムＳｅｔｕｐ（．）が存在すると仮定する。
【００６６】
Ｇ１、Ｇ２、およびｇは同一の素数位数ｐを有するので、双線形の特性と非縮退の特性からｅ（ｇ１，ｇ２）＝ｇであることは容易に理解できる。．
【００６７】
（ｐ，Ｇ１，Ｇ２，ｇ，ｇ１，ｇ２，ｅ）←Ｓｅｔｕｐ（１ｋ）とし、６つの疑似ランダム関数ｐｒｆ１：｛０，１｝＊→Ｚｐ，ｐｒｆ２：｛０，１｝＊→Ｇ１、ｐｒｆ３（φ）：｛０，１｝＊→Ｚ２ｐ、ｐｒｆＶＦＢ：｛０，１｝＊→Ｚｐ、ｐｒｆ４（φ）：｛０，１｝＊→Ｚ２ｐ、およびｐｒｆ５：Ｇ１→｛０，１｝１６０をシステムパラメータとする。
【００６８】
クライアントによるデータへのフィンガープリント付加
クライアントは、秘密鍵（ｘ，ｖ）←Ｚｐ２と公開鍵Ｙ＝ｇ２ｘ∈Ｇ２を有する。クライアントは、認証局からのＹの証明書を有するのが望ましい。あるいは、クライアントの秘密鍵ｖを、例えばｖ＝ｐｒｆ１（ｘは「第２の秘密鍵」）として計算することもできる。
【００６９】
さらに、クライアントは、（ｈｉ＝ｇ１ｐｒｆ１（Ｉ，ｘ），Ｈｉ＝ｈｉθ）∈Ｇ１２（ｉ＝＋０，１，２，．．．，ｎＢ）を計算して自身の公開鍵とする。
【００７０】
データＭを、各ビット長がｌＭ（ｌＭ＜ｌｏｇｐが必須）のＮ個のブロックＭｉ（Ｉ＝１，２，．．．，Ｎ）に分割する。Ｍは、修飾ファイル名としてＦＮＭのように表わす。
【００７１】
図３に、ＰＤＩスキームにおいて、データＭを論理的に分割してｎ個のスーパーブロックにする方法を示す。スーパーブロック数は、ｎ＝｜Ｎ／ｎＢ｜で表す。データＭの長さがＮ・ｌＭまたはｎ・（ｎＢ・ｌＭ）に満たない場合は、ゼロを使用して論理的に埋められる。
【００７２】
本発明のＩＰＤＩスキームによれば、仮想ファイルブロックＭ（ｉ−１）・ｎＢ＋'＋０'は、ｉ番目（ｉ＝１，２，．．．，ｎ）のスーパーブロックのｎＢ個の真のファイルブロックＭ（ｉ−１）・ｎＢ＋１，…，ＭｉｎＢの前に付加される。真のファイルブロックの長さはｌＭビットであるのに対し、仮想ファイルブロックＭ（ｉ−１）・ｎＢ＋'＋０'の長さはｐビットである。仮想ファイルブロックＭ（ｉ−１）・ｎＢ＋'＋０'は、クライアントによって以下の式で計算される。
Ｍ（ｉ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＦＢ（Ｉ，ｚ，ＦＮＭ）∈Ｚｐ．
【００７３】
図３ａに第１のスーパーブロックを示す。ここで、Ｍ＋０は仮想ファイルブロックであり、下付文字「＋０」は第１の真のファイルブロックＭ１の直前のブロックを表すために使用されている。これは、他のスーパーブロックにおいても同様である。
【００７４】
あるいは、ｐｒｆＶＦＢ：｛０，１｝＊→Ｚ（ここで、Ｚ⊆Ｚｐ）を選択することにより、仮想ファイルブロックの長さをｐビットよりも短くすることもできる。
【００７５】
クライアントは、以下を実行してデータにフィンガープリントを付加する。
ａ）  クライアントは識別子ｚＭ←Ｚｐを選択し、以下の式でロケータＷｉ＝ｐｒｆ２（Ｉ，ｚＭ，ＦＮＭ）∈Ｇ１を計算する。
【数１３】
2010166549.tif 000015
ここで、ｉ＝１，２，．．．，ｎである。ｉ番目のスーパーブロックのフィンガープリントをＴｉと命名する。
ｂ）  クライアントは秘密鍵ｘを使用して（ＦＮＭ，Ｍ，ｚＭ，｛Ｔｉ｝）に署名し、署名Ｓを生成する。
ｃ）  クライアントはＦＮＭに対してｚＭを保存する。
ｄ）  クライアントはＦＮＭ、Ｍ、ｚＭ∈Ｚｐ、｛Ｔｉ｝∈Ｇ１ｎ、およびＳをアーカイブに送信する。
ｅ）  アーカイブはＦＮＭ、Ｍ、ｚＭ，｛Ｔｉ｝、およびＳを受信後、クライアントの公開鍵を使用して、Ｓが（ＦＮＭ，Ｍ，ｚＭ，｛Ｔｉ｝）の有効な署名であるか検証する。
【００７６】
クライアントによるデータへのフィンガープリントの増分的付加
クライアントは、以下を実行してデータに増分的変化のフィンガープリントを付加する。ファイル参照ＦＮＦおよびファイルキーｚを有するファイルＦには、すでにｎＳＢ個のスーパーブロックが存在する。Ｆの最後尾に新たなデータ集合｛ＭｎＳＢ・ｎＢ＋ｊ｝（ｊ＝１，２，．．．，ｎＢ）を追加するために、即ち、ｉ＝ｎＳＢをｉ＝ｎＳＢ+１に増分するために、以下の動作が実行される。
ａ）  クライアントは、以下の式により仮想ファイルブロック（ＶＦＢ）を計算する。
ＭｎＳＢ・ｎＢ＋'＋０'＝ｐｒｆＶＦＢ（ｎＳＢ＋１，ｚ，ＦＮＦ）∈Ｚｐ
ｂ）  クライアントは、以下を計算する。
【数１４】
2010166549.tif 000016
【００７７】
アーカイブによるデータ保全性の証明
アーカイブが（最大の確率２−ｌにおけるエラー以外には）ゼロビットエラー率でＦＮＭのコンテンツを保持しているか確認するため、クライアントがアーカイブにチャレンジデータを送り、アーカイブはそれに対して以下を応答する。
ｉ）  クライアントは、反復因数１≦ψ≦ｌを選択する。
ｉｉ）  クライアントは（ｋ１，ｋ２）←Ｚｐ２を選択し、ＦＮＭ，ｃｈａｌ＝（ｌ，ψ，ｋ１，ｋ２）をアーカイブに送信する。
ｉｉｉ）  アーカイブは、ＦＮＭとｃｈａｌ＝（ｌ，ψ，ｋ１，ｋ２）とを受信後、まずφ＝｜ｌ／ψ｜＋１を計算し、変換済みフィンガープリントＴｋ＝Ｏ∈Ｇ１（ここでｋ＝１，２，．．．ψ、ＯはＧ１の本人情報）を初期化する。その後、以下のアトミック証明手順を独自にψ回にわたって反復する。
ｉｉｉ−ａ．  充填済みフィンガープリントＴｖ＝Ｏ∈Ｇ１、充填済みスーパーブロックｅｖｊ＝０、および変換済みスーパーブロック  Ｅｊ＝０，ｖ＝０，１，．．．，Φ−１＝２φ−１，ｊ＝＋０，１，２，．．．，ｎＢを初期化する。
ｉｉｉ−ｂ．  ｉ＝１，２，．．．，ｎの各々について、以下の計算を行う。
ｂ−ｉ．  σ＝ｐｒｆ３（ｉ，ｋ，ｋ１）
ｂ−ｉｉ．  Ｔσ＊＝Ｔｉ。これはＴｉをσ番目のボックスの充てん済みフィンガープリントに付加することを意味する。
ｂ−ｉｉｉ．  ｊ＝＋０，１，２，．．．，ｎＢの各々について、ｅσｊ＋＝Ｍ（ｊ−１）＊ｎＢ＋ｊｍｏｄｐを計算する。これは、Ｍ（ｊ−１）＊ｎＢ＋ｊをσ番目のボックスの充てん済みスーパーブロックに付加することを意味する。
ｉｉｉ−ｃ．  ｖ＝＋０，１，２，．．．，Φの各々について、以下の計算を行う。
ｃ−ｉ．  ａｖ＝ｐｒｆ４（ｖ，ｋ，ｋ２）  
ｃ−ｉｉ．  Ｔｋ＊＝Ｔｖａｖ
ｃ−ｉｉｉ．  ｊ＝＋０，１，２，．．．，ｎＢの各々について、Ｅｊ＋＝ａｖ・ｅｖｊｍｏｄｐを計算する。
ｉｉｉ−ｄ．  以下を計算し、
【数１５】
2010166549.tif 000017
変換済みスーパーブロックの知識証明とする。
ｉｖ）  アーカイブは、保全性証明（Ｔｋ，Ｈｋ），ｋ＝１，２，．．．，ψをクライアントに送信する。
【００７８】
あるいは、クライアントがｋ１←Ｚｐを選択し、ｋ２を例えばｋ２＝ｐｒｆ１（ｋ１は「第２の無作為性定義キー」）として計算することもできる。この場合は、ｋ２の送信は省略することができる。
【００７９】
先願で提案されたＰＤＩスキームにおける「アーカイブによるデータ保全性の証明」手順と比較すると、ファイルブロックが計算に用いられる場合は常に、ＶＦＢが真のファイルブロックであるかのように使用される点が異なる。
【００８０】
クライアントによるデータ保全性の検証
クライアントは、（Ｔｋ，Ｈｋ）（ここで、ｋ＝１，２，．．．，ψ）の受信後、以下のアトミック検証手順を独自にψ回にわたって反復する。
Ｉ）  変換済みロケータＷｋ＝Ｉ∈Ｇ１、充填済みロケータＷｖ＝Ｉ∈Ｇ１，ｖ＝０，１，．．．，Φ−１＝２φ−１を初期化する。
ＩＩ）  Ｉ＝１，２，．．．，ｎの各々について、σ＝ｐｒｆ３（ｉ，ｋ，ｋ１）およびＷσ＊＝ｐｒｆ２（ｉ，ＦＮＭ）を計算する。
ＩＩＩ）  ｖ＝１，２，．．．，Φの各々について、ａｖ＝ｐｒｆ４（ｖ，ｋ，ｋ２）およびＷｋ＊＝Ｗｖ−ａｖを計算する。
ＩＶ）  計算により、Ｈｋ＝ｐｒｆ５（（Ｔｋｘ＋ｚＭ・Ｗｋ）ｖ）であることを検証する。この合同式が成り立つ場合にのみＴＲＵＥを出力する。
【００８１】
全てのアトミック検証手順でＴＲＵＥが出力された場合にのみ、クライアントはデータ保全性証明が正しいと判断する。
【００８２】
先願で提案されたＰＤＩスキームにおける「クライアントによるデータ保全性の検証」手順と比較すると、修正が不要である点が異なる。
（他の実施例）
（代替スキーム１）
【００８３】
ＰＤＩ−２スキームは、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄと「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。これは、公的検証可能性をサポートするスキームである。
【００８４】
クライアントは、Ｙｖ＝Ｙｖとｇ２ｖ＝ｇ２Ｖとを計算して自身の公開鍵とする。
【００８５】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄ．  以下を計算し、
【数１６】
2010166549.tif 000018
変換済みスーパーブロックの知識証明とする。
【００８６】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ'）  計算により、ｅ（Ｈｋ，ｇ２）＝ｅ（Ｔｋ，Ｙｖ・ｇ２ｖｚＭ）・ｅ（Ｗｋ，ｇ２ｖ）であることを検証する。
【００８７】
ＩＰＤＩ−２スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム１．１）
【００８８】
加速化ＰＤＩ−２は、ＩＰＤＩ−２の「クライアントによるデータ保全性の検証」を一部変更したものである。
【００８９】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ−ｅ）ｋ個の乱数ｒｋ∈Ｚ⊆Ｚｐ（ただし、ｋ＝１，２，．．．，ψ）を選択し、計算により以下であることを検証する。
【数１７】
2010166549.tif 000019
【００９０】
加速化ＩＰＤＩ−２スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム２）
【００９１】
ＩＰＤＩ−３スキームは、「クライアントによるデータへのフィンガープリント付加」のステップａ）と「クライアントによるデータ保全性の検証」のステップＩＶ）を一部変更したものである。
【００９２】
「クライアントによるデータへのフィンガープリント付加」のステップａ）への変更：
ａａ）  クライアントは識別子ｚＭ←Ｚｐを選択し、以下の式でＷｉ＝ｐｒｆ２（Ｉ，ｚＭ，ＦＮＭ）∈Ｇ１を計算する。
【数１８】
2010166549.tif 000020
ここで、ｉ＝１，２，．．．，ｎである。
【００９３】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ”）  計算により、Ｈｋ＝ｐｒｆ５（（Ｔｋ１／ｘ）・Ｗｋ）ｖ）であることを検証する。
（代替スキーム３）
【００９４】
ＩＰＤＩ−４スキームは、上記の代替スキーム２に対し、「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．と「クライアントによるデータ保全性の検証」のステップＩＶ）に一部変更を加えたものである。これもまた、公的検証可能性をサポートするスキームである。
【００９５】
クライアントは、さらに、Ｙｖ＝ｇ２ｖ／ｘとｇ２ｖ＝ｇ２ｖとを計算して自身の公開鍵とする必要がある。
【００９６】
「アーカイブによるデータ保全性の証明」のステップｉｉｉ−ｄ．への変更：
ｉｉｉ−ｄｄｄ．  以下を計算し、
【数１９】
2010166549.tif 000021
変換済みスーパーブロックの知識証明とする。
【００９７】
「クライアントによるデータ保全性の検証」のステップＩＶ）への変更：
ＩＶ'''）  計算により、ｅ（Ｈｋ，ｇ２）＝ｅ（Ｔｋ，Ｙｖ）・ｅ（Ｗｋ，ｇ２ｖ）であることを検証する。
【００９８】
ＩＰＤＩ−４スキームでは、「アーカイブによるデータ保全性の証明」と「クライアントによるデータ保全性の検証」のどのステップもクライアントの秘密鍵を必要とせず、サードパーティ検証器が有効に処理を実行できるため、公的検証可能性がサポートされる。
（代替スキーム３．１）
【００９９】
加速化ＩＰＤＩ−４は、ＩＰＤＩ−４の「クライアントによるデータ保全性の検証」を一部変更したものである。
【０１００】
「クライアントによるデータ保全性の検証」のステップＩＶ'''）への変更：
ＩＶ−ｆ）ｋ個の乱数ｒｋ∈Ｚ⊆Ｚｐ（ただし、ｋ＝１，２，．．．，ψ）を選択し、計算により以下であることを検証する。
【数２０】
2010166549.tif 000022
【０１０１】
加速化ＩＰＤＩ−４スキームでは、クライアントはより低い計算能力で対の評価を行うことができる。
（代替スキーム４）
【０１０２】
上記のすべてのスキームに対し、システムパラメータ、「クライアントによるデータへのフィンガープリント付加」のステップ、および「クライアントによるデータ保全性の検証」のステップに一部変更を加えることで、サンプリングをサポートするスキームが得られる。
【０１０３】
サンプリングをサポートするには、システムパラメータｐｒｆ６：｛０，１｝＊→｛１，２，．．．，ｎ｝を追加する必要がある。チャレンジデータｃｈａｌ＝（ｌ，ψ，ｋ１，ｋ２）には、キーｋ３←Ｚｐと正の数値Λが追加される。
【０１０４】
次に、「クライアントによるデータへのフィンガープリント付加」と「クライアントによるデータ保全性の検証」の全ステップにおいて、ｉ＝１，２，．．．，ｎがすべてｉ＝ｐｒｆ６（ｋ３，１），ｐｒｆ６（ｋ３，２），．．．，ｐｒｆ６（ｋ３，Λ）に置換される。これにより、ｉ＝ｐｒｆ６（ｋ３，１），ｐｒｆ６（ｋ３，２），．．．，ｐｒｆ６（ｋ３，Λ）によって選択されたΛ個のスーパーブロックのみが処理対象となるため、サンプリングされたスーパーブロックデータのみのデータ保全性が検証される。
【０１０５】
したがって、代替スキーム４においては、アーカイブはすべてのスーパーブロックを使用しなくてもデータ保全性証明を生成することができる。アーカイブは、クライアントのチャレンジデータの情報をもとに、証明の生成において、どのスーパーブロックをいくつ選択すべきかを決定する。
（代替動作モデル）
【０１０６】
非特許文献４（ＲＦＣ  ４８１０）で提案されるタイムスタンプ局（ＴＳＡ）を導入することにより、図４に示すように、チャレンジキー（ｋ１，ｋ２）←Ｚｐ２をＴＳＡから取得したデジタル署名付きタイムスタンプに置換することが可能になる。ここで、タイムスタンプをＴとすると、標準的なハッシュアルゴリズムＳＨＡ−１を使用して、ｋ１＝ＳＨＡ−１（Ｔ，“１”）とｋ２＝ＳＨＡ−１（Ｔ，“２”）を得ることができる。こうした置換を行った場合のクライアントのチャレンジデータは、データがＴＳＡによるタイムスタンプ発行時間まで正常に保持されているかどうかの検証を求める内容となる。この事前計算により、アーカイブの応答、すなわち（Ｔｋ，Ｈｋ）、の利用が必須となるのはアトミック検証手順の最後のステップのみとなり、アーカイブとクライアントのいずれにおいても大幅に処理が簡素化される。
【０１０７】
さらに、図５に示すように、検証器がサードパーティ検証器の場合には、ＴＳＡのタイムスタンプからｋ１とｋ２を推論することもできる。また、サンプリングが有効な場合には、ｋ３はＴＳＡのタイムスタンプから、例えばｋ３＝ＳＨＡ−１（Ｔ，“３”）として推論することができる。
（代替スキーム５）
【０１０８】
仮想ファイルブロック（ＶＦＢ）は、「真」のファイルブロック｛Ｍ（Ｉ−１）・ｎＢ＋ｊ｝，ｊ＝１，２，．．．，ｎＢを追加の入力として受け付けることができる。つまり、ＶＦＢは以下により計算できる。
Ｍ（Ｉ−１）・ｎＢ＋'＋０'＝ｐｒｆＶＦＢ（Ｉ，ｚ，ＦＮＭ，｛Ｍ（Ｉ−１）・ｎＢ＋ｊ｝）∈Ｚｐ，ｊ＝１，２，．．．，ｎＢ．
（ハードウェア実装）
【０１０９】
当業者には明らかなように、本発明はハードウェア構造によって実装することもできる。以下では、限定ではなく参考として、いくつかの例について説明する。
【０１１０】
クライアント
図６に、本発明を実装したクライアント１４００のブロック図を示す。この実装では、クライアント１４００はフィンガープリントデータ生成装置として使用される。
【０１１１】
図６に示すように、クライアント１４００は、生成される各スーパーブロックにつき１個の仮想ファイルブロックＭ（Ｉ−１）・ｎＢ＋'＋０'を生成する仮想ファイルブロック生成手段１４０５と、データをＮ個のブロックＭｉ（ｉ＝１，２，．．．，Ｎ）に分割し、ｎＢ個のブロックの各々と仮想ファイルブロック生成手段１４０５からの仮想ファイルブロックＭ（Ｉ−１）・ｎＢ＋'＋０'とを１つのスーパーブロックに結合してｎ＝｜Ｎ／ｎＢ｜スーパーブロックを取得するスーパーブロック生成手段１４１０と、有限循環グループＧ１＝＜ｇ１＞からｎＢ＋１個の要素ｈｊ（ｊ＝１，２，．．．，ｎＢ）を選択し、ｋ番目（ｋ＝１，２，．．．，ｎ）のスーパーブロックのロケータＷｋと、選択されたｎＢ＋１個の要素ｈｊと、第１の秘密鍵ｘとを使用して、ｋ番目のスーパーブロックのフィンガープリントＴｋを生成するフィンガープリントデータ生成手段１４２０とを備える。クライアント１４００は、さらに、生成されたスーパーブロック、有限循環グループ、生成されたフィンガープリント、ロケータ、秘密鍵などの、スーパーブロック生成手段１４１０とフィンガープリントデータ生成手段１４２０によって利用または生成される情報を格納するメモリ１４３０を含む。ただし、メモリ１４３０は、上記のように独立した手段とすることも、あるいはスーパーブロック生成手段１４１０とフィンガープリントデータ生成手段１４２０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１１２】
同様に、ｎＢ＋１個の要素ｈｊは、第１の秘密鍵ｘに対応する公開鍵の一部であるのが望ましい。また、ｎＢ＋１個の要素ｈｊは、ｈｉ＝ｇ１ｒｊ（ｒｊは秘密鍵）の関係を満足するものとすることができる。さらに、公開鍵と秘密鍵もメモリ１４３０に格納することができる。
【０１１３】
アーカイブ
図７に、本発明を実装したアーカイブ１５００のブロック図を示す。この実装では、アーカイブ１５００はデータ保全性証明装置として使用される。
【０１１４】
図７に示すように、アーカイブ１５００は、少なくとも第１のランダム性定義キーｋ１と第２のランダム性定義キーｋ２とから成るチャレンジデータを受信する受信手段１５１０と、前記チャレンジデータによって決定される個数であるΦ個のボックスを構築し、第１のランダム性定義キーによって定義された第１の無作為方法に従って、１つのフィンガープリントが１個のボックスに入るように、ｎ個のフィンガープリントをΦ個のボックスに割り当て、ｎ個のフィンガープリントの上記割り当てに基づいて、Φ個の充てん済みスーパーブロックと対応する充てん済みフィンガープリントとを生成するパッケージ化手段１５２０と、第２のランダム性定義キーｋ２によって定義された第２の無作為方法に従って、Φ個の充てん済みスーパーブロックと対応する充てん済みフィンガープリントとを無作為に変換して、変換済みスーパーブロックと変換済みフィンガープリントとを生成する変換手段１５３０と、変換済みスーパーブロックの知識証明を生成する知識証明生成手段１５４０とを含む。アーカイブ１５００はさらに、受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０によって使用または生成される情報を格納するメモリ１５５０を含む。ただし、メモリ１５５０は、上記のように独立した手段とすることも、あるいは受信手段１５１０、パッケージ化手段１５２０、変換手段１５３０、および知識証明生成手段１５４０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１１５】
知識証明生成手段１５４０は、変換済みスーパーブロックの知識証明を、変換済みスーパーブロック自体として生成することも、あるいは公開鍵と変換済みスーパーブロックに基づいて生成することもできる。
【０１１６】
チャレンジデータは、全ｎ個のスーパーブロックとそれに対応するフィンガープリントの代わりに、どのΛ個のスーパーブロックとそれに対応するフィンガープリントとをパッケージ化手段１５２０がデータ保全性証明のために選択するかを定義する、スーパーブロック選択キー対（ｋ３，Λ）をさらに備えることができる。
【０１１７】
チャレンジデータは、反復因数ψをさらに備えることができる。これにより、パッケージ化手段１５２０と、変換手段１５３０と、知識証明生成手段１５４０の動作がψ回反復され、各反復毎に、１つの変換済みスーパーブロックの知識証明が生成される。これは、変換済みスーパーブロックＨｍ（ｍ＝１，２，．．．，ψ）のｍ番目の知識証明と呼ばれる。
【０１１８】
チャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得したデジタル署名付きのタイムスタンプを含めることができる。
【０１１９】
さらに、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーｋ１、ｋ２の少なくとも一方と、スーパーブロック選択キーｋ３とが生成される。
【０１２０】
また、アーカイブ１５００は、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを送信する送信手段１５６０をさらに備える。
【０１２１】
検証器（クライアントまたはサードパーティ検証器）
図８は、本発明を実装した検証器１６００のブロック図を示す。この実装では、検証器１６００はデータ保全性検証装置として使用される。検証器１６００はクライアント１４００自体、あるいはサードパーティ検証器のいずれでもよいことは当業者には明かであろう。クライアント１４００自体を検証器１６００とする前者のケースでは、図６のデータにフィンガープリントを付加するためのサブシステムと、図８の検証データ保全性を検証するためのサブシステムはクライアント１４００に備えられる。一方、サードパーティ検証器を検証器１６００とする後者のケースでは、サードパーティ検証器は図８の構造を備えることのみが必須となり、図６の構造は任意である。
【０１２２】
図８に示すように、検証器１６００は、第１のランダム性定義キーｋ１と第２のランダム性定義キーｋ２の少なくとも一方を含むチャレンジデータを生成して送信するチャレンジデータ生成・送信手段１６１０と、変換済みフィンガープリントと、変換済みスーパーブロックの知識証明とを受信する受信手段１６２０と、Φ個のボックスを構築し、第１の無作為方法に従って、１つのロケータが１個のボックスに入るように、ｎ個のロケータＷｋをΦ個のボックスに割り当て、ｎ個のロケータの上記割り当てに基づいて、Φ個の充てん済みロケータを生成するロケータパッケージ化手段１６３０と、第２の無作為方法に従って、Φ個の充てん済みロケータを無作為に変換し、変換済みフィンガープリントと変換済みロケータとから、検証対象の変換済みスーパーブロックの知識証明を生成する検証対象知識証明生成手段１６４０と、検証対象の変換済みスーパーブロックの知識証明と、受信した変換済みスーパーブロックの知識証明とを比較する比較器１６５０と、比較結果が一致の場合に、データ保全性を検証する検証装置１６６０とを含む。検証器１６００はさらに、チャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０によって使用または生成される情報を格納するメモリ１６７０を含む。ただし、メモリ１６７０は、上記のように独立した手段とすることも、あるいはチャレンジデータ生成・送信手段１６１０、受信手段１６２０、ロケータパッケージ化手段１６３０、検証対象知識証明生成手段１６４０、比較器１６５０、および検証装置１６６０に組み込まれた１つまたは複数の内蔵手段とすることも可能なことは、当業者には明かであろう。
【０１２３】
検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、データの識別子ｚＭと、変換済みフィンガープリントと、変換済みロケータとに基づいて生成することができる。
【０１２４】
また、検証対象知識証明生成手段１６４０は、検証対象の変換済みスーパーブロックの知識証明を、第１および第２の秘密鍵ｘ、ｖに基づいて生成することもできる。
【０１２５】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、ロケータパッケージ化手段がデータ保全性検証のために全ｎ個のロケータの代わりに、どのΛ個のロケータを選択すべきかを定義するスーパーブロック選択キー対（ｋ３，Λ）をさらに備える。
【０１２６】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータは、反復因数ψをさらに備える。これにより、ロケータパッケージ化手段１６３０と、検証対象知識証明生成手段１６４０と、比較器１６５０の動作がψ回反復され、すべての比較結果が一致の場合にのみ、検証手段１６６０がデータ保全性を検証する。
【０１２７】
チャレンジデータ生成・送信手段１６１０によって生成されるチャレンジデータには、タイムスタンプ局（ＴＳＡ）から取得した、デジタル署名付きのタイムスタンプを含めることができる。
【０１２８】
チャレンジデータ生成・送信手段１６１０は、デジタル署名付きタイムスタンプから、第１および第２のランダム性定義キーｋ１、ｋ２の少なくとも一方と、スーパーブロック選択キーｋ３とを決定する。
【０１２９】
提案されるＶＦＢの代替利用法
ＶＦＢ概念をＰＤＰスキームに応用することも可能である。この場合、ＩＰＤＰを以下の方法（非特許文献７の１１頁）で構築することにより、データファイルの増分的変化を処理できるようになる。原理上は、ＰＤＰスキームは、ｎＢ＝１とするＰＤＩスキームの簡略版とみなすことができる。
【０１３０】
ＩＰＤＰスキームが実行することは、基本的には、各ファイルブロックｍｉに対してＶＦＢ  ｍｉを計算することである。スーパーブロックに１個のファイルブロックが存在する（すなわち、ｎＢ＝１）と考えれば、ＩＰＤＩの中心的概念（すなわち、ファイルブロックの集まりである各スーパーブロックに対してＶＦＢを計算し、それを付加するという概念）とまったく同じである。
【０１３１】
また、ＩＰＤＰスキームでは、ＶＦＢを計算に組み込むためにオリジナルのＰＤＰスキームの別の部分が若干変更される。
【０１３２】
ＩＰＤＰスキームの利点は、ＲＳＡベースのスキームとしては、上記要件（Ｉ）〜（ＶＩＩ）を満足する唯一のスキームであることである。
【０１３３】
ＴａｇＢｌｏｃｋ（．）：
Ｔｉ，ｍ＝（ＰＲＦ（Ｗｉ）・ｈ０ｍ・ｇｍ）ｄｍｏｄＮ（ここで、ＶＦＢ  ｍ＝ｐｒｆ（ｖ，ｉ））。また、ｈ０∈ＲＱＲＮは公開鍵の追加のパラメータである（例えばＮであり、具体的にはＰＲＦ（・）：｛０，１｝＊→ＱＲＮ（ここで、ｅｄ≡１ｍｏｄφ（Ｎ））となる）。
【０１３４】
あるいは、ＶＦＢをｍ＝ｐｒｆ（ｖ，ｉ，ｍ）として計算することもできる。
【０１３５】
ＧｅｎＰｒｏｏｆ（．）：
Ｔ＝Ｔｉ１，ｍｉ１ａ１…‥Ｔｉｃ，ｍｉｃａｃ＝（ＰＲＦ（Ｗｉ１）ａ１）……ＰＲＦ（Ｗｉｃ）ａｃ・ｈ０ａ１ｍｉ１＋…＋ａｃｍｉｃ・ｇａ１ｍｉ１＋…＋ａｃｍｉｃ）ｄｍｏｄＮ．
【０１３６】
Ｐ＝Ｈ（（ｈ０ｓａ１ｍｉ１＋…＋ａｃｍｉｃ・ｇｓａ１ｍｉ１＋…＋ａｃｍｉｃ）ｍｏｄＮ（ここで、ｈ０ｓ＝ｈ０ｓ∈ＱＲＮであり、Ｈ（・）：｛０，１｝＊→Ｚは、例えばＳＨＡ−１ハッシュ関数である。）パラメータｃ、ａｊ、ｉｊ（ここでｊ＝１，２，．．．，ｃ，ｇｓ）、およびｈ０ｓは、チャレンジデータによって決定される。
【０１３７】
ＣｈｅｃｋＰｒｏｏｆ（．）：
この部分は、オリジナルと同じである。
【０１３８】
本発明の詳細がより明確かつ体系的に理解されるよう、中国の先行出願（特許文献１（中国特許第２００８１０１６５８６４．３号））の内容全体をここに（冗長的な反復ではなく）本明細書の一部として組み込む。本発明において理解の困難な部分がある場合は、特許文献１（中国特許第２００８１０１６５８６４．３号）を参照して解決することができ、場合によってはこうした困難そのものの説明も得られるであろう。
【０１３９】
上記の説明は本発明の好適な実施例のみを示したものであり、いかなる形であれ本発明を限定することを意図するものではない。したがって、本発明の適用範囲には、本発明の精神および原則に則ったあらゆる変更、置換、改良等も内包される。
【符号の説明】
【０１４０】
１：チャレンジデータ 
２：データ保全性証明
１'：タイムスタンプ
２'：データ保全性証明
１４０５：仮想ファイルブロック生成手段
１４１０：スーパーブロック生成手段
１４２０：フィンガープリントデータ生成手段
１４３０：メモリ
１５１０：受信手段
１５２０：パッケージ化手段
１５３０：変換手段
１５４０：知識証明生成手段
１５５０：メモリ
１５６０：送信手段
１６１０：チャレンジデータ生成・送信手段
１６２０：受信手段
１６３０：ロケータパッケージ化手段
１６４０：検査対象知識証明生成手段
１６５０：比較器
１６６０：検証手段
１６７０：メモリ
【図１】
2010166549.tif 000027
【図２】
2010166549.tif 000028
【図３】
2010166549.tif 000029
【図３ａ】
2010166549.tif 000030
【図４】
2010166549.tif 000031
【図５】
2010166549.tif 000032
【図６】
2010166549.tif 000033
【図７】
2010166549.tif 000034
【図８】
2010166549.tif 000035
【外国語明細書】
2010166549000001.pdf