(57)【要約】  本発明は、認証タグ生成の計算量の増大を抑える。入力したメッセージを該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対して、ハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を演算の単位元として前記各ハッシュ値を結合演算する（図４）。
2018193507.tif 000002
【特許請求の範囲】
【請求項１】
入力したメッセージを該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対して、ハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から前記部分系列の認証タグを生成し、
前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算するハッシュ関数適用部を備えた、ことを特徴とする認証タグ生成装置。
【請求項２】
前記ハッシュ関数適用部は、前記部分系列の終わりのアイテムに対して、当該アイテムのインデックスが前記部分系列の終わりであることを示す情報に前記ハッシュ関数を演算したハッシュ値を生成し、前記コンバイナでの結合演算に供する、ことを特徴とする請求項１に記載の認証タグ生成装置。
【請求項３】
前記ハッシュ関数適用部は、
前記コンバイナで前記各ハッシュ値を結合演算した値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値を、所定のビット幅にカットした値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値に第２のハッシュ関数を演算したハッシュ値を、
前記認証タグとする、ことを特徴とする請求項１又は２に記載の認証タグ生成装置。
【請求項４】
前記ハッシュ関数適用部は、前記アイテムのインデックスと前記アイテムの連結、及び、前記部分系列の終わりのアイテムのインデックスと前記部分系列の終わりであることを示す予約語の連結に対して、それぞれ、前記ハッシュ関数を演算したハッシュ値を、前記コンバイナで結合演算する、ことを特徴とする請求項２に記載の認証タグ生成装置。
【請求項５】
前記ハッシュ関数は、インクリメンタルハッシュ関数である、ことを特徴とする請求項１又は２に記載の認証タグ生成装置。
【請求項６】
検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記グループテスト行列とを入力として受けるデータ入力部と、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する検証用認証タグ生成部と、
前記検証用認証タグ生成部が生成した前記検証用認証タグと、前記データ入力部が入力した前記認証タグとを比較し改ざんがあるか検証する認証タグ検証部と、
前記認証タグ検証部での検証結果を出力する検証結果出力部と、
を備えた、ことを特徴とする認証タグ検証装置。
【請求項７】
前記検証用認証タグ生成部は、前記グループテスト行列にしたがって分割した部分系列の終わりのアイテムに対して、当該アイテムのインデックスが前記部分系列の終わりであることを示す情報に前記ハッシュ関数を演算したハッシュ値を生成し前記コンバイナでの前記結合演算に供する、ことを特徴とする請求項６に記載の認証タグ検証装置。
【請求項８】
前記検証用認証タグ生成部は、前記入力した認証タグに応じて、
前記コンバイナで前記各ハッシュ値を結合演算した値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値を、所定のビット幅にカットした値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値に第２のハッシュ関数を演算したハッシュ値を、
検証用認証タグとする、ことを特徴とする請求項６又は７に記載の認証タグ検証装置。
【請求項９】
前記検証用認証タグ生成部は、前記アイテムのインデックスと前記アイテムの連結、及び、前記部分系列の終わりのアイテムのインデックスと前記部分系列の終わりであることを示す予約語の連結に対して、それぞれ、前記ハッシュ関数を演算したハッシュ値を、前記コンバイナで結合演算する、ことを特徴とする請求項６乃至８のいずれか１項に記載の認証タグ検証装置。
【請求項１０】
前記ハッシュ関数は、インクリメンタルハッシュ関数である、ことを特徴とする請求項６又は７に記載の認証タグ検証装置。
【請求項１１】
コンピュータによる認証タグ生成方法であって、
入力したメッセージを該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対して、ハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から前記部分系列の認証タグを生成し、
前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する、ことを特徴とする認証タグ生成方法。
【請求項１２】
前記グループテスト行列にしたがって分割した部分系列の終わりのアイテムに対して、当該アイテムのインデックスが前記部分系列の終わりであることを示す情報にハッシュ関数を演算したハッシュ値を生成し前記コンバイナでの前記結合演算に供する、ことを特徴とする請求項１１に記載の認証タグ生成方法。
【請求項１３】
前記コンバイナで前記各ハッシュ値を結合演算した値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値を、所定のビット幅にカットした値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値に第２のハッシュ関数を演算したハッシュ値を、
前記認証タグとする、ことを特徴とする請求項１１又は１２に記載の認証タグ生成方法。
【請求項１４】
検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記グループテスト行列とを入力として受け、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の検証用認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算し、
前記検証用認証タグと、入力した前記認証タグとを比較して改ざんがあるか検証し、
前記検証の結果を出力する、ことを特徴とする認証タグ検証方法。
【請求項１５】
前記グループテスト行列にしたがって分割した部分系列の終わりのアイテムに対して、当該アイテムのインデックスが前記部分系列の終わりであることを示す値にハッシュ関数を演算したハッシュ値を生成し前記コンバイナでの前記結合演算に供する、ことを特徴とする請求項１４に記載の認証タグ検証方法。
【請求項１６】
前記入力した認証タグに応じて、
前記コンバイナで前記各ハッシュ値を結合演算した値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値を、所定のビット幅にカットした値、又は、
前記コンバイナで前記各ハッシュ値を結合演算した値に第２のハッシュ関数を演算したハッシュ値を、
前記検証用認証タグとする、ことを特徴とする請求項１４又は１５に記載の認証タグ検証方法。
【請求項１７】
入力したメッセージを、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し各ハッシュ値を結合演算した値から前記部分系列の認証タグを生成し、その際、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する処理を、コンピュータに実行させるプログラム。
【請求項１８】
検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記グループテスト行列とを入力として受ける処理と、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値を結合演算した値から前記部分系列の検証用認証タグを生成し、その際、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する処理と、
前記検証用認証タグと、入力した前記認証タグとを比較して改ざんがあるか検証する処理と、
前記検証の結果を出力する処理と、
を、コンピュータに実行させるプログラム。
【請求項１９】
前記グループテスト行列にしたがって分割した部分系列の終わりのアイテムに対して、当該アイテムのインデックスが前記部分系列の終わりであることを示す値にハッシュ関数を演算したハッシュ値を生成し前記結合演算に供する処理を、前記コンピュータに実行させる請求項１７又は１８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証タグ生成装置、認証タグ検証装置、方法及びプログラムに関する。
【背景技術】
【０００２】
任意のメッセージの入力に対して固定長の短いハッシュ値を出力するハッシュ関数がある。ハッシュ関数の暗号学的な安全性としては、衝突困難性（Collision-Resistance：CR）が挙げられる。これは、ハッシュ関数Hについて任意の異なる２つの入力x、x'に対して、H(x)=H(x’)を見つける、すなわち出力の衝突を起こすものを見つけることが困難であることを指す。例えば、認証タグ生成装置が、保護する対象のデータＤについて衝突困難性を有するハッシュ関数H()のハッシュ値T=H(D)をデータ認証用のタグである認証タグとして保持しておく。後に、データDがデータD’に改ざんされた場合に、検証装置で、T’=H(D’)と元のハッシュ値Ｔとを比較することで、安全に改ざんを検出することができる。例えばSHA(Secure Hash Algorithm）-2等の一般的な暗号学的ハッシュ関数は、衝突困難性を有するものとみなされており、上記のような改ざんの検出用途等に用いられている。【０００３】
ハッシュ関数H()を用いた改ざんの検出技術に関連して、例えば、非特許文献１〜３等に開示された技術が知られている。非特許文献１〜３には、組み合わせグループテスト（Combinatorial Group Testing： CGT）と呼ばれる組み合わせ問題を利用した、メッセージの改ざん検出技術の一例が開示されている。また非特許文献４には、符号理論を用いてグループテストの適切なテスト数およびテスト毎のアイテムを決定する手法が記載されている。【０００４】
一般に、メッセージの全体に対して１回のハッシュ関数を適用して１つの認証タグを生成する方法（「one-tag法」とも称する）の場合、メッセージ中の改ざん位置の情報を得るのは不可能である。これは、改ざんが行われた場合、ハッシュ値は正しい値とは全く異なるランダムな値となるからである。この問題に対して、例えば、メッセージの全体に１回のハッシュ関数を適用するのではなく、メッセージを任意の部分に分割し、それらの部分ごとにハッシュ関数を適用する方法がある。【０００５】
この方法によれば、部分ごとのチェックが可能となる。すなわち、メッセージに対する改ざん位置を、分割後の部分の範囲内に特定することが可能になる。例えば、メッセージＭがｍ個のアイテムM[1],…,M[m]からなる場合に、各アイテムに対してハッシュ関数を適用して、認証タグT[1]=H(M[1]),…, T[m]=H(M[m])を求める例が挙げられる。求めたm個の認証タグ（T[1],…,T[m]）は、例えば改ざんの危険のない場所に保持されればよい。なお、アイテムは「ブロック」とも称される。【０００６】
改ざんを検出したい最小単位であるアイテムの各々に対して、ハッシュ関数を適用して認証タグを生成する方法を「each-tag法」と称する場合がある。メッセージの分割例として、例えばハードディスク上のデータに対しファイルごとやディスクセクタごとに分けることが挙げられる。しかし、each-tag法はm個のアイテムに対してm個の認証タグが生成されることから、保存すべきデータ量の増加が大きいという問題がある。【０００７】
そこで、非特許文献１や非特許文献２に開示されているように、CGTを利用して、メッセージを、互いに重なりを許す複数の部分系列に分解し、この部分系列ごとにハッシュ関数を適用するという手法が用いられる場合がある。例えば、メッセージM=(M[1],…,M[7])のように、メッセージMが７個のアイテムからなるとき、該メッセージMを３つの部分系列S[1],…,S[3]に分解する。【０００８】
S[1] = (M[1], M[2], M[3], M[4]),
S[2] = (M[1], M[2], M[5], M[6]),
S[3] = (M[1], M[3], M[5], M[7])        
…(1)【０００９】
そして、各部分系列に対してハッシュ関数H()を適用して、以下の３つの認証タグT[1]-T[3]を計算したとする。【００１０】
T[1] = H(S[1]),
T[2] = H(S[2]),
T[3] = H(S[3])
…(2)【００１１】
この場合、each-tag法において、m個（7個）必要であった認証タグの数を、T[1]-T[3]の3個に減らすことが可能となる。なお、改ざん位置は、各(T[i], S[i])に対する検証結果から、CGT理論に基づき、特定ないし限定される。以下、部分系列を例示する際に、上記の部分系列S[1],…,S[3]のことを「第１の分解例」とも称する。【００１２】
CGTでは、部分系列の取り方を工夫することにより、改ざんされたアイテム数が所与のしきい値以下のときには、改ざんされたアイテムまで特定することが可能となる。どのような部分系列に分解し、またその結果どのような改ざんアイテムの特定が可能になるかは、例えば非特許文献１に開示されているように、組み合わせ問題（CGT）と密接に関連する。非特許文献１には、特定の分布を持つ乱数を用いてCGT行列を生成する方法が記載されている。非特許文献２には、巡回行列を用いてCGT行列を生成する方法が記載されている。非特許文献３には、より明示的にCGTとハッシュ関数を用いた方法が開示されている。非特許文献４には、テストの数sがO(d2log2(m))を達成するように、符号理論を用いてグループテスト行列を生成する手法が開示されている。【００１３】
グループテスト行列（「CGT行列」ともいう）は、グループテストに用いるテスト毎の部分系列（アイテムの組合せ）を表す（represent）２値行列である。例えば、r個のアイテムおよびs個のテストからなるCGTでは、s行r列の２値行列であるCGT行列Ｗを生成し、生成したCGT行列Ｗに従ってテストを行う。CGT行列Ｗのi行のj列目の要素の値が「１」である場合、j番目のテストにおけるi番目のアイテムをテストに含める、といったことが示されればよい。以下、非特許文献１〜３に記載されているような、CGTを利用して各グループテスト毎にハッシュ関数を適用する方法を「単純CGT-tag法」と称する場合がある。【００１４】
ところで、データベースシステム等に記憶されているデータ群に対して、認証タグを用いて改ざんの検出を行うことを考えた場合、現実的なシステムの制約などから、不正者が一度に大量のアイテム（ファイルやディスクセクタ）を改ざんすることは考えにくい。CGTを利用してテスト毎（より具体的には、部分系列毎）に認証タグを生成する単純CGT-tag法は、認証タグの総数を抑えつつ、現実的に起こりうる改ざんに対し、その場所を特定可能なデータベースシステムを構築することができる。なお、各アイテムにハッシュ関数を適用した場合と同様、CGTの各テストにハッシュ関数を適用した場合であっても、任意の改ざんに対して、改ざんがあったという事実を検出可能という性質は変わらない。【００１５】
非特許文献１には、認証タグとして、鍵付きのハッシュ関数の出力値であるメッセージ認証コード（Message Authentication Code：MAC)を用いる例が開示されている。非特許文献２には、鍵のないハッシュ関数の出力値であるハッシュ値を用いる例が開示されている。鍵のないハッシュ関数の場合、タグ計算を誰でも行うことができるため、求めたタグ（ハッシュ値）をメッセージと別の安全な場所に保存する必要が一般に生じるが、得られる効果（改ざん検出効果）としては、鍵付きであっても鍵なしであっても基本的に変わらない。非特許文献１〜３に開示されているような単純CGT-tag法を用いれば、each法と比べて認証タグの総数を抑えつつ、改ざんの有無に加えて改ざん位置の特定ないし限定が可能である。【００１６】
しかしながら、単純にCGTを利用してテスト毎に認証タグを生成する方法（単純CGT-tag法）は、one-tag法に比べて計算量が大幅に増加する、という問題がある。【００１７】
グループテスト行列（CGT行列）において、「１」が立つ要素（成分）に対応するアイテムを取り出して連結（concatenate：連接ともいう）する例について説明する。この方法では、テストのインデックスi=1,…, s、アイテムのインデックスj=1,…,mとして、各iについて、CGT行列Ｗのｉ行目で値が１である列ｊを見つけ、見つかった全てのｊについて、それぞれ対応するアイテムM[j]を第１のハッシュ関数H()に与えた出力を計算する。そして、得られた全ての出力を連結した上で、第２のハッシュ関数H’()に入力する。このようにして得られた出力を、当該ｉ番目のテストに対応する認証タグT[i]とする。これを全てのｉについて行い、認証タグリストTL=(T[1],…,T[s])を得る。【００１８】
図１は、第１の分解例に対するハッシュ適用例を示す説明図である（図１は、特許文献１に「愚直な手法」として説明されている）。図１に示す内容を、簡易な式で表すと次の通りとなる。【００１９】
・ｉ＝１
［第１のハッシュ関数適用処理］
Z[i] = H(M[1]) || H(M[2]) || H(M[3]) || H(M[4])
…(3)
［第２のハッシュ関数適用処理］
T[i] = H’(Z[i])
…(4)【００２０】
・ｉ＝２
［第の１ハッシュ関数適用処理］
Z[i] = H(M[1]) || H(M[2]) || H(M[5]) || H(M[6])
…(5)
［第２のハッシュ関数適用処理］
T[i] = H’(Z[i])
…(6)【００２１】
・ｉ＝３
［第１のハッシュ関数適用処理］
Z[i] = H(M[1]) || H(M[3]) || H(M[5]) || H(M[7])
…(7)
［第２のハッシュ関数適用処理］
T[i]=H’(Z[i])
…(8)【００２２】
これにより、認証タグリスト
TL = (T[1], T[2], T[3])
…(9)
を得る。【００２３】
この手法では、認証タグリストTLを得るための第１のハッシュ関数H()の呼び出し回数は、約（アイテム数m）×（テスト数s）＝ms回必要となる（図１の破線内を参照のこと）。【００２４】
特許文献１には、認証タグリストTLを得るための第１のハッシュ関数H()の呼び出し回数がアイテム数mと同じ回数で済むようにした構成が開示されている。特許文献１の開示において、２層ハッシュ木適用手段は、改ざん検出の対象とされるメッセージを、M = (M[1],…,M[m])、（ただし、mはアイテム数）とし、組み合わせグループテストの数をｓとした場合、s個の初期化済みの状態変数:Z[1],…,Z[s]を用意し、j=1,…,mについて、j番目のアイテムM[j]を第１のハッシュ関数H()に適用し、中間ハッシュ値H(M[j])を得て、当該アイテムを使用するテストｉ（ただし、i=1,…,s）がある場合に、状態変数Z[i]に、前記中間ハッシュ値H(M[j])を連結する処理を、前記jの全てに対して行い、最終的に得られた状態変数Z[1],…,Z[s]の各々に対して第２のハッシュ関数H’（）に適用してs個の認証タグを生成する。【００２５】
第１のハッシュ関数H()および第２のハッシュ関数H’()には、AES(Advanced Encryption Standard)など標準的なブロック暗号に用いられる関数やSHA(Secure Hash Algorithm)-2などのハッシュ関数を用いてもよい。また、第１のハッシュ関数H()と第２のハッシュ関数H’()とは単一の関数に異なる定数（０と１など）を入力アイテムに含む（連結する）よう構成されたものであってもよい。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】特開２０１７−５４０９号公報
【特許文献２】国際公開第２０１６／０６３５１２号
【非特許文献】
【００２７】
【非特許文献１】Michael T. Goodrich, Mikhail J. Atallah, Roberto Tamassia, "Indexing Information for Data Forensics", Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005,p.206-221.
【非特許文献２】Giovanni Di Crescenzo, Shaoquan Jiang, Reihaneh Safavi-Naini, "Corruption-Localizing Hashing", Computer Security - ESORICS 2009, 14th European Symposium on Research in Computer Security, Saint-malo, France, September 21-23,2009. p.489-504.
【非特許文献３】Annalisa De Bonis, Giovanni Di Crescenzo, "Combinatorial Group Testing for Corruption Localizing Hashing", COCOON 2011, p.579-591.
【非特許文献４】Ely Porat, AＭir Rothschild, "Explicit Non-Adaptive Combinatorial Group Testing Schemes", ICALP 2008.
【非特許文献５】MIHIR BELLARE, DANIELE MICCIANCIO, "A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost", Advances in Cryptology - Eurocrypt 1997, volume 1233 of Lecture Notes in Computer Science, pages 163--192. Springer-Verlag, 11--15 May 1997.
【発明の概要】
【発明が解決しようとする課題】
【００２８】
以下に、関連技術の分析を与える。【００２９】
特許文献１等に開示された２層の木ハッシュの適用例は計算量が多い。一般的なハッシュ関数は入力長に対して線形オーダの計算量を持つ。例えば図２に示すように、
Z[i]=H(M[1])||H(M[2])||…||H(M[a])
T[i]=H’(Z[i])
…(10)
において、第２のハッシュ関数H'()の入力Z[i]の長さはアイテム数aに依存する。アイテム数がaのメッセージMに対して、任意の１アイテムの改ざんを特定可能にするCGTにおいて、第２のハッシュ関数H’()の入力Z[i]はＯ（a）である。【００３０】
本発明は、上記課題に鑑みて創案されたものであって、その目的は、計算量の増大を抑えることを可能とする認証タグ生成装置、認証タグ検証装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００３１】
本発明の１つの形態によれば、入力したメッセージを該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対して、ハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を演算の単位元として、前記各ハッシュ値を結合演算するハッシュ関数適用部を備えた認証タグ生成装置が提供される。【００３２】
本発明の他の１つの形態によれば、検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記グループテスト行列とを入力として受けるデータ入力部と、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する検証用認証タグ生成部と、
前記検証用認証タグ生成部が生成した前記検証用認証タグと、前記データ入力部が入力した前記認証タグとを比較し改ざんがあるか検証する認証タグ検証部と、
前記認証タグ検証部での検証の結果を出力する検証結果出力部とを備えた認証タグ検証装置が提供される。【００３３】
本発明の他の１つの形態によれば、コンピュータによる認証タグ生成方法であって、
入力したメッセージを該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対して、ハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から前記部分系列の認証タグを生成し、
前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する認証タグ生成方法が提供される。【００３４】
本発明の他の１つの形態によれば、検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記組グループテスト行列とを入力として受け、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値をコンバイナで結合演算した値から、前記部分系列の検証用認証タグを生成し、前記コンバイナでは、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算し、
前記検証用認証タグと、入力した前記認証タグとを比較して改ざんがあるか検証し、
前記検証の結果を出力する認証タグ検証方法が提供される。【００３５】
本発明の他の１つの形態によれば、入力したメッセージを、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し各ハッシュ値を結合演算した値から前記部分系列の認証タグを生成し、その際、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する処理を、コンピュータに実行させるプログラムが提供される。【００３６】
本発明の他の１つの形態によれば、検証対象のメッセージと、該メッセージに関する組み合わせグループテストを表すグループテスト行列にしたがって前記メッセージを分割した各部分系列に対応する認証タグと、前記グループテスト行列とを入力として受ける処理と、
前記グループテスト行列にしたがって分割した部分系列の各アイテムに対してハッシュ関数を演算し、各ハッシュ値を結合演算した値から前記部分系列の検証用認証タグを生成し、その際、空系列のアイテムのハッシュ値を単位元とする演算により前記各ハッシュ値を結合演算する処理と、
前記検証用認証タグと、入力した前記認証タグとを比較して改ざんがあるか検証する処理と、
前記検証の結果を出力する処理と、
を、コンピュータに実行させるプログラムが提供される。【００３７】
本発明のさらに他の形態によれば、上記形態のプログラムを記憶したコンピュータ読み出し可能な記録媒体（例えばRAM(Random Access Memory）、ROM(Read Only Memory）、又は、EEPROM(Electrically Erasable and Programmable ROM））等の半導体ストレージ、HDD(Hard Disk Drive)、CD(Compact Disc）、DVD(Digital Versatile Disc）等のnon-transitory computer readable recording mediumが提供される。
【発明の効果】
【００３８】
本発明の形態によれば、計算量の増大を抑えることを可能とする認証タグ生成装置、方法、プログラムを提供することができる。
【図面の簡単な説明】
【００３９】
【図１】関連技術を説明する図である。
【図２】関連技術を説明する図である。
【図３】本発明の一形態を説明するための図である。
【図４】本発明の一形態を説明するための図である。
【図５】本発明の例示的な第１の実施形態を例示する図である。
【図６】本発明の例示的な第１の実施形態を動作を説明するための流れ図である。
【図７】（Ａ）乃至（Ｃ）は本発明の例示的な第１の実施形態を説明するための図である。
【図８】（Ａ）乃至（Ｃ）は本発明の例示的な第１の実施形態（比較例）を説明するための図である。
【図９】本発明の例示的な第１の実施形態を説明するための図である。
【図１０】本発明の例示的な第１の実施形態の変形例を説明するための図である。
【図１１】本発明の例示的な第１の実施形態の変形例を説明するための図である。
【図１２】本発明の例示的な第２の実施形態を説明するための図である。
【図１３】本発明の例示的な第２の実施形態の動作を説明するための流れ図である。
【図１４】本発明の例示的な第３の実施形態を説明するための図である。
【図１５】本発明の例示的な第４の実施形態を説明するための図である。
【発明を実施するための形態】
【００４０】
本発明の実施形態について説明する。はじめに、基本概念を説明する。図３は、本発明の一形態を説明する図である。入力メッセージをブロックに分けて個別にハッシュ関数H（）を適用する。ハッシュ関数H（）は、例えばSHA-2等であってもよい。
【００４１】
メッセージXがｎ個の連接するブロック(アイテム)x[1],…,x[n]からなる場合に（X=x[1],…,x[n]）、各x[i] (i=1,…,n)に対して、それぞれブロックインデクス（アイテムインデックス）i=1,…,nを連結（concatenate）した拡張ブロック（augmented block）：
<i>. x[i]
…(11)
にハッシュ関数H()を適用する。
y[i]=H(<i>.x[i])    （i=1,…,n）
…(12)
【００４２】
n個のハッシュ値y[i]（i=1,…,n）を次式に示すように、結合演算(combining operation）する。
【００４３】
2018193507.tif 000003
…(13)
【００４４】
ハッシュ値y[1],…,y[n]は、演算
2018193507.tif 000004
に関する群Ｇの要素（元）を構成してもよい。
【００４５】
Ｇに属する任意の２つの元ａ、bは2項演算に関して閉じている。すなわち、∀a,b∈Gに対して、
2018193507.tif 000005
…(14-1)
はGに含まれる。
【００４６】
群Gの３つの元ａ、b、cに関して結合則
2018193507.tif 000006
…(14-2)
が成り立つ。式(14-1)、(14-2)を満たすとき、Gは2項演算
2018193507.tif 000007
に関して半群をなすという。
【００４７】
群Ｇに単位元eが含まれ、
2018193507.tif 000008
…(14-3)
が成り立つ。式(14-1)〜(14-３)を満たす場合、Gは演算
2018193507.tif 000009
に関してモノイドをなすという。
【００４８】
群Ｇに属する全ての元aに対して逆元a-1が存在し、
2018193507.tif 000010
…(14-4)
が成り立つ。式(14-1)乃至(14-4)を満たす場合、Gは2項演算
2018193507.tif 000011
に関して群をなすという。
【００４９】
コンバイナ（combiner）は、演算
2018193507.tif 000012
を介して群Gの元のハッシュ値を結合する。
【００５０】
ハッシュ関数H()がインクリメンタルハッシュ関数であるとき、X＝x[1],…,x[n]に対して、ハッシュ値HASH(X)が計算済みであり、ブロックx[i]をx'[i] (i=1,…,n）に変えた場合、新たなハッシュ値は次式(15)で与えられる。式(15)は、インクリメンタリティ（incrementality）を表す。
2018193507.tif 000013
…(15)
【００５１】
なお、非特許文献５では、ハッシュ関数HASH（）は、理想的（ideal）、すなわちランダムオラクルであることを想定している。
【００５２】
コンバイナでの結合演算（combining operation）の例として、例えばMuHASHは以下で与えられる。  
MuHASHG,H (x[1],…,x[n]) = Π<i=1,n>H(<i>.x[i])
…(16)
【００５３】
位数が素数pの群における剰余（modulo）pでの整数乗算である。すなわち、ブロックをHでランダマイズしてZp*＝Zp-{0}={1,2,…,p-1}を得、これらを剰余（modulo）pでの整数乗算する。MuHASHの衝突攻撃に対する安全性は、例えば群Gにおける離散対数問題（discrete log problem）の困難性に帰着可能であることが知られている。
【００５４】
AdHasHは、kビット整数Mの剰余（mod M）の加算演算であり、以下で与えられる。
AdHASHM,H(x[1],…,x[n])=Σ<i=1,n> H(<i>.xi) mod M
…(17)
【００５５】
AdHASHの安全性は、ビットの整数Mと、q個の数0<a[1],…,a[q]<Mが与えられており、値が｛-1,0,+1｝のいずれかであり、全てが0とはならないq個の重みw=(w[1],…,w[q])が
Σ<i=1,ｑ>w[i]a[i]=0  （mod M） 
…(18)
を見つける(k-q)-重みナップザック問題に帰着することが知られている。重みナッププザック問題が困難である限り、ハッシュ関数はコリジョンフリー（collision-free）である。
【００５６】
また、群Gの演算に関して、
2018193507.tif 000014
…(19)
となるw=(w[1],…,w[q]), (w[i] (i=1,…,q)∈｛-1,0,+1｝)
を見つける問題に帰着することが知られている。
【００５７】
これは、群Gの要素a[1],…,a[n]が与えられたとき、
2018193507.tif 000015
…(20)
をみたす交わりを持たない部分集合(disjoint subsets)
2018193507.tif 000016
…(21)
を見つけるバランス問題に帰着する。
【００５８】
LtHASHはベクトル加算、AdHASHの剰余Mを素数pとして出力をZpｋとしたものである。
LtHASHｐ,h(x1,…,xn)=Σi h(<i>.xi) mod p
…(22)
【００５９】
図４は、前述したメッセージM=(M[1],…,M[7])のように、メッセージが７個のアイテムからなるときの、部分系列S[1] = (M[1], M[2], M[3], M[4])のハッシュ値の演算を説明する図である。(i,M[i])は、アイテムインデックスiとアイテムM[i]を連結(concatenate)したもの（拡張ブロックに対応して「拡張アイテム」（augmented item）と称してもよい）を表しており、図３の表記に従えば、
<i>.M[i]
…(23)
となる。
【００６０】
コンバイナの出力は例えば、MuHASHによれば、
Y= Π<i=1,4>H(i, M[i])
…(24)
となる。
【００６１】
図４において、(2、es) として示すように、グループテスト行列にしたがって分割された部分系列のうちテストに用いられないアイテムM[2]（空のアイテム）に対して、長さ0の空系列 es（empty string）を導入している。すなわち、ブロックの空間を群Gから
G’= G ∪ {es} 
… (25)
に拡張している。なお、群G’上で演算の衝突困難性を安全性要件とする。
【００６２】
空系列に関して、（x[1])と、(x[1], es)とは別の要素である。
【００６３】
また、(es, es)と(es)も別の要素である。
【００６４】
コンバイナによるハッシュ値の結合演算では、部分系列におけるアイテムのインデクスiによらず、（i,es）のハッシュ値を、群G'の単位元として扱う。
【００６５】
H（i,es）=e                                … (26)
【００６６】
MUHASHでは、単位元はe=1, 
AdHashでは、単位元はe=0, 
LtHASHでは、単位元はe=(0,..,0)
となる。
【００６７】
また図４を参照すると、部分系列がnアイテムで終わるとき、（n, end）のハッシュ値H（n, end）をコンバイナ（combiner）に入力するようにしている。ここで、「end」はesや非esとも異なる予め定められた予約語（reserved word）とする。（n, end）は、アイテムインデクスnと予約語endの連結したものである。
【００６８】
＜実施形態１＞
図５は、本発明の例示的な第１の実施形態を説明する図である。図５には、認証タグ生成装置１００の構成の一例が模式的に例示されている。図５を参照すると、認証タグ生成装置１００は、メッセージ入力部１０１と、グループテスト生成部１０２と、ハッシュ関数適用部１０３と、認証タグ出力部１０４と備えている。
【００６９】
メッセージ入力部１０１は、対象となるメッセージＭを入力するハードウェアインタフェース、ソフトウェアを備えた構成としてもよい。特に制限されないが、メッセージ入力部１０１は、例えばキーボード等の文字入力装置、ハードディスクドライブ装置（HDD）、ソリッドステートドライブ（solid state drive, SSD）からデータ、ファイルを読み出すディスクインタフェース（コントローラ／ドライバ）や、宛先ノードへ伝送する通信メッセージをメモリデバイスやネットワークインタフェース等から入力する装置を含む構成としてもよい。
【００７０】
ここで、メッセージMはm(>1)個の個別のアイテムM[1],…,M[m]により構成されているものとする。なお、それぞれのアイテムは長さが互いに異なるものであってもよいし（可変長）、長さが同じであってもよい。特に制限されないが、例えば、HDD（Hard Disk Drive）の1セクタの内容（例えば512バイトや4K（kilo=1024）バイト等）や、データベースの最少単位である１エントリ、あるいは、数ビット、数バイト、数ワード、あるいは、テキスト情報の文字（character）（例えば１文字）等を各アイテムとしてもよい。
【００７１】
グループテスト生成部１０２は、改ざん位置特定のための組み合わせグループテスト（CGT）を生成する。グループテスト生成部１０２は、テストの数ｓと、特定可能な改ざんアイテム数の最大値dに応じてs行m列（ただし、mはアイテム数に対応する）の２値のグループテスト行列Ｗを生成する。
【００７２】
ここで、一例として、メッセージＭ(M[1],M[2],…,M[7])に対して、s＝3、d＝1の場合、グループテスト生成部１０２が、組み合わせグループテスト（CGT）を表すグループテスト行列Ｗとして、以下の3×7の２値行列を出力したとする。
【００７３】
2018193507.tif 000017
…(27)
【００７４】
式(27)に示されるグループテスト行列Ｗは、
第i行の第j列の値が「1」の場合、i番目のテストにアイテムM[j]を用いることを表し、
第i行の第j列の値が「0」の場合、i番目のテストにアイテムM[j]を用いないことを表している。
【００７５】
例えば、式（27）のグループテスト行列Ｗの第1行の行ベクトル[1,1,1,1,0,0,0]は、第1のテストに、アイテムM[1],M[2],M[3],M[4]という計４つのアイテムが用いられることを表している。また、例えば、式（27）のグループテスト行列Ｗの第2行の行ベクトル(1,1,0,0,1,1,0)は、第2のテストに、アイテムM[1],M[2],M[5],M[6］という計４つのアイテムが用いられることを表している。このように、グループテスト行列Ｗの役割は、各要素の値により、各テストに対応するタグ計算においてメッセージ中のどのアイテムを使用するかを示すことにある。
【００７６】
グループテスト行列の生成方法、すなわちグループテストに用いる部分系列の決定方法としては、任意の既存の手法が利用可能である。グループテスト生成部１０２は、例えば、非特許文献１〜４等に開示された手法を用いてグループテスト行列Ｗを生成してもよい。
【００７７】
なお、アイテムをHDDのセクタとし、メッセージＭをファイルやディレクトリに割り当てる最小の容量であるクラスタ（例えば８セクタ）とし、s、dを固定とした場合、グループテスト生成部１０２で求めた２値行列Ｗを入力し認証タグリスト生成装置１００内で記憶保持するようにしてもよい。
【００７８】
ハッシュ関数適用部１０３は、図４に例示したように、グループテスト行列Wに従い、メッセージMを部分系列（アイテム数=m、部分系列数=ｓ）に分解し、各部分系列のアイテムのハッシュ関数を計算し、ハッシュ値を結合演算して認証タグを生成する。
【００７９】
認証タグ出力部１０４は、認証タグT[1]、T[２]、T[3]を受け、認証タグリストTL＝[T[1],T[2], T[3]]を出力する。認証タグ出力部１０４は、認証タグリストTLを例えばディスプレイ装置やプリンタ装置やファイル装置、所定のネットワークノード（データベースや管理サーバなど）等へ出力してもよい。
【００８０】
図６は、本発明の例示的な第１の実施形態の認証タグリスト生成装置１００の動作を説明する流れ図である。
【００８１】
メッセージ入力部１０１はメッセージMを入力する（ステップS1）
【００８２】
ハッシュ関数適用部１０３は、グループテスト行列Wに従い、メッセージMを部分系列（アイテム数=m、部分系列数=ｓ）に分解する（ステップS2）。
【００８３】
ハッシュ関数適用部１０３は、各部分系列のアイテムのハッシュ関数を計算し（ステップS3）、ハッシュ値を結合演算して認証タグを生成する（ステップS４）。
【００８４】
認証タグ出力部１０４は、s個の認証タグからなる認証タグリストを出力する(ステップS5)。  
【００８５】
図７は、図５のハッシュ関数適用部１０３を説明する図である。前述したように、本実施形態では、長さ0の空系列 es（empty string）を導入している。コンバイナでは、部分系列におけるアイテムのインデクスiによらず、（i,es）のハッシュ値を群Gの単位元として扱う。
【００８６】
本実施形態において、部分系列がｎアイテムで終わるとき、ｎアイテムのハッシュ値の隣に、（n, end）のハッシュ値H（（n, end））をコンバイナに入力するようにしてもよい。「end」はes とも非es とも異なる予約語（reserved word）とする。（n, end）は、アイテムインデクスnと予約語endの連結（concatenation）を表している。
【００８７】
ハッシュ関数適用部１０３は、式（27）のグループテスト行列Wに従い、メッセージM(M[1], M[2],…,M[7])は以下の部分系列に分解される。この場合、d=1個の改ざんを特定可能である。
【００８８】
S[1]=(M[1], M[2], M[3], M[4]);
S[2]=(M[1], M[2], M[5], M[6]);
S[3]=(M[1], M[3], M[5], M[7]);
… (28)
【００８９】
図７（A）を参照すると、ハッシュ関数適用部１０３は、部分系列S[1]=(M[1], M[2], M[3], M[4])の各アイテム（アイテムインデクスを連結した拡張アイテム）(1, (M[1])、(2, M[2])、(3, M[3])、(4, M[４])のハッシュ値数H(1, M[1])、H(2, M[2])、H)(3, M[3])、H(4, M[4])と、部分系列S[1]の終わりアイテムインデックス4と予約語（end）を連結した(4, end)のハッシュ値H（4,end）を計算する。そして、第１のコンバイナ（combiner1）では、部分系列S[1]の各アイテムのハッシュ値H(1, M[1])、H(2, M[2])、H(3, M[3])、H(4, M[4])、H（4,end）の結合演算を施し、認証タグT[1]を生成する。
【００９０】
図７（B）を参照すると、ハッシュ関数適用部１０３は、部分系列S[2]=(M[1], M[2], M[5], M[6])のうち、アイテムM[5], M[6]の各アイテム（アイテムインデクスを連結した拡張アイテム）のハッシュ値H(5, M[5])、H(6, M[6])を計算する。アイテムM[1]、M[2]のハッシュ値H(1, M[1])、H(2, M[2])は、部分系列S[1]の処理で計算済みの値を用いる。またハッシュ関数適用部１０３は、部分系列S[2]における空の（テストに用いられない）アイテムM[3], M[4]に対して、H(3, es), H(4, es)、さらに部分系列S[2]の終わりのアイテムインデックス６と予約語（end）とを連結した(6, end)のハッシュ値H(6, end)を計算する。そして、第２のコンバイナ（combiner2）では、S[2]の各アイテム（アイテム番号を連結したもの）ハッシュ関数H(1, M[1])、H(2, M[2])、H(3, es)、H(4, es)、H(5, M[5])、H(6, M[6])、H(6, end)の結合演算を施し、認証タグT[2]を生成する。
【００９１】
図７（C）を参照すると、ハッシュ関数適用部１０３は、部分系列S[3]=(M[1], M[3], M[5], M[7])のアイテム（アイテムインデクスを連結した拡張アイテム）M[7]のハッシュ値H(7, M[7])を計算する。アイテムM[1]、M[3], M[5]のハッシュ値H(1, M[1])、H(2, M[2])は計算済みの値を用いる。さらにハッシュ関数適用部１０３は、部分系列S[3]における空の（テストに用いられない）アイテムM[2], M[4]、M[6]に対して、H(2, es)、 H(4, es)、H(6, es)、さらに部分系列S[3]の終わりのアイテムインデックス７と予約語（end）を連結した(7, end)のハッシュ値H(7, end)を計算する。そして、第３のコンバイナ（combiner 3）では、S[3]の各アイテム（アイテム番号を連結したもの）ハッシュ関数H(1, M[1])、H(2, es)、H(3, M[3])、H(4, es)、H(5, M[5])、H(6, es)、H(7, M[7])、H(7, end)の結合演算を施し、認証タグT[3]を計算する。なお、部分系列のアイテム数m=7に対して、H(7, end)は付加しない構成もあり得る。
【００９２】
図７（A）の例では、部分系列S[1]の終わりのアイテムM[4]以降の空の（テストに用いられない）アイテムM[5]、M[6]、M[7]に対する空系列esのハッシュ値（単位元e）は、第１のコンバイナ(combiner1)には入力されない。
【００９３】
図７（B）の例では、部分系列のS[2]の終わりのアイテムM[6]以降の空の（テストに用いられない）M[7]に対する空系列esのハッシュ値（単位元e）は、第２のコンバイナ(combiner2)には入力されない。空のアイテムM[3]、 M[4]に対する空系列es（(3, es), (4, es)）のハッシュ値は第２のコンバイナ(combiner2)に入力される。
【００９４】
図７のダイアグラムでは、説明の容易化のため、空のアイテムに対応して、空系列(i, es)を入力とするハッシュ関数H()が示されているが、（i, es)のハッシュ値は、結合演算に関する群G'=G∪｛es｝の単位元eとなるため、演算処理上は、当該空のアイテム{es}のハッシュ演算をスキップすることと等価である。
【００９５】
図８は、図５の第１の実施形態において、部分系列がｎアイテムで終わるとき、アイテムインデックスnと予約語（end）を連結した（n, end）のハッシュ値H（n, end）を付加しない例を説明する図である。
【００９６】
図８（A）を参照すると、部分系列S[１]の各アイテム(1, M[1])、(2, M[2])、(3, M[3])、(4, M[4])、(5, es)、(6, es)、（7, es）のハッシュ関数を計算し、結合演算を施し、認証タグT[1]を計算する。
【００９７】
図８（B）を参照すると、部分系列S[2]の各アイテム(1, M[1])、(2, M[2])、(3, es)、(4, es)、(5, M[5])、(6, M[6])、(7, es)のハッシュ関数を計算し、結合演算を施し、認証タグT[2]を計算する。
【００９８】
図８（C）を参照すると、部分系列S[3]の各アイテム(1, M[1])、(2, es)、(3, M[3])、(4, es)、(5, M[5])、(6, es)、(7, M[7])のハッシュ関数を計算し、結合演算を施し、認証タグT[3]を計算する。
【００９９】
このように、図８では、部分系列がnアイテムで終わるときに、終わりを示す予約語のハッシュ関数H（n, end）がない。このため、図８の図式の場合、自明な伸長攻撃（length extension attack）が可能となる。すなわち、伸長攻撃に対して脆弱である。なお、伸長攻撃（length extension attack）は，反復形ハッシュ関数H について，H(M||M') がH(M)とM'のみから計算できるという性質を利用する攻撃である。なお、M||M'はMとM’の連結を表す。
【０１００】
図９(A)は、前述した図７（A）乃至図７（C）を１つにまとめたダイアグラムである。図９において、図９(B)〜（D）は、図９(A)におけるハッシュ関数の記法の説明図である。
【０１０１】
＜変形例１＞
図１０は、図９の変形例１を説明する図である。ハッシュ関数の出力は、MACと同一レベルでの安全性を確保しようとすると、MACよりも大幅に大きくなることがある。MuHAsHの場合、例えば3000ビット、メッセージ認証コード（Message Authentication Code: MAC）では例えば１２８ビットのオーダである。
【０１０２】
例えば楕円曲線等の暗号的ハッシュ関数を用いた場合、ハッシュ関数の出力ビット幅は小さいが、コンバイナの演算コストが大となる。
【０１０３】
コンバイナの出力ビットを所定ビットにカットするか、又は、ハッシュ関数H'()によるコンバイナ（combiner1〜3）の出力ｎハッシュ値を認証タグT[1]〜T[3]とする。図１０の例では、コンバイナ（combiner1〜3）の出力が２Kから４Kビットの場合、ハッシュ関数H'()で例えば256〜512ビットに圧縮するようにしてもよい。
【０１０４】
＜変形例２＞
上記した実施形態は、例えばMACタグリストを生成するルーチンを使用可能である。図１０は、例えば特許文献２等に開示されるMACタグリストを生成するルーチンに実施形態を適用した図式を例示する図である。
【０１０５】
２入力のコンバイナC11では、２つのハッシュ値H(1,M[1])とH(2,M[2])の演算を行う。
【０１０６】
2018193507.tif 000018
… (29)
【０１０７】
２入力のコンバイナC1２では、Y1とハッシュ関数H(3,M[3])を演算する。演算結果は以下となる。
【０１０８】
2018193507.tif 000019
… (30)
【０１０９】
２入力のコンバイナC1３の出力は以下で与えられる。
2018193507.tif 000020
… (31)
【０１１０】
２入力のコンバイナC14の出力Y4は以下で与えられる。
2018193507.tif 000021
… (32)
【０１１１】
コンバイナC14の出力Y4が部分系列S[1]の認証タグT[1]となる。部分系列S[2]、S[3]についても同様である。
【０１１２】
本実施形態において、CGTベースのハッシュ関数の安全性の証明は、非特許文献５の結果をほぼそのまま引き継ぐことができる。すなわち、既存のインクリメンタルハッシュの安全性評価がほぼそのまま使える。CGTハッシュ（ブロック入力空間G’＝G∪｛es｝）の衝突発見確率は、G上のバランス問題を解く確率以下（未満）となる。
【０１１３】
また、インクリメンタルハッシュを用いることで、一度ハッシュをとったデータを更新するコストが小さくできる。
【０１１４】
ただし、本実施形態では、コンバイナに入力するハッシュ値を計算するためのハッシュ関数H()は、逆元の存在を前提とするインクリメンタリティ（式(15）)を有するインクリメンタルハッシュ関数に制限されるものでなく、例えば逆元の存在を前提としないモノイドGの元をなすものであってもよい。
【０１１５】
また、例えば準同型性を有するハッシュ関数を用いるようにしてもよい。準同型性とは、
写像ｆ：X→Y’
が、∀ａ，ｂ∈Xに対して、
f(a・b)=f(a)・f(b)
… (33)
を満たすことをいう。ハッシュ関数H()に関して、
H(a・b)＝H（a）・H(b)
… (34)
である場合に対応する。ここで、演算・は剰余演算（加算又は乗算）であってもよい。
【０１１６】
本実施形態によれば、1アイテムのデータサイズが増えれば、コンバイナの演算コストは相対的に小さくなり、漸近的にはハッシュ関数H()の速度そのものに近づく。
【０１１７】
単純なCGTとハッシュの組合せよりも、本実施形態の方が（一定以上のデータ量であれば）高速と考えられる。
【０１１８】
＜実施形態２＞
図１２は、本発明の例示的な第２の実施形態を説明する図である。図１２には、認証タグ検証装置２００の構成の一例が模式的に示されている。図１２を参照すると認証タグ検証装置２００は、データ入力部２０１と、検証用認証タグ生成部２０２と、認証タグ検証部２０３と、検証結果出力部２０４を備えている。
【０１１９】
データ入力部２０１は、改ざん検出の対象とされるメッセージMと、メッセージMに対して既に生成されている認証タグリストTLと、認証タグリストTLの生成に用いた組み合わせグループテスト（CGT）の部分系列を示す情報としてのグループテスト行列（CGT行列）Ｗとを入力する。データ入力部２０１に入力される、認証タグリストTLおよびCGT行列Ｗは、第１の実施形態の認証タグ生成装置１００が当該メッセージＭに対して生成した認証タグリストTLおよびグループテスト行列Ｗである。データ入力部２０１は、データベースや管理サーバ等から認証タグリストTLを入力するインタフェースや、認証タグ生成装置１００が入力したメッセージMを認証タグ生成装置１００から入力する通信インタフェース等により実現される。
【０１２０】
前記第１の実施形態と同様、以下では、メッセージＭがｍ個の個別のアイテムより構成されているものとする。すなわち、M=(M[1],…,M[m])とする。
【０１２１】
検証用認証タグ生成部２０２は、改ざん検出の対象とされるメッセージＭに対して、入力されたグループテスト行列Ｗを基に、各部分系列に対してハッシュ関数H()を演算し、ハッシュ値を結合した値を検証用認証タグとして生成し、s個の検証用認証タグを含む検証用認証タグリストを生成する。検証用認証タグの生成の仕方は、前記第１の実施形態のハッシュ関数適用部１０３の処理と同様である。
【０１２２】
認証タグ検証部２０３は、入力された認証タグリストTLと、生成された検証用認証タグリストTL’とを比較し、メッセージMに対する改ざんの有無を判定するとともに、改ざん有りと判定された場合には改ざん位置（本実施形態では、改ざんされたアイテム）を特定ないし限定する。また、認証タグ検証部２０３は、改ざんの有無および改ざん位置を示す情報を出力する。認証タグ検証部２０３は、改ざん位置を示す情報として、例えば、改ざんされたアイテムインデックス等を出力してもよい。なお、改ざん無しの場合に改ざん位置を示す情報を無効値に設定するなどして、該情報で改ざんの有無をも示すようにしてもよい。
【０１２３】
認証タグ検証部２０３は、例えば、次のようにして改ざん有無の判定および改ざん位置の特定ないし限定することができる。すなわち、TLとTL’とに対して、エントリごと（例えば、T[i]とT’[i]等。ただし、i=1,…,s）の差をとり、当該エントリのインデックスｉに対応する要素ｂとして、差がゼロの場合に０、差が非ゼロの場合に１をとる２値ベクトル
B=(b[1],…,b[s])
… (35)
を生成してもよい。そして、生成された２値ベクトルBに対し、所定の手続き（復号。より詳細には、グループテストにおける解の解法処理等）を行い、その結果を出力してもよい。
【０１２４】
例えば、認証タグ検証部２０３は、２値ベクトルBのエントリがすべて０であった場合には改ざんなしと判定してもよい。また、認証タグ検証部２０３は、それ以外の場合にはメッセージ全体において、少なくとも１つのアイテムに改ざんがあると判定してもよい。後者の場合（いずれかのエントリが１であった場合）、さらに認証タグ検証部２０３は、b[i]=0となる、すべてのｉ（ただし、i=1,…,ｓ）について、入力されたグループテスト行列Ｗのｉ行目の行ベクトル（wi1，…，wik)を取り出し、wij=1となるすべてのjについて、M[j]を改ざんなしと判定してもよい。以上の処理を行い、改ざんなしと判定されなかったアイテムすべてを改ざん有りとしてもよい。
【０１２５】
検証結果出力部２０４は、認証タグ検証部２０３による検証結果を示す情報、より具体的には、改ざんの有無および改ざんがあった場合の改ざん位置を示す情報を出力する。検証結果出力部２０４は、例えば、ディスプレイ装置やプリンタ装置や所定のネットワークノード（データベースや管理サーバなど）等へ検証結果を示す情報を出力してもよい。
【０１２６】
図１３は、図１２を参照して説明した第２の実施形態の認証タグ検証装置２００の動作の一例を説明する流れ図である。
【０１２７】
まず、データ入力部２０１が、改ざん検出の対象とされるメッセージMと、メッセージＭに対して生成された認証タグリストTLと、s行m列のグループテスト行列Ｗを入力する（ステップS11）。
【０１２８】
次に、検証用認証タグ生成部２０２は、入力されたグループテスト行列Ｗに基づいて、メッセージＭからs個の部分系列S[i](i=1,…,s)を生成（分解）する（ステップS12）。
【０１２９】
次に、検証用認証タグ生成部２０２は、s個の部分系列S[i](i=1,…,s)に対してs個の検証用認証タグからなる検証用認証タグリストTL’=(T’[1],…,T’[s])を生成する（ステップＳ1３）。
【０１３０】
次に、認証タグ検証部２０３が、生成された検証用認証タグリストTL’と、ステップＳ２０１で入力された認証タグリストTLを比較し、改ざんの有無、および改ざんされていた場合には、改ざんされたアイテムを特定し、検証結果とする（ステップS14）。
【０１３１】
最後に、検証結果出力部２０４が、認証タグ検証部２０３による検証結果（改ざんの有無および改ざんされたアイテムの特定結果）を示す情報を出力する（ステップS15）。
【０１３２】
＜第３の実施形態＞
図１４は、本発明の例示的な第３の実施形態のシステム構成の一例を例示する図である。図１４を参照すると、本実施形態のデータ認証システム１は、前述した第１の実施形態の認証タグ生成装置１００と、第２の実施形態の認証タグ検証装置２００と、認証タグ記憶装置３００とを備えている。なお、図１４において、認証タグ生成装置１００、認証タグ記憶装置３００、認証タグ検証装置２００間の矢印はデータの送受信の一例（送信元、宛先）について例示したものであり、認証タグ生成装置１００、認証タグ記憶装置３００、認証タグ検証装置２００間での通信は一方向に制限されることを意味するものでないことは勿論である。
【０１３３】
認証タグ記憶装置３００は、認証タグ生成装置１００が生成した認証タグリストTLを記憶する。認証タグ記憶装置３００は、例えば、認証タグリストTLとともに、当該認証タグリストTLの生成対象とされたメッセージMの識別子と、該認証タグリストTLの生成に用いたグループテスト行列Ｗとを記憶してもよい。なお、認証タグ記憶装置３００は、認証タグ生成時に用いるハッシュ関数H（）として、鍵付きのハッシュ関数を用いる場合などには省略されてもよい。その場合、認証タグ生成装置１００により生成された認証タグリストTLは、メッセージＭとともに、認証タグ検証装置２００もしくはメッセージＭの宛て先とされる任意の装置に送付されてもよい。
【０１３４】
また、認証タグ生成装置１００と認証タグ検証装置２００とは、例えばLAN(Local Area Network)やWAN(Wide Area Network)等の通信ネットワーク等を介して接続する構成としてもよいし、あるいは、一体のユニットに組み込んで実装してもよい。すなわち、１つの装置が、認証タグ生成装置１００の機能（各手段）と認証タグ検証装置２００の機能（各手段）とを有していてもよい。そのような場合、該装置において、ハッシュ関数適用部１０３が検証用認証タグを生成することも可能である。なお、この場合において認証タグ検証装置２００の検証用認証タグ生成部２０２は省略可能である。さらにまた、認証タグ生成装置１００と認証タグ検証装置２００とを特に区別せずに、データ認証装置と呼んでもよい。
【０１３５】
＜第４の実施形態＞
図１５に示すように、前記第１の実施形態の認証タグ生成装置１００、前記第２の実施形態の認証タグ検証装置２００は、それぞれ個別に、あるいは、一体として、コンピュータ装置４００に実装してもよい。図１５を参照すると、コンピュータ装置４００は、プロセッサ（CPU（Central Processing Unit）、データ処理装置）４０１、半導体メモリ（例えばRAM（Random Access Memory）、ROM（Read Only Memory）、又は、EEPROM(Electrically Erasable and Programmable ROＭ）等）、USB（Universal Serial Bus）メモリ、HDD(Hard Disk Drive）、CD（Compact Disc）、DVD（Digital Versatile Disc）等の少なくともいずれかを含む記憶装置４０２と、表示装置（ディスプレイ装置）４０３と、インタフェース４０４を備えている。記憶装置４０２に記憶されたプログラムをプロセッサ４０１で実行することで、前記した認証タグ生成装置１００及び／又は認証タグ検証装置２００の機能を実現するようにしてもよい。なお、記憶装置４０２は、図１４の認証タグ記憶装置３００として用いてもよい。インタフェース４０４は、例えばメッセージＭ、グループテスト行列Ｗ、認証タグリストTL等の少なくともいずれかをネットワークノード（データベース、管理サーバ）等に送信又は、該ネットワークノードから受信するネットワークインタフェースを含む構成としてもよい。
【０１３６】
上記した各実施形態は、改ざん検出システムに適用可能である。例えば、コンピュータシステム全般をターゲットとしてもよいし、クライアントPC（Personal Computer）でエージェントがファイルなどのハッシュを計算、サーバによるハッシュの比較で改ざん検知等に用いてもよい。
また、アプリケーションホワイトリスティング（利用する善良なアプリケーションのみ利用を許可）に適用してもよい。例えば、許可されたファイルのみCPU（Central Processing Unit）に実行させる、あるいは、ファイル実行前に前もって作成したハッシュデータベースとつきあわせる、攻撃リスクが大きい環境（例えばPOS（Point Of Sale）端末等）で用いてもよい。
あるいは、Webアプリケーションファイアウォール（Web Application Firewall :WAF)に適用し、Webサイトの改ざん、不正アクセス対策として用いてもよい。あるいは、ホワイトリスト管理を行う場合、対象のURL（Uniform Resource Locator）毎、パラメータ毎の入力文字種別、正規表現での入力パターンなどを細かく設定するようにしてもよい。
あるは、ログ改ざん検知機能を実装したログ・証跡管理ソフトウェア等に適用してもよい。
あるいは、上記実施形態は、センサネットワーク等に適用してもよい。MAC（Message Authentication Code）タグの送信数を大幅に減らすことが可能である。
また、セキュアブート（ハッシュ値が期待値かどうか確認し、異なる場合には起動を取りやめる）においてハッシュの数を削減することが可能である。
あるいは、上記実施形態は、マルウェアの類似度の判定等に適用してもよい。既存マルウェアのハッシュデータベースの構築に適用してもよい。
【０１３７】
なお、上記の特許文献１、２、非特許文献１−５の開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１３８】
１  データ認証システム
１００  認証タグ生成装置
１０１  メッセージ入力部
１０２  グループテスト生成部
１０３  ハッシュ関数適用部
１０４  認証タグ出力部
２００  認証タグ検証装置
２０１  データ入力部
２０２  検証用認証タグ生成部
２０３  認証タグ検証部
２０４  検証結果出力部
３００  認証タグ記憶装置
４００  コンピュータ装置
４０１  プロセッサ
４０２  記憶装置
４０３  表示装置
４０４  インタフェース
【図１】
2018193507.tif 000022
【図２】
2018193507.tif 000023
【図３】
2018193507.tif 000024
【図４】
2018193507.tif 000025
【図５】
2018193507.tif 000026
【図６】
2018193507.tif 000027
【図７】
2018193507.tif 000028
【図８】
2018193507.tif 000029
【図９】
2018193507.tif 000030
【図１０】
2018193507.tif 000031
【図１１】
2018193507.tif 000032
【図１２】
2018193507.tif 000033
【図１３】
2018193507.tif 000034
【図１４】
2018193507.tif 000035
【図１５】
2018193507.tif 000036
【国際調査報告】
2018193507.tif 000037
2018193507.tif 000038
2018193507.tif 000039