説明

鍵生成装置、プログラム及び方法

【課題】秘密鍵が2つのセクションである場合に、生成される公開鍵のクラスの制限を除去し、制限されたクラスに基づく解読法を阻止する。
【解決手段】公開鍵の一部であるファイブレーションX(x, y, t)を生成する際に、ファイブレーションX(x, y, t)の形式にcijxiyjの項を含めた構成により、生成される公開鍵のクラスの制限を除去する。ここで、cijxiyjの項を含めた構成を実現させるため、cijxiyjの項を、一次の項及び定数項c00以外の項としている。そして始めに、cijxiyjの項をランダムに生成する。続いて、cijxiyjの項と、2つのセクションD1,D2内の1変数多項式とに基づいて一次の項の係数を生成する。最後に、cijxiyjの項と一次の項とに基づいて定数項c00を生成している。これにより、上記課題を解決する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、代数曲面を用いた公開鍵暗号の鍵生成装置、プログラム及び方法に係わり、例えば、代数曲面を用いた公開鍵暗号の鍵の安全性を向上し得る鍵生成装置、プログラム及び方法に関する。
【背景技術】
【0002】
ネットワーク社会では、電子メール等の多くの情報がネットワーク上に伝送されることにより、人々のコミュニケーションが行われる。このようなネットワーク社会において、公開鍵暗号は情報の機密性や真正性を守る技術として広く活用されている。
【0003】
代表的な公開鍵暗号には、RSA暗号と楕円曲線暗号がある。RSA暗号は、素因数分解問題の困難性を安全性の根拠としており、べき乗剰余演算を暗号化演算として用いている。楕円曲線暗号は、楕円曲線上の離散対数問題の困難性を安全性の根拠としており、楕円曲線上の点演算を暗号化演算に用いている。
【0004】
これらの公開鍵暗号は、特定の鍵(公開鍵)に関する解読法が提案されている一方、一般的な解読法が知られていない。しかしながら、RSA暗号と楕円曲線暗号は、いずれも量子計算機が出現すれば解読される可能性が高い。
【0005】
量子計算機は、現在の計算機とは異なり、量子力学におけるエンタングルメントという物理現象を利用して超並列計算を実行可能な計算機である。量子計算機は、実験レベルの仮想の計算機であり、実現に向けて研究開発が進められている。1994年にショア(Shor)は、量子計算機によれば、素因数分解や離散対数問題を効率的に解くアルゴリズムを構成できることを示した。
【0006】
これに対し、量子計算機が実現されても安全な公開鍵暗号が提案されてきている。一例として、量子公開鍵暗号が挙げられる。量子公開鍵暗号においては、現在の計算機では鍵生成が不可能な程に強力なナップサック暗号の鍵を量子計算機により生成する。しかし、量子公開鍵暗号は、現在の計算機では鍵生成が不可能なため、現時点では利用できない。
【0007】
一般に、安全な公開鍵暗号を提案する場合、予め素因数分解問題や離散対数問題などの計算困難な問題を見つける。次に、秘密鍵を知らずに暗号文を解読することを、当該計算困難な問題を解くことと等価になるように構成する。
【0008】
しかし、計算困難な問題を見つけても、その問題を安全性の根拠とする公開鍵暗号を容易に構成できる訳ではない。理由は、計算が困難すぎる問題の場合、鍵を生成する問題も困難になるので、鍵を生成できないためである。一方、鍵生成が可能な程度に容易な問題の場合、解読も容易になってしまう。
【0009】
従って、公開鍵暗号を構成するには、計算困難な問題を見つけると共に、この問題を、鍵生成が容易であるが、解読が容易でない問題に作り変える必要がある。現状は、この作り変えが困難なため、数えるほどの公開鍵暗号しか提案されていない。
【0010】
このような現状において、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であると共に、小電力環境での実現可能性がある公開鍵暗号方式として、代数曲面を用いた公開鍵暗号が本発明者により提案されている(例えば、特許文献1参照)。以下、代数曲面を用いた公開鍵暗号を代数曲面暗号とも呼ぶ。
【0011】
一方、公開鍵暗号の鍵の安全性を向上させるためには、生成される鍵のクラスに制限が無いことが望ましい。理由は、制限されたクラスに依存する鍵の性質又は特殊性に基づく解読法が将来見つかる可能性があるからである。
【特許文献1】特開2005−331656号公報
【発明の開示】
【発明が解決しようとする課題】
【0012】
本発明者の検討によれば、特許文献1記載の代数曲面暗号においても、解読法が将来見つかる可能性が存在する。例えば、特許文献1の第58〜第59段落では、2つのセクションD1,D2に対応して生成可能な代数曲面XのファイブレーションX(x, y, t)として、楕円曲面Et:y2+y=x3+a(t)x+b(t)が例に挙げられている。この楕円曲面Etは、本発明者によれば、次式に示すファイブレーションX(x, y, t)の一例である。
【数19】

【0013】
しかしながら、この式には、cijxiyjの項が含まれていないことから、生成される公開鍵(代数曲面XのファイブレーションX(x, y, t))のクラスに制限が生じると考えられる。なお、この考えは、特許文献1の第60段落にも同様の記載がある。いずれにしても、生成される公開鍵のクラスに制限があるため、制限されたクラスに基づく解読法が将来見つかる可能性を否定できない。
【0014】
従って、特許文献1記載の技術においては、制限されたクラスに基づく解読法を阻止する観点から、秘密鍵が2つのセクションである場合にも、生成される公開鍵のクラスの制限を除去することが望ましいと考えられる。
【0015】
本発明は上記実情を考慮してなされたもので、秘密鍵が2つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止し得る鍵生成装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【0016】
第1の発明は、公開鍵の一部であり、且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置であって、前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データが記憶された形式データ記憶手段と、
【数20】

【0017】
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定手段と、前記次数d 以下の,Fq上定義されたランダムな1変数多項式λx(t)を生成する第1の多項式生成手段と、前記1変数多項式λx(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λy(t)を生成する第2の多項式生成手段と、前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第3の多項式生成手段と、前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第4の多項式生成手段と、前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成手段と、前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(1,0))をランダムに生成する第5の多項式生成手段と、前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c10(t)を生成する第6の多項式生成手段と、
【数21】

【0018】
前記各1変数多項式ux(t), uy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成手段と、
【数22】

【0019】
前記各1変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成手段とを備えた鍵生成装置である。
【0020】
第2の発明は、第1の発明における一次の項c10(t)x に代えて一次の項c01(t)y を用いるように、第1の発明を変形した鍵生成装置である。
【0021】
なお、第1及び第2の発明は、装置として実現した場合を説明したが、これに限らず、プログラム、方法又はコンピュータ読み取り可能な記憶媒体、として実現してもよいことは言うまでもない。
【0022】
(作用)
第1及び第2の発明においては、公開鍵の一部であるファイブレーションX(x, y, t)を生成する際に、ファイブレーションX(x, y, t)の形式にcijxiyjの項を含めた構成により、生成される公開鍵のクラスの制限を除去することができる。
【0023】
ここで、cijxiyjの項を含めた構成を実現させるため、cijxiyjの項を、一次の項及び定数項c00以外の項としている。そして始めに、cijxiyjの項をランダムに生成する。続いて、cijxiyjの項と、2つのセクション内の1変数多項式とに基づいて一次の項の係数を生成する。最後に、cijxiyjの項と一次の項とに基づいて定数項c00を生成している。
【0024】
このような構成により、第1及び第2の発明においては、秘密鍵が2つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止することができる。
【発明の効果】
【0025】
以上説明したように本発明によれば、2つのセクションに対応して生成されるファイブレーションのクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止できる。
【発明を実施するための最良の形態】
【0026】
以下、本発明の各実施形態を図面を用いて説明する。その前に、各実施形態の前提として、代数曲面及び代数曲面上の求因子問題について述べる。
【0027】
本発明で述べる代数曲面は、体K上定義された連立(代数)方程式の解の集合のうち、2次元の自由度を持ったものと定義される。例えば、次の式(1)に示す体K上の連立方程式は、変数5つに対し、それらを束縛する3つの方程式があり、2次元の自由度を持っているので、代数曲面となる。
【0028】
1(x, y, z, v, w)
2(x, y, z, v, w)
3(x, y, z, v, w) (1)
特に、式(2)に示す如き、3変数のK上の代数方程式の解の集合として定義される空間もK上の代数曲面となる。
【0029】
f(x, y, z)=0 (2)
一方、代数曲線は、体K上定義された連立(代数)方程式の解の集合のうち、1次元の自由度を持ったものである。よって、例えば次式のように定義される。
【0030】
g(x, y)=0
本実施形態においては、式(2)のように1つの式で書ける代数曲面のみを扱うので、以下では式(2)を代数曲面の定義方程式のごとく扱う。
【0031】
体とは加減乗除が自由にできる集合であって、実数、有理数、複素数が該当するが、整数や行列など0以外に除算ができない元を含む集合は該当しない。
【0032】
体の中には有限体と呼ばれる有限個の元から構成される体がある。例えば素数pに対し、pを法とする剰余類Z/pZは体をなす。このような体は、素体と呼ばれ、Fpなどと書かれる。
【0033】
有限体にはこの他に素数の冪乗個の元を持つ体Fq(q=pr)がある。pは有限体Fqの標数、rは拡大次数と呼ばれる。但し、本実施形態では、有限体のうち、主に素体Fpのみを扱う。一般に、素体Fpのpは、素体Fpの標数と呼ばれる。
【0034】
一方、一般の有限体でも本発明は自明な変形を施すことによって同様に成立する。公開鍵暗号では、メッセージをデジタルデータとして埋め込む必要から有限体上で構成することが多い。このため、本実施形態においても同様に有限体(本実施形態では特に素体)Fp上で定義された代数曲面を扱う。
【0035】
代数曲面f(x, y, z)=0 上には、図1に示すように、通常、代数曲線D1,D2,Xt0,…が複数存在する。このような代数曲線は代数曲面上の因子と呼ばれる。一般に、代数曲面の定義式が与えられた時に(非自明な)因子を求める問題は、現代の数学においても未解決の難問であり、NP問題である多次多変数方程式の求解問題を解くか、総当りなどの原始的な方法を除けば一般的な解法は知られていない。特に、本実施形態では、有限体で定義された代数曲面を扱う。しかし、有限体で定義された代数曲面の場合、有理数体などの無限体(無限個の元からなる体)と比較して、因子を求めるための手掛かりが少ない。このため、有限体で定義された代数曲面上の因子を求める問題は、より難しい問題である。
【0036】
本実施形態では、この問題を代数曲面上の求因子問題もしくは単に求因子問題と呼び、代数曲面上の求因子問題に安全性の根拠をおく公開鍵暗号を構成する。
【0037】
さて、体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と表す。
【0038】
また、代数曲面Xのファイブレーションにおけるパラメータtに体Kの元t0を代入して得られる代数曲線は、ファイバーと呼ばれ、Xt0のように表される。ここで、ファイバーとセクションは共に代数曲面Xtの因子である。
【0039】
一般に、代数曲面のファイブレーションが与えられたとき、それに対応するファイバーは(tに体の元を代入することにより)直ちに求まる。一方、ファイブレーションに対応するセクションを求めることは、極めて難しい。この意味ではファイバーは自明な因子であり、セクションは非自明な因子であると言える。
【0040】
本発明の鍵生成方式を適用する公開鍵暗号は、代数曲面上の求因子問題のうち、特に、代数曲面XのファイブレーションXtが与えられたときにセクションを求める問題に安全性の根拠をおく。
【0041】
ファイブレーションからセクションを求めるには、現代の数学においても次の(i)(iv)の手順による方法しか知られていない。
【0042】
(i) セクション(ux(t), uy(t), t)を
degux(t) ≦ d,deguy(t) ≦ d
と仮定した上で、ux(t),uy(t)を次式のようにおく。
【0043】
x(t)=α0+α1+・・・+αdd
y(t)=β0+β1+・・・+βdd
(ii) ux(t),uy(t)をX(x, y, t)=0に代入して、次式を得る。
【数23】

【0044】
(iii) 上式の左辺を展開してtiの係数をα0,・・・,αd, β0,・・・,βdの関数ci0,・・・,αd, β0,・・・,βd)で表現し、次の連立方程式系を立てる。
【0045】
00,・・・,αd,β0,・・・,βd)=0
10,・・・,αd,β0,・・・,βd)=0

2d0,・・・,αd,β0,・・・,βd)=0
(iv) 連立方程式系を解く。
【0046】
(第1の実施形態)
(概要)
本実施形態の公開鍵は、以下の4つである。
【0047】
1. 素体の標数p
2. Fp上の代数曲面Xのファイブレーション: X(x, y, t)=0
3. Fp上の1変数既約多項式f(t)の次数l
4. (秘密鍵である)セクションにおける多項式ux(t), uy(t), vx(t), vy(t)の最大次数d
但し、lは代数曲面のファイブレーションX(x, y, t)とセクションの最大次数dの間に次の式(3)の関係を持つ。
【0048】
(degx X(x, y, t)+degy X(x, y, t))d+degt X(x, y, t) < l (3)
ここで、degx X(x, y, t)は、X(x, y, t)のxのみを変数と考えた時の次数(例えばdegx(x3y2t+xy5t6)=3)である。degy(X(x, y, t)), degt(X(x, y, t)) も同様の次数である。
【0049】
また、公開鍵のうち、素体の標数p及びセクションの最大次数dは、安全性のパラメータとしても考えられる。
【0050】
一方、秘密鍵は、以下の2つの異なるセクションD1,D2である。
【0051】
1. Fp上の代数曲面Xのセクション: D1:(x, y, t)=(ux(t), uy(t), t)
2. Fp上の代数曲面Xのセクション: D2:(x, y, t)=(vx(t), vy(t), t)
次に、本実施形態における鍵生成方法を説明する。この鍵生成方法は、セクションD1,D2をランダムに選び、セクションD1,D2に対応したファイブレーションXを計算することによって行う。但し、生成された代数曲面が2つのセクションを同時に持つようにするために以下のような工夫が必要となる。代数曲面(のファイブレーション)は、一般に、次式のように書ける。
【数24】

【0052】
ここで、cij(t)は1変数多項式である。
【0053】
まず、システムパラメータとして素体の標数pを決める。標数pが小さくても安全性に問題は生じない。さて、セクションD1,D2を次のようにおく。
1:(x, y, t)=(ux(t),uy(t),t),
2:(x, y, t)=(vx(t),vy(t),t)
続いて、これらのセクションを代数曲面Xに代入し、次の2つの式を得る。
【数25】

