(57)【要約】      （修正有）【課題】ハッシュデータの再計算に要する演算量をより少なくする。【解決手段】情報処理装置は、元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、元データを識別する第１ハッシュ行列Ａ＊３を算出する第１算出部と、元データの一部が変更された場合に、変更ブロックＸ＊３の直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積Ｃ＊３と変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列Ｄ３と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列Ｂを算出する第２算出部とを有する。【選択図】図６
2017146515.tif 000002
【特許請求の範囲】
【請求項１】
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出する第１算出部と、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する第２算出部と
を有する情報処理装置。
【請求項２】
変更ブロックが複数である場合に、前記第２算出部は、前方から順に各変更ブロックについて、当該変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と当該変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列とを順次乗じ、更に前記末尾ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積を乗じて、第２ハッシュ行列を算出する
請求項１記載の情報処理装置。
【請求項３】
更に、
前記変更ブロックの直前の前記ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積と前記変更ブロックに基づく前記部分ハッシュ行列との前記積によって、前記変更される前の元ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積を更新し、前記変更ブロックを特定するブロック番号を繰り下げる修正部を
有し、
前記第２算出部は、繰り下げられた前記ブロック番号によって特定されるブロックを前記変更ブロックとみなす
請求項１又は２記載の情報処理装置。
【請求項４】
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出し、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する
を含み、コンピュータにより実行されるハッシュ生成方法。
【請求項５】
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出し、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する
処理をコンピュータに実行させるハッシュ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュデータを計算する技術に関する。
【背景技術】
【０００２】
元データに基づいてハッシュ値を生成した後に、元データの一部が変更されることがある。このような場合に、変更されたデータに基づくハッシュ値を改めて求めることを想定する。
【０００３】
一般的には、元データの場合と同様の手順によって、変更されたデータに基づくハッシュ値が算出される。
【０００４】
しかし、部分的に変更される場合には、ハッシュ値のようなハッシュデータの再計算に要する演算量が少ない方が望ましい。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−４９０３７号公報
【特許文献２】特開２０１０−４９１２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、一側面では、ハッシュデータの再計算に要する演算量をより少なくすることである。
【課題を解決するための手段】
【０００７】
一態様に係る情報処理装置は、（Ａ）元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、元データを識別する第１ハッシュ行列を算出する第１算出部と、（Ｂ）元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する第２算出部とを有する。
【発明の効果】
【０００８】
一側面としては、ハッシュデータの再計算に要する演算量をより少なくすることができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、ハッシュ値の算出過程を示す図である。
【図２】図２は、ハッシュ値の算出過程を示す図である。
【図３】図３は、ハッシュ値の算出過程を示す図である。
【図４】図４は、ハッシュ値の算出過程を示す図である。
【図５】図５は、行列に関する第１式及び第２式を示す図である。
【図６】図６は、ブロックが変更された場合におけるハッシュ値の算出過程を示す図である。
【図７】図７は、行列に関する第１式及び第２式を示す図である。
【図８】図８は、ブロックが変更された場合におけるハッシュ値の算出過程を示す図である。
【図９】図９は、行列に関する第１式及び第２式を示す図である。
【図１０】図１０は、ブロックが変更された場合におけるハッシュ値の算出過程を示す図である。
【図１１】図１１は、行列に関する第１式及び第２式を示す図である。
【図１２】図１２は、ブロックが変更された場合におけるハッシュ値の算出過程を示す図である。
【図１３】図１３は、行列に関する第１式及び第２式を示す図である。
【図１４】図１４は、ブロックが追加された場合におけるハッシュ値の算出過程を示す図である。
【図１５】図１５は、行列に関する第１式及び第２式を示す図である。
【図１６】図１６は、第１総積を修正する過程を示す図である。
【図１７】図１７は、行列に関する第１式及び第２式を示す図である。
【図１８】図１８は、第１総積を修正する過程を示す図である。
【図１９】図１９は、行列に関する第１式及び第２式を示す図である。
【図２０】図２０は、第１総積を修正する過程を示す図である。
【図２１】図２１は、行列に関する第１式及び第２式を示す図である。
【図２２】図２２は、第１総積を修正する過程を示す図である。
【図２３】図２３は、行列に関する第１式及び第２式を示す図である。
【図２４】図２４は、第１総積を修正する過程を示す図である。
【図２５】図２５は、行列に関する第１式及び第２式を示す図である。
【図２６】図２６は、第１総積を修正する過程を示す図である。
【図２７】図２７は、行列に関する第１式及び第２式を示す図である。
【図２８】図２８は、第１総積を修正する過程を示す図である。
【図２９】図２９は、行列に関する第１式及び第２式を示す図である。
【図３０】図３０は、ハッシュ生成装置のモジュール構成例を示す図である。
【図３１】図３１は、メイン処理フローを示す図である。
【図３２】図３２は、メイン処理フローを示す図である。
【図３３】図３３は、初期算出部のモジュール構成例を示す図である。
【図３４】図３４は、初期処理フローを示す図である。
【図３５】図３５は、変更部のモジュール構成例を示す図である。
【図３６】図３６は、変更処理フローを示す図である。
【図３７】図３７は、追加部のモジュール構成例を示す図である。
【図３８】図３８は、追加処理フローを示す図である。
【図３９】図３９は、算出処理フローを示す図である。
【図４０】図４０は、修正部のモジュール構成例を示す図である。
【図４１】図４１は、修正処理フローを示す図である。
【図４２】図４２は、修正処理フローを示す図である。
【図４３】図４３は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１０】
本実施の形態では、元データのハッシュ値を算出する過程で生成した内部データの一部を保存する。そして、元データが変更された場合に、その内部データを用いて、より少ない演算で新たなハッシュ値を算出する。元データは、例えば１テラバイト程度であってもよい。
【００１１】
図１乃至図４に、最初にハッシュ値の算出過程を示す。更に、当該算出過程で用いられる行列に関する式を図５に示す。この例における第１式は、左辺に示した行列を定義する式である。同じく第２式は、左辺に示した行列を算出する式である。
【００１２】
まず、図１について説明する。ハッシュ値生成の対象である元データを、所定長（例えば６４キビバイト）のブロックに分割する。この例では、Ｎ個に分割されたものとする。ブロック番号ｉは、１からＮまでの自然数である。この例で、ブロックをＸiと記す。つまり、元データをブロックＸ1，ブロックＸ2，ブロックＸ3，・・・，ブロックＸnに分割する。
【００１３】
最初にブロックＸ1から、ハッシュ値Ｈ1が生成される。以下、各ブロックＸiから得られるハッシュ値を第１ハッシュ値という。また、ハッシュ値をＨiと記す。第１ハッシュ値は、元データの一部に基づくので部分的なハッシュ値である。この例におけるハッシュ値の大きさは、２５６ビットである。ハッシュ値を求めるハッシュ関数は、従来技術による。
【００１４】
第１ハッシュ値Ｈ1は、ハッシュ行列Ａ1に変換される。以下、各第１ハッシュ値Ｈiから得られるハッシュ行列を第１ハッシュ行列という。また、第１ハッシュ行列をＡiと記す。第１ハッシュ行列Ａiは、元データの一部に基づくので部分的なハッシュ行列である。この例で、ハッシュ行列Ａiは、４行×４列の正方行列である。
【００１５】
ハッシュ値Ｈiは、１６ビットの符号に分割される。例えば、最下位ビットから１６ビットずつ切り出す。そして、分割により得られた１番目から４番目までの符号を、ハッシュ行列Ａiの第１行の第１列の要素から第４列の要素までに割り当てる。同じく５番目から８番目までの符号を、ハッシュ行列Ａiの第２行の第１列の要素から第４列の要素までに割り当てる。同じく９番目から１２番目までの符号を、ハッシュ行列Ａiの第３行の第１列の要素から第４列の要素までに割り当てる。同じく１３番目から１６番目までの符号を、ハッシュ行列Ａiの第４行の第１列の要素から第４列の要素までに割り当てる。
【００１６】
本実施の形態では、内部データとして、ハッシュ行列Ａiを順次乗じた総積を保持する。初期の元データから生成される総積を第１総積という。また、第１総積をＣiと記す。最初の第１総積は、図５に示した第１式「Ｃ1＝Ａ1」で定義され、同じく第２式「Ｃ1＝Ａ1」によって導かれる。尚、この例では、内部的に保持されるデータを太線で示している。つまり、ブロックＸi及び第１総積Ｃiは、内部に保持される。
【００１７】
次に、図２を用いて２番目のブロックＸ2に対する計算について説明する。２番目のブロックＸ2に基づいて２番目の第１ハッシュ値Ｈ2が算出される。２番目の第１ハッシュ値Ｈ2は、２番目の第１ハッシュ行列Ａ2に変換される。
【００１８】
２番目の第１総積Ｃ2は、図５に示した第１式「Ｃ2＝Ａ1Ａ2」で定義され、同じく第２式「Ｃ2＝Ｃ1Ａ2」によって導かれる。つまり、２番目の第１総積Ｃ2は、１番目の第１総積Ｃ1に２番目の第１ハッシュ行列Ａ2を乗ずることによって求められる。
【００１９】
次に、図３を用いて３番目のブロックＸ3に対する計算について説明する。３番目のブロックＸ3に基づいて３番目の第１ハッシュ値Ｈ3が算出される。３番目の第１ハッシュ値Ｈ3は、３番目の第１ハッシュ行列Ａ3に変換される。
【００２０】
３番目の第１総積Ｃ3は、図５に示した第１式「Ｃ3＝Ａ1Ａ2Ａ3」で定義され、同じく第２式「Ｃ3＝Ｃ2Ａ3」によって導かれる。つまり、３番目の第１総積Ｃ3は、２番目の第１総積Ｃ2に３番目の第１ハッシュ行列Ａ3を乗ずることによって求められる。
【００２１】
Ｎ番目のブロックまで同様の処理を繰り返す。図４は、Ｎ番目のブロックに対する処理を示している。Ｎ番目のブロックＸNに基づいてＮ番目の第１ハッシュ値ＨNが算出される。Ｎ番目の第１ハッシュ値ＨNは、Ｎ番目の第１ハッシュ行列ＡNに変換される。
【００２２】
Ｎ番目の第１総積ＣNは、図５に示した第１式「ＣN＝Ａ1Ａ2Ａ3・・・ＡN」で定義され、同じく第２式「ＣN＝ＣN-1ＡN」によって導かれる。
【００２３】
つまり、Ｎ番目の第１総積ＣNは、Ｎ−１番目の第１総積ＣN-1にＮ番目の第１ハッシュ行列ＡNを乗ずることによって求められる。
【００２４】
元データを識別する第２ハッシュ行列Ｂは、図５に示した第１式「Ａ1Ａ2Ａ3・・・ＡN」で定義され、同じく第２式「Ｂ＝ＣN」によって導かれる。つまり、第１総積ＣNが、元データを識別する第２ハッシュ行列Ｂとなる。
【００２５】
更に、第２ハッシュ行列Ｂは、元データを識別する第２ハッシュ値Ｈtに変換される。この例では、第２ハッシュ行列Ｂの第１行の第１列の要素から第４列の要素までを、１番目から４番目までの符号とする。第２ハッシュ行列Ｂの第２行の第１列の要素から第４列の要素までを、５番目から８番目までの符号とする。第２ハッシュ行列Ｂの第３行の第１列の要素から第４列の要素までを、９番目から１２番目までの符号とする。第２ハッシュ行列Ｂの第４行の第１列の要素から第４列の要素までを、１３番目から１６番目までの符号とする。そして、１番目から１６番目までの符号を結合することによって、第２ハッシュ値Ｈtが生成される。この例における第２ハッシュ値Ｈtの大きさは、２５６ビットである。
【００２６】
以下、一部のブロックが変更される場合について説明する。図６に、第３ブロックが変更された場合におけるハッシュ値の算出過程を示す。変更された第３ブロックをＸ*3と記す。この例では、変更されたブロックに「＊」を付する。この算出過程に関連する行列の第１式及び第２式を図７に示す。
【００２７】
３番目の変更ブロックＸ*3から３番目の新たな第１ハッシュ値Ｈ*3が算出される。この例では、変更された第１ハッシュ値に「＊」を付する。
【００２８】
更に、３番目の新たな第１ハッシュ値Ｈ*3は新たな第１ハッシュ行列Ａ*3に変換される。この例では、変更された第１ハッシュ行列に「＊」を付する。
【００２９】
そして、新たな第１ハッシュ値Ｈ*3までの第２総積Ｃ*3が算出される。３番目の変更ブロックＸ*3に対応する第２総積Ｃ*3は、図７に示した第１式「Ｃ*3＝Ａ1Ａ2Ａ*3」で定義される。このように、変更された第１ハッシュ行列を含む総積を第２総積という。また、第２総積をＣ*iと記す。尚、第２総積Ｃ*iは、不要になった場合を除き、内部に保持される。
【００３０】
第２総積Ｃ*3は、図７に示した第２式「Ｃ*3＝Ｃ2Ａ*3」によって導かれる。
【００３１】
つまり、３番目の第２総積Ｃ*3は、２番目の第１総積Ｃ2に３番目の新たな第１ハッシュ行列Ａ*3を乗ずることによって求められる。
【００３２】
本実施の形態では、変更ブロックＸ*iに対応する第１総積Ｃiの逆行列Ｄiが求められる。この例で、３番目の変更ブロックＸ*3に対応する逆行列Ｄ3は、図７に示した第１式「Ｄ3＝（Ａ1Ａ2Ａ3）-1」で定義され、同じく第２式「Ｄ3＝Ｃ3-1」によって導かれる。尚、逆行列Ｄiは、不要になった場合を除き、内部に保持される。
【００３３】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図７に示した第１式「Ｂ＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ6Ａ7Ａ8」で定義され、同じく第２式「Ｃ*3Ｄ3Ｃ8」によって導かれる。
【００３４】
つまり、この状態における第２ハッシュ行列Ｂは、３番目の第２総積Ｃ*3に３番目の逆行列Ｄ3を乗じ、更に末尾ブロックに対応する８番目の第１総積Ｃ8を乗ずることによって求められる。そして、第２ハッシュ行列Ｂが第２ハッシュ値Ｈtに変換される。
【００３５】
図８を用いて、更に第６ブロックＸ6が変更された場合におけるハッシュ値の算出過程について説明する。この算出過程に関連する行列の第１式及び第２式を図９に示す。
【００３６】
６番目の変更ブロックＸ*6から６番目の新たな第１ハッシュ値Ｈ*6が算出される。更に、６番目の新たな第１ハッシュ値Ｈ*6は新たな第１ハッシュ行列Ａ*6に変換される。
【００３７】
そして、新たな第１ハッシュ値Ｈ*6までの第２総積Ｃ*6が算出される。６番目の変更ブロックＸ*6に対応する第２総積Ｃ*6は、図９に示した第１式「Ｃ*6＝Ａ1Ａ2Ａ3Ａ4Ａ5Ａ*6」で定義され、同じく第２式「Ｃ*6＝Ｃ5Ａ*6」によって導かれる。
【００３８】
つまり、６番目の第２総積Ｃ*6は、５番目の第１総積Ｃ5に６番目の新たな第１ハッシュ行列Ａ*6を乗ずることによって求められる。
【００３９】
また、６番目の変更ブロックＸ*6に対応する逆行列Ｄ6は、図９に示した第１式「Ｄ6＝（Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6）-1」で定義され、同じく第２式「Ｄ6＝Ｃ6-1」によって導かれる。
【００４０】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図９に示した第１式「Ｂ＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ*6Ａ7Ａ8」で定義され、同じく第２式「Ｂ＝Ｃ*3Ｄ3Ｃ*6Ｄ6Ｃ8」によって導かれる。
【００４１】
つまり、この状態における第２ハッシュ行列Ｂは、３番目の第２総積Ｃ*3に３番目の逆行列Ｄ3を乗じ、更に６番目の第２総積Ｃ*6と６番目の逆行列Ｄ6とを乗じた積に、末尾ブロックに対応する８番目の第１総積Ｃ8を乗ずることによって求められる。そして、第２ハッシュ行列Ｂが第２ハッシュ値Ｈtに変換される。
【００４２】
図１０を用いて、更に第２ブロックＸ2が変更された場合におけるハッシュ値の算出過程について説明する。この算出過程に関連する行列の第１式及び第２式を図１１に示す。
【００４３】
２番目の変更ブロックＸ*2から２番目の新たな第１ハッシュ値Ｈ*2が算出される。更に、２番目の新たな第１ハッシュ値Ｈ*2は新たな第１ハッシュ行列Ａ*2に変換される。
【００４４】
そして、新たな第１ハッシュ値Ｈ*2までの第２総積Ｃ*2が算出される。２番目の変更ブロックＸ*6に対応する第２総積Ｃ*2は、図１１に示した第１式「Ｃ*2＝Ａ1Ａ*2」で定義され、同じく第２式「Ｃ*2＝Ｃ1Ａ*2」によって導かれる。つまり、２番目の第２総積Ｃ*2は、１番目の第１総積Ｃ1に２番目の新たな第１ハッシュ行列Ａ*2を乗ずることによって求められる。
【００４５】
また、２番目の変更ブロックＸ*2に対応する逆行列Ｄ2は、図１１に示した第１式「Ｄ2＝（Ａ1Ａ2）-1」で定義され、同じく第２式「Ｄ2＝Ｃ2-1」によって導かれる。
【００４６】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図１１に示した第１式「Ｂ＝Ａ1Ａ*2Ａ*3Ａ4Ａ5Ａ*6Ａ7Ａ8」で定義され、同じく第２式「Ｂ＝Ｃ*2Ｄ2Ｃ*3Ｄ3Ｃ*6Ｄ6Ｃ8」によって導かれる。
【００４７】
つまり、この状態における第２ハッシュ行列Ｂは、２番目の第２総積Ｃ*2に２番目の逆行列Ｄ2を乗じ、更に３番目の第２総積Ｃ*3と３番目の逆行列Ｄ3とを乗じ、加えて６番目の第２総積Ｃ*6と６番目の逆行列Ｄ6とを乗じた積に、末尾ブロックに対応する８番目の第１総積Ｃ8を乗ずることによって求められる。そして、第２ハッシュ行列Ｂが第２ハッシュ値Ｈtに変換される。
【００４８】
次に、図１２を用いて、末尾ブロックが変更された場合におけるハッシュ値の算出過程について説明する。この算出過程に関連する行列の第１式及び第２式を図１３に示す。
【００４９】
８番目の変更ブロックＸ*8から８番目の新たな第１ハッシュ値Ｈ*8が算出される。更に、８番目の新たな第１ハッシュ値Ｈ*8は新たな第１ハッシュ行列Ａ*8に変換される。
【００５０】
そして、新たな第１ハッシュ値Ｈ*8までの第２総積Ｃ*8が算出される。８番目の変更ブロックＸ*8に対応する第２総積Ｃ*8は、図１３に示した第１式「Ｃ*8＝Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7Ａ*8」で定義され、同じく第２式「Ｃ*8＝Ｃ7Ａ*8」によって導かれる。
【００５１】
つまり、８番目の第２総積Ｃ*8は、７番目の第１総積Ｃ7に８番目の新たな第１ハッシュ行列Ａ*8を乗ずることによって求められる。
【００５２】
また、８番目の変更ブロックＸ*8に対応する逆行列Ｄ8は、図１３に示した第１式「Ｄ8＝（Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7Ａ8）-1」で定義され、同じく第２式「Ｄ8＝Ｃ8-1」によって導かれる。
【００５３】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図１３に示した第１式「Ｂ＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ6Ａ7Ａ*8」で定義され、同じく第２式「Ｂ＝Ｃ*3Ｄ3Ｃ*8」によって導かれる。
【００５４】
つまり、この状態における第２ハッシュ行列Ｂは、３番目の第２総積Ｃ*3に３番目の逆行列Ｄ3を乗じ、変更ブロックＸ*8に対応する８番目の第２総積Ｃ*8を乗ずることによって求められる。このとき、逆行列Ｄ8を用いない。但し、逆行列Ｄ8は、後に第２ハッシュ行列Ｂを算出する場合に用いられることがある。
【００５５】
続いて、図１４を用いて、末尾ブロックの後にブロックが追加された場合におけるハッシュ値の算出過程について説明する。この算出過程に関連する行列の第１式及び第２式を図１５に示す。
【００５６】
追加された９番目のブロックＸ9から第１ハッシュ値Ｈ9が算出される。更に、第１ハッシュ値Ｈ*9は第１ハッシュ行列Ａ9に変換される。
【００５７】
そして、第１ハッシュ値Ｈ9までの第１総積Ｃ9が算出される。９番目のブロックＸ*9に対応する第１総積Ｃ9は、図１５に示した第１式「Ｃ9＝Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7Ａ8Ａ9」で定義され、同じく第２式「Ｃ9＝Ｃ8Ａ9」によって導かれる。つまり、９番目の第１総積Ｃ9は、８番目の第１総積Ｃ8に第１ハッシュ行列Ａ9を乗ずることによって求められる。
【００５８】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図１５に示した第１式「Ｂ＝Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7Ａ8Ａ9」で定義され、同じく第２式「Ｂ＝Ｃ9」によって導かれる。つまり、第１総積Ｃ9が、第２ハッシュ行列Ｂとなる。そして、第２ハッシュ行列Ｂが第２ハッシュ値Ｈtに変換される。
【００５９】
上述したように、変更ブロックＸ*iの数が増えると、第２ハッシュ行列Ｂを算出する式の項数が増える。従って、第２ハッシュ行列Ｂを算出するための演算量が多くなる。また、内部で保持する第２総積Ｃ*i及び逆行列Ｄiの数も増える。その結果、記憶量が多くなる。これらの弊害を解消するために、本実施の形態では、第１総積Ｃiを修正することによって、第２総積Ｃ*i及び逆行列Ｄiを減らし、演算量も削減する。
【００６０】
図１６は、３番目、４番目及び６番目のブロックが変更された状態で、３番目の第１総積Ｃ3を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図１７に示す。
【００６１】
まず、既に変更されたブロックのうち先頭のブロックを特定する。この例では、変更ブロックＸ*3が特定される。
【００６２】
そして、変更ブロックＸ*3に対応する第２総積Ｃ*3を、変更ブロックＸ*3に対応する第１総積Ｃ[3]にコピーする。この例では、更新された第１総積の番号に角括弧を付する。
【００６３】
次に、更新された第１総積Ｃ[3]に基づいて、変更ブロックＸ*3の次のブロックＸ4に対応する第２総積Ｃ4を改める。
【００６４】
そのため、４番目のブロックＸ4から第１ハッシュ値Ｈ4が算出される。更に、第１ハッシュ値Ｈ4は第１ハッシュ行列Ａ4に変換される。
【００６５】
そして、ブロックＸ4に対応する第２総積Ｃ*4が算出される。この例では、更新された第２総積に「＊」を付する。第２総積Ｃ*4は、図１７に示した第１式「Ｃ*4＝Ａ1Ａ2Ａ*3Ａ4」で定義され、同じく第２式「Ｃ*4＝Ｃ[3]Ａ4」によって導かれる。つまり、第２総積Ｃ*4は、３番目の更新された第２総積Ｃ[3]に第１ハッシュ行列Ａ4を乗ずることによって求められる。
【００６６】
更に、ブロックＸ4に対応する逆行列Ｄ4が生成される。逆行列Ｄ4は、図１７に示した第１式「Ｄ4＝（Ａ1Ａ2Ａ3Ａ4）-1」で定義され、同じく第２式「Ｄ4＝Ｃ4-1」によって導かれる。
【００６７】
そして、変更ブロックＸ*3に対応する第２総積Ｃ*3及び逆行列Ｄ3は削除される。
【００６８】
この状態で第２ハッシュ値Ｈtを求める処理について説明する。この状態における第２ハッシュ行列Ｂは、図１７に示した第１式「Ｂ＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ*6Ａ7Ａ8」で定義され、同じく第２式「Ｂ＝Ｃ*4Ｄ4Ｃ*6Ｄ6Ｃ8」によって導かれる。
【００６９】
つまり、この状態における第２ハッシュ行列Ｂは、４番目の第２総積Ｃ*4に４番目の逆行列Ｄ4を乗じ、更に６番目の第２総積Ｃ*6と６番目の逆行列Ｄ6とを乗じた積に、末尾ブロックに対応する８番目の第１総積Ｃ8を乗ずることによって求められる。そして、第２ハッシュ行列Ｂが第２ハッシュ値Ｈtに変換される。
【００７０】
以降、変更ブロックＸ*3は、変更されていないブロックに相当すると看做され、次のブロックＸ*4が変更ブロックに相当すると看做される。尚、変更ブロック或いは変更ブロックに相当すると看做されるブロックの番号は、後述する更新リストに登録される。そして、変更ブロック或いは変更ブロックに相当すると看做されるブロックのうち、先頭のブロックを特定して、第１総積Ｃiを修正する処理を繰り返す。
【００７１】
図１８は、図１６に示した状態に引き続き、４番目の第１総積Ｃ4を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図１９に示す。
【００７２】
まず、変更ブロックに相当すると看做されるブロックＸ4が特定される。そして、ブロックＸ*4に対応する第２総積Ｃ*4を、第１総積Ｃ[4]にコピーする。
【００７３】
次に、更新された第１総積Ｃ[4]に基づいて、次のブロックＸ5に対応する第２総積Ｃ*5が計算される。そのため、５番目のブロックＸ5から第１ハッシュ値Ｈ5が算出される。更に、第１ハッシュ値Ｈ*5は第１ハッシュ行列Ａ5に変換される。
【００７４】
そして、ブロックＸ5に対応する第２総積Ｃ*5が算出される。第２総積Ｃ*5は、図１９に示した第１式「Ｃ*5＝Ａ1Ａ2Ａ*3Ａ4Ａ5」で定義され、同じく第２式「Ｃ*5＝Ｃ[4]Ａ5」によって導かれる。つまり、第２総積Ｃ*5は、４番目の更新された第２総積Ｃ[4]に第１ハッシュ行列Ａ5を乗ずることによって求められる。
【００７５】
更に、ブロックＸ5に対応する逆行列Ｄ5が生成される。逆行列Ｄ5は、図１９に示した第１式「Ｄ5＝（Ａ1Ａ2Ａ3Ａ4Ａ5）-1」で定義され、同じく第２式「Ｄ5＝Ｃ5-1」によって導かれる。
【００７６】
そして、ブロックＸ*4に対応する第２総積Ｃ*4及び逆行列Ｄ4は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。
【００７７】
図２０は、図１８に示した状態に引き続き、５番目の第１総積Ｃ5を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図２１に示す。
【００７８】
まず、変更ブロックに相当すると看做されるブロックＸ5が特定される。そして、ブロックＸ5に対応する第２総積Ｃ*5を、第１総積Ｃ[5]にコピーする。
【００７９】
次に、更新された第１総積Ｃ[5]に基づいて、次の変更ブロックＸ*6に対応する第２総積Ｃ*6を改める。そのため、５番目のブロックＸ*6から第１ハッシュ値Ｈ*6が算出される。更に、第１ハッシュ値Ｈ*6は第１ハッシュ行列Ａ*6に変換される。
【００８０】
そして、ブロックＸ*6に対応する第２総積Ｃ**6が算出される。この例では、更新された第２総積に更に「＊」を付する。第２総積Ｃ**6は、図２１に示した第１式「Ｃ**6＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ*6」で定義され、同じく第２式「Ｃ**6＝Ｃ[5]Ａ*6」によって導かれる。つまり、第２総積Ｃ**6は、５番目の更新された第２総積Ｃ[5]に第１ハッシュ行列Ａ*6を乗ずることによって求められる。
【００８１】
更に、ブロックＸ6に対応する逆行列Ｄ6が生成される。逆行列Ｄ6は、図２１に示した第１式「Ｄ6＝（Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6）-1」で定義され、同じく第２式「Ｄ6＝Ｃ6-1」によって導かれる。
【００８２】
そして、ブロックＸ5に対応する第２総積Ｃ*5及び逆行列Ｄ5は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。
【００８３】
図２２は、図２０に示した状態に引き続き、６番目の第１総積Ｃ6を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図２３に示す。
【００８４】
まず、変更ブロックＸ*6が特定される。そして、変更ブロックＸ*6に対応する第２総積Ｃ**6を、第１総積Ｃ[6]にコピーする。
【００８５】
次に、更新された第１総積Ｃ[6]に基づいて、次のブロックＸ7に対応する第２総積Ｃ**7を生成する。そのため、７番目のブロックＸ7から第１ハッシュ値Ｈ7が算出される。更に、第１ハッシュ値Ｈ7は第１ハッシュ行列Ａ7に変換される。
【００８６】
そして、ブロックＸ7に対応する第２総積Ｃ**7が算出される。この例では、第２総積Ｃ**6に引き続き「＊」を２つ付する。第２総積Ｃ**7は、図２３に示した第１式「Ｃ**7＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ*6Ａ7」で定義され、同じく第２式「Ｃ**7＝Ｃ[6]Ａ7」によって導かれる。つまり、第２総積Ｃ**7は、６番目の更新された第２総積Ｃ[6]に第１ハッシュ行列Ａ7を乗ずることによって求められる。
【００８７】
更に、ブロックＸ7に対応する逆行列Ｄ7が生成される。逆行列Ｄ7は、図２３に示した第１式「Ｄ7＝（Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7）-1」で定義され、同じく第２式「Ｄ7＝Ｃ7-1」によって導かれる。
【００８８】
そして、ブロックＸ6に対応する第２総積Ｃ**6及び逆行列Ｄ6は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。
【００８９】
図２４は、図２２に示した状態に引き続き、７番目の第１総積Ｃ7を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図２５に示す。
【００９０】
まず、変更ブロックに相当すると看做されるブロックＸ7が特定される。そして、ブロックＸ7に対応する第２総積Ｃ**7を、第１総積Ｃ[7]にコピーする。
【００９１】
次に、更新された第１総積Ｃ[7]に基づいて、次のブロックＸ8に対応する第２総積Ｃ**8を生成する。そのため、８番目のブロックＸ8から第１ハッシュ値Ｈ8が算出される。更に、第１ハッシュ値Ｈ8は第１ハッシュ行列Ａ8に変換される。
【００９２】
そして、ブロックＸ8に対応する第２総積Ｃ**8が算出される。第２総積Ｃ**8は、図２５に示した第１式「Ｃ**8＝Ａ1Ａ2Ａ*3Ａ4Ａ5Ａ*6Ａ7Ａ8」で定義され、同じく第２式「Ｃ**8＝Ｃ[7]Ａ8」によって導かれる。つまり、第２総積Ｃ**8は、７番目の更新された第２総積Ｃ[7]に第１ハッシュ行列Ａ8を乗ずることによって求められる。
【００９３】
更に、ブロックＸ8に対応する逆行列Ｄ8が生成される。逆行列Ｄ8は、図２５に示した第１式「Ｄ8＝（Ａ1Ａ2Ａ3Ａ4Ａ5Ａ6Ａ7Ａ8）-1」で定義され、同じく第２式「Ｄ8＝Ｃ8-1」によって導かれる。
【００９４】
そして、ブロックＸ7に対応する第２総積Ｃ**7及び逆行列Ｄ7は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。
【００９５】
次に、変更ブロックが連続している状態で第１総積を修正する場合について説明する。図２６は、２番目、３番目及び６番目のブロックが変更された状態で、２番目の第１総積Ｃ2を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図２７に示す。
【００９６】
まず、既に変更されたブロックのうち先頭のブロックを特定する。この例では、変更ブロックＸ*2が特定される。
【００９７】
そして、変更ブロックＸ*2に対応する第２総積Ｃ*2を、変更ブロックＸ*2に対応する第１総積Ｃ[2]にコピーする。この例では、更新された第１総積の番号に鍵括弧を付する。
【００９８】
次に、更新された第１総積Ｃ[2]に基づいて、変更ブロックＸ*2の次の変更ブロックＸ*3に対応する第２総積Ｃ3を改める。
【００９９】
そのため、３番目の変更ブロックＸ*3から第１ハッシュ値Ｈ＊3が算出される。更に、第１ハッシュ値Ｈ*3は第１ハッシュ行列Ａ*3に変換される。
【０１００】
そして、変更ブロックＸ*3に対応する第２総積Ｃ**3が算出される。第２総積Ｃ**3は、図２７に示した第１式「Ｃ**3＝Ａ1Ａ*2Ａ*3」で定義され、同じく第２式「Ｃ**3＝Ｃ[2]Ａ*3」によって導かれる。つまり、第２総積Ｃ**3は、２番目の更新された第２総積Ｃ[2]に第１ハッシュ行列Ａ*3を乗ずることによって求められる。
【０１０１】
更に、ブロックＸ3に対応する逆行列Ｄ3が生成される。逆行列Ｄ3は、図２７に示した第１式「Ｄ3＝（Ａ1Ａ2Ａ3）-1」で定義され、同じく第２式「Ｄ3＝Ｃ3-1」によって導かれる。
【０１０２】
そして、変更ブロックＸ*2に対応する第２総積Ｃ*2及び逆行列Ｄ2は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。
【０１０３】
図２８は、図２６に示した状態に引き続き、３番目の第１総積Ｃ3を修正する過程を示している。この修正過程に関連する行列の第１式及び第２式を図２９に示す。
【０１０４】
まず、変更ブロックＸ*3が特定される。そして、変更ブロックＸ*3に対応する第２総積Ｃ**3を、第１総積Ｃ[3]にコピーする。
【０１０５】
次に、更新された第１総積Ｃ[3]に基づいて、次のブロックＸ4に対応する第２総積Ｃ**4を生成する。そのため、４番目のブロックＸ4から第１ハッシュ値Ｈ4が算出される。更に、第１ハッシュ値Ｈ4は第１ハッシュ行列Ａ4に変換される。
【０１０６】
そして、ブロックＸ4に対応する第２総積Ｃ**4が算出される。第２総積Ｃ**4は、図２９に示した第１式「Ｃ**4＝Ａ1Ａ*2Ａ*3Ａ4」で定義され、同じく第２式「Ｃ**4＝Ｃ[3]Ａ*4」によって導かれる。つまり、第２総積Ｃ**4は、３番目の更新された第２総積Ｃ[3]に第１ハッシュ行列Ａ4を乗ずることによって求められる。
【０１０７】
更に、ブロックＸ4に対応する逆行列Ｄ4が生成される。逆行列Ｄ4は、図２９に示した第１式「Ｄ4=(Ａ1Ａ2Ａ3Ａ4)-1」で定義され、同じく第２式「Ｄ4＝Ｃ4-1」によって導かれる。
【０１０８】
そして、ブロックＸ3に対応する第２総積Ｃ**3及び逆行列Ｄ3は削除される。この状態で第２ハッシュ値Ｈtを求める処理についての説明は省く。以上で、本実施の形態に係る処理概要の説明を終える。
【０１０９】
図３０に、ハッシュ生成装置のモジュール構成例を示す。ハッシュ生成装置は、ブロック格納部３００１、総数記憶部３００３、第１ハッシュ値記憶部３００５、第１ハッシュ行列記憶部３００７、第１総積格納部３００９、第２総積格納部３０１１、逆行列格納部３０１３、第２ハッシュ行列記憶部３０１５、第２ハッシュ値記憶部３０１７、更新リスト記憶部３０１９及び算出式記憶部３０２１を有する。
【０１１０】
以下、変数記号は省く。ブロック格納部３００１は、各ブロックを格納する。総数記憶部３００３は、ブロック数を記憶する。第１ハッシュ値記憶部３００５は、各ブロックに基づく第１ハッシュ値を記憶する。第１ハッシュ行列記憶部３００７は、第１ハッシュ値に基づく第１ハッシュ行列を記憶する。第１総積格納部３００９は、各ブロックに対応する第１総積を格納する。第２総積格納部３０１１は、変更ブロックに対応する第２総積を格納する。逆行列格納部３０１３は、変更ブロックに対応する第１総積の逆行列を格納する。第２ハッシュ行列記憶部３０１５は、第２ハッシュ行列を記憶する。第２ハッシュ値記憶部３０１７は、第２ハッシュ値を記憶する。更新リスト記憶部３０１９は、変更ブロックの番号及び変更ブロックに看做されるブロックの番号が設定された更新リストを記憶する。以下、変更ブロック及び変更ブロックに看做されるブロックを、更新ブロックといい、変更ブロックの番号及び変更ブロックに看做されるブロックの番号を、更新ブロックの番号という。算出式記憶部３０２１は、算出式に含まれる項に相当する行列を、掛け合わせる順に記憶する。
【０１１１】
上述したブロック格納部３００１、総数記憶部３００３、第１ハッシュ値記憶部３００５、第１ハッシュ行列記憶部３００７、第１総積格納部３００９、第２総積格納部３０１１、逆行列格納部３０１３、第２ハッシュ行列記憶部３０１５、第２ハッシュ値記憶部３０１７、更新リスト記憶部３０１９及び算出式記憶部３０２１は、ハードウエア資源（例えば、図４３）を用いて実現される。
【０１１２】
ハッシュ生成装置は、更に、受付部３０３１、分割部３０３３、初期算出部３０３５、変更部３０３９、追加部３０４１、修正部３０４３、第１算出部３０４５及び出力部３０４７を有する。
【０１１３】
受付部３０３１は、初期データ及び各種指示を受け付ける。分割部３０３３は、初期データをブロックに分割する。初期算出部３０３５は、初期処理を実行する。初期処理については、後述する。変更部３０３９は、変更処理を実行する。変更処理については、後述する。追加部３０４１は、追加処理を実行する。追加処理については、後述する。修正部３０４３は、修正処理を実行する。修正処理については、後述する。第１算出部３０４５は、算出処理を実行する。算出処理については、後述する。出力部３０４７は、第２ハッシュ値を出力する。
【０１１４】
上述した受付部３０３１、分割部３０３３、初期算出部３０３５、変更部３０３９、追加部３０４１、修正部３０４３、第１算出部３０４５及び出力部３０４７は、ハードウエア資源（例えば、図４３）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【０１１５】
図３１に、メイン処理フローを示す。受付部３０３１は、初期データを受け付ける（Ｓ３１０１）。初期データは、ハッシュ値を求める対象、つまり元データである。
【０１１６】
分割部３０３３は、初期データを所定長のブロックに分割する（Ｓ３１０３）。例えば、初期データを６４キビバイトのブロックに分割する。分割されたブロックは、ブロック格納部３００１に記憶される。そして、分割部３０３３は、ブロック数を総数記憶部３００３に記憶する（Ｓ３１０５）。
【０１１７】
初期算出部３０３５は、初期処理を実行する（Ｓ３１０７）。初期処理では、初期データに基づく第２ハッシュ値を算出する。
【０１１８】
図３３に、初期算出部３０３５のモジュール構成例を示す。初期算出部３０３５は、第２算出部３３０１、第１変換部３３０３、第３算出部３３０５及び第２変換部３３０７を有する。
【０１１９】
第２算出部３３０１は、各ブロックに基づく第１ハッシュ値を算出する。第１変換部３３０３は、第１ハッシュ値を第１ハッシュ行列に変換する。第３算出部３３０５は、第１総積を算出する。第２変換部３３０７は、第２ハッシュ行列を第２ハッシュ値に変換する。
【０１２０】
上述した第２算出部３３０１、第１変換部３３０３、第３算出部３３０５及び第２変換部３３０７は、ハードウエア資源（例えば、図４３）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【０１２１】
図３４に、初期処理フローを示す。初期算出部３０３５は、順次ブロックを１つ特定する（Ｓ３４０１）。最初は、先頭のブロックＸ1が特定される。その後、次のブロックＸ2から末尾ブロックＸNまで順に特定される。以下では、Ｓ３４０１で特定されたブロックをＸiと記す。ｉは、ブロック番号を表す。
【０１２２】
第２算出部３３０１は、当該ブロックＸiに基づく第１ハッシュ値Ｈiを算出する（Ｓ３４０３）。ハッシュ値を算出する方法は、従来技術による。
【０１２３】
第１変換部３３０３は、第１ハッシュ値Ｈiを第１ハッシュ行列Ａiに変換する（Ｓ３４０５）。例えば、第１ハッシュ値Ｈiを複数の符号に分け、それらの符号の各々を所定の要素に当てはめることによって第１ハッシュ行列Ａiが生成される。
【０１２４】
第３算出部３３０５は、当該第１ハッシュ行列までの第１総積Ｃiを算出する（Ｓ３４０７）。具体的には、Ｓ３４０１で特定したブロックＸiの前のブロックＸi-1に対応する第１総積Ｃi-1に、第１ハッシュ行列Ａiを乗ずることによって、当該第１総積Ｃiが算出される。尚、先頭のブロックＸ1が特定された場合には、第１ハッシュ行列Ａ1がそのまま第１総積Ｃ1となる。そして、第３算出部３３０５は、当該第１総積Ｃiを第１総積格納部３００９に格納する（Ｓ３４０９）。
【０１２５】
初期算出部３０３５は、未特定のブロックがあるか否かを判定する（Ｓ３４１１）。具体的には、既に末尾ブロックＸNまで特定されている場合には、未特定のブロックがないと判定する。未特定のブロックがあると判定した場合には、Ｓ３４０１に示した処理に戻って、上述した処理を繰り返す。
【０１２６】
一方、未特定のブロックがないと判定した場合には、第２変換部３３０７は、第２ハッシュ行列Ｂを特定する（Ｓ３４１３）。具体的には、末尾ブロックに対応する第１総積ＣNが、第２ハッシュ行列Ｂである。第２ハッシュ行列Ｂは、第２ハッシュ行列記憶部３０１５に記憶される。
【０１２７】
第２変換部３３０７は、第２ハッシュ行列Ｂを第２ハッシュ値Ｈtに変換する（Ｓ３４１５）。例えば、第２ハッシュ行列Ｂにおける要素が示す値を符号として連結することによって、第２ハッシュ値Ｈtが生成される。第２ハッシュ値Ｈtは、第２ハッシュ値記憶部３０１７に記憶される。初期処理を終えると、呼び出し元のメイン処理に復帰する。
【０１２８】
図３１の説明に戻る。受付部３０３１は、更新指示を受け付けたか否かを判定する（Ｓ３１０９）。更新指示は、ユーザ操作による指示であってもよいし、他のプログラムからの指示であってもよい。この例では、１ブロックの変更又は１ブロックの追加の指示を受け付けるものとする。
【０１２９】
更新指示を受け付けたと判定した場合には、受付部３０３１は、ブロック変更の指示であるか否かを判定する（Ｓ３１１１）。ブロック変更の指示であると判定した場合には、変更部３０３９は、変更処理を実行する（Ｓ３１１３）。変更処理では、ブロック変更に伴う内部データの更新を行う。
【０１３０】
図３５に、変更部３０３９のモジュール構成例を示す。変更部３０３９は、第４算出部３５０１、第３変換部３５０３、第５算出部３５０５及び第６算出部３５０７を有する。
【０１３１】
第４算出部３５０１は、更新ブロックに基づく第１ハッシュ値を算出する。第３変換部３５０３は、第１ハッシュ値を第１ハッシュ行列に変換する。第５算出部３５０５は、第２総積を算出する。第６算出部３５０７は、第１総積の逆行列を算出する。
【０１３２】
上述した第４算出部３５０１、第３変換部３５０３、第５算出部３５０５及び第６算出部３５０７は、ハードウエア資源（例えば、図４３）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【０１３３】
図３６に、変更処理フローを示す。変更部３０３９は、既存ブロックを変更する（Ｓ３６０１）。ここでは、変更される前の元ブロックをＸMと記し、変更された後の更新ブロックをＸ*Mと記す。
【０１３４】
第４算出部３５０１は、更新ブロックＸ*Mに基づく第１ハッシュ値Ｈ*Mを算出する（Ｓ３６０３）。ハッシュ値を算出する方法は、従来技術による。
【０１３５】
第３変換部３５０３は、第１ハッシュ値Ｈ*Mを第１ハッシュ行列Ａ*Mに変換する（Ｓ３６０５）。例えば、第１ハッシュ値Ｈ*Mを複数の符号に分け、それらの符号の各々を所定の要素に当てはめることによって第１ハッシュ行列Ａ*Mが生成される。
【０１３６】
第５算出部３５０５は、当該第１ハッシュ行列Ａ*Mまでの第２総積Ｃ*Mを算出する（Ｓ３６０７）。第２総積Ｃ*Mは、更新ブロックＸ*Mの直前のブロックＸM-1に基づくハッシュ行列ＡM-1を最後に掛け合わせた第１総積ＣM-1に、当該第１ハッシュ行列Ａ*Mを乗じることによって求められる。そして、第５算出部３５０５は、当該第２総積Ｃ*Mを第２総積格納部３０１１に格納する（Ｓ３６０９）。
【０１３７】
第６算出部３５０７は、元ブロックＸMに基づく元の第１ハッシュ行列ＡMまでの第１総積ＣMの逆行列ＤMを算出する（Ｓ３６１１）。そして、第６算出部３５０７は、当該逆行列ＤMを逆行列格納部３０１３に格納する（Ｓ３６１３）。
【０１３８】
変更部３０３９は、更新リストに更新ブロックの番号Ｍを加える（Ｓ３６１５）。変更処理を終えると、呼び出し元のメイン処理に復帰する。
【０１３９】
図３１の説明に戻る。Ｓ３１１１においてブロック変更の指示ではないと判定した場合には、つまり、ブロック追加の指示である場合には、追加部３０４１は、追加処理を実行する（Ｓ３１１５）。追加処理では、ブロック追加に伴う内部データの更新を行う。
【０１４０】
図３７に、追加部３０４１のモジュール構成例を示す。追加部３０４１は、第７算出部３７０１、第４変換部３７０３及び第８算出部３７０５を有する。
【０１４１】
第７算出部３７０１は、追加される新規ブロックに基づく第１ハッシュ値を算出する。第４変換部３７０３は、第１ハッシュ値を第１ハッシュ行列に変換する。第８算出部３７０５は、第２総積を算出する。
【０１４２】
上述した第７算出部３７０１、第４変換部３７０３及び第８算出部３７０５は、ハードウエア資源（例えば、図４３）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【０１４３】
図３８に、追加処理フローを示す。追加部３０４１は、末尾ブロックＸNの次に、新規ブロックＸN+1を追加する（Ｓ３８０１）。
【０１４４】
第７算出部３７０１は、新規ブロックＸN+1に基づく第１ハッシュ値ＨN+1を算出する（Ｓ３８０３）。ハッシュ値を算出する方法は、従来技術による。
【０１４５】
第４変換部３７０３は、当該第１ハッシュ値ＨN+1を第１ハッシュ行列ＡN+1に変換する（Ｓ３８０５）。
【０１４６】
第８算出部３７０５は、当該第１ハッシュ行列ＡN+1までの第１総積ＣN+1を算出する（Ｓ３８０７）。第１総積ＣN+1は、末尾ブロックＸNに基づくハッシュ行列ＡNを最後に掛け合わせた第１総積ＣNに、当該第１ハッシュ行列ＡN+1を乗じることによって求められる。そして、第８算出部３７０５は、当該第１総積ＣN+1を第１総積格納部３００９に格納する（Ｓ３８０９）。
【０１４７】
追加部３０４１は、ブロック数を更新する（Ｓ３８１１）。具体的には、ブロック数に１が加えられる。追加処理を終えると、呼び出し元のメイン処理に復帰する。
【０１４８】
図３１の説明に戻る。変更処理又は追加処理を終えると、第１算出部３０４５は、算出処理を実行する（Ｓ３１１６）。
【０１４９】
図３９に、算出処理フローを示す。第１算出部３０４５は、更新リストに更新ブロック番号が設定されているか否かを判定する（Ｓ３９０１）。更新リストに更新ブロック番号が設定されていないと判定した場合には、算出処理を終え、呼び出し元のメイン処理に復帰する。
【０１５０】
一方、更新リストに更新ブロック番号が設定されていると判定した場合には、第１算出部３０４５は、更新リストにおいて、小さい順に更新ブロック番号を特定する（Ｓ３９０３）。ここでは、特定された更新ブロック番号をｊと記す。
【０１５１】
第１算出部３０４５は、当該更新ブロック番号ｊに対応する第２総積Ｃ*jを、算出式の項に加える（Ｓ３９０５）。当該項は、算出式記憶部３０２１に記憶される。
【０１５２】
第１算出部３０４５は、当該更新ブロック番号ｊが末尾ブロックの番号Ｎであるか否かを判定する（Ｓ３９０７）。当該更新ブロック番号ｊが末尾ブロックの番号Ｎであると判定した場合には、第１算出部３０４５は、算出式に従って、第２ハッシュ行列Ｂを算出する（Ｓ３９０９）。第２ハッシュ行列Ｂは、第２ハッシュ行列記憶部３０１５に記憶される。
【０１５３】
第１算出部３０４５は、第２ハッシュ行列Ｂを第２ハッシュ値Ｈtに変換する（Ｓ３９１１）。例えば、第２ハッシュ行列Ｂにおける要素が示す値を符号として連結することによって、第２ハッシュ値Ｈtが生成される。第２ハッシュ値Ｈtは、第２ハッシュ値記憶部３０１７に記憶される。そして、算出処理を終え、呼び出し元のメイン処理に復帰する。
【０１５４】
Ｓ３９０７において、Ｓ３９０３で特定した更新ブロック番号ｊが末尾ブロックの番号Ｎではないと判定した場合には、第１算出部３０４５は、当該更新ブロック番号ｊに対応する逆行列Ｄjを、算出式の項に加える（Ｓ３９１３）。
【０１５５】
第１算出部３０４５は、更新リストに未特定の更新ブロック番号があるか否かを判定する（Ｓ３９１５）。更新リストに未特定の更新ブロック番号があると判定した場合には、Ｓ３９０３に示した処理に戻って、上述した処理を繰り返す。
【０１５６】
一方、更新リストに未特定の更新ブロック番号がないと判定した場合には、第１算出部３０４５は、末尾ブロックの番号Ｎに対応する第１総積ＣNを、算出式の項に加える（Ｓ３９１７）。
【０１５７】
第１算出部３０４５は、算出式に従って、第２ハッシュ行列Ｂを算出する（Ｓ３９１９）。第２ハッシュ行列Ｂは、第２ハッシュ行列記憶部３０１５に記憶される。
【０１５８】
第１算出部３０４５は、第２ハッシュ行列Ｂを第２ハッシュ値Ｈtに変換する（Ｓ３９２１）。第２ハッシュ値Ｈtは、第２ハッシュ値記憶部３０１７に記憶される。算出処理を終えると、呼び出し元のメイン処理に復帰する。
【０１５９】
図３１の説明に戻る。Ｓ３１０９において、更新指示を受け付けていないと判定した場合には、受付部３０３１は、修正指示を受け付けたか否かを判定する（Ｓ３１１７）。修正指示は、ユーザ操作による指示であってもよいし、他のプログラムからの指示であってもよい。修正指示を受け付けたと判定した場合には、修正部３０４３は、修正処理を実行する（Ｓ３１１９）。修正処理では、更新ブロックの第１総積を修正する。
【０１６０】
図４０に、修正部３０４３のモジュール構成例を示す。修正部３０４３は、更新部４００１、削除部４００３、第９算出部４００５、第５変換部４００７、第１０算出部４００９及び第１１算出部４０１１を有する。
【０１６１】
更新部４００１は、第１総積を更新する。削除部４００３は、更新リストにおける更新ブロックの番号を削除する。第９算出部４００５は、第１ハッシュ値を算出する。第５変換部４００７は、第１ハッシュ値を第１ハッシュ行列に変換する。第１０算出部４００９は、第２総積を算出する。第１１算出部４０１１は、第１総積の逆行列を算出する。
【０１６２】
上述した更新部４００１、削除部４００３、第９算出部４００５、第５変換部４００７、第１０算出部４００９及び第１１算出部４０１１は、ハードウエア資源（例えば、図４３）と、以下で述べる処理をプロセッサに実行させるプログラムとを用いて実現される。
【０１６３】
図４１に、修正処理フローを示す。修正部３０４３は、更新リストにおける最小の更新ブロック番号を特定する（Ｓ４１０１）。ここでは、特定された更新ブロック番号をｊと記す。
【０１６４】
更新部４００１は、当該更新ブロック番号ｊに対応する第１総積Ｃjを更新する（Ｓ４１０３）。具体的には、当該更新ブロック番号ｊに対応する第２総積Ｃ*jを第１総積にコピーする。ここでは、更新された第１総積を、Ｃ[j]と記す。
【０１６５】
削除部４００３は、当該更新ブロック番号ｊが末尾ブロックの番号Ｎであるか否かを判定する（Ｓ４１０５）。
【０１６６】
当該更新ブロック番号ｊが末尾ブロックの番号Ｎであると判定した場合には、削除部４００３は、更新リストにおける当該更新ブロック番号ｊを削除する（Ｓ４１０７）。そして、修正処理を終え、呼び出し元のメイン処理に復帰する。
【０１６７】
一方、当該更新ブロック番号ｊが末尾ブロックの番号Ｎではないと判定した場合には、第９算出部４００５は、当該更新ブロック番号ｊの次番号ｊ＋１でブロックＸj+1（当該ブロックが変更されている場合には、変更ブロックＸ*j+1）を特定する（Ｓ４１０９）。
【０１６８】
第９算出部４００５は、Ｓ４１０９で特定したブロックＸj+1（又は変更ブロックＸ*j+1）に基づく第１ハッシュ値Ｈj+1（又は第１ハッシュ値Ｈ*j+1）を算出する（Ｓ４１１１）。ハッシュ値を算出する方法は、従来技術による。
【０１６９】
第５変換部４００７は、第１ハッシュ値Ｈj+1（又は第１ハッシュ値Ｈ*j+1）を第１ハッシュ行列Ａj+1（又は第１ハッシュ行列Ａ*j+1）に変換する（Ｓ４１１３）。
【０１７０】
第１０算出部４００９は、当該第１ハッシュ行列Ａj+1（又は第１ハッシュ行列Ａ*j+1）までの第２総積Ｃ*j+1（又は第２総積Ｃ**j+1）を算出する（Ｓ４１１５）。第２総積Ｃ*j+1（又は第２総積Ｃ**j+1）は、Ｓ４１０１で特定した更新ブロック番号ｊに対応する第１総積Ｃ*jに、当該第１ハッシュ行列Ａj+1（又は第１ハッシュ行列Ａ*j+1）を乗じることによって求められる。
【０１７１】
第１０算出部４００９は、算出した第２総積Ｃ*j+1（又は第２総積Ｃ**j+1）を第２総積格納部３０１１に格納する（Ｓ４１１７）。そして、端子Ｃを介して、図４２に示したＳ４２０１の処理に移る。
【０１７２】
第１１算出部４０１１は、Ｓ４１０１で特定した最小の更新ブロック番号ｊの次番号ｊ＋１に対応する元ブロックＸj+1に基づく元の第１ハッシュ行列Ａj+1までの第１総積Ｃj+1の逆行列Ｄj+1を算出する（Ｓ４２０１）。そして、第１１算出部４０１１は、当該逆行列Ｄj+1を逆行列格納部３０１３に格納する（Ｓ４２０３）。
【０１７３】
削除部４００３は、当該最小の更新ブロック番号ｊに対応する第２総積Ｃ*j及び逆行列Ｄjを削除する（Ｓ４２０５）。修正部３０４３は、更新リストにおける更新ブロック番号ｊに１を加える（Ｓ４２０７）。つまり、更新リストにおける最小の更新ブロック番号ｊを更新ブロック番号ｊ+１に変える。
【０１７４】
修正部３０４３は、修正処理を中断するか否かを判定する（Ｓ４２０９）。例えば、最小の更新ブロック番号ｊが、予定の番号に至った時点で中断するようにしてもよい。修正部３０４３が、ハッシュ生成装置の処理負荷に基づいて修正処理を中断するか否かを判定するようにしてもよい。ユーザ操作による中断指示を受け付けた場合に、修正処理を中断するようにしてもよい。他のプログラムからの中断指示を受け付けた場合に、修正処理を中断するようにしてもよい。修正処理を中断すると判定した場合には、修正処理を終え、呼び出し元のメイン処理に復帰する。
【０１７５】
一方、修正処理を中断しないと判定した場合には、端子Ｄを介して、図４１に示したＳ４１０１の処理に戻る。
【０１７６】
図３１の説明に戻る。修正処理を終えると、Ｓ３１０９に示した処理に戻って、上述した処理を繰り返す。
【０１７７】
Ｓ３１１７において修正指示を受け付けていないと判定した場合には、端子Ａを介して、図３２に示したＳ３２０１の処理に移る。受付部３０３１は、出力指示を受け付けたか否かを判定する（Ｓ３２０１）。出力指示は、ユーザ操作による指示であってもよいし、プログラムからの指示であってもよい。
【０１７８】
出力指示を受け付けたと判定した場合には、出力部３０４７は、第２ハッシュ値記憶部３０１７に記憶している第２ハッシュ値Ｈtを出力する（Ｓ３２０３）。そして、端子Ｂを介して、図３１に示したＳ３１０９の処理に戻る。
【０１７９】
一方、出力指示を受け付けていないと判定した場合には、受付部３０３１は、終了指示を受け付けたか否かを判定する（Ｓ３２０５）。終了指示は、ユーザ操作による指示であってもよいし、プログラムからの指示であってもよい。終了指示を受け付けていないと判定した場合には、端子Ｂを介して、図３１に示したＳ３１０９の処理に戻る。一方、終了指示を受け付けたと判定した場合には、メイン処理を終了する。
【０１８０】
尚、図３１のＳ３１１６に示した算出処理を省き、図３２のＳ３２０３の前に算出処理を実行するようにしてもよい。
【０１８１】
以下、計算について補足する。ハッシュ値Ｈiから分割された符号を所定の剰余に変換するようにしてもよい。例えば、分割された符号を６５５２１で除して剰余を求める。６５５２１は、６５５３５以下で最大の素数である。このようにすれば、符号の値を所定のビット幅に適応させることができる。
【０１８２】
逆行列を求める際の除算は、例えば以下のように定義される。法ｍは、素数（例えば、６５５２１）である。ａは、０以上ｍ未満の整数であるものとする。ｂは、１以上のｍ未満の整数であるものとする。この条件で、ａ＝ｂ×ｃとなる整数ｃのうち、０以上且つｍ未満であるものを商とする。
【０１８３】
行列に含まれるすべての要素が０である場合には、当該行列の逆行列が定まらない。従って、ハッシュ行列Ａiを求める際に、ハッシュ値Ｈiから変換された行列に含まれるすべての要素が０である場合には、当該行列に所定の行列（例えば、単位行列）を加えて、ハッシュ行列Ａiを求めるようにしてもよい。
【０１８４】
本実施の形態では、上述したように行列の積を求める。行列の積算において項の順番が異なる式同士は、等価であるとは限らない。従って、上述した積算の式は、項のみならず、項の順番も意義を有する。例えば、ブロックＸiの順番を入れ替えた場合に、ハッシュ値Ｈtは異なるものになる。
【０１８５】
上述した例では、逆行列Ｄを保持する。このようにすれば、算出処理における演算量がより少なくなる。但し、逆行列Ｄを保持しないようにしてもよい。その場合には、逆行列格納部３０１３を設けなくてもよい。そして、変更処理において、図３６に示したＳ３６１１及びＳ３６１３の処理を省いてもよい。修正処理において、図４２に示したＳ４２０１及びＳ４２０３の処理を省いてもよい。同じくＳ４２０５における逆行列Ｄjの削除処理を省いてもよい。また、算出処理において、図３９に示したＳ３９１３で、更新ブロック番号に対応する第１総積Ｃjの逆行列Ｄjを算出するようにしてもよい。このようにすれば、記憶データ量がより少なくて済む。
【０１８６】
本実施の形態によれば、ハッシュ行列及びハッシュ値の再計算に要する演算量をより少なくすることができる。
【０１８７】
また、元データの複数個所が変更された場合であっても、ハッシュ行列及びハッシュ値の再計算に要する演算量をより少なくすることができる。
【０１８８】
また、元データの多くの個所が変更された場合であっても、ハッシュ行列及びハッシュ値の再計算に要する演算量をより少なくすることができる。保持する内部データの量を減らせる面もある。
【０１８９】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上述の機能ブロック構成はプログラムモジュール構成に一致しない場合もある。
【０１９０】
また、上で説明した各記憶領域の構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ、処理の順番を入れ替えることや複数の処理を並列に実行させるようにしても良い。
【０１９１】
なお、上で述べたハッシュ生成装置は、コンピュータ装置であって、図４３に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１９２】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１９３】
本実施の形態に係る情報処理装置は、（Ａ）元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、元データを識別する第１ハッシュ行列を算出する第１算出部と、（Ｂ）元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する第２算出部とを有する。
【０１９４】
このようにすれば、ハッシュデータの再計算に要する演算量をより少なくすることができる。
【０１９５】
変更ブロックが複数である場合に、第２算出部は、前方から順に各変更ブロックについて、当該変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と当該変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列とを順次乗じ、更に末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積を乗じて、第２ハッシュ行列を算出するようにしてもよい。
【０１９６】
このようにすれば、元データの複数個所が変更された場合であっても、ハッシュデータの再計算に要する演算量をより少なくすることができる。
【０１９７】
更に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と変更ブロックに基づく部分ハッシュ行列との積によって、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積を更新し、変更ブロックを特定するブロック番号を繰り下げる修正部を有してもよい。第２算出部は、繰り下げられた前記ブロック番号によって特定されるブロックを変更ブロックとみなすようにしてもよい。
【０１９８】
このようにすれば、元データの多くの個所が変更された場合であっても、ハッシュデータの再計算に要する演算量をより少なくすることができる。保持する内部データの量を減らせる面もある。
【０１９９】
なお、上で述べた情報処理装置の処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納されるようにしてもよい。尚、中間的な処理結果は、一般的にメインメモリ等の記憶装置に一時保管される。
【０２００】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２０１】
（付記１）
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出する第１算出部と、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する第２算出部と
を有する情報処理装置。
【０２０２】
（付記２）
変更ブロックが複数である場合に、前記第２算出部は、前方から順に各変更ブロックについて、当該変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と当該変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列とを順次乗じ、更に前記末尾ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積を乗じて、第２ハッシュ行列を算出する
付記１記載の情報処理装置。
【０２０３】
（付記３）
更に、
前記変更ブロックの直前の前記ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積と前記変更ブロックに基づく前記部分ハッシュ行列との前記積によって、前記変更される前の元ブロックに基づく前記部分ハッシュ行列が最後に掛け合わされた前記総積を更新し、前記変更ブロックを特定するブロック番号を繰り下げる修正部
を有し、
前記第２算出部は、繰り下げられた前記ブロック番号によって特定されるブロックを前記変更ブロックとみなす
付記１又は２記載の情報処理装置。
【０２０４】
（付記４）
更に、
前記第２ハッシュ行列に基づくハッシュ値を出力する出力部
を有する付記１乃至３いずれか１つ記載の情報処理装置。
【０２０５】
（付記５）
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出し、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する
を含み、コンピュータにより実行されるハッシュ生成方法。
【０２０６】
（付記６）
元データから分割された複数のブロックの順に従って、ブロック毎に先頭ブロックに基づく部分ハッシュ行列から当該ブロックに基づく部分ハッシュ行列まで掛け合わせた総積を保存しつつ、末尾ブロックに基づく部分ハッシュ行列まで掛け合わせた、前記元データを識別する第１ハッシュ行列を算出し、
前記元データの一部が変更された場合に、変更ブロックの直前のブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積と前記変更ブロックに基づく部分ハッシュ行列との積と、変更される前の元ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積の逆行列と、末尾ブロックに基づく部分ハッシュ行列が最後に掛け合わされた総積とを乗じて、変更データを識別する第２ハッシュ行列を算出する
処理をコンピュータに実行させるハッシュ生成プログラム。
【符号の説明】
【０２０７】
３００１  ブロック格納部    ３００３  総数記憶部
３００５  第１ハッシュ値記憶部    ３００７  第１ハッシュ行列記憶部
３００９  第１総積格納部    ３０１１  第２総積格納部
３０１３  逆行列格納部    ３０１５  第２ハッシュ行列記憶部
３０１７  第２ハッシュ値記憶部    ３０１９  更新リスト記憶部
３０２１  算出式記憶部    ３０３１  受付部
３０３３  分割部    ３０３５  初期算出部
３０３９  変更部    ３０４１  追加部
３０４３  修正部    ３０４５  第１算出部
３０４７  出力部    ３３０１  第２算出部
３３０３  第１変換部    ３３０５  第３算出部
３３０７  第２変換部    ３５０１  第４算出部
３５０３  第３変換部    ３５０５  第５算出部
３５０７  第６算出部    ３７０１  第７算出部
３７０３  第４変換部    ３７０５  第８算出部
４００１  更新部    ４００３  削除部
４００５  第９算出部    ４００７  第５変換部
４００９  第１０算出部    ４０１１  第１１算出部
【図１】
2017146515.tif 000003
【図２】
2017146515.tif 000004
【図３】
2017146515.tif 000005
【図４】
2017146515.tif 000006
【図５】
2017146515.tif 000007
【図６】
2017146515.tif 000008
【図７】
2017146515.tif 000009
【図８】
2017146515.tif 000010
【図９】
2017146515.tif 000011
【図１０】
2017146515.tif 000012
【図１１】
2017146515.tif 000013
【図１２】
2017146515.tif 000014
【図１３】
2017146515.tif 000015
【図１４】
2017146515.tif 000016
【図１５】
2017146515.tif 000017
【図１６】
2017146515.tif 000018
【図１７】
2017146515.tif 000019
【図１８】
2017146515.tif 000020
【図１９】
2017146515.tif 000021
【図２０】
2017146515.tif 000022
【図２１】
2017146515.tif 000023
【図２２】
2017146515.tif 000024
【図２３】
2017146515.tif 000025
【図２４】
2017146515.tif 000026
【図２５】
2017146515.tif 000027
【図２６】
2017146515.tif 000028
【図２７】
2017146515.tif 000029
【図２８】
2017146515.tif 000030
【図２９】
2017146515.tif 000031
【図３０】
2017146515.tif 000032
【図３１】
2017146515.tif 000033
【図３２】
2017146515.tif 000034
【図３３】
2017146515.tif 000035
【図３４】
2017146515.tif 000036
【図３５】
2017146515.tif 000037
【図３６】
2017146515.tif 000038
【図３７】
2017146515.tif 000039
【図３８】
2017146515.tif 000040
【図３９】
2017146515.tif 000041
【図４０】
2017146515.tif 000042
【図４１】
2017146515.tif 000043
【図４２】
2017146515.tif 000044
【図４３】
2017146515.tif 000045