JP7677407B2 - 認証暗号化装置、認証復号装置、認証暗号システム、方法及びプログラム - Google Patents

Description

本発明は、認証暗号化装置、認証復号装置、認証暗号システム、方法及びプログラムに関する。

事前に共有された秘密鍵を用いて、平文メッセージに対して暗号化と改ざん検知用の認証タグ計算とを同時に適用する認証暗号（Authenticated Encryption；ＡＥ）という技術が知られている。通信路に認証暗号ＡＥを適用することにより、盗聴に対する内容の秘匿と、不正な改ざんに対する検知とが可能となり、結果として通信内容に対する強力な保護が実現される。認証暗号技術としては、例えば、非特許文献１に開示された技術が知られている。ｂビット入出力（平文ブロックの長さがｂビット）のプリミティブ（暗号部品）を用いる場合、一般的に、安全性は最大でｂビットであるが、非特許文献１にかかるアルゴリズムＰＦＢωでは、ｂビットよりも高いωｂビットの安全性（セキュリティレベル）を実現可能である。

Yusuke Naito, Yu Sasaki, and Takeshi Sugawara、"Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation"、IACR Cryptology ePrint Archive: Report 2020/542、https://eprint.iacr.org/2020/542.pdf

非特許文献１にかかる技術では、安全性上の理由により、一度の認証暗号において処理できる平文ブロックの数に制限がある。したがって、非特許文献１にかかる技術では、安全性を高めることはできるものの、処理できる平文ブロックの数の制限により、長い平文を一度に暗号化することが困難である。

本開示の目的は、このような課題を解決するためになされたものであり、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能な、認証暗号化装置、認証復号装置、認証暗号システム、方法及びプログラムを提供することにある。

本開示にかかる認証暗号化装置は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するタグ生成手段と、を有する。

また、本開示にかかる認証復号装置は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するタグ生成手段と、前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、を有する。

また、本開示にかかる認証暗号システムは、認証暗号化装置と、前記認証暗号化装置との間で通信を行う認証復号装置と、を有し、前記認証暗号化装置は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第１の乱数計算手段と、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する第１のタグ生成手段と、を有し、前記認証復号装置は、前記ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第２の乱数計算手段と、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成する第２のタグ生成手段と、前記検査用のタグと、入力された前記認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、を有する。

また、本開示にかかる認証暗号化方法は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化し、前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する。

また、本開示にかかる認証復号方法は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号し、前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成し、前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行う。

また、本開示にかかるプログラムは、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化するステップと、前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するステップと、をコンピュータに実行させる。

また、本開示にかかるプログラムは、 ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号するステップと、
前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するステップと、
前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うステップと、
をコンピュータに実行させる。

本開示によれば、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能な、認証暗号化装置、認証復号装置、認証暗号システム、方法及びプログラムを提供できる。

比較例にかかる認証暗号化装置の構成を示す図である。 実施の形態１にかかる認証暗号システムの構成を示す図である。 実施の形態１にかかる認証暗号化装置の構成を示す図である。 実施の形態１にかかる認証暗号処理における演算の概略を示す図である。 実施の形態１にかかる認証暗号処理における演算の概略を示す図である。 実施の形態１にかかる認証暗号処理における演算の概略を示す図である。 実施の形態１にかかる認証暗号処理における演算の概略を示す図である。 実施の形態１にかかる認証暗号化装置の作用を説明するための図である。 実施の形態１にかかる認証復号装置の構成を示す図である。 実施の形態１にかかる認証復号処理における演算の概略を示す図である。 実施の形態１にかかる認証復号処理における演算の概略を示す図である。 実施の形態１にかかる認証復号装置の作用を説明するための図である。 実施の形態１にかかる認証暗号化装置で実行される認証暗号化方法を示すフローチャートである。 実施の形態１にかかる認証復号装置で実行される認証復号方法を示すフローチャートである。 実施の形態２にかかる認証暗号化装置の構成を示す図である。 実施の形態２にかかる認証暗号処理における演算の概略を示す図である。 実施の形態２にかかる認証暗号処理における演算の概略を示す図である。 実施の形態２にかかる認証暗号処理における演算の概略を示す図である。 実施の形態２にかかる認証暗号化装置の作用を説明するための図である。 実施の形態２にかかる認証復号装置の構成を示す図である。 実施の形態３にかかる認証暗号化装置の構成を示す図である。 実施の形態３にかかる認証復号装置の構成を示す図である。 各実施形態に係る装置およびシステムを実現可能な計算処理装置のハードウェア構成例を概略的に示すブロック図である。

（本開示にかかる実施形態の概要）
本開示の実施の形態の説明に先立って、本開示にかかる実施の形態の概要について説明する。なお、以下、本開示の実施形態を説明するが、以下の実施形態は請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。また、以下の説明において、使用されるインデックス（英文字）は、本明細書全体で共通のものとは限らない。例えば、インデックスｉは、ある文脈と別の文脈とにおいて、異なるものを意味することがある。

まず、認証暗号（ＡＥ）の基本的な入出力について説明する。なお、以下の説明では、秘密鍵Ｋを共有する２者としてＡｌｉｃｅとＢｏｂとの間の通信を考え、ＡｌｉｃｅからＢｏｂへ認証暗号による暗号化を行ったメッセージを通信するものとする。

認証暗号の暗号化関数をＥｎｃとし、復号関数をＤｅｃとする。また、暗号化したい平文をＭとし、さらにナンス（Ｎｏｎｃｅ（ノンス））と呼ばれる変数Ｎ（初期ベクトル）を導入する。また、関連データ（Ａｓｓｏｃｉａｔｅｄ Ｄａｔａ；ＡＤ）をＡとする。ここで、関連データＡ（ヘッダ）は、暗号化は行われないが改ざん検知は行われる値である。

まず、Ａｌｉｃｅ側の暗号化処理について説明する。Ａｌｉｃｅは、ナンスＮを生成後、（Ｃ，Ｔ）＝Ｅｎｃ＿Ｋ（Ｎ，Ａ，Ｍ）で表される処理を実行する。ここで、Ｅｎｃ＿Ｋは、秘密鍵である鍵Ｋをパラメータとした暗号化関数であり、Ｃは暗号文である。また、Ｔは、タグ（認証タグ）と呼ばれる、固定長の改ざん検出用の変数である。Ａｌｉｃｅは、ナンスＮ、関連データＡ、暗号文Ｃ及びタグＴの組（Ｎ，Ａ，Ｃ，Ｔ）を、Ｂｏｂに送信する。

次に、Ｂｏｂ側の復号処理について説明する。Ｂｏｂが受信した情報を（Ｎ’，Ａ’，Ｃ’，Ｔ’）とする。この場合、Ｂｏｂは、復号処理としてＤｅｃ＿Ｋ（Ｎ’，Ａ’，Ｃ’，Ｔ’）を実行する。なお、Ｄｅｃ＿Ｋは、鍵Ｋをパラメータとした復号関数である。通信の途中で第三者Ｅｖｅによる改ざんがあり、（Ｎ’，Ａ’，Ｃ’，Ｔ’）≠（Ｎ，Ａ，Ｃ，Ｔ）である場合、Ｄｅｃ＿Ｋ（Ｎ’，Ａ’，Ｃ’，Ｔ’）について、改ざんがあったことを示すエラーメッセージ（エラーシンボル⊥）が出力される。つまり、この場合、改ざんが検出される。一方、通信の途中で改ざんがなく、（Ｎ’，Ａ’，Ｃ’，Ｔ’）＝（Ｎ，Ａ，Ｃ，Ｔ）である場合、Ｄｅｃ＿Ｋ（Ｎ’，Ａ’，Ｃ’，Ｔ’）について、Ａｌｉｃｅが暗号化した平文Ｍが正しく復号される。

また、上記の処理においては、通常、暗号化においてナンスＮが過去の値と偶然一致してしまわないようにすることが重要である。このために、暗号化側では、カウンタなどの何らかの状態変数を用いて、ナンスの一致を防ぐ。すなわち、典型的には、状態変数として直前に使ったＮを記憶しておき、毎回Ｎをインクリメントすることで、ナンスＮが過去の値と重複しないことが、実現される。

また、非特許文献１では、暗号化と復号の際に、Ｔｗｅａｋ（トウィーク）と呼ばれる公開調整値（補助変数）を導入するＴｗｅａｋａｂｌｅブロック暗号（Tweakable Block Cipher；ＴＢＣ）と呼ばれるブロック暗号を用いている。つまり、ＴＢＣでは、ブロック暗号の入力にＴｗｅａｋを含めた鍵付き置換を行っている。そして、Ｔｗｅａｋが異なるＴＢＣは、それぞれ独立なブロック暗号とみなすことができる。

ここで、ＴｗｅａｋをＴｗとすると、ＴＢＣ関数は、以下の式１のように表される。

・・・（１）
なお、以降の説明において、式１の左辺（ＴＢＣ関数）を、「Ｅ＿Ｋ＾Ｔｗ^～（Ｍ）」、「Ｅ_Ｋ ^Ｔｗ～（Ｍ）」、又は、単に「Ｅ_Ｋ ^～」又は「Ｅ＿Ｋ^～」などと表記することがある。

図１は、比較例にかかる認証暗号化装置８０の構成を示す図である。図１は、非特許文献１にかかるＰＦＢωにおける暗号化方式を用いて実現された認証暗号化装置８０の構成を示している。また、図１は、比較例にかかる認証暗号化装置８０の演算の概略を示す図である。

比較例にかかる認証暗号化装置８０は、ＡＤ処理部８２と、暗号化部８４と、計算部８６と、タグ生成部８８とを有する。なお、便宜上、図１において、計算部８６は、前段部８６ａと後段部８６ｂとに分離して描かれているが、計算部８６は、一体であってもよい。つまり、計算部８６は、前段部８６ａと後段部８６ｂとが連続して構成されてもよい。

ＡＤ処理部８２は、関連データ（ＡＤ）を処理する。ＡＤ処理部８２には、関連データＡが入力される。ＡＤ処理部８２は、入力された関連データＡを、それぞれｂビットの長さのブロック（Ａ＿１，・・・，Ａ＿ａ）に分割する。つまり、関連データ（ＡＤ）ブロックＡ＿１，・・・，Ａ＿ａそれぞれのデータ長はｂビットである。なお、ａはＡＤブロックの数を示す。ＡＤ処理部８２は、各ＡＤブロックを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。

具体的には、ＡＤ処理部８２は、初期値Ｚ＿０（Ｚ_０）として０＾ｂ（０^ｂ）を設定する。ここで、０＾ｂは、ｂビットのオールゼロを示す。ＡＤ処理部８２は、初期値０＾ｂ（＝Ｚ＿０）と１ブロック目のＡＤブロックＡ＿１との排他的論理和（ＸＯＲ）により得られた値を、ＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、ＴＢＣ関数Ｅ_Ｋ ^～から、暗号化結果として、乱数であるＺ＿１が出力される。ＡＤ処理部８２は、この出力された暗号化結果Ｚ＿１と２ブロック目のＡＤブロックＡ＿２との排他的論理和により得られた値を、ＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、ＴＢＣ関数Ｅ_Ｋ ^～から、暗号化結果として、乱数であるＺ＿２が出力される。このように、ＡＤ処理部８２は、出力された暗号化結果Ｚ＿ｉと次の（ｉ＋１）ブロック目のＡＤブロックＡ＿（ｉ＋１）との排他的論理和により得られた値を、ＴＢＣ関数Ｅ_Ｋ ^～で暗号化する、という処理を繰り返す。なお、１≦ｉ≦ａである。

そして、ＡＤ処理部８２は、最後のＡＤブロックＡ＿ａと暗号化結果Ｚ＿（ａ－１）との排他的論理和により得られた値を、Ｈ＿１として、暗号化部８４に出力する。ここで、Ｈ＿１は、ｂビットの値である。また、ＡＤ処理部８２は、ＴＢＣ関数による暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿１，・・・，Ｚ＿（ａ－１）を、計算部８６に出力する。なお、Ｚは、Ｈ＿１を生成する際の途中で生成された値であるので、中間値であるとも言える。

なお、ＴＢＣ関数に入力されるＴｗｅａｋは、安全性上の理由により、図１に示すように、関連データＡのブロックインデックスｉ（１≦ｉ≦ａ）に対して、（０＾ｎ，ｉ，０，０）のような形式である必要がある。なお、「０＾ｎ（０^ｎ）」は、ｎビットのオールゼロを示す。また、ｎはナンスＮのデータ長（ビット数）を示す。なお、複数のＴＢＣ関数に入力されるＴｗｅａｋは互いに異なるが、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは、異なる平文が暗号化処理される場合でも同じであり得る。つまり、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは定数であり得る。例えば、１番目のＥ_ｋ ^～に入力されるＴｗｅａｋ（０^ｎ，１，０，０）は、ある平文Ｍａが暗号化処理される場合でも別の平文Ｍｂが暗号化処理される場合でも、同じであり得る。また、これらのことは、後述する暗号化部８４及びタグ生成部８８におけるＴＢＣ関数に入力されるＴｗｅａｋについても、ナンスの値を除き、同様である。

また、関連データＡのデータ長は、ｂビットの倍数であるとする。なお、Ｔｗｅａｋを増やせば、任意長（つまりｂビットの倍数とならないような長さ）の関連データについてＡＤ処理が可能となる。しかしながら、このことはこの分野の研究者にとっては自明なことなので、説明を省略する。このことは、後述する本実施の形態においても同様である。また、ＡＥの入力として、関連データ（ＡＤ）が含まれない（空である）場合がある。その場合は、ＡＤ処理部８２は必要ない。その場合は、図１の暗号化部８４におけるＨ＿１を０＾ｂとすればよい。

暗号化部８４は、平文の暗号化を行う。暗号化部８４には、ナンスＮ、平文Ｍ、及び、ＡＤ処理部８２から出力されたＨ＿１が入力される。暗号化部８４は、入力された平文Ｍを、それぞれｂビットの長さのブロック（Ｍ＿１，・・・，Ｍ＿ｍ）に分割する。つまり、平文ブロックＭ＿１，・・・，Ｍ＿ｍそれぞれのデータ長はｂビットである。なお、ｍは平文ブロックの数を示す。暗号化部８４は、各平文ブロックを、鍵Ｋ、ナンスＮ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。

具体的には、暗号化部８４は、初期値としてＨ＿１を設定する。暗号化部８４は、初期値Ｈ＿１をＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、ＴＢＣ関数Ｅ_Ｋ ^～から、暗号化結果として、乱数であるＺ＿ａが出力される。そして、暗号化部８４は、この出力された暗号化結果Ｚ＿ａと１つ目の平文ブロックＭ＿１との排他的論理和により、暗号文ブロックＣ＿１を得る。なお、Ｚは、暗号文ブロックを生成する際の途中で生成される値であるので、中間値であるとも言える。

次に、暗号化部８４は、平文ブロックＭ＿１をＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、暗号化結果として、乱数であるＺ＿（ａ＋１）が出力される。暗号化部８４は、暗号化結果Ｚ＿（ａ＋１）と２つ目の平文ブロックＭ＿２との排他的論理和により、暗号文ブロックＣ＿２を得る。このように、暗号化部８４は、ｉブロック目の平文ブロックＭ＿ｉの暗号化結果Ｚ＿（ａ＋ｉ）と次の（ｉ＋１）ブロック目の平文ブロックＭ＿（ｉ＋１）との排他的論理和により、暗号文ブロックＣ＿（ｉ＋１）を得る、という処理を繰り返す。なお、０≦ｉ≦ｍである。

そして、暗号化部８４は、最後の平文ブロックＭ＿ｍがＴＢＣ関数Ｅ_Ｋ ^～で暗号化されたら、その暗号化結果Ｚ＿（ａ＋ｍ）を、Ｔ＿１として、タグ生成部８８に出力する。なお、Ｔ＿１は、ｂビットの値であり、タグの一部となる。また、暗号化部８４は、生成された暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、暗号文Ｃ＝Ｃ＿１｜｜・・・｜｜Ｃ＿ｍとして出力する。ここで、「｜｜」は、ビット列の連結を示す。また、暗号文Ｃは、平文Ｍと同じ長さ（ビット長）である。また、暗号化部８４は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿ａ，・・・，Ｚ＿（ａ＋ｍ）を、計算部８６に出力する。

なお、ＴＢＣ関数に入力されるＴｗｅａｋは、安全性上の理由により、図１に示すような形式である必要がある。つまり、暗号化部８４は、平文Ｍのブロックインデックスｉ（１≦ｉ≦ｍ）に対して、（Ｎ，ａ，ｉ，０）をＴｗｅａｋとして入力するＴＢＣ関数の暗号化結果を用いてＭ＿ｉを暗号化して、Ｃ＿ｉを得る。なお、暗号化部８４の最後に用いられるＴＢＣ関数（Ｍ＿ｍを入力しＴ＿１を得るもの）に入力されるＴｗｅａｋは、（Ｎ，ａ，ｍ，１）である。また、上述したように、複数のＴＢＣ関数に入力されるＴｗｅａｋは互いに異なるが、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは、異なる平文が暗号化処理される場合でも、ナンスＮの値を除き、同じであり得る。つまり、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは、ナンスＮの値を除き、定数であり得る。なお、このことは、後述する実施の形態においても同様である。

また、関連データと同様に、平文Ｍのデータ長は、ｂビットの倍数であるとする。なお、Ｔｗｅａｋを増やせば、任意長（つまりｂビットの倍数とならないような長さ）の平文について平文処理が可能となる。しかしながら、このことはこの分野の研究者にとって自明なことなので、説明を省略する。また、上述したように、関連データ（ＡＤ）がＡＥの入力に含まれない場合は、Ｈ＿１を０＾ｂとすればよい。

計算部８６は、ＡＤ処理部８２及び暗号化部８４で生成される乱数Ｚ＿１，・・・，Ｚ＿（ａ－１），Ｚ＿ａ，・・・，Ｚ＿（ａ＋ｍ）を受け付ける。つまり、ＡＤ処理部８２及び暗号化部８４におけるＴＢＣ関数の出力値は、全て、計算部８６に入力される。そして、そして、計算部８６は、これらの乱数と、所定の行列ＡＭ（Alpha Matrix）とを用いて、ω－１個の値を生成する。

ここで、以下の式２に示すように、所定の行列ＡＭは、所定の値α＿（ｉ，ｊ）を要素とする、（ω－１）×（ａ＋ｍ）のサイズの行列である。ここで、ωは、所定のセキュリティレベルを示す値であり、３以上の整数である。また、ここでいうｉは、行列ＡＭの行数のインデックスであり、ラインのインデックスに対応する。なお、２≦ｉ≦ωである。また、ｊは、行列ＡＭの列数のインデックスであり、入力される乱数Ｚのインデックス、つまりブロックインデックスに対応する。なお、１≦ｊ≦ａ＋ｍである。

