(57)【特許請求の範囲】
【請求項１】
鍵ＫとデータＭとを入力とし、メッセージ認証子τを出力するメッセージ認証子生成装置であって、
第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を、少なくとも１つは前記鍵Ｋまたは前記データＭを用いて定めるパディング部と、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列が、当該メッセージ認証子生成装置で使用するハッシュ関数内の圧縮関数ｆで圧縮されるビット長ｄの整数倍となるように、付加ビットπを生成する付加ビット生成部と、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列のハッシュ関数による変換結果を、メッセージ認証子τとして出力するハッシュ部と、
を備えるメッセージ認証子生成装置。
【請求項２】
請求項１記載のメッセージ認証子生成装置であって、
前記圧縮関数ｆは、ビット長ｎ＋ｄのビット列をビット長ｎに圧縮する関数、初期ベクトルはあらかじめ定められたビット長がｎのビット列とするときに、
前記ハッシュ部は、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番でｄビットずつ取り出すビット列取り出し手段と、
前記ビット列取り出し手段で取り出したビット列と、初期ベクトルＶまたは前回の圧縮関数ｆによる圧縮結果とを入力として、圧縮関数ｆによる圧縮結果を求める圧縮手段と、
を備え、
前記ビット列取り出し手段でのビット列の取り出しと前記圧縮手段での圧縮を繰り返し、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπのすべてのビット列が圧縮に使用されたときの圧縮結果をメッセージ認証子τとする
ことを特徴とするメッセージ認証子生成装置。
【請求項３】
請求項１または２記載のメッセージ認証子生成装置であって、
前記パディング部は、
データＭに第２パディングＰ２を結合したビット列から、データＭを一意に求めることができるという条件を満たすように第２パディングＰ２を定める
ことを特徴とするメッセージ認証子生成装置。
【請求項４】
請求項３記載のメッセージ認証子生成装置であって、
鍵Ｋ、データＭ、第１パディングＰ１、第２パディングＰ２のビット長をそれぞれ、ｋ、ｍ、ｐ１、ｐ２とするときに、
前記パディング部は、
ｋ＋ｐ１＋ｍ＋ｐ２がｄの倍数となるという条件も満たすように第２パディングＰ２を定める
ことを特徴とするメッセージ認証子生成装置。
【請求項５】
請求項４記載のメッセージ認証子生成装置であって、
前記パディング部は、
ｋ＋ｐ１がｄとなるという条件も満たすように第１パディングＰ１を定める
ことを特徴とするメッセージ認証子生成装置。
【請求項６】
請求項５記載のメッセージ認証子生成装置であって、
前記パディング部は、
いかなる付加ビットπとも異なるという条件も満たすように第１パディングＰ１を定め、
第３パディングＰ３をなしとする
ことを特徴とするメッセージ認証子生成装置。
【請求項７】
請求項１または２記載のメッセージ認証子生成装置であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディング部は、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３をなし
と定める
ことを特徴とするメッセージ認証子生成装置。
【請求項８】
請求項４記載のメッセージ認証子生成装置であって、
前記パディング部は、
第１パディングＰ１のビット列が第３パディングＰ３のビット列の一部または全部とならない、かつ、第３パディングＰ３のビット列が第１パディングＰ１のビット列の一部または全部とならないという条件も満たすように、第１パディングＰ１と第３パディングＰ３とを定める
ことを特徴とするメッセージ認証子生成装置。
【請求項９】
請求項１または２記載のメッセージ認証子生成装置であって、
鍵Ｋ、データＭのビット長をそれぞれ、ｋ、ｍとし、
鍵Ｋ、第１パディングＰ１、データＭを結合したビット列を、ｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディング部は、
第１パディングＰ１を“０”、
第２パディングＰ２を、（ｋ＋１＋ｍ）がｄより小さいときは“１”と（ｄ−ｋ−ｍ−２）個の“０”が並んだビット列、（ｋ＋１＋ｍ）がｄ以上のときは“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を“１”
と定める
ことを特徴とするメッセージ認証子生成装置。
【請求項１０】
請求項５記載のメッセージ認証子生成装置であって、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、
鍵Ｋ、第３パディングＰ３、前記ビット列ＭＬ、付加ビットπを結合したビット列のビット長がｄ以下となる前記ビット長ｍＬの最大値を最大ビット長ｍＬｍａｘとし、
あらかじめ定めた０以上ｍＬｍａｘ以下の整数を整数Σとするときに、
前記パディング部は、
いかなる付加ビットπおよびいかなる前記ビット列ＭＬに対しても、第１パディングＰ１は、第３パディングの第１候補Ｐ３’と付加ビットπとを結合したビット列とは異なるという条件と、第１パディングＰ１は、第３パディングの第２候補Ｐ３”と前記ビット列ＭＬと付加ビットπとを結合したビット列とは異なるという条件も満たすように、第１パディングＰ１と第３パディングの第１候補Ｐ３’と第３パディングの第２候補Ｐ３”とを定め、
前記ビット長ｍＬが前記整数Σより大きい場合には、前記第１パディングＰ１、前記第２パディングＰ２を用いると共に、第３パディングＰ３として前記第１候補Ｐ３’を用い、
前記ビット長ｍＬが前記整数Σ以下の場合には、前記第１パディングＰ１を用いると共に、前記第２パディングＰ２にかかわらず第２パディングＰ２をなしとし、第３パディングＰ３として前記第２候補Ｐ３”に前記ビット列ＭＬを結合させたビット列を用いる
ことを特徴とするメッセージ認証子生成装置。
【請求項１１】
請求項１または２記載のメッセージ認証子生成装置であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディング部は、
前記ビット長ｍＬが０より大きい場合には、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を“０”
と定め、
前記ビット長ｍＬが０の場合には、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２をなし、
第３パディングＰ３を“１”
と定める
ことを特徴とするメッセージ認証子生成装置。
【請求項１２】
請求項５記載のメッセージ認証子生成装置であって、
前記パディング部は、
第１パディングＰ１と第３パディングＰ３とが異なるという条件も満たすように、第１パディングＰ１と第３パディングＰ３とを定める
ことを特徴とするメッセージ認証子生成装置。
【請求項１３】
請求項１または２記載のメッセージ認証子生成装置であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、
前記パディング部は、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を（ｄ−ｋ）個の“１”が並んだビット列
と定める
ことを特徴とするメッセージ認証子生成装置。
【請求項１４】
データＭとメッセージ認識子τを入力とし、データＭの検証を行うメッセージ認証子検証装置であって、
データＭと鍵Ｋからメッセージ認証子τ’を生成する請求項１から１３のいずれかに記載のメッセージ認証子生成装置と、
メッセージ認識子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する比較部と
を備えるメッセージ認証子検証装置。
【請求項１５】
鍵ＫとデータＭとを入力とし、メッセージ認証子τを出力するメッセージ認証子生成方法であって、
パディング部で、第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を、少なくとも１つは前記鍵Ｋまたは前記データＭを用いて定めるパディングステップと、
付加ビット生成部で、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列が、当該メッセージ認証子生成装置で使用するハッシュ関数内の圧縮関数ｆで圧縮されるビット長ｄの整数倍となるように、付加ビットπを生成する付加ビット生成ステップと、
ハッシュ部で、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列のハッシュ関数による変換結果を、メッセージ認証子τとして出力するハッシュステップと、
を有するメッセージ認証子生成方法。
【請求項１６】
請求項１５記載のメッセージ認証子生成方法であって、
前記圧縮関数ｆは、ビット長ｎ＋ｄのビット列をビット長ｎに圧縮する関数、初期ベクトルはあらかじめ定められたビット長がｎのビット列とするときに、
前記ハッシュステップは、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番でｄビットずつ取り出すビット列取り出しサブステップと、
前記ビット列取り出し手段で取り出したビット列と、初期ベクトルＶまたは前回の圧縮関数ｆによる圧縮結果とを入力として、圧縮関数ｆによる圧縮結果を求める圧縮サブステップと、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπのすべてのビット列が圧縮に使用されたことを確認する確認サブステップ
を有し、
前記ビット列取り出しサブステップでのビット列の取り出しと前記圧縮サブステップでの圧縮を繰り返し、
鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπのすべてのビット列が圧縮に使用されたときの圧縮結果をメッセージ認証子τとする
ことを特徴とするメッセージ認証子生成方法。
【請求項１７】
請求項１５または１６記載のメッセージ認証子生成方法であって、
前記パディングステップは、
データＭに第２パディングＰ２を結合したビット列から、データＭを一意に求めることができるという条件を満たすように第２パディングＰ２を定める
ことを特徴とするメッセージ認証子生成方法。
【請求項１８】
請求項１７記載のメッセージ認証子生成方法であって、
鍵Ｋ、データＭ、第１パディングＰ１、第２パディングＰ２のビット長をそれぞれ、ｋ、ｍ、ｐ１、ｐ２とするときに、
前記パディングステップは、
ｋ＋ｐ１＋ｍ＋ｐ２がｄの倍数となるという条件も満たすように第２パディングＰ２を定める
ことを特徴とするメッセージ認証子生成方法。
【請求項１９】
請求項１８記載のメッセージ認証子生成方法であって、
前記パディングステップは、
ｋ＋ｐ１がｄとなるという条件も満たすように第１パディングＰ１を定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２０】
請求項１９記載のメッセージ認証子生成方法であって、
前記パディングステップは、
いかなる付加ビットπとも異なるという条件も満たすように第１パディングＰ１を定め、
第３パディングＰ３をなしとする
ことを特徴とするメッセージ認証子生成方法。
【請求項２１】
請求項１５または１６記載のメッセージ認証子生成方法であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディングステップは、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３をなし
と定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２２】
請求項１８記載のメッセージ認証子生成方法であって、
前記パディングステップは、
第１パディングＰ１のビット列が第３パディングＰ３のビット列の一部または全部とならない、かつ、第３パディングＰ３のビット列が第１パディングＰ１のビット列の一部または全部とならないという条件も満たすように、第１パディングＰ１と第３パディングＰ３とを定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２３】
請求項１５または１６記載のメッセージ認証子生成方法であって、
鍵Ｋ、データＭのビット長をそれぞれ、ｋ、ｍとし、
鍵Ｋ、第１パディングＰ１、データＭを結合したビット列を、ｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディングステップは、
第１パディングＰ１を“０”、
第２パディングＰ２を、（ｋ＋１＋ｍ）がｄより小さいときは“１”と（ｄ−ｋ−ｍ−２）個の“０”が並んだビット列、（ｋ＋１＋ｍ）がｄ以上のときは“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を“１”
と定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２４】
請求項１９記載のメッセージ認証子生成方法であって、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、
鍵Ｋ、第３パディングＰ３、前記ビット列ＭＬ、付加ビットπを結合したビット列のビット長がｄ以下となる前記ビット長ｍＬの最大値を最大ビット長ｍＬｍａｘとし、
あらかじめ定めた０以上ｍＬｍａｘ以下の整数を整数Σとするときに、
前記パディングステップは、
いかなる付加ビットπおよびいかなる前記ビット列ＭＬに対しても、第１パディングＰ１は、第３パディングの第１候補Ｐ３’と付加ビットπとを結合したビット列とは異なるという条件と、第１パディングＰ１は、第３パディングの第２候補Ｐ３”と前記ビット列ＭＬと付加ビットπとを結合したビット列とは異なるという条件も満たすように、第１パディングＰ１と第３パディングの第１候補Ｐ３’と第３パディングの第２候補Ｐ３”とを定め、
前記ビット長ｍＬが前記整数Σより大きい場合には、前記第１パディングＰ１、前記第２パディングＰ２を用いると共に、第３パディングＰ３として前記第１候補Ｐ３’を用い、
前記ビット長ｍＬが前記整数Σ以下の場合には、前記第１パディングＰ１を用いると共に、前記第２パディングＰ２にかかわらず第２パディングＰ２をなしとし、第３パディングＰ３として前記第２候補Ｐ３”に前記ビット列ＭＬを結合させたビット列を用いる
ことを特徴とするメッセージ認証子生成方法。
【請求項２５】
請求項１５または１６記載のメッセージ認証子生成方法であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とするときに、
前記パディングステップは、
前記ビット長ｍＬが０より大きい場合には、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を“０”
と定め、
前記ビット長ｍＬが０の場合には、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２をなし、
第３パディングＰ３を“１”
と定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２６】
請求項１９記載のメッセージ認証子生成方法であって、
前記パディングステップは、
第１パディングＰ１と第３パディングＰ３とが異なるという条件も満たすように、第１パディングＰ１と第３パディングＰ３とを定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２７】
請求項１５または１６記載のメッセージ認証子生成方法であって、
鍵Ｋのビット長をｋとし、
データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、
前記パディングステップは、
第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、
第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、
第３パディングＰ３を（ｄ−ｋ）個の“１”が並んだビット列
と定める
ことを特徴とするメッセージ認証子生成方法。
【請求項２８】
データＭとメッセージ認識子τを入力とし、データＭの検証を行うメッセージ認証子検証方法であって、
データＭと鍵Ｋからメッセージ認証子τ’を生成する請求項１５から２７のいずれかに記載のメッセージ認証子生成方法の各ステップと、
比較部で、メッセージ認識子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する比較ステップと
を有するメッセージ認証子検証方法。
【請求項２９】
請求項１から１４のいずれかに記載の装置として、コンピュータを動作させるプログラム。
【請求項３０】
請求項２９記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データに対する認証子を生成または検証するための、メッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法、およびそれらの方法を用いたプログラムと記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証では、メッセージ認証コードＧは、ｋビットの鍵Ｋと任意のビット長のデータＭからメッセージ認証子τを生成する（τ←ＧＫ（Ｍ））。送信者と受信者、またはデータ作成者とデータ利用者とは、メッセージ認証コードＧと鍵Ｋとを共有することで、次のように認証やデータ内容の検証を行うことができる。
送信者またはデータ作成者は、メッセージ認証子生成装置で、鍵ＫとデータＭからメッセージ認証子τを生成する。そして、データＭとメッセージ認証子とを送信または保存する。受信者またはデータ利用者は、メッセージ認証子検証装置で、鍵ＫとデータＭからメッセージ認証子τ’を生成する。そして、τとτ’とを比較する。τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。
【０００３】
メッセージ認証コードＧは、ハッシュ関数Ｈを用いて鍵ＫとデータＭからメッセージ認証子τを生成することが多い。また、ハッシュ関数Ｈは、マークル・ダンガード強化関数Πとマークル・ダンガード反復による関数Ｆから構成されるものがある。マークル・ダンガード強化関数Πは、任意のビット長のビット列（“０”または“１”が並んだ列）をあらかじめ定めたブロック長ｄの整数倍に変換する。マークル・ダンガード反復による関数Ｆは、圧縮関数ｆを繰り返し用いることでブロック長ｄの整数倍のビット列を、あらかじめ定めたビット長ｎのビット列に変換する。具体的には、以下のような関数である。
【０００４】
ｖ←Ｈ（Ｄ）                                                          （１）
Ｄ‖π←Π（Ｄ）                                                      （２）
ｖ←Ｆ（Ｄ‖π）                                                      （３）
ｖｉ←ｆ（ｖｉ−１‖ｍｉ）                                              （４）
ただし、ｖはハッシュ関数Ｈの出力であって、ｎビットのビット列である。Ｄはハッシュ関数への入力であって、任意のビット長のビット列である。“‖”はビット列の結合を意味する記号、πはビット列の長さを調整するために付加される付加ビットである。ｖｉはｎビットのビット列であって、圧縮関数ｆをｉ回繰り返したときの圧縮結果である。ｍｉはビット列Ｍ‖πをｄビットずつ区切った場合のｉ番目のビット列を示しており、ｄビットのビット列である。ビット列Ｍ‖πのビット長がｄのＬ倍とすると、式（４）をＬ回繰り返したときの圧縮結果ｖＬが式（３）の出力ｖとなる。なお、初期のビット列ｖ０には、あらかじめ定めた初期ベクトルＶが用いられる。つまり、式（３）は式（４）をＬ回繰り返すことで実現できる。また、式（２）と（３）との組合せによって、ハッシュ関数Ｈが構成される。
【０００５】
従来のメッセージ認証コードには、ハッシュ関数Ｈを２回適用して安全性を高めたもの（非特許文献１）、２つの鍵を用いてハッシュ関数Ｈは１回適用したもの（非特許文献２）、その２つの鍵を同一のものとし、ハッシュ関数は１回適用したもの（非特許文献３）などがある。
【０００６】
非特許文献１のメッセージ認証コードＧＫ（Ｍ）は、次式のようにメッセージ認証子τを求める。
【数１】
0004886614.tif 000002
ただし、ＩＰＡＤとＯＰＡＤは、ｄビットのあらかじめ定められた定数である。このメッセージ認証コードは、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である（非特許文献４）。
【０００７】
非特許文献２のメッセージ認証コードＧＫ，Ｋ’（Ｍ）は、次式のようにメッセージ認証子τを求める。
τ←Ｈ（Ｋ‖Ｐ‖Ｍ‖Ｋ’）                                            （６）
ただし、Ｐはあらかじめ定められたパディング定数である。このメッセージ認証コードは、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能である（非特許文献５）。しかし、鍵を効率的に回復される攻撃法が知られており、ぜい弱である（非特許文献６）。
【０００８】
非特許文献３のメッセージ認証コードＧＫ（Ｍ）は、次式のようにメッセージ認証子τを求める。
τ←Ｈ（Ｋ‖Ｐ‖Ｍ‖Ｋ）                                              （７）
ただし、Ｐはあらかじめ定められたパディング定数である。
【非特許文献１】M. Bellare, R. Canetti, H. Krawczyk, “Keying hash functions for message authentication,” CRYPTO 1996, LNCS vol.1109, pp.1-15, Springer, Heidelberg (1996).
【非特許文献２】G. Tsudik, “Message authentication with one-way hash functions,” ACM Computer Communication Review 22(5) pp.29-38 (1992).
【非特許文献３】P. Metzger, W. A. Simpson, “IP authentication using keyed MD5,” RFC 1828, IETF (1995).
【非特許文献４】M. Bellare, “New proofs for NMAC and HMAC: Security without collision-resistance,” CRYPTO 2006, LNCS vol.4117, pp.602-619, Springer, Heidelberg (2006).
【非特許文献５】M. Bellare, R. Canetti, H. Krawczyk, “Pseudorandom functions revisited: The cascade construction and its concrete security,” IEEE Symposium on Foundations of Computer Science, pp.514-523 (1996).
【非特許文献６】B. Preneel, P. C. van Oorschot, “On the security of two MAC algorithms,” EUROCRYPT 1996, LNCS vol.1070, pp.19-32, Springer, Heidelberg (1996).
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１のメッセージ認証コードは、鍵は１つだけでよく、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対しても安全である。しかし、圧縮関数を用いる繰り返し回数が、３回分増える（圧縮関数を用いる計算が３回分追加される）。また、ハッシュ関数を２回呼び出さなければならないという問題があった。
非特許文献２のメッセージ認証コードは、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、圧縮関数を用いる計算の追加は１〜２回で済み、ハッシュ関数の呼び出しも１回でよい。しかし、鍵を２つ必要とし、鍵回復攻撃に対して安全でないという問題があった。
【００１０】
非特許文献３のメッセージ認証コードは、鍵は１つでよく、圧縮関数を用いる計算の追加は１〜２回で済み、ハッシュ関数の呼び出しも１回でよい。しかし、耐偽造安全性の証明は知られていない。また、鍵回復攻撃に対して安全でないという問題があった。
このような状況から、本発明の目的は、鍵が1つでよく、圧縮関数を用いる計算の追加は１〜２回で済み、ハッシュ関数の呼び出しが１回でよいメッセージ認証子生成装置、メッセージ認証子検証装置、メッセージ認証子生成方法、メッセージ認証子検証方法を実現することである。
【課題を解決するための手段】
【００１１】
本発明のメッセージ認証子生成装置は、少なくともパディング部と付加ビット生成部とハッシュ部を備え、鍵Ｋ（ビット長ｋ）とデータＭ（ビット長ｍ）とを入力、メッセージ認証子τ（ビット長ｎ）を出力とする。パディング部は、第１パディングＰ１（ビット長ｐ１）、第２パディングＰ２（ビット長ｐ２）、第３パディングＰ３（ビット長ｐ３）を、少なくとも１つは鍵ＫまたはデータＭを用いて定める。付加ビット生成部は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列が、当該メッセージ認証子生成装置で使用するハッシュ関数内の圧縮関数ｆで圧縮されるビット長ｄの整数倍となるように、付加ビットπを生成する。ハッシュ部は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列をハッシュ関数で変換した結果を、メッセージ認証子τとして出力する。
【００１２】
なお、「付加ビット生成部は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列が、当該メッセージ認証子生成装置で使用するハッシュ関数内の圧縮関数ｆで圧縮されるビット長ｄの整数倍となるように、付加ビットπを生成する。」とは、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列を、実際に作成するものに限定されない。例えば、付加ビット生成部は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３のビット長の情報だけから付加ビットπを求めればよい。また、「ハッシュ部は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列をハッシュ関数で変換した結果を、メッセージ認証子τとして出力する。」も、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列を、実際に作成するものに限定されない。例えば、ハッシュ部は、ビット列取り出し手段と圧縮手段とを備えればよい。この場合、ビット列取り出し手段は、結合したビット列を作成せずに、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番でｄビットずつ取り出せばよい。また、圧縮手段は、取り出したビット列と、初期ベクトルＶまたは前回の圧縮関数ｆによる圧縮結果とを入力として、圧縮関数ｆによる圧縮結果を求めればよい。そして、ビット列取り出し手段でのビット列の取り出しと圧縮手段での圧縮を繰り返し、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπのすべてのビット列が圧縮に使用されたときの圧縮結果をメッセージ認証子τとすればよい。このような処理によって、実際には結合したビット列を作成しなくても、結合したビット列をハッシュ関数で変換した結果を得ることができる。
【００１３】
パディング部は以下に示す条件の中からいくつかの条件を満足するように、第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を定める。
（１）データＭに第２パディングＰ２を結合したビット列から、データＭを一意に求めることができるという条件。
（２）ｋ＋ｐ１＋ｍ＋ｐ２がｄの倍数であるという条件。
（３）ｋ＋ｐ１がｄであるという条件。
（４）第１パディングＰ１がいかなる付加ビットπとも異なり、第３パディングＰ３をなしとするという条件。
【００１４】
（５）第１パディングＰ１のビット列が第３パディングＰ３のビット列の一部または全部とならない、かつ、第３パディングＰ３のビット列が第１パディングＰ１のビット列の一部または全部とならないという条件。
（６）データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、鍵Ｋ、第３パディングＰ３、前記ビット列ＭＬ、付加ビットπを結合したビット列のビット長がｄ以下となるビット長ｍＬの最大値を最大ビット長ｍＬｍａｘとし、あらかじめ定めた０以上ｍＬｍａｘ以下の整数を整数Σとする。また、いかなる付加ビットπおよびいかなるビット列ＭＬに対しても、第１パディングＰ１は、第３パディングの第１候補Ｐ３’と付加ビットπとを結合したビット列とは異なる、かつ、第１パディングＰ１は、第３パディングの第２候補Ｐ３”とビット列ＭＬと付加ビットπとを結合したビット列とは異なるように、第１パディングＰ１と第３パディングの第１候補Ｐ３’と第３パディングの第２候補Ｐ３”とを定める。そして、ビット長ｍＬが整数Σより大きい場合には、第１パディングＰ１、第２パディングＰ２を用いると共に、第３パディングＰ３として第１候補Ｐ３’を用いる。ビット長ｍＬが整数Σ以下の場合には、第１パディングＰ１を用いると共に、第２パディングＰ２をなしとし、第３パディングＰ３として第２候補Ｐ３”にビット列ＭＬを結合させたビット列を用いるという条件。
【００１５】
（７）第１パディングＰ１と第３パディングＰ３とが異なるという条件。
また、本発明のメッセージ認証子検証装置は、前述のメッセージ認証子生成装置と比較部とを備える。メッセージ認証子検証装置内のメッセージ認証子生成装置は、データＭと鍵Ｋからメッセージ認証子τ’を生成する。比較部は、メッセージ認識子τとメッセージ認証子τ’とを比較してデータＭの検証結果を出力する。
【発明の効果】
【００１６】
本発明のメッセージ認証子生成装置はこのような構成なので、鍵が1つでよく、圧縮関数を用いる計算の追加は原則１〜２回で済み、ハッシュ関数の呼び出しが１回でよい。
さらに、第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を、上述のいくつかの条件を満たすように決定すれば、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対する安全性を確保できる。例えば、（１）〜（４）の条件を満たせば、演算量を少なくしながら、安全性を確保できる。（１）と（２）と（５）の条件を満たせば、さらに演算量を少なくできる。（１）〜（３）と（６）の条件を満たせば、さらに圧縮率の低い圧縮関数を用いることができる。（１）〜（３）と（７）の条件を満たせば、（１）〜（４）の条件を満たす場合と同等の効果が得られる。このように、これらの条件は組み合わせることができる。
【発明を実施するための最良の形態】
【００１７】
［第１実施形態］
第１実施形態では、本発明のメッセージ認証子生成装置とメッセージ認証子生成方法を示す。図１に本発明のメッセージ認証子生成装置の機能構成例を示す。また、図２に本発明のメッセージ認証子生成装置の処理フローを示す。メッセージ認証子生成装置１００は、パディング部１１０、付加ビット生成部１２０、ハッシュ部１３０、記録部１９０を備え、鍵Ｋ（ビット長ｋ）とデータＭ（ビット長ｍ）とが入力、メッセージ認証子τ（ビット長ｎ）が出力である。
【００１８】
パディング部１１０は、第１パディングＰ１（ビット長ｐ１）、第２パディングＰ２（ビット長ｐ２）、第３パディングＰ３（ビット長ｐ３）を定める（Ｓ１１０）。付加ビット生成部１２０は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列が、使用するハッシュ関数内の圧縮関数ｆで圧縮されるビット長ｄの整数倍となるように、付加ビットπを生成する（Ｓ１２０）。ハッシュ部１３０は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番で結合されたビット列をハッシュ関数で変換した結果を、メッセージ認証子τとして出力する（Ｓ１３０）。記録部１９０は、鍵Ｋ、データＭ、第１パディングＰ１、第２パディングＰ２、第３パディングＰ３、付加ビットπなどを記録する。なお、記録部１９０を備えず、その他の構成部でこれらの情報を記録してもかまわない。
【００１９】
なお、付加ビット生成部１２０とハッシュ部１３０は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπを結合したビット列を作成するとは限らない。例えば、付加ビット生成部１２０は、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３のビット長の情報だけから付加ビットπを求めれば、結合したビット列を作成する必要は無い。また、例えば、ハッシュ部１３０に、図１に点線で示すように、ビット列取り出し手段１３１と圧縮手段１３２とを備えさせる。この場合の処理フローを、図２に点線で示す。この処理では、ビット列取り出し手段１３１は、結合したビット列を作成せずに、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπの順番でｄビットずつ取り出す（Ｓ１３１）。圧縮手段１３２は、取り出したビット列と、初期ベクトルＶまたは前回の圧縮関数ｆによる圧縮結果とを入力として、圧縮関数ｆによる圧縮結果を求める（Ｓ１３２）。そして、鍵Ｋ、第１パディングＰ１、データＭ、第２パディングＰ２、鍵Ｋ、第３パディングＰ３、付加ビットπのすべてのビット列が圧縮に使用されたかを確認する（Ｓ１３３）。ステップＳ１３３がＮｏの場合は、ビット列取り出し手段１３１でのビット列の取り出しと圧縮手段での圧縮を繰り返す（ビット列取り出し手段１３１で次のｄビットを取り出し、処理を続ける）。ステップＳ１３３がＹｅｓの場合は、このときの圧縮手段１３２の圧縮結果をメッセージ認証子τとする。
【００２０】
図３に、あらかじめ定めた条件にしたがって第１パディングＰ１を定めるステップ（Ｓ１１１）、第２パディングＰ２を定めるステップ（Ｓ１１２）、第３パディングＰ３を定めるステップ（Ｓ１１３）を示した処理フローの例を示す。パディング部１１０は、例えば、以下に示す条件の例の中からいくつかの条件を満足するように、第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を定める。
【００２１】
（１）データＭに第２パディングＰ２を結合したビット列から、データＭを一意に求めることができるという条件。
（２）ｋ＋ｐ１＋ｍ＋ｐ２がｄの倍数であるという条件。
（３）ｋ＋ｐ１がｄであるという条件。
（４）第１パディングＰ１がいかなる付加ビットπとも異なり、第３パディングＰ３をなしとするという条件。
（５）第１パディングＰ１のビット列が第３パディングＰ３のビット列の一部または全部とならない、かつ、第３パディングＰ３のビット列が第１パディングＰ１のビット列の一部または全部とならないという条件。
【００２２】
（６）データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とし、鍵Ｋ、第３パディングＰ３、前記ビット列ＭＬ、付加ビットπを結合したビット列のビット長がｄ以下となるビット長ｍＬの最大値を最大ビット長ｍＬｍａｘとし、あらかじめ定めた０以上ｍＬｍａｘ以下の整数を整数Σとする。また、いかなる付加ビットπおよびいかなるビット列ＭＬに対しても、第１パディングＰ１は、第３パディングの第１候補Ｐ３’と付加ビットπとを結合したビット列とは異なる、かつ、第１パディングＰ１は、第３パディングの第２候補Ｐ３”とビット列ＭＬと付加ビットπとを結合したビット列とは異なるように、第１パディングＰ１と第３パディングの第１候補Ｐ３’と第３パディングの第２候補Ｐ３”とを定める。そして、ビット長ｍＬが整数Σより大きい場合には、第１パディングＰ１、第２パディングＰ２を用いると共に、第３パディングＰ３として第１候補Ｐ３’を用いる。ビット長ｍＬが整数Σ以下の場合には、第１パディングＰ１を用いると共に、第２パディングＰ２をなしとし、第３パディングＰ３として第２候補Ｐ３”にビット列ＭＬを結合させたビット列を用いるという条件。
【００２３】
（７）第１パディングＰ１と第３パディングＰ３とが異なるという条件。
第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を、上記のいくつかの条件を満たすように決定すれば、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対する安全性を確保できる。
【００２４】
条件の組み合わせの例１
１つ目の組み合わせの例は、（１）〜（４）の条件を満たすことである。この例では、データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とする。この条件の具体例としては、第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、第３パディングＰ３をなしと定める例がある。
【００２５】
この例のイメージを図４に示す。圧縮手段１３２は、図１に示したように１つであるが、図４では繰り返し回数が分かるように、圧縮手段１３２を繰り返し回数だけ並べて示している。なお、圧縮手段を示す番号の添え字は、何回目の繰り返しに相当するのかを示している。繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。そして、繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、データＭをｄビットずつに区切った最初のビット列Ｍ１とが、圧縮手段１３２に入力される。このように繰り返し処理が行われ、Ｌ＋１回目の繰り返しでは、Ｌ回目の圧縮結果（ｎビット）と、ビット列ＭＬと第２パディングＰ２を結合したビット列（ｄビット）が、圧縮手段１３２入力される。Ｌ＋２回目の繰り返しでは、Ｌ＋１回目の圧縮結果（ｎビット）と、鍵Ｋと付加ビットπを結合したビット列（ｄビット）が、圧縮手段１３２入力される。そして、Ｌ＋２回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。
【００２６】
このように、（１）〜（４）の条件を満たせば、鍵は１つでよく、圧縮関数を用いる計算の追加は２回で済み、ハッシュ関数の呼び出しも１回でよい。また、この条件の組み合わせの場合は、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対しても安全である。
【００２７】
条件の組み合わせの例２
２つ目の組み合わせの例は、（１）と（２）と（５）の条件を満たすことである。この例では、鍵Ｋ、第１パディングＰ１、データＭを結合したビット列を、ｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とする。この条件の具体例としては、次のような定め方がある。第１パディングＰ１を“０”とする。第２パディングＰ２を、（ｋ＋１＋ｍ）がｄより小さいときは“１”と（ｄ−ｋ−ｍ−２）個の“０”が並んだビット列、（ｋ＋１＋ｍ）がｄ以上のときは“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列とする。第３パディングＰ３を“１”とする。
【００２８】
この例のイメージを図５に示す。図５の（ａ）は、（ｋ＋１＋ｍ）がｄより小さいときの処理を示している。この場合は、繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１とデータＭと第２パディングＰ２を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、鍵Ｋと第３パディングＰ３と付加ビットπが結合したビット列（ｄビット）が、圧縮手段１３２入力される。そして、２回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。
【００２９】
図５の（ｂ）は、（ｋ＋１＋ｍ）がｄ以上のときの処理を示している。この場合は、繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１とデータＭの最初の（ｄ−ｋ−１）ビットＭ１を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、データＭの次のｄビットＭ２とが、圧縮手段１３２に入力される。このように繰り返し処理が行われ、Ｌ回目の繰り返しでは、Ｌ−１回目の圧縮結果（ｎビット）と、ビット列ＭＬと第２パディングＰ２を結合したビット列（ｄビット）が、圧縮手段１３２入力される。Ｌ＋１回目の繰り返しでは、Ｌ回目の圧縮結果（ｎビット）と、鍵Ｋと第３パディングＰ３と付加ビットπを結合したビット列（ｄビット）が、圧縮手段１３２入力される。そして、Ｌ＋１回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。
【００３０】
このように、（１）と（２）と（５）の条件を満たせば、鍵は１つでよく、圧縮関数を用いる計算の追加は１回で済み、ハッシュ関数の呼び出しも１回でよい。したがって、１つ目の組み合わせの例よりも、さらに演算量を少なくできる。また、この条件の組み合わせの場合も、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対しても安全である。
【００３１】
条件の組み合わせの例３
３つ目の組み合わせの例は、（１）〜（３）と（６）の条件を満たすことである。この例では、データＭを結合したビット列を、ｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とする。この条件の具体例としては、次のような定め方がある。ビット長ｍＬが０より大きい場合には、第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、第３パディングＰ３を“０”とする。ビット長ｍＬが０の場合には、第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、第２パディングＰ２をなし、第３パディングＰ３を“１”とする。
【００３２】
この例のイメージを図６に示す。図６の（ａ）は、ビット長ｍＬが０より大きい場合の処理を示している。この場合は、繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、データＭをｄビットずつに区切った最初のビット列Ｍ１とが、圧縮手段１３２に入力される。このように繰り返し処理が行われ、Ｌ＋１回目の繰り返しでは、Ｌ回目の圧縮結果（ｎビット）と、ビット列ＭＬと第２パディングＰ２を結合したビット列（ｄビット）が、圧縮手段１３２入力される。Ｌ＋２回目の繰り返しでは、Ｌ＋１回目の圧縮結果（ｎビット）と、鍵Ｋと第３パディングＰ３と付加ビットπが結合したビット列（ｄビット）が、圧縮手段１３２入力される。そして、Ｌ＋２回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。
【００３３】
図６の（ｂ）は、ビット長ｍＬが０の場合の処理を示している。この場合は、繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、データＭをｄビットずつに区切った最初のビット列Ｍ１とが、圧縮手段１３２に入力される。このように繰り返し処理が行われ、Ｌ回目の繰り返しでは、Ｌ−１回目の圧縮結果（ｎビット）と、データＭをｄビットずつに区切ったときのＬ−１番目のビット列ＭＬ−１とが、圧縮手段１３２入力される。Ｌ＋１回目の繰り返しでは、Ｌ回目の圧縮結果（ｎビット）と、鍵Ｋと第３パディングＰ３と付加ビットπを結合したビット列（ｄビット）が、圧縮手段１３２入力される。そして、Ｌ＋１回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。なお、ビット長ｍＬが０の場合とは、ビット列ＭＬがない場合を意味しているので、ビット列ＭＬを圧縮手段１３２に入力することはない。
【００３４】
このように、（１）〜（３）と（６）の条件を満たせば、鍵は１つでよく、圧縮関数を用いる計算の追加は１回または２回で済み、ハッシュ関数の呼び出しも１回でよい。したがって、１つ目の組み合わせの例よりも、さらに演算量を少なくできる。特に、圧縮率が小さい圧縮関数を使うことができるという効果もある。また、この条件の組み合わせの場合も、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対しても安全である。
【００３５】
条件の組み合わせの例４
４つ目の組み合わせの例は、（１）〜（３）と（７）の条件を満たすことである。この例では、データＭをｄビットずつに区切った時に最後に余るビット列をビット列ＭＬ（ただし、ＭＬのビット長ｍＬは０からｄ−１）とする。この条件の具体例としては、第１パディングＰ１を（ｄ−ｋ）個の“０”が並んだビット列、第２パディングＰ２を“１”と（ｄ−ｍＬ−１）個の“０”が並んだビット列、第３パディングＰ３を（ｄ−ｋ）個の“１”が並んだビット列と定める例がある。
【００３６】
この例のイメージを図７に示す。繰り返しの１回目では、あらかじめ定められた初期ベクトルＶ（ｎビット）と、鍵Ｋと第１パディングＰ１を結合したビット列（ｄビット）とが、圧縮手段１３２に入力される。そして、繰り返しの２回目では、１回目の圧縮結果（ｎビット）と、データＭをｄビットずつに区切った最初のビット列Ｍ１とが、圧縮手段１３２に入力される。このように繰り返し処理が行われ、Ｌ＋１回目の繰り返しでは、Ｌ回目の圧縮結果（ｎビット）と、ビット列ＭＬと第２パディングＰ２を結合したビット列（ｄビット）が、圧縮手段１３２入力される。Ｌ＋２回目の繰り返しでは、Ｌ＋１回目の圧縮結果（ｎビット）と、鍵Ｋと第３パディングＰ３を結合したビット列（ｄビット）が、圧縮手段１３２入力される。Ｌ＋３回目の繰り返しでは、Ｌ＋２回目の圧縮結果（ｎビット）と、付加ビットπが、圧縮手段１３２入力される。そして、Ｌ＋３回目の圧縮結果が、メッセージ認証子τとして、ハッシュ部１３０から出力される。
【００３７】
このように、（１）〜（３）と（７）の条件を満たせば、圧縮関数を用いる計算の追加は３回となってしまうが、鍵は１つでよく、ハッシュ関数の呼び出しも１回でよい。また、この条件の組み合わせの場合は、圧縮関数の擬似乱数性に基づく耐偽造安全性証明が可能であり、鍵回復攻撃に対しても安全である。
なお、上述の条件や条件の組み合わせは例示である。条件は（１）〜（７）に限るものではなく、条件の組み合わせも上述の例に限るものでもない。
【００３８】
［第２実施形態］
図８に本発明のメッセージ認証子検証装置の機能構成例を示す。また、図９に本発明のメッセージ認証子検証装置の処理フロー例を示す。メッセージ認証子検証装置２００は、第１実施形態で示したメッセージ認証子生成装置１００と比較部２１０と記録部２９０を備え、データＭ（ビット長ｍ）とメッセージ認証子τ（ビット長ｎ）が入力、検証結果が出力である。
【００３９】
メッセージ認証子検証装置２００内のメッセージ認証子生成装置１００は、データＭとあらかじめ記録しておいた鍵Ｋからメッセージ認証子τ’を生成する（Ｓ１００）。比較部２１０は、メッセージ認識子τとメッセージ認証子τ’とを比較する。そして、τ＝τ’ならば、送信者またはデータ作成者の認証、およびデータ内容の整合性が検証されたとする。τ≠τ’ならば、送信者またはデータ作成者の詐称、もしくはデータの改ざんがあると判断する。そして、検証結果を出力する（Ｓ２１０）。なお、記録部２９０を備えず、その他の構成部でこれらの情報を記録してもよい。
【００４０】
このような構成なので、メッセージ認証子検証装置２００でも、メッセージ認証子生成装置１００と同じ効果を得ることができる。
図１０に、コンピュータの機能構成例を示す。なお、本発明のメッセージ認証子生成装置およびメッセージ認証子検証装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【００４１】
［安全性の証明］
以下では、第１実施形態の条件の組み合わせの例１で示した具体例で、安全性が確保されることを証明する。
【００４２】
定義
まず、証明に使用する記号等を以下のように定義する。
“Ｖ”は、圧縮手段に入力する初期ベクトル（Initial Vector）である。
“０ｐ”は、ｐ個の“０”が並んだビット列である。
“攻撃者”は、オラクルを呼び出すアルゴリズムＡである。
【００４３】
【数２】
0004886614.tif 000003
は、集合Ｘから要素ｘを一様ランダムに選ぶことである。
【００４４】
【数３】
0004886614.tif 000004
は、オラクルＯにアクセスする攻撃者Ａがｘを出力することを表す。
【００４５】
オラクルＯはしばしばゲームＧで定義される。その場合、
【数４】
0004886614.tif 000005
【００４６】
ＰＲＦｓ：“ＰＲＦ（擬似乱数関数族）”は、安全なＭＡＣであり、本明細書中の全てのＭＡＣは、ＲＦＰ型である。関数｛ｆＫ：Ｘ→Ｙ｝Ｋ∈ＫＥＹについて考えると、prf攻撃者は２つのオラクル
【数５】
0004886614.tif 000006
を区別する。
【００４７】
【数６】
0004886614.tif 000007
をｆに対するＡのprfアドバンテージと定義する。
ｃＡＵ（computationally Almost Universal）：au攻撃者 Ａはオラクルを呼び出さない。メッセージの組（Ｍ，Ｍ’）∈Ｘ×Ｘを出力するだけである。
【００４８】
【数７】
0004886614.tif 000008
をｆに対するＡのauアドバンテージと定義する。
リソース：攻撃者 Ａのリソースは、時間リソースｔ、オラクルへの質問回数ｑ、各質問のビット数μで評価される。
【００４９】
【数８】
0004886614.tif 000009
と定義する。ここで、＊はｐｒｆ、ａｕ等である。また、Ｔｆ（μ）は、ビット数μの入力があった場合に、関数ｆの計算に必要な時間リソースである。
【００５０】
命題１
任意のｔに対して、
【数９】
0004886614.tif 000010
が成り立つ。
【００５１】
証明
Ａを、最大値ｔの時間リソースと最大μビットの出力メッセージのｆに対するau攻撃者とする。上記の定義より、
【数１０】
0004886614.tif 000011
ここで、（Ｍ，Ｍ’）は、最大μビットの異なるメッセージの組である。よって、
【数１１】
0004886614.tif 000012
が成り立つメッセージの組（Ｍ，Ｍ’）が存在する。したがって、定数Ｍ，Ｍ’が組み込まれた新しい攻撃者Ｂを構成することにより、証明したい不等式を得る。
【００５２】
安全性の証明
次の定理１は、条件の組み合わせ１による構成の安全性を示している。
【００５３】
定理１
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎ、ｆで構成される条件の組み合わせ１による構成ＳＫをＳＫ：｛０，１｝≦Ｎ→｛０，１｝ｎとすると、条件の組み合わせ１による構成Ｓは、
【数１２】
0004886614.tif 000013
がＰＲＦであることを条件として、ＰＲＦである。言い換えると、次式が成り立つ。
【００５４】
【数１３】
0004886614.tif 000014
ただし、
【数１４】
0004886614.tif 000015
は、ｆの入力のｎ＋１からｎ＋ｋビット目までを鍵とした関数であり、
【数１５】
0004886614.tif 000016
は、ｆの入力の最初のｎビットを鍵とした関数である。
定理１は、後述の３つの命題により証明できる。
【００５５】
命題２
【数１６】
0004886614.tif 000017
条件の組み合わせの例１による構成ＳはＰＲＦである。言い換えると、次式が成り立つ。
【数１７】
0004886614.tif 000018
【００５６】
証明
Ａを、最大値ｔの時間リソースを持ち、最大ｑ（≧２）回のオラクルへの質問とそれぞれ最大μビットのメッセージを出力するＳに対するprf攻撃者とする。
【００５７】
【数１８】
0004886614.tif 000019
を、図１１に示すようにサブルーチンとしてＡを用いて構築する。ここで、Ｂは最大値ｔの時間リソースを持ち、最大ｑ＋１回の質問をオラクルに対して行う。Ｃは、それぞれ最大μビットの２つのメッセージを出力する。したがって、次式のように表現できる。
【００５８】
【数１９】
0004886614.tif 000020
Ｇ、Ｇ’を図１２に定義された２つのゲームとする。これらのゲームは、攻撃者Ａのためのオラクルである。
【００５９】
主張：次式が成り立つ。
【数２０】
0004886614.tif 000021
【００６０】
証明
【数２１】
0004886614.tif 000022
である。一方、
【数２２】
0004886614.tif 000023
である。
【００６１】
主張：全てのＭに対してπ（λ（Ｍ））≠０ｐとする。よって、ゲームＧでは、すべての質問Ｍに対して
【数２３】
0004886614.tif 000024
であり、Ａの質問への返答の間は、ランダム関数（オラクル）
【００６２】
【数２４】
0004886614.tif 000025
は、入力値Ｖ‖１０ｐに対応する値を出力することはない。これは、ゲームＧでは、
【００６３】
【数２５】
0004886614.tif 000026
は、Ａの質問とは独立なランダムな値であることを意味する。よって、ゲームＧとゲームＧ’は等価である。
ここで、一般性を失うことなく攻撃者Ａは質問を繰り返さず、たとえＡの質問へのどのような返答が行われたとしても、Ａの質問の総数は常に最大値ｑ以下であると仮定する。Ｍ１，…，Ｍｑを順番にＡの質問とする。
【００６４】
Ｅを、１≦ｉ＜ｊ≦ｑに対して発生する事象
【数２６】
0004886614.tif 000027
とする。Ｅが発生しない限り、ゲーム Ｇ’中でのＡとオラクル
【数２７】
0004886614.tif 000028
に対して実行されたＡは、正確に同じ処理を行う。Game Playingの基本的な命題は、非特許文献（M. Bellare, P. Rogaway, “The security of triple encryption and a framework for code-based game-playing proofs,” In:Vaudenay, S. (ed.) EUROCRYPT 2006, LNCS vol.4004, pp.409-426, Springer, Heidelberg (2006).）に示されている。このGame Playningの基本的な命題により、次式が成り立つ。
【数２８】
0004886614.tif 000029
【００６５】
主張：次式が成り立つ。
【数２９】
0004886614.tif 000030
【００６６】
証明
Ｅ’を、１≦ｉ＜ｊ≦ｑに対する事象
【００６７】
【数３０】
0004886614.tif 000031
であって、Ｐｒ［Ｅ］≦Ｐｒ［Ｅ’］とする。１≦α＜β≦ｑに対して、Ｅ’α，βを、
【数３１】
0004886614.tif 000032
が発生しているという事象とする。１≦α＜β≦ｑに対して、事象Ｅ’α，βは互いに素であり、
【数３２】
0004886614.tif 000033
である。よって、次式が成り立つ。
【００６８】
【数３３】
0004886614.tif 000034
また、
【数３４】
0004886614.tif 000035
である。
【００６９】
命題３
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎとすると、マークル・ダンガード繰返しによって圧縮関数ｆから構成された鍵付ハッシュ関数ＦＫ：｛０，１｝ｄ＊→｛０，１｝ｎがｃＡＵならば、任意の１対１パディングを組み合わせて構成した
【数３５】
0004886614.tif 000036
もｃＡＵである。言い換えると、次式の関係が成り立つ。
【００７０】
【数３６】
0004886614.tif 000037
【００７１】
証明
Ａを、最大値ｔの時間リソースを持ち、それぞれ最大μビットのメッセージ（Ｍ，Ｍ’）を出力する、
【数３７】
0004886614.tif 000038
に対するau攻撃者とする。そして、Ｂの出力を組
【数３８】
0004886614.tif 000039
とすることで、Ｆに対するau攻撃者Ｂを容易に構築できる。ここで、Ｍ≠Ｍ’であれば、
【数３９】
0004886614.tif 000040
である。
【００７２】
命題４
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎとすると、
【数４０】
0004886614.tif 000041
がＰＲＦであれば、マークル・ダンガード繰返しによって圧縮関数ｆから構成された鍵付ハッシュ関数ＦＫ：｛０，１｝ｄ＊→｛０，１｝ｎがｃＡＵである。言い換えると、次式の関係が成り立つ。
【００７３】
【数４１】
0004886614.tif 000042
【００７４】
証明
命題４は非特許文献４で証明されている。
上述の命題から、以下の式が成り立つ。
【００７５】
【数４２】
0004886614.tif 000043
このように、定理１が証明できた。したがって、第１実施形態の条件の組み合わせの例１の条件を満足するように第１パディングＰ１、第２パディングＰ２、第３パディングＰ３を定めれば、安全性が確保できる。
なお、組み合わせの例２、条件の組み合わせの例３、条件の組み合わせの例４は、以下に示す定理２、定理３、定理４を同様に証明することで、安全性の証明ができる。具体的な証明は省略する。
【００７６】
定理２
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎ、ｆで構成される条件の組み合わせ２による構成 ＳＫをＳＫ：｛０，１｝≦Ｎ→｛０，１｝ｎとすると、
【数４３】
0004886614.tif 000044
がＰＲＦであることを条件として、次式が成り立つ。
【数４４】
0004886614.tif 000045
【００７７】
定理３
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎ、ｆで構成される条件の組み合わせ３による構成 ＳＫをＳＫ：｛０，１｝≦Ｎ→｛０，１｝ｎとすると、
【００７８】
【数４５】
0004886614.tif 000046
がＰＲＦであることを条件として、次式が成り立つ。
【００７９】
【数４６】
0004886614.tif 000047
【００８０】
定理４
圧縮関数ｆをｆ：｛０，１｝ｎ＋ｐ→｛０，１｝ｎ、ｆで構成される条件の組み合わせ４による構成 ＳＫをＳＫ：｛０，１｝≦Ｎ→｛０，１｝ｎとすると、
【数４７】
0004886614.tif 000048
がＰＲＦであることを条件として、次式が成り立つ。
【００８１】
【数４８】
0004886614.tif 000049
【産業上の利用可能性】
【００８２】
本発明のメッセージ認証子生成装置およびメッセージ認証子検証装置は、例えば携帯電話、パソコン、ルータ、サーバなどに組み込み、送受信されるデータや蓄積されたデータに対する認証子を生成することまたは検証することに利用できる。
【図面の簡単な説明】
【００８３】
【図１】本発明のメッセージ認証子生成装置の機能構成例を示す図。
【図２】本発明のメッセージ認証子生成装置の処理フローを示す図。
【図３】あらかじめ定めた条件にしたがって第１パディングＰ１を定めるステップ、第２パディングＰ２を定めるステップ、第３パディングＰ３を定めるステップを示した処理フローの例を示す図。
【図４】条件の組み合わせの例１の場合のハッシュ部の処理のイメージを示す図。
【図５】条件の組み合わせの例２の場合のハッシュ部の処理のイメージを示す図。
【図６】条件の組み合わせの例３の場合のハッシュ部の処理のイメージを示す図。
【図７】条件の組み合わせの例４の場合のハッシュ部の処理のイメージを示す図。
【図８】本発明のメッセージ認証子検証装置の機能構成例を示す図。
【図９】本発明のメッセージ認証子検証装置の処理フロー例を示す図。
【図１０】コンピュータの機能構成例を示す図。
【図１１】攻撃者Ｂと攻撃者Ｃの記述を示す図。
【図１２】ゲーム Ｇとゲーム Ｇ’を示す図。
【符号の説明】
【００８４】
１００  メッセージ認証子生成装置
１１０  パディング部
１２０  付加ビット生成部
１３０  ハッシュ部
１３１  ビット列取り出し手段
１３２  圧縮手段
１９０  記録部
２００  メッセージ認証子検証装置
２１０  比較部
２９０  記録部
【図１】
0004886614.tif 000050
【図２】
0004886614.tif 000051
【図３】
0004886614.tif 000052
【図４】
0004886614.tif 000053
【図５】
0004886614.tif 000054
【図６】
0004886614.tif 000055
【図７】
0004886614.tif 000056
【図８】
0004886614.tif 000057
【図９】
0004886614.tif 000058
【図１０】
0004886614.tif 000059
【図１１】
0004886614.tif 000060
【図１２】
0004886614.tif 000061