【課題】少ないデータ量で部分完全性保証を実現する。
【解決手段】本コンテンツ処理装置は、更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける手段と、更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する手段と、更新ブロックに対するハッシュ値を計算する手段と、管理データ格納部から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と、更新位置と、更新ブロックに対するハッシュ値と、更新種別とを含む更新記録情報に対して、秘密鍵を用いて電子署名を生成する手段と、更新済みコンテンツと更新記録情報と電子署名とを出力する手段とを有する。

【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、コンテンツ（例えば、文書、動画、写真、音楽など）の部分完全性保証技術（ＰＩＡＴ：Partial Integrity Assurance Technology）に関する。
【背景技術】
【０００２】
例えばＲＳＡ（Rivest Shamir Adleman）等の公開鍵暗号方式を利用した電子署名を文書に付与することによって、その文書が改竄されていないこと、及び文書の作成者を保証することができる。しかし、この方式では、文書の一部を変更した場合、変更後の文書に新たな電子署名を付与することによって、変更後の文書全体の完全性を保証することはできるが、変更されていない部分が元の文書から引き継いだものであることを保証することはできない。
【０００３】
そこで、文書の一部が変更された場合に、変更後の文書の完全性を保証すると共に、変更されていない部分が元の文書から引き継いだものであることを保証（以下、部分完全性保証と呼ぶ）するための技術として、例えばＰＩＡＴ（Partial Integrity Assurance Technology）と呼ばれる技術が従来から存在する。ＰＩＡＴでは、文書を予めいくつかのブロックに分割しておき、各ブロックに対して完全性を保証するようになっている。これにより、変更後の文書の完全性だけでなく、変更されていないブロックが元の文書から引き継いだものであることを保証することができる。なお、ＰＩＡＴでは、図１に示すように、署名者が文書を作成する署名フェーズと、変更者が文書に変更を加える変更フェーズと、検証者が変更後の文書を受け取り、検証を行う検証フェーズの３つのフェーズに分かれている。図１に示すように、変更者は複数人いる場合もあり、複数回変更を加える場合もある。また、署名者が変更者となる場合もある。さらに、誰が検証者になってもよい。
【０００４】
従来のＰＩＡＴの代表的な方式としては、ＳＣＣＳ（Source Code Control System）型とＲＣＳ（Revision Control System）型の２つの方式が存在する。例えば、ＳＣＣＳ型では、図２に示すように、署名フェーズにおいて、署名者により作成された文書Ｍは、複数のブロック（図２では、ｍ₁〜ｍ₅）に分割され、各ブロックに対するハッシュ値（図２では、ｈ₁〜ｈ₅）が計算される。そして、各ブロックのハッシュ値を含むハッシュ値リストに対する電子署名σ₀が生成される。なお、ハッシュ値リストと電子署名σ₀とは、検証者に公開される。
【０００５】
そして、変更フェーズにおいて、変更者１が署名者から文書Ｍを受け取り、例えばブロックｍ₃をブロックｍ₃’に変更したものとする。そうすると、ブロックｍ₃’に対するハッシュ値ｈ₃’が計算され、変更者の識別番号（１）と変更位置番号（３）と当該ハッシュ値（ｈ₃’）とを含むデータ（以下、公開ハッシュ値と呼ぶ）に対する電子署名σ₁が生成される。なお、公開ハッシュ値（１，３，ｈ₃’）と電子署名σ₁とは、検証者に公開される。
【０００６】
また、同じく変更フェーズにおいて、変更者２が変更者１から文書Ｍ’を受け取り、例えばブロックｍ₄をブロックｍ₄’に変更したものとする。そうすると、ブロックｍ₄’に対するハッシュ値ｈ₄’が計算され、変更者の識別番号（２）と変更位置番号（４）と当該ハッシュ値（ｈ₄’）とを含む公開ハッシュ値に対する電子署名σ₂が生成される。なお、変更後の文書Ｍ”と公開ハッシュ値（２，４，ｈ₄’）と電子署名σ₂とは、検証者に公開される。
【０００７】
そして、図３に示すように、ＳＣＣＳ型では、検証フェーズにおいて、検証者は、ハッシュ値リストと、電子署名σ₀と、公開ハッシュ値（１，３，ｈ₃’）と、電子署名σ₁と、公開ハッシュ値（２，４，ｈ₄’）と、電子署名σ₂と、変更後の文書Ｍ”とを受け取る。そして、第１の検証段階として、変更者２によって行われた変更内容の検証が行われる。具体的には、まず、文書Ｍ”に含まれる各ブロックに対するハッシュ値（図３では、ｈ₁、ｈ₂、ｈ₃’、ｈ₄’及びｈ₅）が計算される。次に、電子署名σ₂の検証が行われ、検証に成功した場合には、公開ハッシュ値（２，４，ｈ₄’）を用いて、４番目のブロックの検証が行われる。例えば、先に計算されたハッシュ値ｈ₄’と、公開ハッシュ値に含まれるハッシュ値ｈ₄’とが一致すれば、検証成功と判断される。なお、４番目のハッシュ値ｈ₄’は、ハッシュ値リストに含まれるハッシュ値ｈ₄に置き換えられる。
【０００８】
そして、第２の検証段階として、変更者１によって行われた変更内容の検証が行われる。具体的には、電子署名σ₁の検証が行われ、検証に成功した場合には、公開ハッシュ値（１，３，ｈ₃’）を用いて、３番目のブロックの検証が行われる。例えば、先に計算されたハッシュ値ｈ₃’と、公開ハッシュ値に含まれるハッシュ値ｈ₃’とが一致すれば、検証成功と判断される。なお、３番目のハッシュ値ｈ₃’は、ハッシュ値リストに含まれるハッシュ値ｈ₃に置き換えられる。
【０００９】
そして、第３の検証段階では、第１及び第２の検証段階においてハッシュ値ｈ₃及びｈ₄への置き換えが行われたハッシュ値リストを用いて、電子署名σ₀の検証が行われる。そして、検証に成功した場合には、署名者から公開されたハッシュ値リストをさらに用いてブロックの検証が行われる。これにより、変更後の文書Ｍ”に含まれるブロックｍ₄’は、変更者２によって変更されたものであることが保証され、ブロックｍ₃’は、変更者１によって変更されたものであることが保証される。さらに、変更されなかったブロックについては文書Ｍから引き継いだものであることが保証される。
【００１０】
また、例えばＲＣＳ型では、図４に示すように、ＳＣＣＳ型と同様に、署名フェーズにおいて、署名者により作成された文書Ｍは、複数のブロック（図４では、ｍ₁〜ｍ₅）に分割され、各ブロックに対するハッシュ値（図４では、ｈ₁〜ｈ₅）が計算される。そして、各ブロックのハッシュ値を含むハッシュ値リストに対する電子署名σ₀が生成される。なお、電子署名σ₀は、検証者に公開される。ＲＣＳ型では、署名フェーズにおいて計算されたハッシュ値（ｈ₁〜ｈ₅）は、検証者には公開されない。
【００１１】
そして、変更フェーズにおいて、変更者１が署名者から文書Ｍを受け取ると、文書Ｍに含まれる各ブロック対するハッシュ値（ｈ₁〜ｈ₅）が計算され、ハッシュ値リストが生成される。そして、例えば、変更者１がブロックｍ₃をブロックｍ₃’に変更したものとする。そうすると、変更者の識別番号（１）と、変更位置番号（３）と、変更前のブロックｍ₃のハッシュ値（ｈ₃）とを含む公開ハッシュ値が生成される。そして、変更後のブロックｍ₃’に対するハッシュ値ｈ₃’が計算され、ハッシュ値リストのハッシュ値ｈ₃がハッシュ値ｈ₃’に置き換えられる。そして、このハッシュ値リストと、公開ハッシュ値とに対する電子署名σ₁が生成される。なお、公開ハッシュ値（１，３，ｈ₃）と電子署名σ₁とは、検証者に公開される。
【００１２】
また、同じく変更フェーズにおいて、変更者２が変更者１から文書Ｍ’を受け取ると、文書Ｍ’に含まれる各ブロック対するハッシュ値（ｈ₁、ｈ₂、ｈ₃’、ｈ₄及びｈ₅）が計算され、ハッシュ値リストが生成される。そして、例えば、変更者２がブロックｍ₄をブロックｍ₄’に変更したものとする。そうすると、変更者の識別番号（２）と、変更位置番号（４）と、変更前のブロックｍ₄のハッシュ値（ｈ₄）とを含む公開ハッシュ値が生成される。そして、変更後のブロックｍ₄’に対するハッシュ値ｈ₄’が計算され、ハッシュ値リストのハッシュ値ｈ₄がハッシュ値ｈ₄’に置き換えられる。そして、このハッシュ値リストと、公開ハッシュ値とに対する電子署名σ₂が生成される。なお、公開ハッシュ値（２，４，ｈ₄）と電子署名σ₂とは、検証者に公開される。
【００１３】
そして、図５に示すように、ＲＣＳ型では、検証フェーズにおいて、検証者は、電子署名σ₀と、公開ハッシュ値（１，３，ｈ₃）と、電子署名σ₁と、公開ハッシュ値（２，４，ｈ₄）と、電子署名σ₂と、変更後の文書Ｍ”とを受け取る。そして、第１の検証段階として、変更者２によって行われた変更内容の検証が行われる。具体的には、まず、文書Ｍ”に含まれる各ブロックに対するハッシュ値（図５では、ｈ₁、ｈ₂、ｈ₃’、ｈ₄’及びｈ₅）が計算され、ハッシュ値リストが生成される。そして、このハッシュ値リストと、公開ハッシュ値（２，４，ｈ₄）とを用いて、電子署名σ₂の検証が行われ、検証に成功した場合には、４番目のブロックのハッシュ値ｈ₄’が、公開ハッシュ値に含まれるハッシュ値ｈ₄に置き換えられる。
【００１４】
そして、第２の検証段階として、変更者１によって行われた変更内容の検証が行われる。具体的には、第１の検証段階においてハッシュ値ｈ₄への置き換えが行われたハッシュ値リストと、公開ハッシュ値（１，３，ｈ₃）とを用いて、電子署名σ₁の検証が行われ、検証に成功した場合には、３番目のブロックのハッシュ値ｈ₃’が、公開ハッシュ値に含まれるハッシュ値ｈ₃に置き換えられる。
【００１５】
そして、第３の検証段階では、第１及び第２の検証段階においてハッシュ値ｈ₃及びｈ₄への置き換えが行われたハッシュ値リストを用いて、電子署名σ₀の検証が行われる。これにより、ＳＣＣＳ型と同様に、変更されたブロックを保証すると共に、変更されなかったブロックについては文書Ｍから引き継いだものであることが保証される。
【００１６】
なお、図６に示すように、文書がｎ個のブロックに分割されている際に、ｍ人の変更者によってｄ箇所の変更が行われた場合、従来のＳＣＣＳ型では、検証時、ｎ個のメッセージと、ｎ＋ｄ個のハッシュ値と、ｍ＋１個の電子署名とが必要となる。また、再変更時に元の電子署名の検証が必要となる。また、従来のＲＣＳ型では、ハッシュ値がｄ個となる以外は、ＳＣＣＳ型と同様である。
【００１７】
このように、従来のＰＩＡＴでは、文書の一部のブロックを変更した場合に、変更後の文書の完全性を保証すると共に、変更されていない部分が元の文書から引き継いだものであることを保証できる。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】国際公開第２００６／００８８４７号
【特許文献２】特開２００７−２１３５４９号公報
【非特許文献】
【００１９】
【非特許文献１】武仲正彦，伊豆哲也，吉岡孝司，「電子文書の訂正・流通を考慮した部分完全性保証方式の改良（その２）」，SCIS2006，2B2-4，Jan.2006
【発明の概要】
【発明が解決しようとする課題】
【００２０】
一方で、変更者が、文書、動画、写真、音楽などのコンテンツの最後にブロックを追加したり、コンテンツの途中にブロックを挿入したりする場合もある。例えば、図７に示すように、変更者によってコンテンツの最後に新たなブロックｍ₆が追加された場合、変更フェーズでは、ブロックｍ₆に対するハッシュ値ｈ₆’が計算され、追加された１ブロック分の公開ハッシュ値と、その公開ハッシュ値に対する電子署名σ₁とが生成される。なお、図７は、ブロック追加時におけるＳＣＣＳ型の全体的な流れを示している。
【００２１】
そして、図７に示すように、検証フェーズでは、署名フェーズで生成されたハッシュ値リスト及び電子署名σ₀と、変更フェーズで生成された１ブロック分の公開ハッシュ値及び電子署名σ₁と、ブロック追加後のコンテンツとを用いて検証が行われる。具体的には、まずブロック追加後のコンテンツに含まれる各ブロックのハッシュ値が計算される。そして、電子署名σ₁の検証が行われ、検証に成功した場合には、公開ハッシュ値（１，６，ｈ₆’）を用いて、６番目の追加ブロックの検証が行われる。また、電子署名σ₀の検証が行われ、検証に成功した場合には、元のコンテンツに含まれる各ブロックの検証が行われる。これにより、追加ブロックｍ₆は、変更者１によって追加されたものであることが保証され、ブロックｍ₁〜ｍ₅については、元のコンテンツから引き継いだものであることが保証される。
【００２２】
しかしながら、従来のＰＩＡＴでは、変更者によってコンテンツの途中に新たなブロックが挿入された場合、挿入ブロックより後方の各ブロックは、内容自体に変更はないが、位置がずれたことで、変更扱いとなってしまう。例えば図８に、ブロック挿入時におけるＳＣＣＳ型の全体的な流れを示す。図８に示すように、ブロックｍ₆が３番目の位置に挿入された場合、変更フェーズでは、挿入ブロック以降の４つのブロックの各々について、ハッシュ値（図８では、ｈ₃’〜ｈ₆’）が計算され、公開ハッシュ値が生成されることになる。そのため、例えば、ブロック数の多い動画ファイルなどに対してブロックを挿入する場合、部分完全性保証のために必要となる公開ハッシュ値のデータ量が膨大になってしまう。
【００２３】
また、図８に示すように、ブロックが挿入された場合、検証フェーズでは、公開ハッシュ値を用いて、挿入ブロック以降の各ブロックの検証が行われるようになっている。そのため、従来のＰＩＡＴでは、挿入ブロックより後方の各ブロックは実際には変更していないにもかかわらず、変更されたものと扱われてしまうため、元のコンテンツから引き継いだものであることを保証することができないという問題もある。
【００２４】
従って、本技術の目的は、コンテンツにブロックを挿入する場合でも、公開ハッシュ値のデータ量を抑えつつ、コンテンツの部分完全性保証を実現できるようにすることである。
【課題を解決するための手段】
【００２５】
第１の態様に係るコンテンツ処理装置は、更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、更新ブロックに対するハッシュ値を計算する第１ハッシュ値計算手段と、管理データ格納部から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と、更新位置と、更新ブロックに対するハッシュ値と、更新種別とを含む更新記録情報に対して、秘密鍵を用いて電子署名を生成する署名手段と、更新済みコンテンツと更新記録情報と電子署名とを出力する出力手段とを有する。
【００２６】
第２の態様に係るコンテンツ処理装置は、更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、生成した更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成手段と、管理データ格納部から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と更新位置と更新種別とを含む更新記録情報と、ハッシュ値リストとに対して、秘密鍵を用いて電子署名を生成する署名手段と、更新済みコンテンツと更新記録情報と電子署名とを出力する出力手段とを有する。
【発明の効果】
【００２７】
コンテンツにブロックを挿入する場合でも、公開ハッシュ値のデータ量を抑えつつ、コンテンツの部分完全性保証を実現できるようになる。
【図面の簡単な説明】
【００２８】
【図１】図１は、ＰＩＡＴの各フェーズを示す図である。
【図２】図２は、従来のＳＣＣＳ型ＰＩＡＴの署名及び変更フェーズにおける動作を説明するための図である。
【図３】図３は、従来のＳＣＣＳ型ＰＩＡＴの検証フェーズにおける動作を説明するための図である。
【図４】図４は、従来のＲＣＳ型ＰＩＡＴの署名及び検証フェーズにおける動作を説明するための図である。
【図５】図５は、従来のＲＣＳ型ＰＩＡＴの検証フェーズにおける動作を説明するための図である。
【図６】図６は、従来のＰＩＡＴ（ＳＣＣＳ型及びＲＣＳ型）において必要となるデータを示す図である。
【図７】図７は、従来のＳＣＣＳ型ＰＩＡＴにおけるブロック追加時の流れを示す図である。
【図８】図８は、従来のＳＣＣＳ型ＰＩＡＴにおけるブロック挿入時の流れを示す図である。
【図９】図９は、第１の実施の形態（ＳＣＣＳ型ＰＩＡＴ：方式１）におけるブロック挿入時の流れを示す図である。
【図１０】図１０は、本技術の実施の形態に係るシステム構成図である。
【図１１】図１１は、第１乃至第３の実施の形態における署名者端末の機能ブロック図である。
【図１２】図１２は、署名者端末のメモリ部に含まれる各種格納部を示す図である。
【図１３】図１３は、第１及び第４の実施の形態における変更者端末の機能ブロック図である。
【図１４】図１４は、第１及び第４の実施の形態における変更者端末のメモリ部に含まれる各種格納部を示す図である。
【図１５】図１５は、検証者端末の機能ブロック図である。
【図１６】図１６は、第１及び第４の実施の形態における検証者端末のメモリ部に含まれる各種格納部を示す図である。
【図１７】図１７は、第１乃至第３の実施の形態における署名者端末の処理フローを示す図である。
【図１８】図１８は、第１の実施の形態における変更者端末の処理フローを示す図である。
【図１９】図１９は、コンテンツ変更処理１の処理フローを示す図である。
【図２０】図２０は、第１の実施の形態における検証者端末の処理フロー（第１の部分）を示す図である。
【図２１】図２１は、第１の実施の形態における検証者端末の処理フロー（第２の部分）を示す図である。
【図２２】図２２は、第２の実施の形態（ＳＣＣＳ型ＰＩＡＴ：方式２）におけるブロック挿入時の流れを示す図である。
【図２３】図２３は、第２及び第５の実施の形態における変更者端末の機能ブロック図である。
【図２４】図２４は、第２及び第５の実施の形態における変更者端末のメモリ部に含まれる各種格納部を示す図である。
【図２５】図２５は、第２及び第５の実施の形態における検証者端末のメモリ部に含まれる各種格納部を示す図である。
【図２６】図２６は、第２の実施の形態における変更者端末の処理フローを示す図である。
【図２７】図２７は、コンテンツ変更処理２の処理フローを示す図である。
【図２８】図２８は、挿入テーブルの一例を示す図である。
【図２９】図２９は、第２の実施の形態における検証者端末の処理フロー（第１の部分）を示す図である。
【図３０】図３０は、第２の実施の形態における検証者端末の処理フロー（第２の部分）を示す図である。
【図３１】図３１は、第３の実施の形態（ＳＣＣＳ型ＰＩＡＴ：方式３）におけるブロック挿入時の流れを示す図である。
【図３２】図３２は、第３及び第６の実施の形態における変更者端末の機能ブロック図である。
【図３３】図３３は、第３及び第６の実施の形態における変更者端末のメモリ部に含まれる各種格納部を示す図である。
【図３４】図３４は、第３及び第６の実施の形態における検証者端末のメモリ部に含まれる各種格納部を示す図である。
【図３５】図３５は、第３の実施の形態における変更者端末の処理フローを示す図である。
【図３６】図３６は、コンテンツ変更処理３の処理フローを示す図である。
【図３７】図３７は、第３の実施の形態における検証者端末の処理フロー（第１の部分）を示す図である。
【図３８】図３８は、第３の実施の形態における検証者端末の処理フロー（第２の部分）を示す図である。
【図３９】図３９は、第４の実施の形態（ＲＣＳ型ＰＩＡＴ：方式１）におけるブロック挿入時の流れを示す図である。
【図４０】図４０は、第４乃至第６の実施の形態における署名者端末の処理フローを示す図である。
【図４１】図４１は、第４の実施の形態における変更者端末の処理フローを示す図である。
【図４２】図４２は、コンテンツ変更処理４の処理フローを示す図である。
【図４３】図４３は、第４の実施の形態における検証者端末の処理フローを示す図である。
【図４４】図４４は、第５の実施の形態（ＲＣＳ型ＰＩＡＴ：方式２）におけるブロック挿入時の流れを示す図である。
【図４５】図４５は、第５の実施の形態における変更者端末の処理フローを示す図である。
【図４６】図４６は、コンテンツ変更処理５の処理フローを示す図である。
【図４７】図４７は、第５の実施の形態における検証者端末の処理フローを示す図である。
【図４８】図４８は、第６の実施の形態（ＲＣＳ型ＰＩＡＴ：方式３）におけるブロック挿入時の流れを示す図である。
【図４９】図４９は、第６の実施の形態における変更者端末の処理フローを示す図である。
【図５０】図５０は、コンテンツ変更処理６の処理フローを示す図である。
【図５１】図５１は、第６の実施の形態における検証者端末の処理フローを示す図である。
【図５２】図５２は、各方式による公開データ量の比較例を示す図である。
【図５３】図５３は、コンピュータの機能ブロック図である。
【図５４】図５４は、本技術の第１の態様に係るコンテンツ処理装置の機能ブロック図である。
【図５５】図５５は、本技術の第２の態様に係るコンテンツ処理装置の機能ブロック図である。
【図５６】図５６は、本技術の第３の態様に係る情報処理方法の処理フローを示す図である。
【図５７】図５７は、本技術の第４の態様に係る情報処理方法の処理フローを示す図である。
【発明を実施するための形態】
【００２９】
［実施の形態１］
第１の実施の形態では、図９に示すような流れで、ブロック挿入時の部分完全性保証を実現する。なお、第１の実施の形態は、従来のＳＣＣＳ型ＰＩＡＴを変形したものである。図９に示すように、第１の実施の形態では、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、変更者の識別子と、挿入位置番号と、そのハッシュ値とを含むデータ（以下、公開ハッシュ値と呼ぶ）を生成する。また、第１の実施の形態では、変更フェーズにおいて、図９に示すようなリンクテーブルを生成する。図９に示すリンクテーブルにおいて、先頭から３番目の番号６は、元のコンテンツに含まれるブロック数「５」より大きい値であるため、挿入済みコンテンツの３番目のブロックは変更者１によって挿入されたものであることが分かる。また、図９では、リンクテーブルから、ハッシュ値リストの１番目のハッシュ値は、挿入済みコンテンツの１番目のブロックに対応していることが分かる。同様に、ハッシュ値リストの２番目のハッシュ値は、挿入済みコンテンツの２番目のブロックに対応していることが分かる。さらに、ハッシュ値リストの３番目のハッシュ値は、挿入済みコンテンツの４番目のブロックに対応していることが分かる。また、ハッシュ値リストの４番目のハッシュ値は、挿入済みコンテンツの５番目のブロックに対応していることが分かる。さらに、ハッシュ値リストの５番目のハッシュ値は、挿入済みコンテンツの６番目のブロックに対応していることが分かる。そして、公開ハッシュ値とリンクテーブルとに対する電子署名σ₁を生成する。
【００３０】
そして、検証フェーズでは、公開ハッシュ値とリンクテーブルとを用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。一方、挿入ブロック以外のブロックについては、リンクテーブルと、署名フェーズで生成されたハッシュ値リストとを用いて検証すると共に、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。また、リンクテーブルから挿入ブロックを特定できるので、挿入ブロック以外のブロックについては公開ハッシュ値のデータを生成する必要がなくなり、従来のＳＣＣＳ型ＰＩＡＴに比べて、公開ハッシュ値のデータ量を削減できる。以下、第１の実施の形態について詳細に説明する。
【００３１】
図１０に、第１の実施の形態に係るシステム構成図を示す。例えばインターネットであるネットワーク１には、署名者により操作される署名者端末３と、変更者により操作される変更者端末５（図１０では５ａ乃至５ｃ）と、検証者により操作される検証者端末７とが接続されている。なお、図１０では、署名者端末３が１台、変更者端末５が３台、検証者端末７が１台の例を示しているが、各端末の台数は、これに限定されない。
【００３２】
図１１に、図１０に示した署名者端末３の機能ブロック図を示す。署名者端末３は、入力部３１と、出力部３２と、メモリ部３３と、分割部３４と、ハッシュ値計算部３５と、署名部３６とを有する。なお、図１２に示すように、メモリ部３３には、管理データ格納部３３１と、コンテンツ格納部３３２と、ハッシュ値格納部３３３と、電子署名格納部３３４とが含まれる。管理データ格納部３３１には、署名者の秘密鍵が予め格納される。
【００３３】
なお、入力部３１は、署名者からコンテンツ作成の操作を受け付け、署名者により作成されたコンテンツ（例えば、文書、動画、静止画、音楽など）をコンテンツ格納部３３２に格納し、コンテンツの分割要求を分割部３４に出力する。分割部３４は、入力部３１からの分割要求に応じて、コンテンツ格納部３３２に格納されているコンテンツを複数ブロックに分割する。また、分割部３４は、ハッシュ値計算要求をハッシュ値計算部３５に出力する。ハッシュ値計算部３５は、分割部３４からの要求に応じて、コンテンツ格納部３３２からコンテンツを読み出し、コンテンツに含まれる各ブロックに対するハッシュ値を計算する。そして、ハッシュ値計算部３５は、計算したハッシュ値を含むハッシュ値リストをハッシュ値格納部３３３に格納し、署名要求を署名部３６に出力する。署名部３６は、ハッシュ値計算部３５からの要求に応じて、管理データ格納部３３１とハッシュ値格納部３３３とに格納されるデータを用いて、ハッシュ値リストに対する電子署名を生成し、電子署名格納部３３４に格納する。出力部３２は、コンテンツ格納部３３２に格納されているコンテンツと、ハッシュ値格納部３３３に格納されているハッシュ値リストと、電子署名格納部３３４に格納されている電子署名を含む署名リストとを変更者端末５に出力する。
【００３４】
また、図１３に、図１０に示した変更者端末５の機能ブロック図を示す。変更者端末５は、入力部５１と、出力部５２と、メモリ部５３と、コンテンツ変更部５４と、ハッシュ値計算部５５と、署名部５６と、検証部５７と、リンクテーブル生成部５８とを有する。なお、図１４に示すように、メモリ部５３には、管理データ格納部５３１と、コンテンツ格納部５３２と、ハッシュ値格納部５３３と、電子署名格納部５３４と、リンクテーブル格納部５３５とが含まれる。管理データ格納部５３１には、変更者の識別子と秘密鍵とが予め格納される。また、管理データ格納部５３１には、署名者の公開鍵が格納される場合もある。
【００３５】
なお、入力部５１は、署名者端末３からコンテンツとハッシュ値リストと署名リストとを受信すると、コンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストをハッシュ値格納部５３３に格納し、署名リストを電子署名格納部５３４に格納する。また、入力部５１は、必要に応じて、電子署名の検証要求を検証部５７に出力する。さらに、入力部５１は、変更者からブロックの変更、追加又は挿入の操作を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。検証部５７は、入力部５１からの要求に応じて、管理データ格納部５３１に格納されるデータを用いて、署名リストに含まれる電子署名の検証処理を実施する。コンテンツ変更部５４は、入力部５１からの要求に応じて、コンテンツ格納部５３２に格納されているコンテンツにブロックの変更、追加又は挿入を行うことによりコンテンツを更新する。また、コンテンツ変更部５４は、変更、追加又は挿入されたブロックをハッシュ値計算部５５に出力したり、ブロック挿入の場合には挿入位置番号をリンクテーブル生成部５８に出力したりする。ハッシュ値計算部５５は、コンテンツ変更部５４から変更、追加又は挿入されたブロックを受信すると、そのブロックに対するハッシュ値を計算し、公開ハッシュ値を生成してハッシュ値格納部５３３に格納する。リンクテーブル生成部５８は、コンテンツ変更部５４から挿入位置番号を受信すると、後で説明するリンクテーブルを生成し、リンクテーブル格納部５３５に格納する。署名部５６は、管理データ格納部５３１とハッシュ値格納部５３３とリンクテーブル格納部５３５とに格納されるデータを用いて、公開ハッシュ値とリンクテーブルとに対する電子署名を生成し、電子署名格納部５３４に格納されている署名リストに追加する。出力部５２は、コンテンツ格納部５３２に格納されている更新後コンテンツと、ハッシュ値格納部５３３に格納されているハッシュ値リストと、電子署名格納部５３４に格納されている署名リストと、リンクテーブル格納部５３５に格納されているリンクテーブルとを他の変更者端末５又は検証者端末７に出力する。
【００３６】
また、図１５に、図１０に示した検証者端末７の機能ブロック図を示す。検証者端末７は、入力部７１と、出力部７２と、メモリ部７３と、ハッシュ値計算部７４と、ハッシュ値検証部７５と、署名検証部７６とを有する。なお、図１６に示すように、メモリ部７３には、公開鍵格納部７３１と、コンテンツ格納部７３２と、ハッシュ値格納部７３３と、電子署名格納部７３４と、リンクテーブル格納部７３５とが含まれる。なお、公開鍵格納部７３１には、署名者の公開鍵、変更者の公開鍵が格納される。
【００３７】
なお、入力部７１は、変更者端末５から更新後コンテンツとハッシュ値リストと署名リストと公開ハッシュ値リストとリンクテーブルリストとを受信すると、更新後コンテンツをコンテンツ格納部７３２に格納し、ハッシュ値リストをハッシュ値格納部７３３に格納し、署名リストを電子署名格納部７３４に格納し、リンクテーブルリストをリンクテーブル格納部７３５に格納する。ハッシュ値計算部７４は、コンテンツ格納部７３２から更新後コンテンツを読み出し、更新後コンテンツに含まれる各ブロックに対するハッシュ値を計算してハッシュ値格納部７３３に格納する。ハッシュ値検証部７５は、ハッシュ値格納部７３３とリンクテーブル格納部７３５とに格納されるデータを用いて、各ブロックの検証処理を実施する。署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４とに格納されるデータを用いて、署名リストに含まれる電子署名の検証処理を実施する。出力部７２は、検証結果を表示装置等に出力する。
【００３８】
次に、図１７を用いて、第１の実施の形態における署名者端末３の処理について説明する。まず、署名者が、署名者端末３を操作して、文書、動画、静止画、音楽などのコンテンツを作成する（図１７：ステップＳ１）。なお、本ステップは、署名者の動作であるため、図１７では点線ブロックで示している。そして、入力部３１は、署名者からコンテンツ作成の操作を受け付け、署名者によって作成されたコンテンツをコンテンツ格納部３３２に格納する。その後、入力部３１は、コンテンツの分割要求を分割部３４に出力する。なお、分割要求には、作成されたコンテンツのファイル名などが含まれる。
【００３９】
そして、分割部３４は、入力部３１から分割要求を受信すると、コンテンツ格納部３３２に格納されているコンテンツをｎ個のブロックに分割する（ステップＳ３）。なお、コンテンツをＭ、分割後のブロックをｍとすると、Ｍ＝｛ｍ₁，・・・，ｍ_n｝となる。例えば図９では、コンテンツが、ブロックｍ₁からブロックｍ₅までの５個のブロックに分割される。そして、分割部３４は、ハッシュ値計算要求をハッシュ値計算部３５に出力する。なお、ハッシュ値計算要求には、コンテンツのファイル名などが含まれる。
【００４０】
そして、ハッシュ値計算部３５は、分割部３４からハッシュ値計算要求を受信すると、コンテンツ格納部３３２からハッシュ値計算要求に係るコンテンツを読み出す。そして、読み出したコンテンツに含まれるｎ個のブロックの各々に対するハッシュ値を計算し、計算したｎ個のハッシュ値を含むハッシュ値リストＨ₀を生成する（ステップＳ５）。なお、ハッシュ値をｈとすると、Ｈ₀＝｛ｈ₁，・・・，ｈ_n｝となる。また、ハッシュ値リストＨ₀は、ハッシュ値格納部３３３に格納される。例えば図９では、ハッシュ値ｈ₁からハッシュ値ｈ₅までの５個のハッシュ値が計算され、この５個のハッシュ値を含むハッシュ値リストＨ₀が生成される。その後、ハッシュ値計算部３５は、署名対象となるハッシュ値リストＨ₀の指定を含む署名要求を署名部３６に出力する。
【００４１】
そして、署名部３６は、ハッシュ値計算部３５から署名要求を受信すると、管理データ格納部３３１から署名者の秘密鍵を読み出し、さらにハッシュ値格納部３３３から署名要求に係るハッシュ値リストＨ₀を読み出す。そして、署名部３６は、秘密鍵を用いて、ハッシュ値リストＨ₀に対する電子署名σ₀を生成する（ステップＳ７）。この際、署名部３６は、署名リストΣ＝｛σ₀｝として電子署名格納部３３４に格納する。
【００４２】
その後、出力部３２が、コンテンツ格納部３３２に格納されているコンテンツと、ハッシュ値格納部３３３に格納されているハッシュ値リストＨ₀と、電子署名格納部３３４に格納されている署名リストΣとを読み出し、変更者端末５に出力する（ステップＳ９）。そして、処理を終了する。
【００４３】
次に、図１８及び図１９を用いて、第１の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ、ハッシュ値リストＨ₀及び署名リストΣを受信する（図１８：ステップＳ１１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀をハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力する。
【００４４】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ１３）。例えば、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、これらのハッシュ値と署名者の公開鍵とを用いて、電子署名σ₀を検証する。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【００４５】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ１５）。なお、本ステップは、変更者の動作であるため、図１８では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【００４６】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及びリンクテーブル生成部５８と連携して、コンテンツ変更処理１を実施する（ステップＳ１７）。コンテンツ変更処理１については図１９を用いて説明する。
【００４７】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図１９：ステップＳ３１）。操作種別がブロックの変更である場合（ステップＳ３１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３３）。具体的には、コンテンツ更新要求に含まれるブロック番号のブロックを変更ブロックの内容に変更する。その後、ステップＳ４９の処理に移行する。
【００４８】
一方、操作種別がブロックの変更ではない場合（ステップＳ３１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ３５）。操作種別がブロックの追加である場合（ステップＳ３５：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３７）。その後、ステップＳ４９の処理に移行する。
【００４９】
一方、操作種別がブロックの追加ではない場合（ステップＳ３５：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ３９）。操作種別がブロックの挿入である場合（ステップＳ３９：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ４１）。例えば、コンテンツＭ＝｛ｍ₁，ｍ₂，ｍ₃，ｍ₄，ｍ₅｝の３番目に新たなブロックｍ₆を挿入しようとする場合に、本ステップの処理を実施すると、コンテンツＭ＝｛ｍ₁，ｍ₂，ｍ₃，ｍ₄，ｍ₅，ｍ₅｝となる。
【００５０】
そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ４３）。但し、挿入前のコンテンツにおける最終ブロックは除く。例えば、上の例では、ブロックｍ₄を５番目の位置に移動し、ブロックｍ₃を４番目の位置に移動する。従って、コンテンツＭ＝｛ｍ₁，ｍ₂，ｍ₃，ｍ₃，ｍ₄，ｍ₅｝となる。
【００５１】
そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ４５）。例えば、上の例では、ブロックｍ₆を３番目に挿入する。従って、コンテンツＭ＝｛ｍ₁，ｍ₂，ｍ₆，ｍ₃，ｍ₄，ｍ₅｝となり、図９に示したような挿入済みコンテンツとなる。また、コンテンツ変更部５４は、ブロックの挿入位置番号をリンクテーブル生成部５８に通知する。
【００５２】
そして、リンクテーブル生成部５８は、コンテンツ変更部５４から挿入位置番号を受信すると、リンクテーブル格納部５３５におけるリンクテーブルＬ_kに、挿入ブロックの番号を設定する（ステップＳ４７）。具体的には、以下のような処理を実施する。まず、リンクテーブル格納部５３５にリンクテーブルＬ_kが格納されているか判断し、格納されていなければ、初回の処理であると判断し、リンクテーブルＬ_kを生成する。例えば、挿入前のブロックの数がｎ個であった場合、リンクテーブルＬ_k＝｛１，２，・・・，ｎ｝を生成する。そして、リンクテーブルＬ_kを生成した後、又は、２回目以降の処理の場合、現時点のリンクテーブルＬ_kで最も大きい番号を特定し（初回処理時であればｎ）、その番号の次の番号（初回処理時であればｎ＋１）を挿入ブロックの番号として、リンクテーブルＬ_kに設定する。例えば、図９に示したように、挿入位置が３である場合には、リンクテーブルＬ_kの３番目に挿入ブロックの番号設定する。従って、リンクテーブルＬ_kは、Ｌ_k＝｛１，２，６，３，４，５｝となる。その後、ステップＳ４９の処理に移行する。
【００５３】
一方、ステップＳ３９において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ３９：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【００５４】
そして、ハッシュ値計算部５５は、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ４９）。なお、計算対象となるブロックの位置は、コンテンツ変更部５４から通知される。例えば図９では、先頭から３番目の位置に挿入されたブロックｍ₆に対するハッシュ値ｈ₆が計算される。
【００５５】
そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ５１）。本実施の形態では、変更者の識別子をｋ、ブロック番号をｉ、ハッシュ値をｈ_n+1、挿入前のブロック数をｎとして、ｖ＝（ｋ，ｉ，ｈ_n+1）で表す。なお、一人の変更者によって複数のブロックが挿入される場合もあり、その場合には、各挿入ブロックについて公開ハッシュ値ｖが生成されることとなる。本実施の形態では、挿入ブロックの数をｐとした場合、公開ハッシュ値Ｖ_k＝｛ｖ₁，・・・，ｖ_p｝と表す。例えば図９では、変更者１によって挿入されたブロックは１個であるので、公開ハッシュ値Ｖ₁＝｛ｖ｝となり、ｖ＝（１，３，ｈ₆）となる。その後、本処理を終了し、元の処理に戻る。
【００５６】
図１８の説明に戻って、コンテンツ変更処理１（ステップＳ１７）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ１９）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ１９：Ｎｏルート）、ステップＳ１５の処理に戻り、上で述べた処理を繰り返す。
【００５７】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ１９：Ｙｅｓルート）、ステップＳ２１の処理に移行する。この際、入力部５１は、署名対象となる公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kの指定を含む署名要求を署名部５６に出力する。
【００５８】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出し、リンクテーブル格納部５３５からリンクテーブルＬ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出した公開ハッシュ値Ｖ_kとリンクテーブルＬ_kとに対する電子署名σ_kを生成する（ステップＳ２１）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図９では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【００５９】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ₀及び公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出し、リンクテーブル格納部５３５からリンクテーブルＬ_kを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加し、リンクテーブルＬ_kをリンクテーブルリストＬに追加する。一人目の変更者の場合、公開ハッシュ値リストＶは、Ｖ＝｛Ｖ_k｝となり、リンクテーブルリストＬは、Ｌ＝｛Ｌ_k｝となる。そして、出力部５２は、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを他の変更者端末５又は検証者端末７に出力する（ステップＳ２３）。そして、処理を終了する。
【００６０】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ１１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納し、リンクテーブルリストＬをリンクテーブル格納部５３５に格納するようにすればよい。
【００６１】
また、ステップＳ２３では、出力部５２は、受信した公開ハッシュ値リストＶに、公開ハッシュ値Ｖ_kを追加するようにすればよい。すなわち、Ｖ＝｛・・・，Ｖ_k｝となる。さらに、出力部５２は、受信したリンクテーブルリストＬに、リンクテーブルＬ_kを追加するようにすればよい。すなわち、Ｌ＝｛・・・，Ｌ_k｝となる。
【００６２】
以上のような処理を実施することにより、挿入ブロックを特定するためのリンクテーブルを生成することができる。なお、挿入ブロックより後方の各ブロックについては公開ハッシュ値を生成しないようになっているので、動画ファイルに対してブロックを挿入する場合でも、公開ハッシュ値のデータ量が膨大になることはない。
【００６３】
次に、図２０及び図２１を用いて、第１の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを受信する（図２０：ステップＳ６１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納し、リンクテーブルリストＬをリンクテーブル格納部７３５に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【００６４】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値格納部７３３に格納する（ステップＳ６３）。例えば図９では、ハッシュ値ｈ₁、ｈ₂、ｈ₆、ｈ₃、ｈ₄及びｈ₅が計算される。また、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【００６５】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ６５）。例えば、変更フェーズでは、変更を行った順番に、公開ハッシュ値Ｖ_kが、公開ハッシュ値リストＶに追加されていく。従って、公開ハッシュ値リストＶに含まれる公開ハッシュ値Ｖ_kを逆順で辿ることで、最終変更者から順に変更者ｋを特定することができる。
【００６６】
そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４とリンクテーブル格納部７３５とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から電子署名σ_kを読み出し、リンクテーブル格納部７３５からリンクテーブルＬ_kを読み出す。そして、署名検証部７６は、公開鍵と公開ハッシュ値Ｖ_kとリンクテーブルＬ_kとを用いて、電子署名σ_kの検証処理を実施する（ステップＳ６７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【００６７】
そして、ステップＳ６７における検証に失敗した場合（ステップＳ６９：Ｎｏルート）、端子Ａを介してステップＳ９１（図２１）の処理に移行する。
【００６８】
一方、ステップＳ６７における検証に成功した場合（ステップＳ６９：Ｙｅｓルート）、署名検証部７６は、公開ハッシュ値を検証するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kなどを通知する。なお、ステップＳ６７における検証に成功したということは、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kについて、変更者ｋが作成者であり、さらに偽造・改竄されていないことが証明されたことを意味する。
【００６９】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kを受信する。そして、ハッシュ値検証部７５は、公開ハッシュ値Ｖ_kにおいて、最後に挿入されたブロックの公開ハッシュ値ｖから順に未処理の公開ハッシュ値ｖを特定する（ステップＳ７１）。なお、変更者端末５についての説明の際に述べたように、公開ハッシュ値Ｖ_kには、変更者ｋによって挿入されたブロック数分の公開ハッシュ値ｖが含まれる。公開ハッシュ値ｖは挿入順に並んでいるので、本ステップでは、後ろから順に公開ハッシュ値ｖを特定する。
【００７０】
そして、ハッシュ値検証部７５は、リンクテーブルＬ_kを用いて、特定した公開ハッシュ値に対応する挿入ブロックを特定する（ステップＳ７２）。なお、ステップＳ７１では、挿入順の逆順で公開ハッシュ値ｖが特定されるので、本ステップにおいても、リンクテーブルＬ_kから、挿入順の逆順で挿入ブロックを特定するようにする。例えば、変更者ｋにより、５個のブロックを含むコンテンツに２個のブロックが挿入された際のリンクテーブルＬ_kが、Ｌ_k＝｛１，２，６，３，４，７，５｝であった場合、初回の処理では、先頭から６番目の番号「７」が特定され、挿入済みコンテンツにおける６番目のブロックが特定される。さらに、２回目の処理では、先頭から３番目の番号「６」が特定され、挿入済みコンテンツにおける３番目のブロックが特定される。このように、番号の大きいものから順に辿っていく。
【００７１】
そして、ハッシュ値検証部７５は、特定した公開ハッシュ値を用いて、特定した挿入ブロックに対するハッシュ値の検証処理を実施する（ステップＳ７３）。ここでは、挿入ブロックに対するハッシュ値を検証することによって、その挿入ブロックの正当性を確認する。具体的には、ステップＳ６３において計算され且つ当該挿入ブロックに対するハッシュ値と、公開ハッシュ値ｖに含まれるハッシュ値とを比較し、ハッシュ値が一致すれば、検証成功と判断する。例えば、図９の例では、ステップＳ７２において３番目のブロックが特定され、３番目のブロックｍ₆に対応するハッシュ値ｈ₆と、公開ハッシュ値に含まれるハッシュ値ｈ₆とが比較される。
【００７２】
そして、ステップＳ７３における検証に失敗した場合（ステップＳ７５：Ｎｏルート）、すなわちハッシュ値が一致しなかった場合、端子Ａを介してステップＳ９１（図２１）の処理に移行する。
【００７３】
一方、ステップＳ７３における検証に成功した場合（ステップＳ７５：Ｙｅｓルート）、ステップＳ７７の処理に移行する。なお、ステップＳ７３における検証に成功したということは、挿入ブロックの正当性が確認できたということを意味する。
【００７４】
そして、ハッシュ値検証部７５は、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了したか判断する（ステップＳ７７）。特定された変更者ｋによって挿入された挿入ブロックに係るハッシュ値ｖの全てについて処理が完了していなければ（ステップＳ７７：Ｎｏルート）、ステップＳ７１の処理に戻り、上で述べた処理を繰り返す。
【００７５】
一方、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了した場合（ステップＳ７７：Ｙｅｓルート）、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。そして、処理は、端子Ｂを介してステップＳ７９（図２１）に移行する。
【００７６】
図２１の説明に移行して、端子Ｂの後、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（図２１：ステップＳ７９）。全ての変更者について処理が完了していなければ（ステップＳ７９：Ｎｏルート）、端子Ｃを介してステップＳ６５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。
【００７７】
一方、全ての変更者について処理が完了した場合（ステップＳ７９：Ｙｅｓルート）、署名検証部７６は、挿入ブロック以外の各ブロックを検証するようハッシュ値検証部７５に指示する。
【００７８】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示を受信すると、ハッシュ値格納部７３３に格納されているハッシュ値リストＨ₀を用いて、挿入ブロック以外の各ブロックに対するハッシュ値の検証処理を実施する（ステップＳ８１）。ここでは、挿入ブロック以外の各ブロックに対するハッシュ値の検証を行うことによって、挿入ブロック以外の各ブロックの正当性を確認する。具体的には、ステップＳ６３において計算されたハッシュ値のうち、挿入ブロック以外の各ブロックに対するハッシュ値と、ハッシュ値リストＨ₀に含まれるハッシュ値とを比較する。この際、どれとどれを比較するかは、リンクテーブルＬから特定される。例えば、図９の例では、リンクテーブルＬから、挿入済みコンテンツの１番目のブロックｍ₁は、元のコンテンツの１番目のブロックであることが分かる。従って、ブロックｍ₁に対するハッシュ値ｈ₁と、ハッシュ値リストＨ₀に含まれる１番目のハッシュ値ｈ₁とが比較される。また、挿入済みコンテンツの２番目のブロックｍ₂は、元のコンテンツの２番目のブロックであることが分かる。従って、ブロックｍ₂に対するハッシュ値ｈ₂と、ハッシュ値リストＨ₀に含まれる２番目のハッシュ値ｈ₂とが比較される。さらに、挿入済みコンテンツの３番目のブロックｍ₆は、挿入ブロックであることが分かる。すなわち、ブロックｍ₆については、本ステップの対象外となる。また、挿入済みコンテンツの４番目のブロックｍ₃は、元のコンテンツの３番目のブロックであったことが分かる。従って、ブロックｍ₃に対するハッシュ値ｈ₃と、ハッシュ値リストＨ₀に含まれる３番目のハッシュ値ｈ₃とが比較される。さらに、挿入済みコンテンツの５番目のブロックｍ₄は、元のコンテンツの４番目のブロックであったことが分かる。従って、ブロックｍ₄に対するハッシュ値ｈ₄と、ハッシュ値リストＨ₀に含まれる４番目のハッシュ値ｈ₄とが比較される。また、挿入済みコンテンツの６番目のブロックｍ₅は、元のコンテンツの５番目のブロックであったことが分かる。従って、ブロックｍ₅に対するハッシュ値ｈ₅と、ハッシュ値リストＨ₀に含まれる５番目のハッシュ値ｈ₅とが比較される。そして、比較した結果、挿入ブロック以外の全てのブロックについて、ハッシュ値が一致すれば、検証成功と判断する。
【００７９】
そして、ステップＳ８１における検証に成功した場合（ステップＳ８３：Ｙｅｓルート）、ハッシュ値検証部７５は、検証が完了した旨を署名検証部７６に通知する。なお、ステップＳ８１における検証に成功したということは、挿入ブロック以外の各ブロックの正当性が確認できたということを意味する。そして、処理は、ステップＳ８５に移行する。
【００８０】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、公開鍵格納部７３１から署名者の公開鍵を読み出し、ハッシュ値格納部７３３からハッシュ値リストＨ₀を読み出し、電子署名格納部７３４から署名リストΣを読み出す。そして、署名検証部７６は、署名者の公開鍵とハッシュ値リストＨ₀とを用いて、署名リストΣに含まれる署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ８５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【００８１】
そして、ステップＳ８５における検証に成功した場合（ステップＳ８７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ８９）。そして、処理を終了する。
【００８２】
一方、ステップＳ８１における検証に失敗した場合（ステップＳ８３：Ｎｏルート）、ステップＳ８５における検証に失敗した場合（ステップＳ８７：Ｎｏルート）、又は、端子Ａの後、出力部７２は、検証失敗を表示装置等に出力する（ステップＳ９１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【００８３】
以上のようにＳＣＣＳ型ＰＩＡＴを変形することにより、ブロック挿入時においても、コンテンツの部分完全性保証を実現することができるようになる。すなわち、検証に成功した場合には、挿入後のコンテンツの完全性を証明すると共に、挿入ブロック以外のブロックが元のコンテンツから引き継いだものであることが保証される。
【００８４】
［実施の形態２］
次に、第２の実施の形態について説明する。第２の実施の形態では、図２２に示すような流れで、ブロック挿入時の部分完全性保証を実現する。なお、第２の実施の形態は、第１の実施の形態を変形したものであり、おおまかな流れは第１の実施の形態と同じである。第２の実施の形態では、リンクテーブルの代わりに挿入テーブルを用いる。
【００８５】
図２２に示すように、第２の実施の形態では、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、変更者の識別子と、挿入位置番号と、そのハッシュ値とを含む公開ハッシュ値を生成する。そして、第２の実施の形態では、変更フェーズにおいて、図２２に示すような挿入テーブルを生成する。挿入テーブルには、挿入位置番号が含まれる。そして、公開ハッシュ値と挿入テーブルとに対する電子署名σ₁を生成する。
【００８６】
そして、検証フェーズでは、公開ハッシュ値と挿入テーブルとを用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。そして、検証に成功した場合、第２の実施の形態では、挿入ブロックに対するハッシュ値ｈ₆を取り除く。その後、挿入ブロックに対するハッシュ値を取り除いたハッシュ値と、署名フェーズで生成されたハッシュ値とを用いて、挿入ブロック以外のブロックを検証すると共に、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。また、挿入テーブルは、リンクテーブルより小さなデータであるため、第１の実施の形態の場合よりも、データ量を削減することができる。以下、第２の実施の形態について詳細に説明する。
【００８７】
第２の実施の形態に係るシステム構成は、図１０に示したシステム構成図と同じである。また、本実施の形態における署名者端末３の構成は、図１１及び図１２に示したブロック図と同じである。
【００８８】
図２３に、本実施の形態における変更者端末５の機能ブロック図を示す。本実施の形態における変更者端末５は、入力部５１と、出力部５２と、メモリ部５３と、コンテンツ変更部５４と、ハッシュ値計算部５５と、署名部５６と、検証部５７と、挿入テーブル生成部５９とを有する。なお、入力部５１と、出力部５２と、メモリ部５３と、コンテンツ変更部５４と、ハッシュ値計算部５５と、署名部５６と、検証部５７とは、基本的には第１の実施の形態と同じものであるが、本実施の形態では、メモリ部５３には、図２４に示すような各種格納部が含まれる。具体的には、メモリ部５３には、管理データ格納部５３１と、コンテンツ格納部５３２と、ハッシュ値格納部５３３と、電子署名格納部５３４と、挿入テーブル格納部５３６とが含まれる。なお、管理データ格納部５３１と、コンテンツ格納部５３２と、ハッシュ値格納部５３３と、電子署名格納部５３４とは、第１の実施の形態と同じものである。
【００８９】
本実施の形態では、コンテンツ変更部５４が、挿入位置番号を挿入テーブル生成部５９に出力する。そして、挿入テーブル生成部５９は、コンテンツ変更部５４から挿入位置番号を受信すると、挿入テーブルを生成し、挿入テーブル格納部５３６に格納する。
【００９０】
また、本実施の形態における検証者端末７の構成は、基本的には図１５に示したものと同じであるが、本実施の形態では、メモリ部７３には、図２５に示すような各種格納部が含まれる。具体的には、メモリ部７３には、公開鍵格納部７３１と、コンテンツ格納部７３２と、ハッシュ値格納部７３３と、電子署名格納部７３４と、挿入テーブル格納部７３６とが含まれる。なお、公開鍵格納部７３１と、コンテンツ格納部７３２と、ハッシュ値格納部７３３と、電子署名格納部７３４とは、第１の実施の形態と同じものである。
【００９１】
本実施の形態では、入力部７１が、リンクテーブルリストの代わりに、後で説明する挿入テーブルリストを受信し、挿入テーブル格納部７３６に格納する。そして、ハッシュ値検証部７５が、挿入テーブル格納部７３６に格納される挿入テーブルリストを用いて、挿入ブロックに対するハッシュ値の検証処理を実施する。
【００９２】
次に、第２の実施の形態における変更者端末５及び検証者端末７の処理について説明する。なお、署名者端末３の処理は、第１の実施の形態と同じであるため、ここでは説明は省略する。
【００９３】
まず、図２６乃至図２８を用いて、第２の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ、ハッシュ値リストＨ₀及び署名リストΣを受信する（図２６：ステップＳ１０１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀をハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力する。
【００９４】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ１０３）。例えば、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、これらのハッシュ値と署名者の公開鍵とを用いて、電子署名σ₀を検証する。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【００９５】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ１０５）。なお、本ステップは、変更者の動作であるため、図２６では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【００９６】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及び挿入テーブル生成部５９と連携して、コンテンツ変更処理２を実施する（ステップＳ１０７）。コンテンツ変更処理２については図２７を用いて説明する。
【００９７】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図２７：ステップＳ１２１）。操作種別がブロックの変更である場合（ステップＳ１２１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ１２３）。具体的には、コンテンツ更新要求に含まれるブロック番号のブロックを変更ブロックの内容に変更する。その後、ステップＳ１３９の処理に移行する。
【００９８】
一方、操作種別がブロックの変更ではない場合（ステップＳ１２１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ１２５）。操作種別がブロックの追加である場合（ステップＳ１２５：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ１２７）。その後、ステップＳ１３９の処理に移行する。
【００９９】
一方、操作種別がブロックの追加ではない場合（ステップＳ１２５：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ１２９）。操作種別がブロックの挿入である場合（ステップＳ１２９：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ１３１）。そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ１３３）。そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ１３５）。なお、ステップＳ１３１乃至Ｓ１３５の処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。そして、コンテンツ変更部５４は、ブロックの挿入位置番号を挿入テーブル生成部５９に通知する。
【０１００】
そして、挿入テーブル生成部５９は、コンテンツ変更部５４から挿入位置番号を受信すると、挿入テーブル格納部５３６における挿入テーブルＩ_kに、挿入位置番号を設定する（ステップＳ１３７）。なお、挿入テーブル格納部５３６に挿入テーブルＩ_kが格納されていなければ、初回の処理であると判断し、挿入位置番号を含む挿入テーブルＩ_kを生成し、挿入テーブル格納部５３６に格納する。また、２回目以降の処理であれば、今回受信した挿入位置番号を挿入テーブルＩ_kに追加する。例えば、図２８に、挿入テーブルＩ_kの設定例を示す。なお、図２８は、５個のブロックを含むコンテンツに、３個のブロックが順に挿入される場合の設定例を示す。まず、コンテンツの３番目の位置に第１の挿入ブロック（図２８では、番号６のブロック）が挿入され、挿入テーブルＩ_k＝｛３｝が生成される。次に、挿入済みコンテンツＡの５番目の位置に第２の挿入ブロック（図２８では、番号７のブロック）が挿入され、挿入テーブルＩ_kに「５」が追加される。すなわち、挿入テーブルＩ_k＝｛３，５｝となる。そして、挿入済みコンテンツＢの２番目の位置に第３の挿入ブロックが挿入され、挿入テーブルＩ_kに「２」が追加される。すなわち、挿入テーブルＩ_k＝｛３，５，２｝となる。なお、詳細については後で説明するが、挿入ブロックの検証は、挿入順の逆順で行う。その後、ステップＳ１３９の処理に移行する。
【０１０１】
一方、ステップＳ１２９において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ１２９：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【０１０２】
そして、ハッシュ値計算部５５は、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ１３９）。なお、計算対象となるブロックの位置は、コンテンツ変更部５４から通知される。そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ１４１）。なお、ステップＳ１３９及びＳ１４１の処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。その後、本処理を終了し、元の処理に戻る。
【０１０３】
図２６の説明に戻って、コンテンツ変更処理２（ステップＳ１０７）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ１０９）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ１０９：Ｎｏルート）、ステップＳ１０５の処理に戻り、上で述べた処理を繰り返す。
【０１０４】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ１０９：Ｙｅｓルート）、ステップＳ１１１の処理に移行する。この際、入力部５１は、署名対象となる公開ハッシュ値Ｖ_k及び挿入テーブルＩ_kの指定を含む署名要求を署名部５６に出力する。
【０１０５】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出し、挿入テーブル格納部５３６から挿入テーブルＩ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出した公開ハッシュ値Ｖ_kと挿入テーブルＩ_kとに対する電子署名σ_kを生成する（ステップＳ１１１）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図２２では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【０１０６】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ₀及び公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出し、挿入テーブル格納部５３６から挿入テーブルＩ_kを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加し、挿入テーブルＩ_kを挿入テーブルリストＩに追加する。一人目の変更者の場合、公開ハッシュ値リストＶは、Ｖ＝｛Ｖ_k｝となり、挿入テーブルリストＩは、Ｉ＝｛Ｉ_k｝となる。そして、出力部５２は、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルリストＩとを他の変更者端末５又は検証者端末７に出力する（ステップＳ１１３）。そして、処理を終了する。
【０１０７】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ１０１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルＩとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納し、挿入テーブルリストＩを挿入テーブル格納部５３６に格納するようにすればよい。
【０１０８】
また、ステップＳ１１３では、出力部５２は、受信した挿入テーブルリストＩに、挿入テーブルＩ_kを追加するようにすればよい。すなわち、Ｉ＝｛・・・，Ｉ_k｝となる。
【０１０９】
以上のような処理を実施することにより、挿入ブロックを特定するための挿入テーブルを生成することができる。なお、挿入テーブルは、リンクテーブルより小さなデータであるため、第１の実施の形態の場合よりも、データ量を削減することができる。
【０１１０】
次に、図２９及び図３０を用いて、第２の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルリストＩとを受信する（図２９：ステップＳ１５１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納し、挿入テーブルリストＩを挿入テーブル格納部７３６に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【０１１１】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値格納部７３３に格納する（ステップＳ１５３）。例えば図２２では、ハッシュ値ｈ₁、ｈ₂、ｈ₆、ｈ₃、ｈ₄及びｈ₅が計算される。また、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【０１１２】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ１５５）。そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４と挿入テーブル格納部７３６とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から電子署名σ_kを読み出し、挿入テーブル格納部７３６から挿入テーブルＩ_kを読み出す。そして、署名検証部７６は、公開鍵と公開ハッシュ値Ｖ_kと挿入テーブルＩ_kとを用いて、電子署名σ_kの検証処理を実施する（ステップＳ１５７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０１１３】
そして、ステップＳ１５７における検証に失敗した場合（ステップＳ１５９：Ｎｏルート）、端子Ｄを介してステップＳ１８１（図３０）の処理に移行する。
【０１１４】
一方、ステップＳ１５７における検証に成功した場合（ステップＳ１５９：Ｙｅｓルート）、署名検証部７６は、公開ハッシュ値を検証するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて、公開ハッシュ値Ｖ_k及び挿入テーブルＩ_kなどを通知する。なお、ステップＳ１５７における検証に成功したということは、公開ハッシュ値Ｖ_k及び挿入テーブルＩ_kについて、変更者ｋが作成者であり、さらに偽造・改竄されていないことが証明されたことを意味する。
【０１１５】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に、公開ハッシュ値Ｖ_k及び挿入テーブルＩ_kを受信する。そして、ハッシュ値検証部７５は、公開ハッシュ値Ｖ_kにおいて、最後に挿入されたブロックの公開ハッシュ値ｖから順に未処理の公開ハッシュ値ｖを特定する（ステップＳ１６１）。なお、公開ハッシュ値Ｖ_kには、変更者ｋによって挿入されたブロック数分の公開ハッシュ値ｖが含まれる。公開ハッシュ値ｖは挿入順に並んでいるので、本ステップでは、後ろから順に公開ハッシュ値ｖを特定する。
【０１１６】
そして、ハッシュ値検証部７５は、挿入テーブルＩ_kを用いて、特定した公開ハッシュ値に対応する挿入ブロックを特定する（ステップＳ１６２）。なお、ステップＳ１６１では、挿入順の逆順で公開ハッシュ値ｖが特定されるので、本ステップにおいても、挿入順の逆順で挿入ブロックを特定する。例えば図２８では、挿入テーブルＩ_k＝｛３，５，２｝となっているので、挿入済みコンテンツＣにおける２番目のブロックが挿入ブロックとして特定される。なお、詳細については後で説明するが、この挿入ブロックは取り除かれる。次に、挿入済みコンテンツＢにおける５番目のブロックが挿入ブロックとして特定される。同様に、この挿入ブロックは取り除かれる。そして、挿入済みコンテンツＡにおける３番目のブロックが挿入ブロックとして特定される。
【０１１７】
そして、ハッシュ値検証部７５は、特定した公開ハッシュ値を用いて、特定した挿入ブロックに対するハッシュ値の検証処理を実施する（ステップＳ１６３）。ここでは、挿入ブロックに対するハッシュ値を検証することによって、その挿入ブロックの正当性を確認する。なお、本ステップの処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。
【０１１８】
そして、ステップＳ１６３における検証に失敗した場合（ステップＳ１６５：Ｎｏルート）、すなわちハッシュ値が一致しなかった場合、端子Ｄを介してステップＳ１８１（図３０）の処理に移行する。
【０１１９】
一方、ステップＳ１６３における検証に成功した場合（ステップＳ１６５：Ｙｅｓルート）、ステップＳ１６６の処理に移行する。なお、ステップＳ１６３における検証に成功したということは、挿入ブロックの正当性が確認できたということを意味する。
【０１２０】
そして、ハッシュ値検証部７５は、挿入済みコンテンツから、特定した挿入ブロックを取り除く（ステップＳ１６６）。これにより、特定した挿入ブロックが挿入される前の状態に戻ることになる。なお、変更者端末５から受信した挿入済みコンテンツを複製して検証用のデータを生成し、検証用のデータを用いて処理する。
【０１２１】
そして、ハッシュ値検証部７５は、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了したか判断する（ステップＳ１６７）。特定された変更者ｋによって挿入された挿入ブロックに係るハッシュ値ｖの全てについて処理が完了していなければ（ステップＳ１６７：Ｎｏルート）、ステップＳ１６１の処理に戻り、上で述べた処理を繰り返す。
【０１２２】
一方、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了した場合（ステップＳ１６７：Ｙｅｓルート）、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。そして、処理は、端子Ｅを介してステップＳ１６９（図３０）に移行する。
【０１２３】
図３０の説明に移行して、端子Ｅの後、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（図３０：ステップＳ１６９）。全ての変更者について処理が完了していなければ（ステップＳ１６９：Ｎｏルート）、端子Ｆを介してステップＳ１５５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。
【０１２４】
一方、全ての変更者について処理が完了した場合（ステップＳ１６９：Ｙｅｓルート）、署名検証部７６は、挿入ブロック以外の各ブロックを検証するようハッシュ値検証部７５に指示する。
【０１２５】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示を受信すると、ハッシュ値格納部７３３に格納されているハッシュ値リストＨ₀を用いて、挿入ブロック以外の各ブロックに対するハッシュ値の検証処理を実施する（ステップＳ１７１）。ここでは、挿入ブロック以外の各ブロックに対するハッシュ値の検証を行うことによって、挿入ブロック以外の各ブロックの正当性を確認する。なお、ステップＳ１６６において挿入ブロックは取り除かれるので、全ての変更者について処理が完了したということは、全ての挿入ブロックが取り除かれ、元のコンテンツの状態に戻っているはずである。従って、残っているブロックに対応するハッシュ値と、ハッシュ値リストＨ₀に含まれるハッシュ値とを比較し、ハッシュ値が一致すれば、検証成功と判断する。
【０１２６】
そして、ステップＳ１７１における検証に成功した場合（ステップＳ１７３：Ｙｅｓルート）、ハッシュ値検証部７５は、検証が完了した旨を署名検証部７６に通知する。なお、ステップＳ１７１における検証に成功したということは、挿入ブロック以外の各ブロックの正当性が確認できたということを意味する。そして、処理は、ステップＳ１７５に移行する。
【０１２７】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、公開鍵格納部７３１から署名者の公開鍵を読み出し、ハッシュ値格納部７３３からハッシュ値リストＨ₀を読み出し、電子署名格納部７３４から署名リストΣを読み出す。そして、署名検証部７６は、署名者の公開鍵とハッシュ値リストＨ₀とを用いて、署名リストΣに含まれる署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ１７５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０１２８】
そして、ステップＳ１７５における検証に成功した場合（ステップＳ１７７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ１７９）。そして、処理を終了する。
【０１２９】
一方、ステップＳ１７１における検証に失敗した場合（ステップＳ１７３：Ｎｏルート）、ステップＳ１７５における検証に失敗した場合（ステップＳ１７７：Ｎｏルート）、又は、端子Ｄの後、出力部７２は、検証失敗を表示装置等に出力する（ステップＳ１８１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【０１３０】
以上のようにＳＣＣＳ型ＰＩＡＴを変形することにより、第１の実施の形態よりも少ないデータ量で、ブロック挿入時の部分完全性保証を実現することができるようになる。
【０１３１】
［実施の形態３］
次に、第３の実施の形態について説明する。第３の実施の形態では、図３１に示すような流れで、ブロック挿入時の部分完全性保証を実現する。なお、第３の実施の形態は、第１の実施の形態を変形したものであり、おおまかな流れは第１の実施の形態と同じである。第３の実施の形態では、上で述べたようなリンクテーブル及び挿入テーブルは使用せず、変更、追加又は挿入を表すタグを公開ハッシュ値に追加する。
【０１３２】
図３１に示すように、第３の実施の形態では、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、変更者の識別子と、挿入位置番号と、挿入を表すタグ「insert」（以下、insと略す場合もある）と、そのハッシュ値とを含む公開ハッシュ値を生成する。そして、公開ハッシュ値に対する電子署名σ₁を生成する。
【０１３３】
そして、検証フェーズでは、公開ハッシュ値を用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。そして、検証に成功した場合、挿入ブロックに対するハッシュ値ｈ₆を取り除く。その後、挿入ブロックに対するハッシュ値を取り除いたハッシュ値と、署名フェーズで生成されたハッシュ値とを用いて、挿入ブロック以外のブロックを検証すると共に、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。また、挿入を表すタグを公開ハッシュ値に含めるようにすることで、リンクテーブルを生成する必要がなくなり、第１の実施の形態の場合よりも、データ量を削減することができる。以下、第３の実施の形態について詳細に説明する。
【０１３４】
第３の実施の形態に係るシステム構成は、図１０に示したシステム構成図と同じである。また、本実施の形態における署名者端末３の構成は、図１１及び図１２に示したブロック図と同じである。
【０１３５】
図３２に、本実施の形態における変更者端末５の機能ブロック図を示す。本実施の形態における変更者端末５は、入力部５１と、出力部５２と、メモリ部５３と、コンテンツ変更部５４と、ハッシュ値計算部５５と、署名部５６と、検証部５７と、タグ設定部６０とを有する。なお、入力部５１と、出力部５２と、メモリ部５３と、コンテンツ変更部５４と、ハッシュ値計算部５５と、署名部５６と、検証部５７とは、基本的には第１の実施の形態と同じものであるが、本実施の形態では、メモリ部５３には、図３３に示すような各種格納部が含まれる。具体的には、メモリ部５３には、管理データ格納部５３１と、コンテンツ格納部５３２と、ハッシュ値格納部５３３と、電子署名格納部５３４とが含まれる。なお、管理データ格納部５３１と、コンテンツ格納部５３２と、ハッシュ値格納部５３３と、電子署名格納部５３４とは、基本的には第１の実施の形態と同じものである。
【０１３６】
本実施の形態では、タグ設定部６０が、操作種別に応じたタグを選択し、ハッシュ値計算部５５に出力する。そして、ハッシュ値計算部５５は、タグ設定部６０からのタグを含む公開ハッシュ値を生成し、ハッシュ値格納部５３３に格納する。
【０１３７】
また、本実施の形態における検証者端末７の構成は、基本的には図１５に示したものと同じであるが、本実施の形態では、メモリ部７３には、図３４に示すような各種格納部が含まれる。具体的には、メモリ部７３には、公開鍵格納部７３１と、コンテンツ格納部７３２と、ハッシュ値格納部７３３と、電子署名格納部７３４とが含まれる。なお、公開鍵格納部７３１と、コンテンツ格納部７３２と、ハッシュ値格納部７３３と、電子署名格納部７３４とは、基本的には第１の実施の形態と同じものである。
【０１３８】
次に、第３の実施の形態における変更者端末５及び検証者端末７の処理について説明する。なお、署名者端末３の処理は、第１の実施の形態と同じであるため、ここでは説明は省略する。
【０１３９】
まず、図３５及び図３６を用いて、第３の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ、ハッシュ値リストＨ₀及び署名リストΣを受信する（図３５：ステップＳ１９１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀をハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力する。
【０１４０】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ１９３）。例えば、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、これらのハッシュ値と署名者の公開鍵とを用いて、電子署名σ₀を検証する。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【０１４１】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ１９５）。なお、本ステップは、変更者の動作であるため、図３５では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【０１４２】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及びタグ設定部６０と連携して、コンテンツ変更処理３を実施する（ステップＳ１９７）。コンテンツ変更処理３については図３６を用いて説明する。
【０１４３】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図３６：ステップＳ２１１）。操作種別がブロックの変更である場合（ステップＳ２１１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ２１３）。具体的には、コンテンツ更新要求に含まれるブロック番号のブロックを変更ブロックの内容に変更する。
【０１４４】
その後、タグ設定部６０が、ブロックの変更を表すタグ「change」を選択し（ステップＳ２１５）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ２３３の処理に移行する。
【０１４５】
一方、操作種別がブロックの変更ではない場合（ステップＳ２１１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ２１７）。操作種別がブロックの追加である場合（ステップＳ２１７：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ２１９）。
【０１４６】
その後、タグ設定部６０が、ブロックの追加を表すタグ「append」を選択し（ステップＳ２２１）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ２３３の処理に移行する。
【０１４７】
一方、操作種別がブロックの追加ではない場合（ステップＳ２１７：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ２２３）。操作種別がブロックの挿入である場合（ステップＳ２２３：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ２２５）。そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ２２７）。そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ２２９）。なお、ステップＳ２２５乃至Ｓ２２９の処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。
【０１４８】
その後、タグ設定部６０が、ブロックの挿入を表すタグ「insert」を選択し（ステップＳ２３１）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ２３３の処理に移行する。
【０１４９】
一方、ステップＳ２２３において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ２２３：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【０１５０】
そして、ハッシュ値計算部５５は、タグ設定部６０からタグの情報を受信すると、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ２３３）。そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、変更、追加又は挿入を表すタグと、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ２３５）。なお、本実施の形態では、変更者の識別子をｋ、ブロック番号をｉ、ハッシュ値をｈ_n+1、挿入前のブロック数をｎとして、ｖ＝（ｋ，ｉ，ＴＡＧ，ｈ_n+1）で表す。ＴＡＧは、change、append及びinsertのいずれかを示す。その後、本処理を終了し、元の処理に戻る。
【０１５１】
図３５の説明に戻って、コンテンツ変更処理３（ステップＳ１９７）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ１９９）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ１９９：Ｎｏルート）、ステップＳ１９５の処理に戻り、上で述べた処理を繰り返す。
【０１５２】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ１９９：Ｙｅｓルート）、ステップＳ２０１の処理に移行する。この際、入力部５１は、署名対象となる公開ハッシュ値Ｖ_kの指定を含む署名要求を署名部５６に出力する。
【０１５３】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出した公開ハッシュ値Ｖ_kに対する電子署名σ_kを生成する（ステップＳ２０１）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図３１では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【０１５４】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ₀及び公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加する。一人目の変更者の場合、公開ハッシュ値リストＶは、Ｖ＝｛Ｖ_k｝となる。そして、出力部５２は、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶとを他の変更者端末５又は検証者端末７に出力する（ステップＳ２０３）。そして、処理を終了する。
【０１５５】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ１９１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納するようにすればよい。
【０１５６】
以上のような処理を実施することにより、ブロックの変更、追加又は挿入を表すタグを含む公開ハッシュ値を生成することができる。
【０１５７】
次に、図３７及び図３８を用いて、第３の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、ハッシュ値リストＨ₀と、署名リストΣと、公開ハッシュ値リストＶとを受信する（図３７：ステップＳ２４１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、ハッシュ値リストＨ₀及び公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【０１５８】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値格納部７３３に格納する（ステップＳ２４３）。例えば図３１では、ハッシュ値ｈ₁、ｈ₂、ｈ₆、ｈ₃、ｈ₄及びｈ₅が計算される。また、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【０１５９】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ２４５）。そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から電子署名σ_kを読み出す。そして、署名検証部７６は、公開鍵と公開ハッシュ値Ｖ_kとを用いて、電子署名σ_kの検証処理を実施する（ステップＳ２４７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０１６０】
そして、ステップＳ２４７における検証に失敗した場合（ステップＳ２４９：Ｎｏルート）、端子Ｇを介してステップＳ２７１（図３８）の処理に移行する。
【０１６１】
一方、ステップＳ２４７における検証に成功した場合（ステップＳ２４９：Ｙｅｓルート）、署名検証部７６は、公開ハッシュ値を検証するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて、公開ハッシュ値Ｖ_kを通知する。なお、ステップＳ２４７における検証に成功したということは、公開ハッシュ値Ｖ_kについて、変更者ｋが作成者であり、さらに偽造・改竄されていないことが証明されたことを意味する。
【０１６２】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に、公開ハッシュ値Ｖ_kを受信する。そして、ハッシュ値検証部７５は、公開ハッシュ値Ｖ_kにおいて、最後に挿入されたブロックの公開ハッシュ値ｖから順に未処理の公開ハッシュ値ｖを特定する（ステップＳ２５１）。なお、公開ハッシュ値Ｖ_kには、変更者ｋによって挿入されたブロック数分の公開ハッシュ値ｖが含まれる。公開ハッシュ値ｖは挿入順に並んでいるので、本ステップでは、挿入を表すタグ「insert」を含む公開ハッシュ値ｖを後ろから順に特定する。
【０１６３】
そして、ハッシュ値検証部７５は、特定した公開ハッシュ値を用いて、挿入ブロックに対するハッシュ値の検証処理を実施する（ステップＳ２５３）。ここでは、挿入ブロックに対するハッシュ値を検証することによって、その挿入ブロックの正当性を確認する。なお、本ステップの処理は、第１の実施の形態と同じ処理である。
【０１６４】
そして、ステップＳ２５３における検証に失敗した場合（ステップＳ２５５：Ｎｏルート）、すなわちハッシュ値が一致しなかった場合、端子Ｇを介してステップＳ２７１（図３８）の処理に移行する。
【０１６５】
一方、ステップＳ２５３における検証に成功した場合（ステップＳ２５５：Ｙｅｓルート）、ステップＳ２５６の処理に移行する。なお、ステップＳ２５３における検証に成功したということは、挿入ブロックの正当性が確認できたということを意味する。
【０１６６】
そして、ハッシュ値検証部７５は、挿入済みコンテンツから挿入ブロックを取り除く（ステップＳ２５６）。なお、本ステップは、第２の実施の形態の処理と同じである。
【０１６７】
そして、ハッシュ値検証部７５は、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了したか判断する（ステップＳ２５７）。特定された変更者ｋによって挿入された挿入ブロックに係るハッシュ値ｖの全てについて処理が完了していなければ（ステップＳ２５７：Ｎｏルート）、ステップＳ２５１の処理に戻り、上で述べた処理を繰り返す。
【０１６８】
一方、特定された変更者ｋによって挿入された挿入ブロックに係る公開ハッシュ値ｖの全てについて処理が完了した場合（ステップＳ２５７：Ｙｅｓルート）、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。そして、処理は、端子Ｈを介してステップＳ２５９（図３８）に移行する。
【０１６９】
図３８の説明に移行して、端子Ｈの後、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（図３８：ステップＳ２５９）。全ての変更者について処理が完了していなければ（ステップＳ２５９：Ｎｏルート）、端子Ｉを介してステップＳ２４５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。
【０１７０】
一方、全ての変更者について処理が完了した場合（ステップＳ２５９：Ｙｅｓルート）、署名検証部７６は、挿入ブロック以外の各ブロックを検証するようハッシュ値検証部７５に指示する。
【０１７１】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示を受信すると、ハッシュ値格納部７３３に格納されているハッシュ値リストＨ₀を用いて、挿入ブロック以外の各ブロックに対するハッシュ値の検証処理を実施する（ステップＳ２６１）。ここでは、挿入ブロック以外の各ブロックに対するハッシュ値の検証を行うことによって、挿入ブロック以外の各ブロックの正当性を確認する。なお、ステップＳ２５６において挿入ブロックは取り除かれるので、全ての変更者について処理が完了したということは、全ての挿入ブロックが取り除かれ、元のコンテンツの状態に戻っているはずである。従って、残っているブロックに対応するハッシュ値と、ハッシュ値リストＨ₀に含まれるハッシュ値とを比較し、ハッシュ値が一致すれば、検証成功と判断する。
【０１７２】
そして、ステップＳ２６１における検証に成功した場合（ステップＳ２６３：Ｙｅｓルート）、ハッシュ値検証部７５は、検証が完了した旨を署名検証部７６に通知する。なお、ステップＳ２６１における検証に成功したということは、挿入ブロック以外の各ブロックの正当性が確認できたということを意味する。そして、処理は、ステップＳ２６５に移行する。
【０１７３】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、公開鍵格納部７３１から署名者の公開鍵を読み出し、ハッシュ値格納部７３３からハッシュ値リストＨ₀を読み出し、電子署名格納部７３４から署名リストΣを読み出す。そして、署名検証部７６は、署名者の公開鍵とハッシュ値リストＨ₀とを用いて、署名リストΣに含まれる署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ２６５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０１７４】
そして、ステップＳ２６５における検証に成功した場合（ステップＳ２６７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ２６９）。そして、処理を終了する。
【０１７５】
一方、ステップＳ２６１における検証に失敗した場合（ステップＳ２６３：Ｎｏルート）、ステップＳ２６５における検証に失敗した場合（ステップＳ２６７：Ｎｏルート）、又は、端子Ｇの後、出力部７２は、検証失敗を表示装置等に出力する（ステップＳ２７１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【０１７６】
以上のようにＳＣＣＳ型ＰＩＡＴを変形することにより、第１の実施の形態よりも少ないデータ量で、ブロック挿入時の部分完全性保証を実現することができるようになる。
【０１７７】
［実施の形態４］
次に、第４の実施の形態について説明する。第１乃至第３の実施の形態は、ＳＣＣＳ型ＰＩＡＴに関するものであったが、ＲＣＳ型ＰＩＡＴについても同様に変形可能である。第４の実施の形態は、ＲＣＳ型ＰＩＡＴを、第１の実施の形態で述べたリンクテーブルを用いる方式に変更したものである。第４の実施の形態では、図３９に示すような流れで、ブロック挿入時の部分完全性保証を実現する。
【０１７８】
図３９に示すように、第１の実施の形態では、変更フェーズにおいて、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リスト１を生成する。そして、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、そのハッシュ値をハッシュ値リストに挿入することで、ハッシュ値リスト２を生成する。また、変更者の識別子と、挿入位置番号と、そのハッシュ値とを含む公開ハッシュ値を生成し、さらにリンクテーブルを生成する。そして、ハッシュ値リスト２と公開ハッシュ値とリンクテーブルとに対する電子署名σ₁を生成する。
【０１７９】
そして、検証フェーズでは、まず、挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する。そして、計算したハッシュ値と公開ハッシュ値とリンクテーブルとを用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。また、計算したハッシュ値のうち、挿入ブロック以外のブロックに対するハッシュ値（図３９では、ｈ₁〜ｈ₅）を用いて、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。なお、リンクテーブルから挿入ブロックを特定できるので、挿入ブロック以外のブロックについては公開ハッシュ値のデータを生成する必要がなくなり、従来のＲＣＳ型ＰＩＡＴに比べて、公開ハッシュ値のデータ量を削減できる。以下、第４の実施の形態について詳細に説明する。
【０１８０】
第４の実施の形態に係るシステム構成は、図１０に示したシステム構成図と同じである。また、本実施の形態における署名者端末３、変更者端末５及び検証者端末７の構成は、基本的には第１の実施の形態のものと同じである。
【０１８１】
まず、図４０を用いて、第４の実施の形態における署名者端末３の処理について説明する。まず、署名者が、署名者端末３を操作して、文書、動画、静止画、音楽などのコンテンツを作成する（図４０：ステップＳ２８１）。なお、本ステップは、署名者の動作であるため、図４０では点線ブロックで示している。そして、入力部３１は、署名者からコンテンツ作成の操作を受け付け、署名者によって作成されたコンテンツをコンテンツ格納部３３２に格納する。その後、入力部３１は、コンテンツの分割要求を分割部３４に出力する。なお、分割要求には、作成されたコンテンツのファイル名などが含まれる。
【０１８２】
そして、分割部３４は、入力部３１から分割要求を受信すると、コンテンツ格納部３３２に格納されているコンテンツをｎ個のブロックに分割する（ステップＳ２８３）。例えば図３９では、コンテンツが、ブロックｍ₁からブロックｍ₅までの５個のブロックに分割される。そして、分割部３４は、ハッシュ値計算要求をハッシュ値計算部３５に出力する。なお、ハッシュ値計算要求には、コンテンツのファイル名などが含まれる。
【０１８３】
そして、ハッシュ値計算部３５は、分割部３４からハッシュ値計算要求を受信すると、コンテンツ格納部３３２からハッシュ値計算要求に係るコンテンツを読み出す。そして、読み出したコンテンツに含まれるｎ個のブロックの各々に対するハッシュ値を計算し、計算したｎ個のハッシュ値を含むハッシュ値リストＨ₀を生成する（ステップＳ２８５）。なお、ハッシュ値リストＨ₀は、ハッシュ値格納部３３３に格納される。例えば図３９では、ハッシュ値ｈ₁からハッシュ値ｈ₅までの５個のハッシュ値が計算され、この５個のハッシュ値を含むハッシュ値リストＨ₀が生成される。その後、ハッシュ値計算部３５は、署名対象となるハッシュ値リストＨ₀の指定を含む署名要求を署名部３６に出力する。
【０１８４】
そして、署名部３６は、ハッシュ値計算部３５から署名要求を受信すると、管理データ格納部３３１から署名者の秘密鍵を読み出し、さらにハッシュ値格納部３３３から署名要求に係るハッシュ値リストＨ₀を読み出す。そして、署名部３６は、秘密鍵を用いて、ハッシュ値リストＨ₀に対する電子署名σ₀を生成する（ステップＳ２８７）。この際、署名部３６は、署名リストΣ＝｛σ₀｝として電子署名格納部３３４に格納する。
【０１８５】
その後、出力部３２が、コンテンツ格納部３３２に格納されているコンテンツと、電子署名格納部３３４に格納されている署名リストΣとを読み出し、変更者端末５に出力する（ステップＳ２８９）。そして、処理を終了する。
【０１８６】
次に、図４１及び図４２を用いて、第１の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ及び署名リストΣを受信する（図４１：ステップＳ２９１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力し、ハッシュ値計算要求をハッシュ値計算部５５に出力する。
【０１８７】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ２９３）。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【０１８８】
また、ハッシュ値計算部５５は、入力部５１からハッシュ値計算要求を受信すると、コンテンツ格納部５３２からコンテンツを読み出す。そして、ハッシュ値計算部５５は、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、計算したハッシュ値を含むハッシュ値リストＨ_kを生成する（ステップＳ２９５）。なお、ハッシュ値リストＨ_kは、ハッシュ値格納部５３３に格納される。
【０１８９】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ２９７）。なお、本ステップは、変更者の動作であるため、図４１では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【０１９０】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及びリンクテーブル生成部５８と連携して、コンテンツ変更処理４を実施する（ステップＳ２９９）。コンテンツ変更処理４については図４２を用いて説明する。
【０１９１】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図４２：ステップＳ３１１）。操作種別がブロックの変更である場合（ステップＳ３１１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３１３）。具体的には、コンテンツ更新要求に含まれるブロック番号のブロックを変更ブロックの内容に変更する。その後、ステップＳ３２９の処理に移行する。
【０１９２】
一方、操作種別がブロックの変更ではない場合（ステップＳ３１１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ３１５）。操作種別がブロックの追加である場合（ステップＳ３１５：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３１７）。その後、ステップＳ３２９の処理に移行する。
【０１９３】
一方、操作種別がブロックの追加ではない場合（ステップＳ３１５：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ３１９）。操作種別がブロックの挿入である場合（ステップＳ３１９：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ３２１）。そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ３２３）。そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ３２５）。なお、ステップＳ３２１乃至Ｓ３２５の処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。そして、コンテンツ変更部５４は、ブロックの挿入位置番号をリンクテーブル生成部５８に通知する。
【０１９４】
そして、リンクテーブル生成部５８は、コンテンツ変更部５４から挿入位置番号を受信すると、リンクテーブル格納部５３５におけるリンクテーブルＬ_kに、挿入ブロックの番号を設定する（ステップＳ３２７）。なお、本ステップの処理は、第１の実施の形態と同じ処理であるため、詳細な説明は省略する。そして、ステップＳ３２９の処理に移行する。
【０１９５】
一方、ステップＳ３１９において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ３１９：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【０１９６】
そして、ハッシュ値計算部５５は、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ３２９）。なお、計算対象となるブロックの位置は、コンテンツ変更部５４から通知される。例えば図３９では、先頭から３番目の位置に挿入されたブロックｍ₆に対するハッシュ値ｈ₆が計算される。
【０１９７】
そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ３３１）。
【０１９８】
また、ハッシュ値計算部５５は、ステップＳ３２９において計算したハッシュ値を用いて、ハッシュ値格納部５３３に格納されているハッシュ値リストＨ_kを更新する（ステップＳ３３３）。例えば、操作種別がブロックの挿入であった場合には、ハッシュ値リストＨ_kにハッシュ値を挿入する。例えば図３９では、３番目の位置にハッシュ値ｈ₆が挿入され、ハッシュ値リストＨ_k＝｛ｈ₁，ｈ₂，ｈ₆，ｈ₃，ｈ₄，ｈ₅｝となる。その後、本処理を終了し、元の処理に戻る。
【０１９９】
図４１の説明に戻って、コンテンツ変更処理４（ステップＳ２９９）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ３０１）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ３０１：Ｎｏルート）、ステップＳ２９７の処理に戻り、上で述べた処理を繰り返す。
【０２００】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ３０１：Ｙｅｓルート）、ステップＳ３０３の処理に移行する。この際、入力部５１は、署名対象となるハッシュ値リストＨ_k、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kの指定を含む署名要求を署名部５６に出力する。
【０２０１】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ_k及び公開ハッシュ値Ｖ_kを読み出し、リンクテーブル格納部５３５からリンクテーブルＬ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出したハッシュ値リストＨ_kと公開ハッシュ値Ｖ_kとリンクテーブルＬ_kとに対する電子署名σ_kを生成する（ステップＳ３０３）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図３９では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【０２０２】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出し、リンクテーブル格納部５３５からリンクテーブルＬ_kを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加し、リンクテーブルＬ_kをリンクテーブルリストＬに追加する。そして、出力部５２は、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを他の変更者端末５又は検証者端末７に出力する（ステップＳ３０５）。そして、処理を終了する。
【０２０３】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ２９１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納し、リンクテーブルリストＬをリンクテーブル格納部５３５に格納するようにすればよい。
【０２０４】
また、ステップＳ３０５では、出力部５２は、受信した公開ハッシュ値リストＶに、公開ハッシュ値Ｖ_kを追加するようにすればよい。さらに、受信したリンクテーブルリストＬに、リンクテーブルＬ_kを追加するようにすればよい。
【０２０５】
以上のような処理を実施することにより、ＲＣＳ型ＰＩＡＴの場合においても、リンクテーブルを生成することができる。
【０２０６】
次に、図４３を用いて、第４の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、リンクテーブルリストＬとを受信する（図４３：ステップＳ３４１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納し、リンクテーブルリストＬをリンクテーブル格納部７３５に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【０２０７】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リストＨを生成する（ステップＳ３４３）。なお、ハッシュ値リストＨは、ハッシュ値格納部７３３に格納される。例えば図３９では、ハッシュ値リストＨ＝｛ｈ₁，ｈ₂，ｈ₆，ｈ₃，ｈ₄，ｈ₅｝が生成される。そして、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【０２０８】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ３４５）。そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４とリンクテーブル格納部７３５とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から変更者ｋに係る電子署名σ_kを読み出し、リンクテーブル格納部７３５からリンクテーブルＬ_kを読み出す。また、ステップＳ３４３において生成したハッシュ値リストＨをハッシュ値格納部５３３から読み出す。そして、署名検証部７６は、公開鍵とハッシュ値リストＨと公開ハッシュ値Ｖ_kとリンクテーブルＬ_kとを基に、変更者ｋに係る電子署名σ_kの検証処理を実施する（ステップＳ３４７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２０９】
そして、ステップＳ３４７における検証に成功した場合（ステップＳ３４９：Ｙｅｓルート）、署名検証部７６は、ハッシュ値リストＨを更新するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kを通知する。なお、ステップＳ３４７における検証に成功したということは、変更者ｋによって挿入された挿入ブロックの正当性が確認できたということを意味する。
【０２１０】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に、公開ハッシュ値Ｖ_k及びリンクテーブルＬ_kを受信する。そして、ハッシュ値検証部７５は、公開ハッシュ値Ｖ_kから、変更者ｋによって挿入された挿入ブロックの数を特定する。そして、ハッシュ値検証部７５は、リンクテーブルＬ_kに基づき、ハッシュ値リストＨから挿入ブロックに対するハッシュ値を取り除くことにより、ハッシュ値リストＨを挿入前の状態に復元する（ステップＳ３５１）。なお、第１の実施の形態で述べたように、リンクテーブルＬ_kに含まれる番号を番号の大きい順に辿っていくことで、挿入ブロックを特定する。例えば図３９では、３番目のハッシュ値ｈ₆が取り除かれ、ハッシュ値リストＨ＝｛ｈ₁，ｈ₂，ｈ₃，ｈ₄，ｈ₅｝となる。そして、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。
【０２１１】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（ステップＳ３５３）。全ての変更者について処理が完了していなければ（ステップＳ３５３：Ｎｏルート）、ステップＳ３４５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。なお、全ての変更者について、上で述べたような処理を実施することで、全ての挿入ブロックに対応するハッシュ値がハッシュ値リストＨから取り除かれ、元のコンテンツの状態に戻ることになる。
【０２１２】
一方、全ての変更者について処理が完了した場合（ステップＳ３５３：Ｙｅｓルート）、署名検証部７６は、公開鍵格納部７３１から署名者の公開鍵を読み出し、電子署名格納部７３４から署名者に係る電子署名σ₀を読み出す。そして、署名検証部７６は、署名者の公開鍵と、復元されたハッシュ値リストＨとを基に、署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ３５５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２１３】
そして、ステップＳ３５５における検証に成功した場合（ステップＳ３５７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ３５９）。そして、処理を終了する。
【０２１４】
そして、ステップＳ３４７における検証に失敗した場合（ステップＳ３４９：Ｎｏルート）、又は、ステップＳ３５５における検証に失敗した場合（ステップＳ３５７：Ｎｏルート）、出力部７２が、検証失敗を表示装置等に出力する（ステップＳ３６１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【０２１５】
以上のようにＲＣＳ型ＰＩＡＴを変形することにより、ブロック挿入時においても、コンテンツの部分完全性保証を実現することができるようになる。すなわち、検証に成功した場合には、挿入後のコンテンツの完全性を証明すると共に、挿入ブロック以外のブロックが元のコンテンツから引き継いだものであることが保証される。
【０２１６】
［実施の形態５］
次に、第５の実施の形態について説明する。第５の実施の形態では、図４４に示すような流れで、ブロック挿入時の部分完全性保証を実現する。なお、第５の実施の形態は、第４の実施の形態を変形したものであり、おおまかな流れは第４の実施の形態と同じである。第５の実施の形態では、リンクテーブルの代わりに、第２の実施の形態で説明した挿入テーブルを用いる。
【０２１７】
図４４に示すように、第５の実施の形態では、変更フェーズにおいて、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リスト１を生成する。そして、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、そのハッシュ値をハッシュ値リストに挿入することで、ハッシュ値リスト２を生成する。また、変更者の識別子と、挿入位置番号と、そのハッシュ値とを含む公開ハッシュ値を生成し、さらに挿入テーブルを生成する。そして、ハッシュ値リスト２と公開ハッシュ値と挿入テーブルとに対する電子署名σ₁を生成する。
【０２１８】
そして、検証フェーズでは、まず、挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する。そして、計算したハッシュ値と公開ハッシュ値と挿入テーブルとを用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。また、計算したハッシュ値のうち、挿入ブロック以外のブロックに対するハッシュ値（図４４では、ｈ₁〜ｈ₅）を用いて、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。また、挿入テーブルは、リンクテーブルより小さなデータであるため、第４の実施の形態の場合よりも、データ量を削減することができる。以下、第５の実施の形態について詳細に説明する。
【０２１９】
第５の実施の形態に係るシステム構成は、図１０に示したシステム構成図と同じである。また、本実施の形態における署名者端末３、変更者端末５及び検証者端末７の構成は、基本的には第２の実施の形態のものと同じである。
【０２２０】
第５の実施の形態における変更者端末５及び検証者端末７の処理について説明する。なお、署名者端末３の処理は、第４の実施の形態と同じであるため、ここでは説明は省略する。
【０２２１】
まず、図４５及び図４６を用いて、第５の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ及び署名リストΣを受信する（図４５：ステップＳ３７１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力し、ハッシュ値計算要求をハッシュ値計算部５５に出力する。
【０２２２】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ３７３）。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【０２２３】
また、ハッシュ値計算部５５は、入力部５１からハッシュ値計算要求を受信すると、コンテンツ格納部５３２からコンテンツを読み出す。そして、ハッシュ値計算部５５は、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、計算したハッシュ値を含むハッシュ値リストＨ_kを生成する（ステップＳ３７５）。なお、ハッシュ値リストＨ_kは、ハッシュ値格納部５３３に格納される。
【０２２４】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ３７７）。なお、本ステップは、変更者の動作であるため、図４５では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【０２２５】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及び挿入テーブル生成部５９と連携して、コンテンツ変更処理５を実施する（ステップＳ３７９）。コンテンツ変更処理５については図４６を用いて説明する。
【０２２６】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図４６：ステップＳ３９１）。操作種別がブロックの変更である場合（ステップＳ３９１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３９３）。具体的には、コンテンツ更新要求に含まれるブロック番号のブロックを変更ブロックの内容に変更する。その後、ステップＳ４０９の処理に移行する。
【０２２７】
一方、操作種別がブロックの変更ではない場合（ステップＳ３９１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ３９５）。操作種別がブロックの追加である場合（ステップＳ３９５：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ３９７）。その後、ステップＳ４０９の処理に移行する。
【０２２８】
一方、操作種別がブロックの追加ではない場合（ステップＳ３９５：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ３９９）。操作種別がブロックの挿入である場合（ステップＳ３９９：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ４０１）。そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ４０３）。そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ４０５）。そして、コンテンツ変更部５４は、ブロックの挿入位置番号を挿入テーブル生成部５９に通知する。
【０２２９】
そして、挿入テーブル生成部５９は、コンテンツ変更部５４から挿入位置番号を受信すると、挿入テーブル格納部５３６における挿入テーブルＩ_kに、挿入位置番号を設定する（ステップＳ４０７）。なお、本ステップの処理は、第２の実施の形態と同じ処理であるため、詳細な説明は省略する。そして、ステップＳ４０９の処理に移行する。
【０２３０】
一方、ステップＳ３９９において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ３９９：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【０２３１】
そして、ハッシュ値計算部５５は、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ４０９）。なお、計算対象となるブロックの位置は、コンテンツ変更部５４から通知される。そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ４１１）。また、ハッシュ値計算部５５は、ステップＳ４０９において計算したハッシュ値を用いて、ハッシュ値格納部５３３に格納されているハッシュ値リストＨ_kを更新する（ステップＳ４１３）。なお、ステップＳ４０９乃至Ｓ４１３の処理は、第４の実施の形態と同じ処理であるため、詳細な説明は省略する。その後、本処理を終了し、元の処理に戻る。
【０２３２】
図４５の説明に戻って、コンテンツ変更処理５（ステップＳ３７９）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ３８１）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ３８１：Ｎｏルート）、ステップＳ３７７の処理に戻り、上で述べた処理を繰り返す。
【０２３３】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ３８１：Ｙｅｓルート）、ステップＳ３８３の処理に移行する。この際、入力部５１は、署名対象となるハッシュ値リストＨ_k、公開ハッシュ値Ｖ_k及び挿入テーブルＩ_kの指定を含む署名要求を署名部５６に出力する。
【０２３４】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ_k及び公開ハッシュ値Ｖ_kを読み出し、挿入テーブル格納部５３６から挿入テーブルＩ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出したハッシュ値リストＨ_kと公開ハッシュ値Ｖ_kと挿入テーブルＩ_kとに対する電子署名σ_kを生成する（ステップＳ３８３）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図４４では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【０２３５】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出し、挿入テーブル格納部５３６から挿入テーブルＩ_kを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加し、挿入テーブルＩ_kを挿入テーブルリストＩに追加する。そして、出力部５２は、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルリストＩとを他の変更者端末５又は検証者端末７に出力する（ステップＳ３８５）。そして、処理を終了する。
【０２３６】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ３７１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルリストＩとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納し、挿入テーブルリストＩを挿入テーブル格納部５３６に格納するようにすればよい。
【０２３７】
また、ステップＳ３８５では、出力部５２は、受信した公開ハッシュ値リストＶに、公開ハッシュ値Ｖ_kを追加するようにすればよい。さらに、受信した挿入テーブルリストＩに、挿入テーブルＩ_kを追加するようにすればよい。
【０２３８】
以上のような処理を実施することにより、ＲＣＳ型ＰＩＡＴの場合においても、挿入テーブルを生成することができる。
【０２３９】
次に、図４７を用いて、第５の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶと、挿入テーブルリストＩとを受信する（図４７：ステップＳ４２１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納し、挿入テーブルリストＩを挿入テーブル格納部７３６に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【０２４０】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リストＨを生成する（ステップＳ４２３）。なお、ハッシュ値リストＨは、ハッシュ値格納部７３３に格納される。そして、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【０２４１】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ４２５）。そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４と挿入テーブル格納部７３６とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から変更者ｋに係る電子署名σ_kを読み出し、挿入テーブル格納部７３６から挿入テーブルＩ_kを読み出す。また、ステップＳ４２３において生成したハッシュ値リストＨをハッシュ値格納部５３３から読み出す。そして、署名検証部７６は、公開鍵とハッシュ値リストＨと公開ハッシュ値Ｖ_kと挿入テーブルＩ_kとを基に、変更者ｋに係る電子署名σ_kの検証処理を実施する（ステップＳ４２７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２４２】
そして、ステップＳ４２７における検証に成功した場合（ステップＳ４２９：Ｙｅｓルート）、署名検証部７６は、ハッシュ値リストＨを更新するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて挿入テーブルＩ_kを通知する。なお、ステップＳ４２７における検証に成功したということは、変更者ｋによって挿入された挿入ブロックの正当性が確認できたということを意味する。
【０２４３】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に挿入テーブルＩ_kを受信する。そして、ハッシュ値検証部７５は、挿入テーブルＩ_kに基づき、ハッシュ値リストＨから挿入ブロックに対するハッシュ値を取り除くことにより、ハッシュ値リストＨを挿入前の状態に復元する（ステップＳ４３１）。なお、図２８に示したように、挿入テーブルＩ_kには、挿入順に挿入位置番号が設定されるので、後ろから順に挿入位置番号を特定し、その挿入位置番号の挿入ブロックを取り除く。例えば図４４では、３番目のハッシュ値ｈ₆が取り除かれ、ハッシュ値リストＨ＝｛ｈ₁，ｈ₂，ｈ₃，ｈ₄，ｈ₅｝となる。そして、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。
【０２４４】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（ステップＳ４３３）。全ての変更者について処理が完了していなければ（ステップＳ４３３：Ｎｏルート）、ステップＳ４２５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。なお、全ての変更者について、上で述べたような処理を実施することで、全ての挿入ブロックに対応するハッシュ値がハッシュ値リストＨから取り除かれ、元のコンテンツの状態に戻ることになる。
【０２４５】
一方、全ての変更者について処理が完了した場合（ステップＳ４３３：Ｙｅｓルート）、署名検証部７６は、公開鍵格納部７３１から署名者の公開鍵を読み出し、電子署名格納部７３４から署名者に係る電子署名σ₀を読み出す。そして、署名検証部７６は、署名者の公開鍵と、復元されたハッシュ値リストＨとを基に、署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ４３５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２４６】
そして、ステップＳ４３５における検証に成功した場合（ステップＳ４３７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ４３９）。そして、処理を終了する。
【０２４７】
一方、ステップＳ４２７における検証に失敗した場合（ステップＳ４２９：Ｎｏルート）、又は、ステップＳ４３５における検証に失敗した場合（ステップＳ４３７：Ｎｏルート）、出力部７２が、検証失敗を表示装置等に出力する（ステップＳ４４１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【０２４８】
以上のようにＲＣＳ型ＰＩＡＴを変形することにより、第４の実施の形態よりも少ないデータ量で、ブロック挿入時の部分完全性保証を実現することができるようになる。
【０２４９】
［実施の形態６］
次に、第６の実施の形態について説明する。第６の実施の形態では、図４８に示すような流れで、ブロック挿入時の部分完全性保証を実現する。なお、第６の実施の形態は、第４の実施の形態を変形したものであり、おおまかな流れは第４の実施の形態と同じである。第６の実施の形態では、第３の実施の形態で説明したタグを公開ハッシュ値に追加する。
【０２５０】
図４８に示すように、第５の実施の形態では、変更フェーズにおいて、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リスト１を生成する。そして、例えばコンテンツの３番目にブロックｍ₆が挿入された場合、挿入ブロックｍ₆に対するハッシュ値を計算し、そのハッシュ値をハッシュ値リストに挿入することで、ハッシュ値リスト２を生成する。また、変更者の識別子と、挿入位置番号と、挿入を表すタグ「insert」と、そのハッシュ値とを含む公開ハッシュ値を生成する。そして、ハッシュ値リスト２と公開ハッシュ値とに対する電子署名σ₁を生成する。
【０２５１】
そして、検証フェーズでは、まず、挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する。そして、計算したハッシュ値と公開ハッシュ値とを用いて、挿入ブロックを検証すると共に、電子署名σ₁を検証する。また、計算したハッシュ値のうち、挿入ブロック以外のブロックに対するハッシュ値（図４８では、ｈ₁〜ｈ₅）を用いて、電子署名σ₀を検証する。これにより、挿入ブロックについては、変更者によって挿入されたものであることが保証され、挿入ブロック以外の各ブロックについては、元のコンテンツから引き継いだものであることが保証される。また、挿入を表すタグを公開ハッシュ値に含めるようにすることで、リンクテーブルを生成する必要がなくなり、第４の実施の形態の場合よりも、データ量を削減することができる。以下、第６の実施の形態について詳細に説明する。
【０２５２】
第６の実施の形態に係るシステム構成は、図１０に示したシステム構成図と同じである。また、本実施の形態における署名者端末３、変更者端末５及び検証者端末７の構成は、基本的には第３の実施の形態のものと同じである。
【０２５３】
第６の実施の形態における変更者端末５及び検証者端末７の処理について説明する。なお、署名者端末３の処理は、第４の実施の形態と同じであるため、ここでは説明は省略する。
【０２５４】
まず、図４９及び図５０を用いて、第６の実施の形態における変更者端末５の処理について説明する。ここでは、一人目の変更者である場合について説明する。まず、入力部５１が、署名者端末３からコンテンツ及び署名リストΣを受信する（図４９：ステップＳ４５１）。そして、入力部５１は、受信したコンテンツをコンテンツ格納部５３２に格納し、署名リストΣを電子署名格納部５３４に格納する。そして、入力部５１は、電子署名の検証要求を検証部５７に出力し、ハッシュ値計算要求をハッシュ値計算部５５に出力する。
【０２５５】
そして、検証部５７は、入力部５１から検証要求を受信すると、電子署名格納部５３４から署名リストΣを読み出し、署名リストΣに含まれる署名者の電子署名σ₀の検証処理を実施する（ステップＳ４５３）。なお、署名を検証する処理自体は、従来と変わらないので、これ以上述べない。
【０２５６】
また、ハッシュ値計算部５５は、入力部５１からハッシュ値計算要求を受信すると、コンテンツ格納部５３２からコンテンツを読み出す。そして、ハッシュ値計算部５５は、コンテンツに含まれる各ブロックに対するハッシュ値を計算し、計算したハッシュ値を含むハッシュ値リストＨ_kを生成する（ステップＳ４５５）。なお、ハッシュ値リストＨ_kは、ハッシュ値格納部５３３に格納される。
【０２５７】
その後、変更者が、変更者端末５を操作し、ブロックの変更、追加又は挿入を行うことによりコンテンツを変更する（ステップＳ４５７）。なお、本ステップは、変更者の動作であるため、図４９では点線ブロックで示している。そして、入力部５１は、変更ブロック、追加ブロック又は挿入ブロックの入力を受け付け、コンテンツ更新要求をコンテンツ変更部５４に出力する。なお、コンテンツ更新要求には、入力されたブロックのデータや、操作種別、ブロック番号などが含まれる。
【０２５８】
そして、コンテンツ変更部５４は、入力部５１からコンテンツ更新要求を受信すると、メモリ部５３、ハッシュ値計算部５５及びタグ設定部６０と連携して、コンテンツ変更処理６を実施する（ステップＳ４５９）。コンテンツ変更処理６については図５０を用いて説明する。
【０２５９】
まず、コンテンツ変更部５４は、操作種別がブロックの変更であるか判断する（図５０：ステップＳ４７１）。操作種別がブロックの変更である場合（ステップＳ４７１：Ｙｅｓルート）、コンテンツ変更部５４は、ブロックを変更することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ４７３）。
【０２６０】
その後、タグ設定部６０が、ブロックの変更を表すタグ「change」を選択し（ステップＳ４７５）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ４９３の処理に移行する。
【０２６１】
一方、操作種別がブロックの変更ではない場合（ステップＳ４７１：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの追加であるか判断する（ステップＳ４７７）。操作種別がブロックの追加である場合（ステップＳ４７７：Ｙｅｓルート）、コンテンツ変更部５４は、追加ブロックをコンテンツの最後に追加することにより、コンテンツ格納部５３２に格納されているコンテンツを更新する（ステップＳ４７９）。
【０２６２】
その後、タグ設定部６０が、ブロックの追加を表すタグ「append」を選択し（ステップＳ４８１）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ４９３の処理に移行する。
【０２６３】
一方、操作種別がブロックの追加ではない場合（ステップＳ４７７：Ｎｏルート）、コンテンツ変更部５４は、操作種別がブロックの挿入であるか判断する（ステップＳ４８３）。操作種別がブロックの挿入である場合（ステップＳ４８３：Ｙｅｓルート）、コンテンツ変更部５４は、最終ブロックと同一ブロックをコンテンツの最後に追加する（ステップＳ４８５）。そして、コンテンツ変更部５４は、挿入位置以降の各ブロックを１つずつ後ろにシフトする（ステップＳ４８７）。そして、コンテンツ変更部５４は、挿入位置にブロックを挿入する（ステップＳ４８９）。
【０２６４】
その後、タグ設定部６０が、ブロックの挿入を表すタグ「insert」を選択し（ステップＳ４９１）、選択したタグの情報をハッシュ値計算部５５に出力する。そして、ステップＳ４９３の処理に移行する。
【０２６５】
一方、ステップＳ４８３において、操作種別がブロックの挿入ではないと判断された場合（ステップＳ４８３：Ｎｏルート）、以降の処理をスキップし、本処理を終了する。そして、元の処理に戻る。
【０２６６】
そして、ハッシュ値計算部５５は、タグ設定部６０からタグの情報を受信すると、変更、追加又は挿入されたブロックのハッシュ値を計算する（ステップＳ４９３）。そして、ハッシュ値計算部５５は、管理データ格納部５３１に格納されている変更者の識別子と、ブロック番号と、変更、追加又は挿入を表すタグと、計算したハッシュ値とを含む公開ハッシュ値ｖを生成し、ハッシュ値格納部５３３に格納する（ステップＳ４９５）。また、ハッシュ値計算部５５は、ステップＳ４９３において計算したハッシュ値を用いて、ハッシュ値格納部５３３に格納されているハッシュ値リストＨ_kを更新する（ステップＳ４９７）。なお、本ステップの処理は、第４の実施の形態と同じ処理であるため、詳細な説明は省略する。その後、本処理を終了し、元の処理に戻る。
【０２６７】
図４９の説明に戻って、コンテンツ変更処理６（ステップＳ４５９）を実施した後、入力部５１は、コンテンツの変更が完了したか判断する（ステップＳ４６１）。例えば、変更者から次の操作（ブロックの変更、追加又は挿入）を受け付けた場合には、コンテンツの変更は完了していないと判断し（ステップＳ４６１：Ｎｏルート）、ステップＳ４５７の処理に戻り、上で述べた処理を繰り返す。
【０２６８】
一方、例えば変更者から変更完了が指示された場合には、コンテンツの変更が完了したと判断し（ステップＳ４６１：Ｙｅｓルート）、ステップＳ４６３の処理に移行する。この際、入力部５１は、署名対象となるハッシュ値リストＨ_k及び公開ハッシュ値Ｖ_kの指定を含む署名要求を署名部５６に出力する。
【０２６９】
そして、署名部５６は、入力部５１から署名要求を受信すると、管理データ格納部５３１から変更者ｋの秘密鍵を読み出し、ハッシュ値格納部５３３からハッシュ値リストＨ_k及び公開ハッシュ値Ｖ_kを読み出す。そして、署名部５６は、変更者ｋの秘密鍵を用いて、読み出したハッシュ値リストＨ_kと公開ハッシュ値Ｖ_kとに対する電子署名σ_kを生成する（ステップＳ４６３）。そして、生成した電子署名σ_kを、電子署名格納部５３４における署名リストΣに追加する。例えば図４８では、電子署名σ₁が生成され、署名リストΣ＝｛σ₀，σ₁｝となる。
【０２７０】
その後、出力部５２は、コンテンツ格納部５３２から挿入済みコンテンツを読み出し、ハッシュ値格納部５３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部５３４から署名リストΣを読み出す。そして、出力部５２は、公開ハッシュ値Ｖ_kを公開ハッシュ値リストＶに追加する。そして、出力部５２は、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶとを他の変更者端末５又は検証者端末７に出力する（ステップＳ４６５）。そして、処理を終了する。
【０２７１】
なお、上では、一人目の変更者である場合について説明したが、二人目以降の変更者の場合も基本的な処理は同じである。但し、二人目以降の変更者の場合、ステップＳ４５１では、入力部５１は、前の変更者が操作する変更者端末５から、挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶとを受信する。この場合、入力部５１は、挿入済みコンテンツをコンテンツ格納部５３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部５３３に格納し、署名リストΣを電子署名格納部５３４に格納するようにすればよい。
【０２７２】
また、ステップＳ４６５では、出力部５２は、受信した公開ハッシュ値リストＶに、公開ハッシュ値Ｖ_kを追加するようにすればよい。
【０２７３】
以上のような処理を実施することにより、ＲＣＳ型ＰＩＡＴの場合においても、ブロックの変更、追加又は挿入を表すタグを含む公開ハッシュ値を生成することができる。
【０２７４】
次に、図５１を用いて、第６の実施の形態における検証者端末７の処理について説明する。ここでは、挿入済みコンテンツを検証する場合の処理について説明する。まず、入力部７１が、変更者端末５から挿入済みコンテンツと、署名リストΣと、公開ハッシュ値リストＶとを受信する（図５１：ステップＳ５０１）。そして、入力部７１は、受信した挿入済みコンテンツをコンテンツ格納部７３２に格納し、公開ハッシュ値リストＶをハッシュ値格納部７３３に格納し、署名リストΣを電子署名格納部７３４に格納する。そして、入力部７１は、ハッシュ値計算要求をハッシュ値計算部７４に出力する。なお、ハッシュ値計算要求には、挿入済みコンテンツのファイル名などが含まれる。
【０２７５】
そして、ハッシュ値計算部７４は、入力部７１からハッシュ値計算要求を受信すると、コンテンツ格納部７３２からハッシュ値計算要求に係る挿入済みコンテンツを読み出す。そして、ハッシュ値計算部７４は、読み出した挿入済みコンテンツに含まれる各ブロックに対するハッシュ値を計算し、ハッシュ値リストＨを生成する（ステップＳ５０３）。なお、ハッシュ値リストＨは、ハッシュ値格納部７３３に格納される。そして、ハッシュ値計算部７４は、検証要求を署名検証部７６に出力する。
【０２７６】
そして、署名検証部７６は、ハッシュ値計算部７４から検証要求を受信すると、最終変更者から順に未処理の変更者ｋを特定する（ステップＳ５０５）。そして、署名検証部７６は、公開鍵格納部７３１とハッシュ値格納部７３３と電子署名格納部７３４とから、特定した変更者ｋに係るデータを読み出す。すなわち、公開鍵格納部７３１から変更者ｋの公開鍵を読み出し、ハッシュ値格納部７３３から公開ハッシュ値Ｖ_kを読み出し、電子署名格納部７３４から変更者ｋに係る電子署名σ_kを読み出す。また、ステップＳ５０３において生成したハッシュ値リストＨをハッシュ値格納部５３３から読み出す。そして、署名検証部７６は、公開鍵とハッシュ値リストＨと公開ハッシュ値Ｖ_kとを基に、変更者ｋに係る電子署名σ_kの検証処理を実施する（ステップＳ５０７）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２７７】
そして、ステップＳ５０７における検証に成功した場合（ステップＳ５０９：Ｙｅｓルート）、署名検証部７６は、ハッシュ値リストＨを更新するようハッシュ値検証部７５に指示する。この際、署名検証部７６は、指示と併せて公開ハッシュ値Ｖ_kを通知する。なお、ステップＳ５０７における検証に成功したということは、変更者ｋによって挿入された挿入ブロックの正当性が確認できたということを意味する。
【０２７８】
そして、ハッシュ値検証部７５は、署名検証部７６からの指示と共に公開ハッシュ値Ｖ_kを受信する。そして、ハッシュ値検証部７５は、公開ハッシュ値Ｖ_kに基づき、ハッシュ値リストＨから挿入ブロックに対するハッシュ値を取り除くことにより、ハッシュ値リストＨを挿入前の状態に復元する（ステップＳ５１１）。なお、公開ハッシュ値Ｖ_kには、変更者ｋによって挿入されたブロック数分の公開ハッシュ値ｖが含まれ、公開ハッシュ値ｖは挿入順に並んでいる。従って、本ステップでは、挿入を表すタグ「insert」を含む公開ハッシュ値ｖを後ろから順に特定し、その公開ハッシュ値ｖに含まれるブロック番号の挿入ブロックを取り除く。例えば図４８では、３番目のハッシュ値ｈ₆が取り除かれ、ハッシュ値リストＨ＝｛ｈ₁，ｈ₂，ｈ₃，ｈ₄，ｈ₅｝となる。そして、ハッシュ値検証部７５は、特定された変更者ｋについての処理が完了した旨を署名検証部７６に通知する。
【０２７９】
そして、署名検証部７６は、ハッシュ値検証部７５から完了通知を受信すると、全ての変更者について処理が完了したか判断する（ステップＳ５１３）。全ての変更者について処理が完了していなければ（ステップＳ５１３：Ｎｏルート）、ステップＳ５０５に戻り、上で述べた処理を繰り返す。すなわち、最終変更者から順に、最初にコンテンツ変更を行った変更者まで、上で述べたような処理が繰り返される。なお、全ての変更者について、上で述べたような処理を実施することで、全ての挿入ブロックに対応するハッシュ値がハッシュ値リストＨから取り除かれ、元のコンテンツの状態に戻ることになる。
【０２８０】
一方、全ての変更者について処理が完了した場合（ステップＳ５１３：Ｙｅｓルート）、署名検証部７６は、公開鍵格納部７３１から署名者の公開鍵を読み出し、電子署名格納部７３４から署名者に係る電子署名σ₀を読み出す。そして、署名検証部７６は、署名者の公開鍵と、復元されたハッシュ値リストＨとを基に、署名者に係る電子署名σ₀の検証処理を実施する（ステップＳ５１５）。なお、電子署名の検証処理は、従来と変わらないので、これ以上述べない。
【０２８１】
そして、ステップＳ５１５における検証に成功した場合（ステップＳ５１７：Ｙｅｓルート）、検証に成功した旨を出力部７２に通知する。そして、出力部７２は、検証成功を表示装置等に出力する（ステップＳ５１９）。そして、処理を終了する。
【０２８２】
一方、ステップＳ５０７における検証に失敗した場合（ステップＳ５０９：Ｎｏルート）、又は、ステップＳ５１５における検証に失敗した場合（ステップＳ５１７：Ｎｏルート）、出力部７２が、検証失敗を表示装置等に出力する（ステップＳ５２１）。なお、いずれの検証に失敗したかを併せて表示するようにしてもよい。そして、処理を終了する。
【０２８３】
以上のようにＲＣＳ型ＰＩＡＴを変形することにより、第４の実施の形態よりも少ないデータ量で、ブロック挿入時の部分完全性保証を実現することができるようになる。
【０２８４】
図５２に、リンクテーブルを用いる方式（方式１）、挿入テーブルを用いる方式（方式２）及びタグを用いる方式（方式３）と、従来のＰＩＡＴとの公開データ量の比較例を示す。なお、１時間の動画（３２フレーム／秒、１ＧＯＰ：１６フレーム、１ＧＯＰ：１ブロック）の１ブロック目にブロックを１つ挿入する場面を想定する。また、署名を1024-bit、ハッシュ値を160-bit、ＩＤ（挿入位置番号、ブロック番号、タグ等）の付加情報を１つ当たり32-bitとする。例えば、ＳＣＣＳ型ＰＩＡＴの方式３を採用することで、従来のＳＣＣＳ型ＰＩＡＴに比べて公開データ量を約４２％（２．３分の１）に削減できる。また、例えば、ＲＣＳ型ＰＩＡＴの方式３を採用することで、従来のＲＣＳ型ＰＩＡＴに比べて公開データ量を約７５３分の１に削減できる。
【０２８５】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明した署名者端末３、変更者端末５及び検証者端末７の機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。各端末の機能を一台のコンピュータに実装することも可能である。
【０２８６】
また、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。また、並列に実行させるようにしても良い。
【０２８７】
なお、上で述べた署名者端末３、変更者端末５及び検証者端末７は、コンピュータ装置であって、図５３に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０２８８】
以上述べた本技術の実施の形態をまとめると以下のとおりになる。
【０２８９】
第１の態様に係るコンテンツ処理装置は、（ｚ）更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部（図５４：管理データ格納部２０１１）と、（ａ）複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段（図５４：受付部２００１）と、（ｂ）更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段（図５４：挿入部２００３）と、（ｃ）更新ブロックに対するハッシュ値を計算する第１ハッシュ値計算手段（図５４：ハッシュ値計算部２００５）と、（ｄ）管理データ格納部から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と、更新位置と、更新ブロックに対するハッシュ値と、更新種別とを含む更新記録情報に対して、秘密鍵を用いて電子署名を生成する署名手段（図５４：署名部２００７）と、（ｅ）更新済みコンテンツと更新記録情報と電子署名とを出力する出力手段（図５４：出力部２００９）とを有する。
【０２９０】
このように、更新者識別子と、更新位置と、更新ブロックに対するハッシュ値と、更新種別（挿入）とを含む更新記録情報を生成するようにすることで、検証時に、ブロックが挿入されたことと、挿入位置とを認識できるようになる。すなわち、挿入されたブロックの後方の各ブロックは変更されていないものとして扱うことができるようになる。また、挿入されたブロックについてのみ更新記録情報が生成されるので、コンテンツの部分完全性保証のために必要なデータ量を抑えることができる。なお、更新記録情報に対する電子署名を生成・出力するので、ＳＣＣＳ型ＰＩＡＴで部分完全性保証を実現できるようになる。
【０２９１】
また、第１の態様に係るコンテンツ処理装置が、（ｆ）他のコンテンツ処理装置から、更新済みコンテンツと当該更新済みコンテンツに対応する更新記録情報と電子署名とを受信する受信手段と、（ｇ）受信した更新済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する第２ハッシュ値計算手段と、（ｈ）受信した更新記録情報に含まれる更新者識別子に対応する公開鍵を取得する鍵取得手段と、（ｉ）受信した更新記録情報と公開鍵とを用いて、受信した電子署名を検証する署名検証手段と、（ｊ）受信した更新記録情報に含まれる更新種別が挿入であった場合、計算されたハッシュ値のうち当該更新記録情報に含まれる更新位置のブロックに対するハッシュ値と、当該更新記録情報に含まれるハッシュ値とを比較することにより、当該更新位置のブロックの正当性を確認する挿入操作検証手段とをさらに有するようにしてもよい。このようにすれば、電子署名を検証し、更新位置のブロックの正当性が確認されるので、ブロック更新者を保証し、且つその挿入されたブロックに改ざんがないことを証明できるようになる。
【０２９２】
さらに、第１の態様において、上で述べた受信手段が、ブロック更新前のコンテンツに含まれる複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストと、当該更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とをさらに受信する場合もある。そして、上で述べた署名検証手段が、受信した更新前ハッシュ値リストと、作成者の公開鍵とを用いて、受信した更新前電子署名を検証する場合もある。また、上で述べた挿入操作検証手段が、更新済みコンテンツに含まれる、更新ブロック以外の各ブロックについて、第２ハッシュ値計算手段により計算された、当該ブロックのハッシュ値と、更新前ハッシュ値リストに含まれ且つ当該ブロックに対応するハッシュ値とを比較することにより、更新ブロック以外のブロックの正当性を確認する場合もある。このようにすれば、挿入されたブロック以外のブロックの正当性が確認されるので、挿入されたブロック以外のブロックが元のコンテンツから引き継いだものであることを保証できるようになる。
【０２９３】
第２の態様に係るコンテンツ処理装置は、（Ｚ）更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部（図５５：管理データ格納部２１１１）と、（Ａ）複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段（図５５：受付部２１０１）と、（Ｂ）更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段（図５５：挿入部２１０３）と、（Ｃ）生成した更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成手段（図５５：ハッシュ値リスト生成部２１０５）と、（Ｄ）管理データ格納部から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と更新位置と更新種別とを含む更新記録情報と、ハッシュ値リストとに対して、秘密鍵を用いて電子署名を生成する署名手段（図５５：署名部２１０７）と、（Ｅ）更新済みコンテンツと更新記録情報と電子署名とを出力する出力手段（図５５：出力部２１０９）とを有する。
【０２９４】
このように、更新者識別子と更新位置と更新種別（挿入）とを含む更新記録情報を生成するようにすることで、検証時に、ブロックが挿入されたことと、挿入位置とを認識できるようになる。なお、ハッシュ値リスト及び更新記録情報に対する電子署名を生成・出力するので、ＲＣＳ型ＰＩＡＴで部分完全性保証を実現できるようになる。
【０２９５】
また、第２の態様に係るコンテンツ処理装置が、（Ｆ）他のコンテンツ処理装置から、更新済みコンテンツと、当該更新済みコンテンツに対応する更新記録情報と、電子署名と、ブロック更新前のコンテンツに含まれる複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とを受信する受信手段と、（Ｇ）受信した更新記録情報に含まれる更新者識別子に対応する公開鍵を取得する鍵取得手段と、（Ｈ）受信した更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各ブロックのハッシュ値を含むハッシュ値リストを生成する第２ハッシュ値リスト生成手段と、（Ｉ）受信した更新記録情報に含まれる更新種別が挿入であった場合、第２ハッシュ値リスト生成手段により生成されたハッシュ値リストと、当該更新記録情報と、公開鍵とを用いて、受信した電子署名を検証するとともに、第２ハッシュ値リスト生成手段により生成されたハッシュ値リストから更新ブロックに対するハッシュ値を取り除いたハッシュ値リストと、作成者の公開鍵とを用いて、更新前電子署名を検証する署名検証手段とをさらに有するようにしてもよい。このようにすれば、ハッシュ値リストと更新記録情報と公開鍵とを用いて電子署名が検証されるので、ブロック更新者を保証し、且つその挿入されたブロックに改ざんがないことを証明できるようになる。また、更新前電子署名が検証されるので、挿入されたブロック以外のブロックが元のコンテンツから引き継いだものであることを保証できるようになる。
【０２９６】
第３の態様に係る情報処理方法は、コンテンツの部分完全性保証のための情報処理方法である。そして、本方法は、（ａ）複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップ（図５６：Ｓ１００１）と、（ｂ）更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップ（図５６：Ｓ１００３）と、（ｃ）更新ブロックに対するハッシュ値を計算するハッシュ値計算ステップ（図５６：Ｓ１００５）と、（ｄ）更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部（ｚ）から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と、更新位置と、更新ブロックに対するハッシュ値と、更新種別とを含む更新記録情報に対して、秘密鍵を用いて電子署名を生成する署名ステップ（図５６：Ｓ１００７及びＳ１００９）と、（ｅ）更新済みコンテンツと更新記録情報と電子署名とを出力する出力ステップ（図５６：Ｓ１０１１）とを含む。
【０２９７】
第４の態様に係る情報処理方法は、コンテンツの部分完全性保証のための情報処理方法である。そして、本方法は、（Ａ）複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップ（図５７：Ｓ１１０１）と、（Ｂ）更新種別が挿入であった場合、コンテンツにおける更新位置に更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップ（図５７：Ｓ１１０３）と、（Ｃ）生成した更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成ステップ（図５７：Ｓ１１０５）と、（Ｄ）更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部（Ｚ）から更新者識別子及び秘密鍵を読み出し、当該更新者識別子と更新位置と更新種別とを含む更新記録情報と、ハッシュ値リストとに対して、秘密鍵を用いて電子署名を生成する署名ステップ（図５７：Ｓ１１０７及びＳ１１０９）と、（Ｅ）更新済みコンテンツと更新記録情報と電子署名とを出力する出力ステップ（図５７：Ｓ１１１１）とを含む。
【０２９８】
なお、上で述べたような処理を署名者端末３、変更者端末５及び検証者端末７に実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。また、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【０２９９】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０３００】
（付記１）
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、
前記更新ブロックに対するハッシュ値を計算する第１ハッシュ値計算手段と、
前記管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名手段と、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力手段と、
を有するコンテンツ処理装置。
【０３０１】
（付記２）
他のコンテンツ処理装置から、前記更新済みコンテンツと当該更新済みコンテンツに対応する前記更新記録情報と前記電子署名とを受信する受信手段と、
受信した前記更新済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する第２ハッシュ値計算手段と、
受信した前記更新記録情報に含まれる前記更新者識別子に対応する公開鍵を取得する鍵取得手段と、
受信した前記更新記録情報と前記公開鍵とを用いて、受信した前記電子署名を検証する署名検証手段と、
受信した前記更新記録情報に含まれる前記更新種別が挿入であった場合、計算された前記ハッシュ値のうち当該更新記録情報に含まれる前記更新位置のブロックに対するハッシュ値と、当該更新記録情報に含まれる前記ハッシュ値とを比較することにより、当該更新位置のブロックの正当性を確認する挿入操作検証手段と、
をさらに有する付記１記載のコンテンツ処理装置。
【０３０２】
（付記３）
前記受信手段が、ブロック更新前の前記コンテンツに含まれる前記複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストと、当該更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とをさらに受信し、
前記署名検証手段が、受信した前記更新前ハッシュ値リストと、前記作成者の公開鍵とを用いて、受信した前記更新前電子署名を検証し、
前記挿入操作検証手段が、前記更新済みコンテンツに含まれる、前記更新ブロック以外の各ブロックについて、前記第２ハッシュ値計算手段により計算された、当該ブロックのハッシュ値と、前記更新前ハッシュ値リストに含まれ且つ当該ブロックに対応するハッシュ値とを比較することにより、前記更新ブロック以外のブロックの正当性を確認する
付記２記載のコンテンツ処理装置。
【０３０３】
（付記４）
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、
生成した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成手段と、
前記管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と前記更新位置と前記更新種別とを含む更新記録情報と、前記ハッシュ値リストとに対して、前記秘密鍵を用いて電子署名を生成する署名手段と、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力手段と、
を有するコンテンツ処理装置。
【０３０４】
（付記５）
他のコンテンツ処理装置から、前記更新済みコンテンツと、当該更新済みコンテンツに対応する前記更新記録情報と、前記電子署名と、ブロック更新前の前記コンテンツに含まれる前記複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とを受信する受信手段と、
受信した前記更新記録情報に含まれる前記更新者識別子に対応する公開鍵を取得する鍵取得手段と、
受信した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第２ハッシュ値リスト生成手段と、
受信した前記更新記録情報に含まれる前記更新種別が挿入であった場合、前記第２ハッシュ値リスト生成手段により生成された前記ハッシュ値リストと、当該更新記録情報と、前記公開鍵とを用いて、受信した前記電子署名を検証するとともに、前記第２ハッシュ値リスト生成手段により生成された前記ハッシュ値リストから前記更新ブロックに対するハッシュ値を取り除いたハッシュ値リストと、前記作成者の公開鍵とを用いて、前記更新前電子署名を検証する署名検証手段と、
をさらに有する付記４記載のコンテンツ処理装置。
【０３０５】
（付記６）
コンテンツの部分完全性保証のための処理をコンピュータに実行させるためのプログラムであって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
前記更新ブロックに対するハッシュ値を計算するハッシュ値計算ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
をコンピュータに実行させるためのプログラム。
【０３０６】
（付記７）
コンテンツの部分完全性保証のための処理をコンピュータに実行させるためのプログラムであって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
生成した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と前記更新位置と前記更新種別とを含む更新記録情報と、前記ハッシュ値リストとに対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
をコンピュータに実行させるためのプログラム。
【０３０７】
（付記８）
コンテンツの部分完全性保証のための情報処理方法であって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
前記更新ブロックに対するハッシュ値を計算するハッシュ値計算ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
を含み、コンピュータにより実行される情報処理方法。
【０３０８】
（付記９）
コンテンツの部分完全性保証のための情報処理方法であって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
生成した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と前記更新位置と前記更新種別とを含む更新記録情報と、前記ハッシュ値リストとに対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
を含み、コンピュータにより実行される情報処理方法。
【符号の説明】
【０３０９】
１ ネットワーク
３ 署名者端末
５ａ，５ｂ，５ｃ 変更者端末
７ 検証者端末
３１ 入力部 ３２ 出力部 ３３ メモリ部
３４ 分割部 ３５ ハッシュ値計算部 ３６ 署名部
５１ 入力部 ５２ 出力部 ５３ メモリ部
５４ コンテンツ変更部 ５５ ハッシュ値計算部 ５６ 署名部
５７ 検証部 ５８ リンクテーブル生成部 ５９ 挿入テーブル生成部
６０ タグ設定部
７１ 入力部 ７２ 出力部 ７３ メモリ部
７４ ハッシュ値計算部 ７５ ハッシュ値検証部 ７６ 署名検証部
３３１ 管理データ格納部 ３３２ コンテンツ格納部
３３３ ハッシュ値格納部 ３３４ 電子署名格納部
５３１ 管理データ格納部 ５３２ コンテンツ格納部
５３３ ハッシュ値格納部 ５３４ 電子署名格納部
５３５ リンクテーブル格納部 ５３６ 挿入テーブル格納部
７３１ 公開鍵格納部 ７３２ コンテンツ格納部
７３３ ハッシュ値格納部 ７３４ 電子署名格納部
７３５ リンクテーブル格納部 ７３６ 挿入テーブル格納部

