(57)【要約】  ｈ＝２，…，Ｍについて、第１集合に含まれる複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または第２集合の秘匿文を得る。ただし、複製元の要素ａ（ｆ（ｈ））よりも順序が前であって複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））である。また、第２集合または第２集合の秘匿文を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合または第３集合の秘匿文を得る。
2015107780.tif 000002
【特許請求の範囲】
【請求項１】
第１集合が、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）を含む集合であり、前記複数個の要素ａ（１），…，ａ（Ｎ）からなる集合が複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含み、複製元の要素ａ（ｆ（ｈ））よりも順序が前であって前記複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））であり、ｈ＝２，…，Ｍについて、前記第１集合に含まれる前記複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、前記第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または前記第２集合の秘匿文を得る第１演算部と、
前記第２集合の１番目の要素がａ５（１）であり、前記第２集合のｉ＝２，…，Ｎ番目の要素がａ５（ｉ）であり、前記第２集合または前記第２集合の秘匿文を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合または前記第３集合の秘匿文を得る第２演算部と、
を有する要素複製装置。
【請求項２】
請求項１の要素複製装置であって、
前記複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む集合である第５集合または前記第５集合の秘匿文から、事前に前記要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））を含む集合である第４集合または前記第４集合の秘匿文が得られており、かつ、前記第１演算部が、前記第４集合または前記第４集合の秘匿文を用い、前記第２集合または前記第２集合の秘匿文を得るか、または、
前記第１演算部が、前記第１集合または前記第１集合の秘匿文を用い、前記第２集合または前記第２集合の秘匿文を得る、要素複製装置。
【請求項３】
請求項１または２の要素複製装置であって、
前記要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされた前記複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む第６集合に含まれる前記複製元の要素ａ（ｆ（ｈ））をａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にした集合である第４集合または前記第４集合の秘匿文が事前に得られており、
前記第１演算部は、前記第４集合または前記第４集合の秘匿文を用い、前記第２集合または前記第２集合の秘匿文を得る、要素複製装置。
【請求項４】
請求項１または２の要素複製装置であって、
前記第１演算部は、
前記第１集合または前記第１集合の秘匿文を用い、複製元であるか否かをソート条件として前記第１集合に含まれる前記要素ａ（１），…，ａ（Ｎ）の安定ソートを行って得られる、前記要素ａ（１），…，ａ（Ｎ）を含み、かつ、前記要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））の順序が連続した集合である第７集合または前記第７集合の秘匿文を得、
前記第７集合または前記第７集合の秘匿文を用い、ｈ＝２，…，Ｍについて、前記第７集合に含まれる要素ａ１（１），ａ１（２），…，ａ１（Ｎ）を要素ａ２（１）＝ａ１（１），ａ２（２）＝ａ１（２）−ａ１（１），…，ａ２（Ｎ）＝ａ１（Ｎ）−ａ１（Ｎ−１）にした集合である第８集合または前記第８集合の秘匿文を得、
前記第８集合または前記第８集合の秘匿文を用い、前記第８集合の要素をソートして複製元以外の要素を零にして得られる集合である前記第２集合、または前記第２集合の秘匿文を得る、要素複製装置。
【請求項５】
請求項４の要素複製装置であって、
前記第１演算部は、
前記第１集合の秘匿文を用い、秘密計算によって前記第７集合の秘匿文を得、
前記要素ａ（１），…，ａ（Ｎ）の安定ソートに応じて前記要素ａ（１），…，ａ（Ｎ）それぞれの順序を表す要素ｐ（ａ（１）），…，ｐ（ａ（Ｎ））をソートして得られる要素を含む集合である第９集合の秘匿文を得、
前記第７集合の秘匿文を用い、秘密計算によって前記第８集合の秘匿文を得、
前記第８集合の秘匿文および前記第９集合の秘匿文を用い、秘密計算によって、前記第８集合の要素と前記第９集合の要素との対応関係を維持しつつ、前記第８集合の要素の順序および前記第９集合の要素の順序をランダム置換して得られる、前記第８集合の要素の順序が並び替えられた集合である第１０集合および前記第９集合の要素の順序が並び替えられた集合である第１１集合にそれぞれ対応する、第１０集合の秘匿文および第１１集合の秘匿文を得、
前記第１１集合の秘匿文の復元結果および前記第１０集合の秘匿文を用い、前記第１０集合の要素をソートして複製元以外の要素を零にして得られる集合である前記第２集合の秘匿文を得る、要素複製装置。
【請求項６】
請求項１の要素複製装置であって、
前記第１演算部は、秘密計算によって前記第２集合の秘匿文を得、
前記第２演算部は、前記第２集合の秘匿文を用い、秘密計算によって前記第３集合の秘匿文を得る、要素複製装置。
【請求項７】
第１集合が、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）を含む集合であり、前記複数個の要素ａ（１），…，ａ（Ｎ）からなる集合が複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含み、複製元の要素ａ（ｆ（ｈ））よりも順序が前であって前記複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））であり、第１演算部で、ｈ＝２，…，Ｍについて、前記第１集合に含まれる前記複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、前記第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または前記第２集合の秘匿文を得る第１ステップと、
前記第２集合の１番目の要素がａ５（１）であり、前記第２集合のｉ＝２，…，Ｎ番目の要素がａ５（ｉ）であり、第２演算部で、前記第２集合または前記第２集合の秘匿文を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合または前記第３集合の秘匿文を得る第２ステップと、
を有する要素複製方法。
【請求項８】
請求項１の要素複製装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集合に含まれた要素を効率よく複製する技術に関する。
【背景技術】
【０００２】
秘匿化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１等参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという秘匿化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算，定数和，乗算，定数倍，論理演算（否定，論理積，論理和，排他的論理和），データ形式変換（整数，二進数）等の演算結果を３つの秘密計算装置に分散された状態、すなわち秘匿化されたまま保持させることができる。【０００３】
表に従ってそれらの要素を秘密計算上で写像する方法として、非特許文献２の方法がある。非特許文献２の方法では、秘匿化された表の要素（値）を同一の列内に複製する写像が秘密計算上で実現されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考,” In CSS, 2010.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司, “秘匿計算上の一括写像アルゴリズム,” 電子情報通信学会論文誌, A, 基礎・境界, Vol. 96, No. 4, pp. 157-165, apr 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、要素の複製が行われる列の大きさをＮとすると、要素を同一の列内に複製するためにＯ（Ｎ）回，Ｏ（ｌｏｇ  Ｎ）段の乗算を要していた。このことは、秘匿化された表の要素を同一の列内に秘密計算上で複製する場合だけではなく、順序付けされたＮ個の要素を含む集合の要素を同一の集合内の要素として複製する場合であれば同様である。【０００６】
本発明の課題は、順序付けされた要素を含む集合の要素を複製する場合の演算コストを低減することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、ｈ＝２，…，Ｍについて、第１集合に含まれる複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または第２集合の秘匿文を得、第２集合または第２集合の秘匿文を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合または第３集合の秘匿文を得る。【０００８】
ただし、第１集合は、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）を含む集合である。複数個の要素ａ（１），…，ａ（Ｎ）からなる集合が複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む。複製元の要素ａ（ｆ（ｈ））よりも順序が前であって複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））である。第２集合の１番目の要素がａ５（１）であり、第２集合のｉ＝２，…，Ｎ番目の要素がａ５（ｉ）である。
【発明の効果】
【０００９】
本発明では、演算量が小さな加法演算で集合の要素を複製することができるため、順序付けされた要素を含む集合の要素を複製する場合の演算コストを低減させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の秘密計算システムの構成を例示するためのブロック図である。
【図２】図２Ａは、第１実施形態およびその変形例の要素複製装置の構成を例示するためのブロック図である。図２Ｂは、第１実施形態およびその変形例の事前計算の処理を例示するためのフロー図である。図２Ｃは、第１実施形態およびその変形例の要素複製の処理を例示するためのフロー図である。
【図３】図３Ａは、第２実施形態およびその変形例の要素複製装置の構成を例示するためのブロック図である。図３Ｂは、第２実施形態のソート部の構成を例示するためのブロック図である。
【図４】図４Ａは、第２実施形態およびその変形例の要素複製の処理を例示するためのフロー図である。図４Ｂは、図４ＡのステップＳ２１４およびＳ２１４’の処理を例示するためのフロー図である。図４Ｃは、図４ＢのステップＳ２１４３の処理を例示するためのフロー図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を説明する。
［概要］
まず、各実施形態の概要を説明する。
各実施形態では、ｈ＝２，…，Ｍについて、第１集合に含まれる複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または第２集合の秘匿文を得、第２集合または第２集合の秘匿文を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合または第３集合の秘匿文を得る。
【００１２】
ここで、第３集合は、或る順序に従って、第１集合に含まれる「複製元の要素」を、その要素よりも順序が後であって次の複製元の要素よりも前までのすべての「複製元ではない要素」に複製し、「最後の複製元の要素」を、それよりも後のすべての「複製元ではない要素」に複製したものとなる。第１集合に含まれる複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、複製元以外の要素を零にして得られる第２集合またはその秘匿文を計算しておくことで、累積的な加法演算によって上述の第３集合またはその秘匿文を計算できる。加法演算の演算量は、従来技術で用いられる乗算等の乗法演算に比べて非常に小さい。そのため、順序付けされた要素を含む集合の要素を複製する場合の演算コストを従来よりも低減させることができる。
【００１３】
なお、「第１集合」とは、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）（ただし、Ｎは２以上の整数であり、例えば３以上の整数）を含む集合を意味する。第１集合は、Ｎ個の要素ａ（１），…，ａ（Ｎ）からなるＮ次元ベクトルであってもよいし、Ｎ＋Λ次元ベクトル（ただし、Λは１以上の整数）に含まれるＮ個の要素ａ（１），…，ａ（Ｎ）からなる集合であってもよいし、Ｎ個以上の要素を持つ行列に含まれるＮ個の要素ａ（１），…，ａ（Ｎ）からなる集合であってもよいし、それら以外の集合であってもよい。複数個の要素ａ（１），…，ａ（Ｎ）の間には順序が定められている（すなわち、複数個の要素ａ（１），…，ａ（Ｎ）は順序付けされている）。この順序は予め定められたものであってもよいし、処理を行うたびに定められるものであってもよい。この順序の定め方には限定はなく、異なる要素に異なる順序が対応するのであれば、どのような順序が定められてもよい。例えば、第１集合が第１，…，Ｎ要素をそれぞれａ（１），…，ａ（Ｎ）とするＮ次元のベクトル（ａ（１），…，ａ（Ｎ））である場合、要素ａ（ｎ）にｎ番目（ただし、ｎ∈｛１，…，Ｎ｝）の順序が対応してもよいし、要素ａ（ｎ）にＮ−ｎ＋１番目の順序が対応してもよい。
【００１４】
これらの複数個の要素ａ（１），…，ａ（Ｎ）からなる集合｛ａ（１），…，ａ（Ｎ）｝は、複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む（ただし、２≦Ｍ≦Ｎ、例えばＭ＜Ｎ）。「複製元の要素」とは、複製元となる要素、すなわち複製される要素を意味する。各要素ａ（ｎ）（ただし、ｎ∈｛１，…，Ｎ｝）は、複製元の要素ａ（ｆ（ｍ））（ただし、ｍ∈｛１，…，Ｍ｝）であるか、または、複製元ではない要素である。言い換えると、｛ａ（ｆ（１）），…，ａ（ｆ（Ｍ））｝⊆｛ａ（１），…，ａ（Ｎ）｝であり、例えば、｛ａ（ｆ（１）），…，ａ（ｆ（Ｍ））｝⊂｛ａ（１），…，ａ（Ｎ）｝である。複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））は、要素ａ（１），…，ａ（Ｎ）の順序関係を維持する。すなわち、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））には、要素ａ（１），…，ａ（Ｎ）の順序に従った順序が対応する。例えば、Ｎ＝１０，Ｍ＝４であり、要素ａ（１），…，ａ（１０）の順序がそれぞれ第１，…，１０番目であり、複製元の要素がａ（１），ａ（４），ａ（５），ａ（９）である場合、集合｛ａ（１），ａ（４），ａ（５），ａ（９）｝内での複製元の要素ａ（１），ａ（４），ａ（５），ａ（９）の順序はそれぞれ第１，２，３，４番目となる。また、複製元の要素ａ（ｆ（ｈ））（ただし、ｈ∈｛２，…，Ｍ｝）よりも順序が前であって複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素をａ（ｆ（ｈ−１））と表現する。言い換えると、複製元の要素のみからなる集合内における順序が、複製元の要素ａ（ｆ（ｈ））の直前である複製元の要素をａ（ｆ（ｈ−１））と表現する。
【００１５】
各要素には少なくとも加法演算が定義されており、その加法演算を「＋」と表現する。また、各要素には少なくとも加法逆元が定義されており、要素νの加法逆元を「−ν」と表現する。すなわち、上述のａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））は、要素ａ（ｆ（ｈ））と加法逆元−ａ（ｆ（ｈ−１））との加法演算を表し、ｂ（ｉ−１）＋ａ５（ｉ）は、要素ｂ（ｉ−１）と要素ａ５（ｉ）との加法演算を表す。加法演算の例は、加算、排他的論理和、加算結果θに対する整数Ｐを法とした剰余演算θ ｍｏｄ Ｐ（ただし、Ｐは２以上の整数）などである。例えば、加法演算が加算である場合、ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））はａ（ｆ（ｈ））からａ（ｆ（ｈ−１））を減じた減算値であり、ｂ（ｉ−１）＋ａ５（ｉ）は、要素ｂ（ｉ−１）と要素ａ５（ｉ）との加算値である。また、加法単位元を「零」または「０」と表現する。また、加法生成元を「１」と表現する。
【００１６】
本形態における「αの秘匿文」とは、秘密計算が可能な方法でαが秘匿化されて得られる情報を意味する。周知の秘密分散や暗号化などが秘匿化の例であり、そのうち、周知の線形秘密分散や準同型性暗号などが「秘密計算が可能な秘匿化方法」の例である。これらの方式では、例えば、α１とα２との間に二項演算○が定義されており、α１○α２＝α３が成立する場合、α１の秘匿文Ｅ（α１）とα２の秘匿文Ｅ（α２）とを用いてα３の秘匿文Ｅ（α３）＝Ｅ（α１）○Ｅ（α２）を計算することができる。同様に、例えば、α１に単項演算○が定義されており、○α１＝α３が成立する場合、α１の秘匿文Ｅ（α１）を用いてα３の秘匿文Ｅ（α３）＝○Ｅ（α１）を計算することができる。これらの計算のために秘匿文Ｅ（α１）やＥ（α２）を復元する必要はない。秘密計算による秘匿化，復元，加算，減算，乗算，論理演算には、例えば、非特許文献１や非特許文献２に開示された周知技術を用いることができる。秘密計算によるランダム置換には、例えば、非特許文献２や参考文献１（Sven Laur, Jan Willemson, and Bingsheng Zhang, “Round-efficient oblivious database manipulation,” In Xuejia Lai, Jianying Zhou, and Hui Li, editors, ISC, Vol. 7001 of LNCS, pp. 262-277. Springer, 2011.）等に開示された周知技術を用いることができる。秘密計算による安定ソートには、例えば、非特許文献２や参考文献２（濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “秘匿関数計算上の線形時間ソート,” In SCIS, pp. 1-7, 2011.)等に開示された周知技術を用いることができる。その他、例えば、参考文献３（千田浩司, 谷口展郎, 山本剛, 岡崎聖人, 塩野入理, 金井敦， “エルガマル暗号に基づく秘匿回路計算の実装と応用”， CSS2005, pp. 475 - 480, 2005.）等の技術も利用できる。
【００１７】
なお、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む集合である第５集合または第５集合の秘匿文から、事前に前述の要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））を含む集合である第４集合または第４集合の秘匿文が得られる場合には、第１演算部は、この第４集合または第４集合の秘匿文を用い、第２集合または第２集合の秘匿文を得てもよい（事前計算方式）。例えば、要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされた複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む第６集合に含まれる複製元の要素ａ（ｆ（ｈ））をａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にした集合である第４集合または第４集合の秘匿文が事前に得られる場合には、第１演算部は、この第４集合または第４集合の秘匿文を用い、第２集合または第２集合の秘匿文を得てもよい。これにより、演算コストをさらに低減できる。この方式は、例えば、第１集合または第１集合の秘匿文が、第５集合もしくは第５集合の秘匿文、または第６集合もしくは第６集合の秘匿文（以下「第５集合等」）から得られる場合、すなわち、第１集合または第１集合の秘匿文よりも第５集合等が先に得られる場合（例えば、非特許文献２の方式）に適したものである。
【００１８】
そうでない場合、第１演算部が、第１集合または第１集合の秘匿文を用い、第２集合または第２集合の秘匿文を得てもよい（事後計算方式）。例えば、第１演算部は、第１集合または第１集合の秘匿文を用い、複製元であるか否かをソート条件として第１集合に含まれる要素ａ（１），…，ａ（Ｎ）の安定ソートを行って得られる、要素ａ（１），…，ａ（Ｎ）を含み、かつ、要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））の順序が連続した集合である第７集合または第７集合の秘匿文を得、第７集合または第７集合の秘匿文を用い、ｈ＝２，…，Ｍについて、第７集合に含まれる複製元の要素ａ（ｆ（ｈ））をａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にした集合である第８集合または第８集合の秘匿文を得、第８集合または第８集合の秘匿文を用い、第８集合の要素をソートして複製元以外の要素を零にして得られる集合である第２集合、または第２集合の秘匿文を得てもよい。
【００１９】
この場合、第１演算部は、例えば、第１集合の秘匿文を用い、秘密計算によって第７集合の秘匿文を得、要素ａ（１），…，ａ（Ｎ）の安定ソートに応じて要素ａ（１），…，ａ（Ｎ）それぞれの順序を表す要素ｐ（ａ（１）），…，ｐ（ａ（Ｎ））をソートして得られる要素を含む集合である第９集合の秘匿文を得、第７集合の秘匿文を用い、秘密計算によって第８集合の秘匿文を得、第８集合の秘匿文および第９集合の秘匿文を用い、秘密計算によって、第８集合の要素と第９集合の要素との対応関係を維持しつつ、第８集合の要素の順序および第９集合の要素の順序をランダム置換して得られる、第８集合の要素の順序が並び替えられた集合である第１０集合および第９集合の要素の順序が並び替えられた集合である第１１集合にそれぞれ対応する、第１０集合の秘匿文および第１１集合の秘匿文を得、第１１集合の秘匿文の復元結果および第１０集合の秘匿文を用い、第１０集合の要素をソートして複製元以外の要素を零にして得られる集合である第２集合の秘匿文を得てもよい。
【００２０】
ここで、第８集合の秘匿文は、各要素の内容は秘匿されているものの、複製元の要素に対応するａ（ｆ（ｈ））−ａ（ｆ（ｈ−１）の秘匿文の順序が連続している。そのため、第９集合の秘匿文が復元され、複製元の要素に対応するａ（ｆ（ｈ））−ａ（ｆ（ｈ−１）の秘匿文の順序を表す要素が復元されてしまうと、第１集合のいずれの要素が複製元の要素であったのかについての情報がある程度漏洩してしまう。これに対し、上述のように秘密計算でランダム置換を行ってから順序を表す要素を得ることにすれば、このような情報が漏洩することはない。
【００２１】
なお、各実施形態において「第２集合の秘匿文」および「第３集合の秘匿文」を得る場合、第１演算部は、秘密計算によって第２集合の秘匿文を得、第２演算部は、第２集合の秘匿文を用い、秘密計算によって第３集合の秘匿文を得る。
【００２２】
以下、図面を参照して各実施形態を詳細に説明する。
各実施形態では、ある情報αの秘匿文を［α］と表記する。例えば、秘密分散によって秘匿化された［α］は秘密分散の断片（シェア）であり、暗号化によって秘匿化された［α］は暗号文である。ベクトルβの第ｓ要素をβ（ｓ）と表記し、ベクトルβの各要素β（ｓ）を秘匿化したベクトル全体を［β］と表記し、ベクトルβの秘匿文［β］と呼ぶ。
【００２３】
また、各実施形態では、要素ａ（１），…，ａ（Ｎ）を第１，…，Ｎ要素とするＮ次元のベクトルａを第１集合とし、要素ａ５（１），…，ａ５（Ｎ）を第１，…，Ｎ要素とするＮ次元のベクトルａ５を第２集合とし、要素ｂ（１），…，ｂ（Ｎ）を第１，…，Ｎ要素とするＮ次元のベクトルｂを第３集合とした例を説明する。これらのＮ次元のベクトルの各要素は、第１，…，Ｎ要素としてそれぞれ順序付けされている。以下にＮ＝１０、Ｍ＝４の場合のベクトルａ，ａ５，ｂを例示する。
【数１】
2015107780.tif 000003
ただし、ベクトルａの第１，第４，第５，第９要素であるｗ，ｘ，ｙ，ｚがそれぞれ複製元の要素であり、その他の要素＊が複製元ではない要素である。なお「＊」は任意の要素を表す。また、この例では２≦Ｍ＜Ｎであるが、２≦Ｍ≦Ｎでも本実施形態の処理を行うことはできる。
【００２４】
［第１実施形態］
本形態では、前述した事前計算方式の具体例を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム１は、１個以上の要素複製装置１１−１〜Ｋを有する。ただし、秘密分散によって秘匿化を行う場合にはＫは２以上の整数であり、暗号化によって秘匿計算を行う場合にはＫは１以上の整数である。図２Ａに例示するように、本形態の要素複製装置１１−ｋ（ただし、ｋ∈｛１，…，Ｋ｝）は、記憶部１１１−ｋと加法逆元演算部１１３−ｋと入力情報演算部１１４−ｋ（第１演算部）と累積加法演算部１１５−ｋ（第２演算部）と制御部１１６−ｋとを有する。図２Ｂに例示するように、本形態の入力情報演算部１１４−ｋは、複製元配置部１１４１−ｋと複製元情報生成部１１４２−ｋと乗法演算部１１４３−ｋとを有する。なお、要素複製装置１１−ｋは、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を有する汎用または専用のコンピュータに所定のプログラムが読み込まれることで構成される装置であり、制御部１１６−ｋの制御のもとで各処理を実行する。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００２５】
＜事前計算＞
本形態では、ベクトルａ（第１集合）が要素複製装置１１−ｋに入力されるのではなく、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））のみからなるベクトルｄ１の秘匿文[ｄ１]（第５集合の秘匿文または第６集合の秘匿文）が要素複製装置１１−ｋに入力され、記憶部１１１−ｋに格納されているものとする。なお、ベクトルｄ１の各要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））は、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされたベクトルである。本形態の例の場合、ベクトルｄ１の第ｊ要素ｄ１（ｊ）はｄ１（ｊ）＝ａ（ｆ（ｊ））（ただし、ｊ∈｛１，…，Ｍ｝）である。なお、ベクトルａの大きさＮおよび要素ａ（１），…，ａ（Ｎ）の順序は事前に定められている（本形態では、ａ（１），…，ａ（Ｎ）がＮ次元ベクトルの第１，…，Ｎ要素）。
【００２６】
図２Ｂに例示するように、加法逆元演算部１１３−ｋ（図２Ａ）は、記憶部１１１−ｋからベクトルｄ１の秘匿文［ｄ１］を抽出し、秘密計算によって、ベクトルｄ１に含まれる複製元の要素ａ（ｆ（ｈ））をａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））（ただし、ｈ∈｛２，…，Ｍ｝）にし、複製元の要素ａ（ｆ（１））をそのまま維持したベクトルｄ２（第４集合）の秘匿文［ｄ２］を得る。すなわち、ベクトルｄ２の要素ｄ２（ｈ）（ただし、ｈ∈｛２，…，Ｍ｝）は、要素ｄ２（ｈ）＝ｄ１（ｈ）−ｄ１（ｈ−１）であり、ベクトルｄ２の要素ｄ２（１）は、ｄ２（１）＝ｄ１（１）である（ステップＳ１１３）。加法逆元演算部１１３−ｋは、ベクトルｄ２の秘匿文［ｄ２］を出力し、ベクトルｄ２の秘匿文［ｄ２］は記憶部１１１−ｋに格納される（ステップＳ１１１）。なお、式（１）で例示したベクトルａの場合、ベクトルａ，ｄ１，ｄ２の関係は以下のようになる。
【数２】
2015107780.tif 000004
【００２７】
＜要素複製＞
図２Ｃを用いて本形態の要素複製の処理を説明する。入力情報演算部１１４−ｋは、記憶部１１１−ｋからベクトルｄ２（第４集合）の秘匿文［ｄ２］を抽出する。入力情報演算部１１４−ｋは、ベクトルｄ２の秘匿文［ｄ２］を用い、秘密計算によって、ｈ＝２，…，Ｍについて、ベクトルａの複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、複製元以外の要素を零にして得られる、要素ａ５（１），…，ａ５（Ｎ）を第１，…，Ｎ要素とするＮ次元のベクトルであるベクトルａ５（第２集合）の秘匿文［ａ５］を得る。本形態の例の場合、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序が予め定められており、各複製元の要素ａ（ｆ（ｈ））の順序（ベクトルａでの位置）も定められている。入力情報演算部１１４−ｋは、これに従ってベクトルａの各複製元の要素ａ（ｆ（ｈ））の位置に要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））を配置し、その他の位置に零を配置したＮ次元のベクトルであるベクトルａ５の秘匿文［ａ５］を得て出力する（ステップＳ１１４）。
【００２８】
累積加法演算部１１５−ｋは、ベクトルａ５（第２集合）の秘匿文［ａ５］を用い、秘密計算によって、第１要素がｂ（１）＝ａ５（１）であり、第ｉ＝２，…，Ｎ要素がｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）であるＮ次元ベクトルであるベクトルｂ（第３集合）の秘匿文［ｂ］を得て出力する（ステップＳ１１５）。累積加法演算部１１５−ｋは、例えば、まずｂ（１）＝ａ５（１）の秘匿文［ｂ（１）］を得る秘密計算を行い、その後、ｉ＝２からｉを１ずつ増加させながら、各ｉ＝２，…，Ｎについてｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）の秘匿文［ｂ（ｉ）］を得る秘密計算を行って、ベクトルｂの秘匿文［ｂ］を得る。
【００２９】
例えば、式（１）に例示したベクトルａの場合、上述したベクトルａ５，ｂの関係は以下のようになる。
【数３】
2015107780.tif 000005
【００３０】
［第１実施形態の変形例１］
第１実施形態では、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされたベクトルｄ１の秘匿文[ｄ１]が要素複製装置１１−ｋに入力され、記憶部１１１−ｋに格納されている例を示した。本変形例では、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））のみからなるが、これらがベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序となっていないベクトルｄの秘匿文[ｄ]が要素複製装置１１−ｋに入力され、記憶部１１１−ｋに格納されている場合の処理を説明する。
【００３１】
本変形例の秘密計算システム１’の要素複製装置１１’−ｋは、第１実施形態の要素複製装置１１’−ｋにソート部１１２’−ｋを加えたものである（図１および図２Ａ）。ソート部１１２’−ｋは、記憶部１１１−ｋからベクトルｄの秘匿文[ｄ]を抽出し、秘密計算によってベクトルｄの秘匿文[ｄ]をソートし、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされたベクトルｄ１の秘匿文[ｄ１]を得て出力する（図２Ｂ／ステップＳ１１２’）。ベクトルｄ１の秘匿文[ｄ１]は加法逆元演算部１１３−ｋに入力される。その他は第１実施形態で説明した通りである。例えば、式（１）に例示したベクトルａの場合、ベクトルａ，ｄ，ｄ１，ｄ２の関係は以下のようになる。
【数４】
2015107780.tif 000006
【００３２】
［第１実施形態の変形例２］
第１実施形態および第１実施形態の変形例１では、ベクトルの秘匿文を処理対象として秘密計算を行った。しかしながら、公開してよいベクトルについては、ベクトルの秘匿文を処理対象とすることに代えて平文であるベクトルを処理対象とし、秘密計算を行うことに代えて平文であるベクトルに対する演算を行ってもよい。例えば、ベクトルｄを公開してよい場合には、ソート部１１２’−ｋがベクトルｄをソートしてベクトルｄ１を得てもよい。例えば、ベクトルｄ１を公開してよい場合には、加法逆元演算部１１３−ｋがベクトルｄ２を用いてベクトルｄ１を計算し、入力情報演算部１１４−ｋがベクトルｄ２をそのまま用いてもよい。その他、例えば、加法逆元演算部１１３−ｋがベクトルｄ２を用いてベクトルａ５を計算してもよいし、累積加法演算部１１５−ｋがベクトルａ５を用いてベクトルｂを計算してもよい。その他、演算結果のベクトルを秘匿化して出力してもよい。
【００３３】
［第２実施形態］
本形態では、前述した事後計算方式の具体例を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム２は、１個以上の要素複製装置１２−１〜Ｋを有する。図３Ａに例示するように、本形態の要素複製装置２１−ｋ（ただし、ｋ∈｛１，…，Ｋ｝）は、記憶部２１１−ｋと順序情報生成部２１２−ｋと入力情報演算部２１４−ｋ（第１演算部）と累積加法演算部１１５−ｋ（第２演算部）と制御部１１６−ｋとを有する。入力情報演算部２１４−ｋは、安定ソート部２１４１−ｋと加法逆元演算部２１４２−ｋとソート部２１４３−ｋと乗法演算部２１４４−ｋとを有する。図３Ｂに例示するように、ソート部２１４３−ｋは、ランダム置換部２１４３ａ−ｋと復元部２１４３ｂ−ｋと順序復元部２１４３ｃ−ｋとを有する。なお、累積加法演算部１１５−ｋは第１実施形態で説明したものと同じである。要素複製装置２１−ｋは、例えば、汎用または専用のコンピュータに所定のプログラムが読み込まれることで構成される装置であり、制御部２１６−ｋの制御のもとで各処理を実行する。
【００３４】
＜要素複製＞
図４Ａを用いて本形態の要素複製の処理を説明する。
前提として、ベクトルａ（第１集合）の秘匿文［ａ］と、ベクトルａの要素ａ（１），…，ａ（Ｎ）が複製元の要素であるか否かを表すベクトルｃの秘匿文［ｃ］とが要素複製装置２１−ｋに入力され、記憶部２１１−ｋに格納されているとする。なお、ベクトルｃの第ｎ要素はφ（ａ（ｎ））である。ただし、ａ（ｎ）が複製元の要素であるときφ（ａ（ｎ））＝１であり、φ（ａ（ｎ））が複製元の要素でないときφ（ａ（ｎ））＝０である。例えば、式（１）に例示したベクトルａの場合、ベクトルａ，ｃの関係は以下のようになる。
【数５】
2015107780.tif 000007
【００３５】
まず、順序情報生成部２１２−ｋ（図３Ａ）は、ベクトルａの各要素ａ（ｎ）（ただし、ｎ∈｛１，…，Ｎ｝）の順序（位置）の目印となるベクトルｐの秘匿文［ｐ］を生成して出力する（ステップＳ２１２）。ベクトルｐは、互いに異なるＮ個の要素ｐ（ａ（ｎ））（ただし、ｎ∈｛１，…，Ｎ｝）（例えば、予め定められた要素）からなるＮ次元のベクトルであればよく、例えば、ｐ（ａ（ｎ））＝ｎ−１（ただし、ｎ∈｛１，…，Ｎ｝）とすればよい。ベクトルｐの秘匿文［ｐ］は記憶部２１１−ｋに格納される。例えば、ベクトルａが式（１）に例示したものであり、ｐ（ａ（ｎ））＝ｎ−１である場合、ベクトルａ，ｃ，ｐの関係は以下のようになる。
【数６】
2015107780.tif 000008
【００３６】
入力情報演算部２１４−ｋは、記憶部２１１−ｋからベクトルａ（第１集合）の秘匿文［ａ］とベクトルｐの秘匿文［ｐ］とベクトルｃの秘匿文［ｃ］を抽出し、秘密計算によってベクトルａ５（第２集合）の秘匿文［ａ５］を得て出力する（ステップＳ２１４）。
【００３７】
《ステップＳ２１４の詳細》
図４Ｂを用いてステップＳ２１４の詳細を説明する。
本形態では、まず、安定ソート部２１４１−ｋが、記憶部２１１−ｋからベクトルａの秘匿文［ａ］とベクトルｐの秘匿文［ｐ］とを抽出する。安定ソート部２１４１−ｋは、抽出したベクトルａの秘匿文［ａ］とベクトルｐの秘匿文［ｐ］を用い、秘密計算によって、複製元であるか否かをソート条件としてベクトルａに含まれる要素ａ（１），…，ａ（Ｎ）の安定ソートを行って得られるベクトルａ１（第７集合）の秘匿文［ａ１］と、この要素ａ（１），…，ａ（Ｎ）の安定ソートに応じてベクトルｐの要素ｐ（ａ（１）），…，ｐ（ａ（Ｎ））をソートして得られる要素からなるベクトルｐ１（第９集合）の秘匿文［ｐ１］とを得て出力する（ステップＳ２１４１）。ただし、ベクトルａ１は、要素ａ（１），…，ａ（Ｎ）のみを含み、かつ、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））の順序が連続したベクトルとなる。すなわち、ベクトルａ１は要素ａ（１），…，ａ（Ｎ）のみを含み、かつ、ベクトルａ１の第η，…，η＋Ｍ−１要素が複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））であり、かつ、それ以外の要素が複製元ではない要素である。ただし、ηは１以上Ｎ＋１−Ｍ以下の整数である。また、「第η要素」とはη番目の要素を意味する。例えば、ベクトルａ１の第１，…，Ｍ要素が複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））であり、かつ、それ以外の要素が複製元ではない要素であってもよいし、ベクトルａ１の第Ｎ−Ｍ＋１，…，Ｎ要素が複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））であり、かつ、それ以外の要素が複製元ではない要素であってもよい。この安定ソートはベクトルａの要素ａ（ｎ）とベクトルｐの要素ｐ（ａ（ｎ））との対応を保ったまま行われる。言い換えると、要素ａ（ｎ）と要素ｐ（ａ（ｎ））との対応関係が保持される。例えば、この安定ソートによって要素ａ（ｎ）がベクトルａ１のｎ’番目（ただし、ｎは１以上Ｎ以下の整数）の要素となる場合、要素ａ（ｎ）に対応する要素ｐ（ａ（ｎ））はベクトルｐ１のｎ’番目の要素となる関係にある。ただし、これは平文での要素の順序であり、必ずしも秘匿化された要素がこの順序であるとは限らない。例えば、ベクトルａが式（１）に例示したものであり、ｐ（ａ（ｎ））＝ｎ−１であり、ベクトルａ１の第１，…，Ｍ要素が複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））であり、かつ、それ以外の要素が複製元ではない要素である場合、ベクトルａ１，ｐ１の関係は以下のようになる。
【数７】
2015107780.tif 000009
【００３８】
加法逆元演算部２１４２−ｋは、ベクトルａ１（第７集合）の秘匿文［ａ１］を用い、秘密計算によって、ベクトルａ１に含まれる要素ａ１（１），ａ１（２），…，ａ１（Ｎ）を要素ａ２（１）＝ａ１（１），ａ２（２）＝ａ１（２）−ａ１（１），…，ａ２（Ｎ）＝ａ１（Ｎ）−ａ１（Ｎ−１）にしたＮ次元のベクトルであるベクトルａ２（第８集合）の秘匿文［ａ２］を得て出力する（ステップＳ２１４２）。例えば、式（２）に例示したベクトルａ２の場合、ベクトルｐ１，ａ１，ａ２の関係は以下のようになる。
【数８】
2015107780.tif 000010
【００３９】
ソート部２１４３−ｋは、ベクトルａ２（第８集合）の秘匿文［ａ２］およびベクトルｐ１（第９集合）の秘匿文［ｐ１］を用い、秘密計算によって、ベクトルａ２の要素をソートして得られるＮ次元のベクトルであるベクトルａ４の秘匿文［ａ４］を得て出力する（ステップＳ２１４３）。ただし、ベクトルａ４は、ベクトルａ２の要素の順序を、ベクトルａの要素の順序に対応する元の順序に並び替えて得られるベクトルである。すなわち、ベクトルａ４は、ベクトルａ２の要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））をベクトルａの複製元の要素ａ（ｆ（ｈ））の順序にし、ベクトルａ２の要素ａ（ｆ（１））をベクトルａの複製元の要素ａ（ｆ（１））の順序にし、ベクトルａ２のその他の要素をそれに対応するベクトルａの元の順序に戻して得られるベクトルである。
【００４０】
《ステップＳ２１４３の詳細》
図４Ｃを用い、ステップＳ２１４３の詳細を説明する。
ソート部２１４３−ｋのランダム置換部２１４３ａ−ｋは、ベクトルａ２（第８集合）の秘匿文［ａ２］およびベクトルｐ１（第９集合）の秘匿文［ｐ１］を用い、秘密計算によって、ベクトルａ２の要素ａ２（ｎ）とベクトルｐ１の要素ｐ１（ｎ）との対応関係を維持しつつ（ただし、ｎ∈｛１，…，Ｎ｝）、ベクトルａ２の要素ａ２（１），…，ａ２（Ｎ）の順序およびベクトルｐ１の要素ｐ１（１），…，ｐ１（Ｎ）の順序をランダム置換して得られる、Ｎ次元のベクトルａ３（第１０集合）およびＮ次元のベクトルｐ３（第１１集合）にそれぞれ対応する、ベクトルａ３の秘匿文［ａ３］およびベクトルｐ３の秘匿文［ｐ３］を得て出力する（ステップＳ２１４３ａ）。ただし、ベクトルａ３はベクトルａ２の要素ａ２（１），…，ａ２（Ｎ）の順序が並び替えられたものであり、ベクトルｐ３はベクトルｐ１の要素ｐ１（１），…，ｐ１（Ｎ）の順序が並び替えられたものである。言い換えると、ランダム置換部２１４３ａ−ｋは、ベクトルａ２（第８集合）の秘匿文［ａ２］およびベクトルｐ１（第９集合）の秘匿文［ｐ１］を用い、秘密計算によって、ベクトルａ３の秘匿文［ａ３］およびベクトルｐ３の秘匿文［ｐ３］を得て出力する。ベクトルａ３はベクトルａ２の要素ａ２（１），…，ａ２（Ｎ）の順序をランダム置換して得られるものであり、ベクトルｐ３はベクトルｐ１の要素ｐ１（１），…，ｐ１（Ｎ）の順序をランダム置換して得られるものである。この処理では要素ａ２（ｎ）と要素ｐ１（ｎ）との対応関係が維持される。例えば、このランダム置換によって要素ａ２（ｎ）がベクトルａ３のｎ’番目の要素となる場合、要素ｐ１（ｎ）はベクトルｐ３のｎ’番目の要素となる関係にある。ただし、これは平文での要素の順序であり、必ずしも秘匿化された要素がこの順序であるとは限らない。式（３）に例示したベクトルｐ１，ａ２の場合、ベクトルｐ３，ａ３の関係は、例えば以下のようになる。
【数９】
2015107780.tif 000011
【００４１】
復元部２１４３ｂ−ｋは、ベクトルｐ３の秘匿文［ｐ３］からベクトルｐ３を復元して出力する（ステップｓ２１４３ｂ）。
【００４２】
順序復元部２１４３ｃ−ｋは、ベクトルａ３の秘匿文［ａ３］を用い、秘密計算によって、ベクトルａ３の要素をベクトルｐ３に従ってソートして得られるＮ次元のベクトルであるベクトルａ４の秘匿文［ａ４］を得て出力する（ステップＳ２１４３ｃ）。ベクトルａ４は、ベクトルａ３の要素をベクトルａの要素の順序に対応する元の順序に並び替えて得られるベクトルである。この順序はベクトルｐ３の要素から判断できる（式（４）参照）。すなわち、ベクトルｐ３の要素の順序をベクトルｐの要素の順序に並び替えるソートによって、ベクトルａ３の要素を並び替えて得られるＮ次元のベクトルがベクトルａ４である。式（４）に例示したベクトルｐ３，ａ３の場合、ベクトルａ４は、例えば以下のようになる（《ステップＳ２１４３の詳細》の説明終わり）。
【数１０】
2015107780.tif 000012
【００４３】
乗法演算部２１４４−ｋが、ベクトルａ４の秘匿文［ａ４］およびベクトルｃの暗号文［ｃ］を用い、秘密計算によって、ベクトルａ４の要素ａ４（ｎ）とベクトルｃの要素ｃ（ｎ）との乗法演算結果（例えば、乗算結果や乗算結果の剰余）を要素ａ５（ｎ）（ただし、ｎ∈｛１，…，Ｎ｝）として得られるベクトルａ５（第２集合）の秘匿文［ａ５］を得て出力する（ステップＳ２１４４）。なお、要素ａ４（ｎ）はベクトルａ４のｎ番目の要素であり、要素ｃ（ｎ）はベクトルｃのｎ番目の要素であり、要素ａ５（ｎ）はベクトルａ５のｎ番目の要素である。この処理は、ベクトルａ４の複製元ではない要素を零にしたベクトルａ５の秘匿文［ａ５］を得る処理である。例えば、式（１）に例示したベクトルａに対応するベクトルｃ、および式（５）に例示したベクトルａ４の場合、ベクトルａ４，ｃ，ａ５の関係は以下のようになる（《ステップＳ２１４の詳細》の説明終わり）。
【数１１】
2015107780.tif 000013
【００４４】
ベクトルａ５の秘匿文［ａ５］は、累積加法演算部１１５−ｋに入力され、第１実施形態で説明した処理が実行され、ベクトルｂの秘匿文［ｂ］が得られる。例えば、式（６）のベクトルａ５の場合、ベクトルａ５，ｂの関係は以下のようになる。
【数１２】
2015107780.tif 000014
【００４５】
［第２実施形態の変形例１］
第２実施形態では、ソート部２１４３−ｋが、秘密計算によってランダム置換を含むソートを行った。本変形例では、これに代えて、秘密計算によってランダム置換を含まないソートを行う。その他は、第２実施形態と同じである。
【００４６】
本変形例の秘密計算システム２’の要素複製装置２１’−ｋの入力情報演算部２１４−ｋは、第２実施形態のソート部２１４３−ｋに代えて、ソート部２１４３’−ｋを備えるものである（図３Ａ）。ソート部２１４３’−ｋは、ベクトルａ２（第８集合）の秘匿文［ａ２］およびベクトルｐ１（第９集合）の秘匿文［ｐ１］を用い、秘密計算によって、ベクトルａ２の要素をソートして得られるＮ次元のベクトルであるベクトルａ４の秘匿文［ａ４］を得て出力する（ステップＳ２１４３’）。ただし、ステップＳ２１４３と異なり、ソート部２１４３’−ｋは、前述のステップＳ２１４３ａ，Ｓ２１４３ｂを実行せずに、ベクトルｐ１の秘匿文［ｐ１］を用い、ベクトルａ４の秘匿文［ａ４］を得て出力する。ソート部２１４３’−ｋは、ベクトルｐ１の秘匿文［ｐ１］から復元したベクトルｐ１を用い、秘密計算によってベクトルａ４の秘匿文［ａ４］を得てもよいし、ベクトルｐ１の秘匿文［ｐ１］を復元することなく、秘密計算によってベクトルａ４の秘匿文［ａ４］を得てもよい。
【００４７】
［第２実施形態の変形例２］
第２実施形態および第２実施形態の変形例１では、ベクトルの秘匿文を処理対象として秘密計算を行った。しかしながら、公開してよいベクトルについては、ベクトルの秘匿文を処理対象とすることに代えて平文であるベクトルを処理対象とし、秘密計算を行うことに代えて平文であるベクトルに対する演算を行ってもよい。例えば、順序情報生成部２１２−ｋがベクトルｐを出力してもよいし、安定ソート部２１４１−ｋがベクトルａ，ｐの安定ソートを行ってベクトルａ１，ｐ１を得て出力してもよいし、加法逆元演算部２１４２−ｋがベクトルａ１からベクトルａ２を得て出力してもよいし、ソート部２１４３−ｋや２１４３’−ｋがベクトルａ２，ｐ１を用いてベクトルａ４を得て出力してもよいし、乗法演算部２１４４−ｋがベクトルベクトルａ４，ｃを用いてベクトルａ５を得て出力してもよい。
【００４８】
［特徴］
以上のように、複製元の要素を、当該複製元の要素とその一つ前の複製元の要素の加法逆元との加法演算結果（例えば減算結果）に置き換えておくことで、複製の処理を多くの処理を非常に軽い演算である加法演算（例えば加算）で実現できる。その結果、従来よりも演算コストを低減させることができる。なお、ベクトルａ４または秘匿文［ａ４］からベクトルａ５または秘匿文［ａ５］を得るためには乗算等の乗算演算が１段必要であるが、その段数はＮに依存しない。特に、第１実施形態のように複製元の要素に対して事前処理が行える場合には、要素複製時の複製に要する計算はＯ（Ｎ）回の加算演算のみとなる。
【００４９】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５０】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５１】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５３】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００５４】
本発明は、例えば、表計算分野等に利用でき、特に、秘匿化された表の一部の要素を秘匿化したままで複製する計算を行うソフトウェア分野（暗号技術分野）等に利用できる。例えば、暗号技術分野で利用される集合の要素複製処理（表計算処理等）に本発明を利用できる。
【符号の説明】
【００５５】
秘密計算システム  １，１’，２，２’
要素複製装置  １１−ｋ，１１’−ｋ，２１−ｋ，２１’−ｋ
【図１】
2015107780.tif 000015
【図２】
2015107780.tif 000016
【図３】
2015107780.tif 000017
【図４】
2015107780.tif 000018
【手続補正書】
【提出日】平成28年6月30日(2016.6.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
秘匿化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１等参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという秘匿化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算，定数加算，乗算，定数倍，論理演算（否定，論理積，論理和，排他的論理和），データ形式変換（整数，二進数）等の演算結果を３つの秘密計算装置に分散された状態、すなわち秘匿化されたまま保持させることができる。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
＜事前計算＞
本形態では、ベクトルａ（第１集合）が要素複製装置１１−ｋに入力されるのではなく、複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））のみからなるベクトルｄ１の秘匿文[ｄ１]（第５集合の秘匿文または第６集合の秘匿文）が要素複製装置１１−ｋに入力され、記憶部１１１−ｋに格納されているものとする。なお、ベクトルｄ１の各要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））には、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされている。本形態の例の場合、ベクトルｄ１の第ｊ要素ｄ１（ｊ）はｄ１（ｊ）＝ａ（ｆ（ｊ））（ただし、ｊ∈｛１，…，Ｍ｝）である。なお、ベクトルａの大きさＮおよび要素ａ（１），…，ａ（Ｎ）の順序は事前に定められている（本形態では、ａ（１），…，ａ（Ｎ）がＮ次元ベクトルの第１，…，Ｎ要素）。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
本変形例の秘密計算システム１’の要素複製装置１１’−ｋは、第１実施形態の要素複製装置１１−ｋにソート部１１２’−ｋを加えたものである（図１および図２Ａ）。ソート部１１２’−ｋは、記憶部１１１−ｋからベクトルｄの秘匿文[ｄ]を抽出し、秘密計算によってベクトルｄの秘匿文[ｄ]をソートし、ベクトルａの要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされたベクトルｄ１の秘匿文[ｄ１]を得て出力する（図２Ｂ／ステップＳ１１２’）。ベクトルｄ１の秘匿文[ｄ１]は加法逆元演算部１１３−ｋに入力される。その他は第１実施形態で説明した通りである。例えば、式（１）に例示したベクトルａの場合、ベクトルａ，ｄ，ｄ１，ｄ２の関係は以下のようになる。
【数４】
2015107780.tif 000019
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
加法逆元演算部２１４２−ｋは、ベクトルａ１（第７集合）の秘匿文［ａ１］を用い、秘密計算によって、ベクトルａ１に含まれる要素ａ１（１），ａ１（２），…，ａ１（Ｎ）を要素ａ２（１）＝ａ１（１），ａ２（２）＝ａ１（２）−ａ１（１），…，ａ２（Ｎ）＝ａ１（Ｎ）−ａ１（Ｎ−１）にしたＮ次元のベクトルであるベクトルａ２（第８集合）の秘匿文［ａ２］を得て出力する（ステップＳ２１４２）。例えば、式（２）に例示したベクトルａ１の場合、ベクトルｐ１，ａ１，ａ２の関係は以下のようになる。
【数８】
2015107780.tif 000020
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４１
【補正方法】変更
【補正の内容】
【００４１】
復元部２１４３ｂ−ｋは、ベクトルｐ３の秘匿文［ｐ３］からベクトルｐ３を復元して出力する（ステップＳ２１４３ｂ）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
乗法演算部２１４４−ｋが、ベクトルａ４の秘匿文［ａ４］およびベクトルｃの秘匿文［ｃ］を用い、秘密計算によって、ベクトルａ４の要素ａ４（ｎ）とベクトルｃの要素ｃ（ｎ）との乗法演算結果（例えば、乗算結果や乗算結果の剰余）を要素ａ５（ｎ）（ただし、ｎ∈｛１，…，Ｎ｝）として得られるベクトルａ５（第２集合）の秘匿文［ａ５］を得て出力する（ステップＳ２１４４）。なお、要素ａ４（ｎ）はベクトルａ４のｎ番目の要素であり、要素ｃ（ｎ）はベクトルｃのｎ番目の要素であり、要素ａ５（ｎ）はベクトルａ５のｎ番目の要素である。この処理は、ベクトルａ４の複製元ではない要素を零にしたベクトルａ５の秘匿文［ａ５］を得る処理である。例えば、式（１）に例示したベクトルａに対応するベクトルｃ、および式（５）に例示したベクトルａ４の場合、ベクトルａ４，ｃ，ａ５の関係は以下のようになる（《ステップＳ２１４の詳細》の説明終わり）。
【数１１】
2015107780.tif 000021
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
［第２実施形態の変形例２］
第２実施形態および第２実施形態の変形例１では、ベクトルの秘匿文を処理対象として秘密計算を行った。しかしながら、公開してよいベクトルについては、ベクトルの秘匿文を処理対象とすることに代えて平文であるベクトルを処理対象とし、秘密計算を行うことに代えて平文であるベクトルに対する演算を行ってもよい。例えば、順序情報生成部２１２−ｋがベクトルｐを出力してもよいし、安定ソート部２１４１−ｋがベクトルａ，ｐの安定ソートを行ってベクトルａ１，ｐ１を得て出力してもよいし、加法逆元演算部２１４２−ｋがベクトルａ１からベクトルａ２を得て出力してもよいし、ソート部２１４３−ｋや２１４３’−ｋがベクトルａ２，ｐ１を用いてベクトルａ４を得て出力してもよいし、乗法演算部２１４４−ｋがベクトルａ４，ｃを用いてベクトルａ５を得て出力してもよい。
【手続補正書】
【提出日】平成28年11月16日(2016.11.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１集合が、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）を含む集合であり、前記複数個の要素ａ（１），…，ａ（Ｎ）からなる集合が複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含み、複製元の要素ａ（ｆ（ｈ））よりも順序が前であって前記複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））であり、ｈ＝２，…，Ｍについて、前記第１集合に含まれる前記複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、前記第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または前記第２集合の秘匿文を得る第１演算部と、
前記第２集合の１番目の要素がａ５（１）であり、前記第２集合のｉ＝２，…，Ｎ番目の要素がａ５（ｉ）であり、前記第２集合を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合もしくは前記第３集合の秘匿文を得るか、または、前記第２集合の秘匿文を用い、前記第３集合の秘匿文を得る第２演算部と、
を有する要素複製装置。
【請求項２】
請求項１の要素複製装置であって、
前記複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む集合である第５集合から、事前に前記要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））を含む集合である第４集合もしくは前記第４集合の秘匿文が得られているか、または、前記第５集合の秘匿文から、前記第４集合の秘匿文が得られており、かつ、前記第１演算部が、前記第４集合を用い、前記第２集合もしくは前記第２集合の秘匿文を得るか、または、前記第１演算部が、前記第４集合の秘匿文を用い、前記第２集合の秘匿文を得るか、または、
前記第１演算部が、前記第１集合を用い、前記第２集合もしくは前記第２集合の秘匿文を得るか、または、前記第１演算部が、前記第１集合の秘匿文を用い、前記第２集合の秘匿文を得る要素複製装置。
【請求項３】
請求項１または２の要素複製装置であって、
前記要素ａ（１），…，ａ（Ｎ）の順序に沿った順序付けがなされた前記複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含む第６集合に含まれる前記複製元の要素ａ（ｆ（ｈ））をａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にした集合である第４集合または前記第４集合の秘匿文が事前に得られており、
前記第１演算部は、前記第４集合を用い、前記第２集合もしくは前記第２集合の秘匿文を得るか、または、前記第４集合の秘匿文を用い、前記第２集合の秘匿文を得る要素複製装置。
【請求項４】
請求項１または２の要素複製装置であって、
前記第１演算部は、
前記第１集合を用い、複製元であるか否かをソート条件として前記第１集合に含まれる前記要素ａ（１），…，ａ（Ｎ）の安定ソートを行って得られる、前記要素ａ（１），…，ａ（Ｎ）を含み、かつ、前記要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））の順序が連続した集合である第７集合もしくは前記第７集合の秘匿文を得るか、または、前記第１集合の秘匿文を用い、前記第７集合の秘匿文を得、
前記第７集合を用い、ｈ＝２，…，Ｍについて、前記第７集合に含まれる要素ａ１（１），ａ１（２），…，ａ１（Ｎ）を要素ａ２（１）＝ａ１（１），ａ２（２）＝ａ１（２）−ａ１（１），…，ａ２（Ｎ）＝ａ１（Ｎ）−ａ１（Ｎ−１）にした集合である第８集合もしくは前記第８集合の秘匿文を得るか、または、前記第７集合の秘匿文を用い、前記第８集合の秘匿文を得、
前記第８集合を用い、前記第８集合の要素をソートして複製元以外の要素を零にして得られる集合である前記第２集合もしくは前記第２集合の秘匿文を得るか、または、前記第８集合の秘匿文を用い、前記第２集合の秘匿文を得る、要素複製装置。
【請求項５】
請求項４の要素複製装置であって、
前記第１演算部は、
前記第１集合の秘匿文を用い、秘密計算によって前記第７集合の秘匿文を得、
前記要素ａ（１），…，ａ（Ｎ）の安定ソートに応じて前記要素ａ（１），…，ａ（Ｎ）それぞれの順序を表す要素ｐ（ａ（１）），…，ｐ（ａ（Ｎ））をソートして得られる要素を含む集合である第９集合の秘匿文を得、
前記第７集合の秘匿文を用い、秘密計算によって前記第８集合の秘匿文を得、
前記第８集合の秘匿文および前記第９集合の秘匿文を用い、秘密計算によって、前記第８集合の要素と前記第９集合の要素との対応関係を維持しつつ、前記第８集合の要素の順序および前記第９集合の要素の順序をランダム置換して得られる、前記第８集合の要素の順序が並び替えられた集合である第１０集合および前記第９集合の要素の順序が並び替えられた集合である第１１集合にそれぞれ対応する、第１０集合の秘匿文および第１１集合の秘匿文を得、
前記第１１集合の秘匿文の復元結果および前記第１０集合の秘匿文を用い、前記第１０集合の要素をソートして複製元以外の要素を零にして得られる集合である前記第２集合の秘匿文を得る、要素複製装置。
【請求項６】
請求項１の要素複製装置であって、
前記第１演算部は、秘密計算によって前記第２集合の秘匿文を得、
前記第２演算部は、前記第２集合の秘匿文を用い、秘密計算によって前記第３集合の秘匿文を得る、要素複製装置。
【請求項７】
第１集合が、順序付けされた複数個の要素ａ（１），…，ａ（Ｎ）を含む集合であり、前記複数個の要素ａ（１），…，ａ（Ｎ）からなる集合が複数個の複製元の要素ａ（ｆ（１）），…，ａ（ｆ（Ｍ））を含み、複製元の要素ａ（ｆ（ｈ））よりも順序が前であって前記複製元の要素ａ（ｆ（ｈ））に順序が最も近い複製元の要素ａ（ｆ（ｈ−１））の加法逆元が−ａ（ｆ（ｈ−１））であり、第１演算部で、ｈ＝２，…，Ｍについて、前記第１集合に含まれる前記複製元の要素ａ（ｆ（ｈ））を要素ａ（ｆ（ｈ））−ａ（ｆ（ｈ−１））にし、前記第１集合に含まれる複製元以外の要素を零にして得られる、複数個の要素ａ５（１），…，ａ５（Ｎ）を含む集合である第２集合または前記第２集合の秘匿文を得る第１ステップと、
前記第２集合の１番目の要素がａ５（１）であり、前記第２集合のｉ＝２，…，Ｎ番目の要素がａ５（ｉ）であり、第２演算部で、前記第２集合を用い、１番目の要素ｂ（１）＝ａ５（１）とｉ＝２，…，Ｎ番目の要素ｂ（ｉ）＝ｂ（ｉ−１）＋ａ５（ｉ）とを含む集合である第３集合もしくは前記第３集合の秘匿文を得るか、または、前記第２集合の秘匿文を用い、前記第３集合の秘匿文を得る第２ステップと、
を有する要素複製方法。
【請求項８】
請求項１の要素複製装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2015107780.tif 000022
2015107780.tif 000023