秘密情報を用いて演算する装置、方法およびプログラム
【課題】秘密鍵を用いた演算処理の安全性を向上させる復号装置を提供する。
【解決手段】乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化した暗号文データを復号化する復号装置であって、部分群上の元であってアフィン表現で表された暗号文データを入力する入力部１０１と、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの写像をランダムに選択し、選択した写像によって入力された暗号文データを射影表現に変換する変換部１１１と、射影表現に変換された暗号文データに対して暗号方式で予め定められた復号処理を実行することにより平文データを算出する演算処理部１１２と、を備えた。
【解決手段】乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化した暗号文データを復号化する復号装置であって、部分群上の元であってアフィン表現で表された暗号文データを入力する入力部１０１と、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの写像をランダムに選択し、選択した写像によって入力された暗号文データを射影表現に変換する変換部１１１と、射影表現に変換された暗号文データに対して暗号方式で予め定められた復号処理を実行することにより平文データを算出する演算処理部１１２と、を備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する装置、方法およびプログラムに関する。
【背景技術】
【０００２】
事前に鍵を共有することを必要とせずに安全な通信を実現する公開鍵暗号は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになっている。
【０００３】
公開鍵暗号において現在の典型的な暗号系サイズは１０２４ビットである。なお、暗号系サイズとは、公開鍵暗号で用いる表現形式で表した場合のデータのサイズを表す。例えば公開鍵暗号方式の１つであるＣｒａｍｅｒ−Ｓｈｏｕｐ暗号等では、１０２４ビットの拡大体表現と呼ばれる表現形式で各種データが表現される。計算機の進歩とともに攻撃者の能力も上がっているため、解読が困難とされる暗号系サイズは年々大きくなっている。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となる。例えば、公開鍵サイズは、暗号系サイズと鍵の個数との積になる。また、暗号文サイズは、暗号系サイズと、１つのメッセージを暗号化するのに必要な暗号文の数との積になる。したがって、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する暗号圧縮技術が提案されている（例えば、非特許文献１）。この暗号圧縮技術は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。また、圧縮率、すなわち圧縮前のビット数の圧縮後のビット数に対する割合を増大するための改良技術として、集合の要素を小さいビット数の表現に変換する際に付加的な入力を用いる技術が知られている（例えば、非特許文献２）。
【０００５】
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＲＹＰＴＯ ２００３，Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ２７２９，３４９−３６５，２００３．
【非特許文献２】Ｍ．ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ．Ｗｏｏｄｒｕｆｆ．“Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ” ＣＲＹＰＴＯ ２００４，Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ３１５２，１５７−１７８，２００４．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１などの代数的トーラスを用いた暗号圧縮技術では、電磁波解析などにより秘密情報を解読するサイドチャネル攻撃などへの対処が考慮されていないため、不正な攻撃に対してセキュリティが低下する場合があるという問題があった。
【０００７】
ここで、秘密情報とは、演算処理の途中において出現する、非公開情報の一切を表す。例えば、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号では、秘密鍵だけでなく、暗号化処理の計算途中に出現するハッシュ値やランダムに生成される乱数なども秘密情報に含まれる。公開鍵などは、非公開情報でないため、秘密情報には当たらない。
【０００８】
本発明は、上記に鑑みてなされたものであって、秘密情報を用いた演算処理の安全性を向上させることができる装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明は、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置であって、前記部分群上の元である入力データを入力する入力部と、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理部と、を備えたことを特徴とする。
【００１０】
また、本発明は、上記装置を実行することができる方法およびプログラムである。
【発明の効果】
【００１１】
本発明によれば、秘密情報を用いた演算処理の安全性を向上させることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、この発明にかかる装置、方法およびプログラムの最良な実施の形態を詳細に説明する。なお、以下では、秘密情報を用いた演算処理を実行する演算装置（秘密情報に基づく演算装置）を、代数的トーラスを用いた暗号圧縮技術によって暗号化された暗号化データを秘密情報を用いて復号する復号装置として実現した例について説明する。適用可能な装置は復号装置に限られるものではなく、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する装置であれば、あらゆる装置に適用できる。例えば、秘密鍵データを用いて署名を作成する装置に対しても本実施の形態の手法を適用できる。
【００１３】
一般に、四則演算が定義される数の集合である体のうち、数の集合が有限の体は有限体と呼ばれる。また、有限体に含まれる数の個数は素数であるか素数のべき乗であることが知られている。このような体は、それぞれ素体と拡大体と呼ばれる。暗号圧縮技術で用いられる代数的トーラスは、拡大体上の乗法群の部分群である。
【００１４】
代数的トーラスの表現としては、拡大体表現、射影表現、およびアフィン表現の３種類が存在する。従来の代数的トーラスを用いた暗号圧縮技術では、まず、暗号化装置がメッセージを拡大体表現となっている代数的トーラスの要素に対応させる。次に、拡大体表現で計算を行って暗号文データを算出し、暗号文データを圧縮したアフィン表現へと変換し、圧縮された圧縮暗号文データを復号装置に送信する。復号装置では、受信した圧縮暗号文データを拡大体表現に変換し、拡大体表現で計算を行って平文データを復号する。
【００１５】
一方、本実施の形態にかかる復号装置は、まず、アフィン表現で表された圧縮暗号文データを拡大体表現ではなく射影表現に変換して計算を実行する。このとき、アフィン表現をそれぞれ異なる射影表現に変換する複数の変換写像を用意し、その中からランダムに選択した１つの変換写像を用いてアフィン表現を射影表現に変換する。
【００１６】
これにより、復号処理のランダム性が増加し、安全性が向上する。すなわち、電磁波解析などにより秘密鍵を解読するサイドチャネル攻撃等を受けた場合であっても、波形が一定にならないため秘密鍵を解読されるおそれが低下する。
【００１７】
ここで、本実施の形態にかかる暗号処理システムの概要について用いて説明する。図１は、本実施の形態にかかる暗号処理システムの概要を示す図である。図１に示すように、本実施の形態にかかる暗号処理システムは、暗号化装置２００と、秘密情報に基づく演算装置１００とを含んでいる。
【００１８】
暗号化装置２００は、乗法群の部分群である代数的トーラス上の離散対数問題に基づく公開鍵暗号方式により平文データを暗号化した暗号文を生成し、生成した暗号文をアフィン表現に圧縮して演算装置１００に送信する。
【００１９】
演算装置１００は、アフィン表現で表された暗号文を受信すると、暗号文のアフィン表現を、対応する複数の射影表現のうち、乱数に応じて選択されるいずれかの射影表現に変換する。そして、演算装置１００は、変換した射影表現を用いて演算を実行し、代数的トーラス上の元である平文データを演算結果として出力する。
【００２０】
従来の復号装置は、アフィン表現を対応する１つの射影表現に変換して演算していた。これに対し、本実施の形態では、同図に示したように、複数の射影表現から選択した射影表現に変換して演算を実行できる。これにより、秘密情報を用いた演算処理の１つである代数的トーラスを用いた暗号方式のランダム性を増加させることができる。
【００２１】
次に、本実施の形態にかかる演算装置１００の構成について説明する。図２は、本実施の形態にかかる演算装置１００のブロック図である。図２に示すように、演算装置１００は、代数的トーラスを用いた公開鍵暗号方式で暗号化された暗号文データを復元する装置であり、入力部１０１と、分割部１０２と、乱数生成部１０３と、演算制御部１１０と、記憶部１０４と、を備えている。
【００２２】
入力部１０１は、暗号化装置２００から送信された圧縮暗号文データや、復号化に用いる公開鍵暗号方式の秘密鍵データなどの入力データを入力する。記憶部１０４は、入力された圧縮暗号文データや秘密鍵データなどを保存する。記憶部１０４は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００２３】
分割部１０２は、入力された圧縮暗号文データを、復号処理の単位とする複数の部分データに分割する。例えば、分割部１０２は、圧縮暗号文データを、予め定められたサイズの部分データごとに分割する。なお、分割方法はこれに限られるものではない。また、演算装置１００内では圧縮暗号文データを分割しないように構成してもよい。例えば、暗号化装置２００が平文データを部分データに分割し、各部分データを暗号化および圧縮した複数の圧縮暗号文データを送信するように構成してもよい。この場合、演算装置１００は、複数の圧縮暗号文データを単位として復号処理を実行すればよい。
【００２４】
乱数生成部１０３は、変換部１１１（後述）が複数の変換写像から１つの変換写像を選択するために用いる乱数を生成する。
【００２５】
演算制御部１１０は、秘密情報に基づく演算処理を制御する。本実施の形態では、演算制御部１１０は、暗号文データの復号処理を実行する。演算制御部１１０は、変換部１１１と、演算処理部１１２と、判定部１１３と、を含んでいる。
【００２６】
変換部１１１は、復号処理で扱う各種データの表現形式を相互に変換する。例えば、変換部１１１は、アフィン表現に圧縮された暗号文データを射影表現に変換する。また、変換部１１１は、射影表現で復号された平文データをアフィン表現に変換する。
【００２７】
ここで、本実施の形態で用いる各表現、および表現間の変換方法の詳細について説明する。まず、本実施の形態で用いる用語の定義について説明する。
【００２８】
（定義１）有限個の元からなる体を有限体（finite field）といい、Ｆｐと表す。ここで、ｐは素数である。有限体Ｆｐの元は、（１）式を満たす非負整数で表される。
【数１】
【００２９】
（定義２）以下の（２）式の有限体（以下、Ｆｐ＾ｍと表記する）の元は、以下の（３）式で示すように、Ｆｐに係数を持つ高々（ｍ−１）次（ｍは正整数）の多項式で表される。以下、ｚを多項式の不定元とする。
【数２】
【００３０】
（定義３）以下の（４）式の有限体（以下、Ｆ（ｐ＾ｍ）＾３と表記する）の元は、以下の（５）式で示すように、Ｆｐ＾ｍに係数を持つ高々２次の多項式で表される。以下、ｙを多項式の不定元とする。
【数３】
【００３１】
（定義４）代数的トーラスを、以下の（６）式で表す（以下、Ｔ６（Ｆｐ＾ｍ）と表記する）。
【数４】
【００３２】
（定義５）Ｔ６（Ｆｐ＾ｍ）の要素は、以下の（７）式のようにα，β∈Ｆ（ｐ＾ｍ）＾３を用いて表される。ここで、α＋βｘはＦ（ｐ＾ｍ）＾６の要素であり、Ｆ（ｐ＾ｍ）＾３に係数を持つ高々１次の多項式で表される。有限体Ｆ（ｐ＾ｍ）＾６の元は、Ｆ（ｐ＾ｍ）＾３の要素を係数とし、２次の原始既約多項式の根ηを変数とする１次式ａ０＋ａ１η，ａｉ∈Ｆ（ｐ＾ｍ）＾３で表される。ｘは多項式の不定元である。また、αとβとが（７）式の条件を満たすとき、射影表現を以下の（８）式のように簡略化して表現する。
【数５】
【００３３】
（定義６）（９）式で表される代数的トーラスの単位元を除く要素は、以下の（１０）式を満たすｃ０，ｃ１を用いて表される。ここで、（１１）式は有限体Ｆｐ＾ｍの零元以外の元から構成される、有限体Ｆｐ＾ｍの乗法群を表す。また、（１０）式のｗは、（１１）式の乗法群の要素であって、計算効率等を考慮して事前に定められた値をとる。ｃ０，ｃ１が（１０）式を満たすとき、アフィン表現を以下の（１２）式のように簡略化して表現する。
【数６】
【００３４】
以上の定義を元に、変換部１１１が実行する表現間の変換処理について説明する。まず、変換部１１１がアフィン表現を射影表現に変換する複数の写像の基準となる写像（基準写像）について説明する。
【００３５】
基準写像は、以下の（１３）式に示すアフィン表現を入力とし、（１４）式に示す射影表現を出力する写像である。具体的には、基準写像は、以下の（１５）式に示す手順に従い、アフィン表現の分数式である上述の（１０）式を、射影表現の分数式である上述の（８）式に読み換えることにより、アフィン表現を射影表現に変換する。なお、（１５）式の手順５、６は、ｂ１、ｂ２の値をＦｐ＾ｍの零元とすることを表している。
【数７】
【００３６】
次に、変換部１１１が射影表現をアフィン表現に変換する写像について説明する。変換部１１１は、以下の（１６）式に示す射影表現を入力とし、（１７）式に示すアフィン表現を出力することにより、射影表現をアフィン表現に変換する。具体的には、変換部１１１は、以下の（１８）式に示す手順に従って射影表現をアフィン表現に変換する。なお、（１８）式の手順１は、βがＦ（ｐ＾ｍ）＾３の零元である場合、ｃ０，ｃ１の値をＦｐ＾ｍの零元とすることを表している。
【数８】
【００３７】
本実施の形態では、（１３）式から（１５）式で説明した基準写像が出力する射影表現をＦ（ｐ＾ｍ）＾３の要素であるｋで乗じた射影表現を出力する複数の変換写像を定義して利用する。すなわち、ｎ（ｎは２以上の整数）個のＦ（ｐ＾ｍ）＾３の要素ｋ１〜ｋｎを予め定め、基準写像が出力する射影表現（α，β）をｋ１〜ｋｎ倍した射影表現（ｋ１α，ｋ１β）〜（ｋｎα，ｋｎβ）をそれぞれ出力する、ｎ個の変換写像を用いる。
【００３８】
そして、変換部１１１は、このように定義された複数の変換写像のうち、乱数生成部１０３によって生成された乱数に応じて予め定められた変換写像を選択し、選択した変換写像によってアフィン表現を射影表現に変換する。
【００３９】
図３は、乱数の使用方法を示す説明図である。図３のＣＰＴ３０１は圧縮暗号文データを表している。本実施の形態では、上述のように分割部１０２がＣＰＴ３０１を複数の部分データ３１１〜３１ｔ（ｃｐｔ１〜ｃｐｔｔ）。そして、本実施の形態では、変換部１１１が、ｎ個のｋ（＝ｋ１〜ｋｎ）から乱数に応じて選択されたｋに対応する変換写像によって、各部分データｃｐｔ１〜ｃｐｔｔを復号化する。
【００４０】
なお、複数の変換写像で変換された複数の射影表現は、いずれも同一のアフィン表現に対応する。これは、（１８）式の手順２．１で、αをβで除算したγを求めるときにｋが相殺されるためである。このため、複数の変換写像のうちいずれかの変換写像で変換された射影表現による演算結果と、他の変換写像で変換された射影表現による演算結果は、アフィン表現で表すと一致する。
【００４１】
演算処理部１１２は、変換部１１１によって射影表現に変換された暗号文データに対して秘密情報を用いて演算処理を実行する。具体的には、演算処理部１１２は、暗号文データに対して秘密鍵データを用いて、有限体上の離散対数問題に基づいた復号処理を施して平文データを算出する。具体的には、演算処理部１１２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて暗号文データに復号処理を施して平文データを出力する。なお、演算処理部１１２がＥｌＧａｍａｌ暗号などの他の暗号方式を利用するように構成してもよい。
【００４２】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図４は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。図４で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ〜，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００４３】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文データｍに対応する暗号文データ（ｃｔ１，ｃｔ２，ｃｔ３，ｃｔ４）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖを求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００４４】
復号処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃｔ１，ｃｔ２，ｃｔ３，ｃｔ４）から正当な平文データであるか否かのチェックを行い、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃｔ∈？Ｇ（またはＧ〜）は、ｃｔが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００４５】
なお、上述のように、解読されうる秘密情報は、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）だけでなく、計算の途中に出現するｂ（１１−３）、乱数ｒ、およびハッシュ値ｖなども含まれる。
【００４６】
図２に戻り、判定部１１３は、暗号文データの正当性を判定する。例えば、判定部１１３は、暗号文データの各要素が正しい群の元であるか否かを判定する。また、判定部１１３は、入力された暗号文データのハッシュ値を算出し、算出したハッシュ値を用いて算出した値と、入力された暗号文データの所定の成分とを比較し、両者が一致しているか否かによって、暗号文データが正当であることを判定する。
【００４７】
次に、このように構成された本実施の形態にかかる演算装置１００による復号処理について図５を用いて説明する。図５は、本実施の形態における復号処理の全体の流れを示すフローチャートである。
【００４８】
まず、入力部１０１は、上述のＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式で暗号化され、アフィン表現に圧縮された暗号文データ（圧縮暗号文データ）を入力する（ステップＳ５０１）。例えば、入力部１０１は、暗号化装置２００から受信され、記憶部１０４に保存された圧縮暗号文データを記憶部１０４から入力する。
【００４９】
次に、分割部１０２は、入力された圧縮暗号文データを複数の部分データに分割する（ステップＳ５０２）。以下では、各部分データを４つの成分（ｃｔ１＊，ｃｔ２＊，ｃｔ３＊，ｃｔ４＊）で表す。なお、以下では、記号「＊」が付与された変数は、アフィン表現で表されたデータを意味する。また、記号「’」が付与された変数は射影表現で表されたデータを意味する。
【００５０】
次に、演算制御部１１０は、未処理の部分データを取得する（ステップＳ５０３）。次に、判定部１１３が、取得した部分データの成分（要素）であるｃｔ１＊、ｃｔ２＊、ｃｔ３＊、ｃｔ４＊のそれぞれが正しい群の元であるか否か、すなわち、ｃｔ１＊，ｃｔ２＊，ｃｔ３＊，ｃｔ４＊∈Ｇ４を満たすか否かを判断する（ステップＳ５０４）。
【００５１】
部分データの成分が正しい群の元でないと判断された場合は（ステップＳ５０４：ＮＯ）、復号処理を終了する。部分データの成分が正しい群の元であると判断された場合（ステップＳ５０４：ＹＥＳ）、演算制御部１１０は、ハッシュ関数Ｈへの入力としてｃｔ１＊、ｃｔ２＊、ｃｔ３＊を用いてハッシュ値ｖ＝Ｈ（ｃｔ１＊、ｃｔ２＊、ｃｔ３＊）を算出する（ステップＳ５０５）。
【００５２】
次に、乱数生成部１０３が乱数を生成する（ステップＳ５０６）。そして、変換部１１１は、生成された乱数に対応する変換写像を選択する（ステップＳ５０７）。
【００５３】
複数の変換写像と乱数とは、例えば以下のように対応づけることができる。複数の変換写像は、上述のようにＦ（ｐ＾ｍ）＾３の要素であるｋによって識別される。また、ｋはそれぞれ３ｍ個の要素を持つベクトルで表現することができる。そこで、乱数生成部１０３が、０からｐ３ｍ−１までのいずれかの値を取るような乱数を生成するように構成する。そして、生成した乱数を３ｍ桁のｐ進数で表したときの各桁の値を、ベクトルの各要素とするｋに対応づける。これにより、生成した乱数を、ｐ３ｍ個の異なるｋに対応させることができる。
【００５４】
なお、乱数と変換写像とを対応づける方法はこれに限られるものではなく、乱数に応じて、複数の変換写像のうちいずれかを選択可能な方法であればあらゆる方法を適用できる。
【００５５】
次に、変換部１１１は、選択した変換写像によって、アフィン表現で表されたｃｔ１＊、ｃｔ２＊を射影表現ｃｔ１’、ｃｔ２’に変換する（ステップＳ５０８）。また、演算処理部１１２は、ハッシュ値ｖと、ｃｔ１’、ｃｔ２’と、秘密鍵データのうちｘ１、ｘ２、ｙ１、ｙ２とを用いて、べき乗計算Ｋ’＝ｃｔ１’（ｘ１＋ｙ１ｖ）ｃｔ２’（ｘ２＋ｙ２ｖ）を実行する（ステップＳ５０９）。そして、変換部１１１は、射影表現で表されたＫ’をアフィン表現Ｋ＊に変換する（ステップＳ５１０）。
【００５６】
次に、判定部１１３は、Ｋ＊と入力された暗号文データの成分のうちｃｔ４＊とが一致するか否かを判断する（ステップＳ５１１）。なお、本ステップでは、Ｋ＊とｃｔ４＊とが等価であることを確認できればよい。したがって、射影表現Ｋ’をアフィン表現Ｋ＊に変換する代わりに、拡大体表現Ｋに変換し、Ｋとｃｔ４とが一致することを確認するように構成してもよい。
【００５７】
一致しない場合は（ステップＳ５１１：ＮＯ）、復号処理を終了する。一致する場合は（ステップＳ５１１：ＹＥＳ）、変換部１１１は、アフィン表現で表されたｃｔ３＊を射影表現ｃｔ３’に変換する（ステップＳ５１２）。次に、演算処理部１１２は、ｃｔ１’、ｃｔ２’と、秘密鍵データのうちｚ１、ｚ２とを用いて、べき乗計算ｂ’＝ ｃｔ１’ｚ１ｃｔ２’ｚ２を実行する（ステップＳ５１３）。
【００５８】
次に、演算処理部１１２は、変換により得られたｃｔ３’と、算出されたｂ’とを用いて、射影表現で表された、部分データに対応する復号データｍ’＝ｃｔ３’ｂ’−１を算出する（ステップＳ５１４）。次に、変換部１１１が、復号データｍ’をアフィン表現で表された平文データｍ＊に変換する（ステップＳ５１５）。
【００５９】
次に、演算制御部１１０は、すべての部分データを処理したか否かを判断する（ステップＳ５１６）。すべての部分データを処理していない場合は（ステップＳ５１６：ＮＯ）、次の未処理の部分データを取得して処理を繰り返す（ステップＳ５０３）。
【００６０】
すべての部分データを処理した場合は（ステップＳ５１６：ＹＥＳ）、演算処理部１１２が、各部分データに対応する復号データｍ’を結合した平文データを算出し（ステップＳ５１７）、復号処理を終了する。
【００６１】
なお、本実施の形態では、復号する圧縮暗号文データを部分データに分割し、分割した部分データ単位で、乱数に応じて選択した変換写像を利用していた。これに対し、演算装置１００内に備えられたタイマーなどによって時間を計測し、一定時間が経過するごとに利用する変換写像を切り替えるように構成してもよい。
【００６２】
このように、本実施の形態にかかる復号装置では、アフィン表現をそれぞれ異なる射影表現に変換する複数の変換写像を用意し、その中からランダムに選択した１つの変換写像を用いてアフィン表現を射影表現に変換する。そして、変換した射影表現を用いて復号処理の演算を実行する。これにより、秘密情報を用いた演算処理のランダム性を増加させ、安全性を向上させることができる。
【００６３】
次に、本実施の形態にかかる復号装置のハードウェア構成について図６を用いて説明する。図６は、本実施の形態にかかる復号装置のハードウェア構成を示す説明図である。
【００６４】
本実施の形態にかかる復号装置は、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【００６５】
本実施の形態にかかる復号装置で実行される復号プログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【００６６】
本実施の形態にかかる復号装置で実行される復号プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【００６７】
さらに、本実施の形態にかかる復号装置で実行される復号プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施の形態にかかる復号装置で実行される復号プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【００６８】
本実施の形態にかかる復号装置で実行される復号プログラムは、上述した各部（部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１が上記ＲＯＭ５２から復号プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【００６９】
以上のように、本発明にかかる装置、方法およびプログラムは、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式のように、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを復号化する装置に適している。
【図面の簡単な説明】
【００７０】
【図１】本実施の形態にかかる暗号処理システムの概要を示す図である。
【図２】本実施の形態にかかる復号装置のブロック図である。
【図３】乱数の使用方法を示す説明図である。
【図４】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図５】本実施の形態における復号処理の全体の流れを示すフローチャートである。
【図６】本実施の形態にかかる復号装置のハードウェア構成を示す説明図である。
【符号の説明】
【００７１】
５１ ＣＰＵ
５２ ＲＯＭ
５３ ＲＡＭ
５４ 通信Ｉ／Ｆ
６１ バス
１００ 演算装置
１０１ 入力部
１０２ 分割部
１０３ 乱数生成部
１０４ 記憶部
１１０ 演算制御部
１１１ 変換部
１１２ 演算処理部
１１３ 判定部
２００ 暗号化装置
【技術分野】
【０００１】
この発明は、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する装置、方法およびプログラムに関する。
【背景技術】
【０００２】
事前に鍵を共有することを必要とせずに安全な通信を実現する公開鍵暗号は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになっている。
【０００３】
公開鍵暗号において現在の典型的な暗号系サイズは１０２４ビットである。なお、暗号系サイズとは、公開鍵暗号で用いる表現形式で表した場合のデータのサイズを表す。例えば公開鍵暗号方式の１つであるＣｒａｍｅｒ−Ｓｈｏｕｐ暗号等では、１０２４ビットの拡大体表現と呼ばれる表現形式で各種データが表現される。計算機の進歩とともに攻撃者の能力も上がっているため、解読が困難とされる暗号系サイズは年々大きくなっている。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となる。例えば、公開鍵サイズは、暗号系サイズと鍵の個数との積になる。また、暗号文サイズは、暗号系サイズと、１つのメッセージを暗号化するのに必要な暗号文の数との積になる。したがって、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する暗号圧縮技術が提案されている（例えば、非特許文献１）。この暗号圧縮技術は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。また、圧縮率、すなわち圧縮前のビット数の圧縮後のビット数に対する割合を増大するための改良技術として、集合の要素を小さいビット数の表現に変換する際に付加的な入力を用いる技術が知られている（例えば、非特許文献２）。
【０００５】
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＲＹＰＴＯ ２００３，Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ２７２９，３４９−３６５，２００３．
【非特許文献２】Ｍ．ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ．Ｗｏｏｄｒｕｆｆ．“Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ” ＣＲＹＰＴＯ ２００４，Ｓｐｒｉｎｇｅｒ ＬＮＣＳ ３１５２，１５７−１７８，２００４．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１などの代数的トーラスを用いた暗号圧縮技術では、電磁波解析などにより秘密情報を解読するサイドチャネル攻撃などへの対処が考慮されていないため、不正な攻撃に対してセキュリティが低下する場合があるという問題があった。
【０００７】
ここで、秘密情報とは、演算処理の途中において出現する、非公開情報の一切を表す。例えば、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号では、秘密鍵だけでなく、暗号化処理の計算途中に出現するハッシュ値やランダムに生成される乱数なども秘密情報に含まれる。公開鍵などは、非公開情報でないため、秘密情報には当たらない。
【０００８】
本発明は、上記に鑑みてなされたものであって、秘密情報を用いた演算処理の安全性を向上させることができる装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明は、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置であって、前記部分群上の元である入力データを入力する入力部と、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理部と、を備えたことを特徴とする。
【００１０】
また、本発明は、上記装置を実行することができる方法およびプログラムである。
【発明の効果】
【００１１】
本発明によれば、秘密情報を用いた演算処理の安全性を向上させることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、この発明にかかる装置、方法およびプログラムの最良な実施の形態を詳細に説明する。なお、以下では、秘密情報を用いた演算処理を実行する演算装置（秘密情報に基づく演算装置）を、代数的トーラスを用いた暗号圧縮技術によって暗号化された暗号化データを秘密情報を用いて復号する復号装置として実現した例について説明する。適用可能な装置は復号装置に限られるものではなく、乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する装置であれば、あらゆる装置に適用できる。例えば、秘密鍵データを用いて署名を作成する装置に対しても本実施の形態の手法を適用できる。
【００１３】
一般に、四則演算が定義される数の集合である体のうち、数の集合が有限の体は有限体と呼ばれる。また、有限体に含まれる数の個数は素数であるか素数のべき乗であることが知られている。このような体は、それぞれ素体と拡大体と呼ばれる。暗号圧縮技術で用いられる代数的トーラスは、拡大体上の乗法群の部分群である。
【００１４】
代数的トーラスの表現としては、拡大体表現、射影表現、およびアフィン表現の３種類が存在する。従来の代数的トーラスを用いた暗号圧縮技術では、まず、暗号化装置がメッセージを拡大体表現となっている代数的トーラスの要素に対応させる。次に、拡大体表現で計算を行って暗号文データを算出し、暗号文データを圧縮したアフィン表現へと変換し、圧縮された圧縮暗号文データを復号装置に送信する。復号装置では、受信した圧縮暗号文データを拡大体表現に変換し、拡大体表現で計算を行って平文データを復号する。
【００１５】
一方、本実施の形態にかかる復号装置は、まず、アフィン表現で表された圧縮暗号文データを拡大体表現ではなく射影表現に変換して計算を実行する。このとき、アフィン表現をそれぞれ異なる射影表現に変換する複数の変換写像を用意し、その中からランダムに選択した１つの変換写像を用いてアフィン表現を射影表現に変換する。
【００１６】
これにより、復号処理のランダム性が増加し、安全性が向上する。すなわち、電磁波解析などにより秘密鍵を解読するサイドチャネル攻撃等を受けた場合であっても、波形が一定にならないため秘密鍵を解読されるおそれが低下する。
【００１７】
ここで、本実施の形態にかかる暗号処理システムの概要について用いて説明する。図１は、本実施の形態にかかる暗号処理システムの概要を示す図である。図１に示すように、本実施の形態にかかる暗号処理システムは、暗号化装置２００と、秘密情報に基づく演算装置１００とを含んでいる。
【００１８】
暗号化装置２００は、乗法群の部分群である代数的トーラス上の離散対数問題に基づく公開鍵暗号方式により平文データを暗号化した暗号文を生成し、生成した暗号文をアフィン表現に圧縮して演算装置１００に送信する。
【００１９】
演算装置１００は、アフィン表現で表された暗号文を受信すると、暗号文のアフィン表現を、対応する複数の射影表現のうち、乱数に応じて選択されるいずれかの射影表現に変換する。そして、演算装置１００は、変換した射影表現を用いて演算を実行し、代数的トーラス上の元である平文データを演算結果として出力する。
【００２０】
従来の復号装置は、アフィン表現を対応する１つの射影表現に変換して演算していた。これに対し、本実施の形態では、同図に示したように、複数の射影表現から選択した射影表現に変換して演算を実行できる。これにより、秘密情報を用いた演算処理の１つである代数的トーラスを用いた暗号方式のランダム性を増加させることができる。
【００２１】
次に、本実施の形態にかかる演算装置１００の構成について説明する。図２は、本実施の形態にかかる演算装置１００のブロック図である。図２に示すように、演算装置１００は、代数的トーラスを用いた公開鍵暗号方式で暗号化された暗号文データを復元する装置であり、入力部１０１と、分割部１０２と、乱数生成部１０３と、演算制御部１１０と、記憶部１０４と、を備えている。
【００２２】
入力部１０１は、暗号化装置２００から送信された圧縮暗号文データや、復号化に用いる公開鍵暗号方式の秘密鍵データなどの入力データを入力する。記憶部１０４は、入力された圧縮暗号文データや秘密鍵データなどを保存する。記憶部１０４は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００２３】
分割部１０２は、入力された圧縮暗号文データを、復号処理の単位とする複数の部分データに分割する。例えば、分割部１０２は、圧縮暗号文データを、予め定められたサイズの部分データごとに分割する。なお、分割方法はこれに限られるものではない。また、演算装置１００内では圧縮暗号文データを分割しないように構成してもよい。例えば、暗号化装置２００が平文データを部分データに分割し、各部分データを暗号化および圧縮した複数の圧縮暗号文データを送信するように構成してもよい。この場合、演算装置１００は、複数の圧縮暗号文データを単位として復号処理を実行すればよい。
【００２４】
乱数生成部１０３は、変換部１１１（後述）が複数の変換写像から１つの変換写像を選択するために用いる乱数を生成する。
【００２５】
演算制御部１１０は、秘密情報に基づく演算処理を制御する。本実施の形態では、演算制御部１１０は、暗号文データの復号処理を実行する。演算制御部１１０は、変換部１１１と、演算処理部１１２と、判定部１１３と、を含んでいる。
【００２６】
変換部１１１は、復号処理で扱う各種データの表現形式を相互に変換する。例えば、変換部１１１は、アフィン表現に圧縮された暗号文データを射影表現に変換する。また、変換部１１１は、射影表現で復号された平文データをアフィン表現に変換する。
【００２７】
ここで、本実施の形態で用いる各表現、および表現間の変換方法の詳細について説明する。まず、本実施の形態で用いる用語の定義について説明する。
【００２８】
（定義１）有限個の元からなる体を有限体（finite field）といい、Ｆｐと表す。ここで、ｐは素数である。有限体Ｆｐの元は、（１）式を満たす非負整数で表される。
【数１】
【００２９】
（定義２）以下の（２）式の有限体（以下、Ｆｐ＾ｍと表記する）の元は、以下の（３）式で示すように、Ｆｐに係数を持つ高々（ｍ−１）次（ｍは正整数）の多項式で表される。以下、ｚを多項式の不定元とする。
【数２】
【００３０】
（定義３）以下の（４）式の有限体（以下、Ｆ（ｐ＾ｍ）＾３と表記する）の元は、以下の（５）式で示すように、Ｆｐ＾ｍに係数を持つ高々２次の多項式で表される。以下、ｙを多項式の不定元とする。
【数３】
【００３１】
（定義４）代数的トーラスを、以下の（６）式で表す（以下、Ｔ６（Ｆｐ＾ｍ）と表記する）。
【数４】
【００３２】
（定義５）Ｔ６（Ｆｐ＾ｍ）の要素は、以下の（７）式のようにα，β∈Ｆ（ｐ＾ｍ）＾３を用いて表される。ここで、α＋βｘはＦ（ｐ＾ｍ）＾６の要素であり、Ｆ（ｐ＾ｍ）＾３に係数を持つ高々１次の多項式で表される。有限体Ｆ（ｐ＾ｍ）＾６の元は、Ｆ（ｐ＾ｍ）＾３の要素を係数とし、２次の原始既約多項式の根ηを変数とする１次式ａ０＋ａ１η，ａｉ∈Ｆ（ｐ＾ｍ）＾３で表される。ｘは多項式の不定元である。また、αとβとが（７）式の条件を満たすとき、射影表現を以下の（８）式のように簡略化して表現する。
【数５】
【００３３】
（定義６）（９）式で表される代数的トーラスの単位元を除く要素は、以下の（１０）式を満たすｃ０，ｃ１を用いて表される。ここで、（１１）式は有限体Ｆｐ＾ｍの零元以外の元から構成される、有限体Ｆｐ＾ｍの乗法群を表す。また、（１０）式のｗは、（１１）式の乗法群の要素であって、計算効率等を考慮して事前に定められた値をとる。ｃ０，ｃ１が（１０）式を満たすとき、アフィン表現を以下の（１２）式のように簡略化して表現する。
【数６】
【００３４】
以上の定義を元に、変換部１１１が実行する表現間の変換処理について説明する。まず、変換部１１１がアフィン表現を射影表現に変換する複数の写像の基準となる写像（基準写像）について説明する。
【００３５】
基準写像は、以下の（１３）式に示すアフィン表現を入力とし、（１４）式に示す射影表現を出力する写像である。具体的には、基準写像は、以下の（１５）式に示す手順に従い、アフィン表現の分数式である上述の（１０）式を、射影表現の分数式である上述の（８）式に読み換えることにより、アフィン表現を射影表現に変換する。なお、（１５）式の手順５、６は、ｂ１、ｂ２の値をＦｐ＾ｍの零元とすることを表している。
【数７】
【００３６】
次に、変換部１１１が射影表現をアフィン表現に変換する写像について説明する。変換部１１１は、以下の（１６）式に示す射影表現を入力とし、（１７）式に示すアフィン表現を出力することにより、射影表現をアフィン表現に変換する。具体的には、変換部１１１は、以下の（１８）式に示す手順に従って射影表現をアフィン表現に変換する。なお、（１８）式の手順１は、βがＦ（ｐ＾ｍ）＾３の零元である場合、ｃ０，ｃ１の値をＦｐ＾ｍの零元とすることを表している。
【数８】
【００３７】
本実施の形態では、（１３）式から（１５）式で説明した基準写像が出力する射影表現をＦ（ｐ＾ｍ）＾３の要素であるｋで乗じた射影表現を出力する複数の変換写像を定義して利用する。すなわち、ｎ（ｎは２以上の整数）個のＦ（ｐ＾ｍ）＾３の要素ｋ１〜ｋｎを予め定め、基準写像が出力する射影表現（α，β）をｋ１〜ｋｎ倍した射影表現（ｋ１α，ｋ１β）〜（ｋｎα，ｋｎβ）をそれぞれ出力する、ｎ個の変換写像を用いる。
【００３８】
そして、変換部１１１は、このように定義された複数の変換写像のうち、乱数生成部１０３によって生成された乱数に応じて予め定められた変換写像を選択し、選択した変換写像によってアフィン表現を射影表現に変換する。
【００３９】
図３は、乱数の使用方法を示す説明図である。図３のＣＰＴ３０１は圧縮暗号文データを表している。本実施の形態では、上述のように分割部１０２がＣＰＴ３０１を複数の部分データ３１１〜３１ｔ（ｃｐｔ１〜ｃｐｔｔ）。そして、本実施の形態では、変換部１１１が、ｎ個のｋ（＝ｋ１〜ｋｎ）から乱数に応じて選択されたｋに対応する変換写像によって、各部分データｃｐｔ１〜ｃｐｔｔを復号化する。
【００４０】
なお、複数の変換写像で変換された複数の射影表現は、いずれも同一のアフィン表現に対応する。これは、（１８）式の手順２．１で、αをβで除算したγを求めるときにｋが相殺されるためである。このため、複数の変換写像のうちいずれかの変換写像で変換された射影表現による演算結果と、他の変換写像で変換された射影表現による演算結果は、アフィン表現で表すと一致する。
【００４１】
演算処理部１１２は、変換部１１１によって射影表現に変換された暗号文データに対して秘密情報を用いて演算処理を実行する。具体的には、演算処理部１１２は、暗号文データに対して秘密鍵データを用いて、有限体上の離散対数問題に基づいた復号処理を施して平文データを算出する。具体的には、演算処理部１１２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて暗号文データに復号処理を施して平文データを出力する。なお、演算処理部１１２がＥｌＧａｍａｌ暗号などの他の暗号方式を利用するように構成してもよい。
【００４２】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図４は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。図４で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ〜，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００４３】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文データｍに対応する暗号文データ（ｃｔ１，ｃｔ２，ｃｔ３，ｃｔ４）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖを求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００４４】
復号処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃｔ１，ｃｔ２，ｃｔ３，ｃｔ４）から正当な平文データであるか否かのチェックを行い、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃｔ∈？Ｇ（またはＧ〜）は、ｃｔが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００４５】
なお、上述のように、解読されうる秘密情報は、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）だけでなく、計算の途中に出現するｂ（１１−３）、乱数ｒ、およびハッシュ値ｖなども含まれる。
【００４６】
図２に戻り、判定部１１３は、暗号文データの正当性を判定する。例えば、判定部１１３は、暗号文データの各要素が正しい群の元であるか否かを判定する。また、判定部１１３は、入力された暗号文データのハッシュ値を算出し、算出したハッシュ値を用いて算出した値と、入力された暗号文データの所定の成分とを比較し、両者が一致しているか否かによって、暗号文データが正当であることを判定する。
【００４７】
次に、このように構成された本実施の形態にかかる演算装置１００による復号処理について図５を用いて説明する。図５は、本実施の形態における復号処理の全体の流れを示すフローチャートである。
【００４８】
まず、入力部１０１は、上述のＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式で暗号化され、アフィン表現に圧縮された暗号文データ（圧縮暗号文データ）を入力する（ステップＳ５０１）。例えば、入力部１０１は、暗号化装置２００から受信され、記憶部１０４に保存された圧縮暗号文データを記憶部１０４から入力する。
【００４９】
次に、分割部１０２は、入力された圧縮暗号文データを複数の部分データに分割する（ステップＳ５０２）。以下では、各部分データを４つの成分（ｃｔ１＊，ｃｔ２＊，ｃｔ３＊，ｃｔ４＊）で表す。なお、以下では、記号「＊」が付与された変数は、アフィン表現で表されたデータを意味する。また、記号「’」が付与された変数は射影表現で表されたデータを意味する。
【００５０】
次に、演算制御部１１０は、未処理の部分データを取得する（ステップＳ５０３）。次に、判定部１１３が、取得した部分データの成分（要素）であるｃｔ１＊、ｃｔ２＊、ｃｔ３＊、ｃｔ４＊のそれぞれが正しい群の元であるか否か、すなわち、ｃｔ１＊，ｃｔ２＊，ｃｔ３＊，ｃｔ４＊∈Ｇ４を満たすか否かを判断する（ステップＳ５０４）。
【００５１】
部分データの成分が正しい群の元でないと判断された場合は（ステップＳ５０４：ＮＯ）、復号処理を終了する。部分データの成分が正しい群の元であると判断された場合（ステップＳ５０４：ＹＥＳ）、演算制御部１１０は、ハッシュ関数Ｈへの入力としてｃｔ１＊、ｃｔ２＊、ｃｔ３＊を用いてハッシュ値ｖ＝Ｈ（ｃｔ１＊、ｃｔ２＊、ｃｔ３＊）を算出する（ステップＳ５０５）。
【００５２】
次に、乱数生成部１０３が乱数を生成する（ステップＳ５０６）。そして、変換部１１１は、生成された乱数に対応する変換写像を選択する（ステップＳ５０７）。
【００５３】
複数の変換写像と乱数とは、例えば以下のように対応づけることができる。複数の変換写像は、上述のようにＦ（ｐ＾ｍ）＾３の要素であるｋによって識別される。また、ｋはそれぞれ３ｍ個の要素を持つベクトルで表現することができる。そこで、乱数生成部１０３が、０からｐ３ｍ−１までのいずれかの値を取るような乱数を生成するように構成する。そして、生成した乱数を３ｍ桁のｐ進数で表したときの各桁の値を、ベクトルの各要素とするｋに対応づける。これにより、生成した乱数を、ｐ３ｍ個の異なるｋに対応させることができる。
【００５４】
なお、乱数と変換写像とを対応づける方法はこれに限られるものではなく、乱数に応じて、複数の変換写像のうちいずれかを選択可能な方法であればあらゆる方法を適用できる。
【００５５】
次に、変換部１１１は、選択した変換写像によって、アフィン表現で表されたｃｔ１＊、ｃｔ２＊を射影表現ｃｔ１’、ｃｔ２’に変換する（ステップＳ５０８）。また、演算処理部１１２は、ハッシュ値ｖと、ｃｔ１’、ｃｔ２’と、秘密鍵データのうちｘ１、ｘ２、ｙ１、ｙ２とを用いて、べき乗計算Ｋ’＝ｃｔ１’（ｘ１＋ｙ１ｖ）ｃｔ２’（ｘ２＋ｙ２ｖ）を実行する（ステップＳ５０９）。そして、変換部１１１は、射影表現で表されたＫ’をアフィン表現Ｋ＊に変換する（ステップＳ５１０）。
【００５６】
次に、判定部１１３は、Ｋ＊と入力された暗号文データの成分のうちｃｔ４＊とが一致するか否かを判断する（ステップＳ５１１）。なお、本ステップでは、Ｋ＊とｃｔ４＊とが等価であることを確認できればよい。したがって、射影表現Ｋ’をアフィン表現Ｋ＊に変換する代わりに、拡大体表現Ｋに変換し、Ｋとｃｔ４とが一致することを確認するように構成してもよい。
【００５７】
一致しない場合は（ステップＳ５１１：ＮＯ）、復号処理を終了する。一致する場合は（ステップＳ５１１：ＹＥＳ）、変換部１１１は、アフィン表現で表されたｃｔ３＊を射影表現ｃｔ３’に変換する（ステップＳ５１２）。次に、演算処理部１１２は、ｃｔ１’、ｃｔ２’と、秘密鍵データのうちｚ１、ｚ２とを用いて、べき乗計算ｂ’＝ ｃｔ１’ｚ１ｃｔ２’ｚ２を実行する（ステップＳ５１３）。
【００５８】
次に、演算処理部１１２は、変換により得られたｃｔ３’と、算出されたｂ’とを用いて、射影表現で表された、部分データに対応する復号データｍ’＝ｃｔ３’ｂ’−１を算出する（ステップＳ５１４）。次に、変換部１１１が、復号データｍ’をアフィン表現で表された平文データｍ＊に変換する（ステップＳ５１５）。
【００５９】
次に、演算制御部１１０は、すべての部分データを処理したか否かを判断する（ステップＳ５１６）。すべての部分データを処理していない場合は（ステップＳ５１６：ＮＯ）、次の未処理の部分データを取得して処理を繰り返す（ステップＳ５０３）。
【００６０】
すべての部分データを処理した場合は（ステップＳ５１６：ＹＥＳ）、演算処理部１１２が、各部分データに対応する復号データｍ’を結合した平文データを算出し（ステップＳ５１７）、復号処理を終了する。
【００６１】
なお、本実施の形態では、復号する圧縮暗号文データを部分データに分割し、分割した部分データ単位で、乱数に応じて選択した変換写像を利用していた。これに対し、演算装置１００内に備えられたタイマーなどによって時間を計測し、一定時間が経過するごとに利用する変換写像を切り替えるように構成してもよい。
【００６２】
このように、本実施の形態にかかる復号装置では、アフィン表現をそれぞれ異なる射影表現に変換する複数の変換写像を用意し、その中からランダムに選択した１つの変換写像を用いてアフィン表現を射影表現に変換する。そして、変換した射影表現を用いて復号処理の演算を実行する。これにより、秘密情報を用いた演算処理のランダム性を増加させ、安全性を向上させることができる。
【００６３】
次に、本実施の形態にかかる復号装置のハードウェア構成について図６を用いて説明する。図６は、本実施の形態にかかる復号装置のハードウェア構成を示す説明図である。
【００６４】
本実施の形態にかかる復号装置は、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【００６５】
本実施の形態にかかる復号装置で実行される復号プログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【００６６】
本実施の形態にかかる復号装置で実行される復号プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【００６７】
さらに、本実施の形態にかかる復号装置で実行される復号プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施の形態にかかる復号装置で実行される復号プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【００６８】
本実施の形態にかかる復号装置で実行される復号プログラムは、上述した各部（部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１が上記ＲＯＭ５２から復号プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【００６９】
以上のように、本発明にかかる装置、方法およびプログラムは、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式のように、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを復号化する装置に適している。
【図面の簡単な説明】
【００７０】
【図１】本実施の形態にかかる暗号処理システムの概要を示す図である。
【図２】本実施の形態にかかる復号装置のブロック図である。
【図３】乱数の使用方法を示す説明図である。
【図４】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図５】本実施の形態における復号処理の全体の流れを示すフローチャートである。
【図６】本実施の形態にかかる復号装置のハードウェア構成を示す説明図である。
【符号の説明】
【００７１】
５１ ＣＰＵ
５２ ＲＯＭ
５３ ＲＡＭ
５４ 通信Ｉ／Ｆ
６１ バス
１００ 演算装置
１０１ 入力部
１０２ 分割部
１０３ 乱数生成部
１０４ 記憶部
１１０ 演算制御部
１１１ 変換部
１１２ 演算処理部
１１３ 判定部
２００ 暗号化装置
【特許請求の範囲】
【請求項１】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置であって、
前記部分群上の元である入力データを入力する入力部と、
アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、
射影表現に変換された前記入力データに対して秘密情報を用いて演算処理を実行する演算処理部と、
を備えたことを特徴とする演算装置。
【請求項２】
前記入力データは、前記部分群上の離散対数問題に基づく暗号方式により暗号化し、前記アフィン表現で表された暗号文データであり、
前記変換部は、前記複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記暗号文データを射影表現に変換し、
前記演算処理部は、前記秘密情報を用いて、射影表現に変換された前記暗号文データに対して前記暗号方式で予め定められた復号処理を実行することにより平文データを算出すること、
を特徴とする請求項１に記載の演算装置。
【請求項３】
前記暗号方式は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であること、
を特徴とする請求項２に記載の演算装置。
【請求項４】
前記暗号方式は、代数的トーラスである前記部分群上の離散対数問題に基づく暗号方式であること、
を特徴とする請求項２に記載の演算装置。
【請求項５】
前記変換部は、予め定められた基準写像によってアフィン表現を変換した射影表現に対して予め定められた複数の乗数をそれぞれ乗じて得られる複数の射影表現を、アフィン表現の変換結果としてそれぞれ出力する複数の前記写像のうち、いずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換すること、
を特徴とする請求項１に記載の演算装置。
【請求項６】
乱数を生成する乱数生成部をさらに備え、
前記変換部は、複数の写像のうち、生成された乱数に対応するいずれか１つの前記写像を選択し、選択した前記写像によって入力された前記入力データを射影表現に変換すること、
を特徴とする請求項１に記載の演算装置。
【請求項７】
入力された前記入力データを複数の部分データに分割する分割部をさらに備え、
前記変換部は、前記部分データごとに、複数の前記写像のうちいずれか１つの前記写像を選択し、選択した前記写像によって前記部分データを射影表現に変換し、
前記演算処理部は、射影表現に変換された前記部分データに対して前記秘密情報を用いて演算処理を実行すること、
を特徴とする請求項１に記載の演算装置。
【請求項８】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算方法であって、
入力部が、前記部分群上の元である入力データを入力する入力ステップと、
変換部が、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換ステップと、
演算処理部が、射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理ステップと、
を備えたことを特徴とする演算方法。
【請求項９】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置で実行される演算プログラムであって、
前記演算装置を、
前記部分群上の元である入力データを入力する入力部と、
アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、
射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理部と、
として機能させる演算プログラム。
【請求項１】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置であって、
前記部分群上の元である入力データを入力する入力部と、
アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、
射影表現に変換された前記入力データに対して秘密情報を用いて演算処理を実行する演算処理部と、
を備えたことを特徴とする演算装置。
【請求項２】
前記入力データは、前記部分群上の離散対数問題に基づく暗号方式により暗号化し、前記アフィン表現で表された暗号文データであり、
前記変換部は、前記複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記暗号文データを射影表現に変換し、
前記演算処理部は、前記秘密情報を用いて、射影表現に変換された前記暗号文データに対して前記暗号方式で予め定められた復号処理を実行することにより平文データを算出すること、
を特徴とする請求項１に記載の演算装置。
【請求項３】
前記暗号方式は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であること、
を特徴とする請求項２に記載の演算装置。
【請求項４】
前記暗号方式は、代数的トーラスである前記部分群上の離散対数問題に基づく暗号方式であること、
を特徴とする請求項２に記載の演算装置。
【請求項５】
前記変換部は、予め定められた基準写像によってアフィン表現を変換した射影表現に対して予め定められた複数の乗数をそれぞれ乗じて得られる複数の射影表現を、アフィン表現の変換結果としてそれぞれ出力する複数の前記写像のうち、いずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換すること、
を特徴とする請求項１に記載の演算装置。
【請求項６】
乱数を生成する乱数生成部をさらに備え、
前記変換部は、複数の写像のうち、生成された乱数に対応するいずれか１つの前記写像を選択し、選択した前記写像によって入力された前記入力データを射影表現に変換すること、
を特徴とする請求項１に記載の演算装置。
【請求項７】
入力された前記入力データを複数の部分データに分割する分割部をさらに備え、
前記変換部は、前記部分データごとに、複数の前記写像のうちいずれか１つの前記写像を選択し、選択した前記写像によって前記部分データを射影表現に変換し、
前記演算処理部は、射影表現に変換された前記部分データに対して前記秘密情報を用いて演算処理を実行すること、
を特徴とする請求項１に記載の演算装置。
【請求項８】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算方法であって、
入力部が、前記部分群上の元である入力データを入力する入力ステップと、
変換部が、アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換ステップと、
演算処理部が、射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理ステップと、
を備えたことを特徴とする演算方法。
【請求項９】
乗法群の部分群上の要素に対して秘密情報を用いて演算処理を実行する演算装置で実行される演算プログラムであって、
前記演算装置を、
前記部分群上の元である入力データを入力する入力部と、
アフィン表現を射影表現に変換する複数の写像のうちいずれか１つの前記写像をランダムに選択し、選択した前記写像によって入力された前記入力データを射影表現に変換する変換部と、
射影表現に変換された前記入力データに対して前記秘密情報を用いて演算処理を実行する演算処理部と、
として機能させる演算プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−６８２９３（Ｐ２０１０−６８２９３Ａ）
【公開日】平成２２年３月２５日（２０１０．３．２５）
【国際特許分類】
【出願番号】特願２００８−２３３２３４（Ｐ２００８−２３３２３４）
【出願日】平成２０年９月１１日（２００８．９．１１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月２５日（２０１０．３．２５）
【国際特許分類】
【出願日】平成２０年９月１１日（２００８．９．１１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]