(57)【特許請求の範囲】
【請求項１】
ｉ＝０，１，２であり、
ｘｉ∈｛０，１｝の秘密分散値｛ｘｉ｝を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算する減算部と、
前記秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２を計算して出力する第１排他的論理和演算部と、
乱数ｒの秘密分散値｛ｒ｝および前記秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２を計算して出力する第２排他的論理和演算部と、
を有する秘密計算装置。
【請求項２】
請求項１の秘密計算装置であって、
ｊ＝０，１，２であり、当該秘密計算装置は３個の秘密計算装置Ｐ０，Ｐ１，Ｐ２のいずれかの秘密計算装置Ｐｊであり、前記秘密計算装置Ｐｊに対する前記秘密分散値｛ｘｉ｝が｛ｘｉ｝ｊであり、
乱数ｗ∈｛０，１｝についてｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２を満たす秘密分散値｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１）ｍｏｄ ３ ）を得る乱数取得部をさらに有し、
｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）である、秘密計算装置。
【請求項３】
請求項２の秘密計算装置であって、
前記減算部は、ｗｊおよびｗ（ｊ＋１） ｍｏｄ ３を有限体の元として扱って前記秘密分散値｛ｓｉ｝を計算し、
前記秘密分散値｛ｙ｝は、前記乱数ｗを前記有限体上で秘密分散した場合に得られる秘密分散値である、秘密計算装置。
【請求項４】
請求項１から３の何れかの秘密計算装置であって、
前記第１排他的論理和演算部は、秘密分散値｛４ｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１｝を得、前記秘密分散値｛４ｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１ｓ２｝を得、
前記第２排他的論理和演算部は、秘密分散値｛４ｒ｝および秘密分散値｛ｓ０｝を用いた秘密計算によって秘密分散値｛４ｒｓ０｝を得、前記秘密分散値｛４ｒｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１｝を得、前記秘密分散値｛４ｒｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１ｓ２｝を得る、秘密計算装置。
【請求項５】
秘密計算装置の秘密計算方法であって、
ｉ＝０，１，２であり、
減算部が、ｘｉ∈｛０，１｝の秘密分散値｛ｘｉ｝を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算する減算ステップと、
第１排他的論理和演算部が、前記秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２を計算して出力する第１排他的論理和演算ステップと、
第２排他的論理和演算部が、乱数ｒの秘密分散値｛ｒ｝および前記秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２を計算して出力する第２排他的論理和演算ステップと、
を有する秘密計算方法。
【請求項６】
請求項５の秘密計算方法であって、
ｊ＝０，１，２であり、前記秘密計算装置は３個の秘密計算装置Ｐ０，Ｐ１，Ｐ２のいずれかの秘密計算装置Ｐｊであり、前記秘密計算装置Ｐｊに対する前記秘密分散値｛ｘｉ｝が｛ｘｉ｝ｊであり、
乱数取得部が、乱数ｗ∈｛０，１｝についてｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２を満たす秘密分散値｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１） ｍｏｄ ３ ）を得る乱数取得ステップをさらに有し、
｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）である、秘密計算方法。
【請求項７】
請求項１から４のいずれかの秘密計算装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項１から４のいずれかの秘密計算装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算技術に関し、特に、不正な計算を検知することが可能な秘密計算技術に関する。
【背景技術】
【０００２】
α０∈｛０，１｝とα１∈｛０，１｝との排他的論理和α∈｛０，１｝はα＝α０＋α１‐２α０α１によって計算できる。これを利用するとα０とα１とα２∈｛０，１｝との排他的論理和β＝α０（ＸＯＲ）α１（ＸＯＲ）α２∈｛０，１｝は以下のように計算できる。
α＝α０＋α１‐２α０α１    （１）
β＝α＋α２‐２αα２    （２）【０００３】
値を秘匿しつつ加算、減算、乗算を行う秘密計算技術が知られている（例えば、非特許文献１等参照）。例えば、α０，α１，α２をそれぞれ秘匿した秘密分散値｛α０｝，｛α１｝，｛α２｝を用い、秘密計算によって式（１）および式（２）の計算を行うと、α０，α１，α２との排他的論理和βの秘密分散値｛β｝を得ることができる。このような秘密計算を複数の秘密計算装置で実行し、それぞれの秘密計算装置で得られた結果を所定個数集めることで排他的論理和βを復元できる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考（A Three-Party Secure Function Evaluation with Lightweight Verifiability Revisited）”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
秘密計算では秘密分散値を用いた計算が行われるため、不正な計算が行われたことを検知することが困難である。特に秘密計算による乗算が不正に行われたことを検知することは困難である。そのため、本来の計算式の秘密計算に加え、当該計算式に乱数を乗じた秘密計算も行い、それらの結果を用いて不正な計算を検知する方法が考えられる。【０００６】
しかし、定数倍を行う場合を除き、秘密計算で乗算を行う場合には秘密計算装置間での通信が必要となる。そのため、定数倍以外の乗算回数が少ないほど通信量が少なくなる。式（１）および式（２）にそれぞれ乱数ｒを乗じた値を秘密計算する場合、式（１）の計算のために定数倍以外の乗算を３回行う必要があり（ｒα０，ｒα１，２ｒα０α１）、式（２）の計算のために定数倍以外の乗算をさらに１回行う必要がある（ｒα２）。そのため、秘密計算で４つの乗算を行うための通信が必要である。【０００７】
本発明では、不正な計算を検知することが可能なように３個の値の排他的論理和の秘密計算を行う場合の通信量を削減する。
【課題を解決するための手段】
【０００８】
本発明では、ｉ＝０，１，２であり、ｘｉの秘密分散値｛ｘｉ｝を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算し、秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２を計算して出力し、乱数ｒの秘密分散値｛ｒ｝および秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２を計算して出力する。
【発明の効果】
【０００９】
これにより、不正な計算を検知することが可能なように３個の値の排他的論理和の秘密計算を行う場合の通信量を削減できる。
【図面の簡単な説明】
【００１０】
【図１】図１は実施形態の秘密計算システムの構成を例示したブロック図である。
【図２】図２は実施形態の秘密計算装置の構成を例示したブロック図である。
【図３】図３は実施形態の秘密計算方法を説明するためのフロー図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を説明する。
［概要］
まず実施形態の概要を説明する。実施形態の秘密計算装置では、まず減算部がｘｉ∈｛０，１｝の秘密分散値｛ｘｉ｝を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算して出力する。ただし、ｉ＝０，１，２である。例えば、減算部は秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２ ｍｏｄ ｑを計算する。ただし、ｑは正整数である。例えば、ｑは２以上または３以上の整数（例えば、素数）である。次に、第１排他的論理和演算部が秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値
｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２    （３）
を計算して出力する。例えば、第１排他的論理和演算部は、秘密分散値｛４ｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１｝を得、秘密分散値｛４ｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１ｓ２｝を得る。次に第２排他的論理和演算部が乱数ｒの秘密分散値｛ｒ｝および秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値
｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２    （４）
を計算して出力する。例えば、第２排他的論理和演算部は、秘密分散値｛４ｒ｝および秘密分散値｛ｓ０｝を用いた秘密計算によって秘密分散値｛４ｒｓ０｝を得、秘密分散値｛４ｒｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１｝を得、秘密分散値｛４ｒｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１ｓ２｝を得る。なお、秘密計算方式に限定はなく、例えば非特許文献１に記載された方式を用いることができる。上述のようにｓｉ，ｙ，ｙｒは四則演算が定義された集合の元である。四則演算が定義されているのであれば、どのような集合であってもよい。このような集合の一例は位数ｐの有限体Ｆｐである。ｐは２以上の整数である。ｐの例は３以上の整数であり、例えば、ｐは３以上の素数である。ｓｉ∈Ｆｐ，ｙ∈Ｆｐ，ｙｒ∈Ｆｐそれぞれの秘密分散値を｛ｓｉ｝∈｛Ｆｐ｝，｛ｙ｝∈｛Ｆｐ｝，｛ｙｒ｝∈｛Ｆｐ｝と表現する。
【００１２】
ここでｙ＝４ｓ０ｓ１ｓ２＋１／２およびｓｉ＝ｘｉ‐１／２を満たすが、このようなｙはｘ０とｘ１とｘ２との排他的論理和ｙ＝ｘ０（ＸＯＲ）ｘ１（ＸＯＲ）ｘ２となっている。以下にこの真理値表を示す。
【表１】
0006933293.tif 000002
すなわち、ｙ＝４ｓ０ｓ１ｓ２＋１／２によって、前述した式（１）（２）においてα＝ｘ＝ｘ０＋ｘ１‐２ｘ０ｘ１、β＝ｙ、α０＝ｘ０、α１＝ｘ１、α２＝ｘ２としたのと同じ結果を得ることができる。ここで、式（１）（２）に従って秘密分散値｛ｙ｝を計算するために必要な定数倍以外の乗算回数は２回であり（｛２ｘ０ｘ１｝，｛２ｘｘ２｝）、式（１）（２）に従って｛ｙｒ｝を計算するために必要な定数倍以外の乗算回数は５回である（｛ｒｘ０｝，｛ｒｘ１｝，｛２ｒｘ０ｘ１｝，｛ｒｘ２｝，｛２ｒｘｘ２｝）。これに対し、式（３）を用いて秘密分散値｛ｙ｝を計算するために必要な定数倍以外の乗算回数は２回であり（｛４ｓ０ｓ１｝，｛４ｓ０ｓ１ｓ２｝）、式（４）を用いて｛ｙｒ｝を計算するために必要な定数倍以外の乗算回数は３回である（｛４ｒｓ０｝，｛４ｒｓ０ｓ１｝，｛４ｒｓ０ｓ１ｓ２｝）。そのため、式（３）（４）を用いて秘密計算を行うことにより、式（１）（２）に従って秘密計算を行う場合に比べて定数倍以外の乗算回数を２回削減できる。秘密計算によって定数倍以外の乗算を行う場合には秘密計算装置間で通信を行う必要がある。そのため、定数倍以外の乗算回数を削減する本方式は式（１）（２）に従って秘密計算を行う場合に比べて通信量を削減できる。
【００１３】
ｘ０，ｘ１，ｘ２∈｛０，１｝がどのような性質の値であるかは本質的ではない。例えば、ｘ０，ｘ１，ｘ２∈｛０，１｝は、乱数であってもよいし、他の演算結果であってもよいし、入力値であってもよい。秘密分散値のペア｛ｙ｝｛ｙｒ｝をどのような用途に用いるかも本質的ではない。秘密計算によってｘ０とｘ１とｘ２との排他的論理和ｙ＝ｘ０（ＸＯＲ）ｘ１（ＸＯＲ）ｘ２の秘密分散値｛ｙ｝と、この秘密分散値｛ｙ｝が不正に計算されたことを検知するための秘密分散値｛ｙｒ｝とを用いるのであれば、どのような用途に実施形態の手法が適用されてもよい。
【００１４】
例えば、ｊ＝０，１，２であり、上述の秘密計算装置が３個の秘密計算装置Ｐ０，Ｐ１，Ｐ２のいずれかの秘密計算装置Ｐｊであり、秘密計算装置Ｐｊに対する秘密分散値｛ｘｉ｝が｛ｘｉ｝ｊであり、秘密計算装置Ｐｊの乱数取得部が、乱数ｗ∈｛０，１｝についてｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２を満たす秘密分散値｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１） ｍｏｄ ３）を生成し、減算部が｛ｘｉ｝（ただし、ｉ＝０，１，２）として｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算し、第１排他的論理和演算部が、当該秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２を計算し、第２排他的論理和演算部が、秘密分散値｛ｒ｝および秘密分散値｛ｓｉ｝を用いた秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２を計算してもよい。なお、ｊ＝０，１，２について｛ｘｊ｝ｊ，｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ，｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊを列挙すると以下のようになる。
｛ｘ０｝０＝（ｗ０，０），｛ｘ０｝１＝（０，０），｛ｘ０｝２＝（０，ｗ０）
｛ｘ１｝０＝（０，ｗ１），｛ｘ１｝１＝（ｗ１，０），｛ｘ１｝２＝（０，０）
｛ｘ２｝０＝（０，０），｛ｘ２｝１＝（０，ｗ２），｛ｘ２｝２＝（ｗ２，０）
【００１５】
ｗ０，ｗ１，ｗ２∈｛０，１｝は（２，３）しきい値秘密分散方式の加法的秘密分散方式（例えば、非特許文献１等参照）に則って乱数ｗをｍｏｄ ２上で秘密分散して得られる秘密分散値のサブシェアである。（ｋ，ｎ）しきい値秘密分散方式（「k-of-nしきい値秘密分散方式」ともいう）とは、ｎ個の秘密分散値のうち互いに相違するｋ個の秘密分散値を用いれば平文を復元できるが、互いに相違するｋ個未満の秘密分散値からは平文の情報が一切得られない秘密分散方式をいう。ただし、ｋ≦ｎであり、ｋおよびｎは２以上の整数である。乱数ｗは各秘密計算装置Ｐｊ（ただし、ｊ＝０，１，２）に対して秘匿されているが、各秘密計算装置Ｐｊが自ら乱数ｗｊ∈｛０，１｝を生成し、各秘密計算装置Ｐ（ｊ‐１） ｍｏｄ ３に送信することで、各秘密計算装置Ｐｊはサブシェアｗｊおよびｗ（ｊ＋１） ｍｏｄ ３を得ることができる。各秘密計算装置Ｐｊが生成した乱数ｗ０，ｗ１，ｗ２に応じて乱数ｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２が定まる。
【００１６】
｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）であり、ｓｉ∈Ｆｐ，ｙ∈Ｆｐ，ｙｒ∈Ｆｐである場合、減算部は、ｗｊ∈｛０，１｝およびｗ（ｊ＋１） ｍｏｄ ３∈｛０，１｝を有限体Ｆｐの元として扱って秘密分散値｛ｓｉ｝を計算する。例えば、有限体Ｆｐのすべての元の集合が｛φ０，…，φｐ−１｝である場合、０を有限体Ｆｐの元φ０と扱い、１を有限体Ｆｐの元φ１と扱って有限体Ｆｐ上で秘密分散値｛ｓｉ｝を計算する。｛ｙ｝は乱数ｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２を有限体Ｆｐ上で秘密分散した場合に得られる秘密分散値｛ｗ｝∈｛Ｆｐ｝となる。すなわち、このような秘密計算装置の処理は、（２，３）しきい値秘密分散方式の加法的秘密分散方式に則って乱数ｗをｍｏｄ ２上で秘密分散して得られる秘密分散値｛ｗ｝Ｂｊを、当該乱数ｗの有限体Ｆｐ上の秘密分散値｛ｙ｝∈｛Ｆｐ｝と秘密分散値｛ｙｒ｝∈｛Ｆｐ｝とのペア（秘密乱数ペア）に変換する処理となる。
【００１７】
上述の｛ｒ｝，｛ｙ｝，｛ｙｒ｝をチェックサムとして用いることで｛ｙ｝が正しく計算されていたかを事後的に検証できる。例えば、｛ｒ｝，｛ｙ｝，｛ｙｒ｝を用いた秘密計算によってｙｒ＝ｒｙが満たされるか否かを表す情報の秘密分散値（例えば、｛ｙｒ＝ｒｙ｝）が生成されてもよいし（例えば、国際公開ＷＯ２０１４／１１２５４８号公報（参考文献１）等参照）、検証装置が｛ｒ｝，｛ｙ｝，｛ｙｒ｝からｒ，ｙ，ｙｒを復元してからｙｒ＝ｒｙが満たされるか否かが検証されてもよい。後者の場合、検証装置は上述の秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２と秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２と秘密分散値｛ｒ｝の入力を受け付け、秘密分散値｛ｙ｝と秘密分散値｛ｙｒ｝と秘密分散値｛ｒ｝とを復元してｙ＝４ｓ０ｓ１ｓ２＋１／２とｙｒ＝４ｒｓ０ｓ１ｓ２＋ｒ／２とｒとを得、ｒとｙとを用いてｙｒ’＝ｒｙを得、ｙｒ’＝ｙｒである場合に検証成功である旨を出力し、ｙｒ’≠ｙｒである場合に検証失敗である旨を出力する。
【００１８】
なお、通常、秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝は互いに同一の秘密分散方式（例えば、加法的秘密分散方式）に則ったものである。しかし、公知手法によって秘密分散値の方式変換が可能であるため（参考文献２〜６等参照）、秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝がすべて互いに同一の秘密分散方式に則ったものでなくてもよい。また、上述のように得られた｛ｙ｝や｛ｙｒ｝が別の方式に則った秘密分散値に変換されてもよい。
参考文献２：Ronald Cramer, Ivan Damgard, and Yuval Ishai, "Share conversion, pseudorandom secret-sharing and applications to secure distributed computing," Theory of Cryptography (2005): 342-362
参考文献３：特開２０１６−１７３５３３号公報
参考文献４：特開２０１６−１７３５３２号公報
参考文献５：特開２０１６−１７３５３１号公報
参考文献６：特開２０１６−１５６８５３号公報
【００１９】
［第１実施形態］
図面を用いて第１実施形態を詳細に説明する。
【００２０】
＜構成＞
図１に例示するように、実施形態の秘密計算システム１は、Ｎ個の秘密計算装置１１−０，…，１１−（Ｎ−１）と検証装置１２とを有し、これらはネットワークを通じて通信可能に構成されている。ただし、Ｎは２以上の整数である。例えば、Ｎは３以上の整数であり、その一例はＮ＝３である。図２に例示するように、秘密計算装置１１−ｊ（ただし、ｊ＝０，…，Ｎ−１）は、入力部１１１−ｊと出力部１１２−ｊと記憶部１１３−ｊと制御部１１４−ｊと減算部１１６−ｊと排他的論理和演算部１１７−ｊ，１１８−ｊとを有する。秘密計算装置１１−ｊは、制御部１１４−ｊの制御の下で各処理を実行する。秘密計算装置１１−ｊの各部で得られたデータは、逐一、記憶部１１３−ｊに格納され、必要に応じて読み出されて他の処理に利用される。
【００２１】
＜秘密計算処理＞
図３を用いて秘密計算装置１１−ｊが行う秘密計算処理を説明する。秘密分散方式や秘密計算方式の詳細については、例えば、非特許文献１等を参照されたい。
各秘密計算装置１１−ｊ（ただし、ｊ＝０，…，Ｎ−１）の入力部１１１−ｊには、有限体Ｆｐ上の乱数ｒ∈Ｆｐの秘密分散値｛ｒ｝∈｛Ｆｐ｝が入力される。なお、各秘密計算装置１１−ｊに対応する各値γの秘密分散値は互いに相違するが、記載の簡略化の観点から、特に断りのない限り、値γの秘密分散値を単に｛γ｝と表記する。ただし、各秘密計算装置１１−ｊに対応する秘密分散値であることを明記する場合には、各秘密計算装置１１−ｊに対応する秘密分散値を｛γ｝ｊと表記することにする。本実施形態では、加法的秘密分散方式に則って有限体Ｆｐ上の乱数ｒを秘密分散したものを｛ｒ｝とするが、これは本発明において本質的な事項ではない。本実施形態の秘密分散値｛ｒ｝は各秘密計算装置１１−ｊの外部で生成されたものである。乱数ｒの値は各秘密計算装置１１−ｊに秘匿される。例えば、検証装置１２が、乱数ｒの値を各秘密計算装置１１−ｊに知られることなく、乱数ｒの秘密分散値｛ｒ｝を生成して各秘密計算装置１１−ｊに送信してもよい。秘密分散値｛ｒ｝がどこで作成されるかも、本発明において本質的な事項ではない。秘密分散値｛ｒ｝は各秘密計算装置１１−ｊの記憶部１１３−ｊに格納される（ステップＳ１１１−ｊ）。
【００２２】
記憶部１１３−ｊにはｘｉ∈｛０，１｝の秘密分散値｛ｘｉ｝が格納されている（ただし、ｉ＝０，１，２）。ｘｉはどのような値であってもよい。秘密分散値｛ｘｉ｝は、秘密計算装置１１−ｊの外部から入力されたものであってもよいし、秘密計算装置１１−ｊの内部で生成されたものであってもよいし、秘密計算装置１１−ｊとその外部の秘密計算装置１１−ｊ”（ただし、ｊ”∈｛０，…，Ｎ−１｝、ｊ”≠ｊ）との協力によって生成されたものであってもよい。減算部１１６−ｊは、記憶部１１３−ｊから秘密分散値｛ｘｉ｝を読み込み、当該秘密分散値｛ｘｉ｝を用いた秘密計算によって秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２を計算して出力する（ステップＳ１１６−ｊ）。
【００２３】
排他的論理和演算部１１７−ｊ（第１排他的論理和演算部）は、減算部１１６−ｊから出力された秘密分散値｛ｓｉ｝を用い、秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２を計算して出力する。例えば、排他的論理和演算部１１７−ｊは、秘密分散値｛４ｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１｝を得、秘密分散値｛４ｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｓ０ｓ１ｓ２｝を得、秘密分散値｛４ｓ０ｓ１ｓ２｝および１／２を用いて秘密分散値｛ｙ｝を得て出力する。これらの秘密計算には秘密計算装置１１−０〜１１−（Ｎ−１）間での通信が必要となる。一方、秘密分散値｛４ｓ０｝の計算には通信は不要である。すなわち、各秘密計算装置１１−ｊの排他的論理和演算部１１７−ｊは、通信を行うことなく、秘密分散値｛ｓｉ｝を用いて秘密分散値｛４ｓ０｝を計算できる（ステップＳ１１７−ｊ）。
【００２４】
排他的論理和演算部１１８−ｊ（第２排他的論理和演算部）は、減算部１１６−ｊから出力された秘密分散値｛ｓｉ｝と記憶部１１３−ｊから読み出した秘密分散値｛ｒ｝とを用い、秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２を計算して出力する。例えば、排他的論理和演算部１１８−ｊは、秘密分散値｛４ｒ｝および秘密分散値｛ｓ０｝を用いた秘密計算によって秘密分散値｛４ｒｓ０｝を得、秘密分散値｛４ｒｓ０｝および秘密分散値｛ｓ１｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１｝を得、秘密分散値｛４ｒｓ０ｓ１｝および秘密分散値｛ｓ２｝を用いた秘密計算によって秘密分散値｛４ｒｓ０ｓ１ｓ２｝を得、秘密分散値｛４ｒｓ０ｓ１ｓ２｝および１／２を用いて秘密分散値｛ｙｒ｝を得て出力する。これらの秘密計算には秘密計算装置１１−０〜１１−（Ｎ−１）間での通信が必要となる。一方、秘密分散値｛４ｒ｝の計算には通信は不要である。すなわち、各排他的論理和演算部１１７−ｊの排他的論理和演算部１１７−ｊは、通信を行うことなく、秘密分散値｛ｒ｝を用いて秘密分散値｛４ｒ｝を計算できる（ステップＳ１１８−ｊ）。
【００２５】
秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝は互いに対応付けられて記憶部１１３−ｊに格納される（ステップＳ１１３−ｊ）。出力部１１２−ｊは秘密分散値｛ｙ｝を出力する（ステップＳ１１２−ｊ）。秘密分散値｛ｙ｝は他の任意の秘密計算に用いられる。
【００２６】
秘密分散値｛ｙ｝が正当に計算されたことを検証する場合には、秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝が記憶部１１３−ｊから読み出され、これらの整合性の検証が行われる。例えば、秘密計算装置１１−ｊが秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝を用いた秘密計算によって秘密分散値｛ｒｙ‐ｙｒ｝を計算して出力する（参考文献１参照）。秘密計算装置１１−ｊは秘密分散値｛ｒｙ‐ｙｒ｝を検証装置１２に送信する。検証装置１２は各秘密計算装置１１−ｊから送られた所定個数以上の秘密分散値｛ｒｙ‐ｙｒ｝からｒｙ‐ｙｒを復元し、ｒｙ‐ｙｒ＝０の場合に検証合格である旨を出力し、ｒｙ‐ｙｒ≠０の場合に検証失敗である旨を出力する。あるいは、秘密計算装置１１−ｊが秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝を検証装置１２に送信する。検証装置１２は、各秘密計算装置１１−ｊから送られたそれぞれが所定個数以上の秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝からｙ，ｙｒ，ｒを復元し、ｒｙ‐ｙｒ＝０を満たす場合に検証合格である旨を出力し、ｒｙ‐ｙｒ≠０を満たす場合に検証失敗である旨を出力する。
【００２７】
［第２実施形態］
第２実施形態を説明する。本実施形態では、（２，３）しきい値秘密分散方式の加法的秘密分散方式に則って乱数ｗをｍｏｄ ２上で秘密分散して得られる秘密分散値｛ｗ｝Ｂｊを、当該乱数ｗの有限体Ｆｐ上の秘密分散値｛ｙ｝∈｛Ｆｐ｝と秘密分散値｛ｙｒ｝∈｛Ｆｐ｝とのペア（秘密乱数ペア）に変換する処理を説明する。
【００２８】
＜構成＞
図１に例示するように、実施形態の秘密計算システム２は、３個の秘密計算装置２１−０，２１−１，２１−２と検証装置１２とを有し、これらはネットワークを通じて通信可能に構成されている。図２に例示するように、秘密計算装置２１−ｊ（ただし、ｊ＝０，１，２）は、入力部１１１−ｊと出力部１１２−ｊと記憶部１１３−ｊと制御部１１４−ｊと乱数取得部２１５−ｊと減算部２１６−ｊと排他的論理和演算部１１７−ｊ，１１８−ｊと設定部２１９−ｊとを有する。秘密計算装置２１−ｊは、制御部１１４−ｊの制御の下で各処理を実行する。秘密計算装置２１−ｊの各部で得られたデータは、逐一、記憶部１１３−ｊに格納され、必要に応じて読み出されて他の処理に利用される。
【００２９】
＜秘密計算処理＞
図３を用いて秘密計算装置２１−ｊ（ただし、ｊ＝０，１，２）が行う秘密計算処理を説明する。以下では第１実施形態との相違点を中心に説明し、共通する事項については説明を簡略化する。
【００３０】
各秘密計算装置２１−ｊの入力部１１１−ｊには、有限体Ｆｐ上の乱数ｒ∈Ｆｐの秘密分散値｛ｒ｝∈｛Ｆｐ｝が入力される。本実施形態の秘密分散値｛ｒ｝は、例えば（２，３）しきい値秘密分散方式の加法的秘密分散方式に則った秘密分散値である。秘密分散値｛ｒ｝は各秘密計算装置２１−ｊの記憶部１１３−ｊに格納される（ステップＳ１１１−ｊ）。
【００３１】
各秘密計算装置２１−ｊの乱数取得部２１５−ｊが、乱数ｗ∈｛０，１｝についてｗ＝ｗ０＋ｗ１＋ｗ２ ｍｏｄ ２を満たす秘密分散値｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１） ｍｏｄ ３）を得て出力する。すなわち、乱数取得部２１５−０は｛ｗ｝Ｂ０＝（ｗ０，ｗ１）を得、乱数取得部２１５−１は｛ｗ｝Ｂ１＝（ｗ１，ｗ２）を得、乱数取得部２１５−２は｛ｗ｝Ｂ２＝（ｗ２，ｗ０）を得て出力する。ただし、この処理は乱数ｗが各秘密計算装置２１−ｊに対して秘匿された状態で行われる。例えば、各乱数取得部２１５−ｊが乱数ｗｊ∈｛０，１｝を生成し、当該乱数ｗｊを出力部１１２−ｊから秘密計算装置２１−（（ｊ‐１） ｍｏｄ ３）に対して送信する。秘密計算装置２１−（（ｊ＋１） ｍｏｄ ３）から送信された乱数ｗ（ｊ＋１） ｍｏｄ ３は秘密計算装置２１−ｊの入力部１１１−ｊに入力され、乱数取得部２１５−ｊに送られる。以上の処理により、乱数取得部２１５−ｊは｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１）ｍｏｄ ３ ）を得る（ステップＳ２１５−ｊ）。
【００３２】
設定部２１９−ｊは、秘密分散値｛ｗ｝Ｂｊ＝（ｗｊ，ｗ（ｊ＋１） ｍｏｄ ３）のサブシェアｗｊ，ｗ（ｊ＋１） ｍｏｄ ３∈｛０，１｝を入力とし、｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）を得て出力する（ステップＳ２１９−ｊ）。
【００３３】
減算部２１６−ｊには、｛ｘｊ｝ｊ＝（ｗｊ，０），｛ｘ（ｊ＋１） ｍｏｄ ３｝ｊ＝（０，ｗ（ｊ＋１） ｍｏｄ ３），｛ｘ（ｊ＋２） ｍｏｄ ３｝ｊ＝（０，０）が｛ｘｉ｝（ただし、ｉ＝０，１，２）として入力される。すなわち、減算部２１６−０には｛ｘ０｝＝｛ｘ０｝０＝（ｗ０，０），｛ｘ１｝＝｛ｘ１｝０＝（０，ｗ１），｛ｘ２｝＝｛ｘ２｝０＝（０，０）が入力される。減算部２１６−１には｛ｘ０｝＝｛ｘ０｝１＝（０，０），｛ｘ１｝＝｛ｘ１｝１＝（ｗ１，０），｛ｘ２｝＝｛ｘ２｝１＝（０，ｗ２）が入力される。減算部２１６−２には｛ｘ０｝＝｛ｘ０｝２＝（０，ｗ０），｛ｘ１｝＝｛ｘ１｝２＝（０，０），｛ｘ２｝＝｛ｘ２｝２＝（ｗ２，０）が入力される。減算部２１６−ｊは、入力された｛ｘｉ｝を用いて秘密分散値｛ｓｉ｝＝｛ｘｉ｝‐１／２∈｛Ｆｐ｝を計算して出力する。例えば｛ｘｉ｝がｘｉをｘｉ＝ｘｉ，０＋ｘｉ，１＋ｘｉ，２を満たす３個の秘密分散値（ｘｉ，０，ｘｉ，１），（ｘｉ，１，ｘｉ，２），（ｘｉ，２，ｘｉ，０）に秘密分散したものである場合、秘密分散値（ｘｉ，０，ｘｉ，１），（ｘｉ，１，ｘｉ，２），（ｘｉ，２，ｘｉ，０）のそれぞれに対応する秘密分散値｛ｓｉ｝は、例えば（ｘｉ，０‐１／２，ｘｉ，１），（ｘｉ，１，ｘｉ，２），（ｘｉ，２，ｘｉ，０‐１／２）となる。その他、各秘密分散値｛ｓｉ｝が、例えば（ｘｉ，０‐１／６，ｘｉ，１‐１／６），（ｘｉ，１‐１／６，ｘｉ，２‐１／６），（ｘｉ，２‐１／６，ｘｉ，０‐１／６）であってもよい。前者の方が高速な処理が可能である。この際、減算部２１６−ｊは、ｗｊ∈｛０，１｝およびｗ（ｊ＋１） ｍｏｄ ３∈｛０，１｝を有限体Ｆｐの元として扱って秘密分散値｛ｓｉ｝を計算する（ステップＳ２１６−ｊ）。
【００３４】
排他的論理和演算部１１７−ｊ（第１排他的論理和演算部）は、減算部２１６−ｊから出力された秘密分散値｛ｓｉ｝∈｛Ｆｐ｝を用い、秘密計算によって秘密分散値｛ｙ｝＝｛４ｓ０ｓ１ｓ２｝＋１／２∈｛Ｆｐ｝を計算して出力する（ステップＳ１１７−ｊ）。
【００３５】
排他的論理和演算部１１８−ｊ（第２排他的論理和演算部）は、減算部１１６−ｊから出力された秘密分散値｛ｓｉ｝と記憶部１１３−ｊから読み出した秘密分散値｛ｒ｝とを用い、秘密計算によって秘密分散値｛ｙｒ｝＝｛４ｒｓ０ｓ１ｓ２｝＋｛ｒ｝／２∈｛Ｆｐ｝を計算して出力する（ステップＳ１１８−ｊ）。
【００３６】
秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝は互いに対応付けられて記憶部１１３−ｊに格納される（ステップＳ１１３−ｊ）。出力部１１２−ｊは秘密分散値｛ｙ｝を出力する（ステップＳ１１２−ｊ）。秘密分散値｛ｙ｝∈｛Ｆｐ｝は有限体Ｆｐ上の乱数ｙの秘密分散値である。｛ｙ｝が他の秘密分散方式に則った秘密分散値（例えば、シャミア秘密分散方式）に変換されて出力されてもよい。
【００３７】
秘密分散値｛ｙ｝が正当に計算されたことを検証する場合には、秘密分散値｛ｙ｝，｛ｙｒ｝，｛ｒ｝が記憶部１１３−ｊから読み出され、これらの整合性が検証される。
【００３８】
［変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の実施形態では、各秘密計算装置１１−jに乱数ｒ∈Ｆｐの秘密分散値｛ｒ｝が入力された。しかしながら、各秘密計算装置１１−jがそれぞれの秘密分散値｛ｒ｝を生成してもよい。ただし、乱数ｒは各秘密計算装置１１−jに秘匿しなければならない。このような方法はよく知られており、どのような方法が用いられてもよい。例えば、秘密計算装置１１−０，…，１１−（Ｎ−１）が協調して秘密分散値｛ｒ｝を生成することができる。一例を挙げると、各秘密計算装置１１−j’がそれぞれ乱数ｒj’の秘密分散値｛ｒj’｝j∈［Ｆｐ］を計算して秘密計算装置１１−jに送り（ただし、j＝０，…，Ｎ−１、j’＝０，…，Ｎ−１かつj’≠j）、各秘密計算装置１１−jが秘密分散値｛ｒ０｝j，…，｛ｒＮ−１｝jを用いた秘密計算によって｛ｒ｝＝｛ｒ０＋…＋ｒＮ−１｝jを得る。
【００３９】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４０】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００４１】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４２】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４４】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００４５】
１，２  秘密計算システム
１１−ｊ，２１−ｊ  秘密計算装置
【図１】
0006933293.tif 000003
【図２】
0006933293.tif 000004
【図３】
0006933293.tif 000005