JP7244060B2 - ブロック暗号装置、ブロック暗号方法およびプログラム - Google Patents

Description

本発明は、平文を暗号化するブロック暗号装置およびブロック暗号方法に関し、さらには、これらを実現するためのプログラムに関する。

ブロック暗号に対する解読法の一つとして中間一致攻撃が知られている。中間一致攻撃とは、ブロック暗号を二つのｓｕｂ－ｃｉｐｈｅｒに分割し、平文側から計算した中間値と暗号文側から計算した中間値uの一致を確認することで鍵の候補を絞り込む解読法である。近年、中間一致攻撃はハッシュ関数への原像攻撃として応用され、著しく改良が進んでいる。従来の中間一致攻撃の改良手法として、Biclique Cryptanalysisと呼ばれるものがある（例えば、非特許文献１参照）。Biclique Cryptanalysisは、秘密鍵をBicliqueと呼ばれる特性を満たすグループに分け効率的に中間一致攻撃を行う攻撃である（例えば、非特許文献２参照）。

A. Bogdanov, D. Khovratovich, and C. Rechberger,’Biclique Cryptanalysis of the Full AES,’ASIACRYPT 2011, LNCS 7073, pp.344--371, Springer (2011) W. Diffie, M. E. Hellman: Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer 10 (6): 74-84.

しかしながら、これまでに、Biclique Cryptanalysisに対して安全なブロック暗号を構成する手法は提案されておらず、安全なブロック暗号を構成することができていなかった。

そこで、本発明の目的の一例は、Biclique Cryptanalysisに対して安全なブロック暗号を構成することができるブロック暗号装置、ブロック暗号方法およびプログラムを提供することにある。

上記目的を達成するため、本発明の一側面におけるブロック暗号装置は、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号装置であって、
前記平文をｄ個のｎビットのデータサブブロックに分割する平文分割部と、
前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割する鍵分割部と、
前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返す暗号化部と、
前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返す鍵スケジュール処理部と、
前記暗号化部の出力と、前記鍵スケジュール処理部の出力とを演算して、暗号文を出力する演算部と、
を備え、
前記鍵スケジュール処理部において、
１ラウンド目の第２処理では、前記鍵分割部により生成された前記ｄ個のｎビットの鍵
サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記暗号化部において、
１ラウンドの第１処理では、前記平文分割部により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、ことを特徴とする。

また、上記目的を達成するため、本発明の一側面におけるブロック暗号装置は、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号装置であって、
前記平文をｄ個のｎビットのデータサブブロックに分割する平文分割部と、
前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割する鍵分割部と、
前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返す暗号化部と、
前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返す鍵スケジュール処理部と、
前記暗号化部の出力と、前記鍵スケジュール処理部の出力とを演算して、暗号文を出力する演算部と、
を備え、
前記鍵スケジュール処理部において、
１ラウンド目の第２処理では、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
前記暗号化部において、
１ラウンド目の第１処理では、前記平文分割部により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンドの前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、することを特徴とする。

また、上記目的を達成するため、本発明の一側面におけるブロック暗号方法は、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号方法
であって、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を備え、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、することを特徴とする。

また、上記目的を達成するため、本発明の一側面におけるブロック暗号方法は、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号方法であって、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を備え、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンドの前記第２処理の出力を、ラウンド関数の入力とし、
前記ステップ（ｃ）において、
１ラウンドの第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の
出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、することを特徴とする。

また、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータに、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化させるプログラムであって、
前記コンピュータに、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を実行させ、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、することを特徴とする。

更に、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータに、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化させるプログラムであって、
前記コンピュータに、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を実行させ、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、することを特徴とする。

以上のように本発明におけるブロック暗号装置、ブロック暗号方法及びプログラムによれば、Biclique Cryptanalysisに対して安全なブロック暗号を構成することができる。

図１は、本発明の実施の形態１におけるブロック暗号装置の構成図である。 図２は、本発明の実施の形態１におけるブロック暗号装置でのアルゴリズムを説明する図である。 図３は、本発明の実施の形態１におけるブロック暗号装置の動作を示すフロー図である。 図４は、Ｂｉｃｌｉｑｕｅ特性の構成方法を説明するための図である。 図５は、図４での差分の重なりが遷移する状態を示す図である。 図６は、本発明の実施の形態１におけるブロック暗号装置による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図７は、本発明の実施の形態１におけるブロック暗号装置による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図８は、変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図９は、変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図１０は、本発明の実施の形態２におけるブロック暗号装置でのアルゴリズムを説明する図である。 図１１は、本発明の実施の形態２におけるブロック暗号装置の動作を示すフロー図である。 図１２は、本実施の形態２におけるブロック暗号装置による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図１３は、本実施の形態２におけるブロック暗号装置による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図１４は、変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図１５は、変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。 図１６は、本発明の実施の形態１、２におけるブロック暗号装置を実現するコンピュータの一例を示すブロック図である。

