(57)【要約】【課題】暗号圧縮技術を用いた暗号方式による演算処理のコストを低減することができる復号装置を提供すること。【解決手段】乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化した暗号文データを復号する復号装置４００であって、部分群上の元であってアフィン表現で表された暗号文データを入力する入力部４０１と、入力された暗号文データを射影表現で表された射影表現データに変換する変換部４１１と、射影表現データに対して上記暗号方式で予め定められた復号処理を実行することにより、射影表現で表された平文データを算出する平文算出部４１２と、を備えた。【選択図】        図４
2010049212.tif 000002
【特許請求の範囲】
【請求項１】
乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化する暗号化装置であって、
前記平文データと、少なくとも一部の成分が前記部分群上の元であってアフィン表現で表された暗号鍵データと、を入力する入力部と、
入力された前記暗号鍵データの少なくとも一部を射影表現に変換する第１変換部と、
射影表現に変換された前記暗号鍵データを用いて、前記平文データに対して前記暗号方式で予め定められた暗号化処理を実行することにより、射影表現で表された暗号文データを算出する暗号文算出部と、
射影表現で表された前記暗号文データの少なくとも一部をアフィン表現に変換する第２変換部と、
を備えたことを特徴とする暗号化装置。
【請求項２】
前記入力部は、アフィン表現で表現された前記平文データと、少なくとも一部がアフィン表現で表された前記暗号鍵データとを入力し、
前記第１変換部は、さらに、アフィン表現で表現された前記平文データを射影表現に変換し、
前記暗号文算出部は、射影表現に変換された暗号鍵データを用いて、射影表現に変換された前記平文データに対して前記暗号化処理を実行することにより、射影表現で表された前記暗号文データを算出すること、
を特徴とする請求項１に記載の暗号化装置。
【請求項３】
前記入力部は、拡大体表現で表現された前記平文データと、少なくとも一部がアフィン表現で表された前記暗号鍵データとを入力し、
前記第１変換部は、さらに、拡大体表現で表現された前記平文データを射影表現に変換し、
前記暗号文算出部は、射影表現に変換された暗号鍵データを用いて、射影表現に変換された前記平文データに対して前記暗号化処理を実行することにより、射影表現で表された前記暗号文データを算出すること、
を特徴とする請求項１に記載の暗号化装置。
【請求項４】
前記暗号化装置には入力されたデータのハッシュ値を計算するハッシュ値計算部を含み、
前記ハッシュ値計算部への入力の少なくとも一部にはアフィン表現で表現された暗号文成分を含むこと
を特徴とする請求項１もしくは２もしくは３に記載の暗号化装置。
【請求項５】
前記暗号方式は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であること、
を特徴とする請求項１に記載の暗号化装置。
【請求項６】
前記暗号方式は、代数的トーラスである前記部分群上の離散対数問題に基づく暗号方式であること、
を特徴とする請求項１に記載の暗号化装置。
【請求項７】
乗法群の部分群上の離散対数問題に基づく暗号方式により暗号化された暗号文データを復号する復号装置であって、
前記部分群上の元であってアフィン表現で表された成分を少なくとも含む前記暗号文データを入力する入力部と、
前記暗号文データを射影表現で表された射影表現データに変換する変換部と、
前記射影表現データに対して前記暗号方式で予め定められた復号処理を実行することにより、射影表現で表された復号済み平文データを算出する平文算出部と、
を備えたことを特徴とする復号装置。
【請求項８】
前記入力部は、少なくとも一部の要素がアフィン表現で表された複数の要素を含む前記暗号文データを入力し、
前記変換部は、前記暗号文データに含まれる前記要素それぞれを射影表現に変換し、
前記平文算出部は、射影表現に変換された複数の前記要素を用いて前記復号処理を実行することにより、射影表現で表された前記復号済み平文データを算出すること、
を特徴とする請求項７に記載の復号装置。
【請求項９】
入力された前記暗号文データのハッシュ値を算出し、算出したハッシュ値に基づいて入力された前記暗号文データの正当性を判定する判定部をさらに備え、
前記平文算出部は、入力された前記暗号文データが正当であると判定された場合に、前記射影表現文データに対して前記復号処理を実行することにより、射影表現で表された前記復号済み平文データを算出すること、
を特徴とする請求項７に記載の復号装置。
【請求項１０】
前記変換部は、さらに、算出された前記復号済み平文データを拡大体表現に変換すること、
を特徴とする請求項７に記載の復号装置。
【請求項１１】
前記変換部は、さらに、算出された前記復号済み平文データをアフィン表現に変換すること、
を特徴とする請求項７に記載の復号装置。
【請求項１２】
前記暗号方式は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式であること、
を特徴とする請求項７に記載の復号装置。
【請求項１３】
前記暗号方式は、代数的トーラスである前記部分群上の離散対数問題に基づく暗号方式であること、
を特徴とする請求項７に記載の復号装置。
【請求項１４】
乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化する暗号化方法であって、
前記平文データと、少なくとも一部の成分が前記部分群上の元であってアフィン表現で表された暗号鍵データを入力する入力ステップと、
入力された前記暗号鍵データの少なくとも一部を射影表現に変換する第１変換ステップと、
射影表現に変換された前記暗号鍵データを用いて、前記平文データに対して前記暗号方式で予め定められた暗号化処理を実行することにより、射影表現で表された暗号文データを算出する暗号文算出ステップと、
射影表現で表された前記暗号文データの少なくとも一部をアフィン表現に変換する第２変換ステップと、
を備えたことを特徴とする暗号化方法。
【請求項１５】
乗法群の部分群上の離散対数問題に基づく暗号方式により暗号化された暗号文データを復号する復号方法であって、
入力部が、前記部分群上の元であってアフィン表現で表された前記暗号文データを入力する入力ステップと、
変換部が、前記暗号文データを射影表現で表された射影表現データに変換する変換ステップと、
平文算出部が、前記射影表現データに対して前記暗号方式で予め定められた復号処理を実行することにより、射影表現で表された平文データを算出する平文算出ステップと、
を備えたことを特徴とする復号方法。
【請求項１６】
乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化する暗号化装置で実行されるプログラムであって、
前記暗号化装置を、
前記平文データと、少なくとも一部の成分が前記部分群上の元であってアフィン表現で表された暗号鍵データと、を入力する入力部と、
入力された前記暗号鍵データの少なくとも一部を射影表現に変換する第１変換部と、
射影表現に変換された前記暗号鍵データを用いて、前記平文データに対して前記暗号方式で予め定められた暗号化処理を実行することにより、射影表現で表された暗号文データを算出する暗号文算出部と、
射影表現で表された前記暗号文データの少なくとも一部をアフィン表現に変換する第２変換部と、
として機能させるための暗号化プログラム。
【請求項１７】
乗法群の部分群上の離散対数問題に基づく暗号方式により暗号化された暗号文データを復号する復号装置で実行される復号プログラムであって、
前記復号装置を、
前記部分群上の元であってアフィン表現で表された前記暗号文データを入力する入力部と、
前記暗号文データを射影表現で表された射影表現データに変換する変換部と、
前記射影表現データに対して前記暗号方式で予め定められた復号処理を実行することにより、射影表現で表された平文データを算出する平文算出部と、
として機能させるための復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化または復号する装置、方法およびプログラムに関する。
【背景技術】
【０００２】
事前に鍵を共有することを必要とせずに安全な通信を実現する公開鍵暗号は、ネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキーム／プロトコルが用いられるようになっている。
【０００３】
公開鍵暗号において現在の典型的な暗号系サイズは１０２４ビットである。なお、暗号系サイズとは、公開鍵暗号で用いる表現形式で表した場合のデータのサイズを表す。例えば公開鍵暗号方式の１つであるＣｒａｍｅｒ−Ｓｈｏｕｐ暗号等では、１０２４ビットの拡大体表現と呼ばれる表現形式で各種データが表現される。計算機の進歩とともに攻撃者の能力も上がっているため、解読が困難とされる暗号系サイズは年々大きくなっている。公開鍵暗号では公開鍵サイズや暗号文サイズは暗号系サイズの数倍（方式により異なる）となる。例えば、公開鍵サイズは、暗号系サイズと鍵の個数との積になる。また、暗号文サイズは、暗号系サイズと、１つのメッセージを暗号化するのに必要な暗号文の数との積になる。したがって、メモリ容量や通信帯域が十分でない機器にとっては暗号系サイズの増大が問題となる。
【０００４】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する暗号圧縮技術が提案されている（例えば、非特許文献１）。この暗号圧縮技術は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を小さいビット数で表現できるという事実に基づいている。また、圧縮率、すなわち圧縮前のビット数の圧縮後のビット数に対する割合を増大するための改良技術として、集合の要素を小さいビット数の表現に変換する際に付加的な入力を用いる技術が知られている（例えば、非特許文献２）。
【０００５】
ここで、小さいビット数の表現へ変換する写像をρ、θと書き、ρ、θをそれぞれＲＳ（Ｒｕｂｉｎ  Ｓｉｌｖｅｒｂｅｒｇ）圧縮写像、ＤＷ（Ｄｉｊｋ  Ｗｏｏｄｒｕｆｆ）圧縮写像と呼ぶことにする。以下に、各圧縮者像で暗号文を圧縮する場合の具体例を示す。
【０００６】
ＲＳ圧縮写像では、暗号文ｃを入力として（１）式により計算を行い、圧縮暗号文γを得る。
ρ（c）＝γ・・・（１）
【０００７】
ＤＷ圧縮写像では、暗号文ｃが入力として与えられたときに適当な補助入力ａ１を用いて（２）式により計算を行い、γと補助出力ａ２を得る。
θ（ｃ，ａ１）＝（γ，ａ２）・・・（２）
【０００８】
元のビット数の表現に戻すには、それぞれρ、θの逆写像を計算すればよい。ρ、θの逆写像をρ−１、θ−１と書き、ρ−１、θ−１をそれぞれＲＳ伸長写像、ＤＷ伸長写像と呼ぶことにする。
【０００９】
ＲＳ伸長写像では、圧縮暗号文としてγが与えられたときに（３）式により計算を行い、ｃを得る。
ρ−１（γ）＝ｃ
【００１０】
ＤＷ伸長写像では、圧縮暗号文としてγとａ２の組が与えられたときに（４）式により計算を行い、ｃとａ１を得る。
θ−１（γ，ａ２）＝（ｃ，ａ１）
【００１１】
代数的トーラスを用いた圧縮伸長は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用することができる。
【００１２】
公開鍵暗号の例として、非特許文献３では、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号が提案されている。Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は、標準モデルでの安全性が証明されている方式である。また、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は、公開鍵や暗号文の要素（成分）の数が多いという特徴を有する。なお、特許文献１では、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号のバリエーションとして、秘密鍵の個数を削減できる方式が提案されている。
【００１３】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の暗号文は、４つの成分（ｃ１，ｃ２，ｃ３，ｃ４）からなる。同様に、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号では、公開鍵も４つの成分からなる。そして、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号では、各成分が、実際に暗号に用いられる群よりも大きいデータサイズの表現で表されるという問題がある。すなわち、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は、有限群Ｇ〜の素数位数部分群Ｇ上で定義されているが、公開鍵や暗号文の成分はＧ〜の表現で表されている。具体的には、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号は、素体の乗法群の素数位数部分群で定義されているが、公開鍵や暗号文の成分は素体の表現で表されている。
【００１４】
なお、体とは、四則演算が定義される数の集合であって、数の集合が有限の場合は有限体と呼ばれる。有限体に含まれる数の個数は素数であるか素数のべき乗であることが知られている。このような体は、それぞれ素体と拡大体と呼ばれる。素体や拡大体の要素の個数を決めている素数を標数と呼び、べき乗を拡大次数と呼ぶ。乗法群とは、乗算と除算が定義される数の集合であって、有限体の要素から０を除くと乗法群となることが知られている。群の要素の個数を位数と呼ぶ。
【００１５】
Ｔを拡大体上の代数的トーラスとすると、Ｔの部分群となる、より小さなトーラスが存在する。Ｇ〜を拡大体Ｆの乗法群とすると、より小さなトーラスのうち拡大体Ｆの真部分体に包含されないトーラスＴが決まり、その次数は拡大体の次数となる。ｔはＴの部分群であるので、Ｔの素数位数部分群上で暗号系を定義すると、公開鍵や暗号文はＴのサイズで表現される。圧縮伸長写像が構成できるＴの次数を定め、Ｔが定義される拡大体の次数と標数を安全性の要件から求める。
【００１６】
仮に、Ｇが拡大体の真部分体Ｆ’に包含されるとき、Ｇの安全性を決めるのはＦ’のサイズである。すなわち、そのサイズの差だけ安全性が下がる。Ｆ＝Ｆ’のとき、すなわち、ＧがＴの部分群のとき、元のＦの安全性を下げることなくＴの素数位数部分群Ｇ上で暗号系が定義される。一方、Ｆ＞Ｆ’であっても、Ｆ’を十分大きなサイズとすれば、代数的トーラスＴの最大の圧縮率（＝Ｆのサイズ／Ｔのサイズ）よりは小さいが、十分大きな圧縮率（＝Ｆ’のサイズ／Ｔのサイズ）で圧縮される。
【００１７】
【非特許文献１】Ｋ．Ｒｕｂｉｎ  ａｎｄ  Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＲＹＰＴＯ  ２００３，Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ２７２９，３４９−３６５，２００３．
【非特許文献２】Ｍ．ｖａｎ  Ｄｉｊｋ  ａｎｄ  Ｄ．Ｗｏｏｄｒｕｆｆ．“Ａｓｙｍｐｔｏｔｉｃａｌｌｙ  Ｏｐｔｉｍａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｆｏｒ  Ｔｏｒｕｓ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”  ＣＲＹＰＴＯ  ２００４，Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ３１５２，１５７−１７８，２００４．
【非特許文献３】Ｒ．  Ｃｒａｍｅｒ  ａｎｄ  Ｖ．  Ｓｈｏｕｐ．"Ａ  ｐｒａｃｔｉｃａｌ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ａｇａｉｎｓｔ  ａｄａｐｔｉｖｅ  ｃｈｏｓｅｎ  ｃｉｐｈｅｒｔｅｘｔ  ａｔｔａｃｋ"，ＣＲＹＰＴＯ  １９９８，ＬＮＣＳ  １４６２，１３−２５，１９９８.
【特許文献１】米国特許第７，２２１，７５８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、非特許文献１および非特許文献２などのような暗号圧縮技術を用いる場合、暗号化処理／復号処理の他に、圧縮処理および伸長処理が必要となるため、暗号圧縮技術を用いない場合と比較して一般に計算コストが増加するという問題があった。
【００１９】
本発明は、上記に鑑みてなされたものであって、暗号圧縮技術を用いた暗号方式による演算処理のコストを低減することができる装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
上述した課題を解決し、目的を達成するために、本発明は、乗法群の部分群上の離散対数問題に基づく暗号方式により平文データを暗号化する暗号化装置であって、前記平文データと、少なくとも一部の成分が前記部分群上の元であってアフィン表現で表された暗号鍵データと、を入力する入力部と、入力された前記暗号鍵データの少なくとも一部を射影表現に変換する第１変換部と、射影表現に変換された前記暗号鍵データを用いて、前記平文データに対して前記暗号方式で予め定められた暗号化処理を実行することにより、射影表現で表された暗号文データを算出する暗号文算出部と、射影表現で表された前記暗号文データの少なくとも一部をアフィン表現に変換する第２変換部と、を備えたことを特徴とする。
【００２１】
また、本発明は、上記暗号化装置を実行することができる方法およびプログラムである。
【００２２】
また、本発明は、乗法群の部分群上の離散対数問題に基づく暗号方式により暗号化された暗号文データを復号する復号装置であって、前記部分群上の元であってアフィン表現で表された成分を少なくとも含む前記暗号文データを入力する入力部と、前記暗号文データを射影表現で表された射影表現データに変換する変換部と、前記射影表現データに対して前記暗号方式で予め定められた復号処理を実行することにより、射影表現で表された復号済み平文データを算出する平文算出部と、を備えたことを特徴とする。
【００２３】
また、本発明は、上記復号装置を実行することができる方法およびプログラムである。
【発明の効果】
【００２４】
本発明によれば、暗号圧縮技術を用いた暗号方式による演算処理のコストを低減することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２５】
以下に添付図面を参照して、この発明にかかる装置、方法およびプログラムの最良な実施の形態を詳細に説明する。
【００２６】
（第１の実施の形態）
非特許文献１などのように代数的トーラスを用いた暗号圧縮技術では、アフィン表現に圧縮された暗号文を、射影表現を介して拡大体表現に伸長（変換）している。すなわち、アフィン表現と拡大体表現との間で表現形式を変換する場合、射影表現を経る必要がある。なお、アフィン表現と射影表現との間の変換処理のコストと比較して、拡大体表現と射影表現との間の変換処理のコストが大きい。このため、コストが大きい拡大体表現と射影表現との間の変換処理をできるだけ少なくすれば、暗号化・復号に関する演算処理のコストを低減することが可能となる。
【００２７】
そこで、第１の実施の形態にかかる暗号処理システムは、代数的トーラスを用いた暗号圧縮技術によって拡大体表現からアフィン表現に圧縮された暗号文データを、拡大体表現ではなく射影表現に変換して、べき乗計算や乗算を実行する。
【００２８】
具体的には、第１の実施の形態では、以下のような概念を利用して、暗号化・復号に関する演算処理のコスト低減を実現する。
（１）暗号文の圧縮を伴わない場合、公開鍵暗号方式の暗号化処理および復号処理では拡大体表現で演算を行う。
（２）射影表現でも暗号化処理および復号処理での演算を実行できる。しかし、計算コストがかかるため、拡大体表現を射影表現へ変換してから演算することは通常行われない。
（３）代数的トーラスを用いた圧縮を行う場合、拡大体表現からアフィン表現への変換を行う。
（４）アフィン表現から射影表現への変換は低コストで行うことができる。
（５）拡大体表現および射影表現での演算コストはほぼ同じである。
【００２９】
すなわち、主に上記（４）の概念に基づき、アフィン表現のデータを、拡大体表現ではなく射影表現に変換して演算を実行することで、高コストの変換処理を削減し、全体の演算処理のコストを低減する。
【００３０】
図１は、第１の実施の形態にかかる暗号処理システムのブロック図である。図１に示すように、第１の実施の形態にかかる暗号処理システムは、パラメータ生成装置１０と、鍵生成装置２０と、送信装置３０と、受信装置４０とを含んでいる。
【００３１】
パラメータ生成装置１０は、公開鍵暗号に関する公開情報を生成する。公開情報としては、群の要素やハッシュ関数などの情報や、暗号系が定義される群に関する情報として、位数や生成元の情報が含まれる。
【００３２】
鍵生成装置２０は、パラメータ生成装置１０によって生成された公開情報を用いて、公開鍵と、公開鍵に対応する秘密鍵とを生成する。
【００３３】
暗号化装置３００を有する送信装置３０には、鍵生成装置２０が生成した公開鍵と、暗号化の対象の平文データとが入力される。この平文データは、送信装置３０に予め記憶されたものであっても、送信装置３０が生成したものであっても、他の通信装置から受信したものであっても、記憶媒体から読み出したものであってもよい。
【００３４】
暗号化装置３００は、公開鍵を用いて平文データを暗号化して暗号文を生成し、生成した暗号文を受信装置４０に送信する。暗号化装置３００の構成の詳細については後述する。
【００３５】
復号装置４００を有する受信装置４０は、暗号文を受信すると、当該暗号文の暗号化に用いられた公開鍵に対応する秘密鍵を用いて暗号文を復号することにより、平文データを得る。
【００３６】
なお、送信装置３０および受信装置４０は、例えば、図示しないインターネットなどのネットワークを介して相互に接続されたＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）等によって構成することができる。また、送信装置３０は、鍵生成装置２０からの公開鍵の受信、受信装置４０に対する暗号文の送信等を実行する送受信部（図示せず）などを備えている。同様に、受信装置４０は、鍵生成装置２０からの秘密鍵を受信、送信装置３０からの暗号文の受信等を実行する送受信部（図示せず）などを備えている。
【００３７】
なお、暗号化装置３００および復号装置４００は、暗号方式として、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いる。適用可能な暗号方式はこれに限られず、ＥｌＧａｍａｌ暗号などの有限体上の離散対数問題に基づく暗号方式であればあらゆる方式を適用できる。
【００３８】
また、本実施の形態では、暗号化装置３００および復号装置４００が、それぞれ送信装置３０および受信装置４０に含まれる構成を例に説明するが、装置構成はこれに限られるものではない。例えば、送信装置３０および受信装置４０以外の装置に暗号化装置３００および復号装置４００が含まれるように構成してもよい。また、暗号化装置３００および復号装置４００を同一の装置上に含むように構成してもよい。
【００３９】
ここで、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。図２で、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ〜，ｅ，ｆ，ｈは群Ｇの元である。平文データｍもＧの元である。ｒはランダムに生成される乱数である。
【００４０】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文データｍに対応する暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値ｖ
を求めている。秘密鍵は１からｑまでの整数（または０からｑ−１までの整数）とする。
【００４１】
復号処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）と暗号文データ（ｃ１，ｃ２，ｃ３，ｃ４）から正当な平文データであるか否かのチェックを行い、平文データｍを計算する。ここで、秘密鍵（ｘ１，ｘ２，ｙ１，ｙ２，ｚ１，ｚ２）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ〜）は、ｃが群Ｇ（または群Ｇ〜）に属するか否かを判断することを示している。
【００４２】
次に、暗号化装置３００の構成の詳細について説明する。図３は、第１の実施の形態にかかる暗号化装置３００のブロック図である。図３に示すように、暗号化装置３００は、入力部３０１と、記憶部３２１と、暗号化処理部３１０と、を備えている。
【００４３】
入力部３０１は、平文データや、暗号化に用いる公開鍵暗号方式の暗号鍵データ（以下、公開鍵データという）などを入力する。記憶部３２１は、入力された平文データや公開鍵データなどを保存する。
【００４４】
暗号化処理部３１０は、平文データの暗号化処理を実行するものであり、変換部３１１と、暗号文算出部３１２とを含んでいる。
【００４５】
変換部３１１は、暗号化処理で扱う各種データの表現形式を相互に変換する。例えば、変換部３１１は、平文データを暗号化して得られる、拡大体表現で表された暗号文データをアフィン表現に変換する。
【００４６】
暗号文算出部３１２は、平文データに対して公開鍵データを用いて、有限体上の離散対数問題に基づいた暗号化処理を施して暗号文データを算出する。具体的には、暗号文算出部３１２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて平文データに暗号化処理を施して暗号文データを出力する。なお、上述のように、暗号文算出部３１２がＥｌＧａｍａｌ暗号などの他の暗号方式を利用するように構成してもよい。
【００４７】
次に、復号装置４００の構成の詳細について説明する。図４は、第１の実施の形態にかかる復号装置４００のブロック図である。図４に示すように、復号装置４００は、入力部４０１と、記憶部４２１と、復号処理部４１０と、を備えている。
【００４８】
入力部４０１は、暗号化装置３００によりアフィン表現に圧縮された暗号文データや、復号に用いる公開鍵暗号方式の秘密鍵データなどを入力する。記憶部４２１は、入力された暗号文データや秘密鍵データなどを保存する。
【００４９】
復号処理部４１０は、暗号文データの復号処理を実行するものであり、変換部４１１と、平文算出部４１２と、判定部４１３と、を含んでいる。
【００５０】
変換部４１１は、復号処理で扱う各種データの表現形式を相互に変換する。例えば、変換部４１１は、アフィン表現に圧縮された暗号文データを射影表現に変換する。また、変換部４１１は、射影表現で復号された平文データを拡大体表現に変換する。なお、以下では、射影表現で表された暗号文データを射影表現データという場合がある。
【００５１】
平文算出部４１２は、暗号文データに対して秘密鍵データを用いて、有限体上の離散対数問題に基づいた復号処理を施して平文データを算出する。具体的には、平文算出部４１２は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて暗号文データに復号処理を施して平文データを出力する。なお、上述のように、平文算出部４１２がＥｌＧａｍａｌ暗号などの他の暗号方式を利用するように構成してもよい。
【００５２】
判定部４１３は、暗号文データの正当性を判定する。例えば、判定部４１３は、暗号文データの各要素が正しい群の元であるか否かを判定する。また、判定部４１３は、入力された暗号文データのハッシュ値を算出し、算出したハッシュ値を用いて算出した値と、入力された暗号文データの所定の成分とを比較し、両者が一致しているか否かによって、暗号文データが正当であることを判定する。
【００５３】
なお、記憶部３２１および記憶部４２１は、ＨＤＤ（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）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【０１４２】
さらに、第１〜第４の実施の形態にかかる復号装置で実行される復号プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１〜第４の実施の形態にかかる復号装置で実行される復号プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１４３】
第１〜第４の実施の形態にかかる復号装置で実行される復号プログラムは、上述した各部（入力部、復号処理部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵがＲＯＭから復号プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、各部が主記憶装置上に生成されるようになっている。
【産業上の利用可能性】
【０１４４】
以上のように、本発明にかかる装置、方法およびプログラムは、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式のように、離散対数問題を安全性の根拠とする公開鍵暗号方式によりデータを暗号化または復号する装置に適している。
【図面の簡単な説明】
【０１４５】
【図１】第１の実施の形態にかかる暗号処理システムのブロック図である。
【図２】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号の処理手順を示す説明図である。
【図３】第１の実施の形態にかかる暗号化装置のブロック図である。
【図４】第１の実施の形態にかかる復号装置のブロック図である。
【図５】第１の実施の形態における鍵生成処理の概要を示す図である。
【図６】第１の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図７】第１の実施の形態における復号処理の全体の流れを示すフローチャートである。
【図８】第２の実施の形態にかかる暗号処理システムのブロック図である。
【図９】第２の実施の形態における鍵生成処理の概要を示す図である。
【図１０】第２の実施の形態にかかる暗号化装置の構成を示すブロック図である。
【図１１】第２の実施の形態にかかる復号装置の構成を示すブロック図である。
【図１２】第２の実施の形態における暗号化処理の全体の流れを示すフローチャートである。
【図１３】第２の実施の形態における復号処理の全体の流れを示すフローチャートである。
【図１４】第３の実施の形態にかかる暗号処理システムのブロック図である。
【図１５】第３の実施の形態における鍵生成処理の概要を示す図である。
【図１６】第３の実施の形態にかかる復号装置の構成を示すブロック図である。
【図１７】第３の実施の形態における復号処理の全体の流れを示すフローチャートである。
【図１８】第４の実施の形態にかかる暗号処理システムのブロック図である。
【図１９】第４の実施の形態における鍵生成処理の概要を示す図である。
【図２０】第４の実施の形態にかかる復号装置の構成を示すブロック図である。
【図２１】第４の実施の形態における復号処理の全体の流れを示すフローチャートである。
【符号の説明】
【０１４６】
１０  パラメータ生成装置
２０、８２０、１４２０、１８２０  鍵生成装置
３０、８３０  送信装置
４０、８４０、１４４０、１８４０  受信装置
３００、９００  暗号化装置
３０１  入力部
３１０、９１０  暗号化処理部
３１１、９１１  変換部
３１２、９１２  暗号文算出部
３２１  記憶部
４００、１０００、１６００、２０００  復号装置
４０１  入力部
４１０、１０１０、１６１０、２０１０  復号処理部
４１１、１０１１  変換部
４１２、１６１２、２０１２  平文算出部
４１３、２０１３  判定部
４２１  記憶部
【図１】
2010049212.tif 000003
【図２】
2010049212.tif 000004
【図３】
2010049212.tif 000005
【図４】
2010049212.tif 000006
【図５】
2010049212.tif 000007
【図６】
2010049212.tif 000008
【図７】
2010049212.tif 000009
【図８】
2010049212.tif 000010
【図９】
2010049212.tif 000011
【図１０】
2010049212.tif 000012
【図１１】
2010049212.tif 000013
【図１２】
2010049212.tif 000014
【図１３】
2010049212.tif 000015
【図１４】
2010049212.tif 000016
【図１５】
2010049212.tif 000017
【図１６】
2010049212.tif 000018
【図１７】
2010049212.tif 000019
【図１８】
2010049212.tif 000020
【図１９】
2010049212.tif 000021
【図２０】
2010049212.tif 000022
【図２１】
2010049212.tif 000023