JP5411994B2 - 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム - Google Patents

Description

本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラムに関する。

暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある(例えば、非特許文献１に記載された方法)。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させ、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算(否定，論理積，論理和，排他的論理和)、データ形式変換(整数,二進数)の結果を３つの秘密計算装置に分散保持させることができる。

千田浩司，五十嵐大，高橋克巳，"効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察"，第48回情報処理学会研究報告，CSEC, pp.1-7, 2010，3月.

しかしながら、従来技術はデータの対応を隠したまま複数のデータをランダムに置換できないという課題がある。本発明の目的は、入力された複数のデータと対応つけることができないデータを出力する秘密計算技術を提供することである。

本発明は秘密分散に関する。一般に、（ｋ，ｎ）−秘密分散では、秘密分散システムが２つのパラメータｋ，ｎを持っており、秘密にしたい値をｎ個に分割し、そのうちｋ個未満を集めても元の値に関する情報は漏れないが、ｋ個以上を集めると元の値を復元できる。本発明の秘密分散システムは、Ｎ個の秘密分散装置Ｒ_１，…，Ｒ_Ｎで構成される。ここで、Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）を対応付けられたｋ番目の数値群、ａ_ｋｎ ^（ｍ）をｎ番目の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片とする。本発明の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。選択手段は、２以上Ｎ未満の数の秘密分散装置を選択する。断片置換手段は、選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置Ｒ_ｉ（ただし、ｉは選択された秘密分散装置を示す番号）が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする。再分散手段は、断片置換手段によって置換された数値Ａ_π（ｋ） ^（１），…，Ａ_π（ｋ） ^（Ｍ）に対応する断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）を用いて再分散化して新しい断片ｂ_ｋ１ ^（１），…，ｂ_ｋＮ ^（１），…，ｂ_ｋ１ ^（Ｍ），…，ｂ_ｋＮ ^（Ｍ）を求める（以下、これを「再分散化」と呼ぶ）。なお、対応つけられた数値群の対応を維持したまま数値群を再分散化する場合は、同一の全単射πを用いて、対応つけられた数値群の各数値の断片を置換すればよい。

また、本発明の秘密分散システムは、初期情報分散手段、初期乗算手段、確認分散手段、確認乗算手段、改ざん検出手段も備えてもよい。初期情報分散手段は、秘密分散装置Ｒ_１，…，Ｒ_Ｎのどれも知らないＫ個の数値Ｐ_１，…，Ｐ_Ｋそれぞれの断片ｐ_１ｎ，…，ｐ_Ｋｎを秘密計算によって求め、秘密分散装置Ｒ_ｎに記録させる。初期乗算手段は、秘密分散装置Ｒ_１，…，Ｒ_Ｎで、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋ ^（１）である数値Ｓ_ｋの断片ｓ_ｋ１，…，ｓ_ｋＮを秘密計算によって求め、秘密分散装置Ｒ_１，…，Ｒ_Ｎに分散して記録する。確認分散手段は、ｋ＝１〜Ｋについて、Ｑ_ｋ＝Ｐ_π（ｋ）である数値Ｑ_ｋの断片ｑ_ｋ１，…，ｑ_ｋＮを秘密計算によって生成し、秘密分散装置Ｒ_１，…，Ｒ_Ｎに分散して記録させる。確認乗算手段は、秘密分散装置Ｒ_１，…，Ｒ_Ｎで、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋ ^（１）である数値Ｔ_ｋの断片ｔ_ｋ１，…，ｔ_ｋＮを秘密計算によって求め、秘密分散装置Ｒ_１，…，Ｒ_Ｎに分散して記録する。改ざん検出手段は、ｋ＝１〜Ｋについて、Ｔ_ｋ＝Ｓ_π（ｋ）であることを確認する。

例えば、３つの秘密分散装置で構成する場合であれば、ｋ番目の対応つけられた数値群のｍ番目の数値Ａ_ｋ ^（ｍ）＝ａ_ｋαβ ^（ｍ）＋ａ_ｋβγ ^（ｍ）＋ａ_ｋγα ^（ｍ）（ただし、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）の３つの断片を（ａ_ｋγα ^（ｍ），ａ_ｋαβ ^（ｍ））、（ａ_ｋαβ ^（ｍ），ａ_ｋβγ ^（ｍ））、（ａ_ｋβγ ^（ｍ），ａ_ｋγα ^（ｍ））とする。秘密分散装置が、第１の秘密分散装置として選ばれたときには記録する断片をａ_ｋ１ ^（ｍ）＝（ａ_ｋ３１ ^（ｍ），ａ_ｋ１２ ^（ｍ））、第２の秘密分散装置として選ばれたときには記録する断片をａ_ｋ２ ^（ｍ）＝（ａ_ｋ１２ ^（ｍ），ａ_ｋ２３ ^（ｍ））、第３の秘密分散装置として選ばれたときには記録する断片をａ_ｋ３ ^（ｍ）＝（ａ_ｋ２３ ^（ｍ），ａ_ｋ３１ ^（ｍ））とする。そして、各秘密分散装置は、断片置換部、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部を備えればよい。断片置換部は、第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、π（ｋ）番目の対応つけられた数値群の各数値の断片をｋ番目の対応つけられた数値群の各数値の断片にする。第１乱数生成部は、第１の秘密分散装置のときには、移動後のｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂ_ｋ３１ ^（１），…，ｂ_ｋ３１ ^（Ｍ）を生成し、第３の秘密分散装置に送信する。第２乱数生成部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂ_ｋ２３ ^（１），…，ｂ_ｋ２３ ^（Ｍ）を生成し、第３の秘密分散装置に送信する。第１計算部は、第１の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｘ_ｋ ^（ｍ）＝ｂ_ｋ３１ ^（ｍ）−ａ_{π（ｋ）３１} ^（ｍ）を計算し、第２の秘密分散装置に送信する。第２計算部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｙ_ｋ ^（ｍ）＝ｂ_ｋ２３ ^（ｍ）−ａ_{π（ｋ）２３} ^（ｍ）を計算し、第１の秘密分散装置に送信する。第３計算部は、第１の秘密分散装置または第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１〜Ｍについてｂ_ｋ１２ ^（ｍ）＝ａ_{π（ｋ）１２} ^（ｍ）−ｘ_ｋ ^（ｍ）−ｙ_ｋ ^（ｍ）を計算する。断片更新部は、第１の秘密分散装置のときには（ｂ_ｋ３１ ^（ｍ），ｂ_ｋ１２ ^（ｍ））を断片ｂ_ｋ１ ^（ｍ）とし、第２の秘密分散装置のときには（ｂ_ｋ１２ ^（ｍ），ｂ_ｋ２３ ^（ｍ））を断片ｂ_ｋ２ ^（ｍ）とし、第３の秘密分散装置のときには（ｂ_ｋ２３ ^（ｍ），ｂ_ｋ３１ ^（ｍ））を断片ｂ_ｋ３ ^（ｍ）とする。なお、全ての秘密分散装置の断片置換部で、秘密分散システムの断片置換手段が構成される。また、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部で、秘密分散システムの再分散手段が構成される。

本発明の秘密分散システムによれば、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）と数値Ｂ_１ ^（１），…，Ｂ_Ｋ ^（１），…，Ｂ_１ ^（Ｍ），…，Ｂ_Ｋ ^（Ｍ）との対応が分からない。本発明を用いることにより、クイックソートなどの比較に基づくソーティングアルゴリズムを、比較回数を増やすことなく秘密計算上で実現できる。

実施例１，２の秘密分散システムの機能構成例を示す図。 実施例１の秘密分散システムでの秘密分散の処理フローを示す図。 本発明の秘密分散システムでの数値のソートの処理フローを示す図。 クイックソートのアルゴリズムを示す図。 実施例２の秘密分散システムでの秘密分散の処理フローを示す図。 実施例３，４の秘密分散システムの機能構成例を示す図。 実施例３，４の再分散部の詳細な構成の例を示す図。 実施例３の秘密分散システムでの秘密分散の処理フローを示す図。 実施例４の改ざん検出部の詳細な構造を示す図。 実施例４の秘密分散システムでの秘密分散の処理フローを示す図。

以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

課題を解決するための手段では、数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）を対応付けられたｋ番目の数値群、ａ_ｋｎ ^（ｍ）をｎ番目の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片として説明した。本実施例では、まず本発明の理解を助けるために、Ｍ＝１の場合について説明し、その後Ｍを１に限定しない場合について説明する。また、Ｍ＝１の場合の説明では、Ａ_ｋ ^（１）をＡ_ｋと、ａ_ｋｎ ^（１）をａ_ｋｎと表現する。

［限定シャッフル］
図１に実施例１の秘密分散システムの機能構成例を示す。図２に実施例１の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００_１，…，１００_Ｎと選択手段１０５で構成される。ここで、Ａ_１，…，Ａ_Ｋを各秘密分散装置１００_ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａ_ｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａ_ｋｎを秘密分散装置１００_ｎが記録するｋ番目の断片とする。なお、数値Ａ_１，…，Ａ_Ｋが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａ_ｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。

本実施例の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００_ｎは、少なくとも断片置換部１１０_ｎと再分散部１２０_ｎと記録部１９０_ｎを備える。記録部１９０_ｎは断片ａ_１ｎ，…，ａ_Ｋｎなどを記録する。また、記録部１９０_ｎは、自身が記録している断片ａ_ｋｎが数値Ａ_ｋの何番目の断片なのかに関する情報も記録する。

選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。