（実施の形態１）
以下、本発明の実施の形態１におけるブロック暗号装置およびブロック暗号方法について、図１～図９を参照しながら説明する。

［装置構成］
図１は、本発明の実施の形態１におけるブロック暗号装置の構成図である。

ブロック暗号装置１は、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いてブロック暗号化する装置である。図１に示すように、ブロック暗号装置１は、平文分割部２と、鍵分割部３と、暗号化部４と、鍵スケジュール処理部５と、演算部６とを備えている。

平文分割部２は、ブロック暗号装置１に入力されたｂビットの平文を、ｄ個のｎビットのデータサブブロックに分割する。

鍵分割部３は、ブロック暗号装置１に入力された秘密鍵をｄ個のｎビットの鍵サブブロックに分割する。

暗号化部４は、平文分割部２によって生成されたｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返す。

鍵スケジュール処理部５は、鍵分割部３によって生成されたｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返す。この鍵スケジュール処理部において、１ラウンド目の第２処理では、鍵分割部３により生成されたｄ個のｎビットの鍵サブブロックを全単射関数の入力とする。また、ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の第２処理の出力を、全単射関数の入力とする。

演算部６は、暗号化部４の出力と、鍵スケジュール処理部５の出力とを演算して、暗号文を出力する。

暗号化部４において、１ラウンド目の第１処理では、平文分割部２により生成されたｄ個のｎビットのデータサブブロックそれぞれと、鍵分割部３により生成されたｄ個のｎビットの鍵サブブロックそれぞれとを演算する。この演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とする。また、ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の第１処理の出力と、鍵スケジュール処理部５で実行された（ｉ－１）ラウンド目の第２処理の出力とを演算する。この演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とする。

この暗号化部４の第１処理で用いられるラウンド関数は、入力されるｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させる行
列演算式である。また、暗号化部４の第１処理で実行される演算は、算術加算、算術減算または排他的論理和のいずれかである。

この、本実施の形態１のブロック暗号装置１は、Biclique Cryptanalysisに対して安全なブロック暗号を構成することができる。

続いて、図２～図９を用いて、実施の形態１のブロック暗号装置１の構成について具体的に説明する。

図２は、本発明の実施の形態１におけるブロック暗号装置１でのアルゴリズムを説明する図である。ブロック暗号装置１は、上述した、平文分割部２と、鍵分割部３と、暗号化部４と、鍵スケジュール処理部５と、演算部６とを備えている。ブロック暗号装置１には、図２に示すように、平文と秘密鍵とが入力される。実施の形態１では、平文のブロック長はｂビットである。また、秘密鍵は、平文のブロック長と同じｂビットの鍵長を有する。

平文分割部２は、ブロック暗号装置１に入力された平文を、ｄ個のｎビットのデータサブブロックに分割する。また、鍵分割部３は、ブロック暗号装置１に入力された秘密鍵をｄ個のｎビットの鍵サブブロックに分割する。

鍵スケジュール処理部５は、全単射計算部５１を有する。全単射計算部５１は、ｄ個のｎビットの鍵サブブロックに対して、全単射関数を用いた計算を行う。鍵スケジュール処理部５では、全単射計算部５１が行う計算処理を第２処理として、この第２処理をｒラウンド繰り返す。

１ラウンド目の第２処理では、鍵分割部３により生成されたｄ個のｎビットの鍵サブブロックが、全単射計算部５１に入力される。２ラウンド目以降の第２処理では、直前のラウンドにおいて全単射計算部５１により計算された結果が、全単射計算部５１に入力される。

暗号化部４は、論理演算部４１と、Ｓ層部４２と、行列演算部４３とを有している。

論理演算部４１は、入力されるｄ個のｎビットのデータサブブロックと、ｄ個のｎビットの鍵サブブロックとの排他的論理和を演算する。なお、論理演算部４１が行う演算は、算術加算または算術減算であってもよい。

Ｓ層部４２は、論理演算部４１の出力に対して非線形変換を行う。Ｓ層部４２は、共通鍵暗号におけるＳボックス（Substitution Box）として機能する。例えば、Ｓ層部４２は、記憶した変換テーブルに基づいて非線形変換を行う。