・・・（２）

計算部８６は、以下の式３に示すようにして、行列ＡＭを用いて乱数Ｚ＿１，・・・，Ｚ＿（ａ－１），Ｚ＿ａ，・・・，Ｚ＿（ａ＋ｍ）を処理して、Ｈ＿２，・・・，Ｈ＿ωを生成する。

・・・（３）

また、式３から、各ラインｉ（２≦ｉ≦ω）に対して、以下の式４が成り立つ。

・・・（４）

ここで、行列ＡＭの要素α＿（ｉ，ｊ）は、有限体ＧＦ（２＾ｂ）の元である。また、行列ＡＭの要素α＿（ｉ，ｊ）は、ｂビットの特定の値である。また、α＿（ｉ，ｊ）・Ｚ＿ｊの「・」は、有限体ＧＦ（２＾ｂ）上の乗算を意味し、図１では、円の中に「×」が描かれた記号で示されている。また、円の中に「＋」が描かれた記号は、排他的論理和（ＸＯＲ）を示す。

つまり、計算部８６は、ω－１個のラインｉ（２≦ｉ≦ω）それぞれについて、乱数Ｚ＿ｊとα＿（ｉ，ｊ）との乗算値の排他的論理和を行うことによって、Ｈ＿ｉを算出する。なお、比較例（非特許文献１）では、高い安全性を得るため、乱数Ｚ＿ｊを１個からω－１個に拡大している。したがって、ωは、拡大数を意味するとも言える。ここで、Ｈ＿２，・・・，Ｈ＿ωは、それぞれｂビットの値であり、タグ生成処理に用いられる。そして、計算部８６は、得られたＨ＿２，・・・，Ｈ＿ωを、タグ生成部８８に出力する。なお、式２に示した所定の行列ＡＭは、安全性上の理由により、特定の条件を満たす必要がある。詳しくは後述する。

タグ生成部８８は、タグＴを生成する。タグ生成部８８には、暗号化部８４からＴ＿１が入力され、計算部８６からＨ＿２，・・・，Ｈ＿ωが入力される。さらに、タグ生成部８８には、ナンスＮが入力される。タグ生成部８８は、Ｔ＿１を、そのままタグの一部として出力する。また、タグ生成部８８は、Ｈ＿２，・・・，Ｈ＿ωを、それぞれ、鍵Ｋ、ナンスＮ及び定数であるＴｗｅａｋが入力されたＴＢＣ関数を用いて暗号化する。これにより、暗号化結果として、Ｔ＿２，・・・，Ｔ＿ωが得られる。そして、タグ生成部８８は、それらの暗号化結果をタグとして出力する。つまり、タグ生成部８８は、Ｔ＿１，・・・，Ｔ＿ωを、タグＴ＝Ｔ＿１｜｜・・・｜｜Ｔ＿ωとして出力する。

なお、ＴＢＣ関数に入力されるＴｗｅａｋは、安全性上の理由により、図１に示すような形式である必要がある。つまり、タグ生成部８８は、Ｈのインデックスｉ（２≦ｉ≦ω）に対して、（Ｎ，ａ，ｍ，ｉ）をＴｗｅａｋとして入力するＴＢＣ関数の暗号化結果を用いてＨ＿ｉを暗号化して、Ｔ＿ｉを得る。また、上述したように、複数のＴＢＣ関数に入力されるＴｗｅａｋは互いに異なるが、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは、異なる平文が暗号化処理される場合でも、ナンスＮの値を除き、同じであり得る。つまり、各ＴＢＣ関数に入力されるＴｗｅａｋそれぞれは、ナンスＮの値を除き、定数であり得る。

ここで、比較例にかかる問題点について説明する。比較例にかかる認証暗号処理（ＡＥ）では、安全性上の制限により、一度に処理できるＡＤブロック数と平文ブロック数との合計が（２＾ｂ－１）個以下である必要がある。なお、関連データの入力がない場合、安全性上の制限により、一度に処理できる平文ブロック数は、（２＾ｂ－２）個以下である必要がある。すなわち、安全性上の制限により、ＡＤブロック数と平文ブロック数との合計又は平文ブロック数の合計が上記の条件を満たさないと、式２に示したα＿ｉｊの行列ＡＭの、以下に説明する条件を満たすことができなくなるからである。

すなわち、行列ＡＭは、ＭＤＳ（Maximum Distance Separable）行列でなければならない。つまり、行列ＡＭの小行列で正方行列となるものが、全て正則である必要がある。ここで、「小行列」とは、行列から特定の行（単数でも複数でもよい）及び特定の列（単数でも複数でもよい）を取り除くことでできる行列のことである。そして、行列ＡＭが上記条件を満たさない場合の安全性は、現在、知られていない。したがって、行列ＡＭは、ＭＤＳ行列であることが必要である。

なお、行列ＡＭについて、列数が２＾ｂ－１を超えるとき、上記条件を満たすような行列は存在しないことが数学的に証明できる。ここで、「２＾ｂ－１」というのは、有限体ＧＦ（２＾ｂ）の乗法群の元の個数（つまり０以外のｂビット値の個数）である。したがって、ａ＋ｍ≦２＾ｂ－１でなければならない。なお、関連データ（ＡＤ）が空の場合、ＡＤ処理と暗号化処理との違いのため、以下に説明するように、ｍ≦２＾ｂ－２である必要がある。

すなわち、関連データが空でない場合、ａ個のＡＤブロックの関連データＡを処理するためには、式２の行列ＡＭについて、列数をａ－１とする行列ＡＭを準備する必要がある。なぜならば、図１に示すように、ＴＢＣ関数の前後で、ＡＤブロックを処理できるからである。つまり、１つ目のＴＢＣ関数の処理の前で１つ目のＡＤブロックＡ＿１が処理され、そのＴＢＣ関数の後で２つ目のＡＤブロックＡ＿２が処理される。また、２つ目のＴＢＣ関数の処理の前で２つ目のＡＤブロックＡ＿２が処理され、そのＴＢＣ関数の後で３つ目のＡＤブロックＡ＿３が処理される。以後、これを繰り返して、最終的には、ａ－１番目のＴＢＣ関数の処理の前でａ－１番目のＡＤブロックＡ＿（ａ－１）が処理され、そのＴＢＣ関数の後でａ番目つまり最後のＡＤブロックＡ＿ａが処理される。

また、ｍ個の平文ブロックの平文Ｍを処理するためには、図１に示すように、式２の行列ＡＭについて、列数をｍ＋１とする行列ＡＭを準備する必要がある。なぜならば、図１に示すように、ｍ番目のＴＢＣ関数とｍ番目（つまり最後）の平文ブロックＭ＿ｍとを用いて暗号文ブロックＣ＿ｍを生成して、さらにそのｍ番目の平文ブロックＭ＿ｍをｍ＋１番目のＴＢＣ関数で処理する必要があるからである。これより、関連データが空でない場合は、（ａ－１）＋（ｍ＋１）≦２＾ｂ－１、つまりａ＋ｍ≦２＾ｂ－１である必要がある。つまり、式２の行列ＡＭにおいて、ａ＋ｍ≦２＾ｂ－１であれば、比較例（非特許文献１）にかかるＰＦＢωにおいても、ＡＥ処理が可能である。一方、関連データが空である場合、ｍ＋１≦２＾ｂ－１、つまりｍ≦２＾ｂ－２である必要がある。つまり、式２の行列ＡＭにおいて、ｍ≦２＾ｂ－２であれば、比較例（非特許文献１）にかかるＰＦＢωにおいても、ＡＥ処理が可能である。

このように、比較例（非特許文献１）にかかるＰＦＢωでは、一度に処理できるブロック数（平文ブロック数、又はＡＤブロック数と平文ブロック数との合計）に制限がある。ここで、ＰＦＢωでは、上述したように、ωｂビットという比較的高い安全性を実現できる。したがって、理想的には、１回のＡＥ処理における入力について、処理可能な平文長は、２＾（ωｂ）ブロック程度の長さであることが望ましい。しかしながら、ＰＦＢωでは、入力ブロック数の制限が、ｂビット安全性のＡＥの場合と同じとなってしまっており、効率が悪い。

これに対し、本実施の形態にかかる認証暗号では、以下に説明するように、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能である。つまり、本実施の形態にかかる認証暗号では、ｂビット入出力ＴＢＣ関数を用いて、ｂビットより大きな安全性を実現し、かつ（２＾ｂ－１）個以上のブロック数を処理することが可能である。なお、本実施の形態では、２ｂビット安全性より大きな安全性レベルを対象とできる。

（実施の形態１）
以下、実施の形態について、図面を参照しながら説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。また、各図面において、同一の要素には同一の符号が付されており、必要に応じて重複説明は省略されている。なお、実施の形態１にかかる認証暗号方法は、上述した比較例（非特許文献１）にかかるＰＦＢωを改良した構成に対応する。

図２は、実施の形態１にかかる認証暗号システム１の構成を示す図である。認証暗号システム１は、認証暗号化装置１０と、認証復号装置２０とを有する。認証暗号化装置１０及び認証復号装置２０は、物理的に一体であってもよいし、別個であってもよい。認証暗号化装置１０及び認証復号装置２０が物理的に互いに別個である場合、認証暗号化装置１０及び認証復号装置２０は、有線又は無線を介して通信可能に接続されている。また、後述する認証暗号化装置１０の構成要素が、互いに別の装置で実現されてもよい。同様に、後述する認証復号装置２０それぞれの構成要素が、互いに別の装置で実現されてもよい。

なお、以下の説明では、特に断りのない限り、関連データＡ、平文Ｍ又は暗号文Ｃ等を分割して得られた複数のブロックのうちの１ブロックの長さを、所定長であるｂビットとする。また、上述したＡｌｉｃｅとＢｏｂとの間の通信の例において、認証暗号化装置１０はＡｌｉｃｅに対応し、認証復号装置２０はＢｏｂに対応する。つまり、認証暗号化装置１０及び認証復号装置２０との間で通信が行われる。

＜認証暗号化装置＞
図３は、実施の形態１にかかる認証暗号化装置１０の構成を示す図である。また、図４～図７は、実施の形態１にかかる認証暗号処理における演算の概略を示す図である。図３に示すように、認証暗号化装置１０は、入力部１００と、分割部１０２と、ナンス生成部１０４と、ＡＤ処理部１１０と、暗号化部１２０と、乱数計算部１３０と、タグ生成部１４０と、出力部１５０とを有する。

認証暗号化装置１０は、例えばコンピュータ等の情報処理装置によって実現可能である。つまり、認証暗号化装置１０は、ＣＰＵ（Central Processing Unit）などの演算装置と、メモリ又はディスクなどの記憶装置とを有している。認証暗号化装置１０は、例えば、記憶装置に格納されたプログラムを演算装置が実行することで、上記の各構成要素を実現する。このことは、後述する他の実施の形態においても同様である。

入力部１００は、入力手段としての機能を有する。分割部１０２は、分割手段としての機能を有する。ナンス生成部１０４は、ナンス生成手段としての機能を有する。ＡＤ処理部１１０は、関連データ処理手段としての機能を有する。暗号化部１２０は、暗号化手段としての機能を有する。乱数計算部１３０は、乱数計算手段（計算手段）としての機能を有する。タグ生成部１４０は、タグ生成手段としての機能を有する。出力部１５０は、出力手段としての機能を有する。

入力部１００は、暗号化の対象となる平文Ｍ、及び関連データＡの入力を受け付ける。入力部１００は、例えば、キーボードなどの入力装置により実現されてもよい。入力部１００は、例えば、ネットワークを介して接続された外部装置などから、平文Ｍ及び関連データＡの入力を受け付けてもよい。なお、関連データＡが存在しない場合もあり、この場合は、関連データＡは入力されない。入力部１００は、平文Ｍ及び関連データＡを、分割部１０２に出力する。

分割部１０２は、平文Ｍ及び関連データＡそれぞれを、所定長のブロックに分割する。具体的には、分割部１０２は、平文Ｍを、それぞれｂビットの平文ブロックＭ＿１，・・・，Ｍ＿ｍに分割する。なお、ｍは、平文ブロックの数である。分割部１０２は、平文ブロックＭ＿１，・・・，Ｍ＿ｍを、暗号化部１２０に出力する。また、分割部１０２は、関連データＡを、それぞれｂビットの長さのＡＤブロックＡ＿１，・・・，Ａ＿ａに分割する。なお、ａは、ＡＤブロックの数である。分割部１０２は、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、ＡＤ処理部１１０に出力する。

また、分割部１０２は、分割されたＡＤブロックＡ＿１，・・・，Ａ＿ａ及び平文ブロックＭ＿１，・・・，Ｍ＿ｍを、それぞれブロック数（２＾ｂ－２）個の区域（グループ）に区分けする。つまり、１つの区域には、（２＾ｂ－２）個のブロックが含まれることとなる。ここで、各区域を、区域＃１，・・・，区域＃βとする。ここで、βは、区域数である。区域＃ｋは、ｋ番目の区域を示す。なお、１≦ｋ≦βである。このとき、分割部１０２は、データ列Ｄ＝Ａ＿１｜｜・・・｜｜Ａ＿ａ｜｜Ｍ＿１｜｜・・・｜｜Ｍ＿ｍを、データ列の先頭のブロックから、区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けしてもよい。

具体的には、分割部１０２は、区域＃１に全てのＡＤブロックＡ＿１，・・・，Ａ＿ａが含まれるように、区分けを行う。そして、ａ＜２＾ｂ－２の場合、分割部１０２は、ｍ’個の平文ブロックが区域＃１に含まれるように、区分けを行う。ここで、ｍ’は区域＃１（１区域目）に含まれる平文ブロックの数である。そして、ｍ’は、ａ＋ｍ’＝２＾ｂ－２を満たす。そして、実施の形態１では、ｍ＞ｍ’であることに留意されたい。

そして、分割部１０２は、残りの（ｍ－ｍ’）個の平文ブロックを、区域＃２～区域＃βに区分けする。以後、特に言及しない限り、ａ＜２＾ｂ－２であるとして説明する。なお、βは、ＡＤブロックの数ａ及び平文ブロックの数ｍ、及び、２＾ｂ－２の値（つまりｂの値）に応じて決まる値である。すなわち、（ａ＋ｍ）ｍｏｄ（２＾ｂ－２）＝０である場合、βは、除算（ａ＋ｍ）／（２＾ｂ－２）の商に対応する。一方、（ａ＋ｍ）ｍｏｄ（２＾ｂ－２）≠０である場合、βは、除算（ａ＋ｍ）／（２＾ｂ－２）の商に１を加算した値に対応する。

なお、ａ＝２＾ｂ－２の場合、区域＃１に区分けされる（２＾ｂ－２）個のブロックは、全て、ＡＤブロックとなる。そして、分割部１０２は、区域＃２に、データ列Ｄ＝Ｍ＿１｜｜・・・｜｜Ｍ＿ｍの先頭のブロックから（２＾ｂ－２）個の平文ブロックを区分けする。

また、ａ＞２＾ｂ－２の場合、区域＃１に区分けされる（２＾ｂ－２）個のブロックは、全て、ＡＤブロックとなる。そして、残りのＡＤブロックが、区域＃２に区分けされる。そして、全てのＡＤブロックＡ＿１，・・・，Ａ＿ａが区域＃１及び区域＃２に区分けされた場合、区域＃２に区分けされたＡＤブロックと平文ブロックとの合計が（２＾ｂ－２）個となるように、区域＃２に平文ブロックが区分けされる。ここで、区域＃２に区分けされる平文ブロックの数をｍ’’とすると、ａ＋ｍ’’＝２×（２＾ｂ－２）である。なお、区域＃１及び区域＃２にＡＤブロックが区分けされてもなお全てのＡＤブロックの区分けが完了しない場合、さらに、同様にして、区域＃３に、ＡＤブロックが区分けされる。

なお、関連データが空の場合、分割部１０２は、データ列Ｄ＝Ｍ＿１｜｜・・・｜｜Ｍ＿ｍを、データ列の先頭から区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けする。このとき、区域＃１に区分けされた平文ブロックの数をｍ’とすると、ｍ’＝２＾ｂ－２となる。

なお、区域＃ｋに区分けされた平文ブロックのビット列を「区域平文ブロックＭ［ｋ］」とすると、平文Ｍは、Ｍ＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［β］とも表記され得る。このとき、少なくともＭ［１］及びＭ［β］以外の区域平文ブロックＭ［ｋ］に含まれる平文ブロックの数は、（２＾ｂ－２）個となる。また、関連データが空の場合、区域平文ブロックＭ［１］に含まれる平文ブロックの数も、（２＾ｂ－２）個となる。

ここで、ブロック数（２＾ｂ－２）個の区域にブロック（ＡＤブロック及び平文ブロック）を区分けすることによって、後述するように、比較例にかかるＰＦＢωの手法を用いて、１つの区域ごとに暗号化及び乱数計算を行うことができる。これにより、ＰＦＢωにおいて問題となるブロック数の制限によらないで、ＰＦＢωにおける安全性を実現することが可能となる。

なお、上記では、関連データが空でない場合はａ＋ｍ≦２＾ｂ－１である必要があり、関連データが空である場合はｍ≦２＾ｂ－２である必要があると述べた。しかしながら、処理の複雑さを抑制するため、実施の形態１では、１つの区域ごとのブロック数を（２＾ｂ－２）個とする。したがって、実施の形態１では、後述するように、（２＾ｂ－２）個のブロック（区域）ごとに暗号化及び乱数計算を行う。これにより、実施の形態１では、ａ＋ｍ＞２＾ｂ－１であっても、平文Ｍに対して一度に認証暗号を行うことができる。詳しくは後述する。

ナンス生成部１０４は、過去の値と重複がないようにナンスＮを生成する。つまり、ナンス生成部１０４は、過去に生成された値とは異なるナンスＮを生成する。具体的には、例えば、ナンス生成部１０４は、最初に任意の固定値を出力する。また、ナンス生成部１０４は、直前に生成したナンスの値を記憶している。そして、ナンス生成部１０４は、２回目以降にナンスＮを生成する際に、記憶された直前の値に１を加えた値を出力する。このように、ナンス生成部１０４は、１つ前に既に出力した値に１を加えた値を出力することで、過去に生成した値とは異なるナンスＮを生成してもよい。なお、ナンス生成部１０４は、過去に生成した値とは異なる値を生成可能ならば、上述した例とは異なる方法でナンスを生成してもよい。ナンス生成部１０４は、生成されたナンスＮを、暗号化部１２０及びタグ生成部１４０に出力する。また、ナンス生成部１０４は、生成されたナンスＮを、出力部１５０に出力してもよい。

