TOP > 国内特許検索 > 分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラム > 明細書

明細書 :分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2020-056840 (P2020-056840A)
公開日 令和2年4月9日(2020.4.9)
発明の名称または考案の名称 分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラム
国際特許分類 G09C   1/00        (2006.01)
G06F  21/62        (2013.01)
FI G09C 1/00 650Z
G06F 21/62 318
請求項の数または発明の数 19
出願形態 OL
全頁数 56
出願番号 特願2018-185931 (P2018-185931)
出願日 平成30年9月28日(2018.9.28)
発明者または考案者 【氏名】岩村 惠市
出願人 【識別番号】000125370
【氏名又は名称】学校法人東京理科大学
個別代理人の代理人 【識別番号】100079049、【弁理士】、【氏名又は名称】中島 淳
【識別番号】100084995、【弁理士】、【氏名又は名称】加藤 和詳
【識別番号】100099025、【弁理士】、【氏名又は名称】福田 浩志
審査請求 未請求
テーマコード 5J104
Fターム 5J104AA12
5J104AA16
5J104AA18
5J104EA02
5J104EA13
5J104PA07
5J104PA14
要約 【課題】秘密情報に0を含んでいても、効率よく秘匿演算を繰り返すことを可能にする。
【解決手段】第1生成部は、第1の秘密情報に第1の乱数及び第2の乱数を作用させた第1の値を生成し、前記第1の乱数及び前記第1の秘密情報の少なくとも一方に第3の乱数を作用させた第2の値を生成する。
【選択図】図1
特許請求の範囲 【請求項1】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
第1の秘密情報に第1の乱数及び第2の乱数を作用させた第1の値を生成し、
前記第1の乱数及び前記第1の秘密情報の少なくとも一方に第3の乱数を作用させた第2の値を生成する第1生成部
を備えた分散装置。
【請求項2】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
第1の秘密情報に第1の乱数及び第2の乱数を作用させた複数の第1の値と、前記第1の乱数又は前記第1の秘密情報に第3の乱数を作用させた複数の第2の値とを用いて、
前記複数の第1の秘密情報同士の演算結果に前記複数の第1の乱数同士の演算結果、及び第4の乱数を作用させた第3の値を生成し、
前記複数の第1の乱数同士又は秘密情報同士の演算結果に第5の乱数を作用させた第4の値を生成する第2生成部
を備えた秘匿演算装置。
【請求項3】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
請求項2に記載の第2生成部によって得られた第3の値及び第4の値の少なくとも一方が0である場合に第6の乱数を生成する第3生成部と、
前記第6の乱数を秘匿加算する加算部と、
を更に備えた秘匿演算装置。
【請求項4】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
請求項2又は請求項3に記載の秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第1排除部と、
前記第1排除部による排除によって得られた第1の乱数同士の演算結果が正しいか否かを判定する第1判定部と、
を備えた検証復元装置。
【請求項5】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
請求項2又は請求項3に記載の秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第2排除部と、
前記第2排除部による排除によって得られた第1の乱数同士の演算結果であって、前記第3の値または第4の値が0の場合に第6の乱数を含む第1の乱数同士の演算結果が正しいか否かを判定する第2判定部と、
を備えた検証復元装置。
【請求項6】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
請求項4に記載の第1排除部、もしくは請求項5に記載の第2排除部から得られる値、又は請求項2に記載の第4の値から各々の第5の乱数に相当する値を排除した値と第3の値から第1の秘密情報同士の演算結果を得る復元部を有する秘匿演算装置。
【請求項7】
請求項1に記載の乱数を前記第1の秘密情報の生成者以外が生成した乱数を用いて生成する第4生成部を含む分散装置、
を備えた分散システム。
【請求項8】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
分散値同士の乗算を行う乗算部と、
前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、
乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、
備えた秘匿演算装置。
【請求項9】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
秘匿された登録値を用いて、登録値による検証用演算を行う演算部、を含む演算装置と、
前記演算部による演算結果が正しいかどうかを検証する検証部を含む検証復元装置と、
を備えた秘匿演算検証復元システム。
【請求項10】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、プログラムを、
第1の秘密情報に第1の乱数及び第2の乱数を作用させた第1の値を生成し、
前記第1の乱数及び前記第1の秘密情報の少なくとも一方に第3の乱数を作用させた第2の値を生成する第1生成部
として機能させるプログラム。
【請求項11】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
第1の秘密情報に第1の乱数及び第2の乱数を作用させた複数の第1の値と、前記第1の乱数又は前記第1の秘密情報に第3の乱数を作用させた複数の第2の値とを用いて、
前記複数の第1の秘密情報同士の演算結果に前記複数の第1の乱数同士の演算結果、及び第4の乱数を作用させた第3の値を生成し、
前記複数の第1の乱数同士又は秘密情報同士の演算結果に第5の乱数を作用させた第4の値を生成する第2生成部
として機能させるプログラム。
【請求項12】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項11に記載の第2生成部によって得られた第3の値及び第4の値の少なくとも一方が0である場合に第6の乱数を生成する第3生成部と、
前記第6の乱数を秘匿加算する加算部と、
として機能させるプログラム。
【請求項13】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項11又は請求項12に記載のプログラムによって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第1排除部と、
前記第1排除部による排除によって得られた第1の乱数同士の演算結果が正しいか否かを判定する第1判定部と、
として機能させるプログラム。
【請求項14】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項11又は請求項12に記載のプログラムによって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第2排除部と、
前記第2排除部による排除によって得られた第1の乱数同士の演算結果であって、前記第3の値または第4の値が0の場合に第6の乱数を含む第1の乱数同士の演算結果が正しいか否かを判定する第2判定部と、
として機能させるプログラム。
【請求項15】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
請求項13に記載の第1排除部、もしくは請求項14に記載の第2排除部から得られる値、又は請求項11に記載の第4の値から各々の第5の乱数に相当する値を排除した値と第3の値から第1の秘密情報同士の演算結果を得る手段として機能させるためのプログラム。
【請求項16】
分散装置において、コンピュータを、
請求項10に記載の乱数を前記第1の秘密情報の生成者以外が生成した乱数を用いて生成する第4生成部
として機能させるプログラム。
【請求項17】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、コンピュータを、
分散値同士の乗算を行う乗算部と、
前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、
乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、
として機能させるプログラム。
【請求項18】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
演算装置において、コンピュータを、秘匿された登録値を用いて、登録値による検証用演算を行う演算部、
として機能させるプログラム。
【請求項19】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
検証復元装置において、コンピュータを、請求項18に記載の演算部による演算結果が正しいかどうかを検証する検証部、
として機能させるプログラム。
発明の詳細な説明 【技術分野】
【0001】
本開示は、分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムに関する。
【背景技術】
【0002】
近年、ビッグデータおよびIoT環境の進歩に伴い、個人に関する情報の活用が期待されている。ただし、個人情報の活用においては、個人情報が漏洩すると個人のプライバシーに影響を与える可能性がある。そのため、ビッグデータの利活用においては、ビッグデータを活用する技術と、個人に関する情報を守る技術とを両立させる必要がある。このような個人に関する情報を守る技術に対するアプローチとして、データを守りながら演算を行うことができる秘匿計算技術が研究されている。
【0003】
秘匿計算技術は大きく分けると、主に鍵を用いてデータを秘匿する準同型暗号と、鍵を用いずにデータを秘匿する秘密分散法を用いた手法がある。ただし、準同型暗号は一般的に計算量が多く、演算処理に多大な時間がかかるという問題がある。そのため、クラウドシステムへの適用に対しては、計算量が重い準同型暗号よりも、計算量が軽い秘密分散法を用いるというアプローチが検討されている。
【0004】
秘密分散法とはユーザが持っている秘密情報を複数の異なる値(以降、分散値)に変換し、分散する手法である。秘密分散法の1つであるShamirの(k,n)閾値秘密分散法(以下、「Shamir法」または「(k,n)Shamir法」)が知られている。
【0005】
また、秘密情報をL個に分割し、分散式の係数として含ませるランプ型秘密分散方式も知られている。ランプ型秘密分散方式によって、分散値の小型化が実現できる。
【0006】
秘密分散法に関する技術として、例えば、特許文献1には、データを秘匿しながら計算を行い計算結果の正当性を保証する秘匿計算システムが開示されている。
【0007】
また、特許文献2には、秘密分散によりデータを秘匿しつつ、乗算及び加算からなる式の計算を、計算結果の正当性を保ちながら行う秘匿積和結合システムが開示されている。
【0008】
また、特許文献3には、完全準同型暗号及び信頼できる第三者を利用せずに、集計対象データ及びその集計結果を秘匿した状態で集計装置に集計処理を実行させる技術が開示されている。
【0009】
また、秘密分散法の1つに、Shamir法を用いるTUS法がある。TUS法では、他の秘密分散法では実現できないn<2k-1において秘匿演算を実現することが特徴である。
【先行技術文献】
【0010】

【特許文献1】再公表2014-112548号公報
【特許文献2】再公表2012-121333号公報
【特許文献3】特開2013-205592号公報
【発明の概要】
【発明が解決しようとする課題】
【0011】
もっとも、TUS法では、秘匿乗算において乱数で秘匿化された秘密情報αaを一旦復号するために、秘密情報は0を含まず、乱数も0を含まないものである。ただし、秘匿乗算以外では0を含んでもよいものとされる。
【0012】
上記のTUS法の問題の一つに、秘密情報に0を含むことができず、減算を含む秘匿計算を繰り返せないという問題があった。また、計算結果の正当性を検証できないという問題もあった。
【0013】
本開示は、以上の事情を鑑みて成されたものであり、秘密情報に0を含んでいても、効率よく秘匿演算を繰り返すことに対応する分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムを提供することを目的とする。さらに、その計算結果を効率的に検証できる分散装置、秘匿演算装置、検証復元装置、分散システム、秘匿演算検証復元システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0014】
開示の技術は、一つの態様として、第1の発明に係る分散装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、第1の秘密情報に第1の乱数及び第2の乱数を作用させた第1の値を生成し、前記第1の乱数及び前記第1の秘密情報の少なくとも一方に第3の乱数を作用させた第2の値を生成する第1生成部を備えることを特徴とする。
【0015】
開示の技術は、一つの態様として、第2の発明に係る秘匿演算装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、第1の秘密情報に第1の乱数及び第2の乱数を作用させた複数の第1の値と、前記第1の乱数又は前記第1の秘密情報に第3の乱数を作用させた複数の第2の値とを用いて、前記複数の第1の秘密情報同士の演算結果に前記複数の第1の乱数同士の演算結果、及び第4の乱数を作用させた第3の値を生成し、前記複数の第1の乱数同士又は秘密情報同士の演算結果に第5の乱数を作用させた第4の値を生成する第2生成部を備えることを特徴とする。
【0016】
開示の技術は、一つの態様として、第2の発明に係る秘匿演算装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、上記に記載の第2生成部によって得られた第3の値及び第4の値の少なくとも一方が0である場合に第6の乱数を生成する第3生成部と、前記第6の乱数を秘匿加算する加算部と、を更に備えることを特徴とする。
【0017】
開示の技術は、一つの態様として、第3の発明に係る検証復元装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、第2の発明に係る秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第1排除部と、前記第1排除部による排除によって得られた第1の乱数同士の演算結果が正しいか否かを判定する第1判定部と、を備えることを特徴とする。
【0018】
開示の技術は、一つの態様として、第4の発明に係る検証復元装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、第2の発明に係る秘匿演算装置によって得られた、秘密情報に対して乱数を作用させて生成した第3の値から秘密情報と第4の乱数に相当する値を排除する第2排除部と、前記第2排除部による排除によって得られた第1の乱数同士の演算結果であって、前記第3の値または第4の値が0の場合に第6の乱数を含む第1の乱数同士の演算結果が正しいか否かを判定する第2判定部と、を備えることを特徴とする。
【0019】
開示の技術は、一つの態様として、第2の発明に係る秘匿演算装置が、第3の発明に記載の第1排除部、もしくは第4の発明に記載の第2排除部から得られる値、又は第4の値から各々の第5の乱数に相当する値を排除した値から第1の秘密情報同士の演算結果を得る復元部を有することを特徴とする。
【0020】
開示の技術は、一つの態様として、第5の発明に係る分散システムが、請求項1に記載の乱数を前記第1の秘密情報の生成者以外が生成した乱数を用いて生成する第4生成部を含む分散装置、を備えることを特徴とする。
【0021】
開示の技術は、一つの態様として、第6の発明に係る秘匿演算装置が、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、分散値同士の乗算を行う乗算部と、前記乗算部による乗算により得られた乗算値と他装置から送られた分離できない乗算値とを用いて分散値の次数変換処理を行う変換部と、乱数を生成し、生成した乱数を自装置に返信される次数変換後の分散値に加算する加算部と、を備えることを特徴とする。
【0022】
開示の技術は、一つの態様として、第7の発明に係る秘匿演算検証復元システムが、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、秘匿された登録値を用いて、登録値による検証用演算を行う演算部、を含む演算装置と、前記演算部による演算結果が正しいかどうかを検証する検証部を含む検証復元装置と、を備えることを特徴とする。
【0023】
開示の技術は、一つの態様として、コンピュータを、上記第1~第7の発明のいずれか1つの装置の各部として機能させるプログラムを有する。
【発明の効果】
【0024】
本開示によれば、秘密情報に0を含んでいても、効率よく秘匿演算を繰り返すことができ、その計算結果を効率的に検証することができる。
【図面の簡単な説明】
【0025】
【図1】第1実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図2】第1実施形態に係るサーバ16のハードウェア構成の一例を示す図である。
【図3】第1実施形態に係る変換用乱数組を生成する処理シーケンスの一例を示す図である。
【図4】第1実施形態の変形例に係る変換用乱数組を生成する処理シーケンスの一例を示す図である。
【図5】第2実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図6】第2実施形態に係る入力装置212のハードウェア構成の一例を示す図である。
【図7】第2実施形態に係るサーバ216のハードウェア構成の一例を示す図である。
【図8】第2実施形態に係る分散の処理シーケンスの一例を示す図である。
【図9】第2実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図10】第2実施形態に係る補正処理の処理シーケンスの一例を示す図である。
【図11】第3実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図12】第3実施形態に係る復元装置314のハードウェア構成の一例を示す図である。
【図13】第3実施形態に係る分散の処理シーケンスの一例を示す図である。
【図14】第3実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図15】第3実施形態に係る検証の処理シーケンスの一例を示す図である。
【図16】第4実施形態に係るサーバ416のハードウェア構成の一例を示す図である。
【図17】第4実施形態に係る分散の処理シーケンスの一例を示す図である。
【図18】第4実施形態の変形例に係る分散の処理シーケンスの一例を示す図である。
【図19】第5実施形態に係る復元装置514のハードウェア構成の一例を示す図である。
【図20】第5実施形態に係る分散の処理シーケンスの一例を示す図である。
【図21】第5実施形態に係る秘匿積和演算の処理シーケンスの一例を示す図である。
【図22】第5実施形態に係る補正処理の処理シーケンスの一例を示す図である。
【図23】第5実施形態に係る検証の処理シーケンスの一例を示す図である。
【図24】第6実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図25】第6実施形態に係る復元装置614のハードウェア構成の一例を示す図である。
【図26】第6実施形態に係るブロックチェーン装置616のハードウェア構成の一例を示す図である。
【図27】第6実施形態に係る検証装置618のハードウェア構成の一例を示す図である。
【図28】第6実施形態に係る分散、秘匿積和演算、補正処理の処理シーケンスの一例を示す図である。
【図29】第6実施形態に係る検証の処理シーケンスの一例を示す図である。
【発明を実施するための形態】
【0026】
以下、図面を参照して、本開示の技術を実施するための形態例を詳細に説明する。