行列演算部４３は、ｄ×ｄの行列を用いた演算処理を行う。行列演算部４３は、ＭＤＳ（Maximum Distance Separation）変換によるデータ撹拌として機能する。ＭＤＳ変換は、ＭＤＳ行列を用いた変換である。行列演算部４３におけるＭＤＳ変換では、入力されるデータサブブロックの１つに、２つのデータの排他的論理和差分の影響があると、その差分の影響が、出力されるデータサブブロックすべてに波及する。行列演算部４３におけるＭＤＳ変換は、以下の式で表される。

暗号化部４は、論理演算部４１と、Ｓ層部４２と、行列演算部４３とによる処理を１つの第１処理として、この第１処理をｒラウンド繰り返す。

１ラウンド目の第１処理では、論理演算部４１には、平文分割部２によって生成されたｄ個のｎビットのデータサブブロックと、鍵分割部３によって生成されたｄ個のｎビットの鍵サブブロックとが入力される。そして、論理演算部４１は、２つの入力データの排他的論理和を演算する。

２ラウンド目以降の第１処理では、論理演算部４１には、直前のラウンドにおいて行列演算部４３により演算された結果、および、直前のラウンドにおいて全単射計算部５１により計算された結果が入力される。

演算部６は、暗号化部４の出力と、鍵スケジュール処理部５の出力との排他的論理を演算する。演算部６が行う演算は、算術加算または算術減算であってもよい。暗号化部４の出力は、最終ラウンド（ｒラウンド）の第１処理の行列演算部４３の出力である。また、鍵スケジュール処理部５の出力は、最終ラウンド（ｒラウンド）の第２処理の全単射計算部５１の出力である。この演算部６の出力が、ブロック暗号装置１によりブロック暗号化された平文の暗号文である。

［動作説明］
次に、本発明の実施の形態１におけるブロック暗号装置１の動作について図３を用いて説明する。図３は、本発明の実施の形態１におけるブロック暗号装置１の動作を示すフロー図である。以下の説明においては、適宜図１および図２を参酌する。また、本実施の形態１では、ブロック暗号装置１を動作させることによって、ブロック暗号方法が実施される。よって、本実施の形態におけるブロック暗号方法の説明は、以下のブロック暗号装置１の動作説明に代える。

まず、前提として、ブロック暗号装置１には、ブロック長がｂビットの平文と、平文のブロック長と同じｂビットの鍵長の秘密鍵とが入力されるものとする。

上述の前提において、図３に示すように、平文分割部２は、ｂビットの平文を、ｄ個のｎビットのデータサブブロックに分割する（Ｓ１）。鍵分割部３は、ｂビットの秘密鍵をｄ個のｎビットの鍵サブブロックに分割する（Ｓ２）。

１ラウンド目において、暗号化部４の論理演算部４１は、Ｓ１で生成されたｄ個のｎビットのデータサブブロックと、Ｓ２で生成されたｄ個のｎビットの鍵サブブロックとの排他的論理和を演算する（Ｓ３）。次に、暗号化部４のＳ層部４２は、Ｓ３の排他的論理和の演算結果に対して、記憶した変換テーブルに基づいて非線形変換を行う（Ｓ４）。そして、暗号化部４の行列演算部４３は、Ｓ４の非線形変換に対して、ｄ×ｄの行列を用いたＭＤＳ変換を行う（Ｓ５）。また、鍵スケジュール処理部５の全単射計算部５１は、Ｓ２
で生成されたｄ個のｎビットの鍵サブブロックに対して、全単射関数を用いた計算を行う（Ｓ６）。

Ｓ３～Ｓ６の処理が、最終ラウンドであるｒラウンド目の処理でなければ（Ｓ７：ＮＯ）、Ｓ３～Ｓ６の処理が繰り返される。２ラウンド目以降において、暗号化部４の論理演算部４１は、Ｓ５の変換結果と、Ｓ６の計算結果との排他的論理和を演算する（Ｓ３）。また、鍵スケジュール処理部５の全単射計算部５１は、直前ラウンドでのＳ６の計算結果に対して、全単射関数を用いた計算を行う（Ｓ６）。

Ｓ３～Ｓ６の処理が、ｒラウンド目の処理であれば（Ｓ７：ＹＥＳ）、演算部６は、最終ラウンドでのＳ５の変換結果と、最終ラウンドでのＳ６の計算結果との排他的倫理和を演算する（Ｓ８）。

