公開鍵暗号システム、方法、暗号化装置、復号装置及びこれらのプログラム
【課題】暗号文オーバーヘッドを従来よりも小さくする技術を提供する。
【解決手段】ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いる。０以上ｐ未満の整数ｗが秘密鍵に含まれ、ｇ２はｇ１ｗである。公開鍵暗号システムは、公開鍵を用いて平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する縮小暗号文生成部１１を含む暗号化装置１と、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ２としてｕ１ｗを計算する暗号文補充部２１及び秘密鍵を用いて暗号文を復号して平文を生成する復号部２２を含む復号装置２と、を含む。
【解決手段】ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いる。０以上ｐ未満の整数ｗが秘密鍵に含まれ、ｇ２はｇ１ｗである。公開鍵暗号システムは、公開鍵を用いて平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する縮小暗号文生成部１１を含む暗号化装置１と、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ２としてｕ１ｗを計算する暗号文補充部２１及び秘密鍵を用いて暗号文を復号して平文を生成する復号部２２を含む復号装置２と、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術に関する。特に、平文の暗号化を公開鍵で行い、復号を秘密鍵で行う公開鍵暗号の技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式として、例えば非特許文献１から非特許文献３にそれぞれ記載されているＣｒａｍｅｒ−Ｓｈｏｕｐ暗号、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号及びＯｋａｍｏｔｏ暗号が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ronald Cramer, Victor Shoup, “A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack”, CRYPTO 1998, p.13-25
【非特許文献２】Kaoru Kurosawa, Yvo Desmedt, “A New Paradigm of Hybrid Encryption Scheme”, CRYPTO 2004 p.426-442
【非特許文献３】Tatsuaki Okamoto, “Authenticated Key Exchange and Key Encapsulation in the Standard Model”, ASIACRYPT 2007, p.474-484
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１から非特許文献３に記載された公開鍵暗号方式は、暗号化の対象となる平文のサイズと、暗号化装置から復号装置に送信される暗号文のサイズとの差であるいわゆる暗号文オーバーヘッドが必ずしも小さくない。
【０００５】
この発明の課題は、暗号文オーバーヘッドを従来よりも小さくすることである。
【課題を解決するための手段】
【０００６】
この発明の１つの観点である公開鍵暗号システムは、ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いる。０以上ｐ未満の整数ｗが秘密鍵に含まれ、ｇ２はｇ１ｗである。公開鍵暗号システムは、公開鍵を用いて平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む暗号化装置と、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ２としてｕ１ｗを計算する暗号文補充部及び秘密鍵を用いて暗号文を復号して平文を生成する復号部を含む復号装置と、を含む。
【発明の効果】
【０００７】
ｕ２を含まない縮小暗号文を暗号化装置から復号装置に送信される暗号文とすることにより、暗号文オーバーヘッドを小さくすることができる。
【図面の簡単な説明】
【０００８】
【図１】公開鍵暗号システムの構成の例を説明するためのブロック図。
【図２】第二実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図３】第二実施形態の復号装置の構成の例を説明するためのブロック図。
【図４】第三実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図５】第三実施形態の復号装置の構成の例を説明するためのブロック図。
【図６】第四実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図７】第四実施形態の復号装置の構成の例を説明するためのブロック図。
【図８】公開鍵暗号方法の処理の例を説明するためのフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照してこの発明の実施形態を説明する。
【００１０】
［第一実施形態］
この発明は、ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式（以下、基方式という。）の一部に変更を加えたものである。
【００１１】
第一実施形態は、基方式を限定せず、任意の基方式に適用することができる公開鍵暗号システム、方法、暗号化装置、復号装置である。
【００１２】
例えば、以下のように基方式の一部を変更する。
【００１３】
＜一般的変更方式＞
≪公開パラメータ≫基方式の公開パラメータと同様とする。
【００１４】
≪鍵生成≫基方式の秘密鍵にｗ∈Ｚｐを加える。Ｚｐは０以上ｐ未満の整数集合である。また、公開鍵中のｇ２をｇ１ｗとする。
【００１５】
≪暗号化≫基方式中の暗号文中のｕ２＝（ｇ１ｗ）ｒを削除する。ｕ２を削除した暗号文を縮小暗号文と呼ぶ。
【００１６】
≪復号≫縮小暗号文中のｕ１からｕ２＝ｕ１ｗを計算する。その後、基方式の復号と同様に復号を行う。
【００１７】
公開鍵暗号システムは、図１に例示するように、暗号化装置１、復号装置２及び鍵生成部３を例えば備える。暗号化装置１は、縮小暗号文生成部１１を例えば備える。復号装置２は、暗号文補充部２１及び復号部２２を例えば備える。
【００１８】
鍵生成部３は、基方式で定められた方式により秘密鍵及び公開鍵を生成して、秘密鍵を復号装置２に送信し、公開鍵を暗号化装置１、必要に応じて復号装置２に送信する（ステップＧ１）。この秘密鍵には、０以上ｐ未満の整数ｗが秘密鍵に含まれる。また、この公開鍵中のｇ２はｇ１ｗである。
【００１９】
暗号化装置１は受信した公開鍵を記憶部１２（例えば図２参照。）に記憶し、復号装置２は受信した秘密鍵及び公開鍵を記憶部２３（例えば図３参照。）に記憶する。
【００２０】
暗号化装置１の縮小暗号文生成部１１は、公開鍵を用いて、平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する（ステップＥ１、図８参照）。すなわち、基方式の暗号文からｕ２＝（ｇ１ｗ）ｒを削除したものを縮小暗号文とする。縮小暗号文は、復号装置２に送信される。
【００２１】
復号装置２の暗号文補充部２１は、受信した縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いて、ｕ１ｗを計算する（ステップＤ１）。この計算されたｕ１ｗが、基方式の暗号文におけるｕ２となる。このように、暗号文補充部２１によりｕ２が補充されて、基方式における暗号文が生成されることになる。
【００２２】
復号装置２の復号部２２は、基方式の復号方式と同様の方式により、秘密鍵を用いてこの生成された暗号文を復号して平文を生成する（ステップＤ２）。
【００２３】
このように、ｕ２を含まない縮小暗号文を暗号化装置から復号装置に送信される暗号文とすることにより、少なくともｕ２の分だけ暗号文オーバーヘッドを小さくすることができる。
【００２４】
［第二実施形態］
第二実施形態は、第一実施形態の基方式としてＣｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いたものである。つまり、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第二実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００２５】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の詳細については、非特許文献１を参照のこと。
【００２６】
＜Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ１：Ｇ３→Ｚｐ及びＨ２：Ｇ→｛０，１｝ｋはハッシュ関数であるとする。ｋは、例えば１２８又は１６０である。
【００２７】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）∈Ｚｐ６を生成する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを０以上ｐ未満の整数の乱数とする。ｇ２＝ｇ１ｗとする。ｐｋ＝ｇ１，ｇ２，ｇ１ｘ１，ｇ２ｘ２，ｇ１ｙ１，ｇ２ｙ２，ｇ１ｚ）は公開鍵であり、ｓｋ＝（ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）は秘密鍵である。
【００２８】
ここで、ｇ１の右肩のｘ１は、ｘ１のことである。このように、この出願において、ある文字の右肩に載る文字列の中の数字は、下付きの数字を表わすとする。例えば、後述するｕ１ｘ１＋ｙ１αにおいては、文字ｕ１の右肩に載る文字列ｘ１＋ｙ１αの中の数字である１は下付きの数字を表わすため、この文字列ｘ１＋ｙ１αはｘ１＋ｙ１αを意味する。
【００２９】
≪暗号化≫平文ｍ∈Ｇ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，ｅ＝ｍ・（ｇ１ｚ）ｒ，α＝Ｈ１（ｕ１，ｕ２，ｅ），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。ＣＴ＝（ｕ１，ｅ，ｖ）を縮小暗号文として出力する。
【００３０】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，ｅ，ｖ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α≠ｖなら、入力された縮小暗号文は不正である旨のエラーを出力する。そうでなければ、ｍ＝ｅ・ｕ１−ｚを平文ｍとして出力する。
【００３１】
なお、この上記の例では、暗号化においてｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαとし、復号においてｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであるかを判定しているが、ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）とし、復号においてＨ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであるかを判定してもよい。このように、ハッシュ関数Ｈ２を用いることにより、ｖのサイズを更に小さくすることができ、すなわち縮小暗号文のサイズを更に小さくすることができ、更に暗号文オーバーヘッドを小さくすることができる。
【００３２】
上記の変更方式は、図２に例示する、暗号化装置１の縮小暗号文生成部１１及び図３に例示する復号装置２により実現される。
【００３３】
図２は、第二実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００３４】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第四暗号情報生成部１７及び出力部１３に送られる。
【００３５】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第四暗号情報生成部１７に送られる。
【００３６】
第三暗号情報生成部１６は、第三暗号情報ｅ＝ｍ・（ｇ１ｚ）ｒを計算する。計算された第三暗号情報ｅは、第四暗号情報生成部１７及び出力部１３に送られる。
【００３７】
第四暗号情報生成部１７は、第四暗号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。計算された第四暗号情報αは、第五暗号情報生成部１８に送られる。
【００３８】
第五暗号情報生成部１８は、第五暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算されたｖは、出力部１３に送られる。先に述べたように、第五暗号情報生成部１８は、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算してもよい。
【００３９】
出力部１３は、第一暗号情報及ｕ１、第三暗号情報ｅ及び第五暗号情報ｖの組（ｕ１，ｅ，ｖ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００４０】
図３は、第二実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００４１】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５に送られる。
【００４２】
第一復号情報生成部２５は、第一復号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。計算された第一復号情報αは、第二復号情報生成部２６に送られる。
【００４３】
第二復号情報生成部２６は、第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αは、出力部２４に送られる。
【００４４】
第三復号情報生成部２７は、第三復号情報ｍ＝ｅ・ｕ１−ｚを計算する。計算された第三復号情報ｍは、出力部２４に送られる。
【００４５】
出力部２４は、第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであるか判定する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであれば、第三復号情報ｍを平文として出力する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖでなければ、受信した縮小暗号文は不正である旨の情報を出力する。
【００４６】
なお、第五暗号情報生成部１８が、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算した場合には、第二復号情報生成部２６は、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）を計算する。計算された第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）は、出力部２４に送られる。
【００４７】
そして、この場合、出力部２４は、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであるか判定する。Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであれば、第三復号情報ｍを平文として出力する。Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖでなければ、受信した縮小暗号文は不正である旨の情報を出力する。
【００４８】
基方式としてＣｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００４９】
［第三実施形態］
第三実施形態は、第一実施形態の基方式としてＫｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号を用いたものである。つまり、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第三実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００５０】
Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号の詳細については、非特許文献２を参照のこと。
【００５１】
＜Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、ＫＤＦ：Ｇ→｛０，１｝ｋを所定の鍵導出関数とする。
【００５２】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚｐ５を生成する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数の乱数である。ｇ２＝ｇ１ｗとする。ｐｋ＝（ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２）は公開鍵であり、ｓｋ＝（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）は秘密鍵である。
【００５３】
≪暗号化≫ｎを整数として平文ｍ∈｛０，１｝ｎ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，α＝Ｈ（ｕ１，ｕ２），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα，Ｋ＝ＫＤＦ（ｖ）を計算する。所定の共通鍵暗号方式を用いて上記Ｋを共通鍵として平文ｍを暗号化した情報であるχを計算する。ＣＴ＝（ｕ１，χ）を縮小暗号文として出力する。
【００５４】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，χ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。α＝Ｈ（ｕ１，ｕ２）を計算する。ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。Ｋ＝ＫＤＦ（ｖ）を計算する。共通鍵暗号方式を用いてＫを共通鍵としてχを復号した情報を平文として出力する。
【００５５】
上記の変更方式は、図４に例示する、暗号化装置１の縮小暗号文生成部１１及び図５に例示する復号装置２により実現される。
【００５６】
図４は、第三実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００５７】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第三暗号情報生成部１６及び出力部１３に送られる。
【００５８】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第三暗号情報生成部１６に送られる。
【００５９】
第三暗号情報生成部１６は、第三暗号情報α＝Ｈ（ｕ１，ｕ２）を計算する。計算された第三暗号情報αは、第四暗号情報生成部１７に送られる。
【００６０】
第四暗号情報生成部１７は、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算された第四暗号情報ｖは、第五暗号情報生成部１８に送られる。
【００６１】
第五暗号情報生成部１８は、第五暗号情報Ｋ＝ＫＤＦ（ｖ）を計算する。計算された第五暗号情報Ｋは、第六暗号情報生成部１９に送られる。
【００６２】
第六暗号情報生成部１９は、所定の共通鍵暗号方式を用いて第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する。計算された第六暗号情報χは、出力部１３に送られる。
【００６３】
出力部１３は、第一暗号情報及ｕ１及び第六暗号情報χの組（ｕ１，χ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００６４】
図５は、第三実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００６５】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５及び第二復号情報生成部２６に送られる。
【００６６】
第一復号情報生成部２５は、第一復号情報α＝Ｈ（ｕ１，ｕ２）を計算する。計算された第一復号情報αは、第二復号情報生成部２６に送られる。
【００６７】
第二復号情報生成部２６は、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｖは、第三復号情報生成部２７に送られる。
【００６８】
第三復号情報生成部２７は、第三復号情報Ｋ＝ＫＤＦ（ｖ）を計算する。計算された第三復号情報Ｋは、第四復号情報生成部２８に送られる。
【００６９】
第四復号情報生成部２８は、所定の共通鍵暗号方式を用いて第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する。
【００７０】
基方式としてＫｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００７１】
［第四実施形態］
第四実施形態は、第一実施形態の基方式としてＯｋａｍｏｔｏ暗号を用いたものである。つまり、Ｏｋａｍｏｔｏ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第三実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００７２】
Ｏｋａｍｏｔｏ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｏｋａｍｏｔｏ暗号の詳細については、非特許文献１を参照のこと。
【００７３】
＜Ｏｋａｍｏｔｏ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、Ｆｖ：Ｇ６→｛０，１｝ｋを鍵ｖを用いた擬似ランダム関数とする。
【００７４】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚｐ５を選択する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２を０以上ｐ未満の整数の乱数とする。ｇ２＝ｇ１ｗとする。ｐｋ＝（ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２）は公開鍵であり、ｓｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｗ）は秘密鍵である。
【００７５】
≪暗号化≫ｎを整数として平文ｍ∈｛０，１｝ｎ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα，Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。所定の共通鍵暗号方式を用いてＫを共通鍵として平文ｍを暗号化した情報であるχを計算する。ＣＴ＝（ｕ１，χ）を縮小暗号文として出力する。
【００７６】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，χ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）∈Ｇ４である場合には、すなわち、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の少なくとも１つが有限巡回群Ｇの元でない場合には、受信した縮小暗号文が不正である旨の情報を出力する。ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元である場合には、α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２），ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α，Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算し、所定の共通鍵暗号方式を用いてＫを共通鍵としてχを復号した情報を計算して平文として出力する。
【００７７】
上記の変更方式は、図６に例示する、暗号化装置１の縮小暗号文生成部１１及び図７に例示する復号装置２により実現される。
【００７８】
図６は、第四実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００７９】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第三暗号情報生成部１６、第五暗号情報生成部１８及び出力部１３に送られる。
【００８０】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第三暗号情報生成部１６及び第五暗号情報生成部１８に送られる。
【００８１】
第三暗号情報生成部１６は、第三暗号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する。計算された第三暗号情報αは、第四暗号情報生成部１７に送られる。
【００８２】
第四暗号情報生成部１７は、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算された第四暗号情報生成部ｖは、第五暗号情報生成部１８に送られる。
【００８３】
第五暗号情報生成部１８は、第五暗号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。計算された第五暗号情報Ｋは、第六暗号情報生成部１９に送られる。
【００８４】
第六暗号情報生成部１９は、所定の共通鍵暗号方式を用いて第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する。計算された第六暗号情報χは、出力部１３に送られる。
【００８５】
出力部１３は、第一暗号情報及ｕ１及び第六暗号情報χの組（ｕ１，χ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００８６】
図７は、第四実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００８７】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５、第二復号情報生成部２６及び第三復号情報生成部２７に送られる。
【００８８】
判定部２９は、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であるか判定する。
【００８９】
第一復号情報生成部２５は、第一復号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する。
【００９０】
第二復号情報生成部２６は、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｖは、第三復号情報生成部２７に送られる。
【００９１】
第三復号情報生成部２７と、第三復号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。計算された第三復号情報Ｋは、第四復号情報生成部２８に送られる。
【００９２】
判定部において、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であると判定されている場合には、第四復号情報生成部２８は、所定の共通鍵暗号方式を用いて第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する。この所定の共通鍵暗号方式は、暗号化装置１が用いた共通暗号方式と同じものである。判定部２９において、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であると判定されていない場合には、受信した縮小暗号文が不正である旨の情報を出力する。
【００９３】
基方式としてＯｋａｍｏｔｏ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００９４】
［他の変形例］
この例では、暗号化装置１、復号装置２及び鍵生成部３のそれぞれが別の装置によって実現されているが、暗号化装置１、復号装置２及び鍵生成部３は同一の装置により実現されてもよい。また、鍵生成部３は、復号装置２に設けられていてもよい。
【００９５】
暗号化装置１をコンピュータによって実現する場合、暗号化装置１の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、暗号化装置１の各部の処理機能がコンピュータ上で実現される。
【００９６】
同様に、復号装置２をコンピュータによって実現する場合、復号装置２の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、復号装置２の各部の処理機能がコンピュータ上で実現される。
【００９７】
これらのプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９８】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００９９】
１ 暗号化装置
１１ 縮小暗号文生成部
１２ 記憶部
１３ 出力部
１４ 第一暗号情報生成部
１５ 第二暗号情報生成部
１６ 第三暗号情報生成部
１７ 第四暗号情報生成部
１８ 第五暗号情報生成部
１９ 第六暗号情報生成部
２ 復号装置
２１ 暗号文補充部
２２ 復号部
２３ 記憶部
２４ 出力部
２５ 第一復号情報生成部
２６ 第二復号情報生成部
２７ 第三復号情報生成部
２８ 第四復号情報生成部
２９ 判定部
３ 鍵生成部
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術に関する。特に、平文の暗号化を公開鍵で行い、復号を秘密鍵で行う公開鍵暗号の技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式として、例えば非特許文献１から非特許文献３にそれぞれ記載されているＣｒａｍｅｒ−Ｓｈｏｕｐ暗号、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号及びＯｋａｍｏｔｏ暗号が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ronald Cramer, Victor Shoup, “A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack”, CRYPTO 1998, p.13-25
【非特許文献２】Kaoru Kurosawa, Yvo Desmedt, “A New Paradigm of Hybrid Encryption Scheme”, CRYPTO 2004 p.426-442
【非特許文献３】Tatsuaki Okamoto, “Authenticated Key Exchange and Key Encapsulation in the Standard Model”, ASIACRYPT 2007, p.474-484
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１から非特許文献３に記載された公開鍵暗号方式は、暗号化の対象となる平文のサイズと、暗号化装置から復号装置に送信される暗号文のサイズとの差であるいわゆる暗号文オーバーヘッドが必ずしも小さくない。
【０００５】
この発明の課題は、暗号文オーバーヘッドを従来よりも小さくすることである。
【課題を解決するための手段】
【０００６】
この発明の１つの観点である公開鍵暗号システムは、ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いる。０以上ｐ未満の整数ｗが秘密鍵に含まれ、ｇ２はｇ１ｗである。公開鍵暗号システムは、公開鍵を用いて平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む暗号化装置と、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ２としてｕ１ｗを計算する暗号文補充部及び秘密鍵を用いて暗号文を復号して平文を生成する復号部を含む復号装置と、を含む。
【発明の効果】
【０００７】
ｕ２を含まない縮小暗号文を暗号化装置から復号装置に送信される暗号文とすることにより、暗号文オーバーヘッドを小さくすることができる。
【図面の簡単な説明】
【０００８】
【図１】公開鍵暗号システムの構成の例を説明するためのブロック図。
【図２】第二実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図３】第二実施形態の復号装置の構成の例を説明するためのブロック図。
【図４】第三実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図５】第三実施形態の復号装置の構成の例を説明するためのブロック図。
【図６】第四実施形態の縮小暗号文生成部の構成の例を説明するためのブロック図。
【図７】第四実施形態の復号装置の構成の例を説明するためのブロック図。
【図８】公開鍵暗号方法の処理の例を説明するためのフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照してこの発明の実施形態を説明する。
【００１０】
［第一実施形態］
この発明は、ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式（以下、基方式という。）の一部に変更を加えたものである。
【００１１】
第一実施形態は、基方式を限定せず、任意の基方式に適用することができる公開鍵暗号システム、方法、暗号化装置、復号装置である。
【００１２】
例えば、以下のように基方式の一部を変更する。
【００１３】
＜一般的変更方式＞
≪公開パラメータ≫基方式の公開パラメータと同様とする。
【００１４】
≪鍵生成≫基方式の秘密鍵にｗ∈Ｚｐを加える。Ｚｐは０以上ｐ未満の整数集合である。また、公開鍵中のｇ２をｇ１ｗとする。
【００１５】
≪暗号化≫基方式中の暗号文中のｕ２＝（ｇ１ｗ）ｒを削除する。ｕ２を削除した暗号文を縮小暗号文と呼ぶ。
【００１６】
≪復号≫縮小暗号文中のｕ１からｕ２＝ｕ１ｗを計算する。その後、基方式の復号と同様に復号を行う。
【００１７】
公開鍵暗号システムは、図１に例示するように、暗号化装置１、復号装置２及び鍵生成部３を例えば備える。暗号化装置１は、縮小暗号文生成部１１を例えば備える。復号装置２は、暗号文補充部２１及び復号部２２を例えば備える。
【００１８】
鍵生成部３は、基方式で定められた方式により秘密鍵及び公開鍵を生成して、秘密鍵を復号装置２に送信し、公開鍵を暗号化装置１、必要に応じて復号装置２に送信する（ステップＧ１）。この秘密鍵には、０以上ｐ未満の整数ｗが秘密鍵に含まれる。また、この公開鍵中のｇ２はｇ１ｗである。
【００１９】
暗号化装置１は受信した公開鍵を記憶部１２（例えば図２参照。）に記憶し、復号装置２は受信した秘密鍵及び公開鍵を記憶部２３（例えば図３参照。）に記憶する。
【００２０】
暗号化装置１の縮小暗号文生成部１１は、公開鍵を用いて、平文ｍを暗号化してｕ１を含むがｕ２を含まない縮小暗号文を生成する（ステップＥ１、図８参照）。すなわち、基方式の暗号文からｕ２＝（ｇ１ｗ）ｒを削除したものを縮小暗号文とする。縮小暗号文は、復号装置２に送信される。
【００２１】
復号装置２の暗号文補充部２１は、受信した縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いて、ｕ１ｗを計算する（ステップＤ１）。この計算されたｕ１ｗが、基方式の暗号文におけるｕ２となる。このように、暗号文補充部２１によりｕ２が補充されて、基方式における暗号文が生成されることになる。
【００２２】
復号装置２の復号部２２は、基方式の復号方式と同様の方式により、秘密鍵を用いてこの生成された暗号文を復号して平文を生成する（ステップＤ２）。
【００２３】
このように、ｕ２を含まない縮小暗号文を暗号化装置から復号装置に送信される暗号文とすることにより、少なくともｕ２の分だけ暗号文オーバーヘッドを小さくすることができる。
【００２４】
［第二実施形態］
第二実施形態は、第一実施形態の基方式としてＣｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いたものである。つまり、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第二実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００２５】
Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の詳細については、非特許文献１を参照のこと。
【００２６】
＜Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ１：Ｇ３→Ｚｐ及びＨ２：Ｇ→｛０，１｝ｋはハッシュ関数であるとする。ｋは、例えば１２８又は１６０である。
【００２７】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）∈Ｚｐ６を生成する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚを０以上ｐ未満の整数の乱数とする。ｇ２＝ｇ１ｗとする。ｐｋ＝ｇ１，ｇ２，ｇ１ｘ１，ｇ２ｘ２，ｇ１ｙ１，ｇ２ｙ２，ｇ１ｚ）は公開鍵であり、ｓｋ＝（ｗ，ｘ１，ｘ２，ｙ１，ｙ２，ｚ）は秘密鍵である。
【００２８】
ここで、ｇ１の右肩のｘ１は、ｘ１のことである。このように、この出願において、ある文字の右肩に載る文字列の中の数字は、下付きの数字を表わすとする。例えば、後述するｕ１ｘ１＋ｙ１αにおいては、文字ｕ１の右肩に載る文字列ｘ１＋ｙ１αの中の数字である１は下付きの数字を表わすため、この文字列ｘ１＋ｙ１αはｘ１＋ｙ１αを意味する。
【００２９】
≪暗号化≫平文ｍ∈Ｇ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，ｅ＝ｍ・（ｇ１ｚ）ｒ，α＝Ｈ１（ｕ１，ｕ２，ｅ），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。ＣＴ＝（ｕ１，ｅ，ｖ）を縮小暗号文として出力する。
【００３０】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，ｅ，ｖ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α≠ｖなら、入力された縮小暗号文は不正である旨のエラーを出力する。そうでなければ、ｍ＝ｅ・ｕ１−ｚを平文ｍとして出力する。
【００３１】
なお、この上記の例では、暗号化においてｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαとし、復号においてｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであるかを判定しているが、ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）とし、復号においてＨ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであるかを判定してもよい。このように、ハッシュ関数Ｈ２を用いることにより、ｖのサイズを更に小さくすることができ、すなわち縮小暗号文のサイズを更に小さくすることができ、更に暗号文オーバーヘッドを小さくすることができる。
【００３２】
上記の変更方式は、図２に例示する、暗号化装置１の縮小暗号文生成部１１及び図３に例示する復号装置２により実現される。
【００３３】
図２は、第二実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００３４】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第四暗号情報生成部１７及び出力部１３に送られる。
【００３５】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第四暗号情報生成部１７に送られる。
【００３６】
第三暗号情報生成部１６は、第三暗号情報ｅ＝ｍ・（ｇ１ｚ）ｒを計算する。計算された第三暗号情報ｅは、第四暗号情報生成部１７及び出力部１３に送られる。
【００３７】
第四暗号情報生成部１７は、第四暗号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。計算された第四暗号情報αは、第五暗号情報生成部１８に送られる。
【００３８】
第五暗号情報生成部１８は、第五暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算されたｖは、出力部１３に送られる。先に述べたように、第五暗号情報生成部１８は、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算してもよい。
【００３９】
出力部１３は、第一暗号情報及ｕ１、第三暗号情報ｅ及び第五暗号情報ｖの組（ｕ１，ｅ，ｖ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００４０】
図３は、第二実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００４１】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５に送られる。
【００４２】
第一復号情報生成部２５は、第一復号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する。計算された第一復号情報αは、第二復号情報生成部２６に送られる。
【００４３】
第二復号情報生成部２６は、第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αは、出力部２４に送られる。
【００４４】
第三復号情報生成部２７は、第三復号情報ｍ＝ｅ・ｕ１−ｚを計算する。計算された第三復号情報ｍは、出力部２４に送られる。
【００４５】
出力部２４は、第二復号情報ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであるか判定する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖであれば、第三復号情報ｍを平文として出力する。ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α＝ｖでなければ、受信した縮小暗号文は不正である旨の情報を出力する。
【００４６】
なお、第五暗号情報生成部１８が、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算した場合には、第二復号情報生成部２６は、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）を計算する。計算された第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）は、出力部２４に送られる。
【００４７】
そして、この場合、出力部２４は、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであるか判定する。Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであれば、第三復号情報ｍを平文として出力する。Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖでなければ、受信した縮小暗号文は不正である旨の情報を出力する。
【００４８】
基方式としてＣｒａｍｅｒ−Ｓｈｏｕｐ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００４９】
［第三実施形態］
第三実施形態は、第一実施形態の基方式としてＫｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号を用いたものである。つまり、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第三実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００５０】
Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号の詳細については、非特許文献２を参照のこと。
【００５１】
＜Ｋｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、ＫＤＦ：Ｇ→｛０，１｝ｋを所定の鍵導出関数とする。
【００５２】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚｐ５を生成する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数の乱数である。ｇ２＝ｇ１ｗとする。ｐｋ＝（ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２）は公開鍵であり、ｓｋ＝（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）は秘密鍵である。
【００５３】
≪暗号化≫ｎを整数として平文ｍ∈｛０，１｝ｎ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，α＝Ｈ（ｕ１，ｕ２），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα，Ｋ＝ＫＤＦ（ｖ）を計算する。所定の共通鍵暗号方式を用いて上記Ｋを共通鍵として平文ｍを暗号化した情報であるχを計算する。ＣＴ＝（ｕ１，χ）を縮小暗号文として出力する。
【００５４】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，χ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。α＝Ｈ（ｕ１，ｕ２）を計算する。ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。Ｋ＝ＫＤＦ（ｖ）を計算する。共通鍵暗号方式を用いてＫを共通鍵としてχを復号した情報を平文として出力する。
【００５５】
上記の変更方式は、図４に例示する、暗号化装置１の縮小暗号文生成部１１及び図５に例示する復号装置２により実現される。
【００５６】
図４は、第三実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００５７】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第三暗号情報生成部１６及び出力部１３に送られる。
【００５８】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第三暗号情報生成部１６に送られる。
【００５９】
第三暗号情報生成部１６は、第三暗号情報α＝Ｈ（ｕ１，ｕ２）を計算する。計算された第三暗号情報αは、第四暗号情報生成部１７に送られる。
【００６０】
第四暗号情報生成部１７は、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算された第四暗号情報ｖは、第五暗号情報生成部１８に送られる。
【００６１】
第五暗号情報生成部１８は、第五暗号情報Ｋ＝ＫＤＦ（ｖ）を計算する。計算された第五暗号情報Ｋは、第六暗号情報生成部１９に送られる。
【００６２】
第六暗号情報生成部１９は、所定の共通鍵暗号方式を用いて第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する。計算された第六暗号情報χは、出力部１３に送られる。
【００６３】
出力部１３は、第一暗号情報及ｕ１及び第六暗号情報χの組（ｕ１，χ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００６４】
図５は、第三実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００６５】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５及び第二復号情報生成部２６に送られる。
【００６６】
第一復号情報生成部２５は、第一復号情報α＝Ｈ（ｕ１，ｕ２）を計算する。計算された第一復号情報αは、第二復号情報生成部２６に送られる。
【００６７】
第二復号情報生成部２６は、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｖは、第三復号情報生成部２７に送られる。
【００６８】
第三復号情報生成部２７は、第三復号情報Ｋ＝ＫＤＦ（ｖ）を計算する。計算された第三復号情報Ｋは、第四復号情報生成部２８に送られる。
【００６９】
第四復号情報生成部２８は、所定の共通鍵暗号方式を用いて第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する。
【００７０】
基方式としてＫｕｒｏｓａｗａ−Ｄｅｓｍｅｄｔ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００７１】
［第四実施形態］
第四実施形態は、第一実施形態の基方式としてＯｋａｍｏｔｏ暗号を用いたものである。つまり、Ｏｋａｍｏｔｏ暗号に、第一実施形態で説明した＜一般的変更方式＞を適用したものである。第三実施形態は、この部分のみが第一実施形態と異なる。以下では、第一実施形態と異なる部分を中心に説明をして、同じ部分については重複説明を省略する。
【００７２】
Ｏｋａｍｏｔｏ暗号に、上記の＜一般的変更方式＞を適用すると、以下のようになる。なお、Ｏｋａｍｏｔｏ暗号の詳細については、非特許文献１を参照のこと。
【００７３】
＜Ｏｋａｍｏｔｏ暗号の変更方式＞
≪公開パラメータ≫セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、Ｆｖ：Ｇ６→｛０，１｝ｋを鍵ｖを用いた擬似ランダム関数とする。
【００７４】
≪鍵生成≫ｐを大きな素数として、ｇ１，ｇ２を位数ｐの有限巡回群Ｇの生成元とする。整数の組（ｗ，ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚｐ５を選択する。例えば、ｗ，ｘ１，ｘ２，ｙ１，ｙ２を０以上ｐ未満の整数の乱数とする。ｇ２＝ｇ１ｗとする。ｐｋ＝（ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２）は公開鍵であり、ｓｋ＝（ｘ１，ｘ２，ｙ１，ｙ２，ｗ）は秘密鍵である。
【００７５】
≪暗号化≫ｎを整数として平文ｍ∈｛０，１｝ｎ及び公開鍵ｐｋを入力とする。乱数ｒ∈Ｚｐを生成し、ｕ１＝ｇ１ｒ，ｕ２＝ｇ２ｒ，α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２），ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα，Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。所定の共通鍵暗号方式を用いてＫを共通鍵として平文ｍを暗号化した情報であるχを計算する。ＣＴ＝（ｕ１，χ）を縮小暗号文として出力する。
【００７６】
≪復号≫縮小暗号文ＣＴ＝（ｕ１，χ）及び秘密鍵ｓｋを入力とする。ｕ２＝ｕ１ｗを計算する。（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）∈Ｇ４である場合には、すなわち、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の少なくとも１つが有限巡回群Ｇの元でない場合には、受信した縮小暗号文が不正である旨の情報を出力する。ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元である場合には、α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２），ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α，Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算し、所定の共通鍵暗号方式を用いてＫを共通鍵としてχを復号した情報を計算して平文として出力する。
【００７７】
上記の変更方式は、図６に例示する、暗号化装置１の縮小暗号文生成部１１及び図７に例示する復号装置２により実現される。
【００７８】
図６は、第四実施形態の暗号化装置１の縮小暗号文生成部１１を説明するためのブロック図である。記憶部１２には、公開鍵ｐｋ、平文ｍが記憶されている。縮小暗号文生成部１１の各部は適宜この記憶部１２に記憶された公開鍵ｐｋ、平文ｍを読み込んで計算を行う。
【００７９】
第一暗号情報生成部１４は、第一暗号情報ｕ１＝ｇ１ｒを計算する。計算された第一暗号情報ｕ１は、第三暗号情報生成部１６、第五暗号情報生成部１８及び出力部１３に送られる。
【００８０】
第二暗号情報生成部１５は、第二暗号情報ｕ２＝ｇ２ｒを計算する。計算された第二暗号情報ｕ２は、第三暗号情報生成部１６及び第五暗号情報生成部１８に送られる。
【００８１】
第三暗号情報生成部１６は、第三暗号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する。計算された第三暗号情報αは、第四暗号情報生成部１７に送られる。
【００８２】
第四暗号情報生成部１７は、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する。計算された第四暗号情報生成部ｖは、第五暗号情報生成部１８に送られる。
【００８３】
第五暗号情報生成部１８は、第五暗号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。計算された第五暗号情報Ｋは、第六暗号情報生成部１９に送られる。
【００８４】
第六暗号情報生成部１９は、所定の共通鍵暗号方式を用いて第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する。計算された第六暗号情報χは、出力部１３に送られる。
【００８５】
出力部１３は、第一暗号情報及ｕ１及び第六暗号情報χの組（ｕ１，χ）を縮小暗号文として出力する。この縮小暗号文は、復号装置２に送信される。
【００８６】
図７は、第四実施形態の復号装置２を説明するためのブロック図である。記憶部２３には、受信した縮小暗号文及び秘密鍵ｓｋが記憶されている。復号装置２の各部は適宜この記憶部２３に記憶された縮小暗号文及び秘密鍵ｓｋを読み込んで計算を行う。
【００８７】
暗号文補充部２１は、縮小暗号文に含まれるｕ１及び秘密鍵に含まれるｗを用いてｕ１ｗを計算して、その計算結果をｕ２とする。ｕ２は、第一復号情報生成部２５、第二復号情報生成部２６及び第三復号情報生成部２７に送られる。
【００８８】
判定部２９は、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であるか判定する。
【００８９】
第一復号情報生成部２５は、第一復号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する。
【００９０】
第二復号情報生成部２６は、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する。計算された第二復号情報ｖは、第三復号情報生成部２７に送られる。
【００９１】
第三復号情報生成部２７と、第三復号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する。計算された第三復号情報Ｋは、第四復号情報生成部２８に送られる。
【００９２】
判定部において、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であると判定されている場合には、第四復号情報生成部２８は、所定の共通鍵暗号方式を用いて第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する。この所定の共通鍵暗号方式は、暗号化装置１が用いた共通暗号方式と同じものである。判定部２９において、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが有限巡回群Ｇの元であると判定されていない場合には、受信した縮小暗号文が不正である旨の情報を出力する。
【００９３】
基方式としてＯｋａｍｏｔｏ暗号を用いることにより、ハッシュ関数の入出力の組についての情報であるハッシュリストが漏洩したとしても、いわゆる選択暗号文攻撃安全性を保つことができる。
【００９４】
［他の変形例］
この例では、暗号化装置１、復号装置２及び鍵生成部３のそれぞれが別の装置によって実現されているが、暗号化装置１、復号装置２及び鍵生成部３は同一の装置により実現されてもよい。また、鍵生成部３は、復号装置２に設けられていてもよい。
【００９５】
暗号化装置１をコンピュータによって実現する場合、暗号化装置１の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、暗号化装置１の各部の処理機能がコンピュータ上で実現される。
【００９６】
同様に、復号装置２をコンピュータによって実現する場合、復号装置２の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、復号装置２の各部の処理機能がコンピュータ上で実現される。
【００９７】
これらのプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９８】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００９９】
１ 暗号化装置
１１ 縮小暗号文生成部
１２ 記憶部
１３ 出力部
１４ 第一暗号情報生成部
１５ 第二暗号情報生成部
１６ 第三暗号情報生成部
１７ 第四暗号情報生成部
１８ 第五暗号情報生成部
１９ 第六暗号情報生成部
２ 復号装置
２１ 暗号文補充部
２２ 復号部
２３ 記憶部
２４ 出力部
２５ 第一復号情報生成部
２６ 第二復号情報生成部
２７ 第三復号情報生成部
２８ 第四復号情報生成部
２９ 判定部
３ 鍵生成部
【特許請求の範囲】
【請求項１】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムにおいて、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む暗号化装置と、
上記縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて上記ｕ２としてｕ１ｗを計算する暗号文補充部と、上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号部とを含む復号装置と、を含む、
公開鍵暗号システム。
【請求項２】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ１：Ｇ３→Ｚｐ及びＨ２：Ｇ→｛０，１｝ｋはハッシュ関数であり、
ｘ１，ｘ２，ｙ１，ｙ２，ｚは０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１，ｇ２ｘ２，ｇ１ｙ１，ｇ２ｙ２，ｇ１ｚは公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｚ，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報ｅ＝ｍ・（ｇ１ｚ）ｒを計算する第三暗号情報生成部と、第四暗号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する第四暗号情報生成部と、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算する第五暗号情報生成部と、上記第一暗号情報及ｕ１、上記第三暗号情報ｅ及び上記第五暗号情報ｖの組（ｕ１，ｅ，ｖ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する第一復号情報生成部と、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）を計算する第二復号情報生成部と、第三復号情報ｍ＝ｅ・ｕ１−ｚを計算する第三復号情報生成部と、上記第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであれば上記第三復号情報ｍを平文ｍとして出力する出力部と、を含む、
公開鍵暗号システム。
【請求項３】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、ＫＤＦ：Ｇ→｛０，１｝ｋを鍵導出関数として、
ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２は公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報α＝Ｈ（ｕ１，ｕ２）を計算する第三暗号情報生成部と、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する第四暗号情報生成部と、第五暗号情報Ｋ＝ＫＤＦ（ｖ）を計算する第五暗号情報生成部と、所定の共通鍵暗号方式を用いて上記第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する第六暗号情報生成部と、上記第一暗号情報及ｕ１及び上記第六暗号情報χの組（ｕ１，χ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ（ｕ１，ｕ２）を計算する第一復号情報生成部と、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する第二復号情報生成部と、第三復号情報Ｋ＝ＫＤＦ（ｖ）を計算する第三復号情報生成部と、上記共通鍵暗号方式を用いて上記第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する第四復号情報生成部と、を含む、
公開鍵暗号システム。
【請求項４】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、Ｆｖ：Ｇ６→｛０，１｝ｋを鍵ｖを用いた擬似ランダム関数として、
ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２は公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する第三暗号情報生成部と、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する第四暗号情報生成部と、第五暗号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する第五暗号情報生成部と、所定の共通鍵暗号方式を用いて上記第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する第六暗号情報生成部と、上記第一暗号情報及ｕ１及び上記第六暗号情報χの組（ｕ１，χ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する第一復号情報生成部と、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する第二復号情報生成部と、第三復号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する第三復号情報生成部と、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが上記有限巡回群Ｇの元である場合には上記共通鍵暗号方式を用いて上記第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する第四復号情報生成部と、を含む、
公開鍵暗号システム。
【請求項５】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号方法において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成ステップと、
上記縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて、上記ｕ２としてｕ１ｗを計算する暗号文補充ステップと、
上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号ステップと、を含む、
公開鍵暗号方法。
【請求項６】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムの暗号化装置において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて、平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む、
暗号化装置
【請求項７】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムの復号装置において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化した上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を受信し、その受信した縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて上記ｕ２としてｕ１ｗを計算する暗号文補充部と、
上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号部と、を含む、
復号装置。
【請求項８】
請求項６の暗号化装置の各部としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項７の復号装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムにおいて、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む暗号化装置と、
上記縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて上記ｕ２としてｕ１ｗを計算する暗号文補充部と、上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号部とを含む復号装置と、を含む、
公開鍵暗号システム。
【請求項２】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ１：Ｇ３→Ｚｐ及びＨ２：Ｇ→｛０，１｝ｋはハッシュ関数であり、
ｘ１，ｘ２，ｙ１，ｙ２，ｚは０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１，ｇ２ｘ２，ｇ１ｙ１，ｇ２ｙ２，ｇ１ｚは公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｚ，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報ｅ＝ｍ・（ｇ１ｚ）ｒを計算する第三暗号情報生成部と、第四暗号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する第四暗号情報生成部と、第五暗号情報ｖ＝Ｈ２（（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒα）を計算する第五暗号情報生成部と、上記第一暗号情報及ｕ１、上記第三暗号情報ｅ及び上記第五暗号情報ｖの組（ｕ１，ｅ，ｖ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ１（ｕ１，ｕ２，ｅ）を計算する第一復号情報生成部と、第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）を計算する第二復号情報生成部と、第三復号情報ｍ＝ｅ・ｕ１−ｚを計算する第三復号情報生成部と、上記第二復号情報Ｈ２（ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２α）＝ｖであれば上記第三復号情報ｍを平文ｍとして出力する出力部と、を含む、
公開鍵暗号システム。
【請求項３】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、ＫＤＦ：Ｇ→｛０，１｝ｋを鍵導出関数として、
ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２は公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報α＝Ｈ（ｕ１，ｕ２）を計算する第三暗号情報生成部と、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する第四暗号情報生成部と、第五暗号情報Ｋ＝ＫＤＦ（ｖ）を計算する第五暗号情報生成部と、所定の共通鍵暗号方式を用いて上記第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する第六暗号情報生成部と、上記第一暗号情報及ｕ１及び上記第六暗号情報χの組（ｕ１，χ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ（ｕ１，ｕ２）を計算する第一復号情報生成部と、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する第二復号情報生成部と、第三復号情報Ｋ＝ＫＤＦ（ｖ）を計算する第三復号情報生成部と、上記共通鍵暗号方式を用いて上記第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する第四復号情報生成部と、を含む、
公開鍵暗号システム。
【請求項４】
請求項１に記載の公開鍵暗号システムにおいて、
セキュリティパラメータｋは正の整数であり、Ｈ：Ｇ２→Ｚｐはハッシュ関数であり、Ｆｖ：Ｇ６→｛０，１｝ｋを鍵ｖを用いた擬似ランダム関数として、
ｘ１，ｘ２，ｙ１，ｙ２は０以上ｐ未満の整数であり、ｇ１，ｇ２，ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２は公開鍵であり、ｘ１，ｘ２，ｙ１，ｙ２，ｗは秘密鍵であり、
上記縮小暗号文生成部は、第一暗号情報ｕ１＝ｇ１ｒを計算する第一暗号情報生成部と、第二暗号情報ｕ２＝ｇ２ｒを計算する第二暗号情報生成部と、第三暗号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する第三暗号情報生成部と、第四暗号情報ｖ＝（ｇ１ｘ１ｇ２ｘ２）ｒ・（ｇ１ｙ１ｇ２ｙ２）ｒαを計算する第四暗号情報生成部と、第五暗号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する第五暗号情報生成部と、所定の共通鍵暗号方式を用いて上記第五暗号情報Ｋを共通鍵として平文ｍを暗号化した情報である第六暗号情報χを計算する第六暗号情報生成部と、上記第一暗号情報及ｕ１及び上記第六暗号情報χの組（ｕ１，χ）を上記縮小暗号文として出力する出力部と、を含み、
上記復号部は、第一復号情報α＝Ｈ（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２）を計算する第一復号情報生成部と、第二復号情報ｖ＝ｕ１ｘ１＋ｙ１α・ｕ２ｘ２＋ｙ２αを計算する第二復号情報生成部と、第三復号情報Ｋ＝Ｆｖ（ｐｋ，ｕ１，ｕ２）を計算する第三復号情報生成部と、ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２，ｕ１，ｕ２の全てが上記有限巡回群Ｇの元である場合には上記共通鍵暗号方式を用いて上記第三復号情報Ｋを共通鍵としてχを復号した情報である第四復号情報ｍを計算して平文として出力する第四復号情報生成部と、を含む、
公開鍵暗号システム。
【請求項５】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号方法において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成ステップと、
上記縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて、上記ｕ２としてｕ１ｗを計算する暗号文補充ステップと、
上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号ステップと、を含む、
公開鍵暗号方法。
【請求項６】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムの暗号化装置において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて、平文ｍを暗号化して上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を生成する縮小暗号文生成部を含む、
暗号化装置
【請求項７】
ｐは素数であり、ｒは０以上ｐ未満の整数であり、位数ｐの有限巡回群Ｇの生成元ｇ１，ｇ２が公開鍵に含まれ、ｕ１＝ｇ１ｒ及びｕ２＝ｇ２ｒが暗号文に含まれる公開鍵暗号方式を用いた公開鍵暗号システムの復号装置において、
０以上ｐ未満の整数ｗが秘密鍵に含まれ、上記ｇ２はｇ１ｗであり、
上記公開鍵を用いて平文ｍを暗号化した上記ｕ１を含むが上記ｕ２を含まない縮小暗号文を受信し、その受信した縮小暗号文に含まれるｕ１及び上記秘密鍵に含まれるｗを用いて上記ｕ２としてｕ１ｗを計算する暗号文補充部と、
上記秘密鍵を用いて上記暗号文を復号して平文ｍを生成する復号部と、を含む、
復号装置。
【請求項８】
請求項６の暗号化装置の各部としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項７の復号装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１１８３６５（Ｐ２０１２−１１８３６５Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２６９０５９（Ｐ２０１０−２６９０５９）
【出願日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]