(57)【特許請求の範囲】
【請求項１】
外部から入力を受け付けたメッセージに該メッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置であって、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ部と、
前記メッセージの入力を外部から受付けた場合、該メッセージと独立な乱数を生成する乱数生成部と、
前記乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化部と、
前記乱数と前記ハッシュ値との排他的論理和に対して第２の鍵を有する前記暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化部と、
前記第１の中間変数と前記第２の中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、前記タグとして生成するタグ生成部と、
前記メッセージと前記乱数と前記タグとを該メッセージの宛先へ送信する出力部と、
を有するタグ生成装置。
【請求項２】
請求項１記載のタグ生成装置において、
前記ハッシュ部は、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記ハッシュ値として生成することを特徴とするタグ生成装置。
【請求項３】
請求項１または２記載のタグ生成装置において、
前記マスク付暗号化部は、前記第２の中間変数を生成するとともに、前記ハッシュ値に対して第３の鍵を有する前記暗号関数を適用して得られた値を第３の中間変数として生成し、
前記タグ生成部は、前記第１の中間変数と前記第２の中間変数と前記第３の中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記タグとして生成することを特徴とするタグ生成装置。
【請求項４】
外部から送信されてきたメッセージを該メッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証装置であって、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ部と、
前記メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化部と、
前記乱数と前記検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する前記暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化部と、
前記第１の検証用中間変数と前記第２の検証用中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成部と、
前記検証用タグと、前記メッセージとともに外部から送信されてきた前記タグとを比較する比較部と、
を有するタグ検証装置。
【請求項５】
請求項４記載のタグ検証装置において、
前記ハッシュ部は、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記検証用ハッシュ値として生成することを特徴とするタグ検証装置。
【請求項６】
請求項４または５に記載のタグ検証装置において、
前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが同じである場合、前記送信されてきたメッセージが正当な送信者から送られたものである旨を示す情報を出力し、前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが異なっている場合、前記送信されてきたメッセージが正当な送信者から送られたものでない旨を示す情報を出力する出力部を有することを特徴とするタグ検証装置。
【請求項７】
請求項４乃至６のいずれか１項に記載のタグ検証装置において、
前記マスク付暗号化部は、前記第２の検証用中間変数を生成するとともに、前記検証用ハッシュ値に対して第３の検証鍵を有する前記暗号関数を適用して得られた値を第３の検証用中間変数として生成し、
前記タグ生成部は、前記第１の検証用中間変数と前記第２の検証用中間変数と前記第３の検証用中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記検証用タグとして生成することを特徴とするタグ検証装置。
【請求項８】
外部から入力を受付けたメッセージに該メッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置と、前記メッセージの送信元から送信されてきた前記メッセージを前記タグを用いて検証するタグ検証装置とを有する通信システムであって、
前記タグ生成装置は、
前記メッセージに対して所定のハッシュ関数を適用して得られた値をハッシュ値として生成し、前記メッセージの入力を外部から受付けた場合、該メッセージと独立な乱数を生成し、前記乱数に対して第１の鍵を有する暗号関数を適用して得られた値を第１の中間変数として生成し、前記乱数と前記ハッシュ値との排他的論理和に対して第２の鍵を有する前記暗号関数を適用して得られた値を第２の中間変数として生成し、前記第１の中間変数と前記第２の中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を前記タグとして生成し、前記メッセージと前記乱数と前記タグとを該メッセージの宛先である前記タグ検証装置へ送信し、
前記タグ検証装置は、
前記送信されてきたメッセージに対して前記ハッシュ関数を適用して得られた値を検証用ハッシュ値として生成し、前記メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する前記暗号関数を適用して得られた値を第１の検証用中間変数として生成し、前記送信されてきた乱数と前記検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する前記暗号関数を適用して得られた値を第２の検証用中間変数として生成し、前記第１の検証用中間変数と前記第２の検証用中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を検証用タグとして生成し、前記検証用タグと前記メッセージとともに外部から送信されてきたタグとを比較する、通信システム。
【請求項９】
請求項８記載の通信システムにおいて、
前記タグ生成装置は、前記外部から入力を受付けたメッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を前記ハッシュ値として生成し、
前記タグ検証装置は、前記送信されてきたメッセージに対して前記ハッシュ鍵を有する前記鍵付ハッシュ関数を適用して得られた値を前記検証用ハッシュ値として生成することを特徴とする通信システム。
【請求項１０】
請求項８または９に記載の通信システムにおいて、
前記タグ生成装置は、前記第２の中間変数を生成するとともに、前記ハッシュ値に対して第３の鍵を有する前記暗号関数を適用して得られた値を第３の中間変数として生成し、前記第１の中間変数と前記第２の中間変数と前記第３の中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を前記タグとして生成し、前記メッセージと前記乱数と前記タグとを該メッセージの宛先である前記タグ検証装置へ送信し、
前記タグ検証装置は、前記第２の検証用中間変数を生成するとともに、前記検証用ハッシュ値に対して第３の検証鍵を有する前記暗号関数を適用して得られた値を第３の検証用中間変数として生成し、前記第１の検証用中間変数と前記第２の検証用中間変数と前記第３の検証用中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を検証用タグとして生成することを特徴とする通信システム。
【請求項１１】
請求項８乃至１０のいずれか１項に記載の通信システムにおいて、
前記タグ検証装置は、前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが同じである場合、前記送信されてきたメッセージが正当な送信者から送られたものである旨を示す情報を出力し、前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが異なっている場合、前記送信されてきたメッセージが正当な送信者から送られたものでない旨を示す情報を出力することを特徴とする通信システム。
【請求項１２】
外部から入力を受け付けたメッセージに該メッセージに対する変更の有無を判別するためのタグを付与するタグ生成方法であって、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ処理と、
前記メッセージの入力を外部から受付けた場合、該メッセージと独立な乱数を生成する乱数生成処理と、
前記乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化処理と、
前記乱数と前記ハッシュ値との排他的論理和に対して第２の鍵を有する前記暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化処理と、
前記第１の中間変数と前記第２の中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、前記タグとして生成するタグ生成処理と、
前記メッセージと前記乱数と前記タグとを該メッセージの宛先へ送信する出力処理と、
を有するタグ生成方法。
【請求項１３】
請求項１２記載のタグ生成方法において、
前記ハッシュ処理では、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記ハッシュ値として生成することを特徴とするタグ生成方法。
【請求項１４】
請求項１２または１３記載のタグ生成方法において、
前記マスク付暗号化処理では、前記第２の中間変数を生成するとともに、前記ハッシュ値に対して第３の鍵を有する前記暗号関数を適用して得られた値を第３の中間変数として生成し、
前記タグ生成処理では、前記第１の中間変数と前記第２の中間変数と前記第３の中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記タグとして生成することを特徴とするタグ生成方法。
【請求項１５】
外部から送信されてきたメッセージを該メッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証方法であって、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ処理と、
前記メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化処理と、
前記乱数と前記検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する前記暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化処理と、
前記第１の検証用中間変数と前記第２の検証用中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成処理と、
前記検証用タグと、前記メッセージとともに外部から送信されてきた前記タグとを比較する比較処理と、
を有するタグ検証方法。
【請求項１６】
請求項１５記載のタグ検証方法において、
前記ハッシュ処理では、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記検証用ハッシュ値として生成することを特徴とするタグ検証方法。
【請求項１７】
請求項１５または１６に記載のタグ検証方法において、
前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが同じである場合、前記送信されてきたメッセージが正当な送信者から送られたものである旨を示す情報を出力し、前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが異なっている場合、前記送信されてきたメッセージが正当な送信者から送られたものでない旨を示す情報を出力する出力処理を有することを特徴とするタグ検証方法。
【請求項１８】
請求項１５乃至１７のいずれか１項に記載のタグ検証方法において、
前記マスク付暗号化処理では、前記第２の検証用中間変数を生成するとともに、前記検証用ハッシュ値に対して第３の検証鍵を有する前記暗号関数を適用して得られた値を第３の検証用中間変数として生成し、
前記タグ生成処理では、前記第１の検証用中間変数と前記第２の検証用中間変数と前記第３の検証用中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記検証用タグとして生成することを特徴とするタグ検証方法。
【請求項１９】
外部から入力を受け付けたメッセージに該メッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置に、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ手順と、
前記メッセージの入力を外部から受付けた場合、該メッセージと独立な乱数を生成する乱数生成手順と、
前記乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化手順と、
前記乱数と前記ハッシュ値との排他的論理和に対して第２の鍵を有する前記暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化手順と、
前記第１の中間変数と前記第２の中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、前記タグとして生成するタグ生成手順と、
前記メッセージと前記乱数と前記タグとを該メッセージの宛先へ送信する出力手順とを実行させるためのプログラムを記録した記録媒体。
【請求項２０】
請求項１９記載の記録媒体において、
前記ハッシュ手順では、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記ハッシュ値として生成することを特徴とするプログラムを記録した記録媒体。
【請求項２１】
請求項１９または２０記載の記録媒体において、
前記マスク付暗号化手順では、前記第２の中間変数を生成するとともに、前記ハッシュ値に対して第３の鍵を有する前記暗号関数を適用して得られた値を第３の中間変数として生成し、
前記タグ生成手順では、前記第１の中間変数と前記第２の中間変数と前記第３の中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記タグとして生成することを特徴とするプログラムを記録した記録媒体。
【請求項２２】
外部から送信されてきたメッセージを該メッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証装置に、
前記メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ手順と、
前記メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化手順と、
前記乱数と前記検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する前記暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化手順と、
前記第１の検証用中間変数と前記第２の検証用中間変数との排他的論理和のうちから抽出した前記乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成手順と、
前記検証用タグと、前記メッセージとともに外部から送信されてきた前記タグとを比較する比較手順とを実行させるためのプログラムを記録した記録媒体。
【請求項２３】
請求項２２記載の記録媒体において、
前記ハッシュ手順では、前記メッセージに対してハッシュ鍵を有する鍵付ハッシュ関数を適用して得られた値を、前記検証用ハッシュ値として生成することを特徴とするプログラムを記録した記録媒体。
【請求項２４】
請求項２２または２３に記載の記録媒体において、
前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが同じである場合、前記送信されてきたメッセージが正当な送信者から送られたものである旨を示す情報を出力し、前記比較の結果、前記検証用タグと前記外部から送信されてきたタグとが異なっている場合、前記送信されてきたメッセージが正当な送信者から送られたものでない旨を示す情報を出力する出力手順を前記タグ検証装置にさらに実行させることを特徴とするプログラムを記録した記録媒体。
【請求項２５】
請求項２２乃至２４のいずれか１項に記載の記録媒体において、
前記マスク付暗号化手順では、前記第２の検証用中間変数を生成するとともに、前記検証用ハッシュ値に対して第３の検証鍵を有する前記暗号関数を適用して得られた値を第３の検証用中間変数として生成し、
前記タグ生成手順では、前記第１の検証用中間変数と前記第２の検証用中間変数と前記第３の検証用中間変数との排他的論理和のうちから抽出した前記所定のビット数のビットに含まれる値を、前記検証用タグとして生成することを特徴とするプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、タグ生成装置、タグ検証装置、通信システム、タグ生成方法、タグ検証方法、および、プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
メッセージ認証（Message  Authentication  Code,  MAC）とは、秘密鍵Ｋを知っている特定の者が当該秘密鍵Ｋを用いて計算できるタグＴを、送信するメッセージＭに付与することで、当該メッセージＭの正当性を保証する技術である。【０００３】
例えば、秘密鍵Ｋを共有した２者間の通信において、送信者がメッセージＭとタグＴとを受信者へ送った場合、受信者側では受け取ったメッセージからタグを計算し、計算したタグと受信したタグとを比較する。比較の結果、計算したタグと受信したタグとが一致した場合、当該メッセージＭが正当な送信者から送られたものであると判断できる。一方、計算したタグと受信したタグとが一致しない場合、当該メッセージが正当な送信者から送られたものではないと判断することや、通信の間に第３者による改ざんが行われたことを検知することが可能となる。【０００４】
メッセージ認証の方式には、メッセージＭを送信する第１の通信装置がカウンタなどの状態変数を保持する方式（stateful  MAC）と、状態変数を保持しない方式（stateless  MAC）とがある。さらに、このstateless  MACには、メッセージＭを送信する第１の通信装置がメッセージＭと独立した一様な乱数Ｕを毎回生成することを許す方式（randomized  MAC）と、それ以外の方式（deterministic  MAC）とがある。【０００５】
状態変数もしくは乱数を用いるMACでは、それらの値は、タグＴの生成に用いられるとともに、暗号化されることなくメッセージＭの宛先へ通信路を介して送信される。なお、randomized  MACにて生成されるタグTは、暗号関数をＦ、暗号関数Ｆの鍵をK、メッセージをM、乱数をUでそれぞれ表わした場合、T=Ｆ(K,M,U)と表すことができる。第１の通信装置は、乱数UとメッセージMとタグTとを第２の通信装置へ送信する。メッセージＭの宛先である第２の通信装置は、通信路を介して送信されてきた乱数U'とメッセージM'とタグT'とを受信した場合、第１の通信装置が記憶している秘密鍵Ｋと同じ秘密鍵Kと、受信したメッセージM'および乱数U'とから検証用タグＴ１を求め、検証用タグＴ１と送信されてきたタグT'とを比較することで、受信した乱数U'とメッセージM'とタグT'とが通信路を介して送信されてくる間に変更されたかどうかを判別する。【０００６】
以下では、乱数Ｕのビット数がｎビットであり、タグＴのビット数がｓビット（sは、n以下の正の整数）である場合を例に挙げて説明する。なお、メッセージＭは、任意のビット数のビットを有するバイナリ系列（ビット列）であるが、以下では、理解を容易とするためメッセージＭのビット数の最大値をLである場合を例に挙げる。【０００７】
randomized  MACでは、乱数Ｕのビット数ｎと同じビット数の任意のデータを入力して乱数Ｕのビット数ｎと同じビット数の暗号化された当該データを出力する（以下、「ｎビット入出力」という）鍵付の暗号関数Ｆと、可変長のデータを入力して乱数Ｕのビット数ｎと同じビット数のハッシュ値を出力する鍵付のハッシュ関数Hとを用いて、タグTを、以下の式１として算出する。【０００８】
【数１】
0005447510.tif 000002
ここで、式１に示したKeは暗号関数Fの鍵であり、Khはハッシュ関数Hの鍵である。また、記号「＋」は、ビットごとの排他的論理和を示す演算記号である。また、chop(x)は、xのうちから所定のビット数ｓのビットに含まれる値を抽出するための関数である。【０００９】
なお、鍵付の暗号関数Fは、疑似ランダム関数と呼ばれる十分安全な関数である。鍵付の暗号関数Fとしては、例えば、AES（Advanced  Encryption  Standard）などのブロック暗号が一般的に用いられる。【００１０】
また、ハッシュ関数Hには、それぞれ異なる２つのメッセージM、M'が入力された場合に、各メッセージM、M'のそれぞれに対して出力される各ハッシュ値が互いに一致する確率Ｐｒが非常に小さなことが求められる。すなわち、ハッシュ関数Hには、十分小さな任意の正数eについて、任意のビット数L以下である互いに異なるメッセージM、M'の対（M,M')に対して、以下の式２が成立することが求められる。【００１１】
【数２】
0005447510.tif 000003
なお、任意の正数eは、ハッシュ関数Hの出力サイズの逆数より小さくなることは不可能であるため、この場合、正数eの下限値は2(-n)となる。なお、正数ｅは、ハッシュ値Ｓの算出対象となるメッセージＭのビット数の最大値Lをパラメータとして取り得るため、e(L)と記述するのが適当である。しかし、以下では、メッセージＭのビット数の最大値Lを定数として扱う場合を例に説明するとともに、e(L)をeと略記する。このような関数は、「e-almostユニバーサルハッシュ関数」と呼ばれ、有限体上の多項式演算などの代数的構成方法により効率的に構成することが可能である。なお、このように構成されたrandomized  MACは、randomized  Carter-Wegman  MAC  (randomized  CW-MAC）と呼ばれている。【００１２】
以下に、randomized  MACの安全性の一般的な定義について説明する。randomized  MACにおける攻撃のシナリオは、タグ生成フェーズと、偽造フェーズとの２つのフェーズに分かれる。まず、タグ生成フェーズにおいて、攻撃を行う第３者が、第１の通信装置および第２の通信装置と異なる第３の通信装置を用いて選択可能な任意のメッセージMについて第１の通信装置から送信されてきた乱数UとメッセージMとタグTとを含むデータをQmac個取得する。つぎに、偽造フェーズにおいて、その第３者は、第３の通信装置を用いて、タグ生成フェーズで取得したQmac個のデータ（乱数UとメッセージMとタグT）に基づいて、乱数U'とメッセージM'とタグT'とを含むQver個の偽造データを生成して第２の通信装置へ送信する。そして、第２の通信装置が、第３者の通信装置から送信されてきた偽造データ（乱数U'とメッセージM'とタグT')のうちの少なくとも１つの偽造データが第１の通信装置から送信された変更されていないデータである判別した場合、攻撃が成功したとみなされる。【００１３】
ここでいう偽造データとは、タグ生成フェーズにて、第３者が観測した第１の通信装置が送信したデータ（乱数UとメッセージMとタグT）と異なっているデータであれば、どのようなデータでもよい。例えば、タグ生成フェーズにて観測したデータ（乱数UとメッセージMとタグT）に含まれる乱数Uのみを別の乱数U'に変更した（乱数U'とメッセージMとタグT）を、偽造データとして生成してもよい。このような安全性の概念は強偽造不可能性と呼ばれる。なお、安全性の基準として、偽造データに含まれるメッセージがタグ生成フェーズで観測されたメッセージMと必ず異なることを要求した場合には、弱偽造不可能性と呼ばれる。【００１４】
ハッシュ関数Hと鍵付の暗号関数Fとを用いたrandomized  CW-MACの強偽造不可能性の意味での偽造成功確率については、以下の式３に示す関係が成り立つ。【００１５】
【数３】
0005447510.tif 000004
ここで、式３の左辺に示したSuc(Qmac,Qver,time)は、タグ生成フェーズにおいて第３者が送信されたデータをQmac個取得し、偽造フェーズにてQver個の偽造データを生成し、全体での計算量がtimeである場合における偽造成功確率を表す。また、式３の右辺に示したSec(F,Qmac+Qver,time')は、第３者が、計算量がtime'であるような選択平文攻撃により鍵付の暗号関数Fと乱数Ｕを生成するための真のランダム関数との判別をブラックボックスの状態で「Qmac+Qver」回行った場合の最大利得（判別成功確率−（1/2））を表す。なお、計算量time'は、計算量timeの多項式オーダである。【００１６】
上述した式３から、randomized  CW-MACにおいて偽造の確率を十分小さくするためには、鍵付関数Fが「Qmac+Qver」回の選択平文攻撃に対して十分な安全性を持つ疑似ランダム関数であることと、第３者が取得するデータの個数Qmacが2(n/2)と比べて非常に小さいことと、第３者が生成した偽造データの個数Qverが正数eおよび1/2sのそれぞれと比べて非常に小さいこととの３つの条件が必要となることが分かる。【００１７】
攻撃に対する安全性を向上させる上で特に問題となる条件は、これらのうち２番目の条件である。なぜならば、第３者が取得するデータ（乱数UとメッセージMとタグT）の個数Qmacは、第３者が静的に通信路を観測することにより非常に大きくすることができるからである。一方、第３者が生成した偽造データの個数Qverは、偽造データを受信した第２の通信装置にてメッセージ認証の失敗が多発した時点で通信路に妨害があることを認識することが可能であることから、Qmacと比べて非常に小さな値であることが一般的である。また、Qmacの項はべき数が「２」であるのに対して、偽造データの個数Qverの項はべき数が「１」である。そのため、乱数Ｕのビット数ｎとタグＴのビット数ｓとが正数ｅの逆数と同じ（つまり、n=1/e=s）である場合、Qverの項が増大する際、Qmacよりも非常に緩やかに増大する。上記の考察から、現実の場面では、Qmacは、MACの鍵の寿命と一致すると考えられる。すなわち、上述したrandomized  CW-MACでは、メッセージＭを2  (n/2)回よりも非常に小さな回数送信した後、攻撃の有無に関わらず、タグＴ生成用の鍵Ｋの更新を行わなければならない。この性質のことを、ある１つの鍵Ｋでメッセージを送信することが可能な回数の最大値である鍵寿命（Key  Life  Time,  以下、「KLT」と略す）が「n/2」であると呼ぶこととする。なお、2(n/2)回というQmacの上限値は、nについてのバースデーバウンドとも呼ばれる。【００１８】
このKLTをn/2よりも大きくするための方法として、非特許文献１に開示されているようなMACRX方法が考えられている。このMACRX方法とは、乱数Ｕのビット数をビット数ｎよりも増やすものである。例えば、乱数Ｕのビット数が「3×n」ビットであり、タグＴのビット数がnビットである場合、MACRX方法にて生成されるタグＴは、以下の式４で表わされる。【００１９】
【数４】
0005447510.tif 000005
なお、式４に示した乱数U1、U2、U3のそれぞれは、ビット数がnビットの独立な一様乱数である。そのため、MACRX方法においては、第１の通信装置は、乱数U1、U2、U3  とメッセージMとタグTとを第２の通信装置へ送信する。ただし、このままでは乱数U1、U2、U3を並び替えるだけで偽造が成功してしまうため、弱い意味での偽造不可能性しか保証されない。MACRX方法にて強偽造不可能性を保証するためには、乱数U1、U2、U3に適当な符号化を施した後、これらを送信する必要がある。【００２０】
なお、非特許文献１によると、MACRX方式の弱偽造不可能性は、以下の式５で表わすことができる。【００２１】
【数５】
0005447510.tif 000006
ここで、式５に示したd(3,n)は実際には小さな値であるため、KLTはほぼnとなることがわかる。なお、MACRX方式においては、乱数Ｕのビット数を2nビット以下とした場合、KLTは「n/2」のままであることも示されている。【００２２】
また、非特許文献２には、randomized  MACにおいて、ハッシュ関数Hへ入力するデータのうちに乱数Ｕを含める形式、すなわち、以下の式６で表わされるようなタグTを生成する方式が開示されている。【００２３】
【数６】
0005447510.tif 000007
なお、式６に示した記号「||」は、乱数ＵとメッセージＭとの連結を示す。しかし、非特許文献２に開示された技術においては、互いに異なるメッセージのそれぞれにハッシュ関数Hを適用した場合にそれぞれ得られるハッシュ値が互いに衝突する確率eが、各メッセージのビット数の最大値Lが増加することに伴って大きくなってしまうことを抑制するために、乱数Ｕにもハッシュ関数Ｈを適用している。そのため、この技術においては、KLTを「n/2」よりも大きくすることはできず、ＫＬＴは「n/2」のままである。【００２４】
また、乱数に代えてカウンタなどの状態変数を用い、かつ十分よいユニバーサルハッシュ関数とnビット入出力の暗号関数Ｆとを用いてタグＴを生成した際、Carter-Wegman  MACのKLTはほぼnとなることが、非特許文献３や特許文献１に開示されている。しかし、この場合、メッセージＭを送信する通信装置がカウンタなどの状態変数を保持しておく必要がある。そのため、これらの技術においては、同じ鍵を用いる複数のデバイスが存在する場合、デバイス間で相互に同期をとることが必要となり、不都合が生じる。【００２５】
また、乱数もカウンタも用いないdeterministic  MACにおいて、KLTをほぼnとすることができる方式が非特許文献４に開示されている。しかし、この技術においては、暗号関数Ｆへ入力されるデータのビット数が2nビット以上である。そのため、この技術は、前提条件が異なるMACRXやrandomized  Carter-Wegman  MACに適用することはできないという問題点がある。【００２６】
なお、上述した特許文献１および非特許文献１〜４のそれぞれは、以下の通りである。
【先行技術文献】
【特許文献】
【００２７】
【特許文献１】米国特許第５７５７９１３号明細書
【非特許文献】
【００２８】
【非特許文献１】M.  Bellare,  O.  Goldreich,  and  H.  Krawczyk,  Stateless  evaluation  of  pseudorandom  functions:  Security  beyond  the  birthday  barrier,  Advances  in  Cryptology  -  CRYPTO  '99,  19th  Annual  International  Cryptology  Conference,  Santa  Barbara,  California,  USA,  August  15-19,  1999,  Proceedings.  Lecture  Notes  in  Computer  Science  1666  Springer  1999,  pp.  270-287.
【非特許文献２】Y.  Dodis  and  K.  Pietrzak,  Improving  the  Security  of  MACs  Via  Randomized  Message  Preprocessing,  Fast  Software  Encryption,  14th  International  Workshop,  FSE  2007,  Luxembourg,  Luxembourg,  March  26-28,  2007,  Revised  Selected  Papers.  Lecture  Notes  in  Computer  Science  4593  Springer  2007,  pp.  414-433.
【非特許文献３】D.  J.  Bernstein.  Stronger  Security  Bounds  for  Wegman-  Carter-  Shoup  Authenticators.  Advances  in  Cryptology-  EUROCRYPT  '05,  LNCS  3494,  pp.  164-180,  2005.
【非特許文献４】K.  Yasuda,  A  One-Pass  Mode  of  Operation  for  Deterministic  Message  Authentication-  Security  beyond  the  Birthday  Barrier,  Fast  Software  Encryption,  FSE'08,  LNCS  5086,  pp.  316-333,  2008.
【発明の概要】
【００２９】
上述したrandomized  Carter-Wegman  MACを用いた技術では、乱数のビット数をnビットとした場合、１つの鍵Ｋでメッセージを送信することが可能な最大メッセージ送信回数を2(n/2)回よりも十分小さな値としなければならないという問題点がある。
【００３０】
また、非特許文献１に開示された技術においては、最大メッセージ送信回数を2n回とすることはできるが、乱数Ｕのビット数が3nビット以上であることが必要となる。そのため、メッセージＭを送信する通信装置が乱数Ｕを生成するための処理負荷が大きくなるとともに、送信する乱数UとメッセージMとタグTとに付随するデータ量も増大してしまうという問題点がある。
【００３１】
本発明の目的の一つは、上述した課題を解決するタグ生成装置、タグ検証装置、通信システム、タグ生成方法、タグ検証方法、および、プログラムを記録した記録媒体を提供することである。
【００３２】
本発明の一側面のタグ生成装置は、外部から入力を受け付けたメッセージにこのメッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置であって、メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ部と、メッセージの入力を外部から受付けた場合、メッセージと独立な乱数を生成する乱数生成部と、乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化部と、乱数とハッシュ値との排他的論理和に対して第２の鍵を有する暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化部と、第１の中間変数と第２の中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、タグとして生成するタグ生成部と、メッセージと乱数とタグとをメッセージの宛先へ送信する出力部とを有する。
【００３３】
本発明の一側面のタグ検証装置は、外部から送信されてきたメッセージをこのメッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証装置であって、メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ部と、メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化部と、乱数と検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化部と、第１の検証用中間変数と第２の検証用中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成部と、検証用タグと、メッセージとともに外部から送信されてきたタグとを比較する比較部とを有する。
【００３４】
本発明の一側面の通信システムは、外部から入力を受付けたメッセージにこのメッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置と、メッセージの送信元から送信されてきたメッセージをタグを用いて検証するタグ検証装置とを有する通信システムであって、タグ生成装置は、メッセージに対して所定のハッシュ関数を適用して得られた値をハッシュ値として生成し、メッセージの入力を外部から受付けた場合、メッセージと独立な乱数を生成し、乱数に対して第１の鍵を有する暗号関数を適用して得られた値を第１の中間変数として生成し、乱数とハッシュ値との排他的論理和に対して第２の鍵を有する暗号関数を適用して得られた値を第２の中間変数として生成し、第１の中間変数と第２の中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値をタグとして生成し、メッセージと乱数とタグとをメッセージの宛先であるタグ検証装置へ送信し、タグ検証装置は、送信されてきたメッセージに対してハッシュ関数を適用して得られた値を検証用ハッシュ値として生成し、メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を第１の検証用中間変数として生成し、送信されてきた乱数と検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する暗号関数を適用して得られた値を第２の検証用中間変数として生成し、第１の検証用中間変数と第２の検証用中間変数との排他的論理和のうちから抽出した所定のビット数のビットに含まれる値を検証用タグとして生成し、検証用タグとメッセージとともに外部から送信されてきたタグとを比較する。
【００３５】
本発明の一側面のタグ生成方法は、外部から入力を受け付けたメッセージにこのメッセージに対する変更の有無を判別するためのタグを付与するタグ生成方法であって、メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ処理と、メッセージの入力を外部から受付けた場合、メッセージと独立な乱数を生成する乱数生成処理と、乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化処理と、乱数とハッシュ値との排他的論理和に対して第２の鍵を有する暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化処理と、第１の中間変数と第２の中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、タグとして生成するタグ生成処理と、メッセージと乱数とタグとをメッセージの宛先へ送信する出力処理とを有する。
【００３６】
本発明の一側面のタグ検証方法は、外部から送信されてきたメッセージをこのメッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証方法であって、メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ処理と、メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化処理と、乱数と検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化処理と、第１の検証用中間変数と第２の検証用中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成処理と、検証用タグと、メッセージとともに外部から送信されてきたタグとを比較する比較処理とを有する。
【００３７】
本発明の一側面の記録媒体は、コンピュータに実行させるプログラムを記録した記録媒体であって、外部から入力を受け付けたメッセージにこのメッセージに対する変更の有無を判別するためのタグを付与するタグ生成装置に、メッセージに対して所定のハッシュ関数を適用して得られた値を、ハッシュ値として生成するハッシュ手順と、メッセージの入力を外部から受付けた場合、メッセージと独立な乱数を生成する乱数生成手順と、乱数に対して第１の鍵を有する暗号関数を適用して得られた値を、第１の中間変数として生成する乱数暗号化手順と、乱数とハッシュ値との排他的論理和に対して第２の鍵を有する暗号関数を適用して得られた値を第２の中間変数として生成するマスク付暗号化手順と、第１の中間変数と第２の中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、タグとして生成するタグ生成手順と、メッセージと乱数とタグとをメッセージの宛先へ送信する出力手順とを実行させるプログラムを記録したものである。
【００３８】
本発明の一側面の記録媒体は、コンピュータに実行させるプログラムを記録した記録媒体であって、外部から送信されてきたメッセージをこのメッセージに対する変更の有無を判別するためのタグを用いて検証するタグ検証装置に、メッセージに対して所定のハッシュ関数を適用して得られた値を、検証用ハッシュ値として生成するハッシュ手順と、メッセージとともに送信されてきた乱数に対して第１の検証鍵を有する暗号関数を適用して得られた値を、第１の検証用中間変数として生成する乱数暗号化手順と、乱数と検証用ハッシュ値との排他的論理和に対して第２の検証鍵を有する暗号関数を適用して得られた値を第２の検証用中間変数として生成するマスク付暗号化手順と、第１の検証用中間変数と第２の検証用中間変数との排他的論理和のうちから抽出した乱数のビット数以下である所定のビット数のビットに含まれる値を、検証用タグとして生成するタグ生成手順と、検証用タグと、メッセージとともに外部から送信されてきたタグとを比較する比較手順とを実行させるプログラムを記録したものである。
【図面の簡単な説明】
【００３９】
【図１】図１は本発明の実施形態１に従った通信システムの構成を示す図である。
【図２】図２は図１に示したタグ生成装置の構成を示す図である。
【図３】図３は図２に示したハッシュ部と乱数暗号化部とマスク付暗号化部とタグ生成部との構成の一形態を示す図である。
【図４】図４は図１に示したタグ検証装置の構成を示す図である。
【図５】図５は図４に示したハッシュ部と乱数暗号化部とマスク付暗号化部とタグ生成部との構成の一形態を示す図である。
【図６】図６は実施形態１のタグ生成装置がタグを生成する動作を示すフローチャートである。
【図７】図７は実施形態１のタグ検証装置が外部から送信されてきたタグを検証する動作を示すフローチャートである。
【図８】図８は実施形態２のタグ生成装置が有するハッシュ部と乱数暗号化部とマスク付暗号化部とタグ生成部との構成の一形態を示す図である。
【図９】図９は実施形態２のタグ検証装置が有するハッシュ部と乱数暗号化部とマスク付暗号化部とタグ生成部との構成の一形態を示す図である。
【発明を実施するための形態】
【００４０】
（実施形態１）
以下、本発明の実施形態１に従った通信システム（タグ生成装置、タグ検証装置、タグ生成方法、タグ検証方法およびプログラムを含む）を説明する。
【００４１】
まず、本実施形態の通信システムの構成を説明する。図１に示すように、この通信システムは、通信路３を介して互いに通信可能に接続されたタグ生成装置１とタグ検証装置２とから構成されている。
【００４２】
タグ生成装置１は、タグ検証装置２へ任意のメッセージＭを送信する。なお、タグ生成装置１は、メッセージＭを送信する際、そのメッセージＭに対する変更の有無を判別するためのタグＴを生成し、メッセージＭとともにタグＴを送信する。
【００４３】
タグ検証装置２は、通信路３を介して送信されてきたメッセージMrを、そのメッセージＭｒとともに送信されてきたタグTrを用いて認証する。
【００４４】
つぎに、図１に示したタグ生成装置１の構成について、図２を参照して詳細に説明する。
【００４５】
図２に示すように、実施形態１のタグ生成装置１は、入力部１１と、ハッシュ部１２と、乱数生成部１３と、乱数暗号化部１４と、マスク付暗号化部１５と、タグ生成部１６と、出力部１７とから構成される。
【００４６】
入力部１１は、メッセージMの入力を外部から受付けた場合、その旨を乱数生成部１３へ通知する。また、入力部１１は、そのメッセージＭをハッシュ部１２と出力部１７とへ出力する。入力部１１の一例としては、文字の入力が可能なキーボードなどの任意の入力装置などが挙げられる。
【００４７】
ハッシュ部１２は、入力部１１から出力されてきたメッセージMへ「所定のハッシュ関数Ｈ」を適用して得られた値を、ハッシュ値Ｓとして生成する。そして、ハッシュ部１２は、そのハッシュ値Ｓを、マスク付暗号化部１５へ出力する。
【００４８】
この説明例では、ハッシュ部１２は、所定のハッシュ関数Ｈとして、ハッシュ鍵Ｋｈを有する鍵付ハッシュ関数HをメッセージＭへ適用することにより、ハッシュ値Ｓを生成する。
【００４９】
ここで、「ハッシュ鍵Ｋｈ」とは、メッセージＭに付随するハッシュ値Ｓを生成する際、そのハッシュ値Ｓのビット数の最大値を、メッセージＭのブロック長と同じビット数とするための情報である。
【００５０】
なお、ハッシュ関数Hの鍵がハッシュ鍵Khである場合、メッセージＭに対してハッシュ関数Ｈを適用して生成されるハッシュ値Ｓは、S=H(Kh,M)となる。ここで、ハッシュ関数Hは、ハッシュ値Ｓの生成対象となるメッセージＭの集合に対して、十分小さい任意の正数eについて「e-almost  XOR（eXclusive  OR）ユニバーサル」であることが求められる。
【００５１】
ここで、e-almost  XORユニバーサルとは、それぞれ異なる２つの任意のメッセージM、M'に対してハッシュ関数Ｈを適用した場合に、メッセージMに付随して生成されるハッシュ値がｙとなり、かつメッセージM'に付随して生成されるハッシュ値がy'となる確率Pr[H(Kh,M)=y,  H(Kh,M')=y']が、どのようなyとy'についても正数e以下となることを指す。なお、確率Pr[H(Kh,M)=y,  H(Kh,M')=y']に付随する確率空間は、ハッシュ鍵Khによって定義される。なお、このような性質を有する鍵付関数はe-almost  XORユニバーサルハッシュ関数と呼ばれ、例えば、有限体上の多項式で実現可能である。
【００５２】
具体例として、ハッシュ関数Ｈのハッシュ鍵Khのビット数がｎビットである場合に、ハッシュ部１２が、ビット数がn×LビットであるメッセージMに対してハッシュ関数Ｈを適用することによりハッシュ値Ｓを生成する動作について説明する。この場合、ハッシュ部１２は、ビット数がそれぞれｎビットであるL個のブロックM[0],M[1],・・・,M[L]にメッセージＭを分割する。その後、ハッシュ部１２は、以下の式７に従ってＹ［Ｌ］を算出し、Y[L]をハッシュ値Ｓとして出力する。
【００５３】
【数７】
0005447510.tif 000008
ここで、式７に示したGFmul(Y[i-1]+M[i],Kh)は、「Y[i-1]+M[i]」とハッシュ鍵Khとを有限体GF(2n)上の要素とした乗算である。
【００５４】
なお、ハッシュ部１２は、文献Ａ（S.  Halevi  and  H.  Krawczyk,  MMH:Software  Message  Authentication  in  the  Gbit/second  rates,  Fast  Software  Encryption,  4th  Internatioanl  Workshop,  FSE  '97,  Lecture  Notes  in  Computer  Science;  Vol.  1267,  Feb.  1997）に開示されているような具体的な実装環境に特化した算術乗算を行うための関数をメッセージＭに適用することにより、ハッシュ値Ｓを生成してもよい。
【００５５】
あるいは、ハッシュ部１２は、計算量的なXORユニバーサルハッシュ関数をメッセージMに適用することにより、ハッシュ値Ｓを生成してもよい。ここで、XORユニバーサルハッシュ関数は、ブロック暗号などの暗号関数Ｆを用いて構成される関数であり、暗号関数Ｆの計算量的安全性に基づいて出力ペアの確率の最大値が非常に小さな値以下となるように抑制することができるという特徴を有する。なお、XORユニバーサルハッシュ関数を用いたメッセージ認証方式の一例としては、CBC-MAC（Cipher  Block  Chaining  Message  Authentication  Code）などがある。ビット数がＬ×nビットであるメッセージMに付随するハッシュ値ＳをCBC-MACを用いて生成する場合、ハッシュ部１２は、ビット数がそれぞれｎビットであるL個のブロックM[0],M[1],…,M[L]にメッセージＭを分割する。そして、ハッシュ部１２は、n-bitブロック暗号Eを用いて、以下の式８に従ってY[Ｌ]を算出し、Y[L]をハッシュ値Ｓとして出力とする。
【００５６】
【数８】
0005447510.tif 000009
また、ハッシュ部１２は、文献Ｂ（P.  Rogaway.  Efficient  Instantiations  of  Tweakable  Blockciphers  and  Refinements  to  Modes  OCB  and  PMAC.  Advances  in  Cryptology-  ASIACRYPT'04.  LNCS  3329,  pp.  16-31,  2004,）に開示されているような並列実行可能なPMAC（Parallelizable  MAC）などをメッセージMに適用することによりハッシュ値Ｓを生成することも可能である。メッセージＭに対するパディングが不要である場合、ハッシュ部１２は、PMACは、以下の式９に従ってY[L]を算出し、Y[L]をハッシュ値Ｓとして出力する。
【００５７】
【数９】
0005447510.tif 000010
なお、CBC-MACやPMACそのものは、上述したようにメッセージＭと独立な乱数Ｕを毎回生成することを許可しないdeterministic  MACであり、約2(n/2)回の選択平文攻撃により偽造データを生成することが可能である。しかし、本実施形態では、ハッシュ関数ＨがXORユニバーサル性を有しているハッシュ関数であれば、ハッシュ部１２が、任意のハッシュ関数Ｈを用いてハッシュ値Ｓを生成してもよい。
【００５８】
また、ハッシュ部１２は、暗号学的ハッシュ関数をベースとした、文献Ｃ（M.  Bellare,  R.  Canetti,  and  H.  Krawczyk,  Keyed  Hash  Functions  and  Message  Authentication,  Proceedings  of  Crypto'96,  LNCS  1109,  pp.  1-15.）に記載されているようなHMAC（Keyed-Hashing  for  Message  Authentication  code）などをメッセージMに適用することによりハッシュ値Ｓを生成することも可能である。
【００５９】
乱数生成部１３は、メッセージMの入力を外部から受付けた旨が入力部１１から通知された場合、そのメッセージMと独立したビット数がｎビットの乱数Uを生成する。そして、乱数生成部１３は、乱数Ｕを、乱数暗号化部１４とマスク付暗号化部１５とへ出力する。
【００６０】
なお、乱数生成部１３が乱数Ｕを生成する方法は、十分高いエントロピーを有する乱数Ｕを生成可能な方法であれば任意である。例えば、熱雑音などの物理現象を利用して乱数Ｕを生成する方法でもよい。また、例えば、汎用PC（Personal  Computer）のOS（Operating  System）に付属されているような入力部１１が使用者から入力を受付けたデータに基づいて乱数Ｕを生成する方法でもよい。
【００６１】
乱数暗号化部１４は、乱数生成部１３から出力されてきた乱数Uを、「第１の鍵Ｋｅ１」を有する暗号関数Fを用いて暗号化することにより、ビット数がｎビットの第１の中間変数Vを生成する。そして、乱数暗号化部１４は、第１の中間変数Ｖをタグ生成部１６へ出力する。
【００６２】
ここで、「第１の鍵Ｋｅ１」とは、乱数Ｕのビット数と同じビット数の第１の中間変数Ｖを生成するための情報である。また、暗号関数F  の例としては、n-bitブロック暗号や、鍵付きの暗号学的ハッシュ関数などが挙げられる。
【００６３】
マスク付暗号化部１５は、乱数生成部１３から出力されてきた乱数Uと、ハッシュ部１２から出力されてきたハッシュ値Sとの排他的論理和を算出する。そして、マスク付暗号化部１５は、乱数Uとハッシュ値Ｓとの排他的論理和を第２の鍵Ｋｅ２を有する暗号関数Fで暗号化した値を、第２の中間変数Wとして生成する。そして、マスク付暗号化部１５は、第２の中間変数Ｗをタグ生成部１６へ出力する。
【００６４】
ここで、「第２の鍵Ｋｅ２」とは、乱数Ｕとハッシュ値Sとの排他的論理和のビット数と同じビット数の第２の中間変数Ｗを生成するための情報である。
【００６５】
また、マスク付暗号化部１５は、ハッシュ部１２から出力されてきたハッシュ値Sを第３の鍵Ｋｅ３を有する暗号関数Fを用いて暗号化した値を、第３の中間変数Zとして生成する。そして、マスク付暗号化部１５は、第３の中間変数Zをタグ生成部１６へ出力する。
【００６６】
ここで、「第３の鍵Ｋｅ３」とは、ハッシュ値Sのビット数と同じビット数の第３の中間変数Ｚを生成するための情報である。
【００６７】
なお、乱数暗号化部１４が第１の中間変数Ｖの生成に用いる暗号関数Ｆと、マスク付暗号化部１５が第２の中間変数Ｗおよび第３の中間変数Ｚの生成に用いる暗号関数Ｆとは互いに同じである。また、マスク付暗号化部１５が用いる第２の鍵Ｋｅ２と第３の鍵Ｋｅ３と、乱数暗号化部１４が用いる第１の鍵Ｋｅ１とは、同じでもよく異なっていてもよい。
【００６８】
タグ生成部１６は、乱数暗号化部１４から出力されてきた第１の中間変数Vと、マスク付暗号化部１５から出力されてきた第２の中間変数Wと第３の中間変数Zとの排他的論理和を算出する。そして、タグ生成部１６は、第１の中間変数Vと第２の中間変数Wと第３の中間変数Zとの排他的論理和のうちから抽出した「所定のビット数ｓのビットに含まれる値」を、タグTとして生成する。なお、「所定のビット数ｓ」は、乱数Ｕのビット数ｎ以下である。そして、タグ生成部１６は、タグＴを、出力部１７へ出力する。
【００６９】
なお、所定のビット数ｓのビットに含まれる値の抽出方法は、任意であり、例えば、第１の中間変数Vと第２の中間変数Wと第３の中間変数Zとの排他的論理和のうち最上位からｓ個のビットに含まれる値を抽出してもよい。
【００７０】
出力部１７は、乱数生成部１３から出力されてきた乱数Uと、タグ生成部１６から出力されてきたタグTと、入力部１１から出力されてきたメッセージMとを連結する。そして、出力部１７は、乱数ＵとタグＴとメッセージＭとを連結したデータを、そのメッセージＭの宛先であるタグ検証装置２へ送信する。なお、出力部１７は、連結した乱数ＵとタグＴとメッセージＭとを、コンピュータディスプレイなどの表示装置やプリンタなどへ出力してもよい。
【００７１】
なお、図２に示したハッシュ部１２と乱数暗号化部１４とマスク付暗号化部１５とタグ生成部１６とは、図３に示すような構成の一形態で実現することが可能である。
【００７２】
つぎに、タグ検証装置２の構成について、図４を参照して説明する。なお、図４は、実施形態１のタグ検証装置２の構成を示すブロック図である。
【００７３】
図４に示すように、タグ検証装置２は、入力部２１と、ハッシュ部２２と、乱数暗号化部２３と、マスク付暗号化部２４と、タグ生成部２５と、比較部２６と、出力部２７とから構成される。
【００７４】
入力部２１は、タグ生成装置１を含む任意の送信元から通信路３を介して送信されてきたメッセージMrと乱数ＵｒとタグTrとを連結したデータを受信する。
【００７５】
そして、入力部２１は、メッセージMrをハッシュ部２２へ出力する。また、入力部２１は、乱数Ｕｒを乱数暗号化部２３へ出力する。また、入力部２１は、タグTrを比較部２６へ出力する。なお、入力部２１は、タグ生成装置１から送信されてきたメッセージMrと乱数ＵｒとタグTrとの入力を外部から受け付けるキーボードなどの任意の入力装置でもよい。
【００７６】
ハッシュ部２２は、入力部２１から出力されてきたメッセージMrへ所定のハッシュ関数Hを適用して得られた値を、検証用ハッシュ値Ｓ１として生成する。そして、ハッシュ部２２は、検証用ハッシュ値Ｓ１を、マスク付暗号化部２４へ出力する。
【００７７】
本実施形態では、ハッシュ部２２は、所定のハッシュ関数Hとして、ハッシュ鍵Ｋｈを有する鍵付ハッシュ関数HをメッセージＭｒへ適用することにより、検証用ハッシュ値Ｓ１を生成する。
【００７８】
なお、ハッシュ部２２が検証用ハッシュ値Ｓ１の生成に用いるハッシュ関数Ｈおよびハッシュ鍵Ｋｈと、ハッシュ部１２がハッシュ値Ｓの生成に用いるハッシュ関数Ｈおよびハッシュ鍵Ｋｈとは互いに同じである。
【００７９】
乱数暗号化部２３は、入力部２１から出力されてきた乱数Ｕｒを第１の検証鍵Kv1を有する暗号関数Fで暗号化してビット数がｎビットの第１の検証用中間変数V１を生成する。そして、乱数暗号化部２３は、第１の検証用中間変数Ｖ１をタグ生成部２５へ出力する。
【００８０】
ここで、「第１の検証鍵Ｋｖ１」とは、乱数Ｕｒのビット数と同じビット数の第１の検証用中間変数Ｖ１を生成するための情報である。
【００８１】
なお、乱数暗号化部２３が乱数Ｕｒの暗号化に用いる暗号関数Ｆおよび第１の検証鍵Kv1と、乱数暗号化部１４が乱数Ｕの暗号化に用いる暗号関数Ｆおよび第１の鍵Ｋｅ１とは互いに同じである。
【００８２】
マスク付暗号化部２４は、入力部２１から出力されてきた乱数Ｕｒと、ハッシュ部２２から出力されてきた検証用ハッシュ値Ｓ１との排他的論理和を算出する。そして、マスク付暗号化部２４は、乱数Ｕｒと検証用ハッシュ値Ｓ１との排他的論理和を第２の検証鍵Ｋｖ２を有する暗号関数Fで暗号化した値を、第２の検証用中間変数W１として生成する。そして、マスク付暗号化部２４は、第２の検証用中間変数Ｗ１をタグ生成部２５へ出力する。
【００８３】
ここで、「第２の検証鍵Ｋｖ２」とは、乱数Ｕｒと検証用ハッシュ値Ｓ１との排他的論理和のビット数と同じビット数の第２の検証用中間変数Ｗ１を生成するための情報である。
【００８４】
また、マスク付暗号化部２４は、ハッシュ部２２から出力されてきた検証用ハッシュ値S１を第３の検証鍵Ｋｖ３を有する暗号関数Fを用いて暗号化した値を、第３の検証用中間変数Ｚ１として生成する。そして、マスク付暗号化部２４は、第３の検証用中間変数Z１をタグ生成部２５へ出力する。
【００８５】
ここで、「第３の検証鍵Ｋｖ３」とは、検証用ハッシュ値Ｓ１のビット数と同じビット数の第３の検証用中間変数Ｚ１を生成するための情報である。
【００８６】
なお、マスク付暗号化部２４が、第２の検証用中間変数W１および第３の検証用中間変数Ｚ１の生成に用いる暗号関数Ｆと第２の検証鍵Ｋｖ２と第３の検証鍵Ｋｖ３と、マスク付暗号化部１５が第２の中間変数Wおよび第３の中間変数Ｚの生成に用いる暗号関数Ｆと第２の鍵Ｋｅ２と第３の鍵Ｋｅ３とは互いに同じである。
【００８７】
タグ生成部２５は、乱数暗号化部２３から出力されてきた第１の検証用中間変数V１と、マスク付暗号化部２４から出力されてきた第２の検証用中間変数W１と第３の検証用中間変数Z１との排他的論理和を算出する。そして、タグ生成部２５は、第１の検証用中間変数V１と第２の検証用中間変数W１と第３の検証用中間変数Z１との排他的論理和のうちから抽出した所定のビット数ｓのビットに含まれる値を、検証用タグT１として生成する。なお、「所定のビット数ｓ」は、乱数Ｕｒのビット数ｎ以下である。そして、タグ生成部２５は、検証用タグＴ１を、比較部２６へ出力する。
【００８８】
比較部２６は、タグ生成部２５から出力されてきた検証用タグＴ１と、入力部２１から出力されてきたタグＴｒとを比較し、その比較結果を出力部２７へ出力する。
【００８９】
出力部２７は、比較部２６による比較の結果、検証用タグＴ１とタグＴｒとが同じである場合、メッセージＭｒが正当な送信者から送られたものである旨を示す情報を出力する。
【００９０】
また、出力部２７は、比較部２６による比較の結果、検証用タグＴ１とタグＴｒとが異なっている場合、メッセージＭｒが正当な送信者から送られたものでない旨を示す情報を出力する。なお、出力部２７の例としては、コンピュータディスプレイやプリンタなどが挙げられる。
【００９１】
なお、図４に示したハッシュ部２２と乱数暗号化部２３とマスク付暗号化部２４とタグ生成部２５とは、図５に示すような構成の一形態で実現することが可能である。
【００９２】
つぎに、上記構成を有する実施形態１のタグ生成装置１がタグＴを生成する動作を、図６を参照して説明する。
【００９３】
図６に示すステップ４１にて、まず、入力部１１は、メッセージMの入力を外部から受付ける。すると、入力部１１は、メッセージMの入力を外部から受付けた旨を乱数生成部１３へ通知する。また、入力部１１は、そのメッセージＭをハッシュ部１２と出力部１７とへ出力する。
【００９４】
すると、ステップ４２にて、ハッシュ部１２は、入力部１１から出力されてきたメッセージMへハッシュ鍵Ｋｈを有する鍵付ハッシュ関数Ｈを適用して得られた値を、ハッシュ値Ｓとして生成する。そして、ハッシュ部１２は、そのハッシュ値Ｓを、マスク付暗号化部１５へ出力する。
【００９５】
また、メッセージMの入力を外部から受付けた旨が入力部１１から通知された場合、ステップ４３にて、乱数生成部１３は、そのメッセージMと独立したビット数がｎビットの乱数Uを生成する。そして、乱数生成部１３は、乱数Ｕを、乱数暗号化部１４とマスク付暗号化部１５とへ出力する。
【００９６】
すると、ステップ４４にて、乱数暗号化部１４は、乱数生成部１３から出力されてきた乱数Uを第１の鍵Ｋｅ１を有する暗号関数Fで暗号化することにより、ビット数がｎビットの中間変数Vを生成する。そして、乱数暗号化部１４は、第１の中間変数Ｖをタグ生成部１６へ出力する。
【００９７】
続いて、ステップ４５にて、マスク付暗号化部１５は、乱数生成部１３から出力されてきた乱数Uと、ハッシュ部１２から出力されてきたハッシュ値Sとの排他的論理和を算出する。そして、マスク付暗号化部１５は、乱数Uとハッシュ値Ｓとの排他的論理和を第２の鍵Ｋｅ２を有する暗号関数Fで暗号化した値を、第２の中間変数Wとして生成する。そして、マスク付暗号化部１５は、第２の中間変数Ｗをタグ生成部１６へ出力する。
【００９８】
さらに、ステップ４６にて、マスク付暗号化部１５は、ハッシュ部１２から出力されてきたハッシュ値Sを第３の鍵Ｋｅ３を有する暗号関数Fを用いて暗号化した値を、第３の中間変数Zとして生成する。そして、マスク付暗号化部１５は、第３の中間変数Zをタグ生成部１６へ出力する。
【００９９】
すると、タグ生成部１６は、乱数暗号化部１４から出力されてきた第１の中間変数Vと、マスク付暗号化部１５から出力されてきた第２の中間変数Wと第３の中間変数Zとの排他的論理和を算出する。続いて、ステップ４７にて、タグ生成部１６は、第１の中間変数Vと第２の中間変数Wと第３の中間変数Zとの排他的論理和のうちから抽出した所定のビット数ｓのビットを、タグTとして生成する。そして、タグ生成部１６は、タグＴを、出力部１７へ出力する。
【０１００】
その後、出力部１７は、乱数生成部１３から出力されてきた乱数Uと、タグ生成部１６から出力されてきたタグTと、入力部１１から出力されてきたメッセージMとを連結する。そして、ステップ４８にて、出力部１７は、連結した乱数ＵとタグＴとメッセージＭとを、メッセージＭの宛先であるタグ検証装置２へ送信する。以上で、タグ生成装置１がタグＴを生成する一連の動作が終了する。
【０１０１】
つぎに、上記構成を有する実施形態１のタグ検証装置２が外部から送信されてきたタグＴｒを検証する動作を、図７を参照して説明する。
【０１０２】
図７に示すステップ５１にて、入力部２１は、タグ生成装置１を含む任意の送信元から通信路３を介して送信されてきたメッセージMrと乱数ＵｒとタグTrとを受信する。そして、入力部２１は、そのメッセージMrをハッシュ部２２へ出力する。また、入力部２１は、その乱数Ｕｒを乱数暗号化部２３へ出力する。また、入力部２１は、そのタグTrを比較部２６へ出力する。
【０１０３】
すると、ステップ５２にて、ハッシュ部２２は、入力部２１から出力されてきたメッセージMrへハッシュ鍵Ｋｈを有する鍵付ハッシュ関数Hを適用して得られた値を、検証用ハッシュ値Ｓ１として生成する。そして、ハッシュ部２２は、検証用ハッシュ値Ｓ１を、マスク付暗号化部２４へ出力する。
【０１０４】
また、ステップ５３にて、乱数暗号化部２３は、入力部２１から出力されてきた乱数Ｕｒを第１の検証鍵Kv1を有する暗号関数Fで暗号化してビット数がｎビットの第１の検証用中間変数V１を生成する。そして、乱数暗号化部２３は、第１の検証用中間変数Ｖ１をタグ生成部２５へ出力する。
【０１０５】
続いて、マスク付暗号化部２４は、入力部２１から出力されてきた乱数Ｕｒと、ハッシュ部２２から出力されてきた検証用ハッシュ値Ｓ１との排他的論理和を算出する。そして、ステップ５４にて、マスク付暗号化部２４は、乱数Ｕｒと検証用ハッシュ値Ｓ１との排他的論理和を第２の検証鍵Ｋｖ２を有する暗号関数Fで暗号化した値を、第２の検証用中間変数W１として生成する。そして、マスク付暗号化部２４は、第２の検証用中間変数Ｗ１をタグ生成部２５へ出力する。
【０１０６】
さらに、ステップ５５にて、マスク付暗号化部２４は、ハッシュ部２２から出力されてきた検証用ハッシュ値S１を第３の検証鍵Ｋｖ３を有する暗号関数Fを用いて暗号化した値を、第３の検証用中間変数Ｚ１として生成する。そして、マスク付暗号化部２４は、第３の検証用中間変数Z１をタグ生成部２５へ出力する。
【０１０７】
すると、タグ生成部２５は、乱数暗号化部２３から出力されてきた第１の検証用中間変数V１と、マスク付暗号化部２４から出力されてきた第２の検証用中間変数W１と第３の検証用中間変数Z１との排他的論理和を算出する。
【０１０８】
そして、ステップ５６にて、タグ生成部２５は、第１の検証用中間変数V１と第２の検証用中間変数W１と第３の検証用中間変数Z１との排他的論理和のうちから抽出した所定数ｓのビットを、検証用タグT１として生成する。そして、タグ生成部２５は、検証用タグＴ１を、比較部２６へ出力する。
【０１０９】
すると、ステップ５７にて、比較部２６は、タグ生成部２５から出力されてきた検証用タグＴ１と、入力部２１から出力されてきたタグＴｒとを比較し、その比較結果を出力部２７へ出力する。
【０１１０】
この比較の結果、検証用タグＴ１とタグＴｒとが同じである場合、ステップ５８にて、出力部２７は、メッセージＭｒが正当な送信者から送られたものである旨を示す情報を出力する。
【０１１１】
一方、ステップ５７における比較の結果、検証用タグＴ１とタグＴｒとが異なっている場合、ステップ５９にて、出力部２７は、メッセージＭｒが正当な送信者から送られたものでない旨を示す情報を出力する。以上で、実施形態１のタグ検証装置２が外部から送信されてきたタグＴｒを検証する一連の動作が終了する。
【０１１２】
以上説明したように、本発明の実施形態１によれば、タグ生成装置１は、メッセージＭに対して鍵付ハッシュ関数Ｈを適用して得られたビット数がnビットのハッシュ値Sと、ビット数がnビットの乱数Uとの排他的論理和を算出する。そして、タグ生成装置１は、この排他的論理和の値をnビットのデータを入力してｎビットのデータを出力する暗号関数Ｆ（例えば、n-bitブロック暗号）を用いて暗号化することにより、第２の中間変数Wを生成する。さらに、乱数Uを暗号関数Ｆを用いて暗号化して得られた第１の中間変数Vと、ハッシュ値Sを暗号関数Ｆを用いて暗号化して得られた第３の中間変数Zと、第２の中間変数Wとの排他的論理和を、タグＴとして生成する。
【０１１３】
このような方法により生成されたタグＴ（メッセージ認証コード）は、Carter-Wegman  MAC方式にて生成されたタグと異なり、乱数生成部１３が生成した複数の乱数が互いに一致した場合でもハッシュ関数Ｈが有するハッシュ鍵Ｋｈの漏洩につながらない。
【０１１４】
これにより、選択平文攻撃に対する大幅な安全性の向上を可能とし、結果的に１つの鍵で安全に通信できる回数を一般的な方式と比べて大幅に増やすことができる。さらに、実施形態１によれば、一般的な方式と比べて、通信量が増加することを回避できるとともに、計算量の増加量を緩和することができる。
【０１１５】
また、実施形態１によれば、鍵の寿命(KLT)が「n/2」より大きくすることができるとともに、乱数Ｕのビット数はCarter-Wegman  MACなどのように鍵寿命が「n/2」である方式で用いられる乱数のビット数（＝nビット）と同じである。そのため、乱数付きのタグＴを効率的に生成することができる。
【０１１６】
これは、実施形態１では、タグＴの生成に用いられる第１の中間変数Ｖおよび第２の中間変数Ｗの両方に乱数Ｕが介在しているからである。そのため、乱数Ｕが一致（衝突）した場合でも、ハッシュ関数Hから出力されるハッシュ値Ｓの差分に基づいて、そのハッシュ値Ｓの生成に用いられたハッシュ鍵Ｋｈが容易に推測されてしまうことを困難にすることができる。
【０１１７】
なお、randomized  CW-MACでは、乱数が一致した場合、出力されるハッシュ値の差分が漏れてしまうため、ハッシュ値Ｓの生成に用いたハッシュ関数Ｈのハッシュ鍵Ｋｈを導出することができてしまう。その結果、任意のメッセージＭについて強偽造不可能性の意味で、偽造データの生成が可能となってしまう。なお、乱数Ｕのビット数がnビットである場合、異なる２回の通信内容で乱数Ｕが互いに同じになる確率はおよそ（Qmac2）/2nとなる。そのため、Qmacの値が2(n/2)である場合（つまり、攻撃を行う第３者がタグ生成装置１から送信されたデータ（乱数ＵとタグＴとメッセージＭ）をQmac個取得した場合）、乱数Ｕが少なくとも１回互いに同じとなってしまう可能性がある。
【０１１８】
一方、互いに異なるメッセージに対してそれぞれ生成したハッシュ値が同じであること（ハッシュ値Ｓのビット数がnビットである場合、Qmacの値が２(n/2)である場合にハッシュ値が少なくとも１回同じとなってしまう可能性がある）を第３者に観測によって認識されてしまった場合には、直ちに攻撃（偽造データの生成および送信）へつながってしまう。
【０１１９】
しかし、実施形態１によれば、ハッシュ値Ｓが同じであった場合でも、乱数Ｕも同じでない限り、ハッシュ鍵Ｋｈは第３者によって容易に推測することはできず安全である。具体的には、ユニバーサルハッシュ関数を適切に選択することにより、KLTが少なくともほぼ「2/3n」となることが示せる。これは、非特許文献１に加持された技術における値がほぼnである鍵寿命（KLT）と比べると安全性は落ちる。しかし、ＫＬＴは、ある１つの鍵でメッセージＭを送信することが可能な回数の最大値（鍵寿命）を２のべき乗で表したときのべき数で表現された評価指標であるため、一般的なn-bit乱数によるrandomized  CW-MACにおけるKLT（＝「n/2」）と比べて非常に長くすることが可能である。
【０１２０】
また、実施形態１によれば、非特許文献１に開示された方式よりも乱数Ｕのビット数が少なくなっているとともに、かつ暗号関数Ｆを用いて計算を実行する回数も非特許文献１に開示された方式における当該回数以下である。そのため、タグ生成装置１がタグＴを生成するために実行する計算量が増大することなく、乱数Ｕの量を削減することが可能であり、ひいては通信帯域におけるオーバーヘッドを減らすことが可能となる。なお、この効率の差は、メッセージＭのデータ長が比較的短い場合（例えば、インターネットなどを含む通信路３上を伝送されるパケットなど）にとりわけ顕著となる。
【０１２１】
（実施形態２）
つぎに、実施形態２の通信システムについて説明する。
【０１２２】
実施形態２の通信システムの構成は、図１に示した通信システムの構成と同じである。
【０１２３】
また、実施形態２のタグ生成装置１の構成は、図２に示したタグ生成装置１の構成と同じである。
【０１２４】
ただし、実施形態２においては、マスク付暗号部１５は第３の中間変数Ｚを生成しない点が、実施形態１と異なっている。つまり、実施形態２のマスク付暗号部１５は、乱数生成部１３から出力されてきた乱数Uとハッシュ部１２から出力されてきたハッシュ値Sとの排他的論理和を第２の鍵Ｋｅ２を有する暗号関数Fを用いて暗号化した値を、第２の中間変数Wとして生成してタグ生成部１６へ出力する。
【０１２５】
また、実施形態２のタグ生成部１６は、乱数暗号化部１４から出力されてきた第１の中間変数Vと、マスク付暗号化部１５から出力されてきた第２の中間変数Wとの排他的論理和を算出する。そして、タグ生成部１６は、第１の中間変数Vと第２の中間変数Wとの排他的論理和のうちから抽出した乱数Ｕのビット数ｎ以下である所定のビット数ｓのビットに含まれる値を、タグTとして生成して出力部１７へ出力する。
【０１２６】
なお、実施形態２のハッシュ部１２と乱数暗号化部１４とマスク付暗号化部１５とタグ生成部１６とは、図８に示すような構成の一形態で実現することが可能である。
【０１２７】
また、実施形態２のタグ検証装置２の構成は、図４に示したタグ検証装置２の構成と同じである。
【０１２８】
ただし、実施形態２においては、マスク付暗号部２４は第３の検証用中間変数Ｚ１を生成しない点が、実施形態１と異なっている。つまり、実施形態２のマスク付暗号部２４は、入力部２１から出力されてきた乱数Ｕｒと、ハッシュ部２２から出力されてきた検証用ハッシュ値Ｓ１との排他的論理和を算出する。そして、マスク付暗号化部２４は、乱数Ｕｒと検証用ハッシュ値Ｓ１との排他的論理和を第２の検証鍵Ｋｖ２を有する暗号関数Fで暗号化した値を、第２の検証用中間変数W１として生成してタグ生成部２５へ出力する。
【０１２９】
また、実施形態２のタグ生成部２５は、乱数暗号化部２３から出力されてきた第１の検証用中間変数V１と、マスク付暗号化部２４から出力されてきた第２の検証用中間変数W１との排他的論理和を算出する。そして、タグ生成部２５は、第１の検証用中間変数V１と第２の検証用中間変数W１との排他的論理和のうちから乱数Ｕｒのビット数ｎ以下である抽出した所定のビット数ｓのビットに含まれる値を、検証用タグT１として生成して比較部２６へ出力する。
【０１３０】
そして、実施形態２のタグ検証装置が有する比較部２６は、第１の検証用中間変数V１と第２の検証用中間変数W１との排他的論理和に基づいて生成された検証用タグＴ１と、入力部２１から出力されてきたタグＴｒとを比較する。
【０１３１】
この比較の結果、検証用タグＴ１とタグＴｒとが同じである場合、出力部２７は、メッセージＭｒが正当な送信者から送られたものである旨を示す情報を出力し、比較の結果、検証用タグＴ１とタグＴｒとが異なっている場合、メッセージＭｒが正当な送信者から送られたものでない旨を示す情報を出力する。
【０１３２】
以上説明したように、本発明の実施形態２によれば、タグＴの生成に用いられる第１の中間変数Ｖおよび第２の中間変数Ｗの両方に乱数Ｕが介在している。そのため、乱数Ｕが一致（衝突）した場合でも、ハッシュ関数Hから出力されるハッシュ値の差分に基づいて、そのハッシュ値の生成に用いられたハッシュ鍵Ｋｈが容易に推測されてしまうことを困難にすることができる。
【０１３３】
なお、本発明においては、タグ生成装置１内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、タグ生成装置１として動作させるコンピュータにて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムをそのコンピュータに読み込ませ、実行するものであってもよい。タグ生成装置１として動作させるコンピュータにて読取可能な記録媒体とは、フロッピーディスク（登録商標）、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、そのコンピュータに内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、例えば、タグ生成装置１として動作させるコンピュータが有するハッシュ部１２、乱数生成部１３、乱数暗号化部１４、マスク付暗号化部１５およびタグ生成部１６として動作するプロセッサにて読み込まれ、そのプロセッサの制御によって、上述したものと同様の処理が行われる。
【０１３４】
ここで、ハッシュ部１２、乱数生成部１３、乱数暗号化部１４、マスク付暗号化部１５およびタグ生成部１６として動作するプロセッサは、プログラムが記録された記録媒体から読み込まれたプログラムを実行するものである。なお、上述のプログラムは、タグ検証装置２についても同様に適用可能である。
【０１３５】
なお、本発明は、例えば、無線通信方式もしくは有線通信方式により行われる通信にて送受信されるデータの認証といった用途や、ストレージ装置に記憶されているデータの改ざん防止といった用途などに適用が可能である。
【０１３６】
本発明の効果の一例として、安全性が高いメッセージ認証用のタグを効率的に生成することができる。
【０１３７】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１３８】
なお、この出願は、２００９年５月１１日に出願された日本出願の特願２００９−１１４５０４の内容が全て取り込まれており、この日本出願を基礎として優先権を主張するものである。
【符号の説明】
【０１３９】
１  タグ生成装置
２  タグ検証装置
３  ネットワーク
１１  入力部
１２  ハッシュ部
１３  乱数生成部
１４  乱数暗号化部
１５  マスク付暗号化部
１６  タグ生成部
１７  出力部
２１  入力部
２２  ハッシュ部
２３  乱数暗号化部
２４  マスク付暗号化部
２５  タグ生成部
２６  比較部
２７  出力部
【図１】
0005447510.tif 000011
【図２】
0005447510.tif 000012
【図３】
0005447510.tif 000013
【図４】
0005447510.tif 000014
【図５】
0005447510.tif 000015
【図６】
0005447510.tif 000016
【図７】
0005447510.tif 000017
【図８】
0005447510.tif 000018
【図９】
0005447510.tif 000019