"N個の秘密集合関数装置R1,...,RNで構成され、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求めるセキュア集合関数システムであって、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号とし、M個のデータz1,...,zMを、zm=vmのように設定し、情報[k1],[z1],...,[kM],[zM]を生成する初期化手段と、キーkiとキーkjただし、i≠jとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算手段と、を備えるセキュア集合関数システム。請求項1記載のセキュア集合関数システムであって、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とし、前記結合演算手段の処理後に、M個の情報[km],[zm]を秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除する削除手段も備え、前記結合演算手段は、iを1からM-1まで順番に値を大きくしながら、j=i1に対して前記結合処理を行う、または、iをMから2まで順番に値を小さくしながら、j=i-1に対して前記結合処理を行うことを特徴とするセキュア集合関数システム。請求項1記載のセキュア集合関数システムであって、Tはlog2M-1以上の最小の整数、tは0以上T以下の整数、^はべき乗を示す記号、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とし、前記結合演算手段の処理後に、M個の情報[km],[zm]を秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除する削除手段も備え、前記結合演算手段は、i=1,2,...,M-2^tについてkiとki2^tが等しいときにはzi2^t’=zizi2^tとし、等しくないときにはzi2^t’=zi2^tとする第1結合手段と、i=1,2,...,Mについてzi=zi’とする第2結合手段と、i=1,2,...,M-1について、kiとki1が等しいときにはzi=ziとし、等しくないときにはzi=0とするとする第3結合手段と、を有し、t=0,1,2,...,Tについて、前記第1結合手段と前記第2結合手段の処理を繰返した後に前記第3結合手段の処理を行うことを特徴とするセキュア集合関数システム。請求項2または3記載のセキュア集合関数システムであって、sをあらかじめ定めたM以下の整数、Kはキーkmの取り得る値の数とし、M’=Mとする第1事前初期化手段と、t=0、M=M’とする第2事前初期化手段と、tにt1を代入し、1からM/2以下の最大の整数までのiについて、k2i-1とk2iが等しいときにはz2i=z2i-1z2i,z2i-1=0とし、等しくないときにはz2i=z2i,z2i-1=z2i-1とする事前結合手段と、奇数番目の情報[km’],[zm’]を抜き取って保存し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数を新しいMとする保存手段と、前記事前結合手段と前記保存手段の処理を、Mが2K以下になるまで繰り返す第2事前繰返手段と、前記保存手段が保存したすべての情報[km’],[zm’]と残った情報[km],[zm]とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数をM’とする事前削除手段と、前記第2事前初期化手段、前記事前結合手段、前記保存手段、前記第2事前繰返手段、前記事前削除手段の処理をM’がsより小さくなるまで繰り返す第1事前繰返手段とを有する事前処理手段も備え、Mを、前記事前処理手段の処理後の情報[km],[zm]の数に変更し、前記事前処理手段の処理後の情報[km],[zm]に対して、前記初期化手段の処理を実行することを特徴とするセキュア集合関数システム。キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求めるセキュア集合関数システムを構成するN個の秘密集合関数装置の中の秘密集合関数装置であって、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号とし、M個のデータz1,...,zMを、zm=vmのように設定し、情報[k1],[z1],...,[kM],[zM]を生成するための初期化部と、キーkiとキーkjただし、i≠jとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行するための結合演算部と、を備える秘密集合関数装置。N個の秘密集合関数装置R1,...,RNを用いて、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求めるセキュア集合関数処理方法であって、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号とし、M個のデータz1,...,zMを、zm=vmのように設定し、情報[k1],[z1],...,[kM],[zM]を生成する初期化ステップと、キーkiとキーkjただし、i≠jとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算ステップと、を有するセキュア集合関数処理方法。請求項6記載のセキュア集合関数処理方法であって、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とし、前記結合演算ステップ後に、M個の情報[km],[zm]を秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除する削除ステップも有し、前記結合演算ステップは、iを1からM-1まで順番に値を大きくしながら、j=i1に対して前記結合処理を行う、または、iをMから2まで順番に値を小さくしながら、j=i-1に対して前記結合処理を行うことを特徴とするセキュア集合関数処理方法。請求項6記載のセキュア集合関数処理方法であって、Tはlog2M-1以上の最小の整数、tは0以上T以下の整数、^はべき乗を示す記号、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とし、前記結合演算ステップ後に、M個の情報[km],[zm]を秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除する削除ステップも有し、前記結合演算ステップは、i=1,2,...,M-2^tについてkiとki2^tが等しいときにはzi2^t’=zizi2^tとし、等しくないときにはzi2^t’=zi2^tとする第1結合サブステップと、i=1,2,...,Mについてzi=zi’とする第2結合サブステップと、i=1,2,...,M-1について、kiとki1が等しいときにはzi=ziとし、等しくないときにはzi=0とするとする第3結合サブステップと、を有し、t=0,1,2,...,Tについて、前記第1結合サブステップと前記第2結合サブステップを繰返した後に前記第3結合サブステップを行うことを特徴とするセキュア集合関数処理方法。請求項7または8記載のセキュア集合関数処理方法であって、sをあらかじめ定めたM以下の整数、Kはキーkmの取り得る値の数とし、M’=Mとする第1事前初期化サブステップと、t=0、M=M’とする第2事前初期化サブステップと、tにt1を代入し、1からM/2以下の最大の整数までのiについて、k2i-1とk2iが等しいときにはz2i=z2i-1z2i,z2i-1=0とし、等しくないときにはz2i=z2i,z2i-1=z2i-1とする事前結合サブステップと、奇数番目の情報[km’],[zm’]を抜き取って保存し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数を新しいMとする保存サブステップと、前記事前結合サブステップと前記保存サブステップを、Mが2K以下になるまで繰り返す第2事前繰返サブステップと、前記保存サブステップが保存したすべての情報[km’],[zm’]と残った情報[km],[zm]とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のzmが0かを確認し、zm=0の場合には情報[km],[zm]を削除し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数をM’とする事前削除サブステップと、前記第2事前初期化サブステップ、前記事前結合サブステップ、前記保存サブステップ、前記第2事前繰返サブステップ、前記事前削除サブステップをM’がsより小さくなるまで繰り返す第1事前繰返サブステップとを有する事前処理ステップも有し、Mを、前記事前処理ステップ後の情報[km],[zm]の数に変更し、前記事前処理ステップ後の情報[km],[zm]に対して、前記初期化ステップの処理を実行することを特徴とするセキュア集合関数処理方法。請求項1から4のいずれかに記載のセキュア集合関数システムの各秘密集合関数装置としてコンピュータを機能させるためのセキュア集合関数プログラム。例えば、従来の秘密計算を用いた以下の処理で、グループ化して集合関数演算を行うことが可能と考える。なお、集合関数演算を行う対象を、キーkiと属性値viを含む情報ki,viとする。全てのキー属性値に対して以下を繰り返す。1.i番目のキー属性値kiに対して、zi=0とする。2.全データに対して以下を繰り返す。j番目のデータのキー属性がkiならば、zi=zivjキー属性がkiでなければzi=ziただし、0は単位元、は当該集合関数の可換モノイド演算である。しかしながら、上記の方法では、計算量がキー属性値の数×データ数に比例し、効率が悪い。本発明は、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を可能にする技術の提供を目的とする。本発明のセキュア集合関数システムは、N個の秘密集合関数装置R1,...,RNで構成され、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求める。ここで、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号とする。セキュア集合関数システムは、初期化手段と結合演算手段とを備える。初期化手段は、M個のデータz1,...,zMを、zm=vmのように設定し、情報[k1],[z1],...,[kM],[zM]を生成する。結合演算手段は、キーkiとキーkjとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する。本発明のセキュア集合関数システムによれば、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を実行できる。以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。図1に実施例1のセキュア集合関数システムの構成例を示す。また、図2に実施例1のセキュア集合関数システムの処理フローを示す。実施例1のセキュア集合関数システムは、N個の秘密集合関数装置101,...,10Nで構成され、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求める。ここで、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号とする。の具体例としては、和総和、最小値、最大値などがある。秘密集合関数装置10nは、集合関数制御部300n、秘密分散装置100n、記録部190nを備える。秘密分散装置100nは、集合関数制御部300nの指示にしたがって実施例1の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、四則演算などがある。ただし、本発明は、これらの秘密計算を利用して効率よく集合関数演算を行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、1つの例であり、実施例1が利用できる秘密計算を限定するものではない。記録部190nは、秘密集合関数装置10nの処理に必要な情報を記録する構成部である。図1に示した選択手段105は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。各秘密集合関数装置10nの集合関数制御部300nは、初期化部320n、結合演算部330n、削除部340nを備える。そして、セキュア集合関数システムの初期化手段320図示していないは初期化部3201,...,320Nで構成され、結合演算手段330図示していないは結合演算部3301,...,330Nで構成され、削除手段340図示していないは削除部3401,...,340Nで構成される。初期化手段320は、M個のデータz1,...,zMを、zm=vmのように設定し、情報[k1],[z1],...,[kM],[zM]を生成するS340。より具体的には、初期化部3201,...,320N初期化手段320は、秘密分散装置1001,...,100Nに属性値vmの断片と同じ断片を持つデータvmの断片を作らせ、各断片を秘密分散させることで情報[k1],[z1],...,[kM],[zM]を生成させる。結合演算手段330は、キーkiとキーkjとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとする結合処理が、すべての等しいキーを持つ情報に対して実行されるまで、秘密計算で実行するS330。例えば、キーkiとキーkjとが等しいことを確認する論理回路は、従来技術として蓄積された論理回路の技術を用いれば、実現できる。キーkiとキーkjの2ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。C=1-{kiB[∨]kjB∨∨ki1[∨]kj1}1ただし、[∨]は排他的論理和XORを示す記号、∨は論理和ORを示す記号、kibは2ビット展開したときのキーkiの下からbビット目の値、Bは2ビット展開したときのキーkiの桁数とする。式1では、C=1ならばキーkiとキーkjとが等しく真、C=0ならばキーkiとキーkjとが異なる偽。また、式1の個々の演算は後述の秘密計算の例に示されているので、式1の演算は秘密計算で実行でき、秘密分散された[C]が求められる。したがって、確認後の分岐も秘密にするのであれば、[C]を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、大小比較を比較する演算などの所望の演算を、後述する秘密計算の方法の組合せで実行できる。さらに、情報[k1],[z1],...,[kM],[zM]がランダムに並んだ情報の場合は、i,jのすべての組合せに対して結合演算手段330の処理を行う必要がある。一方、情報[k1],[z1],...,[kM],[zM]が何らかの規則に従って並んでいれば、i,jのすべての組合せまで実行する必要はない。例えば、情報[k1],[z1],...,[kM],[zM]がキーkmに基づいてソートされている場合であれば、iを1からM-1まで順番に値を大きくしながら、j=i1に対して、キーkiとキーkjとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとすればよい。もしくは、iをMから2まで順番に値を小さくしながら、j=i-1に対して、キーkiとキーkjとが等しいときにはzj=zizj,zi=0とし、等しくないときにはzj=zj,zi=ziとすればよい。このようにソート済みの情報であれば、隣り合う情報同士の比較を順番に行うだけで、同じ値のキーを持つすべての情報に対する集合関数演算を実行し、最後に結合したzjに集合関数演算の結果をまとめることができる。したがって、OMの計算量で処理ができる。削除手段340は、結合演算手段330の処理後に、M個の情報[km],[zm]を秘密計算でランダム置換し、ランダム置換後のzmが0かを秘密計算で確認し、確認結果を復元する。つまり、式1でzmと0に対する[C]を求め、[C]を復元してCを求める。そして、zm=0の場合式1であればC=1の場合には情報[km],[zm]を削除するS340。ステップS340の削除は、残りの情報の数が、情報[km],[zm]の数とキーの値の数の少ない方になるまで削除すればよい。なお、情報[k1],[z1],...,[kM],[zM]がもともとランダムに並んでいる場合は、ランダム置換は必要ないので削除手段340を省略してもよい。情報[k1],[z1],...,[kM],[zM]がキーkmに基づいてソートされている場合は、zm=0の確認結果を復元すると、キーの値が同じ情報が何個あるのか、何番目に境界があるのかなどのキーに関する情報が漏れてしまう。したがって、ランダム置換が必要となる。図1に実施例2のセキュア集合関数システムの構成例を示す。また、図3に実施例2のセキュア集合関数システムの処理フローを示す。実施例2のセキュア集合関数システムも、N個の秘密集合関数装置101,...,10Nで構成され、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求める。ここで、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号、Tはlog2M-1以上の最小の整数、tは0以上T以下の整数、^はべき乗を示す記号とする。また、実施例2では、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とする。秘密集合関数装置10nは、集合関数制御部300n、秘密分散装置100n、記録部190nを備え、秘密分散装置100n、記録部190n、集合関数制御部300nの初期化部320n、削除部340nは実施例1と同じである。異なるのは、結合演算部330nである。つまり、初期化手段320と削除手段340は実施例1と同じであり、結合演算手段330が異なる。実施例2の結合演算部330nは、第1結合部331n、第2結合部332n、第3結合部333nを備える。そして、第1結合手段331図示していないは第1結合部3311,...,331Nで構成され、第2結合手段332図示していないは第2結合部3321,...,332Nで構成され、第3結合手段333図示していないは第3結合部3331,...,333Nで構成される。また、結合演算手段330は、第1結合手段331、第2結合手段332、第3結合手段333を有する。結合演算手段330は、tに0を代入するS336。第1結合手段331は、i=1,2,...,M-2^tについて、kiとki2^tが等しいときにはzi2^t’=zizi2^tとし、等しくないときにはzi2^t’=zi2^tとするS331。より具体的には、第1結合部3311,...,331N第1結合手段331は、秘密分散装置1001,...,100Nに、i=1,2,...,M-2^tについて、kiとki2^tが等しいかを、例えば式1の秘密計算で確認させる。そして、その結果に基づいて、zi2^t’=zizi2^tまたはzi2^t’=zi2^tの秘密計算を実行させる。なお、ステップS331のi=1,2,...,M-2^tについての処理は、互いに影響しないため並列に処理できる。第2結合手段332は、i=1,2,...,Mについてzi=zi’とするS332。なお、ステップS332もi=1,2,...,Mについての処理は互いに影響しないため、並列に処理できる。そして、結合演算手段330は、t=Tかを確認しS337、Yesの場合にはステップS333に進み、Noの場合にはtにt1を代入しS338、ステップS331に戻る。ステップS333では、第3結合手段が、i=1,2,...,M-1について、kiとki1が等しいときにはzi=ziとし、等しくないときにはzi=0とするS333。なお、ステップS320とS340の処理は実施例1と同じである。このように、結合演算手段330は、t=0,1,2,...,Tについて、第1結合手段331と第2結合手段332の処理S331,S332を繰返した後に第3結合手段333の処理S333を行う。また、ステップS331、S332は並列処理が可能なので、演算回数が多くなったとしても、繰返しの演算を順番に実行せざるを得ない実施例1の方法よりも高速の演算が可能である。より具体的に説明すると、実施例2のセキュア集合関数システムの計算量は、データ数Mに対しOMlogMとなる。したがって、実施例1のOMよりも増加する。一方、実施例1は順番に処理する必要があるので、段数直列に処理せざるを得ない計算数もOMである。しかし、実施例2では大幅に並列度が上昇するので、段数はOlogMに減少する。図4に実施例3のセキュア集合関数システムの構成例を示す。また、図5に実施例3のセキュア集合関数システムの処理フローを示す。実施例3のセキュア集合関数システムも、N個の秘密集合関数装置101,...,10Nで構成され、キーkmと属性値vmを含むM個の情報k1,v1,...,kM,vMがそれぞれ秘密分散された情報[k1],[v1],...,[kM],[vM]から、秘密分散された集計結果を求める。ここで、Mは2以上の整数、Nは3以上の整数、m,i,jは1以上M以下の整数、[]はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、0は演算の単位元を示す記号、sはあらかじめ定めたM以下の整数、Kはキーkmの取り得る値の数とする。また、実施例3では、情報[k1],[v1],...,[kM],[vM]はキーkmに基づいてソートされた情報とする。秘密集合関数装置10nは、集合関数制御部300n、秘密分散装置100n、記録部190nを備え、秘密分散装置100n、記録部190n、集合関数制御部300nの初期化部320n、結合演算手段330、削除部340nは実施例1または実施例2と同じである。異なるのは、事前処理部310nである。つまり、初期化手段320と結合演算手段330と削除手段340は、実施例1または実施例2と同じである。事前処理部310nは、第1事前初期化部311n、第2事前初期化部312n、事前結合部313n、保存部314n、第2事前繰返部315n、事前削除部316n、第1事前繰返部317nを有する。そして、第1事前初期化手段311図示していないは第1事前初期化部3111,...,311Nで構成され、第2事前初期化手段312図示していないは第2事前初期化部3121,...,312Nで構成され、事前結合手段313図示していないは事前結合部3131,...,313Nで構成され、保存手段314図示していないは保存部3141,...,314Nで構成され、第2事前繰返手段315図示していないは第2事前繰返部3151,...,315Nで構成され、事前削除手段316図示していないは事前削除部3161,...,316Nで構成され、第1事前繰返手段317図示していないは第1事前繰返部3171,...,317Nで構成される。また、事前処理手段310は、第1事前初期化手段311、第2事前初期化手段312、事前結合手段313、保存手段314、第2事前繰返手段315、事前削除手段316、第1事前繰返手段317を有する。第1事前初期化手段311は、M’=MとするS311。第2事前初期化手段312は、t=0、M=M’とするS312。事前結合手段313は、tにt1を代入し、1からM/2以下の最大の整数までのiについて、k2i-1とk2iが等しいときにはz2i=z2i-1z2i,z2i-1=0とし、等しくないときにはz2i=z2i,z2i-1=z2i-1とするS313。なお、k2i-1とk2iとの比較は、事前結合部3131,...,313N事前結合手段313が、秘密分散装置1001,...,100Nに、例えば式1の論理式を用いた秘密計算を実行させればよい。また、異なるiに対する演算同士は互いに影響を与えないので、異なるiに対する演算は並列で行うことができる。保存手段314は、奇数番目の情報[km’],[zm’]を抜き取って保存し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数を新しいMとするS314。第2事前繰返手段315は、Mが2K以下か第2事前繰返条件を確認し、第2事前繰返条件を満たすまで事前結合手段313の処理S313と保存手段314の処理S314を繰り返すS315。事前削除手段S316は、保存手段314が保存したすべての情報[km’],[zm’]と残った情報[km],[zm]とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のzmが0かを秘密計算で確認し、zm=0の場合には情報[km],[zm]を削除し、残った情報を新しい情報[km],[zm]とし、新しい情報[km],[zm]の数をM’とするS316。なお、新しい情報残りの情報の数M’がtK最後のステップS315で残った情報の数になるまでステップS316で情報を削除できる。第1事前繰返手段S317は、M’がsより小さいか第1事前繰返条件を確認し、第1事前繰返条件を満たすまで第2事前初期化手段312の処理S312、事前結合手段313の処理S313、保存手段314の処理S314、第2事前繰返手段315S315、事前削除手段316S316を繰り返すS317。そして、セキュア集合関数システムは、Mを、事前処理手段310の処理S310後の情報[km],[zm]の数に変更し、事前処理手段310の処理S310後の情報[km],[zm]に対して、実施例1または実施例2に示した初期化手段320の処理S320、結合演算手段330の処理S330、を実行する。実施例3の事前処理手段310の処理は、情報の数Mがキーの取り得る値の数Kに比べて非常に大きい場合に演算量を減らす効果がある。一方、MとKの値が近くなると実施例1や実施例2の結合演算手段330の処理S330の方が演算量を少なくできる。したがって、MがKに比べて非常に大きいときに、事前処理手段310を用いて情報の数Mを少なくし、MがKに近づいたところで実施例1や実施例2の結合演算手段330に切り替えて処理すれば効率的である。より具体的には、実施例3のセキュア集合関数システムの計算量はOMKlogMであり、段数はOlogMである。あらかじめ定めるsは、どの程度MがKに近づいたところで切り替えるのかを定める値であり、全体の演算量が少なくなるように適宜決めればよい。このように、実施例3のセキュア集合関数システムによれば、情報の数Mがキーの取り得る値の数Kに比べて非常に大きい場合に演算量を減らすことができる。[演算量の具体例]情報の数M=1000、キーの取り得る値の数K=10とする。実施例3のステップS314の1回目でM=500、2回目でM=250となり、6回目でM=16となる。そして、ここまでの結合演算の回数は985回であり、残りの情報の数は次のようになる。tK最後のステップS315で残った情報の数=6×1016=76これをもう一度繰り返すと、t=2でM=19、結合演算の回数は57回増えて1042回、残りの情報の数の最大値実際にはこの数以下となる数は2×1019=39となる。例えばsを40に設定していれば、ステップS317は終了し、ステップS320に進む。ステップS320,S330,S340を実施例1の方法で実行すれば、結合演算の回数は1080回、段数は46段である。ステップS320,S330,S340を実施例2の方法で実行すれば、結合演算の回数は1213回、段数は14段である。比較として、最初から実施例1の方法にした場合は、結合演算の回数は999回、段数は999段、実施例2の方法の場合の結合演算の回数は8977回、段数は10段となり、情報の数Mがキーの取り得る値の数Kよりかなり大きい場合、実施例3の方法は計算量と段数のバランスに優れることが分かる。なお、従来の方法の場合、結合演算の回数は9990回、段数は10段である。[秘密計算]上述の説明では、秘密計算については1つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密集合関数装置101,...,10Nが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、1つの例でありこれに限定されるものではない。本発明のセキュア集合関数システムでは他の秘密計算を用いてもよい。ランダム置換1図6に本発明に利用できる秘密分散装置100nの機能構成例を詳しく示したセキュア集合関数システムを示す。図7にランダム置換の1つ目の処理フロー例を示す。この例では、セキュア集合関数システムは選択手段105も備える。ここで、A1,...,AKを各秘密集合関数装置10nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密集合関数装置10nが記録するk番目の断片とする。なお、数値A1,...,AKが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Akが各々の人の年収を示すような数値群が考えられる。選択手段105は、いずれかの秘密集合関数装置の内部に配置されてもよいし、単独の装置であってもよい。セキュア集合関数システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置100nは、少なくとも断片置換部110nと再分散部120nと記録部190nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105は、N未満の数の秘密集合関数装置10nを選択するS105。例えば、N個の断片のうちN’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がN’個以上N未満の秘密集合関数装置を選べばよい。断片置換手段は、少なくとも断片置換部1101,...,110Nを含んで構成される。そして、選択手段105に選択された秘密集合関数装置10iただし、iは選択された秘密集合関数装置を示す番号の断片置換部110i間で{1,...,K}→{1,...,K}の全単射πを作成し、選択された秘密集合関数装置10iの記録部190iが記録する断片aπkiをk番目の断片にするS110。全単射πは、1~Kを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisherYatesshuffle参考文献1:RichardDurstenfeldAlgorithm235RandompermutationCommunicationsoftheACMarchiveVolume7Issue71964などを用いて作成すればよい。また、全単射πは選択された秘密集合関数装置10i間で生成してもよいし、選択された秘密集合関数装置10iのうちの1つの秘密集合関数装置が生成して、選択された秘密集合関数装置10i間で共有してもよい。再分散手段は、少なくとも再分散部1201,...,120Nを含んで構成される。再分散手段は、断片置換手段によって置換された数値Aπkに対応する断片aπkik番目に置換されているを用いて再分散化して新しい断片bk1,...,bkNを求め、数値Bkの断片とするS120。つまり、Aπk=Bkの関係が成り立つが、選ばれなかった秘密集合関数装置は全単射πを知らないので、Aπk=Bkであることを知らない。なお、各秘密集合関数装置10nの記録部190nは、断片bknを記録するだけでなく、自身が記録しているk番目の断片である断片bknが数値Bkの断片であるという情報も記録する。また、数値B1,...,BKを新しい数値A1,...,AKとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。本発明のセキュア集合関数システムによれば、限定された秘密集合関数装置間で断片をシャッフルする。したがって、選ばれなかった秘密集合関数装置は、全単射πを知らないので、数値A1,...,AKと数値B1,...,BKとの対応が分からない。つまり、特定の秘密集合関数装置からは数値A1,...,AKと数値B1,...,BKとの対応が分からない状態にしたいのであれば、その秘密集合関数装置を選択手段105で選ばないように、選択する秘密集合関数装置をあらかじめ定めればよい。また、選択手段105が選ぶ秘密集合関数装置を変更しながらこの処理を繰り返し、全ての秘密集合関数装置が選ばれなかったことがある状態にすれば、全ての秘密集合関数装置が数値A1,...,AKと対応つけることができない数値B1,...,BKを得ることができる。ランダム置換2次のランダム置換のためのセキュア集合関数システムの秘密分散装置100nを詳細に示した機能構成例も図6に示す。図8にランダム置換の2つ目の処理フロー例を示す。この例でも、セキュア集合関数システムは選択手段105も備える。ここで、A1,...,AKを各秘密集合関数装置10nが断片を分散して記録するK個の数値Kは2以上の整数、数値Akをk番目の数値kは1以上K以下の整数、aknを秘密集合関数装置10nが記録する数値Akの断片とする。本発明のセキュア集合関数システムは、選択手段105、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置100nは、初期情報分散部130n、初期乗算部140n、断片置換部110n、再分散部120n、確認分散部150n、確認乗算部160n、改ざん検出部170nを備える。記録部190nは断片a1n,...,aKnなどを記録する。また、記録部190nは、自身が記録している断片aknが数値Akの何番目の断片なのかに関する情報も記録する。選択手段105はランダム置換1と同じである。初期情報分散手段は、初期情報分散部1301,...,130Nで構成される。そして、選択手段105に選択された秘密集合関数装置10iの初期情報分散部130iは、秘密集合関数装置101,...,10Nのどれも知らないK個の数値P1,...,PKそれぞれの断片p1n,...,pKnを秘密計算によって求め、記録部190nに記録するS130。具体的には、選択手段105に選択された秘密集合関数装置から、2つ以上の秘密集合関数装置を選定する。そして、選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、2つの秘密集合関数装置10i,10jを選定しただし、i≠j、秘密集合関数装置10iが生成した数値の断片と、秘密集合関数装置10jが生成した数値の断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を2つとしたが、2つ以上でもかまわない。初期乗算手段は、初期乗算部1401,...,140Nで構成される。初期乗算部1401,...,140Nは、Sk=Pk×Akである数値Skの断片sk1,...,skNを秘密計算によって求め、記録部1901,...,190Nに分散して記録するS140。断片置換手段と再分散手段は、ランダム置換1と同じである。確認分散手段は、確認分散部1501,...,150Nで構成される。確認分散部1501,...,150Nは、k=1~Kについて、Qk=Pπkである数値Qkの断片qk1,...,qkNを秘密計算によって生成し、記録部1901,...,190Nに分散して記録するS150。具体的には、ステップS130で選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップS130で選定された秘密集合関数装置10iが数値Pπk用に生成した数値の別の断片新しい断片と、ステップS130で選定された秘密集合関数装置10jが数値Pπk用に生成した数値の別の断片新しい断片を分散して記録する。そして、その2つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Qk=Pπkであり、かつ、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を2つとしたが、ステップS130と同じように2つ以上でもかまわない。確認乗算手段は、確認乗算部1601,...,160Nで構成される。確認乗算部1601,...,160Nは、Tk=Qk×Bkである数値Tkの断片tk1,...,tkNを秘密計算によって求め、記録部1901,...,190Nに分散して記録するS160。改ざん検出手段は、改ざん検出部1701,...,170Nで構成される。改ざん検出部1701,...,170Nは、k=1~Kについて、Tk=Sπkであることを確認するS170。tkn≠sπknの場合には、改ざんがあったとして異常終了する。また、数値B1,...,BKを新しい数値A1,...,AKとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができるS111,S112。[その他の秘密計算]ここでは、セキュア集合関数システムが3個の秘密集合関数装置で構成された場合の秘密計算の例を示す。また、秘密集合関数装置101,102,103の番号を固定する必要はないので、秘密集合関数装置10α,10β,10γと表現することにする。つまり、α,β,γは、1,2,3、2,3,1、3,1,2のいずれかである。以下の秘密計算では、秘密集合関数装置10α,10β,10γが分散して記録する数値Aの断片をaγα,aαβ、aαβ,aβγ、aβγ,aγα、数値Bの断片をbγα,bαβ、bαβ,bβγ、bβγ,bγα、数値Cの断片をcγα,cαβ、cαβ,cβγ、cβγ,cγαとする。なお、以下の説明では、Wを2以上のあらかじめ定めた整数とし、計算結果はWで除した余りである。言い換えると、以下の説明の計算式ではmodWを省略している。数値Aの秘密分散1乱数aαβ,aβγを生成する。2aγα=A-aαβ-aβγを計算し、断片をaγα,aαβ、aαβ,aβγ、aβγ,aγαとし、秘密集合関数装置10α,10β,10γに分散して記録する。数値Aの復元1秘密集合関数装置10αは秘密集合関数装置10βにaγαを送信し、秘密集合関数装置10γにaαβを送信する。秘密集合関数装置10βは秘密集合関数装置10γにaαβを送信し、秘密集合関数装置10αにaβγを送信する。秘密集合関数装置10γは秘密集合関数装置10αにaβγを送信し、秘密集合関数装置10βにaγαを送信する。2秘密集合関数装置10αは秘密集合関数装置10βから受信したaβγと秘密集合関数装置10γから受信したaβγとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密集合関数装置10βは秘密集合関数装置10γから受信したaγαと秘密集合関数装置10αから受信したaγαとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。秘密集合関数装置10γは秘密集合関数装置10αから受信したaαβと秘密集合関数装置10βから受信したaαβとが一致していれば、aαβaβγaγαを計算して数値Aを復元する。C=ABの秘密計算1秘密集合関数装置10αはcγα,cαβ=aγαbγα,aαβbαβを計算して記録し、秘密集合関数装置10βはcαβ,cβγ=aαβbαβ,aβγbβγを計算して記録し、秘密集合関数装置10γはcβγ,cγα=aβγbβγ,aγαbγαを計算して記録する。C=A-Bの秘密計算1秘密集合関数装置10αはcγα,cαβ=aγα-bγα,aαβ-bαβを計算して記録し、秘密集合関数装置10βはcαβ,cβγ=aαβ-bαβ,aβγ-bβγを計算して記録し、秘密集合関数装置10γはcβγ,cγα=aβγ-bβγ,aγα-bγαを計算して記録する。C=ASの秘密計算ただし、Sは既知の定数1秘密集合関数装置10αはcγα,cαβ=aγαS,aαβを計算して記録し、秘密集合関数装置10γはcβγ,cγα=aβγ,aγαSを計算して記録する。秘密集合関数装置10βの処理はない。C=ASの秘密計算ただし、Sは既知の定数1秘密集合関数装置10αはcγα,cαβ=aγαS,aαβSを計算して記録し、秘密集合関数装置10βはcαβ,cβγ=aαβS,aβγSを計算して記録し、秘密集合関数装置10γはcβγ,cγα=aβγS,aγαSを計算して記録する。C=ABの秘密計算1秘密集合関数装置10αは、乱数r1,r2,cγαを生成し、cαβ=aγαaαβbγαbαβ-r1-r2-cγαを計算する。そして、秘密集合関数装置10αは、秘密集合関数装置10βにr1,cαβを、秘密集合関数装置10γにr2,cγαを送信する。2秘密集合関数装置10βは、y=aαβbβγaβγbαβr1を計算し、秘密集合関数装置10γに送信する。3秘密集合関数装置10γは、z=aβγbγαaγαbβγr2を計算し、秘密集合関数装置10αに送信する。4秘密集合関数装置10βと秘密集合関数装置10γは、それぞれcβγ=yzaβγbβγを計算する。5秘密集合関数装置10αはcγα,cαβを記録し、秘密集合関数装置10βはcαβ,cβγを記録し、秘密集合関数装置10γはcβγ,cγαを記録する。ビットAの否定C=1-Aの秘密計算秘密集合関数装置10αはcγα,cαβ=1-aγα,-aαβmodWを計算して記録し、秘密集合関数装置10βはcαβ,cβγ=-aαβmodW,-aβγmodWを計算して記録し、秘密集合関数装置10γはcβγ,cγα=-aβγmodW,1-aγαを計算して記録する。ビットの論理積C=A∧B=ABの秘密計算秘密集合関数装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行う。ビットの論理和C=A∨B=AB-ABの秘密計算1秘密集合関数装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C’=ABの結果として、秘密集合関数装置10αが断片cγα’,cαβ’を、秘密集合関数装置10βが断片cαβ’,cβγ’を、秘密集合関数装置10γが断片cβγ’,cγα’を記録する。また、秘密集合関数装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行い、C=ABの結果として、秘密集合関数装置10αが断片cγα,cαβを、秘密集合関数装置10βが断片cαβ,cβγを、秘密集合関数装置10γが断片cβγ,cγαを記録する。2秘密集合関数装置10α,10β,10γは、S=-1として整数の乗算C=ASmodWの秘密計算ただし、Sは既知の定数と同じ処理を行い、C’’’=-Cの結果として、秘密集合関数装置10αが断片cγα’’’,cαβ’’’を、秘密集合関数装置10βが断片cαβ’’’,cβγ’’’を、秘密集合関数装置10γが断片cβγ’’’,cγα’’’を記録する。3秘密集合関数装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C=C’C’’’の結果として、秘密集合関数装置10αが断片cγα,cαβを、秘密集合関数装置10βが断片cαβ,cβγを、秘密集合関数装置10γが断片cβγ,cγαを記録する。ビットの排他的論理和C=A[∨]B=AB-2ABの秘密計算1秘密集合関数装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C’=ABの結果として、秘密集合関数装置10αが断片cγα’,cαβ’を、秘密集合関数装置10βが断片cαβ’,cβγ’を、秘密集合関数装置10γが断片cβγ’,cγα’を記録する。また、秘密集合関数装置10α,10β,10γは、整数の乗算C=ABmodWの秘密計算と同じ処理を行い、C=ABの結果として、秘密集合関数装置10αが断片cγα,cαβを、秘密集合関数装置10βが断片cαβ,cβγを、秘密集合関数装置10γが断片cβγ,cγαを記録する。2秘密集合関数装置10α,10β,10γは、S=-2として整数の乗算C=ASmodWの秘密計算ただし、Sは既知の定数の秘密計算と同じ処理を行い、C’’’=-2Cの結果として、秘密集合関数装置10αが断片cγα’’’,cαβ’’’を、秘密集合関数装置10βが断片cαβ’’’,cβγ’’’を、秘密集合関数装置10γが断片cβγ’’’,cγα’’’を記録する。3秘密集合関数装置10α,10β,10γは、整数の加算C=ABmodWの秘密計算と同じ処理を行い、C=C’C’’’の結果として、秘密集合関数装置10αが断片cγα,cαβを、秘密集合関数装置10βが断片cαβ,cβγを、秘密集合関数装置10γが断片cβγ,cγαを記録する。ビットAn,n=0,...,N-1の整数変換の秘密計算ビットAnの整数変換とは、を求めることである。また、秘密集合関数装置10α,10β,10γが分散して記録するビットAnの断片をanγα,anαβ、anαβ,anβγ、anβγ,anγαとする。秘密集合関数装置10αは、を計算して記録し、秘密集合関数装置10βはを計算して記録し、秘密集合関数装置10γはを計算して記録する。Nビットの整数Aの二進数変換の秘密計算xnは、xの下位n1番目のビットを示すものとする。1n=0からN-1について、秘密集合関数装置10βがaαβaβγmodWnを秘密分散し、秘密集合関数装置10α,10β,10γがaαβaβγmodWnの断片bnγα,bnαβ、bnαβ,bnβγ、bnβγ,bnγαを分散して記録する。n=0からN-1について、秘密集合関数装置10γがaγαnを秘密分散し、秘密集合関数装置10α,10β,10γがaγαnの断片aγαnγα,aγαnαβ、aγαnαβ,aγαnβγ、aγαnβγ,aγαnγαを分散して記録する。2cγα=0とし、n=0からN-1について2-1から2-3の処理を繰返し実行する。2-1dn=bnaγαn-2bnaγαnの秘密計算を実行し、dnの断片を分散して記録する。2-2an=dncn-2dncnの秘密計算を実行し、anの断片を分散して記録する。2-3n<N-1であれば、cn1=bnaγαndncn-bnaγαndncnの秘密計算を実行し、cn1の断片を分散して記録する。[プログラム、記録媒体]上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"