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