(57)【要約】【課題】あるグループの同じジェネレータを有する秘密鍵から複数の公開鍵を生成する方法、装置およびシステムを提供する。【解決手段】公開鍵暗号システムは、セキュリティ通信を利用する同一当事者に対して公開する複数の秘匿化された公開鍵を生成する。それらの秘匿化された公開鍵は、同じジェネレータを利用して単一の秘密鍵から生成される。この公開鍵の生成方法によれば、計算量の減少、記憶容量の節約及びセキュリティ・レベルの改善が実現される。【選択図】図１
2006141032.tif 000002
【特許請求の範囲】
【請求項１】
送信されるメッセージを暗号化するための公開鍵を生成する方法であって、
秘密鍵を選択するステップ、
所定のグループからの前記秘密鍵及びジェネレータを利用することにより、公開鍵を生成するステップ、
通信セッションの以前あるいは初めに、前記公開鍵を公開するステップとを有し、
複数の公開鍵が、複数の通信セッション毎に前記秘密鍵と前記ジェネレータを利用して生成される。
【請求項２】
請求項１に記載の方法であって、
前記公開鍵の生成ステップが、さらに、
所定の位数の前記グループを選択するステップ、
前記位数に基づいて前記秘密鍵を選択するステップ、
前記ジェネレータとして前記グループの要素を選択するステップ、
前記位数の内の指標として整数を選択するステップ、
前記秘密鍵、前記ジェネレータ及び前記指標に基づいて前記公開鍵を計算するステップを含む。
【請求項３】
請求項２に記載の方法であって、
前記公開鍵の生成ステップが、
等しい位数又はより小さい位数の前記グループのサブグループを選択するステップを含み、
前記秘密鍵と前記指標が前記サブグループの位数内にある。
【請求項４】
請求項３に記載の方法であって、
前記グループの位数が正の整数ｎであり、
前記サブグループの位数ｍは、ｍ≦ｎを満たし、
前記秘密鍵は、１＜｜ｘ｜＜ｍを満たし、
前記ジェネレータが前記グループの要素であり、
前記指標ｒは、０＜｜ｒ｜＜ｍを満たし、
前記公開鍵の計算が、ｙ１＝ｇｒ と ｙ２＝ｙ１ｘの計算であり、
新たな指標が選択されると、新たな公開鍵が生成される。
【請求項５】
請求項３に記載の方法であって、
y2に基づいた一連の公開鍵を計算するステップをさらに含む。
【請求項６】
請求項２に記載の方法であって、
前記ジェネレータのべき数を格納するステップと、
前記ジェネレータの格納されたべき数に基づいて新たな公開鍵を計算するステップを含む。
【請求項７】
請求項６に記載の方法であって、
格納された前記べき数の積として新たな公開鍵を計算するために前記ジェネレータの格納された前記べき数を使用するステップを含む。
【請求項８】
複数の公開鍵を生成するためのコンピュータ装置であって、
所定の位数のグループを選択するグループ選択手段と、
選択され又は生成された情報を格納する記憶手段と、
前記位数に基づく指標として秘密鍵と整数を選択する整数選択手段と、
前記グループからジェネレータを選択するジェネレータ選択手段と、
前記グループのグループ演算を実行するグループ演算手段と、
前記ジェネレータを有する前記秘密鍵から複数の公開鍵を生成する生成手段と、
前記グループ選択手段、前記記憶手段、前記整数選択手段、グループ演算手段及び前記生成手段を動作を制御する制御手段とを備える。
【請求項９】
請求項８に記載のコンピュータ装置であって、
位数ｍが前記グループの位数と等しいかあるいは前記グループの位数より小さい前記グループのサブグループを選択するサブグループ選択手段を備え、
前記秘密鍵ｘおよび前記指標ｒが、それぞれ１＜｜ｘ｜＜ｍ と ０＜｜ｒ｜＜ｍを満たし、
前記生成手段が、ｙ１＝ｇｒ及びｙ２ｙ１ｘの計算により公開鍵（ｙ１，  ｙ２）を計算すると共に、新たな指標が選択されると、新たな公開鍵を生成する。
【請求項１０】
請求項９に記載のコンピュータ装置であって、
前記記憶手段は、前記生成手段によって新たな公開鍵を生成するために使用する前記ジェネレータのべき数を格納する。
【請求項１１】
請求項１０に記載のコンピュータ装置であって、
格納された複数のべき数に基づいて、新たな公開鍵を格納された前記べき数の積として計算する。
【請求項１２】
請求項８に記載のコンピュータ装置であって、
前記制御手段、前記グループ選択手段、前記記憶手段、前記整数選択手段、グループ演算手段及び前記生成手段の少なくも一つが、ソフトウェア又はハードウェア、あるいはソフトウェアとハードウェアの組み合わせによって実現される。
【請求項１３】
送信するメッセージを公開鍵で暗号化する通信方法であって、
秘密鍵を選択するステップ、
所定のグループからの前記秘密鍵及びジェネレータを利用することにより、公開鍵を生成するステップ、
前記公開鍵を公開するステップ、
暗号化されたメッセージＣを得るために前記公開鍵を持つメッセージＭを暗号化するステップ、
通信チャネル上に前記暗号化されたメッセージＣを送信するステップ、
前記通信チャネル上の前記暗号化されたメッセージＣを受信するステップ、
前記メッセージＭを復元するために前記秘密鍵を有する前記暗号化されたメッセージＣを解読するステップとを有し、
複数の公開鍵が、複数の通信セッション毎に前記秘密鍵と前記ジェネレータを利用して生成される。
【請求項１４】
請求項１３に記載の通信方法であって、
等しい位数又はより小さい位数の前記グループのサブグループを選択するステップを含み、
前記公開鍵が、前記サブグループに基づいて生成される。
【請求項１５】
請求項１４に記載の通信方法であって、
前記グループの位数が正の整数ｎであり、
前記サブグループの位数ｍは、ｍ≦ｎを満たし、
前記秘密鍵は、１＜｜ｘ｜＜ｍを満たし、
前記ジェネレータが前記グループの要素であり、
前記指標ｒは、０＜｜ｒ｜＜ｍを満たし、
前記公開鍵の計算が、ｙ１＝ｇｒ と ｙ２＝ｙ１ｘの計算であり、
他の指標が選択されると、他の公開鍵が生成される。
【請求項１６】
請求項１５に記載の通信方法であって、
前記暗号化されたメッセージは、
ｌ＜｜ｋ｜＜ｍを満たす指標として整数ｋを選択するステップと、
下記の式を満たす、Ｃ＝（Ｃ１，  Ｃ２）の計算により暗号化されたメッセージＣを計算するステップとによって、前記メッセージＭから計算され、
前記暗号化されたメッセージが受信されると、Ｃ１がメッセージから検索され、新たな開鍵を生成するために利用される。
【数１】
2006141032.tif 000010
【請求項１７】
請求項１６に記載の通信方法であって、
複数の前記暗号化されたメッセージが受信されると、受信された前記暗号化されたメッセージの部分的な積に基づいて一連の新たな公開鍵が生成される。
【請求項１８】
通信システムであって、
１つ以上の暗号化装置と、
秘密鍵を有する解読装置と、
前記暗号化装置が前記解読装置と通信する1つ以上の通信チャネルとを備え、
新たな通信セッションが前記チャネルの1つで開始された場合、前記解読装置が、あるグループと同じジェネレータを有する前記秘密鍵から新たな公開鍵を生成する。
【請求項１９】
請求項１８に記載の通信システムであって、
前記解読装置が、新しい公開鍵の計算において使用される前記のジェネレータのべき数を格納する。
【請求項２０】
請求項１８に記載の通信システムであって、
前記暗号化されたメッセージが解読装置で受信されると、前記暗号化されたメッセージが新たな公開鍵を生成するために利用される。
【請求項２１】
1台以上のプロセッサ上で実行される公開鍵を生成するプログラムであって、
前記プロセッサに、
秘密鍵を選択する処理と、
所定のグループの前記秘密鍵とジェネレータを利用して公開鍵を生成する処理と、
前記公開鍵を、通信セッションの前或いは開始時に公開する処理とを実行させ、
複数の公開鍵を、複数の通信セッション毎に前記秘密鍵と前記ジェネレータを利用して生成するプログラム。
【請求項２２】
1台以上のプロセッサ上で実行される公開鍵を生成するプログラムであって、
前記プロセッサに、
秘密鍵を選択する処理と、
所定のグループの前記秘密鍵とジェネレータを利用して公開鍵を生成する処理と、
前記公開鍵を公開する処理と、
前記公開鍵を有するメッセージを暗号化する処理と、
前記暗号化されたメッセージを通信チャネル上に送信する処理と、
前記暗号化されたメッセージを前記通信チャネル上で受信する処理と、
前記メッセージを復元するための秘密鍵によって前記暗号化されたメッセージを解読する処理とを実行させ、
異なる複数の公開鍵を、複数の通信セッション毎に前記秘密鍵と前記ジェネレータを利用して生成するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ通信ネットワークセキュリティに関し、特に、公開鍵で暗号化する通信システム及びその通信方法に関する。
【背景技術】
【０００２】
ＩＰネットワーク、電気通信網、モバイルネットワーク及びパーソナル・エリア・ネットワークのようなコンピュータ通信ネットワークの増加に伴って、多くの利用形態が開発され、前述のコンピュータ通信ネットワークに展開されている。
【０００３】
これらの利用形態は、健康管理システム、電子処方システム、電子メールシステム、電子取引システム、電子オークションシステム、マルチメディアシステム、ペイＴＶシステム、位置情報提供システム、ユビキタスコンピューティングシステムなどを含んでいる。
【０００４】
しかし、これらのシステムによって転送される情報やより一般的なデータは、ハッキング、探索、盗聴、不正利用及び改ざんなどの影響を受ける。
【０００５】
セキュリティとプライバシーに対する懸念の程度は、利用形態毎に、特に、個人毎に異なるかもしれないが、デジタル情報が送信者から受信者に安全に配信されるということ、第三者も受信者も情報のセキュリティを危険にさらすことができないということが一般的に要求される。
【０００６】
さらに、送信者のプライバシーが、受信者のプライバシーと同様に、十分に保護されることも要求される。
【０００７】
情報のセキュリティを保護するための一例として、セキュリティ電子メールシステムがある。この例の場合、送信者及び受信者だけが電子メールを解読することができる。別の例として、セキュリティ電子支払いシステムがあり、そのシステムでは、口座の所有者だけがその口座の資金を利用することができる。
【０００８】
多くの場合において情報のプライバシーの問題は、その程度の高さではなく、情報セキュリティの問題と同程度の認識を必要とする。
【０００９】
前述のセキュリティ電子メールシステムとセキュリティ電子支払いシステム、すなわち、電子メールシステム、電子支払いシステムの参加者以外の誰もそのシステム上の通信（取引）の存在を知らないとその参加者が期待するシステムを考察する。
【００１０】
前述のセキュリティ電子メールシステムとセキュリティ電子支払いシステムを考慮すると、電子メールシステム、電子支払いシステムの参加者は、参加者以外の誰もそのシステム上の通信（取引）の存在を知らないということを期待する。
【００１１】
電子メールにおける送信者のプライバシーを保護するためには、受信者さえ送信者が誰か分からないという状況が必要かもしれない。
【００１２】
電子支払い処理については、受取人が支払人を識別することができないことが好ましいであろう。
【００１３】
情報のプライバシーに関する多くの他の例がある。
【００１４】
位置情報提供システムのサービスを利用する場合においては、モバイル装置を携帯する所有者の位置は、ほとんどの場合、その所有者の十分な管理の元にある。
【００１５】
電子ショッピングの場合では、支払者は、オンライン上の販売者に自分の購入履歴を推測されたくないと思い、さらに、購入履歴から自分の関心を推測されたくないと考えるだろう。
【００１６】
電子オークションにおいては、競売人は、競合者が自分の入札戦略を分析し、そして自分に競り勝つためにそれらの知識を利用するのを阻止したいと思うだろう。
【００１７】
他の例としては、匿名会員の管理や、電子投票のための匿名による投票者などの例がある。
【００１８】
一般に、暗号通信システムは、遠隔の場所相互間でメッセージを転送するために適用される。
【００１９】
このようなシステムは、一方の場所に少なくとも1つの符号化装置を有し、他方の位置に少なくとも1つの復号化装置を備えており、それら符号化装置及び復号化装置の双方がコンピュータ通信ネットワークに接続されている。
【００２０】
デジタルシステムにおいては、メッセージは、ディジタルメッセージ、すなわち、いくつかのアルファベットからなる一連の符号と定義される。
【００２１】
実際上は、アルファベットとして、符号０及び１から成る２進法によるアルファベットが用いられる。
【００２２】
典型的な通信においては、ユーザがもう一人のユーザと暗号化された情報を送受信できるように、各ユーザの端末装置には暗号化装置と復号化装置の両方が装備されているのが一般的である。
【００２３】
従来、多くの公開鍵の暗号化及び復号化の技術は、プライバシーの場合と同程度のセキュリティを容易に提供することが可能である。
【００２４】
例えば、Rivestらによる米国特許第4,405,829号、及びEI Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(Tahir
EIGamal. A public-key cryptosystem and a signature scheme based on discrete
logarithms. Advances in Cryptology Proceedings of CRYPTO 84, pages 10-18, 1985)に開示された技術は、当該技術分野で広く知られた技術である。
【００２５】
上記Rivest特許およびEI  Gamalの技術を引用して説明する。
【００２６】
公開鍵暗号方式では、ユーザ(例えばユーザＡ)は、公開ファイルに、暗号化するための演算子か公開鍵（ＥＡ）を配置する。
【００２７】
ユーザＡは、対応する解読の演算子又は秘密鍵ＤＡであって、任意のメッセージＭについて以下の式を満たす解読の演算子又は秘密鍵ＤＡの詳細を自身で保持する。
【００２８】
ＤＡ（ＥＡ（Ｍ））＝Ｍ
【００２９】
実際の公開鍵システムでは、公開鍵（暗号鍵）ＥＡと秘密鍵ＤＡは、共に効率的に計算可能であるはずである。
【００３０】
しかし、公開鍵ＥＡを明らかにする場合、ユーザＡは秘密鍵ＤＡを危険にさらしてはならない。
【００３１】
すなわち、悪意ある者が、暗号鍵ＥＡとある種のプレーンテキストの暗号文のペアだけを与えられて、秘密鍵ＤＡを計算する効率的な方法を探すことが計算上実現可能であってはならない。
【００３２】
公開鍵システムでは、鍵を適切に選択することが、ユーザＡだけが秘密鍵ＤＡを効率的に計算できることを保証する。
【００３３】
別のユーザ（例えばユーザＢ）がユーザＡにメッセージＭを送りたい場合、ユーザＢは、常に、公開されているファイル中の公開鍵ＥＡを調べ、そのうえで暗号化されたメッセージＥＡ（Ｍ）ユーザＡに送信する。
【００３４】
受信に際して、ユーザＡは、下記に示す式を計算することによってメッセージを解読する。
【００３５】
ＤＡ（ＥＡ（Ｍ））＝Ｍ
【００３６】
通常の方法では秘密鍵DAを公開鍵EAから導き出すことができないので、ユーザＡだけが彼のもとへ送られたメッセージＥＡ（Ｍ）を解読することができる。
【００３７】
同様に、ユーザＡがユーザＢへ応答としてメッセージを送信したい場合、ユーザＡは、公開ファイルにおいて利用可能なユーザＢ用の暗号鍵ＥＢを用いて応答メッセージを暗号化する。
【００３８】
上述したセキュリティ通信の手順は、個人的な通信を受信したい各ユーザが、公開ファイルに自身の暗号鍵Ｅを配置しなければならないことを示す。
【００３９】
言いかえれば、RSA方式やEI Gamalのような従来の公開鍵暗号方式によって安全に他者と通信するためには、ユーザＡは外部に自身の公開鍵を公開することが要求される。
【００４０】
しかし、多くの場合、ユーザＡは、1つの公開鍵と秘密鍵のペア、すなわち、１つの公開鍵とそれに対応する唯一の秘密鍵とを所有するだけである。
【００４１】
公開鍵暗号方式のこの従来の簡易な使用法は、ユーザＡの公開鍵をユーザＡの識別情報として適切に機能させるとという偶発的な結果を生じる。
【００４２】
それは、たとえ十分に計画された他のプライバシー保護基準のみならずこの種の公開鍵暗号方式によってユーザに関するプライバシーが保護されるとしても、悪意ある者が、唯一の公開鍵についての使用パターンに基づいてユーザによって公表された情報を収集して観察することを通じて、保護されているユーザの活動を把握することが依然可能なことを意味する。
【００４３】
情報化時代において、プライバシーは、情報交換における重要な関心事として広く認識されている。
【００４４】
プライバシー調査では、全ての人々の８０〜９０パーセントがプライバシーについて関心を持っており、２５パーセントが、それに対して相当な金銭的あるいは不自由さに対する代価を払うつもりがあることを一貫して示している。
【００４５】
そのようなプライバシーの保護の重要性は、既存の公開鍵暗号方式の欠点をあらわにするだけでなく、新しく改善され、秘匿化された公開鍵方法論の重要性および緊急性を強調する。
【００４６】
仮に、ユーザＡが、自身の単一の公開鍵によって自身のプライバシーがあばかれるかもしれないと懸念するならば、RSA方式及びEI  Gamalによって示されているような従来の公開鍵暗号方式の範囲内で、自己の公開鍵における身元確認可能な特性を排除することは可能である。
【００４７】
その方法は、例えば、いくつかの異なる公開鍵を所有し、各公開鍵を異なる通信者に用心して公開することを関係者、すなわちユーザＡに指示するだけである。
【００４８】
多くの公開鍵ペアの所有に加えて、Watersらは、ユーザが単一の秘密鍵に対応する幾つかの公開鍵を同時に所有することができるようにする唯一無比の公開鍵スキーム（仕組み）を実現するために、Ei
Gamalによる暗号化方式を用いる方法を提案している。
【００４９】
B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（Receiver
Anonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121) (以下に、Waters)を参照。上記Watersに開示される技術を引用して説明する。
【特許文献１】米国特許第４，４０５，８２９号
【非特許文献１】EI Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(TahirEIGamal. A public-key cryptosystem and a signature scheme based on discretelogarithms. Advances in Cryptology Proceedings of CRYPTO 84, pages 10-18, 1985)
【非特許文献２】B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（ReceiverAnonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121)
【非特許文献３】応用暗号学のハンドブック（Handbook ofApplied Cryptography）(http://www.cacr.math.uwaterloo.ca/hac/)
【発明の開示】
【発明が解決しようとする課題】
【００５０】
複数の公開鍵ペアを使用することによって、従来の公開鍵暗号方式でもある程度までプライバシーに対する懸念を緩和することができるが、セキュリティを守る各個人は、依然として到底満足できるものではない。
【００５１】
実際、上述したような手法は多くの欠点を有する。
【００５２】
第１に、異なる各公開鍵がそれぞれに対応する個別の秘密鍵を持つことは、公開鍵の数が増加することに加えて、個人にとって公開鍵−秘密鍵のペアに対する管理コストが増加することを意味する。
【００５３】
第２に、異なる各公開鍵がそれぞれに対応する異なる秘密鍵を持つことは、秘密鍵の数が増加することに加えて、秘密鍵の紛失あるいは露見に対するセキュリティ上のリスクが増加することを意味する。
【００５４】
第３に、従来の公開鍵暗号方式を用いる人向けには非常に数が多いが、１００個の公開鍵のペアを所有する個人について考察する。上記１００個の公開鍵のペアを所有する個人が、双方向通信又は片方向通信のいずれかによって２００人の通信者と通信しようとしていると仮定する。
【００５５】
この結果、上記通信者の少なくとも二人に一人は、プライバシーを守るう個人のものと同一の公開鍵であることに気づくであろうし、それはプライバシーを守る個人にとって受け入れがたいプライバシーの侵害と明確に見なされる。
【００５６】
最終的に、暗号化されたメッセージの受信者は、そのメッセージを解読するために全ての秘密鍵を試さなければならないであろうし、それは非常に時間の浪費であり非能率的である。
【００５７】
Watersによるスキームは、付随するセキュリティ上のリスクといくつかの公開鍵ペアに対する管理コストを削減することが可能なように思える。
【００５８】
しかし、上記唯一無比の公開鍵スキームは、EI Gamalの暗号方式による公開鍵を構成するための種々のジェネレータを用いることによって、新しい公開鍵を生成するけれども、それは計算における最適化を困難にする。
【００５９】
例えば、（ｇ，  ｇａ）と（ｈ，  ｈａ）がWatersの唯一無比の公開鍵スキームによって生成された異なる公開鍵であると仮定する。ここで、ｇとｈは、異なるジェネレータである。
【００６０】
従来、EI Gamalによる暗号化方式は、単一のジェネレータだけを使用する。
【００６１】
従って、複数のジェネレータをオフラインで計算させることができ、かつ複数のジェネレータについて１つのテーブルだけを維持すればよいという利点が得られる。
【００６２】
Watersによるスキームは、複数の異なるジェネレータについての数種類のテーブルの維持、及びオンラインによる計算を要求するため、計算の最適化及び管理コストの何れの点においても好ましくない。
【課題を解決するための手段】
【００６３】
本発明は、セキュリティ通信を利用する同一の当事者に対して公開する複数の秘匿化された公開鍵を生成するための公開鍵暗号方式を提案する。それらの秘匿化された公開鍵は、同じジェネレータを利用して単一の秘密鍵から生成される。
【００６４】
特に、本発明は、（ｙ１＝ｇｒ，  ｙ２＝ｙ１ｘ）の式で仮定される同じジェネレーターｇに基づいて、秘密鍵xから複数の公開鍵を生成する方法と装置を提案する。新たな公開鍵は、異なる通信セッションや異なる通信者に応じて異なるｒが選択される場合に生成される。
【００６５】
特に、本発明は、数学上の有名なグループ理論の適用及び実装に基づく。
【００６６】
Ｇを有限の巡回グループとする。復号化鍵(秘密鍵)Ｄは、グループＧから選択された要素ｘである。ｇをグループＧのジェネレータとする。暗号化鍵(公開鍵)Ｅは、グループＧの要素のうち、以下に示す式に基づいて計算される一組のペアｙ１およびｙ２から成る。
【００６７】
ｙ１＝ｇｒ
【００６８】
ｙ２＝（ｙ１）ｘ
【００６９】
ここで、ｒは整数である（以下、「指標」と称する）。
【００７０】
もし、ｙ１又はｙ２が、元々グループＧの範囲外であるならば、グループＧへそれらをマッピングしなければならない。このマッピング方法は、選択されたグループによって定義されるように様々なグループ毎に異なっていてもよい。
【００７１】
さらに、異なるr(指標)が選択されると、新しい公開鍵が生成される。
【００７２】
符号化装置は以下に示すようにプレーンテキストＭを暗号化する。
【００７３】
【数２】
2006141032.tif 000003
【００７４】
ここで、ｋは整数(以下、「指定子」と称する)である。
【００７５】
以下の記号１で示す演算子はグループＧの可逆演算子である。
【００７６】
【数３】
2006141032.tif 000004
【００７７】
また、Ｃ１とＣ２は、グループＧの要素である。
【００７８】
送信機から暗号文Ｃを受け取ると、受信機側の解読装置は、以下のように、ＣをメッセージＭ´(すなわち、再構成されたプレーンテキスト)に変形する。
【００７９】
【数４】
2006141032.tif 000005
【００８０】
ここで、メッセージＭ´は、グループＧの要素である。記号１で示す演算子はグループＧの可逆演算子である。
【００８１】
グループＧの範囲外にある暗号化すべきメッセージは、暗号化前にいくつかのグループの要素に変換される。
【００８２】
後の復号化に続いて、復元されたグループ要素は、元のメッセージに変形されてもよい。
【００８３】
その変形方法は、種々のグループ毎に、あるいは種々の実施例毎に異なっていてもよい。
【００８４】
Ｃ１またはＣ２がグループＧの範囲外に元々ある場合、グループＧへそれらをマッピングする必要がある。
【００８５】
このマッピング方法は、種々のグループ毎、あるいは種々の実施例毎に異なっていてもよく、また、それらは、当該技術分野の当業者にとって広く知られている。
【００８６】
指標ｒの選択を通じて、ユーザは、単一の秘密鍵xに対応する複数の公開鍵を生成することができる。
【００８７】
このため、ユーザは、ジェネレータ（生成子）のべき数を格納するための単一のテーブルを保持し、そしてそれらをオフラインで計算することができる。これにより、オンライン計算のためのオーバヘッドが回避される。
【００８８】
Watersの提案に基づいたセキュリティ通信システムとは対照的に、本発明はセキュリティ通信システムのための斬新な秘匿化された公開鍵の方式を提案する。
【００８９】
本発明は、秘匿化された公開鍵を生成するためにジェネレータのべき数（累乗）を利用する。一方、EI  Gamalの暗号化方式及びWatersによるスキームでは、公開鍵を生成するためにジェネレータを直接利用する。  
【発明の効果】
【００９０】
本発明によれば、従来の技術に対して少なくとも次の利点が存在する。  
【００９１】
第１に、本発明は、プライバシー関係者に対して、通信履歴が重要であるセキュリティ通信を構築するために、自身の公開鍵を通信者に公開することを可能にする。
【００９２】
第２に、本発明は、複数の公開鍵を単一の秘密鍵に対応させるという新しい技術に基づくので、公開鍵のペアの個々の管理コストを非常に低減し、また、秘密鍵に関するセキュリティリスクを最大限低下させる。
【００９３】
第３に、本発明は、提案された秘匿化された公開鍵をより低コストで適用することを容易にし、かつ大量の計算を必要とするタスクを計算システムのオフライン時にあるいは閑散時に実行するための、新たな最適化技術を実現する。
【００９４】
第４に、本発明は、通信における追加コストを特に導入することなく、通信者に対する計算負荷を効果的、効率的に取り除くことにより、計算における不可避のオーバヘッドを縮小することができる。
【００９５】
第５に、本発明は、公開鍵によって消費される記憶容量を効率的に減少させることができる新しい最適化技術を実現する。
【００９６】
第６に、本発明は、公開鍵を秘匿化することによって、当然に秘密鍵の秘匿性を保証する。これと反対に、従来の公開鍵暗号方式においては、秘密鍵の正確な値は秘密であるが、秘密鍵は唯一の公開鍵によって必然的に識別される。このことは、いくつかの場合、例えば、ユーザがいくつかの秘密鍵を所有する場合や、異なる秘密鍵用の一連の秘匿化された公開鍵を生成する場合において、本発明の有用性を示している。この意味で、使用に際して秘密鍵は秘匿化されており、すなわち、それらは秘匿化された秘密鍵であるといえる。
【発明を実施するための最良の形態】
【００９７】
（第１の実施の形態）
【００９８】
セキュリティ通信システムにおける秘匿化された公開鍵を生成する方法、装置及びシステムについて説明する。
【００９９】
以下の詳細な説明では、本発明についての十分な理解を提供するために多くの限定的な詳細が示される。しかし、当業者にとって、これらの限定的な詳細のうちのいくつかがなくとも本発明が実現可能であることは明白であると思われる。
【０１００】
他の実施例において、広く知られた構成及び技術内容については、本発明の理解を妨げないようにするため詳細には説明しない。
【０１０１】
明細書全体にわたって、用語「グループ」は、他の定義が示されない限り以下のように定義される数学的な概念を指す。
【０１０２】
グループ（Ｇ，  ◇）は、次の３つの公理を満たすＧにおけるブール演算◇を備えた集合Ｇから成る。
【０１０３】
（１）  グループ演算は結合である。すなわち、Ｇのすべての要素ａ，ｂ，ｃについて、ａ◇（ｂ◇ｃ）＝（ａ◇ｂ）◇Ｃを満たす。
【０１０４】
（２）  Ｇのすべての要素ａについてａ◇ｅ＝ｅ◇ａ＝ａを満たすＧの単位元eがある。
【０１０５】
（３）  Ｇの各要素ａについて、ａ◇ａ−１＝ａ−１◇ａ＝ｅを満たすaの逆関数と呼ばれるＧの要素ａ−１が存在する。
【０１０６】
例えば、追加の演算を備えた整数Zの集合は、あるグループを形成する。
【０１０７】
単位元は“０”であり、整数ａの逆関数は整数ａ−１である。
【０１０８】
より詳細に関しては、オンラインで利用可能な応用暗号学のハンドブック（Handbook of Applied Cryptography）を参照(http://www.cacr.math.uwaterloo.ca/hac/)。
【０１０９】
本発明による通信システムは、複数の端末装置及び複数の通信チャネルを備える。
【０１１０】
図１は、本発明の一実施例を示すブロック図である。
【０１１１】
図１において、端末装置Ａは、複数のセッションによって端末装置ａと通信する。端末装置Ａには、端末装置ａに情報を送るための少なくとも1つの通信チャネルが存在する。
【０１１２】
そのセッションは、１つあるいは複数の通信チャネルを利用する。
【０１１３】
端末装置ａは、端末装置Ａに情報を送るために同じ通信チャネルを使用してもよいし、使用しなくてもよい。
【０１１４】
通信チャネルを通じて、端末装置のＡは、異なる通信セッション毎に、端末装置ａに各種の公開鍵Ｅａ〜Ｅｚを通知するが、その秘密鍵ｘについては秘匿する。
【０１１５】
端末装置ａは、必要に応じて端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同様である。
【０１１６】
図１に示されるように、異なるセッション毎に異なる公開鍵を生成することにより、端末装置ａあるいは任意の第三者が、端末装置Ａの活動パターンを推測することは事実上不可能である。
【０１１７】
例えば、電子オークション環境では、異なる公開鍵が各セッション毎に生成されるため、端末装置Ａからのユーザは、自身の入札パタ−ン及び戦略が他者によって推測及び分析されるのを防ぐことができる。
【０１１８】
また、図２は、本発明の他の実施例を示すブロック図である。
【０１１９】
図２において、端末装置Ａは、端末装置ａから端末装置ｚの複数の端末装置と通信する。
【０１２０】
端末装置Ａと各々の通信先との間で使用される通信チャネルは、同じでも、同じではなくてもよい。
【０１２１】
図２の左側に示されるように、通信チャネルを通じて、端末装置Ａは、異なる公開鍵Ｅａ〜Ｅｚを他の端末装置、すなわち、端末装置ａ，端末装置ｂ，・・・端末装置ｚにそれぞれ通知する。
【０１２２】
この場合、端末装置Ａと端末装置ａ〜端末装置ｚとの間に、「１対複数」の関係があるといえる。上記公開鍵の通知は様々な方法で実現することができる。
【０１２３】
例えば、公開鍵と一緒に明らかにされる他の情報があってもよいし、あるいは、公開鍵が電子メールか証明書に組み込まれてもよい。
【０１２４】
また、端末装置ａ〜端末装置ｚは、受信した公開鍵で暗号化される情報を端末装置Ａに送るために、端末装置ａ〜端末装置ｚの各々が端末装置Ａからの公開鍵を受け取る通信チャネルと同一の通信チャネルを使用してもよいし、使用しなくてもよい。
【０１２５】
上述の場合と同様に、端末装置Ａは、自身の秘密鍵ｘを秘密にする。
【０１２６】
同様に、端末装置ａ〜端末装置ｚは、必要に応じて、端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同じである。
【０１２７】
図２の右側に示すように、端末装置ａ〜ｚは、それぞれ自身の公開鍵Ｅａ〜Ｅｚを端末装置Ａに通知する。
【０１２８】
この場合、端末装置ａ〜ｚと端末装置のＡとの間に、「複数対１」の関係があるといえる。
【０１２９】
図３は、図１及び図２に示された通信システムに参加する送信側と受信側の間の好適な通信セッション例を示す。
【０１３０】
図３において、送信側が受信側に公開鍵を公表しようとする度に、送信側は、既存の公開鍵のプールから１つの公開鍵を選択する（ステップＳ３２）か、もしくは新しい公開鍵を生成する（ステップＳ３３）かを決定する（ステップＳ３１）。
【０１３１】
その後、送信側は受信側に対して公開鍵を送信する（ステップＳ３４）。
【０１３２】
受信側は、送信すべきメッセージがある場合(ステップＳ３５)には、送信側からの公開鍵を認識して(ステップＳ３６)、メッセージを暗号化しその暗号化されたメッセージを送信側に送る(ステップＳ３７)。
【０１３３】
最後に、送信側は、受信した暗号化されたメッセージを解読し(ステップＳ３８)、受信側から送信されたオリジナルのメッセージを復元する。
【０１３４】
なお、受信側が暗号化されたメッセージを送信側に送信することを欲する以前に、受信側が送信側から公開鍵を予め受け取っていることも想定される。
【０１３５】
既存の鍵と無関係に、送信側が常に異なる公開鍵を生成する（ステップＳ３３）ように構成されていてもよい。
【０１３６】
しかしながら、当業者であれば分かるように、既存の鍵の操作はゼロから公開鍵を計算するほど集中的な計算を必要とないので、既存の公開鍵のプールを使用することは、計算のオーバヘッドを著しく軽減する。
【０１３７】
送信機が自身の公開鍵を受信機へ最初に送るため、図３の送信機及び受信機が便宜的にそのように示されていることに留意すべきである。
【０１３８】
一旦受信機が送信機からの公開鍵を保持すれば、その受信機が暗号化されたメッセージを受信側である送信機に送る場合、その受信機は実際には送信機となる。
【０１３９】
２つの端末装置間の典型的な相互の通信セッションにおいて、上記役割は、セッションの間頻繁に逆転する。
【０１４０】
ここで、図４を参照すると、本発明による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図が示されている。
【０１４１】
ここで、送信機４１は、少なくとも、通信チャネルを処理する送信装置４３及び受信装置４５と、暗号文の解読を行う復号化装置４７と、公開鍵を生成する公開鍵生成装置４９とを備える。
【０１４２】
受信機４２は、少なくとも、送信装置４４と、受信装置４６と、プレーンテキストのような送信される情報の暗号化を行うための暗号化装置４８とを備える。
【０１４３】
送信機４１は、複数の公開鍵を受信機４２に公開してもよいし、送信機４１と受信機４２の間に複数のセッションがある場合、各セッションがそれぞれ送信機４１の異なる公開鍵を公開してもよい。
【０１４４】
また、送信機４１は、受信機として動作する場合、さらに暗号化装置４８を備える。
【０１４５】
同様に、受信機４２は、送信機として動作する場合、さらに復号化装置４７及び公開鍵生成装置４９を備える。
【０１４６】
図４に示す暗号化装置４８及び復号化装置４７については、どちらもデータ通信と暗号化の分野においてよく知られているものである。
【０１４７】
公開鍵生成装置４９について、以下に示す図５においてさらに詳細に説明する。
【０１４８】
図５を参照すると、制御装置５５は、鍵を管理する処理だけでなく公開鍵を生成する処理を制御する。
【０１４９】
記憶部５４は、秘密鍵、生成された公開鍵、受信した公開鍵及び制御装置５５によって要求される他のデータを格納する。
【０１５０】
なお、公開鍵生成装置４９で使用される記憶部５４は、オンチップレジスタ、ＲＯＭ及びＲＡＭのような情報を格納することが可能な全ての装置によって実現することができる。
【０１５１】
公開鍵生成装置４９は、受信した暗号文及び解読における中間で出力されるデータを格納するために、記憶部５４を復号化装置４７と共有することも可能である。
【０１５２】
公開鍵生成装置４９の他の構成要素については後述する。
【０１５３】
図５においては、「グループ」演算がグループ指数演算子５７によって処理される。
【０１５４】
「グループ」演算を別のグループ演算子によって処理する公開鍵生成装置４９の他の実施例も可能である。
【０１５５】
次に、本発明に従って秘匿化された公開鍵(“ＡＰＫ”)を生成する、図４及び図５に示す公開鍵生成装置４９の処理について説明する。
【０１５６】
図６は、ＡＰＫ−秘密鍵ペアを生成するための典型的な処理の流れを示す。
【０１５７】
まず、グループＧが、グループ選択手段５１によって選択される（ステップＳ６０）。
【０１５８】
例えば、コンピュータには、様々の適切なグループを表す様々なデータを格納するメモリが備えらえている。
【０１５９】
制御装置５５による管理のもと、グループ選択手段５１は、グループを示すデータの選択によって１つのグループを選択する。
【０１６０】
実際の運用においては、コンピュータ上で動作可能で、そのようなサービスを提供するいくつかの関数ライブラリの製品が既に提供されている。
【０１６１】
本発明を実施するアプリケーションプログラムは、いくつかの特定のパラメータと共に、上記のようなライブラリによって提供される特別の関数を呼び出すことも可能である。そして、呼び出された関数が、要求されたグループを返す。
【０１６２】
本実施例において、グループＧは有限の巡回グループであり、そのグループＧの位数はｎである。また、位数ｎは正整数である。
【０１６３】
有限の巡回グループＧの候補は以下のものを含むが、これらに限定されるものではない。
【０１６４】
（１）有限体Ｆｑ１における楕円曲線上の点からなるグループ
【０１６５】
（２）有限体Ｆｑ２の乗法グループＦｑ２、ただし、ｑ２＝ｐｍ１であり、ｍ１は正整数、Ｐは素数
【０１６６】
（３）Ｚｎ１のグループ、ただし、ｎ１は合成整数
【０１６７】
（４）Ｚｎ２の乗法グループ、ただし、ｎ２は素数。
【０１６８】
上記の４つの典型的な種類のグループにおいて、最初のグループは、最良のセキュリティパフォーマンスを有しており、一方、後の３つのグループは、当該技術分野において一般的に用いられている。
【０１６９】
グループＧの「有限の巡回」性が、グループ指数演算の結果がグループＧへマッピングされることを示している。しかし、そのマッピング方法はグループ毎に変わってもよい。さらに、それは、ジェネレータ（生成子）が存在することを示している。
【０１７０】
その後、部分グループ選択手段５２は、ｍ≦ｎである位数ｍのグループＧの部分グループを選択する(ステップＳ６１)。
【０１７１】
位数ｍとして素数が選択される場合、好ましいセキュリティパフォーマンスが得られる。
【０１７２】
グループＧ自身が部分グループとして選択される場合があることに留意する必要がる。これは、ｍ＝ｎの場合である。
【０１７３】
他の実施例として、グループＧが後に決定されるか又は選択されるという前提の場合には、部分グループの選択を省略することが可能である。それは、グループＧが数学的にグループＧ自身の部分グループであるため、グループＧ自身が部分グループとして暗黙に選択されていることを意味する。
【０１７４】
すなわち、グループＧ自身が部分グループとして選択されている場合(ｍ＝ｎとなる場合)、そのような選択は見かけ上実施されない。
【０１７５】
もちろん、部分グループの選択を省略する場合には、図５に示す部分グループ選択手段５２も省くことが可能である。
【０１７６】
次いで、整数選択手段５６は、秘密鍵ｘとしてｘが１＜｜ｘ｜＜ｍを満たすような整数を選択する(ステップＳ６２)。
【０１７７】
簡潔のため、ここでは、１つの秘密鍵から複数の公開鍵を生成する方法について主に説明するが、１つの端末装置が複数の秘密鍵を備えていることも考えられる。
【０１７８】
その後、ジェネレータ選択手段５３は、グループＧのジェネレータｇを選択して決定する（ステップＳ６３）。グループＧが有限の巡回グループである場合、常に少なくとも一つのジェネレータを有している。
【０１７９】
ジェネレータｇと秘密鍵ｘの選択は、互いに独立して行われることに留意する。
【０１８０】
すなわち、ステップＳ６２はステップＳ６３より前に説明されているが、それらの処理の順序は反対でもよいし、あるいは、それらの処理が並行して行われてもよい。
【０１８１】
Ｇ，ｍ，ｘ及びｇの選択の後、整数ｒが、制御装置５５の管理のもとで新しい公開鍵を生成するための、０＜｜ｒ｜＜ｍを満たす指標として選択される(ステップＳ６４)。
【０１８２】
Ｇ，ｍ，ｘ，ｇ及びｒの選択と共に、新しい公開鍵が、ｙ１＝ｇｒの演算、次に、ｙ２＝ｙ１ｘの演算によって生成される(ステップＳ６５)。
【０１８３】
その後、公開鍵（ｙ１，  ｙ２）は、暗号化のために受信機に公開される(ステップＳ６６)。
【０１８４】
もちろん、公開鍵と一緒に公開される他の情報があってもよい。
【０１８５】
ｇ，ｘ及びｒの選択は、それらの選択において連続性や依存関係が要求されない点に留意する。すなわち、そのような選択のステップＳ６２，Ｓ６３，Ｓ６４は任意の順番で、連続してあるいは同時に実行することが可能である。
【０１８６】
なお、ｇ，ｘ及びｒの選択は、任意にあるいは要求されるいくつかの基準に従ってなされてもよい。
【０１８７】
他方、前述の手順のうちのいくつかは制御装置５５によって省略され、どこか他所で実行されるかもしれない。
【０１８８】
例えば、グループＧ及び部分グループの選択手順を、信頼ある組織である第三者に割り当てることもできる。
【０１８９】
従って、グループ及び部分グループが外部的に決定されるので、制御装置５５はグループ及び部分グループを選択する手順をスキップする。
【０１９０】
さらに、１つの秘匿化された公開鍵が以前に生成されている場合、グループ、部分グループ、ジェネレータ及び秘密鍵の全てが既に選択及び決定されていることは確かである。
【０１９１】
それゆえ、新しい公開鍵を生成することになっている場合、制御装置５５は、これらの４ステップをスキップし、次のステップに直接進む。
【０１９２】
ｙ１又はｙ２が元々グループＧの範囲外にある場合、それらをグループＧへマッピングしなければならない。そのマッピング方法は、異なるグループ毎に変わってもよい。
【０１９３】
しかし、巡回グループＧは、そのようなマッピング方法があることを示している。
【０１９４】
前述の手順は、システムの単一の装置／モジュール(統合されたコンポーネントあるいは個別のコンポーネントを備えた)において、あるいはいくつかの手順を実行するシステムのそれぞれの装置に分散する方法で、それぞれ実行可能であることに留意する。
【０１９５】
（グループ、部分グループ及びジェネレータの選択の例）
【０１９６】
グループ、部分グループ及びジェネレータの選択例を、以下に示す。
【０１９７】
グループＺｐ＊が、ｐ＝１１、よって、Ｚ１１＊＝｛１，  ２，  ３，  ４，  ５，  ６，  ７，  ８，  ９，  １０｝の条件のもとで選択されたと想定する。
【０１９８】
「１１」が素数であるので、数学上、Ｚ１１＊の位数は１１−１＝１０となる。
【０１９９】
要素２は、Ｚ１１＊＝｛２ｉ
ｍｏｄ１１ ／ ｉ＝０，  １，  ・・・，  ９｝であることを容易に確認できることから、Ｚ１１＊のジェネレータである。
【０２００】
さらに、グループが部分グループそれ自身であるので、部分グループがＺ１１＊として選択される。
【０２０１】
部分グループの別の選択例は、例えば、位数５のジェネレータ３を持つ｛１，３，４，５，９｝である。
【０２０２】
さらに、３５＝１ ｍｏｄ １１であることは容易に確認できる。
【０２０３】
さらに、当該技術分野における当業者であれば分かるように、この装置及び構成要素の全ては、多様な考察に基づきハードウェア、ソフトウェア、ファームウェアあるいはそれらの組み合わせで実現できることができる。
【０２０４】
（キー生成の最適化）
【０２０５】
主として図６に示した典型的な法の例は、本発明による秘匿化された公開鍵を生成するために利用可能な多くの方法のうちのほんの１例である。
【０２０６】
同じ目的に使用することができるだけでなく処理の最適化を達成することができるより進んだ方法がある。
【０２０７】
最適化方法を説明するために、当該技術分野においてよく知られている符号化及び復号化する手順について、図４、図５及び図７を参照して簡潔に要約する。
【０２０８】
ここで、記号１で示す演算子は、Ｇの可逆演算子である。
【０２０９】
以下の記号２で示す演算子は、記号１で示す可逆演算子の正確な逆演算子である。
【０２１０】
【数５】
2006141032.tif 000006
【０２１１】
本発明を図７中の手順で適用する。
【０２１２】
プレーンテキストＭを暗号化するために、プレーンテキストＭがグループＧの要素として最初に表す（例えば、ＭはＡＳＣＩＩコードとして表わされる）（ステップＳ８０）。
【０２１３】
次いで、整数ｋが、１＜｜ｋ｜＜ｍを満たす指定子として選択され（ステップＳ８１）、そして、１ペアの値が以下のように計算される（ステップＳ８２）。
【０２１４】
【数６】
2006141032.tif 000007
ここで、Ｃ１とＣ２はグループＧの要素である。
【０２１５】
これらの演算処理の全ては図４に示す暗号化装置４８によって実行することができる。
【０２１６】
記号１による演算は、グループＧの乗算、除算、加算あるいは減算となる。
【０２１７】
Ｃ１又はＣ２が元々グループＧの範囲外にある場合、グループＧへそれらをマッピングしなければならない。そのマッピング方法は、各グループ毎に異なっていてもよい。
【０２１８】
この時、メッセージＭの暗号文がＣ＝（Ｃ１，  Ｃ２）として得られ（ステップＳ８３）、その暗号分が送信装置４４によって通信チャネル上に送信される（ステップＳ８３）。
【０２１９】
符号化されるグループＧの範囲外にあるメッセージＭについては、符号化前にいくつかのグループ要素に変換される。
【０２２０】
後の復号化に続いて、復元されたグループ要素はオリジナルメッセージへ戻されてもよい。
【０２２１】
その変換方法は、各グループ毎に異なっていてもよい。
【０２２２】
１例としては、メッセージをいくつかのブロック（それらの各々はグループＧの要素である）に分解し、Ｍを復元するために全てのブロックを連結する。
【０２２３】
通信チャネルの反対側で、暗号文メッセージＣが受信される（ステップＳ８４）。
【０２２４】
暗号文ＣからプレーンテキストＭを検索するために、２つの方法として、直接のべき数法かそうでないかを最初に決定する（ステップＳ８５）。
【０２２５】
べき数法の場合、ｒｂ＝Ｃ１ｘが最初に計算され（ステップＳ８６）、次に、以下の式による計算からＭが求められる（ステップＳ８７）。
【０２２６】
【数７】
2006141032.tif 000008
【０２２７】
そうでなければ、ｒａ＝Ｃ１−ｘが最初に計算され（ステップＳ８８）、次に、以下の式による計算からＭが求められる（ステップＳ８９）。
【０２２８】
【数８】
2006141032.tif 000009
【０２２９】
暗号文（Ｃ１，Ｃ２）の復号化に成功した後、復号化の実行に伴って、本発明による公開鍵生成装置４９は、（ｙ１＝Ｃ１−１，  ｙ２＝ｒａ）の書式で新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒａのみならず受信した暗号文を用いてもよい。
【０２３０】
同様に、公開鍵生成装置４９は、（ｙ１＝Ｃ１，  ｙ２＝ｒｂ）の書式で新しい秘匿化された公開鍵を生成するために復号化途中で出力された中間出力ｒｂのみならず受信した暗号文を用いてもよい。
【０２３１】
新しい秘匿化された公開鍵を生成する上記いずれかの方法によって、べき数演算が回避され、また計算効率が向上する。
【０２３２】
さらに、単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、公開鍵生成装置４９は、（ｙ２，ｙ２ｘ）の形式で新しい秘匿化された公開鍵を生成してもよい。
【０２３３】
この方法は、一連の公開鍵を生成するために複数回用いることが可能である。
【０２３４】
この方法では、公開鍵ｙ２の第２の部分が、次に続く公開鍵の最初の部分と同一であるので、生成された公開鍵による記憶容量の消費が非常に減少する。
【０２３５】
一連のｗ個の公開鍵について、記憶容量が（ｗ−１）／２ｗパーセントにセーブされるということは、十分に大きなｗについて約５０パーセントの節約を意味する。
【０２３６】
本発明においては、公開鍵が、ジェネレータのべき数の形式に基づいて同一のジェネレータで生成されるので、べき数法の代わりに乗法を含む一連の公開鍵を生成するためにジェネレータｇのべき数を再使用することができる。このようにして、記憶容量を節約し、計算を加速できる。
【０２３７】
また、復号化装置において、ジェネレータのべき数のただ１つのテーブルを維持する必要があるだけなので、新しい公開鍵の計算をオフラインで行うことが可能である。
【０２３８】
例えば、実施例において、暗号文メッセージＣ＝（Ｃ１，  Ｃ２）が復号化装置で受信される場合、新しい公開鍵を生成するためにＣ１を検索して用いることができる。
【０２３９】
上述したＣ１＝ｙ１ｋ＝ｇｒｋの場合、積“ｒｋ”が単なる他の整数であるので、ｇｒｋを新しい公開鍵を生成するために保存することができる。
【０２４０】
新しい公開鍵を生成するためにｇｒｋを保存することができるが、暗号化されたメッセージを送る時、もしも符号化装置がｋを明らかにしなかったならば、ｒｋの値は復号化装置には依然知られていない可能性がある点に留意すべきである。
【０２４１】
単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、公開鍵生成装置４９は、（ｙ１×ｙ１，ｙ２×ｙ２）の式から新しい秘匿化された公開鍵を生成してもよい。ここで、×はグループ乗算である。
【０２４２】
一般に、ｙ１１＝ｇｒ１，  ｙ１２＝ｇｒ２，  ・・・，  ｙ１ｊ＝ｇｒｊ
及び ｙ２１＝ｙ１１ｘ，  ｙ２２＝ｙ１２ｘ，  ・・・，  ｙ２ｊ＝ｙ１ｊｘである、複数の格納されたｇのべき数に基づいていくつかの秘匿化された公開鍵（ｙ１１，  ｙ２１），（ｙ１２，  ｙ２２），・・・，（ｙ１ｊ，  ｙ２ｊ），  ｊ≧２が提供される場合、新しい公開鍵が（ｙ１（ｊ＋１）＝ｙ１１ｙ１２・・・ｙ１ｊ，  ｙ２（ｊ＋１）＝ｙ２１ｙ２２・・・ｙ２ｊ）として計算される。
【０２４３】
ここで、上記 ｙ１１ｙ１２・・・ｙ１ｊは、ｙ１１，  ｙ１２，  ・・・、  ｙ１ｊの積であり、ｙ２１ｙ２２・・・ｙ２ｊは、ｙ２１，  ｙ２２，  ・・・、  ｙ２ｊの積である。
【０２４４】
明らかに、新しい秘匿化された公開鍵を生成するために、べき数演算は、乗算に置き換えられ、計算効率が向上する。
【０２４５】
乗法演算をオンラインで実行することができるので、このように生成された新しい公開鍵をあらかじめ計算する必要がなく、このことは直ちに記憶容量の節約を意味する。
【０２４６】
上記の最適化技術は、新しい秘匿化された公開鍵を生成するために一緒に用いてもよい。
【０２４７】
例えば、受信した上で、一連の暗号文（Ｃ１１，  Ｃ２１），（Ｃ１２，  Ｃ２２），・・・，（Ｃ１ｊ，  Ｃ２ｊ）（ただし、ｊ≧２）の復号化に成功した後、公開鍵生成装置４９は、（ｙ１＝（Ｃ１１
Ｃ１２・・・Ｃ１ｊ）， ｙ２＝（ｒｂ１ｒｂ２・・・ｒｂｊ））の式によって新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒｂ１，  ｒｂ２，  ・・・，  ｒｂｊのみならず受信した暗号文も用いることができる。
【０２４８】
ここで、Ｃ１１Ｃ１２・・・Ｃ１ｊはＣ１１，  Ｃ１２，  ・・・，  Ｃ１ｊの積、ｒｂ１ｒｂ２・・・ｒｂｊは、ｒｂ１，  ｒｂ２，・・・，  ｒｂｊの積である。
【０２４９】
また、ｙ２の計算で、一連の公開鍵は、（ｙ２ｗ１，  ｙ２ｗ２）として計算される。ここで，ｗ１＝ｘｗ，  ｗ２＝ｘ（ｗ＋１）
，  ｗ≧０である。
また、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０２５０】
さらに、暗号文メッセージＣから検索されたＣ１に基づいて、復号化装置はさらに多くの新しい公開鍵を生成することが可能である。
【０２５１】
この目的のために、Ｃ１ｘ及びＣ１−ｘを計算して保存され、次いで、２つの一連の公開鍵が生成される。
【０２５２】
一般に、多くの暗号化されたメッセージＣＣ１＝（Ｃ１１、Ｃ１２），  ＣＣ２＝（Ｃ２１、Ｃ２２），  ・・・，  ＣＣｊ＝（Ｃｊ１、Ｃｊ２）が受信された時、Ｃ１ｘの場合、一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｕ１＝ｘｕ，  ｕ２＝ｘ（ｕ＋１），  ｕ≧０）の積である。また、Ｃ１−ｘの場合、別の一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｖ１＝−ｘｖ，  ｖ２＝−ｘ（ｖ＋１），  ｖ≧０）の積である。
【０２５３】
さらに、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０２５４】
（秘匿化された秘密鍵）
【０２５５】
ある場合には、ユーザが、いくつかの秘密鍵を選択して、いくつかの一連の秘匿化された公開鍵を、それぞれ異なる秘密鍵用に生成したいと思うかもしれない。
【０２５６】
ユーザは、いくつかの秘密鍵ｘｉを選択し、各ｘｉ毎に（ｇａ、ｇａｘｉ）として秘匿化された公開鍵を生成することができる。
【０２５７】
１秘密鍵に対して１公開鍵のモデルが本発明で置き換えられることから、秘匿化された公開鍵の秘匿性はそれぞれの上記秘密鍵の秘匿性を意味する。
【０２５８】
この意味で、さらに本発明は、秘匿化された秘密鍵を実現する。
【０２５９】
（セキュリティ通信セッションの例）
【０２６０】
本発明によるセキュリティ通信システムの例を説明する。ここで、秘匿化された公開鍵の手法は巡回グループＺｐ＊に基づく。
【０２６１】
簡単のため、Ｐ＝１１であり、よって、Ｚ１１＊＝｛１，  ２，  ３，  ４，  ５，  ６，  ７，  ８，  ９，  １０｝であるとする。
【０２６２】
Ｚ１１＊の位数は１０である。
【０２６３】
部分グループはＺ１１＊として選択される。ジェネレータ（生成子）は２である。
【０２６４】
符号解読側では、秘密鍵はｘ＝３として選択される。
【０２６５】
整数ａ＝４が指標として選択されている場合、公開鍵生成装置４９は、秘匿化された公開鍵（２４＝５，  ５３＝４）
ｍｏｄ １１を生成する。
【０２６６】
他の整数ａ＝７について、公開鍵生成装置４９は、他の秘匿化された公開鍵（２７＝７，  ７３＝２）
ｍｏｄ １１を生成する。
【０２６７】
ここで、これら２つの秘匿化された公開鍵が２つの受信機に送信されることを想定する。
【０２６８】
公開鍵（５，  ４）を受け取る受信機Ａは、暗号化すべきプレーンテキスト８を有している。もう一つの受信機である受信機Ｂは、暗号化すべきプレーンテキスト１０を有している。
【０２６９】
受信機Ａは、指定子として整数６を選択し、（５６の＝５，  ８×４６＝１０）
ｍｏｄ １１としてプレーンテキスト８の暗号文を計算する。
【０２７０】
同様に、受信機Ｂは、整数３を選択し、（７３＝２，  １０×２３＝３） ｍｏｄ １１としてプレーンテキスト１０の暗号文を計算する。
【０２７１】
暗号文（５，  １０）及び（２，  ３）は、解読側にそれぞれ渡される。
【０２７２】
暗号文（５，  １０）のプレーンテキストは、５−３ ＝ ５１０×５−３ ＝
５７ ＝ ３ ｍｏｄ １１及び１０×３ ＝ ８ ｍｏｄ １１によって計算される。
【０２７３】
暗号文（４，  ７）のプレーンテキストは、２３＝８ ｍｏｄ １１及び３／８＝３×８−１＝３×８１０×８−１＝３×８９＝１０
ｍｏｄ １１ によって計算される。
【０２７４】
このように、プレーンテキスト８及びプレーンテキスト１０は、解読側で的確に復元される。
【０２７５】
さらに、新しい秘匿化された公開鍵を生成するために最適化技術を利用することが可能である。
【０２７６】
暗号文（２，  ３）及び中間の解読出力８に基づいて、秘匿化された公開鍵を（２，  ８）として生成することも可能である。
【０２７７】
暗号文（５，  １０）及び中間の解読出力３に基づいて、秘匿化された公開鍵を（５−１＝９，  ３）
ｍｏｄ １１として生成することも可能である。
【０２７８】
秘匿化された公開鍵（２，  ８）のうちの１つに基づいて、一連の公開鍵を（２，  ８） ，  （８，  ８３＝６），  （６，  ６３＝７）
ｍｏｄ １１として生成することも可能である。
【０２７９】
秘匿化された公開鍵（９，  ３）のうちの１つに基づいて、新たな公開鍵を（２，  ８），
（８，  ８３＝６）， （６，  ６３＝７）ｍｏｄ １１．として生成することも可能である。
【０２８０】
（２，  ８）， （７，  ２）のような秘匿化された公開鍵のうちのいくつかに基づいて、新たな公開鍵を（２
× ７＝３， ８ × ２＝５） ｍｏｄ １１として生成することもできる。
【０２８１】
上述した説明から分かるように、各送信機からのパラメータが、新たな公開鍵を生成するために用いられる。
【０２８２】
したがって、結果として得られる公開鍵のプライバシーレベルが向上する。
【０２８３】
一つの秘密鍵x及び同一のジェネレータgに基づいて、全ての公開鍵が生成される点に留意すべきである。
【０２８４】
本発明は、コンピュータ読取り可能な記憶媒体に格納されたコンピュータ実行可能な命令によって実現することができる。また、ハードワイヤド論理回路、あるいはハードウェアとソフトウェアの組み合わせによって実現することができる。
【０２８５】
さらに、本明細書に示される装置は、本発明で示された手順を実行するための必要なデータ及びコンピュータ実行可能な命令を格納するために、RAM、DRAM及びROM等のメモリを備えていてもよい。
【０２８６】
また、上記のようなメモリを、端末装置の符号化装置と復号化装置の少なくとも一方に組み込むことが可能である。
【０２８７】
メモリのそのような使用は、当該技術分野においてよく知られているので、ここでは説明せず、添付図面中にも示していない。
【０２８８】
本発明は、その思想あるいは本質的特徴から外れない範囲で、他の特定の態様において具体化されることも可能である。
【０２８９】
また、本実施例は、全ての点において具体的な例として考慮され、限定的に考慮されるものではない。また、本発明の範囲は、実施例の記載ではなく請求の範囲によって示される。さらにクレームと同等の意味及び範囲内に含まれる全ての変形例は本発明に包含される。
【図面の簡単な説明】
【０２９０】
本発明の前述の目的及び他の目的、本発明の本質及び本発明の各特徴は、以下に述べる説明を添付図面と共に読まれることにより十分に理解されるだろう。
【図１】図１は、本発明によって秘匿化する公開鍵暗号方式を用いる２つの端末装置(端末装置のうちの一方が、他方の端末装置との新しい通信セッション用の種々の公開鍵を公開する)を備えた好適なシステムを示す図である。
【図２】図２は、本発明によって秘匿化する公開鍵暗号方式を用いるいくつかの端末装置(ある端末装置が、異なる通信用に異なる公開鍵を有する他の端末装置と通信する)を備えた好適なシステムの例を示す図である。
【図３】図３は、図１と図２で例をあげて説明した通信システムに参加する送信機と受信機の間の好適な通信セッション例を示す図である。
【図４】図４は、本発明による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図である。
【図５】図５は、本発明による図４に示す公開鍵生成装置の好適な機能ブロック図である。
【図６】図６は、秘匿化された公開鍵を生成する本発明の生成フローを示すフローチャートである。
【図７】図７は、メッセージの暗号化及び復号化の好適な手続き例を示す図である。
【符号の説明】
【０２９１】
Ａ、ａ，ｂ，・・・，ｚ１０：端末装置
Ｅ，Ｅａ，Ｅｂ，・・・，Ｅｚ：公開鍵
ｘ，ｘａ，ｘｂ，ｘｃ，・・・，ｘｚ：秘密鍵
４１：送信機
４２：受信機
４３，４４：送信装置
４５，４６：受信装置
４７：復号化装置
４８：暗号化装置
４９：公開鍵生成装置
５１：グループ選択手段
５２：部分グループ選択手段
５３：ジェネレータ選択手段
５４：記憶部
５５：制御装置
５６：整数選択手段
５７：グループ指数演算子
【図１】
2006141032.tif 000011
【図２】
2006141032.tif 000012
【図３】
2006141032.tif 000013
【図４】
2006141032.tif 000014
【図５】
2006141032.tif 000015
【図６】
2006141032.tif 000016
【図７】
2006141032.tif 000017
【外国語明細書】
2006141032000001.pdf