［実施の形態１による効果］
以上の構成のブロック暗号装置１により、Ｂｉｃｌｉｑｕｅ特性が成り立たないように、平文を暗号化することができる。以下の説明では、上記アルゴリズムにより、Ｂｉｃｌｉｑｕｅ特性が成り立たないように、平文を暗号化することができたことを示す。まず、Ｂｉｃｌｉｑｕｅ特性の構成方法について説明する。

図４は、Ｂｉｃｌｉｑｕｅ特性の構成方法を説明するための図である。図４は、平文に対して秘密鍵との排他的論理和を算出して、「ＳＢ」、「ＳＲ」、「ＭＣ」の各処理を行った際の、データの差分（色または斜線のあるブロック）が遷移する状態を示す。差分とは、２つの平文データの差のことであり、排他的論理和による差分が用いられることが多い。図４では、差分はｎビット単位の丸め差分で扱っている。「ＳＢ」は、非線形な変換を行う処理である。「ＳＲ」は、順序の入れ替えを行う処理である。「ＭＣ」は、線形変換を行う処理である。また、図４の（１）は、順方向（入力から出力方向）にデータの差分が遷移する状態を示す。図４の（２）は、逆方向（出力から入力方向）にデータの差分が遷移する状態を示す。

図４（１）において、鍵サブブロックに差分を入れる（図４（Ａ））。そして、順方向に暗号化処理を行う（図４では２ラウンド）。図４（Ｂ）は、２ラウンド処理を行った後の差分の伝搬結果を示す。図４（２）において、図４（Ｂ）に示す鍵サブブロックの差分と重ならないように、鍵サブブロックの空き領域に差分を入れる（図４（Ｃ））。そして、逆方向に暗号化処理を２ラウンド行う。図４（Ｄ）は、逆方向に２ラウンド処理を行った後の差分の伝搬結果を示す。なお、図４において、差分がどのように波及するかは、アルゴリズムに依存して決まる。

図５は、図４での差分の重なりが遷移する状態を示す図である。図５に示すように、データサブブロックには差分の重なりがあるブロックがない。

差分はブロック暗号の安全性を評価する上で、重要な指標として用いられる。差分に偏りがあると、そのブロック暗号は、２つの平文を簡単に見つけることができるとして安全ではないと評価される。一方、２つの平文を見つけることが困難であると、そのブロック暗号は安全であると評価される。なお、差分がどのように伝播するかは、アルゴリズムに依存して決まる。つまり、図５に示すように、データサブブロックには差分の重なりがないと、Ｂｉｑｌｉｑｕｅ特性が成り立ち、安全ではないブロック暗号であると評価される。

図６および図７は、本発明の実施の形態１におけるブロック暗号装置による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。図６の（１）は、順方向に
データの差分が遷移する状態を示す。図６の（２）は、逆方向にデータの差分が遷移する状態を示す。

図６（１）において、鍵サブブロックに差分を入れる（図６（Ａ））。なお、鍵サブブロックの差分が、必ずデータサブブロックに影響するように、鍵サブブロックの鍵長は、データサブブロックのブロック長と同じである必要がある。実施の形態１では、ＭＤＳ変換を行うため、順方向に２ラウンド目の暗号化処理を行うと、図６（Ｂ）に示すように、データサブブロックのすべてのブロックに、差分が伝搬する。

これにより、図６（Ｃ）に示す鍵サブブロックの差分と重ならないように、鍵サブブロックに差分を入れ（図６（Ｄ））、逆方向に暗号化処理を２ラウンド行った場合に、データブロックのすべてに差分がなくても（図６（Ｅ））、図７（Ａ）に示すように、データサブブロックには差分が重なるブロック（図７での黒ブロック）が存在する。つまり、上記のブロック暗号装置１では、１ラウンドの処理で、Ｂｉｑｌｉｑｕｅ特性が成り立たない、ブロック暗号が行われることが分かる。

以上のように、Biclique Cryptanalysisに対して安全なブロック暗号を構成することができる。

［プログラム］
本実施の形態１におけるプログラムは、コンピュータに、図３に示すステップＳ１～Ｓ８を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態１におけるブロック暗号装置１とブロック暗号方法とを実現することができる。この場合、コンピュータのプロセッサは、平文分割部２、鍵分割部３、暗号化部４、鍵スケジュール処理部５および演算部６として機能し、処理を行なう。

また、本実施の形態１におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、平文分割部２、鍵分割部３、暗号化部４、鍵スケジュール処理部５および演算部６のいずれかとして機能しても良い。

