暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラム
【課題】乗法群の部分群上の離散対数問題に安全性の根拠を置く公開鍵暗号方式において、処理時間の増大を抑制しつつ、データのサイズを低減可能な暗号化技術を提供する。
【解決手段】暗号化装置は、暗号文(c1,c2)の各暗号文成分のうち一部の暗号文成分を圧縮すると同時に別の暗号文成分を生成する。一方、復号装置は、暗号文(c1,c2)の各暗号文成分のうち圧縮された暗号文成分を伸張すると同時に、圧縮されていない暗号文成分あるいは伸張済み暗号文成分と秘密鍵とを用いてべき乗算や乗算などの各種演算を行うことにより、平文を得る。
【解決手段】暗号化装置は、暗号文(c1,c2)の各暗号文成分のうち一部の暗号文成分を圧縮すると同時に別の暗号文成分を生成する。一方、復号装置は、暗号文(c1,c2)の各暗号文成分のうち圧縮された暗号文成分を伸張すると同時に、圧縮されていない暗号文成分あるいは伸張済み暗号文成分と秘密鍵とを用いてべき乗算や乗算などの各種演算を行うことにより、平文を得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式にかかる暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムに関する。
【背景技術】
【０００２】
通信路を流れる情報を保護するために、暗号を用いる方法がある。暗号を用いる方法には、通信相手と事前に鍵を共有しておく必要があるものもある。このような方法では、鍵の共有や管理に大きな手間がかかる。一方、公開鍵暗号を用いる方法では、事前に鍵を共有することなしに安全な通信を実現できる。このため、ネットワーク・セキュリティの基盤技術として幅広く用いられている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキームやプロトコルが用いられるようになってきた。
【０００３】
公開鍵暗号の暗号方式にはＥｌＧａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号のように離散対数問題の困難性を安全性の根拠とするものがある。離散対数問題とは、巡回群‘Ｇ＝＜ｇ＞’において‘ｙ∈Ｇ’が与えられたときに、‘ｙ＝ｇ＾ｘ’を満たすｘを求める問題である。尚、‘^’はべき乗を表す。巡回群Ｇとしては、有限体の乗法群や楕円曲線の有理点のなす加法群（ヤコビ群）が用いられる。離散対数問題を解くアルゴリズムには、シャンクのアルゴリズムやポラードのρ法のようにいずれの巡回群上で定義された離散対数問題に対しても適用可能なものと、位数計算法にように有限体の乗法群上で定義された離散対数問題のみに適用可能なものとが存在する。
【０００４】
位数計算法は効率的であるため、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は解読されやすい。したがって、同じ安全性を確保するために、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は、楕円曲線上の離散対数問題を用いた公開鍵暗号よりも鍵長や暗号文長を大きくする必要がある。
【０００５】
現在、公開鍵暗号において典型的なセキュリティパラメータは１０２４ビット〜２０４８ビットである。セキュリティパラメータとは、公開鍵サイズや暗号文サイズを決定するパラメータであり、暗号方式の安全性に影響を与えるパラメータである。このセキュリティパラメータが大きくなれば、公開鍵サイズや暗号文サイズも大きくなる。解読が困難とされるセキュリティパラメータは年々大きくなっている。これは、計算機の進歩に伴い攻撃者の能力も向上するためである。公開鍵暗号では公開鍵サイズや暗号文サイズは、暗号方式により異なるが、セキュリティパラメータの数倍となる。
【０００６】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する方法が提案されている（例えば、非特許文献１参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の成分を小さいビット数で表現できるという事実に基づいている。代数的トーラスの属する拡大体の次数ｎが高々二つの素数ｐ，ｑの冪の積‘ｌ＝（ｐ＾ｍ）・（ｑ＾ｎ）’であるとき、圧縮率（＝圧縮前のビット数／圧縮後のビット数）は、‘ｌ/φ(ｌ)’となることが知られている。ただし、φ（・）はオイラー関数である。ｐ＾ｍは、pのｍ乗である。小さいビット数の表現への変換は、拡大体表現を射影表現に変換する写像ρと射影表現をアフィン表現に変換する写像τによって行われる。暗号文を圧縮する場合の具体例を示す。拡大体表現の暗号文ｃを入力として計算を行い、圧縮暗号文γを得る（式１参照）。
【０００７】
ρ(c)=γ・・・（式１）
【０００８】
元のビット数の表現に戻すには、それぞれρ、τの逆写像を計算すればよい。ρの逆写像をψと書き、τの逆写像をτ−1と書くことにする。圧縮暗号文としてγが与えられたときに計算を行い、cを得る（式２参照）。
【０００９】
ψτ―1(γ)= c・・・（式２）
【００１０】
また、非特許文献１、２では、前記圧縮写像１、２と前記伸張写像１，２の構成法と、それらを用いて次のような拡大体表現をアフィン表現に圧縮する写像ρ６、アフィン表現を拡大体表現に伸張する写像‘ρ６＾（−１）’の構成法が示されている。圧縮写像ρ６は、６次拡大体Ｆ｛（ｐ＾ｍ）＾６｝上の拡大体表現のトーラスＴの任意の元ｔを入力として計算し、アフィン表現Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊の要素との組を得る（式３参照）。
【００１１】
ρ６（ｔ）＝（ａ，ｂ）∈Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊・・・（式３）
【００１２】
尚、ここで‘×’は直積を表すものとする。また、Ａが集合であるとき、Ａ＾ｍはｍ個のＡの直積集合となる。例えば、‘Ａ＾３＝Ａ×Ａ×Ａ’となる。具体的には例えば、‘｛０，１、２｝＾２＝｛（０，０），（０，１），（０，２），（１，０），（１，１），（１，２），（２，０），（２，１），（２，２）｝’となる。ここで、Ｆ｛ｐ＾ｍ｝は、素体Ｆ｛ｐ｝のｍ次拡大体であり、 Ｆ｛ｐ＾ｍ｝の要素はベクトル表現を用いると、｛０，・・・，ｐ−１｝＾ｍの要素で表現できる。Ｆ｛ｐ＾ｍ｝＾＊は、Ｆ｛ｐ＾ｍ｝の乗法群であり、Ｆ｛ｐ＾ｍ｝＾ｍの要素はベクトル表現を用いると、｛０，・・・，ｐ−１｝＼｛０｝＾ｍの要素で表される。‘＼’は集合の引き算を表す。
６＾（−１）’は、（ａ，ｂ）∈Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊を入力として計算し、６次拡大体Ｆ｛（ｐ＾ｍ）＾６｝上の拡大体表現のトーラスＴの元ｔを得る（式４参照）。
【００１３】
ρ−１（ａ，ｂ）＝ｔ∈Ｔ・・・（式４）
【００１４】
また、非特許文献２では、Ｆ｛ｐ＾ｍ｝の６次拡大体上のトーラスの要素の拡大体表現｛０，・・・，ｐ−１｝＾｛６＾ｍ｝と射影表現｛０，・・・，ｐ−１｝＾｛６＊ｍ｝とアフィン表現Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊に対して、上記のρ、ψ、τ、τ−１の構成法を示し、それを元に（式３）と（式４）との写像を構成している。このとき、拡大体表現と射影表現とに対する演算は、共にＦ｛ｐ＾（６＊ｍ）｝の演算で、非特許文献１、２ではＦ｛ｐ＾（６＊ｍ）｝の演算をＦ｛（（ｐ＾ｍ）＾３）＾２｝の演算として実現している。アフィン表現の要素は拡大体表現や射影表現よりも短いビット長で表現できる反面、演算することができない。
【００１５】
代数的トーラスを用いた圧縮や伸張は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用できる。
【００１６】
近年では、離散対数問題の困難性に基づく様々な公開鍵暗号の暗号方式が提案されている。例えば、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号（非特許文献３参照）は、標準モデルでの安全性が証明されている方式であるが、公開鍵や暗号文の成分の数が多いという特徴がある。具体的には、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号の暗号文は４つの成分（ｃ１， ｃ２, ｃ３, ｃ４）からなり、公開鍵も５つの成分（ｇ，ｇ~，ｅ，ｆ，ｈ）が含まれる。しかも、各成分は実際に暗号に用いられる群よりも大きな表現で表されるという問題がある。つまり、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号は有限群Ｇ~の素数位数部分群Ｇ上で定義されているが、公開鍵や暗号文の成分は有限群Ｇ~の表現で表されている。具体的には、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号は素体の乗法群の素数位数部分群で定義されているが、公開鍵や暗号文の成分は素体の表現で表されている。
【００１７】
Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号やその他の公開鍵暗号において、有限群Ｇ~の部分群であって実際に暗号に用いられる群Ｇを代数的トーラスＴの部分群とすることにより、公開鍵や暗号文を有限群Ｇ~のサイズではなく代数的トーラスＴのサイズ、すなわち群Ｇ~よりも小さなビット数で表現が可能となる。例えば、素体上の代数的トーラスを用いたＥｌＧａｍａｌ暗号やＤＨ鍵交換（非特許文献１、４参照）はこの概念を利用し、公開鍵や暗号文のサイズを小さくしたものである。
【００１８】
ここで、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号の処理の概要を説明する。平文ｍを暗号化する暗号化装置には、鍵生成装置で生成された公開鍵(ｑ,ｇ,ｇ~,ｅ,ｆ,ｈ)が入力される。尚、ｑは素数で有限群Ｇ~の部分群Ｇの位数、ｇは暗号が定義される部分群Ｇの生成元、ｇ~,ｅ,ｆ,ｈも部分群Ｇの元とする。平文ｍもＧの元でなければならない。暗号化装置は、乱数の生成、べき乗計算、乗算、ハッシュ計算を行い、平文ｍに対応する暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を計算する。この暗号文(ｃ１, ｃ２, ｃ３, ｃ４)は、復号装置に入力される。また、復号装置には、公開鍵に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)が入力される。この秘密鍵は‘１’から‘ｑ−１’までの整数(又は‘０’から‘ｑ-１’までの整数)とする。復号装置は、秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)と暗号文(ｃ１, ｃ２, ｃ３, ｃ４)とを用いて、正当な暗号文であるかのチェックを行い、平文ｍを計算する。
【００１９】
【非特許文献１】K. Rubin and A. Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003.
【非特許文献２】Robert Granger, Dan Page, Martijn Stam: A Comparison of CEILIDH and XTR. ANTS 2004: 235-249
【非特許文献３】R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertextattack”, CRYPTO'98, LNCS 1462, pp.13-25, 1998.
【非特許文献４】M. van Dijkand D. Woodruff, “Asymptotically Optimal Communication for Torus-Based Cryptography”, CRYPTO 2004, LNCS 3152, 157-178, 2004.
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、例えばＣｒａｍｅｒ-Ｓｈｏｕｐ暗号のような乗法群の部分群上の離散対数問題を安全性の根拠とする公開鍵暗号の暗号方式において、暗号化や復号と圧縮や伸張とを行うことを考えた場合、通常、暗号化装置で暗号化して圧縮した後データを送信し、復号装置で受信したデータを伸張して復号するという手順で処理を行う。暗号化装置でこのような圧縮を行う場合、これを行わない場合と比べ、送信するデータのサイズを小さくすることができるため、通信コストが下がるものの、処理時間が増大する。復号装置で伸張を行う場合も、これを行わない場合に比べ、処理時間が増大する。
【００２１】
本発明は、上記に鑑みてなされたものであって、乗法群の部分群上の離散対数問題に安全性の根拠を置く暗号方式において、処理時間の増大を抑制しつつ、データのサイズを低減可能な暗号化装置、復号装置、暗号化方法、復号方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
上述した課題を解決し、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、平文を受信する平文受信部と、１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成部と、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る暗号文成分圧縮部と、受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力部とを備えることを特徴とする。
【００２３】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成部と、前記復号済みの平文を出力する復号済み平文出力部とを備えることを特徴とする。
【００２４】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が正当ではない旨を出力する復号済み平文出力部とを備えることを特徴とする。
【００２５】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文正当性検証装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、前記圧縮暗号文成分の表現を演算可能な表現である伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて前記暗号文の正当性を検証する正当性検証部と、前記正当性検証部の検証結果を出力する検証結果出力部とを備えることを特徴とする。
【００２６】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文検証装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、前記正当性検証部の検証結果を出力する検証結果出力部とを備えることを特徴とする。
【００２７】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置で実行される暗号化方法であって、平文を受信する平文受信ステップと、１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信ステップと、受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成ステップと、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮ステップと、受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成ステップと、少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力ステップとを含むことを特徴とする。
【００２８】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置で実行される復号方法であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信ステップと、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信ステップと、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成ステップと、前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張ステップと、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成ステップと、復号済みの前記平文を出力する復号済み平文出力ステップとを含むことを特徴とする。
【００２９】
また、本発明は、プログラムであって、上記の方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００３０】
本発明によれば、乗法群の部分群上の離散対数問題に安全性の根拠を置く暗号方式において、処理時間の増大を抑制しつつ、データのサイズを低減可能になる。
【発明を実施するための最良の形態】
【００３１】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの最良な実施の形態を詳細に説明する。
【００３２】
[第１の実施の形態]
（１）構成
＜一般的暗号方式の構成＞
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式で複数の暗号文成分を含む暗号文の正当性を検証する基本的な構成について図１を用いて説明する。まず、公開鍵に含まれる公開鍵成分ｐｋ及び当該公開鍵成分に対応する秘密鍵に含まれる秘密鍵成分ｓｋが図示しない鍵生成装置で生成される。公開鍵成分ｐｋが暗号化装置で受信され、当該公開鍵成分ｐｋに対応する秘密鍵成分ｓｋが暗号文検証装置で受信される。暗号化装置は公開鍵成分ｐｋを用いて平文ｍに対応する暗号文（ｃ１、ｃ２）を計算してこれを出力する。一方、暗号文検証装置２０は暗号文（ｃ１，ｃ２）を受信すると、これと秘密鍵成分ｓｋを用いて暗号文（ｃ１，ｃ２）が正当なものであるか否かを検証する。なお、公開鍵成分ｐｋおよび平文ｍが圧縮された表現、即ち、アフィン表現（ｐｋ＊，ｍ＊）となっている場合、暗号化装置１０への入力以前に拡大体表現や射影表現に伸張（変換）するものとする。
【００３３】
次に、本実施の形態にかかる暗号化装置及び暗号文検証装置の構成について説明する。暗号化装置及び暗号文検証装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００３４】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施の形態に特有の各種機能について説明する。図２は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１０は、平文受信部１１と、公開鍵受信部１２と、第１暗号文生成部１３と、暗号文成分圧縮部１４と、第２暗号文生成部１５と、暗号文出力部１６とを有する。これらの各部の実体は、暗号化装置１０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００３５】
平文受信部１１は、平文ｍを受信する。公開鍵受信部１２は、公開鍵成分ｐｋを受信する。第１暗号文生成部１３は、平文受信部１１が受信した平文ｍと公開鍵受信部１２が受信した公開鍵成分ｐｋとを用いて、暗号文成分ｃ１を生成する。暗号文成分圧縮部１４は、第１暗号文生成部１３が生成した暗号文成分ｃ１をアフィン表現に変換して圧縮暗号文成分ｃ１＊を生成する。即ち、本実施の形態において暗号化装置１０は、複数の暗号文成分のうち、暗号文成分ｃ１を圧縮する。同時に第２暗号文生成部１５は、第１暗号文生成部１３が生成した暗号文成分ｃ１と公開鍵受信部１２が受信した公開鍵成分ｐｋとを用いて暗号文成分ｃ２を生成する。暗号文出力部１６は、暗号文成分圧縮部１４が生成した圧縮暗号文成分ｃ１＊と第２暗号文生成部１５が生成した暗号文成分ｃ２とを出力する。
【００３６】
＜暗号文検証装置の構成＞
次に、本実施の形態にかかる暗号文検証装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図３は、本実施の形態にかかる暗号文検証装置の機能的構成を例示する図である。暗号文検証装置２０は、暗号文受信部２１と、秘密鍵受信部２２と、中間データ生成部２３と、暗号文成分伸張部２４と、正当性検証部２５と、検証結果出力部２６とを有する。これらの各部は、暗号文検証装置２０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００３７】
暗号文受信部２１は、暗号文（ｃ１＊，ｃ２）を受信する。秘密鍵受信部２２は、秘密鍵成分ｓｋを受信する。中間データ生成部２３は、暗号文受信部２１が受信した暗号文成分ｃ２と秘密鍵受信部２２が受信した秘密鍵成分ｓｋとを用いて、暗号文の復号に用いる中間データｋを生成する。中間データ生成部２３が中間データｋを生成すると同時に、暗号文成分伸張部２４は、暗号文受信部２１が受信した圧縮暗号文成分ｃ１＊を拡大体表現である暗号文成分ｃ１へと伸張（変換）する。正当性検証部２５は、中間データ生成部２３が生成した中間データｋと暗号文成分伸張部２４が伸張した暗号文成分ｃ１とを用いて暗号文の正当性を検証する。検証結果出力部２６は正当性検証部２５の検証結果を出力する。
【００３８】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１０の行う暗号化処理の手順について図４を用いて説明する。暗号化装置１０は、公開鍵である公開鍵成分ｐｋと平文ｍとを受信し、公開鍵成分ｐｋと平文ｍとを用いて計算を行って、暗号文成分ｃ１を生成する（ステップＳＴ１）。次に暗号化装置１０は、ｃ１の表現をアフィン表現へと圧縮（変換）する（ステップＳＴ２）。続いて、ステップＳＴ１で求めた暗号文成分ｃ１と公開鍵成分ｐｋとを用いて計算を行って、暗号文成分ｃ２を生成する（ステップＳＴ３）。
【００３９】
＜暗号文検証処理＞
次に、本実施の形態にかかる暗号文検証装置２０の行う暗号文検証処理の手順について図５を用いて説明する。暗号文検証装置２０は、暗号文（ｃ１＊，ｃ２）と秘密鍵に含まれる秘密鍵成分ｓｋとを受信し、暗号文成分ｃ２と秘密鍵成分ｓｋとを用いて中間データｋを生成する（ステップＳＴ１１）。次に、暗号文検証装置２０は、アフィン表現となっている圧縮暗号文成分ｃ１＊を拡大体表現である暗号文成分ｃ１に伸張（変換）する（ステップＳＴ１２）。次に、暗号文検証装置２０は、暗号文成分ｃ１と中間データｋとを比較し、暗号文の正当性を検証する（ステップＳＴ１３）。
【００４０】
暗号文成分の生成に依存関係があり暗号文成分ｃ１を用いて暗号文成分ｃ２を生成する場合には、暗号文成分ｃ２をアフィン表現へと圧縮すると、暗号文成分ｃ２を圧縮する処理の分だけ暗号文成分ｃ２を圧縮しない場合と比べ、処理時間が必要となる。暗号文成分圧縮部１４と第２暗号文生成部１５とが並列に動作可能であれば、第１暗号文生成部１３が暗号文成分ｃ１を生成した後、第２暗号文生成部１５がｃ２を生成している間に暗号文成分圧縮部１４が暗号文成分ｃ１をアフィン表現に圧縮し、（ｃ１＊，ｃ２）を暗号文とすれば、圧縮にかかる処理時間を隠蔽した上で、暗号文の一部を圧縮できる。
【００４１】
一方、暗号文検証装置２０で暗号文成分ｃ２を用いて中間データｋを生成し、暗号文成分ｃ１と比較する場合、暗号文成分ｃ２がアフィン表現でなければ暗号文を受信した直後に中間データｋを生成する処理を行うことができる。暗号文成分ｃ２がアフィン表現であった場合にはアフィン表現では演算が行えないので、拡大体表現か射影表現への変換が必要になり（本実施の形態では拡大体表現に変換）、その分の処理時間が余計に必要になる。しかし、本実施の形態によれば、中間データｋの生成に用いる成分を伸張する必要がないため、圧縮された成分の伸張にかかる処理時間を隠蔽することができる。
【００４２】
尚、暗号文検証装置２０に上述の実施の形態にかかる構成を適用したが、暗号文を復号する復号装置に適用しても良い。この場合、復号装置は、上述した暗号文受信部２１と、秘密鍵受信部２２と、中間データ生成部２３と、暗号文成分伸張部２４とに加え、復号済み平文生成部と、復号済み平文出力部とを有するように構成すれば良い。復号済み平文生成部は、中間データ生成部２３が生成した中間データと暗号文成分伸張部２４が伸張した暗号文成分ｃ１とを用いて復号済みの平文を生成する。復号済み平文出力部は、復号済み平文生成部が生成した復号済みの平文を出力する。このような復号装置や上述の暗号文検証装置によれば、処理時間の増加を抑えながら、暗号文の圧縮や伸張が行えるため、処理時間を短縮したい場合に用いて好適である。
【００４３】
ここでは暗号化にかかる処理時間及び暗号文の正当性の検証にかかる処理時間の両方を変えることなく暗号文成分を圧縮する例を示したが、暗号化にかかる処理時間、暗号文の正当性の検証にかかる処理時間及び復号にかかる処理時間のいずれか一つのみに処理時間の短縮の効果をもたらすように構成することも可能である。また本実施の形態では、演算可能な表現として拡大体表現を採ったが、射影表現で演算しても上述した効果は変わらない。
【００４４】
[第２の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００４５】
（１）構成
＜ＥｌＧａｍａｌ暗号＞
復号処理を高速化する具体的な例としてＥｌＧａｍａｌ暗号を取り上げる。図６は、ＥｌＧａｍａｌ暗号において平文ｍを暗号化して暗号文を生成する暗号化装置と暗号文を復号する復号装置とを例示する図である。尚、図示しない鍵生成装置は、生成元ｇを選択し、ｘをランダムに選択して、‘ｈ＝ｇ＾ｘ’を計算し、（ｑ,ｇ,ｈ）を公開鍵とし、ｘを秘密鍵とする。尚、ｑは素数で群Ｇ~の部分群Ｇの位数とし、ｇ，ｈは暗号が定義される部分群Ｇ（位数はｑ）の生成元とする。平文ｍも部分群Ｇの元でなければならない。暗号化装置には、鍵生成装置で生成された公開鍵(ｑ,ｇ,ｈ)と平文ｍとが入力される。暗号化装置は、乱数ｒを生成し、べき乗計算及び乗算を行って、平文ｍに対応する暗号文(ｃ１, ｃ２)を出力する。この暗号文(ｃ１, ｃ２)は、復号装置に入力される。また、復号装置には、公開鍵に対応する秘密鍵成分ｘが秘密鍵として入力される。この秘密鍵成分ｘは‘１’から‘ｑ’までの整数(又は‘０’から‘ｑ-１’までの整数)とする。復号装置は、秘密鍵成分ｘと暗号文(ｃ１, ｃ２)とを用いて、復号済みの平文ｍを得る。
【００４６】
次に、本実施の形態にかかる暗号化装置及び復号装置の構成について説明する。暗号化装置及び復号装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００４７】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施に特有の各種機能について説明する。図７は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１０´は、第１の実施の形態と同様に、平文受信部１１と、公開鍵受信部１２と、第１暗号文生成部１３と、暗号文成分圧縮部１４と、第２暗号文生成部１５と、暗号文出力部１６とを有する。これらの各部の実体は、暗号化装置１０´のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００４８】
平文受信部１１は、平文ｍを受信する。公開鍵受信部１２は、公開鍵（ｑ，ｇ，ｈ）を受信する。第１暗号文生成部１３は、‘０≦ｒ＜ｑ’なる乱数ｒを生成し、平文受信部１１が受信した平文ｍと公開鍵受信部１２が受信した公開鍵に含まれる公開鍵成分ｈとを用いて、‘ｃ２＝ｍ・ｈ＾ｒ’を計算して、暗号文成分ｃ２を生成する。暗号文成分圧縮部１４は、第１暗号文生成部１３が生成した暗号文成分ｃ２をアフィン表現に変換して圧縮暗号文成分ｃ２＊を生成する。即ち、本実施の形態において暗号化装置１０は、複数の暗号化成分のうち、暗号文成分ｃ２を圧縮する。同時に第２暗号文生成部１５は、第１暗号文生成部１３が生成した乱数ｒと公開鍵受信部１２が受信した公開鍵成分ｇとを用いて‘ｃ１＝ｇ＾ｒ’を計算し、暗号文成分ｃ１を生成する。暗号文出力部１６は、暗号文成分圧縮部１４が生成した圧縮暗号文成分ｃ２＊と第２暗号文生成部１５が生成した暗号文成分ｃ１とを出力する。
【００４９】
＜復号装置の構成＞
次に、本実施の形態にかかる復号装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図８は、本実施の形態にかかる復号装置の機能的構成を例示する図である。復号装置３０は、暗号文受信部３１と、秘密鍵受信部３２と、中間データ生成部３３と、暗号文成分伸張部３４と、復号済み平文生成部３５と、復号済み平文出力部３６とを有する。これらの各部は、復号装置３０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００５０】
暗号文受信部３１は、暗号文（ｃ１，ｃ２＊）を受信する。秘密鍵受信部３２は、秘密鍵成分ｘを受信する。中間データ生成部３３は、暗号文受信部３１が受信した暗号文成分ｃ１と秘密鍵受信部３２が受信した秘密鍵成分ｘとを用いて‘ｋ＝（ｃ１＾ｘ）＾（−１）’を計算して、中間データｋを生成する。中間データ生成部３３が中間データｋを生成すると同時に、暗号文成分伸張部２４は、暗号文受信部３１が受信した圧縮暗号文成分ｃ２＊を拡大体表現である暗号文成分ｃ２へと伸張（変換）する。復号済み平文生成部３５は、中間データ生成部３３が生成した中間データｋと暗号文成分伸張部３４が伸張した暗号文成分ｃ２とを用いて、‘ｍ＝ｃ２・ｋ’を計算して、復号済みの平文を生成する。復号済み平文出力部３６は、復号済み平文生成部３５が生成した復号済みの平文を出力する。
【００５１】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１０´の行う暗号化処理の手順について図９を用いて説明する。暗号化装置１０´は、公開鍵（ｑ，ｇ，ｈ）と平文ｍとを受信し、乱数ｒを生成する（ステップＳＴ２１）。次いで、暗号化装置１０´は、乱数ｒと公開鍵成分ｈと平文ｍとを用いて暗号文成分ｃ２を生成する（ステップＳＴ２２）。次に暗号化装置１０´は、暗号文成分ｃ２の表現をアフィン表現へと変換することにより圧縮する（ステップＳＴ２３）。続いて、暗号化装置１０´は、乱数ｒと公開鍵成分ｇとを用いて暗号文成分ｃ１を生成する（ステップＳＴ２４）。
【００５２】
＜復号処理＞
次に、本実施の形態にかかる復号装置３０の行う暗号化処理の手順について図１０を用いて説明する。復号装置３０は、暗号文（ｃ１，ｃ２＊）と秘密鍵に含まれる秘密鍵成分ｘとを受信し、暗号文成分ｃ１と秘密鍵成分ｘとを用いて中間データｋを生成する（ステップＳＴ３１）。次に、復号装置３０は、アフィン表現となっている圧縮暗号文成分ｃ２＊を拡大体表現である暗号文成分ｃ２に伸張する（ステップＳＴ３２）。次に、復号装置３０は、ステップＳＴ３２で伸張した暗号文成分ｃ２とステップＳＴ３１で生成した中間データｋとを乗算し、復号済みの平文ｍを生成する（ステップＳＴ３３）。
【００５３】
以上のような構成によれば、ステップＳＴ３１で中間データｋを生成している間に、ステップＳＴ３２で圧縮暗号文成分ｃ２＊を暗号文成分ｃ２に伸張できるので、圧縮暗号文成分ｃ２＊の伸張にかかる処理時間を隠蔽しつつ、圧縮暗号文成分を伸張することが可能である。
【００５４】
[第３の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第３の実施の形態について説明する。なお、上述の第１の実施の形態又は第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５５】
（１）構成
＜Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号スキーム＞
次に、もうひとつの具体的な実施例として、上述の従来技術欄で説明したＣｒａｍｅｒ-Ｓｈｏｕｐ暗号スキームの基本的な構成について図１１を用いて説明する。まず、公開鍵及び当該公開鍵に対応する秘密鍵が鍵生成装置で生成される。公開鍵が暗号化装置に入力され、当該公開鍵に対応する秘密鍵が復号装置に入力される。公開鍵は上述の（ｑ,ｇ,ｇ~,ｅ,ｆ,ｈ）である。秘密鍵は上述の(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)である。暗号化装置は、公開鍵を用いて平文ｍに対応する暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を計算する。具体的には、暗号化装置は、公開鍵成分ｑを用いて‘０≦ｒ＜ｑ−１’なる乱数ｒを生成する。そして、暗号化装置は、乱数ｒと公開鍵成分ｇとを用いて暗号文の成分ｃ１として‘ｇ^ｒ’を求める。また、暗号化装置は、乱数ｒと公開鍵成分ｇ~とを用いて、暗号文成分ｃ２として‘ｇ~＾ｒ’を求める。また、暗号化装置は、乱数ｒと公開鍵成分ｈとを用いて係数ｂとして‘ｈ＾ｒ’を求める。そして、暗号化装置は、係数ｂと平文ｍとを用いて、暗号文成分ｃ３として‘ｂ×ｍ’を求める。次いで、暗号化装置は、各暗号文成分ｃ１, ｃ２, ｃ３についてハッシュ関数を用いた計算により、ハッシュ値‘ｖ＝Ｈ（ｃ１，ｃ２，ｃ３）’を求める。そして、暗号化装置は、乱数ｒと公開鍵成分ｅ，ｆとハッシュ値ｖとを用いて、暗号文成分ｃ４として‘ｅ^ｒ×ｆ^（ｒｖ）’を求める。この結果、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)が得られる。暗号化装置はこの暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を出力する。
【００５６】
一方、復号装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を受信すると、これと秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)とから暗号文が正当であるか否かの判定を行い、当該判定結果が肯定的である場合、平文ｍを計算する。具体的には、復号装置は、各暗号文成分ｃ１, ｃ２, ｃ３, ｃ４が群Ｇ~の元であるか否か及び各暗号文成分ｃ１，ｃ２，ｃ３が群Ｇの元であるか否かを判定する。当該判定結果が肯定的である場合、復号装置は、暗号文成分ｃ１，ｃ２と秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂとして‘ｃ１^ｚ１×ｃ２^ｚ２’を求める。また、復号装置は、暗号文成分ｃ１,ｃ２,ｃ３を用いてハッシュ関数による計算を行い、暗号文成分ｃ１,ｃ２と秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いてべき乗計算と乗算とにより検査式に用いる検証用データｋとして‘ｃ１^（ｘ１+ｙ１×ｖ）×ｃ２^（ｘ２+ｙ２×ｖ）’を求める。検証用データとは、暗号文の正当性を検証するためのものである。そして、復号装置２００は、検証用データｋと暗号文成分ｃ４とを用いた検査式‘ｃ４＝ｋ’が成立するか否かを判定する。また、復号装置２００は、暗号文成分ｃ１,ｃ２と秘密鍵成分ｚ１,ｚ２とを用いてべき乗計算を行い、当該計算結果の逆元を中間データとして導出した後、暗号文成分ｃ３を用いて乗算を行うことにより、復号済みの平文ｍを得る。
【００５７】
尚、暗号文成分ｃ３は、復号時に平文の生成に用いる平文生成用暗号文成分であり、暗号文成分ｃ１〜ｃ２は、復号時に平文の生成と暗号文の正当性の検証とに用いる総合暗号文成分であり、暗号文成分ｃ４は、復号時に暗号文の正当性の検証に用いる検証用暗号文成分である。
【００５８】
＜公開鍵及び秘密鍵生成＞
次に、鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図１２を用いて説明する。鍵生成装置は、公開鍵成分ｇを群Ｇ~の元となるよう拡大体表現あるいは射影表現から選択し、０以外の乱数ｗを生成する（ＧＳ１）。次いで、鍵生成装置は、各秘密鍵成分ｘ１,ｘ２,ｙ１,ｙ２,ｚ１,ｚ２として各々乱数を生成する（ＧＳ２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ１×ｇ~^ｘ２’を求め、公開鍵成分ｆとして‘ｇ^ｙ１×ｇ~^ｙ２’を求め、公開鍵成分ｈとして‘ｇ^ｚ１×ｇ~^ｚ２’を求める（ＧＳ３）。そして、鍵生成装置は、秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ１,ｚ２）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００５９】
尚、この例では公開鍵成分ｇ,ｇ~,ｅ,ｆ,ｈの表現をアフィン表現に変換していないが、アフィン表現に変換する、即ち、圧縮することにより、鍵長を短くすることもできる。この場合は、暗号化処理や復号処理の前に公開鍵成分の表現を拡大体表現や射影表現に変換する、即ち、伸張する必要がある。平文についてもアフィン表現を用いることが可能である。
【００６０】
以上のようなＣｒａｍｅｒ-Ｓｈｏｕｐ暗号において、本実施の形態においては、暗号化装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)の各成分のうち一部の成分を圧縮し、圧縮した成分の全部又は一部を、ハッシュ値を求める際に用いる。一方、復号装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)の各成分のうち圧縮された成分を伸張すると共に、圧縮されていない成分と秘密鍵成分とを用いてべき乗算や乗算などの各種演算を行うことにより、復号済みの平文を得る。
【００６１】
尚、本実施の形態にかかる暗号化装置及び復号装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００６２】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施に特有の各種機能について説明する。図１３は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１００は、乱数生成部１０１と、第１べき乗計算部１０２と、乗算部１０３と、暗号文成分圧縮部１０４と、ハッシュ値計算部１０５と、第２べき乗計算部１０６と、第２暗号文成分圧縮部１０７と、出力部（図示せず）とを有する。これらの各部の実体は、暗号化装置１００のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００６３】
乱数生成部１０１は、乱数ｕを生成する。第１べき乗計算部１０２は、乱数生成部１０１が生成した乱数ｕと、公開鍵成分ｇ，ｇ~，ｈとを用いて、暗号文成分ｃ１として‘ｇ＾ｕ’を求め、暗号文成分ｃ２として‘ｇ~＾ｕ’を求め、係数ｂとして‘ｈ＾ｕ’を求める。乗算部１０３は、第１べき乗計算部１０２が求めたｂと、平文ｍとを用いて、暗号文成分ｃ３として‘ｍ×ｂ’を求める。暗号文成分圧縮部１０４は、乗算部１０３が求めた暗号文成分ｃ３でありトーラス上の元となっている暗号文成分ｃ３を圧縮することによりアフィン表現である圧縮暗号文成分ｃ３＊に変換する。即ち暗号文成分ｃ３に対してトーラス圧縮が行われることになる。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１，ｃ２と、暗号文成分圧縮部１０４が変換したｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。尚、従来の暗号化装置はここでハッシュ計算を行う場合、暗号文成分ｃ１,ｃ２と共にｃ３を用いていた。しかし、本実施の形態の暗号化装置１００は、ｃ３がアフィン表現に変換された圧縮暗号文成分ｃ３＊をハッシュ計算に用いる。
【００６４】
第２べき乗計算部１０６は、公開鍵成分ｅ，ｆと、乱数生成部１０１が生成した乱数ｕと、ハッシュ値計算部１０５が求めたハッシュ値ｖとを用いて、暗号文の成分ｃ４として‘ｅ^ｕ×ｆ^（ｕｖ）’を求める。第２暗号文成分圧縮部１０７は、第２べき乗計算部１０６が求めた暗号文成分ｃ４でありトーラス上の元となっている暗号文成分ｃ４をアフィン表現である圧縮暗号文成分ｃ４＊に変換する。出力部は、暗号文（ｃ１,ｃ２，ｃ３*，ｃ４*）を出力する。ここで、乱数生成部１０１、第１べき乗計算部１０２及び乗算部１０３は第１暗号文生成部として機能し、ハッシュ値計算部１０５及び第２べき乗計算部１０６は第２暗号文生成部として機能している。
【００６５】
以上のように、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号においてトーラス圧縮を行う場合、本実施の形態における暗号化装置１００は、暗号文の４つの成分のうち、復号時に最初に演算を行う必要のない２つの暗号文成分ｃ３,ｃ４のみを圧縮すると、復号時の伸張にかかる処理時間を隠蔽できる。
【００６６】
＜復号装置の構成＞
次に、本実施の形態にかかる復号装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図１４は、本実施の形態にかかる復号装置の機能的構成を例示する図である。復号装置２００は、受信部（図示せず）と、ハッシュ計算部２０１と、暗号文成分伸張部２０２と、第１べき乗計算部２０３と、第２べき乗計算部２０４と、逆元計算部２０５と、第１乗算部２０６と、第２乗算部２０７と、第３乗算部２０８と、トーラス元検証部２０９と、正当性検証部２１０と、復号済み平文出力部２１１とを有する。これらの各部は、復号装置２００のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００６７】
復号装置２００は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)を受信する。受信部は、暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）を暗号化装置１００から受信する。ハッシュ計算部２０１は、暗号文成分ｃ１，ｃ２と、圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。尚、従来の復号装置はここでハッシュ計算を行う場合、暗号文成分ｃ１,ｃ２と共に暗号文成分ｃ３を用いていた。しかし、本実施の形態の復号装置２００は、暗号文成分ｃ３がアフィン表現に変換された圧縮暗号文成分ｃ３＊をハッシュ計算に用いる。
【００６８】
第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いて、係数ｋ１として‘ｃ１＾（ｘ１＋ｙ１×ｖ）’を求め、係数ｋ２として‘ｃ２＾（ｘ２＋ｙ２×ｖ）’を求める。第２乗算部２０７は、第２べき乗計算部２０４が求めた係数ｋ１及びｋ２を用いて、検査式に用いる検証用データｋとして‘ｋ１×ｋ２’を求める。暗号文成分伸張部２０２は、アフィン表現である圧縮暗号文成分ｃ３＊及びｃ４＊を各々伸張することにより、拡大体表現である暗号文成分ｃ３及びｃ４に各々変換する。第１べき乗計算部２０３は、暗号文成分ｃ１，ｃ２と、秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂ１として‘ｃ１＾ｚ１’を求め、係数ｂ２として‘ｃ２＾ｚ２’を求める。第１乗算部２０６は、第１べき乗計算部２０３が求めた係数ｂ１及びｂ２を用いて、係数ｂとして‘ｂ１×ｂ２’を求める。逆元計算部２０５は、第１乗算部２０６が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。第３乗算部２０８は、逆元計算部２０５が求めた中間データ‘ｂ＾（−１）’と、暗号文成分伸張部２０２が変換した暗号文成分ｃ３とを用いて、復号済みの平文ｍとして‘ｃ３×ｂ＾（−１）’を求める。
【００６９】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。具体的には、トーラス元検証部２０９は、各成分ｃ１，ｃ２，ｃ３＊，ｃ４＊が群Ｇ~の元であるか否か及び各成分ｃ１，ｃ２が群Ｇの元であるか否かを判定する。群Ｇの元であるか否かの判定は例えばｃ１，ｃ２をそれぞれＧの位数乗（ｑ乗）が‘１’（単位元）となっているかを確認することで確かめられる。尚、従来では、各成分ｃ１，ｃ２，ｃ３が群Ｇの元であるか否かを判定するが、ここでは、暗号文成分ｃ３が変換された圧縮暗号文成分ｃ３＊については、圧縮により群Ｇの元となっていることが明らかなため、ｃ３＊に関する判定を行わない。そして、トーラス元検証部２０９は、当該判定結果が肯定的である場合、暗号文は正当であるという検証結果を出力し、当該判定結果が否定的である場合、暗号文は正当ではないという検証結果を出力する。
【００７０】
正当性検証部２１０は、第２乗算部２０７が求めた検証用データｋと、暗号文成分伸張部２０２が変換した圧縮暗号文成分ｃ４とを比較する。ここでは、正当性検証部２１０は、この比較によりこれらが等価であるか否かを判定する。即ち、正当性検証部２１０は、検査式‘ｋ＝ｃ４’が成立するか否かを判定することにより、暗号文が正当であるか否かを検証する。そして、正当性検証部２１０は、当該検証結果を出力する。復号済み平文出力部２１１は、トーラス元検証部２０９が出力した検証結果と、正当性検証部２１０が出力した検証結果とが共に暗号文が正当であることを示す場合に、平文ｍを出力し、いずれか一方の検証結果が暗号文が正当でないことを示す場合に、エラーを出力する。なお、本実施の形態においては、第１べき乗計算部２０３、逆元計算部２０５及び第１乗算部２０６は中間データ生成部として機能し、ハッシュ値計算部２０１、第２べき乗計算部２０４及び第２乗算部２０７は検証用データ生成部として機能し、第３乗算部２０８は復号済み平文生成部として機能している。
【００７１】
以上のように、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号においてトーラス圧縮を行う場合、本実施の形態における復号装置２００は、暗号文の４つの成分のうち圧縮されている成分ｃ３,ｃ４のみを伸張して、平文を復号する。
【００７２】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１００の行う暗号化処理の手順について図１５を用いて説明する。暗号化装置１００は、公開鍵（ｑ，ｇ，ｇ~，ｅ，ｆ，ｈ）と、平文ｍとを予め取得しているものとする。暗号化装置１００は、乱数ｕを生成する（ステップＳ１）。次いで、暗号化装置１００は、公開鍵成分ｇ，ｇ~，ｈとを用いて、暗号文成分ｃ１として‘ｇ＾ｕ’を求め、暗号文成分ｃ２として‘ｇ~＾ｕ’を求め、係数ｂとして‘ｈ＾ｕ’を求める（ステップＳ２）。次いで、暗号化装置１００は、ステップＳ２で求めたｂと、平文ｍとを用いて、暗号文成分ｃ３として‘ｍ×ｂ’を求めることにより、平文マスクを行う（ステップＳ３）。そして、暗号化装置１００は、ステップＳ３で求めた暗号文成分ｃ３でありトーラス上の元となっている暗号文成分ｃ３をアフィン表現である圧縮暗号文成分ｃ３＊に変換する（ステップＳ４）。次いで、暗号化装置１００は、ステップＳ２で求めた暗号文成分ｃ１，ｃ２と、ステップＳ４で得られた圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ５）。続いて、暗号化装置１００は、公開鍵成分ｅ，ｆと、ステップＳ１で生成した乱数ｕと、ステップＳ５で求めたハッシュ値ｖとを用いて、暗号文の成分ｃ４として‘ｅ^ｕ×ｆ^（ｕｖ）’を求める（ステップＳ６）。そして、暗号化装置１００は、ステップＳ４が求めた暗号文成分ｃ４でありトーラス上の元となっている暗号文成分ｃ４をアフィン表現である圧縮暗号文成分ｃ４＊に変換する（ステップＳ７）。そして、暗号化装置１００は、暗号文（ｃ１,ｃ２，ｃ３*，ｃ４*）を復号装置２００に送信する。
【００７３】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００の行う復号処理の手順について図１６を用いて説明する。尚、復号装置２００は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)を予め取得しているものとする。復号装置２００は、暗号化装置１００から送信された暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。そして、復号装置２００は、暗号文が正当であると判定した場合（ステップＳ２０：ＹＥＳ）、次いで、暗号文成分ｃ１，ｃ２と、圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ２１）。
【００７４】
そして、復号装置２００は、ステップＳ２１で求めたハッシュ値ｖと、秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いて、係数ｋ１として‘ｃ１＾（ｘ１＋ｙ１×ｖ）’を求め、係数ｋ２として‘ｃ２＾（ｘ２＋ｙ２×ｖ）’を求める（ステップＳ２２）。次いで、復号装置２００は、検査式に用いる検証用データｋとして、‘ｋ１×ｋ２’を求める（ステップＳ２３）。
【００７５】
また、復号装置２００は、圧縮暗号文成分ｃ４＊を伸張し、拡大体表現である暗号文成分ｃ４を得る（ステップＳ２４）。また、復号装置２００は、ステップＳ２３で求めた検証用データｋとステップＳ２４で伸張した暗号文成分ｃ４とを用いて、検査式‘ｋ＝ｃ４’が成立するか否かを判定して、暗号文の正当性を検証する（ステップＳ２５）。そして、復号装置２００は、ステップＳ２５の検査式が成立する、即ち、暗号文が正当であると判定した場合（ステップＳ２５：ＹＥＳ）、暗号文成分ｃ１，ｃ２と、秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂ１として‘ｃ１＾ｚ１’を求め、係数ｂ２として‘ｃ２＾ｚ２’を求める（ステップＳ２６）。次いで復号装置２００は、ステップＳ２６が求めた係数ｂ１及びｂ２を用いて、係数ｂとして‘ｂ１×ｂ２’を求める（ステップＳ２７）。その後、復号装置２００は、ステップＳ２７で求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める（ステップＳ２８）。また、復号装置２００は、圧縮暗号文成分ｃ３＊を伸張し、ｃ３を得る（ステップＳ２９）。そして、復号装置２００は、ステップＳ２８で求めた中間データ‘ｂ＾（−１）’と、ステップＳ２９で伸張したｃ３とを用いて、復号済みの平文ｍとして‘ｃ３×ｂ＾（−１）’を求める（ステップＳ３０）。ステップＳ２０及びステップＳ２５の判定結果が肯定的である場合には、復号装置２００は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ２０又はステップＳ２５の判定結果が否定的である場合、復号装置２００はエラーを出力し、復号済みの平文を出力しない。
【００７６】
尚、ステップＳ２０の処理と、ステップＳ２１〜Ｓ２３の処理と、ステップＳ２４の処理と、ステップＳ２６〜Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図６においては、各成分ｃ１,ｃ２,ｃ３＊,ｃ４＊が与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、伸張にかかる処理時間を隠蔽することができる。
【００７７】
即ち、上述したようにＣｒａｍｅｒ-Ｓｈｏｕｐ暗号の場合、暗号文が４つの成分の組になっており、これらの成分を独立に扱うことは非常に容易であることに注目し、並行処理が可能な環境では、暗号文成分を選択的に圧縮する。これにより、処理時間の増加分の一部を隠蔽することができる。従って、圧縮や伸張にかかる処理時間を隠蔽しつつ、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号にトーラス圧縮を組み合わせた暗号化方式を実現することができる。
【００７８】
ただし、並行して処理を実行する場合には、ステップＳ２０の判定結果やステップＳ２５の判定結果が否定的となる不正な暗号文を取り除く機構が必要となる。このため、本実施の形態においては、図１４に示したように、復号装置２００が復号済み平文出力部２１１を有するように構成して、トーラス元検証部２０９の判定結果であるステップＳ２０の判定結果と、正当性検証部２１０の判定結果であるステップＳ２５の判定結果とを用いて、暗号文が正当であるか否かを最終的に判定する。復号装置２００は、ステップＳ３０で得られる復号済みの平文ｍを出力しないことにより、結果的に不正な暗号文を取り除くことができる。
【００７９】
なお、本発明においては、暗号化装置１００と復号装置２００との間でハッシュ関数の出力が同じであれば暗号化や復号は可能である。このため、上述のステップＳ５とステップＳ２１とでハッシュ値を求める際に用いられる成分と表現とが表現の変換を施すことなく同一であれば、圧縮する暗号文成分は限定されない。
【００８０】
また、本実施の形態において各演算は拡大体表現で行ったが、射影表現で行ってもよい。ただし、射影表現では同じデータに対し複数の値を取り得るので、ハッシュ関数への入力や復号済みの平文を導出する際や正当性検証部２１０で等価性の判定を行う際に注意が必要である。
【００８１】
[第４の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００８２】
（１）構成
米国特許文献 ＵＳＰ７，２２１，７５８Ｂ２にＣｒａｍｅｒ−Ｓｈｏｕｐ暗号において暗号化方式のバリエーションが記載されており、この方式を用いると秘密鍵成分の個数を削減できる。このバリエーションに対しても、暗号文成分の一部を圧縮する構成を適用することが可能である。本実施の形態は、秘密鍵成分ｚ１,ｚ２の代わりにｚひとつで暗号化や復号を行うものである。
【００８３】
ここで、本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図１７を用いて説明する。鍵生成装置は、公開鍵ｇ（ｇ∈Ｇ）を拡大体表現から選択し、０以外の乱数ｗを生成する（ＧＳ１１）。次いで、鍵生成装置は、秘密鍵成分ｘ１,ｘ２,ｙ１,ｙ２,ｚとして各々乱数を生成する（ＧＳ１２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ１×ｇ~^ｘ２’を求め、公開鍵成分ｆとして‘ｇ^ｙ１×ｇ~^ｙ２’を求め、公開鍵成分ｈとして‘ｇ^ｚ’を求める（ＧＳ１３）。そして、鍵生成装置は、秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００８４】
暗号化装置１００の構成は上述の第３の実施の形態と同様であるため、その説明を省略する。図１８は本実施の形態にかかる復号装置２００´の機能的構成を例示する図である。
本実施の形態にかかる復号装置２００´の機能的構成が上述の第３の実施の形態の復号装置２００の機能的構成と異なる点は以下の通りである。復号装置２００´には秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ）が入力される。復号装置２００´は、第１乗算部２０６を有さない。第１べき乗計算部２０３は、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。なお、本実施の形態においては第１べき乗計算部２０３及び逆元計算部２０５が中間データ生成部として機能している。
【００８５】
（２）動作
＜復号処理＞
次に、本実施の形態にかかる復号装置２００´の行う復号処理の手順について図１９を用いて説明する。尚、暗号化装置１００の行う暗号化処理の手順は上述の第３の実施の形態と同様であるため、その説明を省略する。復号装置２００´は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ)を予め取得しているものとする。ステップＳ２０〜Ｓ２５は上述の第１の実施の形態と同様である。ステップＳ４０では、復号装置２００´は、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。次いで、ステップＳ２８では、復号装置２００´は、ステップＳ４０が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。Ｓ２９〜Ｓ３０の処理は上述の第３の実施の形態と同様である。
【００８６】
本実施の形態においては、ステップＳ２０の処理と、ステップＳ２１〜Ｓ２３の処理と、ステップＳ２４の処理と、ステップＳ４０，Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図１９においては、各成分ｃ１,ｃ２,ｃ３＊,ｃ４＊が与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号において本実施の形態のようにして秘密鍵成分の個数を削減した場合であっても、伸張にかかる処理時間を隠蔽することができる。
【００８７】
また本実施の形態においては複数の暗号文成分のうちｃ３を圧縮したが、ｃ１やｃ２を圧縮し、ｃ１ｃ２を圧縮している間にｃ３を生成すれば暗号化処理においても圧縮にかかる処理時間を隠蔽できる。どの暗号文成分を圧縮するかによって、暗号化、復号、あるいはその両方の圧縮にかかる処理時間や伸張にかかる処理時間を隠蔽できるのかが決まる。
【００８８】
[第５の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００８９】
（１）構成
上述の第４の実施の形態においては、秘密鍵成分ｚ１,ｚ２の代わりにｚを用いて秘密鍵成分の個数を削減した。ここでは秘密鍵成分の個数を更に削減して、秘密鍵成分ｘ１,ｘ２の代わりにｘを用い、秘密鍵成分ｙ１,ｙ２の代わりにｙを用いる。ただし、公開鍵の生成に用いられた乱数ｗが秘密鍵成分として加わる。また、ここでは圧縮する対象の暗号文成分がｃ３，ｃ４のみならずｃ２も含む場合について説明する。
【００９０】
ここで、本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図２０を用いて説明する。鍵生成装置は、公開鍵成分ｇ（ｇ∈Ｇ）を拡大体表現から選択し、‘０’以外の乱数ｗを生成する（ＧＳ２１）。次いで、鍵生成装置は、秘密鍵成分ｘ,ｙ,ｚとして各々乱数を生成する（ＧＳ２２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ’を求め、公開鍵成分fとして‘ｇ^ｙ’を求め、公開鍵成分ｈとして‘ｇ^ｚ’を求める（ＧＳ２３）。そして、鍵生成装置は、秘密鍵（ｘ,ｙ,ｚ，ｗ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００９１】
次に、本実施の形態にかかる暗号化装置１００´の機能的構成について図２１を用いて説明する。暗号化装置１００´の機能的構成が上述の第３の実施の形態の暗号化装置１００の機能的構成と異なる点は以下の通りである。暗号文成分圧縮部１０４は、第１べき乗計算部１０２が求めた暗号文成分ｃ２と、乗算部１０３が求めた暗号文成分ｃ３とを圧縮することによりアフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊に各々変換する。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１と、暗号文成分圧縮部１０４が変換した圧縮暗号文成分ｃ２＊及びｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。出力部は、暗号文（ｃ１,ｃ２*，ｃ３*，ｃ４*）を復号装置２００”に送信する。
【００９２】
次に、本実施の形態にかかる復号装置２００”の機能的構成について図２２を用いて説明する。本実施の形態にかかる復号装置２００”の機能的構成が上述の第３の実施の形態の復号装置２００の機能的構成と異なる点は以下の通りである。復号装置２００”は、第１乗算部２０６と、第２乗算部２０７とを有さず、第３べき乗計算部２１２を更に有する。復号装置２００”には秘密鍵（ｘ,ｙ,ｚ，ｗ）が入力される。受信部は、暗号文（ｃ１,ｃ２*，ｃ３*，ｃ４*）を暗号化装置１００´から受信する。暗号文成分伸張部２０２は、アフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊，ｃ４＊を各々伸張することにより、拡大体表現である暗号文成分ｃ２，ｃ３，ｃ４に各々変換する。第１べき乗計算部２０３は、上述の第２の実施の形態と同様にして、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を求める。ハッシュ計算部２０１は、暗号文成分ｃ１と、圧縮暗号文成分ｃ２＊，ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙとを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める。第３べき乗計算部２１２は、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める。
【００９３】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２＊，ｃ３＊，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。即ち、トーラス元検証部２０９は、暗号文成分ｃ１と、圧縮暗号文成分ｃ２＊，ｃ３＊，ｃ４＊とが群Ｇ~の元であるか否か及び各成分ｃ１が群Ｇの元であるか否かを判定し、当該判定結果を出力する。尚、圧縮暗号文成分ｃ２＊,ｃ３＊については、圧縮により群Ｇの元となっていることが明らかなため、ここではその判定を行わない。正当性検証部２１０は、第３べき乗計算部２１２が求めた検証用データｋ１と暗号文成分ｃ２とを用いて検査式１‘ｋ１＝ｃ２’が成立するか否かを判定すると共に、第２べき乗計算部２０４が求めた検証用データｋ２と成分ｃ４とを用いて検査式２‘ｋ２＝ｃ４’が成立するか否かを判定する。なお、本実施の形態においてはハッシュ値計算部２０１、第２べき乗計算部２０４及び第３べき乗計算部２１２が検証用データ生成部として機能している。
【００９４】
（２）動作
＜暗号化処理＞
本実施の形態にかかる暗号化装置１００´の行う暗号化処理の手順について図２３を用いて説明する。ステップＳ１〜Ｓ３の処理は上述の第３の実施の形態と同様である。ステップＳ５０では、暗号化装置１００´は、ステップＳ２で求めた暗号文成分ｃ２と、ステップＳ３で求めた暗号文成分ｃ３とをアフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊に各々変換する。次いで、暗号化装置１００´は、ステップＳ２で求めたｃ１と、ステップＳ５０で変換した圧縮暗号文成分ｃ２＊及びｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ５１）。ステップＳ６〜Ｓ７の処理は上述の第１の実施の形態と同様である。そして、暗号化装置１００´は、暗号文（ｃ１,ｃ２＊，ｃ３＊，ｃ４＊）を復号装置２００”に送信する。
【００９５】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００”の行う復号処理の手順について図２４を用いて説明する。復号装置２００”は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ, ｙ, ｚ，ｗ)を予め取得しているものとする。復号装置２００”は、暗号化装置１００´から送信された暗号文（ｃ１，ｃ２＊，ｃ３＊，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。そして、復号装置２００”は、暗号文が正当であると判定した場合（ステップＳ６０：ＹＥＳ）、次いで、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める（ステップＳ６１）。次いで、復号装置２００”は、暗号文成分ｃ１と圧縮暗号文成分ｃ２＊，ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ６２）。そして、復号装置２００”は、ステップＳ６２で求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙと、暗号文成分ｃ１とを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める（ステップＳ６３）。また、復号装置２００”は、圧縮暗号文成分ｃ２＊，ｃ４＊を伸張することにより、拡大体表現である暗号文成分ｃ２，ｃ４に各々変換する（ステップＳ６４）。そして、復号装置２００”は、検査式１‘ｋ１＝ｃ２’及び検査式２‘ｋ２＝ｃ４’が成立するか否かを判定する（ステップＳ６５）。双方の検査式が成立する場合（ステップＳ６５：ＹＥＳ）、上述の第４の実施の形態と同様にして、ステップＳ４０の処理を行う。ステップＳ２８〜Ｓ３０の処理は上述の第３の実施の形態と同様である。ステップＳ６０及びステップＳ６５の判定結果が肯定的である場合には、復号装置２００”は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ６０又はステップＳ６５の判定結果が否定的である場合、復号装置２００”はエラーを出力し、復号済みの平文を出力しない。
【００９６】
本実施の形態においては、ステップＳ６０の処理と、ステップＳ６１の処理と、ステップＳ６２〜Ｓ６３の処理と、ステップＳ６４の処理と、ステップＳ４０，Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図１４においては、暗号文成分ｃ１，ｃ４と、圧縮暗号文ｃ２＊，ｃ３＊とが与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号において本実施の形態のようにして秘密鍵成分の個数を削減した場合であっても、伸張にかかる処理時間を隠蔽することができる。
【００９７】
[第６の実施形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第６の実施の形態について説明する。なお、上述の第１の実施の形態乃至第５の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００９８】
上述の第１の実施の形態で説明した暗号文検証装置２０の正当性検証部２５や、第３の実施の形態乃至第５の実施の形態において説明した復号装置の正当性検証部２１０では、圧縮暗号成分が拡大体表現に伸張された後の暗号文成分を用いて、暗号文の正当性の検証を行った、しかし、異なる表現間で暗号文成分の同一性が判定できる場合、圧縮暗号文成分の伸張が不要となる場合がある。本実施の形態においてはその一例を説明する。尚、本実施の形態にかかる暗号方式は第５の実施の形態と同じであるものとし、圧縮する対象の暗号文成分はｃ２とｃ４とであるものとする。
【００９９】
本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理は第５の実施の形態と同一であるので省略するが、鍵生成装置は秘密鍵（ｘ,ｙ,ｚ，ｗ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【０１００】
次に、本実施の形態にかかる暗号化装置１００”の機能的構成について図２５を用いて説明する。暗号化装置１００”の機能的構成が上述の第５の実施の形態の暗号化装置１００´の機能的構成と異なる点は以下の通りである。暗号文成分圧縮部１０４は、第１べき乗計算部１０２が求めた暗号文成分ｃ２をアフィン表現である暗号文成分ｃ２＊に変換する。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１と、第１の暗号文成分圧縮部１０４が圧縮した圧縮暗号文成分ｃ２＊と、乗算部１０３が求めた暗号文成分ｃ３とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。出力部は、暗号文（ｃ１,ｃ２*，ｃ３，ｃ４*）を復号装置２００’’’に送信する。
【０１０１】
次に、本実施の形態にかかる復号装置２００’’’の機能的構成について図２６を用いて説明する。本実施の形態にかかる復号装置２００’’’の機能的構成が上述の第５の実施の形態の復号装置２００”の機能的構成と異なる点は以下の通りである。復号装置２００’’’は、暗号文成分伸張部２０２を有さない。復号装置２００’’’には秘密鍵（ｘ,ｙ,ｚ，ｗ）が入力される。受信部は、圧縮暗号文（ｃ１,ｃ２*，ｃ３，ｃ４*）を暗号化装置１００”から受信する。第１べき乗計算部２０３は、上述の第５の実施の形態と同様にして、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。ハッシュ計算部２０１は、暗号文成分ｃ１，ｃ３と、圧縮暗号文成分ｃ２＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙとを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める。第３べき乗計算部２１２は、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める。
【０１０２】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２＊，ｃ３，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。即ち、トーラス元検証部２０９は、各成分ｃ１，ｃ２＊，ｃ３，ｃ４＊が群Ｇの元であるか否か及び各成分ｃ１，ｃ３が群Ｇの元であるか否かを判定し、当該判定結果を出力する。尚、圧縮暗号文成分ｃ２＊については、圧縮により群Ｇの元となっていることが明らかなため、ここではその判定を行わない。正当性検証部２１０は、第３べき乗計算部２１２が求めた検証用データｋ１と圧縮暗号文成分ｃ２＊とを用いてｋ１とｃ２＊とが等価であるか否かを判定すると共に、第２べき乗計算部２０４が求めた検証用データｋ２と圧縮暗号文成分ｃ４＊とを用いてｋ２とｃ４＊とが等価であるか否かを判定することにより、暗号文の正当性を検証する。即ち、本実施の形態においては、正当性検証部２１０は、圧縮暗号文成分ｃ２＊，ｃ４＊が伸張された拡大体表現である暗号文成分ｃ２，ｃ４を用いるのではなく、圧縮暗号文成分ｃ２＊，ｃ４＊自体を用いて、暗号文の正当性を検証する。なお、本実施の形態においては、第１べき乗計算部２０３、逆元計算部２０５及び第３乗算部２０８が復号済み平文生成部として機能している。
【０１０３】
（２）動作
＜暗号化処理＞
本実施の形態にかかる暗号化装置１００”の行う暗号化処理の手順について図２７を用いて説明する。ステップＳ１〜Ｓ３の処理は上述の第５の実施の形態と同様である。ステップＳ７０では、暗号化装置１００”は、ステップＳ２で求めた暗号文成分ｃ２をアフィン表現である圧縮暗号文成分ｃ２＊に変換する。次いで、暗号化装置１００”は、ステップＳ２で求めた暗号文成分ｃ１と、ステップＳ７０で変換した圧縮暗号文成分ｃ２＊と、ステップＳ３で生成した暗号文成分ｃ３とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ７１）。ステップＳ６〜Ｓ７の処理は上述の第５の実施の形態と同様である。そして、暗号化装置１００”は、暗号文（ｃ１,ｃ２＊，ｃ３，ｃ４＊）を復号装置２００に送信する。
【０１０４】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００’’’の行う復号処理の手順について図２８を用いて説明する。復号装置２００’’’は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ, ｙ, ｚ，ｗ)を予め取得しているものとする。復号装置２００’’’は、暗号化装置１００”から送信された圧縮暗号文（ｃ１，ｃ２＊，ｃ３，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、圧縮暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する（ステップＳ８０）。そして、復号装置２００’’’は、暗号文が正当であると判定した場合（ステップＳ８０：ＹＥＳ）、次いで、第５の実施の形態と同様に乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める（ステップＳ６１）。次いで、復号装置２００’’’は、暗号文成分ｃ１，ｃ３と、圧縮暗号文ｃ２＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ８１）。そして、復号装置２００’’’は、ステップＳ８１で求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙと、暗号文成分ｃ１とを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める（ステップＳ６３）。また、復号装置２００’’’は、検証用データｋ１とｃ圧縮暗号文成分ｃ２＊とが等価であるか否か及び検証用データｋ２と圧縮暗号文成分ｃ４＊とが等価であるか否かを判定する（ステップＳ８２）。双方とも同値である場合（ステップＳ８２：ＹＥＳ）、上述の第５の実施の形態と同様にして、復号装置２００’’’は、ステップＳ４０、ステップ２８の処理を行い、ステップ２８の計算の結果得られた中間データと暗号文成分ｃ３とを用いて‘ｍ＝ｂ＾（−１）・ｃ３’を計算して（ステップＳ３０）、復号済み平文ｍを得る。ステップＳ８０及びステップＳ８２の判定結果が肯定的である場合には、復号装置２００’’’は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ８０又はステップＳ８２の判定結果が否定的である場合、復号装置２００’’’はエラーを出力し、復号済みの平文を出力しない。
【０１０５】
以上のようにして、異なる表現間で暗号文成分の同一性が判定できる場合、圧縮暗号文成分の伸張を行わないことにより、伸張にかかる処理時間を削減することができる。
【０１０６】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成成分を変形して具体化できる。また、前記実施形態に開示されている複数の構成成分の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成成分から幾つかの構成成分を削除してもよい。さらに、異なる実施形態にわたる構成成分を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【０１０７】
＜変形例１＞
上述した各実施の形態において、暗号化装置１０で各々実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。暗号化装置１０´、１００、１００´，１００”，復号装置３０，２００，２００´，２００”、２００’’’及び暗号文検証装置２０で各々実行される各種プログラムについても同様である。
【０１０８】
また、上述した実施の形態において、暗号化装置１０の有する各部は、ＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものとしたが、これらの全部又は一部をハードウェアにより構成するようにしても良い。暗号化装置１０´、１００、１００´，１００”，復号装置３０，２００，２００´，２００”、２００’’’ 及び暗号文検証装置２０の有する各部についても同様である。
【０１０９】
また、上述の各実施の形態の暗号化装置及び復号装置においては、べき乗計算及び乗算をべき乗計算部及び乗算部が各々行うように構成したが、べき乗計算部及び乗算部を１つの計算部として取り扱い、計算部がべき乗計算及び乗算を行うように構成しても良い。
【０１１０】
＜変形例２＞
上述の第４の実施の形態においては、暗号化装置１００は、暗号文成分のうちｃ３,ｃ４のみならずｃ２を圧縮するように構成したが、第３の実施の形態と同様にして、暗号文成分ｃ３,ｃ４のみを圧縮するようにしても良い。
【０１１１】
また、各実施の形態においては、圧縮する対象の暗号文成分の数は、２つ又は３つに限らず１つであっても４つであっても良い。また、いずれの暗号文成分を圧縮するかは上述の例に限らない。
【０１１２】
尚、第３の実施の形態乃至第６の実施の形態においては、暗号文は（ｃ１，ｃ２，ｃ３，ｃ４）の４つの暗号文成分を含むように構成したが、暗号文成分の数はこれに限らない。
【０１１３】
また、上述の第３の実施の形態乃至第６の実施の形態の暗号化処理においては、ハッシュ値ｖと公開鍵成分とを用いて暗号文成分ｃ４を求める方法としてべき乗計算を行うこととしたが、その方法はべき乗計算に限らない。
【図面の簡単な説明】
【０１１４】
【図１】有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式で複数の暗号文成分を含む暗号文の正当性を検証する基本的な構成を例示する図である。
【図２】第１の実施の形態にかかる暗号化装置の機能的構成を例示する図である。
【図３】同実施の形態にかかる暗号文検証装置の機能的構成を例示する図である。
【図４】同実施の形態にかかる暗号化装置１０の行う暗号化処理の手順を示すフローチャートである。
【図５】同実施の形態にかかる暗号文検証装置２０の行う暗号文検証処理の手順を示すフローチャートである。
【図６】ＥｌＧａｍａｌ暗号において平文ｍを暗号化して暗号文を生成する暗号化装置と暗号文を復号する復号装置とを例示する図である。
【図７】第２の実施の形態にかかる暗号化装置の機能的構成を例示する図である。
【図８】同実施の形態にかかる復号装置の機能的構成を例示する図である。
【図９】同実施の形態にかかる暗号化装置１０´の行う暗号化処理の手順を示すフローチャートである。
【図１０】同実施の形態にかかる復号装置３０の行う暗号化処理の手順を示すフローチャートである。
【図１１】Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号スキームの基本的な構成を例示する図である。
【図１２】第３の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図１３】同実施の形態にかかる暗号化装置１００の機能的構成を例示する図である。
【図１４】同実施の形態にかかる復号装置２００の機能的構成を例示する図である。
【図１５】同実施の形態にかかる暗号化装置１００の行う暗号化処理の手順を示すフローチャートである。
【図１６】同実施の形態にかかる復号装置２００の行う復号処理の手順を示すフローチャートである。
【図１７】第４の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図１８】同実施の形態にかかる復号装置２００´の機能的構成を例示する図である。
【図１９】同実施の形態にかかる復号装置２００´の行う復号処理の手順を示すフローチャートである。
【図２０】第５の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図２１】同実施の形態にかかる暗号化装置１００の機能的構成を例示する図である。
【図２２】同実施の形態にかかる復号装置２００”の機能的構成を例示する図である。
【図２３】同実施の形態にかかる暗号化装置１００の行う暗号化処理の手順を示すフローチャートである。
【図２４】同実施の形態にかかる復号装置２００”の行う復号処理の手順を示すフローチャートである。
【図２５】第６の実施の形態にかかる暗号化装置１００”の機能的構成を例示する図である。
【図２６】同実施の形態にかかる復号装置２００’’’の機能的構成を例示する図である。
【図２７】同実施の形態にかかる暗号化装置１００”の行う暗号化処理の手順を示すフローチャートである。
【図２８】同実施の形態にかかる復号装置２００’’’の行う復号処理の手順を示すフローチャートである。
【符号の説明】
【０１１５】
１０，１０´，１００，１００´,１００” 暗号化装置
１１ 平文受信部
１２ 公開鍵受信部
１３ 第１暗号文生成部
１４ 暗号文成分圧縮部
１５ 第１暗号文生成部
１６ 暗号文出力部
２０ 暗号文検証装置
２１ 暗号文受信部
２２ 秘密鍵受信部
２３ 中間データ生成部
２４ 暗号文成分伸張部
２５ 正当性検証部
２６ 検証結果出力部
３０ 復号装置
３１ 暗号文受信部
３２ 秘密鍵受信部
３３ 中間データ生成部
３４ 暗号文成分伸張部
３５ 復号済み平文生成部
３６ 復号済み平文出力部
１０１ 乱数生成部
１０２ 第１べき乗計算部
１０３ 乗算部
１０４ 暗号文成分圧縮部
１０５ ハッシュ値計算部
１０６ 第２べき乗計算部
１０７ 第２暗号文成分圧縮部
２００,２００´，２００”，２００’’’ 復号装置
２０１ ハッシュ計算部
２０２ 圧縮暗号文成分伸張部
２０３ 第１べき乗計算部
２０４ 第２べき乗計算部
２０５ 逆元計算部
２０６ 第１乗算部
２０７ 第２乗算部
２０８ 第３乗算部
２０９ トーラス元検証部
２１０ 正当性検証部
２１１ 復号済み平文出力部
２１２ 第３べき乗計算部
【技術分野】
【０００１】
本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式にかかる暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムに関する。
【背景技術】
【０００２】
通信路を流れる情報を保護するために、暗号を用いる方法がある。暗号を用いる方法には、通信相手と事前に鍵を共有しておく必要があるものもある。このような方法では、鍵の共有や管理に大きな手間がかかる。一方、公開鍵暗号を用いる方法では、事前に鍵を共有することなしに安全な通信を実現できる。このため、ネットワーク・セキュリティの基盤技術として幅広く用いられている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキームやプロトコルが用いられるようになってきた。
【０００３】
公開鍵暗号の暗号方式にはＥｌＧａｍａｌ暗号やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号のように離散対数問題の困難性を安全性の根拠とするものがある。離散対数問題とは、巡回群‘Ｇ＝＜ｇ＞’において‘ｙ∈Ｇ’が与えられたときに、‘ｙ＝ｇ＾ｘ’を満たすｘを求める問題である。尚、‘^’はべき乗を表す。巡回群Ｇとしては、有限体の乗法群や楕円曲線の有理点のなす加法群（ヤコビ群）が用いられる。離散対数問題を解くアルゴリズムには、シャンクのアルゴリズムやポラードのρ法のようにいずれの巡回群上で定義された離散対数問題に対しても適用可能なものと、位数計算法にように有限体の乗法群上で定義された離散対数問題のみに適用可能なものとが存在する。
【０００４】
位数計算法は効率的であるため、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は解読されやすい。したがって、同じ安全性を確保するために、有限体の乗法群上の離散対数問題を用いた公開鍵暗号は、楕円曲線上の離散対数問題を用いた公開鍵暗号よりも鍵長や暗号文長を大きくする必要がある。
【０００５】
現在、公開鍵暗号において典型的なセキュリティパラメータは１０２４ビット〜２０４８ビットである。セキュリティパラメータとは、公開鍵サイズや暗号文サイズを決定するパラメータであり、暗号方式の安全性に影響を与えるパラメータである。このセキュリティパラメータが大きくなれば、公開鍵サイズや暗号文サイズも大きくなる。解読が困難とされるセキュリティパラメータは年々大きくなっている。これは、計算機の進歩に伴い攻撃者の能力も向上するためである。公開鍵暗号では公開鍵サイズや暗号文サイズは、暗号方式により異なるが、セキュリティパラメータの数倍となる。
【０００６】
そこで、公開鍵暗号における公開鍵サイズや暗号文サイズを圧縮する方法が提案されている（例えば、非特許文献１参照）。この方法は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の成分を小さいビット数で表現できるという事実に基づいている。代数的トーラスの属する拡大体の次数ｎが高々二つの素数ｐ，ｑの冪の積‘ｌ＝（ｐ＾ｍ）・（ｑ＾ｎ）’であるとき、圧縮率（＝圧縮前のビット数／圧縮後のビット数）は、‘ｌ/φ(ｌ)’となることが知られている。ただし、φ（・）はオイラー関数である。ｐ＾ｍは、pのｍ乗である。小さいビット数の表現への変換は、拡大体表現を射影表現に変換する写像ρと射影表現をアフィン表現に変換する写像τによって行われる。暗号文を圧縮する場合の具体例を示す。拡大体表現の暗号文ｃを入力として計算を行い、圧縮暗号文γを得る（式１参照）。
【０００７】
ρ(c)=γ・・・（式１）
【０００８】
元のビット数の表現に戻すには、それぞれρ、τの逆写像を計算すればよい。ρの逆写像をψと書き、τの逆写像をτ−1と書くことにする。圧縮暗号文としてγが与えられたときに計算を行い、cを得る（式２参照）。
【０００９】
ψτ―1(γ)= c・・・（式２）
【００１０】
また、非特許文献１、２では、前記圧縮写像１、２と前記伸張写像１，２の構成法と、それらを用いて次のような拡大体表現をアフィン表現に圧縮する写像ρ６、アフィン表現を拡大体表現に伸張する写像‘ρ６＾（−１）’の構成法が示されている。圧縮写像ρ６は、６次拡大体Ｆ｛（ｐ＾ｍ）＾６｝上の拡大体表現のトーラスＴの任意の元ｔを入力として計算し、アフィン表現Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊の要素との組を得る（式３参照）。
【００１１】
ρ６（ｔ）＝（ａ，ｂ）∈Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊・・・（式３）
【００１２】
尚、ここで‘×’は直積を表すものとする。また、Ａが集合であるとき、Ａ＾ｍはｍ個のＡの直積集合となる。例えば、‘Ａ＾３＝Ａ×Ａ×Ａ’となる。具体的には例えば、‘｛０，１、２｝＾２＝｛（０，０），（０，１），（０，２），（１，０），（１，１），（１，２），（２，０），（２，１），（２，２）｝’となる。ここで、Ｆ｛ｐ＾ｍ｝は、素体Ｆ｛ｐ｝のｍ次拡大体であり、 Ｆ｛ｐ＾ｍ｝の要素はベクトル表現を用いると、｛０，・・・，ｐ−１｝＾ｍの要素で表現できる。Ｆ｛ｐ＾ｍ｝＾＊は、Ｆ｛ｐ＾ｍ｝の乗法群であり、Ｆ｛ｐ＾ｍ｝＾ｍの要素はベクトル表現を用いると、｛０，・・・，ｐ−１｝＼｛０｝＾ｍの要素で表される。‘＼’は集合の引き算を表す。
６＾（−１）’は、（ａ，ｂ）∈Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊を入力として計算し、６次拡大体Ｆ｛（ｐ＾ｍ）＾６｝上の拡大体表現のトーラスＴの元ｔを得る（式４参照）。
【００１３】
ρ−１（ａ，ｂ）＝ｔ∈Ｔ・・・（式４）
【００１４】
また、非特許文献２では、Ｆ｛ｐ＾ｍ｝の６次拡大体上のトーラスの要素の拡大体表現｛０，・・・，ｐ−１｝＾｛６＾ｍ｝と射影表現｛０，・・・，ｐ−１｝＾｛６＊ｍ｝とアフィン表現Ｆ｛ｐ＾ｍ｝×Ｆ｛ｐ＾ｍ｝＾＊に対して、上記のρ、ψ、τ、τ−１の構成法を示し、それを元に（式３）と（式４）との写像を構成している。このとき、拡大体表現と射影表現とに対する演算は、共にＦ｛ｐ＾（６＊ｍ）｝の演算で、非特許文献１、２ではＦ｛ｐ＾（６＊ｍ）｝の演算をＦ｛（（ｐ＾ｍ）＾３）＾２｝の演算として実現している。アフィン表現の要素は拡大体表現や射影表現よりも短いビット長で表現できる反面、演算することができない。
【００１５】
代数的トーラスを用いた圧縮や伸張は、公開鍵暗号における公開鍵や暗号文だけでなく、デジタル署名における署名や鍵交換スキームにおける交換メッセージにも適用できる。
【００１６】
近年では、離散対数問題の困難性に基づく様々な公開鍵暗号の暗号方式が提案されている。例えば、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号（非特許文献３参照）は、標準モデルでの安全性が証明されている方式であるが、公開鍵や暗号文の成分の数が多いという特徴がある。具体的には、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号の暗号文は４つの成分（ｃ１， ｃ２, ｃ３, ｃ４）からなり、公開鍵も５つの成分（ｇ，ｇ~，ｅ，ｆ，ｈ）が含まれる。しかも、各成分は実際に暗号に用いられる群よりも大きな表現で表されるという問題がある。つまり、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号は有限群Ｇ~の素数位数部分群Ｇ上で定義されているが、公開鍵や暗号文の成分は有限群Ｇ~の表現で表されている。具体的には、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号は素体の乗法群の素数位数部分群で定義されているが、公開鍵や暗号文の成分は素体の表現で表されている。
【００１７】
Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号やその他の公開鍵暗号において、有限群Ｇ~の部分群であって実際に暗号に用いられる群Ｇを代数的トーラスＴの部分群とすることにより、公開鍵や暗号文を有限群Ｇ~のサイズではなく代数的トーラスＴのサイズ、すなわち群Ｇ~よりも小さなビット数で表現が可能となる。例えば、素体上の代数的トーラスを用いたＥｌＧａｍａｌ暗号やＤＨ鍵交換（非特許文献１、４参照）はこの概念を利用し、公開鍵や暗号文のサイズを小さくしたものである。
【００１８】
ここで、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号の処理の概要を説明する。平文ｍを暗号化する暗号化装置には、鍵生成装置で生成された公開鍵(ｑ,ｇ,ｇ~,ｅ,ｆ,ｈ)が入力される。尚、ｑは素数で有限群Ｇ~の部分群Ｇの位数、ｇは暗号が定義される部分群Ｇの生成元、ｇ~,ｅ,ｆ,ｈも部分群Ｇの元とする。平文ｍもＧの元でなければならない。暗号化装置は、乱数の生成、べき乗計算、乗算、ハッシュ計算を行い、平文ｍに対応する暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を計算する。この暗号文(ｃ１, ｃ２, ｃ３, ｃ４)は、復号装置に入力される。また、復号装置には、公開鍵に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)が入力される。この秘密鍵は‘１’から‘ｑ−１’までの整数(又は‘０’から‘ｑ-１’までの整数)とする。復号装置は、秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)と暗号文(ｃ１, ｃ２, ｃ３, ｃ４)とを用いて、正当な暗号文であるかのチェックを行い、平文ｍを計算する。
【００１９】
【非特許文献１】K. Rubin and A. Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003.
【非特許文献２】Robert Granger, Dan Page, Martijn Stam: A Comparison of CEILIDH and XTR. ANTS 2004: 235-249
【非特許文献３】R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertextattack”, CRYPTO'98, LNCS 1462, pp.13-25, 1998.
【非特許文献４】M. van Dijkand D. Woodruff, “Asymptotically Optimal Communication for Torus-Based Cryptography”, CRYPTO 2004, LNCS 3152, 157-178, 2004.
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、例えばＣｒａｍｅｒ-Ｓｈｏｕｐ暗号のような乗法群の部分群上の離散対数問題を安全性の根拠とする公開鍵暗号の暗号方式において、暗号化や復号と圧縮や伸張とを行うことを考えた場合、通常、暗号化装置で暗号化して圧縮した後データを送信し、復号装置で受信したデータを伸張して復号するという手順で処理を行う。暗号化装置でこのような圧縮を行う場合、これを行わない場合と比べ、送信するデータのサイズを小さくすることができるため、通信コストが下がるものの、処理時間が増大する。復号装置で伸張を行う場合も、これを行わない場合に比べ、処理時間が増大する。
【００２１】
本発明は、上記に鑑みてなされたものであって、乗法群の部分群上の離散対数問題に安全性の根拠を置く暗号方式において、処理時間の増大を抑制しつつ、データのサイズを低減可能な暗号化装置、復号装置、暗号化方法、復号方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
上述した課題を解決し、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、平文を受信する平文受信部と、１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成部と、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る暗号文成分圧縮部と、受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力部とを備えることを特徴とする。
【００２３】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成部と、前記復号済みの平文を出力する復号済み平文出力部とを備えることを特徴とする。
【００２４】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が正当ではない旨を出力する復号済み平文出力部とを備えることを特徴とする。
【００２５】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文正当性検証装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、前記圧縮暗号文成分の表現を演算可能な表現である伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて前記暗号文の正当性を検証する正当性検証部と、前記正当性検証部の検証結果を出力する検証結果出力部とを備えることを特徴とする。
【００２６】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文検証装置であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、前記正当性検証部の検証結果を出力する検証結果出力部とを備えることを特徴とする。
【００２７】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置で実行される暗号化方法であって、平文を受信する平文受信ステップと、１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信ステップと、受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成ステップと、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮ステップと、受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成ステップと、少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力ステップとを含むことを特徴とする。
【００２８】
また、本発明は、有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置で実行される復号方法であって、前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信ステップと、前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信ステップと、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成ステップと、前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張ステップと、前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成ステップと、復号済みの前記平文を出力する復号済み平文出力ステップとを含むことを特徴とする。
【００２９】
また、本発明は、プログラムであって、上記の方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００３０】
本発明によれば、乗法群の部分群上の離散対数問題に安全性の根拠を置く暗号方式において、処理時間の増大を抑制しつつ、データのサイズを低減可能になる。
【発明を実施するための最良の形態】
【００３１】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの最良な実施の形態を詳細に説明する。
【００３２】
[第１の実施の形態]
（１）構成
＜一般的暗号方式の構成＞
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式で複数の暗号文成分を含む暗号文の正当性を検証する基本的な構成について図１を用いて説明する。まず、公開鍵に含まれる公開鍵成分ｐｋ及び当該公開鍵成分に対応する秘密鍵に含まれる秘密鍵成分ｓｋが図示しない鍵生成装置で生成される。公開鍵成分ｐｋが暗号化装置で受信され、当該公開鍵成分ｐｋに対応する秘密鍵成分ｓｋが暗号文検証装置で受信される。暗号化装置は公開鍵成分ｐｋを用いて平文ｍに対応する暗号文（ｃ１、ｃ２）を計算してこれを出力する。一方、暗号文検証装置２０は暗号文（ｃ１，ｃ２）を受信すると、これと秘密鍵成分ｓｋを用いて暗号文（ｃ１，ｃ２）が正当なものであるか否かを検証する。なお、公開鍵成分ｐｋおよび平文ｍが圧縮された表現、即ち、アフィン表現（ｐｋ＊，ｍ＊）となっている場合、暗号化装置１０への入力以前に拡大体表現や射影表現に伸張（変換）するものとする。
【００３３】
次に、本実施の形態にかかる暗号化装置及び暗号文検証装置の構成について説明する。暗号化装置及び暗号文検証装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００３４】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施の形態に特有の各種機能について説明する。図２は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１０は、平文受信部１１と、公開鍵受信部１２と、第１暗号文生成部１３と、暗号文成分圧縮部１４と、第２暗号文生成部１５と、暗号文出力部１６とを有する。これらの各部の実体は、暗号化装置１０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００３５】
平文受信部１１は、平文ｍを受信する。公開鍵受信部１２は、公開鍵成分ｐｋを受信する。第１暗号文生成部１３は、平文受信部１１が受信した平文ｍと公開鍵受信部１２が受信した公開鍵成分ｐｋとを用いて、暗号文成分ｃ１を生成する。暗号文成分圧縮部１４は、第１暗号文生成部１３が生成した暗号文成分ｃ１をアフィン表現に変換して圧縮暗号文成分ｃ１＊を生成する。即ち、本実施の形態において暗号化装置１０は、複数の暗号文成分のうち、暗号文成分ｃ１を圧縮する。同時に第２暗号文生成部１５は、第１暗号文生成部１３が生成した暗号文成分ｃ１と公開鍵受信部１２が受信した公開鍵成分ｐｋとを用いて暗号文成分ｃ２を生成する。暗号文出力部１６は、暗号文成分圧縮部１４が生成した圧縮暗号文成分ｃ１＊と第２暗号文生成部１５が生成した暗号文成分ｃ２とを出力する。
【００３６】
＜暗号文検証装置の構成＞
次に、本実施の形態にかかる暗号文検証装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図３は、本実施の形態にかかる暗号文検証装置の機能的構成を例示する図である。暗号文検証装置２０は、暗号文受信部２１と、秘密鍵受信部２２と、中間データ生成部２３と、暗号文成分伸張部２４と、正当性検証部２５と、検証結果出力部２６とを有する。これらの各部は、暗号文検証装置２０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００３７】
暗号文受信部２１は、暗号文（ｃ１＊，ｃ２）を受信する。秘密鍵受信部２２は、秘密鍵成分ｓｋを受信する。中間データ生成部２３は、暗号文受信部２１が受信した暗号文成分ｃ２と秘密鍵受信部２２が受信した秘密鍵成分ｓｋとを用いて、暗号文の復号に用いる中間データｋを生成する。中間データ生成部２３が中間データｋを生成すると同時に、暗号文成分伸張部２４は、暗号文受信部２１が受信した圧縮暗号文成分ｃ１＊を拡大体表現である暗号文成分ｃ１へと伸張（変換）する。正当性検証部２５は、中間データ生成部２３が生成した中間データｋと暗号文成分伸張部２４が伸張した暗号文成分ｃ１とを用いて暗号文の正当性を検証する。検証結果出力部２６は正当性検証部２５の検証結果を出力する。
【００３８】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１０の行う暗号化処理の手順について図４を用いて説明する。暗号化装置１０は、公開鍵である公開鍵成分ｐｋと平文ｍとを受信し、公開鍵成分ｐｋと平文ｍとを用いて計算を行って、暗号文成分ｃ１を生成する（ステップＳＴ１）。次に暗号化装置１０は、ｃ１の表現をアフィン表現へと圧縮（変換）する（ステップＳＴ２）。続いて、ステップＳＴ１で求めた暗号文成分ｃ１と公開鍵成分ｐｋとを用いて計算を行って、暗号文成分ｃ２を生成する（ステップＳＴ３）。
【００３９】
＜暗号文検証処理＞
次に、本実施の形態にかかる暗号文検証装置２０の行う暗号文検証処理の手順について図５を用いて説明する。暗号文検証装置２０は、暗号文（ｃ１＊，ｃ２）と秘密鍵に含まれる秘密鍵成分ｓｋとを受信し、暗号文成分ｃ２と秘密鍵成分ｓｋとを用いて中間データｋを生成する（ステップＳＴ１１）。次に、暗号文検証装置２０は、アフィン表現となっている圧縮暗号文成分ｃ１＊を拡大体表現である暗号文成分ｃ１に伸張（変換）する（ステップＳＴ１２）。次に、暗号文検証装置２０は、暗号文成分ｃ１と中間データｋとを比較し、暗号文の正当性を検証する（ステップＳＴ１３）。
【００４０】
暗号文成分の生成に依存関係があり暗号文成分ｃ１を用いて暗号文成分ｃ２を生成する場合には、暗号文成分ｃ２をアフィン表現へと圧縮すると、暗号文成分ｃ２を圧縮する処理の分だけ暗号文成分ｃ２を圧縮しない場合と比べ、処理時間が必要となる。暗号文成分圧縮部１４と第２暗号文生成部１５とが並列に動作可能であれば、第１暗号文生成部１３が暗号文成分ｃ１を生成した後、第２暗号文生成部１５がｃ２を生成している間に暗号文成分圧縮部１４が暗号文成分ｃ１をアフィン表現に圧縮し、（ｃ１＊，ｃ２）を暗号文とすれば、圧縮にかかる処理時間を隠蔽した上で、暗号文の一部を圧縮できる。
【００４１】
一方、暗号文検証装置２０で暗号文成分ｃ２を用いて中間データｋを生成し、暗号文成分ｃ１と比較する場合、暗号文成分ｃ２がアフィン表現でなければ暗号文を受信した直後に中間データｋを生成する処理を行うことができる。暗号文成分ｃ２がアフィン表現であった場合にはアフィン表現では演算が行えないので、拡大体表現か射影表現への変換が必要になり（本実施の形態では拡大体表現に変換）、その分の処理時間が余計に必要になる。しかし、本実施の形態によれば、中間データｋの生成に用いる成分を伸張する必要がないため、圧縮された成分の伸張にかかる処理時間を隠蔽することができる。
【００４２】
尚、暗号文検証装置２０に上述の実施の形態にかかる構成を適用したが、暗号文を復号する復号装置に適用しても良い。この場合、復号装置は、上述した暗号文受信部２１と、秘密鍵受信部２２と、中間データ生成部２３と、暗号文成分伸張部２４とに加え、復号済み平文生成部と、復号済み平文出力部とを有するように構成すれば良い。復号済み平文生成部は、中間データ生成部２３が生成した中間データと暗号文成分伸張部２４が伸張した暗号文成分ｃ１とを用いて復号済みの平文を生成する。復号済み平文出力部は、復号済み平文生成部が生成した復号済みの平文を出力する。このような復号装置や上述の暗号文検証装置によれば、処理時間の増加を抑えながら、暗号文の圧縮や伸張が行えるため、処理時間を短縮したい場合に用いて好適である。
【００４３】
ここでは暗号化にかかる処理時間及び暗号文の正当性の検証にかかる処理時間の両方を変えることなく暗号文成分を圧縮する例を示したが、暗号化にかかる処理時間、暗号文の正当性の検証にかかる処理時間及び復号にかかる処理時間のいずれか一つのみに処理時間の短縮の効果をもたらすように構成することも可能である。また本実施の形態では、演算可能な表現として拡大体表現を採ったが、射影表現で演算しても上述した効果は変わらない。
【００４４】
[第２の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００４５】
（１）構成
＜ＥｌＧａｍａｌ暗号＞
復号処理を高速化する具体的な例としてＥｌＧａｍａｌ暗号を取り上げる。図６は、ＥｌＧａｍａｌ暗号において平文ｍを暗号化して暗号文を生成する暗号化装置と暗号文を復号する復号装置とを例示する図である。尚、図示しない鍵生成装置は、生成元ｇを選択し、ｘをランダムに選択して、‘ｈ＝ｇ＾ｘ’を計算し、（ｑ,ｇ,ｈ）を公開鍵とし、ｘを秘密鍵とする。尚、ｑは素数で群Ｇ~の部分群Ｇの位数とし、ｇ，ｈは暗号が定義される部分群Ｇ（位数はｑ）の生成元とする。平文ｍも部分群Ｇの元でなければならない。暗号化装置には、鍵生成装置で生成された公開鍵(ｑ,ｇ,ｈ)と平文ｍとが入力される。暗号化装置は、乱数ｒを生成し、べき乗計算及び乗算を行って、平文ｍに対応する暗号文(ｃ１, ｃ２)を出力する。この暗号文(ｃ１, ｃ２)は、復号装置に入力される。また、復号装置には、公開鍵に対応する秘密鍵成分ｘが秘密鍵として入力される。この秘密鍵成分ｘは‘１’から‘ｑ’までの整数(又は‘０’から‘ｑ-１’までの整数)とする。復号装置は、秘密鍵成分ｘと暗号文(ｃ１, ｃ２)とを用いて、復号済みの平文ｍを得る。
【００４６】
次に、本実施の形態にかかる暗号化装置及び復号装置の構成について説明する。暗号化装置及び復号装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００４７】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施に特有の各種機能について説明する。図７は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１０´は、第１の実施の形態と同様に、平文受信部１１と、公開鍵受信部１２と、第１暗号文生成部１３と、暗号文成分圧縮部１４と、第２暗号文生成部１５と、暗号文出力部１６とを有する。これらの各部の実体は、暗号化装置１０´のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００４８】
平文受信部１１は、平文ｍを受信する。公開鍵受信部１２は、公開鍵（ｑ，ｇ，ｈ）を受信する。第１暗号文生成部１３は、‘０≦ｒ＜ｑ’なる乱数ｒを生成し、平文受信部１１が受信した平文ｍと公開鍵受信部１２が受信した公開鍵に含まれる公開鍵成分ｈとを用いて、‘ｃ２＝ｍ・ｈ＾ｒ’を計算して、暗号文成分ｃ２を生成する。暗号文成分圧縮部１４は、第１暗号文生成部１３が生成した暗号文成分ｃ２をアフィン表現に変換して圧縮暗号文成分ｃ２＊を生成する。即ち、本実施の形態において暗号化装置１０は、複数の暗号化成分のうち、暗号文成分ｃ２を圧縮する。同時に第２暗号文生成部１５は、第１暗号文生成部１３が生成した乱数ｒと公開鍵受信部１２が受信した公開鍵成分ｇとを用いて‘ｃ１＝ｇ＾ｒ’を計算し、暗号文成分ｃ１を生成する。暗号文出力部１６は、暗号文成分圧縮部１４が生成した圧縮暗号文成分ｃ２＊と第２暗号文生成部１５が生成した暗号文成分ｃ１とを出力する。
【００４９】
＜復号装置の構成＞
次に、本実施の形態にかかる復号装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図８は、本実施の形態にかかる復号装置の機能的構成を例示する図である。復号装置３０は、暗号文受信部３１と、秘密鍵受信部３２と、中間データ生成部３３と、暗号文成分伸張部３４と、復号済み平文生成部３５と、復号済み平文出力部３６とを有する。これらの各部は、復号装置３０のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００５０】
暗号文受信部３１は、暗号文（ｃ１，ｃ２＊）を受信する。秘密鍵受信部３２は、秘密鍵成分ｘを受信する。中間データ生成部３３は、暗号文受信部３１が受信した暗号文成分ｃ１と秘密鍵受信部３２が受信した秘密鍵成分ｘとを用いて‘ｋ＝（ｃ１＾ｘ）＾（−１）’を計算して、中間データｋを生成する。中間データ生成部３３が中間データｋを生成すると同時に、暗号文成分伸張部２４は、暗号文受信部３１が受信した圧縮暗号文成分ｃ２＊を拡大体表現である暗号文成分ｃ２へと伸張（変換）する。復号済み平文生成部３５は、中間データ生成部３３が生成した中間データｋと暗号文成分伸張部３４が伸張した暗号文成分ｃ２とを用いて、‘ｍ＝ｃ２・ｋ’を計算して、復号済みの平文を生成する。復号済み平文出力部３６は、復号済み平文生成部３５が生成した復号済みの平文を出力する。
【００５１】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１０´の行う暗号化処理の手順について図９を用いて説明する。暗号化装置１０´は、公開鍵（ｑ，ｇ，ｈ）と平文ｍとを受信し、乱数ｒを生成する（ステップＳＴ２１）。次いで、暗号化装置１０´は、乱数ｒと公開鍵成分ｈと平文ｍとを用いて暗号文成分ｃ２を生成する（ステップＳＴ２２）。次に暗号化装置１０´は、暗号文成分ｃ２の表現をアフィン表現へと変換することにより圧縮する（ステップＳＴ２３）。続いて、暗号化装置１０´は、乱数ｒと公開鍵成分ｇとを用いて暗号文成分ｃ１を生成する（ステップＳＴ２４）。
【００５２】
＜復号処理＞
次に、本実施の形態にかかる復号装置３０の行う暗号化処理の手順について図１０を用いて説明する。復号装置３０は、暗号文（ｃ１，ｃ２＊）と秘密鍵に含まれる秘密鍵成分ｘとを受信し、暗号文成分ｃ１と秘密鍵成分ｘとを用いて中間データｋを生成する（ステップＳＴ３１）。次に、復号装置３０は、アフィン表現となっている圧縮暗号文成分ｃ２＊を拡大体表現である暗号文成分ｃ２に伸張する（ステップＳＴ３２）。次に、復号装置３０は、ステップＳＴ３２で伸張した暗号文成分ｃ２とステップＳＴ３１で生成した中間データｋとを乗算し、復号済みの平文ｍを生成する（ステップＳＴ３３）。
【００５３】
以上のような構成によれば、ステップＳＴ３１で中間データｋを生成している間に、ステップＳＴ３２で圧縮暗号文成分ｃ２＊を暗号文成分ｃ２に伸張できるので、圧縮暗号文成分ｃ２＊の伸張にかかる処理時間を隠蔽しつつ、圧縮暗号文成分を伸張することが可能である。
【００５４】
[第３の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第３の実施の形態について説明する。なお、上述の第１の実施の形態又は第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５５】
（１）構成
＜Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号スキーム＞
次に、もうひとつの具体的な実施例として、上述の従来技術欄で説明したＣｒａｍｅｒ-Ｓｈｏｕｐ暗号スキームの基本的な構成について図１１を用いて説明する。まず、公開鍵及び当該公開鍵に対応する秘密鍵が鍵生成装置で生成される。公開鍵が暗号化装置に入力され、当該公開鍵に対応する秘密鍵が復号装置に入力される。公開鍵は上述の（ｑ,ｇ,ｇ~,ｅ,ｆ,ｈ）である。秘密鍵は上述の(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)である。暗号化装置は、公開鍵を用いて平文ｍに対応する暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を計算する。具体的には、暗号化装置は、公開鍵成分ｑを用いて‘０≦ｒ＜ｑ−１’なる乱数ｒを生成する。そして、暗号化装置は、乱数ｒと公開鍵成分ｇとを用いて暗号文の成分ｃ１として‘ｇ^ｒ’を求める。また、暗号化装置は、乱数ｒと公開鍵成分ｇ~とを用いて、暗号文成分ｃ２として‘ｇ~＾ｒ’を求める。また、暗号化装置は、乱数ｒと公開鍵成分ｈとを用いて係数ｂとして‘ｈ＾ｒ’を求める。そして、暗号化装置は、係数ｂと平文ｍとを用いて、暗号文成分ｃ３として‘ｂ×ｍ’を求める。次いで、暗号化装置は、各暗号文成分ｃ１, ｃ２, ｃ３についてハッシュ関数を用いた計算により、ハッシュ値‘ｖ＝Ｈ（ｃ１，ｃ２，ｃ３）’を求める。そして、暗号化装置は、乱数ｒと公開鍵成分ｅ，ｆとハッシュ値ｖとを用いて、暗号文成分ｃ４として‘ｅ^ｒ×ｆ^（ｒｖ）’を求める。この結果、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)が得られる。暗号化装置はこの暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を出力する。
【００５６】
一方、復号装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)を受信すると、これと秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)とから暗号文が正当であるか否かの判定を行い、当該判定結果が肯定的である場合、平文ｍを計算する。具体的には、復号装置は、各暗号文成分ｃ１, ｃ２, ｃ３, ｃ４が群Ｇ~の元であるか否か及び各暗号文成分ｃ１，ｃ２，ｃ３が群Ｇの元であるか否かを判定する。当該判定結果が肯定的である場合、復号装置は、暗号文成分ｃ１，ｃ２と秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂとして‘ｃ１^ｚ１×ｃ２^ｚ２’を求める。また、復号装置は、暗号文成分ｃ１,ｃ２,ｃ３を用いてハッシュ関数による計算を行い、暗号文成分ｃ１,ｃ２と秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いてべき乗計算と乗算とにより検査式に用いる検証用データｋとして‘ｃ１^（ｘ１+ｙ１×ｖ）×ｃ２^（ｘ２+ｙ２×ｖ）’を求める。検証用データとは、暗号文の正当性を検証するためのものである。そして、復号装置２００は、検証用データｋと暗号文成分ｃ４とを用いた検査式‘ｃ４＝ｋ’が成立するか否かを判定する。また、復号装置２００は、暗号文成分ｃ１,ｃ２と秘密鍵成分ｚ１,ｚ２とを用いてべき乗計算を行い、当該計算結果の逆元を中間データとして導出した後、暗号文成分ｃ３を用いて乗算を行うことにより、復号済みの平文ｍを得る。
【００５７】
尚、暗号文成分ｃ３は、復号時に平文の生成に用いる平文生成用暗号文成分であり、暗号文成分ｃ１〜ｃ２は、復号時に平文の生成と暗号文の正当性の検証とに用いる総合暗号文成分であり、暗号文成分ｃ４は、復号時に暗号文の正当性の検証に用いる検証用暗号文成分である。
【００５８】
＜公開鍵及び秘密鍵生成＞
次に、鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図１２を用いて説明する。鍵生成装置は、公開鍵成分ｇを群Ｇ~の元となるよう拡大体表現あるいは射影表現から選択し、０以外の乱数ｗを生成する（ＧＳ１）。次いで、鍵生成装置は、各秘密鍵成分ｘ１,ｘ２,ｙ１,ｙ２,ｚ１,ｚ２として各々乱数を生成する（ＧＳ２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ１×ｇ~^ｘ２’を求め、公開鍵成分ｆとして‘ｇ^ｙ１×ｇ~^ｙ２’を求め、公開鍵成分ｈとして‘ｇ^ｚ１×ｇ~^ｚ２’を求める（ＧＳ３）。そして、鍵生成装置は、秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ１,ｚ２）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００５９】
尚、この例では公開鍵成分ｇ,ｇ~,ｅ,ｆ,ｈの表現をアフィン表現に変換していないが、アフィン表現に変換する、即ち、圧縮することにより、鍵長を短くすることもできる。この場合は、暗号化処理や復号処理の前に公開鍵成分の表現を拡大体表現や射影表現に変換する、即ち、伸張する必要がある。平文についてもアフィン表現を用いることが可能である。
【００６０】
以上のようなＣｒａｍｅｒ-Ｓｈｏｕｐ暗号において、本実施の形態においては、暗号化装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)の各成分のうち一部の成分を圧縮し、圧縮した成分の全部又は一部を、ハッシュ値を求める際に用いる。一方、復号装置は、暗号文(ｃ１, ｃ２, ｃ３, ｃ４)の各成分のうち圧縮された成分を伸張すると共に、圧縮されていない成分と秘密鍵成分とを用いてべき乗算や乗算などの各種演算を行うことにより、復号済みの平文を得る。
【００６１】
尚、本実施の形態にかかる暗号化装置及び復号装置は各々、装置全体を制御するＣＰＵ（Central Processing Unit）等の制御装置と、各種データや各種プログラムを記憶するＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等の記憶装置と、各種データや各種プログラムを記憶するＨＤＤ（Hard Disk Drive）やＣＤ（Compact Disk）ドライブ装置等の外部記憶装置と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００６２】
＜暗号化装置の構成＞
次に、本実施の形態にかかる暗号化装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される本実施に特有の各種機能について説明する。図１３は、本実施の形態にかかる暗号化装置の機能的構成を例示する図である。暗号化装置１００は、乱数生成部１０１と、第１べき乗計算部１０２と、乗算部１０３と、暗号文成分圧縮部１０４と、ハッシュ値計算部１０５と、第２べき乗計算部１０６と、第２暗号文成分圧縮部１０７と、出力部（図示せず）とを有する。これらの各部の実体は、暗号化装置１００のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００６３】
乱数生成部１０１は、乱数ｕを生成する。第１べき乗計算部１０２は、乱数生成部１０１が生成した乱数ｕと、公開鍵成分ｇ，ｇ~，ｈとを用いて、暗号文成分ｃ１として‘ｇ＾ｕ’を求め、暗号文成分ｃ２として‘ｇ~＾ｕ’を求め、係数ｂとして‘ｈ＾ｕ’を求める。乗算部１０３は、第１べき乗計算部１０２が求めたｂと、平文ｍとを用いて、暗号文成分ｃ３として‘ｍ×ｂ’を求める。暗号文成分圧縮部１０４は、乗算部１０３が求めた暗号文成分ｃ３でありトーラス上の元となっている暗号文成分ｃ３を圧縮することによりアフィン表現である圧縮暗号文成分ｃ３＊に変換する。即ち暗号文成分ｃ３に対してトーラス圧縮が行われることになる。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１，ｃ２と、暗号文成分圧縮部１０４が変換したｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。尚、従来の暗号化装置はここでハッシュ計算を行う場合、暗号文成分ｃ１,ｃ２と共にｃ３を用いていた。しかし、本実施の形態の暗号化装置１００は、ｃ３がアフィン表現に変換された圧縮暗号文成分ｃ３＊をハッシュ計算に用いる。
【００６４】
第２べき乗計算部１０６は、公開鍵成分ｅ，ｆと、乱数生成部１０１が生成した乱数ｕと、ハッシュ値計算部１０５が求めたハッシュ値ｖとを用いて、暗号文の成分ｃ４として‘ｅ^ｕ×ｆ^（ｕｖ）’を求める。第２暗号文成分圧縮部１０７は、第２べき乗計算部１０６が求めた暗号文成分ｃ４でありトーラス上の元となっている暗号文成分ｃ４をアフィン表現である圧縮暗号文成分ｃ４＊に変換する。出力部は、暗号文（ｃ１,ｃ２，ｃ３*，ｃ４*）を出力する。ここで、乱数生成部１０１、第１べき乗計算部１０２及び乗算部１０３は第１暗号文生成部として機能し、ハッシュ値計算部１０５及び第２べき乗計算部１０６は第２暗号文生成部として機能している。
【００６５】
以上のように、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号においてトーラス圧縮を行う場合、本実施の形態における暗号化装置１００は、暗号文の４つの成分のうち、復号時に最初に演算を行う必要のない２つの暗号文成分ｃ３,ｃ４のみを圧縮すると、復号時の伸張にかかる処理時間を隠蔽できる。
【００６６】
＜復号装置の構成＞
次に、本実施の形態にかかる復号装置の備えるＣＰＵが記憶装置や外部記憶装置に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図１４は、本実施の形態にかかる復号装置の機能的構成を例示する図である。復号装置２００は、受信部（図示せず）と、ハッシュ計算部２０１と、暗号文成分伸張部２０２と、第１べき乗計算部２０３と、第２べき乗計算部２０４と、逆元計算部２０５と、第１乗算部２０６と、第２乗算部２０７と、第３乗算部２０８と、トーラス元検証部２０９と、正当性検証部２１０と、復号済み平文出力部２１１とを有する。これらの各部は、復号装置２００のＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものである。
【００６７】
復号装置２００は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)を受信する。受信部は、暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）を暗号化装置１００から受信する。ハッシュ計算部２０１は、暗号文成分ｃ１，ｃ２と、圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。尚、従来の復号装置はここでハッシュ計算を行う場合、暗号文成分ｃ１,ｃ２と共に暗号文成分ｃ３を用いていた。しかし、本実施の形態の復号装置２００は、暗号文成分ｃ３がアフィン表現に変換された圧縮暗号文成分ｃ３＊をハッシュ計算に用いる。
【００６８】
第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いて、係数ｋ１として‘ｃ１＾（ｘ１＋ｙ１×ｖ）’を求め、係数ｋ２として‘ｃ２＾（ｘ２＋ｙ２×ｖ）’を求める。第２乗算部２０７は、第２べき乗計算部２０４が求めた係数ｋ１及びｋ２を用いて、検査式に用いる検証用データｋとして‘ｋ１×ｋ２’を求める。暗号文成分伸張部２０２は、アフィン表現である圧縮暗号文成分ｃ３＊及びｃ４＊を各々伸張することにより、拡大体表現である暗号文成分ｃ３及びｃ４に各々変換する。第１べき乗計算部２０３は、暗号文成分ｃ１，ｃ２と、秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂ１として‘ｃ１＾ｚ１’を求め、係数ｂ２として‘ｃ２＾ｚ２’を求める。第１乗算部２０６は、第１べき乗計算部２０３が求めた係数ｂ１及びｂ２を用いて、係数ｂとして‘ｂ１×ｂ２’を求める。逆元計算部２０５は、第１乗算部２０６が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。第３乗算部２０８は、逆元計算部２０５が求めた中間データ‘ｂ＾（−１）’と、暗号文成分伸張部２０２が変換した暗号文成分ｃ３とを用いて、復号済みの平文ｍとして‘ｃ３×ｂ＾（−１）’を求める。
【００６９】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。具体的には、トーラス元検証部２０９は、各成分ｃ１，ｃ２，ｃ３＊，ｃ４＊が群Ｇ~の元であるか否か及び各成分ｃ１，ｃ２が群Ｇの元であるか否かを判定する。群Ｇの元であるか否かの判定は例えばｃ１，ｃ２をそれぞれＧの位数乗（ｑ乗）が‘１’（単位元）となっているかを確認することで確かめられる。尚、従来では、各成分ｃ１，ｃ２，ｃ３が群Ｇの元であるか否かを判定するが、ここでは、暗号文成分ｃ３が変換された圧縮暗号文成分ｃ３＊については、圧縮により群Ｇの元となっていることが明らかなため、ｃ３＊に関する判定を行わない。そして、トーラス元検証部２０９は、当該判定結果が肯定的である場合、暗号文は正当であるという検証結果を出力し、当該判定結果が否定的である場合、暗号文は正当ではないという検証結果を出力する。
【００７０】
正当性検証部２１０は、第２乗算部２０７が求めた検証用データｋと、暗号文成分伸張部２０２が変換した圧縮暗号文成分ｃ４とを比較する。ここでは、正当性検証部２１０は、この比較によりこれらが等価であるか否かを判定する。即ち、正当性検証部２１０は、検査式‘ｋ＝ｃ４’が成立するか否かを判定することにより、暗号文が正当であるか否かを検証する。そして、正当性検証部２１０は、当該検証結果を出力する。復号済み平文出力部２１１は、トーラス元検証部２０９が出力した検証結果と、正当性検証部２１０が出力した検証結果とが共に暗号文が正当であることを示す場合に、平文ｍを出力し、いずれか一方の検証結果が暗号文が正当でないことを示す場合に、エラーを出力する。なお、本実施の形態においては、第１べき乗計算部２０３、逆元計算部２０５及び第１乗算部２０６は中間データ生成部として機能し、ハッシュ値計算部２０１、第２べき乗計算部２０４及び第２乗算部２０７は検証用データ生成部として機能し、第３乗算部２０８は復号済み平文生成部として機能している。
【００７１】
以上のように、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号においてトーラス圧縮を行う場合、本実施の形態における復号装置２００は、暗号文の４つの成分のうち圧縮されている成分ｃ３,ｃ４のみを伸張して、平文を復号する。
【００７２】
（２）動作
＜暗号化処理＞
次に、本実施の形態にかかる暗号化装置１００の行う暗号化処理の手順について図１５を用いて説明する。暗号化装置１００は、公開鍵（ｑ，ｇ，ｇ~，ｅ，ｆ，ｈ）と、平文ｍとを予め取得しているものとする。暗号化装置１００は、乱数ｕを生成する（ステップＳ１）。次いで、暗号化装置１００は、公開鍵成分ｇ，ｇ~，ｈとを用いて、暗号文成分ｃ１として‘ｇ＾ｕ’を求め、暗号文成分ｃ２として‘ｇ~＾ｕ’を求め、係数ｂとして‘ｈ＾ｕ’を求める（ステップＳ２）。次いで、暗号化装置１００は、ステップＳ２で求めたｂと、平文ｍとを用いて、暗号文成分ｃ３として‘ｍ×ｂ’を求めることにより、平文マスクを行う（ステップＳ３）。そして、暗号化装置１００は、ステップＳ３で求めた暗号文成分ｃ３でありトーラス上の元となっている暗号文成分ｃ３をアフィン表現である圧縮暗号文成分ｃ３＊に変換する（ステップＳ４）。次いで、暗号化装置１００は、ステップＳ２で求めた暗号文成分ｃ１，ｃ２と、ステップＳ４で得られた圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ５）。続いて、暗号化装置１００は、公開鍵成分ｅ，ｆと、ステップＳ１で生成した乱数ｕと、ステップＳ５で求めたハッシュ値ｖとを用いて、暗号文の成分ｃ４として‘ｅ^ｕ×ｆ^（ｕｖ）’を求める（ステップＳ６）。そして、暗号化装置１００は、ステップＳ４が求めた暗号文成分ｃ４でありトーラス上の元となっている暗号文成分ｃ４をアフィン表現である圧縮暗号文成分ｃ４＊に変換する（ステップＳ７）。そして、暗号化装置１００は、暗号文（ｃ１,ｃ２，ｃ３*，ｃ４*）を復号装置２００に送信する。
【００７３】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００の行う復号処理の手順について図１６を用いて説明する。尚、復号装置２００は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ１, ｚ２)を予め取得しているものとする。復号装置２００は、暗号化装置１００から送信された暗号文（ｃ１，ｃ２，ｃ３＊，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。そして、復号装置２００は、暗号文が正当であると判定した場合（ステップＳ２０：ＹＥＳ）、次いで、暗号文成分ｃ１，ｃ２と、圧縮暗号文成分ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ２１）。
【００７４】
そして、復号装置２００は、ステップＳ２１で求めたハッシュ値ｖと、秘密鍵成分ｘ１, ｘ２, ｙ１, ｙ２とを用いて、係数ｋ１として‘ｃ１＾（ｘ１＋ｙ１×ｖ）’を求め、係数ｋ２として‘ｃ２＾（ｘ２＋ｙ２×ｖ）’を求める（ステップＳ２２）。次いで、復号装置２００は、検査式に用いる検証用データｋとして、‘ｋ１×ｋ２’を求める（ステップＳ２３）。
【００７５】
また、復号装置２００は、圧縮暗号文成分ｃ４＊を伸張し、拡大体表現である暗号文成分ｃ４を得る（ステップＳ２４）。また、復号装置２００は、ステップＳ２３で求めた検証用データｋとステップＳ２４で伸張した暗号文成分ｃ４とを用いて、検査式‘ｋ＝ｃ４’が成立するか否かを判定して、暗号文の正当性を検証する（ステップＳ２５）。そして、復号装置２００は、ステップＳ２５の検査式が成立する、即ち、暗号文が正当であると判定した場合（ステップＳ２５：ＹＥＳ）、暗号文成分ｃ１，ｃ２と、秘密鍵成分ｚ１，ｚ２とを用いて、係数ｂ１として‘ｃ１＾ｚ１’を求め、係数ｂ２として‘ｃ２＾ｚ２’を求める（ステップＳ２６）。次いで復号装置２００は、ステップＳ２６が求めた係数ｂ１及びｂ２を用いて、係数ｂとして‘ｂ１×ｂ２’を求める（ステップＳ２７）。その後、復号装置２００は、ステップＳ２７で求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める（ステップＳ２８）。また、復号装置２００は、圧縮暗号文成分ｃ３＊を伸張し、ｃ３を得る（ステップＳ２９）。そして、復号装置２００は、ステップＳ２８で求めた中間データ‘ｂ＾（−１）’と、ステップＳ２９で伸張したｃ３とを用いて、復号済みの平文ｍとして‘ｃ３×ｂ＾（−１）’を求める（ステップＳ３０）。ステップＳ２０及びステップＳ２５の判定結果が肯定的である場合には、復号装置２００は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ２０又はステップＳ２５の判定結果が否定的である場合、復号装置２００はエラーを出力し、復号済みの平文を出力しない。
【００７６】
尚、ステップＳ２０の処理と、ステップＳ２１〜Ｓ２３の処理と、ステップＳ２４の処理と、ステップＳ２６〜Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図６においては、各成分ｃ１,ｃ２,ｃ３＊,ｃ４＊が与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、伸張にかかる処理時間を隠蔽することができる。
【００７７】
即ち、上述したようにＣｒａｍｅｒ-Ｓｈｏｕｐ暗号の場合、暗号文が４つの成分の組になっており、これらの成分を独立に扱うことは非常に容易であることに注目し、並行処理が可能な環境では、暗号文成分を選択的に圧縮する。これにより、処理時間の増加分の一部を隠蔽することができる。従って、圧縮や伸張にかかる処理時間を隠蔽しつつ、Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号にトーラス圧縮を組み合わせた暗号化方式を実現することができる。
【００７８】
ただし、並行して処理を実行する場合には、ステップＳ２０の判定結果やステップＳ２５の判定結果が否定的となる不正な暗号文を取り除く機構が必要となる。このため、本実施の形態においては、図１４に示したように、復号装置２００が復号済み平文出力部２１１を有するように構成して、トーラス元検証部２０９の判定結果であるステップＳ２０の判定結果と、正当性検証部２１０の判定結果であるステップＳ２５の判定結果とを用いて、暗号文が正当であるか否かを最終的に判定する。復号装置２００は、ステップＳ３０で得られる復号済みの平文ｍを出力しないことにより、結果的に不正な暗号文を取り除くことができる。
【００７９】
なお、本発明においては、暗号化装置１００と復号装置２００との間でハッシュ関数の出力が同じであれば暗号化や復号は可能である。このため、上述のステップＳ５とステップＳ２１とでハッシュ値を求める際に用いられる成分と表現とが表現の変換を施すことなく同一であれば、圧縮する暗号文成分は限定されない。
【００８０】
また、本実施の形態において各演算は拡大体表現で行ったが、射影表現で行ってもよい。ただし、射影表現では同じデータに対し複数の値を取り得るので、ハッシュ関数への入力や復号済みの平文を導出する際や正当性検証部２１０で等価性の判定を行う際に注意が必要である。
【００８１】
[第４の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００８２】
（１）構成
米国特許文献 ＵＳＰ７，２２１，７５８Ｂ２にＣｒａｍｅｒ−Ｓｈｏｕｐ暗号において暗号化方式のバリエーションが記載されており、この方式を用いると秘密鍵成分の個数を削減できる。このバリエーションに対しても、暗号文成分の一部を圧縮する構成を適用することが可能である。本実施の形態は、秘密鍵成分ｚ１,ｚ２の代わりにｚひとつで暗号化や復号を行うものである。
【００８３】
ここで、本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図１７を用いて説明する。鍵生成装置は、公開鍵ｇ（ｇ∈Ｇ）を拡大体表現から選択し、０以外の乱数ｗを生成する（ＧＳ１１）。次いで、鍵生成装置は、秘密鍵成分ｘ１,ｘ２,ｙ１,ｙ２,ｚとして各々乱数を生成する（ＧＳ１２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ１×ｇ~^ｘ２’を求め、公開鍵成分ｆとして‘ｇ^ｙ１×ｇ~^ｙ２’を求め、公開鍵成分ｈとして‘ｇ^ｚ’を求める（ＧＳ１３）。そして、鍵生成装置は、秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００８４】
暗号化装置１００の構成は上述の第３の実施の形態と同様であるため、その説明を省略する。図１８は本実施の形態にかかる復号装置２００´の機能的構成を例示する図である。
本実施の形態にかかる復号装置２００´の機能的構成が上述の第３の実施の形態の復号装置２００の機能的構成と異なる点は以下の通りである。復号装置２００´には秘密鍵（ｘ１,ｘ２,ｙ１,ｙ２,ｚ）が入力される。復号装置２００´は、第１乗算部２０６を有さない。第１べき乗計算部２０３は、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。なお、本実施の形態においては第１べき乗計算部２０３及び逆元計算部２０５が中間データ生成部として機能している。
【００８５】
（２）動作
＜復号処理＞
次に、本実施の形態にかかる復号装置２００´の行う復号処理の手順について図１９を用いて説明する。尚、暗号化装置１００の行う暗号化処理の手順は上述の第３の実施の形態と同様であるため、その説明を省略する。復号装置２００´は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ１, ｘ２, ｙ１, ｙ２, ｚ)を予め取得しているものとする。ステップＳ２０〜Ｓ２５は上述の第１の実施の形態と同様である。ステップＳ４０では、復号装置２００´は、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。次いで、ステップＳ２８では、復号装置２００´は、ステップＳ４０が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。Ｓ２９〜Ｓ３０の処理は上述の第３の実施の形態と同様である。
【００８６】
本実施の形態においては、ステップＳ２０の処理と、ステップＳ２１〜Ｓ２３の処理と、ステップＳ２４の処理と、ステップＳ４０，Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図１９においては、各成分ｃ１,ｃ２,ｃ３＊,ｃ４＊が与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号において本実施の形態のようにして秘密鍵成分の個数を削減した場合であっても、伸張にかかる処理時間を隠蔽することができる。
【００８７】
また本実施の形態においては複数の暗号文成分のうちｃ３を圧縮したが、ｃ１やｃ２を圧縮し、ｃ１ｃ２を圧縮している間にｃ３を生成すれば暗号化処理においても圧縮にかかる処理時間を隠蔽できる。どの暗号文成分を圧縮するかによって、暗号化、復号、あるいはその両方の圧縮にかかる処理時間や伸張にかかる処理時間を隠蔽できるのかが決まる。
【００８８】
[第５の実施の形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００８９】
（１）構成
上述の第４の実施の形態においては、秘密鍵成分ｚ１,ｚ２の代わりにｚを用いて秘密鍵成分の個数を削減した。ここでは秘密鍵成分の個数を更に削減して、秘密鍵成分ｘ１,ｘ２の代わりにｘを用い、秘密鍵成分ｙ１,ｙ２の代わりにｙを用いる。ただし、公開鍵の生成に用いられた乱数ｗが秘密鍵成分として加わる。また、ここでは圧縮する対象の暗号文成分がｃ３，ｃ４のみならずｃ２も含む場合について説明する。
【００９０】
ここで、本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要について図２０を用いて説明する。鍵生成装置は、公開鍵成分ｇ（ｇ∈Ｇ）を拡大体表現から選択し、‘０’以外の乱数ｗを生成する（ＧＳ２１）。次いで、鍵生成装置は、秘密鍵成分ｘ,ｙ,ｚとして各々乱数を生成する（ＧＳ２２）。そして、鍵生成装置は、公開鍵成分ｇ~として‘ｇ^ｗ’を求め、公開鍵成分ｅとして‘ｇ^ｘ’を求め、公開鍵成分fとして‘ｇ^ｙ’を求め、公開鍵成分ｈとして‘ｇ^ｚ’を求める（ＧＳ２３）。そして、鍵生成装置は、秘密鍵（ｘ,ｙ,ｚ，ｗ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【００９１】
次に、本実施の形態にかかる暗号化装置１００´の機能的構成について図２１を用いて説明する。暗号化装置１００´の機能的構成が上述の第３の実施の形態の暗号化装置１００の機能的構成と異なる点は以下の通りである。暗号文成分圧縮部１０４は、第１べき乗計算部１０２が求めた暗号文成分ｃ２と、乗算部１０３が求めた暗号文成分ｃ３とを圧縮することによりアフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊に各々変換する。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１と、暗号文成分圧縮部１０４が変換した圧縮暗号文成分ｃ２＊及びｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。出力部は、暗号文（ｃ１,ｃ２*，ｃ３*，ｃ４*）を復号装置２００”に送信する。
【００９２】
次に、本実施の形態にかかる復号装置２００”の機能的構成について図２２を用いて説明する。本実施の形態にかかる復号装置２００”の機能的構成が上述の第３の実施の形態の復号装置２００の機能的構成と異なる点は以下の通りである。復号装置２００”は、第１乗算部２０６と、第２乗算部２０７とを有さず、第３べき乗計算部２１２を更に有する。復号装置２００”には秘密鍵（ｘ,ｙ,ｚ，ｗ）が入力される。受信部は、暗号文（ｃ１,ｃ２*，ｃ３*，ｃ４*）を暗号化装置１００´から受信する。暗号文成分伸張部２０２は、アフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊，ｃ４＊を各々伸張することにより、拡大体表現である暗号文成分ｃ２，ｃ３，ｃ４に各々変換する。第１べき乗計算部２０３は、上述の第２の実施の形態と同様にして、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を求める。ハッシュ計算部２０１は、暗号文成分ｃ１と、圧縮暗号文成分ｃ２＊，ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙとを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める。第３べき乗計算部２１２は、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める。
【００９３】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２＊，ｃ３＊，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。即ち、トーラス元検証部２０９は、暗号文成分ｃ１と、圧縮暗号文成分ｃ２＊，ｃ３＊，ｃ４＊とが群Ｇ~の元であるか否か及び各成分ｃ１が群Ｇの元であるか否かを判定し、当該判定結果を出力する。尚、圧縮暗号文成分ｃ２＊,ｃ３＊については、圧縮により群Ｇの元となっていることが明らかなため、ここではその判定を行わない。正当性検証部２１０は、第３べき乗計算部２１２が求めた検証用データｋ１と暗号文成分ｃ２とを用いて検査式１‘ｋ１＝ｃ２’が成立するか否かを判定すると共に、第２べき乗計算部２０４が求めた検証用データｋ２と成分ｃ４とを用いて検査式２‘ｋ２＝ｃ４’が成立するか否かを判定する。なお、本実施の形態においてはハッシュ値計算部２０１、第２べき乗計算部２０４及び第３べき乗計算部２１２が検証用データ生成部として機能している。
【００９４】
（２）動作
＜暗号化処理＞
本実施の形態にかかる暗号化装置１００´の行う暗号化処理の手順について図２３を用いて説明する。ステップＳ１〜Ｓ３の処理は上述の第３の実施の形態と同様である。ステップＳ５０では、暗号化装置１００´は、ステップＳ２で求めた暗号文成分ｃ２と、ステップＳ３で求めた暗号文成分ｃ３とをアフィン表現である圧縮暗号文成分ｃ２＊，ｃ３＊に各々変換する。次いで、暗号化装置１００´は、ステップＳ２で求めたｃ１と、ステップＳ５０で変換した圧縮暗号文成分ｃ２＊及びｃ３＊とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ５１）。ステップＳ６〜Ｓ７の処理は上述の第１の実施の形態と同様である。そして、暗号化装置１００´は、暗号文（ｃ１,ｃ２＊，ｃ３＊，ｃ４＊）を復号装置２００”に送信する。
【００９５】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００”の行う復号処理の手順について図２４を用いて説明する。復号装置２００”は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ, ｙ, ｚ，ｗ)を予め取得しているものとする。復号装置２００”は、暗号化装置１００´から送信された暗号文（ｃ１，ｃ２＊，ｃ３＊，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。そして、復号装置２００”は、暗号文が正当であると判定した場合（ステップＳ６０：ＹＥＳ）、次いで、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める（ステップＳ６１）。次いで、復号装置２００”は、暗号文成分ｃ１と圧縮暗号文成分ｃ２＊，ｃ３＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ６２）。そして、復号装置２００”は、ステップＳ６２で求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙと、暗号文成分ｃ１とを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める（ステップＳ６３）。また、復号装置２００”は、圧縮暗号文成分ｃ２＊，ｃ４＊を伸張することにより、拡大体表現である暗号文成分ｃ２，ｃ４に各々変換する（ステップＳ６４）。そして、復号装置２００”は、検査式１‘ｋ１＝ｃ２’及び検査式２‘ｋ２＝ｃ４’が成立するか否かを判定する（ステップＳ６５）。双方の検査式が成立する場合（ステップＳ６５：ＹＥＳ）、上述の第４の実施の形態と同様にして、ステップＳ４０の処理を行う。ステップＳ２８〜Ｓ３０の処理は上述の第３の実施の形態と同様である。ステップＳ６０及びステップＳ６５の判定結果が肯定的である場合には、復号装置２００”は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ６０又はステップＳ６５の判定結果が否定的である場合、復号装置２００”はエラーを出力し、復号済みの平文を出力しない。
【００９６】
本実施の形態においては、ステップＳ６０の処理と、ステップＳ６１の処理と、ステップＳ６２〜Ｓ６３の処理と、ステップＳ６４の処理と、ステップＳ４０，Ｓ２８の処理と、ステップＳ２９との処理とを並行して行うことができる。即ち、図１４においては、暗号文成分ｃ１，ｃ４と、圧縮暗号文ｃ２＊，ｃ３＊とが与えられたときに、破線で囲まれた各部分は即座に並行して実行することができる。また第１グループ、第２グループ及び第３グループはそれぞれ独立して処理を行うことができるため、これらの各グループの処理も並行して実行することが可能となる。このため、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号において本実施の形態のようにして秘密鍵成分の個数を削減した場合であっても、伸張にかかる処理時間を隠蔽することができる。
【００９７】
[第６の実施形態]
次に、暗号化装置、復号装置、暗号文検証装置、暗号化方法、復号方法及びプログラムの第６の実施の形態について説明する。なお、上述の第１の実施の形態乃至第５の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００９８】
上述の第１の実施の形態で説明した暗号文検証装置２０の正当性検証部２５や、第３の実施の形態乃至第５の実施の形態において説明した復号装置の正当性検証部２１０では、圧縮暗号成分が拡大体表現に伸張された後の暗号文成分を用いて、暗号文の正当性の検証を行った、しかし、異なる表現間で暗号文成分の同一性が判定できる場合、圧縮暗号文成分の伸張が不要となる場合がある。本実施の形態においてはその一例を説明する。尚、本実施の形態にかかる暗号方式は第５の実施の形態と同じであるものとし、圧縮する対象の暗号文成分はｃ２とｃ４とであるものとする。
【００９９】
本実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理は第５の実施の形態と同一であるので省略するが、鍵生成装置は秘密鍵（ｘ,ｙ,ｚ，ｗ）と公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）とを出力する。
【０１００】
次に、本実施の形態にかかる暗号化装置１００”の機能的構成について図２５を用いて説明する。暗号化装置１００”の機能的構成が上述の第５の実施の形態の暗号化装置１００´の機能的構成と異なる点は以下の通りである。暗号文成分圧縮部１０４は、第１べき乗計算部１０２が求めた暗号文成分ｃ２をアフィン表現である暗号文成分ｃ２＊に変換する。ハッシュ値計算部１０５は、第１べき乗計算部１０２が求めた暗号文成分ｃ１と、第１の暗号文成分圧縮部１０４が圧縮した圧縮暗号文成分ｃ２＊と、乗算部１０３が求めた暗号文成分ｃ３とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める。出力部は、暗号文（ｃ１,ｃ２*，ｃ３，ｃ４*）を復号装置２００’’’に送信する。
【０１０１】
次に、本実施の形態にかかる復号装置２００’’’の機能的構成について図２６を用いて説明する。本実施の形態にかかる復号装置２００’’’の機能的構成が上述の第５の実施の形態の復号装置２００”の機能的構成と異なる点は以下の通りである。復号装置２００’’’は、暗号文成分伸張部２０２を有さない。復号装置２００’’’には秘密鍵（ｘ,ｙ,ｚ，ｗ）が入力される。受信部は、圧縮暗号文（ｃ１,ｃ２*，ｃ３，ｃ４*）を暗号化装置１００”から受信する。第１べき乗計算部２０３は、上述の第５の実施の形態と同様にして、暗号文成分ｃ１と、秘密鍵成分ｚとを用いて、係数ｂとして‘ｃ１＾ｚ’を求める。逆元計算部２０５は、第１べき乗計算部２０３が求めた係数ｂの逆元‘ｂ＾（−１）’を中間データとして求める。ハッシュ計算部２０１は、暗号文成分ｃ１，ｃ３と、圧縮暗号文成分ｃ２＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める。第２べき乗計算部２０４は、ハッシュ計算部２０１が求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙとを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める。第３べき乗計算部２１２は、乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める。
【０１０２】
トーラス元検証部２０９は、暗号文（ｃ１，ｃ２＊，ｃ３，ｃ４＊）の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する。即ち、トーラス元検証部２０９は、各成分ｃ１，ｃ２＊，ｃ３，ｃ４＊が群Ｇの元であるか否か及び各成分ｃ１，ｃ３が群Ｇの元であるか否かを判定し、当該判定結果を出力する。尚、圧縮暗号文成分ｃ２＊については、圧縮により群Ｇの元となっていることが明らかなため、ここではその判定を行わない。正当性検証部２１０は、第３べき乗計算部２１２が求めた検証用データｋ１と圧縮暗号文成分ｃ２＊とを用いてｋ１とｃ２＊とが等価であるか否かを判定すると共に、第２べき乗計算部２０４が求めた検証用データｋ２と圧縮暗号文成分ｃ４＊とを用いてｋ２とｃ４＊とが等価であるか否かを判定することにより、暗号文の正当性を検証する。即ち、本実施の形態においては、正当性検証部２１０は、圧縮暗号文成分ｃ２＊，ｃ４＊が伸張された拡大体表現である暗号文成分ｃ２，ｃ４を用いるのではなく、圧縮暗号文成分ｃ２＊，ｃ４＊自体を用いて、暗号文の正当性を検証する。なお、本実施の形態においては、第１べき乗計算部２０３、逆元計算部２０５及び第３乗算部２０８が復号済み平文生成部として機能している。
【０１０３】
（２）動作
＜暗号化処理＞
本実施の形態にかかる暗号化装置１００”の行う暗号化処理の手順について図２７を用いて説明する。ステップＳ１〜Ｓ３の処理は上述の第５の実施の形態と同様である。ステップＳ７０では、暗号化装置１００”は、ステップＳ２で求めた暗号文成分ｃ２をアフィン表現である圧縮暗号文成分ｃ２＊に変換する。次いで、暗号化装置１００”は、ステップＳ２で求めた暗号文成分ｃ１と、ステップＳ７０で変換した圧縮暗号文成分ｃ２＊と、ステップＳ３で生成した暗号文成分ｃ３とを用いてハッシュ関数による計算を行ってハッシュ値ｖを求める（ステップＳ７１）。ステップＳ６〜Ｓ７の処理は上述の第５の実施の形態と同様である。そして、暗号化装置１００”は、暗号文（ｃ１,ｃ２＊，ｃ３，ｃ４＊）を復号装置２００に送信する。
【０１０４】
＜復号処理＞
次に、本実施の形態にかかる復号装置２００’’’の行う復号処理の手順について図２８を用いて説明する。復号装置２００’’’は、公開鍵（ｑ，ｇ,ｇ~,ｅ,ｆ,ｈ）に対応する秘密鍵(ｘ, ｙ, ｚ，ｗ)を予め取得しているものとする。復号装置２００’’’は、暗号化装置１００”から送信された圧縮暗号文（ｃ１，ｃ２＊，ｃ３，ｃ４＊）を受信すると、上述の構成欄で具体的に説明したように、圧縮暗号文の各成分が正しい群の元となっているか否かを検査して、暗号文の正当性を検証する（ステップＳ８０）。そして、復号装置２００’’’は、暗号文が正当であると判定した場合（ステップＳ８０：ＹＥＳ）、次いで、第５の実施の形態と同様に乱数ｗと暗号文成分ｃ１とを用いて、検証用データｋ１として‘ｃ１＾ｗ’を求める（ステップＳ６１）。次いで、復号装置２００’’’は、暗号文成分ｃ１，ｃ３と、圧縮暗号文ｃ２＊とを用いてハッシュ関数による計算を行って、ハッシュ値ｖを求める（ステップＳ８１）。そして、復号装置２００’’’は、ステップＳ８１で求めたハッシュ値ｖと、秘密鍵成分ｘ,ｙと、暗号文成分ｃ１とを用いて、検証用データｋ２として‘ｃ１＾（ｘ＋ｙ×ｖ）’を求める（ステップＳ６３）。また、復号装置２００’’’は、検証用データｋ１とｃ圧縮暗号文成分ｃ２＊とが等価であるか否か及び検証用データｋ２と圧縮暗号文成分ｃ４＊とが等価であるか否かを判定する（ステップＳ８２）。双方とも同値である場合（ステップＳ８２：ＹＥＳ）、上述の第５の実施の形態と同様にして、復号装置２００’’’は、ステップＳ４０、ステップ２８の処理を行い、ステップ２８の計算の結果得られた中間データと暗号文成分ｃ３とを用いて‘ｍ＝ｂ＾（−１）・ｃ３’を計算して（ステップＳ３０）、復号済み平文ｍを得る。ステップＳ８０及びステップＳ８２の判定結果が肯定的である場合には、復号装置２００’’’は、ステップＳ３０で求めた復号済みの平文を出力することになる。ステップＳ８０又はステップＳ８２の判定結果が否定的である場合、復号装置２００’’’はエラーを出力し、復号済みの平文を出力しない。
【０１０５】
以上のようにして、異なる表現間で暗号文成分の同一性が判定できる場合、圧縮暗号文成分の伸張を行わないことにより、伸張にかかる処理時間を削減することができる。
【０１０６】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成成分を変形して具体化できる。また、前記実施形態に開示されている複数の構成成分の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成成分から幾つかの構成成分を削除してもよい。さらに、異なる実施形態にわたる構成成分を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【０１０７】
＜変形例１＞
上述した各実施の形態において、暗号化装置１０で各々実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成しても良い。暗号化装置１０´、１００、１００´，１００”，復号装置３０，２００，２００´，２００”、２００’’’及び暗号文検証装置２０で各々実行される各種プログラムについても同様である。
【０１０８】
また、上述した実施の形態において、暗号化装置１０の有する各部は、ＣＰＵのプログラム実行時にＲＡＭなどの記憶装置上に生成されるものとしたが、これらの全部又は一部をハードウェアにより構成するようにしても良い。暗号化装置１０´、１００、１００´，１００”，復号装置３０，２００，２００´，２００”、２００’’’ 及び暗号文検証装置２０の有する各部についても同様である。
【０１０９】
また、上述の各実施の形態の暗号化装置及び復号装置においては、べき乗計算及び乗算をべき乗計算部及び乗算部が各々行うように構成したが、べき乗計算部及び乗算部を１つの計算部として取り扱い、計算部がべき乗計算及び乗算を行うように構成しても良い。
【０１１０】
＜変形例２＞
上述の第４の実施の形態においては、暗号化装置１００は、暗号文成分のうちｃ３,ｃ４のみならずｃ２を圧縮するように構成したが、第３の実施の形態と同様にして、暗号文成分ｃ３,ｃ４のみを圧縮するようにしても良い。
【０１１１】
また、各実施の形態においては、圧縮する対象の暗号文成分の数は、２つ又は３つに限らず１つであっても４つであっても良い。また、いずれの暗号文成分を圧縮するかは上述の例に限らない。
【０１１２】
尚、第３の実施の形態乃至第６の実施の形態においては、暗号文は（ｃ１，ｃ２，ｃ３，ｃ４）の４つの暗号文成分を含むように構成したが、暗号文成分の数はこれに限らない。
【０１１３】
また、上述の第３の実施の形態乃至第６の実施の形態の暗号化処理においては、ハッシュ値ｖと公開鍵成分とを用いて暗号文成分ｃ４を求める方法としてべき乗計算を行うこととしたが、その方法はべき乗計算に限らない。
【図面の簡単な説明】
【０１１４】
【図１】有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式で複数の暗号文成分を含む暗号文の正当性を検証する基本的な構成を例示する図である。
【図２】第１の実施の形態にかかる暗号化装置の機能的構成を例示する図である。
【図３】同実施の形態にかかる暗号文検証装置の機能的構成を例示する図である。
【図４】同実施の形態にかかる暗号化装置１０の行う暗号化処理の手順を示すフローチャートである。
【図５】同実施の形態にかかる暗号文検証装置２０の行う暗号文検証処理の手順を示すフローチャートである。
【図６】ＥｌＧａｍａｌ暗号において平文ｍを暗号化して暗号文を生成する暗号化装置と暗号文を復号する復号装置とを例示する図である。
【図７】第２の実施の形態にかかる暗号化装置の機能的構成を例示する図である。
【図８】同実施の形態にかかる復号装置の機能的構成を例示する図である。
【図９】同実施の形態にかかる暗号化装置１０´の行う暗号化処理の手順を示すフローチャートである。
【図１０】同実施の形態にかかる復号装置３０の行う暗号化処理の手順を示すフローチャートである。
【図１１】Ｃｒａｍｅｒ-Ｓｈｏｕｐ暗号スキームの基本的な構成を例示する図である。
【図１２】第３の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図１３】同実施の形態にかかる暗号化装置１００の機能的構成を例示する図である。
【図１４】同実施の形態にかかる復号装置２００の機能的構成を例示する図である。
【図１５】同実施の形態にかかる暗号化装置１００の行う暗号化処理の手順を示すフローチャートである。
【図１６】同実施の形態にかかる復号装置２００の行う復号処理の手順を示すフローチャートである。
【図１７】第４の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図１８】同実施の形態にかかる復号装置２００´の機能的構成を例示する図である。
【図１９】同実施の形態にかかる復号装置２００´の行う復号処理の手順を示すフローチャートである。
【図２０】第５の実施の形態にかかる鍵生成装置が公開鍵及び秘密鍵を生成する鍵生成処理の概要を例示する図である。
【図２１】同実施の形態にかかる暗号化装置１００の機能的構成を例示する図である。
【図２２】同実施の形態にかかる復号装置２００”の機能的構成を例示する図である。
【図２３】同実施の形態にかかる暗号化装置１００の行う暗号化処理の手順を示すフローチャートである。
【図２４】同実施の形態にかかる復号装置２００”の行う復号処理の手順を示すフローチャートである。
【図２５】第６の実施の形態にかかる暗号化装置１００”の機能的構成を例示する図である。
【図２６】同実施の形態にかかる復号装置２００’’’の機能的構成を例示する図である。
【図２７】同実施の形態にかかる暗号化装置１００”の行う暗号化処理の手順を示すフローチャートである。
【図２８】同実施の形態にかかる復号装置２００’’’の行う復号処理の手順を示すフローチャートである。
【符号の説明】
【０１１５】
１０，１０´，１００，１００´,１００” 暗号化装置
１１ 平文受信部
１２ 公開鍵受信部
１３ 第１暗号文生成部
１４ 暗号文成分圧縮部
１５ 第１暗号文生成部
１６ 暗号文出力部
２０ 暗号文検証装置
２１ 暗号文受信部
２２ 秘密鍵受信部
２３ 中間データ生成部
２４ 暗号文成分伸張部
２５ 正当性検証部
２６ 検証結果出力部
３０ 復号装置
３１ 暗号文受信部
３２ 秘密鍵受信部
３３ 中間データ生成部
３４ 暗号文成分伸張部
３５ 復号済み平文生成部
３６ 復号済み平文出力部
１０１ 乱数生成部
１０２ 第１べき乗計算部
１０３ 乗算部
１０４ 暗号文成分圧縮部
１０５ ハッシュ値計算部
１０６ 第２べき乗計算部
１０７ 第２暗号文成分圧縮部
２００,２００´，２００”，２００’’’ 復号装置
２０１ ハッシュ計算部
２０２ 圧縮暗号文成分伸張部
２０３ 第１べき乗計算部
２０４ 第２べき乗計算部
２０５ 逆元計算部
２０６ 第１乗算部
２０７ 第２乗算部
２０８ 第３乗算部
２０９ トーラス元検証部
２１０ 正当性検証部
２１１ 復号済み平文出力部
２１２ 第３べき乗計算部
【特許請求の範囲】
【請求項１】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、
平文を受信する平文受信部と、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する暗号文成分生成部と、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮部と、
受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、
少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力部とを備える
ことを特徴とする暗号化装置。
【請求項２】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、
平文を受信する平文受信部と、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成部と、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮部と、
受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、
前記第２の暗号文成分のうち少なくとも１つ以上を圧縮して、第２の圧縮暗号文成分を得る第２暗号文成分圧縮部と、
少なくとも前記第１の圧縮暗号文成分と第２の圧縮暗号文成分とを含む暗号文を出力する暗号文出力部とを備える
ことを特徴とする暗号化装置。
【請求項３】
前記第２暗号文生成部は、
少なくとも１つ以上の前記第１の圧縮暗号文成分を用いてハッシュ値を計算するハッシュ計算部と、
前記ハッシュ値を用いて前記第２の暗号文成分を生成する生成部とを有する
ことを特徴とする請求項１又は２に記載の暗号化装置。
【請求項４】
前記暗号文は、復号時に平文の生成に用いる平文生成用暗号文成分又は前記平文生成用暗号文を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮平文生成用暗号文成分と、復号時に平文の生成と暗号文の正当性の検証とに用いる総合暗号文成分又は前記総合暗号文成分を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮総合暗号文成分と、復号時に暗号文の正当性の検証に用いる検証用暗号文成分又は前記検証用暗号文成分を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮検証用暗号文成分とを含み、
前記第１の暗号文成分は、前記平文生成用暗号文成分と、前記総合暗号文成分とを少なくとも含み、
前記第１暗号文生成部は、前記公開鍵を用いたべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵を用いたべき乗算を行うことにより前記総合暗号文成分を計算し、
前記ハッシュ値計算部は、前記平文生成用暗号文成分又は前記圧縮平文生成用暗号文成分と、前記総合暗号文成分又は前記圧縮総合暗号文成分とを少なくとも用いてハッシュ値を計算し、
前記生成部は、前記ハッシュ値と前記公開鍵とを用いて、乗算とべき乗算とを行うことにより、前記検証用暗号文成分を含む前記第２の暗号文成分を生成する
ことを特徴とする請求項３に記載の暗号化装置。
【請求項５】
前記第１暗号文生成部は、
乱数を生成する乱数生成部と、
前記公開鍵に含まれる第１の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵に含まれる第２の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより前記総合暗号文成分を計算する計算部とを有し、
前記生成部は、前記公開鍵に含まれる第３の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第２の暗号化係数を計算し、前記公開鍵に含まれる第４の公開鍵成分を用いてべき指数が前記乱数と前記ハッシュ値との積であるべき乗算を行うことにより第３の暗号化係数を計算し、前記第２の暗号化係数と前記第３の暗号化係数とを乗算することにより、前記検証用暗号文成分を含む前記第２の暗号文成分を生成する
ことを特徴とする請求項４に記載の暗号化装置。
【請求項６】
前記計算部は、前記公開鍵に含まれる第１の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵に含まれる少なくとも２つの第２の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を各々行うことにより、少なくとも２つの前記総合暗号文成分を計算する
ことを特徴とする請求項５に記載の暗号化装置。
【請求項７】
前記第１暗号文成分圧縮部は、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、アフィン表現で表現された第１の圧縮暗号文成分を得る
ことを特徴とする請求項１乃至６のいずれか一項に記載の暗号化装置。
【請求項８】
前記第２暗号文成分圧縮部は、前記第２の暗号文成分のうち少なくとも１つ以上を圧縮して、アフィン表現で表現された第２の圧縮暗号文成分を得る
ことを特徴とする請求項２乃至７のいずれか一項に記載の暗号化装置。
【請求項９】
前記第１暗号文成分圧縮部と前記第２暗号文生成部とは並行して動作可能である
ことを特徴とする請求項２乃至８のいずれか一項に記載の暗号化装置。
【請求項１０】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、
前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成部と、
復号済みの前記平文を出力する復号済み平文出力部とを備える
ことを特徴とする復号装置。
【請求項１１】
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記検証用データと前記検証用暗号文成分の少なくとも一部を用いて前記暗号文の正当性を検証する正当性検証部とを更に備え、
前記復号済み平文出力部は、前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が正当ではない旨を出力する
ことを特徴とする請求項１０に記載の復号装置。
【請求項１２】
前記暗号文は、前記平文の生成に用いる暗号文成分である平文生成用暗号文成分又は前記平文生成用暗号文成分を圧縮した圧縮平文生成用暗号文成分と、前記平文の生成と前記暗号文の正当性の検証とに用いる暗号文成分である総合暗号文成分又は前記総合暗号文成分を圧縮した圧縮総合暗号文成分と、前記暗号文の正当性の検証に用いる暗号文成分である検証用暗号文成分又は前記検証用暗号文成分を圧縮した圧縮検証用暗号文成分とを含む４つの暗号文成分を含み、
前記中間データ生成部は、
前記平文生成用暗号文成分又は前記圧縮平文生成用暗号文成分と、前記総合暗号文成分又は前記圧縮総合暗号文成分とを少なくとも用いてハッシュ値を計算するハッシュ値計算部と、
前記ハッシュ値と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて前記中間データを生成する生成部とを有する
ことを特徴とする請求項１０又は１１に記載の復号装置。
【請求項１３】
前記暗号文成分伸張部は、前記圧縮暗号文成分を演算可能な表現である拡大体表現又は射影表現で表現した伸張済み圧縮暗号分成分に伸張する
ことを特徴とする請求項１０乃至１２のいずれか一項に記載の復号装置。
【請求項１４】
前記正当性検証部は、前記検証用データと、前記検証用暗号文成分又は前記圧縮検証用暗号文成分との等価性を検証することにより、前記暗号文の正当性を検証する
ことを特徴とする請求項１２に記載の復号装置。
【請求項１５】
前記ハッシュ値計算部、前記暗号文成分伸張部、前記検証用データ生成部及び前記復号済み平文生成部は並列に動作可能である
ことを特徴とする請求項１２乃至１４のいずれか一項に記載の復号装置。
【請求項１６】
前記ハッシュ値計算部、前記暗号文成分伸張部、前記検証用データ生成部、前記復号済み平文生成部及び前記生成部は並列に動作可能である
ことを特徴とする請求項１２乃至１４のいずれか一項に記載の復号装置。
【請求項１７】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、
前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が不正である旨を出力する復号済み平文出力部とを備える
ことを特徴とする復号装置。
【請求項１８】
前記暗号文は、前記平文の生成に用いる平文生成用暗号文成分と、前記平文の生成と前記暗号文の正当性の検証に用いる総合暗号文成分と、前記暗号文の正当性の検証に用いる検証用暗号文成分又は前記検証用暗号文成分を圧縮した圧縮検証用暗号文成分とを含む４つの暗号文成分を含み、
前記検証用データ生成部は、
前記平文生成用暗号文成分と、前記総合暗号文成分とを少なくとも用いて、ハッシュ値を計算するハッシュ値計算部と、
前記ハッシュ値と受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記検証用データを生成する生成部とを有する
ことを特徴とする請求項１７に記載の復号装置。
【請求項１９】
各前記暗号文成分が正しくトーラスの元となっているか否かを検証するトーラス元検証部を更に備える
ことを特徴とする請求項１０乃至１８のいずれか一項に記載の復号装置。
【請求項２０】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文正当性検証装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、
前記圧縮暗号文成分の表現を演算可能な表現である伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて前記暗号文の正当性を検証する正当性検証部と、
前記正当性検証部の検証結果を出力する検証結果出力部とを備える
ことを特徴とする暗号文検証装置。
【請求項２１】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文検証装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、
前記正当性検証部の検証結果を出力する検証結果出力部とを備える
ことを特徴とする暗号文検証装置。
【請求項２２】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置で実行される暗号化方法であって、
平文を受信する平文受信ステップと、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信ステップと、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成ステップと、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮ステップと、
受信された平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成ステップと、
少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力ステップとを含む
ことを特徴とする暗号化方法。
【請求項２３】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置で実行される復号方法であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信ステップと、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信ステップと、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて復号に必要な中間データを生成する中間データ生成ステップと、
前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張ステップと、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成ステップと、
復号済みの前記平文を出力する復号済み平文出力ステップとを含む
ことを特徴とする復号方法。
【請求項２４】
請求項２２又は２３に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、
平文を受信する平文受信部と、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する暗号文成分生成部と、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮部と、
受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、
少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力部とを備える
ことを特徴とする暗号化装置。
【請求項２】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置であって、
平文を受信する平文受信部と、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信部と、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成部と、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮部と、
受信された前記平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成部と、
前記第２の暗号文成分のうち少なくとも１つ以上を圧縮して、第２の圧縮暗号文成分を得る第２暗号文成分圧縮部と、
少なくとも前記第１の圧縮暗号文成分と第２の圧縮暗号文成分とを含む暗号文を出力する暗号文出力部とを備える
ことを特徴とする暗号化装置。
【請求項３】
前記第２暗号文生成部は、
少なくとも１つ以上の前記第１の圧縮暗号文成分を用いてハッシュ値を計算するハッシュ計算部と、
前記ハッシュ値を用いて前記第２の暗号文成分を生成する生成部とを有する
ことを特徴とする請求項１又は２に記載の暗号化装置。
【請求項４】
前記暗号文は、復号時に平文の生成に用いる平文生成用暗号文成分又は前記平文生成用暗号文を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮平文生成用暗号文成分と、復号時に平文の生成と暗号文の正当性の検証とに用いる総合暗号文成分又は前記総合暗号文成分を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮総合暗号文成分と、復号時に暗号文の正当性の検証に用いる検証用暗号文成分又は前記検証用暗号文成分を前記第１の暗号文成分圧縮部あるいは前記第２の暗号文成分圧縮部で圧縮した圧縮検証用暗号文成分とを含み、
前記第１の暗号文成分は、前記平文生成用暗号文成分と、前記総合暗号文成分とを少なくとも含み、
前記第１暗号文生成部は、前記公開鍵を用いたべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵を用いたべき乗算を行うことにより前記総合暗号文成分を計算し、
前記ハッシュ値計算部は、前記平文生成用暗号文成分又は前記圧縮平文生成用暗号文成分と、前記総合暗号文成分又は前記圧縮総合暗号文成分とを少なくとも用いてハッシュ値を計算し、
前記生成部は、前記ハッシュ値と前記公開鍵とを用いて、乗算とべき乗算とを行うことにより、前記検証用暗号文成分を含む前記第２の暗号文成分を生成する
ことを特徴とする請求項３に記載の暗号化装置。
【請求項５】
前記第１暗号文生成部は、
乱数を生成する乱数生成部と、
前記公開鍵に含まれる第１の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵に含まれる第２の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより前記総合暗号文成分を計算する計算部とを有し、
前記生成部は、前記公開鍵に含まれる第３の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第２の暗号化係数を計算し、前記公開鍵に含まれる第４の公開鍵成分を用いてべき指数が前記乱数と前記ハッシュ値との積であるべき乗算を行うことにより第３の暗号化係数を計算し、前記第２の暗号化係数と前記第３の暗号化係数とを乗算することにより、前記検証用暗号文成分を含む前記第２の暗号文成分を生成する
ことを特徴とする請求項４に記載の暗号化装置。
【請求項６】
前記計算部は、前記公開鍵に含まれる第１の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を行うことにより第１の暗号化係数を計算し、前記第１の暗号化係数と前記平文との乗算を行うことにより前記平文生成用暗号文成分を計算し、前記公開鍵に含まれる少なくとも２つの第２の公開鍵成分を用いてべき指数が前記乱数であるべき乗算を各々行うことにより、少なくとも２つの前記総合暗号文成分を計算する
ことを特徴とする請求項５に記載の暗号化装置。
【請求項７】
前記第１暗号文成分圧縮部は、少なくとも１つ以上の前記第１の暗号文成分を圧縮して、アフィン表現で表現された第１の圧縮暗号文成分を得る
ことを特徴とする請求項１乃至６のいずれか一項に記載の暗号化装置。
【請求項８】
前記第２暗号文成分圧縮部は、前記第２の暗号文成分のうち少なくとも１つ以上を圧縮して、アフィン表現で表現された第２の圧縮暗号文成分を得る
ことを特徴とする請求項２乃至７のいずれか一項に記載の暗号化装置。
【請求項９】
前記第１暗号文成分圧縮部と前記第２暗号文生成部とは並行して動作可能である
ことを特徴とする請求項２乃至８のいずれか一項に記載の暗号化装置。
【請求項１０】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、
前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成部と、
復号済みの前記平文を出力する復号済み平文出力部とを備える
ことを特徴とする復号装置。
【請求項１１】
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記検証用データと前記検証用暗号文成分の少なくとも一部を用いて前記暗号文の正当性を検証する正当性検証部とを更に備え、
前記復号済み平文出力部は、前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が正当ではない旨を出力する
ことを特徴とする請求項１０に記載の復号装置。
【請求項１２】
前記暗号文は、前記平文の生成に用いる暗号文成分である平文生成用暗号文成分又は前記平文生成用暗号文成分を圧縮した圧縮平文生成用暗号文成分と、前記平文の生成と前記暗号文の正当性の検証とに用いる暗号文成分である総合暗号文成分又は前記総合暗号文成分を圧縮した圧縮総合暗号文成分と、前記暗号文の正当性の検証に用いる暗号文成分である検証用暗号文成分又は前記検証用暗号文成分を圧縮した圧縮検証用暗号文成分とを含む４つの暗号文成分を含み、
前記中間データ生成部は、
前記平文生成用暗号文成分又は前記圧縮平文生成用暗号文成分と、前記総合暗号文成分又は前記圧縮総合暗号文成分とを少なくとも用いてハッシュ値を計算するハッシュ値計算部と、
前記ハッシュ値と、受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて前記中間データを生成する生成部とを有する
ことを特徴とする請求項１０又は１１に記載の復号装置。
【請求項１３】
前記暗号文成分伸張部は、前記圧縮暗号文成分を演算可能な表現である拡大体表現又は射影表現で表現した伸張済み圧縮暗号分成分に伸張する
ことを特徴とする請求項１０乃至１２のいずれか一項に記載の復号装置。
【請求項１４】
前記正当性検証部は、前記検証用データと、前記検証用暗号文成分又は前記圧縮検証用暗号文成分との等価性を検証することにより、前記暗号文の正当性を検証する
ことを特徴とする請求項１２に記載の復号装置。
【請求項１５】
前記ハッシュ値計算部、前記暗号文成分伸張部、前記検証用データ生成部及び前記復号済み平文生成部は並列に動作可能である
ことを特徴とする請求項１２乃至１４のいずれか一項に記載の復号装置。
【請求項１６】
前記ハッシュ値計算部、前記暗号文成分伸張部、前記検証用データ生成部、前記復号済み平文生成部及び前記生成部は並列に動作可能である
ことを特徴とする請求項１２乃至１４のいずれか一項に記載の復号装置。
【請求項１７】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、
前記暗号文が正当であると検証された場合、前記平文を出力し、前記暗号文が正当でないと検証された場合、前記暗号文が不正である旨を出力する復号済み平文出力部とを備える
ことを特徴とする復号装置。
【請求項１８】
前記暗号文は、前記平文の生成に用いる平文生成用暗号文成分と、前記平文の生成と前記暗号文の正当性の検証に用いる総合暗号文成分と、前記暗号文の正当性の検証に用いる検証用暗号文成分又は前記検証用暗号文成分を圧縮した圧縮検証用暗号文成分とを含む４つの暗号文成分を含み、
前記検証用データ生成部は、
前記平文生成用暗号文成分と、前記総合暗号文成分とを少なくとも用いて、ハッシュ値を計算するハッシュ値計算部と、
前記ハッシュ値と受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記検証用データを生成する生成部とを有する
ことを特徴とする請求項１７に記載の復号装置。
【請求項１９】
各前記暗号文成分が正しくトーラスの元となっているか否かを検証するトーラス元検証部を更に備える
ことを特徴とする請求項１０乃至１８のいずれか一項に記載の復号装置。
【請求項２０】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文正当性検証装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の復号に用いる中間データを生成する中間データ生成部と、
前記圧縮暗号文成分の表現を演算可能な表現である伸張済み圧縮暗号分成分に伸張する暗号文成分伸張部と、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて前記暗号文の正当性を検証する正当性検証部と、
前記正当性検証部の検証結果を出力する検証結果出力部とを備える
ことを特徴とする暗号文検証装置。
【請求項２１】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文の正当性を検証する暗号文検証装置であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信部と、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、平文を計算する平文計算部と、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて、前記暗号文の正当性を検証するための検証用データを生成する検証用データ生成部と、
前記圧縮暗号文成分と前記検証用データとを少なくとも用いて、前記暗号文の正当性を検証する正当性検証部と、
前記正当性検証部の検証結果を出力する検証結果出力部とを備える
ことを特徴とする暗号文検証装置。
【請求項２２】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により平文を暗号化し、複数の暗号文成分を含む暗号文を出力する暗号化装置で実行される暗号化方法であって、
平文を受信する平文受信ステップと、
１つ以上の公開鍵成分を含む公開鍵を受信する公開鍵受信ステップと、
受信された前記平文と前記公開鍵成分とを用いて暗号文成分である第１の暗号文成分を少なくとも１つ以上生成する第１暗号文成分生成ステップと、
少なくとも１つ以上の前記第１の暗号文成分を圧縮して、第１の圧縮暗号文成分を得る第１暗号文成分圧縮ステップと、
受信された平文と、前記公開鍵成分と、前記第１の暗号文成分と、前記第１の圧縮暗号文成分とのうち、少なくとも１つ以上を用いて第２の暗号文成分を生成する第２暗号文成分生成ステップと、
少なくとも前記第１の圧縮暗号文成分と前記第２の暗号文成分とを含む暗号文を出力する暗号文出力ステップとを含む
ことを特徴とする暗号化方法。
【請求項２３】
有限体上の乗法群の離散対数問題に安全性の根拠を置く暗号方式により暗号化され複数の暗号文成分を含む暗号文を復号して平文を得る復号装置で実行される復号方法であって、
前記暗号文成分のうち少なくとも１つが圧縮された圧縮暗号文成分を含む暗号文を受信する暗号文受信ステップと、
前記暗号文の暗号化に用いられた公開鍵に対応する１つ以上の秘密鍵成分を含む秘密鍵を受信する秘密鍵受信ステップと、
受信された前記暗号文成分と前記秘密鍵成分とのうちいずれかを少なくとも用いて復号に必要な中間データを生成する中間データ生成ステップと、
前記圧縮暗号文成分を演算可能な表現で表現した伸張済み圧縮暗号分成分に伸張する暗号文成分伸張ステップと、
前記中間データの一部と、前記伸張済み圧縮暗号文成分と、前記暗号文成分とのいずれかを少なくとも用いて復号済みの平文を生成する復号済み平文生成ステップと、
復号済みの前記平文を出力する復号済み平文出力ステップとを含む
ことを特徴とする復号方法。
【請求項２４】
請求項２２又は２３に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【公開番号】特開２０１０−４９２１４（Ｐ２０１０−４９２１４Ａ）
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願番号】特願２００８−２１６０１６（Ｐ２００８−２１６０１６）
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月４日（２０１０．３．４）
【国際特許分類】
【出願日】平成２０年８月２５日（２００８．８．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]