ＡＤ処理部１１０は、図１に示したＡＤ処理部８２と同様に、関連データＡを処理する。つまり、ＡＤ処理部１１０は、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。このとき、ＡＤ処理部１１０は、上述した区域ごとに、ＡＤブロックを処理する。なお、ａ＜２＾ｂ－２であれば、ＡＤ処理部１１０の処理は、ＡＤ処理部８２の処理と実質的に同様となる。ＡＤ処理部１１０は、Ｈ＿１を暗号化部１２０に出力する。また、ＡＤ処理部１１０は、ＴＢＣ関数の出力値である乱数Ｚ＿１，・・・，Ｚ＿（ａ－１）を乱数計算部１３０に出力する。

なお、ＡＤ処理部１１０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、ＡＤ処理部８２において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと異なり得る。詳しくは後述する。

暗号化部１２０は、図１に示した暗号化部８４と同様に、平文Ｍを処理する。つまり、暗号化部１２０は、平文ブロックＭ＿１，・・・，Ｍ＿ｍを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。そして、暗号化部１２０は、平文ブロックと、この平文ブロックの前の平文ブロックをＴＢＣ関数を用いて暗号化して得られた暗号化結果との排他的論理和によって、暗号文ブロックを生成する。このとき、暗号化部１２０は、上述した区域ごとに、平文ブロック（平文）を暗号化する。つまり、暗号化部１２０は、区域＃１に含まれる平文ブロックについて、暗号化部８４と同様に暗号化を行う。そして、暗号化部１２０は、区域＃２に含まれる平文ブロックについて、暗号化部８４と同様に暗号化を行う。以降、暗号化部１２０は、区域＃ｋに含まれる平文ブロックについて、暗号化部８４と同様に暗号化を行う。つまり、暗号化部１２０は、区域＃ｋに含まれる区域平文ブロックＭ［ｋ］について、暗号化を行う。

暗号化部１２０は、生成された暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、暗号文Ｃ＝Ｃ＿１｜｜・・・｜｜Ｃ＿ｍとして、出力部１５０に出力する。また、暗号化部１２０は、区域＃ｋに含まれる区域平文ブロックＭ［ｋ］について暗号化を行って、区域暗号文ブロックＣ［ｋ］を得る。ここで、区域暗号文ブロックＣ［ｋ］は、区域平文ブロックＭ［ｋ］と同じブロック数の暗号文ブロックから構成される。暗号化部１２０は、各区域で得られた乱数Ｚ（ＴＢＣ関数の出力値）を、乱数計算部１３０に出力する。また、暗号化部１２０は、各区域において、最後の平文ブロックがＴＢＣ関数で処理されて得られた暗号化結果Ｚを、乱数Ｓ＿１として、タグ生成部１４０に出力する。暗号化部１２０の処理の詳細については、後述する。

なお、暗号化部１２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、暗号化部８４において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと異なり得る。詳しくは後述する。なお、区域ごとに行われるＡＤ処理及び暗号化処理等で用いられるＴＢＣ関数に入力されるＴｗｅａｋを互いに区別するため、実施の形態１にかかるＴｗｅａｋの桁数は、比較例にかかるＴｗｅａｋの桁数よりも多くなっている。つまり、比較例では、１つの区域のみの処理が実行されるのに対し、実施の形態１では、複数の区域について処理が実行されるので、その分、Ｔｗｅａｋを区別するために桁数を多くする必要がある。

乱数計算部１３０は、図１に示した計算部８６と同様に、ＡＤ処理部１１０及び暗号化部１２０で生成される乱数Ｚと、所定の行列ＡＭとを用いて、タグを生成するための値（乱数）を計算する。なお、実施の形態１にかかる行列ＡＭを、以下の式５に示す。ここで、行列ＡＭは、所定の値α＿（ｉ，ｊ）を要素とする、（ω－１）×（２＾ｂ－１）のサイズの行列である。

・・・（５）

乱数計算部１３０は、区域ごとに、乱数Ｓを計算する。具体的には、乱数計算部１３０は、区域ごとに、ＡＤ処理部１１０及び暗号化部１２０で生成される乱数Ｚと、所定の行列ＡＭとを用いて、ω－１個の乱数Ｓの組（Ｓ＿２，・・・，Ｓ＿ω）を生成する。ここで、乱数Ｓの組は、タグＴを生成するために使用される。乱数計算部１３０は、各区域において、ω－１個のラインｉ（２≦ｉ≦ω）それぞれについて、乱数Ｚ＿ｊとα＿（ｉ，ｊ）との乗算値の排他的論理和を行うことによって、Ｓ＿ｉを算出する。

つまり、乱数計算部１３０は、各区域＃ｋにおいて、以下の式６に示すように、行列ＡＭを用いて乱数Ｚ＿１＾（ｋ），・・・，Ｚ＿（２＾ｂ－１）＾（ｋ）を処理して、乱数の組Ｓ＿２＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。つまり、乱数計算部１３０は、各区域＃ｋについて、式５に示した同じ行列ＡＭを用いて、乱数の組を生成する。ここで、ｋは、区域数のインデックスである。

・・・（６）

なお、式６から、ｉ（２≦ｉ≦ω）に対して、以下の式７が成り立つ。

・・・（７）

ここで、乱数計算部１３０は、区域ごとに、Ｚとαとの乗算値の排他的論理和の各ラインの初期値をリセットする。つまり、乱数計算部１３０は、各区域について、ラインｉの初期値を、０＾ｂとする。言い換えると、乱数計算部１３０は、区域ごとに、乱数の組が生成される複数のラインそれぞれの初期値を、リセットする。乱数計算部１３０の処理の詳細については後述する。乱数計算部１３０は、各区域＃ｋについて生成された乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を、タグ生成部１４０に出力する。なお、上述したように、各区域＃ｋにおける乱数Ｓ＿１＾（ｋ）については、暗号化部１２０によって生成され、タグ生成部１４０に出力される。

図４は、１区域目つまり区域＃１についての、ＡＤ処理部１１０及び乱数計算部１３０の演算の概略を示す図である。また、図５は、１区域目つまり区域＃１についての、暗号化部１２０及び乱数計算部１３０の演算の概略を示す図である。また、図６は、２区域目つまり区域＃２についての、暗号化部１２０及び乱数計算部１３０の演算の概略を示す図である。なお、便宜上、図４及び図５において、乱数計算部１３０は、前段部１３０ａと後段部１３０ｂとに分離して描かれているが、乱数計算部１３０は、一体であってもよい。つまり、乱数計算部１３０は、前段部１３０ａと後段部１３０ｂとが連続して構成されてもよい。実際に、図６では、乱数計算部１３０は、一体に描かれている。

図４に示すように、ＡＤ処理部１１０は、区域＃１について、ＡＤブロックＡ＿１，・・・，Ａ＿ａに対して、図１に示したＡＤ処理部８２と実質的に同様の処理を行う。そして、ＡＤ処理部１１０は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ－１）＾（１）を、乱数計算部１３０に出力する。なお、上述したように、Ｚ＿ｊ＾（ｋ）のｋは、区域数のインデックスである。つまり、乱数Ｚ＿１＾（１）の「（１）」は、区域＃１（１区域目）において生成された乱数であることを示す。また、ＡＤ処理部１１０は、最後のＡＤブロックＡ＿ａと暗号化結果Ｚ＿（ａ－１）＾（１）との排他的論理和により得られた値を、Ｈ＿１として、暗号化部１２０に出力する。なお、図４～図６の例では、ａ＜２＾ｂ－２であるので、ＡＤ処理部１１０は、区域＃１についてのみ、処理を行う。

また、図５に示すように、暗号化部１２０は、区域＃１について、平文ブロックＭ＿１，・・・，Ｍ＿ｍのうちのＭ＿１，・・・，Ｍ＿ｍ’に対して、図１に示した暗号化部８４と実質的に同様の処理を行う。そして、暗号化部１２０は、Ｍ＿１，・・・，Ｍ＿ｍ’にそれぞれ対応する暗号文ブロックＣ＿１，・・・，Ｃ＿ｍ’を得る。また、暗号化部１２０は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を、乱数計算部１３０に出力する。なお、暗号化部１２０は、区域＃１における最後の平文ブロックＭ＿ｍ’を区域＃１における最後のＴＢＣ関数で暗号化することにより、区域＃１における最後の乱数Ｚ＿（ａ＋ｍ’）＾（１）を得る。また、暗号化部１２０は、最後の平文ブロックＭ＿ｍ’がＴＢＣ関数で暗号化されたら、その暗号化結果Ｚ＿（ａ＋ｍ’）＾（１）を、Ｓ＿１＾（１）として、乱数計算部１３０に出力する。

ここで、上述したように、ＡＤ処理部１１０及び暗号化部１２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、ＡＤ処理部８２及び暗号化部８４において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと異なる。ＡＤ処理部１１０において使用されるＴＢＣ関数に入力されるＴｗｅａｋは、関連データＡのブロックインデックスｉ（１≦ｉ≦ａ）に対して、（０＾ｎ，ｉ，０，０，０）となる。また、暗号化部１２０において使用されるＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉ（１≦ｉ≦ｍ’）に対して、（Ｎ，ａ，ｉ，０，０）となる。なお、区域＃１について、暗号化部１２０の最後に用いられるＴＢＣ関数（Ｍ＿ｍ’を入力しＳ＿１＾（１）を得るもの）に入力されるＴｗｅａｋは、（Ｎ，ａ，ｍ’，１，０）である。このようにＴｗｅａｋを設定することによって、あるＴｗｅａｋが他のＴｗｅａｋと一致することがなくなる。

また、図４及び図５に示すように、乱数計算部１３０は、区域＃１について、ＡＤ処理部１１０及び暗号化部１２０で生成される乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ－１）＾（１），Ｚ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。つまり、乱数計算部１３０は、上記の式６により、式５に示した行列ＡＭを用いて、乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ－１）＾（１），Ｚ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。これにより、乱数計算部１３０は、区域＃１についての乱数の組Ｓ＿２＾（１），・・・，Ｓ＿ω＾（１）を生成する。言い換えると、乱数計算部１３０は、乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）それぞれと行列ＡＭの対応する要素との乗算値の排他的論理和を計算することによって、乱数の組Ｓ＿２＾（１），・・・，Ｓ＿ω＾（１）を生成する。乱数計算部１３０は、区域＃１について生成された乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を、タグ生成部１４０に出力する。

ここで、上述したように、ａ＋ｍ’＝２＾ｂ－２である。つまり、区域＃１の最後の乱数Ｚ＿（ａ＋ｍ’）＾（１）は、Ｚ＿（２＾ｂ－２）＾（１）に対応する。したがって、区域＃１については、上記の式６において、Ｚ＿（２＾ｂ－１）＾（１）＝０である。つまり、区域＃１については、上記の式５に示す行列ＡＭの最後の列（α＿（２，２＾ｂ－１），・・・α＿（ω，２＾ｂ－１））は、用いられない。つまり、区域＃１においては、上記の式７の最後の排他的論理和では、０（＝α＿（ｉ，２＾ｂ－１）・Ｚ＿（２＾ｂ－１）＾（１））が排他的論理和される。このことは、後述する認証復号装置２０における復号処理においても同様である。

また、図６に示すように、暗号化部１２０は、区域＃２について、平文ブロックＭ＿１，・・・，Ｍ＿ｍのうち、Ｍ＿ｍ’から続く（２＾ｂ－２）個のＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－２）に対して、区域＃１と同様の処理を行う。なお、暗号化部１２０は、区域＃２については、最初のＴＢＣ関数に入力される初期値を０＾ｂにリセットしている。そして、暗号化部１２０は、Ｍ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－２）にそれぞれ対応する暗号文ブロックＣ＿（ｍ’＋１），・・・，Ｃ＿（ｍ’＋２＾ｂ－２）を得る。また、暗号化部１２０は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を、乱数計算部１３０に出力する。なお、暗号化部１２０は、区域＃２における最後の平文ブロックＭ＿（ｍ’＋２＾ｂ－２）を区域＃２における最後のＴＢＣ関数で暗号化することにより、区域＃２における最後の乱数Ｚ＿（２＾ｂ－１）＾（２）を得る。また、暗号化部１２０は、最後の平文ブロックＭ＿（ｍ’＋２＾ｂ－２）がＴＢＣ関数で暗号化されたら、その暗号化結果Ｚ＿（２＾ｂ－１）＾（２）を、Ｓ＿１＾（２）として、乱数計算部１３０に出力する。

また、図６に示すように、乱数計算部１３０は、区域＃２について、暗号化部１２０で生成される乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。つまり、乱数計算部１３０は、上記の式６により、式５に示した行列ＡＭを用いて、乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。これにより、乱数計算部１３０は、区域＃２についての乱数の組Ｓ＿２＾（２），・・・，Ｓ＿ω＾（２）を生成する。言い換えると、乱数計算部１３０は、乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）それぞれと行列ＡＭの対応する要素との乗算値の排他的論理和を計算することによって、乱数の組Ｓ＿２＾（２），・・・，Ｓ＿ω＾（２）を生成する。なお、乱数計算部１３０は、区域＃２については、各ラインｉの初期値を０＾ｂにリセットしている。乱数計算部１３０は、区域＃２について生成された乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を、タグ生成部１４０に出力する。

ここで、上述したように、暗号化部１２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、暗号化部８４において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと異なる。区域＃２において、暗号化部１２０において使用されるＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉ（ｍ’＋１≦ｉ≦ｍ’＋２＾ｂ－２）に対して、（Ｎ，ａ，ｉ，０，０）となる。なお、区域＃２について、暗号化部１２０の最後に用いられるＴＢＣ関数（Ｍ＿（ｍ’＋２＾ｂ－２）を入力しＳ＿１＾（２）を得るもの）に入力されるＴｗｅａｋは、（Ｎ，ａ，ｍ’＋２＾ｂ－２，１，０）である。これにより、区域＃２におけるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、区域＃１におけるＴＢＣ関数それぞれに入力されるＴｗｅａｋとは異なることとなる。これらのことは、後述する認証復号装置２０における復号処理においても同様である。

なお、図４～図６には、区域＃１及び区域＃２についての演算の概略が示されているが、区域＃３以降についても、図６に示した区域＃２と実質的に同様の演算がなされる。したがって、区域＃３以降の具体的な処理の説明については省略する。なお、乱数計算部１３０は、ある区域について処理を行うごとに、各ラインの初期値をリセットし、式５に示した同じ行列ＡＭ（つまり同じ要素α）を繰り返し呼び出して、乱数の組を生成する。

なお、暗号化部１２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、図６を用いて上述した規則に従って設定される。つまり、各区域＃ｋにおいて、１番目から（２＾ｂ－２）番目のＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉに対して、（Ｎ，ａ，ｉ，０，０）となる。なお、暗号化部１２０の最後（２＾ｂ－１番目）に用いられるＴＢＣ関数に入力されるＴｗｅａｋは、（Ｎ，ａ，ｉ，１，０）である。なお、ここでは、ｉは平文ブロック数ｍのインデックスであるので、ある区域＃ｋにおけるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、別の区域におけるＴＢＣ関数それぞれに入力されるＴｗｅａｋとは異なることとなる。なお、最終の区域＃βにおいて、平文ブロック数が２＾ｂ－２に満たない場合、その満たない分の乱数Ｚ＿（ｊ）＾（β）の値が０となる。これらのことは、後述する認証復号装置２０における復号処理においても同様である。

タグ生成部１４０は、乱数計算部１３０によって生成された乱数Ｓの組と、ナンスＮとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コード（Message Authentication Code；ＭＡＣ）により、認証用のタグＴを生成する。タグ生成部１４０は、乱数Ｓから安全にタグＴを生成するために、ナンスベースＭＡＣを用いて、乱数の組を統合して、タグＴを生成する。ここで、ナンスベースＭＡＣとは、ＭＡＣの入力にナンスが含まれたものである。

タグ生成部１４０には、ナンス生成部１０４からナンスＮが入力される。また、タグ生成部１４０には、乱数計算部１３０から乱数の組が入力される。乱数計算部１３０が各区域について上述した処理を行うことによって、タグ生成部１４０は、以下の式８の行列で示されるような乱数の組を得る。ここで、式８は、乱数Ｓを要素とするω×βの大きさの乱数行列を示す。

・・・（８）

ここで、式８に示す行列において、各列は、各区域について出力された乱数Ｓを示す。つまり、ｋ番目の列は、区域＃ｋについてタグ生成部１４０に対して出力された、ω個の乱数Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を示す。なお、１つの乱数Ｓのデータ長はｂビットであるので、区域＃ｋについて出力された乱数の組のデータ長は、ωｂビットとなる。

また、式８に示す行列において、各行は、乱数計算部１３０における各ラインで出力された乱数を示す。つまり、ｉ番目の行は、区域＃１～区域＃βについて、乱数計算部１３０におけるラインｉで出力された、β個の乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を示す。なお、１番目の行は、区域＃１～区域＃βについて、暗号化部１２０から出力された乱数Ｓ＿１＾（１），・・・，Ｓ＿１＾（β）を示す。

そして、タグ生成部１４０は、式８に示す乱数行列の各行に含まれる乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を、ナンスベースＭＡＣを用いて処理して、タグＴ［ｉ］を生成する。これにより、以下の式９に示すように、タグ生成部１４０は、式８に示す乱数行列を用いて、タグＴ［１］，・・・，Ｔ［ω］を生成する。

・・・（９）
ここで、タグ生成部１４０は、ω個のＭＡＣを用いてタグＴ［１］，・・・，Ｔ［ω］を生成する。つまり、１≦ｉ≦ωとして、タグ生成部１４０は、ｉ番目のＭＡＣ＿ｉを用いて、タグＴ［ｉ］を生成する。

図７は、実施の形態１にかかるタグ生成部１４０の演算の概略を示す図である。図７は、タグ生成部１４０で用いられるタグ導出関数を示す。つまり、図７は、タグ生成部１４０で用いられるナンスベースＭＡＣを示す。ここで、図７は、タグ生成部１４０が、式８及び式９におけるｉ番目の行に対応する乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）をＭＡＣ＿ｉで処理して、タグＴ［ｉ］を生成する例を示している。

