JP2008058944A - 暗号通信方法、受信者側装置、鍵管理センタ側装置及びプログラム - Google Patents

Abstract

【課題】 ＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供すること。
【解決手段】 暗号文の受信者となる受信者側装置１１０は、乱数ｓ_１,ｓ_２を選び、公開の鍵情報の一部として、Ｐ,Ｑ∈Ｇ₁、および、双線形写像ｅ：Ｇ₁×Ｇ₁→Ｇ₂、を作成し、さらに、Ｐ₁=s₁ＰおよびＰ₂=s₂Ｐを公開の鍵情報の一部として作成する。暗号文の送信者である送信者側装置１２０は、受信者側装置１１０の公開の鍵情報Ｑ、双線形写像ｅを用いて、e(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を計算し、さらに、これらの情報e(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を用いて受信者側装置１１０に送信する暗号文を作成する。
【選択図】図１

Description

本発明は、暗号通信の技術に関する。

公開鍵暗号システムにおいては、ユーザが作成した公開鍵を認証局（ＣＡ）に登録し、証明書を発行してもらう必要がある。すなわち、暗号文の送信者は受信者の公開鍵とその正当性の根拠である証明書を手に入れ、その上で送信するメッセージ文の暗号化を行う必要がある。

これに対して、ＣＡの証明書発行の手間を省いて、より簡単な公開鍵の管理を行うことを目的として、ユーザのＩＤ情報を公開鍵とする暗号システム（以下、ＩＤベース暗号システム）が提案された。

ＩＤベース暗号システムでは、暗号通信、認証（ディジタル署名、個人認証、等）を目的として用途に応じたアルゴリズムが用いられる。

例えば、暗号通信の場合、ユーザは、自身のＩＤ情報を公開鍵として鍵管理センタに登録し、該ＩＤ情報に対応するプライベート鍵を発行してもらう。暗号文の送信者は、受信者の該ＩＤ情報と鍵管理センタが作成したシステム・パラメータを用いて暗号文を作成し、受信者に送信する。受信者は、該プライベート鍵を用いてメッセージの復号化を行う。

公開鍵暗号システムでは、受信者の公開鍵はランダムなビット列であるのに対して、ＩＤベース暗号システムでは、メールアドレス等の個人情報であるため、取り扱いが容易で証明書を不要とすることができる。

多くのＩＤベース暗号方式が提案されたが、安全性の証明が可能な方式は長い間知られていなかったが、２００１年に、非特許文献１において、楕円曲線上の双線形写像の特性を利用することで、安全性の証明が可能な初めてのＩＤベースの暗号通信方式が提案された。非特許文献１の方式では、安全性を高めるために、非特許文献２に記載の変換方法を利用している。

以降、双線形写像を利用した様々な暗号システムが提案されるようになった。非特許文献２では、非特許文献１に記載の暗号通信方式をベースとして階層化されたシステムにおける安全性証明可能な階層的ＩＤベース暗号通信方式が提案された。

非特許文献３では、安全性証明において、タイトなセキュリティ・リダクションを実現するためのアイデアが提案され、非特許文献４では、同アイデアを用いて、タイトなセキュリティ・リダクションをもつＩＤベース暗号方法が具体的に提案された。

Boneh and M. Franklin. Identity Based Encryption From the Weil Pairing, http://crypto.stanford.edu/~dabo/pubs.html E.Fujisaki and T.Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes, Crypto’99, LNCS1666, Springer-Verlag, pp.537554 （1999） C. Gentry and A. Silverberg. Hierarchical ID-based Cryptography, http://eprint.iacr.org/2002/056 J. Katz, N. Wang. Efficiency Improvements for Signature Schemes with Tight Security Reductions, http://www.cs.umd.edu/~jkatz/ N. Attrapadung, J. Furukawa, T. Gomi, G. Hanaoka, H. Imai, R. Zhang. Identity-Based Encryption Schemes with Tight Security Reductions, http://eprint.iacr.org/2005/320

近年提案されている暗号には、その暗号の安全性の証明が可能であるものが多い。すなわち、暗号を破ることの計算量を数論問題などの計算量的複雑性をもつ問題（例えば、素因数分解問題、離散対数問題、Diffie-Hellman 問題、等）に置き換えて定量的に評価する。

セキュリティ・リダクションとは、暗号方式が安全性を証明する場合において、安全性の根拠（暗号学的仮定）とする数論問題の計算量的困難性と暗号方式の安全性の関係を示すひとつのパラメータである。セキュリティ・リダクションがタイトであることは、暗号の安全性が暗号学的仮定とする数論問題の計算量的困難性に近いことを意味する。

このことは、セキュリティ・リダクションの悪い（タイトでない）暗号方式と比較した場合、セキュリティ・リダクションがタイトな方式はより高い安全性を有することを意味し、また、一定の安全性を得るために必要な鍵長を短く設定できるメリットを有する。

ここで、セキュリティ・リダクションがタイトであったとしても、暗号学的仮定に用いられる数論問題の計算量的困難性が期待できないような場合には暗号の安全性に意味はなくなってしまう。よって、より計算量的困難性が期待されているような問題に対して、タイトなセキュリティ・リダクションを持ち、安全性が証明できるような暗号方式が理想的である。

本発明では、十分に計算量的困難性が期待されているＢＤＨ（Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供することを目的とする。

また、さらに、ＢＤＨ問題よりも計算量的に簡単な問題であるＬＢＤＨ（List Bilinear Diffie-Hellman）問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムが既に存在した場合において、暗号部分の入れ替えを行うのではなく、既に使われている暗号を利用しながら、ＢＤＨ問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムに変換する方法を提供することを目的とする。

上記課題を解決するために、本発明では、双線形写像ｅ：Ｇ₁×Ｇ₁→Ｇ₂、Ｐ,Ｑ∈Ｇ₁、に対して、乱数ｓ_１,ｓ_２を選び、Ｐ₁=ｓ_１ＰおよびＰ₂=ｓ_２Ｐを公開の鍵情報の一部として作成し、暗号文の送信者は、e（Ｑ,Ｐ₁）およびe（Ｑ,Ｐ₂）を計算し、これらの値を用いて暗号文を作成する。以下、実現するための公開鍵暗号の一具体例について説明する。

例えば、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、前記受信者側装置又は鍵管理センタ側装置が、乱数ｓ_１,ｓ_２を選択するステップと、公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ₁、および、双線形写像ｅ：Ｇ₁×Ｇ₁→Ｇ₂、を作成するステップと、Ｐ₁=ｓ_１ＰおよびＰ₂=ｓ_２Ｐを公開する鍵情報の一部として作成するステップと、作成したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を、前記送信者側装置に送信するステップと、を備え、前記送信者側装置は、前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ_１、Ｐ_２を受信するステップと、受信したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を用いて、e（Ｑ,Ｐ₁）およびe（Ｑ,Ｐ₂）を計算するステップと、計算されたe（Ｑ,Ｐ₁）およびe（Ｑ,Ｐ₂）を用いて、前記受信者側装置に送信する暗号文を作成するステップと、を備えること、を特徴とする。

また、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、（１）前記受信者側装置が、
素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを作成するステップと、
s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶステップと、

を算出するステップと、
SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ_１,Ｈ_２は、

なるハッシュ関数を意味する。）と、
前期暗号化鍵ＰＫ_Ａを出力するステップと、
を行い、
（２）前期送信者側装置が、
メッセージ文Ｍ∈｛０，１｝ⁿに対して、ｒ∈Ｚ_qをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵ＰＫ_Ａを用いて、

を計算するステップと、
計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SK_Aを用いて、

により、Ｍ∈｛０，１｝ⁿを計算するステップと、

の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと、を特徴とする。

また、本発明は、
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
公開鍵と秘密鍵のペアを複数生成する鍵生成ステップと、
前記鍵生成ステップで生成した複数の公開鍵を含む公開鍵情報を生成するステップと、
前記鍵生成ステップで生成した複数の秘密鍵を含む秘密鍵情報を生成するステップと、
前記送信者側装置が、
前記公開鍵情報を取得するステップと、
前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成するステップと、
前記受信者側装置が、
前記暗号文を取得するステップと、
前記暗号文を前記秘密鍵情報で復号するステップと、
を備えることを特徴とする。

本発明の暗号システムによれば、十分な計算量的困難性を期待されるＢＤＨ（bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつ、安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供することができる。これにより、利便性に優れ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。

また、さらに、既存の暗号システムを利用しながら、新しい暗号方法を提供することが可能であるため、システム入れ替えのためのコストを削減することができ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。

図１は、本発明の第一及び第二の実施形態に共通する通信システム１００の概略図である。

図示するように、通信システム１００は、受信者側装置１１０と、送信者側装置１２０と、を備えており、これらは通信回線１４０に接続されている。

図２は、受信者側装置１１０の概略図である。

図示するように、受信者側装置１１０は、情報を入力する入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置１１０の各部の制御を行う演算部１１２と、記憶部１１５と、通信回線１４０を介して送信者側装置１２０と通信を行う通信部１１６と、情報を出力する出力部１１７と、を備えている。

また、演算部１１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部１１３と、暗復号化処理を行う暗復号化部１１４と、を有する。

図３は、送信者側装置１２０の概略図である。

図示するように、送信者側装置１２０は、情報を入力する入力部１２１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置１２０の各部の制御を行う演算部１２２と、記憶部１２５と、通信回線１４０を介して受信者側装置１１０と通信を行う通信部１２６と、情報を出力する出力部１２７と、を備えている。

また、演算部１２２は、乱数を生成する乱数生成部１２３と、暗復号化処理を行う暗復号化部１２４と、を有する。

上記構成の受信者側装置１１０及び送信者側装置１２０は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１１５、１２５に利用され、通信装置４０８が通信部１１６、１２６に利用され、入力装置４０６や読取装置４０５が入力部１１１、１２１に利用され、そして、出力装置４０７が出力部１１７、１２７に利用される。

この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第一の実施形態）
本発明の第一の実施形態について説明する。

本実施形態では、受信者側装置１１０を用いるユーザＡと送信者側装置１２０を用いるユーザＢが、ユーザＡが受信者側装置１１０において作成した公開鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。

なお、図５は、本発明の第一の実施形態における動作手順を説明するための図である。
１．受信者側装置１１０での処理
受信者側装置１１０において、演算部１１２は、入力部１１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部１１３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを作成する（Ｓ６１０）。

次に、演算部１１２は、鍵情報生成部１１３を用いて、ｓ_１、ｓ_２∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ（Ｓ６１１）。

そして、演算部１１２の鍵情報生成部１１３は、ランダムに選んだｓ_１、ｓ_２及びＰを用いて、

を生成する（Ｓ６１２）。

そして、演算部１１２は、SK_A=（s₁Ｑ,s₂Ｑ）を復号化（秘密）鍵として、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を暗号化（公開）鍵として、両者を記憶部１１５に記憶する（Ｓ６１３）。但し、m,nは自然数、Ｈ_１,Ｈ_２は、

なるハッシュ関数を意味する。

次に、演算部１１２は、Ｓ６１３で生成した暗号化（公開）鍵ＰＫ_Ａ=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を、出力部１１７から出力するか、あるいは、通信部１１６から通信回線１４０を介して送信者側装置１２０に送信する（Ｓ６１４）。なお、出力部１１７から暗号化（公開）鍵ＰＫ_Ａが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫ_Ａを通知する。
２．送信者側装置１２０での処理
送信者側装置１２０の演算部１２２は、通信部１２６が通信回線１４０を介して受信者側装置１１０より受信した、あるいは、ユーザＢが入力部１２１を介して入力した暗号化（公開）鍵ＰＫ_Ａを記憶部１２５に記憶する（Ｓ６１５）。

次に、ユーザＢは、入力部１２１を介してメッセージ文Ｍ∈{0,1}^ｎ（ｎは正整数）を入力する（Ｓ６１６）。

メッセージ文Ｍが入力されると、演算部１２２は、入力されたメッセージ文Ｍを記憶部１２５に記憶する（Ｓ６１７）。

そして、演算部１２２は、乱数生成部１２３を用いて、メッセージＭに対して、r∈Ｚ^* _ｑをランダムに選ぶ（Ｓ６１８）。

次に、演算部１２２は、Ｓ６１６で選択されたｒと、記憶部１２５に記憶されている暗号化（公開）鍵ＰＫ_Ａ及びメッセージＭと、暗復号化部１２４を用いて、

を計算する（Ｓ６１９）。

そして、演算部１２２は、Ｓ６１９で生成した暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）を、出力部１２７から出力するか、あるいは、通信部１２６から通信回線１４０を介して受信者側装置１１０に送信する（Ｓ６２０）。なお、出力部１２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置１１０での処理
受信者側装置１１０の演算部１１２は、通信部１１６が通信回線１４０を介して送信者側装置１２０より受信した、あるいは、ユーザＡが入力部１１１を介して入力した暗号文Ｃを記憶部１１５に記憶する（Ｓ６２１）。

次に、演算部１１２は、暗復号化部１１４を用いて、記憶部１１５に記憶されている暗号文Ｃに対して、記憶部１１５に記憶されているユーザＡの復号（秘密）鍵ＳＫ_Ａから、

により、Ｍ∈｛０，１｝^ｎを計算する（Ｓ６２２）。

さらに、演算部１１２は、Ｓ２２での計算結果であるＭと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、

の検査式が成立するか否かを検査する（Ｓ６２３）。この検査式が成立する場合には、Ｓ２０での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）を不正な暗号文とみなして棄却する。

実施例１に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-CCA2の意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CCA2の意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。

本実施例における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。

また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
（第二の実施形態）
次に、本発明の第二の実施形態について説明する。本実施形態は、第一の実施形態の変形例である。

図６は、本発明の第二の実施形態における動作手順を説明するための図である。
１．受信者側装置１１０での処理
受信者側装置１１０において、演算部１１２は、入力部１１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部１１３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを作成する（Ｓ６３０）。

次に、演算部１１２は、鍵情報生成部１１３を用いて、s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ（Ｓ６３１）。

そして、演算部１１２の鍵情報生成部１１３は、ランダムに選んだｓ_１、ｓ_２及びＰを用いて、

を生成する（Ｓ６３２）。

そして、演算部１１２は、SK_A=（s₁Ｑ,s₂Ｑ）を復号化（秘密）鍵として、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３）を暗号化（公開）鍵として、両者を記憶部１１５に記憶する（Ｓ６３３）。但し、m,nは自然数、Ｈ_１,Ｈ_２,Ｈ_３は、

なるハッシュ関数を意味する。

次に、演算部１１２は、Ｓ６３３で生成した暗号化（公開）鍵をPK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３）を、出力部１１７から出力するか、あるいは、通信部１１６から通信回線１４０を介して送信者側装置１２０に送信する（Ｓ６３４）。なお、出力部１１７から暗号化（公開）鍵ＰＫ_Ａが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫ_Ａを通知する。
２．送信者側装置１２０での処理
送信者側装置１２０の演算部１２２は、通信部１２６が通信回線１４０を介して受信者側装置１１０より受信した、あるいは、ユーザＢが入力部１２１を介して入力した暗号化（公開）鍵ＰＫ_Ａを記憶部１２５に記憶する（Ｓ６３５）
次に、ユーザＢは、入力部１２１を介してメッセージ文Ｍ∈{0,1}^ｎ（ｎは正整数）を入力する（Ｓ６３６）。

メッセージ文Ｍが入力されると、演算部１２２は、入力されたメッセージ文Ｍを記憶部１２５に記憶する（Ｓ６３７）。

そして、演算部１２２は、乱数生成部１２３を用いて、メッセージＭに対して、σ∈{0,1}^mをランダムに選ぶ（Ｓ６３８）。

次に、演算部１２２は、Ｓ６３８で選択されたσを用いて、

を計算する（Ｓ６３９）。

そして、演算部１２２は、Ｓ６３９で計算されたｒと、記憶部１２５に記憶されている暗号化（公開）鍵ＰＫ_Ａ及びメッセージＭと、暗復号化部１２４を用いて、

を計算する（Ｓ６４０）。

そして、演算部１２２は、Ｓ６４０で生成した暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）を、出力部１２７から出力するか、あるいは、通信部１２６から通信回線１４０を介して受信者側装置１１０に送信する（Ｓ６４１）。なお、出力部１２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置１１０での処理
受信者側装置１１０の演算部１１２は、通信部１１６が通信回線１４０を介して送信者側装置１２０より受信した、あるいは、ユーザＡが入力部１１１を介して入力した暗号文Ｃを記憶部１１５に記憶する（Ｓ６４２）。

次に、演算部１１２は、暗復号化部１１４を用いて、記憶部１１５に記憶されている暗号文Ｃに対して、記憶部１１５に記憶されているユーザＡの復号（秘密）鍵ＳＫ_Ａから、

により、σ∈｛０，１｝^ｍを計算する（Ｓ６４３）。

さらに、演算部１１２は、Ｓ４３での計算結果であるσと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、

により、Ｍ∈｛０，１｝^ｎを計算する（Ｓ６４４）。

さらに、演算部１１２は、Ｓ６４４での計算結果であるＭと、Ｓ６４３での計算結果であるσと、から、

により、r∈Ｚ_qを計算する（Ｓ６４５）。

そして、演算部１１２は、Ｓ６４５での計算結果ｒと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、

の検査式が成立するか否かを検査する（Ｓ６４６）。この検査式が成立する場合には、Ｓ６４４での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）を不正な暗号文とみなして棄却する。

第二の実施形態に記載の公開鍵暗号通信方法は、第一の実施形態の場合と同様、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。また、タイトなセキュリティ・リダクションをもつことも第一の実施形態の場合と同様に示される。

図７は、本発明の第三及び第四の実施形態に共通する通信システム２００の概略図である。

図示するように、通信システム２００は、受信者側装置２１０Ａと、送信者側装置２１０Ｂと、鍵管理センタ側装置２３０と、を備えており、これらは通信回線１４０に接続されている。

図８は、受信者側装置２１０Ａ及び送信者側装置２１０Ｂの概略図である。本実施形態における受信者側装置２１０Ａ及び送信者側装置２１０Ｂは、同様の構成を有している。

図示するように、受信者側装置２１０Ａ及び送信者側装置２１０Ｂは、情報を入力する入力部２１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置２１０Ａ又は送信者側装置２１０Ｂの各部の制御を行う演算部２１２と、記憶部２１５と、通信回線１４０を介して通信を行う通信部２１６と、情報を出力する出力部２１７と、を備えている。

また、演算部２１２は、乱数を生成する乱数生成部２１３と、暗復号化処理を行う暗復号化部２１４と、を有する。

図９は、鍵管理センタ側装置２３０の概略図である。

図示するように、鍵管理センタ側装置２３０は、情報を入力する入力部２３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置２３０の各部の制御を行う演算部２３２と、記憶部２３４と、通信回線１４０を介して受信者側装置２１０Ａ及び送信者側装置２１０Ｂと通信を行う通信部２３５と、情報を出力する出力部２３６と、を備えている。

また、演算部２３２は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部２３３を有する。

上記構成の受信者側装置２１０Ａ、送信者側装置２１０Ｂ及び鍵管理センタ側装置２３０についても、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部２１５、２３４に利用され、通信装置４０８が通信部２１６、２３５に利用され、入力装置４０６や読取装置４０５が入力部２１１、２３１に利用され、そして、出力装置４０７が出力部２１７、２３６に利用される。

この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第三の実施形態）
本発明の第三の実施形態について説明する。

本実施形態では、受信者側装置２１０Ａを用いるユーザＡと、送信者側装置２１０Ｂを用いるユーザＢと、が、鍵管理センタ側装置２３０が作成した鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。

なお、図１０は、本発明における第三の実施形態における動作手順を説明するための図である。
１．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、入力部２３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部２３３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを生成する（Ｓ６５０）。

次に、演算部２３２は、鍵情報生成部２３３を用いて、s₀,s₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ（Ｓ６５１）。

そして、演算処理部２３２の鍵情報生成部２３３は、ランダムに選んだｓ_０、ｓ_１及びＰを用いて、

を生成する（Ｓ６５２）。

そして、演算部２３２は、s＝（s₀,s₁）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部２３４に記憶する（Ｓ６５３）。但し、ｌ,ｍ,ｎは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、

なるハッシュ関数を意味する。

次に、演算部２３２は、Ｓ６５３で生成したシステムパラメータＰＫを、出力部２３６から出力するか、あるいは、通信部２３５から通信回線１４０を介して送信者側端末２１０Ｂに送信する（Ｓ６５４）。なお、出力部２３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、入力部２１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤ_Aを記憶部２１５に記憶するとともに、通信回線１４０を介して通信部２１６から鍵管理センタ側装置２３０に送信する（Ｓ６５５）。なお、ユーザＡの個別情報ＩＤ_Aについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置２１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、通信部２３５が通信回線１４０を介して受信者側装置２１０Ａより受信した、あるいは、入力部２３１を介して受信者側装置２１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤ_Ａを、受信者側装置２１０Ａのアドレスに対応付けて記憶部２３４に記憶する（Ｓ６５６）。

そして、演算部２３２は、鍵情報生成部２３３を用いて、ｂ_IDA∈{0,1}をランダムに選ぶ（Ｓ６５７）。

次に、演算部２３２は、鍵情報生成部２３３を用いて、記憶部２３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤ_Ａから、

を計算する（Ｓ６５８）。

そして、演算部２３２は、ＳＫ_Ａ＝（ｂ_IDA,d_IDA,0,d_IDA,1）をユーザＡのプライベート鍵として、出力部２３６から出力するか、あるいは、通信回線１４０を介して通信部２３５から受信者側装置２１０Ａに安全な方法（例えば、鍵管理センタ側装置２３０が受信者側装置２１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ６５９）。なお、出力部２３６からプライベート鍵ＳＫ_Ａが出力された場合には、鍵管理センタはＩＣカードの郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫ_Ａを通知する。
４．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたプライベート鍵ＳＫ_Ａを、記憶部２１５に記憶する（Ｓ６６０）。

また、演算部２１２は、ユーザＡから入力部２１１を介してユーザＡの個別情報ＩＤ_Ａの送信指示を受けると、通信回線１４０を介して通信部２１６からユーザＡの個別情報ＩＤ_Ａを送信する（Ｓ６６１）。
５．送信者側装置２１０Ｂでの処理
送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたシステムパラメータＰＫを、記憶部２１５に記憶する（Ｓ６６２）。

また、送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して受信側装置２１０Ａより受信した、あるいは、入力部２１１を介して入力されたユーザＡの個別情報ＩＤ_Ａを、記憶部２１５に記憶する（Ｓ６６３）。

次に、ユーザＢは、入力部２１１を介してメッセージ文Ｍ∈{0,1}^ｎ（ｎは正整数）を入力する（Ｓ６６４）。

メッセージ文Ｍが入力されると、演算部２１２は、入力されたメッセージＭを記憶部２１５に記憶する（Ｓ６６５）。

そして、演算部２１２は、乱数生成部２１３を用いて、Ｒ∈｛０，１｝^lをランダムに選ぶ（Ｓ６６６）。

次に、演算部２１２は、Ｓ６６６で選択されたＲと、記憶部２１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤ_Ａ及びユーザＢの個別情報ＩＤ_Ｂと、を用いて、

なるｒ∈Ｚ_qおよびＫ∈｛０，１｝^mを計算する（Ｓ６６７）。

さらに、演算部２１２は、Ｓ６６７で計算されたｒ及びＫを用いて、

を計算する（Ｓ６６８）。

そして、演算部２１２は、Ｓ６６８で作成した暗号文Ｃ＝（Ｕ,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を出力部２１７から出力するか、あるいは、通信回線１４０を介して通信部２１６から受信者側装置２１０Ａに送信する（Ｓ６６９）。なお、出力部２１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａの演算部２１２は、通信部２１６が通信回線１４０を介して送信者側装置２１０Ｂより受信した、あるいは、ユーザＡが入力部２１１を介して入力した暗号文Ｃを記憶部２１５に記憶する（Ｓ６７０）。

次に、演算部２１２は、暗復号化部２１４を用いて、記憶部２１５に記憶されている暗号文Ｃに対して、記憶部２１５に記憶されているユーザＡの個別情報ＩＤ_Ａ及びプライベート鍵ＳＫ_Ａから、

なるＲ∈｛０，１｝^lを計算する（Ｓ６７１）。

さらに、演算部２１２は、Ｓ７１で計算されたＲと、記憶部２１５に記憶されているユーザＡの個別情報ＩＤ_Ａ及びユーザＢの個別情報ＩＤ_Ｂと、を用いて、

により、ｒ∈Ｚ_qおよびＫ∈｛０，１｝^mを計算する（Ｓ６７２）。

次に、演算部２１２は、Ｓ６７２で計算されたＫを用いて、

により、Ｍ∈｛０，１｝ⁿを計算する（Ｓ６７３）。

そして、演算部２１２は、Ｓ６７１で計算されたＲと、Ｓ６７２で計算されたｒと、Ｓ６７３で計算されたＭと、暗号文Ｃと、から、

の検査式が成立するか否かを検査する（Ｓ６７４）。この検査式が成立する場合には、Ｓ６７３での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を不正な暗号文とみなして棄却する。

第三の実施形態に記載のＩＤベース暗号通信方法は、非特許文献４に記載の手法と同様の手法により、List Bilinear Diffie-Hellman（LBDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。

このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでLBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のＩＤベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。

また、本実施例の方式は、非特許文献４に記載の方式よりも、暗号化処理において、計算量の多い双線形写像の計算がひとつ少ないため、より高速な暗号化処理を実現できる。本実施形態における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。

本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
（第四の実施形態）
本発明の第四の実施形態について説明する。

本実施形態は、第三の実施形態に比べて、鍵長は長くなるが、暗号化及び復号化処理の高速性に優れる方式である。

なお、図１１は、本発明における第四の実施形態における動作手順を説明するための図である。
１．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、入力部２３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部２３３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを生成する（Ｓ６８０）。

次に、演算部２３２は、鍵情報生成部２３３を用いて、s₁₀,s₁₁,s₂₀,s₂₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ（Ｓ６８１）。

そして、演算処理部２３２の鍵情報生成部２３３は、ランダムに選んだｓ_１０、ｓ_１１、ｓ_２０、ｓ_２１及びＰを用いて、

を生成する（Ｓ６８２）。

そして、演算部２３２は、s＝（s₁₀,s₁₁,s₂₀,s₂₁）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,10,Ｐ_pub,11,Ｐ_pub,1,Ｐ_pub,20,Ｐ_pub,21,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部２３４に記憶する（Ｓ６８３）。但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、

なるハッシュ関数を意味する。

次に、演算部２３２は、Ｓ８３で生成したシステムパラメータＰＫを、出力部２３６から出力するか、あるいは、通信部２３５から通信回線１４０を介して送信者側端末２１０Ｂに送信する（Ｓ６８４）。なお、出力部２３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、入力部２１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤ_Aを記憶部２１５に記憶するとともに、通信回線１４０を介して通信部２１６から鍵管理センタ側装置２３０に送信する（Ｓ６８５）。なお、ユーザＡの個別情報ＩＤ_Aについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置２１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、通信部２３５が通信回線１４０を介して受信者側装置２１０Ａより受信した、あるいは、入力部２３１を介して受信者側装置２１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤ_Ａを、受信者側装置２１０Ａのアドレスに対応付けて記憶部２３４に記憶する（Ｓ６８６）。

そして、演算部２３２は、鍵情報生成部２３３を用いて、ｂ_IDA∈{0,1}をランダムに選ぶ（Ｓ６８７）。

次に、演算部２３２は、鍵情報生成部２３３を用いて、記憶部２３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤ_Ａから、

を計算する（Ｓ６８８）。但し、εはシステムに固有のストリングで予め定められているものとする。

さらに、演算部２３２は、ＳＫ_Ａ＝（ｂ_IDA,d_（1,IDA）,d_（2,IDA））をユーザＡのプライベート鍵として、出力部２３６から出力するか、あるいは、通信回線１４０を介して通信部２３５から受信者側装置２１０Ａに安全な方法（例えば、鍵管理センタ側装置２３０が受信者側装置２１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ６８９）。なお、出力部２３６からプライベート鍵ＳＫ_Ａが出力された場合には、鍵管理センタはＩＣカードを梱包した郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫ_Ａを通知する。
４．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたプライベート鍵ＳＫ_Ａを、記憶部２１５に記憶する（Ｓ６９０）。

また、演算部２１２は、ユーザＡから入力部２１１を介してユーザＡの個別情報ＩＤ_Ａの送信指示を受けると、通信回線１４０を介して通信部２１６からユーザＡの個別情報ＩＤ_Ａを送信する（Ｓ６９１）。
５．送信者側装置２１０Ｂでの処理
送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたシステムパラメータＰＫを、記憶部２１５に記憶する（Ｓ６９２）。

また、送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して受信側装置２１０Ａより受信した、あるいは、入力部２１１を介して入力されたユーザＡの個別情報ＩＤ_Ａを、記憶部２１５に記憶する（Ｓ６９３）。

次に、ユーザＢは、入力部２１１を介してメッセージ文Ｍ∈{0,1}^ｎ（ｎは正整数）を入力する（Ｓ６９４）。

メッセージ文Ｍが入力されると、演算部２１２は、入力されたメッセージＭを記憶部２１５に記憶する（Ｓ６９５）。

そして、演算部２１２は、乱数生成部２１３を用いて、Ｒ∈｛０，１｝^lをランダムに選ぶ（Ｓ６９６）。

次に、演算部２１２は、Ｓ６９６で選択されたＲと、記憶部２１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤ_Ａ及びユーザＢの個別情報ＩＤ_Ｂと、を用いて、

なるｒ₀,r₁∈Ｚ_qおよびＫ∈｛０，１｝^mを計算する（Ｓ６９７）。

さらに、演算部２１２は、Ｓ６９７で計算されたｒ_０、ｒ_１及びＫを用いて、

を計算する（Ｓ６９８）。

そして、演算部２１２は、Ｓ９８で作成した暗号文Ｃ＝（Ｕ₁₀,Ｕ₁₁,Ｕ₂₀,Ｕ₂₁,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を出力部２１７から出力するか、あるいは、通信回線１４０を介して通信部２１６から受信者側装置２１０Ａに送信する（Ｓ６９９）。なお、出力部２１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａの演算部２１２は、通信部２１６が通信回線１４０を介して送信者側装置２１０Ｂより受信した、あるいは、ユーザＡが入力部２１１を介して入力した暗号文Ｃを記憶部２１５に記憶する（Ｓ７００）。

次に、演算部２１２は、暗復号化部２１４を用いて、記憶部２１５に記憶されている暗号文Ｃに対して、記憶部２１５に記憶されているユーザＡの個別情報ＩＤ_Ａ及びプライベート鍵ＳＫ_Ａから、

なるＲ∈｛０，１｝^lを計算する（Ｓ７０１）。

さらに、演算部２１２は、Ｓ７０１で計算されたＲと、記憶部２１５に記憶されているユーザＡの個別情報ＩＤ_Ａ及びユーザＢの個別情報ＩＤ_Ｂと、を用いて、

により、ｒ₀,r₁∈Ｚ_qおよびＫ∈｛０，１｝^mを計算する（Ｓ７０２）。

次に、演算部２１２は、

なるＲ’∈｛０，１｝^lを計算する（Ｓ７０３）。

そして、演算部２１２は、Ｓ７０１で計算されたＲと、Ｓ７０２で計算されたｒと、Ｓ７０３で計算されたＲ’と、暗号文Ｃと、から、

の検査式が成立するか否かを検査する（Ｓ７０４）。

そして、この検査式が成立する場合には、

を計算する（Ｓ７０５）。

さらに、演算部２１２は、

の検査式が成立するか否かを検査する（Ｓ７０６）。この検査式が成立する場合には、Ｓ７３での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ₁₀,Ｕ₁₁,Ｕ₂₀,Ｕ₂₁,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を不正な暗号文とみなして棄却する。

本実施形態の暗号方式では、非特許文献１および非特許文献４に記載の手法と同様の手法により、BDH（Bilinear Diffie-Hellman）問題の計算量的困難性を暗号学的仮定にしてIND-ID-CCA安全であることが証明可能である。

このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のＩＤベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。

本実施形態のＩＤベース暗号方式は、計算量の大きい双線形写像を用いた計算が少ないため、効率の良い暗号化および復号化が可能である。

本実施形態における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。

また、本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。

上記実施形態では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびＩＤベース暗号が使われている様々なシステムに適用することが可能である。

また、以上に記載した実施形態における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。

図１２は、本発明の第五、第六、第七及び第八の実施形態に共通する通信システム８００の概略図である。

図示するように、通信システム８００は、受信者側装置８１０と、送信者側装置８２０と、を備えており、これらは通信回線１４０に接続されている。

図１３は、受信者側装置８１０の概略図である。

図示するように、受信者側装置８１０は、情報を入力する入力部８１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置８１０の各部の制御を行う演算部８１２と、記憶部８１５と、通信回線１４０を介して送信者側装置８２０と通信を行う通信部８１６と、情報を出力する出力部８１７と、を備えている。

また、演算部８１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部８１３と、暗復号化処理を行う暗復号化部８１４と、を有する。

図１４は、送信者側装置８２０の概略図である。

図示するように、送信者側装置８２０は、情報を入力する入力部８２１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置８２０の各部の制御を行う演算部８２２と、記憶部８２５と、通信回線１４０を介して受信者側装置８１０と通信を行う通信部８２６と、情報を出力する出力部８２７と、を備えている。

また、演算部８２２は、乱数を生成する乱数生成部８２３と、暗復号化処理を行う暗復号化部８２４と、を有する。

上記構成の受信者側装置８１０及び送信者側装置８２０は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部８１５、８２５に利用され、通信装置４０８が通信部８１６、８２６に利用され、入力装置４０６や読取装置４０５が入力部８１１、８２１に利用され、そして、出力装置４０７が出力部８１７、８２７に利用される。

この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第五の実施形態）
図１５は、本発明の第五の実施形態における動作手順を説明するための図である。

本実施形態は、通信回線１４０を介して、受信者側装置８１０と、送信者側装置８２０と、の間で暗号通信を行う暗号システムに関するものであり、公開鍵暗号（以下、暗号方式ＰＫＥ）が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方法を利用しながら別の暗号システム（より安全性の高い暗号システム）を構築する場合について述べる。

なお、本実施形態における受信者側装置８１０及び送信者側装置８２０は、ある共通の暗号方式に対応しているものとする。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＳＫ_１），（ＰＫ_２，ＳＫ_２）を生成する（Ｓ１０００）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、

を新しい公開鍵として公開し（但し、ｎは負でない整数）（Ｓ１００１）、

を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１００２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１００３）。

次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ（ｎは、公開鍵として公開されている負でない整数）を入力する（Ｓ１００４）。

メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１００５）。

次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選ぶ（Ｓ１００６）。

そして、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１００７）。但し、Ｅ_ＰＫ（ｘ）は、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。

さらに、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１００８）。

そして、送信者側装置８２０の演算部８２２は、ステップＳ１００８で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１００９）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０１０）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部８１２は、暗復号化部８１４を用いて、

を計算する（Ｓ１０１１）。但し、Ｄ_ＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。

そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、

を計算することで、メッセージＭを復号する（Ｓ１０１２）。

本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
（第六の実施形態）
次に、本発明の第六の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、第五の実施形態よりも安全性の高い暗号システムを提供するものである。

図１６は、本発明の第六の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＳＫ_１），（ＰＫ_２，ＳＫ_２）を生成する（Ｓ１０２０）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、

を新しい公開鍵として公開し（但し、ｎ_１，ｎ_２，ｎ_３は負でない整数）（Ｓ１０２１）、

を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１０２２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１０２３）。

次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ_１（ｎ_１は、公開鍵として公開されている負でない整数）を入力する（Ｓ１０２４）。

メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０２５）。

次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選び、また、Ｒ_１，Ｒ_２∈｛０，１｝^ｍ、ｍ＝ｎ_２（ｎ_２は、公開鍵として公開されている負でない整数）をランダムに選ぶ（Ｓ１０２６）。

そして、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１０２７）。但し、Ｅ_ＰＫ（ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。即ち、暗号文が乱数Ｒによって変わってくるようにする。

次に、演算部８２２は、乱数生成部８２３を用いて、τ∈{0,1}^ｍ、ｍ＝ｎ_３（ｎ_３は、公開鍵として公開されている負でない整数）をランダムに選び（Ｓ１０２８）、さらに、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１０２９）。

そして、送信者側装置８２０の演算部８２２は、ステップＳ１０２９で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１０３０）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０３１）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部８１２は、暗復号化部８１４を用いて、

を計算する（Ｓ１０３２）。但し、Ｄ_ＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。

そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、

を計算し（Ｓ１０３３）、さらに、Ｍ∈{0,1}^ｍ（ｍ＝ｎ_１）、Ｒ_１，Ｒ_２∈｛０，１｝^ｍ（ｍ＝ｎ_２）、τ∈{0,1}^ｍ（ｍ＝ｎ_３）を計算し、

を検査する（Ｓ１０３４）。

そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。

本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。

本実施例の方法では、Bilinear Diffie-Hellman（BDH）問題の数学的性質であるランダム自己帰着性を利用するために、二重暗号の技術を用いる。ここで、二重暗号とは、既存の暗号システムによる暗号化および復号化を２度行うことを意味している。これにより、実施例１に記載の公開鍵暗号通信方法は、既存の暗号方式がＬＢＤＨ（List Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ（Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第七の実施形態）
次に、本発明の第七の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、非特許文献２に記載の変換方法を利用するものである。

図１７は、本発明の第七の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＳＫ_１），（ＰＫ_２，ＳＫ_２）を生成する（Ｓ１０４０）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、

を新しい公開鍵として公開し（但し、ｎ_１，ｎ_２，ｎ_３は負でない整数）（Ｓ１０４１）、

を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１０４２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１０４３）。

次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ_１（ｎ_１は、公開鍵として公開されている負でない整数）を入力する（Ｓ１０４４）。

メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０４５）。

次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選び、また、ｒ_１，ｒ_２∈｛０，１｝^ｍ、ｍ＝ｎ_２（ｎ_２は、公開鍵として公開されている負でない整数）をランダムに選ぶ（Ｓ１０４６）。

そして、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１０４７）。

さらに、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１０４８）。但し、Ｅ_ＰＫ（ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。即ち、暗号文が乱数Ｒによって変わってくるようにする。

次に、演算部８２２は、乱数生成部８２３を用いて、τ∈{0,1}^ｍ、ｍ＝ｎ_３（ｎ_３は、公開鍵として公開されている負でない整数）をランダムに選び（Ｓ１０４９）、さらに、演算部８２２は、暗復号化部８２４を用いて、

を計算する（Ｓ１０５０）。

そして、送信者側装置８２０の演算部８２２は、ステップＳ１０５０で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１０５１）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０５２）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部８１２は、暗復号化部８１４を用いて、

を計算する（Ｓ１０５３）。但し、Ｄ_ＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。

そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、

を計算し（Ｓ１０５４）、さらに、Ｍ∈{0,1}^ｍ（ｍ＝ｎ_１）、ｒ_１，ｒ_２∈｛０，１｝^ｍ（ｍ＝ｎ_２）、τ∈{0,1}^ｍ（ｍ＝ｎ_３）を計算し、

を検査する（Ｓ１０５５）。

そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。

本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。

また、第五及び第六の実施形態の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第八の実施形態）
本実施形態では、受信者側装置８１０を用いるユーザＡと送信者側装置８２０を用いるユーザＢとが通信を行う通信システム８００において、送信者側装置８２０のユーザＢが、ユーザＡの受信者側装置８１０において作成された公開鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。

図１８は、本発明の第八の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを作成する（Ｓ１０６０）。

次に、演算部８１２は、鍵情報生成部８１３を用いて、ｓ₁,ｓ₂∈Ｚ_qおよびＰ∈Ｇ₁をランダムに選ぶ（Ｓ１０６１）。

そして、演算部８１２の鍵情報生成部８１３は、ランダムに選んだｓ_１、ｓ_２及びＰを用いて、

を生成する（Ｓ１０６２）。

そして、演算部８１２は、ＳＫ_A=（ｄ_IDA,1,ｄ_IDA,2）を復号化（秘密）鍵として、ＰＫ_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,ＩＤ_A,Ｈ_１,Ｈ_２）を暗号化（公開）鍵として、両者を記憶部８１５に記憶する（Ｓ１０６３）。但し、

であり，ｍ,ｎは自然数、ＩＤ_A∈{０，１}^m，Ｈ_１,Ｈ_２は、

なるハッシュ関数を意味する。

次に、演算部８１２は、暗号化（公開）鍵ＰＫ_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,ＩＤ_A,Ｈ_１,Ｈ_２）を、出力部８１７から出力するか、あるいは、通信部８１６から通信回線１４０を介して送信者側装置８２０に送信する（Ｓ１０６４）。なお、出力部８１７から暗号化（公開）鍵ＰＫ_Ａが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫ_Ａを通知する。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６が通信回線１４０を介して受信者側装置８１０より受信した、あるいは、ユーザＢが入力部８２１を介して入力した暗号化（公開）鍵ＰＫ_Ａを記憶部８２５に記憶する（Ｓ１０６５）。

次に、ユーザＢは、入力部８２１を介してメッセージ文Ｍ∈{０，１}^ｎ（ｎは正整数）を入力する（Ｓ１０６６）。

メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０６７）。

そして、演算部８２２は、乱数生成部８２３を用いて、メッセージＭに対して、ｒ∈Ｚ_ｑをランダムに選び（Ｓ１０６８）、

を計算する。さらに，記憶部１２５に記憶されている暗号化（公開）鍵ＰＫ_Ａ及びメッセージＭと、暗復号化部１２４を用いて、

を計算し，さらに，

を計算する（Ｓ１０６９）。

そして、演算部１２２は、暗号文Ｃ＝（Ｕ，Ｖ₀，Ｖ₁）を、出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して受信者側装置８１０に送信する（Ｓ１０７０）。なお、出力部８２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、ユーザＡが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０７１）。

次に、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、記憶部８１５に記憶されているユーザＡの復号（秘密）鍵ＳＫ_Ａから、

を計算し（Ｓ１０７２），

により、Ｍ∈｛０，１｝^ｎを計算する（Ｓ１０７３）。

本実施例に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、ＩＮＤ−ＣＰＡの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。

本実施例における暗号通信方法は，下記非特許文献６、７に記載の方法などを用いることにより，ＩＮＤ−ＣＣＡの意味での安全に強化することが可能である。
非特許文献６：E. Fujisaki and T. Okamoto: How to enhance the security of the public-key encryption at minimum cost, PKC1999, LNCS 1560. pp.53-68, Springer-Verlag, 1999.
非特許文献７：E. Fujisaki and T. Okamoto: Secure integration of asymmetric and symmetric encryption schemes, Crypto’99, LNCS 1666. pp.537-554, Springer-Verlag, 1999.
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。

また，本実施例の暗号方式において、（（１３６）式における）Ｖ_0、Ｖ₁の作成方法として、Ｈ₂（ＩＤ||ｉ，ｖ_i,1，ｖ_i,2）を用いて共通鍵暗号における暗号化鍵Ｋを作成し、鍵Ｋを用いてメッセージ文Ｍを（該共通鍵暗号を用いて）暗号化することで、Ｖ₀，Ｖ₁を作成することも可能である．
図１９は、本発明の第九、第十、第十一及び第十二の実施形態に共通する通信システム９００の概略図である。

図示するように、通信システム９００は、受信者側装置９１０Ａと、送信者側装置９１０Ｂと、鍵管理センタ側装置９３０と、を備えており、これらは通信回線１４０に接続されている。

図２０は、受信者側装置９１０Ａ及び送信者側装置９１０Ｂの概略図である。本実施形態における受信者側装置９１０Ａ及び送信者側装置９１０Ｂは、同様の構成を有している。

図示するように、受信者側装置９１０Ａ及び送信者側装置９１０Ｂは、情報を入力する入力部９１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置９１０Ａ又は送信者側装置９１０Ｂの各部の制御を行う演算部９１２と、記憶部９１５と、通信回線１４０を介して通信を行う通信部９１６と、情報を出力する出力部９１７と、を備えている。

また、演算部９１２は、乱数を生成する乱数生成部９１３と、暗復号化処理を行う暗復号化部９１４と、を有する。

図２１は、鍵管理センタ側装置９３０の概略図である。

図示するように、鍵管理センタ側装置９３０は、情報を入力する入力部９３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置９３０の各部の制御を行う演算部９３２と、記憶部９３４と、通信回線１４０を介して受信者側装置９１０Ａ又は送信者側装置９１０Ｂと通信を行う通信部９３５と、情報を出力する出力部９３６と、を備えている。

また、演算部９３２は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部９３３を有する。

上記構成の受信者側装置９１０Ａ、送信者側装置９１０Ｂ及び鍵管理センタ側装置９３０についても、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部９１５、９３４に利用され、通信装置４０８が通信部９１６、９３５に利用され、入力装置４０６や読取装置４０５が入力部９１１、９３１に利用され、そして、出力装置４０７が出力部９１７、９３６に利用される。

この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第九の実施形態）
図２２は、本発明の第九の実施形態における動作手順を説明するための図である。本実施形態では、第五の実施形態における方法をＩＤベース暗号に適用したものである。そして、第五の実施形態と同様に、ＩＤベース暗号（以下、暗号方式ＩＢＥ）が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方式ＩＢＥを利用しながら別の暗号システム（より安全性の高い暗号システム）を構築する場合について述べる。

なお、本実施形態における受信者側装置９１０Ａ、送信者側装置９１０Ｂ及び鍵管理センタ側装置９３０は、ある共通の暗号方式ＩＢＥに対応しているものとする。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＭＳＫ_１），（ＰＫ_２，ＭＳＫ_２）を生成する（Ｓ１０８０）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、

をシステムパラメータとして公開し（但し、ｎは負でない整数）（Ｓ１０８１）、

を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１０８２）。

そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}^ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫ_ＩＤ，１，ＳＫ_ＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫ_ＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１０８３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１０８４）。

次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}^ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１０８５）。

