(57)【要約】  木構造以外の一般の半順序構造で表される階層型暗号を実現する。情報生成においては、乱数σｖ，（σｖｊ）ｊ∈ｗ（ｖ）∈Ｚｑを生成し、主情報ｋｖ＝σｖΣｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｖｉｂｉ＊＋ｂＮ＊を計算し、各ｊ∈ｗ（ｖ）について導出情報ｋｖｊ＝σｖｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｖｉｂｉ＊＋ｂｊ＊を計算する。情報導出においては、乱数σｕ，（σｕｊ）ｊ∈ｗ（ｕ）∈Ｚｑを生成し、主情報ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖを計算し、各ｊ∈ｗ（ｕ）について導出情報ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊを計算する。
2010123116.tif 000002
【特許請求の範囲】
【請求項１】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する乱数生成部と、
上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する主情報生成部と、
上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、
を含むことを特徴とする情報生成装置。
【請求項２】
請求項１に記載の情報生成装置において、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
インデックスｖに対応する主情報ｋｖ及びインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記乱数生成部は、更に乱数σｕ∈Ｚｑを生成し、
上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、
を含む情報生成装置。
【請求項３】
請求項２に記載の情報生成装置において、
上記乱数生成部は、更に集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）に対応する乱数σｕｊ∈Ｚｑを生成し、
上記記憶部から読み込んだ導出情報ｋｖｊ及び上記生成された乱数σｕｉを用いて、ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊの関係を満たすインデックスｕに対応する導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項４】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、σＹ∈Ｚｑを乱数とし、σＹｉを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数とし、インデックスＹに対応する主情報ｋＹはｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たし、インデックスＹに対応する導出情報ｋＹｉはｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たし、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
上記主情報ｋＹである又は上記主情報ｋＹ及び上記導出情報ｋＹｉから導出されたインデックスｖに対応する主情報ｋｖ、及び、上記導出情報ｋＹｉである又は上記導出情報ｋＹｉから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
乱数σｕ∈Ｚｑを生成する子乱数生成部と、
上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、
を含む情報生成装置。
【請求項５】
請求項４に記載の情報生成装置において、
上記乱数生成部は、さらに集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）に対応する乱数σｕｊ∈Ｚｑを生成し、
上記記憶部から読み込んだ導出情報ｋｖｊ及び上記生成された乱数σｕｉを用いて、ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項６】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数ｒＹ∈Ｚｑを生成する乱数生成部と、
上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する第一主情報生成部と、
上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する第二主情報生成部と、
上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、
を含むことを特徴とする情報生成装置。
【請求項７】
請求項６に記載の情報生成装置において、
上記乱数生成部は、更に乱数ｒｕ∈Ｚｑを生成し、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
インデックスｖに対応する第一主情報ｋｖ、第二主情報ｇｒ及びインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記記憶部から読み込んだ第一主情報ｋｖ及び導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、
上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、
を含むことを特徴とする情報生成装置。
【請求項８】
請求項７に記載の情報生成装置において、
上記記憶部から読み込んだ導出情報ｋｖｉ及び上記生成された乱数ｒｕを用いて、ｋｕｊ＝ｋｖｊｈｊｒｕの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項９】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、
ｒＹ∈Ｚｑを乱数とし、インデックスＹに対応する第一主情報ｋＹはｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たし、ｇｒＹをインデックスＹに対応する第二主情報とし、インデックスＹに対応する導出情報ｋＹｉはｋＹｊ＝ｈｊｒＹの関係を満たし、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
乱数ｒｕ∈Ｚｑを生成する乱数生成部と、
上記第一主情報ｋＹである又は上記第一主情報ｋＹ及び上記導出情報ｋＹｉから導出されたインデックスｖに対応する第一主情報ｋｖ、上記導出情報ｋＹｉである又は上記導出情報ｋＹｉから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記記憶部から読み込んだ第一主情報ｋｖ及び上記導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、
上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、
を含む情報生成装置。
【請求項１０】
請求項９に記載された情報生成装置において、
上記記憶部から読み込んだ導出情報ｋｖｉ及び上記生成された乱数ｒｕを用いて、ｋｕｊ＝ｋｖｊｈｊｒｕの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
情報生成装置。
【請求項１１】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数生成部が、乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する乱数生成ステップと、
主情報生成部が、上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する主情報生成ステップと、
導出情報生成部が、上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成ステップと、
を含むことを特徴とする情報生成方法。
【請求項１２】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数生成部が、乱数ｒＹ∈Ｚｑを生成する乱数生成ステップと、
第一主情報生成部が、上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する第一主情報生成ステップと、
第二主情報生成部が、上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する第二主情報生成ステップと、
導出情報生成部が、上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成ステップと、
を含むことを特徴とする情報生成方法。
【請求項１３】
請求項１から１０の何れかに記載された情報生成装置の各部としてコンピュータを機能させるための情報生成プログラム。
【請求項１４】
請求項１３に記載された情報生成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術に関する。例えば、復号鍵からより復号権限の制限された復号鍵を導出することができる階層型暗号に関するものである。
【背景技術】
【０００２】
階層型暗号の従来技術として、非特許文献１に記載された技術が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Craig Gentry, Alice Silverberg, “Hierarchical ID-Based Cryptography”, ASIACRYPT 2002, p.548-566
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載された技術では、木構造の親ノードに対応する鍵から子ノードに対応する鍵を導出することはできるが、木構造以外の一般の半順序構造ｓで表される鍵導出を実現することはできなかった。例えば、共通の子ノードＣを持つ親ノードＡと親ノードＢに対して、親ノードＡの鍵から共通の子ノードＣの鍵を導出し、親ノードＢの鍵から共通の子ノードＣの鍵を導出することはできないという課題があった。
【課題を解決するための手段】
【０００５】
上記の課題を解決するために、請求項１の情報生成装置は、ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する乱数生成部と、上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する主情報生成部と、上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、を含む。【０００６】
請求項４の情報生成装置は、ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、σＹ∈Ｚｑを乱数とし、σＹｉを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数とし、インデックスＹに対応する主情報ｋＹはｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たし、インデックスＹに対応する導出情報ｋＹｉはｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たし、＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、上記主情報ｋＹである又は上記主情報ｋＹ及び上記導出情報ｋＹｉから導出されたインデックスｖに対応する主情報ｋｖ、及び、上記導出情報ｋＹｉである又は上記導出情報ｋＹｉから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、乱数σｕ∈Ｚｑを生成する子乱数生成部と、上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、を含む。【０００７】
請求項６の情報生成装置は、Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、乱数ｒＹ∈Ｚｑを生成する乱数生成部と、上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する第一主情報生成部と、上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する第二主情報生成部と、上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、を含む。【０００８】
請求項９の情報生成装置は、Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、ｒＹ∈Ｚｑを乱数とし、インデックスＹに対応する第一主情報ｋＹはｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たし、ｇｒＹをインデックスＹに対応する第二主情報とし、インデックスＹに対応する導出情報ｋＹｉはｋＹｊ＝ｈｊｒＹの関係を満たし、＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、乱数ｒｕ∈Ｚｑを生成する乱数生成部と、上記第一主情報ｋＹである又は上記第一主情報ｋＹ及び上記導出情報ｋＹｉから導出されたインデックスｖに対応する第一主情報ｋｖ、上記導出情報ｋＹｉである又は上記導出情報ｋＹｉから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、上記記憶部から読み込んだ第一主情報ｋｖ及び上記導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、を含む。
【発明の効果】
【０００９】
共通の子ノードＣを持つ親ノードＡと親ノードＢに対して、親ノードＡの情報から共通の子ノードＣの情報を導出し、親ノードＢの情報から共通の子ノードＣの情報を導出することができる。
【図面の簡単な説明】
【００１０】
【図１】第一実施形態の情報生成装置の機能ブロック図の例。
【図２】第一実施形態の情報生成のフローチャートの例。
【図３】第一実施形態の情報導出のフローチャートの例。
【図４】第二実施形態の情報生成装置の機能ブロック図の例。
【図５】第二実施形態の情報生成のフローチャートの例。
【図６】第二実施形態の情報導出のフローチャートの例。
【発明を実施するための形態】
【００１１】
以下、この発明の実施の形態について、詳細に説明する。
［述語暗号］
まず、第一実施形態で用いる概念である述語暗号の概要について説明する。
【００１２】
〔定義〕
まず、本形態で使用する用語や記号を定義する。
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
【００１３】
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
ｋ：ｋはセキュリティパラメータ（k∈Z, k>0）を表す。
【００１４】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}*は整数0及び1からなる系列に限定されない。{0,1}*は位数2の有限体又はその拡大体と同義である。
{0,1}ζ：{0,1}ζはビット長ζ（ζ∈Z, ζ>0）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}ζは整数0及び1からなる系列に限定されない。{0,1}ζは位数2の有限体（ζ=1の場合）又はそれをζ次拡大した拡大体（ζ>1の場合）と同義である。
(+):(+)はバイナリ系列間の排他的論理和演算子を表す。例えば、10110011(+)11100001=01010010を満たす。
【００１５】
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。なお、有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。また、有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献１「ISO/IEC 18033-2: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers」に開示されている。
【００１６】
0F：0Fは有限体Fqの加法単位元を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
E：Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6          …(1)
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線E上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線E上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献３「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
【００１７】
また、楕円曲線E上の有理点からなる有限集合は位数p(p≧1)の部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数を＃Eとし、pを＃Eを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合E[p]は、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A＝Ｏを満たす点を意味する。
【００１８】
G1, G2,GT：G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のｐ乗根からなる有限集合である。
【００１９】
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群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で定義された演算を行うことを意味する。
【００２０】
G1n+1：G1n+1はn+1(n≧1)個の巡回群G1の直積を表す。
G2n+1：G2n+1はn+1個の巡回群G2の直積を表す。
g1, g2, gT：g1, g2, gTは巡回群G1, G2,GTの生成元を表す。
V：Vはn+1個の巡回群G1の直積からなるn+1次元のベクトル空間を表す。
V*：V*はn+1個の巡回群G2の直積からなるn+1次元のベクトル空間を表す。
【００２１】
e：eは直積G1n+1と直積G2n+1との直積G1n+1×G2n+1を巡回群GTに写す非退化な双線形写像（bilinear map）を計算するための関数（「双線形関数」と呼ぶ）を表す。双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)(n≧1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)とを入力とし、巡回群GTの１個の元を出力する。
e：G1n+1×G2n+1→GT            …(2)
【００２２】
双線形関数eは以下の性質を満たす。
［双線形性］すべてのΓ1∈G1n+1，Γ2∈G2n+1及びν，κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ          …(3)
［非退化性］すべての
Γ1∈G1n+1，Γ2∈G2n+1          …(4)
を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1n+1，Γ2∈G2n+1についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２３】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT            …(5)
を用いて双線形関数eを構成する。本形態の双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)からなるn+1次元ベクトル(γ1,...,γn+1)と、巡回群G2のn+1個の元γL*(i=1,...,n+1)からなるn+1次元ベクトル(γ1*,...,γn+1*)との入力に対し、巡回群GTの１個の元
e=ΠL=1n+1 Pair(γL, γL*)          …(6)
を出力する関数である。
【００２４】
なお、双線形関数Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する関数であり、以下の性質を満たす。
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(7)
［非退化性］すべての
Ω1∈G1，Ω2∈G2          …(8)
を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００２５】
なお、双線形関数Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献４「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))（Ω1∈G1，Ω2∈G2）を双線形関数Pairとして用いてもよい（例えば、参考文献２等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献５「V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。また、ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている（例えば、参考文献２、参考文献６「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献７「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献８「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」等参照）。
【００２６】
ai(i=1,...,n+1)：巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn+1次元の基底ベクトルである。この場合、n+1次元の基底ベクトルai(i=1,...,n+1)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0)           …(9)
...
an+1=(0,0,0,...,κ1・g1)
【００２７】
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルai(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルaiは前述のベクトル空間Vを張る。
【００２８】
ai*(i=1,...,n+1)：ai*は巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn+1次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+1)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0)            …(10)
...
an+1*=(0,0,0,...,κ2・g2)
【００２９】
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルai*(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルai*は前述のベクトル空間V*を張る。
【００３０】
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j)           …(11)
を満たす。すなわち、i=jの場合には、式(6)(7)の関係から、
e(ai, aj*)= Pair(κ1・g1,κ2・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。一方、i≠jの場合には、e(ai, aj*)は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(7)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
e(ai, aj*)=e(g1, g2)0=gT0
を満たす。
【００３１】
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(ai, aj*)=gTδ(i,j)           …(12)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【００３２】
A：Aは基底ベクトルai(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。例えば、基底ベクトルai(i=1,...,n+1)が式(9)によって表現される場合、行列Aは、
【００３３】
【数１】
2010123116.tif 000003
【００３４】
となる。
A*：A*は基底ベクトルai*(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+1)が式(10)によって表現される場合、行列A*は、
【００３５】
【数２】
2010123116.tif 000004
【００３６】
となる。
X：Xは有限体Fqの元を要素とするn+1行n+1列の行列を表す。行列Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列(i=1,...,n+1,j=1,...,n+1)の要素をχi,j∈Fqとすると、行列Xは、
【００３７】
【数３】
2010123116.tif 000005
【００３８】
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
X *：X *は行列Xの逆行列の転置行列X*=( X-1)Tを表す。行列X *は基底ベクトルai*の座標変換に用いられる。行列X *のi行j列の要素をχi,j*∈Fqとすると、行列X*は、
【００３９】
【数４】
2010123116.tif 000006
【００４０】
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
この場合、n+1行n+1列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【００４１】
【数５】
2010123116.tif 000007
【００４２】
に対し、
【００４３】
【数６】
2010123116.tif 000008
【００４４】
を満たす。ここで、n+1次元ベクトル
χi→=(χi,1,...,χi,n+1)            …(19)
χj→*=(χj,1*,...,χj,n+1*)           …(20)
を定義する。すると、式(18)の関係から、n+1次元ベクトルχi→とχj→*との内積は、
χi→・χj→*=δ(i,j)          …(21)
となる。
【００４５】
bi：biは巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルbiは行列Xを用いて基底ベクトルai(i=1,...,n+1)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bi=Σj=1n+1χi,j・aj          …(22)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+1)が式(9)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
bi=(χi,1・κ1・g1 ,χi,2・κ1・g1 ,...,χi,n+1・κ1・g1)     …(23)
【００４６】
巡回群G1のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルbi(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルbiは前述のベクトル空間Vを張る。
【００４７】
bi*：bi*は巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+1)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*=Σj=1n+1χi,j*・aj*          …(24)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+1)が式(10)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*=(χi,1*・κ2・g2 ,χi,2*・κ2・g2 ,...,χi,n+1*・κ2・g2)   …(25)
巡回群G2のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルbi*(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
【００４８】
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j)           …(26)
を満たす。すなわち、式(6)(21)(23)(25)の関係から、
【００４９】
【数７】
2010123116.tif 000009
【００５０】
を満たす。特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(bi, bj*)=gTδ(i,j)           …(27)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間（ベクトル空間Vとベクトル空間V*）の双対正規直交基底である。
なお、式(26)の関係を満たすのであれば、式(9)(10)で例示したもの以外の基底ベクトルai及びai*や、式(22)(24)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
【００５１】
B：Bは基底ベクトルbi(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。B=X・Aを満たす。例えば、基底ベクトルbiが式(23)によって表現される場合、行列Bは、
【００５２】
【数８】
2010123116.tif 000010
【００５３】
となる。
B*：B*は基底ベクトルbi*(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+1)が式(25)によって表現される場合、行列B*は、
【００５４】
【数９】
2010123116.tif 000011
【００５５】
となる。
w→：w→は有限体Fqの元を要素とするn次元ベクトルを表す。
w→=(w1,...,wn)∈Fqn          …(30)
wμ：wμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
v→：v→は有限体Fqの元を要素とするn次元ベクトルを表す。
v→=(v1,...,vn)∈Fqn          …(31)
vμ：vμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
【００５６】
衝突困難な関数：「衝突困難な関数」とは、十分大きなセキュリティパラメータkに対して以下の条件を満たす関数h、又は、それとみなせる関数を表す。
Pr[A(h)=(x,y)|h(x)=h(y)∧x≠y]<ε(k)           …(32)
ただし、Pr[・]は事象[・]の確率であり、A(h)は関数hに対してh(x)=h(y)を満たす値x,y（x≠y）を算出する確率的多項式時間アルゴリズムであり、ε(k)はセキュリティパラメータkについての多項式である。衝突困難な関数の例は、参考文献１に開示された「cryptographic hash function」などのハッシュ関数である。
【００５７】
単射関数：「単射関数」とは、値域に属する元が何れもその定義域のただ一つの元の像として表される関数、又は、それとみなせる関数を表す。
【００５８】
擬似的なランダム関数：「擬似的なランダム関数」とは、任意の確率的多項式時間アルゴリズムが集合Φζとその部分集合φζとを区別できない場合における、当該部分集合φζに属する関数、又は、それとみなせる関数を表す。ただし、集合Φζは集合{0,1}ζの元を集合{0,1}ζの元へ写すすべての関数の集合である。擬似的なランダム関数の例は、上述のようなハッシュ関数である。
【００５９】
H1：H1は２つのバイナリ系列（ω1,ω2）∈{0,1}k×{0,1}*を入力とし、有限体Fqの２つの元（ψ1,ψ2）∈Fq×Fqを出力する衝突困難な関数を表す。
H1：{0,1}k×{0,1}*→Fq×Fq           …(33)
【００６０】
このような関数H1の例は、ω1とω2とのビット連結値ω1||ω2を入力とし、参考文献１に開示された「cryptographic hash function」などのハッシュ関数と、「バイナリ系列から整数への変換関数（Octet string/integer conversion）」と、「バイナリ系列から有限体の元への変換関数（Octet string and integer/finite field conversion）」との演算を行い、有限体Fqの２つの元（ψ1,ψ2）∈Fq×Fqを出力する関数である。なお、関数H1は、擬似的なランダム関数であることが望ましい。
【００６１】
H2：H2は巡回群GTの元とバイナリ系列（ξ,ω2）∈GT×{0,1}*を入力とし、有限体Fqの１つの元ψ∈Fqを出力する衝突困難な関数を表す。
H2：GT×{0,1}*→Fq          …(34)
【００６２】
このような関数H2の例は、巡回群GTの元ξ∈GTとバイナリ系列ω2∈{0,1}*とを入力とし、巡回群GTの元ξ∈GTを参考文献１に開示された「有限体の元からバイナリ系列への変換関数（Octet string and integer/finite field conversion）」に入力してバイナリ系列を求め、そのバイナリ系列とバイナリ系列ω2∈{0,1}*とのビット連結値に対して参考文献１に開示された「cryptographic hash function」などのハッシュ関数演算を行い、さらに「バイナリ系列から有限体の元への変換関数（Octet string and integer/finite field conversion）」の演算を行い、有限体Fqの１つの元ψ∈Fqを出力する関数である。なお、安全性の観点から、関数H2は擬似的なランダム関数であることがより望ましい。
【００６３】
R:Rは１つの巡回群GTの元ξ∈GTを入力とし、１つのバイナリ系列ω∈{0,1}kを出力する単射関数を表す。
R：GT→{0,1}k          …(35)
【００６４】
このような単射関数Rの例は、巡回群GTの元ξ∈GTを入力とし、参考文献１に開示された「有限体の元からバイナリ系列への変換関数（Octet string and integer/finite field conversion）」と、参考文献１に開示された「KDF(Key Derivation Function)」などのハッシュ関数との演算を行い、１つのバイナリ系列ω∈{0,1}kを出力する関数である。なお、安全性の観点から、関数Rは衝突困難な関数であることが望ましく、擬似的なランダム関数であることがより望ましい。
【００６５】
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。共通鍵暗号方式の具体例は、カメリア（Camellia）やAESなどである。
Enck(M)：Enck(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
Deck(C)：Deck(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【００６６】
〔内積述語暗号〕
次に、内積述語暗号の基本的な構成について説明する。
＜述語暗号＞
述語暗号（「関数暗号」と呼ぶ場合もある）とは、「属性情報」と呼ばれる情報と「述語情報」と呼ばれる情報との組み合わせが所定の論理式を「真」にする場合に暗号文が復号できる方式である。「属性情報」と「述語情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。従来の述語暗号の構成は、例えば、参考文献９「"Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products," with Amit Sahai and Brent Waters One of 4 papers from Eurocrypt 2008 invited to the Journal of Cryptology」等に開示されている。
【００６７】
＜内積述語暗号＞
内積述語暗号は、属性情報や述語情報としてベクトルを用い、それらの内積が０となる場合に暗号文が復号される述語暗号である。内積述語暗号では、内積が０となることと論理式が「真」となることとが等価である。
【００６８】
［論理式と多項式との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
まず、「xがη1である」という命題１と「xがη2である」という命題２との論理和 (x=η1)∨(x=η2)を
(x-η1)・(x-η2)          …(36)
という多項式で表現する。すると、各真理値と式(36)の関数値との関係は以下のようになる。
【００６９】
【表１】
2010123116.tif 000012
[表1]から分かるように、論理和(x=η1)∨(x=η2)が真である場合、式(36)の関数値は0になり、論理和(x=η1)∨(x=η2)が偽である場合、式(36)の関数値は0以外の値となる。すなわち、論理和(x=η1)∨(x=η2)が真であることと、式(36)の関数値が0となることとは等価である。よって、論理和は式(36)で表現できる。
【００７０】
また、「xがη1である」という命題１と「xがη2である」という命題２との論理積 (x=η1)∧(x=η2)を
ι1・(x-η1)+ι2・(x-η2)          …(37)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(37)の関数値とは以下の関係となる。
【００７１】
【表２】
2010123116.tif 000013
[表２]から分かるように、論理積 (x=η1)∧(x=η2)が真である場合、式(37)の関数値は0になり、論理積 (x=η1)∧(x=η2)が偽である場合、式(37)の関数値は0以外の値となる。すなわち、論理積 (x=η1)∧(x=η2)が真であることと、式(37)の関数値が0となることとは等価である。よって、論理積は式(37)で表現できる。
【００７２】
以上のように、式(36)と式(37)とを用いることで論理和や論理積からなる論理式を多項式f(x)で表現できる。例えば、論理式{(x=η1)∨(x=η2)∨(x=η3)}∧(x=η4)∧(x=η5)は、多項式
f(x)=ι1・{(x-η1)・(x-η2)・(x-η3)}+ι2・(x=η4)+ι3・(x=η5)  …(38)
で表現できる。
【００７３】
なお、式(36）では、１つの不定元xを用いて論理和を表現したが、複数の不定元を用いて論理和を表現することも可能である。例えば、２つの不定元x0及びx1を用い、「x0がη0である」という命題１と「x1がη1である」という命題２との論理和 (x0=η0)∨(x1=η1)を
(x0-η0)・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理和を多項式で表現することも可能である。
【００７４】
また、式(37）では、１つの不定元xを用いて論理積を表現したが、複数の不定元を用いて論理積を表現することも可能である。例えば、また、「x0がη0である」という命題１と「x1がη1である」という命題２との論理積 (x0=η0)∧(x1=η1)を
ι0・(x0-η0)+ι1・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理積を多項式で表現することも可能である。
【００７５】
論理和及び／又は論理積を含む論理式をH(H≧1)種類の不定元x0,...,xH-1を用いて表現した多項式をf(x0,...,xH-1)と表現する。また、各不定元x0,...,xH-1に対応する命題を「xhがηhである」とする。ただし、ηh（h=0,...H-1）は命題ごとに定まる定数である。この場合、当該論理式を示す多項式f(x0,...,xH-1)は、不定元xhと定数ηhとの差をとる多項式によって当該不定元xhが当該定数ηhであるという命題を表現し、命題をそれぞれ表現する多項式の積によって当該命題の論理和を表現し、命題又は命題の論理和をそれぞれ表現する多項式の線形和によって当該命題又は命題の論理和の論理積を表現し、それによって論理式を表現した多項式となる。例えば、５つの不定元x0,...,x4を用い、論理式{(x0=η0)∨(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)を多項式で表現すると、
f(x0,...,x4)
=ι0・{(x0-η0)・(x1-η1)・(x2-η2)}+ι1・(x3=η3)+ι2・(x4=η4)
となる。
【００７６】
［多項式と内積の関係］
論理式を示す多項式f(x0,...,xH-1)は、２つのn次元ベクトルの内積で表現できる。すなわち、多項式f(x0,...,xH-1)は、当該多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトル
v→=(v1,...,vn)
と、当該多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
w→=(w1,...,wn)
との内積
f(x0,...,xH-1)=w→・v→
に等しい。すなわち、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルv→と、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトルw→との内積が0であるか否かとは等価である。
【００７７】
f(x0,...,xH-1)=0  ←→  w→・v→=0
例えば、１つの不定元xで表現された多項式f(x)=θ0・x0+θ1・x+...+θn-1・xn-1は、２つのn次元ベクトル
w→=(w1,...,wn)=(θ0,...,θn-1)          …(39)
v→=(v1,...,vn)=(x0,...,xn-1)          …(40)
の内積
f(x)= w→・v→          …(41)
で表現できる。すなわち、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
【００７８】
f(x)=0  ←→  w→・v→=0          …(42)
また、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルを
w→=(w1,...,wn)
とし、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
v→=(v1,...,vn)
としても、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、ベクトルw→とベクトルv→との内積が0であるか否かとは等価である。
【００７９】
例えば、式(39)(40)の代わりに
w→=(w1,...,wn)=(x0,...,xn)        …(43)
v→=(v1,...,vn)=(θ1,...,θn-1)          …(44)
としても、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
【００８０】
内積述語暗号では、ベクトルv→=(v0,...,vn-1)及びw→=(w0,...,wn-1)の何れか一方を属性情報とし、他方を述語情報とし、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、n次元ベクトル(θ0,...,θn-1)が述語情報とされ、n次元ベクトル(x0,...,xn-1)が属性情報とされ、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。なお、以下では、鍵情報に埋め込まれるn次元ベクトルをw→=(w1,...,wn)とし、暗号文に埋め込まれるn次元ベクトルをv→=(v1,...,vn)とする。例えば、
述語情報：w→=(w1,...,wn)=(θ0,...,θn-1)
属性情報：v→=(v1,...,vn)=(x0,...,xn-1)
であるか、
述語情報：v→=(v1,...,vn)=(θ0,...,θn-1)
属性情報：w→=(w1,...,wn)=(x0,...,xn-1)
である。
【００８１】
［内積述語暗号の基本構成］
以下では、内積述語暗号を用いて鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。この構成はSetup(1k)，GenKey(MSK,w→)，Enc(PA,v→)，Dec(SKw,C2)を含む。
【００８２】
《Setup(1k)：セットアップ》
−入力：セキュリティパラメータk
−出力：マスター鍵情報MSK，公開パラメータPK
Setup(1k)の一例では、まず、セキュリティパラメータkをnとして、n+1次元の基底ベクトルai(i=1,...,n+1)を要素とするn+1行n+1列の行列Aと、基底ベクトルai*(i=1,...,n+1)を要素とするn+1行n+1列の行列A*と、座標変換のためのn+1行n+1列の行列X，X*とが選択される。次に、式(22)に従って座標変換されたn+1次元の基底ベクトルbi(i=1,...,n+1)が算出され、式(24)に従って座標変換されたn+1次元の基底ベクトルbi*(i=1,...,n+1)が算出される。そして、基底ベクトルbi*(i=1,...,n+1)を要素とするn+1行n+1列の行列B*がマスター鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+1)を要素とするn+1行n+1列の行列B、セキュリティパラメータk、有限体Fq、楕円曲線E、巡回群G1, G2,GT、生成元g1, g2, gT、双線形関数eなどが公開パラメータPKとして出力される。
【００８３】
《GenKey(MSK,w→)：鍵情報生成》
−入力：マスター鍵情報MSK，ベクトルw→
−出力：ベクトルw→に対応する鍵情報D*
GenKey(MSK,w→)の一例では、まず、有限体Fqから元α∈Fqが選択される。そして、マスター鍵情報MSKである行列B*を用い、ベクトルw→に対応する鍵情報
D*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1        …(45)
が生成され、出力される。なお、巡回群G2上での離散対数問題の求解が困難である場合、鍵情報D*からwμ・bμ*やbn+1*の成分を分離抽出することは困難である。
【００８４】
《Enc(PA,v→)：暗号化》
−入力：公開パラメータPK，ベクトルv→
−出力：暗号文C2，共通鍵K
Enc(PA,v→)の一例では、まず、共通鍵Kと有限体Fqの元である乱数υ1とが生成される。そして、行列Bなどの公開パラメータPKと、共通鍵Kを含む値に対応する有限体Fqの元υ2と、ベクトルv→と、乱数υ1とを用い、暗号文
C2=υ1・(Σμ=1nvμ・bμ)+υ2・bn+1∈G1n+1        …(46)
が生成される。そして、暗号文C2と共通鍵Kとが出力される。共通鍵Kの一例はK=gTτ・υ2∈GTである。ここで、添え字のυ2はυ2を意味する。また、前述のようにτの一例はτ=1Fである。なお、巡回群G1上での離散対数問題の求解が困難である場合、暗号文C2からvμ・bμやυ2・bn+1の成分を分離抽出することは困難である。
【００８５】
《Dec(SKw,C2)：復号・鍵共有》
−入力：ベクトルw→に対応する鍵情報D1*，暗号文C2
−出力：共通鍵K
Dec(SKw,C2)の一例では、まず、暗号文C2と鍵情報D1*とが式(2)の双線形関数eに入力される。すると、式(3)(26)の性質から、
【００８６】
【数１０】
2010123116.tif 000014
【００８７】
を満たす。
ここで、内積w→・v→=0であれば、式(47)は、
【００８８】
【数１１】
2010123116.tif 000015
【００８９】
と変形できる。この結果から共通鍵Kが生成され出力される。共通鍵Kの一例はK=gTτ・υ2∈GTである。
【００９０】
［第一実施形態］
第一実施形態の情報生成装置及び方法は、前述した述語暗号を用いて階層型暗号を実現したものである。具体的には、前述した述語暗号で登場する基底ｂ＊を用いて、木構造以外の一般の半順序構造で表される情報導出を実現するものである。
図１に、第一実施形態の情報生成装置の機能ブロック図を例示する。
【００９１】
各情報には、インデックスｖが付けられている。インデックスｖは、ｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１であり、インデックスｖには対応する集合ｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝が定義されている。＊は不定文字である。以下に登場するインデックスｕ，インデックスＹ等のインデックスはインデックスｖと同様の構造を持ち、インデックスｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１、インデックスＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１であるとする。インデックスｕ∈Ｉとインデックスｖ∈Ｉに対して、ｗ（ｕ）⊂ｗ（ｖ）かつｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））であるとき、すなわち、ｗ（ｕ）⊂ｗ（ｖ）かつ任意のｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）に対してｖｉ＝ｕｉであるとき、インデックスｕ≦インデックスｖであり、インデックスｖはインデックスｕよりも上位の情報であるとする。ここで、記号「＼」は集合の減算を意味し、例えば集合Ａ＝｛１，２，３｝、集合Ｂ＝｛１｝のとき、Ａ＼Ｂ＝｛２，３｝である。
【００９２】
例えば、インデックスｖ＝｛ｖ１，ｖ２，ｖ３｝＝｛２，＊，＊｝であり、インデックスｕ＝｛ｕ１，ｕ２，ｕ３｝＝｛２，＊，４｝であるとする。このとき、ｗ（ｖ）＝｛２，３｝、ｗ（ｕ）＝｛２｝となり、ｗ（ｕ）⊂ｗ（ｖ）が成立する。また、ｖ１＝ｕ１＝２である。したがって、インデックスｕ≦インデックスｖであり、インデックスｖはインデックスｕよりも上位の情報であるといえる。
【００９３】
以下、基底ｂｉ＊から生成される情報に対するインデックスをインデックスＹと表記し、導出基の情報に対するインデックスをインデックスｖと表記し、その導出基の情報から導出された情報に対するインデックスをインデックスｕと表記する。
【００９４】
＜情報生成＞
情報生成装置及び方法は、図２のステップＡ１からステップＡ３において、基底ｂｉ＊を用いてインデックスＹに対応する情報ＫＹを生成する。情報ＫＹは、主情報ｋＹと導出情報ｋＹｊとを含む。主情報ｋＹは、述語暗号において例えば復号鍵として使用される。導出情報ｋＹｊは、インデックスＹに対応する情報ＫＹよりも下位の情報を生成するために用いられる。
【００９５】
情報生成装置には、インデックスＹ∈Ｉが入力される。
乱数生成部１は、乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する（ステップＡ１）。生成された乱数σＹは、主情報生成部２に送られる。生成された乱数σＹｊは、導出情報生成部３に送られる。例えば、集合ｗ（Ｙ）＝｛２，３｝である場合には、乱数生成部１はσＹ、σＹ２及びσＹ３の３つの乱数を生成する。
【００９６】
主情報生成部２は、上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する（ステップＡ２）。計算された主情報ｋＹは記憶部４に格納される。
【００９７】
導出情報生成部３は、上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する（ステップＡ３）。計算された導出情報ｋＹｊは記憶部４に格納される。
【００９８】
＜情報導出＞
情報生成装置及び方法は、図３のステップＢ１からステップＢ３において、ｕ≦ｖとして、上位のインデックスｖに対応する情報Ｋｖから、下位のインデックスｕに対応する情報Ｋｕを生成する。
【００９９】
インデックスｖに対応する情報Ｋｖは、主情報ｋｖと導出情報ｋｖｊを含む。主情報ｋｖは、述語暗号において例えば復号鍵として使用される。導出情報ｋｖｊは、インデックスｖに対応する情報Ｋｖよりも下位の情報を生成するために用いられる。例えば、インデックスｖ＝Ｙであり、情報Ｋｖ＝情報ＫＹである。また、ステップＢ１からステップＢ３の処理により生成された情報Ｋｕを新たな情報Ｋｖとして、インデックスｕに対応する情報Ｋｕよりも下位の情報Ｋｕ’（ｕ’≦ｕ）を生成してもよい。
【０１００】
インデックスｕに対応する情報Ｋｕは、主情報ｋｕと導出情報ｋｕｊを含む。主情報ｋｕは、述語暗号において例えば復号鍵として使用される。導出情報ｋｕｊは、インデックスｕに対応する情報Ｋｕよりも下位の情報を生成するために用いられる。
情報生成装置には、インデックスｖ及びインデックスｕが入力される。
記憶部４には、インデックスｖに対応する情報Ｋｖが格納されているとする。
【０１０１】
乱数生成部１は、乱数σｕ∈Ｚｑ及び集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）に対応する乱数σｕｊ∈Ｚｑを生成する（ステップＢ１）。生成された乱数σｕは主情報導出部５に送られ、生成された乱数σｕｊは導出情報導出部６に送られる。
【０１０２】
主情報導出部５は、記憶部４から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する（ステップＢ２）。計算された主情報ｋｕは、記憶部４に格納される。
【０１０３】
導出情報導出部６は、記憶部４から読み込んだ導出情報ｋｖｊ及び上記生成された乱数σｕｊを用いて、ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊの関係を満たすインデックスｕに対応する導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する（ステップＢ３）。計算された導出情報ｋｕｊは、記憶部４に格納される。
【０１０４】
このようにして、インデックスＹに対応する情報ＫＹを生成して、この情報ＫＹを基にして下位のインデックスに対応する情報を導出することにより、共通の子ノードＣを持つ親ノードＡと親ノードＢに対して、親ノードＡの情報から共通の子ノードＣの情報を導出し、親ノードＢの情報から共通の子ノードＣの情報を導出することができる。
【０１０５】
＜具体例１＞
以下、各ノードの情報が述語暗号における鍵であり、インデックスｖ１の情報から生成したインデックスｖ３の情報と、インデックスｖ２の情報から生成したインデックスｖ３の情報とが、述語暗号における鍵という観点から一致することを説明する。以下に示すインデックスｖ１、インデックスｖ２、インデックスｖ３は一例であり、他のインデックスについても同様のことが言える。
【０１０６】
インデックスｖ１＝｛ｖ１，ｖ２，＊，＊｝とし、インデックスｖ２＝｛＊，＊，ｖ３，ｖ４｝とし、インデックスｖ３＝｛ｖ１，ｖ２，ｖ３，ｖ４｝とする。定義より、ｖ１≧ｖ３、ｖ２≧ｖ３であり、親ノードであるインデックスｖ１及び親ノードであるインデックスｖ２は、インデックスｖ３を共通する子ノードとして有する。なお、以下では、ｖｉ（ｉ＝１，２，３）をｖ＾ｉと表記することもある。また、インデックスｖｉのｊ番目の要素をｖ＾ｉｊと表記することもある。
【０１０７】
Ｎ＝５として、Ｎ個の基底ｂ１＊，ｂ２＊，ｂ３＊，ｂ４＊，ｂ５＊から、インデックスｖ１に対応する情報Ｋｖ＾１及びインデックスｖ２に対応する情報Ｋｖ＾２を生成する。σｖ＾１、σｖ＾１３、σｖ＾１４、σｖ＾２、σｖ＾２３、σｖ＾２４、σｖ＾３、σｖ＾３’は乱数生成部１により生成される乱数である。
【０１０８】
インデックスｖ１に対応する情報Ｋｖ＾１（主情報ｋｖ＾１、導出情報ｋｖ＾１３、ｋｖ＾１４）は以下のようになる。
ｋｖ＾１＝σｖ＾１（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ５＊
ｋｖ＾１３＝σｖ＾１３（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ３＊
ｋｖ＾１４＝σｖ＾１４（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ４＊
【０１０９】
また、インデックスｖ２に対応する情報Ｋｖ＾２（主情報ｋｖ＾２、導出情報ｋｖ＾２１、ｋｖ＾２２）は以下のようになる。
ｋｖ＾２＝σｖ＾２（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊
ｋｖ＾２１＝σｖ＾２３（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ１＊
ｋｖ＾２２＝σｖ＾２４（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ２＊
【０１１０】
インデックスｖ１に対応する情報Ｋｖ＾１からインデックスｖ３に対応する主情報ｋｖ＾３を導出すると以下のようになる。以下の式において、ａ＝（σｖ＾３（ｖ３σｖ＾１３＋ｖ４σｖ＾１４）＋σｖ１）であり、ｂ＝σｖ＾３である。
ｋｖ＾３＝σｖ＾３（ｖ３ｋｖ＾１３＋ｖ４ｋｖ＾１４）＋ｋｖ＾１
＝（σｖ＾３（ｖ３σｖ＾１３＋ｖ４σｖ＾１４）＋σｖ＾１）（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋σｖ＾３（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊
＝ａ（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊ 
…（Ａ）
【０１１１】
インデックスｖ２に対応する情報Ｋｖ＾２からインデックスｖ３に対応する主情報ｋｖ＾３を導出すると以下のようになる。以下の式において、ｃ＝σｖ＾３’であり、ｄ＝（σｖ＾３’（ｖ１σｖ＾２３＋ｖ４σｖ＾２４）＋σｖ＾２）である。
ｋｖ＾３＝σｖ＾３’（ｖ１ｋｖ＾２１＋ｖ２ｋｖ＾２２）＋ｋｖ＾２
＝（σｖ＾３’（ｖ１σｖ＾２３＋ｖ４σｖ＾２４）＋σｖ＾２）（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋σｖ＾３’（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ５＊
＝ｃ（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｄ（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊
…（Ｂ）
【０１１２】
上記（Ａ）式に示した情報Ｋｖ＾１から導出した主情報ｋｖ＾３と、上記（Ｂ）式に示した情報Ｋｖ２から導出した主情報ｋｖ３とを比較すると、値は一致しないが、述語暗号において同値な鍵となる。すなわち、（ｖ１ｂ１＊＋ｖ２ｂ２＊）をベクトル（ｂ１＊，ｂ２＊）とベクトル（ｖ１，ｖ２）の内積と見ると、ベクトル（ｂ１＊，ｂ２＊）に対するベクトル（ｖ１，ｖ２）の方向が（Ａ）式と（Ｂ）式で一致しており、同様に、（ｖ３ｂ３＊＋ｖ４ｂ４＊）をベクトル（ｂ３＊，ｂ４＊）とベクトル（ｖ３，ｖ４）の内積と見ると、ベクトル（ｂ３＊，ｂ４＊）に対するベクトル（ｖ３，ｖ４）の方向が（Ａ）式と（Ｂ）式で一致しており、両鍵は述語暗号において同値な鍵となる。
【０１１３】
［第二実施形態］
図４に、第二実施形態の情報生成装置の機能ブロック図を例示する。
【０１１４】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されているとする。
【０１１５】
＜情報生成＞
情報生成装置及び方法は、図５のステップＣ１からステップＣ４において、公開鍵を用いてインデックスＹに対応する情報ＫＹを生成する。情報ＫＹは、第一主情報ｋＹと第二主情報ｇｒＹと導出情報ｋＹｊとを含む。第一主情報ｋＹ及び第二主情報ｇｒＹは、例えば復号鍵として使用される。導出情報ｋＹｉは、インデックスＹに対応する情報ＫＹよりも下位の情報を生成するために用いられる。
【０１１６】
情報生成装置には、インデックスＹ∈Ｉが入力される。
乱数生成部１は、乱数ｒＹ∈Ｚｑを生成する（ステップＣ１）。生成された乱数ｒＹは、第一主情報生成部２１、第二主情報生成部２２及び導出情報生成部３に送られる。
【０１１７】
第一主情報生成部２１は、上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する（ステップＣ２）。計算された第一主情報ｋＹは記憶部４に格納される。
第二主情報生成部２２は、上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する（ステップＣ３）。計算された第二主情報ｋＹは記憶部４に格納される。
【０１１８】
導出情報生成部３は、上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する（ステップＣ４）。計算された導出情報ｋＹｉは、記憶部４に格納される。
【０１１９】
＜情報導出＞
情報生成装置及び方法は、図６のステップＤ１からステップＤ４において、ｕ≦ｖとして、上位のインデックスｖに対応する情報Ｋｖから、下位のインデックスｕに対応する情報Ｋｕを生成する。
【０１２０】
インデックスｖに対応する情報Ｋｖは、第一主情報ｋｖと第二主情報ｇｒｖと導出情報ｋｖｊとを含む。第一主情報ｋｖ及び第二主情報ｇｒｖは、例えば復号鍵として使用される。導出情報ｋｖｊは、インデックスｖに対応する情報Ｋｖよりも下位の情報を生成するために用いられる。例えば、インデックスｖ＝Ｙであり、情報Ｋｖ＝情報ＫＹである。また、ステップＤ１からステップＤ４の処理により生成された情報Ｋｕを新たな情報Ｋｖとして、インデックスｕに対応する情報Ｋｕよりも下位の情報Ｋｕ’（ｕ’≦ｕ）を生成してもよい。
【０１２１】
インデックスｕに対応する情報Ｋｕは、第一主情報ｋｕと第二主情報ｇｒｕと導出情報ｋｕｊとを含む。第一主情報ｋｕ及び第二主情報ｇｒｕは、例えば復号鍵として使用される。導出情報ｋｕｊは、インデックスｕに対応する情報Ｋｕよりも下位の情報を生成するために用いられる。
【０１２２】
情報生成装置には、インデックスｖ及びインデックスｕが入力される。
記憶部４には、インデックスｖに対応する情報Ｋｖが格納されているとする。
乱数生成部１は、乱数ｒｕを生成する（ステップＤ１）。生成された乱数は、第一主情報導出部５１、第二主情報導出部５２及び導出情報導出部６に送られる。
【０１２３】
第一主情報導出部５１は、上記生成された乱数ｒｕ、記憶部４から読み込んだ第一主情報ｋｖ及び導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する（ステップＤ２）。計算された第一主情報ｋｕは、記憶部４に格納される。
【０１２４】
第二主情報導出部５２は、上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する（ステップＤ３）。計算された第二主情報ｇｒｕは、記憶部４に格納される。
【０１２５】
導出情報導出部６は、上記記憶部から読み込んだ導出情報ｋｖｉ及び上記生成された乱数ｒｕを用いて、ｋｕｊ＝ｋｖｊｈｊｒｕの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する（ステップＤ４）。計算された導出情報ｋｕｊは、記憶部４に記憶される。
【０１２６】
このようにして、インデックスＹに対応する情報ＫＹを生成して、この情報ＫＶを基にして下位のインデックスに対応する情報を導出することにより、共通の子ノードＣを持つ親ノードＡと親ノードＢに対して、親ノードＡの情報から共通の子ノードＣの情報を導出し、親ノードＢの情報から共通の子ノードＣの情報を導出することができる。
【０１２７】
＜具体例２＞
以下、各ノードの情報が述語暗号における鍵であり、インデックスｖ１の情報から生成したインデックスｖ３の情報と、インデックスｖ２の情報から生成したインデックスｖ３の情報とが、述語暗号における鍵という観点から一致することを説明する。以下に示すインデックスｖ１、インデックスｖ２、インデックスｖ３は一例であり、他のインデックスについても同様のことが言える。
【０１２８】
インデックスｖ１＝｛ｖ１，ｖ２，＊，＊｝とし、インデックスｖ２＝｛＊，＊，ｖ３，ｖ４｝とし、インデックスｖ３＝｛ｖ１，ｖ２，ｖ３，ｖ４｝とする。定義より、ｖ１≧ｖ３、ｖ２≧ｖ３であり、親ノードであるインデックスｖ１及び親ノードであるインデックスｖ２は、インデックスｖ３を共通する子ノードとして有する。なお、以下では、ｖｉ（ｉ＝１，２，３）をｖ＾ｉと表記することもある。また、インデックスｖｉのｊ番目の要素をｖ＾ｉｊと表記することもある。
【０１２９】
Ｎ＝５として、ｇ１＝ｇａ，ｇ２，ｇ３，ｈ１，ｈ２，ｈ３，ｈ４∈Ｇが公開鍵として公開されているとする。これらの公開鍵から、インデックスｖ１に対応する情報Ｋｖ＾１及びインデックスｖ２に対応する情報Ｋｖ＾２を生成する。ｒｖ＾１、ｒｖ＾２は乱数生成部１により生成される乱数である。
【０１３０】
インデックスｖ１に対応する情報Ｋｖ＾１（第一主情報ｋｖ＾１、第二主情報ｇｒｖ＾１、導出情報ｋｖ＾１３、ｋｖ＾１４）は以下のようになる。
ｋｖ＾１＝ｇ２ａ（ｇ３ｈ１ｖ１ｈ２ｖ２）ｒｖ＾１
ｇｒｖ＾１
ｋｖ＾１３＝ｈ３ｒｖ＾１
ｋｖ＾１４＝ｈ４ｒｖ＾１
【０１３１】
また、インデックスｖ２に対応する情報Ｋｖ＾２（第一主情報ｋｖ＾２、第二導出情報ｇｒｖ＾２、導出情報ｋｖ＾２１、ｋｖ＾２２）は以下のようになる。
ｋｖ＾２＝ｇ２ａ（ｇ３ｈ３ｖ３ｈ４ｖ４）ｒｖ＾２
ｇｒｖ＾２
ｋｖ＾２１＝ｈ１ｒｖ＾２
ｋｖ＾２２＝ｈ２ｒｖ＾２
【０１３２】
インデックスｖ１に対応する情報Ｋｖ＾１からインデックスｖ３に対応する第一主情報ｋｖ＾３を導出すると以下のようになる。なお、ｒｖ＾３は乱数生成部１により生成される乱数であり、ｒ＝ｒｖ＾１＋ｒｖ＾３である。
ｋｖ＾３＝ｋｖ＾１(ｋｖ＾１３ｖ３ｋｖ＾１４ｖ４)(ｇ３ｈ１ｖ１ｈ２ｖ２ｈ３ｖ３ｈ４ｖ４)ｒｖ＾３
＝ｇ２ａ（ｇ３ｈ１ｖ１ｈ２ｖ２ｈ３ｖ３ｈ４ｖ４）ｒ  …（Ｃ）
インデックスｖ２に対応する情報Ｋｖ＾２からインデックスｖ３に対応する主情報ｋｖ＾３を導出すると以下のようになる。なお、ｒｖ＾３’は乱数であり、ｒ’＝ｒｖ＾２＋ｒｖ＾３’である。
ｋｖ＾３＝ｋｖ＾２(ｋｖ＾２１ｖ１ｋｖ＾２２ｖ２)(ｇ３ｈ１ｖ１ｈ２ｖ２ｈ３ｖ３ｈ４ｖ４)ｒｖ＾３’
＝ｇ２ａ（ｇ３ｈ１ｖ１ｈ２ｖ２ｈ３ｖ３ｈ４ｖ４）ｒ’  …（Ｄ）
【０１３３】
上記（Ｃ）式に示した情報Ｋｖ＾１から導出した第一主情報ｋｖ＾３及び第二主情報ｇｒｖ＾３と、上記（Ｄ）式に示した情報Ｋｖ＾２から導出した第一主情報ｋｖ＾３及び第二主情報ｇｒｖ＾３’とを比較すると、これらの値は一致しないが、公開鍵ｇ３，ｈ１，ｈ２，ｈ３，ｈ４の指数の比が一致しており、述語暗号において同値な鍵となる。
【０１３４】
［変形例等］
上記の実施形態では、情報生成装置は、主情報生成部２、導出情報生成部３、主情報導出部５及び導出情報導出部６の全てを有していたが、これらの少なくとも１つの部を有していればよい。例えば、主情報生成部２及び導出情報生成部３のみを有していてもよい。また、主情報導出部５及び導出情報導出部６のみを有しており、既に生成され記憶部４に格納された情報Ｋｖを用いて、情報Ｋｕを生成してもよい。
【０１３５】
また、上述の有限体Fq上で定義された各演算を位数qの有限環Zq上で定義された演算に置き換えてもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置き換える方法の一例は、素数やそのべき乗値以外のqを許容する方法である。
【０１３６】
情報生成装置は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【０１３７】
この処理内容を記述した情報生成プログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１３８】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図１】
2010123116.tif 000016
【図２】
2010123116.tif 000017
【図３】
2010123116.tif 000018
【図４】
2010123116.tif 000019
【図５】
2010123116.tif 000020
【図６】
2010123116.tif 000021
【手続補正書】
【提出日】平成23年9月30日(2011.9.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
請求項４の情報生成装置は、ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、σＹ∈Ｚｑを乱数とし、σＹｉを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数とし、インデックスＹに対応する主情報ｋＹはｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たし、インデックスＹに対応する導出情報ｋＹｊはｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たし、＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、上記主情報ｋＹである又は上記主情報ｋＹ及び上記導出情報ｋＹｊから導出されたインデックスｖに対応する主情報ｋｖ、及び、上記導出情報ｋＹｊである又は上記導出情報ｋＹｊから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、乱数σｕ∈Ｚｑを生成する子乱数生成部と、上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、を含む。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
請求項９の情報生成装置は、Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、ｒＹ∈Ｚｑを乱数とし、インデックスＹに対応する第一主情報ｋＹはｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たし、ｇｒＹをインデックスＹに対応する第二主情報とし、インデックスＹに対応する導出情報ｋＹｊはｋＹｊ＝ｈｊｒＹの関係を満たし、＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、乱数ｒｕ∈Ｚｑを生成する乱数生成部と、上記第一主情報ｋＹである又は上記第一主情報ｋＹ及び上記導出情報ｋＹｊから導出されたインデックスｖに対応する第一主情報ｋｖ、上記導出情報ｋＹｊである又は上記導出情報ｋＹｊから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、上記記憶部から読み込んだ第一主情報ｋｖ及び上記導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、を含む。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT            …(5)
を用いて双線形関数eを構成する。本形態の双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)からなるn+1次元ベクトル(γ1,...,γn+1)と、巡回群G2のn+1個の元γL*(L=1,...,n+1)からなるn+1次元ベクトル(γ1*,...,γn+1*)との入力に対し、巡回群GTの１個の元
e=ΠL=1n+1 Pair(γL, γL*)          …(6)
を出力する関数である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
以上のように、式(36)と式(37)とを用いることで論理和や論理積からなる論理式を多項式f(x)で表現できる。例えば、論理式{(x=η1)∨(x=η2)∨(x=η3)}∧(x=η4)∧(x=η5)は、多項式
f(x)=ι1・{(x-η1)・(x-η2)・(x-η3)}+ι2・(x-η4)+ι3・(x-η5)  …(38)
で表現できる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
論理和及び／又は論理積を含む論理式をH(H≧1)種類の不定元x0,...,xH-1を用いて表現した多項式をf(x0,...,xH-1)と表現する。また、各不定元x0,...,xH-1に対応する命題を「xhがηhである」とする。ただし、ηh（h=0,...H-1）は命題ごとに定まる定数である。この場合、当該論理式を示す多項式f(x0,...,xH-1)は、不定元xhと定数ηhとの差をとる多項式によって当該不定元xhが当該定数ηhであるという命題を表現し、命題をそれぞれ表現する多項式の積によって当該命題の論理和を表現し、命題又は命題の論理和をそれぞれ表現する多項式の線形和によって当該命題又は命題の論理和の論理積を表現し、それによって論理式を表現した多項式となる。例えば、５つの不定元x0,...,x4を用い、論理式{(x0=η0)∨(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)を多項式で表現すると、
f(x0,...,x4)
=ι0・{(x0-η0)・(x1-η1)・(x2-η2)}+ι1・(x3-η3)+ι2・(x4-η4)
となる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
例えば、式(39)(40)の代わりに
w→=(w1,...,wn)=(x0,...,xn-1)        …(43)
v→=(v1,...,vn)=(θ0,...,θn-1)          …(44)
としても、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１１０
【補正方法】変更
【補正の内容】
【０１１０】
インデックスｖ１に対応する情報Ｋｖ＾１からインデックスｖ３に対応する主情報ｋｖ＾３を導出すると以下のようになる。以下の式において、ａ＝（σｖ＾３（ｖ３σｖ＾１３＋ｖ４σｖ＾１４）＋σｖ＾１）であり、ｂ＝σｖ＾３である。
ｋｖ＾３＝σｖ＾３（ｖ３ｋｖ＾１３＋ｖ４ｋｖ＾１４）＋ｋｖ＾１
＝（σｖ＾３（ｖ３σｖ＾１３＋ｖ４σｖ＾１４）＋σｖ＾１）（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋σｖ＾３（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊
＝ａ（ｖ１ｂ１＊＋ｖ２ｂ２＊）＋ｂ（ｖ３ｂ３＊＋ｖ４ｂ４＊）＋ｂ５＊ 
…（Ａ）
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１１２
【補正方法】変更
【補正の内容】
【０１１２】
上記（Ａ）式に示した情報Ｋｖ＾１から導出した主情報ｋｖ＾３と、上記（Ｂ）式に示した情報Ｋｖ＾２から導出した主情報ｋｖ＾３とを比較すると、値は一致しないが、述語暗号において同値な鍵となる。すなわち、（ｖ１ｂ１＊＋ｖ２ｂ２＊）をベクトル（ｂ１＊，ｂ２＊）とベクトル（ｖ１，ｖ２）の内積と見ると、ベクトル（ｂ１＊，ｂ２＊）に対するベクトル（ｖ１，ｖ２）の方向が（Ａ）式と（Ｂ）式で一致しており、同様に、（ｖ３ｂ３＊＋ｖ４ｂ４＊）をベクトル（ｂ３＊，ｂ４＊）とベクトル（ｖ３，ｖ４）の内積と見ると、ベクトル（ｂ３＊，ｂ４＊）に対するベクトル（ｖ３，ｖ４）の方向が（Ａ）式と（Ｂ）式で一致しており、両鍵は述語暗号において同値な鍵となる。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１２６
【補正方法】変更
【補正の内容】
【０１２６】
このようにして、インデックスＹに対応する情報ＫＹを生成して、この情報ＫＹを基にして下位のインデックスに対応する情報を導出することにより、共通の子ノードＣを持つ親ノードＡと親ノードＢに対して、親ノードＡの情報から共通の子ノードＣの情報を導出し、親ノードＢの情報から共通の子ノードＣの情報を導出することができる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１３１
【補正方法】変更
【補正の内容】
【０１３１】
また、インデックスｖ２に対応する情報Ｋｖ＾２（第一主情報ｋｖ＾２、第二主導出情報ｇｒｖ＾２、導出情報ｋｖ＾２１、ｋｖ＾２２）は以下のようになる。
ｋｖ＾２＝ｇ２ａ（ｇ３ｈ３ｖ３ｈ４ｖ４）ｒｖ＾２
ｇｒｖ＾２
ｋｖ＾２１＝ｈ１ｒｖ＾２
ｋｖ＾２２＝ｈ２ｒｖ＾２
【手続補正１１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する乱数生成部と、
上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する主情報生成部と、
上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、
を含むことを特徴とする情報生成装置。
【請求項２】
請求項１に記載の情報生成装置において、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
インデックスｖに対応する主情報ｋｖ及びインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記乱数生成部は、更に乱数σｕ∈Ｚｑを生成し、
上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、
を含む情報生成装置。
【請求項３】
請求項２に記載の情報生成装置において、
上記乱数生成部は、更に集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）に対応する乱数σｕｊ∈Ｚｑを生成し、
上記記憶部から読み込んだ導出情報ｋｖｊ及び上記生成された乱数σｕｊを用いて、ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊの関係を満たすインデックスｕに対応する導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項４】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、σＹ∈Ｚｑを乱数とし、σＹｉを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数とし、インデックスＹに対応する主情報ｋＹはｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たし、インデックスＹに対応する導出情報ｋＹｊはｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たし、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
上記主情報ｋＹである又は上記主情報ｋＹ及び上記導出情報ｋＹｊから導出されたインデックスｖに対応する主情報ｋｖ、及び、上記導出情報ｋＹｊである又は上記導出情報ｋＹｊから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
乱数σｕ∈Ｚｑを生成する乱数生成部と、
上記記憶部から読み込んだ主情報ｋｖ、導出情報ｋｖｉ及び上記生成された乱数σｕを用いて、ｋｕ＝σｕΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖの関係を満たす、インデックスｕに対応する主情報ｋｕを計算する主情報導出部と、
を含む情報生成装置。
【請求項５】
請求項４に記載の情報生成装置において、
上記乱数生成部は、さらに集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）に対応する乱数σｕｊ∈Ｚｑを生成し、
上記記憶部から読み込んだ導出情報ｋｖｊ及び上記生成された乱数σｕｊを用いて、ｋｕｊ＝σｕｊΣｉ∈ｗ（ｖ）＼ｗ（ｕ）ｕｉｋｖｉ＋ｋｖｊの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項６】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数ｒＹ∈Ｚｑを生成する乱数生成部と、
上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する第一主情報生成部と、
上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する第二主情報生成部と、
上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成部と、
を含むことを特徴とする情報生成装置。
【請求項７】
請求項６に記載の情報生成装置において、
上記乱数生成部は、更に乱数ｒｕ∈Ｚｑを生成し、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
インデックスｖに対応する第一主情報ｋｖ、第二主情報ｇｒ及びインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記記憶部から読み込んだ第一主情報ｋｖ及び導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、
上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、
を含むことを特徴とする情報生成装置。
【請求項８】
請求項７に記載の情報生成装置において、
上記記憶部から読み込んだ導出情報ｋｖｉ及び上記生成された乱数ｒｕを用いて、ｋｕｊ＝ｋｖｊｈｊｒｕの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
ことを特徴とする情報生成装置。
【請求項９】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝とし、
ｒＹ∈Ｚｑを乱数とし、インデックスＹに対応する第一主情報ｋＹはｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たし、ｇｒＹをインデックスＹに対応する第二主情報とし、インデックスＹに対応する導出情報ｋＹｊはｋＹｊ＝ｈｊｒＹの関係を満たし、
＊を不定文字とし、インデックスｖをｖ＝（ｖ１，…，ｖＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｖに対応する集合ｗ（ｖ）をｗ（ｖ）＝｛ｉ｜ｖｉ＝＊｝とし、インデックスｕをｕ＝（ｕ１，…，ｕＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスｕに対応する集合ｗ（ｕ）をｗ（ｕ）＝｛ｉ｜ｕｉ＝＊｝とし、集合ｗ（ｕ）⊂集合ｗ（ｖ）とし、ｖｉ＝ｕｉ（ｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ））として、
乱数ｒｕ∈Ｚｑを生成する乱数生成部と、
上記第一主情報ｋＹである又は上記第一主情報ｋＹ及び上記導出情報ｋＹｊから導出されたインデックスｖに対応する第一主情報ｋｖ、上記導出情報ｋＹｊである又は上記導出情報ｋＹｊから導出されたインデックスｖに対応する導出情報ｋｖｊを記憶する記憶部と、
上記記憶部から読み込んだ第一主情報ｋｖ及び上記導出情報ｋｖｉを用いて、ｋｕ＝ｋｖ（Πｉ∈ｗ（ｖ）＼ｗ（ｕ）ｋｖｉｕｉ）（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（ｖ）ｈｉｖｉΠｉ∈ｗ（ｖ）＼ｗ（ｕ）ｈｉｕｉ）ｒｕの関係を満たす、インデックスｕに対応する第一主情報ｋｕを計算する第一主情報導出部と、
上記生成された乱数ｒｕを用いて、第二主情報ｇｒｕを計算する第二主情報導出部と、
を含む情報生成装置。
【請求項１０】
請求項９に記載された情報生成装置において、
上記記憶部から読み込んだ導出情報ｋｖｉ及び上記生成された乱数ｒｕを用いて、ｋｕｊ＝ｋｖｊｈｊｒｕの関係を満たす導出情報ｋｕｊを集合ｗ（ｕ）の各要素ｊ∈ｗ（ｕ）ごとに計算する導出情報導出部を更に含む、
情報生成装置。
【請求項１１】
ｅが巡回群Ｇ１のＮ個の元γＬ（Ｌ＝１，…，Ｎ）（Ｎ≧２）と巡回群Ｇ２のＮ個の元γＬ＊（Ｌ＝１，…，Ｎ）との入力に対して巡回群ＧＴの１個の元を出力する非退化な双線形関数であり、ｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ１のＮ個の元を要素とするＮ次元の基底ベクトルであり、ｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）のそれぞれが、上記巡回群Ｇ２のＮ個の元を要素とするＮ次元の基底ベクトルであり、上記基底ベクトルｂｉ∈Ｇ１Ｎ（ｉ＝１，…，Ｎ）の各要素と上記基底ベクトルｂｊ＊∈Ｇ２Ｎ（ｊ＝１，…，Ｎ）の各要素とを上記双線形関数ｅに入力して得られる関数値が、ｉ＝ｊの場合にδ（ｉ，ｊ）＝１Ｆとなってｉ≠ｊの場合にδ（ｉ，ｊ）＝０Ｆとなるクロネッカーのデルタ関数δ（ｉ，ｊ）を用いてｇＴτ・δ（ｉ，ｊ）∈ＧＴと表現され、０Ｆが有限体Ｆｑの加法単位元であり、１Ｆが有限体Ｆｑの乗法単位元であり、τが０Ｆを除く有限体Ｆｑの元であり、ｇＴが上記巡回群ＧＴの生成元であり、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数生成部が、乱数σＹ∈Ｚｑ、及び、集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）に対応する乱数σＹｊ∈Ｚｑを生成する乱数生成ステップと、
主情報生成部が、上記生成された乱数σＹを用いて、ｋＹ＝σＹΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂＮ＊の関係を満たす主情報ｋＹを計算する主情報生成ステップと、
導出情報生成部が、上記生成された乱数σＹｊを用いて、ｋＹｊ＝σＹｊΣｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）Ｙｉｂｉ＊＋ｂｊ＊の関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成ステップと、
を含むことを特徴とする情報生成方法。
【請求項１２】
Ｇ、ＧＴを素数位数ｑの巡回群とし、ｇを巡回群Ｇの生成元とし、巡回群ＧにはｇＴ＝ｅ（ｇ，ｇ）が巡回群ＧＴの生成元となるようなペアリング関数ｅ：Ｇ×Ｇ→ＧＴが存在するとし、ａをＺｐからランダムに選択された乱数とし、ｇとｇ１＝ｇａ∈Ｇと巡回群Ｇからランダムに選択されたｇ２，ｇ３，ｈ１，…，ｈＮ−１∈Ｇとが公開鍵として公開されており、
＊を不定文字とし、インデックスＹをＹ＝（Ｙ１，…，ＹＮ−１）∈Ｉ＝（Ｆｑ∪｛＊｝）Ｎ−１とし、インデックスＹに対応する集合ｗ（Ｙ）をｗ（Ｙ）＝｛ｉ｜Ｙｉ＝＊｝として、
乱数生成部が、乱数ｒＹ∈Ｚｑを生成する乱数生成ステップと、
第一主情報生成部が、上記生成された乱数ｒＹを用いて、ｋＹ＝ｇ２ａ（ｇ３Πｉ∈｛１，…，Ｎ−１｝＼ｗ（Ｙ）ｈｉＹｉ）ｒＹの関係を満たす第一主情報ｋＹを計算する第一主情報生成ステップと、
第二主情報生成部が、上記生成された乱数ｒＹを用いて、第二主情報ｇｒＹを計算する第二主情報生成ステップと、
導出情報生成部が、上記生成された乱数ｒＹを用いて、ｋＹｊ＝ｈｊｒＹの関係を満たす導出情報ｋＹｊを集合ｗ（Ｙ）の各要素ｊ∈ｗ（Ｙ）ごとに計算する導出情報生成ステップと、
を含むことを特徴とする情報生成方法。
【請求項１３】
請求項１から１０の何れかに記載された情報生成装置の各部としてコンピュータを機能させるための情報生成プログラム。
【請求項１４】
請求項１３に記載された情報生成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【国際調査報告】
2010123116.tif 000022
2010123116.tif 000023
2010123116.tif 000024
2010123116.tif 000025