（変形例）
ここで、本実施の形態１における変形例について説明する。本変形例では、行列演算部４３は、係数に０を持たないｄ×ｄの行列を用いて、Ｓ層部４２での非線形変換に対して行列変換する。行列演算部４３における行列変換では、入力されるデータサブブロックの１つに、論理演算部４１による排他的論理和差分の影響があると、出力されるデータサブブロックすべてに必ず差分がでる。行列演算部４３における行列変換は、上記の式と同様に表される。

［変形例による効果］
図８および図９は、本変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。図８の（１）は、順方向にデータの差分が遷移する状態を示す。図８の（２）は、逆方向にデータの差分が遷移する状態を示す。

図８（１）において、鍵サブブロックに差分を入れる（図８（Ａ））。本変形例では、係数に０を持たないｄ×ｄの行列で行列変換を行うため、順方向に２ラウンド目の暗号化処理を行うと、図８（Ｂ）に示すように、データサブブロックのすべてのブロックに、差分が伝搬する。

これにより、図８（Ｃ）に示す鍵サブブロックの差分と重ならないように、鍵サブブロックに差分を入れ（図８（Ｄ））、逆方向に暗号化処理を２ラウンド行った場合に、データブロックのすべてに差分がなくても（図８（Ｅ））、図９（Ａ）に示すように、データサブブロックには差分が重なるブロック（図９での黒ブロック）が存在する。つまり、上記のブロック暗号装置１では、１ラウンドの処理で、Ｂｉｑｌｉｑｕｅ特性が成り立たない、ブロック暗号が行われることが分かる。

（実施の形態２）
次に、本発明の実施の形態２における、ブロック暗号装置、ブロック暗号方法、及びプログラムについて、図１０～図１６を参照しながら説明する。

［装置構成］
図１０は、本発明の実施の形態２におけるブロック暗号装置１Ａでのアルゴリズムを説明する図である。ブロック暗号装置１Ａは、上述した、平文分割部２と、鍵分割部３と、暗号化部４と、鍵スケジュール処理部５と、演算部６とを備えている。実施の形態２では、暗号化部４におけるラウンド関数、および、鍵スケジュール処理部５での処理が、実施の形態１と相違する。以下、その相違点を中心に説明する。

鍵スケジュール処理部５は、ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返す。鍵スケジュール処理部５において、１ラウンド目の第２処理では、鍵分割部３により生成されたｄ個のｎビットの鍵サブブロックをラウンド関数の入力とする。また、ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の第２処理の出力を、ラウンド関数の入力とする。

鍵スケジュール処理部５は、Ｓ層部５２と、行列演算部５３とを有している。

Ｓ層部５２は、ｄ個のｎビットの鍵サブブロックに対して非線形変換を行う。Ｓ層部５２は、共通鍵暗号におけるＳボックス（Substitution Box）として機能する。例えば、Ｓ層部５２は、記憶した変換テーブルに基づいて非線形変換を行う。

行列演算部５３は、ｄ×ｄの行列を用いた演算処理を行う。行列演算部５３は、ＭＤＳ（Maximum Distance Separation）変換によるデータ撹拌として機能する。ＭＤＳ変換は、ＭＤＳ行列を用いた変換である。

暗号化部４の行列演算部４３は、ｄ×ｄの行列を用いた演算処理を行う。

暗号化部４の行列演算部４３と、鍵スケジュール処理部５の行列演算部５３とで用いられるｄ×ｄの行列は、実施の形態１で説明したＢｉｑｌｉｑｕｅ特性が成り立たないようにする組合せが適宜設定される。実施の形態２では、行列演算部５３で用いられるｄ×ｄの行列を、ＭＤＳ行列としてある。

［装置動作］
次に、本実施の形態２におけるブロック暗号装置１Ａの動作について図１１を用いて説明する。図１１は、本発明の実施の形態２におけるブロック暗号装置１Ａの動作を示すフロー図である。また、本実施の形態２では、ブロック暗号装置１Ａを動作させることによって、情報処理方法が実施される。よって、本実施の形態２におけるブロック暗号方法の説明は、以下のブロック暗号装置１Ａの動作説明に代える。

まず、前提として、ブロック暗号装置１Ａには、ブロック長がｂビットの平文と、平文のブロック長と同じｂビットの鍵長の秘密鍵とが入力されるものとする。

