(57)【要約】【課題】  代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止する。【解決手段】  暗号装置１０においては、暗号文Fに含まれる２つの乗算結果X(x, y, t)r(x, y, t)とf(t)s(x, y, t)とがx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される。これにより、一方の乗算結果X(x, y, t)r(x, y, t)にはあるが、他方の乗算結果f(t)s(x, y, t)には無いという項を解析する手法を用いても、各項の見分けがつかず、r(x, y, t)の一部が漏洩することがない。【選択図】  図１
2008026498.tif 000002
【特許請求の範囲】
【請求項１】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置であって、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込む平文埋め込み手段と、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段と、
「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r(x, y, t)、s(x, y, t)を生成する多項式生成手段と、
前記平文多項式m(t)に対し、前記乗算結果X(x, y, t)r(x, y, t)と、前記乗算結果f(t)s(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)を生成する暗号化手段と
を備えたことを特徴とする暗号装置。
【請求項２】
請求項１に記載の暗号装置において、
前記多項式生成手段は、
前記１変数既約多項式f(t)の次数L0を取得する次数取得手段と、
前記ファイブレーションX(x, y, t)をx, yの２変数多項式Σcij(t)xiyjとしたとき、前記係数cij(t)の次数の最小値dtを選択する最小値選択手段と、
３変数多項式r(x, y, t)をxとyの多項式としたとき、前記多項式r(x, y, t)に含まれる複数の単項式rij(t)xiyjのうちの定数項r00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第１定数項算出手段と、
前記複数の単項式rij(t)xiyjのうちの定数項r00(t)以外の変数項rij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第１変数項算出手段と、
前記定数項r00(t)及び前記変数項rij(t)xiyjを足し合わせて、前記３変数多項式r(x, y, t)を算出する第１多項式算出手段と、
前記ファイブレーションX(x, y, t)と当該３変数多項式r(x, y, t)とを乗算し、乗算結果X(x, y, t)r(x, y, t)を得る多項式乗算手段と、
３変数多項式s(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r(x, y, t)に含まれる複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)のｔの次数degt s’00(t)に基づいて、前記多項式s(x, y, t)の定数項s00(t)を、tの次数がdegt s’00(t)−L0となる範囲でランダムに算出する第２定数項算出手段と、
前記複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)以外の変数項s’ij(t)xiyjに基づいて、前記多項式s(x, y, t)の変数項sij(t)xiyjを、tの次数がdegt s’ij(t)−L0となる範囲でランダムに算出する第２変数項算出手段と、
前記定数項s00(t)及び前記変数項sij(t)xiyjを足し合わせて、前記３変数多項式s(x, y, t)を算出する第２多項式算出手段と
を備えたことを特徴とする暗号装置。
【請求項３】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置であって、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込む平文埋め込み手段と、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段と、
「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r1(x, y, t)、s1(x, y, t)を生成する第１多項式生成手段と、
前記平文多項式m(t)に対し、前記乗算結果X(x, y, t)r1(x, y, t)と、前記乗算結果f(t)s1(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第１暗号文F1＝Epk(m, s1, r1, f, X)を生成する第１暗号化手段と、
「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r2(x, y, t)、s2(x, y, t)を生成する第２多項式生成手段と、
前記平文多項式m(t)に対し、前記乗算結果X(x, y, t)r2(x, y, t)と、前記乗算結果f(t)s2(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第２暗号文F2＝Epk(m, s2, r2, f, X)を生成する第２暗号化手段と
を備えたことを特徴とする暗号装置。
【請求項４】
請求項３に記載の暗号装置において、
前記第１多項式生成手段は、
前記１変数既約多項式f(t)の次数L0を取得する次数取得手段と、
前記ファイブレーションX(x, y, t)をx, yの２変数多項式Σcij(t)xiyjとしたとき、前記係数cij(t)の次数の最小値dtを選択する最小値選択手段と、
３変数多項式r1(x, y, t)をxとyの多項式としたとき、前記多項式r1(x, y, t)に含まれる複数の単項式r1_ij(t)xiyjのうちの定数項r1_00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第１定数項算出手段と、
前記複数の単項式r1_ij(t)xiyjのうちの定数項r1_00(t)以外の変数項r1_ij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第１変数項算出手段と、
前記定数項r1_00(t)及び前記変数項r1_ij(t)xiyjを足し合わせて、前記３変数多項式r1(x, y, t)を算出する第１多項式算出手段と、
前記ファイブレーションX(x, y, t)と当該３変数多項式r1(x, y, t)とを乗算し、乗算結果X(x, y, t)r1(x, y, t)を得る第１多項式乗算手段と、
３変数多項式s1(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r1(x, y, t)に含まれる複数の単項式s1’ij(t)xiyjのうちの定数項s1’00(t)のｔの次数degt s1’00(t)に基づいて、前記多項式s1(x, y, t)の定数項s1_00(t)を、tの次数がdegt s1’00(t)−L0となる範囲でランダムに算出する第２定数項算出手段と、
前記複数の単項式s1’ij(t)xiyjのうちの定数項s1_00(t)以外の変数項s1’ij(t)xiyjに基づいて、前記多項式s1(x, y, t)の変数項s1_ij(t)xiyjを、tの次数がdegt s1’ij(t)−L0となる範囲でランダムに算出する第２変数項算出手段と、
前記定数項s1_00(t)及び前記変数項s1_ij(t)xiyjを足し合わせて、前記３変数多項式s1(x, y, t)を算出する第２多項式算出手段とを備えており
前記第２多項式生成手段は、
前記３変数多項式r1(x, y, t)とは異なる３変数多項式r2(x, y, t)をxとyの多項式としたとき、前記多項式r2(x, y, t)に含まれる複数の単項式r2_ij(t)xiyjのうちの定数項r2_00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第３定数項算出手段と、
前記複数の単項式r2_ij(t)xiyjのうちの定数項r2_00(t)以外の変数項r2_ij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第３変数項算出手段と、
前記定数項r2_00(t)及び前記変数項r2_ij(t)xiyjを足し合わせて、前記３変数多項式r2(x, y, t)を算出する第３多項式算出手段と、
前記ファイブレーションX(x, y, t)と当該３変数多項式r2(x, y, t)とを乗算し、乗算結果X(x, y, t)r2(x, y, t)を得る第２多項式乗算手段と、
３変数多項式s2(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r2(x, y, t)に含まれる複数の単項式s2’ij(t)xiyjのうちの定数項s2’00(t)のｔの次数degt s2’00(t)に基づいて、前記多項式s2(x, y, t)の定数項s2_00(t)を、tの次数がdegt s2’00(t)−L0となる範囲でランダムに算出する第４定数項算出手段と、
前記複数の単項式s2’ij(t)xiyjのうちの定数項s2_00(t)以外の変数項s2’ij(t)xiyjに基づいて、前記多項式s2(x, y, t)の変数項s2_ij(t)xiyjを、tの次数がdegt s2’ij(t)−L0となる範囲でランダムに算出する第４変数項算出手段と、
前記定数項s2_00(t)及び前記変数項s2_ij(t)xiyjを足し合わせて、前記３変数多項式s2(x, y, t)を算出する第４多項式算出手段と
を備えたことを特徴とする暗号装置。
【請求項５】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力手段と、
前記入力された暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段と、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段と
を備えたことを特徴とする復号装置。
【請求項６】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力手段と、
前記入力された暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力手段と
を備えたことを特徴とする復号装置。
【請求項７】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力手段と、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力手段と、
入力された複数の暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段と、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段と
を備えたことを特徴とする復号装置。
【請求項８】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力手段と、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力手段と、
入力された複数の暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力手段と
を備えたことを特徴とする復号装置。
【請求項９】
メモリを有する暗号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための前記暗号装置のプログラムであって、
前記暗号装置のコンピュータを、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込むことにより、平文多項式m(t)を得る平文埋め込み手段、
前記平文埋め込み手段により得られた平文多項式m(t)を前記メモリに書き込む書込手段、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段、
「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r(x, y, t)、s(x, y, t)を生成する多項式生成手段、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r(x, y, t)と、前記乗算結果f(t)s(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)を生成する暗号化手段、
として機能させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムにおいて、
前記多項式生成手段は、
前記１変数既約多項式f(t)の次数L0を取得する次数取得手段、
前記ファイブレーションX(x, y, t)をx, yの２変数多項式Σcij(t)xiyjとしたとき、前記係数cij(t)の次数の最小値dtを選択する最小値選択手段、
３変数多項式r(x, y, t)をxとyの多項式としたとき、前記多項式r(x, y, t)に含まれる複数の単項式rij(t)xiyjのうちの定数項r00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第１定数項算出手段、
前記複数の単項式rij(t)xiyjのうちの定数項r00(t)以外の変数項rij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第１変数項算出手段、
前記定数項r00(t)及び前記変数項rij(t)xiyjを足し合わせて、前記３変数多項式r(x, y, t)を算出する第１多項式算出手段、
前記ファイブレーションX(x, y, t)と当該３変数多項式r(x, y, t)とを乗算し、乗算結果X(x, y, t)r(x, y, t)を得る多項式乗算手段、
３変数多項式s(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r(x, y, t)に含まれる複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)のｔの次数degt s’00(t)に基づいて、前記多項式s(x, y, t)の定数項s00(t)を、tの次数がdegt s’00(t)−L0となる範囲でランダムに算出する第２定数項算出手段、
前記複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)以外の変数項s’ij(t)xiyjに基づいて、前記多項式s(x, y, t)の変数項sij(t)xiyjを、tの次数がdegt s’ij(t)−L0となる範囲でランダムに算出する第２変数項算出手段、
前記定数項s00(t)及び前記変数項sij(t)xiyjを足し合わせて、前記３変数多項式s(x, y, t)を算出する第２多項式算出手段、
として前記コンピュータを機能させるためのプログラム。
【請求項１１】
メモリを有する暗号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応するセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための前記暗号装置のプログラムであって、
前記暗号装置のコンピュータを、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込むことにより、平文多項式m(t)を得る平文埋め込み手段、
前記平文埋め込み手段により得られた平文多項式m(t)を前記メモリに書き込む書込手段、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段、
ランダム３変数多項式r1(x, y, t)、s1(x, y, t)を「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r1(x, y, t)、s1(x, y, t)を生成する第１多項式生成手段、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r1(x, y, t)と、前記乗算結果f(t)s1(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第１暗号文F1＝Epk(m, s1, r1, f, X)を生成する第１暗号化手段、
「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r2(x, y, t)、s2(x, y, t)を生成する第２多項式生成手段、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r2(x, y, t)と、前記乗算結果f(t)s2(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第２暗号文F2＝Epk(m, s2, r2, f, X)を生成する第２暗号化手段、
として機能させるためのプログラム。
【請求項１２】
請求項１１に記載のプログラムにおいて、
前記第１多項式生成手段は、
前記１変数既約多項式f(t)の次数L0を取得する次数取得手段、
前記ファイブレーションX(x, y, t)をx, yの２変数多項式Σcij(t)xiyjとしたとき、前記係数cij(t)の次数の最小値dtを選択する最小値選択手段、
３変数多項式r1(x, y, t)をxとyの多項式としたとき、前記多項式r1(x, y, t)に含まれる複数の単項式r1_ij(t)xiyjのうちの定数項r1_00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第１定数項算出手段、
前記複数の単項式r1_ij(t)xiyjのうちの定数項r1_00(t)以外の変数項r1_ij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第１変数項算出手段、
前記定数項r1_00(t)及び前記変数項r1_ij(t)xiyjを足し合わせて、前記３変数多項式r1(x, y, t)を算出する第１多項式算出手段、
前記ファイブレーションX(x, y, t)と当該３変数多項式r1(x, y, t)とを乗算し、乗算結果X(x, y, t)r1(x, y, t)を得る第１多項式乗算手段、
３変数多項式s1(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r1(x, y, t)に含まれる複数の単項式s1’ij(t)xiyjのうちの定数項s1’00(t)のｔの次数degt s1’00(t)に基づいて、前記多項式s1(x, y, t)の定数項s1_00(t)を、tの次数がdegt s1’00(t)−L0となる範囲でランダムに算出する第２定数項算出手段、
前記複数の単項式s1’ij(t)xiyjのうちの定数項s1_00(t)以外の変数項s1’ij(t)xiyjに基づいて、前記多項式s1(x, y, t)の変数項s1_ij(t)xiyjを、tの次数がdegt s1’ij(t)−L0となる範囲でランダムに算出する第２変数項算出手段、
前記定数項s1_00(t)及び前記変数項s1_ij(t)xiyjを足し合わせて、前記３変数多項式s1(x, y, t)を算出する第２多項式算出手段、として前記コンピュータを機能させ、
前記第２多項式生成手段は、
前記３変数多項式r1(x, y, t)とは異なる３変数多項式r2(x, y, t)をxとyの多項式としたとき、前記多項式r2(x, y, t)に含まれる複数の単項式r2_ij(t)xiyjのうちの定数項r2_00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する第３定数項算出手段、
前記複数の単項式r2_ij(t)xiyjのうちの定数項r2_00(t)以外の変数項r2_ij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する第３変数項算出手段、
前記定数項r2_00(t)及び前記変数項r2_ij(t)xiyjを足し合わせて、前記３変数多項式r2(x, y, t)を算出する第３多項式算出手段、
前記ファイブレーションX(x, y, t)と当該３変数多項式r2(x, y, t)とを乗算し、乗算結果X(x, y, t)r2(x, y, t)を得る第２多項式乗算手段、
３変数多項式s2(x, y, t)をxとyの多項式としたとき、前記乗算結果X(x, y, t)r2(x, y, t)に含まれる複数の単項式s2’ij(t)xiyjのうちの定数項s2’00(t)のｔの次数degt s2’00(t)に基づいて、前記多項式s2(x, y, t)の定数項s2_00(t)を、tの次数がdegt s2’00(t)−L0となる範囲でランダムに算出する第４定数項算出手段、
前記複数の単項式s2’ij(t)xiyjのうちの定数項s2_00(t)以外の変数項s2’ij(t)xiyjに基づいて、前記多項式s2(x, y, t)の変数項s2_ij(t)xiyjを、tの次数がdegt s2’ij(t)−L0となる範囲でランダムに算出する第４変数項算出手段、
前記定数項s2_00(t)及び前記変数項s2_ij(t)xiyjを足し合わせて、前記３変数多項式s2(x, y, t)を算出する第４多項式算出手段、
として機能させるためのプログラム。
【請求項１３】
メモリを有する復号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置のプログラムであって、
前記復号装置のコンピュータを、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力手段、
前記入力された暗号文Ｆを前記メモリに書き込む手段、
前記メモリ内の暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段、
として機能させるためのプログラム。
【請求項１４】
メモリを有する復号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置のプログラムであって、
前記復号装置のコンピュータを、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力手段、
前記入力された暗号文Ｆを前記メモリに書き込む手段、
前記メモリ内の暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力手段、
として機能させるためのプログラム。
【請求項１５】
メモリを有する復号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置のプログラムであって、
前記復号装置のコンピュータを、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力手段、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力手段、
入力された複数の暗号文F1, F2を前記メモリに書き込む手段、
前記メモリ内の各暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段、
として機能させるためのプログラム。
【請求項１６】
メモリを有する復号装置に用いられ、代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置のプログラムであって、
前記復号装置のコンピュータを、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力手段、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力手段、
入力された複数の暗号文F1, F2を前記メモリに書き込む手段、
前記メモリ内の各暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力手段、
として機能させるためのプログラム。
【請求項１７】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置が実行する暗号方法であって、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込むことにより、平文多項式m(t)を得る平文埋め込み工程と、
前記平文多項式m(t)を前記暗号装置のメモリに書き込む工程と、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成工程と、
「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r(x, y, t)、s(x, y, t)を生成する多項式生成工程と、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r(x, y, t)と、前記乗算結果f(t)s(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)を生成する暗号化工程と
を備えたことを特徴とする暗号方法。
【請求項１８】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置が実行する暗号方法であって、
メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込むことにより、平文多項式m(t)を得る平文埋め込み工程と、
前記平文多項式m(t)を前記暗号装置のメモリに書き込む工程と、
次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成工程と、
「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r1(x, y, t)、s1(x, y, t)を生成する第１多項式生成工程と、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r1(x, y, t)と、前記乗算結果f(t)s1(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第１暗号文F1＝Epk(m, s1, r1, f, X)を生成する第１暗号化工程と、
「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r2(x, y, t)、s2(x, y, t)を生成する第２多項式生成工程と、
前記メモリ内の平文多項式m(t)に対し、前記乗算結果X(x, y, t)r2(x, y, t)と、前記乗算結果f(t)s2(x, y, t)とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第２暗号文F2＝Epk(m, s2, r2, f, X)を生成する第２暗号化工程と
を備えたことを特徴とする暗号方法。
【請求項１９】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置が実行する復号方法であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力工程と、
前記入力された暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入工程と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算工程と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解工程と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出工程と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算工程と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査工程と、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開工程と、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算工程を制御する制御工程と、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力工程と
を備えたことを特徴とする復号方法。
【請求項２０】
代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置が実行する復号方法であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力工程と、
前記入力された暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入工程と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算工程と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解工程と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出工程と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算工程と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査工程と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開工程と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力工程と
を備えたことを特徴とする復号方法。
【請求項２１】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置が実行する復号方法であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力工程と、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力工程と、
入力された複数の暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入工程と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算工程と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解工程と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出工程と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算工程と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査工程と、
前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開工程と、
前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算工程を制御する制御工程と、
前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力工程と
を備えたことを特徴とする復号方法。
【請求項２２】
代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置が実行する復号方法であって、
メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力工程と、
前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力工程と、
入力された複数の暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入工程と、
前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算工程と、
前記減算結果{h1(t)−h2(t)}を因数分解する因数分解工程と、
因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出工程と、
抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算工程と、
前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査工程と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が１つだけあるとき、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開工程と、
前記検査の結果、両者が一致する場合の既約多項式f(t)が無いか又は２つ以上あるとき、エラーを出力するエラー出力工程と
を備えたことを特徴とする復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号システムに用いられる暗号装置、復号装置、プログラム及び方法に関する。
【背景技術】
【０００２】
代表的な公開鍵暗号としてはＲＳＡ暗号と楕円曲線暗号がある。これらの公開鍵暗号は、一般的な解読法が知られていないため、後述する量子計算機による解読法を除き、安全性に関する重大な問題が見つかっていない。他の公開鍵暗号としてはナップサック暗号と多次多変数暗号などがある。しかしながら、ナップサック暗号は有力な解読法があるため、安全性に疑問がある。多次多変数暗号は、鍵サイズの増大により、有力な攻撃方法を避けられる反面、鍵サイズが膨大になってしまう問題がある。
【０００３】
一方、ＲＳＡ暗号と楕円曲線暗号は量子計算機が出現すれば解読される可能性が高い。量子計算機は、現在の計算機とは異なり、量子力学におけるエンタングルメントという物理現象を利用して超並列計算を実行可能な計算機である。量子計算機は、実験レベルの仮想の計算機であるが、実現に向けて研究開発が進められている。1994年にショア(Shor)は、量子計算機によれば素因数分解や離散対数問題を効率的に解けることを示した。従って、量子計算機が実現すれば、素因数分解に基づくＲＳＡ暗号や、楕円曲線上の離散対数問題に基づく楕円曲線暗号は解読される可能性が高い。
【０００４】
他方、量子計算機が実現されても安全な公開鍵暗号が研究されてきている。一例として、量子公開鍵暗号が挙げられる。量子公開鍵暗号では、現在の計算機では鍵生成が不可能である程に強力なナップサック暗号の鍵を量子計算機により生成する。このため、量子公開鍵暗号では、量子計算機でも計算できない程に強力なナップサック暗号を構成し得る。しかしながら、量子公開鍵暗号は、現在の計算機では鍵生成が不可能であるため、現時点では利用できない。
【０００５】
一方、多次多変数暗号は、現時点でも実現可能であり、量子計算機でも解読が難しい。しかしながら、多次多変数暗号は、前述した通り、膨大な鍵サイズを要するため、実用化が疑問視されている。
【０００６】
更に、公開鍵暗号は、共通鍵暗号と比べ、回路規模が大きく、処理時間が長い。よって、モバイル端末などの小電力環境では実現できないか、実現しても待ち時間が長いという問題がある。このため、小電力環境でも実現できる公開鍵暗号が求められている。
【０００７】
一般に公開鍵暗号は、予め素因数分解問題や離散対数問題などの計算困難な問題を見出し、秘密鍵を知らずに暗号文の解読を試みる場合に当該計算困難な問題を解くことと同等になるように構成する。
【０００８】
しかし、計算困難な問題が見つかっても、その問題を安全性の根拠とする公開鍵暗号を容易に構成できる訳ではない。理由は、計算が困難すぎる問題を安全性の根拠にすると鍵を生成する問題も困難になるので、鍵を生成できないためである。一方、鍵生成が可能な程度に問題を容易にすると、解読も容易になってしまう。
【０００９】
従って、公開鍵暗号を構成するには、計算困難な問題を見つけるとともに、見つけた問題を、鍵生成が容易だが、解読が容易でないという絶妙なバランスを持つ問題に作り変える必要がある。このような問題の作り変えには高い創造性を必要とする。実際には、問題の作り変えが極めて困難なため、数えるほどの公開鍵暗号しか提案されていない。
【００１０】
このような状況において、量子計算機でも効率的に解読できない可能性があり、小電力環境でも高速に処理可能な公開鍵暗号として、代数曲面を用いた公開鍵暗号が提案されている（例えば、特許文献１参照）。
【００１１】
代数曲面を用いた公開鍵暗号は、秘密鍵を代数曲面X(x, y, t)に対応する２つのセクションとし、公開鍵を代数曲面X(x, y, t)とする時、平文mを平文多項式m(t)に埋め込む処理と、次数Lの１変数既約多項式f(t)をランダムに生成する処理と、３変数x, y, tのランダム化多項式s(x, y, t), r(x, y, t)を生成する処理と、各多項式s(x, y, t), r(x, y, t), f(t)と定義式X(x, y, t)とを演算する暗号化処理とにより、平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)を生成する方式である。この方式は、後述する代数曲面上の求因子問題に安全性の根拠をおくので、解読が困難となっている。
【特許文献１】特開２００５−３３１６５６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、以上のような代数曲面を用いた公開鍵暗号は、通常は何の問題も無いが、本発明者の検討によれば、ランダム化多項式s(x, y, t), r(x, y, t)によっては、暗号文Fの解析により、r(x, y, t)の一部が漏洩する可能性が生じてしまう。
【００１３】
補足すると、ランダム化多項式s(x, y, t), r(x, y, t)の生成に関しては、ランダム化多項式の次数に関する条件が開示されているものの、生成アルゴリズムが開示されていない。このため、生成されたランダム化多項式s(x, y, t), r(x, y, t)によっては、暗号文Fの解析により、r(x, y, t)の一部が漏洩する可能性が生じてしまう。
【００１４】
本発明は上記実情を考慮してなされたもので、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止し得る暗号装置、復号装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
第１の発明は、代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置であって、メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込む平文埋め込み手段と、次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段と、「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r(x, y, t)、s(x, y, t)を生成する多項式生成手段と、前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)を生成する暗号化手段とを備えた暗号装置である。
【００１６】
第２の発明は、代数曲面XのファイブレーションX(x, y, t)に対応するセクションが秘密鍵のとき、前記ファイブレーションX(x, y, t)である公開鍵に基づいて、メッセージmを暗号化するための暗号装置であって、メッセージmを１変数tで次数L−1以下の平文多項式m(t)の係数として埋め込む平文埋め込み手段と、次数L以上のランダムな１変数既約多項式f(t)を生成する既約多項式生成手段と、「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r1(x, y, t)、s1(x, y, t)を生成する第１多項式生成手段と、前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第１暗号文F1＝Epk(m, s1, r1, f, X)を生成する第１暗号化手段と、「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r2(x, y, t)、s2(x, y, t)を生成する第２多項式生成手段と、前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、前記平文多項式m(t)から第２暗号文F2＝Epk(m, s2, r2, f, X)を生成する第２暗号化手段とを備えた暗号装置である。
【００１７】
第３の発明は、代数曲面XのファイブレーションX(x, y, t)に対応する２つ以上のセクションD1, D2である秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された暗号文Fから、メッセージmを復号するための復号装置であって、メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F＝Epk(m, s, r, f, X)が入力される暗号文入力手段と、前記入力された暗号文Ｆに対し、前記各セクションD1, D2を代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段と、前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段とを備えた復号装置である。
【００１８】
第４の発明は、代数曲面XのファイブレーションX(x, y, t)に対応するセクションDである秘密鍵に基づいて、前記ファイブレーションX(x, y, t)である公開鍵により生成された複数の暗号文F1, F2から、メッセージmを復号するための復号装置であって、メッセージmが１変数tで次数(L−1)以下の平文多項式m(t)の係数として埋め込まれた平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F1＝Epk(m, s1, r1, f, X)が入力される第１暗号文入力手段と、前記平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「前記ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により生成された前記暗号文F2＝Epk(m, s2, r2, f, X)が入力される第２暗号文入力手段と、入力された複数の暗号文F1, F2に対し、前記セクションDを代入して２つの１変数多項式h1(t), h2(t)を生成するセクション代入手段と、前記各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、前記減算結果{h1(t)−h2(t)}を因数分解する因数分解手段と、因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する多項式抽出手段と、抽出された既約多項式f(t)で前記１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で前記１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る剰余演算手段と、前記多項式候補m1(t), m2(t)が互いに一致するか否かを検査する平文多項式検査手段と、前記検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)からメッセージmを展開する展開手段と、前記検査の結果、否の場合には、抽出された他の既約多項式f(t)により前記除算を実行するように前記剰余演算手段を制御する制御手段と、前記検査の結果、否の場合で且つ他の既約多項式f(t)が無い場合には、エラーを出力するエラー出力手段とを備えた復号装置である。
【００１９】
なお、以上の各発明は、「装置」として表現したが、これに限らず、「方法」、「プログラム」、「コンピュータ読み取り可能な記憶媒体」といった他の表現を用いてもよいことは言うまでもない。
【００２０】
（作用）
第１及び第３の発明は、暗号文Fに含まれる２つの乗算結果X(x, y, t)r(x, y, t)及びf(t)s(x, y, t)が、それぞれx, yの多項式として見たときの変数xiyjについての同類項から構成されるので、一方の乗算結果X(x, y, t)r(x, y, t)にはあるが、他方の乗算結果f(t)s(x, y, t)には無いという項を解析する手法を用いても、各項の見分けがつかず、r(x, y, t)の一部が漏洩することがない。
【００２１】
従って、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止することができる。
【００２２】
第２及び第４の発明は、第１及び第３の発明と同様の理由により、暗号文F1, F2を解析しても、r1(x, y, t), r2(x, y, t)の一部が漏洩することがないので、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止することができる。
【発明の効果】
【００２３】
以上説明したように本発明によれば、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の各実施形態を図面を用いて説明する。
【００２５】
本発明で述べる代数曲面は体K上定義された連立(代数)方程式の解の集合のうち２次元の自由度を持ったものと定義される。例えば、次の式(1)に示す体K上の連立方程式はは５つの変数を束縛する３つの方程式があることから、２次元の自由度を持っているので、代数曲面となる。
【数１】
2008026498.tif 000003
【００２６】
特に、式(2)に示す如き、３変数のK上代数方程式の解の集合として定義される空間もK上の代数曲面となる。
【００２７】
f(x, y, z)＝0     (2)
なお、式(1)、式(2)に示した代数曲面の定義式はアフィン空間におけるものである。射影空間における代数曲面の定義式は（式(2)の場合）f(x, y, z, w)＝0である。
【００２８】
しかし、本実施形態では代数曲面を射影空間で扱うことはないので代数曲面の定義式を式(1)若しくは式(2)としたが、射影空間で表現しても本発明はそのまま成立する。
【００２９】
一方、代数曲線は体K上定義された連立(代数)方程式の解の集合のうち1次元の自由度を持ったものである。よって、例えば次式のように定義される。
【００３０】
g(x, y)＝0
本実施形態においては式(2)のように１つの式で書ける代数曲面のみを扱うので、以下では式(2)を代数曲面の定義方程式のごとく扱う。
【００３１】
体とは加減乗除が自由にできる集合である。実数、有理数、複素数は体に該当するが、整数や行列など０以外に除算ができない元を含む集合は体に該当しない。体の中には有限体と呼ばれる有限個の元から構成される体がある。例えば素数pに対し、pを法とする剰余類Z/pZは体をなす。このような体は、素体と呼ばれ、Fpなどと書く。有限体にはこの他に素数の冪乗個の元を持つ体Fq(q＝pr)がある。但し、本実施形態では、簡単のため、主に素体Fpのみを扱う。一般に素体Fpのpは素体Fpの標数と呼ばれる。
【００３２】
一方、一般の有限体でも本発明は自明な変形を施すことによって同様に成立する。公開鍵暗号ではメッセージをデジタルデータとして埋め込む必要から有限体上で構成することが多く、本実施形態においても同様に有限体（本実施形態では特に素体）Fp上定義された代数曲面を扱う。
【００３３】
代数曲面f(x, y, z)＝0上には図１に示すように通常代数曲線が複数存在する。このような代数曲線は代数曲面上の因子と呼ばれる。
【００３４】
一般に代数曲面の定義式が与えられた時に（非自明な）因子を求める問題は現代の数学においても未解決の難問であり、後述するような多次多変数連立方程式を解いたり、総当りによって求めるなどの原始的な方法を除けば一般的な解法は知られていない。特に本実施形態で扱うような有限体で定義された代数曲面においては有理数体などの無限体（無限個の元からなる体）と比較しても手掛かりが少なく、より難しい問題であることが知られている。
【００３５】
本実施形態ではこの問題を代数曲面上の求因子問題もしくは単に求因子問題と呼び、代数曲面上の求因子問題に安全性の根拠をおく公開鍵暗号を構成する。
【００３６】
さて、体K上の代数曲面X: f(x, y, z)＝0のうち、
h(x, y, t)＝0
と定義され、セクションと呼ばれるx, yがtでパラメタライズされた曲線
(x, y, t)＝(ux(t), uy(t), t)
が存在するような形式に表現された代数曲面を代数曲面Xのファイブレーションといい、Xtなどと表す。なお、以下では、ファイブレーションであることが明らかであるので、単にXと表す。
【００３７】
また、パラメータtに体Kの元t0を代入して得られる代数曲線はファイバーと呼ばれ、Xt0のように表される。ここでファイバーとセクションは共に代数曲面Xtの因子である。
【００３８】
一般に代数曲面のファイブレーションが与えられたとき、それに対応するファイバーは（tに体の元を代入することにより）直ちに求まるが、対応するセクションを求めることは極めて難しい。この意味ではファイバーは自明な因子であり、セクションは非自明な因子であると言える。
【００３９】
本発明の公開鍵暗号は代数曲面上の求因子問題のうち、特に代数曲面XのファイブレーションXtが与えられたとき、セクションを求める問題に安全性の根拠をおいた公開鍵暗号である。
【００４０】
ファイブレーションからセクションを求めるには現代の数学においてもセクション(ux(t), uy(t), t)を
deg ux(t) ＜ rx, deg uy(t) ＜ ry
と仮定した上で、
【数２】
2008026498.tif 000004
【００４１】
を立てて、これを解くことによって求める方法しか知られていない。代数曲面上の求セクション問題に基づいた本発明の公開鍵暗号を具体的に説明する。
【００４２】
（第１の実施形態）
（概要）
本実施形態の公開鍵暗号は、システムパラメータとして
1. 素体の標数p
2. Fp上の１変数既約多項式f(t)の次数L
を持っている。また、公開鍵は
1. Fp上の代数曲面Xのファイブレーション:X(x, y, t)＝ 0
である。秘密鍵は
1. Fp上の代数曲面Xのセクション:D1:(x, y, t)＝(ux(t), uy(t), t)
2. Fp上の代数曲面Xのセクション:D2:(x, y, t)＝(vx(t), vy(t), t)
である。これらは後述する鍵生成方法で容易に求めることができる。
【００４３】
次に暗号化処理の概要を述べる。暗号化処理ではまず暗号化したいメッセージ（以下では平文と呼ぶ）をブロック分割して
m＝m0‖m1‖ ・ ・ ・ ‖mL−1
のようにし、平文多項式m(t)に
m(t)＝mL−1tL−1＋・ ・ ・＋m1t＋m0
として埋め込む（平文埋め込み処理）。ここでm(t)をFp上の多項式とするために、各mi (0 ＜ i ＜ L−1)はFpの元となるように取る必要がある。即ち、平文はpのビット長に基づいて
0 ＜ mi ＜ p−1
となるように分割される。なお、平文ｍは整数であり、例えばメッセージを表す文字コード列が整数に読み替えられることにより、構成されている。
【００４４】
次に、Fp上でランダムなL以上の次数を持つ１変数既約多項式f(t)を決める。ここで既約多項式とは、これ以上因数分解できない多項式のことである。有限体上の１変数多項式の場合、既約性判定は極めて容易であることが知られている。いま、選択された既約多項式の次数をL0とする。
【００４５】
次に、Fp上のランダム化多項式r(x, y, t), s(x, y, t)を生成して、式m(t), f(t) 及び公開鍵である代数曲面XのファイブレーションX(x, y, t)から次の式(3)によって暗号文F(x, y, t)を計算する。
【００４６】
F(x, y, t)＝m(t)＋f(t)s(x, y, t)＋X(x, y, t)r(x, y, t)    (3)
各実施形態ではr(x, y, t), s(x, y, t)の生成に一定の条件を定め、安全性を向上させるとともに、暗号文のサイズを見積もり易く構成している。このために、公開鍵である代数曲面X(x, y, t)をx, yの多項式として見た次式に関し、係数cij(t)の次数の最小値dtを求める。
【数３】
2008026498.tif 000005
【００４７】
次に、r(x, y, t)をx, yの多項式として見たときに各項を生成する単項式rij(t)xiyjを決定する。ここで、生成される単項式の中には定数項が含まれ、当該定数項を含む各項の係数であるrij(t)を次数がL0−dt以上となる範囲でランダムに決定する。これにより、暗号文の構成要素であるX(x, y, t)r(x, y, t)の全ての項の係数の次数を、同じく暗号文の構成要素である１変数既約多項式f(t)の次数以上にすることができる。
【００４８】
なお、以下で３変数多項式Σcij(t)xiyjの係数を述べる時には、特に断らない限り、x, yのみの多項式として見たときの項cij(t)xiyjを対象にする。即ち、３変数多項式の項cij(t)xiyjの係数はcij(t)であり、係数の次数はcij(t)のtに関する次数である。また、ｘ、ｙの多項式として見たときの項ηij(t)xiyjの同類項とは変数xiyjが等しい項τij(t)xiyjのことである。ここで、それぞれの項の係数であるηij(t)とτij(t)は一般には等しくはない（ただ、便宜的にηij(t)＝τij(t)の場合も同類項という）。また、２つの３変数多項式Ｇ1(x,y,t), Ｇ2(x,y,t)がx, yの多項式として見たときの変数xiyjについての同類項から構成されるとは、Ｇ1(x,y,t)に含まれるx, yの多項式として見たときの項のxiyjについての同類項がＧ2(x,y,t)の非零の項（係数が０でない項）として含まれており、かつその逆、即ちＧ2(x,y,t)に含まれるx, yの多項式として見たときの項のxiyjについての同類項がＧ1(x,y,t)の非零の項（係数が０でない項）として含まれていることと定義する。
【００４９】
次に、前述のように決定したr(x, y, t)に基づいてX(x, y, t)r(x, y, t)を計算し、多項式s(x, y, t)を以下のように決定する。即ち、計算したX(x, y, t)r(x, y, t)に含まれるaij(t)xiyjの同類項bij(t)xiyjを含め、それらの係数bij(t)の次数がX(x, y, t)r(x, y, t)における対応する項aij(t)xiyjの係数aij(t)の次数からL0を減じた値となるようにランダムに決定する。
【００５０】
また、X(x, y, t)r(x, y, t)に含まれない項の同類項は含まない（即ち係数を０にする）。このようにすることによって、暗号文の構成要素であるX(x, y, t)r(x, y, t)とf(t)s(x, y, t)の形容を同じにすることができる。即ち、前述した構成によればX(x, y, t)r(x, y, t)とf(t)s(x, y, t)は互いに x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成されており、かつ対応する項の係数の次数が一致するため両者の式は、その形において区別が付かない。また、両者の式にはX(x, y, t), r(x, y, t)の作り方から定数項が含まれており、かつdeg f(t) ＞ L, degm(t) ＜ Lであるため、暗号文に含まれる要素X(x, y, t)r(x, y, t)とf(t)s(x, y, t)は互いに他の雑音（ランダム要素）となっており、その区別が付かない。特に、これらの定数項を見るとm(t)とX(x, y, t)r(x, y, t)とf(t)s(x, y, t)が互いに他の雑音になっていることが分かる。
【００５１】
逆に、このように構成しないと、f(t)s(x, y, t)に含まれているがX(x, y, t)r(x, y, t)には含まれていない項や、X(x, y, t)r(x, y, t)に含まれているがf(t)s(x, y, t)には含まれていない項が存在することになる。前者の場合はf(t)s(x, y, t)のみに含まれる項の係数を因数分解することでf(t) 若しくはf(t)を含むf(t)の複数の候補が得られる。後者の場合はX(x, y, t)r(x, y, t)のみに含まれる項aij(t)xiyjに対応したr(x, y, t)の項の係数が分かってしまう。しかし、いずれの場合もどの項が該当する項かを予め特定しておく必要があるため、前記方法が直ちに先発明（特開２００５−３３１６５６）の公開鍵暗号の安全性を脅かすものではない。しかし、将来の解読技術の進歩により、特定が簡単に実現してしまう可能性も少なくない。このため、ランダム多項式r(x, y, t), s(x, y, t)を各実施形態のように生成する必要がある。同様にf(t)s(x, y, t)とX(x, y, t)r(x, y, t)の定数項に関しても、もし定数項が存在しなければ暗号文F(x, y, t)の定数項からm(t)が漏洩するという問題がある。
【００５２】
暗号文F(x, y, t)を受け取った受信者は、所有する秘密鍵D1, D2を利用して次のように復号を行う。まず、セクションD1, D2を暗号文F(x, y, t)に代入する。ここで、セクションD1, D2を代数曲面X(x, y, t)に代入する。
【００５３】
X(ux(t), uy(t), t)＝0, X(vx(t), vy(t), t)＝0
なる関係があることに注意すると
h1(t)＝F(ux(t), uy(t), t)＝m(t)＋f(t)p(ux(t), uy(t), t)
h2(t)＝F(vx(t), vy(t), t)＝m(t)＋f(t)p(vx(t), vy(t), t)
という関係を持つ２つの式h1(t), h2(t)が求まることが分かる。次に、２式を辺々引き算して、次の式(4)を計算する。
【００５４】
h1(t)−h2(t)＝f(t){p(ux(t), uy(t), t)−p(vx(t), vy(t), t)}    (4)
次に、h1(t)−h2(t)を因数分解して、次数がL以上の因数を取得する。ここで、次数がL以上の因子は１つとは限らない。そこで、それらを
fi(t) (1 ＜ i ＜ n)
とする。また、h1(t)−h2(t)の因数分解は１変数多項式の因数分解が容易であることから十分有効な時間内に処理可能である。
【００５５】
次に、得られたfi(t)でh1(t)を除すると、もしfi(t)＝f(t)であれば、m(t)の次数がL 未満であることに注意すると、
h1(t)＝m(t)＋f(t)p(ux(t), uy(t), t) (5)
の関係から、剰余として平文多項式m(t)が得られる。しかし、f(t)の候補が複数ある場合は必ずしも、平文多項式m(t)が得られない。そこで、ここで得られた剰余m1(t)とし、更にfi(t)でh2(t)を除した時に得られる剰余をm2(t)とすると、もしfi(t)＝f(t)であれば、m1(t)＝m2(t)となるはずである。逆にm1(t)≠m2(t)であればfi(t)≠f(t)であると言える。そこで、全ての候補fi(t)について、検査を行い、検査に成功（即ち、２つの剰余が一致した）候補をf(t)とする。
【００５６】
一方で、検査に成功した候補が複数ある場合や１つも無かった場合は復号失敗として処理する。前者の場合は理論的に否定はできないが、確率は無視できるほど小さいと考えられる。後者の場合は理論的には有り得ないが、送信側の計算ミスや伝送路上での改竄などの何らかの理由により正しくない暗号文を受信したことにより起こる可能性がある。
【００５７】
次に、得られた平文多項式m(t)から平文埋め込み処理と逆の処理で平文mを求めることができる。
【００５８】
最後に本実施形態における鍵生成方法を説明する。本実施形態の鍵生成はセクションD1, D2をランダムに選び、それに対応したファイブレーションを計算することによって行う。但し、生成された代数曲面が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。代数曲面（のファイブレーション）は、一般に次式のように書ける。
【数４】
2008026498.tif 000006
【００５９】
ここで、eij(t)は１変数多項式である。
【００６０】
まず、システムパラメータとして素体の標数pを決める。このとき、pは小さくても安全性に問題は生じない。さて、セクションD1, D2を
D1 : (x, y, t)＝(ux(t), uy(t), t),  
D2 : (x, y, t)＝(vx(t), vy(t), t)
とおいて代数曲面Xに代入し、
Σ(i,j) eij(t)ux(t)iuy(t)j＝0
Σ(i,j) eij(t)vx(t)ivy(t)j＝0
を得る。これらを辺々引くと両式に共通の定数項e00(t)が消え、
【数５】
2008026498.tif 000007
【００６１】
から多項式となるc10(t)を生成するには、
ux(t)−vx(t)｜uy(t)−vy(t)
のように設定すれば十分である（なお、A｜Bの表記は、AがBを割り切ること、即ちBがAの倍数（倍式）であることを意味する）。このことは式(7)と
(ux(t)−vx(t))｜(ux(t)i−vx(t)i)
(uy(t)−vy(t))｜(uy(t)j−vy(t)j)
から明らかである。
【００６２】
以上のことを利用して以下に示すアルゴリズムで鍵生成を行うことができる。まず、λx(t)｜λy(t)となる２つの多項式をランダムに選択する。
【００６３】
具体的にこのような多項式の組λx(t),λy(t)を求めるには、dをセクションの最大次数としたとき、例えばｄ次以下のλx(t)をランダムに与えて、次数d−deg λx(t)以下のランダムな多項式c(t)によってλy(t)＝c(t)λx(t)を計算すればよい。
【００６４】
ここで、λx(t)＝ux(t)−vx(t), λy(t)＝uy(t)−vy(t)
とおき、多項式vx(t)をランダムに選択し、
ux(t)＝λx(t)＋vx(t)
によってux(t)を計算する。λx(t), vx(t)の次数はd以下なので、ux(t)の次数もd以下となる。
【００６５】
同様に多項式vy(t)をランダムに選択し
uy(t)＝λy(t)＋vy(t)
によってuy(t)を計算する。同様にλy(t), vy(t)の次数はd以下なのでuy(t)の次数もd以下となる。
【００６６】
次に、e00(t), e10(t)x以外の係数eij(t)((i,j)≠(0,0),(1,0))をランダムに生成し、前述のように計算されたux(t), vx(t), uy(t), vy(t)を利用して式(6)に従ってe10(t)を計算する。更に、
【数６】
2008026498.tif 000008
【００６７】
を計算することにより多項式e00(t)が得られる。
【００６８】
＜第１の実施形態のバリエーション＞
第１のバリエーションは、暗号化処理に用いる式(3)の変形に関するバリエーションである。式(3)は、例えば
F(x, y, t)＝m(t)−f(t)s(x, y, t)−X(x, y, t)r(x, y, t)
のように変形しても同様に暗号化／復号が可能であり、同様の安全性が証明可能である。このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することが十分可能である。
【００６９】
第２のバリエーションは、平文mを１変数既約多項式f(t)にも埋め込む方式である。前述した実施形態ではf(t)をランダムに生成する方式を示したが、秘密鍵無しにf(t)を求めることが困難であることも本発明の公開鍵暗号の性質であるから、f(t)にも平文情報を埋め込む方式が実現可能となっている。
【００７０】
f(t)にも平文mを埋め込む場合、より大きなサイズの平文を一度に暗号化できる。但し、埋め込んだ結果f(t)を既約多項式とする必要から、特定の係数にはランダムな係数が入るように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文mを埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。仮に得られなかった場合にはf(t)の次数を上げることにより、探索範囲を増やすことも可能である。このような変形を施しても同様の安全性が実現できる。
【００７１】
また、復号処理に関しては、m(t)と共にf(t)を展開し、f(t)のうちの予め定められた一部の係数から平文mの一部を取り出すことで復号が可能となる。
【００７２】
第３のバリエーションは、復号処理において、式(4)からh1(t)−h2(t)を因数分解して、次数がL以上の因数を取得する際にf(t)の候補が複数ある場合、本実施形態では全ての候補に関して、２つの剰余m1(t)とm2(t)を比較して、１つの候補のみが一致することを確認して、平文多項式を決定していた。しかし、（本実施形態でも述べた通り）２つ以上の候補がそれぞれ別々の平文多項式として一致することは無視できるほど小さい確率だと考えられるため、m1(t)とm2(t)が一致する候補があった場合に、それをf(t)と考えて対応するm1(t)を平文多項式処理を進めても誤った平文となる確率は無視できる程度である。また、このように構成することで、復号処理の一部を削減することが可能になるばかりでなく、他の（無視できる確率を除いて正しいf(t)とならない）f(t)の候補に関して同様の処理を行なう必要がなくなるため、平文多項式検査処理の回数を平均して半分程度に減らすことが可能となる。
【００７３】
＜安全性の検討＞
以下では前述したように構成した本発明の公開鍵暗号の安全性に関して［１］〜［３］に示すように考察する。
【００７４】
［１］総当り攻撃
暗号文F(x, y, t)を構成する各要素m(t), f(t), s(x, y, t), r(x, y, t)を
【数７】
2008026498.tif 000009
【００７５】
とおき、これらと暗号文F(x, y, t)を比較することによって、多次多変数連立方程式系を生成し、これを解くという攻撃が考えられる。しかしこの場合、r(x, y, t)をx, yの多項式として見て、十分多くの項を含ませると共に、x, yの多項式として見たとき各項の係数となる多項式の次数を十分高くすることにより、変数の数を増大させ、容易に解けないレベルにまで高めることが可能である。例えば、現在１００程度の変数を持つ多次多変数方程式は現在の計算機処理量と処理手法では解くのが極めて困難である。そこで、項や係数の次数を変数の数が１００を超える程度にまで増大させ、本攻撃を回避することができる。
【００７６】
［２］リダクション攻撃
本発明の公開鍵暗号では代数曲面X(x, y, t)のみが公開されている。そこで暗号文F(x, y, t)をX(x, y, t)で割った余りとして、m(t)＋f(t)s(x, y, t)が求まらないかを検討しなくてはならない。しかし、３変数多項式同士の割り算の場合、剰余が一意に決まらない。なぜならば文献（D. コックス  他,“グレブナ基底と代数多様体入門（上）,” Springer(200)，p.94 例4）にあるように２変数以上の多項式では一般に除法の定理が成り立たないためである。しかも、暗号文の性質から
degx (m(t)＋f(t)s(x, y, t))＞degx X(x, y, t)
degy (m(t)＋f(t)s(x, y, t))＞degy X(x, y, t)        (9)
degt (m(t)＋f(t)s(x, y, t)) ＞degt X(x, y, t)
の３つの条件が得られ、除する式X(x, y, t)よりも次数の高い余りを見出さなくてはならず、更に正しい剰余m(t)＋f(t)s(x, y, t)を得ることを困難にしている。ここで、degx g(x, y, t)の表記は、多項式g(x, y, t)をｘの多項式として見た時の次数を示している。
【００７７】
［３］代入攻撃
［３−１：代数曲面上の代数曲線を代入する攻撃］
（セクションを含む）代数曲線はωをパラメータとして
x＝ux(ω), y＝uy(ω), t＝ut(ω)         (10)
のように書ける。ここでセクションはω＝tとした特殊な場合と考える。前述の鍵生成アルゴリズムに従って鍵生成すると、degt(X(x, y, t)はdegx X(x, y, t), degy X(x, y, t)よりも相当に大きくなる。このため、deg ut(ω) ＞ 2の場合は変数の数がセクションの場合(deg ut(ω)＝1) よりも困難になると考えられる。
【００７８】
deg ut(ω)＝1の場合の代数曲線は簡単な線型変換によってセクションとなるので、これは求セクション問題の困難性の仮定から困難である。
【００７９】
deg ut(ω)＝0の場合、代数曲線はファイバーである。代数曲面のファイバーは、ファイブレーションを持つ代数曲面X(x, y, t)においてはtに特殊値tiを代入することにより容易に求めることができる。
【００８０】
従って、これを暗号文F(x, y, t)に代入することで、
F(ux(ω), uy(ω), ti)＝m(ti)＋f(ti)s(ux(ω), uy(ω), ti)
のような連立方程式が導かれるが、tiに取りえる値は高々pだけであり、これらの関係式からは何の情報も導かれない。
【００８１】
［３−２：代数曲面外の代数曲線を代入する攻撃］
代数曲面外の代数曲線の場合も式(10)として書け、X(ux(ω), uy(ω), ut(ω))≠0である。よって、
【数８】
2008026498.tif 000010
【００８２】
を得る。しかし、ここで分かっている式はX(ux(ω), uy(ω), ut(ω))であるのでF(ux(ω), uy(ω), ut(ω))をX(ux(ω), uy(ω), ut(ω))でリダクションする攻撃が考えられる。これは１変数なので可能ではあるが、式(9)により、m(ut(ω))＋f(ut(ω))s(ux(ω), uy(ω), ut(ω))の次数の方が、X(ux(ω), uy(ω), ut(ω))の次数が大きいため正確な剰余に辿りつくことは容易ではない。
【００８３】
［３−３：代数曲面上の有理点を代入する攻撃］
代数曲面X(x, y, t)の有理点（X(x, y, t)＝ 0となる点）を代入することによる攻撃がある。即ち、平文多項式をa0, a1, ・ ・ ・ , aL−1を未知数として
m(t)＝aL−1xL−1＋・ ・ ・＋a1x＋a0
とおく。（公開鍵である）代数曲面Xt(x, y, t)＝0のK 有理点(xi, yi, ti)は（どのような代数曲面でも）比較的簡単かつ大量に求まることが知られているため、これらの有理点を暗号文F(x, y, t)に代入して、
F(xi, yi, ti)＝m(ti)＋f(ti)s(xi, yi, ti)
という関係式が大量に求まる。これらを連立させるとm(t)が解ける可能性がある。
【００８４】
しかし、f(t), s(x, y, t)はランダムな多項式である。特に
【数９】
2008026498.tif 000011
【００８５】
はX(x, y, t)r(x, y, t)に含まれる項を全て含むと共に、各項の係数の次数から１変数既約多項式f(t)の次数を減じた値だけの次数を持つ係数が対応するs(x, y, t)の項にランダムに書かれる。このため、r(x, y, t)の各係数の次数を十分大きくしておけば、必然的にs(x, y, t)の係数の次数も方程式が解けないほど大きくなり、事実上計算不可能となる。
【００８６】
従ってこのような攻撃は本発明の公開鍵暗号にとっては脅威とはならない。
【００８７】
一方、暗号文からs(x, y, t)の因子を削除すると、連立方程式は
F(xi, yi, ti)＝m(ti)＋f(ti)
となり
degm(t)＜deg f(t)＝L
であるのでLが１００程度であっても比較的簡単に係数が求められてしまう。この理由で因子s(x, y, t)が存在する。
【００８８】
以上のように本発明の公開鍵暗号は攻撃に対する耐性がある。即ち（逆に言うと）本発明の公開鍵暗号は耐性を持つように各構成要素が設定されている。
【００８９】
（第１の実施形態の具体的な構成）
次に、本発明の第１の実施形態について具体的に説明する。図２は本発明の第１の実施形態に係る暗号装置の全体構成図であり、図３は同実施形態における復号装置の全体構成図である。
【００９０】
なお、以下の暗号装置１０及び復号装置２０は、各装置１０，２０毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【００９１】
ここで、暗号装置１０は、図２に示すように、システムパラメータ格納部１１、メモリ１２、平文入力部１３、公開鍵入力部１４、平文埋め込み部１５、暗号化部１６、暗号文出力部１７及び演算部２０を備えている。演算部２０は、メモリ２１、１変数既約多項式生成部２２、第１多項式生成部２３、ランダム値生成部２４及び第２多項式生成部２５を備えている。
【００９２】
システムパラメータ格納部１１は、暗号化部１６から読出可能なメモリであり、システムパラメータである１変数既約多項式f(t)の次数Lと素体の標数pを格納している。
【００９３】
メモリ（ハードウエア資源）１２は、暗号化部１６から処理中のデータ等が適宜読出／書込可能となっている。
【００９４】
平文入力部１３は、外部から入力された平文（メッセージ）ｍを平文埋め込み部１５に送出する機能をもっている。
【００９５】
公開鍵入力部１４は、外部から入力された公開鍵X(x, y, t)を平文埋め込み部１５及び暗号化部１６に送出する機能をもっている。
【００９６】
平文埋め込み部１５は、平文入力部１３から受けた平文m及び公開鍵入力部１４から受けた公開鍵に基づいて、平文mを１変数tで次数L−１以下の平文多項式m(t)の係数として埋め込む機能と、得られた平文多項式m(t)を暗号化部１６に送出する機能をもっている。
【００９７】
暗号化部１６は、平文埋め込み部１３から受けた平文多項式ｍ(t)及び公開鍵入力部１４から受けた公開鍵Ｘ(x,y,t)に基づいて、図４〜図６に示す動作を実行するように、後段の各部１７，２０〜２５を制御するものであり、特に、平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、平文多項式m(t)から暗号文F＝Epk(m, s, r, f, X)＝F(x, y, t)を生成する機能をもっている。
【００９８】
暗号文出力部１７は、暗号化部１６により生成された暗号文F(x, y, t)を出力する機能をもっている。
【００９９】
メモリ（ハードウェア資源）２１は、暗号化部１６及び各生成部２２〜２５から処理中のデータ等が適宜読出／書込可能となっている。
【０１００】
１変数既約多項式生成部２２は、暗号化部１６に制御され、次数L以上のランダムな１変数既約多項式f(t)を生成する機能をもっている。
【０１０１】
第１多項式生成部２３、ランダム値生成部２４及び第２多項式生成部２５は、暗号化部１６に制御され、「ファイブレーションX(x, y, t)と３変数多項式r(x, y, t)との乗算結果X(x, y, t)r(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s(x, y, t)との乗算結果f(t)s(x, y, t)」とを互いにx, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成するように、ランダム３変数多項式r(x, y, t)、s(x, y, t)を生成する多項式生成機能をもっている。具体的には、第１多項式生成部２３、ランダム値生成部２４及び第２多項式生成部２５は、以下の機能をもっている。
【０１０２】
第１多項式生成部２３は、暗号化部１６に制御され、１変数既約多項式f(t)の次数L0を取得する機能と、ファイブレーションX(x, y, t)をx, yの２変数多項式Σcij(t)xiyjとしたとき、係数cij(t)の次数の最小値dtを選択する機能と、３変数多項式r(x, y, t)をxとyの多項式としたとき、多項式r(x, y, t)に含まれる複数の単項式rij(t)xiyjのうちの定数項r00(t)を、tの次数がL0−dt以上となる範囲でランダムに算出する機能と、複数の単項式rij(t)xiyjのうちの定数項r00(t)以外の変数項rij(t)xiyjを、tの次数がL0−dt以上となる範囲でランダムに算出する機能と、定数項r00(t)及び変数項rij(t)xiyjを足し合わせて、３変数多項式r(x, y, t)を算出する機能とを持っている。
【０１０３】
ランダム値生成部２４は、各多項式生成部２３，２５に制御され、指定されたビット数のランダム値zを生成して多項式生成部２３，２５に返信する機能をもっている。
【０１０４】
第２多項式生成部２５は、暗号化部１６に制御され、ファイブレーションX(x, y, t)と当該３変数多項式r(x, y, t)とを乗算し、乗算結果X(x, y, t)r(x, y, t)を得る機能と、３変数多項式s(x, y, t)をxとyの多項式としたとき、乗算結果X(x, y, t)r(x, y, t)に含まれる複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)のｔの次数degt s’00(t)に基づいて、前記多項式s(x, y, t)の定数項s00(t)を、tの次数がdegt s’00(t)−L0となる範囲でランダムに算出する機能と、複数の単項式s’ij(t)xiyjのうちの定数項s’00(t)以外の変数項s’ij(t)xiyjに基づいて、多項式s(x, y, t)の変数項sij(t)xiyjを、tの次数がdegt s’ij(t)−L0となる範囲でランダムに算出する機能と、定数項s00(t)及び前記変数項sij(t)xiyjを足し合わせて、３変数多項式s(x, y, t)を生成する機能とをもっている。
【０１０５】
一方、復号装置３０は、図３に示すように、パラメータ格納部３１、メモリ３２、暗号文入力部３３、鍵入力部３４、復号部３５、平文展開部３６、平文出力部３７及び演算部４０を備えている。演算部４０は、メモリ４１、セクション代入部４２、１変数多項式演算部４３、１変数多項式因数分解部４４、１変数多項式剰余演算部４５及び平文多項式検査部４６を備えている。
【０１０６】
ここで、パラメータ格納部３１は、復号部３５から読出可能なメモリであり、システムパラメータである１変数既約多項式f(t)の次数Lと素体の標数pを格納している。
【０１０７】
メモリ３２は、復号部３５から処理中のデータ等が適宜読出／書込可能となっている。
【０１０８】
暗号文入力部３３は、外部から入力された暗号文Fを復号部３５に送出する機能をもっている。
【０１０９】
鍵入力部３４は、外部から入力された公開鍵X(x, y, t)と秘密鍵を復号部３５に送出する機能をもっている。
【０１１０】
復号部３５は、図７〜図８に示す動作を実行するように、後段の各部３６，４０〜４６を制御する機能をもっている。
【０１１１】
平文展開部３６は、復号部３５に制御され、検査の結果、両者が一致する場合、当該多項式候補m1(t)又はm2(t)の係数からメッセージmを展開する機能をもっている。
【０１１２】
平文出力部３７は、平文展開部２９から受けた平文ｍを出力する機能をもっている。
【０１１３】
メモリ４１は、復号部３５及び各部４２〜４６から処理中のデータ等が適宜読出／書込可能となっている。
【０１１４】
セクション代入部４２は、復号部３５に制御され、入力された暗号文Fに対し、各セクションD1, D2を代入して２つの１変数多項式ｈ1(t),ｈ2(t)を生成する機能をもっている。
【０１１５】
１変数多項式演算部４３は、復号部３５に制御され、各１変数多項式h1(t), h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る機能をもっている。
【０１１６】
１変数多項式因数分解部４４は、復号部３５に制御され、減算結果{h1(t)−h2(t)}を因数分解する機能と、因数分解結果からL以上の次数を持つ全ての既約多項式f(t)を抽出する機能とをもっている。
【０１１７】
１変数多項式剰余演算部４５は、復号部３５に制御され、抽出された既約多項式f(t)で１変数多項式h1(t)を除算し、剰余として多項式候補m1(t)を得ると共に、当該既約多項式f(t)で１変数多項式h2(t)を除算し、剰余として多項式候補m2(t)を得る機能とをもっている。
【０１１８】
平文多項式検査部４６は、復号部３５に制御され、多項式候補m1(t), m2(t)が互いに一致するか否かを検査する機能と、検査結果を復号部３５に送出する機能とをもっている。
【０１１９】
次に、以上のように構成された暗号装置及び復号装置の動作を図４乃至図８のフローチャートを用いて説明する。
【０１２０】
（暗号化処理：図４乃至図６）
暗号装置１０においては、平文入力部１３から平文（メッセージ）mが入力され（ＳＴ１）、公開鍵入力部１４から公開鍵X(x, y, t)が入力されると（ＳＴ２）、処理を開始する。また、システムパラメータである１変数既約多項式f(t)の次数Lと素体の標数pは、暗号化部１６により、システムパラメータ格納部１１から取得され（ＳＴ３）、平文埋め込み部１５に送られる。
【０１２１】
平文埋め込み部１５では、別途、平文入力部１３から送信された平文mを、標数pのビット長よりも１小さいビット長にL−1分割する。例えばp＝17の場合は、平文mを４ビット毎に分割することができる。ここで、平文mが１６進表示で
m＝0x315763ef25c04c792ef151
であるとする。この場合、平文埋め込み部１５は、１６進表示の平文mを４ビット毎に分割し、次式に示すように、この平文mを係数としてL−1次の平文多項式m(t)に埋め込む（ＳＴ４）。
【０１２２】
m(t)＝3t21＋t20＋5t19＋7t18＋6t17＋3t16＋15t15＋11t14＋2t13＋5t12
＋12t11＋0t10＋4t9＋12t8＋7t7＋9t6＋2t5＋14t4＋15t3＋t2＋5t＋1
平文埋め込み部１５は、平文多項式m(t)を暗号化部１６に送信する。一方で、公開鍵入力部１４は公開鍵X(x, y, t)を暗号化部１６に送信する。システムパラメータ格納部１１はパラメータL, pを暗号化部１６に送信する。
【０１２３】
暗号化部１６では、平文多項式m(t)、パラメータL, p、公開鍵X(x, y, t)を受信すると、これらをメモリ１２に書き込む。しかる後、暗号化部１６は、メモリ１２内のパラメータL, pを１変数既約多項式生成部２２に送信する。
【０１２４】
１変数既約多項式生成部２２は、L次以上の１変数既約多項式f(t)をランダムに生成し（ＳＴ５）、得られた１変数既約多項式f(t)を暗号化部１６に返信する。ここで、既約多項式の生成は、L次以上の多項式をランダムに生成し、Fp上の既約性判定を１変数多項式が既約多項式となるまで繰り返すことにより行う。
【０１２５】
暗号化部１６は、１変数既約多項式f(t)をメモリ１２に保存した後、第１多項式生成部２３にp, L, f(t), X(x, y, t)を送信する。第１多項式生成部２３は、以下の処理を実行して３変数多項式r(x, y, t)を生成する。
【０１２６】
始めに、第１多項式生成部２３は、受信した１変数既約多項式f(t)の次数L0を求める（ＳＴ６）。次数L0としては最高次の次数を求めれば良く、具体的な処理はデータ構造によって異なるが、当業者であれば容易に実現できる。次に、公開鍵である代数曲面X(x, y, t)をx, yの多項式として見た場合の次式に関し、係数cij(t)の次数の最小値dtを求める（ＳＴ７）。
【数１０】
2008026498.tif 000012
【０１２７】
を得たとき、係数cij(t)を抽出する処理と、係数cij(t)からｔの次数を求める処理と、ｔの次数の最小値dtを選択する処理とを実行すれば良い。なお、ｔの次数を求める処理としては、f(t)の次数を求めた手法と同じ手法を実行すれば良い。
【０１２８】
次に、第１多項式生成部２３は、r(x, y, t)をx, yの多項式として見た場合に、各項を生成する単項式rij(t)xiyjを決定する。まず、定数項r00(t)を以下のように決定する（ＳＴ８〜ＳＴ１０）。すなわち、値L0−dt＋1を計算し（ＳＴ８）、得られた値L0−dt＋1以上の値d00をランダム値生成部２４に送信する。ランダム値生成部２４は、d00ビットのランダム値を生成し（ＳＴ９）、このランダム値を第１多項式生成部２３に返信する。ここで、L0−dt＋1以上の値d00を得るには、例えばランダム値生成部２４に自然数３を送信して０〜７の数を生成し、前記生成された値をL0−dt＋1に加える方法がある。
【０１２９】
第１多項式生成部２３は、ランダム値を受信すると、最高次の係数を１とするためランダム値の最上位ビットを強制的に１にする。次に、第１多項式生成部２３は、ランダム値の第ｉビットの値ziをti−1の係数として、次式に示すように多項式を生成し、この多項式を定数項r00(t)とする（ＳＴ１０）。
【数１１】
2008026498.tif 000013
【０１３０】
定数項r00(t)の次数は、L0−dt以上となっている。理由は、最小次数dtのX(x, y, t)をr(x, y, t)に乗じた際に、得られる多項式X(x, y, t)r(x, y, t)のｔに関する最小次数をL0とするためである。これは定数項以外の変数項rij(t)xiyjのｔの次数でも同様である。
【０１３１】
次に、定数項以外の変数項rij(t)xiyjを以下のように決定する（ＳＴ１１〜ＳＴ１６）。なお、定数項以外にどのような項を否零の項として採用するかはシステムで予め定められる。ここでは、x及びyに関する次数の上限をｅとする項を否零の項として採用するものとする。
【０１３２】
第１多項式生成部２３は、メモリ２１から次数の上限ｅを読み出してランダム値生成部２４に送出する。ランダム値生成部２４は、上限e以下の値i, jを生成し（ＳＴ１１）、この値i, jが過去に生成した値か否かを判定する（ＳＴ１２）。この判定は、例えば過去に生成した値i, jを書き込んだメモリ２１内のリストを参照し、今回生成した値i, jがこのリストに無いことを確認すればよい。ステップＳＴ１２の判定の結果、過去に生成した値の場合にはステップＳＴ１１に戻る。一方、ステップＳＴ１２の判定の結果、否の場合には、生成した値i, jをそれぞれ次数i, jとすることにより、項の変数xiyjを決定する。これに加え、否の場合には今回生成した値i, jをリストに追加する。
【０１３３】
また、決定した項の係数rij(t)は、次式に示すように、定数項r00(t)を生成するステップＳＴ９〜ＳＴ１０と同じ処理で生成する（ＳＴ１３〜ＳＴ１４）。但し、式１２におけいてdijはrij(t)の次数であり、前記d00同様L0−dt＋1以上の値である。
【数１２】
2008026498.tif 000014
【０１３４】
しかる後、係数rij(t)及び変数xiyjに基づいて、変数項rij(t)xiyjを生成する（ＳＴ１５）。また、否零の項の数に関しても同様にメモリ２１に格納されている否零項の数を示すパラメータｗによって決められる。すなわち、第１多項式生成部２３は、ステップＳＴ１５の後、合計でｗ個の否零項を生成したか否かを判定し（ＳＴ１６）、否の場合にはステップＳＴ１１に戻る。ここで、ｗが大きければ大きいほどできる暗号文は大きくなるので、安全性が確保できる最適なｗを設計段階で決定する必要がある。
【０１３５】
一方、ステップＳＴ１６の判定の結果、ｗ個の否零項を生成した場合には、第１多項式生成部２３は、定数項r00(t)と、全ての変数項rij(t)xiyjとを足し合わせることにより、３変数多項式r(x, y, t)を生成する（ＳＴ１７）。第１多項式生成部２３は、当該３変数多項式r(x, y, t)を暗号化部１６に送信し、処理を終了する。暗号化部１６は、３変数多項式r(x, y, t)をメモリ１２に書き込んで保存する。
【０１３６】
以下で３変数多項式の係数を述べるときには、特に断らない限り、x, yのみの多項式Σcij(t)xiyjと考えた時の項cij(t)xiyjを対象にする。即ち、項cij(t)xiyjの係数はcij(t)であり、係数の次数はcij(t)のtに関する次数である。この説明は、“cij(t)xiyj”に限らず、“rij(t)xiyj”又は“sij(t)xiyj”等でも同様である。
【０１３７】
次に、暗号化部１６は、メモリ１２内のr(x, y, t)に基づいて、s’(x, y, t)＝X(x, y, t)r(x, y, t)を計算し（ＳＴ１８）、X(x, y, t)r(x, y, t)とp, L0を第２多項式生成部２５に送信する。
【０１３８】
第２多項式生成部２５では、多項式s(x, y, t)を以下のように決定する（ＳＴ１９〜ＳＴ２７）。
【０１３９】
始めに、計算したX(x, y, t)r(x, y, t)に含まれる項のそれぞれについて、それらの係数を次数がX(x, y, t)r(x, y, t)における対応する項の次数からL0を減じた値となるようにランダムに決定する。ここで、係数はr(x, y, t)で各係数を生成した場合と同じ処理で決定する。以下、念のため、説明する。
【０１４０】
第２多項式生成部２５は、X(x, y, t)r(x, y, t)＝s’(x, y, t)をx, yの多項式として見たときに各項を生成する単項式s’ij(t)xiyjに基づいて、３変数多項式s(x, y, t)の各項を生成する単項式sij(t)xiyjを決定する。まず、定数項s00(t)を以下のように決定する（ＳＴ１９〜ＳＴ２１）。すなわち、s’(x, y, t)の定数項s’00(t)におけるtの次数degt s’00(t)から値degt s’00(t)−L0＋1を計算し（ＳＴ１９）、得られた値degt s’00(t)−L0＋1をランダム値生成部２４に送信する。ランダム値生成部２４は、degt s’00(t)−L0＋1ビットのランダム値を生成し（ＳＴ２０）、このランダム値を第２多項式生成部２５に返信する。
【０１４１】
第２多項式生成部２５は、ランダム値を受信すると、最高次の係数を１とするためランダム値の最上位ビットを強制的に１にする。次に、第２多項式生成部２５は、ランダム値の第ｉビットの値ziをti−1の係数として、次式のように多項式を生成し、この多項式を定数項s00(t)とする（ＳＴ２１）。
【数１３】
2008026498.tif 000015
【０１４２】
定数項s00(t)の次数は、degt s’00(t)−L0となっている。理由は、最小次数L0のｆ(t)をs(x, y, t)に乗じた際に、得られる多項式f(t)s(x, y, t)のｔに関する次数をX(x, y, t)r(x, y, t)のｔに関する次数degt s’00(t)に合わせるためである。これは定数項以外の変数項sij(t)xiyjのｔの次数でも同様である。
【０１４３】
次に、定数項以外の項sij(t)xiyjを以下のように決定する（ＳＴ２２〜ＳＴ２６）。すなわち、変数項s’ij(t)xiyjの係数s’ij(t)におけるtの次数degt s’ij(t)から値degt s’ij(t)−L0＋1を計算し（ＳＴ２２）、得られた値degt s’ij(t)−L0＋1をランダム値生成部２４に送信する。ランダム値生成部２４は、degt s’ij(t)−L0＋1ビットのランダム値を生成し（ＳＴ２３）、このランダム値を第２多項式生成部２５に返信する。
【０１４４】
第２多項式生成部２５は、ランダム値を受信すると、前述同様にランダム値の最上位ビットを強制的に１にする。次に、第２多項式生成部２５は、ランダム値の第ｉビットの値ziをti−1の係数として、次式に示すように多項式を生成し、この多項式を変数項の係数sij(t)とする（ＳＴ２４）。なお、変数項の係数sij(t)は定数項を生成する処理と同じ処理で生成する。
【数１４】
2008026498.tif 000016
【０１４５】
しかる後、第２多項式生成部２５は、係数sij(t)及び変数xiyjに基づいて、変数項sij(t)xiyjを生成する（ＳＴ２５）。この変数項sij(t)xiyjの生成は、s’(x, y, t)における変数項s’ij(t)xiyj毎に、順次、実行される。第２多項式生成部２５、ステップＳＴ２５の後、r(x, y ,t)X(x, y, t)の各項に対応する全ての項を生成したか否かを判定し（ＳＴ２６）、否の場合にはステップＳＴ２２に戻る。
【０１４６】
一方、ステップＳＴ２６の判定の結果、全ての項を生成した場合には、第２多項式生成部２５は、定数項s00(t)と、全ての変数項sij(t)xiyjとを足し合わせることにより、３変数多項式s(x, y, t)を生成する（ＳＴ２７）。第２多項式生成部２５は、当該３変数多項式s(x, y, t)を暗号化部１６に送信し、処理を終了する。暗号化部１６は、３変数多項式s(x, y, t)をメモリ１２に書き込んで保存する。
【０１４７】
暗号化部１６は、以上の処理で得られたm(t), f(t), s(x, y, t), r(x, y, t)と公開鍵である代数曲面X(x, y, t)を利用して、式(3)に従って暗号文F(x, y, t)を計算し展開する（ＳＴ２８）。暗号化部１６は、この暗号文F(x, y, t)を（必要ならば予め定められたフォーマットに合わせて変形し）暗号文出力部１７から出力し（ＳＴ２９）、暗号化処理を終了する。
【０１４８】
（復号処理：図７及び図８）
復号装置３０においては、暗号文入力部３３から暗号文F(x, y, t)を取得し（ＳＴ３１）、鍵入力部３４から公開鍵X(x, y, t)と秘密鍵を取得し（ＳＴ３２）、パラメータ格納部３１からp, Lを取得することから復号処理を開始する。ここで、秘密鍵とは２つのセクションD1, D2である。取得された暗号文と鍵情報等は復号部３５に送られる。復号部３５は、暗号文と鍵情報等をメモリ３２に書き込んで保存する。
【０１４９】
復号部３５は、セクション代入部４２にメモリ３２内の暗号文F(x, y, t)とセクションD1を送信する。セクション代入部４２は、D1をF(x, y, t)に代入し、必要に応じて１変数多項式演算部４３を利用することにより、h1(t)を得る（ＳＴ３３）。ここで、１変数多項式演算部４３は１変数多項式の加減乗除演算を行う。得られたh1(t)は、セクション代入部４２から復号部３５に送出される。
【０１５０】
また同様に、復号部３５は、セクション代入部４２にメモリ３２内の暗号文F(x, y, t)とセクションD2を送信する。セクション代入部４２は、セクションD2をF(x, y, t)に代入し、h2(t)を得る（ＳＴ３４）。得られたh2(t)は、セクション代入部４２から復号部３５に送出される。
【０１５１】
復号部３５は、h1(t), h2(t)を１変数多項式演算部４３に送信して減算させる。１変数多項式演算部４３は、減算結果{h1(t)−h2(t)}を復号部３５に送出する。
【０１５２】
復号部３５は、減算結果{h1(t)−h2(t)}を１変数多項式因数分解部４４に送信して因数分解させる（ＳＴ３５）。１変数多項式因数分解部４４は、因数分解結果のうち、次数L以上の因子として既約多項式f(t)を得ると（ＳＴ３６）、この既約多項式f(t)を復号部３５に送出する。なお、本復号処理では１変数既約多項式f(t)の候補が複数現れる可能性があるため、正しいf(t)を選択するように以下の処理を行なう。まず、復号部３５は、f(t)候補を１つ抽出し（ＳＴ３７）、正しいf(t)候補のカウンタ値kを０にセットする（ＳＴ３８）。なお、カウンタ値kはメモリ４１に記憶されている。
【０１５３】
復号部３５は、１変数多項式剰余演算部４５を利用してh1(t)をf(t)で除し、剰余として平文多項式m1(t)を得る（ＳＴ３９）。同様に１変数多項式剰余演算部４５を利用してh2(t)をf(t)で除し、剰余として平文多項式m2(t)を得る（ＳＴ４０）。
【０１５４】
次に、復号部３５は、これらの式m1(t), m2(t)を平文多項式検査部４６に送信する。平文多項式検査部４６は、m1(t), m2(t)が等しいか否かを判定し（ＳＴ４１）、判定結果を復号部３５に送信する。判定結果が等しい場合、復号部３５は、メモリ４１にm1(t)＝m2(t)なる多項式を格納し、カウンタ値kを１だけインクリメントして（ＳＴ４２）、次候補の有無を判定し（ＳＴ４３）、次候補があれば、次候補の多項式をf(t)とおいて（ＳＴ４４）、ステップＳＴ３９〜ＳＴ４３の処理を繰り返す。
【０１５５】
ステップＳＴ４１の判定結果が等しくない場合、復号部３５は、f(t)候補が誤りであることを意味するため、ステップＳＴ４３に進んで次候補のf(t)で同様の操作を行う。
【０１５６】
一方、ステップＳＴ４３の判定の結果、次候補が無い場合には、復号部３５は、カウンタ値kがk＝1か否（k＝0か、k＜2）かを判定する（ＳＴ４５）。
【０１５７】
ステップＳＴ４５の判定の結果、k＝0か、k＜2の場合には、正しい候補が全くないか、２つ以上存在することを意味するため、復号処理の失敗であるから、エラーを出力して復号処理を終了する（ＳＴ４６）。
【０１５８】
ステップＳＴ４５の判定の結果、k＝1の場合には、正しいf(t)が１つだけ見つかったことを意味するため、復号部３５は、メモリ４１に格納したm(t)を平文多項式として、平文展開部３６へ送信する。平文展開部３６は、平文多項式m(t)を展開し（ＳＴ４７）、得られた平文mを平文出力部３７に送出する。平文出力部３７は、この平文mを出力することにより（ＳＴ４８）、復号処理を終了する。
【０１５９】
上述したように本実施形態によれば、暗号文Fに含まれる２つの乗算結果X(x, y, t)r(x, y, t)及びf(t)s(x, y, t)が、それぞれx, yの多項式として見たときの変数xiyjについての同類項から構成される。これにより、一方の乗算結果X(x, y, t)r(x, y, t)にはあるが、他方の乗算結果f(t)s(x, y, t)には無いという項を解析する手法を用いても、各項の見分けがつかず、r(x, y, t)の一部が漏洩することがない。
【０１６０】
従って、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止することができる。
【０１６１】
＜第１の実施形態のバリエーション＞
第１のバリエーションは、暗号化処理に用いる式(3)の変形に関するバリエーションである。式(3)は、例えば
F(x, y, t)＝m(t)−f(t)s(x, y, t)−X(x, y, t)r(x, y, t)
のように変形しても同様に暗号化／復号が可能であり、同様の安全性が証明可能である。このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することが十分可能である。
【０１６２】
第２のバリエーションは、平文mを１変数既約多項式f(t)にも埋め込む方式である。前述した実施形態ではf(t)をランダムに生成する方式を示したが、秘密鍵無しにf(t)を求めることが困難であることも本発明の公開鍵暗号の性質であるから、f(t)にも平文情報を埋め込む方式が実現可能となっている。
【０１６３】
f(t)にも平文mを埋め込む場合、より大きなサイズの平文を一度に暗号化できる。但し、埋め込んだ結果f(t)を既約多項式とする必要から、特定の係数にはランダムな係数が入るように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文mを埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。仮に得られなかった場合にはf(t)の次数を上げることにより、探索範囲を増やすことも可能である。このような変形を施しても同様の安全性が実現できる。
【０１６４】
また、復号処理に関しては、m(t)と共にf(t)を展開し、f(t)のうちの予め定められた一部の係数から平文mの一部を取り出すことで復号が可能となる。
【０１６５】
第３のバリエーションは、復号処理のみに関連するバリエーションである。図９のステップＳＴ４１’に示すように、m1(t)＝m2(t)となるf(t)が発見された時点で、復号部３５は、m1(t)を平文展開部３６に送信する。また、復号部３５は、m1(t)＝m2(t)でないときには次候補の有無を判定し（ＳＴ４３’）、次候補が無いときにはエラーを出力して処理を終了する。第３のバリエーションによれば、m1(t)＝m2(t)の判定対象が減るので、復号処理の一部（ＳＴ３８，ＳＴ４２，ＳＴ４５）を削減することが可能となるだけでなく、m1(t)＝m2(t)が成立した時点で残りのf(t)の候補に関して同様の処理を行なう必要がなる。
【０１６６】
補足すると、復号処理において、式(4)からh1(t)−h2(t)を因数分解して、次数がL以上の因数を取得する際にf(t)の候補が複数ある場合、本実施形態では全ての候補に関して、２つの剰余m1(t)とm2(t)を比較して、１つの候補のみが一致することを確認して、平文多項式を決定していた。しかし、（本実施形態でも述べた通り）２つ以上の候補がそれぞれ別々の平文多項式として一致することは無視できるほど小さい確率だと考えられるため、m1(t)とm2(t)が一致する候補があった場合に、それをf(t)と考えて対応するm1(t)に対して平文多項式処理を進めても誤った平文となる確率は無視できる程度である。また、このように構成することで、復号処理の一部を削減することが可能になるばかりでなく、他の（無視できる確率を除いて正しいf(t)とならない）f(t)の候補に関して同様の処理を行なう必要がなくなるため、平文多項式検査処理の回数を平均して半分程度に減らすことが可能となる。
【０１６７】
（第２の実施形態）
（概要）
次に、本発明の第２の実施形態について説明する。本実施形態のシステムパラメータは、第１の実施形態と同じく
1. 素体の標数p
2. Fp上の１変数既約多項式f(t)の次数L
である。また、公開鍵は
1. Fp上の代数曲面Xのファイブレーション:X(x, y, t)
である。秘密鍵は
1. Fp上の代数曲面Xのセクション:D:(x, y, t)＝(ux(t), uy(t), t)
である。第２の実施形態は、第１の実施形態と比較し、秘密鍵であるセクションが１つであることが大きく異なる。第２の実施形態は、このため、秘密鍵のサイズが小さくなる上、鍵生成の自由度が増えるという効果がある。
【０１６８】
（暗号化処理）
本実施形態における暗号化処理の概要を述べる。暗号処理は第１の実施形態とほぼ同じであるが、１つの暗号文F(x, y, t)を生成した第１の実施形態とは異なり、第２の実施形態では、２つの暗号文F1(x, y, t), F2(x, y, t)を生成する。
【０１６９】
具体的には、第２の実施形態は、共通のf(t)を用いて、第１の実施形態と同様の手段で異なる２つのランダムな３変数多項式の組(s1(x, y, t), s2(x, y, t))と(r1(x, y, t), r2(x, y, t))を生成して２つの暗号文F1(x, y, t), F2(x, y, t)を次式のように生成する。
【０１７０】
F1(x, y, t)＝m(t)＋f(t)s1(x, y, t)＋X(x, y, t)r1(x, y, t)
F2(x, y, t)＝m(t)＋f(t)s2(x, y, t)＋X(x, y, t)r2(x, y, t)
受信者は、暗号文F1(x, y, t), F2(x, y, t)を受けると、所有する秘密鍵Dを利用して次のように復号を行う。まず、セクションDを暗号文F1(x, y, t), F2(x, y, t)に代入することにより第１の実施形態と同様の考え方で次の２式h1(t), h2(t)を求める。
【０１７１】
h1(t)＝F1(ux(t), uy(t), t)＝m(t)＋f(t)s1(ux(t), uy(t), t)
h2(t)＝F2(ux(t), uy(t), t)＝m(t)＋f(t)s2(ux(t), uy(t), t)
次に、２式を辺々引き算して次式h1(t)−h2(t)を計算する。
【０１７２】
h1(t)−h2(t)＝f(t){s1(ux(t), uy(t), t)−s2(ux(t), uy(t), t)}
しかる後、h1(t)−h2(t)を因数分解して、最大次数を持つ因数をf(t)と定める。この後の処理は第１の実施形態と同じであるので説明を省略する。
【０１７３】
（鍵生成処理）
最後に本実施形態における鍵生成方法を説明する。本実施形態の鍵生成は第１の実施形態と同様にセクションDをランダムに選び、それに対応したファイブレーションを計算することによって行う。
【０１７４】
但し、本実施形態では第１の実施形態と異なり１つのセクションを満たすように構成すれば良く、第１の実施形態よりも容易にしかも自由度の高い鍵が生成される。
【０１７５】
ここでは代数曲面のうち以下のような代数曲面を例にとって鍵生成方法を示す。
【０１７６】
Xt: y3＝x3＋ξ1(t)x2y＋ξ2(t)xy2＋ξ3(t)y＋ξ4(t)
ここでξ1(t), ξ2(t), ξ3(t), ξ4(t)は１変数多項式である。まず、素体の標数pを決める。このときpは小さくても安全性に問題は生じない。さて、セクションDを
D:(x, y, t)＝(ux(t), uy(t), t)
とおき、定数項以外の１変数多項式ξ1(t), ξ2(t), ξ3(t)をランダムに定め、これらξ1(t), ξ2(t), ξ3(t)とセクションDを代数曲面Xtに代入することで
【数１５】
2008026498.tif 000017
【０１７７】
によりξ4(t)を得る。
【０１７８】
また、第１の実施形態で述べた第１〜第３のバリエーションは本実施形態でも同様に成立する。
【０１７９】
（安全性の検討）
以下ではこのように構成した本実施形態の公開鍵暗号の安全性に関して考察する。基本的に第１の実施形態における安全性の検討がそのまま本実施形態の安全性の検討となる。第１の実施形態と異なるのは暗号文が２つあることであり、この部分の安全性に関して考察を行う。暗号文F1(x, y, t), F2(x, y, t)の引き算を行うと以下のようになる。
【数１６】
2008026498.tif 000018
【０１８０】
この式では、平文多項式m(t)は消去されるもののs1(x, y, t)≠s2(x, y, t) 若しくはr1(x, y, t)≠r2(x, y, t)である。ここで、３変数多項式の因数分解が必ずしも一意的でないことから、その因子等からもほとんど情報が得られない。
【０１８１】
（第２の実施形態の具体的な構成）
次に、本発明の第２の実施形態について具体的に説明する。暗号装置１０及び復号装置３０は、それぞれ第１の実施形態と同様のハードウエア構成を備えているため、前述した図２及び図３を参照して述べる。
【０１８２】
本実施形態は、第１の実施形態の変形形態であり、１つのセクションDと、２つの暗号文F1(x, y, t), F2(x, y, t)とを用いる点で第１の実施形態とは異なっている。そこで、以下の説明は、第１の実施形態と異なる部分について主に述べる。
【０１８３】
具体的には暗号化部１６は、平文埋め込み部１３から受けた平文多項式ｍ(t)及び公開鍵入力部１４から受けた公開鍵Ｘ(x,y,t)に基づいて、図１０〜図１４に示す動作を実行するように、後段の各部１７，２０〜２５を制御するものであり、特に、平文多項式m(t)に対し、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「ファイブレーションX(x, y, t)と３変数多項式r1(x, y, t)との乗算結果X(x, y, t)r1(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s1(x, y, t)との乗算結果f(t)s1(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、平文多項式m(t)から暗号文F1＝Epk(m, s1, r1, f, X)＝F1(x, y, t)を生成する機能とをもっている。
【０１８４】
また暗号化部１６は、平文多項式m(t)に対し、同様に、x, yの多項式として見たときの変数xiyjについての同類項（但し、i, jは０以上の次数）から構成される「ファイブレーションX(x, y, t)と３変数多項式r2(x, y, t)（≠r1(x, y, t)）との乗算結果X(x, y, t)r2(x, y, t)」と、「次数L以上のランダムな１変数既約多項式f(t)と３変数多項式s2(x, y, t)との乗算結果f(t)s2(x, y, t)」とを用いて、加算及び減算のうち少なくとも加算を行う暗号化処理により、平文多項式m(t)から暗号文F2＝Epk(m, s2, r2, f, X)＝F2(x, y, t)を生成する機能をもっている。
【０１８５】
暗号文入力部３３は、外部から入力された暗号文F1(x, y, t), F2(x, y, t)を復号部３５に送出する機能をもっている。
【０１８６】
復号部３５は、図１５〜図１６に示す動作を実行するように、後段の各部３６，４０〜４６を制御する機能をもっている。
【０１８７】
セクション代入部４２は、復号部３５に制御され、入力された暗号文F1(x, y, t), F2(x, y, t)に対し、セクションDを代入して２つの１変数多項式ｈ1(t),ｈ2(t)を生成する機能をもっている。
【０１８８】
次に、以上のように構成された暗号装置及び復号装置の動作を図１０乃至図１６のフローチャートを用いて説明する。
【０１８９】
（暗号化処理：図１０乃至図１４）
暗号装置１０においては、前述同様に、ステップＳＴ１〜ＳＴ７を実行し、公開鍵X(x, y, t)の係数cij(t)におけるｔの次数の最小値dtを求める。
【０１９０】
続いて、暗号装置１０においては、前述したステップＳＴ８〜ＳＴ１７と同様の処理により、３変数多項式r1(x, y, t)を生成し（ＳＴ８ａ〜ＳＴ１７ａ）、前述したステップＳＴ１８〜ＳＴ２７と同様の処理により、３変数多項式s1(x, y, t)を生成する（ＳＴ１８ａ〜ＳＴ２７ａ）。また、暗号装置１０においては、暗号化部１６がm(t), f(t), s1(x, y, t), r1(x, y, t), X(x, y, t)に基づいて、前述したステップＳＴ２８と同様の処理により、第１の暗号文F1(x, y, t)を生成する（ＳＴ２８ａ）。
【０１９１】
次に、暗号装置１０においては、前述したステップＳＴ９〜ＳＴ１７と同様の処理により、３変数多項式r2(x, y, t)を生成し（ＳＴ９ｂ〜ＳＴ１７ｂ）、前述したステップＳＴ１８〜ＳＴ２７と同様の処理により、３変数多項式s2(x, y, t)を生成する（ＳＴ１８ｂ〜ＳＴ２７ｂ）。しかる後、暗号装置１０においては、暗号化部１６がm(t), f(t), s2(x, y, t), r2(x, y, t), X(x, y, t)に基づいて、前述したステップＳＴ２８と同様の処理により、第２の暗号文F2(x, y, t)を生成する（ＳＴ２８ｂ）。
【０１９２】
暗号化部１６は、この暗号文F1(x, y, t), F2(x, y, t)を（必要ならば予め定められたフォーマットに合わせて変形し）暗号文出力部１７から出力し（ＳＴ２９ａｂ）、暗号化処理を終了する。
【０１９３】
（復号処理：図１５及び図１６）
復号装置３０においては、暗号文入力部３３から２つの暗号文F1(x, y, t), F2(x, y, t)を取得し（ＳＴ３１”）、鍵入力部３４から公開鍵X(x, y, t)と秘密鍵を取得し（ＳＴ３２”）、パラメータ格納部３１からp, Lを取得することから復号処理を開始する。ここで、秘密鍵とは１つのセクションDである。取得された暗号文と鍵情報等は復号部３５に送られる。
【０１９４】
続いて、復号部３５は、セクション代入部４２に暗号文F1(x, y, t)とセクションDを送信する。セクション代入部４２は、DをF1(x, y, t)に代入し、必要に応じて１変数多項式演算部４３を利用することにより、h1(t)を得る（ＳＴ３３”）。ここで、１変数多項式演算部４３は１変数多項式の加減乗除演算を行う。得られたh1(t)は、セクション代入部４２から復号部３５に送出される。
【０１９５】
また同様に、復号部３５は、セクション代入部４２に暗号文F2(x, y, t)とセクションDを送信する。セクション代入部４２は、セクションDをF2(x, y, t)に代入し、h2(t)を得る（ＳＴ３４）。得られたh2(t)は、セクション代入部４２から復号部３５に送出される。
【０１９６】
以下、前述同様に、復号装置３０は、ステップＳＴ３５〜ＳＴ４８を実行することにより、復号した平文mを出力する。
【０１９７】
上述したように本実施形態によれば、１つのセクションDと２つの暗号文F1(x, y, t), F2(x, y, t)を用いる場合であっても、第１の実施形態と同様にして各暗号文F1(x, y, t), F2(x, y, t)が構成されるので、暗号文F1, F2を解析しても、f(t)やr1(x, y, t), r2(x, y, t)の一部が漏洩することがない。従って、代数曲面を用いた公開鍵暗号におけるランダム化多項式の漏洩を阻止することができる。
【０１９８】
＜第２の実施形態のバリエーション＞
第１の実施形態で述べた第１のバリエーションと第２のバリエーションは、本実施形態でも同様に実行することができる。また、第３のバリエーションに関しては、図１７のステップＳＴ３３”，ＳＴ３４”に示すように、第１の実施形態の第３のバリエーションから若干の変形を施して同様に実行することができる。
【０１９９】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２００】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０２０１】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０２０２】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０２０３】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０２０４】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０２０５】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２０６】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２０７】
【図１】一般的な代数曲線を説明するための模式図である。
【図２】本発明の第１の実施形態に係る暗号装置の全体構成図である。
【図３】同実施形態における復号装置の全体構成図である。
【図４】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図５】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図６】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図７】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図８】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図９】同実施形態における復号処理のバリエーションを説明するためのフローチャートである。
【図１０】本発明の第２の実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１１】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１２】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１３】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１４】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１５】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図１６】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図１７】同実施形態における復号処理のバリエーションを説明するためのフローチャートである。
【符号の説明】
【０２０８】
１０…暗号装置、１１…システムパラメータ格納部、１２，２１，３２，４１…メモリ、１３…平文入力部、１４…公開鍵入力部、１５…平文埋め込み部、１６…暗号化部、１７…暗号文出力部、２０…演算部、２２…１変数既約多項式生成部、２３…第１多項式生成部、２４…ランダム値生成部、２５…第２多項式生成部、３０…復号装置、３１…パラメータ格納部、３３…暗号文入力部、３４…鍵入力部、３５…復号部、３６…平文展開部、３７…平文出力部、４０…演算部、４２…セクション代入部、４３…１変数多項式演算部、４４…１変数多項式因数分解部、４５…１変数多項式剰余演算部、４６…平文多項式検査部。
【図１】
2008026498.tif 000019
【図２】
2008026498.tif 000020
【図３】
2008026498.tif 000021
【図４】
2008026498.tif 000022
【図５】
2008026498.tif 000023
【図６】
2008026498.tif 000024
【図７】
2008026498.tif 000025
【図８】
2008026498.tif 000026
【図９】
2008026498.tif 000027
【図１０】
2008026498.tif 000028
【図１１】
2008026498.tif 000029
【図１２】
2008026498.tif 000030
【図１３】
2008026498.tif 000031
【図１４】
2008026498.tif 000032
【図１５】
2008026498.tif 000033
【図１６】
2008026498.tif 000034
【図１７】
2008026498.tif 000035