(57)【要約】  数値分散装置は、数値wとパラメータpとを取得し、ゼロ以上でパラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成し、数値wとパラメータpと第１の乱数r1と第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算し、第１乃至第３の乱数r1, r2, r3とパラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1、s2、s3を計算し、第1の断片s1と第２の乱数r2の組、第２の断片s2と第３の乱数r3の組、および第３の断片s3 と第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する。
2018211653.tif 000002
【特許請求の範囲】
【請求項１】
数値wとパラメータpとを取得する取得回路部と、
ゼロ以上で前記パラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成する乱数生成回路部と、
前記数値wと前記パラメータpと前記第１の乱数r1と前記第２の乱数r2とから、数式r3=w-r1-r2 mod p に従って、第３の乱数r3を計算する乱数計算回路部と、
前記第１乃至第３の乱数r1, r2, r3と前記パラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算する断片計算回路部と、
前記第1の断片s1と前記第２の乱数r2の組、前記第２の断片s2と前記第３の乱数r3の組、および前記第３の断片s3 と前記第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する送信回路部と
を備える数値分散装置。
【請求項２】
請求項１に記載の数値分散装置で生成された、数値wAを分散した数値sA, tAと、数値wBを分散した数値sB, tBと、パラメータpとを入力として送信情報uを生成する送信情報生成装置であって、
前記数値sA, tA, sB, tBを取得する情報取得回路部と、
擬似乱数生成処理によって２値の擬似乱数を生成して、前記パラメータpを用いて前記２値の擬似乱数の差rを生成する擬似乱数差生成回路部と、
前記数値sA, tA, sB, tBと前記パラメータpとを用いて、数式tAtB-sAsB +  r mod p に従って前記送信情報ｕを計算する送信情報計算回路部と、
前記送信情報ｕを送信する送信回路部と、
を備える送信情報生成装置。
【請求項３】
各々が請求項２に記載の送信情報生成装置を含む第１乃至第３の秘密計算装置から成る秘密計算システムに用いられる秘密計算装置であって、
当該秘密計算装置の前記送信情報生成装置が生成した送信情報u1と、隣接する秘密計算装置の前記送信情報生成装置が生成した送信情報u3とを取得する送信情報取得回路部と、
前記送信情報u1, u3と前記パラメータpとから、数式u1+u3 mod pによって断片sを計算する断片計算回路部と、
前記断片sと前記送信情報 u1とを外部記憶装置に格納する情報格納回路部と、
から成る分散情報整形装置を備えることを特徴とする秘密計算装置。
【請求項４】
請求項３に記載の秘密計算装置を３台備える、秘密計算システム。
【請求項５】
数値wとパラメータpとを取得し、
ゼロ以上で前記パラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成し、
前記数値wと前記パラメータpと前記第１の乱数r1と前記第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算し、
前記第１乃至第３の乱数r1, r2, r3と前記パラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算し、
前記第1の断片s1と前記第２の乱数r2の組、前記第２の断片s2と前記第３の乱数r3の組、および前記第３の断片s3 と前記第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する
数値分散方法。
【請求項６】
請求項５に記載の数値分散方法で生成された、数値wAを分散した数値sA, tAと、数値wBを分散した数値sB, tBと、パラメータpとを入力として送信情報uを生成する送信情報生成方法であって、
前記数値sA, tA, sB, tBを取得し、
擬似乱数生成処理によって２値の擬似乱数を生成して、前記パラメータpを用いて前記２値の擬似乱数の差rを生成し、
前記数値sA, tA, sB, tBと前記パラメータpとを用いて、数式tAtB-sAsB+r mod pに従って前記送信情報ｕを計算し、
前記送信情報ｕを送信する、
送信情報生成方法。
【請求項７】
各々が請求項６に記載の送信情報生成方法を実施する第１乃至第３の秘密計算装置から成る秘密計算システムに用いられる秘密計算装置で実施される分散乗算方法あって、
当該秘密計算装置の前記送信情報生成方法で生成した送信情報u1と、隣接する秘密計算装置の前記送信情報生成方法で生成した送信情報u3とを取得し、
前記送信情報u1, u3と前記パラメータpとから、数式u1+u3 mod pによって断片sを計算し、
前記断片sと前記送信情報 u1とを外部記憶装置に格納する、
分散乗算方法。
【請求項８】
数値分散プログラムを記録したプログラム記録媒体であって、
前記数値分散プログラムは、コンピュータに、
数値wとパラメータpとを取得する機能と、
ゼロ以上で前記パラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成する機能と、
前記数値wと前記パラメータpと前記第１の乱数r1と前記第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算する機能と、
前記第１乃至第３の乱数r1, r2, r3と前記パラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算する機能と、
前記第1の断片s1と前記第２の乱数r2の組、前記第２の断片s2と前記第３の乱数r3の組、および前記第３の断片s3 と前記第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する機能と、
を実現させるプログラム記録媒体。
【請求項９】
請求項８に記載の数値分散プログラムを使用して生成された、数値wAを分散した数値sA, tAと、数値wBを分散した数値sB, tBと、パラメータpとを入力として送信情報uを生成する送信情報生成プログラムを記録したプログラム記録媒体であって、
前記送信情報生成プログラムは、コンピュータに、
前記数値sA, tA, sB, tBを取得する機能と、
擬似乱数生成処理によって２値の擬似乱数を生成して、前記パラメータpを用いて前記２値の擬似乱数の差rを生成する機能と、
前記数値sA, tA, sB, tBと前記パラメータpとを用いて、数式tAtB-sAsB+r mod pに従って前記送信情報ｕを計算する機能と、
前記送信情報ｕを送信する機能と、
を実現させるプログラム記録媒体。
【請求項１０】
各々が請求項９に記載の送信情報生成プログラムを実施する第１乃至第３の秘密計算装置から成る秘密計算システムに用いられる分散乗算プログラムを記録したプログラム記録媒体あって、
前記分散乗算プログラムは、秘密計算装置であるコンピュータに、
当該秘密計算装置の前記送信情報生成プログラムを使用して生成した送信情報u1と、隣接する秘密計算装置の前記送信情報生成プログラムを使用して生成した送信情報u3とを取得する機能と、
前記送信情報u1, u3と前記パラメータpとから、数式u1+u3 mod pによって断片sを計算する機能と、
前記断片sと前記送信情報 u1とを外部記憶装置に格納する機能と、
を実現させるプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、数値分散装置、送信情報生成装置、秘密計算装置、方法、プログラム記録媒体、および秘密計算システムに関する。
【背景技術】
【０００２】
秘密計算方法とは、複数の秘密計算装置が互いに通信を介しながら計算することで、与えられた関数を計算する方法である。そして、秘密計算方法は、これらのいずれの秘密計算装置も十分な数の秘密計算装置間で互いに扱うデータを共有しない限り、関数への入力や関数の出力に関する情報を得ることができない特徴を持つ。【０００３】
公知の秘密計算方法として、非特許文献１に記載の方法が知られている。【０００４】
非特許文献１に記載の秘密計算方法は、３台の秘密計算装置によって実現される。後で詳細に説明するように、非特許文献１に記載の秘密計算方法では、積の計算を、各秘密計算装置において乗算２回、除算１回行って実現している。【０００５】
特許文献１は、数値Ｘを３つの計算装置で分散して記録し、秘密計算を行う秘密計算システムを開示している。３つの計算装置は、数値の断片（分散された情報）を分散して記録し、秘密計算を行う。第１乃至第３の計算装置が記憶する断片を、それぞれ、（ｘ０、ｘ１）、（ｘ１、ｘ２）、（ｘ２、ｘ０）と示すことにすると、数値Ｘと断片とは、Ｘ＝ｘ０＋ｘ１＋ｘ２  ｍｏｄ  Ｍの関係を満たす。但し、Ｍは２以上の整数である。例えば、整数Ａの秘密分散は次のように行われる。（１）０以上Ｍ未満の整数の乱数ａ０、ａ１を生成する。（２）ａ２＝Ａ−ａ０−ａ１を計算し、断片を（ａ０、ａ１）、（ａ１、ａ２）、（ａ２、ａ０）とし、第１乃至第３の計算装置に分散して記録する。【０００６】
特許文献２は、ビット表現された２つの整数を秘匿計算でビット加算する計算装置を開示している。Ｎ台の計算装置で有限体Ｚｑに属する整数ａを秘密分散する方法として、（Ｋ−１）次多項式ｆ＿ａ（ｘ）を用いる方法がある（ただし、Ｋ＜Ｎ／２）。この方法では、例えば、ｆ＿ａ（０）＝ａとし、計算装置にｆ＿ａ（ｎ）を配る。配られる情報ｆ＿ａ（ｎ）を整数ａの断片と呼ぶ。このとき、Ｋ台の計算装置が協力すれば（Ｋ−１）次多項式ｆ＿ａ（ｘ）を解くことができるので、ｆ＿ａ（０）を求めることができる。加算結果の断片を秘密分散する場合、ａ＋ｂ  ｍｏｄ  ｑに対する断片を求めるためには、計算装置は個別に、
ｆ＿ａ＋ｂ（ｎ）＝ｆ＿ａ（ｎ）＋ｆ＿ｂ（ｎ）  ｍｏｄ  ｑ
を計算する。各計算装置が個別に計算すればよいので、計算装置間での通信は不要である。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１２−０７８４４６号公報
【特許文献２】特開２０１４−１３７７４０号公報
【非特許文献】
【０００８】
【非特許文献１】Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, Kazuma Ohara, "High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority", ACM-CCS 2016
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記述される方法は、通信を必要とせず加減算を分散したまま計算することができる。また少ない通信（各秘密計算装置が１つの値を送り、１つ受け取る）で積を分散したまま計算することができる。【００１０】
しかしながら、非特許文献１に開示された方法では、積の計算には、各秘密計算装置において乗算２回と、除算１回を必要とする。除算は、３の逆元を定数とみなすと乗算を行うことと同等のコストとみなすこともできるが、乗算は加・減算に比べて重い処理であるので削減したい。【００１１】
また、非特許文献１に開示された方法は、３の逆元が存在しないような法では用いることができない点も問題である。【００１２】
特許文献１は、単に、整数の断片（分散された情報）を分散して記録し、秘密計算を行う秘密計算システムを開示しているに過ぎない。【００１３】
特許文献２は、加算結果の断片を秘密分散する場合、各計算装置が個別に所定の計算を行うことを開示しているに過ぎない。【００１４】
本発明の目的は、上述した課題を解決する、数値分散装置、送信情報生成装置、秘密計算装置、方法、プログラム記録媒体、および秘密計算システムを提供することにある。
【課題を解決するための手段】
【００１５】
本発明の数値分散装置は、数値wとパラメータpとを取得する取得回路部と、ゼロ以上でパラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成する乱数生成回路部と、数値wとパラメータpと第１の乱数r1と第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算する乱数計算回路部と、第１乃至第３の乱数r1, r2, r3とパラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算する断片計算回路部と、第1の断片s1と第２の乱数r2の組、第２の断片s2と第３の乱数r3の組、および第３の断片s3 と第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する送信回路部とを備える。【００１６】
本発明の数値分散方法は、数値wとパラメータpとを取得し、ゼロ以上でパラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成し、数値wとパラメータpと第１の乱数r1と第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算し、第１乃至第３の乱数r1, r2, r3とパラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算し、第1の断片s1と第２の乱数r2の組、第２の断片s2と第３の乱数r3の組、および第３の断片s3 と第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する。【００１７】
本発明のプログラム記録媒体は、数値分散プログラムを記録したプログラム記録媒体であって、上記数値分散プログラムは、コンピュータに、数値wとパラメータpとを取得する機能と、ゼロ以上でパラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成する機能と、数値wとパラメータpと第１の乱数r1と第２の乱数r2とから、数式r3 = w-r1-r2 mod p に従って、第３の乱数r3を計算する機能と、第１乃至第３の乱数r1, r2, r3とパラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1, s2, s3を計算する機能と、第1の断片s1と第２の乱数r2の組、第２の断片s2と第３の乱数r3の組、および第３の断片s3 と第１の乱数r1の組を、それぞれ、第１乃至第３の秘密計算装置へ送信する機能と、を実現させる。
【発明の効果】
【００１８】
本発明によれば、上記のようにして生成した分散値を使用することにより、積の計算を、各秘密計算装置において乗算２回で実行することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】非特許文献１に記載された関連技術の秘密計算システムの構成例を示すブロック図である。
【図２】本発明の実施の形態に係る秘密計算システムの一構成例を示すブロック図である。
【図３】本発明の実施の形態に係る数値分散装置と第１乃至第３の秘密計算装置との関係を示すブロック図である。
【図４】第１乃至第３の秘密計算装置が２つの分散された値に関する乗算を実行し、その結果の分散値を保管する際の、実施の形態に係る秘密計算システムの一構成例を示すブロック図である。
【図５】図４において、第１および第３の秘密計算装置の内部構成の一例を詳細に示すブロック図である。
【図６】図３に示した数値分散装置によって数値を分散する動作を示すフローチャートである。
【図７】図４および図５に示した秘密計算システムにおいて乗算を実施する動作を示すフローチャートである。
【図８】図３に示した数値分散装置の内部構成の一例を詳細に示すブロック図である。
【図９】図４および図５に示した秘密計算システムの秘密計算装置に用いられる送信情報生成装置の内部構成の一例を詳細に示すブロック図である。
【図１０】図４および図５に示した秘密計算システムの第１の秘密計算装置に用いられる分散情報整形装置の内部構成の一例を詳細に示すブロック図である。
【発明を実施するための形態】
【００２０】
［関連技術］
本発明の理解を容易にするために、上記非特許文献１に記載の方法を用いて関連技術について説明する。図１に示されるように、この方法を実現する秘密計算システム１は３台の秘密計算装置によって実行される。ここでは、３台の秘密計算装置を、それぞれ、第１の秘密計算装置１−１、第２の秘密計算装置１−２、および第３の秘密計算装置１−３とする。
【００２１】
nを１以上の整数として、0以上、2^n-1以下の値wを３台の秘密計算装置１−１〜１−３で分散して保管するとする。ここで、2^n-1は２の（ｎ−１）乗を表す。この場合、合同式
r1+r2+r3 = 0 mod 2^n
を満たすランダムに選ばれた値（乱数）を用いて以下のように加工して３台の秘密計算装置１−１〜１−３で保管する。ここで、mod 2^nは、二つの整数が2^nを法として合同であることを意味し、それらを2^nで割ったときの余りが等しいことを意味する。したがって、上記合同式は、(r1+r2+r3)を2^nで割ったときの余りが0に等しいことを示している。
【００２２】
第１の秘密計算装置１−１は、wの分散値として(r1, r3-w mod 2^n)を保管する。第２の秘密計算装置１−２は、wの分散値として (r2, r1-w mod 2^n)を保管する。第３の秘密計算装置１−３は、wの分散値として（r3, r2-w mod 2^n)を保管する。
【００２３】
３台の秘密計算装置１−１〜１−３のうち２台の秘密計算装置が協力すると、値wを復元することができる。たとえば、第１の秘密計算装置１−１からのr1と、第２の秘密計算装置１−２からのr1-w mod 2^nとを用いて、
w = r1+(r1-w) mod 2^n 
と計算することができる。他の組み合わせも同様である。以降では、このように分散された値に関する加算（減算）処理、乗算処理について説明する。
【００２４】
[加算（減算）処理]
先に示した方法によって、第１の秘密計算装置１−１、第２の秘密計算装置１−２、および第３の秘密計算装置１−３に分散されて保管されている上記値wと値w'に関して実行される加算処理について説明する。
【００２５】
まず、各秘密計算装置１−１〜１−３がどのような値を保管しているかを示す。r1, r2, r3は
r1+r2+r3 = 0 mod 2^n
を満たすランダムに選ばれた値（乱数）であり、r1', r2', r3'は
r1'+r2'+r3' = 0 mod 2^n
を満たすランダムに選ばれた値（乱数）であるとする。
【００２６】
第１の秘密計算装置１−１は、wの分散値として
(s1, t1) = (r1, r3-w mod 2^n)
を保管し、w'の分散値として
(s1', t1') = (r1', r3'-w' mod 2^n)
を保管している。
【００２７】
第２の秘密計算装置１−２は、wの分散値 として
(s2, t2) = (r2, r1-w mod 2^n)
を保管し、w'の分散値 として
(s2', t2') = (r2', r1'-w' mod 2^n)
を保管している。
【００２８】
第３の秘密計算装置１−３は、wの分散値として 
(s3, t3) = (r3, r2-w mod 2^n)
を保管し、w'の分散値 として
(s3', t3') = (r3', r2'-w' mod 2^n)
を保管している。
【００２９】
各秘密計算装置１−１〜１−３は、以下の手順に従った処理を行う。
【００３０】
第１の秘密計算装置１−1は
(s1'', t1'') = (s1+s1' mod 2^n, t1+t1' mod 2^n)
によって(s1'', t1'')を計算し、w+w'の分散値として保管する。
【００３１】
第２の秘密計算装置１−2は
(s2'', t2'') = (s2+s2' mod 2^n, t2+t2' mod 2^n)
によって(s2'', t2'')を計算し、w+w'の分散値として保管する。
【００３２】
第３の秘密計算装置１−3は
(s3'', t3'') = (s3+s3' mod 2^n, t3+t3' mod 2^n)
によって(s3'', t3'')を計算し、w+w'の分散値として保管する。
【００３３】
それぞれの計算結果は、
w'' = w+w' mod 2^n
を前述の方法で分散したようにみなすことができる。これらの値から、w''を復元することができる。たとえば、第１の秘密計算装置１−１と第２の秘密計算装置１−２より
s1'' = r1+r1' mod2^n
と
t2'' = r1+r1'-w-w' mod 2^n
であるので
s1''-t2'' mod 2^n = w+w' mod 2^n
となる。これは他の秘密計算装置の組み合わせについても同様である。
【００３４】
減算の方法は加算と同様である。
【００３５】
[乗算処理について]
先に示した方法によって、第１の秘密計算装置１−１、第２の秘密計算装置１−２、および第３の秘密計算装置１−３に分散されて保管されている上記値wと値w'に関して実行される乗算処理について説明する。
【００３６】
まず、各秘密計算装置１−１〜１−３がどのような値を保管しているかを示す。r1, r2, r3は
r1+r2+r3 = 0 mod 2^n
を満たすランダムに選ばれた値（乱数）であり、r1', r2', r3'は
r1'+r2'+r3' = 0 mod 2^n
を満たすランダムに選ばれた値（乱数）であるとする。
【００３７】
第１の秘密計算装置１−１は、wの分散値として
(s1, t1) = (r1, r3-w mod 2^n)
を保管し、w'の分散値として
(s1', t1') = (r1', r3'-w' mod 2^n)
を保管する。
【００３８】
第２の秘密計算装置１−２は、wの分散値 として
(s2, t2) = (r2, r1-w mod 2^n)
を保管し、w'の分散値 として
(s2', t2') = (r2', r1'-w' mod 2^n)
を保管する。
【００３９】
第３の秘密計算装置１−３は、wの分散値として 
(s3, t3) = (r3, r2-w mod 2^n)
を保管し、w'の分散値 として
(s3', t3') = (r3', r2'-w' mod 2^n)
を保管する。
【００４０】
各秘密計算装置１−１〜１−３は、以下の手順に従った処理を行う。
【００４１】
なお、
r1''+r2''+r3'' = 0 mod 2^n
を満たすランダムに選ばれた値として、第１の秘密計算装置１−１はr1''を保管し、第２の秘密計算装置１−2はr2''を保管し、第３の秘密計算装置１−３はr3''を保管しているものとする。このような性質を満たすr1'', r2'', r3''は乗算を実行するたびに使い捨てで必要となる。このような３つの値を３台の秘密計算装置１−１〜１−３が効率的に生成する方法については後述する。
【００４２】
第１の秘密計算装置１−1は、
u1 = (t1t'1-s1s1'+r1'')/3 mod 2^n
を計算し、u1を第２の秘密計算装置１−２に送付する。ここで、/3は、３の逆元を意味し、３を掛けると１になる値を示す。
【００４３】
第２の秘密計算装置１−2は、
u2 = (t2t2'-s2s2'+r2'')/3 mod 2^n
を計算し、u2を第３の秘密計算装置１−３に送付する。
【００４４】
第３の秘密計算装置１−3は、
u3 = (t3t3'-s3s3'+r3'')/3 mod 2^n 
を計算し、u3を第１の秘密計算装置１−１に送付する。
【００４５】
第１の秘密計算装置１−1は、
(s1'', t1'') = (u3-u1mod 2^n, -2u3-r1 mod 2^n)
を計算し、(s1'', t1'')をww'の分散値として保管する。
【００４６】
第２の秘密計算装置１−2は、
(s2'', t2'') = (u1-u2 mod 2^n, -2u1-u2 mod 2^n)
を計算し、(s2'', t2'')をww'の分散値として保管する。
【００４７】
第３の秘密計算装置１−3は、
(s3'', t3'') = (u2-u3 mod 2^n, -2u2-u3 mod 2^n)
を計算し、(s3'', t3'')をww'の分散値として保管する。
【００４８】
まず、
u1+u2+u3
= (t1t'1-s1s1'+t2t2'-s2・s2'+t3・t3'-s3s3+r1''+r2''+r3'')/3 mod 2^n
= (3ww'-(r1+r2+r3)w'-(r1'+r2'+r3')w+r1''+r2''+r3'')/3 mod 2^n
= ww' mod 2^n
となっていることが確認できる。なお、2^n と3 とは互いに素なので、mod 2^n 上での3の逆元は必ず計算できる。
【００４９】
s1''-t2''
= u3-u1+2u1+u2
= u1+u2+u3
= ww' mod 2^n
であり、第１の秘密計算装置１−１と第２の秘密計算装置１−２の保管する値からww' mod 2^nが同じ計算方法で計算できることがわかる。他の秘密計算装置の組み合わせについても同様である。
【００５０】
[乱数の生成について]
次に、
r1+r2+r3 = 0 mod 2^n
のように３つ足すと0となる値を、第１の秘密計算装置１−１、第２の秘密計算装置１−２、および第３の秘密計算装置１−３が通信することなく、また、各秘密計算装置が所有する値を他の秘密計算装置に知られることのない方法で大量に生成する方法について説明する。ここでは、
r[i,1]+r[i,2]+r[i,3] = 0 mod 2^n
なるr[i,1], r[i,2], r[i,3]を多くのi = 1, …, Nに関して生成する方法を説明する。PRGを、鍵とインデックスとを入力としてnビットの数値列を出力する擬似乱数生成器とする。インデックスは、カウンタなどで良い。
【００５１】
まず、秘密計算装置のセットアップ処理として、PRGの第１乃至第３の鍵L1, L2, L3を生成する。第１の秘密計算装置１−1に第１の鍵L1と第３の鍵L3とを記憶させ、第２の秘密計算装置１−２に第２の鍵L2と第１の鍵L1とを記憶させ、第３の秘密計算装置１−3に第３の鍵L3と第２の鍵L2とを記憶させているものとする。
【００５２】
各秘密計算装置１−１〜１−３はカウンタなどで同期されたインデックスidxを共有しているものとする。
【００５３】
第１の秘密計算装置１−１は、第１の鍵L1とインデックスidxとをPRGに入力し、その出力であるnビットの数値をr'[1]を生成する。また、第１の秘密計算装置１−１は、第３の鍵L3とインデックスidxとをPRGに入力し、その出力であるnビットの数値をnビット毎に分割した値r'[3]を生成する。そして、第１の秘密計算装置１−１は、
r[1] = r'[1]-r'[3] mod 2^n
とする。
【００５４】
第２の秘密計算装置１−２は、第２の鍵L2とインデックスidxとをPRGに入力し、その出力であるnビットの数値r'[2]を生成する。また、第２の秘密計算装置１−２は、第１の鍵L1とインデックスidxとをPRGに入力し、その出力であるnビットの数値r'[1]を生成する。そして、第２の秘密計算装置１−２は、
r[2] = r'[2]-r'[1] mod 2^n
とする。
【００５５】
第３の秘密計算装置１−３は、第３の鍵L３とインデックスidxとをPRGに入力し、その出力であるnビットの数値r'[3]を生成する。また、第３の秘密計算装置１−３は、第２の鍵L2とインデックスidxとをPRGに入力し、その出力であるnビットの数値r'[2]を生成する。第３の秘密計算装置１−３は、
r[3] = r'[3]-r'[2] mod 2^nとする。
【００５６】
r[1]+r[2]+r[3]
= r'[1]-r'[3]+r'[2]-r'[1]+r[3]-r[2] = 0 mod 2^n
となっており、N組全てが条件を満たす。第１の秘密計算装置１−１が生成する値
r[1] = r'[1]-r'[3] mod 2^n
に着目すると、第３の秘密計算装置１−３はr'[1]を得られず、第２の秘密計算装置１−２はr'[3]を得られない。これより、第３の秘密計算装置１−３、第２の秘密計算装置２はr[1]を計算できないことがわかる。これは、r[2]やr[3]についても同様である。
【００５７】
セットアップ処理が済んでいれば、以上の処理は計算が行われる前などにも実行可能である。
【００５８】
このように、関連技術では、積の計算には、各秘密計算装置において乗算２回と、除算１回を必要とする。
【００５９】
［実施の形態］
次に、本発明の実施の形態について説明する。図２に示されるように、本実施形態による方法を実現する秘密計算システム１Ａは３台の秘密計算装置によって実行される。３台の秘密計算装置を、それぞれ第１の秘密計算装置１Ａ−１、第２の秘密計算装置１Ａ−２、および第３の秘密計算装置１Ａ−３とする。
【００６０】
pを１以上の整数として、0以上、p-1以下の値wを３台の秘密計算装置１Ａ−１〜１Ａ−３で分散して保管するとする。この場合、
r1+r2+r3 = w mod p
を満たすランダムに選ばれた値（乱数）を用いて以下のように加工して保管する。第１乃至第３の乱数r1, r2, r3は、r1とr2とをランダムに選択した後に
r3 = w-r1-r2 mod p
とすれば生成できる。
【００６１】
第１の秘密計算装置１Ａ−１は、wの分散値として(r1+r2 mod p, r2)を保管する。第２の秘密計算装置１Ａ−２は、wの分散値として (r2+r3 mod p, r3)を保管する。第３の秘密計算装置３は、wの分散値として（r3+r1 mod p, r1)を保管する。
【００６２】
3台の秘密計算装置１Ａ−１〜１Ａ−３のうち2台の秘密計算装置が協力するとwを復元することができる。たとえば、第１の秘密計算装置１Ａ−１からのr1+r2 mod p  と、第２の秘密計算装置１Ａ−２からのr3とを用いて、
w = r1+r2+r3 mod p 
と計算することができる。他の組み合わせも同様である。次に、このように分散された値に関する加算（減算）処理、乗算処理について説明する。
【００６３】
[加算（減算）処理]
先に示した方法によって、第１の秘密計算装置１Ａ−１、第２の秘密計算装置１Ａ−２、および第３の秘密計算装置１Ａ−３に分散されて保管されている上記値wと値w'に関して実行される加算処理について説明する。
【００６４】
まず、各秘密計算装置１Ａ−１〜１Ａ−３がどのような値を保管しているかを示す。r1, r2, r3は
r1+r2+r3 = w mod p
を満たすランダムに選ばれた値であり、r1', r2', r3'は
r1'+r2'+r3' = w' mod p
を満たすランダムに選ばれた値とする。
【００６５】
第１の秘密計算装置１Ａ−１は、wの分散値として
(s1, t1) = (r1+r2 mod p, r2)
を保管し、w'の分散値として
(s1', t1') = (r1'+r2' mod p, r2')
を保管している。
【００６６】
第２の秘密計算装置１Ａ−２は、wの分散値 として
(s2, t2) = (r2+r3 mod p, r3)
を保管し、w'の分散値 として
(s2', t2') = (r2'+r3' mod p, r3')
を保管している。
【００６７】
第３の秘密計算装置３は、wの分散値として
(s3, t3) = (r3+r1 mod p, r1)
を保管し、w'の分散値 として
(s3', t3') = (r3'+r1' mod p, r1')
を保管している。
【００６８】
各秘密計算装置は、以下の手順に従った処理を行う。
【００６９】
第１の秘密計算装置１Ａ−1は
(s1'', t1'') = (s1+s1' mod p, t1+t1' mod p)
によって(s1'', t1'')を計算し、w+w'の分散値として保管する。
【００７０】
第２の秘密計算装置１Ａ−2は
(s2'', t2'') = (s2+s2' mod p, t2+t2' mod p)
によって(s2'', t2'')を計算し、w+w'の分散値として保管する。
【００７１】
第３の秘密計算装置１Ａ−3は
(s3'', t3'') = (s3+s3' mod p, t3+t3' mod p)
によって(s3'', t3'')を計算し、w+w'の分散値として保管する。
【００７２】
この処理は上記非特許文献１の方法と同じである。
【００７３】
それぞれの計算結果は、
w'' = w+w' mod p
を前述の方法で分散した場合と同じ特徴を持つ。第１の秘密計算装置１Ａ−１と第２の秘密計算装置１Ａ−２より
s1'' = r1+r2+r1'+r2' mod p
と
t2' = r3+r3' mod p
であるので
s1''+t2'' mod p  = r1+r2+r3+r1'+r2'+r3' = w+w' mod p
となる。これは他の秘密計算装置の組み合わせについても同様である。
【００７４】
減算の方法は加算と同様である。
【００７５】
[乗算処理について]
先に示した方法によって、第１の秘密計算装置１Ａ−１、第２の秘密計算装置１Ａ−２、および第３の秘密計算装置１Ａ−３に分散されて保管されている上記値wと値w'に関して実行される乗算処理について説明する。
【００７６】
まず、各秘密計算装置がどのような値を保管しているかを示す。r1, r2, r3は
r1+r2+r3 = w mod p
を満たすランダムに選ばれた値であり、r1', r2', r3'は
r1'+r2'+r3' = w' mod p
を満たすランダムに選ばれた値とする。
【００７７】
第１の秘密計算装置１Ａ−１は、wの分散値として
(s1, t1) = (r1+r2 mod p, r2 )
を保管し、w'の分散値として
(s1', t1') = (r1'+r2' mod p, r2')
を保管する。
【００７８】
第２の秘密計算装置１Ａ−２は、wの分散値 として
(s2, t2) = (r2+r3 mod p, r3)
を保管し、w'の分散値 として
(s2', t2') = (r2'+r3' mod p, r3')
を保管する。
【００７９】
第３の秘密計算装置３は、wの分散値として
(s3, t3) = (r3+r1 mod p, r1)
を保管し、w'の分散値 として
(s3', t3') = (r3'+r1' mod p, r1')
を保管する。
【００８０】
つまり、本実施形態に係る方法と非特許文献１に記載の方法とは、値を分散する段階で異なっている。
【００８１】
各秘密計算装置１Ａ−１〜１Ａ−３は、以下の手順に従った処理を行う。
【００８２】
なお、
r1''+r2''+r3'' = 0 mod p
を満たすランダムに選ばれた値として、第１の秘密計算装置１Ａ−１はr1''を保管し、第２の秘密計算装置１Ａ−2はr2''を保管し、第３の秘密計算装置１Ａ−３はr3''を保管しているものとする。このような性質を満たすr1'', r2'', r3''は乗算を実行するたびに使い捨てで必要となる。
【００８３】
第１の秘密計算装置１Ａ−1は、
u1 = t1t1'-s1s1'+r1'' mod p
を計算し、第１の送信情報u1を第２の秘密計算装置１Ａ−２に送付する。
【００８４】
第２の秘密計算装置１Ａ−2は、
u2 = t2t2'-s2s2'+r2'' mod p
を計算し、第２の送信情報u2を第３の秘密計算装置１Ａ−３に送付する。
【００８５】
第３の秘密計算装置１Ａ−3は、
u3 = t3t3'-s3s3'+r3'' mod p 
を計算し、第３の送信情報u3を第１の秘密計算装置１Ａ−１に送付する。
【００８６】
第１の秘密計算装置１Ａ−1は、
(s1'', t1'') = (u1+u3 mod p, u1)
を計算し、(s1'', t1'')をww'の分散値として保管する。
【００８７】
第２の秘密計算装置１Ａ−2は、
(s2'', t2'') = (u1+u2 mod p, u2)
を計算し、(s2'', t2'')をww'の分散値として保管する。
【００８８】
第３の秘密計算装置１Ａ−3は、
(s3'', t3'') = (u2+u3 mod p, u3)
を計算し、(s3'', t3'')をww'の分散値として保管する。
【００８９】
まず、
u1+u2+u3
= (t1t1'-s1s1'+t2t2'-s2s2'+t3t3'-s3s3+r1''+r2''+r3'') mod 2^n
= (r1+r2)(r1'+r2')-r2r2'+(r2+r3)(r2'+r3')-r2r3'+(r3+r1)(r3'+r1')-r1r1'+ r1''+r2''+r3'' mod 2^n 
= r1r1'+r1r2'+r1'r2+r2r2'+r2r3'+r2'r3+r3r3'+r3r1'+r3'r1 mod 2^n
= (r1+r2+r3)(r1'+r2'+r3') mod 2^n 
= ww' mod 2^n
となっていることが確認できる。
【００９０】
s1''+t2'' = u1+u3+u2 = u1+u2+u3 = ww' mod p
であり、第１の秘密計算装置１Ａ−１と第２の秘密計算装置１Ａ−２の保管する値からww' mod pが同じ計算方法で計算できることが確認できる。他の秘密計算装置の組み合わせについても同様である。
【００９１】
[実施形態の効果]
以上の方法によれば、積の計算は、各秘密計算装置において乗算２回で実行される。したがって、本実施形態の方法は、非特許文献１に記載の方法と比べて、乗算一回分効率的である。また、逆元を要する計算がなく、法を選ばず利用できる。
【００９２】
本実施形態の方法と非特許文献１に記載の方法との間の差は、数値の分散方法、分散された数値に関する乗算の方法であり、加減算の方法は全く同じである。これらの実施の形態の構成と動作を、図面を参照して説明する。
【００９３】
まず、本発明の実施の形態の構成について図面を参照して説明する。
【００９４】
図３は、本発明の実施の形態に係る数値分散装置１００の構成を示すブロック図である。図３を参照すると、本発明の実施の形態の数値分散装置１００は、数値を３台の秘密分散装置１Ａ−１、１Ａ−２、１Ａ−３に分散するための装置である。第１乃至第３の秘密分散装置１Ａ−１、１Ａ−２、１Ａ−３は、それぞれ、分散された値を保管する第１乃至第３の分散値保管装置200-1、200-2、200-3を備える。
【００９５】
各分散値保管装置200は、第１分散値保管手段201と、第２分散値保管手段202とを備える。
【００９６】
数値分散装置100は、数値wとパラメータpとを入力として、3台の分散値保管装置200に値を記憶させる。
【００９７】
前述したように、３台の分散値保管装置200を第１の分散値保管装置200-1、第２の分散値保管装置200-2、および第３の分散値保管装置200-3とする。また、第ｉの分散値保管装置200-iの第１分散値保管部を201-iとし、第２分散値保管部を202-iとする。ここで、ｉ＝１，２，３である。
【００９８】
具体的には、数値分散装置１００は、数値wとパラメータpとを入力として、0以上p-1以下の第１および第２の乱数r1, r2を生成する。引き続いて、数値分散装置１００は、次式に従って、第３の乱数r3を計算する。
r3 = w-r1-r2 mod p
【００９９】
引き続いて、数値分散装置１００は、次式に従って、第１乃至第３の断片s1, s2, s3を計算する。
s1 = r1+r2 mod p,
s2 = r2+r3 mod p,
s3 = r3+r1 mod p
【０１００】
そして、数値分散装置１００は、t1 = r2, t2 = r3, t3 = r1として、i = 1, 2, 3について、siを第１分散値保管部201-iに記憶させ、tiを第２分散値保管部202-iに記憶させる。
【０１０１】
図４および図５を参照して、本発明の実施の形態に係る秘密計算システム１Ａの構成について説明する。図示の秘密計算システム１Ａは、乗算処理を実行するためのシステムである。
【０１０２】
図４に示されるように、秘密計算システム１Ａは、第１乃至第３の秘密計算装置１Ａ−１、１Ａ−２、および１Ａ−３から成る。第１乃至第３の秘密計算装置１Ａ−１、１Ａ−２、および１Ａ−３の各々は、同様の構成をしている。従って、以下では、主に第１の秘密計算装置１Ａ−１について詳細に説明する。
【０１０３】
第１の秘密計算装置１Ａ−１は、第１乃至第３の分散値保管装置２００-A-1、２００-B-1、２００-C-1と、送信情報生成装置３００-1と、分散情報整形装置４００-1とを備える。
【０１０４】
第１の分散値保管装置２００-A-1は、数値wAの分散値として値sA1と値tB1とを保管している。第２の分散値保管装置２００-B-1は、数値wBの分散値として値sB1と値tB1とを保管している。
【０１０５】
図５は、図４の中の第１の秘密計算装置１Ａ−１および第３の秘密計算装置１Ａ−３の内部構成を詳細に示すブロック図である。
【０１０６】
送信情報生成装置300-1は、第１の分散値保管装置200-A-1の備える第1分散値保管部の記憶する値sA1と、第２分散値保管部の記憶する値tA1と、第２の分散値保管装置200-B-2の備える第1分散値保管部の記憶する値sB1と、第２分散値保管部の記憶する値tB1と、インデックスjとを入力とする。送信情報生成装置３００-1は、擬似乱数差生成回路部301-1と、送信情報計算回路部302-1とを備え、送信情報u1を出力する。
【０１０７】
擬似乱数差生成回路部301-1は、２つの擬似乱数の鍵K1, K2を記憶しており、インデックスjとパラメータpとを入力とする。擬似乱数差生成回路部301-1は、K1を鍵、インデックスをjとして擬似ランダム関数に入力してrK1'を計算し、K2を鍵、インデックスをjとして擬似ランダム関数に入力してrK2'を計算し、
r = rK1'-rK2'mod p
を出力する。
【０１０８】
送信情報計算回路部302-1は、sA1, sB1, tA1, tB1, r, pを入力として、tA1tB1-sA1sB1+r mod pを計算し、第１の送信情報u1とする。
【０１０９】
図４に戻って、第２の秘密計算装置１Ａ−２は、第１乃至第３の分散値保管装置２００-A-2、２００-B-2、２００-C-2と、送信情報生成装置３００-2と、分散情報整形装置４００-2とを備える。同様に、第３の秘密計算装置１Ａ−３は、第１乃至第３の分散値保管装置２００-A-3、２００-B-3、２００-C-3と、送信情報生成装置３００-3と、分散情報整形装置４００-3とを備える。
【０１１０】
第２の秘密計算装置１Ａ−２において、第１の分散値保管装置２００-A-2は値sA2と値tA2とを保管し、第２の分散値保管装置２００-B-2は値sB2と値tB2とを保管している。第３の秘密計算装置１Ａ−３において、第１の分散値保管装置２００-A-3は値sA3と値tA3とを保管し、第２の分散値保管装置２００-B-3は値sB3と値tB3とを保管している。
【０１１１】
図５に示されるように、第３の秘密計算装置１Ａ−３の送信情報生成装置３００-3は、
擬似乱数差生成回路部301-3と、送信情報計算回路部302-3とを備え、第３の送信情報u3を出力する。
【０１１２】
第１の秘密計算装置１Ａ−１において、分散情報整形装置400-1は、2台の送信情報生成装置300-1、300-3が計算した、第１の送信情報u1と第３の送信情報 u3とpを入力とする。引き続いて、分散情報整形装置400-1は、次式で表されるsを計算する。
s = u1+u3 mod pを計算し、
【０１１３】
そして、分散情報整形装置400-1は、第３の分散値保管装置200-C-1の備える第1分散値保管部201-C-2にsを記憶させ、第2分散値保管部202-C-2にu1を記憶させる。
【０１１４】
次に、本発明の実施の形態の動作について図面を参照して説明する。
【０１１５】
図４は、3組の秘密計算装置１Ａ−１、１Ａ−２、１Ａ−３に２つの数値wAおよびwBが分散された値に関する乗算を実行し、その結果の分散値を保管する際の実施の形態の構成を示す図である。
【０１１６】
これらは、分散値保管装置200-X-iは、値Xに関するシェアのi個目が保管されていることを表す。A*Bを分散して計算し、分散値保管装置200-C-iに保管する。
【０１１７】
送信情報生成装置300-iは送信情報生成装置300-i+１と分散情報整形装置400-iに送信情報を送付する。i+1=4の場合は1に読み替える。
【０１１８】
図６は、本発明における数値を分散する実施の形態の動作を示すフローチャートである。
【０１１９】
まず、数値分散装置100には、数値wとパラメータpとが入力される（ステップＳ１０１）。
【０１２０】
次に、数値分散装置100は、2つの乱数r1, r2を生成し（ステップＳ１０２）、r3 = w-r1-r2 mod pを計算する（ステップＳ１０３）。
【０１２１】
次に、数値分散装置100は、s1 = r1+r2 mod p, s2 = r2+r3 mod p, s3 = r3+r1 mod pを計算する（ステップＳ１０４）。なお、数値分散装置100は、t1 = r2, t2 = r3, t3 = r1とみなす（ステップＳ１０５）。
【０１２２】
次に、数値分散装置１００は、i = 1, 2, 3について、siを第１分散値保管部201-iに記憶させ、tiを第２分散値保管部202-iに記憶させる（ステップＳ１０６）。
【０１２３】
図７は、本発明の実施の形態における送信情報生成装置300と分散情報整形装置400とが、第１の分散値保管装置200-Aと第２の分散値保管装置200-Bとに分散されている値に関する乗算を実行し、第３の分散値保管装置200-Cに記憶させるまでの実施の形態の動作を示すフローチャートである。
【０１２４】
まず、送信情報生成装置300には、インデックスjが入力される（ステップＳ２０１）。
【０１２５】
次に、送信情報生成装置300は、第１の分散値保管装置200-Aの備える第1分散値保管部201-Aの記憶する値sAと、第２分散値保管部202-Aの記憶する値tAと、第２の分散値保管装置200-Bの備える第1分散値保管部201-Bの記憶する値sBと、第２分散値保管部202-Bの記憶する値tBとを読み出す（ステップＳ２０２）。
【０１２６】
次に、送信情報生成装置300は、インデックスjを擬似乱数差生成回路部301に入力する（ステップＳ２０３）。
【０１２７】
擬似乱数差生成回路部301は、インデックスjに従って２つの擬似乱数を生成し、それらの差rを出力する（ステップＳ２０４）。
【０１２８】
次に送信情報生成装置300は、sA, tA, sB, tB, rを送信情報計算回路部302に入力する(ステップＳ２０５)。
【０１２９】
送信情報計算回路部302は、送信情報uとしてu = tAtB-sAsB+r mod pを計算し、2台の分散情報整形装置400に入力する（ステップＳ２０６）。
【０１３０】
分散情報整形装置４００は、２つの送信情報u1とu3を受け取り、
s = u1+u3 mod p
とu1 を第３の分散値保管装置200-Cに記憶させる（ステップＳ２０７）。
【０１３１】
本発明を用いれば、複数の秘密計算装置にデータを分散して各秘密計算装置にデータを隠ぺいしたままmod p上の任意の多項式を計算することが可能になる。また、この計算に必要な通信量と計算量は小さい。これはある秘密計算装置で秘密のデータを扱ってなんらかのサービスを提供する時に、秘密計算装置の管理者がデータを盗む出すことを防止することに防止する。なぜなら、複数の秘密計算装置に異なる管理者を割り当てれば、一人で全ての秘密計算装置中のデータを見ることのできる管理者がいなくなり、このような管理者を通じたデータの盗み出しを防止することに貢献する。
【実施例】
【０１３２】
図８は、数値分散装置１００の構成の一例を示すブロック図である。数値分散装置１００は、取得回路部１１０と、乱数生成回路部１２０と、乱数計算回路部１３０と、断片計算回路部１４０と、送信回路部１５０とから成る。【０１３３】
取得回路部１１０は、数値wとパラメータpとを取得する。乱数生成回路部１２０は、ゼロ以上でパラメータp未満のランダムな第１の乱数r1および第２の乱数r2を生成する。乱数計算回路部１３０は、数値wとパラメータpと第１の乱数r1と第２の乱数r2とから、数式r3=w-r1-r2 mod p に従って、第３の乱数r3を計算する。【０１３４】
断片計算回路部１４０は、第１乃至第３の乱数r1, r2, r3とパラメータpとから、数式s1 = r1+r2 mod p、s2 = r2+r3 mod p、s3 = r3+r1 mod pに従って、第１乃至第３の断片s1、s2、s3を計算する。送信回路部１５０は、第1の断片s1と第２の乱数r2の組(s1, r2)、第２の断片s2と第３の乱数r3の組(s2, r3)、および第３の断片s3 と第１の乱数r1の組(s3, r1)を、それぞれ、第１乃至第３の秘密計算装置１Ａ−１、１Ａ−２、１Ａ−３へ送信する。【０１３５】
尚、t1 = r2, t2 = r3, t3 = r1とする。この場合、第１の秘密計算装置１Ａ−１は、数値wの分散値として組(s1, t1)を保管し、第２の秘密計算装置１Ａ−２は、数値wの分散値として組(s2, t2)を保管し、第３の秘密計算装置１Ａ−３は、数値wの分散値として組(s3, t3)を保管することになる。【０１３６】
同様の構成において、数値分散装置１００に、数値w'とパラメータｐとが供給されたとする。この場合、乱数生成回路部１２０および乱数計算回路部１３０によって、第１乃至第３の乱数r1', r2', r3'が得られる。したがって、この場合、第１の秘密計算装置１Ａ−１は、数値w'の分散値として組(s1', t1')を保管し、第２の秘密計算装置１Ａ−２は、数値w'の分散値として組(s2', t2')を保管し、第３の秘密計算装置１Ａ−３は、数値w'の分散値として組(s3', t3')を保管することになる。【０１３７】
図９は、送信情報生成装置３００の構成の一例を示すブロック図である。送信情報生成装置３００は、情報取得回路部３１０と、擬似乱数差生成回路部３２０と、送信情報計算回路部３３０と、送信回路部３４０とから成る。【０１３８】
情報取得回路部３１０は、第１の分散値保管装置２００−Ａと第２の分散値保管装置２００−Ｂとに接続されている。第１の分散値保管装置２００−Ａは、数値wAの分散値として数値sA, tAを保管している。第２の分散値保管装置２００−Ｂは、数値wBの分散値として数値sB, tBを保管している。情報取得回路部３１０は、第１の分散値保管装置２００−Ａから数値sA, tAを取得し、第２の分散値保管装置２００−Ｂから数値sB, tBを取得する。【０１３９】
擬似乱数差生成回路部３２０は、鍵Ｋ1、Ｋ2を記憶し、インデックスjとパラメータpとを入力する。擬似乱数差生成回路３２０は、鍵Ｋ1、Ｋ2とインデックスjとを使用して２つの擬似乱数を生成し、生成された２つの擬似乱数とパラメータpとから差rを計算し、出力する。【０１４０】
送信情報計算回路部３３０には、数値sA, tA, sB, tBと差rとパラメータpとが供給される。送信情報計算回路部３３０は、送信情報uとして、
u = tAtB-sAsB+r mod p
を計算する。送信回路部３４０は、２台の分散情報整形装置４００へ送信情報uを送信する。【０１４１】
図１０は、第１の秘密計算装置１Ａ−１に用いられる分散情報整形装置４００−１の構成の一例を示すブロック図である。分散情報整形装置４００−１は、送信情報取得回路部４１０−１と、断片計算回路部４２０−１と、情報格納回路部４３０−１とから成る。【０１４２】
送信情報取得回路部４１０−１は、第１の秘密計算装置１Ａ−１の送信情報生成装置３００−１から第１の送信情報u1を取得し、第３の秘密計算装置１Ａ−３の送信情報生成装置３００−３から第３の送信情報u3を取得する。【０１４３】
断片計算回路部４２０−１は、送信情報取得回路部４１０−１からの第１および第３の送信情報u1およびu3と、パラメータpと受ける。断片計算回路部４２０−１は、次式に従って断片sを計算する。
s = u1+u3 mod p【０１４４】
情報格納回路部４３０−１は、断片sと第１の送信情報u1とを第３の分散値保管装置２００−Ｃ−１に格納する。【０１４５】
なお、本発明に記載した方法は、コンピュータに実行させることができる。この方法を実行させるプログラムは、フロッピー（登録商標）ディスク、ハードディスクなどの磁気ディスク、ＣＤ-ＲＯＭ（Compact Disc- Read Only Memory）、ＤＶＤ（digital versatile disc）などの光ディスク、光磁気ディスク（magneto-optical disc）、半導体メモリなどの記録媒体に格納して頒布することもできる。【０１４６】
また、この記録媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。【０１４７】
また、記録媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト等のミドルウェアなどが各処理の一部を実行してもよい。【０１４８】
さらに、本発明における記録媒体は、コンピュータと独立した媒体に限らず、ＬＡＮ（Local Area Network）やインターネットなどにより伝送されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。【０１４９】
また、記録媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記録媒体に含まれ、媒体構成は何れの構成であってもよい。【０１５０】
本発明におけるコンピュータは、記録媒体に記憶されたプログラムに基づき各処理を実行するものであって、パソコンなどからなる装置、複数の装置がネットワーク接続されたシステムなどの何れの構成であってもよい。【０１５１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置を含み、プログラムによって本発明の機能を実現することが可能な機器、装置である。【０１５２】
以上、実施の形態（実施例）を参照して本願発明を説明したが、本願発明は上記実施の形態（実施例）に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１５３】
１Ａ    秘密計算システム
１Ａ−１    第１の秘密計算装置
１Ａ−２    第２の秘密計算装置
１Ａ−３    第３の秘密計算装置
１００    数値分散装置
１１０    取得回路部
１２０    乱数生成回路部
１３０    断片計算回路部
１５０    送信回路部
２００−１    第１の分散値保管装置
２００−２    第２の分散値保管装置
２００−３    第３の分散値保管装置
２００−Ａ    第１の分散値保管装置
２００−Ａ−１〜２００−Ａ−３    第１の分散値保管装置
２００−Ｂ    第２の分散値保管装置
２００−Ｂ−１〜２００−Ｂ−３    第２の分散値保管装置
２００−Ｃ−１〜２００−Ｃ−３    第３の分散値保管装置
２０１−１〜２０１−３    第１分散値保管部
２０１−Ｃ−１、２０１−Ｃ−３    第１分散値保管部
２０２−１〜２０２−３    第２分散値保管部
２０２−Ｃ−１、２０２−Ｃ−３    第２分散値保管部
３００    送信情報生成装置
３００−１〜３００−３    送信情報生成装置
３０１−１、３０１−３    擬似乱数差生成回路部
３０２−１、３０２−３    送信情報計算回路部
３１０    情報取得回路部
３２０    擬似乱数差生成回路部
３３０    送信情報計算回路部
３４０    送信回路部
４００−１〜４００−３    分散情報整形装置
４１０−１    送信情報取得回路部
４２０−１    断片計算回路部
４３０−１    情報格納回路部
【図１】
2018211653.tif 000003
【図２】
2018211653.tif 000004
【図３】
2018211653.tif 000005
【図４】
2018211653.tif 000006
【図５】
2018211653.tif 000007
【図６】
2018211653.tif 000008
【図７】
2018211653.tif 000009
【図８】
2018211653.tif 000010
【図９】
2018211653.tif 000011
【図１０】
2018211653.tif 000012
【国際調査報告】
2018211653.tif 000013
2018211653.tif 000014
2018211653.tif 000015
2018211653.tif 000016