(57)【要約】【課題】秘密情報に０を含んでいても、効率よく秘匿演算を繰り返すことを可能にする。【解決手段】第１生成部は、第１の秘密情報に第１の乱数及び第２の乱数を作用させた第１の値を生成し、前記第１の乱数及び前記第１の秘密情報の少なくとも一方に第３の乱数を作用させた第２の値を生成する。【選択図】図１
2020056840.tif 000002
【特許請求の範囲】
【請求項１】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
第１の秘密情報に第１の乱数及び第２の乱数を作用させた第１の値を生成し、
前記第１の乱数及び前記第１の秘密情報の少なくとも一方に第３の乱数を作用させた第２の値を生成する第１生成部
を備えた分散装置。
【請求項２】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
第１の秘密情報に第１の乱数及び第２の乱数を作用させた複数の第１の値と、前記第１の乱数又は前記第１の秘密情報に第３の乱数を作用させた複数の第２の値とを用いて、
前記複数の第１の秘密情報同士の演算結果に前記複数の第１の乱数同士の演算結果、及び第４の乱数を作用させた第３の値を生成し、
前記複数の第１の乱数同士又は秘密情報同士の演算結果に第５の乱数を作用させた第４の値を生成する第２生成部
を備えた秘匿演算装置。
【請求項３】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
請求項２に記載の第２生成部によって得られた第３の値及び第４の値の少なくとも一方が０である場合に第６の乱数を生成する第３生成部と、
前記第６の乱数を秘匿加算する加算部と、
を更に備えた秘匿演算装置。
【請求項４】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
請求項２又は請求項３に記載の秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第１排除部と、
前記第１排除部による排除によって得られた第１の乱数同士の演算結果が正しいか否かを判定する第１判定部と、
を備えた検証復元装置。
【請求項５】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
請求項２又は請求項３に記載の秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第２排除部と、
前記第２排除部による排除によって得られた第１の乱数同士の演算結果であって、前記第３の値または第４の値が０の場合に第６の乱数を含む第１の乱数同士の演算結果が正しいか否かを判定する第２判定部と、
を備えた検証復元装置。
【請求項６】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
請求項４に記載の第１排除部、もしくは請求項５に記載の第２排除部から得られる値、又は請求項２に記載の第４の値から各々の第５の乱数に相当する値を排除した値と第３の値から第１の秘密情報同士の演算結果を得る復元部を有する秘匿演算装置。
【請求項７】
請求項１に記載の乱数を前記第１の秘密情報の生成者以外が生成した乱数を用いて生成する第４生成部を含む分散装置、
を備えた分散システム。
【請求項８】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
分散値同士の乗算を行う乗算部と、
前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、
乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、
備えた秘匿演算装置。
【請求項９】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
秘匿された登録値を用いて、登録値による検証用演算を行う演算部、を含む演算装置と、
前記演算部による演算結果が正しいかどうかを検証する検証部を含む検証復元装置と、
を備えた秘匿演算検証復元システム。      
【請求項１０】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、プログラムを、
第１の秘密情報に第１の乱数及び第２の乱数を作用させた第１の値を生成し、
前記第１の乱数及び前記第１の秘密情報の少なくとも一方に第３の乱数を作用させた第２の値を生成する第１生成部
として機能させるプログラム。
【請求項１１】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
第１の秘密情報に第１の乱数及び第２の乱数を作用させた複数の第１の値と、前記第１の乱数又は前記第１の秘密情報に第３の乱数を作用させた複数の第２の値とを用いて、
前記複数の第１の秘密情報同士の演算結果に前記複数の第１の乱数同士の演算結果、及び第４の乱数を作用させた第３の値を生成し、
前記複数の第１の乱数同士又は秘密情報同士の演算結果に第５の乱数を作用させた第４の値を生成する第２生成部
として機能させるプログラム。
【請求項１２】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項１１に記載の第２生成部によって得られた第３の値及び第４の値の少なくとも一方が０である場合に第６の乱数を生成する第３生成部と、
前記第６の乱数を秘匿加算する加算部と、
として機能させるプログラム。
【請求項１３】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項１１又は請求項１２に記載のプログラムによって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第１排除部と、
前記第１排除部による排除によって得られた第１の乱数同士の演算結果が正しいか否かを判定する第１判定部と、
として機能させるプログラム。
【請求項１４】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項１１又は請求項１２に記載のプログラムによって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第２排除部と、
前記第２排除部による排除によって得られた第１の乱数同士の演算結果であって、前記第３の値または第４の値が０の場合に第６の乱数を含む第１の乱数同士の演算結果が正しいか否かを判定する第２判定部と、
として機能させるプログラム。
【請求項１５】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項１３に記載の第１排除部、もしくは請求項１４に記載の第２排除部から得られる値、又は請求項１１に記載の第４の値から各々の第５の乱数に相当する値を排除した値と第３の値から第１の秘密情報同士の演算結果を得る手段として機能させるためのプログラム。
【請求項１６】
分散装置において、コンピュータを、
請求項１０に記載の乱数を前記第１の秘密情報の生成者以外が生成した乱数を用いて生成する第４生成部
として機能させるプログラム。
【請求項１７】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
分散値同士の乗算を行う乗算部と、
前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、
乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、
として機能させるプログラム。
【請求項１８】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
演算装置において、コンピュータを、秘匿された登録値を用いて、登録値による検証用演算を行う演算部、
として機能させるプログラム。
【請求項１９】
ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、
検証復元装置において、コンピュータを、請求項１８に記載の演算部による演算結果が正しいかどうかを検証する検証部、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムに関する。
【背景技術】
【０００２】
近年、ビッグデータおよびＩｏＴ環境の進歩に伴い、個人に関する情報の活用が期待されている。ただし、個人情報の活用においては、個人情報が漏洩すると個人のプライバシーに影響を与える可能性がある。そのため、ビッグデータの利活用においては、ビッグデータを活用する技術と、個人に関する情報を守る技術とを両立させる必要がある。このような個人に関する情報を守る技術に対するアプローチとして、データを守りながら演算を行うことができる秘匿計算技術が研究されている。
【０００３】
秘匿計算技術は大きく分けると、主に鍵を用いてデータを秘匿する準同型暗号と、鍵を用いずにデータを秘匿する秘密分散法を用いた手法がある。ただし、準同型暗号は一般的に計算量が多く、演算処理に多大な時間がかかるという問題がある。そのため、クラウドシステムへの適用に対しては、計算量が重い準同型暗号よりも、計算量が軽い秘密分散法を用いるというアプローチが検討されている。
【０００４】
秘密分散法とはユーザが持っている秘密情報を複数の異なる値（以降、分散値）に変換し、分散する手法である。秘密分散法の１つであるＳｈａｍｉｒの（ｋ,ｎ）閾値秘密分散法（以下、「Ｓｈａｍｉｒ法」または「（ｋ,ｎ）Ｓｈａｍｉｒ法」）が知られている。
【０００５】
また、秘密情報をＬ個に分割し、分散式の係数として含ませるランプ型秘密分散方式も知られている。ランプ型秘密分散方式によって、分散値の小型化が実現できる。
【０００６】
秘密分散法に関する技術として、例えば、特許文献１には、データを秘匿しながら計算を行い計算結果の正当性を保証する秘匿計算システムが開示されている。
【０００７】
また、特許文献２には、秘密分散によりデータを秘匿しつつ、乗算及び加算からなる式の計算を、計算結果の正当性を保ちながら行う秘匿積和結合システムが開示されている。
【０００８】
また、特許文献３には、完全準同型暗号及び信頼できる第三者を利用せずに、集計対象データ及びその集計結果を秘匿した状態で集計装置に集計処理を実行させる技術が開示されている。
【０００９】
また、秘密分散法の１つに、Ｓｈａｍｉｒ法を用いるＴＵＳ法がある。ＴＵＳ法では、他の秘密分散法では実現できないｎ＜２ｋ−１において秘匿演算を実現することが特徴である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】再公表２０１４−１１２５４８号公報
【特許文献２】再公表２０１２−１２１３３３号公報
【特許文献３】特開２０１３−２０５５９２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
もっとも、ＴＵＳ法では、秘匿乗算において乱数で秘匿化された秘密情報αａを一旦復号するために、秘密情報は０を含まず、乱数も０を含まないものである。ただし、秘匿乗算以外では０を含んでもよいものとされる。
【００１２】
上記のＴＵＳ法の問題の一つに、秘密情報に０を含むことができず、減算を含む秘匿計算を繰り返せないという問題があった。また、計算結果の正当性を検証できないという問題もあった。
【００１３】
本開示は、以上の事情を鑑みて成されたものであり、秘密情報に０を含んでいても、効率よく秘匿演算を繰り返すことに対応する分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムを提供することを目的とする。さらに、その計算結果を効率的に検証できる分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
開示の技術は、一つの態様として、第１の発明に係る分散装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、第１の秘密情報に第１の乱数及び第２の乱数を作用させた第１の値を生成し、前記第１の乱数及び前記第１の秘密情報の少なくとも一方に第３の乱数を作用させた第２の値を生成する第１生成部を備えることを特徴とする。
【００１５】
開示の技術は、一つの態様として、第２の発明に係る秘匿演算装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、第１の秘密情報に第１の乱数及び第２の乱数を作用させた複数の第１の値と、前記第１の乱数又は前記第１の秘密情報に第３の乱数を作用させた複数の第２の値とを用いて、前記複数の第１の秘密情報同士の演算結果に前記複数の第１の乱数同士の演算結果、及び第４の乱数を作用させた第３の値を生成し、前記複数の第１の乱数同士又は秘密情報同士の演算結果に第５の乱数を作用させた第４の値を生成する第２生成部を備えることを特徴とする。
【００１６】
開示の技術は、一つの態様として、第２の発明に係る秘匿演算装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、上記に記載の第２生成部によって得られた第３の値及び第４の値の少なくとも一方が０である場合に第６の乱数を生成する第３生成部と、前記第６の乱数を秘匿加算する加算部と、を更に備えることを特徴とする。
【００１７】
開示の技術は、一つの態様として、第３の発明に係る検証復元装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、第２の発明に係る秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第１排除部と、前記第１排除部による排除によって得られた第１の乱数同士の演算結果が正しいか否かを判定する第１判定部と、を備えることを特徴とする。
【００１８】
開示の技術は、一つの態様として、第４の発明に係る検証復元装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、第２の発明に係る秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第３の値から秘密情報と第４の乱数に相当する値を排除する第２排除部と、前記第２排除部による排除によって得られた第１の乱数同士の演算結果であって、前記第３の値または第４の値が０の場合に第６の乱数を含む第１の乱数同士の演算結果が正しいか否かを判定する第２判定部と、を備えることを特徴とする。
【００１９】
開示の技術は、一つの態様として、第２の発明に係る秘匿演算装置が、第３の発明に記載の第１排除部、もしくは第４の発明に記載の第２排除部から得られる値、又は第４の値から各々の第５の乱数に相当する値を排除した値から第１の秘密情報同士の演算結果を得る復元部を有することを特徴とする。
【００２０】
開示の技術は、一つの態様として、第５の発明に係る分散システムが、請求項１に記載の乱数を前記第１の秘密情報の生成者以外が生成した乱数を用いて生成する第４生成部を含む分散装置、を備えることを特徴とする。
【００２１】
開示の技術は、一つの態様として、第６の発明に係る秘匿演算装置が、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、分散値同士の乗算を行う乗算部と、前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、を備えることを特徴とする。
【００２２】
開示の技術は、一つの態様として、第７の発明に係る秘匿演算検証復元システムが、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の前記分散値によって前記秘密情報を復元でき、ｋ個未満では前記秘密情報を復元できないシステムにおいて、秘匿された登録値を用いて、登録値による検証用演算を行う演算部、を含む演算装置と、前記演算部による演算結果が正しいかどうかを検証する検証部を含む検証復元装置と、を備えることを特徴とする。
【００２３】
開示の技術は、一つの態様として、コンピュータを、上記第１〜第７の発明のいずれか１つの装置の各部として機能させるプログラムを有する。
【発明の効果】
【００２４】
本開示によれば、秘密情報に０を含んでいても、効率よく秘匿演算を繰り返すことができ、その計算結果を効率的に検証することができる。
【図面の簡単な説明】
【００２５】
【図１】第１実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図２】第１実施形態に係るサーバ１６のハードウェア構成の一例を示す図である。
【図３】第１実施形態に係る変換用乱数組を生成する処理シーケンスの一例を示す図である。
【図４】第１実施形態の変形例に係る変換用乱数組を生成する処理シーケンスの一例を示す図である。
【図５】第２実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図６】第２実施形態に係る入力装置２１２のハードウェア構成の一例を示す図である。
【図７】第２実施形態に係るサーバ２１６のハードウェア構成の一例を示す図である。
【図８】第２実施形態に係る分散の処理シーケンスの一例を示す図である。
【図９】第２実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図１０】第２実施形態に係る補正処理の処理シーケンスの一例を示す図である。
【図１１】第３実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図１２】第３実施形態に係る復元装置３１４のハードウェア構成の一例を示す図である。
【図１３】第３実施形態に係る分散の処理シーケンスの一例を示す図である。
【図１４】第３実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図１５】第３実施形態に係る検証の処理シーケンスの一例を示す図である。
【図１６】第４実施形態に係るサーバ４１６のハードウェア構成の一例を示す図である。
【図１７】第４実施形態に係る分散の処理シーケンスの一例を示す図である。
【図１８】第４実施形態の変形例に係る分散の処理シーケンスの一例を示す図である。
【図１９】第５実施形態に係る復元装置５１４のハードウェア構成の一例を示す図である。
【図２０】第５実施形態に係る分散の処理シーケンスの一例を示す図である。
【図２１】第５実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図２２】第５実施形態に係る補正処理の処理シーケンスの一例を示す図である。
【図２３】第５実施形態に係る検証の処理シーケンスの一例を示す図である。
【図２４】第６実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図２５】第６実施形態に係る復元装置６１４のハードウェア構成の一例を示す図である。
【図２６】第６実施形態に係るブロックチェーン装置６１６のハードウェア構成の一例を示す図である。
【図２７】第６実施形態に係る検証装置６１８のハードウェア構成の一例を示す図である。
【図２８】第６実施形態に係る分散、秘匿積和演算、補正処理の処理シーケンスの一例を示す図である。
【図２９】第６実施形態に係る検証の処理シーケンスの一例を示す図である。
【発明を実施するための形態】
【００２６】
以下、図面を参照して、本開示の技術を実施するための形態例を詳細に説明する。
【００２７】
まず、実施形態の詳細を説明する前に、実施形態の技術の前提となるＳｈａｍｉｒ法、及びＴＵＳ法の詳細を説明した上で、ＴＵＳ法における各問題点を説明する。
【００２８】
＜Ｓｈａｍｉｒ法＞
Ｓｈａｍｉｒ法は、ある秘密情報をｎ個の分散情報に分散し、そのうちのｋ個以上の分散情報を集めることによって、元の秘密情報を復元することができるという方法である。ただし、ｋ個未満の分散情報からは元の秘密情報を得ることが一切できないというものである。Ｓｈａｍｉｒ法での秘密情報の分散及び復元は、以下に示すように行われる。このような手法を（ｋ，ｎ）Ｓｈａｍｉｒ法と呼ぶ。
【００２９】
＜分散＞
１．ユーザはｓ＜ｐかつｎ＜ｐの条件を満たす任意の素数ｐを選択する。
【００３０】
２．ユーザはＧＦ（ｐ）の元から、ｎ個のｘｉ（ｉ＝０,１,２,…,ｎ−１）を選び、サーバＩＤとする。
【００３１】
３．ユーザはＧＦ（ｐ）の元から、ｋ−１個の乱数ａｌ（ｌ＝１,２,…,ｋ−１)を選び、以下の分散式を生成する。
【００３２】
Ｗｉ＝ｓ＋ａ１ｘｉ＋ａ２ｘｉ２＋…＋ａｋ−１ｘｋ−１  （ｍｏｄ ｐ）
【００３３】
４．ユーザは上記式のｘｉに各サーバＩＤを代入して分散値Ｗｉを計算し、各サーバＳｉに送信する。
【００３４】
＜復元処理＞
１．復元に用いる分散情報をＷｉ(ｉ＝０,１,２,…,ｋ−１）とする。また、その分散情報に対応するサーバＩＤをｘｉとする。
【００３５】
２．復元者は、ｋ個の（ｘｉ,Ｗｉ）を集め、集めたｋ個の（ｘｉ,Ｗｉ）を上記の分散式に代入し、ｋ個の連立方程式を解くことで秘密情報であるｓを復元する。なお、ｓの復元の際には、Ｌａｇｒａｎｇｅの補間公式を用いることができる。
【００３６】
以上がＳｈａｍｉｒ法の詳細である。
【００３７】
＜ＴＵＳ法＞
次にＴＵＳ法の詳細を説明する。以下に、ＴＵＳ法を用いてａｂ＋ｃの積和演算を行う場合の例を示す。なお、秘密情報ａ,ｂ,ｃ及び乱数αｊ,βｊ,λｊ,γｊは、ａ,ｂ,ｃ,αｊ,βｊ,λｊ,γｊ∈Ｚ／ｐＺである。ただし、乗算において一旦復元されるａと乱数は０ではない。以下において、［ａ］ｊは秘密情報ａに対してサーバＳｊが保持する分散値を表す。以降、秘密分散の処理も含めてすべての秘匿演算はｐを法として行われる。また、サーバＳｉは攻撃者が知らない変換用乱数組（［ε］ｊ,εｊ）,（［φ］ｊ,φｊ）を持つものとする。変換用乱数組とは、例えば
2020056840.tif 000003
の関係を満たす変換用乱数εの分散値と、εを構成する乱数εｊからなる組である。
【００３８】
ａｂ＋ｃの秘匿演算の入出力を以下に示す。
【００３９】
（入力）
（［αａ］ｊ,［α０］ｊ,…,［αｋ−１］ｊ）（ｊ＝０,１,…,ｋ−１）
（［βｂ］ｊ,［β０］ｊ,…,［βｋ−１］ｊ）（ｊ＝０,１,…,ｋ−１）
（［γｃ］ｊ,［γ０］ｊ,…,［γｋ−１］ｊ）（ｊ＝０,１,…,ｋ−１）
（出力）
（［δ（ａｂ＋ｃ）］ｉ,［δ０］ｊ,…,［δｋ−１］ｊ）（ｉ＝０,１,…,ｎ−１）
【００４０】
上記の入出力のもと、ａｂ＋ｃの秘匿演算は以下に示すように行われる。
【００４１】
１．ｋ台のサーバＳｊは［αａ］ｊ,［βｂ］ｊ,［γｃ］ｊを公開する。また、Ｓｊは、αａ,βｂ,γｃを復元する。
【００４２】
２−１．ｋ台のサーバＳｊは［αｊ］０,…,［αｊ］ｋ−１,［βｊ］０,…,［βｊ］ｋ−１,［γｊ］０,…,［γｊ］ｋ−１を収集して、乱数αｊ,βｊ,γｊを復元する。
【００４３】
２−２．サーバＳｊは、乱数δｊを生成する。
【００４４】
２−３．サーバＳｊは、生成した乱数δｊを用いて、δｊ／αｊβｊεｊ,δｊ／γｊφｊを計算して公開する。
【００４５】
３．全てのサーバＳｉは、以下の式を計算する。
2020056840.tif 000004
【００４６】
ただし、
2020056840.tif 000005
とする。
【００４７】
４．ｋ台のサーバＳｊは乱数δｊをＳｈａｍｉｒ法で分散し、全てのサーバＳｉに分散する。
【００４８】
５．以上より、サーバＳｉ（ｉ＝０,１,２,…,ｎ−１）は秘密情報ａｂ＋ｃに関する分散情報として（［δ（ａｂ＋ｃ）］ｉ,［δ０］ｊ,…,［δｋ−１］ｊ）を保持する。
【００４９】
以上がＴＵＳ法による秘匿演算の詳細である。ＴＵＳ法は以下の３つの問題点を持つ。
【００５０】
＜問題点１＞
問題点１は、複数人による変換用乱数組の安全な生成法が知られていないというものである。変換用乱数組を一人が生成する場合、例えば生成者はｋ個の乱数ε０,ε１,…,εｋ−１を生成して、ε＝ε０ε１…εｋ−１を計算し、εを秘密分散して、［ε］ｊとεｊをサーバＳｊに送れば、Ｓｊは変換用乱数組（［ε］ｊ,εｊ）を持つことができる。ＴＵＳ法の安全性は変換用乱数組の安全性に依存するため、変換用乱数組の生成者が攻撃者であれば、その変換用乱数組を用いた秘匿計算は安全ではない。よって、信頼できない複数の生成者が変換用乱数組を生成しても、その値を知ることができない安全な変換用乱数組の生成法がなければ、上記ＴＵＳ法は安全ではないということである。
【００５１】
＜問題点２＞
問題点２は、秘密情報に０を含むことができないというものである。例えば、入力をａではなくａ＋１として入力すれば、最初の入力ａは０であってもよいが、減算を含む場合、すなわちａｂ−ｃまたはａ−ｃを演算する場合、その出力が０となる可能性がある。そのため、ＴＵＳ法による演算結果を用いて秘匿演算を繰り返せないという問題がある。
【００５２】
＜問題点３＞
問題点３は、秘匿計算の正当性を検証できないというものである。一般に秘密分散においては、ｋ−１台までのサーバがもつ情報は盗聴などにより知られることを想定している。しかし、その盗聴可能なｋ−１台のサーバが乗っ取られ、偽の情報を出力したり、決められた処理をしない場合、上記秘匿演算の結果は信用できないものとなる。
【００５３】
以上がＴＵＳ法の問題点１〜３である。
【００５４】
問題点１の解決はＴＵＳ法において必須であり、問題点１が解決されることにより、ＴＵＳ法の安全性が向上する。例えば、信頼できる変換用乱数組の生成者がいない場合でもＴＵＳ法を用いて秘匿演算できるようになる。また問題点１を解消することは、秘匿計算の検証においても必要となる。
【００５５】
問題点２が解決されることにより、減算を含む秘匿演算を繰り返すことができるようになり、ＴＵＳ法の実用性が向上する。また問題点２を解消することは、繰返し演算された結果、または０を含む結果を検証する場合に必要となる。
【００５６】
問題点３が解決されることにより、嘘の情報を出力するなど決められたプロトコルに従わないａｃｔｉｖｅな攻撃者に対しても安全性を確保することができるようになる。さらに、一般の検証機能付き秘匿計算は非常に複雑な処理を必要とするが、本発明の実施形態の手法によって非常に効率的に演算結果を検証できるようになる。
【００５７】
以上の各問題点を解消することによって、安全かつ効率的、実用的に秘匿演算を検証できるようになる。
【００５８】
以上を踏まえて、以下に各実施形態を展開する。以下の各実施形態において説明する秘密分散システムは、ｎを２以上の整数、ｋを２以上ｎ以下の整数とし、秘密情報をｎ個の分散値に分散し、ｋ個の分散値によって秘密情報を復元でき、ｋ個未満では秘密情報を復元できないシステムである。
【００５９】
［第１実施形態］
第１実施形態は、上記問題点１に対応する。すなわち複数の信頼できない入力者及び復元者によって生成されていたとしても、変換用乱数の値が知られない安全な変換用乱数組の生成法を実現するものである。本実施形態の手法によって生成された変換用乱数組は、以降の各実施形態においても用いられる。
【００６０】
まず第１実施形態の手法の前提について説明する。第１実施形態では、変換用乱数組を生成するために、参考文献１及び２に示される手法を拡張する。
【００６１】
［参考文献１］M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” STOC ’88, 1988, pp. 1−10, ACM Press.
［参考文献２］Rosario Gennaro, Michael O. Rabin, and Tal Rabin, “Simplified VSS and fast-track multiparty computations with applications to threshold cryptography,” In Brian A. Coen and Yehuda Afek, editors, PODC, 1998, pp. 101−111, ACM.
【００６２】
参考文献１及び２において、２ｋ次の多項式に対する分散値をｋ次の多項式に対する分散値に変換する方法が示されている。例えば参考文献１では、以下に示す変換手法が開示されている。
【００６３】
ある規則によって生成された定数を要素とする行列を以下の行列Ａとする。
【００６４】
2020056840.tif 000006
【００６５】
上記行列Ａを用いて、２ｋ次の多項式に対する分散値ベクトルＷ＝（Ｗ０,Ｗ１,・・・,Ｗ２ｋ−１）に対してＲ＝Ｗ・Ａを計算することで、ｋ次の多項式に対する分散値ベクトルＲ＝（Ｒ０,Ｒ１,・・・,Ｒ２ｋ−１）に変換することができる。参考文献２の手法もほぼ同様の処理で、分散値ベクトルＲへの変換を実現できる。
【００６６】
ただし、参考文献１及び２の手法はサーバ台数がｎ≧２ｋ−１の場合に有効であるが、本実施形態ではＴＵＳ法と同様にｎ＜２ｋ−１の場合を扱う。以下で説明する本実施形態の構成では、二人の入力者に対応する入力装置と、一人の復元者に対応する復元装置とを想定し、ｎ＝ｋの場合の生成法を示す。ただし、後述するように復元装置は復元を行わず、演算支援装置としてふるまう。
【００６７】
２ｋ−１＞ｎ＞ｋの場合は乱数αｉ等を直接サーバに送らず、（ｋ,ｎ）Ｓｈａｍｉｒ法を用いて分散し、演算を行うｋ台のサーバが乱数αｉ等を復元して使用する。また、秘密情報λ０,λ１は（ｋ,ｎ＋ｋ−１）Ｓｈａｍｉｒ法を用いて分散され、ｎ台のサーバ中ｋ−１台のサーバのみが［αλ０］ｉ＋ｋを持つ。また、復元装置は復元を行うと変換用乱数の値を知るので、復元装置は復元を行わず、演算支援の役割を持つ。以下において、秘密情報λ０,λ１及び乱数αｊ,ｉ,βｊ,ｉ,γｉはλ０,λ１,αｊ,ｉ,βｊ,ｉ,γｉ∈Ｚ／ｐＺである。ただし、秘密情報と乱数は０を含まないものとする。また、０ｒ１などは０を表し、他と区別するため記号を付ける。
【００６８】
以上の前提を踏まえて、図１を参照して、本実施形態に係る秘密分散システム１０の構成を説明する。図１に示すように、秘密分散システム１０は、２台の入力装置１２Ａ及び入力装置１２Ｂ、復元装置１４、並びにサーバ１６０〜１６ｎ−１を含む。以下、入力装置１２Ａ及び入力装置１２Ｂについて共通する内容については「入力装置１２」、サーバ１６０〜１６ｎ−１について共通する内容については「サーバ１６」とし、末尾の識別記号を省略して説明する場合もある。入力装置１２、復元装置１４、及びサーバ１６は、ネットワークＮに接続され、互いに通信可能とされる。なお、サーバ１６が、乗算部と、変換部と、加算部とを含む秘匿演算装置の一例である。
【００６９】
入力装置１２は、秘密情報の入力者（以下、単に「入力者」という）によって操作される装置であり、入力装置１２の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。
【００７０】
復元装置１４は、秘密情報を復元する復元者（以下、単に「復元者」という）によって操作される装置であり、復元装置１４の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。
【００７１】
サーバ１６は、変換用乱数組の生成に係る計算、変換用乱数組の保管などをする役割を持つ。また、サーバ１６はｎ台存在し、説明に応じてサーバＳｉ（ｉ＝０,…,ｎ−１）等とも記載する（以下、各実施形態において同様である）。
【００７２】
次に、図２を参照して、本実施形態に係るサーバ１６のハードウェア構成を説明する。図２に示すように、サーバ１６は、ＣＰＵ（Central Processing Unit）２０、一時記憶領域としてのメモリ２１、不揮発性の記憶部２２を含む。また、サーバ１６は、液晶ディスプレイ等の表示装置２３、キーボード等の入力Ｉ／Ｆ２４、及びネットワークＮに接続されるネットワークＩ／Ｆ２５（InterFace）を含む。ＣＰＵ２０、メモリ２１、記憶部２２、表示装置２３、入力Ｉ／Ｆ２４、及びネットワークＩ／Ｆ２５は、バス２６に接続される。
【００７３】
記憶部２２は、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部２２には、変換用乱数組生成プログラム２８が記憶される。変換用乱数組生成プログラム２８は、乗算プロセス２８ａと、変換プロセス２８ｂと、加算プロセス２８ｃとを含む。ＣＰＵ２０は、記憶部２２から変換用乱数組生成プログラム２８を読み出してからメモリ２１に展開し、展開した生成プログラム２８を実行する。ＣＰＵ２０が変換用乱数組生成プログラム２８の乗算プロセス２８ａを実行することで、開示の技術の乗算部として動作する。ＣＰＵ２０が変換用乱数組生成プログラム２８の変換プロセス２８ｂを実行することで、開示の技術の変換部として動作する。ＣＰＵ２０が変換用乱数組生成プログラム２８の加算プロセス２８ｃを実行することで、開示の技術の加算部として動作する。
【００７４】
なお、入力装置１２、及び復元装置１４についてはサーバ１６と同様の装置構成をとることができ、実行するプログラムのみが異なるため詳細な説明を省略する。
【００７５】
次に、図３を参照して、本実施形態に係る秘密分散システム１０の作用を説明する。
【００７６】
＜変換用乱数組生成１：ｎ＝ｋ＞
図３は、秘密分散システム１０の変換用乱数組を生成する処理シーケンスを説明したものである。以下において、サーバ１６は、シーケンスの各処理に応じてサーバＳｉ、Ｓｊ、及びＳｋ−１のいずれかが対象であるものとして説明する。
【００７７】
Ｓ１０で、入力装置１２Ａは、乱数λ０,ｉ、及びαｉ（ｉ＝０,…,ｋ−１）を生成する。
【００７８】
Ｓ１２で、入力装置１２Ａは、
2020056840.tif 000007
を計算する。また、入力装置１２Ａは、λ０を（ｋ,２ｋ−１）Ｓｈａｍｉｒ法で分散して［αλ０］ｉ＋ｋ＝α×［λ０］ｉ＋ｋを計算する。
【００７９】
Ｓ１４で、入力装置１２Ａは、Ｓ１０及びＳ１２で得られた［λ０］ｉ,［αλ０］ｉ＋ｋ,αｉ,λ０,ｉをサーバＳｉに送信する。ただし、サーバＳｋ−１は［αλ０］２ｋ−１を持たないものとする。
【００８０】
Ｓ１６で、入力装置１２Ｂは、乱数λ１,ｉ、及びβｉ（ｉ＝０,…,ｋ−１）を生成する。
【００８１】
Ｓ１８で、入力装置１２Ｂは、
2020056840.tif 000008
を計算する。また、入力装置１２Ｂは、λ１を（ｋ,２ｋ−１）Ｓｈａｍｉｒ法で分散して［βλ１］ｉ＋ｋ＝β×［λ１］ｉ＋ｋを計算する。
【００８２】
Ｓ２０で、入力装置１２Ｂは、Ｓ１６及びＳ１８で得られた［λ１］ｉ,［βλ１］ｉ＋ｋ,βｉ,λ１,ｉをＳｉに送信する。ただし、サーバＳｋ−１は［βλ１］２ｋ−１を持たないものとする。
【００８３】
Ｓ２２で、サーバＳｋ−１を除くサーバＳｉ（以下、本シーケンスの説明では単にＳｉと記載する）は、［λ０λ１］ｉ＝［λ０］ｉ×［λ１］ｉ,［αβλ０λ１］ｉ＋ｋ＝［αλ０］ｉ＋ｋ×［βλ１］ｉ＋ｋを計算する。なお、Ｓ２２は、サーバＳｉにおける、変換用乱数組生成プログラム２８の乗算プロセス２８ａに対応する。サーバＳｉのＣＰＵ２０が、乗算プロセス２８ａを実行することで、開示の技術における分散値同士を乗算する処理を行う。
【００８４】
Ｓ２４で、サーバＳｉは、［αβλ０λ１］ｉ＋ｋを復元装置１４に送信する。
【００８５】
Ｓ２６で、サーバＳｉは、αｉβｉを計算する。
【００８６】
Ｓ２８で、復元装置１４は、０ｒ１を（２ｋ−１,２ｋ−１）Ｓｈａｍｉｒ法で分散する。
【００８７】
Ｓ３０で、復元装置１４は、サーバＳｉで計算されたαｉβｉを取得する。
【００８８】
Ｓ３２で、取得したαｉβｉを元に、αβを復元する。
【００８９】
Ｓ３４で、復元装置１４は、Ｓ２８で分散した０ｒ１、及びＳ３２で復元したαβを用いて［λ０λ１］′ｉ＋ｋ＝［αβλ０λ１］ｉ＋ｋ／αβ＋［０ｒ１］ｉ＋ｋを計算する。
【００９０】
Ｓ３６で、復元装置１４は、計算した［λ０λ１］′ｉ＋ｋをサーバＳｉに送信する。
【００９１】
Ｓ３８で、サーバＳｉは、０ｉを（ｋ,ｎ）Ｓｈａｍｉｒ法で分散し、Ｒｉ,ｊを計算する。ｊ≠ｉ（ｊ＝０,…,ｎ−１）のとき、Ｒｉ,ｊは以下のように計算できる。なお、以下におけるａｉ,ｊなどは上記行列Ａの要素である。
Ｒｉ,ｊ＝ａｉ,ｊ×［λ０λ１］ｉ＋ａｉ＋ｎ,ｊ×［λ０λ１］′ｉ＋ｎ＋［０ｉ］ｊ
【００９２】
なお、Ｓ３８は、サーバＳｉにおける、変換用乱数組生成プログラム２８の変換プロセス２８ｂに対応する。サーバＳｉのＣＰＵ２０が、変換プロセス２８ｂを実行することで、開示の技術における分散値の次数変換処理を行う。Ｓ３８のＲｉ,ｊの計算ではＳ３６で返却された［λ０λ１］′ｉ＋ｋを用いるが、［λ０λ１］′ｉ＋ｋが他装置から送られた分離できない乗算値の一例である。また、Ｒｉ,ｊが次数変換後の分散値の一例である。
【００９３】
Ｓ４０で、サーバＳｉは、ｉ＝ｊか否かを判定する。ｉ＝ｊであればＳ４２へ移行し、ｉ＝ｊでなければ（すなわち、ｉ≠ｊであれば）、Ｓ４４へ移行する。
【００９４】
Ｓ４２で、サーバＳｉは、乱数ｒｉを生成して、以下のようにＲｉ,ｊにｒｉを加算する。
Ｒｉ,ｊ＝ａｉ,ｊ×［λ０λ１］ｉ＋ａｉ＋ｎ,ｊ×［λ０λ１］′ｉ＋ｎ＋［０ｉ］ｊ＋ｒｉ
【００９５】
なお、Ｓ４２は、サーバＳｉにおける、変換用乱数組生成プログラム２８の加算プロセス２８ｃに対応する。サーバＳｉのＣＰＵ２０が、加算プロセス２８ｃを実行することで、開示の技術における乱数を分散値に加算する処理を行う。
【００９６】
Ｓ４４で、サーバＳｉは、計算したＲｉ,ｊを復元装置１４に送信する。
【００９７】
Ｓ４６で、復元装置１４は、０ｒ２を（ｋ,ｎ）Ｓｈａｍｉｒ法で分散し、Ｒ′ｉ,ｊ＝Ｒｉ,ｊ＋ａｉ,ｊ×［０ｒ１］ｉ＋［０ｒ２］ｉを計算する。ただし、ｊ＝０,…,ｎ−１とし、
（ｉ≠ｊ）のとき：
Ｒ′ｉ,ｊ＝ａｉ,ｊ×［λ０λ１］′ｉ＋ａｉ＋ｎ,ｊ×［λ０λ１］′ｉ＋ｎ＋［０ｉ］ｊ＋［０ｒ２］ｊ（ｉ＝ｊ）のとき：
Ｒ′ｉ,ｊ＝ａｉ,ｊ×［λ０λ１］′ｉ＋ａｉ＋ｎ,ｊ×［λ０λ１］′ｉ＋ｎ＋［０ｉ］ｊ＋［０ｒ２］ｊ＋ｒｉ
とする。
【００９８】
Ｓ４８で、復元装置１４は、Ｒ′ｉ,ｊをサーバＳｊに送信する。このように、サーバＳｉで計算された次数変換後の分散値であるＲｉ,ｊは、Ｒ′ｉ,ｊとなってサーバＳｊに返信される。
【００９９】
Ｓ５０で、サーバＳｊは、Σｉ＝０ｋ−１Ｒ′ｉ,ｊ−ｒｉ＝［λ］ｊと計算する。また、サーバＳｊは、λｉ＝λ０,ｉλ１,ｉを計算する。以上のシーケンスによって、変換用乱数組（［λ］ｊ,λｉ）が得られる。
【０１００】
［第１実施形態の変形例］
上述した変換用乱数組生成１では、ｎ＝ｋのとき、入力装置１２及び復元装置１４を必要とする場合を例に説明した。一方、ｎ=ｋ＝２の場合、入力装置１２及び復元装置１４を不要とした以下の処理が可能となる。すなわち、サーバ１６だけの構成で変換用乱数組生成が可能となる。
【０１０１】
＜変換用乱数組生成１′：ｎ=ｋ＝２＞
図４は、ｎ=ｋ＝２の場合の変換用乱数組を生成する処理シーケンスを説明したものである。以下において、サーバ１６のうち、サーバＳ０、及びＳ１の間で処理する場合を例に説明する。図４のシーケンスにおいて、以下のＳ６０〜Ｓ９４の処理が行われる。なお、図４において各処理は簡略化して記載するものとする。
【０１０２】
Ｓ６０では、サーバＳ０は、乱数λ０,α０,α１,τ０を生成し、α＝α０α１を計算する。
【０１０３】
Ｓ６２では、サーバＳ０は、λ０を（２,３）Ｓｈａｍｉｒ法で分散して、［αλ０］０＝α×［λ０］０,［αλ０］２＝α×［λ０］２,［τ０λ０］１＝τ０×［λ０］１を計算する。
【０１０４】
Ｓ６４では、サーバＳ０は、得られた［τ０λ０］１,α１をサーバＳ１に送信する。
【０１０５】
Ｓ６６では、サーバＳ１は、乱数λ１,β０,β１を生成し、β＝β０β１を計算する。
【０１０６】
Ｓ６８では、サーバＳ１は、λ１を（２,３）Ｓｈａｍｉｒ法で分散して、［βλ１］０＝β×［λ１］０,［βλ１］２＝β×［λ１］２を計算する。
【０１０７】
Ｓ７０では、サーバＳ１は、得られた［βλ１］０,［βλ１］２,β０をサーバＳ０に送信する。
【０１０８】
Ｓ７２では、サーバＳ０は、００を（３,３）Ｓｈａｍｉｒ法で分散し、α０β０と以下を計算する。
［αβλ０λ１］′０＝［αλ０］０×［βλ１］０＋［００］０,［αβλ０λ１］′２＝［αλ０］２×［βλ１］２＋［００］２,［００］１
【０１０９】
Ｓ７４では、サーバＳ０は、計算した［αβλ０λ１］′０、［αβλ０λ１］′２、α０β０をサーバＳ１に送信する。
【０１１０】
Ｓ７６では、サーバＳ１は、０１を（３,３）Ｓｈａｍｉｒ法で分散し、α１β１とα０β０からαβを計算すると共に、以下を計算する。ただし、［００１］ｉ＝［００］ｉ／αβ＋［０１］ｉである。
【０１１１】
2020056840.tif 000009
2020056840.tif 000010
［００１］１＝［００］１／αβ＋［０１］１
【０１１２】
Ｓ７８では、サーバＳ１は、得られた［λ０λ１］′０,［λ０λ１］′２,［００１］１をサーバＳ０に送信する。
【０１１３】
Ｓ８０では、サーバＳ０は、００′を（２,２）Ｓｈａｍｉｒ法で分散する。
【０１１４】
Ｓ８２では、サーバＳ０は、乱数ｒ０を生成する。
【０１１５】
Ｓ８４では、サーバＳ０は、分散した００′、及び乱数ｒ０を用いて、以下のＲ０,０及びＲ０,１を計算する。
Ｒ０,０＝τ０（ａ０,０×［λ０λ１］′０＋ａ２,０×［λ０λ１］′２＋ａ１,０×［００１］１）＋［００′］０＋ｒ０＝τ０（ａ０,０［λ０λ１］０＋ａ２,０［λ０λ１］２）＋τ０［００１］″０＋［００′］０＋ｒ０
Ｒ０,１＝τ０（ａ０,１×［λ０λ１］′０＋ａ２,１×［λ０λ１］′２＋ａ１,１×τ０［００１］１）＋［００′］１＝τ０（ａ０,１［λ０λ１］０＋ａ２,１［λ０λ１］２）＋τ０［００１］″１＋［００′］１
【０１１６】
Ｓ８６では、サーバＳ０は、計算したＲ０,０,Ｒ０,１をサーバＳ１に送信する。
【０１１７】
Ｓ８８では、サーバＳ１は、［τ０λ０λ１］１＝［τ０λ０］１×［λ１］１を計算すると共に、０１′を（２,２）Ｓｈａｍｉｒ法で分散し、以下を計算する。
Ｒ′０,０＝Ｒ０,０＋ａ１,０×［τ０λ０λ１］１＋［０１′］０＝τ０［λ０λ１］０＋τ０［００１］″０＋［００′］０＋［０１′］０＋ｒ０
Ｒ′０,１＝Ｒ０,１＋ａ１,１×［τ０λ０λ１］１＋［０１′］１＝τ０［λ０λ１］１＋τ０［００１］″１＋［００′］１＋［０１′］１
【０１１８】
Ｓ９０では、サーバＳ１は、得られたＲ′０,０をサーバＳ０に送信する。
【０１１９】
Ｓ９２では、サーバＳ０は［λ］０＝Ｒ′０,０−ｒ０,λ０＝τ０λ０として変換用乱数組（［λ］０,λ０）を得る。
【０１２０】
Ｓ９４では、サーバＳ１は［λ］１＝Ｒ′０,１として変換用乱数組（［λ］１,λ１）を得る。
【０１２１】
以上が、変換用乱数組生成１′の場合の説明である。
【０１２２】
以上説明したように、本発明の第１実施形態の手法を用いて変換用乱数組を生成することにより、安全に変換用乱数組を生成することができる。
【０１２３】
［第２実施形態］
第２実施形態は、上記問題点２に対応する。すなわち秘密情報に０を含む場合の手法である。
【０１２４】
まず第２実施形態の手法の前提について説明する。以下において,秘密情報ａ,ｂ,ｃ及び乱数αｊ,ｉ,βｊ,ｉ,γｊ,ｉ,ａ１,ｂ１,ｃ１はａ,ｂ,ｃ,αｊ,ｉ,βｊ,ｉ,γｊ,ｉ,ａ１,ｂ１,ｃ１∈Ｚ／ｐＺである。また、秘密情報に０を含んでもよいが、乱数は０を含まないものとする。また、第２実施形態では、第１実施形態に示した手法により変換用乱数組が予め生成されており、サーバＳｉは変換用乱数組（［εｈ,ｉ］ｉ,εｈ,ｉ）,（ｈ＝１,…,必要個数）を持つものとする。以下の説明においては、ｎ＝ｋにおける秘匿積和演算を示すが、ｎ＞ｋの場合、αｊ,ｉ,βｊ,ｉ,γｊ,ｉ,εｊ,ｉなどは（ｋ,ｎ）Ｓｈａｍｉｒ法で分散し、演算に参加するｋ台のサーバが復元してもよい。また、ａ＋ａ１のように秘密情報に加えられる乱数ａ１,ｂ１,ｃ１は０でなく、その加算結果も０とならない値を選ぶものとする。積和演算を組み合わせることにより、任意の四則演算を構成できるため、秘匿積和演算を例に以下、詳細を説明する。
【０１２５】
以上の前提を踏まえて、図５を参照して、本実施形態に係る秘密分散システム２１０の構成を説明する。図５に示すように、秘密分散システム２１０は、３台の入力装置２１２Ａ〜２１２Ｃ、及び複数台のサーバ２１６０〜２１６ｎ−１を含む。以下、入力装置２１２Ａ〜２１２Ｃについて共通する内容については「入力装置２１２」、サーバ２１６０〜２１６ｎ−１について共通する内容については「サーバ２１６」とし、末尾の識別記号を省略して説明する場合もある。入力装置２１２、及びサーバ２１６は、ネットワークＮに接続され、互いに通信可能とされる。なお、入力装置２１２が、第１生成部を含む分散装置の一例である。また、サーバ２１６が、第２生成部を含む秘匿演算装置の一例である。また、サーバ２１６が、第３生成部と、加算部とを含む秘匿演算装置の一例である。
【０１２６】
入力装置２１２は、秘密情報の入力者によって操作される装置である。入力装置２１２は、乱数を作用させた所定の値を生成して、サーバ２１６に分散する。
【０１２７】
サーバ２１６は、秘匿積和演算に係る計算などをする役割を持つ。
【０１２８】
次に、図６を参照して、本実施形態に係る入力装置２１２のハードウェア構成を説明する。図６に示すように、入力装置２１２は、ＣＰＵ２２０、一時記憶領域としてのメモリ２２１、不揮発性の記憶部２２２を含む。また、入力装置２１２は、表示装置２２３、入力Ｉ／Ｆ２２４、及びネットワークＮに接続されるネットワークＩ／Ｆ２２５を含む。ＣＰＵ２２０、メモリ２２１、記憶部２２２、表示装置２２３、入力Ｉ／Ｆ２２４、及びネットワークＩ／Ｆ２２５は、バス２２６に接続される。
【０１２９】
記憶部２２２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部２２２には、第１生成プログラム２２８が記憶される。ＣＰＵ２２０は、記憶部２２２から第１生成プログラム２２８を読み出してからメモリ２２１に展開し、展開した第１生成プログラム２２８を実行する。ＣＰＵ２２０が第１生成プログラム２２８を実行することで、開示の技術の第１生成部として動作する。なお、後述する第３〜第５実施形態においても同様である。
【０１３０】
次に、図７を参照して、本実施形態に係るサーバ２１６のハードウェア構成を説明する。図７に示すように、サーバ２１６は、ＣＰＵ２３０、一時記憶領域としてのメモリ２３１、不揮発性の記憶部２３２を含む。また、サーバ２１６は、表示装置２３３、入力Ｉ／Ｆ２３４、及びネットワークＮに接続されるネットワークＩ／Ｆ２３５を含む。ＣＰＵ２３０、メモリ２３１、記憶部２３２、表示装置２３３、入力Ｉ／Ｆ２３４、及びネットワークＩ／Ｆ２３５は、バス２３６に接続される。
【０１３１】
記憶部２３２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部２３２には、秘匿積和演算プログラム２３８が記憶される。秘匿積和演算プログラム２３８は、第２生成プロセス２３８ａと、第３生成プロセス２３８ｂと、加算プロセス２３８ｃとを含む。ＣＰＵ２３０は、記憶部２３２から秘匿積和演算プログラム２３８を読み出してからメモリ２３１に展開し、展開した秘匿積和演算プログラム２３８を実行する。ＣＰＵ２３０が秘匿積和演算プログラム２３８の第２生成プロセス２３８ａを実行することで、開示の技術の第２生成部として動作する。ＣＰＵ２３０が秘匿積和演算プログラム２３８の第３生成プロセス２３８ｂを実行することで、開示の技術の第３生成部として動作する。ＣＰＵ２３０が秘匿積和演算プログラム２３８の加算プロセス２３８ｃを実行することで、開示の技術の加算部として動作する。なお、後述する第３、第５実施形態においても同様である。なお、サーバ２１６において補正処理が行われない想定とし、秘匿積和演算プログラム２３８において第２生成プロセス２３８ａのみを含み、第３生成プロセス２３８ｂと、加算プロセス２３８ｃとを含まないようにしてもよい。
【０１３２】
次に、図８〜１０を参照して、本実施形態に係る秘密分散システム２１０の作用を説明する。
【０１３３】
まず、秘密情報を各サーバに分散する処理について説明する。図８は、秘密分散システム２１０における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置２１２Ａ〜Ｃが持つ秘密情報をサーバ２１６に分散する。以下において、サーバ２１６は、分散の処理シーケンスの各処理に応じてｎ台の全てのサーバである全サーバＳ、及びサーバＳｉのいずれかが対象であるものとして説明する。
【０１３４】
＜分散２＞
Ｓ２１０で、入力装置２１２Ａは、乱数ａ１,α１,ｉ,α２,ｉ（ｉ＝０,…,ｋ−１）を生成する。
【０１３５】
Ｓ２１２で、入力装置２１２Ａは、以下の式に基づいて、秘密情報ａに対してα１ａ１とα２（ａ＋ａ１）を計算する。
【０１３６】
2020056840.tif 000011
2020056840.tif 000012
【０１３７】
なお、Ｓ２１２は、入力装置２１２Ａにおける、第１生成プログラム２２８に対応する。入力装置２１２ＡのＣＰＵ２２０が、第１生成プログラム２２８を実行することで、開示の技術における第１生成部の処理を行う。秘密情報ａが第１の秘密情報、乱数ａ１が第１の乱数、乱数α２が第２の乱数、乱数α１が第３の乱数の一例である。α２（ａ＋ａ１）が、第１の乱数及び第２の乱数を作用させた第１の値の一例である。α１ａ１が、第１の乱数に第３の乱数を作用させた第２の値の一例である。第１生成プログラム２２８との対応は、以下、入力装置２１２Ｂ、及び入力装置２１２Ｃの秘密情報に対して行う処理において同様である。
【０１３８】
Ｓ２１４で、入力装置２１２Ａは、計算したα１ａ１とα２（ａ＋ａ１）を全サーバＳに送信する。
【０１３９】
Ｓ２１６で、入力装置２１２Ａは、乱数α１,ｉ,α２,ｉをサーバＳｉに送信する。
【０１４０】
Ｓ２１８で、入力装置２１２Ｂは、乱数ｂ１,β１,ｉ,β２,ｉ（ｉ＝０,…,ｋ−１）を生成する。
【０１４１】
Ｓ２２０で、入力装置２１２Ｂは、以下の式に基づいて、秘密情報ｂに対してβ１ｂ１とβ２（ｂ＋ｂ１）を計算する。
【０１４２】
2020056840.tif 000013
2020056840.tif 000014
【０１４３】
Ｓ２２２で、入力装置２１２Ｂは、計算したβ１ｂ１とβ２（ｂ＋ｂ１）を全サーバＳに送信する。
【０１４４】
Ｓ２２４で、入力装置２１２Ｂは、乱数β１,ｉ,β２,ｉをＳｉに送信する。
【０１４５】
Ｓ２２６で、入力装置２１２Ｃは、乱数ｃ１,γ１,ｉ,γ２,ｉ（ｉ＝０,…,ｋ−１）を生成する。
【０１４６】
Ｓ２２８で、入力装置２１２Ｃは、以下の式に基づいて、秘密情報ｃに対してγ１ｃ１とγ２（ｃ＋ｃ１）を計算する。
【０１４７】
2020056840.tif 000015
2020056840.tif 000016
【０１４８】
Ｓ２３０で、入力装置２１２Ｃは、計算したγ１ｃ１とγ２（ｃ＋ｃ１）を全サーバＳに送信する。
【０１４９】
Ｓ２３２で、入力装置２１２Ｃは、乱数γ１,ｉ,γ２,ｉをサーバＳｉに送信する。
【０１５０】
以上の分散の処理シーケンスを実行することで、サーバＳｉはα１ａ１,α２（ａ＋ａ１）,β１ｂ１,β２（ｂ＋ｂ１）,γ１ｃ１,γ２（ｃ＋ｃ１）とα１,ｉ,β１,ｉ,γ１,ｉ,α２,ｉ,β２,ｉ,γ２,ｉを持つことになる。また、サーバＳｉは、上記第１実施形態の手法で生成された変換用乱数組（［εｈ,ｉ］ｉ,εｈ,ｉ）（ｈ＝０,…,必要個数）も予め持つものとする。
【０１５１】
上記で説明した分散２の特徴は、秘密情報が漏洩しないよう、秘密情報に乱数を加えた値とその乱数のみが秘匿されて公開される点である。また、下記に説明する秘匿積和演算２は、秘密情報に乱数を加えた値とその乱数のみから、秘密情報による秘匿演算結果に乱数を加えた値とその乱数による秘匿演算結果が得られるように構成される。また、以下の秘匿積和演算において、計算結果を新たなα２（ａ＋ａ１）,α１ａ１などとするが、β１ｂ１,β２（ｂ＋ｂ１）またはγ１ｃ１,γ２（ｃ＋ｃ１）としてもよい。またα２,ｉ,α１,ｉも同様である。
【０１５２】
＜秘匿積和演算２＞
次に秘匿積和演算する処理について説明する。図９は、秘密分散システム２１０における、秘匿積和演算の処理シーケンスを説明したものである。図９では、説明の便宜のため、サーバ２１６のうち、サーバＳｉ、Ｓ０の間で秘匿積和演算の処理シーケンスが行われるものとし、図９上は全サーバＳへの送信はサーバＳｉに対する送信であるものとして説明するが、サーバＳｉで行われる処理はサーバＳ０でも行われる。
【０１５３】
Ｓ２４０で、サーバＳｉ（ｉ＝０,…,ｋ−１）は、以下の乱数δ１,ｉ,δ２,ｉを生成する。
【０１５４】
2020056840.tif 000017
【０１５５】
Ｓ２４２で、サーバＳｉは、Ｓ２４０で生成した乱数δ１,ｉ,δ２,ｉを用いて以下を計算する。
【０１５６】
2020056840.tif 000018
2020056840.tif 000019
【０１５７】
Ｓ２４４で、サーバＳｉは、Ｓ２４２の計算結果をサーバＳ０に送信する。
【０１５８】
Ｓ２４６で、サーバＳ０は、サーバＳｉから受信した計算結果を用いて、以下を計算する。ただし以降、Πはｉ＝０,…,ｋ−１に関する乗算を表す。
【０１５９】
2020056840.tif 000020
2020056840.tif 000021
【０１６０】
Ｓ２４８で、サーバＳ０は、Ｓ２４６の計算結果を全サーバＳに送信する。
【０１６１】
Ｓ２５０で、サーバＳｉは、サーバＳ０から受信した計算結果を用いて、以下を計算して公開し、計算結果を復元する。
【０１６２】
2020056840.tif 000022
【０１６３】
なお、Ｓ２５０は、サーバＳｉにおける、秘匿積和演算プログラム２３８の第２生成プロセス２３８ａに対応する。サーバＳｉのＣＰＵ２３０が、第２生成プロセス２３８ａを実行することで、開示の技術における第３の値の生成、及び第４の値の生成を行う。δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝が、開示の技術における第３の値の一例である。δ１（ｃ１−ａ１ｂ１）が、開示の技術における第４の値の一例である。第３の値は、複数の第１の秘密情報同士の演算結果（ａｂ＋ｃ）に複数の乱数同士の演算結果（ｃ１−ａ１ｂ１）、及び第４の乱数（δ２）を作用させた値である。また、第３の値は、複数の第１の秘密情報同士の演算結果を第１の秘密情報に置き換え、複数の第１の乱数同士の演算結果を第１の乱数に置き換え、第４の乱数を第２の乱数に置き換えた場合に第１の値と同形式になる。第４の値は、第１の乱数同士の演算結果（ｃ１−ａ１ｂ１）に第５の乱数（δ１）を作用させた値である。また、第４の値は、複数の第１の乱数同士の演算結果を第１の乱数に置き換え、第５の乱数を第３の乱数に置き換えた場合に第２の値と同形式になる。
【０１６４】
Ｓ２５２は、秘匿積和演算の処理シーケンスを繰り返す場合の処理である。Ｓ２５２で、サーバＳｉは、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝及びδ１（ｃ１−ａ１ｂ１）が０でなければ、その復元値を新たなα２（ａ＋ａ１）及びα１ａ１として設定し、δ２,ｉ,δ１,ｉを新たなα２,ｉ,α１,ｉに設定してＳ２４０に戻る。上記の秘匿積和演算の処理シーケンスは、例えば全てのサーバＳｉについて処理を終了するまで繰り返す。
【０１６５】
＜補正処理２＞
次に、補正処理について説明する。上述した図９の秘匿積和演算の処理シーケンスにおいて、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１）の少なくとも１つが０の場合、以下の補正処理を行う。図１０は、秘密分散システム２１０における補正処理の処理シーケンスを説明したものである。補正処理の処理シーケンスは、サーバ２１６のうち、全サーバＳ、サーバＳｉ、及びＳ０の間で行われるものとして説明する。また、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝＝０の場合を第１のケース、δ１（ｃ１−ａ１ｂ１）＝０の場合を第２のケースとして、第１のケース及び第２のケースのいずれか少なくとも一つに当てはまる場合の計算例を説明する。
【０１６６】
Ｓ２６０で、サーバＳｉは、新たな乱数τ１,ｉとａ′１,ｉを生成し、その積τ１,ｉａ′１,ｉを公開する。
【０１６７】
Ｓ２６２で、サーバＳｉは、τ１ａ′１＝Πτ１,ｉａ′１,ｉを新たなα１ａ１に設定する。また、τ１,ｉを新たなα１,ｉに設定する。なお、Ｓ２６２は、サーバＳｉにおける、秘匿積和演算プログラム２３８の第３生成プロセス２３８ｂに対応する。サーバＳｉのＣＰＵ２３０が、第３生成プロセス２３８ｂを実行することで、開示の技術における第６の乱数の生成を行う。ａ′１が、第６の乱数の一例である。
【０１６８】
Ｓ２６４で、サーバＳｉは、乱数τ２,ｉを生成する。
【０１６９】
Ｓ２６６で、サーバＳｉは、Ｓ２６４で生成した乱数τ２,ｉを用いて計算を行う。第１ケースの場合、
2020056840.tif 000023
と計算する。第２のケースの場合、
2020056840.tif 000024
と計算する。
【０１７０】
Ｓ２６８で、サーバＳｉは、Ｓ２６６の計算結果をサーバＳ０に送信する。
【０１７１】
Ｓ２７０で、サーバＳ０は、サーバＳｉから受信した計算結果を用いて、ｉについて乗算し計算を行う。第１のケースの場合
2020056840.tif 000025
と計算する。第２のケースの場合
2020056840.tif 000026
と計算する。
【０１７２】
Ｓ２７２で、サーバＳ０は、Ｓ２７０の計算結果をサーバＳｉに送信する。
【０１７３】
Ｓ２７４で、サーバＳｉは、Ｓ２７２で返却された計算結果を用いて計算を行い、秘密情報を復元する。第１のケースの場合
2020056840.tif 000027
を計算する。第２のケースの場合
2020056840.tif 000028
を計算する。なお、Ｓ２６４は、サーバＳｉにおける、秘匿積和演算プログラム２３８の加算プロセス２３８ｃに対応する。サーバＳｉのＣＰＵ２３０が、加算プロセス２３８ｃを実行することで、開示の技術における第６の乱数（ａ′）を秘匿加算する処理を行う。
【０１７４】
Ｓ２７６で、サーバＳｉは、Ｓ２７４の計算結果を用いて、新たなα２（ａ＋ａ１）を設定する。また、τ２,ｉを新たなα２,ｉに設定する。
【０１７５】
秘匿積和演算を繰り返す場合には、上記図９の秘匿積和演算の処理シーケンスのＳ２４０に戻る。
【０１７６】
以上が補正処理の処理シーケンスの説明である。以下に補正処理に関する補足を述べる。
【０１７７】
上記において、ｃ＝ｃ１＝ｃ＋ｃ１＝０としてｃに関する処理を省略すれば秘匿乗算になり、α２（ａ＋ａ１）＝α０ａ＝１としてａに関する処理を省略すれば秘匿加算になる。また、ａｂとｃの間の＋を−にすれば秘匿減算となる。また、α２（ａ＋ａ１）からα１ａ１を秘匿減算すればα０ａが出力されるので、上記秘匿積和演算の処理シーケンスのＳ２５０におけるα２（ａ＋ａ１）による乗算をα０ａによる除算にし、−β２（ｂ＋ｂ１）を−β１ｂ１にすれば
2020056840.tif 000029
の除算が実現できる。この場合、
2020056840.tif 000030
は
2020056840.tif 000031
に変化させる。
【０１７８】
上記において、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝＝０の場合、ａｂ＋ｃ＝（ａ１ｂ１−ｃ１）となるが、ａ１,ｂ１,ｃ１が秘匿されている。そのため、秘密情報ａｂ＋ｃは漏えいせず、（ａ１ｂ１−ｃ１）＝ａｂ＋ｃとして、ａ′１を秘密情報ａｂ＋ｃに加える新たな乱数とする。そして、新たなα２（ａ＋ａ１）及びα１ａ１を計算することによって、演算を継続可能とする。
【０１７９】
δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１）の２つが０の場合、ａｂ＋ｃ＝０が漏洩する。上記の補正処理の処理シーケンスの第１のケース及び第２のケースでは、簡単のためδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１）を同時に復元するように読めるが、まずδ１（ｃ１−ａ１ｂ１）を復元して０である場合、以下を計算してδ２（ａｂ＋ｃ＋ａ′１）を復元する。
【０１８０】
2020056840.tif 000032
【０１８１】
このとき、δ２（ａｂ＋ｃ＋ａ′１）が０であれば、補正処理の処理シーケンスにおけるＳ２７４の第１のケースの場合の計算を行えばよい。これによって、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１）の２つが０であったとしてもａｂ＋ｃ＝０は漏洩しない。
【０１８２】
また、後述の第５実施形態の秘匿積和演算に示すようにδ１（ｃ１−ａ１ｂ１）,δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝のどちらかが０であった場合、０となった値を新たな乱数で置き換え、０でない値の方にその乱数を加えてもよい。
【０１８３】
以上説明したように、本発明の第２実施形態の手法を用いて秘匿積和演算を行うことにより、秘密情報に０を含んでいても、効率よく秘匿演算を繰り返すことができる。
【０１８４】
なお、復元を行う場合、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝からδ１（ｃ１−ａ１ｂ１）を秘匿減算すればδ０（ａｂ＋ｃ）が得られ、復元者はδ０を復元してその値を排除することにより、秘密情報による演算結果（ａｂ＋ｃ）が得られる。この処理は復元装置によって実行されるので、復元を含む場合、後述する図１１と同様のネットワーク構成となる。
【０１８５】
［第３実施形態］
第３実施形態は、上記問題点３に対応する。すなわち秘匿計算の検証を実現する機能である。以下は、簡単のため秘密情報ａ,ｂ,ｃ及び演算結果に０を含まない場合に検証を行う場合を例に説明する。
【０１８６】
図１１を参照して、本実施形態に係る秘密分散システム３１０の構成を説明する。図１１に示すように、秘密分散システム３１０は、３台の入力装置３１２Ａ〜３１２Ｃ、復元装置３１４、及び複数台のサーバ３１６０〜３１６ｎ−１を含む。以下、入力装置３１２Ａ〜３１２Ｃについて共通する内容については「入力装置３１２」、サーバ３１６０〜３１６ｎ−１について共通する内容については「サーバ３１６」とし、末尾の識別記号を省略して説明する場合もある。入力装置３１２、復元装置３１４、及びサーバ３１６は、ネットワークＮに接続され、互いに通信可能とされる。なお、復元装置３１４が、第１排除部と、第１判定部とを含む検証復元装置の一例である。
【０１８７】
入力装置３１２は、秘密情報の入力者によって操作される装置である。入力装置３１２は、乱数を作用された所定の値を生成して、サーバ３１６に分散する。
【０１８８】
復元装置３１４は、秘密情報の復元者によって操作される装置である。復元装置３１４は、入力装置３１２、及びサーバ３１６によって公開されている値を収集して、秘匿積和演算の結果に不正がないかを検証する。
【０１８９】
サーバ３１６は、秘匿積和演算に係る計算などをする役割を持つ。
【０１９０】
次に、図１２を参照して、本実施形態に係る復元装置３１４のハードウェア構成を説明する。なお、入力装置３１２、及びサーバ３１６については第２実施形態と同様の装置構成をとることができるため詳細な説明を省略する。
【０１９１】
図１２に示すように、復元装置３１４は、ＣＰＵ３４０、一時記憶領域としてのメモリ３４１、不揮発性の記憶部３４２を含む。また、復元装置３１４は、表示装置３４３、入力Ｉ／Ｆ３４４、及びネットワークＮに接続されるネットワークＩ／Ｆ３４５を含む。ＣＰＵ３４０、メモリ３４１、記憶部３４２、表示装置３４３、入力Ｉ／Ｆ３４４、及びネットワークＩ／Ｆ３４５は、バス３４６に接続される。
【０１９２】
記憶部３４２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部３４２には、復号プログラム３４８が記憶される。復号プログラム３４８は、第１排除プロセス３４８ａと、第１判定プロセス３４８ｂと、復元プロセス３４８ｃとを含む。ＣＰＵ３４０は、記憶部３４２から復号プログラム３４８を読み出してからメモリ３４１に展開し、展開した復号プログラム３４８を実行する。ＣＰＵ３４０が第１生成プログラム３４８の第１排除プロセス３４８ａを実行することで、開示の技術の第１排除部として動作する。ＣＰＵ３４０が第１生成プログラム３４８の第１判定プロセス３４８ｂを実行することで、開示の技術の第１判定部として動作する。ＣＰＵ３４０が第１生成プログラム３４８の復元プロセス３４８ｃを実行することで、開示の技術の復元部として動作する。
【０１９３】
次に、図１３〜１５を参照して、本実施形態に係る秘密分散システム３１０の作用を説明する。
【０１９４】
＜分散３＞
まず、秘密情報を各サーバに分散する処理について説明する。図１３は、秘密分散システム３１０における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置３１２Ａ〜Ｃが持つ秘密情報をサーバ３１６に分散する。以下において、サーバ３１６は、分散の処理シーケンスの各処理に応じてｎ台の全てのサーバである全サーバＳ、及びサーバＳｉのいずれかが対象であるものとして説明する。
【０１９５】
Ｓ３１０で、入力装置３１２Ａは、乱数αｉ,０,…,αｉ,ｋ−１（ｉ＝０,２）を生成する。
【０１９６】
Ｓ３１２で、入力装置３１２Ａは、乱数αｉ＝Πｊ＝０ｋ−１αｉ,ｊを計算する。
【０１９７】
Ｓ３１４で、入力装置３１２Ａは、乱数ａ１を生成し、秘密情報ａに対して以下を計算して計算結果を公開する。また、入力装置３１２Ａは、ａ１に対するハッシュ値ｈａ１を公開する。
【０１９８】
2020056840.tif 000033
【０１９９】
Ｓ３１６で、入力装置３１２Ａは、α０,ｊ,α２,ｊをサーバＳｉに送信する。
【０２００】
Ｓ３１８で、入力装置３１２Ｂは、乱数βｉ,０,…,βｉ,ｋ−１（ｉ＝０,２）を生成する。
【０２０１】
Ｓ３２０で、入力装置３１２Ｂは、乱数βｉ＝Πｊ＝０ｋ−１βｉ，ｊを計算する。
【０２０２】
Ｓ３２２で、入力装置３１２Ｂは、乱数ｂ１を生成し、秘密情報ｂに対して以下を計算して計算結果を公開する。また、入力装置３１２Ｂは、ｂ１に対するハッシュ値ｈｂ１を公開する。
【０２０３】
2020056840.tif 000034
【０２０４】
Ｓ３２４で、入力装置３１２Ｂは、β０,ｊ,β２,ｊをサーバＳｉに送信する。
【０２０５】
Ｓ３２６で、入力装置３１２Ｃは、乱数γｉ,０,…,γｉ,ｋ−１（ｉ＝０,２）を生成する。
【０２０６】
Ｓ３２８で、入力装置３１２Ｃは、乱数γｉ＝Πｊ＝０ｋ−１γｉ，ｊを計算する。
【０２０７】
Ｓ３３０で、入力装置３１２Ｃは、乱数ｃ１を生成し、秘密情報ｃに対して以下を計算して計算結果を公開する。また、入力装置３１２Ｃは、ｃ１に対するハッシュ値ｈｃ１を公開する。
【０２０８】
2020056840.tif 000035
【０２０９】
Ｓ３３２で、入力装置３１２Ｃは、γ０,ｊ,γ２,ｊをサーバＳｉに送信する。
【０２１０】
以上の分散の処理シーケンスにより、サーバＳｉは、以下を持つことになる。
【０２１１】
2020056840.tif 000036
【０２１２】
なお、入力装置３１２Ａ、入力装置３１２Ｂ、及び入力装置３１２Ｃは、ａ１,ｂ１,ｃ１を秘密分散してもよい。
【０２１３】
＜秘匿積和演算３＞
次に秘匿積和演算する処理について説明する。
【０２１４】
秘匿積和演算の前提として、分散処理は正しく行われているものとする。ここでは変換用乱数組として（［μｈ］ｉ,μｈ,ｉ）（ｈ＝１,…,必要個数）も持つものとする。
【０２１５】
以下において、ｃ＝ｃ１＝ｃ＋ｃ１＝０としてｃに関する処理を省略すれば秘匿乗算になり、α２（ａ＋ａ１）＝α０ａ＝１としてａに関する処理を省略すれば秘匿加算になる。また、ａｂとｃの間の＋を−にすれば秘匿減算となる。また以下の秘匿積和演算において、計算結果を新たなα２（ａ＋ａ１）,α１ａ１などとするが、β１ｂ１,β２（ｂ＋ｂ１）またはγ１ｃ１,γ２（ｃ＋ｃ１）としてもよい。α２,ｉ，α１,ｉについても同様である。
【０２１６】
図１４は、秘密分散システム３１０における、秘匿積和演算の処理シーケンスを説明したものである。図１４では、説明の便宜のため、サーバ３１６のうち、サーバＳｉまたは全サーバＳおいて秘匿積和演算の処理シーケンスが行われるものとして説明する。
【０２１７】
Ｓ３４０で、サーバＳｉは、乱数δ０,ｉ,δ２,ｉを生成する。
【０２１８】
Ｓ３４２で、サーバＳｉは、生成した乱数δ０,ｉ,δ２,ｉを用いて、以下を計算して計算結果を公開する。ただし、０となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。
【０２１９】
2020056840.tif 000037
【０２２０】
Ｓ３４４で、全サーバは、以下を計算する。
【０２２１】
2020056840.tif 000038
【０２２２】
Ｓ３４６で、サーバＳｉは、以下を計算して復元し、復元したδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ０（ａｂ＋ｃ）を公開する。
【０２２３】
2020056840.tif 000039
【０２２４】
Ｓ３４８は、演算を継続する場合の処理である。Ｓ３４８で、サーバＳｉは、δ０（ａｂ＋ｃ）,δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）を新たなα０ａ,α２（ａ＋ａ１）に設定し、新たなα０ａ,α２（ａ＋ａ１）に合わせて、δ０,ｉ,δ２,ｉを新たなα０,ｉ,α２,ｉに設定してＳ３４０に戻る。
【０２２５】
＜検証・復元３＞
次に、検証処理について説明する。図１５は、秘密分散システム３１０における検証の処理シーケンスを説明したものである。検証の処理シーケンスにおいて、入力装置３１２Ａ、入力装置３１２Ｂ、及び入力装置３１２Ｃは、それぞれａ１,ｂ１,ｃ１を公開しているものとする。
【０２２６】
Ｓ３６０で、復元装置３１４は、サーバＳｉからδ０,ｉ,δ２,ｉを収集する。
【０２２７】
Ｓ３６２で、復元装置３１４は、収集したδ０,ｉ,δ２,ｉの積δ０,δ２を計算し、積δ０,δ２を用いて以下を計算して公開する。
【０２２８】
2020056840.tif 000040
【０２２９】
なお、Ｓ３６２は、復元装置３１４における、復号プログラム３４８の第１排除プロセス３３８ａに対応する。復元装置３１４のＣＰＵ３４０が、第１排除プロセス３４８ａを実行することで、開示の技術における第１排除部の処理を行う。上記の計算が、秘密情報同士の演算結果に対して乱数を作用させて生成した第３の値δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝とδ０（ａｂ＋ｃ）を用いて秘密情報（ａｂ＋ｃ）と第４の乱数δ２,δ０に相当する値を排除し、判定を行うための第１の乱数同士の演算結果を得ることに対応する。
【０２３０】
Ｓ３６４で、復元装置３１４は、入力装置３１２Ａ、入力装置３１２Ｂ、及び入力装置３１２Ｃが公開しているａ１,ｂ１,ｃ１及びそのハッシュ値を収集する。
【０２３１】
Ｓ３６６で、復元装置３１４は、公開されているａ１,ｂ１,ｃ１と、そのハッシュ値が一致するかを検証し、ハッシュ値が正しければＳ３６８へ移行し、正しくなければＳ３７４へ移行して不正検出とする。
【０２３２】
Ｓ３６８で、復元装置３１４は、公開されているａ１,ｂ１,ｃ１を用いてｃ１−ａ１ｂ１を計算する。
【０２３３】
Ｓ３７０で、復元装置３１４は、公開されているａ１,ｂ１,ｃ１から計算されたｃ１−ａ１ｂ１と、Ｓ３６２で計算されたｃ１−ａ１ｂ１が等しいか検証し、計算結果が正しければＳ３７２へ移行し、正しくなければＳ３７４へ移行して不正検出とする。
【０２３４】
なお、Ｓ３７０は、復元装置３１４における、復号プログラム３４８の第１判定プロセス３４８ｂに対応する。復元装置３１４のＣＰＵ３４０が、第１判定プロセス３４８ｂを実行することで、開示の技術における第１判定部の処理を行う。
【０２３５】
Ｓ３７２で、復元装置３１４は、検証結果が正しい場合、Ｓ３６２で用いられたδ０（ａｂ＋ｃ）／δ０をａｂ＋ｃと判定する。
【０２３６】
Ｓ３７４で、検証結果が不正検出であるものとする。
【０２３７】
以上が、検証の処理シーケンスである。なお、ａ１,ｂ１,ｃ１が秘密分散されている場合、Ｓ３６６に対応する処理として、各サーバでａ１,ｂ１,ｃ１の分散値を公開して、復元装置３１４でａ１,ｂ１,ｃ１を復元してもよい。
【０２３８】
また、演算が繰り返されている場合、Ｓ３６２において乱数による最終的な演算結果を復元し、Ｓ３６４で全乱数を収集して、その乱数を用いて同様の演算を構成し、Ｓ３６２の結果とＳ３６８の結果が一致するかを検証する。
【０２３９】
攻撃者が入力値や乱数を知らない場合、（ｃ１−ａ１ｂ１）が一致するように操作できないことが言える。よって、その計算に使用したδ０（ａｂ＋ｃ）／δ０は正しいといえる。
【０２４０】
また、検証処理は演算の最後でなく、任意の積和演算単位で検証することも可能である。
【０２４１】
また、本実施形態における検証の処理シーケンスは復元装置３１４が行うものとしたが、サーバＳｉがδ０,ｉ,δ２,ｉを公開すればどの装置でも公開値から検証可能である。この場合、復元者は不正ができないこととなる。
【０２４２】
ただし、サーバＳｉがδ０,ｉ,δ２,ｉを公開する場合、例えば入力者Ａが攻撃者で、分散処理においてハッシュ値を公開したａ１と異なるａ′１を用いてａ＋ａ′１を入力し、ａ１を公開しているとすれば、Ｓ３７０における検証結果は不正となるが、Ｓ３６２においてδ０（ａｂ＋ｃ）／δ０は復元されているので、攻撃者のみ演算結果が正しいことを知ることができる。よって、Ｓ３６０、Ｓ３６２を以下Ｓ３６０′〜Ｓ３６４′のように変形し、Ｓ３７０の結果が正しい場合に以下Ｓ３７１′を追加して処理するようにすれば、δ０（ａｂ＋ｃ）は秘匿されたままａ１ｂ１＋ｃ１が計算されるので、攻撃者のみ演算結果を知ることを防止できる。また、下記Ｓ３６０′〜Ｓ３６４′における秘匿計算を秘匿積和演算の一環と考えれば、下記Ｓ３６０′〜Ｓ３６４′における処理も検証されるため不正を行えば検証される。また、Ｓ３７４を復元装置３１４ではなく、サーバＳｉがδ０,ｉ,［μ７］ｉ,［μ８］ｉを公開すれば、公開の処理とできる。この対策は以降の実施形態においても適用できる。
【０２４３】
Ｓ３６０′では、サーバＳｉは、（１／δ０,ｉμ７,ｉ）,（１／δ２,ｉμ８,ｉ）を復元装置３１４に送信する。
【０２４４】
Ｓ３６２′では、復元装置３１４は、受信したその積（１／δ０μ７）,（１／δ２μ８）を公開して、各サーバが計算した以下を収集する。
【０２４５】
2020056840.tif 000041
【０２４６】
Ｓ３６４′では、復元装置３１４は、収集した上記の計算結果を復元してその結果を公開する。
【０２４７】
Ｓ３７１′では、復元装置３１４は、Ｓ３７０の結果が正しいとき、δ０,ｉ,［μ７］ｉ,［μ８］ｉを収集してＳ３６４′の結果を検算し、計算したδ０（ａｂ＋ｃ）／δ０をａｂ＋ｃとする。検算結果が一致しない場合、［ａ１ｂ１＋ｃ１］ｉが一致しないサーバを不正とする。
【０２４８】
ただし、入力者が攻撃者の場合、以下のようにすれば不正検出されずに、偽の答えを復元者に得させることができる。例えば、ユーザＣはｃ,ｃ１を知っており、ａ,ｂと独立であるので、ｃに関連する部分のみ正しくない処理をしてもｃ１と一致させることが可能である。この対策は次の実施形態で示される。
【０２４９】
よって、本実施形態は入力者が不正をしない場合、すなわち攻撃者がｋ−１台までのサーバまたは入力を知らない外部攻撃者の場合に対して有効である。
【０２５０】
また、復元装置３１４は、第１排除部から得られる値から第１の秘密情報同士の演算結果を得る演算結果を得る復元部を含む秘匿演算装置として機能する。復元装置３１４は、上記、本実施形態の各処理シーケンスを経て、復元プロセス３４８ｃの実行によって、Ｓ３７２から得られる値を取得し、第１の秘密情報同士の演算結果（ａｂ＋ｃ）を得る。
【０２５１】
以上説明したように、本発明の第３実施形態の手法を用いて秘匿積和演算を検証することにより、秘匿積和演算の不正を検出することができる。
【０２５２】
［第４実施形態］
第４実施形態は、第３実施形態では入力を知るユーザの不正は防げなかった点に着目し、本実施形態ではユーザの結託を含む不正を防止することができる手法を示す。
【０２５３】
第４実施形態の構成は上記図５の第２実施形態と同様の構成をとることができ、秘密分散システム４１０において、入力装置２１２を入力装置４１２に、サーバ２１６をサーバ４１６に置き換えた構成とすればよい。なお、サーバ４１６が分散装置の一例であり、秘密分散システム４１０が分散システムの一例である。
【０２５４】
秘密分散システム４１０において、不正の防止のためには、ａ１,ｂ１,ｃ１を入力装置４１２だけで生成しないようにする。これによって、例えば、入力装置４１２Ｃを操作するユーザＣはｃ１を知らないため、Ｃに関する部分を不正にｃ１に一致させられなくなる。また、本実施の形態は第３の実施の形態と同様に秘密情報に０は含まないが、第１の実施の形態に示す変換用乱数組（［εｈ］ｉ，εｈ,ｉ）（ｈ＝１,…,１２）が事前に配布されているものとする。
【０２５５】
次に、図１６を参照して、本実施形態に係るサーバ４１６のハードウェア構成を説明する。なお、入力装置４１２については第２実施形態と同様のハードウェア構成をとることができるため、詳細な説明を省略する。
【０２５６】
図１６に示すように、サーバ４１６は、ＣＰＵ４３０、一時記憶領域としてのメモリ４３１、不揮発性の記憶部４３２を含む。また、サーバ４１６は、表示装置４３３、入力Ｉ／Ｆ４３４、及びネットワークＮに接続されるネットワークＩ／Ｆ４３５を含む。ＣＰＵ４３０、メモリ４３１、記憶部４３２、表示装置４３３、入力Ｉ／Ｆ４３４、及びネットワークＩ／Ｆ４３５は、バス４３６に接続される。
【０２５７】
記憶部４３２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部４３２には、秘匿積和演算プログラム２３８、及び第４生成プログラム４４０が記憶される。ＣＰＵ４３０は、記憶部４３２から第４生成プログラムを読み出してからメモリ４３１に展開し、展開した第４生成プログラム４４０を実行する。ＣＰＵ４３０が第４生成プログラム４４０を実行することで、開示の技術の第４生成部として動作する。
【０２５８】
次に、図１７を参照して、本実施形態に係る秘密分散システム４１０の作用を説明する。第４実施形態は分散の処理シーケンスが、第３実施形態と異なるため、分散の処理シーケンスについてのみ説明する。図１７は、秘密分散システム４１０における分散の処理シーケンスを説明したものである。
【０２５９】
＜分散４＞
Ｓ４１０で、入力装置４１２Ａは、ｋ個の乱数α０,０,…,α０,ｋ−１生成し、乱数α０＝Πｊ＝０ｋ−１α０,ｊを計算する。
【０２６０】
Ｓ４１２で、入力装置４１２Ａは、ｋ個の乱数の組（α１ａ,０,…,α１ａ,ｋ−１）,（β１ａ,０,…,β１ａ,ｋ−１）,（γ１ａ,０,…,γ１ａ,ｋ−１）を生成し、乱数α１ａ＝Πｊ＝０ｋ−１α１ａ,ｊ,β１ａ＝Πｊ＝０ｋ−１β１ｂ,ｊ,γ１ａ＝Πｊ＝０ｋ−１γ１ａ,ｊを計算する。
【０２６１】
Ｓ４１４で、入力装置４１２Ａは、秘密情報ａに対してα０ａ＝α０×ａを計算して公開する。
【０２６２】
Ｓ４１６で、入力装置４１２Ａは、（α１ａ,ｉ,β１ａ,ｉ,γ１ａ,ｉ,α０,ｉ）をサーバＳｉに送信する。
【０２６３】
Ｓ４１８で、入力装置４１２Ａは、乱数ａ１ａ,ｂ１ａ,ｃ１ａを生成する。
【０２６４】
Ｓ４２０で、入力装置４１２Ａは、Ｓ４１８で生成した乱数を用いて、以下を計算してα１ａａ１ａ,β１ａｂ１ａ,γ１ａｃ１ａを公開する。また、入力装置４１２Ａは、乱数ａ１ａ,ｂ１ａ,ｃ１ａを保持し、そのハッシュ値ｈａ１,ａ,ｈｂ１,ａ,ｈｃ１,ａを公開する。
【０２６５】
2020056840.tif 000042
【０２６６】
Ｓ４２２で、入力装置４１２Ｂは、ｋ個の乱数β０,０,…,β０,ｋ−１を生成し、乱数β０＝Πｊ＝０ｋ−１β０,ｊを計算する。
【０２６７】
Ｓ４２４で、入力装置４１２Ｂは、ｋ個の乱数の組（α１ｂ,０,…,α１ｂ,ｋ−１）,（β１ｂ,０,…,β１ｂ,ｋ−１）,（γ１ｂ,０,…,γ１ｂ,ｋ−１）を生成し、乱数α１ｂ＝Πｊ＝０ｋ−１α１ｂ,ｊ,β１ｂ＝Πｊ＝０ｋ−１β１ｂ,ｊ,γ１ｂ＝Πｊ＝０ｋ−１γ１ｂ,ｊを計算する。
【０２６８】
Ｓ４２６で、入力装置４１２Ｂは、秘密情報ｂに対してβ０ｂ＝β０×ｂを計算して公開する。
【０２６９】
Ｓ４２８で、入力装置４１２Ｂは、（α１ｂ,ｉ,β１ｂ,ｉ,γ１ｂ,ｉ,β０,ｉ）をサーバＳｉに送信する。
【０２７０】
Ｓ４３０で、入力装置４１２Ｂは、ユーザＢは乱数ａ１ｂ,ｂ１ｂ,ｃ１ｂを生成する。
【０２７１】
Ｓ４３２で、入力装置４１２Ｂは、Ｓ４３０で生成した乱数を用いて、以下を計算してα１ｂａ１ｂ,β１ｂｂ１ｂ,γ１ｂｃ１ｂを公開する。また、ユーザＢは乱数ａ１ｂ,ｂ１ｂ,ｃ１ｂを保持し、そのハッシュ値ｈａ１,ｂ,ｈｂ１,ｂ,ｈｃ１,ｂを公開する。
【０２７２】
2020056840.tif 000043
【０２７３】
Ｓ４３４で、入力装置４１２Ｃは、ｋ個の乱数γ０,０,…,γ０,ｋ−１を生成し、乱数γ０＝Πｊ＝０ｋ−１γ０,ｊを計算する。
【０２７４】
Ｓ４３６で、入力装置４１２Ｃは、ｋ個の乱数の組（α１ｃ,０,…,α１ｃ,ｋ−１）,（β１ｃ,０,…,β１ｃ,ｋ−１）,（γ１ｃ,０,…,γ１ｃ,ｋ−１）を生成し、乱数α１ｃ＝Πｊ＝０ｋ−１α１ｃ,ｊ,β１ｃ＝Πｊ＝０ｋ−１２β１ｃ,ｊ,γ１ｃ＝Πｊ＝０ｋ−１γ１ｃ,ｊを計算する。
【０２７５】
Ｓ４３８で、入力装置４１２Ｃは、ユーザＣは秘密情報ｃに対してγ０ｃ＝γ０×ｃを計算して公開する。
【０２７６】
Ｓ４４０で、入力装置４１２Ｃは、（α１ｃ,ｉ,β１ｃ,ｉ,γ１ｃ,ｉ,γ０,ｉ）をサーバＳｉに送信する。
【０２７７】
Ｓ４４２で、入力装置４１２Ｃは、乱数ａ１ｃ,ｂ１ｃ,ｃ１ｃを生成する。
【０２７８】
Ｓ４４４で、入力装置４１２Ｃは、Ｓ４４２で生成した乱数を用いて、以下を計算してα１ｃａ１ｃ,β１ｃｂ１ｃ,γ１ｃｃ１ｃ公開する。また、ユーザＣは乱数ａ１ｃ,ｂ１ｃ,ｃ１ｃを保持し、そのハッシュ値ｈａ１,ｃ,ｈｂ１,ｃ,ｈｃ１,ｃを公開する。
【０２７９】
2020056840.tif 000044
【０２８０】
以上が入力装置４１２Ａ〜Ｃでの処理である。以下からはサーバＳｉでの処理である。
【０２８１】
Ｓ４４６で、サーバＳｉは、乱数α１,ｉ,β１,ｉ,γ１,ｉを生成する。
【０２８２】
Ｓ４４８で、サーバＳｉは、Ｓ４４６で生成した乱数を用いて、以下を計算し、計算結果を公開する。ただし、０となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。
【０２８３】
2020056840.tif 000045
2020056840.tif 000046
【０２８４】
Ｓ４５０で、サーバＳｉは、ｉに関する乗算により、以下を計算する。
【０２８５】
2020056840.tif 000047
【０２８６】
Ｓ４５２で、サーバＳｉは、変換用乱数組［ε１］ｉ〜［ε９］ｉを用いて以下を計算し、計算結果を公開する。
【０２８７】
2020056840.tif 000048
【０２８８】
なお、Ｓ４５０は、サーバＳｉにおける、第４生成プログラム４４０に対応する。サーバＳｉのＣＰＵ４３０が、第４生成プログラム４４０を実行することで、開示の技術における第４生成部の処理を行う。例えば計算の過程で、乱数ａ１を、ａ１ａ,ａ１ｂ,ａ１ｃを用いて生成する。ａ１ａ,ａ１ｂ,ａ１ｃが、第１の秘密情報の生成者以外が生成した乱数の一例である。
【０２８９】
Ｓ４５４で、サーバＳｉは、α１ａ１,β１ｂ１,γ１ｃ１を復元する。
【０２９０】
Ｓ４５６で、サーバＳｉは、乱数α２,ｉ,β２,ｉ,γ２,ｉを生成する。
【０２９１】
Ｓ４５８で、サーバＳｉは、Ｓ４５６で生成した乱数を用いて、以下を計算し、計算結果を公開する。ただし、０となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。
【０２９２】
2020056840.tif 000049
【０２９３】
Ｓ４６０で、サーバＳｉは、ｉに関する乗算により、以下を計算する。
【０２９４】
2020056840.tif 000050
【０２９５】
Ｓ４６２で、サーバＳｉは、以下を計算し、計算結果を公開する。
【０２９６】
2020056840.tif 000051
【０２９７】
Ｓ４６４で、サーバＳｉは、α２（ａ＋ａ１）,β２（ｂ＋ｂ１）,γ２（ｃ＋ｃ１）を復元する。
【０２９８】
以上の分散の処理シーケンスにより、サーバＳｉは、は変換用乱数組の他に以下を持つことになる。なお、入力装置４１２Ａ、入力装置４１２Ｂ、及び入力装置４１２Ｃはそれぞれａ１ｈ,ｂ１ｈ,ｃ１ｈ（ｈ＝ａ,ｂ,ｃ）を秘密分散してもよい。
【０２９９】
2020056840.tif 000052
【０３００】
以上が本実施形態の分散の処理シーケンスである。
【０３０１】
本実施の形態に対する秘匿積和演算は第３実施形態と同様であり、検証も第３実施形態と基本的には同じである。ただし、ａ１,ａ,ａ１,ｂ,ａ１,ｃ,ｂ１,ａ,ｂ１,ｂ,ｂ１,ｃ,ｃ１,ａ,ｃ１,ｂ,ｃ１,ｃをハッシュ値で検証し、ａ１,ｂ１,ｃ１をａ１＝ａ１,ａ＋ａ１,ｂ＋ａ１,ｃ,ｂ１＝ｂ１,ａ＋ｂ１,ｂ＋ｂ１,ｃ,ｃ１＝ｃ１,ａ＋ｃ１,ｂ＋ｃ１,ｃによって計算することだけが異なる。また、演算が繰り返された場合、全てのａ１ｈ,ｂ１ｈ,ｃ１ｈ（ｈ＝ａ,ｂ,ｃ）を集めて乱数による演算部分の正当性を検証する。
【０３０２】
安全性に関しては、入力者が攻撃者ではない場合、すなわち攻撃者がｋ−１台までのサーバまたは外部攻撃者である場合は第３の実施の形態と同様に安全であることが言える。それに加えて、本実施形態ではａ１,ｂ１,ｃ１を入力装置４１２Ａを操作するユーザＡ、入力装置４１２Ｂを操作するユーザＢ、及び入力装置４１２Ｃを操作するユーザＣの全員で生成するため、入力者が攻撃者となっても安全であることが以下のように言える。
【０３０３】
例えば、ユーザＣが攻撃者である場合、ユーザＣはｃを知るが、ｃ１を知らない。これはｃ１はユーザＡ,Ｂ,Ｃによって作られるためである。よって、ユーザＣはＣに関する部分を不正に操作しても、ｃ１を知らないため最終結果を０にできない。また、ユーザＣはｑ４−ｑ６を操作できるが、ｃ１を知らないため、他の値を調整できない。これはユーザ２者の結託に関しても言うことができ、（ｃ１−ａ１ｂ１）′−（ｃ１−ａ１ｂ１）＝０であれば不正が行われていないことが言える。
【０３０４】
ただし、ａ,ｂ,ｃの値を知る全員が結託すれば、（ｃ１−ａ１ｂ１）′−（ｃ１−ａ１ｂ１）＝０としながら、異なる値を秘密情報による計算結果とすることができる。１回の秘匿積和演算において全員が結託することは想定しないが、秘匿積和演算を繰り返す場合、１つの積和演算を実行する全入力者が結託すれば、上記差分値を０にしたまま、不正な値を計算結果とすることができる。よって、秘匿積和演算を繰り返す場合、１回の積和演算を構成する入力者は全員結託することはないという前提を置く。また、秘匿積和演算を繰り返し、１つの積和演算に関する入力者全員の結託が考えられる場合、乱数ａ１,ｂ１,ｃ１も漏洩する。よって、演算参加者が乱数ａ１,ｂ１,ｃ１を知らないようにするため、各サーバが予め保有する変換用乱数組を用いる。このようにすると、分散４は以下のように非常に簡単にできる。
【０３０５】
［第４実施形態の変形例］
以下に、第４実施形態の変形例として、変換用乱数組（［λ］ｊ,λｉ）,（［ε］ｊ,εｉ）,（［μ］ｊ,μｉ）を用いる例を示す。以下におけるａ１等はα１,ｉの乗算によって構成され、ａ１等の値は誰も知らないので安全である。以下の［α２（ａ＋ａ１）］ｉなどの生成において、ａ＝０の場合でも利用できる手法も示す。
【０３０６】
図１８は、変形例における分散の処理シーケンスを説明したものである。図１８のシーケンスにおいて、以下のＳ４７０〜Ｓ４９０の処理が行われる。なお、図１８において各処理は簡略化して記載するものとする。
【０３０７】
＜分散４′＞
Ｓ４７０で、入力装置４１２Ａは、乱数α２,ｊ（ｊ＝０,…,ｋ−１）を生成して乱数α２＝Πｊ＝０ｋ−１α２,ｊを計算し、秘密情報ａに対してα２ａ＝α２×ａを計算して秘密分散する。
【０３０８】
Ｓ４７２で、入力装置４１２Ａは、α２,ｊ,［α２ａ］ｊをサーバＳｊに送信する。
【０３０９】
Ｓ４７４で、入力装置４１２Ｂは、乱数β２,ｊ（ｊ＝０,…,ｋ−１）を生成して乱数β２＝Πｊ＝０ｋ−１β２,ｊを計算し、秘密情報ｂに対してβ２ｂ＝β２×ｂを計算して秘密分散する。
【０３１０】
Ｓ４７６で、入力装置４１２Ｂは、β２,ｊ,［β２ｂ］ｊをサーバＳｊに送信する。
【０３１１】
Ｓ４７８で、入力装置４１２Ｃは、乱数γ２,ｊ（ｊ＝０,…,ｋ−１）生成して乱数γ２＝Πｊ＝０ｋ−１γ２,ｊを計算し、秘密情報ｃに対してγ２ｃ＝γ２×ｃを計算して秘密分散する。
【０３１２】
Ｓ４８０で、入力装置４１２Ｃは、γ２,ｊ,［γ２ｃ］ｊをサーバＳｊに送る。
【０３１３】
Ｓ４８２で、サーバＳｉは乱数ａ１,ｉ,ｂ１,ｉ,ｃ１,ｉを定め、λｉ＝α１,ｉａ１,ｉ,εｉ＝β１,ｉｂ１,ｉ,μｉ＝γ１,ｉｃ１,ｉと分解する。サーバＳｉはａ１,ｉ,ｂ１,ｉ,ｃ１,ｉのハッシュ値を公開する。
【０３１４】
Ｓ４８４で、サーバＳｉは、［λ］ｉ,［ε］ｉ,［μ］ｉを公開してλ＝α１ａ１,ε＝β１ｂ１,μ＝γ１ｃ１を復元する。ただし、α１＝Πｉ＝０ｋ−１α１,ｉ,ａ１＝Πｉ＝０ｋ−１ａ１,ｉ,β１＝Πｉ＝０ｋ−１β１,ｉ,ｂ１＝Πｉ＝０ｋ−１ｂ１,ｉ,γ１＝Πｉ＝０ｋ−１γ１,ｉ,ｃ１＝Πｉ＝０ｋ−１ｃ１,ｉとする。
【０３１５】
Ｓ４８６で、サーバＳｉは、乱数α２,ｉ,β２,ｉ,γ２,ｉを生成し、以下を計算して公開する。
【０３１６】
2020056840.tif 000053
【０３１７】
Ｓ４８８で、サーバＳｉは、以下を計算する。
【０３１８】
2020056840.tif 000054
【０３１９】
Ｓ４９０で、サーバＳｉは、以下を計算して復元し、α２（ａ＋ａ１）,β２（ｂ＋ｂ１）,α２（ａ＋ａ１）を公開する。
【０３２０】
2020056840.tif 000055
【０３２１】
以上説明したように、本発明の第４実施形態の手法を用いて秘密情報を分散することにより、秘密情報に０を含んでいても、ユーザの結託を含む不正を防止することができる。
【０３２２】
［第５実施形態］
第５実施形態は、秘密情報に０を含む場合の演算結果の検証法を示すものである。
【０３２３】
まず第５実施形態の手法の前提について説明する。第３、第４実施形態では秘密情報に乱数をかけたα０ａを公開するため、秘密情報が０、例えばａ＝０の場合α０ａ＝０となり、秘密情報が漏洩する。それに対して、第２実施形態では秘密情報に乱数をかけた値を生成しないため、秘密情報が０であっても漏洩しない。よって、その原理を生かして秘密情報に０を含む場合の検証を行う。
【０３２４】
また、本実施形態の分散では簡単のため、第３実施形態の分散と同様にユーザからの攻撃がない場合を考える。ユーザからの攻撃に対しても安全性を確保したい場合、下記におけるａ１などの乱数を、第４実施形態の変形例のように入力者が直接生成せず、変換用乱数組を用いて生成すれば良い。この場合、入力装置側では生成されるα２（ａ＋ａ１）のα２もａ１も知ることができず、不正防止が可能となる。また、ｂ１,ｃ１,ａ２,ｂ２,ｃ２についても同様である。また、本実施形態の秘匿積和演算では、サーバＳｉは変換用乱数組として（［μｈ］ｉ,μｈ,ｉ）（ｈ＝１,…,必要個数）を持つものとする。
【０３２５】
第５実施形態の構成は上記図１１の第３実施形態と同様の構成をとることができ、秘密分散システム５１０において、入力装置３１２を入力装置５１２に、復元装置３１４を復元装置５１４に、サーバ３１６をサーバ５１６に置き換えた構成とすればよい。なお、復元装置５１４が、第２排除部と、第２判定部とを含む検証復元装置の一例である。
【０３２６】
次に、図１９を参照して、本実施形態に係る復元装置５１４のハードウェア構成を説明する。
【０３２７】
図１９に示すように、復元装置５１４は、ＣＰＵ５４０、一時記憶領域としてのメモリ５４１、不揮発性の記憶部５４２を含む。また、復元装置５１４は、表示装置５４３、入力Ｉ／Ｆ５４４、及びネットワークＮに接続されるネットワークＩ／Ｆ５４５を含む。ＣＰＵ５４０、メモリ５４１、記憶部５４２、表示装置５４３、入力Ｉ／Ｆ５４４、及びネットワークＩ／Ｆ５４５は、バス５４６に接続される。
【０３２８】
記憶部５４２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部５４２には、復号プログラム５４８が記憶される。復号プログラム５４８は、第２排除プロセス５４８ａと、第２判定プロセス５４８ｂと、復元プロセス５４８ｃとを含む。ＣＰＵ５４０は、記憶部５４２から復号プログラム５４８を読み出してからメモリ５４１に展開し、展開した復号プログラム５４８を実行する。ＣＰＵ５４０が復号プログラム５４８の第２排除プロセス５４８ａを実行することで、開示の技術の第２排除部として動作する。ＣＰＵ５４０が復号プログラム５４８の第２判定プロセス５４８ｂを実行することで、開示の技術の第２判定部として動作する。ＣＰＵ５４０が復号プログラム５４８の復元プロセス５４８ｃを実行することで、開示の技術の復元部として動作する。
【０３２９】
なお、他の各装置のハードウェア構成は第３実施形態と同様のハードウェア構成をとることができるため、詳細な説明を省略する。
【０３３０】
次に、図２０〜２３を参照して、本実施形態に係る秘密分散システム５１０の作用を説明する。
【０３３１】
＜分散５＞
まず、秘密情報を各サーバに分散する処理について説明する。図２０は、秘密分散システム５１０における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置５１２Ａ〜Ｃが持つ秘密情報をサーバ５１６に分散する。以下において、サーバ５１６は、分散の処理シーケンスの各処理に応じてｎ台の全てのサーバである全サーバＳ、及びサーバＳｉのいずれかが対象であるものとして説明する。
【０３３２】
Ｓ５１０で、入力装置５１２Ａは、乱数αｉ,０,…,αｉ,ｋ−１（ｉ＝１,..,４）を生成する。
【０３３３】
Ｓ５１２で、入力装置５１２Ａは、乱数αｉ＝Πｊ＝０ｋ−１αｉ,ｊを計算する。
【０３３４】
Ｓ５１４で、入力装置５１２Ａは、乱数ａ１,ａ２を生成し、秘密情報ａに対して以下を計算して計算結果を公開する。また、入力装置５１２Ａは、ａ１,ａ２に対するハッシュ値ｈａ１,ｈａ２を公開する。
【０３３５】
2020056840.tif 000056
【０３３６】
Ｓ５１６で、入力装置５１２Ａは、α０,ｊ,..,α４,ｊをサーバＳｉに送信する。
【０３３７】
Ｓ５１８で、入力装置５１２Ｂは、乱数βｉ,０,…,βｉ,ｋ−１（ｉ＝１,..,４）を生成する。
【０３３８】
Ｓ５２０で、入力装置５１２Ｂは、乱数βｉ＝Πｊ＝０ｋ−１βｉ，ｊを計算する。
【０３３９】
Ｓ５２２で、入力装置５１２Ｂは、乱数ｂ１,ｂ２を生成し、秘密情報ｂに対して以下を計算して計算結果を公開する。また、入力装置５１２Ｂは、ｂ１,ｂ２に対するハッシュ値ｈｂ１,ｈｂ２を公開する。
【０３４０】
2020056840.tif 000057
【０３４１】
Ｓ５２４で、入力装置５１２Ｂは、β０,ｊ,..,β４,ｊをサーバＳｉに送信する。
【０３４２】
Ｓ５２６で、入力装置５１２Ｃは、乱数γｉ,０,…,γｉ,ｋ−１（ｉ＝１,..,４）を生成する。
【０３４３】
Ｓ５２８で、入力装置５１２Ｃは、乱数γｉ＝Πｊ＝０ｋ−１γｉ，ｊを計算する。
【０３４４】
Ｓ５３０で、入力装置５１２Ｃは、乱数ｃ１,ｃ２を生成し、秘密情報ｃに対して以下を計算して計算結果を公開する。また、入力装置５１２Ｃは、ｃ１,ｃ２に対するハッシュ値ｈｃ１,ｈｃ２を公開する。
【０３４５】
2020056840.tif 000058
【０３４６】
Ｓ５３２で、入力装置５１２Ｃは、γ０,ｊ,..,γ４,ｊをサーバＳｉに送信する。
【０３４７】
以上の分散の処理シーケンスにより、サーバＳｉは、以下を持つことになる。
【０３４８】
2020056840.tif 000059
【０３４９】
なお、入力装置５１２Ａ、入力装置５１２Ｂ、及び入力装置５１２Ｃは、ａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２を秘密分散してもよい。
【０３５０】
＜秘匿積和演算５＞
次に秘匿積和演算する処理について説明する。図２１は、秘密分散システム５１０における、秘匿積和演算の処理シーケンスを説明したものである。図２１では、説明の便宜のため、サーバ５１６のうち、サーバＳｉまたは全サーバＳおいて秘匿積和演算の処理シーケンスが行われるものとして説明する。
【０３５１】
Ｓ５４０で、サーバＳｉは、乱数δ１,ｉ,δ２,ｉ,δ３,ｉ,δ４,ｉを生成する。
【０３５２】
Ｓ５４２で、サーバＳｉは、生成した乱数δ１,ｉ,δ２,ｉ,δ３,ｉ,δ４,ｉを用いて、以下を計算して計算結果を公開する。ただし、０となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。
【０３５３】
2020056840.tif 000060
【０３５４】
Ｓ５４４で、全サーバは、以下を計算する。
【０３５５】
2020056840.tif 000061
【０３５６】
Ｓ５４６で、サーバＳｉは、以下を計算して復元し、復元したδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１），δ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝,δ３（ｃ２−ａ２ｂ２）を公開する。
【０３５７】
2020056840.tif 000062
【０３５８】
Ｓ５４８は、演算を継続する場合の処理である。Ｓ５４８で、サーバＳｉは、δ１（ｃ１−ａ１ｂ１）,δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ３（ｃ２−ａ２ｂ２）,δ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝が０でなければ、新たなα１ａ１,α２（ａ＋ａ１）,α３ａ２,α４（ａ＋ａ２）に設定し、δ１,ｉ,δ２,ｉ,δ３,ｉ,δ４,ｉを新たなα１,ｉ,α２,ｉ,α３,ｉ,α４,ｉに設定してＳ５４０に戻る。
【０３５９】
＜補正処理５＞
次に、Ｓ５４６の計算結果が０であった場合の補正処理について説明する。上述した図２１の秘匿積和演算の処理シーケンスにおいて、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ１（ｃ１−ａ１ｂ１）の少なくとも１つが０の場合、以下の補正処理を行う。図２２は、秘密分散システム５１０における補正処理の処理シーケンスを説明したものである。補正処理の処理シーケンスは、サーバＳｉで行われるものとして説明する。また、δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝＝０の場合を第１のケース、δ１（ｃ１−ａ１ｂ１）＝０の場合を第２のケースとして、第１のケース及び第２のケースのいずれか少なくとも一つに当てはまる場合の計算例を説明する。
【０３６０】
Ｓ５６０で、サーバＳｉは、新たな乱数τ０,ｉとｗｉを生成し、公開する。
【０３６１】
Ｓ５６２で、サーバＳｉは、τ０ｗ＝Πτ０,ｉｗｉを計算する。また、サーバＳｉは、ｗｉのハッシュ値を公開する。
【０３６２】
Ｓ５６４で、サーバＳｉは、乱数τ１,i,τ２,iを生成して、生成した乱数を用いて以下を計算する。第１のケースの場合、
2020056840.tif 000063
を計算する。第２のケースの場合、
2020056840.tif 000064
を計算する。
【０３６３】
Ｓ５６６で、サーバＳｉは、Ｓ５６４の計算結果を公開する。ただし、０となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。
【０３６４】
Ｓ５６８で、サーバＳｉは公開された計算結果を用いて、ｉについて乗算し以下を計算する。第１のケースの場合、
2020056840.tif 000065
。
第２のケースの場合、
2020056840.tif 000066
。
【０３６５】
Ｓ５７０で、サーバＳｉは、以下の計算を行い、新たな値の設定を行う。第１のケースの場合、
2020056840.tif 000067
と考えて、τ０ｗを新たなτ２｛（ａｂ＋ｃ）＋（ｃ′１−ａ１ｂ１）｝とする。また、サーバＳｉは以下を計算して復元し公開し、それらを新たなα１ａ１,α２（ａ＋ａ１）とし、τ１,ｉ,τ２,ｉ＝τ０,ｉを新たなα１,ｉ,α２,ｉとして上記図２１の秘匿積和演算の処理シーケンスのＳ５４０に戻る。
【０３６６】
2020056840.tif 000068
【０３６７】
第２のケースの場合、
2020056840.tif 000069
と考えて、τ０ｗを新たなτ１（ｃ´１−ａ１ｂ１）とする。また、サーバＳｉは以下を計算して復元し公開し、それらを新たなα１ａ１,α２（ａ＋ａ１）とし、τ１,ｉ＝τ０,ｉ,τ２,ｉを新たなα１,ｉ,α２,ｉとして上記図２１の秘匿積和演算の処理シーケンスのＳ５４０に戻る。ただし、ｃ´１＝ｃ１＋ｗとする。
【０３６８】
2020056840.tif 000070
【０３６９】
以上が補正処理の処理シーケンスである。なお、δ３（ｃ２−ａ２ｂ２）,δ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝が０の場合も同様である。
【０３７０】
＜検証・復元５＞
次に、検証処理について説明する。図２３は、秘密分散システム５１０における検証の処理シーケンスを説明したものである。検証の処理シーケンスにおいて、入力装置５１２Ａ、入力装置５１２Ｂ、及び入力装置５１２Ｃは、ａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２を公開しているものとする。また、補正処理を行っている場合、ｗｉを生成したサーバはその値とハッシュ値を公開する。以降、ｗｉについてはｃ´１＝ｃ１＋ｗよりｃ´１に含まれるが、簡単のためｃ´１もｃ１として表現する。
【０３７１】
Ｓ５８０で、復元装置５１４は、サーバＳｉからδ２,ｉ,δ４,ｉを収集する。
【０３７２】
Ｓ５８２で、復元装置５１４は、収集したδ２,ｉ,δ４,ｉの積δ２,δ４を計算し、積δ２,δ４を用いて以下を計算して公開する。
【０３７３】
2020056840.tif 000071
【０３７４】
なお、Ｓ５８２は、復元装置５１４における、復号プログラム５４８の第２排除プロセス５４８ａに対応する。復元装置５１４のＣＰＵ５４０が、第２排除プロセス５４８ａを実行することで、開示の技術における第２排除部の処理を行う。上記の計算が、複数の第３の値δ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝,δ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝から各々の第４の乱数δ２,δ４に相当する値を排除することに対応する。
【０３７５】
Ｓ５８４で、復元装置５１４は、入力装置５１２Ａ、入力装置５１２Ｂ、及び入力装置５１２Ｃが公開しているａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２及びそのハッシュ値を収集する。
【０３７６】
Ｓ５８６で、復元装置５１４は、公開されているａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２と、そのハッシュ値が一致するかを検証し、ハッシュ値が正しければＳ５８８へ移行し、正しくなければＳ５９４へ移行して不正検出とする。なお、途中演算結果が０になっている場合、復元装置５１４は新たに定めたｗｉを集めて公開し、そのハッシュ値を検証する。
【０３７７】
Ｓ５８８で、復元装置５１４は、公開されているａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２を用いて（ｃ１−ａ１ｂ１）−（ｃ２−ａ２ｂ２）を計算する。なお、途中演算結果が０になり補正した場合、ｃ１,ｃ２はｃ´１,ｃ´２となる。
【０３７８】
Ｓ５９０で、復元装置５１４は、公開されているａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２から計算された（ｃ１−ａ１ｂ１）−（ｃ２−ａ２ｂ２）と、Ｓ５８２で復元値（つまり積δ２,δ４）から計算された（ｃ１−ａ１ｂ１）−（ｃ２−ａ２ｂ２）が等しいか検証し、計算結果が正しければＳ５９０へ移行し、正しくなければＳ５９４へ移行して不正検出とする。
【０３７９】
なお、Ｓ５９０は、復元装置５１４における、復号プログラム５４８の第２判定プロセス５４８ｂに対応する。復元装置５１４のＣＰＵ５４０が、第２判定プロセス５４８ｂを実行することで、開示の技術における第２判定部の処理を行う。また、δ１（ｃ１−ａ１ｂ１）＝０で補正した場合におけるｃ´１＝ｃ１＋ｗが第６の乱数に対応する。Ｓ５８２の計算結果である（ｃ１−ａ１ｂ１）−（ｃ２−ａ２ｂ２）が第１の乱数同士の演算結果に対応する。上述したようにここでのｃ１,ｃ２はｃ´１,ｃ´２となる。
【０３８０】
Ｓ５９２で、復元装置５１４は、検証結果が正しい場合、Ｓ５８２で用いられたδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝／δ２から公開値による（ｃ１−ａ１ｂ１）を差し引いた値をａｂ＋ｃとする。
【０３８１】
Ｓ５９４で、検証結果が不正検出であるものとする。
【０３８２】
以上が、検証の処理シーケンスである。なお、ａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２が秘密分散されている場合、Ｓ５８６に対応する処理として、各サーバでａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２の分散値を公開して、復元装置５１４でａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２を復元してもよい。
【０３８３】
また、演算が繰り返されている場合、Ｓ５８２において乱数による最終的な演算結果を計算し、Ｓ５８４で全乱数を収集して、その乱数を用いて同様の演算を構成し、Ｓ５８２で計算した結果とＳ５８８で計算した結果が一致するかを検証する。
【０３８４】
また、上記においてδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝とδ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝は簡単のため同形式のものを用いたが、どちらも（ａｂ＋ｃ）を含んでいれば、異なる形式の演算であっても、その差分が乱数のみになれば問題ない。
【０３８５】
また、第２実施形態と同様の変形を行えば、秘匿減算及び秘匿除算も実現できる。また、本実施の形態の安全性は第３実施形態と同様に秘密情報及び乱数を知らない攻撃者に対しては安全であることが言える。ただし、これも第３実施形態と同様に例えばユーザＣはｃ,ｃ１,ｃ２を知るのでその間の関係を調整することによって不正ができる。よって、乱数ａ１,ｂ１,ｃ１,ａ２,ｂ２,ｃ２は入力装置の入力者が生成せず、第４実施形態に示したように分散４または分散４’のようにして生成すればよい。
【０３８６】
また、補正処理５においてδ２｛（ａｂ＋ｃ）＋（ｃ１−ａ１ｂ１）｝やδ４｛（ａｂ＋ｃ）＋（ｃ２−ａ２ｂ２）｝が補正されたとしても安全であることが言える。
【０３８７】
以上により、問題点１〜３の全てを解決できる。
【０３８８】
また、復元装置５１４は、第２排除部から得られる値から第１の秘密情報同士の演算結果を得る演算結果を得る復元部を含む秘匿演算装置として機能する。復元装置５１４は、上記、本実施形態の各処理シーケンスを経て、復元プロセス５４８ｃの実行によって、Ｓ５９２から得られる値を取得し、第１の秘密情報同士の演算結果（ａｂ＋ｃ）を得る。
【０３８９】
以上説明したように、本発明の第５実施形態の手法を用いて秘密情報を分散することにより、秘密情報に０を含んでいても、ユーザの結託を含む不正を防止することができる。また、また、第５実施形態の手法を用いて秘匿積和演算を行うことにより、秘密情報に０を含んでいても、効率よく秘匿演算を繰り返すことができる。また、第５実施形態の手法を用いて秘匿積和演算を検証することにより、秘匿積和演算の不正を検出することができる。
【０３９０】
［第６実施形態］
第６実施形態は、第１〜第５実施形態で説明した提案手法を変形してブロックチェーンに応用する場合を示す。すなわち、値を登録する入力者が操作する入力装置と、その値を検証してブロックチェーンに公開する検証者が操作する検証装置と、ブロックチェーン装置と、ブロックチェーンに公開された値を確認する復元者が操作する復元装置からなるシステムを考える。入力装置は検証装置には登録する値を知らせるが、復元装置に対しては登録した値を秘匿したいものとする。ただし、ブロックチェーンでは公開性、及び検証性が重要なので、秘匿した登録値から合計値や各種統計値などの演算（以降、検証用演算と呼ぶ）を復元装置が実行でき、その演算結果を検証できるようにする。すなわち、登録値は１台のブロックチェーン装置に秘匿されて公開されるが、その登録値を用いた検証用演算は誰でも実行でき、その合計値や統計値などを知ることができ、かつその演算結果が正しいことを検証できることが大きな特徴である。
【０３９１】
図２４を参照して、本実施形態に係る秘密分散システム６１０の構成を説明する。図２４に示すように、秘密分散システム６１０は、入力装置６、復元装置６１４、ブロックチェーン装置６１６、及び検証装置６１８を含む。各装置はネットワークＮに接続され、互いに通信可能とされる。なお、ブロックチェーン装置６１６が演算装置の一例であり、復元装置６１４が検証部を含む検証復元装置の一例であり、秘密分散システム６１０が秘匿演算検証復元システムの一例である。
【０３９２】
以降において、ブロックチェーン装置６１６をＳ１、登録値を秘密情報と呼び、ｋ＝２の場合で説明する（ｋは任意に設定できるが、１台のサーバで演算を行う場合、ｋ＝２が最も効率的）。また、簡単のため実行する検証用演算を積和演算とし、登録値には０を含まず、演算結果も０を含まないとする。また以下では、秘密情報に対する演算と乱数に対する演算を同じ処理とするためにα２（ａ＋ａ１）,α１ａ１,α０ａを用いる場合を示す。以下の例では入力者がａ，ｂ，ｃの値を発生毎に検証者に送り、検証者がそれらを確認した後、秘匿して公開する場合を示す。
【０３９３】
次に、図２５を参照して、本実施形態に係る復元装置６１４のハードウェア構成を説明する。
【０３９４】
図２５に示すように、復元装置６１４は、ＣＰＵ６４０、一時記憶領域としてのメモリ６４１、不揮発性の記憶部６４２を含む。また、復元装置６１４は、表示装置６４３、入力Ｉ／Ｆ６４４、及びネットワークＮに接続されるネットワークＩ／Ｆ６４５を含む。ＣＰＵ６４０、メモリ６４１、記憶部６４２、表示装置６４３、入力Ｉ／Ｆ６４４、及びネットワークＩ／Ｆ６４５は、バス６４６に接続される。
【０３９５】
記憶部６４２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部６４２には、検証復元プログラム６４８が記憶される。ＣＰＵ６４０は、記憶部６４２から検証復元プログラム６４８を読み出してからメモリ６４１に展開し、展開した検証復元プログラム６４８を実行する。ＣＰＵ６４０が検証復元プログラム６４８を実行することで、開示の技術の検証部として動作する。
【０３９６】
次に、図２６を参照して、本実施形態に係るブロックチェーン装置６１６のハードウェア構成を説明する。
【０３９７】
図２６に示すように、ブロックチェーン装置６１６は、ＣＰＵ６５０、一時記憶領域としてのメモリ６５１、不揮発性の記憶部６５２を含む。また、ブロックチェーン装置６１６は、表示装置６５３、入力Ｉ／Ｆ６５４、及びネットワークＮに接続されるネットワークＩ／Ｆ６５５を含む。ＣＰＵ６５０、メモリ６５１、記憶部６５２、表示装置６５３、入力Ｉ／Ｆ６５４、及びネットワークＩ／Ｆ６５５は、バス６５６に接続される。
【０３９８】
記憶部６５２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部６５２には、演算プログラム６５８が記憶される。ＣＰＵ６５０は、記憶部６５２から演算プログラム６５８を読み出してからメモリ６５１に展開し、展開した演算プログラム６５８を実行する。ＣＰＵ６５０が演算プログラム６５８を実行することで、開示の技術の演算部として動作する。
【０３９９】
次に、図２７を参照して、本実施形態に係る検証装置６１８のハードウェア構成を説明する。
【０４００】
図２７に示すように、検証装置６１８は、ＣＰＵ６６０、一時記憶領域としてのメモリ６６１、不揮発性の記憶部６６２を含む。また、検証装置６１８は、表示装置６６３、入力Ｉ／Ｆ６６４、及びネットワークＮに接続されるネットワークＩ／Ｆ６６５を含む。ＣＰＵ６６０、メモリ６６１、記憶部６６２、表示装置６６３、入力Ｉ／Ｆ６６４、及びネットワークＩ／Ｆ６６５は、バス６６６に接続される。
【０４０１】
記憶部６６２は、ＨＤＤ、ＳＳＤ、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部６６２には、検証プログラム６６８が記憶される。ＣＰＵ６６０は、記憶部６６２から検証プログラム６６８を読み出してからメモリ６６１に展開し、展開した検証プログラム６６８を実行する。
【０４０２】
なお、入力装置６１２は検証装置６１８と同様の構成をとることができるため詳細な説明を省略する。
【０４０３】
次に、図２８、図２９を参照して、本実施形態に係る秘密分散システム６１０の作用を説明する。
【０４０４】
＜分散６＝データ登録＞
図２８は、秘密分散システム６１０における分散（データ登録）、秘匿積和演算（検証用演算）の処理シーケンスを説明したものである。また、図２９は、検証・復元処理（データ検証）の処理シーケンスを説明したものである。
【０４０５】
Ｓ６１０で、入力装置６１２は、各秘密情報ａ,ｂ,ｃが発生する毎に安全な通信路を用いて検証装置６１８に送信する。
【０４０６】
検証装置６１８は、受信したａ,ｂ,ｃを確認し、問題なければ以下を行う。
【０４０７】
Ｓ６１２で、検証装置６１８は、秘密情報ａに対して３個の乱数α０,α１,α２を生成する。また、乱数ａ１を生成し、以下の値を計算する。
【０４０８】
2020056840.tif 000072
【０４０９】
Ｓ６１４で、検証装置６１８は、Ｓ６１２の計算結果、及び、ａ１に対するハッシュ値ｈａ１をブロックチェーン装置Ｓ１に送信する。
【０４１０】
Ｓ６１６で、検証装置６１８は、秘密情報ｂに対して３個の乱数β０,β１,β２を生成する。また、乱数ｂ１を生成し、以下の値を計算する。
【０４１１】
2020056840.tif 000073
【０４１２】
Ｓ６１８で、検証装置６１８は、Ｓ６１６の計算結果、及び、ｂ１に対するハッシュ値ｈｂ１をブロックチェーン装置Ｓ１に送信する。
【０４１３】
Ｓ６２０で、検証装置６１８は、秘密情報ｃに対して３個の乱数γ０,γ１,γ２を生成する。また、乱数ｃ１を生成し、以下の値を計算する。
【０４１４】
2020056840.tif 000074
【０４１５】
Ｓ６２２で、検証装置６１８は、Ｓ６２０の計算結果、及び、ｃ１に対するハッシュ値ｈｃ１をブロックチェーン装置Ｓ１に送信する。
【０４１６】
Ｓ６２４で、検証装置６１８は、変換用乱数組（［εｉ］０,εｉ,０）と（［εｉ］１,εｉ,１）（ｉ＝１,…,必要個数）を生成する。
【０４１７】
Ｓ６２６で、検証装置６１８は、（［εｉ］１,εｉ,１）に乱数μをかけて（［εｉ］０,εｉ,０）,（μ［εｉ］１,εｉ,１）をブロックチェーン装置Ｓ１に送信する。
【０４１８】
Ｓ６２８で、検証装置６１８は、乱数δ０,δ１,δ２を生成し、以下をブロックチェーン装置Ｓ１に送信する。
【０４１９】
2020056840.tif 000075
【０４２０】
Ｓ６３０で、ブロックチェーン装置Ｓ１は、検証装置６１８から送られてきた値を登録値として公開する。
【０４２１】
以上が分散の処理シーケンスである。
【０４２２】
＜秘匿積和演算６＝検証用演算＞
Ｓ６３２で、ブロックチェーン装置Ｓ１は、以下を計算し計算結果を検証装置６１８に送信する。ただし、μ２＝μδ２,μ１＝μδ１,μ０＝μδ０とする。
【０４２３】
2020056840.tif 000076
【０４２４】
なお、Ｓ６３２は、ブロックチェーン装置Ｓｉにおける、演算プログラム６５８の処理に対応する。ブロックチェーン装置ＳｉのＣＰＵ６５０が、演算プログラム６５８を実行することで、開示の技術における演算部の処理を行う。秘匿された登録値であるδ２／α２β２ε１等を用いて、登録値による検証用演算、つまり上記計算を行う。
【０４２５】
以上が秘匿積和演算の処理シーケンスである。
【０４２６】
＜検証・復元６＝データ検証＞
図２９は、秘密分散システム６１０における検証の処理シーケンスを説明したものである。秘密分散システム６１０は、演算を終了し検証を行う場合、以下の検証の処理シーケンスを実行する。
【０４２７】
Ｓ６５０で、検証装置６１８は、δ２｛（ａｂ＋ｃ）＋（ａ１ｂ１＋ｃ１）｝,δ０（ａｂ＋ｃ）とａ１,ｂ１,ｃ１,δ２,δ０を公開する。
【０４２８】
Ｓ６５２で、復元装置６１４は、以下を計算する。
【０４２９】
2020056840.tif 000077
【０４３０】
Ｓ６５４で、復元装置６１４は、ａ１,ｂ１,ｃ１がそのハッシュ値と一致するか検証し、ハッシュ値が正しければＳ６５６へ移行し、正しくなければＳ６６２へ移行して不正とする。
【０４３１】
Ｓ６５６で、復元装置６１４は、公開されているａ１,ｂ１,ｃ１を用いてａ１ｂ１＋ｃ１を計算する。
【０４３２】
Ｓ６５８で、復元装置６１４は、Ｓ６５６で計算されたａ１ｂ１＋ｃ１とＳ６５２で計算されたａ１ｂ１＋ｃ１が等しいか検証し、計算結果が等しく、正しければＳ６６０へ移行し、正しくなければＳ６６２へ移行して不正とする。
【０４３３】
なお、Ｓ６５８は、復元装置６１４における、検証復元プログラム６４８の処理に対応する。サーバＳｉのＣＰＵ６４０が、検証復元プログラム６４８を実行することで、開示の技術における検証部の処理を行う。
【０４３４】
Ｓ６６０で、復元装置６１４は、（ａｂ＋ｃ＝δ０（ａｂ＋ｃ））／δ０を確認値とする。
【０４３５】
Ｓ６６２で、検証結果が不正であるものとする。
【０４３６】
以上が検証の処理シーケンスである。
【０４３７】
上記において、検証用演算を積和演算としたが、積和演算はｂ＝１とすれば加算となり、ｃ＝０とすれば乗算となる。また、第２の実施の形態に示したように減算及び除算も可能である。さらに、積和演算の組み合わせにより任意の四則演算が構成できるので、任意の検証用演算が可能である。
【０４３８】
また、本実施形態の分散（データ登録）の時点で登録値は秘匿されて公開されるが、復元者は秘密情報に関して何の情報も得ることができない。また、秘匿積和演算（検証用演算）においても乱数δ２,δ１,δ０が秘匿されているので、演算は実行できるが秘密情報及び演算結果について何の情報も得ることはできない。また、δ０（ａｂ＋ｃ）が０になれば秘密情報が漏洩するが、秘密情報による演算結果に０を含まないとするので問題ない。演算結果に０を含む場合は、第５実施形態の秘匿計算を採用すればよい。よって、本実施形態の補正処理におけるδ２｛（ａｂ＋ｃ）＋（ａ１ｂ１＋ｃ１）｝,δ１（ａ１ｂ１＋ｃ１）の更新についても情報は得られない。最後に、本実施形態の検証（データ検証）において検証装置６１８により乱数ａ１,ｂ１,ｃ１,δ２,δ０が公開されることにより、復元された演算結果の正当性を検証できる。
【０４３９】
本実施の形態の特徴は誰でも秘匿計算及びその検証処理が実行できる点である。すなわち、前実施形態までは秘匿積和演算に参加できるメンバーは分散時に種々の値を配布されたｋ台のサーバに限定され、それ以外のメンバーは演算結果の正しさを確認できるが、自ら検証処理を行えなかった。本実施の形態によりｋ台のサーバに秘匿演算を依頼しなくても、全ての値が公開されるため誰でも検証処理できる。また、最終結果に用いられた乱数が公開されることにより、最終結果は知ることができるが、途中結果を復元するためのδ２,δ０が公開されないため、入力値及び途中の演算結果に関する情報は得られないというものである。
【０４４０】
ただし、検証者は全入力を知っており、乱数も自ら設定するため、不正することが可能であるが、検証者が信頼できるとする場合はこのままで問題はない。信頼できるとしない場合は、第４実施形態と同様に乱数を検証者だけが生成しないようにすればよい。例えば、分散（データ登録）のＳ６１２〜６２２の処理とＳ６２８の処理の代わりに以下の生成処理を入力装置６１２が行い検証装置６１８に送信する。
【０４４１】
2020056840.tif 000078
【０４４２】
検証装置６１８は受信した値を秘密分散して、片側の分散値にμをかけた以下の値をブロックチェーン装置Ｓ１に送る。
【０４４３】
2020056840.tif 000079
【０４４４】
このとき、検証装置６１８ではＳ６１０で送られたａ,ｂ,ｃの値からα０,β０,γ０を知ることができるが、それ以上の情報を知ることができない。そのため、乱数の演算結果の差分が０となるように公開値を調整できない。また、入力装置６１２が偽の値を送っている場合、検証装置６１８はＳ６１０によって知る秘密情報による検証結果の正当性をＳ６５４において直接確認できる。また、入力装置６１２が送る値に入力装置６１２のデジタル署名をつけて送らせ、それを検証した後上記処理を行えば、入力装置６１２が偽の値を送っていることを証明できる。またこれに対して検証装置のデジタル署名を入力装置が得れば、検証装置６１８による偽の値の登録を防ぐために利用できる。
【０４４５】
また、第４実施形態に示したように入力の乱数ａ１,ｂ１,ｃ１を他者と協力して生成してもよい。例えば、入力装置と検証装置、または検証装置と復元装置などの組合せで、入力装置または検証装置が設定したａ１をその生成者が知らないａ"１＝ａ１＋ａ′１に変更してもよい。
【０４４６】
また、上記分散（データ登録）ではα２（ａ＋ａ１）,α１ａ１,α０ａの３つの入力を生成したが、乱数の演算を秘密情報の演算と同じ形にしなくてよい場合は、第３実施形態のようにα２（ａ＋ａ１）,α０ａまたは第５の実施の形態のように２組のα２（ａ＋ａ１）,α１ａ１として、各々同じ形式で更新して行ってもよい。
【０４４７】
以上説明したように、本発明の第６実施形態の手法を用いて秘密情報を分散することにより、ブロックチェーンのような公開性が重視される応用に対しても、上述した第１〜第５実施形態と同様の秘匿計算を適用することができる。
【０４４８】
なお、上記各実施形態でＣＰＵがソフトウェア（プログラム）を実行することにより実行した各種処理を、ＣＰＵ以外の各種のプロセッサが実行してもよい。この場合のプロセッサとしては、ＦＰＧＡ（Field-Programmable Gate Array）等の製造後に回路構成を変更可能なＰＬＤ（Programmable Logic Device）、及びＡＳＩＣ（Application Specific Integrated Circuit）等の特定の処理を実行させるために専用に設計された回路構成を有するプロセッサである専用電気回路等が例示される。また、各種処理を、これらの各種のプロセッサのうちの１つで実行してもよいし、同種又は異種の２つ以上のプロセッサの組み合わせ（例えば、複数のＦＰＧＡ、及びＣＰＵとＦＰＧＡとの組み合わせ等）で実行してもよい。また、これらの各種のプロセッサのハードウェア的な構造は、より具体的には、半導体素子等の回路素子を組み合わせた電気回路である。
【０４４９】
また、上記各実施形態では、各種プログラムが記憶部に予め記憶（インストール）されている態様を説明したが、これに限定されない。各種プログラムは、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）、及びＵＳＢ（Universal Serial Bus）メモリ等の記録媒体に記録された形態で提供されてもよい。また、各種プログラムは、ネットワークを介して外部装置からダウンロードされる形態としてもよい。
【符号の説明】
【０４５０】
１０、２１０、３１０、４１０、５１０、６１０     秘密分散システム
１２、２１２、３１２、４１２、５１２、６１２     入力装置
１４、３１４、４１４、５１４、６１４      復元装置
１６、２１６、３１６、４１６、５１６      サーバ
６１６ ブロックチェーン装置
６１８ 検証装置
【図１】
2020056840.tif 000080
【図２】
2020056840.tif 000081
【図３】
2020056840.tif 000082
【図４】
2020056840.tif 000083
【図５】
2020056840.tif 000084
【図６】
2020056840.tif 000085
【図７】
2020056840.tif 000086
【図８】
2020056840.tif 000087
【図９】
2020056840.tif 000088
【図１０】
2020056840.tif 000089
【図１１】
2020056840.tif 000090
【図１２】
2020056840.tif 000091
【図１３】
2020056840.tif 000092
【図１４】
2020056840.tif 000093
【図１５】
2020056840.tif 000094
【図１６】
2020056840.tif 000095
【図１７】
2020056840.tif 000096
【図１８】
2020056840.tif 000097
【図１９】
2020056840.tif 000098
【図２０】
2020056840.tif 000099
【図２１】
2020056840.tif 000100
【図２２】
2020056840.tif 000101
【図２３】
2020056840.tif 000102
【図２４】
2020056840.tif 000103
【図２５】
2020056840.tif 000104
【図２６】
2020056840.tif 000105
【図２７】
2020056840.tif 000106
【図２８】
2020056840.tif 000107
【図２９】
2020056840.tif 000108