(57)【特許請求の範囲】
【請求項１】
(A)  暗号化装置の記憶部にn‐zビット（n＞z≧k，kはセキュリティパラメータ）の平文mを格納する平文格納過程と、
(B)  上記暗号化装置の記憶部にzビットの乱数rを格納する乱数格納過程と、
(C)  暗号化装置の第１ビット分割部が、平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2とにビット分割し、当該第２平文m2をビット列s(0)とする第１ビット分割過程と、
(D)  暗号化装置の第１ビット結合部が、乱数rと第１平文m1とのビット結合値を生成し、当該ビット結合値をビット列t(0)とする第１ビット結合過程と、
(E)  ラウンド数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について上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程とを実行する、撹乱過程と、
(F)  ラウンド数Rが偶数である場合には、暗号化装置の第２ビット結合部が、ビット列t(R/2)とビット列s(R/2)とを含むビット結合値yを生成し、
ラウンド数Rが奇数である場合には、暗号化装置の第２ビット結合部が、ビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値yを生成する、第２ビット結合過程と、
(G)  暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた暗号文u=f(y)を算出する一方向性置換関数演算過程と、
(H)  暗号化装置の送信部が、暗号文uを復号装置に送信する暗号文送信過程と、
(I)  暗号文uを復号装置の記憶部に格納する暗号文格納過程と、
(J)  復号装置の逆関数演算部が、暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算過程と、
(K)  復号装置の第２ビット分割部が、ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出する第２ビット分割過程と、
(L)  ラウンド数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まで順番に、上記第３ハッシュ関数演算過程と上記第３排他的論理和演算過程と上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行する、撹乱復元過程と、
(M)  復号装置の第３ビット分割部が、ビット列t(0)をビット分割し、zビットの乱数rとv‐zビットの第１平文m1とを抽出する第３ビット分割過程と、
(N)  復号装置の第３ビット結合部が、第１平文m1とビット列s(0)とのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合過程と、
を有することを特徴とする暗号通信方法。
【請求項２】
請求項１に記載の暗号通信方法であって、
上記第２ビット結合過程で生成される上記ビット結合値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が上記所定値以外の値を示す場合に、復号装置の偽装復号結果生成部が、n‐zビットの乱数を生成し、当該乱数を復号結果として出力する偽装復号結果生成過程をさらに有する、
ことを特徴とする暗号通信方法。
【請求項３】
請求項１に記載の暗号通信方法であって、
上記第２ビット結合過程で生成される上記ビット結合値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が先頭にビット結合された値である、
ことを特徴とする暗号通信方法。
【請求項６】
請求項１から５の何れかに記載の暗号通信方法であって、
z=kであり、v=3kである、
ことを特徴とする暗号通信方法。
【請求項７】
n‐zビット（n＞z≧k，kはセキュリティパラメータ）の平文mと、zビットの乱数rとが格納された記憶部と、
上記記憶部から平文mを読み込み、当該平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2とにビット分割し、当該第１平文m1と、第２平文m2であるビット列s(0)と、を上記暗号化装置の記憶部に格納する第１ビット分割部と、
上記記憶部から乱数rと第１平文m1とを読み込み、これらのビット結合値を生成し、当該ビット結合値をビット列t(0)として上記記憶部に格納する第１ビット結合部と、
上記記憶部からビット列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を上記記憶部に格納する一方向性置換関数演算部と、
上記記憶部から読み込まれた暗号文uを復号装置に送信する送信部と、
を有することと特徴とする暗号化装置。
【請求項８】
請求項７に記載の暗号化装置から送信された暗号文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とを上記記憶部に格納する第３ビット分割部と、
上記記憶部から、第１平文m1とビット列s(0)とを読み込み、これらのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合部と、
を有することを特徴とする復号装置。
【請求項９】
請求項７に記載の暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項８に記載の暗号化装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信技術に関し、特に、公開鍵暗号通信技術に関する。
【背景技術】
【０００２】
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を出力する。
【０００９】
この方式のオーバーヘッドが2ｋビットとなる理由は、乱数rと同じビット数の出力域を持つハッシュ関数H2を利用しているためである。従来方式の安全性の解析では、ハッシュ関数の出力が衝突を起こさないことが前提となっている。図２０の方式ではハッシュ関数H2の出力域が乱数rのビット数|r|と同一でなければならないところ、異なる入力値に対する理想化されたハッシュ関数H2の出力値がq回訊かれる（即ち、攻撃者がハッシュ関数H2をq回計算する）とすると、その出力がすべて異なる確率は1‐(q2)/(2|r|)となる。qが2k以下であるとすると、この確率1‐(22k)/(2|r|)が意味を持つ（即ち、０以上より大きくなる）ためには、|r|は2kよりも大きくなければならない。
【００１０】
また、公開鍵暗号が安全となる、即ち識別不可能性を有する為には、kビットの乱数を用いることは不可避であり、その意味で、オーバーヘッドをkビットより小さくすることはできない。即ち、kビットがオーバーヘッドの最小値である。
【００１１】
より強い仮定に基づく場合、kビットのオーバーヘッドを達成できる。PhanとPointchevalは、非特許文献２の中で、理想化された落とし戸付き一方向性置換が利用できるという仮定を用いてkビットのオーバーヘッドとなる方法を提案している。しかしながら、非特許文献２では、理想化された落とし戸付き一方向性置換が現実のどのような関数に対応するのかは全く示されておらず、この方法を具体的に実現することは困難である。その上、理想化された落とし戸付き一方向性置換という仮定は、理想化されたハッシュ関数よりも更に強い仮定であり、即ち、達成することがより困難なものであるため、暗号方式の構成要素として望ましくない。
【００１２】
また、Jonssonは、非特許文献３において、理想化された対称鍵暗号が利用できるという仮定の下でkビットのオーバーヘッドとなる方法を提案しているが、これも上記と同様に、ハッシュ関数よりも更に強い仮定を用いたものであり、望ましくない。
【非特許文献１】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＞
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述のように、理想化されたハッシュ関数を用いた場合に適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた従来の公開鍵暗号のうち、最も効率の良い方法のオーバーヘッドは2kビットである。そのため、理想化されたハッシュ関数を用いた場合に適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号では、n-2kビットまでの平文しか暗号化できなかった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、従来よりも効率がよい、理想化されたハッシュ関数を用いた場合に適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明では、上述の課題を解決するために、
(A)  暗号化装置の記憶部にn‐zビット（n＞z≧k，kはセキュリティパラメータ）の平文mを格納する平文格納過程と、
(B)  上記暗号化装置の記憶部にzビットの乱数rを格納する乱数格納過程と、
(C)  暗号化装置の第１ビット分割部が、平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2とにビット分割し、当該第２平文m2をビット列s(0)とする第１ビット分割過程と、
(D)  暗号化装置の第１ビット結合部が、乱数rと第１平文m1とのビット結合値を生成し、当該ビット結合値をビット列t(0)とする第１ビット結合過程と、
(E)  ラウンド数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について上記第１ハッシュ関数演算過程と上記第１排他的論理和演算過程とを実行する、撹乱過程と、
【００１７】
(F)  ラウンド数Rが偶数である場合には、暗号化装置の第２ビット結合部が、ビット列t(R/2)とビット列s(R/2)とを含むビット結合値yを生成し、
ラウンド数Rが奇数である場合には、暗号化装置の第２ビット結合部が、ビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを含むビット結合値yを生成する、第２ビット結合過程と、
(G)  暗号化装置の一方向性置換関数演算部が、ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた暗号文u=f(y)を算出する一方向性置換関数演算過程と、
(H)  暗号化装置の送信部が、暗号文uを復号装置に送信する暗号文送信過程と、
(I)  暗号文uを復号装置の記憶部に格納する暗号文格納過程と、
(J)  復号装置の逆関数演算部が、暗号文uに対して上記落とし戸付き一方向性置換関数fの逆関数f−1を作用させ、ビット結合値y=f−1(u)を抽出する逆関数演算過程と、
(K)  復号装置の第２ビット分割部が、ビット結合値yをビット分割し、ラウンド数Rが偶数である場合にはビット列t(R/2)とビット列s(R/2)とを少なくとも抽出し、ラウンド数Rが奇数である場合にはビット列t((R‐1)/2)とビット列s(((R‐1)/2)+1)とを少なくとも抽出する第２ビット分割過程と、
(L)  ラウンド数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まで順番に、上記第３ハッシュ関数演算過程と上記第３排他的論理和演算過程と上記第４ハッシュ関数演算過程と上記第４排他的論理和演算過程とを実行する、撹乱復元過程と、
(M)  復号装置の第３ビット分割部が、ビット列t(0)をビット分割し、zビットの乱数rとv‐zビットの第１平文m1とを抽出する第３ビット分割過程と、
(N)  復号装置の第３ビット結合部が、第１平文m1とビット列s(0)とのビット結合値を生成し、当該ビット結合値を復号結果として出力する第３ビット結合過程と、を実行する。
【００２０】
このように本発明では、平文mを第１平文m1と第２平文m2とにビット分割し、乱数rと第１平文m1とのビット結合値と、第２平文m2とを入力として撹乱過程を実行する。前述のように、ハッシュ関数の出力域との関係では乱数rと第１平文m1とのビット結合値のビット数は2k以上でなければならないが、このビットの一部を第１平文m1とできることにより、従来よりもオーバーヘッドを向上できる。
【００２１】
また、安全性のためには、復号要求によって乱数rが攻撃者に漏えいしないことが重要である。本発明では、乱数rと第１平文m1とのビット結合値を用いているが、この場合、平文が攻撃者に与えられることによって乱数rに関する情報が攻撃者に漏えいすることを防止するための処置が必要となる。本発明では、ラウンド数Rを４以上とし、乱数rと第１平文m1との結合を攪乱することによって、このような危険性を排除している。
【発明の効果】
【００２２】
以上のように、本発明では、従来よりも効率がよい、理想化されたハッシュ関数を用いた場合に適応的選択暗号攻撃に対して安全な、落とし戸付き一方向性置換関数を用いた公開鍵暗号が実現できる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１実施形態〕
＜全体構成＞
図１（ａ）は、第１実施形態の暗号通信システム１の構成を例示した図である。
図１（ａ）に例示するように、本形態の暗号通信システム１は、公開鍵暗号方式によって暗号化を行う暗号化装置１０と、それによって生成された暗号文を復号する復号装置２０とを有し、それらはインターネット等の安全ではないネットワーク３０を通じて通信可能に接続されている。なお、暗号化装置１０と復号装置２０との間の通信はネットワーク３０を通じて行われるが、以下ではその旨を省略して説明する。
【００２４】
＜ハードウェア構成＞
図１（ｂ）は、暗号化装置１０のハードウェア構成を例示したブロック図である。
【００２５】
図１（ｂ）に例示するように、この例の暗号化装置１０は、ＣＰＵ（Central Processing Unit）１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ（Random Access Memory）１０ｆ、ＲＯＭ（Read Only Memory）１０ｅ及びバス１０ｇを有している。
【００２６】
ＣＰＵ１０ａは、読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１０ｂは、データが入力される入力ポート、キーボード、マウス等であり、出力部１０ｃは、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１０ｄは、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、ＲＡＭ１０ｆは、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等である。また、バス１０ｇは、ＣＰＵ１０ａ、入力部１０ｂ、出力部１０ｃ、補助記憶装置１０ｄ、ＲＡＭ１０ｆ及びＲＯＭ１０ｅを通信可能に接続している。
なお、復号装置２０のハードウェア構成は、暗号化装置１０のそれと同様であるため説明を省略する。
【００２７】
＜ハードウェアとソフトウェアとの協働＞
第１実施形態の暗号化装置１０及び復号装置２０は、それぞれ、上述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【００２８】
図２は、第１実施形態の暗号化装置１０の機能構成を例示したブロック図である。また、図３は、第１実施形態の復号装置２０の機能構成を例示したブロック図である。なお、図２，３における矢印はデータの流れを示すが、制御部１３ａ，２３ａに出入りするデータの流れに対応する矢印は省略してある。
【００２９】
図２に例示するように、本形態の暗号化装置１０は、記憶部１１と、送信部１２と、制御部１３ａと、乱数生成部１３ｂと、第１ビット分割部１３ｃと、第１ビット結合部１３ｄと、第１ハッシュ関数演算部１３ｅと、第１排他的論理和演算部１３ｆと、第２ハッシュ関数演算部１３ｇと、第２排他的論理和演算部１３ｈと、第２ビット結合部１３ｉと、一方向性置換関数演算部１３ｊとを有する。
【００３０】
なお、記憶部１１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、送信部１２は、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部１３ａ、乱数生成部１３ｂ、第１ビット分割部１３ｃ、第１ビット結合部１３ｄ、第１ハッシュ関数演算部１３ｅ、第１排他的論理和演算部１３ｆ、第２ハッシュ関数演算部１３ｇ、第２排他的論理和演算部１３ｈ、第２ビット結合部１３ｉ及び一方向性置換関数演算部１３ｊは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置１０は、制御部１３ａの制御の下、各処理を実行する。
【００３１】
図３に例示するように、本形態の復号装置２０は、記憶部２１と、受信部２２と、制御部２３ａと、逆関数演算部２３ｂと、第２ビット分割部２３ｃと、第３ハッシュ関数演算部２３ｄと、第３排他的論理和演算部２３ｅと、第４ハッシュ関数演算部２３ｆと、第４排他的論理和演算部２３ｇと、第３ビット分割部２３ｈと、第３ビット結合部２３ｉとを有する。
【００３２】
なお、記憶部２１は、例えば、キャッシュメモリ、レジスタ、ＲＡＭ、若しくは補助記憶装置、又はそれらを結合した記憶領域である。また、受信部２２は、所定のプログラムが読み込まれたＣＰＵの制御のもと駆動するＬＡＮカード、モデム等の通信装置である。さらに、制御部２３ａ、逆関数演算部２３ｂ、第２ビット分割部２３ｃ、第３ハッシュ関数演算部２３ｄ、第３排他的論理和演算部２３ｅ、第４ハッシュ関数演算部２３ｆ、第４排他的論理和演算部２３ｇ、第３ビット分割部２３ｈ及び第３ビット結合部２３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置２０は、制御部２３ａの制御の下、各処理を実行する。
【００３３】
＜処理＞
次に、本形態の処理について説明する。以下では、撹乱過程のラウンド数が偶数の場合の処理、及び、奇数の場合の処理をそれぞれ別個に説明する。しかし、撹乱過程のラウンド数が偶数であるか奇数であるかに応じ、以下の各処理が選択的に実行される構成であってもよい。
【００３４】
［ラウンド数R（R≧4）が偶数である場合］
《暗号化処理》
図４は、ラウンド数R（R≧4）が偶数である場合における暗号化処理を説明するためのフローチャートである。以下、この図に従って説明を行う。
【００３５】
まず、暗号化装置１０（図２）の記憶部１１にn‐zビット（n＞z≧k，kはセキュリティパラメータ）の平文mを格納する（平文格納過程／ステップＳ１）。なお、本形態のnは、暗号化装置１０が使用する一方向性置換関数fの入力域のビット数を意味する。また、キュリティパラメータkの値には特に制限はなく、求められる安全性のレベルに応じて設定すればよい。一般的にはk＞80とすることが望ましい。
【００３６】
次に、暗号化装置１０の乱数生成部１３ｂが、zビットの乱数rを生成し、それを記憶部１１に格納する（乱数格納過程／ステップＳ２）。
【００３７】
次に、暗号化装置１０の第１ビット分割部１３ｃが、記憶部１１から平文mを読み込み、当該平文mを、v‐zビット（n＞v‐z≧2k）の第１平文m1と、n‐vビットの第２平文m2とにビット分割し、第１平文m1と、第２平文m2（=s(0)）とを記憶部１１に格納する（第１ビット分割過程／ステップＳ３）。
【００３８】
なお、n＞z≧kを満たすのであれば、zはどのような値であってもよく、また、n＞v‐z≧2kを満たすのであれば、vはどのような値でもよい。しかし、z=k，v=3kとした場合、安全性を確保しつつオーバーヘッドを最小化できるため、z=k，v=3kとすることが望ましい。
【００３９】
また、平文mを第１平文m1と第２平文m2とにビット分割する際の分割方法にも制限はなく、例えば、平文mの上位v‐zビットを第１平文m1とし、残りのn‐vビットの第２平文m2としてもよいし、平文mの下位v‐zビットを第１平文m1とし、残りのn‐vビットの第２平文m2としてもよい。
【００４０】
次に、暗号化装置１０の第１ビット結合部１３ｄが、記憶部１１から乱数rと第１平文m1とを読み込み、これらのビット結合値r|m1を生成し、当該ビット結合値r|m1をビット列
t(0)=r|m1
として記憶部１１に格納する（第１ビット結合過程／ステップＳ４）。
【００４１】
なお、乱数rと第１平文m1とのビット結合方法にも制限はなく、例えば、乱数rを上位zビットとし、第１平文m1を残りのビットとして結合してもよいし、第１平文m1を上位v‐zビットとし、乱数rを残りのビットとして結合してもよい。
【００４２】
次に、制御部１３ａがi=0と設定し、当該iをレジスタ（図示せず）に保持する（ステップＳ５）。
【００４３】
次に、暗号化装置１０の第１ハッシュ関数演算部１３ｅが、記憶部１１からビット列t(i)を読み込み、当該ビット列t(i)にハッシュ関数H(2・i+1)を作用させてn‐vビットのハッシュ値
h(2・i+1)=H(2・i+1) (t(i))
を算出し、当該ハッシュ値h(2・i+1)を記憶部１１に格納する（第１ハッシュ関数演算過程／ステップＳ６）。なお、本形態のハッシュ関数H(2・i+1)は、
H(2・i+1)：{0,1}v→{0,1}n−v
の入出力域を持つ。また、当該ハッシュ関数H(2・i+1)としては、例えば、SHA-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)を記憶部１１に格納する（第２ハッシュ関数演算過程／ステップＳ８）。なお、本形態のハッシュ関数H(2・i+2)は、
H(2・i+2)：{0,1}n−v→{0,1}v
の入出力域を持つ。また、当該ハッシュ関数H(2・i+2)としては、例えば、SHA-1等を用いることができる。
【００４６】
次に、暗号化装置１０の第２排他的論理和演算部１３ｈが、記憶部１１からビット列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を記憶部１１に格納する（第２ビット結合過程／ステップＳ１２）。
【００４８】
次に、暗号化装置１０の一方向性置換関数演算部１３ｊが、記憶部１１からビット結合値yを読み込み、当該ビット結合値yに対して落とし戸付き一方向性置換関数fを作用させた暗号文
u=f(y)
を算出し、当該暗号文uを暗号化装置の記憶部に格納する（一方向性置換関数演算過程／ステップＳ１３）。なお、落とし戸付き一方向性置換関数fとしては、例えば、因数分解問題の求解困難性に安全性の根拠をおくRSA暗号の暗号化関数や、離散対数問題の求解困難性に安全性の根拠をおくElGamal暗号の暗号化関数等を例示できる（例えば、『岡本龍明，山本博資著、「現代暗号」、産業図書出版、ISBN4-7828-5353-X（参考文献１）』等参照）。
【００４９】
その後、暗号化装置１０の送信部１２が、記憶部１１から読み込まれた暗号文uを復号装置２０に送信する（暗号文送信過程／ステップＳ１４）。
【００５０】
《復号処理》
図５は、ラウンド数R（R≧4）が偶数である場合における復号処理を説明するためのフローチャートである。以下、この図に従って説明を行う。
上述のように送信された暗号文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)(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)(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として抽出する。
【００５８】
次に、復号装置２０の第３ビット結合部２３ｉが、記憶部２１から、第１平文m1とビット列s(0)(=m2)とを読み込み、これらのビット結合値
m=m1 | s(0)
を生成し、当該ビット結合値を復号結果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) (t(i))
を算出し、当該ハッシュ値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を暗号化装置の記憶部に格納し（一方向性置換関数演算過程／ステップＳ１３）、暗号化装置１０の送信部１２が、記憶部１１から読み込まれた暗号文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)(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の場合における撹乱過程を説明するためのフローチャートである。この例では、
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)), s(2)=s(1) (+) h(3), h(4)=H(4) (s(2)), t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)とが出力される。
【００７１】
図８（ｂ）は、ラウンド数R=4の場合における撹乱復元過程を説明するためのフローチャートである。この例では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(t(1)), 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)
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【００７２】
［ラウンド数R=5である場合］
図９（ａ）は、ラウンド数R=5の場合における撹乱過程を説明するためのフローチャートである。この例では、
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)), 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)とが出力される。
【００７３】
図９（ｂ）は、ラウンド数R=5の場合における撹乱復元過程を説明するためのフローチャートである。この例では、
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)), 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)
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【００７４】
＜第１実施形態の特徴＞
本形態では、n‐zビット（n＞z≧k，kはセキュリティパラメータ）の平文mを、v‐zビット（n＞v-z≧2k）の第１平文m1と、n‐vビットの第２平文m2とにビット分割し、zビットの乱数rと第１平文m1とのビット結合値r|m1と、第２平文m2とを入力として撹乱過程を実行することとした。前述のように、ハッシュ関数の出力域との関係ではr|m1のビット数vは2k以上でなければならないが、このビットの一部を第１平文m1とできることにより、従来よりもオーバーヘッドを向上できる。特に、z=k，v=3kとした場合には、オーバーヘッドがkビットとなり、オーバーヘッドを最小化できる。
【００７５】
また、安全性のためには、復号要求によって乱数rが攻撃者に漏えいしないことが重要であるが、ラウンド数Rを４以上とし、乱数rと第１平文m1との結合を攪乱しているため、安全性が確保される。
【００７６】
なお、本発明は上述の実施形態に限定されるわけではなく、暗号化装置１０と復号装置２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【００７７】
〔第２実施形態〕
次に、本発明の第２実施形態について説明する。
本形態は、第１実施形態の変形例であり、(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が所定値以外の値を示す場合には、復号装置の偽装復号結果生成部が、n‐zビットの乱数を生成し、当該乱数を復号結果として出力する点である。
【００７８】
以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
＜全体構成＞
第２実施形態の暗号通信システムは、第１実施形態の暗号化装置１０を暗号化装置１１０に置換し、復号装置２０を復号装置１２０に置換した構成となる。
【００７９】
＜ハードウェア構成＞
第１実施形態と同様であるため説明を省略する。
【００８０】
＜ハードウェアとソフトウェアとの協働＞
第２実施形態の暗号化装置１１０及び復号装置１２０は、それぞれ、前述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【００８１】
図１０は、第２実施形態の暗号化装置１１０の機能構成を例示したブロック図である。また、図１１は、第２実施形態の復号装置１２０の機能構成を例示したブロック図である。なお、図１０及び図１１において第１実施形態と共通する部分には、図２及び図３と同じ符号を付している。
【００８２】
図１０に示すように、第２実施形態の暗号化装置１１０は、第１実施形態の暗号化装置１０の第２ビット結合部１３ｉを第２ビット結合部１１３ｉに置換することによって構成される。なお、第２ビット結合部１１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置１１０は、制御部１３ａの制御の下、各処理を実行する。
【００８３】
また、図１１に示すように、第２実施形態の復号装置１２０は、第１実施形態の復号装置２０の第２ビット分割部２３ｃを第２ビット分割部１２３ｃに置換し、さらに、判定部１２３ｄと偽装復号結果生成部１２３ｅを付加することによって構成される。なお、第２ビット分割部１２３ｃ、判定部１２３ｄ及び偽装復号結果生成部１２３ｅは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置１２０は、制御部２３ａの制御の下、各処理を実行する。
【００８４】
また、本形態では、一例として、落とし戸付き一方向性置換関数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を記憶部１１に格納する（第２ビット結合過程／ステップＳ１１１）。
その後、暗号化装置１１０が第１実施形態と同様に、ステップＳ１３，１４の処理を実行し、暗号文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’でないと判定された場合、偽装復号結果生成部１２３ｅが、n‐zビットの乱数を生成し、当該乱数を復号結果m’として出力する（偽装復号結果生成過程／ステップＳ１２３）。一方、b=b’であると判定された場合、第１実施形態と同様、ラウンド数Ｒが偶数の場合には、ステップＳ２４〜Ｓ３２の処理が実行され、ラウンド数Ｒが奇数の場合には、ステップＳ５１〜Ｓ５４，Ｓ２５〜Ｓ３２の処理が実行され、復号結果mが出力される。
【００９１】
＜第２実施形態の特徴＞
本形態でも、第１実施形態と同様、安全性を確保しつつオーバーヘッドを小さくすることができる。
また、本形態では、ビット結合値yが付加情報bを具備し、復号装置１２０が当該付加情報bを用いて暗号文uの正当性を検証し、暗号文uが正当である場合には第１実施形態と同様に復号処理を行ってn‐zビットの復号結果を出力し、暗号文uが不当である場合にはn-zビットの乱数を復号結果として出力することとした。これにより、暗号文uが不当である場合に復号装置１２０が復号処理を行うことを抑制できる。さらに、暗号文uが不当である場合に正規の復号結果と同じビット数n-zの乱数を復号結果として出力することで、選択暗号文攻撃に有効な情報が攻撃者に漏えいすることを防止できる。
【００９２】
なお、本形態では、落とし戸付き一方向性置換関数fが、0以上N未満（Nは自然数）の値を入力とする関数であり、Ｎのビット長を|N|とし、付加情報bのビット長を|b|とした場合にn=|N|‐|b|を満たし、付加情報bは、0を示すビット又はビット列であり、第２ビット結合過程で生成されるビット結合値yが、付加情報bが先頭にビット結合された値である場合について説明した。しかし、本発明はこれに限定されず、落とし戸付き一方向性置換関数fとして、入力域がnビットのElGamal暗号の暗号化関数等を用いた場合に本形態を適用してもよい。また、付加情報b, b’が0以外の値を示すものであってもよい。
【００９３】
また、暗号化装置１１０と復号装置１２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【００９４】
〔第３実施形態〕
次に、本発明の第３実施形態について説明する。
第３実施形態は、第２実施形態の変形例であり、(1)付加情報bを少なくとも一部のハッシュ関数の入力に含める点、(2)復号装置において付加情報bの検証を行って暗号文の正当性を検証し、暗号文が不当である場合に乱数を復号結果として出力する処理を行わない点が第２実施形態と相違する。以下では、第１，２実施形態との相違点を中心に説明し、これらと共通する事項については説明を省略する。
【００９５】
＜全体構成＞
第３実施形態の暗号通信システムは、第１実施形態の暗号化装置１０を暗号化装置２１０に置換し、復号装置２０を復号装置２２０に置換した構成となる。
【００９６】
＜ハードウェア構成＞
第１実施形態と同様であるため説明を省略する。
【００９７】
＜ハードウェアとソフトウェアとの協働＞
第２実施形態の暗号化装置２１０及び復号装置２２０は、それぞれ、前述のようなハードウェアに所定のプログラムが読み込まれ、ＣＰＵがそれを実行することによって構築される。以下、このように構築される各装置の機能構成を説明する。
【００９８】
図１３は、第３実施形態の暗号化装置２１０の機能構成を例示したブロック図である。また、図１４は、第３実施形態の復号装置２２０の機能構成を例示したブロック図である。なお、図１３及び図１４において第１，２実施形態と共通する部分には、図２，３，１０，１１と同じ符号を付している。
【００９９】
図１３に示すように、第３実施形態の暗号化装置２１０は、第１実施形態の暗号化装置１０の第１ハッシュ関数演算部１３ｅを第１ハッシュ関数演算部２１３ｅに置換し、第２ハッシュ関数演算部１３ｇを第２ハッシュ関数演算部２１３ｇに置換し、第２ビット結合部１３ｉを第２ビット結合部１１３ｉに置換することによって構成される。第１ハッシュ関数演算部２１３ｅ、第２ハッシュ関数演算部２１３ｇ、及び第２ビット結合部１１３ｉは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、暗号化装置２１０は、制御部１３ａの制御の下、各処理を実行する。
【０１００】
また、図１４に示すように、第３実施形態の復号装置２２０は、第１実施形態の復号装置２０の第２ビット分割部２３ｃを第２ビット分割部１２３ｃに置換し、第３ハッシュ関数演算部２３ｄを第３ハッシュ関数演算部２２３ｄに置換し、第４ハッシュ関数演算部２３ｆを第４ハッシュ関数演算部２２３ｆに置換することによって構成される。なお、第２ビット分割部１２３ｃ、第３ハッシュ関数演算部２２３ｄ及び第４ハッシュ関数演算部２２３ｆは、例えば、所定のプログラムがＣＰＵに読み込まれ、実行されることによって構築される演算部である。また、復号装置２２０は、制御部２３ａの制御の下、各処理を実行する。
【０１０１】
また、第１実施形態では、全てのiについて、ハッシュ関数H(2・i+1)が{0,1}v→{0,1}n−vの入出力域を持ち、ハッシュ関数H(2・i+2)が{0,1}n−v→{0,1}vの入出力域を持つこととしたが、本形態では、少なくとも一部のiに対応するハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、
H(2・i+1)：{0,1}v+|b|→{0,1}n−v  …(1)
H(2・i+2)：{0,1}n−v+|b|→{0,1}v  …(2)
の入出力域を持ち、その他のiに対応するハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、
H(2・i+1)：{0,1}v→{0,1}n−v  …(3)
H(2・i+2)：{0,1}n−v→{0,1}v  …(4)
の入出力域を持つ。なお、上述したように付加情報bのビット長|b|に制限はないが、オーバーヘッドをできるだけ小さくするという観点から|b|=1であることが望ましい。
【０１０２】
また、各ハッシュ関数H(2・i+1)を式(1)(3)いずれの関数にするか、及び、各ハッシュ関数H(2・i+1)を式(2)(4)いずれの関数にするかについても特に制限はない。しかし、安全性の観点からは、ラウンド数Rが偶数である場合には、少なくとも何れかのi≧1に対応するハッシュ関数H(2・i+1)を式(1)の関数とするか、或いは、少なくとも何れかのi≦(R/2)‐2に対応するハッシュ関数H(2・i+2)を式(2)の関数とすることが望ましい。また、ラウンド数Rが奇数である場合には、少なくとも何れかのiに対応するハッシュ関数H(2・i+2)を式(2)の関数とする。すなわち、最初のラウンド及び最後のラウンド以外のハッシュ関数のうち、少なくとも一部を式(1)(2) のいずれかにすることが望ましい。また、安全性の観点からより好ましくは、全てのハッシュ関数を式(1)(2)のいずれかにすることが望ましい。
【０１０３】
また、前処理において、式(1)(2)のハッシュ関数を用いるラウンドを特定する情報Rbが記憶部１１，２１にそれぞれ格納され、各装置の制御部１３ａ，２３ａは、この情報Rbを用い、各ハッシュ関数を特定する。また、Rbが事前にプログラムに記述されている構成であってもよい。
【０１０４】
＜処理＞
《暗号化処理》
第１実施形態との相違点は、(1)暗号化装置２１０が、ステップＳ１２又はＳ４６の代わりに、第２実施形態で説明したステップＳ１１１の処理を実行し、ビット結合値
y=b|t(R/2)|s(R/2)  (Rが偶数の場合)
y=b|t((R‐1)/2)|s(((R‐1)/2)+1) (Rが奇数の場合)
を生成する点、(2)撹乱過程で、第１ハッシュ関数演算部２１３ｅ及び／又は第２ハッシュ関数演算部２１３ｇでそれぞれ算出される、少なくとも一部のiに対応する（2・i+1=Rb及び／又は2・i+2=Rbである）ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、付加情報bとビット列t(i)とのビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値
h(2・i+1)= H(2・i+1)(b|t(i)) …(5)
及び／又は付加情報bとビット列s(i+1)とのビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値
h(2・i+2)= H(2・i+2)(b|s(i+1)) …(6)
であり、その他のハッシュ値が第１，２実施形態と同様である点である。
【０１０５】
なお、式(5),(6)を算出するためのハッシュ関数H(2・i+1)，H(2・i+2)は、上述の式(1)(2)の関数であり、その他のハッシュ関数H(2・i+1)，H(2・i+2)は、上述の式(3)(4)の関数である。
【０１０６】
《復号処理》
第１実施形態との相違点は、(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に対応する（2・i+1=Rb及び／又は2・i+2=Rbである）ハッシュ値h(2・i+1)及び／又はハッシュ値h(2・i+2)が、付加情報bとビット列t(i)とのビット結合値にハッシュ関数H(2・i+1)を作用させたハッシュ値
h(2・i+1)= H(2・i+1)(b|t(i)) …(5)
及び／又は付加情報bとビット列s(i+1)とのビット結合値にハッシュ関数H(2・i+2)を作用させたハッシュ値
h(2・i+2)= H(2・i+2)(b|s(i+1)) …(6)
であり、その他のハッシュ値が第１，２実施形態と同様である点である。
【０１０７】
＜撹乱過程・撹乱復元過程の具体例＞
次に、本形態の撹乱過程・撹乱復元過程の具体例を説明する。
図１５（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の一例を説明するための図であり、図１５（ｂ）は、その撹乱復元過程を説明するための図である。
【０１０８】
この例の撹乱過程では、
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)(b|t(1)), s(2)=s(1) (+) h(3), h(4)=H(4) (s(2)),t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)とが出力される。
【０１０９】
また、この例の撹乱復元過程では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(b|t(1)), 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)
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【０１１０】
図１６（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の他の例を説明するための図であり、図１６（ｂ）は、その撹乱復元過程を説明するための図である。
【０１１１】
この例の撹乱過程では、
i=0: h(1)=H(1)(t(0)), s(1)=s(0) (+) h(1), h(2)=H(2) (b|s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(b|t(1)), s(2)=s(1) (+) h(3), h(4)=H(4) (s(2)),t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)とが出力される。
【０１１２】
また、この例の撹乱復元過程では、
i=1: h(4)=H(4)(s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(b|t(1)), s(1)=s(2)(+) h(3)
i=0: h(2)=H(2)(b|s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(t(0)), s(0)=s(1) (+) h(1)
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【０１１３】
図１７（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の他の例を説明するための図であり、図１７（ｂ）は、その撹乱復元過程を説明するための図である。
【０１１４】
この例の撹乱過程では、
i=0: h(1)=H(1)(b|t(0)), s(1)=s(0) (+) h(1), h(2)=H(2) (b|s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(b|t(1)), s(2)=s(1) (+) h(3), h(4)=H(4) (b|s(2)),t(2) =t(1) (+) h(4)
が実行され、ビット列t(2)とビット列s(2)とが出力される。
【０１１５】
また、この例の撹乱復元過程では、
i=1: h(4)=H(4)(b|s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(b|t(1)), s(1)=s(2)(+) h(3)
i=0: h(2)=H(2)(b|s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(b|t(0)), s(0)=s(1)(+) h(1) 
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【０１１６】
図１８（ａ）は、第３実施形態におけるR=5の場合の撹乱過程の一例を説明するための図であり、図１８（ｂ）は、その撹乱復元過程を説明するための図である。
【０１１７】
この例の撹乱過程では、この例では、
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)(b|t(1)), 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)とが出力される。
【０１１８】
また、この例の撹乱復元過程では、
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)(b|t(1)), 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)
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【０１１９】
図１９（ａ）は、第３実施形態におけるR=5の場合の撹乱過程の他の例を説明するための図であり、図１９（ｂ）は、その撹乱復元過程を説明するための図である。
【０１２０】
この例の撹乱過程では、この例では、
i=0: h(1)=H(1)(b|t(0)), s(1)=s(0) (+) h(1), h(2)=H(2) (b|s(1)), t(1) =t(0) (+) h(2)
i=1: h(3)=H(3)(b|t(1)), s(2)=s(1) (+) h(3), h(4)=H(4)(b|s(2)),t(2) =t(1) (+) h(4)
i=2: h(5)=H(5)(b|t(2)), s(3)=s(2) (+) h(5)
が実行され、ビット列t(2)とビット列s(3)とが出力される。
【０１２１】
また、この例の撹乱復元過程では、
i=2: h(5)= H(5)(b|t(2)), s(2)=s(3)(+) h(5)
i=1: h(4)=H(4)(b|s(2)), t(1)=t(2) (+) h(4), h(3)= H(3)(b|t(1)), s(1)=s(2)(+) h(3)
i=0: h(2)=H(2)(b|s(1)), t(0)=t(1) (+) h(2), h(1)= H(1)(b|t(0)), s(0)=s(1)(+) h(1) 
が実行され、ビット列t(0)とビット列s(0)とが出力される。
【０１２２】
＜第３実施形態の特徴＞
本形態でも、第１実施形態で説明したのと同様、安全性を確保しつつオーバーヘッドを小さくすることができる。また、本形態では、ビット結合値yが付加情報bを具備し、この付加情報bを少なくとも一部のハッシュ関数の入力値に含めることとしたため、安全性がより向上する。さらに、そのために第２実施形態のように復号時に付加情報bの値を検証したり、乱数を復号結果として生成する必要もない。
また、暗号化装置２１０と復号装置２２０との間で整合が採れるのであれば、ビット結合される何れかの情報にさらに他の情報をビット結合してもよい。
【０１２３】
〔その他の変形等〕
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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の場合における撹乱過程を説明するためのフローチャートである。図８（ｂ）は、ラウンド数R=4の場合における撹乱復元過程を説明するためのフローチャートである。
【図９】図９（ａ）は、ラウンド数R=5の場合における撹乱過程を説明するためのフローチャートである。図９（ｂ）は、ラウンド数R=5の場合における撹乱復元過程を説明するためのフローチャートである。
【図１０】図１０は、第２実施形態の暗号化装置の機能構成を例示したブロック図である。
【図１１】図１１は、第２実施形態の復号装置の機能構成を例示したブロック図である。
【図１２】図１２（ａ）は、第２実施形態の暗号化処理を説明するためのフローチャートである。図１２（ｂ）は、第２実施形態の復号処理を説明するためのフローチャートである。
【図１３】図１３は、第３実施形態の暗号化装置の機能構成を例示したブロック図である。
【図１４】図１４は、第３実施形態の復号装置の機能構成を例示したブロック図である。
【図１５】図１５（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の一例を説明するための図であり、図１５（ｂ）は、その撹乱復元過程を説明するための図である。
【図１６】図１６（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の他の例を説明するための図であり、図１６（ｂ）は、その撹乱復元過程を説明するための図である。
【図１７】図１７（ａ）は、第３実施形態におけるR=4の場合の撹乱過程の他の例を説明するための図であり、図１７（ｂ）は、その撹乱復元過程を説明するための図である。
【図１８】図１８（ａ）は、第３実施形態におけるR=5の場合の撹乱過程の一例を説明するための図であり、図１８（ｂ）は、その撹乱復元過程を説明するための図である。
【図１９】図１９（ａ）は、第３実施形態におけるR=5の場合の撹乱過程の他の例を説明するための図であり、図１９（ｂ）は、その撹乱復元過程を説明するための図である。
【図２０】図２０（ａ）は、従来のOAEP 3-roundパディング関数pdの処理を説明するための図であり、図２０（ｂ）は、その逆関数pd-1の処理を説明するための図である。
【符号の説明】
【０１３０】
１０，１１０，２１０  暗号化装置
２０，１２０，２２０  復号装置
【図１】
0005032955.tif 000002
【図２】
0005032955.tif 000003
【図３】
0005032955.tif 000004
【図４】
0005032955.tif 000005
【図５】
0005032955.tif 000006
【図６】
0005032955.tif 000007
【図７】
0005032955.tif 000008
【図８】
0005032955.tif 000009
【図９】
0005032955.tif 000010
【図１０】
0005032955.tif 000011
【図１１】
0005032955.tif 000012
【図１２】
0005032955.tif 000013
【図１３】
0005032955.tif 000014
【図１４】
0005032955.tif 000015
【図１５】
0005032955.tif 000016
【図１６】
0005032955.tif 000017
【図１７】
0005032955.tif 000018
【図１８】
0005032955.tif 000019
【図１９】
0005032955.tif 000020
【図２０】
0005032955.tif 000021