メッセージ文ＭとＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１０８６）。

次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選ぶ（Ｓ１０８７）。

そして、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１０８８）。但し、Ｅ_ＰＫ（ｘ）は、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。

さらに、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１０８９）。

そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１０８９で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１０９０）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫ_ＩＤを取得して、記憶部９１５に記憶する（Ｓ１０９１）。

また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１０９２）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１０９３）。但し、Ｄ_ＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫ_ＩＤを用いて復号化した結果を表す。

そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、

を計算することで、メッセージＭを復号する（Ｓ１０９４）。

本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
（第十の実施形態）
図２３は、本発明の第十の実施形態における動作手順を説明するための図である。本実施形態では、第六の実施形態における方法をＩＤベース暗号に適用したものである。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＭＳＫ_１），（ＰＫ_２，ＭＳＫ_２）を生成する（Ｓ１１００）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、

をシステムパラメータとして公開し（但し、ｎ_１，ｎ_２，ｎ_３，ｎ_４は負でない整数）（Ｓ１１０１）、

を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１１０２）。

そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}^ｍ、ｍ＝ｎ_４（ｎ_４は、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫ_ＩＤ，１，ＳＫ_ＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫ_ＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１１０３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１１０４）。

次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ_１（ｎ_１は、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}^ｍ、ｍ＝ｎ_４（ｎ_４は、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１１０５）。

メッセージ文Ｍ及びＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１１０６）。

次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選び、また、Ｒ_１，Ｒ_２∈｛０，１｝^ｍ、ｍ＝ｎ_２ｍ＝ｎ_２（ｎ_２は、システムパラメータとして公開されている負でない整数）をランダムに選ぶ（Ｓ１１０７）。

そして、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１０８）。但し、Ｅ_ＰＫ（ＩＤ，ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。

さらに、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１０９）。

そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１０８９で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１１１０）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫ_ＩＤを取得して、記憶部９１５に記憶する（Ｓ１１１１）。

また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１１２）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１１３）。但し、Ｄ_ＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫ_ＩＤを用いて復号化した結果を表す。

そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、

を計算し（Ｓ１１１４）、さらに、Ｍ∈{0,1}^ｍ（ｍ＝ｎ_１）、Ｒ_１，Ｒ_２∈｛０，１｝^ｍ（ｍ＝ｎ_２）、τ∈{0,1}^ｍ（ｍ＝ｎ_３）を計算し、

を検査する（Ｓ１１１５）。

そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。

本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施形態では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。

また、実施例１の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第十一の実施形態）
図２４は、本発明の第十一の実施形態における動作手順を説明するための図である。本実施形態では、第七の実施形態における方法をＩＤベース暗号に適用したものである。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ_１，ＭＳＫ_１），（ＰＫ_２，ＭＳＫ_２）を生成する（Ｓ１１２０）。

次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、

をシステムパラメータとして公開し（但し、ｎ_１，ｎ_２，ｎ_３，ｎ_４は負でない整数）（Ｓ１１２１）、

を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１１２２）。

そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}^ｍ、ｍ＝ｎ_４（ｎ_４は、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫ_ＩＤ，１，ＳＫ_ＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫ_ＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１１２３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１１２４）。

次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}^ｍ、ｍ＝ｎ_１（ｎ_１は、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}^ｍ、ｍ＝ｎ_４（ｎ_４は、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１１２５）。

メッセージ文Ｍ及びＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１１２６）。

次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ_１，σ_２をランダムに選び、また、ｒ_１，ｒ_２∈｛０，１｝^ｍ、ｍ＝ｎ_２（ｎ_２は、システムパラメータとして公開されている負でない整数）をランダムに選ぶ（Ｓ１１２７）。

そして、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１２８）。

さらに、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１２９）。但し、Ｅ_ＰＫ（ＩＤ，ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。

さらに、演算部９１２は、乱数生成部９１３を用いて、τ∈｛０，１｝^ｍ、ｍ＝ｎ_３（ｎ_３は、システムパラメータとして公開されている負でない整数）をランダムに選び、暗復号化部９１４を用いて、

を計算する（Ｓ１１３０）。

そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１１３０で生成した暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１１３１）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫ_ＩＤを取得して、記憶部９１５に記憶する（Ｓ１１３２）。

また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１３３）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ_１，Ｕ_２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。

次に、演算部９１２は、暗復号化部９１４を用いて、

を計算する（Ｓ１１３４）。但し、Ｄ_ＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫ_ＩＤを用いて復号化した結果を表す。

そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、

を計算し（Ｓ１１３５）、さらに、Ｍ∈{0,1}^ｍ（ｍ＝ｎ_１）、Ｒ_１，Ｒ_２∈｛０，１｝^ｍ（ｍ＝ｎ_２）、τ∈{0,1}^ｍ（ｍ＝ｎ_３）を計算し、

を検査する（Ｓ１１３６）。

そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。

本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。

また、第六又は第七の実施形態の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第十二の実施形態）
図２５は、本発明の第十二の実施形態における動作手順を説明するための図である。

本実施形態では、受信者側装置９１０Ａを用いるユーザＡと、送信者側装置９１０Ｂを用いるユーザＢと、が、鍵管理センタ側装置９３０が作成した鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０において、演算部９３２は、入力部９３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、

なる双線形写像ｅを生成する（Ｓ１１４０）。

次に、演算部９３２は、鍵情報生成部２３３を用いて、ｓ_1，ｓ₂∈Ｚ_qおよびＰ∈Ｇ₁をランダムに選ぶ（Ｓ１１４１）。

そして、演算処理部９３２の鍵情報生成部９３３は、ランダムに選んだｓ₁、ｓ₂及びＰを用いて、

を生成する（Ｓ１１４２）。

そして、演算部９３２は、ｓ＝（ｓ₁，ｓ₂）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部９３４に記憶する（Ｓ１１４３）。但し、ｌ,ｍ,ｎは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２は、

なるハッシュ関数を意味する。

次に、演算部９３２は、システムパラメータＰＫを、出力部９３６から出力するか、あるいは、通信部９３５から通信回線１４０を介して送信者側端末９１０Ｂに送信する（Ｓ１１４４）。なお、出力部９３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａにおいて、演算部９１２は、入力部９１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤ_Aを記憶部９１５に記憶するとともに、通信回線１４０を介して通信部９１６から鍵管理センタ側装置９３０に送信する（Ｓ１１４５）。なお、ユーザＡの個別情報ＩＤ_Aについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置９１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０において、演算部９３２は、通信部９３５が通信回線１４０を介して受信者側装置９１０Ａより受信した、あるいは、入力部９３１を介して受信者側装置９１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤ_Ａを、受信者側装置９１０Ａのアドレスに対応付けて記憶部９３４に記憶する（Ｓ１１４６）。

そして、演算部９３２は、鍵情報生成部９３３を用いて、ｂ_IDA∈{0,1}をランダムに選ぶ（Ｓ１１４７）。

次に、演算部９３２は、鍵情報生成部９３３を用いて、記憶部９３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤ_Ａから、

を計算する（Ｓ１１４８）。

そして、演算部９３２は、ＳＫ_Ａ＝（ｂ_IDA,d_IDA,1,d_IDA,2）をユーザＡのプライベート鍵として、出力部９３６から出力するか、あるいは、通信回線１４０を介して通信部９３５から受信者側装置９１０Ａに安全な方法（例えば、鍵管理センタ側装置９３０が受信者側装置９１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ１１４９）。なお、出力部９３６からプライベート鍵ＳＫ_Ａが出力された場合には、鍵管理センタはＩＣカードの郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫ_Ａを通知する。
４．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して鍵管理センタ側装置９３０より受信した、あるいは、入力部９１１を介して入力されたプライベート鍵ＳＫ_Ａを、記憶部９１５に記憶する（Ｓ１１５０）。

また、演算部９１２は、ユーザＡから入力部９１１を介してユーザＡの個別情報ＩＤ_Ａの送信指示を受けると、通信回線１４０を介して通信部９１６からユーザＡの個別情報ＩＤ_Ａを送信する（Ｓ１１５１）。
５．送信者側装置９１０Ｂでの処理
送信側装置９１０Ｂにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して鍵管理センタ側装置９３０より受信した、あるいは、入力部９１１を介して入力されたシステムパラメータＰＫを、記憶部９１５に記憶する（Ｓ１１５２）。

また、送信側装置９１０Ｂにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して受信側装置９１０Ａより受信した、あるいは、入力部９１１を介して入力されたユーザＡの個別情報ＩＤ_Ａを、記憶部９１５に記憶する（Ｓ１１５３）。

次に、ユーザＢは、入力部９１１を介してメッセージ文Ｍ∈{0,1}^ｎ（ｎは正整数）を入力する（Ｓ１１５４）。

メッセージ文Ｍが入力されると、演算部９１２は、入力されたメッセージＭを記憶部９１５に記憶する（Ｓ１１５５）。

そして、演算部９１２は、乱数生成部９１３を用いて、ｒ∈Ｚ_qをランダムに選び（Ｓ１１５６）、

を計算する。さらに、記憶部９１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤ_Ａ及びユーザＢの個別情報ＩＤ_Ｂと、を用いて、

を計算し、

を計算する（Ｓ１１５７）。

そして、演算部９１２は、暗号文Ｃ＝（Ｕ,Ｖ₀,Ｖ₁）を出力部９１７から出力するか、あるいは、通信回線１４０を介して通信部９１６から受信者側装置９１０Ａに送信する（Ｓ１１５８）。なお、出力部９１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、ユーザＡが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１５９）。

次に、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、記憶部９１５に記憶されているユーザＡの個別情報ＩＤ_Ａ及びプライベート鍵ＳＫ_Ａから、

を計算し（Ｓ１１６０），

により、Ｍ∈｛０，１｝ⁿを計算する（Ｓ１１６１）。

本実施例に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CPAの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-ID-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。

本実施例における暗号通信方法は、上記非特許文献６，７に記載の方法などを用いることにより，IND-ID-CCAの意味での安全に強化することが可能である。

また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。

また，本実施例の暗号方式において、（（１３６）式における）Ｖ₀，Ｖ₁の作成方法として、Ｈ₂（ＩＤ||ｉ，ｖ_i,1，ｖ_i,2）を用いて共通鍵暗号における暗号化鍵Ｋを作成し、鍵Ｋを用いてメッセージ文Ｍを（該共通鍵暗号を用いて）暗号化することで、Ｖ₀，Ｖ₁を作成することも可能である。

上記実施例では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびＩＤベース暗号が使われている様々なシステムに適用することが可能である。また、実施例における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。

第一及び第二の実施形態に共通する通信システム１００の概略図。 受信者側装置１１０の概略図。 送信者側装置１２０の概略図。 コンピュータ４００の概略図。 第一の実施形態における動作手順を説明するための図。 第二の実施形態における動作手順を説明するための図。 第三及び第四の実施形態に共通する通信システム２００の概略図。 受信者側装置２１０Ａ及び送信者側装置２１０Ｂの概略図。 鍵管理センタ側装置２３０の概略図。 第三の実施形態における動作手順を説明するための図。 第四の実施形態における動作手順を説明するための図。 第五、第六、第七及び第八の実施形態の通信システム８００の概略図。 受信者側装置１１０の概略図。 送信者側装置１２０の概略図。 第五の実施形態における動作手順を説明するための図。 第六の実施形態における動作手順を説明するための図。 第七の実施形態における動作手順を説明するための図。 第八の実施形態における動作手順を説明するための図。 第九、第十、第十一及び第十二の実施形態の通信システム９００の概略図。 受信者側装置９１０Ａ及び送信者側装置９１０Ｂの概略図。 鍵管理センタ側装置９３０の概略図。 第九の実施形態における動作手順を説明するための図。 第十の実施形態における動作手順を説明するための図。 第十一の実施形態における動作手順を説明するための図。 第十二の実施形態における動作手順を説明するための図。

符号の説明

１００、２００、８００、９００：通信システム、１１０、２１０Ａ、８１０、９１０Ａ：受信者側装置、１１１、２１１、８１１、９１１：入力部、１１２、２１２、８１２、９１２：演算部、１１５、２１５、８１５、９１５：記憶部、１１６、２１６、８１６、９１６：通信部、１１７、２１７、８１７、９１７：出力部、１２０、２１０Ｂ、８２０、９１０Ｂ：送信者側装置、１２１、８２１：入力部、１２２、８２２：演算部、１２５、８２５：記憶部、１２６、８２６：通信部、１２７、８２７：出力部、２３０、９３０：鍵管理センタ側装置、２３１、９１１：入力部、２３２、９３２：演算部、２３４、９３４：記憶部、２３５、９３５：通信部、２３６、９３６：出力部、１４０：通信回線

Claims (20)

1. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
   前記受信者側装置又は鍵管理センタ側装置が、
   乱数ｓ_１,ｓ_２を選択するステップと、
   公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ₁、および、双線形写像ｅ：Ｇ₁×Ｇ₁→Ｇ₂、を作成するステップと、
   Ｐ₁=s₁ＰおよびＰ₂=s₂Ｐを公開する鍵情報の一部として作成するステップと、
   作成したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を、前記送信者側装置に送信するステップと、
   を備え、
   前記送信者側装置は、
   前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ_１、Ｐ_２を受信するステップと、
   受信したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を用いて、e(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を計算するステップと、
   計算されたe(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を用いて、前記受信者側装置に送信する暗号文を作成するステップと、
   を備えること、
   を特徴とする暗号通信方法。
2. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
   （１）前記受信者側装置が、
   素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
   

   

   なる双線形写像ｅを作成するステップと、
   s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶステップと、
   

   

   を算出するステップと、
   SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ_１,Ｈ_２は、
   

   

   なるハッシュ関数を意味する。）と、
   前記暗号化鍵PK_Aを出力するステップと、
   を行い、
   （２）前記送信者側装置が、
   メッセージ文Ｍ∈{0,1}ⁿに対して、ｒ∈Ｚ_ｑをランダムに選ぶステップと、
   前記受信者側装置が出力した前記暗号化鍵PK_Aを用いて、
   

   

   を計算するステップと、
   計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
   を行い、
   （３）前記受信者側装置が、
   前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SK_Aを用いて、
   

   

   により、Ｍ∈｛０，１｝ⁿを計算するステップと、
   

   

   の検査式が成立するか否かを検査するステップと、
   前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
   を行うこと、
   を特徴とする暗号通信方法。
3. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
   （１）前記受信者側装置が、
   素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
   

   

   なる双線形写像ｅを作成するステップと、
   s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶステップと、
   

   

   を算出するステップと、
   SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ_１,Ｈ_２,Ｈ_３は、
   

   

   なるハッシュ関数を意味する。）と、
   前記暗号化鍵PK_Aを出力するステップと、
   を行い、
   （２）前記送信者側装置が、
   メッセージ文Ｍ∈{0,1}ⁿに対して、σ∈{0,1}^mをランダムに選ぶステップと、
   前記受信者側装置が出力した前記暗号化鍵PK_Aを用いて、
   

   

   
   を計算するステップと、
   

   

   
   を計算するステップと、
   計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
   を行い、
   （３）前記受信者側装置が、
   前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SK_Aを用いて、
   

   

   
   により、σ∈｛０，１｝^ｍを計算するステップと、
   

   

   
   により、Ｍを計算するステップと、
   

   

   
   により、r∈Ｚ_qを計算するステップと、
   

   

   
   の検査式が成立するか否かを検査するステップと、
   前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
   を行うこと
   を特徴とする暗号通信方法。
4. 送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたＩＤベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
   （１）前記鍵管理センタ側装置が、
   素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
   

   

   
   なる双線形写像ｅを作成するステップと、
   s₀,s₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶステップと、
   

   

   
   を作成するステップと、
   (s₀,s₁)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,0,Ｐ_pub,1,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）を前記システムパラメータとして、記憶部に記憶するステップ（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
   

   

   
   なるハッシュ関数を意味する。）と、
   前記システムパラメータＰＫを出力するステップと、
   前記受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶部に記憶するステップと、
   ｂ_IDA∈{0,1}をランダムに選ぶステップと、
   前記マスタ鍵(s₀,s₁)を用いて、
   

   

   
   を計算するステップと、
   計算したＳＫ_Ａ＝（ｂ_IDA,d_IDA,0,d_IDA,1）を前記受信者側ユーザのプライベート鍵として出力するステップと、
   を行い、
   （２）前記送信者側装置が、
   メッセージ文Ｍ∈｛０，１｝^ｎに対して、Ｒ∈｛０，１｝^lをランダムに選ぶステップと、
   メッセージ文Ｍ及びＲ、前記受信者側装置より受信した前記個別情報ＩＤ_Ａ、前記鍵管理センタ側装置より出力された前記システムパラメータＰＫを用いて、
   

   

   
   なるｒ∈Ｚ_qおよびＫ∈｛０，１｝^mを計算するステップと、
   

   

   
   を計算するステップ（但し、Ｅ_Ｋ（Ｍ）は平文Ｍをデータ暗号化鍵Ｋを用いて暗号化した結果を表す）と、
   計算したＣ＝（Ｕ,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を暗号文として前記受信者側装置に送信するステップと、
   を行い、
   （３）前記受信者側装置が、
   前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ₀,Ｖ₁,Ｗ,Ｚ）に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵ＳＫ_Ａを用いて、
   

   

   
   なるＲ∈｛０，１｝^lを計算するステップと、
   

   

   
   により、ｒ∈Ｚ_qおよびＫ∈｛０，１｝^mを計算するステップと、
   

   

   
   により、Ｍ∈｛０，１｝ⁿを計算するステップ（但し、Ｄ_Ｋ（Ｙ）は暗号文Ｙを鍵Ｋを用いて復号化した結果を表す。）と、
   

   

   
   の検査式が成立するか否かを検査するステップと、
   前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
   を行うこと、
   を特徴とする暗号通信方法。
5. 請求項４に記載の暗号通信方法であって、
   ハッシュ関数Ｈ_１からＨ_４への入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行うこと、
   を特徴とする暗号通信方法。
6. 送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたＩＤベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
   （１）前記鍵管理センタ側装置が、
   素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
   

   

   
   なる双線形写像ｅを作成するステップと、
   s₁₀,s₁₁,s₂₀,s₂₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶステップと、
   

   

   
   を作成するステップと、
   ＳＫ＝（s₁₀,s₁₁,s₂₀,s₂₁）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,10,Ｐ_pub,11,Ｐ_pub,1,Ｐ_pub,20,Ｐ_pub,21,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶するステップ（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
   

   

   
   なるハッシュ関数を意味する。）と、
   前記システムパラメータＰＫを出力するステップと、
   前記受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶部に記憶するステップと、
   ｂ_IDA∈{0,1}をランダムに選ぶステップと、
   前記マスタ鍵ＳＫを用いて、
   

   

   
   を計算するステップと、
   計算したＳＫ_Ａ＝（ｂ_IDA,d_(1,IDA),d_(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力するステップと、
   を行い、
   （２）前記送信者側装置が、
   メッセージ文Ｍ∈｛０，１｝^ｎに対して、Ｒ∈｛０，１｝^lをランダムに選ぶステップと、
   メッセージ文Ｍ及びＲ、前記受信者側装置より受信した前記個別情報ＩＤ_Ａ、前記鍵管理センタ側装置より出力されたシステムパラメータＰＫを用いて、
   

   

   
   なるｒ₀,r₁∈Ｚ_qおよびＫ∈｛０，１｝^mを計算するステップと、
   

   

   
   を計算するステップ（但し、Ｅ_Ｋ（Ｍ）は平文Ｍをデータ暗号化鍵Ｋを用いて暗号化した結果を表す）と、
   計算したＣ＝（Ｕ₁₀,Ｕ₁₁,Ｕ₂₀,Ｕ₂₁,Ｖ₀,Ｖ₁,Ｗ,Ｚ）を暗号文として前記受信者側装置に送信するステップと、
   を行い、
   （３）前記受信者側装置が、
   前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ₁₀,Ｕ₁₁,Ｕ₂₀,Ｕ₂₁,Ｖ₀,Ｖ₁,Ｗ,Ｚ）に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵ＳＫ_Ａを用いて、
   

   

   
   なるＲ∈｛０，１｝^lを計算するステップと、
   

   

   
   により、ｒ₀,r₁∈Ｚ_qおよびＫ∈｛０，１｝^mを計算するステップと、
   

   

   
   なるＲ’∈｛０，１｝^lを計算するステップと、
   

   

   
   の第一の検査式が成立するか否かを検査するステップと、
   前記第一の検査式が成立する場合に、
   

   

   
   を計算するステップ（但し、Ｄ_Ｋ（Ｙ）は暗号文Ｙを鍵Ｋを用いて復号化した結果を表す。）と、
   

   

   
   の第二の検査式が成立するか否かを検査するステップと、
   前記第二の検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記第一の検査式又は前記第二の検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
   を行うこと、
   を特徴とする暗号通信方法。
7. 請求項６に記載の暗号通信方法であって、
   ハッシュ関数Ｈ_１からＨ_４への入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行う
   ことを特徴とする暗号通信方法。
8. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
   前記受信者側装置又は鍵管理センタ側装置の演算部は、
   乱数ｓ_１,ｓ_２を選択する処理と、
   公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ₁、および、双線形写像ｅ：Ｇ₁×Ｇ₁→Ｇ₂、を作成する処理と、
   Ｐ₁=s₁ＰおよびＰ₂=s₂Ｐを公開する鍵情報の一部として作成する処理と、
   作成したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を、通信部を介して前記送信者側装置に送信する処理と、
   を行い、
   前記送信者側装置の演算部は、
   前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ_１、Ｐ_２を、通信部を介して受信する処理と、
   受信したＰ、Ｑ、ｅ、Ｐ_１、Ｐ_２を用いて、e(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を計算する処理と、
   計算されたe(Ｑ,Ｐ₁)およびe(Ｑ,Ｐ₂)を用いて、前記受信者側装置に送信する暗号文を作成する処理と、
   を行うこと、
   を特徴とする暗号通信システム。
9. 送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
   演算部が、
   素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
   

   

   
   なる双線形写像ｅを作成する処理と、
   s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ処理と、
   

   

   
   を算出する処理と、
   SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ_１,Ｈ_２は、
   

   

   
   なるハッシュ関数を意味する。）と、
   前記暗号化鍵PK_Aを出力する処理と、
   を行うこと、
   を特徴とする受信者側装置。
10. 送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
    演算部が、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を算出する処理と、
    SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ_１,Ｈ_２,Ｈ_３は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記暗号化鍵PK_Aを出力する処理と、
    を行うこと、
    を特徴とする受信者側装置。
11. 送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
    演算部が、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₀,s₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を作成する処理と、
    (s₀,s₁)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,0,Ｐ_pub,1,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）を前記システムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記システムパラメータＰＫを出力する処理と、
    受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶部に記憶する処理と、
    ｂ_IDA∈{0,1}をランダムに選ぶ処理と、
    前記マスタ鍵(s₀,s₁)を用いて、
    

    

    
    を計算する処理と、
    計算したＳＫ_Ａ＝（ｂ_IDA,d_IDA,0,d_IDA,1）を前記受信者側ユーザのプライベート鍵として出力する処理と、
    を行うこと、
    を特徴とする鍵管理センタ側装置。
12. 送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
    演算部が、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₁₀,s₁₁,s₂₀,s₂₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を作成する処理と、
    ＳＫ＝（s₁₀,s₁₁,s₂₀,s₂₁）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,10,Ｐ_pub,11,Ｐ_pub,1,Ｐ_pub,20,Ｐ_pub,21,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記システムパラメータＰＫを出力する処理と、
    受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶部に記憶する処理と、
    ｂ_IDA∈{0,1}をランダムに選ぶ処理と、
    前記マスタ鍵ＳＫを用いて、
    

    

    
    を計算する処理と、
    計算したＳＫ_Ａ＝（ｂ_IDA,d_(1,IDA),d_(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力する処理と、
    を行うこと、
    を特徴とする鍵管理センタ側装置。
13. コンピュータを、
    送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置として機能させるプログラムであって、
    前記コンピュータの演算手段に、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を算出する処理と、
    SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２）を暗号化鍵として、記憶手段に記憶する処理（但し、m,nは自然数、Ｈ_１,Ｈ_２は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記暗号化鍵PK_Aを出力する処理と、
    を行わせること、
    を特徴とするプログラム。
14. コンピュータを、
    送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置として機能させるプログラムであって、
    前記コンピュータの演算手段に、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₁,s₂∈Ｚ^* _qおよびＰ,Ｑ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を算出する処理と、
    SK_A=（s₁Ｑ,s₂Ｑ）を復号化鍵とし、PK_A=（ｑ,Ｇ₁,Ｇ₂,ｅ,ｍ,ｎ,Ｐ,Ｐ_pub,1,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ_１,Ｈ_２,Ｈ_３は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記暗号化鍵PK_Aを出力する処理と、
    を行わせること、
    を特徴とするプログラム。
15. コンピュータを、
    送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置として機能させるプログラムであって、
    前記コンピュータの演算手段に、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₀,s₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を作成する処理と、
    (s₀,s₁)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,0,Ｐ_pub,1,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）を前記システムパラメータとして、記憶手段に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記システムパラメータＰＫを出力する処理と、
    受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶手段に記憶する処理と、
    ｂ_IDA∈{0,1}をランダムに選ぶ処理と、
    前記マスタ鍵(s₀,s₁)を用いて、
    

    

    
    を計算する処理と、
    計算したＳＫ_Ａ＝（ｂ_IDA,d_IDA,0,d_IDA,1）を前記受信者側ユーザのプライベート鍵として出力する処理と、
    を行わせること、
    を特徴とするプログラム。
16. コンピュータを、
    送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置として機能させるプログラムであって、
    前記コンピュータの演算手段に、
    素数ｑ，位数ｑの加法群Ｇ₁，位数ｑの乗法群Ｇ₂，および、
    

    

    
    なる双線形写像ｅを作成する処理と、
    s₁₀,s₁₁,s₂₀,s₂₁∈Ｚ^* _qおよびＰ∈Ｇ₁をランダムに選ぶ処理と、
    

    

    
    を作成する処理と、
    ＳＫ＝（s₁₀,s₁₁,s₂₀,s₂₁）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ₁,Ｇ₂,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐ_pub,10,Ｐ_pub,11,Ｐ_pub,1,Ｐ_pub,20,Ｐ_pub,21,Ｐ_pub,2,Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ_１,Ｈ_２,Ｈ_３,Ｈ₄は、
    

    

    
    なるハッシュ関数を意味する。）と、
    前記システムパラメータＰＫを出力する処理と、
    受信者側装置より受信した受信者側ユーザの個別情報ＩＤ_Aを記憶手段に記憶する処理と、
    ｂ_IDA∈{0,1}をランダムに選ぶ処理と、
    前記マスタ鍵ＳＫを用いて、
    

    

    
    を計算する処理と、
    計算したＳＫ_Ａ＝（ｂ_IDA,d_(1,IDA),d_(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力する処理と、
    を行わせること、
    を特徴とするプログラム。
17. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
    前記受信者側装置又は鍵管理センタ側装置が、
    公開鍵と秘密鍵のペアを複数生成する鍵生成ステップと、
    前記鍵生成ステップで生成した複数の公開鍵を含む公開鍵情報を生成するステップと、
    前記鍵生成ステップで生成した複数の秘密鍵を含む秘密鍵情報を生成するステップと、
    前記送信者側装置が、
    前記公開鍵情報を取得するステップと、
    前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成するステップと、
    前記受信者側装置が、
    前記暗号文を取得するステップと、
    前記暗号文を前記秘密鍵情報で復号するステップと、
    を備えることを特徴とする暗号通信方法。
18. 請求項１７に記載の暗号通信方法であって、
    前記公開鍵及び前記秘密鍵は、任意の暗号方式を選択することができること、
    を特徴とする暗号通信方法。
19. 送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
    前記受信者側装置又は鍵管理センタ側装置の演算部が、
    公開鍵と秘密鍵のペアを複数生成する鍵生成処理と、
    前記鍵生成処理で生成した複数の公開鍵を含む公開鍵情報を生成する処理と、
    前記鍵生成処理で生成した複数の秘密鍵を含む秘密鍵情報を生成する処理と、
    前記送信者側装置の演算部が、
    前記公開鍵情報を取得する処理と、
    前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成する処理と、
    前記受信者側装置の演算部が、
    前記暗号文を取得する処理と、
    前記暗号文を前記秘密鍵情報で復号する処理と、
    を備えることを特徴とする暗号通信装置。
20. 請求項１９に記載の暗号通信装置であって、
    前記公開鍵及び前記秘密鍵は、任意の暗号方式を選択することができること、
    を特徴とする暗号通信装置。

Images