【0054】
関係式(5)から多項式となるc10(t)を生成するには、次式を設定すれば十分である(A|BはAがBを割り切ること、即ちBがAの倍数(倍式)であることを意味する。)。
【0055】
x(t)−vx(t)|uy(t)−vy(t)
この式は、関係式(5)と、次の2つの式から明らかである。
【0056】
(ux(t)−vx(t))|(ux(t)i −vx(t)i)
(uy(t)−vy(t))|(uy(t)j −vy(t)j)
以上のことを利用して以下に示すアルゴリズムで鍵生成を行うことができる。
始めに、λx(t)|λy(t)となる2つの多項式をランダムに選択する。
【0057】
具体的に、このような多項式の組を求めるには、例えばλx(t)をランダムに与えて、同じく次数d−deg λx(t)以下のランダムな多項式c(t)によってλy(t)=c(t)λx(t)を計算することにより、λy(t)を求めればよい。
【0058】
次に、λx(t)=ux(t)−vx(t), λy(t)=uy(t)−vy(t)とおき、多項式vx(t)をランダムに選択し、ux(t)=λx(t)+vx(t)を計算する。λx(t), vx(t)の次数はd 以下なので、ux(t)の次数もd 以下となる。
【0059】
同様に多項式vy(t)をランダムに選択し、uy(t)=λy(t)+vy(t)を計算する。同様に、λy(t), vy(t)の次数はd 以下なのでuy(t)の次数もd 以下となる。
【0060】
次に、定数項c00(t), 一次の項c10(t)x 以外の係数cij(t)((i, j)≠(0,0),(1,0))をランダムに生成し、前述したux(t), vx(t), uy(t), vy(t)及び式(4)に基づいて、一次の項の係数c10(t)を計算する。更に、次の式(6)を計算し、定数項c00(t)を得る。
【数26】

【0061】
(第1の実施形態の具体的な構成)
次に、本発明の第1の実施形態に係る鍵生成装置の具体的な構成とそのアルゴリズムについて説明する。尚、以下の説明は、理解を助けるための例として、具体的な数値や式を挙げて述べる。但し、これらの数値や式は、あくまでも理解を助けるための例であり、実際に使われる十分な安全性を持つ数値や式とは必ずしも一致していない。これは以下の各実施形態及び各バリエーションでも同様である。なお、必ずしも一致しない数値としては、例えばセクションの最大次数dなどが挙げられる。
【0062】
図2は本発明の第1の実施形態に係る鍵生成装置の全体構成図である。なお、この鍵生成装置10は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。これは以下の各実施形態の各装置10,30,40でも同様である。
【0063】
ここで、鍵生成装置10は、図2に示すように、パラメータ入力部11、制御部12、代数曲面決定部13、セクション生成部14、1変数多項式生成部15、1変数多項式演算部16、代数曲面生成部17、1変数既約多項式最小次数生成部18及び鍵出力部19を備えている。また、鍵生成装置10は、図示しないメモリ(ハードウェア資源)を有し、各部11〜19から入力データ、出力データ及び処理中のデータ等が適宜読出/書込可能となっている。なお、このことは他の各装置20,30でも同様である。
【0064】
ここで、パラメータ入力部11は、外部から入力されたパラメータp, dを一時的にメモリに記憶し、メモリ内のパラメータp, dを制御部12に送出する機能をもっている。
【0065】
制御部12は、後述する図4及び図5に示す動作を実行するように、各部11,13〜14,17〜19を制御する機能をもっている。
【0066】
代数曲面決定部13は、制御部12に制御され、図示しないメモリに記憶された後述する代数曲面テーブルT内の各形式データのいずれかをランダムに選択することにより、ファイブレーションX(x, y, t)の形式データを決定する機能をもっている。
【0067】
ここで、代数曲面の決定の手法としては、図3に示す如き、代数曲面形式テーブルTを用いる第1の方法と、変数x, yに関する総次数dcを決定し、その範囲で係数が0でない項をランダムに決定して生成する第2の方法が適宜、使用可能となっている。なお、本実施形態では第1の方法を用いている。
【0068】
第1の方法に関し、代数曲面形式テーブルTは、例えば、変数x, yに関する総次数dcと、代数曲面の定義式(形式データ)の候補とが互いに関連付けられてメモリに記憶されたものである。ここで、形式データは、ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表すものである。
【数27】

【0069】
但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる。なお、使用する次数の組合せ(i, j)の集合は、0でない項に対応している。
【0070】
形式データとしては、tの1変数多項式cij(t)を係数としたxijの多項式を表すデータであれば、任意のデータが使用可能となっている。
【0071】
第2の方法に関し、係数が0でない項の個数を予めプログラムに記述するか、パラメータとして入力するか、又は予めメモリに格納することにより、係数が0で無い項を効果的に決定できる。理由は、0でない項を制限することで代数曲面の定義式の形を簡略化でき、公開鍵サイズを削減可能なためである。
【0072】
セクション生成部14は、制御部12に制御され、1変数多項式生成部15及び1変数多項式演算部16を制御して各1変数多項式ux(t), vx(t), uy(t), vy(t)を得る機能と、これら1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成する機能をもっている。
【0073】
1変数多項式生成部15は、セクション生成部14又は代数曲面生成部17に制御され、指定された素数p 及び次数d に基づいて、ランダムな1変数多項式を生成する機能をもっている。このとき、1変数多項式生成部15は、d次未満の各項の係数を、有限体Fpの元として0 からp−1 までの範囲でそれぞれランダムに生成する。すなわち、各1変数多項式λx(t),λy(t)は、有限体Fp上定義されている。これに限らず、他の各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t), c10(t), c00(t)も、有限体Fp上定義されている。
【0074】
具体的には1変数多項式生成部15は、セクション生成部14に制御されるとき、次数d 未満のランダムな1変数多項式λx(t)を生成する機能と、1変数多項式λx(t)で割り切れる次数d 以下の1変数多項式λy(t)を生成する機能とをもっている。
【0075】
また、1変数多項式生成部15は、代数曲面生成部17に制御されるとき、決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である1変数多項式cij(t)(但し(i,j)≠(0,0),(1,0))をランダムに生成する機能をもっている。
【0076】
1変数多項式演算部16は、セクション生成部14又は代数曲面生成部17に制御され、受信した演算命令に基づいて、有限体Fp上の1変数多項式の加減乗除演算を実行する機能をもっている。
【0077】
具体的には1変数多項式演算部16は、セクション生成部14に制御されるとき、1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の2つの1変数多項式ux(t), vx(t)を生成する機能と、1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の2つの1変数多項式uy(t), vy(t)を生成する機能とをもっている。
【0078】
また、1変数多項式演算部16は、代数曲面生成部17に制御されるとき、各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、式(4)に示す一次の項の係数である1変数多項式c10(t)を生成する機能と、各1変数多項式ux(t), uy(t), cij(t), c10(t)に基づいて、式(6)に示す定数項である1変数多項式c00(t)を生成する機能とをもっている。
【0079】
代数曲面生成部17は、制御部12に制御され、1変数多項式生成部15及び1変数多項式演算部16を制御して各1変数多項式cij(t), c10(t), c00(t)を得る機能と、得られた各1変数多項式cij(t), c10(t), c00(t)を、決定された形式データに設定することにより、代数曲面XのファイブレーションX(x, y, t)を生成する機能とをもっている。
【0080】
1変数既約多項式最小次数生成部18は、制御部12に制御され、生成されたファイブレーションX(x, y, t)における各々の変数x, y, t の次数degx X(x, y, t), degy X(x, y, t), degt X(x, y, t)及び前記次数d に基づいて、(degX(x, y, t)+degy X(x, y, t))d+degt X(x, y, t) 以上となるように、暗号化用のランダム1変数多項式の最小次数lを定める機能をもっている。
【0081】
鍵出力部19は、公開鍵である代数曲面Xと、一変数既約多項式の最小次数lと、秘密鍵であるセクションD1,D2とを制御部12から受信し、これらの鍵データX,l,D1,D2を鍵出力装置10の外部に出力する機能をもっている。
【0082】
次に、以上のように構成された鍵生成装置の動作について図4及び図5のフローチャートを用いて説明する。
鍵生成装置10は、鍵生成のパラメータである素体の標数pとセクションの最大次数dがパラメータ入力部11に入力されると、処理を開始する。ここでは簡単のためp=2, d=3が入力されたとする(ST1)。
【0083】
パラメータ入力部11は、入力されたパラメータp, dを一時的にメモリに記憶し、メモリ内のパラメータp, dを制御部12に送信する。制御部12は、パラメータp, dを受けると、代数曲面決定部13に代数曲面の形式を出力する旨の指示を出す。
【0084】
代数曲面決定部13は、この指示により、メモリに記憶された代数曲面形式テーブルT内の各形式データのいずれかをランダムに選択することにより、代数曲面XのファイブレーションX(x, y, t)の形式を決定する(ST2)。ここでは、形式として、X(x, y, t)=x5+y5+c21(t)x2y+c10(t)x+c00(t)を決定したとする。
【0085】
代数曲面決定部13は、決定した代数曲面の形式データを制御部12に出力する。制御部12は、この代数曲面の形式データとパラメータp, dをセクション生成部14に送信する。
【0086】
セクション生成部14は、代数曲面の形式データとパラメータp, dに基づいて、セクションの生成を開始する。始めに、セクション生成部14は、素数pとセクションの最大次数d 未満の値を1変数多項式生成部15に送信し、1変数多項式の生成を要求する。
【0087】
1変数多項式生成部15は、この要求に基づいて、d次未満の1変数多項式λx(t)(=t2+1)をランダムに生成する(ST3)。このとき、1変数多項式生成部15は、d次未満の各項の係数を、有限体Fpの元として0 からp−1 までの範囲でそれぞれランダムに生成する。これにより、1変数多項式λx(t)が得られる。1変数多項式生成部15は、得られたλx(t)は、セクション生成部14に出力される。
【0088】
セクション生成部14では、前述同様に、素数pと、次数d−deg λx(t)とを1変数多項式生成部15に送信し、1変数多項式の生成を要求する。
【0089】
1変数多項式生成部15は、ステップST3と同様にして、次数d−deg λx(t)の1変数多項式c(t)(=t)をランダムに生成する(ST4)。得られたc(t)は、セクション生成部14に出力される。
【0090】
次に、セクション生成部14は、c(t)とλx(t)を1変数多項式演算部16に送信する。1変数多項式演算部16は、c(t)とλx(t)に基づいて、λy(t)=c(t)λx(t)を計算する(ST5)。このとき、1変数多項式演算部16は、有限体Fp上の1変数多項式の加減乗除演算を行ない、λy(t)を得る。得られたλy(t)(=t3+t)は、セクション生成部14に送信される。
【0091】
セクション生成部14は、λy(t)を受信すると、前述同様に、1変数多項式生成部15に1変数多項式の生成を要求する。1変数多項式生成部15は、d次の1変数多項式vx(t)をランダムに生成し(ST6)、得られたvx(t)をセクション生成部14に出力される。
【0092】
セクション生成部14は、これらλx(t)(=t2+1)とvx(t)(=t3+1)を1変数多項式演算部16に送信する。1変数多項式演算部16は、λx(t)とvx(t)に基づいて、ux(t)(=λx(t)+vx(t)=t3+t2)を計算し(ST7)、得られたux(t)をセクション生成部14に送信する。
【0093】
以下同様に、セクション生成部14は、1変数多項式生成部15及び1変数多項式演算部16により、vy(t)(=t3+t2+1)を生成し(ST8)、uy(=λy(t)+vy(t)=t2+t+1)を計算する(ST9)。
【0094】
しかる後、セクション生成部14は、得られたux(t), uy(t), vx(t), vy(t)に基づいて、2つのセクションD1,D2を生成する。なお、D1:(x, y, t)=(ux(t),uy(t),t),D2:(x, y, t)=(vx(t),vy(t),t)である。セクションD1,D2は、セクション生成部14から制御部12に送信される。
【0095】
制御部12では、セクションD1,D2を受けると、このセクションD1,D2を持つ代数曲面を作成するため、代数曲面生成部17にセクションD1,D2を入力する。
【0096】
代数曲面生成部17は、セクションD1,D2を受けると、c10(t), c00(t)以外の係数であるc21(t)をランダムに生成させるための指示を1変数多項式生成部15に送信する。
【0097】
1変数多項式生成部15は、この指示により、係数c21(t)をランダムに生成する。ここで次数は、例えば2dなどのように、dの倍数に取る(c21(t)=t6+t4+t3+t+1)。得られたc21(t)は、1変数多項式生成部15から代数曲面生成部17に返信される。
【0098】
代数曲面生成部17は、入力されたセクションD1,D2とランダムに生成された係数c21(t)から式(4)に基づいて、1変数多項式演算部16に繰り返し演算命令を送信することにより、一次の項の係数c10(t)を計算する(ST10)。この例では、c10(t)=t8+t7+t6+t5+t4+t3+t2が算出される。
【0099】
更に、代数曲面生成部17は、c10(t), c21(t)とux(t), uy(t), vx(t), vy(t)から式(6)に基づいて、1変数多項式演算部16に繰り返し演算命令を送信することにより、定数項c00(t)を計算する(ST11)。この例では、c00(t)=t15+t13+t12+t11+t9+t8+t5+t4+t2+t+1が算出される。
【0100】
以上で代数曲面X(x, y, t)の形式データに必要な各項の係数の生成が完了する。
代数曲面生成部17は、各1変数多項式c21(t), c10(t), c00(t)を、ステップST3で決定した形式データに設定することにより、代数曲面XのファイブレーションX(x, y, t)を生成する。生成されたファイブレーションX(x, y, t)は、代数曲面生成部17から制御部12に送信される。
【0101】
以上の処理により、公開鍵である代数曲面Xのファイブレーション
X(x, y, t) : x5+y5+(t6+t4+t3+t+1)x2y+(t8+t7+t6+t5+t4+t3+t2)x
+t15+t13+t12+t11+t9+t8+t5+t4+t2+t+1 = 0 (7)
と秘密鍵である2つのセクション
1:(ux(t),uy(t),t)=(t3+t2, t2+t+1, t)
2:(vx(t),vy(t),t)=(t3+1, t3+t2+1, t) (8)
が得られた。
【0102】
次に、制御部12では、式(3)を満たす次数lを生成するため、1変数既約多項式次数生成部18に、代数曲面X(x, y, t)とセクションの最大次数dとを入力して次数lの生成を指示する。
【0103】
1変数既約多項式次数生成部18は、代数曲面X(x, y, t)とセクションの最大次数dとに基づいて式(3)の左辺((5+5) * 3+15=45)を計算する。次に、1変数既約多項式次数生成部18は、式(3)の右辺を得るために、この計算値(=45)よりも大きい値をランダムに選択する。ここでは例えば、値46を選択する。1変数既約多項式次数生成部18は、選択した値(46)を次数l(=46)として(ST12)、制御部12へ出力する。
【0104】
制御部12は、公開鍵である代数曲面Xと、一変数既約多項式の最小次数lと、秘密鍵であるセクションD1,D2とを鍵出力部19に送信する。
【0105】
鍵出力部19は、これらの鍵データX,l,D1,D2を鍵出力装置10の外部に出力する(ST13)。
【0106】
上述したように本実施形態によれば、公開鍵の一部であるファイブレーションX(x, y, t)を生成する際に、ファイブレーションX(x, y, t)の形式にcijxiyjの項を含めた構成により、生成される公開鍵のクラスの制限を除去することができる。
【0107】
ここで、cijxiyjの項を含めた構成を実現させるため、cijxiyjの項を、一次の項及び定数項c00以外の項としている。そして始めに、cijxiyjの項をランダムに生成する。続いて、cijxiyjの項と、2つのセクション内の1変数多項式とに基づいて一次の項の係数を生成する。最後に、cijxiyjの項と一次の項とに基づいて定数項c00を生成している。
【0108】
このような構成により、本実施形態においては、秘密鍵が2つのセクションである場合に、生成される公開鍵のクラスの制限を除去でき、もって、制限されたクラスに基づく解読法を阻止することができる。
【0109】
<第1の実施形態のバリエーション>
次に、本実施形態における幾つかのバリエーションを述べる。
第1のバリエーションは、代数曲面の定義体に関するバリエーションである。本実施形態では、代数曲面の定義体として素体を用いたが、これに限らず、一般の有限体Fq(q=pr)を代数曲面の定義体としてもよい。有限体は、素体と同様に、0での除算を除く四則演算を定義でき、一意的に値が定まるからである。有限体は、素体とその(有限次)拡大体から構成される。拡大体は、素体Fp上の拡大次数rの線形空間の元として定義される。また、拡大体は、当該拡大体の原始多項式によりリダクションが行なわれ、演算が定義される。なお、リダクションは、素体におけるpによるリダクション(割り算)と同種の操作である。
【0110】
第1のバリエーションによれば、有限体を代数曲面の定義体とした際に、拡大体の導入に伴い、生成できる鍵の種類が増えるので、安全性の更なる向上に貢献できる。第1のバリエーションを実施する場合、本実施形態で素数pが入力される部分に、更に拡大次数rを入力すればよい。なお、第1のバリエーションにおいては、内部演算を全て拡大体Fq上で行なう必要がある。但し、鍵生成のアルゴリズムでは四則演算のみを用いるので、本実施形態の内部演算がそのまま成立する。
【0111】
第2のバリエーションは、ステップST1において、入力される素数pとセクションの最大次数dのうち、いずれか一方又は両方(以下、「及び/又は」とも言う)をシステムパラメータとして固定するバリエーションである。パラメータp及び/又はdを固定することにより、ユーザは、セキュリティレベルを気にせずに、鍵生成装置10内の適切なパラメータの下で安全な鍵を生成できる。なお、「適切なパラメータ」とは、十分高いセキュリティレベルを持ったパラメータを意味する。
【0112】
第2のバリエーションを実現するには、図6に示すように、素数格納部11a及び/又はセクションの最大次数格納部11bを更に備え、鍵生成アルゴリズムにおいて、これらのパラメータp, dが入力されるステップST1の代わりに、図7に示すように、格納部11a,11b内の値を読み出すステップを挿入すればよい。また、第1のバリエーションで述べた拡大次数rに関しても同様のことが成り立つ。この場合、素数格納部11aに代えて、図8に示すように、素数pと拡大次数rを格納する有限体格納部11cを設ければよい。
【0113】
第3のバリエーションは、0でない定数項c00(t)と一次の項c10(t)xに関するバリエーションである。本実施形態では、定数項c00(t)と一次の項c10(t)xを用いたが、これに限らず、図7に示すように、定数項c00(t)と一次の項c01(t)yを用いてもよい。理由は、セクションから代数曲面を求めることができれば、一次の項はc10(t)x又はc01(t)yのいずれでもよいからである。なお、本実施形態では、一次の項c10(t)xを用いる場合には、c00(t), c10(t)x 以外の項の係数cij(t)をランダムに定め、係数cij(t)からc00(t), c10(t)を計算している。同様にして、一次の項c01(t)yを用いる場合には、c00(t), c01(t)y 以外の項の係数cij(t)をランダムに定め、係数cij(t)からc00(t), c01(t)を計算すればよい。c00(t), c01(t)の計算は、本実施形態におけるλx(t)をλy(t)に置き換えると共に、これに準じてux(t), vx(t)をuy(t), vy(t)に置き換えれば良い。
【0114】
第4のバリエーションは、鍵生成処理のうち、一変数既約多項式f(t)の最小次数lを求める処理を外部で実行するバリエーションである。鍵生成処理の主要部分は、2つのセクションから安全性の高い代数曲面を生成する処理にある。このため、最小次数lを求める処理は、代数曲面X(x, y, t)とパラメータdに基づいて、鍵生成装置10の外でも実行できる。鍵生成装置10の外部に一変数既約多項式生成部18を配置した場合、鍵生成装置10の構成を簡素化できる。これに加え、一変数既約多項式最小次数生成部18をモジュール化することにより、より安全性の高い実装が可能になる。
【0115】
(第2の実施形態)
本実施形態における公開鍵・秘密鍵は、第1の実施形態と同じである。
【0116】
本実施形態は、将来に亘って代数曲面の安全性を確保する観点から、第1の実施形態で得られた代数曲面が特殊なクラスに属するか否かを検査し、特殊なクラスに属する代数曲面を避ける形態である。
【0117】
補足すると、代数曲面には、楕円曲面、有理曲面と呼ばれる特殊なクラスが存在する。特殊なクラスの代数曲面は、それぞれ性質が良く知られている。従って、特殊なクラスの代数曲面は、求セクション問題の効率的な解法こそ見出されてないものの、1つのセクションが求まれば他のセクションが求まる等といった解析し易い性質があるので、安全性が低い。そこで、将来に亘って安全性を確保するには、解析し易い特殊なクラスの代数曲面を避けることが望ましい。
【0118】
さて、生成された代数曲面に関し、特殊なクラスの代数曲面か否かの判定に必要な種数という量を定義する。始めに、代数曲面のファイブレーションを
【数28】

