(57)【要約】【課題】  秘匿性が高くユーザに負担がかからない暗号化データ保管サーバシステムを提供する。【解決手段】  ユーザ４１は、再暗号化のための新たな鍵と古い鍵との差分のみを代理サーバ２０に送る。代理サーバ２０は、保管サーバ１０に保管された暗号化データを復号化することなく、送られた鍵の差分のみで直接再暗号化する。保管サーバ１０は、代理サーバ２０により再暗号化された暗号化データを保管する。【選択図】      図３
2005252384.tif 000002
【特許請求の範囲】
【請求項１】
暗号化データを保管する暗号化データ保管サーバと、
再暗号化の鍵と前記暗号化データの鍵との関係により前記暗号化データを直接再暗号化する少なくとも１つの代理サーバを備える暗号化データ保管システム。
【請求項２】
前記関係は差分である請求項１に記載の暗号化データ保管システム。
【請求項３】
前記代理サーバは複数配置され、前記再暗号化の鍵は前記複数の代理サーバに分散して格納される請求項１又は２に記載の暗号化データ保管システム。
【請求項４】
前記複数の代理サーバのうち所定数以上の代理サーバが協働しないと、鍵が復元できないように構成された請求項３に記載の暗号化データ保管システム。
【請求項５】
暗号系としてエルガマル暗号を用いる請求項１〜４のいずれか１項に記載の暗号化データ保管システム。
【請求項６】
暗号系としてクレイマー・シュープ暗号を用いる請求項１〜４のいずれか１項に記載の暗号化データ保管システム。
【請求項７】
暗号化データ保管サーバと再暗号化を行なう代理サーバとを備えた暗号化データ保管サーバシステムにおける暗号化データ保管方法であって、
ユーザが、鍵を作成してデータを暗号化し、該暗号化データを暗号化データ保管サーバへ保管するステップと、
前記ユーザが、再暗号化のための鍵を作成して、先の暗号化のための鍵との関係を代理サーバに送るステップと、
前記代理サーバが、前記暗号化データを前記関係によって直接再暗号化するステップと、
前記暗号化データ保管サーバが前記再暗号化データを保管するステップと
を有する暗号化データ保管方法。
【請求項８】
前記関係は、差分である請求項７に記載の暗号化データ保管方法。
【請求項９】
先の鍵で暗号化されている暗号化データを、新たな鍵により暗号化する再暗号方法であって、
新たな鍵を生成するステップと、
前記新たな鍵と前記先の鍵との関係を得るステップと、
前記関係により前記暗号化データを直接暗号化するステップと、
からなる再暗号化方法。
【請求項１０】
前記関係は、差分である請求項９に記載の再暗号化方法。
【請求項１１】
暗号化データ保管サーバと再暗号化するための少なくとも１つの代理サーバとを備える暗号化データ保管システムにおいて、代理サーバによる再暗号化のために使用される請求項９又は１０に記載の再暗号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを暗号化して保管するサーバシステムに関する。
【背景技術】
【０００２】
企業や個人が所有する電子データには、第３者に対して秘匿しなければならない重要な電子データが存在するが、このようなデータは、ネットワークを介しての漏洩、あるいはハッカーの侵入による破壊・盗難のおそれが常にあり、企業や個人で保管しておくには問題がある。したがって、電子データを安全確実に保管する保管サービスが求められている。
【０００３】
このようなデータ保管サービスでは、データを保管する保管サーバに対する不正アクセスを防止する機能を高くすることが求められるが、保管データについて暗号化ができるようにしておくことも必要である。データを暗号化して保管しておくと、第三者に対してはもちろん保管サーバに対しても内容が秘匿でき、よりセキュリティの高いサービスを提供することができる。データを暗号化する場合、ユーザ本人のみが、暗号化及び復号化のための鍵をもち、保管すべきデータを暗号化して保管サーバに送信するのが最も安全である。すなわち、暗号化及び復号化のための鍵はユーザがもっているので、秘匿性はきわめて高い。また、ユーザが必要なときには、保管された暗号化データをユーザ側に戻してユーザが復号化すれば利用できる。しかしながら、ユーザがもっている鍵が盗まれたり漏洩したりすると、データの内容がすべてわかってしまうという危険性がある。ネットワーク上では、鍵の盗難等は発見されにくく、漏洩した鍵で、現在のデータはもちろん過去に保管されたデータ、今後保管されるデータなどすべてが漏洩するおそれがある。
【０００４】
暗号化及び復号化鍵の漏洩を防止するための対策として、通信の分野では、（１）鍵を分散あるいは分割して管理する方法、（２）鍵の頻繁な更新を行なう方法が取られている。しかしながら、データ保管サービス用には、（１）の方法は向いていない。なぜならデータの所有者（ユーザ）が、保管サービスを利用する場合は、安全な記憶装置を少ししか持っていないからであり、鍵の分散管理のために自分で複数の記憶装置をもちこれを管理するのは負担が大きい。
【０００５】
また、通信は、空間的に離れた場所にいる送信者と受信者間でデータがやり取りされるもので、通常送信者が暗号化し、受信者が復号化する。一般に暗号化鍵と復号鍵とは対になっており、（２）の方法を採用して鍵を更新するには、受信者が暗号化鍵を作って送信者に送る必要がある。頻繁に鍵を変更するためには、受信者から送信者に頻繁に暗号化鍵を送信する必要があるが、これは面倒であるので、通信では（２）の方法を採用しても、鍵を無作為に変更するようなことはせず、例えば送信が必要な暗号化鍵は変えないで復号化鍵だけ変える方式をとっている。
【０００６】
しかしながら、復号化鍵は暗号化鍵と対になるもので、変更された復号鍵も暗号化鍵と一定の関係を満たしている。したがって、暗号化鍵を変更しないで復号化鍵のみを変更する方式では、現在の復号化鍵から将来の復号化鍵を解読される可能性を否定できない。例えば、通信用のフォワードセキュリティ（ｆｏｒｗａｒｄ  ｓｅｃｕｒｉｔｙ）方式では、復号化鍵が盗まれても過去のものは復号できないが、一旦盗まれると、復号化鍵を変更したとしても暗号化鍵が共通であるので、これより以後のものは解読される可能性が残る。したがって、（２）の方法でも、通信用に開発されたモデルは、保管用としてはセキュリティの点で問題が残る。
【０００７】
このように、通信用の方式をデータ保管用に直接適用するには安全性の面で問題がある。しかしながら、データ保管用の暗号化・復号化は、同一ユーザが行なうことができるので、暗号化及び復号化の鍵をそっくり無作為に（以前のものとは独立に）取り替えることができる。こうすれば、漏洩した鍵以外の鍵で暗号化してあるデータは、安全である。ネットワーク上では、鍵が盗まれたかどうかは分りにくいものであるから、増加してゆくデータが次々と漏洩してゆくのは大きな問題であるが、鍵を無作為に取り替えることができれば、鍵が漏洩しても今後蓄積されるデータは確実に守ることができる。したがって、データ保管用の場合は、鍵を定期的に更新する方法を採用して、非常に安全度の高いシステムが構築できる。なお、当然のことながら、過去のデータであって、変更した鍵で再暗号化しなかったものは、変更した鍵を盗まれても安全である。
【０００８】
電子データ保管サービスでは、ユーザ本人が、暗号化及び復号化のための鍵を作成保持し、かつ鍵を頻繁に変更すると、秘匿性のきわめて高い保管サービスが可能である。しかしながら、鍵を変更して再暗号化する場合、保管してあるデータを保管サーバから引き出して一旦復号化して、それを新しい鍵で暗号化し直して、保管サーバに送信するという作業が必要となる。安全のために１ヶ月に一度鍵を変更するとすれば、１ヶ月に１度保管サーバから引き出して復号して新たに暗号化することは、ユーザにとって負担は大きく、また保管データが膨大であれば、ハードウエア資源の乏しいユーザにとっては現実的ではない。
【０００９】
ユーザの負担を軽減させるために、新たに作成した鍵をユーザがデータ保管サービス側に渡して、保管サービス側で再暗号化を行なうことも考えられるが、新たに暗号化する場合は、一旦暗号化されていない状態に戻す必要があるから、保管サービス側に内容が見える状態を経由することになる。これではデータを暗号化して保管している意味が薄れてしまう。
【００１０】
なお、従来の暗号化データ保管システムとして、ユーザで暗号化したデータ及び鍵を分散保管して安全性を確保することが提案されている（特許文献１参照）が、前述のようなユーザによる再暗号化負担を考慮したものではない。
【００１１】
【特許文献１】特開２００３−３４８０６５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、新たな再暗号化方法により秘匿性を高めた暗号化データ保管サーバシステムと暗号化データ保管方法を提供すること、さらに再暗号化方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の暗号化データ保管システムは、前記目的を達成するために、暗号化データを保管する暗号化データ保管サーバと、再暗号化のための鍵と現在の暗号化鍵との関係により前記暗号化データを直接再暗号化する少なくとも１つの代理サーバを備える。
【００１４】
再暗号化するための前記関係は差分とすることができる。
さらに、代理サーバは複数配置され、前記再暗号化の鍵は前記複数の代理サーバに分散して格納してもよく、複数の代理サーバのうち所定数以上の代理サーバが協働しないと、鍵が復元できないようにしてもよい。
【００１５】
暗号系としては、エルガマル暗号を用いることができ、またクレイマー・シュープ暗号を用いることができる。
【００１６】
本発明の第２の態様では、暗号化データ保管サーバと再暗号化を行なう代理サーバとを備えた暗号化データ保管サーバシステムにおける暗号化データ保管方法が提供される。この暗号化データ保管方法は、ユーザが、鍵を作成してデータを暗号化するステップと、前記ユーザが、前記暗号化データを暗号化データ保管サーバへ保管するステップと、前記ユーザが、再暗号化のための鍵を作成して、先の暗号化のための鍵との関係を代理サーバに送るステップと、前記暗号化データ保管サーバが、前記暗号化データを前記代理サーバに送るステップと、前記代理サーバが、前記暗号化データを前記関係によって再暗号化し、該再暗号化データを前記保管サーバ送るステップと、を有する。
【００１７】
さらに本発明の第３の態様では、先の鍵で暗号化されている暗号化データを、新たな鍵により暗号化する再暗号方法が提供され、この再暗号化方法は、新たな鍵を生成するステップと、前記新たな鍵と前記先の鍵との関係を得るステップと、前記関係により前記暗号化データを暗号化するステップとからなる。
【発明の効果】
【００１８】
このように、本発明によるデータ保管サーバシステムは、古い鍵と新しい鍵との関係を用いるだけで再暗号化する代理サーバを備えたことで、ユーザの再暗号化負担を軽減する。また暗号化データから復号化することなく、直接に再暗号化が可能であるから、秘匿性もきわめて高い。代理サーバを複数設けて鍵を分散配置すれば、さらに安全なシステムとすることができる。また、本発明の一態様である再暗号化方法においては、復号化しなくても無作為に選択された新たな鍵で再暗号化でき、再暗号化過程における秘匿性が高く、効率的に再暗号化を達成できる。
【発明を実施するための最良の形態】
【００１９】
本発明の実施の形態を説明する前に、本発明の作用効果を明確に示すために、データの所有者すなわちデータ保管サービスシステムのユーザ自らが鍵を変更し暗号化及び復号化を行なう参考例を、図１及び２を参照して説明する。なお、一般に暗号化及び復号化は、有限体上でのｍｏｄ計算で実行されるが、本明細書では、煩雑になるのでｍｏｄを省略してある。ｍｏｄを省略しても、当業者であれば誤解はないであろう。
【００２０】
ここでは、ユーザが十分な計算資源を持っていると仮定し、暗号化をｃ＝Ｅ（ｍ）、復号化をｍ＝Ｄ（ｃ）とする。ここでｍは、暗号化される対象の平文データを示し、ｃは、暗号化された結果である暗号化データを示す。暗号化は暗号化関数Ｅにより、復号化は復号化関数Ｄにより行なわれる。
【００２１】
データ保管サーバに暗号化データを保管する場合、ユーザはまずデータを暗号化する必要がある。図１は、最初の暗号化を説明するための図で、ユーザのもつデータの１単位（例えばファイル）をｍｉとして、６個のデータｍ１，ｍ２…ｍ６が、鍵ｋｅｙ１を用いて暗号化され、暗号化データＣ＝（ｃ１，ｃ２，…，ｃ６）が生成されることを示す。
【００２２】
これを一般的に式で表すと、ユーザのデータＭを、ｎ個のデータｍ１，ｍ２・・・ｍｎからなるデータとすると、次の式（１）のように表すことができる。
【００２３】
【数１】
2005252384.tif 000003
【００２４】
今、ユーザが適当な鍵ｋｅｙ１を選んでデータを暗号化する場合、データｍｉ（ｉ＝１，・・・，ｎ）に対して暗号化されたデータをｃｉとすると、暗号化は暗号化関数をＥｋｅｙ１として次の式（２）で表され、その結果データＭに対して式（３）に示す暗号化データＣが得られる。
【００２５】
【数２】
2005252384.tif 000004
【００２６】
次に、暗号化データＣをデータ保管サーバに送信して保管する。鍵ｋｅｙ１は、データと比較して小さいので、ユーザの記憶装置に保管しておく。このようにして、鍵ｋｅｙ１が最初の期間の鍵となる。
【００２７】
その後ユーザは定期的あるいは不定期に、データの安全のために鍵を換えて再暗号化を行なう。図２は、ｔ番目あるいは第ｔ期間（ｔ＞１）への移行のための再暗号化を示す説明図である。第ｔ期間への移行に際しては、第（ｔ−１）期間の鍵ｋｅｙｔ−１により暗号化したデータを、ｋｅｙｔで再暗号化する。
【００２８】
ここでは、ユーザは、今回使用する鍵ｋｅｙｔを、ランダムに言い換えれば前回の鍵ｋｅｙｔ−１とは独立に選択する。必要があれば新しい暗号データの列Ｃ’を初期化した後、保管サーバと通信を行なって自分のデータを戻し、前回の鍵ｋｅｙｔ−１で暗号化データｃ１〜ｃ６の復号化Ｄを行なう。
【００２９】
ここで、あるｍｉが不要になったデータであれば、復号化しないで破棄する。通常再暗号化すると以前の鍵は削除するので、復号化しないということは破棄することになる。図では、暗号化データｃ４，ｃ６は不要になったものとして示した。復号化の結果得られた元データｍ１〜ｍ３，ｍ５を今回のｋｅｙｔを用いて暗号化Ｅを行ない、新たな暗号化データｃ’１〜ｃ’３，ｃ’５を得る。
【００３０】
前回の鍵ｋｅｙｔ−１は消去する。また、新たに追加して保管するデータｍ’７，ｍ’８があれば、これについても今回のｋｅｙｔで暗号化して、ｃ’７，ｃ’８として、データ保管サーバに送る。このようにして、データ保管サーバにあるＣをＣ’に置き換える。
【００３１】
第ｔ期間（ｔ＞１）への移行のための再暗号化を一般的に式で示すと以下のようになる。
前回の鍵ｋｅｙｔ−１で暗号化データｃ１〜ｃ６の復号化を行なう過程は、
【００３２】
【数３】
2005252384.tif 000005
【００３３】
で示される。ここで、不要になったデータは復号化しないで破棄する。復号化の結果得られた元データｍｉを今回のｋｅｙｔを用いて暗号化を行ない、次の式に示すように新たな暗号化データｃ’ｉを得る。
【００３４】
【数４】
2005252384.tif 000006
【００３５】
次いで、前回の鍵ｋｅｙｔ−１は完全に消去する。また、新たに追加するデータｍ’ｊ（ｊ＝ｎ＋１，…）があれば、ｋｅｙｔで暗号化して、データ保管サーバにあるＣをＣ’に置き換える。これを式で表現すると、以下のようになる。
【００３６】
【数５】
2005252384.tif 000007
【００３７】
このようにすると、ｋｅｙｔが盗まれた場合であっても、ｋｅｙｔで暗号化された平文は復号されるが、それ以外のものについては全く安全であり、データ保管用として非常に安全性の高いシステムとなる。しかしながら、ユーザは、毎回（例えば１月ごとに）すべてのデータについて復号し暗号化しなければならず、手間がかかり多くの計算資源も必要である。
【００３８】
本発明は、先に述べたように、このようなユーザの負担を減らすことができるものである。
【００３９】
以下、図面を参照して、本発明の実施の形態を説明する。まず、図３，４により本暗号化データシステムの概略を説明する。
【００４０】
図３に、本発明の一実施形態のデータ保管サーバシステムの概念図を示す。データ保管サーバシステムは、暗号化データ保管サーバ１０とユーザに代わって再復号化を行なう代理サーバ２０とを備え、複数のユーザ４１〜４３等が、インターネット等のネットワーク３０を介して保管サーバ１０と代理サーバ２０に接続している。
【００４１】
今、ユーザ４１が初めて暗号化データ保管サーバを利用するとする。まず、保管サーバ１０では、ユーザの暗号化データを保管するための空きリストを作成しておく。ユーザ４１は、所定の暗号系を用いて自分の鍵ｋｅｙ１（暗号化鍵と復号化鍵との対）を作成し、保管すべきデータＭを暗号化して、暗号化データＣを作成する。鍵ｋｅｙ１はユーザが秘密に保管しておく。これは、図１及び式（１）〜（３）により説明した参考例と同様であるので、説明を省略する。このように、データＭを暗号化して暗号化データＣを作成する。そして、暗号化データＣを保管サーバ１０に預ける。
【００４２】
その後、第ｔ期間への移行のために再暗号化する場合を、図４を参照して説明する。第（ｔ−１）期間の終わりには、暗号化データ保管サーバ１０には、暗号化データＣが保管されているとする。再暗号化するユーザ４１は、保管サーバ１０に対して、再暗号化することを通知するとともに、保管データに不要のものがあればそれを通知する。通知を受けた保管サーバでは、不要データを破棄し、新たに暗号化データＤとする。なお、必要がなくなったデータは再暗号化しないだけで、鍵が消去されるので、自動的に破棄されたことになる。暗号化データＣから不要データを破棄したデータＤは、再暗号化のために代理サーバ２０に送られる。
【００４３】
本実施形態では、特定の暗号系を使用しており、この暗号系では先の暗号化で使用した鍵と新たに暗号化する鍵の差分を使用するのみで、先の暗号化データから直接にすなわち復号化の過程を経ることなく再暗号化が可能である。言い換えれば、本実施形態では、鍵の差分のみで再暗号化できる暗号系を使用する。この暗号系については、後に詳しく説明する。
【００４４】
したがって、ユーザは、新たに従前のものとは全く独立に暗号化鍵ｋｅｙｔを作成し、直前の暗号化鍵ｋｅｙｔ−１との差分Δｋ
【００４５】
【数６】
2005252384.tif 000008
【００４６】
を代理サーバ２０に送る。代理サーバ２０は、データＤを差分Δｋのみにより再暗号化して、暗号化データＤ’を得る。すなわち、
【００４７】
【数７】
2005252384.tif 000009
【００４８】
となる。
ここで、本実施形態による再暗号化は、鍵の差分のみを用いて行なわれ、また暗号化データを平文データに戻すことなく暗号化データから新たな暗号化データに変換されるので、鍵が漏洩することもなく、データの内容が分るということもない。暗号化する代理サーバに対しても、鍵及びデータ内容は秘匿される。代理サーバ２０は、再暗号化した暗号化データＤ’を保管サーバ１０に送り、保管サーバはデータＣに代えてデータＤ’を保管する。
【００４９】
ユーザ４１が、新たなデータｍ’ｊを追加して保管したい場合は、この期間の鍵ｋｅｙｔで暗号化する。この処理は、先の参考例と同様である。次いで、この暗号化データｃ’ｊを保管サーバ１０に送る。保管サーバ１０では、これをＤ’に追加して、以下のような暗号化データＣ’として保管する。
【００５０】
【数８】
2005252384.tif 000010
【００５１】
以上のように、本実施形態では、再暗号化を、暗号化データを用いて、かつ鍵の差分情報のみで実行でき、データ内容が漏洩することも鍵が盗まれることもない、きわめて秘匿性の高い再暗号化が可能で、たとえ鍵が漏洩したとしても、漏洩した鍵以外の鍵で暗号化してあるデータは、過去のものも未来のものも安全である。
【００５２】
次に、本実施形態で使用する暗号系を説明する。
本実施形態で使用する暗号系は、エルガマル（ＥｌＧａｍａｌ）暗号である。図４に示した代理サーバによる第ｔ期間への移行のための暗号化のための再暗号化の過程を例として説明する。暗号化鍵をｐｋ、復号化鍵をｓｋとして、添え字により期間を表す。エルガマル暗号系では、第（ｔ−１）期間の復号化鍵ｓｋｔ−１と暗号化鍵ｐｋｔ−１とについて、次の式（４）が成立している。エルガマル暗号の公開のパラメータは、素数ｐ、素数位数ｑをもつ元ｇである。
【００５３】
【数９】
2005252384.tif 000011
【００５４】
ここで、復号化鍵ｓｋｔ−１は、適当な範囲から乱数ｘｔ−１を選択したもので、暗号化鍵ｐｋｔ−１である数ｙｔ−１は、元ｇのｘｔ−１乗で得られる。エルガマル暗号系自体はよく知られているので詳しい説明は省略する。また、先に述べたようにｍｏｄ記号は省略されている。第ｔ期間では、新しい鍵と差分及び比は、次の式（５）〜（７）で表される。
【００５５】
【数１０】
2005252384.tif 000012
【００５６】
式（５）のｘｔは、式（４）のｘｔ−１とは全く無関係に言い換えれば独立に選ばれた乱数である。注目すべきは、復号化鍵の前回と今回との差分Δｋ（式６）によって、前回と今回の暗号化鍵の比ｙｔ／ｙｔ−１がｇΔｋ（式７）で表せる点である。
【００５７】
次に、代理サーバが、暗号化データＤを差分Δｋで再暗号化して暗号化データＤ’を得る過程を説明する。
【００５８】
【数１１】
2005252384.tif 000013
【００５９】
暗号化データＤを構成している１つの暗号文ｃｉは、式（８）のように表すことができる。ここで、ｍｉは平文データで、元ｇは適当に選択された定数であり、ｒは暗号化に使用した乱数であり、ｙｔ−１は第（ｔ−１）期間の暗号化鍵である。すなわち、第（ｔ−１）期間で、平文データｍｉが暗号化され、その結果暗号化データｃｉは、ｇｒと、ｍｉｙｔ−１ｒとを並べたもの（ｇｒ，ｍｉｙｔ−１ｒ）で表されている。
【００６０】
これを新しい鍵による暗号文とするには、ｃｉからｃ’ｉを生成すればよい。ｃ’ｉを生成するには、式（９）の下線部に示したように、ｃｉのｍｉｙｔ−１ｒに、ｃｉの（ｇｒ）Δｋを乗算する。（ｇｒ）Δｋは、（ｇΔｋ）ｒであり、ｇΔｋは、式（４）によりｙｔ／ｙｔ−１であるから、式（６）が導かれる。これで分るように、ｃ’ｉを導く際に、導入されるのはΔｋのみで、復号化の過程を経ることなく、前回の暗号化データｃｉから再暗号化データｃ’ｉを生成することができる。
【００６１】
以上のように、エルガマル暗号を用いれば、鍵の差分を入手するのみで、暗号化データを復号化することなく、先の暗号化に対して独立した新たな暗号化を行なうことができる。ここで、式（８）と式（９）を比較すると分るように、暗号化の鍵は独立な値に更新されるが、乱数ｒは再利用されている。一般には乱数を再利用すると安全性が弱まるが、エルガマル暗号では、新たな鍵での暗号化に乱数を再利用しても安全性が弱まらないことが証明されている。したがって、本例の鍵更新の安全性はエルガマル信号と同じレベルであるといえる。
【００６２】
本実施形態では、エルガマル暗号を用いたが、エルガマル暗号に限定されるものではない。例えばクレイマー・シュープ（Ｃｒａｍｅｒ−Ｓｈｏｕｐ）暗号等鍵の差分のみで再暗号化できる暗号系であればどのような暗号系も使用できる。クレイマー・シュープ暗号を用いると、その場合の保管システムの安全性はクレイマー・シュープ暗号と同じものとなる。
【００６３】
また、本実施形態では、先の鍵と新たな鍵との差分のみにより再暗号化を行なったが、先の鍵と新たな鍵との関係を与えれば先の暗号化データから新たな暗号化データが作成できる暗号系を使用して、その関係のみを代理サーバに渡して再暗号化を行なうことも可能である。
【００６４】
〔第２の実施形態〕
先の実施形態では、データ保管システムには１つの代理サーバが配置されるとしたが、本例では、図５に示すように、複数の代理サーバ２０−１〜２０−ｎを配置して、再暗号化に必要な鍵の差分Δｋを分散配置する。ここで、暗号化保管サーバ１０とユーザ４１〜４３がネットワークを介してデータ保管システムに接続している点では第１の実施形態と同じである。
【００６５】
分散配置する手法として、秘密分散法である多項式を利用した（Ｌ，Ｎ）しきい値法（Ｌ＜Ｎ）を用いる。（Ｌ，Ｎ）しきい値法によれば、差分ΔｋをＮ個のサーバに分散し、Ｌ（閾値）個以上の分散サーバが協力すれば、元の差分Δｋを復元できるが、（Ｌ−１）個以下のサーバより情報を得たとしても差分Δｋを復元できないようにできる。
【００６６】
（Ｌ，Ｎ）閾値法は、（Ｌ−１）次多項式はｌ個の点で決まることを利用するものである。（Ｌ−１）次多項式ｆ（ｘ）は、
【００６７】
【数１２】
2005252384.tif 000014
【００６８】
と表せ、（Ｌ−１）次多項式ｆ（ｘ）上のｌ個の点の座標が決まれば、（Ｌ−１）次多項式ｆ（ｘ）が決まる。具体的には、ラグランジェの補間多項式として知られている式によって表わされる。特に、Ｌ個の点の座標が（ｉｌ，ｆ（ｉｌ）），…，（ｉＬ，ｆ（ｉＬ））である場合、ｆ（ｘ）のｙ切片であるａ０すなわちｆ（０）は、次の式によって表わされる。
【００６９】
【数１３】
2005252384.tif 000015
【００７０】
次に、（Ｌ，Ｎ）しきい値法を利用して、ｃｉ＝（ｇｒ，ｍｉｙｔ−１ｒ）を再暗号化してｃ’ｉ＝（ｇｒ，ｍｉｙｔｒ）を求める方法を説明する。ユーザは、第一の実施形態と同じ手順によりΔｋを計算し、ｆ（０）をΔｋとするｆ（ｘ）を選び、ｆ（ｌ），…，ｆ（ｎ）を求め、ｎ個の代理サーバにそれぞれｆ（ｉ）を送る。図５では、ユーザ４１の鍵の差分Δｋ＝ｆ（０）が、ｎ個の代理サーバ２０−１〜２０−ｎにそれぞれｆ（ｌ）〜ｆ（ｎ）として分散配置されていることを示す。このうち、Ｌ個のサーバがｃｉのｇｒとｆ（ｉ）から（ｇｒ）ｆ（ｉ）を計算し、Ｌ個の計算された値すなわち（ｇｒ）ｆ（ｉｌ），…，（ｇｒ）ｆ（ｉＬ）と、定数λ１，…，λＬから
【数１４】
2005252384.tif 000016
を決定できる。（ｇｒ）Δｋが得られたならば、第一の形態と同じ手順により、ｃ’ｉ＝（ｇｒ，ｍｉｙｔｒ）を求めることができる。
【００７１】
第一の実施形態では、期間の移行をするためにユーザが代理サーバにΔｋを送り、再暗号化を終わった時点で、すなわち次の期間への移行が終了した時点で、代理サーバはΔｋを消去している。これと同様に、第二の実施形態においては、期間の移行をするためにユーザがｆ（ｉ）をそれぞれの代理サーバに送り、再暗号化を終わった時点で各サーバはｆ（ｉ）を消去する。また、ｆ（ｉ）からΔｋを復元することはせず、ｇｒから（ｇｒ）Δｋを計算するので、Ｌ個のサーバが結託しない限り、鍵の差分Δｋですら漏れないことになる。
【００７２】
第２の実施形態では、代理サーバが分散配置され、所定数のサーバの協力により再暗号化が実行されるので、よりセキュリティを高くでき、事故あるいは故障に強いシステムを構築することができる。また、（Ｌ，Ｎ）閾値法では、個々の代理サーバの不正あるいは誤りもチェックできることが公知であるので、個々のサーバをチェックする機能も容易に備えることができる。さらに、代理サーバに配置するのは、鍵の差分であるから、すべての代理サーバが結託したとしても、秘密鍵が漏れることはない。
【図面の簡単な説明】
【００７３】
【図１】一般的なデータの暗号化を示す図である。
【図２】一般的なデータの再暗号化を示す図である。
【図３】本発明の第１の実施形態である暗号化データ保管サーバシステムの概略構成を示す図である。
【図４】本発明の第１の実施形態である暗号化データ保管サーバシステムの再暗号化を示す図である。
【図５】本発明の第２の実施形態である暗号化データ保管サーバシステムの概略構成を示す図である。
【符号の説明】
【００７４】
１０…暗号化データ保管サーバ
２０、２０−１〜２０−ｎ…代理サーバ
３０…ネットワーク
４１〜４３…ユーザ
【図１】
2005252384.tif 000017
【図２】
2005252384.tif 000018
【図３】
2005252384.tif 000019
【図４】
2005252384.tif 000020
【図５】
2005252384.tif 000021