(57)【特許請求の範囲】
【請求項１】
公開鍵の一部であり、且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、
前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データが記憶された形式データ記憶手段と、
【数１】
0004664850.tif 000030
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定手段と、
前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λx(t)を生成する第１の多項式生成手段と、
前記１変数多項式λx(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λy(t)を生成する第２の多項式生成手段と、
前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第３の多項式生成手段と、
前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第４の多項式生成手段と、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成手段と、
前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(1,0)）をランダムに生成する第５の多項式生成手段と、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c10(t)を生成する第６の多項式生成手段と、
【数２】
0004664850.tif 000031
前記各１変数多項式ｕx(t), ｕy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成手段と、
【数３】
0004664850.tif 000032
前記各１変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成手段と
を備えたことを特徴とする鍵生成装置。
【請求項２】
公開鍵の一部であり、且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、
前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データが記憶された形式データ記憶手段と、
【数４】
0004664850.tif 000033
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む,  各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定手段と、
前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λy(t)を生成する第１の多項式生成手段と、
前記１変数多項式λy(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λx(t)を生成する第２の多項式生成手段と、
前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第３の多項式生成手段と、
前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第４の多項式生成手段と、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成手段と、
前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(0,1)）をランダムに生成する第５の多項式生成手段と、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c01(t)を生成する第６の多項式生成手段と、
【数５】
0004664850.tif 000034
前記各１変数多項式ｕx(t), ｕy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成手段と、
【数６】
0004664850.tif 000035
前記各１変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成手段と
を備えたことを特徴とする鍵生成装置。
【請求項３】
請求項１又は請求項２に記載の鍵生成装置において、
前記素数ｐ、前記拡大次数r 及び前記次数d を含むパラメータを入力するためのパラメータ入力手段と、
このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項４】
請求項１乃至請求項３のいずれか１項に記載の鍵生成装置において、
前記生成されたファイブレーションＸ(x, y, t)における各々の変数x, y, t の次数degx Ｘ(x, y, t), degy Ｘ(x, y, t), degt Ｘ(x, y, t)及び前記次数d に基づいて、(deg x Ｘ(x, y, t)＋degy Ｘ(x, y, t))d＋degt Ｘ(x, y, t) 以上となるように、暗号化用のランダム１変数多項式の最小次数lを定めるランダム１変数多項式最小次数決定手段を更に備えたことを特徴とする鍵生成装置。
【請求項５】
請求項１乃至請求項４のいずれか１項に記載の鍵生成装置であって、
前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算手段と、
前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定手段と、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記形式データ決定手段から前記種数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項６】
請求項１乃至請求項４のいずれか１項に記載の鍵生成装置であって、
前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定手段と、
この判定の結果、総次数dcが４未満のとき、前記形式データ決定手段から前記総次数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項７】
請求項１乃至請求項４のいずれか１項に記載の鍵生成装置において、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算手段と、
前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定手段と、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段と、
前記再選択した形式データについて前記種数計算手段から前記種数判定手段までの処理を実行するように、当該再選択した形式データを前記種数計算手段に送出する送出手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項８】
請求項１乃至請求項４のいずれか１項に記載の鍵生成装置において、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定手段と、
この判定の結果、総次数dcが４未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段と、
前記再選択した形式データについて前記総次数判定手段の処理を実行するように、当該再選択した形式データを前記総次数判定手段に送出する送出手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項９】
公開鍵の一部であり、且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置のプログラムであって、
前記鍵生成装置のコンピュータを、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段、
前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データが記憶された形式データ記憶手段、
【数７】
0004664850.tif 000036
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定手段、
前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λx(t)を生成する第１の多項式生成手段、
前記１変数多項式λx(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λy(t)を生成する第２の多項式生成手段、
前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第３の多項式生成手段、
前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第４の多項式生成手段、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成手段、
前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(1,0)）をランダムに生成する第５の多項式生成手段、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c10(t)を生成する第６の多項式生成手段、
【数８】
0004664850.tif 000037
前記各１変数多項式ｕx(t), ｕy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成手段、
【数９】
0004664850.tif 000038
前記各１変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成手段、
として機能させるためのプログラム。
【請求項１０】
公開鍵の一部であり、且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置のプログラムであって、
前記鍵生成装置のコンピュータを、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段、
前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データが記憶された形式データ記憶手段、
【数１０】
0004664850.tif 000039
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定手段、
前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λy(t)を生成する第１の多項式生成手段、
前記１変数多項式λy(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λx(t)を生成する第２の多項式生成手段、
前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第３の多項式生成手段、
前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第４の多項式生成手段、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成手段、
前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(0,1)）をランダムに生成する第５の多項式生成手段、
前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c01(t)を生成する第６の多項式生成手段、
【数１１】
0004664850.tif 000040
前記各１変数多項式ｕx(t), ｕy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成手段、
【数１２】
0004664850.tif 000041
前記各１変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成手段、
として機能させるためのプログラム。
【請求項１１】
請求項９又は請求項１０に記載のプログラムにおいて、
前記鍵生成装置のコンピュータを、
前記素数ｐ、前記拡大次数r 及び前記次数d を含むパラメータを入力するためのパラメータ入力手段、
このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込手段、
として機能させるためのプログラム。
【請求項１２】
請求項９乃至請求項１１のいずれか１項に記載のプログラムにおいて、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションＸ(x, y, t)における各々の変数x, y, t の次数degx Ｘ(x, y, t), degy Ｘ(x, y, t), degt Ｘ(x, y, t)及び前記次数d に基づいて、(deg x Ｘ(x, y, t)＋degy Ｘ(x, y, t))d＋degt Ｘ(x, y, t) 以上となるように、暗号化用のランダム１変数多項式の最小次数lを定めるランダム１変数多項式最小次数決定手段、として更に機能させるためのプログラム。
【請求項１３】
請求項９乃至請求項１２のいずれか１項に記載のプログラムであって、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算手段、
前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定手段、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記形式データ決定手段から前記種数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段、
として更に機能させるためのプログラム。
【請求項１４】
請求項９乃至請求項１２のいずれか１項に記載のプログラムであって、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定手段、
この判定の結果、総次数dcが４未満のとき、前記形式データ決定手段から前記総次数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段、
として更に機能させるためのプログラム。
【請求項１５】
請求項９乃至請求項１２のいずれか１項に記載のプログラムにおいて、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算手段、
前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定手段、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段、
前記再選択した形式データについて前記種数計算手段から前記種数判定手段までの処理を実行するように、当該再選択した形式データを前記種数計算手段に送出する送出手段、
を更に備えたプログラム。
【請求項１６】
請求項９乃至請求項１２のいずれか１項に記載のプログラムにおいて、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定手段、
この判定の結果、総次数dcが４未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段、
前記再選択した形式データについて前記総次数判定手段の処理を実行するように、当該再選択した形式データを前記総次数判定手段に送出する送出手段、
を更に備えたプログラム。
【請求項１７】
パラメータ記憶手段、形式データ記憶手段、形式データ決定手段、第１の多項式生成手段、第２の多項式生成手段、第３の多項式生成手段、第４の多項式生成手段、セクション生成手段、第５の多項式生成手段、第６の多項式生成手段、第７の多項式生成手段及びファイブレーション生成手段を有し、公開鍵の一部であり且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置が実行する鍵生成方法であって、
前記パラメータ記憶手段が、前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータを記憶するパラメータ記憶工程と、
前記形式データ記憶手段が、前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データを予め記憶する形式データ記憶工程と、
【数１３】
0004664850.tif 000042
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ決定手段が、前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定工程と、
前記第１の多項式生成手段が、前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λx(t)を生成する第１の多項式生成工程と、
前記第２の多項式生成手段が、前記１変数多項式λx(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λy(t)を生成する第２の多項式生成工程と、
前記第３の多項式生成手段が、前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第３の多項式生成工程と、
前記第４の多項式生成手段が、前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第４の多項式生成工程と、
前記セクション生成手段が、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成工程と、
前記第５の多項式生成手段が、前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(1,0)）をランダムに生成する第５の多項式生成工程と、
前記第６の多項式生成手段が、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c10(t)を生成する第６の多項式生成工程と、
【数１４】
0004664850.tif 000043
前記第７の多項式生成手段が、前記各１変数多項式ｕx(t), ｕy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成工程と、
【数１５】
0004664850.tif 000044
前記ファイブレーション生成手段が、前記各１変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成工程と
を備えたことを特徴とする鍵生成方法。
【請求項１８】
パラメータ記憶手段、形式データ記憶手段、形式データ決定手段、第１の多項式生成手段、第２の多項式生成手段、第３の多項式生成手段、第４の多項式生成手段、セクション生成手段、第５の多項式生成手段、第６の多項式生成手段、第７の多項式生成手段及びファイブレーション生成手段を有し、公開鍵の一部であり且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置が実行する鍵生成方法であって、
前記パラメータ記憶手段が、前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータを記憶するパラメータ記憶工程と、
前記形式データ記憶手段が、前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データを予め記憶する形式データ記憶工程と、
【数１６】
0004664850.tif 000045
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む,  各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ決定手段が、前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定工程と、
前記第１の多項式生成手段が、前記次数d 未満の，Ｆq上定義されたランダムな１変数多項式λy(t)を生成する第１の多項式生成工程と、
前記第２の多項式生成手段が、前記１変数多項式λy(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λx(t)を生成する第２の多項式生成工程と、
前記第３の多項式生成手段が、前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第３の多項式生成工程と、
前記第４の多項式生成手段が、前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第４の多項式生成工程と、
前記セクション生成手段が、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成工程と、
前記第５の多項式生成手段が、前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(0,1)）をランダムに生成する第５の多項式生成工程と、
前記第６の多項式生成手段が、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c01(t)を生成する第６の多項式生成工程と、
【数１７】
0004664850.tif 000046
前記第７の多項式生成手段が、前記各１変数多項式ｕx(t), ｕy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成工程と、
【数１８】
0004664850.tif 000047
前記ファイブレーション生成手段が、前記各１変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成工程と
を備えたことを特徴とする鍵生成方法。
【請求項１９】
請求項１７又は請求項１８に記載の鍵生成方法において、
前記鍵生成装置は、パラメータ入力手段及びパラメータ書込手段を更に備え、
前記パラメータ入力手段が、前記素数ｐ、前記拡大次数r 及び前記次数d を含むパラメータを入力するパラメータ入力工程と、
前記パラメータ書込手段が、このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項２０】
請求項１７乃至請求項１９のいずれか１項に記載の鍵生成方法において、
前記鍵生成装置は、ランダム１変数多項式最小次数決定手段を更に備え、
前記ランダム１変数多項式最小次数決定手段が、前記生成されたファイブレーションＸ(x, y, t)における各々の変数x, y, t の次数degx Ｘ(x, y, t), degy Ｘ(x, y, t), degt Ｘ(x, y, t)及び前記次数d に基づいて、(degx Ｘ(x, y, t)＋degy Ｘ(x, y, t))d＋degt Ｘ(x, y, t) 以上となるように、暗号化用のランダム１変数多項式の最小次数lを定めるランダム１変数多項式最小次数決定工程を更に備えたことを特徴とする鍵生成方法。
【請求項２１】
請求項１７乃至請求項２０のいずれか１項に記載の鍵生成方法であって、
前記鍵生成装置は、種数計算手段、種数判定手段及び制御手段を更に備え、
前記種数計算手段が、前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算工程と、
前記種数判定手段が、前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定工程と、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記制御手段が、前記形式データ決定工程から前記種数判定工程までの処理を再実行するように、前記形式データ決定手段を制御する制御工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項２２】
請求項１７乃至請求項２０のいずれか１項に記載の鍵生成方法であって、
前記鍵生成装置は、総次数判定手段及び制御手段を更に備え、
前記総次数判定手段が、前記生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定工程と、
この判定の結果、総次数dcが４未満のとき、前記制御手段が、前記形式データ決定工程から前記総次数判定工程までの処理を再実行するように、前記形式データ決定工程を制御する制御工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項２３】
請求項１７乃至請求項２０のいずれか１項に記載の鍵生成方法において、
前記鍵生成装置は、種数計算手段、種数判定手段、再選択手段及び送出手段を更に備え、
前記形式データ決定工程は、
前記種数計算手段が、前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆp(t)上の代数曲線Ｃ(x, y)とみなしたときの種数ｇ（Ｃ）を計算する種数計算工程と、
前記種数判定手段が、前記計算された種数ｇ（Ｃ）が２未満であるか否かを判定する種数判定工程と、
この判定の結果、種数ｇ（Ｃ）が２未満のとき、前記再選択手段が、前記選択した形式データとは異なる形式データを再選択する再選択工程と、
前記送出手段が、前記再選択した形式データについて前記種数計算工程から前記種数判定工程までの処理を実行するように、当該再選択した形式データを前記種数計算工程に送出する送出工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項２４】
請求項１７乃至請求項２０のいずれか１項に記載の鍵生成方法において、
前記鍵生成装置は、総次数判定手段、再選択手段及び送出手段を更に備え、
前記形式データ決定工程は、
前記総次数判定手段が、前記選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)が４未満か否かを判定する総次数判定工程と、
この判定の結果、総次数dcが４未満のとき、前記再選択手段が、前記選択した形式データとは異なる形式データを再選択する再選択工程と、
前記送出手段が、前記再選択した形式データについて前記総次数判定工程の処理を実行するように、当該再選択した形式データを前記総次数判定工程に送出する送出工程と
を更に備えたことを特徴とする鍵生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、代数曲面を用いた公開鍵暗号の鍵生成装置、プログラム及び方法に係わり、例えば、代数曲面を用いた公開鍵暗号の鍵の安全性を向上し得る鍵生成装置、プログラム及び方法に関する。
【背景技術】
【０００２】
ネットワーク社会では、電子メール等の多くの情報がネットワーク上に伝送されることにより、人々のコミュニケーションが行われる。このようなネットワーク社会において、公開鍵暗号は情報の機密性や真正性を守る技術として広く活用されている。
【０００３】
代表的な公開鍵暗号には、ＲＳＡ暗号と楕円曲線暗号がある。ＲＳＡ暗号は、素因数分解問題の困難性を安全性の根拠としており、べき乗剰余演算を暗号化演算として用いている。楕円曲線暗号は、楕円曲線上の離散対数問題の困難性を安全性の根拠としており、楕円曲線上の点演算を暗号化演算に用いている。
【０００４】
これらの公開鍵暗号は、特定の鍵（公開鍵）に関する解読法が提案されている一方、一般的な解読法が知られていない。しかしながら、ＲＳＡ暗号と楕円曲線暗号は、いずれも量子計算機が出現すれば解読される可能性が高い。
【０００５】
量子計算機は、現在の計算機とは異なり、量子力学におけるエンタングルメントという物理現象を利用して超並列計算を実行可能な計算機である。量子計算機は、実験レベルの仮想の計算機であり、実現に向けて研究開発が進められている。１９９４年にショア（Shor）は、量子計算機によれば、素因数分解や離散対数問題を効率的に解くアルゴリズムを構成できることを示した。
【０００６】
これに対し、量子計算機が実現されても安全な公開鍵暗号が提案されてきている。一例として、量子公開鍵暗号が挙げられる。量子公開鍵暗号においては、現在の計算機では鍵生成が不可能な程に強力なナップサック暗号の鍵を量子計算機により生成する。しかし、量子公開鍵暗号は、現在の計算機では鍵生成が不可能なため、現時点では利用できない。
【０００７】
一般に、安全な公開鍵暗号を提案する場合、予め素因数分解問題や離散対数問題などの計算困難な問題を見つける。次に、秘密鍵を知らずに暗号文を解読することを、当該計算困難な問題を解くことと等価になるように構成する。
【０００８】
しかし、計算困難な問題を見つけても、その問題を安全性の根拠とする公開鍵暗号を容易に構成できる訳ではない。理由は、計算が困難すぎる問題の場合、鍵を生成する問題も困難になるので、鍵を生成できないためである。一方、鍵生成が可能な程度に容易な問題の場合、解読も容易になってしまう。
【０００９】
従って、公開鍵暗号を構成するには、計算困難な問題を見つけると共に、この問題を、鍵生成が容易であるが、解読が容易でない問題に作り変える必要がある。現状は、この作り変えが困難なため、数えるほどの公開鍵暗号しか提案されていない。
【００１０】
このような現状において、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であると共に、小電力環境での実現可能性がある公開鍵暗号方式として、代数曲面を用いた公開鍵暗号が本発明者により提案されている（例えば、特許文献１参照）。以下、代数曲面を用いた公開鍵暗号を代数曲面暗号とも呼ぶ。
【００１１】
一方、公開鍵暗号の鍵の安全性を向上させるためには、生成される鍵のクラスに制限が無いことが望ましい。理由は、制限されたクラスに依存する鍵の性質又は特殊性に基づく解読法が将来見つかる可能性があるからである。
【特許文献１】特開２００５−３３１６５６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明者の検討によれば、特許文献１記載の代数曲面暗号においても、解読法が将来見つかる可能性が存在する。例えば、特許文献１の第５８〜第５９段落では、２つのセクションＤ1，Ｄ2に対応して生成可能な代数曲面ＸのファイブレーションＸ(x, y, t)として、楕円曲面Ｅt：y2＋y＝x3＋a(t)x＋b(t)が例に挙げられている。この楕円曲面Ｅtは、本発明者によれば、次式に示すファイブレーションＸ(x, y, t)の一例である。
【数１９】
0004664850.tif 000002
【００１３】
しかしながら、この式には、cijxiyjの項が含まれていないことから、生成される公開鍵（代数曲面ＸのファイブレーションＸ(x, y, t)）のクラスに制限が生じると考えられる。なお、この考えは、特許文献１の第６０段落にも同様の記載がある。いずれにしても、生成される公開鍵のクラスに制限があるため、制限されたクラスに基づく解読法が将来見つかる可能性を否定できない。
【００１４】
従って、特許文献１記載の技術においては、制限されたクラスに基づく解読法を阻止する観点から、秘密鍵が２つのセクションである場合にも、生成される公開鍵のクラスの制限を除去することが望ましいと考えられる。
【００１５】
本発明は上記実情を考慮してなされたもので、秘密鍵が２つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止し得る鍵生成装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
第１の発明は、公開鍵の一部であり、且つ有限体Ｆq（但しｑ＝ｐr（ｐは素数、ｒは拡大次数））上定義された代数曲面ＸのファイブレーションＸ(x, y, t)＝0 と、前記ファイブレーションＸ(x, y, t)＝0に対応する２つのセクションＤ1,Ｄ2である秘密鍵とを生成するための鍵生成装置であって、前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数ｐ及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、前記ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表す複数の形式データが記憶された形式データ記憶手段と、  
【数２０】
0004664850.tif 000003
【００１７】
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションＸ(x, y, t)の形式データを決定する形式データ決定手段と、前記次数d 以下の，Ｆq上定義されたランダムな１変数多項式λx(t)を生成する第１の多項式生成手段と、前記１変数多項式λx(t)で割り切れる次数d 以下の，Ｆq上定義された１変数多項式λy(t)を生成する第２の多項式生成手段と、前記１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕx(t), ｖx(t)を生成する第３の多項式生成手段と、前記１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の，Ｆq上定義された２つの１変数多項式ｕy(t), ｖy(t)を生成する第４の多項式生成手段と、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、前記２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成するセクション生成手段と、前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である，Ｆq上定義された１変数多項式cij(t)（但し(i,j)≠(0,0),(1,0)）をランダムに生成する第５の多項式生成手段と、前記各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、下記式に示す一次の項の係数である，Ｆq上定義された１変数多項式c10(t)を生成する第６の多項式生成手段と、  
【数２１】
0004664850.tif 000004
【００１８】
前記各１変数多項式ｕx(t), ｕy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である，Ｆq上定義された１変数多項式c00(t)を生成する第７の多項式生成手段と、  
【数２２】
0004664850.tif 000005
【００１９】
前記各１変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面ＸのファイブレーションＸ(x, y, t)を生成するファイブレーション生成手段とを備えた鍵生成装置である。
【００２０】
第２の発明は、第１の発明における一次の項c10(t)x に代えて一次の項c01(t)y を用いるように、第１の発明を変形した鍵生成装置である。
【００２１】
なお、第１及び第２の発明は、装置として実現した場合を説明したが、これに限らず、プログラム、方法又はコンピュータ読み取り可能な記憶媒体、として実現してもよいことは言うまでもない。
【００２２】
（作用）
第１及び第２の発明においては、公開鍵の一部であるファイブレーションＸ(x, y, t)を生成する際に、ファイブレーションＸ(x, y, t)の形式にcijxiyjの項を含めた構成により、生成される公開鍵のクラスの制限を除去することができる。
【００２３】
ここで、cijxiyjの項を含めた構成を実現させるため、cijxiyjの項を、一次の項及び定数項c00以外の項としている。そして始めに、cijxiyjの項をランダムに生成する。続いて、cijxiyjの項と、２つのセクション内の１変数多項式とに基づいて一次の項の係数を生成する。最後に、cijxiyjの項と一次の項とに基づいて定数項c00を生成している。
【００２４】
このような構成により、第１及び第２の発明においては、秘密鍵が２つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止することができる。
【発明の効果】
【００２５】
以上説明したように本発明によれば、２つのセクションに対応して生成されるファイブレーションのクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の各実施形態を図面を用いて説明する。その前に、各実施形態の前提として、代数曲面及び代数曲面上の求因子問題について述べる。
【００２７】
本発明で述べる代数曲面は、体Ｋ上定義された連立(代数)方程式の解の集合のうち、２次元の自由度を持ったものと定義される。例えば、次の式(1)に示す体Ｋ上の連立方程式は、変数５つに対し、それらを束縛する３つの方程式があり、２次元の自由度を持っているので、代数曲面となる。
【００２８】
ｆ1(x, y, z, v, w)
ｆ2(x, y, z, v, w)
ｆ3(x, y, z, v, w)            (1)
特に、式(2)に示す如き、３変数のＫ上の代数方程式の解の集合として定義される空間もＫ上の代数曲面となる。
【００２９】
ｆ(x, y, z)＝0      (2)
一方、代数曲線は、体Ｋ上定義された連立(代数)方程式の解の集合のうち、１次元の自由度を持ったものである。よって、例えば次式のように定義される。
【００３０】
g(x, y)＝0
本実施形態においては、式(2)のように１つの式で書ける代数曲面のみを扱うので、以下では式(2)を代数曲面の定義方程式のごとく扱う。
【００３１】
体とは加減乗除が自由にできる集合であって、実数、有理数、複素数が該当するが、整数や行列など０以外に除算ができない元を含む集合は該当しない。
【００３２】
体の中には有限体と呼ばれる有限個の元から構成される体がある。例えば素数pに対し、pを法とする剰余類Ｚ/pＺは体をなす。このような体は、素体と呼ばれ、Ｆpなどと書かれる。
【００３３】
有限体にはこの他に素数の冪乗個の元を持つ体Ｆq(q＝pr)がある。pは有限体Ｆqの標数、rは拡大次数と呼ばれる。但し、本実施形態では、有限体のうち、主に素体Ｆpのみを扱う。一般に、素体Ｆpのpは、素体Ｆpの標数と呼ばれる。
【００３４】
一方、一般の有限体でも本発明は自明な変形を施すことによって同様に成立する。公開鍵暗号では、メッセージをデジタルデータとして埋め込む必要から有限体上で構成することが多い。このため、本実施形態においても同様に有限体（本実施形態では特に素体）Ｆp上で定義された代数曲面を扱う。
【００３５】
代数曲面ｆ(x, y, z)＝0 上には、図１に示すように、通常、代数曲線Ｄ1，Ｄ2，Ｘt0，…が複数存在する。このような代数曲線は代数曲面上の因子と呼ばれる。一般に、代数曲面の定義式が与えられた時に（非自明な）因子を求める問題は、現代の数学においても未解決の難問であり、ＮＰ問題である多次多変数方程式の求解問題を解くか、総当りなどの原始的な方法を除けば一般的な解法は知られていない。特に、本実施形態では、有限体で定義された代数曲面を扱う。しかし、有限体で定義された代数曲面の場合、有理数体などの無限体（無限個の元からなる体）と比較して、因子を求めるための手掛かりが少ない。このため、有限体で定義された代数曲面上の因子を求める問題は、より難しい問題である。
【００３６】
本実施形態では、この問題を代数曲面上の求因子問題もしくは単に求因子問題と呼び、代数曲面上の求因子問題に安全性の根拠をおく公開鍵暗号を構成する。
【００３７】
さて、体Ｋ上の代数曲面Ｘ：ｆ(x, y, z)＝0のうち
h(x, y, t)＝0
と定義され、セクションと呼ばれるx, yがtでパラメタライズされた曲線
(x, y, t)＝(ｕx(t), ｕy(t), t)
が存在する形式の代数曲面を代数曲面Ｘのファイブレーションといい、Ｘtなどと表す。なお、以下では簡単のため、ファイブレーションであることが明らかであるときには単なるＸと表す。
【００３８】
また、代数曲面Ｘのファイブレーションにおけるパラメータtに体Kの元t0を代入して得られる代数曲線は、ファイバーと呼ばれ、Ｘt0のように表される。ここで、ファイバーとセクションは共に代数曲面Ｘtの因子である。
【００３９】
一般に、代数曲面のファイブレーションが与えられたとき、それに対応するファイバーは（tに体の元を代入することにより）直ちに求まる。一方、ファイブレーションに対応するセクションを求めることは、極めて難しい。この意味ではファイバーは自明な因子であり、セクションは非自明な因子であると言える。
【００４０】
本発明の鍵生成方式を適用する公開鍵暗号は、代数曲面上の求因子問題のうち、特に、代数曲面ＸのファイブレーションＸtが与えられたときにセクションを求める問題に安全性の根拠をおく。
【００４１】
ファイブレーションからセクションを求めるには、現代の数学においても次の(i)(iv)の手順による方法しか知られていない。
【００４２】
(i) セクション(ｕx(t), ｕy(t), t)を
degｕx(t) ≦ d，degｕy(t) ≦ d
と仮定した上で、ｕx(t)，ｕy(t)を次式のようにおく。
【００４３】
ｕx(t)＝α0＋α1＋・・・＋αdｔd
ｕy(t)＝β0＋β1＋・・・＋βdｔd
(ii) ｕx(t)，ｕy(t)をＸ（x, y, t）＝０に代入して、次式を得る。
【数２３】
0004664850.tif 000006
【００４４】
(iii) 上式の左辺を展開してｔiの係数をα0,・・・,αd, β0,・・・,βdの関数ci(α0,・・・,αd, β0,・・・,βd)で表現し、次の連立方程式系を立てる。
【００４５】
ｃ0(α0，・・・，αd，β0，・・・，βd)＝０
ｃ1(α0，・・・，αd，β0，・・・，βd)＝０
：
ｃ2d(α0，・・・，αd，β0，・・・，βd)＝０
(iv) 連立方程式系を解く。
【００４６】
（第１の実施形態）
（概要）
本実施形態の公開鍵は、以下の４つである。
【００４７】
1. 素体の標数p
2. Ｆp上の代数曲面Ｘのファイブレーション: Ｘ(x, y, t)＝0
3. Ｆp上の１変数既約多項式ｆ(t)の次数l
4. （秘密鍵である）セクションにおける多項式ｕx(t), ｕy(t), ｖx(t), ｖy(t)の最大次数d
但し、lは代数曲面のファイブレーションＸ(x, y, t)とセクションの最大次数dの間に次の式(3)の関係を持つ。
【００４８】
(degx Ｘ(x, y, t)＋degy Ｘ(x, y, t))d＋degt Ｘ(x, y, t) ＜ l     (3)
ここで、degx Ｘ(x, y, t)は、Ｘ(x, y, t)のxのみを変数と考えた時の次数（例えばdegx(x3y2t＋xy5t6)＝3）である。degy(Ｘ(x, y, t)), degt(Ｘ(x, y, t)) も同様の次数である。
【００４９】
また、公開鍵のうち、素体の標数p及びセクションの最大次数dは、安全性のパラメータとしても考えられる。
【００５０】
一方、秘密鍵は、以下の２つの異なるセクションＤ1，Ｄ2である。
【００５１】
1. Ｆp上の代数曲面Ｘのセクション: Ｄ1：(x, y, t)＝(ｕx(t), ｕy(t), t)
2. Ｆp上の代数曲面Ｘのセクション: Ｄ2：(x, y, t)＝(ｖx(t), ｖy(t), t)
次に、本実施形態における鍵生成方法を説明する。この鍵生成方法は、セクションＤ1,Ｄ2をランダムに選び、セクションＤ1,Ｄ2に対応したファイブレーションＸを計算することによって行う。但し、生成された代数曲面が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。代数曲面（のファイブレーション）は、一般に、次式のように書ける。
【数２４】
0004664850.tif 000007
【００５２】
ここで、cij(t)は１変数多項式である。
【００５３】
まず、システムパラメータとして素体の標数pを決める。標数pが小さくても安全性に問題は生じない。さて、セクションＤ1,Ｄ2を次のようにおく。  
Ｄ1：(x, y, t)＝(ｕx(t),ｕy(t),t),  
Ｄ2：(x, y, t)＝(ｖx(t),ｖy(t),t)  
続いて、これらのセクションを代数曲面Ｘに代入し、次の２つの式を得る。
【数２５】
0004664850.tif 000008
【００５４】
関係式(5)から多項式となるc10(t)を生成するには、次式を設定すれば十分である（A｜BはAがBを割り切ること、即ちBがAの倍数（倍式）であることを意味する。）。
【００５５】
ｕx(t)−ｖx(t)｜ｕy(t)−ｖy(t)
この式は、関係式(5)と、次の２つの式から明らかである。
【００５６】
(ｕx(t)−ｖx(t))｜(ｕx(t)i −ｖx(t)i)
(ｕy(t)−ｖy(t))｜(ｕy(t)j −ｖy(t)j)
以上のことを利用して以下に示すアルゴリズムで鍵生成を行うことができる。  
始めに、λx(t)｜λy(t)となる２つの多項式をランダムに選択する。
【００５７】
具体的に、このような多項式の組を求めるには、例えばλx(t)をランダムに与えて、同じく次数d−deg λx(t)以下のランダムな多項式c(t)によってλy(t)＝c(t)λx(t)を計算することにより、λy(t)を求めればよい。
【００５８】
次に、λx(t)＝ｕx(t)−ｖx(t), λy(t)＝ｕy(t)−ｖy(t)とおき、多項式ｖx(t)をランダムに選択し、ｕx(t)＝λx(t)＋ｖx(t)を計算する。λx(t), ｖx(t)の次数はd 以下なので、ｕx(t)の次数もd 以下となる。
【００５９】
同様に多項式ｖy(t)をランダムに選択し、ｕy(t)＝λy(t)＋ｖy(t)を計算する。同様に、λy(t), ｖy(t)の次数はd 以下なのでｕy(t)の次数もd 以下となる。
【００６０】
次に、定数項c00(t), 一次の項c10(t)x 以外の係数cij(t)((i, j)≠(0,0),(1,0))をランダムに生成し、前述したｕx(t), ｖx(t), ｕy(t), ｖy(t)及び式(4)に基づいて、一次の項の係数c10(t)を計算する。更に、次の式(6)を計算し、定数項c00(t)を得る。
【数２６】
0004664850.tif 000009
【００６１】
（第１の実施形態の具体的な構成）
次に、本発明の第１の実施形態に係る鍵生成装置の具体的な構成とそのアルゴリズムについて説明する。尚、以下の説明は、理解を助けるための例として、具体的な数値や式を挙げて述べる。但し、これらの数値や式は、あくまでも理解を助けるための例であり、実際に使われる十分な安全性を持つ数値や式とは必ずしも一致していない。これは以下の各実施形態及び各バリエーションでも同様である。なお、必ずしも一致しない数値としては、例えばセクションの最大次数dなどが挙げられる。
【００６２】
図２は本発明の第１の実施形態に係る鍵生成装置の全体構成図である。なお、この鍵生成装置１０は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。これは以下の各実施形態の各装置１０，３０，４０でも同様である。
【００６３】
ここで、鍵生成装置１０は、図２に示すように、パラメータ入力部１１、制御部１２、代数曲面決定部１３、セクション生成部１４、１変数多項式生成部１５、１変数多項式演算部１６、代数曲面生成部１７、１変数既約多項式最小次数生成部１８及び鍵出力部１９を備えている。また、鍵生成装置１０は、図示しないメモリ（ハードウェア資源）を有し、各部１１〜１９から入力データ、出力データ及び処理中のデータ等が適宜読出／書込可能となっている。なお、このことは他の各装置２０，３０でも同様である。
【００６４】
ここで、パラメータ入力部１１は、外部から入力されたパラメータp, dを一時的にメモリに記憶し、メモリ内のパラメータp, dを制御部１２に送出する機能をもっている。
【００６５】
制御部１２は、後述する図４及び図５に示す動作を実行するように、各部１１，１３〜１４，１７〜１９を制御する機能をもっている。
【００６６】
代数曲面決定部１３は、制御部１２に制御され、図示しないメモリに記憶された後述する代数曲面テーブルＴ内の各形式データのいずれかをランダムに選択することにより、ファイブレーションＸ(x, y, t)の形式データを決定する機能をもっている。
【００６７】
ここで、代数曲面の決定の手法としては、図３に示す如き、代数曲面形式テーブルＴを用いる第１の方法と、変数x, yに関する総次数dcを決定し、その範囲で係数が0でない項をランダムに決定して生成する第２の方法が適宜、使用可能となっている。なお、本実施形態では第１の方法を用いている。
【００６８】
第１の方法に関し、代数曲面形式テーブルＴは、例えば、変数x, yに関する総次数dcと、代数曲面の定義式（形式データ）の候補とが互いに関連付けられてメモリに記憶されたものである。ここで、形式データは、ファイブレーションＸ(x, y, t)の形式データの候補を、下記式に基づいて、tの１変数多項式cij(t)を係数としたｘiｙjの多項式として表すものである。
【数２７】
0004664850.tif 000010
【００６９】
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる。なお、使用する次数の組合せ(i, j)の集合は、０でない項に対応している。
【００７０】
形式データとしては、tの１変数多項式cij(t)を係数としたｘiｙjの多項式を表すデータであれば、任意のデータが使用可能となっている。
【００７１】
第２の方法に関し、係数が0でない項の個数を予めプログラムに記述するか、パラメータとして入力するか、又は予めメモリに格納することにより、係数が0で無い項を効果的に決定できる。理由は、0でない項を制限することで代数曲面の定義式の形を簡略化でき、公開鍵サイズを削減可能なためである。
【００７２】
セクション生成部１４は、制御部１２に制御され、１変数多項式生成部１５及び１変数多項式演算部１６を制御して各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)を得る機能と、これら１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t)に基づいて、２つのセクションＤ1：(x, y, t)＝(ｕx(t), ｕy(t), t) 及びＤ2：(x, y, t)＝(ｖx(t), ｖy(t), t)を生成する機能をもっている。
【００７３】
１変数多項式生成部１５は、セクション生成部１４又は代数曲面生成部１７に制御され、指定された素数p 及び次数d に基づいて、ランダムな１変数多項式を生成する機能をもっている。このとき、１変数多項式生成部１５は、d次未満の各項の係数を、有限体Ｆpの元として0 からp−1 までの範囲でそれぞれランダムに生成する。すなわち、各１変数多項式λx(t)，λy(t)は、有限体Ｆp上定義されている。これに限らず、他の各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t), c10(t), c00(t)も、有限体Ｆp上定義されている。
【００７４】
具体的には１変数多項式生成部１５は、セクション生成部１４に制御されるとき、次数d 未満のランダムな１変数多項式λx(t)を生成する機能と、１変数多項式λx(t)で割り切れる次数d 以下の１変数多項式λy(t)を生成する機能とをもっている。
【００７５】
また、１変数多項式生成部１５は、代数曲面生成部１７に制御されるとき、決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である１変数多項式cij(t)（但し(i,j)≠(0,0),(1,0)）をランダムに生成する機能をもっている。
【００７６】
１変数多項式演算部１６は、セクション生成部１４又は代数曲面生成部１７に制御され、受信した演算命令に基づいて、有限体Ｆp上の１変数多項式の加減乗除演算を実行する機能をもっている。
【００７７】
具体的には１変数多項式演算部１６は、セクション生成部１４に制御されるとき、１変数多項式λx(t)に基づいて、互いの差分{ｕx(t)−ｖx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の２つの１変数多項式ｕx(t), ｖx(t)を生成する機能と、１変数多項式λy(t)に基づいて、互いの差分{ｕy(t)−ｖy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の２つの１変数多項式ｕy(t), ｖy(t)を生成する機能とをもっている。
【００７８】
また、１変数多項式演算部１６は、代数曲面生成部１７に制御されるとき、各１変数多項式ｕx(t), ｖx(t), ｕy(t), ｖy(t), cij(t)に基づいて、式(4)に示す一次の項の係数である１変数多項式c10(t)を生成する機能と、各１変数多項式ｕx(t), ｕy(t), cij(t), c10(t)に基づいて、式(6)に示す定数項である１変数多項式c00(t)を生成する機能とをもっている。
【００７９】
代数曲面生成部１７は、制御部１２に制御され、１変数多項式生成部１５及び１変数多項式演算部１６を制御して各１変数多項式cij(t), c10(t), c00(t)を得る機能と、得られた各１変数多項式cij(t), c10(t), c00(t)を、決定された形式データに設定することにより、代数曲面ＸのファイブレーションＸ(x, y, t)を生成する機能とをもっている。
【００８０】
１変数既約多項式最小次数生成部１８は、制御部１２に制御され、生成されたファイブレーションＸ(x, y, t)における各々の変数x, y, t の次数degx Ｘ(x, y, t), degy Ｘ(x, y, t), degt Ｘ(x, y, t)及び前記次数d に基づいて、(degＸ(x, y, t)＋degy Ｘ(x, y, t))d＋degt Ｘ(x, y, t) 以上となるように、暗号化用のランダム１変数多項式の最小次数lを定める機能をもっている。
【００８１】
鍵出力部１９は、公開鍵である代数曲面Ｘと、一変数既約多項式の最小次数lと、秘密鍵であるセクションＤ1，Ｄ2とを制御部１２から受信し、これらの鍵データＸ，l，Ｄ1，Ｄ2を鍵出力装置１０の外部に出力する機能をもっている。
【００８２】
次に、以上のように構成された鍵生成装置の動作について図４及び図５のフローチャートを用いて説明する。  
鍵生成装置１０は、鍵生成のパラメータである素体の標数pとセクションの最大次数dがパラメータ入力部１１に入力されると、処理を開始する。ここでは簡単のためp＝2, d＝3が入力されたとする（ＳＴ１）。
【００８３】
パラメータ入力部１１は、入力されたパラメータp, dを一時的にメモリに記憶し、メモリ内のパラメータp, dを制御部１２に送信する。制御部１２は、パラメータp, dを受けると、代数曲面決定部１３に代数曲面の形式を出力する旨の指示を出す。
【００８４】
代数曲面決定部１３は、この指示により、メモリに記憶された代数曲面形式テーブルＴ内の各形式データのいずれかをランダムに選択することにより、代数曲面ＸのファイブレーションＸ(x, y, t)の形式を決定する（ＳＴ２）。ここでは、形式として、Ｘ(x, y, t)＝x5＋y5＋c21(t)x2y＋c10(t)x＋c00(t)を決定したとする。
【００８５】
代数曲面決定部１３は、決定した代数曲面の形式データを制御部１２に出力する。制御部１２は、この代数曲面の形式データとパラメータp, dをセクション生成部１４に送信する。
【００８６】
セクション生成部１４は、代数曲面の形式データとパラメータp, dに基づいて、セクションの生成を開始する。始めに、セクション生成部１４は、素数pとセクションの最大次数d 未満の値を１変数多項式生成部１５に送信し、１変数多項式の生成を要求する。
【００８７】
１変数多項式生成部１５は、この要求に基づいて、d次未満の１変数多項式λx(t)(＝t2＋1)をランダムに生成する（ＳＴ３）。このとき、１変数多項式生成部１５は、d次未満の各項の係数を、有限体Ｆpの元として0 からp−1 までの範囲でそれぞれランダムに生成する。これにより、１変数多項式λx(t)が得られる。１変数多項式生成部１５は、得られたλx(t)は、セクション生成部１４に出力される。
【００８８】
セクション生成部１４では、前述同様に、素数pと、次数d−deg λx(t)とを１変数多項式生成部１５に送信し、１変数多項式の生成を要求する。
【００８９】
１変数多項式生成部１５は、ステップＳＴ３と同様にして、次数d−deg λx(t)の１変数多項式c(t)(＝t)をランダムに生成する（ＳＴ４）。得られたc(t)は、セクション生成部１４に出力される。
【００９０】
次に、セクション生成部１４は、c(t)とλx(t)を１変数多項式演算部１６に送信する。１変数多項式演算部１６は、c(t)とλx(t)に基づいて、λy(t)＝c(t)λx(t)を計算する（ＳＴ５）。このとき、１変数多項式演算部１６は、有限体Ｆp上の１変数多項式の加減乗除演算を行ない、λy(t)を得る。得られたλy(t)(＝t3＋t)は、セクション生成部１４に送信される。
【００９１】
セクション生成部１４は、λy(t)を受信すると、前述同様に、１変数多項式生成部１５に１変数多項式の生成を要求する。１変数多項式生成部１５は、d次の１変数多項式ｖx(t)をランダムに生成し（ＳＴ６）、得られたｖx(t)をセクション生成部１４に出力される。
【００９２】
セクション生成部１４は、これらλx(t)(＝t2＋1)とｖx(t)(＝t3＋1)を１変数多項式演算部１６に送信する。１変数多項式演算部１６は、λx(t)とｖx(t)に基づいて、ｕx(t)(＝λx(t)＋ｖx(t)＝t3＋t2)を計算し（ＳＴ７）、得られたｕx(t)をセクション生成部１４に送信する。
【００９３】
以下同様に、セクション生成部１４は、１変数多項式生成部１５及び１変数多項式演算部１６により、ｖy(t)(＝t3＋t2＋1)を生成し（ＳＴ８）、ｕy(＝λy(t)＋ｖy(t)＝t2＋t＋1)を計算する（ＳＴ９）。
【００９４】
しかる後、セクション生成部１４は、得られたｕx(t), ｕy(t), ｖx(t), ｖy(t)に基づいて、２つのセクションＤ1，Ｄ2を生成する。なお、Ｄ1：(x, y, t)＝(ｕx(t),ｕy(t),t)，Ｄ2：(x, y, t)＝(ｖx(t),ｖy(t),t)である。セクションＤ1，Ｄ2は、セクション生成部１４から制御部１２に送信される。
【００９５】
制御部１２では、セクションＤ1，Ｄ2を受けると、このセクションＤ1，Ｄ2を持つ代数曲面を作成するため、代数曲面生成部１７にセクションＤ1，Ｄ2を入力する。
【００９６】
代数曲面生成部１７は、セクションＤ1，Ｄ2を受けると、c10(t), c00(t)以外の係数であるc21(t)をランダムに生成させるための指示を１変数多項式生成部１５に送信する。
【００９７】
１変数多項式生成部１５は、この指示により、係数c21(t)をランダムに生成する。ここで次数は、例えば2dなどのように、dの倍数に取る(c21(t)＝t6＋t4＋t3＋t＋1)。得られたc21(t)は、１変数多項式生成部１５から代数曲面生成部１７に返信される。
【００９８】
代数曲面生成部１７は、入力されたセクションＤ1，Ｄ2とランダムに生成された係数c21(t)から式(4)に基づいて、１変数多項式演算部１６に繰り返し演算命令を送信することにより、一次の項の係数ｃ10(t)を計算する（ＳＴ１０）。この例では、c10(t)＝t8＋t7＋t6＋t5＋t4＋t3＋t2が算出される。
【００９９】
更に、代数曲面生成部１７は、c10(t), c21(t)とｕx(t), ｕy(t), ｖx(t), ｖy(t)から式(6)に基づいて、１変数多項式演算部１６に繰り返し演算命令を送信することにより、定数項c00(t)を計算する（ＳＴ１１）。この例では、c00(t)＝t15＋t13＋t12＋t11＋t9＋t8＋t5＋t4＋t2＋t＋1が算出される。
【０１００】
以上で代数曲面Ｘ(x, y, t)の形式データに必要な各項の係数の生成が完了する。  
代数曲面生成部１７は、各１変数多項式c21(t), c10(t), c00(t)を、ステップＳＴ３で決定した形式データに設定することにより、代数曲面ＸのファイブレーションＸ(x, y, t)を生成する。生成されたファイブレーションＸ(x, y, t)は、代数曲面生成部１７から制御部１２に送信される。
【０１０１】
以上の処理により、公開鍵である代数曲面Ｘのファイブレーション
X(x, y, t) : x5＋y5＋(t6＋t4＋t3＋t＋1)x2y＋(t8＋t7＋t6＋t5＋t4＋t3＋t2)x  
＋t15＋t13＋t12＋t11＋t9＋t8＋t5＋t4＋t2＋t＋1 ＝ 0        (7)
と秘密鍵である２つのセクション
Ｄ1：(ｕx(t),ｕy(t),t)＝(t3＋t2, t2＋t＋1, t)
Ｄ2：(ｖx(t),ｖy(t),t)＝(t3＋1, t3＋t2＋1, t)                      (8)
が得られた。
【０１０２】
次に、制御部１２では、式(3)を満たす次数lを生成するため、１変数既約多項式次数生成部１８に、代数曲面Ｘ(x, y, t)とセクションの最大次数dとを入力して次数lの生成を指示する。
【０１０３】
１変数既約多項式次数生成部１８は、代数曲面Ｘ(x, y, t)とセクションの最大次数dとに基づいて式(3)の左辺((5＋5) * 3＋15＝45)を計算する。次に、１変数既約多項式次数生成部１８は、式(3)の右辺を得るために、この計算値(＝45)よりも大きい値をランダムに選択する。ここでは例えば、値46を選択する。１変数既約多項式次数生成部１８は、選択した値(46)を次数l(＝46)として（ＳＴ１２）、制御部１２へ出力する。
【０１０４】
制御部１２は、公開鍵である代数曲面Ｘと、一変数既約多項式の最小次数lと、秘密鍵であるセクションＤ1，Ｄ2とを鍵出力部１９に送信する。
【０１０５】
鍵出力部１９は、これらの鍵データＸ，l，Ｄ1，Ｄ2を鍵出力装置１０の外部に出力する（ＳＴ１３）。
【０１０６】
上述したように本実施形態によれば、公開鍵の一部であるファイブレーションＸ(x, y, t)を生成する際に、ファイブレーションＸ(x, y, t)の形式にcijxiyjの項を含めた構成により、生成される公開鍵のクラスの制限を除去することができる。
【０１０７】
ここで、cijxiyjの項を含めた構成を実現させるため、cijxiyjの項を、一次の項及び定数項c00以外の項としている。そして始めに、cijxiyjの項をランダムに生成する。続いて、cijxiyjの項と、２つのセクション内の１変数多項式とに基づいて一次の項の係数を生成する。最後に、cijxiyjの項と一次の項とに基づいて定数項c00を生成している。
【０１０８】
このような構成により、本実施形態においては、秘密鍵が２つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止することができる。
【０１０９】
＜第１の実施形態のバリエーション＞
次に、本実施形態における幾つかのバリエーションを述べる。  
第１のバリエーションは、代数曲面の定義体に関するバリエーションである。本実施形態では、代数曲面の定義体として素体を用いたが、これに限らず、一般の有限体Fq(q＝pr)を代数曲面の定義体としてもよい。有限体は、素体と同様に、0での除算を除く四則演算を定義でき、一意的に値が定まるからである。有限体は、素体とその（有限次）拡大体から構成される。拡大体は、素体Ｆp上の拡大次数rの線形空間の元として定義される。また、拡大体は、当該拡大体の原始多項式によりリダクションが行なわれ、演算が定義される。なお、リダクションは、素体におけるpによるリダクション（割り算）と同種の操作である。
【０１１０】
第１のバリエーションによれば、有限体を代数曲面の定義体とした際に、拡大体の導入に伴い、生成できる鍵の種類が増えるので、安全性の更なる向上に貢献できる。第１のバリエーションを実施する場合、本実施形態で素数pが入力される部分に、更に拡大次数rを入力すればよい。なお、第１のバリエーションにおいては、内部演算を全て拡大体Ｆq上で行なう必要がある。但し、鍵生成のアルゴリズムでは四則演算のみを用いるので、本実施形態の内部演算がそのまま成立する。
【０１１１】
第２のバリエーションは、ステップＳＴ１において、入力される素数pとセクションの最大次数dのうち、いずれか一方又は両方（以下、「及び／又は」とも言う）をシステムパラメータとして固定するバリエーションである。パラメータp及び／又はdを固定することにより、ユーザは、セキュリティレベルを気にせずに、鍵生成装置１０内の適切なパラメータの下で安全な鍵を生成できる。なお、「適切なパラメータ」とは、十分高いセキュリティレベルを持ったパラメータを意味する。
【０１１２】
第２のバリエーションを実現するには、図６に示すように、素数格納部１１ａ及び／又はセクションの最大次数格納部１１ｂを更に備え、鍵生成アルゴリズムにおいて、これらのパラメータp, dが入力されるステップＳＴ１の代わりに、図７に示すように、格納部１１ａ，１１ｂ内の値を読み出すステップを挿入すればよい。また、第１のバリエーションで述べた拡大次数rに関しても同様のことが成り立つ。この場合、素数格納部１１ａに代えて、図８に示すように、素数pと拡大次数rを格納する有限体格納部１１ｃを設ければよい。
【０１１３】
第３のバリエーションは、0でない定数項c00(t)と一次の項c10(t)xに関するバリエーションである。本実施形態では、定数項c00(t)と一次の項c10(t)xを用いたが、これに限らず、図７に示すように、定数項c00(t)と一次の項c01(t)yを用いてもよい。理由は、セクションから代数曲面を求めることができれば、一次の項はc10(t)x又はc01(t)yのいずれでもよいからである。なお、本実施形態では、一次の項c10(t)xを用いる場合には、c00(t), c10(t)x 以外の項の係数cij(t)をランダムに定め、係数cij(t)からc00(t), c10(t)を計算している。同様にして、一次の項c01(t)yを用いる場合には、c00(t), c01(t)y 以外の項の係数cij(t)をランダムに定め、係数cij(t)からc00(t), c01(t)を計算すればよい。c00(t), c01(t)の計算は、本実施形態におけるλx(t)をλy(t)に置き換えると共に、これに準じてｕx(t), ｖx(t)をｕy(t), ｖy(t)に置き換えれば良い。
【０１１４】
第４のバリエーションは、鍵生成処理のうち、一変数既約多項式ｆ(t)の最小次数lを求める処理を外部で実行するバリエーションである。鍵生成処理の主要部分は、２つのセクションから安全性の高い代数曲面を生成する処理にある。このため、最小次数lを求める処理は、代数曲面Ｘ(x, y, t)とパラメータdに基づいて、鍵生成装置１０の外でも実行できる。鍵生成装置１０の外部に一変数既約多項式生成部１８を配置した場合、鍵生成装置１０の構成を簡素化できる。これに加え、一変数既約多項式最小次数生成部１８をモジュール化することにより、より安全性の高い実装が可能になる。
【０１１５】
（第２の実施形態）
本実施形態における公開鍵・秘密鍵は、第１の実施形態と同じである。
【０１１６】
本実施形態は、将来に亘って代数曲面の安全性を確保する観点から、第１の実施形態で得られた代数曲面が特殊なクラスに属するか否かを検査し、特殊なクラスに属する代数曲面を避ける形態である。
【０１１７】
補足すると、代数曲面には、楕円曲面、有理曲面と呼ばれる特殊なクラスが存在する。特殊なクラスの代数曲面は、それぞれ性質が良く知られている。従って、特殊なクラスの代数曲面は、求セクション問題の効率的な解法こそ見出されてないものの、１つのセクションが求まれば他のセクションが求まる等といった解析し易い性質があるので、安全性が低い。そこで、将来に亘って安全性を確保するには、解析し易い特殊なクラスの代数曲面を避けることが望ましい。
【０１１８】
さて、生成された代数曲面に関し、特殊なクラスの代数曲面か否かの判定に必要な種数という量を定義する。始めに、代数曲面のファイブレーションを
【数２８】
0004664850.tif 000011
で表現する。更に、このファイブレーションを、x, yを変数とする代数関数体K(＝Ｆp(t)) 上の代数曲線とみなした場合の曲線をＣ(x, y)＝0もしくはＣで表す。種数はこの曲線Ｃに対して定義され、g(Ｃ)で表される。いま、xとyに関するＣの総次数をdcとおくとき、種数g(Ｃ)は
【数２９】
0004664850.tif 000012
のように表される。ここで、PはＣの特異点を表し、右辺第二項の和はＣの全ての特異点にわたる。特異点とは、代数曲線Ｃ(x, y)＝0 上の微分係数が一意に定まらない点を云う。交点や尖点は特異点である。交点は２個の微分係数が対応し、尖点は２個以上の微分係数が対応している。式(9)におけるσ(P)は、各特異点の特異性を測る量であり、例えば、文献“飯高茂・上野健爾・浪川幸彦著「デカルトの精神と代数幾何」（日本評論社、1993 年）、p.23”に定義が記されている。しかしながら、σ(P)の定義からも容易に推察されるように、一般に、σ(P)を求めることは、計算機を用いても困難である。
【０１１９】
一方、有限体のサイズ(本実施形態ではp) 又はcij(t)の最高次数eが十分大きければ、任意に代数曲線を抽出したとき、特異点を持たない代数曲線（非特異な代数曲線）となる確率が十分大きくなる。理由は以下の通りである。Ｃの定義式
【数３０】
0004664850.tif 000013
のxとyの総次数をdcとする。まず、与えられた２つのセクションをファイブレーションＸが有するという条件を考慮せず、任意のdc次多項式を考える。このとき、Ｃ(x, y)の中に現れる項の数は
【数３１】
0004664850.tif 000014
【０１２０】
さて、{cij(t)}をＮd_c次のベクトルと考えると、{cij(t)} 全体はＫ上Ｎd_c次元のベクトル空間をなす。
【０１２１】
さらに、一つのベクトル{cij(t)}を0でない定数倍（b(t)倍）し、得られるdc次多項式b(t)Ｃ(x, y)は、元の多項式Ｃ(x, y)と本質的に同じである。そこで、dc次同次多項式全体のなす集合を定数倍の作用で割り、得られた集合をＨd_cとおく。つまりＨd_c＝{Ｋ上３変数dc次多項式}/(定数倍)である。すると
【数３２】
0004664850.tif 000015
である（岩波講座・現代数学の展開・向井  茂著「モジュライ理論１」、ｐ．１４７）。上式は、Ｈd_cの中にあるほとんど全ての多項式は非特異な曲線を定義することを示す。理由は、係数{cij(t)}の次数の上限をeとすると、＃Ｋ＝pe+1であるからである。
【０１２２】
よって、Ｈd_cの中から任意に選んだ曲線が特異曲線となる確率は
【数３３】
0004664850.tif 000016
で与えられる。この確率は、p もしくはeが大きいと極めて小さい数になる。鍵生成装置１０により生成される代数曲面は、cij(t)の次数eが極めて大きいため、たとえpが小さくても、十分高い確率で非特異な代数曲面となる。よって、種数g(Ｃ)を
【数３４】
0004664850.tif 000017
と近似的に求める式(10)が相当に高い確率で成立する。
【０１２３】
また、種数ｇと、特殊なクラスの代数曲面（楕円曲面、有理曲面）とは、以下の関係にあることが知られている。
【０１２４】
ｇ＝０  ⇒  （有理曲面）
ｇ＝１  ⇒  （楕円曲面）      (11)
よって、安全な鍵を生成するためには、ｇ≧２の代数曲面を用いることが望ましい。
【０１２５】
（第２の実施形態の具体的な構成）
図９は本発明の第２の実施形態に係る鍵生成装置の全体構成図であり、図２と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した部分の説明を省略する。
【０１２６】
本実施形態は、第１の実施形態の変形例であり、予め特殊なクラスの代数曲面を避ける観点から、種数計算部２１及び安全性検証部２２を付加した構成となっている。
【０１２７】
ここで、種数計算部２１は、各部１１〜１７により生成されたファイブレーションＸ(x, y, t)における変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)に基づいて、当該ファイブレーションＸ(x, y, t)を１変数関数体Ｆｐ(t)上の代数曲線Ｃ(x, y)とみなしたときの種数g(Ｃ)を、計算式 g(Ｃ)＝(dc−１)(dc−２)／２に基づいて計算する機能と、計算した種数g(Ｃ)を制御部１２に送信する機能とをもっている。
【０１２８】
安全性検証部２２は、制御部１２から受けた種数g(Ｃ)が２未満であるか否かを判定する機能と、判定の結果、種数g(Ｃ)が２未満のとき、代数曲面決定部１３から種数計算部２１までの処理を再実行するように、エラー信号を制御部１２に送信する機能と、判定の結果、種数g(Ｃ)が２以上のとき、安全を通知する信号を制御部１２に送信する機能とをもっている。
【０１２９】
次に、以上のように構成された鍵生成装置の動作を図１０及び図１１のフローチャートを用いて説明する。
【０１３０】
鍵生成装置１０においては、前述同様に、ステップＳＴ１〜ＳＴ１１までの処理を実行する。制御部１２は、この処理により得られた有限体の情報（本実施形態では素数p）と代数曲面Ｘ(x, y, t)とを種数計算部２１に送信する。
【０１３１】
種数計算部２１は、有限体の情報、代数曲面Ｘ(x, y, t)及び式(10)に基づいて、種数ｇ(Ｘ)を近似的に計算する（ＳＴ１１−２）。詳しくは、代数曲面をx, yに関する多項式と見た場合の総次数dcを計算する。この計算は、代数曲面の各項のx, yに関する総次数を求め、その最大値をdcとして実行される。次に、dc を式(10)に代入して種数ｇ(Ｘ)を計算する。得られた種数ｇ(Ｘ)は、制御部１２へ送信される。
【０１３２】
制御部１２は、種数g(Ｘ)を安全性検証部２２に送信する。安全性検証部２２は、この種数ｇ(Ｘ)が２未満（g(Ｘ) ＜ 2）であるか否かを判定する（ＳＴ１１−３）。種数ｇ(Ｘ)が２未満の場合、ファイブレーションＸが特殊なクラスの代数曲面（楕円曲面又は有理曲面）であるので、将来にわたる安全性を確保できない。
【０１３３】
そこで、安全性検証部２２は、種数ｇ(Ｘ)が２未満の場合、ステップＳＴ２からＳＴ１１−３までの処理を再実行するように、エラー信号を制御部１２に送信する。制御部１２は、エラー信号を受けると、他の鍵を生成するため、ステップＳＴ２に戻り、代数曲面決定部１３を制御する。
【０１３４】
一方、ステップＳＴ１１−３の結果が否（g(Ｘ) ≧ 2）の場合、ファイブレーションＸが特殊なクラスの代数曲面ではないので、安全性を確保できる。そこで、安全性検証部２２は、否（g(Ｘ) ≧ 2）の場合、安全を通知する信号を制御部１２に送信する。
【０１３５】
制御部１２は、安全を通知する信号を受けると、一変数既約多項式ｆ(t)の最小次数lを計算するための指示を一変数既約多項式最小次数生成部１８に送信する。以下、第１の実施形態と同様にステップＳＴ１２，ＳＴ１３の処理を実行する。
【０１３６】
上述したように本実施形態によれば、第１の実施形態の効果に加え、生成されたファイブレーションＸ(x, y, t)を代数曲線Ｃ(x, y)とみなしたときの種数g(Ｃ)を計算し、得られた種数g(Ｃ)が２未満のとき、他のファイブレーションＸ(x, y, t)を生成するため、ステップＳＴ２に戻る構成により、解析し易いクラスの代数曲面の使用を避けることができ、もって、将来にわたる安全性を確保することができる。
【０１３７】
＜第２の実施形態のバリエーション＞
前述した第１〜４のバリエーションは、図１２及び図１３に示すように、本実施形態でも同様に成り立つ。  
第５のバリエーションは、代数曲面の総次数dcに基づいて、代数曲面決定部１３で代数曲面を絞り込むバリエーションである。第５のバリエーションでは、種数計算部２１及び安全性検証部２２（ステップＳＴ１１−２，ＳＴ１１−３）を省略し、代数曲面決定部１３により、予め特殊なクラスの代数曲面を排除している。なお、種数計算部２１及び安全性検証部２２（ステップＳＴ１１−２，ＳＴ１１−３）は省略しなくてもよい。
【０１３８】
ここで、代数曲面決定部１３は、具体的には、式(10)，(11)から得られる以下の関係に基づいて特殊なクラスの代数曲面を排除する。
【０１３９】
dc ＝ １，２  ⇒  ｇ＝０（有理曲面）
dc ＝ ３      ⇒  ｇ＝０（楕円曲面）
この関係によれば、総次数dcが３以下の代数曲面は、確実に特殊なクラスの代数曲面である。一方、総次数が４以上の代数曲面は、高い確率で特殊なクラスの代数曲面ではない。従って、代数曲面決定部１３においては、図１４に示すように、ステップＳＴ２で選択した形式データにおけるファイブレーションＸ(x, y, t)の変数x, yに関する総次数dc＝degx Ｘ(x, y, t)＋degy Ｘ(x, y, t)を算出し（ＳＴ２−２）、得られた総次数dcが４未満か否かを判定する（ＳＴ２−３）。
【０１４０】
代数曲面決定部１３は、この判定の結果、総次数dcが４未満のとき、ステップＳＴ２に戻り、選択した形式データとは異なる形式データを再選択し、再選択した形式データについて、ステップＳＴ２−２からＳＴ２−３までの処理を実行する。なお、ステップＳＴ２−３の判定の結果、総次数dcが４以上であれば、ステップＳＴ３に進むことは言うまでも無い。
【０１４１】
すなわち、代数曲面決定部１３は、ステップＳＴ２−２からＳＴ２−３までの処理により、総次数dcが３以下の代数曲面の形式を出力しないようにフィルタリングする。これにより、ステップＳＴ１１の後にＳＴ２に戻る場合が無くなるので、鍵生成の効率を向上できる。
【０１４２】
尚、第５のバリエーションにおける総次数dcが４以上のとき安全であり、４未満のとき安全でないと判断する判定方法は、代数曲面決定部１３で代数曲面を絞り込む部分で用いるだけでなく、第２の実施形態における安全性検証部２２での種数ｇ（Ｘ）による判定と置き換えて利用することができる。これは、種数ｇ（Ｘ）による判定と総次数dcによる判定とのどちらも出来上がった代数曲面の安全性を検証するための判定方法であり、式(10)からも分かる通り、総次数dcのみをパラメータとしているからである。従って、安全性検証部２２を総次数dcにより判定する構成に変えることにより、第２の実施形態に必須であった種数計算部２１が不要になる。またこの逆も成り立つ。即ち、第２の実施形態における式(10)により計算した種数ｇ（Ｘ）による代数曲面の安全性検証に変わって第５のバリエーションで述べた総次数dcのみによる判定方法を利用してもよい。これにより種数計算部２１が省略されるとともに、計算処理時間が短くなる。
【０１４３】
なお、第５のバリエーションの変形例としては、代数曲面決定部１３にて代数曲面を絞り込む際に、種数計算部２１及び安全性検証部２２を用い、種数ｇ（Ｘ）による判定を実行する構成を適用することができる。また、代数曲面決定部１３における判定と、代数曲面Ｘ(x, y, t)生成後の判定とにおいては、種数ｇ（Ｘ）又は総次数dcによる判定方法のうち、いずれか一方の判定方法のみを用いてもよく、あるいは各判定方法を交互に用いてもよい。また、他の変形例としては、種数ｇ（Ｘ）を計算する場合、種数ｇ（Ｘ）を式(9)に基づいて計算する構成とすることもできる。
【０１４４】
（第３の実施形態）
以下、本発明の第１又は第２の実施形態により生成された鍵を使用可能な暗号化・復号処理に関する実施形態を説明する。なお、第１又は第２の実施形態により生成された鍵は、特許文献１記載の暗号化・復号処理にも適用可能である。但し、ここでは、それ以外の暗号化・復号処理に関する実施形態について述べる。なお、第３の実施形態を述べる前に、前提となる安全性証明について述べる。
【０１４５】
公開鍵暗号の安全性は、素因数分解問題や離散対数問題のように、安全性の根拠となる問題の困難性に基づくと考えられている。しかし、この考えは、両者の厳密な帰着関係を述べるものではない。
【０１４６】
厳密な帰着関係を述べるためには、解読者による攻撃と達成される安全性とをモデル化し、モデル化した攻撃の下で安全性を達成することと、安全性の根拠となる問題の難しさとが等価であることを証明する必要がある。すなわち、公開鍵暗号の安全性と、公開鍵暗号を構成する問題の困難性との間の厳密な帰着関係を述べることが安全性証明である。
【０１４７】
安全性証明において、攻撃のモデルは、受動的攻撃(Chosen Plaintext Attack(ＣＰＡ))と、能動的攻撃(Chosen Cipher Attack(ＣＣＡ))とに大きく分類できる。
【０１４８】
受動的攻撃とは、公開鍵を利用して平文を繰り返し暗号化し、得られる暗号文から情報を引き出そうとする攻撃である。能動的攻撃とは、更に暗号文を復号装置に適応的に入力し、得られる復号結果から秘密鍵の情報を引き出そうとする攻撃である。この意味からＣＣＡの方がＣＰＡより強い攻撃となっている。
【０１４９】
また、安全性証明において、達成される安全性には２つの基準が提案されている。  
第１の基準は、２つの平文を暗号化した後に区別できないこと(Indistinguishable(ＩＮＤ))である。第２の基準は、多項式時間において暗号文を操作しても、元の平文に関係する暗号文を作成できないこと(Non-Malleable(ＮＭ))である。
【０１５０】
従って、安全性証明の基準は、敵による攻撃のモデルと、達成される安全性との組合せでＩＮＤ−ＣＰＡ，ＮＭ−ＣＣＡのように表現される。ＩＮＤ−ＣＰＡは、受動的攻撃の下で、２つの暗号文から元の平文を区別する情報を抽出できない旨を意味する。ＮＭ−ＣＣＡは、能動的攻撃の下で、暗号文を操作した結果から元の平文に関係した情報を得られない旨を意味する。現在のところ、最強の安全性と考えられている基準はＩＮＤ−ＣＣＡである。
【０１５１】
一方、ＩＮＤ−ＣＰＡの意味で安全性が証明された公開鍵暗号を、ＩＮＤ−ＣＣＡの意味で証明可能安全な公開鍵暗号アルゴリズムに変換する方法が知られている（例えば、特許第３３０６３８４号公報参照）。従って、ＩＮＤ−ＣＰＡの意味で安全性が証明された公開鍵暗号を構成できれば、この公開鍵暗号をＩＮＤ−ＣＣＡの意味で証明可能安全（provable secure）な公開鍵暗号に変換することが可能となっている。
【０１５２】
続いて、第３の実施形態を説明する。なお、以下の各実施形態は、前述した求セクション問題を前提とし、この求セクション問題と関連するランダム化多項式判定問題に基づいて安全性を証明可能な構成となっている。
【０１５３】
（概要）
本実施形態の公開鍵は以下の５つである。
【０１５４】
１．素体の標数ｐ
２．Ｆp上の代数曲面Ｘのファイブレーション：Ｘ(x,y,t)＝０
３．Ｆp上の１変数既約多項式ｆ(t)の次数ｌ
但し、
degtＸ(x,y,t)＜ｌ  (12)
４．（秘密鍵である）セクションにおける多項式ｕx(t),ｕy(t),ｖx(t),ｖy(t)の最大次数ｄ
５．３変数多項式ｐ(x,y,t)のx,yの最高指数ｅ
秘密鍵は以下の２つの異なるセクションＤ1,Ｄ2である。
【０１５５】
１．Ｆp上の代数曲面Ｘのセクション：Ｄ1：(x,y,t)＝(ｕx(t),ｕy(t),t)
２．Ｆp上の代数曲面Ｘのセクション：Ｄ2：(x,y,t)＝(ｖx(t),ｖy(t),t)
これらは、前述した鍵生成方法で容易に求めることができる。
【０１５６】
次に、暗号化処理の概要を述べる。暗号化処理では、まず暗号化したいメッセージ（以下では平文と呼ぶ）をブロック分割して
ｍ＝ｍ0‖ｍ1‖・・・‖ｍl-1
のようにし、平文多項式ｍ(t)の係数として次式のように埋め込む（平文埋め込み処理）。
【数３５】
0004664850.tif 000018
【０１５７】
ここで、ｍ(t)をＦp上の多項式とするために、各ｍi（０≦ｉ≦ｌ-１）はＦpの元となるように取る必要がある。即ち、平文ｍはｐのビット長に基づいて
０≦ｍi≦ｐ-１
となるように分割される。なお、平文ｍは整数であり、例えばメッセージを表す文字コード列が整数に読み替えられることにより、構成されている。
【０１５８】
次に、Ｆp上のランダム多項式ｐ(x,y,t),ｑ(x,y,t)をランダムに決める。このとき、ｐ(x,y,t)は、次の条件(13)(14)を満たすように決める。
【０１５９】
α＞degxＸ(x,y,t)
β＞degyＸ(x,y,t)
なる指数α，βに対して  ｘαｙβの項を含む                      (13)
(degxｐ(x,y,t)＋degyｐ(x,y,t))ｄ＋degtｐ(x,y,t)＜ｌ      (14)
ここで、degx, degy, degtにより、それぞれ多項式のx,y,tに関する次数を表すものとする。また、ｑ(x,y,t)は、次の条件(15)を満たすように決める。
【０１６０】
degtｑ(x,y,t)＜ｌ      (15)
次に、Ｆp上ランダムな１変数のｌ次既約多項式ｆ(t)を決める。既約多項式とは、これ以上因数分解できない多項式のことである。有限体上の１変数多項式の既約性判定は、容易であることが知られている。以上の式ｍ(t),ｐ(x,y,t),ｑ(x,y,t),ｆ(t)及び公開鍵である代数曲面ＸのファイブレーションＸ(x,y,t)から、次の式(16)によって暗号文Ｆ(x,y,t)を計算する。
【０１６１】
Ｆ(x,y,t)＝ｍ(t)＋ｆ(t)ｐ(x,y,t)＋Ｘ(x,y,t)ｑ(x,y,t)      (16)
暗号文Ｆ(x,y,t)を受け取った受信者は、所有する秘密鍵Ｄ1,Ｄ2を利用して次のように復号を行う。まず、セクションＤ1,Ｄ2を暗号文Ｆ(x,y,t)に代入する。ここで、セクションＤ1,Ｄ2を代数曲面Ｘ(x,y,t)に代入すると、
Ｘ(ｕx(t),ｕy(t),t)＝０,Ｘ(ｖx(t),ｖy(t),t)＝０により、次の２式ｈ1(t),ｈ2(t)が求まる。
【０１６２】
ｈ1(t)＝Ｆ(ｕx(t),ｕy(t),t)＝ｍ(t)＋ｆ(t)ｐ(ｕx(t),ｕy(t),t)
ｈ2(t)＝Ｆ(ｖx(t),ｖy(t),t)＝ｍ(t)＋ｆ(t)ｐ(ｖx(t),ｖy(t),t)
次に、２式を辺々引き算して、次の式(17)を計算する。
【０１６３】
ｈ1(t)−ｈ2(t)＝ｆ(t)｛ｐ(ｕx(t),ｕy(t),t)−ｐ(ｖx(t),ｖy(t),t)｝
(17)
次に、ｈ1(t)−ｈ2(t)を因数分解して、最大次数を持つ因数をｆ(t)と定める。ここで、最大次数の因子がｆ(t)であるためには、ｆ(t)の次数をｌとした時、条件(18)を満たすようなｐ(x,y,t)を選択すれば必要十分である。
【０１６４】
deg(ｐ(ｕx(t),ｕy(t),t)−ｐ(ｖx(t),ｖy(t),t))＜ｌ        (18)
このためには、条件(19)の両方が成り立つように選択する必要がある。
【０１６５】
deg(ｐ(ｕx(t),ｕy(t),t))＜ｌ
deg(ｐ(ｖx(t),ｖy(t),t))＜ｌ
(19)
しかし、送信者にはセクションが秘匿されているので、ｆ(t)の次数ｌを十分大きく取るとともに、セクションの各要素である多項式ｕx(t),ｕy(t),ｖx(t),ｖy(t)における次数の最大値ｄを公開鍵として公開している。即ち、ｐ(x,y,t)を決定するときは条件式(14)を満たしていれば十分である。尚、ｈ1(t)−ｈ2(t)の因数分解は、１変数多項式の因数分解が容易であることから、十分有効な時間内に処理可能である。得られたｆ(t)でｈ1(t)を除すると（ｍ(t)の次数がｆ(t)の次数ｌ以下であることに注意すると）
ｈ1(t)＝ｍ(t)＋ｆ(t)ｐ(ｕx(t),ｕy(t),t)
の関係から、平文多項式ｍ(t)が得られる。
【０１６６】
得られた平文多項式ｍ(t)から平文埋め込み処理と逆の処理で平文ｍを求めることができる。ここで、ｍ(t)が剰余として一意的であることは特筆すべきことである。一意的でないと平文多項式ｍ(t)の候補が複数存在し、真の平文多項式を特定することが困難になる。ｍ(t)が一意的である理由は、ｈ1(t)が含まれる一変数多項式環Ｆ[t]では整数と同様に除法の定理が成立するため、一変数多項式を一変数多項式で割った商と剰余は一意的となるからである。なお、２変数以上の多項式では除法の定理が成立しないことが知られている。
【０１６７】
続いて、本実施形態のアルゴリズムが、後述するランダム化多項式判定問題が難しいと仮定すると、ＩＮＤ−ＣＰＡの意味で証明可能安全であることを説明する。まず、復号アルゴリズムは式(17)において、
｛ｐ(ｕx(t),ｕy(t),t)−ｐ(ｖx(t),ｖy(t),t)｝＝０
の場合、失敗する。しかしながら、この失敗は公開鍵であるｅに対して無視できる（negligible）確率でしか生じない。
【０１６８】
［命題１］  少なくとも２つの相異なるセクション
【数３６】
0004664850.tif 000019
を持つ有限体Ｆp上定義された代数曲面のファイブレーションＸ(x,y,t)＝０と３変数多項式ｐ(x,y,t)のx,yに関する指数の最大値ｅに対して、
ｐ(ｕx(t),ｕy(t),t)＝ｐ(ｖx(t),ｖy(t),t)    (20)
となる確率は１／ｐe+1である。
【０１６９】
［証明１］  Ｘ(x,y,t)の有する相異なるセクション(ｕx(t),ｕy(t),t),(ｖx(t),ｖy(t),t)においてｕx(t)≠ｖx(t)であるとする。もし、ｕx(t)＝ｖx(t)であった場合はｕy(t)≠ｖy(t)となり、以下の議論をｕy(t)≠ｖy(t)の仮定で同様に展開できる。
【０１７０】
さて、式(20)を満たすようなxにおいて指数の最大値ｅを取るｐ(x,y,t)が存在したとする。このとき、Ｆp上の任意の（ｅ−１）次以下の１変数多項式ｇ(x)（≠０）に対して、ｐ(x,y,t)＋ｇ(x)は式(20)を満たさない。なぜなら、もし満たしたとすると
ｇ(ｕx(t))＝ｇ(ｖx(t))
が成り立ち、有限体Ｆpを無限体にまで拡大したときに無限個の解を持つことになり、ｕx(t)＝ｖx(t)が従う。また、このように生成された式は、式(20)を満たすような別のｐ(x,y,t)から同様の手段で得られる多項式とは決して一致しない。実際、式(20)を満たす他のｐ1(x,y,t),ｐ2(x,y,t)と１変数多項式ｇ1(x),ｇ2(x)に対して
ｐ1(x,y,t)＋ｇ1(x)＝ｐ2(x,y,t)＋ｇ2(x)      (21)
であったとする。このとき
ｐ1(x,y,t)−ｐ2(x,y,t)＝ｇ2(x)−ｇ1(x)
となる。ここでｇ1(x)＝ｇ2(x)であるならばｐ1(x,y,t)＝ｐ2(x,y,t)となり矛盾するので、ｇ1(x)≠ｇ2(x)である。いま、ｇ(x)＝ｇ2(x)−ｇ1(x)とすると、ｐ1(x,y,t)−ｐ2(x,y,t)の性質から
ｇ(ｕx(t))＝ｇ(ｖx(t))
を満たすので、ｕx(t)＝ｖx(t)が従う。よって、式(21)を満たすような相異なる（ｐ1(x,y,t),ｇ1(t)）,（ｐ2(x,y,t),ｇ2(t)）の組は存在しない。尚、ｐ(x,y,t)がyにおいて指数の最大値をとった場合は、xとyの役割を変更することにより証明がそのまま成り立つ。
【０１７１】
以上のことから式(20)を満たす１つのＦp[x,y,t]上の３変数多項式ｐ(x,y,t)に対し、少なくともｐe+1個の式(20)を満たさない多項式を重複なく対応付けできる。よって、式(20)を満たすｐ(x,y,t)は高々１／ｐe+1の確率でしか生じない。
【０１７２】
代数曲面暗号の安全性は、以下の代数曲面暗号に関するランダム化多項式判定問題に依存している。
【０１７３】
［定義１］  代数曲面暗号に関するランダム化多項式判定問題
Ｆp上定義された次数ｄ以下の２つの相異なるセクションを有する代数曲面のファイブレーションＸ(x,y,t)＝０と自然数ｌが与えられた時、３変数多項式Ａ(x,y,t)が集合Ｓ
【数３７】
0004664850.tif 000020
に属するか否かを判定する問題を代数曲面暗号に関するランダム化多項式判定問題といい、代数曲面暗号に関することが明らかなときには単にランダム化多項式判定問題という。
【０１７４】
ランダム化多項式判定問題は、次数ｄ以下の２つの相異なるセクションを有する代数曲面のファイブレーションＸ(x,y,t)＝０と既約多項式ｆ(t)の最小次数ｌが与えられた時、与えられた多項式ｇ(x,y,t)が
ｆ(t)ｐ(x,y,t)＋Ｘ(x,y,t)ｑ(x,y,t)      (22)
という形に書けるか否かを判定する問題である。仮に、多項式ｇ(x,y,t)が２通り以上の書き方で式(22)の形に書けたとする。この場合、攻撃者（問題を解く人）は、複数の書き方のうちの１つの書き方を見出せばよいので、ランダム化多項式判定問題はそれだけ容易となる。しかしｐ(x,y,t)が条件(13)(14)、ｑ(x,y,t)が条件(15)を満たす限りにおいては、そのようなことはなく一意に書けることが以下のように示せる。
【０１７５】
［命題２］  多項式ｇ(x,y,t)が次数ｄ以下の２つの相異なるセクションを有する代数曲面のファイブレーションＸ(x,y,t)＝０と既約多項式ｆ(t)の最小次数ｌと、条件(13)(14)を満たすｐ(x,y,t)、条件(15)を満たすｑ(x,y,t)によって
ｆ(t)ｐ(x,y,t)＋Ｘ(x,y,t)ｑ(x,y,t)
のように書けるとき、その書き方は一意的である。
【０１７６】
［証明２］  ２通りの表現で、仮定のごとく書けるｇ(x,y,t)が存在したと仮定する。
【０１７７】
ｇ(x,y,t)＝ｆ1(t)ｐ1(x,y,t)＋Ｘ(x,y,t)ｑ1(x,y,t)
＝ｆ2(t)ｐ2(x,y,t)＋Ｘ(x,y,t)ｑ2(x,y,t)            (23)
仮定からＸ(x,y,t)は２つの相異なる次数ｄ以下のセクションを持つ代数曲面である。このため、各セクションを(ｕx(t),ｕy(t),t),(ｖx(t),ｖy(t),t)とすると、次式の関係がある。
【数３８】
0004664850.tif 000021
【０１７８】
ここで、命題１から無視できる（negligible）確率を除けば
ｐ1(ｕx(t),ｕy(t),t)−ｐ1(ｖx(t),ｖy(t),t)≠０
であるので、
ｐ2(ｕx(t),ｕy(t),t)−ｐ2(ｖx(t),ｖy(t),t)≠０
である。ｐ1(x,y,t),ｐ2(x,y,t)が条件(14)を満たすことから、次数の関係によって
ｆ2(t)＝ｃｆ1(t)となる。ここでｃは有限体Ｆpの元である。従って、式(23)の辺々を引いて前式を反映させると、次式を得る。
【０１７９】
ｆ1(t)(ｐ1(x,y,t)−ｃｐ2(x,y,t))＝Ｘ(x,y,t)(ｑ2(x,y,t)−ｑ1(x,y,t))
ここで、代数曲面Ｘ(x,y,t)の既約性から(ｆ(t),Ｘ(x,y,t))＝１となり、Ｆp[x,y,t]は一意分解整域である。このため、
ｆ1(t)｜ｑ2(x,y,t)−ｑ1(x,y,t)
が従う。ここでｑ(x,y,t)に対する条件(15)により、
degtｑ2(x,y,t)−ｑ1(x,y,t)＜deg ｆ1(t)
であるので
ｑ1(x,y,t)＝ｑ2(x,y,t)
となる。従って、
ｐ1(x,y,t)＝ｐ2(x,y,t)
となり、ｃ＝１即ち
ｆ1(t)＝ｆ2(t)
が従う。よって２つの表現は一致する。
【０１８０】
このようにランダム化多項式判定問題を解くには、一意的な解が存在する問題の解の有無を判定する必要がある。このため、ランダム多項式判定問題は容易に解けない。もちろん、求セクション問題が容易に解ければ、ランダム化多項式判定問題も容易に解ける。しかし、求セクション問題を解く以外にランダム化多項式判定問題を解く方法は知られていない。よって、ランダム化多項式判定問題も十分に難しい問題であると考えられる。
【０１８１】
また、命題から本発明の公開鍵暗号の復号結果が一意的であることが以下のように示される。
【０１８２】
［補題１］  少なくとも２つの次数ｄ以下の相異なるセクションを持つ代数曲面のファイブレーションＸ(x,y,t)＝０と既約多項式ｆ(t)の最小次数ｌに対応したランダム化多項式Ｇ(x,y,t)に対して、ｍ(t)＋Ｇ(x,y,t)はランダム化多項式とはならない。但し、ｍ(t)は０でない次数ｌ−１以下の１変数多項式である。
【０１８３】
［証明３］  ｍ(t)＋Ｇ(x,y,t)がランダム化多項式だとすると、式(24)を書ける。
【０１８４】
ｍ(t)＋Ｇ(x,y,t)＝ｆ1(t)ｐ1(x,y,t)＋Ｘ(x,y,t)ｑ1(x,y,t)
＝ｍ(t)＋ｆ2(t)ｐ2(x,y,t)＋Ｘ(x,y,t)ｑ2(x,y,t)
(24)
ここで、仮定からＸ(x,y,t)は２つのセクションを持つ代数曲面なので、それらのセクションを(ｕx(t),ｕy(t),t),(ｖx(t),ｖy(t),t)とすると、次式を書ける。
【数３９】
0004664850.tif 000022
【０１８５】
ここで、命題１から無視できる（negligible）確率を除けば
ｐ1(ｕx(t),ｕy(t),t)−ｐ1(ｖx(t),ｖy(t),t)≠０
であるので、
ｐ2(ｕx(t),ｕy(t),t)−ｐ2(ｖx(t),ｖy(t),t)≠０
となる。ｐ1(x,y,t),ｐ2(x,y,t)が条件(14)を満たすことから、次数の関係によって
ｆ2(t)＝ｃｆ1(t)
となる。よって、式(24)に(ｕx(t),ｕy(t),t)と前式を代入することで、
ｍ(t)＝ｆ1(t)｛ｐ1(ｕx(t),ｕy(t),t)−ｃｐ2(ｕx(t),ｕy(t),t)｝
を得る。しかし、これはdeg ｍ(t)≧ｌとなり矛盾する。従って、ｍ(t)＋Ｇ(x,y,t)はランダム化多項式とはならない。
【０１８６】
［定理１］
少なくとも２つのセクションを持つ代数曲面のファイブレーションＸ(x,y,t)＝０と既約多項式ｆ(t)の最小次数ｌと２つのセクションに含まれる１変数多項式の最大次数ｄに対応したランダム化多項式Ｇ(x,y,t)と、次数ｌ−１以下の１変数多項式ｍ(t)による表現ｍ(t)＋Ｇ(x,y,t)は一意的である。
【０１８７】
［証明４］
deg ｍ1(t),deg ｍ2(t)＜ｌを満たす１変数多項式ｍ1(t),ｍ2(t)とランダム化多項式Ｇ1(x,y,t),Ｇ2(x,y,t)に対して
ｍ1(t)＋Ｇ1(x,y,t)＝ｍ2(t)＋Ｇ2(x,y,t)
となる関係があったとする。このとき
ｍ1(t)−ｍ2(t)＋Ｇ1(x,y,t)
がランダム化多項式となる。すると補題１により、
ｍ1(t)＝ｍ2(t)
となり、
Ｇ1(x,y,t)＝Ｇ2(x,y,t)
が従う。よって表現は一意的である。
【０１８８】
次にこれらの結果に基づいて本実施形態の公開鍵暗号の安全性証明を行なう。
【０１８９】
［定義２］  ＩＮＤ−ＣＰＡ
Π：＝（Ｋ,Ｅ,Ｄ）を公開鍵暗号、これに対する確率的アルゴリズムＡ：＝（Ａ1,Ａ2）を考え、このアルゴリズムに対してセキュリティパラメータをｋ∈Ｎとして
【数４０】
0004664850.tif 000023
【０１９０】
パラメータｋは、公開鍵暗号の安全性の基本となる問題の難しさを表わす指標である。本発明の公開鍵暗号においては、ｐを固定した場合、ｄもしくはｌがパラメータとなる。実際、後述するパラメータ設計方法でも明らかになるようにｌはｄの関数であるため、ｄをパラメータと考えても良い。
【０１９１】
ここで、ＣＰＡは、平文を暗号化プログラムに掛け、出力されてくる暗号文を参考に適応的に平文を構成することを意味しており、アルゴリズムＡ（＝(Ａ1,Ａ2)）はＣＰＡを実行できることを仮定している。尚、以下で詳しく述べるようにアルゴリズムは大きく分けて２つのアルゴリズムＡ1とＡ2を有しているためＡ（＝(Ａ1,Ａ2)）のように記述する。
【０１９２】
次に、達成される安全性の基準であるＩＮＤに関して説明する。ＩＮＤとは、以下の手順（i）〜（iv）により得られた暗号文から元のメッセージを当てることができることを意味する。
【０１９３】
（i）  鍵生成アルゴリズムＫを使ってパラメータｋを満たすように生成した公開鍵と秘密鍵のペア（ｐｋ,ｓｋ）を出力させる。
【０１９４】
（ｐｋ,ｓｋ）←Ｋ（１k）
(ii)  鍵ペアのうち公開鍵ｐｋのみを知っているアルゴリズムＡ1が何度か適応的に平文を暗号化した後で、２つのメッセージｍ0,ｍ1を選択する。
【０１９５】
（x0,x1,ｓ）←Ａ1（ｐｋ）；
(iii)  暗号化オラクルと呼ばれる第３者にｍ0,ｍ1のどちらかを選んで暗号化させ、暗号文yを得たとする。
【０１９６】
ｂ←Ｒ｛０,１｝；y ←Ｅpk(xb)：
(iv)  得た暗号文yから対応するメッセージがｍ0であるかｍ1であるかをアルゴリズムＡ2を利用して当てる
Ａ2(x0,x1,ｓ,y)＝ｂ
一方、ＩＮＤにおいては、答えは０か１なのであるから、出鱈目に回答した場合１／２の確率で正解となる。そこで、正解率（成功確率）が１／２から隔たる度合いが問題となる。即ち、確率
【数４１】
0004664850.tif 000024
【０１９７】
無視できる(negligibleである)とはパラメータｋに対して確率が指数関数的に小さくなることである。例えば１／ｐlや１／ｐdなどはパラメータをｄとしたとき、無視できる(negligible)確率であるということができる。
【０１９８】
さて、ランダム化多項式判定問題が難しいとすると、代数曲面暗号の安全性を以下のように証明できる。
【０１９９】
［定理２］  代数曲面暗号がＩＮＤ−ＣＰＡの意味で安全であることと、ランダム化多項式判定問題が多項式時間で解けないこととは同値である。
【０２００】
［証明５］  代数曲面暗号ΠがＩＮＤ−ＣＰＡの意味で安全ならば、ランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けないことを示す。ランダム化多項式判定問題を多項式時間内に無視できない(non-negligible)確率ＡdvAで解くアルゴリズムＡが存在したとする。このとき、代数曲面暗号ΠをＩＮＤ−ＣＰＡの意味で解く敵Ｃ＝（Ｃ1,Ｃ2）を図１５に示すように構成できる。Ｃ1は、公開鍵として与えられたＸ,ｌ,ｄ,ｅが入力されると、公開鍵を使った何らかの処理を行い、２つの平文ｍ0(t),ｍ1(t)を暗号化オラクルεに出力する。暗号オラクルεは、入力された平文のうちの１つのｍb(t)を選んで、公開鍵を利用して暗号化し、暗号文Ｆ(x,y,t)を敵Ｃに返す。敵Ｃは、受け取った暗号文Ｆ(x,y,t)に対して
η0(x,y,t)＝Ｆ(x,y,t)−ｍ0(t)
を作成し、アルゴリズムＡによって結果Ｄ(η0,Ｓ)を得る。ここで、Ｄ(η,Ｓ)は｛０,１｝を値域として取る関数で、多項式ηがランダム化多項式の集合Ｓに属する場合１、属さない場合０とする。敵Ｃは、Ｄ(η0,Ｓ)の値が０ならばｂ＝１を、Ｄ(η0,Ｓ)値が１ならばｂ＝０を出力する。以上の処理はアルゴリズムＡが多項式時間で終了することを仮定しているので、多項式時間で終了する。
【数４２】
0004664850.tif 000025
【０２０１】
次に、ランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けないならば、代数曲面暗号ΠがＩＮＤ−ＣＰＡの意味で安全であることを示す。代数曲面暗号ΠがＩＮＤ−ＣＰＡの意味で安全でないとする。このとき、代数曲面暗号ΠをＩＮＤ−ＣＰＡの意味で破る敵Ａ＝(Ａ1,Ａ2)が存在する。この敵Ａを仮定してランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けるアルゴリズムＡが存在することを示す。即ち、アルゴリズムＡはランダム化多項式集合Ｓ（＝Ｓ(Ｘ,ｌ,ｄ)）と多項式η(x,y,t)が与えられたとき、η(x,y,t)がＳに属するか否かを図１６のように判定する。図１６において、ランダム化多項式集合のパラメータＸ,ｌ,ｄを公開鍵とする公開鍵暗号Πを考え、Ｘ,ｌ,ｄを公開鍵として敵Ａ＝（Ａ1,Ａ2）に入力する（ＳＴ２１）。Ａ1は平文ｍ0(t),ｍ1(t)を暗号化オラクルεに出力する。暗号化オラクルεはｂを集合｛０,１｝からランダムに選択し、暗号文Ｆ(x,y,t)（＝ｍb(t)＋η(x,y,t)）を生成することによりシミュレートされる（ＳＴ２２）。敵Ａは暗号オラクルによって生成された暗号文Ｆ(x,y,t)を受け取って（Ａ2において）多項式時間内に終了するアルゴリズムで処理し、ｂ’を出力する（ＳＴ２３）。ここでｂ’＝ｂであればＤ(η,Ｓ)＝１、ｂ’≠ｂであればＤ(η,Ｓ)＝０とする。アルゴリズムＡは明らかに多項式時間内に終了する。次にＡdvAを以下のように評価する。ここで、Ｇ＝Ｆp[x,y,t],Ｒ＝Ｇ−Ｓと定義する。
【数４３】
0004664850.tif 000026
【０２０２】
【数４４】
0004664850.tif 000027
【０２０３】
［パラメータの設定方法］
本節では、上述した議論でその安全性がランダム化多項式判定問題に帰着された本発明の公開鍵暗号に関し、パラメータの具体的な設定方法を説明する。
【０２０４】
本発明の公開鍵暗号のパラメータは、有限体Ｆpのサイズｐとセクションの最高次数ｄである。また１変数多項式ｆ(t)の次数l(d)は条件(14)から
l(d)＝(2d＋１)e(d)＋１      (25)
とすれば良いことが分かる。また、３変数多項式ｐ(x,y,t)のx,yの最大指数e(d)は復号の失敗確率に関するパラメータである。失敗確率は命題１により１／ｐe(d)+1である。従って、失敗確率を２nとしたければ、
(|ｐ|−１)(e(d)＋１)＞ｎ
を満たすようにとれば良い。ここで|ｐ|はｐのビット長を表す。
【０２０５】
（第３の実施形態の具体的な構成）
次に、本実施形態の公開鍵暗号における暗号装置、復号装置の具体的な構成とそのアルゴリズムについて説明する。図１７は本発明の第３の実施形態に係る暗号装置の全体構成図であり、図１８は同実施形態における復号装置の全体構成図である。
【０２０６】
ここで、暗号装置３０は、図１７に示すように、平文入力部３１、公開鍵入力部３２、平文埋め込み部３３、暗号化部３４、１変数既約多項式生成部３５、多項式生成部３６及び暗号文出力部３７を備えている。また、暗号装置３０は、図示しないメモリ（ハードウェア資源）を有し、各部３１〜３７から入力データ、出力データ及び処理中のデータ等が適宜読出／書込可能となっている。
【０２０７】
ここで、平文入力部３１は、外部から入力された平文（メッセージ）ｍを一時的にメモリに保持し、この平文ｍを平文埋め込み部３３に送出する機能をもっている。
【０２０８】
公開鍵入力部３２は、外部から入力された公開鍵を一時的にメモリに保持し、この公開鍵を平文埋め込み部３３及び暗号化部３４に送出する機能をもっている。
【０２０９】
平文埋め込み部３３は、平文入力部３１から受けた平文ｍ及び公開鍵入力部３２から受けた公開鍵に基づいて、平文ｍを１変数tで次数ｌ-１以下の平文多項式ｍ(t)の係数として埋め込む機能と、得られた平文多項式ｍ(t)を暗号化部３４に送出する機能をもっている。
【０２１０】
暗号化部３４は、平文埋め込み部３３から受けた平文多項式ｍ(t)及び公開鍵入力部３２から受けた公開鍵Ｘ(x,y,t),ｐ,ｌ,ｄ,ｅに基づいて、図１９に示す動作を実行するように、後段の各部３５〜３７を制御するものである。特に、暗号化部３４は、平文多項式ｍ(t)に対し、各多項式ｐ(x,y,t),ｑ(x,y,t),ｆ(t)とファイブレーションＸ(x,y,t)とを加算、減算及び乗算のうち少なくとも一つを含む演算を行う暗号化処理により、平文多項式ｍ(t)から暗号文Ｆ(x,y,t)（＝Ｅpk(ｍ,ｐ,ｑ,ｆ,Ｘ)）を生成する機能をもっている。
【０２１１】
１変数既約多項式生成部３５は、暗号化部３４に制御され、次数ｌ以上のランダムな１変数既約多項式ｆ(t)を生成する機能をもっている。
【０２１２】
多項式生成部３６は、暗号化部３４に制御され、３変数x,y,tのランダムな多項式ｐ(x,y,t),ｑ(x,y,t)を生成する機能をもっている。
【０２１３】
暗号文出力部３７は、暗号化部３４により生成された暗号文Ｆ(x,y,t)を出力する機能をもっている。
【０２１４】
一方、復号装置４０は、図１８に示すように、暗号文入力部４１、鍵入力部４２、復号部４３、セクション代入部４４、１変数多項式演算部４５、１変数多項式因数分解部４６、多項式抽出部４７、１変数多項式剰余演算部４８、平文展開部４９及び平文出力部５０を備えている。また、復号装置４０は、図示しないメモリ（ハードウェア資源）を有し、各部４１〜５０から入力データ、出力データ及び処理中のデータ等が適宜読出／書込可能となっている。
【０２１５】
暗号文入力部４１は、外部から入力された暗号文Ｆを一時的にメモリに保持し、この暗号文Ｆを復号部４３に送出する機能をもっている。
【０２１６】
鍵入力部４２は、外部から入力された公開鍵を一時的にメモリに保持し、この公開鍵を復号部４３に送出する機能をもっている。
【０２１７】
復号部４３は、図２０に示す動作を実行するように、後段の各部４４〜２９を制御する機能をもっている。
【０２１８】
セクション代入部４４は、復号部４３に制御され、入力された暗号文Ｆに対し、各セクションＤ1,Ｄ2を代入して２つの１変数多項式ｈ1(t),ｈ2(t)を生成する機能をもっている。
【０２１９】
１変数多項式演算部４５は、復号部４３に制御され、各１変数多項式ｈ1(t),ｈ2(t)を互いに減算し、減算結果｛ｈ1(t)−ｈ2(t)｝を得る機能をもっている。
【０２２０】
１変数多項式因数分解部４６は、復号部４３に制御され、減算結果｛ｈ1(t)−ｈ2(t)｝を因数分解する機能をもっている。
【０２２１】
多項式抽出部４７は、復号部４３に制御され、因数分解結果から最も大きな次数を持つ既約多項式ｆ(t)を抽出する機能をもっている。
【０２２２】
１変数多項式剰余演算部４８は、復号部４３に制御され、１変数多項式ｈ1(t)を既約多項式ｆ(t)で除算し、剰余として平文多項式ｍ(t)を得る機能をもっている。
【０２２３】
平文展開部４９は、復号部４３から受けた平文多項式ｍ(t)の係数から平文ｍを抽出する機能をもっている。
【０２２４】
平文出力部５０は、平文展開部４９から受けた平文ｍを出力する機能をもっている。
【０２２５】
次に、以上のように構成された暗号装置及び復号装置の動作を図１９及び図２０のフローチャートを用いて説明する。
【０２２６】
（暗号化処理：図１９）
暗号装置３０においては、平文入力部３０から平文（メッセージ）ｍが入力され（ＳＴ３１）、公開鍵入力部３２から公開鍵Ｘ(x,y,t),ｐ,ｌ,ｄ,ｅが入力されると（ＳＴ３２）、暗号化処理を開始する。入力された公開鍵のうち、１変数既約多項式ｆ(t)の次数であるｌと素体の標数ｐとが取得され（ＳＴ３３）、ｌ，ｐが平文埋め込み部３３に送られる。
【０２２７】
平文埋め込み部３３では、別途、平文入力部３１から送出された平文ｍを標数ｐのビット長よりも１小さいビット長に分割する。例えばｐ＝１７の場合は４ビットに分割する。ここで、平文ｍが１６進表示で
ｍ＝０x３１５７６３ｅｆ２５ｃ０４ｃ７９２ｅｆ１５１
であるとする。
【０２２８】
この場合、平文埋め込み部３３は、１６進表示の平文ｍを４ビット毎に分割し、平文多項式ｍ(t)の係数として次式のように埋め込む（ＳＴ３４）。
【０２２９】
ｍ(t)＝３t21＋t20＋５t19＋７t18＋６t17＋３t16＋１５t15＋１１t14＋２t13 
＋５t12＋１２t11＋０t10＋４t9＋１２t8＋７t7＋９t6＋２t5＋１４t4 
＋１５t3＋t2＋５t＋１
平文埋め込み部３３は、平文多項式ｍ(t)を暗号化部３４に送信する。一方で、公開鍵入力部３２は、公開鍵Ｘ(x,y,t),ｐ,ｌ,ｄ,ｅを暗号化部３４に送信する。
【０２３０】
暗号化部３４では、公開鍵のうち、ｌとｐを１変数既約多項式生成部３５に送信する。
【０２３１】
１変数既約多項式生成部３５は、ｌ次の１変数既約多項式ｆ(t)をランダムに生成し（ＳＴ３５）、得られた１変数既約多項式ｆ(t)を暗号化部３４に返信する。ここで、既約多項式の生成は、ｌ次の多項式をランダムに生成し、得られる１変数多項式が既約多項式となるまでＦp上の既約性判定を繰り返すことにより行う。
【０２３２】
暗号化部３４は、１変数既約多項式ｆ(t)を得ると、多項式生成部３６にｐ,ｌ,ｄ,ｅを送信する。多項式生成部３６は、ｐ,ｌ,ｄ,ｅに基づいて、３変数多項式の各項が次数に関する関係式(13)と条件(14)を満たすようにランダムな３変数多項式ｐ(x,y,t)を生成する（ＳＴ３６）。生成方法としては、ランダムに生成した後、２つの条件を満たすことをチェックし、満たさなかった時には再度ランダムに生成する方法と、２条件に合うように、生成する３変数多項式に制約を掛ける方法がある。いずれの方法にしても、条件(13)(14)の範囲にて十分に多様な係数を取りえるため、実行可能な時間内で生成が終了する。多項式生成部３６は、得られた３変数多項式ｐ(x,y,t)を暗号化部３４に送信する。
【０２３３】
暗号化部３４は、３変数多項式ｐ(x,y,t)を受けると、公開鍵のうちｐ,ｌ,ｄ,ｅを多項式生成部３６に送信する。多項式生成部３６は、ｐ,ｌ,ｄ,ｅに基づいて、条件(５)を満たすように３変数のランダムな多項式ｑ(x,y,t)を生成し（ＳＴ３７）、得られた３変数多項式ｑ(x,y,t)を暗号化部３４に送信する。
【０２３４】
暗号化部３４は、以上の処理で得られたｍ(t),ｆ(t),ｐ(x,y,t),ｑ(x,y,t)と、公開鍵である代数曲面Ｘ(x,y,t)を利用して、式(16)に従って暗号文Ｆ(x,y,t)を計算し展開する（ＳＴ３８）。暗号化部３４は、この暗号文を暗号文出力部３７から出力し（ＳＴ３９）、暗号化処理を終了する。なお、暗号化部３４は、必要により、暗号文を予め定められたフォーマットに合わせて変形して暗号文出力部３７から出力してもよい。
【０２３５】
（復号処理：図２０）
復号装置４０においては、暗号文入力部４１から暗号文Ｆ(x,y,t)を取得し（ＳＴ４１）、鍵入力部４２から公開鍵Ｘ(x,y,t),ｐと秘密鍵を取得すると（ＳＴ４２）、復号処理を開始する。秘密鍵は２つのセクションＤ1,Ｄ2である。取得された暗号文と鍵情報は復号部４３に送られる。
【０２３６】
復号部４３は、セクション代入部４４に暗号文Ｆ(x,y,t)とセクションＤ1を送信する。セクション代入部４４は、Ｄ1をＦ(x,y,t)に代入し、必要に応じて１変数多項式演算部４５を利用することにより、ｈ1(t)を得る（ＳＴ４３）。ここで、１変数多項式演算部４５は１変数多項式の加減乗除演算を行う。得られたｈ1(t)は、セクション代入部４４から復号部４３に送信される。
【０２３７】
また同様に、復号部４３は、セクション代入部４４に暗号文Ｆ(x,y,t)とセクションＤ2を送信する。セクション代入部４４は、セクションＤ2をＦ(x,y,t)に代入し、ｈ2(t)を得る（ＳＴ４４）。得られたｈ2(t)は、セクション代入部４４から復号部４３に送信される。
【０２３８】
復号部４３は、ｈ1(t),ｈ2(t)を１変数多項式演算部４５に送信して減算させる。１変数多項式演算部４５は、減算結果｛ｈ1(t)−ｈ2(t)｝を復号部４３に送信する。
【０２３９】
復号部４３は、減算結果｛ｈ1(t)−ｈ2(t)｝を１変数多項式因数分解部４６に送信して因数分解させる（ＳＴ４５）。１変数多項式因数分解部４６は、因数分解結果のうち、最大次数の因子として既約多項式ｆ(t)を決定し（ＳＴ４６）、この既約多項式ｆ(t)を復号部４３に送信する。
【０２４０】
次に、復号部４３は、ｆ(t),ｈ1(t)を１変数多項式剰余演算部４８に送信する。
【０２４１】
１変数多項式剰余演算部４８は、ｈ1(t)をｆ(t)で除し、剰余として平文多項式ｍ(t)を計算し（ＳＴ４７）、復号部４３に送信する。
【０２４２】
復号部４３では、ｍ(t)を平文展開部４９に送信する。平文展開部４９はこの平文多項式ｍ(ｔ)から平文ｍを展開し、得られた平文ｍを平文出力部５０に送信する。平文出力部５０はこの平文ｍを出力する（ＳＴ４９）。これにより、復号装置４０は、復号処理を終了する。
【０２４３】
上述したように本実施形態によれば、第１又は第２の実施形態の効果に加え、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある証明可能安全な公開鍵暗号方式を構成することができる。
【０２４４】
補足すると、本実施形態によれば、復号用の秘密鍵が代数曲面ＸのファイブレーションＸ(x,y,t)＝０に対応する２つ以上のセクションであり、公開鍵が代数曲面ＸのファイブレーションＸ(x,y,t)であるという構成により、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある公開鍵暗号方式を構成できる。
【０２４５】
また、本実施形態によれば、次数ｌ-１以下の平文多項式ｍ(t)と、次数ｌ以上のランダムな１変数既約多項式ｆ(t)とを用いる構成により、前述した証明５に基づいて、ＩＮＤ−ＣＰＡの意味で証明可能安全な公開鍵暗号方式を構成できる。
【０２４６】
＜第３の実施形態のバリエーション＞
第６のバリエーションは、本実施形態の公開鍵におけるｐ,ｌ,ｄ,ｅを固定パラメータとする構成により、公開鍵のサイズを減らすバリエーションである。勿論これらの一部だけを固定にする利用方法も考えられる。
【０２４７】
本バリエーションにおいては、パラメータの一部が固定されることから、鍵生成時に制約があるものの、十分大きいｌ,ｄ,ｅが取られていれば、何回かの試行で所望の公開鍵Ｘ(x,y,t)を生成可能である。
【０２４８】
第７のバリエーションは、暗号化に用いる式(16)の変形に関するバリエーションである。式(16)は、例えば
Ｆ(x,y,t)＝ｍ(t)−ｆ(t)ｐ(x,y,t)−Ｘ(x,y,t)ｑ(x,y,t)
のように変形しても同様に暗号化／復号が可能であり、同様の安全性が証明可能である。このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することが十分可能である。
【０２４９】
第８のバリエーションは、平文ｍを１変数既約多項式ｆ(t)にも埋め込む方式である。前述した実施形態ではｆ(t)をランダムに生成する方式を示したが、秘密鍵無しにｆ(t)を求めることが困難であることも本発明の公開鍵暗号の性質であるから、ｆ(t)にも平文情報を埋め込む方式が実現可能となっている。
【０２５０】
ｆ(t)にも平文ｍを埋め込む場合、より大きなサイズの平文を一度に暗号化できる。但し、埋め込んだ結果ｆ(t)を既約多項式とする必要から、特定の係数にはランダムな係数が入るように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文ｍを埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。仮に得られなかった場合にはｆ(t)の次数を上げることにより、探索範囲を増やすことも可能である。このような変形を施しても同様の安全性を証明可能となっている。
【０２５１】
第９のバリエーションは、公開鍵から３変数多項式ｐ(x,y,t)のx,yの最高指数としてのパラメータｅを除く方式である。このパラメータｅは、命題１に示したように、復号の失敗確率を表現する時の指数になるものである。即ち、安全性に関して直接の指標にならないため、復号失敗時には（ｐ(x,y,t)を変更して）再暗号化する規則にすれば、パラメータｅを公開鍵から外す実施形態も可能である。このような実施形態をとることにより、公開鍵サイズが小さくなる他、ｐ(x,y,t)の生成を必要以上に制限する必要がなくなる。
【０２５２】
（第４の実施形態）
次に、本発明の第４の実施形態について説明する。本実施形態の公開鍵と秘密鍵は、第３の実施形態と同じである。本実施形態の公開鍵暗号は、受動的な攻撃に関して安全性（ＩＮＤ−ＣＰＡ）を保証した第３の実施形態に比べ、より高い安全性を保証するものであり、具体的には、能動的な攻撃に関しても安全性（ＩＮＤ−ＣＣＡ）を保証する。
【０２５３】
本実施形態は、第３の実施形態に示した公開鍵暗号がＩＮＤ−ＣＰＡの意味での安全性を有することから、特許第３３０６３８４号公報に記載されている変換を用いることによってＩＮＤ−ＣＣＡの意味で安全な公開鍵暗号を構成する。
【数４５】
0004664850.tif 000028
のように実行する。即ち、平文ｍとランダム要素ｒ（第３の実施形態では３変数多項式ｐ(x,y,t),ｑ(x,y,t)や一変数多項式ｆ(t)の各因子の係数などにあたる）に基づいて暗号化されていた公開鍵を、ｍ‖ｒを平文として、ｍ‖ｒのハッシュ値Ｈ(ｍ‖ｒ)をランダム要素として暗号化する方式に変換する。
【０２５４】
これに伴い復号処理においては、第３の実施形態と同様の復号処理で復号した後、平文ｍ‖ｒから真のメッセージであるｍを抽出すると共に、平文ｍ‖ｒのハッシュ値Ｈ(ｍ‖ｒ)を計算し、Ｈ(ｍ‖ｒ)をランダム要素とする暗号文Ｆ’(x,y,t)を再現して入力された暗号文Ｆ(x,y,t)と比較し、一致している場合には復号された平文ｍを出力する。一致していない場合には復号結果を出力せず、無効な暗号文である旨の出力を行なう。
【０２５５】
しかし、特許第３３０６３８４号公報に記載の変換は、強い意味での安全性を主張するため、暗号文にある種の構造を持たせることから、第３の実施形態のようなランダム性の強い暗号文の構成が難しくなる。これに伴い、特許第３３０６３８４号公報に記載の暗号化の方式自体は（ランダム性という側面からみれば）弱いアルゴリズムとなっている。例えばｐ(x,y,t),ｑ(x,y,t)で用いる多項式の項の種類、即ち
【数４６】
0004664850.tif 000029
において出現する項xiyjtkやxlymtnを決めておき、係数ａi,j,k,ｂl,m,nにランダム要素Ｈ(ｍ‖ｒ)を割り振るような単純な変換を施すだけでは安全な方式を構成することができない。一方、本実施形態では、安全性を保ったまま変換を実施する具体的な方式を示す。
【０２５６】
（第４の実施形態の具体的な構成）
次に、本発明の第４の実施形態について説明する。なお、本実施形態の公開鍵と秘密鍵は第３の実施形態と同様なので、説明を省略する。鍵生成に関しても第３の実施形態と同様である。
【０２５７】
図２１は本発明の第４の実施形態に係る暗号装置の全体構成図であり、図２２は同実施形態における復号装置の全体構成図であって、図１７又は図１８と同一部分については同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【０２５８】
すなわち、本実施形態は、第３の実施形態の変形例であり、前述した通り、より高い安全性を保証するものであって、平文ｍに乱数ｒを連結してｍ‖ｒとし、このｍ‖ｒのハッシュ値Ｈ(ｍ‖ｒ)をランダム要素として用いている。
【０２５９】
具体的には、暗号装置３０においては、平文埋め込み部３３’、暗号化部３４’及び多項式生成部３６’が若干変形されており、乱数生成部３８が付加されている。また、復号装置４０においては、平文展開部４９’及び平文出力部５０’が若干変形されており、暗号文検証部５１が付加されている。
【０２６０】
ここで、平文埋め込み部３３’は、平文入力部３１から送出された平文（メッセージ）ｍを受け、且つ公開鍵入力部３２から送出された公開鍵を受けたとき、乱数生成部３８に乱数生成を指示する機能と、平文ｍと乱数ｒとを連結して新たな平文Ｍ（＝ｍ‖ｒ）を生成する機能と、公開鍵に基づいて、平文Ｍを１変数tで次数ｌ-１以下の平文多項式Ｍ(t)の係数として埋め込む機能をもっている。
【０２６１】
暗号化部３４’は、前述した機能に加え、図２３〜図２５に示す動作を実現させるように、多項式生成部３６’を制御する機能をもっている。
【０２６２】
多項式生成部３６’は、暗号化部３４’に制御され、平文Ｍのハッシュ値Ｈ(M)に基づいて３変数x,y,tのランダムな多項式ｐ(x,y,t),ｑ(x,y,t)を生成するものである。多項式生成部３６’は、平文Ｍのハッシュ値Ｈ(M)に基づいて３変数x,y,tのランダムな多項式ｐ(x,y,t),ｑ(x,y,t)の各項のx指数、y指数、t指数及び係数のうち、少なくとも２つ以上を生成する機能をもっている。
【０２６３】
乱数生成部３８は、平文埋め込み部３３’に制御され、固定長の乱数ｒを生成する機能と、生成した乱数ｒを平文埋め込み部３３’に送出する機能とをもっている。
【０２６４】
一方、平文展開部４９’は、復号部４３から受けた平文多項式Ｍ(t)の係数から平文Ｍを抽出する機能と、この平文Ｍを暗号文検証部５１に送出する機能とをもっている。
【０２６５】
平文出力部５０’は、暗号文検証部５１による判定結果が一致の場合、暗号文検証部５１から受けた平文Ｍ又はメッセージｍを出力する機能と、この判定結果が否の場合、暗号文無効情報を出力する機能をもっている。
【０２６６】
暗号文検証部５１は、平文展開部４９’により得られた平文Ｍに基づいて、この平文Ｍのハッシュ値Ｈ(M)を演算する機能と、得られたハッシュ値Ｈ(M)をメモリ（図示せず）に保持する機能と、メモリ内のハッシュ値Ｈ(M)に基づいて、３変数x,y,tの多項式ｐ(x,y,t),ｑ(x,y,t)を生成する機能と、各多項式ｐ(x,y,t),ｑ(x,y,t),ｆ(t)とファイブレーションＸ(x,y,t)とに基づいて、暗号装置３０の暗号化処理と同じ処理により、暗号文Ｆ’(x,y,t)（＝Ｅpk(Ｍ,ｐ,ｑ,ｆ,Ｘ)）を再現する機能と、入力された暗号文Ｆ(x,y,t)と再現された暗号文Ｆ’(x,y,t)とが一致するか否かを判定する機能と、判定結果に応じて平文出力部５０’を制御する機能とをもっている。
【０２６７】
次に、以上のように構成された暗号装置及び復号装置の動作を図２３〜図２６のフローチャートを用いて説明する。
【０２６８】
（暗号化処理：図２３〜図２５）
ステップＳＴ３１〜ＳＴ３３までの処理は、前述した通りに実行される。
【０２６９】
次に、平文埋め込み部３３’は、平文入力部３１から入力された平文ｍに対し、乱数生成部３８に乱数生成を指示する。乱数生成部３８は、この指示により、固定長の乱数ｒを生成して平文埋め込み部３３’に送信する（ＳＴ３４’−１）。
【０２７０】
平文埋め込み部３３’は、受信した乱数ｒを平文ｍに連結してＭ(＝ｍ‖ｒ)を生成すると共に（ＳＴ３４’−２）、Ｍを新たな平文として平文多項式Ｍ(t)を第３の実施形態と同じ処理で生成する（ＳＴ３４’−３）。
【０２７１】
次に、本実施形態における３変数多項式ｐ(x,y,t),ｑ(x,y,t)の生成処理について説明する。暗号化部３４’は、１変数既約多項式ｆ(t)を１変数既約多項式生成部３５に生成させた後（ＳＴ３５）、Ｍ(＝ｍ‖ｒ)のハッシュ値Ｈ(ｍ‖ｒ)を計算する（ＳＴ３６’−１）。次に、暗号化部３４’は、多項式生成部３６’にｐ,ｌ,ｄ,ｅ及びＨ(ｍ‖ｒ)を送信する。
【０２７２】
多項式生成部３６’は、ｐ,ｌ,ｄ,ｅ及びＨ(ｍ‖ｒ)に基づいて、３変数多項式ｐ(x,y,t),ｑ(x,y,t)の各項がハッシュ値Ｈ(ｍ‖ｒ)の値を反映するように、３変数多項式ｐ(x,y,t),ｑ(x,y,t)を生成する。このとき、ｐ(x,y,t)は、条件(13)と条件(14)を満たし、最高次数をｅ以上とするように、生成される。ｑ(x,y,t)は、条件(15)を満たすように生成される。具体的な生成方法は以下の通りである。
【０２７３】
ｅx,ｅy,ｅtをｅx,ｅy がそれぞれdegxＸ(x,y,t),degyＸ(x,y,t)を超える自然数であり、かつ(ｅx＋ｅy)ｄ＋ｅt＜ｌを満たすように定める（ＳＴ３６’−２）。このようなｅx,ｅy,ｅtはｌを十分大きくとっているので具体的に定めることができる。
【０２７４】
更に、生成される多項式ｑ(x,y,t)が条件(15)を満足するためにｄx,ｄy,ｄtをｄt＜ｌなる条件の下で定める（ＳＴ３６’−３）。続いて、次式に示すように、ブロックサイズｂp,ｂqを定める（ＳＴ３６’−４）。
【０２７５】
ｂp＝|ｐ|＋|ｅx|＋|ｅy|＋|ｅt|,
ｂq＝|ｐ|＋|ｄx|＋|ｄy|＋|ｄt|
ここで、|ａ|はａのビット長を意味する。また、ｂpはｐ(x,y,t)の１つの項ａi,j,kxiyjtkを生成するために必要なブロックサイズである。同様にｂqはｑ(x,y,t)の１つの項ｂi,j,kxiyjtkを生成するために必要なブロックサイズである。
【０２７６】
これを受けて、Ｈ(ｍ‖ｒ)の前半分をｂpビットずつｇブロックに、後半分をｂqビットずつｈブロックに分解して
Ｈ(ｍ‖ｒ)＝α1‖・・・‖αg‖β1‖・・・‖βh
とする（ＳＴ３６−５’）。
【０２７７】
そしてｐ(x,y,t)＝０として（ＳＴ３６’−６）、３変数ランダム多項式ｐ(x,y,t)を条件(14)を満たすように生成する。具体的には、Ｈ(ｍ‖ｒ)の前半分α1‖α2‖・・・‖αgの各ブロックに対して以下の操作をｎ＝１・・・,ｇにおいて繰り返し行なう（ＳＴ３６’−７〜ＳＴ３６’−９）。
【０２７８】
ここで、ブロックの各αnは
|γ0|＝|ｐ|,|γ1|＝|ｅx|,|γ2|＝|ｅy|,|γ3|＝|ｅt|
の大きさで
αn＝γ0(n)‖γ1(n)‖γ2(n)‖γ3(n)
のごとく分割される（ＳＴ３６’−７）。
【０２７９】
ａ＝γ0(n)  (ｍｏｄ  ｐ)
ｉ＝γ1(n)  (ｍｏｄ  ｅx)
ｊ＝γ2(n)  (ｍｏｄ  ｅy)
ｋ＝γ3(n)  (ｍｏｄ  ｅt)
（ＳＴ３６’−８）
ｐ(x,y,t)＋＝ａxiyjtk      （ＳＴ３６’−９）
なお、記号“＋＝”は、左辺に右辺を足し込む旨を意味する。
【０２８０】
このようにして完成されたｐ(x,y,t)は、条件(13)を満たすか否かが判定され（ＳＴ３６’−１０）、否の場合、多項式生成部３６’は、暗号化部３４’にその旨を出力する。
【０２８１】
暗号化部３４’では、ステップＳＴ３３終了後の状態に戻り、平文埋め込み部３３’に対して平文の再埋め込みを指示する。以下、前述同様に、ステップＳＴ３４〜ＳＴ３６’−１０までの処理が再度、実行される。
【０２８２】
一方、ステップＳＴ３６’−１０の判定の結果、ｐ(x,y,t)が条件(13)を満たしたとする。この場合、ｑ(x,y,t)＝０として（ＳＴ３７’−１）、３変数ランダム多項式ｑ(x,y,t)を条件(15)を満たすように生成する。具体的には、Ｈ(ｍ‖ｒ)の後半分β1‖β2‖・・・‖βhの各ブロックに対して以下の操作をｍ＝１・・・,ｈにおいて繰り返し行なう（ＳＴ３７’−２〜ＳＴ３７’−４）。
【０２８３】
ここで、ブロックの各βmは
|ζ0|＝|ｐ|,|ζ1|＝|ｄx|,|ζ2|＝|ｄy|,|ζ3|＝|ｄt|
の大きさで
βn＝ζ0(m)‖ζ1(m)‖ζ2(m)‖ζ3(m)
のごとく分割される（ＳＴ３７’−２）。
【０２８４】
ｂ＝ζ0(m)  (ｍｏｄ  ｐ)
ｉ＝ζ1(m)  (ｍｏｄ  ｄx)
ｊ＝ζ2(m)  (ｍｏｄ  ｄy)
ｋ＝ζ3(m)  (ｍｏｄ  ｄt)
（ＳＴ３７’−３）
ｑ(x,y,t)＋＝ｂxiyjtk        （ＳＴ３７’−４）
これにより、３変数多項式ｑ(x,y,t)が生成される。多項式生成部３６’は、これら３変数多項式ｐ(x,y,t),ｑ(x,y,t)を暗号化部３４’に出力する。
【０２８５】
暗号化部３４’は、Ｍ(t),ｆ(t),ｐ(x,y,t),ｑ(x,y,t)を用いて
Ｆ(x,y,t)＝Ｍ(t)＋ｆ(t)ｐ(x,y,t)＋Ｘ(x,y,t)ｑ(x,y,t)によって暗号文Ｆ(x,y,t)を計算する（ＳＴ３８’）。得られた暗号文Ｆ(x,y,t)は、前述同様に、暗号文出力部３７から出力される（ＳＴ３９）。
【０２８６】
（復号処理：図２６）
ステップＳＴ４１〜ＳＴ４７までの処理は、前述した通りに実行される。これにより、復号部４３では、ステップＳＴ４１で入力された暗号文Ｆ(x,y,t)から、平文多項式Ｍ(t)が得られる。
【０２８７】
復号部４３は、この平文多項式Ｍ(t)を平文展開部４９’に送信する。平文展開部４９’は、この平文多項式Ｍ(t)から平文Ｍを展開し（ＳＴ４８’−１）、得られた平文Ｍを暗号文検証部５１に送る。
【０２８８】
暗号文検証部５１では、この平文Ｍからハッシュ値Ｈ(ｍ‖ｒ)を計算し（ＳＴ４８’−２）、得られたＨ(ｍ‖ｒ)から暗号装置３０の暗号化処理と同じ処理により、３変数多項式ｐ(x,y,t),ｑ(x,y,t)を生成する（ＳＴ４８’−３）。次に、暗号文検証部５１は、３変数多項式ｐ(x,y,t),ｑ(x,y,t)と、先に得られているｆ(t),Ｍ(t)とに基づいて、暗号文Ｆ’(x,y,t)を再現する（ＳＴ４８’−４）。
【０２８９】
しかる後、暗号文検証部５１は、ステップＳＴ４１で入力された暗号文Ｆ(x,y,t)と、ステップＳＴ４８’−４で再現した暗号文Ｆ’(x,y,t)とが一致するか否かを判定する（ＳＴ４８’−５）。
【０２９０】
この判定結果が否の場合、暗号文検証部５１は、平文出力部５０’に暗号文が無効である旨の信号を送り、平文出力部５０’は暗号文無効情報を出力する（ＳＴ４８’−６）。
【０２９１】
一方、ステップ２８’−５の判定結果が一致を示す場合、暗号文検証部５１は、平文出力部５０’に平文Ｍを送る。平文出力部５０’は、平文Ｍを真の平文ｍに変換し、平文ｍを出力する（ＳＴ４９）。
【０２９２】
上述したように本実施形態によれば、第３の実施形態の効果に加え、第４の実施形態のＩＮＤ−ＣＰＡよりも安全であるＩＮＤ−ＣＣＡの意味で証明可能安全な公開鍵暗号方式を構成することができる。
【０２９３】
補足すると、本実施形態では、メッセージｍと乱数ｒを連結した平文Ｍを平文多項式Ｍ(t)の係数として埋め込む構成により、ＩＮＤ−ＣＰＡの意味で安全な公開鍵暗号方式を、ＩＮＤ−ＣＣＡの意味で証明可能安全な公開鍵暗号方式に変換している。従って、本実施形態によれば、ＩＮＤ−ＣＣＡの意味で証明可能安全な公開鍵暗号方式を構成することができる。
【０２９４】
＜第４の実施形態のバリエーション＞
第３の実施形態で述べた第６〜第９のバリエーションは、本実施形態でもそのまま成り立つ。すなわち、第６のバリエーションとして、公開鍵におけるｐ,ｌ,ｄ,ｅの一部又は全部を固定パラメータとし、公開鍵のサイズを減らすことができる。
【０２９５】
また、第７のバリエーションとして、暗号化に用いる式(16)を例えば、
Ｆ(x,y,t)＝ｍ(t)−ｆ(t)ｐ(x,y,t)−Ｘ(x,y,t)ｑ(x,y,t)
のように変形して暗号化／復号してもよい。
【０２９６】
さらに、第８のバリエーションとして、平文Ｍ＝ｍ‖ｒを１変数既約多項式ｆ(t)にも埋め込む方式としてもよい。この場合、暗号化処理及び復号処理のフローチャートはそれぞれ図２７（ＳＴ３４”−３，ＳＴ３５”）又は図２８（ＳＴ４８”）に示すように変形される。これに伴い、平文埋め込み部３３’、１変数既約多項式生成部３５及び平文展開部４９’は、それぞれ以下のように変形される。
【０２９７】
すなわち、平文埋め込み部３３’は、メッセージｍと乱数ｒを連結した平文Ｍを１変数tで次数ｌ-１以下の平文多項式Ｍ(t)と次数ｌ以上の１変数既約多項式ｆ(t)の候補の一部の係数とに分担して埋め込むものに変形される。また、１変数既約多項式生成部３５は、１変数既約多項式ｆ(t)の候補の各係数のうち、平文Ｍが埋め込まれていない係数をランダムな値に設定し、１変数既約多項式ｆ(t)を生成するものに変形される。さらに、平文展開部４９’は、平文多項式Ｍ(t)の係数と既約多項式ｆ(t)の一部の係数とから平文Ｍを抽出するものに変形される。
【０２９８】
以上のように、第４の実施形態においても、第３の実施形態で述べた第６〜第８のバリエーションを用いることができる。
【０２９９】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０３００】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０３０１】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０３０２】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０３０３】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０３０４】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０３０５】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０３０６】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０３０７】
【図１】本発明の各実施形態における代数曲面を説明するための模式図である。
【図２】本発明の第１の実施形態に係る鍵生成装置の全体構成図である。
【図３】同実施形態における代数曲面形式テーブルを説明するための模式図である。
【図４】同実施形態における動作を説明するためのフローチャートである。
【図５】同実施形態における動作を説明するためのフローチャートである。
【図６】同実施形態における鍵生成装置の第２のバリエーションの全体構成図である。
【図７】同実施形態における第２のバリエーションの動作を説明するためのフローチャートである。
【図８】同実施形態における鍵生成装置の第１及び第２のバリエーションの全体構成図である。
【図９】本発明の第１の実施形態に係る鍵生成装置の全体構成図である。
【図１０】同実施形態における動作を説明するためのフローチャートである。
【図１１】同実施形態における動作を説明するためのフローチャートである。
【図１２】同実施形態における鍵生成装置の第２のバリエーションの全体構成図である。
【図１３】同実施形態における鍵生成装置の第１及び第２のバリエーションの全体構成図である。
【図１４】同実施形態における第５のバリエーションの動作を説明するためのフローチャートである。
【図１５】本発明の第３及び第４の実施形態における安全性証明を説明するための模式図である。
【図１６】本発明の第３及び第４の実施形態における安全性証明を説明するための模式図である。
【図１７】本発明の第３の実施形態に係る暗号装置の全体構成図である。
【図１８】同実施形態に係る復号装置の全体構成図である。
【図１９】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図２０】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図２１】本発明の第４の実施形態に係る暗号装置の全体構成図である。
【図２２】同実施形態に係る復号装置の全体構成図である。
【図２３】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図２４】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図２５】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図２６】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図２７】同実施形態における暗号装置の第８のバリエーションの動作を説明するためのフローチャートである。
【図２８】同実施形態における復号装置の第８のバリエーションの動作を説明するためのフローチャートである。
【符号の説明】
【０３０８】
１０…鍵生成装置、１１…パラメータ入力部、１１ａ…素数格納部、１１ｂ…最大次数格納部、１１ｃ…有限体格納部、１２…制御部、１３…代数曲面決定部、１４…セクション生成部、１５…１変数多項式生成部、１６…１変数多項式演算部、１７…代数曲面生成部、１８…１変数既約多項式最小次数生成部、１９…鍵出力部、２１…種数計算部、２２…安全性検証部、３０…暗号装置、３１…平文入力部、３２…公開鍵入力部、３３，３３’…平文埋め込み部、３４，３４’…暗号化部、３５…１変数既約多項式生成部、３６，３６’…多項式生成部、３７…暗号文出力部、３８…乱数生成部、４０…復号装置、４１…暗号文入力部、４２…鍵入力部、４３…復号部、４４…セクション代入部、４５…１変数多項式演算部、４６…１変数多項式因数分解部、４７…多項式抽出部、４８…１変数多項式剰余演算部、４９，４９’…平文展開部、５０…平文出力部、５１…暗号文検証部。
【図１】
0004664850.tif 000048
【図２】
0004664850.tif 000049
【図３】
0004664850.tif 000050
【図４】
0004664850.tif 000051
【図５】
0004664850.tif 000052
【図６】
0004664850.tif 000053
【図７】
0004664850.tif 000054
【図８】
0004664850.tif 000055
【図９】
0004664850.tif 000056
【図１０】
0004664850.tif 000057
【図１１】
0004664850.tif 000058
【図１２】
0004664850.tif 000059
【図１３】
0004664850.tif 000060
【図１４】
0004664850.tif 000061
【図１５】
0004664850.tif 000062
【図１６】
0004664850.tif 000063
【図１７】
0004664850.tif 000064
【図１８】
0004664850.tif 000065
【図１９】
0004664850.tif 000066
【図２０】
0004664850.tif 000067
【図２１】
0004664850.tif 000068
【図２２】
0004664850.tif 000069
【図２３】
0004664850.tif 000070
【図２４】
0004664850.tif 000071
【図２５】
0004664850.tif 000072
【図２６】
0004664850.tif 000073
【図２７】
0004664850.tif 000074
【図２８】
0004664850.tif 000075