で表現する。更に、このファイブレーションを、x, yを変数とする代数関数体K(=Fp(t)) 上の代数曲線とみなした場合の曲線をC(x, y)=0もしくはCで表す。種数はこの曲線Cに対して定義され、g(C)で表される。いま、xとyに関するCの総次数をdcとおくとき、種数g(C)は
【数29】

のように表される。ここで、PはCの特異点を表し、右辺第二項の和はCの全ての特異点にわたる。特異点とは、代数曲線C(x, y)=0 上の微分係数が一意に定まらない点を云う。交点や尖点は特異点である。交点は2個の微分係数が対応し、尖点は2個以上の微分係数が対応している。式(9)におけるσ(P)は、各特異点の特異性を測る量であり、例えば、文献“飯高茂・上野健爾・浪川幸彦著「デカルトの精神と代数幾何」(日本評論社、1993 年)、p.23”に定義が記されている。しかしながら、σ(P)の定義からも容易に推察されるように、一般に、σ(P)を求めることは、計算機を用いても困難である。
【0119】
一方、有限体のサイズ(本実施形態ではp) 又はcij(t)の最高次数eが十分大きければ、任意に代数曲線を抽出したとき、特異点を持たない代数曲線(非特異な代数曲線)となる確率が十分大きくなる。理由は以下の通りである。Cの定義式
【数30】

のxとyの総次数をdcとする。まず、与えられた2つのセクションをファイブレーションXが有するという条件を考慮せず、任意のdc次多項式を考える。このとき、C(x, y)の中に現れる項の数は
【数31】

【0120】
さて、{cij(t)}をNd_c次のベクトルと考えると、{cij(t)} 全体はK上Nd_c次元のベクトル空間をなす。
【0121】
さらに、一つのベクトル{cij(t)}を0でない定数倍(b(t)倍)し、得られるdc次多項式b(t)C(x, y)は、元の多項式C(x, y)と本質的に同じである。そこで、dc次同次多項式全体のなす集合を定数倍の作用で割り、得られた集合をHd_cとおく。つまりHd_c={K上3変数dc次多項式}/(定数倍)である。すると
【数32】

である(岩波講座・現代数学の展開・向井 茂著「モジュライ理論1」、p.147)。上式は、Hd_cの中にあるほとんど全ての多項式は非特異な曲線を定義することを示す。理由は、係数{cij(t)}の次数の上限をeとすると、#K=pe+1であるからである。
【0122】
よって、Hd_cの中から任意に選んだ曲線が特異曲線となる確率は
【数33】

で与えられる。この確率は、p もしくはeが大きいと極めて小さい数になる。鍵生成装置10により生成される代数曲面は、cij(t)の次数eが極めて大きいため、たとえpが小さくても、十分高い確率で非特異な代数曲面となる。よって、種数g(C)を
【数34】

と近似的に求める式(10)が相当に高い確率で成立する。
【0123】
また、種数gと、特殊なクラスの代数曲面(楕円曲面、有理曲面)とは、以下の関係にあることが知られている。
【0124】
g=0 ⇒ (有理曲面)
g=1 ⇒ (楕円曲面) (11)
よって、安全な鍵を生成するためには、g≧2の代数曲面を用いることが望ましい。
【0125】
(第2の実施形態の具体的な構成)
図9は本発明の第2の実施形態に係る鍵生成装置の全体構成図であり、図2と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した部分の説明を省略する。
【0126】
本実施形態は、第1の実施形態の変形例であり、予め特殊なクラスの代数曲面を避ける観点から、種数計算部21及び安全性検証部22を付加した構成となっている。
【0127】
ここで、種数計算部21は、各部11〜17により生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を、計算式 g(C)=(dc−1)(dc−2)/2に基づいて計算する機能と、計算した種数g(C)を制御部12に送信する機能とをもっている。
【0128】
安全性検証部22は、制御部12から受けた種数g(C)が2未満であるか否かを判定する機能と、判定の結果、種数g(C)が2未満のとき、代数曲面決定部13から種数計算部21までの処理を再実行するように、エラー信号を制御部12に送信する機能と、判定の結果、種数g(C)が2以上のとき、安全を通知する信号を制御部12に送信する機能とをもっている。
【0129】
次に、以上のように構成された鍵生成装置の動作を図10及び図11のフローチャートを用いて説明する。
【0130】
鍵生成装置10においては、前述同様に、ステップST1〜ST11までの処理を実行する。制御部12は、この処理により得られた有限体の情報(本実施形態では素数p)と代数曲面X(x, y, t)とを種数計算部21に送信する。
【0131】
種数計算部21は、有限体の情報、代数曲面X(x, y, t)及び式(10)に基づいて、種数g(X)を近似的に計算する(ST11−2)。詳しくは、代数曲面をx, yに関する多項式と見た場合の総次数dcを計算する。この計算は、代数曲面の各項のx, yに関する総次数を求め、その最大値をdcとして実行される。次に、dc を式(10)に代入して種数g(X)を計算する。得られた種数g(X)は、制御部12へ送信される。
【0132】
制御部12は、種数g(X)を安全性検証部22に送信する。安全性検証部22は、この種数g(X)が2未満(g(X) < 2)であるか否かを判定する(ST11−3)。種数g(X)が2未満の場合、ファイブレーションXが特殊なクラスの代数曲面(楕円曲面又は有理曲面)であるので、将来にわたる安全性を確保できない。
【0133】
そこで、安全性検証部22は、種数g(X)が2未満の場合、ステップST2からST11−3までの処理を再実行するように、エラー信号を制御部12に送信する。制御部12は、エラー信号を受けると、他の鍵を生成するため、ステップST2に戻り、代数曲面決定部13を制御する。
【0134】
一方、ステップST11−3の結果が否(g(X) ≧ 2)の場合、ファイブレーションXが特殊なクラスの代数曲面ではないので、安全性を確保できる。そこで、安全性検証部22は、否(g(X) ≧ 2)の場合、安全を通知する信号を制御部12に送信する。
【0135】
制御部12は、安全を通知する信号を受けると、一変数既約多項式f(t)の最小次数lを計算するための指示を一変数既約多項式最小次数生成部18に送信する。以下、第1の実施形態と同様にステップST12,ST13の処理を実行する。
【0136】
上述したように本実施形態によれば、第1の実施形態の効果に加え、生成されたファイブレーションX(x, y, t)を代数曲線C(x, y)とみなしたときの種数g(C)を計算し、得られた種数g(C)が2未満のとき、他のファイブレーションX(x, y, t)を生成するため、ステップST2に戻る構成により、解析し易いクラスの代数曲面の使用を避けることができ、もって、将来にわたる安全性を確保することができる。
【0137】
<第2の実施形態のバリエーション>
前述した第1〜4のバリエーションは、図12及び図13に示すように、本実施形態でも同様に成り立つ。
第5のバリエーションは、代数曲面の総次数dcに基づいて、代数曲面決定部13で代数曲面を絞り込むバリエーションである。第5のバリエーションでは、種数計算部21及び安全性検証部22(ステップST11−2,ST11−3)を省略し、代数曲面決定部13により、予め特殊なクラスの代数曲面を排除している。なお、種数計算部21及び安全性検証部22(ステップST11−2,ST11−3)は省略しなくてもよい。
【0138】
ここで、代数曲面決定部13は、具体的には、式(10),(11)から得られる以下の関係に基づいて特殊なクラスの代数曲面を排除する。
【0139】
dc = 1,2 ⇒ g=0(有理曲面)
dc = 3 ⇒ g=0(楕円曲面)
この関係によれば、総次数dcが3以下の代数曲面は、確実に特殊なクラスの代数曲面である。一方、総次数が4以上の代数曲面は、高い確率で特殊なクラスの代数曲面ではない。従って、代数曲面決定部13においては、図14に示すように、ステップST2で選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)を算出し(ST2−2)、得られた総次数dcが4未満か否かを判定する(ST2−3)。
【0140】
代数曲面決定部13は、この判定の結果、総次数dcが4未満のとき、ステップST2に戻り、選択した形式データとは異なる形式データを再選択し、再選択した形式データについて、ステップST2−2からST2−3までの処理を実行する。なお、ステップST2−3の判定の結果、総次数dcが4以上であれば、ステップST3に進むことは言うまでも無い。
【0141】
すなわち、代数曲面決定部13は、ステップST2−2からST2−3までの処理により、総次数dcが3以下の代数曲面の形式を出力しないようにフィルタリングする。これにより、ステップST11の後にST2に戻る場合が無くなるので、鍵生成の効率を向上できる。
【0142】
尚、第5のバリエーションにおける総次数dcが4以上のとき安全であり、4未満のとき安全でないと判断する判定方法は、代数曲面決定部13で代数曲面を絞り込む部分で用いるだけでなく、第2の実施形態における安全性検証部22での種数g(X)による判定と置き換えて利用することができる。これは、種数g(X)による判定と総次数dcによる判定とのどちらも出来上がった代数曲面の安全性を検証するための判定方法であり、式(10)からも分かる通り、総次数dcのみをパラメータとしているからである。従って、安全性検証部22を総次数dcにより判定する構成に変えることにより、第2の実施形態に必須であった種数計算部21が不要になる。またこの逆も成り立つ。即ち、第2の実施形態における式(10)により計算した種数g(X)による代数曲面の安全性検証に変わって第5のバリエーションで述べた総次数dcのみによる判定方法を利用してもよい。これにより種数計算部21が省略されるとともに、計算処理時間が短くなる。
【0143】
なお、第5のバリエーションの変形例としては、代数曲面決定部13にて代数曲面を絞り込む際に、種数計算部21及び安全性検証部22を用い、種数g(X)による判定を実行する構成を適用することができる。また、代数曲面決定部13における判定と、代数曲面X(x, y, t)生成後の判定とにおいては、種数g(X)又は総次数dcによる判定方法のうち、いずれか一方の判定方法のみを用いてもよく、あるいは各判定方法を交互に用いてもよい。また、他の変形例としては、種数g(X)を計算する場合、種数g(X)を式(9)に基づいて計算する構成とすることもできる。
【0144】
(第3の実施形態)
以下、本発明の第1又は第2の実施形態により生成された鍵を使用可能な暗号化・復号処理に関する実施形態を説明する。なお、第1又は第2の実施形態により生成された鍵は、特許文献1記載の暗号化・復号処理にも適用可能である。但し、ここでは、それ以外の暗号化・復号処理に関する実施形態について述べる。なお、第3の実施形態を述べる前に、前提となる安全性証明について述べる。
【0145】
公開鍵暗号の安全性は、素因数分解問題や離散対数問題のように、安全性の根拠となる問題の困難性に基づくと考えられている。しかし、この考えは、両者の厳密な帰着関係を述べるものではない。
【0146】
厳密な帰着関係を述べるためには、解読者による攻撃と達成される安全性とをモデル化し、モデル化した攻撃の下で安全性を達成することと、安全性の根拠となる問題の難しさとが等価であることを証明する必要がある。すなわち、公開鍵暗号の安全性と、公開鍵暗号を構成する問題の困難性との間の厳密な帰着関係を述べることが安全性証明である。
【0147】
安全性証明において、攻撃のモデルは、受動的攻撃(Chosen Plaintext Attack(CPA))と、能動的攻撃(Chosen Cipher Attack(CCA))とに大きく分類できる。
【0148】
受動的攻撃とは、公開鍵を利用して平文を繰り返し暗号化し、得られる暗号文から情報を引き出そうとする攻撃である。能動的攻撃とは、更に暗号文を復号装置に適応的に入力し、得られる復号結果から秘密鍵の情報を引き出そうとする攻撃である。この意味からCCAの方がCPAより強い攻撃となっている。
【0149】
また、安全性証明において、達成される安全性には2つの基準が提案されている。
第1の基準は、2つの平文を暗号化した後に区別できないこと(Indistinguishable(IND))である。第2の基準は、多項式時間において暗号文を操作しても、元の平文に関係する暗号文を作成できないこと(Non-Malleable(NM))である。
【0150】
従って、安全性証明の基準は、敵による攻撃のモデルと、達成される安全性との組合せでIND−CPA,NM−CCAのように表現される。IND−CPAは、受動的攻撃の下で、2つの暗号文から元の平文を区別する情報を抽出できない旨を意味する。NM−CCAは、能動的攻撃の下で、暗号文を操作した結果から元の平文に関係した情報を得られない旨を意味する。現在のところ、最強の安全性と考えられている基準はIND−CCAである。
【0151】
一方、IND−CPAの意味で安全性が証明された公開鍵暗号を、IND−CCAの意味で証明可能安全な公開鍵暗号アルゴリズムに変換する方法が知られている(例えば、特許第3306384号公報参照)。従って、IND−CPAの意味で安全性が証明された公開鍵暗号を構成できれば、この公開鍵暗号をIND−CCAの意味で証明可能安全(provable secure)な公開鍵暗号に変換することが可能となっている。
【0152】
続いて、第3の実施形態を説明する。なお、以下の各実施形態は、前述した求セクション問題を前提とし、この求セクション問題と関連するランダム化多項式判定問題に基づいて安全性を証明可能な構成となっている。
【0153】
(概要)
本実施形態の公開鍵は以下の5つである。
【0154】
1.素体の標数p
2.Fp上の代数曲面Xのファイブレーション:X(x,y,t)=0
3.Fp上の1変数既約多項式f(t)の次数l
但し、
degtX(x,y,t)<l (12)
4.(秘密鍵である)セクションにおける多項式ux(t),uy(t),vx(t),vy(t)の最大次数d
5.3変数多項式p(x,y,t)のx,yの最高指数e
秘密鍵は以下の2つの異なるセクションD1,D2である。
【0155】
1.Fp上の代数曲面Xのセクション:D1:(x,y,t)=(ux(t),uy(t),t)
2.Fp上の代数曲面Xのセクション:D2:(x,y,t)=(vx(t),vy(t),t)
これらは、前述した鍵生成方法で容易に求めることができる。
【0156】
次に、暗号化処理の概要を述べる。暗号化処理では、まず暗号化したいメッセージ(以下では平文と呼ぶ)をブロック分割して
m=m0‖m1‖・・・‖ml-1
のようにし、平文多項式m(t)の係数として次式のように埋め込む(平文埋め込み処理)。
【数35】

【0157】
ここで、m(t)をFp上の多項式とするために、各mi(0≦i≦l-1)はFpの元となるように取る必要がある。即ち、平文mはpのビット長に基づいて
0≦mi≦p-1
となるように分割される。なお、平文mは整数であり、例えばメッセージを表す文字コード列が整数に読み替えられることにより、構成されている。
【0158】
次に、Fp上のランダム多項式p(x,y,t),q(x,y,t)をランダムに決める。このとき、p(x,y,t)は、次の条件(13)(14)を満たすように決める。
【0159】
α>degxX(x,y,t)
β>degyX(x,y,t)
なる指数α,βに対して xαβの項を含む (13)
(degxp(x,y,t)+degyp(x,y,t))d+degtp(x,y,t)<l (14)
ここで、degx, degy, degtにより、それぞれ多項式のx,y,tに関する次数を表すものとする。また、q(x,y,t)は、次の条件(15)を満たすように決める。
【0160】
degtq(x,y,t)<l (15)
次に、Fp上ランダムな1変数のl次既約多項式f(t)を決める。既約多項式とは、これ以上因数分解できない多項式のことである。有限体上の1変数多項式の既約性判定は、容易であることが知られている。以上の式m(t),p(x,y,t),q(x,y,t),f(t)及び公開鍵である代数曲面XのファイブレーションX(x,y,t)から、次の式(16)によって暗号文F(x,y,t)を計算する。
【0161】
F(x,y,t)=m(t)+f(t)p(x,y,t)+X(x,y,t)q(x,y,t) (16)
暗号文F(x,y,t)を受け取った受信者は、所有する秘密鍵D1,D2を利用して次のように復号を行う。まず、セクションD1,D2を暗号文F(x,y,t)に代入する。ここで、セクションD1,D2を代数曲面X(x,y,t)に代入すると、
X(ux(t),uy(t),t)=0,X(vx(t),vy(t),t)=0により、次の2式h1(t),h2(t)が求まる。
【0162】
1(t)=F(ux(t),uy(t),t)=m(t)+f(t)p(ux(t),uy(t),t)
2(t)=F(vx(t),vy(t),t)=m(t)+f(t)p(vx(t),vy(t),t)
次に、2式を辺々引き算して、次の式(17)を計算する。
【0163】
1(t)−h2(t)=f(t){p(ux(t),uy(t),t)−p(vx(t),vy(t),t)}
(17)
次に、h1(t)−h2(t)を因数分解して、最大次数を持つ因数をf(t)と定める。ここで、最大次数の因子がf(t)であるためには、f(t)の次数をlとした時、条件(18)を満たすようなp(x,y,t)を選択すれば必要十分である。
【0164】
deg(p(ux(t),uy(t),t)−p(vx(t),vy(t),t))<l (18)
このためには、条件(19)の両方が成り立つように選択する必要がある。
【0165】
deg(p(ux(t),uy(t),t))<l
deg(p(vx(t),vy(t),t))<l
(19)
しかし、送信者にはセクションが秘匿されているので、f(t)の次数lを十分大きく取るとともに、セクションの各要素である多項式ux(t),uy(t),vx(t),vy(t)における次数の最大値dを公開鍵として公開している。即ち、p(x,y,t)を決定するときは条件式(14)を満たしていれば十分である。尚、h1(t)−h2(t)の因数分解は、1変数多項式の因数分解が容易であることから、十分有効な時間内に処理可能である。得られたf(t)でh1(t)を除すると(m(t)の次数がf(t)の次数l以下であることに注意すると)
1(t)=m(t)+f(t)p(ux(t),uy(t),t)
の関係から、平文多項式m(t)が得られる。
【0166】
得られた平文多項式m(t)から平文埋め込み処理と逆の処理で平文mを求めることができる。ここで、m(t)が剰余として一意的であることは特筆すべきことである。一意的でないと平文多項式m(t)の候補が複数存在し、真の平文多項式を特定することが困難になる。m(t)が一意的である理由は、h1(t)が含まれる一変数多項式環F[t]では整数と同様に除法の定理が成立するため、一変数多項式を一変数多項式で割った商と剰余は一意的となるからである。なお、2変数以上の多項式では除法の定理が成立しないことが知られている。
【0167】
続いて、本実施形態のアルゴリズムが、後述するランダム化多項式判定問題が難しいと仮定すると、IND−CPAの意味で証明可能安全であることを説明する。まず、復号アルゴリズムは式(17)において、
{p(ux(t),uy(t),t)−p(vx(t),vy(t),t)}=0
の場合、失敗する。しかしながら、この失敗は公開鍵であるeに対して無視できる(negligible)確率でしか生じない。
【0168】
[命題1] 少なくとも2つの相異なるセクション
【数36】

を持つ有限体Fp上定義された代数曲面のファイブレーションX(x,y,t)=0と3変数多項式p(x,y,t)のx,yに関する指数の最大値eに対して、
p(ux(t),uy(t),t)=p(vx(t),vy(t),t) (20)
となる確率は1/pe+1である。
【0169】
[証明1] X(x,y,t)の有する相異なるセクション(ux(t),uy(t),t),(vx(t),vy(t),t)においてux(t)≠vx(t)であるとする。もし、ux(t)=vx(t)であった場合はuy(t)≠vy(t)となり、以下の議論をuy(t)≠vy(t)の仮定で同様に展開できる。
【0170】
さて、式(20)を満たすようなxにおいて指数の最大値eを取るp(x,y,t)が存在したとする。このとき、Fp上の任意の(e−1)次以下の1変数多項式g(x)(≠0)に対して、p(x,y,t)+g(x)は式(20)を満たさない。なぜなら、もし満たしたとすると
g(ux(t))=g(vx(t))
が成り立ち、有限体Fpを無限体にまで拡大したときに無限個の解を持つことになり、ux(t)=vx(t)が従う。また、このように生成された式は、式(20)を満たすような別のp(x,y,t)から同様の手段で得られる多項式とは決して一致しない。実際、式(20)を満たす他のp1(x,y,t),p2(x,y,t)と1変数多項式g1(x),g2(x)に対して
1(x,y,t)+g1(x)=p2(x,y,t)+g2(x) (21)
であったとする。このとき
1(x,y,t)−p2(x,y,t)=g2(x)−g1(x)
となる。ここでg1(x)=g2(x)であるならばp1(x,y,t)=p2(x,y,t)となり矛盾するので、g1(x)≠g2(x)である。いま、g(x)=g2(x)−g1(x)とすると、p1(x,y,t)−p2(x,y,t)の性質から
g(ux(t))=g(vx(t))
を満たすので、ux(t)=vx(t)が従う。よって、式(21)を満たすような相異なる(p1(x,y,t),g1(t)),(p2(x,y,t),g2(t))の組は存在しない。尚、p(x,y,t)がyにおいて指数の最大値をとった場合は、xとyの役割を変更することにより証明がそのまま成り立つ。
【0171】
以上のことから式(20)を満たす1つのFp[x,y,t]上の3変数多項式p(x,y,t)に対し、少なくともpe+1個の式(20)を満たさない多項式を重複なく対応付けできる。よって、式(20)を満たすp(x,y,t)は高々1/pe+1の確率でしか生じない。
【0172】
代数曲面暗号の安全性は、以下の代数曲面暗号に関するランダム化多項式判定問題に依存している。
【0173】
[定義1] 代数曲面暗号に関するランダム化多項式判定問題
p上定義された次数d以下の2つの相異なるセクションを有する代数曲面のファイブレーションX(x,y,t)=0と自然数lが与えられた時、3変数多項式A(x,y,t)が集合S
【数37】