上述の前提において、図１１に示すように、平文分割部２は、ｂビットの平文を、ｄ個のｎビットのデータサブブロックに分割する（Ｓ２１）。鍵分割部３は、ｂビットの秘密鍵をｄ個のｎビットの鍵サブブロックに分割する（Ｓ２２）。

１ラウンド目において、暗号化部４の論理演算部４１は、Ｓ２１で生成されたｄ個のｎビットのデータサブブロックと、Ｓ２２で生成されたｄ個のｎビットの鍵サブブロックとの排他的論理和を演算する（Ｓ２３）。次に、暗号化部４のＳ層部４２は、Ｓ２３の排他的論理和の演算結果に対して、記憶した変換テーブルに基づいて非線形変換を行う（Ｓ２４）。そして、暗号化部４の行列演算部４３は、Ｓ２４の非線形変換に対して、ｄ×ｄの行列を用いた行列変換を行う（Ｓ２４）。また、鍵スケジュール処理部５のＳ層部５２は、Ｓ２２で生成されたｄ個のｎビットの鍵サブブロックに対して、非線形変換を行う（Ｓ２６）。そして、鍵スケジュール処理部５の行列演算部５３は、Ｓ２６の非線形変換に対して、ｄ×ｄの行列を用いたＭＤＳ変換を行う（Ｓ２７）。

Ｓ２３～Ｓ２７の処理が、最終ラウンドであるｒラウンド目の処理でなければ（Ｓ２８：ＮＯ）、Ｓ２３～Ｓ２７の処理が繰り返される。２ラウンド目以降において、暗号化部４の論理演算部４１は、Ｓ２５の変換結果と、Ｓ２７の変換結果との排他的論理和を演算する（Ｓ２３）。また、鍵スケジュール処理部５のＳ層部５２は、直前ラウンドでのＳ２７の変換結果に対して、全非線形変換を行う（Ｓ２６）。

Ｓ２３～Ｓ２７の処理が、ｒラウンド目の処理であれば（Ｓ２８：ＹＥＳ）、演算部６は、最終ラウンドでのＳ２５の変換結果と、最終ラウンドでのＳ２７の変換結果との排他的倫理和を演算する（Ｓ２９）。

［実施の形態２における効果］
図１２および図１３は、本実施の形態２におけるブロック暗号装置１Ａによる暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。

図１２（１）において、鍵サブブロックに差分を入れる（図１２（Ａ））。実施の形態２では、鍵サブブロックに対してＭＤＳ変換を行うため、順方向に２ラウンド目の暗号化処理を行うと、図１２（Ｂ）に示すように、鍵サブブロックのすべてのブロックに、差分が伝搬する。

これにより、図１２（Ｃ）に示すように、鍵サブブロックに差分を入れ、逆方向に暗号化処理を２ラウンド行った場合に、データブロックのすべてに差分がなくても（図１２（Ｄ））、図１３（Ａ）に示すように、鍵サブブロックには差分が重なるブロック（図１３での黒ブロック）が存在する。つまり、上記のブロック暗号装置１Ａでは、１ラウンドの処理で、Ｂｉｑｌｉｑｕｅ特性が成り立たない、ブロック暗号が行われることが分かる。

［プログラム］
本実施の形態２におけるプログラムは、コンピュータに、図１１に示すステップＳ２１～Ｓ２９を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態２におけるブロック暗号装置１Ａとブロック暗号方法とを実現することができる。この場合、コンピュータのプロセッサは、平文分割部２、鍵分割部３、暗号化部４、鍵スケジュール処理部５および演算部６として機能し、処理を行なう。

また、本実施の形態２におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータ
が、それぞれ、平文分割部２、鍵分割部３、暗号化部４、鍵スケジュール処理部５および演算部６のいずれかとして機能しても良い。

（変形例）
ここで、本実施の形態２における変形例について説明する。本変形例では、行列演算部５３は、係数に０を持たないｄ×ｄの行列を用いて、Ｓ層部５２での非線形変換に対して行列変換する。行列演算部５３における行列変換では、入力されるデータサブブロックの１つに、排他的論理和差分の影響があると、出力されるデータサブブロックすべてに必ず差分がでる。行列演算部４３における行列変換は、上記の式と同様に表される。

［変形例による効果］

図１４および図１５は、本変形例による暗号化では、Ｂｉｃｌｉｑｕｅ特性が成り立たないことを示す図である。図１４（１）において、鍵サブブロックに差分を入れる（図１４（Ａ））。実施の形態２では、係数に０を持たないｄ×ｄの行列で行列変換を行うため、順方向に２ラウンド目の暗号化処理を行うと、図１４（Ｂ）に示すように、データサブブロックのすべてのブロックに、差分が伝搬する。

