"暗号化装置であって、乱数rを生成する乱数生成部と、前記乱数rに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2を生成する第1暗号化部と、前記乱数rと前記暗号文C2との組を衝突困難な関数HSのそれぞれに入力して得られる、SmaxSmax≧1個の関数値HSを生成する関数演算部と、巡回群GTの元である共通鍵Kを生成する共通鍵生成部と、前記共通鍵Kを用いて共通鍵暗号方式によって前記乱数rを暗号化して暗号文Cを生成する第2暗号化部と、Cυb1Σι2Iυιbι、CυΣι1nwιbιΣιn1nζυιbι、及び前記暗号文Cを含む暗号文C1を生成する第3暗号化部と、を有し、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、nが1以上の整数であり、ζが0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上nζ以下の定数であり、eψのそれぞれが巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力として前記巡回群GTの1個の元を出力する非退化な双線形写像であり、iが1以上nζ以下の整数であり、biが前記巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルであり、biが前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルであり、δがクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数ττに対してeψbjgTττδが満たされ、w→wnがw1wnを要素とするn次元ベクトルであり、υυιυι1nζの少なくとも一部の値が前記関数値HSの何れかに対応する、暗号化装置。請求項1の暗号化装置であって、前記乱数rに応じたバイナリ系列は、前記乱数rにランダム関数を作用させた関数値である、暗号化装置。請求項1の暗号化装置であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化装置。請求項2の暗号化装置であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化装置。請求項1から4の何れかの暗号化装置であって、前記定数ττ、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、暗号化装置。請求項1から4の何れかの暗号化装置であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかである、暗号化装置。請求項6の暗号化装置であって、前記定数ττ、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、暗号化装置。復号装置であって、SEΣμ∈SETconstshareμ∈SETを満たす係数constが存在する場合に、第1鍵情報D、第2鍵情報D、及び、入力された暗号文C、Cを用いて、共通鍵を生成する共通鍵生成部と、前記共通鍵Kを用い、入力された暗号文Cを復号して復号値rを生成する第1復号部と、前記復号値rと入力された暗号文C2との組を衝突困難な関数HSのそれぞれに入力して得られる、SmaxSmax≧1個の関数値HSを生成する関数演算部と、前記暗号文CCと、暗号文Cυb1Σι2IυιbιCυΣι1nwιbιΣιn1nζυιbιと、が一致しない場合に復号を拒絶する判定部と、を有し、υυιυι1nζの少なくとも一部の値が前記関数値HSの何れかに対応し、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、ζが0以上の整数であり、λが1以上Ψ以下の整数であり、nが1以上の整数であり、Iが2以上nζ以下の定数であり、eψのそれぞれが巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力として巡回群GTの1個の元を出力する非退化な双線形写像であり、iが1以上nζ以下の整数であり、biが前記巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルであり、biが前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルであり、δがクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数ττに対してeψbjgTττδが満たされ、v→vnがv1vnを要素とするn次元ベクトルであり、w→wnがw1wnを要素とするn次元ベクトルであり、ラベルLABλ1Ψが前記n次元ベクトルv→又は前記n次元ベクトルv→の否定¬v→を表す情報であり、LABv→は、LABが前記n次元ベクトルv→を表すことを意味し、LAB¬v→は、LABが前記n次元ベクトルv→の否定¬v→を表すことを意味し、shareが秘密情報SEを秘密分散して得らたシェア情報を表し、前記第1鍵情報がDSEb1Σι2Icoefιbιであり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣιn1nζcoefιbιであり、SETがLABv→∧v→w→0又はLAB¬v→∧v→w→≠0を満たすλの集合を表す、復号装置。請求項8の復号装置であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、復号装置。請求項9の復号装置であって、前記要素v1vn、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、復号装置。請求項8の復号装置であって、前記要素v1vn、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、復号装置。請求項8から11の何れかの復号装置であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかであり、前記第1鍵情報がDSEb1b3coef4b4であり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣι2n13ncoefιbιである、復号装置。請求項12の復号装置であって、前記復号値rに応じたバイナリ系列は、前記復号値rにランダム関数を作用させた関数値である、復号装置。請求項8から11の何れかの復号装置であって、前記暗号文C及びCと、暗号文Cυb1Σι2Iυιbι及びCυΣι1nwιbιΣιn1nζυιbιと、が一致する場合に、前記復号値rに応じたバイナリ系列と入力されたバイナリ系列の暗号文C2との排他的論理和である復号値Mを生成する第2復号部をさらに有する、復号装置。請求項14の復号装置であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかであり、前記第1鍵情報がDSEb1b3coef4b4であり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣι2n13ncoefιbιである、復号装置。請求項15の復号装置であって、前記復号値rに応じたバイナリ系列は、前記復号値rにランダム関数を作用させた関数値である、復号装置。暗号化方法であって、乱数生成部が、乱数rを生成するステップと、第1暗号化部が、前記乱数rに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2を生成するステップと、関数演算部が、前記乱数rと前記暗号文C2との組を衝突困難な関数HSのそれぞれに入力して得られる、SmaxSmax≧1個の関数値HSを生成するステップと、共通鍵生成部が、巡回群GTの元である共通鍵Kを生成するステップと、第2暗号化部が、前記共通鍵Kを用いて共通鍵暗号方式によって前記乱数rを暗号化して暗号文Cを生成するステップと、第3暗号化部が、Cυb1Σι2Iυιbι、CυΣι1nwιbιΣιn1nζυιbι、及び前記暗号文Cを含む暗号文C1を生成するステップと、を有し、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、nが1以上の整数であり、ζが0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上nζ以下の定数であり、eψのそれぞれが巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力として前記巡回群GTの1個の元を出力する非退化な双線形写像であり、iが1以上nζ以下の整数であり、biが前記巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルであり、biが前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルであり、δがクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数ττに対してeψbjgTττδが満たされ、w→wnがw1wnを要素とするn次元ベクトルであり、υυιυι1nζの少なくとも一部の値が前記関数値HSの何れかにに対応する、暗号化方法。請求項17の暗号化方法であって、前記乱数rに応じたバイナリ系列は、前記乱数rにランダム関数を作用させた関数値である、暗号化方法。請求項17の暗号化方法であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化方法。請求項18の暗号化方法であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化方法。請求項17から20の何れかの暗号化方法であって、前記定数ττ、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、暗号化方法。請求項17から20の何れかの暗号化方法であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかである、暗号化方法。請求項22の暗号化方法であって、前記定数ττ、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、暗号化方法。復号方法であって、SEΣμ∈SETconstshareμ∈SETを満たす係数constが存在する場合に、共通鍵生成部が、第1鍵情報D、第2鍵情報D、及び、入力された暗号文C、Cを用いて、共通鍵を生成するステップと、第1復号部が、前記共通鍵Kを用い、入力された暗号文Cを復号して復号値rを生成するステップと、関数演算部が、前記復号値rと入力された暗号文C2との組をSmaxSmax≧1個の衝突困難な関数HSのそれぞれに入力してSmaxSmax≧1個の関数値HSを生成するステップと、判定部が、前記暗号文CCと、暗号文Cυb1Σι2IυιbιCυΣι1nwιbιΣιn1nζυιbιと、が一致しない場合に復号を拒絶するステップと、を有し、υυιυι1nζの少なくとも一部の値が前記関数値HSの何れかに対応し、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、ζが0以上の整数であり、λが1以上Ψ以下の整数であり、nが1以上の整数であり、Iが2以上nζ以下の定数であり、eψのそれぞれが巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力として巡回群GTの1個の元を出力する非退化な双線形写像であり、iが1以上nζ以下の整数であり、biが前記巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルであり、biが前記巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルであり、δがクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数ττに対してeψbjgTττδが満たされ、v→vnがv1vnを要素とするn次元ベクトルであり、w→wnがw1wnを要素とするn次元ベクトルであり、ラベルLABλ1Ψが前記n次元ベクトルv→又は前記n次元ベクトルv→の否定¬v→を表す情報であり、LABv→は、LABが前記n次元ベクトルv→を表すことを意味し、LAB¬v→は、LABが前記n次元ベクトルv→の否定¬v→を表すことを意味し、shareが秘密情報SEを秘密分散して得らたシェア情報を表し、前記第1鍵情報がDSEb1Σι2Icoefιbιであり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣιn1nζcoefιbιであり、SETがLABv→∧v→w→0又はLAB¬v→∧v→w→≠0を満たすλの集合を表す、復号方法。請求項24の復号方法であって、前記衝突困難な関数HSの少なくとも一部はランダム関数である、復号方法。請求項25の復号方法であって、前記要素v1vn、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、復号方法。請求項24の復号方法であって、前記要素v1vn、前記要素w1wn、前記関数値HS、及びυυιυι1nζが有限体Fqの元であり、前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数qと等しい、復号方法。請求項24から27の何れかの復号方法であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかであり、前記第1鍵情報がDSEb1b3coef4b4であり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣι2n13ncoefιbιである、復号方法。請求項28の復号方法であって、前記復号値rに応じたバイナリ系列は、前記復号値rにランダム関数を作用させた関数値である、復号方法。請求項24から27の何れかの復号方法であって、前記暗号文C及びCと、暗号文Cυb1Σι2Iυιbι及びCυΣι1nwιbιΣιn1nζυιbιと、が一致する場合に、前記復号値rに応じたバイナリ系列と入力されたバイナリ系列の暗号文C2との排他的論理和である復号値Mを生成する第2復号部をさらに有する、復号方法。請求項30の復号方法であって、ζ3n、I5、Smax3Σλ1Ψnであり、υ2υ4υn1υ3nが零元であり、KgTττυ∈GT、υυ3であり、υυ3υ5υ3n1υ4nのそれぞれがH1HSmaxの何れかであり、前記第1鍵情報がDSEb1b3coef4b4であり、LABv→となるλに対する前記第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣι2n13ncoefιbιであり、LAB¬v→となるλに対する前記第2鍵情報がDshareΣι1nvιbιΣι2n13ncoefιbιである、復号方法。請求項31の復号方法であって、前記復号値rに応じたバイナリ系列は、前記復号値rにランダム関数を作用させた関数値である、復号方法。請求項1の暗号化装置としてコンピュータを機能させるためのプログラム。請求項1の暗号化装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。請求項8の復号装置としてコンピュータを機能させるためのプログラム。請求項8の復号装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。上述したCHK変換方式に基づいて生成された暗号文は、暗号化された平文と当該暗号化された平文のOneTime署名と当該OneTime署名を検証するための署名鍵とを含む。そのため、CHK変換方式に基づいて生成される暗号文の暗号文空間は、暗号化された平文のための空間だけではなく、OneTime署名や署名鍵のための空間を含む。上述したBK変換方式に基づいて生成された暗号文は、暗号化された平文とメッセージ認証子とビットコミットメント列とを含む。そのため、BK変換方式に基づいて生成される暗号文の暗号文空間は、暗号化された平文のための空間だけではなく、メッセージ認証子やビットコミットメント列のための空間を含む。すなわち、CHK変換方式やBK変換方式に基づいて生成される暗号文空間は、CCA安全性を向上させるためのみに割り当てられた2次元の空間を含む。しかしながら、暗号文空間のサイズが大きくなるほど演算量やデータ量が増加するため、暗号文空間のサイズはできるだけ小さいほうが望ましい。また、IDベース暗号方式では、暗号化を行う者が、暗号化を行う前に復号を行う者のIDを取得しておかなければならない。これに対し、暗号化を行う者が復号を行う者を特定することなく暗号文を生成でき、所望の条件に合致した者が当該暗号文を復号できる方式を構成できれば便利である。本発明はこのような点に鑑みてなされたものであり、利便性が高く、CCA安全性の向上のための付加的な暗号文空間なしにCCA安全性を向上できる暗号方式を提供する。本発明の暗号化では、乱数rが生成され、乱数rに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2が生成される。乱数rと暗号文C2との組が衝突困難な関数HSのそれぞれに入力されてSmaxSmax≧1個の関数値HSが生成される。巡回群GTの元である共通鍵Kが生成され、共通鍵Kを用いて共通鍵暗号方式によって乱数rを暗号化して暗号文Cが生成される。Cυb1Σι2Iυιbι、CυΣι1nwιbιΣιn1nζυιbι、及び暗号文Cを含む暗号文C1が生成される。ここで、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、nが1以上の整数であり、ζが0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上nζ以下の定数であり、eψのそれぞれが巡回群G1のnζ個の元γβζと巡回群G2のnζ個の元γβζとを入力として巡回群GTの1個の元を出力する非退化な双線形写像であり、iが1以上nζ以下の整数であり、biが巡回群G1のnζ個の元を要素とするnζ次元の基底ベクトルであり、biが巡回群G2のnζ個の元を要素とするnζ次元の基底ベクトルであり、δがクロネッカーのデルタ関数であり、巡回群GTの生成元gT及び定数ττに対してeψbjgTττδが満たされ、w→wnがw1wnを要素とするn次元ベクトルである。υυιυι1nζの少なくとも一部の値が関数値HSの何れかに対応する。本発明の復号では、SEΣμ∈SETconstshareμ∈SETを満たす係数constが存在する場合に、第1鍵情報D、第2鍵情報D、及び、入力された暗号文C、Cを用いて、以下のように共通鍵Kが生成される。共通鍵Kを用い、入力された暗号文Cが復号されて復号値rが生成される。復号値rと入力された暗号文C2との組が衝突困難な関数HSのそれぞれに入力されてSmaxSmax≧1個の関数値HSが生成される。暗号文CCと暗号文Cυb1Σι2IυιbιCυΣι1nwιbιΣιn1nζυιbιとそれぞれが一致しない場合に復号が拒絶される。ただし、v→vnがv1vnを要素とするn次元ベクトルであり、w→wnがw1wnを要素とするn次元ベクトルであり、ラベルLABλ1Ψがn次元ベクトルv→又はn次元ベクトルv→の否定¬v→を表す情報であり、LABv→はLABがn次元ベクトルv→を表すことを意味し、LAB¬v→はn次元ベクトルv→の否定¬v→を表すことを意味し、shareが秘密情報SEを秘密分散して得られたシェア情報を表し、第1鍵情報がDSEb1Σι2Icoefιbιであり、LABv→となるλに対する第2鍵情報がDcoefv1b1Σι2ncoefvιbιΣιn1nζcoefιbιであり、LAB¬v→となるλに対する第2鍵情報がDshareΣι1nvιbιΣιn1nζcoefιbιであり、SETがLABv→∧v→w→0又はLAB¬v→∧v→w→≠0を満たすλの集合を表す。υυιυι1nζの少なくとも一部の値が関数値HSの何れかに対応する。本発明では、暗号文CCと暗号文CCとがそれぞれ一致しない場合に復号を拒絶することとしたためCCA安全性が向上する。本発明では、CCA安全性を向上させるための付加的な暗号文空間が不要である。本発明は、暗号化を行う者が復号を行う者を特定することなく暗号文を生成でき、所望の条件に合致した者が当該暗号文を復号できる。このように本発明では、利便性が高く、CCA安全性の向上のための付加的な暗号文空間なしにCCA安全性を向上できる。本発明を実施するための形態を説明する。定義行列:行列とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも行列である。T:Tはの転置行列を表す。1:1はの逆行列を表す。∧:∧は論理積ANDを表す論理記号である。∨:∨は論理和ORを表す論理記号である。¬:¬は否定NOTを表す論理記号である。命題変数:命題変数は命題の真偽falsetrueを要素とする集合{真,偽}上の変数である。すなわち、命題変数の定義域は真偽を要素とする集合である。命題変数及び命題変数の否定を総称してリテラルliteralと呼ぶ。論理式:論理式とは数理論理学における命題を表す式を意味する。具体的には真及び偽は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。Z:Zは整数集合を表す。sec:secはセキュリティパラメータsec∈Zsec0を表す。0:0は個の0からなる列を表す。1:1は個の1からなる列を表す。01:01は任意ビット長のバイナリ系列を表す。01の一例は、整数0及び1からなる系列である。しかし、01は整数0及び1からなる系列に限定されない。01は位数2の有限体又はその拡大体と同義である。01ζ:01ζはビット長ζζ∈Zζ0のバイナリ系列を表す。01ζの一例は、ζ個の整数0及び1からなる系列である。しかし、01ζは整数0及び1からなる系列に限定されない。01ζは位数2の有限体ζ1の場合又はそれをζ次拡大した拡大体ζ1の場合と同義である。はバイナリ系列間の排他的論理和演算子を表す。例えば、101100111110000101010010を満たす。Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献1ISOIEC180332InformationtechnologySecuritytechniquesEncryptionalgorithmsPart2Asymmetricciphersに開示されている。0F:0Fは有限体Fqの加法単位元零元を表す。1F:1Fは有限体Fqの乗法単位元を表す。δ:δはクロネッカーのデルタ関数を表す。ijの場合にδ1Fを満たし、i≠jの場合にδ0Fを満たす。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を満たす点を意味する。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とは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を復号して得られた復号結果を表す。衝突困難な関数:衝突困難な関数とは、十分大きなセキュリティパラメータsecに対して以下の条件を満たす関数h、又は、関数hとみなせる関数を表す。PrAhh∧x≠yに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とされる。CCA安全性以下の14が実行された場合に式の関係が満たされるとき、以下の暗号オラクル及び復号オラクルに対応する暗号方式はCCA安全である。Prbitbitであるか否かが判定する。前述のように、GV→∈spanであれば共通鍵K∈GTが復元可能であり、GV→∈spanでなければ共通鍵K∈GTが復元可能でないステップS43。ステップS43の処理の具体例は後述する。共通鍵K∈GTが復元可能でないと判断された場合には復号が拒絶されステップS48、復号処理が終了する。一方、共通鍵K∈GTが復元可能であると判断された場合、共通鍵生成部126aは、式を満たす係数constを求め、式に従って共通鍵K∈GTを計算する。生成された共通鍵Kは記憶部123に格納されるステップS44。暗号文C1が含む暗号文C及び共通鍵Kは復号部126bに入力される。C1C1で或る場合、CCが満たされる。復号部126bは、共通鍵Kを用い、入力された暗号文Cを復号し、以下の復号値rを得る。rDecK...復号部126bは、復号値rを記憶部123に格納するステップS45。関数演算部126cに復号値rと暗号文C2とが入力される。関数演算部126cは、復号値rと暗号文C2との組をSmaxSmax≧1個の衝突困難な関数HSのそれぞれに入力して関数値HSを生成する。各関数値HSは記憶部123に格納されるステップS46。次に、判定部126dに、関数値HS∈Fqの少なくとも一部、及び、暗号文C1が含む第2情報VSET2並びに暗号文CC→∈VSET2が入力される。判定部126dは、第2情報VSET2が含むn次元ベクトルw→及び関数値HSの少なくとも一部を用いて、以下の暗号文CCλ1Ψを生成する。Cυb1Σι2Iυιbι...CυΣι1nwιbιΣιn1nζυιbι...暗号文C及びCλ1Ψの生成方法は、第2情報VSET2が第2情報VSET2に置換され、関数値HSが関数値HSに置換され、υυιυι1nζがυυιυι1nζに置換される以外は、ステップS27での暗号文C及びCλ1Ψの生成方法と同一である。すなわち、判定部126dは、上記の予め定められた基準に従い、関数値HS∈Fqの少なくとも一部に対応する値をυυιυι1nζの少なくとも一部の値とし、式に従ってC及びCλ1Ψを生成する。例えば、υυιυι1nζの少なくとも一部が、関数値HS∈Fqの少なくとも一部又は関数値HS∈Fqの少なくとも一部の関数値とされる。式のυιυιがυιυιに置換された関係が満たされる必要もある。例えば、Smax3Σλ1Ψnの場合、ζ3n、I5とし、υ2υ4υn1υ3nをそれぞれ零元0Fとし、υυ3υ5υ3n1υ4nのそれぞれをH1HSmaxの何れかとする。例えば、υυ3υ5υ3n1υ4nとH1HSmaxとは一対一で対応する。その場合、Smaxの値は、υυ3υ5υ3n1υ4nの個数以上である。関数値HS∈Fqのいずれにも対応しないυυιυι1nζは、例えば、有限体Fqから選択された定数ステップS27と同一の定数とされる。υυιυι1nζの何れがH1HSmaxの何れに対応するのかは、例えば、ステップS27と同一の基準に従って予め定められている。判定部126dは、以下のすべてが満たされるか否かを判定するステップS47。CC...CCλ1Ψ...ここで、式の少なくとも一部が満たさない場合には復号が拒絶されステップS48、復号処理が終了する。一方、式がすべて満たされる場合、復号部126eにバイナリ系列の暗号文C2及び復号値rが入力される。復号部126eは、復号値rに単射関数Rを作用させたバイナリ系列の関数値Rと暗号文C2との排他的論理和値を復号値Mとして生成するステップS49MC2R...。復号値Mは出力部122に送られ、出力部122は復号値Mを出力するステップS50。これで復号処理が終了する。[ステップS43の処理の具体例]以下にステップS43の処理の具体例を説明する。なお、以下では説明の簡略化のため、式のCOL次元ベクトルGV→が用いられる場合を例示する。ただし、これは本発明を限定するものではなく、式のように一般化されたCOL次元ベクトルGV→が用いられる場合に以下の処理が拡張され、適用されてもよい。図10に例示するように、まず共通鍵生成部126aは、ラベル付き行列LMTに対応する第1情報VSET1λv→λ1Ψ、暗号文C1が含む第2情報VSET2λw→λ1Ψ、及びLMTの各ラベルLABとを用い、式に示した部分行列MTTFVを生成する。ここではMTTFVが以下のように表現される。ただし、式のMTTFVはω行COL列の行列であり、ωは1以上の整数であり、ROWROWはそれぞれLIT1LIT1となる行列MT式の行番号ROWROW∈SETであるステップS431。次に、共通鍵生成部126aは、MTTFVの行ベクトルmtλ→λROWROWごとの演算やMTTFVの行ベクトルmtλ→間の演算を行って、対角成分を乗法単位元1FとしたΩ×Ωの上三角行列を1行1列からΩ行Ω列までの部分行列とし、Ω1行以降の行ベクトルmtλ→が存在する場合にはΩ1行以降の行ベクトルmtλ→の全要素を加法単位元0Fとした上三角化行列MTTFVを生成する。ただし、Ωは1以上であって部分行列MTTFVの行数及び列数以下の整数である。MTTFVは例えば以下のようになる。ただしΩ1行以降の各要素が存在しない場合もあり得、また、Ω1列以降の各要素が存在しない場合もあり得る。このような上三角化行列MTTFVは例えば、ガウスの消去法を利用して生成できる。すなわち、例えばまず、部分行列MTTFVの1行目の行ベクトルmt1→をmt11で除算したものをMTTFVの1行目の行ベクトルとする。次に、部分行列MTTFVの2行目の行ベクトルmt2→からMTTFVの1行目の行ベクトルをmt21倍した行ベクトルを減じた行ベクトルをmt22で除算したものをMTTFVの2行目の行ベクトルとする。同様に、既に生成したMTTFVの各行ベクトルを用いてそれよりも大きな行番号の行ベクトルを加工していくことにより、上三角化行列MTTFVが生成できる。なお、上三角化行列MTTFVを生成するための演算は、行ベクトル単位の単項演算と行ベクトル間の2項演算であり、同一の行ベクトル内の異なる要素に対して異なる演算を行うことは許されない。除算するための法が加法単位元0Fとなった場合には加工対象の行ベクトルが選びなおされる。部分行列MTTFVが互いに線形独立でない複数の行ベクトルすなわち一次従属な複数の行ベクトルを含む場合、そのような行ベクトルを代表する1つの行ベクトルがΩ×Ωの上三角行列の要素を含む行ベクトルとなり、その他の行ベクトルは加法単位元0Fのみを要素とした行ベクトルとなるステップS432。次に、共通鍵生成部126aはλ2に設定するステップS433。共通鍵生成部126aは、以下の式のベクトルを新たなとして、上三角化行列MTTFVの1行目の行ベクトルを更新する。...は上三角化行列MTTFVのλ行目の行ベクトルを表す。共通鍵生成部126aはλΩであるか否かを判定しステップS435、λΩでなければλ1を新たなλとしステップS436、ステップS434の処理に戻る。一方、λΩであれば共通鍵生成部126aは、以下が満たされるか否かを判定するステップS437。...共通鍵生成部126aは、式が満たされるならばKの復号が可能であると判定しステップS438、これを満たさないならばKの復号が不可能であると判定するステップS439。ステップS432の上三角化行列MTTFVを生成するためのすべての演算内容とステップS434でのすべての演算内容とは記憶部123に格納される。Kの復号が可能であると判定された場合ステップS438、上三角化行列MTTFVを生成するためのすべての演算とステップS434でのすべての演算が、部分行列MTTFVの各要素を不定元として得られる行列に施される。それによって得られる行列の1行目の列ベクトルは、部分行列MTTFVの各要素を不定元として得られる行列INDTFVの列ベクトルindλ→λROWROW∈SETの線形和、すなわち、当該列ベクトルindλ→と当該列ベクトルに対応する係数constとの積和となる。constindROW→constindROW→行列INDTFVのμ行目μ∈SETの列ベクトルindμ→に対応する係数constが式を満たす係数constとなる式の関係参照。変形例等本発明は上述の各実施の形態に限定されるものではない。例えば、ステップS47では、式がともに満たされるか否かが判定されたが、その代わりにC及びCλ1Ψを結合した情報とC及びCλ1Ψを結合した情報とが一致するか否かが判定されてもよい。或いはC及びCλ1Ψに対応する1つの関数値とC及びCλ1Ψに対応する1つの関数値とが一致するか否かが判定されてもよい。或いは式がともに満たされる場合に第1値が出力され、式の少なくとも一部が満たされない場合に第1値が出力される関数によって判定がなされてもよい。ステップS48で復号が拒絶されるときに、復号装置120がエラー情報を出力してもよいし、復号結果と無関係な乱数を出力してもよいし、何も出力しなくてもよい。上述の有限体Fq上で定義された各演算が位数qの有限環Zq上で定義された演算に置き換えられてもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置き換える方法の一例は、素数やそのべき乗値以外のqを許容する方法である。式その他の演算において加法単位元が乗じられる項は巡回群G1やG2の単位元となる。加法単位元が乗じられる項の演算は行われてもよいし、行われなくてもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。"