暗号化装置、復号装置、暗号通信システム、方法及びプログラム
【課題】冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが可能な暗号化技術を提供する。
【解決手段】暗号化装置３０１は、入力された平文msgが、6次拡大体上の代数的トーラス上の元であるか否かを検査する。検査結果が肯定的である場合、暗号化装置３０１は、公開鍵を用いて平文msgを暗号化する。圧縮装置３０２は、生成された暗号文を圧縮写像により圧縮して圧縮暗号文を出力する。送信装置３００はこれを受信装置４００に送信する。受信装置４００の伸長装置４０２は、受信された圧縮暗号文の各要素が、6次拡大体上の代数的トーラス上の元であるか否かを検査する。当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文を伸長写像により伸長して暗号文を得る。復号装置４０１は、秘密鍵を用いて、暗号化された平文を復号する。
【解決手段】暗号化装置３０１は、入力された平文msgが、6次拡大体上の代数的トーラス上の元であるか否かを検査する。検査結果が肯定的である場合、暗号化装置３０１は、公開鍵を用いて平文msgを暗号化する。圧縮装置３０２は、生成された暗号文を圧縮写像により圧縮して圧縮暗号文を出力する。送信装置３００はこれを受信装置４００に送信する。受信装置４００の伸長装置４０２は、受信された圧縮暗号文の各要素が、6次拡大体上の代数的トーラス上の元であるか否かを検査する。当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文を伸長写像により伸長して暗号文を得る。復号装置４０１は、秘密鍵を用いて、暗号化された平文を復号する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号により平文を暗号化する暗号化装置、公開鍵暗号により暗号化された平文を復号する復号装置、暗号通信システム、方法及びプログラムに関する。
【背景技術】
【０００２】
通信路を流れる情報を保護するために、暗号を用いる方法がある。暗号には、例えば、共通鍵暗号と公開鍵暗号とがある。共通鍵暗号を用いる場合、通信相手と事前に鍵を共有しておく必要があるため、インターネットのような不特定多数との通信の際には鍵の共有や管理に大きな手間がかかる。公開鍵暗号は、事前に鍵を共有することなしに安全な通信を実現できるため、ネットワーク・セキュリティの基盤技術として幅広く用いられている。
【０００３】
現在、公開鍵暗号において典型的なセキュリティパラメータは1024ビット〜2048ビットである。セキュリティパラメータとは、公開鍵サイズや暗号文サイズを決定するパラメータであり、暗号方式の安全性に影響を与えるパラメータである。このセキュリティパラメータが大きくなれば、公開鍵サイズや暗号文サイズも大きくなる。解読が困難とされるセキュリティパラメータは年々大きくなっている。これは、計算機の進歩に伴い攻撃者の能力も向上するためである。公開鍵暗号では公開鍵サイズや暗号文サイズは、暗号方式により異なるが、セキュリティパラメータの数倍となる。このため、メモリ容量や通信帯域が十分でない装置ではセキュリティパラメータの増大が問題になる。
【０００４】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する方法が提案されている（例えば、非特許文献１、８参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。代数的トーラスの属する拡大体の次数nが高々二つの素数p,qの冪の積ｌ=(p^m)*(q^n)であるとき、圧縮率（＝圧縮前のビット数／圧縮後のビット数）は、ｌ/φ(ｌ)となることが知られている。ただし、φ（・）はオイラー関数である。尚、‘^’はべき乗を表す。p^mは、pのm乗である。小さいビット数の表現への変換は、拡大体表現を射影表現に変換する写像ρと射影表現をアフィン表現に変換する写像τによって行われる。暗号文を圧縮する場合の具体例を示す。拡大体表現の暗号文cを入力として計算を行い、圧縮暗号文γを得る（式１参照）。
【０００５】
τρ (c)=γ・・・（式１）
【０００６】
元のビット数の表現に戻すには、それぞれρ、τの逆写像を計算すればよい。ρの逆写像をψと書き、τの逆写像をτ―1と書くことにする。圧縮暗号文としてγが与えられたときに計算を行い、cを得る（式２参照）。
【０００７】
ψτ―1(γ)= c・・・（式２）
【０００８】
また、非特許文献１、７では、前記圧縮写像１、２と前記伸長写像１，２の構成法と、それらを用いて次のような拡大体表現をアフィン表現に圧縮する写像ρ6、アフィン表現を拡大体表現に伸長する写像‘ρ6-1’の構成法が示されている。圧縮写像ρ6は、6次拡大体F_{(p^m)^6}上の拡大体表現のトーラスＴの任意の元tを入力として計算し、アフィン表現F_{p^m}×F_{p^m}^* の要素との組を得る（式３参照）。
【０００９】
ρ6(t)= (a,b) ∈ F_{p^m}× F_{p^m}＾*・・・（式３）
【００１０】
尚、ここでは‘×’を直積を表すものとする。また、Aが集合であるとき、A^mはm個のAの直積集合となる。例えば、‘A^4 ＝ A × A × A × A’となる。具体的には例えば、‘{0,1,2}^2 = {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}’となる。ここで、F_{p^m}は、素体F_{p}のm次拡大体であり、 F_{p^m}の要素はベクトル表現を用いると、{0,…,p-1}^mの要素で表現できる。F_{p^m}^*は、F_{p^m}の乗法群であり、F_{p^m}^*の要素はベクトル表現を用いると、{0,…,p-1}^m ＼ {0}^m の要素で表される。‘＼’は集合の引き算を表す。
【００１１】
伸長写像‘ρ6-1’は、(a,b) ∈ F_{p^m}× F_{p^m}＾*を入力として計算し、6次拡大体F_{（p^m）^6}上の拡大体表現のトーラスＴの元tを得る（式４参照）。
【００１２】
ρ-1(a,b)＝t ∈ T・・・（式４）
【００１３】
また、非特許文献７では、F_{p^m}の6次拡大体上のトーラスの要素の拡大体表現{0,…,p-1}^(6*m)と射影表現{0,…,p-1}^(6*m)とアフィン表現F_{p^m}×F_{p^m}^*に対して、上記のρ、ψ、τ、τ-1の構成法を示し、それを元に（式３）と（式４）との写像を構成している。このとき、拡大体表現と射影表現とに対する演算は、共にF_{p^(6*m)}の演算で、非特許文献１、７ではF_{p^(6*m)}の演算をF_{((p^m)^3)^2}の演算として実現している。アフィン表現の要素は、演算することができない。
【００１４】
また、xがTの要素であるか否かの検査は、例えば、F_{p^(6*m)}上の演算で以下の２通りの方法で行うことができる。
方法１：(p^(6*m)-1)/ (p^(3m)-1)乗して‘１’となる且つ(p^(6*m)-1)/ (p^(2m)-1)乗して‘1’となることが成立するか否か調べる。
方法２：(p^(2m)-p^m+1)乗して‘1’となることが成立するか否か調べる。
【００１５】
離散対数問題系を利用したElGamal暗号（例えば、非特許文献４参照）やCramer-Shoup暗号（例えば、非特許文献２参照）などは、暗号化可能な平文のサイズと比べて、鍵長と暗号文とのサイズが大きいという問題を抱えている。代数的トーラス上で構成されたElGamal暗号の公開鍵と暗号文とは代数的トーラス上の要素となることを利用し、公開鍵と暗号文とを圧縮することでサイズを抑える方法がある（例えば、非特許文献１、５ 〜６参照）。
【００１６】
【非特許文献１】K.Rubin and A.Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, pp. 349-365, 2003.
【非特許文献２】R.Ｃｒａｍｅｒ and V.Shoup, “A practical key cryptosystem provably secure against adaptive chosen ciphertext attack”, CRYPTO 1998, LNCS 1462, pp. 13-25, 1998.
【非特許文献３】V.Shoup, “ACE Encrypt: The Advanced Cryptographic Engine’s Public Key Encryption Scheme”, “http://www.zurich.ibm.com/security/ace/ace_encrypt.pdf”,2000.
【非特許文献４】Taher El Gamal: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4): 469-472 (1985)
【非特許文献５】Marten van Dijk, David P. Woodruff: Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO 2004: 157-178
【非特許文献６】Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff: Practical Cryptography in High Dimensional Tori. EUROCRYPT 2005: 234-250
【非特許文献７】Robert Granger, Dan Page, Martijn Stam: A Comparison of CEILIDH and XTR. ANTS 2004: 235-249
【発明の開示】
【発明が解決しようとする課題】
【００１７】
公開鍵暗号において暗号化処理や復号処理を安全に実現するためには、処理の対象が、暗号が定義される群の要素であるか否かを検査する必要がある。また、代数的トーラスにおける圧縮処理や伸長処理においても、暗号が定義される群の要素でなければ、正しく写像することができない。しかし、非特許文献１，５〜７に示したような既存の代数的トーラスを用いた暗号系では、暗号化処理や復号処理への入力が、暗号が定義される群の要素であるか否かをどの時点でどのように検査するかについて検討する必要がある。例えば、代数的トーラスにおける圧縮処理及び伸長処理と公開鍵暗号の暗号化処理及び復号処理とを単純に組み合わせた場合、入力がそれぞれの処理で、暗号が定義される群上の元であるかを判定するための処理に、冗長な処理を含む恐れがある。このため、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが望まれていた。
【００１８】
本発明は、上記に鑑みてなされたものであって、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが可能な暗号化装置、復号装置、暗号通信システム、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
上述した課題を解決し、本発明は、復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置であって、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２０】
また、本発明は、F_{p^m}の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}× F_｛p＾m｝^*(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置であって、暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得手段と、前記平文msgに含まれるベクトル成分が、アフィン表現F_{p^m}×F＿｛p＾m｝^*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_｛p^m｝^*上の要素の組で表現される暗号文cを求める暗号化手段を備えることを特徴とする。
【００２１】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{{0,・・・,p-1}^{6*m}}(p:素数、m:自然数)で表現された平文msgを暗号化する暗号化装置であって、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、 前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現F_{p^m} ×F_{p^m}^*に写像する圧縮手段とを備えることを特徴とする。
【００２２】
また、本発明は、F_{p^m}の6次拡大体(p：素数、m：自然数)上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*、(^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、前記暗号化装置は、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、前記復号装置は、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２３】
また、本発明は、F_{p^m}の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数、^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、前記暗号化装置は、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、前記復号装置は、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２４】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*(p:素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得ステップと、前記平文msgに含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める暗号化ステップとを含むことを特徴とする。
【００２５】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、暗号化の対象である平文msgと、公開鍵とを取得する取得ステップと、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定ステップと、前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化ステップと、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮ステップとを含むことを特徴とする。
【００２６】
また、本発明は、復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置で実行される復号方法であって、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得ステップと、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長ステップと、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号ステップとを含むことを特徴とする。
【００２７】
また、本発明は、プログラムであって、上記記載の方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２８】
本発明によれば、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが可能になる。
【発明を実施するための最良の形態】
【００２９】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号装置、暗号通信システム、方法及びプログラムの最良な実施の形態を詳細に説明する。
【００３０】
[第１の実施の形態]
（１）構成
＜公開鍵暗号スキーム＞
まず、本実施の形態にかかる公開鍵暗号スキームについて説明する。図１は、公開鍵暗号スキームの構成を例示する図である。公開鍵暗号スキームにおいては、パラメータ生成装置１００が、公開鍵暗号に関する公開情報を生成する。公開情報としては、公開鍵に関する情報として、群の要素やハッシュ関数などの情報や、暗号系が定義される群に関する情報として、位数や生成元の情報がある。公開情報のうち群に関する情報は、後述するCramer-Shoup暗号の場合、(p, q, m, n)である。そして、鍵生成装置２００が、公開情報を用いて公開鍵と、これに対応する秘密鍵とを生成する。暗号化装置３０１を有する送信装置３００には、鍵生成装置２００が生成した公開鍵と、暗号化の対象の平文が入力される。この平文は、送信装置３００において予め記憶されたものであっても、送信装置３００が生成したものであっても、他の通信装置から受信したものであっても、記憶媒体から読み出したものであっても良い。暗号化装置３０１は、公開鍵を用いて平文を暗号化して暗号文を生成しこれを受信装置４００に送信する。復号装置４０１を有する受信装置４００は、暗号文を受信すると、当該暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて暗号文を復号することにより、平文を得る。
【００３１】
＜トーラス圧縮：公開鍵暗号スキーム＞
次に、トーラス圧縮による公開鍵暗号スキームについて図２を用いて説明する。トーラス圧縮による公開鍵暗号スキームにおいては、送信装置３００は暗号化装置３０１に加え圧縮装置３０２を更に有する。受信装置４００は、復号装置４０１に加え伸長装置４０２を更に有する。パラメータ生成装置１００及び鍵生成装置２００の構成は上述と同様であるため、その説明を省略する。暗号化装置３０１は、公開鍵を用いて平文を暗号化して暗号文を生成するが、この暗号化を圧縮しない表現で行う。生成された暗号文は、ベクトル形式により表現される。圧縮装置３０２は、暗号文に含まれるベクトル成分を圧縮して出力する。圧縮された暗号文（圧縮暗号文という）を送信装置３００は受信装置４００に送信する。伸長装置４０２は、圧縮暗号文に含まれるベクトル成分を伸長する。復号装置４０１は、伸長された暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて当該暗号文を復号することにより、平文を得る。ここでの復号は圧縮しない表現で行う。尚、同図では、鍵生成装置２００が行う公開鍵及び秘密鍵の生成と、暗号化装置３０１が行う暗号化と、復号装置４０１が行う復号とは拡大体表現による演算で行う。
【００３２】
尚、パラメータ生成装置１００、鍵生成装置２００、送信装置３００及び受信装置４００は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、送信装置３００及び受信装置４００は、インターネット等のネットワーク（図示せず）を介して接続されて通信を行う。また、送信装置３００の有する暗号化装置３０１及び圧縮装置３０２は、送信装置３００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものである。同様に、受信装置４００の有する復号装４００及び伸長装置４０２は、受信装置４００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものである。
【００３３】
＜Cramer-Shoup暗号＞
次に、公開鍵暗号スキームで説明した送信装置３００及び受信装置４００の構成において、Cramer-Shoup暗号を適用する構成について説明する。図３は、Cramer-Shoup暗号における処理を概念的に示す図である。鍵生成装置２００は、公開鍵（p,q,g,g~,e,f,h）を生成する。尚、p,qは素数でそれぞれ群G^の位数とその部分群Gの位数、gは暗号が定義される部分群G（位数はq）の生成元、g~,e,f,hも群Gの元とする。平文msgも部分群Gの元でなければならない。一方、当該公開鍵に対応する秘密鍵(x1, x2, y1, y2, z1, z2)は‘1’から‘q-1’までの整数又は‘0’から‘q-1’までの整数とする。送信装置３００の有する暗号化装置３０１は、公開鍵を用いて平文msgに対応する暗号文(c1, c2, c3, c4)を計算する。具体的には、暗号化装置３０１は、qを用いて‘0≦r＜q-1’なる乱数rを生成する。そして、暗号化装置３０１は、ｃ1としてg^rを求め、ｃ2としてg~^rを求め、bとしてh^rを求める。そして、暗号化装置３０１は、b*mをｃ3として求める。‘*’は乗算を表す。次いで、暗号化装置３０１は、(c1, c2, c3)についてハッシュ関数を用いた計算により、ハッシュ値H(c1, c2, c3)を求める。そして、暗号化装置３０１は、ｃ4として、e^r*f^r*vを求める。この結果、暗号文(c1, c2, c3, c4)が得られる。この暗号文(c1, c2, c3, c4)を送信装置３００は受信装置４００に送信する。
【００３４】
一方、受信装置４００は、暗号文(c1, c2, c3, c4)を受信すると、復号装置４０１が、秘密鍵(x1, x2, y1, y2, z1, z2)と暗号文(c1, c2, c3, c4)とから正当な平文であるか否かの判定を行い、当該判定結果が肯定的である場合、平文msgを計算する。具体的には、復号装置４０１は、(c1, c2, c3, c4)の各要素が、群G＾の元であるか否かを判定する。当該判定結果が肯定的である場合、復号装置４０１は、bとして、ｃ1^z1*ｃ2^z2を求める。次いで、復号装置４０１は、(c1, c2, c3)の各要素が、群G^の部分群Gの元であるか否かを判定する。また、復号装置４０１は、暗号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求める。そして、復号装置４０１は、当該値と暗号文の要素とを用いた以下の検査式５が成立するか否かを判定する。また、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する。
【００３５】
c4=c1^（x1+y1*v）*c2^（x2+y2*v）・・・（式５）
【００３６】
＜トーラス圧縮Cramer-Shoup暗号＞
以上のような構成において、トーラス圧縮によるCramer-Shoup暗号（トーラス圧縮Cramer-Shoup暗号という）について説明する。ここでは、F_{p^(6*m)}上のトーラスの位数は合成数で、平文は拡大体表現で表し、暗号文の計算を拡大体表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群Gは、F_{p^m}の6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。図４は、本構成における鍵生成装置２００の構成を概念的に示す図である。鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数部分群Gの生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。Cramer-Shoup暗号の公開鍵の計算においては、べき乗計算も乗算も素体上で行うが、本実施の形態のトーラス圧縮Cramer-Shoup暗号の公開鍵の計算においては、べき乗計算と乗算とは拡大体上で行う。６次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算は拡大体F_{p^(6*m)}上の演算を用いる。
【００３７】
次に、トーラス圧縮Cramer-Shoup暗号において、送信装置３００の有する暗号化装置３０１と圧縮装置３０２との構成について説明する。図５は、トーラス圧縮Cramer-Shoup暗号における暗号化装置３０１と圧縮装置３０２とが行う処理を概念的に示す図である。暗号化装置３０１には、鍵生成装置２００が生成した公開鍵が入力され、暗号化の対象の平文msgが入力される。尚、暗号化装置３０１は、拡大体表現{{0,…,p-1}^ (6*m)}で表現されたmsg毎に平文を処理するものとする。暗号化装置３０１は、まず、入力された平文msgが正しい群の元であるか否かを検査する。この検査は、平文msgが、以下の条件(A1)〜(C1)の全てを満たすか否かを判定することにより行う。
【００３８】
(A1){0,…,p-1}^(6*m)に含まれる
(B1_1)拡大体表現の演算で msg^{p^(2*m)-p^(m)} = 1を満たす
(B 1_2)拡大体表現の演算で msg^(q) = 1を満たす
【００３９】
条件(A1)を満たす場合、平文msgは、6次拡大体上の元である。条件(B1_1)を満たす場合、平文msgは、合成数位数代数的トーラス上の元である。条件(B1_2)を満たす場合、平文msgは、合成数位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。条件(B1_1)を判定するための計算は効率的に実行できるため、この計算を、条件(B1_2)を判定するための計算の前に行うことで効率的な検査が可能となる。これらの条件を用いた検査結果が肯定的である場合、入力された平文msgは、拡大体表現{{0,…,p-1}^(6*m)}で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０１は、公開鍵を用いて平文msgを暗号化する。具体的には、暗号化装置３０１は、Cramer-Shoup暗号において説明したように、乱数を生成し、公開鍵に含まれるg~,e,fを用いて、当該乱数を乗数に用いたべき乗計算を行い、暗号文の要素であるc1,c2を求める。そして、暗号化装置３０１は、乗算を行うことにより平文マスクを行い、暗号文の要素であるc3を求める。また、暗号化装置３０１は、公開鍵に含まれるe,fと、乱数とを用いてハッシュ計算を行ってハッシュ値を求め、当該ハッシュ値を乗数に用いたべき乗計算を行うことにより、暗号文の要素であるc4を求める。この暗号文は、復号の対象である平文msgを含んで暗号化されたものとなる。尚、ここでの各乗算は拡大体F_p^{(6*m)}上で行う。次いで、圧縮装置３０２は、各要素c1,c2,c3,c4を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を出力する。出力された圧縮暗号文はアフィン表現となっている。送信装置３００は出力されたこの圧縮暗号文を受信装置４００に送信する。
【００４０】
次に、トーラス圧縮Cramer-Shoup暗号において、受信装置４００の有する復号装置４０１と伸長装置４０２との構成について説明する。図６は、トーラス圧縮Cramer-Shoup暗号における復号装置４０１と伸長装置４０２とが行う処理を概念的に示す図である。伸長装置４０２には、送信装置３００が送信した圧縮暗号文(c1, c2, c3, c4)が入力される。尚、伸長装置４０２は、アフィン表現F_{p^m}×F_{p^m}^*の組毎に処理を行うものとする。伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査する。この検査は、圧縮暗号文の各要素ciが以下の条件(C1)〜(D1)を全て満たすか否かを判定することにより行う。
【００４１】
(C1) F_{p^m}×F_{p^m}^* に含まれる
(D1)拡大体表現による演算で、ci^(q) = 1 が成立する
【００４２】
これらの検査を伸長写像の前に行うことにより伸長写像における無駄な計算を省くことができる。尚、条件(C1)を満たす場合、ciは、アフィン表現により表現されている。条件(D1)を満たす場合、ciは、代数的トーラスの位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現F_{p^m}×F_{p^m}^*で表現される暗号文であって、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の部分群Gの元である。この場合、伸長装置４０２は、(D1)において拡大体表現に写像された圧縮暗号文の各要素を伸長写像によりアフィン表現から伸長 した暗号文(c1, c2, c3, c4)を得る。復号装置４０１には、秘密鍵が入力される。そして、復号装置４０１は、Cramer-Shoup暗号において説明したように、暗号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求める。そして、復号装置４０１は、当該値と暗号文の要素とを用いた検査式が成立するか否かを判定する。また、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する。この結果、平文msgが得られる。
【００４３】
（２）動作
＜暗号化処理及び圧縮処理＞
次に、本実施の形態にかかる送信装置３００が平文を暗号化して圧縮する処理の手順について図７を用いて説明する。送信装置３００の暗号化装置３０１には、鍵生成装置２００が生成した公開鍵が入力され、暗号化の対象の平文が入力される。暗号化装置３０１は、まず、入力された平文msgが正しい群の元であるか否かを検査する（ステップＳ１）。この検査は、平文msgが、上述の条件(A1),(B1_1),(B1_2)の全てを満たすか否かを判定することにより行う。ステップＳ１の検査結果が肯定的である場合、暗号化装置３０１は、Cramer-Shoup暗号において説明したように、乱数を生成して（ステップＳ２）、公開鍵に含まれるg~,e,fを用いて、当該乱数を乗数に用いたべき乗計算と乗算とを行い（ステップＳ３）、暗号文の要素であるc1,c2を求める。そして、暗号化装置３０１は、乗算を行うことにより平文マスクを行い、暗号文の要素であるc3を求める。また、暗号化装置３０１は、公開鍵に含まれるe,fと乱数とを用いてハッシュ計算を行ってハッシュ値を求め（ステップＳ４）、当該ハッシュ値を乗数に用いたべき乗計算を行うことにより（ステップＳ５）、暗号文の要素であるc4を求める。尚、ここでの各乗算は拡大体F_{p^(6*m)}上で行う。以上のようにして暗号化装置３０１が暗号化処理を行った後、圧縮装置３０２が以下の通りに圧縮処理を行う。圧縮装置３０２は、ステップＳ２〜Ｓ５により生成された暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成して（ステップＳ６）、これを出力する（ステップＳ７）。そして、ステップＳ６で出力された圧縮暗号文を送信装置３００は受信装置４００に送信する。尚、ステップＳ１の検査結果が否定的である場合、暗号化装置３０１は、エラーであるとして以降の処理を中断する。
【００４４】
＜伸長処理及び復号処理＞
次に、本実施の形態にかかる受信装置４００が、送信装置３００から送信された圧縮暗号文を伸長して復号する処理の手順について図８を用いて説明する。受信装置４００の伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する（ステップＳ２０）。この検査は、圧縮暗号文の各要素ciが上述の条件(C1)〜(D1)を全て満たすか否かを判定することにより行う。そして、ステップＳ２０の検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文を伸長写像により伸長して暗号文 (c1, c2, c3, c4)を求める（ステップＳ２１）。以上のようにして伸長装置４０２が伸長処理を行った後、復号装置４０１が以下の通りに復号処理を行う。尚、復号装置４０１には、秘密鍵が入力される。復号装置４０１は、ステップＳ２１で求められた暗号文の要素号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い（ステップＳ２２）、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求め（ステップＳ２３）、当該値と暗号文の要素とを用いた上述の検査式５が成立するか否かを判定する（ステップＳ２４）。そして、当該判定結果が肯定的である場合、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する（ステップＳ２５）。この結果、平文msgが得られる。尚、ステップＳ２０の検査結果が否定的である場合、伸長装置４０２は、エラーであるとして以降の処理を中断する。
【００４５】
以上のような構成によれば、送信装置３００で平文を暗号化して暗号文を圧縮し、受信装置４００で圧縮暗号文を伸長して復号する場合に、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【００４６】
例えば、F_{p^m}の6次拡大体上のトーラスを使う暗号系と圧縮処理とを単純に組み合わせた場合、図９に示されるように、暗号化処理の前の他、圧縮処理の前にも入力が正しい群の元であるか否かを検査する必要がある。しかし、上述した実施の形態においては、圧縮処理の前にこの検査を行う必要がなくなるため、冗長な処理を省くことが可能になる。同様に、F_{p^m}の6次拡大体上のトーラスを使う復号系と伸長処理とを単純に組み合わせた場合、図１０に示されるように、伸長処理の前の他、復号処理の前にも入力が正しい群の元であるか否かを検査する必要がある。しかし、上述した実施の形態においては、復号処理の前にこの検査を行う必要がなくなるため、冗長な処理を省くことが可能になる。
【００４７】
つまり、上述の実施の形態のように、合成数位数トーラス上の素数位数部分群を暗号系に用いる場合、入力された平文がF_{p^m}の6次拡大体上の合成数位数トーラス上の元であり素数位数部分群の元であれば、暗号化処理の結果得られる暗号文の各要素は、6次拡大体のトーラスの元となる。このため、圧縮処理の前にトーラスの元であるか否かの検査は不要となる。また、伸長後の暗号文の各要素が6次拡大体上の合成数位数トーラス上の元であり素数位数部分群の元であるか否かの検査を伸長処理の前に行うことで、不正な暗号文を早い段階で識別し、不正な暗号文が入力された際の処理を軽減できる。
【００４８】
尚、上述の実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査する際に、上述の条件(B1_2)を判定するための計算の前に条件(B1_1)を判定するための計算を行うようにした。これは部分群の位数qをべき指数とするべき乗を行う前に代数的トーラスの要素であるか否かを検査するのは冗長な検査であるが、大量の不正な平文が入力されうる環境であっても効率的に検査できるという効果がある。なぜなら、F_{p^m}上の要素xについて、(x^(p^m))の計算はフロベニウス写像（参考文献参照）を用いて効率的に計算できることが知られている。F_{p^m}の6次拡大体上のトーラスの位数は‘p^(2*m)-p^(m)+1’であるため、p^m乗フロベニウス写像を利用することでx^{ p^(2*m)-p^(m)+1}を効率的に計算できるからである。
（参考文献）X: Henri Cohen, Gerhard Frey: Handbook of elliptic and hyperelliptic curve cryptography : Chapman & Hall/CRC
【００４９】
[第２の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５０】
上述の第１の実施の形態においては、合成数位数トーラス上の素数位数部分群を暗号系に用いる場合について説明した。本実施の形態においては、素数位数トーラスを暗号系に用いる場合について説明する。即ち、ここでは、F_{p^(6*m)}上のトーラスの位数は素数で、平文は拡大体表現で表し、暗号文の計算を拡大体表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群は、6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００は、公開情報である素数位数トーラス上の生成元gとその位数qを入力として、乱数を得て、当該乱数を用いたべき乗計算と乗算とを行うことにより公開鍵を計算する。本実施の形態の公開鍵の計算においては、上述の第１の実施の形態と同様に、べき乗計算と乗算とは拡大体表現で行う。また、F_{p^m}の6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算は拡大体F_{p^(6*m)}上の演算を用いる。
【００５１】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第１の実施の形態と異なる点について説明する。本実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かの検査を行う際に、上述の条件(A1),(B1_1)のみを満たすか否かの判定を行う。
【００５２】
当該検査結果が肯定的である場合、入力された平文msgは、拡大体表現{{0,…,p-1}^(6*m)}で表現された、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０１は、上述した第１の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。以降は、上述した第１の実施の形態と同様である。
【００５３】
伸長装置４０２が行う検査は上述の第２の実施の形態と同様で、入力が正しい群の元であるか否かの検査である。送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する際に、上述の条件(C1)のみを満たすか否かを判定し、上述の条件(D1)を満たすか否かの判定を行わない。
【００５４】
当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、伸長装置４０２は、上述の第１の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。以降は、上述した第１の実施の形態と同様である。
【００５５】
以上のように、素数位数トーラスを暗号系に用いる場合、素数位数トーラス上の全ての要素を暗号系に用いることができる。そのため、暗号化の対象である平文の各ベクトル成分が、トーラス上の元であるか否かのみ検査すれば十分である。従って、本実施の形態においては、上述した条件(B1_2)や(D1)を満たすか否かを判定を必要とせず、合成数位数のトーラス上の素数位数部分群を用いた場合と比べ検査のための処理負担が軽減される。
【００５６】
[第３の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第３の実施の形態について説明する。なお、上述の第１の実施の形態又は上述の第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５７】
上述の各実施の形態においては、平文を拡大体表現で表し、暗号文の計算を拡大体表現で行う場合について説明した。本実施の形態においては、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合について説明する。特にここでは、F_｛p^(6*m)｝上のトーラスの位数が合成数である場合を取り扱う。即ち、ここでは、F_｛p^(6*m)｝上のトーラスの位数は合成数で、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、F_{p^m}の6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。本実施の形態における鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数巡回部分群の生成元とその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。尚、本実施の形態の公開鍵の計算においては、べき乗計算と乗算とは射影表現で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００５８】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第１の実施の形態と異なる点について説明する。ここでは、暗号化装置３０１はアフィン表現 F_{p^m}×F_{p^m}＾*で表現されたmsg毎に平文を処理するものとする。暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かの検査を、平文msgが、以下の条件(A3)〜(B3)の全てを満たすか否かを判定することにより行う。
【００５９】
(A3) F_{p^m}×F_{p^m}^* に含まれる
(B3)射影表現による演算で msg^(q) = 1 が成立する
【００６０】
条件(A3)を満たす場合、平文msgは、アフィン表現により表現されている。条件(B3)を満たす場合、平文msgは、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０１は、上述した第１の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。但しここでは、暗号化装置３０１は、上述したように、代数的トーラス上の演算を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行って、アフィン空間F_{p^m}×F_{p^m}＾*上の要素ciの組で表現される暗号文を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。
【００６１】
次に、本実施の形態における受信装置４００の有する伸長装置４０２の構成が、上述の第１の実施の形態と異なる点について説明する。ここでは、伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査を、圧縮暗号文の各要素ciが以下の条件(C3)〜(D3)を全て満たすか否かを判定することにより行う。
【００６２】
(C3) F_{p^m}×F_{p^m}＾* に含まれる
(D3)射影表現による演算で、ci^(q) = 1が成立する
【００６３】
条件(C3)を満たす場合、ciは、アフィン表現により表現されている。条件(D3)を満たす場合、ciは、位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の素数位数部分群の元である。この場合、伸長装置４０２は、上述の第１の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。但しここでは、伸長装置４０２は、上述したように、伸長写像や代数的トーラス上の演算を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。復号装置３０１が行う復号処理は上述の第１の実施の形態と同様である。
【００６４】
以上のような構成によれば、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であっても、入力が正しい群の元であるか否かの検査において、冗長な処理を省くことができる。また、全ての演算を射影表現で行うことによって、射影表現と拡大体表現との間の写像処理を省き、アフィン表現と射影表現との間の写像のみで判定装置を構成できる。
【００６５】
[第４の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００６６】
上述の第３の実施形態においては、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であって、F_{p^(6*m)}上のトーラスの位数は合成数である場合について説明した。本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は素数である場合について説明する。即ち、ここでは、F_{p^(6*m)}上のトーラスの位数は素数で、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、F_{p^m}の6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００は、公開情報である素数位数トーラス上の生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。尚、本実施の形態における公開鍵の計算においては、上述の第３の実施の形態と同様に、べき乗計算と乗算とは射影表現上で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００６７】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第３の実施の形態と異なる点について説明する。本実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査する際に、上述の(A3)のみを満たすか否かを判定を行い、上述した条件(B3)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０１は、上述した第１の実施の形態乃至第３の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。以降は、上述した第１の実施の形態乃至第３の実施の形態と同様である。
【００６８】
次に、本実施の形態における受信装置４００の有する伸長装置４０２の構成が、上述の第３の実施の形態と異なる点について説明する。本実施の形態においては、伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する際に、上述の(C3)のみを満たすか否かを判定を行い、上述した条件(D3)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、伸長装置４０２は、上述した第１の実施の形態乃至第３の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。以降は、上述した第１の実施の形態乃至第３の実施の形態と同様である。
【００６９】
以上のような構成によれば、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合、F_{p^(6*m)}上のトーラスの位数が素数であれば、これが合成数である場合に比べて、処理負担を軽減することができる。入力が正しい群の元であるか否かの各検査において、上述した条件(B3) や条件(D3)を満たすか否かの判定を必要としないからである。
【００７０】
[第５の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００７１】
（１）構成
本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は合成数で、トーラス上の素数位数群の位数はqで、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。本実施の形態における鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数部分群の生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算により公開鍵を計算する。そして、鍵生成装置２００は、公開鍵を圧縮写像により圧縮して、圧縮公開鍵を生成する。尚、本実施の形態の公開鍵の計算においても、上述の第３の実施の形態又は第４の実施の形態と同様に、べき乗計算と乗算とは射影表現上で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００７２】
次に、本実施の形態にかかる送信装置３００´の構成について図１１を用いて説明する。本実施の形態においては、送信装置３００´は、暗号化装置３０３を有する。暗号化装置３０３には、鍵生成装置２００が生成した圧縮公開鍵と、暗号化の対象である平文msgとが入力される。尚、暗号化装置３０３は、アフィン表現 F_{p^m}×F_{p^m}＾*の組で表現されるmsg毎に処理するものとする。暗号化装置３０３は、平文msgが、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否かを検査する。この検査は、以下の条件(A5)〜(C5)を全て満たすか否かを判定することにより行う。
【００７３】
(A5)平文msgのベクトル表現による各ベクトル成分について、1項目からm項目までの各項目が‘0’から‘p-1’までの範囲に入っている
(B5)平文msgのベクトル表現による各ベクトル成分について、‘m+1’項目から2m項目までの各項目が‘0’から‘p-1’までの範囲に入っている且つ全て項目が‘0’でない
(C5)平文msgを伸長して射影表現に変換し、射影表現による演算で以下の条件式６が成立する
msg^（q）=1・・・(式６)
【００７４】
全ての項目について条件(A 5)及び(B5)を満たす場合、平文msgは、アフィン表現により表現されている。条件(C5)を満たす場合、平文msgは、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０３は、圧縮公開鍵と生成元とを伸長し、べき乗計算、圧縮写像及び伸長写像及びハッシュ計算などの各種処理を行って暗号文(c1,c2,c3,c4)を生成し、これを圧縮して圧縮暗号文(c1,c2,c3,c4)を生成して出力する。この圧縮暗号文を送信装置３００´は受信装置４００´に送信する。
【００７５】
次に、本実施の形態にかかる受信装置４００´の構成について図１１を用いて説明する。本実施の形態においては、受信装置４００´は、復号装置４０３を有する。復号装置４０３には、鍵生成装置２００が生成した秘密鍵と、送信装置３００´が送信した圧縮暗号平文とが入力される。復号装置４０３は、圧縮暗号文(c1,c2,c3,c4)の各要素がF_{p^m}×F_{p^m}^*の元であるか否かを検査する。この検査は、以下の条件(D5)〜(F5)を全て満たすか否かを判定することにより行う。
(D5)ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、1項目からm項目までの各項目が‘0’から‘p-1’までの範囲に入っている
(E5)ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、‘m+1’項目から2m項目までの各項目が‘0’から‘p-1’までの範囲に入っている且つ全て項目が‘0’でない
(F5)各ciを伸長して射影表現に変換し、射影表現による演算で以下の条件式７が成立する
ci^q=1・・・(式７)
【００７６】
各ciの全ての項目について条件(D5)及び条件(E5)を満たす場合、ciは、アフィン表現により表現されている。各ciについて条件(F5)を満たす場合、ciは、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。この場合、復号装置４０３は、暗号化された平文を、秘密鍵を用いて復号する。具体的には、復号装置４０３は、ハッシュ計算、圧縮写像、検査式による判定及び平文の計算等の各種処理を行うことにより、平文を得る。
【００７７】
（２）動作
＜鍵生成処理＞
次に、本実施の形態にかかる鍵生成装置２００が公開鍵及び秘密鍵を生成する処理の手順について図１２を用いて説明する。鍵生成装置２００は、パラメータ生成装置１００が生成した公開情報に含まれる、6次拡大体上の合成位数代数的トーラスの位数として公開パラメータqを取得する（ステップＳ４０）。次いで、鍵生成装置２００は、取得した公開パラメータqを用いて、‘0＜w＜q’なる乱数wを生成する（ステップＳ４１）。また、鍵生成装置２００は、公開パラメータqを用いて、‘0≦x1,x2,y1,y2,z1,z2＜q’なる乱数x1,x2,y1,y2,z1,z2を生成する（ステップＳ４２）。鍵生成装置２００は、公開情報に含まれる、素数位数トーラスの生成元gを取得する（ステップＳ４３）。次いで、鍵生成装置２００は、以下の式８〜１１によりべき乗を計算する（ステップＳ４４）。
【００７８】
g~=g^w・・・(式８)
e=g^（x1+w*x2）・・・(式９)
f=g^（y1+w*y2）・・・(式１０)
h=g^（z1+w*z2）・・・(式１１)
【００７９】
そして、鍵生成装置２００は、g~,e,f,hを圧縮写像によりアフィン表現に圧縮する（ステップＳ４５）。次いで、鍵生成装置２００は、（g~,e,f,h）を圧縮公開鍵として出力する（ステップＳ４６）。また、鍵生成装置２００は、（x1,x2,y1,y2,z1,z2）を秘密鍵として出力する（ステップＳ４７）。
【００８０】
＜暗号化処理＞
次に、本実施の形態にかかる送信装置３００´が行う暗号化処理の手順について図１３を用いて説明する。尚、送信装置３００´の暗号化装置３０３は、上述した鍵生成装置２００が生成した圧縮公開鍵（g~,e,f,h）と、暗号化の対象である平文msgを予め取得しているものとする。暗号化装置３０３は、平文msgがF_{p^m}×F_{p^m}^*の元であるか否かを検査する。具体的には、暗号化装置３０３は、まず、平文msgのベクトル表現による各ベクトル成分について、1項目からm項目までと‘m+1’項目から2m項目までとに分割する（ステップＳ６０）。次いで、暗号化装置３０３は、上述の条件(A5)〜(C5)を全て満たすか否かを判定する（ステップＳ６１〜Ｓ６３）。
【００８１】
ステップＳ６１〜Ｓ６３の判定結果が１つでも否定的である場合、暗号化装置３０３は、エラーを出力し以降の処理を中断する（ステップＳ７５）。ステップＳ６１〜Ｓ６３の判定結果が全て肯定的である場合、ステップＳ６４に進み、暗号化装置３０３は、公開情報に含まれる公開パラメータqを用いて、‘0≦u＜q’なる乱数uを生成する。そして、暗号化装置３０３は、圧縮公開鍵（g~,e,f,h）と生成元gとを伸長写像により射影表現で伸長する（ステップＳ６５）。次いで、暗号化装置３０３は、以下の式１２〜１３により射影表現でべき乗を計算して、c1,c2を求める（ステップＳ６６）。
【００８２】
c1=g^u・・・(式１２)
c2=（g~）^u・・・(式１３)
【００８３】
次いで、暗号化装置３０３は、c1,c2を圧縮写像によりアフィン表現に圧縮する（ステップＳ６７）。その後、暗号化装置３０３は、平文msgを伸長写像により射影表現に伸長する（ステップＳ６８）。そして、暗号化装置３０３は、以下の式１４により射影表現による演算でべき乗を計算することにより、平文マスクを行い、ｃ3を求める（ステップＳ６９）。
【００８４】
c3=msg*h^u・・・(式１４)
【００８５】
次いで、暗号化装置３０３は、c3を圧縮写像により圧縮する（ステップＳ７０）。そして、暗号化装置３０３は、ハッシュ計算により(c1,c2,c3)からハッシュ値を求め、これをvとする（ステップＳ７１）。次いで、暗号化装置３０３は、以下の式１５によりべき乗を計算して、c4を求める（ステップＳ７２）。
【００８６】
c4= e^(u)*f^（u*v）・・・(式１５)
【００８７】
次いで、暗号化装置３０３は、c4を圧縮写像により圧縮する（ステップＳ７３）。そして、暗号化装置３０３は、(c1,c2,c3,c4)を圧縮暗号文として出力する（ステップＳ７４）。そして、この圧縮暗号文を送信装置３００´は受信装置４００´に送信する。
【００８８】
＜復号処理＞
次に、本実施の形態にかかる受信装置４００´が行う復号処理の手順について図１４を用いて説明する。尚、受信装置４００´の有する復号装置４０３は、上述した鍵生成装置２００が生成した秘密鍵（x1,x2,y1,y2,z1,z2）を予め取得しているものとする。復号装置４０３は、圧縮暗号文(c1,c2,c3,c4)の各要素が、F_{p^m}×F_{p^m}^*の元であるか検査する。具体的には、復号装置４０３は、ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、1項目からm項目までと‘m+1’項目から2m項目までとに分割する（ステップＳ８０）。次いで、復号装置４０３は、上述の条件(D5)〜(F5)を全て満たすか否かを判定する（ステップＳ８１〜Ｓ８３）。
【００８９】
ステップＳ８１〜Ｓ８３の判定結果が全て肯定的である場合、ステップＳ８４に進み、復号装置４０３は、次いで、ハッシュ計算により(c1,c2,c3)からハッシュ値を求め、これをvとする。そして、復号装置４０３は、(c1,c2,c3)を伸長写像により伸長する（ステップＳ８５）。次いで、復号装置４０３は、式１６により射影表現による演算でべき乗を計算することにより、検査式に用いるcを求める（ステップＳ８６）。
【００９０】
c=c1^（x1+y1*v）*c2^（x2+y2*v）・・・(式１６)
【００９１】
次いで、復号装置４０３は、cを圧縮写像によりアフィン表現に圧縮する（ステップＳ８７）。その後、復号装置４０３は、検査式‘c=c4’ が成立するか否かを判定する（ステップＳ８８）。この判定は、例えば、c及びc4のベクトル表現における各ベクトル成分の値が一致するか否かを判定することにより行うことができる。そして、当該判定結果が肯定的である場合、復号装置４０３は、式１７により射影表現による演算でべき乗を計算して、bを求める（ステップＳ８９）。
【００９２】
b= c1^z1*c2^z2・・・(式１７)
【００９３】
次いで、復号装置４０３は、式１８により平文msgを計算する（ステップＳ９０）。
【００９４】
msg=c3*b^（-1）・・・(式１８)
【００９５】
その後、復号装置４０３は、平文msgを圧縮写像によりアフィン表現に圧縮して（ステップＳ９１）、これを出力する。尚、ステップＳ８８の判定結果が否定的である場合、復号装置４０３は、rejectを出力し、以降の処理を中断する（ステップＳ９２）。また、ステップＳ８１〜Ｓ８３の判定結果が否定的である場合、復号装置４０３は、invalidを出力し、以降の処理を中断する（ステップＳ９３）。但し、いずれの場合であっても、復号装置４０３は、なにも出力せずに処理を終了するようにしても良い。
【００９６】
以上のような構成によれば、F_{p^(6*m)}上のトーラスについて、その位数が合成数であって、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であっても、入力が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【００９７】
[第６の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第６の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第６の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００９８】
（１）構成
本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は素数qで、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群は、6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００の構成は上述の第５の実施の形態と同様である。
【００９９】
本実施の形態にかかる送信装置３００´の有する暗号化装置３０３´の構成が、上述の第５の実施の形態にかかる暗号化装置３０３の構成と異なる点は以下の点である。上述の暗号化装置３０３は、平文が、F_{p^m}×F_{p^m}^*の元であるか否かを検査する際に、上述の条件(A5),(B5)のみを満たすか否かの判定を行い、条件(C5) 満たすか否かの判定を行わない。当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}^*で表現された、6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０３は、上述の第５の実施の形態と同様にして、圧縮暗号文(c1,c2,c3,c4)を生成する。以降は、上述の第５の実施の形態と同様である。
【０１００】
また、本実施の形態にかかる受信装置４００´の有する復号装置４０３´の構成が、上述の第５の実施の形態にかかる復号装置４０３の構成と異なる点は以下の点である。上述の復号装置４０３は、圧縮暗号文が、暗号が定義されている群上の元であるか否かを検査する際に、上述の条件(D5),(E5)のみ満たすか否かの判定を行い、条件(F5)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}^*で表現される暗号文であって、6次拡大体上の素数位数代数的トーラス上の元である。この場合、復号装置４０３は、上述の第５の実施の形態と同様にして、暗号化された平文を、秘密鍵を用いて復号する。
【０１０１】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる送信装置３００´が行う暗号化処理の手順について図１５を用いて説明する。ステップＳ６０〜Ｓ６２は上述の第５の実施の形態と同様である。そして、ステップＳ６２の判定結果肯定的である場合、暗号化装置３０３´は、ステップＳ６３を行わずに、ステップＳ６４以降の処理を行う。
【０１０２】
＜復号処理＞
次に、本実施の形態にかかる受信装置４００´が行う復号処理の手順について図１６を用いて説明する。ステップＳ８０〜Ｓ８２は上述の第５の実施の形態と同様である。そして、ステップＳ８２の判定結果肯定的である場合、復号装置４０３´は、ステップＳ８３を行わずに、ステップＳ８４以降の処理を行う。
【０１０３】
以上のような構成によれば、F_{p^(6*m)}上のトーラスについて、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合、F_{p^(6*m)}上のトラースの位数が素数であれば、これが合成数である場合に比べて、処理負担を軽減することができる。入力が正しい群の元であるか否かの各検査において、上述した条件(C5)や条件(F5)を満たすか否かの判定を必要としないからである。
【０１０４】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【０１０５】
＜変形例１＞
上述した各実施の形態において、送信装置３００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。受信装置４００で実行される各種プログラムについても同様である。
【０１０６】
また、上述した第１の実施の形態乃至第３の実施の形態において、暗号化装置３０１及び圧縮装置３０２は、送信装置３００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものとしたが、これに限らず、ハードウェアにより構成させるようにしても良い。復号装置４０１及び伸長装置４０２についても同様である。また、第５の実施の形態又は第６の実施の形態における暗号化装置３０３及び復号装置４０３についても同様である。
【０１０７】
＜変形例２＞
上述の第１の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを拡大体表現による演算で行うようにしたが、これらを射影表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(A1)〜(B1´)の全てを満たすか否かを判定することにより行う。(A1)は上述の第１の実施の形態と同様である。
【０１０８】
(A1) {0,…,p-1}^(6*m)に含まれる
(B1´) 射影表現の演算でmsg^(q) = 1を満たす
【０１０９】
当該検査結果が肯定的である場合、暗号化装置３０１は、射影表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。
【０１１０】
また、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、圧縮暗号文の各要素ciが以下の条件(C1)〜(D1´)を全て満たすか否かを判定することにより行う。条件(C1)は上述の第１の実施の形態と同様である。
【０１１１】
(C1) F_{p^m}×F_{p^m}^* に含まれる
(D1´) 拡大体表現による演算で、ci^(q) = 1 が成立する
【０１１２】
当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長 した暗号文(c1, c2, c3, c4)を得る。
【０１１３】
以上のように、平文を拡大体表現で表し、暗号文の計算を射影表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。特に、条件(D1’)の検証は射影表現を拡大体表現へ写像する前に実行できるため、(D1)の検証よりも効率的に不正な暗号文を検出できる。
【０１１４】
＜変形例３＞
上述の第２の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを拡大体表現で行うようにしたが、これを射影表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(B2´)を満たすか否かを判定することにより行う。
【０１１５】
（B2´）射影表現による演算で msg^｛p^(2*m)-p^(m)+1｝=1を満たす
【０１１６】
当該検査結果が肯定的である場合、暗号化装置３０１は、射影表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。また、伸長装置４０２が行う検査は上述の第２の実施の形態と同様である。
【０１１７】
以上のように、平文を拡大体表現現で表し、暗号文の計算を射影表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１１８】
＜変形例４＞
上述の第３の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを射影表現で行うようにしたが、これを拡大体表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(A3)〜(B3´)の全てを満たすか否かを判定することにより行う。条件(A3)は上述の第３の実施の形態と同様である。
【０１１９】
(A3) F_{p^m}×F_{p^m}^* に含まれる
(B3´) 拡大体表現による演算で msg^(q) = 1 が成立する
【０１２０】
当該検査結果が肯定的である場合、暗号化装置３０１は、拡大体表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、各要素c1,c2,c3,c4を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を出力する。
【０１２１】
また、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、圧縮暗号文の各要素ciが以下の条件(C3)〜(D3´)を全て満たすか否かを判定することにより行う。条件(C3)は上述の第３の実施の形態と同様である。
【０１２２】
(C3) F_{p^m}×F_{p^m}＾* に含まれる
(D 3´) 拡大体表現による演算で、 ci^{q} = 1 が成立する
【０１２３】
当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文の各要素を伸長写像によりアフィン表現から伸長 した暗号文(c1, c2, c3, c4)を得る。
【０１２４】
以上のように、平文をアフィン表現で表し、暗号文の計算を拡大対表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１２５】
＜変形例５＞
上述の第４の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを射影表現で行うようにしたが、これを拡大体表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、上述の条件(A3)を満たすか否かを判定すれば良い。一方、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、上述の条件(C3)を満たすか否かを判定すれば良い。
【０１２６】
以上のように、平文をアフィン表現で表し、暗号文の計算を拡大対表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１２７】
＜変形例６＞
上述の第１の実施の形態あるいは上述の変形例４において、復号装置４０１の伸長装置４０２は圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長したが、条件(D1)あるいは条件(D3’)の検査の際に得る拡大体表現を用いても良い。
【０１２８】
＜変形例７＞
上述の第３の実施の形態あるいは上述の変形例２において、復号装置４０１の伸長装置４０２は圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長したが、条件(D1’)の検査の際に得る射影表現から拡大体表現に伸長しても良い。
【０１２９】
＜変形例８＞
上述の第３の実施の形態において、暗号化装置３０１は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めるが、条件(B3)の検査の際に用いる射影表現の平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めても良い。
【０１３０】
＜変形例９＞
上述の変形例２において、暗号化装置３０１は、拡大体表現で表現された平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めるが、条件(B1’)の検査の際に用いる射影表現の平文msgより射影表現による演算によって射影表の現要素ciの組で表現される暗号文を求めても良い。
【０１３１】
＜変形例１０＞
上述の変形例４において、暗号化装置３０１は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された平文msgより拡大体表現による演算によって拡大体表現の要素ciの組で表現される暗号文を求めるが、条件(B3’)の検査の際に用いる拡大体表現の平文msgより拡大体表現による演算によって拡大体表現の要素ciの組で表現される暗号文を求めても良い。
【図面の簡単な説明】
【０１３２】
【図１】公開鍵暗号スキームの構成を例示する図である。
【図２】トーラス圧縮による公開鍵暗号スキームの構成を例示する図である。
【図３】Cramer-Shoup暗号における処理を概念的に示す図である。
【図４】第１の実施の形態にかかる鍵生成装置２００の構成を概念的に示す図である。
【図５】同実施の形態にかかるトーラス圧縮Cramer-Shoup暗号における暗号化装置３０１と圧縮装置３０２とが行う処理を概念的に示す図である。
【図６】同実施の形態にかかるトーラス圧縮Cramer-Shoup暗号における復号装置４０１と伸長装置４０２とが行う処理を概念的に示す図である。
【図７】同実施の形態にかかる送信装置３００が平文を暗号化して圧縮する処理の手順を示すフローチャートである。
【図８】同実施の形態にかかる受信装置４００が、送信装置３００から送信された圧縮暗号文を伸長して復号する処理の手順を示すフローチャートである。
【図９】暗号化処理及び圧縮処理を単純に組み合わせた場合に、入力が正しい群の元であるか否かを検査する処理を模式的に示す図である。
【図１０】伸長処理及び復号処理を単純に組み合わせた場合に、入力が正しい群の元であるか否かを検査する処理を模式的に示す図である。
【図１１】第５の実施の形態にかかる送信装置３００´及び受信装置４００´の構成を例示する図である。
【図１２】同実施の形態にかかる鍵生成装置２００が公開鍵及び秘密鍵を生成する処理の手順を示すフローチャートである。
【図１３】同実施の形態にかかる送信装置３００´が行う暗号化処理の手順を示すフローチャートである。
【図１４】同実施の形態にかかる受信装置４００´が行う復号処理の手順を示すフローチャートである。
【図１５】第６の実施の形態にかかる送信装置３００´が行う暗号化処理の手順を示すフローチャートである。
【図１６】同実施の形態にかかる受信装置４００´が行う復号処理の手順を示すフローチャートである。
【符号の説明】
【０１３３】
１００ パラメータ生成装置
２００ 鍵生成装置
３００ 送信装置
３０１ 暗号化装置
３０２ 圧縮装置
３０３ 暗号化装置
４００ 受信装置
４０１ 復号装置
４０２ 伸長装置
４０３ 復号装置
【技術分野】
【０００１】
本発明は、公開鍵暗号により平文を暗号化する暗号化装置、公開鍵暗号により暗号化された平文を復号する復号装置、暗号通信システム、方法及びプログラムに関する。
【背景技術】
【０００２】
通信路を流れる情報を保護するために、暗号を用いる方法がある。暗号には、例えば、共通鍵暗号と公開鍵暗号とがある。共通鍵暗号を用いる場合、通信相手と事前に鍵を共有しておく必要があるため、インターネットのような不特定多数との通信の際には鍵の共有や管理に大きな手間がかかる。公開鍵暗号は、事前に鍵を共有することなしに安全な通信を実現できるため、ネットワーク・セキュリティの基盤技術として幅広く用いられている。
【０００３】
現在、公開鍵暗号において典型的なセキュリティパラメータは1024ビット〜2048ビットである。セキュリティパラメータとは、公開鍵サイズや暗号文サイズを決定するパラメータであり、暗号方式の安全性に影響を与えるパラメータである。このセキュリティパラメータが大きくなれば、公開鍵サイズや暗号文サイズも大きくなる。解読が困難とされるセキュリティパラメータは年々大きくなっている。これは、計算機の進歩に伴い攻撃者の能力も向上するためである。公開鍵暗号では公開鍵サイズや暗号文サイズは、暗号方式により異なるが、セキュリティパラメータの数倍となる。このため、メモリ容量や通信帯域が十分でない装置ではセキュリティパラメータの増大が問題になる。
【０００４】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する方法が提案されている（例えば、非特許文献１、８参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。代数的トーラスの属する拡大体の次数nが高々二つの素数p,qの冪の積ｌ=(p^m)*(q^n)であるとき、圧縮率（＝圧縮前のビット数／圧縮後のビット数）は、ｌ/φ(ｌ)となることが知られている。ただし、φ（・）はオイラー関数である。尚、‘^’はべき乗を表す。p^mは、pのm乗である。小さいビット数の表現への変換は、拡大体表現を射影表現に変換する写像ρと射影表現をアフィン表現に変換する写像τによって行われる。暗号文を圧縮する場合の具体例を示す。拡大体表現の暗号文cを入力として計算を行い、圧縮暗号文γを得る（式１参照）。
【０００５】
τρ (c)=γ・・・（式１）
【０００６】
元のビット数の表現に戻すには、それぞれρ、τの逆写像を計算すればよい。ρの逆写像をψと書き、τの逆写像をτ―1と書くことにする。圧縮暗号文としてγが与えられたときに計算を行い、cを得る（式２参照）。
【０００７】
ψτ―1(γ)= c・・・（式２）
【０００８】
また、非特許文献１、７では、前記圧縮写像１、２と前記伸長写像１，２の構成法と、それらを用いて次のような拡大体表現をアフィン表現に圧縮する写像ρ6、アフィン表現を拡大体表現に伸長する写像‘ρ6-1’の構成法が示されている。圧縮写像ρ6は、6次拡大体F_{(p^m)^6}上の拡大体表現のトーラスＴの任意の元tを入力として計算し、アフィン表現F_{p^m}×F_{p^m}^* の要素との組を得る（式３参照）。
【０００９】
ρ6(t)= (a,b) ∈ F_{p^m}× F_{p^m}＾*・・・（式３）
【００１０】
尚、ここでは‘×’を直積を表すものとする。また、Aが集合であるとき、A^mはm個のAの直積集合となる。例えば、‘A^4 ＝ A × A × A × A’となる。具体的には例えば、‘{0,1,2}^2 = {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}’となる。ここで、F_{p^m}は、素体F_{p}のm次拡大体であり、 F_{p^m}の要素はベクトル表現を用いると、{0,…,p-1}^mの要素で表現できる。F_{p^m}^*は、F_{p^m}の乗法群であり、F_{p^m}^*の要素はベクトル表現を用いると、{0,…,p-1}^m ＼ {0}^m の要素で表される。‘＼’は集合の引き算を表す。
【００１１】
伸長写像‘ρ6-1’は、(a,b) ∈ F_{p^m}× F_{p^m}＾*を入力として計算し、6次拡大体F_{（p^m）^6}上の拡大体表現のトーラスＴの元tを得る（式４参照）。
【００１２】
ρ-1(a,b)＝t ∈ T・・・（式４）
【００１３】
また、非特許文献７では、F_{p^m}の6次拡大体上のトーラスの要素の拡大体表現{0,…,p-1}^(6*m)と射影表現{0,…,p-1}^(6*m)とアフィン表現F_{p^m}×F_{p^m}^*に対して、上記のρ、ψ、τ、τ-1の構成法を示し、それを元に（式３）と（式４）との写像を構成している。このとき、拡大体表現と射影表現とに対する演算は、共にF_{p^(6*m)}の演算で、非特許文献１、７ではF_{p^(6*m)}の演算をF_{((p^m)^3)^2}の演算として実現している。アフィン表現の要素は、演算することができない。
【００１４】
また、xがTの要素であるか否かの検査は、例えば、F_{p^(6*m)}上の演算で以下の２通りの方法で行うことができる。
方法１：(p^(6*m)-1)/ (p^(3m)-1)乗して‘１’となる且つ(p^(6*m)-1)/ (p^(2m)-1)乗して‘1’となることが成立するか否か調べる。
方法２：(p^(2m)-p^m+1)乗して‘1’となることが成立するか否か調べる。
【００１５】
離散対数問題系を利用したElGamal暗号（例えば、非特許文献４参照）やCramer-Shoup暗号（例えば、非特許文献２参照）などは、暗号化可能な平文のサイズと比べて、鍵長と暗号文とのサイズが大きいという問題を抱えている。代数的トーラス上で構成されたElGamal暗号の公開鍵と暗号文とは代数的トーラス上の要素となることを利用し、公開鍵と暗号文とを圧縮することでサイズを抑える方法がある（例えば、非特許文献１、５ 〜６参照）。
【００１６】
【非特許文献１】K.Rubin and A.Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, pp. 349-365, 2003.
【非特許文献２】R.Ｃｒａｍｅｒ and V.Shoup, “A practical key cryptosystem provably secure against adaptive chosen ciphertext attack”, CRYPTO 1998, LNCS 1462, pp. 13-25, 1998.
【非特許文献３】V.Shoup, “ACE Encrypt: The Advanced Cryptographic Engine’s Public Key Encryption Scheme”, “http://www.zurich.ibm.com/security/ace/ace_encrypt.pdf”,2000.
【非特許文献４】Taher El Gamal: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4): 469-472 (1985)
【非特許文献５】Marten van Dijk, David P. Woodruff: Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO 2004: 157-178
【非特許文献６】Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff: Practical Cryptography in High Dimensional Tori. EUROCRYPT 2005: 234-250
【非特許文献７】Robert Granger, Dan Page, Martijn Stam: A Comparison of CEILIDH and XTR. ANTS 2004: 235-249
【発明の開示】
【発明が解決しようとする課題】
【００１７】
公開鍵暗号において暗号化処理や復号処理を安全に実現するためには、処理の対象が、暗号が定義される群の要素であるか否かを検査する必要がある。また、代数的トーラスにおける圧縮処理や伸長処理においても、暗号が定義される群の要素でなければ、正しく写像することができない。しかし、非特許文献１，５〜７に示したような既存の代数的トーラスを用いた暗号系では、暗号化処理や復号処理への入力が、暗号が定義される群の要素であるか否かをどの時点でどのように検査するかについて検討する必要がある。例えば、代数的トーラスにおける圧縮処理及び伸長処理と公開鍵暗号の暗号化処理及び復号処理とを単純に組み合わせた場合、入力がそれぞれの処理で、暗号が定義される群上の元であるかを判定するための処理に、冗長な処理を含む恐れがある。このため、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが望まれていた。
【００１８】
本発明は、上記に鑑みてなされたものであって、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが可能な暗号化装置、復号装置、暗号通信システム、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
上述した課題を解決し、本発明は、復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置であって、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２０】
また、本発明は、F_{p^m}の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}× F_｛p＾m｝^*(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置であって、暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得手段と、前記平文msgに含まれるベクトル成分が、アフィン表現F_{p^m}×F＿｛p＾m｝^*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_｛p^m｝^*上の要素の組で表現される暗号文cを求める暗号化手段を備えることを特徴とする。
【００２１】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{{0,・・・,p-1}^{6*m}}(p:素数、m:自然数)で表現された平文msgを暗号化する暗号化装置であって、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、 前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現F_{p^m} ×F_{p^m}^*に写像する圧縮手段とを備えることを特徴とする。
【００２２】
また、本発明は、F_{p^m}の6次拡大体(p：素数、m：自然数)上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*、(^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、前記暗号化装置は、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、前記復号装置は、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２３】
また、本発明は、F_{p^m}の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数、^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、前記暗号化装置は、暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、前記復号装置は、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備えることを特徴とする。
【００２４】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*(p:素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得ステップと、前記平文msgに含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める暗号化ステップとを含むことを特徴とする。
【００２５】
また、本発明は、F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、暗号化の対象である平文msgと、公開鍵とを取得する取得ステップと、前記平文msgが、{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定ステップと、前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化ステップと、前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮ステップとを含むことを特徴とする。
【００２６】
また、本発明は、復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置で実行される復号方法であって、ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得ステップと、前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長ステップと、前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号ステップとを含むことを特徴とする。
【００２７】
また、本発明は、プログラムであって、上記記載の方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２８】
本発明によれば、冗長な処理を行うことなく、暗号化処理や復号処理への入力が、暗号が定義される群の元であるか否かを判定することが可能になる。
【発明を実施するための最良の形態】
【００２９】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号装置、暗号通信システム、方法及びプログラムの最良な実施の形態を詳細に説明する。
【００３０】
[第１の実施の形態]
（１）構成
＜公開鍵暗号スキーム＞
まず、本実施の形態にかかる公開鍵暗号スキームについて説明する。図１は、公開鍵暗号スキームの構成を例示する図である。公開鍵暗号スキームにおいては、パラメータ生成装置１００が、公開鍵暗号に関する公開情報を生成する。公開情報としては、公開鍵に関する情報として、群の要素やハッシュ関数などの情報や、暗号系が定義される群に関する情報として、位数や生成元の情報がある。公開情報のうち群に関する情報は、後述するCramer-Shoup暗号の場合、(p, q, m, n)である。そして、鍵生成装置２００が、公開情報を用いて公開鍵と、これに対応する秘密鍵とを生成する。暗号化装置３０１を有する送信装置３００には、鍵生成装置２００が生成した公開鍵と、暗号化の対象の平文が入力される。この平文は、送信装置３００において予め記憶されたものであっても、送信装置３００が生成したものであっても、他の通信装置から受信したものであっても、記憶媒体から読み出したものであっても良い。暗号化装置３０１は、公開鍵を用いて平文を暗号化して暗号文を生成しこれを受信装置４００に送信する。復号装置４０１を有する受信装置４００は、暗号文を受信すると、当該暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて暗号文を復号することにより、平文を得る。
【００３１】
＜トーラス圧縮：公開鍵暗号スキーム＞
次に、トーラス圧縮による公開鍵暗号スキームについて図２を用いて説明する。トーラス圧縮による公開鍵暗号スキームにおいては、送信装置３００は暗号化装置３０１に加え圧縮装置３０２を更に有する。受信装置４００は、復号装置４０１に加え伸長装置４０２を更に有する。パラメータ生成装置１００及び鍵生成装置２００の構成は上述と同様であるため、その説明を省略する。暗号化装置３０１は、公開鍵を用いて平文を暗号化して暗号文を生成するが、この暗号化を圧縮しない表現で行う。生成された暗号文は、ベクトル形式により表現される。圧縮装置３０２は、暗号文に含まれるベクトル成分を圧縮して出力する。圧縮された暗号文（圧縮暗号文という）を送信装置３００は受信装置４００に送信する。伸長装置４０２は、圧縮暗号文に含まれるベクトル成分を伸長する。復号装置４０１は、伸長された暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて当該暗号文を復号することにより、平文を得る。ここでの復号は圧縮しない表現で行う。尚、同図では、鍵生成装置２００が行う公開鍵及び秘密鍵の生成と、暗号化装置３０１が行う暗号化と、復号装置４０１が行う復号とは拡大体表現による演算で行う。
【００３２】
尚、パラメータ生成装置１００、鍵生成装置２００、送信装置３００及び受信装置４００は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。また、送信装置３００及び受信装置４００は、インターネット等のネットワーク（図示せず）を介して接続されて通信を行う。また、送信装置３００の有する暗号化装置３０１及び圧縮装置３０２は、送信装置３００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものである。同様に、受信装置４００の有する復号装４００及び伸長装置４０２は、受信装置４００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものである。
【００３３】
＜Cramer-Shoup暗号＞
次に、公開鍵暗号スキームで説明した送信装置３００及び受信装置４００の構成において、Cramer-Shoup暗号を適用する構成について説明する。図３は、Cramer-Shoup暗号における処理を概念的に示す図である。鍵生成装置２００は、公開鍵（p,q,g,g~,e,f,h）を生成する。尚、p,qは素数でそれぞれ群G^の位数とその部分群Gの位数、gは暗号が定義される部分群G（位数はq）の生成元、g~,e,f,hも群Gの元とする。平文msgも部分群Gの元でなければならない。一方、当該公開鍵に対応する秘密鍵(x1, x2, y1, y2, z1, z2)は‘1’から‘q-1’までの整数又は‘0’から‘q-1’までの整数とする。送信装置３００の有する暗号化装置３０１は、公開鍵を用いて平文msgに対応する暗号文(c1, c2, c3, c4)を計算する。具体的には、暗号化装置３０１は、qを用いて‘0≦r＜q-1’なる乱数rを生成する。そして、暗号化装置３０１は、ｃ1としてg^rを求め、ｃ2としてg~^rを求め、bとしてh^rを求める。そして、暗号化装置３０１は、b*mをｃ3として求める。‘*’は乗算を表す。次いで、暗号化装置３０１は、(c1, c2, c3)についてハッシュ関数を用いた計算により、ハッシュ値H(c1, c2, c3)を求める。そして、暗号化装置３０１は、ｃ4として、e^r*f^r*vを求める。この結果、暗号文(c1, c2, c3, c4)が得られる。この暗号文(c1, c2, c3, c4)を送信装置３００は受信装置４００に送信する。
【００３４】
一方、受信装置４００は、暗号文(c1, c2, c3, c4)を受信すると、復号装置４０１が、秘密鍵(x1, x2, y1, y2, z1, z2)と暗号文(c1, c2, c3, c4)とから正当な平文であるか否かの判定を行い、当該判定結果が肯定的である場合、平文msgを計算する。具体的には、復号装置４０１は、(c1, c2, c3, c4)の各要素が、群G＾の元であるか否かを判定する。当該判定結果が肯定的である場合、復号装置４０１は、bとして、ｃ1^z1*ｃ2^z2を求める。次いで、復号装置４０１は、(c1, c2, c3)の各要素が、群G^の部分群Gの元であるか否かを判定する。また、復号装置４０１は、暗号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求める。そして、復号装置４０１は、当該値と暗号文の要素とを用いた以下の検査式５が成立するか否かを判定する。また、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する。
【００３５】
c4=c1^（x1+y1*v）*c2^（x2+y2*v）・・・（式５）
【００３６】
＜トーラス圧縮Cramer-Shoup暗号＞
以上のような構成において、トーラス圧縮によるCramer-Shoup暗号（トーラス圧縮Cramer-Shoup暗号という）について説明する。ここでは、F_{p^(6*m)}上のトーラスの位数は合成数で、平文は拡大体表現で表し、暗号文の計算を拡大体表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群Gは、F_{p^m}の6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。図４は、本構成における鍵生成装置２００の構成を概念的に示す図である。鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数部分群Gの生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。Cramer-Shoup暗号の公開鍵の計算においては、べき乗計算も乗算も素体上で行うが、本実施の形態のトーラス圧縮Cramer-Shoup暗号の公開鍵の計算においては、べき乗計算と乗算とは拡大体上で行う。６次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算は拡大体F_{p^(6*m)}上の演算を用いる。
【００３７】
次に、トーラス圧縮Cramer-Shoup暗号において、送信装置３００の有する暗号化装置３０１と圧縮装置３０２との構成について説明する。図５は、トーラス圧縮Cramer-Shoup暗号における暗号化装置３０１と圧縮装置３０２とが行う処理を概念的に示す図である。暗号化装置３０１には、鍵生成装置２００が生成した公開鍵が入力され、暗号化の対象の平文msgが入力される。尚、暗号化装置３０１は、拡大体表現{{0,…,p-1}^ (6*m)}で表現されたmsg毎に平文を処理するものとする。暗号化装置３０１は、まず、入力された平文msgが正しい群の元であるか否かを検査する。この検査は、平文msgが、以下の条件(A1)〜(C1)の全てを満たすか否かを判定することにより行う。
【００３８】
(A1){0,…,p-1}^(6*m)に含まれる
(B1_1)拡大体表現の演算で msg^{p^(2*m)-p^(m)} = 1を満たす
(B 1_2)拡大体表現の演算で msg^(q) = 1を満たす
【００３９】
条件(A1)を満たす場合、平文msgは、6次拡大体上の元である。条件(B1_1)を満たす場合、平文msgは、合成数位数代数的トーラス上の元である。条件(B1_2)を満たす場合、平文msgは、合成数位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。条件(B1_1)を判定するための計算は効率的に実行できるため、この計算を、条件(B1_2)を判定するための計算の前に行うことで効率的な検査が可能となる。これらの条件を用いた検査結果が肯定的である場合、入力された平文msgは、拡大体表現{{0,…,p-1}^(6*m)}で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０１は、公開鍵を用いて平文msgを暗号化する。具体的には、暗号化装置３０１は、Cramer-Shoup暗号において説明したように、乱数を生成し、公開鍵に含まれるg~,e,fを用いて、当該乱数を乗数に用いたべき乗計算を行い、暗号文の要素であるc1,c2を求める。そして、暗号化装置３０１は、乗算を行うことにより平文マスクを行い、暗号文の要素であるc3を求める。また、暗号化装置３０１は、公開鍵に含まれるe,fと、乱数とを用いてハッシュ計算を行ってハッシュ値を求め、当該ハッシュ値を乗数に用いたべき乗計算を行うことにより、暗号文の要素であるc4を求める。この暗号文は、復号の対象である平文msgを含んで暗号化されたものとなる。尚、ここでの各乗算は拡大体F_p^{(6*m)}上で行う。次いで、圧縮装置３０２は、各要素c1,c2,c3,c4を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を出力する。出力された圧縮暗号文はアフィン表現となっている。送信装置３００は出力されたこの圧縮暗号文を受信装置４００に送信する。
【００４０】
次に、トーラス圧縮Cramer-Shoup暗号において、受信装置４００の有する復号装置４０１と伸長装置４０２との構成について説明する。図６は、トーラス圧縮Cramer-Shoup暗号における復号装置４０１と伸長装置４０２とが行う処理を概念的に示す図である。伸長装置４０２には、送信装置３００が送信した圧縮暗号文(c1, c2, c3, c4)が入力される。尚、伸長装置４０２は、アフィン表現F_{p^m}×F_{p^m}^*の組毎に処理を行うものとする。伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査する。この検査は、圧縮暗号文の各要素ciが以下の条件(C1)〜(D1)を全て満たすか否かを判定することにより行う。
【００４１】
(C1) F_{p^m}×F_{p^m}^* に含まれる
(D1)拡大体表現による演算で、ci^(q) = 1 が成立する
【００４２】
これらの検査を伸長写像の前に行うことにより伸長写像における無駄な計算を省くことができる。尚、条件(C1)を満たす場合、ciは、アフィン表現により表現されている。条件(D1)を満たす場合、ciは、代数的トーラスの位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現F_{p^m}×F_{p^m}^*で表現される暗号文であって、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の部分群Gの元である。この場合、伸長装置４０２は、(D1)において拡大体表現に写像された圧縮暗号文の各要素を伸長写像によりアフィン表現から伸長 した暗号文(c1, c2, c3, c4)を得る。復号装置４０１には、秘密鍵が入力される。そして、復号装置４０１は、Cramer-Shoup暗号において説明したように、暗号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求める。そして、復号装置４０１は、当該値と暗号文の要素とを用いた検査式が成立するか否かを判定する。また、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する。この結果、平文msgが得られる。
【００４３】
（２）動作
＜暗号化処理及び圧縮処理＞
次に、本実施の形態にかかる送信装置３００が平文を暗号化して圧縮する処理の手順について図７を用いて説明する。送信装置３００の暗号化装置３０１には、鍵生成装置２００が生成した公開鍵が入力され、暗号化の対象の平文が入力される。暗号化装置３０１は、まず、入力された平文msgが正しい群の元であるか否かを検査する（ステップＳ１）。この検査は、平文msgが、上述の条件(A1),(B1_1),(B1_2)の全てを満たすか否かを判定することにより行う。ステップＳ１の検査結果が肯定的である場合、暗号化装置３０１は、Cramer-Shoup暗号において説明したように、乱数を生成して（ステップＳ２）、公開鍵に含まれるg~,e,fを用いて、当該乱数を乗数に用いたべき乗計算と乗算とを行い（ステップＳ３）、暗号文の要素であるc1,c2を求める。そして、暗号化装置３０１は、乗算を行うことにより平文マスクを行い、暗号文の要素であるc3を求める。また、暗号化装置３０１は、公開鍵に含まれるe,fと乱数とを用いてハッシュ計算を行ってハッシュ値を求め（ステップＳ４）、当該ハッシュ値を乗数に用いたべき乗計算を行うことにより（ステップＳ５）、暗号文の要素であるc4を求める。尚、ここでの各乗算は拡大体F_{p^(6*m)}上で行う。以上のようにして暗号化装置３０１が暗号化処理を行った後、圧縮装置３０２が以下の通りに圧縮処理を行う。圧縮装置３０２は、ステップＳ２〜Ｓ５により生成された暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成して（ステップＳ６）、これを出力する（ステップＳ７）。そして、ステップＳ６で出力された圧縮暗号文を送信装置３００は受信装置４００に送信する。尚、ステップＳ１の検査結果が否定的である場合、暗号化装置３０１は、エラーであるとして以降の処理を中断する。
【００４４】
＜伸長処理及び復号処理＞
次に、本実施の形態にかかる受信装置４００が、送信装置３００から送信された圧縮暗号文を伸長して復号する処理の手順について図８を用いて説明する。受信装置４００の伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する（ステップＳ２０）。この検査は、圧縮暗号文の各要素ciが上述の条件(C1)〜(D1)を全て満たすか否かを判定することにより行う。そして、ステップＳ２０の検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文を伸長写像により伸長して暗号文 (c1, c2, c3, c4)を求める（ステップＳ２１）。以上のようにして伸長装置４０２が伸長処理を行った後、復号装置４０１が以下の通りに復号処理を行う。尚、復号装置４０１には、秘密鍵が入力される。復号装置４０１は、ステップＳ２１で求められた暗号文の要素号文の要素c1,c2,c3を用いてハッシュ関数による計算を行い（ステップＳ２２）、要素c1,c2と秘密鍵x1, x2, y1, y2とを用いてべき乗計算と乗算とにより検査式に用いる値を求め（ステップＳ２３）、当該値と暗号文の要素とを用いた上述の検査式５が成立するか否かを判定する（ステップＳ２４）。そして、当該判定結果が肯定的である場合、復号装置４０１は、要素c1,c2と秘密鍵z1,z2とを用いてべき乗計算を行い、当該計算結果の逆元を導出した後、要素c3を用いて乗算を行うことにより、暗号化された平文msgを復号する（ステップＳ２５）。この結果、平文msgが得られる。尚、ステップＳ２０の検査結果が否定的である場合、伸長装置４０２は、エラーであるとして以降の処理を中断する。
【００４５】
以上のような構成によれば、送信装置３００で平文を暗号化して暗号文を圧縮し、受信装置４００で圧縮暗号文を伸長して復号する場合に、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【００４６】
例えば、F_{p^m}の6次拡大体上のトーラスを使う暗号系と圧縮処理とを単純に組み合わせた場合、図９に示されるように、暗号化処理の前の他、圧縮処理の前にも入力が正しい群の元であるか否かを検査する必要がある。しかし、上述した実施の形態においては、圧縮処理の前にこの検査を行う必要がなくなるため、冗長な処理を省くことが可能になる。同様に、F_{p^m}の6次拡大体上のトーラスを使う復号系と伸長処理とを単純に組み合わせた場合、図１０に示されるように、伸長処理の前の他、復号処理の前にも入力が正しい群の元であるか否かを検査する必要がある。しかし、上述した実施の形態においては、復号処理の前にこの検査を行う必要がなくなるため、冗長な処理を省くことが可能になる。
【００４７】
つまり、上述の実施の形態のように、合成数位数トーラス上の素数位数部分群を暗号系に用いる場合、入力された平文がF_{p^m}の6次拡大体上の合成数位数トーラス上の元であり素数位数部分群の元であれば、暗号化処理の結果得られる暗号文の各要素は、6次拡大体のトーラスの元となる。このため、圧縮処理の前にトーラスの元であるか否かの検査は不要となる。また、伸長後の暗号文の各要素が6次拡大体上の合成数位数トーラス上の元であり素数位数部分群の元であるか否かの検査を伸長処理の前に行うことで、不正な暗号文を早い段階で識別し、不正な暗号文が入力された際の処理を軽減できる。
【００４８】
尚、上述の実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査する際に、上述の条件(B1_2)を判定するための計算の前に条件(B1_1)を判定するための計算を行うようにした。これは部分群の位数qをべき指数とするべき乗を行う前に代数的トーラスの要素であるか否かを検査するのは冗長な検査であるが、大量の不正な平文が入力されうる環境であっても効率的に検査できるという効果がある。なぜなら、F_{p^m}上の要素xについて、(x^(p^m))の計算はフロベニウス写像（参考文献参照）を用いて効率的に計算できることが知られている。F_{p^m}の6次拡大体上のトーラスの位数は‘p^(2*m)-p^(m)+1’であるため、p^m乗フロベニウス写像を利用することでx^{ p^(2*m)-p^(m)+1}を効率的に計算できるからである。
（参考文献）X: Henri Cohen, Gerhard Frey: Handbook of elliptic and hyperelliptic curve cryptography : Chapman & Hall/CRC
【００４９】
[第２の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５０】
上述の第１の実施の形態においては、合成数位数トーラス上の素数位数部分群を暗号系に用いる場合について説明した。本実施の形態においては、素数位数トーラスを暗号系に用いる場合について説明する。即ち、ここでは、F_{p^(6*m)}上のトーラスの位数は素数で、平文は拡大体表現で表し、暗号文の計算を拡大体表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群は、6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００は、公開情報である素数位数トーラス上の生成元gとその位数qを入力として、乱数を得て、当該乱数を用いたべき乗計算と乗算とを行うことにより公開鍵を計算する。本実施の形態の公開鍵の計算においては、上述の第１の実施の形態と同様に、べき乗計算と乗算とは拡大体表現で行う。また、F_{p^m}の6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算は拡大体F_{p^(6*m)}上の演算を用いる。
【００５１】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第１の実施の形態と異なる点について説明する。本実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かの検査を行う際に、上述の条件(A1),(B1_1)のみを満たすか否かの判定を行う。
【００５２】
当該検査結果が肯定的である場合、入力された平文msgは、拡大体表現{{0,…,p-1}^(6*m)}で表現された、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０１は、上述した第１の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。以降は、上述した第１の実施の形態と同様である。
【００５３】
伸長装置４０２が行う検査は上述の第２の実施の形態と同様で、入力が正しい群の元であるか否かの検査である。送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する際に、上述の条件(C1)のみを満たすか否かを判定し、上述の条件(D1)を満たすか否かの判定を行わない。
【００５４】
当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、伸長装置４０２は、上述の第１の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。以降は、上述した第１の実施の形態と同様である。
【００５５】
以上のように、素数位数トーラスを暗号系に用いる場合、素数位数トーラス上の全ての要素を暗号系に用いることができる。そのため、暗号化の対象である平文の各ベクトル成分が、トーラス上の元であるか否かのみ検査すれば十分である。従って、本実施の形態においては、上述した条件(B1_2)や(D1)を満たすか否かを判定を必要とせず、合成数位数のトーラス上の素数位数部分群を用いた場合と比べ検査のための処理負担が軽減される。
【００５６】
[第３の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第３の実施の形態について説明する。なお、上述の第１の実施の形態又は上述の第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５７】
上述の各実施の形態においては、平文を拡大体表現で表し、暗号文の計算を拡大体表現で行う場合について説明した。本実施の形態においては、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合について説明する。特にここでは、F_｛p^(6*m)｝上のトーラスの位数が合成数である場合を取り扱う。即ち、ここでは、F_｛p^(6*m)｝上のトーラスの位数は合成数で、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、F_{p^m}の6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。本実施の形態における鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数巡回部分群の生成元とその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。尚、本実施の形態の公開鍵の計算においては、べき乗計算と乗算とは射影表現で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００５８】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第１の実施の形態と異なる点について説明する。ここでは、暗号化装置３０１はアフィン表現 F_{p^m}×F_{p^m}＾*で表現されたmsg毎に平文を処理するものとする。暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かの検査を、平文msgが、以下の条件(A3)〜(B3)の全てを満たすか否かを判定することにより行う。
【００５９】
(A3) F_{p^m}×F_{p^m}^* に含まれる
(B3)射影表現による演算で msg^(q) = 1 が成立する
【００６０】
条件(A3)を満たす場合、平文msgは、アフィン表現により表現されている。条件(B3)を満たす場合、平文msgは、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０１は、上述した第１の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。但しここでは、暗号化装置３０１は、上述したように、代数的トーラス上の演算を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行って、アフィン空間F_{p^m}×F_{p^m}＾*上の要素ciの組で表現される暗号文を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。
【００６１】
次に、本実施の形態における受信装置４００の有する伸長装置４０２の構成が、上述の第１の実施の形態と異なる点について説明する。ここでは、伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査を、圧縮暗号文の各要素ciが以下の条件(C3)〜(D3)を全て満たすか否かを判定することにより行う。
【００６２】
(C3) F_{p^m}×F_{p^m}＾* に含まれる
(D3)射影表現による演算で、ci^(q) = 1が成立する
【００６３】
条件(C3)を満たす場合、ciは、アフィン表現により表現されている。条件(D3)を満たす場合、ciは、位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の合成位数代数的トーラス上の素数位数部分群の元である。この場合、伸長装置４０２は、上述の第１の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。但しここでは、伸長装置４０２は、上述したように、伸長写像や代数的トーラス上の演算を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。復号装置３０１が行う復号処理は上述の第１の実施の形態と同様である。
【００６４】
以上のような構成によれば、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であっても、入力が正しい群の元であるか否かの検査において、冗長な処理を省くことができる。また、全ての演算を射影表現で行うことによって、射影表現と拡大体表現との間の写像処理を省き、アフィン表現と射影表現との間の写像のみで判定装置を構成できる。
【００６５】
[第４の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００６６】
上述の第３の実施形態においては、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であって、F_{p^(6*m)}上のトーラスの位数は合成数である場合について説明した。本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は素数である場合について説明する。即ち、ここでは、F_{p^(6*m)}上のトーラスの位数は素数で、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、F_{p^m}の6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００は、公開情報である素数位数トーラス上の生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算と、乗算とにより公開鍵を計算する。尚、本実施の形態における公開鍵の計算においては、上述の第３の実施の形態と同様に、べき乗計算と乗算とは射影表現上で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００６７】
次に、本実施の形態における送信装置３００の有する暗号化装置３０１の構成が、上述の第３の実施の形態と異なる点について説明する。本実施の形態においては、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査する際に、上述の(A3)のみを満たすか否かを判定を行い、上述した条件(B3)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０１は、上述した第１の実施の形態乃至第３の実施の形態と同様にして、公開鍵を用いて平文msgを暗号化する。以降は、上述した第１の実施の形態乃至第３の実施の形態と同様である。
【００６８】
次に、本実施の形態における受信装置４００の有する伸長装置４０２の構成が、上述の第３の実施の形態と異なる点について説明する。本実施の形態においては、伸長装置４０２は、送信装置３００が送信した圧縮暗号文の各要素が正しい群の元であるか否かを検査する際に、上述の(C3)のみを満たすか否かを判定を行い、上述した条件(D3)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、F_{p^m}の6次拡大体上の素数位数代数的トーラス上の元である。この場合、伸長装置４０２は、上述した第１の実施の形態乃至第３の実施の形態と同様にして、圧縮暗号文を伸長写像により伸長して暗号文を得る。以降は、上述した第１の実施の形態乃至第３の実施の形態と同様である。
【００６９】
以上のような構成によれば、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合、F_{p^(6*m)}上のトーラスの位数が素数であれば、これが合成数である場合に比べて、処理負担を軽減することができる。入力が正しい群の元であるか否かの各検査において、上述した条件(B3) や条件(D3)を満たすか否かの判定を必要としないからである。
【００７０】
[第５の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００７１】
（１）構成
本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は合成数で、トーラス上の素数位数群の位数はqで、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。暗号が定義される群は、6次拡大体上の代数的トーラス上の位数qの部分群である素数位数部分群Gとなる。本実施の形態における鍵生成装置２００は、公開情報である合成数位数トーラス上の素数位数部分群の生成元gとその位数qを入力として、乱数を得て、乱数を用いたべき乗計算により公開鍵を計算する。そして、鍵生成装置２００は、公開鍵を圧縮写像により圧縮して、圧縮公開鍵を生成する。尚、本実施の形態の公開鍵の計算においても、上述の第３の実施の形態又は第４の実施の形態と同様に、べき乗計算と乗算とは射影表現上で行う。また、6次拡大体上の代数的トーラスを用いて構成する場合、圧縮写像や伸長写像や代数的トーラス上の演算はアフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算を用いる。
【００７２】
次に、本実施の形態にかかる送信装置３００´の構成について図１１を用いて説明する。本実施の形態においては、送信装置３００´は、暗号化装置３０３を有する。暗号化装置３０３には、鍵生成装置２００が生成した圧縮公開鍵と、暗号化の対象である平文msgとが入力される。尚、暗号化装置３０３は、アフィン表現 F_{p^m}×F_{p^m}＾*の組で表現されるmsg毎に処理するものとする。暗号化装置３０３は、平文msgが、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否かを検査する。この検査は、以下の条件(A5)〜(C5)を全て満たすか否かを判定することにより行う。
【００７３】
(A5)平文msgのベクトル表現による各ベクトル成分について、1項目からm項目までの各項目が‘0’から‘p-1’までの範囲に入っている
(B5)平文msgのベクトル表現による各ベクトル成分について、‘m+1’項目から2m項目までの各項目が‘0’から‘p-1’までの範囲に入っている且つ全て項目が‘0’でない
(C5)平文msgを伸長して射影表現に変換し、射影表現による演算で以下の条件式６が成立する
msg^（q）=1・・・(式６)
【００７４】
全ての項目について条件(A 5)及び(B5)を満たす場合、平文msgは、アフィン表現により表現されている。条件(C5)を満たす場合、平文msgは、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された、6次拡大体上の合成位数代数的トーラス上の素数位数部分群Gの元である。この場合、暗号化装置３０３は、圧縮公開鍵と生成元とを伸長し、べき乗計算、圧縮写像及び伸長写像及びハッシュ計算などの各種処理を行って暗号文(c1,c2,c3,c4)を生成し、これを圧縮して圧縮暗号文(c1,c2,c3,c4)を生成して出力する。この圧縮暗号文を送信装置３００´は受信装置４００´に送信する。
【００７５】
次に、本実施の形態にかかる受信装置４００´の構成について図１１を用いて説明する。本実施の形態においては、受信装置４００´は、復号装置４０３を有する。復号装置４０３には、鍵生成装置２００が生成した秘密鍵と、送信装置３００´が送信した圧縮暗号平文とが入力される。復号装置４０３は、圧縮暗号文(c1,c2,c3,c4)の各要素がF_{p^m}×F_{p^m}^*の元であるか否かを検査する。この検査は、以下の条件(D5)〜(F5)を全て満たすか否かを判定することにより行う。
(D5)ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、1項目からm項目までの各項目が‘0’から‘p-1’までの範囲に入っている
(E5)ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、‘m+1’項目から2m項目までの各項目が‘0’から‘p-1’までの範囲に入っている且つ全て項目が‘0’でない
(F5)各ciを伸長して射影表現に変換し、射影表現による演算で以下の条件式７が成立する
ci^q=1・・・(式７)
【００７６】
各ciの全ての項目について条件(D5)及び条件(E5)を満たす場合、ciは、アフィン表現により表現されている。各ciについて条件(F5)を満たす場合、ciは、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。従って、当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現される暗号文であって、6次拡大体上の合成位数代数的トーラス上の位数qの部分群である素数位数部分群Gの元である。この場合、復号装置４０３は、暗号化された平文を、秘密鍵を用いて復号する。具体的には、復号装置４０３は、ハッシュ計算、圧縮写像、検査式による判定及び平文の計算等の各種処理を行うことにより、平文を得る。
【００７７】
（２）動作
＜鍵生成処理＞
次に、本実施の形態にかかる鍵生成装置２００が公開鍵及び秘密鍵を生成する処理の手順について図１２を用いて説明する。鍵生成装置２００は、パラメータ生成装置１００が生成した公開情報に含まれる、6次拡大体上の合成位数代数的トーラスの位数として公開パラメータqを取得する（ステップＳ４０）。次いで、鍵生成装置２００は、取得した公開パラメータqを用いて、‘0＜w＜q’なる乱数wを生成する（ステップＳ４１）。また、鍵生成装置２００は、公開パラメータqを用いて、‘0≦x1,x2,y1,y2,z1,z2＜q’なる乱数x1,x2,y1,y2,z1,z2を生成する（ステップＳ４２）。鍵生成装置２００は、公開情報に含まれる、素数位数トーラスの生成元gを取得する（ステップＳ４３）。次いで、鍵生成装置２００は、以下の式８〜１１によりべき乗を計算する（ステップＳ４４）。
【００７８】
g~=g^w・・・(式８)
e=g^（x1+w*x2）・・・(式９)
f=g^（y1+w*y2）・・・(式１０)
h=g^（z1+w*z2）・・・(式１１)
【００７９】
そして、鍵生成装置２００は、g~,e,f,hを圧縮写像によりアフィン表現に圧縮する（ステップＳ４５）。次いで、鍵生成装置２００は、（g~,e,f,h）を圧縮公開鍵として出力する（ステップＳ４６）。また、鍵生成装置２００は、（x1,x2,y1,y2,z1,z2）を秘密鍵として出力する（ステップＳ４７）。
【００８０】
＜暗号化処理＞
次に、本実施の形態にかかる送信装置３００´が行う暗号化処理の手順について図１３を用いて説明する。尚、送信装置３００´の暗号化装置３０３は、上述した鍵生成装置２００が生成した圧縮公開鍵（g~,e,f,h）と、暗号化の対象である平文msgを予め取得しているものとする。暗号化装置３０３は、平文msgがF_{p^m}×F_{p^m}^*の元であるか否かを検査する。具体的には、暗号化装置３０３は、まず、平文msgのベクトル表現による各ベクトル成分について、1項目からm項目までと‘m+1’項目から2m項目までとに分割する（ステップＳ６０）。次いで、暗号化装置３０３は、上述の条件(A5)〜(C5)を全て満たすか否かを判定する（ステップＳ６１〜Ｓ６３）。
【００８１】
ステップＳ６１〜Ｓ６３の判定結果が１つでも否定的である場合、暗号化装置３０３は、エラーを出力し以降の処理を中断する（ステップＳ７５）。ステップＳ６１〜Ｓ６３の判定結果が全て肯定的である場合、ステップＳ６４に進み、暗号化装置３０３は、公開情報に含まれる公開パラメータqを用いて、‘0≦u＜q’なる乱数uを生成する。そして、暗号化装置３０３は、圧縮公開鍵（g~,e,f,h）と生成元gとを伸長写像により射影表現で伸長する（ステップＳ６５）。次いで、暗号化装置３０３は、以下の式１２〜１３により射影表現でべき乗を計算して、c1,c2を求める（ステップＳ６６）。
【００８２】
c1=g^u・・・(式１２)
c2=（g~）^u・・・(式１３)
【００８３】
次いで、暗号化装置３０３は、c1,c2を圧縮写像によりアフィン表現に圧縮する（ステップＳ６７）。その後、暗号化装置３０３は、平文msgを伸長写像により射影表現に伸長する（ステップＳ６８）。そして、暗号化装置３０３は、以下の式１４により射影表現による演算でべき乗を計算することにより、平文マスクを行い、ｃ3を求める（ステップＳ６９）。
【００８４】
c3=msg*h^u・・・(式１４)
【００８５】
次いで、暗号化装置３０３は、c3を圧縮写像により圧縮する（ステップＳ７０）。そして、暗号化装置３０３は、ハッシュ計算により(c1,c2,c3)からハッシュ値を求め、これをvとする（ステップＳ７１）。次いで、暗号化装置３０３は、以下の式１５によりべき乗を計算して、c4を求める（ステップＳ７２）。
【００８６】
c4= e^(u)*f^（u*v）・・・(式１５)
【００８７】
次いで、暗号化装置３０３は、c4を圧縮写像により圧縮する（ステップＳ７３）。そして、暗号化装置３０３は、(c1,c2,c3,c4)を圧縮暗号文として出力する（ステップＳ７４）。そして、この圧縮暗号文を送信装置３００´は受信装置４００´に送信する。
【００８８】
＜復号処理＞
次に、本実施の形態にかかる受信装置４００´が行う復号処理の手順について図１４を用いて説明する。尚、受信装置４００´の有する復号装置４０３は、上述した鍵生成装置２００が生成した秘密鍵（x1,x2,y1,y2,z1,z2）を予め取得しているものとする。復号装置４０３は、圧縮暗号文(c1,c2,c3,c4)の各要素が、F_{p^m}×F_{p^m}^*の元であるか検査する。具体的には、復号装置４０３は、ci(i=1,2,3,4)のベクトル表現による各ベクトル成分について、1項目からm項目までと‘m+1’項目から2m項目までとに分割する（ステップＳ８０）。次いで、復号装置４０３は、上述の条件(D5)〜(F5)を全て満たすか否かを判定する（ステップＳ８１〜Ｓ８３）。
【００８９】
ステップＳ８１〜Ｓ８３の判定結果が全て肯定的である場合、ステップＳ８４に進み、復号装置４０３は、次いで、ハッシュ計算により(c1,c2,c3)からハッシュ値を求め、これをvとする。そして、復号装置４０３は、(c1,c2,c3)を伸長写像により伸長する（ステップＳ８５）。次いで、復号装置４０３は、式１６により射影表現による演算でべき乗を計算することにより、検査式に用いるcを求める（ステップＳ８６）。
【００９０】
c=c1^（x1+y1*v）*c2^（x2+y2*v）・・・(式１６)
【００９１】
次いで、復号装置４０３は、cを圧縮写像によりアフィン表現に圧縮する（ステップＳ８７）。その後、復号装置４０３は、検査式‘c=c4’ が成立するか否かを判定する（ステップＳ８８）。この判定は、例えば、c及びc4のベクトル表現における各ベクトル成分の値が一致するか否かを判定することにより行うことができる。そして、当該判定結果が肯定的である場合、復号装置４０３は、式１７により射影表現による演算でべき乗を計算して、bを求める（ステップＳ８９）。
【００９２】
b= c1^z1*c2^z2・・・(式１７)
【００９３】
次いで、復号装置４０３は、式１８により平文msgを計算する（ステップＳ９０）。
【００９４】
msg=c3*b^（-1）・・・(式１８)
【００９５】
その後、復号装置４０３は、平文msgを圧縮写像によりアフィン表現に圧縮して（ステップＳ９１）、これを出力する。尚、ステップＳ８８の判定結果が否定的である場合、復号装置４０３は、rejectを出力し、以降の処理を中断する（ステップＳ９２）。また、ステップＳ８１〜Ｓ８３の判定結果が否定的である場合、復号装置４０３は、invalidを出力し、以降の処理を中断する（ステップＳ９３）。但し、いずれの場合であっても、復号装置４０３は、なにも出力せずに処理を終了するようにしても良い。
【００９６】
以上のような構成によれば、F_{p^(6*m)}上のトーラスについて、その位数が合成数であって、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合であっても、入力が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【００９７】
[第６の実施の形態]
次に、暗号化装置、復号装置、暗号通信システム、方法及びプログラムの第６の実施の形態について説明する。なお、上述の第１の実施の形態乃至上述の第６の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００９８】
（１）構成
本実施の形態においては、F_{p^(6*m)}上のトーラスの位数は素数qで、平文をアフィン表現で表し、暗号文の計算を射影表現で行い、その結果をアフィン表現で圧縮したり伸長したりする。ここでは、暗号が定義される群は、6次拡大体上の素数位数トーラス自体となる。本実施の形態における鍵生成装置２００の構成は上述の第５の実施の形態と同様である。
【００９９】
本実施の形態にかかる送信装置３００´の有する暗号化装置３０３´の構成が、上述の第５の実施の形態にかかる暗号化装置３０３の構成と異なる点は以下の点である。上述の暗号化装置３０３は、平文が、F_{p^m}×F_{p^m}^*の元であるか否かを検査する際に、上述の条件(A5),(B5)のみを満たすか否かの判定を行い、条件(C5) 満たすか否かの判定を行わない。当該検査結果が肯定的である場合、入力された平文msgは、アフィン表現 F_{p^m}×F_{p^m}^*で表現された、6次拡大体上の素数位数代数的トーラス上の元である。この場合、暗号化装置３０３は、上述の第５の実施の形態と同様にして、圧縮暗号文(c1,c2,c3,c4)を生成する。以降は、上述の第５の実施の形態と同様である。
【０１００】
また、本実施の形態にかかる受信装置４００´の有する復号装置４０３´の構成が、上述の第５の実施の形態にかかる復号装置４０３の構成と異なる点は以下の点である。上述の復号装置４０３は、圧縮暗号文が、暗号が定義されている群上の元であるか否かを検査する際に、上述の条件(D5),(E5)のみ満たすか否かの判定を行い、条件(F5)を満たすか否かの判定を行わない。当該検査結果が肯定的である場合、受信された圧縮暗号文(c1, c2, c3, c4)は、アフィン表現 F_{p^m}×F_{p^m}^*で表現される暗号文であって、6次拡大体上の素数位数代数的トーラス上の元である。この場合、復号装置４０３は、上述の第５の実施の形態と同様にして、暗号化された平文を、秘密鍵を用いて復号する。
【０１０１】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる送信装置３００´が行う暗号化処理の手順について図１５を用いて説明する。ステップＳ６０〜Ｓ６２は上述の第５の実施の形態と同様である。そして、ステップＳ６２の判定結果肯定的である場合、暗号化装置３０３´は、ステップＳ６３を行わずに、ステップＳ６４以降の処理を行う。
【０１０２】
＜復号処理＞
次に、本実施の形態にかかる受信装置４００´が行う復号処理の手順について図１６を用いて説明する。ステップＳ８０〜Ｓ８２は上述の第５の実施の形態と同様である。そして、ステップＳ８２の判定結果肯定的である場合、復号装置４０３´は、ステップＳ８３を行わずに、ステップＳ８４以降の処理を行う。
【０１０３】
以上のような構成によれば、F_{p^(6*m)}上のトーラスについて、平文をアフィン表現で表し、暗号文の計算を射影表現により行う場合、F_{p^(6*m)}上のトラースの位数が素数であれば、これが合成数である場合に比べて、処理負担を軽減することができる。入力が正しい群の元であるか否かの各検査において、上述した条件(C5)や条件(F5)を満たすか否かの判定を必要としないからである。
【０１０４】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【０１０５】
＜変形例１＞
上述した各実施の形態において、送信装置３００で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。受信装置４００で実行される各種プログラムについても同様である。
【０１０６】
また、上述した第１の実施の形態乃至第３の実施の形態において、暗号化装置３０１及び圧縮装置３０２は、送信装置３００の有するＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現されるものとしたが、これに限らず、ハードウェアにより構成させるようにしても良い。復号装置４０１及び伸長装置４０２についても同様である。また、第５の実施の形態又は第６の実施の形態における暗号化装置３０３及び復号装置４０３についても同様である。
【０１０７】
＜変形例２＞
上述の第１の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを拡大体表現による演算で行うようにしたが、これらを射影表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(A1)〜(B1´)の全てを満たすか否かを判定することにより行う。(A1)は上述の第１の実施の形態と同様である。
【０１０８】
(A1) {0,…,p-1}^(6*m)に含まれる
(B1´) 射影表現の演算でmsg^(q) = 1を満たす
【０１０９】
当該検査結果が肯定的である場合、暗号化装置３０１は、射影表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。
【０１１０】
また、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、圧縮暗号文の各要素ciが以下の条件(C1)〜(D1´)を全て満たすか否かを判定することにより行う。条件(C1)は上述の第１の実施の形態と同様である。
【０１１１】
(C1) F_{p^m}×F_{p^m}^* に含まれる
(D1´) 拡大体表現による演算で、ci^(q) = 1 が成立する
【０１１２】
当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長 した暗号文(c1, c2, c3, c4)を得る。
【０１１３】
以上のように、平文を拡大体表現で表し、暗号文の計算を射影表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。特に、条件(D1’)の検証は射影表現を拡大体表現へ写像する前に実行できるため、(D1)の検証よりも効率的に不正な暗号文を検出できる。
【０１１４】
＜変形例３＞
上述の第２の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを拡大体表現で行うようにしたが、これを射影表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(B2´)を満たすか否かを判定することにより行う。
【０１１５】
（B2´）射影表現による演算で msg^｛p^(2*m)-p^(m)+1｝=1を満たす
【０１１６】
当該検査結果が肯定的である場合、暗号化装置３０１は、射影表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、上述した第１の実施の形態と同様にして、この暗号文を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を生成するが、この圧縮写像を、アフィン表現 F_{p^m}×F_{p^m}＾*の射影表現による演算により行う。また、伸長装置４０２が行う検査は上述の第２の実施の形態と同様である。
【０１１７】
以上のように、平文を拡大体表現現で表し、暗号文の計算を射影表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１１８】
＜変形例４＞
上述の第３の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを射影表現で行うようにしたが、これを拡大体表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、平文msgが、以下の条件(A3)〜(B3´)の全てを満たすか否かを判定することにより行う。条件(A3)は上述の第３の実施の形態と同様である。
【０１１９】
(A3) F_{p^m}×F_{p^m}^* に含まれる
(B3´) 拡大体表現による演算で msg^(q) = 1 が成立する
【０１２０】
当該検査結果が肯定的である場合、暗号化装置３０１は、拡大体表現上で乗算を行って、各要素c1,c2,c3,c4を求める。また、圧縮装置３０２は、各要素c1,c2,c3,c4を圧縮写像により圧縮して圧縮暗号文(c1, c2, c3, c4)を出力する。
【０１２１】
また、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、圧縮暗号文の各要素ciが以下の条件(C3)〜(D3´)を全て満たすか否かを判定することにより行う。条件(C3)は上述の第３の実施の形態と同様である。
【０１２２】
(C3) F_{p^m}×F_{p^m}＾* に含まれる
(D 3´) 拡大体表現による演算で、 ci^{q} = 1 が成立する
【０１２３】
当該検査結果が肯定的である場合、伸長装置４０２は、圧縮暗号文の各要素を伸長写像によりアフィン表現から伸長 した暗号文(c1, c2, c3, c4)を得る。
【０１２４】
以上のように、平文をアフィン表現で表し、暗号文の計算を拡大対表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１２５】
＜変形例５＞
上述の第４の実施の形態においては、暗号化装置３０１が行う演算と復号装置４０１が行う復号とを射影表現で行うようにしたが、これを拡大体表現で行うようにしても良い。この場合、暗号化装置３０１は、入力された平文msgが正しい群の元であるか否かを検査として、上述の条件(A3)を満たすか否かを判定すれば良い。一方、伸長装置４０２は、圧縮暗号文(c1, c2, c3, c4)の各要素が正しい群の元であるか否かを検査として、上述の条件(C3)を満たすか否かを判定すれば良い。
【０１２６】
以上のように、平文をアフィン表現で表し、暗号文の計算を拡大対表現により行う場合であっても、入力である平文や圧縮暗号文が正しい群の元であるか否かの各検査において、冗長な処理を省くことができる。
【０１２７】
＜変形例６＞
上述の第１の実施の形態あるいは上述の変形例４において、復号装置４０１の伸長装置４０２は圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長したが、条件(D1)あるいは条件(D3’)の検査の際に得る拡大体表現を用いても良い。
【０１２８】
＜変形例７＞
上述の第３の実施の形態あるいは上述の変形例２において、復号装置４０１の伸長装置４０２は圧縮暗号文の各要素を伸長写像によりアフィン表現から拡大体表現に伸長したが、条件(D1’)の検査の際に得る射影表現から拡大体表現に伸長しても良い。
【０１２９】
＜変形例８＞
上述の第３の実施の形態において、暗号化装置３０１は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めるが、条件(B3)の検査の際に用いる射影表現の平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めても良い。
【０１３０】
＜変形例９＞
上述の変形例２において、暗号化装置３０１は、拡大体表現で表現された平文msgより射影表現による演算によって射影表現の要素ciの組で表現される暗号文を求めるが、条件(B1’)の検査の際に用いる射影表現の平文msgより射影表現による演算によって射影表の現要素ciの組で表現される暗号文を求めても良い。
【０１３１】
＜変形例１０＞
上述の変形例４において、暗号化装置３０１は、アフィン表現 F_{p^m}×F_{p^m}＾*で表現された平文msgより拡大体表現による演算によって拡大体表現の要素ciの組で表現される暗号文を求めるが、条件(B3’)の検査の際に用いる拡大体表現の平文msgより拡大体表現による演算によって拡大体表現の要素ciの組で表現される暗号文を求めても良い。
【図面の簡単な説明】
【０１３２】
【図１】公開鍵暗号スキームの構成を例示する図である。
【図２】トーラス圧縮による公開鍵暗号スキームの構成を例示する図である。
【図３】Cramer-Shoup暗号における処理を概念的に示す図である。
【図４】第１の実施の形態にかかる鍵生成装置２００の構成を概念的に示す図である。
【図５】同実施の形態にかかるトーラス圧縮Cramer-Shoup暗号における暗号化装置３０１と圧縮装置３０２とが行う処理を概念的に示す図である。
【図６】同実施の形態にかかるトーラス圧縮Cramer-Shoup暗号における復号装置４０１と伸長装置４０２とが行う処理を概念的に示す図である。
【図７】同実施の形態にかかる送信装置３００が平文を暗号化して圧縮する処理の手順を示すフローチャートである。
【図８】同実施の形態にかかる受信装置４００が、送信装置３００から送信された圧縮暗号文を伸長して復号する処理の手順を示すフローチャートである。
【図９】暗号化処理及び圧縮処理を単純に組み合わせた場合に、入力が正しい群の元であるか否かを検査する処理を模式的に示す図である。
【図１０】伸長処理及び復号処理を単純に組み合わせた場合に、入力が正しい群の元であるか否かを検査する処理を模式的に示す図である。
【図１１】第５の実施の形態にかかる送信装置３００´及び受信装置４００´の構成を例示する図である。
【図１２】同実施の形態にかかる鍵生成装置２００が公開鍵及び秘密鍵を生成する処理の手順を示すフローチャートである。
【図１３】同実施の形態にかかる送信装置３００´が行う暗号化処理の手順を示すフローチャートである。
【図１４】同実施の形態にかかる受信装置４００´が行う復号処理の手順を示すフローチャートである。
【図１５】第６の実施の形態にかかる送信装置３００´が行う暗号化処理の手順を示すフローチャートである。
【図１６】同実施の形態にかかる受信装置４００´が行う復号処理の手順を示すフローチャートである。
【符号の説明】
【０１３３】
１００ パラメータ生成装置
２００ 鍵生成装置
３００ 送信装置
３０１ 暗号化装置
３０２ 圧縮装置
３０３ 暗号化装置
４００ 受信装置
４０１ 復号装置
４０２ 伸長装置
４０３ 復号装置
【特許請求の範囲】
【請求項１】
復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置であって、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする復号装置。
【請求項２】
前記代数的トーラスの位数は、素数であり、
前記伸長手段は、前記判定手段の判定結果が肯定的である場合、アフィン空間F_{p^m}×F_{p^m}＾*上の要素である前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、前記ベクトル成分を射影表現に写像し、射影表現による演算で
c^(q) =1
を満たすか否かを判定することにより、位数qの部分群である素数位数部分群Gの元であるか否かを判定する部分群上元判定手段とを有し、
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記ベクトル成分を、伸長写像により前記代数的トーラス上の元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、前記ベクトル成分を拡大体表現に写像し、拡大体表現による演算で
c^(q) =1
を満たすか否かを判定することにより、位数qの部分群である素数位数部分群Gの元であるか否かを判定する部分群上元判定手段とを有し、
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記ベクトル成分を、伸長写像により前記代数的トーラス上の元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項５】
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から写像して得た射影表現を用いて、前記ベクトル成分を前記代数的トーラス上の元に写像する
ことを特徴とする請求項３に記載の復号装置。
【請求項６】
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から写像する際に得た表現を用いて、前記ベクトル成分を前記代数的トーラス上の元に写像する
ことを特徴とする請求項４に記載の復号装置。
【請求項７】
前記復号手段は、アフィン表現で表現された前記平文を、前記秘密鍵を用いて復号する
ことを特徴とする請求項１に記載の復号装置。
【請求項８】
（拡大体上 復号）
前記復号手段は、拡大体表現で表現された前記平文を、前記秘密鍵を用いて復号する
ことを特徴とする請求項１に記載の復号装置。
【請求項９】
F_{p^m}の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_｛p＾m｝^*(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置であって、
暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得手段と、
前記平文msgに含まれるベクトル成分が、アフィン表現F_{p^m}×F_｛p＾m｝^*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}× F_｛p^m｝^*上の要素の組で表現される暗号文cを求める暗号化手段を備える
ことを特徴とする暗号化装置。
【請求項１０】
前記代数的トーラスの位数は、素数であり、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１１】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、アフィン表現を射影表現に写像し、前記ベクトル成分を射影表現に写像し、射影表現による演算で
msg^(q) = 1
を満たすか否か判定することにより、位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１２】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、アフィン表現を拡大体表現に写像し、前記ベクトル成分を拡大体表現に写像し、拡大体表現による演算で
msg^(q) = 1
を満たすか否か判定することにより、位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１３】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から射影表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項１１に記載の暗号化装置。
【請求項１４】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から拡大体表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項１２に記載の暗号化装置。
【請求項１５】
前記取得手段は、前記平文msgと、前記代数的トーラス上で暗号が定義される群Gの位数qと、前記群Gの生成元gと、前記群Gの少なくとも１つの元とを含む公開鍵と取得し、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、乱数と、前記平文msgと、前記生成元g及び前記少なくとも１つの元とを用いた計算を行うことにより、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９乃至１４のいずれか一項に記載の暗号化装置。
【請求項１６】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{{0,・・・,p-1}^(6*m)}(p:素数、m:自然数)で表現された平文msgを暗号化する暗号化装置であって、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現F_{p^m} ×F_{p^m}^*に写像する圧縮手段とを備える
ことを特徴とする暗号化装置。
【請求項１７】
前記代数的トーラスの位数は、素数であり、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項１８】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かを判定することにより、前記6次拡大体上の元であるか否かを判定する拡大体上元判定手段と、
前記拡大体上元判定手段の判定結果が肯定的である場合、‘p^(2*m)-p^(m)+1’を割り切るようなqに対して、F_{p^m}の6次拡大体上の演算で
msg^(q) = 1
を満たすか否かを判定することにより、前記平文msgが、代数的トーラス上の位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項１９】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かを判定することにより、前記6次拡大体上の元であるか否かを判定する拡大体上元判定手段と、
前記拡大体上元判定手段の判定結果が肯定的である場合、‘p^(2*m)-p^(m)+1’を割り切るような素数qに対して、射影表現による演算で
msg^(q) = 1
を満たすか否かを判定することにより、前記平文msgが、代数的トーラス上の位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項２０】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から射影表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１９に記載の暗号化装置。
【請求項２１】
前記取得手段は、前記平文msgと、前記代数的トーラス上で暗号が定義される群Gの位数qと、前記群Gの生成元gと、前記群Gの少なくとも１つの元とを含む公開鍵と取得し、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、乱数と、前記平文msgと、前記生成元g及び前記少なくとも１つの元とを用いた計算を行うことにより、前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６乃至２０のいずれか一項に記載の暗号化装置。
【請求項２２】
F_{p^m}の6次拡大体(p：素数、m：自然数)上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*、(^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、
前記暗号化装置は、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、
前記復号装置は、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする暗号通信システム。
【請求項２３】
F_{p^m}の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数、^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、
前記暗号化装置は、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、
前記復号装置は、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする暗号通信システム。
【請求項２４】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*(p:素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、
暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得ステップと、
前記平文msgに含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、
前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める暗号化ステップとを含む
ことを特徴とする暗号化方法。
【請求項２５】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、
暗号化の対象である平文msgと、公開鍵とを取得する取得ステップと、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定ステップと、
前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化ステップと、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮ステップとを含む
ことを特徴とする暗号化方法。
【請求項２６】
復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置で実行される復号方法であって、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得ステップと、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長ステップと、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号ステップとを含む
ことを特徴とする復号方法。
【請求項２７】
請求項２４乃至２６のいずれか一項に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１】
復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置であって、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする復号装置。
【請求項２】
前記代数的トーラスの位数は、素数であり、
前記伸長手段は、前記判定手段の判定結果が肯定的である場合、アフィン空間F_{p^m}×F_{p^m}＾*上の要素である前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、前記ベクトル成分を射影表現に写像し、射影表現による演算で
c^(q) =1
を満たすか否かを判定することにより、位数qの部分群である素数位数部分群Gの元であるか否かを判定する部分群上元判定手段とを有し、
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記ベクトル成分を、伸長写像により前記代数的トーラス上の元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項４】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、前記ベクトル成分を拡大体表現に写像し、拡大体表現による演算で
c^(q) =1
を満たすか否かを判定することにより、位数qの部分群である素数位数部分群Gの元であるか否かを判定する部分群上元判定手段とを有し、
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記ベクトル成分を、伸長写像により前記代数的トーラス上の元に写像する
ことを特徴とする請求項１に記載の復号装置。
【請求項５】
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から写像して得た射影表現を用いて、前記ベクトル成分を前記代数的トーラス上の元に写像する
ことを特徴とする請求項３に記載の復号装置。
【請求項６】
前記伸長手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から写像する際に得た表現を用いて、前記ベクトル成分を前記代数的トーラス上の元に写像する
ことを特徴とする請求項４に記載の復号装置。
【請求項７】
前記復号手段は、アフィン表現で表現された前記平文を、前記秘密鍵を用いて復号する
ことを特徴とする請求項１に記載の復号装置。
【請求項８】
（拡大体上 復号）
前記復号手段は、拡大体表現で表現された前記平文を、前記秘密鍵を用いて復号する
ことを特徴とする請求項１に記載の復号装置。
【請求項９】
F_{p^m}の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_｛p＾m｝^*(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置であって、
暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得手段と、
前記平文msgに含まれるベクトル成分が、アフィン表現F_{p^m}×F_｛p＾m｝^*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}× F_｛p^m｝^*上の要素の組で表現される暗号文cを求める暗号化手段を備える
ことを特徴とする暗号化装置。
【請求項１０】
前記代数的トーラスの位数は、素数であり、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１１】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、アフィン表現を射影表現に写像し、前記ベクトル成分を射影表現に写像し、射影表現による演算で
msg^(q) = 1
を満たすか否か判定することにより、位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１２】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記ベクトル成分が、アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定するアフィン表現判定手段と、
前記アフィン表現判定手段の判定結果が肯定的である場合、アフィン表現を拡大体表現に写像し、前記ベクトル成分を拡大体表現に写像し、拡大体表現による演算で
msg^(q) = 1
を満たすか否か判定することにより、位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９に記載の暗号化装置。
【請求項１３】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から射影表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項１１に記載の暗号化装置。
【請求項１４】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から拡大体表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項１２に記載の暗号化装置。
【請求項１５】
前記取得手段は、前記平文msgと、前記代数的トーラス上で暗号が定義される群Gの位数qと、前記群Gの生成元gと、前記群Gの少なくとも１つの元とを含む公開鍵と取得し、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、乱数と、前記平文msgと、前記生成元g及び前記少なくとも１つの元とを用いた計算を行うことにより、前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める
ことを特徴とする請求項９乃至１４のいずれか一項に記載の暗号化装置。
【請求項１６】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{{0,・・・,p-1}^(6*m)}(p:素数、m:自然数)で表現された平文msgを暗号化する暗号化装置であって、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現F_{p^m} ×F_{p^m}^*に写像する圧縮手段とを備える
ことを特徴とする暗号化装置。
【請求項１７】
前記代数的トーラスの位数は、素数であり、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項１８】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かを判定することにより、前記6次拡大体上の元であるか否かを判定する拡大体上元判定手段と、
前記拡大体上元判定手段の判定結果が肯定的である場合、‘p^(2*m)-p^(m)+1’を割り切るようなqに対して、F_{p^m}の6次拡大体上の演算で
msg^(q) = 1
を満たすか否かを判定することにより、前記平文msgが、代数的トーラス上の位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項１９】
前記代数的トーラスの位数は、合成数であり、
前記判定手段は、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かを判定することにより、前記6次拡大体上の元であるか否かを判定する拡大体上元判定手段と、
前記拡大体上元判定手段の判定結果が肯定的である場合、‘p^(2*m)-p^(m)+1’を割り切るような素数qに対して、射影表現による演算で
msg^(q) = 1
を満たすか否かを判定することにより、前記平文msgが、代数的トーラス上の位数qの部分群である素数位数部分群Gの元であるか否か判定する部分群上元判定手段とを有し、
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６に記載の暗号化装置。
【請求項２０】
前記暗号化手段は、前記部分群上元判定手段の判定結果が肯定的である場合、前記部分群上元判定手段が前記ベクトル成分から射影表現に写像する際に得た表現を用いて、前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１９に記載の暗号化装置。
【請求項２１】
前記取得手段は、前記平文msgと、前記代数的トーラス上で暗号が定義される群Gの位数qと、前記群Gの生成元gと、前記群Gの少なくとも１つの元とを含む公開鍵と取得し、
前記暗号化手段は、前記判定手段の判定結果が肯定的である場合、乱数と、前記平文msgと、前記生成元g及び前記少なくとも１つの元とを用いた計算を行うことにより、前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める
ことを特徴とする請求項１６乃至２０のいずれか一項に記載の暗号化装置。
【請求項２２】
F_{p^m}の6次拡大体(p：素数、m：自然数)上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*、(^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、
前記暗号化装置は、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
アフィン表現F_{p^m}×F_{p^m}＾*であるか否か判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、
前記復号装置は、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする暗号通信システム。
【請求項２３】
F_{p^m}の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数、^:べき乗）で表現された平文msgを暗号化する暗号化装置と、前記暗号化装置とネットワークを介して接続される復号装置であって復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*で表現された暗号文を復号する復号装置とを備える暗号通信システムであって、
前記暗号化装置は、
暗号化の対象である平文msgと、公開鍵とを取得する取得手段と、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化手段と、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮手段とを備え、
前記復号装置は、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得手段と、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定手段と、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長手段と、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号手段とを備える
ことを特徴とする暗号通信システム。
【請求項２４】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元でありアフィン表現F_{p^m}×F_{p^m}＾*(p:素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、
暗号化の対象であってベクトル形式により表現される平文msgと、公開鍵とを取得する取得ステップと、
前記平文msgに含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、
前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、アフィン空間F_{p^m}×F_{p^m}＾*上の要素の組で表現される暗号文cを求める暗号化ステップとを含む
ことを特徴とする暗号化方法。
【請求項２５】
F_{p^m}（^:べき乗）の6次拡大体上の代数的トーラス上の元であり拡大体表現{0,…,p-1}^(6*m)(p：素数、m：自然数)で表現された平文msgを暗号化する暗号化装置で実行される暗号化方法であって、
暗号化の対象である平文msgと、公開鍵とを取得する取得ステップと、
前記平文msgが、
{0,…,p-1}^(6*m)に含まれるか否かと、msg^(p^(2*m)-p^(m)+1)=1
を満たすか否かとを判定することにより、前記代数的トーラス上の元であるか否か判定する判定ステップと、
前記判定ステップの判定結果に基づいて、前記公開鍵を用いて前記平文msgを暗号化して、前記代数的トーラス上の元の組で表現される暗号文cを求める暗号化ステップと、
前記暗号文cの各元を、圧縮写像によりアフィン表現 F_{p^m}×F_{p^m}＾*に写像する圧縮ステップとを含む
ことを特徴とする暗号化方法。
【請求項２６】
復号の対象である平文を含んで暗号化され、アフィン表現F_{p^m}×F_{p^m}＾*(p：素数、m：自然数、^:べき乗）で表現された暗号文を復号する復号装置で実行される復号方法であって、
ベクトル形式により表現される暗号文と、公開鍵に対応する秘密鍵とを取得する取得ステップと、
前記暗号文に含まれるベクトル成分が、アフィン表現 F_{p^m}×F_{p^m}＾*であるか否か判定する判定ステップと、
前記判定手段の判定結果に基づいて、前記ベクトル成分を、伸長写像により前記代数的トーラス上の各元に写像する伸長ステップと、
前記代数的トーラス上の各元に写像された前記暗号文に含まれる前記平文を、前記秘密鍵を用いて復号する復号ステップとを含む
ことを特徴とする復号方法。
【請求項２７】
請求項２４乃至２６のいずれか一項に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１０−４９２１３（Ｐ２０１０−４９２１３Ａ）
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願番号】特願２００８−２１６０１５（Ｐ２００８−２１６０１５）
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]