(57)【要約】      （修正有）【課題】安全性を確保しつつ、秘匿計算を行うために必要な情報の受け渡し量を削減する技術を提供する。【解決手段】分散管理装置に入力値ａが入力されたとき、シード値ｓ０，…，ｓＮ−１を生成し、シード値ｓ０，…，ｓＮ−１それぞれの関数値ａ０，…，ａＮ−１と入力値ａとに対する関数値ａ’を計算し、部分集合Ｐｓｕｂ（ｊ）に属する元Ｐ（ｉ）に対し、関数値ａ’の分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）を得て出力する。ただし、ｎおよびｋが２以上の整数、Ｎ＝ｎＣｋ−１、Ｐｓｅｔがｎ個の元Ｐ（０），…，Ｐ（ｎ−１）からなる集合、Ｐｓｕｂ（ｊ）が集合Ｐｓｅｔに属するｎ−ｋ＋１個の元からなる部分集合である。【選択図】図５
2014137516.tif 000002
【特許請求の範囲】
【請求項１】
ｎおよびｋが２以上の整数、Ｎ＝ｎＣｋ−１であり、シード値ｓ０，…，ｓＮ−１を得るシード部と、
前記シード値ｓ０，…，ｓＮ−１それぞれの関数値ａ０，…，ａＮ−１と入力値ａとに対する関数値ａ’を得る演算部と、
Ｐｓｅｔがｎ個の元Ｐ（０），…，Ｐ（ｎ−１）からなる集合、Ｐｓｕｂ（ｊ）が前記集合Ｐｓｅｔに属するｎ−ｋ＋１個の元からなる部分集合であり、前記部分集合Ｐｓｕｂ（ｊ）に属する元Ｐ（ｉ）に対し、前記関数値ａ’の分散値ａｉ’と前記シード値ｓｊとを含む分散値Ｔ（ｉ）を得る分散値生成部と、
を有する分散管理装置。
【請求項２】
請求項１の分散管理装置であって、
前記入力値ａに対応する誤り検出符号ｂを得る誤り検出符号部と、
シード値ｅ０，…，ｅＮ−１を得る第２シード部と、
前記シード値ｅ０，…，ｅＮ−１それぞれの関数値ｂ０，…，ｂＮ−１と前記誤り検出符号ｂとに対する関数値ｂ’を得る第２演算部と、
前記部分集合Ｐｓｕｂ（ｊ）に属する元Ｐ（ｉ）に対し、前記関数値ｂ’の分散値ｂｉ’と前記シード値ｅｊとを含む分散値Ｅ（ｉ）を得る第２分散値生成部と、
を有する分散管理装置。
【請求項３】
ｎおよびｋが２以上の整数、Ｎ＝ｎＣｋ−１であり、分散値であるシード値ｓ０，…，ｓＮ−１それぞれの関数値ａ０，…，ａＮ−１を得る演算部と、
分散値ａｉ’の復元値ａ’と前記関数値ａ０，…，ａＮ−１とに対する関数値である復元値ａを得る復元部と、
を有する復元装置。
【請求項４】
請求項３の復元装置であって、
分散値であるシード値ｅ０，…，ｅＮ−１それぞれの関数値ｂ０，…，ｂＮ−１を得る第２演算部と、
分散値ｂｉ’の復元値ｂ’と前記関数値ｂ０，…，ｂＮ−１とに対する関数値である復元値ｂを得る第２復元部と、
前記復元値ｂを用いて前記復元値ａを検証する検証部と、
を有する復元装置。
【請求項５】
ｎおよびｋが２以上の整数、Ｐｓｅｔがｎ個のパーティ装置Ｐ（０），…，Ｐ（ｎ−１）からなる集合、Ｐｓｕｂ（ｊ）が前記集合Ｐｓｅｔに属するｎ−ｋ＋１個のパーティ装置からなる部分集合であり、前記部分集合Ｐｓｕｂ（ｊ）に属するパーティ装置Ｐ（ι）には、シード値ｓｊを含む分散値Ｔ（ι）が与えられており、
前記部分集合Ｐｓｕｂ（ｊ）に属し、
前記パーティ装置Ｐ（ι）から提供されたシード値ｓｊが入力される入力部と、
入力された前記シード値ｓｊを含む復旧分散値Ｔ’（Ｉ）を得る復旧部と、
を有するパーティ装置。
【請求項６】
請求項５のパーティ装置であって、
前記パーティ装置Ｐ（ι）には、さらにシード値ｅｊを含む分散値Ｅ（ｉ）が与えられており、
前記パーティ装置Ｐ（ι）から提供されたシード値ｅｊが入力される第２入力部と、
入力された前記シード値ｅｊを含む復旧分散値Ｅ’（Ｉ）を得る第２復旧部と、
を有するパーティ装置。
【請求項７】
請求項６のパーティ装置であって、
当該パーティ装置に与えられていた分散値Ｔ（Ｉ）と分散値Ｅ（Ｉ）とに対応する復旧誤り検出符号Ｂ（Ｉ）が分散された分散値Ｂｉ（Ｉ）が、前記集合Ｐｓｅｔに属するパーティ装置Ｐ（ｉ）に与えられており、
前記分散値Ｂｉ（Ｉ）の復元値である前記復旧誤り検出符号Ｂ（Ｉ）を得る第３復元部と、
前記復旧誤り検出符号Ｂ（Ｉ）を用いて前記復旧分散値Ｔ’（Ｉ）と前記復旧分散値Ｅ’（Ｉ）とを検証する第２検証部と、
を有するパーティ装置。
【請求項８】
ｎおよびｋが２以上の整数、Ｐｓｅｔがｎ個のパーティ装置Ｐ（０），…，Ｐ（ｎ−１）からなる集合、Ｐｓｕｂ（ｊ）が前記集合Ｐｓｅｔに属するｎ−ｋ＋１個のパーティ装置からなる部分集合であり、
前記部分集合Ｐｓｕｂ（ｊ）に属し、
シード値ｓｊを含む分散値Ｔ（ι）が格納された記憶部と、
前記シード値ｓｊを前記部分集合Ｐｓｕｂ（ｊ）に属する他のパーティ装置Ｐ（Ｉ）に対して出力する出力部と、
を有するパーティ装置。
【請求項９】
請求項８のパーティ装置であって、
シード値ｅｊを含む分散値Ｅ（ｉ）が格納された第２記憶部と、
前記シード値ｅｊを前記他のパーティ装置Ｐ（Ｉ）に対して出力する第２出力部と、
を有するパーティ装置。
【請求項１０】
ｎおよびｋが２以上の整数、Ｐｓｅｔがｎ個のパーティ装置Ｐ（０），…，Ｐ（ｎ−１）からなる集合であり、Ｐｓｕｂ（ｊ）が前記集合Ｐｓｅｔに属するｎ−ｋ＋１個のパーティ装置からなる部分集合であり、
前記部分集合Ｐｓｕｂ（ｊ）に属し、
分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）が格納された記憶部と、
前記分散値ａｉ’の復元値ａ’と前記シード値ｓｊの関数値ａｊとに対する準同型関数値ｚｊを得る第２関数部と、
を有するパーティ装置。
【請求項１１】
ｎおよびｋが２以上の整数、Ｐｓｅｔがｎ個のパーティ装置からなる集合、Ｐｓｕｂ（ｊ）が前記集合Ｐｓｅｔに属するｎ−ｋ＋１個のパーティ装置からなる部分集合、Ｎ＝ｎＣｋ−１であり、
前記部分集合Ｐｓｕｂ（ｊ）に属し、
分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）が格納された記憶部と、
前記シード値ｓｊの関数値と前記部分集合Ｐｓｕｂ（ｊ）で共有された新たなシード値ｓｊ’の関数値とに対する関数値ｄｊを得る第３関数部と、
前記関数値ｄｊを分散して分散値ｄｊ，０，…，ｄｊ，ｎ−１を得る分散部と、
前記分散値ａｉ’の復元値ａ’と前記分散値ｄ０，ｉ，…，ｄＮ−１，ｉとに対する関数値である分散値αｉを得る第４関数部と、
前記分散値αｉの復元値ａ’’の分散値ａｉ’’と前記シード値ｓｊ’とを含む分散値Ｔ’（ｉ）を得る再分散部と、
を有するパーティ装置。
【請求項１２】
請求項１１のパーティ装置であって、
２ｋ−１≦ｎ、αｉが前記分散値ａｉ’の復元値ａ’と前記分散値ｄ０，ｉ，…，ｄＮ−１，ｉとに対する関数値である分散値であり、
ｎ個の分散値α０，…，αｎ−１のうちｋ個を用いて前記復元値ａ’’を得る第４復元部と、
前記分散値α０，…，αｎ−１のうち前記復元値ａ’’を得るために用いられなかったものを前記復元値ａ’’の誤り検出符号とする第２誤り検出符号部と、
を有するパーティ装置。
【請求項１３】
請求項１０から１２の何れかのパーティ装置であって、
２ｋ−１≦ｎであり、前記復元値ａ’がｎ個の分散値ａ０’，…，ａｎ−１’に分散されており、
前記分散値ａ０’，…，ａｎ−１’のうちｋ個を用いて前記復元値ａ’を得る第５復元部と、
前記分散値ａ０’，…，ａｎ−１’のうち前記復元値ａ’を得るために用いられなかったものを前記復元値ａ’の誤り検出符号とする第３誤り検出符号部と、
を有するパーティ装置。
【請求項１４】
請求項１もしくは２の分散管理装置、または、請求項３もしくは４の復元装置としてコンピュータを機能させるためのプログラム。
【請求項１５】
請求項５から１３の何れかのパーティ装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを秘匿しつつデータ処理を行うための秘密分散技術に関する。
【背景技術】
【０００２】
秘匿計算（ＭＰＣ：Multi-Party Computation）のための従来技術として、非特許文献１に記載されたショート秘密分散がある。この技術では、ｋ−１個（ただしｋ≧２）のシード値ｓ１，…，ｓｋ−１にそれぞれ擬似乱数生成関数を作用させて擬似乱数ｆａ（１），...，ｆａ（ｋ−１）を得、擬似乱数ｆａ（１），...，ｆａ（ｋ−１）と入力データとに対応する１個の対応値ｆａ（ｋ）を得、シード値ｓ１，…，ｓｋ−１および対応値ｆａ（ｋ）をそれぞれ任意の（ｋ，ｎ）秘密分散によって分散し（ただしｎ≧２）、ｋ個ずつの分散値からなる組を第１分散値とする。この方式はデータ効率がよく、秘匿計算も行うことができるという特徴がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】千田浩司，五十嵐大，菊池亮，濱田浩気，“計算量的秘密分散およびランプ型秘密分散のマルチパーティ計算拡張”，In CSEC58，2012.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１の方式は、秘匿計算を行うために必要な情報の受け渡し量が大きいという問題点がある。
【０００５】
準同型性を持つ秘密分散の場合、各分散値をそのまま用いた秘匿計算を行うことができる。しかしながら、擬似乱数生成関数は準同型性を持たず、非特許文献１の方式では、第１分散値をそのまま用いた秘匿計算を行うことはできない。そのため、秘匿計算を始める前に第１分散値から準同型性を持つ秘密分散の第２分散値への変換（分散情報変換）を行う必要がある。従来の分散情報変換では、第１分散値からシード値ｓ１，…，ｓｋ−１および対応値ｆａ（ｋ）が復元され、シード値ｓ１，…，ｓｋ−１からｆａ（１），...，ｆａ（ｋ−１）が得られる。その後、各計算装置Ｐρ（ただしρ＝１，...，ｋ）が、準同型性を持つ秘密分散によってｆａ（ρ）を分散し、それによって得た分散値ｆｓρ（η）（ただし、η＝１，...，ｎ）を他の計算主体Ｐ（η）に送り、各計算主体Ｐηが、分散値ｆｓ１（η），...，ｆｓｋ（η）を用いて第２分散値を得る。
【０００６】
このように非特許文献１の方式では、秘匿計算を始める前に、ｋ個の計算主体Ｐρのそれぞれがｎ−１個の分散値ｆｓρ（δ）（ただし、δ＝１，...，ｎかつδ≠ρ）を他のｎ−１個の計算主体Ｐδに提供する必要があり、合計ｋ×（ｎ−１）個の分散値の受け渡しが必要となる。
【０００７】
本発明はこのような点に鑑みてなされたものであり、安全性を確保しつつ、秘匿計算を行うために必要な情報の受け渡し量を削減する技術を提供する。
【課題を解決するための手段】
【０００８】
本発明では、シード値ｓ０，…，ｓＮ−１を得、シード値ｓ０，…，ｓＮ−１それぞれの関数値ａ０，…，ａＮ−１と入力値ａとに対する関数値ａ’を得、部分集合Ｐｓｕｂ（ｊ）に属する元Ｐ（ｉ）に対し、関数値ａ’の分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）を得る。ただし、ｎおよびｋが２以上の整数、Ｎ＝ｎＣｋ−１、Ｐｓｅｔがｎ個の元Ｐ（０），…，Ｐ（ｎ−１）からなる集合、Ｐｓｕｂ（ｊ）が集合Ｐｓｅｔに属するｎ−ｋ＋１個の元からなる部分集合である。
【発明の効果】
【０００９】
本発明では、部分集合Ｐｓｕｂ（ｊ）に属する元Ｐ（ｉ）に対し、関数値ａ’の分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）を得る。分散値Ｔ（ｉ）がシード値ｓｊそのものを含むため、秘匿計算を行うために必要な情報の受け渡し量を削減できる。さらに分散値Ｔ（ｉ）がすべてのシード値を含むわけではないため、安全性も確保できる。
【図面の簡単な説明】
【００１０】
【図１】図１は、第１，２実施形態の秘密分散システムの構成を説明するための図である。
【図２】図２Ａは、第１，２実施形態の分散装置の構成を説明するためのブロック図である。図２Ｂは、第１，２実施形態の復元装置の構成を説明するためのブロック図である。
【図３】図３は、第１，２実施形態のパーティ装置の構成を説明するためのブロック図である。
【図４】図４は、パーティ装置Ｐ（０），…，Ｐ（２）と集合Ｐｓｅｔとる部分集合Ｐｓｕｂ（０），…，Ｐｓｕｂ（０）との関係を例示するための概念図である。
【図５】図５Ａは、第１実施形態の分散方法を説明するためのフロー図である。図５Ｂは、第１実施形態の復元方法を説明するためのフロー図である。
【図６】図６Ａおよび図６Ｂは、第１実施形態の復旧方法を説明するためのフロー図である。
【図７】図７Ａは、第１実施形態の分散情報変換方法を説明するためのフロー図である。図７Ｂは、第１実施形態の再分散方法を説明するためのフロー図である。
【図８】図８は、第２実施形態の分散方法を説明するためのフロー図である。
【図９】図９は、第２実施形態の復元方法を説明するためのフロー図である。
【図１０】図１０Ａおよび図１０Ｂは、第２実施形態の復旧方法を説明するためのフロー図である。
【図１１】図１１Ａは、第２実施形態の分散情報変換方法を説明するためのフロー図である。図１１Ｂは、第２実施形態の再分散方法を説明するためのフロー図である。
【発明を実施するための形態】
【００１１】
本発明の実施形態を説明する。
＜定義＞
各実施形態で用いる記号や用語を定義する。
（ｋ，ｎ）−秘密分散は、データをｎ個の分散値（シェア）に分散し、分散値がｋ個以上あればデータを完全に復元できるデータ分散方法である。ただし、ｎおよびｋが２以上の整数であり、ｎ≧ｋである。（ｋ，ｎ）−秘密分散は、ｋ個未満の分散値からはデータに関する一切の情報を得ることができないという安全性をもつ。分散値を生成して提供する装置をディーラー装置と呼び、各分散値を保持する装置をパーティ装置とよぶ。
【００１２】
加法準同型（ｋ，ｎ）−秘密分散は、分散されたデータ上で、元のデータの秘匿性を保ったまま、他のパーティ装置と情報の受け渡しなしで加算を行うことができる（ｋ，ｎ）−秘密分散である。加法準同型（ｋ，ｎ）−秘密分散としては、Ｓｈａｍｉｒの秘密分散が有名である。加法準同型（ｋ，ｎ）−秘密分散では、パーティ装置間で情報のやり取りを行うことで秘匿計算を行うことができる。
【００１３】
（ｋ，ｎ）−ＩＤＡは、（ｋ，ｎ）−秘密分散から上述の安全性の要件を取り除いた方式である。つまり（ｋ，ｎ）−ＩＤＡでも、分散値がｋ個以上あればデータを完全に復元することができる。ただし（ｋ，ｎ）−ＩＤＡでは、ｋ個未満の分散値からデータに関する一切の情報を得ることができないことは保証されない。
【００１４】
以下に（ｋ，ｎ）−ＩＤＡの一例として、多項式ベースの方式を示す。
１．パーティ装置Ｐ（０）の公開パラメータをχ０、・・・、パーティ装置Ｐ（ｎ−１）の公開パラメータをχｎ−１とする。
２．ディーラー装置は、分散対象のデータβ０，...，βｎ―１に対して、ｆ（ｘ）＝β０＋β１χ＋β２χ２＋...＋βｋ−１χｋ−１とする。
３．ディーラー装置は、パーティ装置Ｐ（０）に分散値ｆ（χ０）、・・・、パーティ装置Ｐ（ｎ−１）に分散値ｆ（χｎ−１）を分散する。
任意のｋ個の分散値を得たディーラー装置は、それらの線形結合によって各データβ０，...，βｎ―１を復元できる。
【００１５】
複製型秘密分散は、以下のような（ｋ，ｎ）−秘密分散である。
１．ｎ個のパーティ装置Ｐ（０）,...,Ｐ（ｎ−１）のうち、任意のｎ−ｋ＋１個のパーティ装置からなる部分集合Ｐｓｕｂ（ｊ）を考える。このような部分集合はＮ＝ｎＣｋ−１個存在する。
２．ディーラー装置は、ν＝０,...,Ｎ−２について乱数βνを生成する。
３．ディーラー装置は、分散対象のデータβに対し、βＮ−１＝β−Σν∈｛０,...,Ｎ−２｝βνとする。ただし、Σν∈｛０,...,Ｎ−２｝βνは、β０＋β１＋・・・＋βＮ−２を表す。
４．各部分集合Ｐｓｕｂ（ｊ）に属する各パーティ装置Ｐ（ｉ）にβｊを提供する。ただしｊ＝０,...,Ｎ−１である。各パーティ装置Ｐ（ｉ）は、ｎ−１Ｃｋ−１個の部分集合Ｐｓｕｂ（ｊ）に属し、ｎ−１Ｃｋ−１個のβｊからなる列を分散値として保持する。
５．任意のｋ個のパーティ装置から集めた分散値は必ずβ０,...,βＮ−２,βＮ−１を含み、β＝Σｊ∈｛０,...,Ｎ−１｝βｊによってデータβを復元できる。
例えば（２,３）−秘密分散とする場合、ディーラー装置は、分散対象のデータβをβ＝β０＋β１＋β２と分割し、パーティ装置Ｐ（０）に分散値（β０,β１）を、パーティ装置Ｐ（１）に分散値（β１,β２）を、パーティ装置Ｐ（２）に分散値（β２,β０）をそれぞれ提供する。任意の２個のパーティ装置から集めた分散値は必ずβ０,β１,β２を含み、β＝β０＋β１＋β２によってデータβを復元できる。
【００１６】
［ｘ］は、値ｘを秘密分散して得られた分散値を表す。集合Ｘに対する［Ｘ］は、集合Ｘの元を秘密分散して得られた分散値の集合を表す。
【００１７】
各実施形態では、秘密分散の基本操作であるデータの分散および復元の他に、復旧、分散情報変換、および再分散を行う。分散および復元は、ディーラー装置が行い、復旧、分散情報変換、および再分散は、パーティ装置が行う。
【００１８】
復旧は、ｋ個以上のパーティ装置を利用し、秘匿性を失うことなく、他の何れかのパーティ装置の分散値を再構築する処理である。例えば、一部のパーティ装置が利用不能になり分散値が失われたような場合に、少なくともｋ個のパーティ装置が利用可能であれば、復旧によって、秘匿性を失うことなく当該利用不能となったパーティ装置の分散値を再構築できる。
【００１９】
分散情報変換は、秘密分散方式が準同型性を持たず、各分散値をそのまま用いた秘匿計算を行うことができない場合に、秘匿性を失うことなく、各分散値を準同型性を持つ秘密分散の分散値に変換する処理である。
【００２０】
再分散は、秘匿性を失うことなく、秘密分散をやり直す処理である。例えば、ｋ個未満のγ個の分散値（例えば、γ＝ｋ−１）が漏洩した場合、他のｋ−γ個の分散値がさらに漏洩すると秘匿性が破られてしまう。このような場合に再分散を行えば、その後に再分散後の分散値がｋ−γ個漏洩したとしても、秘匿性は破られない。
【００２１】
＜第１実施形態＞
第１実施形態を説明する。
《全体構成》
図１に例示するように、本形態の秘密分散システム１は、分散管理装置１１、復元装置１２、およびパーティ装置１３−０,・・・,１３−（ｎ−１）を有し、ネットワーク１４を通じて情報の受け渡しが可能なように構成されている。分散管理装置１１および復元装置１２はディーラー装置に相当する。本形態では、分散管理装置１１と復元装置１２とが別の装置であるが、分散管理装置１１と復元装置１２とが一体であってもよい。パーティ装置１３−０,・・・,１３−（ｎ−１）（パーティ装置Ｐ（０），…，Ｐ（ｎ−１））を元とする集合をＰｓｅｔ＝｛Ｐ（０），…，Ｐ（ｎ−１）｝とする。集合Ｐｓｅｔに属するｎ−ｋ＋１個の元からなる部分集合をＰｓｕｂ（ｊ）⊂Ｐｓｅｔとする。このような部分集合Ｐｓｕｂ（ｊ）はＮ＝ｎＣｋ−１個存在し、ｊ＝０，…，Ｎ−１とする。ｎおよびｋは２以上の整数である。図４は、ｎ＝３，ｋ＝２の場合の集合Ｐｓｅｔおよび部分集合Ｐｓｕｂ（ｊ）を例示しており、この例ではＰｓｕｂ（０）＝｛Ｐ（０），Ｐ（１）｝、Ｐｓｕｂ（１）＝｛Ｐ（１），Ｐ（２）｝、Ｐｓｕｂ（２）＝｛Ｐ（２），Ｐ（０）｝である。
【００２２】
《分散管理装置》
図２Ａに例示するように、本形態の分散管理装置１１は、入力部１１１とシード部１１２と関数部１１３と演算部１１４と分散部１１５と分散値生成部１１６と出力部１１７と記憶部１１８と制御部１１９とを有する。
【００２３】
《復元装置》
図２Ｂに例示するように、本形態の復元装置１２は、入力部１２１と復元部１２２，１２４と演算部１２３と出力部１２５と記憶部１２８と制御部１２９とを有する。
【００２４】
《パーティ装置》
図３に例示するように、各パーティ装置１３−ｉ（ただし、ｉ＝０，...，ｎ−１）は、提供部１３１−ｉと出力部１３２−ｉと入力部１３３−ｉと復旧部１３４−ｉと記憶部１３５−ｉと復元部１３６−ｉ，１３１４−ｉと関数部１３７−ｉ，１３８−ｉ，１３１０−ｉ，１３１３−ｉとシード部１３９−ｉと分散部１３１１−ｉと制御部１３１９−ｉとを有する。
【００２５】
本形態の分散管理装置１１、復元装置１２、およびパーティ装置１３−ｉは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。復元装置１２、およびパーティ装置１３−ｉは、それぞれ、制御部１１９，１２９，１３１９−ｉの制御のもとで各処理を実行する。入力データや各処理で得られたデータは、それぞれ記憶部１１８，１２９，１３５−ｉに格納され、必要に応じて読み出されて各処理に利用される。
【００２６】
《分散》
図５Ａを用いて、本形態の分散を説明する。
分散管理装置１１（図２Ａ）の入力部１１１に環Ｒの元である入力値ａ∈Ｒが入力され、演算部１１４に送られる（ステップＳ１１１）。
【００２７】
シード部１１２は、Ｎ個のシード値ｓ０，…，ｓＮ−１∈Ｓを生成して出力する。例えば、シード部１１２は、Ｎ個の乱数をシード値ｓ０，…，ｓＮ−１とする。ただし、Ｓはシード値が採りうる値の空間（集合）である。どのような空間Ｓが選ばれてもよい。シード値ｓ０，…，ｓＮ−１は、関数部１１３および分散値生成部１１６に送られる（ステップＳ１１２）。
【００２８】
関数部１１３は、シード値ｓ０，…，ｓＮ−１および所定の擬似乱数生成関数Ｆ：Ｓ→Ｒを用い、各ｊ＝０，…，Ｎ−１に対してａｊ＝Ｆ（ｓｊ）∈Ｒを計算して出力する。得られた関数値（擬似乱数）ａ０＝Ｆ（ｓ０），…，ａＮ−１＝Ｆ（ｓＮ−１）は、演算部１１４に送られる（ステップＳ１１３）。
【００２９】
演算部１１４は、入力値ａと関数値ａ０＝Ｆ（ｓ０），…，ａＮ−１＝Ｆ（ｓＮ−１）とに対する関数値ａ’＝Ｇ（ａ，ａ０，…，ａＮ−１）∈Ｒを計算して出力する。ただし、Ｇは環ＲのＮ＋１個の元を入力として環の１個の元を出力する所定の関数Ｇ：ＲＮ＋１→Ｒである。例えば、Ｇは環ＲのＮ＋１個の元を入力とし、入力された元の加算および／または入力された元の逆元の加算を行う準同型関数である。関数値ａの具体例は、ａ’＝ａ−Σｊ∈｛０，...，Ｎ−１｝ａｊ＝ａ−ａ０＋ａ１＋…＋ａＮ−１などである。関数値ａ’は分散部１１５に送られる（ステップＳ１１４）。
【００３０】
分散部１１５は、（ｋ，ｎ）−ＩＤＡによって関数値ａ’を分散し、ｎ個の分散値ａ０’，…，ａｎ−１’を得て出力する。分散値ａ０’，…，ａｎ−１’は分散値生成部１１６に入力される（ステップＳ１１５）。分散値生成部１１６は、前述した部分集合Ｐｓｕｂ（ｊ）に属する元である各パーティ装置１３−ｉ（すなわちＰ（ｉ））に対し、それぞれ分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）を得て出力する。ただし、ｉ＝０，…，ｎ−１である。すなわち、各パーティ装置１３−ｉに対し、分散値ａｉ’とシード列Ｓｉ＝｛ｓｊ∈Ｓ｜Ｐ（ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝とを含む分散値Ｔ（ｉ）を得て出力する。分散値Ｔ（ｉ）は、分散値ａｉ’とシード列Ｓｉのみを含んでいてもよいし、さらに共通パラメータ等のその他の情報を含んでいてもよい。ｎ個の分散値Ｔ（０），…，Ｔ（ｎ−１）は、出力部１１７に送られる（ステップＳ１１６）。
【００３１】
出力部１１７は、各分散値Ｔ（ｉ）を各パーティ装置１３−ｉに対して出力する。分散値Ｔ（ｉ）は、パーティ装置１３−ｉの入力部１３３−ｉに入力され、記憶部１３５−ｉに格納される。このように各パーティ装置１３−ｉに分散値Ｔ（ｉ）が与えられる（ステップＳ１１７）。
【００３２】
《復元》
図５Ｂを用いて、本形態の復元を説明する。
任意のｋ個の分散値Ｔ（φ（０）），…，Ｔ（φ（ｋ−１））が、復元装置１２（図２Ｂ）の入力部１２１に入力される。ただし、｛φ（０），…，φ（ｋ−１）｝⊂｛０，…，ｎ−１｝である。分散値Ｔ（φ（０）），…，Ｔ（φ（ｋ−１））が含む分散値ａφ（０）’，…，ａφ（ｋ−１）’は復元部１２２に送られ、シード列Ｓφ（０），…，Ｓφ（ｋ―１）は演算部１２３に送られる（ステップＳ１２１）。
【００３３】
復元部１２２は、（ｋ，ｎ）−ＩＤＡの復元方式によって、ｋ個の分散値ａφ（０）’，…，ａφ（ｋ−１）’からａ’を復元して出力する。復元値ａ’は復元部１２４に送られる（ステップＳ１２２）。
【００３４】
演算部１２３は、シード列Ｓφ（０），…，Ｓφ（ｋ―１）に含まれるＮ個のシード値ｓ０，…，ｓＮ−１および前述の擬似乱数生成関数Ｆを用い、関数値ａ０＝Ｆ（ｓ０），…，ａＮ−１＝Ｆ（ｓＮ−１）を計算して出力する。シード列Ｓφ（０），…，Ｓφ（ｋ―１）からなる集合は、必ずすべてのシード値ｓ０，…，ｓＮ−１を含む。関数値ａ０，…，ａＮ−１は復元部１２４に送られる（ステップＳ１２３）。
【００３５】
復元部１２４は、復元値ａ’と関数値ａ０，…，ａＮ−１とに対する関数値である復元値ａ＝Ｄ（ａ’，ａ０，…，ａＮ−１）を計算して出力する。ただし、Ｄは環ＲのＮ＋１個の元を入力として環の１個の元を出力する所定の関数Ｄ：ＲＮ＋１→Ｒであり、例えば、Ｄは準同型関数であり、前述の関数Ｇに対応する。すなわち、ＧおよびＤは、ａ’＝Ｇ（ａ，ａ０，…，ａＮ−１）およびａ＝Ｄ（ａ’，ａ０，…，ａＮ−１）の関係を満たす。例えば、ａ’＝ａ−Σｊ∈｛０，...，Ｎ−１｝ａｊである場合、ａ＝ａ’＋Σｊ∈｛０，...，Ｎ−１｝ａｊである。復元値ａは出力部１２５に送られる（ステップＳ１２４）。出力部１２５は復元値ａを出力する。
【００３６】
《復旧》
図６Ａおよび６Ｂを用いて、本形態の復旧を説明する。以下では、ｋ個のパーティ装置１３−ιで、１個のパーティ装置１３−Ｉに格納された分散値Ｔ（Ｉ）を復旧する例を示す。ただし、ι＝ν（０），…，ν（ｋ−１）、｛ν（０），…，ν（ｋ−１）｝⊂｛０，…，ｎ−１｝、Ｉ∈｛０，…，ｎ−１｝である。
【００３７】
図６Ａに例示するように、パーティ装置１３−Ｉが属する部分集合Ｐｓｕｂ（ｊ）（ただし０≦ｊ＜Ｎ）に属するパーティ装置１３−ι（すなわちＰ（ι）∈Ｐｓｕｂ（ｊ））の提供部１３１−ι（図３）が、記憶部１３５−ιに格納された分散値Ｔ（ι）が含むシード列Ｓιのシード値ｓｊを抽出する。シード値ｓｊは出力部１３２−ιに送られる。出力部１３２−ιは、シード値ｓｊをパーティ装置１３−Ｉに対して出力する（ステップＳ１３１）。
【００３８】
ｋ個のパーティ装置１３−ν（０），…，１３−ν（ｋ−１）が協力し、パーティ装置１３−Ｉの分散値ａＩ’を再構築する。例えば、パーティ装置１３−ν（０），…，１３−ν（ｋ−１）の提供部１３１−ν（０），…，１３１−ν（ｋ−１）が、記憶部１３５−ν（０），…，１３５−ν（ｋ−１）から読み出した分散値ａν（１）’，…，ａν（ｋ−１）’を用い、情報のやり取りを行って分散値ａＩ’を再構築する（例えば、参考文献１「Michael O. Rabin, “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance,” Journal of the ACM, vol. 36, no. 2, pp. 355-348, 1989.」参照）。あるいは、（ｋ，ｎ）−ＩＤＡとして前述の多項式ベースの方式（ただし、関数値ａ’をｎ個に分割したものをβ０，...，βｎ―１とする）が用いる場合、以下のように分散値ａＩ’が再構築できる。パーティ装置１３−ν（１），…，１３−ν（ｋ−１）の提供部１３１−ν（１），…，１３１−ν（ｋ−１）が、記憶部１３５−ν（１），…，１３５−ν（ｋ−１）から分散値ａν（１）’，…，ａν（ｋ−１）’を読み出し、出力部１３２−ν（１），…，１３２−ν（ｋ−１）がそれらをパーティ装置１３−ν（０）に対して出力する。パーティ装置１３−ν（０）の提供部１３１−ν（０）は、前述の多項式ベースの（ｋ，ｎ）−ＩＤＡに則って、記憶部１３５−ν（０）から読み出した分散値ａν（０）’とパーティ装置１３−ν（１），…，１３−ν（ｋ−１）から出力された分散値ａν（１）’，…，ａν（ｋ−１）’とから、Ｌａｇｒａｎｇｅ補完によって分散値ａＩ’＝ｆ（χＩ）を復元する（ステップＳ１３２）。
【００３９】
何れかのパーティ装置１３−ιの出力部１３２−ιが、復元された分散値ａＩ’をパーティ装置１３−Ｉに対して出力する（ステップＳ１３３）。
【００４０】
図６Ｂに例示するように、ステップＳ１３１で各パーティ装置１３−ιから出力された各シード値ｓｊが、パーティ装置１３−Ｉ（図３）の入力部１３３−Ｉに入力され、これらのシード値ｓｊから構成されるシード列ＳＩ＝｛ｓｊ∈Ｓ｜Ｐ（Ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝が復旧部１３４−Ｉに送られる（ステップＳ１４１）。
【００４１】
ステップＳ１３３で何れかのパーティ装置１３−ιから出力された分散値ａＩ’が、パーティ装置１３−Ｉの入力部１３３−Ｉに入力され、復旧部１３４−Ｉに送られる（ステップＳ１４２）。
【００４２】
復旧部１３４−Ｉは、分散値ａＩ’とシード列ＳＩとを含む復旧分散値Ｔ’（Ｉ）を生成し、これを新たな分散値Ｔ（Ｉ）として記憶部１３５−Ｉに格納する（ステップＳ１４３）。
【００４３】
《分散情報変換》
次に、図７Ａを用いて、本形態の分散情報変換を説明する。
ｎ個のパーティ装置１３−ｉ（図３）の関数部１３７−ｉが、それぞれ、記憶部１３５−ｉから分散値Ｔ（ｉ）が含むシード列Ｓｉを読み出し、シード列Ｓｉが含む各シード値ｓｊおよび擬似乱数生成関数Ｆを用い、各関数値ａｊ＝Ｆ（ｓｊ）（ただし、ｓｊ∈Ｓｉ）を計算して出力する。関数値ａｊは、複製型秘密分散によってΣｊ∈｛０，...，Ｎ−１｝ａｊを分散して得られる分散値［Σｊ∈｛０，...，Ｎ−１｝ａｊ］となっている。各関数値ａｊは、各関数部１３８−ｉに送られる（ステップＳ１５１）
【００４４】
何れかのパーティ装置１３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部１３６−Ｉに、任意のｋ個のパーティ装置１３−ν（０），…，１３−ν（ｋ−１）の分散値ａν（０）’，…，ａν（ｋ−１）’が送られる。ただし、｛ν（０），…，ν（ｋ−１）｝⊂｛０，…，ｎ−１｝である。復元部１３６−Ｉは（ｋ，ｎ）−ＩＤＡの復元方式によって、分散値ａν（０）’，…，ａν（ｋ−１）’からａ’を復元し、復元値ａ’を出力する。復元値ａ’はパーティ装置１３−Ｉの出力部１３２−Ｉから、その他すべてのパーティ装置１３−０，…，１３−（ｎ−１）に対して出力される。復元値ａ’は、すべてのパーティ装置１３−０，…，１３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｎ−１）に格納される（ステップＳ１５２）。
【００４５】
ｎ個のパーティ装置１３−ｉの関数部１３８−ｉは、それぞれ、関数部１３７−ｉから送られた各関数値ａｊと、記憶部１３５−ｉから読み出した復元値ａ’とに対する準同型関数値ｚｊ＝Ｄ（ａ’，ａｊ）を計算して出力する。例えば、ａ’＝ａ−Σｊ∈｛０，...，Ｎ−１｝ａｊである場合、関数部１３８−ｉは、ｚｊ＝ａ’＋ａｊやｚｊ＝ａ’／Ｎ＋ａｊなどを計算して出力する（ステップＳ１５３）。
【００４６】
《再分散》
次に、図７Ｂを用いて、本形態の再分散を説明する。
各部分集合Ｐｓｕｂ（ｊ）に属する何れかのパーティ装置１３−υ（ｊ）（ただし、Ｐ（υ（ｊ））∈Ｐｓｕｂ（ｊ）、０≦υ（ｊ）＜ｎ、ｊ＝０，…，Ｎ−１）のシード部１３９−υ（ｊ）が、それぞれ、当該部分集合Ｐｓｕｂ（ｊ）で共有する新たなシード値ｓｊ’∈Ｓを生成して出力する。新たなシード値ｓｊ’の例は乱数である。新たなシード値ｓｊ’は、部分集合Ｐｓｕｂ（ｊ）に属するすべてのパーティ装置１３−ｉ（ただし、Ｐ（ｉ）∈Ｐｓｕｂ（ｊ））の記憶部１３５−ｉに格納される（ステップＳ１６１）。
【００４７】
関数部１３１０−υ（ｊ）は、記憶部１３５−υ（ｊ）に格納されたシード値ｓｊおよび新たなシード値ｓｊ’ならびに擬似乱数生成関数Ｆを用い、シード値ｓｊの関数値Ｆ（ｓｊ）と新たなシード値ｓｊ’の関数値Ｆ（ｓｊ’）とに対する関数値ｄｊ＝Ｈ（Ｆ（ｓｊ），Ｆ（ｓｊ’））を計算して出力する。例えば、Ｈ：Ｒ２→Ｒは準同型関数であり、関数値ｄｊの例はｄｊ＝Ｆ（ｓｊ）−Ｆ（ｓｊ’）である。関数値ｄｊは分散部１３１１−υ（ｊ）に送られる（ステップＳ１６２）。
【００４８】
分散部１３１１−υ（ｊ）は、（ｋ，ｎ）−秘密分散によって関数値ｄｊを分散し、分散値［ｄｊ］＝ｄｊ，０，…，ｄｊ，ｎ−１を生成して出力する。分散値ｄｊ，υ（ｊ）は記憶部１３５−υ（ｊ）に格納され、その他の分散値ｄｊ，ｉは、出力部１３２−υ（ｊ）から出力され、パーティ装置１３−ｉの記憶部１３５−ｉに格納される（ステップＳ１６３）。
【００４９】
何れかのパーティ装置１３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部１３６−Ｉに、任意のｋ個のパーティ装置１３−ν（０），…，１３−ν（ｋ−１）の分散値ａν（０）’，…，ａν（ｋ−１）’が送られる。復元部１３６−Ｉは、（ｋ，ｎ）−ＩＤＡの復元方式によって、分散値ａν（０）’，…，ａν（ｋ−１）’から復元値ａ’を計算して出力する。出力部１３２−Ｉは、復元値ａ’を他のすべてのパーティ装置１３−０，…，１３−（ｎ−１）に対して出力する。復元値ａ’は、すべてのパーティ装置１３−０，…，１３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｋ−１）に入力されて格納される（ステップＳ１６４）。
【００５０】
各パーティ装置１３−ｉ（ただし、ｉ＝０，…，ｎ−１）の関数部１３１３−ｉは、記憶部１３５−ｉから読み出した復元値ａ’と分散値ｄ０，ｉ，…，ｄＮ−１，ｉとに対する関数値である分散値αｉ＝Ｑ（ａ’，ｄ０，ｉ，…，ｄＮ−１，ｉ）∈Ｒを計算して出力する。Ｑは環ＲのＮ＋１個の元を入力として環の１個の元を出力する所定の関数Ｑ：ＲＮ＋１→Ｒである。関数Ｑは、ステップＳ１６３で用いた（ｋ，ｎ）−秘密分散によってａ’’＝Ｇ（ａ，ａ０’，…，ａＮ−１’）を分散して得られる分散値［ａ’’］が分散値αｉとなる関数である。ただし、ａ０’＝Ｆ（ｓ０’），…，ａＮ−１’＝Ｆ（ｓＮ−１’）である。例えば、ａ’＝ａ−Σｊ∈｛０，...，Ｎ−１｝ａｊかつｄｊ＝Ｆ（ｓｊ）−Ｆ（ｓｊ’）である場合、αｉ＝ａ’＋Σｊ∈｛０，...，Ｎ−１｝ｄｊ，ｉである（ステップＳ１６５）。
【００５１】
何れかのパーティ装置１３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部１３１４−Ｉに、任意のｋ個のパーティ装置１３−ν（０），…，１３−ν（ｋ−１）の分散値αν（０），…，αν（ｋ−１）が送られる。復元部１３１４−Ｉは、（ｋ，ｎ）−秘密分散の復元方式によって、分散値αν（０），…，αν（ｋ−１）から復元値ａ’’を得て出力する。復元値ａ’’は再分散部１３１５−Ｉに送られる（ステップＳ１６６）。
【００５２】
再分散部１３１５−Ｉは、（ｋ，ｎ）−ＩＤＡによって復元値ａ’’を分散してｎ個の分散値ａ０’’，…，ａｎ−１’’を生成して出力する。分散値ａＩ’’は記憶部１３５−Ｉに格納される。その他の分散値ａｉ’’は、出力部１３２−Ｉからその他のパーティ装置１３−ｉに対して出力され、その他のパーティ装置１３−ｉの１３５−ｉに格納される。再分散部１３１５−ｉは、記憶部１３５−ｉに格納された分散値ａｉ’’とシード値ｓｊ’の列（シード列Ｓｉ’＝｛ｓｊ’∈Ｓ｜Ｐ（ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝）を含む分散値Ｔ’（ｉ）を得、分散値Ｔ’（ｉ）を記憶部１３５−ｉに格納する（ステップＳ１６７）。
【００５３】
《第１実施形態の特徴》
本形態では、部分集合Ｐｓｕｂ（ｊ）に属するパーティ装置１３−ｉに対し、関数値ａ’の分散値ａｉ’とシード値ｓｊとを含む分散値Ｔ（ｉ）を与える。分散値Ｔ（ｉ）がシード値ｓｊそのものを含むため、秘匿計算を行うために必要な情報の受け渡し量を削減できる。例えば、非特許文献１の方式では、環要素のサイズ｜Ｒ｜とすれば、１要素の分散情報変換につきｋ回の準同型秘密分散、すなわちｋ（ｎ−１）｜Ｒ｜の通信量が必要となる。一方、本形態では、１要素の分散情報変換につき（ｋ，ｎ）−ＩＤＡの復元をｎ回行うのみでよい。ＩＤＡの復元に必要な通信量は（１−１／ｋ）｜Ｒ｜であるため（ｋ−１個のパーティ装置から分散値を１個ずつもらうことでｋ個の値を復元できるため）、通信量は合計ｎ（１−１／ｋ）｜Ｒ｜であり、ｋの因数が消え通信量のオーダーが低下していることが分かる。さらに分散値Ｔ（ｉ）がすべてのシード値を含むわけではないため、安全性も確保できる。このように本形態では、安全性を確保しつつ、秘匿計算を行うために必要な情報の受け渡し量を削減する技術を提供する。
【００５４】
＜第２実施形態＞
第２実施形態を説明する。本形態は第１実施形態の変形例であり、さらに改ざん検知機能が付加されたものである。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項について第１実施形態と同じ参照番号を用いて説明を省略する。
《全体構成》
図１に例示するように、本形態の秘密分散システム２は、分散管理装置２１、復元装置２２、およびパーティ装置２３−０,・・・,２３−（ｎ−１）を有し、ネットワーク１４を通じて情報の受け渡しが可能なように構成されている。分散管理装置２１および復元装置２２はディーラー装置に相当する。本形態では、分散管理装置２１と復元装置２２とが別の装置であるが、分散管理装置２１と復元装置２２とが一体であってもよい。パーティ装置２３−０,・・・,２３−（ｎ−１）（パーティ装置Ｐ（０），…，Ｐ（ｎ−１））を元とする集合をＰｓｅｔ＝｛Ｐ（０），…，Ｐ（ｎ−１）｝とする。集合Ｐｓｅｔに属するｎ−ｋ＋１個の元からなる部分集合をＰｓｕｂ（ｊ）⊂Ｐｓｅｔとする。このような部分集合Ｐｓｕｂ（ｊ）はＮ＝ｎＣｋ−１個存在し、ｊ＝０，…，Ｎ−１とする。ｎおよびｋは２以上の整数であり、ｋ−１≦ｎを満たす。
【００５５】
《分散管理装置》
図２Ａに例示するように、本形態の分散管理装置２１は、入力部２１１とシード部２１２と関数部２１３と演算部２１４と分散部２１５と分散値生成部２１６と出力部２１７と記憶部１１８と誤り検出符号部２１１と制御部２１９とを有する。
【００５６】
《復元装置》
図２Ｂに例示するように、本形態の復元装置２２は、入力部２２１と復元部２２２，２２４と演算部２２３と出力部２２５と記憶部１２８と検証部２１１と制御部２２９とを有する。
【００５７】
《パーティ装置》
図３に例示するように、各パーティ装置２３−ｉ（ただし、ｉ＝０，...，ｎ−１）は、提供部２３１−ｉと出力部２３２−ｉと入力部２３３−ｉと復旧部２３４−ｉと記憶部１３５−ｉと復元部２３６−ｉ，２３１４−ｉ，２３１７−ｉと関数部２３７−ｉ，２３８−ｉ，２３１０−ｉ，２３１３−ｉとシード部２３９−ｉと分散部２３１１−ｉと誤り検出符号部２３１４−ｉ，２３１６−ｉと検証部２３１８−ｉと制御部２３１９−ｉとを有する。
【００５８】
本形態の分散管理装置２１、復元装置２２、およびパーティ装置２３−ｉは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。復元装置２２、およびパーティ装置２３−ｉは、それぞれ、制御部２１９，２２９，２３１９−ｉの制御のもとで各処理を実行する。入力データや各処理で得られたデータは、それぞれ記憶部１１８，１２９，１３５−ｉに格納され、必要に応じて読み出されて各処理に利用される。
【００５９】
《分散》
図８を用いて、本形態の分散を説明する。
分散管理装置２１（図２Ａ）の入力部２１１に環Ｒの元からなるＭ個の入力値ｘ０，…，ｘＭ−１∈ＲＭが入力され、演算部２１４および誤り検出符号部２１１に送られる。ただし、Ｍは１以上の整数である（ステップＳ２１１）。
【００６０】
誤り検出符号部２１１は、入力値ｘ０，…，ｘＭ−１に対応する誤り検出符号ｂを生成して出力する。誤り検出符号ｂの例は入力値ｘ０，…，ｘＭ−１のチェックサムである。本形態では、以下のチェックサムｂを誤り検出符号とする（チェックサムの具体例）。
１．乱数ｒを生成する。
２．ｃ＝Σｍ∈｛０，...，Ｍ−１｝ｘｍｒｍ＋１
３．ｂ＝（ｘＭ，ｘＭ＋１）＝（ｃ，ｒ）を誤り検出符号とする。
得られた誤り検出符号ｂは演算部２１４に送られる（ステップＳ２１２）。
【００６１】
制御部２１９はｍ＝０に設定する（ステップＳ２１３）。
【００６２】
シード部２１２と関数部２１３と演算部２１４と分散部２１５と分散値生成部２１６ととによって、ａ＝ｘｍとして第１実施形態のステップＳ１１２−Ｓ１１６を実行し、ｉ＝０，…，ｎ−１について分散値Ｔｍ（ｉ）＝（Ｓｍ，ｉ，ａｍ，ｉ’）を得る。すなわち、まずシード部２１２が、Ｎ個のシード値ｓｍ，０，…，ｓｍ，Ｎ−１∈Ｓを生成して出力する。次に関数部２１３が、各ｊ＝０，…，Ｎ−１に対してａｍ，ｊ＝Ｆ（ｓｍ，ｊ）∈Ｒを計算して出力し、演算部２１４が、関数値ｘｍ’＝Ｇ（ｘｍ，ａｍ，０，…，ａｍ，Ｎ−１）∈Ｒを計算して出力する（例えば、ｘｍ’＝ｘｍ−Σｊ∈｛０，...，Ｎ−１｝ａｍ，ｊ）。次に分散部２１５が、（ｋ，ｎ）−ＩＤＡによって関数値ｘｍ’を分散し、ｎ個の分散値ａｍ，０’，…，ａｍ，ｎ−１’を得て出力する。次に分散値生成部２１６が、部分集合Ｐｓｕｂ（ｊ）に属する元である各パーティ装置２３−ｉ（すなわちＰ（ｉ））に対し、それぞれ分散値ａｍ，ｉ’とシード値ｓｍ，ｊとを含む分散値Ｔｍ（ｉ）を得て出力する。すなわち、各パーティ装置２３−ｉに対し、分散値ａｍ，ｉ’とシード列Ｓｍ，ｉ＝｛ｓｍ，ｊ∈Ｓ｜Ｐ（ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝とを含む分散値Ｔｍ（ｉ）を得て出力する。なお、ｍ＝０，…，Ｍ−１での「シード値ｓｍ，０，…，ｓｍ，Ｎ−１」「関数値ｘｍ’」「分散値ａｍ，ｉ’」および「分散値Ｔｍ（ｉ）」は、それぞれ、入力値ａ＝ｘｍに対応する「シード値ｓ０，…，ｓＮ−１」「関数値ａ’」「分散値ａｉ’」および「分散値Ｔ（ｉ）」に相当する。ｍ＝Ｍ，Ｍ＋１での「シード値ｓｍ，０，…，ｓｍ，Ｎ−１」「関数値ａｍ’」「分散値ｘｍ，ｉ’」および「分散値Ｔｍ（ｉ）」は、それぞれ、誤り検出符号ｂに対応する「シード値ｅ０，…，ｅＮ−１」「関数値ｂ’」「分散値ｂｉ’」および「分散値Ｅ（ｉ）」に相当する（ステップＳ２１４）。
【００６３】
制御部２１９は、ｍ＝Ｍ＋１であるかを判定する（ステップＳ２１５）。ｍ＝Ｍ＋１でなければｍを１だけインクリメントし（ｍ＋１を新たなｍとし）（ステップＳ２１６）、ステップＳ２１４に進む。ｍ＝Ｍ＋１であれば、出力部１１７が各分散値Ｔｍ（ｉ）を各パーティ装置２３−ｉに対して出力する。各分散値Ｔ０（ｉ），…，ＴＭ＋１（ｉ）は、パーティ装置２３−ｉの入力部２３３−ｉに入力され、記憶部２３５−ｉに格納される。このように各パーティ装置２３−ｉに分散値Ｔ０（ｉ），…，ＴＭ＋１（ｉ）が与えられる（ステップＳ２１７）。
【００６４】
《復元》
図９を用いて、本形態の復元を説明する。
各ｍ＝０，…，Ｍ＋１について、任意のｋ個の分散値Ｔｍ（φｍ（０）），…，Ｔｍ（φｍ（ｋ−１））が、復元装置２２（図２Ｂ）の入力部２２１に入力される。ただし、｛φｍ（０），…，φｍ（ｋ−１）｝⊂｛０，…，ｎ−１｝である。分散値Ｔｍ（φｍ（０）），…，Ｔｍ（φｍ（ｋ−１））が含む分散値ａφｍ（０）’，…，ａφｍ（ｋ−１）’は復元部２２２に送られ、シード列Ｓｍ，φｍ（０），…，Ｓｍ，φｍ（ｋ―１）は演算部２２３に送られる。ただし、下付き添え字の「φｍ」は「φｍ」を表す（ステップＳ２２１）。
【００６５】
制御部２２９はｍ＝０に設定する（ステップＳ２２２）。
【００６６】
復元部２２２は、（ｋ，ｎ）−ＩＤＡの復元方式によって、ｋ個の分散値ａφｍ（０）’，…，ａφｍ（ｋ−１）’からｘｍ’を復元して出力する。復元値ｘｍ’は復元部２２４に送られる（ステップＳ２２３）。
【００６７】
演算部２２３は、シード列Ｓｍ，φｍ（０），…，Ｓｍ，φｍ（ｋ―１）に含まれるＮ個のシード値ｓｍ，０，…，ｓｍ，Ｎ−１および前述の擬似乱数生成関数Ｆを用い、関数値ａｍ，０＝Ｆ（ｓｍ，０），…，ａｍ，Ｎ−１＝Ｆ（ｓｍ，Ｎ−１）を計算して出力する。シード列Ｓｍ，φ（０），…，Ｓｍ，φ（ｋ―１）からなる集合は、必ずすべてのシード値ｓｍ，０，…，ｓｍ，Ｎ−１を含む。関数値ａｍ，０，…，ａｍ，Ｎ−１は復元部２２４に送られる（ステップＳ２２４）。
【００６８】
復元部２２４は、復元値ｘｍ’と関数値ａｍ，０，…，ａｍ，Ｎ−１とに対する関数値である復元値ｘｍ＝Ｄａ（ｘｍ’，ａｍ，０，…，ａｍ，Ｎ−１）を計算して出力する。復元値ｘｍは検証部２２１と出力部２２５に送られる（ステップＳ２２５）。
【００６９】
制御部２２９は、ｍ＝Ｍ＋１であるかを判定する（ステップＳ２２６）。ｍ＝Ｍ＋１でなければｍを１だけインクリメントし（ステップＳ２２７）、ステップＳ２２３に進む。ｍ＝Ｍ＋１であれば、検証部２２１が、誤り検出符号の復元値ｂ＝（ｘＭ，ｘＭ＋１）＝（ｃ，ｒ）を用い、入力値の復元値ｘ０，…，ｘＭ−１を検証し、検証合格であるか、検証不合格であるかを判定する（ステップＳ２２８）。上述したチェックサムの具体例を誤り検出符号ｂとした場合、検証部２２１は検証式Σｍ∈｛０，...，Ｍ−１｝ｘｍｒｍ＋１−ｃの演算結果が０となるかを検証し、０であれば検証合格とし、０でなければ検証不合格とする。検証合格であれば、出力部２２５は復元値ｘ０，…，ｘＭ−１を出力する（ステップＳ２２９）。検証不合格であれば、出力部２２５はエラーを出力する（ステップＳ２２１０）。
【００７０】
《復旧準備》
本形態では、復旧を行う前に復旧準備が行われる。
復旧準備では、各パーティ装置１３−ε（ただし、ε＝０，…，ｎ−１）の分散値Ｔ０（ε），…，ＴＭ＋１（ε）に対応する復旧誤り検出符号Ｂ（ε）が生成され、（ｋ，ｎ）−秘密分散によって、復旧誤り検出符号Ｂ（ε）の分散値Ｂｉ（ε）（ただし、ｉ＝０，…，ｎ−１）が生成される。各分散値Ｂｉ（ε）は各パーティ装置１３−ｉに与えられ、記憶部１３５−ｉに格納される。復旧誤り検出符号Ｂ（ε）の例は、分散値Ｔ０（ε），…，ＴＭ＋１（ε）のチェックサムである。例えば、ｘｍ＝Ｔｍ（ε）とした前述したチェックサムの具体例によって、復旧誤り検出符号Ｂ（ε）＝（ｃ，ｒ）が計算される。なお、復旧誤り検出符号Ｂ（ε）や分散値Ｂｉ（ε）の生成は、上記《分散》の後または《分散》と同時に、分散管理装置２１によって行われてもよいし、分散値Ｔ０（ｉ），…，ＴＭ＋１（ｉ）が各パーティ装置２３−ｉに与えられた後に、各パーティ装置２３−ｉによって行われてもよい。
《復旧》
図１０Ａおよび１０Ｂを用いて、本形態の復旧を説明する。以下では、ｋ個のパーティ装置２３−ιで、１個のパーティ装置２３−Ｉに格納された分散値Ｔ（Ｉ）を復旧する例を示す。ただし、ι＝ν（０），…，ν（ｋ−１）、｛ν（０），…，ν（ｋ−１）｝⊂｛０，…，ｎ−１｝、Ｉ∈｛０，…，ｎ−１｝である。
【００７１】
図１０Ａに例示するように、パーティ装置２３−Ｉが属する部分集合Ｐｓｕｂ（ｊ）（ただし０≦ｊ＜Ｎ）に属するパーティ装置２３−ι（すなわちＰ（ι）∈Ｐｓｕｂ（ｊ））の提供部２３１−ι（図３）が、記憶部２３５−ιに格納された分散値Ｔ０（ι），…，ＴＭ＋１（ι）が含むシード列Ｓ０，ι，…，ＳＭ＋１，ιのシード値ｓ０，ｊ，…，ｓＭ＋１，ｊを抽出する。シード値ｓ０，ｊ，…，ｓＭ＋１，ｊは出力部２３２−ιに送られる。なお、ｍ＝０，…，Ｍ−１でのシード値ｓｍ，ｊは、入力値ａ＝ｘｍに対応する「シード値ｓｊ」に相当し、ｍ＝Ｍ，Ｍ＋１でのシード値ｓｍ，ｊは、誤り検出符号ｂに対応する「シード値ｅｊ」に相当する。出力部２３２−ιは、シード値ｓ０，ｊ，…，ｓＭ＋１，ｊをパーティ装置２３−Ｉに対して出力する（ステップＳ２３１）。
【００７２】
ｋ個のパーティ装置２３−ν（０），…，２３−ν（ｋ−１）が協力し、パーティ装置２３−Ｉの分散値ａ０，Ｉ’，…，ａＭ＋１，Ｉ’を再構築する。この処理は、第１実施形態のステップＳ１３１のａＩ’に対する処理を各分散値ａｍ，Ｉ’に対して実行すればよい（ステップＳ２３２）。
【００７３】
何れかのパーティ装置２３−ιの出力部２３２−ιが、復元された分散値ａ０，Ｉ’，…，ａＭ＋１，Ｉ’をパーティ装置２３−Ｉに対して出力する（ステップＳ２３３）。
【００７４】
図６Ｂに例示するように、ステップＳ２３１で各パーティ装置２３−ιから出力された各シード値ｓ０，ｊ，…，ｓＭ＋１，ｊが、パーティ装置２３−Ｉ（図３）の入力部２３３−Ｉに入力され、これらのシード値ｓ０，ｊ，…，ｓＭ＋１，ｊから構成されるシード列Ｓｍ，Ｉ＝｛ｓｊ∈Ｓ｜Ｐ（Ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝（ただし、ｍ＝０，…，Ｍ＋１）が復旧部２３４−Ｉに送られる（ステップＳ２４１）。
【００７５】
ステップＳ２３３で何れかのパーティ装置２３−ιから出力された分散値ａ０，Ｉ’，…，ａＭ＋１，Ｉ’が、パーティ装置２３−Ｉの入力部２３３−Ｉに入力され、復旧部２３４−Ｉに送られる（ステップＳ２４２）。
【００７６】
復旧部２３４−Ｉは、分散値ａｍ，Ｉ’とシード列Ｓｍ，Ｉとを含む復旧分散値Ｔｍ’（Ｉ）（ただし、ｍ＝０，…，Ｍ＋１）を生成して記憶部２３５−Ｉに格納する。なお、ｍ＝０，…，Ｍ−１での復旧分散値Ｔｍ’（Ｉ）は、入力値ａ＝ｘｍに対応する「復旧分散値Ｔ’（Ｉ）」に相当し、ｍ＝Ｍ，Ｍ＋１での復旧分散値Ｔｍ’（Ｉ）は、誤り検出符号ｂに対応する「復旧分散値Ｅ’（Ｉ）」に相当する（ステップＳ２４３）。
【００７７】
任意のｋ個の分散値Ｂφ（０）（Ｉ），…，Ｂφ（０）（Ｉ）が入力部２３３−Ｉに入力される。ただし、｛φ（０），…，φ（ｋ−１）｝⊂｛０，…，ｎ−１｝である。分散値Ｂφ（０）（Ｉ），…，Ｂφ（０）（Ｉ）は復元部２３１７−Ｉに入力される。復元部２３１７−Ｉは、（ｋ，ｎ）−秘密分散の復元方式によって、分散値Ｂφ（０）（Ｉ），…，Ｂφ（０）（Ｉ）から復旧誤り検出符号Ｂ（Ｉ）を復元して出力する。復旧誤り検出符号Ｂ（Ｉ）は検証部２３１８−Ｉに送られる。検証部２３１８−Ｉは、記憶部２３５−Ｉから復旧分散値Ｔ０’（Ｉ），…，ＴＭ＋１’（Ｉ）を読み出し、復旧誤り検出符号Ｂ（Ｉ）を用いて復旧分散値Ｔ０’（Ｉ），…，ＴＭ＋１’（Ｉ）（復旧分散値Ｔ’（Ｉ）と復旧分散値Ｅ’（Ｉ）とに相当）を検証し、検証合格であるか、検証不合格であるかを判定する。例えば、前述したチェックサムの具体例を復旧誤り検出符号Ｂ（Ｉ）＝（ｃ，ｒ）とした場合、検証部２３１８−Ｉは、ｘｍ＝Ｔｍ（ε）およびＢ（Ｉ）＝（ｃ，ｒ）に対する検証式Σｍ∈｛０，...，Ｍ−１｝ｘｍｒｍ＋１−ｃの演算結果が０となるかを検証し、０であれば検証合格とし、０でなければ検証不合格とする（ステップＳ２４４）。検証合格であれば、復旧部２３４−Ｉは、復旧分散値Ｔｍ’（Ｉ）（ただし、ｍ＝０，…，Ｍ＋１）を新たな分散値Ｔｍ（Ｉ）として記憶部２３５−Ｉに格納する（ステップＳ２４５）。検証不合格であれば、出力部２３２−Ｉがエラーを出力する（ステップＳ２４６）。
【００７８】
《分散情報変換》
次に、図１１Ａを用いて、本形態の分散情報変換を説明する。
ｎ個のパーティ装置２３−ｉ（図３）の関数部２３７−ｉが、それぞれ、記憶部１３５−ｉから分散値Ｔｍ（ｉ）（ただし、ｍ＝０，…，Ｍ＋１）が含むシード列Ｓｍ，ｉを読み出し、シード列Ｓｍ，ｉが含む各シード値ｓｍ，ｊおよび擬似乱数生成関数Ｆを用い、各関数値ａｍ，ｊ＝Ｆ（ｓｍ，ｊ）（ただし、ｓｍ，ｊ∈Ｓｍ，ｉ）を計算して出力する。関数値ａｍ，ｊは、複製型秘密分散によってΣｊ∈｛０，...，Ｎ−１｝ａｍ，ｊを分散して得られる分散値［Σｊ∈｛０，...，Ｎ−１｝ａｍ，ｊ］となっている。各関数値ａｍ，ｊは、各関数部２３８−ｉに送られる（ステップＳ１５１）
【００７９】
何れかのパーティ装置２３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部２３６−Ｉに、任意のｋ個のパーティ装置２３−νｍ（０），…，２３−νｍ（ｋ−１）の分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’が送られる。ただし、ｍ＝０，…，Ｍ＋１であり、下付き添え字の「νｍ」は「νｍ」を表し、｛νｍ（０），…，νｍ（ｋ−１）｝⊂｛０，…，ｎ−１｝である。復元部２３６−Ｉは、（ｋ，ｎ）−ＩＤＡの復元方式によって、分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’からｘｍ’を復元し、復元値ｘｍ’を出力する。復元値ｘｍ’はパーティ装置２３−Ｉの出力部２３２−Ｉから、その他すべてのパーティ装置２３−０，…，２３−（ｎ−１）に対して出力される。復元値ｘｍ’は、すべてのパーティ装置２３−０，…，２３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｎ−１）に格納される（ステップＳ２５２）。
【００８０】
次に誤り検出符号部２３１６−Ｉに、各ｍに対するｎ個の分散値ａｍ，０’，…，ａｍ，ｎ−１’のうち、ステップＳ２５２で復元値ｘｍ’を得るために用いられなかった分散値ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’が送られる。ただし、ｍ＝０，…，Ｍ＋１であり、下付き添え字の「θｍ」は「θｍ」を表し、｛θθ（０），…，θθ（ｋ−２）｝⊂｛０，…，ｎ−１｝である。誤り検出符号部２３１６−Ｉは、分散値ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’を復元値ｘｍ’の誤り検出符号とする。出力部２３２−Ｉは、その他すべてのパーティ装置２３−０，…，２３−（ｎ−１）に対して、復元値ｘｍ’の誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）を出力する。誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）は、すべてのパーティ装置２３−０，…，２３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｎ−１）に格納される（ステップＳ２５２）。
【００８１】
誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）を用いることで復元値ｘｍ’を検証することができる（２ｋ−１パーティ改ざん検知機能）。例えば、分散値ａｍ，０’，…，ａｍ，ｎ−１’が多項式ベースの（ｋ，ｎ）−ＩＤＡによって生成されている場合、復元値ｘｍ’を復元するために用いた分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’を用い、その他の分散値をＬａｇｒａｎｇｅ補完し、それらの補完値からなる列が誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）に一致すれば検証合格とし、それ以外の場合に検証不合格とする。なお、復元値ｘｍ’を復元するために用いた分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’は復元値ｘｍ’から算出可能である。
【００８２】
ｎ個のパーティ装置２３−ｉの関数部２３８−ｉは、それぞれ、関数部２３７−ｉから送られた各関数値ａｍ，ｊと、記憶部１３５−ｉから読み出した復元値ｘｍ’とに対する準同型関数値ｚｍ，ｊ＝Ｄ（ｘｍ’，ａｍ，ｊ）を計算して出力する。例えば、ｘｍ’＝ｘｍ−Σｊ∈｛０，...，Ｎ−１｝ａｍ，ｊである場合、関数部２３８−ｉは、ｚｍ，ｊ＝ｘｍ’＋ａｍ，ｊやｚｍ，ｊ＝ｘｍ’／Ｎ＋ａｍ，ｊなどを計算して出力する（ステップＳ２５４）。
【００８３】
《再分散》
次に、図１１Ｂを用いて、本形態の再分散を説明する。
各部分集合Ｐｓｕｂ（ｊ）に属する何れかのパーティ装置２３−υｍ（ｊ）（ただし、Ｐ（υｍ（ｊ））∈Ｐｓｕｂ（ｊ）、０≦υｍ（ｊ）＜ｎ、ｊ＝０，…，Ｎ−１、ｍ＝０，…，Ｍ＋１）のシード部２３９−υｍ（ｊ）が、それぞれ、当該部分集合Ｐｓｕｂ（ｊ）で共有する新たなシード値ｓｍ，ｊ’∈Ｓを生成して出力する。新たなシード値ｓｍ，ｊ’の例は乱数である。新たなシード値ｓｍ，ｊ’は、部分集合Ｐｓｕｂ（ｊ）に属するすべてのパーティ装置２３−ｉ（ただし、Ｐ（ｉ）∈Ｐｓｕｂ（ｊ））の記憶部１３５−ｉに格納される（ステップＳ２６１）。
【００８４】
関数部２３１０−υｍ（ｊ）は、記憶部１３５−υｍ（ｊ）に格納されたシード値ｓｍ，ｊおよび新たなシード値ｓｍ，ｊ’ならびに擬似乱数生成関数Ｆを用い、シード値ｓｍ，ｊの関数値Ｆ（ｓｍ，ｊ）と新たなシード値ｓｍ，ｊ’の関数値Ｆ（ｓｍ，ｊ’）とに対する関数値ｄｍ，ｊ＝Ｈ（Ｆ（ｓｍ，ｊ），Ｆ（ｓｍ，ｊ’））を計算して出力する（例えば、ｄｍ，ｊ＝Ｆ（ｓｍ，ｊ）−Ｆ（ｓｍ，ｊ’））。関数値ｄｍ，ｊは分散部２３１１−υｍ（ｊ）に送られる（ステップＳ２６２）。
【００８５】
分散部２３１１−υｍ（ｊ）は、（ｋ，ｎ）−秘密分散によって関数値ｄｍ，ｊを分散し、分散値［ｄｍ，ｊ］＝ｄｍ，ｊ，０，…，ｄｍ，ｊ，ｎ−１を生成して出力する。分散値ｄｍ，ｊ，υｍ（ｊ）は記憶部１３５−υ（ｊ）に格納され、その他の分散値ｄｍ，ｊ，ｉは、出力部２３２−υｍ（ｊ）から出力され、パーティ装置２３−ｉの記憶部１３５−ｉに格納される（ステップＳ２６３）。ただし、下付き添え字の「υｍ」は「υｍ」を表す。
【００８６】
何れかのパーティ装置２３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部２３６−Ｉに、ｍごとに任意のｋ個のパーティ装置２３−νｍ（０），…，２３−νｍ（ｋ−１）の分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’が送られる。ただし、下付き添え字の「νｍ」は「νｍ」を表す。復元部２３６−Ｉは、（ｋ，ｎ）−ＩＤＡの復元方式によって、分散値ａｍ，νｍ（０）’，…，ａｍ，νｍ（ｋ−１）’から復元値ｘｍ’を計算して出力する。出力部２３２−Ｉは、復元値ｘ０’，…，ｘＭ+1’を他のすべてのパーティ装置２３−０，…，２３−（ｎ−１）に対して出力する。復元値ｘ０’，…，ｘＭ+1’は、すべてのパーティ装置２３−０，…，２３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｋ−１）に入力されて格納される（ステップＳ２６４）。
【００８７】
次に誤り検出符号部２３１６−Ｉに、各ｍに対するｎ個の分散値ａｍ，０’，…，ａｍ，ｎ−１’のうち、ステップＳ２６４で復元値ｘｍ’を得るために用いられなかった分散値ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’が送られる。誤り検出符号部２３１６−Ｉは、分散値ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’を復元値ｘｍ’の誤り検出符号とする。出力部２３２−Ｉは、その他すべてのパーティ装置２３−０，…，２３−（ｎ−１）に対して、復元値ｘｍ’の誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）を出力する。誤り検出符号（ａｍ，θｍ（０）’，…，ａｍ，θｍ（ｋ−２）’）は、すべてのパーティ装置２３−０，…，２３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｎ−１）に格納される（ステップＳ２６５）。
【００８８】
各パーティ装置２３−ｉ（ただし、ｉ＝０，…，ｎ−１）の関数部２３１３−ｉは、記憶部１３５−ｉから読み出した復元値ｘｍ’と分散値ｄｍ，０，ｉ，…，ｄｍ，Ｎ−１，ｉとに対する関数値である分散値αｍ，ｉ＝Ｑ（ｘｍ’，ｄｍ，０，ｉ，…，ｄｍ，Ｎ−１，ｉ）∈Ｒを計算して出力する。Ｑは環ＲのＮ＋１個の元を入力として環の１個の元を出力する所定の関数Ｑ：ＲＮ＋１→Ｒである。関数Ｑは、ステップＳ２６３で用いた（ｋ，ｎ）−秘密分散によってｘｍ’’＝Ｇ（ｘｍ，ａｍ，０’，…，ａｍ，Ｎ−１’）を分散して得られる分散値［ｘｍ’’］が分散値αｍ，ｉとなる関数である。ただし、ａｍ，０’＝Ｆ（ｓｍ，０’），…，ａｍ，Ｎ−１’＝Ｆ（ｓｍ，Ｎ−１’）である。例えば、ｘｍ’＝ｘｍ−Σｊ∈｛０，...，Ｎ−１｝ａｍ，ｊかつｄｍ，ｊ＝Ｆ（ｓｍ，ｊ）−Ｆ（ｓｍ，ｊ’）である場合、αｍ，ｉ＝ｘｍ’＋Σｊ∈｛０，...，Ｎ−１｝ｄｍ，ｊ，ｉである（ステップＳ２６６）。
【００８９】
何れかのパーティ装置２３−Ｉ（ただし、Ｉ∈｛０，…，ｎ−１｝）の復元部２３１４−Ｉに、ｍごとに任意のｋ個のパーティ装置２３−νｍ（０），…，２３−νｍ（ｋ−１）の分散値αｍ,νｍ（０），…，αｍ,νｍ（ｋ−１）が送られる。復元部２３１４−Ｉは、（ｋ，ｎ）−秘密分散の復元方式によって、分散値αｍ,νｍ（０），…，αｍ,νｍ（ｋ−１）から復元値ｘｍ’’を得て出力する。復元値ｘ０’’，…，ｘＭ+1’’は再分散部２３１５−Ｉに送られる（ステップＳ２６７）。
【００９０】
次に誤り検出符号部２３１４−Ｉに、各ｍに対するｎ個の分散値αｍ,０，…，αｍ,ｎ−１のうち、ステップＳ２６７で復元値ｘｍ’’を得るために用いられなかった分散値αｍ，θｍ（０）’，…，αｍ，θｍ（ｋ−２）’が送られる。誤り検出符号部２３１６−Ｉは、分散値αｍ，θｍ（０）’，…，αｍ，θｍ（ｋ−２）’を復元値ｘｍ’’の誤り検出符号とする。出力部２３２−Ｉは、その他すべてのパーティ装置２３−０，…，２３−（ｎ−１）に対して、復元値ｘｍ’’の誤り検出符号（αｍ，θｍ（０）’，…，αｍ，θｍ（ｋ−２）’）を出力する。誤り検出符号（αｍ，θｍ（０）’，…，αｍ，θｍ（ｋ−２）’）は、すべてのパーティ装置２３−０，…，２３−（ｎ−１）の記憶部１３５−０，…，１３５−（ｎ−１）に格納される（ステップＳ２６８）。
【００９１】
再分散部２３１５−Ｉは、復元部２３６−Ｉは（ｋ，ｎ）−ＩＤＡを用い、ｍごとに復元値ｘｍ’’を分散してｎ個の分散値ｘｍ，０’’，…，ｘｍ，ｎ−１’’を生成して出力する（ただし、ｍ＝０，…，Ｍ＋１）。分散値ｘｍ，Ｉ’’は記憶部１３５−Ｉに格納される。その他の分散値ｘｍ，ｉ’’は、出力部２３２−Ｉからその他のパーティ装置２３−ｉに対して出力され、その他のパーティ装置２３−ｉの１３５−ｉに格納される。分散部２３１５−ｉは、記憶部１３５−ｉに格納された分散値ｘｍ，ｉ’’とシード値ｓｍ，ｊ’の列（シード列Ｓｍ，ｉ’＝｛ｓｍ，ｊ’∈Ｓ｜Ｐ（ｉ）∈Ｐｓｕｂ（ｊ） ａｎｄ ０≦ｊ＜Ｎ｝）を含む分散値Ｔｍ’（ｉ）を得、分散値Ｔｍ’（ｉ）を記憶部１３５−ｉに格納する（ステップＳ２６９）。
【００９２】
《第２実施形態の特徴》
本形態でも第１実施形態と同様、安全性を確保しつつ、秘匿計算を行うために必要な情報の受け渡し量を削減する技術を提供する。さらにチェックサム等の誤り訂正符号も分散することとしたため、秘匿性だけではなく正当性も保証できる。
【００９３】
＜変形例等＞
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１実施形態では１個の入力値ａを対象とした各処理を例示したが、複数個の入力値を対象とする場合には第１実施形態で説明した処理を各入力値について繰り返し実行すればよい。ただし、安全性の観点から、入力値ごとにシード値を変更することが望ましい。
【００９４】
擬似乱数生成関数Ｆの定義域の値のデータ量は、値域の値のデータ量よりも小さいことが望ましい。例えば、シード値のデータ量が無視できる程度であることが望ましい。これにより分散値のデータ量を小さくすることができる。あるいは、シード値がそのまま擬似乱数として用いられてもよい。例えば、ａ０＝ｓ０，…，ａＮ−１＝ｓＮ−１であってもよい。
【００９５】
第２実施形態では各ｍにおいて同一の擬似乱数生成関数Ｆ：Ｓ→Ｒを用いたが、各ｍに応じて擬似乱数生成関数Ｆが異なってもよい。例えば、入力値とｍとの組に対して所定の擬似乱数関数を作用させる関数をＦとしてもよい（すなわち、Ｆ（入力値，ｍ））。このように各ｍに応じて擬似乱数生成関数Ｆが異なる場合、各ｍでの入力値に同じシード値を用いてもよい。これにより、同じシード値を複数個のｍについて流用することができ、分散値のデータ量を削減できる。同様に、各ｍに応じて関数Ｇ、Ｄ、Ｈ、その他の関数が異なっていてもよい。
【００９６】
第２実施形態では、分散管理装置２１が入力値ｘ０，…，ｘＭ−１の誤り検出符号を生成し、誤り検出符号を分散することとした。しかしながら、分散管理装置２１が入力値ｘ０，…，ｘＭ−１の誤り検出符号を生成せずに分散値Ｔ０（ｉ），…，ＴＭ―１（ｉ）のみを生成して各パーティ装置２３−ｉに与え、各パーティ装置２３−ｉが、分散値Ｔ０（ｉ），…，ＴＭ―１（ｉ）を用いた秘匿計算によって入力値ｘ０，…，ｘＭ−１の誤り検出符号の分散値ＴＭ（ｉ），ＴＭ＋１（ｉ）を生成してもよい。この場合、ステップＳ２１５でｍ＝Ｍ−１であるかが判定され、ｍ＝Ｍ−１でなければ、ｍを１だけインクリメントしてステップＳ２１４に進み、ｍ＝Ｍ−１であれば、各分散値Ｔｍ（ｉ）を各パーティ装置２３−ｉに対して出力する。
【００９７】
第１実施形態の分散情報変換および再分散に変えて、Ｍ＝１、ａ０，ｊ＝ａｊ、Ｓ０，ｊ＝Ｓｊ、ｘ０’＝ａ’、ｚ０，ｊ＝Ｄ（ｘ０’，ａ０，ｊ）＝Ｄ（ａ’，ａｊ）＝ｚ０、ｄ０，ｊ＝Ｈ（Ｆ（ｓ０，ｊ），Ｆ（ｓ０，ｊ’））＝Ｈ（Ｆ（ｓｊ），Ｆ（ｓｊ’）＝ｄｊ、α０，ｉ＝Ｑ（ｘ０’，ｄ０，０，ｉ，．．．，ｄ０，Ｎ−１，ｉ）＝Ｑ（ａ’，ｄ０，ｉ，．．．，ｄＮ−１，ｉ）、ｘ０’’ ＝ａ’’、（ｘ０，０’’，．．．，ｘ０，ｎ−１’’）＝（ａ０’’，．．．，ａｎ−１’’）とした第２実施形態の分散情報変換および再分散を実行してもよい。
【００９８】
第１実施形態では１個の入力値ａ∈Ｒを秘密分散する例を説明した。しかしながら、複数個の環の要素を入力値として第１実施形態の秘密分散が行われてもよい。その場合には、複数個の入力値それぞれに対して第１実施形態で説明した各処理を行えばよい。その際に上述のようにシード値を流用することでデータ量を削減できる。
【００９９】
各実施形態では各装置がネットワーク１４を通じて情報の受け渡しが可能なように構成されていた。しかしながら、各装置が可搬型記録媒体を介して情報の受け渡しが可能なように構成されていてもよい。すなわち、各装置間の情報の受け渡しはネットワーク１４を通じた通信によって行われてもよいし、可搬型記録媒体を介して行われてもよい。また、何れかのパーティ装置がディーラー装置として機能してもよい。すなわち、何れかのパーティ装置が分散管理装置および／または復元装置であってもよい。
【０１００】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０１】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１０２】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【０１０４】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１０５】
１，２  秘密分散システム
１１，２１  分散管理装置
１２，２２  復元装置
１３−０〜（ｎ−１），２３−０〜（ｎ−１）  パーティ装置
【図１】
2014137516.tif 000003
【図２】
2014137516.tif 000004
【図３】
2014137516.tif 000005
【図４】
2014137516.tif 000006
【図５】
2014137516.tif 000007
【図６】
2014137516.tif 000008
【図７】
2014137516.tif 000009
【図８】
2014137516.tif 000010
【図９】
2014137516.tif 000011
【図１０】
2014137516.tif 000012
【図１１】
2014137516.tif 000013