代数的トーラスを用いたデータ圧縮処理を行う装置およびプログラム
【課題】圧縮できない例外点が現れた場合であっても適切に処理を実行できる情報処理装置を提供すること。
【解決手段】代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる代数的トーラス上の元を表す対象元が、圧縮写像によって圧縮できない代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、圧縮部は、対象元が例外点であると判定された場合に、対象元が例外点であることを表す例外情報を含む処理結果を生成し、対象元が例外点でないと判定された場合に、対象元を圧縮写像によって圧縮したアフィン表現を含む処理結果を生成することを特徴とする。
【解決手段】代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる代数的トーラス上の元を表す対象元が、圧縮写像によって圧縮できない代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、圧縮部は、対象元が例外点であると判定された場合に、対象元が例外点であることを表す例外情報を含む処理結果を生成し、対象元が例外点でないと判定された場合に、対象元を圧縮写像によって圧縮したアフィン表現を含む処理結果を生成することを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、有限体の乗法群の部分群の上で定義された離散対数問題の困難性を安全性の根拠とする公開鍵暗号方式などのように代数的トーラスを用いてデータ長を圧縮する処理を実行する装置およびプログラムに関する。
【背景技術】
【０００２】
離散対数問題は、巡回群Ｇ＝＜ｇ＞においてｙ∈Ｇが与えられたときに、ｙ＝ｇｘを満たすｘを求める問題である。巡回群Ｇとしては、有限体の乗法群や楕円曲線の有理点のなす加法群（ヤコビ群）が用いられる。これらの問題は、公開鍵暗号を構成するために利用される。これらの問題を解くアルゴリズムには、シャンクのアルゴリズムやポラードのρ法のようにいずれの巡回群上で定義された離散対数問題に対しても適用可能なものと、位数計算法にように有限体の乗法群上で定義された離散対数問題のみに適用可能なものが存在する。
【０００３】
位数計算法は効率的であるため、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は解読されやすい。したがって、同じ安全性を確保するために、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は、楕円曲線上の離散対数問題を用いた公開鍵暗号よりも鍵長や暗号文長を大きくする必要がある。
【０００４】
そこで、代数的トーラスを利用することにより、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する暗号圧縮技術が提案されている（例えば、非特許文献１）。代数的トーラスは、有限体の乗法群の部分群として定義される。代数的トーラスは、元の表現を圧縮することができる。これにより、有限体の乗法群上の離散対数問題を用いた公開鍵暗号における鍵長や暗号文長が大きいという問題を解消することが可能である。
【０００５】
例えば、（１）式で表される有限体の元は、（２）式で表される有限体の６つの成分を用いて（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）と表現される。ここでａｉ（ｉ＝１〜６）は、（２）式の有限体の元である。これに対して、（３）式で表される６次のトーラスは、（１）式の有限体に含まれる巡回群であって、その元は、（２）式の有限体の２つの成分を用いて表現される。この表現をａｆｆｉｎｅ表現（アフィン表現）と呼ぶ。このように、公開鍵暗号の鍵や暗号文がこのトーラスの元の場合には、長さを１／３に圧縮することができる。
【数１】
【０００６】
なお、以下では、（１）式のような有限体をＦｑ＾６と表記する場合がある。
【０００７】
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”、ＣＲＹＰＴＯ ２００３、Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ２７２９、３４９−３６５、２００３．
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、Ｔ６（Ｆｑ）には、アフィン表現に圧縮できない元を表す例外点が存在し、例外点はそれ以外の点と同じように表現できないという問題がある。非特許文献１では、例外点が現れた場合、暗号化が失敗するが、例外点が現れる確率は小さいため無視することが記載されている。しかし、公開鍵暗号における乗算、平方、べき乗、逆元、Ｆｒｏｂｅｎｉｕｓ写像などの演算では、確率は小さくても通常点を例外点に写像する場合があるので、暗号文や公開鍵として例外点を用いないようにすることはできない。
【０００９】
なお、トーラスの元をｅｘｔｅｎｓｉｏｎ ｆｉｅｌｄ表現（拡大体表現、詳細は後述）またはｐｒｏｊｅｃｔｉｖｅ表現（射影表現、詳細は後述）で表現すれば、例外点も表現できるため上記の問題は生じない。しかし、アフィン表現ではないため圧縮の効果が得られない。
【００１０】
本発明は、上記に鑑みてなされたものであって、非特許文献１の暗号圧縮技術のように代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても、適切に処理を実行できる装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するために、本発明は、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、を特徴とする。
【００１２】
また、本発明は、コンピュータを、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、を特徴とする。
【００１３】
また、本発明は、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、乱数を生成し、生成した乱数を用いて予め定められた演算を実行し、圧縮の対象となる前記代数的トーラス上の元を表す対象元を生成する演算部と、前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、前記演算部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点でないと判定されるまで、乱数を新たに生成し、新たに生成した乱数を用いて前記演算を実行して前記対象元を生成し、前記圧縮部は、前記例外点でないと判定された前記対象元を前記圧縮写像によってアフィン表現に圧縮すること、を特徴とする。
【００１４】
また、本発明は、代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、を備え、前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、を特徴とする。
【００１５】
また、本発明は、コンピュータを、代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、を特徴とする。
【発明の効果】
【００１６】
本発明によれば、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても、適切に処理を実行することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明にかかる装置およびプログラムの最良な実施の形態を詳細に説明する。
【００１８】
（第１の実施の形態）
第１の実施の形態では、代数的トーラスを用いた公開鍵暗号方式による暗号処理システムを構成する暗号化装置または復号装置として本発明の情報処理装置を実現した例について説明する。適用可能な装置はこれに限られず、代数的トーラスを用いてデータ長を圧縮する処理を実行する装置であればあらゆる装置に適用できる。
【００１９】
第１の実施の形態にかかる暗号処理システムでは、暗号化装置が、アフィン表現に圧縮する対象となるトーラス上の元である対象元が例外点であるか否かを判定し、例外点の場合は対象元を圧縮せず、例外点であることを表す情報を含む暗号文を生成する。そして、復号装置は、例外点であることを表す情報を元に暗号文を復元する。
【００２０】
ここで、本実施の形態で用いる用語の定義等について説明する。
（定義１：体）環ｋは、零元０（加法に関する単位元）を除く、以下の（４）式で表される集合ｋ＊に関して環となるとき、体（field）であるという。有限個の元からなる体を有限体（finite field）といい、上述のようにＦｑと表す。ここで、ｑは元の個数であり、その有限体の位数（order）と呼ばれる。ｑは素数のべき乗（素べき）となる。すなわち、ｑは素数ｐと正整数ｎによりｑ＝ｐｎと表される。
【数２】
【００２１】
（定義２：乗法群）群Ｇの演算が乗法のとき、Ｇを乗法群（multiplicative group）という。
【００２２】
（定義３：体の乗法群）体ｋの元のうち、０以外の元の集合は、乗法に関して群をなす。これを体ｋの乗法群（multiplicative group of field k）という。有限体Ｆｑの乗法群は、０以外の元から構成され、以下の（５）式で表される。
【数３】
【００２３】
（定義４：アフィン空間）ｋを体とする。集合｛（ａ１，ａ２， ・ ・ ・ , ａｎ） ｜ ａ１∈ｋ, ａ２∈ｋ, ・ ・ ・ , ａｎ∈ｋ｝を、体ｋ上のｎ次元アフィン空間（affine space）といい、以下の（６）式で表す。
【数４】
【００２４】
（定義５：代数的トーラス）代数的トーラス（algebraic torus）Ｔｎを、以下の（７）式のように定義する。
【数５】
ＲｅｓＫ／ｋは、体Ｋから体ｋへのスカラーのＷｅｉｌ ｒｅｓｔｒｉｃｔｉｏｎと呼ばれ、以下の（８）式で表される同形が成り立つ。
【数６】
【００２５】
（定理１）以下の（９）式および（１０）式の定理が成り立つ。
【数７】
【００２６】
（定義６：有理トーラス）ＴをＦｑ上の次元ｄの代数的トーラスとする。双有理写像（ｂｉｒａｔｉｏｎａｌ ｍａｐ）ρ：Ｔ→Ａｄが存在するとき、Ｔは有理（ｒａｔｉｏｎａｌ）であるという。すなわち、Ｔが有理であるとき、Ｚａｒｉｓｋｉ開部分集合Ｗ⊂Ｔ、Ｕ⊂Ａｄ（Ｆｑ）、有理関数ρ１, ・ ・ ・ , ρｄ∈Ｆｑ（ｘ１, ・ ・ ・ , ｘｔ）と、ψ１, ・ ・ ・ , ψｔ∈Ｆｑ（ｙ１, ・ ・ ・ , ｙｄ）が存在し、ρ＝（ρ１, ・ ・ ・ , ρｄ）:Ｗ→Ｕかつψ＝（ψ１, ・ ・ ・ , ψｔ）:Ｕ→Ｗである。
【００２７】
（例１：Ｔ６の有理パラメトライゼーション）ｘ∈Ｆｑ＾２−Ｆｑとする。Ｆｑ＾３のＦｑ基底を｛α１,α２,α３｝とする。｛α１,α２,α３,ｘα１,ｘα２,ｘα３｝は、Ｆｑ＾６のＦｑ基底となる。σ∈Ｇａｌ（Ｆｑ＾６／Ｆｑ）を位数２の元とする。具体的には、以下の（１１）式とする。また、以下の（１２）式で表されるψ０を、以下の（１３）式で定義する。
【数８】
ここで、γ＝ｕ１α１＋ｕ２α２＋ｕ３α３とする。ｘ∈Ｆｑ＾２であるため、以下の（１４）式が成り立つ。
【数９】
【００２８】
１．以下の（１５）式および（１６）式を用いると、すべてのｕ＝（ｕ１, ｕ２, ｕ３）に対して、以下の（１７）式が成り立つ。
【数１０】
【００２９】
２．Ｕを以下の（１８）式で定義すると、以下の（１９）式が成り立つ。また、Ｈｉｌｂｅｒｔの定理９０より、Ｔ６（Ｆｑ）−｛１｝の元はすべてψ０の像に含まれる。よって、以下の（２０）式が成り立つ。
【数１１】
【００３０】
Ｕは、ｕ１、ｕ２、ｕ３の２次方程式で定義された、Ａ３の中の超曲面である。一点ａ＝（ａ１，ａ２，ａ３）∈Ｕ（Ｆｑ）をとる。（α１,α２,α３）を適当にとると、ａにおけるＵの接平面をｕ１＝ａ１とすることができる。（ｖ１,ｖ２）∈Ｆｑ×Ｆｑに対して、Ｕと直線ａ＋（１,ｖ１,ｖ２）／ｔは、２個の交点を持つ。一方はｕ＝ａ、他方はｔ＝ｆ（ｖ１,ｖ２）である。ここで、ｆ（ｖ１,ｖ２）＝１−ｖ１２−ｖ２２＋ｖ１ｖ２である。（ｖ１,ｖ２）から２番目の点への写像ｇは、以下の（２１）式で示すように同形である。
【数１２】
【００３１】
ここで、ｖ（ｆ）は、ｆ（ｖ１,ｖ２）＝０で定義されるＡ２の部分多様体である。また、以下の（２２）式で示すように、ψ＝ψ０○ｇは同形である。ここで、記号「○」は写像の合成を表す。
【数１３】
【００３２】
β＝β１＋β２ｘ∈Ｔ６（Ｆｑ）−｛１,ψ０（ａ）｝とする。また、β１,β２∈Ｆｑ＾３とする。さらに、γ＝（１＋β１）／β２とすると、以下の（２３）式が成り立つ。
【数１４】
【００３３】
また、γ＝ｕ１α１＋ｕ２α２＋ｕ３α３とし、ρ（β）を以下の（２４）式で表すと、以下の（２５）式の写像ρは、同形ψの逆写像である。
【数１５】
【００３４】
（定理２）上述の写像ρとψは、Ｔ６とＡ２の間の双有理写像とその逆写像を与える。
【００３５】
（例２）ｑ≡２ ｏｒ ５ （ｍｏｄ ９）とする。また、ｘ＝ζ３、ｙ＝ζ９＋ζ９−１とすると、Ｆｑ＾６＝Ｆｑ（ζ９）、Ｆｑ＾２＝Ｆｑ（ｘ）、Ｆｑ＾３＝Ｆｑ（ｙ）である。Ｆｑ＾３のための基底を｛１,ｙ,ｙ２−２｝とする。また、ａ＝（０，０，０）とすると、以下の（２６）式が成り立つ。
【数１６】
【００３６】
Ｕを定義する方程式は、以下の（２７）式である。この方程式を解くと、以下の（２８）式が成り立つ。
【数１７】
【００３７】
ここで、基底に関して以下の（２９）式〜（３１）式を用い、Ｆｒｏｂｅｎｉｕｓ写像に関して以下の（３２）式および（３３）式を用いる。
【数１８】
【００３８】
ここで、γ＝ｕ１＋ｕ２ｙ＋ｕ３(ｙ２−２）を（２８）式に代入する。以下の（３４）式および（３５）式より、（３６）式が成り立つ。
【数１９】
【００３９】
これと直線ｕ＝ａ＋（１,ｖ１,ｖ２）／ｔとの交点は、ａと、ｔ＝ｆ（ｖ１,ｖ２）＝１−ｖ１２−ｖ２2＋ｖ１ｖ２≡ｆ（ｖ１,ｖ２）で与えられる。よって、以下の（３７）式が成り立つ。
【数２０】
【００４０】
逆写像は、β＝β１＋β２ｘ∈Ｔ６（Ｆｑ）−｛１、ｘ２｝に対して、（１＋β１）／β２＝ｕ１＋ｕ２ｙ＋ｕ３（ｙ２−２）とすると、以下の（３８）式のρ（β）で表される。
【数２１】
【００４１】
（定義７：拡大体表現）ｚ＝ζ９とするとき、以下の（３９）式を、Ｔ６（Ｆｑ）の拡大体表現という。
【数２２】
【００４２】
（定義８：射影表現）ｘ＝ζ３とするとき、以下の（４０）式を、Ｔ６（Ｆｑ）の射影表現という。
【数２３】
【００４３】
（定義９：ａｆｆｉｎｅ表現）ｘ＝ζ３とするとき、以下の（４１）式を、Ｔ６（Ｆｑ）のａｆｆｉｎｅ表現という。
【数２４】
【００４４】
（定義１０：例外点と通常点）以下の（４２）式で示すような、代数的トーラスＴ６（Ｆｑ）からアフィン空間Ａ２（Ｆｑ）への有理写像ψと、その逆写像ρが定義されている。
【数２５】
【００４５】
このとき、１、ψ０（ａ）＝ｘ２∈Ｔ６（Ｆｑ）を例外点と呼ぶ。このような例外点１およびψ０（ａ）は、写像ρによっては圧縮できない。また、例外点以外のＴ６（Ｆｑ）の元を通常点と呼ぶ。通常点は、写像ρによって、Ａ２（Ｆｑ）の元として表現できる。すなわち、通常点は１／３の長さに圧縮できる。
【００４６】
次に、第１の実施の形態にかかる暗号処理システムの構成について説明する。図１は、第１の実施の形態にかかる暗号処理システムのブロック図である。図１に示すように、第１の実施の形態にかかる暗号処理システムは、暗号化装置１００と、復号装置２００とを含んでいる。
【００４７】
最初に、暗号化装置１００の構成について説明する。暗号化装置１００は、代数的トーラスを用いた公開鍵暗号方式で平文を暗号化する装置であり、入力部１０１と、暗号化処理部１０２と、判定部１０３と、圧縮部１０４と、記憶部１２１と、を備えている。
【００４８】
入力部１０１は、平文データや、暗号化に用いる公開鍵暗号方式の暗号鍵データ（以下、公開鍵データという）などを入力する。記憶部１２１は、入力された平文データや公開鍵データなどを保存する。
【００４９】
暗号化処理部１０２は、平文データに対して公開鍵データを用いて、有限体上の離散対数問題に基づいた暗号化処理を施して複数の要素を含む暗号文データを出力する。具体的には、暗号化処理部１０２は、有限体上の離散対数問題に基づく暗号化方式として、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて平文データに暗号化処理を施して暗号文データを出力する。以下では、暗号化処理部１０２が、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式で平文データを暗号化するものとして説明する。
【００５０】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。図２で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ〜，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００５１】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文データｍに対応する暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖ
を求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００５２】
復号処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）から正当な平文データであるか否かをチェックし、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ〜）は、ｃが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００５３】
このように、暗号化処理部１０２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式によって４つの要素からなる暗号文データｃ１，ｃ２，ｃ３，ｃ４を出力する。ｃ１，ｃ２，ｃ３，ｃ４は、それぞれ代数的トーラスの元であり、拡大体表現の場合は、各要素がそれぞれａ１＋ａ２ｘ＋ａ３ｙ＋ａ４ｘｙ＋ａ５（ｙ２−２）＋ａ６ｘ（ｙ２−２）のように表される。ここで、各ａｉはＦｑの元である。上述のように、この拡大体表現はａｉのみを用いて（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）と表してもよい。
【００５４】
暗号文データの各要素が、後述する圧縮部１０４による圧縮の対象となる代数的トーラス上の元（対象元）となる。
【００５５】
判定部１０３は、暗号化処理部１０２が出力した暗号文データに含まれる各要素が、上述した代数的トーラス上の例外点であるか否かを判定する。また、判定部１０３は、例外点であると判定した要素が、代数的トーラス上の複数の例外点のうち、いずれの例外点であるかを判定する。
【００５６】
圧縮部１０４は、非特許文献１のような代数的トーラスを利用した暗号圧縮技術によって暗号文データを圧縮した圧縮暗号文データを出力する。具体的には、圧縮部１０４は、判定部１０３が例外点でないと判定した暗号文データの要素を、上述の双有理写像ρによって拡大体表現からアフィン表現に圧縮し、圧縮したアフィン表現と、圧縮の対象となった対象元が通常点であることを表す情報を含む処理結果を生成する。
【００５７】
このように、本実施の形態では、圧縮部１０４は、圧縮したアフィン表現だけでなく、対象元が通常点であるか例外点であるかを表す情報を含む処理結果を生成する。例えば、圧縮部１０４は、処理結果中の所定の１ビットを通常点であるか例外点であるかを表すビット（例外情報ビット）とする。そして、例えば例外情報ビットが０の場合は通常点であることを表し、１の場合は例外点であることを表す。
【００５８】
判定部１０３が例外点であると判定した要素に対しては、圧縮部１０４は、例外情報ビットと、いずれの例外点であるかを識別する識別情報とを含む処理結果を生成する。例えば、処理結果中で例外情報ビットと異なる所定の１ビットを、いずれの例外点であるかを表すビット（識別情報ビット）とする。そして、例えば識別情報ビットが０の場合は例外点が１であることを表し、１の場合は例外点ψ０（ａ）を表す。
【００５９】
なお、通常点の場合に圧縮して得られるアフィン表現を格納するビット列に含まれるいずれか１ビットを、識別情報ビットとして利用するように構成してもよい。これは、通常点であって、かつ、例外点であるような場合は生じないからである。
【００６０】
また、アフィン表現はＡ２（Ｆｑ）の全てをとりえるわけではないため、上述の部分多様体ｖ（ｆ）に含まれる点を使って例外点を表現するように構成してもよい。例えば、（Ａ１，Ａ２）と（Ｂ１，Ｂ２）とがｖ（ｆ）の元であるならば、（Ａ１，Ａ２）および（Ｂ１，Ｂ２）が、それぞれ例外点１および例外点ψ０（ａ）を表すものとすればよい。この場合、出力される情報のサイズはアフィン表現のサイズと同じである。
【００６１】
圧縮部１０４は、このようにして暗号文データの各要素に対して生成した処理結果を圧縮暗号文データとして出力する。また、出力された圧縮暗号文データは、外部装置との間でデータを送受信する送受信部（図示せず）などによって、復号装置２００に送信される。
【００６２】
次に、復号装置２００の構成について説明する。復号装置２００は、代数的トーラスを用いた公開鍵暗号方式で暗号化された暗号文データを復元する装置であり、入力部２０１と、判定部２０２と、伸長部２０３と、復号処理部２０４と、記憶部２２１と、を備えている。
【００６３】
入力部２０１は、暗号化装置１００から送信された圧縮暗号文データや、復号化に用いる公開鍵暗号方式の秘密鍵データなどを入力する。記憶部２２１は、入力された圧縮暗号文データや秘密鍵データなどを保存する。
【００６４】
判定部２０２は、圧縮暗号文データの各要素に含まれる例外情報ビットが０（通常点）であるか、１（例外点）であるかを判定する。これは、暗号化装置１００の圧縮部１０４が当該要素を得るために圧縮の対象とした対象元が例外点であるか否かを判定することを意味する。
【００６５】
伸長部２０３は、代数的トーラスを利用した暗号圧縮技術によって圧縮された暗号文データを伸長する。具体的には、伸長部２０３は、判定部２０２が例外情報ビット＝０（通常点）と判定した場合に、暗号文データの要素を、上述の双有理写像ρの逆写像ψによってアフィン表現から拡大体表現に伸長する。なお、以下では逆写像ψを伸長写像という。
【００６６】
判定部２０２が例外情報ビット＝１（例外点）と判定した場合は、伸長部２０３は、識別情報ビットで識別される例外点に対応する、拡大体表現で表された所定の元を、暗号文データの要素に対する伸長結果として生成する。
【００６７】
復号処理部２０４は、伸長部２０３で伸長された暗号文データの要素それぞれに対して、記憶部２２１に記憶された秘密鍵データを用いて、有限体上の離散対数問題に基づいた復号化処理を施して平文データを出力する。具体的には、復号処理部２０４は、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算または暗号文データを入力値として用いるハッシュ関数を用いて、暗号文データに復号化処理を施して平文データを得る。
【００６８】
なお、暗号化装置１００の記憶部１２１および復号装置２００の記憶部２２１は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００６９】
次に、このように構成された第１の実施の形態にかかる暗号化装置１００による暗号化処理について図３を用いて説明する。図３は、第１の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【００７０】
なお、暗号化装置１００は、事前に公開鍵データおよび平文データを入力し、記憶部１２１等に記憶しているものとする。
【００７１】
まず、暗号化処理部１０２は、図２で示したように乱数ｒを生成する（ステップＳ３０１）。次に、暗号化処理部１０２は、公開鍵データに含まれるｇ〜、ｅ、ｆを用いて、生成した乱数ｒを乗数に用いたべき乗計算と乗算とを実行し、暗号文データの要素であるｃ１，ｃ２を求める（ステップＳ３０２）。次に、暗号化処理部１０２は、乗算により平文を加工し、暗号文データの要素であるｃ３を求める（ステップＳ３０３）。
【００７２】
次に、暗号化処理部１０２は、公開鍵データに含まれるｅ、ｆと乱数とを用いてハッシュ計算を行ってハッシュ値ｖを求める（ステップＳ３０４）次に、暗号化処理部１０２は、求めたハッシュ値ｖを乗数に用いたべき乗計算を行うことにより暗号文データの要素であるｃ４を求める（ステップＳ３０５）。そして、暗号化処理部１０２は、算出した暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を出力する（ステップＳ３０６）。
【００７３】
次に、判定部１０３は、受け取った暗号文データの要素のうち、未処理の要素を取得する（ステップＳ３０７）。そして、判定部１０３は、拡大体表現（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）で表された要素が例外点であるかを判定する例外点判定処理を実行する（ステップＳ３０８）。例外点判定処理の詳細については後述する。
【００７４】
次に、圧縮部１０４が、例外点判定処理の判定結果が例外点１または例外点ψ０（ａ）であることを表すか否かを判断する（ステップＳ３０９）。判定結果が例外点１または例外点ψ０（ａ）でないこと、すなわち、通常点であることを表す場合は（ステップＳ３０９：ＮＯ）、圧縮部１０４は、双有理写像ρにより暗号文データの要素を圧縮し、アフィン表現を生成する（ステップＳ３１０）。そして、圧縮部１０４は、通常点であることを表す情報を含む圧縮暗号文データの要素を出力する（ステップＳ３１１）。具体的には、圧縮部１０４は、例外情報ビット＝０であり、その他のビット列に圧縮したアフィン表現を含む圧縮暗号文データの要素を出力する。
【００７５】
ステップＳ３０９で、判定結果が例外点１または例外点ψ０（ａ）であると判断された場合は（ステップＳ３０９：ＹＥＳ）、圧縮部１０４は、例外点であることを表す情報と、いずれの例外点かを識別する識別情報を含む圧縮暗号文データの要素を出力する（ステップＳ３１２）。具体的には、圧縮部１０４は、判定結果が例外点１の場合は、例外情報ビット＝１、識別情報ビット＝０である圧縮暗号文データの要素を出力する。また、圧縮部１０４は、判定結果が例外点ψ０（ａ）の場合は、例外情報ビット＝１、識別情報ビット＝１である圧縮暗号文データの要素を出力する。
【００７６】
次に、圧縮部１０４は、暗号文データのすべての要素を処理したか否かを判断し（ステップＳ３１３）、処理していない場合は（ステップＳ３１３：ＮＯ）、次の未処理の要素を取得して処理を繰り返す（ステップＳ３０７）。すべての要素を処理した場合は（ステップＳ３１３：ＹＥＳ）、暗号化処理を終了する。
【００７７】
次に、ステップＳ３０８の例外点判定処理の詳細について図４を用いて説明する。図４は、第１の実施の形態における例外点判定処理の全体の流れを示すフローチャートである。
【００７８】
まず、判定部１０３は、暗号文データの要素が例外点１であるか否かを判断する（ステップＳ４０１）。具体的には、判定部１０３は、要素の拡大体表現（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）を用いて、ａ１＝１、かつ、ａ２＝ａ３＝ａ４＝ａ５＝ａ６＝０であるか否かを判断する。
【００７９】
要素が例外点１である場合は（ステップＳ４０１：ＹＥＳ）、判定部１０３は、例外点１であることを表す判定結果を出力し（ステップＳ４０２）、例外点判定処理を終了する。要素が例外点１でない場合は（ステップＳ４０１：ＮＯ）、判定部１０３は、さらに、要素が例外点ψ０（ａ）であるか否かを判断する（ステップＳ４０３）。具体的には、判定部１０３は、ａ１＝ａ２＝ｐ−１、かつ、ａ３＝ａ４＝ａ５＝ａ６＝０であるか否かを判断する。
【００８０】
要素が例外点ψ０（ａ）である場合は（ステップＳ４０３：ＹＥＳ）、判定部１０３は、例外点ψ０（ａ）であることを表す判定結果を出力し（ステップＳ４０４）、例外点判定処理を終了する。要素が例外点ψ０（ａ）でない場合は（ステップＳ４０３：ＮＯ）、判定部１０３は、要素が通常点であることを表す判定結果を出力し（ステップＳ４０５）、例外点判定処理を終了する。
【００８１】
なお、判定部１０３は拡大体表現を用いて例外点か否かを判定しているが、要素が射影表現で表されている場合であっても同様の判定が可能である。
【００８２】
次に、第１の実施の形態にかかる復号装置２００による復号処理について図５を用いて説明する。図５は、第１の実施の形態における復号処理の全体の流れを示すフローチャートである。
【００８３】
なお、復号装置２００には、暗号化装置１００が圧縮に用いた公開鍵データに対応する秘密鍵データが事前に入力され、記憶部２２１等に記憶されているものとする。
【００８４】
まず、入力部２０１は、復号の対象となる圧縮暗号文データを入力する（ステップＳ５０１）。例えば、入力部２０１は、暗号化装置１００から送信され、記憶部２２１に記憶された圧縮暗号文データを、当該記憶部２２１から入力する。
【００８５】
次に、復号処理部２０４は、入力された圧縮暗号文データの各要素が正しい群の元であるか否かを検査する（ステップＳ５０２）。具体的には、復号処理部２０４は、図２の（１１−１）および（１１−２）に示すように、各要素が群Ｇまたは群Ｇ〜に属することを検査する。
【００８６】
圧縮暗号文データの各要素が正しい群の元でない場合は（ステップＳ５０２：ＮＯ）、復号処理を終了する。圧縮暗号文データの各要素が正しい群の元である場合（ステップＳ５０２：ＹＥＳ）、伸長部２０３は、圧縮暗号文データの要素のうち、未処理の要素を取得する（ステップＳ５０３）。
【００８７】
次に、判定部２０２が、取得した要素に例外点であることを表す情報が含まれるか否かを判断する（ステップＳ５０４）。具体的には、判定部２０２は、取得した要素に含まれる例外情報ビットを参照し、例外情報ビットが１の場合に、例外点であることを表す情報が含まれると判断する。また、判定部２０２は、例外情報ビットが０の場合に、例外点であることを表す情報が含まれないと判断する。
【００８８】
例外点であることを表す情報が含まれない場合は（ステップＳ５０４：ＮＯ）、伸長部２０３は、伸長写像により圧縮暗号文データの要素を伸長する（ステップＳ５０５）。例外点であることを表す情報が含まれる場合は（ステップＳ５０４：ＹＥＳ）、伸長部２０３は、取得した要素に含まれる識別情報ビットで識別される例外点に対応する元を、伸長処理の結果として出力する（ステップＳ５０５）。
【００８９】
例えば、伸長部２０３は、取得した要素に含まれる識別情報ビットを参照し、識別情報ビットが０の場合に、例外点１に対応する拡大体表現の元（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）＝（１，０，０，０，０，０）を出力する。また、伸長部２０３は、識別情報ビットが１の場合に、例外点ψ０（ａ）に対応する拡大体表現の元（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）＝（ｐ−１，ｐ−１，０，０，０，０）を出力する。
【００９０】
ステップＳ５０５またはステップＳ５０６の後、伸長部２０３は、圧縮暗号文データのすべての要素を処理したか否かを判断する（ステップＳ５０７）。すべての要素を処理していない場合は（ステップＳ５０７：ＮＯ）、次の要素を取得して処理を繰り返す（ステップＳ５０３）。
【００９１】
すべての要素を処理した場合は（ステップＳ５０７：ＹＥＳ）、以下に示すように、復号処理部２０４が伸長した暗号文データを平文データに復号する（ステップＳ５０８〜ステップＳ５１１）。なお、すべての要素を伸長することにより、暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）が得られている。
【００９２】
まず、復号処理部２０４は、秘密鍵データと暗号文データの要素ｃ１，ｃ２，ｃ３とを用いてハッシュ関数によりハッシュ値ｖを算出する（ステップＳ５０８）。次に、復号処理部２０４は、ハッシュ値ｖと、暗号文データの要素ｃ１，ｃ２と、秘密鍵データとを用いて、べき乗計算と乗算とにより検査式に用いる値を計算する（ステップＳ５０９）。具体的には、復号処理部２０４は、図２の（１１−６）の検査式の右辺の値を計算する。
【００９３】
次に、復号処理部２０４は、検査式が成立するか否か、すなわち、計算した値と暗号文データの要素ｃ４とが一致するか否かを判断する（ステップＳ５１０）。検査式が成立しない場合は（ステップＳ５１０：ＮＯ）、復号処理を終了する。
【００９４】
検査式が成立する場合は（ステップＳ５１０：ＹＥＳ）、図２の（１１−３）、（１１−４）に示すように、暗号文データの要素ｃ１，ｃ２と秘密鍵データｚ１、ｚ２とを用いたべき乗計算、および、べき乗計算で得られた値と暗号文データの要素ｃ３とを用いた乗算を実行し、平文データｍを復号する（ステップＳ５１１）。
【００９５】
このように、第１の実施の形態にかかる暗号処理システムでは、暗号化装置が、アフィン表現に圧縮する対象となるトーラス上の元である対象元が例外点であるか否かを判定し、例外点の場合は圧縮せず、例外点であることを表す情報を含む暗号文を生成することができる。そして、復号装置は、例外点であることを表す情報を元に暗号文を復元することができる。これにより、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても適切に処理を実行することが可能となる。
【００９６】
また、例外点であることを表す情報は例えば１ビットで表すことができる。すなわち、圧縮したアフィン表現のデータ長と比較して十分に小さい。このため、例外点であることを表す情報を含めたとしても圧縮の効果に与える影響は小さい。
【００９７】
（第２の実施の形態）
第２の実施の形態にかかる暗号処理システムは、暗号化装置が、圧縮する対象となる対象元が例外点であるか否かを判定し、例外点の場合は、対象元が通常点となるまで、新たに生成した乱数を元に対象元を再計算する。復号装置は、暗号文が例外点であるか否かを判定することなく暗号文を復号する。
【００９８】
図６は、第２の実施の形態にかかる暗号処理システムの構成を示すブロック図である。図６に示すように、第２の実施の形態にかかる暗号処理システムは、暗号化装置６００と、復号装置７００とを含んでいる。
【００９９】
同図に示すように、第２の実施の形態にかかる暗号化装置６００は、入力部１０１と、暗号化処理部６０２と、判定部１０３と、圧縮部６０４と、記憶部１２１と、を備えている。
【０１００】
第２の実施の形態では、暗号化処理部６０２および圧縮部６０４の機能が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる暗号化装置１００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１０１】
暗号化処理部６０２は、第１の実施の形態の暗号化処理部１０２と同様に、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式などの有限体上の離散対数問題に基づいた暗号方式により、平文データを暗号化して暗号文データを出力する。第２の実施の形態では、暗号化処理部６０２が、判定部１０３によって暗号文データの要素が例外点であると判定された場合に、暗号文データを算出するための乱数を新たに生成し、暗号文データのすべての要素が通常点となるまで新たな乱数を用いて暗号文データを再度計算する点が、第１の実施の形態と異なっている。これにより、暗号化処理部６０２は、すべての要素が通常点である暗号文データを出力することができる。
【０１０２】
圧縮部６０４は、暗号化処理部６０２から出力された暗号文データを、代数的トーラスを利用した暗号圧縮技術によって圧縮した圧縮暗号文データを出力する。暗号化処理部６０２が例外点を要素に含まない暗号文データを出力するため、第２の実施の形態の圧縮部６０４は、要素が例外点であるか否かを判定することなく暗号文データを圧縮できる。また、これにより、圧縮部６０４は、例外情報ビットのように例外点であることを表す情報や、識別情報ビットのように例外点の種類を表す情報を含まず、圧縮したアフィン表現のみを含む処理結果を出力することができる。
【０１０３】
次に、復号装置７００の構成について説明する。第２の実施の形態にかかる復号装置７００は、入力部２０１と、伸長部７０３と、復号処理部２０４と、記憶部２２１と、を備えている。
【０１０４】
第２の実施の形態では、判定部２０２を削除したこと、および、伸長部７０３の機能が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる復号装置２００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１０５】
伸長部７０３は、代数的トーラスを利用した暗号圧縮技術によって圧縮された暗号文データを伸長する。第２の実施の形態では、圧縮されたアフィン表現のみを含む圧縮暗号文データが入力されるため、圧縮暗号文データが例外点に対応する要素を含むか否かを例外情報ビット等によって判定する必要がない。同様に、伸長部７０３が判定結果にしたがって伸長処理を変更する必要がない。すなわち、伸長部７０３は、圧縮暗号文データのすべての要素に対して伸長写像による伸長処理を実行する。
【０１０６】
次に、このように構成された第２の実施の形態にかかる暗号化装置６００による暗号化処理について図７を用いて説明する。図７は、第２の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【０１０７】
ステップＳ７０１からステップＳ７０９までの、乱数生成処理、暗号文算出処理、例外点判定処理、および結果判定処理は、第１の実施の形態にかかる暗号化装置１００におけるステップＳ３０１からステップＳ３０９までと同様の処理なので、その説明を省略する。
【０１０８】
ステップＳ７０９で、判定結果が例外点１または例外点ψ０（ａ）であると判断された場合は（ステップＳ７０９：ＹＥＳ）、暗号化処理部１０２は、暗号化に用いる乱数ｒを新たに生成し（ステップＳ７０１）、処理を繰り返す。
【０１０９】
判定結果が例外点１または例外点ψ０（ａ）でないと判断された場合は（ステップＳ７０９：ＮＯ）、圧縮部６０４は、暗号文データのすべての要素を処理したか否かを判断する（ステップＳ７１０）。すべての要素を処理していない場合は（ステップＳ７１０：ＮＯ）、次の未処理の要素を取得して処理を繰り返す（ステップＳ７０７）。
【０１１０】
すべての要素を処理した場合は（ステップＳ７１０：ＹＥＳ）、圧縮部６０４は、双有理写像ρにより暗号文データの各要素を圧縮し、アフィン表現を生成する（ステップＳ７１１）。
【０１１１】
このように、第２の実施の形態では、圧縮の対象となる対象元がすべて通常点となるまで乱数を再生成して処理を繰り返すため、双有理写像ρによって圧縮されたアフィン表現のみを要素として含む圧縮暗号文データを生成することができる。
【０１１２】
次に、このように構成された第２の実施の形態にかかる復号装置７００による復号処理について図８を用いて説明する。図８は、第２の実施の形態における復号処理の全体の流れを示すフローチャートである。
【０１１３】
ステップＳ８０１からステップＳ８０３までの、暗号文入力処理、元判定処理、および要素取得処理は、第１の実施の形態にかかる復号装置２００におけるステップＳ５０１からステップＳ５０３までと同様の処理なので、その説明を省略する。
【０１１４】
ステップＳ８０３で、圧縮暗号文データの未処理の要素を取得した後、伸長部７０３は、取得した要素を伸長写像により伸長する（ステップＳ８０４）。
【０１１５】
このように、第２の実施の形態では、圧縮暗号文データの要素に例外点であることを表す情報が含まれるか否かを判定し、含まれる場合に例外点に対応する元を出力する処理（図５のステップＳ５０４〜ステップＳ５０５）が不要となる。
【０１１６】
ステップＳ８０５からステップＳ８０９までの、完了判定処理および平文算出処理は、第１の実施の形態にかかる復号装置２００におけるステップＳ５０７からステップＳ５１１までと同様の処理なので、その説明を省略する。
【０１１７】
このように、第２の実施の形態にかかる暗号処理システムでは、暗号化装置が、圧縮する対象となる対象元が例外点であるか否かを判定し、例外点の場合は、対象元が通常点となるまで、新たに生成した乱数を元に対象元を再計算することができる。これにより、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても適切に処理を実行することが可能となる。また、これにより、復号装置は暗号文が例外点であるか否かを判定することなく暗号文を復号することができる。
【０１１８】
次に、第１および第２の実施の形態にかかる暗号化装置および復号装置のハードウェア構成について説明する。第１および第２の実施の形態にかかる暗号化装置および復号装置は、ＣＰＵ（Central Processing Unit）などの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆと、各部を接続するバスを備えている。
【０１１９】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、ＲＯＭ等に予め組み込まれて提供される。
【０１２０】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【０１２１】
さらに、第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１２２】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、上述した各部（入力部、暗号化処理部、判定部、圧縮部、または、入力部、判定部、伸長部、復号処理部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵがＲＯＭから情報処理プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０１２３】
以上のように、本発明にかかる装置およびプログラムは、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式のように、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化または復号化する装置に適している。
【図面の簡単な説明】
【０１２４】
【図１】第１の実施の形態にかかる暗号処理システムのブロック図である。
【図２】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図３】第１の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図４】第１の実施の形態における例外点判定処理の全体の流れを示すフローチャートである。
【図５】第１の実施の形態における復号処理の全体の流れを示すフローチャートである。
【図６】第２の実施の形態にかかる暗号処理システムの構成を示すブロック図である。
【図７】第２の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図８】第２の実施の形態における復号処理の全体の流れを示すフローチャートである。
【符号の説明】
【０１２５】
１００、６００ 暗号化装置
１０１ 入力部
１０２、６０２ 暗号化処理部
１０３ 判定部
１０４、６０４ 圧縮部
１２１ 記憶部
２００、７００ 復号装置
２０１ 入力部
２０２ 判定部
２０３、７０３ 伸長部
２０４ 復号処理部
２２１ 記憶部
【技術分野】
【０００１】
この発明は、有限体の乗法群の部分群の上で定義された離散対数問題の困難性を安全性の根拠とする公開鍵暗号方式などのように代数的トーラスを用いてデータ長を圧縮する処理を実行する装置およびプログラムに関する。
【背景技術】
【０００２】
離散対数問題は、巡回群Ｇ＝＜ｇ＞においてｙ∈Ｇが与えられたときに、ｙ＝ｇｘを満たすｘを求める問題である。巡回群Ｇとしては、有限体の乗法群や楕円曲線の有理点のなす加法群（ヤコビ群）が用いられる。これらの問題は、公開鍵暗号を構成するために利用される。これらの問題を解くアルゴリズムには、シャンクのアルゴリズムやポラードのρ法のようにいずれの巡回群上で定義された離散対数問題に対しても適用可能なものと、位数計算法にように有限体の乗法群上で定義された離散対数問題のみに適用可能なものが存在する。
【０００３】
位数計算法は効率的であるため、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は解読されやすい。したがって、同じ安全性を確保するために、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は、楕円曲線上の離散対数問題を用いた公開鍵暗号よりも鍵長や暗号文長を大きくする必要がある。
【０００４】
そこで、代数的トーラスを利用することにより、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する暗号圧縮技術が提案されている（例えば、非特許文献１）。代数的トーラスは、有限体の乗法群の部分群として定義される。代数的トーラスは、元の表現を圧縮することができる。これにより、有限体の乗法群上の離散対数問題を用いた公開鍵暗号における鍵長や暗号文長が大きいという問題を解消することが可能である。
【０００５】
例えば、（１）式で表される有限体の元は、（２）式で表される有限体の６つの成分を用いて（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）と表現される。ここでａｉ（ｉ＝１〜６）は、（２）式の有限体の元である。これに対して、（３）式で表される６次のトーラスは、（１）式の有限体に含まれる巡回群であって、その元は、（２）式の有限体の２つの成分を用いて表現される。この表現をａｆｆｉｎｅ表現（アフィン表現）と呼ぶ。このように、公開鍵暗号の鍵や暗号文がこのトーラスの元の場合には、長さを１／３に圧縮することができる。
【数１】
【０００６】
なお、以下では、（１）式のような有限体をＦｑ＾６と表記する場合がある。
【０００７】
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”、ＣＲＹＰＴＯ ２００３、Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ２７２９、３４９−３６５、２００３．
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、Ｔ６（Ｆｑ）には、アフィン表現に圧縮できない元を表す例外点が存在し、例外点はそれ以外の点と同じように表現できないという問題がある。非特許文献１では、例外点が現れた場合、暗号化が失敗するが、例外点が現れる確率は小さいため無視することが記載されている。しかし、公開鍵暗号における乗算、平方、べき乗、逆元、Ｆｒｏｂｅｎｉｕｓ写像などの演算では、確率は小さくても通常点を例外点に写像する場合があるので、暗号文や公開鍵として例外点を用いないようにすることはできない。
【０００９】
なお、トーラスの元をｅｘｔｅｎｓｉｏｎ ｆｉｅｌｄ表現（拡大体表現、詳細は後述）またはｐｒｏｊｅｃｔｉｖｅ表現（射影表現、詳細は後述）で表現すれば、例外点も表現できるため上記の問題は生じない。しかし、アフィン表現ではないため圧縮の効果が得られない。
【００１０】
本発明は、上記に鑑みてなされたものであって、非特許文献１の暗号圧縮技術のように代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても、適切に処理を実行できる装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するために、本発明は、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、を特徴とする。
【００１２】
また、本発明は、コンピュータを、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、を特徴とする。
【００１３】
また、本発明は、代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、乱数を生成し、生成した乱数を用いて予め定められた演算を実行し、圧縮の対象となる前記代数的トーラス上の元を表す対象元を生成する演算部と、前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、前記演算部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点でないと判定されるまで、乱数を新たに生成し、新たに生成した乱数を用いて前記演算を実行して前記対象元を生成し、前記圧縮部は、前記例外点でないと判定された前記対象元を前記圧縮写像によってアフィン表現に圧縮すること、を特徴とする。
【００１４】
また、本発明は、代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、を備え、前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、を特徴とする。
【００１５】
また、本発明は、コンピュータを、代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、を特徴とする。
【発明の効果】
【００１６】
本発明によれば、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても、適切に処理を実行することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明にかかる装置およびプログラムの最良な実施の形態を詳細に説明する。
【００１８】
（第１の実施の形態）
第１の実施の形態では、代数的トーラスを用いた公開鍵暗号方式による暗号処理システムを構成する暗号化装置または復号装置として本発明の情報処理装置を実現した例について説明する。適用可能な装置はこれに限られず、代数的トーラスを用いてデータ長を圧縮する処理を実行する装置であればあらゆる装置に適用できる。
【００１９】
第１の実施の形態にかかる暗号処理システムでは、暗号化装置が、アフィン表現に圧縮する対象となるトーラス上の元である対象元が例外点であるか否かを判定し、例外点の場合は対象元を圧縮せず、例外点であることを表す情報を含む暗号文を生成する。そして、復号装置は、例外点であることを表す情報を元に暗号文を復元する。
【００２０】
ここで、本実施の形態で用いる用語の定義等について説明する。
（定義１：体）環ｋは、零元０（加法に関する単位元）を除く、以下の（４）式で表される集合ｋ＊に関して環となるとき、体（field）であるという。有限個の元からなる体を有限体（finite field）といい、上述のようにＦｑと表す。ここで、ｑは元の個数であり、その有限体の位数（order）と呼ばれる。ｑは素数のべき乗（素べき）となる。すなわち、ｑは素数ｐと正整数ｎによりｑ＝ｐｎと表される。
【数２】
【００２１】
（定義２：乗法群）群Ｇの演算が乗法のとき、Ｇを乗法群（multiplicative group）という。
【００２２】
（定義３：体の乗法群）体ｋの元のうち、０以外の元の集合は、乗法に関して群をなす。これを体ｋの乗法群（multiplicative group of field k）という。有限体Ｆｑの乗法群は、０以外の元から構成され、以下の（５）式で表される。
【数３】
【００２３】
（定義４：アフィン空間）ｋを体とする。集合｛（ａ１，ａ２， ・ ・ ・ , ａｎ） ｜ ａ１∈ｋ, ａ２∈ｋ, ・ ・ ・ , ａｎ∈ｋ｝を、体ｋ上のｎ次元アフィン空間（affine space）といい、以下の（６）式で表す。
【数４】
【００２４】
（定義５：代数的トーラス）代数的トーラス（algebraic torus）Ｔｎを、以下の（７）式のように定義する。
【数５】
ＲｅｓＫ／ｋは、体Ｋから体ｋへのスカラーのＷｅｉｌ ｒｅｓｔｒｉｃｔｉｏｎと呼ばれ、以下の（８）式で表される同形が成り立つ。
【数６】
【００２５】
（定理１）以下の（９）式および（１０）式の定理が成り立つ。
【数７】
【００２６】
（定義６：有理トーラス）ＴをＦｑ上の次元ｄの代数的トーラスとする。双有理写像（ｂｉｒａｔｉｏｎａｌ ｍａｐ）ρ：Ｔ→Ａｄが存在するとき、Ｔは有理（ｒａｔｉｏｎａｌ）であるという。すなわち、Ｔが有理であるとき、Ｚａｒｉｓｋｉ開部分集合Ｗ⊂Ｔ、Ｕ⊂Ａｄ（Ｆｑ）、有理関数ρ１, ・ ・ ・ , ρｄ∈Ｆｑ（ｘ１, ・ ・ ・ , ｘｔ）と、ψ１, ・ ・ ・ , ψｔ∈Ｆｑ（ｙ１, ・ ・ ・ , ｙｄ）が存在し、ρ＝（ρ１, ・ ・ ・ , ρｄ）:Ｗ→Ｕかつψ＝（ψ１, ・ ・ ・ , ψｔ）:Ｕ→Ｗである。
【００２７】
（例１：Ｔ６の有理パラメトライゼーション）ｘ∈Ｆｑ＾２−Ｆｑとする。Ｆｑ＾３のＦｑ基底を｛α１,α２,α３｝とする。｛α１,α２,α３,ｘα１,ｘα２,ｘα３｝は、Ｆｑ＾６のＦｑ基底となる。σ∈Ｇａｌ（Ｆｑ＾６／Ｆｑ）を位数２の元とする。具体的には、以下の（１１）式とする。また、以下の（１２）式で表されるψ０を、以下の（１３）式で定義する。
【数８】
ここで、γ＝ｕ１α１＋ｕ２α２＋ｕ３α３とする。ｘ∈Ｆｑ＾２であるため、以下の（１４）式が成り立つ。
【数９】
【００２８】
１．以下の（１５）式および（１６）式を用いると、すべてのｕ＝（ｕ１, ｕ２, ｕ３）に対して、以下の（１７）式が成り立つ。
【数１０】
【００２９】
２．Ｕを以下の（１８）式で定義すると、以下の（１９）式が成り立つ。また、Ｈｉｌｂｅｒｔの定理９０より、Ｔ６（Ｆｑ）−｛１｝の元はすべてψ０の像に含まれる。よって、以下の（２０）式が成り立つ。
【数１１】
【００３０】
Ｕは、ｕ１、ｕ２、ｕ３の２次方程式で定義された、Ａ３の中の超曲面である。一点ａ＝（ａ１，ａ２，ａ３）∈Ｕ（Ｆｑ）をとる。（α１,α２,α３）を適当にとると、ａにおけるＵの接平面をｕ１＝ａ１とすることができる。（ｖ１,ｖ２）∈Ｆｑ×Ｆｑに対して、Ｕと直線ａ＋（１,ｖ１,ｖ２）／ｔは、２個の交点を持つ。一方はｕ＝ａ、他方はｔ＝ｆ（ｖ１,ｖ２）である。ここで、ｆ（ｖ１,ｖ２）＝１−ｖ１２−ｖ２２＋ｖ１ｖ２である。（ｖ１,ｖ２）から２番目の点への写像ｇは、以下の（２１）式で示すように同形である。
【数１２】
【００３１】
ここで、ｖ（ｆ）は、ｆ（ｖ１,ｖ２）＝０で定義されるＡ２の部分多様体である。また、以下の（２２）式で示すように、ψ＝ψ０○ｇは同形である。ここで、記号「○」は写像の合成を表す。
【数１３】
【００３２】
β＝β１＋β２ｘ∈Ｔ６（Ｆｑ）−｛１,ψ０（ａ）｝とする。また、β１,β２∈Ｆｑ＾３とする。さらに、γ＝（１＋β１）／β２とすると、以下の（２３）式が成り立つ。
【数１４】
【００３３】
また、γ＝ｕ１α１＋ｕ２α２＋ｕ３α３とし、ρ（β）を以下の（２４）式で表すと、以下の（２５）式の写像ρは、同形ψの逆写像である。
【数１５】
【００３４】
（定理２）上述の写像ρとψは、Ｔ６とＡ２の間の双有理写像とその逆写像を与える。
【００３５】
（例２）ｑ≡２ ｏｒ ５ （ｍｏｄ ９）とする。また、ｘ＝ζ３、ｙ＝ζ９＋ζ９−１とすると、Ｆｑ＾６＝Ｆｑ（ζ９）、Ｆｑ＾２＝Ｆｑ（ｘ）、Ｆｑ＾３＝Ｆｑ（ｙ）である。Ｆｑ＾３のための基底を｛１,ｙ,ｙ２−２｝とする。また、ａ＝（０，０，０）とすると、以下の（２６）式が成り立つ。
【数１６】
【００３６】
Ｕを定義する方程式は、以下の（２７）式である。この方程式を解くと、以下の（２８）式が成り立つ。
【数１７】
【００３７】
ここで、基底に関して以下の（２９）式〜（３１）式を用い、Ｆｒｏｂｅｎｉｕｓ写像に関して以下の（３２）式および（３３）式を用いる。
【数１８】
【００３８】
ここで、γ＝ｕ１＋ｕ２ｙ＋ｕ３(ｙ２−２）を（２８）式に代入する。以下の（３４）式および（３５）式より、（３６）式が成り立つ。
【数１９】
【００３９】
これと直線ｕ＝ａ＋（１,ｖ１,ｖ２）／ｔとの交点は、ａと、ｔ＝ｆ（ｖ１,ｖ２）＝１−ｖ１２−ｖ２2＋ｖ１ｖ２≡ｆ（ｖ１,ｖ２）で与えられる。よって、以下の（３７）式が成り立つ。
【数２０】
【００４０】
逆写像は、β＝β１＋β２ｘ∈Ｔ６（Ｆｑ）−｛１、ｘ２｝に対して、（１＋β１）／β２＝ｕ１＋ｕ２ｙ＋ｕ３（ｙ２−２）とすると、以下の（３８）式のρ（β）で表される。
【数２１】
【００４１】
（定義７：拡大体表現）ｚ＝ζ９とするとき、以下の（３９）式を、Ｔ６（Ｆｑ）の拡大体表現という。
【数２２】
【００４２】
（定義８：射影表現）ｘ＝ζ３とするとき、以下の（４０）式を、Ｔ６（Ｆｑ）の射影表現という。
【数２３】
【００４３】
（定義９：ａｆｆｉｎｅ表現）ｘ＝ζ３とするとき、以下の（４１）式を、Ｔ６（Ｆｑ）のａｆｆｉｎｅ表現という。
【数２４】
【００４４】
（定義１０：例外点と通常点）以下の（４２）式で示すような、代数的トーラスＴ６（Ｆｑ）からアフィン空間Ａ２（Ｆｑ）への有理写像ψと、その逆写像ρが定義されている。
【数２５】
【００４５】
このとき、１、ψ０（ａ）＝ｘ２∈Ｔ６（Ｆｑ）を例外点と呼ぶ。このような例外点１およびψ０（ａ）は、写像ρによっては圧縮できない。また、例外点以外のＴ６（Ｆｑ）の元を通常点と呼ぶ。通常点は、写像ρによって、Ａ２（Ｆｑ）の元として表現できる。すなわち、通常点は１／３の長さに圧縮できる。
【００４６】
次に、第１の実施の形態にかかる暗号処理システムの構成について説明する。図１は、第１の実施の形態にかかる暗号処理システムのブロック図である。図１に示すように、第１の実施の形態にかかる暗号処理システムは、暗号化装置１００と、復号装置２００とを含んでいる。
【００４７】
最初に、暗号化装置１００の構成について説明する。暗号化装置１００は、代数的トーラスを用いた公開鍵暗号方式で平文を暗号化する装置であり、入力部１０１と、暗号化処理部１０２と、判定部１０３と、圧縮部１０４と、記憶部１２１と、を備えている。
【００４８】
入力部１０１は、平文データや、暗号化に用いる公開鍵暗号方式の暗号鍵データ（以下、公開鍵データという）などを入力する。記憶部１２１は、入力された平文データや公開鍵データなどを保存する。
【００４９】
暗号化処理部１０２は、平文データに対して公開鍵データを用いて、有限体上の離散対数問題に基づいた暗号化処理を施して複数の要素を含む暗号文データを出力する。具体的には、暗号化処理部１０２は、有限体上の離散対数問題に基づく暗号化方式として、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて平文データに暗号化処理を施して暗号文データを出力する。以下では、暗号化処理部１０２が、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式で平文データを暗号化するものとして説明する。
【００５０】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。図２で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ〜，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００５１】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文データｍに対応する暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖ
を求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００５２】
復号処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）から正当な平文データであるか否かをチェックし、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ〜）は、ｃが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００５３】
このように、暗号化処理部１０２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式によって４つの要素からなる暗号文データｃ１，ｃ２，ｃ３，ｃ４を出力する。ｃ１，ｃ２，ｃ３，ｃ４は、それぞれ代数的トーラスの元であり、拡大体表現の場合は、各要素がそれぞれａ１＋ａ２ｘ＋ａ３ｙ＋ａ４ｘｙ＋ａ５（ｙ２−２）＋ａ６ｘ（ｙ２−２）のように表される。ここで、各ａｉはＦｑの元である。上述のように、この拡大体表現はａｉのみを用いて（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）と表してもよい。
【００５４】
暗号文データの各要素が、後述する圧縮部１０４による圧縮の対象となる代数的トーラス上の元（対象元）となる。
【００５５】
判定部１０３は、暗号化処理部１０２が出力した暗号文データに含まれる各要素が、上述した代数的トーラス上の例外点であるか否かを判定する。また、判定部１０３は、例外点であると判定した要素が、代数的トーラス上の複数の例外点のうち、いずれの例外点であるかを判定する。
【００５６】
圧縮部１０４は、非特許文献１のような代数的トーラスを利用した暗号圧縮技術によって暗号文データを圧縮した圧縮暗号文データを出力する。具体的には、圧縮部１０４は、判定部１０３が例外点でないと判定した暗号文データの要素を、上述の双有理写像ρによって拡大体表現からアフィン表現に圧縮し、圧縮したアフィン表現と、圧縮の対象となった対象元が通常点であることを表す情報を含む処理結果を生成する。
【００５７】
このように、本実施の形態では、圧縮部１０４は、圧縮したアフィン表現だけでなく、対象元が通常点であるか例外点であるかを表す情報を含む処理結果を生成する。例えば、圧縮部１０４は、処理結果中の所定の１ビットを通常点であるか例外点であるかを表すビット（例外情報ビット）とする。そして、例えば例外情報ビットが０の場合は通常点であることを表し、１の場合は例外点であることを表す。
【００５８】
判定部１０３が例外点であると判定した要素に対しては、圧縮部１０４は、例外情報ビットと、いずれの例外点であるかを識別する識別情報とを含む処理結果を生成する。例えば、処理結果中で例外情報ビットと異なる所定の１ビットを、いずれの例外点であるかを表すビット（識別情報ビット）とする。そして、例えば識別情報ビットが０の場合は例外点が１であることを表し、１の場合は例外点ψ０（ａ）を表す。
【００５９】
なお、通常点の場合に圧縮して得られるアフィン表現を格納するビット列に含まれるいずれか１ビットを、識別情報ビットとして利用するように構成してもよい。これは、通常点であって、かつ、例外点であるような場合は生じないからである。
【００６０】
また、アフィン表現はＡ２（Ｆｑ）の全てをとりえるわけではないため、上述の部分多様体ｖ（ｆ）に含まれる点を使って例外点を表現するように構成してもよい。例えば、（Ａ１，Ａ２）と（Ｂ１，Ｂ２）とがｖ（ｆ）の元であるならば、（Ａ１，Ａ２）および（Ｂ１，Ｂ２）が、それぞれ例外点１および例外点ψ０（ａ）を表すものとすればよい。この場合、出力される情報のサイズはアフィン表現のサイズと同じである。
【００６１】
圧縮部１０４は、このようにして暗号文データの各要素に対して生成した処理結果を圧縮暗号文データとして出力する。また、出力された圧縮暗号文データは、外部装置との間でデータを送受信する送受信部（図示せず）などによって、復号装置２００に送信される。
【００６２】
次に、復号装置２００の構成について説明する。復号装置２００は、代数的トーラスを用いた公開鍵暗号方式で暗号化された暗号文データを復元する装置であり、入力部２０１と、判定部２０２と、伸長部２０３と、復号処理部２０４と、記憶部２２１と、を備えている。
【００６３】
入力部２０１は、暗号化装置１００から送信された圧縮暗号文データや、復号化に用いる公開鍵暗号方式の秘密鍵データなどを入力する。記憶部２２１は、入力された圧縮暗号文データや秘密鍵データなどを保存する。
【００６４】
判定部２０２は、圧縮暗号文データの各要素に含まれる例外情報ビットが０（通常点）であるか、１（例外点）であるかを判定する。これは、暗号化装置１００の圧縮部１０４が当該要素を得るために圧縮の対象とした対象元が例外点であるか否かを判定することを意味する。
【００６５】
伸長部２０３は、代数的トーラスを利用した暗号圧縮技術によって圧縮された暗号文データを伸長する。具体的には、伸長部２０３は、判定部２０２が例外情報ビット＝０（通常点）と判定した場合に、暗号文データの要素を、上述の双有理写像ρの逆写像ψによってアフィン表現から拡大体表現に伸長する。なお、以下では逆写像ψを伸長写像という。
【００６６】
判定部２０２が例外情報ビット＝１（例外点）と判定した場合は、伸長部２０３は、識別情報ビットで識別される例外点に対応する、拡大体表現で表された所定の元を、暗号文データの要素に対する伸長結果として生成する。
【００６７】
復号処理部２０４は、伸長部２０３で伸長された暗号文データの要素それぞれに対して、記憶部２２１に記憶された秘密鍵データを用いて、有限体上の離散対数問題に基づいた復号化処理を施して平文データを出力する。具体的には、復号処理部２０４は、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算または暗号文データを入力値として用いるハッシュ関数を用いて、暗号文データに復号化処理を施して平文データを得る。
【００６８】
なお、暗号化装置１００の記憶部１２１および復号装置２００の記憶部２２１は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００６９】
次に、このように構成された第１の実施の形態にかかる暗号化装置１００による暗号化処理について図３を用いて説明する。図３は、第１の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【００７０】
なお、暗号化装置１００は、事前に公開鍵データおよび平文データを入力し、記憶部１２１等に記憶しているものとする。
【００７１】
まず、暗号化処理部１０２は、図２で示したように乱数ｒを生成する（ステップＳ３０１）。次に、暗号化処理部１０２は、公開鍵データに含まれるｇ〜、ｅ、ｆを用いて、生成した乱数ｒを乗数に用いたべき乗計算と乗算とを実行し、暗号文データの要素であるｃ１，ｃ２を求める（ステップＳ３０２）。次に、暗号化処理部１０２は、乗算により平文を加工し、暗号文データの要素であるｃ３を求める（ステップＳ３０３）。
【００７２】
次に、暗号化処理部１０２は、公開鍵データに含まれるｅ、ｆと乱数とを用いてハッシュ計算を行ってハッシュ値ｖを求める（ステップＳ３０４）次に、暗号化処理部１０２は、求めたハッシュ値ｖを乗数に用いたべき乗計算を行うことにより暗号文データの要素であるｃ４を求める（ステップＳ３０５）。そして、暗号化処理部１０２は、算出した暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を出力する（ステップＳ３０６）。
【００７３】
次に、判定部１０３は、受け取った暗号文データの要素のうち、未処理の要素を取得する（ステップＳ３０７）。そして、判定部１０３は、拡大体表現（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）で表された要素が例外点であるかを判定する例外点判定処理を実行する（ステップＳ３０８）。例外点判定処理の詳細については後述する。
【００７４】
次に、圧縮部１０４が、例外点判定処理の判定結果が例外点１または例外点ψ０（ａ）であることを表すか否かを判断する（ステップＳ３０９）。判定結果が例外点１または例外点ψ０（ａ）でないこと、すなわち、通常点であることを表す場合は（ステップＳ３０９：ＮＯ）、圧縮部１０４は、双有理写像ρにより暗号文データの要素を圧縮し、アフィン表現を生成する（ステップＳ３１０）。そして、圧縮部１０４は、通常点であることを表す情報を含む圧縮暗号文データの要素を出力する（ステップＳ３１１）。具体的には、圧縮部１０４は、例外情報ビット＝０であり、その他のビット列に圧縮したアフィン表現を含む圧縮暗号文データの要素を出力する。
【００７５】
ステップＳ３０９で、判定結果が例外点１または例外点ψ０（ａ）であると判断された場合は（ステップＳ３０９：ＹＥＳ）、圧縮部１０４は、例外点であることを表す情報と、いずれの例外点かを識別する識別情報を含む圧縮暗号文データの要素を出力する（ステップＳ３１２）。具体的には、圧縮部１０４は、判定結果が例外点１の場合は、例外情報ビット＝１、識別情報ビット＝０である圧縮暗号文データの要素を出力する。また、圧縮部１０４は、判定結果が例外点ψ０（ａ）の場合は、例外情報ビット＝１、識別情報ビット＝１である圧縮暗号文データの要素を出力する。
【００７６】
次に、圧縮部１０４は、暗号文データのすべての要素を処理したか否かを判断し（ステップＳ３１３）、処理していない場合は（ステップＳ３１３：ＮＯ）、次の未処理の要素を取得して処理を繰り返す（ステップＳ３０７）。すべての要素を処理した場合は（ステップＳ３１３：ＹＥＳ）、暗号化処理を終了する。
【００７７】
次に、ステップＳ３０８の例外点判定処理の詳細について図４を用いて説明する。図４は、第１の実施の形態における例外点判定処理の全体の流れを示すフローチャートである。
【００７８】
まず、判定部１０３は、暗号文データの要素が例外点１であるか否かを判断する（ステップＳ４０１）。具体的には、判定部１０３は、要素の拡大体表現（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）を用いて、ａ１＝１、かつ、ａ２＝ａ３＝ａ４＝ａ５＝ａ６＝０であるか否かを判断する。
【００７９】
要素が例外点１である場合は（ステップＳ４０１：ＹＥＳ）、判定部１０３は、例外点１であることを表す判定結果を出力し（ステップＳ４０２）、例外点判定処理を終了する。要素が例外点１でない場合は（ステップＳ４０１：ＮＯ）、判定部１０３は、さらに、要素が例外点ψ０（ａ）であるか否かを判断する（ステップＳ４０３）。具体的には、判定部１０３は、ａ１＝ａ２＝ｐ−１、かつ、ａ３＝ａ４＝ａ５＝ａ６＝０であるか否かを判断する。
【００８０】
要素が例外点ψ０（ａ）である場合は（ステップＳ４０３：ＹＥＳ）、判定部１０３は、例外点ψ０（ａ）であることを表す判定結果を出力し（ステップＳ４０４）、例外点判定処理を終了する。要素が例外点ψ０（ａ）でない場合は（ステップＳ４０３：ＮＯ）、判定部１０３は、要素が通常点であることを表す判定結果を出力し（ステップＳ４０５）、例外点判定処理を終了する。
【００８１】
なお、判定部１０３は拡大体表現を用いて例外点か否かを判定しているが、要素が射影表現で表されている場合であっても同様の判定が可能である。
【００８２】
次に、第１の実施の形態にかかる復号装置２００による復号処理について図５を用いて説明する。図５は、第１の実施の形態における復号処理の全体の流れを示すフローチャートである。
【００８３】
なお、復号装置２００には、暗号化装置１００が圧縮に用いた公開鍵データに対応する秘密鍵データが事前に入力され、記憶部２２１等に記憶されているものとする。
【００８４】
まず、入力部２０１は、復号の対象となる圧縮暗号文データを入力する（ステップＳ５０１）。例えば、入力部２０１は、暗号化装置１００から送信され、記憶部２２１に記憶された圧縮暗号文データを、当該記憶部２２１から入力する。
【００８５】
次に、復号処理部２０４は、入力された圧縮暗号文データの各要素が正しい群の元であるか否かを検査する（ステップＳ５０２）。具体的には、復号処理部２０４は、図２の（１１−１）および（１１−２）に示すように、各要素が群Ｇまたは群Ｇ〜に属することを検査する。
【００８６】
圧縮暗号文データの各要素が正しい群の元でない場合は（ステップＳ５０２：ＮＯ）、復号処理を終了する。圧縮暗号文データの各要素が正しい群の元である場合（ステップＳ５０２：ＹＥＳ）、伸長部２０３は、圧縮暗号文データの要素のうち、未処理の要素を取得する（ステップＳ５０３）。
【００８７】
次に、判定部２０２が、取得した要素に例外点であることを表す情報が含まれるか否かを判断する（ステップＳ５０４）。具体的には、判定部２０２は、取得した要素に含まれる例外情報ビットを参照し、例外情報ビットが１の場合に、例外点であることを表す情報が含まれると判断する。また、判定部２０２は、例外情報ビットが０の場合に、例外点であることを表す情報が含まれないと判断する。
【００８８】
例外点であることを表す情報が含まれない場合は（ステップＳ５０４：ＮＯ）、伸長部２０３は、伸長写像により圧縮暗号文データの要素を伸長する（ステップＳ５０５）。例外点であることを表す情報が含まれる場合は（ステップＳ５０４：ＹＥＳ）、伸長部２０３は、取得した要素に含まれる識別情報ビットで識別される例外点に対応する元を、伸長処理の結果として出力する（ステップＳ５０５）。
【００８９】
例えば、伸長部２０３は、取得した要素に含まれる識別情報ビットを参照し、識別情報ビットが０の場合に、例外点１に対応する拡大体表現の元（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）＝（１，０，０，０，０，０）を出力する。また、伸長部２０３は、識別情報ビットが１の場合に、例外点ψ０（ａ）に対応する拡大体表現の元（ａ１，ａ２，ａ３，ａ４，ａ５，ａ６）＝（ｐ−１，ｐ−１，０，０，０，０）を出力する。
【００９０】
ステップＳ５０５またはステップＳ５０６の後、伸長部２０３は、圧縮暗号文データのすべての要素を処理したか否かを判断する（ステップＳ５０７）。すべての要素を処理していない場合は（ステップＳ５０７：ＮＯ）、次の要素を取得して処理を繰り返す（ステップＳ５０３）。
【００９１】
すべての要素を処理した場合は（ステップＳ５０７：ＹＥＳ）、以下に示すように、復号処理部２０４が伸長した暗号文データを平文データに復号する（ステップＳ５０８〜ステップＳ５１１）。なお、すべての要素を伸長することにより、暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）が得られている。
【００９２】
まず、復号処理部２０４は、秘密鍵データと暗号文データの要素ｃ１，ｃ２，ｃ３とを用いてハッシュ関数によりハッシュ値ｖを算出する（ステップＳ５０８）。次に、復号処理部２０４は、ハッシュ値ｖと、暗号文データの要素ｃ１，ｃ２と、秘密鍵データとを用いて、べき乗計算と乗算とにより検査式に用いる値を計算する（ステップＳ５０９）。具体的には、復号処理部２０４は、図２の（１１−６）の検査式の右辺の値を計算する。
【００９３】
次に、復号処理部２０４は、検査式が成立するか否か、すなわち、計算した値と暗号文データの要素ｃ４とが一致するか否かを判断する（ステップＳ５１０）。検査式が成立しない場合は（ステップＳ５１０：ＮＯ）、復号処理を終了する。
【００９４】
検査式が成立する場合は（ステップＳ５１０：ＹＥＳ）、図２の（１１−３）、（１１−４）に示すように、暗号文データの要素ｃ１，ｃ２と秘密鍵データｚ１、ｚ２とを用いたべき乗計算、および、べき乗計算で得られた値と暗号文データの要素ｃ３とを用いた乗算を実行し、平文データｍを復号する（ステップＳ５１１）。
【００９５】
このように、第１の実施の形態にかかる暗号処理システムでは、暗号化装置が、アフィン表現に圧縮する対象となるトーラス上の元である対象元が例外点であるか否かを判定し、例外点の場合は圧縮せず、例外点であることを表す情報を含む暗号文を生成することができる。そして、復号装置は、例外点であることを表す情報を元に暗号文を復元することができる。これにより、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても適切に処理を実行することが可能となる。
【００９６】
また、例外点であることを表す情報は例えば１ビットで表すことができる。すなわち、圧縮したアフィン表現のデータ長と比較して十分に小さい。このため、例外点であることを表す情報を含めたとしても圧縮の効果に与える影響は小さい。
【００９７】
（第２の実施の形態）
第２の実施の形態にかかる暗号処理システムは、暗号化装置が、圧縮する対象となる対象元が例外点であるか否かを判定し、例外点の場合は、対象元が通常点となるまで、新たに生成した乱数を元に対象元を再計算する。復号装置は、暗号文が例外点であるか否かを判定することなく暗号文を復号する。
【００９８】
図６は、第２の実施の形態にかかる暗号処理システムの構成を示すブロック図である。図６に示すように、第２の実施の形態にかかる暗号処理システムは、暗号化装置６００と、復号装置７００とを含んでいる。
【００９９】
同図に示すように、第２の実施の形態にかかる暗号化装置６００は、入力部１０１と、暗号化処理部６０２と、判定部１０３と、圧縮部６０４と、記憶部１２１と、を備えている。
【０１００】
第２の実施の形態では、暗号化処理部６０２および圧縮部６０４の機能が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる暗号化装置１００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１０１】
暗号化処理部６０２は、第１の実施の形態の暗号化処理部１０２と同様に、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式などの有限体上の離散対数問題に基づいた暗号方式により、平文データを暗号化して暗号文データを出力する。第２の実施の形態では、暗号化処理部６０２が、判定部１０３によって暗号文データの要素が例外点であると判定された場合に、暗号文データを算出するための乱数を新たに生成し、暗号文データのすべての要素が通常点となるまで新たな乱数を用いて暗号文データを再度計算する点が、第１の実施の形態と異なっている。これにより、暗号化処理部６０２は、すべての要素が通常点である暗号文データを出力することができる。
【０１０２】
圧縮部６０４は、暗号化処理部６０２から出力された暗号文データを、代数的トーラスを利用した暗号圧縮技術によって圧縮した圧縮暗号文データを出力する。暗号化処理部６０２が例外点を要素に含まない暗号文データを出力するため、第２の実施の形態の圧縮部６０４は、要素が例外点であるか否かを判定することなく暗号文データを圧縮できる。また、これにより、圧縮部６０４は、例外情報ビットのように例外点であることを表す情報や、識別情報ビットのように例外点の種類を表す情報を含まず、圧縮したアフィン表現のみを含む処理結果を出力することができる。
【０１０３】
次に、復号装置７００の構成について説明する。第２の実施の形態にかかる復号装置７００は、入力部２０１と、伸長部７０３と、復号処理部２０４と、記憶部２２１と、を備えている。
【０１０４】
第２の実施の形態では、判定部２０２を削除したこと、および、伸長部７０３の機能が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる復号装置２００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１０５】
伸長部７０３は、代数的トーラスを利用した暗号圧縮技術によって圧縮された暗号文データを伸長する。第２の実施の形態では、圧縮されたアフィン表現のみを含む圧縮暗号文データが入力されるため、圧縮暗号文データが例外点に対応する要素を含むか否かを例外情報ビット等によって判定する必要がない。同様に、伸長部７０３が判定結果にしたがって伸長処理を変更する必要がない。すなわち、伸長部７０３は、圧縮暗号文データのすべての要素に対して伸長写像による伸長処理を実行する。
【０１０６】
次に、このように構成された第２の実施の形態にかかる暗号化装置６００による暗号化処理について図７を用いて説明する。図７は、第２の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【０１０７】
ステップＳ７０１からステップＳ７０９までの、乱数生成処理、暗号文算出処理、例外点判定処理、および結果判定処理は、第１の実施の形態にかかる暗号化装置１００におけるステップＳ３０１からステップＳ３０９までと同様の処理なので、その説明を省略する。
【０１０８】
ステップＳ７０９で、判定結果が例外点１または例外点ψ０（ａ）であると判断された場合は（ステップＳ７０９：ＹＥＳ）、暗号化処理部１０２は、暗号化に用いる乱数ｒを新たに生成し（ステップＳ７０１）、処理を繰り返す。
【０１０９】
判定結果が例外点１または例外点ψ０（ａ）でないと判断された場合は（ステップＳ７０９：ＮＯ）、圧縮部６０４は、暗号文データのすべての要素を処理したか否かを判断する（ステップＳ７１０）。すべての要素を処理していない場合は（ステップＳ７１０：ＮＯ）、次の未処理の要素を取得して処理を繰り返す（ステップＳ７０７）。
【０１１０】
すべての要素を処理した場合は（ステップＳ７１０：ＹＥＳ）、圧縮部６０４は、双有理写像ρにより暗号文データの各要素を圧縮し、アフィン表現を生成する（ステップＳ７１１）。
【０１１１】
このように、第２の実施の形態では、圧縮の対象となる対象元がすべて通常点となるまで乱数を再生成して処理を繰り返すため、双有理写像ρによって圧縮されたアフィン表現のみを要素として含む圧縮暗号文データを生成することができる。
【０１１２】
次に、このように構成された第２の実施の形態にかかる復号装置７００による復号処理について図８を用いて説明する。図８は、第２の実施の形態における復号処理の全体の流れを示すフローチャートである。
【０１１３】
ステップＳ８０１からステップＳ８０３までの、暗号文入力処理、元判定処理、および要素取得処理は、第１の実施の形態にかかる復号装置２００におけるステップＳ５０１からステップＳ５０３までと同様の処理なので、その説明を省略する。
【０１１４】
ステップＳ８０３で、圧縮暗号文データの未処理の要素を取得した後、伸長部７０３は、取得した要素を伸長写像により伸長する（ステップＳ８０４）。
【０１１５】
このように、第２の実施の形態では、圧縮暗号文データの要素に例外点であることを表す情報が含まれるか否かを判定し、含まれる場合に例外点に対応する元を出力する処理（図５のステップＳ５０４〜ステップＳ５０５）が不要となる。
【０１１６】
ステップＳ８０５からステップＳ８０９までの、完了判定処理および平文算出処理は、第１の実施の形態にかかる復号装置２００におけるステップＳ５０７からステップＳ５１１までと同様の処理なので、その説明を省略する。
【０１１７】
このように、第２の実施の形態にかかる暗号処理システムでは、暗号化装置が、圧縮する対象となる対象元が例外点であるか否かを判定し、例外点の場合は、対象元が通常点となるまで、新たに生成した乱数を元に対象元を再計算することができる。これにより、代数的トーラスを用いてデータ長を圧縮する処理で、圧縮できない例外点が現れた場合であっても適切に処理を実行することが可能となる。また、これにより、復号装置は暗号文が例外点であるか否かを判定することなく暗号文を復号することができる。
【０１１８】
次に、第１および第２の実施の形態にかかる暗号化装置および復号装置のハードウェア構成について説明する。第１および第２の実施の形態にかかる暗号化装置および復号装置は、ＣＰＵ（Central Processing Unit）などの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆと、各部を接続するバスを備えている。
【０１１９】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、ＲＯＭ等に予め組み込まれて提供される。
【０１２０】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【０１２１】
さらに、第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１２２】
第１および第２の実施の形態にかかる暗号化装置または復号装置で実行される情報処理プログラムは、上述した各部（入力部、暗号化処理部、判定部、圧縮部、または、入力部、判定部、伸長部、復号処理部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵがＲＯＭから情報処理プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０１２３】
以上のように、本発明にかかる装置およびプログラムは、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式のように、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化または復号化する装置に適している。
【図面の簡単な説明】
【０１２４】
【図１】第１の実施の形態にかかる暗号処理システムのブロック図である。
【図２】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図３】第１の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図４】第１の実施の形態における例外点判定処理の全体の流れを示すフローチャートである。
【図５】第１の実施の形態における復号処理の全体の流れを示すフローチャートである。
【図６】第２の実施の形態にかかる暗号処理システムの構成を示すブロック図である。
【図７】第２の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図８】第２の実施の形態における復号処理の全体の流れを示すフローチャートである。
【符号の説明】
【０１２５】
１００、６００ 暗号化装置
１０１ 入力部
１０２、６０２ 暗号化処理部
１０３ 判定部
１０４、６０４ 圧縮部
１２１ 記憶部
２００、７００ 復号装置
２０１ 入力部
２０２ 判定部
２０３、７０３ 伸長部
２０４ 復号処理部
２２１ 記憶部
【特許請求の範囲】
【請求項１】
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、
を特徴とする情報処理装置。
【請求項２】
前記判定部は、さらに、前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを判定し、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記例外情報と、前記対象元が複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報とを含む前記処理結果を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記圧縮部は、前記対象元が前記例外点であると判定された場合に前記識別情報を生成し、前記対象元が前記例外点でないと判定された場合に前記対象元を前記圧縮写像によって圧縮したアフィン表現を生成し、生成した前記識別情報または生成した前記アフィン表現と、前記例外情報と、を含む前記処理結果を生成すること、
を特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記対象元は、公開鍵暗号で用いる公開鍵と、前記公開鍵で暗号化された暗号文と、の少なくとも一方であること、
を特徴とする請求項１に記載の情報処理装置。
【請求項５】
コンピュータを、
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、
を特徴とする情報処理プログラム。
【請求項６】
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
乱数を生成し、生成した乱数を用いて予め定められた演算を実行し、圧縮の対象となる前記代数的トーラス上の元を表す対象元を生成する演算部と、
前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、
前記演算部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点でないと判定されるまで、乱数を新たに生成し、新たに生成した乱数を用いて前記演算を実行して前記対象元を生成し、
前記圧縮部は、前記例外点でないと判定された前記対象元を前記圧縮写像によってアフィン表現に圧縮すること、
を特徴とする情報処理装置。
【請求項７】
代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、
前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、
前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、を備え、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする情報処理装置。
【請求項８】
前記入力部は、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報と、前記例外情報と、を含む前記処理結果を入力し、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、複数の前記例外点に対して予め定められた複数の前記代数的トーラス上の元のうち、前記識別情報の前記例外点に対応する元を生成すること、
を特徴とする請求項７に記載の情報処理装置。
【請求項９】
前記入力部は、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報、および、前記圧縮写像によって圧縮されたアフィン表現のいずれかと、前記例外情報と、を含む前記処理結果を入力し、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、複数の前記例外点に対して予め定められた複数の前記代数的トーラス上の元のうち、前記識別情報の前記例外点に対応する元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする請求項７に記載の情報処理装置。
【請求項１０】
前記対象元は、公開鍵暗号で用いる公開鍵と、前記公開鍵で暗号化された暗号文と、の少なくとも一方であること、
を特徴とする請求項７に記載の情報処理装置。
【請求項１１】
コンピュータを、
代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、
前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、
前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする情報処理プログラム。
【請求項１】
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、
を特徴とする情報処理装置。
【請求項２】
前記判定部は、さらに、前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを判定し、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記例外情報と、前記対象元が複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報とを含む前記処理結果を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記圧縮部は、前記対象元が前記例外点であると判定された場合に前記識別情報を生成し、前記対象元が前記例外点でないと判定された場合に前記対象元を前記圧縮写像によって圧縮したアフィン表現を生成し、生成した前記識別情報または生成した前記アフィン表現と、前記例外情報と、を含む前記処理結果を生成すること、
を特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記対象元は、公開鍵暗号で用いる公開鍵と、前記公開鍵で暗号化された暗号文と、の少なくとも一方であること、
を特徴とする請求項１に記載の情報処理装置。
【請求項５】
コンピュータを、
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
圧縮の対象となる前記代数的トーラス上の元を表す対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、
前記圧縮部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点であることを表す例外情報を含む処理結果を生成し、前記対象元が前記例外点でないと判定された場合に、前記対象元を前記圧縮写像によって圧縮したアフィン表現を含む処理結果を生成すること、
を特徴とする情報処理プログラム。
【請求項６】
代数的トーラス上の元を圧縮写像によってアフィン表現に圧縮可能な圧縮部と、
乱数を生成し、生成した乱数を用いて予め定められた演算を実行し、圧縮の対象となる前記代数的トーラス上の元を表す対象元を生成する演算部と、
前記対象元が、前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを判定する判定部と、を備え、
前記演算部は、前記対象元が前記例外点であると判定された場合に、前記対象元が前記例外点でないと判定されるまで、乱数を新たに生成し、新たに生成した乱数を用いて前記演算を実行して前記対象元を生成し、
前記圧縮部は、前記例外点でないと判定された前記対象元を前記圧縮写像によってアフィン表現に圧縮すること、
を特徴とする情報処理装置。
【請求項７】
代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、
前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、
前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、を備え、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする情報処理装置。
【請求項８】
前記入力部は、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報と、前記例外情報と、を含む前記処理結果を入力し、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、複数の前記例外点に対して予め定められた複数の前記代数的トーラス上の元のうち、前記識別情報の前記例外点に対応する元を生成すること、
を特徴とする請求項７に記載の情報処理装置。
【請求項９】
前記入力部は、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す複数の前記例外点のうちいずれの前記例外点であるかを識別する識別情報、および、前記圧縮写像によって圧縮されたアフィン表現のいずれかと、前記例外情報と、を含む前記処理結果を入力し、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、複数の前記例外点に対して予め定められた複数の前記代数的トーラス上の元のうち、前記識別情報の前記例外点に対応する元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする請求項７に記載の情報処理装置。
【請求項１０】
前記対象元は、公開鍵暗号で用いる公開鍵と、前記公開鍵で暗号化された暗号文と、の少なくとも一方であること、
を特徴とする請求項７に記載の情報処理装置。
【請求項１１】
コンピュータを、
代数的トーラス上の元をアフィン表現に圧縮する圧縮写像によって、圧縮の対象となる前記代数的トーラス上の元を表す対象元を圧縮した結果であって、前記対象元が前記圧縮写像によって圧縮できない前記代数的トーラス上の元を表す例外点であるか否かを表す例外情報を含む処理結果を入力する入力部と、
前記圧縮写像によって圧縮された前記代数的トーラス上の元を、前記圧縮写像に対応する伸長写像によって伸長可能な伸長部と、
前記処理結果に含まれる前記例外情報に基づいて、前記対象元が前記例外点であるか否かを判定する判定部と、として機能させる情報処理プログラムであって、
前記伸長部は、前記対象元が前記例外点であると判定された場合に、前記例外点に対して予め定められた前記代数的トーラス上の元を生成し、前記対象元が前記例外点でないと判定された場合に、前記処理結果を前記伸長写像によって伸長した前記代数的トーラス上の元を生成すること、
を特徴とする情報処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−４９２１１（Ｐ２０１０−４９２１１Ａ）
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願番号】特願２００８−２１６０１３（Ｐ２００８−２１６０１３）
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]