断片置換手段は、少なくとも断片置換部１１０_１，…，１１０_Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００_ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０_ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００_ｉの記録部１９０_ｉが記録する断片ａ_{π（ｋ）ｉ}をｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密分散装置１００_ｉ間で生成してもよいし、選択された秘密分散装置１００_ｉのうちの１つの秘密分散装置が生成して、選択された秘密分散装置１００_ｉ間で共有してもよい。

再分散手段は、少なくとも再分散部１２０_１，…，１２０_Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａ_π（ｋ）に対応する断片ａ_{π（ｋ）ｉ}（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂ_ｋ１，…，ｂ_ｋＮを求め、数値Ｂ_ｋの断片とする（Ｓ１２０）。つまり、Ａ_π（ｋ）＝Ｂ_ｋの関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａ_π（ｋ）＝Ｂ_ｋであることを知らない。なお、各秘密分散装置１００_ｎの記録部１９０_ｎは、断片ｂ_ｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂ_ｋｎが数値Ｂ_ｋの断片であるという情報も記録する。また、数値Ｂ_１，…，Ｂ_Ｋを新しい数値Ａ_１，…，Ａ_Ｋとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。

本発明の秘密分散システムによれば、限定された秘密分散装置間で断片をシャッフルする。したがって、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ_１，…，Ａ_Ｋと数値Ｂ_１，…，Ｂ_Ｋとの対応が分からない。つまり、特定の秘密分散装置からは数値Ａ_１，…，Ａ_Ｋと数値Ｂ_１，…，Ｂ_Ｋとの対応が分からない状態にしたいのであれば、その秘密分散装置を断片置換部で選ばないように、選択する秘密分散装置をあらかじめ定めればよい。また、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ_１，…，Ａ_Ｋと対応つけることができない数値Ｂ_１，…，Ｂ_Ｋを得ることができる。

［再分散］
上述の限定シャッフルの説明では、再分散については詳しく説明しなかった。ここでは、再分散の方法について説明する。再分散の方法としては、参考文献２（Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung, “Proactive secret sharing or: How to cope with perpetual leakage”, In Don Coppersmith, editor, CRYPTO 1995, volume 963 of LNCS, pages 339-352. Springer, 1995.）の3.3節に示された更新方法と、参考文献３（Haiyun Luo and Songwu Lu, “Ubiquitous and robust authentication services for ad hoc wireless networks”, In UCLA-CSD-TR-200030, 2000.）の6.1節に示された再作成方法を用いる。選択手段１０５が選択した秘密計算装置間で参考文献２の更新方法を用いて新しい断片を生成し、その後、参考文献３の再作成方法を用いて選択手段１０５が選択しなかった秘密計算装置の新しい断片を生成する。

参考文献２の更新方法を、本件に適用したアルゴリズムを以下に示す。選択手段１０５がＮ’個の秘密分散装置を選択したとする。そして、ｉとｊは選択された秘密分散装置を示す番号（１〜Ｎの中から選ばれたＮ’個の数の中のいずれか）であって、ｊ≠ｉとする。また、値ｚ_１，…，ｚ_Ｎはあらかじめ決められた値であり、すべての秘密分散装置間で共有されているとする。
（１）すべての秘密分散装置１００_ｉは、Ｎ’−１個の乱数ｕ_ｉ，１，ｕ_ｉ，２，…，ｕ_{ｉ，Ｎ’−１}を作成する。
（２）すべての秘密分散装置１００_ｉは、Ｚ_ｉ（ｚ）：＝０＋ｕ_ｉ，１ｚ＋ｕ_ｉ，２ｚ^２＋…＋ｕ_{ｉ，Ｎ’−１}ｚ^Ｎ’−１を定める。
（３）すべての秘密分散装置１００_ｉは、選択された他の秘密分散装置１００_ｊ（Ｎ’−１個存在する）のすべてに対して、それぞれＺ_ｉ（ｚ_ｊ）の値を送信する。
（４）すべての秘密分散装置１００_ｉは、選択された他の秘密分散装置１００_ｊ（Ｎ’−１個存在する）から受け取ったすべてのＺ_ｊ（ｚ_ｉ）の和をＺ（ｚ_ｉ）とし、新しい断片ｂ_ｋｉを置換された断片ａ_{π（ｋ）ｉ}を用いて、
ｂ_ｋｉ＝ａ_{π（ｋ）ｉ}＋Ｚ（ｚ_ｉ）
のように求める。

次に、参考文献３の再作成方法を、本件に適用したアルゴリズムを以下に示す。ｈは選択されなかった秘密分散装置を示す番号（１〜Ｎの中から選ばれなかったＮ−Ｎ’個の数のなかのいずれか）とする。また、Ｌ_ｉｊ（ｚ）＝（ｚ−ｚ_ｊ）／（ｚ_ｉ−ｚ_ｊ）とし、Ｌ_ｉ（ｚ）は、すべてのｊについてのＬ_ｉｊ（ｚ）の積とする。
（５）すべての秘密分散装置１００_ｉは、ｉ＜ｊであるｊと、選択されなかった秘密分散装置１００_ｈのすべての組み合わせに対して、乱数ｖ_ｉ，ｊ ^（ｈ）を生成する。
（６）すべての秘密分散装置１００_ｉは、ｖ_ｉ，ｊ ^（ｈ）を秘密分散装置１００_ｊに送信する。
（７）すべての秘密分散装置１００_ｉは、すべての選択されなかった秘密分散装置１００_ｈについて、ｊ＜ｉのすべての乱数ｖ_ｉ，ｊ ^（ｈ）の和をＶ^（ｈ＋）とし、ｉ＜ｊのすべての乱数ｖ_ｉ，ｊ ^（ｈ）の和をＶ^（ｈ−）とし、値ｗ_ｈｉを、
ｗ_ｈｉ＝ｂ_ｋｉＬ_ｉ（ｚ_ｈ）＋Ｖ^（ｈ＋）−Ｖ^（ｈ−）
のように求め、秘密分散装置１００_ｈに値ｗ_ｈｉを送信する。
（８）すべての秘密分散装置１００_ｈは、受信したすべての値ｗ_ｈｉの和を新しい断片ｂ_ｋｈとする。

上述のように、（１）〜（４）の処理で、すべての選択された秘密分散装置が、新しい断片を記録する。（５）〜（８）の処理で、すべての選択されなかった秘密分散装置が、新しい断片を記録する。

なお、（３）と（６）の処理を同時に行えば、処理の高速化を図ることができる。具体的には、（１）、（２）、（５）の処理をまず行い、（３）と（６）を同時に行い、（４）、（７）、（８）の処理を行えばよい。

［ソート］
図３に実施例１の秘密分散システムでの数値のソートの処理フローを示す。上述の方法によって初期の数値Ａ_１，…，Ａ_Ｋと対応つけることができない新しい数値Ａ_１，…，Ａ_Ｋを得ている（Ｓ１０１）。ソートも行う場合は、秘密分散装置１００_ｎは、比較部２１０_ｎと交換部２２０_ｎも備える。比較部２１０_１，…，２１０_Ｎは、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する（Ｓ２１０）。

交換部２２０_１，…，２２０_Ｎは、それぞれ比較部２１０_１，…，２１０_Ｎでの比較結果に基づいて、０組または１組または複数組の数値の断片を入れ替える（Ｓ２２０）。そして、全ての数値に対するソート処理が終わるまで、ステップＳ２１０とＳ２２０（比較、交換、組合せの変更などの必要な処理）を繰り返せばよい（Ｓ２１１，Ｓ２１２）。

ステップＳ２１０の比較結果は、全ての秘密分散装置の次の処理に必要な情報なので全ての秘密分散装置が知る情報である。しかし、ステップＳ１０１によって全ての秘密分散装置が初期の数値Ａ_１，…，Ａ_Ｋと対応できなくなった新しい数値Ａ_１，…，Ａ_Ｋに対して処理しているので、初期の数値Ａ_１，…，Ａ_Ｋに関する情報は漏れない。さらに、比較結果は、ソートの出力という公開情報から計算可能な情報でもある。そのため、本実施例のプロトコル全体で見ても、比較結果が開示されることは必要以上の情報を漏らしたことにはならない。

なお、より具体的には、ソートの部分（ステップＳ２１０，Ｓ２２０，Ｓ２１１，Ｓ２１２）には図４に示すクイックソートのアルゴリズムを適用すればよい。この場合もＡ［ｉ］とＡ［ｊ］とを比較する処理はＡ［ｉ］とＡ［ｊ］の値を秘匿したままで行い、比較結果は公開される。この方法の場合、比較回数は元のクイックソートと同じであり、平均Ｏ（Ｎ・ｌｏｇＮ）回である。また、この他にも、数値の大小比較の処理と配列の２つの要素を入れ替える処理で構成できるソーティングアルゴリズムにも本実施例は適用できる。

このように、本実施例の秘密分散システムを用いれば、比較と要素の入れ替えからなるソーティングアルゴリズムを比較回数を増やすことなく秘密計算で実現できる。

［限定シャッフルの変形例］
次に、Ｍを１に限定しない場合について説明する。Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ^（１），…，Ａ^（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ^（ｍ）＝(Ａ_１ ^（ｍ），…，Ａ_Ｋ ^（ｍ）)とする。また、ベクトルＡ^（１），…，Ａ^（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）は対応付けられたｋ番目の数値群とする。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、ａ_ｋｎ ^（ｍ）を秘密分散装置１００_ｎが記録する数値Ａ_ｋ ^（ｍ）の断片とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。