タグ生成部１４０は、定数ｆｉｘを、鍵Ｋ、ナンスＮ及びＴｗｅａｋが入力されたＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。ここで、このＴＢＣ関数Ｅ_Ｋ ^～に入力されるＴｗｅａｋは、安全性上の理由により、図７に示すような形式である必要がある。つまり、タグ生成部１４０は、式８及び式９の各行（各ライン）のインデックスｉ（１≦ｉ≦ω）に対して、（Ｎ，ａ，ｍ，ｉ，１）をＴｗｅａｋとして入力するＴＢＣ関数の暗号化結果を用いて、定数ｆｉｘを暗号化する。この、定数ｆｉｘを暗号化して得られた暗号化結果は、ナンスを含むＴｗｅａｋが入力されたＴＢＣ関数を用いて生成されるので、ナンス由来の乱数と言える。

また、タグ生成部１４０は、乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を、ＴＢＣ関数Ｅ_Ｋ ^～’で暗号化する。ここで、ＴＢＣ関数Ｅ_Ｋ ^～’は、図４～図６（及び図７）に記載されたどのＴＢＣ関数Ｅ_Ｋ ^～に入力されるＴｗｅａｋとも異なるＴｗｅａｋが入力されるＴＢＣ関数である。なお、ＴＢＣ関数Ｅ_Ｋ ^～’に入力されるＴｗｅａｋの形式は、ＴＢＣ関数Ｅ_Ｋ ^～に入力されるＴｗｅａｋの形式と異なってもよいし、同じであってもよい。例えば、Ｓ＿ｉ＾（ｋ）を暗号化するＴＢＣ関数Ｅ_Ｋ ^～’に入力されるＴｗｅａｋは、（（ｋ）＿ｎ，ａ，ｍ，ｉ，２）としてもよい。ここで、「（ｋ）＿ｎ」は、数値ｋをｎビット値として表現したものである。なお、このＴｗｅａｋの最後の値が「２」となっているが、図４～図６に記載されたＴＢＣ関数Ｅ_Ｋ ^～に入力されるＴｗｅａｋの最後の値は、「２」とならない。したがって、Ｔｗｅａｋの重複を避けることができる。

そして、タグ生成部１４０は、ＴＢＣ関数Ｅ_Ｋ ^～を用いて定数ｆｉｘを暗号化した暗号化結果と、ＴＢＣ関数Ｅ_Ｋ ^～’を用いて乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を暗号化した暗号化結果との排他的論理和（総和）を、タグＴ［ｉ］として生成する。タグ生成部１４０は、ｉ＝１～ωについて上記の処理を行い、タグＴ［１］，・・・，Ｔ［ω］を生成する。そして、タグ生成部１４０は、Ｔ［１］，・・・，Ｔ［ω］を、タグＴ＝Ｔ［１］｜｜・・・｜｜Ｔ［ω］として出力する。

なお、上述したように、ナンスＮは、過去の値と重複がないように生成される。したがって、１つのナンスで２回以上平文Ｍを処理することは、なされない。したがって、ナンスを含んでいないＭＡＣと比較して、所望のレベルの安全性を、効率的に実現することができる。すなわち、所望の安全性を実現するためには、例えば、タグの生成に用いられるＭＡＣは、ｔａｇｇｉｎｇクエリの回数に依存しないｂビット安全性を持つＭＡＣである必要がある。つまり、何回ＭＡＣを呼び出しても、安全性に影響がないようなＭＡＣが望まれる。言い換えると、攻撃者が何回ｔａｇｇｉｎｇクエリを実行したとしても、ＭＡＣの安全性が低下しないことが望まれる。

そして、図７に示したナンスベースＭＡＣでは、定数ｆｉｘの暗号化で、ナンス由来の乱数が出力される。ここで、上述したように、ナンスＮは、平文Ｍの認証暗号処理ごとに、異なる値となる。したがって、定数ｆｉｘの暗号化では、平文Ｍの認証暗号処理ごとに、異なる乱数が出力され得る。そして、図７に示したナンスベースＭＡＣでは、乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を暗号化した暗号化結果の総和（排他的論理和）を、このナンス由来の乱数で排他的論理和している。したがって、乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）及びそれらの暗号化結果の総和（排他的論理和）が、マスクされることになる。したがって、攻撃者にとってはｔａｇｇｉｎｇクエリの度に新しい乱数が導出されることとなるため、ｔａｇｇｉｎｇクエリの回数は安全性に影響しないこととなる。

出力部１５０は、暗号文ＣとタグＴとを出力するための制御を行う。このとき、出力部１５０は、暗号文ＣとタグＴとを連結して出力するようにしてもよい。出力部１５０は、例えば、ディスプレイなどの出力装置に暗号文ＣとタグＴとを表示させるための制御を行ってもよい。また、出力部１５０は、例えば、ネットワークを介して接続された外部装置などに対して、暗号文Ｃ及びタグＴを出力するように制御を行ってもよい。また、出力部１５０は、ナンスＮ及び関連データＡを出力するように制御を行ってもよい。例えば、出力部１５０は、（Ｎ，Ａ，Ｃ，Ｔ）を、認証復号装置２０に送信する。

図８は、実施の形態１にかかる認証暗号化装置１０の作用を説明するための図である。なお、説明の明確化のため、図８では、関連データを空としている。上述したように、認証暗号化装置１０は、平文Ｍの平文ブロックを、区域＃１，区域＃２，・・・区域＃βにそれぞれ対応する区域平文ブロックＭ［１］，Ｍ［２］，・・・，Ｍ［β］に区分けする。なお、上述したように、区域平文ブロックＭ［ｋ］それぞれには、（２＾ｂ－２）個の平文ブロックが含まれる。

そして、暗号化部１２０及び乱数計算部１３０は、区域＃１について、入力されたナンスＮ及び区域平文ブロックＭ［１］を用いて、区域暗号文ブロックＣ［１］、及び、乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を生成する。また、暗号化部１２０及び乱数計算部１３０は、区域＃２について、入力されたナンスＮ及び区域平文ブロックＭ［２］を用いて、区域暗号文ブロックＣ［２］、及び、乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を生成する。以下同様にして、暗号化部１２０及び乱数計算部１３０は、区域＃ｋそれぞれについて、入力されたナンスＮ及び区域平文ブロックＭ［ｋ］を用いて、区域暗号文ブロックＣ［ｋ］、及び、乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。

このとき、暗号化部１２０は、各区域それぞれについて、比較例にかかる暗号化部８４の演算と実質的に同様の演算をサブルーチンとして用いて、処理を行うことができる。なお、このとき、区域ごとに初期値をリセットし、Ｔｗｅａｋを適切に設定する必要があることに留意されたい。また、乱数計算部１３０は、各区域それぞれについて、式５に示す行列ＡＭを呼び出して、比較例にかかる計算部８６の演算と実質的に同様の演算をサブルーチンとして用いて、処理を行うことができる。なお、このとき、区域ごとに初期値をリセットする必要があることに留意されたい。これらのことは、後述する認証復号装置２０における復号処理においても同様である。

そして、タグ生成部１４０は、生成された乱数Ｓの組（式８で示す行列）と、ナンスＮとを入力として、上述したように、ω個の適切なナンスベースＭＡＣを用いて、タグＴ［１］，・・・，Ｔ［ω］を生成する。ここで、上述したように、生成された乱数Ｓの、ＴＢＣ関数による暗号化結果の組が、ナンス由来の乱数によってマスクされるので、生成された乱数Ｓの組の安全性は確保されている。

＜認証復号装置＞
図９は、実施の形態１にかかる認証復号装置２０の構成を示す図である。また、図１０～図１１は、実施の形態１にかかる認証復号処理における演算の概略を示す図である。図９に示すように、認証復号装置２０は、入力部２００と、分割部２０２と、ＡＤ処理部２１０と、復号部２２０と、乱数計算部２３０と、タグ生成部２４０と、タグ検査部２５０とを有する。

認証復号装置２０は、例えばコンピュータ等の情報処理装置によって実現可能である。つまり、認証復号装置２０は、ＣＰＵなどの演算装置と、メモリ又はディスクなどの記憶装置とを有している。認証復号装置２０は、例えば、記憶装置に格納されたプログラムを演算装置が実行することで、上記の各構成要素を実現する。このことは、後述する他の実施の形態においても同様である。

入力部２００は、入力手段としての機能を有する。分割部２０２は、分割手段としての機能を有する。ＡＤ処理部２１０は、関連データ処理手段としての機能を有する。復号部２２０は、復号手段としての機能を有する。乱数計算部２３０は、乱数計算手段（計算手段）としての機能を有する。タグ生成部２４０は、タグ生成手段としての機能を有する。タグ検査部２５０は、タグ検査手段としての機能を有する。

入力部２００は、認証暗号化装置１０から出力された、ナンスＮ、関連データＡ、復号の対象となる暗号文Ｃ、及びタグＴの入力を受け付ける。入力部２００は、例えば、キーボードなどの入力装置により実現されてもよい。入力部２００は、例えば、ネットワークを介して接続された外部装置などから、ナンスＮ、関連データＡ、暗号文Ｃ及びタグＴの入力を受け付けてもよい。なお、関連データＡが存在しない場合もあり、この場合は、関連データＡは入力されない。入力部２００は、ナンスＮを、復号部２２０及びタグ生成部２４０に出力する。また、入力部２００は、暗号文Ｃ及び関連データＡを、分割部２０２に出力する。また、入力部２００は、タグＴを、タグ検査部２５０に出力する。

分割部２０２は、暗号文Ｃ及び関連データＡそれぞれを、所定長のブロックに分割する。具体的には、分割部２０２は、暗号文Ｃを、それぞれｂビットの暗号文ブロックＣ＿１，・・・，Ｃ＿ｍに分割する。なお、ｍは、暗号文ブロック（つまり平文ブロック）の数である。分割部２０２は、暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、復号部２２０に出力する。また、分割部２０２は、関連データＡを、それぞれｂビットの長さのＡＤブロックＡ＿１，・・・，Ａ＿ａに分割する。分割部２０２は、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、ＡＤ処理部２１０に出力する。

また、上述した分割部１０２と同様に、分割部２０２は、分割されたＡＤブロックＡ＿１，・・・，Ａ＿ａ及び暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、それぞれブロック数（２＾ｂ－２）個の区域（グループ）に区分けする。つまり、１つの区域には、（２＾ｂ－２）個のブロックが含まれることとなる。このとき、分割部２０２は、データ列Ｄ＝Ａ＿１｜｜・・・｜｜Ａ＿ａ｜｜Ｃ＿１｜｜・・・｜｜Ｃ＿ｍを、データ列の先頭のブロックから、区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けする。なお、区分けの方法は、上述した分割部１０２の場合と同様であってもよい。

なお、区域＃ｋに区分けされた暗号文ブロックのビット列を「区域暗号文ブロックＣ［ｋ］」とすると、暗号文Ｃは、Ｃ＝Ｃ［１］｜｜Ｃ［２］｜｜・・・｜｜Ｃ［β］とも表記され得る。このとき、少なくともＣ［１］及びＣ［β］以外の区域暗号文ブロックＣ［ｋ］に含まれる暗号文ブロックの数は、（２＾ｂ－２）個となる。また、関連データが空の場合、区域暗号文ブロックＣ［１］に含まれる暗号文ブロックの数も、（２＾ｂ－２）個となる。

ＡＤ処理部２１０は、上述したＡＤ処理部１１０と実質的に同様の処理を行う。つまり、ＡＤ処理部２１０は、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。このとき、ＡＤ処理部２１０は、上述した区域ごとに、ＡＤブロックを処理する。ＡＤ処理部２１０は、Ｈ＿１を復号部２２０に出力する。また、ＡＤ処理部２１０は、ＴＢＣ関数の出力値である乱数Ｚ＿１，・・・，Ｚ＿（ａ－１）を乱数計算部２３０に出力する。なお、ＡＤ処理部２１０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、上述したＡＤ処理部１１０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと、実質的に同様に設定されてもよい。

復号部２２０は、上述した暗号化部１２０における暗号化処理に対応した復号処理を行う。復号部２２０は、暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。このとき、復号部２２０は、上述した区域ごとに、暗号文ブロック（暗号文）を復号する。つまり、復号部２２０は、区域＃１に含まれる暗号文ブロックについて、上述した暗号化部１２０における暗号化処理に対応した復号処理を行う。そして、復号部２２０は、区域＃２に含まれる暗号文ブロックについて、上述した暗号化部１２０における暗号化処理に対応した復号処理を行う。以降、復号部２２０は、区域＃ｋに含まれる暗号文ブロックについて、上述した暗号化部１２０における暗号化処理に対応した復号処理を行う。つまり、復号部２２０は、区域＃ｋに含まれる区域暗号文ブロックＣ［ｋ］について、復号を行う。

復号部２２０は、生成された平文ブロックＭ＿１，・・・，Ｍ＿ｍを、平文Ｍ＝Ｍ＿１｜｜・・・｜｜Ｍ＿ｍとして、タグ検査部２５０に出力する。また、復号部２２０は、区域＃ｋに含まれる区域暗号文ブロックＣ［ｋ］について復号を行って、区域平文ブロックＭ［ｋ］を得る。なお、復号部２２０は、得られた平文を、平文Ｍ＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［β］として、タグ検査部２５０に出力してもよい。また、復号部２２０は、各区域で得られた乱数Ｚ（ＴＢＣ関数の出力値）を、乱数計算部２３０に出力する。また、復号部２２０は、各区域において、最後の暗号文ブロックがＴＢＣ関数で処理されて得られた暗号化結果Ｚを、乱数Ｓ＿１として、タグ生成部２４０に出力する。復号部２２０の処理の詳細については、後述する。なお、復号部２２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、上述した暗号化部１２０において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと、実質的に同様に設定されてもよい。

乱数計算部２３０は、上述した乱数計算部１３０と同様に、ＡＤ処理部２１０及び復号部２２０で生成される乱数Ｚと、式５に示した所定の行列ＡＭとを用いて、タグを生成するための乱数Ｓを計算する。このとき、乱数計算部２３０は、区域ごとに、乱数Ｓを計算する。具体的には、乱数計算部２３０は、区域ごとに、ＡＤ処理部２１０及び復号部２２０で生成される乱数Ｚと、所定の行列ＡＭとを用いて、ω－１個の乱数Ｓの組（Ｓ＿２，・・・，Ｓ＿ω）を生成する。ここで、乱数Ｓの組は、検査用のタグＴ^＊を生成するために使用される。乱数計算部２３０は、上述した乱数計算部１３０と同様に、各区域において、ω－１個のラインｉ（２≦ｉ≦ω）それぞれについて、乱数Ｚ＿ｊとα＿（ｉ，ｊ）との乗算値の排他的論理和を行うことによって、Ｓ＿ｉを算出する。つまり、乱数計算部２３０は、各区域＃ｋにおいて、上記の式６に示すように、行列ＡＭを用いて乱数Ｚ＿１＾（ｋ），・・・，Ｚ＿（２＾ｂ－１）＾（ｋ）を処理して、乱数の組Ｓ＿２＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。

ここで、乱数計算部２３０は、区域ごとに、Ｚとαとの乗算値の排他的論理和の各ラインの初期値をリセットする。つまり、乱数計算部２３０は、各区域について、ラインｉの初期値を、０＾ｂとする。言い換えると、乱数計算部２３０は、区域ごとに、乱数の組が生成される複数のラインそれぞれの初期値を、リセットする。乱数計算部２３０の処理の詳細については後述する。乱数計算部２３０は、各区域＃ｋについて生成された乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を、タグ生成部２４０に出力する。なお、上述したように、各区域＃ｋにおける乱数Ｓ＿１＾（ｋ）については、復号部２２０によって生成され、タグ生成部２４０に出力される。

図１０は、１区域目つまり区域＃１についての、復号部２２０及び乱数計算部２３０の演算の概略を示す図である。なお、区域＃１についてのＡＤ処理部２１０の演算の概略については、図４に記載されたものと実質的に同様であるので、図示を省略している。また、図１１は、２区域目つまり区域＃２についての、復号部２２０及び乱数計算部２３０の演算の概略を示す図である。

図１０に示すように、区域＃１について、暗号文ブロックＣ＿１，・・・，Ｃ＿ｍのうちのＣ＿１，・・・，Ｃ＿ｍ’に対して、復号処理を行う。具体的には、復号部２２０は、初期値としてＨ＿１を設定する。復号部２２０は、初期値Ｈ＿１をＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、ＴＢＣ関数Ｅ_Ｋ ^～から、暗号化結果として、乱数であるＺ＿ａ＾（１）が出力される。そして、復号部２２０は、この出力された暗号化結果Ｚ＿ａと１つ目の暗号文ブロックＣ＿１との排他的論理和により、平文ブロックＭ＿１を得る。

次に、復号部２２０は、平文ブロックＭ＿１をＴＢＣ関数Ｅ_Ｋ ^～で暗号化する。これにより、暗号化結果として、乱数であるＺ＿（ａ＋１）＾（１）が出力される。復号部２２０は、暗号化結果Ｚ＿（ａ＋１）＾（１）と２つ目の暗号文ブロックＣ＿２との排他的論理和により、平文ブロックＭ＿２を得る。以降、復号部２２０は、暗号文ブロックＣ＿ｉを用いて復号された平文ブロックＭ＿ｉの暗号化結果Ｚ＿（ａ＋ｉ）と暗号文ブロックＣ＿（ｉ＋１）との排他的論理和により、平文ブロックＭ＿（ｉ＋１）を得る、という処理を繰り返す。

そして、復号部２２０は、Ｃ＿１，・・・，Ｃ＿ｍ’にそれぞれ対応する平文ブロックＭ＿１，・・・，Ｍ＿ｍ’を得る。また、復号部２２０は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を、乱数計算部２３０に出力する。なお、復号部２２０は、区域＃１における最後の平文ブロックＭ＿ｍ’を区域＃１における最後のＴＢＣ関数で暗号化することにより、区域＃１における最後の乱数Ｚ＿（ａ＋ｍ’）＾（１）を得る。また、復号部２２０は、最後の平文ブロックＭ＿ｍ’がＴＢＣ関数で暗号化されたら、その暗号化結果Ｚ＿（ａ＋ｍ’）＾（１）を、Ｓ＿１＾（１）として、乱数計算部２３０に出力する。

また、図１０に示すように、乱数計算部２３０は、区域＃１について、復号部２２０で生成されるＺ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。なお、図１０には、ＡＤ処理部２１０については図示されていないが、図４と同様にして、乱数計算部２３０は、区域＃１について、ＡＤ処理部２１０で生成される乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ－１）＾（１）を処理する。つまり、乱数計算部２３０は、上記の式６により、式５に示した行列ＡＭを用いて、乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ－１）＾（１），Ｚ＿ａ＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。これにより、乱数計算部２３０は、区域＃１についての乱数の組Ｓ＿２＾（１），・・・，Ｓ＿ω＾（１）を生成する。言い換えると、乱数計算部２３０は、乱数Ｚ＿１＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）それぞれと行列ＡＭの対応する要素との乗算値の排他的論理和を計算することによって、乱数の組Ｓ＿２＾（１），・・・，Ｓ＿ω＾（１）を生成する。乱数計算部２３０は、区域＃１について生成された乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を、タグ生成部２４０に出力する。

