パラメータ生成装置、暗号処理システム、方法およびプログラム
【課題】拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成すること。
【解決手段】パラメータ生成装置であって、有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、有限体ＦのサイズＷと、代数的トーラスＴの次数ｎと、拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部１３０と、群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部１４０と、代数的トーラスＴの次数ｎと有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部１５０と、乗算値ｎｍがｑで割り切れない場合に、暗号系が安全性ありと判定する安全性判定部１７０と、暗号系が安全性ありと判定された場合に、素数ｐと、素数ｑと、代数的トーラスＴの次数ｎと、拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部１６０とを備えた。
【解決手段】パラメータ生成装置であって、有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、有限体ＦのサイズＷと、代数的トーラスＴの次数ｎと、拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部１３０と、群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部１４０と、代数的トーラスＴの次数ｎと有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部１５０と、乗算値ｎｍがｑで割り切れない場合に、暗号系が安全性ありと判定する安全性判定部１７０と、暗号系が安全性ありと判定された場合に、素数ｐと、素数ｑと、代数的トーラスＴの次数ｎと、拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部１６０とを備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化する際のパラメータを生成するパラメータ生成装置、このパラメータ生成装置を備えた暗号処理システム、方法およびプログラムに関する。
【背景技術】
【０００２】
事前の鍵共有なしに安全な通信を実現する公開鍵暗号方式は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになってきた。
【０００３】
公開鍵暗号方式において現在の典型的な暗号系サイズは１０２４ビットであるが、解読が困難とされる暗号系サイズは年々大きくなっている。計算機の進歩とともに攻撃者の能力も上がっているためである。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となるので、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号方式における公開鍵のサイズや暗号文のサイズを圧縮する圧縮暗号技術が考案されている（例えば、非特許文献１参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。圧縮暗号の技術では、圧縮率（すなわち、圧縮前のビット数／圧縮後のビット数）を大きくする改良を行っており、集合の要素を小さいビット数の表現に変換する際に付加的な入力を用いる（例えば、非特許文献２参照）。小さいビット数の表現へ変換を行う写像を圧縮写像ρ、θといい、それぞれＲＳ圧縮写像、ＤＷ圧縮写像と呼ぶことにする。
【０００５】
暗号文を圧縮する場合には、ＲＳ圧縮写像ρでは、暗号文ｃを入力として次式に示す計算を行い、圧縮暗号文γを得る。
【０００６】
ρ（ｃ）＝γ
また、DW圧縮写像θでは、暗号文cが入力として与えられたときに適当な補助入力ａ１を用いて次式のような計算を行い、圧縮暗号文γと補助出力ａ１を得る。
θ（ｃ，ａ１）＝（γ，ａ２）
【０００７】
圧縮暗号文を圧縮前の元のビット数の表現に戻す場合には、それぞれρ、θの逆写像を（γ，ａ２）に施す。圧縮写像ρの逆写像をρ-1、圧縮写像θの逆写像をθ-1と記述し、それぞれＲＳ伸長写像、ＤＷ伸長写像と呼ぶ。ＲＳ伸長写像では、圧縮暗号文としてγが与えられたときに次式のような計算を行い、cを得る。
【０００８】
ρ-1（γ）＝ｃ
ＤＷ伸長写像では、圧縮暗号文としてγとａ２の組が与えられたときに次式の計算を行い、ｃとａ１を得る。
【０００９】
θ-1（γ，ａ２）＝（ｃ，ａ１）
代数的トーラスを用いた圧縮伸長は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用できる。
【００１０】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号が非特許文献３にて提案されている。Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は標準モデルでの安全性が証明されている方式であるが、公開鍵や暗号文の成分の数が多いという特徴がある。具体的には、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の暗号文は４つの成分（ｃ１，ｃ２，ｃ３，ｃ４）からなる。公開鍵も４つの成分（ｇ〜，ｅ，ｆ，ｈ）からなる。しかも、各成分は実際に暗号に用いられる群よりも大きな表現で表されるという問題がある。つまり、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は有限群Ｇ~の素数位数部分群Ｇ上で定義されているが、公開鍵や暗号文の成分はＧ~の表現で表されている。具体的には、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は素体の乗法群の素数位数部分群で定義されているが、公開鍵や暗号文の成分は素体の表現で表されている。
【００１１】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号やその他の公開鍵暗号において、有限群Ｇ~の部分群であって実際に暗号に用いられる群Ｇを代数的トーラスＴの部分群とすることにより、公開鍵や暗号文を有限群Ｇ~のサイズではなく代数的トーラスＴのサイズで表現する。ここで、代数的トーラスＴは有限群Ｇ~の部分群とする。
【００１２】
これまでに、素体上の代数的トーラスを用いたＥｌＧａｍａｌ暗号やＤＨ鍵交換が提案されている（非特許文献１、２参照）。Ｔが素体上のトーラスの場合、Ｔの部分群となるより小さなトーラスは存在しない。このとき、Ｇ~を拡大体Ｆの乗法群とする。部分群Ｇを選択する際には、Ｇの位数がＴの位数を割り切ることと、Ｇの位数がＦの拡大次数を割り切らないことを示していた。
【００１３】
【非特許文献１】Ｋ． Ｒｕｂｉｎ ａｎｄ Ａ． Ｓｉｌｖｅｒｂｅｒｇ， “Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＹＰＴＯ ２００３， ＬＮＣＳ ２７２９， ３４９−３６５， ２００３．
【非特許文献２】Ｍ． ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ． Ｗｏｏｄｒｕｆｆ， “Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＹＰＴＯ ２００４， ＬＮＣＳ ３１５２， １５７−１７８， ２００４．
【非特許文献３】Ｒ． Ｃｒａｍｅｒ ａｎｄ Ｖ． Ｓｈｏｕｐ， ”Ａ ｐｒａｃｔｉｃａｌ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍ ｐｒｏｖａｂｌｙ ｓｅｃｕｒｅ ａｇａｉｎｓｔ ａｄａｐｔｉｖｅ ｃｈｏｓｅｎ ｃｉｐｈｅｒｔｅｘｔ ａｔｔａｃｋ”， ＣＲＹＰＴＯ’９８， ＬＮＣＳ １４６２， ｐｐ．１３−２５， １９９８．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、拡大体上の代数的トーラスを用いた公開鍵暗号については、適切なパラメータ選択は知られていない。このため、素体上の代数的トーラスの場合のパラメータの選択方法を、拡大体上の代数的トーラスを用いた公開鍵暗号にそのまま適用することも考えられる。
【００１５】
しかしながら、この方法では、部分群Ｇが拡大体Ｆよりも小さな拡大体に包含される場合を排除できず、適切なパラメータを選択することができないという問題がある。
【００１６】
本発明は、上記に鑑みてなされたものであって、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができるパラメータ生成装置、暗号処理システム、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上述した課題を解決し、目的を達成するために、本発明にかかるパラメータ生成装置は、 トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、前記有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、を備えたことを特徴とする。
【００１８】
また、本発明にかかる暗号処理システムは、パラメータ生成装置と、鍵生成装置と、暗号化装置と、前記暗号化装置にネットワークで接続された復号化装置とを備えた暗号処理システムであって、前記パラメータ生成装置は、トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、前記代数的トーラスが定義され、安全性を定める有限体FのサイズＷと、前記群ＧのサイズＳの入力を受け付ける第１入力受付部と、前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する第１出力部と、を備え、前記鍵生成装置は、前記パラメータ（ｐ，ｑ，ｎ，ｍ）の入力を受け付ける第２入力受付部と、前記素数ｑを前記群Ｇの位数とし、前記素数ｐを前記有限体Ｆの標数とし、前記標数ｐ、前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせで公開鍵を計算する公開鍵計算部と、前記公開鍵を出力する第２出力部と、を備え、前記暗号化装置は、前記公開鍵と平文の入力を受け付ける第３入力受付部と、前記標数ｐおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記平文に対して前記公開鍵を用いた暗号化処理を施して、暗号文を求める暗号化処理部と、前記暗号文を前記復号化装置に送信する送信部と、を備え、前記復号化装置は、秘密鍵を記憶する記憶部と、前記暗号文を受信する受信部と、前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記暗号文に対して前記秘密鍵を用いた復号化処理を施して、前記平文を求める復号化処理部と、前記平文を出力する第４出力部と、を備えたことを特徴とする。
【００１９】
また、本発明は上記パラメータ生成装置で実行される方法およびコンピュータを上記パラメータ生成装置の各部として機能させるプログラムである。
【発明の効果】
【００２０】
本発明によれば、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２１】
以下に添付図面を参照して、この発明にかかるパラメータ生成装置、暗号処理システム、方法およびプログラムの最良な実施の形態を詳細に説明する。
【００２２】
（実施の形態１）
図１は、実施の形態１にかかる暗号処理システムのシステム構成を示すブロック図である。図１に示すように、実施の形態１にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【００２３】
パラメータ生成装置１００は、公開鍵暗号に関する公開情報としてのパラメータを生成する。パラメータとしては、群の要素やハッシュ関数などの情報や、暗号系が定義される群に関する情報として、位数や生成元の情報が含まれる。パラメータ生成装置１００の構成の詳細については後述する。
【００２４】
鍵生成装置２００は、パラメータ生成装置１００によって生成されたパラメータ（公開情報）を用いて、公開鍵と、公開鍵に対応する秘密鍵とを生成する。鍵生成装置２００の構成の詳細については後述する。
【００２５】
暗号化装置３００を有する送信装置３０には、鍵生成装置２００が生成した公開鍵と、暗号化の対象の平文データとが入力される。この平文データは、送信装置３０に予め記憶されたものであっても、送信装置３０が生成したものであっても、他の通信装置から受信したものであっても、記憶媒体から読み出したものであってもよい。
【００２６】
暗号化装置３００は、公開鍵を用いて平文データを暗号化して暗号文を生成し、生成した暗号文を受信装置４０に送信する。暗号化装置３００の構成の詳細については後述する。
【００２７】
復号装置４００を有する受信装置４０は、暗号文を受信すると、当該暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて暗号文を復号することにより、平文データを得る。復号化装置４００の構成の詳細については後述する。
【００２８】
なお、送信装置３０および受信装置４０は、例えば、図示しないインターネットなどのネットワークを介して相互に接続されたＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）等によって構成することができる。
【００２９】
なお、暗号化装置３００および復号装置４００は、暗号方式として、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いる。適用可能な暗号方式はこれに限られず、ＥｌＧａｍａｌ暗号などの有限体上の離散対数問題に基づく暗号方式であればあらゆる方式を適用できる。
【００３０】
また、本実施の形態では、暗号化装置３００および復号装置４００が、それぞれ送信装置３０および受信装置４０に含まれる構成を例に説明するが、装置構成はこれに限られるものではない。例えば、送信装置３０および受信装置４０以外の装置に暗号化装置３００および復号装置４００が含まれるように構成してもよい。また、暗号化装置３００および復号装置４００を同一の装置上に含むように構成してもよい。
【００３１】
本実施の形態のパラメータ生成装置１００について説明する。まず、本実施の形態におけるパラメータ生成の原理について説明する。
【００３２】
体とは四則演算が定義される数の集合であって、数の集合が有限の場合は有限体と呼ばれる。有限体に含まれる数の個数は素数であるか素数のべき乗であることが知られている。数の個数が素数である体を素体といい、数の個数が素数のべき乗である体を拡大体という。素体や拡大体の要素の個数を決めている素数を標数と呼び、べき乗を拡大次数と呼ぶ。
【００３３】
乗法群とは乗算と除算が定義される数の集合であって、有限体の要素から０を除くと乗法群となることが知られている。また、群の要素の個数を位数と呼ぶ。
【００３４】
Ｔを拡大体上の代数的トーラスとすると、Ｔの部分群となるより小さなトーラスが存在する。Ｇ~を拡大体Ｆの乗法群とすると、より小さなトーラスのうち拡大体Ｆの真部分体に包含されないトーラスｔが決まり、その次数は拡大体の次数となる。ｔはＴの部分群であるので、ｔの素数位数部分群上で暗号系を定義すると、公開鍵や暗号文はＴのサイズで表現される。圧縮伸長写像が構成できるＴの次数を定め、Ｔが定義される拡大体の次数と標数を安全性の要件から求める。
【００３５】
仮に、群Ｇが拡大体Ｆの真部分体Ｆ’に包含されるとき、Ｇの安全性を決定するのはＦ’のサイズである。つまり、そのサイズの差だけ安全性が低下する。Ｆ＝Ｆ’のとき（すなわち、Ｇがｔの部分群のとき）、元のＦの安全性を下げることなくＴの素数位数部分群Ｇ上で暗号系が定義される。
【００３６】
一方、Ｆ＞Ｆ’であってもＦ’を十分なサイズとすれば、代数的トーラスＴの最大の圧縮率（すなわち、Ｆのサイズ／Ｔのサイズ）よりは小さい圧縮率（Ｆ’のサイズ／Ｔのサイズ）で圧縮される。Ｆ＝Ｆ’とするパラメータ生成法の原理を以下に詳しく示す。
【００３７】
ここで、拡大体Ｆで定まる安全性を有する群Ｇ上で公開鍵暗号系を定義することを考える。ここで拡大体Ｆの乗法群をＧ~とし、その部分群である代数的トーラスをＴとする。Ｇは代数的トーラスＴの素数位数部分群とする。これらの集合として、以下の具体的な集合を考える。
【００３８】
１）拡大体Ｆは，標数ｐのｎｍ次拡大体とする。ここで、ｐは素数、ｎとｍは正整数、Ｆの位数（要素の数）はｐnmである。すなわち、（１）式で示される。
【００３９】
【数１】
【００４０】
２）拡大体Ｆの乗法群Ｇ~の位数は、ｐnm−１である。これを（２）式で示す。
【００４１】
【数２】
（２）式において、＃Ｘは群Ｘの位数を示す。
【００４２】
３）拡大体Ｆの乗法群Ｇ~の部分群である代数的トーラスＴは、標数ｐのｍ次拡大体上で定義された次数ｎの代数的トーラスとする。代数的トーラスＴの位数は、Φn（ｐm)である。ここで、Φn（ｘ)はｎ次の円分多項式とする。これを（３）式で示す。
【００４３】
【数３】
【００４４】
４）代数的トーラスＴの素数位数部分群Ｇの位数をｑは、安全性の観点からΦnm（ｐ）を割り切る素数としなければならない。これを（４）式に示す。
【００４５】
【数４】
【００４６】
代数的トーラスＴの素数位数部分群Ｇ、代数的トーラスＴ、拡大体Ｆの乗法群Ｇ~、拡大体Ｆは、公開情報となるパラメータ（ｐ，ｑ，ｍ，ｎ）によって一意に定まる。このとき、ｐ：拡大体Ｆの標数、ｑ：素数位数部分群Ｇの位数、ｍ：代数的トーラスＴが定義される拡大体Ｆｐmの次数、ｎ：代数的トーラスＴの次数である。代数的トーラスＴの素数位数部分群Ｇが包含される最小の拡大体をＦ’とすると、ｐのｍｏｄ ｑでの位数が拡大体Ｆ’の拡大次数である。拡大体Ｆ’の拡大次数はｑ｜（ｐx−１）を満たす最小のｘであり、この関係式が（５）式のように書き換えられることより明らかである。
【００４７】
【数５】
【００４８】
この結果は、文献「Ｌａｕｒａ Ｈｉｔｔ，”Ｏｎ ｔｈｅ ｍｉｎｉｍａｌ ｅｍｂｅｄｄｉｎｇ ｆｉｅｌｄ”，Ｐａｉｒｉｎｇ２００７，ＬＮＣＳ ４５７５，ｐｐ．２９４−３０１，２００７．」に記述された拡大体上楕円曲線の埋め込み次数に関する議論を再考することにより導かれる。ｐのｍｏｄ ｑでの位数をｏｒｄ（ｑ，ｐ）と記述すると、Ｆ’＝Ｆはｏｒｄ（ｑ，ｐ）＝ｎｍと同値である。さらに、ｏｒｄ（ｑ，ｐ）＝ｎｍは（６）式と同値である。
【００４９】
【数６】
【００５０】
ｐnm−１がｄ｜ｎｍなる円分多項式Φd（ｐ）の積で分解されることより、（６）式は（７）式と同値であることを導いた。
【００５１】
【数７】
【００５２】
ここで、拡大体Ｆ’の拡大次数がｎｍの約数になることは、ｘがｑ｜（ｐx−１）を満たす最小のｘであることより証明される。さらに、文献「Ｗ．Ｂｏｓｍａ，Ｊ．Ｈｕｔｔｏｎ ａｎｄ Ｅ．Ｒ．Ｖｅｒｈｅｕｌ，“Ｌｏｏｋｉｎｇ ｂｅｙｏｎｄ ＸＴＲ”，Ａｓｉａｃｒｙｐｔ’０２，ＬＮＣＳ ２５０１，ｐｐ．４６−６３，２００２．」に記述されているように、ｑがｎｍを割り切らない場合は、ｍｏｄ ｑの多項式（Ｘnm−１）が重根を持たないので、この場合は（６）、（７）式の「かつ」以降の条件は、自動的に成立する。また、拡大体上の代数的トーラスＴの位数について、円分多項式の性質を用いると、（８）式に表されることを発見した。ここで、ｍnはｍの因数であってｎの素因数の全ての積とし、ｍ~nはｍ／ｍnとする。
【００５３】
【数８】
【００５４】
本実施の形態のパラメータ生成装置１００では、この（８）式を用いて安全でかつ扱いやすいパラメータ（ｐ，ｑ，ｍ、ｎ）を効率よく生成する。
【００５５】
図２は、実施の形態１のパラメータ生成装置１００の機能的構成を示すブロック図である。図２に示すように、本実施の形態のパラメータ生成装置１００は、入力受付部１１０と、拡大次数決定部１２０と、第１素数探索部１３０と、第２素数探索部１４０と、検査部１５０と、安全性判定部１７０と、出力部１６０とを主に備えている。
【００５６】
入力受付部１１０は、代数的トーラスＴの次数ｎと、拡大体ＦのサイズＷと、代数的トーラスＴの素数位数部分群ＧのサイズＳの入力を受け付ける。拡大次数決定部１２０は、拡大体Ｆの拡大次数ｍを決定する。
【００５７】
トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号で用いられる群は、パラメータ（ｐ，ｑ，ｍ，ｎ）によって一意に定まる。このとき、ｐ：拡大体の標数、ｑ：素数位数部分群の位数、ｍ：代数的トーラスが定義される拡大体の次数、ｎ：代数的トーラスの次数である。本実施の形態では、（７）式に基づいて定められた（９−１）式で示す条件１および（９−２）式で示す条件２の両方を満たすパラメータ（ｐ，ｑ，ｍ，ｎ）を探索する。
【００５８】
【数９】
【００５９】
条件１は、素数位数部分群Ｇが代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるための条件である。この条件１を満たす素数ｐ、ｑは、それぞれ第１素数探索部１３０、第２素数探索部１４０で探索される。
【００６０】
すなわち、第１素数探索部１３０は、拡大体FのサイズＷと、代数的トーラスＴの次数ｎと、拡大次数ｍとに基づくビット数の素数ｐを探索する。具体的には、第１素数探索部１３０は、Ｗ／ｎｍビット以上の素数pを探索する。
【００６１】
第２素数探索部１４０は、円分多項式Φnm（ｐ）を割り切る素数であって、素数位数部分群ＧのサイズＳに基づいて定められるビット数である素数ｑを探索する。具体的には、第２素数探索部１４０は、円分多項式Φnm（ｐ）を割り切るSビット以上の素数qを探索する。
【００６２】
（９−２）式で示す条件２は、素数位数部分群Ｇが代数的トーラスＴの部分群のうち、唯一の部分群に含まれる条件である。拡大次数決定部１２０で決定されたｍ、第１探索部１３０で探索された素数ｐ、第２素数探索部１４０で探索された素数ｑが、条件２を満たすかどうかは、検査部１５０で検査される。すなわち、検査部１５０は、代数的トーラスＴの次数ｎと有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍが素数qで割り切れるか否かを検査する。そして、条件２を満たさない場合には、再度、ｍの決定、ｐ、ｑの探索を行うことになる。
【００６３】
ここで、条件２として（９−２）式を用いる代わりに、（１０）式を用いるように構成してもよい。
【００６４】
【数１０】
【００６５】
ここで、ｄはｎｍの約数である。この（１０）式の条件は、ｏｒｄ（ｑ，ｐ）＝ｎｍであることの必要十分条件となる。ただし、（１０）式では、全てのdについて検査を行う必要があるため、（９−２）式の条件を判断する手法の方が、検査時間を短縮することができるという利点がある。
【００６６】
安全性判定部１７０は、検査部１５０によって乗算値ｎｍが素数qで割り切れないと検査された場合に、暗号系が安全性ありと判定する。
【００６７】
出力部１６０は、ｎｍが素数ｑで割り切れない場合に、暗号系が安全性ありと判定し、素数ｐと、素数ｑと、拡大次数ｍと、代数的トーラスの次数ｎとからなるパラメータ（ｐ，ｑ，ｍ，ｎ）を出力する。
【００６８】
次に、鍵生成装置２００について説明する。図３は、実施の形態１の鍵生成装置２００の機能的構成を示すブロック図である。本実施の形態の鍵生成装置２００は、図３に示すように、鍵計算部２１０と、通信部２２０とを主に備えている。
【００６９】
鍵計算部２１０は、パラメータ生成装置１００で生成されたパラメータ（ｐ，ｑ，ｍ，ｎ）を入力して公開鍵や秘密鍵を生成する。鍵計算部２１０は、乱数生成部２１１と、演算部２１２とを備えている。
【００７０】
乱数生成部２１１は、素数位数部分群Ｇの位数qで範囲が限定される乱数を生成する。演算部２１２は、秘密鍵を生成する。また、演算部２１２は、素数位数部分群Ｇの生成元ｇを入力し、標数pおよび拡大次数mの拡大体またはその部分体上で、素数位数部分群Ｇの生成元ｇに対して、生成した乱数を用いてべき乗演算および乗算を行うことにより、その演算結果を公開鍵として求める。
【００７１】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における鍵生成処理では、べき乗も乗算も素体上でおこなっていたが、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における鍵生成処理では、べき乗と乗算は拡大体上で行う。標数ｐの拡大次数ｎｍの拡大体上の演算となるが、ｎは代数的トーラスの次数であり、ｍは代数的トーラスが定義される拡大体の拡大次数であることより、拡大体Ｆｐmの元ｎ個からなるベクトルの計算とする。圧縮伸長写像や代数的トーラス上の演算は拡大体Ｆｐm上の演算を用いるため、同じ演算処理を利用することができ、効率な演算を行うことができる。
【００７２】
なお、拡大体Ｆｐm上の乗算と加算は必ずしも逐次的に行う必要はなく、ベクトル表現の変換やｎ次拡大の法多項式や基底は、あらかじめ拡大体の表現を合意していれば必要ない。
【００７３】
通信部２２０は、生成した秘密鍵、公開鍵をネットワークを介して暗号化装置３００、復号化装置４００に送信する。
【００７４】
次に、暗号化装置３００について説明する。図４は、実施の形態１の暗号化装置３００の機能的構成を示すブロック図である。暗号化装置３００は、図４に示すように、暗号化処理部３１０と、圧縮処理部３２０と、公開鍵記憶部３４０と、通信部３３０とを備えている。
【００７５】
暗号化処理部３１０は、拡大体Ｆの標数ｐおよび拡大次数ｍの拡大体Ｆまたはその部分体上の演算の組み合わせにより、平文に対して公開鍵を用いた暗号化処理を施して、暗号文を求めるものである。
【００７６】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図５は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。図５で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ~，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００７７】
図４に示すように、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の暗号化の具体的な処理は、乱数乗のべき乗計算と乗算、ハッシュ関数の計算からなる。
【００７８】
暗号化処理部３１０では、（Ａ−１）〜（Ａ−４）式により平文データｍに対応する暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を計算する。ここで、（Ａ−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖを求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００７９】
図４に戻り、この手順を実行するため、暗号化処理部３１０は、乱数生成部３１１と、演算部３１２とを備えている。
【００８０】
乱数生成部３１１は、素数位数群Ｇの位数qで範囲が限定される乱数ｒを生成する。演算部３１２は、生成元ｇと公開鍵とを乱数で第１のべき乗演算し（Ａ−１）、第１のべき乗演算の結果と平文とを乗算し（Ａ−２）、乗算した結果と第１のべき乗演算の結果のハッシュ値を求め（Ａ−３）、ハッシュ値と乱数で公開鍵を第２のべき乗演算し、第１のべき乗演算の結果と第２のべき乗演算の結果とを、暗号文として求める（Ａ−４）。
【００８１】
圧縮処理部３２０は、暗号化処理部３１０で生成された暗号文を圧縮写像によりトーラス圧縮する。
【００８２】
トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における上記の暗号化処理と圧縮処理では、べき乗と乗算は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で行われる。
【００８３】
すなわち、暗号化処理と圧縮処理は、標数ｐの拡大次数ｎｍの拡大体上の演算となるが、ｎは代数的トーラスの次数であり、ｍは代数的トーラスが定義される拡大体の拡大次数であることより、拡大体Ｆｐmの元ｎ個からなるベクトルの計算とする。圧縮写像や代数的トーラス上の演算は拡大体Ｆｐm上の演算を用いるため、同じ演算処理を利用することができ、効率な演算を行うことができる。
【００８４】
なお、拡大体Ｆ上の乗算と加算は必ずしも逐次的に行う必要はなく、ベクトル表現の変換やｎ次拡大の法多項式や基底は、あらかじめ拡大体の表現を合意していれば必要ない。
【００８５】
通信部３３０は、鍵生成装置２００や復号化装置４００とのデータの送受信を行う。具体的には、通信部３３０は、鍵生成装置２００から公開鍵を受信する。また、通信部３３０は、復号化装置４００に、トーラス圧縮された暗号文を送信する。公開鍵記憶部３４０は、鍵生成装置２００から受信した公開鍵を保存しておく記憶媒体である。
【００８６】
次に、復号化装置４００について説明する。図６は、実施の形態１の復号化装置４００の機能的構成を示すブロック図である。復号化装置４００は、図６に示すように、伸長処理部４１０と、復号化処理部４２０と、圧縮処理部４５０と、秘密鍵記憶部４４０と、通信部４３０とを主に備えている。
【００８７】
通信部４３０は、鍵生成装置２００から秘密鍵を受信する。また、通信部４３０は、暗号化装置３００から圧縮された暗号文を受信する。秘密鍵記憶部４４０は、受信した秘密鍵を保存しておく記憶媒体である。
【００８８】
伸長処理部４１０は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、暗号化装置３００から受信した圧縮された暗号文を伸長写像を使って伸長する。
【００８９】
復号化処理部４２０は、暗号文を秘密鍵を用いて復号化し、平文を取得する。ここで、図５に戻り、復号化処理部４２０では、（Ｂ−１）〜（Ｂ−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）から正当な平文データであるか否かのチェックを行い、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ〜）は、ｃが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００９０】
このため、復号化処理部４２０は、第１判定部４２１と、第２判定部４２２と、演算部４２３とを備えている。
【００９１】
すなわち、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の復号の具体的な処理は、正しい群の元であるかの検査とハッシュ関数の計算、検査式のチェック（べき乗と乗算）、平文の計算（逆元と乗算）からなる。
【００９２】
第１判定部４２１は、暗号文が素数位数部分群Ｇの元であるか否かを検査し、素数位数部分群Ｇまたは拡大体Ｆの乗法群Ｇ~の元である場合には、暗号文は正当であると判定する（Ｂ−１、Ｂ−２）。
【００９３】
演算部４２３は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、暗号文の要素であるｃ１、ｃ２をべき乗演算および乗算して逆元を求め、暗号文の要素であるｃ３と乗算して平文ｍを求める（Ｂ−３，Ｂ−４）。
【００９４】
第２判定部４２２は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、ハッシュ関数Ｈを用いて暗号文のハッシュ値を求め（Ｂ−５）、ハッシュ値と秘密鍵とにより暗号文の要素であるｃ１、ｃ２をべき乗演算および乗算して、暗号文の要素であるｃ４と一致する場合に、暗号文は正当であると判定する（Ｂ−６）。
【００９５】
なお、（Ｂ−１），（Ｂ−２）式による正しい群の元であるかの検査を、伸長処理の前に実行するように構成してもよく、この場合には無駄な伸長写像の計算を省くことができる。また、素数位数の代数的トーラスを用いる場合には、圧縮された表現における検査は容易となり都合が良い。さらに、ハッシュ関数の計算についても、暗号化処理部４２０とその入力値を圧縮後の値とすることで合意されているならば、伸長処理の前に行っても良い。
【００９６】
圧縮処理部４５０は、復号化処理部４２０で算出された平文を、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上の演算によりトーラス圧縮する。
【００９７】
次に、以上のように構成された本実施の形態の暗号処理システムにおけるパラメータ生成から復号化までの処理について説明する。
【００９８】
まず、パラメータ生成装置１００におけるパラメータ生成処理について説明する。図７は、実施の形態１のパラメータ処理の手順を示すフローチャートである。
【００９９】
まず、入力受付部１１０は、代数的トーラスＴの次数ｎ、拡大体ＦのサイズＷ、素数位数部分群ＧのサイズＳの組の入力を受け付ける（ステップＳ１１）。
【０１００】
そして、拡大次数決定部１２０により、拡大体Ｆの拡大次数ｍを決定する（ステップＳ１２）。ここで、拡大次数ｍの決定について詳細に説明する。
【０１０１】
例えば、ｎ＝６、Ｗ＝２０４８、Ｓ＝２２４として考える。拡大体Ｆｐmを構成するための条件として、素体Ｆpのｍ次拡大の法多項式がＦp上で既約であること、ｍ次拡大体Ｆpmの３次拡大の法多項式がＦpm上で既約であること、３ｍ次拡大体Ｆp3mの２次拡大の法多項式がＦp3m上で既約であることである。
【０１０２】
例えば、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１のとき、これらの法多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である十分条件は次の４つの条件が同時に成立することである。
【０１０３】
１）ｍが奇数であること。
２）ｍは３で割り切れるかつｐは４ｍで割った余りが２ｍ＋１であること、または、ｍは３で割り切れないかつｐは１２ｍで割った余りが６ｍ＋１であること。
３）ｓ(floor(p/m)d)≠１，ｄ｜ｍ，ｄ≠ｍ
４）ｗ(floor(p/m)×(p^m-1)/(p-1))≠１
ここで、ｆｌｏｏｒ（ｘ）は床関数であり、ｘを越えない最大の整数を返す関数である。また、ｐ＾ｘは、ｐのｘ乗を示す。
【０１０４】
また、素数位数トーラスとなる条件として、トーラスＴ６（Ｆpm）の位数はΦ６（ｐm）であり、これが素数となる必要条件は次式が成り立つことである。
【０１０５】
５）ｍ＝２a×３b
従って、拡大次数決定部１２０は、上記１）〜５）までの条件を満たすように、拡大次数ｍを決定している。
【０１０６】
他の例では、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δのとき、これらの法多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である必要十分条件は次の５つの条件が同時に成立することである。
【０１０７】
１’）ｍの素因数で（ｐ−１）が割り切れること、かつ、（ｐm−１）が３で割り切れること、かつ、（ｐ3m−１）が２で割り切れること。
２’）ｍが４で割り切れるならば（ｐ−１）が４で割り切れること。
３’）ｓ(floor(p/P))≠１ ただし、Ｐは、ｍの素因数である。
４’）ｗ(floor(p＾ｍ/３))≠１
５’）δ(floor(p＾（３ｍ）/２))≠１
ここで、ｆｌｏｏｒ（ｘ）は床関数であり、ｘを越えない最大の整数を返す関数である。
【０１０８】
また、素数位数トーラスとなる条件として、トーラスＴ６（Ｆpm）の位数はΦ６（ｐm）であり、これが素数となる必要条件は次式が成り立つことである。
【０１０９】
６’）ｍ＝２a×３b
従って、拡大次数決定部１２０は、上記１’）〜６’）までの条件を満たすように、拡大次数ｍを決定している。
【０１１０】
次いで、第１素数探索部１３０が、Ｗ／ｎｍビット以上の素数ｐを探索する（ステップＳ１３）。
【０１１１】
例えば、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１の場合、素数ｐとして、２）の条件を満たす素数を探索する。ｍの候補が複数ある場合にはそれぞれについて実施する。上述の例では，ｍ＝２７，８１，２４３であるため，ｍが３で割り切れるので、素数ｐとして、４ｍで除算した余りが２ｍ＋１となるような素数を探索する。
【０１１２】
また、他の例では、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δの場合、素数ｐとして、１’）および２’）の条件を満たす素数を探索する。ｍの候補が複数ある場合にはそれぞれについて実施する。上述の例では，ｍ＝１８，２４，２７，３２，…であるため、素数ｐとして、ｍが２で割り切れる場合（ｐ−１）が２で割り切れ、ｍが３で割り切れる場合（ｐ−１）が３で割り切れ、ｍが４で割り切れる場合（ｐ−１）が４で割り切れ、かつ、（ｐm−１）が３で割り切れ、かつ、（ｐ3m−１）が２で割り切れるような素数を探索する。
【０１１３】
そして、素数ｐが探索されるまで（ステップＳ１４：Ｎｏ）、上記ステップＳ１２およびＳ１３の処理を繰り返す。
【０１１４】
素数ｐが探索された場合には（ステップＳ１４：Ｙｅｓ）、（９−１）式の条件を満たすべく、第２素数探索部１４０は、Φnm（ｐ）を割り切るＳビット以上の素数ｑを探索する（ステップＳ１５）。
【０１１５】
そして、素数ｑが探索されたら、（９−２）式で示す条件２を満たしているか判断するため、検査部１５０は、ｎｍが素数ｑで割り切れるか否かを判断する（ステップＳ１６）。ｎｍが素数ｑで割り切れる場合には（ステップＳ１６：Ｙｅｓ）、ステップＳ１５の素数ｑの探索を繰り返す。
【０１１６】
一方、ステップＳ１６で、ｎｍが素数ｑで割り切れない場合（ステップＳ１６：Ｎｏ）、安全性判定部１７０は暗号系が安全性ありと判定して、出力部１６０は、（９−２）式の条件２を満足する素数ｑが探索されたと判断して、パラメータ（ｐ，ｑ，ｍ，ｎ）を出力する（ステップＳ１７）。
【０１１７】
ここで、パラメータ生成処理の第１変形例（実施の形態１の変形例１）として、暗号系が定義される素数位数部分群Ｇとして素数位数トーラスＴそのものを用いる場合の処理がある。このような場合には、素数位数トーラスＴの位数が素数位数部分群Ｇの位数と等しくなるので、Φn（ｐm）＝ｑである。従って、この条件の下、条件１と条件２を満たすパラメータを探索する。
【０１１８】
図８は、実施の形態１の変形例１のパラメータ生成処理の手順を示すフローチャートである。図８に示すように、本変形例では、ステップＳ２６の素数ｑの探索において、Φn（ｐm）＝Φnm（ｐ）＝ｑを満たす素数ｑを探索している点が、図７の処理と異なり、他のステップＳ２１〜２４、Ｓ２６，Ｓ７の処理は、図７の処理と同様である。
【０１１９】
また、パラメータ生成処理の第２の変形例（実施の形態１の変形例２）として、（８）式に基づいた条件により素数ｑの探索を行うこともできる。図９は、実施の形態１の変形例２のパラメータ生成処理の手順を示すフローチャートである。本変形例では、代数的トーラスＴの位数について（８）式が成立するので、ｍ~n＝１の場合、Φn（ｐm）＝Φnm（ｐ）となる。このため、ステップＳ３２の拡大体Ｆの拡大次数ｍを決定する際に、ｍ~n＝１という制約を課し、この上で、ステップＳ３５の素数ｑの探索処理において、＝Φnm（ｐ）＝ｑとなる素数ｑを探索している。これにより、変形例２のステップＳ２５におけるΦn（ｐm）＝Φnm（ｐ）の検査を省略することができる。
【０１２０】
また、パラメータ生成処理の第３の変形例（実施の形態１の変形例３）として、次の処理がある。図１０は、実施の形態１の変形例３のパラメータ生成処理の手順を示すフローチャートである。（９−２）式に示す条件２が成立しない場合でも、全てのｄ｜ｎｍ，ｄ＜ｎｍについて（１０）式が成立すれば、パラメータを求めることができる。ここで、ｄはｎｍの約数である。
【０１２１】
このため、本変形例では、ステップＳ４６において、（９−２）式の条件２が成立しない場合、すなわち、ｎｍが素数ｑで割り切れる場合には（ステップＳ４６：Ｙｅｓ）、（１０）式の判断、すなわち、ｎｍの約数ｄについてΦd（ｐ）が割り切れるか否かを判断し（ステップＳ４７）、割り切れない場合には（ステップＳ４７：Ｎｏ）、条件２が成立しない場合でもパラメータ（ｐ、ｑ、ｍ、ｎ）を出力している。一方、割り切れる場合には（ステップＳ４７：Ｙｅｓ）、再度、素数ｑの探索を行う。
【０１２２】
他のステップＳ４１〜Ｓ４５，Ｓ４６，Ｓ４８の処理については、変形例２の処理と同様に行われる。なお、図１０では、ステップＳ４７の処理を変形例２（図９）の処理に組み込んだ例を示したが、これに限定されるものではなく、実施の形態１の図７の処理、変形例２の図８の処理に組み込むように構成してもよい。
【０１２３】
次に、鍵生成装置２００による鍵生成処理について説明する。図１１は、実施の形態１の鍵生成処理の手順を示すフローチャートである。
【０１２４】
まず、乱数生成部２１１は、パラメータ生成装置１００からパラメータ（ｐ、ｑ、ｍ、ｎ）を入力し（ステップＳ５１）、その中の素数位数部分群Ｇの位数ｑを用いて、０＜ｗ＜ｑとなる乱数ｗを生成する（ステップＳ５２）。また、乱数生成部２１１は、素数位数部分群Ｇの位数ｑを用いて、０≦ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２＜ｑとなる乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２を生成する（ステップＳ５３）。
【０１２５】
次に、演算部２１２が、素数位数部分群Ｇの生成元ｇを取得する（ステップＳ５４）。
【０１２６】
次に、演算部２１２は、次の（１１−１）〜（１１−４）式のべき乗計算を行う（ステップＳ５５）。
【０１２７】
【数１１−１】
【０１２８】
そして、出力部２２０は、その計算結果である（ｇ~，ｅ，ｆ，ｈ）を公開鍵として出力し（ステップＳ５６）、また、（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を秘密鍵として出力する（ステップＳ５７）。より具体的には、出力部２２０は、公開鍵を暗号化装置３００に送信し、秘密鍵を復号化装置４００に送信する。
【０１２９】
次に、暗号化装置３００による暗号化処理ついて説明する。図１２は、実施の形態１の暗号化処理の手順を示すフローチャートである。具体的には、図５に示す（Ａ−１）〜（Ａ−５）式に示す算出処理が行われる。
【０１３０】
まず、通信部３０３は、生成元ｇ、公開鍵ｇ~、ｅ、ｆ、ｈと、平文データｍとを入力する（ステップＳ６１）。次に、乱数生成部３１１は、乱数ｒを生成する（ステップＳ６２）。
【０１３１】
次に、演算部３１２、生成元ｇ、公開鍵のうちｇ~、ｈと、乱数ｒとを用いて、べき乗計算ｃ１＝ｇr、ｃ２＝ｇ〜r、ｂ＝ｈrを実行する（ステップＳ６３）。また、演算部３１２は、平文データｍと、算出したｂとを乗算し、ｃ３＝ｍｂを算出する（ステップＳ６４）。
【０１３２】
次に、圧縮処理部３２０は、ｃ１、ｃ２、ｃ３を、圧縮写像により圧縮する（ステップＳ６５）。
【０１３３】
次に、演算部３１２は、ハッシュ関数Ｈへの入力としてｃ１、ｃ２、ｃ３を用いてハッシュ値ｖ＝Ｈ（ｃ１、ｃ２、ｃ３）を算出する（ステップＳ６６）。そして、演算部３１２は、公開鍵のうちｅ、ｆと、乱数ｒと、算出されたハッシュ値ｖとを用いて、べき乗計算ｃ４＝ｅrｆrｖを実行する（ステップＳ６７）。
【０１３４】
次に、圧縮処理部３２０は、ｃ４を、圧縮写像を用いて圧縮する（ステップＳ６８）。最後に、通信部３３０は、圧縮後の（ｃ１、ｃ２、ｃ３、ｃ４）を圧縮された暗号文データ（圧縮暗号文）として出力し（ステップＳ６９）、復号化装置４００に送信する。
【０１３５】
次に、復号化装置４００による復号化処理について説明する。図１３は、実施の形態１の復号化処理の手順を示すフローチャートである。具体的には、図５の（Ｂ−１）〜（Ｂ−６）式の算出処理を行う。
【０１３６】
まず、通信部４３０は、復号の対象となる暗号文データ（圧縮暗号文）を受信することにより入力する（ステップＳ７１）。
【０１３７】
次に、第１判定部４２１は、暗号文データの成分（要素）である圧縮されたｃ１、ｃ２、ｃ３、ｃ４のそれぞれが正しい群の元であるか否か、すなわち、ｃ１、ｃ２、ｃ３、ｃ４それぞれが群Ｇの元となっているか否かを判断する（ステップＳ７２）。具体的には、暗号文の成分を要素とするベクトル表現（ｃ１，ｃ２，ｃ３，ｃ４）の各値が、０からｐ−１までの範囲に入っている場合に、暗号文ｃ１，ｃ２，ｃ３，ｃ４のそれぞれが正しい群の元であると判定することができる。
【０１３８】
暗号文データの成分が正しい群Ｇの元でないと判断された場合は（ステップＳ７２：ＮＯ）、復号処理を終了する。
【０１３９】
暗号文データの成分が正しい群Ｇの元であると判断された場合（ステップＳ７２：ＹＥＳ）、復号処理部４１０は、ハッシュ関数Ｈへの入力としてｃ１、ｃ２、ｃ３を用いてハッシュ値ｖ＝Ｈ（ｃ１、ｃ２、ｃ３）を算出する（ステップＳ７３）。
【０１４０】
次に、伸長処理部４１０は、圧縮された暗号文ｃ１、ｃ２、ｃ３を伸長写像を用いて伸長する（ステップＳ７４）。また、演算部４２３は、ハッシュ値ｖと、伸長後の暗号文ｃ１、ｃ２と、秘密鍵のうちｘ１、ｘ２、ｙ１、ｙ２とを用いて、べき乗計算ｃ＝ｃ１（ｘ１＋ｙ１ｖ）ｃ２（ｘ２＋ｙ２ｖ）を実行する（ステップＳ７５）。そして、演算部４２３は、べき乗計算により算出されたｃを圧縮する（ステップＳ７６）。また、伸長処理部４１０は、圧縮された暗号文ｃ４を伸長する。
【０１４１】
次に、第２判定部４２２は、ｃと入力された暗号文データの成分のうちｃ４とが一致するか否かを判断する（ステップＳ７７）。具体的には、暗号文のベクトル表現における各値が一致した場合に、ｃと入力された暗号文データの成分ｃ４とが一致すると判定することができる。
【０１４２】
そして、両者が一致しない場合は（ステップＳ７７：Ｎｏ）、復号処理を終了する。一方、両者が一致する場合は（ステップＳ７７：Ｙｅｓ）、演算部４２３は、ｃ１、ｃ２と、秘密鍵のうちｚ１、ｚ２とを用いて、べき乗計算ｂ＝ｃ１ｚ１ｃ２ｚ２を実行する（ステップＳ７８）。
【０１４３】
次に、演算部４２３は、ｃ３と、算出されたｂとを用いて、平文ｍ＝ｃ３ｂ−１を算出する（ステップＳ７９）。そして、圧縮処理部４５０によって平文ｍを圧縮し（ステップＳ８０）、圧縮された平文ｍを出力する（ステップＳ８１）。
【０１４４】
以上説明したように、本実施の形態によれば、パラメータ生成装置１００で、（９−１）式および（９−２）式を満たすように、パラメータ（ｐ、ｑ，ｍ、ｎ）を生成し、このパラメータを用いて、鍵生成、暗号化処理、復号化処理を行っているので、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができ、これにより、より安全性のある暗号化処理を実現することができる。
【０１４５】
ここで、鍵生成処理で生成し、復号化処理で使用する秘密鍵としては、上述した（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）に限定されるものではない。例えば、秘密鍵の個数を（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）よりも少なく構成してもよい。
【０１４６】
このような場合の鍵生成処理の変形例（実施の形態１の変形例４）として、鍵生成装置２００において生成する秘密鍵の個数が４個とする場合の処理がある。図１４は、実施の形態１の変形例４の鍵生成処理の手順を示すフローチャートである。この変形例では、実施の形態１の鍵生成処理（図１１）と同様に、パラメータ（ｐ，ｑ，ｍ，ｎ）の入力（ステップＳ５１）、乱数ｗの生成（ステップＳ５２）の後、乱数生成部２１１は、素数位数部分群Ｇの位数ｑを用いて、０≦ｘ，ｙ，ｚ＜ｑとなる乱数ｘ，ｙ，ｚを生成する（ステップＳ５３ｂ）。
【０１４７】
次に、演算部２１２は、次の（１１−５）〜（１１−８）式のべき乗計算を行う（ステップＳ５５ｂ）。
【０１４８】
【数１１−２】
【０１４９】
そして、出力部２２０は、その計算結果である（ｇ~，ｅ，ｆ，ｈ）を公開鍵として出力し（ステップＳ５６）、また、（ｗ，ｘ，ｙ，ｚ）を秘密鍵として出力する（ステップＳ５７ｂ）。
【０１５０】
また、復号化処理の変形例（実施の形態１の変形例５）として、上記変形例４の鍵生成処理により生成された４個の秘密鍵を用いる場合の処理がある。図１５は、実施の形態１の変形例５の復号化処理の手順を示すフローチャートである。
【０１５１】
圧縮暗号文の入力から圧縮暗号文ｃ１，ｃ２，ｃ３の伸長までの処理（ステップＳ７１〜Ｓ７４）については、図１３で示した実施の形態１の復号化処理と同様に行われる。
【０１５２】
本変形例では、ステップＳ７４ｂにおいて圧縮暗号文ｃ１，ｃ３を伸長したら、演算部４２３は、ハッシュ値ｖと、伸長後の暗号文ｃ１と、秘密鍵のうちｗ、ｘ、ｙとを用いて、べき乗計算ｔ１＝ｃ１ｗ，ｔ２＝ｃ１（ｘ＋ｙｖ）を実行する（ステップＳ７５ｂ）。そして、演算部４２３は、算出されたｔ１，ｔ２を圧縮する（ステップＳ７６ｂ）。
【０１５３】
次に、第２判定部４２２は、ｔ１と、入力された暗号文データの成分のうちｃ２とが一致するか否か、および、ｔ２と、入力された暗号文データの成分のうちｃ４とが一致するか否かを判断する（ステップＳ７７ｂ）。
【０１５４】
そして、ｔ１とｃ２が一致しない、あるいはｔ２とｃ４とが一致しない場合には（ステップＳ７７ｂ：Ｎｏ）、復号処理を終了する。一方、ｔ１とｃ２が一致し、かつｔ２とｃ４とが一致する場合には（ステップＳ７７ｂ：Ｙｅｓ）、演算部４２３は、ｃ１と、秘密鍵のうちのｚとを用いて、べき乗計算ｂ＝ｃ１ｚを実行する（ステップＳ７８ｂ）。
【０１５５】
この後の平文ｍの圧縮（ステップＳ８０）、平文ｍの出力（ステップＳ８１）は、図１３で示した実施の形態１の復号化処理と同様に行われる。
【０１５６】
なお、本変形例では、秘密鍵の個数が４個の場合を例にあげて説明したが、秘密鍵の個数はこれに限定されるものではない。
【０１５７】
（実施の形態２）
実施の形態２の暗号処理システムは、鍵生成装置において生成した公開鍵を圧縮するものである。図１６は、実施の形態２にかかる暗号処理システムのシステム構成を示すブロック図である。図１６に示すように、実施の形態２にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置１４２０と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置１４３０を備え、受信装置４０は復号化装置４００を備えている。
【０１５８】
本実施の形態において、パラメータ装置１００、復号化装置４００は、実施の形態１と同様の機能、構成を有している。
【０１５９】
鍵生成装置１４２０は、パラメータ生成装置１００によって生成されたパラメータ（公開情報）を用いて、公開鍵と、公開鍵に対応する秘密鍵とを生成し、生成された公開鍵を圧縮して出力する。
【０１６０】
図１７は、実施の形態２の鍵生成装置１４２０の機能的構成を示すブロック図である。本実施の形態の鍵生成装置１４２０は、図１７に示すように、鍵計算部２１０と、圧縮処理部１４２１と、通信部２２０とを備えている。鍵計算部２１０と通信部２２０は、実施の形態１の鍵生成装置２００と同様の機能および構成を有している。
【０１６１】
圧縮処理部１４２１は、鍵計算部２１０で生成された公開鍵を、標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算により、トーラス圧縮する。圧縮された公開鍵は、通信部２２０によって暗号化装置１４３０に送信される。
【０１６２】
図１８は、暗号化装置１４３０の機能的構成を示すブロック図である。本実施の形態の暗号化装置１４３０は、暗号化処理部３１０と、圧縮処理部３２０と、伸長処理部１４３１と、通信部３３０と、公開鍵記憶部３４０とを備えている。ここで、暗号化処理部３１０、圧縮処理部３２０、通信部３３０、公開鍵記憶部３４０については実施の形態１の暗号化装置３００と同様の機能および構成を有している。
【０１６３】
伸長処理部１４３１は、通信部３３０が鍵生成装置１４２０から受信したトーラス圧縮された公開鍵を、標数ｐおよび拡大次数mの拡大体またはその部分体上の演算により、トーラス伸長する。
【０１６４】
次に、以上のように構成された本実施の形態の鍵生成処理について説明する。図１９は、実施の形態２の鍵生成処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力から生成元ｇに対するべき乗計算までの処理（ステップＳ９１〜Ｓ９５）については、実施の形態１におけるステップＳ５１からＳ５５までの処理と同様に行われる。
【０１６５】
べき乗演算が終了したら、算出されたｇ~，ｅ，ｆ，ｈを、圧縮処理部１４２１により圧縮写像を用いて標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算によりトーラス圧縮する（ステップＳ９６）。
【０１６６】
そして、通信部２２０は、圧縮された（ｇ~，ｅ，ｆ，ｈ）を圧縮公開鍵として出力し（ステップＳ９７）、また、（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を秘密鍵として出力する（ステップＳ９８）。より具体的には、出力部２２０は、公開鍵を暗号化装置１４３０に送信し、秘密鍵を復号化装置４００に送信する。
【０１６７】
次に、暗号化装置１４３０による暗号化処理について説明する。図２０は、実施の形態２の暗号化処理の手順を示すフローチャートである。
【０１６８】
まず、通信部３０３が、生成元ｇ、圧縮公開鍵（ｇ~、ｅ、ｆ、ｈ）と、平文データｍとを受信（入力）する（ステップＳ１０１）。次に、伸長処理部１４３１は、受信した圧縮公開鍵（ｇ~、ｅ、ｆ、ｈ）を、伸長写像を用いて標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算によりトーラス伸長する（ステップＳ１０２）。
【０１６９】
これ以降、伸長された公開鍵を用いた暗号文の生成処理については、実施の形態１の暗号化処理におけるステップＳ６２からＳ６９までの処理と同様に行われる。
【０１７０】
このように実施の形態２では、鍵生成の際の圧縮処理、暗号化処理の際の伸長処理における演算を、標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上で行っている。このため、本実施の形態では、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができ、これにより、より安全性のある暗号化処理を実現することができる。
【０１７１】
（実施の形態３）
実施の形態３の暗号処理システムは、パラメータ生成装置において、パラメータに対してトーラス上離散対数問題における効率的な計算法が有効な場合に、当該パラメータの生成を回避するものである。
【０１７２】
図２１は、実施の形態３にかかる暗号処理システムのシステム構成を示すブロック図である。図２１に示すように、実施の形態３にかかる暗号処理システムは、パラメータ生成装置１９１０と、鍵生成装置２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【０１７３】
本実施の形態において、鍵生成装置２００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１と同様の機能、構成を有している。
【０１７４】
図２２は、実施の形態３のパラメータ生成装置１９１０の機能的構成を示すブロック図である。本実施の形態のパラメータ生成装置１９１０は、図２２に示すように、入力受付部１１０と、拡大次数決定部１２０と、第１素数探索部１３０と、第２素数探索部１４０と、検査部１５０と、安全性判定部１７０と、有効性判定部１９１１と、出力部１６０とを主に備えている。ここで、入力受付部１１０、拡大次数決定部１２０、第１素数探索部１３０、第２素数探索部１４０、検査部１５０、安全性判定部１７０、出力部１６０については、実施の形態１のパラメータ生成装置１００と同様の機能および構成を有している。
【０１７５】
有効性判定部１９１１は、パラメータ（ｐ，ｑ，ｍ，ｎ）に対し、トーラス上離散対数問題における効率的な計算法が有効か否かを判定する。以下、かかる判定について詳細に説明する。
【０１７６】
トーラス上離散対数問題の解法にＧｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法がある。このＧｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法については、文献「Ｒ．Ｇｒａｎｇｅｒ ａｎｄ Ｆ． Ｖｅｒｃａｕｔｅｒｅｎ，“Ｏｎ ｔｈｅ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｐｒｏｂｌｅｍ ｏｎ Ａｌｇｅｂｒａｉｃ Ｔｏｒｉ”， ＣＲＹＰＴＯ ２００５， ＬＮＣＳ ３６２１，ｐｐ．６６−８５，２００５．」に開示されている。
【０１７７】
Ｇｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法により効率的な解法を行うことができるパラメータの生成を回避する必要がある。Ｇｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法では、Ｔ２アルゴリズムとＴ６アルゴリズムの２種類のアルゴリズムが提案されている。
【０１７８】
Ｔ２アルゴリズムの計算量は、（１２−１）式、Ｔ６アルゴリズムの計算量は（１２−２）式で算出される量になると見積もられている。
【０１７９】
【数１２】
【０１８０】
ここで、Ｔ２アルゴリズムはｎ＝２であってｍ！≒ｐ、すなわち、（１３−１）式を満たす場合に、準指数時間になると理論的に見積もられている。一方、Ｔ６アルゴリズムはｎ＝６であって（２ｍ）！２12m≒ｐ、すなわち、（１３−２）式のとき準指数時間になると実験により見積もられている。
【０１８１】
【数１３】
【０１８２】
従って、（１３−１）式、あるいは（１３−２）式を満たすようなパラメータの生成を回避する必要がある。
【０１８３】
本実施の形態の有効性判定部１９１１では、パラメータ（ｐ，ｑ，ｍ，ｎ）が、（１３−１）式または（１３−２）式の条件を満たすか否かを調べることにより、当該パラメータに対してトーラス上離散対数問題における効率的な計算法が有効か否かを判定する。
【０１８４】
ここで、有効性判定部１９１１では、（１３−１）式、（１３−２）式のそれぞれにおいて、右辺の値と左辺の値とが近似しているか否かは、右辺の値と左辺の値との差が所定の範囲内にあるか否かを判断することにより判定する。
【０１８５】
また、Ｔ２アルゴリズムは （ｐ，ｑ，ｍ，ｎ（＝６））に対して（ｐ，ｑ，ｍ’（＝３ｍ），ｎ’（＝２））として適用できるので、有効性判定部１９１１は、ｎ＝６の場合には、かかる適用を行って、（１３−１）式、（１３−２）式の判定を行っている。
【０１８６】
また、本実施の形態では、有効性判定部１９１１は、すべてのパラメータ（ｐ、ｑ、ｍ、ｎ）生成された場合に、（１３−１）式、（１３−２）式の判定を行って、（１３−１）式、（１３−２）式を満たす場合には、再度、パラメータ（ｐ、ｑ、ｍ、ｎ）の決定をやり直している。
【０１８７】
次に、本実施の形態のパラメータ生成処理について説明する。図２３は、実施の形態３のパラメータ生成処理の手順を示すフローチャートである。（ｎ，Ｗ，Ｓ）の入力受付けからパラメータ（ｐ，ｑ，ｍ，ｎ）の出力までの処理（ステップＳ１２１〜Ｓ１２７）については、実施の形態１のパラメータ生成処理と同様に行われる。
【０１８８】
本実施の形態では、ステップＳ１２７において、パラメータ（ｐ，ｑ，ｍ，ｎ）が出力された場合、さらに、このパラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式または（１３−２）式の条件を満たすか否かを判定する（ステップＳ１２８）。
【０１８９】
そして、パラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式または（１３−２）式の条件を満たす場合には（ステップＳ１２８：Ｙｅｓ）、かかるパラメータはトーラス上離散対数問題における効率的な計算法が有効なパラメータであるため、これらを除外すべく、再度、ステップＳ１２２からの処理を繰り返す。
【０１９０】
ステップＳ１２８において、パラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式および（１３−２）式の条件を満たさない場合には（ステップＳ１２８：Ｎｏ）、かかるパラメータはトーラス上離散対数問題における効率的な計算法が有効でないパラメータであるため、これらのパラメータを以降の暗号処理に用いるべく、パラメータ（ｐ，ｑ，ｍ，ｎ）を出力する（ステップＳ１２９）。
【０１９１】
このように本実施の形態では、パラメータ生成処理の際に、トーラス上離散対数問題における効率的な計算法が有効であるパラメータを除外しているので、より安全で適切なパラメータ生成を行うことができる。
【０１９２】
ここで、(１３−１)式、（１３−２）式の判定のタイミングについて、他の例を考える。(１３−１)式、（１３−２）式を見てみると、この２つの条件式は、素数ｑに依存しないことがわかる。従って、実施の形態３の変形例１では、素数ｐの探索が終了した時点で、有効性判定部１９１１により、素数ｑをのぞいたパラメータｍ、ｐ、ｎが(１３−１)式、または（１３−２）式の条件を満たすか否か判定している。これにより、パラメータ生成の処理時間の短縮化を図ることができる。
【０１９３】
図２４は、実施の形態３の変形例１のパラメータ生成処理の手順を示すフローチャートである。図２４に示すように、第１素数探索部１３０で素数ｐが探索された場合に（ステップＳ１４４：Ｙｅｓ）、有効性判定部１９１１により、ステップＳ１４２で決定された拡大次数ｍ、探索された素数ｐと、ｎとを用いて、（１３−１）式または（１３−２）式の条件の判断を行う（ステップＳ１４５）。そして、（１３−１）式または（１３−２）式の条件が成立する場合には（ステップＳ１４５：Ｙｅｓ）、ステップＳ１４２へ戻り、再度、ｍの決定、ｐの探索を繰り返す。
【０１９４】
一方、（１３−１）式または（１３−２）式の条件が成立しない場合には（ステップＳ１４５：Ｎｏ）、素数ｑの探索を行う。これ以降の処理は、実施の形態１のパラメータ生成処理と同様に行われる。
【０１９５】
実施の形態３の変形例２では、素数ｐを探索する際に、有効性判定部１９１１は、（１３−１）式または（１３−２）式の条件を満たす素数ｐの範囲を決定し、第１素数探索部１３０でこの範囲で素数ｐの探索を行っている。
【０１９６】
図２５は、実施の形態３の変形例２のパラメータ生成処理の手順を示すフローチャートである。本変形例では、実施の形態１の変形例２のパラメータ生成処理に上記処理を追加している。すなわち、ｍ~n＝１となるｍを決定したら（ステップＳ１６２）、有効性判定部１９１１は、（１３−１)式または（１３−２）式の条件が成立する素数ｐの範囲を決定する（ステップＳ１６３）。そして、第１素数探索部１３０は、Ｗ／ｎｍビット以上で、かつステップＳ１６２で決定された範囲で素数ｐを探索する（ステップＳ１６４）。これ以降の処理については、実施の形態１の変形例２のパラメータ生成処理と同様である。
【０１９７】
実施の形態３の変形例３では、素数ｐを探索する際に、拡大次数決定部１２０は、（１３−１）式または（１３−２）式の条件を満たすｍを決定している。
【０１９８】
図２６は、実施の形態３の変形例３のパラメータ生成処理の手順を示すフローチャートである。入力受付部１１０が（ｎ，Ｗ，Ｓ）の入力を受け付ける（ステップＳ１８１）。そして、有効性判定部１９１１は、（１３−１）式、（１３−２）式の条件が成立しないｍの範囲を定め、拡大次数決定部１２０は、この範囲で拡大次数ｍを決定する（ステップＳ１８２）。
【０１９９】
例えば、Ｔ２アルゴリズムについて（１４−１）式、Ｔ６アルゴリズムについて（１４−２）式となるｍを避ける。
【０２００】
【数１４】
【０２０１】
例えば、右辺と左辺に１０倍以上の差があれば採用する。ｌｏｇ（ｐ）の下限はＷ／ｎｍであるから（１４−１）式と（１４−２）式の右辺はＷ／ｎｍとして良い。実施の形態１で説明したように、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１のとき、これらの多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である十分条件のうち、１）と５）の条件より、ｍ＝３eであるから、ｍ＝３，９，２７，８１，２４３，７２９，・・・について、Ｗ／ｎｍ，３ｍ×ｌｏｇ（３ｍ），２ｍ×ｌｏｇ（ｍ）＋１２ｍを計算する。さらに、（１４−１）式と（１４−２）式の条件を回避すると、ｍ＝２７，８１，２４３が得られる。７２９以上のｍについてはＷ／ｎｍ＜１となるので有限体のサイズ６ｍ×ｌｏｇ（ｐ）がＷ程度となるｐは存在しないので対象外とする。
【０２０２】
他の例では、実施の形態１で説明したように、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δのとき、これらの多項式がそれぞれＦｐ、Ｆｐm、Ｆｐ3m上で既約である必要十分条件のうち、６‘）の条件より、ｍ＝２ａ３ｂであるから、（１４−１）式と（１４−２）式の条件を回避すると、１６以下が除外される。３８４以上のｍについてはＷ／ｎｍ＜１となるので有限体のサイズ６ｍ×ｌｏｇ（ｐ）がＷ程度となるｐは存在しないので対象外とする。
【０２０３】
（実施の形態４）
実施の形態４の暗号処理システムでは、パラメータ生成装置１００で生成されたパラメータの安全性を判定する安全性判定装置を備えている。
【０２０４】
図２７は、実施の形態４にかかる暗号処理システムのシステム構成を示すブロック図である。図２７に示すように、実施の形態４にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置２００と、安全性判定装置２４００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【０２０５】
本実施の形態において、パラメータ生成装置１００、鍵生成装置２００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１と同様の機能、構成を有している。
【０２０６】
図２８は、安全性判定装置２４００の機能的構成を示すブロック図である。本実施の形態の安全性判定装置２４００は、第１検査部２４１０と、第２検査部２４２０と、判定部２４３０と、通信部２４５０と、記憶部２４４０とを主に備えている。
【０２０７】
素数位数ｑの群が標数ｐの拡大体に埋め込まれるとき、最小の拡大次数をｏｒｄ（ｑ，ｐ）と表すと、パラメータが満たすべき条件はｏｒｄ（ｑ，ｐ）＝ｎｍと書き換えられる。この条件をパラメータが満たしているかどうかについては、パラメータ（ｐ，ｑ，ｍ，ｎ）が上述した（９−１）式と（９−２）式の２つの条件を満たしているかを判断する。
【０２０８】
代数的トーラスの部分トーラスがいくつかあるとき、暗号に使う部分群の位数はｑで固定しておくとする。(９−１）式の条件１は、一番大きな拡大体に対応する（その部分体には包含されない）部分トーラスに含まれる部分群を暗号に使うことを意味する。（９−２）式の条件２は、暗号に使う部分群が、より小さな拡大体と対応する部分トーラスには含まれないことを意味する。すなわち、（９−２）式の条件２は、暗号に使う部分群は、部分トーラスのうち、ただひとつのトーラスに含まれることを意味する。
【０２０９】
従って、第１検査部２４１０は、パラメータが上述した（９−１）式を満たすか否かを判断して円分多項式Φnm（ｐ）がｑで割り切れるか否かを判断することにより、素数位数部分群Ｇが代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるか否かを検査する。
【０２１０】
第２検査部２４２０は、パラメータが上述した（９−２）式を満たすか否かを判断して乗算値ｎｍがｑで割り切れるか否かを判断することにより、素数位数部分群Ｇが代数的トーラスＴの部分群のうち、唯一の部分群に含まれるかを検査する。
【０２１１】
判定部２４３０は、第１検査部２４１０の検査結果が肯定的であり、かつ、第２検査部によ２４２０る検査結果が肯定的である場合に、パラメータ（ｐ，ｑ，ｍ，ｎ）は標数ｐ、拡大次数ｎｍの拡大体と同等の安全性を有すると判定する。
【０２１２】
通信部２４５０は、パラメータ（ｐ，ｑ，ｍ，ｎ）を受信し、また安全性の判定結果を送信する。
【０２１３】
記憶部２４４０は、判定結果などを一時的に保存する記憶媒体である。
【０２１４】
次に以上のように構成された安全性判定装置２４００による安全性判定処理について説明する。図２９は、実施の形態４の安全性判定処理の手順を示すフローチャートである。
【０２１５】
まず、通信部２４５０が、パラメータ生成装置１００で生成されたパラメータ（ｐ、ｑ、ｍ、ｎ）を受信することより受け付ける（ステップＳ２０１）。次に検査部２４１０は、円分多項式Φnm（ｐ）がｑで割り切れるか否かを調べる（ステップＳ２０２）。そして、割り切れない場合には（ステップＳ２０２：Ｎｏ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnm（標数ｐ、拡大次数ｎｍの拡大体）と同等の安全性がないと判定し（ステップＳ２０６）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２０７）。
【０２１６】
一方、ステップＳ２０２で、円分多項式Φnm（ｐ）がｑで割り切れる場合には（ステップＳ２０２：Ｙｅｓ）、第２検査部２４２０は、ｎｍがｑで割り切れるか否かを調べる（ステップＳ２０３）。そして、ｎｍがｑで割り切れた場合には（ステップＳ２０３：Ｙｅｓ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性がないと判定し（ステップＳ２０６）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２０７）。
【０２１７】
一方、ステップＳ２０３で、ｎｍがｑで割り切れない場合には（ステップＳ２０３：Ｎｏ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性があると判定し（ステップＳ２０４）、通信部２４５０は、パラメータ（ｐ、ｑ、ｍ、ｎ）の出力を行う（ステップＳ２０５）。
【０２１８】
このように実施の形態４では、得られたパラメータが（９−１）式、（９−２）式の条件を満たすか否かを判定しているので、安全性の低下を未然に防止することが可能となる。
【０２１９】
ここで、（９−２）式で示す条件２が成立しない場合でも、すべてのｄ｜ｎｍ，ｄ＜ｎｍについて、（１０）式が成立すれば、パラメータは安全性を有することになる。
【０２２０】
図３０は、実施の形態４の変形例１の安全性判定処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力受付け（ステップＳ２２１）、円分多項式Φnm（ｐ）がｑで割り切れるか否かの判断（ステップＳ２２２）およびｎｍがｑで割り切れるか否かの判断（ステップＳ２２３）は、実施の形態４における図２９の処理（ステップＳ２０１，Ｓ２０２，Ｓ２０３）と同様に行われる。本変形例では、ステップＳ２２３において、ｎｍがｑで割り切れ、（９−２）式の条件２を満たさない場合でも（ステップＳ２２３：Ｙｅｓ）、すべてのｄ｜ｎｍ，ｄ＜ｎｍについて、（１０）式が成立するか否かを調べる。すなわち、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるか否かを調べる（ステップＳ２２６）。そして、割り切れない場合には（ステップＳ２２６：Ｎｏ）、（１０）式を満たすと判断して、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性があると判定し（ステップＳ２２４）、通信部２４５０は、パラメータ（ｐ、ｑ、ｍ、ｎ）の出力を行う（ステップＳ２２５）。
【０２２１】
一方、ステップＳ２２６において、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２２６：Ｙｅｓ）、（１０）式を満たさないと判断して、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性がないと判定し（ステップＳ２２７）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２２８）。
【０２２２】
また、実施の形態４の変形例２として、（９−１）式で示す条件１、（９−２）式で示す条件２が成立しない場合でも、暗号系が定義されている素数位数部分群Ｇがどの拡大体に包含されるかを調べ、どの程度安全性が低下するかを出力しても良い。
【０２２３】
図３１は、実施の形態４の変形例２の安全性判定処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力（ステップＳ２４１）および円分多項式Φnm（ｐ）がｑで割り切れるか否かの判断（ステップＳ２４２）、ｎｍがｑで割り切れるか否かの判断（ステップＳ２４３）およびｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるか否かの判断（ステップＳ２４４）は、実施の形態４の変形例１における図３０の処理（ステップＳ２２１，Ｓ２２２，Ｓ２２３，Ｓ２２４）と同様に行われる。
【０２２４】
本変形例では、ステップＳ２４２において、円分多項式Φnm（ｐ）がｑで割り切れず（ステップＳ２４２：Ｎｏ）、（９−１）式の条件１を満たさない場合には、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるかどうか調べる（ステップＳ２４７）。そして、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２４７：Ｙｅｓ）、（１０）式を満たさないと判断して、割り切れた最小のｄを取得して（ステップＳ２４８）、拡大体Ｆｐdと同等の安全性があると判定する（ステップＳ２４９）。
【０２２５】
一方、ステップＳ２４７において、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れない場合には（ステップＳ２４７：Ｎｏ）、判定部２４３０は安全性は不明であると判定し（ステップＳ２５１）、通信部２４５０は安全性が不明である旨を出力する（ステップＳ２５３）。
【０２２６】
また、ステップＳ２４３において、ｎｍがｑで割り切れ、（９−２）式の条件２を満たさない場合でも（ステップＳ２４３：Ｙｅｓ）、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるかどうか調べる（ステップＳ２４４）。そして、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２４４：Ｙｅｓ）、（１０）式を満たさないと判断して、割り切れた最小のｄを取得して（ステップＳ２４８）、拡大体Ｆｐdと同等の安全性があると判定する（ステップＳ２４９）。これにより、安全性のレベルを判定することが可能となる。
【０２２７】
一方、ステップＳ２４４において、ｎｍがｑで割り切れない場合には（ステップＳ２４４：Ｎｏ）、実施の形態４の変形例１における図３０と同様の処理（ステップＳ２２４，Ｓ２２５）が行われる（ステップＳ２４５，Ｓ２４６）。
【０２２８】
（実施の形態５）
実施の形態５にかかる暗号処理システムは、鍵生成装置における公開鍵計算部の処理を効率化するものである。図３２は、実施の形態５にかかる暗号処理システムのシステム構成を示すブロック図である。図３２に示すように、実施の形態５にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置３２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置３００を備えている。
【０２２９】
本実施の形態において、パラメータ生成装置１００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１または２と同様の機能、構成を有している。
【０２３０】
図３３は、実施の形態５の鍵生成装置３２００の機能的構成を示すブロック図である。本実施の形態の鍵生成装置３２００は、図３３に示すように、鍵計算部３２１０と、通信部２２０とを主に備えている。ここで、通信部２２０の機能は、実施の形態１と同様である。
【０２３１】
鍵計算部３２１０は、実施の形態１と同様に、パラメータ生成装置１００で生成されたパラメータ（ｐ，ｑ，ｍ，ｎ）を入力して公開鍵や秘密鍵を生成する。鍵計算部３２１０は、乱数生成部２１１と、伸長処理部３２３２と、演算部３２１２とを備えている。乱数生成部２１１の機能は、実施の形態１と同様である。
【０２３２】
演算部３２１２は、実施の形態１と同様に秘密鍵を生成する他、素数位数部分群Ｇの生成元ｇを取得する。このとき、演算部３２１２は、生成元ｇを圧縮された表現で取得する。生成元ｇを生成する場合、圧縮した表現とすると素数位数部分群Ｇに入らない生成元を生成する確率が下がり、生成元の生成効率を向上させることができる。特に、素数位数部分群Ｇが素数位数の代数的トーラスＴの場合は、代数的トーラスＴが定義される有限体Ｆｐmの要素を生成すれば、常に素数位数部分群Ｇに入る生成元ｇを生成することができる。また、生成元ｇをメモリに記憶しておき、メモリから生成元ｇを読み出す形態においても、生成元ｇを圧縮した表現でメモリ等に記憶する場合の方が、圧縮されていない生成元ｇを記憶する場合に比べて、メモリの記憶容量を削減することができるという利点がある。
【０２３３】
伸長処理部３２３２は、演算部３２１２により取得した圧縮した表現の生成元ｇを、演算部３２１２によるべき乗または乗算を行う前に、トーラス伸長する。演算部３２１２は、伸長処理部３２３２によりトーラス伸長された生成元ｇに対して、実施の形態１と同様に、標数pおよび拡大次数mの拡大体またはその部分体上で、生成した乱数を用いてべき乗演算および乗算を行い公開鍵を求める。
【０２３４】
次に、鍵生成装置３２００による鍵生成処理について説明する。図３４は、実施の形態５の鍵生成処理の手順を示すフローチャートである。
【０２３５】
まず、パラメータ（ｐ、ｑ、ｍ、ｎ）の入力から乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２の生成までの処理（ステップＳ２６１〜Ｓ２６３）は、実施の形態１における鍵生成処理（ステップＳ５１〜Ｓ５３）と同様に行われる。
【０２３６】
乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２が生成されたら、演算部３２１２が、素数位数部分群Ｇの圧縮された表現の生成元ｇを取得する（ステップＳ２６４）。そして、べき乗計算または乗算を行う前に、伸長処理部３２３２は、圧縮された表現の生成元ｇをトーラス伸長する（ステップＳ２６５）。
【０２３７】
これ以降の公開鍵の生成および出力、秘密鍵の出力の処理（ステップＳ２６６〜Ｓ２６８）は、実施の形態１における鍵生成処理（ステップＳ５５〜Ｓ５７）と同様に行われる。
このように実施の形態５では、鍵生成装置３２００において、圧縮された表現の生成元ｇを取得して、伸長処理部３２３２によって取得した生成元ｇ（圧縮表現）のトーラス伸長を行っているので、生成元ｇの生成時にその位数をチェックしたり、代数的トーラスの要素を伸長した表現で記憶しなければならない伸長処理部３２３２のない鍵生成装置に比べて、生成元ｇの取得にかかる処理を効率的に行うことができる。
【０２３８】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置は、ＣＰＵなどの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭなどの記憶装置と、ＨＤＤ、ＣＤドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０２３９】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０２４０】
また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０２４１】
また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０２４２】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムは、上述した各部を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体から各プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上記各部が主記憶装置上に生成されるようになっている。
【０２４３】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【図面の簡単な説明】
【０２４４】
【図１】実施の形態１にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２】実施の形態１のパラメータ生成装置の機能的構成を示すブロック図である。
【図３】実施の形態１の鍵生成装置の機能的構成を示すブロック図である。
【図４】実施の形態１の暗号化装置の機能的構成を示すブロック図である。
【図５】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。
【図６】実施の形態１の復号化装置の機能的構成を示すブロック図である。
【図７】実施の形態１のパラメータ処理の手順を示すフローチャートである。
【図８】実施の形態１の変形例１のパラメータ生成処理の手順を示すフローチャートである。
【図９】実施の形態１の変形例２のパラメータ生成処理の手順を示すフローチャートである。
【図１０】実施の形態１の変形例３のパラメータ生成処理の手順を示すフローチャートである。
【図１１】実施の形態１の鍵生成処理の手順を示すフローチャートである。
【図１２】実施の形態１の暗号化処理の手順を示すフローチャートである。
【図１３】実施の形態１の復号化処理の手順を示すフローチャートである。
【図１４】実施の形態１の変形例４の鍵生成処理の手順を示すフローチャートである。
【図１５】実施の形態１の変形例５の復号化処理の手順を示すフローチャートである。
【図１６】実施の形態２にかかる暗号処理システムのシステム構成を示すブロック図である。
【図１７】実施の形態２の鍵生成装置の機能的構成を示すブロック図である。
【図１８】暗号化装置１４３０の機能的構成を示すブロック図である。
【図１９】実施の形態２の鍵生成処理の手順を示すフローチャートである。
【図２０】実施の形態２の暗号化処理の手順を示すフローチャートである。
【図２１】実施の形態３にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２２】実施の形態３のパラメータ生成装置の機能的構成を示すブロック図である。
【図２３】実施の形態３のパラメータ生成処理の手順を示すフローチャートである。
【図２４】実施の形態３の変形例１のパラメータ生成処理の手順を示すフローチャートである。
【図２５】実施の形態３の変形例２のパラメータ生成処理の手順を示すフローチャートである。
【図２６】実施の形態３の変形例３のパラメータ生成処理の手順を示すフローチャートである。
【図２７】実施の形態４にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２８】安全性判定装置の機能的構成を示すブロック図である。
【図２９】実施の形態４の安全性判定処理の手順を示すフローチャートである。
【図３０】実施の形態４の変形例１の安全性判定処理の手順を示すフローチャートである。
【図３１】実施の形態４の変形例２の安全性判定処理の手順を示すフローチャートである。
【図３２】実施の形態５にかかる暗号処理システムのシステム構成を示すブロック図である。
【図３３】実施の形態５の鍵生成装置の機能的構成を示すブロック図である。
【図３４】実施の形態５の鍵生成処理の手順を示すフローチャートである。
【符号の説明】
【０２４５】
３０ 送信装置
４０ 受信装置
１００，１９１０ パラメータ生成装置
１１０ 入力受付部
１２０ 拡大次数決定部
１３０ 第１素数探索部
１４０ 第２素数探索部
１５０ 検査部
１６０ 出力部
１７０ 安全性判定部
２００，１４２０ 鍵生成装置
２１０ 鍵計算部
２１１，３１１ 乱数生成部
２１２，３１２，４２３ 演算部
２２０，３３０，４３０，２４５０ 通信部
３００、１４３０ 暗号化装置
３１０ 暗号化処理部
３２０，４５０，１４２１ 圧縮処理部
３４０ 公開鍵記憶部
４００ 復号化装置
４１０，１４３１ 伸長処理部
４２０ 復号化処理部
４２１ 第１判定部
４２２ 第２判定部
４４０ 秘密鍵記憶部
１９１１ 有効性判定部
２４００ 安全性判定装置
２４１０ 第１検査部
２４２０ 第２検査部
２４３０ 判定部
２４４０ 記憶部
【技術分野】
【０００１】
この発明は、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化する際のパラメータを生成するパラメータ生成装置、このパラメータ生成装置を備えた暗号処理システム、方法およびプログラムに関する。
【背景技術】
【０００２】
事前の鍵共有なしに安全な通信を実現する公開鍵暗号方式は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになってきた。
【０００３】
公開鍵暗号方式において現在の典型的な暗号系サイズは１０２４ビットであるが、解読が困難とされる暗号系サイズは年々大きくなっている。計算機の進歩とともに攻撃者の能力も上がっているためである。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となるので、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号方式における公開鍵のサイズや暗号文のサイズを圧縮する圧縮暗号技術が考案されている（例えば、非特許文献１参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。圧縮暗号の技術では、圧縮率（すなわち、圧縮前のビット数／圧縮後のビット数）を大きくする改良を行っており、集合の要素を小さいビット数の表現に変換する際に付加的な入力を用いる（例えば、非特許文献２参照）。小さいビット数の表現へ変換を行う写像を圧縮写像ρ、θといい、それぞれＲＳ圧縮写像、ＤＷ圧縮写像と呼ぶことにする。
【０００５】
暗号文を圧縮する場合には、ＲＳ圧縮写像ρでは、暗号文ｃを入力として次式に示す計算を行い、圧縮暗号文γを得る。
【０００６】
ρ（ｃ）＝γ
また、DW圧縮写像θでは、暗号文cが入力として与えられたときに適当な補助入力ａ１を用いて次式のような計算を行い、圧縮暗号文γと補助出力ａ１を得る。
θ（ｃ，ａ１）＝（γ，ａ２）
【０００７】
圧縮暗号文を圧縮前の元のビット数の表現に戻す場合には、それぞれρ、θの逆写像を（γ，ａ２）に施す。圧縮写像ρの逆写像をρ-1、圧縮写像θの逆写像をθ-1と記述し、それぞれＲＳ伸長写像、ＤＷ伸長写像と呼ぶ。ＲＳ伸長写像では、圧縮暗号文としてγが与えられたときに次式のような計算を行い、cを得る。
【０００８】
ρ-1（γ）＝ｃ
ＤＷ伸長写像では、圧縮暗号文としてγとａ２の組が与えられたときに次式の計算を行い、ｃとａ１を得る。
【０００９】
θ-1（γ，ａ２）＝（ｃ，ａ１）
代数的トーラスを用いた圧縮伸長は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用できる。
【００１０】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号が非特許文献３にて提案されている。Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は標準モデルでの安全性が証明されている方式であるが、公開鍵や暗号文の成分の数が多いという特徴がある。具体的には、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の暗号文は４つの成分（ｃ１，ｃ２，ｃ３，ｃ４）からなる。公開鍵も４つの成分（ｇ〜，ｅ，ｆ，ｈ）からなる。しかも、各成分は実際に暗号に用いられる群よりも大きな表現で表されるという問題がある。つまり、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は有限群Ｇ~の素数位数部分群Ｇ上で定義されているが、公開鍵や暗号文の成分はＧ~の表現で表されている。具体的には、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は素体の乗法群の素数位数部分群で定義されているが、公開鍵や暗号文の成分は素体の表現で表されている。
【００１１】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号やその他の公開鍵暗号において、有限群Ｇ~の部分群であって実際に暗号に用いられる群Ｇを代数的トーラスＴの部分群とすることにより、公開鍵や暗号文を有限群Ｇ~のサイズではなく代数的トーラスＴのサイズで表現する。ここで、代数的トーラスＴは有限群Ｇ~の部分群とする。
【００１２】
これまでに、素体上の代数的トーラスを用いたＥｌＧａｍａｌ暗号やＤＨ鍵交換が提案されている（非特許文献１、２参照）。Ｔが素体上のトーラスの場合、Ｔの部分群となるより小さなトーラスは存在しない。このとき、Ｇ~を拡大体Ｆの乗法群とする。部分群Ｇを選択する際には、Ｇの位数がＴの位数を割り切ることと、Ｇの位数がＦの拡大次数を割り切らないことを示していた。
【００１３】
【非特許文献１】Ｋ． Ｒｕｂｉｎ ａｎｄ Ａ． Ｓｉｌｖｅｒｂｅｒｇ， “Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＹＰＴＯ ２００３， ＬＮＣＳ ２７２９， ３４９−３６５， ２００３．
【非特許文献２】Ｍ． ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ． Ｗｏｏｄｒｕｆｆ， “Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， ＣＲＹＰＴＯ ２００４， ＬＮＣＳ ３１５２， １５７−１７８， ２００４．
【非特許文献３】Ｒ． Ｃｒａｍｅｒ ａｎｄ Ｖ． Ｓｈｏｕｐ， ”Ａ ｐｒａｃｔｉｃａｌ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍ ｐｒｏｖａｂｌｙ ｓｅｃｕｒｅ ａｇａｉｎｓｔ ａｄａｐｔｉｖｅ ｃｈｏｓｅｎ ｃｉｐｈｅｒｔｅｘｔ ａｔｔａｃｋ”， ＣＲＹＰＴＯ’９８， ＬＮＣＳ １４６２， ｐｐ．１３−２５， １９９８．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、拡大体上の代数的トーラスを用いた公開鍵暗号については、適切なパラメータ選択は知られていない。このため、素体上の代数的トーラスの場合のパラメータの選択方法を、拡大体上の代数的トーラスを用いた公開鍵暗号にそのまま適用することも考えられる。
【００１５】
しかしながら、この方法では、部分群Ｇが拡大体Ｆよりも小さな拡大体に包含される場合を排除できず、適切なパラメータを選択することができないという問題がある。
【００１６】
本発明は、上記に鑑みてなされたものであって、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができるパラメータ生成装置、暗号処理システム、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上述した課題を解決し、目的を達成するために、本発明にかかるパラメータ生成装置は、 トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、前記有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、を備えたことを特徴とする。
【００１８】
また、本発明にかかる暗号処理システムは、パラメータ生成装置と、鍵生成装置と、暗号化装置と、前記暗号化装置にネットワークで接続された復号化装置とを備えた暗号処理システムであって、前記パラメータ生成装置は、トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、前記代数的トーラスが定義され、安全性を定める有限体FのサイズＷと、前記群ＧのサイズＳの入力を受け付ける第１入力受付部と、前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する第１出力部と、を備え、前記鍵生成装置は、前記パラメータ（ｐ，ｑ，ｎ，ｍ）の入力を受け付ける第２入力受付部と、前記素数ｑを前記群Ｇの位数とし、前記素数ｐを前記有限体Ｆの標数とし、前記標数ｐ、前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせで公開鍵を計算する公開鍵計算部と、前記公開鍵を出力する第２出力部と、を備え、前記暗号化装置は、前記公開鍵と平文の入力を受け付ける第３入力受付部と、前記標数ｐおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記平文に対して前記公開鍵を用いた暗号化処理を施して、暗号文を求める暗号化処理部と、前記暗号文を前記復号化装置に送信する送信部と、を備え、前記復号化装置は、秘密鍵を記憶する記憶部と、前記暗号文を受信する受信部と、前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記暗号文に対して前記秘密鍵を用いた復号化処理を施して、前記平文を求める復号化処理部と、前記平文を出力する第４出力部と、を備えたことを特徴とする。
【００１９】
また、本発明は上記パラメータ生成装置で実行される方法およびコンピュータを上記パラメータ生成装置の各部として機能させるプログラムである。
【発明の効果】
【００２０】
本発明によれば、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２１】
以下に添付図面を参照して、この発明にかかるパラメータ生成装置、暗号処理システム、方法およびプログラムの最良な実施の形態を詳細に説明する。
【００２２】
（実施の形態１）
図１は、実施の形態１にかかる暗号処理システムのシステム構成を示すブロック図である。図１に示すように、実施の形態１にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【００２３】
パラメータ生成装置１００は、公開鍵暗号に関する公開情報としてのパラメータを生成する。パラメータとしては、群の要素やハッシュ関数などの情報や、暗号系が定義される群に関する情報として、位数や生成元の情報が含まれる。パラメータ生成装置１００の構成の詳細については後述する。
【００２４】
鍵生成装置２００は、パラメータ生成装置１００によって生成されたパラメータ（公開情報）を用いて、公開鍵と、公開鍵に対応する秘密鍵とを生成する。鍵生成装置２００の構成の詳細については後述する。
【００２５】
暗号化装置３００を有する送信装置３０には、鍵生成装置２００が生成した公開鍵と、暗号化の対象の平文データとが入力される。この平文データは、送信装置３０に予め記憶されたものであっても、送信装置３０が生成したものであっても、他の通信装置から受信したものであっても、記憶媒体から読み出したものであってもよい。
【００２６】
暗号化装置３００は、公開鍵を用いて平文データを暗号化して暗号文を生成し、生成した暗号文を受信装置４０に送信する。暗号化装置３００の構成の詳細については後述する。
【００２７】
復号装置４００を有する受信装置４０は、暗号文を受信すると、当該暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて暗号文を復号することにより、平文データを得る。復号化装置４００の構成の詳細については後述する。
【００２８】
なお、送信装置３０および受信装置４０は、例えば、図示しないインターネットなどのネットワークを介して相互に接続されたＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）等によって構成することができる。
【００２９】
なお、暗号化装置３００および復号装置４００は、暗号方式として、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いる。適用可能な暗号方式はこれに限られず、ＥｌＧａｍａｌ暗号などの有限体上の離散対数問題に基づく暗号方式であればあらゆる方式を適用できる。
【００３０】
また、本実施の形態では、暗号化装置３００および復号装置４００が、それぞれ送信装置３０および受信装置４０に含まれる構成を例に説明するが、装置構成はこれに限られるものではない。例えば、送信装置３０および受信装置４０以外の装置に暗号化装置３００および復号装置４００が含まれるように構成してもよい。また、暗号化装置３００および復号装置４００を同一の装置上に含むように構成してもよい。
【００３１】
本実施の形態のパラメータ生成装置１００について説明する。まず、本実施の形態におけるパラメータ生成の原理について説明する。
【００３２】
体とは四則演算が定義される数の集合であって、数の集合が有限の場合は有限体と呼ばれる。有限体に含まれる数の個数は素数であるか素数のべき乗であることが知られている。数の個数が素数である体を素体といい、数の個数が素数のべき乗である体を拡大体という。素体や拡大体の要素の個数を決めている素数を標数と呼び、べき乗を拡大次数と呼ぶ。
【００３３】
乗法群とは乗算と除算が定義される数の集合であって、有限体の要素から０を除くと乗法群となることが知られている。また、群の要素の個数を位数と呼ぶ。
【００３４】
Ｔを拡大体上の代数的トーラスとすると、Ｔの部分群となるより小さなトーラスが存在する。Ｇ~を拡大体Ｆの乗法群とすると、より小さなトーラスのうち拡大体Ｆの真部分体に包含されないトーラスｔが決まり、その次数は拡大体の次数となる。ｔはＴの部分群であるので、ｔの素数位数部分群上で暗号系を定義すると、公開鍵や暗号文はＴのサイズで表現される。圧縮伸長写像が構成できるＴの次数を定め、Ｔが定義される拡大体の次数と標数を安全性の要件から求める。
【００３５】
仮に、群Ｇが拡大体Ｆの真部分体Ｆ’に包含されるとき、Ｇの安全性を決定するのはＦ’のサイズである。つまり、そのサイズの差だけ安全性が低下する。Ｆ＝Ｆ’のとき（すなわち、Ｇがｔの部分群のとき）、元のＦの安全性を下げることなくＴの素数位数部分群Ｇ上で暗号系が定義される。
【００３６】
一方、Ｆ＞Ｆ’であってもＦ’を十分なサイズとすれば、代数的トーラスＴの最大の圧縮率（すなわち、Ｆのサイズ／Ｔのサイズ）よりは小さい圧縮率（Ｆ’のサイズ／Ｔのサイズ）で圧縮される。Ｆ＝Ｆ’とするパラメータ生成法の原理を以下に詳しく示す。
【００３７】
ここで、拡大体Ｆで定まる安全性を有する群Ｇ上で公開鍵暗号系を定義することを考える。ここで拡大体Ｆの乗法群をＧ~とし、その部分群である代数的トーラスをＴとする。Ｇは代数的トーラスＴの素数位数部分群とする。これらの集合として、以下の具体的な集合を考える。
【００３８】
１）拡大体Ｆは，標数ｐのｎｍ次拡大体とする。ここで、ｐは素数、ｎとｍは正整数、Ｆの位数（要素の数）はｐnmである。すなわち、（１）式で示される。
【００３９】
【数１】
【００４０】
２）拡大体Ｆの乗法群Ｇ~の位数は、ｐnm−１である。これを（２）式で示す。
【００４１】
【数２】
（２）式において、＃Ｘは群Ｘの位数を示す。
【００４２】
３）拡大体Ｆの乗法群Ｇ~の部分群である代数的トーラスＴは、標数ｐのｍ次拡大体上で定義された次数ｎの代数的トーラスとする。代数的トーラスＴの位数は、Φn（ｐm)である。ここで、Φn（ｘ)はｎ次の円分多項式とする。これを（３）式で示す。
【００４３】
【数３】
【００４４】
４）代数的トーラスＴの素数位数部分群Ｇの位数をｑは、安全性の観点からΦnm（ｐ）を割り切る素数としなければならない。これを（４）式に示す。
【００４５】
【数４】
【００４６】
代数的トーラスＴの素数位数部分群Ｇ、代数的トーラスＴ、拡大体Ｆの乗法群Ｇ~、拡大体Ｆは、公開情報となるパラメータ（ｐ，ｑ，ｍ，ｎ）によって一意に定まる。このとき、ｐ：拡大体Ｆの標数、ｑ：素数位数部分群Ｇの位数、ｍ：代数的トーラスＴが定義される拡大体Ｆｐmの次数、ｎ：代数的トーラスＴの次数である。代数的トーラスＴの素数位数部分群Ｇが包含される最小の拡大体をＦ’とすると、ｐのｍｏｄ ｑでの位数が拡大体Ｆ’の拡大次数である。拡大体Ｆ’の拡大次数はｑ｜（ｐx−１）を満たす最小のｘであり、この関係式が（５）式のように書き換えられることより明らかである。
【００４７】
【数５】
【００４８】
この結果は、文献「Ｌａｕｒａ Ｈｉｔｔ，”Ｏｎ ｔｈｅ ｍｉｎｉｍａｌ ｅｍｂｅｄｄｉｎｇ ｆｉｅｌｄ”，Ｐａｉｒｉｎｇ２００７，ＬＮＣＳ ４５７５，ｐｐ．２９４−３０１，２００７．」に記述された拡大体上楕円曲線の埋め込み次数に関する議論を再考することにより導かれる。ｐのｍｏｄ ｑでの位数をｏｒｄ（ｑ，ｐ）と記述すると、Ｆ’＝Ｆはｏｒｄ（ｑ，ｐ）＝ｎｍと同値である。さらに、ｏｒｄ（ｑ，ｐ）＝ｎｍは（６）式と同値である。
【００４９】
【数６】
【００５０】
ｐnm−１がｄ｜ｎｍなる円分多項式Φd（ｐ）の積で分解されることより、（６）式は（７）式と同値であることを導いた。
【００５１】
【数７】
【００５２】
ここで、拡大体Ｆ’の拡大次数がｎｍの約数になることは、ｘがｑ｜（ｐx−１）を満たす最小のｘであることより証明される。さらに、文献「Ｗ．Ｂｏｓｍａ，Ｊ．Ｈｕｔｔｏｎ ａｎｄ Ｅ．Ｒ．Ｖｅｒｈｅｕｌ，“Ｌｏｏｋｉｎｇ ｂｅｙｏｎｄ ＸＴＲ”，Ａｓｉａｃｒｙｐｔ’０２，ＬＮＣＳ ２５０１，ｐｐ．４６−６３，２００２．」に記述されているように、ｑがｎｍを割り切らない場合は、ｍｏｄ ｑの多項式（Ｘnm−１）が重根を持たないので、この場合は（６）、（７）式の「かつ」以降の条件は、自動的に成立する。また、拡大体上の代数的トーラスＴの位数について、円分多項式の性質を用いると、（８）式に表されることを発見した。ここで、ｍnはｍの因数であってｎの素因数の全ての積とし、ｍ~nはｍ／ｍnとする。
【００５３】
【数８】
【００５４】
本実施の形態のパラメータ生成装置１００では、この（８）式を用いて安全でかつ扱いやすいパラメータ（ｐ，ｑ，ｍ、ｎ）を効率よく生成する。
【００５５】
図２は、実施の形態１のパラメータ生成装置１００の機能的構成を示すブロック図である。図２に示すように、本実施の形態のパラメータ生成装置１００は、入力受付部１１０と、拡大次数決定部１２０と、第１素数探索部１３０と、第２素数探索部１４０と、検査部１５０と、安全性判定部１７０と、出力部１６０とを主に備えている。
【００５６】
入力受付部１１０は、代数的トーラスＴの次数ｎと、拡大体ＦのサイズＷと、代数的トーラスＴの素数位数部分群ＧのサイズＳの入力を受け付ける。拡大次数決定部１２０は、拡大体Ｆの拡大次数ｍを決定する。
【００５７】
トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号で用いられる群は、パラメータ（ｐ，ｑ，ｍ，ｎ）によって一意に定まる。このとき、ｐ：拡大体の標数、ｑ：素数位数部分群の位数、ｍ：代数的トーラスが定義される拡大体の次数、ｎ：代数的トーラスの次数である。本実施の形態では、（７）式に基づいて定められた（９−１）式で示す条件１および（９−２）式で示す条件２の両方を満たすパラメータ（ｐ，ｑ，ｍ，ｎ）を探索する。
【００５８】
【数９】
【００５９】
条件１は、素数位数部分群Ｇが代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるための条件である。この条件１を満たす素数ｐ、ｑは、それぞれ第１素数探索部１３０、第２素数探索部１４０で探索される。
【００６０】
すなわち、第１素数探索部１３０は、拡大体FのサイズＷと、代数的トーラスＴの次数ｎと、拡大次数ｍとに基づくビット数の素数ｐを探索する。具体的には、第１素数探索部１３０は、Ｗ／ｎｍビット以上の素数pを探索する。
【００６１】
第２素数探索部１４０は、円分多項式Φnm（ｐ）を割り切る素数であって、素数位数部分群ＧのサイズＳに基づいて定められるビット数である素数ｑを探索する。具体的には、第２素数探索部１４０は、円分多項式Φnm（ｐ）を割り切るSビット以上の素数qを探索する。
【００６２】
（９−２）式で示す条件２は、素数位数部分群Ｇが代数的トーラスＴの部分群のうち、唯一の部分群に含まれる条件である。拡大次数決定部１２０で決定されたｍ、第１探索部１３０で探索された素数ｐ、第２素数探索部１４０で探索された素数ｑが、条件２を満たすかどうかは、検査部１５０で検査される。すなわち、検査部１５０は、代数的トーラスＴの次数ｎと有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍが素数qで割り切れるか否かを検査する。そして、条件２を満たさない場合には、再度、ｍの決定、ｐ、ｑの探索を行うことになる。
【００６３】
ここで、条件２として（９−２）式を用いる代わりに、（１０）式を用いるように構成してもよい。
【００６４】
【数１０】
【００６５】
ここで、ｄはｎｍの約数である。この（１０）式の条件は、ｏｒｄ（ｑ，ｐ）＝ｎｍであることの必要十分条件となる。ただし、（１０）式では、全てのdについて検査を行う必要があるため、（９−２）式の条件を判断する手法の方が、検査時間を短縮することができるという利点がある。
【００６６】
安全性判定部１７０は、検査部１５０によって乗算値ｎｍが素数qで割り切れないと検査された場合に、暗号系が安全性ありと判定する。
【００６７】
出力部１６０は、ｎｍが素数ｑで割り切れない場合に、暗号系が安全性ありと判定し、素数ｐと、素数ｑと、拡大次数ｍと、代数的トーラスの次数ｎとからなるパラメータ（ｐ，ｑ，ｍ，ｎ）を出力する。
【００６８】
次に、鍵生成装置２００について説明する。図３は、実施の形態１の鍵生成装置２００の機能的構成を示すブロック図である。本実施の形態の鍵生成装置２００は、図３に示すように、鍵計算部２１０と、通信部２２０とを主に備えている。
【００６９】
鍵計算部２１０は、パラメータ生成装置１００で生成されたパラメータ（ｐ，ｑ，ｍ，ｎ）を入力して公開鍵や秘密鍵を生成する。鍵計算部２１０は、乱数生成部２１１と、演算部２１２とを備えている。
【００７０】
乱数生成部２１１は、素数位数部分群Ｇの位数qで範囲が限定される乱数を生成する。演算部２１２は、秘密鍵を生成する。また、演算部２１２は、素数位数部分群Ｇの生成元ｇを入力し、標数pおよび拡大次数mの拡大体またはその部分体上で、素数位数部分群Ｇの生成元ｇに対して、生成した乱数を用いてべき乗演算および乗算を行うことにより、その演算結果を公開鍵として求める。
【００７１】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における鍵生成処理では、べき乗も乗算も素体上でおこなっていたが、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における鍵生成処理では、べき乗と乗算は拡大体上で行う。標数ｐの拡大次数ｎｍの拡大体上の演算となるが、ｎは代数的トーラスの次数であり、ｍは代数的トーラスが定義される拡大体の拡大次数であることより、拡大体Ｆｐmの元ｎ個からなるベクトルの計算とする。圧縮伸長写像や代数的トーラス上の演算は拡大体Ｆｐm上の演算を用いるため、同じ演算処理を利用することができ、効率な演算を行うことができる。
【００７２】
なお、拡大体Ｆｐm上の乗算と加算は必ずしも逐次的に行う必要はなく、ベクトル表現の変換やｎ次拡大の法多項式や基底は、あらかじめ拡大体の表現を合意していれば必要ない。
【００７３】
通信部２２０は、生成した秘密鍵、公開鍵をネットワークを介して暗号化装置３００、復号化装置４００に送信する。
【００７４】
次に、暗号化装置３００について説明する。図４は、実施の形態１の暗号化装置３００の機能的構成を示すブロック図である。暗号化装置３００は、図４に示すように、暗号化処理部３１０と、圧縮処理部３２０と、公開鍵記憶部３４０と、通信部３３０とを備えている。
【００７５】
暗号化処理部３１０は、拡大体Ｆの標数ｐおよび拡大次数ｍの拡大体Ｆまたはその部分体上の演算の組み合わせにより、平文に対して公開鍵を用いた暗号化処理を施して、暗号文を求めるものである。
【００７６】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図５は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。図５で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ~，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００７７】
図４に示すように、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の暗号化の具体的な処理は、乱数乗のべき乗計算と乗算、ハッシュ関数の計算からなる。
【００７８】
暗号化処理部３１０では、（Ａ−１）〜（Ａ−４）式により平文データｍに対応する暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を計算する。ここで、（Ａ−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖを求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００７９】
図４に戻り、この手順を実行するため、暗号化処理部３１０は、乱数生成部３１１と、演算部３１２とを備えている。
【００８０】
乱数生成部３１１は、素数位数群Ｇの位数qで範囲が限定される乱数ｒを生成する。演算部３１２は、生成元ｇと公開鍵とを乱数で第１のべき乗演算し（Ａ−１）、第１のべき乗演算の結果と平文とを乗算し（Ａ−２）、乗算した結果と第１のべき乗演算の結果のハッシュ値を求め（Ａ−３）、ハッシュ値と乱数で公開鍵を第２のべき乗演算し、第１のべき乗演算の結果と第２のべき乗演算の結果とを、暗号文として求める（Ａ−４）。
【００８１】
圧縮処理部３２０は、暗号化処理部３１０で生成された暗号文を圧縮写像によりトーラス圧縮する。
【００８２】
トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号における上記の暗号化処理と圧縮処理では、べき乗と乗算は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で行われる。
【００８３】
すなわち、暗号化処理と圧縮処理は、標数ｐの拡大次数ｎｍの拡大体上の演算となるが、ｎは代数的トーラスの次数であり、ｍは代数的トーラスが定義される拡大体の拡大次数であることより、拡大体Ｆｐmの元ｎ個からなるベクトルの計算とする。圧縮写像や代数的トーラス上の演算は拡大体Ｆｐm上の演算を用いるため、同じ演算処理を利用することができ、効率な演算を行うことができる。
【００８４】
なお、拡大体Ｆ上の乗算と加算は必ずしも逐次的に行う必要はなく、ベクトル表現の変換やｎ次拡大の法多項式や基底は、あらかじめ拡大体の表現を合意していれば必要ない。
【００８５】
通信部３３０は、鍵生成装置２００や復号化装置４００とのデータの送受信を行う。具体的には、通信部３３０は、鍵生成装置２００から公開鍵を受信する。また、通信部３３０は、復号化装置４００に、トーラス圧縮された暗号文を送信する。公開鍵記憶部３４０は、鍵生成装置２００から受信した公開鍵を保存しておく記憶媒体である。
【００８６】
次に、復号化装置４００について説明する。図６は、実施の形態１の復号化装置４００の機能的構成を示すブロック図である。復号化装置４００は、図６に示すように、伸長処理部４１０と、復号化処理部４２０と、圧縮処理部４５０と、秘密鍵記憶部４４０と、通信部４３０とを主に備えている。
【００８７】
通信部４３０は、鍵生成装置２００から秘密鍵を受信する。また、通信部４３０は、暗号化装置３００から圧縮された暗号文を受信する。秘密鍵記憶部４４０は、受信した秘密鍵を保存しておく記憶媒体である。
【００８８】
伸長処理部４１０は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、暗号化装置３００から受信した圧縮された暗号文を伸長写像を使って伸長する。
【００８９】
復号化処理部４２０は、暗号文を秘密鍵を用いて復号化し、平文を取得する。ここで、図５に戻り、復号化処理部４２０では、（Ｂ−１）〜（Ｂ−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）から正当な平文データであるか否かのチェックを行い、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ〜）は、ｃが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００９０】
このため、復号化処理部４２０は、第１判定部４２１と、第２判定部４２２と、演算部４２３とを備えている。
【００９１】
すなわち、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の復号の具体的な処理は、正しい群の元であるかの検査とハッシュ関数の計算、検査式のチェック（べき乗と乗算）、平文の計算（逆元と乗算）からなる。
【００９２】
第１判定部４２１は、暗号文が素数位数部分群Ｇの元であるか否かを検査し、素数位数部分群Ｇまたは拡大体Ｆの乗法群Ｇ~の元である場合には、暗号文は正当であると判定する（Ｂ−１、Ｂ−２）。
【００９３】
演算部４２３は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、暗号文の要素であるｃ１、ｃ２をべき乗演算および乗算して逆元を求め、暗号文の要素であるｃ３と乗算して平文ｍを求める（Ｂ−３，Ｂ−４）。
【００９４】
第２判定部４２２は、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上で、ハッシュ関数Ｈを用いて暗号文のハッシュ値を求め（Ｂ−５）、ハッシュ値と秘密鍵とにより暗号文の要素であるｃ１、ｃ２をべき乗演算および乗算して、暗号文の要素であるｃ４と一致する場合に、暗号文は正当であると判定する（Ｂ−６）。
【００９５】
なお、（Ｂ−１），（Ｂ−２）式による正しい群の元であるかの検査を、伸長処理の前に実行するように構成してもよく、この場合には無駄な伸長写像の計算を省くことができる。また、素数位数の代数的トーラスを用いる場合には、圧縮された表現における検査は容易となり都合が良い。さらに、ハッシュ関数の計算についても、暗号化処理部４２０とその入力値を圧縮後の値とすることで合意されているならば、伸長処理の前に行っても良い。
【００９６】
圧縮処理部４５０は、復号化処理部４２０で算出された平文を、標数pおよび拡大次数mの拡大体Ｆｐmまたはその部分体上の演算によりトーラス圧縮する。
【００９７】
次に、以上のように構成された本実施の形態の暗号処理システムにおけるパラメータ生成から復号化までの処理について説明する。
【００９８】
まず、パラメータ生成装置１００におけるパラメータ生成処理について説明する。図７は、実施の形態１のパラメータ処理の手順を示すフローチャートである。
【００９９】
まず、入力受付部１１０は、代数的トーラスＴの次数ｎ、拡大体ＦのサイズＷ、素数位数部分群ＧのサイズＳの組の入力を受け付ける（ステップＳ１１）。
【０１００】
そして、拡大次数決定部１２０により、拡大体Ｆの拡大次数ｍを決定する（ステップＳ１２）。ここで、拡大次数ｍの決定について詳細に説明する。
【０１０１】
例えば、ｎ＝６、Ｗ＝２０４８、Ｓ＝２２４として考える。拡大体Ｆｐmを構成するための条件として、素体Ｆpのｍ次拡大の法多項式がＦp上で既約であること、ｍ次拡大体Ｆpmの３次拡大の法多項式がＦpm上で既約であること、３ｍ次拡大体Ｆp3mの２次拡大の法多項式がＦp3m上で既約であることである。
【０１０２】
例えば、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１のとき、これらの法多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である十分条件は次の４つの条件が同時に成立することである。
【０１０３】
１）ｍが奇数であること。
２）ｍは３で割り切れるかつｐは４ｍで割った余りが２ｍ＋１であること、または、ｍは３で割り切れないかつｐは１２ｍで割った余りが６ｍ＋１であること。
３）ｓ(floor(p/m)d)≠１，ｄ｜ｍ，ｄ≠ｍ
４）ｗ(floor(p/m)×(p^m-1)/(p-1))≠１
ここで、ｆｌｏｏｒ（ｘ）は床関数であり、ｘを越えない最大の整数を返す関数である。また、ｐ＾ｘは、ｐのｘ乗を示す。
【０１０４】
また、素数位数トーラスとなる条件として、トーラスＴ６（Ｆpm）の位数はΦ６（ｐm）であり、これが素数となる必要条件は次式が成り立つことである。
【０１０５】
５）ｍ＝２a×３b
従って、拡大次数決定部１２０は、上記１）〜５）までの条件を満たすように、拡大次数ｍを決定している。
【０１０６】
他の例では、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δのとき、これらの法多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である必要十分条件は次の５つの条件が同時に成立することである。
【０１０７】
１’）ｍの素因数で（ｐ−１）が割り切れること、かつ、（ｐm−１）が３で割り切れること、かつ、（ｐ3m−１）が２で割り切れること。
２’）ｍが４で割り切れるならば（ｐ−１）が４で割り切れること。
３’）ｓ(floor(p/P))≠１ ただし、Ｐは、ｍの素因数である。
４’）ｗ(floor(p＾ｍ/３))≠１
５’）δ(floor(p＾（３ｍ）/２))≠１
ここで、ｆｌｏｏｒ（ｘ）は床関数であり、ｘを越えない最大の整数を返す関数である。
【０１０８】
また、素数位数トーラスとなる条件として、トーラスＴ６（Ｆpm）の位数はΦ６（ｐm）であり、これが素数となる必要条件は次式が成り立つことである。
【０１０９】
６’）ｍ＝２a×３b
従って、拡大次数決定部１２０は、上記１’）〜６’）までの条件を満たすように、拡大次数ｍを決定している。
【０１１０】
次いで、第１素数探索部１３０が、Ｗ／ｎｍビット以上の素数ｐを探索する（ステップＳ１３）。
【０１１１】
例えば、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１の場合、素数ｐとして、２）の条件を満たす素数を探索する。ｍの候補が複数ある場合にはそれぞれについて実施する。上述の例では，ｍ＝２７，８１，２４３であるため，ｍが３で割り切れるので、素数ｐとして、４ｍで除算した余りが２ｍ＋１となるような素数を探索する。
【０１１２】
また、他の例では、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δの場合、素数ｐとして、１’）および２’）の条件を満たす素数を探索する。ｍの候補が複数ある場合にはそれぞれについて実施する。上述の例では，ｍ＝１８，２４，２７，３２，…であるため、素数ｐとして、ｍが２で割り切れる場合（ｐ−１）が２で割り切れ、ｍが３で割り切れる場合（ｐ−１）が３で割り切れ、ｍが４で割り切れる場合（ｐ−１）が４で割り切れ、かつ、（ｐm−１）が３で割り切れ、かつ、（ｐ3m−１）が２で割り切れるような素数を探索する。
【０１１３】
そして、素数ｐが探索されるまで（ステップＳ１４：Ｎｏ）、上記ステップＳ１２およびＳ１３の処理を繰り返す。
【０１１４】
素数ｐが探索された場合には（ステップＳ１４：Ｙｅｓ）、（９−１）式の条件を満たすべく、第２素数探索部１４０は、Φnm（ｐ）を割り切るＳビット以上の素数ｑを探索する（ステップＳ１５）。
【０１１５】
そして、素数ｑが探索されたら、（９−２）式で示す条件２を満たしているか判断するため、検査部１５０は、ｎｍが素数ｑで割り切れるか否かを判断する（ステップＳ１６）。ｎｍが素数ｑで割り切れる場合には（ステップＳ１６：Ｙｅｓ）、ステップＳ１５の素数ｑの探索を繰り返す。
【０１１６】
一方、ステップＳ１６で、ｎｍが素数ｑで割り切れない場合（ステップＳ１６：Ｎｏ）、安全性判定部１７０は暗号系が安全性ありと判定して、出力部１６０は、（９−２）式の条件２を満足する素数ｑが探索されたと判断して、パラメータ（ｐ，ｑ，ｍ，ｎ）を出力する（ステップＳ１７）。
【０１１７】
ここで、パラメータ生成処理の第１変形例（実施の形態１の変形例１）として、暗号系が定義される素数位数部分群Ｇとして素数位数トーラスＴそのものを用いる場合の処理がある。このような場合には、素数位数トーラスＴの位数が素数位数部分群Ｇの位数と等しくなるので、Φn（ｐm）＝ｑである。従って、この条件の下、条件１と条件２を満たすパラメータを探索する。
【０１１８】
図８は、実施の形態１の変形例１のパラメータ生成処理の手順を示すフローチャートである。図８に示すように、本変形例では、ステップＳ２６の素数ｑの探索において、Φn（ｐm）＝Φnm（ｐ）＝ｑを満たす素数ｑを探索している点が、図７の処理と異なり、他のステップＳ２１〜２４、Ｓ２６，Ｓ７の処理は、図７の処理と同様である。
【０１１９】
また、パラメータ生成処理の第２の変形例（実施の形態１の変形例２）として、（８）式に基づいた条件により素数ｑの探索を行うこともできる。図９は、実施の形態１の変形例２のパラメータ生成処理の手順を示すフローチャートである。本変形例では、代数的トーラスＴの位数について（８）式が成立するので、ｍ~n＝１の場合、Φn（ｐm）＝Φnm（ｐ）となる。このため、ステップＳ３２の拡大体Ｆの拡大次数ｍを決定する際に、ｍ~n＝１という制約を課し、この上で、ステップＳ３５の素数ｑの探索処理において、＝Φnm（ｐ）＝ｑとなる素数ｑを探索している。これにより、変形例２のステップＳ２５におけるΦn（ｐm）＝Φnm（ｐ）の検査を省略することができる。
【０１２０】
また、パラメータ生成処理の第３の変形例（実施の形態１の変形例３）として、次の処理がある。図１０は、実施の形態１の変形例３のパラメータ生成処理の手順を示すフローチャートである。（９−２）式に示す条件２が成立しない場合でも、全てのｄ｜ｎｍ，ｄ＜ｎｍについて（１０）式が成立すれば、パラメータを求めることができる。ここで、ｄはｎｍの約数である。
【０１２１】
このため、本変形例では、ステップＳ４６において、（９−２）式の条件２が成立しない場合、すなわち、ｎｍが素数ｑで割り切れる場合には（ステップＳ４６：Ｙｅｓ）、（１０）式の判断、すなわち、ｎｍの約数ｄについてΦd（ｐ）が割り切れるか否かを判断し（ステップＳ４７）、割り切れない場合には（ステップＳ４７：Ｎｏ）、条件２が成立しない場合でもパラメータ（ｐ、ｑ、ｍ、ｎ）を出力している。一方、割り切れる場合には（ステップＳ４７：Ｙｅｓ）、再度、素数ｑの探索を行う。
【０１２２】
他のステップＳ４１〜Ｓ４５，Ｓ４６，Ｓ４８の処理については、変形例２の処理と同様に行われる。なお、図１０では、ステップＳ４７の処理を変形例２（図９）の処理に組み込んだ例を示したが、これに限定されるものではなく、実施の形態１の図７の処理、変形例２の図８の処理に組み込むように構成してもよい。
【０１２３】
次に、鍵生成装置２００による鍵生成処理について説明する。図１１は、実施の形態１の鍵生成処理の手順を示すフローチャートである。
【０１２４】
まず、乱数生成部２１１は、パラメータ生成装置１００からパラメータ（ｐ、ｑ、ｍ、ｎ）を入力し（ステップＳ５１）、その中の素数位数部分群Ｇの位数ｑを用いて、０＜ｗ＜ｑとなる乱数ｗを生成する（ステップＳ５２）。また、乱数生成部２１１は、素数位数部分群Ｇの位数ｑを用いて、０≦ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２＜ｑとなる乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２を生成する（ステップＳ５３）。
【０１２５】
次に、演算部２１２が、素数位数部分群Ｇの生成元ｇを取得する（ステップＳ５４）。
【０１２６】
次に、演算部２１２は、次の（１１−１）〜（１１−４）式のべき乗計算を行う（ステップＳ５５）。
【０１２７】
【数１１−１】
【０１２８】
そして、出力部２２０は、その計算結果である（ｇ~，ｅ，ｆ，ｈ）を公開鍵として出力し（ステップＳ５６）、また、（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を秘密鍵として出力する（ステップＳ５７）。より具体的には、出力部２２０は、公開鍵を暗号化装置３００に送信し、秘密鍵を復号化装置４００に送信する。
【０１２９】
次に、暗号化装置３００による暗号化処理ついて説明する。図１２は、実施の形態１の暗号化処理の手順を示すフローチャートである。具体的には、図５に示す（Ａ−１）〜（Ａ−５）式に示す算出処理が行われる。
【０１３０】
まず、通信部３０３は、生成元ｇ、公開鍵ｇ~、ｅ、ｆ、ｈと、平文データｍとを入力する（ステップＳ６１）。次に、乱数生成部３１１は、乱数ｒを生成する（ステップＳ６２）。
【０１３１】
次に、演算部３１２、生成元ｇ、公開鍵のうちｇ~、ｈと、乱数ｒとを用いて、べき乗計算ｃ１＝ｇr、ｃ２＝ｇ〜r、ｂ＝ｈrを実行する（ステップＳ６３）。また、演算部３１２は、平文データｍと、算出したｂとを乗算し、ｃ３＝ｍｂを算出する（ステップＳ６４）。
【０１３２】
次に、圧縮処理部３２０は、ｃ１、ｃ２、ｃ３を、圧縮写像により圧縮する（ステップＳ６５）。
【０１３３】
次に、演算部３１２は、ハッシュ関数Ｈへの入力としてｃ１、ｃ２、ｃ３を用いてハッシュ値ｖ＝Ｈ（ｃ１、ｃ２、ｃ３）を算出する（ステップＳ６６）。そして、演算部３１２は、公開鍵のうちｅ、ｆと、乱数ｒと、算出されたハッシュ値ｖとを用いて、べき乗計算ｃ４＝ｅrｆrｖを実行する（ステップＳ６７）。
【０１３４】
次に、圧縮処理部３２０は、ｃ４を、圧縮写像を用いて圧縮する（ステップＳ６８）。最後に、通信部３３０は、圧縮後の（ｃ１、ｃ２、ｃ３、ｃ４）を圧縮された暗号文データ（圧縮暗号文）として出力し（ステップＳ６９）、復号化装置４００に送信する。
【０１３５】
次に、復号化装置４００による復号化処理について説明する。図１３は、実施の形態１の復号化処理の手順を示すフローチャートである。具体的には、図５の（Ｂ−１）〜（Ｂ−６）式の算出処理を行う。
【０１３６】
まず、通信部４３０は、復号の対象となる暗号文データ（圧縮暗号文）を受信することにより入力する（ステップＳ７１）。
【０１３７】
次に、第１判定部４２１は、暗号文データの成分（要素）である圧縮されたｃ１、ｃ２、ｃ３、ｃ４のそれぞれが正しい群の元であるか否か、すなわち、ｃ１、ｃ２、ｃ３、ｃ４それぞれが群Ｇの元となっているか否かを判断する（ステップＳ７２）。具体的には、暗号文の成分を要素とするベクトル表現（ｃ１，ｃ２，ｃ３，ｃ４）の各値が、０からｐ−１までの範囲に入っている場合に、暗号文ｃ１，ｃ２，ｃ３，ｃ４のそれぞれが正しい群の元であると判定することができる。
【０１３８】
暗号文データの成分が正しい群Ｇの元でないと判断された場合は（ステップＳ７２：ＮＯ）、復号処理を終了する。
【０１３９】
暗号文データの成分が正しい群Ｇの元であると判断された場合（ステップＳ７２：ＹＥＳ）、復号処理部４１０は、ハッシュ関数Ｈへの入力としてｃ１、ｃ２、ｃ３を用いてハッシュ値ｖ＝Ｈ（ｃ１、ｃ２、ｃ３）を算出する（ステップＳ７３）。
【０１４０】
次に、伸長処理部４１０は、圧縮された暗号文ｃ１、ｃ２、ｃ３を伸長写像を用いて伸長する（ステップＳ７４）。また、演算部４２３は、ハッシュ値ｖと、伸長後の暗号文ｃ１、ｃ２と、秘密鍵のうちｘ１、ｘ２、ｙ１、ｙ２とを用いて、べき乗計算ｃ＝ｃ１（ｘ１＋ｙ１ｖ）ｃ２（ｘ２＋ｙ２ｖ）を実行する（ステップＳ７５）。そして、演算部４２３は、べき乗計算により算出されたｃを圧縮する（ステップＳ７６）。また、伸長処理部４１０は、圧縮された暗号文ｃ４を伸長する。
【０１４１】
次に、第２判定部４２２は、ｃと入力された暗号文データの成分のうちｃ４とが一致するか否かを判断する（ステップＳ７７）。具体的には、暗号文のベクトル表現における各値が一致した場合に、ｃと入力された暗号文データの成分ｃ４とが一致すると判定することができる。
【０１４２】
そして、両者が一致しない場合は（ステップＳ７７：Ｎｏ）、復号処理を終了する。一方、両者が一致する場合は（ステップＳ７７：Ｙｅｓ）、演算部４２３は、ｃ１、ｃ２と、秘密鍵のうちｚ１、ｚ２とを用いて、べき乗計算ｂ＝ｃ１ｚ１ｃ２ｚ２を実行する（ステップＳ７８）。
【０１４３】
次に、演算部４２３は、ｃ３と、算出されたｂとを用いて、平文ｍ＝ｃ３ｂ−１を算出する（ステップＳ７９）。そして、圧縮処理部４５０によって平文ｍを圧縮し（ステップＳ８０）、圧縮された平文ｍを出力する（ステップＳ８１）。
【０１４４】
以上説明したように、本実施の形態によれば、パラメータ生成装置１００で、（９−１）式および（９−２）式を満たすように、パラメータ（ｐ、ｑ，ｍ、ｎ）を生成し、このパラメータを用いて、鍵生成、暗号化処理、復号化処理を行っているので、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができ、これにより、より安全性のある暗号化処理を実現することができる。
【０１４５】
ここで、鍵生成処理で生成し、復号化処理で使用する秘密鍵としては、上述した（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）に限定されるものではない。例えば、秘密鍵の個数を（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）よりも少なく構成してもよい。
【０１４６】
このような場合の鍵生成処理の変形例（実施の形態１の変形例４）として、鍵生成装置２００において生成する秘密鍵の個数が４個とする場合の処理がある。図１４は、実施の形態１の変形例４の鍵生成処理の手順を示すフローチャートである。この変形例では、実施の形態１の鍵生成処理（図１１）と同様に、パラメータ（ｐ，ｑ，ｍ，ｎ）の入力（ステップＳ５１）、乱数ｗの生成（ステップＳ５２）の後、乱数生成部２１１は、素数位数部分群Ｇの位数ｑを用いて、０≦ｘ，ｙ，ｚ＜ｑとなる乱数ｘ，ｙ，ｚを生成する（ステップＳ５３ｂ）。
【０１４７】
次に、演算部２１２は、次の（１１−５）〜（１１−８）式のべき乗計算を行う（ステップＳ５５ｂ）。
【０１４８】
【数１１−２】
【０１４９】
そして、出力部２２０は、その計算結果である（ｇ~，ｅ，ｆ，ｈ）を公開鍵として出力し（ステップＳ５６）、また、（ｗ，ｘ，ｙ，ｚ）を秘密鍵として出力する（ステップＳ５７ｂ）。
【０１５０】
また、復号化処理の変形例（実施の形態１の変形例５）として、上記変形例４の鍵生成処理により生成された４個の秘密鍵を用いる場合の処理がある。図１５は、実施の形態１の変形例５の復号化処理の手順を示すフローチャートである。
【０１５１】
圧縮暗号文の入力から圧縮暗号文ｃ１，ｃ２，ｃ３の伸長までの処理（ステップＳ７１〜Ｓ７４）については、図１３で示した実施の形態１の復号化処理と同様に行われる。
【０１５２】
本変形例では、ステップＳ７４ｂにおいて圧縮暗号文ｃ１，ｃ３を伸長したら、演算部４２３は、ハッシュ値ｖと、伸長後の暗号文ｃ１と、秘密鍵のうちｗ、ｘ、ｙとを用いて、べき乗計算ｔ１＝ｃ１ｗ，ｔ２＝ｃ１（ｘ＋ｙｖ）を実行する（ステップＳ７５ｂ）。そして、演算部４２３は、算出されたｔ１，ｔ２を圧縮する（ステップＳ７６ｂ）。
【０１５３】
次に、第２判定部４２２は、ｔ１と、入力された暗号文データの成分のうちｃ２とが一致するか否か、および、ｔ２と、入力された暗号文データの成分のうちｃ４とが一致するか否かを判断する（ステップＳ７７ｂ）。
【０１５４】
そして、ｔ１とｃ２が一致しない、あるいはｔ２とｃ４とが一致しない場合には（ステップＳ７７ｂ：Ｎｏ）、復号処理を終了する。一方、ｔ１とｃ２が一致し、かつｔ２とｃ４とが一致する場合には（ステップＳ７７ｂ：Ｙｅｓ）、演算部４２３は、ｃ１と、秘密鍵のうちのｚとを用いて、べき乗計算ｂ＝ｃ１ｚを実行する（ステップＳ７８ｂ）。
【０１５５】
この後の平文ｍの圧縮（ステップＳ８０）、平文ｍの出力（ステップＳ８１）は、図１３で示した実施の形態１の復号化処理と同様に行われる。
【０１５６】
なお、本変形例では、秘密鍵の個数が４個の場合を例にあげて説明したが、秘密鍵の個数はこれに限定されるものではない。
【０１５７】
（実施の形態２）
実施の形態２の暗号処理システムは、鍵生成装置において生成した公開鍵を圧縮するものである。図１６は、実施の形態２にかかる暗号処理システムのシステム構成を示すブロック図である。図１６に示すように、実施の形態２にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置１４２０と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置１４３０を備え、受信装置４０は復号化装置４００を備えている。
【０１５８】
本実施の形態において、パラメータ装置１００、復号化装置４００は、実施の形態１と同様の機能、構成を有している。
【０１５９】
鍵生成装置１４２０は、パラメータ生成装置１００によって生成されたパラメータ（公開情報）を用いて、公開鍵と、公開鍵に対応する秘密鍵とを生成し、生成された公開鍵を圧縮して出力する。
【０１６０】
図１７は、実施の形態２の鍵生成装置１４２０の機能的構成を示すブロック図である。本実施の形態の鍵生成装置１４２０は、図１７に示すように、鍵計算部２１０と、圧縮処理部１４２１と、通信部２２０とを備えている。鍵計算部２１０と通信部２２０は、実施の形態１の鍵生成装置２００と同様の機能および構成を有している。
【０１６１】
圧縮処理部１４２１は、鍵計算部２１０で生成された公開鍵を、標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算により、トーラス圧縮する。圧縮された公開鍵は、通信部２２０によって暗号化装置１４３０に送信される。
【０１６２】
図１８は、暗号化装置１４３０の機能的構成を示すブロック図である。本実施の形態の暗号化装置１４３０は、暗号化処理部３１０と、圧縮処理部３２０と、伸長処理部１４３１と、通信部３３０と、公開鍵記憶部３４０とを備えている。ここで、暗号化処理部３１０、圧縮処理部３２０、通信部３３０、公開鍵記憶部３４０については実施の形態１の暗号化装置３００と同様の機能および構成を有している。
【０１６３】
伸長処理部１４３１は、通信部３３０が鍵生成装置１４２０から受信したトーラス圧縮された公開鍵を、標数ｐおよび拡大次数mの拡大体またはその部分体上の演算により、トーラス伸長する。
【０１６４】
次に、以上のように構成された本実施の形態の鍵生成処理について説明する。図１９は、実施の形態２の鍵生成処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力から生成元ｇに対するべき乗計算までの処理（ステップＳ９１〜Ｓ９５）については、実施の形態１におけるステップＳ５１からＳ５５までの処理と同様に行われる。
【０１６５】
べき乗演算が終了したら、算出されたｇ~，ｅ，ｆ，ｈを、圧縮処理部１４２１により圧縮写像を用いて標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算によりトーラス圧縮する（ステップＳ９６）。
【０１６６】
そして、通信部２２０は、圧縮された（ｇ~，ｅ，ｆ，ｈ）を圧縮公開鍵として出力し（ステップＳ９７）、また、（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）を秘密鍵として出力する（ステップＳ９８）。より具体的には、出力部２２０は、公開鍵を暗号化装置１４３０に送信し、秘密鍵を復号化装置４００に送信する。
【０１６７】
次に、暗号化装置１４３０による暗号化処理について説明する。図２０は、実施の形態２の暗号化処理の手順を示すフローチャートである。
【０１６８】
まず、通信部３０３が、生成元ｇ、圧縮公開鍵（ｇ~、ｅ、ｆ、ｈ）と、平文データｍとを受信（入力）する（ステップＳ１０１）。次に、伸長処理部１４３１は、受信した圧縮公開鍵（ｇ~、ｅ、ｆ、ｈ）を、伸長写像を用いて標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上の演算によりトーラス伸長する（ステップＳ１０２）。
【０１６９】
これ以降、伸長された公開鍵を用いた暗号文の生成処理については、実施の形態１の暗号化処理におけるステップＳ６２からＳ６９までの処理と同様に行われる。
【０１７０】
このように実施の形態２では、鍵生成の際の圧縮処理、暗号化処理の際の伸長処理における演算を、標数pおよび拡大次数ｍの拡大体Ｆｐmまたはその部分体上で行っている。このため、本実施の形態では、拡大体上の代数的トーラスを用いた公開鍵暗号方式において適切なパラメータを生成することができ、これにより、より安全性のある暗号化処理を実現することができる。
【０１７１】
（実施の形態３）
実施の形態３の暗号処理システムは、パラメータ生成装置において、パラメータに対してトーラス上離散対数問題における効率的な計算法が有効な場合に、当該パラメータの生成を回避するものである。
【０１７２】
図２１は、実施の形態３にかかる暗号処理システムのシステム構成を示すブロック図である。図２１に示すように、実施の形態３にかかる暗号処理システムは、パラメータ生成装置１９１０と、鍵生成装置２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【０１７３】
本実施の形態において、鍵生成装置２００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１と同様の機能、構成を有している。
【０１７４】
図２２は、実施の形態３のパラメータ生成装置１９１０の機能的構成を示すブロック図である。本実施の形態のパラメータ生成装置１９１０は、図２２に示すように、入力受付部１１０と、拡大次数決定部１２０と、第１素数探索部１３０と、第２素数探索部１４０と、検査部１５０と、安全性判定部１７０と、有効性判定部１９１１と、出力部１６０とを主に備えている。ここで、入力受付部１１０、拡大次数決定部１２０、第１素数探索部１３０、第２素数探索部１４０、検査部１５０、安全性判定部１７０、出力部１６０については、実施の形態１のパラメータ生成装置１００と同様の機能および構成を有している。
【０１７５】
有効性判定部１９１１は、パラメータ（ｐ，ｑ，ｍ，ｎ）に対し、トーラス上離散対数問題における効率的な計算法が有効か否かを判定する。以下、かかる判定について詳細に説明する。
【０１７６】
トーラス上離散対数問題の解法にＧｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法がある。このＧｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法については、文献「Ｒ．Ｇｒａｎｇｅｒ ａｎｄ Ｆ． Ｖｅｒｃａｕｔｅｒｅｎ，“Ｏｎ ｔｈｅ ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ ｐｒｏｂｌｅｍ ｏｎ Ａｌｇｅｂｒａｉｃ Ｔｏｒｉ”， ＣＲＹＰＴＯ ２００５， ＬＮＣＳ ３６２１，ｐｐ．６６−８５，２００５．」に開示されている。
【０１７７】
Ｇｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法により効率的な解法を行うことができるパラメータの生成を回避する必要がある。Ｇｒａｎｇｅｒ−Ｖｅｒｃａｕｔｅｒｅｎ法では、Ｔ２アルゴリズムとＴ６アルゴリズムの２種類のアルゴリズムが提案されている。
【０１７８】
Ｔ２アルゴリズムの計算量は、（１２−１）式、Ｔ６アルゴリズムの計算量は（１２−２）式で算出される量になると見積もられている。
【０１７９】
【数１２】
【０１８０】
ここで、Ｔ２アルゴリズムはｎ＝２であってｍ！≒ｐ、すなわち、（１３−１）式を満たす場合に、準指数時間になると理論的に見積もられている。一方、Ｔ６アルゴリズムはｎ＝６であって（２ｍ）！２12m≒ｐ、すなわち、（１３−２）式のとき準指数時間になると実験により見積もられている。
【０１８１】
【数１３】
【０１８２】
従って、（１３−１）式、あるいは（１３−２）式を満たすようなパラメータの生成を回避する必要がある。
【０１８３】
本実施の形態の有効性判定部１９１１では、パラメータ（ｐ，ｑ，ｍ，ｎ）が、（１３−１）式または（１３−２）式の条件を満たすか否かを調べることにより、当該パラメータに対してトーラス上離散対数問題における効率的な計算法が有効か否かを判定する。
【０１８４】
ここで、有効性判定部１９１１では、（１３−１）式、（１３−２）式のそれぞれにおいて、右辺の値と左辺の値とが近似しているか否かは、右辺の値と左辺の値との差が所定の範囲内にあるか否かを判断することにより判定する。
【０１８５】
また、Ｔ２アルゴリズムは （ｐ，ｑ，ｍ，ｎ（＝６））に対して（ｐ，ｑ，ｍ’（＝３ｍ），ｎ’（＝２））として適用できるので、有効性判定部１９１１は、ｎ＝６の場合には、かかる適用を行って、（１３−１）式、（１３−２）式の判定を行っている。
【０１８６】
また、本実施の形態では、有効性判定部１９１１は、すべてのパラメータ（ｐ、ｑ、ｍ、ｎ）生成された場合に、（１３−１）式、（１３−２）式の判定を行って、（１３−１）式、（１３−２）式を満たす場合には、再度、パラメータ（ｐ、ｑ、ｍ、ｎ）の決定をやり直している。
【０１８７】
次に、本実施の形態のパラメータ生成処理について説明する。図２３は、実施の形態３のパラメータ生成処理の手順を示すフローチャートである。（ｎ，Ｗ，Ｓ）の入力受付けからパラメータ（ｐ，ｑ，ｍ，ｎ）の出力までの処理（ステップＳ１２１〜Ｓ１２７）については、実施の形態１のパラメータ生成処理と同様に行われる。
【０１８８】
本実施の形態では、ステップＳ１２７において、パラメータ（ｐ，ｑ，ｍ，ｎ）が出力された場合、さらに、このパラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式または（１３−２）式の条件を満たすか否かを判定する（ステップＳ１２８）。
【０１８９】
そして、パラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式または（１３−２）式の条件を満たす場合には（ステップＳ１２８：Ｙｅｓ）、かかるパラメータはトーラス上離散対数問題における効率的な計算法が有効なパラメータであるため、これらを除外すべく、再度、ステップＳ１２２からの処理を繰り返す。
【０１９０】
ステップＳ１２８において、パラメータ（ｐ，ｑ，ｍ，ｎ）が（１３−１）式および（１３−２）式の条件を満たさない場合には（ステップＳ１２８：Ｎｏ）、かかるパラメータはトーラス上離散対数問題における効率的な計算法が有効でないパラメータであるため、これらのパラメータを以降の暗号処理に用いるべく、パラメータ（ｐ，ｑ，ｍ，ｎ）を出力する（ステップＳ１２９）。
【０１９１】
このように本実施の形態では、パラメータ生成処理の際に、トーラス上離散対数問題における効率的な計算法が有効であるパラメータを除外しているので、より安全で適切なパラメータ生成を行うことができる。
【０１９２】
ここで、(１３−１)式、（１３−２）式の判定のタイミングについて、他の例を考える。(１３−１)式、（１３−２）式を見てみると、この２つの条件式は、素数ｑに依存しないことがわかる。従って、実施の形態３の変形例１では、素数ｐの探索が終了した時点で、有効性判定部１９１１により、素数ｑをのぞいたパラメータｍ、ｐ、ｎが(１３−１)式、または（１３−２）式の条件を満たすか否か判定している。これにより、パラメータ生成の処理時間の短縮化を図ることができる。
【０１９３】
図２４は、実施の形態３の変形例１のパラメータ生成処理の手順を示すフローチャートである。図２４に示すように、第１素数探索部１３０で素数ｐが探索された場合に（ステップＳ１４４：Ｙｅｓ）、有効性判定部１９１１により、ステップＳ１４２で決定された拡大次数ｍ、探索された素数ｐと、ｎとを用いて、（１３−１）式または（１３−２）式の条件の判断を行う（ステップＳ１４５）。そして、（１３−１）式または（１３−２）式の条件が成立する場合には（ステップＳ１４５：Ｙｅｓ）、ステップＳ１４２へ戻り、再度、ｍの決定、ｐの探索を繰り返す。
【０１９４】
一方、（１３−１）式または（１３−２）式の条件が成立しない場合には（ステップＳ１４５：Ｎｏ）、素数ｑの探索を行う。これ以降の処理は、実施の形態１のパラメータ生成処理と同様に行われる。
【０１９５】
実施の形態３の変形例２では、素数ｐを探索する際に、有効性判定部１９１１は、（１３−１）式または（１３−２）式の条件を満たす素数ｐの範囲を決定し、第１素数探索部１３０でこの範囲で素数ｐの探索を行っている。
【０１９６】
図２５は、実施の形態３の変形例２のパラメータ生成処理の手順を示すフローチャートである。本変形例では、実施の形態１の変形例２のパラメータ生成処理に上記処理を追加している。すなわち、ｍ~n＝１となるｍを決定したら（ステップＳ１６２）、有効性判定部１９１１は、（１３−１)式または（１３−２）式の条件が成立する素数ｐの範囲を決定する（ステップＳ１６３）。そして、第１素数探索部１３０は、Ｗ／ｎｍビット以上で、かつステップＳ１６２で決定された範囲で素数ｐを探索する（ステップＳ１６４）。これ以降の処理については、実施の形態１の変形例２のパラメータ生成処理と同様である。
【０１９７】
実施の形態３の変形例３では、素数ｐを探索する際に、拡大次数決定部１２０は、（１３−１）式または（１３−２）式の条件を満たすｍを決定している。
【０１９８】
図２６は、実施の形態３の変形例３のパラメータ生成処理の手順を示すフローチャートである。入力受付部１１０が（ｎ，Ｗ，Ｓ）の入力を受け付ける（ステップＳ１８１）。そして、有効性判定部１９１１は、（１３−１）式、（１３−２）式の条件が成立しないｍの範囲を定め、拡大次数決定部１２０は、この範囲で拡大次数ｍを決定する（ステップＳ１８２）。
【０１９９】
例えば、Ｔ２アルゴリズムについて（１４−１）式、Ｔ６アルゴリズムについて（１４−２）式となるｍを避ける。
【０２００】
【数１４】
【０２０１】
例えば、右辺と左辺に１０倍以上の差があれば採用する。ｌｏｇ（ｐ）の下限はＷ／ｎｍであるから（１４−１）式と（１４−２）式の右辺はＷ／ｎｍとして良い。実施の形態１で説明したように、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2＋１のとき、これらの多項式がそれぞれＦp、Ｆpm、Ｆp3m上で既約である十分条件のうち、１）と５）の条件より、ｍ＝３eであるから、ｍ＝３，９，２７，８１，２４３，７２９，・・・について、Ｗ／ｎｍ，３ｍ×ｌｏｇ（３ｍ），２ｍ×ｌｏｇ（ｍ）＋１２ｍを計算する。さらに、（１４−１）式と（１４−２）式の条件を回避すると、ｍ＝２７，８１，２４３が得られる。７２９以上のｍについてはＷ／ｎｍ＜１となるので有限体のサイズ６ｍ×ｌｏｇ（ｐ）がＷ程度となるｐは存在しないので対象外とする。
【０２０２】
他の例では、実施の形態１で説明したように、ｍ次、３次、２次拡大の法多項式がそれぞれｚm−ｓ、ｙ3−ｗ、ｘ2−δのとき、これらの多項式がそれぞれＦｐ、Ｆｐm、Ｆｐ3m上で既約である必要十分条件のうち、６‘）の条件より、ｍ＝２ａ３ｂであるから、（１４−１）式と（１４−２）式の条件を回避すると、１６以下が除外される。３８４以上のｍについてはＷ／ｎｍ＜１となるので有限体のサイズ６ｍ×ｌｏｇ（ｐ）がＷ程度となるｐは存在しないので対象外とする。
【０２０３】
（実施の形態４）
実施の形態４の暗号処理システムでは、パラメータ生成装置１００で生成されたパラメータの安全性を判定する安全性判定装置を備えている。
【０２０４】
図２７は、実施の形態４にかかる暗号処理システムのシステム構成を示すブロック図である。図２７に示すように、実施の形態４にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置２００と、安全性判定装置２４００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置４００を備えている。
【０２０５】
本実施の形態において、パラメータ生成装置１００、鍵生成装置２００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１と同様の機能、構成を有している。
【０２０６】
図２８は、安全性判定装置２４００の機能的構成を示すブロック図である。本実施の形態の安全性判定装置２４００は、第１検査部２４１０と、第２検査部２４２０と、判定部２４３０と、通信部２４５０と、記憶部２４４０とを主に備えている。
【０２０７】
素数位数ｑの群が標数ｐの拡大体に埋め込まれるとき、最小の拡大次数をｏｒｄ（ｑ，ｐ）と表すと、パラメータが満たすべき条件はｏｒｄ（ｑ，ｐ）＝ｎｍと書き換えられる。この条件をパラメータが満たしているかどうかについては、パラメータ（ｐ，ｑ，ｍ，ｎ）が上述した（９−１）式と（９−２）式の２つの条件を満たしているかを判断する。
【０２０８】
代数的トーラスの部分トーラスがいくつかあるとき、暗号に使う部分群の位数はｑで固定しておくとする。(９−１）式の条件１は、一番大きな拡大体に対応する（その部分体には包含されない）部分トーラスに含まれる部分群を暗号に使うことを意味する。（９−２）式の条件２は、暗号に使う部分群が、より小さな拡大体と対応する部分トーラスには含まれないことを意味する。すなわち、（９−２）式の条件２は、暗号に使う部分群は、部分トーラスのうち、ただひとつのトーラスに含まれることを意味する。
【０２０９】
従って、第１検査部２４１０は、パラメータが上述した（９−１）式を満たすか否かを判断して円分多項式Φnm（ｐ）がｑで割り切れるか否かを判断することにより、素数位数部分群Ｇが代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるか否かを検査する。
【０２１０】
第２検査部２４２０は、パラメータが上述した（９−２）式を満たすか否かを判断して乗算値ｎｍがｑで割り切れるか否かを判断することにより、素数位数部分群Ｇが代数的トーラスＴの部分群のうち、唯一の部分群に含まれるかを検査する。
【０２１１】
判定部２４３０は、第１検査部２４１０の検査結果が肯定的であり、かつ、第２検査部によ２４２０る検査結果が肯定的である場合に、パラメータ（ｐ，ｑ，ｍ，ｎ）は標数ｐ、拡大次数ｎｍの拡大体と同等の安全性を有すると判定する。
【０２１２】
通信部２４５０は、パラメータ（ｐ，ｑ，ｍ，ｎ）を受信し、また安全性の判定結果を送信する。
【０２１３】
記憶部２４４０は、判定結果などを一時的に保存する記憶媒体である。
【０２１４】
次に以上のように構成された安全性判定装置２４００による安全性判定処理について説明する。図２９は、実施の形態４の安全性判定処理の手順を示すフローチャートである。
【０２１５】
まず、通信部２４５０が、パラメータ生成装置１００で生成されたパラメータ（ｐ、ｑ、ｍ、ｎ）を受信することより受け付ける（ステップＳ２０１）。次に検査部２４１０は、円分多項式Φnm（ｐ）がｑで割り切れるか否かを調べる（ステップＳ２０２）。そして、割り切れない場合には（ステップＳ２０２：Ｎｏ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnm（標数ｐ、拡大次数ｎｍの拡大体）と同等の安全性がないと判定し（ステップＳ２０６）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２０７）。
【０２１６】
一方、ステップＳ２０２で、円分多項式Φnm（ｐ）がｑで割り切れる場合には（ステップＳ２０２：Ｙｅｓ）、第２検査部２４２０は、ｎｍがｑで割り切れるか否かを調べる（ステップＳ２０３）。そして、ｎｍがｑで割り切れた場合には（ステップＳ２０３：Ｙｅｓ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性がないと判定し（ステップＳ２０６）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２０７）。
【０２１７】
一方、ステップＳ２０３で、ｎｍがｑで割り切れない場合には（ステップＳ２０３：Ｎｏ）、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性があると判定し（ステップＳ２０４）、通信部２４５０は、パラメータ（ｐ、ｑ、ｍ、ｎ）の出力を行う（ステップＳ２０５）。
【０２１８】
このように実施の形態４では、得られたパラメータが（９−１）式、（９−２）式の条件を満たすか否かを判定しているので、安全性の低下を未然に防止することが可能となる。
【０２１９】
ここで、（９−２）式で示す条件２が成立しない場合でも、すべてのｄ｜ｎｍ，ｄ＜ｎｍについて、（１０）式が成立すれば、パラメータは安全性を有することになる。
【０２２０】
図３０は、実施の形態４の変形例１の安全性判定処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力受付け（ステップＳ２２１）、円分多項式Φnm（ｐ）がｑで割り切れるか否かの判断（ステップＳ２２２）およびｎｍがｑで割り切れるか否かの判断（ステップＳ２２３）は、実施の形態４における図２９の処理（ステップＳ２０１，Ｓ２０２，Ｓ２０３）と同様に行われる。本変形例では、ステップＳ２２３において、ｎｍがｑで割り切れ、（９−２）式の条件２を満たさない場合でも（ステップＳ２２３：Ｙｅｓ）、すべてのｄ｜ｎｍ，ｄ＜ｎｍについて、（１０）式が成立するか否かを調べる。すなわち、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるか否かを調べる（ステップＳ２２６）。そして、割り切れない場合には（ステップＳ２２６：Ｎｏ）、（１０）式を満たすと判断して、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性があると判定し（ステップＳ２２４）、通信部２４５０は、パラメータ（ｐ、ｑ、ｍ、ｎ）の出力を行う（ステップＳ２２５）。
【０２２１】
一方、ステップＳ２２６において、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２２６：Ｙｅｓ）、（１０）式を満たさないと判断して、判定部２４３０は、パラメータ（ｐ、ｑ、ｍ、ｎ）が拡大体Ｆｐnmと同等の安全性がないと判定し（ステップＳ２２７）、通信部２４５０は、安定性なしの出力を行う（ステップＳ２２８）。
【０２２２】
また、実施の形態４の変形例２として、（９−１）式で示す条件１、（９−２）式で示す条件２が成立しない場合でも、暗号系が定義されている素数位数部分群Ｇがどの拡大体に包含されるかを調べ、どの程度安全性が低下するかを出力しても良い。
【０２２３】
図３１は、実施の形態４の変形例２の安全性判定処理の手順を示すフローチャートである。パラメータ（ｐ，ｑ，ｍ，ｎ）の入力（ステップＳ２４１）および円分多項式Φnm（ｐ）がｑで割り切れるか否かの判断（ステップＳ２４２）、ｎｍがｑで割り切れるか否かの判断（ステップＳ２４３）およびｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるか否かの判断（ステップＳ２４４）は、実施の形態４の変形例１における図３０の処理（ステップＳ２２１，Ｓ２２２，Ｓ２２３，Ｓ２２４）と同様に行われる。
【０２２４】
本変形例では、ステップＳ２４２において、円分多項式Φnm（ｐ）がｑで割り切れず（ステップＳ２４２：Ｎｏ）、（９−１）式の条件１を満たさない場合には、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるかどうか調べる（ステップＳ２４７）。そして、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２４７：Ｙｅｓ）、（１０）式を満たさないと判断して、割り切れた最小のｄを取得して（ステップＳ２４８）、拡大体Ｆｐdと同等の安全性があると判定する（ステップＳ２４９）。
【０２２５】
一方、ステップＳ２４７において、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れない場合には（ステップＳ２４７：Ｎｏ）、判定部２４３０は安全性は不明であると判定し（ステップＳ２５１）、通信部２４５０は安全性が不明である旨を出力する（ステップＳ２５３）。
【０２２６】
また、ステップＳ２４３において、ｎｍがｑで割り切れ、（９−２）式の条件２を満たさない場合でも（ステップＳ２４３：Ｙｅｓ）、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れるかどうか調べる（ステップＳ２４４）。そして、ｎｍの約数ｄについてΦd（ｐ）がｑで割り切れる場合には（ステップＳ２４４：Ｙｅｓ）、（１０）式を満たさないと判断して、割り切れた最小のｄを取得して（ステップＳ２４８）、拡大体Ｆｐdと同等の安全性があると判定する（ステップＳ２４９）。これにより、安全性のレベルを判定することが可能となる。
【０２２７】
一方、ステップＳ２４４において、ｎｍがｑで割り切れない場合には（ステップＳ２４４：Ｎｏ）、実施の形態４の変形例１における図３０と同様の処理（ステップＳ２２４，Ｓ２２５）が行われる（ステップＳ２４５，Ｓ２４６）。
【０２２８】
（実施の形態５）
実施の形態５にかかる暗号処理システムは、鍵生成装置における公開鍵計算部の処理を効率化するものである。図３２は、実施の形態５にかかる暗号処理システムのシステム構成を示すブロック図である。図３２に示すように、実施の形態５にかかる暗号処理システムは、パラメータ生成装置１００と、鍵生成装置３２００と、送信装置３０と、受信装置４０とを含んでいる。送信装置３０は暗号化装置３００を備え、受信装置４０は復号化装置３００を備えている。
【０２２９】
本実施の形態において、パラメータ生成装置１００、送信装置３０（すなわち、暗号化装置３００）、受信装置４０（すなわち、復号化装置４００）については、実施の形態１または２と同様の機能、構成を有している。
【０２３０】
図３３は、実施の形態５の鍵生成装置３２００の機能的構成を示すブロック図である。本実施の形態の鍵生成装置３２００は、図３３に示すように、鍵計算部３２１０と、通信部２２０とを主に備えている。ここで、通信部２２０の機能は、実施の形態１と同様である。
【０２３１】
鍵計算部３２１０は、実施の形態１と同様に、パラメータ生成装置１００で生成されたパラメータ（ｐ，ｑ，ｍ，ｎ）を入力して公開鍵や秘密鍵を生成する。鍵計算部３２１０は、乱数生成部２１１と、伸長処理部３２３２と、演算部３２１２とを備えている。乱数生成部２１１の機能は、実施の形態１と同様である。
【０２３２】
演算部３２１２は、実施の形態１と同様に秘密鍵を生成する他、素数位数部分群Ｇの生成元ｇを取得する。このとき、演算部３２１２は、生成元ｇを圧縮された表現で取得する。生成元ｇを生成する場合、圧縮した表現とすると素数位数部分群Ｇに入らない生成元を生成する確率が下がり、生成元の生成効率を向上させることができる。特に、素数位数部分群Ｇが素数位数の代数的トーラスＴの場合は、代数的トーラスＴが定義される有限体Ｆｐmの要素を生成すれば、常に素数位数部分群Ｇに入る生成元ｇを生成することができる。また、生成元ｇをメモリに記憶しておき、メモリから生成元ｇを読み出す形態においても、生成元ｇを圧縮した表現でメモリ等に記憶する場合の方が、圧縮されていない生成元ｇを記憶する場合に比べて、メモリの記憶容量を削減することができるという利点がある。
【０２３３】
伸長処理部３２３２は、演算部３２１２により取得した圧縮した表現の生成元ｇを、演算部３２１２によるべき乗または乗算を行う前に、トーラス伸長する。演算部３２１２は、伸長処理部３２３２によりトーラス伸長された生成元ｇに対して、実施の形態１と同様に、標数pおよび拡大次数mの拡大体またはその部分体上で、生成した乱数を用いてべき乗演算および乗算を行い公開鍵を求める。
【０２３４】
次に、鍵生成装置３２００による鍵生成処理について説明する。図３４は、実施の形態５の鍵生成処理の手順を示すフローチャートである。
【０２３５】
まず、パラメータ（ｐ、ｑ、ｍ、ｎ）の入力から乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２の生成までの処理（ステップＳ２６１〜Ｓ２６３）は、実施の形態１における鍵生成処理（ステップＳ５１〜Ｓ５３）と同様に行われる。
【０２３６】
乱数ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２が生成されたら、演算部３２１２が、素数位数部分群Ｇの圧縮された表現の生成元ｇを取得する（ステップＳ２６４）。そして、べき乗計算または乗算を行う前に、伸長処理部３２３２は、圧縮された表現の生成元ｇをトーラス伸長する（ステップＳ２６５）。
【０２３７】
これ以降の公開鍵の生成および出力、秘密鍵の出力の処理（ステップＳ２６６〜Ｓ２６８）は、実施の形態１における鍵生成処理（ステップＳ５５〜Ｓ５７）と同様に行われる。
このように実施の形態５では、鍵生成装置３２００において、圧縮された表現の生成元ｇを取得して、伸長処理部３２３２によって取得した生成元ｇ（圧縮表現）のトーラス伸長を行っているので、生成元ｇの生成時にその位数をチェックしたり、代数的トーラスの要素を伸長した表現で記憶しなければならない伸長処理部３２３２のない鍵生成装置に比べて、生成元ｇの取得にかかる処理を効率的に行うことができる。
【０２３８】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置は、ＣＰＵなどの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭなどの記憶装置と、ＨＤＤ、ＣＤドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０２３９】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０２４０】
また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０２４１】
また、実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０２４２】
実施の形態１〜５のパラメータ生成装置、鍵生成装置、暗号化装置、復号化装置で実行される各プログラムは、上述した各部を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体から各プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上記各部が主記憶装置上に生成されるようになっている。
【０２４３】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【図面の簡単な説明】
【０２４４】
【図１】実施の形態１にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２】実施の形態１のパラメータ生成装置の機能的構成を示すブロック図である。
【図３】実施の形態１の鍵生成装置の機能的構成を示すブロック図である。
【図４】実施の形態１の暗号化装置の機能的構成を示すブロック図である。
【図５】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。
【図６】実施の形態１の復号化装置の機能的構成を示すブロック図である。
【図７】実施の形態１のパラメータ処理の手順を示すフローチャートである。
【図８】実施の形態１の変形例１のパラメータ生成処理の手順を示すフローチャートである。
【図９】実施の形態１の変形例２のパラメータ生成処理の手順を示すフローチャートである。
【図１０】実施の形態１の変形例３のパラメータ生成処理の手順を示すフローチャートである。
【図１１】実施の形態１の鍵生成処理の手順を示すフローチャートである。
【図１２】実施の形態１の暗号化処理の手順を示すフローチャートである。
【図１３】実施の形態１の復号化処理の手順を示すフローチャートである。
【図１４】実施の形態１の変形例４の鍵生成処理の手順を示すフローチャートである。
【図１５】実施の形態１の変形例５の復号化処理の手順を示すフローチャートである。
【図１６】実施の形態２にかかる暗号処理システムのシステム構成を示すブロック図である。
【図１７】実施の形態２の鍵生成装置の機能的構成を示すブロック図である。
【図１８】暗号化装置１４３０の機能的構成を示すブロック図である。
【図１９】実施の形態２の鍵生成処理の手順を示すフローチャートである。
【図２０】実施の形態２の暗号化処理の手順を示すフローチャートである。
【図２１】実施の形態３にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２２】実施の形態３のパラメータ生成装置の機能的構成を示すブロック図である。
【図２３】実施の形態３のパラメータ生成処理の手順を示すフローチャートである。
【図２４】実施の形態３の変形例１のパラメータ生成処理の手順を示すフローチャートである。
【図２５】実施の形態３の変形例２のパラメータ生成処理の手順を示すフローチャートである。
【図２６】実施の形態３の変形例３のパラメータ生成処理の手順を示すフローチャートである。
【図２７】実施の形態４にかかる暗号処理システムのシステム構成を示すブロック図である。
【図２８】安全性判定装置の機能的構成を示すブロック図である。
【図２９】実施の形態４の安全性判定処理の手順を示すフローチャートである。
【図３０】実施の形態４の変形例１の安全性判定処理の手順を示すフローチャートである。
【図３１】実施の形態４の変形例２の安全性判定処理の手順を示すフローチャートである。
【図３２】実施の形態５にかかる暗号処理システムのシステム構成を示すブロック図である。
【図３３】実施の形態５の鍵生成装置の機能的構成を示すブロック図である。
【図３４】実施の形態５の鍵生成処理の手順を示すフローチャートである。
【符号の説明】
【０２４５】
３０ 送信装置
４０ 受信装置
１００，１９１０ パラメータ生成装置
１１０ 入力受付部
１２０ 拡大次数決定部
１３０ 第１素数探索部
１４０ 第２素数探索部
１５０ 検査部
１６０ 出力部
１７０ 安全性判定部
２００，１４２０ 鍵生成装置
２１０ 鍵計算部
２１１，３１１ 乱数生成部
２１２，３１２，４２３ 演算部
２２０，３３０，４３０，２４５０ 通信部
３００、１４３０ 暗号化装置
３１０ 暗号化処理部
３２０，４５０，１４２１ 圧縮処理部
３４０ 公開鍵記憶部
４００ 復号化装置
４１０，１４３１ 伸長処理部
４２０ 復号化処理部
４２１ 第１判定部
４２２ 第２判定部
４４０ 秘密鍵記憶部
１９１１ 有効性判定部
２４００ 安全性判定装置
２４１０ 第１検査部
２４２０ 第２検査部
２４３０ 判定部
２４４０ 記憶部
【特許請求の範囲】
【請求項１】
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
前記有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、
を備えたことを特徴とするパラメータ生成装置。
【請求項２】
前記第１素数探索部は、Ｗ／ｎｍビット以上の素数を探索し、
前記第２素数探索部は、円分多項式Φnm（ｐ）を割り切るSビット以上の素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項３】
前記群Ｇは、素数位数トーラスＴを用い、
前記第２素数探索部は、Φn(ｐm)=Φnm（ｐ）＝ｑを満たし、かつSビット以上の素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項４】
前記群Ｇは、素数位数トーラスＴを用い、
前記拡大次数決定部は、前記拡大次数ｍを、代数的トーラスＴの次数ｎの素因数のべき乗の積を算出することにより決定し、
前記第２素数探索部は、Φnm（ｐ）＝ｑを満たし、かつＳビット以上の前記素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項５】
前記群Ｇは、素数位数トーラスＴを用い、
前記検査部は、前記乗算値ｎｍが素数ｑで割り切れる場合に、さらに、前記乗算値ｎｍの約数ｄ（但し、ｄ＜ｎｍ）のそれぞれを採択して、円分多項式Φd（ｐ）がqで割り切れるか否かの検査を行い、
前記出力部は、さらに、採択されたいずれの約数ｄについても、前記円分多項式Φd（ｐ）がqで割り切れない場合に、前記パラメータ（ｐ、ｑ、ｍ）を出力することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項６】
前記検査部は、前記素数pのビット数が所定ビット数より大きい場合に、nmが前記素数qよりも小さいか否かの検査を行い、
前記出力部は、前記乗算値ｎｍが前記素数qよりも小さい場合に、前記暗号系が安全性ありと判定し、前記パラメータ（ｐ，ｑ，ｎ，ｍ）を出力することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項７】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項２〜６のいずれか１項に記載のパラメータ生成装置。
【請求項８】
前記代数的トーラスＴの次数ｎが２で割り切れる場合に、前記素数ｐ、前記代数的トーラスＴの次数ｎ、前記有限体Ｆｐmの拡大次数ｍが条件１を満たすか否かを判定し、前記代数的トーラスＴの次数ｎが６で割り切れる場合に、前記素数ｐ、前記代数的トーラスＴの次数ｎ、前記有限体Ｆｐmの拡大次数ｍが条件２を満たすか否かを判定することにより、トーラス上離散対数問題の計算法が有効か否かを判定する有効性判定部を更に備えたことを特徴とする請求項１に記載のパラメータ生成装置。
条件１：ｍ’ｌｏｇｍ’≒ｌｏｇｐ
ただし、ｎ’＝２、ｍ’＝ｎｍ／２
条件２：２ｍ’ｌｏｇｍ’＋１２ｍ’ｌｏｇ２≒ｌｏｇｐ
ただし、ｎ’＝６、ｍ’＝ｎｍ／６
【請求項９】
前記出力部は、トーラス上離散対数問題の計算法が有効でないと判定された場合に、前記パラメータ（ｐ，ｑ，ｎ，ｍ）を出力することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１０】
前記有効性判定部は、前記第１素数探索部により前記素数ｐが探索された後、トーラス上離散対数問題の計算法が有効か否かを判定し、
前記第２素数探索部は、トーラス上離散対数問題の計算法が有効でないと判定された場合に、前記素数ｑを探索することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１１】
前記第１素数探索部は、前記有効性判定部によって前記条件１または前記条件２を満たさないと判定され、かつ前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の前記素数ｐを探索することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１２】
前記拡大次数決定部は、前記有効性判定部によって前記条件１または前記条件２を満たさないと判定された、前記有限体Ｆｐmの拡大次数ｍを決定することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１３】
パラメータ生成装置と、鍵生成装置と、暗号化装置と、前記暗号化装置にネットワークで接続された復号化装置とを備えた暗号処理システムであって、
前記パラメータ生成装置は、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、前記代数的トーラスが定義され、安全性を定める有限体FのサイズＷと、前記群ＧのサイズＳの入力を受け付ける第１入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する第１安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する第１出力部と、を備え、
前記鍵生成装置は、
前記パラメータ（ｐ，ｑ，ｎ，ｍ）の入力を受け付ける第２入力受付部と、
前記素数ｑを前記群Ｇの位数とし、前記素数ｐを前記有限体Ｆの標数とし、前記標数ｐ、前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせで公開鍵を計算する公開鍵計算部と、
前記公開鍵を出力する第２出力部と、を備え、
前記暗号化装置は、
前記公開鍵と平文の入力を受け付ける第３入力受付部と、
前記標数ｐおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記平文に対して前記公開鍵を用いた暗号化処理を施して、暗号文を求める暗号化処理部と、
前記暗号文を前記復号化装置に送信する送信部と、を備え、
前記復号化装置は、
秘密鍵を記憶する記憶部と、
前記暗号文を受信する受信部と、
前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記暗号文に対して前記秘密鍵を用いた復号化処理を施して、前記平文を求める復号化処理部と、
前記平文を出力する第４出力部と、
を備えたことを特徴とする暗号処理システム。
【請求項１４】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記鍵生成装置の前記公開鍵計算部は、
前記群Ｇの位数qで範囲が限定される乱数を生成する第１乱数生成部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記群Ｇの生成元ｇに対して、生成した乱数または前記乱数を用いて計算されるべき指数でべき乗演算および乗算を行うことにより、前記公開鍵を求める第１演算部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項１５】
前記鍵生成装置は、前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算により、前記公開鍵をトーラス圧縮する第１圧縮処理部を更に備え、
前記第２出力部は、前記公開鍵として前記第１圧縮処理部によりトーラス圧縮された公開鍵を出力することを特徴とする請求項１４に記載の暗号処理システム。
【請求項１６】
前記鍵生成装置は、トーラス圧縮された前記生成元ｇをトーラス伸長する第１伸長処理部を更に備え、
前記第１演算部は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記第１伸長処理部によりトーラス伸長された生成元ｇに対して、生成した乱数または前記乱数を用いて計算されるべき指数でべき乗演算および乗算を行うことにより、前記公開鍵を求めることを特徴とする請求項１４に記載の暗号処理システム。
【請求項１７】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項１５または１６に記載の暗号処理システム。
【請求項１８】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記暗号化装置の前記暗号化処理部は、
前記群Ｇの位数qで範囲が限定される乱数を生成する第２乱数生成部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上で、前記生成元ｇと前記公開鍵とを前記乱数で第１のべき乗演算し、第１のべき乗演算の結果と前記平文とを乗算し、乗算した結果と前記第１のべき乗演算の結果のハッシュ値を求め、前記ハッシュ値と前記乱数で前記公開鍵を第２のべき乗演算し、第１のべき乗演算の結果と第２のべき乗演算の結果とを、前記暗号文として求める第２演算部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項１９】
前記暗号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文をトーラス圧縮する第２圧縮処理部をさらに備えたことを特徴とする請求項１８に記載の暗号処理システム。
【請求項２０】
前記暗号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記トーラス圧縮された公開鍵をトーラス伸長する第２伸長処理部をさらに備えたことを特徴とする請求項１８に記載の暗号処理システム。
【請求項２１】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項１９または２０に記載の暗号処理システム。
【請求項２２】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記復号化装置の前記復号化処理部は、
前記暗号文が前記群Ｇの元であるか否かを検査し、前記群Ｇの元である場合には、前記暗号文は正当であると判定する第１判定部と、
前記暗号文のハッシュ値を求め、前記ハッシュ値と前記秘密鍵とにより前記暗号文の要素をべき乗演算および乗算して、所定の検査式と一致する場合に、前記暗号文は正当であると判定する第２判定部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文の要素をべき乗演算および乗算して逆元値を求め、前記暗号文の要素と乗算して前記平文を求める第３演算部と、を備え、
前記第４出力部は、前記第１判定部および前記第２判定部により前記暗号文が正当であると判定された場合に、前記平文を出力することを特徴とする請求項１３に記載の暗号処理システム。
【請求項２３】
前記復号化装置の前記受信部は、トーラス圧縮された暗号文を受信し、
前記復号化装置の前記第１判定部は、前記トーラス圧縮された暗号文が前記群Ｇの元であるか否かを検査し、前記群Ｇの元である場合には、前記暗号文は正当であると判定し、
前記復号化装置は、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記トーラス圧縮された暗号文をトーラス伸長する第３伸長処理部をさらに備えたことを特徴とする請求項２２に記載の暗号処理システム。
【請求項２４】
前記復号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記平文をトーラス圧縮する第３圧縮処理部をさらに備え、
前記第４出力部は、前記平文として前記第３圧縮処理部によりトーラス圧縮された平文を出力することを特徴とする請求項２２に記載の暗号処理システム。
【請求項２５】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であって、
前記第３演算部は、前記逆元値を前記暗号文の第３の要素と乗算して前記平文を求めることを特徴とする請求項２３または２４に記載の暗号処理システム。
【請求項２６】
前記第２判定部は、前記ハッシュ値と前記秘密鍵とにより前記暗号文の第１要素および第２要素をべき乗演算および乗算して、前記検査式として前記暗号文の第４の要素と一致する場合に、前記暗号文は正当であると判定することを特徴とする請求項２５に記載の暗号処理システム。
【請求項２７】
前記第２判定部は、前記ハッシュ値と前記秘密鍵とにより前記暗号文の第１要素をべき乗演算および乗算して、前記検査式として前記暗号文の第２の要素および第４の要素とそれぞれ一致する場合に、前記暗号文は正当であると判定し、
前記第３演算部は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文の第１の要素をべき乗演算および乗算して逆元値を求めることを特徴とする請求項２５に記載の暗号処理システム。
【請求項２８】
前記暗号系の安全性を判定する安全性判定装置をさらに備え、
前記安全性判定装置は、
前記パラメータ生成装置で出力された前記パラメータ（ｐ，ｑ，ｍ，ｎ）の入力を受け付ける第５入力受付部と、
前記円分多項式Φnm（ｐ）がｑで割り切れるか否かを判断することにより、前記群Ｇが前記代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるか否かを検査する第１検査部と、
前記乗算値ｎｍがｑで割り切れるか否かを判断することにより、前記群Ｇが前記代数的トーラスＴの部分群のうち、唯一の部分群に含まれるかを検査する第２検査部と、
前記第１検査部の検査結果が肯定的であり、かつ、前記第２検査部による検査結果が肯定的である場合に、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は前記標数ｐ、前記拡大次数ｎｍの拡大体と同等の安全性を有すると判定する第２安全性判定部と、
前記第２安全性判定部による判定結果を出力する第５出力部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項２９】
前記第２検査部は、前記乗算値ｎｍが素数ｑで割り切れる場合に、さらに、前記乗算値ｎｍの約数ｄ（但し、ｄ＜ｎｍ）のそれぞれを採択して、円分多項式Φd（ｐ）がqで割り切れるか否かの検査を行い、
前記第２安全性判定部は、前記第１検査部による検査結果が肯定的であり、前記第２検査部による最小の約数ｄがｎｍである場合に、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は標数ｐ、拡大次数ｎｍの拡大体と同等の安全性を有すると判定することを特徴とする請求項２８に記載の暗号処理システム。
【請求項３０】
前記最小のｄを記憶する拡大次数記憶部をさらに備え、
前記第２安全性判定部は、さらに、前記拡大体記憶部に記憶されたｄを取得し、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は前記標数ｐ、拡大次数ｄの拡大体と同等の安全性を有すると判定することを特徴とする請求項２９に記載の暗号処理システム。
【請求項３１】
パラメータ生成装置で実行されるパラメータ生成方法であって、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付ステップと、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定ステップと、
前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索ステップと、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索ステップと、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査ステップと、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定ステップと、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力ステップと、
を含むことを特徴とするパラメータ生成方法。
【請求項３２】
コンピュータを、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、
して機能させるプログラム。
【請求項１】
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
前記有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、
を備えたことを特徴とするパラメータ生成装置。
【請求項２】
前記第１素数探索部は、Ｗ／ｎｍビット以上の素数を探索し、
前記第２素数探索部は、円分多項式Φnm（ｐ）を割り切るSビット以上の素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項３】
前記群Ｇは、素数位数トーラスＴを用い、
前記第２素数探索部は、Φn(ｐm)=Φnm（ｐ）＝ｑを満たし、かつSビット以上の素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項４】
前記群Ｇは、素数位数トーラスＴを用い、
前記拡大次数決定部は、前記拡大次数ｍを、代数的トーラスＴの次数ｎの素因数のべき乗の積を算出することにより決定し、
前記第２素数探索部は、Φnm（ｐ）＝ｑを満たし、かつＳビット以上の前記素数qを探索することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項５】
前記群Ｇは、素数位数トーラスＴを用い、
前記検査部は、前記乗算値ｎｍが素数ｑで割り切れる場合に、さらに、前記乗算値ｎｍの約数ｄ（但し、ｄ＜ｎｍ）のそれぞれを採択して、円分多項式Φd（ｐ）がqで割り切れるか否かの検査を行い、
前記出力部は、さらに、採択されたいずれの約数ｄについても、前記円分多項式Φd（ｐ）がqで割り切れない場合に、前記パラメータ（ｐ、ｑ、ｍ）を出力することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項６】
前記検査部は、前記素数pのビット数が所定ビット数より大きい場合に、nmが前記素数qよりも小さいか否かの検査を行い、
前記出力部は、前記乗算値ｎｍが前記素数qよりも小さい場合に、前記暗号系が安全性ありと判定し、前記パラメータ（ｐ，ｑ，ｎ，ｍ）を出力することを特徴とする請求項１に記載のパラメータ生成装置。
【請求項７】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項２〜６のいずれか１項に記載のパラメータ生成装置。
【請求項８】
前記代数的トーラスＴの次数ｎが２で割り切れる場合に、前記素数ｐ、前記代数的トーラスＴの次数ｎ、前記有限体Ｆｐmの拡大次数ｍが条件１を満たすか否かを判定し、前記代数的トーラスＴの次数ｎが６で割り切れる場合に、前記素数ｐ、前記代数的トーラスＴの次数ｎ、前記有限体Ｆｐmの拡大次数ｍが条件２を満たすか否かを判定することにより、トーラス上離散対数問題の計算法が有効か否かを判定する有効性判定部を更に備えたことを特徴とする請求項１に記載のパラメータ生成装置。
条件１：ｍ’ｌｏｇｍ’≒ｌｏｇｐ
ただし、ｎ’＝２、ｍ’＝ｎｍ／２
条件２：２ｍ’ｌｏｇｍ’＋１２ｍ’ｌｏｇ２≒ｌｏｇｐ
ただし、ｎ’＝６、ｍ’＝ｎｍ／６
【請求項９】
前記出力部は、トーラス上離散対数問題の計算法が有効でないと判定された場合に、前記パラメータ（ｐ，ｑ，ｎ，ｍ）を出力することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１０】
前記有効性判定部は、前記第１素数探索部により前記素数ｐが探索された後、トーラス上離散対数問題の計算法が有効か否かを判定し、
前記第２素数探索部は、トーラス上離散対数問題の計算法が有効でないと判定された場合に、前記素数ｑを探索することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１１】
前記第１素数探索部は、前記有効性判定部によって前記条件１または前記条件２を満たさないと判定され、かつ前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の前記素数ｐを探索することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１２】
前記拡大次数決定部は、前記有効性判定部によって前記条件１または前記条件２を満たさないと判定された、前記有限体Ｆｐmの拡大次数ｍを決定することを特徴とする請求項８に記載のパラメータ生成装置。
【請求項１３】
パラメータ生成装置と、鍵生成装置と、暗号化装置と、前記暗号化装置にネットワークで接続された復号化装置とを備えた暗号処理システムであって、
前記パラメータ生成装置は、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、前記代数的トーラスが定義され、安全性を定める有限体FのサイズＷと、前記群ＧのサイズＳの入力を受け付ける第１入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
有限体ＦのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する第１安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する第１出力部と、を備え、
前記鍵生成装置は、
前記パラメータ（ｐ，ｑ，ｎ，ｍ）の入力を受け付ける第２入力受付部と、
前記素数ｑを前記群Ｇの位数とし、前記素数ｐを前記有限体Ｆの標数とし、前記標数ｐ、前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせで公開鍵を計算する公開鍵計算部と、
前記公開鍵を出力する第２出力部と、を備え、
前記暗号化装置は、
前記公開鍵と平文の入力を受け付ける第３入力受付部と、
前記標数ｐおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記平文に対して前記公開鍵を用いた暗号化処理を施して、暗号文を求める暗号化処理部と、
前記暗号文を前記復号化装置に送信する送信部と、を備え、
前記復号化装置は、
秘密鍵を記憶する記憶部と、
前記暗号文を受信する受信部と、
前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算の組み合わせにより、前記暗号文に対して前記秘密鍵を用いた復号化処理を施して、前記平文を求める復号化処理部と、
前記平文を出力する第４出力部と、
を備えたことを特徴とする暗号処理システム。
【請求項１４】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記鍵生成装置の前記公開鍵計算部は、
前記群Ｇの位数qで範囲が限定される乱数を生成する第１乱数生成部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記群Ｇの生成元ｇに対して、生成した乱数または前記乱数を用いて計算されるべき指数でべき乗演算および乗算を行うことにより、前記公開鍵を求める第１演算部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項１５】
前記鍵生成装置は、前記標数pおよび前記拡大次数ｍの有限体またはその部分体上の演算により、前記公開鍵をトーラス圧縮する第１圧縮処理部を更に備え、
前記第２出力部は、前記公開鍵として前記第１圧縮処理部によりトーラス圧縮された公開鍵を出力することを特徴とする請求項１４に記載の暗号処理システム。
【請求項１６】
前記鍵生成装置は、トーラス圧縮された前記生成元ｇをトーラス伸長する第１伸長処理部を更に備え、
前記第１演算部は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記第１伸長処理部によりトーラス伸長された生成元ｇに対して、生成した乱数または前記乱数を用いて計算されるべき指数でべき乗演算および乗算を行うことにより、前記公開鍵を求めることを特徴とする請求項１４に記載の暗号処理システム。
【請求項１７】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項１５または１６に記載の暗号処理システム。
【請求項１８】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記暗号化装置の前記暗号化処理部は、
前記群Ｇの位数qで範囲が限定される乱数を生成する第２乱数生成部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上で、前記生成元ｇと前記公開鍵とを前記乱数で第１のべき乗演算し、第１のべき乗演算の結果と前記平文とを乗算し、乗算した結果と前記第１のべき乗演算の結果のハッシュ値を求め、前記ハッシュ値と前記乱数で前記公開鍵を第２のべき乗演算し、第１のべき乗演算の結果と第２のべき乗演算の結果とを、前記暗号文として求める第２演算部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項１９】
前記暗号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文をトーラス圧縮する第２圧縮処理部をさらに備えたことを特徴とする請求項１８に記載の暗号処理システム。
【請求項２０】
前記暗号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記トーラス圧縮された公開鍵をトーラス伸長する第２伸長処理部をさらに備えたことを特徴とする請求項１８に記載の暗号処理システム。
【請求項２１】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であることを特徴とする請求項１９または２０に記載の暗号処理システム。
【請求項２２】
前記トーラス圧縮公開鍵暗号方式は、離散対数問題に基づく暗号方式であり、
前記復号化装置の前記復号化処理部は、
前記暗号文が前記群Ｇの元であるか否かを検査し、前記群Ｇの元である場合には、前記暗号文は正当であると判定する第１判定部と、
前記暗号文のハッシュ値を求め、前記ハッシュ値と前記秘密鍵とにより前記暗号文の要素をべき乗演算および乗算して、所定の検査式と一致する場合に、前記暗号文は正当であると判定する第２判定部と、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文の要素をべき乗演算および乗算して逆元値を求め、前記暗号文の要素と乗算して前記平文を求める第３演算部と、を備え、
前記第４出力部は、前記第１判定部および前記第２判定部により前記暗号文が正当であると判定された場合に、前記平文を出力することを特徴とする請求項１３に記載の暗号処理システム。
【請求項２３】
前記復号化装置の前記受信部は、トーラス圧縮された暗号文を受信し、
前記復号化装置の前記第１判定部は、前記トーラス圧縮された暗号文が前記群Ｇの元であるか否かを検査し、前記群Ｇの元である場合には、前記暗号文は正当であると判定し、
前記復号化装置は、
前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記トーラス圧縮された暗号文をトーラス伸長する第３伸長処理部をさらに備えたことを特徴とする請求項２２に記載の暗号処理システム。
【請求項２４】
前記復号化装置は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記平文をトーラス圧縮する第３圧縮処理部をさらに備え、
前記第４出力部は、前記平文として前記第３圧縮処理部によりトーラス圧縮された平文を出力することを特徴とする請求項２２に記載の暗号処理システム。
【請求項２５】
前記トーラス圧縮公開鍵暗号方式は、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であって、
前記第３演算部は、前記逆元値を前記暗号文の第３の要素と乗算して前記平文を求めることを特徴とする請求項２３または２４に記載の暗号処理システム。
【請求項２６】
前記第２判定部は、前記ハッシュ値と前記秘密鍵とにより前記暗号文の第１要素および第２要素をべき乗演算および乗算して、前記検査式として前記暗号文の第４の要素と一致する場合に、前記暗号文は正当であると判定することを特徴とする請求項２５に記載の暗号処理システム。
【請求項２７】
前記第２判定部は、前記ハッシュ値と前記秘密鍵とにより前記暗号文の第１要素をべき乗演算および乗算して、前記検査式として前記暗号文の第２の要素および第４の要素とそれぞれ一致する場合に、前記暗号文は正当であると判定し、
前記第３演算部は、前記標数pおよび前記拡大次数mの有限体またはその部分体上の演算により、前記暗号文の第１の要素をべき乗演算および乗算して逆元値を求めることを特徴とする請求項２５に記載の暗号処理システム。
【請求項２８】
前記暗号系の安全性を判定する安全性判定装置をさらに備え、
前記安全性判定装置は、
前記パラメータ生成装置で出力された前記パラメータ（ｐ，ｑ，ｍ，ｎ）の入力を受け付ける第５入力受付部と、
前記円分多項式Φnm（ｐ）がｑで割り切れるか否かを判断することにより、前記群Ｇが前記代数的トーラスＴの部分群のうち次数ｎｍの代数的トーラスに包含されるか否かを検査する第１検査部と、
前記乗算値ｎｍがｑで割り切れるか否かを判断することにより、前記群Ｇが前記代数的トーラスＴの部分群のうち、唯一の部分群に含まれるかを検査する第２検査部と、
前記第１検査部の検査結果が肯定的であり、かつ、前記第２検査部による検査結果が肯定的である場合に、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は前記標数ｐ、前記拡大次数ｎｍの拡大体と同等の安全性を有すると判定する第２安全性判定部と、
前記第２安全性判定部による判定結果を出力する第５出力部と、
を備えたことを特徴とする請求項１３に記載の暗号処理システム。
【請求項２９】
前記第２検査部は、前記乗算値ｎｍが素数ｑで割り切れる場合に、さらに、前記乗算値ｎｍの約数ｄ（但し、ｄ＜ｎｍ）のそれぞれを採択して、円分多項式Φd（ｐ）がqで割り切れるか否かの検査を行い、
前記第２安全性判定部は、前記第１検査部による検査結果が肯定的であり、前記第２検査部による最小の約数ｄがｎｍである場合に、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は標数ｐ、拡大次数ｎｍの拡大体と同等の安全性を有すると判定することを特徴とする請求項２８に記載の暗号処理システム。
【請求項３０】
前記最小のｄを記憶する拡大次数記憶部をさらに備え、
前記第２安全性判定部は、さらに、前記拡大体記憶部に記憶されたｄを取得し、前記パラメータ（ｐ，ｑ，ｍ，ｎ）は前記標数ｐ、拡大次数ｄの拡大体と同等の安全性を有すると判定することを特徴とする請求項２９に記載の暗号処理システム。
【請求項３１】
パラメータ生成装置で実行されるパラメータ生成方法であって、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付ステップと、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定ステップと、
前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索ステップと、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索ステップと、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査ステップと、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定ステップと、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力ステップと、
を含むことを特徴とするパラメータ生成方法。
【請求項３２】
コンピュータを、
トーラス圧縮公開鍵暗号方式で用いられる暗号系が定義される群Ｇが包含される代数的トーラスＴの次数ｎと、安全性を定める有限体ＦのサイズＷと、前記群ＧのサイズＳの入力を受け付ける入力受付部と、
前記代数的トーラスが定義される有限体Ｆｐmの拡大次数ｍを決定する拡大次数決定部と、
前記有限体FのサイズＷと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとに基づくビット数の素数ｐを探索する第１素数探索部と、
前記群ＧのサイズＳに基づいて定められるビット数であり、円分多項式Φnm（ｐ）を割り切る素数ｑを探索する第２素数探索部と、
代数的トーラスＴの次数ｎと前記有限体Ｆｐmの拡大次数ｍとの乗算値ｎｍがqで割り切れるか否かを検査する検査部と、
前記乗算値ｎｍがｑで割り切れない場合に、前記暗号系が安全性ありと判定する安全性判定部と、
前記暗号系が安全性ありと判定された場合に、前記素数ｐと、前記素数ｑと、前記代数的トーラスＴの次数ｎと、前記拡大次数ｍとからなるパラメータ（ｐ，ｑ，ｎ，ｍ）を出力する出力部と、
して機能させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【公開番号】特開２０１０−４９２１５（Ｐ２０１０−４９２１５Ａ）
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願番号】特願２００８−２１６０１７（Ｐ２００８−２１６０１７）
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]