秘密分散システムの構成は図１と同じであり、秘密分散の処理フローは図２と同じである。秘密分散装置１００_ｎは、少なくとも断片置換部１１０_ｎと再分散部１２０_ｎと記録部１９０_ｎを備える。ただし、各構成部とその処理は以下のようになる。

記録部１９０_ｎは断片ａ_１ｎ ^（１），…，ａ_Ｋｎ ^（１），…，ａ_１ｎ ^（Ｍ），…，ａ_Ｋｎ ^（Ｍ）などを記録する。また、記録部１９０_ｎは、自身が記録している断片ａ_ｋｎが数値Ａ_ｋの何番目の断片なのかに関する情報も記録する。

選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。この処理は同じである。

断片置換手段は、少なくとも断片置換部１１０_１，…，１１０_Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００_ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０_ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００_ｉの記録部１９０_ｉが記録する断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。

再分散手段は、少なくとも再分散部１２０_１，…，１２０_Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値群Ａ_π（ｋ） ^（１），…，Ａ_π（ｋ） ^（Ｍ）に対応する断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂ_ｋ１ ^（１），…，ｂ_ｋＮ ^（１），…，ｂ_ｋ１ ^（Ｍ），…，ｂ_ｋＮ ^（Ｍ）を求め、数値Ｂ_ｋ ^（１），…，Ｂ_ｋ ^（Ｍ）の断片とする（Ｓ１２０）。つまり、Ａ_π（ｋ） ^（ｍ）＝Ｂ_ｋ ^（ｍ）の関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａ_π（ｋ） ^（ｍ）＝Ｂ_ｋ ^（ｍ）であることを知らない。なお、各秘密分散装置１００_ｎの記録部１９０_ｎは、断片ｂ_ｋｎ ^（ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂ_ｋｎ ^（ｍ）が数値Ｂ_ｋ ^（ｍ）の断片であるという情報も記録する。また、数値Ｂ_１ ^（１），…，Ｂ_Ｋ ^（１），…，Ｂ_１ ^（Ｍ），…，Ｂ_Ｋ ^（Ｍ）を新しい数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。

このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。

［限定シャッフル］
実施例２の秘密分散システムの構成も図１に示す。なお、本実施例の秘密分散装置１００_ｎは、点線で示された構成部も備えている。図５に実施例２の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００_１，…，１００_Ｎと選択手段１０５で構成される。ここで、Ａ_１，…，Ａ_Ｋを各秘密分散装置１００_ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａ_ｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａ_ｋｎを秘密分散装置１００_ｎが記録する数値Ａ_ｋの断片とする。

本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００_ｎは、初期情報分散部１３０_ｎ、初期乗算部１４０_ｎ、断片置換部１１０_ｎ、再分散部１２０_ｎ、確認分散部１５０_ｎ、確認乗算部１６０_ｎ、改ざん検出部１７０_ｎ、記録部１９０_ｎを備える。記録部１９０_ｎは断片ａ_１ｎ，…，ａ_Ｋｎなどを記録する。また、記録部１９０_ｎは、自身が記録している断片ａ_ｋｎが数値Ａ_ｋの何番目の断片なのかに関する情報も記録する。

選択手段１０５は実施例１と同じである。初期情報分散手段は、初期情報分散部１３０_１，…，１３０_Ｎで構成される。そして、選択手段１０５に選択された秘密計算装置１００_ｉの初期情報分散部１３０_ｉは、秘密分散装置１００_１，…，１００_Ｎのどれも知らないＫ個の数値Ｐ_１，…，Ｐ_Ｋそれぞれの断片ｐ_１１，…，ｐ_Ｋ１，…，ｐ_１ｎ，…，ｐ_Ｋｎ，…，ｐ_１Ｎ，…，ｐ_ＫＮを秘密計算によって求め、秘密分散装置１００_ｎに断片ｐ_１ｎ，…，ｐ_Ｋｎを記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密分散装置から、２つ以上の秘密分散装置を選定する。そして、選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密分散装置１００_ｉ，１００_ｊを選定し（ただし、ｉ≠ｊ）、秘密分散装置１００_ｉが生成した数値の断片と、秘密分散装置１００_ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、２つ以上でもかまわない。

初期乗算手段は、初期乗算部１４０_１，…，１４０_Ｎで構成される。初期乗算部１４０_１，…，１４０_Ｎは、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋである数値Ｓ_ｋの断片ｓ_ｋ１，…，ｓ_ｋＮを秘密計算によって求め、秘密分散装置１００_１，…，１００_Ｎに分散して記録する（Ｓ１４０）。

断片置換手段と再分散手段は、実施例１と同じである。確認分散手段は、確認分散部１５０_１，…，１５０_Ｎで構成される。確認分散部１５０_１，…，１５０_Ｎは、ｋ＝１〜Ｋについて、Ｑ_ｋ＝Ｐ_π（ｋ）である数値Ｑ_ｋの断片ｑ_ｋ１，…，ｑ_ｋＮを秘密計算によって生成し、秘密分散装置１００_１，…，１００_Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密分散装置１００_ｉが数値Ｐ_π（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密分散装置１００_ｊが数値Ｐ_π（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑ_ｋ＝Ｐ_π（ｋ）であり、かつ、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。

確認乗算手段は、確認乗算部１６０_１，…，１６０_Ｎで構成される。確認乗算部１６０_１，…，１６０_Ｎは、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋである数値Ｔ_ｋの断片ｔ_ｋ１，…，ｔ_ｋＮを秘密計算によって求め、秘密分散装置１００_１，…，１００_Ｎに分散して記録する（Ｓ１６０）。

改ざん検出手段は、改ざん検出部１７０_１，…，１７０_Ｎで構成される。改ざん検出部１７０_１，…，１７０_Ｎは、ｋ＝１〜Ｋについて、Ｔ_ｋ＝Ｓ_π（ｋ）であることを確認する（Ｓ１７０）。ｔ_ｋｎ≠ｓ_{π（ｋ）ｎ}の場合には、改ざんがあったとして異常終了する。また、数値Ｂ_１，…，Ｂ_Ｋを新しい数値Ａ_１，…，Ａ_Ｋとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。

実施例２の秘密分散システムによれば、実施例１の秘密分散装置と同じ効果が得られると共に、数値Ａ_１，…，Ａ_Ｋと数値Ｂ_１，…，Ｂ_Ｋとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００_ｎは、比較部２１０_ｎと交換部２２０_ｎも備える。具体的なソートの処理については実施例１と同じである。

実施例１、２では、秘密分散装置の数をＮ（Ｎは３以上の整数）としていた。実施例３では、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。

［限定シャッフル］
図６に実施例３の秘密分散システムの機能構成例を示す。図７に実施例３の再分散部の詳細な構成の例を示す。図８に実施例３の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００_α，１００_β，１００_γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａ_ｋ＝ａ_ｋαβ＋ａ_ｋβγ＋ａ_ｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａ_ｋγα，ａ_ｋαβ）、（ａ_ｋαβ，ａ_ｋβγ）、（ａ_ｋβγ，ａ_ｋγα）とする。なお、選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。

本実施例の秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。各秘密分散装置１００_ｎは、断片置換部１１０_ｎ、再分散部１２０_ｎ、記録部１９０_ｎを備えている（ただし、ｎはα、β、γのいずれか）。記録部１９０_ｎは、数値Ａ_１，…，Ａ_Ｋの断片などを記録する。

選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００_１、他方を第２の秘密分散装置１００_２、選択されなかった秘密分散装置を第３の秘密分散装置１００_３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００_１が記録するｋ番目の断片をａ_ｋ１＝（ａ_ｋ３１，ａ_ｋ１２）、第２の秘密分散装置１００_２が記録するｋ番目の断片をａ_ｋ２＝（ａ_ｋ１２，ａ_ｋ２３）、第３の秘密分散装置１００_３が記録するｋ番目の断片をａ_ｋ３＝（ａ_ｋ２３，ａ_ｋ３１）とする。

断片置換手段は、少なくとも断片置換部１１０_α，１１０_β，１１０_γを含んで構成される。断片置換手段は、第１の秘密分散装置１００_１または第２の秘密分散装置１００_２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００_１が記録する断片ａ_{π（ｋ）１}をｋ番目の断片にし、第２の秘密分散装置１００_２が記録する断片ａ_{π（ｋ）２}をｋ番目の断片にする（Ｓ１１０）。実施例１で説明した通り、全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffleなどを用いて作成すればよい。

再分散手段は、少なくとも再分散部１２０_α，１２０_β，１２０_γを含んで構成される。図７に示すように再分散部１２０_ｎは、第１乱数生成部１２１_ｎ、第２乱数生成部１２２_ｎ、第１計算部１２３_ｎ、第２計算部１２４_ｎ、第３計算部１２５_ｎ、断片更新部１２６_ｎを備えている。

第１の秘密分散装置１００_１の第１乱数生成部１２１_１は、ｋ番目の断片の再分散化のために、ランダムな値であるｂ_ｋ３１を生成し、第３の秘密分散装置１００_３に送信する（Ｓ１２１）。第２の秘密分散装置１００_２の第２乱数生成部１２２_２は、ｋ番目の断片の再分散化のために、ランダムな値であるｂ_ｋ２３を生成し、第３の秘密分散装置１００_３に送信する（Ｓ１２２）。第１の秘密分散装置１００_１の第１計算部１２３_１は、ｋ番目の断片の再分散化のために、ｘ_ｋ＝ｂ_ｋ３１−ａ_{π（ｋ）３１}を計算し、第２の秘密分散装置１００_２に送信する（Ｓ１２３）。

