(57)【特許請求の範囲】
【請求項１】
デジタル情報処理装置からなり、第１検査記号発生手段と、第２検査記号発生手段と、訂正値算出手段と、訂正手段と、エンティティ間の通信手段とを備えた複数のエンティティにより、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正するための方法であって、
(1)  各エンティティが秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、各エンティティは、受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて、剰余Ｒic（Ｘ）をエンティティ間で通信し、剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１検査記号発生手段により第１の検査記号として発生させて記憶するステップと、
(2)  各エンティティが秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)はノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)はノイズｎiを他のエンティティに秘密にし、各エンティティは、秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２検査記号発生手段により第２の検査記号として発生させるステップと、
(3)  前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、訂正値算出手段を用いて前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求めるステップと、
(4)  秘密のデータを消失したエンティティ(i=1〜k)は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得るステップ、
とを行う秘密データの訂正方法。
【請求項２】
前記線形符号システムが巡回符号システムであることを特徴とする、請求項１の秘密データの訂正方法。
【請求項３】
前記巡回符号システムは、リードソロモン符号システムであることを特徴とする、請求項２の秘密データの訂正方法。
【請求項４】
デジタル情報処理装置からなり、第１検査記号発生手段と、第２検査記号発生手段と、訂正値算出手段と、訂正手段と、通信手段とを備えた複数のエンティティが、誤り訂正可能な線形符号システムを用いて、秘密のデータを訂正するシステムであって、
(1)  各エンティティの第１検査記号発生手段は、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、かつ受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて剰余Ｒic（Ｘ）をエンティティ間で通信し、さらにエンティティ間で通信した剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１の検査記号として発生させて記憶し、
(2)  各エンティティの第２検査記号発生手段は、秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)ではノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)ではノイズｎiを他のエンティティに秘密にし、さらに秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、通信した剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２の検査記号として発生させ、
(3)  秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(4)  秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する秘密データの訂正システム。
【請求項５】
前記線形符号システムが巡回符号システムであることを特徴とする、請求項４の秘密データの訂正システム。
【請求項６】
前記巡回符号システムは、リードソロモン符号システムであることを特徴とする、請求項５の秘密データの訂正システム。
【請求項７】
通信手段を備えたデジタル情報処理装置からなるエンティティで処理可能なプログラムであって、複数のエンティティにより、誤り訂正可能な線形符号システムを用いて、秘密のデータを訂正するために、
(1)  エンティティに第１検査記号発生手段を設けて、第１検査記号発生手段により、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、かつ受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて、剰余Ｒic（Ｘ）をエンティティ間で通信し、さらに通信した剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１の検査記号として発生させて記憶するための第１検査記号発生命令と、
(2)  エンティティに第２検査記号発生手段を設けて、第２検査記号発生手段により、秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)ではノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)ではノイズｎiを他のエンティティに秘密にし、さらに秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑirｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、通信した剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２の検査記号として発生させるための、第２検査記号発生命令と、
(3)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段により、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求めるための訂正値算出命令と、
(4)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段により、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正するための訂正命令、とを設けた秘密データの訂正用のプログラム。
【請求項８】
デジタル情報処理装置からなる複数のエンティティとセンターとから成り、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正する方法であって、
(1)  各エンティティに、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)と第１の値ｇｒi(ｇはエンティティ間で共有の数)との発生手段と、
エンティティ間で第１の値ｇｒiを通信する手段と、
受信した第１の値ｇｒiから第２の値ｇrirj(ここにｊは他のエンティティを表す添字)を求めるための手段と、
第２の値ｇrirjの直和と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めるための手段とを設けて、
秘密の数ｒiと秘密のデータＩiから求めた剰余Ｒic（Ｘ）を送信手段によりセンターへ送信し、
(2)  センターに、受信した剰余Ｒic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第１の検査記号として発生させるための手段と、
発生した第１の検査記号を各エンティティに送信する手段とを設けて、
第１の検査記号を発生させて各エンティティに送信し、
(3)  各エンティティは、受信した第１の検査記号を記憶手段により記憶し、
(4)  各エンティティに、秘密の数ｑiとノイズｎiと第３の値ｇｑiとの発生手段と、  秘密のデータを消失していないエンティティ(i=e+1〜k)では、第３の値ｇｑiとノイズｎiを送信し、秘密のデータを消失したエンティティ(i=1〜e)では第３の値ｇｑiを送信する送信手段と、
受信した第３の値ｇｑiから第４の値ｇｑiｑjを求めるための手段と、  
秘密のデータを消失していない場合、第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の法Ｇに対する剰余Ｓic（Ｘ）を求め、剰余Ｓic（Ｘ）とノイズｎiとをセンターへ送信し、秘密のデータを消失している場合、第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて剰余Ｓic（Ｘ）をセンターへ送信する手段とを設けて、
秘密の数ｑiとノイズｎiと秘密のデータを消失していないエンティティの秘密のデータＩiとから求めた剰余Ｓic（Ｘ）をセンターへ送信し、
(5)  センターに、受信した剰余Ｓic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第２の検査記号として発生させて、各エンティティに送信するための手段を設けて、受信した剰余Ｓic（Ｘ）から第２の検査記号を発生させて各エンティティに送信し、
(6)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(7)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する、秘密データの訂正方法。
【請求項９】
デジタル情報処理装置からなる複数のエンティティとセンターとから成り、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正するシステムであって、
(1)  各エンティティに、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)と第１の値ｇｒi(ｇはエンティティ間で共有の数)との発生手段と、
エンティティ間で第１の値ｇｒiを通信する手段と、
受信した第１の値ｇｒiから第２の値ｇrirj(ここにｊは他のエンティティを表す添字)を求めるための手段と、
第２の値ｇrirjの直和と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めるための手段とを設けて、
求めた剰余Ｒic（Ｘ）を送信手段によりセンターへ送信し、
(2)  センターに、受信した剰余Ｒic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第１の検査記号として発生させるための手段と、
発生した第１の検査記号を各エンティティに送信する手段とを設けて、
(3)  各エンティティは、受信した第１の検査記号を記憶手段により記憶し、
(4)  各エンティティに、秘密の数ｑiとノイズｎiと第３の値ｇｑiとの発生手段と、  秘密のデータを消失していないエンティティ(i=e+1〜k)では、第３の値ｇｑiとノイズｎiを送信し、秘密のデータを消失したエンティティ(i=1〜e)では第３の値ｇｑiを送信する送信手段と、
受信した第３の値ｇｑiから第４の値ｇｑiｑjを求めるための手段と、  
秘密のデータを消失していない場合、第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の法Ｇに対する剰余Ｓic（Ｘ）を求め、剰余Ｓic（Ｘ）とノイズｎiとをセンターへ送信し、秘密のデータを消失している場合、第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて剰余Ｓic（Ｘ）をセンターへ送信する手段とを設けて、
求めた剰余Ｓic（Ｘ）をセンターへ送信し、
(5)  センターに、受信した剰余Ｓic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第２の検査記号として発生させて、各エンティティに送信するための手段を設け、
(6)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(7)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する、秘密データの訂正システム。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
この発明は、複数のエンティティが保持する秘密のデータを復元あるいは訂正することに関し、特に他のエンティティに自己の秘密データを知られずに復元あるいは訂正することに関する。
【０００２】
【従来技術】
パスワード等のエンティティの秘密のデータを、エンティティが紛失したりした場合、パスワードの訂正や復元は困難である。センターがパスワードを管理して再発行することも可能ではあるが、センターの信頼性や、センターとエンティティとの秘密通信の信頼性に問題がある。
【０００３】
【発明の課題】
この発明の課題は、他のエンティティに自己の秘密データを知られずに、秘密データを訂正することにある。
この発明は特に、消失した秘密データを他のエンティティに知られずに復元させることを課題とする。
【０００４】
【用語法】
この発明では、検査記号を発生あるいは記憶するとは、必ずしも検査記号の全体を発生あるいは記憶することを意味せず、例えば検査記号の一部を発生させて記憶すること、検査記号やその一部に変換可能なデータを発生させて記憶することをも含んでいる。これは秘密データの訂正は、複数のエンティティの協力で行うことがことができ、例えば各エンティティが検査記号の全体を記憶するか、その一部のみを記憶して通信等により検査記号の全体を得るかは、全く同等な事項だからである。
【０００５】
【発明の構成】
この発明の秘密データの訂正方法では、デジタル情報処理装置からなり、第１検査記号発生手段と、第２検査記号発生手段と、訂正値算出手段と、訂正手段と、エンティティ間の通信手段とを備えた複数のエンティティにより、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正するための方法であって、
(1)  各エンティティが秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、各エンティティは、受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて、剰余Ｒic（Ｘ）をエンティティ間で通信し、剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１検査記号発生手段により第１の検査記号として発生させて記憶するステップと、
(2)  各エンティティが秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)はノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)はノイズｎiを他のエンティティに秘密にし、各エンティティは、秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２検査記号発生手段により第２の検査記号として発生させるステップと、
(3)  前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、訂正値算出手段を用いて前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求めるステップと、
(4)  秘密のデータを消失したエンティティ(i=1〜k)は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得るステップ、
とを行う。
【０００６】
好ましくは、前記線形符号システムが巡回符号システムである。
特に好ましくは、前記巡回符号システムは、リードソロモン符号システムである。
【０００７】
この発明の秘密データの訂正システムでは、デジタル情報処理装置からなり、第１検査記号発生手段と、第２検査記号発生手段と、訂正値算出手段と、訂正手段と、通信手段とを備えた複数のエンティティが、誤り訂正可能な線形符号システムを用いて、秘密のデータを訂正するシステムであって、
(1)  各エンティティの第１検査記号発生手段は、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、かつ受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて剰余Ｒic（Ｘ）をエンティティ間で通信し、さらにエンティティ間で通信した剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１の検査記号として発生させて記憶し、
(2)  各エンティティの第２検査記号発生手段は、秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)ではノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)ではノイズｎiを他のエンティティに秘密にし、さらに秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、通信した剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２の検査記号として発生させ、
(3)  秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(4)  秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する。
【０００８】
この発明の秘密データの訂正用のプログラムは、通信手段を備えたデジタル情報処理装置からなるエンティティで処理可能なプログラムであって、複数のエンティティにより、誤り訂正可能な線形符号システムを用いて、秘密のデータを訂正するために、
(1)  エンティティに第１検査記号発生手段を設けて、第１検査記号発生手段により、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)を発生させて、エンティティ間で第１の値ｇｒi(i=１〜k)(ｇはエンティティ間で共有の数)を通信し、かつ受信した第１の値ｇｒiから求めた第２の値ｇrirjの直和(ここにｊは他のエンティティを表す添字)と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めて、剰余Ｒic（Ｘ）をエンティティ間で通信し、さらに通信した剰余Ｒic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第１の検査記号として発生させて記憶するための第１検査記号発生命令と、
(2)  エンティティに第２検査記号発生手段を設けて、第２検査記号発生手段により、秘密の数ｑiとノイズｎiとを発生させて、エンティティ間で第３の値ｇｑi(i=１〜k)を通信すると共に、秘密のデータを消失していないエンティティ(i=e+1〜k)ではノイズｎiを他のエンティティへ送信することにより公開し、秘密のデータを消失したエンティティ(i=1〜e)ではノイズｎiを他のエンティティに秘密にし、さらに秘密のデータを消失していない場合、受信した第３の値ｇｑiから求めた第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の、法Ｇに対する剰余Ｓic（Ｘ）を求め、秘密のデータを消失している場合、受信した第３の値ｇｑiから求めた第４の値ｇｑirｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて、いずれの場合も剰余Ｓic（Ｘ）をエンティティ間で通信し、通信した剰余Ｓic（Ｘ）のエンティティに渡る直和の法Ｇに対する剰余を、第２の検査記号として発生させるための、第２検査記号発生命令と、
(3)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段により、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求めるための訂正値算出命令と、
(4)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段により、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正するための訂正命令、とを設けたものである。
【０００９】
この発明の秘密データの訂正方法は、デジタル情報処理装置からなる複数のエンティティとセンターとから成り、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正する方法であって、
(1)  各エンティティに、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)と第１の値ｇｒi(ｇはエンティティ間で共有の数)との発生手段と、
エンティティ間で第１の値ｇｒiを通信する手段と、
受信した第１の値ｇｒiから第２の値ｇrirj(ここにｊは他のエンティティを表す添字)の直和を求めるための手段と、
第２の値ｇrirjの直和と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めるための手段とを設けて、
秘密の数ｒiと秘密のデータＩiから求めた剰余Ｒic（Ｘ）を送信手段によりセンターへ送信し、
(2)  センターに、受信した剰余Ｒic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第１の検査記号として発生させるための手段と、
発生した第１の検査記号を各エンティティに送信する手段とを設けて、
第１の検査記号を発生させて各エンティティに送信し、
(3)  各エンティティは、受信した第１の検査記号を記憶手段により記憶し、
(4)  各エンティティに、秘密の数ｑiとノイズｎiと第３の値ｇｑiとの発生手段と、  秘密のデータを消失していないエンティティ(i=e+1〜k)では、第３の値ｇｑiとノイズｎiを送信し、秘密のデータを消失したエンティティ(i=1〜e)では第３の値ｇｑiを送信する送信手段と、
受信した第３の値ｇｑiから第４の値ｇｑiｑjを求めるための手段と、  
秘密のデータを消失していない場合、第４の値ｇｑiｑjの直和と自己の秘密のデータＩiとの直和の法Ｇに対する剰余Ｓic（Ｘ）を求め、剰余Ｓic（Ｘ）とノイズｎiとをセンターへ送信し、秘密のデータを消失している場合、第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて剰余Ｓic（Ｘ）をセンターへ送信する手段とを設けて、
秘密の数ｑiとノイズｎiと秘密のデータを消失していないエンティティの秘密のデータＩiとから求めた剰余Ｓic（Ｘ）をセンターへ送信し、
(5)  センターに、受信した剰余Ｓic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第２の検査記号として発生させて、各エンティティに送信するための手段を設けて、受信した剰余Ｓic（Ｘ）から第２の検査記号を発生させて各エンティティに送信し、
(6)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(7)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する。
【００１０】
この発明の秘密データの訂正システムは、デジタル情報処理装置からなる複数のエンティティとセンターとから成り、誤り訂正可能な線形符号システムを用いて、エンティティの秘密のデータを訂正するシステムであって、
(1)  各エンティティに、秘密の数ｒi(i=１〜ｋ：iは個々のエンティティを表す添字で、kはエンティティの数を表す)と第１の値ｇｒi(ｇはエンティティ間で共有の数)との発生手段と、
エンティティ間で第１の値ｇｒiを通信する手段と、
受信した第１の値ｇｒiから第２の値ｇrirj(ここにｊは他のエンティティを表す添字)の直和を求めるための手段と、
第２の値ｇrirjの直和と自己の秘密のデータＩiとの直和の、エンティティ間で共有の法Ｇに対する剰余Ｒic（Ｘ）を求めるための手段とを設けて、
求めた剰余Ｒic（Ｘ）を送信手段によりセンターへ送信し、
(2)  センターに、受信した剰余Ｒic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第１の検査記号として発生させるための手段と、
発生した第１の検査記号を各エンティティに送信する手段とを設けて、
(3)  各エンティティは、受信した第１の検査記号を記憶手段により記憶し、
(4)  各エンティティに、秘密の数ｑiとノイズｎiと第３の値ｇｑiとの発生手段と、  秘密のデータを消失していないエンティティ(i=e+1〜k)では、第３の値ｇｑiとノイズｎiを送信し、秘密のデータを消失したエンティティ(i=1〜e)では第３の値ｇｑiを送信する送信手段と、
受信した第３の値ｇｑiから第４の値ｇｑiｑjを求めるための手段と、  
秘密のデータを消失していない場合、第４の値ｇｑiｑjの直和と自己の秘密のデータＩiの直和の法Ｇに対する剰余Ｓic（Ｘ）を求め、剰余Ｓic（Ｘ）とノイズｎiとをセンターへ送信し、秘密のデータを消失している場合、第４の値ｇｑiｑjの直和の法Ｇに対する剰余Ｓic（Ｘ）を求めて剰余Ｓic（Ｘ）をセンターへ送信する手段とを設けて、
求めた剰余Ｓic（Ｘ）をセンターへ送信し、
(5)  センターに、受信した剰余Ｓic（Ｘ）のエンティティに渡る直和を求めて、求めた直和の法Ｇに対する剰余を第２の検査記号として発生させて、各エンティティに送信するための手段を設け、
(6)  エンティティに訂正値算出手段を設けて、秘密のデータを消失したエンティティの訂正値算出手段は、前記第１の検査記号と前記第２の検査記号との線形結合から第３の検査記号を求めると共に、該第３の検査記号を検査記号とし前記公開のノイズｎi(i=e+1〜k)を情報部分の一部とする符号語を、前記線形符号システムにより誤り訂正して、前記ノイズへの訂正値ｎi＋Ｉi(i=1〜e)を求め、
(7)  エンティティに訂正手段を設けて、秘密のデータを消失したエンティティの訂正手段は、訂正値ｎi＋Ｉiとノイズｎiとから、秘密のデータＩiを得ることにより消失した秘密データを訂正する。
【００１１】
【発明の作用と効果】
この発明では、パスワードや秘密鍵等をエンティティの秘密データと見なし、複数のエンティティの秘密データのセットを線形符号システムでの情報部分もしくは情報ブロックと見なす。これらの秘密データは、パスワードや秘密鍵等、エンティティにとって固定的なものが好ましい。この発明で線形符号システムを用いるのは、符号の線形性を用いるためである。線形符号システムは誤り訂正可能なものとし、好ましくは消失誤り訂正可能なものとし、特に好ましくは扱いやすい巡回符号システムとし、最も好ましくは実装が容易で効率の高いリードソロモン符号システムとする。特に好ましくは、組織的リードソロモン符号システムとする。そして線形符号システムでの線形符号は、情報部分や情報ブロックとそれに対する検査記号とで構成されている。
【００１２】
この発明では、秘密データの訂正の準備として、各エンティティがパスワードや秘密鍵等を定めた時点等で、第１の検査記号を発生させる。この検査記号はエンティティの秘密データのセットに対する線形符号システムでの検査記号である。以下この検査記号を第１の検査記号という。
【００１３】
次に秘密データの訂正が必要になった時点等で、各エンティティが保有する秘密データにノイズを加えたデータのセットを、同じ線形符号システムでの情報部分と見なして、第２の検査記号を発生させる。ここで秘密データを消失したエンティティは、秘密データを保有していないので、ノイズのみを自己のデータとする。
【００１４】
第１の検査記号を発生させた時点での秘密データのセットに第１の検査記号を付加した符号も、秘密データの訂正のために、秘密データにノイズを加えたデータのセットに第２の検査記号を付加した符号も、共に同じ線形符号システムの符号語である。従ってこれらの符号語の線形結合も同じ線形符号システムの符号語となる。第１の検査記号を発生させた時点の符号語と、第２の検査記号を発生させた時点の符号語の線形結合を考える。この線形結合での検査記号を第３の検査記号とすると、その情報部分には、第２の検査記号の発生時に各エンティティが加えたノイズが表れるようにできる。ここで誤り訂正の線形符号システムを用いているので、各エンティティが加えたノイズに対して誤り訂正を行うことができる。
【００１５】
各エンティティは、自己が加えたノイズに対する訂正値を受け取り、秘密のノイズを知っているので、自己の秘密データを訂正できる。当該エンティティ以外の他のエンティティに判明するのは、他のエンティティのノイズへの訂正値である。従って他のエンティティに対しては秘密のままで、各エンティティは自己の秘密データを訂正できる。
【００１６】
この発明で特に重要なのは、パスワードや秘密鍵等の秘密データをエンティティが消失あるいは忘れた際に、これらを復元することである。そのためには第２の検査記号の発生時に、自己の秘密データを消失したエンティティは、ノイズを自己のデータとし、自己のノイズへの訂正値を受け取る。自己のノイズと受け取ったノイズの訂正値との差は、消失した秘密データに変換できる。このようにして、秘密データを失ったエンティティが、秘密データを他のエンティティに知られずに、秘密データを復元できる。
【００１７】
秘密データの訂正と復元との差異は、一般的に、データの訂正ではどのエンティティのデータにエラーがあるのかが不明であるのに対して、データの復元では、データを復元する必要のあるエンティティが既知で、他のエンティティのデータはエラーを含んでいないと仮定し得る点である。ただしこの明細書で、訂正は一般に復元を含むものとする。
【００１８】
この発明での秘密データの訂正や復元は、各エンティティ間の協力で行うことができ、特に信頼性のあるセンターを必要としない(請求項１〜７)。
【００１９】
【実施例】
図１〜図７に実施例とその変形とを示す。図１は復元用データの準備時のエンティティ間の通信を示し、Ｅ1〜Ｅkはエンティティで、Ｉ1〜ＩkはエンティティＥ1〜Ｅkの秘密データで、例えばここではパスワードとする。エンティティの人数はk人で、添え字iは個々のエンティティを表し、添え字jは他のエンティティや、エンティティ全体等を表す場合に用いる。エンティティＥ1〜Ｅkは通信路２により結ばれ、通信路２は例えば公開の通信路とする。各エンティティＥ1〜Ｅkは、図１〜図６に示す秘密データの訂正を実現できる程度のデジタル情報処理装置を備えているものとする。実施例では各エンティティＥ1〜Ｅkが、第１検査記号発生手段、第２検査記号発生手段、訂正値算出手段、訂正値を用いたパスワードの復元用の訂正手段、エンティティ間の通信手段を備えているものとする。
【００２０】
エンティティＥ1〜Ｅkは、パスワードＩ1〜Ｉkを定めたときに、第１の検査記号Ｒ(Ｘ)を発生させる。パスワードＩ1〜Ｉkのセット(Ｉ1,Ｉ2,…,Ｉk)は、組織的リードソロモン符号の情報ブロックであるものとし、これに対する検査記号Ｒ(Ｘ)を発生させる。なおここでは検査記号を多項式表現するが、多項式表現に限るものではない。個々のパスワードＩ1〜Ｉkはガロワ体Ｆ(2m)上の元と見なし、ガロワ体Ｆ(2m)がリードソロモン符号での符号アルファベットをなすものとする。またリードソロモン符号は、Ｆ(2m)上の多項式Ｇ(Ｘ)＝(Ｘ−α)(Ｘ−α2)…(Ｘ−αh)により生成されるものとする。なお以下では、多項式演算は生成多項式Ｇ(Ｘ)による剰余演算を伴うものとする。パスワードのセット(Ｉ1〜Ｉk)に対する復元用データ(第１の検査記号)は、
Ｒ(Ｘ)≡Ｉ1・Ｘh＋Ｉ2・Ｘh+1＋…＋Ｉk・Ｘh+k-1  mod  Ｇ(Ｘ)
で与えられる。この多項式の次数は h-1で、(Ｉ1,Ｉ2,Ｉ3,…,Ｉk,Ｒ(Ｘ))は最小距離 h+1のリードソロモン符号である。
【００２１】
ここで第１の検査記号Ｒ(Ｘ)の性質を検討すると、ｋ個のパスワードＩiのうち、h-1 個までが消失しても復元可能である。これは最小距離 h+1 のリードソロモン符号の訂正距離よりも長いように見えるが、パスワードの消失の場合、どのエンティティのパスワードが失われているかが判明しており、しかもそれ以外のエンティティのパスワードは正しいものと仮定し得るので、h-1 個までのパスワードを復元可能である。パスワードの復元ではなく訂正を行う場合、誤り訂正が可能なエンティティの人数は(h+1)／２となる。次にエンティティの人数kが前記のhよりも小さい場合、検査記号Ｒ(Ｘ)からパスワードＩ1〜Ｉkが露呈する。これに対してエンティティの人数kがh以上の場合、第１の検査記号Ｒ(Ｘ)からはパスワードは露呈しない。
【００２２】
エンティティＥ1〜Ｅkは協力して、第１の検査記号Ｒ(Ｘ)を生成する。この時、自己のパスワードＩiを元に検査記号の一部Ｒi(Ｘ)を生成し、これを他のエンティティに送信して加算すれば、第１の検査記号Ｒ(Ｘ)を生成できる。即ちＲi(Ｘ)からＲ(Ｘ)への変換は、Ｒ(Ｘ)≡Σ(i=1〜k)Ｒi(Ｘ)となる。また
Ｒi(Ｘ)≡Ｉi・Ｘ(h+i-1)  mod  Ｇ(Ｘ)となる。Ｒi(Ｘ)は、１人のエンティティに対して、h-1人までのデータが消失した際に復号可能な符号の復元用データとしての性質を有するので、Ｒi(Ｘ)をこのまま通信路２で他のエンティティに送信すると、パスワードＩiが露呈する。
【００２３】
ディフィーヘルマン方式の鍵共有を行い、各エンティティＥiは一時的に使用する自己の秘密の乱数ｒiを生成し、ｍｈよりも絶対値の大きな素数Ｐを用いてガロワ体ＧＦ(Ｐ)を生成し、その原始元ｇを用いて、ｇriを生成する。そして各エンティティＥiは、ｇriを他のエンティティに送信する。エンティティＥiは他のエンティティから｛ｇrj｝を受信し、
Ｒic (Ｘ)≡Ｒi(Ｘ)＋Σ(j≠i j=1〜k)ｇrirj(Ｘ)  を求める。ｇrirj(Ｘ)はｇrjriの上位ｍｈ桁を多項式表現したものである。なおここでは、エンティティＥiは、自分以外の全ての他のエンティティからｇrjを受信するものとしているが、通信量を減らすためには、例えば左右両隣との間でのみｇri等を交換するようにしても良い。この場合ｇriを交換する範囲を狭めると、エンティティ間の結束により、Ｒi(Ｘ)が露呈する可能性が増す。なおここまでで、原始元ｇや素数Ｐは、各エンティティ間で共有されているものとする。
【００２４】
エンティティＥiはＲic(Ｘ)を通信路２で送信し、各エンティティは受信したＲjc(Ｘ)から  Ｒ(Ｘ)≡Σ(j=1〜k)Ｒjc(Ｘ)として、第１の検査記号Ｒ(Ｘ)を生成する。ここで加算演算は直和演算であり、同じ項ｇrirj(Ｘ)を２回加算すると、０になる。即ち、ｇrirj(Ｘ)はエンティティＥiがＲic(Ｘ)を生成した際と、エンティティＥjがＲjc(Ｘ)を生成した際に２度用いられており、これらのものを加算した場合、２回表れるので０となる。このようにして各エンティティＥiは、自己のパスワードＩiを秘密に保ち、復元用のデータとしてＲ(Ｘ)を記憶する。
【００２５】
図２に、パスワードの復元を示す。簡単のために、e人のエンティティＥ1〜Ｅeがパスワードを忘れ、残るエンティティＥe+1〜Ｅkはパスワードを記憶しているものとする。そしてパスワードを記憶しているエンティティＥe+1〜Ｅkは、パスワードの復元に協力するものとする。なおパスワードの復元に協力しないエンティティが存在した場合、そのエンティティはパスワードが消失したものと見なして、パスワードの生成に必要なＳic(Ｘ)を他のエンティティが代行して生成すれば、一部のエンティティがパスワードの復元に協力しない場合でも、パスワードを復元できる。
【００２６】
パスワードを消失したエンティティＥ1〜Ｅeは、ガロワ体Ｆ(2m)上の元を適宜に選んでノイズｎiとし、これを自己の秘密データとする。パスワードを記憶しているエンティティも同様にガロワ体Ｆ(2m)の元ｎiをノイズとして用い、これを公開データとする。各エンティティは前記の乱数ｒiと同様の乱数ｑiを選び、前記と同様の手順によってｇqiを他のエンティティに送信し、他のエンティティから受信した｛ｇqj｝を用いて、Σ(j≠i j=1〜k)ｇqiqj(Ｘ)を生成する。またパスワードを消失したエンティティは、ノイズから成る秘密データｎiに対する検査記号Ｓi(Ｘ)を発生させ、Ｓi(Ｘ)に前記のΣ(j≠i j=1〜k)ｇqjqi(Ｘ)を加算したものを、送信データ  Ｓic(Ｘ)として他のエンティティ(j≠i j=1〜k)に送信する。
【００２７】
パスワードを記憶しているエンティティは、自己のパスワードＩiに公開ノイズｎiを加算したものに対する検査記号をＳi(Ｘ)とし、これに同様にして
Σ(j≠i j=1〜k)ｇqjqi(Ｘ)を加算したものをＳic(Ｘ)とし、Ｓic(Ｘ)とｎiとを送信する。
【００２８】
パスワードを忘れたエンティティは、Ｓjc(Ｘ)(j=1〜k)が揃うので、これらを加算することにより、第２の検査記号Ｓ(Ｘ)を生成する。また第１の検査記号Ｒ(Ｘ)は、それ自体としてはパスワードを露呈しないデータなので、例えば電子的に記憶されているものとする。さらにこのエンティティは、パスワードを記憶しているエンティティのノイズｎe+1〜ｎkを受信している。
【００２９】
第１の検査記号Ｒ(Ｘ)を生成した時点で、(Ｉ1,Ｉ2,Ｉ3,…,Ｉk,Ｒ(Ｘ))はリードソロモン符号システムでの符号語である。この符号語を符号語Ａと呼ぶ。次にパスワードの復元を行う時点で、
(ｎ1,ｎ2,…,ｎe,ｎe+1＋Ｉe+1,ｎe+2＋Ｉe+2,…,ｎk＋Ｉk,Ｓ(Ｘ))もリードソロモン符号システムでの符号語で、この符号語を符号語Ｂと呼ぶ。これらを直和演算により加算した
(ｎ1＋Ｉ1,ｎ2＋Ｉ2,…,ｎe＋Ｉn,ｎe+1,ｎe+2,…,ｎk,Ｒ(Ｘ)＋Ｓ(Ｘ))も、リードソロモン符号が線形符号であることから、同じ符号システムでの符号語で、これを符号語Ｃと呼ぶ。各エンティティは、図２で受信したデータを用いて、符号語Ｃの一部を生成でき、検査記号Ｒ(Ｘ)＋Ｓ(Ｘ)で一意に復元できる。パスワードを消失したエンティティＥ1〜Ｅeは、元のパスワードＩi＋ｎiを符号語Ｃから得、秘密のノイズｎiを除いて、パスワードＩiを復元できる。パスワードの復元に協力したエンティティＥe+1〜Ｅkについて、符号語Ｃ中でのデータはノイズのみで、これからパスワードを復元することはできない。次にパスワードを消失したエンティティ以外のエンティティには、他のエンティティのデータｎi＋Ｉi中のノイズｎiが不明なため、パスワードＩiを復元できない。このようにして他のエンティティに知られずに、消失したパスワードを復元できる。
【００３０】
図３,図４に、第１の検査記号Ｒ(Ｘ)の生成手続を示し、これを実行するための手段を第１検査記号発生手段として、各エンティティに設ける。Ｆ(2m)をガロワ体とし、パスワードのセット(Ｉ1,Ｉ2,…,Ｉk)をＦ(2m)の元のセットと見なす。続いてリードソロモン符号の生成多項式として、Ｆ(2m)上の多項式Ｇ(Ｘ)を準備する。このようにしてパスワードＩi〜Ｉkを定めた際に、パスワード系データ４を生成する。復元用データの準備データ６として、絶対値がｍｈ以上の素数Ｐを選び、ガロワ体ＧＦ(Ｐ)を生成し、ｇをその原始元として、各エンティティの秘密の乱数ｒj(j=1〜k)に対してｇrjを生成し、他のエンティティに送信する。但し自己の乱数ｒi自体は秘密とする。なお図３,図５において、斜線を付した範囲は秘密データを意味する。各エンティティは、受信したｇrjを用いて検査記号Ｒi(Ｘ)を暗号化したＲic(Ｘ)を生成し、これを互いに送信する。続いて各エンティティは、自己のＲic(Ｘ)に受信したＲj(Ｘ)を加算し、検査記号Ｒ(Ｘ)を生成する。前記のように、Ｒjc(Ｘ)の加算の過程で、ｇrjri(Ｘ)は同じ項が２回表れるので、直和演算により０となる。このようにして検査記号Ｒ(Ｘ)の生成８を行う。
【００３１】
図４に、復元用データＲ(Ｘ)の生成アルゴリズムを示す。各エンティティは、ステップ１で自己のパスワードＩiに対してＩiＸ(h+i-1)  mod  Ｇ(Ｘ)を求め、これをＲi(Ｘ)とする。ステップ２で各エンティティに共通のガロワ体ＧＦ(Ｐ)の共通の原始元ｇを用い、秘密の乱数ｒiによりｇriを生成する。そして各エンティティは自己のｇriを他のエンティティに送信する。
【００３２】
ステップ３で各エンティティは、受信したｇrj(j=1〜k,j≠i)を用いて、
Σ(j≠i j=1〜k)ｇｒjｒi(Ｘ)＋Ｒi(Ｘ)を演算し、これをＲic(Ｘ)としてエンティティ間で送信する。ステップ４で各エンティティは受信したＲjc(Ｘ)より、
Σ(j=1〜k)Ｒjc(Ｘ)を演算し、Ｇ(Ｘ)の剰余を求めて、第１の検査記号Ｒ(Ｘ)として記憶する。
【００３３】
図５,図６に、消失したパスワードＩ1〜Ｉeの復元を示す。図５のパスワード復元時の状況データ１０には、記憶している第１の検査記号Ｒ(Ｘ)と素数Ｐ及び原始元ｇがあり、パスワードＩ1〜Ｉeは消失しており、パスワードＩe+1〜Ｉkは保存されている。
【００３４】
各エンティティはノイズｎjと乱数ｑjを生成し、ｇqjをエンティティ間で通信すると共に、ノイズｎi(i=1〜e)はエンティティＥiの秘密とし、ノイズｎjをエンティティ間で通信する(j=e+1〜ｋ)。また乱数ｑi(i=1〜k)もエンティティＥiの秘密とする。このようにして乱数の発生と通信処理１２を行う。パスワードの復元処理１４では、Ｒi(Ｘ)からＲic(Ｘ)への変換と全く同様にして、Ｓi(Ｘ)に
Σ(j≠i j=1〜k) ｇqjqi(Ｘ)を加算し、Ｓic(Ｘ)とする。ここにＳi(Ｘ)は各エンティティの秘密であり、パスワードを消失したエンティティにとっては、
Ｓi(ｘ)≡ｎi・Ｘ(h+i-1)  mod  Ｇ(Ｘ)であり、
パスワードを保持しているエンティティにとっては、
Ｓi(ｘ)≡(ｎi＋Ｉi)・Ｘ(h+i-1)  mod  Ｇ(Ｘ)である。各エンティティが自己の  Ｓic(Ｘ)に受信したＳjc(Ｘ)を加算すると、Ｓ(Ｘ)を得ることができる。
Ｓ(Ｘ)の算出を実行するための手段を第２検査記号発生手段とし、各エンティティに設ける。
【００３５】
e個の記号が消失した符号語として、(ｎe+1,ｎe+2,…,ｎk,Ｒ(Ｘ)＋Ｓ(Ｘ))を考えると、その消失部は、誤り訂正により、j=1〜eに対して、ｎj＋Ｉjで与えられる。ｎj＋Ｉjを算出するための手段を訂正値算出手段とし、各エンティティに設ける。ｎj＋Ｉj中のｎjはｊ番目のエンティティにとっては既知で、これ以外のエンティティにとっては秘密なので、当該エンティティのみが自己のパスワードＩjを復元できる。ｎj＋ＩjをＩjに変換するための手段を訂正手段とし、これも各エンティティに設ける。
【００３６】
図６にパスワードの復元アルゴリズムを示す。ステップ１０で各エンティティは乱数ｑiとノイズｎiを生成し、ｇqiをエンティティ間で通信し、ｎ1〜ｎeを秘密にし、ｎe+1〜ｎkをエンティティ間で通信する。ステップ１１で各エンティティをＳi(Ｘ)を求め、ステップ１２でＳi(Ｘ)を暗号化してＳic(Ｘ)としＳic(Ｘ)をエンティティ間で送信する。ステップ１３で、各エンティティはＳjc(Ｘ)を加算し、第２の検査記号Ｓ(Ｘ)を生成する。
【００３７】
これから符号語の一部(ｎe+1,ｎe+2,…,ｎk,Ｒ(Ｘ)＋Ｓ(Ｘ))が得られ、消失したパスワードの個数eが復元可能範囲 h-1 以下であれば、消失した符号ｎi＋Ｉiを復元できる。ここにi=1〜eである。そしてノイズｎiを知っているのは、i番目のエンティティＥiのみなので、このエンティティのみが自己のパスワードＩiを復元できる。
【００３８】
図７に、センター２０を用いた変形例を示す。センター２０は各エンティティＥ1〜Ｅkと通信し、各エンティティはＲiｃ(Ｘ)をセンター２０に送信し、センター２０はこれらの加算値Ｒ(Ｘ)を各エンティティに返信する。データの復元時には、各エンティティはＳic(Ｘ)と、パスワードを消失していないエンティティのノイズｎiとをセンターに送信し、センター２０は各エンティティにＳ(Ｘ)とi=e+1〜ｋについてノイズｎiの値を返信する。このようにセンター２０を介在させてパスワードを復元させても良いが、実施例では、信頼性のあるセンターを設ける必要がなく、仮に一部のエンティティが結託あるいは非協力的な態度をとっても、パスワードの復元ができる。また検査記号の暗号化の手法は任意で、検査記号を加算することにより復号できるものであればよい。
【００３９】
パスワードＩ1〜Ｉkは、線形符号システム(実施例ではリードソロモン符号システム)で誤り訂正なフォーマットで表現されていれば良く、ガロワ体の元には限らない。例えばガロワ体Ｆ(2m)上のｕ次ベクトル空間の元で、パスワードＩ1〜Ｉkが構成されているとする。その場合１個のパスワードが失われると、ｕ個のデータが失われたものと見なす必要があり、リードソロモン符号システムでの訂正可能範囲ｈもｕ倍するする必要がある。
【００４０】
パスワードＩ1〜Ｉkをガロワ体Ｆ(2m)上のｕ次ベクトル空間の元とすると、Ｘを不定元とする多項式表現で、
Ｉi＝Ｉi0＋Ｉi1・Ｘ＋Ｉi2・Ｘ２＋…＋Ｉi(u-1)Ｘu-1 (i＝１〜ｋ)
となり、最高次の次数がｕ−１次の多項式となる。これに対応して検査記号
Ｒ(Ｘ)も、
Ｒ(Ｘ)＝Ｉ1・Ｘh＋Ｉ2・Ｘh+u ＋…＋Ｉk・Ｘh+u(k-1) 
となる。ここでｅ個のパスワードが消失すると、Ｆ(2m)のｅｕ個の元が失われたと見なすことができ、誤り訂正能力  ｈ−１≧ｅｕ  で、ｅ個のパスワードを復活させることができる。
【００４１】
検査記号を分散して、各エンティティが保有することを検討してみよう。例えば検査記号の誤り訂正能力を増すと、検査記号を元にパスワードを盗まれる可能性が増加する。これに対して検査記号を複数に分散して、検査記号に関する部分的なデータをエンティティに分配すると、検査記号自体の秘匿性が増す。言い換えると、各エンティティは検査記号全体にはアクセスできず、複数のエンティティの協力によって検査記号が得られるようにする。例えば検査記号を複数の部分に分解して、各部分をエンティティに分配しても良く、あるいは検査記号を暗号化したものを複数の部分に分解して、各部分をエンティティに分配しても良い。このようにすると、検査記号の誤り訂正能力を増しても、パスワードの秘匿性が低下しない。このような例として、エンティティの人数(パスワードの個数)ｋとリードソロモン符号での誤り訂正能力ｈ−１とが等しい例を考える。この例では検査記号が手にはいると、ｋ個のパスワードを全数再生できる。
【００４２】
リードソロモン符号の生成多項式Ｇ(Ｘ)をｈ次の多項式とし、ｋ人のエンティティのパスワードをＩ1〜Ｉkとする。ｋ個のパスワード(Ｉ1,Ｉ2,…,Ｉk)をリードソロモン符号の情報部分と見なした際の検査記号を(Ｒ1,Ｒ2,…,Ｒk)とすると、各エンティティが、検査記号(Ｒ1,Ｒ2,…,Ｒk)の一部のみにしかアクセスできないようにして、検査記号を発生させることができれば、問題は解決する。なお誤り訂正能力ｈ−１とエンティティの数ｋとが等しいとしたので、検査記号はｋ−１次の多項式の係数で構成され、このため検査記号は情報部分と同じ次数となる。また各エンティティは、検査記号中のアクセス可能な部分のみを記憶する。簡単のために、エンティティiは、パスワードＩiと検査記号の一部Ｒiとの直積(Ｉi,Ｒi)を、他のエンティティに秘密に記憶するものとする。
【００４３】
Ｉi・Ｘk+i-1 ≡Ｑi(Ｘ)  modＧ(Ｘ)
としてＱi(Ｘ)を求め、
Ｑi(Ｘ)＝Ｑi,k・Ｘｋ−１＋Ｑi,k-1・Ｘｋ−２＋…＋Ｑi,1・Ｘ０
と表記する。前記と同様にしてエンティティＡiはｇri(riは乱数，ｇはガロワ体ＧＦ(Ｐ)の原始元)を他のエンティティＡj(j=1〜k,j≠i)に送信し、同時にｇrjを受信し、Ｑi,j＋(ｇrj)ri を送信する。エンティティＡiは他のエンティティＡj
(j=1〜k,j≠i)からＱj,i＋(ｇrｊ)ri を受信し、これらの総和
Ｒiｃ＝Σ(ｊ＝１〜ｋ,ｊ≠i)(Ｑj,i＋(ｇrj)ri)を導く。Σ(ｊ＝１〜ｋ,ｊ≠i)(ｇrｊ)ri  はエンティティＡiには既知であり、  Ｒi＝Ｒiｃ＋Ｒi,i＋Σ(ｊ＝１〜ｋ,ｊ≠i)(ｇrj)ri  を導く。このＲiは、ｋ個のパスワード(Ｉ1,Ｉ2,…,Ｉk)に対する検査記号(Ｒ1,Ｒ2,…,Ｒk)のi番目の要素であり、エンティティＡiは(Ｉi,Ｒi)を秘密に記憶する。ここでＩiはパスワード、Ｒiは検査記号の要素である。このようにして、検査記号
Ｒ＝(Ｒ1,Ｒ2,…,Ｒk)を秘密にしたまま、各エンティティがその一部のみを保有することができる。なおここではエンティティの数ｋと検査記号Ｒでの要素の数が等しいとしたので、各エンティティが検査記号の１要素を記憶することにしたが、エンティティの数ｋと検査記号Ｒでの要素の数ｈ−１とが異なる場合、
ｈ−１人のエンティティが検査記号を１要素ずつ記憶し、検査記号を１要素も記憶しないエンティティが生じても良い(ｋ＞ｈ−１の場合)。またｋ＜ｈ−１の場合、検査記号の要素を複数個、例えば２個記憶するエンティティが生じても良い。
【００４４】
パスワードの再生時には、検査記号(Ｒ1,Ｒ2,…,Ｒk)を秘密にしたまま、前記のパスワード再生の手順を実行する。i＝1〜eのエンティティがパスワードＩiと検査記号の要素Ｒi(i=1〜e)を忘却あるいは紛失し、i＝e+1〜kのエンティティがパスワードＩiと検査記号の要素Ｒiとを記憶しているものとする。前記と同様にノイズｎ1〜ｎeと、ノイズとパスワードの合成値ｎe+1＋Ｉe+1〜ｎk＋Ｉkを用い、これらの全体で構成されるリードソロモン符号の検査記号Ｓを求める。検査記号Ｓを、個々の要素を明示して(Ｓ1,Ｓe,…,Ｓe+1,Ｓk)と表記すると、上記と同様にして各エンティティiは検査記号Ｓのi番目の要素Ｓiを秘密に導く。検査記号の要素Ｓ1〜Ｓeは用いない要素で、求めなくても良い。エンティティe+1〜ｋは、リードソロモン符号の一部(ｎe+1,Ｓe+1＋Ｒe+1)を他のエンティティに送信する。
【００４５】
ｋ＝ｈ−１との仮定から、ｅが１／２ｋ以下でパスワードが再生でき、再生されるリードソロモン符号は検査記号(Ｓ＋Ｒ)に対するもので、検査記号Ｒ自体は秘密のままである。またエンティティe+1〜ｋに関するデータでは、情報部分としてノイズｎi(i＝e+1〜ｋ)しか再生されず、エンティティ(i＝1〜e)に関するデータでは情報部分としてｎi＋Ｉiが再生され、ノイズｎiの値は他のエンティティには秘密なので、本人のみがパスワードＩiを再生できる。
【００４６】
実施例の全体に対して、秘密データ訂正装置の構成や秘密データの訂正用のプログラムの構成を補足する。秘密データの訂正装置は、他のエンティティとの通信手段(例えばインターネットへの接続能力)と、用いる有限体の原始元ｇを演算あるいは記憶すると共に乱数を発生させ、ｇri,Σ(ｊ＝１〜ｋ,ｊ≠i)(ｇri)rj等を介して検査記号あるいはその一部を求めるための手段と、検査記号から誤り訂正により符号語中のパスワードを再生するための手段とを備えたものとする。そしてこれらの手段を資源として、第１検査記号発生手段や第２検査記号発生手段、訂正値算出手段、訂正手段等を構成できる。
【００４７】
秘密データの再生プログラムは、ＣＤ−ＲＯＭ等の記憶媒体やネットワーク上の搬送波などを介して配布され、用いる有限体の原始元ｇを演算あるいは記憶すると共に乱数を発生させ、ｇri,Σ(ｊ＝１〜ｋ,ｊ≠i)(ｇri)rj等を介して検査記号あるいはその一部を求めるための命令と、検査記号から誤り訂正により符号語中のパスワードを再生するための命令とを備えたものとする。そしてこれらの命令を資源として、第１検査記号発生命令や第２検査記号発生命令、訂正値算出命令、訂正命令等を構成できる。
【図面の簡単な説明】
【図１】  実施例での、復元用データの準備でエンティティ間の通信を示すブロック図
【図２】  実施例での、データ消失時のエンティティ間の通信を示すブロック図
【図３】  実施例の秘密データの訂正方法での、復元用データの生成時のデータフローを示す図
【図４】  実施例での、復元用データの生成アルゴリズムを示すフローチャート
【図５】  実施例の秘密データの訂正方法での、消失データの復元時のデータフローを示す図
【図６】  実施例での、消失データの復元アルゴリズムを示すフローチャート
【図７】  変形例での、エンティティとセンターとの通信を示すブロック図
【符号の説明】
Ｅ1〜Ｅk      エンティティ
Ｉ1〜Ｉk      パスワード
Ｒ(Ｘ)        検査記号
Ｓ(Ｘ)        検査記号
ｎi           ノイズ
ｒi,ｑi      秘密の乱数
Ｅ1〜Ｅe      パスワードを消失したエンティティ
Ｅe+1〜Ｅk    パスワードを記憶しているエンティティ
２            通信路
４            パスワード系データ
６            準備データ
８            検査記号Ｒ(Ｘ)の生成
１０          パスワード復元時の状況データ
１２          乱数の発生と通信処理
１４          パスワードの復元処理
２０          センター
【図１】
0003931061.tif 000002
【図２】
0003931061.tif 000003
【図３】
0003931061.tif 000004
【図４】
0003931061.tif 000005
【図５】
0003931061.tif 000006
【図６】
0003931061.tif 000007
【図７】
0003931061.tif 000008