【0027】
まず、実施形態の詳細を説明する前に、実施形態の技術の前提となるShamir法、及びTUS法の詳細を説明した上で、TUS法における各問題点を説明する。

【0028】
<Shamir法>
Shamir法は、ある秘密情報をn個の分散情報に分散し、そのうちのk個以上の分散情報を集めることによって、元の秘密情報を復元することができるという方法である。ただし、k個未満の分散情報からは元の秘密情報を得ることが一切できないというものである。Shamir法での秘密情報の分散及び復元は、以下に示すように行われる。このような手法を(k,n)Shamir法と呼ぶ。

【0029】
<分散>
1.ユーザはs<pかつn<pの条件を満たす任意の素数pを選択する。

【0030】
2.ユーザはGF(p)の元から、n個のx(i=0,1,2,…,n-1)を選び、サーバIDとする。

【0031】
3.ユーザはGF(p)の元から、k-1個の乱数a(l=1,2,…,k-1)を選び、以下の分散式を生成する。

【0032】
=s+a+a+…+ak-1k-1 (mod p)

【0033】
4.ユーザは上記式のxに各サーバIDを代入して分散値Wを計算し、各サーバSに送信する。

【0034】
<復元処理>
1.復元に用いる分散情報をW(i=0,1,2,…,k-1)とする。また、その分散情報に対応するサーバIDをxとする。

【0035】
2.復元者は、k個の(x,W)を集め、集めたk個の(x,W)を上記の分散式に代入し、k個の連立方程式を解くことで秘密情報であるsを復元する。なお、sの復元の際には、Lagrangeの補間公式を用いることができる。

【0036】
以上がShamir法の詳細である。

【0037】
<TUS法>
次にTUS法の詳細を説明する。以下に、TUS法を用いてab+cの積和演算を行う場合の例を示す。なお、秘密情報a,b,c及び乱数αは、a,b,c,α∈Z/pZである。ただし、乗算において一旦復元されるaと乱数は0ではない。以下において、[a]は秘密情報aに対してサーバSが保持する分散値を表す。以降、秘密分散の処理も含めてすべての秘匿演算はpを法として行われる。また、サーバSは攻撃者が知らない変換用乱数組([ε]),([φ])を持つものとする。変換用乱数組とは、例えば
JP2020056840A_000003t.gif
の関係を満たす変換用乱数εの分散値と、εを構成する乱数εからなる組である。

【0038】
ab+cの秘匿演算の入出力を以下に示す。