また、図１１に示すように、復号部２２０は、区域＃２について、暗号文ブロックＣ＿１，・・・，Ｃ＿ｍのうち、Ｃ＿ｍ’から続く（２＾ｂ－２）個のＣ＿（ｍ’＋１），・・・，Ｃ＿（ｍ’＋２＾ｂ－２）に対して、区域＃１と同様の処理を行う。なお、復号部２２０は、区域＃２については、最初のＴＢＣ関数に入力される初期値を０＾ｂにリセットしている。そして、復号部２２０は、Ｃ＿（ｍ’＋１），・・・，Ｃ＿（ｍ’＋２＾ｂ－２）にそれぞれ対応する平文ブロックＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－２）を得る。また、復号部２２０は、暗号化結果、つまりＴＢＣ関数の出力値である乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を、乱数計算部２３０に出力する。なお、復号部２２０は、区域＃２における最後の平文ブロックＭ＿（ｍ’＋２＾ｂ－２）を区域＃２における最後のＴＢＣ関数で暗号化することにより、区域＃２における最後の乱数Ｚ＿（２＾ｂ－１）＾（２）を得る。また、復号部２２０は、最後の平文ブロックＭ＿（ｍ’＋２＾ｂ－２）がＴＢＣ関数で暗号化されたら、その暗号化結果Ｚ＿（２＾ｂ－１）＾（２）を、Ｓ＿１＾（２）として、乱数計算部２３０に出力する。

また、図１１に示すように、乱数計算部２３０は、乱数計算部１３０と実質的に同様にして、区域＃２について、復号部２２０で生成される乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。つまり、乱数計算部２３０は、上記の式６により、式５に示した行列ＡＭを用いて、乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。これにより、乱数計算部２３０は、区域＃２についての乱数の組Ｓ＿２＾（２），・・・，Ｓ＿ω＾（２）を生成する。言い換えると、乱数計算部２３０は、乱数Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）それぞれと行列ＡＭの対応する要素との乗算値の排他的論理和を計算することによって、乱数の組Ｓ＿２＾（２），・・・，Ｓ＿ω＾（２）を生成する。なお、乱数計算部２３０は、区域＃２については、各ラインｉの初期値を０＾ｂにリセットしている。乱数計算部２３０は、区域＃２について生成された乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を、タグ生成部２４０に出力する。

なお、図１０～図１１には、区域＃１及び区域＃２についての演算の概略が示されているが、区域＃３以降についても、図１１に示した区域＃２と実質的に同様の演算がなされる。したがって、区域＃３以降の具体的な処理の説明については省略する。なお、乱数計算部２３０は、乱数計算部１３０と同様に、ある区域について処理を行うごとに、式５に示した同じ行列ＡＭ（つまり同じ要素α）を繰り返し呼び出して、乱数の組を生成する。

タグ生成部２４０は、乱数計算部２３０によって生成された乱数Ｓの組と、ナンスＮとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグＴ^＊を生成する。なお、タグＴ^＊の生成方法については、タグ生成部１４０におけるタグＴの生成方法と実質的に同様である。つまり、タグ生成部２４０は、ＴＢＣ関数Ｅ_Ｋ ^～を用いて定数ｆｉｘを暗号化した暗号化結果と、ＴＢＣ関数Ｅ_Ｋ ^～’を用いて乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を暗号化した暗号化結果との排他的論理和（総和）を、タグＴ^＊［ｉ］として生成する。タグ生成部２４０は、ｉ＝１～ωについて上記の処理を行い、タグＴ^＊［１］，・・・，Ｔ^＊［ω］を生成する。そして、タグ生成部２４０は、Ｔ^＊［１］，・・・，Ｔ^＊［ω］を、タグＴ^＊＝Ｔ^＊［１］｜｜・・・｜｜Ｔ^＊［ω］として、タグ検査部２５０に出力する。

タグ検査部２５０は、認証暗号化装置１０によって生成された認証用のタグＴと、タグ生成部２４０によって生成された検査用のタグＴ^＊とを比較して、改ざんの有無を検査する。そして、タグ検査部２５０は、検査結果に基づいて、情報を出力するための制御を行う。なお、タグ検査部２５０は、例えば、ディスプレイなどの出力装置に情報を表示させるための制御を行ってもよい。また、タグ検査部２５０は、例えば、ネットワークを介して接続された外部装置などに対して、情報を出力するように制御を行ってもよい。

具体的には、タグ検査部２５０は、認証用のタグＴと検査用のタグＴ^＊とが一致する場合に、認証が成功したとして、復号部２２０によって生成された平文Ｍを出力するための制御を行う。一方、タグ検査部２５０は、認証用のタグＴと検査用のタグＴ^＊とが一致しない場合に、認証が失敗したとして、タグＴとタグＴ^＊とが一致しないことを示すエラーメッセージ⊥を出力するための制御を行う。

図１２は、実施の形態１にかかる認証復号装置２０の作用を説明するための図である。なお、説明の明確化のため、図１２では、関連データを空としている。上述したように、認証復号装置２０は、暗号文Ｃの暗号文ブロックを、区域＃１，区域＃２，・・・区域＃βにそれぞれ対応する区域暗号文ブロックＣ［１］，Ｃ［２］，・・・，Ｃ［β］に区分けする。なお、上述したように、区域暗号文ブロックＣ［ｋ］それぞれには、（２＾ｂ－２）個の暗号文ブロックが含まれる。

そして、復号部２２０及び乱数計算部２３０は、区域＃１について、入力されたナンスＮ及び区域暗号文ブロックＣ［１］を用いて、区域平文ブロックＭ［１］、及び、乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を生成する。また、復号部２２０及び乱数計算部２３０は、区域＃２について、入力されたナンスＮ及び区域暗号文ブロックＣ［２］を用いて、区域平文ブロックＭ［２］、及び、乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を生成する。以下同様にして、復号部２２０及び乱数計算部２３０は、区域＃ｋそれぞれについて、入力されたナンスＮ及び区域暗号文ブロックＣ［ｋ］を用いて、区域平文ブロックＭ［ｋ］、及び、乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。

そして、タグ生成部２４０は、生成された乱数Ｓの組（式８で示す行列）と、ナンスＮとを入力として、上述したように、ω個の適切なナンスベースＭＡＣを用いて、検査用のタグＴ^＊［１］，・・・，Ｔ^＊［ω］を生成する。そして、タグ検査部２５０は、タグＴとタグＴ^＊とが一致する場合に、平文Ｍ＝Ｍ［１］｜｜・・・｜｜Ｍ［β］を出力する。一方、タグ検査部２５０は、タグＴとタグＴ^＊とが一致しない場合に、エラーメッセージ⊥を出力する。

＜認証暗号化方法及び認証復号方法＞
次に、図１３及び図１４を用いて、実施の形態１にかかる認証暗号システム１にかかる動作について説明する。図１３は、実施の形態１にかかる認証暗号化装置１０で実行される認証暗号化方法を示すフローチャートである。

入力部１００は、上述したように、平文Ｍ及び関連データＡを入力する（ステップＳ１０２）。分割部１０２は、上述したように、平文Ｍ及び関連データＡそれぞれを、所定長のブロック（平文ブロック及びＡＤブロック）に分割する（ステップＳ１０４）。また、分割部１０２は、上述したように、分割されたＡＤブロック及び平文ブロックを、区域ごとに区分けする（ステップＳ１０６）。ナンス生成部１０４は、上述したように、ナンスＮを生成する（ステップＳ１０８）。

次に、ＡＤ処理部１１０、暗号化部１２０及び乱数計算部１３０は、区域ごとの処理を行う（ステップＳ１１０）。具体的には、ＡＤ処理部１１０は、上述したように、ＡＤブロックを処理する（ステップＳ１１２）。暗号化部１２０は、上述したように、平文ブロックを暗号化し、暗号文ブロックを取得する（ステップＳ１１４）。乱数計算部１３０は、上述したように、乱数Ｓの組を取得する（ステップＳ１１６）。

次に、タグ生成部１４０は、上述したように、区域ごとに生成された乱数Ｓの組を用いてタグＴを生成する（ステップＳ１２２）。そして、出力部１５０は、ナンスＮ、関連データＡ、暗号文Ｃ、及びタグＴを出力する（ステップＳ１２４）。

図１４は、実施の形態１にかかる認証復号装置２０で実行される認証復号方法を示すフローチャートである。入力部２００は、ナンスＮ、関連データＡ、暗号文Ｃ及びタグＴを入力する（ステップＳ２０２）。分割部２０２は、上述したように、暗号文Ｃ及び関連データＡそれぞれを、所定長のブロック（暗号文ブロック及びＡＤブロック）に分割する（ステップＳ２０４）。また、分割部２０２は、上述したように、分割されたＡＤブロック及び暗号文ブロックを、区域ごとに区分けする（ステップＳ２０６）。

次に、ＡＤ処理部２１０、復号部２２０及び乱数計算部２３０は、区域ごとの処理を行う（ステップＳ２１０）。具体的には、ＡＤ処理部２１０は、上述したように、ＡＤブロックを処理する（ステップＳ２１２）。復号部２２０は、上述したように、暗号文ブロックを復号し、平文ブロックを取得する（ステップＳ２１４）。乱数計算部２３０は、上述したように、乱数Ｓの組を取得する（ステップＳ２１６）。

次に、タグ生成部２４０は、上述したように、区域ごとに生成された乱数Ｓの組を用いてタグＴ^＊を生成する（ステップＳ２２２）。タグ検査部２５０は、上述したように、認証用のタグＴと検査用のタグＴ^＊とが一致するか否かを判定する（ステップＳ２３０）。認証用のタグＴと検査用のタグＴ^＊とが一致する場合（Ｓ２３０のＹＥＳ）、タグ検査部２５０は、平文Ｍを出力する（ステップＳ２３２）。一方、認証用のタグＴと検査用のタグＴ^＊とが一致しない場合（Ｓ２３０のＮＯ）、タグ検査部２５０は、エラーメッセージ⊥を出力する（ステップＳ２３４）。

＜効果＞
上述したように、実施の形態１にかかる認証暗号化装置１０は、入力ブロック（ＡＤブロック及び平文ブロック）を、比較例にかかるＰＦＢωの手法で処理可能なサイズである（２＾ｂ－２）個のブロックを含む区域に区分けする。そして、実施の形態１にかかる認証暗号化装置１０は、各区域で生成される乱数Ｓの組から、タグＴを適切に導出するように構成されている。これにより、実施の形態１にかかる認証暗号システム１は、比較例にかかるＰＦＢωの手法では安全性上不可能であった、（２＾ｂ－１）個以上の入力ブロックを処理することが可能となる。

そして、上述したように、比較例では、ωｂビットの安全性を実現できるにも関わらず、入力ブロック数の制限が、ｂビット安全性のＡＥの場合と同じとなっている。したがって、比較例において入力ブロック数の制限を超えるサイズ（ｂ×（２＾ｂ－２）ビットを超えるサイズ）の平文を送信しようとすると、前もって処理可能なブロック数ごとに平文を分割する必要がある。そして、分割された平文ごとに暗号化を行って、得られた暗号文の送信を行う必要がある。つまり、比較例では、１つの平文に対して、複数の（Ｎ，Ａ，Ｃ，Ｔ）を送信する必要がある。これに対し、実施の形態１にかかる認証暗号システム１では、処理可能なブロック数の制限がなくなるので、平文のサイズによらないで、一度で、暗号文を送信することが可能となる。つまり、実施の形態１では、単一の（Ｎ，Ａ，Ｃ，Ｔ）のみの送信を行うだけでよい。したがって、通信の負荷を抑制することが可能となる。

（実施の形態２）
次に、実施の形態２について説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。また、各図面において、同一の要素には同一の符号が付されており、必要に応じて重複説明は省略されている。なお、実施の形態２にかかるシステム構成については、実施の形態１のシステム構成と実質的に同様であるので、説明を省略する。つまり、実施の形態２にかかる認証暗号システム１は、認証暗号化装置１０に対応する認証暗号化装置１０Ａと、認証復号装置２０に対応する認証復号装置２０Ａとを有する。

実施の形態２は、上述した比較例にかかるＰＦＢωの方式を、比較例で言及されたΘＣＢの方式に拡張した場合の改良であるΘＣＢωに対応する。つまり、実施の形態２では、ＰＦＢωにおけるブロックのＴＢＣ関数を用いた処理（暗号化又は復号、及びＡＤ処理）を、並列に実行することができる。さらに、実施の形態２では、実施の形態１と同様に、平文ブロック（及びＡＤブロック）を所定の長さの区域に区分けして、区域ごとに、処理が行われる。

＜認証暗号化装置＞
図１５は、実施の形態２にかかる認証暗号化装置１０Ａの構成を示す図である。また、図１６～図１８は、実施の形態２にかかる認証暗号処理における演算の概略を示す図である。図１５に示すように、認証暗号化装置１０Ａは、入力部１００と、分割部１０２Ａと、ナンス生成部１０４と、ＡＤ処理部１１０Ａと、暗号化部１２０Ａと、乱数計算部１３０Ａと、タグ生成部１４０Ａと、出力部１５０とを有する。

認証暗号化装置１０Ａは、図２及び図３に示した認証暗号化装置１０に対応する。分割部１０２Ａは、実施の形態１にかかる分割部１０２に対応する。ＡＤ処理部１１０Ａは、実施の形態１にかかるＡＤ処理部１１０に対応する。暗号化部１２０Ａは、実施の形態１にかかる暗号化部１２０に対応する。乱数計算部１３０Ａは、実施の形態１にかかる乱数計算部１３０に対応する。タグ生成部１４０Ａは、実施の形態１にかかるタグ生成部１４０に対応する。なお、以下、認証暗号化装置１０Ａの構成について、主に、認証暗号化装置１０の構成と異なる部分について説明する。

分割部１０２Ａは、実施の形態１にかかる分割部１０２と同様に、平文Ｍ及び関連データＡそれぞれを、所定長のブロックに分割する。具体的には、分割部１０２Ａは、平文Ｍを、それぞれｂビットの平文ブロックＭ＿１，・・・，Ｍ＿ｍに分割する。分割部１０２Ａは、平文ブロックＭ＿１，・・・，Ｍ＿ｍを、暗号化部１２０Ａに出力する。また、分割部１０２Ａは、関連データＡを、それぞれｂビットの長さのＡＤブロックＡ＿１，・・・，Ａ＿ａに分割する。分割部１０２Ａは、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、ＡＤ処理部１１０Ａに出力する。

また、分割部１０２Ａは、分割されたＡＤブロックＡ＿１，・・・，Ａ＿ａ及び平文ブロックＭ＿１，・・・，Ｍ＿ｍを、それぞれブロック数（２＾ｂ－１）個の区域（グループ）に区分けする。つまり、実施の形態２では、１つの区域には、（２＾ｂ－１）個のブロックが含まれることとなる。このとき、分割部１０２Ａは、データ列Ｄ＝Ａ＿１｜｜・・・｜｜Ａ＿ａ｜｜Ｍ＿１｜｜・・・｜｜Ｍ＿ｍを、データ列の先頭のブロックから、区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けする。なお、実施の形態１の場合と異なり、１つの区域に含まれるブロック数が（２＾ｂ－１）個であるのは、実施の形態２では、ブロックの並列処理が可能であるからである。詳しくは後述する。

分割部１０２Ａは、区域＃１に全てのＡＤブロックＡ＿１，・・・，Ａ＿ａが含まれるように、区分けを行う。そして、ａ＜２＾ｂ－１の場合、分割部１０２Ａは、ｍ’個の平文ブロックが区域＃１に含まれるように、区分けを行う。ここで、ｍ’は区域＃１（１区域目）に含まれる平文ブロックの数である。そして、ｍ’は、ａ＋ｍ’＝２＾ｂ－１を満たす。そして、分割部１０２Ａは、残りの（ｍ－ｍ’）個の平文ブロックを、区域＃２～区域＃βに区分けする。以後、特に言及しない限り、ａ＜２＾ｂ－１であるとして説明する。なお、ａ＝２＾ｂ－１又はａ＞２＾ｂ－１である場合の処理については、実施の形態１においてａ＝２＾ｂ－２又はａ＞２＾ｂ－２であるの場合の処理と実質的に同様である。

なお、関連データが空の場合、分割部１０２Ａは、データ列Ｄ＝Ｍ＿１｜｜・・・｜｜Ｍ＿ｍを、データ列の先頭から、区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けする。このとき、区域＃１に区分けされた平文ブロックの数をｍ’とすると、ｍ’＝２＾ｂ－１となる。

なお、区域＃ｋに区分けされた平文ブロックのビット列を「区域平文ブロックＭ［ｋ］」とすると、平文Ｍは、Ｍ＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［β］とも表記され得る。このとき、少なくともＭ［１］及びＭ［β］以外の区域平文ブロックＭ［ｋ］に含まれる平文ブロックの数は、（２＾ｂ－１）個となる。また、関連データが空の場合、区域平文ブロックＭ［１］に含まれる平文ブロックの数も、（２＾ｂ－１）個となる。

ＡＤ処理部１１０Ａは、実施の形態１にかかるＡＤ処理部１１０と同様に、関連データＡを処理する。ここで、ＡＤ処理部１１０Ａは、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に処理する。このとき、ＡＤ処理部１１０Ａは、上述した区域ごとに、ＡＤブロックを処理する。ＡＤ処理部１１０Ａは、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数に各ＡＤブロックを入力することで、乱数Ｚを得る。ＡＤ処理部１１０Ａは、各ＴＢＣ関数の出力値（乱数）である中間値Ｚ＿１，・・・，Ｚ＿ａを乱数計算部１３０Ａに出力する。ＡＤ処理部１１０Ａの処理の詳細については後述する。

暗号化部１２０Ａは、実施の形態１にかかる暗号化部１２０と同様に、平文Ｍを処理する。ここで、暗号化部１２０Ａは、平文ブロックＭ＿１，・・・，Ｍ＿ｍを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に処理する。このとき、暗号化部１２０Ａは、上述した区域ごとに、ＴＢＣ関数を用いて、平文ブロック（平文）を並列に暗号化する。つまり、暗号化部１２０Ａは、区域＃１に含まれる平文ブロックについて、ＴＢＣ関数を用いて、並列に暗号化を行う。そして、暗号化部１２０Ａは、区域＃２に含まれる平文ブロックについて、ＴＢＣ関数を用いて、並列に暗号化を行う。以降、暗号化部１２０Ａは、区域＃ｋに含まれる平文ブロックを、ＴＢＣ関数を用いて、並列に暗号化する。つまり、暗号化部１２０Ａは、区域＃ｋに含まれる区域平文ブロックＭ［ｋ］について、平文ブロックごとに並列に暗号化を行う。暗号化部１２０Ａは、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数に各平文ブロックを入力することで、ＴＢＣ関数の出力値として、暗号文ブロックを得る。つまり、暗号化部１２０Ａは、区域ごとに、複数の平文ブロックをＴＢＣ関数を用いて並列に暗号化することによって、暗号文ブロックを生成する。