これにより、図１４（Ｃ）に示すように、鍵サブブロックに差分を入れ、逆方向に暗号化処理を２ラウンド行った場合に、データブロックのすべてに差分がなくても（図１４（Ｄ））、図１５（Ａ）に示すように、データサブブロックには差分が重なるブロック（図１５での黒ブロック）が存在する。つまり、上記のブロック暗号装置１Ａでは、１ラウンドの処理で、Ｂｉｑｌｉｑｕｅ特性が成り立たない、ブロック暗号が行われることが分かる。

なお、暗号化部４の行列演算部４３と、鍵スケジュール処理部５の行列演算部５３とで用いられるｄ×ｄの行列は、第１処理および第２処理を順方向に行ったときの、ｎビットのデータサブブロックおよびｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて第１処理および第２処理を逆方向に行ったときのｎビットのデータサブブロックおよびｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在するように、適宜設定すればよい。

（物理構成）
ここで、実施の形態１、２におけるプログラムを実行することによって、ブロック暗号装置を実現するコンピュータについて図１６を用いて説明する。図１６は、本発明の実施の形態１、２におけるブロック暗号装置を実現するコンピュータの一例を示すブロック図である。

図１６に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていても良い。

ＣＰＵ１１１は、記憶装置１１３に格納された、実施の形態１、２におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、実施の形態１、２におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお
、実施の形態１、２におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。

また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。

データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。

また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））およびＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ－ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体が挙げられる。

なお、実施の形態１、２におけるブロック暗号装置は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、ブロック暗号装置は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。

上述した実施の形態１、２の一部又は全部は、以下に記載する（付記１）～（付記８）によって表現することができるが、以下の記載に限定されるものではない。

（付記１）
ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号装置であって、
前記平文をｄ個のｎビットのデータサブブロックに分割する平文分割部と、
前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割する鍵分割部と、
前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返す暗号化部と、
前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返す鍵スケジュール処理部と、
前記暗号化部の出力と、前記鍵スケジュール処理部の出力とを演算して、暗号文を出力する演算部と、
を備え、
前記鍵スケジュール処理部において、
１ラウンド目の第２処理では、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記暗号化部において、
１ラウンドの第１処理では、前記平文分割部により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の
出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、
ことを特徴とするブロック暗号装置。

（付記２）
ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号装置であって、
前記平文をｄ個のｎビットのデータサブブロックに分割する平文分割部と、
前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割する鍵分割部と、
前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返す暗号化部と、
前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返す鍵スケジュール処理部と、
前記暗号化部の出力と、前記鍵スケジュール処理部の出力とを演算して、暗号文を出力する演算部と、
を備え、
前記鍵スケジュール処理部において、
１ラウンド目の第２処理では、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
前記暗号化部において、
１ラウンド目の第１処理では、前記平文分割部により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンドの前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、
ことを特徴とするブロック暗号装置。

（付記３）
付記２に記載のブロック暗号装置であって、
前記第２処理のラウンド関数は、入力されるｄ個のｎビットの鍵サブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、
ことを特徴とするブロック暗号装置。

（付記４）
付記１から付記３のいずれか一つに記載のブロック暗号装置であって、
前記暗号化部の第１処理で行う演算は、算術加算、算術減算または排他的論理和のいず
れかであり、
前記演算部で行う演算は、算術加算、算術減算または排他的論理和のいずれかである、
ことを特徴とするブロック暗号装置。

（付記５）
ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号方法であって、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を備え、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、
ことを特徴とするブロック暗号方法。

（付記６）
ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号方法であって、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を備え、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンドの前記第２処理の出力を、ラウンド関数の入力とし、
前記ステップ（ｃ）において、
１ラウンドの第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、
ことを特徴とするブロック暗号方法。

（付記７）
コンピュータに、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化させるプログラムであって、
前記コンピュータに、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、全単射関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を実行させ、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックを前記全単射関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、前記全単射関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記ラウンド関数は、入力されるｄ個のｎビットのデータサブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、
ことを特徴とするプログラム。

（付記８）
コンピュータに、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化させるプログラムであって、
前記コンピュータに、
（ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
（ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
（ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた第１処理をrラウンド繰り返すステップと、
（ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
（ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
を実行させ、
前記ステップ（ｄ）において、
１ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
前記ステップ（ｃ）において、
１ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックとを比較すると、丸め差分の重なりが必ず存在する、
ことを特徴とするプログラム。

