(57)【要約】【課題】全ての公開鍵暗号と秘密鍵暗号の組み合わせを可能とした安全性のレベルが高いハイブリッド暗号装置を提供する。【解決手段】公開鍵暗号装置Πasyと秘密鍵暗号装置Πsyからなるハイブリッド暗号装置Πhy（鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy，復号化アルゴリズム装置Ｄhy）であって、Ｅhyは、公開鍵ｐｋと平文ｍを入力し、乱数σにハッシュ関数Ｇを施して秘密鍵ｒ2を生成し、平文ｍをｒ2を用いて暗号文ｃ2を生成し、σとｃ2にハッシュ関数Ｈを施して認証子ｒ1を生成し、σをｐｋとｒ1を用いて暗号文ｃ1を生成し、ｃ1||ｃ2を出力し、Ｄhyは、秘密鍵ｓｋとｃ1||ｃ2を入力し、ｃ1をｓｋを用いてσを生成し、σ∈ＣＯＩＮhy（乱数空間）ならば、秘密鍵ｒ2とし、ｃ2をｒ2を用いて復号化してｍを生成し、σとｃ2にＨを施してｒ1を生成し、σをｐｋとｒ1を用いて暗号化し、ｃ1と一致したならばｍを出力する。【選択図】図３
2005175583.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵暗号装置Πasy＝（鍵生成装置Ｋasy，暗号化アルゴリズム装置Ｅasy，復号化アルゴリズム装置Ｄasy）と秘密鍵暗号装置Πsy＝（暗号化アルゴリズム装置Ｅsy，復号化アルゴリズム装置Ｄsy）を基に構成されるハイブリッド暗号装置Πhy＝（鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy，復号化アルゴリズム装置Ｄhy）において、
暗号化アルゴリズム装置Ｅhy は、
公開鍵ｐｋと平文ｍを入力し、
内部の乱数空間ＣＯＩＮhyから乱数σを取り出し、ハッシュ関数Ｇを施して秘密鍵ｒ2（：＝Ｇ（σ））を生成する手段と、
平文ｍを秘密鍵ｒ2を用いて暗号化し、
【数１】
2005175583.tif 000011
乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成する手段と、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1（：＝Ｅpkasy（σ；ｒ1））を生成する手段と、
生成した暗号文ｃ1||ｃ2（「||」は連結を表す。）を出力する手段と、を備え、
復号化アルゴリズム装置Ｄhyは、
秘密鍵ｓｋと暗号文ｃ1||ｃ2を入力し、
暗号文ｃ1を秘密鍵ｓｋを用いて復号化し、乱数σ（：＝Ｄskasy（ｃ1））を生成する手段と、
乱数σが乱数空間ＣＯＩＮhyに属していれば（σ∈ＣＯＩＮhyならば）、秘密鍵ｒ2（：＝Ｇ（σ））とし、それ以外の時は不正暗号文と設定して出力する手段と、
暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、
【数２】
2005175583.tif 000012
乱数σと暗号文ｃ2にハッシュ関数Ｈを施して認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成する手段と、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致したならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）平文ｍを出力し、それ以外の時は、不正暗号文として設定して出力する手段と、を備えた
ことを特徴とするハイブリッド暗号装置。
【請求項２】
公開鍵暗号化装置（鍵生成装置Ｋasy，暗号化アルゴリズム装置Ｅasy）と秘密鍵暗号化アルゴリズム装置Ｅsyを基に構成されるハイブリッド暗号化装置（鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy） において、
公開鍵ｐｋと平文ｍを入力し、
内部の乱数空間ＣＯＩＮhyから乱数σを取り出し、ハッシュ関数Ｇを施して秘密鍵ｒ2（：＝Ｇ（σ））を生成する手段と、
平文ｍを秘密鍵ｒ2を用いて暗号化し、
【数３】
2005175583.tif 000013
乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成する手段と、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号文ｃ1（：＝Ｅpkasy（σ；ｒ1））を生成する手段と、
生成した暗号文ｃ1||ｃ2（「||」は連結を表す。）を出力する手段と、を備えた
ことを特徴とする暗号化アルゴリズム装置。
【請求項３】
公開鍵復号化アルゴリズム装置Ｄasyと秘密鍵復号化アルゴリズム装置Ｄsyを基に構成されるハイブリッド復号化アルゴリズム装置Ｄhyにおいて、
請求項２に記載の暗号化アルゴリズム装置で生成された暗号文ｃ1||ｃ2と秘密鍵ｓｋを入力し、
暗号文ｃ1を秘密鍵ｓｋを用いて乱数σ（：＝Ｄskasy（ｃ1））を生成する手段と、
乱数σが乱数空間ＣＯＩＮhyに属していれば（σ∈ＣＯＩＮhyならば）、秘密鍵ｒ2（：＝Ｇ（σ））とし、それ以外の時は不正暗号文と設定して出力する手段と、
暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、
【数４】
2005175583.tif 000014
乱数σと暗号文ｃ2にハッシュ関数Ｈを施して認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成する手段と、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致したならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）平文ｍを出力し、それ以外の時は、不正暗号文として設定して出力する手段と、を備えた
ことを特徴とするハイブリッド復号化アルゴリズム装置。
【請求項４】
公開鍵暗号装置Πasy＝（鍵生成装置Ｋasy，暗号化アルゴリズム装置Ｅasy，復号化アルゴリズム装置Ｄasy）と秘密鍵暗号装置Πsy＝（暗号化アルゴリズム装置Ｅsy，復号化アルゴリズム装置Ｄsy）を基に構成されるハイブリッド暗号装置Πhy＝（鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy，復号化アルゴリズム装置Ｄhy）におけるハイブリッド暗号・復号方法において、
暗号化アルゴリズム装置Ｅhy は、
公開鍵ｐｋと平文ｍを入力するステップと、
内部の乱数空間ＣＯＩＮhyから乱数σを取り出し、ハッシュ関数Ｇを施して秘密鍵ｒ2（：＝Ｇ（σ））を生成するステップと、
平文ｍを秘密鍵ｒ2を用いて
【数５】
2005175583.tif 000015
乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成するステップと、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号文ｃ1（：＝Ｅpkasy（σ；ｒ1））を生成するステップと、
生成した暗号文ｃ1||ｃ2（「||」は連結を表す。）を出力するステップと、を有し、
復号化アルゴリズム装置Ｄhyは、
秘密鍵ｓｋと暗号文ｃ1||ｃ2を入力するステップと、
暗号文ｃ1を秘密鍵ｓｋを用いて乱数σ（：＝Ｄskasy（ｃ1））を生成し、
乱数σが乱数空間ＣＯＩＮhyに属していれば（σ∈ＣＯＩＮhy）、秘密鍵ｒ2（：＝Ｇ（σ））とし、それ以外の時は不正暗号文と設定し、出力するステップと、
暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、
【数６】
2005175583.tif 000016
乱数σと暗号文ｃ2にハッシュ関数Ｈを施して認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成するステップと、
乱数σが公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致したならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）、平文ｍを出力し、それ以外の時は、不正暗号文として設定して出力するステップと、を有する
ことを特徴とするハイブリッド暗号・復号方法。
【請求項５】
公開鍵暗号化装置（鍵生成装置Ｋasy，暗号化アルゴリズム装置Ｅasy）と秘密鍵暗号化アルゴリズム装置Ｅsyを基に構成されるハイブリッド暗号化装置（鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy） におけるハイブリッド暗号方法おいて、
暗号化アルゴリズム装置Ｅhy は、
公開鍵ｐｋと平文ｍを入力するステップと、
乱数発生装置の乱数空間ＣＯＩＮhyから乱数σを取り出し、ハッシュ関数Ｇを施して秘密鍵ｒ2（：＝Ｇ（σ））を生成するステップと、
平文ｍを秘密鍵ｒ2を用いて
【数７】
2005175583.tif 000017
乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成するステップと、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号文ｃ1（：＝Ｅpkasy（σ；ｒ1））を生成するステップと、
生成した暗号文ｃ1||ｃ2（「||」は連結を表す。）を出力するステップと、を有する、
ことを特徴とするハイブリッド暗号方法。
【請求項６】
公開鍵復号化アルゴリズム装置Ｄasyと秘密鍵復号アルゴリズム装置Ｄsyを基に構成されるハイブリッド復号化アルゴリズム装置Ｄhyにおけるハイブリッド復号化方法において、
請求項５に記載のハイブリッド暗号方法で生成された暗号文ｃ1||ｃ2と秘密鍵ｓｋを入力するステップと、
暗号文ｃ1を秘密鍵ｓｋを用いて乱数σ（：＝Ｄskasy（ｃ1））を生成するステップと、
乱数σが乱数空間ＣＯＩＮhyに属していれば（σ∈ＣＯＩＮhyならば）、秘密鍵ｒ2（：＝Ｇ（σ））とし、それ以外の時は不正暗号文と設定し、出力するステップと、
暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、
【数８】
2005175583.tif 000018
乱数σと暗号文ｃ2にハッシュ関数Ｈを施して認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成するステップと、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致したならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）、平文ｍを出力し、それ以外の時は、不正暗号文として設定し、出力するステップと、を有する、
ことを特徴とするハイブリッド復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はハイブリッド暗号装置とその方法に関する。
【背景技術】
【０００２】
一般に、暗号は共通鍵暗号と公開鍵暗号の二種類に類別できる。公開鍵暗号は、送信側が受信側の（秘密ではない）公開鍵を使って、データ（平文）を暗号化して送信するために利用する。多くの場合、共通鍵暗号より低速なため、共通鍵暗号で問題となる秘密鍵の共有問題（鍵配送問題）などの解決に利用される。一方、共通鍵暗号は送信側、受信側が同じ鍵を秘密に保持しているとき、データ（平文）を暗号化して送信するために利用する。
公開鍵暗号システムとは、公開鍵を登録する公開鍵簿と送信装置、受信装置からなるシステムである。公開鍵暗号システムは公開鍵暗号のみでも実装できるが、公開鍵暗号で鍵配送をし、その時共有された秘密鍵で、共通鍵暗号法を使って平文を暗号通信するのが一般的な公開鍵暗号（ハイブリッド暗号）システムの構成である。
【０００３】
公開鍵暗号システムの攻撃には、さまざまな攻撃法と安全性の基準が知られている（非特許文献１  参照）。
公開鍵暗号システムは、「選択暗号文攻撃に対して強秘匿」性を持つべきであるというのが現在の暗号学者の一致した見解である。
まず、公開鍵暗号装置、秘密鍵暗号装置を厳密に定義する。公開鍵暗号装置と秘密鍵暗号装置を用いて、選択暗号文攻撃の基、強秘匿な暗号文を構成するハイブリッド（公開鍵）暗号装置の従来構成法は後述する。
【０００４】
従来の公開鍵暗号装置、秘密鍵暗号装置を図１を参照して説明する。
I．公開鍵暗号装置Πとは、次のような３つの装置の組Π＝（Ｋ，Ｅ，Ｄ）である。
（鍵生成装置Ｋ）
鍵生成装置Ｋはセキュリティパラメータｋ（慣用的に１kと書く）を引数に取り、公開鍵、秘密鍵の組（ｐｋ，ｓｋ）を出力する確率的アルゴリズム装置である。
以後、この（ｋを入力し（ｐｋ，ｓｋ）を出力する）確率的な試行を、（ｐｋ，ｓｋ）←Ｋ（１k）と記述することにする。
（暗号化アルゴリズム装置Ｅ）
暗号化装置Ｅは、公開鍵ｐｋと平文ｘ∈ＭＳＰを引数に取り、内部で乱数ｒをＣＯＩＮから取り、暗号文 ｙ：＝Ｅpk（ｘ；ｒ）を生成する（平文ｘを公開鍵ｐｋと乱数ｒを用いて暗号化する）確率的アルゴリズム装置である。
ここで、ＭＳＰとＣＯＩＮはそれぞれ平文空間、内部乱数空間（コイン空間）であり、公開鍵ｐｋにより一意に定められるものとする。
以後、この確率的な試行を、ｙ←Ｅpk（ｘ）と記述することにする。
（復号化アルゴリズム装置Ｄ）
復号化アルゴリズム装置Ｄは、秘密鍵ｓｋと暗号文（ことによるとガラクタのビット列）ｙ∈｛０，１｝*を取り、平文ｘ：＝Ｄsk（ｙ）を出力する（暗号文ｙを秘密鍵ｓｋを用いて復号化する）確定的アルゴリズム装置である。
（装置間の関係）
任意の（ｐｋ，ｓｋ）←Ｋ（１k）と任意のｘ∈ＭＳＰに対して、Ｄsk（Ｅpk（ｘ））＝ｘが常に成り立つ。
このようなΠ＝（Ｋ，Ｅ，Ｄ）を公開鍵暗号装置と呼ぶ。
【０００５】
II．秘密鍵暗号装置Πとは、次のような２つの装置の組Π＝（Ｅ，Ｄ）である。
セキュリティパラメータｋに対して、鍵空間ＫＳＰ、平文空間ＭＳＰ、内部乱数空間（コイン空間）ＣＯＩＮが一意に定まり、Ｅ，Ｄは次のような装置である。
（暗号化アルゴリズム装置Ｅ）
暗号化アルゴリズム装置Ｅは、秘密鍵ａ∈ＫＳＰと平文ｘ∈ＭＳＰを引数に取り、内部で乱数ｒをＣＯＩＮから取り、暗号文ｙ：＝Ｅa（ｘ；ｒ）を生成する（平文ｘを秘密鍵ａと乱数ｒを用いて暗号化する）確率的アルゴリズム装置である。
以後、この確率的な試行を、ｙ←Ｅa（ｘ）と記述することにする。
（復号化アルゴリズム装置Ｄ）
復号化アルゴリズム装置Ｄは、秘密鍵ａと暗号文（ことによると、ガラクタのビット列）ｙ∈｛０，１｝*を取り、平文ｘ：＝Ｄa（ｙ）を出力する（暗号文ｙを秘密鍵ａを用いて復号化する）確定的アルゴリズム装置である。
（装置間の関係）
任意のａ∈ＫＳＰと任意のｘ∈ＭＳＰに対して、Ｄa（Ｅ（ａ，ｘ））＝ｘが常に成り立つ。
このようなΠ＝（Ｅ，Ｄ）を、秘密鍵暗号と呼ぶ。
【０００６】
特に内部コイン空間ＣＯＩＮが空集合で（存在せず）、暗号文ｙが秘密鍵ａと平文ｘから一意に定まるとき、Ｅを確定的と呼び、Πを「確定的」な秘密鍵暗号装置と呼ぶ。一方、「確定的」と対比して、一般の秘密鍵暗号装置を「確率的」と呼ぶ。
その他、後述するハイブリッド暗号装置を構成するために利用される補助的な装置としてハッシュ関数装置Ｈがある。ハッシュ関数装置Ｈとは、任意の長さのビットストリング（すなわち、｛０，１｝*の元）を入力に取り、ある有限濃度の値域Ｉ（Ｈ）に値を返す関数Ｈ：｛０，１｝*→Ｉ（Ｈ）を実装したものである。現実のハッシュ関数では、例えばＳＨＡ−１，ＲＩＰＥＭＤ−１６０などが知られている。
【０００７】
III. 次に図２を参照して従来のハイブリッド（公開鍵）暗号装置（非特許文献２  参照）を説明する。
ハイブリッド（公開鍵）暗号装置ΠFO（＝ＫFO，ＥFO，ＤFO）は、任意の公開鍵暗号装置Πasy（＝（Ｋasy，Ｅasy，Ｄasy））と任意の「確定的」な秘密鍵暗号装置Πsy（＝（Ｅsy，Ｄsy））から、次のように実現される。
（鍵生成アルゴリズム装置ＫFO）
鍵生成アルゴリズム装置ＫFOは、セキュリティパラメータ１kを取り、Ｋasyを起動して、（ｐｋ，ｓｋ）←Ｋasy（１k）により得た、公開鍵、秘密鍵の組（ｐｋ，ｓｋ）をＫFO（１k）の出力として出力する。
この確率的試行を（ｐｋ，ｓｋ）←ＫFO（１k）と書くこととする。
ここで、公開鍵ｐｋは、元々Ｋasyの公開鍵であることから、ＭＳＰasy，ＣＯＩＮasyが定まる。一方、セキュリティパラメータｋからＭＳＰsy，ＣＯＩＮsy，ＫＳＰsyが一意に定まる。
公開鍵ｐｋに対するΠhyの乱数空間（コイン空間）、平文空間は以下のように定義することとする。
ＣＯＩＮFO：＝ＭＳＰasy、ＭＳＰFO：＝ＭＳＰsy．ｐｋは便宜上ｋを含んでいるものとすれば、公開鍵ｐｋにより、ΠFOの上記空間は一意に定まることとなる。
【０００８】
（暗号化アルゴリズム装置ＥFO）
暗号化アルゴリズム装置ＥFOは、公開鍵ｐｋと平文ｍ∈ＭＳＰFOを取り、次のように動作する。
１．乱数σを乱数空間ＣＯＩＮFOから取る。
σ←RＣＯＩＮFO．（Ｒ：乱数）
２．乱数σと平文ｍにハッシュ関数Ｈを適用して、σ、ｍを特定できないような認証子ｒ1（乱数成分として用いるパラメータ）を生成する。
ｒ1：＝Ｈ（σ，ｍ）．
３．乱数σにハッシュ関数Ｇを適用してハイブリッド暗号装置ΠFO（秘密鍵暗号装置Πsy）の秘密鍵（セッションキー又はワンタイムの鍵）ｒ2を生成する。
ｒ2：＝Ｇ（σ）．
４．乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1を生成する。
ｃ1：＝Ｅpkasy（σ；ｒ1）．
５．平文ｍを秘密鍵ｒ2を用いて暗号化し、暗号文ｃ2を生成する。
【数９】
2005175583.tif 000003
６．暗号文ｃ1||ｃ2をＥpkFO（ｍ；σ）として出力（送信）する。
ここで、ｃ1||ｃ2は、ビット列ｃ1とｃ2を並べて作ったビット列である。
【数１０】
2005175583.tif 000004
＊秘密鍵暗号装置Πsyは、前記したように確定的であるので、上記のステップ５．の秘密鍵暗号化アルゴリズム装置Ｅsyは「確定的」なアルゴリズム装置である点に注意。
【０００９】
（復号化アルゴリズム装置ＤFO）
復号化アルゴリズム装置ＤFOは、秘密鍵ｓｋと暗号文ｃ1||ｃ2を取り、次のように動作する。
１．暗号文ｃ1||ｃ2を所定の組（ｃ1，ｃ2）に分割する。
２．秘密鍵ｓｋを用いて暗号文ｃ1を復号化し、乱数σを生成する。
σ：＝Ｄskasy（ｃ1）．
３．乱数σにハッシュ関数Ｇを適用して秘密鍵ｒ2を生成する。
ｒ2：＝Ｇ（σ）．
４．暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、平文ｍを生成する。
【数１１】
2005175583.tif 000005
５．乱数σと平文ｍにハッシュ関数Ｈを施して、認証子ｒ1を生成する。
ｒ1：＝Ｈ（σ，ｍ）．
６．もし、（ａ）乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致し               たならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）、平文ｍを出力する。
（ｂ）それ以外の時は、不正暗号文の印εを設定し、出力する。
【非特許文献１】M.Bellare, A.Desai, D.Pointcheval, and P.Rogaway. Relations among notions of security for public-key encryption schemes. In H.Krawczyk, editor, Advances in Cryptology-CRYPTO'98, volume 1462 of Lecture Notes in Computer Science, pages 26-45. Springer-Verlag,1998.
【非特許文献２】E.Fujisaki and T.Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In M. Wiener, editor, Advances in Cryptology -CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 537-554. Springer-Verlag,1999.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記に強調したように、非特許文献２に記載の従来のハイブリッド（公開鍵）暗号装置は、一般の秘密鍵暗号装置と組み合わせることができない（実際、「確率的」な秘密鍵暗号装置と組み合わせると安全でなくなる）。
確かに、ＤＥＳ(Data Encryption Standard)，ＡＥＳ(Advanced Encryption Standard)，Cameliaなどの秘密鍵ブロック暗号は「確定的」な暗号であるが、長い平文を扱えるよう、ＣＦＢ(cipher feedback chaining)，ＯＦＢ(output feedback chaining)，ＣＢＣ(cipher block chaining)モードなどを用いてストリーム暗号にするのが一般的である。ストリーム暗号は「確率的」な暗号である。
本発明では、任意の秘密鍵暗号と組み合わせが可能になり、実質、全ての公開鍵暗号と秘密鍵暗号の組み合わせが可能となるハイブリッド暗号装置および方法を提供する。
【課題を解決するための手段】
【００１１】
本発明は、公開鍵暗号装置（Πasy＝鍵生成装置Ｋasy，暗号化アルゴリズム装置Ｅasy，復号化アルゴリズム装置Ｄasy）と秘密鍵暗号装置（Πsy＝暗号化アルゴリズム装置Ｅsy，復号化アルゴリズム装置Ｄsy）を用いて構成されるハイブリッド暗号装置（Πhy＝鍵生成装置Ｋhy，暗号化アルゴリズム装置Ｅhy，復号化アルゴリズム装置Ｄhy）において、
【００１２】
暗号化アルゴリズム装置Ｅhy は、
公開鍵ｐｋと平文ｍを入力し、
内部の乱数空間ＣＯＩＮhyから乱数σを取り出し、ハッシュ関数Ｇを施して秘密鍵ｒ2（：＝Ｇ（σ））を生成し、
平文ｍを秘密鍵ｒ2を用いて暗号化し、
【数１２】
2005175583.tif 000006
乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成し、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1（：＝Ｅpkasy（σ；ｒ1））を生成し、
生成した暗号文ｃ1||ｃ2（「||」は連結を表す。）を出力し、
【００１３】
復号化アルゴリズム装置Ｄhyは、
秘密鍵ｓｋと暗号文ｃ1||ｃ2を入力し、
暗号文ｃ1を秘密鍵ｓｋを用いて復号化し、乱数σ（：＝Ｄskasy（ｃ1））を生成し、
乱数σが乱数空間ＣＯＩＮhyに属していれば（σ∈ＣＯＩＮhyならば）、秘密鍵ｒ2（：＝Ｇ（σ））とし、それ以外の時は不正暗号文と設定して出力し、
暗号文ｃ2を秘密鍵ｒ2を用いて復号化し、
【数１３】
2005175583.tif 000007
乱数σと暗号文ｃ2にハッシュ関数Ｈを施して認証子ｒ1（：＝Ｈ（σ，ｃ2））を生成し、
乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1と一致したならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）平文ｍを出力し、それ以外の時は、不正暗号文として設定して出力する、ことを特徴とする。
【発明の効果】
【００１４】
本発明は、平文ｍ（従来例のステップ２．）の代わりに、秘密鍵による暗号文ｃ2をハッシュ関数Ｈに入力したため、秘密鍵暗号が確率的でも安全性を保持できるようになった。
本発明では、任意の秘密鍵暗号と組み合わせが可能になり、実質、全ての公開鍵暗号と秘密鍵暗号の組み合わせが可能となった。
本発明は、公開鍵暗号が一方向性を満たし、秘密鍵暗号が受動的攻撃に対して識別不可能性を持つとき、選択暗号文攻撃の基（自分が勝手に選んだ暗号文を復号してもらい、それを元にチャレンジに成功しようとするもの）、強秘匿なハイブリッド公開鍵暗号を実現できる。基礎となる公開鍵・秘密鍵暗号の安全性の条件及びハイブリッド暗号が到達する安全性のレベルは、前記した従来のハイブリッド暗号装置と同じである。ただし、既に述べたように本発明はより多くの暗号の組み合わせを可能とした。
各安全性の定義及び証明は、文献３：E.Fujisaki. Plaintext-simulatability and universally implementasble security. Unpublished Manuscript, 2003.，文献４：E.Fujisaki and T.Okamoto. Secure integration of asymmetric and symmetric encryption schemes, revised manuscript. Unpublished Manuscript, 2003.に掲載されている。
【発明を実施するための最良の形態】
【００１５】
本発明は、任意の公開鍵暗号装置Πasyと任意の秘密鍵暗号装置Πsyを基に、新たに構成されるハイブリッド暗号装置Πhyである。ハイブリッド暗号装置Πhyは、公開鍵簿、送信装置、受信装置からなる典型的な公開鍵暗号システムを構成する。
図３を参照して本発明のハイブリッド（公開鍵）暗号装置を説明する。
いま、Πasy＝（Ｋasy，Ｅasy，Ｄasy）をある公開鍵暗号装置、同様にΠsy＝（Ｅsy，Ｄsy）を秘密鍵暗号装置とする。このとき、これらの暗号装置から新たなハイブリッド（公開鍵）暗号装置Πhy＝（Ｋhy，Ｅhy，Ｄhy）を以下のように構成する。
【００１６】
（鍵生成アルゴリズム装置Ｋhy）
鍵生成アルゴリズム装置Ｋhyは、セキュリティパラメータ１kを取り、Ｋasyを起動して、（ｐｋ，ｓｋ）←Ｋasy（１k）により得た、公開鍵、秘密鍵の組（ｐｋ，ｓｋ）をＫhy（１k）の出力として出力する。
この確率的試行を（ｐｋ，ｓｋ）←Ｋhy（１k）と書くこととする。
ここで、公開鍵ｐｋは、元々Ｋasyの公開鍵であることから、ＭＳＰasy，ＣＯＩＮasyが定まる。一方、セキュリティパラメータｋからＭＳＰsy，ＣＯＩＮsy，ＫＳＰsyが一意に定まる。
公開鍵ｐｋに対するΠhyの乱数空間（コイン空間）、平文空間は以下のように定義することとする。
ＣＯＩＮhy：＝ＭＳＰasy、ＭＳＰhy：＝ＭＳＰsy．
公開鍵ｐｋは便宜上ｋを含んでいるものとすれば、公開鍵ｐｋにより、Πhyの上記空間は一意に定まることとなる。
【００１７】
（暗号化アルゴリズム装置Ｅhy）
暗号化アルゴリズム装置Ｅhyは、公開鍵ｐｋと平文ｍ∈ＭＳＰhyを取り、次のステップ１〜６を実行する手段を有する。
１．乱数空間ＣＯＩＮhyから乱数σを取り出す。
σ←RＣＯＩＮhy．
２．乱数σにハッシュ関数Ｇを施して、ハイブリッド暗号装置Πhy（秘密鍵暗号装置Πsy）の秘密鍵（ワンタイムの鍵）ｒ2を生成する。
ｒ2：＝Ｇ（σ）．
３．平文ｍを秘密鍵ｒ2を用いて暗号化し、暗号文ｃ2を生成する。
【数１４】
2005175583.tif 000008
４．乱数σと暗号文ｃ2にハッシュ関数Ｈを施してσ、ｃ2を特定できないような認証子ｒ1を生成する。
ｒ1：＝Ｈ（σ，ｃ2）．
５．乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1を生成する。
ｃ1：＝Ｅpkasy（σ；ｒ1）．
６．暗号文ｃ1||ｃ2をＥpkhy（ｍ；σ）として出力（送信）する。
ここで、暗号文ｃ1||ｃ2は、ビット列ｃ1とｃ2を並べて作ったビット列である。
【数１５】
2005175583.tif 000009
＊秘密鍵暗号装置Πsyは確率的で良いので、一般に、上記ステップ３．の秘密鍵暗号化アルゴリズム装置Ｅsyは「確率的」なアルゴリズム装置である。すなわち、暗号文ｃ2は秘密鍵ｒ2，平文ｍだけから一意に決まらない。
【００１８】
（復号化アルゴリズム装置）
復号化アルゴリズム装置Ｄhyは、秘密鍵ｓｋ∈SKhyと暗号文ビット列ｃ1||ｃ2 ∈｛０，１｝*を取り、次のステップ１〜６を実行する手段を有する。
１．ビット列ｃ1||ｃ2を所定の組（ｃ1，ｃ2）に分割する。仮に正しく指定されたフォーマットに分割できないようであれば、アルゴリズムを中断して、不正暗号文の印εを設定し、出力する。
２．暗号文ｃ1を秘密鍵ｓｋを用いて復号化し、乱数σを生成する。
σ：＝Ｄskasy（ｃ1）．
３．もし、（ａ）σ∈  ＣＯＩＮhy，ならば、秘密鍵ｒ2：＝Ｇ（σ）とし、
（ｂ）それ以外の時は、不正暗号文の印εを設定し、出力する。
４．暗号文ｃ2を秘密鍵ｒ2 を用いて復号化し、平文ｍを生成する。
【数１６】
2005175583.tif 000010
５．乱数σと暗号文ｃ2にハッシュ関数Ｈを適用して認証子ｒ1を生成する。
ｒ1：＝Ｈ（σ，ｃ2）．
６．もし、（ａ）乱数σを公開鍵ｐｋと認証子ｒ1を用いて暗号化し、暗号文ｃ1に一致し               たならば（ｃ1＝Ｅpkasy（σ；ｒ1）ならば）、平文ｍを出力する。
（ｂ）それ以外の時は、不正暗号文の印εを設定し、出力する。
上記Ｇ，Ｈはハッシュ関数Ｇ：｛０，１｝*→ＫＳＰsy，Ｈ：ＣＯＩＮhy×｛０，１｝*→ＣＯＩＮasyをそれぞれ実装したハッシュ関数装置である。
【００１９】
公開鍵暗号システム
以下では、上記ハイブリッド暗号装置Πhyを利用した、公開鍵暗号システムの一実施例について説明する。
公開鍵簿には、受信側装置Ｂの公開鍵が登録されている。送信側装置Ａ、受信側装置Ｂは安全でない通信路を介して結合されているとする。
（鍵の登録）
受信側装置Ｂは、鍵生成装置Ｋhyを起動し、（ｐｋ，ｓｋ）を作成し、ｐｋを公開鍵簿に登録する。
（暗号文の送信）
送信側装置Ａは、暗号化装置Ｅhyと公開鍵ｐｋを用いて、平文ｍの暗号文ｃ＝Ｅpkhy（ｍ）を作成し、受信側装置Ｂに送信する。
（暗号文の復号）
受信側装置Ｂは、復号化装置Ｄhyと秘密鍵ｓｋを用いて、Ｄskhy（ｃ）を計算し、暗号文ｃの平文ｍとして出力する。
【図面の簡単な説明】
【００２０】
【図１】従来の公開鍵暗号装置と秘密鍵暗号装置を説明する図。
【図２】従来のハイブリッド暗号装置を説明する図。
【図３】本発明のハイブリッド暗号装置を説明する図。
【図１】
2005175583.tif 000019
【図２】
2005175583.tif 000020
【図３】
2005175583.tif 000021