暗号化部１２０Ａは、生成された暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、暗号文Ｃ＝Ｃ＿１｜｜・・・｜｜Ｃ＿ｍとして、出力部１５０に出力する。また、暗号化部１２０Ａは、区域＃ｋに含まれる区域平文ブロックＭ［ｋ］について暗号化を行って、区域暗号文ブロックＣ［ｋ］を得る。ここで、区域暗号文ブロックＣ［ｋ］は、区域平文ブロックＭ［ｋ］と同じブロック数の暗号文ブロックから構成される。また、暗号化部１２０Ａは、各区域においてＴＢＣ関数に入力される平文ブロック（ＴＢＣ関数の入力値）を、中間値Ｚとして、乱数計算部１３０Ａに出力する。暗号化部１２０Ａの処理の詳細については、後述する。

なお、暗号化部１２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、暗号化部８４において用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと異なり得る。詳しくは後述する。なお、区域ごとに行われるＡＤ処理及び暗号化処理等で用いられるＴＢＣ関数に入力されるＴｗｅａｋを互いに区別するため、実施の形態２にかかるＴｗｅａｋの桁数は、実施の形態１と同様に、比較例にかかるＴｗｅａｋの桁数よりも多くなっている。つまり、比較例では、１つの区域のみの処理が実行されるのに対し、実施の形態２では、複数の区域について処理が実行されるので、その分、Ｔｗｅａｋを区別するために桁数を多くする必要がある。

乱数計算部１３０Ａは、実施の形態１にかかる乱数計算部１３０と同様に、タグを生成するための乱数を計算する。乱数計算部１３０Ａは、ＡＤ処理部１１０Ａで生成される乱数（中間値）Ｚ及び暗号化部１２０Ａから出力された平文ブロックと、所定の行列ＡＭとを用いて、タグを生成するための値を計算する。なお、実施の形態２にかかる行列ＡＭを、以下の式１０に示す。ここで、行列ＡＭは、所定の値α＿（ｉ，ｊ）を要素とする、ω×（２＾ｂ－１）のサイズの行列である。

・・・（１０）

乱数計算部１３０Ａは、区域ごとに、乱数Ｓを計算する。乱数計算部１３０Ａは、乱数計算部１３０と実質的に同様の処理を行って、区域ごとに乱数Ｓの組を生成する。具体的には、乱数計算部１３０Ａは、区域ごとに、ＡＤ処理部１１０Ａで生成される乱数（中間値）Ｚと、暗号化部１２０Ａから出力される平文ブロック（中間値Ｚ）と、所定の行列ＡＭとを用いて、ω個の乱数Ｓの組（Ｓ＿１，・・・，Ｓ＿ω）を生成する。ここで、乱数Ｓの組は、タグＴを生成するために使用される。乱数計算部１３０Ａは、各区域において、ω個のラインｉ（１≦ｉ≦ω）それぞれについて、中間値Ｚ＿ｊとα＿（ｉ，ｊ）との乗算値の排他的論理和を計算することによって、Ｓ＿ｉを算出する。詳しくは後述する。

乱数計算部１３０Ａは、各区域＃ｋにおいて、以下の式１１に示すように、行列ＡＭを用いて中間値Ｚ＿１＾（ｋ），・・・，Ｚ＿（２＾ｂ－１）＾（ｋ）を処理して、乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。つまり、乱数計算部１３０Ａは、各区域＃ｋについて、式１０に示した同じ行列ＡＭを用いて、乱数の組を生成する。

・・・（１１）

なお、式１１から、ｉ（１≦ｉ≦ω）に対して、以下の式１２が成り立つ。

・・・（１２）

ここで、乱数計算部１３０と同様に、乱数計算部１３０Ａは、区域ごとに、Ｚとαとの乗算値の排他的論理和の各ラインの初期値をリセットする。つまり、乱数計算部１３０Ａは、各区域について、ラインｉの初期値を、０＾ｂとする。言い換えると、乱数計算部１３０Ａは、区域ごとに、乱数の組が生成される複数のラインそれぞれの初期値を、リセットする。乱数計算部１３０Ａの処理の詳細については後述する。乱数計算部１３０Ａは、各区域＃ｋについて生成された乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を、タグ生成部１４０Ａに出力する。

図１６は、１区域目つまり区域＃１についての、ＡＤ処理部１１０Ａ及び乱数計算部１３０Ａの演算の概略を示す図である。また、図１７は、１区域目つまり区域＃１についての、暗号化部１２０Ａ及び乱数計算部１３０Ａの演算の概略を示す図である。また、図１８は、２区域目つまり区域＃２についての、暗号化部１２０Ａ及び乱数計算部１３０Ａの演算の概略を示す図である。

図１６に示すように、ＡＤ処理部１１０Ａは、区域＃１について、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に処理する。具体的には、ＡＤ処理部１１０Ａは、ＡＤブロックＡ＿１をＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、中間値（乱数）であるＺ＿１＾（１）が出力される。同様に、ＡＤ処理部１１０Ａは、ＡＤブロックＡ＿２を、ＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、中間値（乱数）であるＺ＿２＾（１）が出力される。同様に、ＡＤ処理部１１０Ａは、ＡＤブロックＡ＿ａを、ＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、中間値（乱数）であるＺ＿ａ＾（１）が出力される。ＡＤ処理部１１０Ａは、暗号化結果、つまりＴＢＣ関数の出力値である中間値Ｚ＿１＾（１），・・・，Ｚ＿ａ＾（１）を、乱数計算部１３０Ａに出力する。

ここで、実施の形態１では、ＴＢＣ関数からの出力値である乱数Ｚの数は、ＡＤブロックの数よりも１つ少ない。これに対し、実施の形態２では、ＡＤブロックの並列処理が可能であることから、ＴＢＣ関数からの出力値である中間値Ｚの数は、ＡＤブロックの数と同じとなる。なお、図１６～図１８の例では、ａ＜２＾ｂ－１であるので、ＡＤ処理部１１０Ａは、区域＃１についてのみ、処理を行う。

また、図１７に示すように、暗号化部１２０Ａは、区域＃１について、平文ブロックＭ＿１，・・・，Ｍ＿ｍのうちのＭ＿１，・・・，Ｍ＿ｍ’に対して、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に暗号化処理を行う。具体的には、暗号化部１２０Ａは、平文ブロックＭ＿１を、ＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、暗号文ブロックＣ＿１が出力される。同様に、暗号化部１２０Ａは、平文ブロックＭ＿２を、ＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、暗号文ブロックＣ＿２が出力される。同様に、暗号化部１２０Ａは、平文ブロックＭ＿ｍ’を、ＴＢＣ関数で暗号化する。これにより、ＴＢＣ関数から、暗号化結果として、暗号文ブロックＣ＿ｍ’が出力される。このようにして、暗号化部１２０Ａは、Ｍ＿１，・・・，Ｍ＿ｍ’にそれぞれ対応する暗号文ブロックＣ＿１，・・・，Ｃ＿ｍ’を得る。また、暗号化部１２０Ａは、ＴＢＣ関数の入力である平文ブロックＭ＿１，・・・，Ｍ＿ｍ’を、それぞれ、中間値Ｚ＿（ａ＋１）＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）として、乱数計算部１３０Ａに出力する。

なお、ＡＤ処理部１１０Ａ及び暗号化部１２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、ＡＤ処理部１１０及び暗号化部１２０におけるものと実質的に同様の規則によって設定され得る。すなわち、ＡＤ処理部１１０Ａにおいて使用されるＴＢＣ関数に入力されるＴｗｅａｋは、関連データＡのブロックインデックスｉ（１≦ｉ≦ａ）に対して、（０＾ｎ，ｉ，０，０，０）となる。また、暗号化部１２０Ａにおいて使用されるＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉ（１≦ｉ≦ｍ’）に対して、（Ｎ，ａ，ｉ，０，０）となる。なお、区域＃１について、暗号化部１２０Ａの最後に用いられるＴＢＣ関数に入力されるＴｗｅａｋは、（Ｎ，ａ，ｍ’，１，０）である。つまり、区域の最後に用いられるＴＢＣ関数に入力されるＴｗｅａｋについては、（Ｎ，ａ，ｉ，ｘ，０）のｘを、「１」とする。このようにＴｗｅａｋを設定することによって、あるＴｗｅａｋが他のＴｗｅａｋと一致することがなくなる。

また、図１６及び図１７に示すように、乱数計算部１３０Ａは、区域＃１について、ＡＤ処理部１１０Ａ及び暗号化部１２０Ａから出力される中間値Ｚ＿１＾（１），・・・，Ｚ＿ａ＾（１），Ｚ＿（ａ＋１）＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。つまり、乱数計算部１３０Ａは、上記の式１１により、式１０に示した行列ＡＭを用いて、中間値Ｚ＿１＾（１），・・・，Ｚ＿ａ＾（１），Ｚ＿（ａ＋１）＾（１），・・・，Ｚ＿（ａ＋ｍ’）＾（１）を処理する。これにより、乱数計算部１３０Ａは、区域＃１についての乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を生成する。乱数計算部１３０Ａは、区域＃１について生成された乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を、タグ生成部１４０Ａに出力する。

また、図１８に示すように、暗号化部１２０Ａは、区域＃２について、平文ブロックＭ＿１，・・・，Ｍ＿ｍのうち、Ｍ＿ｍ’から続く（２＾ｂ－１）個のＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－１）に対して、区域＃１と同様の処理を行う。すなわち、暗号化部１２０Ａは、区域＃２について、平文ブロックＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－１）に対して、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に暗号化処理を行う。これにより、暗号化部１２０Ａは、平文ブロックＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－１）にそれぞれ対応する暗号文ブロックＣ＿（ｍ’＋１），・・・，Ｃ＿（ｍ’＋２＾ｂ－１）を得る。また、暗号化部１２０Ａは、ＴＢＣ関数の入力である平文ブロックＭ＿（ｍ’＋１），・・・，Ｍ＿（ｍ’＋２＾ｂ－１）を、それぞれ、中間値Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）として、乱数計算部１３０Ａに出力する。

また、図１８に示すように、乱数計算部１３０Ａは、区域＃２について、暗号化部１２０Ａから出力される、平文ブロックに対応する中間値Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。つまり、乱数計算部１３０Ａは、上記の式１１により、式１０に示した行列ＡＭを用いて、中間値Ｚ＿１＾（２），・・・，Ｚ＿（２＾ｂ－１）＾（２）を処理する。これにより、乱数計算部１３０Ａは、区域＃２についての乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を生成する。なお、乱数計算部１３０と同様に、乱数計算部１３０Ａは、区域＃２については、各ラインｉの初期値を０＾ｂにリセットしている。乱数計算部１３０Ａは、区域＃２について生成された乱数の組Ｓ＿１＾（２），・・・，Ｓ＿ω＾（２）を、タグ生成部１４０Ａに出力する。

なお、区域＃２について、暗号化部１２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、暗号化部１２０におけるものと実質的に同様の規則によって設定され得る。すなわち、暗号化部１２０Ａにおいて使用されるＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉ（ｍ’＋１≦ｉ≦ｍ’＋２＾ｂ－１）に対して、（Ｎ，ａ，ｉ，０，０）となる。なお、区域＃２について、暗号化部１２０Ａの最後に用いられるＴＢＣ関数に入力されるＴｗｅａｋは、（Ｎ，ａ，ｍ’＋２＾ｂ－１，１，０）である。つまり、区域の最後に用いられるＴＢＣ関数に入力されるＴｗｅａｋについては、（Ｎ，ａ，ｉ，ｘ，０）のｘを、「１」とする。このようにＴｗｅａｋを設定することによって、あるＴｗｅａｋが他のＴｗｅａｋと一致することがなくなる。

ここで、上述した比較例にかかる問題点で述べたように、行列ＡＭの列数は、２＾ｂ－１を超えてはならない。したがって、実施の形態１と同様に、実施の形態２においても、式１０で示したように、行列ＡＭの列数は、（２＾ｂ－１）個である。ここで、実施の形態２にかかる認証暗号では、各ブロックに並列に暗号化する。したがって、実施の形態２では、図１６で示すように、ａ個のＡＤブロックを処理するためには、列数をａとする行列ＡＭを準備すればよい。また、実施の形態２では、図１７及び図１８で示すように、ｍ”個の平文ブロックを処理するためには、列数をｍ”とする行列ＡＭを準備すればよい。すなわち、実施の形態２では、処理すべきブロックの数と、対応する行列ＡＭの列数とが、一致している。したがって、上述した比較例にかかる問題点で述べた行列ＡＭの条件を満たすためには、ａ＋ｍ”≦２＾ｂ－１であればよい。したがって、実施の形態２では、１つの区域に含まれるブロック（ＡＤブロック又は平文ブロック）の数を、（２＾ｂ－１）個としている。また、区域＃１について、ａ＋ｍ’＝２＾ｂ－１である。したがって、実施の形態２において１つの区域で処理できるブロックの数は、実施の形態１において１つの区域で処理できるブロックの数よりも、１つ多くてもよい。なお、ａ＋ｍ’＝２＾ｂ－１であるので、図１７のα＿（１，ａ＋ｍ’＋１）は、式１０のα＿（１，２＾ｂ－１）に対応する。

なお、図１６～図１８には、区域＃１及び区域＃２についての演算の概略が示されているが、区域＃３以降についても、図１８に示した区域＃２と実質的に同様の演算がなされる。したがって、区域＃３以降の具体的な処理の説明については省略する。なお、乱数計算部１３０Ａは、ある区域について処理を行うごとに、各ラインの初期値をリセットし、式１０に示した同じ行列ＡＭ（つまり同じ要素α）を繰り返し呼び出して、乱数の組を生成する。

なお、暗号化部１２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、図１８を用いて上述した規則に従って設定される。つまり、各区域＃ｋにおいて、１番目から（２＾ｂ－２）番目のＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉに対して、（Ｎ，ａ，ｉ，０，０）となる。また、各区域＃ｋにおいて、（２＾ｂ－１）番目のＴＢＣ関数に入力されるＴｗｅａｋは、平文Ｍのブロックインデックスｉに対して、（Ｎ，ａ，ｉ，１，０）となる。なお、ここでは、ｉは平文ブロック数ｍのインデックスであるので、ある区域＃ｋにおけるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、別の区域におけるＴＢＣ関数それぞれに入力されるＴｗｅａｋとは異なることとなる。なお、最終の区域＃βにおいて、平文ブロック数が２＾ｂ－１に満たない場合、その満たない分の中間値Ｚ＿（ｊ）＾（β）の値が０となる。これらのことは、後述する認証復号装置２０Ａにおける復号処理においても同様である。

タグ生成部１４０Ａは、実施の形態１にかかるタグ生成部１４０と同様に、タグを生成する。タグ生成部１４０Ａは、乱数計算部１３０Ａによって生成された乱数Ｓの組と、ナンスＮとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグＴを生成する。ここで、タグ生成部１４０Ａの処理は、実施の形態１にかかるタグ生成部１４０の処理と、実質的に同様である。つまり、乱数計算部１３０Ａが各区域について上述した処理を行うことによって、タグ生成部１４０Ａは、上記の式８の行列で示されるような乱数の組を得る。タグ生成部１４０Ａは、ＴＢＣ関数Ｅ_Ｋ ^～を用いて定数ｆｉｘを暗号化した暗号化結果と、ＴＢＣ関数Ｅ_Ｋ ^～’を用いて乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を暗号化した暗号化結果との排他的論理和（総和）を、タグＴ［ｉ］として生成する。タグ生成部１４０Ａは、ｉ＝１～ωについて上記の処理を行い、タグＴ［１］，・・・，Ｔ［ω］を生成する。そして、タグ生成部１４０Ａは、Ｔ［１］，・・・，Ｔ［ω］を、タグＴ＝Ｔ［１］｜｜・・・｜｜Ｔ［ω］として、出力部１５０に出力する。

図１９は、実施の形態２にかかる認証暗号化装置１０Ａの作用を説明するための図である。なお、説明の明確化のため、図１９では、関連データを空としている。上述したように、認証暗号化装置１０Ａは、平文Ｍの平文ブロックを、区域＃１，区域＃２，・・・区域＃βにそれぞれ対応する区域平文ブロックＭ［１］，Ｍ［２］，・・・，Ｍ［β］に区分けする。なお、上述したように、区域平文ブロックＭ［ｋ］それぞれには、（２＾ｂ－１）個の平文ブロックが含まれる。

そして、暗号化部１２０Ａ及び乱数計算部１３０Ａは、区域＃１について、入力されたナンスＮ及び区域平文ブロックＭ［１］を用いて、区域暗号文ブロックＣ［１］、及び、乱数の組Ｓ＿１＾（１），・・・，Ｓ＿ω＾（１）を生成する。以下同様にして、暗号化部１２０Ａ及び乱数計算部１３０Ａは、区域＃ｋそれぞれについて、入力されたナンスＮ及び区域平文ブロックＭ［ｋ］を用いて、区域暗号文ブロックＣ［ｋ］、及び、乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。そして、タグ生成部１４０Ａは、生成された乱数Ｓの組（式８で示す行列）と、ナンスＮとを入力として、上述したように、ω個の適切なナンスベースＭＡＣを用いて、タグＴ［１］，・・・，Ｔ［ω］を生成する。

このとき、暗号化部１２０Ａは、各区域それぞれについて、図１７及び図１８に示した演算をサブルーチンとして用いて、処理を行うことができる。また、乱数計算部１３０Ａは、各区域それぞれについて、式１０に示す行列ＡＭを呼び出して、図１６～図１８に示した演算をサブルーチンとして用いて、処理を行うことができる。なお、このとき、区域ごとに初期値をリセットする必要があることに留意されたい。これらのことは、後述する認証復号装置２０Ａにおける復号処理においても同様である。

＜認証復号装置＞
図２０は、実施の形態２にかかる認証復号装置２０Ａの構成を示す図である。図２０に示すように、認証復号装置２０Ａは、入力部２００と、分割部２０２Ａと、ＡＤ処理部２１０Ａと、復号部２２０Ａと、乱数計算部２３０Ａと、タグ生成部２４０Ａと、タグ検査部２５０とを有する。