以上のように、本発明によれば、Biclique Cryptanalysisに対して安全なブロック暗号を構成することができる。

１、１Ａ ブロック暗号装置
２ 平文分割部
３ 鍵分割部
４ 暗号化部
５ 鍵スケジュール処理部
６ 演算部
４１ 論理演算部
４２ Ｓ層部
４３ 行列演算部
５１ 全単射計算部
５２ Ｓ層部
５３ 行列演算部

Claims (4)

1. ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号装置であって、
   前記平文をｄ個のｎビットのデータサブブロックに分割する平文分割部と、
   前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割する鍵分割部と、
   前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた、算術加算、算術減算、排他的論理和のいずれかを、第１処理として、rラウンド繰り返す暗号化部と、
   前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返す鍵スケジュール処理部と、
   前記暗号化部の出力と、前記鍵スケジュール処理部の出力とを演算して、暗号文を出力する演算部と、
   を備え、
   前記鍵スケジュール処理部において、
   １ラウンド目の第２処理では、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
   前記暗号化部において、
   １ラウンド目の第１処理では、前記平文分割部により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記鍵分割部により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンドの前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
   更に、前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、
   前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、を比較すると、丸め差分の重なりが必ず存在するように設定されている、
   ことを特徴とするブロック暗号装置。
2. 請求項１に記載のブロック暗号装置であって、
   前記第２処理のラウンド関数は、入力されるｄ個のｎビットの鍵サブブロックにおける１の丸め差分の影響を、他の全データサブブロックに波及させるｄ×ｄの行列演算式である、
   ことを特徴とするブロック暗号装置。
3. コンピュータが、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化するブロック暗号方法であって、
   （ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
   （ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
   （ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた、算術加算、算術減算、排他的論理和のいずれかを、第１処理として、rラウンド繰り返すステップと、
   （ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
   （ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
   を備え、
   前記ステップ（ｄ）において、
   １ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンドの前記第２処理の出力を、ラウンド関数の入力とし、
   前記ステップ（ｃ）において、
   １ラウンドの第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
   更に、前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、
   前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、を比較すると、丸め差分の重なりが必ず存在するように設定されている、
   ことを特徴とするブロック暗号方法。
4. コンピュータに、ブロック長がｂビットの平文を、鍵長がｂビットの秘密鍵を用いて暗号化させるプログラムであって、
   前記コンピュータに、
   （ａ）前記平文をｄ個のｎビットのデータサブブロックに分割するステップと、
   （ｂ）前記秘密鍵をｄ個のｎビットの鍵サブブロックに分割するステップと、
   （ｃ）前記ｄ個のｎビットのデータサブブロックに対し、ラウンド関数を用いた、算術加算、算術減算、排他的論理和のいずれかを、第１処理として、rラウンド繰り返すステップと、
   （ｄ）前記ｄ個のｎビットの鍵サブブロックに対し、ラウンド関数を用いた第２処理をｒラウンド繰り返すステップと、
   （ｅ）前記ステップ（ｃ）の出力と、前記ステップ（ｄ）の出力とを演算して、暗号文を出力するステップと、
   を実行させ、
   前記ステップ（ｄ）において、
   １ラウンド目の第２処理では、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックをラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第２処理では、（ｉ－１）ラウンド目の前記第２処理の出力を、ラウンド関数の入力とし、
   前記ステップ（ｃ）において、
   １ラウンド目の第１処理では、前記ステップ（ａ）により生成された前記ｄ個のｎビットのデータサブブロックそれぞれと、前記ステップ（ｂ）により生成された前記ｄ個のｎビットの鍵サブブロックそれぞれとを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   ｉ（ｉ＝２～ｒ）ラウンド目の第１処理では、（ｉ－１）ラウンド目の前記第１処理の出力と、（ｉ－１）ラウンド目の前記第２処理の出力とを演算し、演算結果に対して非線形変換処理を行った結果を、ラウンド関数の入力とし、
   前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、ｄ×ｄの行列演算式であり、
   更に、前記第１処理のラウンド関数、および、前記第２処理のラウンド関数それぞれは、
   前記第１処理および前記第２処理を順方向に行ったときの、前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、差分をｎ個の鍵サブブロックの空き領域に入れて前記第１処理および前記第２処理を逆方向に行ったときの前記ｎビットのデータサブブロックおよび前記ｎビットの鍵サブブロックと、を比較すると、丸め差分の重なりが必ず存在するように設定されている、
   ことを特徴とするプログラム。
   

Images