(57)【要約】【課題】演算効率のよい認証暗号技術を提供する。【解決手段】平文情報Ｐ［ｉ］（ｉ＝１，・・・，ｐ）を暗号化し、暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）を得る。暗号文Ｃ［ｉ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、拡大体ＧＦ（２ｎ）の元である秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得る。（×）は拡大体ＧＦ（２ｍ［ｊ］）（ｍ［ｊ］＜ｎ）上の乗算演算子を表す。拡大体ＧＦ（２ｎ）の元を或るＳ［０］とし、ｉ＝１，・・・，ｐについて拡大体演算部の処理を行って得られた元Ｓ［ｐ］に対応する認証子Ｔを得る。【選択図】図１
2014002230.tif 000002
【特許請求の範囲】
【請求項１】
ｎ，ｑが２以上の整数であり、ｐが１以上の整数であり、ｍ［ｊ］（ｊ＝１，・・・，ｑ）がｍ［１］＋・・・＋ｍ［ｑ］＝ｎを満たす正整数であり、ＧＦ（２）が位数２の有限体であり、ＧＦ（２ｎ）が前記有限体ＧＦ（２）をｎ次拡大した拡大体であり、ＧＦ（２ｍ［ｊ］）（ｊ＝１，・・・，ｑ）が前記有限体ＧＦ（２）をｍ［ｊ］次拡大した拡大体であり、
ＸがＸ［１］，・・・，Ｘ［ｑ］からなり、Ｘ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、ＹがＹ［１］，・・・，Ｙ［ｑ］からなり、Ｙ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、Ｘ（＋）ＹがＸとＹを被演算子とした拡大体ＧＦ（２ｎ）上での加算であり、Ｘ（×）ＹがＸとＹを被演算子としてＸ［１］・Ｙ［１］，・・・，Ｘ［ｑ］・Ｙ［ｑ］からなる値を得る演算であり、Ｘ［ｊ］・Ｙ［ｊ］がＸ［ｊ］とＹ［ｊ］を被演算子とした拡大体ＧＦ（２ｍ［ｊ］）上での乗算であり、
平文情報Ｐ［ｉ］（ｉ＝１，・・・，ｐ）を暗号化し、暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）を得る暗号化部と、
前記暗号文Ｃ［ｉ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、拡大体ＧＦ（２ｎ）の元である秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得る拡大体演算部と、
拡大体ＧＦ（２ｎ）の元を或るＳ［０］とし、ｉ＝１，・・・，ｐについて前記拡大体演算部の処理を行って得られた元Ｓ［ｐ］に対応する認証子Ｔを得る認証子生成部と、
を有する認証暗号化装置。
【請求項２】
請求項１の認証暗号化装置であって、
ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２である、
ことを特徴とする認証暗号化装置。
【請求項３】
請求項１または２の認証暗号化装置であって、
ａが１以上の整数であり、付加情報Ａ［ｄ］（ｄ＝１，・・・，ａ）が拡大体ＧＦ（２ｎ）の元であり、初期値Ｉが拡大体ＧＦ（２ｎ）の元であり、
前記初期値Ｉおよび前記秘密情報Ｗを用い、演算Ｕ［０］＝（Ｉ）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［０］を得る初期拡大体演算部と、
前記付加情報Ａ［ｄ］、前記秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｕ［ｉ−１］を用い、演算Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［ｄ］を得る付加拡大体演算部と、
をさらに有し、
前記元Ｓ［０］は、ｄ＝１，・・・，ａについて前記付加拡大体演算部の処理を行って得られた元Ｕ［ａ］である、
ことを特徴とする認証暗号化装置。
【請求項４】
ｎ，ｑが２以上の整数であり、ｐが１以上の整数であり、ｍ［ｊ］（ｊ＝１，・・・，ｑ）がｍ［１］＋・・・＋ｍ［ｑ］＝ｎを満たす正整数であり、ＧＦ（２）が位数２の有限体であり、ＧＦ（２ｎ）が前記有限体ＧＦ（２）をｎ次拡大した拡大体であり、ＧＦ（２ｍ［ｊ］）（ｊ＝１，・・・，ｑ）が前記有限体ＧＦ（２）をｍ［ｊ］次拡大した拡大体であり、
ＸがＸ［１］，・・・，Ｘ［ｑ］からなり、Ｘ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、ＹがＹ［１］，・・・，Ｙ［ｑ］からなり、Ｙ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、Ｘ（＋）ＹがＸとＹを被演算子とした拡大体ＧＦ（２ｎ）上での加算であり、Ｘ（×）ＹがＸとＹを被演算子としてＸ［１］・Ｙ［１］，・・・，Ｘ［ｑ］・Ｙ［ｑ］からなる値を得る演算であり、Ｘ［ｊ］・Ｙ［ｊ］がＸ［ｊ］とＹ［ｊ］を被演算子とした拡大体ＧＦ（２ｍ［ｊ］）上での乗算であり、
暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、拡大体ＧＦ（２ｎ）の元である秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得る拡大体演算部と、
拡大体ＧＦ（２ｎ）の或る元をＳ［０］とし、ｉ＝１，・・・，ｐについて前記拡大体演算部の処理を行って得られた元Ｓ［ｐ］に対応する検証用認証子ＶＴを得る認証子生成部と、
前記検証用認証子ＶＴと入力された認証子Ｔとが等しいかを判定する判定部と、
を有する認証復号装置。
【請求項５】
請求項４の認証復号装置であって、
ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２である、
ことを特徴とする認証復号装置。
【請求項６】
請求項４または５の認証復号装置あって、
ａが１以上の整数であり、付加情報Ａ［ｄ］（ｄ＝１，・・・，ａ）が拡大体ＧＦ（２ｎ）の元であり、初期値Ｉが拡大体ＧＦ（２ｎ）の元であり、
前記初期値Ｉおよび前記秘密情報Ｗを用い、演算Ｕ［０］＝（Ｉ）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［０］を得る初期拡大体演算部と、
前記付加情報Ａ［ｄ］、前記秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｕ［ｉ−１］を用い、演算Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［ｄ］を得る付加拡大体演算部と、
をさらに有し、
前記元Ｓ［０］は、ｄ＝１，・・・，ａについて前記付加拡大体演算部の処理を行って得られた元Ｕ［ａ］である、
ことを特徴とする認証復号装置。
【請求項７】
請求項１から３のいずれかの認証暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項４から６のいずれかの認証復号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に暗号文の認証子を用いる認証暗号技術に関する。
【背景技術】
【０００２】
認証暗号の暗号化アルゴリズムεは、秘密鍵Ｋ、ナンス値ＩＶ、平文メッセージＰ、および付加データＡを入力とし、暗号文Ｃ、および認証子Ｔを出力する。これを数式で書けば以下のようになる。
【数１】
2014002230.tif 000003
ここでナンス値とは暗号化の度に変化する値であり、決して同じ値を繰り返さないという要件を満たすものである。ナンス値は秘密である必要もないしランダムである必要もない。付加情報とは平文メッセージに付随するデータであるが暗号化されずにそのまま送信ないし保存されるものである。
【０００３】
認証暗号の復号アルゴリズムＤは、秘密鍵Ｋ、ナンス値ＩＶ、暗号文Ｃ、認証子Ｔ、および付加データＡを入力とし、平文メッセージＰないし不正エラーを示す特別シンボル⊥を出力する。これを数式で書けば以下のようになる。
【数２】
2014002230.tif 000004
【０００４】
上記２つのアルゴリズムは健全性を満たさねばならない。すなわち、式（１）を満たすときには必ず式（３）を満たさず、なおかつ、式（２）を満たすものとなっていなければならない。
【０００５】
認証暗号の方式としてEncrypt-then-MACに基づくものがある。例えば、非特許文献１に基づく方式の暗号化アルゴリズムでは、まず平文メッセージＰをビット長ｎごとに分割してブロックＰ［１］，・・・，Ｐ［ｐ］を得る（ただし、ｎ，ｐは１以上の整数）。平文メッセージＰのビット長がｎの整数倍である場合には、ブロックＰ［１］，・・・，Ｐ［ｐ］のビット長はすべてｎである。そうでない場合には、ブロックＰ［１］，・・・，Ｐ［ｐ−１］のビット長はすべてｎであり、ブロックＰ［ｐ］のビット長はｎ未満である。ブロックＰ［１］，・・・，Ｐ［ｐ］は、秘密鍵Ｋおよびナンス値ＩＶを用いたブロック暗号のＣＴＲモードによって暗号化され、暗号文Ｃ［１］，・・・，Ｃ［ｐ］が得られる。平文メッセージＰのビット長がｎの整数倍である場合には暗号文Ｃ［１］，・・・，Ｃ［ｐ］のビット長はすべてｎである。そうでない場合には、暗号文Ｃ［１］，・・・，Ｃ［ｐ−１］のビット長はすべてｎであり、暗号文Ｃ［ｐ］のビット長はｎ未満である。さらに、ビット長ｎの秘密情報Ｗ、付加データＡを分割して得られたビット長ｎまたはｎ未満の付加情報Ａ［１］，・・・，Ａ［ａ］、暗号文Ｃ［１］，・・・，Ｃ［ｐ］を用い、多項式ハッシュ関数によって認証子Ｔを得る。従来の多項式ハッシュ関数の演算では、ビットを有限体ＧＦ（２）の元とし、ビット長ｎの情報を拡大体ＧＦ（２ｎ）の元とした拡大体ＧＦ（２ｎ）上での乗算が実行される。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】NIST: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 800-38D, November, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に基づく認証暗号方式では、多項式ハッシュ関数の演算を行うために、拡大体ＧＦ（２ｎ）上での乗算を行う。通常、ｎがα倍になると拡大体ＧＦ（２ｎ）上での乗算の演算量はα２となる。そのため、多項式ハッシュ関数の演算のために拡大体ＧＦ（２ｎ）上での乗算を行ったのでは、ｎの増加に伴って演算効率が著しく低下してしまう。
本発明はこのような点に鑑みてなされたものであり、演算効率のよい認証暗号技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明では、ｎ，ｑが２以上の整数であり、ｐが１以上の整数であり、ｍ［ｊ］（ｊ＝１，・・・，ｑ）がｍ［１］＋・・・＋ｍ［ｑ］＝ｎを満たす正整数であり、ＧＦ（２）が位数２の有限体であり、ＧＦ（２ｎ）が有限体ＧＦ（２）をｎ次拡大した拡大体であり、ＧＦ（２ｍ［ｊ］）（ｊ＝１，・・・，ｑ）が有限体ＧＦ（２）をｍ［ｊ］次拡大した拡大体である。またＸがＸ［１］，・・・，Ｘ［ｑ］からなり、Ｘ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、ＹがＹ［１］，・・・，Ｙ［ｑ］からなり、Ｙ［ｊ］が拡大体ＧＦ（２ｍ［ｊ］）の元であり、Ｘ（＋）ＹがＸとＹを被演算子とした拡大体ＧＦ（２ｎ）上での加算であり、Ｘ（×）ＹがＸとＹを被演算子としてＸ［１］・Ｙ［１］，・・・，Ｘ［ｑ］・Ｙ［ｑ］からなる値を得る演算であり、Ｘ［ｊ］・Ｙ［ｊ］がＸ［ｊ］とＹ［ｊ］を被演算子とした拡大体ＧＦ（２ｍ［ｊ］）上での乗算である。
【０００９】
認証暗号化では、平文情報Ｐ［ｉ］（ｉ＝１，・・・，ｐ）を暗号化し、暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）を得る。また、暗号文Ｃ［ｉ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、拡大体ＧＦ（２ｎ）の元である秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得る。さらに、拡大体ＧＦ（２ｎ）の元を或るＳ［０］とし、ｉ＝１，・・・，ｐについて拡大体演算部の処理を行って得られた元Ｓ［ｐ］に対応する認証子Ｔを得る。
【００１０】
認証復号では、暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、拡大体ＧＦ（２ｎ）の元である秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得る。また、拡大体ＧＦ（２ｎ）の或る元をＳ［０］とし、ｉ＝１，・・・，ｐについて拡大体演算部の処理を行って得られた元Ｓ［ｐ］に対応する検証用認証子ＶＴを得、検証用認証子ＶＴと入力された認証子Ｔとが等しいかを判定する。
【発明の効果】
【００１１】
本発明では、拡大体ＧＦ（２ｍ［ｊ］）（ただしｍ［ｊ］＜ｎ）上での乗算によって多項式ハッシュ関数の演算を行うため、従来よりも演算効率がよい。
【図面の簡単な説明】
【００１２】
【図１】実施形態の認証システムの構成を例示したブロック図。
【図２】実施形態の認証暗号化方法を説明するためのフロー図。
【図３】実施形態の認証復号方法を説明するためのフロー図。
【図４】認証子生成処理の具体例を説明するための図。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施形態を説明する。
＜定義＞
本形態で使用する用語や記号を定義する。
ｎ，ｑは２以上の整数であり、ａ，ｐは１以上の整数であり、ｍ［ｊ］（ｊ＝１，・・・，ｑ）はｍ［１］＋・・・＋ｍ［ｑ］＝ｎを満たす正整数である。一例を挙げると、ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２である。
【００１４】
ＧＦ（２）は位数２の有限体であり、ＧＦ（２ｎ）は有限体ＧＦ（２）をｎ次拡大した拡大体であり、ＧＦ（２ｍ［ｊ］）（ｊ＝１，・・・，ｑ）は有限体ＧＦ（２）をｍ［ｊ］次拡大した拡大体である。ＧＦ（２）の例はビット∈｛０，１｝であり、ＧＦ（２ｎ）の例はｎ個のビットからなるビット列∈｛０，１｝ｎであり、ＧＦ（２ｍ［ｊ］）の例はｍ［ｊ］個のビットからなるビット列∈｛０，１｝ｍ［ｊ］である。
【００１５】
Ｘ（×）Ｙは、ＸとＹを被演算子としてＸ［１］・Ｙ［１］，・・・，Ｘ［ｑ］・Ｙ［ｑ］からなる値を得る演算である。ただし、Ｘ［ｊ］・Ｙ［ｊ］は、Ｘ［ｊ］とＹ［ｊ］を被演算子とした拡大体ＧＦ（２ｍ［ｊ］）上での乗算であり、ＸはＸ［１］，・・・，Ｘ［ｑ］からなり、Ｘ［ｊ］（ｊ＝１，・・・，ｑ）は拡大体ＧＦ（２ｍ［ｊ］）の元であり、ＹはＹ［１］，・・・，Ｙ［ｑ］からなり、Ｙ［ｊ］（ｊ＝１，・・・，ｑ）は拡大体ＧＦ（２ｍ［ｊ］）の元である。例えば、ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２の場合、Ｘ（×）ＹがＸとＹを被演算子としてＸ［１］・Ｙ［１］，Ｘ［２］・Ｙ［２］からなる値を得る演算であり、Ｘ［ｊ］・Ｙ［ｊ］がＸ［ｊ］とＹ［ｊ］を被演算子とした拡大体ＧＦ（２ｎ／２）上での乗算であり、ＸはＸ［１］，Ｘ［２］からなり、Ｘ［ｊ］（ｊ＝１，２）は拡大体ＧＦ（２ｎ／２）の元であり、ＹはＹ［１］，Ｙ［２］からなり、Ｙ［ｊ］（ｊ＝１，２）は拡大体ＧＦ（２ｎ／２）の元である。特に断りのない限り、Ｘ（＋）Ｙは、ＸとＹを被演算子とした拡大体ＧＦ（２ｎ）上での加算である。拡大体ＧＦ（２ｍ［ｊ］）上の演算は、例えば、被演算子である拡大体ＧＦ（２ｍ［ｊ］）を多項式表現し、ｍ［ｊ］次の既約多項式を法とし、これらの多項式間で剰余演算（剰余乗算や剰余加算）を行うことで実現できる。拡大体ＧＦ（２ｍ［ｊ］）上での演算結果は、この剰余演算で得られた多項式の係数からなる。
【００１６】
＜構成＞
図１に例示するように、本形態の認証システム１は、認証暗号化装置１００および認証復号装置２００を有する。認証暗号化装置１００および認証復号装置２００は、例えば互いに通信可能に構成され、それぞれ以下の機能構成を有する。
【００１７】
認証暗号化装置１００は、例えば、入力部１０１、初期値生成部１０２、初期拡大体演算部１０３、付加情報分割部１０４、付加拡大体演算部１０５、平文分割部１０６、暗号化部１０７、拡大体演算部１０８、暗号文連結部１０９、認証子生成部１１０、出力部１１１、制御部１１３、および記憶部１１４を有する。認証復号装置２００は、例えば、入力部２０１、初期値生成部２０２、初期拡大体演算部２０３、付加情報分割部２０４、付加拡大体演算部２０５、暗号文分割部２０６、復号部２０７、拡大体演算部２０８、平文情報連結部２０９、認証子生成部２１０、出力部２１２、制御部２１３、および記憶部２１４を有する。
【００１８】
認証暗号化装置１００および認証復号装置２００は、それぞれ、ＣＰＵ（central processing unit）やＲＡＭ（random-access memory）等を有する公知または専用のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。認証暗号化装置１００は、制御部１１３の制御のもとで各処理を実行し、認証復号装置２００は、制御部２１３の制御のもとで各処理を実行する。証暗号化装置１００への入力情報や証暗号化装置１００の各部から出力された情報は、逐一、記憶部１１４に格納され、必要に応じて読み出されて各部の入力とされる。認証復号装置２００への入力情報や認証復号装置２００の各部から出力された情報は、逐一、記憶部２１４に格納され、必要に応じて読み出されて各部の入力とされる。
【００１９】
＜認証暗号化＞
図２および図４を参照して、本形態の認証暗号化方法を説明する。
まず、認証暗号化装置１００の入力部１０１に、共通鍵暗号方式の秘密鍵Ｋ、ナンス値ＩＶ、平文メッセージＰ、および付加データＡが入力される。これらはいずれも有限体ＧＦ（２）上の拡大体の元である。例えば、有限体ＧＦ（２）が排他的論理和演算の定義されたビット集合｛０，１｝、ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２の場合（以下「具体例」と呼ぶ）、Ｋ∈｛０，１｝ｋ（ただしｋは１以上の整数）、ＩＶ（≠０）∈｛０，１｝ｎ／２、Ｐ∈｛０，１｝*、Ａ∈｛０，１｝*である。ただし｛０，１｝χはビット長χのビット列の集合を表し、｛０，１｝*は任意長のビット列の集合を表す（ステップＳ１０１）。
【００２０】
初期値生成部１０２は秘密鍵Ｋを入力とし、秘密鍵Ｋに対応する拡大体ＧＦ（２ｎ）の元である秘密情報Ｗを生成して出力する。例えば、初期値生成部１０２は、秘密鍵Ｋを用いて所定の値βを暗号化して秘密情報Ｗ＝ＥＫ（β）を得る。βの具体例は０である。なお「ＥＫ（ω）」は、秘密鍵Ｋを用い、所定の共通鍵暗号方式に則ってωを暗号化する処理を意味する。「具体例」の場合、Ｗ＝（Ｈ｜Ｌ）と表現する。ＨはＷの上位ｎ／２ビットを表し、ＬはＷの残りの下位ｎ／２ビットを表し、「γ｜δ」はγとδとのビット結合（「ビット連結」ともいう）を表す（ステップＳ１０２）。
【００２１】
初期拡大体演算部１０３にはナンス値ＩＶおよび秘密情報Ｗが入力される。初期拡大体演算部１０３は、ナンス値ＩＶから得られる拡大体ＧＦ（２ｎ）の元である初期値Ｉおよび秘密情報Ｗを用い、演算Ｕ［０］＝（Ｉ）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［０］を得て出力する。「具体例」の場合、初期拡大体演算部１０３は、演算Ｕ［０］＝（ＩＶ｜ＩＶ）（×）（Ｈ｜Ｌ）を行い、元Ｕ［０］を得て出力する（ステップＳ１０３）。
【００２２】
付加情報分割部１０４は、付加データＡを入力とし、付加データＡを構成する有限体ＧＦ（２）の個数（「具体例」の場合にはビット長）ＬＡ＝Ｌｅｎ（Ａ）を得て出力する。さらに付加情報分割部１０４は、付加データＡから拡大体ＧＦ（２ｎ）の元である付加情報Ａ［１］，・・・，Ａ［ａ］を得て出力する。「具体例」の場合には、Ａ［ｄ］∈｛０，１｝ｎ（ただしｄ＝１，・・・，ａ）を得て出力する。
【００２３】
以下に付加情報Ａ［１］，・・・，Ａ［ａ］の具体例を示す。
付加データＡを構成する拡大体ＧＦ（２）の個数がｎの整数倍である場合、付加情報分割部１０４は、Ａ＝（Ａ［１］，・・・，Ａ［ａ］）を満たす付加情報Ａ［１］，・・・，Ａ［ａ］を得る。例えば「具体例」の場合、付加情報分割部１０４は、Ａ＝Ａ［１］｜・・・｜Ａ［ａ］を満たすＡ［１］，・・・，Ａ［ａ］を得る。
付加データＡを構成する拡大体ＧＦ（２）の個数がｎの整数倍でない場合、付加情報分割部１０４は、Ａ＝（Ａ［１］，・・・，Ａ［ａ］）を満たすＡ［１］，・・・，Ａ［ａ］を得、Ａ［ａ］に所定の拡大体ＧＦ（２）の元を追加して拡大体ＧＦ（２ｎ）の元としたものを新たなＡ［ａ］とし、Ａ［１］，・・・，Ａ［ａ−１］および新たなＡ［ａ］を付加情報とする。例えば「具体例」の場合、付加情報分割部１０４は、Ａ＝Ａ［１］｜・・・｜Ａ［ａ］を満たすＡ［１］，・・・，Ａ［ａ］を得、Ａ［ａ］に所定のビット（例えば「０」）を追加してビット長ｎとしたものＡ［ａ］｜０*∈｛０，１｝ｎを新たなＡ［ａ］とし、Ａ［１］，・・・，Ａ［ａ−１］および新たなＡ［ａ］を付加情報とする（ステップＳ１０４）。
【００２４】
付加拡大体演算部１０５は、付加情報Ａ［ｄ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｕ［ｉ−１］を入力とし、演算Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［ｄ］を得て出力する。付加拡大体演算部１０５は、ｄ＝１，・・・，ａについてこの処理を実行し、元Ｕ［ａ］を得て出力する（ステップＳ１０５）。
【００２５】
以下にステップＳ１０５の具体例を示す。
≪Ｓ１０５−１≫
付加拡大体演算部１０５は、ｄ＝１に初期化する。
≪Ｓ１０５−２≫
付加拡大体演算部１０５は、Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを計算する。
≪Ｓ１０５−３≫
ｄ＜ａであればｄ＋１を新たなｄとしてＳ１０５−２に戻り、ｄ＝ａであれば付加拡大体演算部１０５がＵ［ａ］を出力する（ステップＳ１０５の具体例の説明終わり）。
【００２６】
平文分割部１０６は、平文メッセージＰを入力とし、平文メッセージＰから平文情報Ｐ［１］，・・・，Ｐ［ｐ］を得て出力する。本形態の平文分割部１０６は、Ｐ＝（Ｐ［１］，・・・，Ｐ［ｐ］）を満たす平文情報Ｐ［１］，・・・，Ｐ［ｐ］を得て出力する。例えば、Ｐ［１］，・・・，Ｐ［ｐ−１］は拡大体ＧＦ（２ｎ）の元であり、Ｐ［ｐ］は拡大体ＧＦ（２ｎ）の元、またはｎ個未満の有限体ＧＦ（２）の元からなる値である。「具体例」の場合、平文分割部１０６は、Ｐ＝Ｐ［１］｜・・・｜Ｐ［ｐ］を満たす平文情報Ｐ［１］，・・・，Ｐ［ｐ］を得て出力する。これらは、Ｐ［１］，・・・，Ｐ［ｐ−１］∈｛０，１｝ｎ、およびＰ［ｐ］∈｛０，１｝*を満たす（ステップＳ１０６）。
【００２７】
暗号化部１０７は、秘密鍵Ｋを用いて平文情報Ｐ［ｉ］（ｉ＝１，・・・，ｐ）を暗号化し、暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）を得て出力する。拡大体演算部１０８は、暗号文Ｃ［ｉ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得て出力する。拡大体演算部１０８は、Ｓ［０］＝Ｕ［ａ］とし、ｉ＝１，・・・，ｐについて、この処理を行って元Ｓ［ｐ］を得て出力する（ステップＳ１０７）。
【００２８】
以下にステップＳ１０７の具体例を示す。
≪Ｓ１０７−１≫
暗号化部１０７は、ｉ＝１に初期化する。
≪Ｓ１０７−２≫
ｉ≦ｐ−１であればＳ１０７−３に進み、ｉ＝ｐでればＳ１０７−６に進む。
≪Ｓ１０７−３≫
暗号化部１０７は、秘密鍵Ｋ、平文情報Ｐ［ｉ］、およびナンス値ＩＶを入力とし、秘密鍵Ｋを用い、平文情報Ｐ［ｉ］およびナンス値ＩＶに対応する暗号文Ｃ［ｉ］∈ＧＦ（２ｎ）を得て出力する。「具体例」の場合、暗号化部１０７は、Ｃ［ｉ］＝ＥＫ（ＩＶ｜＜ｉ−１＞ｎ／２）（＋）Ｐ［ｉ］によって暗号文Ｃ［ｉ］∈｛０，１｝ｎを得て出力する。ただし＜ｉ−１＞ｎ／２は、整数（ｉ−１）のｎ／２ビット表現値である。次にＳ１０７−４に進む。
≪Ｓ１０７−４≫
拡大体演算部１０８は、暗号文ＣＮ［ｉ］＝Ｃ［ｉ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を入力とし、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得て出力する。「具体例」の場合、拡大体演算部１０８は、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）（Ｈ｜Ｌ）を行い、Ｓ［ｉ］∈｛０，１｝ｎを得て出力する。次にＳ１０７−５に進む。
≪Ｓ１０７−５≫
ｉ＋１を新たなｉとしてＳ１０７−２に戻る。
≪Ｓ１０７−６≫
暗号化部１０７は、秘密鍵Ｋ、平文情報Ｐ［ｐ］、およびナンス値ＩＶを入力とし、秘密鍵Ｋを用い、平文情報Ｐ［ｐ］およびナンス値ＩＶに対応する暗号文Ｃ［ｐ］を得て出力する。ただし、暗号文Ｃ［ｐ］は有限体ＧＦ（２）を基礎体とした拡大体の元である。「具体例」の場合、暗号化部１０７は、Ｃ［ｐ］＝ｍｓｂＬｅｎ（Ｐ［ｐ］）｛ＥＫ（ＩＶ｜＜ｐ−１＞ｎ／２）｝（＋）Ｐ［ｐ］によって暗号文Ｃ［ｐ］∈｛０，１｝Ｌｅｎ（Ｐ［ｐ］）を得て出力する。ただし、ｍｓｂＬｅｎ（Ｐ［ｐ］）｛ＥＫ（ＩＶ｜＜ｐ−１＞ｎ／２）｝（＋）Ｐ［ｐ］は、ｍｓｂＬｅｎ（Ｐ［ｐ］）｛ＥＫ（ＩＶ｜＜ｐ−１＞ｎ／２）｝とＰ［ｐ］を被演算子とした拡大体ＧＦ（２Ｌｅｎ（Ｐ［ｐ］））上での加算である。ｍｓｂι（Ψ）はΨの最左（最上位）のι個の元（ビット）を表し、Ｌｅｎ（Ｐ［ｐ］）はＰ［ｐ］のビット長を表す。次にＳ１０７−７に進む。
≪Ｓ１０７−７≫
拡大体演算部１０８は、暗号文Ｃ［ｐ］、秘密情報Ｗ、および元Ｓ［ｐ−１］を入力とし、暗号文Ｃ［ｐ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｐ］を用いて演算Ｓ［ｐ］＝（Ｓ［ｐ−１］（＋）ＣＮ［ｐ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｐ］を得て出力する。「具体例」の場合、拡大体演算部１０８は、ＣＮ［ｐ］＝Ｃ［ｐ］｜０*∈｛０，１｝ｎとして演算Ｓ［ｐ］＝（Ｓ［ｐ−１］（＋）ＣＮ［ｐ］）（×）（Ｈ｜Ｌ）を行い、Ｓ［ｐ］∈｛０，１｝ｎを得て出力する（ステップＳ１０７の具体例の説明終わり）。
【００２９】
暗号文連結部１０９は、暗号文Ｃ［１］，・・・，Ｃ［ｐ］を入力とし、Ｃ［１］，・・・，Ｃ［ｐ］からなる出力暗号文Ｃを得て出力する。「具体例」の場合、暗号文連結部１０９は、Ｃ＝Ｃ［１］｜・・・｜Ｃ［ｐ］を出力暗号文として出力する。また暗号文連結部１０９は、出力暗号文Ｃを入力とし、出力暗号文Ｃを構成する有限体ＧＦ（２）の元の個数（「具体例」の場合には出力暗号文Ｃのビット長）ＬＣ＝Ｌｅｎ（Ｃ）を得て出力する（ステップＳ１０９）。
【００３０】
認証子生成部１１０は、Ｓ［ｐ］に対応する認証子Ｔを得て出力する。認証子生成部１１０は、例えば、Ｓ［ｐ］、ＬＡおよびＬＣに対する像（関数値）である認証子Ｔを得て出力する。一例を挙げると、認証子生成部１１０は、Ｓ［ｐ］、ＬＡおよびＬＣを入力とし、Ｓ*＝Ｓ［ｐ］（＋）（＜ＬＡ＞ｎ／２｜＜ＬＣ＞ｎ／２）を得、認証子Ｔ＝ｍｓｂｔ（ＥＫ（Ｓ*））を得て出力する。「具体例」の場合にはＴ∈｛０，１｝ｔとなる。ただし、ｔは１以上の整数である（ステップＳ１１０）。
【００３１】
出力部１１１は、出力暗号文Ｃおよび認証子Ｔを出力し、認証暗号化処理を終了する（ステップＳ１１１）。
【００３２】
＜認証復号＞
図３および図４を参照して、本形態の認証暗号化方法を説明する。
まず、認証復号装置２００の入力部２０１に、出力暗号文Ｃおよび認証子Ｔ、並びに認証暗号化で用いられたものと同一の秘密鍵Ｋ、ナンス値ＩＶおよび付加データＡが入力される。これらはいずれも有限体ＧＦ（２）上の拡大体の元である。「具体例」の場合、Ｃ∈｛０，１｝*、Ｔ∈｛０，１｝ｔ、Ｋ∈｛０，１｝ｋ、ＩＶ（≠０）∈｛０，１｝ｎ／２、およびＡ∈｛０，１｝*である（ステップＳ２０１）。
【００３３】
初期値生成部２０２は秘密鍵Ｋを入力とし、認証暗号化時と同じ方法で秘密鍵Ｋに対応する拡大体ＧＦ（２ｎ）の元である秘密情報Ｗを生成して出力する。例えば、初期値生成部１０２は、秘密鍵Ｋを用いて所定の値βを暗号化して秘密情報Ｗ＝ＥＫ（β）を得る。βの具体例は０である。「具体例」の場合、Ｗ＝（Ｈ｜Ｌ）と表現する（ステップＳ１０２）。
【００３４】
初期拡大体演算部２０３にはナンス値ＩＶおよび秘密情報Ｗが入力される。初期拡大体演算部２０３は、ナンス値ＩＶから得られる拡大体ＧＦ（２ｎ）の元である初期値Ｉおよび秘密情報Ｗを用い、演算Ｕ［０］＝（Ｉ）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［０］を得て出力する。「具体例」の場合、初期拡大体演算部２０３は、演算Ｕ［０］＝（ＩＶ｜ＩＶ）（×）（Ｈ｜Ｌ）を行い、元Ｕ［０］を得て出力する（ステップＳ２０３）。
【００３５】
付加情報分割部２０４は、付加データＡを入力とし、付加データＡを構成する有限体ＧＦ（２）の個数（「具体例」の場合にはビット長）ＬＡ＝Ｌｅｎ（Ａ）を得て出力する。さらに付加情報分割部２０４は、認証暗号化時と同じ方法で、付加データＡから拡大体ＧＦ（２ｎ）の元である付加情報Ａ［１］，・・・，Ａ［ａ］を得て出力する。「具体例」の場合には、Ａ［ｄ］∈｛０，１｝ｎ（ただしｄ＝１，・・・，ａ）を得て出力する。
【００３６】
以下に付加情報Ａ［１］，・・・，Ａ［ａ］の具体例を示す。
Ｌｅｎ（Ａ）がｎの正整数倍である場合、付加情報分割部２０４は、Ａ＝（Ａ［１］，・・・，Ａ［ａ］）を満たす付加情報Ａ［１］，・・・，Ａ［ａ］を得る。例えば「具体例」の場合、付加情報分割部２０４は、Ａ＝Ａ［１］｜・・・｜Ａ［ａ］を満たすＡ［１］，・・・，Ａ［ａ］を得る。
Ｌｅｎ（Ａ）がｎの正整数倍でない場合、付加情報分割部２０４は、Ａ＝（Ａ［１］，・・・，Ａ［ａ］）を満たすＡ［１］，・・・，Ａ［ａ］を得、Ａ［ａ］にＧＦ（２）の所定の拡大体の元を追加して拡大体ＧＦ（２ｎ）の元としたものを新たなＡ［ａ］とし、Ａ［１］，・・・，Ａ［ａ−１］および新たなＡ［ａ］を付加情報とする。例えば「具体例」の場合、付加情報分割部２０４は、Ａ＝Ａ［１］｜・・・｜Ａ［ａ］を満たすＡ［１］，・・・，Ａ［ａ］を得、Ａ［ａ］に所定のビット（例えば「０」）を追加してビット長ｎとしたものＡ［ａ］｜０*∈｛０，１｝ｎを新たなＡ［ａ］とし、Ａ［１］，・・・，Ａ［ａ−１］および新たなＡ［ａ］を付加情報とする（ステップＳ２０４）。
【００３７】
付加拡大体演算部２０５は、付加情報Ａ［ｄ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｕ［ｉ−１］を入力とし、演算Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｕ［ｄ］を得て出力する。付加拡大体演算部２０５は、ｄ＝１，・・・，ａについてこの処理を実行し、元Ｕ［ａ］を得て出力する（ステップＳ２０５）。
【００３８】
以下にステップＳ２０５の具体例を示す。
≪Ｓ２０５−１≫
付加拡大体演算部２０５は、ｄ＝１に初期化する。
≪Ｓ２０５−２≫
付加拡大体演算部２０５は、Ｕ［ｄ］＝（Ｕ［ｄ−１］（＋）Ａ［ｄ］）（×）Ｗを計算する。
≪Ｓ２０５−３≫
ｄ＜ａであればｄ＋１を新たなｄとしてＳ２０５−２に戻り、ｄ＝ａであれば付加拡大体演算部２０５がＵ［ａ］を出力する（ステップＳ２０５の具体例の説明終わり）。
【００３９】
暗号文分割部２０６は、出力暗号文Ｃを入力とし、出力暗号文Ｃから暗号文Ｃ［１］，・・・，Ｃ［ｐ］を得て出力する。本形態の暗号文分割部２０６は、Ｃ＝（Ｃ［１］，・・・，Ｃ［ｐ］）を満たす暗号文Ｃ［１］，・・・，Ｃ［ｐ］を得て出力する。例えば、Ｃ［１］，・・・，Ｃ［ｐ−１］は拡大体ＧＦ（２ｎ）の元であり、Ｃ［ｐ］は拡大体ＧＦ（２ｎ）の元、またはｎ個未満の有限体ＧＦ（２）の元からなる値である。「具体例」の場合、暗号文分割部２０６は、Ｃ＝Ｃ［１］｜・・・｜Ｃ［ｐ］を満たす暗号文Ｃ［１］，・・・，Ｃ［ｐ］を得て出力する。これらは、Ｃ［１］，・・・，Ｃ［ｐ−１］∈｛０，１｝ｎ、およびＣ［ｐ］∈｛０，１｝*を満たす（ステップＳ２０６）。
【００４０】
復号部２０７は、秘密鍵Ｋを用いて暗号文Ｃ［ｉ］（ｉ＝１，・・・，ｐ）を復号し、平文情報Ｐ［ｉ］（ｉ＝１，・・・，ｐ）を得て出力する。拡大体演算部２０８は、暗号文Ｃ［ｉ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｉ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を用い、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得て出力する。拡大体演算部１０８は、Ｓ［０］＝Ｕ［ａ］とし、ｉ＝１，・・・，ｐについて、この処理を行って元Ｓ［ｐ］を得て出力する（ステップＳ２０７）。
【００４１】
以下にステップＳ２０７の具体例を示す。
≪Ｓ２０７−１≫
復号部２０７は、ｉ＝１に初期化する。
≪Ｓ２０７−２≫
ｉ≦ｐ−１であればＳ２０７−３に進み、ｉ＝ｐでればＳ２０７−６に進む。
≪Ｓ２０７−３≫
復号部２０７は、秘密鍵Ｋ、暗号文Ｃ［ｉ］、およびナンス値ＩＶを入力とし、秘密鍵Ｋを用い、暗号文Ｃ［ｉ］を復号して平文情報Ｐ［ｉ］∈ＧＦ（２ｎ）を得て出力する。「具体例」の場合、復号部２０７は、Ｐ［ｉ］＝ＥＫ（ＩＶ｜＜ｉ−１＞ｎ／２）（＋）Ｃ［ｉ］によって平文情報Ｐ［ｉ］∈｛０，１｝ｎを得て出力する。次にＳ２０７−４に進む。
≪Ｓ２０７−４≫
拡大体演算部２０８は、暗号文ＣＮ［ｉ］＝Ｃ［ｉ］、秘密情報Ｗ、および拡大体ＧＦ（２ｎ）の元Ｓ［ｉ−１］を入力とし、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｉ］を得て出力する。「具体例」の場合、拡大体演算部２０８は、演算Ｓ［ｉ］＝（Ｓ［ｉ−１］（＋）ＣＮ［ｉ］）（×）（Ｈ｜Ｌ）を行い、Ｓ［ｉ］∈｛０，１｝ｎを得て出力する。次にＳ２０７−５に進む。
≪Ｓ２０７−５≫
ｉ＋１を新たなｉとしてＳ１０７−２に戻る。
≪Ｓ２０７−６≫
復号部２０７は、秘密鍵Ｋ、暗号文Ｃ［ｐ］、およびナンス値ＩＶを入力とし、秘密鍵Ｋを用い、暗号文Ｃ［ｐ］を復号して平文情報Ｐ［ｐ］∈ＧＦ（２Ｌｅｎ（Ｃ［ｐ］））を得て出力する。「具体例」の場合、復号部２０７は、Ｐ［ｐ］＝ｍｓｂＬｅｎ（Ｃ［ｐ］）｛ＥＫ（ＩＶ｜＜ｐ−１＞ｎ／２）｝（＋）Ｃ［ｐ］によって平文情報Ｐ［ｐ］∈｛０，１｝Ｌｅｎ（Ｃ［ｐ］）を得て出力する。次にＳ２０７−７に進む。
≪Ｓ２０７−７≫
拡大体演算部２０８は、暗号文Ｃ［ｐ］、秘密情報Ｗ、および元Ｓ［ｐ−１］を入力とし、認証化暗号化時と同じ方法で暗号文Ｃ［ｐ］から得られる拡大体ＧＦ（２ｎ）の元ＣＮ［ｐ］を用いて演算Ｓ［ｐ］＝（Ｓ［ｐ−１］（＋）ＣＮ［ｐ］）（×）Ｗを行い、拡大体ＧＦ（２ｎ）の元Ｓ［ｐ］を得て出力する。「具体例」の場合、拡大体演算部２０８は、ＣＮ［ｐ］＝Ｃ［ｐ］｜０*∈｛０，１｝ｎとして演算Ｓ［ｐ］＝（Ｓ［ｐ−１］（＋）ＣＮ［ｐ］）（×）（Ｈ｜Ｌ）を行い、Ｓ［ｐ］∈｛０，１｝ｎを得て出力する（ステップＳ２０７の具体例の説明終わり）。
【００４２】
平文情報連結部２０９は、平文情報Ｐ［１］，・・・，Ｐ［ｐ］を入力とし、Ｐ［１］，・・・，Ｐ［ｐ］からなる平文メッセージＰを得て出力する。「具体例」の場合、平文情報連結部２０９は、Ｐ＝Ｐ［１］｜・・・｜Ｐ［ｐ］を平文メッセージＰとして出力する。また平文情報連結部２０９は、出力暗号文Ｃを入力とし、出力暗号文Ｃを構成する有限体ＧＦ（２）の元の個数（「具体例」の場合には出力暗号文Ｃのビット長）ＬＣ＝Ｌｅｎ（Ｃ）を得て出力する（ステップＳ２０９）。
【００４３】
認証子生成部２１０は、Ｓ［ｐ］に対応する検証用認証子Ｔ＋を得て出力する。認証子生成部２１０は、例えば、Ｓ［ｐ］、ＬＡおよびＬＣに対する像（関数値）である検証用認証子Ｔ＋を得て出力する。例えば認証子生成部２１０は、Ｓ［ｐ］、ＬＡおよびＬＣを入力とし、Ｓ*＝Ｓ［ｐ］（＋）（＜ＬＡ＞ｎ／２｜＜ＬＣ＞ｎ／２）を得、検証用認証子Ｔ＋＝ｍｓｂｔ（ＥＫ（Ｓ*））を得て出力する。「具体例」の場合にはＴ＋∈｛０，１｝ｔとなる。ただし、ｔは１以上の整数である（ステップＳ２１０）。
【００４４】
判定部２１１は、認証子Ｔおよび検証用認証子Ｔ＋を入力とし、認証子Ｔと検証用認証子Ｔ＋が等しいかを判定する（ステップＳ２１１）。Ｔ＝Ｔ＋である場合、出力部２１２が平文メッセージＰを出力し、認証復号処理を終了する（ステップＳ２１２）。Ｔ≠Ｔ＋でない場合、出力部２１２が不正エラーを示す特別シンボル⊥を出力し、認証復号処理を終了する（ステップＳ２１３）。
【００４５】
＜特徴＞
本形態では拡大体ＧＦ（２ｍ［ｊ］）（ただしｍ［ｊ］＜ｎ）上での乗算によって多項式ハッシュ関数の演算（例えば、ステップＳ１０７，Ｓ２０７）を行うため、拡大体ＧＦ（２ｎ）上での乗算によって多項式ハッシュ関数を行う従来方式よりも演算効率がよい。特に、ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２である場合には、従来方式から安全性を低下させることなく、演算効率を向上させることができる。ｎが偶数、ｑ＝２、ｍ［１］＝ｍ［２］＝ｎ／２の場合の共通鍵暗号方式の例としては、ブロックビット長ｎ＝１２８のＡＥＳがある。この場合に使用できる既約多項式の例は、ｘ６４＋ｘ４＋ｘ３＋ｘ＋１である。
【００４６】
＜変形例等＞
本発明は上述の実施形態に限定されるものではない。例えば、ｍ［１］，・・・，ｍ［ｑ］がすべて等しくてもよいし、そうでなくてもよい（ｍ［１］，・・・，ｍ［ｑ］の少なくとも一部が他と異なっていてもよい）。また、Ｘ（×）Ｙの演算量がＸとＹとの拡大体ＧＦ（２ｎ）上での乗算の演算量よりも少ないのであればｎやｑの値に限定はない。また、認証暗号化装置１００と認証復号装置２００とが通信可能に構成されるのではなく、可搬型記録媒体を介して情報をやり取りしてもよく、あるいは、認証暗号化装置１００と認証復号装置２００とが同一筺体内に構成されてもよい。また上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４８】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００５０】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００５１】
認証システム１
認証暗号化装置  １００
認証復号装置  ２００
【図１】
2014002230.tif 000005
【図２】
2014002230.tif 000006
【図３】
2014002230.tif 000007
【図４】
2014002230.tif 000008