(57)【特許請求の範囲】
【請求項１】
少なくとも２つの固定小数点数の各固定小数点数を加法型の秘密分散法を用いて分散することによって、前記少なくとも２つの固定小数点数から複数の分散データ値と、複数の分散符号値と、複数の分散キャリー値と、を生成する分散情報生成装置と、
少なくとも２台の秘密計算装置を含む秘密計算装置群と、
を備える秘密計算システムであって、
前記秘密計算装置群は、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張手段と、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記秘密桁拡張手段により生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算手段と、
を有し、
前記固定小数点数のデータ値は、前記固定小数点数に、下位からの固定小数点までの桁数でべき乗した２を積算した値であり、前記固定小数点数の符号値は、２の補数表現を用いた最上位桁のビットであり、
前記少なくとも２台の秘密計算装置間での秘密を保持したデータ交換は、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記少なくとも２台の秘密計算装置に分散し、分散された数を用いて実行される秘密計算システム。
【請求項２】
前記分散情報生成装置は、
第１固定小数点数と第２固定小数点数とを含む２つの固定小数点数から、前記固定小数点数のデータ値を加法型の秘密分散法を用いて分散した分散データ値と、前記固定小数点数の符号を前記加法型の秘密分散法を用いて分散した分散符号値と、前記データ値を分散した際に発生したキャリー値を、前記加法型の秘密分散法を用いて分散した分散キャリー値と、をそれぞれ生成する分散情報生成手段を有し、
前記秘密桁拡張手段は、前記第１固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記第２固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、
前記秘密乗算手段は、前記第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値と、前記第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを用いて、前記第１拡張固定小数点数と前記第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする、
請求項１に記載の秘密計算システム。
【請求項３】
前記秘密計算装置群は、それぞれ分散された値を記憶する少なくとも第１秘密計算装置と第２秘密計算装置とを備え、
前記秘密桁拡張手段は、
１桁の２つのランダム数と前記ランダム数の積とを、加法型の秘密分散法を用いて前記第１秘密計算装置と前記第２秘密計算装置とに分散するランダム数分散手段と、
前記第１秘密計算装置において、前記固定小数点数の第１分散データ値の最上位桁の値と、第１分散符号値と、第１分散キャリー値とから、（最上位＋１）桁の第１分散データ値を算出し、前記第２秘密計算装置において、前記固定小数点数の第２分散データ値の最上位桁の値と、第２分散符号値と、第２分散キャリー値とから、（最上位＋１）桁の第２分散データ値を算出する拡張桁データ生成手段と、
算出された（最上位＋１）桁の第１分散データ値および第２分散データ値のそれぞれを、前記第１秘密計算装置と前記第２秘密計算装置とに分散する拡張桁データ分散手段と、
前記分散された（最上位＋１）桁の第１分散データ値および第２分散データ値と、最上位桁の分散キャリー値と、前記２つのランダム数および前記ランダム数の積の分散ランダム数とを用いて、前記第１秘密計算装置と前記第２秘密計算装置とが協働して、（最上位＋１）桁の第１分散キャリー値と第２分散キャリー値とを生成する拡張桁キャリー生成手段と、
算出された（最上位＋１）桁の第１分散キャリー値および第２分散キャリー値のそれぞれを、前記第１秘密計算装置と前記第２秘密計算装置とに分散する拡張桁キャリー分散手段と、
前記拡張桁データ生成手段による上位桁の分散データ値の算出と、前記拡張桁データ分散手段による上位桁の分散データ値の分散と、前記拡張桁キャリー生成手段による上位桁の分散キャリー値の算出と、前記拡張桁キャリー分散手段による上位桁の分散キャリー値の分散とを上位桁に向かって繰り返し、算出された拡張桁数の第１分散データ値を前記固定小数点数の第１分散データ値の上位に追加して前記拡張固定小数点数の第１拡張分散データ値とし、算出された拡張最上位桁の拡張分散キャリー値を前記拡張固定小数点数の第１拡張分散キャリー値とし、算出された拡張桁数の第２分散データ値を前記固定小数点数の第２分散データ値の上位に追加して前記拡張固定小数点数の第２拡張分散データ値とし、算出された拡張最上位桁の拡張分散キャリー値を前記拡張固定小数点数の第２拡張分散キャリー値とする、拡張固定小数点数生成手段と、
を有し、
前記第１固定小数点数および前記第２固定小数点数のそれぞれに対して、前記第１拡張分散データ値と前記第２拡張分散データ値、および、第１拡張分散キャリー値と第２拡張分散キャリー値、を生成する、請求項２に記載の秘密計算システム。
【請求項４】
前記秘密計算装置群は、それぞれ分散された値を記憶する少なくとも第１秘密計算装置と第２秘密計算装置とを備え、
前記秘密乗算手段は、
拡張固定小数点数と同じ桁の２つのランダム数と前記ランダム数の積とを、加法型の秘密分散法を用いて前記第１秘密計算装置と前記第２秘密計算装置とに分散するランダム数分散手段と、
前記第１拡張固定小数点数および前記第２拡張固定小数点数の拡張分散データ値と、前記２つのランダム数および前記ランダム数の積の分散ランダム数とを用いて、前記第１秘密計算装置と前記第２秘密計算装置とが協働して秘密を保持しながら秘密乗算を実行し、前記拡張乗算結果の拡張分散データ値を算出する拡張乗算手段と、
前記拡張乗算結果の拡張分散データ値の桁を調整して、前記乗算結果の分散データ値を生成する桁調整手段と、
を有する請求項２または３に記載の秘密計算システム。
【請求項５】
前記秘密乗算手段は、
前記拡張乗算結果の拡張分散データ値の下位桁を切除する下位桁切除手段と、
前記拡張乗算結果の分散符号値を抽出する符号抽出手段と、
前記拡張乗算結果の分散キャリー値を抽出するキャリー抽出手段と、
を有する請求項１乃至４のいずれか１項に記載の秘密計算システム。
【請求項６】
前記分散情報生成装置が生成した前記分散情報を記憶するための記憶装置をさらに備える、請求項１乃至５のいずれか１項に記載の秘密計算システム。
【請求項７】
少なくとも２つの固定小数点数の各固定小数点数を加法型の秘密分散法を用いて分散することによって、前記少なくとも２つの固定小数点数から複数の分散データ値と、複数の分散符号値と、複数の分散キャリー値と、を生成する分散情報生成ステップと、
少なくとも２台の秘密計算装置が、前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張ステップと、
前記少なくとも２台の秘密計算装置が、前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記秘密桁拡張ステップにおいて生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算ステップと、
を含み、
前記固定小数点数のデータ値は、前記固定小数点数に、下位からの固定小数点までの桁数でべき乗した２を積算した値であり、前記固定小数点数の符号値は、２の補数表現を用いた最上位桁のビットであり、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換は、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記少なくとも２台の秘密計算装置に分散し、分散された数を用いて実行される秘密計算システムの秘密計算方法。
【請求項８】
請求項１に記載の秘密計算システムにおける秘密計算装置であって、
前記分散情報生成装置が前記少なくとも２つの固定小数点数から生成した前記複数の分散データ値と、前記複数の分散符号値と、前記複数の分散キャリー値と、を記憶する分散情報記憶手段と、
前記秘密計算装置群に含まれる他の秘密計算装置との間で秘密を保持したデータ交換をするために用いられる、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とから加法型の秘密分散法を用いて分散された値を共有するランダム値共有手段と、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張手段と、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記秘密桁拡張手段により生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算手段と、
を備える秘密計算装置。
【請求項９】
請求項１に記載の秘密計算システムにおける秘密計算装置の秘密計算プログラムであって、
前記分散情報生成装置が前記少なくとも２つの固定小数点数から生成した前記複数の分散データ値と、前記複数の分散符号値と、前記複数の分散キャリー値と、を分散情報記憶部に記憶する分散情報記憶ステップと、
前記秘密計算装置群に含まれる他の秘密計算装置との間で秘密を保持したデータ交換をするために用いられる、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とから加法型の秘密分散法を用いて分散された値を共有するランダム値共有ステップと、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張ステップと、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記秘密桁拡張ステップにおいて生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算ステップと、
をコンピュータに実行させる秘密計算装置の秘密計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算システム、秘密計算方法、秘密計算装置、分散情報生成装置およびそれらの方法とプログラムに関する。
【背景技術】
【０００２】
秘密計算法は、関連する主体に対して計算過程と結果を秘匿することができる技術である。データをクラウドのような第３者が管理する複数サーバに分散して保管することで、データに対してあらゆる演算を実行することができる。第３者には、データ、計算過程、計算結果を知られることがないため、個人情報のような機微な情報に対する分析処理をアウトソースするために用いることができる。秘密計算法は、任意の計算を実行するための基本処理の方法が知られており、任意の計算を実行することができる。【０００３】
上記技術分野において、データがShamir(k,n)法を用いて分散されていることを前提とした手法（非特許文献２、非特許文献３等に記載）が代表的である。非特許文献２には、加減算と乗算を実行するための秘密計算法が記載されており、乗算では２ラウンドの通信を必要とする。また、非特許文献３には、乗算を１ラウンドの通信のみで実行可能な方式が提案されている。【０００４】
さらに、非特許文献４には、k桁の分散されている数[a]をmビット右シフトする分散プロトコルTrancPr([a],k,m)と、この分散プロトコルTrancPr([a],k,m)を用い、k桁で小数点以下fビットの数[a]と[b]とを秘密乗算する乗算プロコルFPMul([a],[b],k,f)とが記載されている。ここで、FPMul([a],[b],k,f)の計算手順は、(1)[c]←[a]*[b]、(2)[d]←TrancPr([c],2k,f)で表わされる。また、分散プロトコルTrancPr([a],k,m)の手順には、ランダムな０か１を分散するアルゴリズムと、ランダムな１ビットの情報を参加者間で共有するためのプロトコルPRandBit()と、指定されたxビット長の乱数を参加者間で共有するためのプロトコルPRandInt()と、が用いられる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Adi Shamir, “How to Share a Secret, ”Commun. ACM 22 (11), pp.612-613, 1979.
【非特許文献２】Michael Ben-Or, Shafi Goldwasser , Avi Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract),” Proceedings of the 20 th Annual ACM Symposium on Theory of Computing, 1988.
【非特許文献３】Rosario Gennaro, Michael O. Rabin, Tal Rabin, “Simplified VSS and Fast-track multiparty Computations with Applications to Threshold Cryptography,” PODC 1998: pp101-111
【非特許文献４】Octavian Catrina and Amitabh Saxena, “Secure Computation With Fixed-Point Numbers,” Financial Cryptography 2010: pp35-50
【非特許文献５】Ivan Dangard, Matthias Fitzi, Eike Kilts, Jesper Buus Nielsen, Tomas Toft, “Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation,” TCC 2006: pp285-304
【非特許文献６】Donald Beaver, “Efficient Multiparty Protocols Using Circuit Randomization，” CRYPTO '91, LNCS 576, pp.420-432, 1992.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献４に記載の技術では、通信量が非常に大きい。例えば、PRandBit()やPRandInt()は入力される値に依存しないため、乗算を実行する前の段階で実行できるが、PRandBit()は多量の通信を要する。非特許文献５を参照すると、(2,3)しきい値法を用いる場合でも、１ビット辺り数百ビットの通信を要する。つまり、ｍビットの固定小数点数に関する一度の乗算について、(数百*m)ビットの通信が前処理にかかることになる。このような前処理も含めて、全体の通信量を抑えた方式が望ましい。【０００７】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明に係る秘密計算システムは、
少なくとも２つの固定小数点数の各固定小数点数を加法型の秘密分散法を用いて分散することによって、前記少なくとも２つの固定小数点数から複数の分散データ値と、複数の分散符号値と、複数の分散キャリー値と、を生成する分散情報生成装置と、
少なくとも２台の秘密計算装置を含む秘密計算装置群と、
を備える秘密計算システムであって、
前記秘密計算装置群は、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張手段と、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記秘密桁拡張手段により生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算手段と、
を有し、
前記固定小数点数のデータ値は、前記固定小数点数に、下位からの固定小数点までの桁数でべき乗した２を積算した値であり、前記固定小数点数の符号値は、２の補数表現を用いた最上位桁のビットであり、
前記少なくとも２台の秘密計算装置間での秘密を保持したデータ交換は、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記少なくとも２台の秘密計算装置に分散し、分散された数を用いて実行される。
【０００９】
上記目的を達成するため、本発明に係る秘密計算システムの秘密計算方法は、
少なくとも２つの固定小数点数の各固定小数点数を加法型の秘密分散法を用いて分散することによって、前記少なくとも２つの固定小数点数から複数の分散データ値と、複数の分散符号値と、複数の分散キャリー値と、を生成する分散情報生成ステップと、
少なくとも２台の秘密計算装置が、前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張ステップと、
前記少なくとも２台の秘密計算装置が、前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換をしながら、前記秘密桁拡張ステップにおいて生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算ステップと、
を含み、
前記固定小数点数のデータ値は、前記固定小数点数に、下位からの固定小数点までの桁数でべき乗した２を積算した値であり、前記固定小数点数の符号値は、２の補数表現を用いた最上位桁のビットであり、
前記少なくとも２台の秘密計算装置間で秘密を保持したデータ交換は、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記少なくとも２台の秘密計算装置に分散し、分散された数を用いて実行される。
【００１２】
上記目的を達成するため、本発明に係る秘密計算装置は、
上記の秘密計算システムにおける秘密計算装置であって、
前記分散情報生成装置が前記少なくとも２つの固定小数点数から生成した前記複数の分散データ値と、前記複数の分散符号値と、前記複数の分散キャリー値と、を記憶する分散情報記憶手段と、
前記秘密計算装置群に含まれる他の秘密計算装置との間で秘密を保持したデータ交換をするために用いられる、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とから加法型の秘密分散法を用いて分散された値を共有するランダム値共有手段と、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張手段と、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記秘密桁拡張手段により生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算手段と、
を備える。
【００１３】
上記目的を達成するため、本発明に係る秘密計算装置の秘密計算プログラムは、
上記の秘密計算システムにおける秘密計算装置の秘密計算プログラムであって、
前記分散情報生成装置が前記少なくとも２つの固定小数点数から生成した前記複数の分散データ値と、前記複数の分散符号値と、前記複数の分散キャリー値と、を分散情報記憶部に記憶する分散情報記憶ステップと、
前記秘密計算装置群に含まれる他の秘密計算装置との間で秘密を保持したデータ交換をするために用いられる、前記データ値と同じ桁の少なくとも２つのランダム数と該ランダム数の積とから加法型の秘密分散法を用いて分散された値を共有するランダム値共有ステップと、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記少なくとも２つの固定小数点数の前記複数の分散データ値と前記複数の分散符号値と前記複数の分散キャリー値とを用いて桁数を拡張することによって、複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とからなる少なくとも２つの拡張固定小数点数を生成する秘密桁拡張ステップと、
前記他の秘密計算装置との間で秘密を保持したデータ交換をしながら、前記秘密桁拡張ステップにおいて生成された前記少なくとも２つの拡張固定小数点数を乗算した拡張乗算結果の複数の拡張分散データ値と複数の拡張分散符号値と複数の拡張分散キャリー値とを生成し、前記拡張乗算結果の前記複数の拡張分散データ値の桁数を調整することによって、秘密乗算結果の複数の分散値を計算する秘密乗算ステップと、
をコンピュータに実行させる。
【発明の効果】
【００１４】
本発明によれば、被計算値や計算結果や計算途中の値を知ることができない秘密乗算を、全体の通信量を抑えて実行することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１実施形態に係る秘密計算システムの構成を示すブロック図である。
【図２】本発明の第２実施形態に係る秘密計算システムの構成を示すブロック図である。
【図３】本発明の第２実施形態に係る秘密計算システムにおける分散情報生成装置の機能構成を示すブロック図である。
【図４】本発明の第２実施形態に係る秘密計算システムにおける秘密計算装置の機能構成を示すブロック図である。
【図５】本発明の第２実施形態に係る分散情報生成装置のハードウェア構成を示すブロック図である。
【図６】本発明の第２実施形態に係る分散情報生成装置の分散情報生成処理の手順を示すフローチャートである。
【図７】本発明の第２実施形態に係る秘密計算装置のハードウェア構成を示すブロック図である。
【図８】本発明の第２実施形態に係る秘密計算装置群による秘密乗算処理の手順を示すフローチャートである。
【図９Ａ】本発明の第２実施形態に係る各秘密計算装置の法拡大（桁拡大）における秘密計算処理の手順を示すフローチャートである。
【図９Ｂ】本発明の第２実施形態に係る各秘密計算装置の乗算における秘密計算処理の手順を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。
【００１７】
［第１実施形態］
本発明の第１実施形態としての秘密計算システム１００について、図１を用いて説明する。秘密計算システム１００は、分散情報を用いて、秘密を保持しながら固定小数点数の秘密計算を行なうシステムである。
【００１８】
図１に示すように、秘密計算システム１００は、分散情報生成装置１０１と、少なくとも２台の秘密計算装置１０２１〜１０２ｎを含む秘密計算装置群１０２と、を含む。分散情報生成装置１０１は、少なくとも２つの固定小数点数から、各固定小数点数を加法型の秘密分散法を用いて分散した分散データ値と、分散符号値と、分散キャリー値と、を生成する。秘密計算装置群１０２は、秘密桁拡張部１２１と、秘密乗算部１２２と、を有する。
【００１９】
秘密桁拡張部１２１は、各固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を、秘密を保持しながら生成する。秘密乗算部１２２は、分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする。
【００２０】
本実施形態によれば、各固定小数点数の分散データ値と分散符号値と分散キャリー値とを生成して、分散データ値の秘密乗算と分散キャリー値の秘密計算とを独立させたので、被計算値や計算結果や計算途中の値を知ることができない秘密乗算を、全体の通信量を抑えて実行することができる。
【００２１】
［第２実施形態］
次に、本発明の第２実施形態に係る秘密計算システムについて説明する。本実施形態に係る秘密計算システムは、ネットワークを介して接続された、固定小数点数を分散する分散情報を生成する分散情報生成装置と、分散情報を用いて秘密を保持しながら固定小数点数の秘密計算を行なう少なくとも２つの秘密計算装置からなる秘密計算装置群と、を備える。
【００２２】
分散情報生成装置は、少なくとも２つの固定小数点数から、各固定小数点数を加法型の秘密分散法を用いて分散した分散データ値と、分散符号値と、分散キャリー値と、を生成する。本実施形態では、加法型の秘密分散法として、秘密計算法が利用可能な加法型(2,2)法を用いるが、他の加法型(k,n)法や加法型(k,n)法に基づく秘密計算法であってもよい。秘密計算装置群は、少なくとも２つの秘密計算装置との間でのデータの秘密交換を伴って桁拡張処理および乗算処理を実行する。ここで、データの秘密交換は、データと同じ桁の少なくとも２つのランダム数とランダム数の積とを、加法型の秘密分散法を用いて少なくとも２つの秘密計算装置に分散し、分散された数を用いて実行される。
【００２３】
また、秘密計算装置群は、各固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を、秘密を保持しながら生成し、分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする。すなわち、秘密乗算結果の分散値を得るため、拡張乗算結果に対して、拡張分散データ値の下位桁を切除し、分散符号値を抽出し、分散キャリー値を抽出する。
【００２４】
なお、以下の説明において、x[1],x[2],x[i],x[n]などは、数値ｘの構成要素ｉへの分散値を表わし、x{1},x{k},x{j}などは、数値ｘの桁ｊの値（２値）を表わしている。また、+は加算、*は乗算を表し、^はべき乗算を表し、a mod b はaをbで割った余り、a||bはaとbのビット連結を表わす。
【００２５】
《前提技術》
まず、本実施形態の前提となる技術の説明を行う。前提技術として、秘密分散法と、秘密計算法について説明する。秘密分散法は、秘密計算法において計算対象となるデータをシステムに入力するために利用される。
【００２６】
（秘密分散法について）
秘密分散法とは、秘密情報から複数の分散情報を生成する技術である。分散情報は定められた組み合わせからは秘密情報を復元できるが、それ以外の組み合わせからは秘密情報が復元できないように作られる。定められた組み合わせには様々な構造をとることができ、その構造はアクセス構造と呼ばれる。ここでは、代表的なアクセス構造としてしきい値型アクセス構造について説明する。しきい値型アクセス構造は、生成される分散情報の数：nと、しきい値：kの２つのパラメータで表すことができる。これはk個以上の分散情報からは秘密情報が復元できるがk個未満の分散情報からは秘密情報が復元できないというものである。以降、分散情報の数がnであり、しきい値がkのしきい値型アクセス構造の秘密分散法を(k,n)法と呼ぶ。
【００２７】
(k,n)法としては、Shamirによって提案された方法（［非特許文献１］に記載）が代表的である。本明細書では、この方法をShamir(k,n)法と呼ぶ。また、(n,n)法として基本的な方法として、mビットの値xを分散するため、mビットのランダムな値r[2]、…、r[n]を生成し、v[1]=(x+r[2]+ … +r[n])mod2^m、v[2]=r[2]、…、v[n]=r[n]を分散情報とする方法が知られている。全ての分散情報が揃うと、v[1]に加算された全てのランダムな値を取り除くことができ、値xを復元することができる。このように、各分散情報の生成処理が乱数の生成を除くとmod2^m上の加減算のみで構成されているような方法を、2^m上の加法型(n,n)法とする。2^mは法として何を用いるかによって変化する。
【００２８】
同様に、各分散情報の生成処理が、乱数の生成を除くとmod2^m上の加減算のみで構成されている、(k(＜n),n)法も知られている。例として、mビットの値を分散する(2,3)法を、以下に示す。
【００２９】
入力値:xとした場合の分散処理は、以下の処理で実現される。
(1) r1+r2+r3=0 mod2^mとなるような、r1、r2、r3をランダムに生成する。
(2) x[1]=(r1,r3-x)、x[2]=(r2,r1-w)、x[3]=(r3,r2-w)とし、x[1]、x[2]、x[3]を３つのシェア（分散値、分割値）として出力する。
【００３０】
以上の方法によって分散された値は、２つ以上の分散情報からxを復元できる。このような方法を、一般に加法型(k,n)法と呼ぶことにする。
【００３１】
（秘密計算法について）
秘密分散法によって分散されたデータに関する計算を実行することができる技術は、秘密計算法と呼ばれる。秘密計算法によれば、秘密分散法によって複数のサーバに分散して保管されたデータ群に対する演算をデータの復元を伴うことなく実行できる。秘密計算法を用いれば、複数のサーバにデータを分散して登録し、登録したデータに関する任意の演算が実行可能である。計算対象のデータを複数台のサーバに分散して保管し、その解析を秘密計算法で行うことによって、サーバにも解析対象データと解析結果を知られることなく様々な分析を実行することができる。なお、秘密計算法によって実行された演算の結果は、秘密分散された形で各サーバに保管される。したがって、演算結果を得たい場合は、演算結果に関する分散情報を集めて復元することになる。
【００３２】
秘密計算法には様々な方法がある。データがShamir(k,n)法を用いて分散されていることを前提とした手法（［非特許文献２］、［非特許文献３］等に記載）が代表的である。［非特許文献２］には、加減算と乗算を実行するための秘密計算法が記載されている。加算はサーバ間の通信を行うことなく実行可能であるが、乗算では２ラウンドの通信を必要とする方法が記載されている。［非特許文献３］には、乗算を１ラウンドの通信のみで実行可能な方式が提案されている。これ以降も、これらの基本演算を組み合わせた様々な方法が提案されている。
【００３３】
先に示した加法型(n,n)法による秘密分散においては、加算が容易に実行可能であり、乗算も後述する方法によって実行できる。なお、加減算と乗算とが実行できれば、任意の処理が実行可能である。
【００３４】
先に挙げたShamir(k,n)法や、加法型(n,n)法、加法型(2,3)法を用いて分散された値に関して、加減算や乗算に関する秘密計算を実行する方法が知られている。このように任意の処理を実行するために十分な秘密計算の方法を備える秘密分散法を、秘密計算を利用可能な秘密分散法と呼ぶ。
【００３５】
（［非特許文献４］に記載の固定小数点数向け乗算用秘密計算法）
固定小数点数の乗算に関する秘密計算法の前提技術として、［非特許文献４］に記載の方法を示す。この方法には、前処理の通信量が非常に大きいという課題がある。
【００３６】
この方法は、Shamir(k,n)法で分散されたデータに対して実行される。Shamir(k,n)法は、整数値を分散するために用いることができるので、固定小数点数を整数値として扱う。fを小数点の位置を定める整数として、整数値aにより固定小数点数a*2^{-f}を表す方法である。整数値xをShamir(k,n)法で分散して生成したn個の分散情報をx1、…、xnと書く。[x]と書く場合、n人の参加者P1、…、Pnがそれぞれx1、…、xnを所有していることを表す。Shamir(k,n)法ではmビットの整数値を分散する場合、その分散情報は2^mよりも大きい素数pについて0、…、p-1の値となり、各分散情報はmビット以上の値となる。Shamir(k,n)法で分散されたaとbとに関して、乗算の秘密計算法を実行し、その結果が[c]に格納されることを[c]←[a]*[b]と書く。同様に、aとbに関して、加算の秘密計算法を実行し、その結果が[c]に格納されることを[c]←[a]+[b]と書く。
【００３７】
［非特許文献４］に記載の方法において、a*2^(-f)とb*2^(-f)との積であるa*b^(-2f)を計算する方法を示す。aとbはそれぞれm桁の数で表されているものとする。a*bは2m桁の数となり、上位m桁を取る処理を行う。a*bは2m桁になるので、aやbを分散する場合、2^{2m}よりも大きい素数pを用いたShamir(k,n)法を用い、a，bのそれぞれを分散して入力するものとする。この分散のプロトコルは、［非特許文献４］のProtcol 3.1に示される、k桁の分散されている数[a]をmビット右シフトする秘密計算プロトコルTrancPr([a],k,m)を用いる。
【００３８】
［非特許文献４］に記載の秘密乗算方法によるFPMul([a],[b],2m,f)は、以下の通りである。
【００３９】
入力は[a]，[b]であって、FPMul([a],[b],2m,f)の計算手順は、
(11) [c]←[a]*[b]
(12) [d]←TrancPr([c],2m,f)であり、
出力が[d]である。
【００４０】
次に、［非特許文献４］のプロトコルTrancPr([a],k,m)を適用したTrancPr([c],2m,f)の処理について説明する。このプロトコルは、ランダムな０か１を分散するアルゴリズムと、ランダムな１ビットの情報を参加者間で共有するための秘密計算プロトコルPRandBit()と、指定されたxビット長の乱数を参加者間で共有するための秘密計算プロトコルPRandInt()と、が用いられる。
【００４１】
入力は[c]、2m、fであって、TrancPr([c],2m,f)の計算手順は、
(21) i=0,…,f-1について，[ri]←PRandBit()
(22) [r']←[r0]+[r1]*2^1+ … +[r{f-1}]*2^(f-1)
(23) [r"]←PRandInt(κ+2m-f)
(24) [r]←2^f*[r"]+[r']
(25) [c]←[a]+[r]
(26) cを復元し，参加者間で共有する。
(27) c'←c mod2^f
(28) [a']←c'-[r']
(29) [d]←[a]-[a']/2^(-f)
(30) [d]が出力である。
【００４２】
以上の処理のうち、PRandBit()やPRandInt()は入力される値に依存しないため、これらの処理は掛け算を実行する前の段階で実行できる。その他の処理のほとんどは定数倍などの軽量な秘密計算処理から成る。通信を要するのは、FPMulの(1)の手順の乗算と、Trancの(6)の手順の復元とになる。しかし、PRandBit()は多量の通信を要する。［非特許文献５］を参照すると、(2,3)しきい値法を用いる場合でも、１ビット当たり数百ビットの通信を要する。つまり、一度の固定小数点数に関する乗算について、（数百*f）ビットの通信が前処理にかかる。このような前処理も含めて全体の通信量を抑えた方式が望ましい。
【００４３】
《本実施形態の説明》
以下、本実施形態の秘密分散および秘密乗算について、その処理を説明する。
【００４４】
（本実施形態の秘密分散処理）
本実施形態では、データを(2,2)法で分散して、秘密計算装置群としての２台の秘密計算用サーバに格納する。本実施形態の用いる(2,2)法の具体的な方法は、以下の通りである。
【００４５】
なお、分散する固定小数点数xについて以下を前提とする。 ・mビットのデータで表され、下からf桁目に固定小数点がある。・最上位桁は符号ビットsであり、2の補数表現を用いる。・x'=x*2^fとする。xに対するx'を固定小数点数xのデータ値とする。
【００４６】
（データの分散方法）
入力:固定小数点数x(x'=x*2^f)
(31) 0、…、(2^m)-1からランダムな値rを選ぶ。
(32) x[1]=r、 x[2]=(x'+r)mod2^mとする。
(33) c=(x[1]+x[2])/2^mを計算し、小数点以下を切り下げる。
(34) c[1]を{0,1}からランダムに選択する。
(35) c[2]=(c+c[1])mod2を計算する。
(36) s[1]を{0,1}からランダムに選択する。
(37) s[2]=(s+s[1])mod2を計算する。
(38) v[1]=(x[1],c[1],s[1])、 v[2]=(x[2],c[2],s[2])を2つの分散情報として出力する。
【００４７】
ここで、
・x[1]、x[2]は、mod2^m上の加法型(2,2)法によって、データ値x'を分散した値である。
・cは、加法型(2,2)法によって、(x[1]+x[2])/2^m の小数点以下を切り下げた値である。この値は、(x[1]+x[2])が2^m以上になっている場合は１となり、それ以外の場合０となる。つまり、xを加法型(2,2)法で分散した際の桁溢れ（キャリー）が起こっているかどうかを表す。
・c[1]、c[2]はキャリーcを加法型(2,2)法によって分散した値である。
・s[1]、s[2]は、加法型(2,2)法によって、xの符号sを分散した値である。
・なお、以上の分散処理の過程に、fが一切関与していないことに注意を要する。したがって、固定小数点数を分散する秘密分散装置にはデータ値が入力されるものとする。
【００４８】
つまり、本実施形態においては、固定小数点数のデータ値x'と、データ値を分散したさいに生じたキャリーcと、データ値の符号sをそれぞれのビット長に応じた加法型(2,2)法によって分散する。
【００４９】
（本実施形態の秘密乗算処理）
次に、以上のような方法で分散された固定小数点数x、yに関する乗算を行う方法を示す。なお、xとyのデータ値は、それぞれx'(=x*2^f)、y(=y'*2^f)とする’。
【００５０】
2つの固定小数点数x、yは前述した方法で分散されて、秘密計算装置としての2台の固定小数点数乗算用サーバに記憶された状態から処理は開始される。2台の固定小数点数乗算用サーバを、それぞれ固定小数点数乗算用サーバ１（第１秘密計算装置に相当）、固定小数点数乗算用サーバ２（第２秘密計算装置に相当）とする。
【００５１】
xからは、v[1]=(x[1],c[1],s[1])とv[2]=(x[2],c[2],s[2])との２つの値が生成され、yからは、w[1]=(y[1],d[1],t[1])とw[2]=(y[2],d[2],t[2])との２つの値が生成される。固定小数点数乗算用サーバ１はv[1]とw[1]とを記憶し、固定小数点数乗算用サーバ２はv[2]とw[2]とを記憶する。
【００５２】
固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２とは、2mビットの乱数r1およびr2と、２つの乱数の法2^(2m)上の積である(r1*r2)mod2^(2m)=r12とを、加法型(2,2)法で分散した値を共有しているものとする。具体的には、r1=(r1[1]+r1[2])mod2^(2m)、r2=(r2[1]+r2[2])mod2^(2m)、r1*r2=(r12[1]+r12[2])mod2^(2m)について、固定小数点数乗算用サーバ１はr1[1]、r2[1]、r12[1]を保有し、固定小数点数乗算用サーバ２はr1[2]、r2[2]、r12[2]を保有する。このように、r1、r2、r1*r2が加法型(2,2)法で分散されているとき、これらを用いて、同じく加法型(2,2)法で分散されている値a、bに関する乗算を行うことができる。乗算ごとにr1、r2、r1*r2の３つ組みが加法型(2,2)法で分散されていなければならないが、効率的な方法である。具体的な方法は［非特許文献６］などに記載されている。この過程に実行される通信は、４ｋビットである。このようなr1、r2、r3の３つ組は使い捨てであり、繰り返し使うことはできない。そのため、必要な乗算の回数だけ固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２との間で共有しておかなければならない。
【００５３】
また、同様に、固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２とは、1ビットの乱数r1およびr2と、２つの乱数の法2上の積であるr1*r2mod2とを、加法型(2,2)法で分散した値を共有しているものとする。具体的には、r1=(r1[1]+r1[2])mod2、r2=(r2[1]+r2[2])mod2、r1*r2=(r12[1]+r12[2])mod2について、固定小数点数乗算用サーバ１はr1[1]、r2[1]、r12[1]を保有し、固定小数点数乗算用サーバ２は、r1[2]、r2[2]、r12[2]を保有する。このように、r1、r2、r1*r2が加法型(2,2)法で分散されているとき、これらを用いて、同じく加法型(2,2)法で分散されている値a、bに関する乗算を行うことができる。乗算ごとにr1、r2、r1*r2の３つ組みが加法型(2,2)法で分散されていなければならないが、効率的な方法である。具体的な方法は［非特許文献６］などに記載されている。この過程に実行される通信は、２ビットである。このようなr1、r2、r3の３つ組は使い捨てであり、繰り返し使うことはできない。そのため、必要な乗算の回数だけ固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２との間で共有しておかなければならない。
【００５４】
本実施形態で、固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２との間で分散されているaとbの乗算を計算する秘密計算を実行すると記載されているときには、前述した乱数の３つ組を用いた通信を伴って乗算を行っているものとする。
【００５５】
また、固定小数点数乗算用サーバ１と固定小数点数乗算用サーバ２とが１ビットの値Bを法2上の加法型(2,2)法で分散し、固定小数点数乗算用サーバ１がB[1]を保有し、固定小数点数乗算用サーバ２がB[2]を保有しているとき、以下の処理によってbと同じ値を分散しなおすことができる。
(41) 固定小数点数乗算用サーバ１はB[1]=(B'[1,1]+B'[1,2])mod2となるようなB'[1,1]とB'[1,2]とを{0,1}からランダムに選択し、B'[1,2]を固定小数点数乗算用サーバ２に送付する。
(42) 固定小数点数乗算用サーバ２は、B[2]=(B'[2,1]+B'[2,2])mod2となるようなB'[2,1]とB'[2,2]とを{0,1}からランダムに選択し、B'[2,1]を固定小数点数乗算用サーバ１に送付する。
(43) 固定小数点数乗算用サーバ１は、B'[1]=(B'[1,1]+B'[2,1])mod2を計算する。
(44) 固定小数点数乗算用サーバ２は、B'[2]=(B'[1,2]+B'[2,2])mod2を計算する。
【００５６】
以上の処理の結果として、B'[1]+B'[2]=B'[1,1]+B'[2,1]+B'[1,2]+B'[2,2]=B[1]+B[2]=(Bmod2)となるので、B'[1]とB'[2]とはBと同じ値の分散情報となっている。以上の過程において、Bは一度も復元されることはない。(41)、(42)の処理は並列に実行できるので、以上の処理は１ラウンドの通信で実行される。２ビットである。以降、ある値を再分散する場合、単に再分散すると記載するが、前述した処理が実行されているものとする。
【００５７】
（秘密乗算手順）
(51) j=1、…、mについて以下の処理を実行する。なお、c{m}=cとする。
(51-1) x{m+j}=s+c{m+j-1}を実行する秘密計算を実行する、なお、結果の分散情報はx[1]{m+j},x[2]{m+j}とする。固定小数点数乗算用サーバi(i=1,2)はx[i]{m+j}を保有する。
(51-2) ｙ{m+j}=t+d{m+j-1}を実行する秘密計算を実行する、なお、結果の分散情報はy[1]{m+j}、y[2]{m+j}とする。固定小数点数乗算用サーバi(i=1,2)はy[i]{m+j}を保有する。
(51-3) c{m+j}=x[1]{m+j}+(x[1]{m+j}+x[2]{m+j})(x[2]{m+j}+c{m+j-1}+1)を実行する秘密計算を実行する、なお、結果の分散情報はc{m+j}[1]、c{m+j}[2]とする。固定小数点数乗算用サーバi(i=1,2)はc[i]{m+j}を保有する。なお、この処理は、x[1]{m+j}、x[2]{m+j}はそれぞれの値を所有する固定小数点数乗算用サーバが、所有する値を再分散し、それぞれの所有する値を明かすことなく実行する。
(51-4) d{m+j}=y[1]{m+j}+(y[1]{m+j}+y[2]{m+j})(y[2]{m+j}+d{m+j+1}+1)を実行する秘密計算を実行する、なお、結果の分散情報はd[1]{m+1}、d[2]{m+1}とする。固定小数点数乗算用サーバi(i=1,2)はd[i]{m+1}を保有する。なお、この処理は、y[1]{m+1}、y[2]{m+1}はそれぞれの値を所有する固定小数点数乗算用サーバが、所有する値を再分散し、それぞれの所有する値を明かすことなく実行する。
【００５８】
(52) i=1,2について、x'[i]=x[i]{m+f}||x[i]{m+f-1}||…||x[i]{m+1}||x[i]、 y'[i]=y[i]{m+f}||y[i]{m+f-1}||…||y[i]{m+1}||y[i]とする。
【００５９】
(53) z'=(x'*y')mod2^(m+f)に相当する秘密計算を実行する。なお、結果の分散情報はz'[1]、z'[2]とする。固定小数点数乗算用サーバi(i=1,2)はz'[i]を保有する。z'[i](i=1,2)の下位からjビット目をz'[i]{j}とする。
【００６０】
(54) j=1、…、f+mについて、以下の処理を実行する。なお、c{0}=0とする。
(54-1) e{j}=z'[1]{j}+(z'[1]{j}+z'[2]{j})(z[2]{j}+e{j-1}+1)を実行する秘密計算を実行する、なお、結果の分散情報はe[1]{j}、e[2]{j}とする。固定小数点数乗算用サーバi(i=1,2)はe[i]{j}を保有する。なお、この処理は、z[1]{j}、z[2]{j}はそれぞれの値を所有する固定小数点数乗算用サーバが、所有する値を再分散し、それぞれの所有する値を明かすことなく実行する。
(54-2) j=f+mのとき、e{j}を再分散した分散情報をe[i](i=1,2)とする。固定小数点数乗算用サーバi(i=1,2)はe[i]を保有する。
【００６１】
(55) j=,2について、u[i]=(s[i]+t[i])mod2を計算する。固定小数点数乗算用サーバi(i=1,2)はu[i]を保有する。
【００６２】
(56) i=1,2について、z[i]=z'[i]{m+f}||z'[i]{m+f-1}||…||z'[i]{f}とし、固定小数点数乗算用サーバiの出力はz[i]、u[i]、e[i]の組とする。
【００６３】
（各処理手順の説明）
次に、先に示した処理の意味を説明する。本実施形態においては、固定小数点数xと固定小数点数ｙの計算を実行してこれらの積を計算する場合、まず、それぞれのデータ値であるx'(=x*2^f)とy'(=y*2^f)の掛け算結果x'y'を計算する。この結果x'y'はx'y'*2^{-f}を表しているため、所望の結果xy=x'y'*2^(-2f)を得るため、x'y'を右にfビットシフトする（下位fビットを切り捨てる）という方法で答えを求める。
【００６４】
まず、(51)の処理について説明する。この処理は、法2^(m)上の加法型(2,2)法で分散された２つのデータ値ｘ'、ｙ'を、法2^(m+f)上の加法型(2,2)法で分散された値に変換する処理である。法を2^{m+f}に変更する必要があるのは、fビット切り捨ててもmビットの結果を得るためである。法を大きくする際に考慮しなければならないこととして、符号ビットの扱いがある。
【００６５】
符号ビットの扱いについてだが、補数表現を用いたmビットデータを乗算のためにm+fビットを用いて表す場合、上位fビットには符号ビットを詰めると正しい乗算結果となる。m=4、f=2、２進表記でデータ値がの浮動小数点であれば、２進表記で111110とし、0110であれば、000110である。上位ビットにどのような値を配置するのかを定めるために、データ値を分散する際に符号を単独で分散している。しかし、単純に符号ビットを再分散した値を4つ並べればよいかというと、不十分である。これは桁上がりが起こるためである。
【００６６】
例として、データ値D=0110を加法的(2,2)法によってD[1]=1101とD[2]=1001とに分散した場合、D[1]+D[2]=10110であり、(10110)mod10000=0110である。これらの値の上位に符号ビットとして00を付け加える場合、E=00を加法的(2,2)法によってE[1]=11、E[2]=01に分散したとする。D'[1]=E[1]||D[1]=111101、D'[2]=E[2]||D[2]=011001とすると、(D'[1]+D'[2])mod100000=010110となり、符号である０が並ばなくなってしまう。そのため、桁上がりを考慮した結果が符号ビットとなる方法で上位桁は付け足さなければならない。このように、桁上がりを考慮して符号ビットを付けたすために、データ値を分散した値で桁上がりが起きていたかどうかを表す１ビットも分散している。
【００６７】
次に、より具体的に(51)の処理の内容について示す。この処理はxとyの２つの値について同じ処理を実行しているので、xに関する処理((51-1)と（51-3）)を説明する。
【００６８】
(51-1)は、m+jビット目の値を分散するための秘密計算を実行している。この秘密計算は、値xのm+jビット目の値として利用するx{m+j}をm+j-1ビット目からの桁上がりであるc{m+j-1}を考慮しても符号sと等しくなるような値を計算している。x{m+j}を、真理値表を用いて表すと、表１の通りである。
【００６９】
【表１】
0006988807.tif 000002
つまり、x{m+j}=(s+c{m+j-1})mod2によって表される。この秘密計算の結果として、x{m+j}が分散されて、x[1]{m+j}とx[2]{m+j}とが生成される。
【００７０】
(51-3)は、m+jビット目の値(x[1]{m+j}+x[2]{m+j}+c{m+j-1})が2以上であるか（２以上の場合は１、それ以外の場合は０）を計算し、c{m+j}としている。この値は、m+j+1ビット目の値への桁上がりがあるかどうかを表す値である。c{m+j}を、真理値表を用いて表すと、表２の通りである。
【００７１】
【表２】
0006988807.tif 000003
つまり、c{m+j}=(x[1]{m+j}+(x[1]{m+j}+x[2]{m+j})(x[2]{m+j}+c{m+j-1}+1))mod2によって表される。加法型(2,2)法では、加減算については通信が必要なく、乗算は通信が必要となる。そのため、同じ演算であっても可能な限り乗算の回数少なく計算するのがよい。前述の方法は乗算１回である。c{m+j}を計算する秘密計算の結果としてc[1]{m+j}とc[2]{m+j}とが生成される。
【００７２】
これら(51-1)と(51-3)との処理によって、x[i]{m+1}、…x[i]{m+m}が生成される。これらはx[i]の上位に付け加えるmビットであるので、x[i]{m+m}||x[i]{m+m-1}||…||x[i]{m+f}||x[i]が所望の拡張結果となっている。
【００７３】
(53)の処理は、mod2^(m+f)上で、x'*y'を秘密計算する処理である。データ値x'*y'は固定小数点数x'*y'*2^{-f}を表している。この値からx'*y'*2^{-2f}を計算したい。2^{-1}を乗じることは下位１ビットを切ることに対応するため、x'*y'の下位fビットを切ることで、所望の値が得られることになる。つまり、x'*y'からf+1ビット目からf+mビット目を取り出す処理を実行する。
【００７４】
(54)の乗算結果に関してf+kビット目を定める処理について説明する。(54)では、j=1、…、mについて、c{j}=(z'[1]{j}+(z'[1]{j}+z'[2]{j})(z[2]{j}+c{j-1}+1))mod2を計算している。これは、j+1ビット目へのキャリーがあるかどうかの計算である。この計算によってキャリーが求まるのは、(51-3)と同じ理由である。この処理の結果、f+1ビット目に対するキャリーc{f}が分散された形式で求められる。
【００７５】
(55)の処理では、計算結果の符号を計算している。正の数は０、負の数は１であるので，mod2上で符号に関するシェアを加算することで計算できる。正は０、負を１とすると、負×負が正になることも(1+1)mod2から保たれているためである。
【００７６】
以上の手順は、次の手順によって構成されていることが分かる。
（１）データ値の法を拡大する秘密計算
（２）拡大後の法における乗算の秘密計算
（３）下位ビットの切り捨て処理に関する秘密計算
（４）キャリーと符号の分散処理
【００７７】
《本実施形態を実現する構成》
以下、本実施形態の秘密分散処理および秘密乗算処理を実現するシステムおよび装置の構成と動作とを説明する。
【００７８】
《秘密計算システム》
図２は、本実施形態に係る秘密計算システム２００の構成を示すブロック図である。
【００７９】
図２を参照すると、本実施形態の秘密計算システム２００は、固定小数点数分散装置としての分散情報生成装置２１０と、ネットワーク２４０を介して接続される少なくとも２つの秘密計算装置２２０、２３０と、を備える。
【００８０】
分散情報生成装置２１０は、データ値分散部２１１と、符号分散部２１２と、キャリー分散部２１３と、ランダム数分散部２１４とを有し、少なくとも２つの固定小数点数のデータ値、符号、キャリー、および、ランダム数を生成して、少なくとも２つの秘密計算装置２２０、２３０に分散する。
【００８１】
秘密計算装置２２０は、分散情報生成装置２１０から送信された分散情報を記憶する分散情報記憶部２２１と、他の秘密計算装置２３０と秘密を保持したデータ交換を行ないながら秘密乗算を実行する乗算処理部２２２とを有する。また、秘密計算装置２３０は、分散情報生成装置２１０から送信された分散情報を記憶する分散情報記憶部２３１と、他の秘密計算装置２２０と秘密を保持したデータ交換を行ないながら秘密乗算を実行する乗算処理部２３２とを有する。
【００８２】
そして、乗算処理部２２２と乗算処理部２３２とが、秘密を保持してデータ交換を行ないながら、協働して桁の拡張と秘密乗算とを行なう、秘密桁拡張部や秘密乗算部に相当する。
【００８３】
なお、ランダム数分散部２１４は、分散情報生成装置２１０とは別の装置にあってもよい。また、分散情報記憶部２２１や２３１は、秘密計算装置の外部の分散情報記憶装置として構成されてもよい。
【００８４】
《分散情報生成装置の機能構成》
図３は、本実施形態に係る秘密計算システム２００における分散情報生成装置２１０の機能構成を示すブロック図である。図３には、分散情報生成装置２１０が、生成した分散情報を秘密計算装置２２０の分散情報記憶部２２１、および、秘密計算装置２３０の分散情報記憶部２３１に分散する構成も図示している。固定小数点の位置を表すfが固定されており、これを利用する装置にはあらかじめ記憶されている前提で記載しているが、各装置に入力されるものとしてもよい。
【００８５】
固定小数点数分散装置としての分散情報生成装置２１０は、データ値分散部２１１と、符号分散部２１２と、キャリー分散部２１３と、ランダム数分散部２１４と、を備える。データ値分散ぶ２１１は、データ値x'を入力とし、データ値を加法型(2,2)法で分散した値x[i](i=1,2)と、データ値の分散情報に対するキャリーcを出力する。符号分散部２１２は、データ値x'を入力とし、データ値x'から符号ビットsを抽出し、符号ビットを加法型(2,2)法で分散した値s[i](i=1,2)を出力する。キャリー分散部２１３は、データ値分散部２１１の出力であるキャリーcを入力とし、データ値を加法型(2,2)法で分散した値c[i](i=1,2)を出力する。ランダム数分散部２１４は、秘密計算するビット数を有する、少なくとも２つのランダム数p,qとその乗算結果r=p*qの分散値（p[i],q[i],r=p*q[i])(i=1,2)を出力する。
【００８６】
データ値分散部２１１と、符号分散部２１２と、キャリー分散部２１３と、ランダム数分散部２１４とは、生成した各分散値を複数の秘密計算装置２２０、２３０に送信して、それらの分散情報記憶部に記憶させる。なお、ランダム数分散部２１４は、分散情報生成装置２１０以外の装置に設けられてもよい。
【００８７】
秘密計算装置２２０は分散情報記憶部２２１を有し、秘密計算装置２３０は分散情報記憶部２３１をそれぞれ有している。分散情報記憶部２２１は、第１固定小数点数の分散情報記憶部３２１と、第２固定小数点数の分散情報記憶部３２５と、ランダム数の分散情報記憶部３２９と、を含む。なお、固定小数点数が３つ以上の場合には、さらに分散情報記憶部を有する。そして、第１固定小数点数の分散情報記憶部３２１には、第１固定小数点数の分散データ値３２２と分散符号値３２３と分散キャリー値３２４とが記憶される。第２固定小数点数の分散情報記憶部３２５には、第２固定小数点数の分散データ値３２６と分散符号値３２７と分散キャリー値３２８とが記憶される。ランダム数の分散情報記憶部３２９には、１ビットランダム数の分散値と乗算時の拡張ビットランダム数の分散値とが記憶される。
【００８８】
また、分散情報記憶部２３１は、第１固定小数点数の分散情報記憶部３３１と、第２固定小数点数の分散情報記憶部３３５と、ランダム数の分散情報記憶部３３９と、を含む。なお、固定小数点数が３つ以上の場合には、さらに分散情報記憶部を有する。そして、第１固定小数点数の分散情報記憶部３３１には、第１固定小数点数の分散データ値３３２と分散符号値３３３と分散キャリー値３３４とが記憶される。第２固定小数点数の分散情報記憶部３３５には、第２固定小数点数の分散データ値３３６と分散符号値３３７と分散キャリー値３３８とが記憶される。ランダム数の分散情報記憶部３３９には、１ビットランダム数の分散値と乗算時の拡張ビットランダム数の分散値とが記憶される。
【００８９】
例えば、第１固定小数点数xのデータ値x'を入力とし、データ値分散部２１１の出力であるデータ値分散情報x[i](i=1,2)が、第１固定小数点数の分散情報記憶部３２１の分散データ値３２２、および、第１固定小数点数の分散情報記憶部３３１の分散データ値３３２にそれぞれ分散記憶される。
【００９０】
第１固定小数点数xの符号値sを入力とし、符号分散部２１２の出力である符号分散情報s[i](i=1,2)が、第１固定小数点数の分散情報記憶部３２１の分散符号値３２３、および、第１固定小数点数の分散情報記憶部３３１の分散符号値３３３にそれぞれ分散記憶される。
【００９１】
第１固定小数点数xのキャリー値cを入力とし、キャリー分散部２１３の出力であるキャリー分散情報c[i](i=1,2)が、第１固定小数点数の分散情報記憶部３２１の分散キャリー値３２４、および、第１固定小数点数の分散情報記憶部３３１の分散キャリー値３３４にそれぞれ分散記憶される。
【００９２】
《秘密計算装置の機能構成》
図４は、本実施形態に係る秘密計算システム２００における秘密計算装置２２０、２３０の機能構成を示すブロック図である。なお、図４において、図３と同様の構成要素には同じ参照番号を付して、重複する説明を省略する。
【００９３】
秘密計算装置２２０の固定小数点数の乗算処理部２２２は、法拡大用秘密計算部４２１と、乗算用秘密計算部４２２と、下位桁切除部４２３と、符号抽出部４２４と、キャリー抽出秘密計算部４２５と、を備える。秘密計算装置２３０の固定小数点数の乗算処理部２３２は、法拡大用秘密計算部４３１と、乗算用秘密計算部４３２と、下位桁切除部４３３と、符号抽出部４３４と、キャリー抽出秘密計算部４３５と、を備える。
【００９４】
法拡大用秘密計算部４２１と法拡大用秘密計算部４３１とは、第１固定小数点数および第２固定小数点数の、各分散データ値、各分散符号値、各分散キャリー値を入力とし、互いに秘密を保持したデータ交換を行ないながら、第１拡張固定小数点数および第２拡張固定小数点数の、各拡張分散データ値、各拡張分散符号値、各拡張分散キャリー値を生成する。秘密を保持したデータ交換には、ランダム数の分散情報記憶部３２９および３３９の１ビットランダム分散値が用いられる。この法拡大用秘密計算部４２１と法拡大用秘密計算部４３１とが、秘密桁拡張部に相当する。
【００９５】
乗算用秘密計算部４２２と乗算用秘密計算部４３２とは、法拡大された第１拡張固定小数点数および第２拡張固定小数点数の、各拡張分散データ値、各拡張分散符号値、各拡張分散キャリー値に基づいて、互いに秘密を保持したデータ交換を行ないながら、拡張秘密乗算結果の拡張分散データ値、拡張分散符号値、拡張分散キャリー値を生成する。秘密を保持したデータ交換には、ランダム数の分散情報記憶部３２９および３３９の拡張ビットランダム分散値が用いられる。
【００９６】
各下位桁切除部４２３、４３３は、それぞれの拡張秘密乗算結果の拡張分散データ値から、固定小数点数である秘密乗算結果の各分散データ値を生成する。各符号抽出部４２４、４３４は、それぞれの拡張秘密乗算結果の拡張分散符号値から、固定小数点数である秘密乗算結果の各分散符号値を生成する。キャリー抽出秘密計算部４２５、４３５は、互いに秘密を保持したデータ交換を行ないながら、拡張秘密乗算結果の互いに秘密を保持したデータ交換を行ないながら、拡張秘密乗算結果の拡張分散データ値と拡張分散キャリー値とから、固定小数点数である秘密乗算結果の各分散キャリー値を生成する。
【００９７】
なお、上記の乗算用秘密計算部４２２、下位桁切除部４２３、符号抽出部４２４およびキャリー抽出秘密計算部４２５と、乗算用秘密計算部４３２、下位桁切除部４３３、符号抽出部４３４およびキャリー抽出秘密計算部４３５とが、秘密乗算部に相当する。
【００９８】
乗算処理部２２２の下位桁切除部４２３の出力である秘密乗算結果の分散データ値は、分散情報記憶部２２１が有する乗算結果の分散情報記憶部４２６に分散データ値４２７として記憶される。乗算処理部２２２の符号抽出部４２４の出力である秘密乗算結果の分散符号値は、分散情報記憶部２２１が有する乗算結果の分散情報記憶部４２６に分散符号値４２８として記憶される。乗算処理部２２２のキャリー抽出秘密計算部４２５の出力である秘密乗算結果の分散キャリー値は、分散情報記憶部２２１が有する乗算結果の分散情報記憶部４２６に分散キャリー値４２９として記憶される。
【００９９】
一方、乗算処理部２３２の下位桁切除部４３３の出力である秘密乗算結果の分散データ値は、分散情報記憶部２３１が有する乗算結果の分散情報記憶部４３６に分散データ値４３７として記憶される。乗算処理部２３２の符号抽出部４３４の出力である秘密乗算結果の分散符号値は、分散情報記憶部２３１が有する乗算結果の分散情報記憶部４３６に分散符号値４３８として記憶される。乗算処理部２３２のキャリー抽出秘密計算部４３５の出力である秘密乗算結果の分散キャリー値は、分散情報記憶部２３１が有する乗算結果の分散情報記憶部４３６に分散キャリー値４３９として記憶される。
【０１００】
なお、固定小数点数の分散情報記憶部は、２つでひとつの値の分散情報を記憶するような構成であるが、一組の装置が多くの値を記憶してもよい。その場合、各値に識別情報などをつけて記憶することになる。
【０１０１】
以上の説明では、加法型(2,2)法を分散するために用いる方法で記載したが、他の(k,n)法でもよい。その場合、固定小数点数の分散情報記憶部はn個になり、固定小数点数の乗算処理部は、対応する秘密計算の方法で必要となる個数になる。なお、［非特許文献５］との違いは、［非特許文献５］の方法は乱数でマスクした乗算結果を一端復元するというステップを踏んでいることにある。
【０１０２】
《動作手順の説明》
次に、本実施形態における秘密乗算処理を、
（１）固定小数点数の分散情報の生成処理と、
（２）固定小数点数の乗算に関する秘密計算と、
に分けて、その動作手順をさらに説明する。
【０１０３】
《分散情報生成装置のハードウェア構成》
図５は、本実施形態に係る分散情報生成装置２１０のハードウェア構成を示すブロック図である。
【０１０４】
図５で、ＣＰＵ(Central Processing Unit)５１０は演算制御用のプロセッサであり、プログラムを実行することで図３の機能構成部を実現する。ＣＰＵ５１０は複数のプロセッサを有し、異なるプログラムやモジュール、タスク、スレッドなどを並行して実行してもよい。ＲＯＭ(Read Only Memory)５２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。ネットワークインタフェース５３０は、ネットワークを介して、複数の秘密計算装置との通信を制御する。
【０１０５】
ＲＡＭ(Random Access Memory)５４０は、ＣＰＵ５１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ５４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。第１固定小数点数５４１は、本実施形態において秘密乗算する一方の数である。第２固定小数点数５４２は、本実施形態において秘密乗算する他方の数である。
【０１０６】
第１固定小数点数の第１分散値５４３は、第１固定小数点数５４１から生成された一方の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第１固定小数点数の第２分散値５４４は、第１固定小数点数５４１から生成された他方の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第１分散値５４３と第２分散値５４４とは、異なる秘密計算装置に送信される。
【０１０７】
第２固定小数点数の第１分散値５４５は、第２固定小数点数５４２から生成された一方の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第２固定小数点数の第２分散値５４６は、第２固定小数点数５４２から生成された一方の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第１分散値５４５と第２分散値５４６とは、異なる秘密計算装置に送信される。
【０１０８】
ランダム数(p,q,p*q)５４７は、異なる秘密計算装置間の通信のために使用される乱数である。かかる乱数のビット数は、異なる秘密計算装置間で通信されるデータのビット数に対応して設定される。ランダム数の第１分散値５４８は、ランダム数(p,q,p*q)５４７から生成された一方の分散値である。ランダム数の第２分散値５４９は、ランダム数(p,q,p*q)５４７から生成された他方の分散値である。第１分散値５４８と第２分散値５４９とは、異なる秘密計算装置に送信される。
【０１０９】
ストレージ５５０は、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。データ値分散アルゴリズム５５１は、本実施形態で使用される被乗算値のデータ値を分散するアルゴリズムである。符号分散アルゴリズム５５２は、本実施形態で使用される被乗算値の符号を分散するアルゴリズムである。キャリー分散アルゴリズム５５３は、本実施形態で使用される被乗算値のキャリーを分散するアルゴリズムである。ランダム数分散アルゴリズム５５４は、本実施形態で使用される被乗算値のランダム数を分散するアルゴリズムである。
【０１１０】
ストレージ５５０には、以下のプログラムが格納される。分散情報生成プログラム５５５は、本分散情報生成装置２１０を制御して分散情報を生成するプログラムである。データ値分散モジュール５５６は、固定小数点数から分散データ値を生成するモジュールである。符号分散モジュール５５７は、固定小数点数から分散符号値を生成するモジュールである。キャリー分散モジュール５５８は、データ値分散モジュール５５６が固定小数点数から分散データ値を生成した際に発生したキャリーの分散キャリー値を生成するモジュールである。ランダム数分散モジュール５５９は、ランダム数から分散ランダム数を生成するモジュールである。
【０１１１】
なお、図５のＲＡＭ５４０やストレージ５５０には、分散情報生成装置２１０が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【０１１２】
《分散情報生成処理》
図６は、本実施形態に係る分散情報生成装置２１０の分散情報生成処理の手順を示すフローチャートである。このフローチャートは、図５のＣＰＵ５１０がＲＡＭ５４０を使用して実行し、図３の分散情報生成装置２１０の機能構成部を実現する。
【０１１３】
分散情報生成装置２１０は、ステップＳ６０１において、固定小数点数のデータ値を取得する。分散情報生成装置２１０は、ステップＳ６０３において、データ値から、加法型(2,2)法を用いて分散した分散データ値を生成し、分散データ値に関するキャリーを出力する。
【０１１４】
分散情報生成装置２１０は、ステップＳ６０５において、データ値から符号を抽出し、符号を、加法型(2,2)法を用いて分散した分散符号値を生成する。分散情報生成装置２１０は、ステップＳ６０７において、ステップＳ６０３で出力されたキャリー値を、加法型(2,2)法を用いて分散した分散キャリー値を生成する。
【０１１５】
分散情報生成装置２１０は、ステップＳ６０９において、秘密計算中に交換する値のビット数に対応する、少なくとも２つのランダム数とその乗算値の分散値を生成する。
【０１１６】
そして、分散情報生成装置２１０は、ステップＳ６１１において、分散データ値、分散符号値、分散キャリー値の組である分散値を、それぞれ秘密計算装置が有する固定小数点数の分散情報記憶部に送信して記憶させる。また、少なくとも２つのランダム数とその乗算値の分散値をランダム数の分散情報記憶部に送信して記憶させる。なお、少なくとも２つのランダム数とその乗算値の分散値は、各秘密計算の前に送信されてもよい。
【０１１７】
《秘密計算装置のハードウェア構成》
図７は、本実施形態に係る秘密計算装置２２０、２３０のハードウェア構成を示すブロック図である。なお、図７には、秘密計算装置２２０、２３０のいずれか１つの構成を示す。図７に示す秘密計算装置の複数が秘密データの交換をしながら、秘密乗算を実行することになる。
【０１１８】
図７で、ＣＰＵ７１０は演算制御用のプロセッサであり、プログラムを実行することで図３の機能構成部を実現する。ＣＰＵ７１０は複数のプロセッサを有し、異なるプログラムやモジュール、タスク、スレッドなどを並行して実行してもよい。ＲＯＭ７２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。ネットワークインタフェース７３０は、ネットワークを介して、分散情報生成装置２１０または他の秘密計算装置との通信を制御する。
【０１１９】
ＲＡＭ７４０は、ＣＰＵ７１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ７４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。第１固定小数点数の分散値７４１は、第１固定小数点数５４１の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第２固定小数点数の分散値７４２は、第２固定小数点数５４２の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。ランダム数の分散値７４３は、ランダム数５４７の分散値であり、本実施形態では、１桁の数の分散値と、被乗算数の拡張桁の数の分散値とを含む。
【０１２０】
第１拡張固定小数点数の分散値７４４は、第１固定小数点数の分散値７４１と、他の秘密計算装置に記憶された第１固定小数点数の分散値とから、秘密計算により第１固定小数点数の桁数を拡張した第１拡張固定小数点数の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。第２拡張固定小数点数の分散値７４５は、第２固定小数点数の分散値７４２と、他の秘密計算装置に記憶された第２固定小数点数の分散値とから、秘密計算により第２固定小数点数の桁数を拡張した第２拡張固定小数点数の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。
【０１２１】
拡張秘密乗算結果の分散値７４６は、第１拡張固定小数点数の分散値７４４と、第２拡張固定小数点数の分散値７４５と、他の秘密計算装置に記憶された第１拡張固定小数点数の分散値および第２拡張固定小数点数の分散値とから、秘密計算により乗算した拡張乗算結果の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。
【０１２２】
秘密乗算結果の分散値７４７は、拡張秘密乗算結果の分散値７４６と、他の秘密計算装置に記憶された拡張秘密乗算結果の分散値とから、秘密計算により拡張桁を切除した乗算結果の分散値であり、分散データ値と分散符号値と分散キャリー値との組である。
【０１２３】
中間秘密値７４８は、固定小数点数の桁拡張と、秘密乗算と、秘密乗算結果の拡散キャリー値の計算とで使用される、ランダム数の分散値を用いた中間の秘密値であり、後述のg,h,g-p,h-g,x'-p,y'-qなどが含まれる。
【０１２４】
ストレージ７５０は、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。上位桁の分散データ値生成アルゴリズム７５１は、本実施形態で使用される被乗算値のデータ値の上位桁を生成して分散するアルゴリズムである。上位桁の分散キャリー値生成アルゴリズム７５２は、本実施形態で使用される被乗算値のキャリー値の上位桁を生成して分散するアルゴリズムである。拡張分散データ値の秘密乗算アルゴリズム７５３は、本実施形態で使用される被乗算値の拡張分散データ値を秘密乗算するアルゴリズムである。秘密乗算結果の後処理アルゴリズム７５４は、拡張秘密乗算結果の分散値から拡張桁を切除した秘密乗算結果を生成するアルゴリズムであり、下位桁切除処理や符号抽出処理やキャリー抽出処理を含む。
【０１２５】
ストレージ７５０には、以下のプログラムが格納される。秘密乗算制御プログラム７５５は、本秘密計算装置２２０または２３０を制御して秘密乗算するプログラムである。拡張分散値生成モジュール７５６は、上記分散データ値生成アルゴリズム７５１および分散キャリー値生成アルゴリズム７５２に従って、桁が拡張された乗算用の分散値である、拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成するモジュールである。拡張分散値秘密乗算モジュール７５７は、上記秘密乗算アルゴリズム７５３に従って、拡張分散データ値を用いて秘密乗算を行なうモジュールである。秘密乗算結果後処理モジュール７５８は、上記後処理アルゴリズム７５４に従って、拡張秘密乗算結果から拡張桁を切除した、秘密乗算結果の分散データ値と分散符号値と分散キャリー値とを生成するモジュールである。
【０１２６】
なお、図７のＲＡＭ７４０やストレージ７５０には、秘密計算装置２２０、２３０が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【０１２７】
《秘密乗算処理》
図８は、本実施形態に係る秘密計算装置群による秘密乗算処理の手順を示すフローチャートである。このフローチャートは、図７のＣＰＵ７１０がＲＡＭ７４０を使用して実行し、図４の秘密計算装置群の秘密計算装置２２０、２３０の機能構成部を実現する。
【０１２８】
秘密計算装置群の秘密計算装置２２０、２３０のそれぞれは、ステップＳ８０１において、各分散情報記憶部２２１、２３１から各分散情報を読み出す。すなわち、秘密計算装置２２０の乗算処理部２２２は、第１固定小数点数の分散情報記憶部３２１から、第１固定小数点数の分散データ値３２２と、分散符号値３２３と、分散キャリー値３２４と、を読み出す。また、乗算処理部２２２は、第２固定小数点数の分散情報記憶部３２５から、第２固定小数点数の分散データ値３２６と、分散符号値３２７と、分散キャリー値３２８と、を読み出す。一方、秘密計算装置２３０の乗算処理部２３２は、第１固定小数点数の分散情報記憶部３３１から、第１固定小数点数の分散データ値３３２と、分散符号値３３３と、分散キャリー値３３４と、を読み出す。また、乗算処理部２３２は、第２固定小数点数の分散情報記憶部３３５から、第２固定小数点数の分散データ値３３６と、分散符号値３３７と、分散キャリー値３３８と、を読み出す。
【０１２９】
秘密計算装置群の秘密計算装置２２０、２３０は協働して、ステップＳ８０３において、法拡大用秘密計算部４２１と４３１とで秘密を保持しながらデータ交換して、第１固定小数点数および第２固定小数点数それぞれの拡張分散データ値と拡張符号値と拡張キャリアとを生成する秘密計算処理を実行する。
【０１３０】
秘密計算装置群の秘密計算装置２２０、２３０は協働して、ステップＳ８０５において、乗算用秘密計算部４２２と４３２とで秘密を保持しながらデータ交換して、第１固定小数点数の拡張分散データと第２固定小数点数の拡張分散データとを用いて第１固定小数点数と第２固定小数点数との拡張乗算結果の拡張分散データ値を求める秘密計算処理を実行する。
【０１３１】
秘密計算装置群の秘密計算装置２２０、２３０のそれぞれは、ステップＳ８０７において、下位桁切除部４２３と４３３とのそれぞれで、拡張乗算結果の拡張分散データ値の下位桁を切除して、乗算結果の分散データ値を生成する。秘密計算装置群の秘密計算装置２２０、２３０のそれぞれは、ステップＳ８０９において、符号抽出部４２４と４３４とのそれぞれで、乗算結果の分散符号値を抽出する。秘密計算装置群の秘密計算装置２２０、２３０は協働して、ステップＳ８１１において、キャリー抽出秘密計算部４２５と４３５とで秘密を保持しながらデータ交換して、拡張分散データ値と拡張キャリアとを用いて、分散キャリー値を抽出する秘密計算処理を実行する。
【０１３２】
そして、秘密計算装置群の秘密計算装置２２０、２３０のそれぞれは、ステップＳ８１３において、秘密算出した、第１固定小数点数と第２固定小数点数との秘密乗算結果の分散データ値と分散符号値と分散キャリー値とを、乗算結果の固定小数点数の分散情報記憶部４２６と４３６とにそれぞれ記憶する。すなわち、秘密計算装置２２０は、固定小数点数の分散情報記憶部４２６に乗算結果の分散データ値４２７と分散符号値４２８と分散キャリー値４２９とを記憶する。また、秘密計算装置２３０は、固定小数点数の分散情報記憶部４３６に乗算結果の分散データ値４３７と分散符号値４３８と分散キャリー値４３９とを記憶する。
【０１３３】
（法拡大（桁拡大）における秘密計算処理）
図９Ａは、本実施形態に係る各秘密計算装置２２０、２３０の法拡大（桁拡大）における秘密計算処理（Ｓ８０３）の手順を示すフローチャートである。図９Ａの説明においては、秘密計算装置２２０の処理として説明する。なお、本実施形態においては、固定小数点数の数ｊ＝２である。
【０１３４】
秘密計算装置２２０は、ステップＳ９１１において、１桁のランダム数の分散値を取得する。秘密計算装置２２０は、ステップＳ９１３において、固定小数点数の個数を表わす制御パラメータｊ＝０に初期化し、ステップＳ９１４において、ｊを１つインクリメントする。秘密計算装置２２０は、ステップＳ９１６において、追加桁数を表わす制御パラメータｉ＝０に初期化して、ステップＳ９１７において、ｉを１つインクリメントする。
【０１３５】
秘密計算装置２２０は、ステップＳ９１９において、第ｊ固定小数点数の(最上位＋ｉ)桁の分散データ値を生成する。そして、秘密計算装置２２０は、ステップＳ９２１において、生成した(最上位＋ｉ)桁の分散データを秘密計算装置２２０と他の秘密計算装置２３０とに分散し、ステップＳ９２３において、他の秘密計算装置２３０から、(最上位＋ｉ)桁の分散データを取得する。
【０１３６】
秘密計算装置２２０は、ステップＳ９２５において、第ｊ固定小数点数の(最上位＋ｉ)桁の分散キャリー値の部分値をそれぞれ生成する。そして、秘密計算装置２２０は、ステップＳ９２７において、生成した(最上位＋ｉ)桁の分散キャリー値の各部の値の、分散ランダム数を用いた秘密値を、他の秘密計算装置２３０に送付し、ステップＳ９２９において、他の秘密計算装置２３０から、(最上位＋ｉ桁の分散キャリー値の各部分値の秘密値を取得する。ここで、部分値とは、以下の具体例で示す“ｇ”や“ｈ”を示し、部分値の秘密値とは（ｇ−ｐ）や（ｈ−ｑ）を示す。
【０１３７】
秘密計算装置２２０は、ステップＳ９３１において、生成した部分値や取得した部分値の秘密値、あるいは、ランダム数の積r(=p*q)の分散値などを用いて、秘密を保持しながら、第ｊ固定小数点数の(最上位＋ｉ)桁の分散キャリー値を生成する。
【０１３８】
秘密計算装置２２０は、ステップＳ９３３において、ｉが初期分散データ値の桁であるか否かを判定する。すなわち、分散データ値が倍の桁にまで拡張されたかを判定する。ｉが初期分散データ値の桁でない場合、秘密計算装置２２０は、ステップＳ９１７に戻って、ｉをさらに１つインクリメントして、ステップＳ９１９〜Ｓ９３３を繰り返す。
【０１３９】
ｉが初期分散データ値の桁となった場合、秘密計算装置２２０は、ステップＳ９３５において、第ｊ固定小数点数について、初期分散データ値に生成した上位桁の分散データ値を加えて拡散分散データ値とし、最上位桁の分散キャリー値を拡散分散キャリー値とする。
【０１４０】
秘密計算装置２２０は、ステップＳ９３７において、ｊが固定小数点数の個数であるか否かを判定する。すなわち、秘密乗算する固定小数点数が全て拡張されたかを判定する。ｊが固定小数点数の個数でない場合、秘密計算装置２２０は、ステップＳ９１４に戻って、ｊをさらに１つインクリメントして、ステップＳ９１６〜Ｓ９３７を繰り返す。ｊが固定小数点数の個数となった場合、秘密乗算する全ての固定小数点数の拡張分散が終了したので、法拡大の秘密計算処理を終了する。
【０１４１】
（乗算における秘密計算処理）
図９Ｂは、本実施形態に係る各秘密計算装置２２０、２３０の乗算における秘密計算処理（Ｓ８０５）の手順を示すフローチャートである。図９Ｂの説明においては、秘密計算装置２２０の処理として説明する。なお、本実施形態においては、固定小数点数の数ｊ＝２である。
【０１４２】
秘密計算装置２２０は、ステップＳ９５１において、拡張分散データ値の桁のランダム数の分散値を取得する。秘密計算装置２２０は、ステップＳ９５３において、固定小数点数の個数を表わす制御パラメータｊ＝０に初期化し、ステップＳ９５５において、ｊを１つインクリメントする。
【０１４３】
秘密計算装置２２０は、ステップＳ９５７において、第ｊ固定小数点数の拡張分散データ値の、ランダム分散値を用いた秘密値を他の秘密計算装置２３０に送付し、ステップＳ９５９において、他の秘密計算装置２３０から、拡張分散データ値の秘密値を取得する。ここで、秘密値とは、以下の具体例で示す(x'[1]-p[1])mod2^(2m)、あるいは、(x'[2]-p[2])mod2^(2m)を示す。なお、次の処理では、(y'[1]-q[1])mod2^(2m)、あるいは、(y'[2]-q[2])mod2^(2m)となる。
【０１４４】
秘密計算装置２２０は、ステップＳ９６１において、生成した秘密値と取得した秘密値とを用いて、拡張乗算結果の分散データ値を生成するための第ｊ固定小数点数の中間秘密値を生成する。ここで、中間秘密値とは、以下の具体例で示す（ｘ’−ｐ）を示す。なお、次の処理では、（ｙ’−ｑ）となる。
【０１４５】
秘密計算装置２２０は、ステップＳ９６３において、ｊが固定小数点数の個数であるか否かを判定する。すなわち、秘密乗算するための全ての秘密値や中間秘密値が準備されたかを判定する。ｊが固定小数点数の個数でない場合、秘密計算装置２２０は、ステップＳ９５５に戻って、次の固定小数点数の拡張分散データ値から秘密値や中間秘密値の生成、送付および取得を繰り返す。
【０１４６】
ｊが固定小数点数の個数になった場合、秘密乗算するための全ての秘密値や中間秘密値が準備されたので、秘密計算装置２２０は、ステップＳ９６５において、第１固定小数点数および第２固定小数点数の中間秘密値を用いて、拡張乗算結果の分散データ値を生成する。同様に、他の秘密計算装置２３０も拡張乗算結果の分散データ値を生成する。
【０１４７】
（キャリー抽出の秘密計算処理）
図８のステップＳ８１１におけるキャリー抽出の秘密計算処理は、図９ＡのステップＳ３０３における上位桁の分散キャリー値の生成処理と類似の処理であるので、重複を避けて説明を書略する。
【０１４８】
《秘密乗算の具体例》
以下、本実施形態の秘密計算システムにおいて、具体的な秘密分散および秘密乗算を行なった例を説明する。
【０１４９】
（数値例）
x=-2.0とy=+2.5に関する、x*y=-5.0の本実施形態に基づく秘密乗算例を示す。この秘密乗算を２進表記すると、1110.0*0010.1=1011.0となる。すなわち、ｍ（桁数）＝５、ｆ（小数点以下の桁）＝１である。
【０１５０】
補数を用いる場合の乗算では、
1111111100
*   0000000101
1001111101100      
となり、下位の６桁目から２桁目の５桁を乗算結果として得ることになる。
【０１５１】
《数値の分散》
（xの分散）
x(=1110.0)のデータ値x'(=11100)を２つのサーバに分散する。
0から11111までの任意の数を、r=11000とすると、(x'+r)mod2^5(=100000)=10100となる。そして、x[1]=11000はサーバ１への分散値となり、x[2]=10100はサーバ２への分散値となる。なお、x[1]の下位からj桁目をx[1]{j}、x[2]の下位からj桁目をx[2]{j}とする。
（x'のキャリー:cの分散）
c=1であり、c[1]=1とc[2]=0とに分散される。
（xの符号:sの分散）
s=1であり、s[1]=0とs[2]=1とに分散される。
xの分散情報は、v[1]=(11000,1,0)と、v[2]=(10100,0,1)とになる。
【０１５２】
（yの分散）
y(=0010.1)のデータ値y'(=00101)を２つのサーバに分散する。
0から11111までの任意の数を、r=00100とすると、(y'+r)mod2^5(=100000)=01001となる。そして、y[1]=00100はサーバ１への分散値となり、y[2]=01001はサーバ２への分散値となる。なお、y[1]の下位からj桁目をy[1]{j}, y[2]の下位からj桁目をy[2]{j}とする。
（y'のキャリー:dの分散）
d=0であり、d[1]=0とd[2]=0とに分散される。
（yの符号:tの分散）
t=0であり、t[1]=0とt[2]=0とに分散される。
yの分散情報は、w[1]=(00100,0,0)と、w[2] = (01001,0,0)とになる。
【０１５３】
乗算される数値として、サーバ１にv[1],w[1]が配られ、サーバ２にv[2],w[2]が配られる。
【０１５４】
《数値の桁の拡張：秘密乗算の準備処理》
乗算の前に、桁の拡張処理を行う。なお、ここではxに関する分散情報の桁拡張処理についてのみ書く。yについては、同様の方法で拡張した結果のシェアの値の例を挙げる。
【０１５５】
また、拡張の処理の過程で、p*q=rを満たすランダムビット値p,q,rをサーバ１およびサーバ２の間で複数分散しているものとする。
(p[2]-p[1])mod2=p
(q[2]-q[1])mod2=q
(r[2]-r[1])mod2=r=p*q
ここで、サーバ１はp[1],q[1],r[1]を持ち、サーバ２はp[2],q[2],r[2]を持つ。
【０１５６】
また、xの桁の拡張では、６桁目から１０桁目を作るが、ここでは、６桁目に関する計算過程を記載し、残りの桁は同様の手順なので省略して、その拡張結果を示す。
【０１５７】
（６桁目の数値生成）
サーバ１において、x[1]{6}=(s[1]+c[1])mod2=1  によりx[1]の６桁目を生成する。
サーバ２において、x[2]{6}=(s[2]+c[2])mod2=1  によりx[2]の６桁目を生成する。
【０１５８】
（x[1]{6}=1の再分散）
サーバ１によって、x[1]{6}=1の再分散を行なう。なお、x[1][1]{6}を、x[1]{6}のサーバ１への分散値とし、x[2][1]{6}を、x[1]{6}のサーバ２への分散値とする。すなわち、(x[2][1]{6}-x[1][1]{6})mod2=x[1]{6}を満たす、x[2][1]{6}およびx[1][1]{6}を計算し、x[2][1]{6}をサーバ２へ送付する。
ここでは、x[1][1]{6}=1、 x[2][1]{6}=0とする。
【０１５９】
（x[2]{6}=1の再分散）
サーバ２によって、x[2]{6}=1の再分散を行なう。なお、x[1][2]{6}を、x[2]{6}のサーバ１への分散値とし、x[2][2]{6}を、x[2]{6}のサーバ２への分散値とする。すなわち、(x[2][2]{6}-x[1][2]{6})mod2=x[2]{6}を満たす、x[2][2]{6}およびx[1][2]{6}を計算し、x[1][2]{6}をサーバ１へ送付する。
ここでは、x[1][2]{6}=1、 x[2][2]{6}=0とする。
【０１６０】
（６桁目のキャリー生成）
以上の処理によって、６桁目のシェアが計算できたが、７桁目を計算するために６桁目から７桁目への桁上がり（キャリー）を計算する。６桁目からのキャリーであるc{6}は、x[1]{6}, x[2]{6}, cに関連し、表３の真理値表によって定まる。
【０１６１】
【表３】
0006988807.tif 000004
以上の真理値表は、
c{6}=(c+(x[1]{6}+x[2]{6})(x[2]{6}+c+1))mod2=(c+g*h)mod2  によって定まる。ここで、g=(x[1]{6}+x[2]{6})、h=(x[2]{6}+c+1)である。この処理を秘密計算により計算する。
【０１６２】
（gのシェアの計算）
g=x[1]{6}+x[2]{6}により、g[1]、g[2]をそれぞれ計算する。
サーバ１において、g[1]=(x[1][1]{6}+x[1][2]{6})mod2=(1+1)mod2=0  を算出する。
サーバ２において、g[2]=(x{2}[1]{6}+x{2}[2]{6})mod2=(0+0)mod2=0  を算出する。
【０１６３】
（hのシェアの計算）
h=x[2]{6}+c+1により、h[1]、h[2]をそれぞれ計算する。
サーバ１において、h[1]=(x[1][2]{6}+c[1])mod2=(1+1)mod2=0  を算出する。
サーバ２において、h[2]=(x[2][2]{6}+c[2]+1)mod2=(0+0+1)mod2=1  を算出する。
【０１６４】
（g*hの秘密計算）
g*hの秘密計算では、g*h=p*q+(g-p)*q+(h-q)*p+(g-p)*(h-q)であることを利用する。そして、サーバ間通信のため、例えば、p=q=r=1とし、p[1]=1, p[2]=0, q[1]=1, q[2]=0, r[1]=0, r[2]=1が事前に共通されているとする。サーバ１は、p[1],q[1],r[1]を有し、サーバ２はp[2],q[2],r[2]を有する。
【０１６５】
（g-pの秘密計算）
サーバ１において、(g[1]-p[1])mod2=(0-1)mod2=1  を算出して、サーバ２に送付する。
サーバ２において、(g[2]-p[2])mod2=(0-0)mod2=0  を算出して、サーバ１に送付する。
そして、サーバ１とサーバ２とのそれぞれにおいて、(g[2]-p[2]-(g[1]-p[1]))mod2を計算し、(g-p)=1を得る。
【０１６６】
（h-qの秘密計算）
サーバ１において、(h[1]-q[1])mod2=(0-1)mod2=1  を算出して、サーバ２に送付する。
サーバ２において、(h[2]-q[2])mod2=(1-0)mod2=1  を算出して、サーバ１に送付する。
そして、サーバ１とサーバ２とのそれぞれにおいて、(h[2]-q[2]-(h[1]-q[1]))mod2を計算し、(f-q)=0を得る。
【０１６７】
（g*hのシェアgh[1]とgh[2]との計算）
サーバ１において、gh[1]=(r[1]+(g-p)*q[1]+(h-q)*p[1])mod2=(0+1*1+0*1)mod2=1  を算出する。
サーバ２において、gh[2]=(r[2]+(g-p)*q[2]+(h-q)*p[2]+(g-p)*(h-q))mod2=(1+1*0+0*0+1*0)mod2=1  を算出する。
【０１６８】
（c{6}のシェアの計算）
サーバ１において、c[1]{6}=(c[1]+gh[1])mod2=(1+1)mod2=0  を算出する。
サーバ２において、c[2]{6}=(c[2]+gh[2])mod2=(0+1)mod2=1  を算出する。
【０１６９】
《拡張結果》
以上の手順を繰り返して用い、以下の７桁目〜１０桁目の値を計算する。
x[1]{7} =0, c[1]{7} =1、 x[2]{7} =0, c[2]{7} =0
x[1]{8} =1, c[1]{8} =1、 x[2]{8} =1, c[2]{8} =0
x[1]{9} =1, c[1]{9} =1、 x[2]{9} =1, c[2]{9} =0
x[1]{10}=1, c[1]{10}=0、 x[2]{10}=1, c[2]{10}=1
【０１７０】
以上の情報を、５桁のx'のシェアの上位桁につなげ、桁を１０桁に伸ばしたx'(10桁)のシェア、c'(キャリー)のシェア、および、s'(符号)のシェアを得る。なお、符号は変更されない。
x'[1]           ： 1110111000
x'[2]           ： 1110110100
c'[1]= c[1]{10} ： 0
c'[2]= c[2]{10} ： 1
s'[1]           ： 0
s'[2]           ： 1
を得る。
【０１７１】
同様に、５桁のy'のシェアの桁を上位に伸ばし、桁を１０桁に伸ばしたy'(10桁)のシェア、d'(キャリー)のシェア、および、t'(符号)のシェアを得る。なお、符号は変更されない。
y'[1]           ： 0100000100
y'[2]           ： 0100001001
d'[1]= d[1]{10} ： 1
d'[2]= d[2]{10} ： 1
t'[1]           ： 0
t'[2]           ： 0
【０１７２】
《秘密乗算》
次に、例えば、p=0110111000, q=1101011010, r=(p*q)mod2^10=1010110000をサーバ１とサーバ２とに分散した値、p[1]=1000110011, p[2]=1111101011, q[1]=1110011010, q[2]=1011110100, r[1]=1111110000, r[2]=1010100000を用いて、拡張したx'とy'の掛け算を実行する。サーバ１はp[1],q[1],r[1]を有し、サーバ２はp[2],q[2],r[2]を有する。
【０１７３】
そして、サーバ１の乗算分散値として、x'y'[1]=(r[1]+(x'-p)*q[1]+(y'-q)*p[1])mod2^10を算出し、サーバ２の乗算分散値として、x'y'[2]=(r[2]+(x'-p)*q[2]+(y'-q)*p[2]+(x'-p)*(y'-q))mod2^10を算出する。
【０１７４】
（x'-pに相当する値の秘密計算）
サーバ１において、(x'[1]-p[1])mod2^10=0110000101を算出し、サーバ２に送付する。
サーバ２において、(x'[2]-p[2])mod2^10=1111001001を算出し、サーバ１に送付する。
サーバ１およびサーバ２のそれぞれにおいて、(x'[2]-p[2]-(x'[1]-p[1]))mod2^10を計算して、(x'-p)に相当する値=1001000100を得る。
【０１７５】
（y'-qに相当する値の秘密計算）
サーバ１において、(y'[1]-q[1])mod2^10=0101101010を算出し、サーバ２に送付する。
サーバ２において、(y'[2]-q[2])mod2^10=1000010101を算出して、サーバ１に送付する。
サーバ１およびサーバ２のそれぞれにおいて、(y'[2]-q[2]-(y'[1]-q[1]))mod2^10を計算して、(y'-q)に相当する値=0010101011を得る。
【０１７６】
（乗算結果のシェア算出）
サーバ１において、x'y'[1]=(r[1]+(x'-p)*q[1]+(y'-q)*p[1])mod2^10=0011101001を算出して、乗算結果のサーバ１のシェアとする。
サーバ２において、x'y'[2]=(r[2]+(x'-p)*q[2]+(y'-q)*p[2]+(x'-p)*(y'-q))mod2^10=0011010101を算出して、乗算結果のサーバ１のシェアとする。
【０１７７】
なお、x'y'[1]とx'y'[2]とのシェアから、(0011010101-0011101001)mod2^10を計算すると、桁を拡張した秘密乗算結果の1111101100が復元されることが分かる。
【０１７８】
《秘密乗算の後処理》
（桁の切り捨て処理）
各サーバのシェアに対して、下位１桁と上位４桁とを切除して長さを揃える。具体的には、x'y'[1]の２桁目から６桁目を切り出し、xy'[1]=10100とする。また、x'y'[2]の２桁目から６桁目を切り出し、xy'[2]=01010とする。これらが乗算結果のデータ値のシェアである。
【０１７９】
（新しいキャリーの計算）
xy'[1]とxy'[2]の各桁と各桁に対するキャリーの分散値から次の桁へのキャリーの分散値を、下位桁から計算すればよい。この秘密計算は、先に桁の拡張を行った際に用いたものと同じ方法でよい。ただし、１桁目のキャリーは０が分散された値を決定的に用いる。仮にサーバ１が所有する値をc[1]、サーバ２が所有する値をc[2]とするならば、(0,0)の組み合わせか、(1,1)の組み合わせのいずれかを使用することを定めておけばよい。ここでは,サーバ１のキャリーのシェアをe[1]=1、サーバ２のキャリーのシェアをe[2]=0とする。
【０１８０】
（新しい符号の計算）
xy'の符号は、(xの符号+yの符号)mod2の秘密計算で求まる。これは、各サーバがxの符号とyの符号のシェアとの和をとってmod2を計算すればよい。今回の場合、xの符号であるs=1が、s[1]=0とs[2]=1とに分散されており、yの符号であるt=0が、t[1]=0とt[2]=0とに分散されている。x*yの符号のサーバ１のシェアu[1]は、(s[1]+t[1])mod2=0、x*yの符号のサーバ２のシェアu[2]は、(s[2]+t[2])mod2=1となる。したがって、(u[2]-u[1])mod2=1となって、xyの符号となっていることが確認できる。
【０１８１】
《最終乗算結果》
サーバ１は、xy'[1]=10100, e[1]=1, u[1]=0を有し、
サーバ２は、xy'[2]=01010, e[2]=0, u[2]=1を有する。
【０１８２】
これらが固定小数点数xとyを掛けた結果のシェアである。(01010-10100)mod2^5=10110であり、これは、-5.0に相当する。このように、秘密乗算により数値を秘匿したまま、正しい計算結果が得られていることが分かる。なお、桁を切り捨てることによって誤差が生じる可能性がある。
【０１８３】
本実施形態によれば、各固定小数点数の分散データ値と分散符号値と分散キャリー値とを生成して、分散データ値の秘密乗算と分散キャリー値の秘密計算とを独立させたので、被計算値や計算結果や計算途中の値を知ることができない秘密乗算を、全体の通信量を抑えて実行することができる。
【０１８４】
例えば、上記具体例における、５ビットの固定小数点数においては、次のような通信量で秘密乗算が可能となった。
【０１８５】
まず、１０ビットの拡張固定小数点数の拡張分散データ値と拡張分散キャリー値の秘密計算時の通信量は、１ビット当たり６ビットで、５ビット拡張で２つの拡張固定小数点数なので、６０（＝６×５×２）ビットとなる。次に、１０ビットの拡張固定小数点数の分散データ値の秘密乗算においては、４０（１０×４）ビットとなる。また、秘密乗算結果の分散キャリー値の秘密計算を上記拡張処理と同等とすると、６０ビットとなる。
【０１８６】
したがって、秘密乗算における秘密計算装置間の通信量は、固定小数点数の１ビット当たり３２（＝｛６０＋４０＋６０｝／５）ビットとなり、［非特許文献４］における１ビット当たり数百ビットの通信量を大幅に削減することができた。
【０１８７】
［他の実施形態］
なお、本実施形態では、加法型(2,2)法を用いることを前提に固定小数点数の分散と秘密乗算とについて説明した。しかしながら、加法型(2,2)法の代わりに、他の加法型(k,n)法や加法型(k,n)法に基づく秘密計算法によっても、固定小数点数の分散と秘密乗算とが実行でき、本発明と同様の全体の通信量を抑えるという効果を奏することができる。すなわち、本発明の固定小数点数の分散情報は、データ値、符号、キャリーに分けて分散されるが、これらのそれぞれを加法型(k,n)法で分散し、秘密計算も分散処理に用いた加法型(k,n)法に対応する方法で実行する構成である。
【０１８８】
また、本実施形態では、各分散値を秘密計算装置内の記憶部に記憶したが、記憶装置を秘密計算装置の外部に設けて、秘密計算装置は秘密計算を集中処理してもよい。
【０１８９】
また、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【０１９０】
また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する情報処理プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされるプログラム、あるいはそのプログラムを格納した媒体、そのプログラムをダウンロードさせるＷＷＷ(World Wide Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、上述した実施形態に含まれる処理ステップをコンピュータに実行させるプログラムを格納した非一時的コンピュータ可読媒体（non-transitory computer readable medium）は本発明の範疇に含まれる。
【０１９１】
［実施形態の他の表現］
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
少なくとも２つの固定小数点数から、各固定小数点数を加法型の秘密分散法を用いて分散した分散データ値と、分散符号値と、分散キャリー値と、を生成する分散情報生成装置と、
前記各固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を、秘密を保持しながら生成する秘密桁拡張手段と、
分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算手段と、
を有する少なくとも２台の秘密計算装置を含む秘密計算装置群と、
を備える、秘密計算システム。
（付記２）
前記分散情報生成装置は、
前記少なくとも２つの固定小数点数から、前記固定小数点数のデータ値を加法型の秘密分散法を用いて分散した分散データ値と、前記固定小数点数の符号を前記加法型の秘密分散法を用いて分散した分散符号値と、前記データ値を分散した際に発生したキャリー値を、前記加法型の秘密分散法を用いて分散した分散キャリー値と、をそれぞれ生成する分散情報生成手段を有し、
前記秘密計算装置群は、
第１固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、第２固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成する秘密桁拡張手段と、
前記第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値と、前記第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを用いて、前記第１拡張固定小数点数と前記第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算手段と、
を有する、付記１に記載の秘密計算システム。
（付記３）
前記秘密計算装置群は、それぞれ分散された値を記憶する少なくとも第１秘密計算装置と第２秘密計算装置とを備え、前記少なくとも第１秘密計算装置と第２秘密計算装置との間でのデータの秘密交換を伴って前記秘密桁拡張手段による桁拡張処理および前記秘密乗算手段による乗算処理を実行し、
前記データの秘密交換は、前記データと同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記第１秘密計算装置と前記第２秘密計算装置とに分散し、分散された数を用いて実行される、付記１または２に記載の秘密計算システム。
（付記４）
前記秘密乗算手段は、
前記拡張乗算結果の拡張分散データ値の下位桁を切除する下位桁切除手段と、
前記拡張乗算結果の分散符号値を抽出する符号抽出手段と、
前記拡張乗算結果の分散キャリー値を抽出するキャリー抽出手段と、
を有する付記１乃至３のいずれか１項に記載の秘密計算システム。
（付記５）
前記秘密桁拡張手段は、
１桁の２つのランダム数と前記ランダム数の積とを、加法型の秘密分散法を用いて前記第１秘密計算装置と前記第２秘密計算装置とに分散するランダム数分散手段と、
前記第１秘密計算装置において、前記固定小数点数の第１分散データ値の最上位桁の値と、第１分散符号値と、第１分散キャリー値とから、（最上位＋１）桁の第１分散データ値を算出し、前記第２秘密計算装置において、前記固定小数点数の第２分散データ値の最上位桁の値と、第２分散符号値と、第２分散キャリー値とから、（最上位＋１）桁の第２分散データ値を算出する拡張桁データ生成手段と、
算出された（最上位＋１）桁の第１分散データ値および第２分散データ値のそれぞれを、前記第１秘密計算装置と前記第２秘密計算装置とに分散する拡張桁データ分散手段と、
前記分散された（最上位＋１）桁の第１分散データ値および第２分散データ値と、最上位桁の分散キャリー値と、前記２つのランダム数および前記ランダム数の積の分散ランダム数とを用いて、前記第１秘密計算装置と前記第２秘密計算装置とが協働して、（最上位＋１）桁の第１分散キャリー値と第２分散キャリー値とを生成する拡張桁キャリー生成手段と、
算出された（最上位＋１）桁の第１分散キャリー値および第２分散キャリー値のそれぞれを、前記第１秘密計算装置と前記第２秘密計算装置とに分散する拡張桁キャリー分散手段と、
前記拡張桁データ生成手段による上位桁の分散データ値の算出と、前記拡張桁データ分散手段による上位桁の分散データ値の分散と、前記拡張桁キャリー生成手段による上位桁の分散キャリー値の算出と、前記拡張桁キャリー分散手段による上位桁の分散キャリー値の分散とを上位桁に向かって繰り返し、算出された拡張桁数の第１分散データ値を前記固定小数点数の第１分散データ値の上位に追加して前記拡張固定小数点数の第１拡張分散データ値とし、算出された拡張最上位桁の拡張分散キャリー値を前記拡張固定小数点数の第１拡張分散キャリー値とし、算出された拡張桁数の第２分散データ値を前記固定小数点数の第２分散データ値の上位に追加して前記拡張固定小数点数の第２拡張分散データ値とし、算出された拡張最上位桁の拡張分散キャリー値を前記拡張固定小数点数の第２拡張分散キャリー値とする、拡張固定小数点数生成手段と、
を有し、
前記第１固定小数点数および前記第２固定小数点数のそれぞれに対して、前記第１拡張分散データ値と前記第２拡張分散データ値、および、第１拡張分散キャリー値と第２拡張分散キャリー値、を生成する、付記３または４に記載の秘密計算システム。
（付記６）
前記秘密乗算手段は、
拡張固定小数点数と同じ桁の２つのランダム数と前記ランダム数の積とを、加法型の秘密分散法を用いて前記第１秘密計算装置と前記第２秘密計算装置とに分散するランダム数分散手段と、
前記第１拡張固定小数点数および前記第２拡張固定小数点数の拡張分散データ値と、前記２つのランダム数および前記ランダム数の積の分散ランダム数とを用いて、前記第１秘密計算装置と前記第２秘密計算装置とが協働して秘密を保持しながら秘密乗算を実行し、前記拡張乗算結果の拡張分散データ値を算出する拡張乗算手段と、
前記拡張乗算結果の拡張分散データ値の桁を調整して、前記乗算結果の分散データ値を生成する桁調整手段と、
を有する付記３乃至５のいずれか１項に記載の秘密計算システム。
（付記７）
前記分散情報生成装置が生成した前記分散情報を記憶するための記憶装置をさらに備える、付記１乃至６のいずれか１項に記載の秘密計算システム。
（付記８）
少なくとも２つの固定小数点数から、各固定小数点数を加法型の秘密分散法を用いて分散した分散データ値と、分散符号値と、分散キャリー値と、を生成する分散情報生成ステップと、
前記各固定小数点数の分散データ値と分散符号値と分散キャリー値とを用いて、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を、秘密を保持しながら生成する秘密桁拡張ステップと、
分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを秘密を保持しながら生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算ステップと、
を含む秘密計算システムの秘密計算方法。
（付記９）
少なくとも２つの固定小数点数のデータ値を、秘密乗算のために加法型の秘密分散法を用いて分散するデータ値分散手段と、
前記少なくとも２つの固定小数点数の符号を、前記秘密乗算のために加法型の秘密分散法を用いて分散する符号分散手段と、
前記少なくとも２つの固定小数点数のデータ値を加法型の秘密分散法を用いて分散した際に発生したキャリーを、前記秘密乗算のために加法型の秘密分散法を用いて分散するキャリー分散手段と、
を備える分散情報生成装置。
（付記１０）
前記加法型の秘密分散法は、秘密計算法が利用可能な加法型(2,2)法である、付記９に記載の分散情報生成装置。
（付記１１）
少なくとも２つの固定小数点数のデータ値を、秘密乗算のために加法型の秘密分散法を用いて分散するデータ値分散ステップと、
前記少なくとも２つの固定小数点数の符号を、前記秘密浄罪のために加法型の秘密分散法を用いて分散する符号分散ステップと、
前記少なくとも２つの固定小数点数のデータ値を加法型の秘密分散法を用いて分散した際に発生したキャリーを、前記秘密乗算のために加法型の秘密分散法を用いて分散するキャリー分散ステップと、
を含む分散情報生成方法。
（付記１２）
少なくとも２つの固定小数点数のデータ値を、秘密乗算のために加法型の秘密分散法を用いて分散するデータ値分散ステップと、
前記少なくとも２つの固定小数点数の符号を、前記秘密乗算のために加法型の秘密分散法を用いて分散する符号分散ステップと、
前記少なくとも２つの固定小数点数のデータ値を加法型の秘密分散法を用いて分散した際に発生したキャリーを、前記秘密乗算のために加法型の秘密分散法を用いて分散するキャリー分散ステップと、
をコンピュータに実行させる分散情報生成プログラム。
（付記１３）
少なくとも２つの固定小数点数の分散データ値と分散符号値と分散キャリー値とを用い、各固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を生成する秘密桁拡張手段と、
各拡張固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算手段と、
を備える秘密計算装置。
（付記１４）
前記秘密桁拡張手段は、
第１固定小数点数の分散データ値と分散符号値と分散キャリー値とを用い、前記第１固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、桁数を拡張した第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、第２固定小数点数の分散データ値と分散符号値と分散キャリー値とを用い、前記固定第２小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、桁数を拡張した第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、
前記秘密乗算手段は、
前記第１拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値と、前記第２拡張固定小数点数の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを用い、前記第１拡張固定第１小数点数および前記第２拡張固定小数点数の他の分散値により生成された拡張乗算結果の拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、前記第１拡張固定小数点数と前記第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、前記拡張乗算結果の分散値の桁数を調整して秘密乗算結果の分散値とする、
付記１３に記載の秘密計算装置。
（付記１５）
前記秘密計算装置は、他の秘密計算装置との間でのデータの秘密交換を伴って前記秘密桁拡張手段による桁拡張処理および前記秘密乗算手段による乗算処理を実行し、
前記データの秘密交換は、前記データと同じ桁の少なくとも２つのランダム数と該ランダム数の積とを、加法型の秘密分散法を用いて前記秘密計算装置と前記他の秘密計算装置とに分散し、分散された数を用いて実行される、付記１３または１４に記載の秘密計算装置。
（付記１６）
前記秘密乗算手段は、
前記拡張乗算結果の拡張分散データ値の下位桁を切除する下位桁切除手段と、
前記拡張乗算結果の分散符号値を抽出する符号抽出手段と、
前記拡張乗算結果の分散キャリー値を抽出するキャリー抽出手段と、
を有する付記１３乃至１５のいずれか１項に記載の秘密計算装置。
（付記１７）
前記秘密桁拡張手段は、
１桁の２つのランダム数と前記ランダム数の積とが加法型の秘密分散法を用いて分散された分散ランダム数を取得するランダム数取得手段と、
前記固定小数点数の第１分散データ値の最上位桁の値と、第１分散符号値と、第１分散キャリー値とから、（最上位＋１）桁の第１分散データ値を算出する拡張桁データ生成手段と、
算出された前記（最上位＋１）桁の第１分散データ値を、前記秘密計算装置と前記他の秘密計算装置とに分散する拡張桁データ分散手段と、
前記他の秘密計算装置において算出された前記固定小数点数の（最上位＋１）桁の第２分散データ値の分散値を取得する拡張桁データ取得手段と、
前記（最上位＋１）桁の第１分散データ値の分散値および前記（最上位＋１）桁の第２分散データ値の分散値と、最上位桁の分散キャリー値と、前記２つのランダム数および前記ランダム数の積の分散ランダム数とを用いて、（最上位＋１）桁の第１分散キャリー値を生成する拡張桁キャリー生成手段と、
算出された前記（最上位＋１）桁の第１分散キャリー値を、前記第１秘密計算装置と前記第２秘密計算装置とに分散する拡張桁キャリー分散手段と、
前記拡張桁データ生成手段による上位桁の分散データ値の算出と、前記拡張桁データ分散手段による上位桁の分散データ値の分散と、前記拡張桁キャリー生成手段による上位桁の分散キャリー値の算出と、前記拡張桁キャリー分散手段による上位桁の分散キャリー値の分散とを上位桁に向かって繰り返し、算出された拡張桁数の第１分散データ値を前記固定小数点数の第１分散データ値の上位に追加して前記拡張固定小数点数の第１拡張分散データ値とし、算出された拡張最上位桁の拡張分散キャリー値を前記拡張固定小数点数の第１拡張分散キャリー値とする、拡張固定小数点数生成手段と、
を有し、
前記第１固定小数点数および前記第２固定小数点数のそれぞれに対して、前記第１拡張分散データ値および第１拡張分散キャリー値を生成する、付記１５または１６に記載の秘密計算装置。
（付記１８）
前記秘密乗算手段は、
拡張固定小数点数と同じ桁の２つのランダム数と前記ランダム数の積とを、加法型の秘密分散法を用いて分散した分散ランダム数を取得するランダム数取得手段と、
前記２つのランダム数および前記ランダム数の積の分散ランダム数により秘匿化された、前記第１拡張固定小数点数および前記第２拡張固定小数点数の第２拡張分散データ値を前記他の秘密計算装置から取得する拡張分散データ値取得手段と、
前記第１拡張固定小数点数および前記第２拡張固定小数点数の第１拡張分散データ値と、前記秘匿化された前記第１拡張固定小数点数および前記第２拡張固定小数点数の第２拡張分散データ値とに基づいて、前記拡張乗算結果の第１拡張分散データ値を算出する拡張乗算手段と、
前記拡張乗算結果の第１拡張分散データ値の桁を調整して、前記乗算結果の第１分散データ値を生成する桁調整手段と、
を有する付記１７に記載の秘密計算装置。
（付記１９）
少なくとも２つの固定小数点数の分散データ値と分散符号値と分散キャリー値とを用い、各固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を生成する秘密桁拡張ステップと、
各拡張固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算ステップと、
を含む秘密計算装置の秘密計算方法。
（付記２０）
少なくとも２つの固定小数点数の分散データ値と分散符号値と分散キャリー値とを用い、各固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、桁数を拡張した拡張分散データ値と拡張分散符号値と拡張分散キャリー値とからなる分散された各拡張固定小数点数を生成する秘密桁拡張ステップと、
各拡張固定小数点数の他の分散値により生成された拡張分散データ値および拡張分散キャリーを、秘密を保持して参照しながら、分散された第１拡張固定小数点数と第２拡張固定小数点数とを乗算した拡張乗算結果の拡張分散データ値と拡張分散符号値と拡張分散キャリー値とを生成し、前記拡張乗算結果の拡張分散データ値の桁数を調整して秘密乗算結果の分散値とする秘密乗算ステップと、
をコンピュータに実行させる秘密計算プログラム。
【０１９２】
この出願は、２０１６年８月１８日に出願された日本国特許出願  特願２０１６−１６０３８３号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
0006988807.tif 000005
【図２】
0006988807.tif 000006
【図３】
0006988807.tif 000007
【図４】
0006988807.tif 000008
【図５】
0006988807.tif 000009
【図６】
0006988807.tif 000010
【図７】
0006988807.tif 000011
【図８】
0006988807.tif 000012
【図９Ａ】
0006988807.tif 000013
【図９Ｂ】
0006988807.tif 000014