認証復号装置２０Ａは、図２及び図９に示した認証復号装置２０に対応する。分割部２０２Ａは、実施の形態１にかかる分割部２０２に対応する。ＡＤ処理部２１０Ａは、実施の形態１にかかるＡＤ処理部２１０に対応する。復号部２２０Ａは、実施の形態１にかかる復号部２２０に対応する。乱数計算部２３０Ａは、実施の形態１にかかる乱数計算部２３０に対応する。タグ生成部２４０Ａは、実施の形態１にかかるタグ生成部２４０に対応する。なお、以下、認証復号装置２０Ａの構成について、主に、認証復号装置２０の構成と異なる部分について説明する。

分割部２０２Ａは、分割部１０２Ａと同様に、暗号文Ｃ及び関連データＡそれぞれを、所定長のブロックに分割する。具体的には、分割部２０２Ａは、暗号文Ｃを、それぞれｂビットの暗号文ブロックＣ＿１，・・・，Ｃ＿ｍに分割する。また、分割部２０２Ａは、関連データＡを、それぞれｂビットの長さのＡＤブロックＡ＿１，・・・，Ａ＿ａに分割する。分割部２０２Ａは、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、ＡＤ処理部２１０Ａに出力する。

また、上述した分割部１０２Ａと同様に、分割部２０２Ａは、分割されたＡＤブロックＡ＿１，・・・，Ａ＿ａ及び暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、それぞれブロック数（２＾ｂ－１）個の区域（グループ）に区分けする。つまり、１つの区域には、（２＾ｂ－１）個のブロックが含まれることとなる。このとき、分割部２０２Ａは、データ列Ｄ＝Ａ＿１｜｜・・・｜｜Ａ＿ａ｜｜Ｃ＿１｜｜・・・｜｜Ｃ＿ｍを、データ列の先頭のブロックから、区域＃１，区域＃２，・・・，区域＃βの順に区分けされるように、各区域に区分けする。なお、区分けの方法は、上述した分割部１０２Ａの場合と同様であってもよい。

なお、区域＃ｋに区分けされた暗号文ブロックのビット列を「区域暗号文ブロックＣ［ｋ］」とすると、暗号文Ｃは、Ｃ＝Ｃ［１］｜｜Ｃ［２］｜｜・・・｜｜Ｃ［β］とも表記され得る。このとき、少なくともＣ［１］及びＣ［β］以外の区域暗号文ブロックＣ［ｋ］に含まれる暗号文ブロックの数は、（２＾ｂ－１）個となる。また、関連データが空の場合、区域暗号文ブロックＣ［１］に含まれる暗号文ブロックの数も、（２＾ｂ－１）個となる。

ＡＤ処理部２１０Ａは、上述したＡＤ処理部１１０Ａと実質的に同様の処理を行う。つまり、ＡＤ処理部２１０Ａは、ＡＤブロックＡ＿１，・・・，Ａ＿ａを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて処理する。このとき、ＡＤ処理部２１０Ａは、上述した区域ごとに、ＡＤブロックを処理する。ＡＤ処理部２１０Ａは、ＴＢＣ関数の出力値（乱数）である中間値Ｚ＿１，・・・，Ｚ＿ａを乱数計算部２３０Ａに出力する。なお、ＡＤ処理部２１０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、上述したＡＤ処理部１１０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと、実質的に同様に設定されてもよい。

復号部２２０Ａは、上述した暗号化部１２０Ａにおける暗号化処理に対応した復号処理を行う。復号部２２０Ａは、暗号文ブロックＣ＿１，・・・，Ｃ＿ｍを、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数を用いて、並列に処理する。このとき、復号部２２０Ａは、上述した区域ごとに、暗号文ブロック（暗号文）を、並列に復号する。つまり、復号部２２０Ａは、区域＃１に含まれる暗号文ブロックについて、上述した暗号化部１２０Ａにおける暗号化処理に対応した復号処理を行う。そして、復号部２２０Ａは、区域＃２に含まれる暗号文ブロックについて、上述した暗号化部１２０Ａにおける暗号化処理に対応した復号処理を行う。以降、復号部２２０Ａは、区域＃ｋに含まれる暗号文ブロックについて、上述した暗号化部１２０Ａにおける暗号化処理に対応した復号処理を行う。つまり、復号部２２０Ａは、区域＃ｋに含まれる区域暗号文ブロックＣ［ｋ］について、復号を行う。復号部２２０Ａは、鍵Ｋ及びＴｗｅａｋが入力されたＴＢＣ関数（復号関数）に各暗号文ブロックを入力することで、ＴＢＣ関数の出力値として、平文ブロックを得る。この復号関数は、上述した暗号化部１２０Ａで用いられるＴＢＣ関数Ｅ_Ｋ ^～が行う暗号化処理に対応する復号処理を行うように構成されている。

復号部２２０Ａは、生成された平文ブロックＭ＿１，・・・，Ｍ＿ｍを、平文Ｍ＝Ｍ＿１｜｜・・・｜｜Ｍ＿ｍとして、タグ検査部２５０に出力する。また、復号部２２０Ａは、区域＃ｋに含まれる区域暗号文ブロックＣ［ｋ］について復号を行って、区域平文ブロックＭ［ｋ］を得る。なお、復号部２２０Ａは、得られた平文を、平文Ｍ＝Ｍ［１］｜｜Ｍ［２］｜｜・・・｜｜Ｍ［β］として、タグ検査部２５０に出力してもよい。また、復号部２２０Ａは、各区域においてＴＢＣ関数（復号関数）から出力される平文ブロック（ＴＢＣ関数の出力値）を、中間値Ｚとして、乱数計算部２３０Ａに出力する。

なお、復号部２２０Ａにおける演算は、図１７及び図１８における暗号化部１２０Ａにおいて、暗号化関数であるＴＢＣ関数を復号関数に置き換え、復号関数（ＴＢＣ関数）に暗号文ブロックを入力し、平文ブロックが出力されるように置き換えたものに対応する。なお、復号部２２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋは、上述した暗号化部１２０Ａにおいて用いられるＴＢＣ関数それぞれに入力されるＴｗｅａｋと、実質的に同様に設定されてもよい。

乱数計算部２３０Ａは、上述した乱数計算部１３０Ａと同様に、ＡＤ処理部２１０Ａ及び復号部２２０Ａで生成される乱数Ｚと、式１０に示した所定の行列ＡＭとを用いて、タグを生成するための乱数を計算する。このとき、乱数計算部２３０Ａは、区域ごとに、乱数を計算する。具体的には、乱数計算部２３０Ａは、区域ごとに、ＡＤ処理部２１０Ａ及び復号部２２０Ａで生成される中間値Ｚと、所定の行列ＡＭとを用いて、ω個の乱数Ｓの組（Ｓ＿１，・・・，Ｓ＿ω）を生成する。ここで、乱数Ｓの組は、検査用のタグＴ^＊を生成するために使用される。乱数計算部２３０Ａは、上述した乱数計算部１３０Ａと同様に、各区域において、ω個のラインｉ（１≦ｉ≦ω）それぞれについて、中間値Ｚ＿ｊとα＿（ｉ，ｊ）との乗算値の排他的論理和を行うことによって、Ｓ＿ｉを算出する。つまり、乱数計算部２３０Ａは、各区域＃ｋにおいて、上記の式１１に示すように、行列ＡＭを用いて乱数Ｚ＿１＾（ｋ），・・・，Ｚ＿（２＾ｂ－１）＾（ｋ）を処理して、乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を生成する。

ここで、乱数計算部２３０Ａは、区域ごとに、Ｚとαとの乗算値の排他的論理和の各ラインの初期値をリセットする。つまり、乱数計算部２３０Ａは、各区域について、ラインｉの初期値を、０＾ｂとする。言い換えると、乱数計算部２３０Ａは、区域ごとに、乱数の組が生成される複数のラインそれぞれの初期値を、リセットする。乱数計算部２３０Ａは、各区域＃ｋについて生成された乱数の組Ｓ＿１＾（ｋ），・・・，Ｓ＿ω＾（ｋ）を、タグ生成部２４０Ａに出力する。

タグ生成部２４０Ａは、実施の形態１にかかるタグ生成部２４０と同様に、タグを生成する。タグ生成部２４０Ａは、乱数計算部２３０Ａによって生成された乱数Ｓの組と、ナンスＮとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグＴ^＊を生成する。なお、タグＴ^＊の生成方法については、実施の形態１にかかるタグ生成部２４０におけるタグＴの生成方法と実質的に同様である。つまり、タグ生成部２４０Ａは、ＴＢＣ関数Ｅ_Ｋ ^～を用いて定数ｆｉｘを暗号化した暗号化結果と、ＴＢＣ関数Ｅ_Ｋ ^～’を用いて乱数Ｓ＿ｉ＾（１），・・・，Ｓ＿ｉ＾（β）を暗号化した暗号化結果との排他的論理和（総和）を、タグＴ^＊［ｉ］として生成する。タグ生成部２４０Ａは、ｉ＝１～ωについて上記の処理を行い、タグＴ^＊［１］，・・・，Ｔ^＊［ω］を生成する。そして、タグ生成部２４０Ａは、Ｔ^＊［１］，・・・，Ｔ^＊［ω］を、タグＴ^＊＝Ｔ^＊［１］｜｜・・・｜｜Ｔ^＊［ω］として、タグ検査部２５０に出力する。

＜効果＞
実施の形態２にかかる認証暗号システム１は、上述した実施の形態１にかかる認証暗号システム１と実質的に同様の効果を奏し得る。つまり、上述したように、実施の形態２にかかる認証暗号化装置１０Ａは、入力ブロック（ＡＤブロック及び平文ブロック）を、比較例にかかる手法で処理可能なサイズである（２＾ｂ－１）個のブロックを含む区域に区分けする。そして、実施の形態２にかかる認証暗号化装置１０Ａは、各区域で生成される乱数Ｓの組から、タグＴを適切に導出するように構成されている。これにより、実施の形態２にかかる認証暗号システム１は、比較例にかかる手法では安全性上不可能であった、（２＾ｂ－１）個以上の入力ブロックを処理することが可能となる。また、実施の形態２にかかる認証暗号システム１においても、処理可能なブロック数の制限がなくなるので、平文のサイズによらないで、一度で、暗号文を送信することが可能となる。つまり、実施の形態２においても、単一の（Ｎ，Ａ，Ｃ，Ｔ）のみの送信を行うだけでよい。したがって、通信の負荷を抑制することが可能となる。

（実施の形態３）
次に、実施の形態３について説明する。実施の形態３は、上述した実施の形態にかかる構成の概要を示している。

図２１は、実施の形態３にかかる認証暗号化装置３０の構成を示す図である。実施の形態３にかかる認証暗号化装置３０は、実施の形態１にかかる認証暗号化装置１０及び実施の形態２にかかる認証暗号化装置１０Ａに対応する。実施の形態３にかかる認証暗号化装置３０は、暗号化部３２０と、乱数計算部３３０と、タグ生成部３４０とを有する。暗号化部３２０は、暗号化手段としての機能を有する。乱数計算部３３０は、乱数計算手段（第１の乱数計算手段）としての機能を有する。タグ生成部３４０は、タグ生成手段（第１のタグ生成手段）としての機能を有する。

暗号化部３２０は、図３に示した暗号化部１２０又は図１５に示した暗号化部１２０Ａが有している機能と実質的に同様の機能によって実現できる。暗号化部３２０は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号（ＴＢＣ関数）を用いて、所定の長さ（例えばｂビット）の平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する。

ここで、上述した実施の形態では、「所定の長さの区域」は、平文ブロックのビット長をｂビットとした場合に、実施の形態１では（２＾ｂ－２）個のブロックを含み得る区域に対応し、実施の形態２では（２＾ｂ－１）個のブロックを含み得る区域に対応する。しかしながら、「所定の長さの区域」は、これらの数のブロックを含み得る区域に限られない。なお、上述したように、最後の区域では、（２＾ｂ－２）個（又は（２＾ｂ－１）個）のブロックを有する必要はない。また、関連データが入力される場合、少なくとも最初の区域では、（２＾ｂ－２）個（又は（２＾ｂ－１）個）の平文ブロックが含まれていないことがある。これらのことは、後述する実施の形態３にかかる認証復号装置４０においても同様である。

乱数計算部３３０は、図３に示した乱数計算部１３０又は図１５に示した乱数計算部１３０Ａが有している機能と実質的に同様の機能によって実現できる。乱数計算部３３０は、暗号化において、各区域におけるＴｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する。

ここで、「Ｔｗｅａｋａｂｌｅブロック暗号に関する関数」は、上述した実施の形態では、ＴＢＣ関数に対応する。また、「第１のデータ」は、実施の形態１では、ＴＢＣ関数から出力された乱数Ｚに対応する。一方、実施の形態２では、「第１のデータ」は、ＴＢＣ関数に入力される平文ブロック（中間値Ｚ）に対応する。なお、第１のデータは、ＴＢＣ関数に入力されるデータ、又は、ＴＢＣ関数から出力されるデータに限られない。第１のデータは、ＴＢＣ関数の入力データ及び出力データの両方を用いて導出されてもよい。また、「Ｔｗｅａｋａｂｌｅブロック暗号に関する関数」は、上述した実施の形態におけるＴＢＣ関数に限られない。これらのことは、後述する実施の形態３にかかる認証復号装置４０においても同様である。

また、「所定の行列」は、上述した行列ＡＭに対応するが、これに限られない。なお、上述した実施の形態１では、「所定の行列」は、式５に示した行列ＡＭに対応する。また、上述した実施の形態２では、「所定の行列」は、式１０に示した行列ＡＭに対応する。また、「所定の値」とは、上述した行列ＡＭにおける要素であるαに対応するが、これに限られない。また、乱数計算部３３０によって生成される乱数は、上述した乱数Ｓに対応するが、これに限られない。これらのことは、後述する実施の形態３にかかる認証復号装置４０においても同様である。

タグ生成部３４０は、図３に示したタグ生成部１４０又は図１５に示したタグ生成部１４０Ａが有している機能と実質的に同様の機能によって実現できる。タグ生成部３４０は、乱数の組とナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する。

ここで、生成されるタグは、上述したタグＴに対応する。また、「Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コード」は、上述した実施の形態では、ナンスベースＭＡＣに対応するが、これに限られない。これらのことは、後述する実施の形態３にかかる認証復号装置４０においても同様である。

また、上述した実施の形態のように、乱数計算部３３０は、各区域について同じ所定の行列を用いて、乱数の組を生成してもよい。また、上述した実施の形態のように、乱数計算部３３０は、乱数の組を生成する際に、区域ごとに、乱数の組が生成されるラインの初期値をリセットしてもよい。また、上述した実施の形態のように、乱数計算部３３０は、β個の区域それぞれについて、所定のセキュリティレベルを示す値ωに対応する数の乱数からなる乱数の組を生成してもよい。このとき、タグ生成部３４０は、乱数を要素とするω×βの大きさの乱数行列に基づいて、ω個のタグの組を生成してもよい。なお、「所定のセキュリティレベルを示す値ωに対応する数」は、実施の形態１ではω－１に対応し、実施の形態２ではωに対応する。また、このとき、上述した実施の形態のように、タグ生成部３４０は、ω個のメッセージ認証コードを処理してもよい。また、上述した実施の形態のように、タグ生成部３４０は、ナンスをＴｗｅａｋとして含むＴＢＣ関数を用いて定数を暗号化して得られた値と、区域ごとに生成された乱数を暗号化して得られた値との排他的論理和によって、タグを生成してもよい。これらのことは、後述する実施の形態３にかかる認証復号装置４０においても同様である。

図２２は、実施の形態３にかかる認証復号装置４０の構成を示す図である。実施の形態３にかかる認証復号装置４０は、実施の形態１にかかる認証復号装置２０及び実施の形態２にかかる認証復号装置２０Ａに対応する。実施の形態３にかかる認証復号装置４０は、復号部４２０と、乱数計算部４３０と、タグ生成部４４０と、タグ検査部４５０とを有する。復号部４２０は、復号手段としての機能を有する。乱数計算部４３０は、乱数計算手段（第２の乱数計算手段）としての機能を有する。タグ生成部４４０は、タグ生成手段（第２のタグ生成手段）としての機能を有する。タグ検査部４５０は、タグ検査手段としての機能を有する。

復号部４２０は、図９に示した復号部２２０又は図２０に示した復号部２２０Ａが有している機能と実質的に同様の機能によって実現できる。復号部４２０は、ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号（ＴＢＣ関数）を用いて、所定の長さ（例えばｂビット）の暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する。

乱数計算部４３０は、図９に示した乱数計算部２３０又は図２０に示した乱数計算部２３０Ａが有している機能と実質的に同様の機能によって実現できる。乱数計算部４３０は、復号において、各区域におけるＴｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する。

タグ生成部４４０は、図９に示したタグ生成部２４０又は図２０に示したタグ生成部２４０Ａが有している機能と実質的に同様の機能によって実現できる。タグ生成部４４０は、乱数の組とナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成する。

タグ検査部４５０は、図９又は図２０に示したタグ検査部２５０が有している機能と実質的に同様の機能によって実現できる。タグ検査部４５０は、検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行う。

実施の形態３にかかる認証暗号化装置３０及び認証復号装置４０は、上述した構成によって、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能となる。なお、認証暗号化装置３０及び認証復号装置４０を有する認証暗号システムによっても、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能となる。また、認証暗号化装置３０によって実行される認証暗号化方法及び認証暗号化方法を実行するプログラムによっても、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能となる。暗号化及び復号における遅延を抑制することが可能である。また、認証復号装置４０によって実行される認証復号方法及び認証復号方法を実行するプログラムによっても、高い安全性を実現しつつ、一度の認証暗号において処理できる平文ブロックの数を増やすことが可能となる。

（ハードウェア構成例）
上述した各実施形態に係る装置およびシステムを、１つの計算処理装置（情報処理装置、コンピュータ）を用いて実現するハードウェア資源の構成例について説明する。但し、各実施形態に係る装置（認証暗号化装置及び認証復号装置）は、物理的または機能的に少なくとも２つの計算処理装置を用いて実現されてもよい。また、各実施形態に係る装置は、専用の装置として実現されてもよいし、汎用の情報処理装置で実現されてもよい。

