"秘密分散システムであって、分散装置とΣα1Lh個の分散管理装置PA1HH≧2と取得装置とを有し、前記分散装置は、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、nを1以上の整数とし、ζを0以上の整数とし、巡回群G2の生成元をg2とし、θζβ1nζn≧1ζ≧1に対する前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルをbig2θζg2∈G2nζとした場合における、前記基底ベクトルbiの各要素θg2に応じた値を、それぞれH個の分散管理装置PAPAからなる部分集合SUBごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θg2に応じた値のシェア情報SH1Hを生成する秘密分散部を含み、前記分散管理装置PAは、前記部分集合SUBごとに共有される共通情報と、前記シェア情報SH1Hとに対し、前記部分集合SUBごとに共通の共通演算を行って分散秘密値DSHを生成する分散秘密値生成部を含み、前記取得装置は、同一の前記部分集合SUBに対応する複数の前記分散秘密値DSHを用い、前記秘密分散方式に従った部分集合SUBごとの復元処理によって、当該部分集合SUBごとの秘密復元値SUBSKを生成する復元部と、前記秘密復元値SUBSKを用いて生成情報Dを生成する合成部とを含む、秘密分散システム。請求項1の秘密分散システムであって、互いに異なる前記部分集合SUBでそれぞれ共有される前記共通情報は、互いに独立である、秘密分散システム。請求項1の秘密分散システムであって、前記共通演算は、線形性を持った演算である、秘密分散システム。請求項2の秘密分散システムであって、前記共通演算は、線形性を持った演算である、秘密分散システム。請求項1の秘密分散システムであって、前記合成部は、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成する、秘密分散システム。請求項2の秘密分散システムであって、前記合成部は、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成する、秘密分散システム。請求項3の秘密分散システムであって、前記合成部は、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成する、秘密分散システム。請求項4の秘密分散システムであって、前記合成部は、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成する、秘密分散システム。請求項1から8の何れかの秘密分散システムであって、前記基底ベクトルbiの各要素θg2に応じた値はθであり、前記共通情報は、λを1以上Ψ以下の整数λ1Ψとした場合における、coefιcoefcoefιSEshareを含み、前記分散秘密値生成部は、SHbiSHとした場合における、DSHSESHb1g2Σι2IcoefιSHbιg2をψ0に対応する前記分散秘密値として生成し、さらに、SHbiSHζαhとし、v→vnをn次元ベクトルとした場合における、DSHcoefv1SHb1g2Σι2ncoefvιSHbιg2Σιn1nζcoefιSHbιg2又は、DSHshareΣι1nvιSHb1g2Σιn1nζcoefιSHbιg2を各λに対応する前記分散秘密値として生成する、秘密分散システム。請求項1から8の何れかの秘密分散システムであって、前記基底ベクトルbiの各要素θg2に応じた値はθg2であり、前記共通情報は、λを1以上Ψ以下の整数λ1Ψとした場合における、coefιcoefcoefιSEshareを含み、前記分散秘密値生成部は、SHbiSHとした場合における、DSHSESHb1Σι2IcoefιSHbιをψ0に対応する前記分散秘密値として生成し、さらに、SHbiSHζαhとし、v→vnをn次元ベクトルとした場合における、DSHcoefv1SHb1Σι2ncoefvιSHbιΣιn1nζcoefιSHbι又は、DSHshareΣι1nvιSHb1Σιn1nζcoefιSHbιを各λに対応する前記分散秘密値として生成する、秘密分散システム。請求項9の秘密分散システムであって、前記復元部は、SUBSKSEb1Σι2Icoefιbιをψ0に対応する前記秘密復元値として生成し、SUBSKcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι又は、SUBSKshareΣι1nvιb1Σιn1nζcoefιbιを各λに対応する前記秘密復元値として生成する、秘密分散システム。請求項10の秘密分散システムであって、前記復元部は、SUBSKSEb1Σι2Icoefιbιをψ0に対応する前記秘密復元値として生成し、SUBSKcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι又は、SUBSKshareΣι1nvιb1Σιn1nζcoefιbιを各λに対応する前記秘密復元値として生成する、秘密分散システム。Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、nを1以上の整数とし、ζを0以上の整数とし、巡回群G2の生成元をg2とし、θζβ1nζn≧1ζ≧1に対する前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルをbig2θζg2∈G2nζとした場合における、前記基底ベクトルbiの各要素θg2に応じた値を、それぞれH1HH≧2個の分散管理装置PAPAからなる部分集合SUBごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θg2に応じた値のシェア情報SH1Hを生成する分散装置。H1HH≧2個の分散管理装置PAPAからなる部分集合SUBごとに共有される共通情報と、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、nを1以上の整数とし、ζを0以上の整数とし、巡回群G2の生成元をg2とし、θζβ1nζn≧1ζ≧1に対する前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルをbig2θζg2∈G2nζとした場合における、前記基底ベクトルbiの各要素θg2に応じた値をそれぞれ前記部分集合SUBごとに独立に秘密分散して得られた各要素θg2に応じた値のシェア情報SH1Hとに対し、前記部分集合SUBごとに共通の共通演算を行って分散秘密値DSHを生成する分散管理装置。Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、H1HH≧2個の分散管理装置PAPAからなる部分集合をSUBとした場合における、同一の前記部分集合SUBに対応する複数の前記分散秘密値DSHを用い、所定の秘密分散方式に従った部分集合SUBごとの復元処理によって、当該部分集合SUBごとの秘密復元値SUBSKを生成する復元部と、前記秘密復元値SUBSKを用いて生成情報Dを生成する合成部と、を有する取得装置。分散装置とΣα1Lh個の分散管理装置PA1HH≧2と取得装置とによって行われる秘密分散方法であって、前記分散装置が、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、nを1以上の整数とし、ζを0以上の整数とし、巡回群G2の生成元をg2とし、θζβ1nζn≧1ζ≧1に対する前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルをbig2θζg2∈G2nζとした場合における、前記基底ベクトルbiの各要素θg2に応じた値を、それぞれH個の分散管理装置PAPAからなる部分集合SUBごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θg2に応じた値のシェア情報SH1Hを生成するステップと、前記分散管理装置PAが、前記部分集合SUBごとに共有される共通情報と、前記シェア情報SH1Hとに対し、前記部分集合SUBごとに共通の共通演算を行って分散秘密値DSHを生成するステップと、前記取得装置が、同一の前記部分集合SUBに対応する複数の前記分散秘密値DSHを用い、前記秘密分散方式に従った部分集合SUBごとの復元処理によって、当該部分集合SUBごとの秘密復元値SUBSKを生成するステップと、前記取得装置が、前記秘密復元値SUBSKを用いて生成情報Dを生成するステップと、を有する秘密分散方法。請求項16の秘密分散方法であって、互いに異なる前記部分集合SUBでそれぞれ共有される前記共通情報は、互いに独立である、秘密分散方法。請求項16の秘密分散方法であって、前記共通演算は、線形性を持った演算である、秘密分散方法。請求項17の秘密分散方法であって、前記共通演算は、線形性を持った演算である、秘密分散方法。請求項16の秘密分散方法であって、前記ステップは、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成するステップを含む、秘密分散方法。請求項17の秘密分散方法であって、前記ステップは、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成するステップを含む、秘密分散方法。請求項18の秘密分散方法であって、前記ステップは、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成するステップを含む、秘密分散方法。請求項19の秘密分散方法であって、前記ステップは、前記秘密復元値SUBSKを線形結合して前記生成情報Dを生成するステップを含む、秘密分散方法。請求項16から23の何れかの秘密分散方法であって、前記基底ベクトルbiの各要素θg2に応じた値はθであり、前記共通情報は、λを1以上Ψ以下の整数λ1Ψとした場合における、coefιcoefcoefιSEshareを含み、前記ステップは、SHbiSHとした場合における、DSHSESHb1g2Σι2IcoefιSHbιg2をψ0に対応する前記分散秘密値として生成するステップと、SHbiSHζαhとし、v→vnをn次元ベクトルとした場合における、DSHcoefv1SHb1g2Σι2ncoefvιSHbιg2Σιn1nζcoefιSHbιg2又は、DSHshareΣι1nvιSHb1g2Σιn1nζcoefιSHbιg2を各λに対応する前記分散秘密値として生成するステップと、を含む、秘密分散方法。請求項16から23の何れかの秘密分散方法であって、前記基底ベクトルbiの各要素θg2に応じた値はθg2であり、前記共通情報は、λを1以上Ψ以下の整数λ1Ψとした場合における、coefιcoefcoefιSEshareを含み、前記ステップは、SHbiSHとした場合における、DSHSESHb1Σι2IcoefιSHbιをψ0に対応する前記分散秘密値として生成するステップと、SHbiSHζαhとし、v→vnをn次元ベクトルとした場合における、DSHcoefv1SHb1Σι2ncoefvιSHbιΣιn1nζcoefιSHbι又は、DSHshareΣι1nvιSHb1Σιn1nζcoefιSHbιを各λに対応する前記分散秘密値として生成するステップと、を含む、秘密分散方法。請求項24の秘密分散方法であって、前記ステップは、SUBSKSEb1Σι2Icoefιbιをψ0に対応する前記秘密復元値として生成するステップと、SUBSKcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι又は、SUBSKshareΣι1nvιb1Σιn1nζcoefιbιを各λに対応する前記秘密復元値として生成するステップと、を含む、秘密分散方法。請求項25の秘密分散方法であって、前記ステップは、SUBSKSEb1Σι2Icoefιbιをψ0に対応する前記秘密復元値として生成するステップと、SUBSKcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι又は、SUBSKshareΣι1nvιb1Σιn1nζcoefιbιを各λに対応する前記秘密復元値として生成するステップと、を含む、秘密分散方法。請求項13の分散装置としてコンピュータを機能させるためのプログラム。請求項14の分散管理装置としてコンピュータを機能させるためのプログラム。請求項15の取得装置としてコンピュータを機能させるためのプログラム。請求項13の分散装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。請求項14の分散管理装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。請求項15の取得装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。以下の条件を満たす方式を想定する。分散装置が秘密情報MSKを秘密分散して複数のシェア情報SHSHを生成し、これらを複数の分散管理装置PAPAに分散して管理させる。各分散管理装置PAPAがそれぞれ何らかの演算を実行する。取得装置は、秘密情報MSKを得ることはできないが、所定数以上の分散管理装置で生成された演算結果が与えられた場合に、秘密情報MSKと任意な値σとを被演算子に含む演算の結果に対応する生成情報を得ることができる。しかし、このような方式を実現することは容易ではない。すなわち、各分散管理装置PAPAがそれぞれ互いに独立な値σσを用いて演算を実行したのでは、取得装置は各分散管理装置の演算結果をシェア情報とした復元処理を正しく実行することができず、所望の生成情報が得られない。一方、値σは生成情報を推測するための情報となり得るため、すべての分散管理装置PAPAが値σそのものを共有することは、安全性の観点から好ましくない。本発明はこのような点に鑑みてなされたものであり、上記条件1~3を満たす方式を安全に実現することを目的とする。本発明では、分散装置とΣα1Lh個の分散管理装置PA1HH≧2と取得装置とによって秘密分散処理が実行される。分散装置が、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ0Ψとし、nを1以上の整数とし、ζを0以上の整数とし、巡回群G2の生成元をg2とし、θζβ1nζn≧1ζ≧1に対する巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルをbig2θζg2∈G2nζとした場合における、基底ベクトルbiの各要素θg2に応じた値を、それぞれH個の分散管理装置PAPAからなる部分集合SUBごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θg2に応じた値のシェア情報SH1Hを生成する。分散管理装置PAが、部分集合SUBごとに共有される共通情報と、シェア情報SH1Hとに対し、部分集合SUBごとに共通の共通演算を行って分散秘密値DSHを生成する。取得装置が、同一の部分集合SUBに対応する複数の分散秘密値DSHを用い、前記秘密分散方式に従った部分集合SUBごとの復元処理によって当該部分集合SUBごとの秘密復元値SUBSKを生成し、秘密復元値SUBSKを用いて生成情報Dを生成する。本発明では、部分集合SUBごとに独立に秘密情報である基底ベクトルbiを秘密分散し、部分集合SUBごとに共有される共通情報を用い、分散秘密値DSHを生成する。この場合、部分集合SUB単位では、分散秘密値DSHをシェア情報とした復元処理を正しく実行できる。共通情報は部分集合SUBごとに共有され、すべての分散管理装置PAに共有されないため、安全性が高い。以上のように、本発明では、上記条件1~3を満たす方式を安全に実現することができる。以下、図面を参照して本発明の実施形態を説明する。第1実施形態まず、本発明の第1実施形態を説明する。定義本形態で使用する用語や記号を定義する。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献1ISOIEC180332InformationtechnologySecuritytechniquesEncryptionalgorithmsPart2Asymmetricciphersに開示されている。0F:0Fは有限体Fqの加法単位元を表す。1F:1Fは有限体Fqの乗法単位元を表す。E:Eは有限体Fq上で定義された楕円曲線を表す。楕円曲線Eは、以下に示すアフィンaffine座標上のWeierstrass方程式を満たすxy∈Fqからなる点の集合と無限遠点と呼ばれる特別な点Oとを含む集合である。y2a1xya3yx3a2x2a4xa6ただし、a1a2a3a4a6∈Fqを満たす。楕円曲線E上の任意の2点に対して楕円加算と呼ばれる二項演算が定義され、楕円曲線E上の任意の1点に対して逆元演算と呼ばれる単項演算-が定義される。楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている例えば、参考文献1、参考文献2RFC5091IdentityBasedCryptographyStandard1SupersingularCurveImplementationsoftheBFandBB1Cryptosystems、参考文献3イアンFブラケ、ガディエルセロッシ、ナイジェルPスマート=著、楕円曲線暗号、出版=ピアソンエデュケーション、ISBN4894714310等参照。楕円曲線E上の有理点からなる有限集合は位数pの部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数をEとし、pをEを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合Epは、楕円曲線E上の有理点からなる有限集合の部分群を構成する。楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値pAがpA=Oを満たす点を意味する。GGは巡回群を表す。巡回群Gの具体例は、楕円曲線Eのp等分点からなる有限集合Ep、その部分群、剰余群などである。本形態では、巡回群G上で定義された演算を加法的に表現する。すなわち、χ∈Fq及びΩ∈Gに対するχΩ∈Gは、Ω∈G1に対して巡回群Gで定義された演算をχ回施すことを意味し、Ω1Ω2∈Gに対するΩ1Ω2∈Gは、Ω1∈GとΩ2∈Gとを被演算子として巡回群Gで定義された演算を行うことを意味する。g:gは巡回群Gの生成元を表す。<全体構成>図1は、第1実施形態の秘密分散システムの全体構成を説明するためのブロック図である。図1に例示するように、本形態の秘密分散システム1は、分散装置110と、Σα1Lh個の分散管理装置PA1HH≧2120-α-hαと、取得装置130と、共有値生成装置140-1~Lとを有し、それらはネットワーク150を通じて通信可能である。説明を簡略化するため、本形態では、分散装置110及び取得装置130が1つずつ存在する構成を例示するが、分散装置110及び/又は取得装置130が2以上存在してもよい。同様な理由により、本形態では、Σα1Lh個の分散管理装置PA120-α-hαからなる集合が1つのみ存在する構成を例示するが、このような集合が複数存在していてもよい。図1に例示するように、Σα1Lh個の分散管理装置PA120-α-hαからなる集合は、H個の分散管理装置PAPAからなる複数の部分集合SUBごとに区分される。各部分集合SUBには、それぞれ、各部分集合SUBごとに共有される共有値σを生成する共有値生成装置140-αがそれぞれ対応する。<分散装置110>図2は、図1の分散装置110の構成を説明するためのブロック図である。図5Aは、図2の秘密分散部114-αの詳細を説明するためのブロック図である。図2に例示するように、本形態の分散装置110は、一時記憶部111と、記憶部112と、制御部113と、秘密分散部114-αα1Lと、送信部115とを有する。図5Aに例示するように、本形態の秘密分散部114-αは、関数選択部114a-αと、インデックス生成部114b-αと、分散処理部114c-αとを有する。本形態の分散装置110は、例えば、CPUCentralProcessingUnit、RAMRandomAccessMemory、ROMReadOnlyMemory等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部111及び記憶部112は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部113及び秘密分散部114-αα1Lは、例えば、CPUが所定のプログラムを実行することで構成される処理部である。制御部113及び秘密分散部114-αα1Lの少なくとも一部が特別な集積回路であってもよい。送信部115は、例えば、モデム、LANLocalAreaNetworkカード等の通信装置である。分散装置110は、制御部113の制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部111又は記憶部112に格納される。一時記憶部111又は記憶部112に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。<分散管理装置PA120-α-hα>図3Aは、第1実施形態の分散管理装置PA120-α-hαの構成を説明するためのブロック図である。図5Bは、図3Aの分散秘密値生成部124-α-hαの詳細を説明するためのブロック図である。図3Aに例示するように、本形態の分散管理装置PA120-α-hαは、一時記憶部121-α-hαと、記憶部122-α-hαと、制御部123-α-hαと、分散秘密値生成部124-α-hαと、送信部125-α-hαと、受信部126-α-hαとを有する。図5Bに例示するように、分散秘密値生成部124-α-hαは、線形演算部124a-α-hαと、分散秘密値合成部124b-α-hαとを有する。分散管理装置PA120-α-hαは、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部121-α-hα及び記憶部122-α-hαは、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部123-α-hα及び分散秘密値生成部124-α-hαは、例えば、CPUが所定のプログラムを実行することで構成される処理部である。なお、制御部123-α-hα及び分散秘密値生成部124-α-hαの少なくとも一部が特別な集積回路であってもよい。送信部125-α-hαや受信部126-α-hαは、例えば、モデム、LANカード等の通信装置である。分散管理装置PA120-α-hαは、制御部123-α-hαの制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部121-α-hα又は記憶部122-α-hαに格納される。一時記憶部121-α-hα又は記憶部122-α-hαに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。<共有値生成装置140-α>図3Bは、第1実施形態の共有値生成装置140-αの構成を説明するためのブロック図である。図3Bに例示するように、本形態の共有値生成装置140-αは、乱数生成部141-α及び送信部142-αを有する。本形態の共有値生成装置140-αは、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置であるが、乱数生成部141-αが特別な集積回路であってもよい。<取得装置130>図4は、第1実施形態の取得装置130の構成を説明するためのブロック図である。図6は、図4の復元部134-αの詳細を説明するためのブロック図である。図4に例示するように、本形態の取得装置130は、一時記憶部131と、記憶部132と、制御部133と、復元部134-αα1Lと、合成部137と、送信部135と、受信部136とを有する。図6に例示するように、復元部134-αは、係数算出部134a-αと、多項式演算部134b-αとを有する。本形態の取得装置130は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部131及び記憶部132は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部133、復元部134-αα1L及び合成部137は、例えば、CPUが所定のプログラムを実行することで構成される処理部である。制御部133、復元部134-αα1L及び合成部137の少なくとも一部が特別な集積回路であってもよい。送信部135や受信部136は、例えば、モデム、LANカード等の通信装置である。取得装置130は、制御部133の制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部131又は記憶部132に格納される。一時記憶部131又は記憶部132に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。<秘密分散処理>本形態の秘密分散処理を説明する。事前処理本形態の秘密分散処理の事前処理として、秘密情報θg∈Gを特定するための情報θ∈Fqが分散装置110の記憶部112に格納される。秘密分散処理の全体図7は、第1実施形態の秘密分散処理の全体を説明するための図である。以下、図7を用いて、本形態の秘密分散処理の全体を説明する。本形態では、まず、分散装置110図1が、部分集合SUBごとに独立に、秘密情報θg∈Gを秘密分散してシェア情報SH1Hを生成し、当該シェア情報SHを出力するステップS11。各シェア情報SHは、それぞれ、ネットワーク150経由で各分散管理装置PA120-α-hαに分散して送信される。各シェア情報SHが送信された各分散管理装置PA120-α-hαは、それぞれ、そのシェア情報SHと、部分集合SUBごとに共有される共有値σを含む共通情報とを用い、所定の共通演算を行って分散秘密値DSHを生成し、当該分散秘密値DSHを出力するステップS12。本形態の場合、互いに異なる部分集合SUBでそれぞれ共有される共有値σは互いに独立である。同一の部分集合SUBに属する分散管理装置PA120-α-hαがそれぞれ用いる共通情報は互いに同一である。特に、本形態で例示する共通情報は、共有値σと、取得装置130から提供されたすべての分散管理装置PA120-α-hαに共通の提供情報vとを含む。同一の部分集合SUBに属する分散管理装置PA120-α-hαがそれぞれ行う共通演算は互いに同一である。本形態では、すべての共通演算が同一であるものとする。本形態の共通演算は、線形性を持った演算である。各分散管理装置PA120-α-hαから出力された各分散秘密値DSHは、それぞれ、ネットワーク150経由で取得装置130に送信される。取得装置130は、同一の部分集合SUBに対応する複数の分散秘密値DSHを用い、部分集合SUBごとの復元処理によって秘密復元値SUBSKを生成するステップS13。次に、取得装置130は、各部分集合SUBについてそれぞれ生成された秘密復元値SUBSKを用いて生成情報SKを生成し、当該生成情報SKを出力するステップS14。なお、本形態では、取得装置130が秘密復元値SUBSKを線形結合して生成情報SKする。分散装置の処理ステップS11図8Aは、第1実施形態の分散装置の処理を例示するための図であり、図8Bは、ステップS112の処理の詳細を例示するための図である。以下、これらの図を用いて、分散装置110の処理の詳細を説明する。まず、分散装置110図2の制御部113が、α1に設定し、その設定内容を一時記憶部111に格納するステップS111。次に、記憶部112から秘密情報θg∈Gを特定するための情報θ∈Fqが読み出され、秘密分散部114-αに入力される。秘密分散部114-αは、情報θ∈Fqを用いて秘密情報θg又は情報θを、所定の秘密分散方式に従って秘密分散し、部分集合SUBに対するH個のシェア情報SHSHを生成して出力するステップS112。《ステップS112の詳細》本形態の秘密分散部114-αは、各部分集合SUBに対し、,Hしきい値秘密分散方式但し、Rは、2≦R<Hを満たす定数を用い、秘密情報を秘密分散して得られるシェア情報SH1Hを生成する。図8Bに例示するように、まず、秘密分散部114-α図5Aの関数選択部114a-αが、予め定められた有限体Fqの元ω∈Fqに対してfθを満たすR1次の多項式をf∈Fqをランダムに選択して出力するステップS112a。なお、xは有限体Fqの元からなる変数であり、元ω∈Fqの一例は0Fである。次に、インデックス生成部114b-αが、各h1Hに対応するインデックスφ∈Fqを生成して出力する。なお、インデックスφh∈Fqとする場合や、すでにインデックスφ∈Fqが得られている場合には、ステップS112の処理は省略されてもよい。次に、分散処理部114c-αが、多項式f∈Fqとインデックスφ∈Fqとを用い、以下のシェア情報SH1Hを生成する。SHfg∈G...分散処理部114c-αはシェア情報SHを出力するステップS112c/《ステップS112の詳細》の説明終わり。次に、制御部113は、一時記憶部111に格納されたαがLであるか否かを判定するステップS113。ここで、αLでないと判定された場合、制御部113は、α1を新たなαとし、その設定内容を一時記憶部111に格納しステップS114、新たなαによってステップS112の処理を実行させる。一方、ステップS113でαLであると判定された場合、各秘密分散部114-αから出力された各シェア情報SHが送信部115に送られる。送信部115は、各シェア情報SHを、それぞれ、ネットワーク150経由で分散管理装置PA120-α-hに送信するステップS115。すなわち、シェア情報SHは分散管理装置PA120-1-1に、シェア情報SHは分散管理装置PA120-1-2に、シェア情報SHは分散管理装置PA120-L-HLに、それぞれ送信される。[共有値生成装置の処理]各共有値生成装置140-α図3Bは、自らに対応する部分集合SUBを構成する各分散管理装置PA120-α-hで共有する共有値σを生成する。本形態では、乱数生成部141-αが生成した乱数を共有値σとし、送信部142-αが共有値σを、部分集合SUBを構成する各分散管理装置PA120-α-hに送信する。[分散管理装置の処理ステップS12]図9Aは、第1実施形態の分散管理装置PA120-α-hの処理を例示するための図であり、図9Bは、ステップS124の処理の詳細を例示するための図である。以下、これらの図を用いて、本形態の分散管理装置PA120-α-hの処理を説明する。まず、分散管理装置PA120-α-h図3Aの受信部126-α-hが、送信されたシェア情報SHを受信し、それを記憶部122-α-hに格納するステップS121。なお、過去にステップS121の処理が実行され、既にシェア情報SHが分散管理装置PA120-α-hの記憶部122-α-hに格納されているのであれば、ステップS121の処理を省略してもよい。分散管理装置PA120-α-hの受信部126-α-hは、共有値生成装置140-αから送信された共有値σを受信し、それを記憶部122-α-hに格納するステップS122。本形態では、取得装置130図4の記憶部132から読み出された提供情報vが送信部135からネットワーク150経由で各分散管理装置PA120-α-hに送信される。この提供情報vは、すべての分散管理装置PA120-α-hαに共通である。提供情報vは、分散管理装置PA120-α-h図3Aの受信部126-α-hで受信され、記憶部122-α-hに格納されるステップS123。次に、分散秘密値生成部124-α-hが、記憶部122-α-hからシェア情報SHと共有値σと提供情報vとを読み込む。分散秘密値生成部124-α-hは、共有値σと提供情報vとを含む共通情報と、シェア情報SHとを用い、共通演算FNC1を行って分散秘密値DSHを生成し、当該分散秘密値DSHを出力するステップS124。《ステップS124の詳細》同一の部分集合SUBに属する分散管理装置PA120-α-hの分散秘密値生成部124-α-hがそれぞれ用いる共通情報は互いに同一であり、同一の部分集合SUBに属する分散管理装置PA120-α-hの分散秘密値生成部124-α-hがそれぞれ行う共通演算は互いに同一である。本形態のシェア情報は式に示すものである。図9Bに例示するように、まず、本形態の分散秘密値生成部124-α-hの線形演算部124a-α-hαに、共有値σと提供情報vとシェア情報SHfgのfgとが入力される。線形演算部124a-α-hαは以下の演算を行い、その演算結果dshを出力するステップS124a。dshσvfg∈G...出力された演算結果dshは、分散秘密値合成部124b-α-hαに入力される。分散秘密値合成部124b-α-hαには、さらにシェア情報SHfgのインデックスφが入力され、分散秘密値合成部124b-α-hαは、以下の演算によって分散秘密値DSHを生成する。DSHdsh...分散秘密値合成部124b-α-hαは分散秘密値DSHを出力するステップS124b/《ステップS124の詳細》の説明終わり。生成された分散秘密値DSHは送信部125-α-hαに送られる。送信部125-α-hαは、分散秘密値DSHをネットワーク150経由で取得装置130に送信するステップS125。[取得装置の処理ステップS13,S14]図10Aは、第1実施形態の取得装置の処理を例示するための図であり、図10Bは、ステップS134の処理を例示するための図である。各分散管理装置PA120-α-hから送信された分散秘密値DSHは、取得装置130図4の受信部136で受信され、記憶部132に格納されるステップS131。次に、制御部133が、必要数以上の分散秘密値DSHが記憶部132に格納されたか否かを判定するステップS132。本形態の場合、各α1Lについて、それぞれ、相違なるR2≦R<H個以上の分散秘密値DSHが記憶部132に格納されたか否かを判定する。ここで、必要数以上の分散秘密値DSHが記憶部132に格納されていないと判定された場合には、ステップS131の処理に戻される。一方、必要数以上の分散秘密値DSHが記憶部132に格納されたと判定された場合、制御部133が、α1に設定し、その設定内容を一時記憶部131に格納するステップS133。次に、記憶部132から部分集合SUBに対応する必要数分の分散秘密値DSHが読み出され、復元部134-αに入力される。復元部134-αは、入力された分散秘密値DSHを用い、前述のステップS112で用いられた秘密分散方式に従った部分集合SUBごとの復元処理によって秘密復元値SUBSKを生成し、当該部分集合SUBごとの秘密復元値SUBSKを出力するステップS134。《ステップS134の詳細》本形態の分散秘密値DSHは式に示すものである。復元部134-α図6には、αごとにR個ずつの相違なる分散秘密値DSHが入力される。以下では、復元部134-αに入力される各αに対応する分散秘密値DSHを以下のように表現する。DSHdsh1...DSHdshRただし、以下が満たされる。φR⊂φ...dshR⊂dsh...図10Bに例示するように、式に示すDSHDSHの各インデックスφ1φRが係数算出部134a-αに入力され、係数算出部134a-αは、各ρ1Rについて、それぞれ以下の演算を行い、各係数λρを生成して出力するステップS134a。生成された各係数λρと、式に示すDSHDSHのdsh1dshRとが、多項式演算部134b-αに入力される。多項式演算部134b-αは、以下の演算によって部分集合SUBの秘密復元値SUBSKを生成する。SUBSKλ1dsh1λRdshR∈G...多項式演算部134b-αは、秘密復元値SUBSKを出力するステップS134b/《ステップS134の詳細》の説明終わり。制御部133は、一時記憶部131に格納されたαがLであるか否かを判定するステップS135。ここで、αLでないと判定された場合、制御部133は、α1を新たなαとし、その設定内容を一時記憶部131に格納しステップS136、新たなαによってステップS134の処理を実行させる。一方、ステップS135でαLであると判定された場合、各復元部134-αから出力された各秘密復元値SUBSKが合成部137に送られる。合成部137は、各部分集合SUBについてそれぞれ生成された各秘密復元値SUBSKを用いて、以下の生成情報SKを生成し、当該生成情報SKを出力するステップS141。SKFNC2SUBSK...《ステップS141の詳細》以下に式の具体例を示す。具体例1:SKSUBSKSUBSK∈G...具体例2:SKCE1SUBSKCELSUBSK∈G...ただし、CEα∈Fqは係数であり、その一例はLの乗法逆元1∈Fqである。また、係数CE1CELの何れか一部を0Fとしてもよい。この場合には、SUBSKSUBSKの一部のみを用いて生成情報SKが生成される。この際、合成部137が、係数CE1CELのうち0Fとする係数をランダムに選択してもよい。これにより、安全性が向上する。合成部137が、係数CE1CELを自由に設定できる構成でもよい。これにより、取得装置130は、信頼性が低い部分集合SUBに対応する秘密復元値SUBSKを使用せずに生成情報SKを生成すること等が可能となる《ステップS141の詳細》の説明終わり。<第1実施形態の特徴>本形態では、分散装置110が部分集合SUBごとに独立に秘密情報θg∈Gを秘密分散してシェア情報SHを生成し、各分散管理装置PA120-α-hが、共有値σと提供情報vを含む共通情報とシェア情報SHとを用い、共通演算を行って分散秘密値DSHを生成し、取得装置130が、同一の部分集合SUBに対応する複数の分散秘密値DSHを用い、部分集合SUBごとの復元処理によって秘密復元値SUBSKを生成し、秘密復元値SUBSKを用いて生成情報SKを生成することとした。このように部分集合SUBごとに共有される共有値σを用い、部分集合SUBごとに秘密分散、共通演算、復元処理を行うため、これらの処理の実行は可能である。さらに、すべての分散管理装置PA120-α-hが値σを共有するのではなく、部分集合SUBごとに独立に共有値σを共有するため、安全性が高い。特に、本形態では、互いに異なる部分集合SUBでそれぞれ共有される共有値σは、互いに独立なものとした。これにより、高い安全性を確保できる。本形態では、分散管理装置PA120-α-hがすべて同一の共通演算FNC1を行うこととした。本形態の共通演算FNC1は、線形性を持った演算である。よって、本形態では、秘密復元値SUBSKを線形結合して生成情報SKを生成することにより、各秘密復元値SUBSKを用いて生成された生成情報SKを、秘密情報θgと或る値σとを被演算子として共通演算FNC1を行った結果と同一にすることができる。本形態では、,Hしきい値秘密分散方式を用い、部分集合SUBごとに秘密情報θg∈Gを秘密分散した。この構成は、例えば、シェア情報SHが、有限体Fqの元からなる変数をxとし、予め定められた有限体Fqの元ω∈Fqに対してfθを満たすR1次の多項式をf∈Fqとし、hに対応するインデックスをφとした場合における、巡回群Gの元fg∈Gを含む構成とすることで可能である。このように巡回群の元である秘密情報θg∈Gを秘密分散することで、たとえ、シェア情報SHから復元された秘密情報θgが外部に漏洩したとしても、巡回群Gでの離散対数問題の求解が困難であるとの前提のもとでは、θが外部に漏洩することはない。これにより、高い安全性を確保できる。第1実施形態の変形例1次に、第1実施形態の変形例1を説明する。第1実施形態では、巡回群Gの元を秘密情報θg∈Gとし、これを秘密分散した。しかし、有限体Fqの元θ∈Fqを秘密分散してもよい。この場合、,Hしきい値秘密分散方式を用いて秘密分散されたシェア情報SHは、有限体Fqの元からなる変数をxとし、予め定められた有限体Fqの元ω∈Fqに対してfθを満たすR1次の多項式をf∈Fqとし、hに対応するインデックスをφとした場合における、有限体Fqの元f∈Fqを含む。図11Aは、第1実施形態における変形例1の秘密分散部214-αの構成を説明するための図であり、図11Bは、第1実施形態における変形例1の分散秘密値生成部224-α-hαの構成を説明するための図である。なお、これらの図において、第1実施形態と共通する部分については、第1実施形態と同じ符号を付した。第1実施形態の変形例1の秘密分散システム2は、分散装置110が分散装置210に置換され、分散管理装置120-α-hαα1Lが分散管理装置220-α-hαα1Lに置換される。秘密分散部114-αα1Lが図11Aに示すような秘密分散部214-αα1Lに置換され、分散秘密値生成部124-α-hαα1Lが図11Bに示すような分散秘密値生成部224-α-hαα1Lに置換される。その他の構成は、第1実施形態と同様である。《第1実施形態の変形例1におけるステップS112の変形》第1実施形態の変形例1では、図8Bに示したステップS112の処理が以下のように変形される。まず、図8Bに示したステップS112a及びS112bが実行される。次に、ステップS112cの代わりに、秘密分散部214-αの分散処理部214c-α図11Aが、多項式f∈Fqとインデックスφ∈Fqとを用い、以下のシェア情報SHを生成して出力する。SHf...《第1実施形態の変形例1におけるステップS124の変形》第1実施形態の変形例1では、図9Bに示したステップS124の処理が以下のように変形される。まず、ステップS124aの代わりに、線形演算部224a-α-hα図11Bに、共有値σと提供情報vとシェア情報SHfのfとが入力され、線形演算部224a-α-hαは、以下の演算を行い、その演算結果dsh∈Gを出力する。dshσvfg∈G...演算結果dsh∈Gは分散秘密値DSHの一部の情報となる。その後、図9Bに示したステップS124bの処理を実行する《第1実施形態の変形例1におけるステップS124の変形》の説明終わり。その他の処理は、第1実施形態と同様である。第1実施形態の変形例2次に、第1実施形態の変形例2を説明する。第1実施形態の変形例2でも有限体Fqの元θ∈Fqを秘密分散する。第1実施形態の変形例1との相違点は、演算結果dshが巡回群Gの元ではなく、有限体Fqの元である点である。図12Aは、第1実施形態における変形例2の分散秘密値生成部324-α-hαの構成を説明するための図であり、図12Bは、第1実施形態における変形例2の復元部334-αの構成を説明するための図である。なお、これらの図において、第1実施形態と共通する部分については、第1実施形態と同じ符号を付した。第1実施形態の変形例2の秘密分散システム3は、分散装置110が分散装置210に置換され、分散管理装置120-α-hαα1Lが分散管理装置320-α-hαα1Lに置換され、取得装置130が取得装置330に置換される。また、分散秘密値生成部124-α-hαα1Lが図12Aに示すような分散秘密値生成部324-α-hαα1Lに置換され、復元部134-αα1Lが図12Bに示すような復元部334-αα1Lに置換される。その他の構成は、第1実施形態と同様である。《第1実施形態の変形例2におけるステップS112の変形》第1実施形態の変形例1におけるステップS112の変形と同一である。《第1実施形態の変形例2におけるステップS124の変形》第1実施形態の変形例2では、図9Bに示したステップS124の処理が以下のように変形される。まず、ステップS124aの代わりに、線形演算部324a-α-hα図12Aに、共有値σと提供情報vとシェア情報SHfのfとが入力され、線形演算部324a-α-hαが、以下の演算を行い、その演算結果dsh∈Fqを出力する。dshσvf∈Fq...演算結果dsh∈Fqは分散秘密値DSHの一部の情報となる。その後、図9Bに示したステップS124bの処理を実行する。《第1実施形態の変形例2におけるステップS134の変形》まず、図10Bに示したステップS134aの処理が実行される。次に、10Bに示したステップS134bの処理の代わりに、各係数λρと、式に示すDSHDSHのdsh1dshRとが、多項式演算部334b-α図12Bに入力され、多項式演算部334b-αが、以下の演算によって、部分集合SUBの秘密復元値SUBSKを生成する。SUBSKλ1dsh1λRdshRg∈G...多項式演算部334b-αは、部分集合SUBの秘密復元値SUBSKを出力する《第1実施形態の変形例2におけるステップS134の変形》の説明終わり。その他の処理は、第1実施形態と同様である。第1実施形態の変形例3第1実施形態の変形例3は、,Hしきい値秘密分散方式の代わりに,Hしきい値秘密分散方式を用いて秘密情報を秘密分散する変形例である。図13Aは、第1実施形態における変形例3の秘密分散部414-αの構成を説明するための図であり、図13Bは、第1実施形態における変形例3の分散秘密値生成部424-α-hαの構成を説明するための図であり、図13Cは、第1実施形態における変形例3の復元部434-αの構成を説明するための図である。第1実施形態の変形例3の秘密分散システム4は、分散装置110が分散装置410に置換され、分散管理装置120-α-hαα1Lが分散管理装置420-α-hαα1Lに置換され、取得装置130が取得装置430に置換される。秘密分散部114-αα1Lが図13Aに示すような秘密分散部414-αα1Lに置換され、分散秘密値生成部124-α-hαα1Lが図13Bに示すような分散秘密値生成部424-α-hαα1Lに置換され、復元部134-αα1Lが図13Cに示すような復元部434-αα1Lに置換される。その他の構成は、第1実施形態と同様である。《第1実施形態の変形例3におけるステップS112の変形》第1実施形態の変形例3では、図8Bに示したステップS112の処理が以下のように変形される。まず、秘密分散部414-α図13Aの乱数生成部414a-αにおいて、以下のH1個の巡回群Gの元をランダムに選択し、これらを出力する。SHSH1∈G...次に、逆元演算部414b-αに、秘密情報θg∈Gと、H1個の巡回群Gの元SHSH1∈Gとが入力される。逆元演算部414b-αは、以下の演算によって、SHを生成して出力する。SHθgSHSH1∈G...秘密分散部414-αは、以下を部分集合SUBのシェア情報として出力する。SHSH∈Gこれらのシェア情報は、以下の関係を満たす。SHSHSHθg∈G...《第1実施形態の変形例3におけるステップS124の変形》第1実施形態の変形例3では、図9Bに示したステップS124の処理が以下のように変形される。まず、分散秘密値生成部424-α-h図13Bに、共有値σと提供情報vとシェア情報SHSHとが入力される。分散秘密値生成部424-α-hは、以下の演算によって、分散秘密値DSHを生成して出力するDSHσvSH∈G...《第1実施形態の変形例3におけるステップS132の変形》第1実施形態の変形例3では、図10Aに示したステップS132の処理が以下のように変形される。この変形例3でも、制御部133が、必要数以上の分散秘密値DSHが記憶部132に格納されたか否かを判定するが、変形例3での必要数はH個である。つまり、この変形例3の場合、各α1Lについて、それぞれ、すべての分散秘密値DSHが記憶部132に格納されたか否かが判定される。《第1実施形態の変形例3におけるステップS134の変形》第1実施形態の変形例3では、図10Bに示したステップS134の処理が以下のように変形される。この変形例3の分散秘密値DSHは式に示すものである。また、復元部434-α図13Cには、αに対応するすべての分散秘密値DSHh1Hが入力される。復元部434-αは、以下の演算によって、部分集合SUBの秘密復元値SUBSKを生成して出力する。SUBSKDSHDSH∈G...その他の処理は、第1実施形態と同様である。第1実施形態の変形例4第1実施形態の変形例4も、,Hしきい値秘密分散方式の代わりに,Hしきい値秘密分散方式を用いて秘密情報を秘密分散する変形例である。変形例3との相違点は、有限体Fqの元である秘密情報θ∈Fqを秘密分散する点である。図14Aは、第1実施形態における変形例4の秘密分散部514-αの構成を説明するための図であり、図14Bは、第1実施形態における変形例4の分散秘密値生成部524-α-hαの構成を説明するための図であり、図14Cは、第1実施形態における変形例4の復元部534-αの構成を説明するための図である。第1実施形態の変形例4の秘密分散システム5は、分散装置110が分散装置510に置換され、分散管理装置120-α-hαα1Lが分散管理装置520-α-hαα1Lに置換され、取得装置130が取得装置530に置換される。秘密分散部114-αα1Lが図14Aに示すような秘密分散部514-αα1Lに置換され、分散秘密値生成部124-α-hαα1Lが図14Bに示すような分散秘密値生成部524-α-hαα1Lに置換され、復元部134-αα1Lが図14Cに示すような復元部534-αα1Lに置換される。その他の構成は、第1実施形態と同様である。《第1実施形態の変形例4におけるステップS112の変形》第1実施形態の変形例4では、図8Bに示したステップS112の処理が以下のように変形される。まず、秘密分散部514-α図14Aの乱数生成部514a-αにおいて、以下のH1個の有限体Fqの元をランダムに選択し、これらを出力する。SHSH1∈Fq...次に、逆元演算部514b-αに、秘密情報θ∈Fqと、H1個の有限体Fqの元SHSH1∈Fqとが入力される。逆元演算部514b-αは、以下の演算によって、SHを生成して出力する。SHθSHSH1∈Fq...秘密分散部514-αは、以下を部分集合SUBのシェア情報として出力する。SHSH∈Fq...これらのシェア情報は、以下の関係を満たす。SHSHSHθ∈Fq...《第1実施形態の変形例4におけるステップS124の変形》第1実施形態の変形例4では、図9Bに示したステップS124の処理が以下のように変形される。まず、分散秘密値生成部524-α-h図14Bに、共有値σと提供情報vとシェア情報SHSHとが入力される。分散秘密値生成部524-α-hは、以下の演算によって、分散秘密値DSHを生成して出力する。DSHσvSH∈Fq...《第1実施形態の変形例4におけるステップS132の変形》第1実施形態の変形例3と同じである。《第1実施形態の変形例4におけるステップS134の変形》第1実施形態の変形例4では、図10Bに示したステップS134の処理が以下のように変形される。この変形例4の分散秘密値DSHは式に示すものである。復元部534-α図14Cには、αに対応するすべての分散秘密値DSHh1Hが入力される。復元部534-αは、以下の演算によって、部分集合SUBの秘密復元値SUBSKを生成して出力する。SUBSKDSHDSHg∈G...その他の処理は、第1実施形態と同様である。第1実施形態のその他の変形例その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、第1実施形態の変形例4の式の代わりに、以下の式の演算を行い、式の代わりに式の演算を行ってもよい。DSHσvSH∈Fq...秘密復元値SUBSKが有限体Fqの元となる構成であってもよい。本形態では、各部分集合SUBに対してそれぞれ同一の秘密分散方式を用いて秘密分散を行ったが、互いに異なる各部分集合SUBに対して互いに異なる秘密分散方式を用いてもよい。本形態では、各部分集合SUBごとに共有値生成装置140-αを設けたが、各部分集合SUBの何れかの分散管理装置が共有値生成装置の機能を持っていてもよい。この場合には、共有値生成装置140-αは不要となる。本形態では、共有値σと提供情報vとを含む共通情報と、シェア情報SHとを用い、共通演算FNC1を行って分散秘密値DSHを生成することとした。しかし、提供情報vを用いることなく、共有値σを共通情報として分散秘密値DSHを生成してもよい。共通情報が、共有値σと提供情報vとその他の情報とを含んでもよい。分散秘密値DSHを求めるための共通演算は、部分集合SUBごとに統一する必要はあるが、必ずしも、互いに異なる部分集合SUB間で同一の共通演算を行う必要はない。第2実施形態次に、本発明の第2実施形態を説明する。本形態は第1実施形態を関数暗号の鍵生成に応用した形態である。<定義>本形態で使用する用語や記号を定義する。行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列と表現する。T:Tはの転置行列を表す。1:1はの逆行列を表す。∧:∧は論理積ANDを表す論理記号である。∨:∨は論理和ORを表す論理記号である。¬:¬は否定NOTを表す論理記号である。命題変数:命題変数は命題の真偽falsetrueを要素とする集合{真,偽}上の変数である。すなわち、命題変数の定義域は真偽を要素とする集合である。命題変数及び命題変数の否定を総称してリテラルliteralと呼ぶ。論理式:論理式とは数理論理学における命題を表す式を意味する。具体的には真及び偽は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Zsec0を表す。0:0は個の0からなる列を表す。1:1は個の1からなる列を表す。Fq:Fqは位数qの有限体を表す第1実施形態と同一。0F:0Fは有限体Fqの加法単位元を表す第1実施形態と同一。1F:は有限体Fqの乗法単位元を表す第1実施形態と同一。δ:δはクロネッカーのデルタ関数を表す。ijの場合にδ1Fを満たし、i≠jの場合にδ0Fを満たす。E:Eは有限体Fq上で定義された楕円曲線を表す第1実施形態と同一。楕円曲線E上の有理点からなる有限集合は位数pの部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数をEとし、pをEを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合Epは、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値pAがpA=Oを満たす点を意味する。G1G2GT:G1G2GTはそれぞれ位数qの巡回群を表す。巡回群G1G2の具体例は、楕円曲線Eのp等分点からなる有限集合Epやその部分群である。G1G2であってもよいしG1≠G2であってもよい。巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。巡回群G1G2GTの位数と有限体Fqの位数とを同一とすることで安全性が向上する。本形態では、巡回群G1G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。例えば、χ∈Fq及びΩ∈G1に対するχΩ∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1Ω2∈G1に対するΩ1Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、例えば、χ∈Fq及びΩ∈G2に対するχΩ∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1Ω2∈G2に対するΩ1Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、例えば、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1Ω2∈GTに対するΩ1Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。Ψ:Ψは1以上の整数を表す。ψ:ψは0以上Ψ以下の整数ψ0Ψを表す。λ:λは1以上Ψ以下の整数λ1Ψを表す。n:nは1以上の整数を表す。ζ:ζは0以上の整数を表す。G1nζ:G1nζはnζ個の巡回群G1の直積を表す。G2nζ:G2nζはnζ個の巡回群G2の直積を表す。g1g2gT:g1g2gTは巡回群GG1G2GTの生成元を表す。V:Vはnζ個の巡回群G1の直積からなるnζ次元のベクトル空間を表す。V:Vはnζ個の巡回群G2の直積からなるnζ次元のベクトル空間を表す。eψ:eψは直積G1nζと直積G2nζとの直積G1nζ×G2nζを巡回群GTに写す非退化な双線形写像bilinearmapを表す。双線形写像eψは、巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力とし、巡回群GTの1個の元を出力する。eψ:G1nζ×G2nζ→GT...双線形写像eψは以下の性質を満たす。[双線形性]双線形写像eψは、すべてのΓ1∈G1nζ,Γ2∈G2nζ及びν,κ∈Fqについて以下の関係を満たす。eψeψνκ...[非退化性]双線形写像eψは、すべてのΓ1∈G1nζ,Γ2∈G2nζを巡回群GTの単位元に写す写像ではない。[計算可能性]あらゆるΓ1∈G1nζ,Γ2∈G2nζ...についてeψを効率的に計算するアルゴリズムが存在する。本形態では、以下のような、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を用いて双線形写像eψを構成する。PairG1×G2→GT...本形態の双線形写像eψは、巡回群G1のnζ個の元γβζからなるnζ次元ベクトルζと、巡回群G2のnζ個の元γβζからなるnζ次元ベクトルζとの入力に対し、巡回群GTの1個の元を出力する。eψ:Πβ1nζPair...双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力する。双線形写像Pairは、以下の性質を満たす。[双線形性]双線形写像Pairは、すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。PairPairνκ...[非退化性]双線形写像Pairは、すべてのΩ1∈G1,Ω2∈G2...を巡回群GTの単位元に写す写像ではない。[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPairを効率的に計算するアルゴリズムが存在する。双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である例えば、参考文献4AlfredJMenezes,ELLIPTICCURVEPUBLICKEYCRYPTOSYSTEMS,KLUWERACADEMICPUBLISHERS,ISBN0792393686,pp6181等参照。楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数eΩ1∈G1,Ω2∈G2を双線形写像Pairとして用いてもよい例えば、参考文献2等参照。ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMillerのアルゴリズム参考文献5VSMillerShortProgramsforfunctionsonCurves1986,インターネット<httpcryptostanfordedumillermillerpdf>などが存在する。ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている例えば、参考文献2、参考文献6AMiyajiMNakabayashiSTakanoNewexplicitconditionsofellipticcurveTracesforFRReductionIEICETransFundamentalsvolE84Ano05pp12341243May2001、参考文献7PSLMBarretoBLynnMScottConstructingellipticcurveswithprescribedembeddingdegreesProcSCN2002LNCS2576pp257267SpringerVerlag2003、参考文献8RDupontAEngeFMorainBuildingcurveswitharbitrarysmallMOVdegreeoverfiniteprimefieldshttpeprintiacrorg2002094等参照。aiζ:aiは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1g1∈G1をi次元目の要素とし、残りのnζ1個の要素を巡回群G1の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、nζ次元の基底ベクトルaiζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ11Fである。基底ベクトルaiは直交基底であり、巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiは前述のベクトル空間Vを張る。aiζ:aiは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ2g2∈G2をi次元目の要素とし、残りのnζ1個の要素を巡回群G2の単位元加法的に0と表現とするnζ次元の基底ベクトルである。この場合、基底ベクトルaiζの各要素をそれぞれ列挙して表現すると、以下のようになる。a1a2...anζここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ21Fである。基底ベクトルaiは直交基底であり、巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルaiζの線形和によって表される。すなわち、nζ次元の基底ベクトルaiは前述のベクトル空間Vを張る。基底ベクトルaiと基底ベクトルaiとは、0Fを除く有限体Fqの元τκ1κ2について以下の関係を満たす。eψajgTτδ...すなわち、ijの場合には、式の関係から以下の関係が満たされる。eψajPairPairPairPairκ1κ2Pair00Pair00Pairκ1κ2gTτ上付き添え字κ1,κ2はそれぞれκ1,κ2を表す。一方、i≠jの場合には、eψajΠi1nζPairajの右辺は、Pairを含まず、PairとPairとPairとの積になる。さらに、式の関係からPairPairPair0を満たす。そのため、i≠jの場合には、以下の関係を満たす。eψajeψ0gT0特に、τκ1κ21Fである場合例えば、κ1κ21Fの場合、eajgTδ...を満たす。gT01は巡回群GTの単位元であり、gT1gTは巡回群GTの生成元である。基底ベクトルaiと基底ベクトルaiとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間双対ペアリングベクトル空間DPVSDualParingVectorspaceである。A:Aは基底ベクトルaiζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiζが式によって表現される場合、行列Aは以下のようになる。A:Aは基底ベクトルaiζを要素とするnζ行nζ列の行列を表す。例えば、基底ベクトルaiζが式によって表現される場合、行列Aは以下のようになる。X:Xは有限体Fqの元を要素とするnζ行nζ列の行列を表す。行列Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列ζj1nζの要素をχij∈Fqとすると、行列Xは以下のようになる。なお、行列Xの各要素χijを変換係数と呼ぶ。X:行列XはXτ1Tの関係を満たす行列である。ただし、τ∈Fqは有限体Fqに属する任意の定数であり、例えば、τ1Fである。Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列の要素をχij∈Fqとすると、行列Xは以下のようになる。なお、行列Xの各要素χijを変換係数と呼ぶ。この場合、nζ行nζ列の単位行列をIとするとXTτIを満たす。すなわち、単位行列を以下のように定義する。これについて以下が満たされる。ここで、nζ次元ベクトルを以下のように定義する。χi→χinζ...χj→χjnζ...すると、式の関係から、nζ次元ベクトルχi→とχj→との内積は、以下のようになる。χi→χj→τδ...bi:biは巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルを表す。biは行列Xを用いて基底ベクトルaiζを座標変換することで得られる。具体的には、基底ベクトルbiは、以下の演算によって得られる。biΣj1nζχijaj...例えば、基底ベクトルajζが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。biκ1g1χi2κ1g1χinζκ1g1...巡回群G1のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。bi:biは巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルを表す。biは行列Xを用いて基底ベクトルaiζを座標変換することで得られる。具体的には、基底ベクトルbiは、以下の演算によって得られる。biΣj1nζχijaj...例えば、基底ベクトルajζが式によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。biκ2g2χi2κ2g2χinζκ2g2...巡回群G2のnζ個の元を要素とするすべてのnζ次元ベクトルは、nζ次元の基底ベクトルbiζの線形和によって表される。すなわち、nζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。なお、基底ベクトルbiと基底ベクトルbiとは、0Fを除く有限体Fqの元τκ1κ2について以下の関係を満たす。eψbjgTττδ...すなわち、式の関係から、以下の関係が満たされる。特にτκ1κ21F例えば、κ1κ21F及びτ1Fである場合、以下の関係が満たされる。eψbjgTδ...基底ベクトルbiと基底ベクトルbiとは、双対ペアリングベクトル空間ベクトル空間Vとベクトル空間Vの双対正規直交基底である。式の関係を満たすのであれば、式で例示したもの以外の基底ベクトルai及びaiや、式で例示したもの以外の基底ベクトルbi及びbiを用いてもよい。B:Bは基底ベクトルbiζを要素とするnζ行nζ列の行列である。BXAを満たす。例えば、基底ベクトルbiが式によって表現される場合、行列Bは、以下のようになる。B:Bは基底ベクトルbiζを要素とするnζ行nζ列の行列を表す。BXAを満たす。例えば、基底ベクトルbiζが式によって表現される場合、行列Bは、以下のようになる。v→:v→は有限体Fqの元を要素とするn次元ベクトルを表す。v→vn∈Fqn...vμ:vμはn次元ベクトルv→のμ番目の要素を表す。w→:w→は有限体Fqの元を要素とするn次元ベクトルを表す。w→wn∈Fqn...wμ:wμはn次元ベクトルw→のμ番目の要素を表す。Enc:Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。EncK:EncKは、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。Dec:Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。DecK:DecKは、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。<関数暗号方式>次に、関数暗号方式の基本的な構成について説明する。関数暗号方式とは、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となる場合に暗号文が復号される方式である。第1情報と第2情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、PredicateEncryptionSupportingDisjunctionsPolynomialEquationsandInnerProductswithAmitSahaiandBrentWatersOneof4papersfromEurocrypt2008invitedtotheJournalofCryptology参考文献9に開示された述語暗号方式は関数暗号方式の一種である。これ以外にも様々な公知の関数暗号方式が存在するが、以下では未公開の新たな関数暗号方式を説明する。以下に説明する新たな関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第1情報と第2情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧,∨,¬の何れか又はすべてを含む。各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が真となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。<論理式と階層的な秘密分散との関係>上述した所定の論理式と階層的な秘密分散との関係を説明する。前述したように、しきい値秘密分散方式では、すべてのシェア情報shareshareが与えられれば秘密情報SEを復元できるが、任意のN1個のシェア情報shareshareが与えられても秘密情報SEの情報はまったく得られない。しきい値秘密分散方式では、任意の相違なるKt個のシェア情報shareshareが与えられれば秘密情報SEを復元できるが、任意のKt1個のシェア情報shareshareが与えられても秘密情報SEの情報はまったく得られない。これらの秘密分散方式は体上でも実行可能である。これらを拡張して秘密情報SEに応じた値をシェア情報shareに応じた値に秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報shareshareに応じた巡回群GTの元gTsharegTshare∈GTに秘密分散することもできる。上述した秘密情報SEはシェア情報shareの線形結合となる。秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ドモルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧,∨の少なくとも一部とリテラルとからなる論理式これらを標準形論理式と呼ぶことにするによって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは1個以上の子ノードの親ノードとされ、親ノードの1つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散して得られるシェア情報に応じた値が対応する。各ノードでの秘密分散形態秘密分散方式やしきい値は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値その親ノードがルートノードであれば秘密情報に応じた値は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成各ノードでの秘密分散の形態を含むとに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。以下に具体例を示す。図15は、命題変数PROPROと命題変数PROの否定¬PROと論理記号∧,∨とを含む標準形論理式PRO∧PRO∨¬PROを表現する木構造データを例示する図である。図15に例示する木構造データは複数のノードN1N5を含む。ノードN1はノードN2N5の親ノードとされ、ノードN2はノードN3N4の親ノードとされ、親ノードの1つノードN1がルートノードとされ、子ノードの一部であるノードN3N4N5が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2N5には、秘密情報SEに応じた値がしきい値秘密分散方式で秘密分散された各シェア情報SESEに応じた値がそれぞれ対応する。ノードN2の子ノードN3N4には、シェア情報SEに応じた値がしきい値秘密分散方式で秘密分散された各シェア情報SESH1SH1に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報shareSESH1に応じた値が対応し、葉ノードN4にはシェア情報shareSH1に応じた値が対応し、葉ノードN5にはシェア情報shareSEに応じた値が対応する。また、葉ノードN3N4N5には標準形論理式PRO∧PRO∨¬PROを構成する各リテラルPROPRO¬PROがそれぞれ対応し、当該各リテラルPROPRO¬PROの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式PRO∧PRO∨¬PROの真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。図16は、命題変数PROPROPROPROPROと命題変数PROPROの否定¬PRO¬PROと論理記号∧,∨とを含む標準形論理式∧PRO∨∧PRO∨∧PRO∨¬PRO∨∨PRO∧PROを表現する木構造データを例示する図である。図16に例示する木構造データは複数のノードN1N11を含む。ノードN1はノードN2N6N7の親ノードとされ、ノードN2はノードN3N4N5の親ノードとされ、ノードN7はノードN8N11の親ノードとされ、ノードN8はノードN9N10の親ノードとされ、親ノードの1つであるノードN1がルートノードとされ、ノードN3N4N5N6N9N10N11が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2N6N7には、秘密情報SEに応じた値がしきい値秘密分散方式で秘密分散された各シェア情報SESESEに応じた値がそれぞれ対応する。ノードN2の子ノードN3N4N5には、シェア情報SEに応じた値がしきい値秘密分散方式で秘密分散された各シェア情報に応じた値がそれぞれ対応する。ノードN7の子ノードN8N11には、シェア情報SEに応じた値がしきい値秘密分散方式で秘密分散された各シェア情報SH4SESH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9N10には、シェア情報SH4に応じた値がしきい値秘密分散方式で秘密分散された各シェア情報SH4SH4に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報shareに応じた値が対応し、葉ノードN4にはシェア情報shareに応じた値が対応し、葉ノードN5にはシェア情報shareに応じた値が対応し、葉ノードN6にはシェア情報shareSEに応じた値が対応し、葉ノードN9にはシェア情報shareSH4に応じた値が対応し、葉ノードN10にはシェア情報shareSH4に応じた値が対応し、葉ノードN11にはシェア情報shareSESH4に応じた値が対応する。また、葉ノードであるノードN3N4N5N6N9N10N11には標準形論理式∧PRO∨∧PRO∨∧PRO∨¬PRO∨∨PRO∧PROを構成する各リテラルPROPROPROPROPROPRO¬PRO¬PROPROPROがそれぞれ対応し、各リテラルPROPROPROPROPROPRO¬PRO¬PROPROPROの真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式∧PRO∨∧PRO∨∧PRO∨¬PRO∨∨PRO∧PROの真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。<アクセス構造>上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第1情報と第2情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となるか偽となるかを判定できる。以下、第1情報と第2情報との組み合わせによって定まる論理式の真理値が真となる場合に第1情報と第2情報との組み合わせを受け入れ、偽となる場合に第1情報と第2情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ1Ψとする。各葉ノードに対応するn次元ベクトルv→の集合v→λ1Ψを第1情報とし、n次元ベクトルw→の集合w→λ1Ψを第2情報とする。上述した木構造データをラベル付き行列LMTとして実装する。ラベル付き行列LMTは、以下のΨ行COL列COL≧1の行列MTと、行列MTの各行λ1Ψに対応付けられたラベルLABとを含む。行列MTの各要素mtλcolcol1COLは次の2つの要件を満たす。第1に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトルGV→と秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトルCV→との間に以下の関係が成立する。GV→∈FqCOL...CV→∈FqCOL...SEGV→T...以下にCOL次元ベクトルGV→の具体例を示す。GV→∈FqCOL...ただし、GV→∈FqCOLなどのその他のCOL次元ベクトルがGV→であってもよい。第2に、識別子λに対応する葉ノードにシェア情報share∈Fqに応じた値が対応する場合、以下の関係が成立する。shareTMTT...上述のように所定の論理式を表現した木構造データが定まれば、これら2つの要件を満たす行列MTを選択することは容易である。また、秘密情報SEやシェア情報shareが変数であったとしても、これら2つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報shareの値が定められてもよい。また、行列MTの各行λ1Ψに対応付けられたラベルLABは、識別子λに対応する葉ノードに対応するリテラルPRO又は¬PROに対応する。ここで、命題変数PROの真理値が真であることと第1情報VSET1λv→λ1Ψが含むv→と第2情報VSET2λw→λ1Ψが含むw→との内積v→w→が0となることとが等価であると扱い、命題変数PROの真理値が偽であることと内積v→w→が0とならないこととが等価であると扱う。PROに対応するラベルLABがv→を表し、¬PROに対応するラベルLABが¬v→を表すものとする。¬v→はv→の否定を表す論理式であり、¬v→からv→の特定が可能である。また、LABがv→を表すことをLABv→と表記し、LABが¬v→を表すことをLAB¬v→と表記する。LABλ1Ψの集合LABλ1ΨをLABと表記する。Ψ次元ベクトルTFV→が以下のように定義される。TFV→tfv...要素tfvは、内積v→w→が0のときにtfv1となり、0以外のときにtfv0となる。tfv1PROが真ifv→w→0...tfv0PROが偽ifv→w→≠0...さらに、以下の論理式の真理値が真になるときLIT1と表記し偽になるときLIT0と表記する。v→∧1∨¬v→∧0...すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が真になるときLIT1と表記し偽になるときLIT0と表記する。すると、行列MTが含む行ベクトルのうちLIT1となる行ベクトルmtλ→のみからなる部分行列MTTFVは以下のように表記できる。MTTFVLIT1...上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報shareに応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属するか否かを判定することで、識別子λに対応するシェア情報shareに応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。行ベクトルmtλ→で張られるベクトル空間とは、行ベクトルmtλ→の線形結合で表すことができるベクトル空間を意味する。ここで、上述の部分行列MTTFVの各行ベクトルmtλ→で張られるベクトル空間spanにCOL次元ベクトルGV→が属する場合に第1情報と第2情報との組み合わせが受け入れられ、そうでない場合に第1情報と第2情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMTが第1情報に対応する場合、アクセス構造が第1情報と第2情報との組み合わせを受け入れることをアクセス構造が第2情報を受け入れるといい、アクセス構造が第1情報と第2情報との組み合わせを受け入れないことをアクセス構造が第2情報を拒絶するという。受け入れifGV→∈span拒絶if¬GV→∈spanの場合、以下を満たす係数constが存在し、このような係数constは行列MTのサイズのオーダーの多項式時間で求めることができる。SEΣμ∈SETconstshare...const∈Fqμ∈SETSET⊆1λLIT1<アクセス構造を用いた関数暗号方式の基本方式>以下では、アクセス構造を用いた関数暗号方式によって鍵カプセル化メカニズムKEMを構成する場合の基本方式を例示する。この基本方式はSetupn,GenKey,Enc→λ1Ψ1F,Decを含む。また、第2情報VSET2λw→λ1Ψの1番目の要素w1が1Fとされる。[Setupn:セットアップ]-入力:1sec,n-出力:マスター鍵情報MSK,公開パラメータPKSetupでは各ψ0Ψについて以下の処理が実行される。1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1G2GT、双線形写像eψが生成されるparam。τ∈Fqが選択され、Xτ1Tを満たす行列X,Xが選択される。基底ベクトルaiζが式に従って座標変換され、nζ次元の基底ベクトルbiζが生成される。基底ベクトルbiζを要素とするnζ行nζ列の行列Bが生成される。基底ベクトルaiζが式に従って座標変換され、nζ次元の基底ベクトルbiζが生成される。基底ベクトルbiζを要素とするnζ行nζ列の行列Bが生成される。B^の集合B^ψ0Ψをマスター鍵情報MSKB^ψ0Ψとする。B^の集合B^ψ0Ψと1secとparamとを公開パラメータPKとする。ただし、B^は行列B又はその部分行列であり、B^は行列B又はその部分行列である。集合B^ψ0Ψは、少なくとも、b1b1...bnλ1Ψを含む。集合B^ψ0Ψは、少なくとも、b1b1...bnλ1Ψを含む。以下に一例を示す。nζ≧5ζ3nB^b3b5TB^...bnb3n1...b4nTλ1ΨB^b3b4TB^...bnb2n1...b3nTλ1Ψ[GenKey:鍵情報生成]-入力:公開パラメータPK,マスター鍵情報MSK,第1情報VSET1λv→λ1Ψに対応するラベル付き行列LMT-出力:鍵情報SKS式を満たす秘密情報SEに対して以下の処理が実行される。DSEb1Σι2Icoefιbι...ただし、Iは2以上nζ以下の定数である。coefι∈Fqは定数又は乱数である。乱数とは真性乱数や擬似乱数を意味する。以下にDの一例を示す。なお、式のcoef4は乱数である。DSEb1b3coef4b4...式を満たすshareに対して以下の処理が実行される。LABv→となるλに対して、以下のDが生成される。Dcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι...LAB¬v→となるλに対して、以下のDが生成される。DshareΣι1nvιbιΣιn1nζcoefιbι...ただしcoefcoefι∈Fqは定数又は乱数である。以下に一例を示す。LABv→となるλに対して、例えば以下のDが生成される。Dcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbι...LAB¬v→となるλに対して、例えば以下のDが生成される。DshareΣι1nvιbιΣι2n13ncoefιbι...なお、式のcoef及びcoefιは乱数である。以下の鍵情報が生成される。SKSDDD...[Enc:暗号化]-入力:公開パラメータPK,平文M,第2情報VSET2λw→λ1Ψ1F-出力:暗号文C以下の処理によって共通鍵Kの暗号文Cが生成される。Cυb1Σι2Iυιbι...CυΣι1nwιbιΣιn1nζυιbι...ただし、υυι∈Fqは定数又は乱数であり、以下の関係が満たされる。coefIυIυ...coefιυι0F1nζ...υの例はυ2υIの何れか1個である。例えば、υυ3υ5υ3n1υ4nが乱数であり、ζ3n、I5であり、以下の関係が満たされる。υI0Fυ5υυ31υ3n共通鍵KgTττυ∈GT...が生成される。例えば、ττ1Fの場合、以下の関係が満たされる。KgTυ∈GT...共通鍵Kを用いて平文Mの暗号文Cが生成される。CEncK...共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリアCamellia登録商標やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncKを生成してもよい。ただし、式の例ではM∈GTとされる。CgTυM...以下の暗号文が生成される。CC→∈VSET2C...ただし、下付き添え字のw→はw→を表す。[Dec:復号]-入力:公開パラメータPK,鍵情報SKS,暗号文C-出力:平文Mλ1Ψについて、鍵情報SKSが含むラベル付き行列LMTの各ラベルLABであるn次元ベクトルv→と暗号文CのVSET2が含むn次元ベクトルw→との内積v→w→が0となるか否かが判定され、これとLMTの各ラベルLABとによってGV→∈spanであるか否かが判定される式。GV→∈spanでなければ暗号文Cが拒絶され、GV→∈spanであれば暗号文Cが受け入れられる。暗号文Cが受け入れられると、SET⊆1λLIT1と式を満たす係数constとが計算される。以下の共通鍵が生成される。式より、以下の関係が満たされる。式及びw11Fより、以下の関係が満たされる。式より、以下の関係が満たされる。式から以下の関係が満たされる。例えば、ττ1Fの場合、以下の関係が満たされる。KgTυ∈GT...共通鍵Kを用い、以下のように平文Mが生成される。MDecKDecK...例えば、式に例示した共通鍵暗号方式の場合、以下のように平文Mが生成される。MCK...gTをGTの生成元とする代わりにgTτやgTτやgTττをGTの生成元と扱ってもよい。鍵情報SKSのλと暗号文のλとを対応関係を特定する写像を用いてCとDとの組み合わせを特定し、[Dec:復号]の処理が実行されてもよい。第2情報VSET2λw→λ1Ψの1番目の要素w1が1Fとされるだけではなく、第1情報VSET1λv→λ1Ψのn番目の要素vnが1Fとされてもよい。要素w1が1Fでない場合にはw→の代わりにw→w1を用いてもよく、要素vnが1Fでない場合にはv→の代わりにv→vnを用いてもよい。第1情報VSET1λv→λ1Ψの代わりに第2情報VSET2λw→λ1Ψが用いられ、第2情報VSET2λw→λ1Ψの代わりに第1情報VSET1λv→λ1Ψが用いられてもよい。この場合には第1情報VSET1λv→λ1Ψの1番目の要素v1が1Fとされる。<全体構成>図17は、第2実施形態の秘密分散システムの全体構成を説明するためのブロック図である。図17に例示するように、本形態の秘密分散システム6は、分散装置610と、Σα1Lh個の分散管理装置PA1HH≧2620-α-hαと、取得装置630と、共有値生成装置640-1~L,650とを有し、それらはネットワーク150を通じて通信可能である。説明を簡略化するため、本形態では、分散装置610及び取得装置630が1つずつ存在する構成を例示するが、分散装置610及び/又は取得装置630が2以上存在してもよい。同様な理由により、本形態では、Σα1Lh個の分散管理装置PA620-α-hαからなる集合が1つのみ存在する構成を例示するが、このような集合が複数存在していてもよい。図17に例示するように、Σα1Lh個の分散管理装置PA620-α-hαからなる集合は、H個の分散管理装置PAPAからなる複数の部分集合SUBごとに区分される。各部分集合SUBには共有値生成装置640-αがそれぞれ対応する。図18は、第2実施形態の分散装置610の構成を説明するためのブロック図である。また、図19A及び19Bは、共有値生成装置640-1~L,650の構成を説明するためのブロック図である。図20は、第2実施形態の分散管理装置PA620-α-hαの構成を説明するためのブロック図である。図21は、第2実施形態の取得装置630の構成を説明するためのブロック図である。なお、これらの図において第1実施形態と共通する部分については、第1実施形態と同じ符号を付して説明を簡略化する。<分散装置610>図18に例示するように、本形態の分散装置610は、一時記憶部111と、記憶部112と、制御部113と、秘密分散部614-αα1Lと、送信部115とを有する。なお、本形態の分散装置610は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。<共有値生成装置640-α,650>図19Aに例示するように、本形態の共有値生成装置640-αは、係数設定部641-αと送信部642-αとを有する。図19Bに例示するように、本形態の共有値生成部650は記憶部651と逆関数演算部652,653と送信部654とを有する。<分散管理装置PA620-α-hα>図20に例示するように、本形態の分散管理装置PA620-α-hαは、一時記憶部121-α-hαと、記憶部122-α-hαと、制御部123-α-hαと、分散秘密値生成部621-α-hα,622-α-hα,623-α-hαと、選択部624-α-hαと、送信部125-α-hαと、受信部126-α-hαとを有する。なお、本形態の分散管理装置PA620-α-hαは、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。<取得装置630>図21に例示するように、本形態の取得装置630は、一時記憶部131と、記憶部132と、制御部133と、復元部634-α,636-αα1Lと、合成部635,637と、受信部136とを有する。なお、本形態の取得装置630は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。<秘密分散処理>次に、本形態の秘密分散処理を説明する。本形態では、第1実施形態を応用し、アクセス構造を用いた関数暗号方式のマスター鍵情報である基底ベクトルbi式を秘密分散し、それらのシェア情報に対する演算結果から鍵情報Dを復元する。以下では式のように一般化された鍵情報Dを復元する例を示す。しかし、同様な処理が式のように具体化された鍵情報Dの場合にも適用可能なことはいうまでもない。式に示した基底ベクトルbiを構成する式に示す各要素を、式のように表現する。χiβκ2g2∈G2ζβ1nζ...θg2∈G2...ただし、以下が満たされる。θχiβκ2∈Fq...すなわち、式の基底ベクトルbiを以下のように表現する。big2θζg2∈G2nζ...この式より、第1実施形態を多次元に拡張することで基底ベクトルbiを秘密分散できることが分かる。秘密情報はシェア情報の線形な演算によって復元されるため、多次元の秘密分散によって得られた各次元のシェア情報に対して線形な演算を施した結果をシェア情報とみなして復元処理を行うことも可能である。そのため、第1実施形態を多次元に拡張することで鍵情報Dの復元処理が実行できることも分かる。以下では、第1実施形態との相違点を中心に説明し、それらと共通する事項については説明を省略する。事前処理本形態の秘密分散処理の事前処理として、各基底ベクトルbiの要素である秘密情報θg2∈G2ζβ1nζを特定するための情報θ∈Fqが分散装置610の記憶部112に格納される。共有値生成装置650の記憶部651に式を満たす秘密情報SEとシェア情報shareとが格納される。式のn次元ベクトルv→の集合v→λ1Ψである第1情報に対応するラベル付き行列LMTが、各分散管理装置620-α-hαの記憶部122-α-hαに、それぞれ格納される。なお、ラベル付き行列LMTは、すべての分散管理装置PA620-α-hαに共通である。秘密分散処理の全体図22及び図23は、第2実施形態の秘密分散処理の全体を説明するための図である。以下、図22及び図23用いて、本形態の秘密分散処理の全体を説明する。本形態では、まず、分散装置610図17が、基底ベクトルbiの各要素θg2に応じた値を、それぞれH個の分散管理装置PAPAからなる部分集合SUBごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θg2に応じた値のシェア情報SH1Hを生成する。本形態での基底ベクトルbiの各要素θg2に応じた値はθであり、秘密分散する対象が複数であること以外、秘密分散の具体的な方法は第1実施形態の変形例1,2,4の何れかと同じである。本形態のすべてのθは第1実施形態の変形例1,2,4の何れかと同じ方法で秘密分散される。つまり、本形態では、第1実施形態の変形例1,2,4の何れかの秘密分散方法のθをθに置換した秘密分散方法が実行される。例えば、以下のようなシェア情報SH1Hが生成される。SHf∈Fqただし、fθを満たし、ω∈Fqは予め定められた有限体Fqの元である。各シェア情報SHは、それぞれ、ネットワーク150経由で各分散管理装置PA620-α-hαに分散して送信されるステップS61及びS61’。各シェア情報SHが送信された各分散管理装置PA620-α-hαは、それぞれ、部分集合SUBごとに共有される共通情報と、シェア情報SH1Hとに対し、部分集合SUBごとに共通の共通演算を行って分散秘密値DSHを生成する。互いに異なる部分集合SUBでそれぞれ共有される共通情報は互いに独立である。共通演算は線形性を持った演算である。本形態の共通情報は、例えば、秘密情報SEから得られたSEFNC21→SESESE、シェア情報shareから得られたshareFNC2’1→shareshareshare、及び定数又は乱数であるcoefιcoefcoefι∈Fqを含む。FNC21は線形演算関数FNC2の逆関数を表す。FNC2’1は線形演算関数FNC2’の逆関数を表す。線形演算関数FNC2は入力されたL個の値の線形演算結果を出力する関数であり、線形演算関数FNC2の例はL個の値の線形結合値を出力する関数である。どのιに対するcoefιやcoefιが共通情報とされるのか、及び、coefιcoefcoefιSEshareが定数なのか乱数なのかは、生成される鍵情報Dの構造に依存する。本形態の各分散管理装置PA620-α-hαは、例えば、以下のようにψ0に対応する分散秘密値DSH1HH≧2を生成するFNC1。SHbiSH...DSHSESHb1g2Σι2IcoefιSHbιg2...さらに、本形態の各分散管理装置PA620-α-hαは、例えば、以下の式のように各λに対応する分散秘密値DSH1HH≧2を生成するFNC1’。SHbiSHζαh...DSHcoefv1SHb1g2Σι2ncoefvιSHbιg2Σιn1nζcoefιSHbιg2...DSHshareΣι1nvιSHb1g2Σιn1nζcoefιSHbιg2...各分散管理装置PA620-α-hαから出力された各分散秘密値DSHは、それぞれ、ネットワーク150経由で取得装置630に送信されるステップS62及びS62’。取得装置630は、同一の部分集合SUBに対応する複数の分散秘密値DSHを用い、前述したステップS61及びS61’の秘密分散方式に従った部分集合SUBごとの復元処理によって、当該部分集合SUBごとの秘密復元値SUBSKを生成する。本形態の取得装置630は、例えば、以下のSUBSKをψ0に対応する秘密復元値とする。SUBSKSEb1Σι2Icoefιbι...本形態の取得装置630は、例えば、以下の式又はを各λ1Ψに対応する秘密復元値SUBSKとする。SUBSKcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbι...SUBSKshareΣι1nvιb1Σιn1nζcoefιbι...これらの処理は、分散秘密値DSHの各次元次数に対して第1実施形態で示した復元処置を実行することで実現できる。すなわち、各分散秘密値DSHはベクトルであるが、それらの各次元次数に対して第1実施形態で示した復元処理ステップS134をそれぞれ実行することで上述の復元処理が実現できる。例えば、この復元処理に利用されるベクトルである分散秘密値DSHのι次元目の要素を以下のように表現する。dsh1dshRこの場合に式の演算が行われて各係数λρが得られ、以下の計算が行われることでψに対応する秘密復元値SUBSKのι次元目が得られる。λ1dsh1λRdshRよって、各ψ及びιに対してそれぞれ同様な処理を行うことで秘密復元値SUBSKが得られるステップS63及びS63’。取得装置630は、各部分集合SUBについてそれぞれ生成された秘密復元値SUBSKを用いて生成情報Dを生成し、当該生成情報Dを出力するDFNC2。例えば、取得装置630は、秘密復元値SUBSKを線形結合して生成情報Dを生成する。例えば、以下の式1102を満たすように秘密分散されていたのであれば、取得装置630は、以下の式に従ってDを生成するステップS64及びS64’。FNC2SUBSKSUBSKSUBSK...FNC2’SUBSKSUBSKSUBSK...DSUBSKSUBSKSUBSK...分散装置の処理テップS61及びS61’図24は、第2実施形態の分散装置の処理を例示するための図である。以下、この図を用いて、分散装置610の処理の詳細を説明する。まず、分散装置610図18の制御部113がψ0に設定し、その設定内容を一時記憶部111に格納するステップS6101。制御部113がα1,β1に設定し、その設定内容を一時記憶部111に格納するステップS6102。次に、分散装置610の制御部113が、i1に設定し、その設定内容を一時記憶部111に格納するステップS6103。次に、記憶部112から秘密情報θg2∈G2ζβ1nζを特定するための情報θ∈Fqがそれぞれ読み出され、秘密分散部614-αα1Lに入力される。秘密分散部614-αは、各情報θ∈Fqを秘密分散し、以下のように、情報θごとに部分集合SUBに対するH個のシェア情報を生成して出力するステップS6104。SHSH...例えば、情報θごとに第1実施形態のステップS112の処理を実行することでステップS6104の処理が実行される。次に、制御部113は、一時記憶部111に格納されたβがnζであるか否かを判定するステップS6105。ここで、βnζでないと判定された場合、制御部113は、β1を新たなβとし、その設定内容を一時記憶部111に格納するステップS6105。ステップS6105の後、ステップS6104に戻る。一方、ステップS6105でβnζであると判定された場合、制御部113は、β1に設定し、その設定内容を一時記憶部111に格納するステップS6107。次に、制御部113は、一時記憶部111に格納されたiがnζであるか否かを判定するステップS6108。ここで、inζでないと判定された場合、制御部113は、i1を新たなiとし、その設定内容を一時記憶部111に格納するステップS6109。ステップS6109の後、ステップS6104に戻る。一方、ステップS6108でinζであると判定された場合、制御部113は、一時記憶部111に格納されたαがLであるか否かを判定するステップS6110。ここで、αLでないと判定された場合、制御部113は、α1を新たなαとし、その設定内容を一時記憶部111に格納するステップS6111。ステップS6111の後、ステップS6103に戻る。一方、ステップS6110でαLであると判定された場合、制御部113は、一時記憶部111に格納されたψがΨであるか否かを判定するステップS6112。ここで、ψΨでないと判定された場合、制御部113は、ψ1を新たなψとし、その設定内容を一時記憶部111に格納するステップS6113。ステップS6113の後、ステップS6102に戻る。一方、ステップS6112でψΨであると判定された場合、各秘密分散部614-αから出力された各SHSHが送信部115に送られる。送信部115は、ネットワーク150経由で、以下のシェア情報をそれぞれ分散管理装置PA620-α-hに送信するステップS6114。SHζβ1nζ...すなわち、各シェア情報SHは分散管理装置PA620-1-1に、各シェア情報SHは分散管理装置PA620-1-2に、、シェア情報SHは分散管理装置PA620-L-HLに、それぞれ送信される。[共有値生成装置の処理]各共有値生成装置640-α図19Aは、自らに対応する部分集合SUBを構成する各分散管理装置PA620-α-hh1Hで共有する共通情報coefιcoefcoefιを生成する。本形態では、共通情報生成部641-αから出力された乱数又は定数を共通情報coefιcoefcoefιとし、送信部642-αが共通情報coefιcoefcoefιを、部分集合SUBを構成する各分散管理装置PA620-α-hh1Hに送信する。共有値生成装置650図19Bは、秘密情報SEからSEを生成し、シェア情報shareからshareを生成する。本形態では、共通情報生成部652が記憶部651に格納された秘密情報SEを用い、以下を満たすSESESEを生成する。FNC21→SESESE...例えば、共通情報生成部652は、以下を満たすSESESEを生成する。SESESESE...本形態では、共通情報生成部653が記憶部651に格納されたシェア情報shareを用い、以下のようにshareshareshareを生成する。FNC2’1→shareshareshare...例えば、共通情報生成部653は、以下の関係を満たすshareshareshareを生成する。shareshareshareshare...SE及びshareα1Lλ1Ψは送信部654に送られ、送信部654はSE及びshareを、部分集合SUBを構成する各分散管理装置PA620-α-hに送信する。[分散管理装置の処理ステップS62]図25は、第2実施形態の分散管理装置PA620-α-hα1Lの処理を例示するための図である。以下、この図を用いて、本形態の分散管理装置PA620-α-hの処理を説明する。まず、分散管理装置PA620-α-h図20の受信部126-α-hが、送信されたシェア情報SHを受信し、それらを記憶部122-α-hに格納するステップS6201。なお、過去にステップステップS6201の処理が実行され、既にシェア情報SHが分散管理装置PA620-α-hの記憶部122-α-hに格納されているのであれば、ステップS6201の処理を省略してもよい。分散管理装置PA620-α-hの受信部126-α-hは、共有値生成装置640-α及び650から送信された共通情報coefιcoefcoefι,SE及びshareを受信し、それらを記憶部122-α-hに格納するステップS6202。次に、分散秘密値生成部621-α-hが、記憶部122-α-hからシェア情報SHと共通情報coefιSEを読み込む。分散秘密値生成部621-α-hは、これらを用いて式を満たす分散秘密値DSHを生成して出力するステップS6203。次に制御部123-α-hからラベルLABを参照してLABv→であるか否かを判定するステップS6205。ここで、LABv→であれば、分散秘密値生成部622-α-hが記憶部122-α-hから、シェア情報SHと共通情報coefcoefιshareとラベルLABによって特定されるn次元ベクトルv→とを読み込む。分散秘密値生成部622-α-hはこれらを用いて式を満たす分散秘密値DSHを生成して出力するステップS6206。一方、LAB¬v→であれば、分散秘密値生成部623-α-hが記憶部122-α-hから、シェア情報SHと共通情報coefιshareとラベルLABによって特定されるn次元ベクトルv→とを読み込む。分散秘密値生成部623-α-hは、これらを用いて式を満たす分散秘密値DSHを生成して出力するステップS6207。λに対応する分散秘密値DSHが生成されると、制御部123-α-hは、一時記憶部121-α-hに格納されたλがΨであるか否かを判定ステップS6208し、λ=Ψでなければλ1を新たなλとしてステップS6209、ステップS6205の処理に移る。一方、λ=Ψあれば、生成された各分散秘密値DSHDSHλ1Ψは送信部125-α-hαに送られる。送信部125-α-hαは、各分散秘密値DSHDSHをネットワーク150経由で取得装置630に送信するステップS6210。[取得装置の処理ステップS63,S63’,S64,S64’]図26は、第2実施形態の取得装置の処理を例示するための図である。各分散管理装置PA630-α-hから送信された分散秘密値DSHDSHλ1Ψは、取得装置630図21の受信部136で受信され、記憶部132に格納されるステップS6301。次に、制御部133が、秘密値の復元に必要な数以下必要数という以上の分散秘密値DSHDSHが記憶部132に格納されたか否かを判定するステップS6302。ここで、必要数以上の分散秘密値DSHDSHが記憶部132に格納されていないと判定された場合には、ステップS6301の処理に戻る。一方、必要数以上の分散秘密値DSHDSHが記憶部132に格納されたと判定された場合、制御部133が、α1に設定し、その設定内容を一時記憶部131に格納するステップS6303。次に、記憶部132から部分集合SUBに対応する必要数分の分散秘密値DSHh1Hが読み出され、各復元部634-αα1Lに入力される。各復元部634-αは、入力された分散秘密値DSHh1Hを用い、部分集合SUBごとの復元処理によって式を満たす秘密復元値SUBSKを生成し、当該部分集合SUBごとの秘密復元値SUBSKを出力するステップS6304。次に制御部133がλ1に設定し、その設定内容を一時記憶部131に格納するステップS6305。次に、記憶部132から部分集合SUBに対応する必要数分の分散秘密値DSHh1Hが読み出され、各復元部636-αα1Lに入力される。各復元部636-αは、入力された分散秘密値DSHh1Hを用い、部分集合SUBごとの復元処理によって式又はを満たす秘密復元値SUBSKを生成し、当該部分集合SUBごとの秘密復元値SUBSKを出力するステップS6306。次に、制御部133は、一時記憶部131に格納されたλがΨであるか否かを判定するステップS6307。ここで、λΨでないと判定された場合、制御部133は、λ1を新たなλとし、その設定内容を一時記憶部131に格納するステップS6308。ステップS6308の後、ステップS6306に戻る。一方、λΨであると判定された場合、制御部133は、一時記憶部131に格納されたαがLであるか否かを判定するステップS6309。ここで、αLでないと判定された場合、制御部133は、α1を新たなαとし、その設定内容を一時記憶部131に格納するステップS6310。ステップS6310の後、ステップS6304に戻る。一方、ステップS6309でαLであると判定された場合、各復元部634-αα1Lから出力された各秘密復元値SUBSKα1Lが合成部635に送られる。合成部635は、各秘密復元値SUBSKα1Lを用い、以下の鍵情報Dを生成して出力する。DFNC2...例えば、ψ0とした式に従って鍵情報Dが生成されて出力されるステップS6311。さらに、各復元部634-αα1Lから出力された各秘密復元値SUBSKα1Lが合成部637に送られる。合成部637は、各秘密復元値SUBSKα1Lを用い、以下の鍵情報DFNC2...例えば、ψλに従って、鍵情報Dの各要素θg2に応じた値はθg2であり、各分散管理装置PA620-α-hαは、例えば、以下のDSHをψ0に対応する分散秘密値として生成するFNC1。DSHSESHb1g2Σι2IcoefιSHbι...さらに、本形態の各分散管理装置PA620-α-hαは、例えば、以下の式又はに従って、以下のDSHを各λに対応する分散秘密値として生成するFNC1’。DSHcoefv1SHb1Σι2ncoefvιSHbιΣιn1nζcoefιSHbι...DSHshareΣι1nvιSHb1Σιn1nζcoefιSHbι...その他は第2実施形態と同様である。第2実施形態の変形例1の秘密分散システム7は、分散装置610が分散装置710に置換され、分散管理装置620-α-hαα1Lが分散管理装置720-α-hαα1Lに置換される。その他の構成は、第6実施形態と同様である。第2実施形態の変形例1では、ステップS6104の代わりに、記憶部112から情報θg2∈G2ζβ1nζがそれぞれ読み出され、秘密分散部714-αα1L図27に入力される。秘密分散部714-αは、各情報θg2∈G2を秘密分散し、情報θg2∈G2ごとに、部分集合SUBに対する以下のH個のシェア情報を生成して出力する。SHSH...各情報θg2∈G2の秘密分散方法は第1実施形態と同様である。すなわち、本形態では、第1実施形態の秘密分散方法のθgをθg2に置換した秘密分散方法が実行される。例えば、以下のようなシェア情報SH1Hが生成される。SHfg2∈G2ただし、fθを満たし、ω∈Fqは予め定められた有限体Fqの元であるステップS7104。第2実施形態の変形例1では、第2実施形態のステップS6203の代わりに、分散秘密値生成部721-α-hが、記憶部122-α-hからシェア情報SHと共通情報coefιSEを読み込む。分散秘密値生成部721-α-hは、これらを用いて式を満たす分散秘密値DSHを生成して出力するステップS7203。第2実施形態の変形例1では、第2実施形態のステップS6206の代わりに、分散秘密値生成部722-α-hが記憶部122-α-hから、シェア情報SHと共通情報coefcoefιshareとラベルLABによって特定されるn次元ベクトルv→とを読み込む。分散秘密値生成部622-α-hは、これらを用いて式を満たす分散秘密値DSHを生成して出力するステップS7206。さらに、第2実施形態のステップS6207の代わりに、分散秘密値生成部723-α-hが記憶部122-α-hから、シェア情報SHと共通情報coefιshareとラベルLABによって特定されるn次元ベクトルv→とを読み込む。分散秘密値生成部623-α-hは、これらを用いて式を満たす分散秘密値DSHを生成して出力するステップS7207。<第2実施形態の変形例2>その他、第2実施形態やその変形例1において、秘密分散方法や復元方法を例えば第1実施形態やその変形例3のように変形してもよい。その他の変形例等本発明は上述の各実施の形態に限定されるものではない。例えば、上述の有限体Fq上で定義された各演算を位数qの有限環Zq上で定義された演算に置換してもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置換する方法の一例は、素数やそのべき乗値以外のqを許容する方法である。また、第2実施形態では生成情報として関数暗号の鍵情報を生成する処理を例示したが、それ以外の生成情報が生成されてもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。上述の各実施形態では、コンピュータ上で所定のプログラムが実行され、各装置の処理内容が実現されたが、これらの処理内容の少なくとも一部がハードウェアのみによって実現されてもよい。"