第２の秘密分散装置１００_２の第２計算部１２４_２は、ｋ番目の断片の再分散化のために、ｙ_ｋ＝ｂ_ｋ２３−ａ_{π（ｋ）２３}を計算し、第１の秘密分散装置１００_１に送信する（Ｓ１２４）。第１の秘密分散装置１００_１の第３計算部１２５_１と第２の秘密分散装置１００_２の第３計算部１２５_２は、ｋ番目の断片の再分散化のために、それぞれｂ_ｋ１２＝ａ_{π（ｋ）１２}−ｘ_ｋ−ｙ_ｋを計算する（Ｓ１２５）。第１の秘密分散装置１００_１の断片更新部１２６_１は（ｂ_ｋ３１，ｂ_ｋ１２）を断片ｂ_ｋ１とし、第２の秘密分散装置１００_２の断片更新部１２６_２は（ｂ_ｋ１２，ｂ_ｋ２３）を断片ｂ_ｋ２とし、第３の秘密分散装置１００_３の断片更新部１２６_３は（ｂ_ｋ２３，ｂ_ｋ３１）を断片ｂ_ｋ３とする（Ｓ１２６）。なお、各秘密分散装置１００_ｎの記録部１９０_ｎは、断片ｂ_ｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂ_ｋｎが数値Ｂ_ｋの断片であるという情報も記録する。実施例１と同じように、断片ｂ_ｋ１，ｂ_ｋ２，ｂ_ｋ３は、数値Ｂ_ｋの断片である。つまり、ステップＳ１２１〜Ｓ１２６が、ステップＳ１２０に相当する。

また、数値Ｂ_１，…，Ｂ_Ｋを新しい数値Ａ_１，…，Ａ_Ｋとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。そして、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ_１，…，Ａ_Ｋと対応つけることができない数値Ｂ_１，…，Ｂ_Ｋを得ることができる。本実施例では、断片置換手段が選択する秘密分散装置を、｛１００_α，１００_β｝，｛１００_β，１００_γ｝，｛１００_γ，１００_α｝のように選択すれば、全ての秘密分散装置が選ばれなかったことがある状態にできる。

したがって、実施例３の秘密分散システムは、実施例１と同様の効果が得られる。なお、ソートも行う場合は、秘密分散装置１００_ｎは、比較部２１０_ｎと交換部２２０_ｎも備える。具体的なソートの処理については実施例１と同じである。

［限定シャッフルの変形例］
Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ^（１），…，Ａ^（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ^（ｍ）＝(Ａ_１ ^（ｍ），…，Ａ_Ｋ ^（ｍ）)とする。また、ベクトルＡ^（１），…，Ａ^（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）は対応付けられたｋ番目の数値群である。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、数値Ａ_ｋ ^（ｍ）＝ａ_ｋαβ ^（ｍ）＋ａ_ｋβγ ^（ｍ）＋ａ_ｋγα ^（ｍ）（ただし、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、の３つの断片を（ａ_ｋγα ^（ｍ），ａ_ｋαβ ^（ｍ））、（ａ_ｋαβ ^（ｍ），ａ_ｋβγ ^（ｍ））、（ａ_ｋβγ ^（ｍ），ａ_ｋγα ^（ｍ））とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。

秘密分散システムの機能構成例は図６と同じであり、再分散部の詳細な構成例は図７と同じであり、秘密分散の処理フローは図８と同じである。秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。秘密分散装置１００_ｎは、少なくとも断片置換部１１０_ｎと再分散部１２０_ｎと記録部１９０_ｎを備える（ただし、ｎはα、β、γのいずれか）。ただし、各構成部とその処理は以下のようになる。

記録部１９０_ｎは断片ａ_１ｎ ^（１），…，ａ_Ｋｎ ^（１），…，ａ_１ｎ ^（Ｍ），…，ａ_Ｋｎ ^（Ｍ）などを記録する。また、記録部１９０_ｎは、自身が記録している断片ａ_ｋｎが数値Ａ_ｋの何番目の断片なのかに関する情報も記録する。

選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００_１、他方を第２の秘密分散装置１００_２、選択されなかった秘密分散装置を第３の秘密分散装置１００_３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００_１が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ１ ^（ｍ）＝（ａ_ｋ３１ ^（ｍ），ａ_ｋ１２ ^（ｍ））、第２の秘密分散装置１００_２が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ２ ^（ｍ）＝（ａ_ｋ１２ ^（ｍ），ａ_ｋ２３ ^（ｍ））、第３の秘密分散装置１００_３が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ３ ^（ｍ）＝（ａ_ｋ２３ ^（ｍ），ａ_ｋ３１ ^（ｍ））とする。

断片置換手段は、少なくとも断片置換部１１０_α，１１０_β，１１０_γを含んで構成される。断片置換手段は、第１の秘密分散装置１００_１または第２の秘密分散装置１００_２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００_１が記録する断片ａ_{π（ｋ）１} ^（１），…，ａ_{π（ｋ）１} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置１００_２が記録する断片ａ_{π（ｋ）２} ^（１），…，ａ_{π（ｋ）２} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。

再分散手段は、少なくとも再分散部１２０_α，１２０_β，１２０_γを含んで構成される。図７に示すように再分散部１２０_ｎは、第１乱数生成部１２１_ｎ、第２乱数生成部１２２_ｎ、第１計算部１２３_ｎ、第２計算部１２４_ｎ、第３計算部１２５_ｎ、断片更新部１２６_ｎを備えている。

第１の秘密分散装置１００_１の第１乱数生成部１２１_１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ３１ ^（１），…，ｂ_ｋ３１ ^（Ｍ）を生成し、第３の秘密分散装置１００_３に送信する（Ｓ１２１）。第２の秘密分散装置１００_２の第２乱数生成部１２２_２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ２３ ^（１），…，ｂ_ｋ２３ ^（Ｍ）を生成し、第３の秘密分散装置１００_３に送信する（Ｓ１２２）。第１の秘密分散装置１００_１の第１計算部１２３_１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘ_ｋ ^（ｍ）＝ｂ_ｋ３１ ^（ｍ）−ａ_{π（ｋ）３１} ^（ｍ）を計算し、ｘ_ｋ ^（１），…，ｘ_ｋ ^（Ｍ）を第２の秘密分散装置１００_２に送信する（Ｓ１２３）。

第２の秘密分散装置１００_２の第２計算部１２４_２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙ_ｋ ^（ｍ）＝ｂ_ｋ２３ ^（ｍ）−ａ_{π（ｋ）２３} ^（ｍ）を計算し、ｙ_ｋ ^（１），…，ｙ_ｋ ^（Ｍ）を第１の秘密分散装置１００_１に送信する（Ｓ１２４）。第１の秘密分散装置１００_１の第３計算部１２５_１と第２の秘密分散装置１００_２の第３計算部１２５_２は、対応付けられたｋ番目の数値群の断片の再分散化のために、それぞれｍ＝１〜Ｍについてｂ_ｋ１２ ^（ｍ）＝ａ_{π（ｋ）１２} ^（ｍ）−ｘ_ｋ ^（ｍ）−ｙ_ｋ ^（ｍ）を計算する（Ｓ１２５）。第１の秘密分散装置１００_１の断片更新部１２６_１は（ｂ_ｋ３１ ^（ｍ），ｂ_ｋ１２ ^（ｍ））を断片ｂ_ｋ１ ^（ｍ）とし、第２の秘密分散装置１００_２の断片更新部１２６_２は（ｂ_ｋ１２ ^（ｍ），ｂ_ｋ２３ ^（ｍ））を断片ｂ_ｋ２ ^（ｍ）とし、第３の秘密分散装置１００_３の断片更新部１２６_３は（ｂ_ｋ２３ ^（ｍ），ｂ_ｋ３１ ^（ｍ））を断片ｂ_ｋ３ ^（ｍ）とする（Ｓ１２６）。なお、各秘密分散装置１００_ｎの記録部１９０_ｎは、断片ｂ_ｋｎ ^（ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂ_ｋｎ ^（ｍ）が数値Ｂ_ｋ ^（ｍ）の断片であるという情報も記録する。実施例１と同じように、断片ｂ_ｋ１ ^（ｍ），ｂ_ｋ２ ^（ｍ），ｂ_ｋ３ ^（ｍ）は、数値Ｂ_ｋ ^（ｍ）の断片である。つまり、ステップＳ１２１〜Ｓ１２６が、ステップＳ１２０に相当する。

また、数値Ｂ_１ ^（１），…，Ｂ_Ｋ ^（１），…，Ｂ_１ ^（Ｍ），…，Ｂ_Ｋ ^（Ｍ）を新しい数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。

このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。

実施例４でも、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。また、実施例４では、実施例２と同じように不正検出機能を具備した例を説明する。

［限定シャッフル］
実施例４の秘密分散システムの構成も図６に示す。なお、本実施例の秘密分散装置１００_ｎは、点線で示された構成部も備えている。図９に改ざん検出部の詳細な構造を示す。図１０に実施例４の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００_α，１００_β，１００_γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａ_ｋ＝ａ_ｋαβ＋ａ_ｋβγ＋ａ_ｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａ_ｋγα，ａ_ｋαβ）、（ａ_ｋαβ，ａ_ｋβγ）、（ａ_ｋβγ，ａ_ｋγα）とする。

本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。秘密分散装置１００_ｎは、初期情報分散部１３０_ｎ、初期乗算部１４０_ｎ、断片置換部１１０_ｎ、再分散部１２０_ｎ、確認分散部１５０_ｎ、確認乗算部１６０_ｎ、改ざん検出部１７０_ｎ、記録部１９０_ｎを備える（ただし、ｎはα、β、γのいずれか）。記録部１９０_ｎは、数値Ａ_１，…，Ａ_Ｋの断片などを記録する。