図２３は、各実施形態に係る装置およびシステムを実現可能な計算処理装置のハードウェア構成例を概略的に示すブロック図である。計算処理装置１０００は、ＣＰＵ１００１、揮発性記憶装置１００２、ディスク１００３、不揮発性記録媒体１００４、及び、通信ＩＦ１００７（ＩＦ：Interface）を有する。したがって、各実施形態に係る装置は、ＣＰＵ１００１、揮発性記憶装置１００２、ディスク１００３、不揮発性記録媒体１００４、及び、通信ＩＦ１００７を有しているといえる。計算処理装置１０００は、入力装置１００５及び出力装置１００６に接続可能であってもよい。計算処理装置１０００は、入力装置１００５及び出力装置１００６を備えていてもよい。また、計算処理装置１０００は、通信ＩＦ１００７を介して、他の計算処理装置、及び、通信装置と情報を送受信することができる。

不揮発性記録媒体１００４は、コンピュータが読み取り可能な、たとえば、コンパクトディスク（Compact Disc)、デジタルバーサタイルディスク（Digital Versatile Disc）である。また、不揮発性記録媒体１００４は、ＵＳＢ（Universal Serial Bus）メモリ、ソリッドステートドライブ（Solid State Drive）等であってもよい。不揮発性記録媒体１００４は、電源を供給しなくても係るプログラムを保持し、持ち運びを可能にする。なお、不揮発性記録媒体１００４は、上述した媒体に限定されない。また、不揮発性記録媒体１００４の代わりに、通信ＩＦ１００７及び通信ネットワークを介して、係るプログラムが供給されてもよい。

揮発性記憶装置１００２は、コンピュータが読み取り可能であって、一時的にデータを記憶することができる。揮発性記憶装置１００２は、ＤＲＡＭ（dynamic random Access memory）、ＳＲＡＭ（static random Access memory）等のメモリ等である。

すなわち、ＣＰＵ１００１は、ディスク１００３に格納されているソフトウェアプログラム（コンピュータ・プログラム：以下、単に「プログラム」と称する）を、実行する際に揮発性記憶装置１００２にコピーし、演算処理を実行する。ＣＰＵ１００１は、プログラムの実行に必要なデータを揮発性記憶装置１００２から読み取る。表示が必要な場合、ＣＰＵ１００１は、出力装置１００６に出力結果を表示する。外部からプログラムを入力する場合、ＣＰＵ１００１は、入力装置１００５からプログラムを取得する。ＣＰＵ１００１は、上述した図３，図９，図１５，図２０～図２２に示される各構成要素の機能（処理）に対応するプログラムを解釈し実行する。ＣＰＵ１００１は、上述した各実施形態において説明した処理を実行する。言い換えると、上述した図３，図９，図１５，図２０～図２２に示される各構成要素の機能は、ディスク１００３又は揮発性記憶装置１００２に格納されたプログラムを、ＣＰＵ１００１が実行することによって実現され得る。

すなわち、各実施形態は、上述したプログラムによっても成し得ると捉えることができる。さらに、上述したプログラムが記録されたコンピュータが読み取り可能な不揮発性の記録媒体によっても、上述した各実施形態は成し得ると捉えることができる。

（変形例）
なお、本発明は上記実施形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述したフローチャートにおいて、各処理（ステップ）の順序は、適宜、変更可能である。また、複数ある処理（ステップ）のうちの１つ以上は、省略されてもよい。

例えば、図１３に示したフローチャートにおいて、Ｓ１０８の処理は、Ｓ１０４又はＳ１０６の処理の前に実行されてもよい。さらに、Ｓ１０８の処理は、Ｓ１０４，Ｓ１０６の処理と、並行して実行され得る。このことは、図１４のフローチャートにおいても同様である。

また、上述した実施の形態１において、関連データＡ及び平文Ｍの分割は、分割部１０２によって行われるとしたが、このような構成に限られない。関連データＡの分割については、ＡＤ処理部１１０が行ってもよい。同様に、平文Ｍの分割については、暗号化部１２０が行ってもよい。また、ＡＤブロックの各区域への区分けについても、ＡＤ処理部１１０が行ってもよい。同様に、平文ブロックの各区域への区分けについても、暗号化部１２０が行ってもよい。これらの場合、分割部１０２は、なくてもよい。これらのことは、図９、図１５及び図２０に示した分割部についても同様である。

また、上述した実施の形態では、先に、ブロック（ＡＤブロック、平文ブロック又は暗号文ブロック）を各区域に区分けするとしたが、このような構成に限られない。先頭のブロックから、各区域に含まれるブロック数（実施の形態１では（２＾ｂ－１）個、実施の形態２では（２＾ｂ－１）個）のブロックを区分けして暗号化（又は復号）及び乱数の生成の処理を行ってもよい。その場合、１番目の区域についての処理が終わったら、２番目の区域についてブロックの区分けを行い、暗号化（又は復号）及び乱数の生成の処理を行ってもよい。以降の区域についても同様である。

さらに、上述した実施の形態では、タグ生成部は、全ての区域についての乱数Ｓが生成された後でタグを生成するとしたが、このような構成に限られない。タグ生成部は、各区域において乱数Ｓが生成されるたびに、タグ生成処理を進めてもよい。すなわち、タグ生成部は、上述した式８に示した乱数行列の全ての要素（乱数Ｓ）を得る前に、区域ごとに乱数Ｓが生成され乱数行列の１列目から順に乱数が生成されるごとに、タグ生成の処理を進めてもよい。この場合、タグ生成処理は、平文の暗号化処理（又は暗号文の復号処理）と、並行に実行されてもよい。

具体的には、図７において、タグ生成部は、先に、ナンス由来の乱数を生成し、仮のタグとしておく。そして、１番目の区域について乱数Ｓ＿ｉ＾（１）が生成されたら、タグ生成部は、その乱数Ｓ＿ｉ＾（１）をＴＢＣ関数で暗号化して、上記の仮のタグとの排他的論理和を算出し、仮のタグを更新する。タグ生成部は、この処理を、各区域について乱数Ｓが生成されるごとに繰り返すことで、タグＴを生成する。このような処理が行われることによって、乱数行列の全ての要素をメモリに保持することが不要となる。したがって、記憶容量を節約することが可能となる。

上述の例において、プログラムは、コンピュータに読み込まれた場合に、実施形態で説明された１又はそれ以上の機能をコンピュータに行わせるための命令群（又はソフトウェアコード）を含む。プログラムは、非一時的なコンピュータ可読媒体又は実体のある記憶媒体に格納されてもよい。限定ではなく例として、コンピュータ可読媒体又は実体のある記憶媒体は、random-access memory（RAM）、read-only memory（ROM）、フラッシュメモリ、solid-state drive（SSD）又はその他のメモリ技術、CD-ROM、digital versatile disk（DVD）、Blu-ray（登録商標）ディスク又はその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又はその他の磁気ストレージデバイスを含む。プログラムは、一時的なコンピュータ可読媒体又は通信媒体上で送信されてもよい。限定ではなく例として、一時的なコンピュータ可読媒体又は通信媒体は、電気的、光学的、音響的、またはその他の形式の伝搬信号を含む。

以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、
前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するタグ生成手段と、
を有する認証暗号化装置。
（付記２）
前記乱数計算手段は、各区域について同じ前記所定の行列を用いて、前記乱数の組を生成する
付記１に記載の認証暗号化装置。
（付記３）
前記乱数計算手段は、乱数の組を生成する際に、区域ごとに、前記乱数の組が生成されるラインの初期値をリセットする、
付記１又は２に記載の認証暗号化装置。
（付記４）
前記乱数計算手段は、β個の前記区域それぞれについて、所定のセキュリティレベルを示す値ωに対応する数の乱数からなる前記乱数の組を生成し、
前記タグ生成手段は、前記乱数を要素とするω×βの大きさの乱数行列に基づいて、ω個のタグの組を生成する、
付記１から３のいずれか１項に記載の認証暗号化装置。
（付記５）
前記タグ生成手段は、ω個のメッセージ認証コードを処理する、
付記４に記載の認証暗号化装置。
（付記６）
前記タグ生成手段は、前記ナンスをＴｗｅａｋとして含むＴｗｅａｋａｂｌｅブロック暗号を用いて定数を暗号化して得られた値と、前記区域ごとに生成された前記乱数を暗号化して得られた値との排他的論理和によって、前記タグを生成する、
付記１から５のいずれか１項に記載の認証暗号化装置。
（付記７）
前記タグ生成手段は、各区域について乱数が生成されるたびに、タグ生成処理を進める、
付記１から６のいずれか１項に記載の認証暗号化装置。
（付記８）
前記暗号化手段は、前記区域ごとに、前記平文ブロックと、当該平文ブロックの前の平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて暗号化して得られた暗号化結果との排他的論理和によって、暗号文ブロックを生成し、
前記乱数計算手段は、前記第１のデータに対応する前記暗号化結果と、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
付記１から７のいずれか１項に記載の認証暗号化装置。
（付記９）
前記暗号化手段は、前記区域ごとに、複数の前記平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて並列に暗号化することによって、暗号文ブロックを生成し、
前記乱数計算手段は、前記第１のデータに対応する前記平文ブロックと、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
付記１から７のいずれか１項に記載の認証暗号化装置。
（付記１０）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、
前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するタグ生成手段と、
前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、
を有する認証復号装置。
（付記１１）
前記乱数計算手段は、各区域について同じ前記所定の行列を用いて、前記乱数の組を生成する
付記１０に記載の認証復号装置。
（付記１２）
前記乱数計算手段は、乱数の組を生成する際に、区域ごとに、前記乱数の組が生成されるラインの初期値をリセットする、
付記１０又は１１に記載の認証復号装置。
（付記１３）
前記乱数計算手段は、β個の前記区域それぞれについて、所定のセキュリティレベルを示す値ωに対応する数の乱数からなる前記乱数の組を生成し、
前記タグ生成手段は、前記乱数を要素とするω×βの大きさの乱数行列に基づいて、ω個のタグの組を生成する、
付記１０から１２のいずれか１項に記載の認証復号装置。
（付記１４）
前記タグ生成手段は、ω個のメッセージ認証コードを処理する、
付記１３に記載の認証復号装置。
（付記１５）
前記タグ生成手段は、前記ナンスをＴｗｅａｋとして含むＴｗｅａｋａｂｌｅブロック暗号を用いて定数を暗号化して得られた値と、前記区域ごとに生成された前記乱数を暗号化して得られた値との排他的論理和によって、前記タグを生成する、
付記１０から１４のいずれか１項に記載の認証復号装置。
（付記１６）
前記タグ生成手段は、各区域について乱数が生成されるたびに、タグ生成処理を進める、
付記１０から１５のいずれか１項に記載の認証復号装置。
（付記１７）
前記復号手段は、前記区域ごとに、前記暗号文ブロックと、当該暗号文ブロックの前の暗号文ブロックを用いて得られた平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて暗号化して得られた暗号化結果との排他的論理和によって、平文ブロックを生成し、
前記乱数計算手段は、前記第１のデータに対応する前記暗号化結果と、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
付記１０から１６のいずれか１項に記載の認証復号装置。
（付記１８）
前記復号手段は、前記区域ごとに、複数の前記暗号文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて並列に復号することによって、平文ブロックを生成し、
前記乱数計算手段は、前記第１のデータに対応する前記平文ブロックと、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
付記１０から１６のいずれか１項に記載の認証復号装置。
（付記１９）
認証暗号化装置と、
前記認証暗号化装置との間で通信を行う認証復号装置と、
を有し、
前記認証暗号化装置は、
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、
前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第１の乱数計算手段と、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する第１のタグ生成手段と、
を有し、
前記認証復号装置は、
前記ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、
前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第２の乱数計算手段と、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成する第２のタグ生成手段と、
前記検査用のタグと、入力された前記認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、
を有する、
認証暗号システム。
（付記２０）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化し、
前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する、
認証暗号化方法。
（付記２１）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号し、
前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成し、
前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行う、
認証復号方法。
（付記２２）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化するステップと、
前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するステップと、
をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体。
（付記２３）
ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号するステップと、
前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、
前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するステップと、
前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うステップと、
をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体。

１ 認証暗号システム
１０ 認証暗号化装置
２０ 認証復号装置
３０ 認証暗号化装置
４０ 認証復号装置
１００ 入力部
１０２ 分割部
１０４ ナンス生成部
１１０ ＡＤ処理部
１２０ 暗号化部
１３０ 乱数計算部
１４０ タグ生成部
１５０ 出力部
２００ 入力部
２０２ 分割部
２１０ ＡＤ処理部
２２０ 復号部
２３０ 乱数計算部
２４０ タグ生成部
２５０ タグ検査部
３２０ 暗号化部
３３０ 乱数計算部
３４０ タグ生成部
４２０ 復号部
４３０ 乱数計算部
４４０ タグ生成部
４５０ タグ検査部

Claims (23)

1. ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、
   前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、
   前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するタグ生成手段と、
   を有する認証暗号化装置。
2. 前記乱数計算手段は、各区域について同じ前記所定の行列を用いて、前記乱数の組を生成する
   請求項１に記載の認証暗号化装置。
3. 前記乱数計算手段は、乱数の組を生成する際に、区域ごとに、前記乱数の組が生成されるラインの初期値をリセットする、
   請求項１又は２に記載の認証暗号化装置。
4. 前記乱数計算手段は、β個の前記区域それぞれについて、所定のセキュリティレベルを示す値ωに対応する数の乱数からなる前記乱数の組を生成し、
   前記タグ生成手段は、前記乱数を要素とするω×βの大きさの乱数行列に基づいて、ω個のタグの組を生成する、
   請求項１から３のいずれか１項に記載の認証暗号化装置。
5. 前記タグ生成手段は、ω個のメッセージ認証コードを処理する、
   請求項４に記載の認証暗号化装置。
6. 前記タグ生成手段は、前記ナンスをＴｗｅａｋとして含むＴｗｅａｋａｂｌｅブロック暗号を用いて定数を暗号化して得られた値と、前記区域ごとに生成された前記乱数を暗号化して得られた値との排他的論理和によって、前記タグを生成する、
   請求項１から５のいずれか１項に記載の認証暗号化装置。
7. 前記タグ生成手段は、各区域について乱数が生成されるたびに、タグ生成処理を進める、
   請求項１から６のいずれか１項に記載の認証暗号化装置。
8. 前記暗号化手段は、前記区域ごとに、前記平文ブロックと、当該平文ブロックの前の平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて暗号化して得られた暗号化結果との排他的論理和によって、暗号文ブロックを生成し、
   前記乱数計算手段は、前記第１のデータに対応する前記暗号化結果と、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
   請求項１から７のいずれか１項に記載の認証暗号化装置。
9. 前記暗号化手段は、前記区域ごとに、複数の前記平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて並列に暗号化することによって、暗号文ブロックを生成し、
   前記乱数計算手段は、前記第１のデータに対応する前記平文ブロックと、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
   請求項１から７のいずれか１項に記載の認証暗号化装置。
10. ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、
    前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する乱数計算手段と、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するタグ生成手段と、
    前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、
    を有する認証復号装置。
11. 前記乱数計算手段は、各区域について同じ前記所定の行列を用いて、前記乱数の組を生成する
    請求項１０に記載の認証復号装置。
12. 前記乱数計算手段は、乱数の組を生成する際に、区域ごとに、前記乱数の組が生成されるラインの初期値をリセットする、
    請求項１０又は１１に記載の認証復号装置。
13. 前記乱数計算手段は、β個の前記区域それぞれについて、所定のセキュリティレベルを示す値ωに対応する数の乱数からなる前記乱数の組を生成し、
    前記タグ生成手段は、前記乱数を要素とするω×βの大きさの乱数行列に基づいて、ω個のタグの組を生成する、
    請求項１０から１２のいずれか１項に記載の認証復号装置。
14. 前記タグ生成手段は、ω個のメッセージ認証コードを処理する、
    請求項１３に記載の認証復号装置。
15. 前記タグ生成手段は、前記ナンスをＴｗｅａｋとして含むＴｗｅａｋａｂｌｅブロック暗号を用いて定数を暗号化して得られた値と、前記区域ごとに生成された前記乱数を暗号化して得られた値との排他的論理和によって、前記タグを生成する、
    請求項１０から１４のいずれか１項に記載の認証復号装置。
16. 前記タグ生成手段は、各区域について乱数が生成されるたびに、タグ生成処理を進める、
    請求項１０から１５のいずれか１項に記載の認証復号装置。
17. 前記復号手段は、前記区域ごとに、前記暗号文ブロックと、当該暗号文ブロックの前の暗号文ブロックを用いて得られた平文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて暗号化して得られた暗号化結果との排他的論理和によって、平文ブロックを生成し、
    前記乱数計算手段は、前記第１のデータに対応する前記暗号化結果と、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
    請求項１０から１６のいずれか１項に記載の認証復号装置。
18. 前記復号手段は、前記区域ごとに、複数の前記暗号文ブロックを前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数を用いて並列に復号することによって、平文ブロックを生成し、
    前記乱数計算手段は、前記第１のデータに対応する前記平文ブロックと、前記所定の行列の要素との乗算値の排他的論理和を行うことによって、前記乱数を生成する、
    請求項１０から１６のいずれか１項に記載の認証復号装置。
19. 認証暗号化装置と、
    前記認証暗号化装置との間で通信を行う認証復号装置と、
    を有し、
    前記認証暗号化装置は、
    ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化する暗号化手段と、
    前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第１の乱数計算手段と、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する第１のタグ生成手段と、
    を有し、
    前記認証復号装置は、
    前記ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号する復号手段と、
    前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出されるデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成する第２の乱数計算手段と、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成する第２のタグ生成手段と、
    前記検査用のタグと、入力された前記認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うタグ検査手段と、
    を有する、
    認証暗号システム。
20. コンピュータが、
    ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化し、
    前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成する、
    認証暗号化方法。
21. コンピュータが、
    ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号し、
    前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成し、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成し、
    前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行う、
    認証復号方法。
22. ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの平文ブロックに分割された平文を、所定の長さの区域ごとに暗号化するステップと、
    前記暗号化において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、認証用のタグを生成するステップと、
    をコンピュータに実行させるプログラム。
23. ナンスをＴｗｅａｋとして用いたＴｗｅａｋａｂｌｅブロック暗号を用いて、所定の長さの暗号文ブロックに分割された暗号文を、所定の長さの区域ごとに復号するステップと、
    前記復号において、各区域における前記Ｔｗｅａｋａｂｌｅブロック暗号に関する関数の入力及び出力の少なくとも一方から導出される第１のデータと、所定の値を要素とする所定の行列とを用いて、区域ごとに乱数の組を生成するステップと、
    前記乱数の組と前記ナンスとを用いて、Ｔｗｅａｋａｂｌｅブロック暗号を用いたメッセージ認証コードにより、検査用のタグを生成するステップと、
    前記検査用のタグと、入力された認証用のタグとを比較することによって、改ざんの有無を検査し、検査結果を出力するための制御を行うステップと、
    をコンピュータに実行させるプログラム。

Images