(57)【要約】【課題】ＩＤを秘匿化でき、かつ暗号文のサイズが階層の深さに依存しない階層型ＩＤベース暗号技術を提供する。【解決手段】本発明の暗号化システムは、鍵生成装置、暗号化装置、復号化装置で構成される。鍵生成装置は、マスター秘密鍵Ｓｍと復号化装置のＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を用いて、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置の識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置は、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。【選択図】図１
2010161523.tif 000002
【特許請求の範囲】
【請求項１】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数２９】
2010161523.tif 000031
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数３０】
2010161523.tif 000032
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数３１】
2010161523.tif 000033
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項２】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数３２】
2010161523.tif 000034
を満たさないように、ランダムに選択する鍵生成ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３３】
2010161523.tif 000035
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３４】
2010161523.tif 000036
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備える
ことを特徴とする鍵生成装置。
【請求項３】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数３５】
2010161523.tif 000037
のように求める暗号化部と
を備える暗号化装置。
【請求項４】
２番目以降の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数３６】
2010161523.tif 000038
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数３７】
2010161523.tif 000039
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数３８】
2010161523.tif 000040
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数３９】
2010161523.tif 000041
のように平文Ｍに復号する
ことを特徴とする復号化装置。
【請求項５】
１番目の階層の復号化装置であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する復号化記録部と、
暗号文Ｃ（１）を
【数４０】
2010161523.tif 000042
のように平文Ｍに復号する復号化部
を備え、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数４１】
2010161523.tif 000043
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数４２】
2010161523.tif 000044
とし、
Ｓｒ（１）を、
【数４３】
2010161523.tif 000045
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化装置。
【請求項６】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化システムであって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する鍵生成記録部と、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成部と、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数４４】
2010161523.tif 000046
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択部と、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成部と、
を備え、
前記階層秘密鍵生成部は、
Ｓｄ（１）を、
【数４５】
2010161523.tif 000047
のように求める復号鍵生成手段と、
Ｓｒ（１）を、
【数４６】
2010161523.tif 000048
のように求める引継情報生成手段と、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成手段と
を備え、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する暗号化記録部と、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択部と、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数４７】
2010161523.tif 000049
のように求める暗号化部と
を備え、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する復号化記録部と、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数４８】
2010161523.tif 000050
を満たさないように、ランダムに選択する復号化ランダム値選択部と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成部と、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化部
を備え、
前記階層鍵生成部は、
Ｓｄ（ｋ）を、
【数４９】
2010161523.tif 000051
のように求める復号鍵生成手段と、
Ｓｒ（ｋ）を、
【数５０】
2010161523.tif 000052
のように求める引継情報生成手段と、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成手段と
を備え、
前記復号化部は、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数５１】
2010161523.tif 000053
のように平文Ｍに復号する
ことを特徴とする暗号化システム。
【請求項７】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
公開鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５２】
2010161523.tif 000054
を満たさない条件で、ランダムに選択する公開鍵生成ステップと、
階層秘密鍵生成部で、階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数５３】
2010161523.tif 000055
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数５４】
2010161523.tif 000056
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項８】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
あらかじめ鍵生成記録部に、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
公開鍵生成部で、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
階層秘密鍵生成部で、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数５５】
2010161523.tif 000057
を満たさないように、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数５６】
2010161523.tif 000058
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数５７】
2010161523.tif 000059
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有する
ことを特徴とする鍵生成方法。
【請求項９】
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｑは素数位数ｑを持つＧ＾の部分群、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、公開鍵ＰをＰ＝［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］とし、
あらかじめ暗号化記録部に、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
暗号化ランダム値選択部で、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する暗号化ランダム値選択ステップと、
暗号化部で、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数５８】
2010161523.tif 000060
のように求める暗号化ステップと
を有する暗号化方法。
【請求項１０】
２番目以降の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す２≦ｋ≦Ｋの整数、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
あらかじめ復号化記録部に、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
復号化ランダム値選択部で、整数γ１，γ２，γ３，δ１，δ２，δ３を
【数５９】
2010161523.tif 000061
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
階層秘密鍵生成部で、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
復号化部で、階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃを平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数６０】
2010161523.tif 000062
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数６１】
2010161523.tif 000063
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数６２】
2010161523.tif 000064
のように平文Ｍに復号する
ことを特徴とする復号化方法。
【請求項１１】
１番目の階層の復号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」、Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（１）のはじめの３つの要素とし、
あらかじめ復号化記録部に、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録しておき、
復号化部で、暗号文Ｃ（１）を
【数６３】
2010161523.tif 000065
のように平文Ｍに復号する復号化ステップ
を有し、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【数６４】
2010161523.tif 000066
を満たさない条件で、ランダムに選択された整数とし、
Ｓｄ（１）を、
【数６５】
2010161523.tif 000067
とし、
Ｓｒ（１）を、
【数６６】
2010161523.tif 000068
とし、
階層秘密鍵Ｓ（１）は、
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求められたものである
ことを特徴とする復号化方法。
【請求項１２】
鍵生成装置、暗号化装置、階層化されたＫ−１個の復号化装置で構成された暗号化方法であって、
ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］とし、
前記鍵生成装置は、
群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録しておき、
Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する公開鍵生成ステップと、
整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【数６７】
2010161523.tif 000069
を満たさない条件で、ランダムに選択する鍵生成ランダム値選択ステップと、
階層秘密鍵Ｓ（１）を生成する階層秘密鍵生成ステップと、
を有し、
前記階層秘密鍵生成ステップは、
Ｓｄ（１）を、
【数６８】
2010161523.tif 000070
のように求める復号鍵生成サブステップと、
Ｓｒ（１）を、
【数６９】
2010161523.tif 000071
のように求める引継情報生成サブステップと、
階層秘密鍵Ｓ（１）を
Ｓ（１）←［Ｓｄ（１），Ｓｒ（１）］
のように求める秘密鍵生成サブステップと
を有し、
前記暗号化装置は、
識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録しておき、
ランダムに整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３を選択する暗号化ランダム値選択ステップと、
群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【数７０】
2010161523.tif 000072
のように求める暗号化ステップと
を有し、
２番目以降のｋ番目の階層の前記復号化装置は、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）をＳ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とし、
ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録しておき、
整数γ１，γ２，γ３，δ１，δ２，δ３を
【数７１】
2010161523.tif 000073
を満たさないように、ランダムに選択する復号化ランダム値選択ステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する階層秘密鍵生成ステップと、
階層秘密鍵Ｓ（ｋ）を用いて暗号文Ｃ（ｋ）を平文Ｍに復号する復号化ステップ
を有し、
前記階層鍵生成ステップは、
Ｓｄ（ｋ）を、
【数７２】
2010161523.tif 000074
のように求める復号鍵生成サブステップと、
Ｓｒ（ｋ）を、
【数７３】
2010161523.tif 000075
のように求める引継情報生成サブステップと、
ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める秘密鍵生成サブステップと
を有し、
前記復号化ステップは、
Ａ０，Ａ１，Ａ２を階層秘密鍵Ｓ（ｋ）のはじめの３つの要素とすると、
暗号文Ｃ（ｋ）を
【数７４】
2010161523.tif 000076
のように平文Ｍに復号する
ことを特徴とする暗号化方法。
【請求項１３】
請求項１から５のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層的な復号化装置に対して、復号化装置の識別情報を用いて暗号化、復号化する階層型ＩＤベース暗号の鍵生成装置、暗号化装置、復号化装置、暗号化システム、鍵生成方法、暗号化方法、復号化方法、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
階層型ＩＤベース暗号は、非特許文献１で初めて提案された。しかし、非特許文献１の方式では、ＩＤ（復号化装置の識別情報）に匿名性を持たせることができなかった。また、階層の深さに依存して暗号文のサイズが増加してしまっていた。
【０００３】
非特許文献２は、暗号文のサイズが階層の深さに依存せず、一定となる方式である。しかし、この方式ではＩＤを秘匿化できなかった。また、ＩＤに秘匿性を持たせる方式として、非特許文献３が提案された。しかし、この方式では、暗号文のサイズが階層の深さに依存して増加してしまう。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、ＩＤ（復号装置の識別情報）を秘匿化でき、かつ暗号文のサイズが階層の深さに依存しない階層型ＩＤベース暗号技術を提供することである。
【課題を解決するための手段】
【０００６】
まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置を識別するための整数、ＤはＫ個の復号化装置を識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。本発明の鍵生成装置は、鍵生成記録部、公開鍵生成部、鍵生成ランダム値選択部、階層秘密鍵生成部を備える。鍵生成記録部は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。公開鍵生成部は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する。鍵生成ランダム値選択部は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を
【０００７】
【数１】
2010161523.tif 000003
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。
復号鍵生成手段は、Ｓｄ（ｋ）を、
【０００８】
【数２】
2010161523.tif 000004
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【０００９】
【数３】
2010161523.tif 000005
のように求める。秘密鍵生成手段は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。
【００１０】
暗号化装置は、暗号化記録部、暗号化ランダム値選択部、暗号化部を備える。暗号化記録部は、識別情報Ｄ、公開鍵Ｐ、平文Ｍを記録する。暗号化ランダム値選択部は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する。暗号化部は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置用の暗号文Ｃ（ｋ）を、
【００１１】
【数４】
2010161523.tif 000006
のように求める。
【００１２】
ｋ番目（ただし、２番目以降）の階層の復号化装置は、復号化記録部、復号化ランダム値選択部、階層秘密鍵生成部、復号化部を備える。復号化記録部は、ｋ−１番目の階層の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部は、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００１３】
【数５】
2010161523.tif 000007
を満たさないように、ランダムに選択する。階層秘密鍵生成部は、復号鍵生成手段、引継情報生成手段、秘密鍵生成手段を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段は、Ｓｄ（ｋ）を、
【００１４】
【数６】
2010161523.tif 000008
のように求める。引継情報生成手段は、Ｓｒ（ｋ）を、
【００１５】
【数７】
2010161523.tif 000009
のように求める。秘密鍵生成手段はｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める。復号化部は、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００１６】
【数８】
2010161523.tif 000010
のように平文Ｍに復号する。
１番目の階層の復号化装置は、復号化記録部と復号化部とを備える。復号化記録部は、１番目の階層の階層秘密鍵Ｓ（１）、暗号文Ｃ（１）を記録する。復号化部は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００１７】
【数９】
2010161523.tif 000011
のように平文Ｍに復号する。なお、１番目の階層の復号化部は鍵生成装置と同一でもよい。
【発明の効果】
【００１８】
本発明によれば、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がない。したがって、ＩＤを秘匿化できる。また、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【図面の簡単な説明】
【００１９】
【図１】本発明の暗号化システムの構成例を示す図。
【図２】本発明の鍵生成装置および１番目の階層の復号化装置の機能構成例を示す図。
【図３】本発明の鍵生成装置の処理フローの例を示す図。
【図４】本発明の暗号化装置の機能構成例を示す図。
【図５】本発明の暗号化装置の処理フローの例を示す図。
【図６】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す図。
【図７】本発明のｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す図。
【図８】コンピュータの機能構成例を示す図。
【発明を実施するための形態】
【００２０】
以下に、本発明について図面を参照しながら説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２１】
図１に本発明の暗号化システムの構成例を示す。本発明の暗号化システムは、鍵生成装置１００（復号化装置３００−１）、暗号化装置２００、復号化装置３００−２，…，Ｋで構成される。まず、ｐとｑは素数位数、Ｇ＾とＧＴ＾は位数ｐｑを持つ巡回群、Ｇｐは素数位数ｐを持つＧ＾の部分群、Ｇｑは素数位数ｑを持つＧ＾の部分群、ｅはｅ：Ｇ＾×Ｇ＾→ＧＴ＾となる双線型写像、Ｋは階層の最大値を示す整数、ｋは階層を示す１≦ｋ≦Ｋの整数、Ｄｋはｋ番目の階層の復号化装置３００−ｋを識別するための整数、ＤはＫ個の復号化装置３００−１，…，Ｋを識別するための識別情報であってＤ＝［Ｄ１,…,ＤＫ］、暗号文Ｃ（ｋ）をＣ（ｋ）＝「Ｃ１，Ｃ２，Ｃ３，Ｃ４」とする。なお、このように定義すると、群Ｇ＾の任意の要素ｇとｈおよび任意の整数ａとｂについてｅ（ｇａ，ｈｂ）＝ｅ（ｇ，ｈ）ａｂ、および、群Ｇｐの任意の要素ｈｐと群Ｇｑの任意の要素ｈｑについてｅ（ｈｐ，ｈｑ）＝１の関係が成り立つ。
【００２２】
鍵生成装置１００は、マスター秘密鍵Ｓｍと復号化装置３００−１，…，ＫのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録しており、公開鍵Ｐ、配下のすべての階層の階層秘密鍵Ｓ（ｋ）を生成できる。暗号化装置２００は、公開鍵Ｐと復号化装置３００−ｋのＩＤ（識別情報Ｄ＝［Ｄ１,…,ＤＫ］）を記録している。暗号化装置２００は、平文Ｍを、公開鍵Ｐと復号化装置３００−１，…，ｋの識別情報Ｄ１,…,Ｄｋを用いて暗号化し、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を得る。１番目の階層の復号化装置３００−１（図１では鍵生成装置１００と同一）は、受信した暗号文Ｃ（１）を、階層秘密鍵Ｓ（１）を用いて復号化し、平文Ｍを得る。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、受信した暗号文Ｃ（ｋ）を、ｋ−１番目の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを用いて復号化し、平文Ｍを得る。本発明の暗号化システムでは、暗号文Ｃ（ｋ）と一緒に復号化装置の識別情報を送信しないので、ＩＤを秘匿化できる。
【００２３】
図２に鍵生成装置１００の機能構成例を示す。また、図３に鍵生成装置１００の処理フロー例を示す。鍵生成装置１００は、鍵生成記録部１１０、公開鍵生成部１２０、鍵生成ランダム値選択部１３０、階層秘密鍵生成部１４０を備える。鍵生成記録部１１０は、群Ｇｐの要素であるデータｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗと、群Ｇｑの要素であるデータＲｇ，Ｒｆ，Ｒｖ，Ｒ１，…，ＲＫ，ｇｑと、識別情報Ｄを記録する。なお、データｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗは、マスター秘密鍵Ｓｍ＝［ｇ，ｆ，ｖ，ｈ１，…，ｈＫ，ｗ］として記録される。公開鍵生成部１２０は、Ｇ＝ｇＲｇ、Ｆ＝ｆＲｆ、Ｖ＝ｖＲｖ、Ｈ１＝ｈ１Ｒ１，…，ＨＫ＝ｈＫＲＫ、Ｅ＝ｅ（ｇ，ｗ）を計算し、［Ｇ，Ｆ，Ｖ，Ｈ１，…，ＨＫ，Ｅ］を公開鍵Ｐとして生成する（Ｓ１２０）。鍵生成ランダム値選択部１３０は、整数ｒ１，ｒ２，ｓ１，ｓ２，ｔ１，ｔ２を、
【００２４】
【数１０】
2010161523.tif 000012
を満たさないように、ランダムに選択する（Ｓ１３０）。
階層秘密鍵生成部１４０は、復号鍵生成手段１５０、引継情報生成手段１６０、秘密鍵生成手段１７０を備え、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を生成する（Ｓ１４０）。復号鍵生成手段１５０は、Ｓｄ（ｋ）を、
【００２５】
【数１１】
2010161523.tif 000013
のように求める（Ｓ１５０）。引継情報生成手段１６０は、Ｓｒ（ｋ）を、
【００２６】
【数１２】
2010161523.tif 000014
のように求める（Ｓ１６０）。秘密鍵生成手段１７０は、ｋ番目の階層の階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ１７０）。
【００２７】
図４に暗号化装置の機能構成例を示す。また、図５に暗号化装置の処理フローの例を示す。暗号化装置２００は、暗号化記録部２１０、暗号化ランダム値選択部２３０、暗号化部２８０を備える。暗号化記録部２１０は、Ｋ個（Ｋ層）の復号化装置を識別するための識別情報Ｄ、鍵生成装置１００が公開した公開鍵Ｐ、送信対象の平文Ｍを記録する。暗号化ランダム値選択部２３０は、整数ｓと群Ｇｑの要素であるＺ１，Ｚ２，Ｚ３をランダムに選択する（Ｓ２３０）。暗号化部２８０は、群ＧＴ＾の要素である平文Ｍから、ｋ番目の階層の復号化装置３００−ｋ用の暗号文Ｃ（ｋ）を、
【００２８】
【数１３】
2010161523.tif 000015
のように求め（Ｓ２８０）、ｋ番目の階層の復号化装置３００−ｋに暗号文Ｃ（ｋ）を送信する。
【００２９】
図６にｋ番目（ただし、２番目以降）の階層の復号化装置の機能構成例を示す。また、図７にｋ番目（ただし、２番目以降）の階層の復号化装置の処理フローの例を示す。ｋ番目（ただし、２番目以降）の階層の復号化装置３００−ｋは、復号化記録部３１０−ｋ、復号化ランダム値選択部３３０−ｋ、階層秘密鍵生成部３４０−ｋ、復号化部３９０−ｋを備える。復号化記録部３１０−ｋは、受信したｋ−１番目の階層の復号化装置３００−ｋ−１の階層秘密鍵Ｓ（ｋ−１）＝［［ａ０，ａ１，ａ２，ｂｋ，…，ｂＫ］，［α０，α１，α２，βｋ，…，βK］，［α０’，α１’，α２’，βｋ’，…，βK’］］、受信した暗号文Ｃ（ｋ）、自己の識別情報Ｄｋを記録する。復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３を
【００３０】
【数１４】
2010161523.tif 000016
を満たさないように、ランダムに選択する（Ｓ３３０−ｋ）。例えば、復号化ランダム値選択部３３０−ｋは、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択し（Ｓ３３１−ｋ）、上記の式を満たすかを確認する（Ｓ３３２−ｋ）。Ｙｅｓの場合には、整数γ１，γ２，γ３，δ１，δ２，δ３をランダムに選択する処理を繰り返す。Ｎｏの場合には、次の処理に進む。
【００３１】
階層秘密鍵生成部３４０−ｋは、復号鍵生成手段３５０−ｋ、引継情報生成手段３６０−ｋ、秘密鍵生成手段３７０−ｋを備え、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を生成する。復号鍵生成手段３５０−ｋは、Ｓｄ（ｋ）を、
【００３２】
【数１５】
2010161523.tif 000017
のように求める（Ｓ３５０−ｋ）。引継情報生成手段３６０−ｋは、Ｓｒ（ｋ）を、
【００３３】
【数１６】
2010161523.tif 000018
のように求める（Ｓ３６０−ｋ）。秘密鍵生成手段３７０−ｋは自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を
Ｓ（ｋ）←［Ｓｄ（ｋ），Ｓｒ（ｋ）］
のように求める（Ｓ３７０−ｋ）。復号化部３９０−ｋは、階層秘密鍵Ｓ（ｋ）のはじめの３つの要素をＡ０，Ａ１，Ａ２とすると、暗号文Ｃ（ｋ）を
【００３４】
【数１７】
2010161523.tif 000019
のように平文Ｍに復号する（Ｓ３９０−ｋ）。
【００３５】
１番目の階層の復号化装置３００−１は、図１の例では鍵生成装置１００と同一の装置である。図２中に点線で示した構成部が１番目の階層の復号化装置３００−１として機能する構成部である。具体的には、復号化記録部３１０−１と復号化部３９０−１である。復号化記録部３１０は、階層秘密鍵生成部１４０が生成した１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）、受信した暗号文Ｃ（１）を記録する。復号化部３９０−１は、階層秘密鍵Ｓ（１）のはじめの３つの要素をＡ０，Ａ１，Ａ２とし、暗号文Ｃ（１）を
【００３６】
【数１８】
2010161523.tif 000020
のように平文Ｍに復号する（Ｓ３９０−１）。なお、図１の例は１番目の階層の復号化装置は鍵生成装置と同一としたが、別の装置としてもよい。別の装置とする場合には、復号化装置３００−１は鍵生成装置１００から、１番目の階層の復号化装置用の階層秘密鍵Ｓ（１）を受け取っておく必要がある。
検証
【００３７】
【数１９】
2010161523.tif 000021
によって平文Ｍが求められることを確認する。
まず、鍵生成装置１００の階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）で確認する。階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００３８】
【数２０】
2010161523.tif 000022
また、Ｃ１，Ｃ２，Ｃ３，Ｃ４は、次のとおりである。
【００３９】
【数２１】
2010161523.tif 000023
したがって、
【００４０】
【数２２】
2010161523.tif 000024
は、次のようになる。
【００４１】
【数２３】
2010161523.tif 000025
【００４２】
また、階層秘密鍵生成部３４０−ｋは、自己の（ｋ番目の階層の復号化装置３００−ｋ用の）階層秘密鍵Ｓ（ｋ）を、ｋ−１番目の階層の復号化装置３００−ｋ−１用の階層秘密鍵Ｓ（ｋ−１）から生成する。また、
Ｓ（ｋ−１）は、
【００４３】
【数２４】
2010161523.tif 000026
であり、階層秘密鍵生成部３４０−ｋが求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２は、次のとおりである。
【００４４】
【数２５】
2010161523.tif 000027
したがって、
【００４５】
【数２６】
2010161523.tif 000028
となる。これらは、階層秘密鍵生成部１４０で求める階層秘密鍵Ｓ（ｋ）の最初の３つの要素Ａ０，Ａ１，Ａ２
【００４６】
【数２７】
2010161523.tif 000029
と同じである。
つまり、ｋ番目（ただし、２番目以降）の階層の復号化装置は、自己（ｋ番目）よりも上位の階層の復号化装置の識別情報Ｄ１，…，Ｄｋ−１を知らなくても暗号文Ｃ（ｋ）を復号化できる。よって、暗号文Ｃ（ｋ）と一緒にＩＤ（復号化装置の識別情報）を送信する必要がなく、ＩＤ（復号化装置の識別情報）を秘匿化できる。また、暗号文Ｃ（ｋ）は、
【００４７】
【数２８】
2010161523.tif 000030
なので、暗号文Ｃ（ｋ）の長さは階層に依存しない。
【００４８】
図８に、コンピュータの機能構成例を示す。なお、本発明の鍵生成装置、暗号化装置および復号化装置は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、処理部２０１０、入力部２０３０、出力部２０４０などを動作させることで実現できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００４９】
本発明は、２台以上の通信装置の間で情報を暗号化して通信するような場合などに利用できる。
【符号の説明】
【００５０】
１００  鍵生成装置                          １１０  鍵生成記録部
１２０  公開鍵生成部                        １３０  鍵生成ランダム値選択部
１４０  階層秘密鍵生成部                    １５０  復号鍵生成手段
１６０  引継情報生成手段                    １７０  秘密鍵生成手段
２００  暗号化装置                          ２１０  暗号化記録部
２３０  暗号化ランダム値選択部              ２８０  暗号化部
３００  復号化装置                          ３１０  復号化記録部
３３０  復号化ランダム値選択部              ３４０  階層秘密鍵生成部
３５０  復号鍵生成手段                      ３６０  引継情報生成手段
３７０  秘密鍵生成手段                      ３９０  復号化部
【図１】
2010161523.tif 000077
【図２】
2010161523.tif 000078
【図３】
2010161523.tif 000079
【図４】
2010161523.tif 000080
【図５】
2010161523.tif 000081
【図６】
2010161523.tif 000082
【図７】
2010161523.tif 000083
【図８】
2010161523.tif 000084