【0039】
(入力)
([αa],[α,…,[αk-1)(j=0,1,…,k-1)
([βb],[β,…,[βk-1)(j=0,1,…,k-1)
([γc],[γ,…,[γk-1)(j=0,1,…,k-1)
(出力)
([δ(ab+c)],[δ,…,[δk-1)(i=0,1,…,n-1)

【0040】
上記の入出力のもと、ab+cの秘匿演算は以下に示すように行われる。

【0041】
1.k台のサーバSは[αa],[βb],[γc]を公開する。また、Sは、αa,βb,γcを復元する。

【0042】
2-1.k台のサーバSは[α,…,[αk-1,[β,…,[βk-1,[γ,…,[γk-1を収集して、乱数αを復元する。

【0043】
2-2.サーバSは、乱数δを生成する。

【0044】
2-3.サーバSは、生成した乱数δを用いて、δ/αβε/γφを計算して公開する。

【0045】
3.全てのサーバSは、以下の式を計算する。
JP2020056840A_000004t.gif

【0046】
ただし、
JP2020056840A_000005t.gif
とする。

【0047】
4.k台のサーバSは乱数δをShamir法で分散し、全てのサーバSに分散する。

【0048】
5.以上より、サーバS(i=0,1,2,…,n-1)は秘密情報ab+cに関する分散情報として([δ(ab+c)],[δ,…,[δk-1)を保持する。

【0049】
以上がTUS法による秘匿演算の詳細である。TUS法は以下の3つの問題点を持つ。

【0050】
<問題点1>
問題点1は、複数人による変換用乱数組の安全な生成法が知られていないというものである。変換用乱数組を一人が生成する場合、例えば生成者はk個の乱数ε,…,εk-1を生成して、ε=εε…εk-1を計算し、εを秘密分散して、[ε]とεをサーバSに送れば、Sは変換用乱数組([ε])を持つことができる。TUS法の安全性は変換用乱数組の安全性に依存するため、変換用乱数組の生成者が攻撃者であれば、その変換用乱数組を用いた秘匿計算は安全ではない。よって、信頼できない複数の生成者が変換用乱数組を生成しても、その値を知ることができない安全な変換用乱数組の生成法がなければ、上記TUS法は安全ではないということである。

【0051】
<問題点2>
問題点2は、秘密情報に0を含むことができないというものである。例えば、入力をaではなくa+1として入力すれば、最初の入力aは0であってもよいが、減算を含む場合、すなわちab-cまたはa-cを演算する場合、その出力が0となる可能性がある。そのため、TUS法による演算結果を用いて秘匿演算を繰り返せないという問題がある。

【0052】
<問題点3>
問題点3は、秘匿計算の正当性を検証できないというものである。一般に秘密分散においては、k-1台までのサーバがもつ情報は盗聴などにより知られることを想定している。しかし、その盗聴可能なk-1台のサーバが乗っ取られ、偽の情報を出力したり、決められた処理をしない場合、上記秘匿演算の結果は信用できないものとなる。

【0053】
以上がTUS法の問題点1~3である。

【0054】
問題点1の解決はTUS法において必須であり、問題点1が解決されることにより、TUS法の安全性が向上する。例えば、信頼できる変換用乱数組の生成者がいない場合でもTUS法を用いて秘匿演算できるようになる。また問題点1を解消することは、秘匿計算の検証においても必要となる。

【0055】
問題点2が解決されることにより、減算を含む秘匿演算を繰り返すことができるようになり、TUS法の実用性が向上する。また問題点2を解消することは、繰返し演算された結果、または0を含む結果を検証する場合に必要となる。

【0056】
問題点3が解決されることにより、嘘の情報を出力するなど決められたプロトコルに従わないactiveな攻撃者に対しても安全性を確保することができるようになる。さらに、一般の検証機能付き秘匿計算は非常に複雑な処理を必要とするが、本発明の実施形態の手法によって非常に効率的に演算結果を検証できるようになる。

【0057】
以上の各問題点を解消することによって、安全かつ効率的、実用的に秘匿演算を検証できるようになる。

【0058】
以上を踏まえて、以下に各実施形態を展開する。以下の各実施形態において説明する秘密分散システムは、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の分散値によって秘密情報を復元でき、k個未満では秘密情報を復元できないシステムである。

【0059】
[第1実施形態]
第1実施形態は、上記問題点1に対応する。すなわち複数の信頼できない入力者及び復元者によって生成されていたとしても、変換用乱数の値が知られない安全な変換用乱数組の生成法を実現するものである。本実施形態の手法によって生成された変換用乱数組は、以降の各実施形態においても用いられる。

【0060】
まず第1実施形態の手法の前提について説明する。第1実施形態では、変換用乱数組を生成するために、参考文献1及び2に示される手法を拡張する。

【0061】
[参考文献1]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.
[参考文献2]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.

【0062】
参考文献1及び2において、2k次の多項式に対する分散値をk次の多項式に対する分散値に変換する方法が示されている。例えば参考文献1では、以下に示す変換手法が開示されている。

【0063】
ある規則によって生成された定数を要素とする行列を以下の行列Aとする。

【0064】
JP2020056840A_000006t.gif

【0065】
上記行列Aを用いて、2k次の多項式に対する分散値ベクトルW=(W,W,・・・,W2k-1)に対してR=W・Aを計算することで、k次の多項式に対する分散値ベクトルR=(R,R,・・・,R2k-1)に変換することができる。参考文献2の手法もほぼ同様の処理で、分散値ベクトルRへの変換を実現できる。

【0066】
ただし、参考文献1及び2の手法はサーバ台数がn≧2k-1の場合に有効であるが、本実施形態ではTUS法と同様にn<2k-1の場合を扱う。以下で説明する本実施形態の構成では、二人の入力者に対応する入力装置と、一人の復元者に対応する復元装置とを想定し、n=kの場合の生成法を示す。ただし、後述するように復元装置は復元を行わず、演算支援装置としてふるまう。

【0067】
2k-1>n>kの場合は乱数α等を直接サーバに送らず、(k,n)Shamir法を用いて分散し、演算を行うk台のサーバが乱数α等を復元して使用する。また、秘密情報λは(k,n+k-1)Shamir法を用いて分散され、n台のサーバ中k-1台のサーバのみが[αλi+kを持つ。また、復元装置は復元を行うと変換用乱数の値を知るので、復元装置は復元を行わず、演算支援の役割を持つ。以下において、秘密情報λ及び乱数αj,ij,iはλj,ij,i∈Z/pZである。ただし、秘密情報と乱数は0を含まないものとする。また、0r1などは0を表し、他と区別するため記号を付ける。

【0068】
以上の前提を踏まえて、図1を参照して、本実施形態に係る秘密分散システム10の構成を説明する。図1に示すように、秘密分散システム10は、2台の入力装置12A及び入力装置12B、復元装置14、並びにサーバ16~16n-1を含む。以下、入力装置12A及び入力装置12Bについて共通する内容については「入力装置12」、サーバ16~16n-1について共通する内容については「サーバ16」とし、末尾の識別記号を省略して説明する場合もある。入力装置12、復元装置14、及びサーバ16は、ネットワークNに接続され、互いに通信可能とされる。なお、サーバ16が、乗算部と、変換部と、加算部とを含む秘匿演算装置の一例である。

【0069】
入力装置12は、秘密情報の入力者(以下、単に「入力者」という)によって操作される装置であり、入力装置12の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。

【0070】
復元装置14は、秘密情報を復元する復元者(以下、単に「復元者」という)によって操作される装置であり、復元装置14の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。

【0071】
サーバ16は、変換用乱数組の生成に係る計算、変換用乱数組の保管などをする役割を持つ。また、サーバ16はn台存在し、説明に応じてサーバS(i=0,…,n-1)等とも記載する(以下、各実施形態において同様である)。

【0072】
次に、図2を参照して、本実施形態に係るサーバ16のハードウェア構成を説明する。図2に示すように、サーバ16は、CPU(Central Processing Unit)20、一時記憶領域としてのメモリ21、不揮発性の記憶部22を含む。また、サーバ16は、液晶ディスプレイ等の表示装置23、キーボード等の入力I/F24、及びネットワークNに接続されるネットワークI/F25(InterFace)を含む。CPU20、メモリ21、記憶部22、表示装置23、入力I/F24、及びネットワークI/F25は、バス26に接続される。

【0073】
記憶部22は、HDD(Hard Disk Drive)、SSD(Solid State Drive)、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部22には、変換用乱数組生成プログラム28が記憶される。変換用乱数組生成プログラム28は、乗算プロセス28aと、変換プロセス28bと、加算プロセス28cとを含む。CPU20は、記憶部22から変換用乱数組生成プログラム28を読み出してからメモリ21に展開し、展開した生成プログラム28を実行する。CPU20が変換用乱数組生成プログラム28の乗算プロセス28aを実行することで、開示の技術の乗算部として動作する。CPU20が変換用乱数組生成プログラム28の変換プロセス28bを実行することで、開示の技術の変換部として動作する。CPU20が変換用乱数組生成プログラム28の加算プロセス28cを実行することで、開示の技術の加算部として動作する。

【0074】
なお、入力装置12、及び復元装置14についてはサーバ16と同様の装置構成をとることができ、実行するプログラムのみが異なるため詳細な説明を省略する。

【0075】
次に、図3を参照して、本実施形態に係る秘密分散システム10の作用を説明する。

【0076】
<変換用乱数組生成1:n=k>
図3は、秘密分散システム10の変換用乱数組を生成する処理シーケンスを説明したものである。以下において、サーバ16は、シーケンスの各処理に応じてサーバS、Sj、及びSk-1のいずれかが対象であるものとして説明する。

【0077】
S10で、入力装置12Aは、乱数λ0,i、及びα(i=0,…,k-1)を生成する。

【0078】
S12で、入力装置12Aは、
JP2020056840A_000007t.gif
を計算する。また、入力装置12Aは、λを(k,2k-1)Shamir法で分散して[αλi+k=α×[λi+kを計算する。

【0079】
S14で、入力装置12Aは、S10及びS12で得られた[λ,[αλi+k0,iをサーバSに送信する。ただし、サーバSk-1は[αλ2k-1を持たないものとする。

【0080】
S16で、入力装置12Bは、乱数λ1,i、及びβ(i=0,…,k-1)を生成する。

【0081】
S18で、入力装置12Bは、
JP2020056840A_000008t.gif
を計算する。また、入力装置12Bは、λを(k,2k-1)Shamir法で分散して[βλi+k=β×[λi+kを計算する。

【0082】
S20で、入力装置12Bは、S16及びS18で得られた[λ,[βλi+k1,iをSに送信する。ただし、サーバSk-1は[βλ2k-1を持たないものとする。

【0083】
S22で、サーバSk-1を除くサーバS(以下、本シーケンスの説明では単にSと記載する)は、[λλ=[λ×[λ,[αβλλi+k=[αλi+k×[βλi+kを計算する。なお、S22は、サーバSにおける、変換用乱数組生成プログラム28の乗算プロセス28aに対応する。サーバSのCPU20が、乗算プロセス28aを実行することで、開示の技術における分散値同士を乗算する処理を行う。

【0084】
S24で、サーバSは、[αβλλi+kを復元装置14に送信する。

【0085】
S26で、サーバSは、αβを計算する。

【0086】
S28で、復元装置14は、0r1を(2k-1,2k-1)Shamir法で分散する。

【0087】
S30で、復元装置14は、サーバSで計算されたαβを取得する。

【0088】
S32で、取得したαβを元に、αβを復元する。

【0089】
S34で、復元装置14は、S28で分散した0r1、及びS32で復元したαβを用いて[λλ]′i+k=[αβλλi+k/αβ+[0r1i+kを計算する。

【0090】
S36で、復元装置14は、計算した[λλ]′i+kをサーバSに送信する。

【0091】
S38で、サーバSは、0を(k,n)Shamir法で分散し、Ri,jを計算する。j≠i(j=0,…,n-1)のとき、Ri,jは以下のように計算できる。なお、以下におけるai,jなどは上記行列Aの要素である。
i,j=ai,j×[λλ+ai+n,j×[λλ]′i+n+[0

【0092】
なお、S38は、サーバSにおける、変換用乱数組生成プログラム28の変換プロセス28bに対応する。サーバSのCPU20が、変換プロセス28bを実行することで、開示の技術における分散値の次数変換処理を行う。S38のRi,jの計算ではS36で返却された[λλ]′i+kを用いるが、[λλ]′i+kが他装置から送られた分離できない乗算値の一例である。また、Ri,jが次数変換後の分散値の一例である。

【0093】
S40で、サーバSは、i=jか否かを判定する。i=jであればS42へ移行し、i=jでなければ(すなわち、i≠jであれば)、S44へ移行する。

【0094】
S42で、サーバSは、乱数rを生成して、以下のようにRi,jにrを加算する。
i,j=ai,j×[λλ+ai+n,j×[λλ]′i+n+[0+r

【0095】
なお、S42は、サーバSにおける、変換用乱数組生成プログラム28の加算プロセス28cに対応する。サーバSのCPU20が、加算プロセス28cを実行することで、開示の技術における乱数を分散値に加算する処理を行う。

【0096】
S44で、サーバSは、計算したRi,jを復元装置14に送信する。

【0097】
S46で、復元装置14は、0r2を(k,n)Shamir法で分散し、R′i,j=Ri,j+ai,j×[0r1+[0r2を計算する。ただし、j=0,…,n-1とし、
(i≠j)のとき:
R′i,j=ai,j×[λλ]′+ai+n,j×[λλ]′i+n+[0+[0r2(i=j)のとき:
R′i,j=ai,j×[λλ]′+ai+n,j×[λλ]′i+n+[0+[0r2+r
とする。

【0098】
S48で、復元装置14は、R′i,jをサーバSに送信する。このように、サーバSで計算された次数変換後の分散値であるRi,jは、R′i,jとなってサーバSに返信される。

【0099】
S50で、サーバSは、Σi=0k-1R′i,j-r=[λ]と計算する。また、サーバSは、λ=λ0,iλ1,iを計算する。以上のシーケンスによって、変換用乱数組([λ])が得られる。

【0100】
[第1実施形態の変形例]
上述した変換用乱数組生成1では、n=kのとき、入力装置12及び復元装置14を必要とする場合を例に説明した。一方、n=k=2の場合、入力装置12及び復元装置14を不要とした以下の処理が可能となる。すなわち、サーバ16だけの構成で変換用乱数組生成が可能となる。

【0101】
<変換用乱数組生成1′:n=k=2>
図4は、n=k=2の場合の変換用乱数組を生成する処理シーケンスを説明したものである。以下において、サーバ16のうち、サーバS、及びSの間で処理する場合を例に説明する。図4のシーケンスにおいて、以下のS60~S94の処理が行われる。なお、図4において各処理は簡略化して記載するものとする。

【0102】
S60では、サーバSは、乱数λを生成し、α=ααを計算する。

【0103】
S62では、サーバSは、λを(2,3)Shamir法で分散して、[αλ=α×[λ,[αλ=α×[λ,[τλ=τ×[λを計算する。

【0104】
S64では、サーバSは、得られた[τλをサーバSに送信する。

【0105】
S66では、サーバSは、乱数λを生成し、β=ββを計算する。

【0106】
S68では、サーバSは、λを(2,3)Shamir法で分散して、[βλ=β×[λ,[βλ=β×[λを計算する。

【0107】
S70では、サーバSは、得られた[βλ,[βλをサーバSに送信する。

【0108】
S72では、サーバSは、0を(3,3)Shamir法で分散し、αβと以下を計算する。
[αβλλ]′=[αλ×[βλ+[0,[αβλλ]′=[αλ×[βλ+[0,[0

【0109】
S74では、サーバSは、計算した[αβλλ]′、[αβλλ]′、αβをサーバSに送信する。

【0110】
S76では、サーバSは、0を(3,3)Shamir法で分散し、αβとαβからαβを計算すると共に、以下を計算する。ただし、[001=[0/αβ+[0である。

【0111】
JP2020056840A_000009t.gif
JP2020056840A_000010t.gif
[001=[0/αβ+[0

【0112】
S78では、サーバSは、得られた[λλ]′,[λλ]′,[001をサーバSに送信する。

【0113】
S80では、サーバSは、00′を(2,2)Shamir法で分散する。

【0114】
S82では、サーバSは、乱数rを生成する。

【0115】
S84では、サーバSは、分散した00′、及び乱数rを用いて、以下のR0,0及びR0,1を計算する。
0,0=τ(a0,0×[λλ]′+a2,0×[λλ]′+a1,0×[001)+[00′+r=τ(a0,0[λλ+a2,0[λλ)+τ[001]″+[00′+r
0,1=τ(a0,1×[λλ]′+a2,1×[λλ]′+a1,1×τ[001)+[00′=τ(a0,1[λλ+a,[λλ)+τ[001]″+[00′

【0116】
S86では、サーバSは、計算したR0,0,R0,1をサーバSに送信する。

【0117】
S88では、サーバSは、[τλλ=[τλ×[λを計算すると共に、01′を(2,2)Shamir法で分散し、以下を計算する。
R′0,0=R0,0+a1,0×[τλλ+[01′=τ[λλ+τ[001]″+[00′+[01′+r
R′0,1=R0,1+a1,1×[τλλ+[01′=τ[λλ+τ[001]″+[00′+[01′

【0118】
S90では、サーバSは、得られたR′0,0をサーバSに送信する。

【0119】
S92では、サーバSは[λ]=R′0,0-r=τλとして変換用乱数組([λ])を得る。

【0120】
S94では、サーバSは[λ]=R′0,1として変換用乱数組([λ])を得る。

【0121】
以上が、変換用乱数組生成1′の場合の説明である。

【0122】
以上説明したように、本発明の第1実施形態の手法を用いて変換用乱数組を生成することにより、安全に変換用乱数組を生成することができる。

【0123】
[第2実施形態]
第2実施形態は、上記問題点2に対応する。すなわち秘密情報に0を含む場合の手法である。

【0124】
まず第2実施形態の手法の前提について説明する。以下において,秘密情報a,b,c及び乱数αj,ij,ij,i,a,b,cはa,b,c,αj,ij,ij,i,a,b,c∈Z/pZである。また、秘密情報に0を含んでもよいが、乱数は0を含まないものとする。また、第2実施形態では、第1実施形態に示した手法により変換用乱数組が予め生成されており、サーバSは変換用乱数組([εh,ih,i),(h=1,…,必要個数)を持つものとする。以下の説明においては、n=kにおける秘匿積和演算を示すが、n>kの場合、αj,ij,ij,ij,iなどは(k,n)Shamir法で分散し、演算に参加するk台のサーバが復元してもよい。また、a+aのように秘密情報に加えられる乱数a,b,cは0でなく、その加算結果も0とならない値を選ぶものとする。積和演算を組み合わせることにより、任意の四則演算を構成できるため、秘匿積和演算を例に以下、詳細を説明する。

【0125】
以上の前提を踏まえて、図5を参照して、本実施形態に係る秘密分散システム210の構成を説明する。図5に示すように、秘密分散システム210は、3台の入力装置212A~212C、及び複数台のサーバ216~216n-1を含む。以下、入力装置212A~212Cについて共通する内容については「入力装置212」、サーバ216~216n-1について共通する内容については「サーバ216」とし、末尾の識別記号を省略して説明する場合もある。入力装置212、及びサーバ216は、ネットワークNに接続され、互いに通信可能とされる。なお、入力装置212が、第1生成部を含む分散装置の一例である。また、サーバ216が、第2生成部を含む秘匿演算装置の一例である。また、サーバ216が、第3生成部と、加算部とを含む秘匿演算装置の一例である。

【0126】
入力装置212は、秘密情報の入力者によって操作される装置である。入力装置212は、乱数を作用させた所定の値を生成して、サーバ216に分散する。

【0127】
サーバ216は、秘匿積和演算に係る計算などをする役割を持つ。

【0128】
次に、図6を参照して、本実施形態に係る入力装置212のハードウェア構成を説明する。図6に示すように、入力装置212は、CPU220、一時記憶領域としてのメモリ221、不揮発性の記憶部222を含む。また、入力装置212は、表示装置223、入力I/F224、及びネットワークNに接続されるネットワークI/F225を含む。CPU220、メモリ221、記憶部222、表示装置223、入力I/F224、及びネットワークI/F225は、バス226に接続される。

【0129】
記憶部222は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部222には、第1生成プログラム228が記憶される。CPU220は、記憶部222から第1生成プログラム228を読み出してからメモリ221に展開し、展開した第1生成プログラム228を実行する。CPU220が第1生成プログラム228を実行することで、開示の技術の第1生成部として動作する。なお、後述する第3~第5実施形態においても同様である。

【0130】
次に、図7を参照して、本実施形態に係るサーバ216のハードウェア構成を説明する。図7に示すように、サーバ216は、CPU230、一時記憶領域としてのメモリ231、不揮発性の記憶部232を含む。また、サーバ216は、表示装置233、入力I/F234、及びネットワークNに接続されるネットワークI/F235を含む。CPU230、メモリ231、記憶部232、表示装置233、入力I/F234、及びネットワークI/F235は、バス236に接続される。

【0131】
記憶部232は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部232には、秘匿積和演算プログラム238が記憶される。秘匿積和演算プログラム238は、第2生成プロセス238aと、第3生成プロセス238bと、加算プロセス238cとを含む。CPU230は、記憶部232から秘匿積和演算プログラム238を読み出してからメモリ231に展開し、展開した秘匿積和演算プログラム238を実行する。CPU230が秘匿積和演算プログラム238の第2生成プロセス238aを実行することで、開示の技術の第2生成部として動作する。CPU230が秘匿積和演算プログラム238の第3生成プロセス238bを実行することで、開示の技術の第3生成部として動作する。CPU230が秘匿積和演算プログラム238の加算プロセス238cを実行することで、開示の技術の加算部として動作する。なお、後述する第3、第5実施形態においても同様である。なお、サーバ216において補正処理が行われない想定とし、秘匿積和演算プログラム238において第2生成プロセス238aのみを含み、第3生成プロセス238bと、加算プロセス238cとを含まないようにしてもよい。

【0132】
次に、図8~10を参照して、本実施形態に係る秘密分散システム210の作用を説明する。

【0133】
まず、秘密情報を各サーバに分散する処理について説明する。図8は、秘密分散システム210における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置212A~Cが持つ秘密情報をサーバ216に分散する。以下において、サーバ216は、分散の処理シーケンスの各処理に応じてn台の全てのサーバである全サーバS、及びサーバSのいずれかが対象であるものとして説明する。

【0134】
<分散2>
S210で、入力装置212Aは、乱数a1,i2,i(i=0,…,k-1)を生成する。

【0135】
S212で、入力装置212Aは、以下の式に基づいて、秘密情報aに対してαとα(a+a)を計算する。

【0136】
JP2020056840A_000011t.gif
JP2020056840A_000012t.gif

【0137】
なお、S212は、入力装置212Aにおける、第1生成プログラム228に対応する。入力装置212AのCPU220が、第1生成プログラム228を実行することで、開示の技術における第1生成部の処理を行う。秘密情報aが第1の秘密情報、乱数aが第1の乱数、乱数αが第2の乱数、乱数αが第3の乱数の一例である。α(a+a)が、第1の乱数及び第2の乱数を作用させた第1の値の一例である。αが、第1の乱数に第3の乱数を作用させた第2の値の一例である。第1生成プログラム228との対応は、以下、入力装置212B、及び入力装置212Cの秘密情報に対して行う処理において同様である。

【0138】
S214で、入力装置212Aは、計算したαとα(a+a)を全サーバSに送信する。

【0139】
S216で、入力装置212Aは、乱数α1,i2,iをサーバSに送信する。

【0140】
S218で、入力装置212Bは、乱数b1,i2,i(i=0,…,k-1)を生成する。

【0141】
S220で、入力装置212Bは、以下の式に基づいて、秘密情報bに対してβとβ(b+b)を計算する。

【0142】
JP2020056840A_000013t.gif
JP2020056840A_000014t.gif

【0143】
S222で、入力装置212Bは、計算したβとβ(b+b)を全サーバSに送信する。

【0144】
S224で、入力装置212Bは、乱数β1,i2,iをSに送信する。

【0145】
S226で、入力装置212Cは、乱数c1,i2,i(i=0,…,k-1)を生成する。

【0146】
S228で、入力装置212Cは、以下の式に基づいて、秘密情報cに対してγとγ(c+c)を計算する。

【0147】
JP2020056840A_000015t.gif
JP2020056840A_000016t.gif

【0148】
S230で、入力装置212Cは、計算したγとγ(c+c)を全サーバSに送信する。

【0149】
S232で、入力装置212Cは、乱数γ1,i2,iをサーバSに送信する。

【0150】
以上の分散の処理シーケンスを実行することで、サーバSはα(a+a),β(b+b),γ(c+c)とα1,i1,i1,i2,i2,i2,iを持つことになる。また、サーバSは、上記第1実施形態の手法で生成された変換用乱数組([εh,ih,i)(h=0,…,必要個数)も予め持つものとする。

【0151】
上記で説明した分散2の特徴は、秘密情報が漏洩しないよう、秘密情報に乱数を加えた値とその乱数のみが秘匿されて公開される点である。また、下記に説明する秘匿積和演算2は、秘密情報に乱数を加えた値とその乱数のみから、秘密情報による秘匿演算結果に乱数を加えた値とその乱数による秘匿演算結果が得られるように構成される。また、以下の秘匿積和演算において、計算結果を新たなα(a+a),αなどとするが、β(b+b)またはγ(c+c)としてもよい。またα2,i1,iも同様である。

【0152】
<秘匿積和演算2>
次に秘匿積和演算する処理について説明する。図9は、秘密分散システム210における、秘匿積和演算の処理シーケンスを説明したものである。図9では、説明の便宜のため、サーバ216のうち、サーバS、Sの間で秘匿積和演算の処理シーケンスが行われるものとし、図9上は全サーバSへの送信はサーバSに対する送信であるものとして説明するが、サーバSで行われる処理はサーバSでも行われる。

【0153】
S240で、サーバS(i=0,…,k-1)は、以下の乱数δ1,i2,iを生成する。

【0154】
JP2020056840A_000017t.gif

【0155】
S242で、サーバSは、S240で生成した乱数δ1,i2,iを用いて以下を計算する。

【0156】
JP2020056840A_000018t.gif
JP2020056840A_000019t.gif

【0157】
S244で、サーバSは、S242の計算結果をサーバSに送信する。

【0158】
S246で、サーバSは、サーバSから受信した計算結果を用いて、以下を計算する。ただし以降、Πはi=0,…,k-1に関する乗算を表す。

【0159】
JP2020056840A_000020t.gif
JP2020056840A_000021t.gif

【0160】
S248で、サーバSは、S246の計算結果を全サーバSに送信する。

【0161】
S250で、サーバSは、サーバSから受信した計算結果を用いて、以下を計算して公開し、計算結果を復元する。

【0162】
JP2020056840A_000022t.gif

【0163】
なお、S250は、サーバSにおける、秘匿積和演算プログラム238の第2生成プロセス238aに対応する。サーバSのCPU230が、第2生成プロセス238aを実行することで、開示の技術における第3の値の生成、及び第4の値の生成を行う。δ{(ab+c)+(c-a)}が、開示の技術における第3の値の一例である。δ(c-a)が、開示の技術における第4の値の一例である。第3の値は、複数の第1の秘密情報同士の演算結果(ab+c)に複数の乱数同士の演算結果(c-a)、及び第4の乱数(δ)を作用させた値である。また、第3の値は、複数の第1の秘密情報同士の演算結果を第1の秘密情報に置き換え、複数の第1の乱数同士の演算結果を第1の乱数に置き換え、第4の乱数を第2の乱数に置き換えた場合に第1の値と同形式になる。第4の値は、第1の乱数同士の演算結果(c-a)に第5の乱数(δ)を作用させた値である。また、第4の値は、複数の第1の乱数同士の演算結果を第1の乱数に置き換え、第5の乱数を第3の乱数に置き換えた場合に第2の値と同形式になる。

【0164】
S252は、秘匿積和演算の処理シーケンスを繰り返す場合の処理である。S252で、サーバSは、δ{(ab+c)+(c-a)}及びδ(c-a)が0でなければ、その復元値を新たなα(a+a)及びαとして設定し、δ2,i1,iを新たなα2,i1,iに設定してS240に戻る。上記の秘匿積和演算の処理シーケンスは、例えば全てのサーバSについて処理を終了するまで繰り返す。

【0165】
<補正処理2>
次に、補正処理について説明する。上述した図9の秘匿積和演算の処理シーケンスにおいて、δ{(ab+c)+(c-a)},δ(c-a)の少なくとも1つが0の場合、以下の補正処理を行う。図10は、秘密分散システム210における補正処理の処理シーケンスを説明したものである。補正処理の処理シーケンスは、サーバ216のうち、全サーバS、サーバS、及びSの間で行われるものとして説明する。また、δ{(ab+c)+(c-a)}=0の場合を第1のケース、δ(c-a)=0の場合を第2のケースとして、第1のケース及び第2のケースのいずれか少なくとも一つに当てはまる場合の計算例を説明する。

【0166】
S260で、サーバSは、新たな乱数τ1,iとa′1,iを生成し、その積τ1,ia′1,iを公開する。

【0167】
S262で、サーバSは、τa′=Πτ1,ia′1,iを新たなαに設定する。また、τ1,iを新たなα1,iに設定する。なお、S262は、サーバSにおける、秘匿積和演算プログラム238の第3生成プロセス238bに対応する。サーバSのCPU230が、第3生成プロセス238bを実行することで、開示の技術における第6の乱数の生成を行う。a′が、第6の乱数の一例である。

【0168】
S264で、サーバSは、乱数τ2,iを生成する。

【0169】
S266で、サーバSは、S264で生成した乱数τ2,iを用いて計算を行う。第1ケースの場合、
JP2020056840A_000023t.gif
と計算する。第2のケースの場合、
JP2020056840A_000024t.gif
と計算する。

【0170】
S268で、サーバSは、S266の計算結果をサーバSに送信する。

【0171】
S270で、サーバSは、サーバSから受信した計算結果を用いて、iについて乗算し計算を行う。第1のケースの場合
JP2020056840A_000025t.gif
と計算する。第2のケースの場合
JP2020056840A_000026t.gif
と計算する。

【0172】
S272で、サーバSは、S270の計算結果をサーバSに送信する。

【0173】
S274で、サーバSは、S272で返却された計算結果を用いて計算を行い、秘密情報を復元する。第1のケースの場合
JP2020056840A_000027t.gif
を計算する。第2のケースの場合
JP2020056840A_000028t.gif
を計算する。なお、S264は、サーバSにおける、秘匿積和演算プログラム238の加算プロセス238cに対応する。サーバSのCPU230が、加算プロセス238cを実行することで、開示の技術における第6の乱数(a′)を秘匿加算する処理を行う。

【0174】
S276で、サーバSは、S274の計算結果を用いて、新たなα(a+a)を設定する。また、τ2,iを新たなα2,iに設定する。

【0175】
秘匿積和演算を繰り返す場合には、上記図9の秘匿積和演算の処理シーケンスのS240に戻る。

【0176】
以上が補正処理の処理シーケンスの説明である。以下に補正処理に関する補足を述べる。

【0177】
上記において、c=c=c+c=0としてcに関する処理を省略すれば秘匿乗算になり、α(a+a)=αa=1としてaに関する処理を省略すれば秘匿加算になる。また、abとcの間の+を-にすれば秘匿減算となる。また、α(a+a)からαを秘匿減算すればαaが出力されるので、上記秘匿積和演算の処理シーケンスのS250におけるα(a+a)による乗算をαaによる除算にし、-β(b+b)を-βにすれば
JP2020056840A_000029t.gif
の除算が実現できる。この場合、
JP2020056840A_000030t.gif

JP2020056840A_000031t.gif
に変化させる。

【0178】
上記において、δ{(ab+c)+(c-a)}=0の場合、ab+c=(a-c)となるが、a,b,cが秘匿されている。そのため、秘密情報ab+cは漏えいせず、(a-c)=ab+cとして、a′を秘密情報ab+cに加える新たな乱数とする。そして、新たなα(a+a)及びαを計算することによって、演算を継続可能とする。

【0179】
δ{(ab+c)+(c-a)},δ(c-a)の2つが0の場合、ab+c=0が漏洩する。上記の補正処理の処理シーケンスの第1のケース及び第2のケースでは、簡単のためδ{(ab+c)+(c-a)},δ(c-a)を同時に復元するように読めるが、まずδ(c-a)を復元して0である場合、以下を計算してδ(ab+c+a′)を復元する。

【0180】
JP2020056840A_000032t.gif

【0181】
このとき、δ(ab+c+a′)が0であれば、補正処理の処理シーケンスにおけるS274の第1のケースの場合の計算を行えばよい。これによって、δ{(ab+c)+(c-a)},δ(c-a)の2つが0であったとしてもab+c=0は漏洩しない。

【0182】
また、後述の第5実施形態の秘匿積和演算に示すようにδ(c-a),δ{(ab+c)+(c-a)}のどちらかが0であった場合、0となった値を新たな乱数で置き換え、0でない値の方にその乱数を加えてもよい。

【0183】
以上説明したように、本発明の第2実施形態の手法を用いて秘匿積和演算を行うことにより、秘密情報に0を含んでいても、効率よく秘匿演算を繰り返すことができる。

【0184】
なお、復元を行う場合、δ{(ab+c)+(c-a)}からδ(c-a)を秘匿減算すればδ(ab+c)が得られ、復元者はδを復元してその値を排除することにより、秘密情報による演算結果(ab+c)が得られる。この処理は復元装置によって実行されるので、復元を含む場合、後述する図11と同様のネットワーク構成となる。

【0185】
[第3実施形態]
第3実施形態は、上記問題点3に対応する。すなわち秘匿計算の検証を実現する機能である。以下は、簡単のため秘密情報a,b,c及び演算結果に0を含まない場合に検証を行う場合を例に説明する。

【0186】
図11を参照して、本実施形態に係る秘密分散システム310の構成を説明する。図11に示すように、秘密分散システム310は、3台の入力装置312A~312C、復元装置314、及び複数台のサーバ316~316n-1を含む。以下、入力装置312A~312Cについて共通する内容については「入力装置312」、サーバ316~316n-1について共通する内容については「サーバ316」とし、末尾の識別記号を省略して説明する場合もある。入力装置312、復元装置314、及びサーバ316は、ネットワークNに接続され、互いに通信可能とされる。なお、復元装置314が、第1排除部と、第1判定部とを含む検証復元装置の一例である。

【0187】
入力装置312は、秘密情報の入力者によって操作される装置である。入力装置312は、乱数を作用された所定の値を生成して、サーバ316に分散する。

【0188】
復元装置314は、秘密情報の復元者によって操作される装置である。復元装置314は、入力装置312、及びサーバ316によって公開されている値を収集して、秘匿積和演算の結果に不正がないかを検証する。

【0189】
サーバ316は、秘匿積和演算に係る計算などをする役割を持つ。

【0190】
次に、図12を参照して、本実施形態に係る復元装置314のハードウェア構成を説明する。なお、入力装置312、及びサーバ316については第2実施形態と同様の装置構成をとることができるため詳細な説明を省略する。

【0191】
図12に示すように、復元装置314は、CPU340、一時記憶領域としてのメモリ341、不揮発性の記憶部342を含む。また、復元装置314は、表示装置343、入力I/F344、及びネットワークNに接続されるネットワークI/F345を含む。CPU340、メモリ341、記憶部342、表示装置343、入力I/F344、及びネットワークI/F345は、バス346に接続される。

【0192】
記憶部342は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部342には、復号プログラム348が記憶される。復号プログラム348は、第1排除プロセス348aと、第1判定プロセス348bと、復元プロセス348cとを含む。CPU340は、記憶部342から復号プログラム348を読み出してからメモリ341に展開し、展開した復号プログラム348を実行する。CPU340が第1生成プログラム348の第1排除プロセス348aを実行することで、開示の技術の第1排除部として動作する。CPU340が第1生成プログラム348の第1判定プロセス348bを実行することで、開示の技術の第1判定部として動作する。CPU340が第1生成プログラム348の復元プロセス348cを実行することで、開示の技術の復元部として動作する。

【0193】
次に、図13~15を参照して、本実施形態に係る秘密分散システム310の作用を説明する。

【0194】
<分散3>
まず、秘密情報を各サーバに分散する処理について説明する。図13は、秘密分散システム310における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置312A~Cが持つ秘密情報をサーバ316に分散する。以下において、サーバ316は、分散の処理シーケンスの各処理に応じてn台の全てのサーバである全サーバS、及びサーバSのいずれかが対象であるものとして説明する。

【0195】
S310で、入力装置312Aは、乱数αi,0,…,αi,k-1(i=0,2)を生成する。

【0196】
S312で、入力装置312Aは、乱数α=Πj=0k-1αi,jを計算する。

【0197】
S314で、入力装置312Aは、乱数aを生成し、秘密情報aに対して以下を計算して計算結果を公開する。また、入力装置312Aは、aに対するハッシュ値ha1を公開する。

【0198】
JP2020056840A_000033t.gif

【0199】
S316で、入力装置312Aは、α0,j2,jをサーバSに送信する。

【0200】
S318で、入力装置312Bは、乱数βi,0,…,βi,k-1(i=0,2)を生成する。

【0201】
S320で、入力装置312Bは、乱数β=Πj=0k-1βi,jを計算する。

【0202】
S322で、入力装置312Bは、乱数bを生成し、秘密情報bに対して以下を計算して計算結果を公開する。また、入力装置312Bは、bに対するハッシュ値hb1を公開する。

【0203】
JP2020056840A_000034t.gif

【0204】
S324で、入力装置312Bは、β0,j2,jをサーバSに送信する。

【0205】
S326で、入力装置312Cは、乱数γi,0,…,γi,k-1(i=0,2)を生成する。

【0206】
S328で、入力装置312Cは、乱数γ=Πj=0k-1γi,jを計算する。

【0207】
S330で、入力装置312Cは、乱数cを生成し、秘密情報cに対して以下を計算して計算結果を公開する。また、入力装置312Cは、cに対するハッシュ値hc1を公開する。

【0208】
JP2020056840A_000035t.gif

【0209】
S332で、入力装置312Cは、γ0,j2,jをサーバSに送信する。

【0210】
以上の分散の処理シーケンスにより、サーバSは、以下を持つことになる。

【0211】
JP2020056840A_000036t.gif

【0212】
なお、入力装置312A、入力装置312B、及び入力装置312Cは、a,b,cを秘密分散してもよい。

【0213】
<秘匿積和演算3>
次に秘匿積和演算する処理について説明する。

【0214】
秘匿積和演算の前提として、分散処理は正しく行われているものとする。ここでは変換用乱数組として([μh,i)(h=1,…,必要個数)も持つものとする。

【0215】
以下において、c=c=c+c=0としてcに関する処理を省略すれば秘匿乗算になり、α(a+a)=αa=1としてaに関する処理を省略すれば秘匿加算になる。また、abとcの間の+を-にすれば秘匿減算となる。また以下の秘匿積和演算において、計算結果を新たなα(a+a),αなどとするが、β(b+b)またはγ(c+c)としてもよい。α2,i,α1,iについても同様である。

【0216】
図14は、秘密分散システム310における、秘匿積和演算の処理シーケンスを説明したものである。図14では、説明の便宜のため、サーバ316のうち、サーバSまたは全サーバSおいて秘匿積和演算の処理シーケンスが行われるものとして説明する。

【0217】
S340で、サーバSは、乱数δ0,i2,iを生成する。

【0218】
S342で、サーバSは、生成した乱数δ0,i2,iを用いて、以下を計算して計算結果を公開する。ただし、0となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。

【0219】
JP2020056840A_000037t.gif

【0220】
S344で、全サーバは、以下を計算する。

【0221】
JP2020056840A_000038t.gif

【0222】
S346で、サーバSは、以下を計算して復元し、復元したδ{(ab+c)+(c-a)},δ(ab+c)を公開する。

【0223】
JP2020056840A_000039t.gif

【0224】
S348は、演算を継続する場合の処理である。S348で、サーバSは、δ(ab+c),δ{(ab+c)+(c-a)を新たなαa,α(a+a)に設定し、新たなαa,α(a+a)に合わせて、δ0,i2,iを新たなα0,i2,iに設定してS340に戻る。

【0225】
<検証・復元3>
次に、検証処理について説明する。図15は、秘密分散システム310における検証の処理シーケンスを説明したものである。検証の処理シーケンスにおいて、入力装置312A、入力装置312B、及び入力装置312Cは、それぞれa,b,cを公開しているものとする。

【0226】
S360で、復元装置314は、サーバSからδ0,i2,iを収集する。

【0227】
S362で、復元装置314は、収集したδ0,i2,iの積δを計算し、積δを用いて以下を計算して公開する。

【0228】
JP2020056840A_000040t.gif

【0229】
なお、S362は、復元装置314における、復号プログラム348の第1排除プロセス338aに対応する。復元装置314のCPU340が、第1排除プロセス348aを実行することで、開示の技術における第1排除部の処理を行う。上記の計算が、秘密情報同士の演算結果に対して乱数を作用させて生成した第3の値δ{(ab+c)+(c-a)}とδ(ab+c)を用いて秘密情報(ab+c)と第4の乱数δに相当する値を排除し、判定を行うための第1の乱数同士の演算結果を得ることに対応する。

【0230】
S364で、復元装置314は、入力装置312A、入力装置312B、及び入力装置312Cが公開しているa,b,c及びそのハッシュ値を収集する。

【0231】
S366で、復元装置314は、公開されているa,b,cと、そのハッシュ値が一致するかを検証し、ハッシュ値が正しければS368へ移行し、正しくなければS374へ移行して不正検出とする。

【0232】
S368で、復元装置314は、公開されているa,b,cを用いてc-aを計算する。

【0233】
S370で、復元装置314は、公開されているa,b,cから計算されたc-aと、S362で計算されたc-aが等しいか検証し、計算結果が正しければS372へ移行し、正しくなければS374へ移行して不正検出とする。

【0234】
なお、S370は、復元装置314における、復号プログラム348の第1判定プロセス348bに対応する。復元装置314のCPU340が、第1判定プロセス348bを実行することで、開示の技術における第1判定部の処理を行う。

【0235】
S372で、復元装置314は、検証結果が正しい場合、S362で用いられたδ(ab+c)/δをab+cと判定する。

【0236】
S374で、検証結果が不正検出であるものとする。

【0237】
以上が、検証の処理シーケンスである。なお、a,b,cが秘密分散されている場合、S366に対応する処理として、各サーバでa,b,cの分散値を公開して、復元装置314でa,b,cを復元してもよい。

【0238】
また、演算が繰り返されている場合、S362において乱数による最終的な演算結果を復元し、S364で全乱数を収集して、その乱数を用いて同様の演算を構成し、S362の結果とS368の結果が一致するかを検証する。

【0239】
攻撃者が入力値や乱数を知らない場合、(c-a)が一致するように操作できないことが言える。よって、その計算に使用したδ(ab+c)/δは正しいといえる。

【0240】
また、検証処理は演算の最後でなく、任意の積和演算単位で検証することも可能である。

【0241】
また、本実施形態における検証の処理シーケンスは復元装置314が行うものとしたが、サーバSがδ0,i2,iを公開すればどの装置でも公開値から検証可能である。この場合、復元者は不正ができないこととなる。

【0242】
ただし、サーバSがδ0,i2,iを公開する場合、例えば入力者Aが攻撃者で、分散処理においてハッシュ値を公開したaと異なるa′を用いてa+a′を入力し、aを公開しているとすれば、S370における検証結果は不正となるが、S362においてδ(ab+c)/δは復元されているので、攻撃者のみ演算結果が正しいことを知ることができる。よって、S360、S362を以下S360′~S364′のように変形し、S370の結果が正しい場合に以下S371′を追加して処理するようにすれば、δ(ab+c)は秘匿されたままa+cが計算されるので、攻撃者のみ演算結果を知ることを防止できる。また、下記S360′~S364′における秘匿計算を秘匿積和演算の一環と考えれば、下記S360′~S364′における処理も検証されるため不正を行えば検証される。また、S374を復元装置314ではなく、サーバSがδ0,i,[μ,[μを公開すれば、公開の処理とできる。この対策は以降の実施形態においても適用できる。

【0243】
S360′では、サーバSは、(1/δ0,iμ7,i),(1/δ2,iμ8,i)を復元装置314に送信する。

【0244】
S362′では、復元装置314は、受信したその積(1/δμ),(1/δμ)を公開して、各サーバが計算した以下を収集する。

【0245】
JP2020056840A_000041t.gif

【0246】
S364′では、復元装置314は、収集した上記の計算結果を復元してその結果を公開する。

【0247】
S371′では、復元装置314は、S370の結果が正しいとき、δ0,i,[μ,[μを収集してS364′の結果を検算し、計算したδ(ab+c)/δをab+cとする。検算結果が一致しない場合、[a+cが一致しないサーバを不正とする。

【0248】
ただし、入力者が攻撃者の場合、以下のようにすれば不正検出されずに、偽の答えを復元者に得させることができる。例えば、ユーザCはc,cを知っており、a,bと独立であるので、cに関連する部分のみ正しくない処理をしてもcと一致させることが可能である。この対策は次の実施形態で示される。

【0249】
よって、本実施形態は入力者が不正をしない場合、すなわち攻撃者がk-1台までのサーバまたは入力を知らない外部攻撃者の場合に対して有効である。

【0250】
また、復元装置314は、第1排除部から得られる値から第1の秘密情報同士の演算結果を得る演算結果を得る復元部を含む秘匿演算装置として機能する。復元装置314は、上記、本実施形態の各処理シーケンスを経て、復元プロセス348cの実行によって、S372から得られる値を取得し、第1の秘密情報同士の演算結果(ab+c)を得る。

【0251】
以上説明したように、本発明の第3実施形態の手法を用いて秘匿積和演算を検証することにより、秘匿積和演算の不正を検出することができる。

【0252】
[第4実施形態]
第4実施形態は、第3実施形態では入力を知るユーザの不正は防げなかった点に着目し、本実施形態ではユーザの結託を含む不正を防止することができる手法を示す。

【0253】
第4実施形態の構成は上記図5の第2実施形態と同様の構成をとることができ、秘密分散システム410において、入力装置212を入力装置412に、サーバ216をサーバ416に置き換えた構成とすればよい。なお、サーバ416が分散装置の一例であり、秘密分散システム410が分散システムの一例である。

【0254】
秘密分散システム410において、不正の防止のためには、a,b,cを入力装置412だけで生成しないようにする。これによって、例えば、入力装置412Cを操作するユーザCはcを知らないため、Cに関する部分を不正にcに一致させられなくなる。また、本実施の形態は第3の実施の形態と同様に秘密情報に0は含まないが、第1の実施の形態に示す変換用乱数組([ε,εh,i)(h=1,…,12)が事前に配布されているものとする。

【0255】
次に、図16を参照して、本実施形態に係るサーバ416のハードウェア構成を説明する。なお、入力装置412については第2実施形態と同様のハードウェア構成をとることができるため、詳細な説明を省略する。

【0256】
図16に示すように、サーバ416は、CPU430、一時記憶領域としてのメモリ431、不揮発性の記憶部432を含む。また、サーバ416は、表示装置433、入力I/F434、及びネットワークNに接続されるネットワークI/F435を含む。CPU430、メモリ431、記憶部432、表示装置433、入力I/F434、及びネットワークI/F435は、バス436に接続される。

【0257】
記憶部432は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部432には、秘匿積和演算プログラム238、及び第4生成プログラム440が記憶される。CPU430は、記憶部432から第4生成プログラムを読み出してからメモリ431に展開し、展開した第4生成プログラム440を実行する。CPU430が第4生成プログラム440を実行することで、開示の技術の第4生成部として動作する。

【0258】
次に、図17を参照して、本実施形態に係る秘密分散システム410の作用を説明する。第4実施形態は分散の処理シーケンスが、第3実施形態と異なるため、分散の処理シーケンスについてのみ説明する。図17は、秘密分散システム410における分散の処理シーケンスを説明したものである。

【0259】
<分散4>
S410で、入力装置412Aは、k個の乱数α0,0,…,α0,k-1生成し、乱数α=Πj=0k-1α0,jを計算する。

【0260】
S412で、入力装置412Aは、k個の乱数の組(α1a,0,…,α1a,k-1),(β1a,0,…,β1a,k-1),(γ1a,0,…,γ1a,k-1)を生成し、乱数α1a=Πj=0k-1α1a,j1a=Πj=0k-1β1b,j1a=Πj=0k-1γ1a,jを計算する。

【0261】
S414で、入力装置412Aは、秘密情報aに対してαa=α×aを計算して公開する。

【0262】
S416で、入力装置412Aは、(α1a,i1a,i1a,i0,i)をサーバSに送信する。

【0263】
S418で、入力装置412Aは、乱数a1a,b1a,c1aを生成する。

【0264】
S420で、入力装置412Aは、S418で生成した乱数を用いて、以下を計算してα1a1a1a1a1a1aを公開する。また、入力装置412Aは、乱数a1a,b1a,c1aを保持し、そのハッシュ値ha1,a,hb1,a,hc1,aを公開する。

【0265】
JP2020056840A_000042t.gif

【0266】
S422で、入力装置412Bは、k個の乱数β0,0,…,β0,k-1を生成し、乱数β=Πj=0k-1β0,jを計算する。

【0267】
S424で、入力装置412Bは、k個の乱数の組(α1b,0,…,α1b,k-1),(β1b,0,…,β1b,k-1),(γ1b,0,…,γ1b,k-1)を生成し、乱数α1b=Πj=0k-1α1b,j1b=Πj=0k-1β1b,j1b=Πj=0k-1γ1b,jを計算する。

【0268】
S426で、入力装置412Bは、秘密情報bに対してβb=β×bを計算して公開する。

【0269】
S428で、入力装置412Bは、(α1b,i1b,i1b,i0,i)をサーバSに送信する。

【0270】
S430で、入力装置412Bは、ユーザBは乱数a1b,b1b,c1bを生成する。

【0271】
S432で、入力装置412Bは、S430で生成した乱数を用いて、以下を計算してα1b1b1b1b1b1bを公開する。また、ユーザBは乱数a1b,b1b,c1bを保持し、そのハッシュ値ha1,b,hb1,b,hc1,bを公開する。

【0272】
JP2020056840A_000043t.gif

【0273】
S434で、入力装置412Cは、k個の乱数γ0,0,…,γ0,k-1を生成し、乱数γ=Πj=0k-1γ0,jを計算する。

【0274】
S436で、入力装置412Cは、k個の乱数の組(α1c,0,…,α1c,k-1),(β1c,0,…,β1c,k-1),(γ1c,0,…,γ1c,k-1)を生成し、乱数α1c=Πj=0k-1α1c,j1c=Πj=0k-12β1c,j1c=Πj=0k-1γ1c,jを計算する。

【0275】
S438で、入力装置412Cは、ユーザCは秘密情報cに対してγc=γ×cを計算して公開する。

【0276】
S440で、入力装置412Cは、(α1c,i1c,i1c,i0,i)をサーバSに送信する。

【0277】
S442で、入力装置412Cは、乱数a1c,b1c,c1cを生成する。

【0278】
S444で、入力装置412Cは、S442で生成した乱数を用いて、以下を計算してα1c1c1c1c1c1c公開する。また、ユーザCは乱数a1c,b1c,c1cを保持し、そのハッシュ値ha1,c,hb1,c,hc1,cを公開する。

【0279】
JP2020056840A_000044t.gif

【0280】
以上が入力装置412A~Cでの処理である。以下からはサーバSでの処理である。

【0281】
S446で、サーバSは、乱数α1,i1,i1,iを生成する。

【0282】
S448で、サーバSは、S446で生成した乱数を用いて、以下を計算し、計算結果を公開する。ただし、0となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。

【0283】
JP2020056840A_000045t.gif
JP2020056840A_000046t.gif

【0284】
S450で、サーバSは、iに関する乗算により、以下を計算する。

【0285】
JP2020056840A_000047t.gif

【0286】
S452で、サーバSは、変換用乱数組[ε~[εを用いて以下を計算し、計算結果を公開する。

【0287】
JP2020056840A_000048t.gif

【0288】
なお、S450は、サーバSにおける、第4生成プログラム440に対応する。サーバSのCPU430が、第4生成プログラム440を実行することで、開示の技術における第4生成部の処理を行う。例えば計算の過程で、乱数aを、a1a,a1b,a1cを用いて生成する。a1a,a1b,a1cが、第1の秘密情報の生成者以外が生成した乱数の一例である。

【0289】
S454で、サーバSは、αを復元する。

【0290】
S456で、サーバSは、乱数α2,i2,i2,iを生成する。

【0291】
S458で、サーバSは、S456で生成した乱数を用いて、以下を計算し、計算結果を公開する。ただし、0となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。

【0292】
JP2020056840A_000049t.gif

【0293】
S460で、サーバSは、iに関する乗算により、以下を計算する。

【0294】
JP2020056840A_000050t.gif

【0295】
S462で、サーバSは、以下を計算し、計算結果を公開する。

【0296】
JP2020056840A_000051t.gif

【0297】
S464で、サーバSは、α(a+a),β(b+b),γ(c+c)を復元する。

【0298】
以上の分散の処理シーケンスにより、サーバSは、は変換用乱数組の他に以下を持つことになる。なお、入力装置412A、入力装置412B、及び入力装置412Cはそれぞれa1h,b1h,c1h(h=a,b,c)を秘密分散してもよい。

【0299】
JP2020056840A_000052t.gif

【0300】
以上が本実施形態の分散の処理シーケンスである。

【0301】
本実施の形態に対する秘匿積和演算は第3実施形態と同様であり、検証も第3実施形態と基本的には同じである。ただし、a1,a,a1,b,a1,c,b1,a,b1,b,b1,c,c1,a,c1,b,c1,cをハッシュ値で検証し、a,b,cをa=a1,a+a1,b+a1,c,b=b1,a+b1,b+b1,c,c=c1,a+c1,b+c1,cによって計算することだけが異なる。また、演算が繰り返された場合、全てのa1h,b1h,c1h(h=a,b,c)を集めて乱数による演算部分の正当性を検証する。

【0302】
安全性に関しては、入力者が攻撃者ではない場合、すなわち攻撃者がk-1台までのサーバまたは外部攻撃者である場合は第3の実施の形態と同様に安全であることが言える。それに加えて、本実施形態ではa,b,cを入力装置412Aを操作するユーザA、入力装置412Bを操作するユーザB、及び入力装置412Cを操作するユーザCの全員で生成するため、入力者が攻撃者となっても安全であることが以下のように言える。

【0303】
例えば、ユーザCが攻撃者である場合、ユーザCはcを知るが、c1を知らない。これはc1はユーザA,B,Cによって作られるためである。よって、ユーザCはCに関する部分を不正に操作しても、c1を知らないため最終結果を0にできない。また、ユーザCはq4-q6を操作できるが、c1を知らないため、他の値を調整できない。これはユーザ2者の結託に関しても言うことができ、(c1-a1b1)′-(c1-a1b1)=0であれば不正が行われていないことが言える。

【0304】
ただし、a,b,cの値を知る全員が結託すれば、(c1-a1b1)′-(c1-a1b1)=0としながら、異なる値を秘密情報による計算結果とすることができる。1回の秘匿積和演算において全員が結託することは想定しないが、秘匿積和演算を繰り返す場合、1つの積和演算を実行する全入力者が結託すれば、上記差分値を0にしたまま、不正な値を計算結果とすることができる。よって、秘匿積和演算を繰り返す場合、1回の積和演算を構成する入力者は全員結託することはないという前提を置く。また、秘匿積和演算を繰り返し、1つの積和演算に関する入力者全員の結託が考えられる場合、乱数a,b,cも漏洩する。よって、演算参加者が乱数a,b,cを知らないようにするため、各サーバが予め保有する変換用乱数組を用いる。このようにすると、分散4は以下のように非常に簡単にできる。

【0305】
[第4実施形態の変形例]
以下に、第4実施形態の変形例として、変換用乱数組([λ]),([ε]),([μ])を用いる例を示す。以下におけるa等はα1,iの乗算によって構成され、a等の値は誰も知らないので安全である。以下の[α(a+a)]などの生成において、a=0の場合でも利用できる手法も示す。

【0306】
図18は、変形例における分散の処理シーケンスを説明したものである。図18のシーケンスにおいて、以下のS470~S490の処理が行われる。なお、図18において各処理は簡略化して記載するものとする。

【0307】
<分散4′>
S470で、入力装置412Aは、乱数α2,j(j=0,…,k-1)を生成して乱数α=Πj=0k-1α2,jを計算し、秘密情報aに対してαa=α×aを計算して秘密分散する。

【0308】
S472で、入力装置412Aは、α2,j,[αa]をサーバSに送信する。

【0309】
S474で、入力装置412Bは、乱数β2,j(j=0,…,k-1)を生成して乱数β=Πj=0k-1β2,jを計算し、秘密情報bに対してβb=β×bを計算して秘密分散する。

【0310】
S476で、入力装置412Bは、β2,j,[βb]をサーバSに送信する。

【0311】
S478で、入力装置412Cは、乱数γ2,j(j=0,…,k-1)生成して乱数γ=Πj=0k-1γ2,jを計算し、秘密情報cに対してγc=γ×cを計算して秘密分散する。

【0312】
S480で、入力装置412Cは、γ2,j,[γc]をサーバSに送る。

【0313】
S482で、サーバSは乱数a1,i,b1,i,c1,iを定め、λ=α1,i1,i=β1,i1,i=γ1,i1,iと分解する。サーバSはa1,i,b1,i,c1,iのハッシュ値を公開する。

【0314】
S484で、サーバSは、[λ],[ε],[μ]を公開してλ=α,ε=β,μ=γを復元する。ただし、α=Πi=0k-1α1,i,a=Πi=0k-11,i=Πi=0k-1β1,i,b=Πi=0k-11,i=Πi=0k-1γ1,i,c=Πi=0k-11,iとする。

【0315】
S486で、サーバSは、乱数α2,i2,i2,iを生成し、以下を計算して公開する。

【0316】
JP2020056840A_000053t.gif

【0317】
S488で、サーバSは、以下を計算する。

【0318】
JP2020056840A_000054t.gif

【0319】
S490で、サーバSは、以下を計算して復元し、α(a+a),β(b+b),α(a+a)を公開する。

【0320】
JP2020056840A_000055t.gif

【0321】
以上説明したように、本発明の第4実施形態の手法を用いて秘密情報を分散することにより、秘密情報に0を含んでいても、ユーザの結託を含む不正を防止することができる。

【0322】
[第5実施形態]
第5実施形態は、秘密情報に0を含む場合の演算結果の検証法を示すものである。

【0323】
まず第5実施形態の手法の前提について説明する。第3、第4実施形態では秘密情報に乱数をかけたαaを公開するため、秘密情報が0、例えばa=0の場合αa=0となり、秘密情報が漏洩する。それに対して、第2実施形態では秘密情報に乱数をかけた値を生成しないため、秘密情報が0であっても漏洩しない。よって、その原理を生かして秘密情報に0を含む場合の検証を行う。

【0324】
また、本実施形態の分散では簡単のため、第3実施形態の分散と同様にユーザからの攻撃がない場合を考える。ユーザからの攻撃に対しても安全性を確保したい場合、下記におけるaなどの乱数を、第4実施形態の変形例のように入力者が直接生成せず、変換用乱数組を用いて生成すれば良い。この場合、入力装置側では生成されるα(a+a)のαもaも知ることができず、不正防止が可能となる。また、b,c,a,b,cについても同様である。また、本実施形態の秘匿積和演算では、サーバSは変換用乱数組として([μh,i)(h=1,…,必要個数)を持つものとする。

【0325】
第5実施形態の構成は上記図11の第3実施形態と同様の構成をとることができ、秘密分散システム510において、入力装置312を入力装置512に、復元装置314を復元装置514に、サーバ316をサーバ516に置き換えた構成とすればよい。なお、復元装置514が、第2排除部と、第2判定部とを含む検証復元装置の一例である。

【0326】
次に、図19を参照して、本実施形態に係る復元装置514のハードウェア構成を説明する。

【0327】
図19に示すように、復元装置514は、CPU540、一時記憶領域としてのメモリ541、不揮発性の記憶部542を含む。また、復元装置514は、表示装置543、入力I/F544、及びネットワークNに接続されるネットワークI/F545を含む。CPU540、メモリ541、記憶部542、表示装置543、入力I/F544、及びネットワークI/F545は、バス546に接続される。

【0328】
記憶部542は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部542には、復号プログラム548が記憶される。復号プログラム548は、第2排除プロセス548aと、第2判定プロセス548bと、復元プロセス548cとを含む。CPU540は、記憶部542から復号プログラム548を読み出してからメモリ541に展開し、展開した復号プログラム548を実行する。CPU540が復号プログラム548の第2排除プロセス548aを実行することで、開示の技術の第2排除部として動作する。CPU540が復号プログラム548の第2判定プロセス548bを実行することで、開示の技術の第2判定部として動作する。CPU540が復号プログラム548の復元プロセス548cを実行することで、開示の技術の復元部として動作する。

【0329】
なお、他の各装置のハードウェア構成は第3実施形態と同様のハードウェア構成をとることができるため、詳細な説明を省略する。

【0330】
次に、図20~23を参照して、本実施形態に係る秘密分散システム510の作用を説明する。

【0331】
<分散5>
まず、秘密情報を各サーバに分散する処理について説明する。図20は、秘密分散システム510における分散の処理シーケンスを説明したものである。分散の処理シーケンスでは、入力装置512A~Cが持つ秘密情報をサーバ516に分散する。以下において、サーバ516は、分散の処理シーケンスの各処理に応じてn台の全てのサーバである全サーバS、及びサーバSのいずれかが対象であるものとして説明する。

【0332】
S510で、入力装置512Aは、乱数αi,0,…,αi,k-1(i=1,..,4)を生成する。

【0333】
S512で、入力装置512Aは、乱数α=Πj=0k-1αi,jを計算する。

【0334】
S514で、入力装置512Aは、乱数a,aを生成し、秘密情報aに対して以下を計算して計算結果を公開する。また、入力装置512Aは、a,aに対するハッシュ値ha1,ha2を公開する。

【0335】
JP2020056840A_000056t.gif

【0336】
S516で、入力装置512Aは、α0,j,..,α4,jをサーバSに送信する。

【0337】
S518で、入力装置512Bは、乱数βi,0,…,βi,k-1(i=1,..,4)を生成する。

【0338】
S520で、入力装置512Bは、乱数β=Πj=0k-1βi,jを計算する。

【0339】
S522で、入力装置512Bは、乱数b,bを生成し、秘密情報bに対して以下を計算して計算結果を公開する。また、入力装置512Bは、b,bに対するハッシュ値hb1,hb2を公開する。

【0340】
JP2020056840A_000057t.gif

【0341】
S524で、入力装置512Bは、β0,j,..,β4,jをサーバSに送信する。

【0342】
S526で、入力装置512Cは、乱数γi,0,…,γi,k-1(i=1,..,4)を生成する。

【0343】
S528で、入力装置512Cは、乱数γ=Πj=0k-1γi,jを計算する。

【0344】
S530で、入力装置512Cは、乱数c,cを生成し、秘密情報cに対して以下を計算して計算結果を公開する。また、入力装置512Cは、c,cに対するハッシュ値hc1,hc2を公開する。

【0345】
JP2020056840A_000058t.gif

【0346】
S532で、入力装置512Cは、γ0,j,..,γ4,jをサーバSに送信する。

【0347】
以上の分散の処理シーケンスにより、サーバSは、以下を持つことになる。

【0348】
JP2020056840A_000059t.gif

【0349】
なお、入力装置512A、入力装置512B、及び入力装置512Cは、a,b,c,a,b,cを秘密分散してもよい。

【0350】
<秘匿積和演算5>
次に秘匿積和演算する処理について説明する。図21は、秘密分散システム510における、秘匿積和演算の処理シーケンスを説明したものである。図21では、説明の便宜のため、サーバ516のうち、サーバSまたは全サーバSおいて秘匿積和演算の処理シーケンスが行われるものとして説明する。

【0351】
S540で、サーバSは、乱数δ1,i2,i3,i4,iを生成する。

【0352】
S542で、サーバSは、生成した乱数δ1,i2,i3,i4,iを用いて、以下を計算して計算結果を公開する。ただし、0となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。

【0353】
JP2020056840A_000060t.gif

【0354】
S544で、全サーバは、以下を計算する。

【0355】
JP2020056840A_000061t.gif

【0356】
S546で、サーバSは、以下を計算して復元し、復元したδ{(ab+c)+(c-a)},δ(c-a),δ{(ab+c)+(c-a)},δ(c-a)を公開する。

【0357】
JP2020056840A_000062t.gif

【0358】
S548は、演算を継続する場合の処理である。S548で、サーバSは、δ(c-a),δ{(ab+c)+(c-a)},δ(c-a),δ{(ab+c)+(c-a)}が0でなければ、新たなα(a+a),α(a+a)に設定し、δ1,i2,i3,i4,iを新たなα1,i2,i3,i4,iに設定してS540に戻る。

【0359】
<補正処理5>
次に、S546の計算結果が0であった場合の補正処理について説明する。上述した図21の秘匿積和演算の処理シーケンスにおいて、δ{(ab+c)+(c-a)},δ(c-a)の少なくとも1つが0の場合、以下の補正処理を行う。図22は、秘密分散システム510における補正処理の処理シーケンスを説明したものである。補正処理の処理シーケンスは、サーバSで行われるものとして説明する。また、δ{(ab+c)+(c-a)}=0の場合を第1のケース、δ(c-a)=0の場合を第2のケースとして、第1のケース及び第2のケースのいずれか少なくとも一つに当てはまる場合の計算例を説明する。

【0360】
S560で、サーバSは、新たな乱数τ0,iとwを生成し、公開する。

【0361】
S562で、サーバSは、τw=Πτ0,iを計算する。また、サーバSは、wのハッシュ値を公開する。

【0362】
S564で、サーバSは、乱数τ1,i2,iを生成して、生成した乱数を用いて以下を計算する。第1のケースの場合、
JP2020056840A_000063t.gif
を計算する。第2のケースの場合、
JP2020056840A_000064t.gif
を計算する。

【0363】
S566で、サーバSは、S564の計算結果を公開する。ただし、0となる値が公開された場合、公開したサーバは不正処理があるとして処理を中断する。

【0364】
S568で、サーバSは公開された計算結果を用いて、iについて乗算し以下を計算する。第1のケースの場合、
JP2020056840A_000065t.gif
第2のケースの場合、
JP2020056840A_000066t.gif

【0365】
S570で、サーバSは、以下の計算を行い、新たな値の設定を行う。第1のケースの場合、
JP2020056840A_000067t.gif
と考えて、τwを新たなτ{(ab+c)+(c′-a)}とする。また、サーバSは以下を計算して復元し公開し、それらを新たなα(a+a)とし、τ1,i2,i=τ0,iを新たなα1,i2,iとして上記図21の秘匿積和演算の処理シーケンスのS540に戻る。

【0366】
JP2020056840A_000068t.gif

【0367】
第2のケースの場合、
JP2020056840A_000069t.gif
と考えて、τwを新たなτ(c´-a)とする。また、サーバSは以下を計算して復元し公開し、それらを新たなα(a+a)とし、τ1,i=τ0,i2,iを新たなα1,i2,iとして上記図21の秘匿積和演算の処理シーケンスのS540に戻る。ただし、c´=c+wとする。

【0368】
JP2020056840A_000070t.gif

【0369】
以上が補正処理の処理シーケンスである。なお、δ(c-a),δ{(ab+c)+(c-a)}が0の場合も同様である。

【0370】
<検証・復元5>
次に、検証処理について説明する。図23は、秘密分散システム510における検証の処理シーケンスを説明したものである。検証の処理シーケンスにおいて、入力装置512A、入力装置512B、及び入力装置512Cは、a,b,c,a,b,cを公開しているものとする。また、補正処理を行っている場合、wを生成したサーバはその値とハッシュ値を公開する。以降、wについてはc´=c+wよりc´に含まれるが、簡単のためc´もcとして表現する。

【0371】
S580で、復元装置514は、サーバSからδ2,i4,iを収集する。

【0372】
S582で、復元装置514は、収集したδ2,i4,iの積δを計算し、積δを用いて以下を計算して公開する。

【0373】
JP2020056840A_000071t.gif

【0374】
なお、S582は、復元装置514における、復号プログラム548の第2排除プロセス548aに対応する。復元装置514のCPU540が、第2排除プロセス548aを実行することで、開示の技術における第2排除部の処理を行う。上記の計算が、複数の第3の値δ{(ab+c)+(c-a)},δ{(ab+c)+(c-a)}から各々の第4の乱数δ2,δに相当する値を排除することに対応する。

【0375】
S584で、復元装置514は、入力装置512A、入力装置512B、及び入力装置512Cが公開しているa,b,c,a,b,c及びそのハッシュ値を収集する。

【0376】
S586で、復元装置514は、公開されているa,b,c,a,b,cと、そのハッシュ値が一致するかを検証し、ハッシュ値が正しければS588へ移行し、正しくなければS594へ移行して不正検出とする。なお、途中演算結果が0になっている場合、復元装置514は新たに定めたwを集めて公開し、そのハッシュ値を検証する。

【0377】
S588で、復元装置514は、公開されているa,b,c,a,b,cを用いて(c-a)-(c-a)を計算する。なお、途中演算結果が0になり補正した場合、c,cはc´,c´となる。

【0378】
S590で、復元装置514は、公開されているa,b,c,a,b,cから計算された(c-a)-(c-a)と、S582で復元値(つまり積δ)から計算された(c-a)-(c-a)が等しいか検証し、計算結果が正しければS590へ移行し、正しくなければS594へ移行して不正検出とする。

【0379】
なお、S590は、復元装置514における、復号プログラム548の第2判定プロセス548bに対応する。復元装置514のCPU540が、第2判定プロセス548bを実行することで、開示の技術における第2判定部の処理を行う。また、δ(c-a)=0で補正した場合におけるc´=c+wが第6の乱数に対応する。S582の計算結果である(c-a)-(c-a)が第1の乱数同士の演算結果に対応する。上述したようにここでのc,cはc´,c´となる。

【0380】
S592で、復元装置514は、検証結果が正しい場合、S582で用いられたδ{(ab+c)+(c-a)}/δから公開値による(c-a)を差し引いた値をab+cとする。

【0381】
S594で、検証結果が不正検出であるものとする。

【0382】
以上が、検証の処理シーケンスである。なお、a,b,c,a,b,cが秘密分散されている場合、S586に対応する処理として、各サーバでa,b,c,a,b,cの分散値を公開して、復元装置514でa,b,c,a,b,cを復元してもよい。

【0383】
また、演算が繰り返されている場合、S582において乱数による最終的な演算結果を計算し、S584で全乱数を収集して、その乱数を用いて同様の演算を構成し、S582で計算した結果とS588で計算した結果が一致するかを検証する。

【0384】
また、上記においてδ{(ab+c)+(c-a)}とδ{(ab+c)+(c-a)}は簡単のため同形式のものを用いたが、どちらも(ab+c)を含んでいれば、異なる形式の演算であっても、その差分が乱数のみになれば問題ない。

【0385】
また、第2実施形態と同様の変形を行えば、秘匿減算及び秘匿除算も実現できる。また、本実施の形態の安全性は第3実施形態と同様に秘密情報及び乱数を知らない攻撃者に対しては安全であることが言える。ただし、これも第3実施形態と同様に例えばユーザCはc,c,cを知るのでその間の関係を調整することによって不正ができる。よって、乱数a,b,c,a,b,cは入力装置の入力者が生成せず、第4実施形態に示したように分散4または分散4’のようにして生成すればよい。

【0386】
また、補正処理5においてδ{(ab+c)+(c-a)}やδ{(ab+c)+(c-a)}が補正されたとしても安全であることが言える。

【0387】
以上により、問題点1~3の全てを解決できる。

【0388】
また、復元装置514は、第2排除部から得られる値から第1の秘密情報同士の演算結果を得る演算結果を得る復元部を含む秘匿演算装置として機能する。復元装置514は、上記、本実施形態の各処理シーケンスを経て、復元プロセス548cの実行によって、S592から得られる値を取得し、第1の秘密情報同士の演算結果(ab+c)を得る。

【0389】
以上説明したように、本発明の第5実施形態の手法を用いて秘密情報を分散することにより、秘密情報に0を含んでいても、ユーザの結託を含む不正を防止することができる。また、また、第5実施形態の手法を用いて秘匿積和演算を行うことにより、秘密情報に0を含んでいても、効率よく秘匿演算を繰り返すことができる。また、第5実施形態の手法を用いて秘匿積和演算を検証することにより、秘匿積和演算の不正を検出することができる。

【0390】
[第6実施形態]
第6実施形態は、第1~第5実施形態で説明した提案手法を変形してブロックチェーンに応用する場合を示す。すなわち、値を登録する入力者が操作する入力装置と、その値を検証してブロックチェーンに公開する検証者が操作する検証装置と、ブロックチェーン装置と、ブロックチェーンに公開された値を確認する復元者が操作する復元装置からなるシステムを考える。入力装置は検証装置には登録する値を知らせるが、復元装置に対しては登録した値を秘匿したいものとする。ただし、ブロックチェーンでは公開性、及び検証性が重要なので、秘匿した登録値から合計値や各種統計値などの演算(以降、検証用演算と呼ぶ)を復元装置が実行でき、その演算結果を検証できるようにする。すなわち、登録値は1台のブロックチェーン装置に秘匿されて公開されるが、その登録値を用いた検証用演算は誰でも実行でき、その合計値や統計値などを知ることができ、かつその演算結果が正しいことを検証できることが大きな特徴である。

【0391】
図24を参照して、本実施形態に係る秘密分散システム610の構成を説明する。図24に示すように、秘密分散システム610は、入力装置6、復元装置614、ブロックチェーン装置616、及び検証装置618を含む。各装置はネットワークNに接続され、互いに通信可能とされる。なお、ブロックチェーン装置616が演算装置の一例であり、復元装置614が検証部を含む検証復元装置の一例であり、秘密分散システム610が秘匿演算検証復元システムの一例である。

【0392】
以降において、ブロックチェーン装置616をS、登録値を秘密情報と呼び、k=2の場合で説明する(kは任意に設定できるが、1台のサーバで演算を行う場合、k=2が最も効率的)。また、簡単のため実行する検証用演算を積和演算とし、登録値には0を含まず、演算結果も0を含まないとする。また以下では、秘密情報に対する演算と乱数に対する演算を同じ処理とするためにα(a+a),αaを用いる場合を示す。以下の例では入力者がa,b,cの値を発生毎に検証者に送り、検証者がそれらを確認した後、秘匿して公開する場合を示す。

【0393】
次に、図25を参照して、本実施形態に係る復元装置614のハードウェア構成を説明する。

【0394】
図25に示すように、復元装置614は、CPU640、一時記憶領域としてのメモリ641、不揮発性の記憶部642を含む。また、復元装置614は、表示装置643、入力I/F644、及びネットワークNに接続されるネットワークI/F645を含む。CPU640、メモリ641、記憶部642、表示装置643、入力I/F644、及びネットワークI/F645は、バス646に接続される。

【0395】
記憶部642は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部642には、検証復元プログラム648が記憶される。CPU640は、記憶部642から検証復元プログラム648を読み出してからメモリ641に展開し、展開した検証復元プログラム648を実行する。CPU640が検証復元プログラム648を実行することで、開示の技術の検証部として動作する。

【0396】
次に、図26を参照して、本実施形態に係るブロックチェーン装置616のハードウェア構成を説明する。

【0397】
図26に示すように、ブロックチェーン装置616は、CPU650、一時記憶領域としてのメモリ651、不揮発性の記憶部652を含む。また、ブロックチェーン装置616は、表示装置653、入力I/F654、及びネットワークNに接続されるネットワークI/F655を含む。CPU650、メモリ651、記憶部652、表示装置653、入力I/F654、及びネットワークI/F655は、バス656に接続される。

【0398】
記憶部652は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部652には、演算プログラム658が記憶される。CPU650は、記憶部652から演算プログラム658を読み出してからメモリ651に展開し、展開した演算プログラム658を実行する。CPU650が演算プログラム658を実行することで、開示の技術の演算部として動作する。

【0399】
次に、図27を参照して、本実施形態に係る検証装置618のハードウェア構成を説明する。

【0400】
図27に示すように、検証装置618は、CPU660、一時記憶領域としてのメモリ661、不揮発性の記憶部662を含む。また、検証装置618は、表示装置663、入力I/F664、及びネットワークNに接続されるネットワークI/F665を含む。CPU660、メモリ661、記憶部662、表示装置663、入力I/F664、及びネットワークI/F665は、バス666に接続される。

【0401】
記憶部662は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部662には、検証プログラム668が記憶される。CPU660は、記憶部662から検証プログラム668を読み出してからメモリ661に展開し、展開した検証プログラム668を実行する。

【0402】
なお、入力装置612は検証装置618と同様の構成をとることができるため詳細な説明を省略する。

【0403】
次に、図28、図29を参照して、本実施形態に係る秘密分散システム610の作用を説明する。

【0404】
<分散6=データ登録>
図28は、秘密分散システム610における分散(データ登録)、秘匿積和演算(検証用演算)の処理シーケンスを説明したものである。また、図29は、検証・復元処理(データ検証)の処理シーケンスを説明したものである。

【0405】
S610で、入力装置612は、各秘密情報a,b,cが発生する毎に安全な通信路を用いて検証装置618に送信する。

【0406】
検証装置618は、受信したa,b,cを確認し、問題なければ以下を行う。

【0407】
S612で、検証装置618は、秘密情報aに対して3個の乱数αを生成する。また、乱数aを生成し、以下の値を計算する。

【0408】
JP2020056840A_000072t.gif

【0409】
S614で、検証装置618は、S612の計算結果、及び、aに対するハッシュ値ha1をブロックチェーン装置Sに送信する。

【0410】
S616で、検証装置618は、秘密情報bに対して3個の乱数βを生成する。また、乱数bを生成し、以下の値を計算する。

【0411】
JP2020056840A_000073t.gif

【0412】
S618で、検証装置618は、S616の計算結果、及び、bに対するハッシュ値hb1をブロックチェーン装置Sに送信する。

【0413】
S620で、検証装置618は、秘密情報cに対して3個の乱数γを生成する。また、乱数cを生成し、以下の値を計算する。

【0414】
JP2020056840A_000074t.gif

【0415】
S622で、検証装置618は、S620の計算結果、及び、cに対するハッシュ値hc1をブロックチェーン装置Sに送信する。

【0416】
S624で、検証装置618は、変換用乱数組([εi,0)と([εi,1)(i=1,…,必要個数)を生成する。

【0417】
S626で、検証装置618は、([εi,1)に乱数μをかけて([εi,0),(μ[εi,1)をブロックチェーン装置Sに送信する。

【0418】
S628で、検証装置618は、乱数δを生成し、以下をブロックチェーン装置Sに送信する。

【0419】
JP2020056840A_000075t.gif

【0420】
S630で、ブロックチェーン装置Sは、検証装置618から送られてきた値を登録値として公開する。

【0421】
以上が分散の処理シーケンスである。

【0422】
<秘匿積和演算6=検証用演算>
S632で、ブロックチェーン装置Sは、以下を計算し計算結果を検証装置618に送信する。ただし、μ=μδ=μδ=μδとする。

【0423】
JP2020056840A_000076t.gif

【0424】
なお、S632は、ブロックチェーン装置Sにおける、演算プログラム658の処理に対応する。ブロックチェーン装置SのCPU650が、演算プログラム658を実行することで、開示の技術における演算部の処理を行う。秘匿された登録値であるδ/αβε等を用いて、登録値による検証用演算、つまり上記計算を行う。

【0425】
以上が秘匿積和演算の処理シーケンスである。

【0426】
<検証・復元6=データ検証>
図29は、秘密分散システム610における検証の処理シーケンスを説明したものである。秘密分散システム610は、演算を終了し検証を行う場合、以下の検証の処理シーケンスを実行する。

【0427】
S650で、検証装置618は、δ{(ab+c)+(a+c)},δ(ab+c)とa,b,cを公開する。

【0428】
S652で、復元装置614は、以下を計算する。

【0429】
JP2020056840A_000077t.gif

【0430】
S654で、復元装置614は、a,b,cがそのハッシュ値と一致するか検証し、ハッシュ値が正しければS656へ移行し、正しくなければS662へ移行して不正とする。

【0431】
S656で、復元装置614は、公開されているa,b,cを用いてa+cを計算する。

【0432】
S658で、復元装置614は、S656で計算されたa+cとS652で計算されたa+cが等しいか検証し、計算結果が等しく、正しければS660へ移行し、正しくなければS662へ移行して不正とする。

【0433】
なお、S658は、復元装置614における、検証復元プログラム648の処理に対応する。サーバSのCPU640が、検証復元プログラム648を実行することで、開示の技術における検証部の処理を行う。

【0434】
S660で、復元装置614は、(ab+c=δ(ab+c))/δを確認値とする。

【0435】
S662で、検証結果が不正であるものとする。

【0436】
以上が検証の処理シーケンスである。

【0437】
上記において、検証用演算を積和演算としたが、積和演算はb=1とすれば加算となり、c=0とすれば乗算となる。また、第2の実施の形態に示したように減算及び除算も可能である。さらに、積和演算の組み合わせにより任意の四則演算が構成できるので、任意の検証用演算が可能である。

【0438】
また、本実施形態の分散(データ登録)の時点で登録値は秘匿されて公開されるが、復元者は秘密情報に関して何の情報も得ることができない。また、秘匿積和演算(検証用演算)においても乱数δが秘匿されているので、演算は実行できるが秘密情報及び演算結果について何の情報も得ることはできない。また、δ(ab+c)が0になれば秘密情報が漏洩するが、秘密情報による演算結果に0を含まないとするので問題ない。演算結果に0を含む場合は、第5実施形態の秘匿計算を採用すればよい。よって、本実施形態の補正処理におけるδ{(ab+c)+(a+c)},δ(a+c)の更新についても情報は得られない。最後に、本実施形態の検証(データ検証)において検証装置618により乱数a,b,cが公開されることにより、復元された演算結果の正当性を検証できる。

【0439】
本実施の形態の特徴は誰でも秘匿計算及びその検証処理が実行できる点である。すなわち、前実施形態までは秘匿積和演算に参加できるメンバーは分散時に種々の値を配布されたk台のサーバに限定され、それ以外のメンバーは演算結果の正しさを確認できるが、自ら検証処理を行えなかった。本実施の形態によりk台のサーバに秘匿演算を依頼しなくても、全ての値が公開されるため誰でも検証処理できる。また、最終結果に用いられた乱数が公開されることにより、最終結果は知ることができるが、途中結果を復元するためのδが公開されないため、入力値及び途中の演算結果に関する情報は得られないというものである。

【0440】
ただし、検証者は全入力を知っており、乱数も自ら設定するため、不正することが可能であるが、検証者が信頼できるとする場合はこのままで問題はない。信頼できるとしない場合は、第4実施形態と同様に乱数を検証者だけが生成しないようにすればよい。例えば、分散(データ登録)のS612~622の処理とS628の処理の代わりに以下の生成処理を入力装置612が行い検証装置618に送信する。

【0441】
JP2020056840A_000078t.gif

【0442】
検証装置618は受信した値を秘密分散して、片側の分散値にμをかけた以下の値をブロックチェーン装置Sに送る。

【0443】
JP2020056840A_000079t.gif

【0444】
このとき、検証装置618ではS610で送られたa,b,cの値からαを知ることができるが、それ以上の情報を知ることができない。そのため、乱数の演算結果の差分が0となるように公開値を調整できない。また、入力装置612が偽の値を送っている場合、検証装置618はS610によって知る秘密情報による検証結果の正当性をS654において直接確認できる。また、入力装置612が送る値に入力装置612のデジタル署名をつけて送らせ、それを検証した後上記処理を行えば、入力装置612が偽の値を送っていることを証明できる。またこれに対して検証装置のデジタル署名を入力装置が得れば、検証装置618による偽の値の登録を防ぐために利用できる。

【0445】
また、第4実施形態に示したように入力の乱数a,b,cを他者と協力して生成してもよい。例えば、入力装置と検証装置、または検証装置と復元装置などの組合せで、入力装置または検証装置が設定したaをその生成者が知らないa"=a+a′に変更してもよい。

【0446】
また、上記分散(データ登録)ではα(a+a),αaの3つの入力を生成したが、乱数の演算を秘密情報の演算と同じ形にしなくてよい場合は、第3実施形態のようにα(a+a),αaまたは第5の実施の形態のように2組のα(a+a),αとして、各々同じ形式で更新して行ってもよい。

【0447】
以上説明したように、本発明の第6実施形態の手法を用いて秘密情報を分散することにより、ブロックチェーンのような公開性が重視される応用に対しても、上述した第1~第5実施形態と同様の秘匿計算を適用することができる。

【0448】
なお、上記各実施形態でCPUがソフトウェア(プログラム)を実行することにより実行した各種処理を、CPU以外の各種のプロセッサが実行してもよい。この場合のプロセッサとしては、FPGA(Field-Programmable Gate Array)等の製造後に回路構成を変更可能なPLD(Programmable Logic Device)、及びASIC(Application Specific Integrated Circuit)等の特定の処理を実行させるために専用に設計された回路構成を有するプロセッサである専用電気回路等が例示される。また、各種処理を、これらの各種のプロセッサのうちの1つで実行してもよいし、同種又は異種の2つ以上のプロセッサの組み合わせ(例えば、複数のFPGA、及びCPUとFPGAとの組み合わせ等)で実行してもよい。また、これらの各種のプロセッサのハードウェア的な構造は、より具体的には、半導体素子等の回路素子を組み合わせた電気回路である。

【0449】
また、上記各実施形態では、各種プログラムが記憶部に予め記憶(インストール)されている態様を説明したが、これに限定されない。各種プログラムは、CD-ROM(Compact Disc Read Only Memory)、DVD-ROM(Digital Versatile Disc Read Only Memory)、及びUSB(Universal Serial Bus)メモリ等の記録媒体に記録された形態で提供されてもよい。また、各種プログラムは、ネットワークを介して外部装置からダウンロードされる形態としてもよい。
【符号の説明】
【0450】
10、210、310、410、510、610 秘密分散システム
12、212、312、412、512、612 入力装置
14、314、414、514、614 復元装置
16、216、316、416、516 サーバ
616 ブロックチェーン装置
618 検証装置
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23
【図25】
24
【図26】
25
【図27】
26
【図28】
27
【図29】
28