選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００_１、他方を第２の秘密分散装置１００_２、選択されなかった秘密分散装置を第３の秘密分散装置１００_３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００_１が記録するｋ番目の断片をａ_ｋ１＝（ａ_ｋ３１，ａ_ｋ１２）、第２の秘密分散装置１００_２が記録するｋ番目の断片をａ_ｋ２＝（ａ_ｋ１２，ａ_ｋ２３）、第３の秘密分散装置１００_３が記録するｋ番目の断片をａ_ｋ３＝（ａ_ｋ２３，ａ_ｋ３１）とする。

初期情報分散手段は、初期情報分散部１３０_α，１３０_β，１３０_γで構成される。初期情報分散部１３０_α，１３０_β，１３０_γは、秘密分散装置１００_α，１００_β，１００_γのどれも知らないＫ個の数値Ｐ_１，…，Ｐ_Ｋそれぞれの断片ｐ_ｋｎを秘密計算によって求め、秘密分散装置１００_ｎに記録する（Ｓ１３０）。例えば、第１の秘密分散装置１００_１でＫ個のランダムな値Ｒ^（１） _１，…，Ｒ^（１） _Ｋを生成し、第２の秘密分散装置１００_２でＫ個のランダムな値Ｒ^（２） _１，…，Ｒ^（２） _Ｋを生成する。そして、秘密分散装置１００_１，１００_２，１００_３で、Ｒ^（１） _ｋの断片（ｒ^（１） _ｋ３１，ｒ^（１） _ｋ１２）、（ｒ^（１） _ｋ１２，ｒ^（１） _ｋ２３）、（ｒ^（１） _ｋ２３，ｒ^（１） _ｋ３１）と、Ｒ^（２） _ｋの断片（ｒ^（２） _ｋ３１，ｒ^（２） _ｋ１２）、（ｒ^（２） _ｋ１２，ｒ^（２） _ｋ２３）、（ｒ^（２） _ｋ２３，ｒ^（２） _ｋ３１）とを秘密分散して記録する。その後、秘密分散装置１００_１，１００_２，１００_３で、Ｐ_ｋ＝Ｒ^（１） _ｋ＋Ｒ^（２） _ｋである数値Ｐ_ｋの断片（ｐ_ｋ３１，ｐ_ｋ１２）、（ｐ_ｋ１２，ｐ_ｋ２３）、（ｐ_ｋ２３，ｐ_ｋ３１）を秘密計算によって求め、秘密分散装置１００_１，１００_２，１００_３に分散して記録する。このような処理によって、全ての秘密分散装置１００_α，１００_β，１００_γが知らない数値の断片を分散して記録できる。

初期乗算手段は、初期乗算部１４０_α，１４０_β，１４０_γで構成される。初期乗算部１４０_α，１４０_β，１４０_γは、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋである数値Ｓ_ｋの断片（ｓ_ｋγα，ｓ_ｋαβ）、（ｓ_ｋαβ，ｓ_ｋβγ）、（ｓ_ｋβγ，ｓ_ｋγα）を秘密計算によって求め、秘密分散装置１００_α，１００_β，１００_γに分散して記録する（Ｓ１４０）。

断片置換手段と再分散手段は、実施例３と同じである。断片置換手段と再分散手段によって、秘密分散装置１００_α，１００_β，１００_γに数値Ｂ_ｋの断片として断片ｂ_ｋ１、ｂ_ｋ２、ｂ_ｋ３が記録される。確認分散手段は、確認分散部１５０_α，１５０_β，１５０_γで構成される。確認分散部１５０_α，１５０_β，１５０_γは、ｋ＝１〜Ｋについて、Ｑ_ｋ＝Ｐ_π（ｋ）である数値Ｑ_ｋの断片（ｑ_ｋγα，ｑ_ｋαβ）、（ｑ_ｋαβ，ｑ_ｋβγ）、（ｑ_ｋβγ，ｑ_ｋγα）を秘密計算によって生成し、秘密分散装置１００_α，１００_β，１００_γに分散して記録する（Ｓ１５０）。例えば、ステップＳ１３０で第１の秘密分散装置１００_１が生成した数値Ｒ^（１） _π（ｋ）の別の断片（ｒ’^（１） _{π（ｋ）３１}，ｒ’^（１） _{π（ｋ）１２}）、（ｒ’^（１） _{π（ｋ）１２}，ｒ’^（１） _{π（ｋ）２３}）、（ｒ’^（１） _{π（ｋ）２３}，ｒ’^（１） _{π（ｋ）３１}）と、第２の秘密分散装置１００_２が生成した数値Ｒ^（２） _π（ｋ）の別の断片（ｒ’^（２） _{π（ｋ）３１}，ｒ’^（２） _{π（ｋ）１２}）、（ｒ’^（２） _{π（ｋ）１２}，ｒ’^（２） _{π（ｋ）２３}）、（ｒ’^（２） _{π（ｋ）２３}，ｒ’^（２） _{π（ｋ）３１}）とを秘密分散して記録する。その後、秘密分散装置１００_１，１００_２，１００_３で、Ｑ_ｋ＝Ｒ^（１） _π（ｋ）＋Ｒ^（２） _π（ｋ）である数値Ｑ_ｋの断片（ｑ_ｋ３１，ｑ_ｋ１２）、（ｑ_ｋ１２，ｑ_ｋ２３）、（ｑ_ｋ２３，ｑ_ｋ３１）を別の断片を用いて秘密計算によって求め、秘密分散装置１００_１，１００_２，１００_３に分散して記録する。このような処理によって、Ｑ_ｋ＝Ｐ_π（ｋ）であり、かつ、全ての秘密分散装置１００_α，１００_β，１００_γが知らない数値の断片を分散して記録できる。

確認乗算手段は、確認乗算部１６０_α，１６０_β，１６０_γで構成される。確認乗算部１６０_α，１６０_β，１６０_γは、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋである数値Ｔ_ｋの断片（ｔ_ｋγα，ｔ_ｋαβ）、（ｔ_ｋαβ，ｔ_ｋβγ）、（ｔ_ｋβγ，ｔ_ｋγα）を秘密計算によって求め、秘密分散装置１００_α，１００_β，１００_γに分散して記録する（Ｓ１６０）。

改ざん検出手段は、改ざん検出部１７０_α，１７０_β，１７０_γで構成される。また、図９に示すように、改ざん検出部１７０_ｎは、第３乱数生成部１７１_ｎ、第４乱数生成部１７２_ｎ、第４計算部１７３_ｎ、第５計算部１７４_ｎ、第１確認部１７５_ｎ、第６計算部１７６_ｎ、第７計算部１７７_ｎ、第２確認部１７８_ｎを備える。改ざん検出手段は、秘密分散装置１００_α，１００_β，１００_γが第１の秘密分散装置１００_１、第２の秘密分散装置１００_２、第３の秘密分散装置１００_３のいずれの装置として動作するかにしたがって、以下のように処理を行う。

第１の秘密分散装置１００_１の第３乱数生成部１７１_１は、ランダムな値であるｕ_ｋを生成し、第２の秘密分散装置１００_２に送信する（Ｓ１７１）。第２の秘密分散装置１００_２の第４乱数生成部１７２_２は、ランダムな値であるｖ_ｋを生成し、第１の秘密分散装置１００_１に送信する（Ｓ１７２）。第１の秘密分散装置１００_１の第４計算部１７３_１は、ｄ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置１００_３に送信する（Ｓ１７３）。

第２の秘密分散装置１００_２の第５計算部１７４_２は、ｅ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置１００_３に送信する（Ｓ１７４）。第３の秘密分散装置１００_３の第１確認部１７５_３は、ｄ_ｋ＝ｅ_ｋであることを確認し、異なっていれば処理を中止する（Ｓ１７５）。

第１の秘密分散装置１００_１の第６計算部１７６_１は、ｆ_ｋ＝ｓ_{π（ｋ）３１}−ｔ_ｋ３１＋ｕ_ｋを計算し、第３の秘密分散装置１００_３に送信する（Ｓ１７６）。第２の秘密分散装置１００_２の第７計算部１７７_２は、ｇ_ｋ＝ｓ_{π（ｋ）２３}−ｔ_ｋ２３＋ｖ_ｋを計算し、第３の秘密分散装置１００_３に送信する（Ｓ１７７）。第３の秘密分散装置１００_３の第２確認部１７８_３は、ｆ_ｋ＋ｇ_ｋ＋ｄ_ｋ＝０であることを確認し、異なっていれば処理を中止する（Ｓ１７８）。また、数値Ｂ_１，…，Ｂ_Ｋを新しい数値Ａ_１，…，Ａ_Ｋとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。

実施例４の秘密分散システムによれば、実施例３の秘密分散装置と同じ効果が得られると共に、数値Ａ_１，…，Ａ_Ｋと数値Ｂ_１，…，Ｂ_Ｋとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００_ｎは、比較部２１０_ｎと交換部２２０_ｎも備える。具体的なソートの処理については実施例１と同じである。

［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、実施例３、４の秘密分散システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、秘密分散装置１００_α，１００_β，１００_γが分散して記録する数値Ａの断片を（ａ_γα，ａ_αβ）、（ａ_αβ，ａ_βγ）、（ａ_βγ，ａ_γα）、数値Ｂの断片を（ｂ_γα，ｂ_αβ）、（ｂ_αβ，ｂ_βγ）、（ｂ_βγ，ｂ_γα）、数値Ｃの断片を（ｃ_γα，ｃ_αβ）、（ｃ_αβ，ｃ_βγ）、（ｃ_βγ，ｃ_γα）とする。

