(57)【特許請求の範囲】
【請求項１】
暗号化装置の第１ビット分割部が、平文mを２つ以上のビット列にビット分割するビット分割過程と、
暗号化装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
暗号化装置の共通鍵暗号化部が、共通鍵wを用い、共通鍵暗号方式によって、上記平文mから分割された１つのビット列を暗号化し、第１暗号文cを生成する共通鍵暗号化過程と、
暗号化装置のパディング部が、上記平文mから分割された残りのビット列と乱数rとを、１つ以上のハッシュ関数を含むパディング関数に入力し、ビット結合値yを生成するパディング過程と、
暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させ、第２暗号文u=f(y)を生成する一方向性置換関数演算過程と、
暗号化装置の送信部が、第１暗号文cと第２暗号文uとを復号装置に送信する暗号文送信過程と、
第１暗号文cと第２暗号文uとを復号装置の記憶部に格納する暗号文格納過程と、
復号装置の逆関数演算部が、第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算過程と、
復号装置の逆パディング部が、ビット結合値yを、１つ以上のハッシュ関数を含むパディング逆関数に入力し、上記平文mから分割された１つ以上のビット列と、乱数rとを抽出する逆パディング過程と、
復号装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
復号装置の共通鍵復号部が、共通鍵wを用いて第１暗号文cを復号し、上記平文mから分割された１つのビット列を抽出する共通鍵復号過程と、
復号装置の第３ビット結合部が、上記撹乱復元過程で抽出された上記１つ以上のビット列と、上記共通鍵復号過程で抽出された上記１つのビット列とのビット結合値を生成し、当該ビット結合値を復号結果として出力するビット結合過程と、を有し、
上記パディング関数及び上記パディング逆関数がそれぞれ具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される、
ことを特徴とする暗号通信方法。
【請求項２】
(A)  暗号化装置の記憶部にpビット（p＞n≧2）の平文mを格納する平文格納過程と、
(B)  上記暗号化装置の記憶部にzビット（n>z≧k，kはセキュリティパラメータ）の乱数rを格納する乱数格納過程と、
(C)  暗号化装置の第１ビット分割部が、平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2と、p‐n+zビットの第３平文meとにビット分割し、当該第２平文m2をビット列s(0)とする第１ビット分割過程と、
(D)  暗号化装置の第１ビット結合部が、乱数rと第１平文m1とのビット結合値を生成し、当該ビット結合値をビット列t(0)とする第１ビット結合過程と、
(E)  暗号化装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
(F)  暗号化装置の共通鍵暗号化部が、共通鍵wを用い、共通鍵暗号方式によって第３平文meを暗号化した第１暗号文cを生成する共通鍵暗号化過程と、
(G)  ラウンド数R（Rは4以上の整数）が偶数である場合には、i=0からi=(R/2)‐1まで順番（iは整数）に、
暗号化装置の第１ハッシュ関数演算部が、ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出する第１ハッシュ関数演算過程と、
暗号化装置の第１排他的論理和演算部が、ビット列s(i)とハッシュ値h(2・i+1)との排他的論理和演算を行い、その演算結果をビット列s(i+1)とする第１排他的論理和演算過程と、
暗号化装置の第２ハッシュ関数演算部が、ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出する第２ハッシュ関数演算過程と、
暗号化装置の第２排他的論理和演算部が、ビット列t(i)とハッシュ値h(2・i+2)との排他的論理和演算を行い、その演算結果をビット列t(i+1)とする第２排他的論理和演算過程と、を実行し、
ラウンド数Rが奇数である場合には、i=0からi={(R‐1)/2}‐1まで順番に、上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程と上記第２ハッシュ関数演算過程と上記第２排他的論理和演算過程とを実行し、さらに、i=(R‐1)/2について上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程とを実行する、撹乱過程と、
(H)  ラウンド数Rが偶数である場合には、暗号化装置の第２ビット結合部が、ビット列t(R/2)とビット列s(R/2)とを含むビット結合値yを生成し、
ラウンド数Rが奇数である場合には、暗号化装置の第２ビット結合部が、上記暗号化装置の記憶部からビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値yを生成する、第２ビット結合過程と、
(I)  暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた第２暗号文u=f(y)を算出する一方向性置換関数演算過程と、
(J)  暗号化装置の送信部が、第１暗号文cと第２暗号文uとを復号装置に送信する暗号文送信過程と、
(K)  第１暗号文cと第２暗号文uとを復号装置の記憶部に格納する暗号文格納過程と、
(L)  復号装置の逆関数演算部が、第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算過程と、
(M)  復号装置の第２ビット分割部が、ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出する第２ビット分割過程と、
(N)  ラウンド数Rが偶数である場合には、i=(R/2)‐1からi=0まで順番に、
復号装置の第３ハッシュ関数演算部が、ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出する第３ハッシュ関数演算過程と、
復号装置の第３排他的論理和演算部が、ビット列t(i+1)とハッシュ値h(2・i+2)との排他的論理和演算を行い、その演算結果をビット列t(i)とする第３排他的論理和演算過程と、
復号装置の第４ハッシュ関数演算部が、ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出する第４ハッシュ関数演算過程と、
復号装置の第４排他的論理和演算部が、ビット列s(i+1)とハッシュ値h(2・i+1)との排他的論理和演算を行い、その演算結果をビット列s(i)とする第４排他的論理和演算過程と、を実行し、
ラウンド数Rが奇数である場合には、i=(R‐1)/2について、上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行し、さらに、i={(R‐1)/2}‐1からi=0まで順番に、上記第３ハッシュ関数演算過程と上記第３排他的論理和演算過程と上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行する、撹乱復元過程と、
(O)  復号装置の第３ビット分割部が、ビット列t(0)をビット分割し、zビットの乱数rと、v‐zビットの第１平文m1とを抽出する第３ビット分割過程と、
(P)  復号装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
(Q)  復号装置の共通鍵復号部が、共通鍵wを用い、第１暗号文cを復号して第３平文meを抽出する共通鍵復号過程と、
(R)  復号装置の第３ビット結合部が、第１平文m1とビット列s(0)と第３平文meとのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合過程と、を有し、
(S)  上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする暗号通信方法。
【請求項３】
(A)  暗号化装置の記憶部にpビット（p＞n≧2）の平文mを格納する平文格納過程と、
(B)  上記暗号化装置の記憶部にvビット（n＞v≧2k，kはセキュリティパラメータ）の乱数rをビット列t(0)として格納する乱数格納過程と、
(C)  暗号化装置の第１ビット分割部が、平文mを、n‐vビットの第１平文m1と、p‐n+vビットの第２平文meとにビット分割し、当該第１平文m1をビット列s(0)とする第１ビット分割過程と、
(D)  暗号化装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
(E)  暗号化装置の共通鍵暗号化部が、共通鍵wを用い、共通鍵暗号方式によって当該第２平文meを暗号化した第１暗号文cを生成する共通鍵暗号化過程と、
(F)  ラウンド数R（Rは2以上の整数）が偶数である場合には、i=0からi=(R/2)‐1まで順番（iは整数）に、
暗号化装置の第１ハッシュ関数演算部が、ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出する第１ハッシュ関数演算過程と、
暗号化装置の第１排他的論理和演算部が、ビット列s(i)とハッシュ値h(2・i+1)との排他的論理和演算を行い、その演算結果をビット列s(i+1)とする第１排他的論理和演算過程と、
暗号化装置の第２ハッシュ関数演算部が、ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出する第２ハッシュ関数演算過程と、
暗号化装置の第２排他的論理和演算部が、ビット列t(i)とハッシュ値h(2・i+2)との排他的論理和演算を行い、その演算結果をビット列t(i+1)とする第２排他的論理和演算過程と、を実行し、
ラウンド数Rが奇数である場合には、i=0からi={(R‐1)/2}‐1まで順番に、上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程と上記第２ハッシュ関数演算過程と上記第２排他的論理和演算過程とを実行し、さらに、i=(R‐1)/2について上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程とを実行する、撹乱過程と、
(G)  ラウンド数Rが偶数である場合には、暗号化装置の第２ビット結合部が、ビット列t(R/2)とビット列s(R/2)とを含むビット結合値yを生成し、
ラウンド数Rが奇数である場合には、暗号化装置の第２ビット結合部が、ビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値yを生成する、第２ビット結合過程と、
(H)  暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた第２暗号文u=f(y)を算出する一方向性置換関数演算過程と、
(I)  暗号化装置の送信部が、第１暗号文cと第２暗号文uとを復号装置に送信する暗号文送信過程と、
(J)  第１暗号文cと第２暗号文uとを復号装置の記憶部に格納する暗号文格納過程と、
(K)  復号装置の逆関数演算部が、第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算過程と、
(L)  復号装置の第２ビット分割部が、ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出する第２ビット分割過程と、
(M)  ラウンド数Rが偶数である場合には、i=(R/2)‐1からi=0まで順番に、
復号装置の第３ハッシュ関数演算部が、ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出する第３ハッシュ関数演算過程と、
復号装置の第３排他的論理和演算部が、ビット列t(i+1)とハッシュ値h(2・i+2)との排他的論理和演算を行い、その演算結果をビット列t(i)とする第３排他的論理和演算過程と、
復号装置の第４ハッシュ関数演算部が、ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出する第４ハッシュ関数演算過程と、
復号装置の第４排他的論理和演算部が、ビット列s(i+1)とハッシュ値h(2・i+1)との排他的論理和演算を行い、その演算結果をビット列s(i)とする第４排他的論理和演算過程と、を実行し、
ラウンド数Rが奇数である場合には、i=(R‐1)/2について、上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行し、さらに、i={(R‐1)/2}‐1からi=0まで順番に、上記第３ハッシュ関数演算過程と上記第３排他的論理和演算過程と上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行する、撹乱復元過程と、
(N)  復号装置の共通鍵生成部が、ビット列t(0)を含む情報によって定まる共通鍵wを生成する共通鍵生成過程と、
(O)  復号装置の共通鍵復号部が、共通鍵wを用い、第１暗号文cを復号して第２平文meをする共通鍵復号過程と、
(P)  復号装置の第３ビット結合部が、ビット列s(0)と第２平文meとのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合過程と、を有し、
(Q)  上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする暗号通信方法。
【請求項４】
請求項２又は３に記載の暗号通信方法であって、
ラウンド数Rが偶数である場合には、
上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのi≧1に対応する上記ハッシュ値h(2・i+1)が、上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値であるか、或いは、少なくとも何れかのi≦(R/2)‐2に対応する上記ハッシュ値h(2・i+2) が、上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値であり、
ラウンド数Rが奇数である場合には、
上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのiに対応する上記ハッシュ値h(2・i+2) が、上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値である、
ことを特徴とする暗号通信方法。
【請求項５】
請求項２から４の何れかに記載の暗号通信方法であって、
上記第２ビット結合過程で生成される上記ビット結合値yは、
ラウンド数Rが偶数である場合には、所定値を示す付加情報bとビット列t(R/2)とビット列s(R/2)とを含むビット結合値であり、ラウンド数Rが奇数である場合には、所定値を示す付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値であり、
上記第２ビット分割過程は、
ビット結合値yをビット分割し、ラウンド数Rが偶数である場合には、少なくとも付加情報bとビット列t(R/2)とビット列s(R/2)を抽出し、ラウンド数Rが奇数である場合には、少なくとも付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを抽出する過程であり、
少なくとも上記第３ビット結合過程は、
上記第２ビット分割過程で抽出された付加情報bが上記所定値を示す場合にのみ実行される過程であり、
上記第２ビット分割過程で抽出された付加情報bが上記所定値以外の値を示す場合に、復号装置の偽装復号結果生成が、pビットの乱数を生成し、当該乱数を復号結果として出力する偽装復号結果生成過程をさらに有する、
ことを特徴とする暗号通信方法。
【請求項６】
請求項２から４の何れかに記載の暗号通信方法であって、
上記第２ビット結合過程で生成される上記ビット結合値yは、
ラウンド数Rが偶数である場合には、所定値を示す付加情報bとビット列t(R/2)とビット列s(R/2)とを含むビット結合値であり、ラウンド数Rが奇数である場合には、所定値を示す付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値であり、
上記第２ビット分割過程は、
ビット結合値yをビット分割し、ラウンド数Rが偶数である場合には、少なくとも付加情報bとビット列t(R/2)とビット列s(R/2)を抽出し、ラウンド数Rが奇数である場合には、少なくとも付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを抽出する過程であり、
上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記付加情報bとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記付加情報bとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする暗号通信方法。
【請求項７】
請求項６に記載の暗号通信方法であって、
ラウンド数Rが偶数である場合には、
上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのi≧1に対応する上記ハッシュ値h(2・i+1)が、上記付加情報bとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値であるか、或いは、少なくとも何れかのi≦(R/2)‐2に対応する上記ハッシュ値h(2・i+2) が、上記付加情報bとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値であり、
ラウンド数Rが奇数である場合には、
上記撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのiに対応する上記ハッシュ値h(2・i+2) が、上記付加情報bとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値である、
ことを特徴とする暗号通信方法。
【請求項８】
請求項５から７の何れかに記載の暗号通信方法であって、
上記落とし戸付き一方向性置換関数fは、0以上N未満（Nは自然数）の値を入力とする関数であり、
nは、Ｎのビット長を|N|とし、付加情報bのビット長を|b|とした場合にn=|N|‐|b|を満たし、
上記付加情報bは、0を示すビット又はビット列であり、
上記第２ビット結合過程で生成される上記ビット結合値yは、付加情報bが先頭にビット結合された値である、
ことを特徴とする暗号通信方法。
【請求項９】
平文mと乱数rとを格納する記憶部と、
平文mを２つ以上のビット列にビット分割するビット分割部と、
乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成部と、
共通鍵wを用い、共通鍵暗号方式によって、上記平文mから分割された１つのビット列を暗号化し、第１暗号文cを生成する共通鍵暗号化部と、
上記平文mから分割された残りのビット列と乱数rとを、１つ以上のハッシュ関数を含むパディング関数に入力し、ビット結合値yを生成するパディング部と、
ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させ、第２暗号文u=f(y)を生成する一方向性置換関数演算部と、
第１暗号文cと第２暗号文uとを復号装置に送信する送信部と、を有し、
上記パディング関数が具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される、
ことを特徴とする暗号化装置。
【請求項１０】
請求項９に記載の暗号化装置から送信された第１暗号文cと第２暗号文uとを格納する格納部と、
第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算部と、
ビット結合値yを、１つ以上のハッシュ関数を含むパディング逆関数に入力し、上記平文mから分割された１つ以上のビット列と、乱数rとを抽出する撹乱復元部と、
乱数rを含む情報によって定まる共通鍵wを生成する共通鍵生成部と、
共通鍵wを用いて第１暗号文cを復号し、上記平文mから分割された１つのビット列を抽出する共通鍵復号部と、
上記撹乱復元部で抽出された上記１つ以上のビット列と、上記共通鍵復号部で抽出された上記１つのビット列とのビット結合値を生成し、当該ビット結合値を復号結果として出力するビット結合部と、を有し、
上記パディング逆関数が具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される、
ことを特徴とする復号装置。
【請求項１１】
pビット（p＞n≧2）の平文mと、zビット（z≧k，kはセキュリティパラメータ）の乱数rとを格納する記憶部と、
上記記憶部から平文mを読み込み、当該平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2と、p‐n+zビットの第３平文meとにビット分割し、当該第１平文m1と、第２平文m2であるビット列s(0)と、第３平文meとを上記記憶部に格納する第１ビット分割部と、
上記記憶部から乱数rと第１平文m1とを読み込み、これらのビット結合値を生成し、当該ビット結合値をビット列t(0)として上記記憶部に格納する第１ビット結合部と、
上記記憶部から乱数rを含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを上記記憶部に格納する共通鍵生成部と、
上記記憶部から第３平文meと共通鍵wとを読み込み、当該共通鍵wを用い、共通鍵暗号方式によって当該第３平文meを暗号化した第１暗号文cを生成し、当該第１暗号文cを上記記憶部に格納する共通鍵暗号化部と、
上記記憶部からビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を上記記憶部に格納する第１ハッシュ関数演算部と、
上記記憶部からビット列s(i)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列s(i+1)として上記記憶部に格納する第１排他的論理和演算部と、
上記記憶部からビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出し、当該ハッシュ値h(2・i+2)を上記記憶部に格納する第２ハッシュ関数演算部と、
上記記憶部からビット列t(i)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列t(i+1)として上記記憶部に格納する第２排他的論理和演算部と、
ラウンド数R（Rは4以上の整数）が偶数である場合には、i=0からi=(R/2)‐1まで順番（iは整数）に、上記第１ハッシュ関数演算部と上記第１排他的論理和演算部と上記第２ハッシュ関数演算部と上記第２排他的論理和演算部の処理を実行させ、ラウンド数Rが奇数である場合には、i=0からi={(R‐1)/2}‐1まで順番に、上記第１ハッシュ関数演算部と上記第１排他的論理和演算部と上記第２ハッシュ関数演算部と上記第２排他的論理和演算部の処理を実行させ、さらに、i=(R‐1)/2について上記第１ハッシュ関数演算部と上記第１排他的論理和演算部とを実行させる制御部と、
ラウンド数Rが偶数である場合には、上記記憶部からビット列t(R/2)とビット列s(R/2)とを読み込み、それらを含むビット結合値yを生成し、当該ビット結合値yを上記記憶部に格納し、ラウンド数Rが奇数である場合には、上記記憶部からビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを読み込み、それらを含むビット結合値yを生成し、当該ビット結合値yを上記記憶部に格納する、第２ビット結合部と、
上記記憶部からビット結合値yを読み込み、当該ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた第２暗号文u=f(y)を算出し、当該第２暗号文uを上記記憶部に格納する一方向性置換関数演算部と、
上記記憶部から読み込まれた第１暗号文cと第２暗号文uとを復号装置に送信する送信部と、を有し、
少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする暗号化装置。
【請求項１２】
請求項１１に記載の暗号化装置から送信された第１暗号文cと第２暗号文uとを格納する記憶部と、
上記記憶部から第２暗号文uを読み込み、当該第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出し、当該ビット結合値yを上記記憶部に格納する逆関数演算部と、
上記記憶部からビット結合値yを読み込み、当該ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出し、それらを上記記憶部に格納する第２ビット分割部と、
上記記憶部からビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出し、当該ハッシュ値h(2・i+2)を上記記憶部に格納する第３ハッシュ関数演算部と、
上記記憶部からビット列t(i+1)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列t(i)として上記記憶部に格納する第３排他的論理和演算部と、
上記記憶部からビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を上記記憶部に格納する第４ハッシュ関数演算部と、
上記記憶部からビット列s(i+1)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列s(i)として上記記憶部に格納する第４排他的論理和演算部と、
ラウンド数R（Rは4以上の整数）が偶数である場合には、i=(R/2)‐1からi=0まで順番に、上記第３ハッシュ関数演算部と上記第３排他的論理和演算部と上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を実行させ、ラウンド数Rが奇数である場合には、i=(R‐1)/2について、上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を実行させ、さらに、i={(R‐1)/2}‐1からi=0まで順番に、上記第３ハッシュ関数演算部と上記第３排他的論理和演算部と上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を実行させる制御部と、
上記記憶部からビット列t(0)を読み込み、当該ビット列t(0)をビット分割し、zビットの乱数rと、v‐zビットの第１平文m1とを抽出し、当該乱数rと第１平文m1とを上記記憶部に格納する第３ビット分割部と、
上記記憶部から乱数rを含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを上記記憶部に格納する共通鍵生成部と、
上記記憶部から第１暗号文cと共通鍵wとを読み込み、当該共通鍵wを用い、当該第１暗号文cを復号して第３平文meを抽出し、当該第３平文meを上記記憶部に格納する共通鍵復号部と、
上記記憶部から、第１平文m1とビット列s(0)と第３平文meとを読み込み、これらのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合部と、を有し、
少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする復号装置。
【請求項１３】
pビット（p＞n≧2）の平文mと、vビット（n＞v≧2k，kはセキュリティパラメータ）の乱数rであるビット列t(0)とを格納する記憶部と、
上記記憶部から平文mを読み込み、当該平文mを、n‐vビットの第１平文m1と、p‐n+vビットの第２平文meとにビット分割し、当該第１平文m1であるビット列s(0)と、第２平文meとを上記記憶部に格納する第１ビット分割部と、
上記記憶部から乱数rを含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを上記記憶部に格納する共通鍵生成部と、
上記記憶部から第２平文meと共通鍵wとを読み込み、当該共通鍵wを用い、共通鍵暗号方式によって当該第２平文meを暗号化した第１暗号文cを生成し、当該第１暗号文cを上記記憶部に格納する共通鍵暗号化部と、
上記記憶部からビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を上記記憶部に格納する第１ハッシュ関数演算部と、
上記記憶部からビット列s(i)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列s(i+1)として上記記憶部に格納する第１排他的論理和演算部と、
上記記憶部からビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出し、当該ハッシュ値h(2・i+2)を上記記憶部に格納する第２ハッシュ関数演算部と、
上記記憶部からビット列t(i)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列t(i+1)として上記記憶部に格納する第２排他的論理和演算部と、
ラウンド数R（Rは2以上の整数）が偶数である場合には、i=0からi=(R/2)‐1まで順番（iは整数）に、上記第１ハッシュ関数演算部と上記第１排他的論理和演算部と上記第２ハッシュ関数演算部と上記第２排他的論理和演算部の処理を実行させ、ラウンド数Rが奇数である場合には、i=0からi={(R‐1)/2}‐1まで順番に、上記第１ハッシュ関数演算部と上記第１排他的論理和演算部と上記第２ハッシュ関数演算部と上記第２排他的論理和演算部の処理を実行させ、さらに、i=(R‐1)/2について上記第１ハッシュ関数演算部と上記第１排他的論理和演算部の処理を実行させる制御部と、
ラウンド数Rが偶数である場合には、暗号化装置の第２ビット結合部が、上記記憶部からビット列t(R/2)とビット列s(R/2)とを読み込み、それらを含むビット結合値yを生成し、当該ビット結合値yを上記記憶部に格納し、ラウンド数Rが奇数である場合には、暗号化装置の第２ビット結合部が、上記記憶部からビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを読み込み、それらを含むビット結合値yを生成し、当該ビット結合値yを上記記憶部に格納する、第２ビット結合部と、
上記記憶部からビット結合値yを読み込み、当該ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた第２暗号文u=f(y)を算出し、当該第２暗号文uを上記記憶部に格納する一方向性置換関数演算部と、
上記記憶部から読み込まれた第１暗号文cと第２暗号文uとを復号装置に送信する暗号文送信部と、を有し、
少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする暗号化装置。
【請求項１４】
請求項１３に記載の暗号化装置から送信された第１暗号文cと第２暗号文uとを格納する記憶部と、
上記記憶部から第２暗号文uを読み込み、当該第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出し、当該ビット結合値yを上記記憶部に格納する逆関数演算部と、
上記記憶部からビット結合値yを読み込み、当該ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出し、それらを上記記憶部に格納する第２ビット分割部と、
上記記憶部からビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出し、当該ハッシュ値h(2・i+2)を上記記憶部に格納する第３ハッシュ関数演算部と、
上記記憶部からビット列t(i+1)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列t(i)として上記記憶部に格納する第３排他的論理和演算部と、
上記記憶部からビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を上記記憶部に格納する第４ハッシュ関数演算部と、
上記記憶部からビット列s(i+1)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算を行い、その演算結果をビット列s(i)として上記記憶部に格納する第４排他的論理和演算部と、
ラウンド数Rが偶数である場合には、i=(R/2)‐1からi=0まで順番に、上記第３ハッシュ関数演算部と上記第３排他的論理和演算部と上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を事項させ、ラウンド数Rが奇数である場合には、i=(R‐1)/2について、上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を実行させ、さらに、i={(R‐1)/2}‐1からi=0まで順番に、上記第３ハッシュ関数演算部と上記第３排他的論理和演算部と上記第４ハッシュ関数演算部と上記第４排他的論理和演算部の処理を事項させる制御部と、
上記記憶部からビット列t(0)を含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを上記記憶部に格納する共通鍵生成部と、
上記記憶部から第１暗号文cと共通鍵wとを読み込み、当該共通鍵wを用い、当該第１暗号文cを復号して第２平文meを抽出し、当該第２平文meを上記記憶部に格納する共通鍵復号部と、
上記記憶部から、ビット列s(0)と第２平文meとを読み込み、これらのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合部と、を有し、
少なくとも一部のiに対応する、上記ハッシュ値h(2・i+1)及び／又は上記ハッシュ値h(2・i+2)は、
上記第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は上記第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)である、
ことを特徴とする復号装置。
【請求項１５】
請求項９，１１又は１３に記載の暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項１６】
請求項１０，１２又は１４に記載の復号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信技術に関し、特に、公開鍵暗号通信技術に関する。
【背景技術】
【０００２】
OAEP暗号（例えば、非特許文献１参照）に代表される、理想化されたハッシュ関数を用いた場合に適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号の効率について説明する。なお、落とし戸付き一方向性置換関数とは、公開情報を用いた関数演算は容易であるが、秘密情報なしで逆関数の演算を行うことが困難な１対１関数を意味する。
【０００３】
nビットの領域{0, 1}nを定義域とする落とし戸付き一方向性置換関数をfとし、その逆関数をf‐1とする。原始的な公開鍵暗号方式では、平文mをそのままfに入力し、u=f(m)としてuを暗号文とする。しかし、このような方法では、攻撃者が任意の暗号文に対する平文を入手することができる環境化での安全性、即ち、適応的選択暗号文攻撃に対して安全であることを示すことができない。
【０００４】
RSA-OAEP暗号に代表される公開鍵暗号では、パディング関数pdとその逆関数pd-1を用いて、平文mの暗号文をu=f(pd(m, r))とし、暗号文uの復号をm=pd-1(f-1(u))とする。ただし、rは乱数である。
【０００５】
パディング関数の効率を評価する尺度として、処理可能な平文mの長さが用いられることが多い。即ち、mのビット数を|m|で表すとき、|m|がnに近いほど、長い平文mを暗号化することができるため、効率が良いといえる。ここで、kをセキュリティパラメータとする。なお、セキュリティパラメータをk=128と設定することは、攻撃者の計算能力の限界を2128回程度の演算と推定することに相当する。最も代表的なOAEPパディング方法では、乱数rの長さ|r|として2kビットが必要であり、さらに、kビット長の固定文字列が平文mに付け加えられる。これらのビット長の合計がnよりも短く、即ち、n＞|m|+3kでなければならず、処理できる平文mのビット長は|m|＜n-3kとなる。この平文の長さ|m|とnとの差（この例では3kビット）をオーバーヘッドと呼ぶ。オーバーヘッドが小さいほど、暗号化できる平文のビット長が長くなるため、効率の良いパディング方法であるといえる。
【０００６】
理想化されたハッシュ関数を用いた場合に適応的選択暗号に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号方式は各種提案されているが、多くは3kビット或いはそれよりも大きなオーバーヘッドを持つ。唯一、非特許文献２等に示されたOAEP 3-roundパディング方法が2kビットのオーバーヘッドを持つ。
【０００７】
図２９（ａ）は、従来のOAEP 3-roundパディング関数pdの処理を説明するための図であり、図２９（ｂ）は、その逆関数pd-1の処理を説明するための図である。
【０００８】
図２９（ｂ）に示すパディング関数pdは、2kビットの乱数r(=t(0))と、n-2kビットの平文m(=s(0))を入力とし、理想化されたハッシュ関数H1, H2, H3と排他的論理和（αとβとの排他的論理和を「α(+)β」と表現する）とを用いて、h(1)=H1(t(0)), s(1)=s(0)(+)h(1), h(2)=H2(s(1)), t(1)=t(0)(+)h(2), h(3)=H3(t(1)), s(2)=s(1)(+)h(3)と計算し、t(1)とs(2)とのビット結合t(1)|s(2)を出力する。そして、これを落とし戸付き一方向性置換関数fに入力し、u=f(t(1)|s(2))と計算したuを暗号文とする。なお、α|βは、αとβとのビット結合を意味する。
【０００９】
復号時には、まず、暗号文uをf‐1に入力して、a=f‐1(u)とする。次に、aの前半の2ｋビットと、残りのn-2kビットに分割し、それぞれをt(1)，s(2)として図２９（ｂ）に示すパディング関数の逆関数pd-1に入力し、図２９（ａ）と逆の手順で演算を行う。即ち、h(3)=H3(t(1)), s(1)=s(2)(+)h(3), h(2)=H2(s(1)), t(0)=t(1)(+)h(2)，h(1)=H1(t(0))，m=s(0)=s(1)(+)h(1)を計算し、平文mを出力する。
【００１０】
なお、公開鍵暗号が安全となる、即ち識別不可能性を有する為には、kビットの乱数を用いることは不可避であり、その意味で、オーバーヘッドをkビットより小さくすることはできない。即ち、kビットがオーバーヘッドの最小値である。
【００１１】
更に、第二の従来法として、RSA-KEM/DEM方式が知られている（例えば、非特許文献４参照）。ここで、E, Dをそれぞれ共通鍵暗号方式の暗号関数・復号関数とする。この方式を用いて任意の長さの平文mを暗号化する手順は以下の通りである。
【００１２】
1.  nビットの乱数rを生成する。
2.  k=H(r), u=f(r)を計算する。
3.  kをセッション鍵として、c=Ek(m)を計算する。
4.  (u, c)を暗号文として出力する。
【００１３】
復号時には、まずr=f‐1(u)及びk=H(r)を計算し、次にkをセッション鍵としてcをm=Dk(c)のように復号して、平文mを得る。
【００１４】
上記RSA-KEM/DEM方式において、共通鍵暗号がlength-preserving、即ち、入力平文と出力暗号文との長さが等しいという性質を持つものであった場合、暗号文(u, c)の長さはn+|m|ビットになる。即ち、平文mの長さにかかわらず、nビットのオーバーヘッドが生じる。落とし戸付き一方向性置換関数fに標準的なRSA関数を用いた場合、n=1024となり、非常に大きなオーバーヘッドが暗号文に付加されることになる。
【００１５】
また、OAEP方式とRSA-KEM/DEM方式を発展させた方法として、非特許文献５で述べられている方式があるが、その方式においても、暗号文の長さはn+|m|ビットになる。
【非特許文献１】M. Bellare, and P. Rogaway,“Optimal Asymmetric Encryption”,  Advancecs in cryptology - Eurocrypt'94, LNCS 950, pp.92-111, Springer-Verlag, 1995.
【非特許文献２】D. H. Phan and D. Pointcheval,“OAEP 3-Round: A Generic and Secure Asymmetric Encryption Padding”, Advances in Cryptology -Asiacrypt ’04, LNCS 3329, pp.63-78, 2004, Springer-Verlag.
【非特許文献３】J. Jonsson, “An OAEP variant with a tight security proof”, [online], March 18, 2002, IACR e-print Archive 2002/034, インターネット＜http://mirror.cr.yp.to/eprint.iacr.org/2002/034.pdf＞
【非特許文献４】V. Shoup, “ISO 18033-2: An Emerging Standard for Public-Key Encryption (Committee Draft)”, [online], June 3, 2004, インターネット＜http://shoup.net/iso/＞
【非特許文献５】M. Abe and R. Gennaro and K. Kurosawa, “Tag-KEM/DEM: A New Framework for Hybrid Encryption”, LACR c-print 2005/027, 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
以上のように、従来のOAEP 3-roundパディング方法では、n−2kビットよりも長い平文を暗号化することができない。また、従来のRSA-KEM/DEM方式や、OAEP方式とRSA-KEM/DEM方式を発展させた方法では、平文mの長さにかかわらず、nビットのオーバーヘッドが生じる。
【００１７】
このように従来は、短いオーバーヘッドで長い平文を暗号化できる、適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号技術が存在しなかった。
【００１８】
本発明はこのような点に鑑みてなされたものであり、パディングに起因するオーバーヘッドのみで長い平文を暗号化できる、適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明では、暗号化装置が、平文mを２つ以上のビット列にビット分割し、乱数rを含む情報によって定まる共通鍵wを生成し、共通鍵wを用い、共通鍵暗号方式によって、上記平文mから分割された１つのビット列を暗号化し、第１暗号文cを生成する。また、暗号化装置が、上記平文mから分割された残りのビット列と乱数rとを、１つ以上のハッシュ関数を含むパディング関数に入力し、ビット結合値yを生成する。ここで、当該パディング関数が具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される。さらに、暗号化装置が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させ、第２暗号文u=f(y)を生成し、第１暗号文cと第２暗号文uとを復号装置に送信する。
【００２０】
復号装置は、第１暗号文cと第２暗号文uとを復号装置の記憶部に格納し、第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出し、ビット結合値yを、１つ以上のハッシュ関数を含むパディング逆関数に入力し、上記平文mから分割された１つ以上のビット列と、乱数rとを抽出する。ここで、パディング逆関数が具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される。さらに、復号装置は、乱数rを含む情報によって定まる共通鍵wを生成し、共通鍵wを用いて第１暗号文cを復号し、上記平文mから分割された１つのビット列を抽出する。そして、復号装置は、当該１つのビット列と、上述のパディング逆関数によって得られた１つ以上のビット列と、のビット結合値を生成し、当該ビット結合値を復号結果として出力する。
【００２１】
このように本発明では、平文mを２つ以上のビット列にビット分割する。そして、分割された１つのビット列を共通鍵暗号方式で暗号化して第１暗号文cを生成し、さらに、残りのビット列に乱数rをパディングし、それを落とし戸付き一方向性置換関数fによって暗号化して第２暗号文uを生成する。この第１暗号文c及び第２暗号文uのオーバーヘッドは、パディングによるオーバーヘッドのみである。
【００２２】
また、平文mのビット列を分割して２つの暗号文、即ち、第１暗号文c及び第２暗号文uを生成するため、本発明では、落とし戸付き一方向性置換関数fの入力域のビット長からオーバーヘッドを差し引いたビット長よりも長い平文を暗号化できる。
【００２３】
さらに、パディング関数及びパディング逆関数がそれぞれ具備する少なくとも一部のハッシュ関数に第１暗号文cを含む情報が入力されている。そのため、第１暗号文cをc'に改ざんするような選択暗号文攻撃を受けた場合に、第２暗号文uから逆パディング関数を用いて生成される共通鍵wに影響が及び、第１暗号文cが正しく復号されなくなるため、攻撃者は有益な情報を得ることができない。その結果、本発明では、選択暗号攻撃に対する安全性をもつ。
【発明の効果】
【００２４】
以上のように、本発明では、適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号技術において、パディングに起因するオーバーヘッドのみで長い平文を暗号化できる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００２６】
〔基本方式〕
まず、本形態の基本方式を説明する。
本形態では、暗号化装置が暗号文を生成して復号装置に送信し、復号装置がその復号を行う。なお、本形態の暗号化装置及び復号装置は、それぞれ、公知のコンピュータに所定のプログラムが読み込まれることで構築される装置である。
【００２７】
まず、暗号化装置の第１ビット分割部が、平文mを２つ以上のビット列にビット分割する（ビット分割過程）。また、暗号化装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成し（共通鍵生成過程）、暗号化装置の共通鍵暗号化部が、共通鍵wを用い、共通鍵暗号方式によって、上記平文mから分割された１つのビット列を暗号化し、第１暗号文cを生成する（共通鍵暗号化過程）。さらに、暗号化装置のパディング部が、上記平文mから分割された残りのビット列と乱数rとを、１つ以上のハッシュ関数を含むパディング関数に入力し、ビット結合値yを生成する（パディング過程）。なお、当該パディング関数がそれぞれ具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される。その後、暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させ、第２暗号文u=f(y)を生成し（一方向性置換関数演算過程）、暗号化装置の送信部が、第１暗号文cと第２暗号文uとを復号装置に送信する（暗号文送信過程）。
【００２８】
復号装置は、当該第１暗号文cと第２暗号文uとを復号装置の記憶部に格納する（暗号文格納過程）。そして、復号装置の逆関数演算部が、第２暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出し（逆関数演算過程）、復号装置の逆パディング部が、ビット結合値yを、１つ以上のハッシュ関数を含むパディング逆関数に入力し、上記平文mから分割された１つ以上のビット列と、乱数rとを抽出する（逆パディング過程）。なお、当該パディング逆関数がそれぞれ具備する少なくとも一部のハッシュ関数には、それぞれ第１暗号文cを含む情報が入力される。そして、復号装置の共通鍵生成部が、乱数rを含む情報によって定まる共通鍵wを生成し（共通鍵生成過程）、復号装置の共通鍵復号部が、共通鍵wを用いて第１暗号文cを復号し、上記平文mから分割された１つのビット列を抽出する（共通鍵復号過程）。その後、復号装置の第３ビット結合部が、上記撹乱復元過程で抽出された上記１つ以上のビット列と、上記共通鍵復号過程で抽出された上記１つのビット列とのビット結合値を生成し、当該ビット結合値を復号結果として出力する（ビット結合過程）。
【００２９】
以下、この基本方式を実現する各実施形態を説明する。
〔第１実施形態〕
第１実施形態では、平文mを３つのビット列である第１平文m1, 第２平文m2及び第３平文meにビット分割する。そして、第３平文meを共通鍵暗号方式で暗号化して第１暗号文cを生成し、残りの第１平文m1,及び第２平文m2に乱数rをパディングし、それを落とし戸付き一方向性置換関数fによって暗号化して第２暗号文uを生成する。
【００３０】
＜全体構成＞
図１（ａ）は、第１実施形態の暗号通信システム１の構成を例示した図である。
図１（ａ）に例示するように、本形態の暗号通信システム１は、公開鍵暗号方式によって暗号化を行う暗号化装置１０と、それによって生成された暗号文を復号する復号装置２０とを有し、それらはインターネット等の安全ではないネットワーク３０を通じて通信可能に接続されている。なお、暗号化装置１０と復号装置２０との間の通信はネットワーク３０を通じて行われるが、以下ではその旨を省略して説明する。
【００３１】
＜ハードウェア構成＞
図１（ｂ）は、暗号化装置１０のハードウェア構成を例示したブロック図である。
図１（ｂ）に例示するように、この例の暗号化装置１０は、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ（Random Access Memory）１０ｆ、ＲＯＭ（Read Only Memory）１０ｅ及びバス１０ｇを有している。
【００３２】
ＣＰＵ１０ａは、読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、データが入力される入力ポート、キーボード、マウス等であり、出力部１０ｃは、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１０ｄは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ＲＡＭ１０ｆは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等である。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ１０ｆ及びＲＯＭ１０ｅを通信可能に接続している。
【００３３】
なお、復号装置２０のハードウェア構成は、暗号化装置１０のそれと同様であるため説明を省略する。
【００３４】
＜ハードウェアとソフトウェアとの協働＞
第１実施形態の暗号化装置１０及び復号装置２０は、それぞれ、上述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【００３５】
図２は、第１実施形態の暗号化装置１０の機能構成を例示したブロック図である。また、図３は、第１実施形態の復号装置２０の機能構成を例示したブロック図である。なお、図２，３における矢印はデータの流れを示すが、制御部１３ａ，２３ａに出入りするデータの流れに対応する矢印は省略してある。
【００３６】
図２に例示するように、本形態の暗号化装置１０は、記憶部１１と、送信部１２と、制御部１３ａと、乱数生成部１３ｂと、第１ビット分割部１３ｃと、第１ビット結合部１３ｄと、共通鍵生成部１３ｋと、共通鍵暗号化部１３ｍと、第１ハッシュ関数演算部１３ｅと、第１排他的論理和演算部１３ｆと、第２ハッシュ関数演算部１３ｇと、第２排他的論理和演算部１３ｈと、第２ビット結合部１３ｉと、一方向性置換関数演算部１３ｊとを有する。
【００３７】
なお、第１ビット結合部１３ｄと、共通鍵生成部１３ｋと、共通鍵暗号化部１３ｍと、第１ハッシュ関数演算部１３ｅと、第１排他的論理和演算部１３ｆと、第２ハッシュ関数演算部１３ｇと、第２排他的論理和演算部１３ｈと、第２ビット結合部１３ｉとは、「パディング部」を構成する。また、記憶部１１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部１２は、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部１３ａ、乱数生成部１３ｂ、共通鍵生成部１３ｋ、共通鍵暗号化部１３ｍ、第１ビット分割部１３ｃ、第１ビット結合部１３ｄ、第１ハッシュ関数演算部１３ｅ、第１排他的論理和演算部１３ｆ、第２ハッシュ関数演算部１３ｇ、第２排他的論理和演算部１３ｈ、第２ビット結合部１３ｉ及び一方向性置換関数演算部１３ｊは、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。なお、当該プログラムには、第１暗号文cをハッシュ関数の入力値に含めるラウンドを示す情報Rcが書き込まれている。また、暗号化装置１０は、制御部１３ａの制御の下、各処理を実行する。
【００３８】
図３に例示するように、本形態の復号装置２０は、記憶部２１と、受信部２２と、制御部２３ａと、逆関数演算部２３ｂと、第２ビット分割部２３ｃと、第３ハッシュ関数演算部２３ｄと、第３排他的論理和演算部２３ｅと、第４ハッシュ関数演算部２３ｆと、第４排他的論理和演算部２３ｇと、第３ビット分割部２３ｈと、共通鍵生成部２３ｊと、共通鍵復号部２３ｋと、第３ビット結合部２３ｉとを有する。
【００３９】
なお、第２ビット分割部２３ｃと、第３ハッシュ関数演算部２３ｄと、第３排他的論理和演算部２３ｅと、第４ハッシュ関数演算部２３ｆと、第４排他的論理和演算部２３ｇと、第３ビット分割部２３ｈとは、「逆パディング部」を構成する。また、記憶部２１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、受信部２２は、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部２３ａ、逆関数演算部２３ｂ、第２ビット分割部２３ｃ、第３ハッシュ関数演算部２３ｄ、第３排他的論理和演算部２３ｅ、第４ハッシュ関数演算部２３ｆ、第４排他的論理和演算部２３ｇ、第３ビット分割部２３ｈ、共通鍵生成部２３ｊ、共通鍵復号部２３ｋ及び第３ビット結合部２３ｉは、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。なお、当該プログラムには、第１暗号文cをハッシュ関数の入力値に含めるラウンドを示す情報Rcが書き込まれている。また、復号装置２０は、制御部２３ａの制御の下、各処理を実行する。
【００４０】
＜処理＞
次に、本形態の処理について説明する。なお、以下では、撹乱過程のラウンド数が偶数の場合の処理、及び、奇数の場合の処理をそれぞれ別個に説明する。しかし、撹乱過程のラウンド数が偶数であるか奇数であるかに応じ、以下の各処理が選択的に実行される構成であってもよい。
【００４１】
［ラウンド数R（R≧4）が偶数である場合］
《暗号化処理》
図４は、ラウンド数R（R≧4）が偶数である場合における暗号化処理を説明するためのフローチャートである。以下、この図に従って説明を行う。
【００４２】
まず、暗号化装置１０（図２）の記憶部１１にpビット（p＞n≧2）の平文mを格納する（平文格納過程／ステップＳ１）。なお、本形態のnは、暗号化装置１０が使用する一方向性置換関数fの入力域のビット数を意味する。また、キュリティパラメータkの値には特に制限はなく、求められる安全性のレベルに応じて設定すればよい。一般的にはk＞80とすることが望ましい。
【００４３】
次に、暗号化装置１０の乱数生成部１３ｂが、zビット（n＞z≧k，kはセキュリティパラメータ）の乱数rを生成し、それを記憶部１１に格納する（乱数格納過程／ステップＳ２）。
【００４４】
次に、暗号化装置１０の第１ビット分割部１３ｃが、記憶部１１から平文mを読み込み、当該平文mを、v‐zビット（n＞v‐z≧2k）の第１平文m1と、n‐vビットの第２平文m2と、p‐n+zビットの第３平文meとにビット分割し、当該第１平文m1と、第２平文m2であるビット列s(0)と、第３平文meとを記憶部１１に格納する（第１ビット分割過程／ステップＳ３）。なお、n＞z≧kを満たすのであれば、zはどのような値であってもよく、また、n＞v‐z≧2kを満たすのであれば、vはどのような値でもよい。しかし、z=k，v=3kとした場合、安全性を確保しつつオーバーヘッドを最小化できるため、z=k，v=3kとすることが望ましい。
【００４５】
また、平文mを第１平文m1と第２平文m2と第３平文meとににビット分割する際の分割方法にも制限はなく、例えば、平文mの上位v‐zビットを第１平文m1とし、次のn‐vビットの第２平文m2とし、残りのp‐n+zビットを第３平文meとしてもよいし、平文mの上位p‐n+zビットを第３平文meとし、次のn‐vビットの第２平文m2とし、残りの上位v‐zビットを第１平文m1としとしてもよい。
【００４６】
次に、暗号化装置１０の第１ビット結合部１３ｄが、記憶部１１から乱数rと第１平文m1とを読み込み、これらのビット結合値r|m1を生成し、当該ビット結合値r|m1をビット列
t(0)=r|m1
として記憶部１１に格納する（第１ビット結合過程／ステップＳ４）。
【００４７】
なお、乱数rと第１平文m1とのビット結合方法にも制限はなく、例えば、乱数rを上位zビットとし、第１平文m1を残りのビットとして結合してもよいし、第１平文m1を上位v‐zビットとし、乱数rを残りのビットとして結合してもよい。
【００４８】
次に、暗号化装置１０の共通鍵生成部１３ｋが、記憶部１１からビット列t(0)=r|m1（「乱数rを含む情報」に相当）を読み込み、当該ビット列t(0)によって定まる共通鍵wを生成し、当該共通鍵wを記憶部１１に格納する（共通鍵生成過程／ステップＳ５）。
【００４９】
本形態では、ビット列t(0)をハッシュ関数Gに作用させたハッシュ値
w=G(t(0)
を共通鍵wとする。なお、本形態のハッシュ関数Gは、
G：{0,1}v→{0,1}w’
の入出力域を持つ。なお、w’は共通鍵wの鍵長を示す。また、ハッシュ関数としては、例えば、SHA-1等を用いることができる（以下同様）。
【００５０】
次に、暗号化装置１０の共通鍵暗号化部１３ｍが、記憶部１１から第３平文meと共通鍵wとを読み込み、当該共通鍵wを用い、共通鍵暗号方式によって当該第３平文meを暗号化した第１暗号文
c=Ew(me)
を生成し、当該第１暗号文cを記憶部１１に格納する（共通鍵暗号化過程／ステップＳ６）。なお、Eは共通鍵暗号方式（例えばCamellia等）の暗号化関数を意味する。
【００５１】
次に、制御部１３ａがi=0と設定し、当該iをレジスタ（図示せず）に保持する（ステップＳ７）。
【００５２】
次に、暗号化装置１０の第１ハッシュ関数演算部１３ｅが、記憶部１１から少なくともビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を記憶部１１に格納する（第１ハッシュ関数演算過程／ステップＳ８）。
【００５３】
具体的には、2・i+1=Rc（第１暗号文cをハッシュ関数の入力値に含めるラウンド）であれば、第１ハッシュ関数演算部１３ｅは、記憶部１１からビット列t(i)と第１暗号文cとを読み込み、当該ビット列t(i)と第１暗号文cとのビット結合値t(i)|cにハッシュ関数
H(2・i+1)：{0,1}v+|c|→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1) (t(i)|c)
を算出し、当該ハッシュ値h(2・i+1)を記憶部１１に格納する。なお、|c|は、第１暗号文cのビット長である。
【００５４】
一方、2・i+1≠Rcであれば、第１ハッシュ関数演算部１３ｅは、記憶部１１からビット列t(i)を読み込み、当該ビット列t(i)にハッシュ関数
H(2・i+1)：{0,1}v→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1)(t(i))
を算出し、当該ハッシュ値h(2・i+1)を記憶部１１に格納する。
【００５５】
次に、暗号化装置１０の第１排他的論理和演算部１３ｆが、記憶部１１からビット列s(i)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算
s(i+1)=s(i)(+) h(2・i+1)
を行い、その演算結果であるビット列s(i+1)を記憶部１１に格納する（第１排他的論理和演算過程／ステップＳ９）。
【００５６】
次に、暗号化装置１０の第２ハッシュ関数演算部１３ｇが、記憶部１１から少なくともビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値
h(2・i+2)=H(2・i+2)(s(i+1))
を算出し、当該ハッシュ値h(2・i+2)を記憶部１１に格納する（第２ハッシュ関数演算過程／ステップＳ１０）。
【００５７】
具体的には、2・i+2=Rcであれば、第２ハッシュ関数演算部１３ｇは、記憶部１１からビット列s(i+1)と第１暗号文cとを読み込み、当該ビット列s(i+1)と第１暗号文cとのビット結合値s(i+1)|cにハッシュ関数
H(2・i+2)：{0,1}n−v+|c|→{0,1}v
を作用させてvビットのハッシュ値
h(2・i+2)=H(2・i+2)(s(i+1)|c)
を算出し、当該ハッシュ値h(2・i+2)を記憶部１１に格納する。
【００５８】
一方、2・i+2=Rcであれば、第２ハッシュ関数演算部１３ｇが、記憶部１１からビット列s(i+1)を読み込み、当該ビット列s(i+1)にハッシュ関数
H(2・i+2)：{0,1}n−v→{0,1}v
を作用させてvビットのハッシュ値
h(2・i+2)=H(2・i+2)(s(i+1))
を算出し、当該ハッシュ値h(2・i+2)を記憶部１１に格納する。
【００５９】
次に、暗号化装置１０の第２排他的論理和演算部１３ｈが、記憶部１１からビット列t(i)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算
t(i+1) =t(i)(+) h(2・i+2)
を行い、その演算結果であるビット列t(i+1)を記憶部１１に格納する（第２排他的論理和演算過程／ステップＳ１１）。
【００６０】
次に、制御部１３ａが、i=(R/2)‐1を満たすか否かを判定する（ステップＳ１２）。ここで、i=(R/2)‐1が満たされなかった場合、制御部１３ａはi+1を新たなiとしてレジスタに格納して（ステップＳ１３）、処理をステップＳ８に戻す。一方、i=(R/2)‐1が満たされた場合、暗号化装置１０の第２ビット結合部１３ｉが、記憶部１１からビット列t(R/2)とビット列s(R/2)とを読み込み、それらを含むビット結合値
y=t(R/2)|s(R/2)
を生成し、当該ビット結合値yを記憶部１１に格納する（第２ビット結合過程／ステップＳ１４）。なお、ステップＳ７〜Ｓ１４の処理が「パディング過程」に相当し、これらの処理によって、入力値ビット列t(0)とs(0)とに施された演算を示す関数が「パディング関数」に相当する。
【００６１】
次に、暗号化装置１０の一方向性置換関数演算部１３ｊが、記憶部１１からビット結合値yを読み込み、当該ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた暗号文
u=f(y)
を算出し、当該暗号文uを暗号化装置の記憶部に格納する（一方向性置換関数演算過程／ステップＳ１５）。なお、落とし戸付き一方向性置換関数fとしては、例えば、因数分解問題の求解困難性に安全性の根拠をおくRSA暗号の暗号化関数や、離散対数問題の求解困難性に安全性の根拠をおくElGamal暗号の暗号化関数等を例示できる（例えば、『岡本龍明，山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X（参考文献１）』等参照）。
【００６２】
その後、暗号化装置１０の送信部１２が、記憶部１１から読み込まれた第１暗号文cと第２暗号文uとを復号装置２０に送信する（暗号文送信過程／ステップＳ１６）。
【００６３】
《復号処理》
図５は、ラウンド数R（R≧4）が偶数である場合における復号処理を説明するためのフローチャートである。以下、この図に従って説明を行う。
【００６４】
上述のように送信された第１暗号文cと第２暗号文uとは、復号装置２０（図３）の受信部２２で受信され、記憶部２１に格納される（暗号文格納過程／ステップＳ２１）。
【００６５】
次に、復号装置２０の逆関数演算部２３ｂが、記憶部２１から暗号文uを読み込み、当該暗号文uに対して落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値
y=f−1(u)
を抽出し、当該ビット結合値yを記憶部２１に格納する（逆関数演算過程／ステップＳ２２）。
【００６６】
次に、復号装置２０の第２ビット分割部２３ｃが、記憶部２１からビット結合値yを読み込み、当該ビット結合値yをビット分割し、ビット列t(R/2)とビット列s(R/2)とを抽出し、
y→ t(R/2), s(R/2)
それらを記憶部２１に格納する（第２ビット分割過程／ステップＳ２３）。
【００６７】
次に、制御部１３ａがi=(R/2)‐1と設定し、当該iをレジスタ（図示せず）に保持する（ステップＳ２４）。
【００６８】
次に、復号装置２０の第３ハッシュ関数演算部２３ｄが、記憶部２１からビット列s(i+1)を読み込み、当該ビット列s(i+1)を含む値にハッシュ関数H(2・i+2)を作用させてvビットのハッシュ値h(2・i+2)を算出し、当該ハッシュ値h(2・i+2)を記憶部２１に格納する（第３ハッシュ関数演算過程／ステップＳ２５）。
【００６９】
具体的には、2・i+2=Rcであれば、第３ハッシュ関数演算部２３ｄは、記憶部２１からビット列s(i+1)と第１暗号文cとを読み込み、読み込み、当該ビット列s(i+1)と第１暗号文cとのビット結合値s(i+1)|cにハッシュ関数に
H(2・i+2)：{0,1}n−v+|c|→{0,1}v
を作用させてvビットのハッシュ値
h(2・i+2)=H(2・i+2)(s(i+1)|c)
を算出し、当該ハッシュ値h(2・i+2)を記憶部２１に格納する。なお、ハッシュ値の入力値とするビット結合値のビット結合方法には制限はないが、暗号化装置１０と復号装置２０とで同一の方法をとる必要がある。
【００７０】
一方、2・i+2≠Rcであれば、第３ハッシュ関数演算部２３ｄは、記憶部２１からビット列s(i+1)を読み込み、読み込み、当該ビット列s(i+1)に
H(2・i+2)：{0,1}n−v→{0,1}v
を作用させてvビットのハッシュ値
h(2・i+2)=H(2・i+2)(s(i+1))
を算出し、当該ハッシュ値h(2・i+2)を記憶部２１に格納する。なお、各ハッシュ関数H(2・i+2)は、暗号化装置１０のものと同一である。
【００７１】
次に、復号装置２０の第３排他的論理和演算部２３ｅが、記憶部２１からビット列t(i+1)とハッシュ値h(2・i+2)とを読み込み、これらの排他的論理和演算
t(i)=t(i+1) (+) h(2・i+2)
を行い、その演算結果であるビット列t(i)を記憶部２１に格納する（第３排他的論理和演算過程／ステップＳ２６）。
【００７２】
次に、復号装置２０の第４ハッシュ関数演算部２３ｆが、記憶部２１から少なくともビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する（第４ハッシュ関数演算過程／ステップＳ２７）。
【００７３】
具体的には、2・i+2=Rcであれば、第４ハッシュ関数演算部２３ｆは、記憶部２１からビット列t(i)と第１暗号文cとを読み込み、当該ビット列t(i)と第１暗号文cとのビット結合値t(i)|cにハッシュ関数
H(2・i+1)：{0,1}v→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1)(t(i)|c)
を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する。
【００７４】
一方、2・i+2≠Rcであれば、第４ハッシュ関数演算部２３ｆは、記憶部２１からビット列t(i)を読み込み、当該ビット列t(i)にハッシュ関数
H(2・i+1)：{0,1}v→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1)(t(i))
を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する。
【００７５】
次に、復号装置２０の第４排他的論理和演算部２３ｇが、記憶部２１からビット列s(i+1)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算
s(i)=s(i+1) (+) h(2・i+1)
を行い、その演算結果であるビット列s(i)を記憶部２１に格納する（第４排他的論理和演算過程／ステップＳ２８）。
【００７６】
次に、制御部２３ａが、i=0を満たすか否かを判定する（ステップＳ２９）。ここで、i=0が満たされなかった場合、制御部２３ａはi‐1を新たなiとしてレジスタに格納して（ステップＳ３０）、処理をステップＳ２５に戻す。一方、i=0が満たされた場合、復号装置２０の第３ビット分割部２３ｈが、記憶部２１からビット列t(0)を読み込み、当該ビット列t(0)をビット分割し、
t(0)→ r, m1
zビットの乱数rとv‐zビットの第１平文m1とを抽出し、当該乱数rと第１平文m1とを記憶部２１に格納する（第３ビット分割過程／ステップＳ３１）。なお、ステップＳ３１のビット分割方法は、暗号化装置１０が行うステップＳ４のビット結合方法に対応するものである。例えば、ステップＳ４において、乱数rを上位zビットとし、第１平文m1を残りのビットとしてビット結合されていたのであれば、ステップＳ３１では、ビット列t(0)の上位zビットを乱数rとして抽出し、残りのビットを第１平文m1として抽出する。
【００７７】
次に、復号装置２０の共通鍵生成部２３ｊが、記憶部２１からビット列t(0)=r|m1（「乱数rを含む情報」に相当）を読み込み、当該ビット列t(0)によって定まる共通鍵wを生成し、当該共通鍵wを記憶部２１に格納する（共通鍵生成過程／ステップＳ３２）。
【００７８】
本形態では、ビット列t(0)をハッシュ関数Gに作用させたハッシュ値
w=G(t(0)
を共通鍵wとする。
【００７９】
次に、復号装置２０の共通鍵復号部２３ｋが、記憶部２１から第１暗号文cと共通鍵wとを読み込み、当該共通鍵wを用い、当該第１暗号文cを復号して第３平文
me=Dw(c)
を抽出し、当該第３平文meを記憶部２１に格納する（共通鍵復号過程／ステップＳ３３）。なお、Dは暗号化装置１０で使用された暗号化関数Eに対応する復号関数を意味する。
【００８０】
次に、復号装置２０の第３ビット結合部２３ｉが、記憶部２１から、第１平文m1とビット列s(0)と第３平文meとを読み込み、これらのビット結合値
m=m1 | s(0) (=m2) | me
を生成し、当該ビット結合値mを復号結果として出力する（第３ビット結合過程／ステップＳ３４）。なお、ここでのビット結合方法は、ステップＳ３でのビット分割方法に対応するものとする。
【００８１】
［ラウンド数Rが奇数である場合］
《暗号化処理》
図６は、ラウンド数R（R≧4）が奇数である場合における暗号化処理を説明するためのフローチャートである。以下、この図に従って説明を行う。なお、ラウンド数Rが偶数である場合の処理と共通する事項については説明を省略する。
【００８２】
まず、暗号化装置１０（図２）が、ラウンド数Rが偶数である場合の処理で説明したステップＳ１〜Ｓ１１の処理を実行する。
【００８３】
次に、暗号化装置１０の制御部１３ａが、i=(R‐1)/2を満たすか否かを判定する（ステップＳ４１）。ここで、i=(R‐1)/2が満たされなかった場合、制御部１３ａはi+1を新たなiとしてレジスタに格納して（ステップＳ４２）、処理をステップＳ８に戻す。一方、i=(R/2)‐1が満たされた場合、暗号化装置１０の第１ハッシュ関数演算部１３ｅが、記憶部１１から少なくともビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を記憶部１１に格納する（第１ハッシュ関数演算過程／ステップＳ４４）。この処理は、ステップＳ８と同じである。
【００８４】
次に、暗号化装置１０の第１排他的論理和演算部１３ｆが、記憶部１１からビット列s(i)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算
s(i+1)=s(i)(+) h(2・i+1)
を行い、その演算結果であるビット列s(i+1)を記憶部１１に格納する（第１排他的論理和演算過程／ステップＳ４５）。
【００８５】
次に、暗号化装置１０の第２ビット結合部１３ｉが、記憶部１１からビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを読み込み、それらを含むビット結合値
y=t((R‐1)/2)|s(((R‐1)/2)+1)
を生成し、当該ビット結合値yを記憶部１１に格納する（ステップＳ４６）。
【００８６】
その後、暗号化装置１０の一方向性置換関数演算部１３ｊが、記憶部１１からビット結合値yを読み込み、当該ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた暗号文
u=f(y)
を算出し、当該暗号文uを暗号化装置の記憶部に格納し（一方向性置換関数演算過程／ステップＳ１５）、暗号化装置１０の送信部１２が、記憶部１１から読み込まれた第１暗号文cと第２暗号文uとを復号装置２０に送信する（暗号文送信過程／ステップＳ１６）。
【００８７】
《復号処理》
図７は、ラウンド数Rが奇数である場合における復号処理を説明するためのフローチャートである。以下、この図に従って説明を行う。なお、ラウンド数Rが偶数である場合の処理と共通する事項については説明を省略する。
【００８８】
まず、復号装置２０（図３）が、ラウンド数Rが偶数である場合の処理で説明したステップＳ２１，Ｓ２２の処理を実行する。
【００８９】
次に、復号装置２０の第２ビット分割部２３ｃが、記憶部２１からビット結合値yを読み込み、当該ビット結合値yをビット分割し、ビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを抽出し、
y→ t((R‐1)/2), s(((R‐1)/2)+1)
それらを記憶部２１に格納する（第２ビット分割過程／ステップＳ５０）。
【００９０】
次に、制御部１３ａがi=(R‐1)/2と設定し、当該iをレジスタ（図示せず）に保持する（ステップＳ５１）。
【００９１】
次に、復号装置２０の第４ハッシュ関数演算部２３ｆが、記憶部２１から少なくともビット列t(i)を読み込み、当該ビット列t(i)を含む値にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値h(2・i+1)を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する（第４ハッシュ関数演算過程／ステップＳ５２）。
【００９２】
具体的には、2・i+2=Rcであれば、第４ハッシュ関数演算部２３ｆは、記憶部２１からビット列t(i)と第１暗号文cとを読み込み、当該ビット列t(i)と第１暗号文cとのビット結合値t(i)|cにハッシュ関数
H(2・i+1)：{0,1}v→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1)(t(i)|c)
を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する。
【００９３】
一方、2・i+2≠Rcであれば、第４ハッシュ関数演算部２３ｆは、記憶部２１からビット列t(i)を読み込み、当該ビット列t(i)にハッシュ関数
H(2・i+1)：{0,1}v→{0,1}n−v 
を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1)(t(i))
を算出し、当該ハッシュ値h(2・i+1)を記憶部２１に格納する。
【００９４】
次に、復号装置２０の第４排他的論理和演算部２３ｇが、記憶部２１からビット列s(i+1)とハッシュ値h(2・i+1)とを読み込み、これらの排他的論理和演算
s(i)=s(i+1) (+) h(2・i+1)
を行い、その演算結果であるビット列s(i)を記憶部２１に格納する（第４排他的論理和演算過程／ステップＳ５３）。
【００９５】
次に、制御部１３ａがi={(R‐1)/2}‐1と設定し、当該iをレジスタ（図示せず）に保持する（ステップＳ５４）。
【００９６】
その後、ラウンド数Rが偶数である場合の処理で説明したステップＳ２５〜Ｓ３４の処理を実行し、復号結果mを出力する。
【００９７】
＜共通鍵生成過程〜撹乱過程・撹乱復元過程〜共通鍵復号過程の具体例＞
次に、ラウンド数R=4, 5の場合の「共通鍵生成過程〜撹乱過程」及び「撹乱復元過程〜共通鍵復号過程」の処理を例示する。
【００９８】
［ラウンド数R=4である場合］
図８（ａ）は、ラウンド数R=4, Rc=3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【００９９】
図８（ｂ）は、ラウンド数R=4, Rc=3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１００】
図９（ａ）は、ラウンド数R=4, Rc=2, 3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|c), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１０１】
図９（ｂ）は、ラウンド数R=4, Rc=2, 3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|c), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１０２】
図１０（ａ）は、ラウンド数R=4, Rc=1, 2, 3, 4の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)|c)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|c), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)|c)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１０３】
図１０（ｂ）は、ラウンド数R=4, Rc=1, 2, 3, 4の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)|c)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|c), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)|c)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１０４】
［ラウンド数R=5である場合］
図１１（ａ）は、ラウンド数R=5, Rc=3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(t(2)), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)と第1暗号文cとが出力される。
【０１０５】
図１１（ｂ）は、ラウンド数R=5, Rc=3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=2: h(5)= H(5)(t(2)), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１０６】
図１２（ａ）は、ラウンド数R=5, Rc=1, 2, 3, 4, 5の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)|c), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|c), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)|c), t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(t(2)|c), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)と第1暗号文cとが出力される。
【０１０７】
図１２（ｂ）は、ラウンド数R=5, Rc=1, 2, 3, 4, 5の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=2: h(5)= H(5)(t(2)|c), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(s(2)|c), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|c), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)|c), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１０８】
＜第１実施形態の特徴＞
本形態の暗号化装置１０は、pビット（p＞n≧2）の平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2（ビット列s(0)）と、p‐n+zビットの第３平文meにビット分割し、zビット（z≧k，kはセキュリティパラメータ）の乱数rと第１平文m1とをビット結合してビット列t(0)を生成する。また、乱数rを含むビット列t(0)を用いて共通鍵wを生成し、当該共通鍵wを用い、共通鍵暗号方式によって当該第３平文meを暗号化した第１暗号文cを生成する。さらに、ビット列s(0)とビット列t(0)とをOAEPの入力として第２暗号文uを生成し、第１暗号文cと第２暗号文uとを暗号文とする。ここで、第１暗号文c及び第２暗号文uのオーバーヘッドは、第２暗号文uを生成する過程でのパディングによるオーバーヘッドzビット（z≧k）のみである。特に、z=k，v=3kとした場合には、オーバーヘッドがkビットとなり、オーバーヘッドを最小化できる。
【０１０９】
また、本形態では、平文mのビット列を分割し、分割されたビット列に対し、それぞれ共通鍵方式の第１暗号文cと、落とし戸付き一方向性置換関数fを用いる第２暗号文uとを生成する。そのため、落とし戸付き一方向性置換関数fの入力域のビット長nからオーバーヘッドzを差し引いたビット長n‐zよりも長い平文mを暗号化できる。
【０１１０】
また、本形態では、撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)を、第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)とした。そのため、第１暗号文cをc'に改ざんするような選択暗号文攻撃を受けた場合に、復号時に第２暗号文uから生成される共通鍵wに影響が及び、第１暗号文cが正しく復号されなくなるため、攻撃者は有益な情報を得ることができない。その結果、選択暗号攻撃に対する安全性を確保できる。
【０１１１】
なお、安全性の観点から、少なくとも内側のラウンド（最初でも最後でもないラウンド）において、第１暗号文cを含む値をハッシュ関数の入力値とすることが望ましい。即ち、ラウンド数Rが偶数である場合には、撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのi≧1に対応するハッシュ値h(2・i+1)が、第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値であるか、或いは、少なくとも何れかのi≦(R/2)‐2に対応するハッシュ値h(2・i+2) が、第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値であり、ラウンド数Rが奇数である場合には、撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも何れかのiに対応するハッシュ値h(2・i+2) が、第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値であることが望ましい。また、安全性の観点からより好ましくは、全てのラウンドにおいて、第１暗号文cを含む値をハッシュ関数の入力値とすることが望ましい。
【０１１２】
なお、本発明は上述の実施形態に限定されるわけではなく、暗号化装置１０と復号装置２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【０１１３】
〔第２実施形態〕
次に、本発明の第２実施形態について説明する。
本形態は、第１実施形態の変形例であり、(1)暗号化装置が行う第２ビット結合過程で生成されるビット結合値yを、ラウンド数Rが偶数である場合には、所定値を示す付加情報bとビット列t(R/2)とビット列s(R/2)とを含むビット結合値とし、ラウンド数Rが奇数である場合には、所定値を示す付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値とする点、(2)復号装置が行う第２ビット分割過程において、ビット結合値yをビット分割し、ラウンド数Rが偶数である場合には、少なくとも付加情報bとビット列t(R/2)とビット列s(R/2)を抽出し、ラウンド数Rが奇数である場合には、少なくとも付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを抽出し、それらを復号装置の記憶部に格納する点、及び(3)第２ビット分割過程で抽出された付加情報bが所定値を示す場合にのみ撹乱復元過程と第３ビット分割過程と共通鍵生成過程と共通鍵復号過程と第３ビット結合過程が実行され、第２ビット分割過程で抽出された付加情報bが所定値以外の値を示す場合には、復号装置の偽装復号結果生成部が、pビットの乱数を生成し、当該乱数を復号結果として出力する点である。
【０１１４】
以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【０１１５】
＜全体構成＞
第２実施形態の暗号通信システムは、第１実施形態の暗号化装置１０を暗号化装置１１０に置換し、復号装置２０を復号装置１２０に置換した構成となる。
【０１１６】
＜ハードウェア構成＞
第１実施形態と同様であるため説明を省略する。
【０１１７】
＜ハードウェアとソフトウェアとの協働＞
第２実施形態の暗号化装置１１０及び復号装置１２０は、それぞれ、前述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【０１１８】
図１３は、第２実施形態の暗号化装置１１０の機能構成を例示したブロック図である。また、図１４は、第２実施形態の復号装置１２０の機能構成を例示したブロック図である。なお、図１３及び図１４において第１実施形態と共通する部分には、図２及び図３と同じ符号を付している。
【０１１９】
図１３に示すように、第２実施形態の暗号化装置１１０は、第１実施形態の暗号化装置１０の第２ビット結合部１３ｉを第２ビット結合部１１３ｉに置換した構成である。。なお、第２ビット結合部１１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置１１０は、制御部１３ａの制御の下、各処理を実行する。
【０１２０】
また、図１４に示すように、第２実施形態の復号装置１２０は、第１実施形態の復号装置２０の第２ビット分割部２３ｃを第２ビット分割部１２３ｃに置換し、さらに、判定部１２３ｄと偽装復号結果生成部１２３ｅを付加した構成である。なお、第２ビット分割部１２３ｃ、判定部１２３ｄ及び偽装復号結果生成部１２３ｅは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置１２０は、制御部２３ａの制御の下、各処理を実行する。
【０１２１】
また、本形態では、一例として、落とし戸付き一方向性置換関数fが、0以上N未満（Nは自然数）の値を入力とする関数であり、Ｎのビット長を|N|とし、付加情報bのビット長を|b|とした場合にn=|N|‐|b|を満たし、付加情報bが0を示すビット又はビット列であり、第２ビット結合過程で生成されるビット結合値yが、付加情報bが先頭にビット結合された値である場合について説明を行う。また、この例のような落とし戸付き一方向性置換関数fとしては、RSA暗号方式における暗号化関数
f(x)=xe mod N
を例示でき、その逆関数f−1としては、RSA暗号方式における復号関数
f−1(y)=yd mod N
を例示できる。なお、e, dはそれぞれRSA暗号の公開鍵，秘密鍵であり、x, yは0以上N未満の整数集合ZNの元である。また、付加情報bのビット長|b|には特に制限はないが、オーバーヘッドを小さくするという意味から|b|=1であることが望ましい。なお、前処理として、この付加情報bが暗号化装置１１０の記憶部１１に格納され、さらに、付加情報bと同一値を示す付加情報b’が復号装置１２０の記憶部２１とに格納される。或いは、これらの付加情報が予め各装置を構成するためのプログラムに記述される構成であってもよい。
【０１２２】
＜処理＞
次に、本形態の処理について説明する。以下では、第１実施形態の処理との相違点のみを説明する。また、本形態では、ラウンド数Ｒが偶数である場合と奇数である場合を同時に説明する。
【０１２３】
《暗号化処理》
図１５（ａ）は、第２実施形態の暗号化処理を説明するためのフローチャートである。
【０１２４】
まず、暗号化装置１１０（図１３）において、ラウンド数Ｒが偶数である場合にはステップＳ１〜Ｓ１３の処理を行い、ラウンド数Ｒが奇数である場合にはステップＳ１〜Ｓ１１，Ｓ４１〜Ｓ４５の処理を行う。
【０１２５】
その後、ラウンド数Rが偶数である場合には、暗号化装置１１０の第２ビット結合部１１３ｉが、所定値を示す付加情報bとビット列t(R/2)とビット列s(R/2)とを記憶部１１から読み込んで、それらのビット結合値
y=b|t(R/2)|s(R/2)  (Rが偶数の場合)
を算出して、当該ビット結合値yを記憶部１１に格納する。また、ラウンド数Rが奇数である場合には、暗号化装置１１０の第２ビット結合部１１３ｉが、所定値を示す付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを記憶部１１から読み込んで、それらのビット結合値
y=b|t((R‐1)/2)|s(((R‐1)/2)+1)  (Rが奇数の場合)
を算出して、当該ビット結合値yを記憶部１１に格納する（第２ビット結合過程／ステップＳ１１１）。
【０１２６】
その後、暗号化装置１１０が第１実施形態と同様に、ステップＳ１５，１６の処理を実行し、第１暗号文cと第２暗号文uを復号装置１２０に送信する。
【０１２７】
《復号処理》
図１５（ｂ）は、第２実施形態の復号処理を説明するためのフローチャートである。
【０１２８】
まず、復号装置１２０（図１４）において、第１実施形態で説明したステップＳ２１，Ｓ２２の処理を実行する。その後、復号装置１２０の第２ビット分割部１２３ｃが、記憶部２１からビット結合値yを読み込み、当該ビット結合値yをビット分割し、ラウンド数Rが偶数である場合には、付加情報bとビット列t(R/2)とビット列s(R/2)を抽出し、ラウンド数Rが奇数である場合には、付加情報bとビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを抽出し、それらを記憶部２１に格納する（第２ビット分割過程／ステップＳ１２１）。
【０１２９】
y→ b, t(R/2), s(R/2)  (Rが偶数の場合)
y→ b, t((R‐1)/2), s(((R‐1)/2)+1) (Rが奇数の場合)
なお、本形態では、ビット結合値yの上位|b|ビットを付加情報bとして抽出する。また、第１実施形態で説明したように、ビット結合値yのどの位置のビットを、ビット列t(R/2)とビット列s(R/2)、又は、ビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)として抽出するかは、第２ビット結合過程（ステップＳ１１１）でのビット結合方法に応じて決定される。
【０１３０】
次に、判定部１２３ｄが、記憶部２１からステップＳ１２１で格納された付加情報bと、前処理で格納された付加情報b’とを読み込み、これらが示す値が同一であるか否かを判定する（ステップＳ１２２）。ここで、b=b’でないと判定された場合、偽装復号結果生成部１２３ｅが、pビットの乱数を生成し、当該乱数を復号結果m’として出力する（偽装復号結果生成過程／ステップＳ１２３）。一方、b=b’であると判定された場合、第１実施形態と同様、ラウンド数Ｒが偶数の場合には、ステップＳ２４〜Ｓ３４の処理が実行され、ラウンド数Ｒが奇数の場合には、ステップＳ５１〜Ｓ５４，Ｓ２５〜Ｓ３４の処理が実行され、復号結果mが出力される。
【０１３１】
＜第２実施形態の特徴＞
本形態における第１暗号文c及び第２暗号文uのオーバーヘッドは、第２暗号文uを生成する過程でのパディング及び付加情報bによるオーバーヘッドz+|b|ビット（z≧k）のみである。特に、z=k，v=3k, |b|とした場合には、オーバーヘッドがk+1ビットとなり、オーバーヘッドを最小化できる。
【０１３２】
また、本形態でも、平文mのビット列を分割し、分割されたビット列に対し、それぞれ共通鍵方式の第１暗号文cと、落とし戸付き一方向性置換関数fを用いる第２暗号文uとを生成する。そのため、落とし戸付き一方向性置換関数fの入力域のビット長nからオーバーヘッドzを差し引いたビット長n‐zよりも長い平文mを暗号化できる。
【０１３３】
また、本形態では、撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)を、第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)とした。そのため、第１暗号文cをc'に改ざんするような選択暗号文攻撃を受けた場合に、復号時に第２暗号文uから生成される共通鍵wに影響が及び、第１暗号文cが正しく復号されなくなるため、攻撃者は有益な情報を得ることができない。その結果、選択暗号攻撃に対する安全性を確保できる。
【０１３４】
また、本形態では、ビット結合値yが付加情報bを具備し、復号装置１２０が当該付加情報bを用いて暗号文uの正当性を検証し、暗号文uが正当である場合には第１実施形態と同様に復号処理を行ってn‐zビットの復号結果を出力し、暗号文uが不当である場合にはpビットの乱数を復号結果として出力することとした。これにより、暗号文uが不当である場合に復号装置１２０が復号処理を行うことを防止できる。さらに、暗号文uが不当である場合に正規の復号結果と同じビット数pの乱数を復号結果として出力することで、選択暗号文攻撃に有効な情報が攻撃者に漏えいすることを防止できる。
【０１３５】
なお、本形態では、落とし戸付き一方向性置換関数fが、0以上N未満（Nは自然数）の値を入力とする関数であり、Ｎのビット長を|N|とし、付加情報bのビット長を|b|とした場合にn=|N|‐|b|を満たし、付加情報bは、0を示すビット又はビット列であり、第２ビット結合過程で生成されるビット結合値yが、付加情報bが先頭にビット結合された値である場合について説明した。しかし、本発明はこれに限定されず、落とし戸付き一方向性置換関数fとして、入力域がnビットのElGamal暗号の暗号化関数等を用いた場合に本形態を適用してもよい。また、付加情報b, b’が0以外の値を示すものであってもよい。
【０１３６】
また、本形態でも安全性の観点から、少なくとも内側のラウンド（最初でも最後でもないラウンド）において、第１暗号文cを含む値をハッシュ関数の入力値とすることが望ましい。さらに、暗号化装置１１０と復号装置１２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【０１３７】
〔第３実施形態〕
次に、本発明の第３実施形態について説明する。
第３実施形態は、第２実施形態の変形例であり、(1)付加情報bを少なくとも一部のハッシュ関数の入力に含める点、(2)復号装置において付加情報bの検証を行って暗号文の正当性を検証し、暗号文が不当である場合に乱数を復号結果として出力する処理を行わない点が第２実施形態と相違する。以下では、第１，２実施形態との相違点を中心に説明し、これらと共通する事項については説明を省略する。
【０１３８】
＜全体構成＞
第３実施形態の暗号通信システムは、第１実施形態の暗号化装置１０を暗号化装置２１０に置換し、復号装置２０を復号装置２２０に置換した構成となる。
【０１３９】
＜ハードウェア構成＞
第１実施形態と同様であるため説明を省略する。
【０１４０】
＜ハードウェアとソフトウェアとの協働＞
第２実施形態の暗号化装置２１０及び復号装置２２０は、それぞれ、前述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【０１４１】
図１６は、第３実施形態の暗号化装置２１０の機能構成を例示したブロック図である。また、図１７は、第３実施形態の復号装置２２０の機能構成を例示したブロック図である。なお、図１６及び図１７において第１，２実施形態と共通する部分には、図２，３，１４，１５と同じ符号を付している。
【０１４２】
図１６に示すように、第３実施形態の暗号化装置２１０は、第１実施形態の暗号化装置１０の第１ハッシュ関数演算部１３ｅを第１ハッシュ関数演算部２１３ｅに置換し、第２ハッシュ関数演算部１３ｇを第２ハッシュ関数演算部２１３ｇに置換し、第２ビット結合部１３ｉを第２ビット結合部１１３ｉに置換した構成である。。第１ハッシュ関数演算部２１３ｅ、第２ハッシュ関数演算部２１３ｇ、及び第２ビット結合部１１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置２１０は、制御部１３ａの制御の下、各処理を実行する。
【０１４３】
また、図１７に示すように、第３実施形態の復号装置２２０は、第１実施形態の復号装置２０の第２ビット分割部２３ｃを第２ビット分割部１２３ｃに置換し、第３ハッシュ関数演算部２３ｄを第３ハッシュ関数演算部２２３ｄに置換し、第４ハッシュ関数演算部２３ｆを第４ハッシュ関数演算部２２３ｆに置換した構成である。。なお、第２ビット分割部１２３ｃ、第３ハッシュ関数演算部２２３ｄ及び第４ハッシュ関数演算部２２３ｆは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置２２０は、制御部２３ａの制御の下、各処理を実行する。
【０１４４】
また、第３実施形態では、第１暗号文cをハッシュ関数の入力値に含めるラウンドを示す情報Rcに加え、付加情報ｂをハッシュ関数の入力値に含めるラウンドを示す情報Rbを設定しておく。
【０１４５】
また、本形態では、少なくとも一部のiに対応するハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、
H(2・i+1)：{0,1}v+|c|→{0,1}n−v  …(1)
H(2・i+2)：{0,1}n−v+|c|→{0,1}v  …(2)
又は、
H(2・i+1)：{0,1}v+|b|+|c|→{0,1}n−v  …(3)
H(2・i+2)：{0,1}n−v+|b|+|c|→{0,1}v  …(4)
入出力域を持ち、その他のiに対応するハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、
H(2・i+1)：{0,1}v→{0,1}n−v  …(5)
H(2・i+2)：{0,1}n−v→{0,1}v  …(6)
の入出力域を持つ。
【０１４６】
なお、上述したように付加情報bのビット長|b|に制限はないが、オーバーヘッドをできるだけ小さくするという観点から|b|=1であることが望ましい。
【０１４７】
また、各ハッシュ関数H(2・i+1)を式(1)(3)(5)いずれの関数にするか、及び、各ハッシュ関数H(2・i+1)を式(2)(4)(6)いずれの関数にするかについても特に制限はない。しかし、安全性の観点からは、ラウンド数Rが偶数である場合には、少なくとも何れかのi≧1に対応するハッシュ関数H(2・i+1)を式(1)又は(3)の関数とするか、或いは、少なくとも何れかのi≦(R/2)‐2に対応するハッシュ関数H(2・i+2)を式(2)又は(4)の関数とすることが望ましい。同様な観点から、ラウンド数Rが偶数である場合には、少なくとも何れかのiに対応するハッシュ関数H(2・i+2)を式(2)又は(4)の関数とすることが望ましい。すなわち、最初のラウンド及び最後のラウンド以外のハッシュ関数のうち、少なくとも一部を式(1)(2)(3)(4)のいずれかにすることが望ましい。また、安全性の観点からより好ましくは、全てのハッシュ関数を式1)(2)(3)(4)のいずれかにすることが望ましい。
【０１４８】
＜処理＞
《暗号化処理》
第１実施形態との相違点は、(1)暗号化装置２１０が、ステップＳ１２又はＳ４６の代わりに、第２実施形態で説明したステップＳ１１１の処理を実行し、ビット結合値
y=b|t(R/2)|s(R/2)  (Rが偶数の場合)
y=b|t((R‐1)/2)|s(((R‐1)/2)+1)  (Rが奇数の場合)
を生成する点、(2)撹乱過程で、第１ハッシュ関数演算部２１３ｅ及び／又は第２ハッシュ関数演算部２１３ｇでそれぞれ算出される、少なくとも一部のiに対応する、ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、さらに付加情報bを結合したビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又はh(2・i+2) であり、その他のハッシュ値が第１，２実施形態と同様である点である。各ラウンドのハッシュ値は以下のように場合分けされる。
【０１４９】
［2・i+1=Rc=Rbであるラウンド］
h(2・i+1)= H(2・i+1)(t(i)|b|c) （H(2・i+1)：{0,1}v+|b|+|c|→{0,1}n−v）
［2・i+2=Rc=Rbであるラウンド］
h(2・i+2)= H(2・i+2)(s(i+1)|b|c)（H(2・i+2)：{0,1}n−v→{0,1}v）
［2・i+1=Rc≠Rbであるラウンド］
h(2・i+1)= H(2・i+1)(t(i)|c) （H(2・i+1)：{0,1}v+|c|→{0,1}n−v）
［2・i+2=Rc≠Rbであるラウンド］
h(2・i+2)= H(2・i+2)(s(i+1)|c)（H(2・i+2)：{0,1}n−v→{0,1}v）
［2・i+1=Rb≠Rcであるラウンド］
h(2・i+1)= H(2・i+1)(t(i)|b) （H(2・i+1)：{0,1}v+|b|→{0,1}n−v）
［2・i+2=Rb≠Rcであるラウンド］
h(2・i+2)= H(2・i+2)(s(i+1)|b)（H(2・i+2)：{0,1}n−v→{0,1}v）
［Rb≠2・i+1≠Rcであるラウンド］
h(2・i+1)= H(2・i+1)(t(i)) （H(2・i+1)：{0,1}v→{0,1}n−v）
［Rb≠2・i+2≠Rcであるラウンド］
h(2・i+2)= H(2・i+2)(s(i+1))（H(2・i+2)：{0,1}n−v→{0,1}v）
【０１５０】
《復号処理》
第１実施形態との相違点は、(1)復号装置２２０が、ステップＳ２３又はＳ５０に代わりに、第２実施形態で説明したステップＳ１２１の処理を実行し、ビット結合値yから
y→ b, t(R/2), s(R/2)（Rが偶数の場合）
y→ b, t((R−1)/2), s(((R−1)/2)+1) （Rが奇数の場合）
を抽出する点、(2)撹乱復元過程で、第４ハッシュ関数演算部２２３ｆ及び／又は第３ハッシュ関数演算部２２３ｄでそれぞれ算出される、少なくとも一部のiに対応する、ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、さらに付加情報bをビット結合させたビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又はh(2・i+2)であり、その他のハッシュ値が第１，２実施形態と同様である点である。各ラウンドのハッシュ値の場合分けは、上述の暗号化処理の場合と同一である。
【０１５１】
＜共通鍵生成過程〜撹乱過程・撹乱復元過程〜共通鍵復号過程の具体例＞
次に、本形態の共通鍵生成過程〜撹乱過程・撹乱復元過程〜共通鍵復号過程の具体例を説明する。
【０１５２】
［ラウンド数R=4である場合］
図１８（ａ）は、第３実施形態のR=4, Rb=3, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|b|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１５３】
図１８（ｂ）は、第３実施形態のラウンド数R=4, Rb=3, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|b|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１５４】
図１９（ａ）は、第３実施形態のR=4, Rb=2, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|b), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１５５】
図１９（ｂ）は、第３実施形態のラウンド数R=4, Rb=2, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|b), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１５６】
図２０（ａ）は、第３実施形態のR=4, Rb=1,2,3,4, Rc=1,2,3,4の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)|b|c), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|b|c), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|b|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)|b|c), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１５７】
図２０（ｂ）は、第３実施形態のラウンド数R=4, Rb=1,2,3,4, Rc=1,2,3,4の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)|b|c), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|b|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|b|c), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)|b|c), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１５８】
［ラウンド数R=5である場合］
図２１（ａ）は、ラウンド数R=5, Rb=3, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|b|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(t(2)), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)と第1暗号文cとが出力される。
【０１５９】
図２１（ｂ）は、ラウンド数R=5, Rb=3, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=2: h(5)= H(5)(t(2)), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|b|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１６０】
図２２（ａ）は、ラウンド数R=5, Rb=2,4, Rc=3,4の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|b), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)|b|c), t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(t(2)), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)と第1暗号文cとが出力される。
【０１６１】
図２２（ｂ）は、ラウンド数R=5, Rb=2,4, Rc=3,4の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=2: h(5)= H(5)(t(2)), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(s(2)|b|c), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|b), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１６２】
図２３（ａ）は、ラウンド数R=5, Rb=1,2,3,4,5, Rc=1,2,3,4,5の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)|b|c), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)|b|c), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|b|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)|b|c), t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(t(2)|b|c), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)と第1暗号文cとが出力される。
【０１６３】
図２３（ｂ）は、ラウンド数R=5, Rb=1,2,3,4,5, Rc=1,2,3,4,5の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=2: h(5)= H(5)(t(2)|b|c), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(s(2)|b|c), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|b|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)|b|c), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)|b|c), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１６４】
＜第３実施形態の特徴＞
本形態でも、第１，２実施形態で説明したのと同様、短いオーバーヘッドで長い平文を暗号化できる。また、本形態では、ビット結合値yが付加情報bを具備し、この付加情報bを少なくとも一部のハッシュ関数の入力値に含めることとしたため、安全性がより向上する。さらに、そのために第２実施形態のように復号時に付加情報bの値を検証したり、乱数を復号結果として生成する必要もない。
【０１６５】
また、暗号化装置２１０と復号装置２２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【０１６６】
〔第４実施形態〕
次に、本発明の第４実施形態について説明する。
【０１６７】
本形態は、第１実施形態の変形例であり、従来のOAEP或いはOAEP 3-roundを含むOAEPの変形例を用い、本発明を構成した形態である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【０１６８】
＜全体構成＞
第４実施形態の暗号通信システムは、第１実施形態の暗号化装置１０を暗号化装置３１０に置換し、復号装置２０を復号装置３２０に置換した構成となる。
【０１６９】
＜ハードウェア構成＞
第１実施形態と同様であるため説明を省略する。
【０１７０】
＜ハードウェアとソフトウェアとの協働＞
第４実施形態の暗号化装置３１０及び復号装置３２０は、それぞれ、前述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【０１７１】
図２４は、第２実施形態の暗号化装置３１０の機能構成を例示したブロック図である。また、図２５は、第２実施形態の復号装置３２０の機能構成を例示したブロック図である。なお、図２４及び図２５において第１実施形態と共通する部分には、図２及び図３と同じ符号を付している。
【０１７２】
図２４に示すように、第４実施形態の暗号化装置３１０は、第１実施形態の暗号化装置１０の第１ビット分割部１３ｃを第１ビット分割部３１３ｃに置換し、第１ビット結合部１３ｄを取り除いた構成である。なお、第１ビット分割部３１３ｃは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置３１０は、制御部１３ａの制御の下、各処理を実行する。
【０１７３】
また、図２５に示すように、第４実施形態の復号装置３２０は、第１実施形態の復号装置２０の第３ビット結合部２３ｉを第３ビット結合部３２３ｉに置換し、第３ビット分割部２３ｈを取り除いた構成である。なお、第３ビット結合部３２３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置３２０は、制御部２３ａの制御の下、各処理を実行する。
【０１７４】
＜処理＞
次に、本形態の処理について説明する。以下では、第１実施形態の処理との相違点のみを説明する。また、本形態では、ラウンド数Ｒが偶数である場合と奇数である場合を同時に説明する。
【０１７５】
《暗号化処理》
図２６（ａ）は、第２実施形態の暗号化処理を説明するためのフローチャートである。
【０１７６】
まず、暗号化装置３１０（図２４）の記憶部１１にpビット（p＞n≧2）の平文mを格納する（平文格納過程／ステップＳ１）。
【０１７７】
次に、暗号化装置３１０の乱数生成部１３がvビット（n＞v≧2k，kはセキュリティパラメータ）の乱数rを生成し、これをビット列t(0)として記憶部１１に格納する（乱数格納過程／ステップＳ２０２）。なお、乱数r のビット数vはn＞v≧2kであればよいが、オーバーヘッドを最小化するという観点からはv=2ｋであることが望ましい。
【０１７８】
次に、暗号化装置３１０の第１ビット分割部３１３ｃが、記憶部１１から平文mを読み込み、当該平文mを、n‐vビットの第１平文m1と、p‐n+vビットの第２平文meとにビット分割し、当該第１平文m1であるビット列s(0)と、第２平文meとを記憶部１１に格納する（第１ビット分割過程／ステップＳ２０３）。
【０１７９】
次に、暗号化装置３１０の共通鍵生成部１３ｋが、記憶部１１から乱数rを含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを記憶部１１に格納する（共通鍵生成過程／ステップＳ２０４）。本形態では、第１実施形態と同じハッシュ関数Gを用い、
w=G(t(0))
の演算によって共通鍵wを生成する。
【０１８０】
その後、ラウンド数Ｒが偶数であれば、第１実施形態のステップＳ６〜Ｓ１６の処理が実行され、ラウンド数Ｒが奇数であれば、第１実施形態のステップＳ６〜Ｓ１１，Ｓ４１〜Ｓ４６，Ｓ１５，Ｓ１６の処理が実行され、第１暗号文ｃと第２暗号文ｕとが復号装置３２０に送信される。
【０１８１】
《復号処理》
図２６（ｂ）は、第４実施形態の復号処理を説明するためのフローチャートである。
【０１８２】
まず、復号装置３２０（図２５）において、ラウンド数Ｒが偶数であれば、第１実施形態のステップＳ２１〜Ｓ３０の処理が実行され、ラウンド数Ｒが奇数であれば、第１実施形態のステップＳ２１，Ｓ２２，Ｓ５０〜Ｓ５４，Ｓ２５〜Ｓ３０の処理が実行される。
【０１８３】
次に、復号装置３２０の共通鍵生成部２３ｊが、記憶部２１からビット列t(0)を含む情報を読み込み、当該情報によって定まる共通鍵wを生成し、当該共通鍵wを記憶部２１に格納する（共通鍵生成過程／ステップＳ２３２）。本形態では、第１実施形態と同じハッシュ関数Gを用い、
w=G(t(0))
の演算によって共通鍵wを生成する。
【０１８４】
次に、復号装置３２０の共通鍵復号部２３ｋが、記憶部２１から第１暗号文cと共通鍵wとを読み込み、当該共通鍵wを用い、当該第１暗号文cを復号して第２平文
me=Dw(c)
を抽出し、当該第２平文meを記憶部２１に格納する（共通鍵復号過程／ステップＳ３３）。
【０１８５】
次に、復号装置３２０の第３ビット結合部３２３ｉが、記憶部２１から、ビット列s(0)と第２平文meとを読み込み、これらのビット結合値
s(0)|me
を生成し、当該ビット結合値を復号結果mとして出力する（第３ビット結合過程／ステップＳ２３４）。
【０１８６】
＜共通鍵生成過程〜撹乱過程・撹乱復元過程〜共通鍵復号過程の具体例＞
次に、ラウンド数R=3 4の場合の「共通鍵生成過程〜撹乱過程」及び「撹乱復元過程〜共通鍵復号過程」の処理を例示する。
【０１８７】
［ラウンド数R=4である場合］
図２７（ａ）は、ラウンド数R=4, Rc=3の場合における、第４実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3), h(4)=H(4)(s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)と第1暗号文cとが出力される。
【０１８８】
図２７（ｂ）は、ラウンド数R=4, Rc=3の場合における、第４実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１８９】
［ラウンド数R=3である場合］
図２８（ａ）は、ラウンド数R=3, Rc=3の場合における、第４実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。この例では、
w=G(t(0)), c=Ew(me)
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2)(s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(t(1)|c), s(2)=s(1) (+) h(3)
が実行され、ビット列t(1)とビット列s(2)と第1暗号文cとが出力される。
【０１９０】
図２８（ｂ）は、ラウンド数R=3, Rc=3の場合における、第４実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。この例では、
i=1: h(3)= H(3)(t(1)|c), s(1)=s(2) (+) h(3)
i=0: h(2)=H(2)(s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1) 
w=G(t(0)), me=Dw(c)
が実行され、ビット列t(0)とビット列s(0)とmeとが出力される。
【０１９１】
＜第４実施形態の特徴＞
本形態の暗号化装置３１０で生成される第１暗号文c及び第２暗号文uのオーバーヘッドは、第２暗号文uを生成する過程でのパディングによるオーバーヘッドvビット（v≧2k）のみである。特に、v=2kとした場合には、オーバーヘッドが2kビットとなり、オーバーヘッドを最小化できる。
【０１９２】
また、本形態では、平文mのビット列を分割し、分割されたビット列に対し、それぞれ共通鍵方式の第１暗号文cと、落とし戸付き一方向性置換関数fを用いる第２暗号文uとを生成する。そのため、落とし戸付き一方向性置換関数fの入力域のビット長nからオーバーヘッドvを差し引いたビット長n‐vよりも長い平文mを暗号化できる。
【０１９３】
また、本形態でも、撹乱過程及び撹乱復元過程でそれぞれ算出される、少なくとも一部のiに対応する、ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)を、第１暗号文cとビット列t(i)とを含むビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値h(2・i+1)及び／又は第１暗号文cとビット列s(i+1)とを含むビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値h(2・i+2)とした。そのため、第１暗号文cをc'に改ざんするような選択暗号文攻撃を受けた場合に、復号時に第２暗号文uから生成される共通鍵wに影響が及び、第１暗号文cが正しく復号されなくなるため、攻撃者は有益な情報を得ることができない。その結果、選択暗号攻撃に対する安全性を確保できる。
【０１９４】
なお、安全性の観点から、少なくとも内側のラウンド（最初でも最後でもないラウンド）において、第１暗号文cを含む値をハッシュ関数の入力値とすることが望ましい。また、安全性の観点からより好ましくは、全てのラウンドにおいて、第１暗号文cを含む値をハッシュ関数の入力値とすることが望ましい。
【０１９５】
また、本形態に、第２実施形態や第３実施形態で説明した付加情報bを導入してもよい。その導入方法は、第２実施形態や第３実施形態と同様である。
【０１９６】
また、暗号化装置３１０と復号装置３２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【０１９７】
〔その他の変形等〕
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、上述した以外のOAEPの変形例を用いて本発明を構成してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１９８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１９９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２０２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０２０３】
本発明は、例えば、公開鍵暗号を用いた暗号通信技術に利用できる。
【図面の簡単な説明】
【０２０４】
【図１】図１（ａ）は、第１実施形態の暗号通信システムの構成を例示した図である。図１（ｂ）は、この暗号化装置のハードウェア構成を例示したブロック図である。
【図２】図２は、第１実施形態の暗号化装置の機能構成を例示したブロック図である。
【図３】図３は、第１実施形態の復号装置の機能構成を例示したブロック図である。
【図４】図４は、ラウンド数R（R≧4）が偶数である場合における暗号化処理を説明するためのフローチャートである。
【図５】図５は、ラウンド数R（R≧4）が偶数である場合における復号処理を説明するためのフローチャートである。
【図６】図６は、ラウンド数R（R≧4）が奇数である場合における暗号化処理を説明するためのフローチャートである。
【図７】図７は、ラウンド数Rが奇数である場合における復号処理を説明するためのフローチャートである。
【図８】図８（ａ）は、ラウンド数R=4, Rc=3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図８（ｂ）は、ラウンド数R=4, Rc=3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図９】図９（ａ）は、ラウンド数R=4, Rc=2, 3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図９（ｂ）は、ラウンド数R=4, Rc=2, 3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図１０】図１０（ａ）は、ラウンド数R=4, Rc=1, 2, 3, 4の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図１０（ｂ）は、ラウンド数R=4, Rc=1, 2, 3, 4の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図１１】図１１（ａ）は、ラウンド数R=5, Rc=3の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図１１（ｂ）は、ラウンド数R=5, Rc=3の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図１２】図１２（ａ）は、ラウンド数R=5, Rc=1, 2, 3, 4, 5の場合における、第１実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図１２（ｂ）は、ラウンド数R=5, Rc=1, 2, 3, 4, 5の場合における、第１実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図１３】図１３は、第２実施形態の暗号化装置の機能構成を例示したブロック図である。
【図１４】図１４は、第２実施形態の復号装置の機能構成を例示したブロック図である。
【図１５】図１５（ａ）は、第２実施形態の暗号化処理を説明するためのフローチャートである。図１５（ｂ）は、第２実施形態の復号処理を説明するためのフローチャートである。
【図１６】図１６は、第３実施形態の暗号化装置の機能構成を例示したブロック図である。
【図１７】図１７は、第３実施形態の復号装置の機能構成を例示したブロック図である。
【図１８】図１８（ａ）は、第３実施形態のR=4, Rb=3, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。図１８（ｂ）は、第３実施形態のラウンド数R=4, Rb=3, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図１９】図１９（ａ）は、第３実施形態のR=4, Rb=2, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。図１９（ｂ）は、第３実施形態のラウンド数R=4, Rb=2, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２０】図２０（ａ）は、第３実施形態のR=4, Rb=1,2,3,4, Rc=1,2,3,4の場合における、第３実施形態の共通鍵生成過程〜撹乱過程の一例を説明するための図である。図２０（ｂ）は、第３実施形態のラウンド数R=4, Rb=1,2,3,4, Rc=1,2,3,4の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２１】図２１（ａ）は、ラウンド数R=5, Rb=3, Rc=3の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図２１（ｂ）は、ラウンド数R=5, Rb=3, Rc=3の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２２】図２２（ａ）は、ラウンド数R=5, Rb=2,4, Rc=3,4の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図２２（ｂ）は、ラウンド数R=5, Rb=2,4, Rc=3,4の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２３】図２３（ａ）は、ラウンド数R=5, Rb=1,2,3,4,5, Rc=1,2,3,4,5の場合における、第３実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図２３（ｂ）は、ラウンド数R=5, Rb=1,2,3,4,5, Rc=1,2,3,4,5の場合における、第３実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２４】図２４は、第２実施形態の暗号化装置の機能構成を例示したブロック図である。
【図２５】図２５は、第２実施形態の復号装置の機能構成を例示したブロック図である。
【図２６】図２６（ａ）は、第２実施形態の暗号化処理を説明するためのフローチャートである。図２６（ｂ）は、第４実施形態の復号処理を説明するためのフローチャートである。
【図２７】図２７（ａ）は、ラウンド数R=4, Rc=3の場合における、第４実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図２７（ｂ）は、ラウンド数R=4, Rc=3の場合における、第４実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２８】図２８（ａ）は、ラウンド数R=3, Rc=3の場合における、第４実施形態の共通鍵生成過程〜撹乱過程を説明するための図である。図２８（ｂ）は、ラウンド数R=3, Rc=3の場合における、第４実施形態の撹乱復元過程〜共通鍵復号過程を説明するための図である。
【図２９】図２９（ａ）は、従来のOAEP 3-roundパディング関数pdの処理を説明するための図であり、図２９（ｂ）は、その逆関数pd-1の処理を説明するための図である。
【符号の説明】
【０２０５】
１０，１１０，２１０，３１０  暗号化装置
２０，１２０，２２０，３２０  復号装置
【図１】
0005038866.tif 000002
【図２】
0005038866.tif 000003
【図３】
0005038866.tif 000004
【図４】
0005038866.tif 000005
【図５】
0005038866.tif 000006
【図６】
0005038866.tif 000007
【図７】
0005038866.tif 000008
【図８】
0005038866.tif 000009
【図９】
0005038866.tif 000010
【図１０】
0005038866.tif 000011
【図１１】
0005038866.tif 000012
【図１２】
0005038866.tif 000013
【図１３】
0005038866.tif 000014
【図１４】
0005038866.tif 000015
【図１５】
0005038866.tif 000016
【図１６】
0005038866.tif 000017
【図１７】
0005038866.tif 000018
【図１８】
0005038866.tif 000019
【図１９】
0005038866.tif 000020
【図２０】
0005038866.tif 000021
【図２１】
0005038866.tif 000022
【図２２】
0005038866.tif 000023
【図２３】
0005038866.tif 000024
【図２４】
0005038866.tif 000025
【図２５】
0005038866.tif 000026
【図２６】
0005038866.tif 000027
【図２７】
0005038866.tif 000028
【図２８】
0005038866.tif 000029
【図２９】
0005038866.tif 000030