(57)【特許請求の範囲】
【請求項１】
n,kをn≧2k-1を満たす整数とし、mを1以上の整数とし、iを0以上n未満の各整数とし、
n台の不整合検知装置piが、m個の値a0,…,am-1を(k,n)-秘密分散により分割したシェア[a0]i,…,[am-1]iを記憶しており、
上記n台の不整合検知装置piが、乱数siを生成し、上記乱数siを公開する公開乱数生成ステップと、
上記n台の不整合検知装置piが、上記乱数s0,…,sn-1の総和である共有乱数sを生成する共有乱数計算ステップと、
上記n台の不整合検知装置piが、上記共有乱数sと上記シェア[a0]i,…,[am-1]iを用いてシェア[c]i=Σj<m-1sj+1[aj]i+sm+1[am-1]iを計算するチェックサム計算ステップと、
上記n台の不整合検知装置piが、復元すると乱数rになるシェア[r]iを生成する乱数分散値生成ステップと、
上記n台の不整合検知装置piが、復元すると判定値dになるシェア[d]i=[c-r]iを計算する判定値計算ステップと、
1台の不整合検知装置p0が、n-1台の不整合検知装置p1,…,pn-1からn-1個のシェア[d]1,…,[d]n-1を受信する判定値通信ステップと、
上記不整合検知装置p0が、k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する判定値復旧ステップと、
上記不整合検知装置p0が、j=k,…,n-1について、上記シェア[d]jと上記シェア[d]'jとが一致するか否かを判定する不整合判定ステップと、
を含む不整合検知方法。
【請求項２】
請求項１に記載の不整合検知方法であって、
mは2以上の整数であり、jを0以上m未満の整数とし、
上記シェア[a0]i,…,[am-1]iを複数のグループに分割し、各グループについて請求項１に記載の不整合検知方法により不整合の有無を検知し、不整合があると判定されたグループをさらに複数のグループに分割し、グループに含まれるシェアが1個になるまで繰り返すことで不整合のあるシェア[aj]iを特定する
不整合検知方法。
【請求項３】
請求項１または２に記載の不整合検知方法であって、
n,n',kをn>n'=2k-1を満たす整数とし、
n台の不整合検知装置から選択したn’台の不整合検知装置の組み合わせすべてについて請求項１または２に記載の不整合検知方法により不整合の有無を検知し、不整合があると判定した上記組み合わせに共通して含まれる上記不整合検知装置が記憶する上記シェア[a0]i,…,[am-1]iに不整合があることを特定する
不整合検知方法。
【請求項４】
n台の不整合検知装置p0,…,pn-1を含む不整合検知システムであって、
n,kをn≧2k-1を満たす整数とし、mを1以上の整数とし、iを0以上n未満の各整数とし、i'をi≠i'である0以上n未満の各整数とし、
上記不整合検知装置piは、
m個の値a0,…,am-1を(k,n)-秘密分散により分割したシェア[a0]i,…,[am-1]iを記憶する記憶部と、
乱数siを生成し、上記乱数siを公開する公開乱数生成部と、
上記乱数s0,…,sn-1の総和である共有乱数sを生成する共有乱数計算部と、
上記共有乱数sと上記シェア[a0]i,…,[am-1]iを用いてシェア[c]i=Σj<m-1sj+1[aj]i+sm+1[am-1]iを計算するチェックサム計算部と、
復元すると乱数rになるシェア[r]iを生成する乱数分散値生成部と、
復元すると判定値dになるシェア[d]i=[c-r]iを計算する判定値計算部と、
他のn-1台の不整合検知装置pi'からn-1個のシェア[d]i'を受信する判定値通信部と、
k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する判定値復旧部と、
j=k,…,n-1について、上記シェア[d]jと上記シェア[d]'jとが一致するか否かを判定する不整合判定部と、
を含む不整合検知システム。
【請求項５】
n,kをn≧2k-1を満たす整数とし、mを1以上の整数とし、iを0以上n未満の整数とし、i'をi≠i'である0以上n未満の各整数とし、
m個の値a0,…,am-1を(k,n)-秘密分散により分割したシェア[a0]i,…,[am-1]iを記憶する記憶部と、
乱数siを生成し、上記乱数siを公開する公開乱数生成部と、
上記乱数s0,…,sn-1の総和である共有乱数sを生成する共有乱数計算部と、
上記共有乱数sと上記シェア[a0]i,…,[am-1]iを用いてシェア[c]i=Σj<m-1sj+1[aj]i+sm+1[am-1]iを計算するチェックサム計算部と、
復元すると乱数rになるシェア[r]iを生成する乱数分散値生成部と、
復元すると判定値dになるシェア[d]i=[c-r]iを計算する判定値計算部と、
他のn-1台の不整合検知装置pi'からn-1個のシェア[d]i'を受信する判定値通信部と、
k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する判定値復旧部と、
j=k,…,n-1について、上記シェア[d]jと上記シェア[d]'jとが一致するか否かを判定する不整合判定部と、
を含む不整合検知装置。
【請求項６】
請求項５に記載の不整合検知装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関し、特に秘密分散されたシェアの不整合を検知する技術に関する。
【背景技術】
【０００２】
秘密分散とは、データを複数に分割した分散値に変換し、一定個数以上のシェアを用いれば元のデータを復元でき、一定個数未満のシェアからは元のデータを一切復元できなくする技術である。なお、秘密分散した複数個の値の組を分散値と呼び、分散値のうちの１個の断片をシェアと呼ぶ。
【０００３】
各計算主体（以下、パーティとも呼ぶ。）が保持するシェアに不整合がある場合、復元する際のシェアの選び方によって復元結果が異なるという問題が発生する。したがって、分散値から元のデータを復元する際に、シェアに不整合がないかを確認する必要がある。非特許文献１には、シェアを他の計算主体に渡すことなく、シェアの不整合を検知する技術が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M. Fitzi, J. A. Garay, S. Gollakota, C. P. Rangan, and K. Srinathan, “Round-optimal and efficient verifiable secret sharing”, TCC 2006, Vol. 3876 of Lecture Notes in Computer Science, pp. 329-342, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載の従来技術は、主に通信段数の効率化に主眼が置かれている。しかし、大規模データを扱う場合には、通信段数よりも通信量を低減した方が効果的である。
【０００６】
この発明の目的は、このような点に鑑みて、シェアの不整合を検知できる秘密分散技術において、通信量を低減することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の不整合検知方法は、n,kをn≧2k-1を満たす整数とし、mを1以上の整数とし、iを0以上n未満の各整数とし、n台の不整合検知装置piが、m個の値a0,…,am-1を(k,n)-秘密分散により分割したシェア[a0]i,…,[am-1]iを記憶しており、n台の不整合検知装置piが、乱数siを生成し、乱数siを公開する公開乱数生成ステップと、n台の不整合検知装置piが、乱数s0,…,sn-1の総和である共有乱数sを生成する共有乱数計算ステップと、n台の不整合検知装置piが、共有乱数sとシェア[a0]i,…,[am-1]iを用いてシェア[c]i=Σj<m-1sj+1[aj]i+sm+1[am-1]iを計算するチェックサム計算ステップと、n台の不整合検知装置piが、復元すると乱数rになるシェア[r]iを生成する乱数分散値生成ステップと、n台の不整合検知装置piが、復元すると判定値dになるシェア[d]i=[c-r]iを計算する判定値計算ステップと、1台の不整合検知装置p0が、n-1台の不整合検知装置p1,…,pn-1からn-1個のシェア[d]1,…,[d]n-1を受信する判定値通信ステップと、不整合検知装置p0が、k個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する判定値復旧ステップと、不整合検知装置p0が、j=k,…,n-1について、シェア[d]jとシェア[d]'jとが一致するか否かを判定する不整合判定ステップと、を含む。
【発明の効果】
【０００８】
この発明の不整合検知技術によれば、少ない通信量でシェアの不整合を検知できる。
【図面の簡単な説明】
【０００９】
【図１】図１は、不整合検知システムの機能構成を例示する図である。
【図２】図２は、不整合検知装置の機能構成を例示する図である。
【図３】図３は、不整合検知方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立って、以下の説明で用いる表記方法および用語を説明する。
［表記方法］
piは、i番目のシェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
[x]（角括弧）は、平文xの(k,n)-秘密分散値を表す。(k,n)-秘密分散値は、平文xを(k,n)-秘密分散で分散した値すべてを集めた組である。(k,n)-秘密分散値[x]は、普段はnパーティ集合Pに分散されて所持されているため、一か所ですべてを所持されることはなく、仮想的である。
[x]iは、(k,n)-秘密分散値[x]のうち、パーティpi∈Pが所持するシェアを表す。
qは、素数である。
Fは、mod qの数の集合である。
|F|は、Fの要素を表すのに必要なビット数である。
【００１１】
［秘密分散］
この発明で不整合検知の対象とする秘密分散値は任意の(k,n)-秘密分散による分散値である。秘密分散の一種である(k,n)-秘密分散は、入力された平文をn個に分割した分散値をn個のパーティに分散して保持しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、n,kは1以上の整数であり、n≧2k-1である。(k,n)-秘密分散の例としては、下記参考文献１に記載されたShamir秘密分散（Shamir's Secret Sharing）や、下記参考文献２に記載された複製型秘密分散（Replicated Secret Sharing）が挙げられる。
〔参考文献１〕A. Shamir, “How to share a secret”, Communications of the ACM, vol. 22(11), pp. 612-613, 1979.
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC 2005, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005.
【００１２】
Shamir秘密分散では、i番目のパーティpiに座標xiを割り当て、乱数riを用いて、次式により、平文aを分散する。
【数１】
0005860556.tif 000002
【００１３】
複製型秘密分散は、例えばn=3, k=2の場合、平文aをa:=a0+a1+a2と変形し、[a0,a1]0、[a1,a2]1、[a2,a0]2の3つのシェアに分散する。シェアを構成する各要素a0,a1,a2はサブシェアと呼ぶ。
【００１４】
［復旧］
復旧とは、シェアを保有する計算主体が利用不能になるなどにより一部のシェアが失われた際に、少なくともk個のシェアが利用可能であることを条件に、利用不能となった一部のシェアを利用可能なk個のシェアから秘匿性を失わずに再構築する方法である。
【００１５】
Shamir秘密分散では、公知のラグランジュ補間により、利用可能なk個のシェアから他のn-k個のシェアを復旧することが可能である。
【００１６】
複製型秘密分散では、利用可能なk個のシェアに含まれるサブシェアを組み合わせることで他のn-k個のシェアを復旧することが可能である。例えば、上記の複製型秘密分散の例においてパーティp2（すなわちシェア[a2,a0]2）が利用不能となった場合、パーティp0が保持するサブシェアa0とパーティp1が保持するサブシェアa2を組み合わせることで、失われたシェア[a2,a0]2を復旧することができる。
【００１７】
［復元］
復元とは、n個のシェアのうちk個のシェアを収集し、k個のシェアから元の平文を得る方法である。Shamir秘密分散では、公知のラグランジュ補間により、k個のシェアから元の平文を復元することが可能である。複製型秘密分散では、k個のシェアに含まれる相異なるサブシェアをすべて加算することで元の平文を復元することが可能である。
【００１８】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［第一実施形態］
第一実施形態の不整合検知システムおよび方法は、複数の秘密分散されたシェアに対して同時に不整合を検知する。本形態では不整合の有無は検知できるが、どのシェアに不整合があったのかは検知することができない。定期的な不整合検知に用いる場面を想定すると、平常時は不整合がない場合がほとんどであると考えられるため、全体として不整合の有無を検知できれば十分に有効である。
【００１９】
図１を参照して、実施形態の不整合検知システムの構成例を説明する。不整合検知システムは、n（≧3）台の不整合検知装置１1,…,１nを含む。本形態では、不整合検知装置１1,…,１nはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、不整合検知装置１1,…,１nへ入力する情報を磁気テープやUSBメモリのような可搬型記録媒体に記憶し、その可搬型記録媒体から不整合検知装置１1,…,１nへオフラインで入力するように構成してもよい。
【００２０】
図２を参照して、不整合検知システムに含まれる不整合検知装置１i（i=1,…,n）の構成例を説明する。不整合検知装置１iは、例えば、記憶部１０、公開乱数生成部１１、共有乱数計算部１２、チェックサム計算部１３、乱数分散値生成部１４、判定値計算部１５、判定値通信部１６、判定値復旧部１７、および不整合判定部１８を含む。
【００２１】
不整合検知装置１iは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。不整合検知装置１iは、例えば、中央演算処理装置の制御のもとで各処理を実行する。不整合検知装置１iに入力されたデータや各処理で得られたデータは、例えば、メモリに格納され、メモリに格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。不整合検知装置１iの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２２】
図３を参照して、実施形態の不整合検知方法の処理手続きを説明する。
【００２３】
以下では、p0,…,pn-1をn個のシェアを分散して保有するn台の不整合検知装置とし、p0をn個のシェアに不整合があるか否かを示す検知結果を出力する不整合検知装置とする。p0,…,pn-1は論理的に不整合検知装置の役割を指し示す符号であり、どの不整合検知装置１1,…,１nがどの不整合検知装置p0,…,pn-1に対応するかは実行時に任意に決定される。以降の説明では、1台の不整合検知装置p0が不整合の検知を行う処理手続きを説明するが、n台の不整合検知装置p0,…,pn-1がそれぞれの役割を入れ替えながら並行して同様の処理を行い、任意の複数台の不整合検知装置がそれぞれ検知結果を出力するように構成することも可能である。
【００２４】
n台の不整合検知装置pi（i=0,…,n-1）の記憶部１０には、シェア[a0]i,…,[am-1]iが記憶されている。シェア[a0]i,…,[am-1]iはm（≧1）個の値a0,…,am-1を(k,n)-秘密分散により分散したシェアである。本形態の(k,n)-秘密分散は、k個のシェアから線形結合で復旧および復元が可能な種類の秘密分散であれば、任意のものを利用することができる。
【００２５】
ステップＳ１１において、n台の不整合検知装置piの公開乱数生成部１１は、乱数siを生成する。生成した乱数siは他のn-1台の不整合検知装置pi'（i'=0,…,n-1、i≠i'）から参照できるように公開する。
【００２６】
ステップＳ１２において、n台の不整合検知装置piの共有乱数計算部１２は、自身が生成した乱数siと他のn-1台の不整合検知装置pi'が公開する乱数si'を併せたn個の乱数s0,…,sn-1を用いて、次式により共有乱数sを計算する。
【数２】
0005860556.tif 000003
【００２７】
ステップＳ１３において、n台の不整合検知装置piのチェックサム計算部１３は、共有乱数計算部１２が計算した共有乱数sと、記憶部１０に記憶されたシェア[a0]i,…,[am-1]iとを用いて、次式によりチェックサム[c]iを計算する。
【数３】
0005860556.tif 000004
【００２８】
ステップＳ１４において、n台の不整合検知装置piの乱数分散値生成部１４は、復元すると乱数rになるシェア[r]iを生成する。シェア[r]iの生成は、いずれの不整合検知装置１1,…,１nからも乱数rが秘匿された状態で行われなければならない。例えば、以下のようにして分散値[r]を生成することができる。まず、不整合検知装置１iそれぞれが乱数riを生成する。次に、不整合検知装置１iそれぞれが、(k,n)-秘密分散により乱数riの分散値[ri]を生成する。そして、不整合検知装置１iそれぞれが、[r]=Σi<n[ri]を計算し、乱数rの分散値[r]を得る。このように構成すれば、いずれの不整合検知装置１1,…,１nも乱数rを知ることがなく、乱数rの分散値[r]を得ることができる。また、事前の乱数共有や疑似乱数の利用を許すことが可能であれば、複製型秘密分散を利用して乱数rの分散値[r]を生成することができる。複製型秘密分散を利用すれば不整合検知装置１1,…,１n間での通信なしに乱数rの分散値[r]を生成することができる。
【００２９】
ステップＳ１５において、n台の不整合検知装置piの判定値計算部１５は、復元すると判定値dとなるシェア[d]i=[c-r]iを計算する。シェア同士の減算は不整合検知装置１1,…,１n間での通信なしに行うことができる。
【００３０】
ステップＳ１６ａにおいて、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を復旧する。Shamir秘密分散の場合には、ラグランジュ補間により、k個のシェアから他のn-k個のシェアを復旧することが可能である。複製型秘密分散では、k個のシェアに含まれるサブシェアを組み合わせることで他のn-k個のシェアを復旧することが可能である。
【００３２】
ステップＳ１８において、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など）を出力する。不整合があったと判定した場合には、その旨を示す情報（例えば、「⊥」など）を出力する。
【００３３】
本形態では、ステップＳ１３において、乱数を変数とする多項式の係数に入力のシェアを埋め込んでいる。秘密分散が体上で行われている場合、改ざんされた断片に不正に加算された値x0,…,xm-1（秘密分散で使う代数構造は群であり、加算で全ての値を表現できる）は乱数が掛かり、si+1xiのような乱数となる。最後の復元でこの乱数の和が0(つまり検知漏れ)となる確率は高々m/|F|程度であり、|F|が大きいとき無視できる。
【００３４】
本形態の不整合検知システムおよび方法は、断片数に関わらず、通信量はO(1)、通信段数はO(1)ラウンドとなり、非常に効率的である。
【００３５】
［第二実施形態］
第一実施形態の不整合検知システムおよび方法では、複数のシェアに対して、全体としての不整合の有無しか検知することができない。しかし、第一実施形態の方法を反復することで、不整合のあったシェアを特定することができる。特に、不整合のあるシェアの数が少ない場合には効率的である。
【００３６】
本形態の不整合検知方法では、シェア[a0],…,[am-1]を2つのグループ（例えば、[a0],…,[am/2-1]と[am/2],…,[am-1]など。）に分割し、それぞれのグループに対して第一実施形態の方法で不整合の有無を検知する。不整合があったグループ（例えば、[a0],…,[am/2-1]に不整合があったとする。）については、さらに2つのグループ（例えば、[a0],…,[am/4-1]と[am/4],…,[am/2-1]など。）に分割し、第一実施形態の方法で不整合の有無を検知する。これを繰り返してグループに含まれるシェアが一つになれば不整合のあるシェアを特定できる。
【００３７】
本形態の不整合検知システムおよび方法は、繰り返し回数が最大でlog mとなるため、通信量がO(log m)、通信段数はO(log m)ラウンドとなる。特に不整合のある断片数が小さいときは繰り返し回数が少なくて済むため効率的である。
【００３８】
［第三実施形態］
第二実施形態の方法でも、秘密分散されたn個のシェアのうちどのシェアが不正なのかは検知することができない。しかし、上述の実施形態の方法は、nをシェアの総数とし、kを復元に必要なシェアの数として、n=2k-1の場合に実行可能である。そこで、n>2k-1のときには、n台の不整合検知装置のうち2k-1台の不整合検知装置を選択して、上述の実施形態の方法により不整合検知を行うことを繰り返す。すると、不整合が検出された場合に共通して処理を行った不整合検知装置が保持しているシェアが不正なシェアであることを検知することができる。
【００３９】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４０】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４２】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４５】
１  不整合検知装置
２  通信網
１０  記憶部
１１  公開乱数生成部
１２  共有乱数計算部
１３  チェックサム計算部
１４  乱数分散値生成部
１５  判定値計算部
１６  判定値通信部
１７  判定値復旧部
１８  不整合判定部
【要約】
【課題】少ない通信量でシェアの不整合を検知する。
【解決手段】n台の不整合検知装置が乱数siを生成し公開する。n台の不整合検知装置が乱数s0,…,sn-1の総和である共有乱数sを生成する。n台の不整合検知装置がシェア[c]iを計算する。n台の不整合検知装置が復元すると乱数rになるシェア[r]iを生成する。n台の不整合検知装置が復元すると判定値dになるシェア[d]iを計算する。1台の不整合検知装置がn-1台の不整合検知装置からシェア[d]1,…,[d]n-1を受信する。1台の不整合検知装置がk個のシェア[d]0,…,[d]k-1からn-k個のシェア[d]'k,…,[d]'n-1を復旧する。1台の不整合検知装置がj=k,…,n-1についてシェア[d]jとシェア[d]'jとが一致するか否かを判定する。
【選択図】図３【図１】
0005860556.tif 000005
【図２】
0005860556.tif 000006
【図３】
0005860556.tif 000007