(57)【特許請求の範囲】
【請求項１】
N台の秘密計算装置が、M個の値a0,…,aM-1を秘密分散した分散値[a0],…,[aM-1]を入力とし、J種類の秘密分散を使う秘密計算を行う関数Fによる関数値[F([a0],…,[aM-1])]を出力とし、秘密計算中の改ざんを検知する秘密改ざん検知方法であって、
Nを3以上の整数とし、Mを1以上の整数とし、μを1以上の整数とし、Jを2以上の整数とし、mを0以上M未満の整数とし、jを0以上J未満の整数とし、
上記秘密計算装置の乱数生成部が、J個の乱数r0,…,rJ-1を秘密分散した分散値[r0],…,[rJ-1]を求める乱数生成ステップと、
上記秘密計算装置のランダム化部が、m番目の分散値[am]がj番目の秘密分散の分散値であるとし、上記分散値[am]と上記分散値[rj]とを積算した分散値[amrj]を計算し、上記分散値[am]と上記分散値[amrj]とを組としたランダム化分散値<am>:=<[am],[amrj]>を生成するランダム化ステップと、
上記秘密計算装置の秘密計算部が、j番目の秘密分散を用いる秘密計算を行う際に、計算対象のランダム化分散値と計算結果のランダム化分散値をチェックサムCjへ含めながら、上記関数値[F([a0],…,[aM-1])]を求める秘密計算ステップと、
上記秘密計算装置の同期部が、すべての秘密分散を使う秘密計算が終了するまで待機する同期ステップと、
上記秘密計算装置の正当性証明部が、j=0,…,J-1について、μjをj番目のチェックサムCjに含まれるランダム化分散値の総数とし、<f0>,…,<fμj-1>をj番目のチェックサムCjに含まれるランダム化分散値とし、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0],…,[fμj-1]の総和に上記分散値[rj]を乗じた分散値[φj]と、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0rj],…,[fμj-1rj]の総和である分散値[ψj]とが等しいか否かを検証する正当性証明ステップと、
を含む秘密改ざん検知方法。
【請求項２】
請求項１に記載の秘密改ざん検知方法であって、
j'を0以上J未満の整数とし、j≠j'とし、j番目の秘密分散とj'番目の秘密分散とが同一の環上の秘密分散であるとし、j番目の秘密分散からj'番目の秘密分散へ改ざん検知可能もしくは改ざん不可能な方式により変換可能であるとし、
上記乱数生成ステップは、乱数rjをj番目の秘密分散により秘密分散した分散値[rj]を生成し、上記分散値[rj]をj'番目の秘密分散へ変換して分散値[rj']を生成するものである
秘密改ざん検知方法。
【請求項３】
請求項２に記載の秘密改ざん検知方法であって、
上記正当性証明ステップは、j番目のチェックサムCjから算出した上記分散値[φj]と上記チェックサムCjから算出した上記分散値[ψj]とをそれぞれj'番目の秘密分散へ変換し、上記分散値[φj]とj'番目のチェックサムCj'から算出した上記分散値[φj']とを合算した分散値[φj+φj']と、上記分散値[ψj]とj'番目のチェックサムCj'から算出した上記分散値[ψj']とを合算した分散値[ψj+ψj']とが等しいか否かを検証するものである
秘密改ざん検知方法。
【請求項４】
請求項１から３のいずれかに記載の秘密改ざん検知方法であって、
上記秘密計算ステップと上記同期ステップと上記正当性証明ステップとを複数回繰り返し実行する
秘密改ざん検知方法。
【請求項５】
N台の秘密計算装置が、M個の値a0,…,aM-1を秘密分散した分散値[a0],…,[aM-1]を入力とし、J種類の秘密分散を使う秘密計算を行う関数Fによる関数値[F([a0],…,[aM-1])]を出力とし、秘密計算中の改ざんを検知する秘密改ざん検知システムであって、
Nを3以上の整数とし、Mを1以上の整数とし、μを1以上の整数とし、Jを2以上の整数とし、mを0以上M未満の整数とし、jを0以上J未満の整数とし、
上記秘密計算装置は、
J個の乱数r0,…,rJ-1を秘密分散した分散値[r0],…,[rJ-1]を求める乱数生成部と、
m番目の分散値[am]がj番目の秘密分散の分散値であるとし、上記分散値[am]と上記分散値[rj]とを積算した分散値[amrj]を計算し、上記分散値[am]と上記分散値[amrj]とを組としたランダム化分散値<am>:=<[am],[amrj]>を生成するランダム化部と、
j番目の秘密分散を用いる秘密計算を行う際に、計算対象のランダム化分散値と計算結果のランダム化分散値をチェックサムCjへ含めながら、上記関数値[F([a0],…,[aM-1])]を求める秘密計算部と、
すべての秘密分散を使う秘密計算が終了するまで待機する同期部と、
j=0,…,J-1について、μjをj番目のチェックサムCjに含まれるランダム化分散値の総数とし、<f0>,…,<fμj-1>をj番目のチェックサムCjに含まれるランダム化分散値とし、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0],…,[fμj-1]の総和に上記分散値[rj]を乗じた分散値[φj]と、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0rj],…,[fμj-1rj]の総和である分散値[ψj]とが等しいか否かを検証する正当性証明部と、
を含む秘密改ざん検知システム。
【請求項６】
M個の値a0,…,aM-1を秘密分散した分散値[a0],…,[aM-1]を入力とし、J種類の秘密分散を使う秘密計算を行う関数Fによる関数値[F([a0],…,[aM-1])]を出力とし、秘密計算中の改ざんを検知する秘密計算装置であって、
Nを3以上の整数とし、Mを1以上の整数とし、μを1以上の整数とし、Jを2以上の整数とし、mを0以上M未満の整数とし、jを0以上J未満の整数とし、
J個の乱数r0,…,rJ-1を秘密分散した分散値[r0],…,[rJ-1]を求める乱数生成部と、
m番目の分散値[am]がj番目の秘密分散の分散値であるとし、上記分散値[am]と上記分散値[rj]とを積算した分散値[amrj]を計算し、上記分散値[am]と上記分散値[amrj]とを組としたランダム化分散値<am>:=<[am],[amrj]>を生成するランダム化部と、
j番目の秘密分散を用いる秘密計算を行う際に、計算対象のランダム化分散値と計算結果のランダム化分散値をチェックサムCjへ含めながら、上記関数値[F([a0],…,[aM-1])]を求める秘密計算部と、
すべての秘密分散を使う秘密計算が終了するまで待機する同期部と、
j=0,…,J-1について、μjをj番目のチェックサムCjに含まれるランダム化分散値の総数とし、<f0>,…,<fμj-1>をj番目のチェックサムCjに含まれるランダム化分散値とし、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0],…,[fμj-1]の総和に上記分散値[rj]を乗じた分散値[φj]と、上記チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0rj],…,[fμj-1rj]の総和である分散値[ψj]とが等しいか否かを検証する正当性証明部と、
を含む秘密計算装置。
【請求項７】
請求項６に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密計算技術に関し、特に秘密計算中の改ざんを検知する技術に関する。
【背景技術】
【０００２】
秘密計算中の改ざんを検知する従来技術として、非特許文献１に記載の方法がある。非特許文献１に記載の秘密改ざん検知方法では、環R上の加算・定数倍・乗算・積和・ランダム置換から構成されるm入力μ出力の関数Fを秘匿性および正当性をもつmaliciousモデル上で計算する。なお、maliciousモデルとは、攻撃者が任意の不正な動作を行うモデルである。対してsemi-honestモデルは、攻撃者の行う処理は正しく、その範疇でデータを盗み見ようとするモデルである。
【０００３】
非特許文献１では、３つのフェーズで秘密計算中の改ざん検知を行う。ランダム化フェーズでは、分散値を正当性検証可能なランダム化分散値へと変換する。計算フェーズでは、semi-honestの演算により構成されるランダム化分散値用の演算を用いて所望の秘密計算を実行する。このとき、後続の正当性証明フェーズで必要となるチェックサムを収集しながら計算が行われる。正当性証明フェーズでは、計算フェーズで収集されたチェックサムに対して、一括で正当性証明を行う。正当であれば計算フェーズによる計算結果を出力し、正当でなければ計算結果は出力せずに正当でない旨のみを出力する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】五十嵐大、千田浩司、濱田浩気、菊池亮、“非常に高効率なn≧2k-1 malicious モデル上秘密分散ベースマルチパーティ計算の構成法”、SCIS2013、2013年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載の秘密改ざん検知技術では、１つの秘密分散を使用する秘密計算を前提としており、複数の秘密分散を使用する秘密計算には適用することができなかった。
【０００６】
この発明の目的は、このような点に鑑みて、複数の秘密分散を使用する秘密計算中の改ざんを検知することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の秘密改ざん検知方法は、N台の秘密計算装置が、M個の値a0,…,aM-1を秘密分散した分散値[a0],…,[aM-1]を入力とし、J種類の秘密分散を使う秘密計算を行う関数Fによる関数値[F([a0],…,[aM-1])]を出力とし、秘密計算中の改ざんを検知する秘密改ざん検知方法であって、Nを3以上の整数とし、Mを1以上の整数とし、μを1以上の整数とし、Jを2以上の整数とし、mを0以上M未満の整数とし、jを0以上J未満の整数とし、秘密計算装置の乱数生成部が、J個の乱数r0,…,rJ-1を秘密分散した分散値[r0],…,[rJ-1]を求める乱数生成ステップと、秘密計算装置のランダム化部が、m番目の分散値[am]がj番目の秘密分散の分散値であるとし、分散値[am]と分散値[rj]とを積算した分散値[amrj]を計算し、分散値[am]と分散値[amrj]とを組としたランダム化分散値<am>:=<[am],[amrj]>を生成するランダム化ステップと、秘密計算装置の秘密計算部が、j番目の秘密分散を用いる秘密計算を行う際に、計算対象のランダム化分散値と計算結果のランダム化分散値をチェックサムCjへ含めながら、関数値[F([a0],…,[aM-1])]を求める秘密計算ステップと、秘密計算装置の同期部が、すべての秘密分散を使う秘密計算が終了するまで待機する同期ステップと、秘密計算装置の正当性証明部が、j=0,…,J-1について、μjをj番目のチェックサムCjに含まれるランダム化分散値の総数とし、<f0>,…,<fμj-1>をj番目のチェックサムCjに含まれるランダム化分散値とし、チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0],…,[fμj-1]の総和に分散値[rj]を乗じた分散値[φj]と、チェックサムCj:=(<f0>,…,<fμj-1>)に含まれる分散値[f0rj],…,[fμj-1rj]の総和である分散値[ψj]とが等しいか否かを検証する正当性証明ステップと、を含む。
【発明の効果】
【０００８】
この発明の秘密改ざん検知技術によれば、複数の秘密分散を使用する秘密計算中の改ざんを検知できる。
【図面の簡単な説明】
【０００９】
【図１】図１は、秘密改ざん検知システムの機能構成を例示する図である。
【図２】図２は、秘密計算装置の機能構成を例示する図である。
【図３】図３は、秘密改ざん検知方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法およびこの発明の基本的な考え方について説明する。
【００１１】
［表記方法］
この発明で扱う値は、特に断りのない限り環R上の値とする。Aは環R上の結合多元環である。結合多元環とは、結合的な環であって、かつそれと両立するような、何らかの体上の線型空間の構造を備えたものである。結合多元環は、ベクトル空間で扱う値が体ではなく環でよくなったものと言える。
【００１２】
ベクトルXの第i要素をXi（下付き添字）で参照する。
【００１３】
[x]は値x∈Rの秘匿文である。秘匿文は値を暗号化や秘密分散などの手段で秘匿化した値である。Xが集合である場合には、[X]は集合Xの各要素を秘匿化した集合である。
【００１４】
|X|は集合Xの要素数である。
【００１５】
<x>は値x∈Rのランダム化分散値である。ランダム化分散値とは、値x∈Rの分散値[x]と、値xと乱数r∈Aとの積算値xrの分散値[xr]との組である。したがって、ランダム化分散値は式（１）のように定義できる。
【数１】
0006053238.tif 000002
【００１６】
ランダム化分散値の第０成分（式（１）における[x]）はR成分、第１成分（式（１）における[xr]）はA成分とも呼ぶ。
【００１７】
乱数r∈Aをパラメータとするランダム化分散値の空間を<Rr>とする。
【００１８】
［安全性］
暗号理論の技術分野ではプロトコルの安全性を証明するために利用者・参加者や攻撃者をモデル化する。このようなモデルとして、maliciousモデルやsemi-honestモデルが用いられている。maliciousモデルは攻撃者が任意の不正な動作を行う。semi-honestモデルは攻撃者の行う処理は正しく、その範疇でデータを盗み見ようとする。したがって、maliciousモデルにおいて安全性が証明されたプロトコルの方がより安全性が高いと評価できる。
【００１９】
［発明のポイント］
従来の秘密改ざん検知技術では、一つの秘密分散を使用する秘密計算しか対応できず、複数の秘密分散を使用する秘密計算では改ざん検知ができなかった。複数の秘密分散を使用する場合、秘密分散ごとに従来の秘密改ざん検知技術を用いて個別に検証すればよいようにも思えるが、そのような実装では安全性の問題がある。この発明では、複数の秘密分散を使用する秘密計算において適切な安全性を確保するために、以下の条件を満たすように構成する。
１．同じ環上の秘密分散ではランダム化分散値を生成する際の乱数の値が一致している。２．正当性検証を行う前にすべての秘密分散において秘密計算が完了している。
【００２０】
また、各秘密分散を個別に検証するよりも、可能な限りまとめて検証を行う方が公開される値が少なくなるため秘匿性が向上する。そこで、同じ環上の秘密分散では、チェックサムの秘密分散形式を統一し、まとめて検証を行うように構成する。
【００２１】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２２】
図１を参照して、実施形態の秘密改ざん検知システムの構成例を説明する。秘密改ざん検知システムは、N（≧3）台の秘密計算装置１1,…,１Nを含む。本形態では、秘密計算装置１1,…,１Nはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１1,…,１Nへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密計算装置１1,…,１Nへオフラインで入力するように構成してもよい。
【００２３】
図２を参照して、秘密改ざん検知システムに含まれる秘密計算装置１n（n=1,…,N）の構成例を説明する。秘密計算装置１nは、例えば、制御部１０１、記憶部１０２、入力部１１、乱数生成部１２、ランダム化部１３、秘密計算部１４、同期部１５、正当性証明部１６、および出力部１７を含む。
【００２４】
秘密計算装置１nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１nは、例えば、制御部１０１の制御のもとで各処理を実行する。秘密計算装置１nに入力されたデータや各処理で得られたデータは、例えば、記憶部１０２に格納され、記憶部１０２に格納されたデータは必要に応じて制御部１０１へ読み出されて他の処理に利用される。秘密計算装置１nの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２５】
図３を参照して、実施形態の秘密改ざん検知方法の処理手続きを説明する。
【００２６】
ステップＳ１１において、秘密計算装置１nの入力部１１へM（≧1）個の分散値[a0],…,[aM-1]が入力される。入力された分散値[a0],…,[aM-1]はランダム化部１３へ出力される。分散値[am]（m=0,…,M-1）は、値amを秘密分散した分散値である。入力される分散値[a0],…,[aM-1]の個数Mは、秘密計算部１４で行われる秘密計算の内容により適宜決定される。
【００２７】
秘密分散の方法は、秘密計算上で所望の演算が可能な秘密分散方式であればどのような秘密分散方式であってもよい。本形態の分散値[a0],…,[aM-1]はJ（≧2）種類の秘密分散による分散値が混在していることを前提とする。また、複数の秘密分散は同一の環上の秘密分散であってもよいし、異なる環上の秘密分散であってもよい。また、同一の環上の複数の秘密分散と異なる環上の秘密分散とが混在していてもよい。なお、分散値[a0],…,[aM-1]が、入力時には1種類の秘密分散による分散値のみであり、秘密計算の中で形式変換を行うなどにより、全体として複数の秘密分散が利用されている場合であっても、この発明の改ざん検知技術は適用可能である。適用可能な秘密分散方法についての詳細は、下記参考文献１などを参照されたい。
〔参考文献１〕千田浩司、濱田浩気、五十嵐大、高橋克己、“軽量検証可能３パーティ秘匿関数計算の再考”、CSS2010、2010年
【００２８】
ステップＳ１２において、乱数生成部１２は、結合多元環Aから選択したJ個の乱数r0,…,rJ-1∈Aの分散値[r0],…,[rJ-1]を生成する。生成した分散値[r0],…,[rJ-1]はランダム化部１３に出力される。分散値[r0],…,[rJ-1]の生成は、いずれの秘密計算装置１1,…,１Nからも乱数r0,…,rJ-1が秘匿された状態で行われなければならない。
【００２９】
例えば、秘密改ざん検知システムを構成する秘密計算装置１1,…,１Nが協調して乱数rjの分散値[rj]を生成することができる。具体的には、まず、秘密計算装置１nはそれぞれが乱数rnを生成する。次に、上記の参考文献１に記載された秘匿方法により乱数rnの分散値[rn]を生成する。そして、秘密計算装置１nはそれぞれ[rj]=Σn<N[rn]を計算し、乱数rjの分散値[rj]を得る。このように構成すれば、いずれの秘密計算装置１1,…,１Nも乱数rjを知ることなく、乱数rjの分散値[rj]を得ることができる。また、事前の乱数共有や疑似乱数の利用を許すことが可能であれば、複製型秘密分散（replicated secret sharing）を利用して乱数rjの分散値[rj]を生成することができる。複製型秘密分散を利用すれば秘密計算装置１1,…,１N間での通信なしに乱数rjの分散値[rj]を生成することができる。複製型秘密分散の詳細については、下記参考文献２を参照されたい。
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, Springer, 2005. 
【００３０】
J個の秘密分散のうち同一の環上の秘密分散が存在する場合には、一方の秘密分散のための分散値を他方の秘密分散のための分散値に変換することで、乱数の値が同一となるように生成する。この形式変換においても、改ざん検知が可能もしくは改ざんが不可能でなければならない。例えば、j（j=0,…,J-1）番目の秘密分散とj'（j'=0,…,J-1、j≠j'）番目の秘密分散が同一の環上の秘密分散である場合には、j番目の秘密分散のための乱数rjを秘密分散した分散値[rj]を生成し、その分散値[rj]を改ざん検知可能もしくは改ざん不可能な方法によりj'番目の秘密分散による分散値[rj']に形式変換する。例えば、複製型秘密分散から線形秘密分散（linear secret sharing）へ変換する改ざん不可能な方法は、上記参考文献２に記載されている。
【００３１】
ステップＳ１３において、ランダム化部１３は、分散値[a0],…,[aM-1]と分散値[r0],…,[rJ-1]とを用いて、ランダム化分散値<a0>,…,<aM-1>を生成する。具体的には、ランダム化部１３は、m=0,…,M-1について、m番目の分散値[am]がj番目の秘密分散による分散値であるとして、分散値[am]と分散値[rj]とを用いて、[amrj]=[am]×[rj]を上記参考文献１に記載された秘密計算方法により求め、分散値[am]と分散値[amrj]とを組としてランダム化分散値<am>=([am],[amrj])を生成する。生成したランダム化分散値<a0>,…,<aM-1>は秘密計算部１４へ出力される。
【００３２】
ステップＳ１４において、秘密計算部１４は、ランダム化分散値<a0>,…,<aM-1>に対して、J種類の秘密分散を使用する秘密計算を実行する関数Fを計算して秘匿された関数値[F([a0],…,[aM-1])]を求める。この際、使用する秘密分散の種類に対応するJ個のチェックサムへ計算対象のランダム化分散値と計算結果のランダム化分散値を含めながら関数Fを計算する。例えば、j（j=0,…,J-1）番目の秘密分散を用いる演算であれば、計算対象のランダム化分散値と計算結果のランダム化分散値をj番目のチェックサムCj:=<f0>,…,<fμj-1>へ追加する。ここで、<f0>,…,<fμj-1>は計算対象もしくは計算結果の各ランダム化分散値であり、下付き添え字の「μj-1」はμj-1を表しており、μjはチェックサムCjに含まれるランダム化分散値の数である。μjの値は初期値を0としてチェックサムCjにランダム化分散値を新たに含めるたびに加算される。チェックサムに含める対象のランダム化分散値やチェックサムにランダム化分散値を取得するべきタイミングは、秘密計算の演算の種類（例えば、加算・定数倍、乗算、積和、ランダム置換など）によって異なる。これらの詳細は、非特許文献１に記載の秘密改ざん検知方法と同様である。
【００３３】
ステップＳ１５において、同期部１５は、正当性証明を行う前に、すべての秘密分散についてすべての秘密計算が終了するまで待機する同期処理（SYNC）を実行する。同期部１５は、すべての秘密分散についてすべての秘密計算が終了したことを検知すると、秘密計算部１４により求められた関数値[F([a0],…,[aM-1])]と、J個のチェックサムC0,…,CJ-1を正当性証明部１６へ出力する。
【００３４】
ステップＳ１６において、正当性証明部１６は、分散値[r0],…,[rJ-1]を用いてチェックサムC0,…,CJ-1を検証することで、関数値[F([a0],…,[aM-1])]の正当性を証明する。J個のチェックサムC0,…,CJ-1すべてを検証した結果、改ざんがないと判定した場合は関数値[F([a0],…,[aM-1])]を出力部１７へ出力する。改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力部１７へ出力する。
【００３５】
ステップＳ１６において改ざんがないと判定した場合であって、所望の関数を計算するための後続の処理が残されている場合には、再度ステップＳ１４に戻り、秘密計算から正当性証明まで処理を繰り返し実行してもよい。この際、正当性証明が完了するたびに、チェックサムC0,…,CJ-1に含まれるランダム化分散値を破棄してもよい。このような秘密計算と正当性証明の繰り返しは、改ざんされていないことが保証された値を公開し、その値を用いて後続の処理を行うような場合に必要となる。改ざんされた値が公開されることは、秘匿性を損なう原因となる場合があるためである。
【００３６】
ステップＳ１７において、出力部１７は、正当性証明部１６から受け取った関数値[F([a0],…,[aM-1])]もしくは改ざんがあった旨を示す情報を出力する。
【００３７】
j番目のチェックサムCjの検証は、チェックサムCjに含まれるランダム化分散値のR成分[f0],…,[fμj-1]の総和に分散値[rj]を乗じた分散値[φj]と、チェックサムCjに含まれるランダム化分散値のA成分[f0rj],…,[fμj-1rj]の総和である分散値[ψj]とに基づいて行われる。具体的には、正当性証明部１６は、例えば、以下のようにしてチェックサムCjを検証する。まず、結合多元環A上のμj個の乱数ρ0,…,ρμj-1の分散値[ρ0],…,[ρμj-1]を生成する。分散値[ρ0],…,[ρμj-1]の生成はいずれの秘密計算装置１nからも乱数ρ0,…,ρμj-1が秘匿された状態で行われなければならない。分散値[ρ0],…,[ρμj-1]の生成は、乱数生成部１２と同様の方法により行えばよい。次に、チェックサムCjに含まれるランダム化分散値のR成分[f0],…,[fμj-1]と、乱数ρ0,…,ρμj-1の分散値[ρ0],…,[ρμj-1]と、乱数rjの分散値[rj]とを用いて、以下の式（２）により分散値[φj]を求める。
【数２】
0006053238.tif 000003
【００３８】
また、チェックサムCjに含まれるランダム化分散値のA成分[f0rj],…,[fμj-1rj]と、乱数ρ0,…,ρμj-1の分散値[ρ0],…,[ρμj-1]とを用いて、以下の式（３）により分散値[ψj]を求める。
【数３】
0006053238.tif 000004
【００３９】
そして、分散値[φj]と分散値[ψj]とを減算した分散値[δj]=[φj]-[ψj]を復元する。復元の方法は、各分散値に対応する秘密分散方式の復元操作で行えばよいが、この際、maliciousモデルで正当性を保証する。具体的にはすべての秘密計算装置１n（n=0,…,N-1）が互いに分散値[δj]を他の秘密計算装置１n'（n'=0,…,N-1、n≠n'）へ送信し、分散値の一貫性を確認することで完全な正当性を保証する。この場合、秘密計算装置１nの総数をNとして、総通信量はN(N-1)である。分散値のデータ量が大きいとき、確率的な方法を用いれば、復元に必要な秘密計算装置１nの数をKとして、総通信量をN(K-1)とすることができる。なお、秘密計算には正当性を保証しない復元を含むsemi-honest演算もあるが、秘密計算の構成要素として正当性を保証しない復元が含まれていても、秘密計算全体の安全性には影響しない。
【００４０】
すべての秘密計算装置１1,…,１Nにおいて復元した値δ0,…,δJ-1が0であれば、秘密計算全体を通して改ざんがなかったものと判定する。いずれかの秘密計算装置１jにおいて復元した値δjが0以外であれば、秘密計算において改ざんがあったものと判定する。
【００４１】
J種類の秘密分散のうち同一の環上の秘密分散が存在する場合には、可能な限りまとめて正当性証明を行うと、公開される値の数が少なくなるため、より秘匿性を向上することができる。例えば、j（j=0,…,J-1）番目の秘密分散とj'（j'=0,…,J-1、j≠j'）番目の秘密分散が同一の環上の秘密分散である場合には、以下のように正当性証明を行う。まず、チェックサムCjから上述のように算出した分散値[φj]と、チェックサムCjから上述のように算出した分散値[ψj]とをそれぞれj'番目の秘密分散へ変換する。そして、変換後の分散値[φj]とチェックサムCj'から算出した分散値[φj']とを合算した分散値[φj+φj']と、変換後の分散値[ψj]とj'番目のチェックサムCj'から算出した分散値[ψj']とを合算した分散値[ψj+ψj']とが等しいか否かを検証する。すなわち、すべての同じ環上の秘密分散の組み合わせについて、[δ]=([φj]+[φj'])-([ψj]+[ψj’])を計算し、復元値δが0であれば、j番目の秘密分散とj'番目の秘密分散を用いる秘密計算は全体を通して改ざんがなかったものと判定する。[δ]=([φj]+[φj'])-([ψj]+[ψj’])を計算し、復元値δが0以外であれば、j番目の秘密分散とj'番目の秘密分散を用いる秘密計算のいずれかの演算において改ざんがあったものと判定する。このようにして、すべての同一の環上の秘密分散の組み合わせについて検証し、秘密計算全体で改ざんがなかったことを検証する。本形態では２個の秘密分散が同一の環上の秘密分散である例を説明したが、３個以上の秘密分散が同一の環上の秘密分散である場合でも、同様の方法により正当性証明を行うことができる。
【００４２】
正当性証明の基本的な考え方を説明する。チェックサムの検証は、ランダム化分散値<fi>それぞれに着目すると、[fi][rj]-[firj]=0であるかを検証することである。ここで、分散値[fi]と分散値[firj]がいずれも改ざんされ、[fi+x]と[firj+y]とされた場合を考えると、検証により得られる値は式（４）となる。
【数４】
0006053238.tif 000005
【００４３】
攻撃者はこのxrj-yの値を0となるように辻褄を合わせて[fi]と[firj]を操作しなければならないが、攻撃者は乱数rj∈Aを知らないため、これを満たすようにすることができる確率は、1/|A|となる。ただし、本形態では乱数ρ0,…,ρμj-1を乗じているため全体の改ざん成功確率は高々2/|A|となる。
【００４４】
このようにして、本形態の秘密改ざん検知システムは、複数の秘密分散を用いる秘密計算においても改ざん検知が可能となる。
【００４５】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４６】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４８】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM、USBメモリ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５１】
１  秘密計算装置
２  通信網
１１  入力部
１２  乱数生成部
１３  ランダム化部
１４  秘密計算部
１５  同期部
１６  正当性証明部
１７  出力部
【図１】
0006053238.tif 000006
【図２】
0006053238.tif 000007
【図３】
0006053238.tif 000008