(57)【要約】  少ない通信量で秘匿性を保ったまま秘密計算中の改ざんを検知する。乱数生成部（１１）は、[→ri], [→si]を生成する。乱数乗算部（１２）は、[→ti]:=[→ri→si]を計算する。秘密乗算部（１３）は、[→z]:=[→x→y]を計算する。乱数検証部（１４）は、[→ri], [→si], [→ti]のうちpi,j番目の要素を公開し、乗算として整合しているか否かを確認する。乱数置換部（１５）は、[→ri], [→si], [→ti]のうちpi,j番目以外の要素をランダム置換し、[→r'i], [→s'i], [→t'i]を生成する。減算値公開部（１６）は、[→x-→r'i], [→y-→s'i]を計算する。検証値計算部（１７）は、[→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算する。検証値確認部（１８）は、検証値ciがすべて0であることを確認する。
2018216512.tif 000002
【特許請求の範囲】
【請求項１】
σは1以上の任意の整数を表し、N, Dは所定の自然数を表し、iは0以上σ未満の各整数を表し、jは0以上D未満の各整数を表し、
少なくとも3台の秘密改ざん検知装置を含み、復元すると要素数Nのベクトル→xとなるシェア[→x]と、復元すると要素数Nのベクトル→yとなるシェア[→y]とを入力とし、復元するとベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトル→zとなるシェア[→z]を出力する秘密改ざん検知システムであって、
上記秘密改ざん検知装置は、
各整数iについて、復元すると要素数N+Dの乱数ベクトル→riとなるσ個のシェア[→ri]と、復元すると要素数N+Dの乱数ベクトル→siとなるσ個のシェア[→si]とを生成する乱数生成部と、
各整数iについて、上記シェア[→ri]と上記シェア[→si]とを秘密計算により乗算して、復元するとベクトル→riとベクトル→siとを要素ごとに乗算した結果のベクトル→tiとなるσ個のシェア[→ti]を生成する乱数乗算部と、
上記シェア[→x]と上記シェア[→y]とを秘密計算により乗算して、上記シェア[→z]を生成する秘密乗算部と、
各整数iについて、0以上D+N未満の相異なるD個の整数pi,jをランダムに選択し、上記シェア[→ri], [→si], [→ti]のうちpi,j番目の要素を公開して、上記シェア[→ri], [→si], [→ti]それぞれに対応する公開した値の組が乗算として整合しているか否かを確認する乱数検証部と、
各整数iについて、上記シェア[→ri], [→si], [→ti]のうちpi,j番目以外の要素をランダム置換したシェア[→r'i], [→s'i], [→t'i]を生成する乱数置換部と、
各整数iについて、[→x-→r'i], [→y-→s'i]を計算して公開する減算値公開部と、
各整数iについて、[→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算して、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を生成する検証値計算部と、
各整数iについて、上記シェア[→ci]を用いて、上記検証値ciがすべて0であることを確認する検証値確認部と、
を含む秘密改ざん検知システム。
【請求項２】
請求項１に記載の秘密改ざん検知システムであって、
上記乱数生成部は、改ざん検知付き乱数生成プロトコルを用いて、上記シェア[→ri]および上記シェア[→si]とを生成するものであり、
上記乱数乗算部は、改ざん検知無し乗算プロトコルを用いて、上記シェア[→ri]と上記シェア[→si]とを乗算するものであり、
上記秘密乗算部は、上記改ざん検知無し乗算プロトコルを用いて、上記シェア[→x]と上記シェア[→y]とを乗算するものであり、
上記乱数検証部は、改ざん検知付き公開プロトコルを用いて、上記シェア[→ri], [→si], [→ti]のうちpi,j番目の要素を公開するものであり、
上記減算値公開部は、上記改ざん検知付き公開プロトコルを用いて、上記[→x-→r'i],[→y-→s'i]を公開するものである、
秘密改ざん検知システム。
【請求項３】
請求項１に記載の秘密改ざん検知システムであって、
上記検証値確認部は、上記シェア[→ci]の各要素と乱数rのべき乗との積和からなるチェックサムを計算し、上記チェックサムcが0であるか否かにより、上記検証値ciがすべて0であることを確認するものである、
秘密改ざん検知システム。
【請求項４】
σは1以上の任意の整数を表し、N, Dは所定の自然数を表し、iは0以上σ未満の各整数を表し、jは0以上D未満の各整数を表し、
復元すると要素数Nのベクトル→xとなるシェア[→x]と、復元すると要素数Nのベクトル→yとなるシェア[→y]とを入力とし、復元するとベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトル→zとなるシェア[→z]を出力する秘密改ざん検知装置であって、
各整数iについて、復元すると要素数N+Dの乱数ベクトル→riとなるσ個のシェア[→ri]と、復元すると要素数N+Dの乱数ベクトル→siとなるσ個のシェア[→si]とを生成する乱数生成部と、
各整数iについて、上記シェア[→ri]と上記シェア[→si]とを秘密計算により乗算して、復元するとベクトル→riとベクトル→siとを要素ごとに乗算した結果のベクトル→tiとなるσ個のシェア[→ti]を生成する乱数乗算部と、
上記シェア[→x]と上記シェア[→y]とを秘密計算により乗算して、上記シェア[→z]を生成する秘密乗算部と、
各整数iについて、0以上D+N未満の相異なるD個の整数pi,jをランダムに選択し、上記シェア[→ri], [→si], [→ti]のうちpi,j番目の要素を公開して、上記シェア[→ri], [→si], [→ti]それぞれに対応する公開した値の組が乗算として整合しているか否かを確認する乱数検証部と、
各整数iについて、上記シェア[→ri], [→si], [→ti]のうちpi,j番目以外の要素をランダム置換したシェア[→r'i], [→s'i], [→t'i]を生成する乱数置換部と、
各整数iについて、[→x-→r'i], [→y-→s'i]を計算して公開する減算値公開部と、
各整数iについて、[→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算して、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を生成する検証値計算部と、
各整数iについて、上記シェア[→ci]を用いて、上記検証値ciがすべて0であることを確認する検証値確認部と、
を含む秘密改ざん検知装置。
【請求項５】
σは1以上の任意の整数を表し、N, Dは所定の自然数を表し、iは0以上σ未満の各整数を表し、jは0以上D未満の各整数を表し、
少なくとも3台の秘密改ざん検知装置を含む秘密改ざん検知システムが実行する、復元すると要素数Nのベクトル→xとなるシェア[→x]と、復元すると要素数Nのベクトル→yとなるシェア[→y]とを入力とし、復元するとベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトル→zとなるシェア[→z]を出力する秘密改ざん検知方法であって、
上記秘密改ざん検知装置が、各整数iについて、復元すると要素数N+Dの乱数ベクトル→riとなるσ個のシェア[→ri]と、復元すると要素数N+Dの乱数ベクトル→siとなるσ個のシェア[→si]とを生成し、
上記秘密改ざん検知装置が、各整数iについて、上記シェア[→ri]と上記シェア[→si]とを秘密計算により乗算して、復元するとベクトル→riとベクトル→siとを要素ごとに乗算した結果のベクトル→tiとなるσ個のシェア[→ti]を生成し、
上記秘密改ざん検知装置が、上記シェア[→x]と上記シェア[→y]とを秘密計算により乗算して、上記シェア[→z]を生成し、
上記秘密改ざん検知装置が、各整数iについて、0以上D+N未満の相異なるD個の整数pi,jをランダムに選択し、上記シェア[→ri], [→si], [→ti]のうちpi,j番目の要素を公開して、上記シェア[→ri], [→si], [→ti]それぞれに対応する公開した値の組が乗算として整合しているか否かを確認し、
上記秘密改ざん検知装置が、各整数iについて、上記シェア[→ri], [→si], [→ti]のうちpi,j番目以外の要素をランダム置換したシェア[→r'i], [→s'i], [→t'i]を生成し、
上記秘密改ざん検知装置が、各整数iについて、[→x-→r'i], [→y-→s'i]を計算して公開し、
上記秘密改ざん検知装置が、各整数iについて、[→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算して、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を生成し、
上記秘密改ざん検知装置が、各整数iについて、上記シェア[→ci]を用いて、上記検証値ciがすべて0であることを確認する、
秘密改ざん検知方法。
【請求項６】
請求項４に記載の秘密改ざん検知装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は秘密計算技術に関し、特に、秘匿性を保ったまま秘密計算中の改ざんを検知する技術に関する。
【背景技術】
【０００２】
秘密計算において秘匿性を保ったまま改ざんを検知する技術には、例えば、非特許文献１に記載された技術がある。非特許文献１に記載された従来技術では、multiplication tripleと呼ばれる事前データを生成し、そのmultiplication tripleを用いて秘密計算中の改ざんを検知する技術が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein. "High-throughput secure three-party computation for malicious adversaries and an honest majority". IACR Cryptology ePrint Archive, 2016:944, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術ではmultiplication tripleを事前に生成する必要があり、これにより通信量が増加する場合がある。【０００５】
この発明の目的は、少ない通信量で秘匿性を保ったまま秘密計算中の改ざんを検知することができる秘密改ざん検知技術を提供することである。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、この発明の秘密改ざん検知システムは、σは1以上の任意の整数を表し、N, Dは所定の自然数を表し、iは0以上σ未満の各整数を表し、jは0以上D未満の各整数を表し、少なくとも3台の秘密改ざん検知装置を含み、復元すると要素数Nのベクトル→xとなるシェア[→x]と、復元すると要素数Nのベクトル→yとなるシェア[→y]とを入力とし、復元するとベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトル→zとなるシェア[→z]を出力する秘密改ざん検知システムであって、秘密改ざん検知装置は、各整数iについて、復元すると要素数N+Dの乱数ベクトル→riとなるσ個のシェア[→ri]と、復元すると要素数N+Dの乱数ベクトル→siとなるσ個のシェア[→si]とを生成する乱数生成部と、各整数iについて、シェア[→ri]とシェア[→si]とを秘密計算により乗算して、復元するとベクトル→riとベクトル→siとを要素ごとに乗算した結果のベクトル→tiとなるσ個のシェア[→ti]を生成する乱数乗算部と、シェア[→x]とシェア[→y]とを秘密計算により乗算して、シェア[→z]を生成する秘密乗算部と、各整数iについて、0以上D+N未満の相異なるD個の整数pi,jをランダムに選択し、シェア[→ri], [→si], [→ti]のうちpi,j番目の要素を公開して、シェア[→ri], [→si], [→ti]それぞれに対応する公開した値の組が乗算として整合しているか否かを確認する乱数検証部と、各整数iについて、シェア[→ri], [→si], [→ti]のうちpi,j番目以外の要素をランダム置換したシェア[→r'i], [→s'i], [→t'i]を生成する乱数置換部と、各整数iについて、[→x-→r'i], [→y-→s'i]を計算して公開する減算値公開部と、各整数iについて、[→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算して、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を生成する検証値計算部と、各整数iについて、シェア[→ci]を用いて、検証値ciがすべて0であることを確認する検証値確認部と、を含む。
【発明の効果】
【０００７】
この発明によれば、少ない通信量で秘匿性を保ったまま秘密計算中の改ざんを検知することができる。
【図面の簡単な説明】
【０００８】
【図１】図１は、秘密改ざん検知システムの機能構成を例示する図である。
【図２】図２は、秘密改ざん検知装置の機能構成を例示する図である。
【図３】図３は、秘密改ざん検知方法の処理フローを例示する図である。
【発明を実施するための形態】
【０００９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１０】
本明細書中で使用する、上付き添え字の右矢印「→」は、ベクトルであることを表す。「→」は、本来直後の文字の真上に記載されるべきものであるが、テキスト記法の制限により、当該文字の直前に記載する。数式中においては、これらの記号は本来の位置、すなわち当該文字の真上に記述する。例えば、「→x」とのテキストは、数式中の次式と同じ意味である。
【００１１】
【数１】
2018216512.tif 000003
【００１２】
[x]は、ある値xが秘密分散されていることを表す。[X]は、ある集合Xの元がすべて秘密分散されたデータの集合を表す。以下、秘密分散された値を「シェア」とも呼ぶ。→x→yは、ベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトルを表す。Fは、任意の体を表す。
【００１３】
この発明の実施形態は、非特許文献１に記載された改ざん検知技術を改良した改ざん検知付き乗算を行う秘密改ざん検知システムおよび方法である。実施形態の秘密改ざん検知システムおよび方法は、次式に示す改ざん検知付き乗算プロトコルを実行する。
【００１４】
Scheme 1: 改ざん検知付き乗算
入力: [→x], [→y]∈[F]N
出力: [→x→y]∈[F]N, ただし改ざん検知した場合は出力なし
パラメータ: σ≧1, D∈N
1: 乱数ベクトル[→ri], [→si]∈[F]N+Dを生成する
2: 各0≦i<σで、[→ti]:=[→ri→si]を計算する
3: [→z]:=[→x→y]を計算し、計算に係る通信が完了したことを確認する
4: 各0≦i<σで、位置pi,0, …, pi,D-1をランダムに選ぶ
ベクトル[→ri], [→si], [→ti]のうち各0≦j<Dに対応するpi,j番目の要素を公開し、値が乗算として整合していることを確認する
整合していない場合、改ざんを検知して終了する
公開していない残りの要素をランダム置換πiにより置換し、ベクトル[→r'i], [→s'i], [→t'i]∈[F]Nを得る
5: [→x-→r'i], [→y-→s'i]を公開する
6: [→ci]:=[→z]-(→x-→r'i)[→y]-(→y-→s'i)[→r'i]-[→t'i]を計算する
7: 各0≦i<σで、[→ci]の全要素が0であることを確認する
0以外が存在する場合、改ざんを検知して終了する
【００１５】
上記の改ざん検知付き乗算プロトコルでは、以下３つの秘密計算プロトコルを用いる。１つ目は、ステップ２、３で実行される改ざん検知無し乗算プロトコルである。既存の改ざん検知無し乗算プロトコルは、例えば、参考文献１などに記載されている。２つ目は、ステップ１で実行される改ざん検知付き乱数生成プロトコルである。既存の改ざん検知付き乱数生成プロトコルは、例えば、参考文献２などに記載されている。３つ目は、ステップ４、５で実行される改ざん検知付き公開プロトコルである。既存の改ざん検知付き公開プロトコルは、例えば、参考文献３などに記載されている。
〔参考文献１〕D. Ikarashi, R. Kikuchi, K. Hamada, and K. Chida. "Actively private and correctMPC scheme in t<n/2 from passively secure schemes with small overhead", IACR Cryptology ePrint Archive, 2014:304, 2014.
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai. "Share conversion, pseudorandom secret-sharingand applications to secure computation", TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362. Springer, 2005.
〔参考文献３〕特開２０１６−１４６５３０号公報
【００１６】
図１を参照して、実施形態の秘密改ざん検知システムの構成例を説明する。秘密改ざん検知システムは、K（≧3）台の秘密改ざん検知装置１1, …, １Kを含む。本形態では、秘密改ざん検知装置１1, …, １Kはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密改ざん検知装置１1, …, １Kへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密改ざん検知装置１1, …, １Kへオフラインで入力するように構成してもよい。
【００１７】
図２を参照して、秘密改ざん検知システムに含まれる秘密改ざん検知装置１k（k=1, …, K）の構成例を説明する。秘密改ざん検知装置１kは、例えば、図２に示すように、入力部１０、乱数生成部１１、乱数乗算部１２、秘密乗算部１３、乱数検証部１４、乱数置換部１５、減算値計算部１６、検証値計算部１７、検証値確認部１８、および出力部１９を含む。この秘密改ざん検知装置１k（1≦k≦K）が他の秘密改ざん検知装置１k'（k'=1, …, K、ただしk≠k'）と協調しながら後述する各ステップの処理を行うことにより実施形態の秘密改ざん検知方法が実現される。
【００１８】
秘密改ざん検知装置１kは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密改ざん検知装置１kは、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密改ざん検知装置１kに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密改ざん検知装置１kの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００１９】
図３を参照して、実施形態の秘密改ざん検知システムが実行する秘密改ざん検知方法の処理手続きを説明する。
【００２０】
ステップＳ１において、各秘密改ざん検知装置１kの入力部１０へ、乗算対象とするシェア[→x], [→y]∈[F]Nが入力される。[→x]は、復元すると要素数Nのベクトル→xとなるシェアである。[→y]は、復元すると要素数Nのベクトル→yとなるシェアである。入力部１０は、シェア[→x], [→y]を秘密乗算部１３へ入力する。
【００２１】
ステップＳ２において、各秘密改ざん検知装置１kの乱数生成部１１は、0≦i<σを満たす各整数iについて、改ざん検知付き乱数生成プロトコルを用いて、復元すると要素数N+Dの乱数ベクトル→riとなるσ個のシェア[→ri]と、復元すると要素数N+Dの乱数ベクトル→siとなるσ個のシェア[→si]とを生成する。ここで、σはあらかじめ定めた1以上の整数である。σが大きいほど改ざん成功確率は低くなるが、計算量は増える。そのため、σの値は所望の安全性と利便性を鑑みて適宜設定すればよい。改ざん検知付き乱数生成プロトコルは、例えば、上記の参考文献２に記載されたプロトコルを適用することができる。乱数生成部１１は、シェア[→ri], [→si]を乱数乗算部１２へ入力する。
【００２２】
ステップＳ３において、各秘密改ざん検知装置１kの乱数乗算部１２は、乱数生成部１１からシェア[→ri], [→si]を受け取り、0≦i<σを満たす各整数iについて、改ざん検知無し乗算プロトコルを用いて、シェア[→ri]とシェア[→si]とを乗算し、復元するとベクトル→riとベクトル→siとを要素ごとに乗算した結果のベクトル→tiとなるσ個のシェア[→ti]:=[→ri→si]を生成する。改ざん検知無し乗算プロトコルは、例えば、上記の参考文献１に記載されたプロトコルを適用することができる。乱数乗算部１２は、シェア[→ri], [→si], [→ti]を組にして乱数検証部１４へ入力する。
【００２３】
ステップＳ４において、各秘密改ざん検知装置１kの秘密乗算部１３は、入力部１０からシェア[→x], [→y]を受け取り、改ざん検知無し乗算プロトコルを用いて、シェア[→x]とシェア[→y]とを乗算し、復元するとベクトル→xとベクトル→yとを要素ごとに乗算した結果のベクトル→zとなるシェア[→z]:=[→x→y]を計算する。秘密乗算部１３は、シェア[→x], [→y]を減算値公開部１６へ入力し、シェア[→y], [→z]を検証値計算部１７へ入力する。
【００２４】
ステップＳ５において、各秘密改ざん検知装置１kの乱数検証部１４は、乱数乗算部１２からシェア[→ri], [→si], [→ti]の組を受け取り、0≦i<σを満たす各整数iについて、0以上D+N未満の相異なるD個の整数pi,0, …, pi,D-1をランダムに選択する。ここで、Dは所定の自然数である。続いて、乱数検証部１４は、改ざん検知付き公開プロトコルを用いて、シェア[→ri], [→si], [→ti]のうち、0≦j<Dを満たす各整数jに対応するpi,j番目の要素を公開して、シェア[→ri], [→si], [→ti]それぞれに対応する公開した値の組が乗算として整合しているか否かを確認する。改ざん検知付き公開プロトコルは、例えば、上記の参考文献３に記載されたプロトコルを適用することができる。乗算として整合していない値の組が存在した場合、改ざんを検知した旨を表す情報を出力部１９から出力して処理を終了する。各値の組がすべて乗算として整合している場合、乱数検証部１４は、シェア[→ri], [→si], [→ti]および整数pi,jを乱数置換部１５へ入力する。
【００２５】
ステップＳ６において、乱数置換部１５は、乱数検証部１４からシェア[→ri], [→si], [→ti]および整数pi,jを受け取り、0≦i<σを満たす各整数iについて、シェア[→ri], [→si], [→ti]のうち、公開していない要素（すなわち、pi,j番目以外の要素）を、あらかじめ定めたランダム置換πiにより置換して、シェア[→r'i], [→s'i], [→t'i]∈[F]Nを生成する。乱数置換部１５は、シェア[→r'i], [→s'i]を減算値公開部１６へ入力し、シェア[→r'i], [→t'i]を検証値計算部１７へ入力する。
【００２６】
ステップＳ７において、各秘密改ざん検知装置１kの減算値公開部１６は、秘密乗算部１３からシェア[→x], [→y]を、乱数置換部１５からシェア[→r'i], [→s'i]を受け取り、0≦i<σを満たす各整数iについて、改ざん検知付き公開プロトコルを用いて、[→x-→r'i]および[→y-→s'i]を計算して公開する。減算値公開部１６は、公開したベクトル(→x-→r'i), (→y-→s'i)を検証値計算部１７へ入力する。
【００２７】
ステップＳ８において、各秘密改ざん検知装置１kの検証値計算部１７は、秘密乗算部１３からシェア[→y], [→z]を、乱数検証部１５からシェア[→r'i], [→t'i]を、減算値公開部１６からベクトル(→x-→r'i), (→y-→s'i)を受け取り、0≦i<σを満たす各整数iについて、式（１）を計算して、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を生成する。検証値計算部１７は、シェア[→z], [→ci]を検証値確認部１８へ入力する。
【００２８】
【数２】
2018216512.tif 000004
【００２９】
ステップＳ９において、各秘密改ざん検知装置１kの検証値確認部１８は、検証値計算部１７からシェア[→z], [→ci]を受け取り、0≦i<σを満たす各整数iについて、改ざん検知付き公開プロトコルを用いて、シェア[→ci]から検証値ciのベクトル→ciを公開する。そして、検証値確認部１８は、公開したベクトル→ciの全要素が0であることを確認する。ここで、公開したベクトル→ciに0でない要素が含まれている場合、改ざんを検知した旨を表す情報を出力部１９から出力して処理を終了する。公開したベクトル→ciの全要素が0である場合、検証値確認部１８は、受け取ったベクトル[→z]を出力部１９へ入力する。
【００３０】
ステップＳ１０において、各秘密改ざん検知装置１kの出力部１９は、検証値確認部１８から受け取ったベクトル[→z]を出力する。
【００３１】
一般に、改ざん検知無し乗算プロトコルでは、攻撃者が改ざんを行うことができてしまう。しかしながら、実施形態の秘密改ざん検知システムでは、ステップＳ４で乗算を行った後、ステップＳ５で乱数ベクトルの検証を行うことで改ざんを防ぐ。攻撃者が改ざんに成功するためには、ステップＳ３でも改ざんを行い、検証に用いるシェア[→ti]も辻褄が合うように改ざんしなければならない。しかしながら、改ざんを行う数が多いほど、ステップＳ５の公開により、改ざんが検知される確率が高くなる。逆に、改ざんを行う数が少ないと、検証を不正に通過する確率が低くなる。このような性質をもつ検証をσ回行うことで、改ざん成功確率をO(N-σ)とすることができる。
【００３２】
上記実施形態は、以下のようにして、さらに効率化することができる。上記実施形態では、ステップＳ９における検証値ciがすべて0であるか否かの確認を、シェア[→ci]から検証値ciを公開してそれぞれ確認することとした。ここで、検証値ciのベクトル→ciのシェア[→ci]から乱数との積和からなるチェックサムを計算し、このチェックサムが0であることを確認することにより、Nの大きさに依存しない通信量で検証値の確認を行うことができる。このようなチェックサムとしては、例えば、下記参考文献４に記載されたチェックサムを用いることができる。
〔参考文献４〕国際公開２０１４／１１２５５０号
【００３３】
参考文献４に記載されたチェックサムは、以下のように計算する。以降の説明では、qを2以上の整数とし、ρを(N+D)/q以上の最小の整数とし、Rを環とする。検証値確認部１８は、復元すると検証値ciのベクトル→ciとなるシェア[→ci]を先頭からq個ずつに分割して、ρ個の値ベクトルA0, …, Aρ-1を生成する。分割した際に最後の値ベクトルAρ-1の要素数がqとならない場合には、要素数がqとなるように任意の値（例えば0）でパディングする。検証値確認部１８は、乱数r∈Rqを選択し、式（２）によりチェックサムcを計算する。
【００３４】
【数３】
2018216512.tif 000005
【００３５】
この際、ベクトルの乗算は、式（３）（４）で定義される関数fを用いて計算する。
【００３６】
【数４】
2018216512.tif 000006
【００３７】
ここで、αi,j,k（i=0, …, q-1; j=0, …, q-1; k=0, …, q-1）は、2つの環Rqの要素から1つの環Rqの要素へ一様に対応させるためのパラメタである。パラメタαi,j,kは複数の種類があり得るが、計算の容易さなどを考慮して、パラメタαi,j,kに含まれるq3個の値に0が最も多く含まれるものをパラメタαi,j,kとして選択することが望ましい。例えば、Rが体であり、Rqが体Rの拡大体となるようにパラメタαi,j,kを決定すれば、効率的に改ざんを検知することが可能となる。
【００３８】
実施形態と従来技術とで通信量を比較した結果を示す。例えば、実施形態において体Fを位数が2の有限体GF(2)とした場合と、非特許文献１に記載された技術とを比較すると、同じ改ざん成功確率O(N-2)では、非特許文献１は各パーティの通信量が約10Nビットであるのに対して、実施形態では約7Nビットで済む。
【００３９】
この発明のポイントは以下のとおりである。従来技術である非特許文献１では、まず、multiplication tripleに対して改ざん検知を行う。一方、この発明では、はじめから、計算したい乗算に対してmultiplication tripleを使った改ざん検知を行う。また、非特許文献１では、計算したい乗算の数の整数倍を単位として処理を行う。一方、この発明では、計算したい乗算の数と同じ単位で並列に処理できる。そのため、従来よりも効率的に改ざん検知付き乗算を行うことができる。
【００４０】
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４１】
＜プログラム、記録媒体＞
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４３】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2018216512.tif 000007
【図２】
2018216512.tif 000008
【図３】
2018216512.tif 000009
【国際調査報告】
2018216512.tif 000010
2018216512.tif 000011
2018216512.tif 000012
2018216512.tif 000013