(57)【特許請求の範囲】
【請求項１】
n台のシェア復旧装置p0,…,pn-1を含むシェア復旧システムであって、
n≧2k-1とし、m≦n-kとし、iは0以上k未満の各整数とし、jはk+1以上k+m未満の各整数とし、[a]0,…,[a]n-1は情報aをShamir秘密分散によりn個に分割したシェアとし、σ0,…,σk-1は正当なシェア[a]0,…,[a]k-1を保持するk台のシェア復旧装置とし、τk,…,τk+m-1は不正なシェア[a]k,…,[a]k+m-1を保持するm台のシェア復旧装置とし、
上記シェア復旧装置σiは、
復元すると乱数rとなるShamir秘密分散値[r]のシェア[r]iを生成する乱数生成部と、
上記シェア[a]iから上記シェア[r]iを減算して、復元すると値bとなるShamir秘密分散値[b]のシェア[b]iを計算する秘匿化部と、
を含み、
上記シェア復旧装置τkは、
上記Shamir秘密分散値[r]のシェア[r]kを生成する乱数生成部と、
上記シェア復旧装置σ0,…,σk-1から上記Shamir秘密分散値[b]のシェア[b]0,…,[b]k-1を受信するシェア通信部と、
上記シェア[b]0,…,[b]k-1を用いて上記Shamir秘密分散値[b]のシェア[b]k,…,[b]k+m-1を復旧する復旧部と、
上記シェア[b]kに上記シェア[r]kを加算して上記シェア[a]kを計算する復元部と、
を含み、
上記シェア復旧装置τjは、
上記Shamir秘密分散値[r]のシェア[r]jを生成する乱数生成部と、
上記シェア復旧装置τkから上記Shamir秘密分散値[b]のシェア[b]jを受信するシェア通信部と、
上記シェア[b]jに上記シェア[r]jを加算して上記シェア[a]jを計算する復元部と、
を含むシェア復旧システム。
【請求項２】
請求項１に記載のシェア復旧システムであって、
上記復旧部は、j'=k,…,k+m-1について、上記シェア[b]0,…,[b]k-1からラグランジュ補間により[b]j'を求めることにより、上記シェア[b]k,…,[b]k+m-1を復旧するものである
シェア復旧システム。
【請求項３】
請求項１または２に記載のシェア復旧システムであって、
上記シェア復旧装置p0,…,pn-1は、
乱数siを生成し、上記乱数siを公開する公開乱数生成部と、
上記乱数s0,…,sn-1の総和である共有乱数sを生成する共有乱数計算部と、
上記共有乱数sと上記シェア[a]iを用いてシェア[c]i=Σi<msi+1[a]iを計算するチェックサム計算部と、
復元すると乱数r'になるShamir秘密分散値[r']のシェア[r']iを生成する乱数分散値生成部と、
上記シェア[c]iから上記シェア[r']iを減算して、復元すると判定値dとなるShamir秘密分散値[d]のシェア[d]iを計算する判定値計算部と、
k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する判定値復旧部と、
h=k,…,n-1について、上記シェア[d]hと上記シェア[d]'hとが一致するか否かを判定する不整合判定部と、
をさらに含むシェア復旧システム。
【請求項４】
n≧2k-1とし、m≦n-kとし、iは0以上k未満の各整数とし、jはk+1以上k+m未満の各整数とし、i'は0以上n未満の各整数とし、j'はk以上k+m未満の各整数とし、[a]0,…,[a]n-1は情報aをShamir秘密分散によりn個に分割したシェアとし、σ0,…,σk-1は正当なシェア[a]0,…,[a]k-1を保持するk台のシェア復旧装置とし、τk,…,τk+m-1は不正なシェア[a]k,…,[a]k+m-1を保持するm台のシェア復旧装置とし、
n台のシェア復旧装置pi'が、復元すると乱数rとなるShamir秘密分散値[r]のシェア[r]i'を生成する乱数生成ステップと、
k台のシェア復旧装置σiが、上記シェア[a]iから上記シェア[r]iを減算して、復元すると値bとなるShamir秘密分散値[b]のシェア[b]iを計算する秘匿化ステップと、
シェア復旧装置τkが、上記シェア復旧装置σ0,…,σk-1から上記Shamir秘密分散値[b]のシェア[b]0,…,[b]k-1を受信する第一シェア通信ステップと、
上記シェア復旧装置τkが、上記シェア[b]0,…,[b]k-1を用いて上記Shamir秘密分散値[b]のシェア[b]k,…,[b]k+m-1を復旧する復旧ステップと、
m-1台のシェア復旧装置τjが、上記シェア復旧装置τkから上記シェア[b]jを受信する第二シェア通信ステップと、
m台のシェア復旧装置τj'が、上記シェア[b]j'に上記シェア[r]j'を加算して上記シェア[a]j'を計算する復元ステップと、
を含むシェア復旧方法。
【請求項５】
請求項４に記載のシェア復旧方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関し、特に、秘密分散された分散値のうち一部のシェアが失われた場合に、その失われたシェアを復旧する技術に関する。
【背景技術】
【０００２】
秘密分散とは、データを複数に分割した分散値に変換し、一定個数以上のシェアを用いれば元のデータを復元でき、一定個数未満のシェアからは元のデータを一切復元できなくする技術である。なお、秘密分散した複数個の値の組を分散値と呼び、分散値のうちの１個の断片をシェアと呼ぶ。秘密分散の例としては、Shamir秘密分散（Shamir's Secret Sharing）や複製型秘密分散（Replicated Secret Sharing）などが挙げられる。
【０００３】
復旧とは、シェアを保有するパーティが利用不能になるなどにより一部のシェアが失われた際に、利用不能となった一部のシェアを利用可能な一定数のシェアから秘匿性を失わずに再構築する方法である。従来の復旧技術としては、例えば、特許文献１や非特許文献１に記載の方法が挙げられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４３０５０４９号明細書
【非特許文献】
【０００５】
【非特許文献１】K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction”, CoRR, vol. abs/1005.4178, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１や非特許文献１に記載の従来技術は、専用の符号化を必要とする。そのため、Shamir秘密分散などとは異なり秘密計算には適用できない。また、特許文献１の方法は、パーティあたりの平均通信量がO(n)であり効率が低い。
【０００７】
この発明の目的は、このような点に鑑みて、Shamir秘密分散に対する効率的なシェア復旧技術を提供することである。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明のシェア復旧システムは、n台のシェア復旧装置p0,…,pn-1を含むシェア復旧システムであって、n≧2k-1とし、m≦n-kとし、iは0以上k未満の各整数とし、jはk+1以上k+m未満の各整数とし、[a]0,…,[a]n-1は情報aをShamir秘密分散によりn個に分割したシェアとし、σ0,…,σk-1は正当なシェア[a]0,…,[a]k-1を保持するk台のシェア復旧装置とし、τk,…,τk+m-1は不正なシェア[a]k,…,[a]k+m-1を保持するm台のシェア復旧装置とし、シェア復旧装置σiは、復元すると乱数rとなるShamir秘密分散値[r]のシェア[r]iを生成する乱数生成部と、シェア[a]iからシェア[r]iを減算して、復元すると値bとなるShamir秘密分散値[b]のシェア[b]iを計算する秘匿化部と、を含み、シェア復旧装置τkは、Shamir秘密分散値[r]のシェア[r]kを生成する乱数生成部と、シェア復旧装置σ0,…,σk-1からShamir秘密分散値[b]のシェア[b]0,…,[b]k-1を受信するシェア通信部と、シェア[b]0,…,[b]k-1を用いてShamir秘密分散値[b]のシェア[b]k,…,[b]k+m-1を復旧する復旧部と、シェア[b]kにシェア[r]kを加算してシェア[a]kを計算する復元部と、を含み、シェア復旧装置τjは、Shamir秘密分散値[r]のシェア[r]jを生成する乱数生成部と、シェア復旧装置τkからShamir秘密分散値[b]のシェア[b]jを受信するシェア通信部と、シェア[b]jにシェア[r]jを加算してシェア[a]jを計算する復元部と、を含む。
【発明の効果】
【０００９】
この発明のシェア復旧技術は、Shamir秘密分散のシェアを復旧する際のパーティ平均通信量が１体要素である。また、複数のシェアが失われた場合でも平均通信量は変化しない。したがって、この発明によれば、効率的にShamir秘密分散のシェアを復旧できる。
【図面の簡単な説明】
【００１０】
【図１】図１は、シェア復旧システムの機能構成を例示する図である。
【図２】図２は、第一実施形態のシェア復旧装置の機能構成を例示する図である。
【図３】図３は、第一実施形態のシェア復旧方法の処理フローを例示する図である。
【図４】図４は、第二実施形態のシェア復旧装置の機能構成を例示する図である。
【図５】図５は、不整合検知部の機能構成を例示する図である。
【図６】図６は、第二実施形態のシェア復旧方法の処理フローを例示する図である。
【図７】図７は、不整合検知方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１１】
実施形態の説明に先立ち、この明細書における表記方法およびこの発明の基本的な考え方について説明する。
【００１２】
［表記方法］
piは、i番目のシェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
σi∈Pは、正当なシェアを所持する稼動中のパーティを表す。
τi∈Pは、正当なシェアを失った故障中のパーティを表す。
[・]x（角括弧）は、平文・のShamir秘密分散による分散値を表す。xは平文空間の要素数を表す。x=pのとき、xは省略して[・]と表す。pは群Zpの位数である素数である。
[・]iは、Shamir秘密分散値[・]のうち、パーティpi∈Pが所持するシェアを表す。
【００１３】
［Shamir秘密分散］
Shamir秘密分散（Shamir's Secret Sharing）は(k,n)-秘密分散の一つである。(k,n)-秘密分散は、入力された平文をn個に分割した分散値をn個のパーティに分散して保持しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、n, kは1以上の整数であり、n=2k-1である。Shamir秘密分散についての詳細は下記参考文献１を参照されたい。
〔参考文献１〕A. Shamir, “How to share a secret”, Communications of the ACM, vol. 22(11), pp. 612-613, 1979.
【００１４】
Shamir秘密分散では、i番目のパーティpiに座標xiを割り当て、乱数riを用いて、次式により、情報aを分散する。
【数１】
0005968484.tif 000002
【００１５】
Shamir秘密分散のメリットは、データ容量が小さいことである。一方、デメリットは、体の要素数がn+1以上でなければならず、mod 2は使えないことである。
【００１６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１７】
［第一実施形態］
第一実施形態のシェア復旧システムは、図１に例示するように、n（≧3）台のシェア復旧装置１1,…,１nを含む。本形態では、シェア復旧装置１1,…,１nはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、シェア復旧装置１i（i∈{1,…,n}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。
【００１８】
シェア復旧装置１は、図２に例示するように、シェア記憶部１０、乱数生成部１１、秘匿化部１２、シェア通信部１３、復旧部１４、および復元部１５を含む。
【００１９】
シェア復旧装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。シェア復旧装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。シェア復旧装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。シェア復旧装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２０】
シェア復旧装置１の備えるシェア記憶部１０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００２１】
図３を参照して、第一実施形態のシェア復旧方法の処理手続きを説明する。
【００２２】
以下では、σ0,…,σk-1を稼動中のシェア復旧装置から任意に選択したk台のシェア復旧装置とし、τk,…,τk+m-1（m≦n-k）を故障中のm台のシェア復旧装置とする。すなわち、情報aのShamir秘密分散値[a]のうち、シェア[a]0,…,[a]k-1は正当なシェアであり、[a]k,…,[a]k+m-1は破損もしくは失われたシェアである。σ0,…,σk-1,τk,…,τk+m-1は論理的にシェア復旧装置の役割を指し示す符号であり、どのシェア復旧装置１1,…,１nがどのシェア復旧装置σ0,…,σk-1,τk,…,τk+m-1に対応するかは実行時に任意に決定される。
【００２３】
少なくともk台のシェア復旧装置σi（i=0,…,k-1）のシェア記憶部１０には、情報aをShamir秘密分散によりn個に分割した分散値[a]のうちi番目のシェア[a]iが記憶されている。情報aは体Fの要素であり、体Fはmod pの数の集合である。なお、pは素数である。
【００２４】
ステップＳ１１において、n台のシェア復旧装置pi（i=0,…,n-1）の乱数生成部１１は、復元すると乱数rとなるShamir秘密分散値[r]のシェア[r]iを生成する。シェア[r]iは、秘匿化部１２および復元部１５へ送られる。シェア[r]iの生成は、いずれのシェア復旧装置piからも乱数rが秘匿された状態で行われなければならない。例えば、以下のようにしてシェア[r]iを生成することができる。まず、シェア復旧装置pj（j=0,…,n-1）それぞれが乱数rjを生成する。次に、シェア復旧装置pjそれぞれが、乱数rjをShamir秘密分散により分割し、乱数rjの分散値[rj]を生成する。そして、シェア復旧装置pi（i=0,…,n-1）それぞれが、[r]i=Σj<n[rj]iを計算し、乱数rのシェア[r]iを得る。このように構成すれば、いずれのシェア復旧装置p0,…,pn-1も乱数rを知ることがなく、乱数rのシェア[r]iを得ることができる。
【００２５】
ステップＳ１２iにおいて、k台のシェア復旧装置σi（i=0,…,k-1）の秘匿化部１２は、シェア記憶部１０に記憶されたシェア[a]iから、乱数生成部１１が出力するシェア[r]iを減算して、Shamir秘密分散のシェア[b]iを計算する。すなわち、[b]i=[a]i-[r]iを計算する。シェア復旧装置σiのシェア通信部１３は、シェア[b]iをシェア復旧装置τkへ送信する。ステップＳ１３kにおいて、シェア復旧装置τkのシェア通信部１３は、シェア復旧装置σ0,…,σk-1からk個のシェア[b]0,…,[b]k-1を受信する。
【００２６】
ステップＳ１４kにおいて、シェア復旧装置τkの復旧部１４は、シェア復旧装置σ0,…,σk-1から受信したk個のシェア[b]0,…,[b]k-1を用いて、m個のシェア[b]k,…,[b]k+m-1を復旧する。シェア復旧装置τkのシェア通信部１３は、m-1個のシェア[b]j（j=k+1,…,k+m-1）をシェア復旧装置τjへ送信する。ステップＳ１３jにおいて、シェア復旧装置τj（j=k+1,…,k+m-1）のシェア通信部１３は、シェア復旧装置τkからシェア[b]jを受信する。
【００２７】
シェア復旧装置τkの復旧部１４は、具体的には以下のようにしてシェアの復旧を行う。復旧部１４は、j=k,…,k+m-1について、次式によりシェア[b]jを計算する。
【数２】
0005968484.tif 000003
ここで、λσ,i,jは、公知のラグランジュ補間において、座標xjの関数値f(xj)を、座標x0,…,xk-1の関数値f(x0),…,f(xk-1)（=[a]0,…,[a]k-1）から計算する際に、関数値f(xi)に乗ずるべき係数である。λσ,i,jは、次式により計算できる。
【数３】
0005968484.tif 000004
【００２８】
ステップＳ１５kにおいて、シェア復旧装置τkの復元部１５は、復旧部１４が出力するシェア[b]kに、乱数生成部１１が出力するシェア[r]kを加算して、シェア[a]kを計算する。すなわち、[a]k=[b]k+[r]kを計算する。同様に、ステップＳ１５jにおいて、m-1台のシェア復旧装置τj（j=k+1,…,k+m-1）の復元部１５は、シェア復旧装置τkから受信したシェア[b]jに、乱数生成部１１が出力するシェア[r]jを加算して、シェア[a]jを計算する。すなわち、[a]j=[b]j+[r]jを計算する。
【００２９】
本形態のシェア復旧システムおよび方法では、処理中で乱数rを用いるが、この乱数rは最後にはキャンセルされるため、シェアを復旧したときに稼働中のパーティのシェアを再生成する必要がない。また、復旧したシェアは失われる前と同一のシェアとなるため、データの版管理を悪化させることがない。
【００３０】
本形態のシェア復旧システムおよび方法の性能は、以下のとおりである。通信量は、次式で計算されるビット数となる。ただし、mは失われたシェアの個数であり、|p|は素数pを表すために必要なビット数である。
【数４】
0005968484.tif 000005
【００３１】
全体のラウンド数は２である。乱数生成量は、次式で計算されるビット数である。
【数５】
0005968484.tif 000006
【００３２】
［第二実施形態］
第二実施形態のシェア復旧システムは、図１に例示するように、n（≧3）台のシェア復旧装置３1,…,３nを含む。
【００３３】
シェア復旧装置３i（i=1,…,n）は、図４に例示するように、シェア記憶部１０、乱数生成部１１、秘匿化部１２、シェア通信部１３、復旧部１４、および復元部１５を第一実施形態と同様に含み、不整合検知部１６をさらに含む。不整合検知部１６は、図５に例示するように、公開乱数生成部１６１、共有乱数計算部１６２、チェックサム計算部１６３、乱数分散値生成部１６４、判定値計算部１６５、判定値通信部１６６、判定値復旧部１６７、および不整合判定部１６８を含む。
【００３４】
図６を参照して、第二実施形態のシェア復旧方法の処理手続きを、第一実施形態との差分を中心に説明する。
【００３５】
ステップＳ１６において、n台のシェア復旧装置pi（i=0,…,n-1）の不整合検知部１６は、シェア記憶部１０に記憶された情報aの分散値[a]に不整合があるか否かを検証し、不正なシェアを持つシェア復旧装置τk,…,τk+m-1を特定する。また、同時に、正当なシェアを持つシェア復旧装置のうち、シェアの復旧を行うk台のシェア復旧装置σ0,…,σk-1を選択する。
【００３６】
ステップＳ１１以降の処理では、不正なシェアを保持するシェア復旧装置τk,…,τk+m-1と、正当なシェアを保持するn-m台のシェア復旧装置から選択したk台のシェア復旧装置σ0,…,σk-1とが、第一実施形態で説明した方法により不正なシェアの復旧を行う。
【００３７】
図７を参照して、不整合検知部１６が分散値の不整合を検知する処理手続きを、より詳細に説明する。
【００３８】
ステップＳ１６１において、n台のシェア復旧装置pi（i=0,…,n-1）の公開乱数生成部１６１は、乱数siを生成する。生成した乱数siは他のn-1台のシェア復旧装置pi'（i'=0,…,n-1、i≠i'）から参照できるように公開する。
【００３９】
ステップＳ１６２において、n台のシェア復旧装置piの共有乱数計算部１６２は、自身が生成した乱数siと他のn-1台のシェア復旧装置pi'が公開する乱数si'を併せたn個の乱数s0,…,sn-1を用いて、次式により共有乱数sを計算する。
【数６】
0005968484.tif 000007
【００４０】
ステップＳ１６３において、n台のシェア復旧装置piのチェックサム計算部１６３は、シェア記憶部１０に記憶されたシェア[a]iを[a]i:=([a0]i,…,[am-1]i)とし、共有乱数計算部１６２が計算した共有乱数sを用いて、次式によりチェックサム[c]iを計算する。
【数７】
0005968484.tif 000008
【００４１】
ステップＳ１６４において、n台のシェア復旧装置piの乱数分散値生成部１６４は、復元すると乱数r'となるShamir秘密分散値[r']のシェア[r']iを生成する。シェア[r']iの生成方法は、上述の乱数生成部１１と同様の処理により行えばよい。
【００４２】
ステップＳ１６５において、n台のシェア復旧装置piの判定値計算部１６５は、チェックサム計算部１６３が計算したチェックサム[c]iから、乱数分散値生成部１６４が生成したシェア[r']iを減算して、復元すると判定値dとなるShamir秘密分散値[d]のシェア[d]i=[c-r']iを計算する。シェア同士の減算はシェア復旧装置p0,…,pn-1間での通信なしに行うことができる。
【００４３】
ステップＳ１６６ａにおいて、n-1台のシェア復旧装置p1,…,pn-1の判定値通信部１６６は、判定値計算部１６５が計算したシェア[d]iをシェア復旧装置p0へ送信する。ステップＳ１６６ｂにおいて、シェア復旧装置p0の判定値通信部１６６は、n-1台のシェア復旧装置p1,…,pn-1からn-1個のシェア[d]1,…,[d]n-1を受信する。
【００４４】
ステップＳ１６７において、n台のシェア復旧装置piの判定値復旧部１６７は、k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する。シェアの復旧方法は、上述の復旧部１４と同様に、ラグランジュ補間を用いて行うことが可能である。
【００４５】
ステップＳ１６８において、n台のシェア復旧装置piの不整合判定部１６８は、j'=k,…,n-1について、シェア復旧装置pj'から受信したシェア[d]j'と復旧したシェア[d]'j'とが一致するか否かを判定する。j'=k,…,n-1のすべてについて[d]j'=[d]'j'が成り立てば不整合がなかったと判定し、いずれかのj'について[d]j'≠[d]'j'であれば不整合があったと判定する。不整合がなかったと判定した場合には、その旨を示す情報（例えば、k個のシェア[d]0,…,[d]k-1から復元した判定値dなど）を出力して処理を終了する。
【００４６】
不整合があったと判定した場合には、n台のシェア復旧装置piのうち2k-1台のシェア復旧装置を選択し、すべての2k-1台のシェア復旧装置の組み合わせについて上述の不整合検知部１６の処理手続きにより不整合検知を行うことを繰り返す。これにより、不整合が検出された場合に共通して処理を行ったシェア復旧装置が保持しているシェアが不正なシェアであることを検知することができる。
【００４７】
第二実施形態のシェア復旧システムおよび方法によれば、シェアが偶発的にビット反転してしまった場合や攻撃者によりシェアが改ざんされた場合など、すべてのシェア復旧装置が稼働中であってもシェアを復旧することができる。特に、シェア本体のハッシュ値を取ることで改ざん検知するような方法ではシェア本体とハッシュ値の両方を改ざんするような攻撃には対応できなかったが、本形態の方法であればすべてのシェアが辻褄の合うように改ざんされない限り不整合を検知できるため有効である。また、不整合検知部の処理は、シェアのデータ量に関わらず、通信量がO(1)、ラウンド数がO(1)であるため、効率がよい。
【００４８】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４９】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５１】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５４】
１、３  シェア復旧装置
２  通信網
１０  シェア記憶部
１１  乱数生成部
１２  秘匿化部
１３  シェア通信部
１４  復元部
１５  復旧部
１６  不整合検知部
【要約】
【課題】Shamir秘密分散に対する効率的なシェア復旧技術を提供する。
【解決手段】n台のシェア復旧装置p0,…,pn-1が、復元すると乱数rとなるShamir秘密分散値のシェア[r]iを生成する。k台のシェア復旧装置σ0,…,σk-1が、シェア[a]iからシェア[r]iを減算してシェア[b]iを計算する。シェア復旧装置τkが、シェア復旧装置σ0,…,σk-1からシェア[b]0,…,[b]k-1を受信する。シェア復旧装置τkが、シェア[b]0,…,[b]k-1を用いてシェア[b]k,…,[b]k+m-1を復旧する。m-1台のシェア復旧装置τk+1,…,τk+m-1が、シェア復旧装置τkからシェア[b]jを受信する。m台のシェア復旧装置τk,…,τk+m-1が、シェア[b]jにシェア[r]jを加算してシェア[a]jを計算する。
【選択図】図３【図１】
0005968484.tif 000009
【図２】
0005968484.tif 000010
【図３】
0005968484.tif 000011
【図４】
0005968484.tif 000012
【図５】
0005968484.tif 000013
【図６】
0005968484.tif 000014
【図７】
0005968484.tif 000015