(57)【特許請求の範囲】
【請求項１】
公開鍵及び秘密鍵ｄを用いるＲＳＡ暗号系に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分最終情報が分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果又は署名結果を生成可能な（ｔ，ｎ）型の秘密分散システムであって、
前記ｎ個の各機関は、
前記公開鍵及び前記秘密鍵ｄを生成する手段と、
この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持する手段と、
ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、前記部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を前記各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散する手段と、
前記各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る手段と、
前記ユーザ装置から受けた処理対象データを前記部分最終情報ｄj,kに基づいて演算処理し、得られた部分出力を前記ユーザ装置に返信する手段とを有し、
前記ユーザ装置は、
前記ｔ個の機関を選択し、この選択したｔ個の各機関に処理対象データを送信する手段と、
前記ｔ個の各機関から受信した部分出力を合成して前記復号結果又は署名結果を得る手段と
を備えたことを特徴とする秘密分散システム。
【請求項２】
第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムであって、
前記ｎ個の各機関は、
前記ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjを前記ユーザ装置に返信する手段とを有し、
前記ユーザ装置は、
前記ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に前記復号対象データＣ２を送信する手段と、
前記ｔ個の各機関から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段と、
前記復号結果Ｃ１、前記復号対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段と
を備えたことを特徴とする秘密分散システム。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
【請求項３】
請求項２に記載の秘密分散システムにおいて、
前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、
前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、
前記最終復号結果Ｍを求める手段に代えて、
前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段と
を備えたことを特徴とする秘密分散システム。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
【請求項４】
公開鍵及び秘密鍵ｄを用いるＲＳＡ暗号系に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分最終情報が分散されたとき、その中の任意のｔ個の機関から得られた部分出力により、前記秘密鍵ｄを算出せずに復号結果又は署名結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用されるコンピュータ読み取り可能な記憶媒体であって、
前記ｎ個の各機関内のコンピュータに、
前記公開鍵及び前記秘密鍵ｄを生成する手段と、
この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持する手段と、
ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、前記部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を前記各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散する手段と、
前記各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る手段、
前記ユーザ装置から受けた処理対象データを前記部分最終情報ｄj,kに基づいて演算処理し、得られた部分出力を前記ユーザ装置に返信する手段、
を実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項５】
第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用される記憶媒体であって、
前記ｎ個の各機関内のコンピュータに、
前記ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjを前記ユーザ装置に返信する手段、を実現させるためのプログラムを記憶し、
前記ユーザ装置内のコンピュータに、
前記ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に前記復号対象データＣ２を送信する手段、
前記ｔ個の各機関から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段、
前記復号結果Ｃ１、前記復号対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段、
を実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
【請求項６】
請求項５に記載の記憶媒体において、
前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、
前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、
前記最終復号結果Ｍを求める手段に代えて、
前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段と
を実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
【請求項７】
公開鍵及び秘密鍵ｄを用いるＲＳＡ暗号系に適用され、互いに送受信可能なｎ個の機関装置及びユーザ装置を備え、ｎ個の機関装置に前記秘密鍵ｄの部分最終情報が分散されたとき、その中の任意のｔ個の機関装置から得られた部分出力により、前記秘密鍵ｄを算出せずに復号結果又は署名結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用される各々の前記機関装置であって、
前記公開鍵及び前記秘密鍵ｄを生成する手段と、
この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持する手段と、
ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、前記部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を前記各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散する手段と、
前記各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る手段と、
前記ユーザ装置から受けた処理対象データを前記部分最終情報ｄj,kに基づいて演算処理し、得られた部分出力を前記ユーザ装置に返信する手段とを備えており、
前記部分出力は、前記復号結果又は署名結果を生成するために用いられる情報であることを特徴とする機関装置。
【請求項８】
第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関における復号対象データＣ２の演算により得られた部分出力Ｚjにより、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用される前記ユーザ装置であって、
前記ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に前記復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を送信する手段と、
前記ｔ個の各機関から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段と、
前記復号結果Ｃ１、前記復号対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段と、
を備えたことを特徴とするユーザ装置。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
【請求項９】
請求項８に記載のユーザ装置において、
前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、
前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、
前記最終復号結果Ｍを求める手段に代えて、
前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段と
を備えたことを特徴とするユーザ装置。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
【請求項１０】
第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関装置及びユーザ装置を備え、
前記ユーザ装置は、
前記ｎ個の機関装置のうちのｔ個の機関装置を選択し、この選択したｔ個の各機関装置に前記復号対象データＣ２を送信する手段と、
前記ｔ個の各機関装置から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段と、
前記復号結果Ｃ１、前記復号対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段とを備えており、
ｎ個の機関装置に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関装置から得られた部分出力Ｚjにより、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用される各々の前記機関装置であって、
前記ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjを前記ユーザ装置に返信する手段を備えたことを特徴とする機関装置。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
【請求項１１】
請求項１０に記載の機関装置において、
前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、
前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、
前記ユーザ装置は、
前記最終復号結果Ｍを求める手段に代えて、
前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段と
を備えたことを特徴とする機関装置。
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、素因数分解問題に基づく暗号系の秘密分散システム、装置及び記憶媒体に係り、特に、ｎ個の機関に秘密鍵を秘密分散し、その中の任意のｔ個の機関により、秘密鍵を算出せずに分散復号及び署名を実現し得る秘密分散システム、装置及び記憶媒体に関する。
【０００２】
【従来の技術】
従来、素因数分解問題に基づく暗号系として、例えばＲＳＡ暗号系を用いた秘密分散の分野では、しきい値法と呼ばれる秘密分散方式がある。ここで、しきい値法は、秘密情報をｎ個の部分情報に分散したとき、ｎ個中のｔ個の部分情報により秘密情報を完全に復元するが、ｔ−１個の部分情報では秘密情報を全く復元できないという、しきい値ｔを境にした秘密情報の復元特性をもっている（なお、１＜ｔ＜ｎ）。
【０００３】
この種の秘密分散方式としては、ＲＳＡ暗号系に、しきい値法の概念を導入し、秘密鍵を（ｔ，ｎ）型で秘密分散させる（ｔ，ｎ）型の秘密分散方式が知られている（Ｙ．  Ｆｒａｎｋｅｌ，  Ｐ．  Ｇｅｍｍｅｌｌ，  Ｐ．  Ｄ．  ＭａｃＫｅｎｚｉｅ  ａｎｄ  Ｍ．  Ｙｕｎｇ，  Ｏｐｔｉｍａｌ−ｒｅｓｉｌｉｅｎｃｅ  ｐｒｏａｃｔｉｖｅ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ，  ３８ｔｈ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｐｐ．  ３８４−３９３，  １９９７．（以下、文献［ＦＧＭＹ９７］という）、及びＴ．  Ｏｋａｍｏｔｏ，  Ｔｈｒｅｓｈｏｌｄ  ｋｅｙ−ｒｅｃｏｖｅｒｙ  ｓｙｓｔｅｍｓ  ｆｏｒ  ＲＳＡ，  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ，  ＬＮＣＳ  １３６１，  ｐｐ．  １９１−２００，  １９９７．  （以下、文献［Ｏｋａ９７］という））。
【０００４】
中でも、文献［ＦＧＭＹ９７］は、ディーラー（分配者）の存在する環境において、秘密鍵ｄを算出せずに、任意ｔ個の機関で復号や署名の可能な方式を示している。すなわち、合成数Ｎの異なる素因数を知るディーラーが、素因数を知らなくても任意のｔ個の部分情報で復号や署名の可能な秘密鍵ｄを作成可能な方式である。
【０００５】
一方、ディーラーの存在しない環境において、しきい値法ではなく、全ての機関で鍵生成を行う（ｎ，ｎ）型の秘密分散方式が知られている（Ｄ．  Ｂｏｎｅｈ  ａｎｄ  Ｍ．  Ｆｒａｎｋｌｉｎ，  Ｅｆｆｉｃｉｅｎｔ  ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ｓｈａｒｅｄ  ＲＳＡ  ｋｅｙｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ９７，  ＬＮＣＳ  １２９４，  ｐｐ．  ４２５−４３９，  １９９７．（以下、文献［ＢＦ９７］という））。
【０００６】
文献［ＢＦ９７］の方式では、鍵生成を実行すると、秘密鍵ｄに対して（ｎ，ｎ）型の秘密分散が同時に行われる。また、保持する部分情報を用いた全ての機関からの部分出力を合成することにより、秘密鍵ｄを算出せずに暗号文を復号可能となっている。
【０００７】
詳しくは、文献［ＢＦ９７］では、以下にアルゴリズムを示すように、（２，２）型の秘密分散から（２，ｎ）型の秘密分散（ｎ≧３を効率的に構築する方式が述べられている。
【０００８】
なお、説明の簡単のため、秘密鍵ｄを知るユーザがいて、このユーザが秘密鍵ｄを（２，ｎ）型で秘密分散すると仮定する。また、機関Ｐの総数ｎに対し、部分情報の組合せを示す秘密分散多項式の個数は、ｒ＋１であるとし、ｒ＝「ｌｏｇ  ｎ」であるとする（本明細書中、「」は、その括弧内の値以上の最小の整数を示す）。
【０００９】
まず、ユーザは、（２，２）型の秘密分散をｒ＋１回実行するため、ｒ＋１個の独立多項式ｄ＝ｄ０，０  ＋ｄ０，１  ＝ｄ１，０  ＋ｄ１，１  ＝…＝ｄｒ，０  ＋ｄｒ，１  を個別に作成する。
【００１０】
次に、総数ｎの機関における個々の機関の識別番号をｚとし（ｚ∈［０，ｎ］）、識別番号ｚの２進表示をｚ（２）＝βｒ  βｒ−１  …  β０とする。ユーザは、０番目〜ｎ番目の全ての機関Ｐ０〜Ｐｎ  を対象とし、順次、ｚ番目の機関Ｐｚに、ｒ＋１個の部分情報：｛ｄｒ，βｒ，ｄｒ−１，βｒ−１，…，ｄ０，β０  ｝を送る。これにより、全ての機関Ｐ０〜Ｐｎ  には、識別番号ｚの２進表示に対応する部分情報の集合が配送される。
【００１１】
配送完了後、機関の番号を唯一に設定することで、任意の２個の機関Ｐｉ，Ｐｊ（ｉ≠ｊ）は、ｒ＋１個の（２，２）型の部分情報のうち、番号ｚ（２）で互いにビットβの異なる同一桁ｉの部分情報（ｄｉ，０  ，ｄｉ，１  ）から、秘密鍵ｄを復元可能となっている（ｄｉ，０  ＋ｄｉ，１  ＝ｄ）。
【００１２】
次に、上述した（２，２）型から（２，ｎ）型の秘密分散を構築する方式のように、秘密分散の型を拡張するための関連技術について述べる。
この種の技術としては、（ｔ，ｌ）型を用いた（ｔ，ｌｍ）型の秘密分散方式がある（Ｓ．  Ｒ．  Ｂｌａｃｋｂｕｒｍ，  Ｍ．  Ｂｕｒｍｅｓｔｅｒ，  Ｙ．  Ｄｅｓｍｅｄｔ  ａｎｄ  Ｐ．  Ｒ．  Ｗｉｌｄ，  Ｅｆｆｉｃｉｅｎｔ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｓｈａｒｉｎｇ  ｓｃｈｅｍｅｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯ−ＣＲＹＰＴ  ９６，  ｐｐ．  １０７−１１８，  １９９６．（以下、文献［ＢＢＤＷ９６］という））。但し、文献［ＢＢＤＷ９６］の方式は、正の整数ｍに対し、次の（１）式を満たすｌに関するものである。
【００１３】
【数１】
0003560860.tif 000002
【００１４】
ｔ＝２  ｂ≧１  →  ｌ≧１
ｔ＝３  ｂ≧３  →  ｌ≧３
ｔ＝４  ｂ≧６  →  ｌ≧６
となり、ｔ≧４ではｔ＜ｌとなる。すなわち、ｔ≧４では、（ｔ，ｔ）型を用いた（ｔ，ｎ）型の秘密分散方式を構築不可能となっている。
【００１５】
このため、以下では、同文献［ＢＢＤＷ９６］における（３，３）型を用いた（３，３３）型の秘密分散方式を説明する。ｍ＝２，ｌ＝３，ｔ＝３とし、（２）式に示すように、ｂを算出する。
【００１６】
【数２】
0003560860.tif 000003
【００１７】
まず、（３，３）型の秘密分散をｂ＋１＝４回実行し、（３）式に示すように、秘密鍵ｄに対する４つの独立多項式を構築する。
【００１８】
0003560860.tif 000004
また、ｆ（ｘ）＝ａ０  ＋ａ１  Ｘ  （ｍｏｄ  ３）とする。
【００１９】
ここで、同文献［ＢＢＤＷ９６］では、最終的な機関（ここでは３２  個の機関）の集合をＰ´としたとき、ｆ（Ｘ）は（４）式のように記載される（ｐｐ．１１３の１行目、なお、式中の“ｄ”は、本明細書中では“ｍ”と表記した）。
【００２０】
【数３】
0003560860.tif 000005
【００２１】
しかしながら、この（４）式は、次の（５）式の誤りと推測される。
【００２２】
【数４】
0003560860.tif 000006
【００２３】
但し、ａ０，ａ１∈Ｆ３であり、ｆ（∞）＝ａ１とする。
【００２４】
ｆ１  （ｘ）＝０  （ｍｏｄ  ３）
ｆ２  （ｘ）＝１  （ｍｏｄ  ３）
ｆ３  （ｘ）＝２  （ｍｏｄ  ３）
ｆ４  （ｘ）＝０＋Ｘ  （ｍｏｄ  ３）
ｆ５  （ｘ）＝１＋Ｘ  （ｍｏｄ  ３）
ｆ６  （ｘ）＝２＋Ｘ  （ｍｏｄ  ３）
ｆ７  （ｘ）＝０＋２Ｘ  （ｍｏｄ  ３）
ｆ８  （ｘ）＝１＋２Ｘ  （ｍｏｄ  ３）
ｆ９  （ｘ）＝２＋２Ｘ  （ｍｏｄ  ３）
各機関ｆｊは（ｄ０，ｆｊ（ ∞）  ，ｄ１，ｆｊ（０）  ，ｄ２，ｆｊ（１）  ，ｄ３，ｆｊ（２）  ）を持つ。具体的に各機関に保管される部分情報の集合は図１２に示す通りであり、機関の組合せと対象の部分情報は図１３に示す通りである。
【００２５】
図１２に示すように、例えば機関ｆ１  ，ｆ４  ，ｆ８  （２行目）で分散復号を行う際は、Ｘ＝∞に対応する部分情報を取り出す。それぞれ（ｄ０，０  ，ｄ０，１  ，ｄ０，２  ）による計算を行い、秘密鍵ｄに相当する出力を算出可能となっている。
【００２６】
また、図１３中、ａ〜ｌのいずれかのアルファベット符号の付された組合せは、各機関の同一の組合せにおいて、秘密鍵ｄに相当する出力の算出ルートが３種類あることを示している（なお、図１３中の“ｄ”は単なるアルファベット符号であり、秘密鍵ｄではない）。例えば符号ｂの付された機関の組合せ（ｆ１  ，ｆ２  ，ｆ３  ）では、Ｘ＝０，１，２の何れでも秘密鍵ｄを回復する３個の部分情報を揃えることが可能である。
【００２７】
また一方、上述した文献［ＢＦ９７］における（ｎ，ｎ）型の秘密分散方式に対し、しきい値法の概念を導入した方式がある（Ｙ．  Ｆｒａｎｋｅｌ，  Ｐ．  Ｄ．  ＭａｃＫｅｎｚｉｅ  ａｎｄ  Ｍ．  Ｙｕｎｇ，  Ｒｏｂｕｓｔ  ｅｆｆｉｃｉｅｎｔ  ｄｉｓｔｒｉｂｕｔｅｄ  ＲＳＡ−ｋｅｙ  ｇｅｎｅｒａｔｉｏｎ，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｔｈｉｒｔｉｅｔｈ  ａｎｎｕａｌ  ＡＣＭ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅｏｒｙ  ｏｆ  ｃｏｍｐｕｔｉｎｇ，  ｐｐ．  ６６３−６７２，  １９９８．（以下、文献［ＦＭＹ９８］という））。
【００２８】
文献［ＦＭＹ９８］の方式では、文献［ＢＦ９７］の（ｎ，ｎ）型の秘密分散に基づく（ｔ，ｎ）型の鍵生成・共有方式が示されている。具体的には、まず（ｎ，ｎ）型の鍵生成を行い、秘密鍵ｄに対する和の多項式を生成する。次に、各機関Ｐｉは、部分情報ｄｉのディーラーとなり、Ｓｕｍ−ｔｏ−Ｐｏｌｙ  （和から複数個へ）の変換を行う。このとき、各機関Ｐｉは、全ての機関Ｐｊ  からの部分情報ｄｊに対する共有情報を合成し、最終的に秘密鍵ｄに対する秘密分散を行って、秘密鍵ｄの（ｔ，ｎ）型の秘密共有を実現する。
【００２９】
これにより、文献［ＦＭＹ９８］の方式では、総数ｎ個のうち、任意のｔ個の機関ＰがＲＳＡ秘密鍵ｄを算出でき、鍵回復が可能となっている。
【００３０】
【発明が解決しようとする課題】
しかしながら以上のような秘密分散システムでは、以下のようにそれぞれ問題がある。
文献［ＢＢＤＷ９６］の方式では、ｔ＝３におけるｎ＞３２の場合とｔ≧４の場合には（ｔ，ｌｍ  ）型の秘密分散の構築が不可であるため、（２，ｎ）型の秘密分散の構築手法が一般化されていない。
【００３１】
また一方、文献［ＦＭＹ９８］の方式では、秘密鍵ｄを算出せずに、秘密鍵ｄを用いた署名や復号を試みる時には問題を生じる。例えば、公開鍵（ｅ，Ｎ）で暗号化された暗号文Ｃ＝Ｍｅ    （ｍｏｄ  Ｎ）があるとする。この暗号文Ｃを任意のｔ個の機関（この集合をΛとする）で復号するとき、各機関Ｐｊは、（６）式のようなラグランジュの補間係数λｊ，Λを算出し、この補間係数λｊ，Λからそれぞれ部分出力を得る必要がある。
【００３２】
【数５】
0003560860.tif 000007
【００３３】
しかしながら、いずれの機関Ｐｊも合成数Ｎ（＝ｐｑ）の素因数を知らないため、巾の位数φ（Ｎ）を法としたｌ−ｊの乗法逆元が算出不可能となり、ラグランジュの補間係数λｊ，Λも算出不可能となる。よって、ラグランジュの補間係数λｊ，Λを算出時に使う部分出力が算出不可能となり、（７）式の如き、部分出力の合成により平文を復元するための分散復号が実行不可能となってしまう。
【００３４】
【数６】
0003560860.tif 000008
【００３５】
本発明は上記実情を考慮してなされたもので、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号や署名を実現し得る（ｔ，ｎ）型の秘密分散システム、装置及び記憶媒体を提供することを目的とする。
【００３６】
【課題を解決するための手段】
請求項１に対応する発明は、公開鍵及び秘密鍵ｄを用いるＲＳＡ暗号系に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分最終情報が分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果又は署名結果を生成可能な（ｔ，ｎ）型の秘密分散システムであって、前記ｎ個の各機関としては、前記公開鍵及び前記秘密鍵ｄを生成する手段と、この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持する手段と、ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、前記部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を前記各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散する手段と、前記各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る手段と、前記ユーザ装置から受けた処理対象データを前記部分最終情報ｄj,kに基づいて演算処理し、得られた部分出力を前記ユーザ装置に返信する手段とを有し、前記ユーザ装置としては、前記ｔ個の機関を選択し、この選択したｔ個の各機関に処理対象データを送信する手段と、前記ｔ個の各機関から受信した部分出力を合成して前記復号結果又は署名結果を得る手段とを備えた秘密分散システムである。
【００３８】
また、請求項２に対応する発明は、第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムであって、前記ｎ個の各機関としては、前記ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjを前記ユーザ装置に返信する手段とを有し、前記ユーザ装置としては、前記ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に前記復号対象データＣ２を送信する手段と、前記ｔ個の各機関から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段と、前記復号結果Ｃ１、前記復号対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段とを備えた秘密分散システムである。
【００３９】
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
さらに、請求項３に対応する発明は、請求項２に対応する秘密分散システムにおいて、前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、前記最終復号結果Ｍを求める手段に代えて、前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段とを備えた秘密分散システムである。
【００４０】
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
また、請求項４に対応する発明は、公開鍵及び秘密鍵ｄを用いるＲＳＡ暗号系に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分最終情報が分散されたとき、その中の任意のｔ個の機関から得られた部分出力により、前記秘密鍵ｄを算出せずに復号結果又は署名結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用されるコンピュータ読み取り可能な記憶媒体であって、前記ｎ個の各機関内のコンピュータに、前記公開鍵及び前記秘密鍵ｄを生成する手段と、この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持する手段と、ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、前記部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を前記各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散する手段と、前記各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る手段、前記ユーザ装置から受けた処理対象データを前記部分最終情報ｄj,kに基づいて演算処理し、得られた部分出力を前記ユーザ装置に返信する手段、を実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体である。
【００４１】
さらに、請求項５に対応する発明は、第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）に適用され、互いに送受信可能なｎ個の機関及びユーザ装置を備え、ｎ個の機関に前記秘密鍵ｄの部分情報ｓjが分散されたとき、その中の任意のｔ個の機関により、前記秘密鍵ｄを算出せずに復号結果を生成可能な（ｔ，ｎ）型の秘密分散システムに使用される記憶媒体であって、前記ｎ個の各機関内のコンピュータに、前記ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjを前記ユーザ装置に返信する手段、を実現させるためのプログラムを記憶し、前記ユーザ装置内のコンピュータに、前記ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に前記復号対象データＣ２を送信する手段、前記ｔ個の各機関から受信した部分出力Ｚjを合成して前記復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ）、^はべき乗を示す記号）を得る手段、前記復号結果Ｃ１、前記処理対象データＣ２及び下記式に基づいて、演算処理を実行し、最終復号結果Ｍを求める手段、を実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体である。
【００４２】
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ）
また、請求項６に対応する発明は、請求項５に対応する記憶媒体において、前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、前記復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、前記最終復号結果Ｍを求める手段に代えて、前記署名結果Ｓ１（＝(Ｍd)e）、前記署名対象データＳ２（＝(Ｍd)Ｌ^2）及び下記式に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める手段とを実現させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体である。
【００４３】
a1＝（Ｌ2）-1  （ｍｏｄ  e）
a2＝（a1Ｌ2−１）／e
Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ）
また、請求項７に対応する発明は、請求項４に対応する発明に関する機関装置である。請求項８，９に対応する発明は、請求項５，６に対応する発明に関するユーザ装置である。請求項１０，１１に対応する発明は、請求項５，６に対応する発明に関する機関装置である。
（作用）
従って、請求項１，４，７に対応する発明は以上のような手段を講じたことにより、ｎ個の各機関が、公開鍵及び秘密鍵ｄを生成し、この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄi（０≦i≦ｎ）を保持し、ｔを底としたｎの対数ｌｏｇtｎ以上の最小の整数をｒとしたとき、この部分情報ｄiを（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数とし、そのうちのｒ＋１個の部分乱数を各機関の識別番号のｔ進表示（ｔj桁目の値k、０≦k≦ｔ−１、０≦j≦ｒ）に基づいて、それぞれ各機関に分散し、各機関から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔj毎にまとめてｒ＋１個の部分最終情報ｄj,kを得る。
【００４４】
続いて、ユーザ装置が、ｔ個の機関を選択し、この選択したｔ個の各機関に処理対象データを送信し、ｔ個の機関が、ユーザ装置から受けた処理対象データを部分最終情報ｄｊ，ｋ  に基づいて演算処理し、得られた部分出力をユーザ装置に返信し、ユーザ装置が、ｔ個の各機関から受信した部分出力を合成して復号結果又は署名結果を得る。
【００４５】
このように、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号や署名を実現することができ、また、ラグランジュ補間法を用いず、高い処理効率を実現することができる。
【００４６】
また、請求項２，５，８，１０に対応する発明は、第１の公開鍵（e，Ｎ）及び秘密鍵ｄと、第２の公開鍵（Ｌ2，Ｎ）とを用いるＲＳＡ暗号系（eとＬ2とは最大公約数が１であり、法Ｎは共通）において、ｎ個の機関に秘密鍵ｄの部分情報ｓjが分散されたとき、ユーザ装置が、ｎ個の機関のうちのｔ個の機関を選択し、この選択したｔ個の各機関に復号対象データＣ２を送信し、ｔ個の各機関が、ユーザ装置から受けた復号対象データＣ２（＝Ｍe  （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚjをユーザ装置に返信し、ユーザ装置が、ｔ個の各機関から受信した部分出力Ｚjを合成して復号結果Ｃ１（＝ＭＬ^2  （ｍｏｄ  Ｎ））を得ると共に、復号結果Ｃ１、処理対象データＣ２及び所定の式（a1＝（Ｌ2）-1  （ｍｏｄ  e）、a2＝（a1Ｌ2−１）／e、Ｍ＝Ｃ1a1（Ｃ2a2）-1  （ｍｏｄ  Ｎ））に基づいて、演算処理を実行し、最終復号結果Ｍを求める。
【００４７】
これにより、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号を実現することができ、また、所定条件の公開鍵を用いたラグランジュ補間法に基づき、高い確実性を実現することができる。
【００４８】
さらに、請求項３，６，９，１１に対応する発明は、前記復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、復号結果Ｃ１に代えて、署名結果Ｓ１（＝ＭdＬ^2（ｍｏｄ  Ｎ）、^はべき乗を示す記号）を用い、最終復号結果Ｍを求める手段に代えて、署名結果Ｓ１（＝(Ｍd)e）、署名対象データＳ２（＝(Ｍd)Ｌ^2）及び所定の式（a1＝（Ｌ2）-1  （ｍｏｄ  e）、a2＝（a1Ｌ2−１）／e、Ｍｄ＝Ｓ1a1（Ｓ2a2）-1  （ｍｏｄ  Ｎ））に基づいて、演算処理を実行し、最終署名結果Ｍｄを求める。
【００４９】
これにより、請求項２，５，８，１０に対応する作用と同様の作用を署名処理において実現することができる。
【００５０】
【発明の実施の形態】
次に、本発明の各実施形態について図面を参照して説明する。なお、第１の実施形態は、ラグランジュ補間法を用いず、高い処理効率を実現したものであり、第２の実施形態は、所定条件の公開鍵を用いたラグランジュ補間法に基づき、高い確実性を実現したものであって、両者ともノンディーラーモデルのしきい値法による分散復号及び署名の可能な（ｔ，ｎ）型の秘密分散システムとなっている。以下、順次説明する。
【００５１】
（第１の実施形態）
本実施形態は、文献［ＢＦ９７］における（２，２）型から（２，ｎ）型の秘密分散を構築する方式を一般化した（ｔ，ｎ）型の秘密分散システムである。
具体的には、文献［ＢＦ９７］の方式を用いて各機関Ｐｉ  が秘密鍵ｄの（ｎ，ｎ）型の部分情報ｄｉ  を保持すると、全ての機関Ｐ１  〜Ｐｎ  がそれぞれ部分情報ｄｉ  を（ｔ，ｎ）型の部分乱数情報として分配し、各機関Ｐ１  〜Ｐｎ  が部分乱数情報を桁毎にまとめて複数の部分情報ｄｊ，ｋ  を得る（ｔ，ｎ）型の秘密分散システムとなっている。
【００５２】
図１は本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、各々計算機システムとしてのｎ個の機関Ｐ１  〜Ｐｎ  及びユーザ装置Ｕが互いにネットワークを介して接続されている。
【００５３】
なお、各機関Ｐ１  〜Ｐｎ  は、互いに同一構成を有するので、ここでは任意の機関Ｐｉ  （但し、１  ≦ｉ  ≦ｎ  ）を代表例として説明する。
【００５４】
機関Ｐｉ  は、公開鍵（ｅ  ，Ｎ）及び秘密鍵ｄを生成する機能と、［ＢＦ９７］の方式に基づいて、秘密鍵ｄを（２，ｎ）型の部分情報とし、そのうちのｒ＋１個の部分情報をそれぞれ各機関Ｐ１  〜Ｐｎ  に分散する機能と、分散されたｒ＋１個の部分情報に基づいて、（ｎ，ｎ）型の１個の部分情報ｄｉ  を保持する機能と、この部分情報ｄｉ  を（ｔ，ｎ）型の部分乱数とし、そのうちのｒ＋１個の部分乱数を機関の識別番号のｔ進表示に基づいて、それぞれ各機関Ｐ１  〜Ｐｎ  に分散する機能と、各機関Ｐ１  〜Ｐｎ  から分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔｊ  毎にまとめてｒ＋１個の部分情報ｄｊ，ｋ  を得る機能と、ユーザ装置Ｕから受けた暗号文Ｃを復号処理して得られた部分出力Ｘｚ  をユーザ装置Ｕに返信する機能とをもっている。
【００５５】
また、各機関Ｐｉ  は、任意のｔ個が選択された場合、図示しないが、“Ｐ”に代えて“Ｔ”の表記を用いる。例えば“機関Ｐｚ  ”は選択されているとき、“機関Ｔｚ  ”と表記される。
【００５６】
ユーザ装置Ｕは、ｎ個の機関Ｐ１  〜Ｐｎ  のうちのｔ個の機関Ｔｚ  を選択する機能と、公開鍵（ｅ  ，Ｎ）で暗号化された暗号文Ｃをｔ個の各機関Ｔｚ  に送信する機能と、各機関Ｔｚ  から受信した部分出力Ｘｚ  を合成して平文Ｍを得る機能とをもっている。
【００５７】
次に、各機関Ｐ１  〜Ｐｎ  及びユーザ装置Ｕの具体的なハードウェア構成について述べる。具体的には、機関Ｐｉ  及びユーザ装置Ｕは、ハードウェア的には図２に示すように、ＣＰＵ１１、コントローラ１２、メモリ１３、通信デバイス１４、ディスプレイ１５、キーボード１６及びプリンタ１７が互いにバス１８を介して接続された計算機システムである。
【００５８】
これらの構成のうち、メモリ１３は、いわゆる主記憶（ＲＡＭ等）と二次記憶装置（ハードディスク等）の双方を含むものである。この主記憶上に読み込まれたプログラムと、このプログラムに従うＣＰＵ１１の制御とにより、機関Ｐｉ  が行うべき機能が実現される。すなわち、各機関Ｐ１  〜Ｐｎ  及びユーザ装置Ｕは、ソフトウェア的には、上述したそれぞれの機能を行うように、互いに異なる構成を有するものである。これらハードウェア及びソフトウェアの結合からなるそれぞれの機能の詳細な内容は、以下の動作説明において詳細に述べる。
【００５９】
但し、各機関Ｐ１  〜Ｐｎ  は、ユーザ装置Ｕから受信したデータを演算処理し、結果をユーザ装置Ｕに返信するためのハードウェアがあればよいので、例えばディスプレイ１５、キーボード１６及びプリンタ１７などを適宜、省略してもよい。同様に、ユーザ装置Ｕにおいても、例えばプリンタ１７を省略してもよい。
【００６０】
次に、以上のように構成された秘密分散システムの動作を説明する。
（（ｔ，ｎ）型の秘密分散）
各機関Ｐ１  〜Ｐｎ  は、公開鍵（ｅ  ，Ｎ）及び秘密鍵ｄを生成すると、文献［ＢＦ９７］の方式に基づいて、秘密鍵ｄを（２，ｎ）型の部分情報とし、そのうちのｒ＋１個の部分情報をそれぞれ各機関Ｐ１  〜Ｐｎ  に分散する。
【００６１】
各機関Ｐ１  〜Ｐｎ  は、［ＢＦ９７］の方式によるｒ＋１個の部分情報に基づき、合成数Ｎにおける互いに異なる２つの素因数ｐ，ｑと、秘密鍵ｄとを（ｎ，ｎ）型で秘密共有している。
【００６２】
すなわち、各機関Ｐｉ  （１≦ｉ≦ｎ）は、図３に示すように、次の（８）式を満たす部分情報ｄｉ  をそれぞれ保管している（ＳＴ１）。
【００６３】
ｄ＝ｄ１  ＋ｄ２  ＋…＋ｄｎ      …（８）
次に、全ての各機関Ｐｉ  は、自己の部分情報ｄｉ  のディーラーとして機能する。すなわち、全ての各機関Ｐｉ  は、（９）式に示すように、自己の部分情報ｄｉ  を示す（ｔ，ｎ）型の部分乱数情報Ｓｊ，ｌ（０≦ｊ  ≦ｒ，０≦ｌ≦ｔ−２）を生成する（ＳＴ２）。但し、ｒ＝「ｌｏｇｔ  ｎ」である。
【００６４】
【数７】
0003560860.tif 000009
【００６５】
なお、この部分乱数情報Ｓｊ，ｌの生成処理は、全ての各機関Ｐｉ  が、それぞれ次に示す如き、自己の部分情報ｄｉ  を示すｒ＋１個の独立多項式を作成することと等価である。
【００６６】
0003560860.tif 000010
次に、全ての各機関Ｐｉは、識別番号をｚとしたとき、以下のステップＳＴ３〜ＳＴ４に示すように、各機関Ｐｚ  （１≦ｚ≦ｎ）と互いに部分乱数情報Ｓｊ，ｌを分散しあう。
すなわち、機関Ｐｚの識別番号ｚを（１０）式に示すように、ｔ進数に変換する（ＳＴ３）。
ｚ＝βｒ，ｚｔｒ  ＋βｒ−１，ｚ  ｔｒ−１  ＋…＋  βｊ，ｚ  ｔｊ  ＋…＋β０，ｚ      …（１０）
簡単のため、（１０）式を（１１）式のように表記する。
ｚ（ｔ）＝βｒ，ｚ  βｒ−１，ｚ  …  βｊ，ｚ  …  β０，ｚ      …（１１）
但し、ｔ進値βｒ，ｚ∈｛０，…，ｔ−１｝
また、各機関Ｐｉは、ｚ（ｔ）における各桁ｔｊ毎のｔ進値βに基づいて、次に示すｒ＋１個の部分乱数情報を含む集合Ｓを機関Ｐｚに送信する（ＳＴ４）。
【００６７】
【数８】
0003560860.tif 000011
【００６８】
各機関Ｐｚ  は、自己を含む全ての各機関Ｐｉから得た集合Ｓに基づいて、次の（１２）式に示すように、各桁ｊ  毎の部分乱数情報Ｓｊ，ｌの総和をとって部分情報ｄｊ，ｋ  を算出する（ＳＴ５）。但し、ｋ  ∈｛βｒ，ｚ  βｒ−１，ｚ  …  β０，ｚ｝，０≦ｊ≦ｒである。
【００６９】
【数９】
0003560860.tif 000012
【００７０】
各機関Ｐｚ  は、桁ｊ  の数に対応するｒ＋１個の部分情報ｄｊ，ｋ  を保管する（ＳＴ６）。なお、部分情報ｄｊ，ｋ  は、秘密鍵ｄの部分集合である。
【００７１】
秘密鍵ｄと部分秘密鍵ｄｊ，ｋ  との関係は、以下の（１３）式に示す通りである。
0003560860.tif 000013
例えば、（３，２７）型の秘密分散における機関ｚ＝２０の保管情報は、以下の通りである。
【００７２】
ｒ＝「ｌｏｇ３    ２７」＝３
２０＝０×３３  ＋２×３２  ＋０×３１  ＋２×３０
２０（３）＝０２０２  （３進表示）
よって、機関Ｐ２０は、次の（１４）式に示す全ての部分情報のうち、識別番号ｚの３進表示（０２０２）に対応する部分情報（ｄ３，０  ，ｄ２，２  ，ｄ１，０  ，ｄ０，２  ）を保管する。
【００７３】
0003560860.tif 000014
（分散復号化）
ｎ個の機関Ｐ１  〜Ｐｎ  のうち、任意のｔ個の機関Ｔｚ  （この集合をΛとする）は、ユーザ装置Ｕからの復号依頼により、ユーザ装置Ｕの公開鍵（ｅ  ，Ｎ）で暗号化されたデータＣ＝Ｍｅ  （ｍｏｄ  Ｎ）を図４のステップＳＴ１１〜ＳＴ１６に示すように分散復号化する。
【００７４】
すなわち、ユーザ装置Ｕは、（１５）式に示すように、ｔ個の機関Ｔｚ  の識別番号ｚをそれぞれｔ進表示に変換する（ＳＴ１１）。
【００７５】
ｚ（ｔ）＝βｒ，ｚ  βｒ−１，ｚ  …  β０，ｚ      …（１５）
続いて、ユーザ装置Ｕは、ｔ個の機関Ｔａ，Ｔｂ∈Λ（ａ≠ｂ）におけるｔ進表示の各桁ｔｊ  （０≦ｊ≦ｒ）毎に、ｔ進表示の値βが全て異なる（βｊ，ａ  ≠βｊ，ｂ）という条件を満たす桁ｔｊ  が有るか否かを判定する（ＳＴ１２）。
【００７６】
この条件を満たす桁ｔｊ  がないとき、この集合Λによる分散復号は不可能であるため、集合Λ内の機関Ｔｚを多少入れ換えて（ＳＴ１３）、ステップＳＴ１１から再実行する。
【００７７】
ステップＳＴ２で条件を満たす桁ｔｊ  があるとき、ユーザ装置Ｕは、暗号化データＣを各機関Ｔｚ  に送信する（ＳＴ１４）。
【００７８】
各機関Ｔｚ  は、ｔｊ  桁に対応する部分情報ｄｊ，ｋ  （ｋ＝βｊ，ｚ  ）に基づいて、暗号化データＣを復号処理し、得られた部分出力Ｘｚ  （＝Ｃｄｊ，ｋ  （ｍｏｄ  Ｎ））をそれぞれユーザ装置Ｕに返信する（ＳＴ１５）。
【００７９】
ユーザ装置は、ｔ個の各機関Ｔｚ  （ｚ∈Λ）から受信したｔ個の部分出力Ｘｚ（ｚ∈Λ）を（１６）式のように合成し、平文Ｍを復元することができる（ＳＴ１６）。
【００８０】
【数１０】
0003560860.tif 000015
【００８１】
また、以上の動作は、暗号化データＣ（＝Ｍｅ  （ｍｏｄ  Ｎ））をｔ個の各機関Ｔｚに送ることにより、平文Ｍを分散復号した場合である。これに限らず、本実施形態は、図５に示すように、暗号化データＣに代えて、署名対象データＭをｔ個の各機関Ｔｚに送信したとき（ＳＴ１４ａ）、前述した部分出力Ｘｚの合成により、署名Ｍｄ  （ｍｏｄ  Ｎ）を得ることもできる（ＳＴ１６ａ）。
上述したように本実施形態によれば、ｎ個の各機関Ｐ１  〜Ｐｎ  が、公開鍵及び秘密鍵ｄを生成し、この秘密鍵ｄに基づいて生成された（ｎ，ｎ）型の１個の部分情報ｄｉ  （０≦ｉ  ≦ｎ）を保持し、ｔを底としたｎの対数ｌｏｇｔ  ｎ以上の最小の整数をｒとしたとき、この部分情報ｄｉ  を（ｔ，ｎ）型のｔ（ｒ＋１）個の部分乱数Ｓｊ  とし、そのうちのｒ＋１個の部分乱数Ｓｊ  を各機関Ｐｉの識別番号ｚのｔ進表示（ｔｊ  桁目の値ｋ  、０≦ｋ  ≦ｔ−１、０≦ｊ  ≦ｒ）に基づいて、それぞれ各機関Ｐ１  〜Ｐｎ  に分散し、これら分散されたｎ（ｒ＋１）個の部分乱数をｔ進表示の桁ｔｊ  毎にまとめてｒ＋１個の部分情報ｄｊ，ｋ  を得る。
【００８２】
続いて、ユーザ装置Ｕが、ｔ個の機関Ｔｚを選択して暗号化データＣ（又は署名対象データ）を送信し、ｔ個の機関Ｔｚが、暗号化データＣ（又は署名対象データ）を部分情報ｄｊ，ｋ  に基づいて演算処理し、得られた部分出力Ｘｚをそれぞれユーザ装置Ｕに返信し、ユーザ装置Ｕが、ｔ個の部分出力Ｘｚを合成して復号結果（又は署名結果）を得る。
【００８３】
このように、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号や署名を実現することができる。また、復号分散時に、ラグランジュの補間係数を算出する手間を省略でき、高い処理効率を実現することができる。
【００８４】
また、本実施形態は、予め暗号文への入力を表として保持でき、ラグランジュの補間係数の算出が不要な分だけ、文献［ＦＭＹ９８］の方式よりも、演算の処理効率を向上させることができる。
【００８５】
さらに、本実施形態は、全ての組合せに応じたラグランジュの補間係数を表として保管する場合、文献［ＦＭＹ９８］の方式よりも、保管する情報の量を低減させることができる。
【００８６】
例えば、文献［ＦＭＹ９８］の方式は、ラグランジュの補間法に基づくしきい値法を用いた分散復号化を行う。ここでは、秘密鍵ｄが各機関Ｐ１  〜Ｐｎ  のもつ部分情報の単純和ではなく、各機関Ｐｊ  は、前述したラグランジュの補間係数λｊ，Λを算出し、合成する必要がある。よって、補間係数λｊ，Λを予め算出して表に保管する場合、１つの部分情報と参加機関Ｔｚ  の全ての組合せに応じたｎＣｔ個の補間係数λｊ，Λを算出して保管する必要がある。
【００８７】
一方、本実施形態では、「ｌｏｇｔ  ｎ」＋１個の部分情報から機関の組合せに対応する部分情報を選択すればよい。よって、保管される部分情報は、「ｌｏｇｔ  ｎ」＋１個でよく、少ない情報量となっている。
【００８８】
ところで、本実施形態の方式によれば、ｔ個の機関の組合せが悪いとき、暗号文を分散復号できない場合がある。この場合について（３，２７）型の秘密分散を例に挙げて補足的に説明する。今、秘密鍵ｄについて、以下のｒ＋１個の多項式が成立しているとする。
【００８９】
0003560860.tif 000016
まず、分散復号が可能な場合を示す。２７個の機関のうち、機関Ｐ２０，Ｐ２３，Ｐ２６が分散復号プロトコルに介入するとき、復号操作Ｃｄ  ＝Ｍｅｄ＝Ｍは成功する。ここで、各機関Ｐ２０，Ｐ２３，Ｐ２６の３進表示は、Ｐ２０＝０２０２，Ｐ２３＝０２１２，Ｐ２６＝０２２２であり、それぞれの保管情報は図６に示す通りとなっている。ここで、３１  桁に注目すると、（１７）式に示すように、ｄ＝ｄ１，０  ＋ｄ１，１  ＋ｄ１，２  からｄによる復号化処理が可能となる。
0003560860.tif 000017
ところが、Ｐ２３に代えてＰ１１を用いた各機関Ｐ２０，Ｐ２３，Ｐ１１では、復号操作は失敗する。すなわち、各機関の３進表示は、Ｐ２０＝０２０２，Ｐ２３＝０２１２，Ｐ１１＝０１０２であり、それぞれの保管情報は図７に示す通りである。
【００９０】
この場合、秘密鍵ｄを構成する３つの部分情報（ｄｊ，０  ＋ｄｊ，１  ＋ｄｊ，２  ）がどの桁ｊ  でも揃わず、いずれかの部分情報が２つ以上の機関において重複（衝突）している。このように保管する部分情報の重複により、分散復号の不可能な場合がある。
【００９１】
この場合、別のｔ個の機関を選択し直す必要がある。
ここで、機関の総数ｎが大きく、ｔ個以上の機関を比較的自由に選択可能な場合、本実施形態の（ｔ，ｎ）型の秘密分散が適している。すなわち、機関の総数ｎが大きいときには復号不能となっても、ｔ個の機関Ｐを再編成して分散復号プロトコルをし直せばよい。
【００９２】
逆にｎの数が小さく、機関Ｐの選択の余地がない場合は、全ての組合せに応じた関係式を作成する方式が適している。例えば、エルガマル（ＥｌＧａｍａｌ）  暗号系では、ｎ個のうちの任意のｔ個の機関がグループの鍵で暗号化された暗号文を復号することができる技術が提案されている（Ｔ．  Ｐ．  Ｐｅｄｅｒｓｅｎ，  Ａ  ｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ｗｉｔｈｏｕｔ  ａ  ｔｒｕｓｔｅｄ  ｐａｒｔｙ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ  ９１，  ＬＮＣＳ  ５４７，  ｐｐ．５２２−５２６，  １９９１．（以下、文献［Ｐｅｄ９１ｂ］という））。すなわち、文献［Ｐｅｄ９１ｂ］の方式のように任意のｔ個の機関で分散復号・鍵復元を行うには、秘密鍵ｄに関するｎ  Ｃｔ  個の独立な関係式を作成すればよい。具体的には、ある組合せ（Λ）のときは（１８）式のように該当する関係式により分散復号を行う方式である。
【００９３】
ｄ＝ｄ１，Λ＋ｄ２，Λ＋…＋ｄｔ，Λ      …（１８）
しかしながら、文献［Ｐｅｄ９１ｂ］の方式では、衝突の可能性はないものの、機関の総数ｎに比例して関係式の数が膨大になってしまう。よって、衝突の可能性の低い範囲で、独立多項式を最小限に抑えることが好ましい。
【００９４】
各方式はそれぞれ長所・短所があるので、第１実施形態の方式（再編成する方式）、第１実施形態の方式において関係式を用いる方式、あるいは後述する第２の実施形態の方式（補間法を用いる方式）のいずれを選択するかは、機関の総数ｎや処理効率、使用される環境、復号処理不能が許されるか否かなどの条件に応じて使い分けることが好ましい。
【００９５】
（第２の実施形態）
次に、本発明の第２の実施形態について説明するが、その前に本実施形態の前提となるＲＳＡ共通法誤用プロトコルについて述べる。
【００９６】
ＲＳＡ暗号系において、１つのメッセージＭを、互いに共通する法Ｎと、互いに異なる公開指数ｅ１，ｅ２とを用いる条件の下でそれぞれ暗号化し、得られた２つの異なる暗号文Ｃ１  ，Ｃ２  があるとする。この場合、合成数Ｎの素因数が不明でも、２つの暗号文Ｃ１  ，Ｃ２  からメッセージＭを復元できる（Ｇ．  Ｊ．  Ｓｉｍｍｏｎｓ，  Ａｗｅａｋ  ｐｒｉｖａｃｙ  ｐｒｏｔｏｃｏｌ  ｕｓｉｎｇ  ｔｈｅ  ＲＳＡ  ｃｒｙｐｔｏａｌｇｏｌｉｔｈｍ，  Ｃｒｙｐｔｏｌｏｇｉａ，  ｖｏｌ．  ７，  ｐｐ．１８０−１８２，  １９８３．（以下、文献［Ｓｉｍ８３］という））。
【００９７】
この文献［Ｓｉｍ８３］の方式において、前述した２つの暗号文Ｃ１  ，Ｃ２  は、次の（１９）式〜（２０）式に示すように得られている。
【００９８】
Ｃ１  ＝Ｍｅ１  （ｍｏｄ  Ｎ）      …（１９）
Ｃ２  ＝Ｍｅ２  （ｍｏｄ  Ｎ）      …（２０）
ここで、異なる公開指数ｅ１，ｅ２  の最大公約数ｇｃｄ  （ｅ１，ｅ２）＝１である場合、以下のステップＳＴｃ１〜ＳＴｃ３を行うと、２つの暗号文Ｃ１  ，Ｃ２  からメッセージＭを復元できる（Ｄ．  Ｒ．  Ｓｔｉｎｓｏｎ，  ＣＲＹＰＴＯＧＲＡＰＨＹ  ：  Ｔｈｅｏｒｙ  ａｎｄ  Ｐｒａｃｔｉｃｅ，  ＣＲＣＰｒｅｓｓ，  Ｉｎｃ．  Ｂｏｃａ  Ｒａｔｏｎ，  Ｆｌｏｒｉｄａ，  Ｕ．Ｓ．Ａ．，  １９９５．  （以下、文献［Ｓｔｉ９５］という））。
【００９９】
（ステップＳＴｃ１）ａ１  ＝ｅ１−１  （ｍｏｄ  ｅ２）
（ステップＳＴｃ２）ａ２  ＝（ａ１ｅ１  −１）／ｅ２
（ステップＳＴｃ３）Ｍ＝Ｃ１ａ１  （Ｃ２ａ２  ）−１  （ｍｏｄ  Ｎ）
また、上記処理（Ｓｔｅｐ  ｃ１  〜ｃ３）を次のように表記する。
【０１００】
Ｃｏｍｍｏｎ（ｅ１，ｅ２）→Ｍ
以上のように、ＲＳＡ暗号系においては、所定の条件を満たすとき、メッセージＭを復元可能なプロトコルが存在する。このプロトコルがＲＳＡ共通法誤用プロトコルと呼ばれている。
【０１０１】
さて次に、本発明の第２の実施形態に係る秘密分散システムについて説明する。本実施形態は、文献［Ｓｉｍ８３］及び［Ｓｔｉ９５］等のＲＳＡ共通法誤用プロトコルを適用可能な条件で公開鍵を作成し、文献［ＦＭＹ９８］の手法により、秘密鍵ｄの部分情報ｓｊ  を分散する（ｔ，ｎ）型の秘密分散システムである。
【０１０２】
なお、ＲＳＡ共通法誤用プロトコルを適用可能な条件とは、次の（ａ）〜（ｃ）を全て満たすことに相当する。
（ａ）メッセージＭが同じである。
（ｂ）法Ｎが共通する。
（ｃ）互いに異なる公開指数（ｅ１，ｅ２）の最大公約数ｇｃｄ  （ｅ１，ｅ２）＝１である。
但し、以下の説明では、公開指数（ｅ１，ｅ２）を（Ｌ２  ，ｅ  ）と表記している。また、公開指数Ｌ２  の元となるＬは、Ｌ＝ｎ！に代えて、Ｌ＝（ｎ−１）！としてもよい。
また、ユーザ装置及び各機関は、ハードウェア的な構成に関しては図１及び図２に示した通りとし、機能に関しては第１実施形態とは異なるので、以下に説明する。
【０１０３】
なお、各機関Ｐ１  〜Ｐｎ  は、前述同様に、任意の機関Ｐｉ  （但し、１  ≦ｉ  ≦ｎ  ）を代表例として説明する。
機関Ｐｉ  は、［ＦＭＹ９８］の方式に基づいて、法Ｎの部分情報（ｐｊ  ，ｑｊ  ）を作成する機能と、これら部分情報ｐｊ  ，ｑｊ  をそれぞれ各機関Ｐ１  〜Ｐｎ  に分散する機能と、各機関Ｐｊ  の（ｐｊ  ，ｑｊ  ）を基に、公開鍵（ｅ  ，Ｎ）を生成する機能と、秘密鍵ｄから（ｔ，ｎ）型の部分情報ｓｊ  を得る機能と、夫々部分情報（ｐｊ  ，ｑｊ  ）及びｓｊ  を保持する機能と、ユーザから受けた暗号文Ｃ（＝Ｃ２  ＝Ｍｅ    （ｍｏｄ  Ｎ））を復号処理して得られた部分出力Ｚｊ  をユーザ装置Ｕに返信する機能とをもっている。
【０１０４】
ユーザ装置Ｕは、ｎ個の機関のうちのｔ個の機関Ｔｚ  を選択する機能と、公開鍵（ｅ  ，Ｎ）で暗号化された暗号文Ｃ２  （＝  Ｍｅ  （ｍｏｄ  Ｎ））をｔ個の各機関Ｔｚ  に送信する機能と、各機関Ｔｚ  から受信した部分出力Ｚｊ  を合成して暗号文Ｃ１  （＝  ＭＬ２（ｍｏｄ  Ｎ））を得る機能と、２つの暗号文（ＭＬ２，Ｍｅ  ）から、前述したＲＳＡ共通法誤用プロトコルＣｏｍｍｏｎ（Ｌ２  ，ｅ  ）→Ｍを用いて、メッセージＭを算出する機能とをもっている。
【０１０５】
次に、以上のように構成された秘密分散システムの動作を説明する。
（（ｔ，ｎ）型の秘密分散）
各機関は互いに、文献［ＦＭＹ９８］の方式に基づいて、秘密鍵ｄを（ｔ，ｎ）型の部分情報とし、対応する部分情報ｓｊ  を個別にｎ個の機関Ｐ１  〜Ｐｎ  に分散する。
【０１０６】
具体的には、各機関Ｐｊ  は、法Ｎの構成要素（ｐｊ  ，ｑｊ）を作成し、夫々送信する。各機関Ｐｊ  は、他の各機関Ｐｊ  から受けた（ｐｊ  ，ｑｊ）の合成Ｎ＝（ｐ１  ＋ｐ２  ＋…＋ｐｎ  ）（ｑ１  ＋ｑ２  ＋…＋ｑｎ  ）が異なる２つの素数の積であるか否かを判定し、異なる素数の積であるとき、正当として次に進む。
【０１０７】
各機関Ｐｊ  は（ｐｊ  ，ｑｊ）を基に、公開鍵（ｅ，Ｎ）を生成し、各機関Ｐｊ  の保持すべき秘密鍵ｄの部分情報ｄｊ  を算出する（（ｎ，ｎ）型秘密分散完了）。
【０１０８】
ｄ＝ｄ１  ＋ｄ２  ＋…＋ｄｊ  ＋…＋ｄｎ
次に、各機関Ｐｊ  は、（ｎ，ｎ）型の秘密鍵ｄをＳｕｍ−ｔｏ−Ｐｏｌｙ  の技術により、（ｔ，ｎ）型の秘密鍵ｄに変換する（（ｔ，ｎ）型秘密分散完了）。
【０１０９】
このとき、ｔ−１個の乱数｛ｂ１，…ｂｔ−１｝∈Ｚに対し、（２１）式の如き、多項式を定める。
ｆ（ｘ）＝ｄ＋ｂ１ｘ＋ｂ２ｘ２＋…＋ｂｔ−１ｘｔ−１      …（２１）
この式は、ｙ切片を秘密鍵ｄとしたｋ−１次の多項式であり、ラグランジュの補間法により、ｋ個の座標点（ｊ  ，ｆ（ｊ））から一意に定まる性質をもっている。但し、ｋ−１個の座標点からは一意に定まらず、任意のｙ切片が可能となり、秘密鍵ｄを得られない性質もある。
【０１１０】
各機関Ｐｊ  は、各機関Ｐ１  〜Ｐｎ  の自己の識別番号ｊ  （１≦ｊ  ≦ｎ）を独立変数ｘとして上記多項式ｆ（ｘ）  に代入してｆ（ｊ）  を計算し、ｆ（ｘ）  上のｙ座標を示す部分情報ｓｊ  （＝ｆ（ｊ）  ）を各機関Ｐｊ  毎に得る。
【０１１１】
各機関Ｐｊ  は、得られた（ｔ，ｎ）型の部分情報ｓｊ  と、予め保持する、法Ｎの素因数ｐｑの部分情報（ｐｊ  ，ｑｊ  ）とを保管する。なお、（ｎ，ｎ）型の部分情報ｄｊ  も保持されるが、本実施形態では特に使用されない。
【０１１２】
（分散復号化）
ｎ個の機関のうち、任意のｔ個の機関Ｔｚ  （この集合をΛとする）は、ユーザ装置Ｕからの復号依頼により、ユーザ装置Ｕの公開鍵（ｅ  ，Ｎ）で暗号化されたデータＣ＝Ｍｅ  （ｍｏｄ  Ｎ）を図８のステップＳＴ２１〜ＳＴ２４に示すように分散復号化する。ここで、Ｌ＝ｎ！かつ最大公約数ｇｃｄ  （ｅ  ，Ｌ２  ）＝１とする。
【０１１３】
すなわち、ユーザ装置Ｕは、暗号文Ｃ（＝Ｍｅ  （ｍｏｄ  Ｎ））をｔ個の各機関Ｔｊ（∈Λ）に送信する（ＳＴ２１）。
各機関Ｔｊは、次の（２２）式〜（２４）式の通り、それぞれ自己の部分情報ｓｊを用いて部分出力Ｚｊを算出し、得られた部分出力Ｚｊをユーザ装置Ｕに返信する（ＳＴ２２）。
【０１１４】
【数１１】
0003560860.tif 000018
【０１１５】
ユーザ装置Ｕは、次の（２５）式のように、ｔ個の各機関Ｔｊから受ける部分出力Ｚｊ  を合成し、暗号文ＭＬ２（ｍｏｄ  Ｎ）を算出する（ＳＴ２３）。
【０１１６】
【数１２】
0003560860.tif 000019
【０１１７】
ユーザ装置Ｕは、元の暗号文Ｍｅ  と、この暗号文ＭＬ２との互いに異なる２つの暗号文（ＭＬ２，Ｍｅ  ）から、前述したＲＳＡ共通法誤用プロトコルＣｏｍｍｏｎ（Ｌ２  ，ｅ  ）→Ｍを用いて、メッセージＭを算出する（ＳＴ２４）。なお、本実施形態と、前述したプロトコルとの対応関係は、（ＭＬ２，Ｍｅ  ）＝（Ｃ１  ，Ｃ２  ）であり、（Ｌ２  ，ｅ  ）＝（ｅ１，ｅ２）である。ここで、ＲＳＡ共通法誤用プロトコルは、（２６）式に示すように、健全性を有している。
【０１１８】
Ｃ１ａ１  （Ｃ２ａ２  ）−１＝ＭＬ２ａ１ −ｅａ２  ＝Ｍ（ｍｏｄ  Ｎ）  …（２６）
（分散署名）
なお、ユーザ装置Ｕは、分散復号に限らず、ｔ個の機関Ｔｚに分散署名を行わせてもよい。
この場合、ユーザ装置Ｕは、図９に示すように、復号対象の暗号文Ｃに代えて、署名対象データＳ１（＝Ｍ）を用い（ＳＴ２１ａ）、復号結果の暗号文ＭＬ２に代えて、署名結果Ｓ２（＝（  Ｍｄ）Ｌ＾２（ｍｏｄ  Ｎ）、＾  はべき乗を示す記号）を用いる（ＳＴ２３ａ）。
【０１１９】
そして、ユーザ装置Ｕは、（Ｃ１  ，Ｃ２  ）＝（Ｍｄ Ｌ＾２，Ｍ）＝（（  Ｍｄ）Ｌ＾２，（  Ｍｄ）ｅ  ）から、前述同様に、以下のＲＳＡ共通法誤用プロトコルに基づいて、署名Ｍｄ  を算出する（ＳＴ２４ａ）。
【０１２０】
ａ１＝（Ｌ２  ）−１  （ｍｏｄ  ｅ  ）
ａ２＝（ａ１Ｌ２  −１）／ｅ
Ｍ＝Ｃ１ａ１  （Ｃ２ａ２  ）−１  （ｍｏｄ  Ｎ）
ここで、ＲＳＡ共通法誤用プロトコルは、（２７）式に示すように、健全性を有している。
【０１２１】
0003560860.tif 000020
（分散署名の変形例）
なお、上述した分散署名は、図１０に示すように変形してもよい。すなわち、ステップＳＴ２３ａの後、ユーザ装置Ｕは、この署名対象データＳ１及び署名結果Ｓ２の組を図示しない相手先の署名検証装置に送信する（ＳＴ２５ａ）。
署名検証装置は、署名対象データＳ１及び第１公開鍵（ｅ  ，Ｎ）から第１比較データＤ１（＝Ｍｅ    （ｍｏｄ  Ｎ））を算出し、署名結果Ｓ２及び第２公開鍵（ｅ  ，Ｎ）から第２比較データＤ２（＝ＭＬ＾２  （ｍｏｄ  Ｎ））を算出する（ＳＴ２６ａ）。
【０１２２】
続いて、署名検証装置は、第１並びに第２比較データＤ１，Ｄ２及び下記（２８）式〜（３０）式のＲＳＡ共通法誤用プロトコルに基づいて、演算処理を実行し、出力Ｍを求める（ＳＴ２７ａ）。
【０１２３】
ａ１＝（Ｌ２  ）−１  （ｍｏｄ  ｅ  ）            …（２８）
ａ２＝（ａ１Ｌ２  −１）／ｅ                      …（２９）
Ｍ＝Ｄ１ａ１  （Ｄ２ａ２  ）−１  （ｍｏｄ  Ｎ）    …（３０）
ここで、出力Ｍと署名対象データＳ１とが一致するとき、署名検証装置は、ユーザ装置Ｕの署名を正当と認める（ＳＴ２８ａ）。
上述したように本実施形態によれば、ＲＳＡ共通法誤用プロトコルを適用可能な条件のＲＳＡ暗号系において、ｎ個の機関Ｐ１  〜Ｐｎ  に秘密鍵ｄの部分情報ｓｊ  が分散されたとき、ユーザ装置Ｕが、ｔ個の機関Ｔｚを選択して暗号化データＣ１を送信し、ｔ個の各機関Ｔｚが、暗号化データＣ１（＝Ｍｅ    （ｍｏｄ  Ｎ））を演算処理して得られた部分出力Ｚｊ  をユーザ装置に返信し、ユーザ装置Ｕが、ｔ個の部分出力Ｚｊ  を合成して復号結果Ｃ２（＝ＭＬ＾２  （ｍｏｄ  Ｎ））を得ると共に、復号結果Ｃ２、処理対象データＣ１及びＲＳＡ共通法誤用プロトコルに基づいて、演算処理を実行し、最終復号結果Ｍを求める。
【０１２４】
これにより、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号を実現することができ、また、所定条件の公開鍵を用いたラグランジュ補間法に基づき、高い確実性を実現することができる。
【０１２５】
さらに、復号対象データＣ２に代えて、署名対象データＳ２（＝Ｍ）を用い、復号結果Ｃ１に代えて、署名結果Ｓ１（＝Ｍｄ Ｌ＾２（ｍｏｄ  Ｎ）、＾  はべき乗を示す記号）を用いることにより、ＲＳＡ共通法誤用プロトコルを用いて、演算処理を実行し、署名Ｍｄを求める。
【０１２６】
これにより、分散復号と同様に、分散署名を行うことができる。
すなわち、本実施形態によれば、所定の条件で公開鍵を作成することにより、ｔ個の機関の組合せとは無関係に、確実に復号処理・署名処理を実行することができる。
【０１２７】
なお、ここでノン・ディーラーモデルでの上述した機能を実現する本実施形態方式と、ディーラーモデルでの機能（（ｔ，ｎ）型での分散復号／分散署名）を実現する文献［ＦＧＭＹ９７］の方式とを比較して述べる。
【０１２８】
本実施形態方式は、文献［ＦＧＭＹ９７］の方式と同じく、α，βを係数として次の（３０）式のユークリッド公式を前提とする。
【０１２９】
ｅ  α＋Ｌ２  β＝１      …（３０）
但し、ｇｃｄ  （ｅ  ，Ｌ２  ）＝１
【数１３】
0003560860.tif 000021
【０１３０】
本実施形態方式では、復号時に部分出力Ｚｊ  を合成した後に、合成出力からユークリッドアルゴリズムによりＭを算出するので、このＭの算出処理の分だけ、文献［ＦＧＭＹ９７］の方式よりも処理効率が低下している（文献［ＦＧＭＹ９７］の方式は、ディーラーが鍵分散時にユークリッド公式を作成するので、復号時に各機関の部分出力を合成し、合成出力がメッセージＭとなる）。
【０１３１】
しかしながら、文献［ＦＧＭＹ９７］の方式は、Ｎのオイラー関数φ（Ｎ）を知るディーラーが必要であり、ｄ≡Ｐ＋Ｌ２ｋ（ｍｏｄ  φ（Ｎ））を満たすＬ  ２ｋを複数の機関に秘密分散して共有する。ここで、ディーラーが秘密鍵ｄと素因数ｐ，ｑを紛失した場合、この複数の機関から秘密鍵ｄを回復できない。理由は、Ｌ２ｋを回復しても、法φ（Ｎ）を紛失しているので、Ｌ２ｋから秘密鍵ｄを算出できないからである。但し、法φ（Ｎ）でｄに合同なＰ＋Ｌ２ｋを算出することはできる。
【０１３２】
すなわち、文献［ＦＧＭＹ９７］の方式では、ディーラーの存在する環境において、分散署名や分散復号を行えるが、ディーラーへのｄそのものの鍵回復を行えない。文献［ＦＧＭＹ９７］の方式では、鍵回復を行う際に、ディーラーモデルの文献（Ｔ．  Ｐ．  Ｐｅｄｅｒｓｅｎ，  Ｄｉｓｔｒｉｂｕｔｅｄ  ｐｒｏｖｅｒｓ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ｕｎｄｅｎｉａｂｌｅ  ｓｉｇｎａｔｕｒｅｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−Ｅｕｒｏｃｒｙｐｔ  ９１，  ＬＮＣＳ  ５４７，  ｐｐ．２２１−２３８，  １９９１．  （以下、文献［Ｐｅｄ９１ａ］という））の方式又は文献［Ｏｋａ９７］の方式といった別の方式を用いる必要がある。ここで、分散ＲＳＡ暗号系における従来方式及び本発明方式の位置づけを整理すると、各方式は、図１１に示すように分類される。
【０１３３】
一方、本発明方式は、ディーラーの存在する環境では、文献［Ｐｅｄ９１ａ］との組合せにより分散署名及び分散復号を実現でき、ディーラーの存在しない環境では、前述した通り、文献［ＦＭＹ９８］等との組合せにより分散署名及び分散復号を実現することができる。
【０１３４】
なお、上述した第１及び第２の実施形態は、ディーラーの存在しない環境の場合を述べているので、以下に、ディーラーの存在する環境に適用する場合の変形例１，２について簡単に説明する。
【０１３５】
すなわち、変形例１は、第１の実施形態をディーラーモデルに適用する場合であり、ディーラーとしてのユーザ装置Ｕは、（１３）式を満たす全ての部分秘密鍵ｄｊ，ｋ  を作成し、各機関に振り分ける作業を行う。この変形例１によれば、前述したステップＳＴ１〜ＳＴ４までの複雑な処理を省略できる分だけ、効率を向上させることができる。
【０１３６】
また、変形例２は、第２の実施形態を文献［Ｐｅｄ９１ａ］と組合せた場合であり、文献［ＦＭＹ９８］と組合せた結果と同じ機能を果たすことができる。
【０１３７】
すなわち、本発明は、（ｔ，ｎ）型の秘密分散であれば、ディーラーの有無とは無関係に実現でき、上述した各実施形態に限らず、ｎ羽の鳥のうち、任意のｔ羽の鳥を異なる巣箱に入れるような関数群（Ｋ．  Ｋｕｒｏｓａｗａ  ａｎｄ  Ｄ．  Ｓｔｉｎｓｏｎ，  Ｐｅｒｓｏｎａｌ  ｃｏｍｍｕｎｉｃａｔｉｏｎ，  Ｊｕｎｅ  １９９６  Ｒｅｆｅｒｒｅｄ  ｉｎ  Ｄｅｓｍｅｄｔｓ  ｐａｐｅｒ．  （Ｙ．  Ｄｅｓｍｅｄｔ，  Ｓｏｍｅ  ｒｅｃｅｎｔ  ｒｅｓｅａｒｃｈ  ａｓｐｅｃｔｓ  ｏｆ  ｔｈｒｅｓｈｏｌｄ  ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，  ＬＮＣＳ  １３９６，  ｐｐ．  １５８−１７３，  １９９７．  ））を適宜利用して実現することができる。
【０１３８】
尚、本発明における記憶媒体としては、磁気ディスク、フロッピーディスク、ハードディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリ等、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１３９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１４０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１４１】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１４２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１４３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１４４】
また、本発明は、ＲＳＡ暗号系に限らず、素因数分解問題に基づく暗号系であれば、ＲＳＡ暗号系以外の暗号系に適用してもよい。
その他、本発明はその要旨を逸脱しない範囲で種々変形して実施できる。
【０１４５】
【発明の効果】
以上説明したように本発明によれば、分配者の無い環境で秘密鍵を算出せずに、ｎ個の機関のうち、任意ｔ個の機関による分散復号や署名を実現し得る（ｔ，ｎ）型の秘密分散システム、装置及び記憶媒体を提供できる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図
【図２】同実施形態における各機関及びユーザ装置のハードウェア構成を示すブロック図
【図３】同実施形態における秘密分散動作を説明するためのフローチャート
【図４】同実施形態における復号化動作を説明するためのフローチャート
【図５】同実施形態における署名動作を説明するためのフローチャート
【図６】同実施形態における復号可能な例を説明するための各機関の保管情報を示す模式図
【図７】同実施形態における復号不可能な例を説明するための各機関の保管情報を示す模式図
【図８】本発明の第２の実施形態における復号化動作を説明するためのフローチャート
【図９】同実施形態における署名動作を説明するためのフローチャート
【図１０】同実施形態における変形動作を説明するためのフローチャート
【図１１】従来方式と本発明方式との位置付けを示す分類図
【図１２】従来の方式における各機関に保管される部分情報の集合を示す模式図
【図１３】従来の方式における機関の組合せと対象の部分情報を示す模式図
【符号の説明】
１…ネットワーク
Ｕ…ユーザ装置
Ｐ１  〜Ｐｎ  ，Ｐｉ  …機関
【図１】
0003560860.tif 000022
【図２】
0003560860.tif 000023
【図３】
0003560860.tif 000024
【図４】
0003560860.tif 000025
【図５】
0003560860.tif 000026
【図６】
0003560860.tif 000027
【図７】
0003560860.tif 000028
【図８】
0003560860.tif 000029
【図９】
0003560860.tif 000030
【図１０】
0003560860.tif 000031
【図１１】
0003560860.tif 000032
【図１２】
0003560860.tif 000033
【図１３】
0003560860.tif 000034