(57)【要約】【課題】代数曲面を用いた公開鍵暗号方式において、１変数多項式に起因した脆弱性を解消する。【解決手段】暗号装置１００は、メッセージmを３変数の平文多項式m(x,y,t)の係数として埋め込む平文埋め込み部１０４と、３変数の識別多項式f(x,y,t)を生成する識別多項式生成部１０６と、３変数の多項式r1(x,y,t),r2(x,y,t),s1(x,y,t),s2(x,y,t)をランダムに生成する多項式生成部１０７と、これら３変数の多項式同士を演算することにより、暗号文F1,F2を生成する暗号化部１０５とを備えている。このように３変数の平文多項式m(x,y,t)及び識別多項式f(x,y,t)を用いるので、１変数の平文多項式m(t)及び既約多項式f(t)を用いた従来とは異なり、上記課題を解決できる。【選択図】図２
2009116183.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)を生成する識別多項式生成手段と、
３変数の多項式r1(x,y,t),r2(x,y,t),s1(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)＝Epk(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)＝Epk(m,s2,r2,f,X)を生成する第２の暗号化手段と、
を備えたことを特徴とする暗号装置。
【請求項２】
請求項１に対応する暗号装置において、
前記平文埋め込み手段は、前記メッセージmを３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込むことを特徴とする暗号装置。
【請求項３】
請求項１又は請求項２に記載の暗号装置において、
前記多項式生成手段は、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式r1(x,y,t)を生成し、前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式s1(x,y,t)を生成する第１の多項式生成手段と、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式r2(x,y,t)を生成し、前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式s2(x,y,t)を生成する第２の多項式生成手段と、
を備えたことを特徴とする暗号装置。
【請求項４】
請求項１乃至請求項３のいずれか１項に記載の暗号装置において、
前記識別多項式生成手段は、識別多項式f(x,y,t)として生成する多項式の範囲を既約多項式となる範囲に更に制限することを特徴とする暗号装置。
【請求項５】
体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)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージ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)＝Epk(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)＝Epk(m,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)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、
前記減算結果{h1(t)−h2(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を平文として出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項６】
請求項５に記載の復号装置において、
前記メッセージ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,z)＝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)＝Epk(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)＝Epk(m,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)}に関し、それぞれ互いに減算した減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}を得る多項式減算手段と、
前記減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}をそれぞれ因数分解する因数分解手段と、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段と、
前記１変数多項式h11(t),…,h1n(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を生成する平文候補生成手段と、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(ux(t),uy(t),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を生成する第２の候補生成手段とを備えており、
前記共通候補判定手段は、
前記第１及び第２の候補生成手段により得られた各々の平文候補Mに共通した平文候補Mがあるか否かを判定することを特徴とする復号装置。
【請求項９】
体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)と、前記秘密鍵であるセクションとを生成するための鍵生成装置であって、
前記セクションをランダムに生成するセクション生成手段と、
前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段と、
前記定数項以外の項に前記セクションを代入して得られる代入結果に負の符号を付すことにより前記定数項を計算し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段と、
メッセージmを埋め込む平文多項式の形式を生成する場合、係数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)の形式を平文多項式の形式として出力する出力手段、
を備えたことを特徴とする鍵生成装置。
【請求項１０】
体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)の係数として埋め込む平文埋め込み手段、
前記係数が埋め込まれた平文多項式m(x,y,t)を前記暗号装置のメモリに書き込む手段、
前記平文多項式に前記セクションを代入したときに得られる１変数多項式の次数に比べ、前記セクションを代入したときに得られる１変数多項式の次数が大きくなる範囲で３変数の識別多項式f(x,y,t)を生成する識別多項式生成手段、
３変数の多項式r1(x,y,t),r2(x,y,t),s1(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)＝Epk(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)＝Epk(m,s2,r2,f,X)を生成する第２の暗号化手段、
として機能させるためのプログラム。
【請求項１１】
請求項１０に対応するプログラムにおいて、
前記平文埋め込み手段は、前記メッセージmを３変数の平文多項式m(x,y,t)の係数と３変数の識別多項式f(x,y,t)の係数とに分担して埋め込むように前記暗号装置を機能させることを特徴とするプログラム。
【請求項１２】
請求項１０又は請求項１１に記載のプログラムにおいて、
前記多項式生成手段は、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式r1(x,y,t)を生成し、前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式s1(x,y,t)を生成する第１の多項式生成手段、
前記識別多項式f(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式r2(x,y,t)を生成し、前記ファイブレーションX(x,y,t)の各項のx,yの次数と同一のx,yの次数を各項がもつように前記多項式s2(x,y,t)を生成する第２の多項式生成手段、
として前記暗号装置を機能させることを特徴とするプログラム。
【請求項１３】
請求項１０乃至請求項１２のいずれか１項に記載のプログラムにおいて、
前記識別多項式生成手段は、識別多項式f(x,y,t)として生成する多項式の範囲を既約多項式となる範囲に更に制限するように、因数分解可能な識別多項式f(x,y,t)を生成したときには当該識別多項式f(x,y,t)を破棄し、識別多項式f(x,y,t)の生成処理を再実行する手段として前記暗号装置を機能させることを特徴とするプログラム。
【請求項１４】
体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)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージ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)＝Epk(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)＝Epk(m,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)を前記復号装置のメモリに書き込む手段、
前記メモリ内の暗号文F1(x,y,t),F2(x,y,t)のそれぞれに対し、前記セクションを代入して２つの１変数多項式h1(t),h2(t)を生成するセクション代入手段、
前記各１変数多項式h1(t),h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段、
前記減算結果{h1(t)−h2(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を平文として出力する出力手段、
として機能させるためのプログラム。
【請求項１５】
請求項１４に記載のプログラムにおいて、
前記メッセージ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,z)＝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)＝Epk(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)＝Epk(m,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)を前記復号装置のメモリに書き込む手段、
前記メモリ内の暗号文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)}に関し、それぞれ互いに減算した減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}を得る多項式減算手段、
前記減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}をそれぞれ因数分解する因数分解手段、
前記因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する多項式抽出手段、
前記１変数多項式h11(t),…,h1n(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を生成する平文候補生成手段、
前記１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(ux(t),uy(t),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を生成する第２の候補生成手段として前記復号装置を機能させ、
前記共通候補判定手段は、
前記第１及び第２の候補生成手段により得られた各々の平文候補Mに共通した平文候補Mがあるか否かを判定する手段として前記復号装置を機能させることを特徴とするプログラム。
【請求項１８】
体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)と、前記秘密鍵であるセクションとを生成するための鍵生成装置に用いられるプログラムであって、
前記鍵生成装置を、
素数pとセクションの最大次数dとを格納する格納手段、
前記格納手段内の素数pと最大次数dとに基づいて、素体Fp上の次数dの１変数多項式ux(t),uy(t)を生成し、当該１変数多項式ux(t),uy(t)から前記セクション(ux(t),uy(t),t)を生成するセクション生成手段、
前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段、
前記定数項以外の項に前記セクションを代入して得られる代入結果に負の符号を付すことにより前記定数項を計算し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段、
係数mijkを変数とした平文多項式の基本形式を前記鍵生成装置のメモリに書き込む手段、
メッセージmを埋め込む平文多項式の形式を生成する場合、前記メモリ内の平文多項式の基本形式にセクションを代入するセクション代入手段、
前記代入した結果得られる変数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)の形式を平文多項式の形式として出力する出力手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号システムに用いられる暗号装置、復号装置、鍵生成装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワーク社会では、電子メール等の多くの情報がネットワーク上に伝送されることにより、人々のコミュニケーションが行われる。このようなネットワーク社会において、公開鍵暗号は情報の機密性や真正性を守る技術として広く活用されている。
【０００３】
代表的な公開鍵暗号としてはＲＳＡ暗号と楕円曲線暗号がある。これらの公開鍵暗号は、一般的な解読法が知られていないため、後述する量子計算機による解読法を除き、安全性に関する重大な問題が見つかっていない。他の公開鍵暗号としてはナップサック暗号と多次多変数暗号などがある。しかしながら、ナップサック暗号は有力な解読法があるため、安全性に疑問がある。多次多変数暗号は、鍵サイズの増大により、有力な攻撃方法を避けられる反面、鍵サイズが膨大になってしまう問題がある。
【０００４】
一方、ＲＳＡ暗号と楕円曲線暗号は量子計算機が出現すれば解読される可能性が高い。量子計算機は、現在の計算機とは異なり、量子力学におけるエンタングルメントという物理現象を利用して超並列計算を実行可能な計算機である。量子計算機は、実験レベルの仮想の計算機であるが、実現に向けて研究開発が進められている。１９９４年にショア(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)を生成する方式である。この方式は、後述する代数曲面上の求因子問題に安全性の根拠をおくので、解読が困難となっている。
【特許文献１】特開２００５−３３１６５６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、以上のような代数曲面を用いた公開鍵暗号は、平文多項式m(t)及び既約多項式f(t)の両方が１変数多項式となっている。このため、１変数多項式に秘密が隠されていることを攻撃者に積極的に利用されると解読される可能性があり、この意味で脆弱性が存在する。
【００１４】
本発明は上記実情を考慮してなされたもので、代数曲面を用いた公開鍵暗号方式において、１変数多項式に起因した脆弱性を解消し得る暗号装置、復号装置、鍵生成装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
第１の発明は、体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)を生成する識別多項式生成手段と、３変数の多項式r1(x,y,t),r2(x,y,t),s1(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)＝Epk(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)＝Epk(m,s2,r2,f,X)を生成する第２の暗号化手段と、を備えた暗号装置である。
【００１６】
第２の発明は、体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)に対応する１つ以上のセクションを秘密鍵とする公開鍵暗号方式が用いられ、前記メッセージ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)＝Epk(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)＝Epk(m,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)を互いに減算し、減算結果{h1(t)−h2(t)}を得る多項式減算手段と、前記減算結果{h1(t)−h2(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,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)と、前記秘密鍵であるセクションとを生成するための鍵生成装置であって、前記セクションをランダムに生成するセクション生成手段と、前記代数曲面のファイブレーションX(x,y,t)を変数x,yの多項式としてみたときに定数項以外の項の係数をランダムに生成することにより、定数項以外の項を生成する係数生成手段と、前記定数項以外の項に前記セクションを代入して得られる代入結果に負の符号を付すことにより前記定数項を計算し、前記定数項以外の項及び前記定数項からなるファイブレーションX(x,y,t)を生成するファイブレーション生成手段と、メッセージmを埋め込む平文多項式の形式を生成する場合、係数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)の形式を平文多項式の形式として出力する出力手段、を備えてもよい。
【００１８】
（作用）
第１及び第２の発明においては、１変数の平文多項式m(t)及び既約多項式f(t)を用いた従来とは異なり、３変数の平文多項式m(x,y,t)及び識別多項式f(x,y,t)を用いている。
【００１９】
また、第３の発明においては、１変数の平文多項式m(t)を用いた従来とは異なり、３変数の平文多項式m(x,y,t)を用いている。
【００２０】
従って、第１乃至第３の発明によれば、代数曲面を用いた公開鍵暗号方式において、１変数多項式に起因した脆弱性を解消することができる。
【発明の効果】
【００２１】
以上説明したように本発明によれば、代数曲面を用いた公開鍵暗号方式において、１変数多項式に起因した脆弱性を解消できる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の各実施形態について図面を用いて説明する。
【００２３】
各実施形態における代数曲面は体K上定義された連立(代数)方程式の解の集合のうち２次元の自由度を持ったものと定義される。例えば、次の式(1)に示す体K上の連立方程式は５つの変数を束縛する３つの方程式があることから、２次元の自由度を持っているので、代数曲面となる。
【数１】
2009116183.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)を次式のようにおく。
【数２】
2009116183.tif 000004
【００４０】
(iv) 連立方程式系を解く。
【００４１】
次に、代数曲面上の求セクション問題に基づく本実施形態の公開鍵暗号を具体的に説明する。
【００４２】
（第１の実施形態）
（概要）
本実施形態の公開鍵暗号は、以下の２つのシステムパラメータp,dを持っている。
【００４３】
1. 有限体のサイズ:p
2. （秘密鍵である）セクションの最高次数:d＝max{deg ux(t),deg uy(t)} (3)
また、公開鍵は、以下の３つである。
【数３】
2009116183.tif 000005
【００４４】
ここで、ΛAは多項式A(x,y,t)をx,yの多項式として見たときに係数が非零であるxの指数i、yの指数jの組の集合を意味する。また、これら形式は、集合Λm,Λfと、各項の係数の次数deg mij(t),deg fij(t)とから構成されている。
【００４５】
秘密鍵は、以下のセクションＤである。
【００４６】
1. Fp 上の代数曲面Xのセクション: Ｄ: (x,y,t)＝(ux(t),uy(t),t)
但し、公開鍵である代数曲面X は条件（４）を満たす。
【００４７】
degx X(x,y,t)＜degx m(x,y,t)
degy X(x,y,t)＜degy m(x,y,t)
degt X(x,y,t)＜degt m(x,y,t)      (4)
平文多項式と識別多項式は条件(5) を満たす。
【００４８】
degx m(x,y,t)＜degx f(x,y,t)
degy m(x,y,t)＜degy f(x,y,t)
degt m(x,y,t)＜degt f(x,y,t)      (5)
ここで、m(x,y,t),f(x,y,t)においては、上記不等式の右辺の次数を与える項がただ１つだけ存在し、同一である。即ち、f(x,y,t)を例に取って説明すると、f(x,y,t)には
【数４】
2009116183.tif 000006
【００４９】
の項がただ一つだけ存在する。ここでcは有限体Fpの元である。
【００５０】
これらは後述する方法（鍵生成方法）で容易に求めることができる。
【００５１】
暗号化処理の概要を述べる。暗号化処理ではまず暗号化したいメッセージ（以下では平文と呼ぶ）をブロック分割して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)に埋め込む。
【数５】
2009116183.tif 000007
【００５２】
尚、本実施形態のメッセージには誤り検出符号が含まれているとしている。誤り検出符号は送信上に生じたノイズなどの影響でメッセージの一部が毀損したときにそれを検出する機能を持つ。誤り検出符号として特にハッシュ関数によるハッシュ値を取ってもよい。
【００５３】
次に、Fp上の識別多項式f(x,y,t)を条件(5)を満たす定められた形式でランダムに生成する。続いて多項式r1(x,y,t),r2(x,y,t),s1(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)＝m(x,y,t)＋f(x,y,t)s2(x,y,t)＋X(x,y,t)r2(x,y,t)      (6)
各実施形態では安全性の観点から平文多項式と識別多項式を３変数としたため、対応する復号処理のために暗号文を２つとしている。
【００５５】
暗号文F1(x,y,t),F2(x,y,t)を受け取った受信者は所有する秘密鍵Ｄを利用して次のように復号を行う。まず、セクションＤを暗号文F(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)
＝m(ux(t),uy(t),t)＋f(ux(t),uy(t),t)s2(vx(t),vy(t),t)
という関係を持つ２つの式h1(t),h2(t) が求まることが分かる。次に、２式を辺々引き算して、次の式(7)を計算する。
【００５７】
h1(t)−h2(t)＝f(ux(t),uy(t),t){s1(ux(t),uy(t),t)−s2(ux(t),uy(t),t)}         (7)
次に、h1(t)−h2(t)を因数分解して、因子f(ux(t),uy(t),t) を求める。但し、因子f(ux(t),uy(t),t)は必ずしも既約因子とはならないため、複数の因子を次数が丁度deg f(ux(t),uy(t),t)となるように組合せる必要が生じる。ここで、識別多項式f(x,y,t)の形式は公開鍵として分かっているが、実際にどのような識別多項式を送信者が生成して暗号化したかは分からない。このため、f(x,y,t)の取り方によっては最高次の係数が零となり実際の次数が、前述した次数deg f(ux(t),uy(t),t)よりも小さくなる可能性がある。しかし、このようなことは条件(5)を満たす限り生じない。なぜなら条件(5)で保証されている項
【数６】
2009116183.tif 000008
【００５８】
となり、この項の次数は他の項の次数よりも真に大きいため、前述のように最高次の係数が零になることはない。
【００５９】
また、前述のように次数が丁度deg f(ux(t),uy(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)を超えた組合せに関してはそれ以上の因子を組合せないことによってより短い処理時間で抽出が可能である。
【００６１】
尚、ここでh1(t)−h2(t)の因数分解は、１変数多項式の因数分解が容易であることから十分有効な時間内に処理可能である。
【００６２】
次に、次式のように、h1(t)を識別多項式候補f(ux(t),uy(t),t)で割った余りとして平文多項式候補m(ux(t),uy(t),t)を求める。
【００６３】
m(ux(t),uy(t),t) ≡ h1(t) (mod f(ux(t),uy(t),t))
ここで、条件(5)よりdeg m(ux(t),uy(t),t)＜deg f(ux(t),uy(t),t)であるため、正しいf(ux(t),uy(t),t)が求まっているという前提の下では正しいm(ux(t),uy(t),t)が求まることが分かる。
【数７】
2009116183.tif 000009
【００６４】
とおき、平文候補多項式m(ux(t),uy(t),t)と、mijkux(t)iuy(t)jtkとが等しいことからtkの係数比較により、mijkを変数とする連立１次方程式が得られる。ここで、ΓAは多項式A(x,y,t)をx,y,tの多項式として見たときに係数が非零であるxの指数i、yの指数j、tの指数kの組の集合を意味する。
【００６５】
実際、
m(ux(t),uy(t),t)＝mijkux(t)i uy(t)j tk 
の両辺はmijk以外の変数はtのみであり、
【数８】
2009116183.tif 000010
【００６６】
であり、連立１次方程式
aτ(…,mijk,…)＝cτ(1≦τ≦K)
を得る。これを解くことによりmijkが求まる。ここで、式の個数と変数の個数の関係によってはmijkが一意的に定まらないこともある。この問題は公開鍵の１つである平文多項式の形式の定め方で解決するが、詳しくは鍵生成手法の部分で述べる。
【００６７】
しかし、識別多項式f(ux(t),uy(t),t)の候補が複数ある場合は必ずしも、ここで得られた平文が真の平文とは限らない。そこで、全ての識別多項式の候補f(ux(t),uy(t),t)から、前述した手法で抽出された平文について誤り検出符号によるチェックを行ない検査に成功（即ち、誤り検出符号によって誤りとならなかった）候補を平文とする。
【００６８】
この検査に成功した候補が１つも無かった場合は復号失敗として処理する。このような場合は理論的には有り得ないが、送信側の計算ミスや伝送路上での改竄などの何らかの理由により正しくない暗号文を受信したことより起こる可能性がある。
【００６９】
最後に本実施形態における鍵生成方法を説明する。本実施形態の鍵生成方法は代数曲面の生成方法、平文多項式の形式の生成手法、識別多項式の形式の生成手法に分かれる。
【００７０】
始めに、代数曲面の生成手法から説明する。
【００７１】
代数曲面の生成はセクションＤをランダムに選び、それに対応したファイブレーションを計算することによって行う。
【００７２】
まず、{deg ux(t),deg uy(t)}＝d となるようにセクションＤ＝(ux(t),uy(t),t)をランダムに決定する。ここで、dはシステムパラメータであり、求セクション問題の困難性を決めるパラメータである。
【００７３】
次に、代数曲面のファイブレーション
【数９】
2009116183.tif 000011
【００７４】
によって定数項a00(t)を決定する。以上によってＤをセクションとして含む代数曲面が生成できる。
【００７５】
次に、平文多項式の形式の生成手法を示す。本生成手法は予め定められた平文多項式の基本形式
【数１０】
2009116183.tif 000012
【００７６】
に対して、各mij(t)の次数を決定することで実行する。尚、ここでこの基本形式は条件(4)を満たし、その範囲で各mij(t)の次数も定められている。平文多項式m(x,y,t)の生成において重要な点はセクションによってできる連立１次方程式に一意解を持たせることである。このために、生成した代数曲面のセクション(x,y,t)＝(u(t),uy(t),t) に基づいて以下のような処理を行なう。まず、定められた基本形式にセクションを代入して、
【数１１】
2009116183.tif 000013
【００７７】
における変数tτの係数であり、有限体Fpの元である。また行列Ａは変数ベクトル(m000,m001,…,mijk,…)において変数mijkがΚ番目の要素として表現されている場合、行列Ａではtτの係数としてのmijkが非零の元として出現している場合は行列Ａの(τ,Κ)成分にその係数、出現しない場合は(τ,Κ)成分に０として表現された行列である。即ち、変数ベクトル(m000,m001,m002,m010,m011,m012)に対して
【数１２】
2009116183.tif 000014
【００７８】
となる。さて、本連立１次方程式が如何なるc0,c1,…,cKが生じても一意解を持つ必要十分条件は線形代数の理論によりベクトル(c0,c1,…,cK)の次元数が行列Ａの階数と等しくなることである。一方、本実施形態においては解があることが保証されているため、更に条件を弱めて「ベクトル(c0,c1,…,cK)の次元数Ｋ＋１が行列Ａの階数以上になること」とすることができる。
【００７９】
よって、行列Ａの階数を計算すると共に、その階数がベクトルの次元数Ｋ＋１を上回っているときはｔの上位次数に対応したmijkに零などの定数を代入して行列Ａの階数を段階的に引き下げていくことにより、一意性が達成できる。ここで０とした変数mijkには平文を埋め込むことができないため、各(i,j)において非零でよいmijkにおけるkの最大値を持ってmij(t)の次数と定める。このことにより、平文多項式の形式が定まる。但し、条件(4)を満たすためにいずれかのmij(t)の上位の項を非零とする必要がある。
【００８０】
識別多項式の形式の生成であるが、これは識別多項式の基本形式
【数１３】
2009116183.tif 000015
【００８１】
を条件(5)を満たす範囲で決定すればよい。
【００８２】
＜バリエーション＞
最後に本実施形態におけるいくつかのバリエーションを述べる。尚、以下ではr1(x,y,t),r2(x,y,t)を区別する必要がない共通の事象の場合には単にr(x,y,t)と書き、s1(x,y,t),s2(x,y,t)を区別する必要がない共通の事象の場合には単にs(x,y,t)と書くこととする。暗号文F1(x,y,t),F2(x,y,t)についても同様とする。
【００８３】
第１のバリエーションは、暗号化処理において、暗号文を生成する式(6)の変形に関するバリエーションである。式(6)は、例えば
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)の項と識別不能となるため、安全性が高まる。
【００８８】
第５のバリエーションは、復号処理において、正しい平文が２つ以上計算される場合に対応したものである。本実施形態では、式(7)からh1(t)−h2(t)を因数分解して、次数が丁度deg f(ux(t),uy(t),t)となるように因子を組合せることにより識別多項式f(ux(t),uy(t),t)の候補を得ている。次に、これに対応した平文候補Mを計算し、当該平文候補Mに含まれる誤り検出符号によって、当該平文候補が正しいものであるか否かを判定し、正しいと判定された場合には処理をそこで止めて、平文を出力していた。これに対し本バリエーションでは全ての識別多項式の候補から平文候補を計算し、前述した検査を行い、検査に成功（即ち、誤り検出符号で誤りが検出されなかった）平文候補のみを記録する。
【００８９】
このとき、全ての識別多項式の候補に伴う処理が終了した時点で、当該候補が複数ある場合や１つも無かった場合は復号失敗として処理する。このように構成することで、誤り検出符号の能力が低い場合や偶然の一致などによって平文が２つ以上計算されてしまう場合の誤りに備えることができる。
【００９０】
第６のバリエーションは、復号処理において、複数のセクションを利用する方式である。本実施形態では１つのセクションのみを利用していたが、複数のセクションを利用することにより誤り検出符号を用いることなく、正しい平文を計算することができる。複数のセクションを利用する場合はセクション毎に本実施形態の復号処理を行ない、出力された平文候補の集合の共通分となる平文を正しい平文として出力することができる。一方、更にセクションによっては（確率的にはほとんど無視できる範囲ではあるが）復号演算において、
s1(ux(t),uy(t),t)−s2(ux(t),uy(t),t)＝0
となり、平文候補が１つも求まらない可能性もある。このようなときにも本バリエーションは有用である。尚、第５のバリエーションと併せて実施することも可能である。
【００９１】
ここで、第６のバリエーションを実現するために複数のセクションを持つ代数曲面の生成手法を説明しなければならない。以下では２つのセクションＤ1,Ｄ2を持つ代数曲面を生成する鍵生成手法について述べる。
【００９２】
本鍵生成はセクションＤ1,Ｄ2をランダムに選び、それに対応したファイブレーションを計算することによって行う。但し、生成された代数曲面が２つのセクションを同時に持つようにするために以下のような工夫が必要となる。代数曲面（のファイブレーション）を次式のように書く。
【数１４】
2009116183.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)が消え、式(9)を得る。
【数１５】
2009116183.tif 000017
【００９４】
から多項式となるａ10(t)を生成するには、
ux(t)−vx(t)｜uy(t)−vy(t)
のように設定すれば十分である（なお、A｜Bの表記は、AがBを割り切ること、即ちBがAの倍数（倍式）であることを意味する）。このことは式(10)と
(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)を利用して式(9)に従ってａ10(t)を計算する。更に、
【数１６】
2009116183.tif 000018
【０１００】
などのようにxの因子とyの因子をランダムに両辺に分けて公開鍵暗号である代数曲面を生成することが望ましい。このように公開鍵と秘密鍵を生成することによって一般にｎ個以上のセクションを持つ代数曲面を生成することができる。
【０１０１】
＜安全性の検討＞
以下では本実施形態で構成した本発明の公開鍵暗号の安全性に関して考察する。
【０１０２】
［１］総当り攻撃
暗号文F(x,y,t)を構成する各要素m(x,y,t),f(x,y,t),s(x,y,t),r(x,y,t)をmijk,fijk,sijk,rijkを変数として
【数１７】
2009116183.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, 例４にあるように２変数以上の多項式では一般に除法の定理が成り立たないためである。
【０１０５】
［３］代入攻撃
［３−１］代数曲面上の代数曲線を代入する攻撃
（セクションを含む）代数曲線はωをパラメータとして、式(13)のように書ける。
【０１０６】
(x,y,t)＝(ux(ω),uy(ω),ut(ω))       (13)
これらの曲線のうち、代数曲面X(x,y,t)に含まれるものを見出すことができれば、セクションの代わりに代入して、セクションによる復号と同様の手法により、解読することができる。ここではこのような代数曲線を見出すことが与えられているセクションを見出すことと同等かそれ以上に計算困難であることを示す。このような曲線をdeg ut(ω)に注目して分類する。
【０１０７】
・ deg ut(ω)≧２の場合
この場合は一般の因子となり、求因子問題の困難性により脅威とはならない。
【０１０８】
・ deg ut(ω)＝１の場合
これが求まると線形変換でセクションが求まるため、求セクション問題が困難であるという仮定の下ではこのような代数曲線を求めることも困難となる。
【０１０９】
・ deg ut(ω)＝０の場合
これは特異ファイバー(singular fiber)と呼ばれるもので、ほとんど全ての代数曲面に存在する。しかし、一般の求因子問題の特別な場合であり、効率的に解く方法は知られていない。
【０１１０】
［３−２］代数曲面外の代数曲線を代入する攻撃
代数曲面外の代数曲線の場合も式(13)として書け、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を未知数として
【数１８】
2009116183.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)を暗号化部１０５に送出する機能とをもっている。
【０１２７】
多項式生成部１０７は、多項式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)を出力する機能をもっている。
【０１３１】
復号装置２００は、図３に示すように、パラメータ格納部２０１、メモリ２０２、入力部２０３、復号部２０４、セクション代入部２０５、１変数多項式演算部２０６、１変数多項式因数分解部２０７、１変数多項式剰余演算部２０８、連立１次方程式求解部２０９、平文検査部２１０及び出力部２１１が互いにバス２１２を介して接続されている。
【０１３２】
パラメータ格納部２０１は、復号部２０４から読出可能なメモリであり、システムパラメータである素体の標数pを格納している。
【０１３３】
メモリ２０２は、各部２０３〜２１１から読出／書込可能な記憶装置である。
【０１３４】
入力部２０３は、外部から入力された暗号文F1(x,y,t),F2(x,y,t)、公開鍵x(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)に代入して１変数多項式h1(t)を得る機能と、セクションＤを暗号文F2(x,y,t)に代入して１変数多項式h2(t)を得る機能と、得られたh1(t),h2(t)を復号部２０４に送出する機能とをもっている。
【０１３７】
１変数多項式演算部２０６は、セクション代入部２０５又は復号部２０４から受けた１変数多項式の加減乗除演算を実行する機能と、演算結果をセクション代入部２０５又は復号部２０４に送出する機能をもっている。
【０１３８】
１変数多項式因数分解部２０７は、復号部２０４から受けた減算結果｛h1(t)−h2(t)｝等の１変数多項式を因数分解する機能と、因数分解の結果を因子の順序付けられた配列として復号部２０４に送出する機能とをもっている。
【０１３９】
１変数多項式剰余演算部２０８は、復号部２０４から受けた被除多項式及び除多項式としての１変数多項式の剰余演算を実行する機能と、演算結果としての剰余を復号部２０４に送出する機能とをもっている。
【０１４０】
連立１次方程式求解部２０９は、復号部２０４から受けた連立１次方程式を行列演算によって解く機能と、得られた解を復号部２０４に送出する機能とをもっている。
【０１４１】
平文検査部２１０は、復号部２０４から受けた平文候補M内の誤り検出符号を検査する機能と、検査結果を復号部２０４に送出する機能とをもっている。
【０１４２】
出力部２１１は、復号部２０４から受けた平文mを出力する機能をもっている。
【０１４３】
鍵生成装置３００は、図４に示すように、固定パラメータ格納部３０１、メモリ３０２、入力部３０３、制御部３０４、セクション生成部３０５、１変数多項式生成部３０６、代数曲面生成部３０７、多項式演算部３０８、平文多項式生成部３０９、行列生成部３１０、階数演算部３１１及び出力部３１２が互いにバス３１３を介して接続されている。
【０１４４】
固定パラメータ格納部３０１は、制御部３０４から読出可能なメモリであり、固定パラメータである素数pとセクションの最大次数dを格納している。
【０１４５】
メモリ３０２は、各部３０３〜３１２から読出／書込可能な記憶装置である。
【０１４６】
入力部３０３は、外部から入力された代数曲面Xの基本形式又は平文多項式の基本形式を一時的にメモリ３０２に保存し、メモリ３０２内の代数曲面Xの基本形式又は平文多項式の基本形式を制御部３０４に送出する機能をもっている。
【０１４７】
制御部３０４は、入力部３０３から受けた代数曲面Xの基本形式と、固定パラメータ格納部３０１内の固定パラメータp,dとに基づいて、図７のＳＴ３４〜ＳＴ３７に示す動作を実行するように各部３０２，３０５〜３１２を制御する機能と、入力部３０３から受けた平文多項式の基本形式及びセクションと、固定パラメータ格納部３０１内の固定パラメータ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)をセクション生成部３０５に送出する機能をもっている。
【０１５０】
代数曲面生成部３０７は、制御部３０４から受けたセクションＤ、代数曲面の基本形式、並びに素数pに基づいて、定数項以外の項の係数をランダムに生成することにより定数項以外の項を生成する機能と、多項式演算部３０８を用い、定数項以外の項にセクションＤを代入して負の符号を付した定数項とを生成し、定数項以外の項及び定数項からなるファイブレーションX(x,y,t)である代数曲面Xを生成する機能と、この代数曲面Xを制御部３０４に送出する機能とをもっている。
【０１５１】
多項式演算部３０８は、代数曲面生成部３０７に制御され、多項式演算を実行し、演算結果を代数曲面生成部３０７に送出する機能をもっている。
【０１５２】
平文多項式生成部３０９は、制御部３０４から受けた平文多項式の基本形式及び素数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)をメモリ１０２に保存した後、多項式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)は、多項式生成部１０７から暗号化部１０５に送出される。
【０１６４】
暗号化部１０５は、受信した多項式r1(x,y,t),s1(x,y,t),r2(x,y,t),s2(x,y,t)をメモリ１０２に保存した後、多項式演算部１０９に順次、多項式とその演算指示を送出しながら第１の暗号文F1(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)
計算された第１の暗号文F1(x,y,t)は、暗号化部１０５によりメモリ１０２に保存される。  
同様に、暗号化部１０５は、第２の暗号文F2(x,y,t)を次式に基づいて多項式演算部１０９により計算し（ＳＴ８）、得られた第２の暗号文F2(x,y,t)をメモリ１０２に保存する。
【０１６６】
F2(x,y,t)＝m(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)を取得し（ＳＴ１１）、入力部２０３から公開鍵X(x,y,t)と秘密鍵を取得し（ＳＴ１２）、パラメータ格納部２０１からpを取得することから処理を開始する。ここで、秘密鍵とはセクションＤである。取得された暗号文と鍵情報は復号部２０４に送られる。復号部２０４は、暗号文と鍵情報等をメモリ２０２に保存する。
【０１６９】
復号部２０４は、メモリ２０２内の暗号文F1(x,y,t),F2(x,y,t)とセクションＤをセクション代入部２０５に送出する。
【０１７０】
セクション代入部２０５は、セクションＤを暗号文F1(x,y,t)に代入し、必要に応じて１変数多項式演算部２０６を利用することにより、h1(t)を得る（ＳＴ１３）。ここで、１変数多項式演算部２０６は１変数多項式の加減乗除演算を行う。得られたh1(t)は、セクション代入部２０５から復号部２０４に送出される。
【０１７１】
同様にセクション代入部２０５は、セクションＤを暗号文F2(x,y,t)に代入し、h2(t)を得る（ＳＴ１４）。得られたh2(t)は、セクション代入部２０５から復号部２０４に送出される。
【０１７２】
復号部２０４は、h1(t),h2(t)を１変数多項式演算部２０６に送出して減算させる。１変数多項式演算部２０６は、減算結果｛h1(t)−h2(t)｝を復号部２０４に送出する。
【０１７３】
復号部２０４は、減算結果｛h1(t)−h2(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))
ここで、条件(5) より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)
【数１９】
2009116183.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として出力部２１１から出力する。
【０１８４】
以上により、復号装置２００は復号処理を終了する。
【０１８５】
（鍵生成処理）
始めに、代数曲面の生成を説明し、続いて平文多項式の形式の生成について述べる。
【０１８６】
［代数曲面の生成］
鍵生成装置３００は、図７に示すように、代数曲面Xの基本形式が入力部３０３から入力されると（ＳＴ３１）、処理を開始する。代数曲面Xの基本形式とは
【数２０】
2009116183.tif 000022
【０１８７】
と数式で表現され、入力データとしてはΛXの要素と、ΛXの要素に対応する各係数aij(t)の次数とからなる。入力部３０３は、代数曲面の基本形式を一時的にメモリ３０２に保存し、メモリ３０２内の代数曲面の基本形式を制御部３０４に送出する。
【０１８８】
制御部３０４は、代数曲面の基本形式を受けると、固定パラメータ格納部３０１から固定パラメータである素数pとセクションの最大次数dを読み込むと（ＳＴ３２，ＳＴ３３）、これら固定パラメータp,dをセクション生成部３０５に送出する。
【０１８９】
セクション生成部３０５は１変数多項式生成部３０６により、素体Fp上の次数dの１変数多項式ux(t),uy(t)を生成し、２つの１変数多項式ux(t),uy(t)からセクションＤ:(x,y,t)＝(ux(t),uy(t),t)を生成して制御部３０４に送出する（ＳＴ３４）。
【０１９０】
制御部３０４は、このセクションＤと、メモリ３０２内の代数曲面の基本形式、並びに素数pを代数曲面生成部３０７に送出する。
【０１９１】
代数曲面生成部３０７は、セクションＤ、代数曲面の基本形式、並びに素数pを受けると、定数項以外のaij(t)をランダムに生成する（ＳＴ３５）。更に、代数曲面生成部３０７は、代数曲面の定数項以外の部分にセクションＤ:(x,y,t)＝(ux(t),uy(t),t)を代入し、代入結果に負の符号を付して定数項a00(t)を生成し（ＳＴ３６）、定数項以外の部分及び定数項a00(t)からなる代数曲面を生成する。尚、この計算の際には多項式演算部３０８に指示を送り加減乗算を行なう。また、ここで生成した代数曲面Xは、代数曲面XのうちのファイブレーションX(x,y,t)である。
【０１９２】
生成された代数曲面Xは、代数曲面生成部３０７から制御部３０４に送出される。制御部３０４は、代数曲面Xを出力部３１２から出力する（ＳＴ３７）。
【０１９３】
［平文多項式の形式の生成］
鍵生成装置３００は、図８に示すように、平文多項式m(x,y,t)の基本形式とセクション(x,y,t)＝(ux(t),uy(t),t)とが入力部３０３から入力されると（ＳＴ４１，ＳＴ４２）、処理を開始する。平文多項式の基本形式とは
【数２１】
2009116183.tif 000023
【０１９４】
と数式で表現され、入力データとしてはΛmの要素と、Λmの要素に対応する各係数mij(t)の次数とからなる。入力部３０３は、平文多項式の基本形式とセクションとを一時的にメモリ３０２に保存し、メモリ３０２内の平文多項式の基本形式を制御部３０４に送出する。
【０１９５】
制御部３０４は、平文多項式の基本形式を受けると、固定パラメータ格納部３０１から固定パラメータである素数pを読み込む（ＳＴ４３）。制御部３０４は、平文多項式の基本形式及び素数pのデータを平文多項式生成部３０９に送出する。
【０１９６】
平文多項式生成部３０９は、この平文多項式の基本形式にメモリ３０２内のセクション(x,y,t)＝(ux(t),uy(t),t)を代入し、次式のm(ux(t),uy(t),t)を計算する（ＳＴ４４）。
【数２２】
2009116183.tif 000024
【０１９７】
ここで、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)の形式を出力部３１２から出力する（ＳＴ５０）。
【０２０３】
以上により、鍵生成装置３００は鍵生成処理を終了する。
【０２０４】
上述したように本実施形態によれば、１変数の平文多項式m(t)及び既約多項式f(t)を用いた従来とは異なり、３変数の平文多項式m(x,y,t)及び識別多項式f(x,y,t)を用いた構成により、代数曲面を用いた公開鍵暗号方式において、１変数多項式に起因した脆弱性を解消することができる。
【０２０５】
＜本実施形態のバリエーション＞
第１のバリエーションに関しては、暗号化部１０７がステップＳＴ７，ＳＴ８において(6)式に代えて、例えば次式に基づいて暗号文を作成することにより実現できる。
【０２０６】
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として出力する。第５のバリエーションは、以上のようにして実現できる。
【０２１１】
第６のバリエーションに関しては、復号処理のステップＳＴ１３〜ＳＴ２２（但し、ＳＴ２０は省略）をセクションＤの数だけ繰り返し、各セクションDnに対応した平文候補の集合Mnを求め、これらの集合Mnに含まれる平文候補をメモリ２０２に保存する。その後、平文候補集合Mnに共通な平文候補を平文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)}は、セクション代入部２０５から復号部２０４に送出される。
【０２１３】
復号部２０４は、各１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}を１変数多項式演算部２０６に送出して減算させることにより、各１変数多項式{h11(t),h21(t)},…,{h1n(t),h2n(t)}に関し、それぞれ互いに減算した減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}を得る。
【０２１４】
ステップＳＴ１５においては、復号部２０４は、減算結果{h11(t)−h21(t)},…,{h1n(t)−h2n(t)}を１変数多項式因数分解部２０７に送出して因数分解させる。
【０２１５】
１変数多項式因数分解部２０７は、因数分解の結果を因子の順序付けられた配列として復号部２０４に送出する。
【０２１６】
ステップＳＴ１６においては、復号部２０４は、因数分解の結果により生じた因子を組合せることによって丁度deg f(ux(t),uy(t),t)を次数に持つ全ての識別多項式候補f(ux(t),uy(t),t)を抽出する。
【０２１７】
ステップＳＴ１７においては、復号部２０４は、識別多項式f(ux(t),uy(t),t)の候補を順に抽出し、順次、h11(t),…,h1n(t)と共に１変数多項式剰余演算部２０８に送出する。
【０２１８】
ステップＳＴ１８においては、１変数多項式剰余演算部２０８は、１変数多項式h11(t),…,h1n(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は、復号部２０４から平文検査部２１０に送出される。
【０２２１】
ステップＳＴ２０においては、平文検査部２１０は、１変数多項式h11(t),…,h1n(t)をそれぞれ除算して得られたｎ個の平文多項式候補m(ux(t),uy(t),t)から得られたｎ個の平文候補Mにおいて共通した平文候補Mがあるか否かを判定する。
【０２２２】
ステップＳＴ２４においては、復号部２０４は、平文検査部２１０による判定の結果、共通した平文候補Mがあった場合に当該共通した平文候補Mを平文として出力部２１１から出力する。
【０２２３】
第６のバリエーションは、以上のようにして実現できる。尚、複数の平文候補がある場合、エラー出力してもよいが、この場合には第５のバリエーションと併用して複数の平文候補に誤り検出符号の検査を用いて平文候補を絞ることにより、エラー出力を回避して実施できる可能性が高い。
【０２２４】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２２５】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０２２６】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０２２７】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０２２８】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０２２９】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０２３０】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２３１】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０２３２】
【図１】一般的な代数曲線を説明するための模式図である。
【図２】本発明の一実施形態に係る暗号装置の全体構成図である。
【図３】同実施形態における復号装置の全体構成図である。
【図４】同実施形態における鍵生成装置の全体構成図である。
【図５】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図６】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図７】同実施形態における鍵生成装置の動作を説明するためのフローチャートである。
【図８】同実施形態における鍵生成装置の動作を説明するためのフローチャートである。
【符号の説明】
【０２３３】
１，２，３…記憶媒体、１００…暗号装置、１０１，２０１…パラメータ格納部、１０２，２０２，３０２…メモリ、１０３，２０３，３０３…入力部、１０４…平文埋め込み部、１０５…暗号化部、１０６…識別多項式生成部、１０７…多項式生成部、１０８…ランダム値生成部、１０９，３０８…多項式演算部、１１０，２１１，３１２…出力部、１１１，２１２，３１３…バス、２００…復号装置、２０４…復号部、２０５…セクション代入部、２０６…１変数多項式演算部、２０７…１変数多項式因数分解部、２０８…１変数多項式剰余演算部、２０９…連立１次方程式求解部、２１０…平文検査部、３００…鍵生成装置、３０１…固定パラメータ格納部、３０４…制御部、３０５…セクション生成部、３０６…１変数多項式生成部、３０７…代数曲面生成部、３０９…平文多項式生成部、３１０…行列生成部、３１１…階数演算部。
【図１】
2009116183.tif 000025
【図２】
2009116183.tif 000026
【図３】
2009116183.tif 000027
【図４】
2009116183.tif 000028
【図５】
2009116183.tif 000029
【図６】
2009116183.tif 000030
【図７】
2009116183.tif 000031
【図８】
2009116183.tif 000032