(57)【要約】【課題】素数位数であっても代数的トーラスT2r(Fq)を表すアフィン表現から代数的トーラスT2(Fq^r)を表す射影表現への変換が可能であると共に、変換後に行う演算処理の処理負荷を軽減可能な表現変換技術を提供する。【解決手段】取得部１０１は、代数的トーラスT6(Fp^r)上のアフィン表現で表現された元（c0,c1）と、2次拡大の法多項式を決定するシステムパラメータwと、3次拡大の法多項式を決定するシステムパラメータδとを取得する。乗算部１０２は、（c0,c1）,w,δを用いて、（c0,c1）の元が代数的トーラスT2r(Fq)に含まれる条件と、2次拡大の方多項式及び基底と3次拡大の法多項式及び基底とにより定まる乗算を行う。加減算部１０３は、乗算部１０２が乗算を行った結果を用いて、加算を行う。出力部１０４は、代数的トーラスT2(Fq^r)の射影表現で表現された元を出力する。【選択図】        図１
2010049217.tif 000002
【特許請求の範囲】
【請求項１】
2r次代数的トーラスT2r(Fq)（r：素数,q：整数）を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換を行う表現変換装置であって、
2r次代数的トーラスT2r(Fq)のアフィン表現で表現される元(c0, c1,…, cr-2)（ci：有限体Fqの元：0≦i≦r-2）を取得する取得部と、
取得された前記元に対して、2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件と、2次拡大の法多項式及び基底とr次拡大の法多項式及び基底とにより定まる乗算を行う乗算部と、
前記条件と前記法多項式と前記基底とにより定まる加減算を行い、2次代数的トーラスT2(Fq^r)の射影表現で表現された元(a0, a1,…, ar-1, b0, b1,…, br-1) （aj, bj：Fqの元：0≦j≦r-1）を得る加減算部と、
射影表現で表現された前記元を出力する出力部とを備え、
xは、拡大体Fq^rから拡大体Fq^2rへの2次拡大の際に添加する元であり、
2次拡大の前記法多項式は、「f2(x) = x^2-δ」であり、その基底は{1, x}である
ことを特徴する表現変換装置。
【請求項２】
「α= (a0, a1,…, ar-1)」,「β= (b0, b1,…, br-1)」は、拡大体Fq^rの元であり、
2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件は、条件式「(α+βx)^Φ2r(q)=1」（Φn(q)：円周n等分多項式）を満たすことであり、
前記乗算部は、取得された前記元に対して、前記条件式と、2次拡大の前記法多項式及び前記基底とr次拡大の前記法多項式及び前記基底とにより定まる乗算を行う
ことを特徴する請求項１に記載の表現変換装置。
【請求項３】
yは、拡大体Fpから拡大体Fp^rへのr次拡大の際に添加する元であり、
wは、拡大体Fpの元であり、
3次拡大の前記法多項式は、「f3(y) = y^r-w」であり、その基底は{1, y, …, y^(r-1)}であり、
前記乗算部は、取得された前記元に対して、前記条件と、2次拡大の前記法多項式及び前記基底と3次拡大の前記法多項式及び前記基底とにより定まる乗算を行う
ことを特徴する請求項１又は２に記載の表現変換装置。
【請求項４】
「ｒ＝3」であり、
(c0, c1)は、6次代数的トーラスT6(Fq)のアフィン表現で表現された元であり、
(a0, a1, a2, b0, b1, b2)は、2次代数的トーラスT2(Fq^3)の射影表現で表現された元であり、
2次代数的トーラスT2(Fq^3)の元が6次代数的トーラスT6(Fq) に含まれる条件は、条件式「(α+βx)q^2-q+1=1」を満たすことであり、
前記取得部は、(c0, c1)を取得し、
前記乗算部は、取得された前記元に対して、前記条件式と、2次拡大の前記法多項式及び前記基底とr次拡大の前記法多項式及び前記基底とにより定まる乗算を行い、
前記出力部は、(a0, a1, a2, b0, b1, b2)を出力する
ことを特徴する請求項１乃至３のいずれか一項に記載の表現変換装置。
【請求項５】
δは、有限体Fqの元であり、
「β≠0」のとき「α/β=γ」とすると、
2次代数的トーラスT2(Fq^3) の元が6次代数的トーラスT6(Fq) に含まれる条件は、条件式「γ^(q^2+q) + γ^(q+1) + γ^(q^2+1) = -δ」を満たすことであり、
前記乗算部は、取得された前記元に対して、前記条件式と、2次拡大の前記法多項式及び前記基底と3次拡大の前記法多項式及び前記基底とにより定まる乗算を行う
ことを特徴する請求項４に記載の表現変換装置。
【請求項６】
前記乗算部は、
t1=c0×c1×d（d：有限体Fqの任意の元）
t2=c1^2×d（^：べき乗）
t3=c0^2
a2=t4×w-1×d
t5=c1×d
を計算し、
前記加減算部は、
a0=t1
a1=t2
t4=t3+δ/3
b0=t5
b1=0
b2=0
を計算する
ことを特徴する請求項５に記載の表現変換装置。
【請求項７】
前記乗算部は、
t1=c0×c1
t2=c1^2（^：べき乗）
t3=c0^2
a2=t4×w^{-1}
を計算し、
前記加減算部は
a0=t1
a1=t2
t4=t3+δ/3
b0=c1
b1=0
b2=0
を計算する
ことを特徴する請求項５に記載の表現変換装置。
【請求項８】
前記乗算部は、
t1=c0×c2×d（d：有限体Fqの任意の元）
t2=c2^2×d（^：べき乗）
t3=c0^2
a1=t4×w^{-1}×d
t5=c2×d
を計算し、
前記加減算部は、
a0=t1
a3=t2
t4=t3+δ/3
b0=t5
b1=0
b2=0
を計算する
ことを特徴する請求項５に記載の表現変換装置。
【請求項９】
前記乗算部は、
t1=c0×c2
t2=c2^2（^：べき乗）
t3=c0^2
a1=t4×w^{-1}
を計算し、
前記加減算部は、
a0=t1
a3=t2
t4=t3+δ/3
b0=c2
b1=0
b2=0
を計算する
ことを特徴する請求項５に記載の表現変換装置。
【請求項１０】
2r次代数的トーラスT2r(Fq)（r：素数,q：整数）を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換後に演算を行う演算装置であって、
2r次代数的トーラスT2r(Fq) のアフィン表現で表現される元(c0, c1,…, cr-2)（ci：Fqの元：0≦i≦r-2）を取得する取得部と、
取得された前記元に対して、2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件と、2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}とr次拡大の法多項式及び基底とにより定まる乗算を行う乗算部と、
前記条件と前記法多項式と前記基底とにより定まる加減算を行い、2次代数的トーラスT2(Fq^r)の射影表現で表現された元(a0, a1,…, ar-1, b0, b1,…, br-1) （aj, bj：Fqの元：0≦j≦r-1）を得る加減算部と、
射影表現で表現された前記元に基づいて、2次拡大の前記法多項式及び前記基底とr次拡大の前記法多項式及び前記基底とにより定まる演算を行う演算部とを備える
ことを特徴とする演算装置。
【請求項１１】
前記演算が行われた前記元をアフィン表現に変換することにより圧縮する圧縮部を更に備える
ことを特徴とする請求項１０に記載の演算装置。
【請求項１２】
前記演算部は、射影表現で表現された前記元を用いて、射影表現で前記演算を行う
ことを特徴とする請求項１０又は１１に記載の演算装置。
【請求項１３】
射影表現で表現された前記元を拡大体表現に変換する変換部を更に備え、
前記演算部は、拡大体表現で表現された前記元に対して、拡大体表現で前記演算を行う
ことを特徴とする請求項１０又は１１に記載の演算装置。
【請求項１４】
前記演算部は、
射影表現で表現された前記元である平文と、公開鍵とを取得する取得部と、
前記平文と前記公開鍵とを用いて公開鍵暗号方式により前記平文を暗号化する暗号部と、
暗号化された平文である暗号文を出力する出力部とを有する
ことを特徴とする請求項１０に記載の演算装置。
【請求項１５】
前記演算部は、
射影表現で表現された前記元であり公開鍵暗号方式により暗号化された暗号文と、秘密鍵とを取得する取得部と、
前記暗号文と前記秘密鍵とを用いて公開鍵暗号方式により前記暗号文を復号する復号部と、
復号された暗号文である平文を出力する出力部とを有する
ことを特徴とする請求項１０に記載の演算装置。
【請求項１６】
前記演算部は、
射影表現で表現された前記元である公開鍵を取得する取得部と、
KEM（Key Encapsulation Mechanism）の暗号化処理により前記公開鍵を用いて共通鍵を暗号化する暗号部と、
暗号化された前記共通鍵を出力する出力部とを有する
ことを特徴とする請求項１０に記載の演算装置。
【請求項１７】
射影表現で表現された前記元であってKEM（Key Encapsulation Mechanism）の暗号化処理により暗号化された共通鍵を取得する取得部と、
KEM（Key Encapsulation Mechanism）の復号処理により前記共通鍵を復号する復号部と、
復号された前記共通鍵を出力する出力部とを有する
ことを特徴とする請求項１０に記載の演算装置。
【請求項１８】
前記暗号部は、前記平文と前記公開鍵とを用いて、Cramer-Shoup暗号方式により前記平文を暗号化する
ことを特徴とする請求項１４に記載の演算装置。
【請求項１９】
前記復号部は、前記暗号文と前記秘密鍵とを用いて、Cramer-Shoup暗号方式により前記暗号文を復号する
ことを特徴とする請求項１５に記載の演算装置。
【請求項２０】
前記暗号部は、Cramer-Shoup暗号方式におけるKEM（Key Encapsulation Mechanism）の暗号化処理により前記共通鍵を暗号化する
ことを特徴とする請求項１６に記載の演算装置。
【請求項２１】
前記復号部は、Cramer-Shoup暗号方式におけるKEM（Key Encapsulation Mechanism）の復号処理により前記共通鍵を復号する
ことを特徴とする請求項１７に記載の演算装置。
【請求項２２】
前記演算部は、
公開鍵の生成元であり射影表現で表現された元と、秘密鍵とを取得する取得部と、
前記元と前記秘密鍵とを用いて、公開鍵に含まれる公開鍵成分を生成する鍵生成部と、
生成された前記公開鍵成分を含む公開鍵を出力する出力部とを有する
ことを特徴とする請求項１０に記載の演算装置。
【請求項２３】
前記鍵生成部は、前記元と前記秘密鍵とを用いて、Cramer-Shoup暗号方式により前記公開鍵成分を生成する
ことを特徴とする請求項２２に記載の演算装置。
【請求項２４】
取得部と、乗算部と、加減算部と、出力部とを備え、2r次代数的トーラスT2r(Fq)（r：素数,q：整数）を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換を行う表現変換装置で実行される表現変換方法であって、
前記取得部が、2r次代数的トーラスT2r(Fq)のアフィン表現で表現される元(c0, c1,…, cr-2)（ci：有限体Fqの元：0≦i≦r-2）を取得する取得部と、
前記乗算部が、取得された前記元に対して、2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件と、2次拡大の法多項式及び基底とr次拡大の法多項式及び基底とにより定まる乗算を行う乗算部と、
前記加減算部が、前記条件と前記法多項式と前記基底とにより定まる加減算を行い、2次代数的トーラスT2(Fq^r)の射影表現で表現された元(a0, a1,…, ar-1, b0, b1,…, br-1) （aj, bj：Fqの元：0≦ｊ≦r-1）を得る加減算部と、
前記出力部が、射影表現で表現された前記元を出力する出力部とを含み、
xは、拡大体Fq^rから拡大体Fq^2rへの2次拡大の際に添加する元であり、
2次拡大の前記法多項式は、「f2(x) = x^2-δ」であり、その基底は{1, x}である
ことを特徴とする表現変換方法。
【請求項２５】
請求項２４に記載の表現変換方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、2r次代数的トーラスT2r(Fq)を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換を行う表現変換装置、演算装置、表現変換方法及びプログラムに関する。
【背景技術】
【０００２】
事前の鍵共有なしに安全な通信を実現する公開鍵暗号はネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキームやプロトコルが用いられるようになってきた。公開鍵暗号において現在の典型的な暗号系サイズは1024ビットであるが、解読が困難とされる暗号系サイズは年々大きくなっている。計算機の進歩とともに攻撃者の能力も上がっているためである。公開鍵暗号では公開鍵サイズや暗号文サイズは、方式により異なるが、暗号系サイズの数倍となることもある。このため、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。このような背景から、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する方法が提案されている（例えば、非特許文献１参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。小さいビット数の表現へ変換を行う写像をρと書き、RS（Rubin-Silverberg）圧縮写像と呼ぶことにする。暗号文を圧縮する場合の具体例を示す。ＲＳ圧縮写像では、暗号文cを入力として計算を行い、以下の式１により、圧縮暗号文γを得る。
ρ(c)=γ・・・（１）
【０００３】
元のビット数の表現に戻すには、ρの逆写像を計算すれば良い。ρの逆写像をρ-1と書き、RS伸長写像と呼ぶことにする。RS伸長写像では、圧縮暗号文としてγが与えられたときに計算を行い、以下の式２により、cを得る。
ρ-1 (γ)= c・・・（２）
【０００４】
尚、代数的トーラスを表現する方法には、アフィン表現、射影表現及び拡大体表現がある（例えば、非特許文献２参照）。このような代数的トーラスにおいて伸張写像とは、代数的トーラスの元をアフィン表現から射影表現に変換したり、射影表現から拡大体表現に変換したり、アフィン表現から拡大体表現に変換したりすることである。一方で、代数的トーラスの元を拡大体表現から射影表現に変換したり、射影表現からアフィン表現に変換したり、拡大体表現からアフィン表現に変換したりすることが圧縮写像に相当する。このような代数的トーラスを用いた圧縮写像や伸長写像は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用できる。例えば非特許文献３では素体上の代数的トーラスを用いたElGamal暗号やＤＨ鍵交換が提案されている。また、非特許文献３では、Cramer-Shoup暗号が提案されている。Cramer-Shoup暗号は標準モデルでの安全性が証明されている方式である。例えば、平文や暗号文は、位数が素数である素体の乗法群G~の素数位数部分群Gの元とする。このとき、平文や暗号文は素体の乗法群G~として表現され、小さな群Gの元を大きな群G~で表現するという無駄が生じていた。そこで、Cramer-Shoup暗号におけるG~を拡大体の乗法群とし、Gを代数的トーラスとすれば、平文や暗号文はGの元でありGで表現でき、表現の無駄をなくすことができる。または、Cramer-Shoup暗号におけるG~を拡大体の乗法群とし、Gを代数的トーラスの安全な部分群とすれば、表現の無駄を小さくすることができる。なお、代数的トーラスを適用して表現の無駄をなくす、または、小さくすることがきる暗号はElGamal暗号やＤＨ鍵交換やCramer-Shoup暗号に限定されない。
【０００５】
RS圧縮写像とRS伸長写像とは、素体上で定義された代数的トーラスT6(Fp)を圧縮したり伸長したりする。ここで、暗号系サイズを2048ビットとする。位数p（素数位数）の素体についてpのサイズは少なくとも「ceil(2048/6)=342」ビットとなる。ceil(x)は天井関数と呼ばれx以上の最小の整数を返す。このpのサイズは計算機のワード長、例えば32ビットや64ビットを超えている。代数的トーラス上の演算は、代数的トーラスが定義されている有限体ないしその基礎体上の演算で実現される。よって、素体Fp上で定義された代数的トーラスTn(Fp)については素体Fp上の演算を用いて、代数的トーラスTn(Fp)上の演算を実現する。素体のサイズがワード長を超えていると、計算機で扱いにくい。
【０００６】
そこで、素体のサイズを小さくするために、拡大体Fp^r上で定義された代数的トーラスT6(Fp^r)を用いることを考える。位数p^rの拡大体について、pのサイズは少なくとも「ceil(2048/(6*r))」である。拡大次数rを調整することでpのサイズを小さくできる。例えば、「r=24」のときpは15ビット、「r=27」のときpは13ビットである。このとき、RS圧縮写像とＲＳ伸長写像とはこのような拡大次数では使えない。Rubin-Silverbergの方法では、6次拡大体を3次拡大の2次拡大として円分体または円分体の部分体を用いて構成している。円分体の法多項式である円分多項式が拡大体上で既約になる条件は厳しい。素数位数の代数的トーラスを構成するために拡大次数rに課される条件と矛盾する場合もある。
【０００７】
一方、拡大体上で定義された代数的トーラスの圧縮写像や伸長写像については、例えば、非特許文献４に提案されている写像がある。これらをGPS（Granger-Page-Stam）圧縮写像、GPS伸長写像と各々呼ぶことにする。Granger-Page-Stamの方法では、６次拡大体を３次拡大の２次拡大としてDuursma-Lee法（Tateペアリングの計算法の１つ）と同様に構成している。Duursma-Lee法において「p=3」である。
【０００８】
【非特許文献１】K. Rubin and A. Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003.
【非特許文献２】Steven Galbraith, “Disguising tori and elliptic curves”, IACR e-print Archive 2006/248, http://eprint.iacr.org/2006/248
【非特許文献３】R. Cramer and V. Shoup, "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack", CRYPTO'98, LNCS 1462, pp.13-25, 1998.
【非特許文献４】R. Granger, D. Page and M. Stam, "On Small Characteristic Algebraic Tori in Pairing Based Cryptography", LMS Journal of Computation and Mathematics, 9, pp. 64-85, 2006.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この場合、素数位数の代数的トーラスを構成するために拡大次数rに課される条件の下でrを探索すると、適当なパラメータが見つからない。つまり、拡大体上で定義されたトーラスを用い、かつ、その位数を素数とすると、非特許文献１や非特許文献４に示される圧縮写像や伸長写像は利用できない恐れがあった。また、一般的な伸張写像を利用しようとすると、アフィン表現から射影表現への変換後の暗号化処理や復号処理などの演算処理の処理負荷が重くなる恐れがあった。
【００１０】
本発明は、上記に鑑みてなされたものであって、2r次代数的トーラスT2r(Fq)を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換後に素数位数の代数的トーラスにおいても演算処理を可能にすると共に、演算処理の処理負荷を軽減可能な表現変換装置、演算装置、表現変換方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、本発明は、2r次代数的トーラスT2r(Fq)（r：素数,q：整数）を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換を行う表現変換装置であって、2r次代数的トーラスT2r(Fq)のアフィン表現で表現される元(c0, c1,…, cr-2)（ci：有限体Fqの元：0≦i≦r-2）を取得する取得部と、取得された前記元に対して、2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件と、2次拡大の法多項式及び基底とr次拡大の法多項式及び基底とにより定まる乗算を行う乗算部と、前記条件と前記法多項式と前記基底とにより定まる加減算を行い、2次代数的トーラスT2(Fq^r)の射影表現で表現された元(a0, a1,…, ar-1, b0, b1,…, br-1) （aj, bj：Fqの元：0≦ｊ≦r-1）を得る加減算部と、射影表現で表現された前記元を出力する出力部とを備え、xは、拡大体Fq^rから拡大体Fq^2rへの2次拡大の際に添加する元であり、2次拡大の前記法多項式は、「f2(x) = x^2-δ」であり、その基底は{1, x}であることを特徴する。
【００１２】
また、本発明は、取得部と、乗算部と、加減算部と、出力部とを備え、2r次代数的トーラスT2r(Fq)（r：素数,q：整数）を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換を行う表現変換装置で実行される表現変換方法であって、前記取得部が、2r次代数的トーラスT2r(Fq)のアフィン表現で表現される元(c0, c1,…, cr-2)（ci：有限体Fqの元：0≦i≦r-2）を取得する取得部と、前記乗算部が、取得された前記元に対して、2次代数的トーラスT2(Fq^r) の元が2r次代数的トーラスT2r(Fq) に含まれる条件と、2次拡大の法多項式及び基底とr次拡大の法多項式及び基底とにより定まる乗算を行う乗算部と、前記加減算部が、前記条件と前記法多項式と前記基底とにより定まる加減算を行い、2次代数的トーラスT2(Fq^r)の射影表現で表現された元(a0, a1,…, ar-1, b0, b1,…, br-1) （aj, bj：Fqの元：0≦ｊ≦r-1）を得る加減算部と、前記出力部が、射影表現で表現された前記元を出力する出力部とを含み、xは、拡大体Fq^rから拡大体Fq^2rへの2次拡大の際に添加する元であり、2次拡大の前記法多項式は、「f2(x) = x^2-δ」であり、その基底は{1, x}であることを特徴とする。
【００１３】
また、本発明は、プログラムであって、上記の表現変換方法をコンピュータに実行させる。
【発明の効果】
【００１４】
本発明によれば、2r次代数的トーラスT2r(Fq)を表すアフィン表現から2次代数的トーラスT2(Fq^r)を表す射影表現への変換後に素数位数の代数的トーラスにおいても演算処理を可能にすると共に、演算処理の処理負荷を軽減可能になる。
【発明を実施するための最良の形態】
【００１５】
以下に添付図面を参照して、この発明にかかる表現変換装置、演算装置、表現変換方法及びプログラムの最良な実施の形態を詳細に説明する。
【００１６】
[第１の実施の形態]
（１）構成
まず、本実施の形態にかかる伸張写像の計算原理について説明する。ここでの伸張写像は、位数qをp^m（p:素数、m:整数）と表し、2r次代数的トーラスT2r(Fp^m)を表すアフィン表現から2次代数的トーラスT2(Fp^rm)を表す射影表現への変換を対象とする。例えば「r=3」であるとき、6次拡大体を3次拡大の2次拡大として一般的な拡大を用いて構成することが考えられる。一般的な拡大体上の演算は効率が良いとはいえない。そこで、本実施の形態においては、6次拡大体を3次拡大の2次拡大として構成する。この場合、Granger-Page-Stamの方法では、3次拡大を3項式で構成し、2次拡大を2項式で構成したが、本実施の形態においては、3次拡大も2次拡大も各々2項式で構成する。2項式で拡大すると拡大体上の演算が簡単になるというメリットがあるからである。従って、本実施の形態においては、このような演算が可能になるような伸長写像を構成する。
【００１７】
まず、射影表現をアフィン表現に変換する計算式を開示し、得られた計算式からアフィン表現から射影表現へ変換する逆写像の計算式を開示する。代数的トーラスT6(Fp^m)は拡大体Fp^6mの乗法群の部分群であるので、拡大体Fp^6mの表現で表すことができる。これが拡大体表現である。拡大体表現では、拡大体Fp^mの元６つでT6(Fp^m)の１つの元を表す。同様にして、代数的トーラスT6(Fp^m)は代数的トーラスT2(Fp^3m)の部分群であるので、代数的トーラスT2(Fp^3m)の表現で表すことができる。これが射影表現である。代数的トーラスT2(Fp^3m)の位数は(p^3m+1)である。「＾」は、べき乗を表す。拡大体Fp^6mの乗法群の元である位数(p^6m-1)の元について、(p^3m+1)/(p^6m-1)乗すれば、位数(p^3m+1)の元となる。つまり、T2(Fp^3m)の元となる。「(p^3m+1)/(p^6m-1) = p^3m-1」であるから、拡大体Fp^6mの元を「α+βx」とすると、以下の式３で表されるものが、代数的トーラスT2(Fp^3m)の元である。
【００１８】
【数１】
2010049217.tif 000003
【００１９】
ここで、αとβとは拡大体Fp^3mの元である。xは拡大体Fp^3mから拡大体Fp^6mへの2次拡大の際に添加する元である。
【００２０】
また、2次拡大の法多項式は「f2(x) = x^2-δ」とし、基底は{1, x}とする。δはFp^mの元である。3次拡大の法多項式は「f3(y) = y^3-w」とし、基底は{1, y, y^2}とする。yは拡大体Fp^mから拡大体Fp^3mへの3次拡大の際に添加する元である。wは拡大体Fp^mの元である。
【００２１】
射影表現は代数的トーラスT2(Fp^3m)の元を表す表現であった。射影表現の元を代数的トーラスT6(Fp^m)の位数乗して「1」となる元は、代数的トーラスT6(Fp^m)の元である。即ち、以下の条件式４を満たすことがαとβとの条件となる。
【００２２】
【数２】
2010049217.tif 000004
【００２３】
この条件式４は、上述した2次拡大の法多項式「f2(x) = x^2-δ」を用いて以下の式５のように書き換えることができる。
【００２４】
【数３】
2010049217.tif 000005
【００２５】
2次拡大の法多項式f2(x)が既約となる条件より、δの(p^3m-1)/2乗は「1」とはならない。即ち、式５の左辺の第１項は「０」とはならない。このため、当該左辺の第２項が「0」となる以下の式６を解く。
【００２６】
【数４】
2010049217.tif 000006
【００２７】
ここで、δが拡大体Fp^mの元として、「β≠0」のとき、式６は、以下の式７のように書き換えることができる。
【００２８】
【数５】
2010049217.tif 000007
【００２９】
ここで、「γ=α/β」と置くと、式７は、以下の式８のように書き換えることができる。
【００３０】
【数６】
2010049217.tif 000008
【００３１】
更に、γを、上述した3次拡大の法多項式におけるyを用いて以下の式９により定義する。
【００３２】
【数７】
2010049217.tif 000009
【００３３】
そして、式９を用いて式８を計算すると、式９の右辺の第２項であるyの項と第３項であるy^2の項とは「0」となり第１項だけが残り、以下の式１０が得られる。
【００３４】
【数８】
2010049217.tif 000010
【００３５】
ここで、「c1≠0」のときc2はc0とc1とを用いて計算することができ、以下の式１１が得られる。
【００３６】
【数９】
2010049217.tif 000011
【００３７】
よって、T6(Fp^m)の元はc0とc1とを用いて一意に定まる。これがアフィン表現である。これを射影表現に変換するには、以下の式１２により、ψ（c0,c1）を計算すれば良い。
【００３８】
【数１０】
2010049217.tif 000012
【００３９】
更に、式１２の右辺の分母及び分子に「w^(-1)」を掛けると、以下の式１３が成り立つ。
【００４０】
【数１１】
2010049217.tif 000013
【００４１】
尚、「c2≠0」のときc1はc0とc2とを用いて計算することができる。従って、T6(Fp^m)の元はc0とc2とを用いて一意に定まるともいえる。このように定められたアフィン表現を射影表現に戻す場合には、以下の式１４により、ψ（c0,c2）を計算すれば良い。
【００４２】
【数１２】
2010049217.tif 000014
【００４３】
更に、式１４の右辺の分母及び分子に「w^(-1)」を掛けると、以下の式１５が成り立つ。
【００４４】
【数１３】
2010049217.tif 000015
【００４５】
一方、「c1=0」となることは無いことが証明される。このためには「-δ/3」が平方非剰余であることを示せば良い。2次拡大の法多項式「f2(x) = x^2-δ」と2次拡大の法多項式「f3(y) = y^3-w」及びr次拡大の法多項式「gr(z)=z^r-s」が既約である条件（例えば、参考文献１又は参考文献２参照）より、「3|mならば3|(p-1)、かつ、「3|(p^m-1)」である。
（参考文献１）R. Lidl and H. Niederreiter, “Finite Fields”, vol. 20 of Encyclopedia of Mathmatics and its Applications. Cambridge univ. press, 1983.
（参考文献２）D. V. Bailey and C. Paar, “Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms”, CRYPTO 1998, LNCS 1462, 472-485, 1998.
【００４６】
まず、「-3」についてFpで平方剰余であるか又は平方非剰余であるか調べる。これは、平方剰余記号と、第１補充法則と相互法則とを用いると、以下の式１６により調べることができる。
【００４７】
【数１４】
2010049217.tif 000016
【００４８】
ここで「p%3」はpを「3」で割った余りを表し、「1」のとき平方剰余であり、「2」のとき平方非剰余である。「p>2」とすると「3|(p-1)」のとき平方剰余であり、「3|(p-2)」のとき平方非剰余である。「-3」がFpで平方剰余であれば拡大体Fp^mでも平方剰余である。何故ならば、以下の式１７が成立するからである。
【００４９】
【数１５】
2010049217.tif 000017
【００５０】
この逆は必ずしも成り立たない。「-3」がFpで平方非剰余であれば、mが「2」で割り切れるときFp^mで平方剰余であり、mが「2」で割り切れないときFp^mでも平方非剰余である。何故ならば、以下の式１８が成立するからである。
【００５１】
【数１６】
2010049217.tif 000018
【００５２】
さて、「-3」がFp^mで平方剰余のとき、「-δ/3」はFp^mで平方非剰余である。何故ならば、δが拡大体Fp^mで平方非剰余であるからである。素数位数である代数的トーラスT6(Fp^m)を得るためには「m=2^a×3^b」となるので、「3|m」のとき「3|(p-1)」であり、「-3」が拡大体Fp^mで平方剰余である。「2|m」ならば、「-3」が拡大体Fp^mで平方剰余である。よって、素数位数の代数的トーラスを考えるときはいつも、「-δ/3」は拡大体Fp^mで平方非剰余である。
【００５３】
＜伸張装置の構成＞
次に、以上のような伸張写像を行う表現変換装置である伸張装置の構成について説明する。伸張装置は、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００５４】
このようなハードウェア構成において、伸張装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図１は、本実施の形態にかかる伸張装置の機能的構成を例示する図である。同図に示されるように、伸張装置１００は、取得部１０１と、乗算部１０２と、加減算部１０３と、出力部１０４とを有する。これらの各部の実体は、ＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００５５】
「r=3」である場合の各部の機能について説明する。取得部１０１は、伸張写像の対象となる代数的トーラスT6(Fp^m)のアフィン表現で表現された元（c0,c1）を取得する。c0,c1は各々拡大体Fp^mの元である。これらは外部装置から通信Ｉ／Ｆを介して受信することにより取得するようにしても良いし、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体から読み出すことにより取得するようにしても良い。また、取得部１０１は、2次拡大の法多項式を決定するシステムパラメータwと、3次拡大の法多項式を決定するシステムパラメータδとを取得する。wとδとは上述したように拡大体Fp^mの元である。システムパラメータw,δは、ＨＤＤなどの外部記憶装置に予め記憶されていても良いし、通信Ｉ／Ｆを介して外部装置から取得するようにしても良い。
【００５６】
乗算部１０２は、取得部１０１が取得した代数的トーラスT6(Fp^m)の元（c0,c1）及びシステムパラメータw,δを用いて伸張写像を行う際に、以下の乗算を行う。尚、ここでは上述の式１３により伸張写像を行うものとする。
t1=c0^2
t2=c0×c1
t3=c1^2
a2=t4×w^{-1}
【００５７】
加減算部１０３は、取得部１０１が取得した代数的トーラスT6(Fp^m)の元（c0,c1）及びシステムパラメータw,δを用いて上述の式１３により伸張写像を行う際に、乗算部１０２が乗算を行った結果を用いて以下の加算を行う。
a0= t2
a1= t3
t4= t1+δ/3
b0=c1
b1=0
b2=0
【００５８】
尚、「w^{-1}」と「δ/3」とは、取得部１０１が取得したシステムパラメータw,δを用いて乗算部１０２及び加減算部１０３のいずれか一方が計算を行って得るようにしても良い。しかし、「w^{-1}」と「δ/3」とを外部記憶装置に予め記憶させ、これらを取得部１０１が取得し、取得されたものを乗算部１０２及び加減算部１０３は用いても良い。
【００５９】
出力部１０４は、乗算部１０２が行った乗算の結果及び加減算部１０３が行った加算の結果を用いて、代数的トーラスT2(Fp^3m)の元であり射影表現で表現された(a0, a1, a2, b0, b1, b2)を出力する。
【００６０】
（２）動作
次に、本実施の形態にかかる伸張装置１００の行う伸張写像の手順について図２を用いて説明する。伸張装置１００は、伸張写像の対象となる代数的トーラスT6(Fp^m)のアフィン表現で表現された元（c0,c1）と、2次拡大の法多項式を決定するシステムパラメータwと、3次拡大の法多項式を決定するシステムパラメータδとを取得する（ステップＳ１）。次いで、伸張装置１００は、ステップＳ１で取得した代数的トーラスT6(Fp^m)の元（c0,c1）及びシステムパラメータwを用いて、以下の乗算を行う（ステップＳ２）。
t1=c0^2
t2=c0×c1
t3=c1^2
a2=t4×w^{-1}
【００６１】
また、伸張装置１００は、ステップＳ１で取得した代数的トーラスT6(Fp^m)の元（c0,c1）のうちc1と，システムパラメータδと、ステップＳ２で行った乗算の結果とを用いて、以下の加算を行う（ステップＳ３）。
a0= t2
a1= t3
t4= t1+δ/3
b0=c1
b1=0
b2=0
【００６２】
以上のようにして、伸張装置１００は、伸張写像を行って、代数的トーラスT6(Fp^m)の元をアフィン表現から射影表現に変換する。そして、伸張装置１００は、ステップＳ２で行った乗算の結果及びステップＳ３で行った加算の結果を用いて、代数的トーラスT2(Fp^m)の１つの元であり射影表現で表現された(a0, a1, a2, b0, b1, b2)を出力する（ステップＳ４）。
【００６３】
本実施の形態においては、以上のような伸張写像を行うことによって、代数的トーラスの元をアフィン表現から射影表現に変換し、変換後に素数位数の代数的トーラス上であっても演算処理を行うことができると共に、その処理負担を軽減することが可能になる。演算処理としては、例えば、後述の暗号化処理、復号処理、鍵生成処理、ハイブリッド暗号特にKEM-DEMフレームワークにおけるKEM-Encの処理やDEM-Decの処理などがある。このような演算処理に含まれる乗算や平方計算などのべき乗計算を射影表現で行うことができる。
【００６４】
これに対し、従来技術欄で説明したRS伸張写像は、以下の式１９又は式２０により行うことができるが、変換後に素数位数の代数的トーラス上では演算処理を行うことができない恐れがあった。
【００６５】
【数１７】
2010049217.tif 000019
【００６６】
また、従来技術欄で説明したGPS伸張写像は、以下の式２１により行うことができるが、素数位数の代数的トーラスを構成するために拡大次数mに課される条件の下でmを探索すると、適当なパラメータが見つからない。よって、実際には伸張後の演算処理を行うことは不可能である。もちろん、合成数位数の代数的トーラスを用いるとパラメータが存在する可能性がある。
【００６７】
【数１８】
2010049217.tif 000020
【００６８】
ここで、GPS伸張写像の概要について図３を用いて簡単に説明する。GPS伸張写像を行う伸張装置には、入力は代数的トーラスT6(Fp^m)の元でありアフィン表現で表現された１つの元（a1, a2）が入力される。a1, a2は各々拡大体Fp^mの元である。伸張装置は、伸長写像として以下の計算を行う。
t1=a1^2
t2=a1×a2
t3=a2^2
b1=1+t1-t3
b2=t2
b3=t3
b4=a2
b5=0
b6=0
得られた（b1, b2, b3, b4, b5, b6）は代数的トーラスの１つの元を表す射影表現である。合成数位数の代数的トーラスを用いた場合にパラメータが存在する場合には、演算処理を射影表現で行ったり、又は、射影表現を更に拡大体表現に変換した後に演算処理を拡大体表現で行ったりすることはできるが、素数位数の代数的トーラス上では、アフィン表現から射影表現への変換後の演算処理を行うことは不可能である。
【００６９】
このようなRS伸張写像やGPS伸張写像以外の一般的な伸張写像を利用すれば、アフィン表現から射影表現への変換後の演算処理を行うことは可能であるが、例えば図４で対比されるように、本実施の形態における伸張写像に比べて処理負担が重い。これに対し、本実施の形態の構成によれば、アフィン表現から射影表現への変換後に素数位数の代数的トーラス上においても演算処理が可能になると共に、変換後の演算処理の処理負担を従来に比べて軽減することができる。
【００７０】
（３）演算装置への適用例
＜暗号化処理＞
次に、本実施の形態にかかる伸張装置を演算装置に適用する例について説明する。図５は、アフィン表現から射影表現への変換後に演算処理として暗号化処理を行う演算装置の構成を例示する図である。当該演算装置は、伸張装置１００と、暗号化部２００と、圧縮部３００とを備える。伸張装置１００の構成は上述した通りである。尚、ここでは、伸張装置１００が取得し伸張写像の対象となる代数的トーラスT6(Fp^m)の元（c0,c1）は平文である。暗号化部２００は、伸張装置１００が伸張写像を行った後出力した(a0, a1, a2, b0, b1, b2)と、公開鍵とを取得し、これらを用いて暗号化処理を行って暗号文を出力する。ここで行う暗号化処理は、上述した2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}と、3次拡大の法多項式「f3(y) = y^3-w」及び基底{1, y, y^2}とにより定まる演算処理である。圧縮部３００は、暗号化部２００が出力した暗号文に対して圧縮写像を行って、圧縮暗号文を出力する。
【００７１】
尚、伸張装置１００と、暗号化部２００と、圧縮部３００とは、各々が装置単体としてＣＰＵや記憶装置を備える構成であっても良いし、又は、上述の伸張装置１００のハードウェア構成の欄で説明したＣＰＵと、記憶装置と、外部記憶装置と、通信Ｉ／Ｆとを演算装置が備え、当該ＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより、伸張装置１００と、暗号化部２００と、圧縮部３００との各機能が実現されるようにしても良い。また、演算装置は、圧縮部３００が出力した圧縮暗号文を通信Ｉ／Ｆを介して外部装置に送信しても良いし、圧縮部３００を備えず、暗号化部２００が出力した暗号文を通信Ｉ／Ｆを介して外部装置に送信するようにしても良い。
【００７２】
以上のような構成によれば、アフィン表現から射影表現への変換後に素数位数の代数的トーラス上においても暗号化処理を可能になると共に、暗号化処理の処理負担を軽減することができる。
【００７３】
＜復号処理＞
図６は、アフィン表現から射影表現への変換後に演算処理として復号処理を行う演算装置の構成を例示する図である。当該演算装置は、伸張装置１００と、復号部２１０と、圧縮部３００とを備える。伸張装置１００の構成は上述した通りである。尚、ここでは、伸張装置１００が取得し伸張写像の対象となる代数的トーラスT6(Fp^m)の元（c0,c1）は暗号文である。復号部２１０は、伸張装置１００が伸張写像を行った後出力した(a0, a1, a2, b0, b1, b2)と、秘密鍵とを取得し、これらを用いて復号処理を行って平文を出力する。ここで行う復号処理は、上述した2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}と、3次拡大の法多項式「f3(y) = y^3-w」及び基底{1, y, y^2}とにより定まる演算処理である。圧縮部３００は、復号部２１０が出力した平文に対して圧縮写像を行って、圧縮平文を出力する。尚、ここでの圧縮写像は、射影表現をアフィン表現に変換するものとなる。
【００７４】
尚、伸張装置１００と、復号部２１０と、圧縮部３００とは、各々が装置単体としてＣＰＵや記憶装置を備える構成であっても良い。また、上述の伸張装置１００のハードウェア構成の欄で説明したＣＰＵと、記憶装置と、外部記憶装置と、通信Ｉ／Ｆとを演算装置が備え、当該ＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより、伸張装置１００と、復号部２１０と、圧縮部３００との各機能が実現されるようにしても良い。また、演算装置は、圧縮部３００を備えない構成であっても良い。
【００７５】
以上のような構成によれば、アフィン表現から射影表現への変換後に素数位数の代数的トーラス上においても復号処理が可能であると共に、復号処理の処理負担を軽減することができる。
【００７６】
＜鍵生成処理＞
図７は、アフィン表現から射影表現への変換後に演算処理として鍵生成処理を行う演算装置の構成を例示する図である。当該演算装置は、生成元選択部４００と、伸張装置１００と、鍵生成部２２０と、圧縮部３００とを備える。生成元選択部４００は、生成元として代数的トーラスT6(Fp^m)の元をランダムに選択する。伸張装置１００の構成は上述した通りである。ここでは、伸張装置１００が取得し伸張写像の対象となる代数的トーラスT6(Fp^m)の元（c0,c1）は、生成元選択部４００が生成元として選択したものである。鍵生成部２２０は、伸張装置１００が伸張写像を行った後出力した(a0, a1, a2, b0, b1, b2)と、秘密鍵成分としてランダムに選択した各秘密鍵成分とを取得し、これらを用いて鍵生成処理を行って公開鍵の各鍵成分となる各公開鍵成分を求め、公開鍵と秘密鍵とを出力する。ここで行う鍵生成処理は、上述した2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}と、3次拡大の法多項式「f3(y) = y^3-w」及び基底{1, y, y^2}とにより定まる演算処理である。圧縮部３００は、鍵生成部２２０が出力した公開鍵及び秘密鍵に対して圧縮写像を行って、圧縮鍵を出力する。
【００７７】
尚、生成元選択部４００と、伸張装置１００と、鍵生成部２２０と、圧縮部３００とは、各々が装置単体としてＣＰＵや記憶装置を備える構成であっても良い。また、上述の伸張装置１００のハードウェア構成の欄で説明したＣＰＵと、記憶装置と、外部記憶装置と、通信Ｉ／Ｆとを演算装置が備え、当該ＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより、生成元選択部４００と、伸張装置１００と、鍵生成部２２０と、圧縮部３００との各機能が実現されるようにしても良い。また、演算装置は、圧縮部３００を備えない構成であっても良い。
【００７８】
以上のような構成によれば、アフィン表現から射影表現への変換後に素数位数の代数的トーラス上においても鍵生成処理が可能になると共に、鍵生成処理の処理負担を軽減することができる。
【００７９】
＜KEM（Key Encapsulation Mechanism）-DEM（Data Encapsulation Mechanism）フレームワークへの適用例＞
図８はKEM-DEMフレームワークにおける共通鍵の暗号化とデータの暗号化とを模式的に示す図である。KEM-DEMフレームワークとは、データの暗号化を共通鍵暗号で行い、共通鍵暗号の鍵を公開鍵暗号で暗号化するハイブリッド暗号の一種である（例えば参考文献４参照）。
（参考文献４）R.Cramer and V.Shoup, “Design and analysis of practical public-key encryption schemes secure against adaptive ciphertext attak”, SIAM journal on computing, 33(1): 167-226,2003
【００８０】
同図に示されるPKは群Gに属する公開鍵であり、kは共通鍵暗号の鍵であり、Yは群Gに属する公開鍵暗号の暗号文であり、SKは公開鍵暗号の秘密鍵であり、msgは共通鍵暗号で暗号化されるデータであり、ψは共通鍵暗号の暗号文である。KEM-DEMフレームワークにおいては、送信装置において公開鍵PKがKEM-Encに入力されると、送信装置は、共通鍵暗号の鍵kを生成してこれに対して伸張写像を行った後、伸張された鍵kを用いて公開鍵PKに対して暗号化処理としてKEMの暗号化処理を行って公開鍵の暗号文を得て、当該公開鍵の暗号文を圧縮してこれを圧縮後の公開鍵の暗号文Yとして受信装置に送信する。また、送信装置において共通鍵暗号の鍵k及びデータmsgが入力されると、送信装置は、これらを用いてDEMの暗号化処理を行って共通鍵暗号の暗号文ψを得て、これを受信装置に送信する。
【００８１】
一方、受信装置において暗号文Y及び公開鍵暗号の秘密鍵SKがKEM-Decに入力されると、圧縮後の公開鍵の暗号文Yに対して伸張写像を行った後、伸張された公開鍵の暗号文Yを用いて復号処理としてKEMの復号処理を行って共通鍵暗号の鍵kを得る。尚、KEM-Decの出力として素数位数部分群Gの元となるものはないので、ここでは圧縮の処理は不要となる。また、受信装置において共通鍵暗号の鍵k及び共通鍵暗号の暗号文ψがDEM-Decに入力されると、復号処理としてDEMの復号処理を行ってデータmsgを復号する。
【００８２】
図９は、演算装置としてKEM-Encの構成を例示する図である。KEM-Encは、鍵生成部４１０と、伸張装置１００と、KEM-Enc処理部２３０と、圧縮部３００とを備える。鍵生成部４１０は、公開鍵PKが入力されると、これを用いて共通鍵暗号の鍵kを生成する。伸張装置１００の構成は上述した通りである。ここでは、伸張装置１００が取得し伸張写像の対象となる代数的トーラスT6(Fp^m)の元（c0,c1）は、鍵生成部４１０が生成した共通鍵暗号の鍵kである。KEM-Enc処理部２３０は、伸張装置１００が伸張写像を行った後出力した(a0, a1, a2, b0, b1, b2)を用いて公開鍵PKに対してKEMの暗号化処理を行って公開鍵の暗号文を出力する。ここで行うKEMの暗号化処理は、上述した2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}と、3次拡大の法多項式「f3(y) = y^3-w」及び基底{1, y, y^2}とにより定まる演算処理である。圧縮部３００は、KEM-Enc処理部２３０が出力した公開鍵の暗号文に対して圧縮写像を行って、圧縮後の公開鍵の暗号文Yを出力する。
【００８３】
尚、鍵生成部４１０と、伸張装置１００と、KEM-Enc処理部２３０と、圧縮部３００とは、各々が装置単体としてＣＰＵや記憶装置を備える構成であっても良い。また、上述の伸張装置１００のハードウェア構成の欄で説明したＣＰＵと、記憶装置と、外部記憶装置と、通信Ｉ／ＦとをKEM-Encが備え、当該ＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより、鍵生成部４１０と、伸張装置１００と、KEM-Enc処理部２３０と、圧縮部３００との各機能が実現されるようにしても良い。
【００８４】
図１０は、演算装置としてKEM-Decの構成を例示する図である。KEM-Decは、伸張装置１００と、KEM-Dec処理部２４０とを備える。伸張装置１００の構成は上述した通りである。ここでは、伸張装置１００が取得し伸張写像の対象となる代数的トーラスT6(Fp^r)の元（c0,c1）は、上述のKEM-Encが出力した圧縮後の公開鍵の暗号文Yである。KEM-Dec処理部２４０は、伸張装置１００が伸張写像を行った後出力した(a0, a1, a2, b0, b1, b2) 及び公開鍵暗号の秘密鍵SKを用いて公開鍵の暗号文Yに対してKEMの復号処理を行って共通鍵暗号の鍵kを得る。ここで行うKEMの復号処理は、上述した2次拡大の法多項式「f2(x) = x^2-δ」及び基底{1, x}と、3次拡大の法多項式「f3(y) = y^3-w」及び基底{1, y, y^2}とにより定まる演算処理である。
【００８５】
尚、伸張装置１００と、KEM-Dec処理部２４０とは、各々が装置単体としてＣＰＵや記憶装置を備える構成であっても良い。また、上述の伸張装置１００のハードウェア構成の欄で説明したＣＰＵと、記憶装置と、外部記憶装置と、通信Ｉ／ＦとをKEM-Decが備え、当該ＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより、伸張装置１００と、KEM-Dec処理部２４０との各機能が実現されるようにしても良い。
【００８６】
以上のような構成によれば、KEM-DEMフレームワークにおいて、アフィン表現から射影表現への変換後に素数位数の代数的トーラス上においてもKEMの暗号化処理やKEMの復号処理を可能であると共に、これらの処理負担を軽減することができる。
【００８７】
尚、Cramer-Shoup暗号方式を適用して、KEM-Enc処理部２３０は、Cramer-Shoup暗号方式におけるKEMの暗号化処理を行うようにし、KEM-Dec処理部２４０は、Cramer-Shoup暗号方式におけるKEMの復号処理を行うようにしても良い。
【００８８】
＜トーラスCramer-Shoup暗号への適用例＞
次に、演算処理である暗号化処理及び復号処理として、特に、トーラスCramer-Shoup暗号における暗号化処理及び復号処理に本実施の形態の伸張装置１００を適用する例について説明する。このような暗号化処理を行う演算装置の構成は、図５と略同様であるため、その図示を省略する。ここでは、図５に示した伸張装置１００、暗号化部２００及び圧縮部３００がトーラスCramer-Shoup暗号において実現させる特有の機能について説明する。当該演算装置には、公開鍵（q,g,g~,e,f,h）及び平文msgが入力される。これらは各々代数的トーラス上T6(Fp^m)の元でありアフィン表現で表現されている。伸張装置１００は、アフィン表現で表現された公開鍵（q,g,g~,e,f,h）に含まれる各公開鍵成分q,g,g~,e,f,hに対して上述と同様の伸張写像を各々行って、これらを射影表現に各々変換する。ここでは、各公開鍵成分q,g,g~,e,f,hの射影表現をq*,g*,g~*,e*,f*,h*と各々記載する。暗号化部２００は、射影表現で表現された公開鍵（q*,g*,g~*,e*,f*,h*）と、平文msgとを取得すると、まず、乱数uを生成する。次いで、暗号化部２００は、公開鍵成分g*,g~*,h*とを用いて、暗号文の成分c1として「g*＾u」を求め、暗号文の成分c2として「g~*^u」を求め、係数bとして「h*＾u」を求める。伸張装置１００は、アフィン表現で表現された平文msgに対して上述と同様の伸張写像を行って、これを射影表現に変換する。ここでは、平文msgの射影表現をmsg*と記載する。また、暗号化部２００は、係数bと、射影表現で表現された平文msg*とを用いて、暗号文の成分c3として「msg*×b」を求めることにより、平文マスクを行う。更に、暗号化部２００は、求めた暗号文の成分c1,c2,c3を用いてハッシュ関数による計算を行ってハッシュ値vを求める。そして、暗号化部２００は、公開鍵成分e*,f*と、乱数uと、ハッシュ値vとを用いて、暗号文の成分c4として「e*^u×f*^uv」を求める。圧縮部３００は、射影表現で表現された暗号文の成分c1,c2,c3,c4に対して圧縮写像を行って、これらをアフィン表現に各々変換する。ここでは、暗号文の各成分c1,c2,c3,c4のアフィン表現をc1*,c2*,c3*,c4*と各々記載する。そして得られる（c1*,c2*,c3*,c4*）が圧縮暗号文となる。この圧縮暗号文これに対して復号処理を行う演算装置に送信される。
【００８９】
次に、圧縮暗号文（c1*,c2*,c3*,c4*）に対して復号処理を行う演算装置について説明する。当該演算装置の構成は、図６と略同様であるため、その図示を省略する。ここでは、図６に示した伸張装置１００、復号部２１０及び圧縮部３００がトーラスCramer-Shoup暗号において実現させる特有の機能について説明する。当該演算装置には、公開鍵（q,g,g~,e,f,h）に対応する秘密鍵(w,x,y,z)とアフィン表現で表現された（c1*,c2*,c3*,c4*）とが入力される。圧縮暗号文の各成分c1*,c2*,c3は、各々代数的トーラス上T6(Fp^m)の元でありアフィン表現で表現されている。伸張装置１００は、圧縮暗号文の各成分c1*,c2*,c3*に対して上述と同様の伸張写像を各々行って、これらを射影表現に各々変換する。この結果射影表現で表現された各成分c1,c2,c3が得られる。復号部２１０は、圧縮暗号文の成分c1*,c2*,c3*を用いてハッシュ関数による計算を行って、ハッシュ値vを求める。また、復号部２１０は、圧縮暗号文の成分c1*と、秘密鍵成分z1,z2と、ハッシュ値vとを用いて、係数t1として「c1*^w」を求めると共に、係数t2として「c1＾（x+y×v）」を求める。圧縮部３００は、復号部２１０が求めた係数t2に対して圧縮写像を行って、射影表現からアフィン表現に変換する。ここでは、係数t2のアフィン表現をt2*と記載する。復号装置２００は、係数t1及びt2*と、暗号文の成分c2と、圧縮暗号文の成分c4*とを用いて、「c2= t1」及び「c4*=t2*」が成立する場合、暗号文の成分c1及び秘密鍵の成分zを用いて、係数bとして「c1^z」を求める。そして、復号部２１０は、求めた係数bの逆元「b^（-1）」と暗号文の成分c3とを用いて、平文msgとして「c3×b^（-1）」を求める。
【００９０】
以上のような構成によれば、トーラスCramer-Shoup暗号において素数位数の代数的トーラス上での暗号化処理や復号処理を可能にしつつ、その処理負担を軽減することができる。
【００９１】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００９２】
＜変形例１＞
上述した実施の形態において、伸張装置１００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。この場合には、プログラムは、伸張装置１００において上記記録媒体から読み出して実行することにより例えばＲＡＭなどの記憶装置上にロードされ、上記機能的構成において説明した各部が記憶装置上に生成される。演算装置,KEM-Enc及びKEM-Decについても同様である。
【００９３】
＜変形例２＞
上述した実施の形態において、伸張装置１００が行った伸張写像の結果得られる射影表現(a0, a1, a2, b0, b1, b2)の各項に、定数d（d：有限体Fqの元）を各々掛けても同じ元を表す。このため、(a0×d, a1×d, a2×d, b0×d, b1×d, b2×d)を用いて各演算処理を行うようにしても良い。
【００９４】
＜変形例３＞
上述した実施の形態において、演算装置は、各演算処理を射影表現で行うようにしても良いし、拡大体表現で行うようにしても良い。
【００９５】
また、伸張装置１００は、アフィン表現から変換した射影表現を更に拡大体表現に変換する変換部を更に備えるようにしても良い。即ち、伸張装置１００は、代数的トーラスの元のアフィン表現（c0,c1）を式３により表される射影表現に変換した後、拡大体表現「α´+β´x」に変換する。この場合、伸張装置１００は、以下の式２２，２３により、c0,c1から、α,βを計算する。
【００９６】
【数１９】
2010049217.tif 000021
【００９７】
次いで、伸張装置１００は、以下の式２４により、α,βから、α´,β´を計算する。
【００９８】
【数２０】
2010049217.tif 000022
【００９９】
また、このように射影表現を経由せずに、アフィン表現から拡大体表現に変換するようにしても良い。この場合、伸張装置１００は、「c1≠0」であるとき、「γ=α/β」として、以下の式２５によりγを計算する。
【０１００】
【数２１】
2010049217.tif 000023
【０１０１】
次いで、伸張装置１００は、以下の式２６により、γから、α´,β´を計算する。
【０１０２】
【数２２】
2010049217.tif 000024
【０１０３】
尚、「c1=0」であるとき、α´,β´は各々「0」である。
【０１０４】
以上のような構成によれば、演算装置は、伸張装置１００が拡大体表現に変換した元を用いて各演算処理を拡大体表現で行うことが可能になる。
【０１０５】
＜変形例４＞
上述した実施の形態において、「r=3」である場合について説明したが、rの値はこれに限らない。
【図面の簡単な説明】
【０１０６】
【図１】一実施の形態にかかる伸張装置の機能的構成を例示する図である。
【図２】同実施の形態にかかる伸張装置１００の行う伸張写像の手順を示すフローチャートである。
【図３】GPS伸張写像の概要を例示する図である。
【図４】従来の構成と本実施の形態の構成との効果の対比を例示する図である。
【図５】同実施の形態にかかる暗号化処理を行う演算装置の構成を例示する図である。
【図６】同実施の形態にかかる復号処理を行う演算装置の構成を例示する図である。
【図７】同実施の形態にかかる鍵生成処理を行う演算装置の構成を例示する図である。
【図８】KEM-DEMフレームワークにおける共通鍵の暗号化とデータの暗号化とを模式的に示す図である。
【図９】同実施の形態にかかる演算装置としてKEM-Encの構成を例示する図である。
【図１０】同実施の形態にかかる演算装置としてKEM-Decの構成を例示する図である。
【符号の説明】
【０１０７】
１００  伸張装置
１０１  取得部
１０２  乗算部
１０３  加減算部
１０４  出力部
２００  暗号化部
２１０  復号部
２２０  鍵生成部
２３０  KEM-Enc処理部
２４０  KEM-Dec処理部
３００  圧縮部
４００  生成元選択部
４１０  鍵生成部
【図１】
2010049217.tif 000025
【図２】
2010049217.tif 000026
【図３】
2010049217.tif 000027
【図４】
2010049217.tif 000028
【図５】
2010049217.tif 000029
【図６】
2010049217.tif 000030
【図７】
2010049217.tif 000031
【図８】
2010049217.tif 000032
【図９】
2010049217.tif 000033
【図１０】
2010049217.tif 000034