数値Ａの秘密分散
（１）乱数ａ_αβ，ａ_βγを生成する。
（２）ａ_γα＝Ａ−ａ_αβ−ａ_βγを計算し、断片を（ａ_γα，ａ_αβ）、（ａ_αβ，ａ_βγ）、（ａ_βγ，ａ_γα）とし、秘密分散装置１００_α，１００_β，１００_γに分散して記録する。

数値Ａの復元
（１）秘密分散装置１００_αは秘密分散装置１００_βにａ_γαを送信し、秘密分散装置１００_γにａ_αβを送信する。秘密分散装置１００_βは秘密分散装置１００_γにａ_αβを送信し、秘密分散装置１００_αにａ_βγを送信する。秘密分散装置１００_γは秘密分散装置１００_αにａ_βγを送信し、秘密分散装置１００_βにａ_γαを送信する。
（２）秘密分散装置１００_αは秘密分散装置１００_βから受信したａ_βγと秘密分散装置１００_γから受信したａ_βγとが一致していれば、ａ_αβ＋ａ_βγ＋ａ_γαを計算して数値Ａを復元する。秘密分散装置１００_βは秘密分散装置１００_γから受信したａ_γαと秘密分散装置１００_αから受信したａ_γαとが一致していれば、ａ_αβ＋ａ_βγ＋ａ_γαを計算して数値Ａを復元する。秘密分散装置１００_γは秘密分散装置１００_αから受信したａ_αβと秘密分散装置１００_βから受信したａ_αβとが一致していれば、ａ_αβ＋ａ_βγ＋ａ_γαを計算して数値Ａを復元する。

Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密分散装置１００_αは（ｃ_γα，ｃ_αβ）＝（ａ_γα＋ｂ_γα，ａ_αβ＋ｂ_αβ）を計算して記録し、秘密分散装置１００_βは（ｃ_αβ，ｃ_βγ）＝（ａ_αβ＋ｂ_αβ，ａ_βγ＋ｂ_βγ）を計算して記録し、秘密分散装置１００_γは（ｃ_βγ，ｃ_γα）＝（ａ_βγ＋ｂ_βγ，ａ_γα＋ｂ_γα）を計算して記録する。

Ｃ＝Ａ−Ｂの秘密計算
（１）秘密分散装置１００_αは（ｃ_γα，ｃ_αβ）＝（ａ_γα−ｂ_γα，ａ_αβ−ｂ_αβ）を計算して記録し、秘密分散装置１００_βは（ｃ_αβ，ｃ_βγ）＝（ａ_αβ−ｂ_αβ，ａ_βγ−ｂ_βγ）を計算して記録し、秘密分散装置１００_γは（ｃ_βγ，ｃ_γα）＝（ａ_βγ−ｂ_βγ，ａ_γα−ｂ_γα）を計算して記録する。

Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００_αは（ｃ_γα，ｃ_αβ）＝（ａ_γα＋Ｓ，ａ_αβ）を計算して記録し、秘密分散装置１００_γは（ｃ_βγ，ｃ_γα）＝（ａ_βγ，ａ_γα＋Ｓ）を計算して記録する。秘密分散装置１００_βの処理はない。

Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００_αは（ｃ_γα，ｃ_αβ）＝（ａ_γαＳ，ａ_αβＳ）を計算して記録し、秘密分散装置１００_βは（ｃ_αβ，ｃ_βγ）＝（ａ_αβＳ，ａ_βγＳ）を計算して記録し、秘密分散装置１００_γは（ｃ_βγ，ｃ_γα）＝（ａ_βγＳ，ａ_γαＳ）を計算して記録する。

Ｃ＝ＡＢの秘密計算
（１）秘密分散装置１００_αは、乱数ｒ_１，ｒ_２，ｃ_γαを生成し、ｃ_αβ＝（ａ_γα＋ａ_αβ）（ｂ_γα＋ｂ_αβ）−ｒ_１−ｒ_２−ｃ_γαを計算する。そして、秘密分散装置１００_αは、秘密分散装置１００_βに（ｒ_１，ｃ_αβ）を、秘密分散装置１００_γに（ｒ_２，ｃ_γα）を送信する。
（２）秘密分散装置１００_βは、ｙ＝ａ_αβｂ_βγ＋ａ_βγｂ_αβ＋ｒ_１を計算し、秘密分散装置１００_γに送信する。
（３）秘密分散装置１００_γは、ｚ＝ａ_βγｂ_γα＋ａ_γαｂ_βγ＋ｒ_２を計算し、秘密分散装置１００_αに送信する。
（４）秘密分散装置１００_βと秘密分散装置１００_γは、それぞれｃ_βγ＝ｙ＋ｚ＋ａ_βγｂ_βγを計算する。
（５）秘密分散装置１００_αは（ｃ_γα，ｃ_αβ）を記録し、秘密分散装置１００_βは（ｃ_αβ，ｃ_βγ）を記録し、秘密分散装置１００_γは（ｃ_βγ，ｃ_γα）を記録する。

［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (14)

1. Ｎ個の秘密分散装置で構成された秘密分散システムであって、
   Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）を対応付けられたｋ番目の数値群、ａ_ｋｎ ^（ｍ）をｎ番目の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片、ｉをＮ個の秘密分散装置の中から選択された秘密分散装置を示すための１以上Ｎ以下の中の一部の整数とし、
   ２以上Ｎ未満の数の秘密分散装置を選択する選択手段と、
   前記選択手段で選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択されたｉ番目の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする断片置換手段と、
   前記断片置換手段によって置換された数値Ａ_π（ｋ） ^（１），…，Ａ_π（ｋ） ^（Ｍ）に対応する断片ａ_{π（ｋ）ｉ} ^（１），…，ａ_{π（ｋ）ｉ} ^（Ｍ）を用いて再分散化して新しい断片ｂ_ｋ１ ^（１），…，ｂ_ｋＮ ^（１），…，ｂ_ｋ１ ^（Ｍ），…，ｂ_ｋＮ ^（Ｍ）を求め、数値Ｂ_ｋ ^（１），…，Ｂ_ｋ ^（Ｍ）の断片とする再分散手段と、
   を備える秘密分散システム。
2. 請求項１記載の秘密分散システムであって、
   Ｍ＝１である秘密分散システム。
3. 請求項２記載の秘密分散システムであって、
   Ｎ個の秘密分散装置のどれも知らないＫ個の数値Ｐ_１，…，Ｐ_Ｋそれぞれの断片を秘密計算によって求め、ｎ番目の秘密分散装置に断片ｐ_１ｎ，…，ｐ_Ｋｎを記録する初期情報分散手段と、
   Ｎ個の秘密分散装置で、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋ ^（１）である数値Ｓ_ｋの断片ｓ_ｋ１，…，ｓ_ｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する初期乗算手段と、
   ｋ＝１〜Ｋについて、Ｑ_ｋ＝Ｐ_π（ｋ）である数値Ｑ_ｋの断片ｑ_ｋ１，…，ｑ_ｋＮを秘密計算によって生成し、Ｎ個の秘密分散装置に分散して記録する確認分散手段と、
   Ｎ個の秘密分散装置で、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋ ^（１）である数値Ｔ_ｋの断片ｔ_ｋ１，…，ｔ_ｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する確認乗算手段と、
   ｋ＝１〜Ｋについて、Ｔ_ｋ＝Ｓ_π（ｋ）であることを確認する改ざん検出手段、
   も備える秘密分散システム。
4. 請求項１記載の秘密分散システムであって、
   Ｎ＝３、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａ_ｋ ^（ｍ）＝ａ_ｋαβ ^（ｍ）＋ａ_ｋβγ ^（ｍ）＋ａ_ｋγα ^（ｍ）の３つの断片を（ａ_ｋγα ^（ｍ），ａ_ｋαβ ^（ｍ））と（ａ_ｋαβ ^（ｍ），ａ_ｋβγ ^（ｍ））と（ａ_ｋβγ ^（ｍ），ａ_ｋγα ^（ｍ））、前記の３つの断片は３つの秘密分散装置に分散して記録されているとし、
   前記選択手段は、２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置とし、
   前記断片置換手段は、第１の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ１ ^（ｍ）＝（ａ_ｋ３１ ^（ｍ），ａ_ｋ１２ ^（ｍ））、第２の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ２ ^（ｍ）＝（ａ_ｋ１２ ^（ｍ），ａ_ｋ２３ ^（ｍ））、第３の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ３ ^（ｍ）＝（ａ_ｋ２３ ^（ｍ），ａ_ｋ３１ ^（ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）１} ^（１），…，ａ_{π（ｋ）１} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）２} ^（１），…，ａ_{π（ｋ）２} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にし、
   前記再分散手段として、各秘密分散装置が、
   第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ３１ ^（１），…，ｂ_ｋ３１ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
   第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ２３ ^（１），…，ｂ_ｋ２３ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
   第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘ_ｋ ^（ｍ）＝ｂ_ｋ３１ ^（ｍ）−ａ_{π（ｋ）３１} ^（ｍ）を計算し、ｘ_ｋ ^（１），…，ｘ_ｋ ^（Ｍ）を第２の秘密分散装置に送信する第１計算部と、
   第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙ_ｋ ^（ｍ）＝ｂ_ｋ２３ ^（ｍ）−ａ_{π（ｋ）２３} ^（ｍ）を計算し、ｙ_ｋ ^（１），…，ｙ_ｋ ^（Ｍ）を第１の秘密分散装置に送信する第２計算部と、
   第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂ_ｋ１２ ^（ｍ）＝ａ_{π（ｋ）１２} ^（ｍ）−ｘ_ｋ ^（ｍ）−ｙ_ｋ ^（ｍ）を計算する第３計算部と、
   第１の秘密分散装置のときには（ｂ_ｋ３１ ^（ｍ），ｂ_ｋ１２ ^（ｍ））を断片ｂ_ｋ１ ^（ｍ）とし、第２の秘密分散装置のときには（ｂ_ｋ１２ ^（ｍ），ｂ_ｋ２３ ^（ｍ））を断片ｂ_ｋ２ ^（ｍ）とし、第３の秘密分散装置のときには（ｂ_ｋ２３ ^（ｍ），ｂ_ｋ３１ ^（ｍ））を断片ｂ_ｋ３ ^（ｍ）とする断片更新部と、
   を備え、断片ｂ_ｋ１ ^（ｍ）、ｂ_ｋ２ ^（ｍ）、ｂ_ｋ３ ^（ｍ）を数値Ｂ_ｋ ^（ｍ）の断片として記録する
   秘密分散システム。