に属するか否かを判定する問題を代数曲面暗号に関するランダム化多項式判定問題といい、代数曲面暗号に関することが明らかなときには単にランダム化多項式判定問題という。
【0174】
ランダム化多項式判定問題は、次数d以下の2つの相異なるセクションを有する代数曲面のファイブレーションX(x,y,t)=0と既約多項式f(t)の最小次数lが与えられた時、与えられた多項式g(x,y,t)が
f(t)p(x,y,t)+X(x,y,t)q(x,y,t) (22)
という形に書けるか否かを判定する問題である。仮に、多項式g(x,y,t)が2通り以上の書き方で式(22)の形に書けたとする。この場合、攻撃者(問題を解く人)は、複数の書き方のうちの1つの書き方を見出せばよいので、ランダム化多項式判定問題はそれだけ容易となる。しかしp(x,y,t)が条件(13)(14)、q(x,y,t)が条件(15)を満たす限りにおいては、そのようなことはなく一意に書けることが以下のように示せる。
【0175】
[命題2] 多項式g(x,y,t)が次数d以下の2つの相異なるセクションを有する代数曲面のファイブレーションX(x,y,t)=0と既約多項式f(t)の最小次数lと、条件(13)(14)を満たすp(x,y,t)、条件(15)を満たすq(x,y,t)によって
f(t)p(x,y,t)+X(x,y,t)q(x,y,t)
のように書けるとき、その書き方は一意的である。
【0176】
[証明2] 2通りの表現で、仮定のごとく書けるg(x,y,t)が存在したと仮定する。
【0177】
g(x,y,t)=f1(t)p1(x,y,t)+X(x,y,t)q1(x,y,t)
=f2(t)p2(x,y,t)+X(x,y,t)q2(x,y,t) (23)
仮定からX(x,y,t)は2つの相異なる次数d以下のセクションを持つ代数曲面である。このため、各セクションを(ux(t),uy(t),t),(vx(t),vy(t),t)とすると、次式の関係がある。
【数38】

【0178】
ここで、命題1から無視できる(negligible)確率を除けば
1(ux(t),uy(t),t)−p1(vx(t),vy(t),t)≠0
であるので、
2(ux(t),uy(t),t)−p2(vx(t),vy(t),t)≠0
である。p1(x,y,t),p2(x,y,t)が条件(14)を満たすことから、次数の関係によって
2(t)=cf1(t)となる。ここでcは有限体Fpの元である。従って、式(23)の辺々を引いて前式を反映させると、次式を得る。
【0179】
1(t)(p1(x,y,t)−cp2(x,y,t))=X(x,y,t)(q2(x,y,t)−q1(x,y,t))
ここで、代数曲面X(x,y,t)の既約性から(f(t),X(x,y,t))=1となり、Fp[x,y,t]は一意分解整域である。このため、
1(t)|q2(x,y,t)−q1(x,y,t)
が従う。ここでq(x,y,t)に対する条件(15)により、
degt2(x,y,t)−q1(x,y,t)<deg f1(t)
であるので
1(x,y,t)=q2(x,y,t)
となる。従って、
1(x,y,t)=p2(x,y,t)
となり、c=1即ち
1(t)=f2(t)
が従う。よって2つの表現は一致する。
【0180】
このようにランダム化多項式判定問題を解くには、一意的な解が存在する問題の解の有無を判定する必要がある。このため、ランダム多項式判定問題は容易に解けない。もちろん、求セクション問題が容易に解ければ、ランダム化多項式判定問題も容易に解ける。しかし、求セクション問題を解く以外にランダム化多項式判定問題を解く方法は知られていない。よって、ランダム化多項式判定問題も十分に難しい問題であると考えられる。
【0181】
また、命題から本発明の公開鍵暗号の復号結果が一意的であることが以下のように示される。
【0182】
[補題1] 少なくとも2つの次数d以下の相異なるセクションを持つ代数曲面のファイブレーションX(x,y,t)=0と既約多項式f(t)の最小次数lに対応したランダム化多項式G(x,y,t)に対して、m(t)+G(x,y,t)はランダム化多項式とはならない。但し、m(t)は0でない次数l−1以下の1変数多項式である。
【0183】
[証明3] m(t)+G(x,y,t)がランダム化多項式だとすると、式(24)を書ける。
【0184】
m(t)+G(x,y,t)=f1(t)p1(x,y,t)+X(x,y,t)q1(x,y,t)
=m(t)+f2(t)p2(x,y,t)+X(x,y,t)q2(x,y,t)
(24)
ここで、仮定からX(x,y,t)は2つのセクションを持つ代数曲面なので、それらのセクションを(ux(t),uy(t),t),(vx(t),vy(t),t)とすると、次式を書ける。
【数39】

【0185】
ここで、命題1から無視できる(negligible)確率を除けば
1(ux(t),uy(t),t)−p1(vx(t),vy(t),t)≠0
であるので、
2(ux(t),uy(t),t)−p2(vx(t),vy(t),t)≠0
となる。p1(x,y,t),p2(x,y,t)が条件(14)を満たすことから、次数の関係によって
2(t)=cf1(t)
となる。よって、式(24)に(ux(t),uy(t),t)と前式を代入することで、
m(t)=f1(t){p1(ux(t),uy(t),t)−cp2(ux(t),uy(t),t)}
を得る。しかし、これはdeg m(t)≧lとなり矛盾する。従って、m(t)+G(x,y,t)はランダム化多項式とはならない。
【0186】
[定理1]
少なくとも2つのセクションを持つ代数曲面のファイブレーションX(x,y,t)=0と既約多項式f(t)の最小次数lと2つのセクションに含まれる1変数多項式の最大次数dに対応したランダム化多項式G(x,y,t)と、次数l−1以下の1変数多項式m(t)による表現m(t)+G(x,y,t)は一意的である。
【0187】
[証明4]
deg m1(t),deg m2(t)<lを満たす1変数多項式m1(t),m2(t)とランダム化多項式G1(x,y,t),G2(x,y,t)に対して
1(t)+G1(x,y,t)=m2(t)+G2(x,y,t)
となる関係があったとする。このとき
1(t)−m2(t)+G1(x,y,t)
がランダム化多項式となる。すると補題1により、
1(t)=m2(t)
となり、
1(x,y,t)=G2(x,y,t)
が従う。よって表現は一意的である。
【0188】
次にこれらの結果に基づいて本実施形態の公開鍵暗号の安全性証明を行なう。
【0189】
[定義2] IND−CPA
Π:=(K,E,D)を公開鍵暗号、これに対する確率的アルゴリズムA:=(A1,A2)を考え、このアルゴリズムに対してセキュリティパラメータをk∈Nとして
【数40】

