(57)【特許請求の範囲】
【請求項１】
入力値の関数値である演算結果の秘密分散値を得る秘密計算装置であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を格納する記憶部と、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力部と、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力される入力部と、
前記取得値が前記入力部に入力される場合には、少なくとも前記取得値を用いて前記秘密分散値を得る演算部と、
を有し、
前記演算結果が前記入力値ａと第２入力値ｂとの乗算結果であり、
前記入力値ａが前記サブシェアａ０Ｐ，ａ１Ｐ，ａ２Ｐについてａ＝ａ０Ｐ＋ａ１Ｐ＋ａ２Ｐを満たし、
前記第２入力値ｂが第２サブシェアｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐについてｂ＝ｂ０Ｐ＋ｂ１Ｐ＋ｂ２Ｐを満たし、
ａ’０Ｐ，ａ’１Ｐ，ｂ’０Ｐ，ｂ’１Ｐが、それぞれａ０Ｐ，ａ１Ｐ，ｂ０Ｐ，ｂ１Ｐに応じた値であり、
前記記憶部が、サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の真部分集合である割り当てシェア（ａ０Ｐ，ａ１Ｐ）、前記サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の真部分集合である第２割り当てシェア（ｂ０Ｐ，ｂ１Ｐ）、および前記第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納し、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、外部の第１秘密計算装置との間で第１任意値ｒＰを共有するためのやり取りを行う第１共有部と、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合に、外部の第２秘密計算装置との間で第２任意値ｒＰ−を共有するためのやり取りを行う第２共有部と、を有し、
前記出力部は、前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、前記提供値ｃＰ：＝ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐ＋ｒＰを出力し、
前記メタ情報Ａ，Ｂから前記取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合に前記入力部に前記取得値ｃＰ＋が入力され、
前記演算部は、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とする第１処理部と、
前記メタ情報Ａ，Ｂから前記取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする第２処理部と、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とする第３処理部と、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする第４処理部と、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られないか、またはａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ０Ｐ：＝ａ’０Ｐｂ’１Ｐ＋ｃ’Ｐ−ｒ’Ｐ−を得る第５処理部と、
前記メタ情報Ａ，Ｂからａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られないか、またはａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ１Ｐ：＝ａ’１Ｐｂ’１Ｐ＋ｃ’Ｐ＋−ｒ’Ｐを得る第６処理部と、を含む、秘密計算装置。
【請求項２】
請求項１の秘密計算装置であって、
前記演算部は、
前記メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にＣ０Ｐ：＝⊥とし、前記メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られる場合に前記メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値を得てＣ０Ｐとする第７処理部と、
前記メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にＣ１Ｐ：＝⊥とし、前記メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られる場合に前記メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値を得てＣ１Ｐとする第８処理部と、
前記メタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合にＣ２Ｐ：＝⊥とし、ａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られる場合に前記メタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値を得てＣ２Ｐとする第９処理部と、を含み、
Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐが前記秘密分散値のメタ情報であり、Ｃ０Ｐ：＝⊥の場合には前記秘密分散値がｃ０Ｐを含み、Ｃ１Ｐ：＝⊥の場合には前記秘密分散値がｃ１Ｐを含む、秘密計算装置。
【請求項３】
入力値の関数値である演算結果の秘密分散値を得る秘密計算装置であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を格納する記憶部と、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力部と、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力される入力部と、
前記取得値が前記入力部に入力される場合には、少なくとも前記取得値を用いて前記秘密分散値を得る演算部と、
を有し、
前記演算結果が前記入力値｛ａ（０），…，ａ（Ｎ−１）｝と第２入力値｛ｂ（０），…，ｂ（Ｎ−１）｝との演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）であり、Ｎ≧１であり、ｎ＝０，…，Ｎ−１であり、
ａ（ｎ）が前記サブシェアａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ）についてａ（ｎ）＝ａ０Ｐ（ｎ）＋ａ１Ｐ（ｎ）＋ａ２Ｐ（ｎ）を満たし、
ｂ（ｎ）が第２サブシェアｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ）についてｂ（ｎ）＝ｂ０Ｐ（ｎ）＋ｂ１Ｐ（ｎ）＋ｂ２Ｐ（ｎ）を満たし、
ａ’０Ｐ（ｎ），ａ’１Ｐ（ｎ），ｂ’０Ｐ（ｎ），ｂ’１Ｐ（ｎ）が、それぞれａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ）に応じた値であり、
前記記憶部が、サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の真部分集合である割り当てシェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ））、前記サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の真部分集合である第２割り当てシェア（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））、および前記第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納し、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、外部の第１秘密計算装置との間で第１任意値ｒＰを共有するためのやり取りを行う第１共有部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合に、外部の第２秘密計算装置との間で第２任意値ｒＰ−を共有するためのやり取りを行う第２共有部と、を有し、
前記出力部は、前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、前記提供値ｃＰ：＝Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝＋ｒＰを出力し、
前記メタ情報Ａ，Ｂから前記取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合に前記入力部に前記取得値ｃＰ＋が入力され、
前記演算部は、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とする第１処理部と、
前記メタ情報Ａ，Ｂから前記取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする第２処理部と、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とする第３処理部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする第４処理部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ０Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’０Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ−ｒ’Ｐ−を得る第５処理部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にｃ１Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’１Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ＋−ｒ’Ｐを得る第６処理部と、を含む、秘密計算装置。
【請求項４】
請求項３の秘密計算装置であって、
前記演算部は、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にＣ０Ｐ：＝⊥とし、前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られる場合に前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値を得てＣ０Ｐとする第７処理部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にＣ１Ｐ：＝⊥とし、前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られる場合に前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値を得てＣ１Ｐとする第８処理部と、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合にＣ２Ｐ：＝⊥とし、Σｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られる場合に前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値を得てＣ２Ｐとする第９処理部と、を含み、
Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐが前記秘密分散値のメタ情報であり、Ｃ０Ｐ：＝⊥の場合には前記秘密分散値がｃ０Ｐを含み、Ｃ１Ｐ：＝⊥の場合には前記秘密分散値がｃ１Ｐを含む、秘密計算装置。
【請求項５】
入力値の関数値である演算結果の秘密分散値を得る秘密計算装置であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を格納する記憶部と、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力部と、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力される入力部と、
前記取得値が前記入力部に入力される場合には、少なくとも前記取得値を用いて前記秘密分散値を得る演算部と、
を有し、
前記演算部は、
前記メタ情報から前記秘密分散値に応じた値が得られない場合に、前記秘密分散値が秘匿値であることを表す第２メタ情報⊥を出力し、
前記メタ情報から前記秘密分散値に応じた値が得られる場合に、前記メタ情報から前記秘密分散値に応じた値を計算し、計算した前記秘密分散値に応じた値を第３メタ情報として出力するものであり、
前記第２メタ情報⊥のみから前記秘密分散値を得ることはできない、秘密計算装置。
【請求項６】
入力値の関数値である演算結果の秘密分散値を得る秘密計算方法であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を記憶部に格納しておき、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、出力部が前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力ステップと、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力部に入力される入力ステップと、
前記取得値が前記入力部に入力される場合に、演算部が少なくとも前記取得値を用いて前記秘密分散値を得る演算ステップと、
を有し、
前記演算結果が前記入力値ａと第２入力値ｂとの乗算結果であり、
前記入力値ａが前記サブシェアａ０Ｐ，ａ１Ｐ，ａ２Ｐについてａ＝ａ０Ｐ＋ａ１Ｐ＋ａ２Ｐを満たし、
前記第２入力値ｂが第２サブシェアｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐについてｂ＝ｂ０Ｐ＋ｂ１Ｐ＋ｂ２Ｐを満たし、
ａ’０Ｐ，ａ’１Ｐ，ｂ’０Ｐ，ｂ’１Ｐが、それぞれａ０Ｐ，ａ１Ｐ，ｂ０Ｐ，ｂ１Ｐに応じた値であり、
前記記憶部が、サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の真部分集合である割り当てシェア（ａ０Ｐ，ａ１Ｐ）、前記サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の真部分集合である第２割り当てシェア（ｂ０Ｐ，ｂ１Ｐ）、および前記第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納し、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、第１共有部が、外部の第１秘密計算装置との間で第１任意値ｒＰを共有するためのやり取りを行う第１共有ステップと、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合に、第２共有部が、外部の第２秘密計算装置との間で第２任意値ｒＰ−を共有するためのやり取りを行う第２共有ステップと、を有し、
前記出力ステップは、前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、前記出力部が前記提供値ｃＰ：＝ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐ＋ｒＰを出力するステップであり、
前記入力ステップは、前記メタ情報Ａ，Ｂから前記取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合に前記入力部に前記取得値ｃＰ＋が入力されるステップであり、
前記演算部が行う前記演算ステップは、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とする第１処理ステップと、
前記メタ情報Ａ，Ｂから前記取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする第２処理ステップと、
前記メタ情報Ａ，Ｂから前記提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とする第３処理ステップと、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする第４処理ステップと、
前記メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られないか、またはａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ０Ｐ：＝ａ’０Ｐｂ’１Ｐ＋ｃ’Ｐ−ｒ’Ｐ−を得る第５処理ステップと、
前記メタ情報Ａ，Ｂからａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られないか、またはａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ１Ｐ：＝ａ’１Ｐｂ’１Ｐ＋ｃ’Ｐ＋−ｒ’Ｐを得る第６処理ステップと、を含む、秘密計算方法。
【請求項７】
入力値の関数値である演算結果の秘密分散値を得る秘密計算方法であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を記憶部に格納しておき、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、出力部が前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力ステップと、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力部に入力される入力ステップと、
前記取得値が前記入力部に入力される場合に、演算部が少なくとも前記取得値を用いて前記秘密分散値を得る演算ステップと、
を有し、
前記演算結果が前記入力値｛ａ（０），…，ａ（Ｎ−１）｝と第２入力値｛ｂ（０），…，ｂ（Ｎ−１）｝との演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）であり、Ｎ≧１であり、ｎ＝０，…，Ｎ−１であり、
ａ（ｎ）が前記サブシェアａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ）についてａ（ｎ）＝ａ０Ｐ（ｎ）＋ａ１Ｐ（ｎ）＋ａ２Ｐ（ｎ）を満たし、
ｂ（ｎ）が第２サブシェアｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ）についてｂ（ｎ）＝ｂ０Ｐ（ｎ）＋ｂ１Ｐ（ｎ）＋ｂ２Ｐ（ｎ）を満たし、
ａ’０Ｐ（ｎ），ａ’１Ｐ（ｎ），ｂ’０Ｐ（ｎ），ｂ’１Ｐ（ｎ）が、それぞれａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ）に応じた値であり、
前記記憶部が、サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の真部分集合である割り当てシェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ））、前記サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の真部分集合である第２割り当てシェア（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））、および前記第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納し、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、第１共有部が、外部の第１秘密計算装置との間で第１任意値ｒＰを共有するためのやり取りを行う第１共有ステップと、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合に、第２共有部が、外部の第２秘密計算装置との間で第２任意値ｒＰ−を共有するためのやり取りを行う第２共有ステップと、を有し、
前記出力ステップは、前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、前記出力部が前記提供値ｃＰ：＝Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝＋ｒＰを出力するステップであり、
前記入力ステップは、前記メタ情報Ａ，Ｂから前記取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合に前記入力部に前記取得値ｃＰ＋が入力されるステップであり、
前記演算部が行う前記演算ステップは、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とする第１処理ステップと、
前記メタ情報Ａ，Ｂから前記取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする第２処理ステップと、
前記メタ情報Ａ，Ｂから前記提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とする第３処理ステップと、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする第４処理ステップと、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ０Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’０Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ−ｒ’Ｐ−を得る第５処理ステップと、
前記メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にｃ１Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’１Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ＋−ｒ’Ｐを得る第６処理ステップと、を含む、秘密計算方法。
【請求項８】
入力値の関数値である演算結果の秘密分散値を得る秘密計算方法であって、
前記入力値が複数個のサブシェアの関数値であり、「αに応じた値」は、αまたはαの関数値であり、
前記複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、および前記サブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を記憶部に格納しておき、
前記メタ情報から前記割り当てシェアの部分集合の関数値である提供対応値に応じた値が得られない場合に、出力部が前記割り当てシェアの部分集合から得た前記提供対応値の関数値である提供値を出力する出力ステップと、
前記メタ情報から前記サブシェア集合の真部分集合である外部割り当てシェアの部分集合の関数値である取得対応値に応じた値が得られない場合に、前記取得対応値の関数値である取得値が入力部に入力される入力ステップと、
前記取得値が前記入力部に入力される場合に、演算部が少なくとも前記取得値を用いて前記秘密分散値を得る演算ステップと、
を有し、
前記演算ステップは、
前記メタ情報から前記秘密分散値に応じた値が得られない場合に、前記秘密分散値が秘匿値であることを表す第２メタ情報⊥を出力し、
前記メタ情報から前記秘密分散値に応じた値が得られる場合に、前記メタ情報から前記秘密分散値に応じた値を計算し、計算した前記秘密分散値に応じた値を表す第３メタ情報を出力するステップであり、
前記第２メタ情報⊥のみから、前記秘密分散値を得ることはできない、秘密計算方法。
【請求項９】
請求項１から５の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算の技術分野に関する。
【背景技術】
【０００２】
複製型秘密分散に基づいて秘密計算を行う技術が知られている（例えば、非特許文献１等参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】五十嵐大，千田浩司，濱田浩気，高橋克巳，“軽量検証可能３パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理，”ＩｎＳＣＩＳ２０１１，２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
複数の秘密計算装置間で値の受け渡しを行い、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密計算を行う方式がある。このような方式でも、各秘密計算装置が他の秘密計算装置から受け取る値の一部を予め取得できる場合がある。このような場合に、秘密計算装置間で全ての値を受け渡しするのでは効率が悪い。
【０００５】
本発明の課題は、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密計算を行う方式の効率を向上させることである。
【課題を解決するための手段】
【０００６】
秘密計算装置は、複数個のサブシェアの関数値である入力値に応じた演算結果の秘密分散値を得るために、複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、およびサブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を格納し、メタ情報から割り当てシェアの部分集合に応じた提供対応値に応じた値が得られない場合に、割り当てシェアの部分集合から得た提供対応値に応じた提供値を出力し、メタ情報からサブシェア集合の真部分集合である外部割り当てシェアの部分集合に応じた取得対応値に応じた値が得られない場合に、取得対応値に応じた取得値の入力を受け付け、取得値が入力される場合には、少なくとも取得値を用いて秘密分散値を得る。
【発明の効果】
【０００７】
これにより、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密計算を行う方式の効率を向上できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の秘密計算システムの機能構成を例示したブロック図である。
【図２】図２は実施形態の秘密計算装置の機能構成を例示したブロック図である。
【図３】図３は実施形態の秘密計算方法を例示するための概念図である。
【図４】図４は実施形態の秘密計算方法を例示するためのフロー図である。
【図５】図５は実施形態の秘密計算方法を例示するためのフロー図である。
【図６】図６は実施形態の秘密計算方法を例示するためのフロー図である。
【図７】図７は実施形態の秘密計算方法を例示するためのフロー図である。
【図８】図８は実施形態の秘密計算方法を例示するための概念図である。
【図９】図９は実施形態の秘密計算方法を例示するためのフロー図である。
【図１０】図１０は実施形態の秘密計算方法を例示するためのフロー図である。
【図１１】図１１は実施形態の秘密計算方法を例示するためのフロー図である。
【図１２】図１２は実施形態の秘密計算方法を例示するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［概要］
実施形態の秘密計算では、複数の秘密計算装置が「入力値」に応じた演算結果の秘密分散値を得る。ここで「入力値」は複製型秘密分散方式に則って秘密分散される。すなわち、「入力値」を複数個のサブシェアの関数値（例えば、加算値、加減算値など）とし、当該複数個のサブシェアを要素とする「サブシェア集合」の真部分集合をシェア（「入力値」の秘密分散値）として各秘密分散装置に割り当てる。ただし、一部のサブシェアに応じた値が各秘密分散装置にとって既知である場合がある。例えば、過去に行われた秘密計算によって一部のサブシェアに応じた値が既に取得されていた場合や、一部のサブシェアに応じた値が公開情報であった場合などである。なお「αに応じた値」は、αそのものであってもよいし、αの関数値であってもよい。このような状況に応じ、「サブシェア集合」の要素に応じた値を表すかまたは要素が秘匿値であることを表す「メタ情報」が設定される。「メタ情報」よって「要素に応じた値」が表された要素は当該「メタ情報」から特定可能である。「メタ情報」によって「秘匿値であること」が表された要素は当該「メタ情報」から特定できない。各秘密計算装置には、これらの「割り当てシェア」および「メタ情報」が格納される。秘密計算装置は、「メタ情報」から「割り当てシェア」の部分集合に応じた「提供対応値」に応じた値が得られない場合に、「割り当てシェア」の部分集合から得た「提供対応値」に応じた「提供値」を他の秘密計算装置に出力する。一方、「メタ情報」から当該「提供対応値」に応じた値が得られる場合、秘密計算装置は「提供値」を他の秘密計算装置に出力する必要はない。また「メタ情報」から「サブシェア集合」の真部分集合である「外部割り当てシェア」の部分集合に応じた「取得対応値」に応じた値が得られない場合、「取得対応値」に応じた「取得値」が秘密計算装置に入力される。なお、「外部割り当てシェア」とは、他の秘密計算装置に割り当てられているシェアを意味する。一方、「メタ情報」から当該「取得対応値」に応じた値が得られる場合、秘密計算装置に「取得値」が入力される必要はない。秘密計算装置は、「取得値」が入力される場合には、少なくとも「取得値」を用いて「入力値に応じた演算結果の秘密分散値」を得る。これにより、秘密計算装置間での値の受け渡し回数を削減し、効率を向上できる。
【００１０】
例えば、「入力値」および「第２入力値」に応じた演算結果の秘密分散値を得る場合には、以下のような処理となる。この場合、「入力値」と同様に「第２入力値」も複製型秘密分散方式に則って秘密分散される。すなわち、「第２入力値」を複数個の第２サブシェアの関数値とし、当該複数個の第２サブシェアを要素とする「第２サブシェア集合」の真部分集合を第２シェア（「第２入力値」の秘密分散値）として各秘密分散装置に割り当てる。ただし、一部の第２サブシェアに応じた値が各秘密計算装置にとって既知である場合がある。このような状況に応じ、「第２サブシェア集合」の要素に応じた値を表すかまたは要素が秘匿値であることを表す「第２メタ情報」が設定される。「第２メタ情報」によって「要素に応じた値」が表された要素は当該「第２メタ情報」から特定可能である。「第２タ情報」によって「秘匿値であること」が表された要素は当該「第２メタ情報」から特定できない。各秘密計算装置には、これらの「第２割り当てシェア」および「第２メタ情報」が格納される。秘密計算装置は、「メタ情報」と「第２メタ情報」とから「割り当てシェア」の部分集合と「第２割り当てシェア」の部分集合とに応じた「提供対応値」に応じた値が得られない場合に、「割り当てシェア」の部分集合と「第２割り当てシェア」の部分集合とから得た「提供対応値」に応じた「提供値」を他の秘密計算装置に出力する。「メタ情報」と「第２メタ情報」とから「サブシェア集合」の真部分集合である「外部割り当てシェア」の部分集合と「第２サブシェア集合」の真部分集合である「第２外部割り当てシェア」の部分集合とに応じた「取得対応値」に応じた値が得られない場合に「取得対応値」に応じた「取得値」が秘密計算装置に入力される。また、秘密計算装置は、「取得値」が入力される場合には、少なくとも「取得値」を用いて「入力値に応じた演算結果の秘密分散値」を得る。
【００１１】
上述の方式を乗算に適用する場合、「演算結果」は入力値ａと第２入力値ｂとの乗算結果ａｂであり、３個の秘密計算装置で乗算結果ａｂの秘密計算を行う。入力値ａはサブシェアａ０Ｐ，ａ１Ｐ，ａ２Ｐについてａ＝ａ０Ｐ＋ａ１Ｐ＋ａ２Ｐを満たし、第２入力値ｂは第２サブシェアｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐについてｂ＝ｂ０Ｐ＋ｂ１Ｐ＋ｂ２Ｐを満たす。秘密計算装置は、サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の真部分集合である割り当てシェア（ａ０Ｐ，ａ１Ｐ）、サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の真部分集合である第２割り当てシェア（ｂ０Ｐ，ｂ１Ｐ）、および第２サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納する。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、外部の秘密計算装置（第１秘密計算装置）との間で第１任意値ｒＰを共有するためのやり取りを行う。そうでない場合には、第１任意値ｒＰを共有するためのやり取りは不要である。秘密計算装置は、メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合に、外部の秘密計算装置（第２秘密計算装置）との間で第２任意値ｒＰ−を共有するためのやり取りを行う。そうでない場合には、第２任意値ｒＰ−を共有するためのやり取りは不要である。なお、下付き添え字の「Ｐ」は当該秘密計算装置に対応し、下付き添え字の「Ｐ＋」は第１秘密計算装置に対応し、下付き添え字の「Ｐ−」は第２秘密計算装置に対応する。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合に、提供値ｃＰ：＝ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐ＋ｒＰを出力し、メタ情報Ａ，Ｂから取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合に取得値ｃＰ＋の入力を受け付ける。ただし、ｃＰ＋：＝ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐ＋ｒＰ＋である。そうでない場合にはこれらのやり取りは不要である。「α：＝β」は、αがβであると定義すること（すなわちαをβの値とすること）を意味する。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とし、メタ情報Ａ，Ｂから取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする。また秘密計算装置は、メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とし、メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする。さらに秘密計算装置は、メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られないか、またはａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にｃ０Ｐ：＝ａ’０Ｐｂ’１Ｐ＋ｃ’Ｐ−ｒ’Ｐ−を得、メタ情報Ａ，Ｂからａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られないか、またはａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にｃ１Ｐ：＝ａ’１Ｐｂ’１Ｐ＋ｃ’Ｐ＋−ｒ’Ｐを得る。ここで、ａ’０Ｐ，ａ’１Ｐ，ｂ’０Ｐ，ｂ’１Ｐは、それぞれａ０Ｐ，ａ１Ｐ，ｂ０Ｐ，ｂ１Ｐに応じた値である。またｃ０Ｐおよびｃ１Ｐは乗算結果ａｂの秘密分散値である。ただし、メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐおよびａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られる場合、ｃ０Ｐがなくとも演算結果ａｂの復元が可能である。この場合にはｃ０Ｐの演算も省略可能である。また、メタ情報Ａ，Ｂからａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐおよびａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られる場合、ｃ１Ｐがなくとも演算結果ａｂの復元が可能である。この場合にはｃ１Ｐの演算も省略可能である。
【００１２】
より具体的には、秘密計算装置は、例えば、メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合にＣ０Ｐ：＝⊥とし、メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られる場合にメタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値を得てＣ０Ｐとする。また、秘密計算装置は、例えば、メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合にＣ１Ｐ：＝⊥とし、メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られる場合にメタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値を得てＣ１Ｐとする。さらに秘密計算装置は、例えば、メタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合にＣ２Ｐ：＝⊥とし、ａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られる場合にメタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値を得てＣ２Ｐとする。この場合、Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐは乗算結果ａｂの秘密分散値のメタ情報であり、Ｃ０Ｐ：＝⊥の場合には乗算結果ａｂの秘密分散値はｃ０Ｐを含み、Ｃ１Ｐ：＝⊥の場合には乗算結果ａｂの秘密分散値はｃ１Ｐを含む。以上のように、秘密計算装置間での値の受け渡し回数、および復元時の秘密分散値の受け渡し回数を削減し、効率を向上できる。さらにｃ０Ｐやｃ１Ｐの演算を省略する場合には、秘密計算装置での演算量も削減できる。
【００１３】
また例えば、メタ情報Ａがａ０Ｐに応じた値を表す場合、ａ’０Ｐはメタ情報Ａによって表される値であり、メタ情報Ａがａ１Ｐに応じた値を表す場合、ａ’１Ｐはメタ情報Ａによって表される値であり、メタ情報Ｂがｂ０Ｐに応じた値を表す場合、ｂ’０Ｐはメタ情報Ｂによって表される値であり、メタ情報Ｂがｂ１Ｐに応じた値を表す場合、ｂ’１Ｐはメタ情報Ｂによって表される値である。ここで、メタ情報Ａによって表されるａ０Ｐに応じた値のデータ量はａ０Ｐのデータ量よりも小さい（条件１−１）、および／または、メタ情報Ａによって表されるａ１Ｐに応じた値のデータ量はａ１Ｐのデータ量よりも小さい（条件１−２）、および／または、メタ情報Ｂによって表されるｂ０Ｐに応じた値のデータ量はｂ０Ｐのデータ量よりも小さい（条件１−３）、および／または、メタ情報Ｂによって表されるｂ１Ｐに応じた値のデータ量はｂ１Ｐのデータ量よりも小さい（条件１−４）という条件を満たす場合、シェアを用いる場合よりも演算量を削減できる。
【００１４】
前述の方式を積和演算に適用する場合、「演算結果」は入力値｛ａ（０），…，ａ（Ｎ−１）｝と第２入力値｛ｂ（０），…，ｂ（Ｎ−１）｝との演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）であり（ただし、ｎ∈｛０，…，Ｎ−１｝、Ｎ≧１）、３個の秘密計算装置で演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密計算を行う。ａ（ｎ）はサブシェアａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ）についてａ（ｎ）＝ａ０Ｐ（ｎ）＋ａ１Ｐ（ｎ）＋ａ２Ｐ（ｎ）を満たし、ｂ（ｎ）は第２サブシェアｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ）についてｂ（ｎ）＝ｂ０Ｐ（ｎ）＋ｂ１Ｐ（ｎ）＋ｂ２Ｐ（ｎ）を満たす。なお、「Σｎ∈｛０，…，Ｎ−１｝α（ｎ）」は「α（０）＋…＋α（Ｎ−１）」を表す。秘密計算装置は、サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の真部分集合である割り当てシェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ））、サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の真部分集合である第２割り当てシェア（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））、および第２サブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表す第２メタ情報Ｂを格納する。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、外部の秘密計算装置（第１秘密計算装置）との間で第１任意値ｒＰを共有するためのやり取りを行う。そうでない場合には、第１任意値ｒＰを共有するためのやり取りは不要である。秘密計算装置は、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合に、外部の秘密計算装置（第２秘密計算装置）との間で第２任意値ｒＰ−を共有するためのやり取りを行う。そうでない場合には、第２任意値ｒＰ−を共有するためのやり取りは不要である。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合に、提供値ｃＰ：＝Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝＋ｒＰを出力し、メタ情報Ａ，Ｂから取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合に取得値ｃＰ＋の入力を受け付ける。ただし、ｃＰ＋：＝Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐ｝＋ｒＰ＋である。そうでない場合にはこれらのやり取りは不要である。秘密計算装置は、メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ’Ｐ：＝ｃＰとし、ｃ’Ｐ：＝ｃＰとしない場合にｃ’Ｐ：＝０とし、メタ情報Ａ，Ｂから取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない��合にｃ’Ｐ＋：＝ｃＰ＋とし、ｃ’Ｐ＋：＝ｃＰ＋としない場合にｃ’Ｐ＋：＝０とする。また秘密計算装置は、メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ：＝ｒＰとし、ｒ’Ｐ：＝ｒＰとしない場合にｒ’Ｐ：＝０とし、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合にｒ’Ｐ−：＝ｒＰ−とし、ｒ’Ｐ−：＝ｒＰ−としない場合にｒ’Ｐ−：＝０とする。さらに秘密計算装置は、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にｃ０Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’０Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ−ｒ’Ｐ−を得る。秘密計算装置は、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にｃ１Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’１Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ＋−ｒ’Ｐを得る。ここで、ａ’０Ｐ（ｎ），ａ’１Ｐ（ｎ），ｂ’０Ｐ（ｎ），ｂ’１Ｐ（ｎ）は、それぞれａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ）に応じた値である。またｃ０Ｐおよびｃ１Ｐは乗算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値である。ただし、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝およびΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られる場合、ｃ０Ｐがなくとも演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の復元が可能である。この場合にはｃ０Ｐの演算も省略可能である。また、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝およびΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られる場合、ｃ１Ｐがなくとも演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の復元が可能である。この場合にはｃ１Ｐ演算も省略可能である。
【００１５】
より具体的には、秘密計算装置は、例えば、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合にＣ０Ｐ：＝⊥とする。秘密計算装置は、例えば、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られる場合に、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値を得てＣ０Ｐとする。秘密計算装置は、例えば、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合にＣ１Ｐ：＝⊥とする。秘密計算装置は、例えば、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られる場合に、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値を得てＣ１Ｐとする。秘密計算装置は、例えば、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合にＣ２Ｐ：＝⊥とする。秘密計算装置は、例えば、Σｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られる場合に、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値を得てＣ２Ｐとする。Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐは演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値のメタ情報であり、Ｃ０Ｐ：＝⊥の場合には演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値がｃ０Ｐを含み、Ｃ１Ｐ：＝⊥の場合には演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値がｃ１Ｐを含む。以上のように、秘密計算装置間での値の受け渡し回数、および復元時の秘密分散値の受け渡し量を削減し、効率を向上できる。さらにｃ０Ｐやｃ１Ｐの演算を省略する場合には、秘密計算装置での演算量も削減できる。
【００１６】
また例えば、メタ情報Ａがａ０Ｐ（ｎ）に応じた値を表す場合、ａ’０Ｐ（ｎ）はメタ情報Ａによって表される値であり、メタ情報Ａがａ１Ｐ（ｎ）に応じた値を表す場合、ａ’１Ｐ（ｎ）はメタ情報Ａによって表される値であり、メタ情報Ｂがｂ０Ｐ（ｎ）に応じた値を表す場合、ｂ’０Ｐ（ｎ）はメタ情報Ｂによって表される値であり、メタ情報Ｂがｂ１Ｐ（ｎ）に応じた値を表す場合、ｂ’１Ｐ（ｎ）はメタ情報Ｂによって表される値である。ここで、メタ情報Ａによって表されるａ０Ｐ（ｎ）に応じた値のデータ量は、ａ０Ｐ（ｎ）のデータ量よりも小さい（条件２−１）、および／または、メタ情報Ａによって表されるａ１Ｐ（ｎ）に応じた値のデータ量はａ１Ｐ（ｎ）のデータ量よりも小さい（条件２−２）、および／または、メタ情報Ｂによって表されるｂ０Ｐ（ｎ）に応じた値のデータ量はｂ０Ｐ（ｎ）のデータ量よりも小さい（条件２−３）、および／または、メタ情報Ｂによって表されるｂ１Ｐ（ｎ）に応じた値のデータ量はｂ１Ｐ（ｎ）のデータ量よりも小さい（条件２−４）という条件を満たす場合、シェアを用いる場合よりも演算量を削減できる。
【００１７】
［第１実施形態］
第１実施形態では、上述の方式を乗算に適用した例を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム１は、３個の秘密計算装置１１−０，１１−１，１１−２を有し、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の秘密計算装置１１−Ｐ（ただし、Ｐ＝０，１，２）は、記憶部１１１−Ｐ、演算部１１２−Ｐ、制御部１１３−Ｐ、共有部１１４−Ｐ、および通信部１１５−Ｐを有する。演算部１１２−Ｐは、処理部１１２０−Ｐ〜１１２Ａ−Ｐを有する。秘密計算装置１１−Ｐは、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の秘密計算装置１１−ｍを構成する電子回路が複数のＣＰＵを含んでいてもよい。なお、秘密計算装置１１−Ｐで実行される各処理は制御部１１３−Ｐの制御下で実行され、各処理で得られた情報は一時メモリ（図示せず）に格納される。一時メモリに格納された情報は、必要に応じて読み出されて使用される。
【００１８】
＜処理の前提＞
本形態では、入力値ａと入力値ｂとの乗算ａｂの秘密計算を行う。入力値ａはａ＝ａ１＋ａ２＋ａ３を満たす３個のサブシェアａ１，ａ２，ａ３に分割され、入力値ｂはｂ＝ｂ１＋ｂ２＋ｂ３を満たす３個のサブシェアｂ１，ｂ２，ｂ３に分割されている。すなわち、入力値ａはサブシェアａ１，ａ２，ａ３の関数値であり、入力値ｂはサブシェアｂ１，ｂ２，ｂ３の関数値である。各秘密計算装置１１−Ｐ（ただし、Ｐ＝０，１，２）には、３個のサブシェアａ０Ｐ，ａ１Ｐ，ａ２Ｐを要素とするサブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の真部分集合であるシェア（ａ０Ｐ，ａ１Ｐ）（割り当てシェア）が割り当てられる。ただし、ａ０Ｐ＝ａ１（Ｐ−１ ｍｏｄ３）かつａ１Ｐ＝ａ０（Ｐ＋１ ｍｏｄ３）である。サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の他の真部分集合（ａ０Ｐ，ａ２Ｐ）および（ａ１Ｐ，ａ２Ｐ）を「外部割り当てシェア」と呼ぶ。また、各秘密計算装置１１−Ｐ（ただし、Ｐ＝０，１，２）には３個のサブシェアｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐを要素とするサブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の真部分集合であるシェア（ｂ０Ｐ，ｂ１Ｐ）（割り当てシェア）が割り当てられる。ただし、ｂ０Ｐ＝ｂ１（Ｐ−１ ｍｏｄ３）かつｂ１Ｐ＝ｂ０（Ｐ＋１ ｍｏｄ３）である。サブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の他の真部分集合（ｂ０Ｐ，ｂ２Ｐ）および（ｂ１Ｐ，ｂ２Ｐ）を「外部割り当てシェア」と呼ぶ。すなわち、秘密計算装置１１−０にはシェア（ａ００，ａ１０）＝（ａ２，ａ０）および（ｂ００，ｂ１０）＝（ｂ２，ｂ０）が割り当てられ、秘密計算装置１１−１にはシェア（ａ０１，ａ１１）＝（ａ０，ａ１）および（ｂ０１，ｂ１１）＝（ｂ０，ｂ１）が割り当てられ、秘密計算装置１１−２にはシェア（ａ０２，ａ１２）＝（ａ１，ａ２），（ｂ０２，ｂ１２）＝（ｂ１，ｂ２）が割り当てられる。秘密計算装置１１−Ｐにとって自らに割り当てられていないシェアは「外部割り当てシェア」である。各秘密計算装置１１−Ｐ（図２）の記憶部１１１−Ｐには、シェア（ａ０Ｐ，ａ１Ｐ）および（ｂ０Ｐ，ｂ１Ｐ）（割り当てシェア）が格納される（図３）。これらのサブシェアは明らかにａ＝ａ０Ｐ＋ａ１Ｐ＋ａ２Ｐおよびｂ＝ｂ０Ｐ＋ｂ１Ｐ＋ｂ２Ｐの関係を満たす。
【００１９】
サブシェア集合（ａ０Ｐ，ａ１Ｐ，ａ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、およびサブシェア集合（ｂ０Ｐ，ｂ１Ｐ，ｂ２Ｐ）の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ｂが設定される。「要素ａＪＰに応じた値を表すメタ情報Ａ」は、要素ａＪＰ（ただし、Ｊ＝０，１，２）そのものを表す値ＡＪＰ（すなわち、ＡＪＰ：＝ａＪＰ）を表してもよいし、要素ａＪＰを一意に定める関数ｆについてａＪＰ＝ｆ（ＡＪＰ）を満たす値ＡＪＰを表してもよい。前者の場合、ＡＪＰは入力値ａが取り得る値を要素とする集合Ｒの元であり、後者の場合、関数ｆによる値域が集合Ｒに属することになる定義域Ｒ’の元である。関数ｆは、例えば準同型性関数である。定義域Ｒ’の元のデータ量が集合Ｒの元のデータ量よりも小さくてもよい。「要素ａＪＰが秘匿値であることを表すメタ情報Ａ」は、要素ａＪＰ（ただし、Ｊ＝０，１，２）が秘匿値であることを表す値ＡＪＰ＝⊥を表す。ＡＪＰ＝⊥である場合、メタ情報Ａのみから要素ａＪＰの値を得ることはできない。このような値Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐを表す情報であれば、どのような情報をメタ情報Ａとしてもよい。例えば、値Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐを要素とする集合（Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐ）をメタ情報Ａとしてもよいし、集合（Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐ）を表す１個の値をメタ情報Ａとしてもよいし、集合（Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐ）の複数の要素からなる部分集合を表す値の集合をメタ情報Ａとしてもよい。以上の点はメタ情報Ｂについても同様であり、値Ｂ０Ｐ，Ｂ１Ｐ，Ｂ２Ｐを表す情報であれば、どのような情報をメタ情報Ｂとしてもよい。ただし、ＢＪＰ：＝ｂＪＰまたはｂＪＰ＝ｆ（ＢＪＰ）またはＢＪＰ：＝⊥である。Ａ０Ｐ，Ａ１Ｐ，Ａ２Ｐ，Ｂ０Ｐ，Ｂ１Ｐ，Ｂ２Ｐの少なくとも一つが「⊥」ではない場合に秘密計算装置１１−Ｐ間での値の受け渡し回数を削減できる。メタ情報ＡおよびＢは、すべての秘密計算装置１１−Ｐ（ただし、Ｐ＝０，１，２）の記憶部１１１−Ｐに格納される。
【００２０】
＜秘密計算処理＞
次に図３〜図７を用い、本形態の秘密計算の処理内容を説明する。秘密計算装置１１−Ｐ（ただし、Ｐ＝０，１，２）は、それぞれ以下の処理を実行する。
【００２１】
秘密計算装置１１−Ｐの共有部１１４−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う。ただし、ｘＪＫ：＝［ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥］∈｛Ｔ，Ｆ｝（ただし、（Ｊ，Ｋ）＝（０，１），（１，２），（２，０））であり、［ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥］は「ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥である」という命題が真（Ｔ）であるか、偽（Ｆ）であるか、を表す真偽値を表す。「ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥である」とは、メタ情報Ａ，ＢからａＪＰｂＫＰ＋ａＫＰｂＪＰに応じた値が得られないことを意味する。メタ情報Ａ，ＢからａＪＰｂＫＰに応じた値が得られないか（ＡＪＰＢＫＰ＝⊥）、または、メタ情報Ａ，ＢからａＫＰｂＪＰに応じた値が得られない場合（ＡＫＰＢＪＰ＝⊥）、メタ情報Ａ，ＢからａＪＰｂＫＰ＋ａＫＰｂＪＰに応じた値は得られない（ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥）。言い換えると、ＡＪＰＢＫＰ＋ＡＫＰＢＪＰ＝⊥は、（ＡＪＰＢＫＰ＝⊥）∨（ＡＫＰＢＪＰ＝⊥）であることを意味する。例えば、（１）ＡＪＰ，ＢＫＰ∈ＲまたはＡＪＰ，ＢＫＰ∈Ｒ’である場合ＡＪＰＢＫＰ≠⊥であり、ＡＫＰ，ＢＪＰ∈ＲまたはＡＫＰ，ＢＪＰ∈Ｒ’である場合ＡＫＰＢＪＰ≠⊥である。（２）ＡＪＰ＝０である場合、ＢＫＰにかかわらずＡＪＰＢＫＰ＝０であってＡＪＰＢＫＰ≠⊥である。ＢＫＰ＝０である場合、ＡＪＰにかかわらずＡＪＰＢＫＰ＝０であってＡＪＰＢＫＰ≠⊥である。ＡＫＰ＝０である場合、ＢＪＰにかかわらずＡＫＰＢＪＰ＝０であってＡＫＰＢＪＰ≠⊥である。ＢＪＰ＝０である場合、ＡＫＰにかかわらずＡＫＰＢＪＰ＝０であってＡＫＰＢＪＰ≠⊥である。（３）ＡＪＰ≠０かつＢＫＰ＝⊥の場合、または、ＡＪＰ＝⊥≠０かつＢＫＰ≠０の場合、ＡＪＰＢＫＰ＝⊥である。ＡＫＰ≠０かつＢＪＰ＝⊥の場合、または、ＡＫＰ＝⊥≠０かつＢＪＰ≠０の場合、ＡＫＰＢＪＰ＝⊥である（ステップＳ１０１）。
【００２２】
ｘ０１が真（ｘ０１＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合）、共有部１１４−Ｐは外部の秘密計算装置１１−（Ｐ＋１  ｍｏｄ３）との間で任意値ｒＰを共有するためのやり取りを行う。任意値ｒＰは、乱数であってもよいし、擬似乱数であってもよいし、定数であってもよい。例えば、共有部１１４−Ｐは、生成または選択した任意値ｒＰを記憶部１１１−Ｐに格納するとともに通信部１１５−Ｐに送り、通信部１１５−Ｐは任意値ｒＰを秘密計算装置１１−（Ｐ＋１  ｍｏｄ３）に送信する。任意値ｒＰは秘密計算装置１１−（Ｐ＋１  ｍｏｄ３）の通信部１１５−（Ｐ＋１  ｍｏｄ３）に入力され、記憶部１１１−（Ｐ＋１  ｍｏｄ３）に格納される（ステップＳ１０２）。その後ステップＳ１０３に進む。一方、ｘ０１が偽（ｘ０１＝Ｆ）である場合、ステップＳ１０２を実行することなく、ステップＳ１０３に進む。
【００２３】
ステップＳ１０３では、共有部１１４−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ２０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１０３）。ｘ２０が真（ｘ２０＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合）、共有部１１４−Ｐは外部の秘密計算装置１１−（Ｐ−１  ｍｏｄ３）との間で任意値ｒＰ−：＝ｒ（Ｐ−１ｍｏｄ３）を共有するためのやり取りを行う。任意値ｒＰ−は、乱数であってもよいし、擬似乱数であってもよいし、定数であってもよい。例えば、秘密計算装置１１−（Ｐ−１  ｍｏｄ３）の共有部１１４−（Ｐ−１  ｍｏｄ３）が、生成または選択した任意値ｒＰ−を記憶部１１１−（Ｐ−１  ｍｏｄ３）に格納するとともに通信部１１５−（Ｐ−１  ｍｏｄ３）に送り、通信部１１５−（Ｐ−１  ｍｏｄ３）は任意値ｒＰ−を秘密計算装置１１−Ｐに送信する。任意値ｒＰ−は共有部１１４−Ｐに入力され、共有部１１４−Ｐは任意値ｒＰ−を記憶部１１１−Ｐに格納する（ステップＳ１０４）。その後ステップＳ１０５に進む。一方、ｘ２０が偽（ｘ２０＝Ｆ）である場合、ステップＳ１０４を実行することなく、ステップＳ１０５に進む。
【００２４】
ステップＳ１０５では、演算部１１２−Ｐの処理部１１２０−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１０５）。ｘ０１が真（ｘ０１＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合）、処理部１１２０−Ｐは、記憶部１１１−Ｐからシェア（ａ０Ｐ，ａ１Ｐ），（ｂ０Ｐ，ｂ１Ｐ）および任意値ｒＰを読み込み、提供値ｃＰ：＝ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐ＋ｒＰを得て出力する（ステップＳ１０６）。提供値ｃＰは、通信部１１５−Ｐから外部の秘密計算装置１１−（Ｐ−１  ｍｏｄ３）に送信される。提供値ｃＰは秘密計算装置１１−（Ｐ−１  ｍｏｄ３）の通信部１１５−（Ｐ−１  ｍｏｄ３）に入力され、記憶部１１１−（Ｐ−１  ｍｏｄ３）に格納される（ステップＳ１０７）。その後ステップＳ１１０に進む。一方、ｘ０１が偽（ｘ０１＝Ｆ）である場合、ステップＳ１０６，Ｓ１０７を実行することなく、ステップＳ１１０に進む。
【００２５】
ステップＳ１１０では、演算部１１２−Ｐの処理部１１２７−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，ＢからＣ０Ｐ：＝Ａ０ＰＢ０Ｐ＋Ａ０ＰＢ１Ｐ＋Ａ１ＰＢ０Ｐを得て、Ｃ０Ｐを出力する（ステップＳ１１０）。ここで、メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合（Ａ０ＰＢ０Ｐ＋Ａ０ＰＢ１Ｐ＋Ａ１ＰＢ０Ｐ＝⊥の場合）にはＣ０Ｐ：＝⊥となる。なお、Ａ０ＰＢ０Ｐ＝⊥またはＡ０ＰＢ１Ｐ＝⊥またはＡ１ＰＢ０Ｐ＝⊥の場合にＡ０ＰＢ０Ｐ＋Ａ０ＰＢ１Ｐ＋Ａ１ＰＢ０Ｐ＝⊥となる。一方、メタ情報Ａ，Ｂからａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られる場合、Ｃ０Ｐはａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値となる。
【００２６】
次に、演算部１１２−Ｐの処理部１１２８−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，ＢからＣ１Ｐ：＝Ａ１ＰＢ１Ｐ＋Ａ１ＰＢ２Ｐ＋Ａ２ＰＢ１Ｐを得て、Ｃ１Ｐを出力する（ステップＳ１１３）。ここで、メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合（Ａ１ＰＢ１Ｐ＋Ａ１ＰＢ２Ｐ＋Ａ２ＰＢ１Ｐ＝⊥の場合）にはＣ１Ｐ：＝⊥となる。一方、メタ情報Ａ，Ｂからａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られる場合、Ｃ１Ｐはａ１Ｐｂ１Ｐ＋ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値となる。
【００２７】
次に、演算部１１２−Ｐの処理部１１２８−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，ＢからＣ２Ｐ：＝Ａ２ＰＢ２Ｐ＋Ａ２ＰＢ０Ｐ＋Ａ０ＰＢ２Ｐを得て、Ｃ２Ｐを出力する（ステップＳ１１６）。ここで、メタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合（Ａ２ＰＢ２Ｐ＋Ａ２ＰＢ０Ｐ＋Ａ０ＰＢ２Ｐ＝⊥）にはＣ２Ｐ：＝⊥となる。一方、メタ情報Ａ，Ｂからａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られる場合、Ｃ２Ｐはａ２Ｐｂ２Ｐ＋ａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値となる。
【００２８】
次に、演算部１１２−Ｐの処理部１１２Ａ−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａに対応するＡ０Ｐが真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１１７）。処理部１１２Ａ−Ｐは、Ａ０Ｐが真（Ａ０Ｐ＝Ｔ）である場合にａ’０Ｐ：＝ａ０Ｐとし（ステップＳ１１８）、Ａ０Ｐが偽（Ａ０Ｐ＝Ｆ）である場合にａ’０Ｐ：＝Ａ０Ｐとする（ステップＳ１１９）。すなわち、メタ情報Ａがａ０Ｐに応じた値を表す場合、ａ’０Ｐはメタ情報Ａによって表される値となる。
【００２９】
また、処理部１１２Ａ−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ａに対応するＡ１Ｐが真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１２０）。処理部１１２Ａ−Ｐは、Ａ１Ｐが真（Ａ１Ｐ＝Ｔ）である場合にａ’１Ｐ：＝ａ１Ｐとし（ステップＳ１２１）、Ａ１Ｐが偽（Ａ１Ｐ＝Ｆ）である場合にａ’１Ｐ：＝Ａ１Ｐとし、ａ’１Ｐを出力する（ステップＳ１２２）。すなわち、メタ情報Ａがａ１Ｐに応じた値を表す場合、ａ’１Ｐはメタ情報Ａによって表される値となる。
【００３０】
また、処理部１１２Ａ−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ｂに対応するＢ０Ｐが真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１２３）。処理部１１２Ａ−Ｐは、Ｂ０Ｐが真（Ｂ０Ｐ＝Ｔ）である場合にｂ’０Ｐ：＝ｂ０Ｐとし（ステップＳ１２４）、Ｂ０Ｐが偽（Ｂ０Ｐ＝Ｆ）である場合にｂ’０Ｐ：＝Ｂ０Ｐとし、ｂ’０Ｐを出力する（ステップＳ１２５）。すなわち、メタ情報Ｂがｂ０Ｐに応じた値を表す場合、ｂ’０Ｐはメタ情報Ｂによって表される値となる。
【００３１】
次に、処理部１１２Ｂ−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ｂに対応するＢ１Ｐが真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１２６）。処理部１１２Ｂ−Ｐは、Ｂ１Ｐが真（Ｂ１Ｐ＝Ｔ）である場合にｂ’１Ｐ：＝ｂ１Ｐとし（ステップＳ１２７）、Ｂ１Ｐが偽（Ｂ１Ｐ＝Ｆ）である場合にｂ’１Ｐ：＝Ｂ１Ｐとし、ｂ’１Ｐを出力する（ステップＳ１２８）。すなわち、メタ情報Ｂがｂ１Ｐに応じた値を表す場合、ｂ’１Ｐはメタ情報Ｂによって表される値となる。
【００３２】
演算部１１２−Ｐの処理部１１２１−Ｐが、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ１０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１２９）。処理部１１２１−Ｐは、ｘ１０が真（ｘ１０＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合）にｃ’Ｐ：＝ｃＰとし（ステップＳ１３０）、そうでない場合（ｃ’Ｐ：＝ｃＰとしない場合）にｃ’Ｐ：＝０とし（ステップＳ１３１）、ｃ’Ｐを出力する。
【００３３】
演算部１１２−Ｐの処理部１１２２−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ１２が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１３２）。ｘ１２が真（Ｔ）である場合（メタ情報Ａ，Ｂから取得対応値ａ１Ｐｂ２Ｐ＋ａ２Ｐｂ１Ｐに応じた値が得られない場合）、前述のステップＳ１０７で秘密計算装置１１−（Ｐ＋１  ｍｏｄ３）から取得値ｃＰ＋：＝ｃ（Ｐ＋１  ｍｏｄ３）が送信されている。この取得値ｃＰ＋は処理部１１２２−Ｐに入力される（ステップＳ１３３）。処理部１１２２−Ｐはｃ’Ｐ＋：＝ｃＰ＋として出力する（ステップＳ１３４）。一方、ｘ１２が偽（Ｆ）である場合（ｃ’Ｐ＋：＝ｃＰ＋としない場合）、処理部１１２２−Ｐはｃ’Ｐ＋：＝０として出力する（ステップＳ１３５）。
【００３４】
演算部１１２−Ｐの処理部１１２３−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１３６）。処理部１１２２−Ｐは、ｘ０１が真（Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合）にｒ’Ｐ：＝ｒＰとし（ステップＳ１３７）、そうでない場合（ｒ’Ｐ：＝ｒＰとしない場合）にｒ’Ｐ：＝０とし（ステップＳ１３８）、ｒ’Ｐを出力する。
【００３５】
演算部１１２−Ｐの処理部１１２４−Ｐは、記憶部１１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ２０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ１３９）。処理部１１２４−Ｐは、ｘ２０が真（Ｔ）である場合（メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られない場合）にｒ’Ｐ−：＝ｒＰ−とし（ステップＳ１４０）、そうでない場合（ｒ’Ｐ−：＝ｒＰ−としない場合）にｒ’Ｐ−：＝０とし（ステップＳ１４１）、ｒ’Ｐ−を出力する。
【００３６】
演算部１１２−Ｐの処理部１１２５−Ｐは、Ｃ０Ｐ＝⊥であるか否かに応じた処理を行う（ステップＳ１４２）。Ｃ０Ｐ＝⊥であれば、処理部１１２５−Ｐがｃ０Ｐ：＝ａ’０Ｐｂ’１Ｐ＋ｃ’Ｐ−ｒ’Ｐ−を得（ステップＳ１４３）、演算部１１２−Ｐがｃ０Ｐを出力し（ステップＳ１４４）、ステップＳ１４５に進む。なお、Ｃ０Ｐ＝⊥となるのは、メタ情報Ａ，Ｂからａ２Ｐｂ０Ｐ＋ａ０Ｐｂ２Ｐに応じた値が得られないか、またはａ０Ｐｂ０Ｐ＋ａ０Ｐｂ１Ｐ＋ａ１Ｐｂ０Ｐに応じた値が得られない場合である。一方、Ｃ０Ｐ＝⊥でなければ、ステップＳ１４３およびＳ１４４を実行することなく、ステップＳ１４５に進む。
【００３７】
ステップＳ１４５では、演算部１１２−Ｐの処理部１１２６−ＰがＣ１Ｐ＝⊥であるか否かに応じた処理を行う（ステップＳ１４５）。Ｃ１Ｐ＝⊥であれば、処理部１１２６−Ｐがｃ１Ｐ：＝ａ’１Ｐｂ’１Ｐ＋ｃ’Ｐ＋−ｒ’Ｐを得（ステップＳ１４６）、演算部１１２−Ｐがｃ１Ｐを出力する（ステップＳ１４７）。一方、Ｃ１Ｐ＝⊥でなければ、ステップＳ１４６およびＳ１４７を実行することなく、ステップＳ１４８に進む。
【００３８】
ステップＳ１４８では、演算部１１２−ＰがＣ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐを出力する。ここで、Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐは演算結果ａｂの秘密分散値のメタ情報である。ｃ０Ｐおよびｃ１Ｐは演算結果ａｂの秘密分散値である。ただし、ｃ０ＰはＣ０Ｐ：＝⊥の場合にのみに出力されればよく、ｃ１ＰはＣ１Ｐ：＝⊥の場合にのみに出力されればよい。
【００３９】
＜本形態の特徴＞
本形態では、メタ情報Ａ，Ｂが表す値に応じ、秘密計算装置１１−Ｐ間での値の送受信回数を削減できる。また、送受信を行う必要がなくなった値の演算を省略できる場合には、演算量も削減できる。さらに、メタ情報を用いた演算量がシェアを用いた演算量よりも小さい場合にも演算量を削減できる。
【００４０】
［第２実施形態］
第２実施形態では、上述の方式を積和演算に適用した例を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム２は、３個の秘密計算装置２１−０，２１−１，２１−２を有し、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の秘密計算装置２１−Ｐ（ただし、Ｐ＝０，１，２）は、記憶部２１１−Ｐ、演算部２１２−Ｐ、制御部２１３−Ｐ、共有部２１４−Ｐ、および通信部２１５−Ｐを有する。演算部２１２−Ｐは、処理部２１２０−Ｐ〜２１２Ａ−Ｐを有する。秘密計算装置２１−Ｐは、例えば、前述のコンピュータが所定のプログラムを実行することで構成される。なお、秘密計算装置２１−Ｐで実行される各処理は制御部２１３−Ｐの制御下で実行され、各処理で得られた情報は一時メモリ（図示せず）に格納される。一時メモリに格納された情報は、必要に応じて読み出されて使用される。
【００４１】
＜処理の前提＞
本形態では、入力値｛ａ（０），…，ａ（Ｎ−１）｝と入力値｛ｂ（０），…，ｂ（Ｎ−１）｝との積和演算Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密計算を行う。Ｎ≧１であるがＮ＝１の場合には第１実施形態と同じ処理となる。本形態が実質的に意味をなすのはＮ≧２の場合である。各ａ（ｎ）（ただし、ｎ＝０，…，Ｎ−１）はａ（ｎ）＝ａ１（ｎ）＋ａ２（ｎ）＋ａ３（ｎ）を満たす３個のサブシェアａ１（ｎ），ａ２（ｎ），ａ３（ｎ）に分割され、ｂ（ｎ）はｂ（ｎ）＝ｂ１（ｎ）＋ｂ２（ｎ）＋ｂ３（ｎ）を満たす３個のサブシェアｂ１（ｎ），ｂ２（ｎ），ｂ３（ｎ）に分割されている。すなわち、ａ（ｎ）はサブシェアａ１（ｎ），ａ２（ｎ），ａ３（ｎ）の関数値であり、ｂ（ｎ）はサブシェアｂ１（ｎ），ｂ２（ｎ），ｂ３（ｎ）の関数値である。各秘密計算装置２１−Ｐ（ただし、Ｐ＝０，１，２）には、３個のサブシェアａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ）を要素とするサブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の真部分集合であるシェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ））（割り当てシェア）が割り当てられる。ただし、ａ０Ｐ（ｎ）＝ａ１（ｎ）（Ｐ−１ ｍｏｄ３）かつａ１Ｐ（ｎ）＝ａ０（ｎ）（Ｐ＋１ ｍｏｄ３）である。また、各秘密計算装置２１−Ｐ（ただし、Ｐ＝０，１，２）には３個のサブシェアｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ）を要素とするサブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の真部分集合であるシェア（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））（割り当てシェア）が割り当てられる。ただし、ｂ０Ｐ（ｎ）＝ｂ１（ｎ）（Ｐ−１ ｍｏｄ３）かつｂ１Ｐ（ｎ）＝ｂ０（ｎ）（Ｐ＋１ ｍｏｄ３）である。すなわち、秘密計算装置２１−０にはシェア（ａ００（ｎ），ａ１０（ｎ））＝（ａ２（ｎ），ａ０（ｎ））および（ｂ００（ｎ），ｂ１０（ｎ））＝（ｂ２（ｎ），ｂ０（ｎ））が割り当てられ、秘密計算装置２１−１にはシェア（ａ０１（ｎ），ａ１１（ｎ））＝（ａ０（ｎ），ａ１（ｎ））および（ｂ０１（ｎ），ｂ１１（ｎ））＝（ｂ０（ｎ），ｂ１（ｎ））が割り当てられ、秘密計算装置２１−２にはシェア（ａ０２（ｎ），ａ１２（ｎ））＝（ａ１（ｎ），ａ２（ｎ）），（ｂ０２（ｎ），ｂ１２（ｎ））＝（ｂ１（ｎ），ｂ２（ｎ））が割り当てられる。秘密計算装置２１−Ｐにとって自らに割り当てられていないシェアは「外部割り当てシェア」である。各秘密計算装置２１−Ｐ（図２）の記憶部２１１−Ｐには、シェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ））および（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））（割り当てシェア）が格納される（図８）。これらのサブシェアは明らかにａ（ｎ）＝ａ０Ｐ（ｎ）＋ａ１Ｐ（ｎ）＋ａ２Ｐ（ｎ）およびｂ（ｎ）＝ｂ０Ｐ（ｎ）＋ｂ１Ｐ（ｎ）＋ｂ２Ｐ（ｎ）の関係を満たす。
【００４２】
サブシェア集合（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ），ａ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ａ、およびサブシェア集合（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ），ｂ２Ｐ（ｎ））の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報Ｂが設定される。「要素ａＪＰ（ｎ）に応じた値を表すメタ情報Ａ」は、要素ａＪＰ（ｎ）（ただし、Ｊ＝０，１，２）そのものを表す値ＡＪＰ（ｎ）（すなわち、ＡＪＰ（ｎ）：＝ａＪＰ（ｎ））を表してもよいし、要素ａＪＰ（ｎ）を一意に定める関数ｆについてａＪＰ（ｎ）＝ｆ（ＡＪＰ（ｎ））を満たす値ＡＪＰ（ｎ）を表してもよい。関数ｆは、例えば準同型性関数である。前者の場合、ＡＪＰ（ｎ）は入力値ａ（ｎ）が取り得る値を要素とする集合Ｒの元であり、後者の場合、関数ｆによる値域が集合Ｒに属することになる定義域Ｒ’の元である。「要素ａＪＰ（ｎ）が秘匿値であることを表すメタ情報Ａ」は、要素ａＪＰ（ｎ）（ただし、Ｊ＝０，１，２）が秘匿値であることを表す値ＡＪＰ（ｎ）＝⊥を表す。ＡＪＰ（ｎ）＝⊥である場合、メタ情報Ａのみから要素ａＪＰ（ｎ）の値を得ることはできない。このような値Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ）を表す情報であれば、どのような情報をメタ情報Ａとしてもよい。例えば、値Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ）を要素とする集合（Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ））（ただし、ｎ＝０，…Ｎ−１）をメタ情報Ａとしてもよいし、集合（Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ））を表す１個の値をメタ情報Ａとしてもよいし、集合（Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ））の複数の要素からなる部分集合を表す値の集合をメタ情報Ａとしてもよい。以上の点はメタ情報Ｂについても同様であり、値Ｂ０Ｐ（ｎ），Ｂ１Ｐ（ｎ），Ｂ２Ｐ（ｎ）を表す情報であれば、どのような情報をメタ情報Ｂとしてもよい。ただし、ＢＪＰ（ｎ）：＝ｂＪＰ（ｎ）またはｂＪＰ（ｎ）＝ｆ（ＢＪＰ（ｎ））またはＢＪＰ（ｎ）：＝⊥である。本形態では、Ａ０Ｐ（ｎ），Ａ１Ｐ（ｎ），Ａ２Ｐ（ｎ），Ｂ０Ｐ（ｎ），Ｂ１Ｐ（ｎ），Ｂ２Ｐ（ｎ）の少なくとも一つが「⊥」でないときに、秘密計算装置２１−Ｐ間での値の受け渡し回数を削減できる。メタ情報ＡおよびＢは、すべての秘密計算装置２１−Ｐ（ただし、Ｐ＝０，１，２）の記憶部２１１−Ｐに格納される。
【００４３】
＜秘密計算処理＞
次に図８〜図１２を用い、本形態の秘密計算の処理内容を説明する。秘密計算装置２１−Ｐ（ただし、Ｐ＝０，１，２）は、それぞれ以下の処理を実行する。
【００４４】
秘密計算装置２１−Ｐの共有部２１４−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う。ただし、ｘＪＫ：＝［Σｎ∈｛０，…，Ｎ−１｝｛ＡＪＰ（ｎ）ＢＫＰ（ｎ）＋ＡＫＰ（ｎ）ＢＪＰ（ｎ）｝＝⊥］∈｛Ｔ，Ｆ｝（ただし、（Ｊ，Ｋ）＝（０，１），（１，２），（２，０）、ｎ＝０，…，Ｎ−１）である。［Σｎ∈｛０，…，Ｎ−１｝｛ＡＪＰ（ｎ）ＢＫＰ（ｎ）＋ＡＫＰ（ｎ）ＢＪＰ（ｎ）｝＝⊥］は「Σｎ∈｛０，…，Ｎ−１｝｛ＡＪＰ（ｎ）ＢＫＰ（ｎ）＋ＡＫＰ（ｎ）ＢＪＰ（ｎ）｝＝⊥である」という命題が真（Ｔ）であるか、偽（Ｆ）であるか、を表す真偽値を表す。「Σｎ∈｛０，…，Ｎ−１｝｛ＡＪＰ（ｎ）ＢＫＰ（ｎ）＋ＡＫＰ（ｎ）ＢＪＰ（ｎ）｝＝⊥である」とは、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａＪＰ（ｎ）ｂＫＰ（ｎ）＋ａＫＰ（ｎ）ｂＪＰ（ｎ）｝に応じた値が得られないことを意味する（ステップＳ２０１）。
【００４５】
ｘ０１が真（ｘ０１＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合）、共有部２１４−Ｐは外部の秘密計算装置２１−（Ｐ＋１  ｍｏｄ３）との間で任意値ｒＰを共有するためのやり取りを行う。例えば、共有部２１４−Ｐは、生成または選択した任意値ｒＰを記憶部２１１−Ｐに格納するとともに通信部２１５−Ｐに送り、通信部２１５−Ｐは任意値ｒＰを秘密計算装置２１−（Ｐ＋１  ｍｏｄ３）に送信する。任意値ｒＰは秘密計算装置２１−（Ｐ＋１  ｍｏｄ３）の通信部２１５−（Ｐ＋１  ｍｏｄ３）に入力され、記憶部２１１−（Ｐ＋１  ｍｏｄ３）に格納される（ステップＳ２０２）。その後ステップＳ２０３に進む。一方、ｘ０１が偽（ｘ０１＝Ｆ）である場合、ステップＳ２０２を実行することなく、ステップＳ２０３に進む。
【００４６】
ステップＳ２０３では、共有部２１４−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ２０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２０３）。ｘ２０が真（ｘ２０＝Ｔ）である場合（メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合）、共有部２１４−Ｐは外部の秘密計算装置２１−（Ｐ−１  ｍｏｄ３）との間で任意値ｒＰ−：＝ｒ（Ｐ−１ｍｏｄ３）を共有するためのやり取りを行う。任意値ｒＰ−は、乱数であってもよいし、擬似乱数であってもよいし、定数であってもよい。例えば、秘密計算装置２１−（Ｐ−１  ｍｏｄ３）の共有部２１４−（Ｐ−１  ｍｏｄ３）が、生成または選択した任意値ｒＰ−を記憶部２１１−（Ｐ−１  ｍｏｄ３）に格納するとともに通信部２１５−（Ｐ−１  ｍｏｄ３）に送り、通信部２１５−（Ｐ−１  ｍｏｄ３）は任意値ｒＰ−を秘密計算装置２１−Ｐに送信する。任意値ｒＰ−は共有部２１４−Ｐに入力され、共有部２１４−Ｐは任意値ｒＰ−を記憶部２１１−Ｐに格納する（ステップＳ２０４）。その後ステップＳ２０５に進む。一方、ｘ２０が偽（ｘ２０＝Ｆ）である場合、ステップＳ２０４を実行することなく、ステップＳ２０５に進む。
【００４７】
ステップＳ２０５では、演算部２１２−Ｐの処理部２１２０−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２０５）。ｘ０１が真（ｘ０１＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合）、処理部２１２０−Ｐは、記憶部２１１−Ｐからシェア（ａ０Ｐ（ｎ），ａ１Ｐ（ｎ）），（ｂ０Ｐ（ｎ），ｂ１Ｐ（ｎ））および任意値ｒＰを読み込み、提供値ｃＰ：＝Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝＋ｒＰを得て出力する（ステップＳ２０６）。提供値ｃＰは、通信部２１５−Ｐから外部の秘密計算装置２１−（Ｐ−１  ｍｏｄ３）に送信される。提供値ｃＰは秘密計算装置２１−（Ｐ−１  ｍｏｄ３）の通信部２１５−（Ｐ−１  ｍｏｄ３）に入力され、記憶部２１１−（Ｐ−１  ｍｏｄ３）に格納される（ステップＳ２０７）。その後ステップＳ２１０に進む。一方、ｘ０１が偽（ｘ０１＝Ｆ）である場合、ステップＳ２０６，Ｓ２０７を実行することなく、ステップＳ２１０に進む。
【００４８】
ステップＳ２１０では、演算部２１２−Ｐの処理部２１２７−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，ＢからＣ０Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝｛Ａ０Ｐ（ｎ）Ｂ０Ｐ（ｎ）＋Ａ０Ｐ（ｎ）Ｂ１Ｐ（ｎ）＋Ａ１Ｐ（ｎ）Ｂ０Ｐ（ｎ）｝を得て、Ｃ０Ｐを出力する（ステップＳ２１０）。ここで、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合（Σｎ∈｛０，…，Ｎ−１｝｛Ａ０Ｐ（ｎ）Ｂ０Ｐ（ｎ）＋Ａ０Ｐ（ｎ）Ｂ１Ｐ（ｎ）＋Ａ１Ｐ（ｎ）Ｂ０Ｐ（ｎ）｝＝⊥の場合）にはＣ０Ｐ：＝⊥となる。一方、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られる場合、Ｃ０Ｐは、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値となる。
【００４９】
次に、演算部２１２−Ｐの処理部２１２８−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，ＢからＣ１Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝｛Ａ１Ｐ（ｎ）Ｂ１Ｐ（ｎ）＋Ａ１Ｐ（ｎ）Ｂ２Ｐ（ｎ）＋Ａ２Ｐ（ｎ）Ｂ１Ｐ（ｎ）｝を得て、Ｃ１Ｐを出力する（ステップＳ２１３）。ここで、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合（Σｎ∈｛０，…，Ｎ−１｝｛Ａ１Ｐ（ｎ）Ｂ１Ｐ（ｎ）＋Ａ１Ｐ（ｎ）Ｂ２Ｐ（ｎ）＋Ａ２Ｐ（ｎ）Ｂ１Ｐ（ｎ）｝＝⊥）にはＣ１Ｐ：＝⊥となる。一方、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られる場合、Ｃ１ＰはΣｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値となる。
【００５０】
次に、演算部２１２−Ｐの処理部２１２８−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，ＢからＣ２Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝｛Ａ２Ｐ（ｎ）Ｂ２Ｐ（ｎ）＋Ａ２Ｐ（ｎ）Ｂ０Ｐ（ｎ）＋Ａ０Ｐ（ｎ）Ｂ２Ｐ（ｎ）｝を得て、Ｃ２Ｐを出力する（ステップＳ２１６）。ここで、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合（Σｎ∈｛０，…，Ｎ−１｝｛Ａ２Ｐ（ｎ）Ｂ２Ｐ（ｎ）＋Ａ２Ｐ（ｎ）Ｂ０Ｐ（ｎ）＋Ａ０Ｐ（ｎ）Ｂ２Ｐ（ｎ）｝＝⊥）にはＣ２Ｐ：＝⊥となる。一方、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られる場合、Ｃ２ＰはΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値となる。
【００５１】
制御部２１３−Ｐは、ｎ：＝０に初期化する（ステップＳ２１５１）。次に、演算部２１２−Ｐの処理部２１２Ａ−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａに対応するＡ０Ｐ（ｎ）が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２１７）。処理部２１２Ａ−Ｐは、Ａ０Ｐ（ｎ）が真（Ａ０Ｐ（ｎ）＝Ｔ）である場合にａ’０Ｐ（ｎ）：＝ａ０Ｐ（ｎ）とし（ステップＳ２１８）、Ａ０Ｐ（ｎ）が偽（Ａ０Ｐ（ｎ）＝Ｆ）である場合にａ’０Ｐ（ｎ）：＝Ａ０Ｐ（ｎ）とする（ステップＳ２１９）。すなわち、メタ情報Ａがａ０Ｐ（ｎ）に応じた値を表す場合、ａ’０Ｐ（ｎ）はメタ情報Ａによって表される値となる。
【００５２】
また、処理部２１２Ａ−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ａに対応するＡ１Ｐ（ｎ）が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２２０）。処理部２１２Ａ−Ｐは、Ａ１Ｐ（ｎ）真（Ａ１Ｐ（ｎ）＝Ｔ）である場合にａ’１Ｐ（ｎ）：＝ａ１Ｐ（ｎ）とし（ステップＳ２２１）、Ａ１Ｐ（ｎ）が偽（Ａ１Ｐ（ｎ）＝Ｆ）である場合にａ’１Ｐ（ｎ）：＝Ａ１Ｐ（ｎ）とし、ａ’１Ｐ（ｎ）を出力する（ステップＳ２２２）。すなわち、メタ情報Ａがａ１Ｐ（ｎ）に応じた値を表す場合、ａ’１Ｐ（ｎ）はメタ情報Ａによって表される値となる。
【００５３】
また、処理部２１２Ａ−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ｂに対応するＢ０Ｐ（ｎ）が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２２３）。処理部２１２Ａ−Ｐは、Ｂ０Ｐ（ｎ）が真（Ｂ０Ｐ（ｎ）＝Ｔ）である場合にｂ’０Ｐ（ｎ）：＝ｂ０Ｐ（ｎ）とし（ステップＳ２２４）、Ｂ０Ｐ（ｎ）が偽（Ｂ０Ｐ（ｎ）＝Ｆ）である場合にｂ’０Ｐ（ｎ）：＝Ｂ０Ｐ（ｎ）とし、ｂ’０Ｐ（ｎ）を出力する（ステップＳ２２５）。すなわち、メタ情報Ｂがｂ０Ｐ（ｎ）に応じた値を表す場合、ｂ’０Ｐ（ｎ）はメタ情報Ｂによって表される値となる。
【００５４】
次に、処理部２１２Ｂ−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ｂに対応するＢ１Ｐ（ｎ）が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２２６）。処理部２１２Ｂ−Ｐは、Ｂ１Ｐ（ｎ）が真（Ｂ１Ｐ（ｎ）＝Ｔ）である場合にｂ’１Ｐ（ｎ）：＝ｂ１Ｐ（ｎ）とし（ステップＳ２２７）、Ｂ１Ｐ（ｎ）が偽（Ｂ１Ｐ（ｎ）＝Ｆ）である場合にｂ’１Ｐ（ｎ）：＝Ｂ１Ｐ（ｎ）とし、ｂ’１Ｐ（ｎ）を出力する（ステップＳ２２８）。すなわち、メタ情報Ｂがｂ１Ｐ（ｎ）に応じた値を表す場合、ｂ’１Ｐ（ｎ）はメタ情報Ｂによって表される値となる。
【００５５】
制御部２１３−Ｐはｎ＝Ｎ−１であるかを判定する（ステップＳ２１５２）。ここで、ｎ＝Ｎ−１でなければ、ｎ：＝ｎ＋１とし（ステップＳ２１５３）、ステップＳ２１７に戻る。ｎ＝Ｎ−１であれば、演算部２１２−Ｐの処理部２１２１−Ｐが、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ１０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２２９）。処理部２１２１−Ｐは、ｘ１０が真（ｘ１０＝Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合）にｃ’Ｐ：＝ｃＰとし（ステップＳ２３０）、そうでない場合（ｃ’Ｐ：＝ｃＰとしない場合）にｃ’Ｐ：＝０とし（ステップＳ２３１）、ｃ’Ｐを出力する。
【００５６】
演算部２１２−Ｐの処理部２１２２−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ１２が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２３２）。ｘ１２が真（Ｔ）である場合（メタ情報Ａ，Ｂから取得対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ１Ｐ（ｎ）ｂ２Ｐ（ｎ）＋ａ２Ｐ（ｎ）ｂ１Ｐ（ｎ）｝に応じた値が得られない場合）、前述のステップＳ２０７で秘密計算装置２１−（Ｐ＋１  ｍｏｄ３）から取得値ｃＰ＋：＝ｃ（Ｐ＋１  ｍｏｄ３）が送信されている。この取得値ｃＰ＋は処理部２１２２−Ｐに入力される（ステップＳ２３３）。処理部２１２２−Ｐはｃ’Ｐ＋：＝ｃＰ＋として出力する（ステップＳ２３４）。一方、ｘ１２が偽（Ｆ）である場合（ｃ’Ｐ＋：＝ｃＰ＋としない場合）、処理部２１２２−Ｐはｃ’Ｐ＋：＝０として出力する（ステップＳ２３５）。
【００５７】
演算部２１２−Ｐの処理部２１２３−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ０１が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２３６）。処理部２１２２−Ｐは、ｘ０１が真（Ｔ）である場合（メタ情報Ａ，Ｂから提供対応値Σｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合）にｒ’Ｐ：＝ｒＰとし（ステップＳ２３７）、そうでない場合（ｒ’Ｐ：＝ｒＰとしない場合）にｒ’Ｐ：＝０とし（ステップＳ２３８）、ｒ’Ｐを出力する。
【００５８】
演算部２１２−Ｐの処理部２１２４−Ｐは、記憶部２１１−Ｐに格納されたメタ情報Ａ，Ｂに対応するｘ２０が真（Ｔ）であるか偽（Ｆ）であるかに否かに応じた処理を行う（ステップＳ２３９）。処理部２１２４−Ｐは、ｘ２０が真（Ｔ）である場合（メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られない場合）にｒ’Ｐ−：＝ｒＰ−とし（ステップＳ２４０）、そうでない場合（ｒ’Ｐ−：＝ｒＰ−としない場合）にｒ’Ｐ−：＝０とし（ステップＳ２４１）、ｒ’Ｐ−を出力する。
【００５９】
演算部２１２−Ｐの処理部２１２５−Ｐは、Ｃ０Ｐ＝⊥であるか否かに応じた処理を行う（ステップＳ２４２）。Ｃ０Ｐ＝⊥であれば、処理部２１２５−Ｐがｃ０Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’０Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ−ｒ’Ｐ−を得（ステップＳ２４３）、演算部２１２−Ｐがｃ０Ｐを出力し（ステップＳ２４４）、ステップＳ２４５に進む。なお、Ｃ０Ｐ＝⊥となるのは、メタ情報Ａ，ＢからΣｎ∈｛０，…，Ｎ−１｝｛ａ２Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ２Ｐ（ｎ）｝に応じた値が得られないか、またはΣｎ∈｛０，…，Ｎ−１｝｛ａ０Ｐ（ｎ）ｂ０Ｐ（ｎ）＋ａ０Ｐ（ｎ）ｂ１Ｐ（ｎ）＋ａ１Ｐ（ｎ）ｂ０Ｐ（ｎ）｝に応じた値が得られない場合である。一方、Ｃ０Ｐ＝⊥でなければ、ステップＳ２４３およびＳ２４４を実行することなく、ステップＳ２４５に進む。
【００６０】
ステップＳ２４５では、演算部２１２−Ｐの処理部２１２６−ＰがＣ１Ｐ＝⊥であるか否かに応じた処理を行う（ステップＳ２４５）。Ｃ１Ｐ＝⊥であれば、処理部２１２６−Ｐがｃ１Ｐ：＝Σｎ∈｛０，…，Ｎ−１｝ａ’１Ｐ（ｎ）ｂ’１Ｐ（ｎ）＋ｃ’Ｐ＋−ｒ’Ｐを得（ステップＳ２４６）、演算部２１２−Ｐがｃ１Ｐを出力する（ステップＳ２４７）。一方、Ｃ１Ｐ＝⊥でなければ、ステップＳ２４６およびＳ２４７を実行することなく、ステップＳ２４８に進む。
【００６１】
ステップＳ２４８では、演算部２１２−ＰがＣ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐを出力する。ここで、Ｃ０Ｐ，Ｃ１Ｐ，Ｃ２Ｐは演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値のメタ情報である。ｃ０Ｐおよびｃ１Ｐは演算結果Σｎ∈｛０，…，Ｎ−１｝ａ（ｎ）ｂ（ｎ）の秘密分散値である。ただし、ｃ０ＰはＣ０Ｐ：＝⊥の場合にのみに出力されればよく、ｃ１ＰはＣ１Ｐ：＝⊥の場合にのみに出力されればよい。
【００６２】
＜本形態の特徴＞
本形態では、メタ情報Ａ，Ｂが表す値に応じ、秘密計算装置２１−Ｐ間での値の送受信回数を削減できる。また、送受信を行う必要がなくなった値の演算を省略できる場合には、演算量も削減できる。さらに、メタ情報を用いた演算量がシェアを用いた演算量よりも小さい場合にも演算量を削減できる。
【００６３】
［変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の実施形態では、秘密計算で乗算または積和演算を行う場合を例示した。しかしながら、複数の秘密計算装置間で値の受け渡しを行い、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密計算を行う方式であれば、どのような方式に本発明を適用してもよい。また、上述した各演算は有限体上の演算であってもよいし、拡大体上の演算であってもよいし、環上の演算であってもよいし、その他の代数系上での演算であってもよい。
【００６４】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、秘密計算装置がネットワーク経由で値の受け渡しを行うのではなく、可搬型記憶媒体を介して値の受け渡しが行われてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００６８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６９】
１１−０〜１１−２，２１−０〜２１−２  秘密計算装置
１，２  秘密計算システム
【要約】
【課題】複数の秘密計算装置間で値の受け渡しを行い、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密計算を行う方式の効率を向上させる。
【解決手段】複数個のサブシェアを要素とするサブシェア集合の真部分集合である割り当てシェア、およびサブシェア集合の要素に応じた値を表すかまたは要素が秘匿値であることを表すメタ情報を格納し、メタ情報から割り当てシェアの部分集合に応じた提供対応値に応じた値が得られない場合に、割り当てシェアの部分集合から得た提供対応値に応じた提供値を出力し、メタ情報からサブシェア集合の真部分集合である外部割り当てシェアの部分集合に応じた取得対応値に応じた値が得られない場合に、取得対応値に応じた取得値の入力を受け付け、取得値が入力される場合には、少なくとも取得値を用いて秘密分散値を得る。
【選択図】図２【図１】
0006006842.tif 000002
【図２】
0006006842.tif 000003
【図３】
0006006842.tif 000004
【図４】
0006006842.tif 000005
【図５】
0006006842.tif 000006
【図６】
0006006842.tif 000007
【図７】
0006006842.tif 000008
【図８】
0006006842.tif 000009
【図９】
0006006842.tif 000010
【図１０】
0006006842.tif 000011
【図１１】
0006006842.tif 000012
【図１２】
0006006842.tif 000013