(57)【要約】  秘匿関数計算において乗算を効率化し、従来より秘匿関数計算を高速化する。３つ以上の計算装置で協調して、乱数ｒの秘匿値[ｒ]を生成し、任意の値Ａ０、…、Ａｎ−１の秘匿値[Ａ０]、…、[Ａｎ−１]について、加算及び乗算からなる関数ｆによる秘匿関数計算を行うことにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]を計算し、更に秘匿値[ｒ・Ｃ−Ｃ’]を計算し、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する。
2012121333.tif 000002
【特許請求の範囲】
【請求項１】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、…、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]のように計算する秘匿積和結合システムであって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
当該秘匿積和結合システムは、ａ、ｂ、α、βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
前記計算装置は、
他の２つの計算装置の乱数生成部と協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成部と、
他の２つの計算装置の関数計算部と協調して、前記秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]を計算する関数計算部と、
他の２つの計算装置の不正検知部と協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知部と、
を備える
ことを特徴とする秘匿積和結合システム。
【請求項２】
請求項１に記載の秘匿積和結合システムであって、
前記関数計算部は、
[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]であるとき、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数α倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数βを加算する関数により得られる関数値である場合、秘匿値[ｒ]に定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とを乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ']と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とを乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
前記不正検知部は、([ｃ]、[ｃ’])が秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合には、更に、他の２つの計算装置の不正検知部と協調して秘匿値[ｒ・ｂ−ｂ’]を求め、[ｒ・ｂ−ｂ’]が０でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する
ことを特徴とする秘匿積和結合システム。
【請求項３】
請求項１又は２に記載の秘匿積和結合システムであって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
計算装置Ｘの乱数生成部は、１以上ｐ未満の乱数ｒzを生成して計算装置Ｙの乱数生成部と共有し、
計算装置Ｙの乱数生成部は、１以上ｐ未満の乱数ｒXを生成して計算装置Ｚの乱数生成部と共有し、
計算装置Ｚの乱数生成部は、１以上ｐ未満の乱数ｒYを生成して計算装置Ｘの乱数生成部と共有し、
前記３つの計算装置の各乱数生成部は協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成し、これらを乗算して秘匿値[ｒ]＝[ｒX・ｒY・ｒZ]を生成する
ことを特徴とする秘匿積和結合システム。
【請求項４】
請求項１又は２に記載の秘匿積和結合システムであって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
計算装置Ｘの乱数生成部は、０以上ｐ未満の乱数ｒzを生成して計算装置Ｙの乱数生成部と共有し、
計算装置Ｙの乱数生成部は、０以上ｐ未満の乱数ｒXを生成して計算装置Ｚの乱数生成部と共有し、
計算装置Ｚの乱数生成部は、０以上ｐ未満の乱数ｒYを生成して計算装置Ｘの乱数生成部と共有し、
前記３つの計算装置の各乱数生成部は協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成し、これらを乗算して秘匿値[ｒ]＝[ｒX＋ｒY＋ｒZ]を生成する
ことを特徴とする秘匿積和結合システム。
【請求項５】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、…、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]のように計算する秘匿積和結合システムを構成する前記計算装置であって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
前記秘匿積和結合システムは、ａ、ｂ、α、βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
他の２つの計算装置の乱数生成部と協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成部と、
他の２つの計算装置の関数計算部と協調して、前記秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]を計算する関数計算部と、
他の２つの計算装置の不正検知部と協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知部と、
を備える計算装置。
【請求項６】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、…、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]のように計算する秘匿積和結合方法であって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
当該秘匿積和結合方法では、ａ、ｂ、α、βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
前記３つの計算装置で協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成ステップと、
前記３つの計算装置で協調して、前記秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]を計算する関数計算ステップと、
前記３つの計算装置で協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知ステップと、
を実行する秘匿積和結合方法。
【請求項７】
請求項６に記載の秘匿積和結合方法であって、
前記関数計算ステップは、
[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]であるとき、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数α倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数βを加算する関数により得られる関数値である場合、秘匿値[ｒ]に定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ']に秘匿値[ｂ']をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’]) を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とを乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ']と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とを乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
前記不正検知ステップは、([ｃ]、[ｃ’])が秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合には、更に、前記３つの計算装置で協調して秘匿値[ｒ・ｂ−ｂ’]を求め、[ｒ・ｂ−ｂ’]が０でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する
ことを特徴とする秘匿積和結合方法。
【請求項８】
請求項６又は７に記載の秘匿積和結合方法であって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
前記乱数生成ステップは、
計算装置Ｘが１以上ｐ未満の乱数ｒzを生成して計算装置Ｙと共有し、計算装置Ｙが１以上ｐ未満の乱数ｒXを生成して計算装置Ｚと共有し、計算装置Ｚが１以上ｐ未満の乱数ｒYを生成して計算装置Ｘと共有する断片共有サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する断片秘匿サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を乗算することにより、秘匿値[ｒ]＝[ｒX・ｒY・ｒZ]を生成する断片結合サブステップと、
を実行する
ことを特徴とする秘匿積和結合方法。
【請求項９】
請求項６又は７に記載の秘匿積和結合方法であって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
前記乱数生成ステップは、
計算装置Ｘが０以上ｐ未満の乱数ｒzを生成して計算装置Ｙと共有し、計算装置Ｙが０以上ｐ未満の乱数ｒXを生成して計算装置Ｚと共有し、計算装置Ｚが０以上ｐ未満の乱数ｒYを生成して計算装置Ｘと共有する断片共有サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する断片秘匿サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を乗算することにより、秘匿値[ｒ]＝[ｒX＋ｒY＋ｒZ]を生成する断片結合サブステップと、
を実行する
ことを特徴とする秘匿積和結合方法。
【請求項１０】
請求項１乃至４のいずれかに記載の秘匿積和結合システム又は請求項５記載の計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散によりデータを秘匿しつつ、乗算及び加算からなる式の計算を、計算結果の正当性を保ちながら行う秘匿積和結合システム、計算装置、秘匿積和結合方法、及びそれらのプログラムに関する。
【背景技術】
【０００２】
従来、データを秘匿した状態で、計算結果の正当性を保証しつつ乗算及び加算を含む計算を行う技術として、非特許文献１の３パーティ秘匿関数計算がある。これは、分散された入力値を復元することなく、３パーティ（３計算主体）の協調計算によって算術／論理演算の結果を導くプロトコルである。３パーティ秘匿関数計算プロトコルでは、秘匿積和結合システムは、データをある定められた素数ｐ未満の自然数として扱う。データを秘匿するときは、そのデータをａとすれば、ａを以下の条件を満たすよう３つに分散する。【０００３】
ａ＝ａ0＋ａ1＋ａ2 mod p
実際には、秘匿積和結合システムは、乱数ａ1、ａ2を生成し、ａ0＝ａ−ａ1−ａ2とする。そして３パーティＸ、Ｙ、Ｚに対して、Ｘに（ａ0、ａ1）、Ｙに（ａ1、ａ2）、Ｚに（ａ2、ａ0）を送信する。すると、ａ1、ａ2が乱数であるため、Ｘ、Ｙ、Ｚのいずれのパーティもａの情報を持たないが、いずれか２パーティが集まればａを復元することができる。【０００４】
この秘匿は加法的な分散であるため、可換性を有する。したがって、分散値を加算してから復元しても、復元してから加算しても結果は等しい。すなわち、加算と定数倍は分散したまま通信なしで行うことが可能である。また、乗算も通信及び乱数生成が必要となるが可能である。そのため、論理回路を構成でき、いかなる計算を実行することも可能である。以下、３パーティ秘匿関数計算の具体例を示す。なお、３パーティ秘匿関数計算プロトコルにおいて、計算結果はｐで除した余りであるが、記載を簡略化するため、以下、"mod p"の記載を省略する。【０００５】
(1)Ｘ、Ｙ、Ｚに分散された秘匿データａの復元
Ｘは、Ｙにａ0を送信し、Ｚにａ1を送信する。Ｙは、Ｚにａ1を送信し、Ｘにａ2を送信する。Ｚは、Ｘにａ2を送信し、Ｙにａ0を送信する。
Ｘは、Ｙから受信したａ2とＺから受信したａ2とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。Ｙは、Ｘから受信したａ0とＺから受信したａ0とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。Ｚは、Ｘから受信したａ1とＹから受信したａ1とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。
(2)ｃ＝ａ＋ｂの秘密計算
データｂもデータａと同様な方法により、Ｘに（ｂ0、ｂ1）が、Ｙに（ｂ1、ｂ2）が、Ｚに（ｂ2、ｂ0）が、それぞれ分散されて秘匿されているとする。
このとき、Ｘは（ｃ0、ｃ1）＝（ａ0＋ｂ0、ａ1＋ｂ1）を計算して記録し、Ｙは（ｃ1、ｃ2）＝（ａ1＋ｂ1、ａ2＋ｂ2）を計算して記録し、Ｚは（ｃ2、ｃ0）＝（ａ2＋ｂ2、ａ0＋ｂ0）を計算して記録する。
(3)ｃ＝ａ＋αの秘密計算（αは既知の定数）
Ｘは、（ｃ0、ｃ1）＝（ａ0＋α、ａ1）を計算して記録し、Ｚは、（ｃ2、ｃ0）＝（ａ2、ａ0＋α）を計算して記録する。Ｙの処理は無い。
(4)ｃ＝ａ・αの秘密計算
Ｘは、（ｃ0、ｃ1）＝（ａ0・α、ａ1・α）を計算して記録し、Ｙは、（ｃ1、ｃ2）＝（ａ1・α、ａ2・α）を計算して記録し、Ｚは、（ｃ2、ｃ0）＝（ａ2・α、ａ0・α）を計算して記録する。
(5)ｃ＝ａ・ｂの秘密計算（不正検知なし乗算）
まず、Ｘは、乱数ｒ1、ｒ2、ｃ0を生成し、ｃ1＝(ａ0＋ａ1)(ｂ0＋ｂ1)−ｒ1−ｒ2−ｃ0を計算し、Ｙに(ｒ1、ｃ1)を、Ｚに(ｒ2、ｃ0)を送信する。
続いて、Ｙは、ｙ＝ａ1・ｂ2＋ｂ1・ａ2＋ｒ1を計算し、Ｚにｙを送信する。また、Ｚは、ｚ＝ａ2・ｂ0＋ｂ0・ａ2＋ｒ2を計算し、Ｙにｚを送信する。
続いて、ＹとＺはそれぞれ、ｃ2＝ｙ＋ｚ＋ａ2・ｂ2を計算する。
そして、Ｘは(ｃ0、ｃ1)を記録し、Ｙは(ｃ1、ｃ2)を記録し、Ｚは(ｃ2、ｃ0)を記録する。
(6) ｃ＝ａ・ｂの秘密計算（不正検知付き乗算）【０００６】
上記(5)の方法によりｃ＝ａ・ｂの乗算を行った上で、Ｘ、Ｙ、Ｚのそれぞれに対して以下の処理を行う。なお、以下の処理においてＰはＸ、Ｙ、Ｚのそれぞれを意味し、ＰがＸである場合は、Ｐ-はＺ、Ｐ+はＹを意味し、ＰがＹである場合は、Ｐ-はＸ、Ｐ+はＺを意味し、ＰがＺである場合は、Ｐ-はＹ、Ｐ+はＸを意味する。【０００７】
まず、Ｐ-、Ｐ+だけで乱数ｒを生成して共有し、Ｐ-、Ｐ+はｒ・ａ0、ｒ・ａ1、ｒ・ａ2をｒ・ａの秘匿値として各パーティに分散する。続いて、上記(5)の方法によりｃ’＝(ｒ・ａ)・ｂを計算する。そして、ｒ・ｃ−ｃ’が０であるか否かを確認し、０でないことをもって不正を検知する。【０００８】
また、不正検知付き乗算を備えない秘匿関数計算として、非特許文献２のShamirの秘密分散をベースとした秘匿関数計算（以下、「Shamir方式」という。）がある。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克己、「軽量検証可能３パーティ秘匿関数計算の再考」、ＣＳＳ２０１０、２０１０年
【非特許文献２】SecureSCM-Consortium, "D9.2 Security Analysis", Cryptographic Aspects, 2009, p19-26．
【発明の概要】
【発明が解決しようとする課題】
【００１０】
３パーティ秘匿関数計算では乗算は可能であるが、通信及び乱数生成を要する。そのため、乗算が計算処理におけるボトルネックとなり、秘匿関数計算の高速化を阻む要因となっていた。Shamir方式は、非特許文献１の方式と比べ、データ量が半分で済む。また、Shamir方式においては、計算装置が４個以上であっても構わない。しかし、Shamir方式は、莫大な計算コスト（例えば約１０００倍程度）のかかる公開鍵暗号方式を用いた方法でしか不正検知を行う方法が知られていない。【００１１】
本発明の目的は、秘匿関数計算において乗算を効率化し、従来より高速に秘匿関数計算が可能な秘匿積和結合システム、計算装置、秘匿積和結合方法、及びそれらのプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の秘匿積和結合システムは、ｎ個の０以上ｐ未満（ｐは素数）の任意の値Ａ０、…、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]を計算する秘匿積和結合システムであって、各計算装置は乱数生成部と関数計算部と不正検知部とを備える。なお、[]は、[]内の値が暗号化または秘密分散により秘匿されていることを表す記号であり、秘匿されていない値と区別するための記号である。例えば、実際の値が秘密分散されているときには、[]は、[]内に示された実際の値の秘密分散された断片の集合を概念的に示している。そして、本発明の秘匿積和結合システムは、ａ，ｂ，α，βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立つ。また、非特許文献１の技術を基に本発明を適用した場合は、秘匿積和結合システムは３つの計算装置で構成でき、Shamir方式を基に本発明を適用した場合は、秘匿積和結合システムは３つ以上の任意の数の計算装置で構成できる。【００１３】
乱数生成部は、他の２つ以上の計算装置の乱数生成部と協調して、１以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する。【００１４】
関数計算部は、他の２つ以上の計算装置の関数計算部と協調して、前記秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]を計算する。【００１５】
不正検知部は、他の２つ以上の計算装置の不正検知部と協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する。
【発明の効果】
【００１６】
本発明の秘匿積和結合システム、計算装置、秘匿積和結合方法、及びそれらのプログラムによれば、秘匿関数計算において乗算を効率的に行うことができ、よって、従来より高速に秘匿関数計算をすることが可能となる。
【図面の簡単な説明】
【００１７】
【図１】秘匿積和結合システム１００の構成例を示す図。
【図２】秘匿積和計算システム１００の処理フロー例を示す図。
【図３】乱数生成部１１ｘ、ｙ、ｚの処理フロー例を示す図。
【図４】秘匿積和結合システム２００の構成例を示す図。
【図５】秘匿積和計算システム２００の処理フロー例を示す図。
【図６】乱数生成部２１ｘ、ｙ、ｚの処理フロー例を示す図。
【発明を実施するための形態】
【００１８】
本発明において対象となる計算は、０以上ｐ未満（ｐは素数）の任意の値ａ、ｂの暗号化または秘密分散による秘匿値[ａ]、[ｂ]に対する、定数倍、定数加算及び秘匿値同士の加算・乗算により構成される。例えば次のような計算である。
【００１９】
[αａ＋β]＝α[ａ]＋β（定数倍・定数加算）
[ａ＋ｂ]＝[ａ]＋[ｂ]（加算）
[ａ・ｂ]＝[ａ]・[ｂ]（乗算）
ここで、αとβはそれぞれ０以上ｐ未満の任意の値である。また、計算結果はｐで除した余りであるが、記載を簡略化するため、"mod p"の記載は省略した。本明細書内の説明および請求項では記載を簡略化するため、"mod p"の記載は省略する。第１式は、（αａ＋β）の秘匿値を、ａの秘匿値[ａ]に定数αを乗算し、定数βを加算することで求めることができることを示している。第２式は、(ａ＋ｂ)の秘匿値[ａ＋ｂ]を、aの秘匿値[ａ]とｂの秘匿値[ｂ]の加算で求めることができることを示している。第３式は、（ａ・ｂ）の秘匿値を、aの秘匿値[ａ]とｂの秘匿値[ｂ]の乗算で求めることができることを示している。本発明の秘匿積和結合システムでは、上記の３つの式が成り立つように秘匿化と定数倍、定数加算及び秘匿値同士の加算・乗算が実行できることを前提としている。なお、非特許文献１の秘匿関数計算には、加算、乗算、定数和、定数倍が備えられている。そのため、非特許文献１の秘匿関数計算によっても、上記の各式を計算することができるが、本発明では、より高速に計算する方法を示す。
【００２０】
本発明では、乱数ｒを乗じた上で行った秘匿計算の結果と秘匿計算を行った上で乱数を乗じた結果とを比較する。乱数ｒの存在により２つの計算結果が等しくなるように不正を行うことができないので、２つの計算結果が等しくないことをもって不正を検知できるというものである。これは、加法と乗法が、法を素数ｐとする領域で行われる場合、乱数ｒが掛かっている方は計算結果が乱数となるので、乱数ｒが掛かっていない方と掛かっている方との辻褄が合うような不正はできないことに基づく。
【００２１】
具体的には、上記の３つの式が成り立つので、０以上ｐ未満の任意の秘匿値[ａ]、[ｂ]、及び[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]に対して、以下の対応関係が成り立つ。
【００２２】
ｒ(α[ａ]＋β)＝α[ａ’]＋ｒ・β（定数倍・定数加算）
ｒ([ａ]＋[ｂ])＝[ａ’]＋[ｂ’]（加算）
ｒ([ａ]・[ｂ])＝[ａ’]・[ｂ’]（乗算）
ｒ([ａ]・[ｂ])＝[ｒ・ａ]・[ｂ]（乗算）
すなわち、左辺の(  )内の本来計算したい値（秘匿値[ｃ]）のｒ倍の値は、右辺の式で算出される（秘匿値[ｃ’]）。これにより、本来計算したい秘匿値[ｃ]に対して、不正がなければ[ｒ・ｃ]＝[ｃ’]すなわち[ｒ・ｃ−ｃ’]＝[０]となるような[ｃ’]を算出できる。これに対し、不正がある場合、すなわち左辺と右辺の計算結果が[ｃ]と[ｃ’]でなく、不正の値ｕ、ｖの加算により[ｃ＋ｕ]と[ｃ’＋ｖ]に改竄された場合、[ｒ(ｃ＋ｕ)−ｃ'’−ｖ]＝[ｒ(ｃ＋ｕ)−ｒ・ｃ−ｖ]＝[０]となるには、ｕ、ｖが[ｒ・ｕ−ｖ]＝[０]を満たす必要がある。しかし、ｒが乱数であるため攻撃者がこれを満たすようにすることができる確率は、ｒが非零乱数（１≦ｒ≦ｐ−１）である場合は１／(ｐ−１)、ｒが一様乱数（０≦ｒ≦ｐ−１）である場合は１／ｐにすぎない。そのため、[ｃ]と[ｃ’]を計算し、[ｒ・ｃ−ｃ’]が[０]かどうかをチェックすることで不正を検知できる。
【実施例１】
【００２３】
図１に秘匿積和結合システム１００の構成例を、図２にその処理フロー例をそれぞれ示す。秘匿積和結合システム１００は、３つの計算装置１０ｘ、１０ｙ、１０ｚを備える。秘匿積和結合システム１００は、ｎ個の０以上ｐ未満（ｐは素数）の任意の値Ａ０、…、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]に対し、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つの計算装置１０ｘ、１０ｙ、１０ｚで協調して行うことにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]を計算する。【００２４】
計算装置１０ｘは乱数生成部１１ｘと関数計算部１２ｘと不正検知部１３ｘとを備え、計算装置１０ｙは乱数生成部１１ｙと関数計算部１２ｙと不正検知部１３ｙとを備え、計算装置１０ｚは乱数生成部１１ｚと関数計算部１２ｚと不正検知部１３ｚとを備える。【００２５】
乱数生成部１１ｘ、１１ｙ、１１ｚは協調して、非零乱数ｒ（１以上ｐ未満の整数からランダムに選ばれた乱数）の秘匿値[ｒ]を生成する（Ｓ１）。具体的には例えば次のように生成する（図３参照）。まず、乱数生成部１１ｘが非零乱数ｒzを生成して乱数生成部１１ｙと共有し、乱数生成部１１ｙが非零乱数ｒXを生成して乱数生成部１１ｚと共有し、乱数生成部１１ｚが非零乱数ｒYを生成して乱数生成部１１ｘと共有する（Ｓ１−１）。続いて、非特許文献１で開示された秘匿方法によりｒX、ｒY、ｒZの秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する（Ｓ１−２）。そして、非特許文献１の不正検知付き乗算によりこれらを乗算して、秘匿値[ｒ]＝[ｒX・ｒY・ｒZ]を生成する（Ｓ１−３）。なお、ここでは乱数ｒ,ｒX,ｒY,ｒzが非零乱数である場合を例示したが、一様乱数（０以上ｐ未満の整数からランダムに選ばれた乱数）であっても構わない。一様乱数である場合には、Ｓ１の代わりに図６に示すＳ１１を実行する。具体的には、乱数生成部１１ｘ、１１ｙ、１１ｚがそれぞれ一様乱数ｒX,ｒY,ｒzを生成し（Ｓ１１−１）、非特許文献１で開示された秘匿方法によりｒX、ｒY、ｒZの秘匿値[ｒX]、[ｒY]、[ｒZ]を生成し（Ｓ１１−２）、これらを加算して秘匿値[ｒ]＝[ｒX＋ｒY＋ｒZ]を生成する（Ｓ１１−３）。【００２６】
関数計算部１２ｘ、１２ｙ、１２ｚは協調して、入力された秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]の各計算を行う（Ｓ２）。[Ｃ]と[Ｃ’]の計算は、並行して行うことで効率的に計算することができる。並行して計算するにあたり、定数、秘匿値、及び秘匿値のペアである秘匿ペアを組み合わた加算・乗算を定義する必要がある。定義される計算は１２通りある。関数ｆは１２通りの計算のいずれか又は複数が１回または複数回組み合わさって構成される。以下では、関数ｆの計算と１２通りの定義される計算とを区別するときには、定義される１２通りの計算を基本計算と呼ぶ。つまり、関数ｆは、１つの基本計算または複数の基本計算を組み合わせた関数である。【００２７】
説明において[ａ]、[ｂ]は、基本計算ごとの秘匿値を示し、[ｃ]は基本計算ごとの乱数ｒを乗算していない計算結果の秘匿値、[ｃ’]は基本計算ごとの乱数ｒを乗算した計算結果の秘匿値を示している。[ａ]、[ｂ]は、０以上ｐ未満の任意の値ａ、ｂの暗号化または秘密分散による秘匿値であり、[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]である。なお、関数ｆが複数の基本計算で構成される場合には、基本計算ごとに[ｃ]、[ｃ’]を算出する。例えば、[Ａ０]と[Ａ１]と[Ａ２]との加算であれば、１回目の基本計算として、[Ａ０]と[Ａ１]との加算を行う。１回目の基本計算では[Ａ０]が[ａ]であり、[Ａ１]が[ｂ]である。そして、１回目の基本計算の結果として[ｃ]、[ｃ’]を算出する。そして、２回目の基本計算では、１回目の結果[ｃ]、[ｃ’]を[ａ]、[ａ’]とし、[Ａ２]を[ｂ]として加算を行い、２回目の基本計算の結果である[ｃ]、[ｃ’]を求める。この例の場合、２回の加算の組合せなので、２回目の基本計算の結果[ｃ]、[ｃ’]が、関数ｆの関数値[Ｃ]、[Ｃ’]である。【００２８】
なお、基本計算のうち、秘匿値同士の加算、秘匿値に対する定数加算・定数倍、定数同士の加算・乗算の５通りについては、非特許文献１の秘匿関数計算の加算・乗算を適用すればよい。ここでは、その他の７通りの基本計算について説明する。
・秘匿ペア([ａ]、[ａ’])の定数倍
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに０以上ｐ未満の任意の定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])に対する定数加算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数を加算する関数により得られる関数値である場合、秘匿値[ｒ]に０以上ｐ未満の任意の定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とする。
・秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))の加算
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]の加算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とを非特許文献１の不正検知なし乗算により乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))の乗算
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ非特許文献１の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]の乗算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ非特許文献１の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。
・秘匿値[ａ]と秘匿値[ｂ]の乗算
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とを非特許文献１の不正検知なし乗算により乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ非特許文献１の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。【００２９】
不正検知部１３ｘ、１３ｙ、１３ｚは協調して、非特許文献１で開示された秘匿関数計算方法により、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する（Ｓ３）。秘匿値[ｒ・Ｃ−Ｃ’]を計算する際には、秘匿値[ｒ]をｒに復元した上で行うと、計算をより効率的に行うことができる。なお、関数ｆを構成する基本計算の中に秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算が含まれている場合には、その基本計算ごとに、その基本計算での[ｂ]、[ｂ’]を記録しておく。そして、ステップＳ３の処理に先立ち、不正検知部１３ｘ、１３ｙ、１３ｚが協調して非特許文献１で開示された秘匿関数計算方法により、それぞれの[ｂ]、[ｂ’]に対して秘匿値[ｒ・ｂ−ｂ’]を求める。そして、いずれかの[ｒ・ｂ−ｂ’]が[０]でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する（Ｓ３’）。なお、[ｒ・ｃ−ｃ']の値の非零性の確認は、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算を行うごとに実行してもよい。【００３０】
以上のように構成した本発明の秘匿積和結合システム、秘匿積和計算方法による演算の効率を非特許文献１の不正検知つき演算の効率と比較する。非特許文献１における計算量は、ほとんどが乱数生成及び物理的セキュアチャネルを用意できない場合の通信の暗号化・復号に係るものであり、暗号化・復号に係る計算量は通信回数に比例する。そのため、乱数生成回数と通信回数を比較することで両者の効率を比較することができる。なお、以下の説明中の「ラウンド数」とは、同時には送受信できない通信の回数である。例えば、他の計算装置から何らかの情報を受信した後でなければ処理を進められないような状態が多いと、ラウンド数が多くなる。
・本発明においては、全体として乱数生成のオーバーヘッドがある。
・秘匿ペアの定数倍は秘匿値の定数倍と同等（乱数生成回数、通信回数、ラウンド数いずれも０）。
・秘匿ペアに対する定数加算は、秘匿値に対する定数加算に対して同等（乱数生成回数、通信回数、ラウンド数いずれも０）。
・秘匿ペア同士の加算は、秘匿値同士の加算と同等（乱数生成回数、通信回数、ラウンド数いずれも０）。
・秘匿ペアと秘匿値の加算に関しては、本発明の場合、不正検知なし乗算１回のオーバーヘッドがある。
・秘匿ペア同士の乗算に関しては、非特許文献１の場合、平均乱数生成回数が１０回、平均通信回数が１８回、ラウンド数が４である。これに対し、本発明の場合、不正検知なし乗算２回と不正検知の際の復元１回で済み、平均乱数生成回数が２回、平均通信回数が６回、ラウンド数が２である。従って、乱数生成回数が５倍、通信回数が３倍、ラウンド数が２倍効率的になっている。なお、平均乱数生成回数とは、各計算装置が行う乱数生成の回数の平均である。例えば、１つの計算装置が３回乱数を生成し、他の２つの計算装置は乱数を生成しなかった場合、平均乱数生成回数は１回である。
・秘匿ペアと秘匿値の乗算に関しても、非特許文献１の場合、平均乱数生成回数が１０回、平均通信回数が１８回、ラウンド数が４である。これに対し、本発明の場合、不正検知なし乗算２回で済み、平均乱数生成回数が２回、平均通信回数が４回、ラウンド数が２である。従って、乱数生成回数が５倍、通信回数が４．５倍、ラウンド数が２倍効率的になっている。
・秘匿値と秘匿値の乗算に関しても、非特許文献１の場合、平均乱数生成回数が１０回、平均通信回数が１８回、ラウンド数が４である。これに対し、本発明の場合、不正検知なし乗算３回で済み、平均乱数生成回数が３回、平均通信回数が６回、ラウンド数が２である。従って、乱数生成回数が約３倍、通信回数が３倍、ラウンド数が２倍効率的になっている。【００３１】
以上より、本発明の場合、乗算以外において非特許文献１と同等もしくは非効率となる部分があるが、秘匿関数計算において主にボトルネックとなる乗算について大きく効率化されるため、全体として非特許文献１よりも効率的に計算を行うことができる。
【実施例２】
【００３２】
実施例２では、実施例１において関数ｆが排他的論理和（ＸＯＲ）、すなわち、入力[Ａ０]、…、[Ａｎ−１]に対し、関数値[Ｃ]を【００３３】
【数１】
2012121333.tif 000003
により計算する具体例を示す。なお、排他的論理和に限らず、加算と乗算のみで表される関数であれば、実施例１の構成により効率的に計算を行うことが可能である。【００３４】
ベースとなる秘匿計算は、非特許文献１の方法を用いる。まず、ＸＯＲは次式のように変形することができる。【００３５】
【数２】
2012121333.tif 000004
【００３６】
そのため、以下のように計算することができる。
１．乱数ｒの秘匿値[ｒ]を生成する。
２．各ｉ（i＝0, …,n-1）について、[Ａｉ−１／２]を計算する。
３．非特許文献１の不正検知なし乗算により、[ｃ'0]＝[ｒ(Ａ０−１／２)]を計算する。また、[ｃ0]＝[Ａ０−１／２]とおく。
４．ｉ＝１からｉ＝ｎ−１まで、(a)、(b)を繰り返す。
(a) [ｃi]＝[−２(ｃi-1−１／２)(Ａｉ−１／２)＋１／２]
(b) [ｃ'i]＝[−２(ｃ'i-1−１／２)(Ａｉ−１／２)＋ｒ／２]
５．秘匿値[ｒ]を復元し、ｒを得る。
６．([ｃn-1],[ｃ'n-1])に対して、[ｒ・ｃn-1−ｃ'n-1]を計算する。計算結果が[０]ならば、[ｃn-1]を出力して終了し、[０]でなければ不正検知を表す情報を出力して終了する。
なお、上記の１は実施例１のＳ１に、２〜４はＳ２に、５〜６はＳ３にそれぞれ相当する。【００３７】
非特許文献１の方法で同じ計算を行う場合、乗算をｎ−１回行い、平均乱数生成回数は定数を除いて１０ｎ回、平均通信回数は１８ｎ回、ラウンド数は４ｎとなる。これに対し、本実施例では不正検知なし乗算２回ずつでよいため、平均乱数生成回数は２ｎ回、平均通信回数は４ｎ回、ラウンド数は２ｎである。そのため、乱数生成回数は５倍、平均通信回数は４．５倍、ラウンド数は２倍効率的になっている。【００３８】
＜参考：不正検知の証明＞
秘匿ペアは、加算及び乗算の結果に対応しているため、秘匿ペアごとに不正がなかった場合の正しい計算結果が１つ存在する。この不正がない場合の結果がａであるような秘匿ペアの集合をＰaと書く。
補題
ｒを非零乱数を表す変数とするとき、秘匿ペア([ｃ]、[ｃ’])∈Ｐaが、([ａ＋ｕ]、[ｒ・ａ＋ｖ])で表されれば、[ｒ・ｃ−ｃ’]＝[０]をチェックすることで、１−１／(ｐ−１）以上の確率で不正検知できる（ｕ、ｖは不正値）。
証明
不正がない場合は、不正を検知できる必要がないため、不正値ｕ、ｖについてｕ≠０またはｖ≠０と仮定してよい。【００３９】
ｕ≠０のとき、[ｒ・ｃ−ｃ’]＝[ｒ(ａ＋ｕ)−ｒ・ａ−ｖ]＝[ｒ・ｕ−ｖ]となり、ｒが１以上ｐ未満の一様な乱数でかつｘ≠０であるため、[ｒ・ｕ−ｖ]＝[０]となる確率、すなわち不正が検出されない確率は、攻撃者から見て１／(ｐ−１)である。逆に検出される確率は、１−１／(ｐ−１）である。【００４０】
ｕ＝０のとき、ｖ≠０でなければならず、[ｒ・ｕ−ｖ]≠[０]であるため、必ず不正が検出される。【００４１】
上記のような([ａ＋ｕ]、[ｒ・ａ＋ｖ])の集合をＲa(＝{([ａ＋ｕ]、[ｒ・ａ＋ｖ])|ｕ，ｖ∈Ｚ／ｐＺ})と書く。次に、実施例１の関数計算部１２ｘ、１２ｙ、１２ｚにおいて定義した算法（１２通りのいずれか）を行った回数ｋに関する帰納法により、次の条件を示す。【００４２】
条件：([ｂ]、[ｂ’])の集合について不正があれば、１−１／(ｐ−１）以上の確率で検知され、そうでなければ上記算法によって生成されるＰaに属する秘匿ペアがすべてＲaに属する。【００４３】
ｋ＝０のとき、([ｂ]、[ｂ’])は生成されておらず不存在であるため、条件は満たされている。【００４４】
ｋ＝ｍ＋１のとき、ｋ＝ｍまでで条件が成り立つと仮定すると、ｍ＋１回目の演算について、それぞれ以下が成り立つ。【００４５】
・秘匿ペアの定数倍：
([ａ＋ｕ]、[ｒ・ａ＋ｖ])∈Ｒaと仮定すれば
(α[ａ＋ｕ]、α[ｒ・ａ＋ｖ])＝
([α・ａ＋α・ｕ]、[ｒ・α・ａ＋α・ｖ])∈Ｒαa
・秘匿ペアに対する定数加算：
([ａ＋ｕ]、[ｒ・ａ＋ｖ])∈Ｒaと仮定すれば
([ａ＋ｕ]＋β、[ｒ・ａ＋ｖ]＋[ｒ・β])＝
([ａ＋β＋ｕ]、[ｒ(ａ＋β)＋ｖ])∈Ｒa+β
・秘匿ペア同士の加算
([ａ＋ｕ]、[ｒ・ａ＋ｖ])∈Ｒa、([ｂ＋ｕ’]、[ｒ・ｂ＋ｖ’])∈Ｒbと仮定すれば、
([ａ＋ｕ]＋[ａ’＋ｕ’]、[ｒ・ａ＋ｖ]＋[ｒ・ｂ＋ｖ’])＝
([ａ＋ｂ＋ｕ＋ｕ’]、[ｒ(ａ＋ｂ)＋ｖ＋ｖ’])∈Ｒa+b
・秘匿ペアと秘匿値の加算
秘匿ペア同士の加算と同じ。【００４６】
・秘匿ペア同士の乗算
([ａ＋ｕ]、[ｒ・ａ＋ｖ])∈Ｒa、([ｂ＋ｕ’]、[ｒ・ｂ＋ｖ’])∈Ｒbと仮定すれば、ｖ’＝０が成り立つ場合、
([ａ＋ｕ][ｂ＋ｕ’]、[ｒ・ａ＋ｖ][ｂ＋ｖ’])＝
([ａ・ｂ＋ａ・ｕ’＋ｂ・ｕ＋ｕ・ｕ’]、[ｒ・ａ・ｂ＋ｒ・ａ・ｖ’＋ｂ・ｖ＋ｖ・ｖ’])∈Ｒab
・秘匿ペアと秘匿値の乗算
([ａ＋ｕ]、[ｒ・ａ＋ｖ])∈Ｒaで、[ｂ]が秘匿値のとき、
([ａ＋ｕ][ｂ]、[ｒ・ａ＋ｖ][ｂ])＝
([ａ・ｂ＋ｂ・ｕ]、[ｒ・ａ・ｂ＋b・ｖ])∈Ｒab
・秘匿値と秘匿値の乗算
[ａ]、[ｂ]が秘匿値のとき、
([ａ][ｂ]、[ｒ・ａ][ｂ])＝([ａ・ｂ]、[ｒ・ａ・ｂ])∈Ｒab
このとき、([ｂ]、[ｂ’])の集合のｍ番目の要素までに不正があれば、仮定より１−１／(ｐ−１）以上の確率で検知され、条件を満たす。ｍ＋１番目が秘匿ペア同士の乗算であった場合に、([ｂ]、[ｂ’])の集合に([ｂ＋ｕ’]、[ｒ・ｂ＋ｖ’])に加わるが、仮定よりこの秘匿ペアはＲbに属するため、これに対する不正があった場合、１−１／(ｐ−１）以上の確率で検知される。([ｂ＋ｕ’]、[ｒ・ｂ＋ｖ’])に対する不正がない場合、ｖ’＝０であるから、上記各演算に関する性質より、ｍ＋１番目の演算結果の秘匿ペアはＰaに属せばＲaに属する。【００４７】
よって、帰納法の仮定より、上記条件は実施例１の関数計算部１２ｘ、１２ｙ、１２ｚにおいて定義した算法の任意の組み合わせについて成り立つ。すなわち、([ｂ]、[ｂ’])の集合の要素に不正が一つでもあれば１−１／(ｐ−１）以上の確率で検知され、不正が一つもなければ任意の秘匿ペアの不正は１−１／(ｐ−１）以上の確率で検知される。【００４８】
結論として、([ｂ]、[ｂ’])の集合の要素の不正検知処理、及び出力となる秘匿ペア[ｃ]、[ｃ’]の不正検知処理を行えば、これら出力となる秘匿ペアの不正は１−１／(ｐ−１）以上の確率で検知される。
【実施例３】
【００４９】
実施例１では、非特許文献１に示される不正検知付き乗算を備える秘匿関数計算を基礎とする構成を説明したが、実施例３では、Shamir方式を前提とした構成を説明する。当該実施例３では、実施例１における乱数生成を一様乱数生成に限定することで不正検知付き乗算を不要にし、Shamir方式への適用を可能にする。これにより、高速かつ安全に算術演算を行うことが可能となり、かつ、非特許文献１の方式と比べデータ量を半分に抑えることができる。更に、実施例３の秘匿積和結合システムはShamir方式を前提としているので、計算装置が４個以上であっても構わない。【００５０】
Shamir方式によるデータの秘匿方法及び復元方法を説明する。Shamir方式においては、計算装置がｑ個（ｑ≧３）であるとき、その全部又は一部であるｔ＋１個の計算装置で秘密を復元できる。ここで、Ｊを選択されたｔ＋１個の計算装置の番号ｉの集合とする。Ｊに属するｔ＋１個の計算装置でデータｓ（０≦ｓ≦ｐ−１）を秘匿するには、一様乱数をｔ個（ｒ1, …,ｒt）を生成し、各ｉ番目の計算装置に、ｓi＝ｓ＋ｒ1・ｉ＋…＋ｒt・ｉtを分散する。このようにｔ＋１個の計算装置に分散されたデータｓの秘匿値[ｓ]（ｔ＋１個の断片ｓiの集合）は、各計算装置に分散された断片ｓiから、次式を計算することにより復元できる。【００５１】
【数３】
2012121333.tif 000005
【００５２】
Shamir方式は、秘匿が加法的な分散であるため、可換性から、分散値を加算してから復元しても、復元してから加算しても結果は等しい。すなわち、加算と定数倍は、分散したまま通信なしで行うことが可能である。また、乗算も、通信及び乱数生成が必要となるが可能である。したがって、上述の
[αａ＋β]＝α[ａ]＋β（定数倍・定数加算）
[ａ＋ｂ]＝[ａ]＋[ｂ]（加算）
[ａ・ｂ]＝[ａ]・[ｂ]（乗算）
の３つの式を成り立たせることができる。そのため、論理回路を構成でき、いかなる計算を実行することも可能である。以下、データａ、ｂが、それぞれ３個の計算装置Ｘ、Ｙ、Ｚに分散されて秘匿されている場合（ｑ＝３）のShamir方式による秘匿関数計算の具体例を示す。すなわち、データａの秘匿値[ａ]の断片ａ1、ａ2、ａ3とデータｂの秘匿値[ｂ]の断片ｂ1、ｂ2、ｂ3は、計算装置Ｘに（ａ1、ｂ1）が、計算装置Ｙに（ａ2、ｂ2）が、計算装置Ｚに（ａ3、ｂ3）が、それぞれ分散されている。なお、ｔ＝１（いずれか２個の計算装置で秘密を復元可能）とする。
(1)ｃ＝ａ＋ｂの秘匿関数計算
各計算装置が、[ａ]と[ｂ]との和である[ｃ]の断片ｃj（ｊ＝１、…、ｑ）を、ｃj＝ａj＋ｂjにより計算することにより得る。この例では、ｑ＝３である。そして、計算装置Ｘがｃ1＝ａ1＋ｂ1を計算し、計算装置Ｙにおいてｃ2＝ａ2＋ｂ2を計算し、計算装置Ｚがｃ3＝ａ3＋ｂ3を計算する。
(2)ｃ＝ａ＋αの秘匿関数計算（αは既知の定数）
各計算装置が、[ａ]と定数αとの和である[ｃ]の断片ｃjをｃj＝ａj＋αにより計算することにより得る。この例では、計算装置Ｘがｃ1＝ａ1＋αを計算し、計算装置Ｙがｃ2＝ａ2＋αを計算し、計算装置Ｚがｃ3＝ａ3＋αを計算する。
(3)ｃ＝ａ・αの秘匿関数計算
各計算装置が、[ａ]と定数αとの積である[ｃ]の断片ｃjをｃj＝ａj・αにより計算することにより得る。この例では、計算装置Ｘがｃ1＝ａ1・αを計算し、計算装置Ｙがｃ2＝ａ2・αを計算し、計算装置Ｚがｃ3＝ａ3・αを計算する。【００５３】
(4)ｃ＝ａ・ｂの秘匿関数計算（不正検知なし乗算）
[ａ]と[ｂ]との積[ｃ]は、次のように求める。
(i)各計算装置が、ｄi＝ａi・ｂi（ｉ＝１、…、２ｔ＋１）を計算する。この例では、計算装置Ｘがｄ0＝ａ0・ｂ0を計算し、計算装置Ｙがｄ1＝ａ1・ｂ1を計算し、計算装置Ｚがｄ2＝ａ2・ｂ2を計算する。
(ii) 上記のShamir方式によるデータの秘匿方法によりｄ1、ｄ2、ｄ3の秘匿値[ｄ1]、[ｄ2]、[ｄ3]を生成する。この例では、[ｄ1]の断片をｄ1,0、ｄ1,1、ｄ1,2、[ｄ2]の断片をｄ2,0、ｄ2,1、ｄ2,2、[ｄ3]の断片をｄ3,0、ｄ3,1、ｄ3,2とする。そして、計算装置Ｘがｄ1,0、ｄ2,0、ｄ3,0を記録し、計算装置Ｙがｄ1,1、ｄ2,1、ｄ3,1を記録し、計算装置Ｚがｄ1,2、ｄ2,2、ｄ3,2を記録することで、ｄ1、ｄ2、ｄ3を秘匿する。
(iii) 各計算装置が、[ａ]と[ｂ]との積[ｃ]の断片ｃjを、次式により計算して得る。この例では、計算装置Ｘ、Ｙ、Ｚがそれぞれｃ1、ｃ2、ｃ3を計算する。【００５４】
【数４】
2012121333.tif 000006
【００５５】
図４に、Shamir方式に基づく秘匿積和結合システム２００の構成例を、図５にその処理フロー例を示す。秘匿積和結合システム２００は、ｑ個の計算装置を備える。ここでは、実施例１と同様、計算装置が３個の場合（計算装置２０ｘ、２０ｙ、２０ｚ）で説明する。【００５６】
秘匿積和結合システム２００は、ｎ個の０以上ｐ未満の任意の値Ａ０、…、Ａｎ−１の秘密分散による秘匿値[Ａ０]、…、[Ａｎ−１]に対し、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つの計算装置２０ｘ、２０ｙ、２０ｚで協調して行うことにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]を計算する。【００５７】
計算装置２０ｘは乱数生成部２１ｘと関数計算部２２ｘと不正検知部２３ｘとを備え、計算装置２０ｙは乱数生成部２１ｙと関数計算部２２ｙと不正検知部２３ｙとを備え、計算装置２０ｚは乱数生成部２１ｚと関数計算部２２ｚと不正検知部２３ｚとを備える。【００５８】
乱数生成部２１ｘ、２１ｙ、２１ｚは協調して、一様乱数ｒの秘匿値[ｒ]を生成する（Ｓ１１）。具体的には例えば次のように生成する（図６参照）。まず、乱数生成部２１ｘが一様乱数ｒXを、乱数生成部２１ｙが一様乱数ｒYを、乱数生成部２１ｚが一様乱数ｒZをそれぞれ生成する（Ｓ１１−１）。続いて、上記のShamir方式によるデータの秘匿方法によりｒX、ｒY、ｒZの秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する。具体的には[ｒX]の断片をｒX,0、ｒX,1、ｒX,2、[ｒY]の断片をｒY,0、ｒY,1、ｒY,2、[ｒZ]の断片をｒZ,0、ｒZ,1、ｒZ,2とする。そして、乱数生成部２１ｘがｒX,0、ｒY,0、ｒZ,0を記録し、乱数生成部２１ｙがｒX,1、ｒY,1、ｒZ,1を記録し、乱数生成部２１ｚがｒX,2、ｒY,2、ｒZ,2を記録する（Ｓ１１−２）。このように断片を分散して記録することで秘匿する。そして、乱数生成部２１ｘがｒ0＝ｒX,0＋ｒY,0＋ｒZ,0を計算し、乱数生成部２１ｙがｒ1＝ｒX,1＋ｒY,1＋ｒZ,1を計算し、乱数生成部２１ｚがｒ2＝ｒX,2＋ｒY,2＋ｒZ,2を計算することで、秘匿値[ｒ]の断片ｒ0、ｒ1、ｒ2を得る（Ｓ１１−３）。【００５９】
関数計算部２２ｘ、２２ｙ、２２ｚは協調して、入力された秘匿値[Ａ０]、…、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、…、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、…、[Ａｎ−１])]の各計算を行う（Ｓ１２）。[Ｃ]と[Ｃ’]の計算は、並行して行うことで効率的に計算することができる。並行して計算するにあたり、定数、秘匿値、及び秘匿値のペアである秘匿ペアを組み合わた加算・乗算を定義する必要がある。なお、定義すべき計算が、実施例１で説明した基本計算に相当する。つまり、実施例３でも関数ｆは、１つの基本計算または複数の基本計算を組み合わせた関数である。【００６０】
定義すべき加算・乗算のうち、秘匿値同士の加算、秘匿値に対する定数加算・定数乗算については、上記のShamir方式の秘匿関数計算方法の加算・乗算を適用すればよい。そこで、ここでは、その他の計算について説明する。説明において[ａ]、[ｂ]は、０以上ｐ未満の任意の値ａ、ｂの暗号化または秘密分散による秘匿値であり、[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]であるとする。なお、関数ｆが複数の基本計算で構成される場合には、基本計算ごとに[ｃ]、[ｃ’]を算出する。例えば、[Ａ０]と[Ａ１]と[Ａ２]との加算であれば、１回目の基本計算として、[Ａ０]と[Ａ１]との加算を行う。１回目の基本計算では[Ａ０]が[ａ]であり、[Ａ１]が[ｂ]である。そして、１回目の基本計算の結果として[ｃ]、[ｃ’]を算出する。そして、２回目の基本計算では、１回目の結果[ｃ]、[ｃ’]を[ａ]、[ａ’]とし、[Ａ２]を[ｂ]として加算を行い、２回目の基本計算の結果である[ｃ]、[ｃ’]を求める。この例の場合、２回の加算の組合せなので、２回目の基本計算の結果[ｃ]、[ｃ’]が、関数ｆの関数値[Ｃ]、[Ｃ’]である。
・秘匿ペア([ａ]、[ａ’])の定数倍
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに０以上ｐ未満の任意の定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])に対する定数加算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数を加算する関数により得られる関数値である場合、秘匿値[ｒ]に０以上ｐ未満の任意の定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とする。
・秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))の加算
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]の加算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とをShamir方式による秘匿関数計算方法の不正検知なし乗算により乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とする。
・秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))の乗算
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’']と秘匿値[ｂ]を、それぞれShamir方式による秘匿関数計算方法の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。
・秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]の乗算
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれShamir方式による秘匿関数計算方法の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。
・秘匿値[ａ]と秘匿値[ｂ]の乗算
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とをShamir方式による秘匿関数計算方法の不正検知なし乗算により乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれShamir方式によるデータの秘匿方法の不正検知なし乗算により乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とする。【００６１】
不正検知部２３ｘ、２３ｙ、２３ｚは協調して、Shamir方式による秘匿関数計算方法により、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する（Ｓ１３）。秘匿値[ｒ・Ｃ−Ｃ’]を計算する際には、秘匿値[ｒ]をｒに復元した上で行うと、計算をより効率的に行うことができる。なお、関数ｆを構成する基本計算の中に秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算が含まれている場合には、その基本計算ごとに、その基本計算での[ｂ]、[ｂ’]を記録しておく。そして、ステップＳ３の処理に先立ち、不正検知部２３ｘ、２３ｙ、２３ｚが協調してShamir方式による秘匿関数計算方法により、それぞれの[ｂ]、[ｂ’]に対して秘匿値[ｒ・ｂ−ｂ’]を求める。そして、いずれかの[ｒ・ｂ−ｂ’]が[０]でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する（Ｓ１３’）。なお、[ｒ・ｃ−ｃ']の値の非零性の確認は、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算を行うごとに実行してもよい。【００６２】
以上説明した本発明の秘匿積和結合システム、秘匿積和計算方法における各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明の秘匿積和計算システムの各構成要素の機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。本発明の各実施例の秘匿積和計算システム、計算装置をコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。
【図１】
2012121333.tif 000007
【図２】
2012121333.tif 000008
【図３】
2012121333.tif 000009
【図４】
2012121333.tif 000010
【図５】
2012121333.tif 000011
【図６】
2012121333.tif 000012
【手続補正書】
【提出日】平成25年8月21日(2013.8.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
(1)Ｘ、Ｙ、Ｚに分散された秘匿データａの復元
Ｘは、Ｙにａ0を送信し、Ｚにａ1を送信する。Ｙは、Ｚにａ1を送信し、Ｘにａ2を送信する。Ｚは、Ｘにａ2を送信し、Ｙにａ0を送信する。
Ｘは、Ｙから受信したａ2とＺから受信したａ2とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。Ｙは、Ｘから受信したａ0とＺから受信したａ0とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。Ｚは、Ｘから受信したａ1とＹから受信したａ1とが一致していれば、ａ0＋ａ1＋ａ2を計算してａを復元する。
(2)ｃ＝ａ＋ｂの秘密計算
データｂもデータａと同様な方法により、Ｘに（ｂ0、ｂ1）が、Ｙに（ｂ1、ｂ2）が、Ｚに（ｂ2、ｂ0）が、それぞれ分散されて秘匿されているとする。
このとき、Ｘは（ｃ0、ｃ1）＝（ａ0＋ｂ0、ａ1＋ｂ1）を計算して記録し、Ｙは（ｃ1、ｃ2）＝（ａ1＋ｂ1、ａ2＋ｂ2）を計算して記録し、Ｚは（ｃ2、ｃ0）＝（ａ2＋ｂ2、ａ0＋ｂ0）を計算して記録する。
(3)ｃ＝ａ＋αの秘密計算（αは既知の定数）
Ｘは、（ｃ0、ｃ1）＝（ａ0＋α、ａ1）を計算して記録し、Ｚは、（ｃ2、ｃ0）＝（ａ2、ａ0＋α）を計算して記録する。Ｙの処理は無い。
(4)ｃ＝ａ・αの秘密計算
Ｘは、（ｃ0、ｃ1）＝（ａ0・α、ａ1・α）を計算して記録し、Ｙは、（ｃ1、ｃ2）＝（ａ1・α、ａ2・α）を計算して記録し、Ｚは、（ｃ2、ｃ0）＝（ａ2・α、ａ0・α）を計算して記録する。
(5)ｃ＝ａ・ｂの秘密計算（不正検知なし乗算）
まず、Ｘは、乱数ｒ1、ｒ2、ｃ0を生成し、ｃ1＝(ａ0＋ａ1)(ｂ0＋ｂ1)−ｒ1−ｒ2−ｃ0を計算し、Ｙに(ｒ1、ｃ1)を、Ｚに(ｒ2、ｃ0)を送信する。
続いて、Ｙは、ｙ＝ａ1・ｂ2＋ｂ1・ａ2＋ｒ1を計算し、Ｚにｙを送信する。また、Ｚは、ｚ＝ａ2・ｂ0＋ｂ2・ａ0＋ｒ2を計算し、Ｙにｚを送信する。
続いて、ＹとＺはそれぞれ、ｃ2＝ｙ＋ｚ＋ａ2・ｂ2を計算する。
そして、Ｘは(ｃ0、ｃ1)を記録し、Ｙは(ｃ1、ｃ2)を記録し、Ｚは(ｃ2、ｃ0)を記録する。
(6) ｃ＝ａ・ｂの秘密計算（不正検知付き乗算）
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
【図１】秘匿積和結合システム１００の構成例を示す図。
【図２】秘匿積和結合システム１００の処理フロー例を示す図。
【図３】乱数生成部１１ｘ、ｙ、ｚの処理フロー例を示す図。
【図４】秘匿積和結合システム２００の構成例を示す図。
【図５】秘匿積和結合システム２００の処理フロー例を示す図。
【図６】乱数生成部２１ｘ、ｙ、ｚの処理フロー例を示す図。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
ｒ(α[ａ]＋β)＝α[ａ’]＋ｒ・β（定数倍・定数加算）
ｒ([ａ]＋[ｂ])＝[ａ’]＋[ｂ’]（加算）
ｒ([ａ]・[ｂ])＝[ａ’]・[ｂ]（乗算）
ｒ([ａ]・[ｂ])＝[ｒ・ａ]・[ｂ]（乗算）
すなわち、左辺の(  )内の本来計算したい値（秘匿値[ｃ]）のｒ倍の値は、右辺の式で算出される（秘匿値[ｃ’]）。これにより、本来計算したい秘匿値[ｃ]に対して、不正がなければ[ｒ・ｃ]＝[ｃ’]すなわち[ｒ・ｃ−ｃ’]＝[０]となるような[ｃ’]を算出できる。これに対し、不正がある場合、すなわち左辺と右辺の計算結果が[ｃ]と[ｃ’]でなく、不正の値ｕ、ｖの加算により[ｃ＋ｕ]と[ｃ’＋ｖ]に改竄された場合、[ｒ(ｃ＋ｕ)−ｃ’−ｖ]＝[ｒ(ｃ＋ｕ)−ｒ・ｃ−ｖ]＝[０]となるには、ｕ、ｖが[ｒ・ｕ−ｖ]＝[０]を満たす必要がある。しかし、ｒが乱数であるため攻撃者がこれを満たすようにすることができる確率は、ｒが非零乱数（１≦ｒ≦ｐ−１）である場合は１／(ｐ−１)、ｒが一様乱数（０≦ｒ≦ｐ−１）である場合は１／ｐにすぎない。そのため、[ｃ]と[ｃ’]を計算し、[ｒ・ｃ−ｃ’]が[０]かどうかをチェックすることで不正を検知できる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
不正検知部２３ｘ、２３ｙ、２３ｚは協調して、Shamir方式による秘匿関数計算方法により、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する（Ｓ１３）。秘匿値[ｒ・Ｃ−Ｃ’]を計算する際には、秘匿値[ｒ]をｒに復元した上で行うと、計算をより効率的に行うことができる。なお、関数ｆを構成する基本計算の中に秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算が含まれている場合には、その基本計算ごとに、その基本計算での[ｂ]、[ｂ’]を記録しておく。そして、ステップＳ１３の処理に先立ち、不正検知部２３ｘ、２３ｙ、２３ｚが協調してShamir方式による秘匿関数計算方法により、それぞれの[ｂ]、[ｂ’]に対して秘匿値[ｒ・ｂ−ｂ’]を求める。そして、いずれかの[ｒ・ｂ−ｂ’]が[０]でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する（Ｓ１３’）。なお、[ｒ・ｃ−ｃ']の値の非零性の確認は、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))との乗算を行うごとに実行してもよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
以上説明した本発明の秘匿積和結合システム、秘匿積和計算方法における各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明の秘匿積和結合システムの各構成要素の機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。本発明の各実施例の秘匿積和結合システム、計算装置をコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、・・・、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]のように計算する秘匿積和結合システムであって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
当該秘匿積和結合システムは、ａ，ｂ，α，βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
前記計算装置は、
他の少なくとも２つの計算装置の乱数生成部と協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成部と、
他の少なくとも２つの計算装置の関数計算部と協調して、前記秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、・・・、[Ａｎ−１])]を計算する関数計算部と、
他の少なくとも２つの計算装置の不正検知部と協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知部と、
を備える
ことを特徴とする秘匿積和結合システム。
【請求項２】
請求項１に記載の秘匿積和結合システムであって、
前記関数計算部は、
[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]であるとき、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数α倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数βを加算する関数により得られる関数値である場合、秘匿値[ｒ]に定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とを乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ']と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とを乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
前記不正検知部は、([ｃ]、[ｃ’])が秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合には、更に、他の２つの計算装置の不正検知部と協調して秘匿値[ｒ・ｂ−ｂ’]を求め、[ｒ・ｂ−ｂ’]が０でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する
ことを特徴とする秘匿積和結合システム。
【請求項３】
請求項１又は２に記載の秘匿積和結合システムであって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
計算装置Ｘの乱数生成部は、１以上ｐ未満の乱数ｒzを生成して計算装置Ｙの乱数生成部と共有し、
計算装置Ｙの乱数生成部は、１以上ｐ未満の乱数ｒXを生成して計算装置Ｚの乱数生成部と共有し、
計算装置Ｚの乱数生成部は、１以上ｐ未満の乱数ｒYを生成して計算装置Ｘの乱数生成部と共有し、
前記３つの計算装置の各乱数生成部は協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成し、これらを乗算して秘匿値[ｒ]＝[ｒX・ｒY・ｒZ]を生成する
ことを特徴とする秘匿積和結合システム。
【請求項４】
請求項１又は２に記載の秘匿積和結合システムであって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
計算装置Ｘの乱数生成部は、０以上ｐ未満の乱数ｒzを生成して計算装置Ｙの乱数生成部と共有し、
計算装置Ｙの乱数生成部は、０以上ｐ未満の乱数ｒXを生成して計算装置Ｚの乱数生成部と共有し、
計算装置Ｚの乱数生成部は、０以上ｐ未満の乱数ｒYを生成して計算装置Ｘの乱数生成部と共有し、
前記３つの計算装置の各乱数生成部は協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成し、これらを乗算して秘匿値[ｒ]＝[ｒX＋ｒY＋ｒZ]を生成する
ことを特徴とする秘匿積和結合システム。
【請求項５】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、・・・、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]のように計算する秘匿積和結合システムを構成する前記計算装置であって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
前記秘匿積和結合システムは、ａ，ｂ，α，βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
他の少なくとも２つの計算装置の乱数生成部と協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成部と、
他の少なくとも２つの計算装置の関数計算部と協調して、前記秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、・・・、[Ａｎ−１])]を計算する関数計算部と、
他の少なくとも２つの計算装置の不正検知部と協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知部と、
を備える計算装置。
【請求項６】
ｐを素数とし、ｎ個の０以上ｐ未満の任意の値Ａ０、・・・、Ａｎ−１の暗号化または秘密分散による秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆによる秘匿関数計算を３つ以上の計算装置で協調して行うことにより、秘匿された関数値[Ｃ]を[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]のように計算する秘匿積和結合方法であって、
[]は、値が暗号化または秘密分散により秘匿されていることを表す記号であり、
当該秘匿積和結合方法では、ａ，ｂ，α，βを０以上ｐ未満の任意の値とするときに、
[αａ＋β]＝α[ａ]＋β
[ａ＋ｂ]＝[ａ]＋[ｂ]
[ａ・ｂ]＝[ａ]・[ｂ]
が成り立ち、
前記３つ以上の計算装置で協調して、０以上ｐ未満の乱数ｒの秘匿値[ｒ]を生成する乱数生成ステップと、
前記３つ以上の計算装置で協調して、前記秘匿値[Ａ０]、・・・、[Ａｎ−１]について、加算若しくは乗算又はその両方からなる関数ｆにより、秘匿された関数値[Ｃ]＝[ｆ([Ａ０]、・・・、[Ａｎ−１])]、[Ｃ’]＝[ｒ・ｆ([Ａ０]、・・・、[Ａｎ−１])]を計算する関数計算ステップと、
前記３つ以上の計算装置で協調して、秘匿値[ｒ・Ｃ−Ｃ’]を求め、[ｒ・Ｃ−Ｃ’]が[０]であれば[Ｃ]を出力し、[０]でなければ不正検知を表す情報を出力する不正検知ステップと、
を実行する秘匿積和結合方法。
【請求項７】
請求項６に記載の秘匿積和結合方法であって、
前記関数計算ステップは、
[ａ’]＝ｒ・[ａ]、[ｂ’]＝ｒ・[ｂ]であるとき、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])を定数α倍する関数により得られる関数値である場合、秘匿ペア([ａ]、[ａ’])のそれぞれに定数αを乗算して得られた秘匿ペア(α・[ａ]、α・[ａ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])に定数βを加算する関数により得られる関数値である場合、秘匿値[ｒ]に定数βを乗算して秘匿値[ｒ・β]を求め、秘匿値[ａ]に定数βを、秘匿値[ａ’]に秘匿値[ｒ・β]をそれぞれ加算して得られた秘匿ペア([ａ]＋β、[ａ’]＋[ｒ・β])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を加算する関数により得られる関数値である場合、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ']に秘匿値[ｂ']をそれぞれ加算して得られた秘匿ペア([ａ]＋[ｂ]、[ａ’]＋[ｂ’]) を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを加算する関数により得られる関数値である場合、秘匿値[ｂ]と秘匿値[ｒ]とを乗算して秘匿値[ｂ’]を求め、秘匿値[ａ]に秘匿値[ｂ]を、秘匿値[ａ’]に秘匿値[ｂ’]をそれぞれ加算して得られた([ａ]＋[ｂ]、[ａ’]＋[ｂ’])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ']と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿ペア([ａ]、[ａ’])と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
([ｃ]、[ｃ’])が、秘匿値[ａ]と秘匿値[ｂ]とを乗算する関数により得られる関数値である場合、秘匿値[ａ]と秘匿値[ｒ]とを乗算して秘匿値[ａ’]を求め、秘匿値[ａ]と秘匿値[ｂ]、秘匿値[ａ’]と秘匿値[ｂ]を、それぞれ乗算して得られた秘匿ペア([ａ]・[ｂ]、[ａ’]・[ｂ])を([ｃ]、[ｃ’])とし、
前記不正検知ステップは、([ｃ]、[ｃ’])が秘匿ペア同士（([ａ]、[ａ’])と([ｂ]、[ｂ’]))を乗算する関数により得られる関数値である場合には、更に、前記３つの計算装置で協調して秘匿値[ｒ・ｂ−ｂ’]を求め、[ｒ・ｂ−ｂ’]が０でない場合にも、[Ｃ]を出力せずに不正検知を表す情報を出力する
ことを特徴とする秘匿積和結合方法。
【請求項８】
請求項６又は７に記載の秘匿積和結合方法であって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
前記乱数生成ステップは、
計算装置Ｘが１以上ｐ未満の乱数ｒzを生成して計算装置Ｙと共有し、計算装置Ｙが１以上ｐ未満の乱数ｒXを生成して計算装置Ｚと共有し、計算装置Ｚが１以上ｐ未満の乱数ｒYを生成して計算装置Ｘと共有する断片共有サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する断片秘匿サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を乗算することにより、秘匿値[ｒ]＝[ｒX・ｒY・ｒZ]を生成する断片結合サブステップと、
を実行する
ことを特徴とする秘匿積和結合方法。
【請求項９】
請求項６又は７に記載の秘匿積和結合方法であって、
秘匿関数計算を協調して行う前記計算装置は、計算装置Ｘ、計算装置Ｙ、及び計算装置Ｚの３つであり、
前記乱数生成ステップは、
計算装置Ｘが０以上ｐ未満の乱数ｒzを生成して計算装置Ｙと共有し、計算装置Ｙが０以上ｐ未満の乱数ｒXを生成して計算装置Ｚと共有し、計算装置Ｚが０以上ｐ未満の乱数ｒYを生成して計算装置Ｘと共有する断片共有サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を生成する断片秘匿サブステップと、
前記３つの計算装置で協調して、秘匿値[ｒX]、[ｒY]、[ｒZ]を乗算することにより、秘匿値[ｒ]＝[ｒX＋ｒY＋ｒZ]を生成する断片結合サブステップと、
を実行する
ことを特徴とする秘匿積和結合方法。
【請求項１０】
請求項１乃至４のいずれかに記載の秘匿積和結合システム又は請求項５記載の計算装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2012121333.tif 000013
2012121333.tif 000014
2012121333.tif 000015
2012121333.tif 000016