鍵生成装置、暗号化装置、復号化装置、暗号化システム、鍵生成方法、暗号化方法、復号化方法、プログラム、および記録媒体
【課題】ＩＤを秘匿化でき、かつ暗号文のサイズが階層の深さに依存しない階層型ＩＤベース暗号技術を提供する。
【解決手段】本発明の暗号化システムは、鍵生成装置、暗号化装置、復号化装置で構成される。鍵生成装置は、マスター秘密鍵Ｓｍと復号化装置のＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を用いて、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置の識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置は、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。
【解決手段】本発明の暗号化システムは、鍵生成装置、暗号化装置、復号化装置で構成される。鍵生成装置は、マスター秘密鍵Ｓｍと復号化装置のＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を用いて、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置の識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置は、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層的な復号化装置に対して、復号化装置の識別情報を用いて暗号化、復号化する階層型ＩＤベース暗号の鍵生成装置、暗号化装置、復号化装置、暗号化システム、鍵生成方法、暗号化方法、復号化方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
階層型ＩＤベース暗号は、非特許文献１で初めて提案された。しかし、非特許文献１の方式では、ＩＤ（復号化装置の識別情報）に匿名性を持たせることができなかった。また、階層の深さに依存して暗号文のサイズが増加してしまっていた。
【０００３】
非特許文献２は、暗号文のサイズが階層の深さに依存せず、一定となる方式である。しかし、この方式ではＩＤを秘匿化できなかった。また、ＩＤに秘匿性を持たせる方式として、非特許文献３が提案された。しかし、この方式では、暗号文のサイズが階層の深さに依存して増加してしまう。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】C. Gentry, A. Silverberg, “Hierarchical ID-based cryptography,” in Proceedings of ASIACRYPT 2002, Lecture Notes in Computer Sience, Springer-Verlag, 2002.
【非特許文献２】Dan Boneh, Xavier Boyen, and Eu-Jin Goh, “Hierarchical identity based encryption with constant size ciphertext,” Proceedings of Eurocrypt 2005, volume 3494 of LNCS, pp.440-456, 2005.
【非特許文献３】Xavier Boyen and Brent Waters, “Anonymous hierarchical identity-based encryption (without random oracles),” Proceedings of CRYPTO 2006, volume 411 of LNCS, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、ＩＤ（復号装置の識別情報）を秘匿化でき、かつ暗号文のサイズが階層の深さに依存しない階層型ＩＤベース暗号技術を提供することである。
【課題を解決するための手段】
【０００６】
まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。本発明の鍵生成装置は、鍵生成記録部、公開鍵生成部、鍵生成ランダム値選択部、階層秘密鍵生成部を備える。鍵生成記録部は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。公開鍵生成部は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する。鍵生成ランダム値選択部は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【０００７】
【数１】
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。
復号鍵生成手段は、Ｓｄ（ｋ）を、
【０００８】
【数２】
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【０００９】
【数３】
のように求める。秘密鍵生成手段は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。
【００１０】
暗号化装置は、暗号化記録部、暗号化ランダム値選択部、暗号化部を備える。暗号化記録部は、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する。暗号化ランダム値選択部は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する。暗号化部は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【００１１】
【数４】
のように求める。
【００１２】
ｋ番目（ただし、２番目以降）の階層の復号化装置は、復号化記録部、復号化ランダム値選択部、階層秘密鍵生成部、復号化部を備える。復号化記録部は、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部は、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００１３】
【数５】
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段は、Ｓｄ（ｋ）を、
【００１４】
【数６】
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【００１５】
【数７】
のように求める。秘密鍵生成手段はｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。復号化部は、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００１６】
【数８】
のように平文Ｍに復号する。
１番目の階層の復号化装置は、復号化記録部と復号化部とを備える。復号化記録部は、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する。復号化部は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００１７】
【数９】
のように平文Ｍに復号する。なお、１番目の階層の復号化部は鍵生成装置と同一でもよい。
【発明の効果】
【００１８】
本発明によれば、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がない。したがって、ＩＤを秘匿化できる。また、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【図面の簡単な説明】
【００１９】
【図１】本発明の暗号化システムの構成例を示す図。
【図２】本発明の鍵生成装置および１番目の階層の復号化装置の機能構成例を示す図。
【図３】本発明の鍵生成装置の処理フローの例を示す図。
【図４】本発明の暗号化装置の機能構成例を示す図。
【図５】本発明の暗号化装置の処理フローの例を示す図。
【図６】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す図。
【図７】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す図。
【図８】コンピュータの機能構成例を示す図。
【発明を実施するための形態】
【００２０】
以下に、本発明について図面を参照しながら説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２１】
図１に本発明の暗号化システムの構成例を示す。本発明の暗号化システムは、鍵生成装置１００（復号化装置３００−１）、暗号化装置２００、復号化装置３００−２，…，Ｋで構成される。まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置３００−ｋを識別するための整数、ＤはＫ個の復号化装置３００−１，…，Ｋを識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。なお、このように定義すると、群Ｇ＾の任意の要素ｇとｈおよび任意の整数ａとｂについてｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂ、および、群Ｇｐの任意の要素ｈｐと群Ｇｑの任意の要素ｈｑについてｅ（ｈｐ，ｈｑ）＝１の関係が成り立つ。
【００２２】
鍵生成装置１００は、マスター秘密鍵Ｓｍと復号化装置３００−１，…，ＫのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録しており、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、公開鍵Ｐと復号化装置３００−ｋのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録している。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置３００−１，…，ｋの識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置３００−１（図１では鍵生成装置１００と同一）は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。本発明の暗号化システムでは、暗号文Ｃ（ｋ）と一緒に復号化装置の識別情報を送信しないので、ＩＤを秘匿化できる。
【００２３】
図２に鍵生成装置１００の機能構成例を示す。また、図３に鍵生成装置１００の処理フロー例を示す。鍵生成装置１００は、鍵生成記録部１１０、公開鍵生成部１２０、鍵生成ランダム値選択部１３０、階層秘密鍵生成部１４０を備える。鍵生成記録部１１０は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。なお、データｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗは、マスター秘密鍵Ｓｍ＝［ｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗ］として記録される。公開鍵生成部１２０は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する（Ｓ１２０）。鍵生成ランダム値選択部１３０は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【００２４】
【数１０】
を満たさないように、ランダムに選択する（Ｓ１３０）。
階層秘密鍵生成部１４０は、復号鍵生成手段１５０、引継情報生成手段１６０、秘密鍵生成手段１７０を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する（Ｓ１４０）。復号鍵生成手段１５０は、Ｓｄ（ｋ）を、
【００２５】
【数１１】
のように求める（Ｓ１５０）。引継情報生成手段１６０は、Ｓｒ（ｋ）を、
【００２６】
【数１２】
のように求める（Ｓ１６０）。秘密鍵生成手段１７０は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ１７０）。
【００２７】
図４に暗号化装置の機能構成例を示す。また、図５に暗号化装置の処理フローの例を示す。暗号化装置２００は、暗号化記録部２１０、暗号化ランダム値選択部２３０、暗号化部２８０を備える。暗号化記録部２１０は、Ｋ個（Ｋ層）の復号化装置を識別するための識別情報Ｄ、鍵生成装置１００が公開した公開鍵Ｐ、送信対象の平文Ｍを記録する。暗号化ランダム値選択部２３０は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する（Ｓ２３０）。暗号化部２８０は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を、
【００２８】
【数１３】
のように求め（Ｓ２８０）、ｋ番目の階層の復号化装置３００−ｋに暗号文Ｃ（ｋ）を送信する。
【００２９】
図６にｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す。また、図７にｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、復号化記録部３１０−ｋ、復号化ランダム値選択部３３０−ｋ、階層秘密鍵生成部３４０−ｋ、復号化部３９０−ｋを備える。復号化記録部３１０−ｋは、受信したｋ−１番目の階層の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、受信した暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００３０】
【数１４】
を満たさないように、ランダムに選択する（Ｓ３３０−ｋ）。例えば、復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択し（Ｓ３３１−ｋ）、上記の式を満たすかを確認する（Ｓ３３２−ｋ）。Ｙｅｓの場合には、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択する処理を繰り返す。Ｎｏの場合には、次の処理に進む。
【００３１】
階層秘密鍵生成部３４０−ｋは、復号鍵生成手段３５０−ｋ、引継情報生成手段３６０−ｋ、秘密鍵生成手段３７０−ｋを備え、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段３５０−ｋは、Ｓｄ（ｋ）を、
【００３２】
【数１５】
のように求める（Ｓ３５０−ｋ）。引継情報生成手段３６０−ｋは、Ｓｒ（ｋ）を、
【００３３】
【数１６】
のように求める（Ｓ３６０−ｋ）。秘密鍵生成手段３７０−ｋは自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ３７０−ｋ）。復号化部３９０−ｋは、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００３４】
【数１７】
のように平文Ｍに復号する（Ｓ３９０−ｋ）。
【００３５】
１番目の階層の復号化装置３００−１は、図１の例では鍵生成装置１００と同一の装置である。図２中に点線で示した構成部が１番目の階層の復号化装置３００−１として機能する構成部である。具体的には、復号化記録部３１０−１と復号化部３９０−１である。復号化記録部３１０は、階層秘密鍵生成部１４０が生成した１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）、受信した暗号文Ｃ（１）を記録する。復号化部３９０−１は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００３６】
【数１８】
のように平文Ｍに復号する（Ｓ３９０−１）。なお、図１の例は１番目の階層の復号化装置は鍵生成装置と同一としたが、別の装置としてもよい。別の装置とする場合には、復号化装置３００−１は鍵生成装置１００から、１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）を受け取っておく必要がある。
検証
【００３７】
【数１９】
によって平文Ｍが求められることを確認する。
まず、鍵生成装置１００の階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）で確認する。階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００３８】
【数２０】
また、Ｃ１，Ｃ２，Ｃ３，Ｃ４は、次のとおりである。
【００３９】
【数２１】
したがって、
【００４０】
【数２２】
は、次のようになる。
【００４１】
【数２３】
【００４２】
また、階層秘密鍵生成部３４０−ｋは、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を、ｋ−１番目の階層の復号化装置３００−ｋ−１用の階層秘密鍵Ｓ（ｋ−１）から生成する。また、
Ｓ（ｋ−１）は、
【００４３】
【数２４】
であり、階層秘密鍵生成部３４０−ｋが求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００４４】
【数２５】
したがって、
【００４５】
【数２６】
となる。これらは、階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２
【００４６】
【数２７】
と同じである。
つまり、ｋ番目（ただし、２番目以降）の階層の復号化装置は、自己（ｋ番目）よりも上位の階層の復号化装置の識別情報Ｄ１，…，Ｄｋ−１を知らなくても暗号文Ｃ（ｋ）を復号化できる。よって、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がなく、ＩＤ（復号化装置の識別情報）を秘匿化できる。また、暗号文Ｃ（ｋ）は、
【００４７】
【数２８】
なので、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【００４８】
図８に、コンピュータの機能構成例を示す。なお、本発明の鍵生成装置、暗号化装置および復号化装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００４９】
本発明は、２台以上の通信装置の間で情報を暗号化して通信するような場合などに利用できる。
【符号の説明】
【００５０】
１００ 鍵生成装置 １１０ 鍵生成記録部
１２０ 公開鍵生成部 １３０ 鍵生成ランダム値選択部
１４０ 階層秘密鍵生成部 １５０ 復号鍵生成手段
１６０ 引継情報生成手段 １７０ 秘密鍵生成手段
２００ 暗号化装置 ２１０ 暗号化記録部
２３０ 暗号化ランダム値選択部 ２８０ 暗号化部
３００ 復号化装置 ３１０ 復号化記録部
３３０ 復号化ランダム値選択部 ３４０ 階層秘密鍵生成部
３５０ 復号鍵生成手段 ３６０ 引継情報生成手段
３７０ 秘密鍵生成手段 ３９０ 復号化部
【技術分野】
【０００１】
本発明は、階層的な復号化装置に対して、復号化装置の識別情報を用いて暗号化、復号化する階層型ＩＤベース暗号の鍵生成装置、暗号化装置、復号化装置、暗号化システム、鍵生成方法、暗号化方法、復号化方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
階層型ＩＤベース暗号は、非特許文献１で初めて提案された。しかし、非特許文献１の方式では、ＩＤ（復号化装置の識別情報）に匿名性を持たせることができなかった。また、階層の深さに依存して暗号文のサイズが増加してしまっていた。
【０００３】
非特許文献２は、暗号文のサイズが階層の深さに依存せず、一定となる方式である。しかし、この方式ではＩＤを秘匿化できなかった。また、ＩＤに秘匿性を持たせる方式として、非特許文献３が提案された。しかし、この方式では、暗号文のサイズが階層の深さに依存して増加してしまう。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】C. Gentry, A. Silverberg, “Hierarchical ID-based cryptography,” in Proceedings of ASIACRYPT 2002, Lecture Notes in Computer Sience, Springer-Verlag, 2002.
【非特許文献２】Dan Boneh, Xavier Boyen, and Eu-Jin Goh, “Hierarchical identity based encryption with constant size ciphertext,” Proceedings of Eurocrypt 2005, volume 3494 of LNCS, pp.440-456, 2005.
【非特許文献３】Xavier Boyen and Brent Waters, “Anonymous hierarchical identity-based encryption (without random oracles),” Proceedings of CRYPTO 2006, volume 411 of LNCS, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、ＩＤ（復号装置の識別情報）を秘匿化でき、かつ暗号文のサイズが階層の深さに依存しない階層型ＩＤベース暗号技術を提供することである。
【課題を解決するための手段】
【０００６】
まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。本発明の鍵生成装置は、鍵生成記録部、公開鍵生成部、鍵生成ランダム値選択部、階層秘密鍵生成部を備える。鍵生成記録部は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。公開鍵生成部は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する。鍵生成ランダム値選択部は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【０００７】
【数１】
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。
復号鍵生成手段は、Ｓｄ（ｋ）を、
【０００８】
【数２】
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【０００９】
【数３】
のように求める。秘密鍵生成手段は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。
【００１０】
暗号化装置は、暗号化記録部、暗号化ランダム値選択部、暗号化部を備える。暗号化記録部は、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する。暗号化ランダム値選択部は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する。暗号化部は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【００１１】
【数４】
のように求める。
【００１２】
ｋ番目（ただし、２番目以降）の階層の復号化装置は、復号化記録部、復号化ランダム値選択部、階層秘密鍵生成部、復号化部を備える。復号化記録部は、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部は、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００１３】
【数５】
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段は、Ｓｄ（ｋ）を、
【００１４】
【数６】
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【００１５】
【数７】
のように求める。秘密鍵生成手段はｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。復号化部は、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００１６】
【数８】
のように平文Ｍに復号する。
１番目の階層の復号化装置は、復号化記録部と復号化部とを備える。復号化記録部は、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する。復号化部は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００１７】
【数９】
のように平文Ｍに復号する。なお、１番目の階層の復号化部は鍵生成装置と同一でもよい。
【発明の効果】
【００１８】
本発明によれば、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がない。したがって、ＩＤを秘匿化できる。また、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【図面の簡単な説明】
【００１９】
【図１】本発明の暗号化システムの構成例を示す図。
【図２】本発明の鍵生成装置および１番目の階層の復号化装置の機能構成例を示す図。
【図３】本発明の鍵生成装置の処理フローの例を示す図。
【図４】本発明の暗号化装置の機能構成例を示す図。
【図５】本発明の暗号化装置の処理フローの例を示す図。
【図６】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す図。
【図７】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す図。
【図８】コンピュータの機能構成例を示す図。
【発明を実施するための形態】
【００２０】
以下に、本発明について図面を参照しながら説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２１】
図１に本発明の暗号化システムの構成例を示す。本発明の暗号化システムは、鍵生成装置１００（復号化装置３００−１）、暗号化装置２００、復号化装置３００−２，…，Ｋで構成される。まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置３００−ｋを識別するための整数、ＤはＫ個の復号化装置３００−１，…，Ｋを識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。なお、このように定義すると、群Ｇ＾の任意の要素ｇとｈおよび任意の整数ａとｂについてｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂ、および、群Ｇｐの任意の要素ｈｐと群Ｇｑの任意の要素ｈｑについてｅ（ｈｐ，ｈｑ）＝１の関係が成り立つ。
【００２２】
鍵生成装置１００は、マスター秘密鍵Ｓｍと復号化装置３００−１，…，ＫのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録しており、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、公開鍵Ｐと復号化装置３００−ｋのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録している。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置３００−１，…，ｋの識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置３００−１（図１では鍵生成装置１００と同一）は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。本発明の暗号化システムでは、暗号文Ｃ（ｋ）と一緒に復号化装置の識別情報を送信しないので、ＩＤを秘匿化できる。
【００２３】
図２に鍵生成装置１００の機能構成例を示す。また、図３に鍵生成装置１００の処理フロー例を示す。鍵生成装置１００は、鍵生成記録部１１０、公開鍵生成部１２０、鍵生成ランダム値選択部１３０、階層秘密鍵生成部１４０を備える。鍵生成記録部１１０は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。なお、データｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗは、マスター秘密鍵Ｓｍ＝［ｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗ］として記録される。公開鍵生成部１２０は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する（Ｓ１２０）。鍵生成ランダム値選択部１３０は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【００２４】
【数１０】
を満たさないように、ランダムに選択する（Ｓ１３０）。
階層秘密鍵生成部１４０は、復号鍵生成手段１５０、引継情報生成手段１６０、秘密鍵生成手段１７０を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する（Ｓ１４０）。復号鍵生成手段１５０は、Ｓｄ（ｋ）を、
【００２５】
【数１１】
のように求める（Ｓ１５０）。引継情報生成手段１６０は、Ｓｒ（ｋ）を、
【００２６】
【数１２】
のように求める（Ｓ１６０）。秘密鍵生成手段１７０は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ１７０）。
【００２７】
図４に暗号化装置の機能構成例を示す。また、図５に暗号化装置の処理フローの例を示す。暗号化装置２００は、暗号化記録部２１０、暗号化ランダム値選択部２３０、暗号化部２８０を備える。暗号化記録部２１０は、Ｋ個（Ｋ層）の復号化装置を識別するための識別情報Ｄ、鍵生成装置１００が公開した公開鍵Ｐ、送信対象の平文Ｍを記録する。暗号化ランダム値選択部２３０は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する（Ｓ２３０）。暗号化部２８０は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を、
【００２８】
【数１３】
のように求め（Ｓ２８０）、ｋ番目の階層の復号化装置３００−ｋに暗号文Ｃ（ｋ）を送信する。
【００２９】
図６にｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す。また、図７にｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、復号化記録部３１０−ｋ、復号化ランダム値選択部３３０−ｋ、階層秘密鍵生成部３４０−ｋ、復号化部３９０−ｋを備える。復号化記録部３１０−ｋは、受信したｋ−１番目の階層の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、受信した暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００３０】
【数１４】
を満たさないように、ランダムに選択する（Ｓ３３０−ｋ）。例えば、復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択し（Ｓ３３１−ｋ）、上記の式を満たすかを確認する（Ｓ３３２−ｋ）。Ｙｅｓの場合には、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択する処理を繰り返す。Ｎｏの場合には、次の処理に進む。
【００３１】
階層秘密鍵生成部３４０−ｋは、復号鍵生成手段３５０−ｋ、引継情報生成手段３６０−ｋ、秘密鍵生成手段３７０−ｋを備え、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段３５０−ｋは、Ｓｄ（ｋ）を、
【００３２】
【数１５】
のように求める（Ｓ３５０−ｋ）。引継情報生成手段３６０−ｋは、Ｓｒ（ｋ）を、
【００３３】
【数１６】
のように求める（Ｓ３６０−ｋ）。秘密鍵生成手段３７０−ｋは自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ３７０−ｋ）。復号化部３９０−ｋは、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００３４】
【数１７】
のように平文Ｍに復号する（Ｓ３９０−ｋ）。
【００３５】
１番目の階層の復号化装置３００−１は、図１の例では鍵生成装置１００と同一の装置である。図２中に点線で示した構成部が１番目の階層の復号化装置３００−１として機能する構成部である。具体的には、復号化記録部３１０−１と復号化部３９０−１である。復号化記録部３１０は、階層秘密鍵生成部１４０が生成した１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）、受信した暗号文Ｃ（１）を記録する。復号化部３９０−１は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００３６】
【数１８】
のように平文Ｍに復号する（Ｓ３９０−１）。なお、図１の例は１番目の階層の復号化装置は鍵生成装置と同一としたが、別の装置としてもよい。別の装置とする場合には、復号化装置３００−１は鍵生成装置１００から、１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）を受け取っておく必要がある。
検証
【００３７】
【数１９】
によって平文Ｍが求められることを確認する。
まず、鍵生成装置１００の階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）で確認する。階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００３８】
【数２０】
また、Ｃ１，Ｃ２，Ｃ３，Ｃ４は、次のとおりである。
【００３９】
【数２１】
したがって、
【００４０】
【数２２】
は、次のようになる。
【００４１】
【数２３】
【００４２】
また、階層秘密鍵生成部３４０−ｋは、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を、ｋ−１番目の階層の復号化装置３００−ｋ−１用の階層秘密鍵Ｓ（ｋ−１）から生成する。また、
Ｓ（ｋ−１）は、
【００４３】
【数２４】
であり、階層秘密鍵生成部３４０−ｋが求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００４４】
【数２５】
したがって、
【００４５】
【数２６】
となる。これらは、階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２
【００４６】
【数２７】
と同じである。
つまり、ｋ番目（ただし、２番目以降）の階層の復号化装置は、自己（ｋ番目）よりも上位の階層の復号化装置の識別情報Ｄ１，…，Ｄｋ−１を知らなくても暗号文Ｃ（ｋ）を復号化できる。よって、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がなく、ＩＤ（復号化装置の識別情報）を秘匿化できる。また、暗号文Ｃ（ｋ）は、
【００４７】
【数２８】
なので、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【００４８】
図８に、コンピュータの機能構成例を示す。なお、本発明の鍵生成装置、暗号化装置および復号化装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００４９】
本発明は、２台以上の通信装置の間で情報を暗号化して通信するような場合などに利用できる。
【符号の説明】
【００５０】
１００ 鍵生成装置 １１０ 鍵生成記録部
１２０ 公開鍵生成部 １３０ 鍵生成ランダム値選択部
１４０ 階層秘密鍵生成部 １５０ 復号鍵生成手段
１６０ 引継情報生成手段 １７０ 秘密鍵生成手段
２００ 暗号化装置 ２１０ 暗号化記録部
２３０ 暗号化ランダム値選択部 ２８０ 暗号化部
３００ 復号化装置 ３１０ 復号化記録部
３３０ 復号化ランダム値選択部 ３４０ 階層秘密鍵生成部
３５０ 復号鍵生成手段 ３６０ 引継情報生成手段
３７０ 秘密鍵生成手段 ３９０ 復号化部
【特許請求の範囲】
【請求項１】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数２９】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数３０】
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数３１】
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項２】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数３２】
を満たさないように、ランダムに選択する鍵生成ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３３】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３４】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項３】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数３５】
のように求める暗号化部と
を備える暗号化装置。
【請求項４】
２番目以降の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数３６】
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３７】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３８】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数３９】
のように平文Ｍに復号する
ことを特徴とする復号化装置。
【請求項５】
１番目の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する復号化記録部と、
暗号文Ｃ（１）を
【数４０】
のように平文Ｍに復号する復号化部
を備え、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数４１】
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数４２】
とし、
Ｓｒ（１）を、
【数４３】
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化装置。
【請求項６】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化システムであって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数４４】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数４５】
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数４６】
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備え、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数４７】
のように求める暗号化部と
を備え、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数４８】
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数４９】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数５０】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数５１】
のように平文Ｍに復号する
ことを特徴とする暗号化システム。
【請求項７】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
公開鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５２】
を満たさない条件で、ランダムに選択する公開鍵生成ステップと、
階層秘密鍵生成部で、階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数５３】
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数５４】
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項８】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
階層秘密鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５５】
を満たさないように、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数５６】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数５７】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項９】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
あらかじめ暗号化記録部に、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
暗号化ランダム値選択部で、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択ステップと、
暗号化部で、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数５８】
のように求める暗号化ステップと
を有する暗号化方法。
【請求項１０】
２番目以降の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
あらかじめ復号化記録部に、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
復号化ランダム値選択部で、整数γ１，γ２，γ３，δ１，δ２，δ３を
【数５９】
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
復号化部で、階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数６０】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数６１】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数６２】
のように平文Ｍに復号する
ことを特徴とする復号化方法。
【請求項１１】
１番目の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
あらかじめ復号化記録部に、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録しておき、
復号化部で、暗号文Ｃ（１）を
【数６３】
のように平文Ｍに復号する復号化ステップ
を有し、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数６４】
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数６５】
とし、
Ｓｒ（１）を、
【数６６】
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化方法。
【請求項１２】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数６７】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数６８】
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数６９】
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有し、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択ステップと、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数７０】
のように求める暗号化ステップと
を有し、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数７１】
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数７２】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数７３】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数７４】
のように平文Ｍに復号する
ことを特徴とする暗号化方法。
【請求項１３】
請求項１から５のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数２９】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数３０】
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数３１】
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項２】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数３２】
を満たさないように、ランダムに選択する鍵生成ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３３】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３４】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項３】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数３５】
のように求める暗号化部と
を備える暗号化装置。
【請求項４】
２番目以降の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数３６】
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３７】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３８】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数３９】
のように平文Ｍに復号する
ことを特徴とする復号化装置。
【請求項５】
１番目の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する復号化記録部と、
暗号文Ｃ（１）を
【数４０】
のように平文Ｍに復号する復号化部
を備え、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数４１】
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数４２】
とし、
Ｓｒ（１）を、
【数４３】
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化装置。
【請求項６】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化システムであって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数４４】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数４５】
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数４６】
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備え、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数４７】
のように求める暗号化部と
を備え、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数４８】
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数４９】
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数５０】
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数５１】
のように平文Ｍに復号する
ことを特徴とする暗号化システム。
【請求項７】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
公開鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５２】
を満たさない条件で、ランダムに選択する公開鍵生成ステップと、
階層秘密鍵生成部で、階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数５３】
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数５４】
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項８】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
階層秘密鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５５】
を満たさないように、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数５６】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数５７】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項９】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
あらかじめ暗号化記録部に、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
暗号化ランダム値選択部で、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択ステップと、
暗号化部で、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数５８】
のように求める暗号化ステップと
を有する暗号化方法。
【請求項１０】
２番目以降の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
あらかじめ復号化記録部に、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
復号化ランダム値選択部で、整数γ１，γ２，γ３，δ１，δ２，δ３を
【数５９】
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
復号化部で、階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数６０】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数６１】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数６２】
のように平文Ｍに復号する
ことを特徴とする復号化方法。
【請求項１１】
１番目の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
あらかじめ復号化記録部に、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録しておき、
復号化部で、暗号文Ｃ（１）を
【数６３】
のように平文Ｍに復号する復号化ステップ
を有し、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数６４】
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数６５】
とし、
Ｓｒ（１）を、
【数６６】
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化方法。
【請求項１２】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数６７】
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数６８】
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数６９】
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有し、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択ステップと、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数７０】
のように求める暗号化ステップと
を有し、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数７１】
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数７２】
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数７３】
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数７４】
のように平文Ｍに復号する
ことを特徴とする暗号化方法。
【請求項１３】
請求項１から５のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−１６１５２３（Ｐ２０１０−１６１５２３Ａ）
【公開日】平成２２年７月２２日（２０１０．７．２２）
【国際特許分類】
【出願番号】特願２００９−１２９８（Ｐ２００９−１２９８）
【出願日】平成２１年１月７日（２００９．１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２２日（２０１０．７．２２）
【国際特許分類】
【出願日】平成２１年１月７日（２００９．１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]