認証付き暗号化装置、認証付き暗号化方法、検証付き復号装置、検証付き復号方法、暗号システム、プログラム、記録媒体
【課題】鍵を1つだけ必要とし、ブロック暗号復号関数が不要な確定的認証付き暗号技術を提供する。
【解決手段】暗号化：入力ｐ，ｑに対してブロック暗号ＥKの出力Ｌ，Ｕを求め、付帯データＨ→と平文Ｍとを入力として、ユニバーサルハッシュ（ＵＨ）関数ＦL,Uとブロック暗号ＥKとで構成されるＭＡＣの出力（認証子Ｔ）を求め、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行するＢＣＭの出力（暗号文Ｃ）を求める。復号：ｐ，ｑに対してブロック暗号ＥKの出力Ｌw，Ｕwを求め、認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと暗号文Ｃとを入力としてブロック暗号利用モードを実行するＢＣＭwの出力（平文Ｍw）を求める。付帯データＨ→と平文Ｍwとを入力として、ＵＨ関数ＦL,Uとブロック暗号ＥKとで構成されるＭＡＣwの出力Ｔwを求め、出力Ｔwと認証子Ｔとが一致するか否かを検証する。
【解決手段】暗号化：入力ｐ，ｑに対してブロック暗号ＥKの出力Ｌ，Ｕを求め、付帯データＨ→と平文Ｍとを入力として、ユニバーサルハッシュ（ＵＨ）関数ＦL,Uとブロック暗号ＥKとで構成されるＭＡＣの出力（認証子Ｔ）を求め、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行するＢＣＭの出力（暗号文Ｃ）を求める。復号：ｐ，ｑに対してブロック暗号ＥKの出力Ｌw，Ｕwを求め、認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと暗号文Ｃとを入力としてブロック暗号利用モードを実行するＢＣＭwの出力（平文Ｍw）を求める。付帯データＨ→と平文Ｍwとを入力として、ＵＨ関数ＦL,Uとブロック暗号ＥKとで構成されるＭＡＣwの出力Ｔwを求め、出力Ｔwと認証子Ｔとが一致するか否かを検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、認証付き暗号技術に関り、詳しくは、暗号化対象のメッセージに対して、当該メッセージの認証子を生成し、当該メッセージの一部（もしくは全部）を暗号化して暗号文を生成する暗号化技術と、（暗号化されないメッセージ部分と）認証子と暗号文の組を検証し、この組から元の暗号化対象であるメッセージを復号する復号技術に関する。
【背景技術】
【０００２】
一般的に秘密鍵（共通鍵）暗号技術では、暗号化処理や復号処理には「鍵」と呼ばれる秘密情報を用いる。このため、予め、暗号化装置（送信者装置）と復号装置（受信者装置）の間で同じ鍵を共有しておく。
【０００３】
暗号化対象であるメッセージは、暗号化されずにそのまま復号装置へ送信もしくは保存される部分と、暗号化されてその結果が復号装置へ送信もしくは保存される部分に分かれる。前者を「付帯データ」、後者を「平文」と呼ぶ。付帯データが無い場合も許容され、この場合メッセージ全体が平文である。平文を暗号化した結果を「暗号文」と呼ぶ。
【０００４】
いわゆる認証付き暗号では、暗号化処理によって、暗号文の他に「メッセージ認証子（ＭＡＣ：Message Authentication Code）」と呼ばれる固定長のデータが生成される。以下、「メッセージ認証子」を単に「認証子」と呼称する。また、本明細書では、慣用的表現に従い、表記「ＭＡＣ」が固定長データではなく、認証子を生成するアルゴリズムや関数を意味する場合がある。
【０００５】
認証付き暗号のうち、暗号化関数の出力が鍵と付帯データと平文のみによって決定的であるようなもの、すなわち１つの鍵と１つの付帯データと１つの平文の組み合わせに対して認証子と暗号文が一意に定まるようなものを「確定的認証付き暗号」という。確定的認証付き暗号は暗号化関数Encと復号関数Decの組（Enc，Dec）として構成される。
【０００６】
暗号化関数Encの動作は次の通りである。鍵Ｋと付帯データＨと平文Ｍを入力として、認証子Ｔと暗号文Ｃの組（Ｔ，Ｃ）を出力する。これを数式で表すと、（Ｔ，Ｃ）←EncK(Ｈ，Ｍ)となる。矢印は代入の操作を表す。
【０００７】
復号関数Decの動作は次の通りである。鍵Ｋと付帯データＨと認証子Ｔと暗号文Ｃを入力として、検証と復号を行う。検証に失敗した場合にはそれを意味する情報⊥を出力する。検証に成功した場合には、復号の結果得られた平文Ｍを出力する。これを数式で表すと、Ｍ←DecK(Ｈ，Ｔ，Ｃ)となる。検証に失敗した場合にはＭ＝⊥となっている。
【０００８】
確定的認証付き暗号が正しく動作するためには、暗号化関数Encと復号関数Decの間に整合性（完全性）が必要である。すなわち、任意の鍵Ｋと任意の付帯データＨと任意の平文Ｍに対し、（Ｔ，Ｃ）←EncK(Ｈ，Ｍ)、Ｍ'←DecK(Ｈ，Ｔ，Ｃ)を計算したとき、常にＭ'＝Ｍとなっていなければならない。
【０００９】
確定的認証付き暗号の例として、ＳＩＶと呼ばれる暗号方式（非特許文献１参照）およびＨＢＳと呼ばれる暗号方式（非特許文献２参照）がある。
【００１０】
ＳＩＶは、ＣＭＡＣ（可変長メッセージに対するＣＢＣ ＭＡＣ）およびＣＴＲと呼ばれる暗号アルゴリズムを含むアルゴリズム構成を持つ。ＣＢＣ（暗号ブロック連鎖モード）およびＣＴＲ（カウンタモード）はブロック暗号利用モード(Block cipher modes of operation)であり、ＣＭＡＣおよびＣＴＲはブロック暗号の暗号化関数ＥKを含むアルゴリズム構成を持つ（非特許文献３参照）。ＣＭＡＣおよびＣＴＲではそれぞれ独立の鍵が使用される。
【００１１】
ブロック暗号とは、固定長ｎの平文Ｍおよびこれとは別に定められた長さの鍵Ｋを入力として（平文Ｍと同じ）固定長ｎの暗号文Ｃを出力する暗号化関数ＥK：Ｍ→Ｃと、固定長ｎの暗号文Ｃと鍵Ｋを入力として固定長ｎの平文Ｍを出力する復号関数ＥK-1：Ｃ→Ｍの組で表される暗号方式である。ここで、同一の鍵Ｋによって平文Ｍを暗号化した結果を復号すれば元の平文Ｍに戻るようになっている。
【００１２】
ＨＢＳは、ユニバーサルハッシュ関数で構成されているＭＡＣと、ブロック暗号の暗号化関数ＥKを要素に持つＣＴＲを含むアルゴリズム構成を持つ。ユニバーサルハッシュ関数においてブロック暗号の暗号化関数ＥKによる特別な暗号文を鍵として流用することによって、ＨＢＳ全体の鍵はブロック暗号の暗号化関数ＥKの鍵Ｋのみになっている。また、ＣＴＲの初期値にはユニバーサルハッシュ関数の出力計算結果Ｓを用いている。認証子Ｔは、計算結果Ｓを入力とするブロック暗号の暗号化関数ＥKの出力で与えられる（Ｔ←ＥK(Ｓ)）。
【００１３】
ユニバーサルハッシュ関数の種類はいくつかあるが、ＨＢＳは有限体上の多項式による方法を採用している。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Phillip Rogaway and Thomas Shrimpton, "A Provable-Security Treatment of the Key-Wrap Problem," EUROCRYPT 2006.
【非特許文献２】Tetsu Iwata and Kan Yasuda, "HBS: A Single-Key Mode of Operation forDeterministic Authenticated Encryption," FSE 2009.
【非特許文献３】Morris Dworkin, "Recommendation for Block Cipher Modes of Operation Methods and Techniques," NIST Special Publication 800-38A 2001 Edition
【発明の概要】
【発明が解決しようとする課題】
【００１５】
このようにＳＩＶでは、鍵が2つ必要であった。他方、ＨＢＳでは、鍵は1つで足りるものの、復号処理において、認証子Ｔからユニバーサルハッシュ関数の出力計算結果Ｓを得るためにブロック暗号の復号関数ＥK-1を必要とし、さらに付帯データＨの個数の上限を予め定めておかなければならないという制約が存在した。
【００１６】
そこで本発明は、鍵を1つだけ必要とし、ブロック暗号の復号関数が不要な、確定的認証付き暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
付帯データＨ→が存在する場合：
本発明は、暗号化技術に関して、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求め（鍵生成処理）、暗号化されない付帯データＨ→と平文Ｍとを入力として、出力Ｌおよび出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求め（認証子生成処理）、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める（暗号化処理）。なお、演算ＭＡＣの出力は、付帯データＨ→と平文Ｍとを入力とするユニバーサルハッシュ関数ＦL,Uの出力Ｓに対するブロック暗号ＥKの出力ＥK(Ｓ)である。
また、復号技術に関して、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求め（鍵生成処理）、上記認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求め（復号処理）、上記付帯データＨ→と平文Ｍwとを入力として、出力Ｌwおよび出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する（検証処理）。なお、演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である。
【００１８】
付帯データＨ→が存在しない場合：
本発明は、暗号化技術に関して、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求め（鍵生成処理）、平文Ｍを入力として、出力Ｌを鍵とするユニバーサルハッシュ関数ＦLとブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求め（認証子生成処理）、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める（暗号化処理）。なお、演算ＭＡＣの出力は、平文Ｍを入力とするユニバーサルハッシュ関数ＦLの出力Ｓに対するブロック暗号ＥKの出力ＥK(Ｓ)である。
また、復号技術に関して、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求め（鍵生成処理）、上記認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求め（復号処理）、平文Ｍwを入力として、出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する（検証処理）。なお、演算ＭＡＣwの出力Ｔwは、平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である。
【００１９】
また、本発明の暗号システムは、上記認証付き暗号化装置と上記検証付き復号装置を含んで構成される。
【００２０】
また、認証付き暗号化装置としてコンピュータを機能させるプログラムによって、コンピュータを認証付き暗号化装置として作動処理させることができる。このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを認証付き暗号化装置として機能させることや、プログラムを流通させることなどが可能になる。同様に、検証付き復号装置としてコンピュータを機能させるプログラムによって、コンピュータを検証付き復号装置として作動処理させることができる。このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検証付き復号装置として機能させることや、プログラムを流通させることなどが可能になる。なお、一つの記録媒体に、これらのプログラムを記録することができる。
【発明の効果】
【００２１】
本発明に拠れば、異なる二つの入力ｐ，ｑそれぞれに対するブロック暗号ＥKの出力Ｌ，Ｌw，Ｕ，Ｕwが鍵として使用されるから、ブロック暗号ＥKの鍵Ｋだけを必要とし、また、復号処理にて認証子Ｔをブロック暗号利用モードの初期値（鍵）の一部に使用するから、ブロック暗号の復号関数が不要な確定的認証付き暗号を実現できる。また、付帯データＨ→が存在する場合、付帯データの個数の上限を決める必要がない。
【図面の簡単な説明】
【００２２】
【図１】本発明による実施形態の認証付き暗号化装置の機能構成例を示す図。
【図２】本発明による実施形態の認証付き暗号化処理を実施する処理フローを示す図。
【図３】２変数ユニバーサルハッシュ関数のスキーム。
【図４】本発明による実施形態の認証付き暗号化装置の機能構成例（変形例）を示す図。
【図５】本発明による実施形態の検証付き復号装置の機能構成例を示す図。
【図６】本発明による実施形態の検証付き復号処理を実施する処理フローを示す図。
【図７】本発明による実施形態の検証付き復号装置の機能構成例（変形例）を示す図。
【図８】本発明による実施形態の暗号システムの構成例を示す図。
【発明を実施するための形態】
【００２３】
図面を参照して、本発明の実施形態を説明する。
実施形態で説明する本発明の細部においては、数値計算処理（特に有限体上の演算）が必要となる場合があるが、数値計算処理自体は、従来的な技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成２１年７月３０日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/〉［平成２１年７月３０日検索］を参照のこと。）。
また、この点に関する文献として、参考文献１を挙げることができる。
（参考文献１）Alfred Menezes, Ian Blake, Shuhong Gao, Ron Mullin, Scott Vanstone, and Tomik Yaghoobian, "Applications of Finite Fields," Kluwer Academic Publishers, 1993.
【００２４】
≪暗号化処理EncK(Ｈ→，Ｍ)≫
図１は、認証付き暗号化装置１００の機能構成図を示している。
認証付き暗号化装置１００は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、ハードディスクである外部記憶装置、並びにこれらの入力部、出力部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置間のデータのやり取りが可能なように接続するバスなどを備えている。また必要に応じて、認証付き暗号化装置１００に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００２５】
認証付き暗号化装置１００の外部記憶装置には、認証付き暗号化処理のためのプログラム並びにこのプログラムの処理において必要となるデータなどが記憶されている〔外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。〕。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、データやその格納領域のアドレスなどを記憶する記憶装置を単に「記憶部」と呼ぶことにする。
【００２６】
認証付き暗号化装置１００の記憶部には、異なる二つの入力それぞれに対して鍵Ｋのブロック暗号ＥKの出力Ｌ，Ｕを求めるためのプログラムと、付帯データＨ→と平文Ｍとを入力として、出力Ｌおよび出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣの出力（認証子Ｔ）を求めるためのプログラムと、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力（暗号文Ｃ）を求めるためのプログラムが記憶されている。
【００２７】
認証付き暗号化装置１００では、記憶部に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭに読み込まれて、ＣＰＵで解釈実行・処理される。この結果、ＣＰＵが所定の機能（鍵生成部、認証子生成部、暗号化部）を実現することで認証付き暗号化処理が実現される。
【００２８】
次に、実施形態として、図２を参照しながら、認証付き暗号化装置１００による認証付き暗号化処理の流れを叙述的に説明する。
【００２９】
なお、本発明では復号処理においてブロック暗号の復号関数ＥK-1が不要であり、詳しくは後述するが、復号処理においてもブロック暗号の暗号化関数ＥKを用いる。よって、敢えてブロック暗号の暗号化関数と復号関数を区別する必要は無いので、暗号化処理および復号処理で用いられるブロック暗号の暗号化関数ＥKを単にブロック暗号ＥKと云うことにする。このブロック暗号ＥKは予め定められたビット長の秘密鍵Ｋを用いて、入力されたｎビットのデータに対してｎビットのデータを出力する。なお、暗号学的安全性の観点から、ブロック暗号ＥKとして暗号学的に安全と信じられているブロック暗号を用いればよい。現在、安全とみなされているブロック暗号には、例えばAES（Advanced Encryption Standard）の128ビット鍵版、Camellia（登録商標）の128ビット鍵版などがある。秘密鍵Ｋは認証付き暗号化装置１００と後述する検証付き復号装置２００とで共有される。
【００３０】
鍵生成部１０１は、０nを入力とするブロック暗号ＥKの出力Ｌ（Ｌ←ＥK(０n)）と、１nを入力とするブロック暗号ＥKの出力Ｕ（Ｕ←ＥK(１n)）を求める（ステップＳ１ｅ）。ここで０nは０のｎビット２進数表記であり、１nは１のｎビット２進数表記である。この出力Ｌと出力Ｕが後述するユニバーサルハッシュ関数ＦL,Uの鍵として使用される。
【００３１】
次に、認証子生成部１０２は、暗号化対象であるメッセージを構成する平文Ｍと付帯データＨを入力として（但し、付帯データＨが無い場合も許容される。）、ユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKで構成される演算ＭＡＣKL,U(Ｈ→,Ｍ)の出力である認証子Ｔを求める（ステップＳ２ｅ）。
【００３２】
付帯データＨは、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりとする。例えば、付帯データＨおよび部分付帯データＨjがそれぞれバイナリ系列であるとして、付帯データＨが(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)のビット結合Ｈ0‖Ｈ1‖…‖Ｈd-2で表される場合も許容される。ビット結合ｘ‖ｙは、バイナリ系列ｘとバイナリ系列ｙの結合であり、例えば、(0110)‖(101)=(0110101)である。
【００３３】
ここで説明の便宜から記号を導入する。ｄ次元ベクトルＸ→=(Ｘ0,Ｘ1,…,Ｘd-2,Ｘd-1)を考える。ただし、Ｘi∈{0,1}* (i=0,1,…,d-2,d-1)とする。ここで{0,1}*は任意のバイナリ系列であり、{0,1}*=∪k≧0{0,1}kである。このベクトル記法に倣い、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりである付帯データＨをＨ→=(Ｈ0,Ｈ1,…,Ｈd-2)とベクトル表記する。また、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりである付帯データＨと平文Ｍから構成されるメッセージを(Ｈ→,Ｍ)=(Ｈ0,Ｈ1,…,Ｈd-2,Ｍ)とｄ次元ベクトル表記する。但し、付帯データＨが無い場合、(Ｈ→,Ｍ)は１次元ベクトル(Ｍ)を意味するものとする。
【００３４】
認証子生成部１０２による具体的な処理内容は次のとおりである。まず、認証子生成部１０２は、式（１）に基づき、２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の出力Ｓを求める。図３は２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)のスキームを示している。なお、付帯データＨが無い場合は、式（１ａ）に基づき、１変数ユニバーサルハッシュ関数ＦL(Ｍ)の出力Ｓを求める。この場合の１変数ユニバーサルハッシュ関数ＦL(Ｍ)のスキームは、図３に示す２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の最下段のスキームである。
【数１】
【００３５】
式（１）に現われる記号"・"は２n個の元からなる有限体上の乗算（後述する。）を表し、記号"＋"の丸囲い文字はビット単位の排他的論理和＋XORを表す。式（１）または式（１ａ）に現れる関数ｆL(Ｘ)は式（２）で与えられる。
【数２】
【００３６】
式（２）に現われるｘは式（３）で与えられる。式（３）に現われる|Ｘ|は、データＸ（各部分付帯データＨjまたは平文Ｍ）をバイナリ系列で表したときのビット長である。Ｘ[g] (g=0,1,・・・,x-1)はデータＸをｘ分割した場合の先頭からｇ番目の部分データである。つまり、データＸおよび部分データＸ[g]がそれぞれバイナリ系列であるとして、データＸは部分データＸ[g] (g=0,1,・・・,x-1)のビット結合Ｘ[0]‖Ｘ[1]‖…‖Ｘ[x-1]で表される。このとき、|Ｘ[0]|=|Ｘ[1]|=・・・=|Ｘ[x-2]|=ｎであり、１≦|Ｘ[x-1]|≦nである。
【数３】
【００３７】
式（２）に現われるπ(Ｘ[x-1])は式（４）で与えられる。π(Ｘ[x-1])は、部分データＸ[x-1]のビット長がｎになるようにするためのパディング処理を行うパディング関数を表している。つまり、|Ｘ[x-1]|＝ｎの場合、そのままＸ[x-1]を出力し、１≦|Ｘ[x-1]|≦ｎ−１の場合、ｎビットのバイナリ系列Ｘ[x-1]‖1‖0n-1-|X[x-1]|を出力する。0n-1-|X[x-1]|は、０を(n-1-|X[x-1]|)個並べたバイナリ系列である。
【数４】
【００３８】
また、式（２）に現われるδ(Ｘ[x-1])は式（５）で与えられる。２nは２のｎビット２進数表記である。δ(Ｘ[x-1])は、|Ｘ[x-1]|＝ｎであるか否かを識別するための識別関数である。
【数５】
【００３９】
＜２n個の元からなる有限体上の乗算＞
ここで有限体上の多項式による演算について、ビット列Ａとビット列Ｂとの足し算は論理的排他和ＸＯＲにより行い、ビット列Ａとビット列Ｂとの乗算は例えば以下のように行う。まず固定長ｎビットのビット列を一変数多項式に変換する。ｎ＝１２８の場合を例として、例えばビット列１０120１００１００１を多項式ｘ127＋ｘ6＋ｘ3＋１に対応させる（０120は０を１２０個並べたビット列を表す。）。このようにｎビットのビット列Ａ，Ｂをそれぞれ最大次数ｎのｘに関する一変数多項式に対応させて、多項式の（二元体の上での）乗算を行う。この積を、予め固定された既約多項式、例えばｘ128＋ｘ7＋ｘ2＋ｘ＋１で割り、剰余を求める。この剰余は高々（ｎ−１）次の多項式であるから、この剰余をビット列に変換（上述のビット列から多項式への変換の逆変換）して、有限体上での積の結果に対応するｎビットのビット列を得る。例えば剰余がｘ50＋ｘ4＋ｘ＋１であればこの変換で得られるビット列は０77１０45１００１１である。既約多項式は暗号化処理と復号処理にて同一のものを使う必要がある。なお、この演算方法に限定されず、その他の演算方法であってもよい。
【００４０】
続いて認証子生成部１０２は、式（１）に基づく２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の出力Ｓ、または、式（１ａ）に基づく１変数ユニバーサルハッシュ関数ＦL(Ｍ)の出力Ｓを入力とするブロック暗号ＥKの出力Ｔ（Ｔ←ＥK(Ｓ)）を求める。この出力Ｔが演算ＭＡＣKL,U(Ｈ→,Ｍ)の出力であり、認証子Ｔでもある。
【００４１】
次に、暗号化部１０３は、平文ＭとＴ＃Ｕを入力としてＣＴＲ（ブロック暗号ＥKとmsb(Most Significant Bit)演算とで構成されている。）を実行する演算ＣＴＲKT#U(Ｍ)の出力である暗号文Ｃを求める（ステップＳ３ｅ）。この場合、Ｔ＃ＵはＣＴＲのカウンタに相当する。Ｔ＃ＵはＴとＵとの混合データを意味し、通常の繰り上がり算術加算＋でもよいし、ビット単位の排他的論理和＋XORでもよいし、バイナリ系列であるＴとＵをそれぞれ部分バイナリ系列Ｔr (r=0,1,・・・,s)とＵr (r=0,1,・・・,s)に分割し（ただし、|Ｔr|=|Ｕr|）、部分バイナリ系列ＴrとＵrとの加算を行い、Ｔ＋Ｕを求める多分割バイナリ算術加算でもよい。ここではＣＴＲの情報理論的安全性と演算負荷のバランスを考慮して、ｓ＝１の場合の２等分割バイナリ算術加算を例示説明する。以下、演算＃は２等分割バイナリ算術加算であることを表す記号"＋"の四角囲い文字であるとする。
【００４２】
暗号化部１０３の具体的な処理内容は次のとおりである。まず、暗号化部１０３は、式（６ａ）に従ってｍを求める。
【数６】
【００４３】
そして、暗号化部１０３は、式（６ｂ）に従って部分データＲ[g] (g=0,1,・・・,m-1)を求め、さらに、これら部分データＲ[g] (g=0,1,・・・,m-1)のビット結合Ｒ[0]‖Ｒ[1]‖…‖Ｒ[m-1]を求める。なお、式（６ｂ）において、ブロック暗号ＥKの入力は、演算＃が通常の繰り上がり算術加算＋の場合はＴ＋Ｕ＋ｇとなり、演算＃が排他的論理和の場合は、２g・（Ｔ ＋XOR Ｕw）となる（記号“・”は有限体での乗算を表す。）
【数７】
【００４４】
さらに、暗号化部１０３は、式（６ｃ）に従って暗号文Ｃを求める。式（６ｃ）に現われる演算msb(|X|,Z)は、バイナリ系列Ｚの上位|Ｘ|ビットを抜き出す処理を表す。
【数８】
【００４５】
このような処理で暗号文Ｃを求めることに限定されず、例えば次のようにして暗号文Ｃを求めてもよい。暗号化部１０３は、平文Ｍが部分データＭ[g] (g=0,1,・・・,m-1)のビット結合Ｍ[0]‖Ｍ[1]‖…‖Ｍ[m-1]で表されているとして（ただし、|Ｍ[0]|=|Ｍ[1]|=・・・=|Ｍ[m-2]|=ｎであり、１≦|Ｍ[m-1]|≦nである。）、式（６ｄ）に基づき、部分データＣ[g] (g=0,1,・・・,m-1)を求め（ただし、|Ｃ[0]|=|Ｃ[1]|=・・・=|Ｃ[m-2]|=ｎであり、１≦|Ｃ[m-1]|≦nである。）、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]を暗号文Ｃとして出力する（図４参照）。なお、ここでは、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]を暗号文Ｃとしたが、Ｃ[g] (g=0,1,・・・,m-1)の組(Ｃ[0],Ｃ[1],…,Ｃ[m-1])を暗号文Ｃとしてもよい。
【数９】
【００４６】
暗号化処理EncK(Ｈ→，Ｍ)の擬似コードを表１に示す。
【表１】
【００４７】
以上の暗号化処理によって、認証付き暗号化装置１００は、付帯データＨ→（但し、付帯データＨ→が存在する場合である。）と認証子Ｔと暗号文Ｃを出力する。付帯データＨ→（但し、付帯データＨ→が存在する場合である。）と認証子Ｔと暗号文Ｃは、図示しない通信路を経由して、あるいは、記録媒体に保存されて、検証付き復号装置２００に送られる。
【００４８】
≪復号処理DecK(Ｈ→，(Ｔ，Ｃ))≫
図５は、検証付き復号装置２００の機能構成図を示している。
検証付き復号装置２００は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、ハードディスクである外部記憶装置、並びにこれらの入力部、出力部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置間のデータのやり取りが可能なように接続するバスなどを備えている。また必要に応じて、検証付き復号装置２００に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００４９】
検証付き復号装置２００の外部記憶装置には、認証付き暗号化処理のためのプログラム並びにこのプログラムの処理において必要となるデータなどが記憶されている〔外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。〕。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、データやその格納領域のアドレスなどを記憶する記憶装置を単に「記憶部」と呼ぶことにする。
【００５０】
検証付き復号装置２００の記憶部には、異なる二つの入力それぞれに対してブロック暗号ＥKの出力Ｌw，Ｕwを求めるためのプログラムと、認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと暗号文Ｃとを入力としてブロック暗号利用モードを実行する演算ＢＣＭwの出力（平文Ｍw）を求めるためのプログラムと、付帯データＨ→と平文Ｍwとを入力として、出力Ｌwおよび出力Ｕwを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと認証子Ｔとが一致するか否かを検証するためのプログラムが記憶されている。なお、以下の説明では、記号に附された上添え字と下添え字では添え字ｗを省略している。
【００５１】
検証付き復号装置２００では、記憶部に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭに読み込まれて、ＣＰＵで解釈実行・処理される。この結果、ＣＰＵが所定の機能（鍵生成部、復号部、検証部）を実現することで検証付き復号処理が実現される。
【００５２】
次に、実施形態として、図６を参照しながら、検証付き復号装置２００による認証付き暗号化処理の流れを叙述的に説明する。
【００５３】
なお、既述のとおり、復号処理において使用されるブロック暗号ＥKは、暗号化処理において使用されるブロック暗号ＥKと同一である。従って、復号処理のために復号関数ＥK-1を準備する必要がないことが本発明の特徴の一つである。
【００５４】
鍵生成部２０１は、０nを入力とするブロック暗号ＥKの出力Ｌw（Ｌw←ＥK(０n)）と、１nを入力とするブロック暗号ＥKの出力Ｕw（Ｕw←ＥK(１n)）を求める（ステップＳ１ｄ）。ここで０nは０のｎビット２進数表記であり、１nは１のｎビット２進数表記である。この出力Ｌwと出力Ｕwが復号処理におけるユニバーサルハッシュ関数ＦL,Uの鍵として使用される。
【００５５】
次に、復号部２０２は、認証付き暗号化装置１００から送られた暗号文Ｃと、認証付き暗号化装置１００から送られた認証子Ｔと鍵生成部２０１が求めた出力Ｕwとの混合データＴ＃Ｕwとを入力としてＣＴＲ（ブロック暗号ＥKとmsb(Most Significant Bit)演算とで構成されている。）を実行する演算ＣＴＲKT#U(Ｃ)の出力である平文Ｍwを求める（ステップＳ２ｄ）。この演算ＣＴＲKT#U(Ｃ)は、入力が暗号文Ｃであること以外は、暗号化処理EncK(Ｈ→，Ｍ)で説明した演算ＣＴＲKT#U(Ｍ)と同じである。ここでの演算＃は、暗号化処理EncK(Ｈ→，Ｍ)での演算ＣＴＲKT#U(Ｍ)の演算＃と同じである。
【００５６】
復号部２０２の具体的な処理内容は次のとおりである。まず、復号部２０２は、式（７）に従ってｍを求める。
【数１０】
【００５７】
そして、復号部２０２は、式（８）に従って部分データＲw[i] (i=0,1,・・・,m-1)を求め、さらに、これら部分データＲw[i] (i=0,1,・・・,m-1)のビット結合Ｒw[0]‖Ｒw[1]‖…‖Ｒw[m-1]を求める。なお、式（８）において、ブロック暗号ＥKの入力は、演算＃が通常の繰り上がり算術加算＋の場合はＴ＋Ｕw＋ｉとなり、演算＃が排他的論理和の場合は、２g・（Ｔ ＋XOR Ｕw）となる（記号“・”は有限体での乗算を表す。）。
【数１１】
【００５８】
さらに、復号部２０２は、式（９）に従って平文Ｍwを求める。
【数１２】
【００５９】
ここでは認証付き暗号化装置１００から送られた暗号文Ｃが、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]である場合の処理の一例を示した。例えば暗号文ＣがＣ[g] (g=0,1,・・・,m-1)の組(Ｃ[0],Ｃ[1],…,Ｃ[m-1])である場合には、次の処理を行うことで平文Ｍwを得ることができる（図７参照）。
まず、復号部２０２は、式（１０）に従ってｍを求める。次に、復号部２０２は、式（１１）に基づき、部分データＭ[i] (i=0,1,・・・,m-1)を求め、Ｍw[i] (i=0,1,・・・,m-1)のビット結合Ｍw[0]‖Ｍw[1]‖…‖Ｍw[m-1]を平文Ｍwとして出力する。
【数１３】
【００６０】
次に、検証部２０３は、ステップＳ２ｄの処理で得られた平文Ｍwと認証付き暗号化装置１００から送られた付帯データＨ→を入力として（但し、付帯データＨ→が無い場合もある。）、ユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKで構成される演算ＭＡＣKL,U(Ｈ→,Ｍw)の出力Ｔ'を求め、出力Ｔ'と認証付き暗号化装置１００から送られた認証子Ｔとが一致するか否かを検証する（ステップＳ３ｄ）。この演算ＭＡＣKL,U(Ｈ→,Ｍw)は、暗号化処理EncK(Ｈ→，Ｍ)で説明した演算ＭＡＣKL,U(Ｈ→,Ｍ)と同じである。
【００６１】
検証部２０３による具体的な処理内容は次のとおりである。まず、検証部２０３は、式（１２）に基づき、２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍw)の出力Ｓwを求める。なお、付帯データＨが無い場合は、式（１２ａ）に基づき、１変数ユニバーサルハッシュ関数ＦL(Ｍw)の出力Ｓwを求める。
【数１４】
【００６２】
式（１２）または式（１２ａ）に現れる関数ｆL(Ｘ)は式（１３）で与えられる。
【数１５】
【００６３】
式（１３）に現われるｘは式（１４）で与えられる。式（１４）に現われる|Ｘ|は、データＸ（各部分付帯データＨjまたは平文Ｍw）をバイナリ系列で表したときのビット長である。
【数１６】
【００６４】
式（１３）に現われるπ(Ｘ[x-1])は上記式（４）で与えられる。また、式（１３）に現われるδ(Ｘ[x-1])は上記式（５）で与えられる。
【００６５】
続いて検証部２０３は、式（１２）に基づく２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍw)の出力Ｓw、または、式（１２ａ）に基づく１変数ユニバーサルハッシュ関数ＦL(Ｍw)の出力Ｓwを入力とするブロック暗号ＥKの出力Ｔ'（Ｔ'←ＥK(Ｓw)）を求める。この出力Ｔ'が演算ＭＡＣKL,U(Ｈ→,Ｍw)の出力である。
【００６６】
もし、Ｔ'＝Ｔならば検証成功であり、検証部２０３はステップＳ２ｄの処理で得られた平文Ｍw（＝Ｍ）を出力する。Ｔ'≠Ｔならば検証失敗であり、検証部２０３は検証失敗を意味する情報Ｍw（＝⊥）を出力する。
【００６７】
復号処理DecK(Ｈ→，(Ｔ，Ｃ))の擬似コードを表２に示す。
【表２】
【００６８】
上記実施形態では、認証付き暗号化装置１００の鍵生成部１０１と検証付き復号装置２００の鍵生成部２０１では、いずれも、０nを入力とするブロック暗号ＥKの出力Ｌ，Ｌwと、１nを入力とするブロック暗号ＥKの出力Ｕ，Ｕwを求めたが、入力は０nと１nに限定されない。予め定められた異なる二つの入力ｐ，ｑそれぞれに対して、ブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｌw←ＥK(ｐ)，Ｕ←ＥK(ｑ)，Ｕw←ＥK(ｑ)を求めればよい。ただし、入力となるｐとｑは、認証付き暗号化装置１００の鍵生成部１０１と検証付き復号装置２００の鍵生成部２０１とで同じでなければならない。
【００６９】
また、上記実施形態では、ブロック暗号利用モードとして情報理論的安全性や演算効率などの観点からＣＴＲを用いたが、これに限定されない。ＣＴＲに替えて、ＣＢＣ（暗号ブロック連鎖モード）、ＣＦＢ（暗号フィードバックモード）、ＯＦＢ（出力フィードバックモード）など初期値（ＣＴＲのカウンタやＣＢＣの初期化ベクトルに相当する。）入力型のブロック暗号利用モードを用いることができる。なお、本発明では、暗号化処理においてブロック暗号利用モードの出力に初期値を含める必要が無い。この初期値は、復号処理において、認証付き暗号化装置１００から送られた認証子Ｔと検証付き復号装置２００の鍵生成部２０１で得られる鍵Ｕから生成できるからである。
【００７０】
なお、上記各擬似コードに現れるＢＴＭ(Bivariate Tag Mixing)は本発明の略記号である。
【００７１】
≪システム≫
本発明の実施形態である暗号システム３００は、図８に示すように、複数のクライアント装置１０を含んでいる。これらの各装置は、例えばインターネットである通信網５を介して相互に通信可能とされている。
【００７２】
クライアント装置１０は、処理目的に応じて、メッセージを暗号化する認証付き暗号化装置１００として、あるいは暗号文Ｃを復号する検証付き復号装置２００として機能する。認証付き暗号化装置１００と検証付き復号装置２００の詳細は既に説明したとおりである。なお、暗号システム３００は、認証付き暗号化装置１００としてのみ機能するクライアント装置および／または検証付き復号装置２００としてのみ機能するクライアント装置を含んでもよい。
【００７３】
以上の実施形態の他、本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７４】
また、上記各装置における処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における処理機能がコンピュータ上で実現される。
【００７５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本発明の各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【技術分野】
【０００１】
本発明は、認証付き暗号技術に関り、詳しくは、暗号化対象のメッセージに対して、当該メッセージの認証子を生成し、当該メッセージの一部（もしくは全部）を暗号化して暗号文を生成する暗号化技術と、（暗号化されないメッセージ部分と）認証子と暗号文の組を検証し、この組から元の暗号化対象であるメッセージを復号する復号技術に関する。
【背景技術】
【０００２】
一般的に秘密鍵（共通鍵）暗号技術では、暗号化処理や復号処理には「鍵」と呼ばれる秘密情報を用いる。このため、予め、暗号化装置（送信者装置）と復号装置（受信者装置）の間で同じ鍵を共有しておく。
【０００３】
暗号化対象であるメッセージは、暗号化されずにそのまま復号装置へ送信もしくは保存される部分と、暗号化されてその結果が復号装置へ送信もしくは保存される部分に分かれる。前者を「付帯データ」、後者を「平文」と呼ぶ。付帯データが無い場合も許容され、この場合メッセージ全体が平文である。平文を暗号化した結果を「暗号文」と呼ぶ。
【０００４】
いわゆる認証付き暗号では、暗号化処理によって、暗号文の他に「メッセージ認証子（ＭＡＣ：Message Authentication Code）」と呼ばれる固定長のデータが生成される。以下、「メッセージ認証子」を単に「認証子」と呼称する。また、本明細書では、慣用的表現に従い、表記「ＭＡＣ」が固定長データではなく、認証子を生成するアルゴリズムや関数を意味する場合がある。
【０００５】
認証付き暗号のうち、暗号化関数の出力が鍵と付帯データと平文のみによって決定的であるようなもの、すなわち１つの鍵と１つの付帯データと１つの平文の組み合わせに対して認証子と暗号文が一意に定まるようなものを「確定的認証付き暗号」という。確定的認証付き暗号は暗号化関数Encと復号関数Decの組（Enc，Dec）として構成される。
【０００６】
暗号化関数Encの動作は次の通りである。鍵Ｋと付帯データＨと平文Ｍを入力として、認証子Ｔと暗号文Ｃの組（Ｔ，Ｃ）を出力する。これを数式で表すと、（Ｔ，Ｃ）←EncK(Ｈ，Ｍ)となる。矢印は代入の操作を表す。
【０００７】
復号関数Decの動作は次の通りである。鍵Ｋと付帯データＨと認証子Ｔと暗号文Ｃを入力として、検証と復号を行う。検証に失敗した場合にはそれを意味する情報⊥を出力する。検証に成功した場合には、復号の結果得られた平文Ｍを出力する。これを数式で表すと、Ｍ←DecK(Ｈ，Ｔ，Ｃ)となる。検証に失敗した場合にはＭ＝⊥となっている。
【０００８】
確定的認証付き暗号が正しく動作するためには、暗号化関数Encと復号関数Decの間に整合性（完全性）が必要である。すなわち、任意の鍵Ｋと任意の付帯データＨと任意の平文Ｍに対し、（Ｔ，Ｃ）←EncK(Ｈ，Ｍ)、Ｍ'←DecK(Ｈ，Ｔ，Ｃ)を計算したとき、常にＭ'＝Ｍとなっていなければならない。
【０００９】
確定的認証付き暗号の例として、ＳＩＶと呼ばれる暗号方式（非特許文献１参照）およびＨＢＳと呼ばれる暗号方式（非特許文献２参照）がある。
【００１０】
ＳＩＶは、ＣＭＡＣ（可変長メッセージに対するＣＢＣ ＭＡＣ）およびＣＴＲと呼ばれる暗号アルゴリズムを含むアルゴリズム構成を持つ。ＣＢＣ（暗号ブロック連鎖モード）およびＣＴＲ（カウンタモード）はブロック暗号利用モード(Block cipher modes of operation)であり、ＣＭＡＣおよびＣＴＲはブロック暗号の暗号化関数ＥKを含むアルゴリズム構成を持つ（非特許文献３参照）。ＣＭＡＣおよびＣＴＲではそれぞれ独立の鍵が使用される。
【００１１】
ブロック暗号とは、固定長ｎの平文Ｍおよびこれとは別に定められた長さの鍵Ｋを入力として（平文Ｍと同じ）固定長ｎの暗号文Ｃを出力する暗号化関数ＥK：Ｍ→Ｃと、固定長ｎの暗号文Ｃと鍵Ｋを入力として固定長ｎの平文Ｍを出力する復号関数ＥK-1：Ｃ→Ｍの組で表される暗号方式である。ここで、同一の鍵Ｋによって平文Ｍを暗号化した結果を復号すれば元の平文Ｍに戻るようになっている。
【００１２】
ＨＢＳは、ユニバーサルハッシュ関数で構成されているＭＡＣと、ブロック暗号の暗号化関数ＥKを要素に持つＣＴＲを含むアルゴリズム構成を持つ。ユニバーサルハッシュ関数においてブロック暗号の暗号化関数ＥKによる特別な暗号文を鍵として流用することによって、ＨＢＳ全体の鍵はブロック暗号の暗号化関数ＥKの鍵Ｋのみになっている。また、ＣＴＲの初期値にはユニバーサルハッシュ関数の出力計算結果Ｓを用いている。認証子Ｔは、計算結果Ｓを入力とするブロック暗号の暗号化関数ＥKの出力で与えられる（Ｔ←ＥK(Ｓ)）。
【００１３】
ユニバーサルハッシュ関数の種類はいくつかあるが、ＨＢＳは有限体上の多項式による方法を採用している。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Phillip Rogaway and Thomas Shrimpton, "A Provable-Security Treatment of the Key-Wrap Problem," EUROCRYPT 2006.
【非特許文献２】Tetsu Iwata and Kan Yasuda, "HBS: A Single-Key Mode of Operation forDeterministic Authenticated Encryption," FSE 2009.
【非特許文献３】Morris Dworkin, "Recommendation for Block Cipher Modes of Operation Methods and Techniques," NIST Special Publication 800-38A 2001 Edition
【発明の概要】
【発明が解決しようとする課題】
【００１５】
このようにＳＩＶでは、鍵が2つ必要であった。他方、ＨＢＳでは、鍵は1つで足りるものの、復号処理において、認証子Ｔからユニバーサルハッシュ関数の出力計算結果Ｓを得るためにブロック暗号の復号関数ＥK-1を必要とし、さらに付帯データＨの個数の上限を予め定めておかなければならないという制約が存在した。
【００１６】
そこで本発明は、鍵を1つだけ必要とし、ブロック暗号の復号関数が不要な、確定的認証付き暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
付帯データＨ→が存在する場合：
本発明は、暗号化技術に関して、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求め（鍵生成処理）、暗号化されない付帯データＨ→と平文Ｍとを入力として、出力Ｌおよび出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求め（認証子生成処理）、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める（暗号化処理）。なお、演算ＭＡＣの出力は、付帯データＨ→と平文Ｍとを入力とするユニバーサルハッシュ関数ＦL,Uの出力Ｓに対するブロック暗号ＥKの出力ＥK(Ｓ)である。
また、復号技術に関して、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求め（鍵生成処理）、上記認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求め（復号処理）、上記付帯データＨ→と平文Ｍwとを入力として、出力Ｌwおよび出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する（検証処理）。なお、演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である。
【００１８】
付帯データＨ→が存在しない場合：
本発明は、暗号化技術に関して、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求め（鍵生成処理）、平文Ｍを入力として、出力Ｌを鍵とするユニバーサルハッシュ関数ＦLとブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求め（認証子生成処理）、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める（暗号化処理）。なお、演算ＭＡＣの出力は、平文Ｍを入力とするユニバーサルハッシュ関数ＦLの出力Ｓに対するブロック暗号ＥKの出力ＥK(Ｓ)である。
また、復号技術に関して、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求め（鍵生成処理）、上記認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求め（復号処理）、平文Ｍwを入力として、出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する（検証処理）。なお、演算ＭＡＣwの出力Ｔwは、平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である。
【００１９】
また、本発明の暗号システムは、上記認証付き暗号化装置と上記検証付き復号装置を含んで構成される。
【００２０】
また、認証付き暗号化装置としてコンピュータを機能させるプログラムによって、コンピュータを認証付き暗号化装置として作動処理させることができる。このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを認証付き暗号化装置として機能させることや、プログラムを流通させることなどが可能になる。同様に、検証付き復号装置としてコンピュータを機能させるプログラムによって、コンピュータを検証付き復号装置として作動処理させることができる。このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検証付き復号装置として機能させることや、プログラムを流通させることなどが可能になる。なお、一つの記録媒体に、これらのプログラムを記録することができる。
【発明の効果】
【００２１】
本発明に拠れば、異なる二つの入力ｐ，ｑそれぞれに対するブロック暗号ＥKの出力Ｌ，Ｌw，Ｕ，Ｕwが鍵として使用されるから、ブロック暗号ＥKの鍵Ｋだけを必要とし、また、復号処理にて認証子Ｔをブロック暗号利用モードの初期値（鍵）の一部に使用するから、ブロック暗号の復号関数が不要な確定的認証付き暗号を実現できる。また、付帯データＨ→が存在する場合、付帯データの個数の上限を決める必要がない。
【図面の簡単な説明】
【００２２】
【図１】本発明による実施形態の認証付き暗号化装置の機能構成例を示す図。
【図２】本発明による実施形態の認証付き暗号化処理を実施する処理フローを示す図。
【図３】２変数ユニバーサルハッシュ関数のスキーム。
【図４】本発明による実施形態の認証付き暗号化装置の機能構成例（変形例）を示す図。
【図５】本発明による実施形態の検証付き復号装置の機能構成例を示す図。
【図６】本発明による実施形態の検証付き復号処理を実施する処理フローを示す図。
【図７】本発明による実施形態の検証付き復号装置の機能構成例（変形例）を示す図。
【図８】本発明による実施形態の暗号システムの構成例を示す図。
【発明を実施するための形態】
【００２３】
図面を参照して、本発明の実施形態を説明する。
実施形態で説明する本発明の細部においては、数値計算処理（特に有限体上の演算）が必要となる場合があるが、数値計算処理自体は、従来的な技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成２１年７月３０日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/〉［平成２１年７月３０日検索］を参照のこと。）。
また、この点に関する文献として、参考文献１を挙げることができる。
（参考文献１）Alfred Menezes, Ian Blake, Shuhong Gao, Ron Mullin, Scott Vanstone, and Tomik Yaghoobian, "Applications of Finite Fields," Kluwer Academic Publishers, 1993.
【００２４】
≪暗号化処理EncK(Ｈ→，Ｍ)≫
図１は、認証付き暗号化装置１００の機能構成図を示している。
認証付き暗号化装置１００は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、ハードディスクである外部記憶装置、並びにこれらの入力部、出力部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置間のデータのやり取りが可能なように接続するバスなどを備えている。また必要に応じて、認証付き暗号化装置１００に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００２５】
認証付き暗号化装置１００の外部記憶装置には、認証付き暗号化処理のためのプログラム並びにこのプログラムの処理において必要となるデータなどが記憶されている〔外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。〕。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、データやその格納領域のアドレスなどを記憶する記憶装置を単に「記憶部」と呼ぶことにする。
【００２６】
認証付き暗号化装置１００の記憶部には、異なる二つの入力それぞれに対して鍵Ｋのブロック暗号ＥKの出力Ｌ，Ｕを求めるためのプログラムと、付帯データＨ→と平文Ｍとを入力として、出力Ｌおよび出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣの出力（認証子Ｔ）を求めるためのプログラムと、認証子Ｔと出力Ｕとの混合データＴ＃Ｕと平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力（暗号文Ｃ）を求めるためのプログラムが記憶されている。
【００２７】
認証付き暗号化装置１００では、記憶部に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭに読み込まれて、ＣＰＵで解釈実行・処理される。この結果、ＣＰＵが所定の機能（鍵生成部、認証子生成部、暗号化部）を実現することで認証付き暗号化処理が実現される。
【００２８】
次に、実施形態として、図２を参照しながら、認証付き暗号化装置１００による認証付き暗号化処理の流れを叙述的に説明する。
【００２９】
なお、本発明では復号処理においてブロック暗号の復号関数ＥK-1が不要であり、詳しくは後述するが、復号処理においてもブロック暗号の暗号化関数ＥKを用いる。よって、敢えてブロック暗号の暗号化関数と復号関数を区別する必要は無いので、暗号化処理および復号処理で用いられるブロック暗号の暗号化関数ＥKを単にブロック暗号ＥKと云うことにする。このブロック暗号ＥKは予め定められたビット長の秘密鍵Ｋを用いて、入力されたｎビットのデータに対してｎビットのデータを出力する。なお、暗号学的安全性の観点から、ブロック暗号ＥKとして暗号学的に安全と信じられているブロック暗号を用いればよい。現在、安全とみなされているブロック暗号には、例えばAES（Advanced Encryption Standard）の128ビット鍵版、Camellia（登録商標）の128ビット鍵版などがある。秘密鍵Ｋは認証付き暗号化装置１００と後述する検証付き復号装置２００とで共有される。
【００３０】
鍵生成部１０１は、０nを入力とするブロック暗号ＥKの出力Ｌ（Ｌ←ＥK(０n)）と、１nを入力とするブロック暗号ＥKの出力Ｕ（Ｕ←ＥK(１n)）を求める（ステップＳ１ｅ）。ここで０nは０のｎビット２進数表記であり、１nは１のｎビット２進数表記である。この出力Ｌと出力Ｕが後述するユニバーサルハッシュ関数ＦL,Uの鍵として使用される。
【００３１】
次に、認証子生成部１０２は、暗号化対象であるメッセージを構成する平文Ｍと付帯データＨを入力として（但し、付帯データＨが無い場合も許容される。）、ユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKで構成される演算ＭＡＣKL,U(Ｈ→,Ｍ)の出力である認証子Ｔを求める（ステップＳ２ｅ）。
【００３２】
付帯データＨは、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりとする。例えば、付帯データＨおよび部分付帯データＨjがそれぞれバイナリ系列であるとして、付帯データＨが(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)のビット結合Ｈ0‖Ｈ1‖…‖Ｈd-2で表される場合も許容される。ビット結合ｘ‖ｙは、バイナリ系列ｘとバイナリ系列ｙの結合であり、例えば、(0110)‖(101)=(0110101)である。
【００３３】
ここで説明の便宜から記号を導入する。ｄ次元ベクトルＸ→=(Ｘ0,Ｘ1,…,Ｘd-2,Ｘd-1)を考える。ただし、Ｘi∈{0,1}* (i=0,1,…,d-2,d-1)とする。ここで{0,1}*は任意のバイナリ系列であり、{0,1}*=∪k≧0{0,1}kである。このベクトル記法に倣い、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりである付帯データＨをＨ→=(Ｈ0,Ｈ1,…,Ｈd-2)とベクトル表記する。また、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりである付帯データＨと平文Ｍから構成されるメッセージを(Ｈ→,Ｍ)=(Ｈ0,Ｈ1,…,Ｈd-2,Ｍ)とｄ次元ベクトル表記する。但し、付帯データＨが無い場合、(Ｈ→,Ｍ)は１次元ベクトル(Ｍ)を意味するものとする。
【００３４】
認証子生成部１０２による具体的な処理内容は次のとおりである。まず、認証子生成部１０２は、式（１）に基づき、２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の出力Ｓを求める。図３は２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)のスキームを示している。なお、付帯データＨが無い場合は、式（１ａ）に基づき、１変数ユニバーサルハッシュ関数ＦL(Ｍ)の出力Ｓを求める。この場合の１変数ユニバーサルハッシュ関数ＦL(Ｍ)のスキームは、図３に示す２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の最下段のスキームである。
【数１】
【００３５】
式（１）に現われる記号"・"は２n個の元からなる有限体上の乗算（後述する。）を表し、記号"＋"の丸囲い文字はビット単位の排他的論理和＋XORを表す。式（１）または式（１ａ）に現れる関数ｆL(Ｘ)は式（２）で与えられる。
【数２】
【００３６】
式（２）に現われるｘは式（３）で与えられる。式（３）に現われる|Ｘ|は、データＸ（各部分付帯データＨjまたは平文Ｍ）をバイナリ系列で表したときのビット長である。Ｘ[g] (g=0,1,・・・,x-1)はデータＸをｘ分割した場合の先頭からｇ番目の部分データである。つまり、データＸおよび部分データＸ[g]がそれぞれバイナリ系列であるとして、データＸは部分データＸ[g] (g=0,1,・・・,x-1)のビット結合Ｘ[0]‖Ｘ[1]‖…‖Ｘ[x-1]で表される。このとき、|Ｘ[0]|=|Ｘ[1]|=・・・=|Ｘ[x-2]|=ｎであり、１≦|Ｘ[x-1]|≦nである。
【数３】
【００３７】
式（２）に現われるπ(Ｘ[x-1])は式（４）で与えられる。π(Ｘ[x-1])は、部分データＸ[x-1]のビット長がｎになるようにするためのパディング処理を行うパディング関数を表している。つまり、|Ｘ[x-1]|＝ｎの場合、そのままＸ[x-1]を出力し、１≦|Ｘ[x-1]|≦ｎ−１の場合、ｎビットのバイナリ系列Ｘ[x-1]‖1‖0n-1-|X[x-1]|を出力する。0n-1-|X[x-1]|は、０を(n-1-|X[x-1]|)個並べたバイナリ系列である。
【数４】
【００３８】
また、式（２）に現われるδ(Ｘ[x-1])は式（５）で与えられる。２nは２のｎビット２進数表記である。δ(Ｘ[x-1])は、|Ｘ[x-1]|＝ｎであるか否かを識別するための識別関数である。
【数５】
【００３９】
＜２n個の元からなる有限体上の乗算＞
ここで有限体上の多項式による演算について、ビット列Ａとビット列Ｂとの足し算は論理的排他和ＸＯＲにより行い、ビット列Ａとビット列Ｂとの乗算は例えば以下のように行う。まず固定長ｎビットのビット列を一変数多項式に変換する。ｎ＝１２８の場合を例として、例えばビット列１０120１００１００１を多項式ｘ127＋ｘ6＋ｘ3＋１に対応させる（０120は０を１２０個並べたビット列を表す。）。このようにｎビットのビット列Ａ，Ｂをそれぞれ最大次数ｎのｘに関する一変数多項式に対応させて、多項式の（二元体の上での）乗算を行う。この積を、予め固定された既約多項式、例えばｘ128＋ｘ7＋ｘ2＋ｘ＋１で割り、剰余を求める。この剰余は高々（ｎ−１）次の多項式であるから、この剰余をビット列に変換（上述のビット列から多項式への変換の逆変換）して、有限体上での積の結果に対応するｎビットのビット列を得る。例えば剰余がｘ50＋ｘ4＋ｘ＋１であればこの変換で得られるビット列は０77１０45１００１１である。既約多項式は暗号化処理と復号処理にて同一のものを使う必要がある。なお、この演算方法に限定されず、その他の演算方法であってもよい。
【００４０】
続いて認証子生成部１０２は、式（１）に基づく２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍ)の出力Ｓ、または、式（１ａ）に基づく１変数ユニバーサルハッシュ関数ＦL(Ｍ)の出力Ｓを入力とするブロック暗号ＥKの出力Ｔ（Ｔ←ＥK(Ｓ)）を求める。この出力Ｔが演算ＭＡＣKL,U(Ｈ→,Ｍ)の出力であり、認証子Ｔでもある。
【００４１】
次に、暗号化部１０３は、平文ＭとＴ＃Ｕを入力としてＣＴＲ（ブロック暗号ＥKとmsb(Most Significant Bit)演算とで構成されている。）を実行する演算ＣＴＲKT#U(Ｍ)の出力である暗号文Ｃを求める（ステップＳ３ｅ）。この場合、Ｔ＃ＵはＣＴＲのカウンタに相当する。Ｔ＃ＵはＴとＵとの混合データを意味し、通常の繰り上がり算術加算＋でもよいし、ビット単位の排他的論理和＋XORでもよいし、バイナリ系列であるＴとＵをそれぞれ部分バイナリ系列Ｔr (r=0,1,・・・,s)とＵr (r=0,1,・・・,s)に分割し（ただし、|Ｔr|=|Ｕr|）、部分バイナリ系列ＴrとＵrとの加算を行い、Ｔ＋Ｕを求める多分割バイナリ算術加算でもよい。ここではＣＴＲの情報理論的安全性と演算負荷のバランスを考慮して、ｓ＝１の場合の２等分割バイナリ算術加算を例示説明する。以下、演算＃は２等分割バイナリ算術加算であることを表す記号"＋"の四角囲い文字であるとする。
【００４２】
暗号化部１０３の具体的な処理内容は次のとおりである。まず、暗号化部１０３は、式（６ａ）に従ってｍを求める。
【数６】
【００４３】
そして、暗号化部１０３は、式（６ｂ）に従って部分データＲ[g] (g=0,1,・・・,m-1)を求め、さらに、これら部分データＲ[g] (g=0,1,・・・,m-1)のビット結合Ｒ[0]‖Ｒ[1]‖…‖Ｒ[m-1]を求める。なお、式（６ｂ）において、ブロック暗号ＥKの入力は、演算＃が通常の繰り上がり算術加算＋の場合はＴ＋Ｕ＋ｇとなり、演算＃が排他的論理和の場合は、２g・（Ｔ ＋XOR Ｕw）となる（記号“・”は有限体での乗算を表す。）
【数７】
【００４４】
さらに、暗号化部１０３は、式（６ｃ）に従って暗号文Ｃを求める。式（６ｃ）に現われる演算msb(|X|,Z)は、バイナリ系列Ｚの上位|Ｘ|ビットを抜き出す処理を表す。
【数８】
【００４５】
このような処理で暗号文Ｃを求めることに限定されず、例えば次のようにして暗号文Ｃを求めてもよい。暗号化部１０３は、平文Ｍが部分データＭ[g] (g=0,1,・・・,m-1)のビット結合Ｍ[0]‖Ｍ[1]‖…‖Ｍ[m-1]で表されているとして（ただし、|Ｍ[0]|=|Ｍ[1]|=・・・=|Ｍ[m-2]|=ｎであり、１≦|Ｍ[m-1]|≦nである。）、式（６ｄ）に基づき、部分データＣ[g] (g=0,1,・・・,m-1)を求め（ただし、|Ｃ[0]|=|Ｃ[1]|=・・・=|Ｃ[m-2]|=ｎであり、１≦|Ｃ[m-1]|≦nである。）、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]を暗号文Ｃとして出力する（図４参照）。なお、ここでは、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]を暗号文Ｃとしたが、Ｃ[g] (g=0,1,・・・,m-1)の組(Ｃ[0],Ｃ[1],…,Ｃ[m-1])を暗号文Ｃとしてもよい。
【数９】
【００４６】
暗号化処理EncK(Ｈ→，Ｍ)の擬似コードを表１に示す。
【表１】
【００４７】
以上の暗号化処理によって、認証付き暗号化装置１００は、付帯データＨ→（但し、付帯データＨ→が存在する場合である。）と認証子Ｔと暗号文Ｃを出力する。付帯データＨ→（但し、付帯データＨ→が存在する場合である。）と認証子Ｔと暗号文Ｃは、図示しない通信路を経由して、あるいは、記録媒体に保存されて、検証付き復号装置２００に送られる。
【００４８】
≪復号処理DecK(Ｈ→，(Ｔ，Ｃ))≫
図５は、検証付き復号装置２００の機能構成図を示している。
検証付き復号装置２００は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、ハードディスクである外部記憶装置、並びにこれらの入力部、出力部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置間のデータのやり取りが可能なように接続するバスなどを備えている。また必要に応じて、検証付き復号装置２００に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００４９】
検証付き復号装置２００の外部記憶装置には、認証付き暗号化処理のためのプログラム並びにこのプログラムの処理において必要となるデータなどが記憶されている〔外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。〕。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、データやその格納領域のアドレスなどを記憶する記憶装置を単に「記憶部」と呼ぶことにする。
【００５０】
検証付き復号装置２００の記憶部には、異なる二つの入力それぞれに対してブロック暗号ＥKの出力Ｌw，Ｕwを求めるためのプログラムと、認証子Ｔと出力Ｕwとの混合データＴ＃Ｕwと暗号文Ｃとを入力としてブロック暗号利用モードを実行する演算ＢＣＭwの出力（平文Ｍw）を求めるためのプログラムと、付帯データＨ→と平文Ｍwとを入力として、出力Ｌwおよび出力Ｕwを鍵とするユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと認証子Ｔとが一致するか否かを検証するためのプログラムが記憶されている。なお、以下の説明では、記号に附された上添え字と下添え字では添え字ｗを省略している。
【００５１】
検証付き復号装置２００では、記憶部に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭに読み込まれて、ＣＰＵで解釈実行・処理される。この結果、ＣＰＵが所定の機能（鍵生成部、復号部、検証部）を実現することで検証付き復号処理が実現される。
【００５２】
次に、実施形態として、図６を参照しながら、検証付き復号装置２００による認証付き暗号化処理の流れを叙述的に説明する。
【００５３】
なお、既述のとおり、復号処理において使用されるブロック暗号ＥKは、暗号化処理において使用されるブロック暗号ＥKと同一である。従って、復号処理のために復号関数ＥK-1を準備する必要がないことが本発明の特徴の一つである。
【００５４】
鍵生成部２０１は、０nを入力とするブロック暗号ＥKの出力Ｌw（Ｌw←ＥK(０n)）と、１nを入力とするブロック暗号ＥKの出力Ｕw（Ｕw←ＥK(１n)）を求める（ステップＳ１ｄ）。ここで０nは０のｎビット２進数表記であり、１nは１のｎビット２進数表記である。この出力Ｌwと出力Ｕwが復号処理におけるユニバーサルハッシュ関数ＦL,Uの鍵として使用される。
【００５５】
次に、復号部２０２は、認証付き暗号化装置１００から送られた暗号文Ｃと、認証付き暗号化装置１００から送られた認証子Ｔと鍵生成部２０１が求めた出力Ｕwとの混合データＴ＃Ｕwとを入力としてＣＴＲ（ブロック暗号ＥKとmsb(Most Significant Bit)演算とで構成されている。）を実行する演算ＣＴＲKT#U(Ｃ)の出力である平文Ｍwを求める（ステップＳ２ｄ）。この演算ＣＴＲKT#U(Ｃ)は、入力が暗号文Ｃであること以外は、暗号化処理EncK(Ｈ→，Ｍ)で説明した演算ＣＴＲKT#U(Ｍ)と同じである。ここでの演算＃は、暗号化処理EncK(Ｈ→，Ｍ)での演算ＣＴＲKT#U(Ｍ)の演算＃と同じである。
【００５６】
復号部２０２の具体的な処理内容は次のとおりである。まず、復号部２０２は、式（７）に従ってｍを求める。
【数１０】
【００５７】
そして、復号部２０２は、式（８）に従って部分データＲw[i] (i=0,1,・・・,m-1)を求め、さらに、これら部分データＲw[i] (i=0,1,・・・,m-1)のビット結合Ｒw[0]‖Ｒw[1]‖…‖Ｒw[m-1]を求める。なお、式（８）において、ブロック暗号ＥKの入力は、演算＃が通常の繰り上がり算術加算＋の場合はＴ＋Ｕw＋ｉとなり、演算＃が排他的論理和の場合は、２g・（Ｔ ＋XOR Ｕw）となる（記号“・”は有限体での乗算を表す。）。
【数１１】
【００５８】
さらに、復号部２０２は、式（９）に従って平文Ｍwを求める。
【数１２】
【００５９】
ここでは認証付き暗号化装置１００から送られた暗号文Ｃが、Ｃ[g] (g=0,1,・・・,m-1)のビット結合Ｃ[0]‖Ｃ[1]‖…‖Ｃ[m-1]である場合の処理の一例を示した。例えば暗号文ＣがＣ[g] (g=0,1,・・・,m-1)の組(Ｃ[0],Ｃ[1],…,Ｃ[m-1])である場合には、次の処理を行うことで平文Ｍwを得ることができる（図７参照）。
まず、復号部２０２は、式（１０）に従ってｍを求める。次に、復号部２０２は、式（１１）に基づき、部分データＭ[i] (i=0,1,・・・,m-1)を求め、Ｍw[i] (i=0,1,・・・,m-1)のビット結合Ｍw[0]‖Ｍw[1]‖…‖Ｍw[m-1]を平文Ｍwとして出力する。
【数１３】
【００６０】
次に、検証部２０３は、ステップＳ２ｄの処理で得られた平文Ｍwと認証付き暗号化装置１００から送られた付帯データＨ→を入力として（但し、付帯データＨ→が無い場合もある。）、ユニバーサルハッシュ関数ＦL,Uとブロック暗号ＥKで構成される演算ＭＡＣKL,U(Ｈ→,Ｍw)の出力Ｔ'を求め、出力Ｔ'と認証付き暗号化装置１００から送られた認証子Ｔとが一致するか否かを検証する（ステップＳ３ｄ）。この演算ＭＡＣKL,U(Ｈ→,Ｍw)は、暗号化処理EncK(Ｈ→，Ｍ)で説明した演算ＭＡＣKL,U(Ｈ→,Ｍ)と同じである。
【００６１】
検証部２０３による具体的な処理内容は次のとおりである。まず、検証部２０３は、式（１２）に基づき、２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍw)の出力Ｓwを求める。なお、付帯データＨが無い場合は、式（１２ａ）に基づき、１変数ユニバーサルハッシュ関数ＦL(Ｍw)の出力Ｓwを求める。
【数１４】
【００６２】
式（１２）または式（１２ａ）に現れる関数ｆL(Ｘ)は式（１３）で与えられる。
【数１５】
【００６３】
式（１３）に現われるｘは式（１４）で与えられる。式（１４）に現われる|Ｘ|は、データＸ（各部分付帯データＨjまたは平文Ｍw）をバイナリ系列で表したときのビット長である。
【数１６】
【００６４】
式（１３）に現われるπ(Ｘ[x-1])は上記式（４）で与えられる。また、式（１３）に現われるδ(Ｘ[x-1])は上記式（５）で与えられる。
【００６５】
続いて検証部２０３は、式（１２）に基づく２変数ユニバーサルハッシュ関数ＦL,U(Ｈ→,Ｍw)の出力Ｓw、または、式（１２ａ）に基づく１変数ユニバーサルハッシュ関数ＦL(Ｍw)の出力Ｓwを入力とするブロック暗号ＥKの出力Ｔ'（Ｔ'←ＥK(Ｓw)）を求める。この出力Ｔ'が演算ＭＡＣKL,U(Ｈ→,Ｍw)の出力である。
【００６６】
もし、Ｔ'＝Ｔならば検証成功であり、検証部２０３はステップＳ２ｄの処理で得られた平文Ｍw（＝Ｍ）を出力する。Ｔ'≠Ｔならば検証失敗であり、検証部２０３は検証失敗を意味する情報Ｍw（＝⊥）を出力する。
【００６７】
復号処理DecK(Ｈ→，(Ｔ，Ｃ))の擬似コードを表２に示す。
【表２】
【００６８】
上記実施形態では、認証付き暗号化装置１００の鍵生成部１０１と検証付き復号装置２００の鍵生成部２０１では、いずれも、０nを入力とするブロック暗号ＥKの出力Ｌ，Ｌwと、１nを入力とするブロック暗号ＥKの出力Ｕ，Ｕwを求めたが、入力は０nと１nに限定されない。予め定められた異なる二つの入力ｐ，ｑそれぞれに対して、ブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｌw←ＥK(ｐ)，Ｕ←ＥK(ｑ)，Ｕw←ＥK(ｑ)を求めればよい。ただし、入力となるｐとｑは、認証付き暗号化装置１００の鍵生成部１０１と検証付き復号装置２００の鍵生成部２０１とで同じでなければならない。
【００６９】
また、上記実施形態では、ブロック暗号利用モードとして情報理論的安全性や演算効率などの観点からＣＴＲを用いたが、これに限定されない。ＣＴＲに替えて、ＣＢＣ（暗号ブロック連鎖モード）、ＣＦＢ（暗号フィードバックモード）、ＯＦＢ（出力フィードバックモード）など初期値（ＣＴＲのカウンタやＣＢＣの初期化ベクトルに相当する。）入力型のブロック暗号利用モードを用いることができる。なお、本発明では、暗号化処理においてブロック暗号利用モードの出力に初期値を含める必要が無い。この初期値は、復号処理において、認証付き暗号化装置１００から送られた認証子Ｔと検証付き復号装置２００の鍵生成部２０１で得られる鍵Ｕから生成できるからである。
【００７０】
なお、上記各擬似コードに現れるＢＴＭ(Bivariate Tag Mixing)は本発明の略記号である。
【００７１】
≪システム≫
本発明の実施形態である暗号システム３００は、図８に示すように、複数のクライアント装置１０を含んでいる。これらの各装置は、例えばインターネットである通信網５を介して相互に通信可能とされている。
【００７２】
クライアント装置１０は、処理目的に応じて、メッセージを暗号化する認証付き暗号化装置１００として、あるいは暗号文Ｃを復号する検証付き復号装置２００として機能する。認証付き暗号化装置１００と検証付き復号装置２００の詳細は既に説明したとおりである。なお、暗号システム３００は、認証付き暗号化装置１００としてのみ機能するクライアント装置および／または検証付き復号装置２００としてのみ機能するクライアント装置を含んでもよい。
【００７３】
以上の実施形態の他、本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７４】
また、上記各装置における処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における処理機能がコンピュータ上で実現される。
【００７５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本発明の各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【特許請求の範囲】
【請求項１】
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段と
を含み、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化装置。
【請求項２】
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段と
を含み、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化装置。
【請求項３】
請求項１に記載の認証付き暗号化装置において、
上記付帯データＨ→が、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりであり、上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦL,Uが式（ｃ１）
【数１７】
で与えられる認証付き暗号化装置。
【請求項４】
請求項２に記載の認証付き暗号化装置において、
上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦLが式（ｃ２）
【数１８】
で与えられる認証付き暗号化装置。
【請求項５】
請求項１から請求項４のいずれかに記載の認証付き暗号化装置において、
上記ブロック暗号利用モードは、初期値入力型のブロック暗号利用モードであり、上記混合データＴ＃Ｕが当該ブロック暗号利用モードの初期値として用いられる
認証付き暗号化装置。
【請求項６】
鍵生成手段が異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成ステップと、
認証子生成手段が、暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成ステップと、
暗号化手段が、上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化ステップと
を有し、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化方法。
【請求項７】
鍵生成手段が、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成ステップと、
認証子生成手段が、平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成ステップと、
暗号化手段が、上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化ステップと
を有し、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化方法。
【請求項８】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、暗号化されない付帯データＨ→と平文Ｍとを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号装置であり、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段と
を含み、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号装置。
【請求項９】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)のうち、Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、平文Ｍを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号装置であり、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段と
を含み、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号装置。
【請求項１０】
請求項８に記載の検証付き復号装置において、
上記付帯データＨ→が、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりであり、上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦL,Uが式（ｃ３）
【数１９】
で与えられる検証付き復号装置。
【請求項１１】
請求項９に記載の検証付き復号装置において、
上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦLが式（ｃ４）
【数２０】
で与えられる検証付き復号装置。
【請求項１２】
請求項８から請求項１１のいずれかに記載の検証付き復号装置において、
上記ブロック暗号利用モードは、初期値入力型のブロック暗号利用モードであり、上記混合データＴ＃Ｕwが当該ブロック暗号利用モードの初期値として用いられる
検証付き復号装置。
【請求項１３】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、暗号化されない付帯データＨ→と平文Ｍとを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号方法であり、
鍵生成手段が、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成ステップと、
復号手段が、上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号ステップと、
検証手段が、上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証ステップと
を有し、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号方法。
【請求項１４】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)のうち、Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、平文Ｍを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号方法であり、
鍵生成手段が、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成ステップと、
復号手段が、上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号ステップと、
検証手段が、上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証ステップと
を有し、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号方法。
【請求項１５】
平文の暗号化と認証子の生成を行う認証付き暗号化装置と、暗号文の復号と認証子の検証を行う検証付き復号装置とを含む暗号システムであって、
上記認証付き暗号化装置は、
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段とを含み、
上記検証付き復号装置は、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段とを含み、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)であり、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
暗号システム。
【請求項１６】
平文の暗号化と認証子の生成を行う認証付き暗号化装置と、暗号文の復号と認証子の検証を行う検証付き復号装置とを含む暗号システムであって、
上記認証付き暗号化装置は、
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段とを含み、
上記検証付き復号装置は、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段とを含み、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)であり、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
暗号システム。
【請求項１７】
請求項１から請求項５のいずれかに記載された認証付き暗号化装置および／または請求項８から請求項１２のいずれかに記載された検証付き復号装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項１７に記載されたプログラムを記録した、コンピュータが読み取り可能な記録媒体。
【請求項１】
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段と
を含み、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化装置。
【請求項２】
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段と
を含み、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化装置。
【請求項３】
請求項１に記載の認証付き暗号化装置において、
上記付帯データＨ→が、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりであり、上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦL,Uが式（ｃ１）
【数１７】
で与えられる認証付き暗号化装置。
【請求項４】
請求項２に記載の認証付き暗号化装置において、
上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦLが式（ｃ２）
【数１８】
で与えられる認証付き暗号化装置。
【請求項５】
請求項１から請求項４のいずれかに記載の認証付き暗号化装置において、
上記ブロック暗号利用モードは、初期値入力型のブロック暗号利用モードであり、上記混合データＴ＃Ｕが当該ブロック暗号利用モードの初期値として用いられる
認証付き暗号化装置。
【請求項６】
鍵生成手段が異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成ステップと、
認証子生成手段が、暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成ステップと、
暗号化手段が、上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化ステップと
を有し、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化方法。
【請求項７】
鍵生成手段が、異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成ステップと、
認証子生成手段が、平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成ステップと、
暗号化手段が、上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化ステップと
を有し、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である
認証付き暗号化方法。
【請求項８】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、暗号化されない付帯データＨ→と平文Ｍとを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号装置であり、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段と
を含み、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号装置。
【請求項９】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)のうち、Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、平文Ｍを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号装置であり、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段と
を含み、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号装置。
【請求項１０】
請求項８に記載の検証付き復号装置において、
上記付帯データＨ→が、ｄを２以上の予め定められた整数として、(ｄ−１)個の部分付帯データＨj (j=0,1,…,d-2)の集まりであり、上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦL,Uが式（ｃ３）
【数１９】
で与えられる検証付き復号装置。
【請求項１１】
請求項９に記載の検証付き復号装置において、
上記ブロック暗号ＥKがｎビットのブロック暗号である場合に、上記ユニバーサルハッシュ関数ＦLが式（ｃ４）
【数２０】
で与えられる検証付き復号装置。
【請求項１２】
請求項８から請求項１１のいずれかに記載の検証付き復号装置において、
上記ブロック暗号利用モードは、初期値入力型のブロック暗号利用モードであり、上記混合データＴ＃Ｕwが当該ブロック暗号利用モードの初期値として用いられる
検証付き復号装置。
【請求項１３】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、暗号化されない付帯データＨ→と平文Ｍとを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号方法であり、
鍵生成手段が、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成ステップと、
復号手段が、上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号ステップと、
検証手段が、上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証ステップと
を有し、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号方法。
【請求項１４】
［１］異なる二つの入力ｐ，ｑそれぞれに対して求められた鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)のうち、Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの、平文Ｍを入力としたときの出力（ただし、当該演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)である。）を認証子Ｔとし、［２］上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力である暗号文Ｃの復号を行う検証付き復号方法であり、
鍵生成手段が、上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成ステップと、
復号手段が、上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号ステップと、
検証手段が、上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証ステップと
を有し、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
検証付き復号方法。
【請求項１５】
平文の暗号化と認証子の生成を行う認証付き暗号化装置と、暗号文の復号と認証子の検証を行う検証付き復号装置とを含む暗号システムであって、
上記認証付き暗号化装置は、
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
暗号化されない付帯データＨ→と平文Ｍとを入力として、上記出力Ｌおよび上記出力Ｕを鍵とするユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段とを含み、
上記検証付き復号装置は、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記付帯データＨ→と上記平文Ｍwとを入力として、上記出力Ｌwおよび上記出力Ｕwを鍵とする上記ユニバーサルハッシュ関数ＦL,Uと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段とを含み、
上記演算ＭＡＣの出力は、上記付帯データＨ→と上記平文Ｍとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)であり、
上記演算ＭＡＣwの出力Ｔwは、上記付帯データＨ→と上記平文Ｍwとを入力とする上記ユニバーサルハッシュ関数ＦL,Uの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
暗号システム。
【請求項１６】
平文の暗号化と認証子の生成を行う認証付き暗号化装置と、暗号文の復号と認証子の検証を行う検証付き復号装置とを含む暗号システムであって、
上記認証付き暗号化装置は、
異なる二つの入力ｐ，ｑそれぞれに対して、鍵Ｋのブロック暗号ＥKの出力Ｌ←ＥK(ｐ)，Ｕ←ＥK(ｑ)を求める鍵生成手段と、
平文Ｍを入力として、上記出力Ｌを鍵とするユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣの出力を認証子Ｔとして求める認証子生成手段と、
上記認証子Ｔと上記出力Ｕとの混合データＴ＃Ｕと上記平文Ｍとを入力としてブロック暗号利用モードを実行する演算ＢＣＭの出力を暗号文Ｃとして求める暗号化手段とを含み、
上記検証付き復号装置は、
上記ｐ，ｑそれぞれに対して、上記ブロック暗号ＥKの出力Ｌw←ＥK(ｐ)，Ｕw←ＥK(ｑ)を求める鍵生成手段と、
上記認証子Ｔと上記出力Ｕwとの混合データＴ＃Ｕwと上記暗号文Ｃとを入力として上記ブロック暗号利用モードを実行する演算ＢＣＭwの出力を平文Ｍwとして求める復号手段と、
上記平文Ｍwを入力として、上記出力Ｌwを鍵とする上記ユニバーサルハッシュ関数ＦLと上記ブロック暗号ＥKとで構成される演算ＭＡＣwの出力Ｔwを求め、当該出力Ｔwと上記認証子Ｔとが一致するか否かを検証する検証手段とを含み、
上記演算ＭＡＣの出力は、上記平文Ｍを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓに対する上記ブロック暗号ＥKの出力ＥK(Ｓ)であり、
上記演算ＭＡＣwの出力Ｔwは、上記平文Ｍwを入力とする上記ユニバーサルハッシュ関数ＦLの出力Ｓwに対する上記ブロック暗号ＥKの出力ＥK(Ｓw)である
暗号システム。
【請求項１７】
請求項１から請求項５のいずれかに記載された認証付き暗号化装置および／または請求項８から請求項１２のいずれかに記載された検証付き復号装置としてコンピュータを機能させるためのプログラム。
【請求項１８】
請求項１７に記載されたプログラムを記録した、コンピュータが読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−４０９３２（Ｐ２０１１−４０９３２Ａ）
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願番号】特願２００９−１８５６２６（Ｐ２００９−１８５６２６）
【出願日】平成２１年８月１０日（２００９．８．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３９６６２）国立大学法人名古屋大学 (996)
【Ｆターム（参考）】
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願日】平成２１年８月１０日（２００９．８．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３９６６２）国立大学法人名古屋大学 (996)
【Ｆターム（参考）】
[ Back to top ]