【特許請求の範囲】
【請求項１】
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、
前記更新ブロックに対するハッシュ値を計算する第１ハッシュ値計算手段と、
前記管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名手段と、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力手段と、
を有するコンテンツ処理装置。
【請求項２】
他のコンテンツ処理装置から、前記更新済みコンテンツと当該更新済みコンテンツに対応する前記更新記録情報と前記電子署名とを受信する受信手段と、
受信した前記更新済みコンテンツに含まれる各ブロックに対するハッシュ値を計算する第２ハッシュ値計算手段と、
受信した前記更新記録情報に含まれる前記更新者識別子に対応する公開鍵を取得する鍵取得手段と、
受信した前記更新記録情報と前記公開鍵とを用いて、受信した前記電子署名を検証する署名検証手段と、
受信した前記更新記録情報に含まれる前記更新種別が挿入であった場合、計算された前記ハッシュ値のうち当該更新記録情報に含まれる前記更新位置のブロックに対するハッシュ値と、当該更新記録情報に含まれる前記ハッシュ値とを比較することにより、当該更新位置のブロックの正当性を確認する挿入操作検証手段と、
をさらに有する請求項１記載のコンテンツ処理装置。
【請求項３】
前記受信手段が、ブロック更新前の前記コンテンツに含まれる前記複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストと、当該更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とをさらに受信し、
前記署名検証手段が、受信した前記更新前ハッシュ値リストと、前記作成者の公開鍵とを用いて、受信した前記更新前電子署名を検証し、
前記挿入操作検証手段が、前記更新済みコンテンツに含まれる、前記更新ブロック以外の各ブロックについて、前記第２ハッシュ値計算手段により計算された、当該ブロックのハッシュ値と、前記更新前ハッシュ値リストに含まれ且つ当該ブロックに対応するハッシュ値とを比較することにより、前記更新ブロック以外のブロックの正当性を確認する
請求項２記載のコンテンツ処理装置。
【請求項４】
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部と、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付手段と、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入手段と、
生成した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第１ハッシュ値リスト生成手段と、
前記管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と前記更新位置と前記更新種別とを含む更新記録情報と、前記ハッシュ値リストとに対して、前記秘密鍵を用いて電子署名を生成する署名手段と、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力手段と、
を有するコンテンツ処理装置。
【請求項５】
他のコンテンツ処理装置から、前記更新済みコンテンツと、当該更新済みコンテンツに対応する前記更新記録情報と、前記電子署名と、ブロック更新前の前記コンテンツに含まれる前記複数ブロックの各々に対応するハッシュ値を含む更新前ハッシュ値リストに対し、当該コンテンツの作成者の秘密鍵によって生成された更新前電子署名とを受信する受信手段と、
受信した前記更新記録情報に含まれる前記更新者識別子に対応する公開鍵を取得する鍵取得手段と、
受信した前記更新済みコンテンツに含まれる各ブロックのハッシュ値を計算し、各前記ブロックのハッシュ値を含むハッシュ値リストを生成する第２ハッシュ値リスト生成手段と、
受信した前記更新記録情報に含まれる前記更新種別が挿入であった場合、前記第２ハッシュ値リスト生成手段により生成された前記ハッシュ値リストと、当該更新記録情報と、前記公開鍵とを用いて、受信した前記電子署名を検証するとともに、前記第２ハッシュ値リスト生成手段により生成された前記ハッシュ値リストから前記更新ブロックに対するハッシュ値を取り除いたハッシュ値リストと、前記作成者の公開鍵とを用いて、前記更新前電子署名を検証する署名検証手段と、
をさらに有する請求項４記載のコンテンツ処理装置。
【請求項６】
コンテンツの部分完全性保証のための処理をコンピュータに実行させるためのプログラムであって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
前記更新ブロックに対するハッシュ値を計算するハッシュ値計算ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
をコンピュータに実行させるためのプログラム。
【請求項７】
コンテンツの部分完全性保証のための情報処理方法であって、
複数ブロックに分割されているコンテンツと、当該コンテンツに対する更新の種類を示す更新種別と、当該コンテンツにおいて更新すべき更新ブロックと、更新位置とを受け付ける受付ステップと、
前記更新種別が挿入であった場合、前記コンテンツにおける前記更新位置に前記更新ブロックを挿入することにより更新済みコンテンツを生成する挿入ステップと、
前記更新ブロックに対するハッシュ値を計算するハッシュ値計算ステップと、
更新者識別子と秘密鍵とを対応付けて格納する管理データ格納部から前記更新者識別子及び前記秘密鍵を読み出し、当該更新者識別子と、前記更新位置と、前記更新ブロックに対する前記ハッシュ値と、前記更新種別とを含む更新記録情報に対して、前記秘密鍵を用いて電子署名を生成する署名ステップと、
前記更新済みコンテンツと前記更新記録情報と前記電子署名とを出力する出力ステップと、
を含み、コンピュータにより実行される情報処理方法。

【図１】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６】

【図１７】

【図１８】

【図１９】

【図２０】

【図２１】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７】

【図２８】

【図２９】

【図３０】

【図３１】

【図３２】

【図３３】

【図３４】

【図３５】

【図３６】

【図３７】

【図３８】

【図３９】

【図４０】

【図４１】

【図４２】

【図４３】

【図４４】

【図４５】

【図４６】

【図４７】

【図４８】

【図４９】

【図５０】

【図５１】

【図５２】

【図５３】

【図５４】

【図５５】

【図５６】

【図５７】

【公開番号】特開２０１１−７１７７１（Ｐ２０１１−７１７７１Ａ）
【公開日】平成２３年４月７日（２０１１．４．７）
【国際特許分類】
【出願番号】特願２００９−２２１４６６（Ｐ２００９−２２１４６６）
【出願日】平成２１年９月２５日（２００９．９．２５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】