(57)【要約】  鍵生成装置（９００）には、階層要素（９０２）を含む公開鍵（９０１）、秘密階層要素（９１１）を含むマスター鍵（９０３）、識別子θ（９０４）、及び、乱数（９０５）が入力される。鍵生成装置（９００）は、乱数（９０５）より、２つの乱数要素（９０６ａ）及び（９０６ｂ）を生成し、秘密階層要素（９１１）を２つの乱数のそれぞれでべき乗した要素を含む秘密鍵（９０８）を生成する。
2008099831.tif 000002
【特許請求の範囲】
【請求項１】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、
前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成することを特徴とする鍵生成装置。
【請求項２】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力し、前記下位識別子に対応した下位秘密鍵を生成する鍵導出装置であって、
前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成することを特徴とする鍵導出装置。
【請求項３】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、前記メッセージの暗号文を生成する暗号化装置であって、
前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置。
【請求項４】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、前記暗号文に対応するメッセージを出力する復号装置であって、
前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置。
【請求項５】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、
前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成することを特徴とする鍵生成装置。
【請求項６】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力し、前記下位識別子に対応する秘密鍵を生成する鍵導出装置であって、
前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成することを特徴とする鍵導出装置。
【請求項７】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、暗号文と共通鍵とを生成する暗号化装置であって、
前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置。
【請求項８】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、
暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、共有鍵を出力する復号装置であって、
前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし,前記群Gと群G'から群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置。
【請求項９】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、
前記コンピュータに、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、
前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法。
【請求項１０】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、
前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力するステップと、
前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法。
【請求項１１】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、暗号文を生成する方法であって、
前記コンピュータに、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、
前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成するステップを有することを特徴とする暗号化方法。
【請求項１２】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、メッセージを生成する方法であって、
前記コンピュータに、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、
前記コンピュータが、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めるステップとを有することを特徴とする復号方法。
【請求項１３】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、
前記コンピュータに、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、  前記コンピュータが、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法。
【請求項１４】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、
前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力するステップと、
前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法。
【請求項１５】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵と暗号文とを生成する方法であって、
前記コンピュータに、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、
前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成するステップとを有することを特徴とする暗号化方法。
【請求項１６】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵を生成する方法であって、
前記コンピュータに、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、
前記コンピュータが、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし,前記群Gと群G'から群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めるステップとを有することを特徴とする復号方法。
【請求項１７】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、
乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、
前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成する処理とを実行させることを特徴とするプログラム。
【請求項１８】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、
乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力する処理と、
前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラム。
【請求項１９】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、暗号文を生成する処理を実行させるプログラムであって、前記コンピュータに、
メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記"秘密階層要素"を含まない公開鍵とを入力する処理と、
前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成する処理とを実行させることを特徴とするプログラム。
【請求項２０】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、メッセージを生成する処理を実行させるプログラムであって、前記コンピュータに、
暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、
前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とする復号方法。
【請求項２１】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、
乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、
前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成する処理とを実行させることを特徴とするプログラム。
【請求項２２】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、
乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力する処理と、  前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラム。
【請求項２３】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵と暗号文とを生成する処理を実行させるプログラムであって、前記コンピュータに、
乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、
前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成する処理を実行させることを特徴とするプログラム。
【請求項２４】
同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、
暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、
前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし、前記群Gと群G'から群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵生成装置、鍵導出装置、暗号化装置、及び、復号化装置に関する。更に詳しくは、本発明は、匿名性を有する階層的な識別子に基づく暗号化方式における鍵生成装置、鍵導出装置、暗号化装置、及び、復号化装置、並びに、これらに用いられる方法、及び、プログラムに関する。
【背景技術】
【０００２】
従来の匿名性のある階層的な識別子に基づく暗号化方式について説明する。なお、以下の説明では、pを素数、GとGTを位数pの巡回群、eをG掛けるGからG への非縮退な双線形写像であるとする。ここで、双線形であるとは、全てのα,β∈Z/pZ（Zは整数の集合）、及び、g∈Gに対して、e(gα,hβ)=e(g,g)αβが成り立つことである。また、非縮退であるとは、gがGの生成元であるとき、e(g,g)が、GTの生成元となるということである。Lは階層の最大深さを表す。a^bはabの別の表記である。【０００３】
従来の匿名性のある階層的な識別子に基づく暗号方式として、文献１に挙げられる方式がある。図９に、文献１における鍵生成装置を示す。鍵生成装置１００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、及び、マスター鍵１０３(x,g[3])が入力される。Lを階層数と呼び、(h[1],...,h[L])を強い階層要素１０２と呼ぶ。g[1],g[2],g[3],h[1],...,h[L]はGの要素であり、あるZ/pZの元αに対して、y=g[1]α、x=g[2]αが成り立つように生成されている。【０００４】
鍵生成装置１００には、更に、乱数１０５と、識別子θ１０４(θ＝(θ[1],...,θ[m])∈(Z/pZ)m)が入力される。鍵生成装置１００は、乱数１０５より、Z/pZの要素である乱数要素ξ１０６を生成し、識別子θ１０４に対応する秘密鍵skey(θ)１０８を、下記式に基づいて生成し、出力する。
skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])
=(x(g[3]Πi=1m h[i]θ[i])ξ,g[1]ξ,h[m+1]ξ,...,h[L]ξ)【０００５】
図１０に、文献１における鍵導出装置２００を示す。鍵導出装置２００には、識別子θ１０４(θ=(θ[1],...,θ[m])、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、及び、秘密鍵skey(θ)１０８(skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])が入力される。また、乱数２０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*２０１とが入力される。ここで、θ[m+1]∈Z/pZとする。【０００６】
鍵導出装置２００は、乱数２０２よりZ/pZの要素である乱数要素λ２０３を生成し、下位識別子θ*２０１に対応する下位秘密鍵skey(θ*)２０４を、下記式に基づいて生成し、出力する。
skey(θ*)=(d[θ*,0],d[θ*,1],d[θ*,m+1],...,d[θ*,L])
=(d[θ,0] (g[3](Πi=1m h[i]θ[i])d[θ,m+1]θ[m+1]) λ)
,d[θ,1] gλ,d[θ,m+2] h[m+2]λ,...,d[θ,L] h[L]λ) 
ここで、ξ+λを乱数要素とみなせば、鍵生成装置１００において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。【０００７】
図１１に、文献１における暗号化装置を示す。暗号化装置３００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)と、乱数３０２と、メッセージM３０１(M∈GT)と、識別子θ１０４(θ=(θ[1],...,θ [m])とが入力される。暗号化装置３００は、乱数３０２よりZ/pZの要素であるτを生成し、暗号文ciph(θ,M)３０３を、下記式に基づいて生成し、出力する。
ciph(θ,M)=(C[0],c[1],c[2])=(M e(g[2],y)τ,g[1]τ,(g[3] Πi=1m h[i]θ[i])τ)【０００８】
図１２に、文献１における復号装置を示す。復号装置４００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、秘密鍵skey(θ)１０８、(skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])、及び、識別子θ１０４(θ=(θ[1],...,θ[m])が入力される。また、暗号文ciph(θ,M)３０３(ciph(θ,M)=(C[0],c[1],c[2])が入力される。復号装置４００は、メッセージM３０１を、以下のように復元して出力する。
M=C[0]｛e(c[2],d[θ,1])/e(c[1],d[θ,0])}【０００９】
従来の匿名性のある階層的な識別子に基づく放送暗号方式として、文献２に挙げられる方式がある。図１３に、文献２における鍵生成装置を示す。鍵生成装置５００は、入力手段、出力手段、及び、計算手段を備えている（図示せず）。鍵生成装置５００には、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、及び、マスター鍵５０３(γ,v',y')が入力される。Lを階層数と呼び、(h[1],...,h[L])を強い階層要素５０２と呼ぶ。g,y,h[1],...,h[L]はGの要素であり、ある Z/pZの元α,γに対して、(g'[i])i=1,...,2N=(g^(α^i))i=1,...,2N、v=gγが成り立つように生成されている。【００１０】
鍵生成装置５００には、更に、乱数５０５と、識別子θ５０４(θ=(θ[1],...,θ[m])∈(Z/pZ)m)と、ユーザ番号i５０７とが入力される。鍵生成装置５００は、乱数５０５よりZ/pZの要素である乱数要素ξ５０６を生成し、i番目のユーザの識別子θ５０４に対応する秘密鍵skey(i,θ)５０８を、下記式に基づいて生成し、出力する。
skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])
=(g[i]γ (yΠi=1mh[i]θ[i])ξ,g'ξ,h[m+1]ξ,...,h[L]ξ)【００１１】
図１４に、文献２における鍵導出装置を示す。鍵導出装置６００には、ユーザ番号i５０７、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)５０８、(skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])、及び、識別子θ５０４(θ=(θ[1],...,θ[m]))が入力される。また、乱数６０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*６０１とが入力される。ここで、θ[m+1]∈Z/pZとする。【００１２】
鍵導出装置６００は、乱数６０２より、Z/pZの要素である乱数要素λ６０３を生成し、下位識別子θ*６０１に対応する下位秘密鍵skey(i,θ*)６０４を、下記式に基づいて生成し、出力する。
skey(i,θ*)=(d[i,θ*,0],d[i,θ*,1],d[i,θ*,m+1],...,d[i,θ*,L])
=((d[i,θ,0] (g[3](Πi=1m h[i]θ[i])d[i,θ,m+1])θ[m+1]λ
,d[i,θ,1] gλ,d[i,θ,m+2] h[m+2]λ,...,d[i,θ,L] h[L]λ)
ここで、ξ+λを乱数要素とみなせば、鍵生成装置５００で、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。【００１３】
図１５に、文献２における暗号化装置を示す。暗号化装置７００には、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、乱数７０２、識別子θ５０４(θ=(θ[1],...,θ[m]))、及び、ユーザ番号集合S７０１(S⊂{1,...,N})が入力される。暗号化装置７００は、乱数７０２よりZ/pZの要素τを生成し、共有鍵K７１０(K∈GT)、及び、暗号文ciph(S,θ)７０３を、以下のように生成し、出力する。
K=e(g[1],g[N])τ
ciph(S,θ)=(c_0,c_1,c_2)=((vΠj∈S g[N+1-j])τ,gτ,(y Πi=1m h[i]θ[i])τ)【００１４】
図１６に、文献２における復号装置を示す。復号装置８００には、ユーザ番号i５０７、識別子θ５０４(θ=(θ[1],...,θ[m])、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、及び、秘密鍵skey(i,θ)５０８(skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])が入力される。また、i∈Sなるユーザ番号集合S７０１、暗号文ciph(S,θ)７０３(ciph(S,θ)=(c[0],c[1],c[2])が入力される。復号装置８００は、共有鍵K７１０を、以下のように復元して出力する。
K=(e(c[0],g[i])e(c[2],d[i,θ,1])/e(c[1],d[i,θ,0]Πj ∈S,j≠Ig[N+1-j+i])【００１５】
ところで、文献３には、双線形写像を持つ楕円曲線についての記載がある。文献３に挙げられている双線形写像を持つ楕円曲線は、次のような性質を持つ。ある位数pの三個の巡回群G、G'、GTが構成可能で、G掛けるG'からGTへの計算が効率的な非縮退な双線形写像eがある。ここで、双線形であるとは、全てのα,β∈Z/pZ、及び、g∈G、g'∈G'に対して、e(gα,hβ)=e(g,g')αβが成り立つことである。また、非縮退であるとは、gがGの生成元であり、g'がG'の生成元であるとき、e(g,g')が、GTの生成元となるということである。更に、トレース写像ψがあり、これは、G'からGへの効率的に計算可能な同型写像となっている。しかも、ψの逆を計算することは困難である。
【文献１】
【００１６】
Xavier Boyen, Brent Waters: Anonymous Hierarchical Identity- Based Encryption (Without Random Oracles). Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, Lecture Notes in Computer Science 4117, pp.290-307, Springer,2006,isbn 3-540-37432-9.
【文献２】
【００１７】
Nuttapong Attrapadung, Jun Furukawa, Hideki Imai: Forward-Secure and Searchable Broadcast Encryption with Short Ciphertexts and Private Keys. Advances in Cryptology - ASIACRYPT 2006, 12th International Conferenc on the Theory and Application of Cryptology and Information Security, Shanghai, China, December 3-7, 2006, Proceedings, Lecture Notes in Computer Science 4284,pp.161-177, Springer, 2006, isbn 3-540-49475-8.
【文献３】
【００１８】
Atsuko Miyaji, Masaki Nakabayashi, Shunzo Takano: Characterization of Elliptic Curve Traces under FR-Reduction. Information Security and Cryptology - ICISC 2000, Third International Conference, Seoul, Korea, December 8-9, 2000, Proceedings, pp. 90-108. Lecture Notes in Computer Science 2015, Springer,2001 年isbn 3-540-41782-6.
【００１９】
文献１では、暗号文が、(C[0],c[1],c[2])=(M e(g[2],y)τ,g[1]τ,(g[3] Πi=1m h[i]θ[i])τ)という形をしており、これが識別子θに対する暗号文であることを確認するには、e(g[1],c[2])=e(c[1],g[3] Πi=1m h[i]θ[i]))が成り立つことを確認すれば良かった。また、文献２では、暗号文が、(c_0,c_1,c_2)=((v Πj∈S g[N+1-j])τ,gτ,(y Πi=1m h[i]θ[i])τ)という形をしており、これが識別子θに対する暗号文であることを確認するには、やはり、e(g[1],c[2])=e(c[1],g[3] Πi=1m h[i]θ[i]))が成り立つことを確認すれば良かった。このように、暗号文がどの識別子に対して生成されたのであるかを確認することができるのは、何れの方式でも、g[3]や、強い階層要素h[1],...,h[L]が公開鍵に含まれていること、及び、これらの値と暗号文の成分c[1],c[2]との双線形写像eによる像が計算できたからである。
【００２０】
一方で、匿名性のある識別子に基づく暗号方式が存在すれば、キーワードサーチ可能な暗号方式が存在することが知られている。キーワードサーチ可能な暗号方式とは、暗号文の受信者が、暗号文が特定のキーワードを暗号化したものであるか否かを調べることができる鍵を第三者に委託し、この第三者が、暗号文を委託されたキーワードの暗号文であるか否かを調べることができる方式である。このとき、委託された第三者は、キーワードが何であるかを知ることができない方式が求められる。これは、メールサーバーがキーワードサーチの鍵を委託され、例えば「緊急」というキーワードを暗号化したものを見つけたときに、利用者に特別な手段で伝達する方法に使える。ただし、このキーワードの鍵が「緊急」という検索単語を発見できるということが分からない方が、より匿名性の高いシステムとなる。
【００２１】
上記のようなキーワードサーチが可能な暗号方式を構成したとき、検索単語が具体的に何の単語か分からないということが、基となる識別子に基づく暗号方式においては、暗号文がどの識別子に対して生成されたかを隠すことに相当する。よって、暗号文がどの識別子に対して生成されたかを隠すことが可能になれば、上記キーワードサーチの可能な暗号方式、階層的暗号方式、放送型暗号方式が可能となるが、従来技術はこのような用途には使えないという問題がある。
【発明の概要】
【００２２】
本発明は、上記従来技術の問題点を解消し、暗号文が、どの識別子に対応する暗号文であるかを隠すことができる暗号化方式における鍵生成装置、鍵導出装置、暗号化装置、復号装置、方法、及び、プラグラムを提供することを目的とする。
【００２３】
上記目的を達成するために、本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成することを特徴とする鍵生成装置を提供する。
【００２４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力し、前記下位識別子に対応した下位秘密鍵を生成する鍵導出装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成することを特徴とする鍵導出装置を提供する。
【００２５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、前記メッセージの暗号文を生成する暗号化装置であって、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置を提供する。
【００２６】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、前記暗号文に対応するメッセージを出力する復号装置であって、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置を提供する。
【００２７】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成することを特徴とする鍵生成装置を提供する。
【００２８】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力し、前記下位識別子に対応する秘密鍵を生成する鍵導出装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成することを特徴とする鍵導出装置を提供する。
【００２９】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、暗号文と共通鍵とを生成する暗号化装置であって、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置を提供する。
【００３０】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、共有鍵を出力する復号装置であって、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力し、前記群Gと群G'から群GT への双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置を提供する。
【００３１】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法を提供する。
【００３２】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法を提供する。
【００３３】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、暗号文を生成する方法であって、前記コンピュータに、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成するステップを有することを特徴とする暗号化方法を提供する。
【００３４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、メッセージを生成する方法であって、前記コンピュータに、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めるステップとを有することを特徴とする復号方法を提供する。
【００３５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、前記コンピュータに、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法を提供する。
【００３６】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法を提供する。
【００３７】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵と暗号文とを生成する方法であって、前記コンピュータに、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成するステップとを有することを特徴とする暗号化方法を提供する。
【００３８】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵を生成する方法であって、前記コンピュータに、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし、前記群Gと群G'から群GT への双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めるステップとを有することを特徴とする復号方法を提供する。
【００３９】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成る処理とを実行させることを特徴とするプログラムを提供する。
【００４０】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４１】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、暗号文を生成する処理を実行させるプログラムであって、前記コンピュータに、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４２】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、メッセージを生成する処理を実行させるプログラムであって、前記コンピュータに、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とするプログラムを提供する。
【００４３】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力する処理と、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵と暗号文とを生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成する処理を実行させることを特徴とする。
【００４６】
本発明のプログラムは、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし,前記群Gと群G'から群GT への双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とする。
【００４７】
従来の技術における問題点を解決するためには、暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれにようすることで幾分達成できる。なお、ここでは、双線形写像を計算できるという意味で「強い」と修飾して呼んでいる。そこで、本発明では、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、これを公開鍵に含まないようにした。このようにすることで、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち、秘密鍵の保持者以外の者は判別できないという効果が得られる。しかしながら、これだけでは、一つの秘密鍵からその下位秘密鍵を計算することができなくなる。従来の方法では、これに階層要素を使ったのであるが、上記のように異なる双線形写像を単純に使った場合、これには秘密階層要素が必要となるからである。そこで、本発明では、秘密鍵を生成するときに使う乱数要素をもう一つ用意し、これで秘密階層要素をべき乗した値を追加した。この追加された値（べき乗された秘密階層要素）を用いることで、下位秘密鍵の導出が可能になるプログラムを提供する。
【００４８】
本発明の上記、及び、他の目的、特徴及び利益は、図面を参照する以下の説明により明らかになる。
【図面の簡単な説明】
【００４９】
【図１】本発明の第１実施形態に係る鍵生成装置を示すブロック図。
【図２】本発明の第１実施形態に係る鍵導出装置を示すブロック図。
【図３】本発明の第１実施形態に係る暗号化装置を示すブロック図。
【図４】本発明の第１実施形態に係る復号装置を示すブロック図。
【図５】本発明の第２実施形態に係る鍵生成装置を示すブロック図。
【図６】本発明の第２実施形態に係る鍵導出装置を示すブロック図。
【図７】本発明の第２実施形態に係る暗号化装置を示すブロック図。
【図８】本発明の第２実施形態に係る復号装置を示すブロック図。
【図９】文献１における鍵生成装置を示すブロック図。
【図１０】文献１における鍵導出装置を示すブロック図。
【図１１】文献１における暗号化装置を示すブロック図。
【図１２】文献１における復号装置を示すブロック図。
【図１３】文献２における鍵生成装置を示すブロック図。
【図１４】文献２における鍵導出装置を示すブロック図。
【図１５】文献２における暗号化装置を示すブロック図。
【図１６】文献２における復号装置を示すブロック図。
【発明を実施するための最良の形態】
【００５０】
本発明の実施形態の説明に先立って、本発明の実施形態の説明に用いる記法について説明する。pを素数、GとG'とGTを位数pの巡回群、eをG掛けるG'からGTへの非縮退な双線形写像であるとする。ここで双線形であるとは、全てのα,β∈Z/pZ、及び、g∈G、g'∈G'に対して、e(gα,hβ)=e(g,g')αβが成り立つことである。また、非縮退であるとは、gがGの生成元であり、g'がG'の生成元であるとき、e(g,g')が、GTの生成元となるということである。ψをG'からGへの効率的に計算可能な同型写像とする。ψの逆を計算することは困難である場合を仮定している。なお、このような群は、非特許文献３で知られている。Lは階層の最大深さを表す。a^bはabの別の表記である。【００５１】
以下、図面を参照し、本発明の実施の形態について詳細に説明する。図１は、本発明の第１実施形態に係る鍵生成装置の構成を示している。この鍵生成装置９００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（９０６ａ）、乱数要素生成部２（９０６ｂ）、秘密鍵生成部９１０ａ、秘密階層要素生成部９１０ｂ、及び、位数群生成部９０９を含む。秘密鍵生成部１０１０ａ、秘密階層生成部１０１０ｂは、必要に応じて、位数群生成部を呼び出して位数群を生成させる。なお、本実施形態及び以下の実施形態において、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。また、以下の説明では、乱数要素生成部１及び２（例えば９０６ａ、９０６ｂ）によって生成される乱数には、それぞれ生成部の符号を付して、乱数９０６ａ、９０６ｂなどとして区別する。他の実施形態においても同様な表記法を採用する。鍵生成装置９００には、公開鍵９０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y')、及び、マスター鍵９０３(x',g'[3],(h'[1],...,h'[L]))が入力される。Lを階層数、(h[1],...,h[L])を階層要素９０２、(h'[1],...,h'[L])を秘密階層要素９１１と呼ぶ。g'[1],g'[2],g'[3],h'[1],...,h'[L]は、G'の要素であり、あるZ/pZの元α に対して、y'=g'[1]α,x'=g'[2]αが成り立ち、g[1]=ψ(g'[1]),g[2]=ψ(g'[2]),g[3]=ψ(g'[3]),(h[i])i=1,...,L=(ψ(h'[i]))i=1,...,Lが成り立つとする。【００５２】
また、鍵生成装置９００には、乱数９０５と、識別子θ９０４(θ=(θ[1],...,θ[m])∈(Z/pZ)mが入力される。鍵生成装置９００は、乱数９０５より、Z/pZの要素である２つの乱数要素（乱数要素ξ９０６ａ、乱数要素ζ９０６ｂ）を生成し、識別子θ９０４に対応する秘密鍵skey(θ)９０８を、以下のように生成し、出力する。
skey(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],..., d'[θ,L],e'[θ,0],e'[θ,1],e'[θ,m+1],...,e'[θ,L])  =(x'(g'[3]Πi=1m  h'[i]θ[i])ξ,g'[1]ξ,h'[m+1]ξ,...,h'[L]ξ,(g'[3] Πi=1m  h'[i]θ[i])ζ,g'[1]ζ,h'[m+1]ζ,...,h'[L]ζ)【００５３】
上記式を参照すると、秘密鍵skey(θ)９０８は、乱数要素ξ９０６ａでべき乗された要素と、乱数要素ζ９０６ｂでべき乗された要素とを有する。このうち、乱数要素ξ９０６ａでべき乗された要素は、非特許文献１の鍵生成装置１００（図９）における「(x(g[3]Πi=1m  h[i]θ[i])ξ,g[1]ξ,h[m+1]ξ,...,h[L]ξ)」に対応する。一方、乱数要素ζ９０６ｂでべき乗された要素(g'[3] Πi=1m  h'[i]θ[i])ζ、及び、g'[1]ζ,h'[m+1]ζ, ...,h'[L]ζは、べき乗された秘密階層要素９１２であり、非特許文献１では存在しない要素である。【００５４】
図２に、鍵導出装置を示す。鍵導出装置１０００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１００３ａ）、乱数要素生成部２（１００３ｂ）、秘密鍵生成部１０１０ａ、秘密階層要素生成部１０１０ｂ、及び、位数群生成部１００９を含む。秘密鍵生成部１０１０ａ、秘密階層生成部１０１０ｂは、必要に応じて、位数群生成部１００９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵導出装置１０００には、公開鍵９０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y')、秘密鍵skey(θ)９０８(skey(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],..., d'[θ,L],e'[θ,0],e'[θ,1],e'[θ,m+1],...,e'[θ,L])、及び、識別子θ９０４(θ=(θ[1],...,θ[m])が入力される。秘密鍵skey(θ)９０８は、鍵生成装置９００（図１）にて生成されたものである。鍵導出装置１０００には、上記に加えて、乱数１００２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1]なる下位識別子θ*１００１とが入力される。ここで、θ[m+1]∈Z/pZとする。【００５５】
鍵導出装置１０００は、乱数１００２より、Z/pZの要素である２つの乱数要素（乱数要素λ１００３ａ、乱数要素ν１００３ｂを生成し、下位識別子θ*１００１に対応する下位秘密鍵skey(θ*)１００４を、以下のように生成し、出力する。
skey(θ*)=(d'[θ*,0],d'[θ*,1],d'[θ*,m+1],...,d'[θ*,L],e'[θ*,0],e'[θ*,1], e'[θ*,m+1],...,e'[θ*,L])
=(d'[θ,0] e'[θ,0]λ)(d'[θ,m+1] e'[θ,m+1]λ)θ[m+1],d'[θ,1] e'[θ,1]λ,d'[θ,m+2] e'[θ,m+2]λ,...,d'[θ,L] e'[θ,L]λ,(e'[θ,0] e'[θ,m+1]λ)ν,e'[θ,1]ν,e'[θ,m+2]ν,...,e'[θ,L]ν)
下位秘密鍵skey(θ*)において、乱数要素ν１００３ｂを用いて生成された(e'[θ,0] e'[θ,m+1]λ)ν,e'[θ,1]ν,e'[θ,m+2]ν,...,e'[θ,L]νは、下位のべき乗された秘密階層要素９１３である。ここで、「ξ+λζ」、「ζν」を２つの乱数要素とみなせば、上記鍵生成装置９００において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。【００５６】
図３に、暗号化装置を示す。暗号化装置１１００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１１０３、暗号化部１１１０、及び、位数群生成部１１０９を含む。暗号化部１１１０は、必要に応じて、位数群生成部１１０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。暗号化装置１１００には、公開鍵９０１(L,g[1], g[2],g[3],(h[1],...,h[L]),y')、乱数１１０２、メッセージM１１０１（M∈GT）、及び、識別子θ９０４（θ=(θ[1],...,θ [m])が入力される。暗号化装置１１００は、乱数１１０２より、Z/pZの要素であるτを生成し、暗号文ciph(θ,M)１１０３を、以下のように生成し、出力する。
ciph(θ,M)=(C[0],c[1],c[2])=(M e(g[2],y')τ,g[1]τ,(g[3] Πi=1m  h[i]θ[i])τ)【００５７】
図４に、復号装置を示す。復号装置１２００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、復号化部１２１０、及び、位数群生成部１２０９を含む。復号化部１２１０は、必要に応じて、位数群生成部１２０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。復号装置１２００には、公開鍵９０１(L,g[1], g[2],g[3],(h[1],...,h[L]),y')、秘密鍵skey(θ)９０８(seky(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],...,d'[θ,L],e'[θ,0],e'[θ,1], e'[θ,m+1],...,e'[θ,L])、及び、識別子θ９０４(θ=(θ[1],...,θ[m])が入力される。秘密鍵skey(θ)９０８は、鍵生成装置９００（図１）にて生成されたものである。【００５８】
復号装置１２００には、上記に加えて、暗号文ciph(θ,M)１１０３(ciph(θ,M)=(C[0],c[1],c[2])が入力される。復号装置１２００は、メッセージM１１０１を、次のように復元して出力する。
M=C[0] {e(c[2],d'[θ,1])/e(c[1],d'[θ,0])}【００５９】
本実施形態では、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、秘密階層要素が公開鍵９０１に含まれないようにする。暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれないようにすることで、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち秘密鍵skey(θ)９０８の保持者以外の者が判別することができなくなるという効果が得られる。また、本実施形態では、秘密鍵skey(θ)９０８が、秘密階層要素を乱数要素ζ９０６ｂでべき乗した“べき乗された秘密階層要素９１２”を含む。このようにすることで、鍵導出装置１０００にて、下位識別子θ*１００１に対応した下位秘密鍵１００４の導出が可能となる。【００６０】
本実施形態で説明した暗号化方式を用いることにより、以下に説明するように、キーワード検索が可能な暗号化方式が構成できる。すなわち、ある識別子に対応する秘密鍵の所持者は、その下位の識別子に属する秘密鍵を生成し、第三者に渡す。この下位の識別子は、識別子に対して、検索したいキーワードを追加したものである。上記説明では、追加されたキーワードはθ[m+1]に対応する。暗号文を生成するものが、キーワードθ[m+1]を暗号として、一の暗号文を前記下位の識別子に対応して暗号化したものを選ぶ。この暗号文が、前記下位の識別子に対応したものであることは、本発明の性質から判別しない。下位の識別子に属する秘密鍵を有する第三者だけは、これを復号して一の暗号文であることを知りうる。しかしながら、第三者は、他のキーワードに対する暗号文を判別することはできない。すなわち、本発明を用いれば、利用者は、自身宛の特別なキーワードの暗号文のみを検索する手段を、第三者に委託することが可能になる。このようなキーワード検索可能な暗号方式を用いれば、メールサーバに対して、自分に宛てられた暗号文のサブジェクトに、“重要”等のあらかじめ指定したキーワードが存在する暗号文が届いたときのみ通知することを要請できる。また、“広告”のようなキーワードがある場合は配信せずに抹消することを委託できる。このとき、メールサーバは、どのようなキーワードが登録されているか知ることができない。【００６１】
図５は、本発明の第２実施形態に係る鍵生成装置の構成を示している。鍵生成装置１３００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１３０６ａ）、乱数要素生成部２（１３０６ｂ）、秘密鍵生成部１３１０ａ、秘密階層要素生成部１３１０ｂ、及び、位数群生成部１３０９を含む。秘密鍵生成部１３１０ａ、秘密階層生成部１３１０ｂは、必要に応じて、位数群生成部１３０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵生成装置１３００には、公開鍵１３０１（(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、及び、マスター鍵１３０３(γ,v',y',(h'[1],...,h'[L]))が入力される。Lを階層数、(h[1],...,h[L])を階層要素１３０２、(h'[1],...,h'[L])を秘密階層要素１３１１と呼ぶ。g',y',h'[1],...,h'[L]は、G'の要素であり、あるZ/pZの元α,γに対して、(g'[i])i=1,...,2N=(g'^(α^i))i=1,...,2N、v'= g'γ、g=ψ(g')、y=ψ(y')、v=ψ(v')、(g[i])i=1,...,2N=(ψ(g'[i]))i=1,...,2N、(h[i])i=1,...,L=(ψ(h'[i]))i=1,...,Lが成り立つとする。【００６２】
鍵生成装置１３００には、上記に加えて、乱数１３０５と、識別子θ１３０４(θ=(θ[1],...,θ[m])∈(Z/pZ)m)と、ユーザ番号i１３０７とが入力される。鍵生成装置１３００は、乱数１３０５より、Z/pZの要素である２つの乱数要素（乱数要素ξ１３０６ａ、乱数要素ζ１３０６ｂ）を生成し、i番目のユーザ（ユーザ番号ｉ１３０７）の識別子θ１３０４に対応する秘密鍵skey(i,θ)１３０８を、以下のように生成し、出力する。
skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L], e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])
=(g'[i]γ  (y' Πi=1m  h'[i]θ[i])ξ,g'ξ,h'[m+1]ξ,...,h'[L]ξ,(y' Πi=1m  h'[i]θ[i])ζ,g'ζ,h'[m+1]ζ,...,h'[L]ζ)【００６３】
上記式を参照すると、秘密鍵skey(i,θ)１３０８は、乱数要素ξ１３０６ａでべき乗された要素と、乱数要素ζ１３０６ｂでべき乗された要素とを有する。このうち、乱数要素ξ１３０６ａでべき乗された要素は、非特許文献２の鍵生成装置５００（図１３）で生成さされる秘密鍵skey(i,θ)５０８「g[i]γ  (yΠi=1mh[i]θ[i])ξ,g'ξ,h[m+1]ξ,...,h[L]ξ」に対応する。一方、乱数要素ζ１３０６ｂでべき乗された要素(y'Π i=1m  h'[i]θ[i])ζ、及び、g'ζ,h'[m+1]ζ,...,h'[L]ζは、べき乗された秘密階層要素１３１２であり、非特許文献２にはなかったものである。【００６４】
図６に、鍵導出装置を示す。鍵導出装置１４００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１４０３ａ）、乱数要素生成部２（１４０３ｂ）、秘密鍵生成部１４１０ａ、秘密階層要素生成部１４１０ｂ、及び、位数群生成部１４０９を含む。秘密鍵生成部１４１０ａ、秘密階層生成部１４１０ｂは、必要に応じて、位数群生成部１４０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵導出装置１４００には、ユーザ番号ｉ１３０７、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)１３０８（skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L],e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])、及び、識別子θ１３０４(θ=(θ[1],...,θ[m]))が入力される。また、鍵導出装置１４００には、乱数１４０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*１４０１とが入力される。ここで、θ[m+1]∈Z/pZとする。【００６５】
鍵導出装置１４００は、乱数１４０２より、Z/pZの要素である２つの乱数要素（乱数要素λ１４０３ａ及び乱数要素ν１４０３ｂを生成し、下位識別子θ*１４０１に対応する下位秘密鍵skey(i,θ*)１４０４を、以下のように生成し、出力する。
skey(i,θ*)=(d'[i,θ*,0],d'[i,θ*,1],d'[i,θ*,m+1],...,d'[i,θ*,L],e'[i,θ*,0],e'[i,θ*,1],e'[i,θ*,m+1],...,e'[i,θ*,L])
=((d'[i,θ,0] e'[i,θ,0]λ) (d'[i,θ,m+1] e'[θ,m+1]λ)θ[m+1],d'[i,θ,1] e'[i,θ,1]λ,d'[i,θ,m+2] e'[i,θ,m+2]λ,...,d'[i,θ,L] e'[i,θ,L]λ,(e'[i,θ,0] e'[i,θ,m+1]λ)ν,e'[i,θ,1]ν,e'[i,θ,m+2]ν,...,e'[i,θ,L]ν)）
乱数要素νを用いて生成された
(e'[i,θ,0] e'[i,θ,m+1]λ)ν,e'[i,θ,1]ν, e'[i,θ,m+2]ν, ...,e'[i,θ,L]ν
は、下位のべき乗された秘密階層要素１３１３である。ここで、「ξ+λζ」、「ζν」を二つの乱数要素とみなせば、鍵生成装置１３００（図５）において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できる事が重要である。【００６６】
図７に、暗号化装置を示す。暗号化装置１５００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１５０３、暗号化部１５１０、及び、位数群生成部１５０９を含む。暗号化部１５１０は、必要に応じて、位数群生成部１５０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。暗号化装置１５００には、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N], g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、乱数１５０２、識別子θ１３０４（θ=(θ[1],...,θ[m])、及び、ユーザ番号集合S１５０１（S⊂{1,...,N}）が入力される。暗号化装置１５００は、乱数１５０２より、Z/pZの要素τを生成し、共有鍵K１５１０(K∈GT)、及び、暗号文ciph(S,θ)１５０３を、以下のように生成し、出力する。
K=e(g[1],g'[N])τ
ciph(S,θ)=(c_0,c_1,c_2)=((v Πj∈S g[N+1-j])τ, gτ,(y Πi=1m  h[i]θ[i])τ)）【００６７】
図８に、復号装置を示す。復号装置１６００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、復号化部１６１０、及び、位数群生成部１６０９を含む。秘密鍵生成部１３１０ａ、復号化部１６１０は、必要に応じて、位数群生成部１６０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。復号装置１６００には、ユーザ番号i１３０７、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)１３０８(skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L],e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])、及び、識別子θ１３０４（θ=(θ[1],...,θ[m])）が入力される。また、i∈Sなるユーザ番号集合S１５０１と、暗号文ciph(S,θ)１５０３(ciph(S,θ)=(c[0],c[1],c[2]))が入力される。復号装置１６００は、共有鍵K１５１０を、次のように復元して出力する。
K=(e(c[0],g'[i]) e(c[2],d'[i,θ,1]) / e(c[1],d'[i,θ,0] Πj∈S, j≠ig'[N+1-j+i])【００６８】
本実施形態においても、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、秘密階層要素が公開鍵１３０１に含まれないようにする。暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれないようにするとで、第１実施形態と同様に、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち秘密鍵skey(i,θ)１３０８の保持者以外の者が判別することができなくなるという効果が得られる。また、本実施形態では、秘密鍵skey(i,θ)１３０８が、秘密階層要素を乱数要素ζ１３０６ｂでべき乗したべき乗された秘密階層要素１３１２を含む。このようにすることで、鍵導出装置１４００にて、下位識別子θ*１４０１に対応した下位秘密鍵１４０４の導出が可能となる。【００６９】
本発明では、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTを考えたとき、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素との双線形写像がとれる要素を秘密階層要素とし、これを公開鍵に含めないようにする。このようにすることで、暗号文から、暗号化に用いた識別子が判別しないようにすることができる。また、本発明では、乱数要素を２つ用意して、秘密鍵に、秘密階層要素を２つの乱数でべき乗した要素を含める。このようにすることで、秘密鍵から、下位秘密鍵を導出することが可能となる。【００７０】
以上、本発明をその好適な実施形態に基づいて説明したが、本発明の鍵生成装置、鍵導出装置、暗号化装置、復号装置、方法、及び、プログラムは、上記実施形態にのみ限定されるものではなく、上記実施形態の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。【００７１】
本出願は、２００７年２月１３日出願に係る日本特許出願２００７−０３２６０２号を基礎とし且つその優先権を主張するものであり、引用によってその開示の内容の全てを本出願の明細書中に加入する。
【産業上の利用可能性】
【００７２】
本発明は、匿名性を有する階層的な識別子に基づく暗号化方式において、キーワード検索が可能な暗号化方式に適用することができる。
【図１】
2008099831.tif 000003
【図２】
2008099831.tif 000004
【図３】
2008099831.tif 000005
【図４】
2008099831.tif 000006
【図５】
2008099831.tif 000007
【図６】
2008099831.tif 000008
【図７】
2008099831.tif 000009
【図８】
2008099831.tif 000010
【図９】
2008099831.tif 000011
【図１０】
2008099831.tif 000012
【図１１】
2008099831.tif 000013
【図１２】
2008099831.tif 000014
【図１３】
2008099831.tif 000015
【図１４】
2008099831.tif 000016
【図１５】
2008099831.tif 000017
【図１６】
2008099831.tif 000018
【手続補正書】
【提出日】平成21年10月13日(2009.10.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】  明細書
【発明の名称】鍵生成装置、鍵導出装置、暗号化装置、復号化装置、方法、及び、プログラム
【技術分野】
【０００１】
本発明は、鍵生成装置、鍵導出装置、暗号化装置、及び、復号化装置に関する。更に詳しくは、本発明は、匿名性を有する階層的な識別子に基づく暗号化方式における鍵生成装置、鍵導出装置、暗号化装置、及び、復号化装置、並びに、これらに用いられる方法、及び、プログラムに関する。
【背景技術】
【０００２】
従来の匿名性のある階層的な識別子に基づく暗号化方式について説明する。なお、以下の説明では、pを素数、GとGTを位数pの巡回群、eをG掛けるGからG への非縮退な双線形写像であるとする。ここで、双線形であるとは、全てのα,β∈Z/pZ（Zは整数の集合）、及び、g∈Gに対して、e(gα,hβ)=e(g,g)αβが成り立つことである。また、非縮退であるとは、gがGの生成元であるとき、e(g,g)が、GTの生成元となるということである。Lは階層の最大深さを表す。a^bはabの別の表記である。
【０００３】
従来の匿名性のある階層的な識別子に基づく暗号方式として、文献１に挙げられる方式がある。図９に、文献１における鍵生成装置を示す。鍵生成装置１００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、及び、マスター鍵１０３(x,g[3])が入力される。Lを階層数と呼び、(h[1],...,h[L])を強い階層要素１０２と呼ぶ。g[1],g[2],g[3],h[1],...,h[L]はGの要素であり、あるZ/pZの元αに対して、y=g[1]α、x=g[2]αが成り立つように生成されている。
【０００４】
鍵生成装置１００には、更に、乱数１０５と、識別子θ１０４(θ＝(θ[1],...,θ[m])∈(Z/pZ)m)が入力される。鍵生成装置１００は、乱数１０５より、Z/pZの要素である乱数要素ξ１０６を生成し、識別子θ１０４に対応する秘密鍵skey(θ)１０８を、下記式に基づいて生成し、出力する。
skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])
=(x(g[3]Πi=1m h[i]θ[i])ξ,g[1]ξ,h[m+1]ξ,...,h[L]ξ)
【０００５】
図１０に、文献１における鍵導出装置２００を示す。鍵導出装置２００には、識別子θ１０４(θ=(θ[1],...,θ[m])、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、及び、秘密鍵skey(θ)１０８(skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])が入力される。また、乱数２０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*２０１とが入力される。ここで、θ[m+1]∈Z/pZとする。
【０００６】
鍵導出装置２００は、乱数２０２よりZ/pZの要素である乱数要素λ２０３を生成し、下位識別子θ*２０１に対応する下位秘密鍵skey(θ*)２０４を、下記式に基づいて生成し、出力する。
skey(θ*)=(d[θ*,0],d[θ*,1],d[θ*,m+1],...,d[θ*,L])
=(d[θ,0] (g[3](Πi=1m h[i]θ[i])d[θ,m+1]θ[m+1])λ)
,d[θ,1] gλ,d[θ,m+2] h[m+2]λ,...,d[θ,L] h[L]λ) 
ここで、ξ+λを乱数要素とみなせば、鍵生成装置１００において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。
【０００７】
図１１に、文献１における暗号化装置を示す。暗号化装置３００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)と、乱数３０２と、メッセージM３０１(M∈GT)と、識別子θ１０４(θ=(θ[1],...,θ [m])とが入力される。暗号化装置３００は、乱数３０２よりZ/pZの要素であるτを生成し、暗号文ciph(θ,M)３０３を、下記式に基づいて生成し、出力する。
ciph(θ,M)=(C[0],c[1],c[2])=(M e(g[2],y)τ,g[1]τ,(g[3] Πi=1m h[i]θ[i])τ)
【０００８】
図１２に、文献１における復号装置を示す。復号装置４００には、公開鍵１０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y)、秘密鍵skey(θ)１０８、(skey(θ)=(d[θ,0],d[θ,1],d[θ,m+1],...,d[θ,L])、及び、識別子θ１０４(θ=(θ[1],...,θ[m])が入力される。また、暗号文ciph(θ,M)３０３(ciph(θ,M)=(C[0],c[1],c[2])が入力される。復号装置４００は、メッセージM３０１を、以下のように復元して出力する。
M=C[0]｛e(c[2],d[θ,1])/e(c[1],d[θ,0])}
【０００９】
従来の匿名性のある階層的な識別子に基づく放送暗号方式として、文献２に挙げられる方式がある。図１３に、文献２における鍵生成装置を示す。鍵生成装置５００は、入力手段、出力手段、及び、計算手段を備えている（図示せず）。鍵生成装置５００には、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、及び、マスター鍵５０３(γ,v',y')が入力される。Lを階層数と呼び、(h[1],...,h[L])を強い階層要素５０２と呼ぶ。g,y,h[1],...,h[L]はGの要素であり、ある Z/pZの元α,γに対して、(g'[i])i=1,...,2N=(g^(α^i))i=1,...,2N、v=gγが成り立つように生成されている。
【００１０】
鍵生成装置５００には、更に、乱数５０５と、識別子θ５０４(θ=(θ[1],...,θ[m])∈(Z/pZ)m)と、ユーザ番号i５０７とが入力される。鍵生成装置５００は、乱数５０５よりZ/pZの要素である乱数要素ξ５０６を生成し、i番目のユーザの識別子θ５０４に対応する秘密鍵skey(i,θ)５０８を、下記式に基づいて生成し、出力する。
skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])
=(g[i]γ (yΠi=1mh[i]θ[i])ξ,g'ξ,h[m+1]ξ,...,h[L]ξ)
【００１１】
図１４に、文献２における鍵導出装置を示す。鍵導出装置６００には、ユーザ番号i５０７、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)５０８、(skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])、及び、識別子θ５０４(θ=(θ[1],...,θ[m]))が入力される。また、乱数６０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*６０１とが入力される。ここで、θ[m+1]∈Z/pZとする。
【００１２】
鍵導出装置６００は、乱数６０２より、Z/pZの要素である乱数要素λ６０３を生成し、下位識別子θ*６０１に対応する下位秘密鍵skey(i,θ*)６０４を、下記式に基づいて生成し、出力する。
skey(i,θ*)=(d[i,θ*,0],d[i,θ*,1],d[i,θ*,m+1],...,d[i,θ*,L])
=((d[i,θ,0] (g[3](Πi=1m h[i]θ[i])d[i,θ,m+1])θ[m+1]λ
,d[i,θ,1] gλ,d[i,θ,m+2] h[m+2]λ,...,d[i,θ,L] h[L]λ)
ここで、ξ+λを乱数要素とみなせば、鍵生成装置５００で、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。
【００１３】
図１５に、文献２における暗号化装置を示す。暗号化装置７００には、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、乱数７０２、識別子θ５０４(θ=(θ[1],...,θ[m]))、及び、ユーザ番号集合S７０１(S⊂{1,...,N})が入力される。暗号化装置７００は、乱数７０２よりZ/pZの要素τを生成し、共有鍵K７１０(K∈GT)、及び、暗号文ciph(S,θ)７０３を、以下のように生成し、出力する。
K=e(g[1],g[N])τ
ciph(S,θ)=(c[0]c[1]c[2])=((vΠj∈Sg[N+1-j])τ,gτ,(y Πi=1m h[i]θ[i])τ)
【００１４】
図１６に、文献２における復号装置を示す。復号装置８００には、ユーザ番号i５０７、識別子θ５０４(θ=(θ[1],...,θ[m])、公開鍵５０１(L,N,p,g,g[1],...,g[N],g[N+2],...,g[2n],h[1],...,h[L],v,y)、及び、秘密鍵skey(i,θ)５０８(skey(i,θ)=(d[i,θ,0],d[i,θ,1],d[i,θ,m+1],...,d[i,θ,L])が入力される。また、i∈Sなるユーザ番号集合S７０１、暗号文ciph(S,θ)７０３(ciph(S,θ)=(c[0],c[1],c[2])が入力される。復号装置８００は、共有鍵K７１０を、以下のように復元して出力する。
K=(e(c[0],g[i])e(c[2],d[i,θ,1])/e(c[1],d[i,θ,0]Πj∈S,j≠ig[N+1-j+i])
【００１５】
ところで、文献３には、双線形写像を持つ楕円曲線についての記載がある。文献３に挙げられている双線形写像を持つ楕円曲線は、次のような性質を持つ。ある位数pの三個の巡回群G、G'、GTが構成可能で、G掛けるG'からGTへの計算が効率的な非縮退な双線形写像eがある。ここで、双線形であるとは、全てのα,β∈Z/pZ、及び、g∈G、g'∈G'に対して、e(gα,hβ)=e(g,g')αβが成り立つことである。また、非縮退であるとは、gがGの生成元であり、g'がG'の生成元であるとき、e(g,g')が、GTの生成元となるということである。更に、トレース写像ψがあり、これは、G'からGへの効率的に計算可能な同型写像となっている。しかも、ψの逆を計算することは困難である。
【００１６】
【文献１】Xavier Boyen, Brent Waters: Anonymous Hierarchical Identity-       Based Encryption (Without Random Oracles). Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, Lecture Notes in Computer Science 4117, pp.290-307, Springer,2006,isbn 3-540-37432-9.
【００１７】
【文献２】Nuttapong Attrapadung, Jun Furukawa, Hideki Imai: Forward-Secure and Searchable Broadcast Encryption with Short Ciphertexts and Private Keys. Advances in Cryptology - ASIACRYPT 2006, 12th International Conferenc on the Theory and Application of Cryptology and Information Security, Shanghai, China, December 3-7, 2006, Proceedings, Lecture Notes in Computer Science 4284,pp.161-177, Springer, 2006, isbn 3-540-49475-8.
【００１８】
【文献３】Atsuko Miyaji, Masaki Nakabayashi, Shunzo Takano: Characteri       zation of Elliptic Curve Traces under FR-Reduction. Information Security and Cryptology - ICISC 2000, Third International Conference, Seoul, Korea, December 8-9, 2000, Proceedings, pp. 90-108. Lecture Notes in Computer Science 2015, Springer,2001 年 isbn 3-540-41782-6.
【００１９】
文献１では、暗号文が、(c[0],c[1],c[2])=(M e(g[2],y)τ,g[1]τ,(g[3] Πi=1m h[i]θ[i])τ)という形をしており、これが識別子θに対する暗号文であることを確認するには、e(g[1],c[2])=e(c[1],g[3] Πi=1m h[i]θ[i]))が成り立つことを確認すれば良かった。また、文献２では、暗号文が、(c[0],c[1],c[2])=((v Πj∈Sg[N+1-j])τ,gτ,(y Πi=1m h[i]θ[i])τ)という形をしており、これが識別子θに対する暗号文であることを確認するには、やはり、e(g[1],c[2])=e(c[1],g[3] Πi=1m h[i]θ[i]))が成り立つことを確認すれば良かった。このように、暗号文がどの識別子に対して生成されたのであるかを確認することができるのは、何れの方式でも、g[3]や、強い階層要素h[1],...,h[L]が公開鍵に含まれていること、及び、これらの値と暗号文の成分c[1],c[2]との双線形写像eによる像が計算できたからである。
【００２０】
一方で、匿名性のある識別子に基づく暗号方式が存在すれば、キーワードサーチ可能な暗号方式が存在することが知られている。キーワードサーチ可能な暗号方式とは、暗号文の受信者が、暗号文が特定のキーワードを暗号化したものであるか否かを調べることができる鍵を第三者に委託し、この第三者が、暗号文を委託されたキーワードの暗号文であるか否かを調べることができる方式である。このとき、委託された第三者は、キーワードが何であるかを知ることができない方式が求められる。これは、メールサーバーがキーワードサーチの鍵を委託され、例えば「緊急」というキーワードを暗号化したものを見つけたときに、利用者に特別な手段で伝達する方法に使える。ただし、このキーワードの鍵が「緊急」という検索単語を発見できるということが分からない方が、より匿名性の高いシステムとなる。
【００２１】
上記のようなキーワードサーチが可能な暗号方式を構成したとき、検索単語が具体的に何の単語か分からないということが、基となる識別子に基づく暗号方式においては、暗号文がどの識別子に対して生成されたかを隠すことに相当する。よって、暗号文がどの識別子に対して生成されたかを隠すことが可能になれば、上記キーワードサーチの可能な暗号方式、階層的暗号方式、放送型暗号方式が可能となるが、従来技術はこのような用途には使えないという問題がある。
【発明の概要】
【００２２】
本発明は、上記従来技術の問題点を解消し、暗号文が、どの識別子に対応する暗号文であるかを隠すことができる暗号化方式における鍵生成装置、鍵導出装置、暗号化装置、復号装置、方法、及び、プラグラムを提供することを目的とする。
【００２３】
上記目的を達成するために、本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成することを特徴とする鍵生成装置を提供する。
【００２４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力し、前記下位識別子に対応した下位秘密鍵を生成する鍵導出装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成することを特徴とする鍵導出装置を提供する。
【００２５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、前記メッセージの暗号文を生成する暗号化装置であって、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置を提供する。
【００２６】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、前記暗号文に対応するメッセージを出力する復号装置であって、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置を提供する。
【００２７】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、秘密鍵を生成する鍵生成装置であって、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成することを特徴とする鍵生成装置を提供する。
【００２８】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力し、前記下位識別子に対応する秘密鍵を生成する鍵導出装置であって、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成することを特徴とする鍵導出装置を提供する。
【００２９】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力し、暗号文と共通鍵とを生成する暗号化装置であって、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成することを特徴とする暗号化装置を提供する。
【００３０】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備え、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力し、共有鍵を出力する復号装置であって、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力し、前記群Gと群G'から群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めることを特徴とする復号装置を提供する。
【００３１】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法を提供する。
【００３２】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法を提供する。
【００３３】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、暗号文を生成する方法であって、前記コンピュータに、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成するステップを有することを特徴とする暗号化方法を提供する。
【００３４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、メッセージを生成する方法であって、前記コンピュータに、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求めるステップとを有することを特徴とする復号方法を提供する。
【００３５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、秘密鍵を生成する方法であって、前記コンピュータに、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成するステップとを有することを特徴とする鍵生成方法を提供する。
【００３６】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、下位秘密鍵を生成する方法であって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成するステップとを有することを特徴とする鍵導出方法を提供する。
【００３７】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵と暗号文とを生成する方法であって、前記コンピュータに、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力するステップと、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成するステップとを有することを特徴とする暗号化方法を提供する。
【００３８】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータを用いて、共有鍵を生成する方法であって、前記コンピュータに、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力するステップと、前記コンピュータが、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし、前記群Gと群G'から群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群Gの要素を求めるステップとを有することを特徴とする復号方法を提供する。
【００３９】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵を生成る処理とを実行させることを特徴とするプログラムを提供する。
【００４０】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含む秘密鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、該２つの乱数要素のそれぞれで、前記秘密鍵に含まれるべき乗された秘密階層要素をべき乗したものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４１】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、暗号文を生成する処理を実行させるプログラムであって、前記コンピュータに、メッセージと、乱数と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を識別子で乗じたものの積とを、前記生成された乱数で乗じて暗号文の要素を生成し、前記群Gの元と群GTの元とを含み、前記群G'の元を含まない暗号文を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４２】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、メッセージを生成する処理を実行させるプログラムであって、前記コンピュータに、暗号文と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、前記秘密鍵の要素の１つと、前記暗号文の要素の１つとを入力とし、前記群Gと群G'とから群GTへの双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とするプログラムを提供する。
【００４３】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、ユーザ番号と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素を含むマスター鍵と、前記階層数と、前記秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて、所定の乱数要素を２つ発生し、前記マスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて、ユーザ番号に対応する値を生成し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４４】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、下位秘密鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、識別子と、該識別子の文字列に更に文字が追加された文字列から成る下位識別子と、前記識別子の階層構造の深さを表す変数である階層数と該階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素とを含み、かつ、前記秘密階層要素を含まない公開鍵と、２つの乱数要素のそれぞれで前記秘密階層要素をべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更にマスター鍵の一つの要素でユーザ番号に対応する公開鍵の要素を乗じて生成された前記ユーザ番号に対応した値を乗じたものを含む秘密鍵とを入力する処理と、前記コンピュータが、前記入力された乱数に基づいて所定の乱数要素を２つ発生し、前記秘密階層要素を前記２つの乱数要素のそれぞれでべき乗したものを含み、かつ、２つの乱数要素のうちの一方でべき乗した要素に更に前記ユーザ番号に対応した値を乗じたものを含む下位秘密鍵を生成する処理とを実行させることを特徴とするプログラムを提供する。
【００４５】
本発明は、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵と暗号文とを生成する処理を実行させるプログラムであって、前記コンピュータに、乱数と、ユーザ番号集合と、識別子と、該識別子の階層構造の深さを表す変数である階層数に比例する個数の群G'の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵とを入力する処理と、前記入力された乱数に基づいて所定の乱数要素を発生し、前記公開鍵の要素と、前記公開鍵の要素を前記識別子で乗じたものの積とを、前記生成された乱数要素で乗じたものを含み、前記群Gの元と群GTの元とをから成り前記群G'の元を含まない暗号文を生成する処理を実行させることを特徴とする。
【００４６】
本発明のプログラムは、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTの計算手段を備えるコンピュータに、共有鍵を生成する処理を実行させるプログラムであって、前記コンピュータに、暗号文と、ユーザ番号と、ユーザ番号集合と、識別子と、識別子の階層構造の深さを表す変数である階層数に比例する個数の群G の要素である秘密階層要素のそれぞれの値の前記同型写像による像の集合である階層要素を含み、かつ、前記秘密階層要素を含まない公開鍵と、前記秘密階層要素を二つの乱数要素でそれぞれ乗じたものを含む秘密鍵とを入力する処理と、前記秘密鍵の要素一つと前記暗号文の要素一つとを入力とし,前記群Gと群G'から群GT への双線形写像を求める計算手段を用いて、前記入力された双方の要素から群GTの要素を求める処理とを実行させることを特徴とする。
【００４７】
従来の技術における問題点を解決するためには、暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれるようにすることで幾分達成できる。なお、ここでは、双線形写像を計算できるという意味で「強い」と修飾して呼んでいる。そこで、本発明では、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、これを公開鍵に含まないようにした。このようにすることで、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち、秘密鍵の保持者以外の者は判別できないという効果が得られる。しかしながら、これだけでは、一つの秘密鍵からその下位秘密鍵を計算することができなくなる。従来の方法では、これに階層要素を使ったのであるが、上記のように異なる双線形写像を単純に使った場合、これには秘密階層要素が必要となるからである。そこで、本発明では、秘密鍵を生成するときに使う乱数要素をもう一つ用意し、これで秘密階層要素をべき乗した値を追加した。この追加された値（べき乗された秘密階層要素）を用いることで、下位秘密鍵の導出が可能になるプログラムを提供する。
【００４８】
本発明の上記、及び、他の目的、特徴及び利益は、図面を参照する以下の説明により明らかになる。
【図面の簡単な説明】
【００４９】
【図１】本発明の第１実施形態に係る鍵生成装置を示すブロック図。
【図２】本発明の第１実施形態に係る鍵導出装置を示すブロック図。
【図３】本発明の第１実施形態に係る暗号化装置を示すブロック図。
【図４】本発明の第１実施形態に係る復号装置を示すブロック図。
【図５】本発明の第２実施形態に係る鍵生成装置を示すブロック図。
【図６】本発明の第２実施形態に係る鍵導出装置を示すブロック図。
【図７】本発明の第２実施形態に係る暗号化装置を示すブロック図。
【図８】本発明の第２実施形態に係る復号装置を示すブロック図。
【図９】文献１における鍵生成装置を示すブロック図。
【図１０】文献１における鍵導出装置を示すブロック図。
【図１１】文献１における暗号化装置を示すブロック図。
【図１２】文献１における復号装置を示すブロック図。
【図１３】文献２における鍵生成装置を示すブロック図。
【図１４】文献２における鍵導出装置を示すブロック図。
【図１５】文献２における暗号化装置を示すブロック図。
【図１６】文献２における復号装置を示すブロック図。
【発明を実施するための形態】
【００５０】
本発明の実施形態の説明に先立って、本発明の実施形態の説明に用いる記法について説明する。pを素数、GとG'とGTを位数pの巡回群、eをG掛けるG'からGTへの非縮退な双線形写像であるとする。ここで双線形であるとは、全てのα,β∈Z/pZ、及び、g∈G、g'∈G'に対して、e(gα,hβ)=e(g,g')αβが成り立つことである。また、非縮退であるとは、gがGの生成元であり、g'がG'の生成元であるとき、e(g,g')が、GTの生成元となるということである。ψをG'からGへの効率的に計算可能な同型写像とする。ψの逆を計算することは困難である場合を仮定している。なお、このような群は、非特許文献３で知られている。Lは階層の最大深さを表す。a^bはabの別の表記である。
【００５１】
以下、図面を参照し、本発明の実施の形態について詳細に説明する。図１は、本発明の第１実施形態に係る鍵生成装置の構成を示している。この鍵生成装置９００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（９０６ａ）、乱数要素生成部２（９０６ｂ）、秘密鍵生成部９１０ａ、秘密階層要素生成部９１０ｂ、及び、位数群生成部９０９を含む。秘密鍵生成部９１０ａ、秘密階層生成部９１０ｂは、必要に応じて、位数群生成部を呼び出して位数群を生成させる。なお、本実施形態及び以下の実施形態において、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。また、以下の説明では、乱数要素生成部１及び２（例えば９０６ａ、９０６ｂ）によって生成される乱数には、それぞれ生成部の符号を付して、乱数９０６ａ、９０６ｂなどとして区別する。他の実施形態においても同様な表記法を採用する。鍵生成装置９００には、公開鍵９０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y')、及び、マスター鍵９０３(x',g'[3],(h'[1],...,h'[L]))が入力される。Lを階層数、(h[1],...,h[L])を階層要素９０２、(h'[1],...,h'[L])を秘密階層要素９１１と呼ぶ。g'[1],g'[2],g'[3],h'[1],...,h'[L]は、G'の要素であり、あるZ/pZの元α に対して、y'=g'[1]α,x'=g'[2]αが成り立ち、g[1]=ψ(g'[1]),g[2]=ψ(g'[2]),g[3]=ψ(g'[3]),(h[i])i=1,...,L=(ψ(h'[i]))i=1,...,Lが成り立つとする。
【００５２】
また、鍵生成装置９００には、乱数９０５と、識別子θ９０４(θ=(θ[1],...,θ[m])∈(Z/pZ)mが入力される。鍵生成装置９００は、乱数９０５より、Z/pZの要素である２つの乱数要素（乱数要素ξ９０６ａ、乱数要素ζ９０６ｂ）を生成し、識別子θ９０４に対応する秘密鍵skey(θ)９０８を、以下のように生成し、出力する。
skey(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],..., d'[θ,L],e'[θ,0],e'[θ,1],e'[θ,m+1],...,e'[θ,L])  =(x'(g'[3]Πi=1m h'[i]θ[i])ξ,g'[1]ξ,h'[m+1]ξ,...,h'[L]ξ,(g'[3] Πi=1m h'[i]θ[i])ζ,g'[1]ζ,h'[m+1]ζ,...,h'[L]ζ)
【００５３】
上記式を参照すると、秘密鍵skey(θ)９０８は、乱数要素ξ９０６ａでべき乗された要素と、乱数要素ζ９０６ｂでべき乗された要素とを有する。このうち、乱数要素ξ９０６ａでべき乗された要素は、非特許文献１の鍵生成装置１００（図９）における「(x(g[3]Πi=1m h[i]θ[i])ξ,g[1]ξ,h[m+1]ξ,...,h[L]ξ)」に対応する。一方、乱数要素ζ９０６ｂでべき乗された要素(g'[3] Πi=1m h'[i]θ[i])ζ、及び、g'[1]ζ,h'[m+1]ζ, ...,h'[L]ζは、べき乗された秘密階層要素９１２であり、非特許文献１では存在しない要素である。
【００５４】
図２に、鍵導出装置を示す。鍵導出装置１０００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１００３ａ）、乱数要素生成部２（１００３ｂ）、秘密鍵生成部１０１０ａ、秘密階層要素生成部１０１０ｂ、及び、位数群生成部１００９を含む。秘密鍵生成部１０１０ａ、秘密階層生成部１０１０ｂは、必要に応じて、位数群生成部１００９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵導出装置１０００には、公開鍵９０１(L,g[1],g[2],g[3],(h[1],...,h[L]),y')、秘密鍵skey(θ)９０８(skey(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],..., d'[θ,L],e'[θ,0],e'[θ,1],e'[θ,m+1],...,e'[θ,L])、及び、識別子θ９０４(θ=(θ[1],...,θ[m])が入力される。秘密鍵skey(θ)９０８は、鍵生成装置９００（図１）にて生成されたものである。鍵導出装置１０００には、上記に加えて、乱数１００２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1]なる下位識別子θ*１００１とが入力される。ここで、θ[m+1]∈Z/pZとする。
【００５５】
鍵導出装置１０００は、乱数１００２より、Z/pZの要素である２つの乱数要素（乱数要素λ１００３ａ、乱数要素ν１００３ｂを生成し、下位識別子θ*１００１に対応する下位秘密鍵skey(θ*)１００４を、以下のように生成し、出力する。
skey(θ*)=(d'[θ*,0],d'[θ*,1],d'[θ*,m+1],...,d'[θ*,L],e'[θ*,0],e'[θ*,1], e'[θ*,m+1],...,e'[θ*,L])
=(d'[θ,0] e'[θ,0]λ)(d'[θ,m+1] e'[θ,m+1]λ)θ[m+1],d'[θ,1] e'[θ,1]λ,d'[θ,m+2] e'[θ,m+2]λ,...,d'[θ,L] e'[θ,L]λ,(e'[θ,0] e'[θ,m+1]λ)ν,e'[θ,1]ν,e'[θ,m+2]ν,...,e'[θ,L]ν)
下位秘密鍵skey(θ*)において、乱数要素ν１００３ｂを用いて生成された(e'[θ,0] e'[θ,m+1]λ)ν,e'[θ,1]ν,e'[θ,m+2]ν,...,e'[θ,L]νは、下位のべき乗された秘密階層要素９１３である。ここで、「ξ+λζ」、「ζν」を２つの乱数要素とみなせば、上記鍵生成装置９００において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できることが重要である。
【００５６】
図３に、暗号化装置を示す。暗号化装置１１００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１１０３、暗号化部１１１０、及び、位数群生成部１１０９を含む。暗号化部１１１０は、必要に応じて、位数群生成部１１０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。暗号化装置１１００には、公開鍵９０１(L,g[1], g[2],g[3],(h[1],...,h[L]),y')、乱数１１０２、メッセージM１１０１（M∈GT）、及び、識別子θ９０４（θ=(θ[1],...,θ [m]))が入力される。暗号化装置１１００は、乱数１１０２より、Z/pZの要素であるτを生成し、暗号文ciph(θ,M)１１０３を、以下のように生成し、出力する。
ciph(θ,M)=(C[0],c[1],c[2])=(M e(g[2],y')τ,g[1]τ,(g[3] Πi=1m h[i]θ[i])τ)
【００５７】
図４に、復号装置１２００を示す。復号装置１２００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、復号化部１２１０、及び、位数群生成部１２０９を含む。復号化部１２１０は、必要に応じて、位数群生成部１２０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。復号装置１２００には、公開鍵９０１(L,g[1], g[2],g[3],(h[1],...,h[L]),y')、秘密鍵skey(θ)９０８(seky(θ)=(d'[θ,0],d'[θ,1],d'[θ,m+1],...,d'[θ,L],e'[θ,0],e'[θ,1], e'[θ,m+1],...,e'[θ,L])、及び、識別子θ９０４(θ=(θ[1],...,θ[m])が入力される。秘密鍵skey(θ)９０８は、鍵生成装置９００（図１）にて生成されたものである。
【００５８】
復号装置１２００には、上記に加えて、暗号文ciph(θ,M)１１０３(ciph(θ,M)=(C[0],c[1],c[2])が入力される。復号装置１２００は、メッセージM１１０１を、次のように復元して出力する。
M=C[0] {e(c[2],d'[θ,1])/e(c[1],d'[θ,0])}
【００５９】
本実施形態では、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、秘密階層要素が公開鍵９０１に含まれないようにする。暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれないようにすることで、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち秘密鍵skey(θ)９０８の保持者以外の者が判別することができなくなるという効果が得られる。また、本実施形態では、秘密鍵skey(θ)９０８が、秘密階層要素を乱数要素ζ９０６ｂでべき乗した“べき乗された秘密階層要素９１２”を含む。このようにすることで、鍵導出装置１０００にて、下位識別子θ*１００１に対応した下位秘密鍵１００４の導出が可能となる。
【００６０】
本実施形態で説明した暗号化方式を用いることにより、以下に説明するように、キーワード検索が可能な暗号化方式が構成できる。すなわち、ある識別子に対応する秘密鍵の所持者は、その下位の識別子に属する秘密鍵を生成し、第三者に渡す。この下位の識別子は、識別子に対して、検索したいキーワードを追加したものである。上記説明では、追加されたキーワードはθ[m+1]に対応する。暗号文を生成するものが、キーワードθ[m+1]を暗号として、一の暗号文を前記下位の識別子に対応して暗号化したものを選ぶ。この暗号文が、前記下位の識別子に対応したものであることは、本発明の性質から判別しない。下位の識別子に属する秘密鍵を有する第三者だけは、これを復号して一の暗号文であることを知りうる。しかしながら、第三者は、他のキーワードに対する暗号文を判別することはできない。すなわち、本発明を用いれば、利用者は、自身宛の特別なキーワードの暗号文のみを検索する手段を、第三者に委託することが可能になる。このようなキーワード検索可能な暗号方式を用いれば、メールサーバに対して、自分に宛てられた暗号文のサブジェクトに、“重要”等のあらかじめ指定したキーワードが存在する暗号文が届いたときのみ通知することを要請できる。また、“広告”のようなキーワードがある場合は配信せずに抹消することを委託できる。このとき、メールサーバは、どのようなキーワードが登録されているか知ることができない。
【００６１】
図５は、本発明の第２実施形態に係る鍵生成装置の構成を示している。鍵生成装置１３００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１３０６ａ）、乱数要素生成部２（１３０６ｂ）、秘密鍵生成部１３１０ａ、秘密階層要素生成部１３１０ｂ、及び、位数群生成部１３０９を含む。秘密鍵生成部１３１０ａ、秘密階層生成部１３１０ｂは、必要に応じて、位数群生成部１３０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵生成装置１３００には、公開鍵１３０１（(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、及び、マスター鍵１３０３(γ,v',y',(h'[1],...,h'[L]))が入力される。Lを階層数、(h[1],...,h[L])を階層要素１３０２、(h'[1],...,h'[L])を秘密階層要素１３１１と呼ぶ。g',y',h'[1],...,h'[L]は、G'の要素であり、あるZ/pZの元α,γに対して、(g'[i])i=1,...,2N=(g'^(α^i))i=1,...,2N、v'= g'γ，g=ψ(g')，y=ψ(y')，v=ψ(v')，(g[i])i=1,...,2N=(ψ(g'[i]))i=1,...,2N,(h[i])i=1,...,L=(ψ(h'[i]))i=1,...,Lが成り立つとする。
【００６２】
鍵生成装置１３００には、上記に加えて、乱数１３０５と、識別子θ１３０４(θ=(θ[1],...,θ[m])∈(Z/pZ)m)と、ユーザ番号i１３０７とが入力される。鍵生成装置１３００は、乱数１３０５より、Z/pZの要素である２つの乱数要素（乱数要素ξ１３０６ａ、乱数要素ζ１３０６ｂ）を生成し、i番目のユーザ（ユーザ番号ｉ１３０７）の識別子θ１３０４に対応する秘密鍵skey(i,θ)１３０８を、以下のように生成し、出力する。
skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L], e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])
=(g'[i]γ (y' Πi=1m h'[i]θ[i])ξ,g'ξ,h'[m+1]ξ,...,h'[L]ξ,(y' Πi=1m h'[i]θ[i])ζ,g'ζ,h'[m+1]ζ,...,h'[L]ζ)
【００６３】
上記式を参照すると、秘密鍵skey(i,θ)１３０８は、乱数要素ξ１３０６ａでべき乗された要素と、乱数要素ζ１３０６ｂでべき乗された要素とを有する。このうち、乱数要素ξ１３０６ａでべき乗された要素は、非特許文献２の鍵生成装置５００（図１３）で生成される秘密鍵skey(i,θ)５０８「g[i]γ (yΠi=1mh[i]θ[i])ξ,g'ξ,h[m+1]ξ,...,h[L]ξ」に対応する。一方、乱数要素ζ１３０６ｂでべき乗された要素(y'Πi=1m h'[i]θ[i])ζ、及び、g'ζ,h'[m+1]ζ,...,h'[L]ζは、べき乗された秘密階層要素１３１２であり、非特許文献２にはなかったものである。
【００６４】
図６に、鍵導出装置を示す。鍵導出装置１４００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１（１４０３ａ）、乱数要素生成部２（１４０３ｂ）、秘密鍵生成部１４１０ａ、秘密階層要素生成部１４１０ｂ、及び、位数群生成部１４０９を含む。秘密鍵生成部１４１０ａ、秘密階層生成部１４１０ｂは、必要に応じて、位数群生成部１４０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。鍵導出装置１４００には、ユーザ番号ｉ１３０７、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)１３０８（skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L],e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])、及び、識別子θ１３０４(θ=(θ[1],...,θ[m]))が入力される。また、鍵導出装置１４００には、乱数１４０２と、θ*=(θ,θ[m+1])=(θ[1],...,θ[m],θ[m+1])なる下位識別子θ*１４０１とが入力される。ここで、θ[m+1]∈Z/pZとする。
【００６５】
鍵導出装置１４００は、乱数１４０２より、Z/pZの要素である２つの乱数要素（乱数要素λ１４０３ａ及び乱数要素ν１４０３ｂを生成し、下位識別子θ*１４０１に対応する下位秘密鍵skey(i,θ*)１４０４を、以下のように生成し、出力する。
skey(i,θ*)=(d'[i,θ*,0],d'[i,θ*,1],d'[i,θ*,m+1],...,d'[i,θ*,L],e'[i,θ*,0],e'[i,θ*,1],e'[i,θ*,m+1],...,e'[i,θ*,L])
=((d'[i,θ,0] e'[i,θ,0]λ) (d'[i,θ,m+1]） e'[θ,m+1]λ)θ[m+1],d'[i,θ,1] e'[i,θ,1]λ,d'[i,θ,m+2] e'[i,θ,m+2]λ,...,d'[i,θ,L] e'[i,θ,L]λ,(e'[i,θ,0] e'[i,θ,m+1]λ)ν,e'[i,θ,1]ν,e'[i,θ,m+2]ν,...,e'[i,θ,L]ν)）
乱数要素νを用いて生成された
(e'[i,θ,0] e'[i,θ,m+1]λ)ν,e'[i,θ,1]ν, e'[i,θ,m+2]ν, ...,e'[i,θ,L]ν
は、下位のべき乗された秘密階層要素１３１３である。ここで、「ξ+λζ」、「ζν」を二つの乱数要素とみなせば、鍵生成装置１３００（図５）において、θをθ*に置き換えても、同様の分布を持つ下位秘密鍵が導出できる事が重要である。
【００６６】
図７に、暗号化装置を示す。暗号化装置１５００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、乱数要素生成部１５０３、秘密鍵生成部１５１０、及び、位数群生成部１５０９を含む。秘密鍵生成部１１５１は、必要に応じて、位数群生成部１５０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。暗号化装置１５００には、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N], g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、乱数１５０２、識別子θ１３０４（θ=(θ[1],...,θ[m])、及び、ユーザ番号集合S１５０１（S⊂{1,...,N}）が入力される。暗号化装置１５００は、乱数１５０２より、Z/pZの要素τを生成し、共有鍵K１５１０(K∈GT)、及び、暗号文ciph(S,θ)１５０３を、以下のように生成し、出力する。
K=e(g[1],g'[N])τ
ciph(S,θ)=(c[0],c[1],c[2])=((v Πj∈Sg[N+1-j])τ, gτ,(y Πi=1m h[i]θ[i])τ)
【００６７】
図８に、復号装置を示す。復号装置１６００は、入力手段、出力手段、及び、演算手段を備えている。演算手段は、プログラムによって構成され、復号化部１６１０、及び、位数群生成部１６０９を含む。秘密鍵生成部１３１０ａ、復号化部１６１０は、必要に応じて、位数群生成部１６０９を呼び出して位数群を生成させる。なお、プログラムの一部は、ＤＳＰ（デジタルシグナルプロセッサ）によって構成してもよい。復号装置１６００には、ユーザ番号i１３０７、公開鍵１３０１(L,N,p,g',g'[1],...,g'[N],g'[N+2],...,g'[2n],h[1],...,h[L],v,y)、秘密鍵skey(i,θ)１３０８(skey(i,θ)=(d'[i,θ,0],d'[i,θ,1],d'[i,θ,m+1],...,d'[i,θ,L],e'[i,θ,0],e'[i,θ,1],e'[i,θ,m+1],...,e'[i,θ,L])、及び、識別子θ１３０４（θ=(θ[1],...,θ[m])）が入力される。また、i∈Sなるユーザ番号集合S１５０１と、暗号文ciph(S,θ)１５０３(ciph(S,θ)=(c[0],c[1],c[2]))が入力される。復号装置１６００は、共有鍵K１５１０を、次のように復元して出力する。
K=(e(c[0],g'[i]) e(c[2],d'[i,θ,1]) / e(c[1],d'[i,θ,0] Πj∈S,j≠ig'[N+1-j+i])
【００６８】
本実施形態においても、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素c[1],c[2]との双線形写像がとれる要素を秘密階層要素とし、秘密階層要素が公開鍵１３０１に含まれないようにする。暗号文との双線形写像の像を計算できるような強い階層要素が公開鍵に含まれないようにすることで、第１実施形態と同様に、暗号文が、どの識別子に対応して生成されたかを、正当な受信者以外の者、すなわち秘密鍵skey(i,θ)１３０８の保持者以外の者が判別することができなくなるという効果が得られる。また、本実施形態では、秘密鍵skey(i,θ)１３０８が、秘密階層要素を乱数要素ζ１３０６ｂでべき乗したべき乗された秘密階層要素１３１２を含む。このようにすることで、鍵導出装置１４００にて、下位識別子θ*１４０１に対応した下位秘密鍵１４０４の導出が可能となる。
【００６９】
本発明では、同じ位数の群G、G'、GTで、群Gと群G'とから群GTへの双線形写像と、群G'から群Gへの同型写像とが存在する三つの群G、G'、GTを考えたとき、Gの元とGの元との双線形写像がとれない群を用いて、暗号文の要素との双線形写像がとれる要素を秘密階層要素とし、これを公開鍵に含めないようにする。このようにすることで、暗号文から、暗号化に用いた識別子が判別しないようにすることができる。また、本発明では、乱数要素を２つ用意して、秘密鍵に、秘密階層要素を２つの乱数でべき乗した要素を含める。このようにすることで、秘密鍵から、下位秘密鍵を導出することが可能となる。
【００７０】
以上、本発明をその好適な実施形態に基づいて説明したが、本発明の鍵生成装置、鍵導出装置、暗号化装置、復号装置、方法、及び、プログラムは、上記実施形態にのみ限定されるものではなく、上記実施形態の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。
【００７１】
本出願は、２００７年２月１３日出願に係る日本特許出願２００７−０３２６０２号を基礎とし、且つその優先権を主張するものであり、引用によってその開示の内容の全てを本出願の明細書中に加入する。
【産業上の利用可能性】
【００７２】
本発明は、匿名性を有する階層的な識別子に基づく暗号化方式において、キーワード検索が可能な暗号化方式に適用することができる。
【国際調査報告】
2008099831.tif 000019
2008099831.tif 000020
2008099831.tif 000021
2008099831.tif 000022