5. 請求項４記載の秘密分散システムであって、
   Ｍ＝１である秘密分散システム。
6. 請求項５記載の秘密分散システムであって、
   第１の秘密分散装置でＫ個のランダムな値Ｒ^（１） _１，…，Ｒ^（１） _Ｋを生成し、第２の秘密分散装置でＫ個のランダムな値Ｒ^（２） _１，…，Ｒ^（２） _Ｋを生成し、前記３つの秘密分散装置で、Ｒ^（１） _ｋの断片（ｒ^（１） _ｋ３１，ｒ^（１） _ｋ１２）、（ｒ^（１） _ｋ１２，ｒ^（１） _ｋ２３）、（ｒ^（１） _ｋ２３，ｒ^（１） _ｋ３１）と、Ｒ^（２） _ｋの断片（ｒ^（２） _ｋ３１，ｒ^（２） _ｋ１２）、（ｒ^（２） _ｋ１２，ｒ^（２） _ｋ２３）、（ｒ^（２） _ｋ２３，ｒ^（２） _ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置で、Ｐ_ｋ＝Ｒ^（１） _ｋ＋Ｒ^（２） _ｋである数値Ｐ_ｋの断片（ｐ_ｋ３１，ｐ_ｋ１２）、（ｐ_ｋ１２，ｐ_ｋ２３）、（ｐ_ｋ２３，ｐ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散手段と、
   前記３つの秘密分散装置で、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋ ^（１）である数値Ｓ_ｋの断片（ｓ_ｋ３１，ｓ_ｋ１２）、（ｓ_ｋ１２，ｓ_ｋ２３）、（ｓ_ｋ２３，ｓ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算手段と、
   前記の数値Ｒ^（１） _π（ｋ）の別の断片（ｒ’^（１） _{π（ｋ）３１}，ｒ’^（１） _{π（ｋ）１２}）、（ｒ’^（１） _{π（ｋ）１２}，ｒ’^（１） _{π（ｋ）２３}）、（ｒ’^（１） _{π（ｋ）２３}，ｒ’^（１） _{π（ｋ）３１}）と、前記の数値Ｒ^（２） _π（ｋ）の別の断片（ｒ’^（２） _{π（ｋ）３１}，ｒ’^（２） _{π（ｋ）１２}）、（ｒ’^（２） _{π（ｋ）１２}，ｒ’^（２） _{π（ｋ）２３}）、（ｒ’^（２） _{π（ｋ）２３}，ｒ’^（２） _{π（ｋ）３１}）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑ_ｋ＝Ｒ^（１） _π（ｋ）＋Ｒ^（２） _π（ｋ）である数値Ｑ_ｋの断片（ｑ_ｋ３１，ｑ_ｋ１２）、（ｑ_ｋ１２，ｑ_ｋ２３）、（ｑ_ｋ２３，ｑ_ｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散手段と、
   前記３つの秘密分散装置で、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋ ^（１）である数値Ｔ_ｋの断片（ｔ_ｋ３１，ｔ_ｋ１２）、（ｔ_ｋ１２，ｔ_ｋ２３）、（ｔ_ｋ２３，ｔ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算手段と、
   第１の秘密分散装置が記録する断片をｓ_ｋ１＝（ｓ_ｋ３１，ｓ_ｋ１２）、ｔ_ｋ１＝（ｔ_ｋ３１，ｔ_ｋ１２）とし、第２の秘密分散装置が記録する断片をｓ_ｋ２＝（ｓ_ｋ１２，ｓ_ｋ２３）、ｔ_ｋ２＝（ｔ_ｋ１２，ｔ_ｋ２３）とし、第３の秘密分散装置が記録する断片をｓ_ｋ３＝（ｓ_ｋ２３，ｓ_ｋ３１）、ｔ_ｋ３＝（ｔ_ｋ２３，ｔ_ｋ３１）とし、
   各秘密分散装置が、
   第１の秘密分散装置のときに、ランダムな値であるｕ_ｋを生成し、第２の秘密分散装置に送信する第３乱数生成部と、
   第２の秘密分散装置のときに、ランダムな値であるｖ_ｋを生成し、第１の秘密分散装置に送信する第４乱数生成部と、
   第１の秘密分散装置のときに、ｄ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置に送信する第４計算部と、
   第２の秘密分散装置のときに、ｅ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置に送信する第５計算部と、
   第３の秘密分散装置のときに、ｄ_ｋ＝ｅ_ｋであることを確認し、異なっていれば処理を中止する第１確認部と、
   第１の秘密分散装置のときに、ｆ_ｋ＝ｓ_{π（ｋ）３１}−ｔ_ｋ３１＋ｕ_ｋを計算し、第３の秘密分散装置に送信する第６計算部と、
   第２の秘密分散装置のときに、ｇ_ｋ＝ｓ_{π（ｋ）２３}−ｔ_ｋ２３＋ｖ_ｋを計算し、第３の秘密分散装置に送信する第７計算部と、
   第３の秘密分散装置のときに、ｆ_ｋ＋ｇ_ｋ＋ｄ_ｋ＝０であることを確認し、異なっていれば処理を中止する第２確認部と、
   を備える
   秘密分散システム。
7. 請求項４記載の秘密分散システムの中の秘密分散装置であって、
   第１の秘密分散装置として選ばれたときには記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ１ ^（ｍ）＝（ａ_ｋ３１ ^（ｍ），ａ_ｋ１２ ^（ｍ））、第２の秘密分散装置として選ばれたときには記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ２ ^（ｍ）＝（ａ_ｋ１２ ^（ｍ），ａ_ｋ２３ ^（ｍ））、第３の秘密分散装置として選ばれたときには記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ３ ^（ｍ）＝（ａ_ｋ２３ ^（ｍ），ａ_ｋ３１ ^（ｍ））とし、
   第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、対応付けられたπ（ｋ）番目の数値群の断片を対応付けられたｋ番目の数値群の断片にする断片置換部と、
   第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ３１ ^（１），…，ｂ_ｋ３１ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
   第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ２３ ^（１），…，ｂ_ｋ２３ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
   第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘ_ｋ ^（ｍ）＝ｂ_ｋ３１ ^（ｍ）−ａ_{π（ｋ）３１} ^（ｍ）を計算し、ｘ_ｋ ^（１），…，ｘ_ｋ ^（Ｍ）を第２の秘密分散装置に送信する第１計算部と、
   第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙ_ｋ ^（ｍ）＝ｂ_ｋ２３ ^（ｍ）−ａ_{π（ｋ）２３} ^（ｍ）を計算し、ｙ_ｋ ^（１），…，ｙ_ｋ ^（Ｍ）を第１の秘密分散装置に送信する第２計算部と、
   第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂ_ｋ１２ ^（ｍ）＝ａ_{π（ｋ）１２} ^（ｍ）−ｘ_ｋ ^（ｍ）−ｙ_ｋ ^（ｍ）を計算する第３計算部と、
   第１の秘密分散装置のときには（ｂ_ｋ３１ ^（ｍ），ｂ_ｋ１２ ^（ｍ））を断片ｂ_ｋ１ ^（ｍ）とし、第２の秘密分散装置のときには（ｂ_ｋ１２ ^（ｍ），ｂ_ｋ２３ ^（ｍ））を断片ｂ_ｋ２ ^（ｍ）とし、第３の秘密分散装置のときには（ｂ_ｋ２３ ^（ｍ），ｂ_ｋ３１ ^（ｍ））を断片ｂ_ｋ３ ^（ｍ）とする断片更新部と、
   を備える秘密分散装置。
8. 請求項７記載の秘密分散装置であって、
   Ｍ＝１である秘密分散装置。
9. Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、Ｍを１以上の整数、ｍを１以上Ｍ以下の整数、Ａ_１ ^（１），…，Ａ_Ｋ ^（１），…，Ａ_１ ^（Ｍ），…，Ａ_Ｋ ^（Ｍ）をＫ×Ｍ個の数値、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａ_ｋ ^（ｍ）＝ａ_ｋαβ ^（ｍ）＋ａ_ｋβγ ^（ｍ）＋ａ_ｋγα ^（ｍ）の３つの断片を（ａ_ｋγα ^（ｍ），ａ_ｋαβ ^（ｍ））と（ａ_ｋαβ ^（ｍ），ａ_ｋβγ ^（ｍ））と（ａ_ｋβγ ^（ｍ），ａ_ｋγα ^（ｍ））、対応付けられたｋ番目の数値群をＡ_ｋ ^（１），…，Ａ_ｋ ^（Ｍ）とし、前記断片を分散して記録する３つの秘密分散装置を用いた秘密分散方法であって、
   ２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置する選択ステップと、
   第１の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ１ ^（ｍ）＝（ａ_ｋ３１ ^（ｍ），ａ_ｋ１２ ^（ｍ））、第２の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ２ ^（ｍ）＝（ａ_ｋ１２ ^（ｍ），ａ_ｋ２３ ^（ｍ））、第３の秘密分散装置が記録する数値Ａ_ｋ ^（ｍ）の断片をａ_ｋ３ ^（ｍ）＝（ａ_ｋ２３ ^（ｍ），ａ_ｋ３１ ^（ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）１} ^（１），…，ａ_{π（ｋ）１} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａ_{π（ｋ）２} ^（１），…，ａ_{π（ｋ）２} ^（Ｍ）を対応付けられたｋ番目の数値群の断片にする断片置換ステップと、
   第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ３１ ^（１），…，ｂ_ｋ３１ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成ステップと、
   第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂ_ｋ２３ ^（１），…，ｂ_ｋ２３ ^（Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成ステップと、
   第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｘ_ｋ ^（ｍ）＝ｂ_ｋ３１ ^（ｍ）−ａ_{π（ｋ）３１} ^（ｍ）を計算し、ｘ_ｋ ^（１），…，ｘ_ｋ ^（Ｍ）を第２の秘密分散装置に送信する第１計算ステップと、
   第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｙ_ｋ ^（ｍ）＝ｂ_ｋ２３ ^（ｍ）−ａ_{π（ｋ）２３} ^（ｍ）を計算し、ｙ_ｋ ^（１），…，ｙ_ｋ ^（Ｍ）を第１の秘密分散装置に送信する第２計算ステップと、
   第１の秘密分散装置と第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１〜Ｍについてｂ_ｋ１２ ^（ｍ）＝ａ_{π（ｋ）１２} ^（ｍ）−ｘ_ｋ ^（ｍ）−ｙ_ｋ ^（ｍ）を計算する第３計算ステップと、
   第１の秘密分散装置が（ｂ_ｋ３１ ^（ｍ），ｂ_ｋ１２ ^（ｍ））を断片ｂ_ｋ１ ^（ｍ）とし、第２の秘密分散装置が（ｂ_ｋ１２ ^（ｍ），ｂ_ｋ２３ ^（ｍ））を断片ｂ_ｋ２ ^（ｍ）とし、第３の秘密分散装置が（ｂ_ｋ２３ ^（ｍ），ｂ_ｋ３１ ^（ｍ））を断片ｂ_ｋ３ ^（ｍ）とする断片更新ステップと、
   を有する秘密分散方法。
10. 請求項９記載の秘密分散方法であって、
    Ｍ＝１である秘密分散方法。
11. 請求項１０記載の秘密分散方法であって、
    第１の秘密分散装置がＫ個のランダムな値Ｒ^（１） _１，…，Ｒ^（１） _Ｋを生成し、第２の秘密分散装置がＫ個のランダムな値Ｒ^（２） _１，…，Ｒ^（２） _Ｋを生成し、前記３つの秘密分散装置がＲ^（１） _ｋの断片（ｒ^（１） _ｋ３１，ｒ^（１） _ｋ１２）、（ｒ^（１） _ｋ１２，ｒ^（１） _ｋ２３）、（ｒ^（１） _ｋ２３，ｒ^（１） _ｋ３１）とＲ^（２） _ｋの断片（ｒ^（２） _ｋ３１，ｒ^（２） _ｋ１２）、（ｒ^（２） _ｋ１２，ｒ^（２） _ｋ２３）、（ｒ^（２） _ｋ２３，ｒ^（２） _ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置がＰ_ｋ＝Ｒ^（１） _ｋ＋Ｒ^（２） _ｋである数値Ｐ_ｋの断片（ｐ_ｋ３１，ｐ_ｋ１２）、（ｐ_ｋ１２，ｐ_ｋ２３）、（ｐ_ｋ２３，ｐ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散ステップと、
    前記３つの秘密分散装置が、Ｓ_ｋ＝Ｐ_ｋ×Ａ_ｋ ^（１）である数値Ｓ_ｋの断片（ｓ_ｋ３１，ｓ_ｋ１２）、（ｓ_ｋ１２，ｓ_ｋ２３）、（ｓ_ｋ２３，ｓ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算ステップと、
    前記３つの秘密分散装置が、請求項１０記載の秘密分散システムによって得られた断片ｂ_ｋ１、ｂ_ｋ２、ｂ_ｋ３を数値Ｂ_ｋ ^（１）の断片として記録する秘密分散更新ステップと、
    前記の数値Ｒ^（１） _π（ｋ）の別の断片（ｒ’^（１） _{π（ｋ）３１}，ｒ’^（１） _{π（ｋ）１２}）、（ｒ’^（１） _{π（ｋ）１２}，ｒ’^（１） _{π（ｋ）２３}）、（ｒ’^（１） _{π（ｋ）２３}，ｒ’^（１） _{π（ｋ）３１}）と、前記の数値Ｒ^（２） _π（ｋ）の別の断片（ｒ’^（２） _{π（ｋ）３１}，ｒ’^（２） _{π（ｋ）１２}）、（ｒ’^（２） _{π（ｋ）１２}，ｒ’^（２） _{π（ｋ）２３}）、（ｒ’^（２） _{π（ｋ）２３}，ｒ’^（２） _{π（ｋ）３１}）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑ_ｋ＝Ｒ^（１） _π（ｋ）＋Ｒ^（２） _π（ｋ）である数値Ｑ_ｋの断片（ｑ_ｋ３１，ｑ_ｋ１２）、（ｑ_ｋ１２，ｑ_ｋ２３）、（ｑ_ｋ２３，ｑ_ｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散ステップと、
    前記３つの秘密分散装置が、Ｔ_ｋ＝Ｑ_ｋ×Ｂ_ｋ ^（１）である数値Ｔ_ｋの断片（ｔ_ｋ３１，ｔ_ｋ１２）、（ｔ_ｋ１２，ｔ_ｋ２３）、（ｔ_ｋ２３，ｔ_ｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算ステップと、
    第１の秘密分散装置が記録する断片をｓ_ｋ１＝（ｓ_ｋ３１，ｓ_ｋ１２）、ｔ_ｋ１＝（ｔ_ｋ３１，ｔ_ｋ１２）とし、第２の秘密分散装置が記録する断片をｓ_ｋ２＝（ｓ_ｋ１２，ｓ_ｋ２３）、ｔ_ｋ２＝（ｔ_ｋ１２，ｔ_ｋ２３）とし、第３の秘密分散装置が記録する断片をｓ_ｋ３＝（ｓ_ｋ２３，ｓ_ｋ３１）、ｔ_ｋ３＝（ｔ_ｋ２３，ｔ_ｋ３１）とし、
    第１の秘密分散装置が、ランダムな値であるｕ_ｋを生成し、第２の秘密分散装置に送信する第３乱数生成ステップと、
    第２の秘密分散装置が、ランダムな値であるｖ_ｋを生成し、第１の秘密分散装置に送信する第４乱数生成ステップと、
    第１の秘密分散装置が、ｄ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置に送信する第４計算ステップと、
    第２の秘密分散装置が、ｅ_ｋ＝ｓ_{π（ｋ）１２}−ｔ_ｋ１２−ｕ_ｋ−ｖ_ｋを計算し、第３の秘密分散装置に送信する第５計算ステップと、
    第３の秘密分散装置が、ｄ_ｋ＝ｅ_ｋであることを確認し、異なっていれば処理を中止する第１確認ステップと、
    第１の秘密分散装置が、ｆ_ｋ＝ｓ_{π（ｋ）３１}−ｔ_ｋ３１＋ｕ_ｋを計算し、第３の秘密分散装置に送信する第６計算ステップと、
    第２の秘密分散装置が、ｇ_ｋ＝ｓ_{π（ｋ）２３}−ｔ_ｋ２３＋ｖ_ｋを計算し、第３の秘密分散装置に送信する第７計算ステップと、
    第３の秘密分散装置が、ｆ_ｋ＋ｇ_ｋ＋ｄ_ｋ＝０であることを確認し、異なっていれば処理を中止する第２確認ステップと、
    を有する秘密分散方法。
12. 請求項９から１１のいずれかに記載の秘密分散方法であって、
    前記断片更新ステップで得られた断片ｂ_ｋ１ ^（ｍ）、ｂ_ｋ２ ^（ｍ）、ｂ_ｋ３ ^（ｍ）を新しい断片ａ_ｋ１ ^（ｍ）、ａ_ｋ２ ^（ｍ）、ａ_ｋ３ ^（ｍ）とし、
    前記断片置換ステップで、あらかじめ定めた全ての組合せで前記秘密分散装置を選択するまで、前記の秘密分散方法を繰り返す
    ことを特徴とする秘密分散方法。
13. 請求項１２記載の秘密分散方法を用いた秘密ソート方法であって、
    請求項１２記載の秘密分散方法によって断片を分散して記録した複数の数値に対して、
    ３つの秘密分散装置が、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する比較ステップと、
    秘密分散装置のそれぞれが、前記比較ステップの結果に基づいて数値の断片を入れ替える交換ステップと、
    を有する秘密ソート方法。
14. 請求項１から６のいずれかに記載の秘密分散システムの各秘密分散装置としてコンピュータを機能させる秘密分散プログラム。
    

Images