(57)【要約】【課題】有限体の乗法群の部分群の元であるか否かを判定するときの計算コストを削減する判定装置を提供すること。【解決手段】拡大体表現で表現された第１拡大体表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部１０２と、アフィン表現データを拡大体表現で表された第２拡大体表現データに変換する第２変換部１０３と、第１拡大体表現データと第２拡大体表現データとを比較し、第１拡大体表現データと第２拡大体表現データとが一致する場合に、第１拡大体表現データが有限体の乗法群の部分群上の元であると判定する判定部１０４と、を備えた。【選択図】        図２
2010156872.tif 000002
【特許請求の範囲】
【請求項１】
拡大体表現で表現された第１拡大体表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、
前記アフィン表現データを拡大体表現で表された第２拡大体表現データに変換する第２変換部と、
前記第１拡大体表現データと前記第２拡大体表現データとを比較し、前記第１拡大体表現データと前記第２拡大体表現データとが一致する場合に、前記第１拡大体表現データが有限体の乗法群の部分群上の元であると判定する判定部と、
を備えたことを特徴とする判定装置。
【請求項２】
前記判定部は、前記第１拡大体表現データと前記第２拡大体表現データとが一致しない場合に、前記第１拡大体表現データが前記部分群上の元でないと判定すること、
を特徴とする請求項１に記載の判定装置。
【請求項３】
前記判定部は、さらに、前記第１変換部および前記第２変換部の少なくとも一方による変換処理が正常に実行できるか否かを判定し、正常に実行できない場合に、前記第１拡大体表現データが前記部分群上の元でないと判定すること、
を特徴とする請求項１に記載の判定装置。
【請求項４】
射影表現で表現された射影表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、
前記第１変換部による変換処理中に算出される複数の中間データを抽出する抽出部と、
前記複数の中間データが予め定められた条件を満たすか否かを判定し、前記複数の中間データが前記条件を満たさない場合に、前記射影表現データが有限体の乗法群の部分群上の元でないと判定する判定部と、
を備えたことを特徴とする判定装置。
【請求項５】
前記抽出部は、前記第１変換部による変換処理中に算出される３つの中間データを抽出し、
前記判定部は、前記３つの中間データのうち２つの中間データを予め定められた関数に入力した結果として出力される出力値を求め、前記出力値と、前記３つの中間データのうち前記２つの中間データ以外の中間データとが一致しない場合に、前記射影表現データが前記部分群上の元でないと判定すること、
を特徴とする請求項４に記載の判定装置。
【請求項６】
前記第１変換部は、拡大体表現で表現された第１拡大体表現データを前記射影表現データに変換し、変換した射影表現データを前記アフィン表現データに変換し、
前記判定部は、前記複数の中間データが前記条件を満たさない場合に、前記第１拡大体表現データが前記部分群上の元でないと判定すること、
を特徴とする請求項４に記載の判定装置。
【請求項７】
前記判定部によって、前記複数の中間データが前記条件を満たすと判定された場合に、前記射影表現データを拡大体表現で表現された第２拡大体表現データに変換する第２変換部をさらに備え、
前記判定部は、さらに、前記第１拡大体表現データと前記第２拡大体表現データとを比較し、前記第１拡大体表現データと前記第２拡大体表現データとが一致する場合に、前記第１拡大体表現データが前記部分群上の元であると判定すること、
を特徴とする請求項６に記載の判定装置。
【請求項８】
前記判定部は、さらに、前記第１変換部による変換処理が正常に実行できるか否かを判定し、正常に実行できない場合に、前記射影表現データが前記部分群上の元でないと判定すること、
を特徴とする請求項４に記載の判定装置。
【請求項９】
第１変換部が、拡大体表現で表現された第１拡大体表現データをアフィン表現で表されたアフィン表現データに変換する第１変換ステップと、
第２変換部が、前記アフィン表現データを拡大体表現で表された第２拡大体表現データに変換する第２変換ステップと、
判定部が、前記第１拡大体表現データと前記第２拡大体表現データとを比較し、前記第１拡大体表現データと前記第２拡大体表現データとが一致する場合に、前記第１拡大体表現データが有限体の乗法群の部分群上の元であると判定する判定ステップと、
を備えたことを特徴とする判定方法。
【請求項１０】
第１変換部が、射影表現で表現された射影表現データをアフィン表現で表されたアフィン表現データに変換する第１変換ステップと、
抽出部が、前記第１変換部による変換処理中に算出される複数の中間データを抽出する抽出ステップと、
判定部が、前記複数の中間データが予め定められた条件を満たすか否かを判定し、前記複数の中間データが前記条件を満たさない場合に、前記射影表現データが有限体の乗法群の部分群上の元でないと判定する判定ステップと、
を備えたことを特徴とする判定方法。
【請求項１１】
コンピュータを、
拡大体表現で表現された第１拡大体表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、
前記アフィン表現データを拡大体表現で表された第２拡大体表現データに変換する第２変換部と、
前記第１拡大体表現データと前記第２拡大体表現データとを比較し、前記第１拡大体表現データと前記第２拡大体表現データとが一致する場合に、前記第１拡大体表現データが有限体の乗法群の部分群上の元であると判定する判定部と、
として機能させるための判定プログラム。
【請求項１２】
コンピュータを、
射影表現で表現された射影表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、
前記第１変換部による変換処理中に算出される複数の中間データを抽出する抽出部と、
前記複数の中間データが予め定められた条件を満たすか否かを判定し、前記複数の中間データが前記条件を満たさない場合に、前記射影表現データが有限体の乗法群の部分群上の元でないと判定する判定部と、
として機能させるための判定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開鍵暗号等で用いられる有限体の乗法群の部分群の元であるか否かを判定する装置、方法およびプログラムに関する。
【背景技術】
【０００２】
事前に鍵を共有することを必要とせずに安全な通信を実現する公開鍵暗号は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになっている。
【０００３】
公開鍵暗号で現在の典型的な暗号系サイズは１０２４ビットである。なお、暗号系サイズとは、公開鍵暗号で用いる表現形式で表した場合のデータのサイズを表す。例えば公開鍵暗号方式の１つであるＣｒａｍｅｒ−Ｓｈｏｕｐ暗号等では、１０２４ビットの拡大体表現と呼ばれる表現形式で各種データが表現される。計算機の進歩とともに攻撃者の能力も上がっているため、解読が困難とされる暗号系サイズは年々大きくなっている。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となる。例えば、公開鍵サイズは、暗号系サイズと鍵の個数との積になる。また、暗号文サイズは、暗号系サイズと、１つのメッセージを暗号化するのに必要な暗号文の数との積になる。したがって、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づき、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する技術が提案されている（例えば、非特許文献１）。代数的トーラスは、有限体の乗法群の部分群として定義される。非特許文献１では、この技術を用いて、素体上の代数的トーラスを用いたＥｌＧａｍａｌ暗号やＤＨ鍵交換が提案されている。
【０００５】
また、非特許文献２では、代数的トーラスを、拡大体表現、射影表現、およびアフィン表現と呼ばれる各表現形式で表す方法の一例が示されている。代数的トーラスを用いた暗号方式では、拡大体表現のデータをアフィン表現で表すことにより、データサイズを１／３に圧縮している。
【０００６】
代数的トーラスを用いた暗号方式では、例えば拡大体表現のデータが入力されたとき、このデータが実際に代数的トーラスの元でなければアフィン表現に圧縮してデータサイズを削減することができない。このため、通常は処理対象とするデータが代数的トーラスの元であるか否かを判定する必要がある。
【０００７】
【非特許文献１】Ｋ．Ｒｕｂｉｎ  ａｎｄ  Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”、ＣＲＹＰＴＯ  ２００３、Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ２７２９、３４９−３６５、２００３．
【非特許文献２】Ｓｔｅｖｅｎ  Ｇａｌｂｒａｉｔｈ．“Ｄｉｓｇｕｉｓｉｎｇ  ｔｏｒｉ  ａｎｄ ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ”ＩＡＣＲ  ｅ−ｐｒｉｎｔ  Ａｒｃｈｉｖｅ  ２００６／２４８，ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ.ｏｒｇ／２００６／２４８
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来、拡大体表現の元が代数的トーラスの元となりうるか否かは、代数的トーラスの位数乗した場合に１となる元であるか否かを確認する必要があった。しかし、公開鍵暗号方式等で用いられる代数的トーラスの位数は非常に大きいので、べき乗計算に膨大な計算コストがかかるという問題があった。
【０００９】
本発明は、上記に鑑みてなされたものであって、有限体の乗法群の部分群の元であるか否かを判定するときの計算コストを削減することができる装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、拡大体表現で表現された第１拡大体表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、前記アフィン表現データを拡大体表現で表された第２拡大体表現データに変換する第２変換部と、前記第１拡大体表現データと前記第２拡大体表現データとを比較し、前記第１拡大体表現データと前記第２拡大体表現データとが一致する場合に、前記第１拡大体表現データが有限体の乗法群の部分群上の元であると判定する判定部と、を備えたことを特徴とする。
【００１１】
また、本発明は、射影表現で表現された射影表現データをアフィン表現で表されたアフィン表現データに変換する第１変換部と、前記第１変換部による変換処理中に算出される複数の中間データを抽出する抽出部と、前記複数の中間データが予め定められた条件を満たすか否かを判定し、前記複数の中間データが前記条件を満たさない場合に、前記射影表現データが有限体の乗法群の部分群上の元でないと判定する判定部と、を備えたことを特徴とする。
【００１２】
また、本発明は、上記装置を実行することができる方法およびプログラムである。
【発明の効果】
【００１３】
本発明によれば、有限体の乗法群の部分群の元であるか否かを判定するときの計算コストを削減することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１４】
以下に添付図面を参照して、この発明にかかる装置、方法およびプログラムの最良な実施の形態を詳細に説明する。
【００１５】
（第１の実施の形態）
第１の実施の形態にかかる判定装置は、拡大体表現のデータをアフィン表現に変換し、さらにアフィン表現に変換したデータを拡大体表現に復元する。そして、復元したデータと変換前の拡大体表現のデータとが一致する場合に、変換前の拡大体表現のデータが代数的トーラスの元であると判定する。
【００１６】
なお、本実施の形態の判定装置は、代数的トーラスを用いた暗号方式を利用した装置などの各種装置に適用できる。例えば、公開鍵や平文の判定に用いることが可能であるので、暗号化装置に適用してもよい。また、暗号文の判定に用いることが可能であるので、復号装置に適用してもよい。さらに、鍵生成装置に適用することも可能である。すなわち、本実施の形態の判定装置は、代数的トーラスの元であると判定されたデータに対して、暗号化処理、復号処理などの所定の処理を実行する各種装置に適用できる。
【００１７】
最初に、本実施の形態で用いる代数的トーラスの元の表現方法について説明する。本実施の形態では、拡大体上で定義された代数的トーラスを用いた例として、代数的トーラスの元を以下のように表現する例について説明する。
【００１８】
代数的トーラスとしてＴ６（Ｆｐ＾ｍ）を考える。代数的トーラスを表現する方法としては、アフィン表現、射影表現、および拡大体表現が存在する。Ｔ６（Ｆｐ＾ｍ）は拡大体Ｆｐ＾６ｍの乗法群の部分群であるので、拡大体Ｆｐ＾６ｍの表現で表すことができる。この表現を拡大体表現と呼ぶ。拡大体表現では、Ｆｐ＾ｍの要素６つでＴ６（Ｆｐ＾ｍ）の要素１つを表す。同様にして、Ｔ６（Ｆｐ＾ｍ）はＴ２（Ｆｐ＾３ｍ）の部分群であるので、代数的トーラスＴ２（Ｆｐ＾３ｍ）の表現で表すことができる。この表現を射影表現と呼ぶ。
【００１９】
Ｔ２（Ｆｐ＾３ｍ）の位数は（ｐ＾（３ｍ）＋１）である。拡大体Ｆｐ＾６ｍの乗法群の要素である位数（ｐ＾（６ｍ）−１）の要素について、（ｐ＾（３ｍ）＋１）／（ｐ＾（６ｍ）−１）乗すれば、位数（ｐ＾（３ｍ）＋１）の要素となる。すなわち、Ｔ２（Ｆｐ＾３ｍ）の要素となる。（ｐ＾（３ｍ）＋１）／（ｐ＾（６ｍ）−１）＝ｐ＾（３ｍ）−１であるから、拡大体Ｆｐ＾６ｍの要素をα＋βｘとすると、以下の（１）式で表される値がＴ２（Ｆｐ＾３ｍ）の要素である。
【数１】
2010156872.tif 000003
【００２０】
ここで、αおよびβはＦｐ＾３ｍの要素であり、ｘはＦｐ＾３ｍからＦｐ＾６ｍへの２次拡大の際に添加する要素である。２次拡大の法多項式はｆ２（ｘ）＝ｘ＾２−δ、基底は｛１，ｘ｝とする。なお、δは、予め定められたＦｐ＾３ｍの要素である。
【００２１】
射影表現はＴ２（Ｆｐ＾３ｍ）の要素を表す表現であった。射影表現の要素をＴ６（Ｆｐ＾ｍ）の位数乗して１となる要素はＴ６（Ｆｐ＾ｍ）の要素である。よって、以下の（２）式を解くことを考える。
【数２】
2010156872.tif 000004
【００２２】
法多項式がｆ２（ｘ）＝ｘ＾２−δであることから上記（２）式は、以下の（３）式に書き換えることができる。
【数３】
2010156872.tif 000005
【００２３】
法多項式ｆ２（ｘ）が既約となる条件より、δの（ｐ＾（３ｍ）−１）／２乗は１とはならない。したがって、以下の（４）式を解く。
【数４】
2010156872.tif 000006
【００２４】
ここで、δがＦｐ＾ｍの要素として、β≠０のとき、上記（４）式は以下の（５）式に書き換えることができる。
【数５】
2010156872.tif 000007
【００２５】
γ＝α／βと置くと、上記（５）式はさらに以下の（６）式に書き換えることができる。
【数６】
2010156872.tif 000008
【００２６】
そこで、γを以下の（７）式として計算すると、ｙとｙ＾２の項は０となり１の項だけが残る。すなわち、以下の（８）式が得られる。
【数７】
2010156872.tif 000009
【００２７】
ｙはＦｐ＾ｍからＦｐ＾３ｍへの３次拡大の際に添加する要素である。３次拡大の法多項式はｆ３（ｙ）＝ｙ＾３−ｗ、基底は｛１，ｙ，ｙ＾２｝とする。ｃ１≠０のときｃ２はｃ０とｃ１を用いて以下の（９）式により計算することができる。なお、ｗは、予め定められたＦｐ＾ｍの要素である。
【数８】
2010156872.tif 000010
【００２８】
よって、Ｔ６（Ｆｐ＾ｍ）の要素はｃ０とｃ１とで一意に定まる。または、ｃ１とｃ２の役割を入れ替えて、ｃ０とｃ２で一意に定まる。これがアフィン表現である。アフィン表現を射影表現に戻すには、以下の（１０）式または（１１）式のような伸張写像を計算すればよい。
【数９】
2010156872.tif 000011
【００２９】
次に、本実施の形態で利用する原理について図１を用いて説明する。図１に示すように、拡大体表現の代数的トーラスの元と、アフィン表現の代数的トーラスの元は１対１に対応する。このため、代数的トーラスの元であるならば、正しい変換方法を用いて拡大体表現からアフィン表現に変換し、さらに拡大体表現に復元しても、値は変化しない。同図では、拡大体表現１０の代数的トーラス１１の元１２と、アフィン表現３０の代数的トーラスの元３１とが１対１に対応することが示されている。なお、元１２は、射影表現２０の代数的トーラス２１上では、複数の元２２および元２３に対応しうる。
【００３０】
また、拡大体表現で表されたすべての元が代数的トーラスの元となっているわけではないのに対し、アフィン表現では任意の元が代数的トーラスの元となっている。
【００３１】
ここで、代数的トーラスの元ではない拡大体表現の元を強制的にアフィン表現に変換すると、アフィン表現上では代数的トーラスの元に変化する。これは変換が正常に実行されないためである。同図では、一例として、拡大体表現１０の元１３が、本来は対応しないアフィン表現の元３１に強制的に変換された例が示されている。なお、同図では、元１３が射影表現では元２４に対応するものとしている。
【００３２】
本実施の形態では、このような性質を用いて、拡大体表現の要素が代数的トーラスの元であるかを判定する。より具体的には、以下の３つの性質を用いて代数的トーラスの元であるかを判定する。
（１）代数的トーラスの元を拡大体表現からアフィン表現に変換し、さらに拡大体表現に変換すると、アフィン表現に変換する前の拡大体表現の元に戻る
（２）代数的トーラスの元ではない拡大体表現の元を強制的に拡大体表現からアフィン表現に変換し、さらに拡大体表現に変換すると、アフィン表現に変換する前の拡大体表現の元に戻らず、代数的トーラスの元となる
（３）拡大体表現で、ある代数的トーラスの元と同値となる元は、その元以外に存在しない
【００３３】
したがって、拡大体表現で与えられた元が代数的トーラスの元となるか否かは、当該元を一度アフィン表現に変換し、それを拡大体表現に復元した値と、与えられた元とを比較し、一致するか否かで判断すればよい。
【００３４】
次に、本実施の形態の判定装置の具体的な構成について図２を用いて説明する。図２は、第１の実施の形態にかかる判定装置１００のブロック図である。同図に示すように、判定装置１００は、入力部１０１と、第１変換部１０２と、第２変換部１０３と、判定部１０４と、を備えている。
【００３５】
入力部１０１は、代数的トーラスの元であるか否かを判定するデータを入力する。本実施の形態では、拡大体表現で表された拡大体表現データ（第１拡大体表現データ）を入力する。判定装置１００を暗号化装置に適用する場合は、入力部１０１は、例えば、暗号の対象となる平文を拡大体表現データとして入力する。
【００３６】
第１変換部１０２は、拡大体表現データをアフィン表現で表されたアフィン表現データに変換する。第２変換部１０３は、アフィン表現データを拡大体表現で表された拡大体表現データ（第２拡大体表現データ）に変換する。第１変換部１０２および第２変換部１０３の機能を１つの構成部で提供するように構成してもよい。
【００３７】
判定部１０４は、入力された拡大体表現のデータ（第１拡大体表現データ）と、アフィン表現に変換後さらに拡大体表現に復元されたデータ（第２拡大体表現データ）とを比較し、両者が一致する場合に、入力されたデータが代数的トーラス上の元であると判定する。
【００３８】
次に、このように構成された第１の実施の形態にかかる判定装置１００による判定処理について図３を用いて説明する。図３は、第１の実施の形態における判定処理の全体の流れを示すフローチャートである。
【００３９】
まず、入力部１０１が、拡大体表現の元（第１拡大体表現データ）を入力する（ステップＳ３０１）。次に、第１変換部１０２が、入力された元をアフィン表現の元（アフィン表現データ）に変換する（ステップＳ３０２）。さらに、第２変換部１０３が、変換された元を拡大体表現の元（第２拡大体表現データ）に復元する（ステップＳ３０３）。
【００４０】
次に、判定部１０４が、入力された元（第１拡大体表現データ）と、アフィン表現に変換後、拡大体表現に復元した元（第２拡大体表現データ）とを比較する（ステップＳ３０４）。両者が一致しない場合（ステップＳ３０４：ＮＯ）、判定部１０４は、入力された元が代数的トーラスの元ではないと判定する（ステップＳ３０５）。両者が一致する場合（ステップＳ３０４：ＹＥＳ）、判定部１０４は、入力された元が代数的トーラスの元であると判定する（ステップＳ３０６）。
【００４１】
次に、上記のような判定処理により計算コストが削減されることについて説明する。
【００４２】
（１）拡大体表現から射影表現への変換
拡大体表現と射影表現との関係式は、以下の（１２）式で表される。なお、（１２）式の左辺が拡大体表現を表し、右辺が射影表現を表している。また、α’，β’，α，およびβは、Ｆｐ＾３ｍの元である。
【数１０】
2010156872.tif 000012
【００４３】
このとき、拡大体表現から射影表現への変換式は、以下の（１３）式で表される。したがって、変換コストは２Ａ（Ｆｐ＾３ｍ換算）である。なお、Ａは加算の変換コストを意味する。また、以下では、乗算の変換コストをＭ、逆元計算の変換コストをＩで表す。
【数１１】
2010156872.tif 000013
【００４４】
（２）射影表現から拡大体表現への変換
射影表現から拡大体表現への変換式は、以下の（１４）式で表される。したがって、変換コストは５Ｍ＋３Ａ＋Ｉ（Ｆｐ＾３ｍ換算）である。
【数１２】
2010156872.tif 000014
【００４５】
（３）射影表現からアフィン表現への変換
γ＝α／βと置き、γ＝ｃ０＋ｃ１ｙ＋ｃ２ｙ２としたときの、ｃ０とｃ１とを取り出したものがアフィン表現なので、変換コストは１Ｍ＋Ｉ（Ｆｐ＾３ｍ換算）である。
【００４６】
（４）アフィン表現から射影表現への変換
アフィン表現から射影表現への変換式は、上記（１０）式で表される。ここで、ｃ０、ｃ１、およびｃ２はＦｐ＾ｍの元であるため、変換コストは６Ｍ＋Ｉ（Ｆｐ＾ｍ換算）である。
【００４７】
以上の計算では、Ｆｐ＾３ｍ換算の変換コストと、Ｆｐ＾ｍ換算の変換コストとが混在しているため、Ｆｐ＾ｍ換算の変換コストに統一することを考える。Ｆｐ＾３ｍの変換コストと、Ｆｐ＾ｍ換算の変換コストとは、以下の関係を有する。
１Ｍ（Ｆｐ＾３ｍ換算）＝８Ｍ＋１５Ａ（Ｆｐ＾ｍ換算）
１Ａ（Ｆｐ＾３ｍ換算）＝３Ａ（Ｆｐ＾ｍ換算）
１Ｉ（Ｆｐ＾３ｍ換算）＝３Ｍ＋Ｉ（Ｆｐ＾ｍ換算）
【００４８】
したがって、上記（１）〜（４）の各変換の変換コストは、Ｆｐ＾ｍ換算で、それぞれ６Ａ、４３Ｍ＋８４Ａ＋Ｉ、１１Ｍ＋１５Ａ＋Ｉ、および６Ｍ＋１Ａとなる。そして、これらの合計は、６０Ｍ＋１０６Ａ＋２Ｉとなる。
【００４９】
すなわち、表現変換全体にかかる変換コストはＦｐ＾ｍ換算で６０Ｍ＋１０６Ａ＋２Ｉである。なお、逆元計算１回にかかるコストはｍＭ（Ｆｐ＾ｍ換算）＋拡張ユークリッドの互除法１回分程度である。
【００５０】
一方、べき乗の計算コストは、１６０ビット程度のべき指数を考えた場合、単純な方法では２乗算１６０回、乗算８０回程度のＦｐ＾６ｍの演算が必要となる。Ｆｐ＾６ｍの乗算１回の計算コストは、Ｆｐ＾ｍ換算で約２４Ｍ＋６０Ａである。このため、乗算４〜５回程度で一連の変換コスト分に相当することになる。２乗算は乗算の７割程度で計算できるので、この値を用いたとしても、べき乗全体で４０００Ｍ分以上（Ｆｐ＾ｍ換算）の計算が必要となる。
【００５１】
すなわち、従来の方法では、代数的トーラスの元であるか否かを判定するために４０００Ｍ以上の計算コストが必要であったのに対し、本実施の形態の方法によれば、計算コストを６０Ｍ＋１０６Ａ＋２Ｉに低減することができる。
【００５２】
このように、第１の実施の形態にかかる判定装置では、拡大体表現のデータをアフィン表現に変換し、さらにアフィン表現に変換したデータを拡大体表現に復元する。そして、復元したデータと元の拡大体表現のデータとが一致する場合に、元の拡大体表現のデータが代数的トーラスの元であると判定する。このような処理を行うことにより、拡大体表現で与えられた元が代数的トーラスの要素となっているか否かを、より小さい計算コストで容易に判定することが可能となる。
【００５３】
（第２の実施の形態）
第１の実施の形態では、入力された元を拡大体表現からアフィン表現へと変換し、さらにアフィン表現から拡大体表現へと復元していた。第２の実施の形態にかかる判定装置は、アフィン表現から拡大体表現への復元処理を行うことなく、アフィン表現に変換する過程で得られる係数を用いて代数的トーラスの元となるか否かを判定する。
【００５４】
図４は、第２の実施の形態にかかる判定装置２００のブロック図である。図４に示すように、判定装置２００は、入力部１０１と、第１変換部２０２と、抽出部２０５と、判定部２０４と、を備えている。
【００５５】
第２の実施の形態では、第１変換部２０２および判定部２０４の機能と、第２変換部１０３の代わりに抽出部２０５を追加したことと、が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる判定装置１００の構成を表すブロック図である図２と同様であるので、同一符号を付し、ここでの説明は省略する。
【００５６】
第１変換部２０２は、拡大体表現データを射影表現で表された射影表現データに変換する。また、第１変換部２０２は、射影表現データをアフィン表現で表されたアフィン表現データに変換する。
【００５７】
抽出部２０５は、第１変換部２０２が射影表現からアフィン表現に変換する過程で得られる複数の中間データを抽出する。以下に、抽出部２０５が抽出する中間データの具体例について説明する。
【００５８】
拡大体表現と射影表現との間には、（α，β）＝（α’＋１，−β）という関係がある。また、射影表現とアフィン表現との間には、γ＝α／β、γ＝ｃ０＋ｃ１ｙ＋ｃ２ｙ２という関係がある。ここで、（α’，β’）は拡大体表現の元、（α，β）は射影表現の元、および（ｃ０，ｃ１）はアフィン表現の元とする。
【００５９】
抽出部２０５は、上式（γ＝ｃ０＋ｃ１ｙ＋ｃ２ｙ２）の係数であるｃ０，ｃ１，およびｃ２を、変換過程で得られる中間データとして抽出する。
【００６０】
判定部２０４は、複数の中間データが予め定められた条件を満たすか否かを判定し、条件を満たさない場合に、拡大体表現データが代数的トーラス上の元でないと判定する。具体的には、判定部２０４は、抽出部２０５によって抽出されたｃ０，ｃ１，およびｃ２が、上記（９）式の関係を満たすか否かを判定し、満たさない場合に、拡大体表現データが代数的トーラス上の元でないと判定する。
【００６１】
次に、このように構成された第２の実施の形態にかかる判定装置２００による判定処理について図５を用いて説明する。図５は、第２の実施の形態における判定処理の全体の流れを示すフローチャートである。
【００６２】
まず、入力部１０１が、拡大体表現の元（拡大体表現データ）を入力する（ステップＳ５０１）。次に、第１変換部２０２が、入力された元を射影表現の元（射影表現データ）に変換する（ステップＳ５０２）。さらに、第１変換部２０２が、射影表現データをアフィン表現の元（アフィン表現データ）に変換する（ステップＳ５０３）。このとき、抽出部２０５が、射影表現からアフィン表現への変換過程で得られる係数ｃ０，ｃ１，およびｃ２を抽出する（ステップＳ５０４）。
【００６３】
次に、判定部２０４が、抽出された係数のうちｃ０およびｃ１を以下の（１５）式に入力することにより、出力値ｋを算出する（ステップＳ５０５）。
【数１３】
2010156872.tif 000015
【００６４】
次に、判定部２０４は、算出されたｋが、抽出された係数のうちｃ２と一致するか否かを判断する（ステップＳ５０６）。ｋとｃ２とが一致しない場合（ステップＳ５０６：ＮＯ）、判定部２０４は、入力された元が代数的トーラスの元ではないと判定する（ステップＳ５０７）。ｋとｃ２とが一致する場合（ステップＳ５０６：ＹＥＳ）、判定部２０４は、入力された元が代数的トーラスの元であると判定する（ステップＳ５０８）。
【００６５】
なお、抽出する係数（中間データ）を（ｃ０，ｃ１）としたが、（ｃ０，ｃ２）や（ｃ１，ｃ２）を抽出するように構成してもよい。この場合、抽出する係数に合わせて（１５）式を適宜変形して判定に用いればよい。
【００６６】
また、拡大体表現ではなく射影表現のデータが入力された場合も、同様の処理により代数的トーラスの元となるかを確認できる。この場合はステップＳ５０１で拡大体表現ではなく射影表現の元を入力し、ステップＳ５０２の変換処理を省略すればよい。
【００６７】
また、表現の変換処理や判定処理で正常に値が計算できないときに、処理を中断し、判定部２０４が、入力された元が代数的トーラスの元ではないと判定するように構成してもよい。例えば、ｃ１が０（零元）の場合、零元の逆元が計算できないため、ステップＳ５０５でｋを算出することができない。このような場合は、判定部２０４は、処理を中断し、入力された元が代数的トーラスの元でないと判定する。
【００６８】
このように、第２の実施の形態にかかる判定装置では、射影表現からアフィン表現に変換する過程で得られる係数を用いて代数的トーラスの元となるか否かを判定することができる。このため、代数的トーラスの元であるか否かの判定処理の計算コストをさらに低減することができる。
【００６９】
（第３の実施の形態）
第２の実施の形態では、代数的トーラスの元であるか否かを確実に判定できない場合が存在する。例えば、入力された拡大体表現の元を射影表現へと変換したときに、元々は代数的トーラスの元ではなかった元が、代数的トーラスの元に強制的に変換された場合である。この場合、射影表現に変換された元をアフィン表現に変換する過程で得られる係数を用いて判定処理を実行すると、入力された拡大体表現の元が代数的トーラスの元であると判定される。すなわち、全体としては誤った判定を下すことになる。
【００７０】
このような事態を回避するため、第３の実施の形態にかかる判定装置は、係数を用いた判定により射影表現の元が代数的トーラスの元であると判定された場合に、さらに、射影表現を拡大体表現に復元し、入力された拡大体表現の元と比較する。そして、両者が一致する場合にのみ、入力された拡大体表現の元が代数的トーラスの元であると判定する。
【００７１】
図６は、第３の実施の形態にかかる判定装置３００のブロック図である。図６に示すように、判定装置３００は、入力部１０１と、第１変換部２０２と、第２変換部３０３と、抽出部２０５と、判定部３０４と、を備えている。
【００７２】
第３の実施の形態では、第２変換部３０３を追加したことと、判定部３０４の機能と、が第２の実施の形態と異なっている。その他の構成および機能は、第２の実施の形態にかかる判定装置２００の構成を表すブロック図である図４と同様であるので、同一符号を付し、ここでの説明は省略する。
【００７３】
判定部３０４は、第２の実施の形態の判定部２０４の機能に加えて、後述する第２変換部３０３による変換結果である拡大体表現の元と、入力された拡大体表現とを比較し、両者が一致する場合に、入力された拡大体表現の元が代数的トーラスの元であると判定する機能を備えている。
【００７４】
第２変換部３０３は、判定部３０４によって、係数ｃ０とｃ１とから算出された出力値ｋと、係数ｃ２とが一致すると判定された場合に、射影表現に変換された元を、拡大体表現で表された拡大体表現データ（第２拡大体表現データ）に変換する。なお、判定部３０４は、このようにして変換された拡大体表現データ（第２拡大体表現データ）と、入力された拡大体表現の元（第１拡大体表現データ）とを比較する。
【００７５】
次に、このように構成された第３の実施の形態にかかる判定装置３００による判定処理について図７を用いて説明する。図７は、第３の実施の形態における判定処理の全体の流れを示すフローチャートである。
【００７６】
ステップＳ７０１からステップＳ７０７までの、入力処理、射影表現への変換処理、アフィン表現への変換処理、係数判定処理は、第２の実施の形態にかかる判定装置２００におけるステップＳ５０１からステップＳ５０７までと同様の処理なので、その説明を省略する。
【００７７】
ステップＳ７０６でｋとｃ２とが一致すると判断された場合（ステップＳ７０６：ＹＥＳ）、第２変換部３０３が、射影表現に変換した元（射影表現データ）を、拡大体表現の元（第２拡大体表現データ）に変換する（ステップＳ７０８）。
【００７８】
次に、判定部３０４は、変換された拡大体表現の元（第２拡大体表現データ）と、入力された拡大体表現の元（第１拡大体表現データ）とを比較する（ステップＳ７０９）。両者が一致しない場合（ステップＳ７０９：ＮＯ）、判定部３０４は、入力された元が代数的トーラスの元でないと判定する（ステップＳ７０７）。両者が一致する場合（ステップＳ７０９：ＹＥＳ）、判定部３０４は、入力された元が代数的トーラスの元であると判定する（ステップＳ７１０）。
【００７９】
このように、第３の実施の形態にかかる判定装置では、第１の実施の形態と同様の方法により、拡大体表現から射影表現への変換および復元を行った後、射影表現への変換前の元と復元された元とが一致するか否かにより、拡大体表現の元が代数的トーラスの元であるか否かを判定する。これにより、代数的トーラスの元であるか否かを正確に判定することができる。
【００８０】
次に、第１〜第３の実施の形態にかかる判定装置のハードウェア構成について図８を用いて説明する。図８は、第１〜第３の実施の形態にかかる判定装置のハードウェア構成図である。
【００８１】
第１〜第３の実施の形態にかかる判定装置は、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ（Random Access Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、ＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）ドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置と、各部を接続するバス６１を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００８２】
第１〜第３の実施の形態にかかる判定装置で実行される判定プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【００８３】
また、第１〜第３の実施の形態にかかる判定装置で実行される判定プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１〜第３の実施の形態にかかる判定装置で実行される判定プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【００８４】
また、第１〜第３の実施の形態の判定プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【００８５】
第１〜第３の実施の形態にかかる判定装置で実行される判定プログラムは、上述した各部（入力部、第１変換部、第２変換部、判定部等）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１（プロセッサ）が上記記憶媒体から判定プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上述した各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【００８６】
以上のように、本発明にかかる装置、方法およびプログラムは、公開鍵暗号等で用いられる有限体の乗法群の部分群の元であるか否かを判定する装置、方法およびプログラムに適している。
【図面の簡単な説明】
【００８７】
【図１】第１の実施の形態で利用する原理を説明するための図である。
【図２】第１の実施の形態にかかる判定装置のブロック図である。
【図３】第１の実施の形態における判定処理の全体の流れを示すフローチャートである。
【図４】第２の実施の形態にかかる判定装置のブロック図である。
【図５】第２の実施の形態における判定処理の全体の流れを示すフローチャートである。
【図６】第３の実施の形態にかかる判定装置のブロック図である。
【図７】第３の実施の形態における判定処理の全体の流れを示すフローチャートである。
【図８】第１〜第３の実施の形態にかかる判定装置のハードウェア構成図である。
【符号の説明】
【００８８】
５１  ＣＰＵ
５２  ＲＯＭ
５３  ＲＡＭ
５４  通信Ｉ／Ｆ
６１  バス
１０  拡大体表現
２０  射影表現
３０  アフィン表現
１１，２１  代数的トーラス
１２，１３，２２，２３，２４，３１  元
１００，２００，３００  判定装置
１０１  入力部
１０２，２０２  第１変換部
１０３，３０３  第２変換部
１０４，２０４，３０４  判定部
２０５  抽出部
【図１】
2010156872.tif 000016
【図２】
2010156872.tif 000017
【図３】
2010156872.tif 000018
【図４】
2010156872.tif 000019
【図５】
2010156872.tif 000020
【図６】
2010156872.tif 000021
【図７】
2010156872.tif 000022
【図８】
2010156872.tif 000023