【0190】
パラメータkは、公開鍵暗号の安全性の基本となる問題の難しさを表わす指標である。本発明の公開鍵暗号においては、pを固定した場合、dもしくはlがパラメータとなる。実際、後述するパラメータ設計方法でも明らかになるようにlはdの関数であるため、dをパラメータと考えても良い。
【0191】
ここで、CPAは、平文を暗号化プログラムに掛け、出力されてくる暗号文を参考に適応的に平文を構成することを意味しており、アルゴリズムA(=(A1,A2))はCPAを実行できることを仮定している。尚、以下で詳しく述べるようにアルゴリズムは大きく分けて2つのアルゴリズムA1とA2を有しているためA(=(A1,A2))のように記述する。
【0192】
次に、達成される安全性の基準であるINDに関して説明する。INDとは、以下の手順(i)〜(iv)により得られた暗号文から元のメッセージを当てることができることを意味する。
【0193】
(i) 鍵生成アルゴリズムKを使ってパラメータkを満たすように生成した公開鍵と秘密鍵のペア(pk,sk)を出力させる。
【0194】
(pk,sk)←K(1k
(ii) 鍵ペアのうち公開鍵pkのみを知っているアルゴリズムA1が何度か適応的に平文を暗号化した後で、2つのメッセージm0,m1を選択する。
【0195】
(x0,x1,s)←A1(pk);
(iii) 暗号化オラクルと呼ばれる第3者にm0,m1のどちらかを選んで暗号化させ、暗号文yを得たとする。
【0196】
b←R{0,1};y ←Epk(xb):
(iv) 得た暗号文yから対応するメッセージがm0であるかm1であるかをアルゴリズムA2を利用して当てる
2(x0,x1,s,y)=b
一方、INDにおいては、答えは0か1なのであるから、出鱈目に回答した場合1/2の確率で正解となる。そこで、正解率(成功確率)が1/2から隔たる度合いが問題となる。即ち、確率
【数41】

【0197】
無視できる(negligibleである)とはパラメータkに対して確率が指数関数的に小さくなることである。例えば1/plや1/pdなどはパラメータをdとしたとき、無視できる(negligible)確率であるということができる。
【0198】
さて、ランダム化多項式判定問題が難しいとすると、代数曲面暗号の安全性を以下のように証明できる。
【0199】
[定理2] 代数曲面暗号がIND−CPAの意味で安全であることと、ランダム化多項式判定問題が多項式時間で解けないこととは同値である。
【0200】
[証明5] 代数曲面暗号ΠがIND−CPAの意味で安全ならば、ランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けないことを示す。ランダム化多項式判定問題を多項式時間内に無視できない(non-negligible)確率AdvAで解くアルゴリズムAが存在したとする。このとき、代数曲面暗号ΠをIND−CPAの意味で解く敵C=(C1,C2)を図15に示すように構成できる。C1は、公開鍵として与えられたX,l,d,eが入力されると、公開鍵を使った何らかの処理を行い、2つの平文m0(t),m1(t)を暗号化オラクルεに出力する。暗号オラクルεは、入力された平文のうちの1つのmb(t)を選んで、公開鍵を利用して暗号化し、暗号文F(x,y,t)を敵Cに返す。敵Cは、受け取った暗号文F(x,y,t)に対して
η0(x,y,t)=F(x,y,t)−m0(t)
を作成し、アルゴリズムAによって結果D(η0,S)を得る。ここで、D(η,S)は{0,1}を値域として取る関数で、多項式ηがランダム化多項式の集合Sに属する場合1、属さない場合0とする。敵Cは、D(η0,S)の値が0ならばb=1を、D(η0,S)値が1ならばb=0を出力する。以上の処理はアルゴリズムAが多項式時間で終了することを仮定しているので、多項式時間で終了する。
【数42】

【0201】
次に、ランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けないならば、代数曲面暗号ΠがIND−CPAの意味で安全であることを示す。代数曲面暗号ΠがIND−CPAの意味で安全でないとする。このとき、代数曲面暗号ΠをIND−CPAの意味で破る敵A=(A1,A2)が存在する。この敵Aを仮定してランダム化多項式判定問題が多項式時間内に無視できない(non-negligible)確率で解けるアルゴリズムAが存在することを示す。即ち、アルゴリズムAはランダム化多項式集合S(=S(X,l,d))と多項式η(x,y,t)が与えられたとき、η(x,y,t)がSに属するか否かを図16のように判定する。図16において、ランダム化多項式集合のパラメータX,l,dを公開鍵とする公開鍵暗号Πを考え、X,l,dを公開鍵として敵A=(A1,A2)に入力する(ST21)。A1は平文m0(t),m1(t)を暗号化オラクルεに出力する。暗号化オラクルεはbを集合{0,1}からランダムに選択し、暗号文F(x,y,t)(=mb(t)+η(x,y,t))を生成することによりシミュレートされる(ST22)。敵Aは暗号オラクルによって生成された暗号文F(x,y,t)を受け取って(A2において)多項式時間内に終了するアルゴリズムで処理し、b’を出力する(ST23)。ここでb’=bであればD(η,S)=1、b’≠bであればD(η,S)=0とする。アルゴリズムAは明らかに多項式時間内に終了する。次にAdvAを以下のように評価する。ここで、G=Fp[x,y,t],R=G−Sと定義する。
【数43】

【0202】
【数44】

【0203】
[パラメータの設定方法]
本節では、上述した議論でその安全性がランダム化多項式判定問題に帰着された本発明の公開鍵暗号に関し、パラメータの具体的な設定方法を説明する。
【0204】
本発明の公開鍵暗号のパラメータは、有限体Fpのサイズpとセクションの最高次数dである。また1変数多項式f(t)の次数l(d)は条件(14)から
l(d)=(2d+1)e(d)+1 (25)
とすれば良いことが分かる。また、3変数多項式p(x,y,t)のx,yの最大指数e(d)は復号の失敗確率に関するパラメータである。失敗確率は命題1により1/pe(d)+1である。従って、失敗確率を2nとしたければ、
(|p|−1)(e(d)+1)>n
を満たすようにとれば良い。ここで|p|はpのビット長を表す。
【0205】
(第3の実施形態の具体的な構成)
次に、本実施形態の公開鍵暗号における暗号装置、復号装置の具体的な構成とそのアルゴリズムについて説明する。図17は本発明の第3の実施形態に係る暗号装置の全体構成図であり、図18は同実施形態における復号装置の全体構成図である。
【0206】
ここで、暗号装置30は、図17に示すように、平文入力部31、公開鍵入力部32、平文埋め込み部33、暗号化部34、1変数既約多項式生成部35、多項式生成部36及び暗号文出力部37を備えている。また、暗号装置30は、図示しないメモリ(ハードウェア資源)を有し、各部31〜37から入力データ、出力データ及び処理中のデータ等が適宜読出/書込可能となっている。
【0207】
ここで、平文入力部31は、外部から入力された平文(メッセージ)mを一時的にメモリに保持し、この平文mを平文埋め込み部33に送出する機能をもっている。
【0208】
公開鍵入力部32は、外部から入力された公開鍵を一時的にメモリに保持し、この公開鍵を平文埋め込み部33及び暗号化部34に送出する機能をもっている。
【0209】
平文埋め込み部33は、平文入力部31から受けた平文m及び公開鍵入力部32から受けた公開鍵に基づいて、平文mを1変数tで次数l-1以下の平文多項式m(t)の係数として埋め込む機能と、得られた平文多項式m(t)を暗号化部34に送出する機能をもっている。
【0210】
暗号化部34は、平文埋め込み部33から受けた平文多項式m(t)及び公開鍵入力部32から受けた公開鍵X(x,y,t),p,l,d,eに基づいて、図19に示す動作を実行するように、後段の各部35〜37を制御するものである。特に、暗号化部34は、平文多項式m(t)に対し、各多項式p(x,y,t),q(x,y,t),f(t)とファイブレーションX(x,y,t)とを加算、減算及び乗算のうち少なくとも一つを含む演算を行う暗号化処理により、平文多項式m(t)から暗号文F(x,y,t)(=Epk(m,p,q,f,X))を生成する機能をもっている。
【0211】
1変数既約多項式生成部35は、暗号化部34に制御され、次数l以上のランダムな1変数既約多項式f(t)を生成する機能をもっている。
【0212】
多項式生成部36は、暗号化部34に制御され、3変数x,y,tのランダムな多項式p(x,y,t),q(x,y,t)を生成する機能をもっている。
【0213】
暗号文出力部37は、暗号化部34により生成された暗号文F(x,y,t)を出力する機能をもっている。
【0214】
一方、復号装置40は、図18に示すように、暗号文入力部41、鍵入力部42、復号部43、セクション代入部44、1変数多項式演算部45、1変数多項式因数分解部46、多項式抽出部47、1変数多項式剰余演算部48、平文展開部49及び平文出力部50を備えている。また、復号装置40は、図示しないメモリ(ハードウェア資源)を有し、各部41〜50から入力データ、出力データ及び処理中のデータ等が適宜読出/書込可能となっている。
【0215】
暗号文入力部41は、外部から入力された暗号文Fを一時的にメモリに保持し、この暗号文Fを復号部43に送出する機能をもっている。
【0216】
鍵入力部42は、外部から入力された公開鍵を一時的にメモリに保持し、この公開鍵を復号部43に送出する機能をもっている。
【0217】
復号部43は、図20に示す動作を実行するように、後段の各部44〜29を制御する機能をもっている。
【0218】
セクション代入部44は、復号部43に制御され、入力された暗号文Fに対し、各セクションD1,D2を代入して2つの1変数多項式h1(t),h2(t)を生成する機能をもっている。
【0219】
1変数多項式演算部45は、復号部43に制御され、各1変数多項式h1(t),h2(t)を互いに減算し、減算結果{h1(t)−h2(t)}を得る機能をもっている。
【0220】
1変数多項式因数分解部46は、復号部43に制御され、減算結果{h1(t)−h2(t)}を因数分解する機能をもっている。
【0221】
多項式抽出部47は、復号部43に制御され、因数分解結果から最も大きな次数を持つ既約多項式f(t)を抽出する機能をもっている。
【0222】
1変数多項式剰余演算部48は、復号部43に制御され、1変数多項式h1(t)を既約多項式f(t)で除算し、剰余として平文多項式m(t)を得る機能をもっている。
【0223】
平文展開部49は、復号部43から受けた平文多項式m(t)の係数から平文mを抽出する機能をもっている。
【0224】
平文出力部50は、平文展開部49から受けた平文mを出力する機能をもっている。
【0225】
次に、以上のように構成された暗号装置及び復号装置の動作を図19及び図20のフローチャートを用いて説明する。
【0226】
(暗号化処理:図19)
暗号装置30においては、平文入力部30から平文(メッセージ)mが入力され(ST31)、公開鍵入力部32から公開鍵X(x,y,t),p,l,d,eが入力されると(ST32)、暗号化処理を開始する。入力された公開鍵のうち、1変数既約多項式f(t)の次数であるlと素体の標数pとが取得され(ST33)、l,pが平文埋め込み部33に送られる。
【0227】
平文埋め込み部33では、別途、平文入力部31から送出された平文mを標数pのビット長よりも1小さいビット長に分割する。例えばp=17の場合は4ビットに分割する。ここで、平文mが16進表示で
m=0x315763ef25c04c792ef151
であるとする。
【0228】
この場合、平文埋め込み部33は、16進表示の平文mを4ビット毎に分割し、平文多項式m(t)の係数として次式のように埋め込む(ST34)。
【0229】
m(t)=3t21+t20+5t19+7t18+6t17+3t16+15t15+11t14+2t13
+5t12+12t11+0t10+4t9+12t8+7t7+9t6+2t5+14t4
+15t3+t2+5t+1
平文埋め込み部33は、平文多項式m(t)を暗号化部34に送信する。一方で、公開鍵入力部32は、公開鍵X(x,y,t),p,l,d,eを暗号化部34に送信する。
【0230】
暗号化部34では、公開鍵のうち、lとpを1変数既約多項式生成部35に送信する。
【0231】
1変数既約多項式生成部35は、l次の1変数既約多項式f(t)をランダムに生成し(ST35)、得られた1変数既約多項式f(t)を暗号化部34に返信する。ここで、既約多項式の生成は、l次の多項式をランダムに生成し、得られる1変数多項式が既約多項式となるまでFp上の既約性判定を繰り返すことにより行う。
【0232】
暗号化部34は、1変数既約多項式f(t)を得ると、多項式生成部36にp,l,d,eを送信する。多項式生成部36は、p,l,d,eに基づいて、3変数多項式の各項が次数に関する関係式(13)と条件(14)を満たすようにランダムな3変数多項式p(x,y,t)を生成する(ST36)。生成方法としては、ランダムに生成した後、2つの条件を満たすことをチェックし、満たさなかった時には再度ランダムに生成する方法と、2条件に合うように、生成する3変数多項式に制約を掛ける方法がある。いずれの方法にしても、条件(13)(14)の範囲にて十分に多様な係数を取りえるため、実行可能な時間内で生成が終了する。多項式生成部36は、得られた3変数多項式p(x,y,t)を暗号化部34に送信する。
【0233】
暗号化部34は、3変数多項式p(x,y,t)を受けると、公開鍵のうちp,l,d,eを多項式生成部36に送信する。多項式生成部36は、p,l,d,eに基づいて、条件(5)を満たすように3変数のランダムな多項式q(x,y,t)を生成し(ST37)、得られた3変数多項式q(x,y,t)を暗号化部34に送信する。
【0234】
暗号化部34は、以上の処理で得られたm(t),f(t),p(x,y,t),q(x,y,t)と、公開鍵である代数曲面X(x,y,t)を利用して、式(16)に従って暗号文F(x,y,t)を計算し展開する(ST38)。暗号化部34は、この暗号文を暗号文出力部37から出力し(ST39)、暗号化処理を終了する。なお、暗号化部34は、必要により、暗号文を予め定められたフォーマットに合わせて変形して暗号文出力部37から出力してもよい。
【0235】
(復号処理:図20)
復号装置40においては、暗号文入力部41から暗号文F(x,y,t)を取得し(ST41)、鍵入力部42から公開鍵X(x,y,t),pと秘密鍵を取得すると(ST42)、復号処理を開始する。秘密鍵は2つのセクションD1,D2である。取得された暗号文と鍵情報は復号部43に送られる。
【0236】
復号部43は、セクション代入部44に暗号文F(x,y,t)とセクションD1を送信する。セクション代入部44は、D1をF(x,y,t)に代入し、必要に応じて1変数多項式演算部45を利用することにより、h1(t)を得る(ST43)。ここで、1変数多項式演算部45は1変数多項式の加減乗除演算を行う。得られたh1(t)は、セクション代入部44から復号部43に送信される。
【0237】
また同様に、復号部43は、セクション代入部44に暗号文F(x,y,t)とセクションD2を送信する。セクション代入部44は、セクションD2をF(x,y,t)に代入し、h2(t)を得る(ST44)。得られたh2(t)は、セクション代入部44から復号部43に送信される。
【0238】
復号部43は、h1(t),h2(t)を1変数多項式演算部45に送信して減算させる。1変数多項式演算部45は、減算結果{h1(t)−h2(t)}を復号部43に送信する。
【0239】
復号部43は、減算結果{h1(t)−h2(t)}を1変数多項式因数分解部46に送信して因数分解させる(ST45)。1変数多項式因数分解部46は、因数分解結果のうち、最大次数の因子として既約多項式f(t)を決定し(ST46)、この既約多項式f(t)を復号部43に送信する。
【0240】
次に、復号部43は、f(t),h1(t)を1変数多項式剰余演算部48に送信する。
【0241】
1変数多項式剰余演算部48は、h1(t)をf(t)で除し、剰余として平文多項式m(t)を計算し(ST47)、復号部43に送信する。
【0242】
復号部43では、m(t)を平文展開部49に送信する。平文展開部49はこの平文多項式m(t)から平文mを展開し、得られた平文mを平文出力部50に送信する。平文出力部50はこの平文mを出力する(ST49)。これにより、復号装置40は、復号処理を終了する。
【0243】
上述したように本実施形態によれば、第1又は第2の実施形態の効果に加え、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある証明可能安全な公開鍵暗号方式を構成することができる。
【0244】
補足すると、本実施形態によれば、復号用の秘密鍵が代数曲面XのファイブレーションX(x,y,t)=0に対応する2つ以上のセクションであり、公開鍵が代数曲面XのファイブレーションX(x,y,t)であるという構成により、量子計算機が出現しても安全性を確保できる可能性があり、現在の計算機でも安全に実現可能であるとともに、小電力環境での実現可能性がある公開鍵暗号方式を構成できる。
【0245】
また、本実施形態によれば、次数l-1以下の平文多項式m(t)と、次数l以上のランダムな1変数既約多項式f(t)とを用いる構成により、前述した証明5に基づいて、IND−CPAの意味で証明可能安全な公開鍵暗号方式を構成できる。
【0246】
<第3の実施形態のバリエーション>
第6のバリエーションは、本実施形態の公開鍵におけるp,l,d,eを固定パラメータとする構成により、公開鍵のサイズを減らすバリエーションである。勿論これらの一部だけを固定にする利用方法も考えられる。
【0247】
本バリエーションにおいては、パラメータの一部が固定されることから、鍵生成時に制約があるものの、十分大きいl,d,eが取られていれば、何回かの試行で所望の公開鍵X(x,y,t)を生成可能である。
【0248】
第7のバリエーションは、暗号化に用いる式(16)の変形に関するバリエーションである。式(16)は、例えば
F(x,y,t)=m(t)−f(t)p(x,y,t)−X(x,y,t)q(x,y,t)
のように変形しても同様に暗号化/復号が可能であり、同様の安全性が証明可能である。このように本発明の趣旨に反しない範囲で暗号化の式を変形し、それに伴い復号処理を変更することが十分可能である。
【0249】
第8のバリエーションは、平文mを1変数既約多項式f(t)にも埋め込む方式である。前述した実施形態ではf(t)をランダムに生成する方式を示したが、秘密鍵無しにf(t)を求めることが困難であることも本発明の公開鍵暗号の性質であるから、f(t)にも平文情報を埋め込む方式が実現可能となっている。
【0250】
f(t)にも平文mを埋め込む場合、より大きなサイズの平文を一度に暗号化できる。但し、埋め込んだ結果f(t)を既約多項式とする必要から、特定の係数にはランダムな係数が入るように予め定めておく必要がある。既約多項式は極めて多く存在するため、一部の係数に平文mを埋め込んだとしても、ほとんどの場合、既約多項式を得ることができる。仮に得られなかった場合にはf(t)の次数を上げることにより、探索範囲を増やすことも可能である。このような変形を施しても同様の安全性を証明可能となっている。
【0251】
第9のバリエーションは、公開鍵から3変数多項式p(x,y,t)のx,yの最高指数としてのパラメータeを除く方式である。このパラメータeは、命題1に示したように、復号の失敗確率を表現する時の指数になるものである。即ち、安全性に関して直接の指標にならないため、復号失敗時には(p(x,y,t)を変更して)再暗号化する規則にすれば、パラメータeを公開鍵から外す実施形態も可能である。このような実施形態をとることにより、公開鍵サイズが小さくなる他、p(x,y,t)の生成を必要以上に制限する必要がなくなる。
【0252】
(第4の実施形態)
次に、本発明の第4の実施形態について説明する。本実施形態の公開鍵と秘密鍵は、第3の実施形態と同じである。本実施形態の公開鍵暗号は、受動的な攻撃に関して安全性(IND−CPA)を保証した第3の実施形態に比べ、より高い安全性を保証するものであり、具体的には、能動的な攻撃に関しても安全性(IND−CCA)を保証する。
【0253】
本実施形態は、第3の実施形態に示した公開鍵暗号がIND−CPAの意味での安全性を有することから、特許第3306384号公報に記載されている変換を用いることによってIND−CCAの意味で安全な公開鍵暗号を構成する。
【数45】

のように実行する。即ち、平文mとランダム要素r(第3の実施形態では3変数多項式p(x,y,t),q(x,y,t)や一変数多項式f(t)の各因子の係数などにあたる)に基づいて暗号化されていた公開鍵を、m‖rを平文として、m‖rのハッシュ値H(m‖r)をランダム要素として暗号化する方式に変換する。
【0254】
これに伴い復号処理においては、第3の実施形態と同様の復号処理で復号した後、平文m‖rから真のメッセージであるmを抽出すると共に、平文m‖rのハッシュ値H(m‖r)を計算し、H(m‖r)をランダム要素とする暗号文F’(x,y,t)を再現して入力された暗号文F(x,y,t)と比較し、一致している場合には復号された平文mを出力する。一致していない場合には復号結果を出力せず、無効な暗号文である旨の出力を行なう。
【0255】
しかし、特許第3306384号公報に記載の変換は、強い意味での安全性を主張するため、暗号文にある種の構造を持たせることから、第3の実施形態のようなランダム性の強い暗号文の構成が難しくなる。これに伴い、特許第3306384号公報に記載の暗号化の方式自体は(ランダム性という側面からみれば)弱いアルゴリズムとなっている。例えばp(x,y,t),q(x,y,t)で用いる多項式の項の種類、即ち
【数46】

において出現する項xiyjtkやxlymtnを決めておき、係数ai,j,k,bl,m,nにランダム要素H(m‖r)を割り振るような単純な変換を施すだけでは安全な方式を構成することができない。一方、本実施形態では、安全性を保ったまま変換を実施する具体的な方式を示す。
【0256】
(第4の実施形態の具体的な構成)
次に、本発明の第4の実施形態について説明する。なお、本実施形態の公開鍵と秘密鍵は第3の実施形態と同様なので、説明を省略する。鍵生成に関しても第3の実施形態と同様である。
【0257】
図21は本発明の第4の実施形態に係る暗号装置の全体構成図であり、図22は同実施形態における復号装置の全体構成図であって、図17又は図18と同一部分については同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【0258】
すなわち、本実施形態は、第3の実施形態の変形例であり、前述した通り、より高い安全性を保証するものであって、平文mに乱数rを連結してm‖rとし、このm‖rのハッシュ値H(m‖r)をランダム要素として用いている。
【0259】
具体的には、暗号装置30においては、平文埋め込み部33’、暗号化部34’及び多項式生成部36’が若干変形されており、乱数生成部38が付加されている。また、復号装置40においては、平文展開部49’及び平文出力部50’が若干変形されており、暗号文検証部51が付加されている。
【0260】
ここで、平文埋め込み部33’は、平文入力部31から送出された平文(メッセージ)mを受け、且つ公開鍵入力部32から送出された公開鍵を受けたとき、乱数生成部38に乱数生成を指示する機能と、平文mと乱数rとを連結して新たな平文M(=m‖r)を生成する機能と、公開鍵に基づいて、平文Mを1変数tで次数l-1以下の平文多項式M(t)の係数として埋め込む機能をもっている。
【0261】
暗号化部34’は、前述した機能に加え、図23〜図25に示す動作を実現させるように、多項式生成部36’を制御する機能をもっている。
【0262】
多項式生成部36’は、暗号化部34’に制御され、平文Mのハッシュ値H(M)に基づいて3変数x,y,tのランダムな多項式p(x,y,t),q(x,y,t)を生成するものである。多項式生成部36’は、平文Mのハッシュ値H(M)に基づいて3変数x,y,tのランダムな多項式p(x,y,t),q(x,y,t)の各項のx指数、y指数、t指数及び係数のうち、少なくとも2つ以上を生成する機能をもっている。
【0263】
乱数生成部38は、平文埋め込み部33’に制御され、固定長の乱数rを生成する機能と、生成した乱数rを平文埋め込み部33’に送出する機能とをもっている。
【0264】
一方、平文展開部49’は、復号部43から受けた平文多項式M(t)の係数から平文Mを抽出する機能と、この平文Mを暗号文検証部51に送出する機能とをもっている。
【0265】
平文出力部50’は、暗号文検証部51による判定結果が一致の場合、暗号文検証部51から受けた平文M又はメッセージmを出力する機能と、この判定結果が否の場合、暗号文無効情報を出力する機能をもっている。
【0266】
暗号文検証部51は、平文展開部49’により得られた平文Mに基づいて、この平文Mのハッシュ値H(M)を演算する機能と、得られたハッシュ値H(M)をメモリ(図示せず)に保持する機能と、メモリ内のハッシュ値H(M)に基づいて、3変数x,y,tの多項式p(x,y,t),q(x,y,t)を生成する機能と、各多項式p(x,y,t),q(x,y,t),f(t)とファイブレーションX(x,y,t)とに基づいて、暗号装置30の暗号化処理と同じ処理により、暗号文F’(x,y,t)(=Epk(M,p,q,f,X))を再現する機能と、入力された暗号文F(x,y,t)と再現された暗号文F’(x,y,t)とが一致するか否かを判定する機能と、判定結果に応じて平文出力部50’を制御する機能とをもっている。
【0267】
次に、以上のように構成された暗号装置及び復号装置の動作を図23〜図26のフローチャートを用いて説明する。
【0268】
(暗号化処理:図23〜図25)
ステップST31〜ST33までの処理は、前述した通りに実行される。
【0269】
次に、平文埋め込み部33’は、平文入力部31から入力された平文mに対し、乱数生成部38に乱数生成を指示する。乱数生成部38は、この指示により、固定長の乱数rを生成して平文埋め込み部33’に送信する(ST34’−1)。
【0270】
平文埋め込み部33’は、受信した乱数rを平文mに連結してM(=m‖r)を生成すると共に(ST34’−2)、Mを新たな平文として平文多項式M(t)を第3の実施形態と同じ処理で生成する(ST34’−3)。
【0271】
次に、本実施形態における3変数多項式p(x,y,t),q(x,y,t)の生成処理について説明する。暗号化部34’は、1変数既約多項式f(t)を1変数既約多項式生成部35に生成させた後(ST35)、M(=m‖r)のハッシュ値H(m‖r)を計算する(ST36’−1)。次に、暗号化部34’は、多項式生成部36’にp,l,d,e及びH(m‖r)を送信する。
【0272】
多項式生成部36’は、p,l,d,e及びH(m‖r)に基づいて、3変数多項式p(x,y,t),q(x,y,t)の各項がハッシュ値H(m‖r)の値を反映するように、3変数多項式p(x,y,t),q(x,y,t)を生成する。このとき、p(x,y,t)は、条件(13)と条件(14)を満たし、最高次数をe以上とするように、生成される。q(x,y,t)は、条件(15)を満たすように生成される。具体的な生成方法は以下の通りである。
【0273】
x,ey,etをex,ey がそれぞれdegxX(x,y,t),degyX(x,y,t)を超える自然数であり、かつ(ex+ey)d+et<lを満たすように定める(ST36’−2)。このようなex,ey,etはlを十分大きくとっているので具体的に定めることができる。
【0274】
更に、生成される多項式q(x,y,t)が条件(15)を満足するためにdx,dy,dtをdt<lなる条件の下で定める(ST36’−3)。続いて、次式に示すように、ブロックサイズbp,bqを定める(ST36’−4)。
【0275】
p=|p|+|ex|+|ey|+|et|,
q=|p|+|dx|+|dy|+|dt|
ここで、|a|はaのビット長を意味する。また、bpはp(x,y,t)の1つの項ai,j,kxiyjtkを生成するために必要なブロックサイズである。同様にbqはq(x,y,t)の1つの項bi,j,kxiyjtkを生成するために必要なブロックサイズである。
【0276】
これを受けて、H(m‖r)の前半分をbpビットずつgブロックに、後半分をbqビットずつhブロックに分解して
H(m‖r)=α1‖・・・‖αg‖β1‖・・・‖βh
とする(ST36−5’)。
【0277】
そしてp(x,y,t)=0として(ST36’−6)、3変数ランダム多項式p(x,y,t)を条件(14)を満たすように生成する。具体的には、H(m‖r)の前半分α1‖α2‖・・・‖αgの各ブロックに対して以下の操作をn=1・・・,gにおいて繰り返し行なう(ST36’−7〜ST36’−9)。
【0278】
ここで、ブロックの各αn
0|=|p|,|γ1|=|ex|,|γ2|=|ey|,|γ3|=|et|
の大きさで
αn=γ0(n)‖γ1(n)‖γ2(n)‖γ3(n)
のごとく分割される(ST36’−7)。
【0279】
a=γ0(n) (mod p)
i=γ1(n) (mod ex)
j=γ2(n) (mod ey)
k=γ3(n) (mod et)
(ST36’−8)
p(x,y,t)+=axiyjtk (ST36’−9)
なお、記号“+=”は、左辺に右辺を足し込む旨を意味する。
【0280】
このようにして完成されたp(x,y,t)は、条件(13)を満たすか否かが判定され(ST36’−10)、否の場合、多項式生成部36’は、暗号化部34’にその旨を出力する。
【0281】
暗号化部34’では、ステップST33終了後の状態に戻り、平文埋め込み部33’に対して平文の再埋め込みを指示する。以下、前述同様に、ステップST34〜ST36’−10までの処理が再度、実行される。
【0282】
一方、ステップST36’−10の判定の結果、p(x,y,t)が条件(13)を満たしたとする。この場合、q(x,y,t)=0として(ST37’−1)、3変数ランダム多項式q(x,y,t)を条件(15)を満たすように生成する。具体的には、H(m‖r)の後半分β1‖β2‖・・・‖βhの各ブロックに対して以下の操作をm=1・・・,hにおいて繰り返し行なう(ST37’−2〜ST37’−4)。
【0283】
ここで、ブロックの各βmは
0|=|p|,|ζ1|=|dx|,|ζ2|=|dy|,|ζ3|=|dt|
の大きさで
βn=ζ0(m)‖ζ1(m)‖ζ2(m)‖ζ3(m)
のごとく分割される(ST37’−2)。
【0284】
b=ζ0(m) (mod p)
i=ζ1(m) (mod dx)
j=ζ2(m) (mod dy)
k=ζ3(m) (mod dt)
(ST37’−3)
q(x,y,t)+=bxiyjtk (ST37’−4)
これにより、3変数多項式q(x,y,t)が生成される。多項式生成部36’は、これら3変数多項式p(x,y,t),q(x,y,t)を暗号化部34’に出力する。
【0285】
暗号化部34’は、M(t),f(t),p(x,y,t),q(x,y,t)を用いて
F(x,y,t)=M(t)+f(t)p(x,y,t)+X(x,y,t)q(x,y,t)によって暗号文F(x,y,t)を計算する(ST38’)。得られた暗号文F(x,y,t)は、前述同様に、暗号文出力部37から出力される(ST39)。
【0286】
(復号処理:図26)
ステップST41〜ST47までの処理は、前述した通りに実行される。これにより、復号部43では、ステップST41で入力された暗号文F(x,y,t)から、平文多項式M(t)が得られる。
【0287】
復号部43は、この平文多項式M(t)を平文展開部49’に送信する。平文展開部49’は、この平文多項式M(t)から平文Mを展開し(ST48’−1)、得られた平文Mを暗号文検証部51に送る。
【0288】
暗号文検証部51では、この平文Mからハッシュ値H(m‖r)を計算し(ST48’−2)、得られたH(m‖r)から暗号装置30の暗号化処理と同じ処理により、3変数多項式p(x,y,t),q(x,y,t)を生成する(ST48’−3)。次に、暗号文検証部51は、3変数多項式p(x,y,t),q(x,y,t)と、先に得られているf(t),M(t)とに基づいて、暗号文F’(x,y,t)を再現する(ST48’−4)。
【0289】
しかる後、暗号文検証部51は、ステップST41で入力された暗号文F(x,y,t)と、ステップST48’−4で再現した暗号文F’(x,y,t)とが一致するか否かを判定する(ST48’−5)。
【0290】
この判定結果が否の場合、暗号文検証部51は、平文出力部50’に暗号文が無効である旨の信号を送り、平文出力部50’は暗号文無効情報を出力する(ST48’−6)。
【0291】
一方、ステップ28’−5の判定結果が一致を示す場合、暗号文検証部51は、平文出力部50’に平文Mを送る。平文出力部50’は、平文Mを真の平文mに変換し、平文mを出力する(ST49)。
【0292】
上述したように本実施形態によれば、第3の実施形態の効果に加え、第4の実施形態のIND−CPAよりも安全であるIND−CCAの意味で証明可能安全な公開鍵暗号方式を構成することができる。
【0293】
補足すると、本実施形態では、メッセージmと乱数rを連結した平文Mを平文多項式M(t)の係数として埋め込む構成により、IND−CPAの意味で安全な公開鍵暗号方式を、IND−CCAの意味で証明可能安全な公開鍵暗号方式に変換している。従って、本実施形態によれば、IND−CCAの意味で証明可能安全な公開鍵暗号方式を構成することができる。
【0294】
<第4の実施形態のバリエーション>
第3の実施形態で述べた第6〜第9のバリエーションは、本実施形態でもそのまま成り立つ。すなわち、第6のバリエーションとして、公開鍵におけるp,l,d,eの一部又は全部を固定パラメータとし、公開鍵のサイズを減らすことができる。
【0295】
また、第7のバリエーションとして、暗号化に用いる式(16)を例えば、
F(x,y,t)=m(t)−f(t)p(x,y,t)−X(x,y,t)q(x,y,t)
のように変形して暗号化/復号してもよい。
【0296】
さらに、第8のバリエーションとして、平文M=m‖rを1変数既約多項式f(t)にも埋め込む方式としてもよい。この場合、暗号化処理及び復号処理のフローチャートはそれぞれ図27(ST34”−3,ST35”)又は図28(ST48”)に示すように変形される。これに伴い、平文埋め込み部33’、1変数既約多項式生成部35及び平文展開部49’は、それぞれ以下のように変形される。
【0297】
すなわち、平文埋め込み部33’は、メッセージmと乱数rを連結した平文Mを1変数tで次数l-1以下の平文多項式M(t)と次数l以上の1変数既約多項式f(t)の候補の一部の係数とに分担して埋め込むものに変形される。また、1変数既約多項式生成部35は、1変数既約多項式f(t)の候補の各係数のうち、平文Mが埋め込まれていない係数をランダムな値に設定し、1変数既約多項式f(t)を生成するものに変形される。さらに、平文展開部49’は、平文多項式M(t)の係数と既約多項式f(t)の一部の係数とから平文Mを抽出するものに変形される。
【0298】
以上のように、第4の実施形態においても、第3の実施形態で述べた第6〜第8のバリエーションを用いることができる。
【0299】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク(フロッピー(登録商標)ディスク、ハードディスクなど)、光ディスク(CD−ROM、DVDなど)、光磁気ディスク(MO)、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【0300】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【0301】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているOS(オペレーティングシステム)や、データベース管理ソフト、ネットワークソフト等のMW(ミドルウェア)等が上記実施形態を実現するための各処理の一部を実行しても良い。
【0302】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、LANやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【0303】
また、記憶媒体は1つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【0304】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の1つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【0305】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【0306】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【0307】
【図1】本発明の各実施形態における代数曲面を説明するための模式図である。
【図2】本発明の第1の実施形態に係る鍵生成装置の全体構成図である。
【図3】同実施形態における代数曲面形式テーブルを説明するための模式図である。
【図4】同実施形態における動作を説明するためのフローチャートである。
【図5】同実施形態における動作を説明するためのフローチャートである。
【図6】同実施形態における鍵生成装置の第2のバリエーションの全体構成図である。
【図7】同実施形態における第2のバリエーションの動作を説明するためのフローチャートである。
【図8】同実施形態における鍵生成装置の第1及び第2のバリエーションの全体構成図である。
【図9】本発明の第1の実施形態に係る鍵生成装置の全体構成図である。
【図10】同実施形態における動作を説明するためのフローチャートである。
【図11】同実施形態における動作を説明するためのフローチャートである。
【図12】同実施形態における鍵生成装置の第2のバリエーションの全体構成図である。
【図13】同実施形態における鍵生成装置の第1及び第2のバリエーションの全体構成図である。
【図14】同実施形態における第5のバリエーションの動作を説明するためのフローチャートである。
【図15】本発明の第3及び第4の実施形態における安全性証明を説明するための模式図である。
【図16】本発明の第3及び第4の実施形態における安全性証明を説明するための模式図である。
【図17】本発明の第3の実施形態に係る暗号装置の全体構成図である。
【図18】同実施形態に係る復号装置の全体構成図である。
【図19】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図20】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図21】本発明の第4の実施形態に係る暗号装置の全体構成図である。
【図22】同実施形態に係る復号装置の全体構成図である。
【図23】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図24】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図25】同実施形態における暗号装置の動作を説明するためのフローチャートである。
【図26】同実施形態における復号装置の動作を説明するためのフローチャートである。
【図27】同実施形態における暗号装置の第8のバリエーションの動作を説明するためのフローチャートである。
【図28】同実施形態における復号装置の第8のバリエーションの動作を説明するためのフローチャートである。
【符号の説明】
【0308】
10…鍵生成装置、11…パラメータ入力部、11a…素数格納部、11b…最大次数格納部、11c…有限体格納部、12…制御部、13…代数曲面決定部、14…セクション生成部、15…1変数多項式生成部、16…1変数多項式演算部、17…代数曲面生成部、18…1変数既約多項式最小次数生成部、19…鍵出力部、21…種数計算部、22…安全性検証部、30…暗号装置、31…平文入力部、32…公開鍵入力部、33,33’…平文埋め込み部、34,34’…暗号化部、35…1変数既約多項式生成部、36,36’…多項式生成部、37…暗号文出力部、38…乱数生成部、40…復号装置、41…暗号文入力部、42…鍵入力部、43…復号部、44…セクション代入部、45…1変数多項式演算部、46…1変数多項式因数分解部、47…多項式抽出部、48…1変数多項式剰余演算部、49,49’…平文展開部、50…平文出力部、51…暗号文検証部。

【特許請求の範囲】
【請求項1】
公開鍵の一部であり、且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データが記憶された形式データ記憶手段と、
【数1】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定手段と、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λx(t)を生成する第1の多項式生成手段と、
前記1変数多項式λx(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λy(t)を生成する第2の多項式生成手段と、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第3の多項式生成手段と、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第4の多項式生成手段と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成手段と、
前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(1,0))をランダムに生成する第5の多項式生成手段と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c10(t)を生成する第6の多項式生成手段と、
【数2】

前記各1変数多項式ux(t), uy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成手段と、
【数3】

前記各1変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成手段と
を備えたことを特徴とする鍵生成装置。
【請求項2】
公開鍵の一部であり、且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段と、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データが記憶された形式データ記憶手段と、
【数4】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定手段と、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λy(t)を生成する第1の多項式生成手段と、
前記1変数多項式λy(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λx(t)を生成する第2の多項式生成手段と、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第3の多項式生成手段と、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第4の多項式生成手段と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成手段と、
前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(0,1))をランダムに生成する第5の多項式生成手段と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c01(t)を生成する第6の多項式生成手段と、
【数5】

前記各1変数多項式ux(t), uy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成手段と、
【数6】

前記各1変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成手段と
を備えたことを特徴とする鍵生成装置。
【請求項3】
請求項1又は請求項2に記載の鍵生成装置において、
前記素数p、前記拡大次数r 及び前記次数d を含むパラメータを入力するためのパラメータ入力手段と、
このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項4】
請求項1乃至請求項3のいずれか1項に記載の鍵生成装置において、
前記生成されたファイブレーションX(x, y, t)における各々の変数x, y, t の次数degx X(x, y, t), degy X(x, y, t), degt X(x, y, t)及び前記次数d に基づいて、(degX(x, y, t)+degy X(x, y, t))d+degt X(x, y, t) 以上となるように、暗号化用のランダム1変数多項式の最小次数lを定めるランダム1変数多項式最小次数決定手段を更に備えたことを特徴とする鍵生成装置。
【請求項5】
請求項1乃至請求項4のいずれか1項に記載の鍵生成装置であって、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算手段と、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定手段と、
この判定の結果、種数g(C)が2未満のとき、前記形式データ決定手段から前記種数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項6】
請求項1乃至請求項4のいずれか1項に記載の鍵生成装置であって、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定手段と、
この判定の結果、総次数dcが4未満のとき、前記形式データ決定手段から前記総次数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項7】
請求項1乃至請求項6のいずれか1項に記載の鍵生成装置において、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算手段と、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定手段と、
この判定の結果、種数g(C)が2未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段と、
前記再選択した形式データを前記総次数判定手段に送出する送出手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項8】
請求項1乃至請求項6のいずれか1項に記載の鍵生成装置において、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定手段と、
この判定の結果、総次数dcが4未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段と、
前記再選択した形式データを前記総次数判定手段に送出する送出手段と
を更に備えたことを特徴とする鍵生成装置。
【請求項9】
公開鍵の一部であり、且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置のプログラムであって、
前記鍵生成装置のコンピュータを、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データが記憶された形式データ記憶手段、
【数7】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定手段、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λx(t)を生成する第1の多項式生成手段、
前記1変数多項式λx(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λy(t)を生成する第2の多項式生成手段、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第3の多項式生成手段、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第4の多項式生成手段、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成手段、
前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(1,0))をランダムに生成する第5の多項式生成手段、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c10(t)を生成する第6の多項式生成手段、
【数8】

前記各1変数多項式ux(t), uy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成手段、
【数9】

前記各1変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成手段、
として機能させるためのプログラム。
【請求項10】
公開鍵の一部であり、且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置のプログラムであって、
前記鍵生成装置のコンピュータを、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータが記憶されるパラメータ記憶手段、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データが記憶された形式データ記憶手段、
【数10】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記形式データ記憶手段内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定手段、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λy(t)を生成する第1の多項式生成手段、
前記1変数多項式λy(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λx(t)を生成する第2の多項式生成手段、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第3の多項式生成手段、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第4の多項式生成手段、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成手段、
前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(0,1))をランダムに生成する第5の多項式生成手段、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c01(t)を生成する第6の多項式生成手段、
【数11】

前記各1変数多項式ux(t), uy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成手段、
【数12】

前記各1変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成手段、
として機能させるためのプログラム。
【請求項11】
請求項9又は請求項10に記載のプログラムにおいて、
前記鍵生成装置のコンピュータを、
前記素数p、前記拡大次数r 及び前記次数d を含むパラメータを入力するためのパラメータ入力手段、
このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込手段、
として機能させるためのプログラム。
【請求項12】
請求項9乃至請求項11のいずれか1項に記載のプログラムにおいて、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションX(x, y, t)における各々の変数x, y, t の次数degx X(x, y, t), degy X(x, y, t), degt X(x, y, t)及び前記次数d に基づいて、(degX(x, y, t)+degy X(x, y, t))d+degt X(x, y, t) 以上となるように、暗号化用のランダム1変数多項式の最小次数lを定めるランダム1変数多項式最小次数決定手段、として更に機能させるためのプログラム。
【請求項13】
請求項9乃至請求項12のいずれか1項に記載のプログラムであって、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算手段、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定手段、
この判定の結果、種数g(C)が2未満のとき、前記形式データ決定手段から前記種数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段、
として更に機能させるためのプログラム。
【請求項14】
請求項9乃至請求項12のいずれか1項に記載のプログラムであって、
前記鍵生成装置のコンピュータを、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定手段、
この判定の結果、総次数dcが4未満のとき、前記形式データ決定手段から前記総次数判定手段までの処理を再実行するように、前記形式データ決定手段を制御する制御手段、
として更に機能させるためのプログラム。
【請求項15】
請求項9乃至請求項14のいずれか1項に記載のプログラムにおいて、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算手段、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定手段、
この判定の結果、種数g(C)が2未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段、
前記再選択した形式データを前記総次数判定手段に送出する送出手段、
を更に備えたプログラム。
【請求項16】
請求項9乃至請求項14のいずれか1項に記載のプログラムにおいて、
前記形式データ決定手段は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定手段、
この判定の結果、総次数dcが4未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択手段、
前記再選択した形式データを前記総次数判定手段に送出する送出手段、
を更に備えたプログラム。
【請求項17】
メモリを有し、公開鍵の一部であり且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置が実行する鍵生成方法であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータを前記メモリに記憶するパラメータ記憶工程と、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データを前記メモリに予め記憶する形式データ記憶工程と、
【数13】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (1, 0), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記メモリ内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定工程と、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λx(t)を生成する第1の多項式生成工程と、
前記1変数多項式λx(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λy(t)を生成する第2の多項式生成工程と、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλx(t)となり、且つ少なくとも一方の次数がdとなるように、変数xをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第3の多項式生成工程と、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第4の多項式生成工程と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成工程と、
前記決定された形式データにおける定数項c00(t)及び一次の項c10(t)x 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(1,0))をランダムに生成する第5の多項式生成工程と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c10(t)を生成する第6の多項式生成工程と、
【数14】

前記各1変数多項式ux(t), uy(t), cij(t), c10(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成工程と、
【数15】

前記各1変数多項式cij(t), c10(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成工程と
を備えたことを特徴とする鍵生成方法。
【請求項18】
メモリを有し、公開鍵の一部であり且つ有限体Fq(但しq=pr(pは素数、rは拡大次数))上定義された代数曲面XのファイブレーションX(x, y, t)=0 と、前記ファイブレーションX(x, y, t)=0に対応する2つのセクションD1,D2である秘密鍵とを生成するための鍵生成装置が実行する鍵生成方法であって、
前記公開鍵の他の一部であるセクションの最大の次数d 、前記素数p及び前記拡大次数r を含むパラメータを前記メモリに記憶するパラメータ記憶工程と、
前記ファイブレーションX(x, y, t)の形式データの候補を、下記式に基づいて、tの1変数多項式cij(t)を係数としたxijの多項式として表す複数の形式データを前記メモリに予め記憶する形式データ記憶工程と、
【数16】

但し、0≦i, 0≦j, 少なくとも(i, j)は(≧1, ≧1), (0, 1), (0, 0)を含む, 各形式データ間では互いに次数の組合せ(i, j)の集合が異なる、
前記メモリ内の各形式データのいずれかをランダムに選択することにより、前記ファイブレーションX(x, y, t)の形式データを決定する形式データ決定工程と、
前記次数d 未満の,Fq上定義されたランダムな1変数多項式λy(t)を生成する第1の多項式生成工程と、
前記1変数多項式λy(t)で割り切れる次数d 以下の,Fq上定義された1変数多項式λx(t)を生成する第2の多項式生成工程と、
前記1変数多項式λy(t)に基づいて、互いの差分{uy(t)−vy(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式uy(t), vy(t)を生成する第3の多項式生成工程と、
前記1変数多項式λx(t)に基づいて、互いの差分{ux(t)−vx(t)}がλy(t)となり、且つ少なくとも一方の次数がdとなるように、変数yをパラメータtで表示する次数d 以下の,Fq上定義された2つの1変数多項式ux(t), vx(t)を生成する第4の多項式生成工程と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t)に基づいて、前記2つのセクションD1:(x, y, t)=(ux(t), uy(t), t) 及びD2:(x, y, t)=(vx(t), vy(t), t)を生成するセクション生成工程と、
前記決定された形式データにおける定数項c00(t)及び一次の項c01(t)y 以外の項の係数である,Fq上定義された1変数多項式cij(t)(但し(i,j)≠(0,0),(0,1))をランダムに生成する第5の多項式生成工程と、
前記各1変数多項式ux(t), vx(t), uy(t), vy(t), cij(t)に基づいて、下記式に示す一次の項の係数である,Fq上定義された1変数多項式c01(t)を生成する第6の多項式生成工程と、
【数17】

前記各1変数多項式ux(t), uy(t), cij(t), c01(t)に基づいて、下記式に示す定数項である,Fq上定義された1変数多項式c00(t)を生成する第7の多項式生成工程と、
【数18】

前記各1変数多項式cij(t), c01(t), c00(t)を、前記決定された形式データに設定することにより、前記代数曲面XのファイブレーションX(x, y, t)を生成するファイブレーション生成工程と
を備えたことを特徴とする鍵生成方法。
【請求項19】
請求項17又は請求項18に記載の鍵生成方法において、
前記素数p、前記拡大次数r 及び前記次数d を含むパラメータを入力するためのパラメータ入力工程と、
このパラメータを前記パラメータ記憶手段に書き込むパラメータ書込工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項20】
請求項17乃至請求項19のいずれか1項に記載の鍵生成方法において、
前記生成されたファイブレーションX(x, y, t)における各々の変数x, y, t の次数degx X(x, y, t), degy X(x, y, t), degt X(x, y, t)及び前記次数d に基づいて、(degX(x, y, t)+degy X(x, y, t))d+degt X(x, y, t) 以上となるように、暗号化用のランダム1変数多項式の最小次数lを定めるランダム1変数多項式最小次数決定工程を更に備えたことを特徴とする鍵生成方法。
【請求項21】
請求項17乃至請求項20のいずれか1項に記載の鍵生成方法であって、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算工程と、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定工程と、
この判定の結果、種数g(C)が2未満のとき、前記形式データ決定工程から前記種数判定工程までの処理を再実行するように、前記形式データ決定手段を制御する制御工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項22】
請求項17乃至請求項20のいずれか1項に記載の鍵生成方法であって、
前記生成されたファイブレーションX(x, y, t)における変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定工程と、
この判定の結果、総次数dcが4未満のとき、前記形式データ決定工程から前記総次数判定工程までの処理を再実行するように、前記形式データ決定工程を制御する制御工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項23】
請求項17乃至請求項22のいずれか1項に記載の鍵生成方法において、
前記形式データ決定工程は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)に基づいて、当該ファイブレーションX(x, y, t)を1変数関数体Fp(t)上の代数曲線C(x, y)とみなしたときの種数g(C)を計算する種数計算工程と、
前記計算された種数g(C)が2未満であるか否かを判定する種数判定工程と、
この判定の結果、種数g(C)が2未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択工程と、
前記再選択した形式データを前記総次数判定工程に送出する送出工程と
を更に備えたことを特徴とする鍵生成方法。
【請求項24】
請求項17乃至請求項22のいずれか1項に記載の鍵生成方法において、
前記形式データ決定工程は、
前記選択した形式データにおけるファイブレーションX(x, y, t)の変数x, yに関する総次数dc=degx X(x, y, t)+degy X(x, y, t)が4未満か否かを判定する総次数判定工程と、
この判定の結果、総次数dcが4未満のとき、前記選択した形式データとは異なる形式データを再選択する再選択工程と、
前記再選択した形式データを前記総次数判定工程に送出する送出工程と
を更に備えたことを特徴とする鍵生成方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate