説明

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

【課題】 BDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびIDベース暗号方式を提供すること。
【解決手段】 暗号文の受信者となる受信者側装置110は、乱数s,sを選び、公開の鍵情報の一部として、P,Q∈G1、および、双線形写像e:G1×G1→G2、を作成し、さらに、P1=s1PおよびP2=s2Pを公開の鍵情報の一部として作成する。暗号文の送信者である送信者側装置120は、受信者側装置110の公開の鍵情報Q、双線形写像eを用いて、e(Q,P1)およびe(Q,P2)を計算し、さらに、これらの情報e(Q,P1)およびe(Q,P2)を用いて受信者側装置110に送信する暗号文を作成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号通信の技術に関する。
【背景技術】
【0002】
公開鍵暗号システムにおいては、ユーザが作成した公開鍵を認証局(CA)に登録し、証明書を発行してもらう必要がある。すなわち、暗号文の送信者は受信者の公開鍵とその正当性の根拠である証明書を手に入れ、その上で送信するメッセージ文の暗号化を行う必要がある。
【0003】
これに対して、CAの証明書発行の手間を省いて、より簡単な公開鍵の管理を行うことを目的として、ユーザのID情報を公開鍵とする暗号システム(以下、IDベース暗号システム)が提案された。
【0004】
IDベース暗号システムでは、暗号通信、認証(ディジタル署名、個人認証、等)を目的として用途に応じたアルゴリズムが用いられる。
【0005】
例えば、暗号通信の場合、ユーザは、自身のID情報を公開鍵として鍵管理センタに登録し、該ID情報に対応するプライベート鍵を発行してもらう。暗号文の送信者は、受信者の該ID情報と鍵管理センタが作成したシステム・パラメータを用いて暗号文を作成し、受信者に送信する。受信者は、該プライベート鍵を用いてメッセージの復号化を行う。
【0006】
公開鍵暗号システムでは、受信者の公開鍵はランダムなビット列であるのに対して、IDベース暗号システムでは、メールアドレス等の個人情報であるため、取り扱いが容易で証明書を不要とすることができる。
【0007】
多くのIDベース暗号方式が提案されたが、安全性の証明が可能な方式は長い間知られていなかったが、2001年に、非特許文献1において、楕円曲線上の双線形写像の特性を利用することで、安全性の証明が可能な初めてのIDベースの暗号通信方式が提案された。非特許文献1の方式では、安全性を高めるために、非特許文献2に記載の変換方法を利用している。
【0008】
以降、双線形写像を利用した様々な暗号システムが提案されるようになった。非特許文献2では、非特許文献1に記載の暗号通信方式をベースとして階層化されたシステムにおける安全性証明可能な階層的IDベース暗号通信方式が提案された。
【0009】
非特許文献3では、安全性証明において、タイトなセキュリティ・リダクションを実現するためのアイデアが提案され、非特許文献4では、同アイデアを用いて、タイトなセキュリティ・リダクションをもつIDベース暗号方法が具体的に提案された。
【0010】
【非特許文献1】Boneh and M. Franklin. Identity Based Encryption From the Weil Pairing, http://crypto.stanford.edu/~dabo/pubs.html
【非特許文献2】E.Fujisaki and T.Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes, Crypto’99, LNCS1666, Springer-Verlag, pp.537554 (1999)
【非特許文献3】C. Gentry and A. Silverberg. Hierarchical ID-based Cryptography, http://eprint.iacr.org/2002/056
【非特許文献4】J. Katz, N. Wang. Efficiency Improvements for Signature Schemes with Tight Security Reductions, http://www.cs.umd.edu/~jkatz/
【非特許文献5】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
【発明の開示】
【発明が解決しようとする課題】
【0011】
近年提案されている暗号には、その暗号の安全性の証明が可能であるものが多い。すなわち、暗号を破ることの計算量を数論問題などの計算量的複雑性をもつ問題(例えば、素因数分解問題、離散対数問題、Diffie-Hellman 問題、等)に置き換えて定量的に評価する。
【0012】
セキュリティ・リダクションとは、暗号方式が安全性を証明する場合において、安全性の根拠(暗号学的仮定)とする数論問題の計算量的困難性と暗号方式の安全性の関係を示すひとつのパラメータである。セキュリティ・リダクションがタイトであることは、暗号の安全性が暗号学的仮定とする数論問題の計算量的困難性に近いことを意味する。
【0013】
このことは、セキュリティ・リダクションの悪い(タイトでない)暗号方式と比較した場合、セキュリティ・リダクションがタイトな方式はより高い安全性を有することを意味し、また、一定の安全性を得るために必要な鍵長を短く設定できるメリットを有する。
【0014】
ここで、セキュリティ・リダクションがタイトであったとしても、暗号学的仮定に用いられる数論問題の計算量的困難性が期待できないような場合には暗号の安全性に意味はなくなってしまう。よって、より計算量的困難性が期待されているような問題に対して、タイトなセキュリティ・リダクションを持ち、安全性が証明できるような暗号方式が理想的である。
【0015】
本発明では、十分に計算量的困難性が期待されているBDH(Bilinear Diffie-Hellman)問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびIDベース暗号方式を提供することを目的とする。
【0016】
また、さらに、BDH問題よりも計算量的に簡単な問題であるLBDH(List Bilinear Diffie-Hellman)問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムが既に存在した場合において、暗号部分の入れ替えを行うのではなく、既に使われている暗号を利用しながら、BDH問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムに変換する方法を提供することを目的とする。
【課題を解決するための手段】
【0017】
上記課題を解決するために、本発明では、双線形写像e:G1×G1→G2、P,Q∈G1、に対して、乱数s,sを選び、P1=sPおよびP2=sPを公開の鍵情報の一部として作成し、暗号文の送信者は、e(Q,P1)およびe(Q,P2)を計算し、これらの値を用いて暗号文を作成する。以下、実現するための公開鍵暗号の一具体例について説明する。
【0018】
例えば、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、前記受信者側装置又は鍵管理センタ側装置が、乱数s,sを選択するステップと、公開する鍵情報の一部として、P,Q∈G1、および、双線形写像e:G1×G1→G2、を作成するステップと、P1=sPおよびP2=sPを公開する鍵情報の一部として作成するステップと、作成したP、Q、e、P、Pを、前記送信者側装置に送信するステップと、を備え、前記送信者側装置は、前記受信者側装置又は前記鍵管理センタ側装置から、P、Q、e、P、Pを受信するステップと、受信したP、Q、e、P、Pを用いて、e(Q,P1)およびe(Q,P2)を計算するステップと、計算されたe(Q,P1)およびe(Q,P2)を用いて、前記受信者側装置に送信する暗号文を作成するステップと、を備えること、を特徴とする。
【0019】
また、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、(1)前記受信者側装置が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0020】
【数66】

【0021】
なる双線形写像eを作成するステップと、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶステップと、
【0022】
【数67】

【0023】
を算出するステップと、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を暗号化鍵として、記憶部に記憶するステップ(但し、m,nは自然数、H,Hは、
【0024】
【数68】

【0025】
なるハッシュ関数を意味する。)と、
前期暗号化鍵PKを出力するステップと、
を行い、
(2)前期送信者側装置が、
メッセージ文M∈{0,1}nに対して、r∈Zqをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵PKを用いて、
【0026】
【数69】

【0027】
を計算するステップと、
計算したC=(U,V,W)を前記メッセージ文Mの暗号文として前記受信者側装置に送信するステップと、
を行い、
(3)前記受信者側装置が、
前記送信者側装置より受信した前記暗号文C=(U,V,W)に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【0028】
【数70】

【0029】
により、M∈{0,1}nを計算するステップと、
【0030】
【数71】

【0031】
の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Mをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Cを不正な暗号文とみなして棄却するステップと、
を行うこと、を特徴とする。
【0032】
また、本発明は、
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
公開鍵と秘密鍵のペアを複数生成する鍵生成ステップと、
前記鍵生成ステップで生成した複数の公開鍵を含む公開鍵情報を生成するステップと、
前記鍵生成ステップで生成した複数の秘密鍵を含む秘密鍵情報を生成するステップと、
前記送信者側装置が、
前記公開鍵情報を取得するステップと、
前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成するステップと、
前記受信者側装置が、
前記暗号文を取得するステップと、
前記暗号文を前記秘密鍵情報で復号するステップと、
を備えることを特徴とする。
【発明の効果】
【0033】
本発明の暗号システムによれば、十分な計算量的困難性を期待されるBDH(bilinear Diffie-Hellman)問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつ、安全性の高い公開鍵暗号方式およびIDベース暗号方式を提供することができる。これにより、利便性に優れ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。
【0034】
また、さらに、既存の暗号システムを利用しながら、新しい暗号方法を提供することが可能であるため、システム入れ替えのためのコストを削減することができ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。
【発明を実施するための最良の形態】
【0035】
図1は、本発明の第一及び第二の実施形態に共通する通信システム100の概略図である。
【0036】
図示するように、通信システム100は、受信者側装置110と、送信者側装置120と、を備えており、これらは通信回線140に接続されている。
【0037】
図2は、受信者側装置110の概略図である。
【0038】
図示するように、受信者側装置110は、情報を入力する入力部111と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置110の各部の制御を行う演算部112と、記憶部115と、通信回線140を介して送信者側装置120と通信を行う通信部116と、情報を出力する出力部117と、を備えている。
【0039】
また、演算部112は、暗号化鍵及び復号化鍵を生成する鍵情報生成部113と、暗復号化処理を行う暗復号化部114と、を有する。
【0040】
図3は、送信者側装置120の概略図である。
【0041】
図示するように、送信者側装置120は、情報を入力する入力部121と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置120の各部の制御を行う演算部122と、記憶部125と、通信回線140を介して受信者側装置110と通信を行う通信部126と、情報を出力する出力部127と、を備えている。
【0042】
また、演算部122は、乱数を生成する乱数生成部123と、暗復号化処理を行う暗復号化部124と、を有する。
【0043】
上記構成の受信者側装置110及び送信者側装置120は、図4に示すような、CPU401と、メモリ402と、HDD等の外部記憶装置403と、CD-ROMやDVD-ROM等の可搬性を有する記憶媒体409から情報を読み出す読取装置404と、キーボードやマウスなどの入力装置405と、ディスプレイなどの出力装置406と、通信回線300を介して相手装置と通信を行なうための通信装置407と、これらの各装置を接続するバス408とを備えた一般的なコンピュータ400において、CPU401がメモリ402上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ402や外部記憶装置403が記憶部115、125に利用され、通信装置408が通信部116、126に利用され、入力装置406や読取装置405が入力部111、121に利用され、そして、出力装置407が出力部117、127に利用される。
【0044】
この所定のプログラムは、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、外部記憶装置403にダウンロードされ、それから、メモリ402上にロードされてCPU401により実行されるようにしてもよい。また、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、メモリ402上に直接ロードされ、CPU401により実行されるようにしてもよい。
(第一の実施形態)
本発明の第一の実施形態について説明する。
【0045】
本実施形態では、受信者側装置110を用いるユーザAと送信者側装置120を用いるユーザBが、ユーザAが受信者側装置110において作成した公開鍵情報を用いて、通信回線140を介して暗号通信を行う方法について述べる。
【0046】
なお、図5は、本発明の第一の実施形態における動作手順を説明するための図である。
1.受信者側装置110での処理
受信者側装置110において、演算部112は、入力部111を介してユーザAから鍵生成の指示を受け付けると、鍵情報生成部113を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0047】
【数72】

【0048】
なる双線形写像eを作成する(S610)。
【0049】
次に、演算部112は、鍵情報生成部113を用いて、s、s∈Z*qおよびP,Q∈G1をランダムに選ぶ(S611)。
【0050】
そして、演算部112の鍵情報生成部113は、ランダムに選んだs、s及びPを用いて、
【0051】
【数73】

【0052】
を生成する(S612)。
【0053】
そして、演算部112は、SKA=(s1Q,s2Q)を復号化(秘密)鍵として、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を暗号化(公開)鍵として、両者を記憶部115に記憶する(S613)。但し、m,nは自然数、H,Hは、
【0054】
【数74】

【0055】
なるハッシュ関数を意味する。
【0056】
次に、演算部112は、S613で生成した暗号化(公開)鍵PK=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を、出力部117から出力するか、あるいは、通信部116から通信回線140を介して送信者側装置120に送信する(S614)。なお、出力部117から暗号化(公開)鍵PKが出力された場合には、ユーザAは、郵送等によりユーザBに暗号化(公開)鍵PKを通知する。
2.送信者側装置120での処理
送信者側装置120の演算部122は、通信部126が通信回線140を介して受信者側装置110より受信した、あるいは、ユーザBが入力部121を介して入力した暗号化(公開)鍵PKを記憶部125に記憶する(S615)。
【0057】
次に、ユーザBは、入力部121を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S616)。
【0058】
メッセージ文Mが入力されると、演算部122は、入力されたメッセージ文Mを記憶部125に記憶する(S617)。
【0059】
そして、演算部122は、乱数生成部123を用いて、メッセージMに対して、r∈Z*をランダムに選ぶ(S618)。
【0060】
次に、演算部122は、S616で選択されたrと、記憶部125に記憶されている暗号化(公開)鍵PK及びメッセージMと、暗復号化部124を用いて、
【0061】
【数75】

【0062】
を計算する(S619)。
【0063】
そして、演算部122は、S619で生成した暗号文C=(U,V,W)を、出力部127から出力するか、あるいは、通信部126から通信回線140を介して受信者側装置110に送信する(S620)。なお、出力部127から暗号文Cが出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
3.受信者側装置110での処理
受信者側装置110の演算部112は、通信部116が通信回線140を介して送信者側装置120より受信した、あるいは、ユーザAが入力部111を介して入力した暗号文Cを記憶部115に記憶する(S621)。
【0064】
次に、演算部112は、暗復号化部114を用いて、記憶部115に記憶されている暗号文Cに対して、記憶部115に記憶されているユーザAの復号(秘密)鍵SKから、
【0065】
【数76】

【0066】
により、M∈{0,1}を計算する(S622)。
【0067】
さらに、演算部112は、S22での計算結果であるMと、暗号文C=(U,V,W)と、から、
【0068】
【数77】

【0069】
の検査式が成立するか否かを検査する(S623)。この検査式が成立する場合には、S20での計算結果Mをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文C=(U,V,W)を不正な暗号文とみなして棄却する。
【0070】
実施例1に記載の公開鍵暗号通信方法は、非特許文献1および非特許文献4に記載の手法と同様の手法により、Bilinear Diffie-Hellman(BDH)問題の計算量的困難性を暗号学的仮定として、IND-CCA2の意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CCA2の意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【0071】
本実施例における暗号通信方法において、暗号文の一部であるWへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【0072】
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
(第二の実施形態)
次に、本発明の第二の実施形態について説明する。本実施形態は、第一の実施形態の変形例である。
【0073】
図6は、本発明の第二の実施形態における動作手順を説明するための図である。
1.受信者側装置110での処理
受信者側装置110において、演算部112は、入力部111を介してユーザAから鍵生成の指示を受け付けると、鍵情報生成部113を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0074】
【数78】

【0075】
なる双線形写像eを作成する(S630)。
【0076】
次に、演算部112は、鍵情報生成部113を用いて、s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶ(S631)。
【0077】
そして、演算部112の鍵情報生成部113は、ランダムに選んだs、s及びPを用いて、
【0078】
【数79】

【0079】
を生成する(S632)。
【0080】
そして、演算部112は、SKA=(s1Q,s2Q)を復号化(秘密)鍵として、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H,H)を暗号化(公開)鍵として、両者を記憶部115に記憶する(S633)。但し、m,nは自然数、H,H,Hは、
【0081】
【数80】

【0082】
なるハッシュ関数を意味する。
【0083】
次に、演算部112は、S633で生成した暗号化(公開)鍵をPKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H,H)を、出力部117から出力するか、あるいは、通信部116から通信回線140を介して送信者側装置120に送信する(S634)。なお、出力部117から暗号化(公開)鍵PKが出力された場合には、ユーザAは、郵送等によりユーザBに暗号化(公開)鍵PKを通知する。
2.送信者側装置120での処理
送信者側装置120の演算部122は、通信部126が通信回線140を介して受信者側装置110より受信した、あるいは、ユーザBが入力部121を介して入力した暗号化(公開)鍵PKを記憶部125に記憶する(S635)
次に、ユーザBは、入力部121を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S636)。
【0084】
メッセージ文Mが入力されると、演算部122は、入力されたメッセージ文Mを記憶部125に記憶する(S637)。
【0085】
そして、演算部122は、乱数生成部123を用いて、メッセージMに対して、σ∈{0,1}mをランダムに選ぶ(S638)。
【0086】
次に、演算部122は、S638で選択されたσを用いて、
【0087】
【数81】

【0088】
を計算する(S639)。
【0089】
そして、演算部122は、S639で計算されたrと、記憶部125に記憶されている暗号化(公開)鍵PK及びメッセージMと、暗復号化部124を用いて、
【0090】
【数82】

【0091】
を計算する(S640)。
【0092】
そして、演算部122は、S640で生成した暗号文C=(U,V,W)を、出力部127から出力するか、あるいは、通信部126から通信回線140を介して受信者側装置110に送信する(S641)。なお、出力部127から暗号文Cが出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
3.受信者側装置110での処理
受信者側装置110の演算部112は、通信部116が通信回線140を介して送信者側装置120より受信した、あるいは、ユーザAが入力部111を介して入力した暗号文Cを記憶部115に記憶する(S642)。
【0093】
次に、演算部112は、暗復号化部114を用いて、記憶部115に記憶されている暗号文Cに対して、記憶部115に記憶されているユーザAの復号(秘密)鍵SKから、
【0094】
【数83】

【0095】
により、σ∈{0,1}を計算する(S643)。
【0096】
さらに、演算部112は、S43での計算結果であるσと、暗号文C=(U,V,W)と、から、
【0097】
【数84】

【0098】
により、M∈{0,1}を計算する(S644)。
【0099】
さらに、演算部112は、S644での計算結果であるMと、S643での計算結果であるσと、から、
【0100】
【数85】

【0101】
により、r∈Zqを計算する(S645)。
【0102】
そして、演算部112は、S645での計算結果rと、暗号文C=(U,V,W)と、から、
【0103】
【数86】

【0104】
の検査式が成立するか否かを検査する(S646)。この検査式が成立する場合には、S644での計算結果Mをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文C=(U,V,W)を不正な暗号文とみなして棄却する。
【0105】
第二の実施形態に記載の公開鍵暗号通信方法は、第一の実施形態の場合と同様、Bilinear Diffie-Hellman(BDH)問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。また、タイトなセキュリティ・リダクションをもつことも第一の実施形態の場合と同様に示される。
【0106】
図7は、本発明の第三及び第四の実施形態に共通する通信システム200の概略図である。
【0107】
図示するように、通信システム200は、受信者側装置210Aと、送信者側装置210Bと、鍵管理センタ側装置230と、を備えており、これらは通信回線140に接続されている。
【0108】
図8は、受信者側装置210A及び送信者側装置210Bの概略図である。本実施形態における受信者側装置210A及び送信者側装置210Bは、同様の構成を有している。
【0109】
図示するように、受信者側装置210A及び送信者側装置210Bは、情報を入力する入力部211と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置210A又は送信者側装置210Bの各部の制御を行う演算部212と、記憶部215と、通信回線140を介して通信を行う通信部216と、情報を出力する出力部217と、を備えている。
【0110】
また、演算部212は、乱数を生成する乱数生成部213と、暗復号化処理を行う暗復号化部214と、を有する。
【0111】
図9は、鍵管理センタ側装置230の概略図である。
【0112】
図示するように、鍵管理センタ側装置230は、情報を入力する入力部231と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置230の各部の制御を行う演算部232と、記憶部234と、通信回線140を介して受信者側装置210A及び送信者側装置210Bと通信を行う通信部235と、情報を出力する出力部236と、を備えている。
【0113】
また、演算部232は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部233を有する。
【0114】
上記構成の受信者側装置210A、送信者側装置210B及び鍵管理センタ側装置230についても、図4に示すような、CPU401と、メモリ402と、HDD等の外部記憶装置403と、CD-ROMやDVD-ROM等の可搬性を有する記憶媒体409から情報を読み出す読取装置404と、キーボードやマウスなどの入力装置405と、ディスプレイなどの出力装置406と、通信回線300を介して相手装置と通信を行なうための通信装置407と、これらの各装置を接続するバス408とを備えた一般的なコンピュータ400において、CPU401がメモリ402上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ402や外部記憶装置403が記憶部215、234に利用され、通信装置408が通信部216、235に利用され、入力装置406や読取装置405が入力部211、231に利用され、そして、出力装置407が出力部217、236に利用される。
【0115】
この所定のプログラムは、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、外部記憶装置403にダウンロードされ、それから、メモリ402上にロードされてCPU401により実行されるようにしてもよい。また、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、メモリ402上に直接ロードされ、CPU401により実行されるようにしてもよい。
(第三の実施形態)
本発明の第三の実施形態について説明する。
【0116】
本実施形態では、受信者側装置210Aを用いるユーザAと、送信者側装置210Bを用いるユーザBと、が、鍵管理センタ側装置230が作成した鍵情報を用いて、通信回線140を介して暗号通信を行う方法について述べる。
【0117】
なお、図10は、本発明における第三の実施形態における動作手順を説明するための図である。
1.鍵管理センタ側装置230での処理
鍵管理センタ側装置230において、演算部232は、入力部231を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部233を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0118】
【数87】

【0119】
なる双線形写像eを生成する(S650)。
【0120】
次に、演算部232は、鍵情報生成部233を用いて、s0,s1∈Z*qおよびP∈G1をランダムに選ぶ(S651)。
【0121】
そして、演算処理部232の鍵情報生成部233は、ランダムに選んだs、s及びPを用いて、
【0122】
【数88】

【0123】
を生成する(S652)。
【0124】
そして、演算部232は、s=(s0,s1)をマスタ鍵として、PK=(q,G1,G2,e,l,m,n,P,Ppub,H,H,H,H4,E,D)をシステムパラメータとして、両者を記憶部234に記憶する(S653)。但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【0125】
【数89】

【0126】
なるハッシュ関数を意味する。
【0127】
次に、演算部232は、S653で生成したシステムパラメータPKを、出力部236から出力するか、あるいは、通信部235から通信回線140を介して送信者側端末210Bに送信する(S654)。なお、出力部236からシステムパラメータPKが出力された場合には、鍵管理センタは郵送等によりユーザBにシステムパラメータPKを通知する。
2.受信者側装置210Aでの処理
受信者側装置210Aにおいて、演算部212は、入力部211を介してユーザAより受け付けたユーザAの個別情報IDAを記憶部215に記憶するとともに、通信回線140を介して通信部216から鍵管理センタ側装置230に送信する(S655)。なお、ユーザAの個別情報IDAについては、ユーザAが郵送等によって鍵管理センタに受信者側装置210Aのアドレスとともに通知してもよい。
3.鍵管理センタ側装置230での処理
鍵管理センタ側装置230において、演算部232は、通信部235が通信回線140を介して受信者側装置210Aより受信した、あるいは、入力部231を介して受信者側装置210Aのアドレスとともに入力されたユーザAの個別情報IDを、受信者側装置210Aのアドレスに対応付けて記憶部234に記憶する(S656)。
【0128】
そして、演算部232は、鍵情報生成部233を用いて、bIDA∈{0,1}をランダムに選ぶ(S657)。
【0129】
次に、演算部232は、鍵情報生成部233を用いて、記憶部234に記憶されているマスタ鍵s及びユーザAの個別情報IDから、
【0130】
【数90】

【0131】
を計算する(S658)。
【0132】
そして、演算部232は、SK=(bIDA,dIDA,0,dIDA,1)をユーザAのプライベート鍵として、出力部236から出力するか、あるいは、通信回線140を介して通信部235から受信者側装置210Aに安全な方法(例えば、鍵管理センタ側装置230が受信者側装置210Aと共有する暗号鍵を用いた暗号通信)で送信する(S659)。なお、出力部236からプライベート鍵SKが出力された場合には、鍵管理センタはICカードの郵送等の安全な方法により、ユーザAにプライベート鍵SKを通知する。
4.受信者側装置210Aでの処理
受信者側装置210Aにおいて、演算部212は、通信部216が通信回線140を介して鍵管理センタ側装置230より受信した、あるいは、入力部211を介して入力されたプライベート鍵SKを、記憶部215に記憶する(S660)。
【0133】
また、演算部212は、ユーザAから入力部211を介してユーザAの個別情報IDの送信指示を受けると、通信回線140を介して通信部216からユーザAの個別情報IDを送信する(S661)。
5.送信者側装置210Bでの処理
送信側装置210Bにおいて、演算部212は、通信部216が通信回線140を介して鍵管理センタ側装置230より受信した、あるいは、入力部211を介して入力されたシステムパラメータPKを、記憶部215に記憶する(S662)。
【0134】
また、送信側装置210Bにおいて、演算部212は、通信部216が通信回線140を介して受信側装置210Aより受信した、あるいは、入力部211を介して入力されたユーザAの個別情報IDを、記憶部215に記憶する(S663)。
【0135】
次に、ユーザBは、入力部211を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S664)。
【0136】
メッセージ文Mが入力されると、演算部212は、入力されたメッセージMを記憶部215に記憶する(S665)。
【0137】
そして、演算部212は、乱数生成部213を用いて、R∈{0,1}lをランダムに選ぶ(S666)。
【0138】
次に、演算部212は、S666で選択されたRと、記憶部215に記憶されているメッセージ文M、システムパラメータPK、ユーザAの個別情報ID及びユーザBの個別情報IDと、を用いて、
【0139】
【数91】

【0140】
なるr∈ZqおよびK∈{0,1}mを計算する(S667)。
【0141】
さらに、演算部212は、S667で計算されたr及びKを用いて、
【0142】
【数92】

【0143】
を計算する(S668)。
【0144】
そして、演算部212は、S668で作成した暗号文C=(U,V0,V1,W,Z)を出力部217から出力するか、あるいは、通信回線140を介して通信部216から受信者側装置210Aに送信する(S669)。なお、出力部217から暗号文が出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
6.受信者側装置210Aでの処理
受信者側装置210Aの演算部212は、通信部216が通信回線140を介して送信者側装置210Bより受信した、あるいは、ユーザAが入力部211を介して入力した暗号文Cを記憶部215に記憶する(S670)。
【0145】
次に、演算部212は、暗復号化部214を用いて、記憶部215に記憶されている暗号文Cに対して、記憶部215に記憶されているユーザAの個別情報ID及びプライベート鍵SKから、
【0146】
【数93】

【0147】
なるR∈{0,1}lを計算する(S671)。
【0148】
さらに、演算部212は、S71で計算されたRと、記憶部215に記憶されているユーザAの個別情報ID及びユーザBの個別情報IDと、を用いて、
【0149】
【数94】

【0150】
により、r∈ZqおよびK∈{0,1}mを計算する(S672)。
【0151】
次に、演算部212は、S672で計算されたKを用いて、
【0152】
【数95】

【0153】
により、M∈{0,1}nを計算する(S673)。
【0154】
そして、演算部212は、S671で計算されたRと、S672で計算されたrと、S673で計算されたMと、暗号文Cと、から、
【0155】
【数96】

【0156】
の検査式が成立するか否かを検査する(S674)。この検査式が成立する場合には、S673での計算結果Mをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文C=(U,V0,V1,W,Z)を不正な暗号文とみなして棄却する。
【0157】
第三の実施形態に記載のIDベース暗号通信方法は、非特許文献4に記載の手法と同様の手法により、List Bilinear Diffie-Hellman(LBDH)問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。
【0158】
このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでLBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のIDベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【0159】
また、本実施例の方式は、非特許文献4に記載の方式よりも、暗号化処理において、計算量の多い双線形写像の計算がひとつ少ないため、より高速な暗号化処理を実現できる。本実施形態における暗号通信方法において、暗号文の一部であるWへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【0160】
本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
(第四の実施形態)
本発明の第四の実施形態について説明する。
【0161】
本実施形態は、第三の実施形態に比べて、鍵長は長くなるが、暗号化及び復号化処理の高速性に優れる方式である。
【0162】
なお、図11は、本発明における第四の実施形態における動作手順を説明するための図である。
1.鍵管理センタ側装置230での処理
鍵管理センタ側装置230において、演算部232は、入力部231を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部233を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0163】
【数97】

【0164】
なる双線形写像eを生成する(S680)。
【0165】
次に、演算部232は、鍵情報生成部233を用いて、s10,s11,s20,s21∈Z*qおよびP∈G1をランダムに選ぶ(S681)。
【0166】
そして、演算処理部232の鍵情報生成部233は、ランダムに選んだs10、s11、s20、s21及びPを用いて、
【0167】
【数98】

【0168】
を生成する(S682)。
【0169】
そして、演算部232は、s=(s10,s11,s20,s21)をマスタ鍵として、PK=(q,G1,G2,e,l,m,n,P,Ppub,10,Ppub,11,Ppub,1,Ppub,20,Ppub,21,Ppub,2,H,H,H,H4,E,D)をシステムパラメータとして、両者を記憶部234に記憶する(S683)。但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【0170】
【数99】

【0171】
なるハッシュ関数を意味する。
【0172】
次に、演算部232は、S83で生成したシステムパラメータPKを、出力部236から出力するか、あるいは、通信部235から通信回線140を介して送信者側端末210Bに送信する(S684)。なお、出力部236からシステムパラメータPKが出力された場合には、鍵管理センタは郵送等によりユーザBにシステムパラメータPKを通知する。
2.受信者側装置210Aでの処理
受信者側装置210Aにおいて、演算部212は、入力部211を介してユーザAより受け付けたユーザAの個別情報IDAを記憶部215に記憶するとともに、通信回線140を介して通信部216から鍵管理センタ側装置230に送信する(S685)。なお、ユーザAの個別情報IDAについては、ユーザAが郵送等によって鍵管理センタに受信者側装置210Aのアドレスとともに通知してもよい。
3.鍵管理センタ側装置230での処理
鍵管理センタ側装置230において、演算部232は、通信部235が通信回線140を介して受信者側装置210Aより受信した、あるいは、入力部231を介して受信者側装置210Aのアドレスとともに入力されたユーザAの個別情報IDを、受信者側装置210Aのアドレスに対応付けて記憶部234に記憶する(S686)。
【0173】
そして、演算部232は、鍵情報生成部233を用いて、bIDA∈{0,1}をランダムに選ぶ(S687)。
【0174】
次に、演算部232は、鍵情報生成部233を用いて、記憶部234に記憶されているマスタ鍵s及びユーザAの個別情報IDから、
【0175】
【数100】

【0176】
を計算する(S688)。但し、εはシステムに固有のストリングで予め定められているものとする。
【0177】
さらに、演算部232は、SK=(bIDA,d(1,IDA),d(2,IDA))をユーザAのプライベート鍵として、出力部236から出力するか、あるいは、通信回線140を介して通信部235から受信者側装置210Aに安全な方法(例えば、鍵管理センタ側装置230が受信者側装置210Aと共有する暗号鍵を用いた暗号通信)で送信する(S689)。なお、出力部236からプライベート鍵SKが出力された場合には、鍵管理センタはICカードを梱包した郵送等の安全な方法により、ユーザAにプライベート鍵SKを通知する。
4.受信者側装置210Aでの処理
受信者側装置210Aにおいて、演算部212は、通信部216が通信回線140を介して鍵管理センタ側装置230より受信した、あるいは、入力部211を介して入力されたプライベート鍵SKを、記憶部215に記憶する(S690)。
【0178】
また、演算部212は、ユーザAから入力部211を介してユーザAの個別情報IDの送信指示を受けると、通信回線140を介して通信部216からユーザAの個別情報IDを送信する(S691)。
5.送信者側装置210Bでの処理
送信側装置210Bにおいて、演算部212は、通信部216が通信回線140を介して鍵管理センタ側装置230より受信した、あるいは、入力部211を介して入力されたシステムパラメータPKを、記憶部215に記憶する(S692)。
【0179】
また、送信側装置210Bにおいて、演算部212は、通信部216が通信回線140を介して受信側装置210Aより受信した、あるいは、入力部211を介して入力されたユーザAの個別情報IDを、記憶部215に記憶する(S693)。
【0180】
次に、ユーザBは、入力部211を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S694)。
【0181】
メッセージ文Mが入力されると、演算部212は、入力されたメッセージMを記憶部215に記憶する(S695)。
【0182】
そして、演算部212は、乱数生成部213を用いて、R∈{0,1}lをランダムに選ぶ(S696)。
【0183】
次に、演算部212は、S696で選択されたRと、記憶部215に記憶されているメッセージ文M、システムパラメータPK、ユーザAの個別情報ID及びユーザBの個別情報IDと、を用いて、
【0184】
【数101】

【0185】
なるr0,r1∈ZqおよびK∈{0,1}mを計算する(S697)。
【0186】
さらに、演算部212は、S697で計算されたr、r及びKを用いて、
【0187】
【数102】

【0188】
を計算する(S698)。
【0189】
そして、演算部212は、S98で作成した暗号文C=(U10,U11,U20,U21,V0,V1,W,Z)を出力部217から出力するか、あるいは、通信回線140を介して通信部216から受信者側装置210Aに送信する(S699)。なお、出力部217から暗号文が出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
6.受信者側装置210Aでの処理
受信者側装置210Aの演算部212は、通信部216が通信回線140を介して送信者側装置210Bより受信した、あるいは、ユーザAが入力部211を介して入力した暗号文Cを記憶部215に記憶する(S700)。
【0190】
次に、演算部212は、暗復号化部214を用いて、記憶部215に記憶されている暗号文Cに対して、記憶部215に記憶されているユーザAの個別情報ID及びプライベート鍵SKから、
【0191】
【数103】

【0192】
なるR∈{0,1}lを計算する(S701)。
【0193】
さらに、演算部212は、S701で計算されたRと、記憶部215に記憶されているユーザAの個別情報ID及びユーザBの個別情報IDと、を用いて、
【0194】
【数104】

【0195】
により、r0,r1∈ZqおよびK∈{0,1}mを計算する(S702)。
【0196】
次に、演算部212は、
【0197】
【数105】

【0198】
なるR’∈{0,1}lを計算する(S703)。
【0199】
そして、演算部212は、S701で計算されたRと、S702で計算されたrと、S703で計算されたR’と、暗号文Cと、から、
【0200】
【数106】

【0201】
の検査式が成立するか否かを検査する(S704)。
【0202】
そして、この検査式が成立する場合には、
【0203】
【数107】

【0204】
を計算する(S705)。
【0205】
さらに、演算部212は、
【0206】
【数108】

【0207】
の検査式が成立するか否かを検査する(S706)。この検査式が成立する場合には、S73での計算結果Mをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文C=(U10,U11,U20,U21,V0,V1,W,Z)を不正な暗号文とみなして棄却する。
【0208】
本実施形態の暗号方式では、非特許文献1および非特許文献4に記載の手法と同様の手法により、BDH(Bilinear Diffie-Hellman)問題の計算量的困難性を暗号学的仮定にしてIND-ID-CCA安全であることが証明可能である。
【0209】
このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のIDベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【0210】
本実施形態のIDベース暗号方式は、計算量の大きい双線形写像を用いた計算が少ないため、効率の良い暗号化および復号化が可能である。
【0211】
本実施形態における暗号通信方法において、暗号文の一部であるWへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【0212】
また、本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【0213】
上記実施形態では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびIDベース暗号が使われている様々なシステムに適用することが可能である。
【0214】
また、以上に記載した実施形態における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。
【0215】
図12は、本発明の第五、第六、第七及び第八の実施形態に共通する通信システム800の概略図である。
【0216】
図示するように、通信システム800は、受信者側装置810と、送信者側装置820と、を備えており、これらは通信回線140に接続されている。
【0217】
図13は、受信者側装置810の概略図である。
【0218】
図示するように、受信者側装置810は、情報を入力する入力部811と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置810の各部の制御を行う演算部812と、記憶部815と、通信回線140を介して送信者側装置820と通信を行う通信部816と、情報を出力する出力部817と、を備えている。
【0219】
また、演算部812は、暗号化鍵及び復号化鍵を生成する鍵情報生成部813と、暗復号化処理を行う暗復号化部814と、を有する。
【0220】
図14は、送信者側装置820の概略図である。
【0221】
図示するように、送信者側装置820は、情報を入力する入力部821と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置820の各部の制御を行う演算部822と、記憶部825と、通信回線140を介して受信者側装置810と通信を行う通信部826と、情報を出力する出力部827と、を備えている。
【0222】
また、演算部822は、乱数を生成する乱数生成部823と、暗復号化処理を行う暗復号化部824と、を有する。
【0223】
上記構成の受信者側装置810及び送信者側装置820は、図4に示すような、CPU401と、メモリ402と、HDD等の外部記憶装置403と、CD-ROMやDVD-ROM等の可搬性を有する記憶媒体409から情報を読み出す読取装置404と、キーボードやマウスなどの入力装置405と、ディスプレイなどの出力装置406と、通信回線300を介して相手装置と通信を行なうための通信装置407と、これらの各装置を接続するバス408とを備えた一般的なコンピュータ400において、CPU401がメモリ402上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ402や外部記憶装置403が記憶部815、825に利用され、通信装置408が通信部816、826に利用され、入力装置406や読取装置405が入力部811、821に利用され、そして、出力装置407が出力部817、827に利用される。
【0224】
この所定のプログラムは、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、外部記憶装置403にダウンロードされ、それから、メモリ402上にロードされてCPU401により実行されるようにしてもよい。また、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、メモリ402上に直接ロードされ、CPU401により実行されるようにしてもよい。
(第五の実施形態)
図15は、本発明の第五の実施形態における動作手順を説明するための図である。
【0225】
本実施形態は、通信回線140を介して、受信者側装置810と、送信者側装置820と、の間で暗号通信を行う暗号システムに関するものであり、公開鍵暗号(以下、暗号方式PKE)が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方法を利用しながら別の暗号システム(より安全性の高い暗号システム)を構築する場合について述べる。
【0226】
なお、本実施形態における受信者側装置810及び送信者側装置820は、ある共通の暗号方式に対応しているものとする。
1.受信者側装置810での処理
受信者側装置810において、演算部812は、入力部811を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部813を用いて、暗号方式PKEの鍵生成のためのステップを2回実行することにより、2組の鍵のペア(PK,SK),(PK,SK)を生成する(S1000)。
【0227】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部816又は出力部817を介して、
【0228】
【数109】

【0229】
を新しい公開鍵として公開し(但し、nは負でない整数)(S1001)、
【0230】
【数110】

【0231】
を受信者側装置810のユーザの秘密鍵として記憶部815に記憶する(S1002)。
2.送信者側装置820での処理
送信者側装置820の演算部822は、通信部826又は入力部821を介して、受信者側装置810が公開している公開鍵PKを取得して、記憶部825に記憶する(S1003)。
【0232】
次に、送信者側装置820のユーザは、入力部821を介してメッセージ文M∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)を入力する(S1004)。
【0233】
メッセージ文Mが入力されると、演算部822は、入力されたメッセージ文Mを記憶部825に記憶する(S1005)。
【0234】
次に、演算部822は、乱数生成部823を用いて、メッセージ文Mに対して、暗号方式PKEのメッセージ空間に含まれるσ,σをランダムに選ぶ(S1006)。
【0235】
そして、演算部822は、暗復号化部824を用いて、
【0236】
【数111】

【0237】
を計算する(S1007)。但し、EPK(x)は、メッセージ文xを公開鍵PKを用いて該暗号方式PKEにて暗号化した結果を表す。
【0238】
さらに、演算部822は、暗復号化部824を用いて、
【0239】
【数112】

【0240】
を計算する(S1008)。
【0241】
そして、送信者側装置820の演算部822は、ステップS1008で生成した暗号文C=(U,U,V)を出力部827から出力するか、あるいは、通信部826から通信回線140を介して、受信者側装置810に送信する(S1009)。なお、出力部827から暗号文Cが出力された場合には、送信者側装置820のユーザは、郵送等により、受信者側装置810のユーザに暗号文Cを通知する。
3.受信者側装置810での処理
受信者側装置810の演算部812は、通信部816が通信回線140を介して送信者側装置820より受信した、あるいは、受信者側装置810のユーザが入力部811を介して入力した暗号文Cを記憶部815に記憶する(S1010)。なお、演算処理部812は、暗号文C=(U,U,V)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0242】
次に、演算部812は、暗復号化部814を用いて、
【0243】
【数113】

【0244】
を計算する(S1011)。但し、DSK(y)は、該暗号方式PKEにおいて、暗号文yを秘密鍵SKを用いて復号化した結果を表す。
【0245】
そして、演算部812は、暗復号化部814を用いて、記憶部815に記憶されている暗号文Cに対して、
【0246】
【数114】

【0247】
を計算することで、メッセージMを復号する(S1012)。
【0248】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
(第六の実施形態)
次に、本発明の第六の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、第五の実施形態よりも安全性の高い暗号システムを提供するものである。
【0249】
図16は、本発明の第六の実施形態における動作手順を説明するための図である。
1.受信者側装置810での処理
受信者側装置810において、演算部812は、入力部811を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部813を用いて、暗号方式PKEの鍵生成のためのステップを2回実行することにより、2組の鍵のペア(PK,SK),(PK,SK)を生成する(S1020)。
【0250】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部816又は出力部817を介して、
【0251】
【数115】

【0252】
を新しい公開鍵として公開し(但し、n,n,nは負でない整数)(S1021)、
【0253】
【数116】

【0254】
を受信者側装置810のユーザの秘密鍵として記憶部815に記憶する(S1022)。
2.送信者側装置820での処理
送信者側装置820の演算部822は、通信部826又は入力部821を介して、受信者側装置810が公開している公開鍵PKを取得して、記憶部825に記憶する(S1023)。
【0255】
次に、送信者側装置820のユーザは、入力部821を介してメッセージ文M∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)を入力する(S1024)。
【0256】
メッセージ文Mが入力されると、演算部822は、入力されたメッセージ文Mを記憶部825に記憶する(S1025)。
【0257】
次に、演算部822は、乱数生成部823を用いて、メッセージ文Mに対して、暗号方式PKEのメッセージ空間に含まれるσ,σをランダムに選び、また、R,R∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)をランダムに選ぶ(S1026)。
【0258】
そして、演算部822は、暗復号化部824を用いて、
【0259】
【数117】

【0260】
を計算する(S1027)。但し、EPK(x;R)は、乱数Rを確率的暗号におけるコイントスとして利用し、メッセージ文xを公開鍵PKを用いて該暗号方式PKEにて暗号化した結果を表す。即ち、暗号文が乱数Rによって変わってくるようにする。
【0261】
次に、演算部822は、乱数生成部823を用いて、τ∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)をランダムに選び(S1028)、さらに、演算部822は、暗復号化部824を用いて、
【0262】
【数118】

【0263】
を計算する(S1029)。
【0264】
そして、送信者側装置820の演算部822は、ステップS1029で生成した暗号文C=(U,U,V,W)を出力部827から出力するか、あるいは、通信部826から通信回線140を介して、受信者側装置810に送信する(S1030)。なお、出力部827から暗号文Cが出力された場合には、送信者側装置820のユーザは、郵送等により、受信者側装置810のユーザに暗号文Cを通知する。
3.受信者側装置810での処理
受信者側装置810の演算部812は、通信部816が通信回線140を介して送信者側装置820より受信した、あるいは、受信者側装置810のユーザが入力部811を介して入力した暗号文Cを記憶部815に記憶する(S1031)。なお、演算処理部812は、暗号文C=(U,U,V,W)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0265】
次に、演算部812は、暗復号化部814を用いて、
【0266】
【数119】

【0267】
を計算する(S1032)。但し、DSK(y)は、該暗号方式PKEにおいて、暗号文yを秘密鍵SKを用いて復号化した結果を表す。
【0268】
そして、演算部812は、暗復号化部814を用いて、記憶部815に記憶されている暗号文Cに対して、
【0269】
【数120】

【0270】
を計算し(S1033)、さらに、M∈{0,1}(m=n)、R,R∈{0,1}(m=n)、τ∈{0,1}(m=n)を計算し、
【0271】
【数121】

【0272】
を検査する(S1034)。
【0273】
そして、検査にパスすれば,出力部817を介して、メッセージ文Mを出力し、検査にパスしなければ暗号文Cを不正な暗号文とみなして拒否する。
【0274】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【0275】
本実施例の方法では、Bilinear Diffie-Hellman(BDH)問題の数学的性質であるランダム自己帰着性を利用するために、二重暗号の技術を用いる。ここで、二重暗号とは、既存の暗号システムによる暗号化および復号化を2度行うことを意味している。これにより、実施例1に記載の公開鍵暗号通信方法は、既存の暗号方式がLBDH(List Bilinear Diffie-Hellman)問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるBDH(Bilinear Diffie-Hellman)問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
(第七の実施形態)
次に、本発明の第七の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、非特許文献2に記載の変換方法を利用するものである。
【0276】
図17は、本発明の第七の実施形態における動作手順を説明するための図である。
1.受信者側装置810での処理
受信者側装置810において、演算部812は、入力部811を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部813を用いて、暗号方式PKEの鍵生成のためのステップを2回実行することにより、2組の鍵のペア(PK,SK),(PK,SK)を生成する(S1040)。
【0277】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部816又は出力部817を介して、
【0278】
【数122】

【0279】
を新しい公開鍵として公開し(但し、n,n,nは負でない整数)(S1041)、
【0280】
【数123】

【0281】
を受信者側装置810のユーザの秘密鍵として記憶部815に記憶する(S1042)。
2.送信者側装置820での処理
送信者側装置820の演算部822は、通信部826又は入力部821を介して、受信者側装置810が公開している公開鍵PKを取得して、記憶部825に記憶する(S1043)。
【0282】
次に、送信者側装置820のユーザは、入力部821を介してメッセージ文M∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)を入力する(S1044)。
【0283】
メッセージ文Mが入力されると、演算部822は、入力されたメッセージ文Mを記憶部825に記憶する(S1045)。
【0284】
次に、演算部822は、乱数生成部823を用いて、メッセージ文Mに対して、暗号方式PKEのメッセージ空間に含まれるσ,σをランダムに選び、また、r,r∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)をランダムに選ぶ(S1046)。
【0285】
そして、演算部822は、暗復号化部824を用いて、
【0286】
【数124】

【0287】
を計算する(S1047)。
【0288】
さらに、演算部822は、暗復号化部824を用いて、
【0289】
【数125】

【0290】
を計算する(S1048)。但し、EPK(x;R)は、乱数Rを確率的暗号におけるコイントスとして利用し、メッセージ文xを公開鍵PKを用いて該暗号方式PKEにて暗号化した結果を表す。即ち、暗号文が乱数Rによって変わってくるようにする。
【0291】
次に、演算部822は、乱数生成部823を用いて、τ∈{0,1}、m=n(nは、公開鍵として公開されている負でない整数)をランダムに選び(S1049)、さらに、演算部822は、暗復号化部824を用いて、
【0292】
【数126】

【0293】
を計算する(S1050)。
【0294】
そして、送信者側装置820の演算部822は、ステップS1050で生成した暗号文C=(U,U,V)を出力部827から出力するか、あるいは、通信部826から通信回線140を介して、受信者側装置810に送信する(S1051)。なお、出力部827から暗号文Cが出力された場合には、送信者側装置820のユーザは、郵送等により、受信者側装置810のユーザに暗号文Cを通知する。
3.受信者側装置810での処理
受信者側装置810の演算部812は、通信部816が通信回線140を介して送信者側装置820より受信した、あるいは、受信者側装置810のユーザが入力部811を介して入力した暗号文Cを記憶部815に記憶する(S1052)。なお、演算処理部812は、暗号文C=(U,U,V)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0295】
次に、演算部812は、暗復号化部814を用いて、
【0296】
【数127】

【0297】
を計算する(S1053)。但し、DSK(y)は、該暗号方式PKEにおいて、暗号文yを秘密鍵SKを用いて復号化した結果を表す。
【0298】
そして、演算部812は、暗復号化部814を用いて、記憶部815に記憶されている暗号文Cに対して、
【0299】
【数128】

【0300】
を計算し(S1054)、さらに、M∈{0,1}(m=n)、r,r∈{0,1}(m=n)、τ∈{0,1}(m=n)を計算し、
【0301】
【数129】

【0302】
を検査する(S1055)。
【0303】
そして、検査にパスすれば,出力部817を介して、メッセージ文Mを出力し、検査にパスしなければ暗号文Cを不正な暗号文とみなして拒否する。
【0304】
本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【0305】
また、第五及び第六の実施形態の場合と同様にして、既存の暗号方式がLBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
(第八の実施形態)
本実施形態では、受信者側装置810を用いるユーザAと送信者側装置820を用いるユーザBとが通信を行う通信システム800において、送信者側装置820のユーザBが、ユーザAの受信者側装置810において作成された公開鍵情報を用いて、通信回線140を介して暗号通信を行う方法について述べる。
【0306】
図18は、本発明の第八の実施形態における動作手順を説明するための図である。
1.受信者側装置810での処理
受信者側装置810において、演算部812は、入力部811を介してユーザAから鍵生成の指示を受け付けると、鍵情報生成部813を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0307】
【数130】

【0308】
なる双線形写像eを作成する(S1060)。
【0309】
次に、演算部812は、鍵情報生成部813を用いて、s1,s2∈ZqおよびP∈G1をランダムに選ぶ(S1061)。
【0310】
そして、演算部812の鍵情報生成部813は、ランダムに選んだs、s及びPを用いて、
【0311】
【数131】

【0312】
を生成する(S1062)。
【0313】
そして、演算部812は、SKA=(dIDA,1,dIDA,2)を復号化(秘密)鍵として、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,IDA,H,H)を暗号化(公開)鍵として、両者を記憶部815に記憶する(S1063)。但し、
【0314】
【数132】

【0315】
であり,m,nは自然数、IDA∈{0,1}m,H,Hは、
【0316】
【数133】

【0317】
なるハッシュ関数を意味する。
【0318】
次に、演算部812は、暗号化(公開)鍵PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,IDA,H,H)を、出力部817から出力するか、あるいは、通信部816から通信回線140を介して送信者側装置820に送信する(S1064)。なお、出力部817から暗号化(公開)鍵PKが出力された場合には、ユーザAは、郵送等によりユーザBに暗号化(公開)鍵PKを通知する。
2.送信者側装置820での処理
送信者側装置820の演算部822は、通信部826が通信回線140を介して受信者側装置810より受信した、あるいは、ユーザBが入力部821を介して入力した暗号化(公開)鍵PKを記憶部825に記憶する(S1065)。
【0319】
次に、ユーザBは、入力部821を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S1066)。
【0320】
メッセージ文Mが入力されると、演算部822は、入力されたメッセージ文Mを記憶部825に記憶する(S1067)。
【0321】
そして、演算部822は、乱数生成部823を用いて、メッセージMに対して、r∈Zをランダムに選び(S1068)、
【0322】
【数134】

【0323】
を計算する。さらに,記憶部125に記憶されている暗号化(公開)鍵PK及びメッセージMと、暗復号化部124を用いて、
【0324】
【数135】

【0325】
を計算し,さらに,
【0326】
【数136】

【0327】
を計算する(S1069)。
【0328】
そして、演算部122は、暗号文C=(U,V0,V1)を、出力部827から出力するか、あるいは、通信部826から通信回線140を介して受信者側装置810に送信する(S1070)。なお、出力部827から暗号文Cが出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
3.受信者側装置810での処理
受信者側装置810の演算部812は、通信部816が通信回線140を介して送信者側装置820より受信した、あるいは、ユーザAが入力部811を介して入力した暗号文Cを記憶部815に記憶する(S1071)。
【0329】
次に、演算部812は、暗復号化部814を用いて、記憶部815に記憶されている暗号文Cに対して、記憶部815に記憶されているユーザAの復号(秘密)鍵SKから、
【0330】
【数137】

【0331】
を計算し(S1072),
【0332】
【数138】

【0333】
により、M∈{0,1}を計算する(S1073)。
【0334】
本実施例に記載の公開鍵暗号通信方法は、非特許文献1および非特許文献4に記載の手法と同様の手法により、Bilinear Diffie-Hellman(BDH)問題の計算量的困難性を暗号学的仮定として、IND−CPAの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【0335】
本実施例における暗号通信方法は,下記非特許文献6、7に記載の方法などを用いることにより,IND−CCAの意味での安全に強化することが可能である。
非特許文献6: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.
非特許文献7:E. Fujisaki and T. Okamoto: Secure integration of asymmetric and symmetric encryption schemes, Crypto’99, LNCS 1666. pp.537-554, Springer-Verlag, 1999.
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【0336】
また,本実施例の暗号方式において、((136)式における)V0、1の作成方法として、H2(ID||i,vi,1,i,2)を用いて共通鍵暗号における暗号化鍵Kを作成し、鍵Kを用いてメッセージ文Mを(該共通鍵暗号を用いて)暗号化することで、V0,V1を作成することも可能である.
図19は、本発明の第九、第十、第十一及び第十二の実施形態に共通する通信システム900の概略図である。
【0337】
図示するように、通信システム900は、受信者側装置910Aと、送信者側装置910Bと、鍵管理センタ側装置930と、を備えており、これらは通信回線140に接続されている。
【0338】
図20は、受信者側装置910A及び送信者側装置910Bの概略図である。本実施形態における受信者側装置910A及び送信者側装置910Bは、同様の構成を有している。
【0339】
図示するように、受信者側装置910A及び送信者側装置910Bは、情報を入力する入力部911と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置910A又は送信者側装置910Bの各部の制御を行う演算部912と、記憶部915と、通信回線140を介して通信を行う通信部916と、情報を出力する出力部917と、を備えている。
【0340】
また、演算部912は、乱数を生成する乱数生成部913と、暗復号化処理を行う暗復号化部914と、を有する。
【0341】
図21は、鍵管理センタ側装置930の概略図である。
【0342】
図示するように、鍵管理センタ側装置930は、情報を入力する入力部931と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置930の各部の制御を行う演算部932と、記憶部934と、通信回線140を介して受信者側装置910A又は送信者側装置910Bと通信を行う通信部935と、情報を出力する出力部936と、を備えている。
【0343】
また、演算部932は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部933を有する。
【0344】
上記構成の受信者側装置910A、送信者側装置910B及び鍵管理センタ側装置930についても、図4に示すような、CPU401と、メモリ402と、HDD等の外部記憶装置403と、CD-ROMやDVD-ROM等の可搬性を有する記憶媒体409から情報を読み出す読取装置404と、キーボードやマウスなどの入力装置405と、ディスプレイなどの出力装置406と、通信回線300を介して相手装置と通信を行なうための通信装置407と、これらの各装置を接続するバス408とを備えた一般的なコンピュータ400において、CPU401がメモリ402上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ402や外部記憶装置403が記憶部915、934に利用され、通信装置408が通信部916、935に利用され、入力装置406や読取装置405が入力部911、931に利用され、そして、出力装置407が出力部917、936に利用される。
【0345】
この所定のプログラムは、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、外部記憶装置403にダウンロードされ、それから、メモリ402上にロードされてCPU401により実行されるようにしてもよい。また、読取装置404を介して記憶媒体409から、あるいは、通信装置407を介して通信回線140から、メモリ402上に直接ロードされ、CPU401により実行されるようにしてもよい。
(第九の実施形態)
図22は、本発明の第九の実施形態における動作手順を説明するための図である。本実施形態では、第五の実施形態における方法をIDベース暗号に適用したものである。そして、第五の実施形態と同様に、IDベース暗号(以下、暗号方式IBE)が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方式IBEを利用しながら別の暗号システム(より安全性の高い暗号システム)を構築する場合について述べる。
【0346】
なお、本実施形態における受信者側装置910A、送信者側装置910B及び鍵管理センタ側装置930は、ある共通の暗号方式IBEに対応しているものとする。
1.鍵管理センタ側装置930での処理
鍵管理センタ側装置930の演算部932は、入力部931を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部933を用いて、暗号方式IBEのセットアップのためのステップを2回実行することにより、2組の鍵のペア(PK,MSK),(PK,MSK)を生成する(S1080)。
【0347】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部935又は出力部936を介して、
【0348】
【数139】

【0349】
をシステムパラメータとして公開し(但し、nは負でない整数)(S1081)、
【0350】
【数140】

【0351】
を鍵管理センタのマスタ鍵として記憶部934に記憶する(S1082)。
【0352】
そして、鍵管理センタ側装置930の演算部932は、入力部931を介してユーザからプライベート鍵の生成指示を受け付けると、ID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)をID情報とするユーザに対して、鍵情報生成部933を用いて、暗号方式IBEのプライベート鍵生成のためのステップを2回繰り返すことにより、2組のプライベート鍵のペアSKID,1,SKID,2を生成し、通信部935又は出力部936を介して、これらのペアをプライベート鍵SKIDとして、受信者側装置910Aに送信又は出力する(S1083)。
2.送信者側装置910Bでの処理
送信者側装置910Bの演算部912は、通信部916又は入力部911を介して、鍵管理センタ側装置930が公開しているシステムパラメータPKを取得して、記憶部915に記憶する(S1084)。
【0353】
次に、送信者側装置910Bのユーザは、入力部911を介してメッセージ文M∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)と、受信者側装置910AのユーザのID情報であるID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)を入力する(S1085)。
【0354】
メッセージ文MとID情報が入力されると、演算部912は、入力されたメッセージ文MとID情報を記憶部915に記憶する(S1086)。
【0355】
次に、演算部912は、乱数生成部913を用いて、メッセージ文M及びID情報に対して、暗号方式IBEのメッセージ空間に含まれるσ,σをランダムに選ぶ(S1087)。
【0356】
そして、演算部912は、暗復号化部914を用いて、
【0357】
【数141】

【0358】
を計算する(S1088)。但し、EPK(x)は、メッセージ文xをシステムパラメータPKを用いて該暗号方式IBEにて暗号化した結果を表す。
【0359】
さらに、演算部912は、暗復号化部914を用いて、
【0360】
【数142】

【0361】
を計算する(S1089)。
【0362】
そして、送信者側装置910Bの演算部912は、ステップS1089で生成した暗号文C=(U,U,V)を出力部917から出力するか、あるいは、通信部916から通信回線140を介して、受信者側装置910Aに送信する(S1090)。なお、出力部917から暗号文Cが出力された場合には、送信者側装置910Bのユーザは、郵送等により、受信者側装置910Aのユーザに暗号文Cを通知する。
3.受信者側装置910Aでの処理
受信者側装置910Aの演算部912は、鍵管理センタ側装置930からプライベート鍵SKIDを取得して、記憶部915に記憶する(S1091)。
【0363】
また、受信者側装置910Aの演算部912は、通信部916が通信回線140を介して送信者側装置910Bより受信した、あるいは、受信者側装置910Aのユーザが入力部911を介して入力した暗号文Cを記憶部915に記憶する(S1092)。なお、演算処理部912は、暗号文C=(U,U,V)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0364】
次に、演算部912は、暗復号化部914を用いて、
【0365】
【数143】

【0366】
を計算する(S1093)。但し、DSKID(y)は、該暗号方式IBEにおいて、暗号文yを秘密鍵SKIDを用いて復号化した結果を表す。
【0367】
そして、演算部912は、暗復号化部914を用いて、記憶部915に記憶されている暗号文Cに対して、
【0368】
【数144】

【0369】
を計算することで、メッセージMを復号する(S1094)。
【0370】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
(第十の実施形態)
図23は、本発明の第十の実施形態における動作手順を説明するための図である。本実施形態では、第六の実施形態における方法をIDベース暗号に適用したものである。
1.鍵管理センタ側装置930での処理
鍵管理センタ側装置930の演算部932は、入力部931を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部933を用いて、暗号方式IBEのセットアップのためのステップを2回実行することにより、2組の鍵のペア(PK,MSK),(PK,MSK)を生成する(S1100)。
【0371】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部935又は出力部936を介して、
【0372】
【数145】

【0373】
をシステムパラメータとして公開し(但し、n,n,n,nは負でない整数)(S1101)、
【0374】
【数146】

【0375】
を鍵管理センタのマスタ鍵として記憶部934に記憶する(S1102)。
【0376】
そして、鍵管理センタ側装置930の演算部932は、入力部931を介してユーザからプライベート鍵の生成指示を受け付けると、ID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)をID情報とするユーザに対して、鍵情報生成部933を用いて、暗号方式IBEのプライベート鍵生成のためのステップを2回繰り返すことにより、2組のプライベート鍵のペアSKID,1,SKID,2を生成し、通信部935又は出力部936を介して、これらのペアをプライベート鍵SKIDとして、受信者側装置910Aに送信又は出力する(S1103)。
2.送信者側装置910Bでの処理
送信者側装置910Bの演算部912は、通信部916又は入力部911を介して、鍵管理センタ側装置930が公開しているシステムパラメータPKを取得して、記憶部915に記憶する(S1104)。
【0377】
次に、送信者側装置910Bのユーザは、入力部911を介してメッセージ文M∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)と、受信者側装置910AのユーザのID情報であるID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)を入力する(S1105)。
【0378】
メッセージ文M及びID情報が入力されると、演算部912は、入力されたメッセージ文MとID情報を記憶部915に記憶する(S1106)。
【0379】
次に、演算部912は、乱数生成部913を用いて、メッセージ文M及びID情報に対して、暗号方式IBEのメッセージ空間に含まれるσ,σをランダムに選び、また、R,R∈{0,1}、m=nm=n(nは、システムパラメータとして公開されている負でない整数)をランダムに選ぶ(S1107)。
【0380】
そして、演算部912は、暗復号化部914を用いて、
【0381】
【数147】

【0382】
を計算する(S1108)。但し、EPK(ID,x;R)は、乱数Rを確率的暗号におけるコイントスとして利用し、メッセージ文xをシステムパラメータPKを用いて該暗号方式IBEにて暗号化した結果を表す。
【0383】
さらに、演算部912は、暗復号化部914を用いて、
【0384】
【数148】

【0385】
を計算する(S1109)。
【0386】
そして、送信者側装置910Bの演算部912は、ステップS1089で生成した暗号文C=(U,U,V,W)を出力部917から出力するか、あるいは、通信部916から通信回線140を介して、受信者側装置910Aに送信する(S1110)。なお、出力部917から暗号文Cが出力された場合には、送信者側装置910Bのユーザは、郵送等により、受信者側装置910Aのユーザに暗号文Cを通知する。
3.受信者側装置910Aでの処理
受信者側装置910Aの演算部912は、鍵管理センタ側装置930からプライベート鍵SKIDを取得して、記憶部915に記憶する(S1111)。
【0387】
また、受信者側装置910Aの演算部912は、通信部916が通信回線140を介して送信者側装置910Bより受信した、あるいは、受信者側装置910Aのユーザが入力部911を介して入力した暗号文Cを記憶部915に記憶する(S1112)。なお、演算処理部912は、暗号文C=(U,U,V,W)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0388】
次に、演算部912は、暗復号化部914を用いて、
【0389】
【数149】

【0390】
を計算する(S1113)。但し、DSKID(y)は、該暗号方式IBEにおいて、暗号文yを秘密鍵SKIDを用いて復号化した結果を表す。
【0391】
そして、演算部912は、暗復号化部914を用いて、記憶部915に記憶されている暗号文Cに対して、
【0392】
【数150】

【0393】
を計算し(S1114)、さらに、M∈{0,1}(m=n)、R,R∈{0,1}(m=n)、τ∈{0,1}(m=n)を計算し、
【0394】
【数151】

【0395】
を検査する(S1115)。
【0396】
そして、検査にパスすれば,出力部817を介して、メッセージ文Mを出力し、検査にパスしなければ暗号文Cを不正な暗号文とみなして拒否する。
【0397】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施形態では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【0398】
また、実施例1の場合と同様にして、既存の暗号方式がLBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
(第十一の実施形態)
図24は、本発明の第十一の実施形態における動作手順を説明するための図である。本実施形態では、第七の実施形態における方法をIDベース暗号に適用したものである。
1.鍵管理センタ側装置930での処理
鍵管理センタ側装置930の演算部932は、入力部931を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部933を用いて、暗号方式IBEのセットアップのためのステップを2回実行することにより、2組の鍵のペア(PK,MSK),(PK,MSK)を生成する(S1120)。
【0399】
次に、受信者側装置810は、入力部811を介してユーザからの指示を受けると、通信部935又は出力部936を介して、
【0400】
【数152】

【0401】
をシステムパラメータとして公開し(但し、n,n,n,nは負でない整数)(S1121)、
【0402】
【数153】

【0403】
を鍵管理センタのマスタ鍵として記憶部934に記憶する(S1122)。
【0404】
そして、鍵管理センタ側装置930の演算部932は、入力部931を介してユーザからプライベート鍵の生成指示を受け付けると、ID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)をID情報とするユーザに対して、鍵情報生成部933を用いて、暗号方式IBEのプライベート鍵生成のためのステップを2回繰り返すことにより、2組のプライベート鍵のペアSKID,1,SKID,2を生成し、通信部935又は出力部936を介して、これらのペアをプライベート鍵SKIDとして、受信者側装置910Aに送信又は出力する(S1123)。
2.送信者側装置910Bでの処理
送信者側装置910Bの演算部912は、通信部916又は入力部911を介して、鍵管理センタ側装置930が公開しているシステムパラメータPKを取得して、記憶部915に記憶する(S1124)。
【0405】
次に、送信者側装置910Bのユーザは、入力部911を介してメッセージ文M∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)と、受信者側装置910AのユーザのID情報であるID∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)を入力する(S1125)。
【0406】
メッセージ文M及びID情報が入力されると、演算部912は、入力されたメッセージ文MとID情報を記憶部915に記憶する(S1126)。
【0407】
次に、演算部912は、乱数生成部913を用いて、メッセージ文M及びID情報に対して、暗号方式IBEのメッセージ空間に含まれるσ,σをランダムに選び、また、r,r∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)をランダムに選ぶ(S1127)。
【0408】
そして、演算部912は、暗復号化部914を用いて、
【0409】
【数154】

【0410】
を計算する(S1128)。
【0411】
さらに、演算部912は、暗復号化部914を用いて、
【0412】
【数155】

【0413】
を計算する(S1129)。但し、EPK(ID,x;R)は、乱数Rを確率的暗号におけるコイントスとして利用し、メッセージ文xをシステムパラメータPKを用いて該暗号方式IBEにて暗号化した結果を表す。
【0414】
さらに、演算部912は、乱数生成部913を用いて、τ∈{0,1}、m=n(nは、システムパラメータとして公開されている負でない整数)をランダムに選び、暗復号化部914を用いて、
【0415】
【数156】

【0416】
を計算する(S1130)。
【0417】
そして、送信者側装置910Bの演算部912は、ステップS1130で生成した暗号文C=(U,U,V,W)を出力部917から出力するか、あるいは、通信部916から通信回線140を介して、受信者側装置910Aに送信する(S1131)。なお、出力部917から暗号文Cが出力された場合には、送信者側装置910Bのユーザは、郵送等により、受信者側装置910Aのユーザに暗号文Cを通知する。
3.受信者側装置910Aでの処理
受信者側装置910Aの演算部912は、鍵管理センタ側装置930からプライベート鍵SKIDを取得して、記憶部915に記憶する(S1132)。
【0418】
また、受信者側装置910Aの演算部912は、通信部916が通信回線140を介して送信者側装置910Bより受信した、あるいは、受信者側装置910Aのユーザが入力部911を介して入力した暗号文Cを記憶部915に記憶する(S1133)。なお、演算処理部912は、暗号文C=(U,U,V,W)が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【0419】
次に、演算部912は、暗復号化部914を用いて、
【0420】
【数157】

【0421】
を計算する(S1134)。但し、DSKID(y)は、該暗号方式IBEにおいて、暗号文yを秘密鍵SKIDを用いて復号化した結果を表す。
【0422】
そして、演算部912は、暗復号化部914を用いて、記憶部915に記憶されている暗号文Cに対して、
【0423】
【数158】

【0424】
を計算し(S1135)、さらに、M∈{0,1}(m=n)、R,R∈{0,1}(m=n)、τ∈{0,1}(m=n)を計算し、
【0425】
【数159】

【0426】
を検査する(S1136)。
【0427】
そして、検査にパスすれば,出力部817を介して、メッセージ文Mを出力し、検査にパスしなければ暗号文Cを不正な暗号文とみなして拒否する。
【0428】
本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【0429】
また、第六又は第七の実施形態の場合と同様にして、既存の暗号方式がLBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるBDH問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
(第十二の実施形態)
図25は、本発明の第十二の実施形態における動作手順を説明するための図である。
【0430】
本実施形態では、受信者側装置910Aを用いるユーザAと、送信者側装置910Bを用いるユーザBと、が、鍵管理センタ側装置930が作成した鍵情報を用いて、通信回線140を介して暗号通信を行う方法について述べる。
1.鍵管理センタ側装置930での処理
鍵管理センタ側装置930において、演算部932は、入力部931を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部933を用いて、素数q,位数qの加法群G1,位数qの乗法群G2,および、
【0431】
【数160】

【0432】
なる双線形写像eを生成する(S1140)。
【0433】
次に、演算部932は、鍵情報生成部233を用いて、s1,2∈ZqおよびP∈G1をランダムに選ぶ(S1141)。
【0434】
そして、演算処理部932の鍵情報生成部933は、ランダムに選んだs1、s2及びPを用いて、
【0435】
【数161】

【0436】
を生成する(S1142)。
【0437】
そして、演算部932は、s=(s1,s2)をマスタ鍵として、PK=(q,G1,G2,e,l,m,n,P,Ppub,1,Ppub,2,H,H,E,D)をシステムパラメータとして、両者を記憶部934に記憶する(S1143)。但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,Hは、
【0438】
【数162】

【0439】
なるハッシュ関数を意味する。
【0440】
次に、演算部932は、システムパラメータPKを、出力部936から出力するか、あるいは、通信部935から通信回線140を介して送信者側端末910Bに送信する(S1144)。なお、出力部936からシステムパラメータPKが出力された場合には、鍵管理センタは郵送等によりユーザBにシステムパラメータPKを通知する。
2.受信者側装置910Aでの処理
受信者側装置910Aにおいて、演算部912は、入力部911を介してユーザAより受け付けたユーザAの個別情報IDAを記憶部915に記憶するとともに、通信回線140を介して通信部916から鍵管理センタ側装置930に送信する(S1145)。なお、ユーザAの個別情報IDAについては、ユーザAが郵送等によって鍵管理センタに受信者側装置910Aのアドレスとともに通知してもよい。
3.鍵管理センタ側装置930での処理
鍵管理センタ側装置930において、演算部932は、通信部935が通信回線140を介して受信者側装置910Aより受信した、あるいは、入力部931を介して受信者側装置910Aのアドレスとともに入力されたユーザAの個別情報IDを、受信者側装置910Aのアドレスに対応付けて記憶部934に記憶する(S1146)。
【0441】
そして、演算部932は、鍵情報生成部933を用いて、bIDA∈{0,1}をランダムに選ぶ(S1147)。
【0442】
次に、演算部932は、鍵情報生成部933を用いて、記憶部934に記憶されているマスタ鍵s及びユーザAの個別情報IDから、
【0443】
【数163】

【0444】
を計算する(S1148)。
【0445】
そして、演算部932は、SK=(bIDA,dIDA,1,dIDA,2)をユーザAのプライベート鍵として、出力部936から出力するか、あるいは、通信回線140を介して通信部935から受信者側装置910Aに安全な方法(例えば、鍵管理センタ側装置930が受信者側装置910Aと共有する暗号鍵を用いた暗号通信)で送信する(S1149)。なお、出力部936からプライベート鍵SKが出力された場合には、鍵管理センタはICカードの郵送等の安全な方法により、ユーザAにプライベート鍵SKを通知する。
4.受信者側装置910Aでの処理
受信者側装置910Aにおいて、演算部912は、通信部916が通信回線140を介して鍵管理センタ側装置930より受信した、あるいは、入力部911を介して入力されたプライベート鍵SKを、記憶部915に記憶する(S1150)。
【0446】
また、演算部912は、ユーザAから入力部911を介してユーザAの個別情報IDの送信指示を受けると、通信回線140を介して通信部916からユーザAの個別情報IDを送信する(S1151)。
5.送信者側装置910Bでの処理
送信側装置910Bにおいて、演算部912は、通信部916が通信回線140を介して鍵管理センタ側装置930より受信した、あるいは、入力部911を介して入力されたシステムパラメータPKを、記憶部915に記憶する(S1152)。
【0447】
また、送信側装置910Bにおいて、演算部912は、通信部916が通信回線140を介して受信側装置910Aより受信した、あるいは、入力部911を介して入力されたユーザAの個別情報IDを、記憶部915に記憶する(S1153)。
【0448】
次に、ユーザBは、入力部911を介してメッセージ文M∈{0,1}(nは正整数)を入力する(S1154)。
【0449】
メッセージ文Mが入力されると、演算部912は、入力されたメッセージMを記憶部915に記憶する(S1155)。
【0450】
そして、演算部912は、乱数生成部913を用いて、r∈Zqをランダムに選び(S1156)、
【0451】
【数164】

【0452】
を計算する。さらに、記憶部915に記憶されているメッセージ文M、システムパラメータPK、ユーザAの個別情報ID及びユーザBの個別情報IDと、を用いて、
【0453】
【数165】

【0454】
を計算し、
【0455】
【数166】

【0456】
を計算する(S1157)。
【0457】
そして、演算部912は、暗号文C=(U,V0,V1)を出力部917から出力するか、あるいは、通信回線140を介して通信部916から受信者側装置910Aに送信する(S1158)。なお、出力部917から暗号文が出力された場合には、ユーザBは、郵送等によりユーザAに暗号文Cを通知する。
6.受信者側装置910Aでの処理
受信者側装置910Aの演算部912は、通信部916が通信回線140を介して送信者側装置910Bより受信した、あるいは、ユーザAが入力部911を介して入力した暗号文Cを記憶部915に記憶する(S1159)。
【0458】
次に、演算部912は、暗復号化部914を用いて、記憶部915に記憶されている暗号文Cに対して、記憶部915に記憶されているユーザAの個別情報ID及びプライベート鍵SKから、
【0459】
【数167】

【0460】
を計算し(S1160),
【0461】
【数168】

【0462】
により、M∈{0,1}nを計算する(S1161)。
【0463】
本実施例に記載の公開鍵暗号通信方法は、非特許文献1および非特許文献4に記載の手法と同様の手法により、Bilinear Diffie-Hellman(BDH)問題の計算量的困難性を暗号学的仮定として、IND-ID-CPAの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-ID-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【0464】
本実施例における暗号通信方法は、上記非特許文献6,7に記載の方法などを用いることにより,IND-ID-CCAの意味での安全に強化することが可能である。
【0465】
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【0466】
また,本実施例の暗号方式において、((136)式における)V0,V1の作成方法として、H2(ID||i,vi,1,vi,2)を用いて共通鍵暗号における暗号化鍵Kを作成し、鍵Kを用いてメッセージ文Mを(該共通鍵暗号を用いて)暗号化することで、V0,V1を作成することも可能である。
【0467】
上記実施例では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびIDベース暗号が使われている様々なシステムに適用することが可能である。また、実施例における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。
【図面の簡単な説明】
【0468】
【図1】第一及び第二の実施形態に共通する通信システム100の概略図。
【図2】受信者側装置110の概略図。
【図3】送信者側装置120の概略図。
【図4】コンピュータ400の概略図。
【図5】第一の実施形態における動作手順を説明するための図。
【図6】第二の実施形態における動作手順を説明するための図。
【図7】第三及び第四の実施形態に共通する通信システム200の概略図。
【図8】受信者側装置210A及び送信者側装置210Bの概略図。
【図9】鍵管理センタ側装置230の概略図。
【図10】第三の実施形態における動作手順を説明するための図。
【図11】第四の実施形態における動作手順を説明するための図。
【図12】第五、第六、第七及び第八の実施形態の通信システム800の概略図。
【図13】受信者側装置110の概略図。
【図14】送信者側装置120の概略図。
【図15】第五の実施形態における動作手順を説明するための図。
【図16】第六の実施形態における動作手順を説明するための図。
【図17】第七の実施形態における動作手順を説明するための図。
【図18】第八の実施形態における動作手順を説明するための図。
【図19】第九、第十、第十一及び第十二の実施形態の通信システム900の概略図。
【図20】受信者側装置910A及び送信者側装置910Bの概略図。
【図21】鍵管理センタ側装置930の概略図。
【図22】第九の実施形態における動作手順を説明するための図。
【図23】第十の実施形態における動作手順を説明するための図。
【図24】第十一の実施形態における動作手順を説明するための図。
【図25】第十二の実施形態における動作手順を説明するための図。
【符号の説明】
【0469】
100、200、800、900:通信システム、110、210A、810、910A:受信者側装置、111、211、811、911:入力部、112、212、812、912:演算部、115、215、815、915:記憶部、116、216、816、916:通信部、117、217、817、917:出力部、120、210B、820、910B:送信者側装置、121、821:入力部、122、822:演算部、125、825:記憶部、126、826:通信部、127、827:出力部、230、930:鍵管理センタ側装置、231、911:入力部、232、932:演算部、234、934:記憶部、235、935:通信部、236、936:出力部、140:通信回線

【特許請求の範囲】
【請求項1】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
乱数s,sを選択するステップと、
公開する鍵情報の一部として、P,Q∈G1、および、双線形写像e:G1×G1→G2、を作成するステップと、
1=s1PおよびP2=s2Pを公開する鍵情報の一部として作成するステップと、
作成したP、Q、e、P、Pを、前記送信者側装置に送信するステップと、
を備え、
前記送信者側装置は、
前記受信者側装置又は前記鍵管理センタ側装置から、P、Q、e、P、Pを受信するステップと、
受信したP、Q、e、P、Pを用いて、e(Q,P1)およびe(Q,P2)を計算するステップと、
計算されたe(Q,P1)およびe(Q,P2)を用いて、前記受信者側装置に送信する暗号文を作成するステップと、
を備えること、
を特徴とする暗号通信方法。
【請求項2】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
(1)前記受信者側装置が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数1】

なる双線形写像eを作成するステップと、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶステップと、
【数2】

を算出するステップと、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を暗号化鍵として、記憶部に記憶するステップ(但し、m,nは自然数、H,Hは、
【数3】

なるハッシュ関数を意味する。)と、
前記暗号化鍵PKAを出力するステップと、
を行い、
(2)前記送信者側装置が、
メッセージ文M∈{0,1}nに対して、r∈Zをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵PKAを用いて、
【数4】

を計算するステップと、
計算したC=(U,V,W)を前記メッセージ文Mの暗号文として前記受信者側装置に送信するステップと、
を行い、
(3)前記受信者側装置が、
前記送信者側装置より受信した前記暗号文C=(U,V,W)に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【数5】

により、M∈{0,1}nを計算するステップと、
【数6】

の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Mをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Cを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項3】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
(1)前記受信者側装置が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数7】

なる双線形写像eを作成するステップと、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶステップと、
【数8】

を算出するステップと、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H,H)を暗号化鍵として、記憶部に記憶するステップ(但し、m,nは自然数、H,H,Hは、
【数9】

なるハッシュ関数を意味する。)と、
前記暗号化鍵PKAを出力するステップと、
を行い、
(2)前記送信者側装置が、
メッセージ文M∈{0,1}nに対して、σ∈{0,1}mをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵PKAを用いて、
【数10】


を計算するステップと、
【数11】


を計算するステップと、
計算したC=(U,V,W)を前記メッセージ文Mの暗号文として前記受信者側装置に送信するステップと、
を行い、
(3)前記受信者側装置が、
前記送信者側装置より受信した前記暗号文C=(U,V,W)に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【数12】


により、σ∈{0,1}を計算するステップと、
【数13】


により、Mを計算するステップと、
【数14】


により、r∈Zqを計算するステップと、
【数15】


の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Mをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Cを不正な暗号文とみなして棄却するステップと、
を行うこと
を特徴とする暗号通信方法。
【請求項4】
送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたIDベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
(1)前記鍵管理センタ側装置が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数16】


なる双線形写像eを作成するステップと、
s0,s1∈Z*qおよびP∈G1をランダムに選ぶステップと、
【数17】


を作成するステップと、
(s0,s1)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,0,Ppub,1,H,H,H,H4,E,D)を前記システムパラメータとして、記憶部に記憶するステップ(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数18】


なるハッシュ関数を意味する。)と、
前記システムパラメータPKを出力するステップと、
前記受信者側装置より受信した受信者側ユーザの個別情報IDAを記憶部に記憶するステップと、
IDA∈{0,1}をランダムに選ぶステップと、
前記マスタ鍵(s0,s1)を用いて、
【数19】


を計算するステップと、
計算したSK=(bIDA,dIDA,0,dIDA,1)を前記受信者側ユーザのプライベート鍵として出力するステップと、
を行い、
(2)前記送信者側装置が、
メッセージ文M∈{0,1}に対して、R∈{0,1}lをランダムに選ぶステップと、
メッセージ文M及びR、前記受信者側装置より受信した前記個別情報ID、前記鍵管理センタ側装置より出力された前記システムパラメータPKを用いて、
【数20】


なるr∈ZqおよびK∈{0,1}mを計算するステップと、
【数21】


を計算するステップ(但し、E(M)は平文Mをデータ暗号化鍵Kを用いて暗号化した結果を表す)と、
計算したC=(U,V0,V1,W,Z)を暗号文として前記受信者側装置に送信するステップと、
を行い、
(3)前記受信者側装置が、
前記送信者側装置より受信した前記暗号文C=(U,V0,V1,W,Z)に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵SKを用いて、
【数22】


なるR∈{0,1}lを計算するステップと、
【数23】


により、r∈ZqおよびK∈{0,1}mを計算するステップと、
【数24】


により、M∈{0,1}nを計算するステップ(但し、D(Y)は暗号文Yを鍵Kを用いて復号化した結果を表す。)と、
【数25】


の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Mをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Cを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項5】
請求項4に記載の暗号通信方法であって、
ハッシュ関数HからHへの入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行うこと、
を特徴とする暗号通信方法。
【請求項6】
送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたIDベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
(1)前記鍵管理センタ側装置が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数26】


なる双線形写像eを作成するステップと、
s10,s11,s20,s21∈Z*qおよびP∈G1をランダムに選ぶステップと、
【数27】


を作成するステップと、
SK=(s10,s11,s20,s21)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,10,Ppub,11,Ppub,1,Ppub,20,Ppub,21,Ppub,2,H,H,H,H4,E,D)をシステムパラメータとして、記憶部に記憶するステップ(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数28】


なるハッシュ関数を意味する。)と、
前記システムパラメータPKを出力するステップと、
前記受信者側装置より受信した受信者側ユーザの個別情報IDAを記憶部に記憶するステップと、
IDA∈{0,1}をランダムに選ぶステップと、
前記マスタ鍵SKを用いて、
【数29】


を計算するステップと、
計算したSK=(bIDA,d(1,IDA),d(2,IDA))を前記受信者側ユーザのプライベート鍵として出力するステップと、
を行い、
(2)前記送信者側装置が、
メッセージ文M∈{0,1}に対して、R∈{0,1}lをランダムに選ぶステップと、
メッセージ文M及びR、前記受信者側装置より受信した前記個別情報ID、前記鍵管理センタ側装置より出力されたシステムパラメータPKを用いて、
【数30】


なるr0,r1∈ZqおよびK∈{0,1}mを計算するステップと、
【数31】


を計算するステップ(但し、E(M)は平文Mをデータ暗号化鍵Kを用いて暗号化した結果を表す)と、
計算したC=(U10,U11,U20,U21,V0,V1,W,Z)を暗号文として前記受信者側装置に送信するステップと、
を行い、
(3)前記受信者側装置が、
前記送信者側装置より受信した前記暗号文C=(U10,U11,U20,U21,V0,V1,W,Z)に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵SKを用いて、
【数32】


なるR∈{0,1}lを計算するステップと、
【数33】


により、r0,r1∈ZqおよびK∈{0,1}mを計算するステップと、
【数34】


なるR’∈{0,1}lを計算するステップと、
【数35】


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


を計算するステップ(但し、D(Y)は暗号文Yを鍵Kを用いて復号化した結果を表す。)と、
【数37】


の第二の検査式が成立するか否かを検査するステップと、
前記第二の検査式が成立する場合には、計算結果Mをメッセージ文として出力し、前記第一の検査式又は前記第二の検査式が成立しない場合には、前記暗号文Cを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項7】
請求項6に記載の暗号通信方法であって、
ハッシュ関数HからHへの入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行う
ことを特徴とする暗号通信方法。
【請求項8】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
前記受信者側装置又は鍵管理センタ側装置の演算部は、
乱数s,sを選択する処理と、
公開する鍵情報の一部として、P,Q∈G1、および、双線形写像e:G1×G1→G2、を作成する処理と、
1=s1PおよびP2=s2Pを公開する鍵情報の一部として作成する処理と、
作成したP、Q、e、P、Pを、通信部を介して前記送信者側装置に送信する処理と、
を行い、
前記送信者側装置の演算部は、
前記受信者側装置又は前記鍵管理センタ側装置から、P、Q、e、P、Pを、通信部を介して受信する処理と、
受信したP、Q、e、P、Pを用いて、e(Q,P1)およびe(Q,P2)を計算する処理と、
計算されたe(Q,P1)およびe(Q,P2)を用いて、前記受信者側装置に送信する暗号文を作成する処理と、
を行うこと、
を特徴とする暗号通信システム。
【請求項9】
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
演算部が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数38】


なる双線形写像eを作成する処理と、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶ処理と、
【数39】


を算出する処理と、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を暗号化鍵として、記憶部に記憶する処理(但し、m,nは自然数、H,Hは、
【数40】


なるハッシュ関数を意味する。)と、
前記暗号化鍵PKAを出力する処理と、
を行うこと、
を特徴とする受信者側装置。
【請求項10】
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
演算部が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数41】


なる双線形写像eを作成する処理と、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶ処理と、
【数42】


を算出する処理と、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H,H)を暗号化鍵として、記憶部に記憶する処理(但し、m,nは自然数、H,H,Hは、
【数43】


なるハッシュ関数を意味する。)と、
前記暗号化鍵PKAを出力する処理と、
を行うこと、
を特徴とする受信者側装置。
【請求項11】
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
演算部が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数44】


なる双線形写像eを作成する処理と、
s0,s1∈Z*qおよびP∈G1をランダムに選ぶ処理と、
【数45】


を作成する処理と、
(s0,s1)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,0,Ppub,1,H,H,H,H4,E,D)を前記システムパラメータとして、記憶部に記憶する処理(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数46】


なるハッシュ関数を意味する。)と、
前記システムパラメータPKを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報IDAを記憶部に記憶する処理と、
IDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵(s0,s1)を用いて、
【数47】


を計算する処理と、
計算したSK=(bIDA,dIDA,0,dIDA,1)を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行うこと、
を特徴とする鍵管理センタ側装置。
【請求項12】
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
演算部が、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数48】


なる双線形写像eを作成する処理と、
s10,s11,s20,s21∈Z*qおよびP∈G1をランダムに選ぶ処理と、
【数49】


を作成する処理と、
SK=(s10,s11,s20,s21)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,10,Ppub,11,Ppub,1,Ppub,20,Ppub,21,Ppub,2,H,H,H,H4,E,D)をシステムパラメータとして、記憶部に記憶する処理(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数50】


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


を計算する処理と、
計算したSK=(bIDA,d(1,IDA),d(2,IDA))を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行うこと、
を特徴とする鍵管理センタ側装置。
【請求項13】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数52】


なる双線形写像eを作成する処理と、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶ処理と、
【数53】


を算出する処理と、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H)を暗号化鍵として、記憶手段に記憶する処理(但し、m,nは自然数、H,Hは、
【数54】


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


なる双線形写像eを作成する処理と、
s1,s2∈Z*qおよびP,Q∈G1をランダムに選ぶ処理と、
【数56】


を算出する処理と、
SKA=(s1Q,s2Q)を復号化鍵とし、PKA=(q,G1,G2,e,m,n,P,Ppub,1,Ppub,2,H,H,H)を暗号化鍵として、記憶部に記憶する処理(但し、m,nは自然数、H,H,Hは、
【数57】


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


なる双線形写像eを作成する処理と、
s0,s1∈Z*qおよびP∈G1をランダムに選ぶ処理と、
【数59】


を作成する処理と、
(s0,s1)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,0,Ppub,1,H,H,H,H4,E,D)を前記システムパラメータとして、記憶手段に記憶する処理(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数60】


なるハッシュ関数を意味する。)と、
前記システムパラメータPKを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報IDAを記憶手段に記憶する処理と、
IDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵(s0,s1)を用いて、
【数61】


を計算する処理と、
計算したSK=(bIDA,dIDA,0,dIDA,1)を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行わせること、
を特徴とするプログラム。
【請求項16】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数q,位数qの加法群G1,位数qの乗法群G2,および、
【数62】


なる双線形写像eを作成する処理と、
s10,s11,s20,s21∈Z*qおよびP∈G1をランダムに選ぶ処理と、
【数63】


を作成する処理と、
SK=(s10,s11,s20,s21)をマスタ鍵とし、PK=(q,G1,G2,e,l,m,n,P,Ppub,10,Ppub,11,Ppub,1,Ppub,20,Ppub,21,Ppub,2,H,H,H,H4,E,D)をシステムパラメータとして、記憶部に記憶する処理(但し、l,m,nは自然数、Eは共通鍵暗号における暗号化関数、Dは共通鍵暗号における復号化関数を表し、H,H,H,H4は、
【数64】


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


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

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate