(57)【要約】【課題】代数曲面を用いた公開鍵暗号方式において、因数分解処理と因数抽出処理の負荷を低減することにより、復号処理の効率化を実現する。【解決手段】復号装置２００は、複数の暗号文Fi(x,y,t)（i＝1,…,k）にセクションＤを代入するセクション代入部２０５と、代入後のＬ組の多項式he(t),hw(t)を互いに減算する１変数多項式演算部２０６と、減算結果のＬ個の多項式gj(t)（＝he(t)−hw(t)）（j＝1,…,L）の最大公約式φ(t)を求める最大公約式演算部２０７とを備えている。従って、高い次数の多項式｛h1(t)−h2(t)｝を因数分解して因数を抽出した従来とは異なり、高い次数の多項式gj(t)から低い次数の最大公約式φ(t)を求め、低い次数の最大公約式φ(t)を因数分解して因数を抽出するので、上記課題を解決できる。【選択図】  図２
2010204466.tif 000002
【特許請求の範囲】
【請求項１】
体Kの代数曲面X(x,y,z)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置であって、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段と、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段と、
３つ以上の多項式の組ri(x,y,t),si(x,y,t)（i＝1,…,k）をランダムに生成する多項式生成手段と、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）を生成する暗号化手段と、
を備えたことを特徴とする暗号装置。
【請求項２】
請求項１に対応する暗号装置において、
前記平文埋め込み手段は、前記メッセージmを３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込むことを特徴とする暗号装置。
【請求項３】
請求項１又は請求項２に記載の暗号装置において、
前記多項式生成手段は、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式ri(x,y,t)（i＝1,…,k）を生成する第１の多項式生成手段と、
前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式si(x,y,t)（i＝1,…,k）を生成する第２の多項式生成手段と、
を備えたことを特徴とする暗号装置。
【請求項４】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置であって、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段と、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段と、
２つの多項式の組r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をランダムに生成する多項式生成手段と、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により、１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)を生成する第１の暗号文生成手段と、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により、１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)を生成する第２の暗号文生成手段と、
を備えたことを特徴とする暗号装置。
【請求項５】
請求項４に対応する暗号装置において、
前記平文埋め込み手段は、前記メッセージmを３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込むことを特徴とする暗号装置。
【請求項６】
請求項４又は請求項５に記載の暗号装置において、
前記多項式生成手段は、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式ri(x,y,t)（i＝1,2）を生成する第１の多項式生成手段と、
前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式si(x,y,t)（i＝1,2）を生成する第２の多項式生成手段と、
を備えたことを特徴とする暗号装置。
【請求項７】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置であって、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段と、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段と、
３つ以上の多項式の組ri(x,y,t),si(x,y,t)（i＝1,…,k）をランダムに生成する多項式生成手段と、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、少なくとも１つの暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）を生成する第１の暗号文生成手段と、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、２つ以上の暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）を生成する第２の暗号文生成手段と、
を備えたことを特徴とする暗号装置。
【請求項８】
請求項７に対応する暗号装置において、
前記平文埋め込み手段は、前記メッセージmを３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込むことを特徴とする暗号装置。
【請求項９】
請求項７又は請求項８に記載の暗号装置において、
前記多項式生成手段は、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式ri(x,y,t)（i＝1,…,k）を生成する第１の多項式生成手段と、
前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式si(x,y,t)（i＝1,…,k）を生成する第２の多項式生成手段と、
を備えたことを特徴とする暗号装置。
【請求項１０】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）が入力されたとき、前記セクションに基づいて、当該暗号文Fi(x,y,t)（i＝1,…,k）から前記メッセージmを復号するための復号装置であって、
前記入力された暗号文Fi(x,y,t)（i＝1,…,k）のそれぞれに対し、前記セクションを代入して３つ以上の１変数多項式hi(t)（i＝1,…,k）を生成するセクション代入手段と、
前記各１変数多項式hi(t)（i＝1,…,k）の中の２組の相異なる多項式を互いに減算し、減算結果としての複数の多項式gj(t)（j＝1,…,L）を得る多項式減算手段と、
前記各多項式のgj(t)（j＝1,…,L）のうちの２つ以上の多項式の最大公約式φ(t)を求める最大公約式演算手段と、
前記最大公約式φ(t)を因数分解する因数分解手段と、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段と、
前記１変数多項式hi(t)（i＝1,…,k）のうち、少なくとも１つの１変数多項式hi(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段と、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段と、
前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段と、
前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項１１】
請求項１０に記載の復号装置において、
前記メッセージmは３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込まれており、
前記平文候補生成手段は、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する第１の候補生成手段と、
前記識別多項式候補f(ux(t),uy(t),t)と、前記識別多項式f(x,y,t)の予め公開されたフレームとに基づいて当該識別多項式f(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する第２の候補生成手段と
を備えたことを特徴とする復号装置。
【請求項１２】
請求項１０又は請求項１１に記載の復号装置において、
前記３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）に代えて、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された少なくとも１つの暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）と、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された１つ以上の暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）とからなる２つ以上の暗号文Fi(x,y,t)（i＝1,…,k）が入力された場合に関し、
前記平文多項式m(x,y,t)を用いずに生成された暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）に前記セクションＤを代入して生成された前記１変数多項式hi(t)（i＝1,…,k）については前記減算を実行しないように前記多項式演算手段を制御することにより、当該１変数多項式hi(t)（i＝1,…,k）を前記多項式gj(t)(j＝1,…,L)として得る手段と、
を備えたことを特徴とする復号装置。
【請求項１３】
請求項１０乃至請求項１２のいずれか１項に記載の復号装置において、
前記最大公約式演算手段により求められた最大公約式φ(t)の次数deg φ(t)と、識別多項式f(ux(t),uy(t),t)の次数deg f(ux(t),uy(t),t)とを比較する手段と、
この比較の結果、両者が一致したとき、前記因数分解手段及び多項式抽出手段を実行せず、前記最大公約式φ(t)を前記識別多項式候補f(ux(t),uy(t),t)として前記除算を実行するように前記剰余演算手段を制御する手段と、
を備えたことを特徴とする復号装置。
【請求項１４】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)とからなる２つの暗号文F1(x,y,t),F2(x,y,t)が入力されたとき、前記セクションに基づいて、当該暗号文F1(x,y,t),F2(x,y,t),から前記メッセージmを復号するための復号装置であって、
前記入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記セクションを代入して２つの１変数多項式h1(t),h2(t)を生成するセクション代入手段と、
前記各１変数多項式h1(t),h2(t)のうち、暗号文F2(x,y,t)から生成された１変数多項式h2(t)を因数分解する因数分解手段と、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段と、
前記１変数多項式h1(t),h2(t)のうち、暗号文F1(x,y,t)から生成された１変数多項式h1(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段と、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段と、
前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段と、
前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項１５】
請求項１４に記載の復号装置において、
前記メッセージmは３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込まれており、
前記平文候補生成手段は、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する第１の候補生成手段と、
前記識別多項式候補f(ux(t),uy(t),t)と、前記識別多項式f(x,y,t)の予め公開されたフレームとに基づいて当該識別多項式f(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する第２の候補生成手段と
を備えたことを特徴とする復号装置。
【請求項１６】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応するｎ個のセクションDl（l＝1,…,n）を秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）が入力されたとき、前記ｎ個のセクションDl（l＝1,…,n）に基づいて、当該暗号文Fi(x,y,t)（i＝1,…,k）から前記メッセージmを復号するための復号装置であって、
前記入力された暗号文Fi(x,y,t)（i＝1,…,k）のそれぞれに対し、前記各セクションDl（l＝1,…,n）を代入してそれぞれｋ個の１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}を生成するセクション代入手段と、
前記各１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}に関し、同じセクションを代入した１変数多項式それぞれを互いに減算した減算結果{h1l(t)−h2l(t)},…,{h(k-1}l(t)−hkl(t)}のうちの２つ以上の多項式の最大公約式φl(t)を求める最大公約式演算手段と、
前記最大公約式φl(t)を因数分解する因数分解手段と、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(uxl(t),uyl(t),t)を次数に持つ全ての識別多項式候補f(uxl(t),uyl(t),t)を抽出する多項式抽出手段と、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ前記識別多項式候補f(uxl(t),uyl(t),t)で除算し、剰余としてｎ個の平文多項式候補m(uxl(t),uyl(t),t)を得る剰余演算手段と、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する平文候補生成手段と、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(uxl(t),uyl(t),t)から得られたｎ個の平文候補Mlにおいて共通した平文候補Mがあるか否かを判定する共通候補判定手段と、
前記判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項１７】
請求項１６に記載の復号装置において、
前記メッセージmは３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込まれており、
前記平文候補生成手段は、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する第１の候補生成手段と、
前記識別多項式候補f(uxl(t),uyl(t),t)と、前記識別多項式f(x,y,t)の予め公開されたフレームとに基づいて当該識別多項式f(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Ml’を生成する第２の候補生成手段とを備えており、
前記共通候補判定手段は、
前記第１及び第２の候補生成手段により得られた各々の平文候補Ml, Ml’に共通した平文候補Mがあるか否かを判定することを特徴とする復号装置。
【請求項１８】
請求項１６又は請求項１７に記載の復号装置において、
前記３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）に代えて、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された少なくとも１つの暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）と、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された１つ以上の暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）とからなる２つ以上の暗号文Fi(x,y,t)（i＝1,…,k）が入力された場合に関し、
前記平文多項式m(x,y,t)を用いずに生成された暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）に前記各セクションDl（l＝1,…,n）を代入して生成された前記１変数多項式{hi1(t),hi2(t),…,hin(t)}については前記減算を実行しないように前記多項式演算手段を制御することにより、前記最大公約式φl(t)を求める最大公約式演算手段と、
を備えたことを特徴とする復号装置。
【請求項１９】
請求項１６乃至請求項１８のいずれか１項に記載の復号装置において、
前記最大公約式演算手段により求められた最大公約式φl(t)の次数deg φl(t)と、識別多項式f(uxl(t),uyl(t),t)の次数deg f(uxl(t),uyl(t),t)とを比較する手段と、
この比較の結果、両者が一致したとき、前記因数分解手段及び多項式抽出手段を実行せず、前記最大公約式φl(t)を前記識別多項式候補f(uxl(t),uyl(t),t)として前記除算を実行するように前記剰余演算手段を制御する手段と、
を備えたことを特徴とする復号装置。
【請求項２０】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応するｎ個のセクションDl（l＝1,…,n）を秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)とからなる２つの暗号文F1(x,y,t),F2(x,y,t)が入力されたとき、前記ｎ個のセクションDl（l＝1,…,n）に基づいて、当該暗号文F1(x,y,t),F2(x,y,t)から前記メッセージmを復号するための復号装置であって、
前記入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記各セクションDl（l＝1,…,n）を代入してそれぞれ２つの１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}を生成するセクション代入手段と、
前記各１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}のうち、暗号文F2(x,y,t)から生成された１変数多項式h21(t),…,h2n(t)を因数分解する因数分解手段と、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(uxl(t),uyl(t),t)を次数に持つ全ての識別多項式候補f(uxl(t),uyl(t),t)を抽出する多項式抽出手段と、
前記１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}のうち、暗号文F1(x,y,t)から生成された１変数多項式h11(t),…,h1n(t)を前記識別多項式候補f(uxl(t),uyl(t),t)で除算し、剰余として平文多項式候補m(uxl(t),uyl(t),t)を得る剰余演算手段と、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する平文候補生成手段と、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(uxl(t),uyl(t),t)から得られたｎ個の平文候補Mlにおいて共通した平文候補Mがあるか否かを判定する共通候補判定手段と、
前記判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項２１】
請求項２０に記載の復号装置において、
前記メッセージmは３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込まれており、
前記平文候補生成手段は、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する第１の候補生成手段と、
前記識別多項式候補f(uxl(t),uyl(t),t)と、前記識別多項式f(x,y,t)の予め公開されたフレームとに基づいて当該識別多項式f(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Ml’を生成する第２の候補生成手段と
を備えたことを特徴とする復号装置。
【請求項２２】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式に関し、前記公開鍵であるファイブレーションX(x,y,t)と、前記秘密鍵であるセクションとを生成するための鍵生成装置であって、
前記ファイブレーションX(x,y,t)の定数項以外の項の次数degt X’及び前記ファイブレーションX(x,y,t)の２変数x,yの係数集合ΛXを入力する手段と、
前記セクションをランダムに生成するセクション生成手段と、
前記生成されたセクション及び前記入力された次数degt X’及び係数集合ΛXに基づいて、前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段と、
前記定数項以外の項に前記セクションを代入して得られる代入結果に負の符号を付すことにより前記定数項を計算する定数項計算手段と、
前記定数項以外の項の次数degt X’及び前記定数項の次数degt a00のうち、いずれか大きい方の次数をファイブレーションの次数degt Xに決定し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段と、
前記ファイブレーションの次数degt X及び係数集合ΛXに基づき、条件“degt X ＜ degt m ＜ degt f”及び“（degx f，degy f）∈Λf”の範囲で、識別多項式の次数degt f及び２変数x,yの係数集合Λfをランダムに生成する手段（但し、degt mは平文多項式の変数ｔの次数、degt fは識別多項式の変数ｔの次数、degx fは識別多項式の変数ｘの次数、degy fは識別多項式の変数ｙの次数）と、
前記係数集合Λf，ΛXの積ΛfΛXを計算し、この計算結果の部分集合で且つ条件“（degx m，degy m，degt m）∈Γm”の範囲で、平文多項式の２変数x,yの係数集合Λmを決定する手段（但し、Γmは、平文多項式m(x,y,t)に含まれる非零の単項式の（x指数，y指数，t指数）の集合）と、
前記平文多項式の次数degt mを、条件“degt X ＜degt m ＜ degt f”の範囲で決定する手段と、
前記係数集合Λfに含まれる各要素(i,j)に基づき、要素(i,j)＝(degx f, degy f）の場合にはdeg fij(t)＝degt fとして前記識別多項式の係数の次数fij(t)を決定し、要素(i,j)≠(degx f, degy f）の場合には０≦deg fij(t)≦degt fの範囲でランダムに前記次数fij(t)を決定することにより、前記係数集合Λf及び前記次数fij(t)からなる識別多項式のフレームＦRfを決定する手段と、
前記代数曲面から係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出し、この係数集合ΛX及び係数の次数deg aij(t)から代数曲面のフレームＦRXを生成する手段と、
前記各フレームＦRf，ＦRXを互いに積算してフレームＦRg（＝ＦRf ＦRX）を生成する手段と、
前記平文多項式の係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij(t)}に決定する手段と、
前記係数集合Λm及び次数deg mij(t)からなるフレームであって、係数mijkを変数とした平文多項式のフレームに対し、前記セクションを代入するセクション代入手段と、
前記代入した結果得られる変数mijkを順序付けして変数ベクトル(m000,m001,…,mijk,…)を生成する手段と、
前記代入した結果得られる１変数多項式m(ux(t),uy(t),t)をtに関して整理し、tの係数mijkux(t)iuy(t)jとなる多項式を抽出する係数抽出手段と、
前記変数ベクトル(m000,m001,…,mijk,…)との積が丁度前記tの係数mijkux(t)iuy(t)jとなるように係数行列を生成する係数行列生成手段と、
前記係数行列の階数を計算する係数行列計算手段と、
前記階数が前記変数ベクトルの次元数と一致しない場合に、前記１変数多項式m(ux(t),uy(t),t)の一部の変数mijkを定数にする変数調整手段と、
前記階数が前記変数ベクトルの次元数と一致する場合の１変数多項式m(ux(t),uy(t),t)に対応する３変数多項式m(x,y,t)のフレームを平文多項式のフレームＦRmとして出力する出力手段、
を備えたことを特徴とする鍵生成装置。
【請求項２３】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置に用いられるプログラムであって、
前記暗号装置を、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段、
前記係数が埋め込まれた平文多項式m(x,y,t)を前記暗号装置のメモリに書き込む手段、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段、
３つ以上の多項式の組ri(x,y,t),si(x,y,t)（i＝1,…,k）をランダムに生成する多項式生成手段、
前記メモリ内の平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）を生成する暗号化手段、
として機能させるためのプログラム。
【請求項２４】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置に用いられるプログラムであって、
前記暗号装置を、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段、
前記係数が埋め込まれた平文多項式m(x,y,t)を前記暗号装置のメモリに書き込む手段、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段、
２つの多項式の組r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をランダムに生成する多項式生成手段、
前記メモリ内の平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により、１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)を生成する第１の暗号文生成手段、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により、１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)を生成する第２の暗号文生成手段、
として機能させるためのプログラム。
【請求項２５】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置に用いられるプログラムであって、
前記暗号装置を、
前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段、
３つ以上の多項式の組ri(x,y,t),si(x,y,t)（i＝1,…,k）をランダムに生成する多項式生成手段、
前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、少なくとも１つの暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）を生成する第１の暗号文生成手段、
前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、２つ以上の暗号文Fi(x,y,t)＝E(si,ri,f,X)（i＝1,…,k）を生成する第２の暗号文生成手段、
として機能させるためのプログラム。
【請求項２６】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）が入力されたとき、前記セクションに基づいて、当該暗号文Fi(x,y,t)（i＝1,…,k）から前記メッセージmを復号するための復号装置に用いられるプログラムであって、
前記復号装置を、
前記入力された暗号文Fi(x,y,t)（i＝1,…,k）を前記復号装置のメモリに書き込む手段、
前記メモリ内の暗号文Fi(x,y,t)（i＝1,…,k）のそれぞれに対し、前記セクションを代入して３つ以上の１変数多項式hi(t)（i＝1,…,k）を生成するセクション代入手段、
前記各１変数多項式hi(t)（i＝1,…,k）の中の２組の相異なる多項式を互いに減算し、減算結果としての複数の多項式gj(t)（j＝1,…,L）を得る多項式減算手段、
前記各多項式のgj(t)（j＝1,…,L）のうちの２つ以上の多項式の最大公約式φ(t)を求める最大公約式演算手段、
前記最大公約式φ(t)を因数分解する因数分解手段、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段、
前記１変数多項式h1(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段、
前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段、
前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段、
として機能させるためのプログラム。
【請求項２７】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)とからなる２つの暗号文F1(x,y,t),F2(x,y,t)が入力されたとき、前記セクションに基づいて、当該暗号文F1(x,y,t),F2(x,y,t)から前記メッセージmを復号するための復号装置に用いられるプログラムであって、
前記復号装置を、
前記入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記セクションを代入して２つの１変数多項式h1(t),h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t),h2(t)のうち、暗号文F2(x,y,t)から生成された１変数多項式h2(t)を因数分解する因数分解手段、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段、
前記１変数多項式h1(t),h2(t)のうち、暗号文F1(x,y,t)から生成された１変数多項式h1(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段、
前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段、
前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段、
前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段、
として機能させるためのプログラム。
【請求項２８】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応するｎ個のセクションD1,…,Dnを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）が入力されたとき、前記ｎ個のセクションD1,…,Dnに基づいて、当該暗号文Fi(x,y,t)（i＝1,…,k）から前記メッセージmを復号するための復号装置に用いられるプログラムであって、
前記復号装置を、
前記入力された暗号文Fi(x,y,t)（i＝1,…,k）を前記復号装置のメモリに書き込む手段、
前記メモリ内の暗号文Fi(x,y,t)（i＝1,…,k）のそれぞれに対し、前記各セクションD1,…,Dnを代入してそれぞれｋ個の１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}を生成するセクション代入手段、
前記各１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}に関し、同じセクションを代入した１変数多項式それぞれを互いに減算した減算結果{h1l(t)−h21(t)},…,{h(k-1)l(t)−hkl(t),…}のうちの２つ以上の多項式の最大公約式φl(t)を求める最大公約式演算手段、
前記最大公約式φl(t)を因数分解する因数分解手段、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(uxl(t),uyl(t),t)を次数に持つ全ての識別多項式候補f(uxl(t),uyl(t),t)を抽出する多項式抽出手段、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ前記識別多項式候補f(uxl(t),uyl(t),t)で除算し、剰余としてｎ個の平文多項式候補m(uxl(t),uyl(t),t)を得る剰余演算手段、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する平文候補生成手段、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(ux(t),uy(t),t)から得られたｎ個の平文候補Mlにおいて共通した平文候補Mがあるか否かを判定する共通候補判定手段、
前記判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力する出力手段、
として機能させるためのプログラム。
【請求項２９】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応するｎ個のセクションD1,…,Dnを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)とからなる２つの暗号文F1(x,y,t),F2(x,y,t)が入力されたとき、前記ｎ個のセクションD1,…,Dnに基づいて、当該暗号文F1(x,y,t),F2(x,y,t)から前記メッセージmを復号するための復号装置に用いられるプログラムであって、
前記復号装置を、
前記入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記各セクションD1,…,Dnを代入してそれぞれ２つの１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}を生成するセクション代入手段、
前記各１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}のうち、暗号文F2(x,y,t)から生成された１変数多項式h21(t),…,h2n(t)を因数分解する因数分解手段、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(uxl(t),uyl(t),t)を次数に持つ全ての識別多項式候補f(uxl(t),uyl(t),t)を抽出する多項式抽出手段、
前記１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}のうち、暗号文F1(x,y,t)から生成された１変数多項式h11(t),…,h1n(t)を前記識別多項式候補f(uxl(t),uyl(t),t)で除算し、剰余として平文多項式候補m(uxl(t),uyl(t),t)を得る剰余演算手段、
前記平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mlを生成する平文候補生成手段、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(uxl(t),uyl(t),t)から得られたｎ個の平文候補Mlにおいて共通した平文候補Mがあるか否かを判定する共通候補判定手段、
前記判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力する出力手段、
として機能させるためのプログラム。
【請求項３０】
体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式に関し、前記公開鍵であるファイブレーションX(x,y,t)と、前記秘密鍵であるセクションとを生成するための鍵生成装置に用いられるプログラムであって、
前記鍵生成装置を、
前記ファイブレーションX(x,y,t)の定数項以外の項の次数degt X’及び前記ファイブレーションX(x,y,t)の２変数x,yの係数集合ΛXを入力する手段、
素数pとセクションの最大次数dとを格納する格納手段、
前記格納手段内の素数pと最大次数dとに基づいて、素体Fp上の次数dの１変数多項式ux(t),uy(t)を生成し、当該１変数多項式ux(t),uy(t)から前記セクション(ux(t),uy(t),t)を生成するセクション生成手段、
前記生成されたセクション及び前記入力された次数degt X’及び係数集合ΛXに基づいて、前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段、
前記定数項以外の項の次数degt X’及び前記定数項の次数degt a00のうち、いずれか大きい方の次数をファイブレーションの次数degt Xに決定し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段、
前記ファイブレーションの次数degt X及び係数集合ΛXに基づき、条件“degt X ＜ degt m ＜ degt f”及び“（degx f，degy f）∈Λf”の範囲で、識別多項式の次数degt f及び２変数x,yの係数集合Λfをランダムに生成する手段（但し、degt mは平文多項式の変数ｔの次数、degt fは識別多項式の変数ｔの次数、degx fは識別多項式の変数ｘの次数、degy fは識別多項式の変数ｙの次数）、
前記係数集合Λf，ΛXの積ΛfΛXを計算し、この計算結果の部分集合で且つ条件“（degx m，degy m，degt m）∈Γm”の範囲で、平文多項式の２変数x,yの係数集合Λmを決定する手段（但し、Γmは、平文多項式m(x,y,t)に含まれる非零の単項式の（x指数，y指数，t指数）の集合）、
前記平文多項式の次数degt mを、条件“degt X ＜degt m ＜ degt f”の範囲で決定する手段、
前記係数集合Λfに含まれる各要素(i,j)に基づき、要素(i,j)＝(degx f, degy f）の場合にはdeg fij(t)＝degt fとして前記識別多項式の係数の次数fij(t)を決定し、要素(i,j)≠(degx f, degy f）の場合には０≦deg fij(t)≦degt fの範囲でランダムに前記次数fij(t)を決定することにより、前記係数集合Λf及び前記次数fij(t)からなる識別多項式のフレームＦRfを決定する手段、
前記代数曲面から係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出し、この係数集合ΛX及び係数の次数deg aij(t)から代数曲面のフレームＦRXを生成する手段、
前記各フレームＦRf，ＦRXを互いに積算してフレームＦRg（＝ＦRf ＦRX）を生成する手段、
前記平文多項式の係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij(t)}に決定する手段、
前記係数集合Λm及び次数deg mij(t)からなるフレームであって、係数mijkを変数とした平文多項式のフレームに対し、前記セクションを代入するセクション代入手段と、
前記代入した結果得られる変数mijkを順序付けして変数ベクトル(m000,m001,…,mijk,…)を生成する手段、
前記代入した結果得られる１変数多項式m(ux(t),uy(t),t)をtに関して整理し、tの係数mijkux(t)iuy(t)jとなる多項式を抽出する係数抽出手段、
前記変数ベクトル(m000,m001,…,mijk,…)との積が丁度前記tの係数mijkux(t)iuy(t)jとなるように係数行列を生成する係数行列生成手段、
前記係数行列の階数を計算する係数行列計算手段、
前記階数が前記変数ベクトルの次元数と一致しない場合に、前記１変数多項式m(ux(t),uy(t),t)の一部の変数mijkを定数にする変数調整手段、
前記階数が前記変数ベクトルの次元数と一致した場合の１変数多項式m(ux(t),uy(t),t)に対応する３変数多項式m(x,y,t)のフレームを平文多項式のフレームＦRmとして出力する出力手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号システムに用いられる暗号装置、復号装置、鍵生成装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワーク社会では、電子メール等の多くの情報がネットワーク上に伝送されることにより、人々のコミュニケーションが行われる。このようなネットワーク社会において、公開鍵暗号は情報の機密性や真正性を守る技術として広く活用されている。
【０００３】
代表的な公開鍵暗号としてはＲＳＡ暗号と楕円曲線暗号がある。これらの公開鍵暗号は、一般的な解読法が知られていないため、後述する量子計算機による解読法を除き、安全性に関する重大な問題が見つかっていない。他の公開鍵暗号としてはナップサック暗号と多次多変数暗号などがある。しかしながら、ナップサック暗号は有力な解読法があるため、安全性に疑問がある。多次多変数暗号は、鍵サイズの増大により、有力な攻撃方法を避けられる反面、鍵サイズが膨大になってしまう問題がある。
【０００４】
一方、ＲＳＡ暗号と楕円曲線暗号は量子計算機が出現すれば解読される可能性が高い。量子計算機は、現在の計算機とは異なり、量子力学におけるエンタングルメントという物理現象を利用して超並列計算を実行可能な計算機である。量子計算機は、実験レベルの仮想の計算機であるが、実現に向けて研究開発が進められている。１９９４年にショア(Shor)は、量子計算機によれば素因数分解や離散対数問題を効率的に解けることを示した。従って、量子計算機が実現すれば、素因数分解に基づくＲＳＡ暗号や、楕円曲線上の離散対数問題に基づく楕円曲線暗号は解読される可能性が高い。
【０００５】
他方、量子計算機が実現されても安全な公開鍵暗号が研究されてきている。一例として、量子公開鍵暗号が挙げられる。量子公開鍵暗号では、現在の計算機では鍵生成が不可能である程に強力なナップサック暗号の鍵を量子計算機により生成する。このため、量子公開鍵暗号では、量子計算機でも計算できない程に強力なナップサック暗号を構成し得る。しかしながら、量子公開鍵暗号は、現在の計算機では鍵生成が不可能であるため、現時点では利用できない。
【０００６】
一方、多次多変数暗号は、現時点でも実現可能であり、量子計算機でも解読が難しい。しかしながら、多次多変数暗号は、前述した通り、膨大な鍵サイズを要するため、実用化が疑問視されている。
【０００７】
更に、公開鍵暗号は、共通鍵暗号と比べ、回路規模が大きく、処理時間が長い。よって、モバイル端末などの小電力環境では実現できないか、実現しても待ち時間が長いという問題がある。このため、小電力環境でも実現できる公開鍵暗号が求められている。
【０００８】
一般に公開鍵暗号は、予め素因数分解問題や離散対数問題などの計算困難な問題を見出し、秘密鍵を知らずに暗号文の解読を試みる場合に当該計算困難な問題を解くことと同等になるように構成する。
【０００９】
しかし、計算困難な問題が見つかっても、その問題を安全性の根拠とする公開鍵暗号を容易に構成できる訳ではない。理由は、計算が困難すぎる問題を安全性の根拠にすると鍵を生成する問題も困難になるので、鍵を生成できないためである。一方、鍵生成が可能な程度に問題を容易にすると、解読も容易になってしまう。
【００１０】
従って、公開鍵暗号を構成するには、計算困難な問題を見つけるとともに、見つけた問題を、鍵生成が容易だが、解読が容易でないという絶妙なバランスを持つ問題に作り変える必要がある。このような問題の作り変えには高い創造性を必要とする。実際には、問題の作り変えが極めて困難なため、数えるほどの公開鍵暗号しか提案されていない。
【００１１】
このような状況において、量子計算機でも効率的に解読できない可能性があり、小電力環境でも高速に処理可能な公開鍵暗号として、代数曲面を用いた公開鍵暗号が提案されている（例えば、非特許文献１参照。）。
【００１２】
代数曲面を用いた公開鍵暗号は、秘密鍵を代数曲面X(x,y,t)に対応する２つのセクションとし、公開鍵を代数曲面X(x,y,t)とする時、平文mを平文多項式m(x,y,t)に埋め込む処理と、因子多項式f(x,y,t)を、ランダムに生成する処理と、３変数x,y,tのランダムな２つの多項式の組si(x,y,t)ri(x,y,t)(i=1,2)を生成する多項式生成処理と、各多項式の組si(x,y,t)ri(x,y,t)(i=1,2)と定義式X(x,y,t)とを加算又は減算する処理により、平文多項式m(x,y,t)から２つの暗号文Fi(x,y,t)＝E(m,si,ri,f,X)(i=1,2)を生成する暗号化処理を実行する。
【００１３】
更に、復号処理においては２つの暗号文F1(x,y,t), F2(x,y,t),に秘密鍵であるセクションＤ：(x,y,t)＝(ux(t),uy(t),t)を代入してそれぞれ１変数多項式h1(t),h2(t)を求めるとともに、これらを互いに減算した結果を因数分解して、その因数分解結果からdeg f(ux(t),uy(t),t)を次数に持つ因子を抽出する。この因子は一意に抽出されるとは限らないが、正しい因子多項式f(ux(t),uy(t),t)を抽出できた際には、１変数多項式h1(t),h2(t)のいずれかを因子多項式f(ux(t),uy(t),t)で割ることにより、剰余として正しい平文多項式候補m(ux(t),uy(t),t)が抽出され、正しい平文mが復元される。
【００１４】
一方、因子多項式f(ux(t),uy(t),t)でない因子が抽出された場合は、前述同様の演算により間違った平文m’が復元され、平文に予め埋め込まれた誤り検出符号などを使ってその誤りを見出すことができる。
【非特許文献１】K. Akiyama, Y. Goto, "An improvement of the algebraic surface public-key cryptosystem", Symposium on Cryptography and Information Security 2009,1F1-1(2009).
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかしながら、以上のような代数曲面を用いた公開鍵暗号は、通常は特に問題が無いが、本発明者の検討によれば、処理全体の効率化を実現することが求められている。
【００１６】
例えば、前述した復号処理においては処理時間の殆どが、因数分解処理と、因数分解結果からdeg f(ux(t),uy(t),t)を次数に持つ因子を抽出する因子抽出処理に掛かる。特に因子抽出処理は因数分解結果により、組み合わせが多大となる場合があり、復号処理時間に大きな違いが生じる。このため、代数曲面を用いた公開鍵暗号は、復号処理の処理時間の殆どを占める因数分解処理と因数抽出処理の負荷を低減し、処理全体の効率化を実現することが求められている。
【００１７】
また、前述した暗号化処理においては、２つの暗号文を作成するための演算処理が４回の乗算と４回の加算によって構成される。また、復号処理においては、セクション代入後の多項式h1(t),h2(t)を互いに減算し、減算結果を因数分解する処理が必須となっている。ここで、暗号化処理又は復号処理のうち、少なくとも一方の演算処理の負荷を低減することが望ましい。
【００１８】
このように本発明者の検討によれば、代数曲面を用いた公開鍵暗号において、このような暗号化処理又は復号処理における演算処理の負荷を低減することにより、処理全体の効率化を実現することが求められている。
【００１９】
本発明は上記実情を考慮してなされたもので、代数曲面を用いた公開鍵暗号において、暗号化処理又は復号処理における演算処理の負荷を低減することにより、処理全体の効率化を実現し得る暗号装置、復号装置、鍵生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の第１の局面は、体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置であって、前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段と、前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段と、３つ以上の多項式の組ri(x,y,t),si(x,y,t)（i＝1,…,k）をランダムに生成する多項式生成手段と、前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式si(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により、３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）を生成する暗号化手段と、を備えた暗号装置である。
【００２１】
本発明の第２の局面は、体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)si(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式ri(x,y,t)の乗算結果X(x,y,t)ri(x,y,t)とを加算又は減算する処理により生成された３つ以上の暗号文Fi(x,y,t)＝E(m,si,ri,f,X)（i＝1,…,k）が入力されたとき、前記セクションに基づいて、当該暗号文Fi(x,y,t)（i＝1,…,k）から前記メッセージmを復号するための復号装置であって、前記入力された暗号文Fi(x,y,t)（i＝1,…,k）のそれぞれに対し、前記セクションを代入して３つ以上の１変数多項式hi(t)（i＝1,…,k）を生成するセクション代入手段と、前記各１変数多項式hi(t)（i＝1,…,k）の中の２組の相異なる多項式を互いに減算し、減算結果としての複数の多項式gj(t)（j＝1,…,L）を得る多項式減算手段と、前記各多項式のgj(t)（j＝1,…,L）のうちの２つ以上の多項式の最大公約式φ(t)を求める最大公約式演算手段と、前記最大公約式φ(t)を因数分解する因数分解手段と、前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段と、前記１変数多項式hi(t)（i＝1,…,k）のうち、少なくとも１つの１変数多項式hi(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段と、前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段と、前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段と、前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段と、を備えた復号装置である。
【００２２】
本発明の第３の局面は、体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式に関し、前記公開鍵であるファイブレーションX(x,y,t)と、前記秘密鍵であるセクションとを生成するための鍵生成装置であって、前記ファイブレーションX(x,y,t)の定数項以外の項の次数degt X’及び前記ファイブレーションX(x,y,t)の２変数x,yの係数集合ΛXを入力する手段と、前記セクションをランダムに生成するセクション生成手段と、前記生成されたセクション及び前記入力された次数degt X’及び係数集合ΛXに基づいて、前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段と、前記定数項以外の項に前記セクションを代入して得られる代入結果に負の符号を付すことにより前記定数項を計算する定数項計算手段と、前記定数項以外の項の次数degt X’及び前記定数項の次数degt a00のうち、いずれか大きい方の次数をファイブレーションの次数degt Xに決定し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段と、前記ファイブレーションの次数degt X及び係数集合ΛXに基づき、条件“degt X ＜ degt m ＜ degt f”及び“（degx f，degy f）∈Λf”の範囲で、識別多項式の次数degt f及び２変数x,yの係数集合Λfをランダムに生成する手段（但し、degt mは平文多項式の変数ｔの次数、degt fは識別多項式の変数ｔの次数、degx fは識別多項式の変数ｘの次数、degy fは識別多項式の変数ｙの次数）と、前記係数集合Λf，ΛXの積ΛfΛXを計算し、この計算結果の部分集合で且つ条件“（degx m，degy m，degt m）∈Γm”の範囲で、平文多項式の２変数x,yの係数集合Λmを決定する手段（但し、Γmは、平文多項式m(x,y,t)に含まれる非零の単項式の（x指数，y指数，t指数）の集合）と、前記平文多項式の次数degt mを、条件“degt X ＜degt m ＜ degt f”の範囲で決定する手段と、前記係数集合Λfに含まれる各要素(i,j)に基づき、要素(i,j)＝(degx f, degy f）の場合にはdeg fij(t)＝degt fとして前記識別多項式の係数の次数fij(t)を決定し、要素(i,j)≠(degx f, degy f）の場合には０≦deg fij(t)≦degt fの範囲でランダムに前記次数fij(t)を決定することにより、前記係数集合Λf及び前記次数fij(t)からなる識別多項式のフレームＦRfを決定する手段と、前記代数曲面から係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出し、この係数集合ΛX及び係数の次数deg aij(t)から代数曲面のフレームＦRXを生成する手段と、前記各フレームＦRf，ＦRXを互いに積算してフレームＦRg（＝ＦRf ＦRX）を生成する手段と、前記平文多項式の係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij(t)}に決定する手段と、前記係数集合Λm及び次数deg mij(t)からなるフレームであって、係数mijkを変数とした平文多項式のフレームに対し、前記セクションを代入するセクション代入手段と、前記代入した結果得られる変数mijkを順序付けして変数ベクトル(m000,m001,…,mijk,…)を生成する手段と、前記代入した結果得られる１変数多項式m(ux(t),uy(t),t)をtに関して整理し、tの係数mijkux(t)iuy(t)jとなる多項式を抽出する係数抽出手段と、前記変数ベクトル(m000,m001,…,mijk,…)との積が丁度前記tの係数mijkux(t)iuy(t)jとなるように係数行列を生成する係数行列生成手段と、前記係数行列の階数を計算する係数行列計算手段と、前記階数が前記変数ベクトルの次元数と一致しない場合に、前記１変数多項式m(ux(t),uy(t),t)の一部の変数mijkを定数にする変数調整手段と、前記階数が前記変数ベクトルの次元数と一致した場合の１変数多項式m(ux(t),uy(t),t)に対応する３変数多項式m(x,y,t)のフレームを平文多項式のフレームＦRmとして出力する出力手段と、を備えた鍵生成装置である。
【００２３】
本発明の第４の局面は、体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式を用い、前記公開鍵であるファイブレーションX(x,y,t)に基づいて、メッセージmを暗号化するための暗号装置であって、前記メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み手段と、前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段と、２つの多項式の組r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をランダムに生成する多項式生成手段と、前記平文多項式m(x,y,t)に対し、前記識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により、１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)を生成する第１の暗号文生成手段と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により、１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)を生成する第２の暗号文生成手段と、を備えた暗号装置である。
【００２４】
本発明の第５の局面は、体Kの代数曲面X(x,y,t)＝0のうち、x,yがtでパラメタライズされた曲線(x,y,t)＝(ux(t),uy(t),t)であるセクションが存在する代数曲面XであるファイブレーションX(x,y,t)＝0を公開鍵とし、前記ファイブレーションX(x,y,t)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージmが係数として埋め込まれた３変数の平文多項式m(x,y,t)に対し、３変数の識別多項式f(x,y,t)及び多項式s1(x,y,t)の乗算結果f(x,y,t)s1(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r1(x,y,t)の乗算結果X(x,y,t)r1(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F1(x,y,t)＝E(m,s1,r1,f,X)と、前記平文多項式m(x,y,t)を用いずに、前記識別多項式f(x,y,t)及び多項式s2(x,y,t)の乗算結果f(x,y,t)s2(x,y,t)と、前記ファイブレーションX(x,y,t)及び多項式r2(x,y,t)の乗算結果X(x,y,t)r2(x,y,t)とを加算又は減算する処理により生成された１つの暗号文F2(x,y,t)＝E(s2,r2,f,X)とからなる２つの暗号文F1(x,y,t),F2(x,y,t)が入力されたとき、前記セクションに基づいて、当該暗号文F1(x,y,t),F2(x,y,t),から前記メッセージmを復号するための復号装置であって、前記入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記セクションを代入して２つの１変数多項式h1(t),h2(t)を生成するセクション代入手段と、前記各１変数多項式h1(t),h2(t)のうち、暗号文F2(x,y,t)から生成された１変数多項式h2(t)を因数分解する因数分解手段と、前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段と、前記１変数多項式h1(t),h2(t)のうち、暗号文F1(x,y,t)から生成された１変数多項式h1(t)を前記識別多項式候補f(ux(t),uy(t),t)で除算し、剰余として平文多項式候補m(ux(t),uy(t),t)を得る剰余演算手段と、前記平文多項式候補m(ux(t),uy(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導き、この連立１次方程式を解くことにより平文候補Mを生成する平文候補生成手段と、前記平文候補Mに含まれる誤り検出符号により真の平文であるか否かを検査する平文多項式検査手段と、前記検査の結果、真の平文である平文候補Mがあった場合に当該平文候補Mを平文として出力する出力手段と、を備えた復号装置である。
【００２５】
なお、第１乃至第５の各局面は、装置として表現したが、装置に限らず、方法、プログラム、プログラムを記憶したコンピュータ読取り可能な記憶媒体として表現してもよい。
【００２６】
（作用）
第１乃至第３の局面においては、高い次数の多項式｛h1(t)−h2(t)｝を因数分解して因数を抽出した従来とは異なり、高い次数の多項式hi(t)から低い次数の最大公約式φ(t)を求め、低い次数の最大公約式φ(t)を因数分解して因数を抽出するための暗号装置、復号装置及び鍵生成装置を実現させている。
【００２７】
従って、第１乃至第３の局面によれば、代数曲面を用いた公開鍵暗号方式において、低い次数の最大公約式φ(t)を用いて因数分解処理と因数抽出処理の負荷を低減することにより、復号処理における演算処理の負荷を低減でき、処理全体の効率化を実現することができる。
【００２８】
第４の局面においては、代数曲面を用いた公開鍵暗号方式において、従来とは異なり、平文多項式m(x,y,t)を用いずに第２の暗号文F2(x,y,t)を生成することから、平文多項式m(x,y,t)に対する加算又は減算処理を１回省略できるので、暗号処理における演算処理の負荷を低減でき、もって、処理全体の効率化を実現することができる。
【００２９】
第５の局面によれば、代数曲面を用いた公開鍵暗号方式において、従来とは異なり、平文多項式m(x,y,t)を用いない第２の暗号文F2(x,y,t)から生成した多項式h2(t)を因数分解することから、従来の平文多項式m(ux(t),uy(t),t)をキャンセルするための減算処理｛h1(t)−h2(t)｝を省略して因数分解を実行できるので、復号処理における演算処理の負荷を低減でき、もって、処理全体の効率化を実現することができる。
【発明の効果】
【００３０】
以上説明したように本発明によれば、代数曲面を用いた公開鍵暗号において、因数分解処理と因数抽出処理の負荷を低減することにより、復号処理の効率化を実現できる。
【発明を実施するための最良の形態】
【００３１】
以下、本発明の各実施形態について図面を用いて説明する。
【００３２】
各実施形態における代数曲面は体K上定義された連立(代数)方程式の解の集合のうち２次元の自由度を持ったものと定義される。例えば、次の式(1)に示す体K上の連立方程式は５つの変数を束縛する３つの方程式があることから、２次元の自由度を持っているので、代数曲面となる。
【数１】
2010204466.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が与えられたとき、セクションを求める問題に安全性の根拠をおく。
【００４７】
ファイブレーションからセクションを求めるには現代の数学においても次の(i)から(iv)の手順による方法しか知られていない。
【００４８】
(i) セクション(ux(t),uy(t),t)を
deg ux(t) ＜ rx,deg uy(t) ＜ ry
と仮定した上で、ux(t)，uy(t)を次式のようにおく。
【数２】
2010204466.tif 000004
【００４９】
(iv) 連立方程式系を解く。
【００５０】
次に、代数曲面上の求セクション問題に基づく各実施形態の公開鍵暗号を具体的に説明する。
【００５１】
（各実施形態の公開鍵暗号）
（用語の定義）
始めに、用語を定義する。３変数多項式ξ(x,y,t)の変数xに関する次数をdegX ξ(x,y,t)、変数yに関する次数をdegyξ(x,y,t)、変数tに関する次数をdegtξ(x,y,t)と表す。
【００５２】
３変数多項式ξ(x,y,t)を表現するとき
【数３】
2010204466.tif 000005
【００５３】
の２通りの表現方法を用いる。ここで、Γξは多項式ξ(x,y,t)に含まれる非零の単項式の（x指数，y指数，t指数）の集合と定義され、ξの（３変数）係数集合と呼ぶ。Λξは多項式ξ(x,y,t)をx,yの多項式としてみた時の非零の項の（x指数，y指数）の集合と定義され、ξの（２変数）係数集合と呼ぶ。
【００５４】
また、（２変数）係数集合Λξと（２変数）係数集合Ληの積ΛξΛηは、
ΛξΛη＝｛(i1＋i2, j1＋j2)｜(i1, j1)∈Λξ，(i2, j2)∈Λη｝
と定義され、３変数多項式ξ(x,y,t)η(x,y,t)の（２変数）係数集合を意味する。（３変数）係数集合の積集合も同様に定義される。
【００５５】
３変数多項式ξ(x,y,t)のフレームＦRξとは、
【数４】
2010204466.tif 000006
【００５６】
において、（２変数）係数集合Λξと係数集合Λξの各要素(i,j)に対応する係数ξij(t)の最大次数degξij(t)のみが定まっているものを言う。また、フレームＦRξとフレームＦRηの積ＦRξＦRηは以下のように定義される。
【数５】
2010204466.tif 000007
【００５７】
において、
Λψ＝ΛξΛη 
(i,j)∈Λψ ⇒ degψij(t)＝degξij(t)＋degηij(t) 
（第１の実施形態の概要）
本実施形態の公開鍵暗号は、以下の２つのシステムパラメータp,dを持っている。
【００５８】
1. 有限体のサイズ:p
2. （秘密鍵である）セクションの最高次数:d＝max{deg ux(t),deg uy(t)} (3)
また、公開鍵は、以下の３つである。
【数６】
2010204466.tif 000008
【００５９】
秘密鍵は、以下のセクションＤである。
【００６０】
1. Fp 上の代数曲面Xのセクション: Ｄ: (x,y,t)＝(ux(t),uy(t),t)
但し、平文多項式、識別多項式それぞれのフレームは、
【数７】
2010204466.tif 000009
【００６１】
と条件(5)を満たすように定める。
【００６２】
Λm⊂ΛfΛX                 (5)
これらは期待される安全性を実現するための条件である。また、復号のための条件
deg m(ux(t),uy(t),t) ＜ deg f(ux(t),uy(t),t)        (6)
は、条件(4)を満たせば次数の関係から、あらゆるセクションに対して必然的に満たされることが分かる。
【００６３】
これらのパラメータは後述する方法（鍵生成方法）で容易に求めることができる。
【００６４】
暗号化処理の概要を述べる。暗号化処理ではまず暗号化したいメッセージ（以下では平文と呼ぶ）をブロック分割してm＝m00‖m10‖…‖mijとする。なお、‖は連接を表す。ここで、L＝deg mij(t)としたとき、
｜mij｜≦（｜p｜−１）（L＋１）とし、mij(t)のtkの係数mijkは上記mijを｜p｜−１ビット毎に分割したものとする。即ち、
mij＝mij0‖mij1‖…‖mijL 
ここで｜p｜はpのビット長を表している。このようにして平文を次式に示す如き平文多項式m(x,y,t)に埋め込む。
【数８】
2010204466.tif 000010
【００６５】
尚、各実施形態のメッセージには誤り検出符号が含まれているとしている。誤り検出符号は送信上に生じたノイズなどの影響でメッセージの一部が毀損したときにそれを検出する機能を持つ。誤り検出符号として特にハッシュ関数によるハッシュ値を取ってもよい。
【００６６】
次に、Fp上の識別多項式f(x,y,t)を定められたフレームでランダムに生成する。続いて多項式ri(x,y,t),si(x,y,t)をランダムに生成して、３変数多項式m(x,y,t),f(x,y,t)及び公開鍵である代数曲面XのファイブレーションX(x,y,t)から３つ以上の暗号文Fi(x,y,t)を計算する。
【００６７】
Fi(x,y,t)＝m(x,y,t)＋f(x,y,t)si(x,y,t)＋X(x,y,t)ri(x,y,t)      (7)
ここで、i＝1…kとし、kは３以上とする。
【００６８】
なお、非特許文献１で開示されている暗号方式は、ｋ＝２である。これは後で述べるように、ｋ≦３とすることによって、因数分解すべき多項式の次数を絞り込み、復号処理時間の掛かる因数分解処理、因数抽出処理の時間を削減するためのものである。
【００６９】
暗号文Fi(x,y,t)（i＝1…k）を受け取った受信者は、所有する秘密鍵であるセクションＤを利用して次のように復号を行う。まず、セクションＤを暗号文F(x,y,t)に代入する。ここで、セクションＤを代数曲面X(x,y,t)に代入する。
【００７０】
X(ux(t),uy(t),t)＝0,
なる関係があることに注意する。そうすれば、
hi(t)＝Fi(ux(t),uy(t),t)
＝m(ux(t),uy(t),t)＋f(ux(t),uy(t),t)si(ux(t),uy(t),t) 
という関係を持つｋ個の式hi(t)（i＝1…k）が求まることが分かる。次に、ｋ個の多項式のうち、互いに異なる２式を辺々引き算して、複数の多項式gj(t)を計算する。
【００７１】
gj(t)＝f(ux(t),uy(t),t){sa(ux(t),uy(t),t)−sb(ux(t),uy(t),t)}   (8)
ここで、１≦ａ≠ｂ≦ｋである。
【００７２】
次に、複数の多項式gj(t)の最大公約式φ(t)を求め、これを因数分解して、deg f(ux(t),uy(t),t)を次数に持つ因子f(ux(t),uy(t),t)を抽出する。ここで、このような因子は一意的に求まるとは限らないが、正しい因子f(ux(t),uy(t),t)が抽出できた際には、条件(6)からhi(t)（i＝1…k）のいずれかを因子f(ux(t),uy(t),t)で割ることにより、剰余として正しい平文多項式候補m(ux(t),uy(t),t)が抽出される。
【００７３】
正しい平文多項式候補m(ux(t),uy(t),t)が求められた場合、そこから平文ｍを以下の手段で導出する。平文多項式m(x,y,t)
【数９】
2010204466.tif 000011
【００７４】
とおき、平文候補多項式m(ux(t),uy(t),t)と、mijkux(t)iuy(t)jtkとが等しいことからtkの係数比較により、mijkを変数とする連立１次方程式が得られる。
【００７５】
実際、
m(ux(t),uy(t),t)＝mijkux(t)i uy(t)j tk 
の両辺はmijk以外の変数はtのみであり、
【数１０】
2010204466.tif 000012
【００７６】
から変数ｔの係数を比較することにより、連立１次方程式
aτ(…,mijk,…)＝cτ(1≦τ≦K)
を得る。これを解くことによりmijkが求まる。ここで、式の個数と変数の個数の関係によってはmijkが一意的に定まらないこともある。この問題は公開鍵の１つである平文多項式のフレームの定め方で解決するが、詳しくは鍵生成手法の部分で述べる。
【００７７】
ここで、求められた平文が正しいものであるか否かは平文に埋め込まれた誤り検出符号で確認する。
【００７８】
しかし、識別多項式f(ux(t),uy(t),t)の候補が複数ある場合は必ずしも、ここで得られた平文が真の平文とは限らない。そこで、前述した手法で抽出された平文について誤り検出符号によるチェックを行ない、検査に成功（即ち、誤り検出符号によって誤りとならなかった）候補を平文とする。
【００７９】
一方、識別多項式f(ux(t),uy(t),t)でない因子が抽出された場合は、前述同様の演算により間違った平文m’が復元され、平文に予め埋め込まれた誤り検出符号などを使ってその誤りを見出すことができる。
【００８０】
復号処理においては、複数の因子の候補が出現するが、本実施形態の復号方式は非特許文献１で開示されている復号方式よりも効率的である。なぜならば非特許文献１で開示されている復号方式は２つの暗号文F1,F2から構成されているため、１つの減算結果g1(t)＝h1(t)−h2(t)しか導出できないため、ここから最大公約式を計算することができず、g1(t)そのものを因数分解するしかなかった。一般にg1(t)の方が本実施形態で計算される最大公約式φ(t)よりも次数が高いため、因数分解処理の処理時間が掛かる。更に、因数分解した結果の因子も多いため、因数抽出処理に処理時間が掛かる。特に後者の因数抽出処理はdeg f(ux(t),uy(t),t)を次数に持つ多項式を抽出するため、以下の例のように多くの組み合わせが生じる。
【００８１】
例えば、deg f(ux(t),uy(t),t)＝５のとき、
g1(t)＝(t3＋1)(t2＋t＋1)t(t＋1)(t＋2)(t＋3)(t＋4)
とすれば、次数の種類が3, 2, 1, 1, 1, 1, 1であるので、次数の組み合わせとして 
５＝３＋２，３＋１＋１，２＋１＋１＋１，１＋１＋１＋１＋１
が考えられる。この問題は一般には数列から所定の値を持つ部分和を求めるという部分和問題となり、極めて困難な問題となる。従って、非特許文献１で開示された暗号方式では十分計算可能な範囲ではあるものの、（因数分解結果によっては）高速に演算することができない場合がある。
【００８２】
これに対して本実施形態の復号方式は暗号方式において３つ以上の暗号文Fi（i＝1…k）を用いるため、複数の減算結果gj(t)（j＝1, …,L）が導出でき、それらの最大公約式φ(t)から、より次数の低い多項式が得られるため、非特許文献１で開示された暗号方式よりも高速に復号できる。
【００８３】
尚、ここで最大公約式の計算はユークリッドの互除法と呼ばれる演算で計算でき、同演算は非常に高速に演算できる。更に因数分解も対象となる多項式が１変数多項式であるため、容易であることが知られており、十分有効な時間内に処理可能である。
【００８４】
ところで、識別多項式f(ux(t),uy(t),t)の候補が複数ある場合は必ずしも、ここで得られた平文が真の平文とは限らない。そこで、全ての識別多項式f(ux(t),uy(t),t)の候補から、前述した手法で抽出された平文について誤り検出符号によるチェックを行ない、検査に成功（即ち、誤り検出符号によって誤りとならなかった）候補を平文とする。
【００８５】
この検査に成功した候補が１つも無かった場合は復号失敗として処理する。このような場合は理論的には有り得ないが、送信側の計算ミスや伝送路上での改竄などの何らかの理由により正しくない暗号文を受信したことより起こる可能性がある。
【００８６】
最後に本実施形態における鍵生成方法を説明する。本実施形態の鍵生成方法は代数曲面及びパラメータの生成、識別多項式のフレームの生成、平文多項式のフレームの生成からなり、この順に実行される。
【００８７】
始めに、代数曲面及びパラメータの生成手法から説明する。同生成方法の入力はシステムパラメータp, d, degt X’, Λxである。ここで、degt X’は代数曲面Xから定数項を除いた多項式X’（＝X−a00(t)）の次数である。これらは公開鍵となる代数曲面のパラメータであり、求セクション問題が十分困難となるように選択されている。まず、代数曲面の生成手法を説明する。代数曲面の生成はセクションＤをランダムに選び、それに対応したファイブレーションを計算することによって行う。
【００８８】
始めに、システムパラメータp, d, degt X’, Λxに基づいて、代数曲面のファイブレーション
【数１１】
2010204466.tif 000013
【００８９】
によって定数項a00(t)を決定する。また、
degt X ＝ max{degt X’, deg a00(t)}
によってdegt Xを決定する。
【００９０】
次に、識別多項式と平文多項式のパラメータ生成手法を説明する。まず、識別多項式のパラメータdegt f, Λfをdegt X, ΛXに基づいて条件(4)の範囲でランダムに生成する。次に、ΛfΛXを計算し、平文多項式の係数集合Λmをその部分集合で且つ条件(4)を満たす範囲で決定する。ここで、条件(4)を満たす係数集合Λmが存在しない場合は、パラメータdegt f, Λfの生成からやり直す。次に、degt mを
degt X ＜degt m ＜ degt f 
の範囲で決定する。ここで、degt f ＝(degt X)＋１である場合など前記条件を満たすdegt mができないときは、degt f, Λfの決定からやり直す。
【００９１】
以上で、代数曲面及びパラメータの生成方法の説明を終了する。
【００９２】
続いて、識別多項式のフレームの生成手法について説明する。識別多項式のフレームの生成は、前述したパラメータに基づいて、係数集合Λfに含まれる各要素(i,j)に対するdeg fij(t)を決定することで行う。但し、要素(i,j)＝(degx f, degy f）の場合はdeg fij(t)＝degt fとし、それ以外の場合は０≦deg fij(t)≦degt fの範囲でランダムに生成する。これで識別多項式のフレームＦRfが決定された。
【００９３】
次に、平文多項式のフレームの生成手法について説明する。代数曲面は既に生成されているので、これから係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出することにより代数曲面のフレームＦRXを導出する。続いて各フレームＦRf,ＦRXからＦRg(＝ＦRf ＦRX)を計算する。ここで、係数集合Λmは、このフレームＦRgに対応する係数集合Λg(＝ΛX Λf)の部分集合になっている。そこで、以下のように係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij(t)}に決定する。これにより、条件(4)が実現できる。
【００９４】
平文多項式m(x,y,t)の生成において重要な点はセクションによってできる連立１次方程式に一意解を持たせることである。このために、生成した代数曲面のセクション(x,y,t)＝(u(t),uy(t),t) に基づいて以下のような処理を行なう。まず、前述したように定めたフレームＦRmにセクションを代入して、
【数１２】
2010204466.tif 000014
【００９５】
における変数tτの係数であり、有限体Fpの元である。また行列Ａは変数ベクトル(m000,m001,…,mijk,…)において変数mijkがΚ番目の要素として表現されている場合、行列Ａではtτの係数としてのmijkが非零の元として出現している場合は行列Ａの(τ,Κ)成分にその係数、出現しない場合は(τ,Κ)成分に０として表現された行列である。即ち、変数ベクトル(m000,m001,m002,m010,m011,m012)に対して
【数１３】
2010204466.tif 000015
【００９６】
となる。さて、本連立１次方程式が如何なるc0,c1,…,cKが生じても一意解を持つ必要十分条件は線形代数の理論により変数ベクトル(m000,m001,m002,m010,m011,m012)の次元数が行列Ａの階数と等しくなることである。
【００９７】
よって、行列Ａの階数を計算すると共に、その階数が変数ベクトルの次元数と一致しないときにはｔの上位次数に対応したmijkに零などの定数を代入して変数の数を段階的に引き下げていくことにより、一意性が達成できる。実際、前記連立１次方程式は解が存在するので、本実施形態において作成される行列Ａは階数が変数ベクトルの次元数よりも大きくなることはない。なぜなら、もし階数が変数ベクトルの次元数よりも大きくなった場合は線形代数の理論により対応する連立１次方程式に解がなくなる。よって行列の階数は必ず変数ベクトルの次元数以下となる。そこで、階数と変数ベクトルの次元数の一致させるためには、変数ベクトルの次元数を段階的に下げていく調整が必要となる。ここで０とした変数mijkには平文を埋め込むことができないため、各(i,j)において非零でよいmijkにおけるkの最大値を持ってmij(t)の次数と定める。このことにより、平文多項式のフレームが定まる。但し、条件(4)を満たすためにいずれかのmij(t)の上位の項を非零とする必要がある。
【００９８】
以上で、平文多項式のフレームの決定手法の説明を終了し、もって鍵生成手法の説明も終了する。
【００９９】
＜第１の実施形態のバリエーション＞
最後に本実施形態におけるいくつかのバリエーションを述べる。各バリエーションは任意の組合せで同時に実施できるが、説明の便宜上、各バリエーションを個別に実施した場合を説明する。尚、以下ではri(x,y,t)（i＝1,…,k）を区別する必要がない共通の事象の場合には単にr(x,y,t)と書き、si(x,y,t)（i＝1,…,k）を区別する必要がない共通の事象の場合には単にs(x,y,t)と書くこととする。暗号文Fi(x,y,t)についても同様とする。
【０１００】
第１のバリエーションは、暗号化処理において、暗号文を生成する式(7)の変形に関するバリエーションである。式(7)は、例えば
F(x,y,t)＝m(x,y,t)−f(x,y,t)s(x,y,t)−X(x,y,t)r(x,y,t)
のように変形しても同様に暗号化／復号が可能である。このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することは可能であり、本発明の範囲に含まれる。
【０１０１】
第２のバリエーションは暗号化処理において、識別多項式f(x,y,t)を既約多項式とする方式である。
【０１０２】
本実施形態においては識別多項式には既約多項式という制約を設けなかったが、既約多項式であれば、２つの暗号文にセクションを代入してできる２つの１変数多項式から計算できるf(ux(t),uy(t),t){s1(ux(t),uy(t),t)−s2(ux(t),uy(t),t)}から因数分解によってf(ux(t),uy(t),t)が既約多項式として抽出される可能性があるだけでなく、確率的に因子の数が少なくなり、f(ux(t),uy(t),t)の抽出が容易となる。
【０１０３】
第３のバリエーションは、暗号化処理において、平文mを識別多項式f(x,y,t)にも埋め込む方式である。前述した実施形態では識別多項式をランダムに生成する方式を示したが、秘密鍵なしにf(x,y,t)を求めることが困難であることも本実施形態の公開鍵暗号の性質であるから、識別多項式にも平文情報を埋め込む方式が実現可能である。逆に、本バリエーションのようにf(x,y,t)にも平文を埋め込む場合、より大きなサイズの平文を一度に暗号化できるという効果もある。但し、第２のバリエーションと共に実施する場合は、埋め込んだ結果であるf(x,y,t)を既約多項式とする必要から、特定の係数にはランダムな係数が埋め込まれるように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文を埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。
【０１０４】
第４のバリエーションは、暗号化処理において、項f(x,y,t)s(x,y,t)と、項X(x,y,t)r(x,y,t)とがx,yの多項式として同じ同類項を含み、かつそれらの係数となるtを変数とする１変数多項式の次数を一致させるように、ランダム多項式s(x,y,t),r(x,y,t)を生成する方式である。このバリエーションによれば暗号文の上からは、f(x,y,t)s(x,y,t)の項と、X(x,y,t)r(x,y,t)の項との区別がつかないため安全性が高まる。更に、m(x,y,t)に関しても同様にx,yの多項式としてみたとき、X(x,y,t)r(x,y,t)（あるいはf(x,y,t)s(x,y,t)）の同類項に含まれ、その係数の次数もX(x,y,t)r(x,y,t)に含まれる当該同類項の次数よりも低いことが満たされると、よりm(x,y,t)がX(x,y,t)r(x,y,t)の項と識別不能となるため、安全性が高まる。
【０１０５】
第５のバリエーションは、復号処理において、正しい平文が２つ以上計算される場合に対応したものである。本実施形態では、最大公約式φ(t)を因数分解して、次数が丁度deg f(ux(t),uy(t),t)となるように因子を組合せることにより識別多項式f(ux(t),uy(t),t)の候補を得ている。次に、これに対応した平文候補Mを計算し、当該平文候補Mに含まれる誤り検出符号によって、当該平文候補が正しいものであるか否かを判定し、正しいと判定された場合には処理をそこで止めて、平文を出力していた。これに対し本バリエーションでは全ての識別多項式の候補から平文候補を計算し、前述した検査を行い、検査に成功（即ち、誤り検出符号で誤りが検出されなかった）平文候補のみを記録する。
【０１０６】
このとき、全ての識別多項式の候補に伴う処理が終了した時点で、当該候補が複数ある場合や１つも無かった場合は復号失敗として処理する。このように構成することで、誤り検出符号の能力が低い場合や偶然の一致などによって平文が２つ以上計算されてしまう場合の誤りに備えることができる。
【０１０７】
第６のバリエーションは、復号処理において、複数のセクションを利用する方式である。本実施形態では１つのセクションのみを利用していたが、複数のセクションを利用することにより誤り検出符号を用いることなく、正しい平文を計算することができる。複数のセクションを利用する場合はセクション毎に本実施形態の復号処理を行ない、出力された平文候補の集合の共通分となる平文を正しい平文として出力することができる。一方、更にセクションによっては（確率的にはほとんど無視できる範囲ではあるが）復号演算において、
si(ux(t),uy(t),t)−sj(ux(t),uy(t),t)＝0
となり、平文候補が１つも求まらない可能性もある。このようなときにも本バリエーションは有用である。尚、第５のバリエーションと併せて実施することも可能である。
【０１０８】
ここで、第６のバリエーションを実現するために複数のセクションを持つ代数曲面の生成手法を説明しなければならない。以下では２つのセクションＤ1,Ｄ2を持つ代数曲面を生成する鍵生成手法について述べる。
【０１０９】
本鍵生成はセクションＤ1,Ｄ2をランダムに選び、それに対応したファイブレーションを計算することによって行う。但し、生成された代数曲面が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。代数曲面（のファイブレーション）を次式のように書く。
【数１４】
2010204466.tif 000016
【０１１０】
ここで、セクションＤ1,Ｄ2を
Ｄ1:(x,y,t)＝(ux(t),uy(t),t),  
Ｄ2:(x,y,t)＝(vx(t),vy(t),t)
とおいて代数曲面Xに代入し、
Σ(i,j) ａij(t)ux(t)iuy(t)j＝0
Σ(i,j) ａij(t)vx(t)ivy(t)j＝0
を得る。これらを辺々引くと両式に共通の定数項ａ00(t)が消え、式(10)を得る。
【数１５】
2010204466.tif 000017
【０１１１】
から多項式となるａ10(t)を生成するには、
ux(t)−vx(t)｜uy(t)−vy(t)
のように設定すれば十分である（なお、A｜Bの表記は、AがBを割り切ること、即ちBがAの倍数（倍式）であることを意味する）。このことは式(11)と
(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以下となる。
【０１１６】
次に、ａ00(t),ａ10(t)x以外の係数ａij(t)((i,j)≠(0,0),(1,0))をランダムに生成し、前述のように計算されたux(t),vx(t),uy(t),vy(t)を利用して式(10)に従ってａ10(t)を計算する。更に、
【数１６】
2010204466.tif 000018
【０１１７】
などのようにxの因子とyの因子をランダムに両辺に分けて公開鍵暗号である代数曲面を生成することが望ましい。このように公開鍵と秘密鍵を生成することによって一般にｎ個以上のセクションを持つ代数曲面を生成することができる。
【０１１８】
第７のバリエーションは、暗号化処理において、暗号文を生成する式(7)の変形に関するバリエーションである。式(7)を例えば
F1(x,y,t)＝m(x,y,t)＋f(x,y,t)s1(x,y,t)＋X(x,y,t)r1(x,y,t) 
F2(x,y,t)＝            f(x,y,t)s2(x,y,t)＋X(x,y,t)r2(x,y,t) 
F3(x,y,t)＝            f(x,y,t)s3(x,y,t)＋X(x,y,t)r3(x,y,t) 
のように変形しても復号が可能である。この際にはF2,F3にセクションを代入して得られる多項式h2(t),h3(t)はm(x,y,t)の項が含まれないので、減算処理をすることなく、減算処理結果として得られた多項式gj(t)（j＝1,…,L）の一部と看做して最大公約式φ(t)を求め、最大公約式φ(t)でh1(t)を割った剰余としてm(ux(t),uy(t),t)を求めることができる。このように少なくとも１つの暗号文にm(x,y,t)の項を含め、他の暗号文にはm(x,y,t)の項を含めないことによって、減算処理を省略でき、更なる高速化が可能となる。また、このことは暗号化処理においても加算を削減する意味でも有効である。
【０１１９】
第８のバリエーションは、復号処理において導出されるgj(t)（j＝1,…,L）の最大公約式φ(t)の次数がdeg f(ux(t),uy(t),t)と一致した場合、φ(t)の因数分解処理と因数抽出処理をスキップすることにより、更なる高速化が実現できる方式である。これはφ(t)の次数とdeg f(ux(t),uy(t),t)が一致するということはf(ux(t),uy(t),t)＝φ(t)を意味し、直接hi(t)（i＝1,…,k）のいずれかをf(ux(t),uy(t),t)で割ることにより、剰余として正しいm(ux(t),uy(t),t)が抽出可能となる。このバリエーションは常に実行できるとは限らないが、基礎体のサイズpが大きくなるとdeg φ(t)＝deg f(ux(t),uy(t),t)となる確率が高くなり、高速化に繋がる。尚、本バリエーションを第７のバリエーションに適用することが可能である。
【０１２０】
（第２の実施形態の概要）
次に、第２の実施形態の概要を説明するが、第１の実施形態と同一部分についてはその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【０１２１】
始めに、第２の実施形態において、システムパラメータ、公開鍵、秘密鍵、フレームの条件といった前提条件は第１の実施形態と同様である。また、第２の実施形態の鍵生成処理は第１の実施形態と同様である。
【０１２２】
続いて、第２の実施形態の暗号化処理の概要を述べる。
【０１２３】
第２の実施形態の暗号化処理においては、平文を平文多項式に埋め込むまでの処理は前述した通りである。また、誤り検出符号についても前述した通りである。
【０１２４】
しかしながら、第２の実施形態の暗号化処理は、第１の実施形態とは異なり、次のように２つの暗号文F1(x,y,t),F2(x,y,t)を生成する。
【０１２５】
すなわち、Fp上の識別多項式f(x,y,t)を定められたフレームでランダムに生成した後、４つの多項式r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をランダムに生成して、３変数多項式m(x,y,t),f(x,y,t)及び公開鍵である代数曲面XのファイブレーションX(x,y,t)から２つの暗号文F1(x,y,t),F2(x,y,t)を計算する。
【０１２６】
F1(x,y,t)＝m(x,y,t)＋f(x,y,t)s1(x,y,t)＋X(x,y,t)r1(x,y,t) 
F2(x,y,t)＝            f(x,y,t)s2(x,y,t)＋X(x,y,t)r2(x,y,t)     (7)’
第２の実施形態の暗号化処理においては、非特許文献１に開示されている暗号化方式と比較して、第２の暗号文F2(x,y,t)において平文多項式m(x,y,t)を加算する処理が少なくなり、全体として加算３回、乗算４回となって高速・効率的となる。
【０１２７】
次に、第２の実施形態の復号処理の概要を述べる。
【０１２８】
暗号文F1(x,y,t),F2(x,y,t)を受け取った受信者は、所有する秘密鍵であるセクションＤを利用して次のように復号を行う。まず、セクションＤを暗号文F1(x,y,t),F2(x,y,t)に代入する。ここで、セクションＤを代数曲面X(x,y,t)に代入する。
【０１２９】
X(ux(t),uy(t),t)＝0,
なる関係があることに注意する。そうすれば、
h1(t)＝F1(ux(t),uy(t),t)
＝m(ux(t),uy(t),t)＋f(ux(t),uy(t),t)s1(ux(t),uy(t),t) 
h2(t)＝F2(ux(t),uy(t),t)
＝                     f(ux(t),uy(t),t)s2(ux(t),uy(t),t) 
という関係を持つ２つの多項式h1(t),h2(t)が求まることが分かる。次に、m(ux(t),uy(t),t)を含まない多項式h2(t)を因数分解して因子f(ux(t),uy(t),t)を求める。このような因子は一意的に求まるとは限らないが、正しい因子f(ux(t),uy(t),t)を抽出できた際には、条件(6)から多項式h1(t)を因子f(ux(t),uy(t),t)で割ることにより、剰余として正しい平文多項式候補m(ux(t),uy(t),t)が抽出される。
【０１３０】
正しい平文多項式候補m(ux(t),uy(t),t)が求められた場合、以降の平文導出処理、平文検査処理及び平文出力処理は第１の実施形態と同様に実行される。
【０１３１】
第２の実施形態の復号処理においては、非特許文献１に開示されている復号方式と比較して、セクション代入後の多項式h1(t),h2(t)を互いに減算する処理が省かれるので、高速・効率的となる。
【０１３２】
＜第２の実施形態のバリエーション＞
最後に本実施形態におけるいくつかのバリエーションを述べる。各バリエーションは任意の組合せで同時に実施できるが、説明の便宜上、各バリエーションを個別に実施した場合を説明する。尚、以下ではri(x,y,t)（i＝1,…,k）を区別する必要がない共通の事象の場合には単にr(x,y,t)と書き、si(x,y,t)（i＝1,…,k）を区別する必要がない共通の事象の場合には単にs(x,y,t)と書くこととする。暗号文Fi(x,y,t)についても同様とする。
【０１３３】
第１のバリエーションは、暗号化処理において、暗号文を生成する式(7)’の変形に関するバリエーションである。式(7)’は、例えば
F1(x,y,t)＝m(x,y,t)−f(x,y,t)s1(x,y,t)−X(x,y,t)r1(x,y,t) 
F2(x,y,t)＝            f(x,y,t)s2(x,y,t)−X(x,y,t)r2(x,y,t) 
のように変形しても同様に暗号化／復号が可能である。なお、復号処理においては、セクション代入後の多項式h1(t),h2(t)は以下のようになる。
【０１３４】
h1(t)＝F1(ux(t),uy(t),t)
＝m(ux(t),uy(t),t)−f(ux(t),uy(t),t)s1(ux(t),uy(t),t) 
h2(t)＝F2(ux(t),uy(t),t)
＝                     f(ux(t),uy(t),t)s2(ux(t),uy(t),t) 
このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することは可能であり、本発明の範囲に含まれる。
【０１３５】
第２のバリエーションは暗号化処理において、識別多項式f(x,y,t)を既約多項式とする方式である。
【０１３６】
本実施形態においては識別多項式には既約多項式という制約を設けなかったが、既約多項式であれば、第２の暗号文F2(x,y,t)にセクションを代入してできる１変数多項式h2(t)から因数分解によってf(ux(t),uy(t),t)が既約多項式として抽出される可能性があるだけでなく、確率的に因子の数が少なくなり、f(ux(t),uy(t),t)の抽出が容易となる。
【０１３７】
第３のバリエーションは、暗号化処理において、平文mを識別多項式f(x,y,t)にも埋め込む方式である。前述した実施形態では識別多項式をランダムに生成する方式を示したが、秘密鍵なしにf(x,y,t)を求めることが困難であることも本実施形態の公開鍵暗号の性質であるから、識別多項式にも平文情報を埋め込む方式が実現可能である。逆に、本バリエーションのようにf(x,y,t)にも平文を埋め込む場合、より大きなサイズの平文を一度に暗号化できるという効果もある。但し、第２のバリエーションと共に実施する場合は、埋め込んだ結果であるf(x,y,t)を既約多項式とする必要から、特定の係数にはランダムな係数が埋め込まれるように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文を埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。
【０１３８】
第４のバリエーションは、暗号化処理において、項f(x,y,t)s(x,y,t)と、項X(x,y,t)r(x,y,t)とがx,yの多項式として同じ同類項を含み、かつそれらの係数となるtを変数とする１変数多項式の次数を一致させるように、ランダム多項式s(x,y,t),r(x,y,t)を生成する方式である。このバリエーションによれば暗号文の上からは、f(x,y,t)s(x,y,t)の項と、X(x,y,t)r(x,y,t)の項との区別がつかないため安全性が高まる。更に、m(x,y,t)に関しても同様にx,yの多項式としてみたとき、X(x,y,t)r(x,y,t)（あるいはf(x,y,t)s(x,y,t)）の同類項に含まれ、その係数の次数もX(x,y,t)r(x,y,t)に含まれる当該同類項の次数よりも低いことが満たされると、よりm(x,y,t)がX(x,y,t)r(x,y,t)の項と識別不能となるため、安全性が高まる。
【０１３９】
第５のバリエーションは、復号処理において、正しい平文が２つ以上計算される場合に対応したものである。本実施形態では、多項式h2(t)を因数分解して、次数が丁度deg f(ux(t),uy(t),t)となるように因子を組合せることにより識別多項式f(ux(t),uy(t),t)の候補を得ている。次に、これに対応した平文候補Mを計算し、当該平文候補Mに含まれる誤り検出符号によって、当該平文候補が正しいものであるか否かを判定し、正しいと判定された場合には処理をそこで止めて、平文を出力していた。これに対し本バリエーションでは全ての識別多項式の候補から平文候補を計算し、前述した検査を行い、検査に成功（即ち、誤り検出符号で誤りが検出されなかった）平文候補のみを記録する。
【０１４０】
このとき、全ての識別多項式の候補に伴う処理が終了した時点で、当該候補が複数ある場合や１つも無かった場合は復号失敗として処理する。このように構成することで、誤り検出符号の能力が低い場合や偶然の一致などによって平文が２つ以上計算されてしまう場合の誤りに備えることができる。
【０１４１】
第６のバリエーションは、復号処理において、複数のセクションを利用する方式である。本実施形態では１つのセクションのみを利用していたが、複数のセクションを利用することにより誤り検出符号を用いることなく、正しい平文を計算することができる。複数のセクションを利用する場合はセクション毎に本実施形態の復号処理を行ない、出力された平文候補の集合の共通分となる平文を正しい平文として出力することができる。一方、更にセクションによっては（確率的にはほとんど無視できる範囲ではあるが）復号演算において、
s2(ux(t),uy(t),t)＝0
となり、平文候補が１つも求まらない可能性もある。このようなときにも本バリエーションは有用である。尚、第５のバリエーションと併せて実施することも可能である。
【０１４２】
ここで、第６のバリエーションを実現するための複数のセクションを持つ代数曲面の生成手法は、第１の実施形態の第６のバリエーションにおける手法と同様である。また、２つのセクションＤ1,Ｄ2を持つ代数曲面を生成する鍵生成手法についても、第１の実施形態の第６のバリエーションにおける手法と同様である。
【０１４３】
＜安全性の検討＞
以下では第１及び第２の実施形態で構成した公開鍵暗号の安全性に関して考察する。
【０１４４】
［１］総当り攻撃
暗号文F(x,y,t)を構成する各要素m(x,y,t),f(x,y,t),s(x,y,t),r(x,y,t)をmijk,fijk,sijk,rijkを変数として
【数１７】
2010204466.tif 000019
【０１４５】
とおき、これらと暗号文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(x,y,t)＋f(x,y,t)s(x,y,t)が求まらないかを検討しなくてはならない。しかし、３変数多項式同士の割り算の場合、剰余が一意に決まらない。なぜならば文献（D.コックス  他,“グレブナ基底と代数多様体入門（上）,”シュプリンガー・フェアラーク東京,(2000),p.94, 例４にあるように２変数以上の多項式では一般に除法の定理が成り立たないためである。
【０１４７】
［３］代入攻撃
［３−１］代数曲面上の代数曲線を代入する攻撃
（セクションを含む）代数曲線はωをパラメータとして、式(14)のように書ける。
【０１４８】
(x,y,t)＝(ux(ω),uy(ω),ut(ω))       (14)
これらの曲線のうち、代数曲面X(x,y,t)に含まれるものを見出すことができれば、セクションの代わりに代入して、セクションによる復号と同様の手法により、解読することができる。ここではこのような代数曲線を見出すことが与えられているセクションを見出すことと同等かそれ以上に計算困難であることを示す。このような曲線をdeg ut(ω)に注目して分類する。
【０１４９】
・ deg ut(ω)≧２の場合
この場合は一般の因子となり、求因子問題の困難性により脅威とはならない。
【０１５０】
・ deg ut(ω)＝１の場合
これが求まると線形変換でセクションが求まるため、求セクション問題が困難であるという仮定の下ではこのような代数曲線を求めることも困難となる。
【０１５１】
・ deg ut(ω)＝０の場合
これは特異ファイバー(singular fiber)と呼ばれるもので、ほとんど全ての代数曲面に存在する。しかし、一般の求因子問題の特別な場合であり、効率的に解く方法は知られていない。
【０１５２】
［３−２］代数曲面外の代数曲線を代入する攻撃
代数曲面外の代数曲線の場合も式(14)として書け、X(ux(ω),uy(ω),ut(ω))≠０である。よって、次式を得る。
【０１５３】
F(ux(ω),uy(ω),ut(ω))＝m(ux(ω),uy(ω),ut(ω))＋f(ux(ω),uy(ω),ut(ω))s(ux(ω),uy(ω),ut(ω))＋X(ux(ω),uy(ω),ut(ω))r(ux(ω),uy(ω),ut(ω))
しかし、ここで分かっている式はX(ux(ω),uy(ω),ut(ω))であるのでF(ux(ω),uy(ω),ut(ω))をX(ux(ω),uy(ω),ut(ω))でリダクションする攻撃が考えられる。これは１変数なので可能ではあるが、条件(4)(5)により、m(ux(ω),uy(ω),ut(ω))＋f(ux(ω),uy(ω),ut(ω))s(ux(ω),uy(ω),ut(ω))の次数の方が、X(ux(ω),uy(ω),ut(ω))の次数よりも大きいため、正確な剰余を得ることが困難である。
【０１５４】
［３−３］代数曲面上の有理点を代入する攻撃
代数曲面X(x,y,t)の有理点（X(x,y,t)＝0 となる点）を代入することによる攻撃がある。即ち、mijk,fijk,sijkを未知数として
【数１８】
2010204466.tif 000020
【０１５５】
とおき、（公開鍵である）代数曲面X(x,y,t)＝０のＫ有理点(xi,yi,ti)は（どのような代数曲面でも）比較的簡単かつ大量に求まることが知られているため、これらの有理点を暗号文F(x,y,t) に代入して、
F(xi,yi,ti)＝m(xi,yi,ti)＋f(xi,yi,ti)s(xi,yi,ti)
という関係式が大量に求まる。ここでＫはFp及びその拡大体をさしている。
【０１５６】
これらを連立させるとm(x,y,t)が解ける可能性がある。しかし、f(x,y,t),s(x,y,t)はランダムな多項式であり、特にf(x,y,t)s(x,y,t)はX(x,y,t)r(x,y,t)に含まれる全ての同類項を全て含むと共に、各項の係数の次数が等しいので、r(x,y,t)の各係数の次数を十分大きくしておけば、必然的にs(x,y,t)の係数の次数も連立方程式が解けないほど大きくなり、事実上計算不可能となる。従ってこのような攻撃は本実施形態の公開鍵暗号にとっては脅威とはならない。
【０１５７】
一方、暗号文からs1(x,y,t)の因子を削除すると、連立方程式は
F1(xi,yi,ti)＝m(xi,yi,ti)＋f(xi,yi,ti)
となり、連立１次方程式を解くことにより、比較的簡単に係数が求められてしまう。この理由で因子s(x,y,t)が存在する。
【０１５８】
また、暗号文から識別多項式f(x,y,t)の要素を削除すると、本攻撃により
F1(xi,yi,ti)＝m(xi,yi,ti)+ s1(xi,yi,ti)
となり、更に簡単に平文多項式m(x,y,t)が求まってしまう。この理由で識別多項式f(x,y,t)を含む要素が存在する。
【０１５９】
以上のように各実施形態の公開鍵暗号は、上述した攻撃に対する耐性がある。即ち（逆に言うと）各実施形態の公開鍵暗号は耐性を持つように各構成要素が設定されている。
【０１６０】
（第１の実施形態の具体的な構成）
以下、本発明の第１の実施形態について具体的に説明する。図２は本発明の第１の実施形態に係る暗号装置の全体構成図であり、図３は同実施形態における復号装置の全体構成図である。図４は同実施形態における鍵生成装置の全体構成図である。
【０１６１】
なお、以下の暗号装置１００、復号装置２００及び鍵生成装置３００は、装置１００，２００，３００毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体１，２，３から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。このことは以下の各実施形態及び各バリエーションでも同様である。
【０１６２】
ここで、暗号装置１００は、図２に示すように、パラメータ格納部１０１、メモリ１０２、入力部１０３、平文埋め込み部１０４、暗号化部１０５、識別多項式生成部１０６、多項式生成部１０７、ランダム値生成部１０８、多項式演算部１０９及び出力部１１０が互いにバス１１１を介して接続されている。
【０１６３】
パラメータ格納部１０１は、暗号化部１０５から読出可能なメモリであり、システムパラメータである素体の標数pを格納している。
【０１６４】
メモリ１０２は、各部１０３〜１０９から読出／書込可能な記憶装置である。
【０１６５】
入力部１０３は、外部から入力された平文多項式のフレームΛm,deg mij(t)及び平文mを平文埋め込み部１０４に送出する機能と、外部から入力された公開鍵X(x,y,t),Λm,Λf,deg mij(t),deg fij(t)を暗号化部１０３に送出する機能とをもっている。
【０１６６】
平文埋め込み部１０４は、入力部１０３から受けた平文多項式のフレーム及び平文mに基づいて、平文mを平文多項式m(x,y,t)の係数に埋め込む機能と、得られた平文多項式m(x,y,t)を暗号化部１０５に送出する機能とをもっている。
【０１６７】
暗号化部１０５は、入力部１０３から受けた公開鍵及びパラメータ格納部１０１内のパラメータpに基づいて、図５のＳＴ５〜ＳＴ８に示す動作を実行するように、各部１０２，１０６〜１０９を制御する機能をもっている。
【０１６８】
識別多項式生成部１０６は、暗号化部１０５から受けた識別多項式f(x,y,t)のフレーム及びパラメータpに基づいて、識別多項式f(x,y,t)をランダムに生成する機能と、得られた識別多項式f(x,y,t)を暗号化部１０５に送出する機能とをもっている。
【０１６９】
多項式生成部１０７は、３組以上の多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）を生成する指示を暗号化部１０５から受けると、ランダム値生成部１０８に対してランダム値の出力要請を繰り返し行い、得られたランダム値を利用して２ｋ個の多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）を生成する機能と、生成した多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）を暗号化部１０５に送出する機能とをもっている。
【０１７０】
ランダム値生成部１０８は、多項式生成部１０７から受けた出力要請に応じてランダム値を生成し、このランダム値を多項式生成部１０７に送出する機能をもっている。
【０１７１】
多項式演算部１０９は、暗号化部１０５から受けた多項式とその演算指示に基づいて、多項式演算を実行し、演算結果を暗号化部１０５に送出する機能をもっている。
【０１７２】
出力部１１０は、暗号化部１０５から受けた暗号文Fi(x,y,t)（i＝1,…,k）を出力する機能をもっている。
【０１７３】
復号装置２００は、図３に示すように、パラメータ格納部２０１、メモリ２０２、入力部２０３、復号部２０４、セクション代入部２０５、１変数多項式演算部２０６、最大公約式演算部２０７、１変数多項式因数分解部２０８、１変数多項式剰余演算部２０９、連立１次方程式求解部２１０、平文検査部２１１及び出力部２１２が互いにバス２１３を介して接続されている。
【０１７４】
パラメータ格納部２０１は、復号部２０４から読出可能なメモリであり、システムパラメータである素体の標数pを格納している。
【０１７５】
メモリ２０２は、各部２０３〜２１１から読出／書込可能な記憶装置である。
【０１７６】
入力部２０３は、外部から入力された暗号文Fi(x,y,t)（i＝1,…,k）、公開鍵x(x,y,t)及びセクションＤを復号部２０４に送出する機能をもっている。
【０１７７】
復号部２０４は、入力部２０４から受けた暗号文Fi(x,y,t)（i＝1,…,k）、公開鍵x(x,y,t)及びセクションＤと、パラメータ格納部内のパラメータpとに基づいて、図６のＳＴ１３〜ＳＴ２５に示す動作を実行するように各部２０２，２０５〜２１２を制御する機能をもっている。
【０１７８】
セクション代入部２０５は、復号部２０４から暗号文Fi(x,y,t)（i＝1,…,k）とセクションＤを受けると、セクションＤを暗号文Fi(x,y,t)（i＝1,…,k）に代入して１変数多項式hi(t)（i＝1,…,k）を得る機能と、得られたhi(t)（i＝1,…,k）を復号部２０４に送出する機能とをもっている。
【０１７９】
１変数多項式演算部２０６は、セクション代入部２０５又は復号部２０４から受けた１変数多項式の加減乗除演算を実行する機能と、演算結果をセクション代入部２０５又は復号部２０４に送出する機能をもっている。
【０１８０】
最大公約式演算部２０７は、復号部から多項式gj(t)（j＝1,…,L）を受けると、多項式gj(t)（j＝1,…,L）の最大公約式φ(t)を求める機能と、求めた最大公約式φ(t)を復号部２０４に送出する機能とをもっている。
【０１８１】
１変数多項式因数分解部２０８は、復号部２０４から受けた最大公約式φ(t)等の１変数多項式を因数分解する機能と、因数分解の結果を因子の順序付けられた配列として復号部２０４に送出する機能とをもっている。
【０１８２】
１変数多項式剰余演算部２０９は、復号部２０４から受けた被除多項式及び除多項式としての１変数多項式の剰余演算を実行する機能と、演算結果としての剰余を復号部２０４に送出する機能とをもっている。
【０１８３】
連立１次方程式求解部２１０は、復号部２０４から受けた連立１次方程式を行列演算によって解く機能と、得られた解を復号部２０４に送出する機能とをもっている。
【０１８４】
平文検査部２１１は、復号部２０４から受けた平文候補M内の誤り検出符号を検査する機能と、検査結果を復号部２０４に送出する機能とをもっている。
【０１８５】
出力部２１２は、復号部２０４から受けた平文mを出力する機能をもっている。
【０１８６】
鍵生成装置３００は、図４に示すように、固定パラメータ格納部３０１、メモリ３０２、入力部３０３、制御部３０４、セクション生成部３０５、１変数多項式生成部３０６、代数曲面生成部３０７、多項式演算部３０８、パラメータ生成部３０９、フレーム生成部３１０、平文多項式生成部３１１、行列生成部３１２、階数演算部３１３及び出力部３１４が互いにバス３１５を介して接続されている。
【０１８７】
固定パラメータ格納部３０１は、制御部３０４から読出可能なメモリであり、固定パラメータである素数pとセクションの最大次数dを格納している。
【０１８８】
メモリ３０２は、各部３０３〜３１２から読出／書込可能な記憶装置である。
【０１８９】
入力部３０３は、外部から入力されたファイブレーションX(x,y,t)の定数項以外の項の次数degt X’及び前記ファイブレーションX(x,y,t)の２変数x,yの係数集合ΛXを一時的にメモリ３０２に保存し、メモリ３０２内の次数degt X’及び係数集合ΛXを制御部３０４に送出する機能をもっている。
【０１９０】
制御部３０４は、入力部３０３から受けた次数degt X’及び係数集合ΛXと、固定パラメータ格納部３０１内の固定パラメータp,dとに基づいて、図７のＳＴ３４〜ＳＴ３７に示す動作を実行するように各部３０２，３０５〜３１４を制御する機能と、入力部３０３から受けた平文多項式の係数集合Λm及び係数の次数deg mij(t)と、固定パラメータ格納部３０１内の固定パラメータpとに基づいて、図８のＳＴ４４〜ＳＴ５０に示す動作を実行するように各部３０２，３０５〜３１２を制御する機能とをもっている。
【０１９１】
セクション生成部３０５は、制御部３０４から受けた固定パラメータp,dに基づいて、１変数多項式生成部３０６により生成した２つの１変数多項式ux(t),uy(t)からセクションＤ:(x,y,t)＝(ux(t),uy(t),t)を生成して制御部３０４に送出する機能をもっている。
【０１９２】
１変数多項式生成部３０６は、セクション生成部３０５から受けた固定パラメータp,dに基づいて、素体Fp上の次数dの１変数多項式ux(t),uy(t)を生成し、これら１変数多項式ux(t),uy(t)をセクション生成部３０５に送出する機能をもっている。
【０１９３】
代数曲面生成部３０７は、制御部３０４から受けたセクションＤ、システムパラメータdegt X’, Λx及び素数pに基づいて、定数項以外の項の係数をランダムに生成することにより定数項以外の項を生成する機能と、多項式演算部３０８を用い、定数項以外の項にセクションＤを代入して負の符号を付した定数項とを生成し、代数曲面Xの次数degt X ＝ max{degt X’, deg a00(t)}を決定し、定数項以外の項及び定数項からなるファイブレーションX(x,y,t)である代数曲面Xを生成する機能と、この代数曲面Xを制御部３０４に送出する機能と、をもっている。
【０１９４】
パラメータ生成部３０９は、識別多項式のパラメータdegt f, Λfをdegt X, ΛXに基づいて条件(4)の範囲でランダムに生成する機能と、ΛfΛXを計算し、平文多項式の係数集合Λmをその部分集合で且つ条件(4)を満たす範囲で決定する機能と、平文多項式の次数degt mを、degt X ＜degt m ＜ degt f の範囲で決定する機能と、前述したパラメータに基づいて、集合Λfに含まれる各要素(i,j)に対するdeg fij(t)を決定し、識別多項式のフレームＦRfを決定する機能とをもっている。
【０１９５】
フレーム生成部３１０は、生成された代数曲面から係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出し、この係数集合ΛX及び係数の次数deg aij(t)から代数曲面のフレームＦRXを生成する機能と、各フレームＦRf，ＦRXを互いに積算してフレームＦRg（＝ＦRf ＦRX）を生成する機能と、平文多項式の係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij}に決定する機能とをもっている。
【０１９６】
多項式演算部３０８は、代数曲面生成部３０７に制御され、多項式演算を実行し、演算結果を代数曲面生成部３０７に送出する機能をもっている。
【０１９７】
平文多項式生成部３１１は、制御部３０４から受けた平文多項式の係数集合Λm及び係数の次数deg mij(t)から定まる平文多項式のフレームＦRm及び素数pのデータと、メモリ３０２内のセクションとに基づいて、平文多項式の係数mijkを変数としてセクションを代入する機能と、代入した結果得られるmijkを順序付けした変数ベクトル(m000,m001,…,mijk,…)とｔを変数とする多項式を行列生成部３１２に送出する機能と、行列生成部３１２から受けた係数行列Ａの階数を計算するための指示を階数演算部３１３に送出する機能と、階数演算部３１３から受けた階数と変数ベクトルの次元数とを比較し、階数が変数ベクトルの次元数と一致するか否かを判定する機能と、この判定の結果、否であれば変数mijkの一部を定数として階数演算部３１３への指示をやり直す機能と、判定の結果、階数がベクトルの次元数が一致すれば平文多項式のフレームを制御部３０４に送出する機能とをもっている。
【０１９８】
行列生成部３１２は、平文多項式生成部３１１から変数ベクトル(m000,m001,…,mijk,…)及び平文多項式m(ux(t),uy(t),t)を受けると、m(ux(t),uy(t),t)を変数tに関して整理し、変数mijkを含む係数を変数ベクトルで表現した係数行列Ａを生成する機能と、係数行列Ａを平文多項式生成部３１１に送出する機能とをもっている。
【０１９９】
階数演算部３１３は、係数行列Ａの階数を計算するための指示を平文多項式生成部３１１から受けると、この指示に基づき、係数行列Ａの階数を計算して平文多項式生成部３１１に送出する機能をもっている。
【０２００】
出力部３１４は、平文多項式生成部３１１から受けた平文多項式m(x,y,t)のフレームを出力する機能をもっている。
【０２０１】
次に、以上のように構成された暗号装置、復号装置及び鍵生成装置の動作について図５乃至図８のフローチャートを用いて説明する。
【０２０２】
（暗号化処理）
暗号装置１００は、図５に示すように、入力部１０３から平文mを取得し（ＳＴ１）、入力部１０３から公開鍵としての代数曲面のファイブレーションX(x,y,t)、平文多項式m(x,y,t)のフレーム、識別多項式f(x,y,t)のフレームを取得すると（ＳＴ２）、処理を開始する。ここで、これらのフレームは、非零の項の集合と同一視できる集合Λm,Λfと、各項の係数の次数deg mij(t),deg fij(t)とから構成されている。また、システムパラメータである素体の標数pは、パラメータ格納部１０１から取得され（ＳＴ３）、平文埋め込み部１０４に送られる。
【０２０３】
平文埋め込み部１０４では、入力部１０３から受けた平文多項式のフレームに基づいて、別途、入力部１０３から受けた平文mを、m＝m00‖m10‖…‖mijのようにブロック分割する。ここで、L＝deg mij(t)としたとき、
｜mij｜≦（｜p｜−１）（L＋１）
とし、mij(t)のtkの係数mijkは上記mijを｜p｜−１ビット毎に分割したものとする。即ち、
mij＝mij0‖mij1‖…‖mijL
ここで｜p｜はpのビット長を表している。このようにして平文mを平文多項式m(x,y,t)の係数に埋め込む（ＳＴ４）。
【０２０４】
平文埋め込み部１０４は、平文多項式m(x,y,t)を暗号化部１０５に送出する。一方、入力部１０３は、公開鍵を暗号化部１０５に送出する。パラメータ格納部１０１はパラメータpを暗号化部１０５に送出する。
【０２０５】
暗号化部１０５では、平文多項式m(x,y,t)、パラメータp、公開鍵を受信すると、これらをメモリ１０２に書き込む。しかる後、暗号化部１０５は、メモリ１０２内の識別多項式f(x,y,t)のフレームと、パラメータpとを識別多項式生成部１０６に送出する。
【０２０６】
識別多項式生成部１０６は、識別多項式f(x,y,t)のフレームと、パラメータpとに基づいて、識別多項式f(x,y,t)をランダムに生成し（ＳＴ５）、得られた識別多項式f(x,y,t)を暗号化部１０５に送出する。
【０２０７】
暗号化部１０５は、この識別多項式f(x,y,t)をメモリ１０２に保存した後、３組以上の多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）を生成する指示を多項式生成部１０７に送出する。
【０２０８】
多項式生成部１０７では、ランダム値生成部１０８に対してランダム値の出力要請を繰り返し行い、その出力であるランダム値を利用して２ｋ個の多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）を生成する（ＳＴ６）。生成された多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）は、多項式生成部１０７から暗号化部１０５に送出される。
【０２０９】
暗号化部１０５は、受信した多項式ri(x,y,t),si(x,y,t)（i＝1,…,k）をメモリ１０２に保存した後、多項式演算部１０９に順次、多項式とその演算指示を送出しながらｋ個の暗号文Fi(x,y,t)（i＝1,…,k）を次式に基づいて計算する（ＳＴ７）。
【０２１０】
Fi(x,y,t)＝m(x,y,t)＋f(x,y,t)si(x,y,t)＋X(x,y,t)ri(x,y,t)
計算された暗号文Fi(x,y,t)（i＝1,…,k）は、暗号化部１０５によりメモリ１０２に保存される。
【０２１１】
しかる後、暗号化部１０５は、メモリ１０２内の暗号文Fi(x,y,t)（i＝1,…,k）を出力部１１０に送出する。出力部１１０はこの暗号文Fi(x,y,t)（i＝1,…,k）を（必要ならば予め定められたフォーマットに合わせて変形し）出力する（ＳＴ８）。
【０２１２】
以上により、暗号装置１００は暗号化処理を終了する。
【０２１３】
（復号処理）
復号装置２００においては、図６に示すように、入力部２０３から暗号文Fi(x,y,t)（i＝1,…,k）を取得し（ＳＴ１１）、入力部２０３から公開鍵X(x,y,t)と秘密鍵を取得し（ＳＴ１２）、パラメータ格納部２０１からpを取得することから処理を開始する。ここで、秘密鍵とはセクションＤである。取得された暗号文と鍵情報は復号部２０４に送られる。復号部２０４は、暗号文と鍵情報等をメモリ２０２に保存する。
【０２１４】
復号部２０４は、メモリ２０２内の暗号文Fi(x,y,t)（i＝1,…,k）とセクションＤをセクション代入部２０５に送出する。
【０２１５】
セクション代入部２０５は、セクションＤを暗号文Fi(x,y,t)（i＝1,…,k）に代入し、必要に応じて１変数多項式演算部２０６を利用することにより、hi(t)（i＝1,…,k）を得る（ＳＴ１３）。ここで、１変数多項式演算部２０６は１変数多項式の加減乗除演算を行う。得られたhi(t)（i＝1,…,k）は、セクション代入部２０５から復号部２０４に送出される。
【０２１６】
復号部２０４は、得られたｋ個の多項式hi(t)（i＝1,…,k）のうち、相異なる２つをＬ組抽出し、Ｌ組のhe(t),hw(t)（i＝1,…,e,…,w,…,k）のそれぞれを１変数多項式演算部２０６に送出する。１変数多項式演算部２０６は、Ｌ組のhe(t),hw(t)の一方から他方を減算して多項式gj(t)｛＝he(t)−hw(t)｝（j＝1,…,L）を生成し（ＳＴ１４）、減算結果の多項式gj(t)（j＝1,…,L）を復号部２０４に送出する。
【０２１７】
復号部２０４は、減算結果の多項式gj(t)（j＝1,…,L）を最大公約式演算部２０７に送出する。最大公約式演算部２０７は、減算結果の多項式gj(t)（j＝1,…,L）の最大公約式φ(t)を求め（ＳＴ１５）、最大公約式φ(t)を復号部２０４に送出する。
【０２１８】
復号部２０４は、最大公約式φ(t)を１変数多項式因数分解部２０８に送出する。１変数多項式因数分解部２０８は、この最大公約式φ(t)を因数分解し（ＳＴ１６）、因数分解の結果を因子の順序付けられた配列として復号部２０４に送出する。
【０２１９】
復号部２０４は、これらの因子の組合せのうち、次数が丁度deg f(ux(t),uy(t),t)となる全ての組合せを識別多項式の候補として抽出する（ＳＴ１７）。具体的には、復号部２０４は、配列として順序付けられた因子を順序の若いものから全ての組合せを順に求め、その中で次数が丁度deg f(ux(t),uy(t),t)となる組合せだけを抽出する手法が使用可能となっている。但し、この手法を実行する場合、因子の数をl個とすれば２lの組合せが存在する。そこで、この手法に加え、次数がdeg f(ux(t),uy(t),t)を超えた組合せに関してはそれ以上の因子を組合せないことにより、より短い処理時間で因子の組合せを抽出する。
【０２２０】
次に、復号部２０４は、識別多項式f(ux(t),uy(t),t)の候補を順に抽出し（ＳＴ１８）、順次、h1(t)と共に１変数多項式剰余演算部２０９に送出する。
【０２２１】
１変数多項式剰余演算部２０９は、次式に示すように、h1(t)を識別多項式f(ux(t),uy(t),t)の候補で割った余りを求めて（ＳＴ１９）、復号部２０４に送出する。
【０２２２】
m(ux(t),uy(t),t) ≡ h1(t) (mod f(ux(t),uy(t),t))
ここで、条件(6)よりdegm(ux(t),uy(t),t)＜deg f(ux(t),uy(t),t)であるため、正しいf(ux(t),uy(t),t)が求まっているという前提の下では正しいm(ux(t),uy(t),t)が求まることが分かる。
【０２２３】
次に、復号部２０４は、平文多項式m(x,y,t)
【数１９】
2010204466.tif 000021
【０２２４】
の係数mijkを変数とし、ステップＳＴ１９で求めたm(ux(t),uy(t),t)と、mijkux(t)iuy(t)jtkのtkにおける係数比較により、mijkを変数とする連立１次方程式を生成し、これを連立１次方程式求解部２１０に送出する。
【０２２５】
連立１次方程式求解部２１０では、この連立１次方程式を行列演算によって解き、解を復号部２０４に出力する。
【０２２６】
復号部２０４は、この解をメッセージの形に復元し、平文候補Mを生成する（ＳＴ２０）。この復元方法は前述の通りである。
【０２２７】
次に、復号部２０４は、平文候補Mを平文検査部２１１に送出する。平文検査部２１１は、平文候補Mに含まれている誤り検出符号を検査し（ＳＴ２１）、検査結果を復号部２０４に送出する。復号部２０４は、ステップＳＴ２１の検査結果が不合格を示す場合には、次の識別多項式の候補があるか否かを判定し（ＳＴ２２）、存在すれば次の識別多項式の候補をf(ux(t),uy(t),t)とおいて、ステップＳＴ１９〜ＳＴ２１を繰り返す（ＳＴ２３）。ステップＳＴ２２の判定の結果、識別多項式の候補が無い場合には、復号部２０４はエラーを出力して（ＳＴ２４）、処理を終了する。
【０２２８】
一方、ステップＳＴ２０の検査結果が合格を示す場合には、復号部２０４は平文候補Mを正しい平文mとして出力部２１２から出力する（ＳＴ２５）。
【０２２９】
以上により、復号装置２００は復号処理を終了する。
【０２３０】
（鍵生成処理）
始めに、代数曲面の生成を説明し、続いて平文多項式のフレームの生成について述べる。
【０２３１】
［代数曲面及びパラメータの生成］
鍵生成装置３００は、図７に示すように、システムパラメータdegt X’, Λxが入力部３０３から入力されると（ＳＴ３１）、処理を開始する。
【０２３２】
入力部３０３は、システムパラメータdegt X’, Λxを一時的にメモリ３０２に保存し、メモリ３０２内のシステムパラメータdegt X’, Λxを制御部３０４に送出する。
【０２３３】
制御部３０４は、システムパラメータdegt X’, Λxを受けると、固定パラメータ格納部３０１から固定パラメータである素数pとセクションの最大次数dを読み込むと（ＳＴ３２）、これら固定パラメータp,dをセクション生成部３０５に送出する。
【０２３４】
セクション生成部３０５は１変数多項式生成部３０６により、素体Fp上の次数dの１変数多項式ux(t),uy(t)を生成し、２つの１変数多項式ux(t),uy(t)からセクションＤ:(x,y,t)＝(ux(t),uy(t),t)を生成して制御部３０４に送出する（ＳＴ３３）。
【０２３５】
制御部３０４は、このセクションＤ、システムパラメータdegt X’, Λx及び素数pを代数曲面生成部３０７に送出する。
【０２３６】
代数曲面生成部３０７は、セクションＤ、システムパラメータdegt X’, Λx及び素数pを受けると、定数項以外のaij(t)をランダムに生成する（ＳＴ３４）。更に、代数曲面生成部３０７は、代数曲面Xの定数項以外の部分にセクションＤ:(x,y,t)＝(ux(t),uy(t),t)を代入し、代入結果に負の符号を付して定数項a00(t)を生成し（ＳＴ３５）、代数曲面Xの次数degt X ＝ max{degt X’, deg a00(t)}を決定する（ＳＴ３６）。
【０２３７】
これにより、代数曲面生成部３０７は、定数項以外の部分及び定数項a00(t)からなる代数曲面を生成する。尚、この計算の際には多項式演算部３０８に指示を送り加減乗算を行なう。また、ここで生成した代数曲面Xは、代数曲面XのうちのファイブレーションX(x,y,t)である。
【０２３８】
生成された代数曲面Xは、代数曲面生成部３０７から制御部３０４に送出される。制御部３０４は、代数曲面X及びセクションＤをメモリ３０２に書き込む。
【０２３９】
次に、鍵生成装置３００においては、パラメータ生成部３０９が、識別多項式のパラメータdegt f, Λfをdegt X, ΛXに基づいて条件(4)の範囲でランダムに生成する（ＳＴ３７）。次に、パラメータ生成部３０９は、ΛfΛXを計算し、平文多項式の係数集合Λmをその部分集合で且つ条件(4)を満たす範囲で決定する（ＳＴ３８）。ここで、条件(4)を満たす係数集合Λmが存在しない場合は、ステップＳＴ３７に戻り、パラメータdegt f, Λfの生成からやり直す。
【０２４０】
次に、パラメータ生成部３０９は、平文多項式の次数degt mを、degt X ＜degt m ＜ degt f の範囲で決定する（ＳＴ３９）。ここで、degt f ＝(degt X)＋１である場合など、この範囲の条件を満たすdegt mができないときは、ステップＳＴ３７に戻り、degt f, Λfの決定からやり直す。
【０２４１】
続いて、パラメータ生成部３０９は、前述したパラメータに基づいて、集合Λfに含まれる各要素(i,j)に対するdeg fij(t)を決定する（ＳＴ４０）。但し、要素(i,j)＝(degx f, degy f）の場合はdeg fij(t)＝degt fとし、それ以外の場合は０≦deg fij(t)≦degt fの範囲でランダムに生成する。これにより、パラメータ生成部３０９は、識別多項式のフレームＦRfを決定する（ＳＴ４１）。
【０２４２】
［平文多項式のフレームの生成］
鍵生成装置３００においては、図８に示すように、フレーム生成部３１０が、ステップＳＴ３６により生成された代数曲面から係数集合ΛXとΛXの要素(i,j)に対応する係数の次数deg aij(t)を抽出し（ＳＴ５１）、この係数集合ΛX及び係数の次数deg aij(t)から代数曲面のフレームＦRXを生成する（ＳＴ５２）。
【０２４３】
続いて、フレーム生成部３１０は、ステップＳＴ４１，ＳＴ５２で得られた各フレームＦRf，ＦRXを互いに積算してフレームＦRg（＝ＦRf ＦRX）を生成する（ＳＴ５３）。
【０２４４】
さらに、フレーム生成部３１０は、平文多項式の係数集合Λmに含まれる要素(i,j)に対応する係数の次数deg mij(t)をdeg mij(t)＝min{degt m, deg gij}に決定する（ＳＴ５４）。
【０２４５】
入力部３０３は、平文多項式の係数集合Λm及び係数の次数deg mij(t)を一時的にメモリ３０２に保存し、メモリ３０２内の平文多項式の係数集合Λm及び係数の次数deg mij(t)を制御部３０４に送出する。
【０２４６】
制御部３０４は、平文多項式の係数集合Λm及び係数の次数deg mij(t)を受けると、固定パラメータ格納部３０１から固定パラメータである素数pを読み込む。制御部３０４は、平文多項式の係数集合Λm、係数の次数deg mij(t)、及び素数pのデータを平文多項式生成部３１１に送出する。
【０２４７】
平文多項式生成部３１１は、この平文多項式の係数集合Λm及び係数の次数deg mij(t)から定まる平文多項式のフレームＦRmにメモリ３０２内のセクション(x,y,t)＝(ux(t),uy(t),t)を代入し、次式のm(ux(t),uy(t),t)を計算する（ＳＴ５５）。
【数２０】
2010204466.tif 000022
【０２４８】
ここで、mijkは変数である。平文多項式生成部３１１は、この変数mijkを順序付けして変数ベクトル(m000,m001,…,mijk,…)を生成し（ＳＴ５６）、これら変数ベクトル(m000,m001,…,mijk,…)及び１変数多項式m(ux(t),uy(t),t)を行列生成部３１２に送出する。
【０２４９】
行列生成部３１２は、m(ux(t),uy(t),t)を変数tに関して整理し、変数mijkを含む係数mijkux(t)iuy(t)jを変数ベクトル(m000,m001,…,mijk,…)で表現した係数行列Ａを生成する（ＳＴ５７）。具体的には、行列生成部３１２は、変数tに関して整理した多項式からtの係数mijkux(t)iuy(t)jとなる多項式を抽出し、変数ベクトル(m000,m001,…,mijk,…)との積が丁度tの係数mijkux(t)iuy(t)jとなるように係数行列を生成する。生成された係数行列Ａは、行列生成部３１２から平文多項式生成部３１１に送出される。
【０２５０】
平文多項式生成部３１１は、この係数行列Ａの階数を計算するための指示を階数演算部３１３に送出する。階数演算部３１３は、この指示に基づき、係数行列Ａの階数を計算して平文多項式生成部３１１に送出する（ＳＴ５８）。
【０２５１】
平文多項式生成部３１１は、この階数と変数ベクトルの次元数とを比較し、階数が変数ベクトルの次元数と一致するか否かを判定する（ＳＴ５９）。
【０２５２】
この判定の結果、否であれば一意解が得られないため、平文多項式生成部３１１は、変数mijkの一部を定数とし（ＳＴ６０）、ステップＳＴ４７の階数の計算からやり直す。また、ステップＳＴ４８の判定の結果、階数がベクトルの次元数と一致すれば一意解が得られるため、１変数多項式m(ux(t),uy(t),t)に対応する平文多項式m(x,y,t)のフレームを制御部３０４に出力する。
【０２５３】
制御部３０４は、平文多項式m(x,y,t)のフレームを出力部３１４から出力する（ＳＴ６１）。
【０２５４】
以上により、鍵生成装置３００は鍵生成処理を終了する。
【０２５５】
上述したように本実施形態によれば、高い次数の多項式｛h1(t)−h2(t)｝を因数分解して因数を抽出した従来とは異なり、高い次数の多項式hi(t)から低い次数の最大公約式φ(t)を求め、低い次数の最大公約式φ(t)を因数分解して因数を抽出するための暗号装置、復号装置及び鍵生成装置を実現させている。
【０２５６】
従って、代数曲面を用いた公開鍵暗号方式において、低い次数の最大公約式φ(t)を用いて因数分解処理と因数抽出処理の負荷を低減することにより、復号処理の効率化を実現することができる。
【０２５７】
＜第１の実施形態のバリエーション＞
第１のバリエーションに関しては、暗号化部１０５がステップＳＴ７において(7)式に代えて、例えば次式に基づいて暗号文を作成することにより実現できる。
【０２５８】
F(x,y,t)＝m(x,y,t)−f(x,y,t)s(x,y,t)−X(x,y,t)r(x,y,t)
一方、復号処理に関しても本バリエーションにおける暗号化演算に併せて自明に変形すれば実現できる。
【０２５９】
第２のバリエーションに関しては、暗号装置１００の識別多項式生成部１０６に既約性を判定する既約性判定機能を付加し、ステップＳＴ５により生成した識別多項式f(x,y,t)について既約多項式か否かを判定すると共に、既約多項式でない場合には、再度、ステップＳＴ５の処理を繰り返すことにより実現できる。なお、既約性の判定としては、例えば識別多項式f(x,y,t)について因数分解可能か否かを判定し、判定結果が因数分解可能であれば既約多項式でないと判定して当該識別多項式を破棄し、判定結果が否であれば当該識別多項式を既約多項式であると判定すればよい。
【０２６０】
第３のバリエーションに関しては、暗号化処理におけるステップＳＴ４の平文mを平文多項式m(x,y,t)に埋め込む処理に代えて、平文埋め込み部１０４が平文mを平文多項式m(x,y,t)の係数と識別多項式f(x,y,t)の係数とに分担して埋め込む処理を実行すれば実現できる。この場合、復号処理においては、平文多項式m(x,y,t)の係数を変数として平文多項式m(ux(t),uy(t),t)と平文多項式の候補Mとの係数比較により生じる連立１次方程式を解くことで平文候補Mを生成して平文mを求めたのと同じ処理を識別多項式f(x,y,t)について実行すればよい。すなわち、復号処理においては、平文多項式からの復号処理と同様に、識別多項式f(x,y,t)の係数を変数として識別多項式f(ux(t),uy(t),t)と識別多項式の候補Mとの係数比較により生じる連立１次方程式を解くことで平文候補Mを生成して平文mを求めればよい。更に第２のバリエーションと併用する場合、識別多項式f(x,y,t)に平文mを埋め込む際には、f(x,y,t)の一部の係数に埋め込むと共に、残りの係数で既約多項式となるように調整する方法を実行すればよい。
【０２６１】
第４のバリエーションに関しては、多項式生成部１０７がステップＳＴ６において、多項式r(x,y,t),s(x,y,t)を生成する際に、X(x,y,t)r(x,y,t)と、f(x,y,t)s(x,y,t)とがx,yの多項式として同じ同類項を含み、かつx,yの多項式の係数となるtを変数とする１変数多項式の次数を一致させる条件を満たすようにすればよい。この条件は、一方の多項式r(x,y,t)のフレームを識別多項式f(x,y,t)のフレームに一致させ、他方の多項式s(x,y,t)のフレームをファイブレーションX(x,y,t)のフレームに一致させるようにして、多項式r(x,y,t),s(x,y,t)を生成することにより満たすことができる。具体的には、識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように多項式r(x,y,t)を生成し、ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように多項式s(x,y,t)を生成すればよい。
【０２６２】
第５のバリエーションに関しては、復号処理のステップＳＴ１７とＳＴ１８との間において、図示しないカウンタの値ｋを０に設定し、ステップＳＴ２１の検査に合格した場合には当該平文候補Mをメモリ２０２に格納すると共に、カウンタの値ｋを“＋１”だけインクリメントし、次候補となるf(ux(t),uy(t),t)に対してステップＳＴ１９から同様の処理を行なう。次候補のf(ux(t),uy(t),t)が無くなった段階で、カウンタの値ｋが２以上か０の場合にはエラーを出力し、カウンタの値ｋが１の場合にはメモリ２０２内の平文候補Mを平文mとして出力する。第５のバリエーションは、以上のようにして実現できる。
【０２６３】
第６のバリエーションに関しては、復号処理のステップＳＴ１３〜ＳＴ２３（但し、ＳＴ２１は省略）をセクションＤの数だけ繰り返し、各セクションDl（l＝1,…,n）に対応した平文候補の集合Mlを求め、これらの集合Mlに含まれる平文候補をメモリ２０２に保存する。その後、平文候補集合Mlに共通な平文候補を平文mとして出力部２１２に出力する。
【０２６４】
補足すると、第６のバリエーションのステップＳＴ１３においては、セクション代入部２０５は、入力された暗号文Fi(x,y,t)（i＝1, …, k）のそれぞれに対し、各セクションDl（l＝1,…,n）を代入してそれぞれｋ個の１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}を生成する。これら１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}は、セクション代入部２０５から復号部２０４に送出される。
【０２６５】
ステップＳＴ１４においては、復号部２０４は、各１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}を１変数多項式演算部２０６に送出して減算させることにより、各１変数多項式{h11(t),h21(t),…,hk1(t)},…,{h1n(t),h2n(t),…,hkn(t)}に関し、それぞれ互いに減算した減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)},…を示す多項式gl(t)（＝{hi1l(t)−hi2l(t)}）（i1,i2 ∈ i、i1≠i2、l＝1, …, n）を得る。
【０２６６】
ステップＳＴ１５においては、復号部２０４は、減算結果を示す多項式gl(t)（l＝1, …, n）を最大公約式演算部２０７に送出して多項式gl(t)（l＝1, …, n）の最大公約式φl(t)を算出させることにより、最大公約式φl(t)を得る。
【０２６７】
ステップＳＴ１６においては、復号部２０４は、最大公約式φl(t)を１変数多項式因数分解部２０８に送出して因数分解させる。
【０２６８】
１変数多項式因数分解部２０８は、因数分解の結果を因子の順序付けられた配列として復号部２０４に送出する。
【０２６９】
ステップＳＴ１７においては、復号部２０４は、因数分解の結果により生じた因子を組合せることによって丁度deg f(uxl(t),uyl(t),t)を次数に持つ全ての識別多項式候補f(uxl(t),uyl(t),t)を抽出する。
【０２７０】
ステップＳＴ１８においては、復号部２０４は、識別多項式f(uxl(t),uyl(t),t)の候補を順に抽出し、順次、h11(t),…,h1n(t)と共に１変数多項式剰余演算部２０９に送出する。
【０２７１】
ステップＳＴ１９においては、１変数多項式剰余演算部２０９は、１変数多項式h11(t),…,h1n(t)をそれぞれ識別多項式候補f(uxl(t),uyl(t),t)で除算し、剰余として得られた平文多項式候補m(uxl(t),uyl(t),t)を復号部２０４に送出する。
【０２７２】
復号部２０４は、前述同様に、平文多項式候補m(uxl(t),uyl(t),t)と、前記平文多項式m(x,y,t)の予め公開されたフレームとに基づいて当該平文多項式m(x,y,t)の係数を変数とする連立１次方程式を導く。
【０２７３】
ステップＳＴ２０においては、この連立１次方程式を連立１次方程式求解部２１０が解くことにより、この解から復号部２０４が平文候補Mlを生成する。この平文候補Mlは、復号部２０４から平文検査部２１１に送出される。
【０２７４】
ステップＳＴ２１においては、平文検査部２１１は、１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(uxl(t),uyl(t),t)から得られたｎ個の平文候補Mlにおいて共通した平文候補Mがあるか否かを判定する。
【０２７５】
ステップＳＴ２５においては、復号部２０４は、平文検査部２１１による判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力部２１２から出力する。
【０２７６】
第６のバリエーションは、以上のようにして実現できる。尚、複数の平文候補がある場合、エラー出力してもよいが、この場合には第５のバリエーションと併用して複数の平文候補に誤り検出符号の検査を用いて平文候補を絞ることにより、エラー出力を回避して実施できる可能性が高い。
【０２７７】
第７のバリエーションに関しては、暗号化処理において、m(x,y,t), ri(x,y,t), si(x,y,t), f(x,y,t)と公開鍵X(x,y,t)を用いて暗号化する際に、少なくとも１つの暗号文を式(7)に従って計算し、それ以外の暗号文は式(7)において平文多項式m(x,y,t)を加算しない式
Fi(x,y,t)＝            f(x,y,t)si(x,y,t)＋X(x,y,t)ri(x,y,t) 
に従って計算する。また、復号処理においては、図９にバリエーションの処理を破線で囲んで示すように、前述したステップＳＴ１２の後、セクション代入部２０５で暗号文Fi(x,y,t)（i＝1,…,k）にセクションＤを代入し、この暗号文Fi(ux(t),uy(t),t)に対応する多項式hi(t)（＝Fi(ux(t),uy(t),t)）を得ると（ＳＴ１３）、平文多項式が加算されていない暗号文Fi(ux(t),uy(t),t)（i＝1,…,k）については、前述したhi(t)をgj(t)としてメモリ２０２に保存する（ＳＴ１４ｖ１）。また、平文多項式が加算されている暗号文Fi(ux(t),uy(t),t)（i＝1,…,k）の多項式hi(t)については、多項式hi(t)の中から、相異なる２つの多項式he(t)，hw(t)を複数組抽出し、各組のhe(t)，hw(t)を１変数多項式演算部２０６に送信して一方の多項式he(t)から他方の多項式hw(t)を減算し、複数の減算結果をgj(t)としてメモリ２０２に保存する（ＳＴ１４ｖ２）。これらステップＳＴ１４ｖ１，ＳＴ１４ｖ２の実行順序は逆でもよい。いずれにしてもステップＳＴ１４ｖ１，ＳＴ１４ｖ２の後、前述した通り、ステップＳＴ１５以降の処理が実行される。
【０２７８】
第８のバリエーションに関しては、復号処理において、図１０にバリエーションの処理を破線で囲んで示すように、前述したステップＳＴ１５によって復号部２０４が最大公約式φ(t)を得た後に、最大公約式φ(t)の次数deg φ(t)と、識別多項式f(ux(t),uy(t),t)の次数deg f(ux(t),uy(t),t)とを復号部２０４が比較する処理（ＳＴ１５ｖ）を付加し、両者が一致した場合（ＳＴ１５ｖ：ＹＥＳ）には、f(ux(t),uy(t),t)＝φ(t)として、復号部２０４がh1(t)のf(ux(t),uy(t),t)による剰余を求める処理（ＳＴ１９）に進む。両者が一致しなかった場合（ＳＴ１５ｖ：ＮＯ）には、前述した通り、復号部２０４がステップＳＴ１６に進み、最大公約式φ(t)の因数分解処理以降の処理を順次実行する。
【０２７９】
（第２の実施形態の具体的な構成）
以下、本発明の第２の実施形態について具体的に説明する。図１１は本発明の第２の実施形態に係る暗号装置の全体構成図であり、図１２は同実施形態における復号装置の全体構成図であって、図２及び図３と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。また、本実施形態の鍵生成装置３００は、第１の実施形態に述べた通りである。
【０２８０】
ここで、本実施形態の暗号装置２００は、図２に示した暗号化部１０５に代えて、暗号化部１０５’を備えている。
【０２８１】
暗号化部１０５’は、入力部１０３から受けた公開鍵及びパラメータ格納部１０１内のパラメータpに基づいて、図１３のＳＴ５〜ＳＴ８ｖに示す動作を実行するように、各部１０２，１０６〜１０９を制御する機能をもっている。
【０２８２】
本実施形態の復号装置２００は、図３に示した復号部２０４及び最大公約式演算部２０７に代えて、復号部２０４’を備えている。
【０２８３】
復号部２０４’は、入力部２０４から受けた暗号文F1(x,y,t),F2(x,y,t)、公開鍵x(x,y,t)及びセクションＤと、パラメータ格納部内のパラメータpとに基づいて、図１４のＳＴ１３ｖ１〜ＳＴ１７及び図６のＳＴ１７〜ＳＴ２５に示した動作を実行するように各部２０２，２０５〜２１２を制御する機能をもっている。
【０２８４】
次に、以上のように構成された暗号装置及び復号装置の動作について図１３及び図１４のフローチャートを用いて説明する。
【０２８５】
（暗号化処理）
暗号装置１００は、図１３に本実施形態固有の処理を破線で囲んで示すように、前述したステップＳＴ５の後、暗号化部１０５’が識別多項式f(x,y,t)をメモリ１０２に保存した後、２組の多項式ri(x,y,t),si(x,y,t)（i＝1,2）を生成する指示を多項式生成部１０７に送出する。
【０２８６】
多項式生成部１０７では、ランダム値生成部１０８によるランダム値を利用して４個の多項式r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)を生成する（ＳＴ６ｖ）。生成された多項式r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)は、多項式生成部１０７から暗号化部１０５’に送出される。
【０２８７】
暗号化部１０５’は、受信した多項式r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をメモリ１０２に保存した後、多項式演算部１０９に順次、多項式とその演算指示を送出しながら２個の暗号文F1(x,y,t), F2(x,y,t)を次式に基づいて計算する（ＳＴ７ｖ１，ＳＴ７ｖ２）。
【０２８８】
F1(x,y,t)＝m(x,y,t)＋f(x,y,t)s1(x,y,t)＋X(x,y,t)r1(x,y,t)
F2(x,y,t)＝            f(x,y,t)s2(x,y,t)＋X(x,y,t)r2(x,y,t)
計算された暗号文F1(x,y,t), F2(x,y,t)は、暗号化部１０５’によりメモリ１０２に保存される。
【０２８９】
しかる後、暗号化部１０５’は、メモリ１０２内の暗号文F1(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を取得することから処理を開始する。取得された暗号文と鍵情報は復号部２０４’に送られる。復号部２０４’は、暗号文と鍵情報等をメモリ２０２に保存する。
【０２９２】
復号部２０４’は、メモリ２０２内の暗号文F1(x,y,t),F2(x,y,t)とセクションＤをセクション代入部２０５に送出する。
【０２９３】
セクション代入部２０５は、順次、セクションＤを暗号文F1(x,y,t),F2(x,y,t)に代入し、必要に応じて１変数多項式演算部２０６を利用することにより、h1(t),h2(t)を得る（ＳＴ１３ｖ１，ＳＴ１３ｖ２）。ここで、１変数多項式演算部２０６は１変数多項式の加減乗除演算を行う。得られたh1(t),h2(t)は、セクション代入部２０５から復号部２０４に送出される。
【０２９４】
復号部２０４’は、得られた多項式h1(t),h2(t)のうち、m(ux(t),uy(t),t)を含まない多項式h2(t)を１変数多項式因数分解部２０８に送出する。１変数多項式因数分解部２０８は、この多項式h2(t)を因数分解し（ＳＴ１６ｖ）、因数分解の結果を因子の順序付けられた配列として復号部２０４’に送出する。以下の復号処理は前述した通りである。
【０２９５】
（鍵生成処理）
鍵生成装置３００による鍵生成動作は、第１の実施形態に述べた通りである。
【０２９６】
上述したように本実施形態によれば、暗号化処理において、従来とは異なり、平文多項式m(x,y,t)を用いずに第２の暗号文F2(x,y,t)を生成することから、平文多項式m(x,y,t)に対する加算又は減算処理を１回省略できるので、暗号処理における演算処理の負荷を低減でき、もって、処理全体の効率化を実現することができる。
【０２９７】
また、復号処理において、従来とは異なり、平文多項式m(x,y,t)を用いない第２の暗号文F2(x,y,t)から生成した多項式h2(t)を因数分解することから、従来の平文多項式m(ux(t),uy(t),t)をキャンセルするための減算処理｛h1(t)−h2(t)｝を省略して因数分解を実行できるので、復号処理における演算処理の負荷を低減でき、もって、処理全体の効率化を実現することができる。
【０２９８】
補足すると、本実施形態は、m(x,y,t)を含まない多項式h2(t)を１つだけ用いるので、前述した減算処理の省略に加え、第１の実施形態に述べた最大公約式φ(t)を求める処理をも省略できるので、より一層高速化を図ることができる。
【０２９９】
＜第２の実施形態のバリエーション＞
第１のバリエーションに関しては、暗号化部１０５’がステップＳＴ７ｖ１，ＳＴ７ｖ２の暗号文F1(x,y,t),F2(x,y,t)の生成時に、以下のように加算に代えて減算を用いることにより実現できる。
【０３００】
F1(x,y,t)＝m(x,y,t)−f(x,y,t)s1(x,y,t)−X(x,y,t)r1(x,y,t) 
F2(x,y,t)＝            f(x,y,t)s2(x,y,t)−X(x,y,t)r2(x,y,t) 
一方、復号処理に関しても本バリエーションにおける暗号化演算に併せて自明に変形すれば実現できる。具体的には、ステップＳＴ１３ｖ１，ＳＴ１３ｖ２で得られる１変数多項式h1(t), h2(t)が以下のようになる。なお、h2(t)は本実施形態と同じである。
【０３０１】
h1(t)＝F1(ux(t),uy(t),t)
＝m(ux(t),uy(t),t)−f(ux(t),uy(t),t)s1(ux(t),uy(t),t) 
h2(t)＝F2(ux(t),uy(t),t)
＝                     f(ux(t),uy(t),t)s2(ux(t),uy(t),t)
このように、第１のバリエーションに関しては、ステップＳＴ７ｖ１，ＳＴ７ｖ２，ＳＴ１３ｖ１，ＳＴ１３ｖ２の処理が若干異なるものの、他の処理を本実施形態と同様に実施して同様の効果を得ることができる。
【０３０２】
また、第２の実施形態は、第２、第３、第４又は第５のバリエーションを実施する場合には、第１の実施形態の各バリエーションと同様に各バリエーションを実施して前述した効果を得ることができる。
【０３０３】
また、第２の実施形態は、第６のバリエーションを実施する場合、復号処理のステップＳＴ１３ｖ１〜ＳＴ２３（但し、ＳＴ２１は省略）をセクションＤの数だけ繰り返し、各セクションDl（l＝1,…,n）に対応した平文候補の集合Mlを求め、これらの集合Mlに含まれる平文候補をメモリ２０２に保存する。その後、平文候補集合Mlに共通な平文候補を平文mとして出力部２１２に出力する。
【０３０４】
補足すると、第２の実施形態のステップＳＴ１３ｖ１，ＳＴ１３ｖ２においては、セクション代入部２０５は、入力された暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、各セクションDl（l＝1,…,n）を代入してそれぞれ２つの１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}を生成する。これら１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}は、セクション代入部２０５から復号部２０４’に送出される。
【０３０５】
ステップＳＴ１６ｖにおいては、復号部２０４’は、これら１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}のうち、m(uxl(t),uyl(t),t)を含まない多項式{h21(t),…,h2n(t)}を１変数多項式因数分解部２０８に送出する。１変数多項式因数分解部２０８は、この多項式{h21(t),…,h2n(t)}を因数分解し（ＳＴ１６ｖ）、因数分解の結果を因子の順序付けられた配列として復号部２０４’に送出する。以下の復号処理は、第１の実施形態の第６のバリエーションに述べた通りである。第６のバリエーションは、以上のようにして実現できる。
【０３０６】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０３０７】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０３０８】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０３０９】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０３１０】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０３１１】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０３１２】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０３１３】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０３１４】
【図１】一般的な代数曲線を説明するための模式図である。
【図２】本発明の第１の実施形態に係る暗号装置の全体構成図である。
【図３】同実施形態における復号装置の全体構成図である。
【図４】同実施形態における鍵生成装置の全体構成図である。
【図５】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図６】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図７】同実施形態における鍵生成装置の動作を説明するためのフローチャートである。
【図８】同実施形態における鍵生成装置の動作を説明するためのフローチャートである。
【図９】同実施形態における復号装置のバリエーションを説明するためのフローチャートである。
【図１０】同実施形態における復号装置の他のバリエーションを説明するためのフローチャートである。
【図１１】本発明の第２の実施形態に係る暗号装置の全体構成図である。
【図１２】同実施形態における復号装置の全体構成図である。
【図１３】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図１４】同実施形態における復号装置の動作を説明するためのフローチャートである。
【符号の説明】
【０３１５】
１，２，３…記憶媒体、１００…暗号装置、１０１，２０１…パラメータ格納部、１０２，２０２，３０２…メモリ、１０３，２０３，３０３…入力部、１０４…平文埋め込み部、１０５，１０５’…暗号化部、１０６…識別多項式生成部、１０７…多項式生成部、１０８…ランダム値生成部、１０９，３０８…多項式演算部、１１０，２１２，３１４…出力部、１１１，２１３，３１５…バス、２００…復号装置、２０４，２０４’…復号部、２０５…セクション代入部、２０６…１変数多項式演算部、２０７…最大公約式演算部、２０８…１変数多項式因数分解部、２０９…１変数多項式剰余演算部、２１０…連立１次方程式求解部、２１１…平文検査部、３００…鍵生成装置、３０１…固定パラメータ格納部、３０４…制御部、３０５…セクション生成部、３０６…１変数多項式生成部、３０７…代数曲面生成部、３０９…パラメータ生成部、３１０…フレーム生成部、３１１…平文多項式生成部、３１２…行列生成部、３１３…階数演算部。
【図１】
2010204466.tif 000023
【図２】
2010204466.tif 000024
【図３】
2010204466.tif 000025
【図４】
2010204466.tif 000026
【図５】
2010204466.tif 000027
【図６】
2010204466.tif 000028
【図７】
2010204466.tif 000029
【図８】
2010204466.tif 000030
【図９】
2010204466.tif 000031
【図１０】
2010204466.tif 000032
【図１１】
2010204466.tif 000033
【図１２】
2010204466.tif 000034
【図１３】
2010204466.tif 000035
【図１４】
2010204466.tif 000036