(57)【要約】【課題】OR-proofを用いた安全性証明が可能であり、安全性を強化した階層型IDベース認証システムを提供する。【解決手段】鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる階層型IDベース認証システムであって、鍵発行局装置は、マスター公開鍵と、マスター秘密鍵と、ルート秘密鍵を生成し、パースを実行して、第1秘密鍵を生成し、中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、パースを実行し、第n+1秘密鍵を生成し、証明者装置は、パースを実行し、コミットメントを生成し、チャレンジを生成し、シュミレーションを生成し、チャレンジを分割し、レスポンスを生成し、検証者装置は、パースを実行し、チャレンジを生成し、チャレンジを分割し、検証を実行することを特徴とする。【選択図】図１
2014078796.tif 000002
【特許請求の範囲】
【請求項１】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる階層型IDベース認証システムであって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行してマスター公開鍵mpk'と、マスター秘密鍵msk'を生成するマスター鍵生成部と、
ルート秘密鍵sk[id(0)]=(msk',msk')を生成するルート秘密鍵生成部と、
mpk=mpk'に、sk[id(0)]=(sk'[0.id(0)],sk'[1.id(0)])にパースするパース部と、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b.id(1)]←KG'(mpk',sk'[b.id(0)],b.id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0.id(1)],sk'[1.id(1)])を生成する第1秘密鍵生成部とを備え、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=mpk'に、sk[id(n)]=(sk'[0.id(n)],sk'[1.id(n)])にパースするパース部と、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b.id(n+1)]←KG'(mpk',sk'[b.id(n)],b.id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0.id(n+1)],sk'[1.id(n+1)])を生成する第n+1秘密鍵生成部とを備え、
証明者装置は、
mpk=mpk'に、sk[id(k)]=(sk'[0.id(k)],sk'[1.id(k)])にパースするパース部と、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b.id(k),sk'[b.id(k)])を実行するコミットメント生成部と、
b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
(ab~,zb~)←Σhibi-sim(mpk',b~.id(k),cb~)を実行するシミュレーション生成部と、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割部と、
zb←Σhibi-res(mpk',b.id(k),sk'[b.id(k)],ab,cb,st)を実行するレスポンス生成部とを備え、
検証者装置は、
mpk=mpk'にパースするパース部と、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割部と、
dec0←Σhibi-vrfy(mpk',0.id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1.id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証部と、
を備えることを特徴とする階層型IDベース認証システム。
【請求項２】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる階層型IDベース認証システムであって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
i○id(x)は、(i,I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行して、各b∈{0,1}について、sk'[(b)]←KG'(mpk',msk',(b))とし、マスター公開鍵mpk'と、マスター秘密鍵(sk'[0],sk'[1])を生成するマスター鍵生成部と、
ルート秘密鍵sk[id(0)]=(sk'[0],sk'[1])を生成するルート秘密鍵生成部と、
mpk=mpk'に、sk[id(0)]=(sk'[0○id(0)],sk'[1○id(0)])にパースするパース部と、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b○id(1)]←KG'(mpk',sk'[b○id(0)],b○id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0○id(1)],sk'[1○id(1)])を生成する第1秘密鍵生成部とを備え、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=mpk'に、sk[id(n)]=(sk'[0○id(n)],sk'[1○id(n)])にパースするパース部と、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b○id(n+1)]←KG'(mpk',sk'[b○id(n)],b○id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0○id(n+1)],sk'[1○id(n+1)])を生成する第n+1秘密鍵生成部とを備え、
証明者装置は、
mpk=mpk'に、sk[id(k)]=(sk'[0○id(k)],sk'[1○id(k)])にパースするパース部と、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b○id(k),sk'[b○id(k)])を実行するコミットメント生成部と、
b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
(ab~,zb~)←Σhibi-sim(mpk',b~○id(k),cb~)を実行するシミュレーション生成部と、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割部と、
zb←Σhibi-res(mpk',b○id(k),sk'[b○id(k)],ab,cb,st)を実行するレスポンス生成部とを備え、
検証者装置は、
mpk=mpk'にパースするパース部と、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割部と、
dec0←Σhibi-vrfy(mpk',0○id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1○id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証部と、
を備えることを特徴とする階層型IDベース認証システム。
【請求項３】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる階層型IDベース認証システムであって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行し、マスターIDであるidmasterを選択してマスター公開鍵(mpk',idmaster)、マスター秘密鍵msk'を生成するマスター鍵生成部と、
ルート秘密鍵sk[id(0)]=msk'を生成するルート秘密鍵生成部と、
mpk=(mpk',idmaster)にパースし、id(1)=idmasterであればreject⊥を出力して停止し、そうでなければsk[id(0)]=sk[id(0)]'にパースするパース部と、
第1装置のIDであるid(1)を取得して、sk[id(1)]'←KG'(mpk',sk[id(0)]',id(1))を実行し、第1秘密鍵sk[id(1)]=sk[id(1)]'を生成する第1秘密鍵生成部とを備え、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=(mpk',idmaster)にパースし、id(n+1)=idmasterであればreject⊥を出力して停止し、そうでなければsk[id(n)]=sk[id(n)]'にパースするパース部と、
装置のIDであるid(n+1)を取得して、sk[id(n+1)]'←KG'(mpk',sk[id(n)]',id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=sk[id(n+1)]'を生成する第n+1秘密鍵生成部とを備え、
証明者装置は、
mpk=(mpk',idmaster)に、sk[id(k)]=sk[id(k)]'にパースするパース部と、
(a0,st)←Σhibi-com(mpk',id(k),sk[id(k)]')を実行するコミットメント生成部と、
c2←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
(a1,z1)←Σhibi-sim(mpk',idmaster,c2)を実行するシミュレーション生成部と、
検証者装置からチャレンジcを取得して、チャレンジの分割c0=c-c2を実行するチャレンジ分割部と、
z0←Σhibi-res(mpk',id(k),sk[id(k)]',a0,c0,st)を実行するレスポンス生成部とを備え、
検証者装置は、
mpk=(mpk',idmaster)にパースするパース部と、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成部と、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割部と、
dec0←Σhibi-vrfy(mpk',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',idmaster,a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証部と、
を備えることを特徴とする階層型IDベース認証システム。
【請求項４】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる階層型IDベース認証システムであって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
c←Σ*hibi-ch(1κ)を、セキュリティパラメータ1κからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Strongly special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk0',msk0')←SetUp'(1κ)および(mpk1',msk1')←SetUp'(1κ)を実行してマスター公開鍵(1κ,mpk0',mpk1')と、マスター秘密鍵(msk0',msk1')を生成するマスター鍵生成部と、
ルート秘密鍵sk[id(0)]=(msk0',msk1')を生成するルート秘密鍵生成部と、
mpk=(1κ,mpk0',mpk1')に、sk[id(0)]=(sk0'[id(0)],sk1'[id(0)])にパースするパース部と、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、skb'[id(1)]←KG'(mpkb',skb'[id(0)],id(1))を実行し、第1秘密鍵sk[id(1)]=(sk0'[id(1)],sk1'[id(1)])を生成する第1秘密鍵生成部とを備え、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=(1κ,mpk0',mpk1')に、sk[id(n)]=(sk0'[id(n)],sk1'[id(n)])にパースするパース部と、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、skb'[id(n+1)]←KG'(mpkb',skb'[id(n)],id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk0'[id(n+1)],sk1'[id(n+1)])を生成する第n+1秘密鍵生成部とを備え、
証明者装置は、
mpk=(1κ,mpk0',mpk1')に、sk[id(k)]=(sk0'[id(k)],sk1'[id(k)])にパースするパース部と、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpkb',id(k),skb'[id(k)])を実行するコミットメント生成部と、
b~を1-bとしてcb~←Σ*hibi-ch(1κ)を実行するチャレンジ生成部と、
(ab~,zb~)←Σhibi-sim(mpkb~',id(k),cb~)を実行するシミュレーション生成部と、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割部と、
zb←Σhibi-res(mpkb',id(k),skb'[id(k)],ab,cb,st)を実行するレスポンス生成部とを備え、
検証者装置は、
mpk=(1κ,mpk0',mpk1')にパースするパース部と、
c←Σ*hibi-ch(1κ)を実行するチャレンジ生成部と、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割部と、
dec0←Σhibi-vrfy(mpk0',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk1',id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証部と、
を備えることを特徴とする階層型IDベース認証システム。
【請求項５】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とが実行する階層型IDベース認証方法であって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行してマスター公開鍵mpk'と、マスター秘密鍵msk'を生成するマスター鍵生成ステップと、
ルート秘密鍵sk[id(0)]=(msk',msk')を生成するルート秘密鍵生成ステップと、
mpk=mpk'に、sk[id(0)]=(sk'[0.id(0)],sk'[1.id(0)])にパースするパースステップと、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b.id(1)]←KG'(mpk',sk'[b.id(0)],b.id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0.id(1)],sk'[1.id(1)])を生成する第1秘密鍵生成ステップとを実行し、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=mpk'に、sk[id(n)]=(sk'[0.id(n)],sk'[1.id(n)])にパースするパースステップと、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b.id(n+1)]←KG'(mpk',sk'[b.id(n)],b.id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0.id(n+1)],sk'[1.id(n+1)])を生成する第n+1秘密鍵生成ステップとを実行し、
証明者装置は、
mpk=mpk'に、sk[id(k)]=(sk'[0.id(k)],sk'[1.id(k)])にパースするパースステップと、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b.id(k),sk'[b.id(k)])を実行するコミットメント生成ステップと、
b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
(ab~,zb~)←Σhibi-sim(mpk',b~.id(k),cb~)を実行するシミュレーション生成ステップと、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割ステップと、
zb←Σhibi-res(mpk',b.id(k),sk'[b.id(k)],ab,cb,st)を実行するレスポンス生成ステップとを実行し、
検証者装置は、
mpk=mpk'にパースするパースステップと、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割ステップと、
dec0←Σhibi-vrfy(mpk',0.id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1.id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証ステップと、
を実行することを特徴とする階層型IDベース認証方法。
【請求項６】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とが実行する階層型IDベース認証方法であって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
i○id(x)は、(i,I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行して、各b∈{0,1}について、sk'[(b)]←KG'(mpk',msk',(b))とし、マスター公開鍵mpk'と、マスター秘密鍵(sk'[0],sk'[1])を生成するマスター鍵生成ステップと、
ルート秘密鍵sk[id(0)]=(sk'[0],sk'[1])を生成するルート秘密鍵生成ステップと、
mpk=mpk'に、sk[id(0)]=(sk'[0○id(0)],sk'[1○id(0)])にパースするパースステップと、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b○id(1)]←KG'(mpk',sk'[b○id(0)],b○id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0○id(1)],sk'[1○id(1)])を生成する第1秘密鍵生成ステップとを実行し、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=mpk'に、sk[id(n)]=(sk'[0○id(n)],sk'[1○id(n)])にパースするパースステップと、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b○id(n+1)]←KG'(mpk',sk'[b○id(n)],b○id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0○id(n+1)],sk'[1○id(n+1)])を生成する第n+1秘密鍵生成ステップとを実行し、
証明者装置は、
mpk=mpk'に、sk[id(k)]=(sk'[0○id(k)],sk'[1○id(k)])にパースするパースステップと、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b○id(k),sk'[b○id(k)])を実行するコミットメント生成ステップと、
b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
(ab~,zb~)←Σhibi-sim(mpk',b~○id(k),cb~)を実行するシミュレーション生成ステップと、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割ステップと、
zb←Σhibi-res(mpk',b○id(k),sk'[b○id(k)],ab,cb,st)を実行するレスポンス生成ステップとを実行し、
検証者装置は、
mpk=mpk'にパースするパースステップと、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割ステップと、
dec0←Σhibi-vrfy(mpk',0○id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1○id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証ステップと、
を実行することを特徴とする階層型IDベース認証方法。
【請求項７】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とが実行する階層型IDベース認証方法であって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行し、マスターIDであるidmasterを選択してマスター公開鍵(mpk',idmaster)、マスター秘密鍵msk'を生成するマスター鍵生成ステップと、
ルート秘密鍵sk[id(0)]=msk'を生成するルート秘密鍵生成ステップと、
mpk=(mpk',idmaster)にパースし、id(1)=idmasterであればreject⊥を出力して停止し、そうでなければsk[id(0)]=sk[id(0)]'にパースするパースステップと、
第1装置のIDであるid(1)を取得して、sk[id(1)]'←KG'(mpk',sk[id(0)]',id(1))を実行し、第1秘密鍵sk[id(1)]=sk[id(1)]'を生成する第1秘密鍵生成ステップとを実行し、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=(mpk',idmaster)にパースし、id(n+1)=idmasterであればreject⊥を出力して停止し、そうでなければsk[id(n)]=sk[id(n)]'にパースするパースステップと、
装置のIDであるid(n+1)を取得して、sk[id(n+1)]'←KG'(mpk',sk[id(n)]',id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=sk[id(n+1)]'を生成する第n+1秘密鍵生成ステップとを実行し、
証明者装置は、
mpk=(mpk',idmaster)に、sk[id(k)]=sk[id(k)]'にパースするパースステップと、
(a0,st)←Σhibi-com(mpk',id(k),sk[id(k)]')を実行するコミットメント生成ステップと、
c2←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
(a1,z1)←Σhibi-sim(mpk',idmaster,c2)を実行するシミュレーション生成ステップと、
検証者装置からチャレンジcを取得して、チャレンジの分割c0=c-c2を実行するチャレンジ分割ステップと、
z0←Σhibi-res(mpk',id(k),sk[id(k)]',a0,c0,st)を実行するレスポンス生成ステップとを実行し、
検証者装置は、
mpk=(mpk',idmaster)にパースするパースステップと、
c←Σ+hibi-ch(mpk')を実行するチャレンジ生成ステップと、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割ステップと、
dec0←Σhibi-vrfy(mpk',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',idmaster,a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証ステップと、
を実行することを特徴とする階層型IDベース認証方法。
【請求項８】
鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とが実行する階層型IDベース認証方法であって、
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とし、
x=1,2,…,kとし、
sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とし、
(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とし、
c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とし、
c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
c←Σ*hibi-ch(1κ)を、セキュリティパラメータ1κからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Strongly special challengeを同時に満たす確率的多項式時間アルゴリズムとし、
(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とし、
z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とし、
dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とし、
bを0と1の間の一様分布に従って選んだ乱数とし、
id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとし、
鍵発行局装置は、
セキュリティパラメータ1κを取得して(mpk0',msk0')←SetUp'(1κ)および(mpk1',msk1')←SetUp'(1κ)を実行してマスター公開鍵(1κ,mpk0',mpk1')と、マスター秘密鍵(msk0',msk1')を生成するマスター鍵生成ステップと、
ルート秘密鍵sk[id(0)]=(msk0',msk1')を生成するルート秘密鍵生成ステップと、
mpk=(1κ,mpk0',mpk1')に、sk[id(0)]=(sk0'[id(0)],sk1'[id(0)])にパースするパースステップと、
第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、skb'[id(1)]←KG'(mpkb',skb'[id(0)],id(1))を実行し、第1秘密鍵sk[id(1)]=(sk0'[id(1)],sk1'[id(1)])を生成する第1秘密鍵生成ステップとを実行し、
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、
mpk=(1κ,mpk0',mpk1')に、sk[id(n)]=(sk0'[id(n)],sk1'[id(n)])にパースするパースステップと、
装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、skb'[id(n+1)]←KG'(mpkb',skb'[id(n)],id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk0'[id(n+1)],sk1'[id(n+1)])を生成する第n+1秘密鍵生成ステップとを実行し、
証明者装置は、
mpk=(1κ,mpk0',mpk1')に、sk[id(k)]=(sk0'[id(k)],sk1'[id(k)])にパースするパースステップと、
b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpkb',id(k),skb'[id(k)])を実行するコミットメント生成ステップと、
b~を1-bとしてcb~←Σ*hibi-ch(1κ)を実行するチャレンジ生成ステップと、
(ab~,zb~)←Σhibi-sim(mpkb~',id(k),cb~)を実行するシミュレーション生成ステップと、
検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行するチャレンジ分割ステップと、
zb←Σhibi-res(mpkb',id(k),skb'[id(k)],ab,cb,st)を実行するレスポンス生成ステップとを実行し、
検証者装置は、
mpk=(1κ,mpk0',mpk1')にパースするパースステップと、
c←Σ*hibi-ch(1κ)を実行するチャレンジ生成ステップと、
証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行するチャレンジ分割ステップと、
dec0←Σhibi-vrfy(mpk0',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk1',id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する検証ステップと、
を実行することを特徴とする階層型IDベース認証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術の分野における相手認証、特にメールアドレスや電話番号などのIDを公開鍵に用いる相手認証方式（階層型IDベース認証）における安全性を強化した階層型IDベース認証システム、階層型IDベース認証方法に関する。
【背景技術】
【０００２】
通信相手の正当性を確認する技術として相手認証の技術がある。相手認証を実現する方式としては、パスワードを用いる方式や、デジタル署名を用いたプロトコル（SIプロトコル）のほかに、利用者の名前やメールアドレスなどのIDを公開鍵に用いるIDベース認証プロトコル(以下IBIプロトコル)がある。一般的に、IBIプロトコルは、鍵発行局・証明者・検証者の三者から構成される。鍵発行局は証明者のIDに対応する秘密鍵sk[id]を証明者に発行し、証明者と検証者が通信することで、検証者が「証明者IDが対応したsk[id]を持っていること」を検証することができる技術である。
【０００３】
さらにIBIプロトコルを階層化したものがHIBIプロトコルである。IBIプロトコルでの鍵発行局の負担を階層化することで軽減することができる。HIBIプロトコルにおける安全性は攻撃の強さにより定義され、最も強い安全性は、並列攻撃に対してなりすましができないこと（secure against impersonation under concurrent attacks、以下「imp-ca安全」）である。また、弱い安全性の定義としては、受動的攻撃に対してなりすましができないこと（secure against impersonation under passive attacks、以下「imp-pa安全」）がある。imp-caとimp-paの違いは、大まかに言えば、imp-caで想定している攻撃者がHIBIプロトコルを利用している全ての利用者にいつでも並列的にアクセスし、操作することが許されているのに対し、imp-paで想定している攻撃者はHIBIプロトコルの利用者間の通信履歴の盗聴のみが許されている点にある（詳細な定義は非特許文献1や非特許文献3を参照）。現実の利用を想定した場合、より高い安全性を持ったimp-ca安全性のHIBIプロトコルであることが望ましい。HIBIプロトコルにおいてこの問題を解決するために、Chinらは、非特許文献3においてHIBIプロトコルを提案し、そのプロトコルのimp-pa安全性とimp-ca安全性にある数学的な問題の求解困難性を仮定して証明している。ただし、この構成は特定の一方式に基づく構成であり、汎用的な構成方法は示されていない。また、この方式は安全性証明にランダムオラクルモデル（非特許文献2参照）と呼ばれる特殊な安全性モデルを利用している。また、IBIプロトコルにおいては、藤岡らは非特許文献5において、imp-pa安全なIBIプロトコルをもとにimp-ca安全なIBIプロトコルを構成する手法を提示している。これらの構成は5つあるが、いずれもIBIプロトコルに対するもので、HIBIプロトコルでの構成は未解決であった。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Mihir Bellare, Chanathip Namprempre, and Gregory Neven. Security proofs for identity-based identification and signature schemes. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT2004, volume 3027 of Lecture Notes in Computer Science, pages 268-286. Springer-Verlag, 2004.
【非特許文献２】Mihir Bellare and Phillip Rogaway. Random oracle are practical: A paradigm for designing efficient protocols. In CCS '93, pages 62-73. ACM, 1993.
【非特許文献３】Ji-Jian Chin, Swee-Huay Heng, and Bok-Min Goi. Hierarchical identity-based identification schemes.In Dominik Slezak, Tai-Hoon Kim, Wai-Chi Fang, and Kirk P. Arnett, editors, FGIT-SecTech 2009,volume 58 of Communications in Computer and Information Science, pages 93-99. Springer-Verlag,2009.
【非特許文献４】Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In STOC '90,pages 416-426. ACM, 1990.
【非特許文献５】Atsushi Fujioka, Taiichi Saito, and Keita Xagawa. Security enhancements by OR-proof in identity-based identification. In Feng Bao, Pierangela Samarati, and Jianying Zhou, editors, ACNS 2012,volume 7341 of Lecture Notes in Computer Science, pages 135-152. Springer-Verlag, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
imp-pa安全性をもつSIプロトコルからimp-ca安全性をもつSIプロトコルを構成する方法にOR-proof（非特許文献4参照）と呼ばれる方法がある。HIBIプロトコルにOR-proofを応用できればHIBIプロトコルの安全性が強化されるが、HIBIプロトコルにOR-proofを応用するためには、秘密鍵を2つ生成する必要があり、このときに装置のIDをどのように分岐させれば、HIBIプロトコルにOR-proofを容易に適用可能となるかが知られておらず、HIBIプロトコルにOR-proofを応用することができなかった。そこで本発明では、OR-proofを用いた安全性証明が可能であり、安全性を強化した階層型IDベース認証システムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の階層型IDベース認証システムは、鍵発行局装置と、k-1個(kは2以上の整数)の第1装置、…、第(k-1)装置よりなる中間鍵発行局装置と、証明者装置と、検証者装置とからなる。
【０００７】
(mpk,msk)←SetUp(1κ)をセキュリティパラメータ1κからマスター公開鍵mpkと、マスター秘密鍵mskを得る写像とする。x=1,2,…,kとし、sk[id(x)]←KG(mpk,sk[id(x-1)],id(x))をマスター公開鍵mpk、秘密鍵sk[id(x-1)]、装置のIDであるid(x)から第x秘密鍵sk[id(x)]を得る写像とする。(a,st)←Σhibi-com(mpk,id,sk[id])を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]からコミットメントa、証明者装置の内部状態stを得る写像とする。c←Σhibi-ch(mpk,id)を、マスター公開鍵mpk、装置のIDであるidからチャレンジcを得る写像とする。c←Σ+hibi-ch(mpk)を、マスター公開鍵mpkからチャレンジcを得る写像であって、Special zero-knowledge, Special soundness, Special challengeを同時に満たす確率的多項式時間アルゴリズムとする。(a,z)←Σhibi-sim(mpk,id,c)を、マスター公開鍵mpk、装置のIDであるid、チャレンジcからコミットメントa、レスポンスzを得る写像とする。z←Σhibi-res(mpk,id,sk[id],a,c,st)を、マスター公開鍵mpk、装置のIDであるid、秘密鍵sk[id]、コミットメントa、チャレンジc、証明者装置の内部状態stからレスポンスzを得る写像とする。dec←Σhibi-vrfy(mpk,id,a,c,z)をマスター公開鍵mpk、装置のIDであるid、コミットメントa、チャレンジc、レスポンスzから検証結果decを得る写像とする。bを0と1の間の一様分布に従って選んだ乱数とする。id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとする。
【０００８】
鍵発行局装置は、マスター鍵生成部と、ルート秘密鍵生成部と、パース部と、第1秘密鍵生成部とを備える。
【０００９】
マスター鍵生成部は、セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行してマスター公開鍵mpk'と、マスター秘密鍵msk'を生成する。ルート秘密鍵生成部は、ルート秘密鍵sk[id(0)]=(msk',msk')を生成する。パース部は、mpk=mpk'に、sk[id(0)]=(sk'[0.id(0)],sk'[1.id(0)])にパースする。第1秘密鍵生成部は、第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b.id(1)]←KG'(mpk',sk'[b.id(0)],b.id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0.id(0)],sk'[1.id(0)]を生成する。
【００１０】
中間鍵発行局装置の第n(n=1,2,…,k-1)装置は、パース部と、第n+1秘密鍵生成部とを備える。
【００１１】
パース部は、mpk=mpk'に、sk[id(n)]=(sk'[0.id(n)],sk'[1.id(n)])にパースする。第n+1秘密鍵生成部は、装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b.id(n+1)]←KG'(mpk',sk'[b.id(n)],b.id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0.id(n)],sk'[1.id(n)]を生成する。
【００１２】
証明者装置は、パース部と、コミットメント生成部と、チャレンジ生成部と、シミュレーション生成部と、チャレンジ分割部と、レスポンス生成部とを備える。
【００１３】
パース部は、mpk=mpk'に、sk[id(k)]=(sk'[0.id(k)],sk'[1.id(k)])にパースする。コミットメント生成部は、b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b.id(k),sk'[b.id(k)])を実行する。チャレンジ生成部は、b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行する。シミュレーション生成部は、(ab~,zb~)←Σhibi-sim(mpk',b~.id(k),cb~)を実行する。チャレンジ分割部は、検証者装置からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行する。レスポンス生成部は、zb←Σhibi-res(mpk',b.id(k),sk'[b.id(k)],ab,cb,st)を実行する。
【００１４】
検証者装置は、パース部と、チャレンジ生成部と、チャレンジ分割部と、検証部とを備える。
【００１５】
パース部は、mpk=mpk'にパースする。チャレンジ生成部は、c←Σ+hibi-ch(mpk')を実行する。チャレンジ分割部は、証明者装置からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行する。検証部は、dec0←Σhibi-vrfy(mpk',0.id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1.id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する。
【発明の効果】
【００１６】
本発明の階層型IDベース認証システムによれば、OR-proofを用いた安全性証明が可能であり、安全性を強化することができる。
【図面の簡単な説明】
【００１７】
【図１】実施例1の階層型IDベース認証システムの構成を示すブロック図。
【図２】実施例1の鍵発行局装置の構成を示すブロック図。
【図３】実施例1の第n装置の構成を示すブロック図。
【図４】実施例1の証明者装置の構成を示すブロック図。
【図５】実施例1の検証者装置の構成を示すブロック図。
【図６】実施例1の鍵発行局装置および第n装置の動作を示すシーケンス図。
【図７】実施例1の証明者装置および検証者装置の動作を示すシーケンス図。
【図８】実施例2の階層型IDベース認証システムの構成を示すブロック図。
【図９】実施例2の鍵発行局装置の構成を示すブロック図。
【図１０】実施例2の第n装置の構成を示すブロック図。
【図１１】実施例2の証明者装置の構成を示すブロック図。
【図１２】実施例2の鍵発行局装置および第n装置の動作を示すシーケンス図。
【図１３】実施例2の証明者装置および検証者装置の動作を示すシーケンス図。
【図１４】実施例3の階層型IDベース認証システムの構成を示すブロック図。
【図１５】実施例3の鍵発行局装置の構成を示すブロック図。
【図１６】実施例3の第n装置の構成を示すブロック図。
【図１７】実施例3の証明者装置の構成を示すブロック図。
【図１８】実施例3の鍵発行局装置および第n装置の動作を示すシーケンス図。
【図１９】実施例3の証明者装置および検証者装置の動作を示すシーケンス図。
【図２０】実施例4の階層型IDベース認証システムの構成を示すブロック図。
【図２１】実施例4の鍵発行局装置の構成を示すブロック図。
【図２２】実施例4の第n装置の構成を示すブロック図。
【図２３】実施例4の証明者装置の構成を示すブロック図。
【図２４】実施例4の検証者装置の構成を示すブロック図。
【図２５】実施例4の鍵発行局装置および第n装置の動作を示すシーケンス図。
【図２６】実施例4の証明者装置および検証者装置の動作を示すシーケンス図。
【図２７】各実施例の階層型IDベース認証システムが何れの攻撃のバリエーションに適応可能に構成されているかを示す図。
【発明を実施するための形態】
【００１８】
［準備］
以下、本明細書で使用する用語について説明する。
【００１９】
＜階層型IDベース認証プロトコル＞
階層型IDベース認証プロトコル(Hierarchical Identity-Based Identificaiton protocol:HIBI protocol)とは、利用者の階層的なIDを公開鍵に用いることのできる相手認証方式である。一般的に、階層型IDベース認証プロトコルは、鍵発行局・中間鍵発行局・証明者・検証者の四者から構成される。中間鍵発行局は階層的なIDであるid(k-1)=(I1,I2,…,Ik-1)を持ち、一つ下位のIDであるid(k)=(I1,I2,…,Ik)に対応する秘密鍵sk[id(k)]を証明者もしくは下位の中間鍵発行局に発行し、証明者と検証者が通信することで、検証者が「証明者ID(id(k))が対応したsk[id(k)]を持っていること」を検証することができる技術である。より形式的には、階層型IDベース認証は次の4つの確率的多項式時間アルゴリズムHIBI=(SetUp,KG,P,V)から構成される。
【００２０】
SetUp(マスター鍵生成アルゴリズム)：セキュリティパラメータ1κを入力として、マスター秘密鍵mskおよびマスター公開鍵mpkを出力する。簡単のため、以下、sk[id(0)]=mskとおく。
【００２１】
KG(ユーザ鍵生成アルゴリズム):mpkとsk[id(k-1)]とユーザIDであるid(k)を入力とする。ここでid(k-1)=(I1,I2,…,Ik-1)、id(k)=(I1,I2,…,Ik)である。このアルゴリズムはid(k)に対応する秘密鍵sk[id(k)]を出力する。
【００２２】
P(証明者アルゴリズム):(mpk,id(k),sk[id(k)])を入力とし、Vと通信する。
【００２３】
V(検証者アルゴリズム):(mpk,id(k))を入力として、Pと通信し、最終的に証明者がsk[id(k)]を持っていることが検証できれば「受理(accept)」、そうでなければ「拒否(reject)」を出力する。
【００２４】
上記のうち、鍵発行局はSetUpとKGを、(中間鍵)発行局はKGを、証明者はPを、検証者はVをそれぞれ実行する。
【００２５】
＜Σ+型および、Σ*型IBIプロトコル＞
ここでは、HIBIプロトコルHIBI=(SetUp,KG,P,V)として、PとVの通信が3回で完了し、PとVは、以下の確率的多項式時間アルゴリズム(Σhibi-com,Σhibi-ch,Σhibi-res,Σhibi-vrfy)を利用するプロトコル（標準的HIBIプロトコル）を対象とする。
P→V:Pは(a,st)←Σhibi-com(mpk,id,sk[id])を計算し、コミットメントaをVに送信する（stはPの内部状態）。
V→P:Vはチャレンジc←Σhibi-ch(mpk,id)を計算し、cをPに送信する。
P→V:Pはレスポンスz←Σhibi-res(mpk,id,sk[id],a,c,st)を計算し、zをVに送信する。
V:Vは検証結果dec←Σhibi-vrfy(mpk,id,a,c,z)を計算し、dec∈{accept,reject}を出力する。
【００２６】
標準的HIBIプロトコルのうち、以下の3つの性質（special zero-knowledge,special soundness、special challenge）を同時に満たすHIBIプロトコルをHIBIΣ+-typeと呼ぶ。
Special zero-knowledge:チャレンジc、マスター公開鍵mpk、およびIDであるidから、受理可能な通信履歴を計算できる。つまり、mpk、idおよびc←Σhibi-ch(mpk,id)を満たすcを入力として、accept=Σhibi-vrfy(mpk,id,a,c,z)を満たすコミットメントとレスポンス(a,z)を出力する確率的多項式時間アルゴリズムΣhibi-simを構成できる。ここで、Σhibi-chとΣhibi-simの出力の確率分布は、実際のプロトコルの出力の分布と識別不可能である。
Special soundness:マスター公開鍵mpkとidと2つの通信履歴(a,c,z)(a,c',z')(ただし、c≠c')から、idに対応する秘密鍵sk[id]を計算できる。つまり、mpkとidとaccept=Σhibi-vrfy(mpk,id,a,c,z)=Σhibi-vrfy(mpk,id,a,c',z')を満たす2つの通信履歴(a,c,z)、(a,c',z')を入力とし、sk[id]を出力する確率的多項式時間アルゴリズムΣhibi-extを構成することができる。
Special challenge:Σhibi-chはマスター公開鍵mpkのみに依存し（つまりidには非依存）、その出力であるチャレンジcはある可換群Gの要素であって、出力の分布はG上の一様分布である。さらに、Gの群演算+は多項式時間で実行できる。つまり、mpkのみを入力とし、cを出力する確率的多項式時間アルゴリズムΣ+hibi-chがあって、その出力はG上の一様分布である。また、上記のHIBIΣ+-typeの性質において、special challenge を以下のStrongly special challenge に置き換えたHIBIプロトコルをHIBIΣ*型と呼ぶ。
Strongly special challenge: Σhibi-chはセキュリティパラメータ1κのみに依存し（つまりmpkとidには非依存）、その出力であるチャレンジcはある可換群Gの要素であって、出力の分布はG上の一様分布である。さらに、Gの群演算+は多項式時間で実行できる。つまり、1κのみを入力とし、cを出力する確率的多項式時間アルゴリズムΣ*hibi-chがあって、その出力はG上の一様分布である。
【００２７】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２８】
以下、図1から図7を参照して本発明の実施例1の階層型IDベース認証システム1について説明する。図1は本実施例の階層型IDベース認証システム1の構成を示すブロック図である。図2は本実施例の鍵発行局装置11の構成を示すブロック図である。図3は本実施例の第n装置12-nの構成を示すブロック図である。図4は本実施例の証明者装置13の構成を示すブロック図である。図5は本実施例の検証者装置14の構成を示すブロック図である。図6は本実施例の鍵発行局装置11および第n(n=1,2,…,k-1)装置12-nの動作を示すシーケンス図である。図7は本実施例の証明者装置13および検証者装置14の動作を示すシーケンス図である。また、以下の実施例においてはbを0と1の間の一様分布に従って選んだ乱数とする。また、x=1,2,…,kとし、id(x)=(I1,I2,…,Ix)とし、b.id(x)は(b‖I1,I2,…,Ix)を示すものとする。
【００２９】
図1に示すように、本実施例の階層型IDベース認証システム1は、鍵発行局装置11と、k-1個(kは2以上の整数)の第1装置12-1、…、第(k-1)装置12-(k-1)よりなる中間鍵発行局装置12と、証明者装置13と、検証者装置14とからなる。
【００３０】
図2に示すように鍵発行局装置11は、マスター鍵生成部111と、ルート秘密鍵生成部112と、パース部113と、第1秘密鍵生成部114とを備える。
【００３１】
マスター鍵生成部111は、セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行してマスター公開鍵mpk'と、マスター秘密鍵msk'を生成する(S111)。ルート秘密鍵生成部112は、ルート秘密鍵sk[id(0)]=(msk',msk')を生成する(S112)。パース部113は、mpk=mpk'に、sk[id(0)]=(sk'[0.id(0)],sk'[1.id(0)])にパースする(S113)。第1秘密鍵生成部114は、第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b.id(1)]←KG'(mpk',sk'[b.id(0)],b.id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0.id(1)],sk'[1.id(1)]を生成する(S114)。
【００３２】
図3に示すように中間鍵発行局装置12の第n(n=1,2,…,k-1)装置12-nは、パース部123-nと、第n+1秘密鍵生成部124-nと、ID記憶部125-nとを備える。
【００３３】
パース部123-nは、mpk=mpk'に、sk[id(n)]=(sk'[0.id(n)],sk'[1.id(n)])にパースする(123-n)。第n+1秘密鍵生成部124-nは、装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b.id(n+1)]←KG'(mpk',sk'[b.id(n)],b.id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0.id(n+1)],sk'[1.id(n+1)]を生成する(S124-n)。下位の装置から取得したid(n+1)はID記憶部125-nに一時記憶しておく。ID記憶部125-nには、自身のIDであるid(n)を記憶しておいてもよい。
【００３４】
図4に示すように証明者装置13は、パース部133と、ID記憶部135と、コミットメント生成部136-1と、チャレンジ生成部136-2と、シミュレーション生成部136-3と、チャレンジ受信部137-1と、レスポンス送信部137-2と、ID送信部137-3と、コミットメント送信部137-4と、チャレンジ分割部138と、レスポンス生成部139とを備える。以下、136-1から136-3をまとめて検証用データ生成部136と呼ぶ。以下、137-1から137-4をまとめて検証用データ送受信部137と呼ぶ。
【００３５】
パース部133は、mpk=mpk'に、sk[id(k)]=(sk'[0.id(k)],sk'[1.id(k)])にパースする(S133)。ID送信部137-3は、証明者装置13のIDであるid(k)を送信する(S137-3)。コミットメント生成部136-1は、b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b.id(k),sk'[b.id(k)])を実行する(S136-1)。チャレンジ生成部136-2は、b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行する(S136-2)。シミュレーション生成部136-3は、(ab~,zb~)←Σhibi-sim(mpk',b~.id(k),cb~)を実行する(S136-3)。コミットメント送信部137-4は、コミットメント(a0,a1)を送信する(S137-4)。チャレンジ受信部137-1はチャレンジcを受信する(S137-1)。チャレンジ分割部138は、チャレンジcを取得して、チャレンジの分割cb=c-cb~を実行する(S138)。レスポンス生成部139は、zb←Σhibi-res(mpk',b.id(k),sk'[b.id(k)],ab,cb,st)を実行する(S139)。レスポンス送信部137-2は、レスポンス(c0,z0,z1)を送信する(S137-2)。
【００３６】
図5に示すように検証者装置14は、パース部143と、チャレンジ生成部146と、チャレンジ送信部147-1と、レスポンス受信部147-2と、ID受信部147-3と、コミットメント受信部147-4と、チャレンジ分割部148と、検証部149とを備える。以下、147-1から147-4をまとめて検証用データ送受信部147と呼ぶ。
【００３７】
パース部143は、mpk=mpk'にパースする(S143)。ID受信部147-3は、証明者装置13のIDであるid(k)を受信する(S147-3)。コミットメント受信部147-4は、コミットメント(a0,a1)を受信する(S147-4)。チャレンジ生成部146は、c←Σ+hibi-ch(mpk')を実行する(S146)。チャレンジ送信部147-1はチャレンジcを送信する(S147-1)。レスポンス受信部147-2は、レスポンス(c0,z0,z1)を受信する(S147-2)。チャレンジ分割部148は、チャレンジc0を取得して、チャレンジの分割c1=c-c0を実行する(S148)。検証部149は、dec0←Σhibi-vrfy(mpk',0.id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1.id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する(S149)。
【００３８】
このように、本実施例の階層型IDベース認証システム1によれば、OR-proofを用いた安全性証明が可能であり、安全性を強化することができる。
【実施例２】
【００３９】
以下、図8から図13を参照して本発明の実施例2の階層型IDベース認証システム2について説明する。図8は本実施例の階層型IDベース認証システム2の構成を示すブロック図である。図9は本実施例の鍵発行局装置21の構成を示すブロック図である。図10は本実施例の第n装置22-nの構成を示すブロック図である。図11は本実施例の証明者装置23の構成を示すブロック図である。図12は本実施例の鍵発行局装置21および第n装置22-nの動作を示すシーケンス図である。図13は本実施例の証明者装置23および検証者装置14の動作を示すシーケンス図である。
【００４０】
図8に示すように、本実施例の階層型IDベース認証システム2は、実施例1と異なる鍵発行局装置21と、実施例1と異なるk-1個(kは2以上の整数)の第1装置22-1、…、第(k-1)装置22-(k-1)よりなる中間鍵発行局装置22と、実施例1と異なる証明者装置23と、実施例1と同じ検証者装置14とからなる。以下、実施例1と異なる鍵発行局装置21、中間鍵発行局装置22、証明者装置23について説明する。本実施例の説明で用いる記号○については、例えばi○id(x)は、(i,I1,I2,…,Ix)を示すものとする。
【００４１】
図9に示すように鍵発行局装置21は、マスター鍵生成部211と、ルート秘密鍵生成部212と、パース部213と、第1秘密鍵生成部114とを備える。
【００４２】
マスター鍵生成部211はセキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行して、各b∈{0,1}について、sk'[(b)]←KG'(mpk',msk',(b))とし、マスター公開鍵mpk'と、マスター秘密鍵(sk'[0],sk'[1])を生成する(S211)。ルート秘密鍵生成部212は、ルート秘密鍵sk[id(0)]=(sk'[0],sk'[1])を生成する(S212)。パース部213は、mpk=mpk'に、sk[id(0)]=(sk'[0○id(0)],sk'[1○id(0)])にパースする(S213)。第1秘密鍵生成部114は、第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、sk'[b○id(1)]←KG'(mpk',sk'[b○id(0)],b○id(1))を実行し、第1秘密鍵sk[id(1)]=(sk'[0○id(1)],sk'[1○id(1)])を生成する(S114)。
【００４３】
図10に示すように中間鍵発行局装置22の第n(n=1,2,…,k-1)装置22-nは、パース部223-nと、第n+1秘密鍵生成部124-nと、ID記憶部125-nとを備える。
【００４４】
パース部223-nは、mpk=mpk'に、sk[id(n)]=(sk'[0○id(n)],sk'[1○id(n)])にパースする(S223-n)。第n+1秘密鍵生成部124-nは、装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、sk'[b○id(n+1)]←KG'(mpk',sk'[b○id(n)],b○id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk'[0○id(n+1)],sk'[1○id(n+1)])を生成する(S124-n)。
【００４５】
図11に示すように、証明者装置23は、パース部233と、ID記憶部135と、実施例1と同じ検証用データ生成部136と、検証用データ送受信部137と、チャレンジ分割部138と、レスポンス生成部139とを備える。
【００４６】
パース部233は、mpk=mpk'に、sk[id(k)]=(sk'[0○id(k)],sk'[1○id(k)])にパースする(S233)。コミットメント生成部136-1は、b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpk',b○id(k),sk'[b○id(k)])を実行する(S136-1)。チャレンジ生成部136-2は、b~を1-bとしてcb~←Σ+hibi-ch(mpk')を実行する(S136-2)。シミュレーション生成部136-3は、(ab~,zb~)←Σhibi-sim(mpk',b~○id(k),cb~)を実行する(S136-3)。チャレンジ分割部138は、検証者装置14からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行する(S138)。レスポンス生成部139は、zb←Σhibi-res(mpk',b○id(k),sk'[b○id(k)],ab,cb,st)を実行する(S139)。
【００４７】
検証者装置14は、実施例1と同じ構成であるため図示を省略する。パース部143は、mpk=mpk'にパースする(S143)。チャレンジ生成部146は、c←Σ+hibi-ch(mpk')を実行する(S146)。チャレンジ分割部148は、証明者装置23からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行する(S148)。検証部149は、dec0←Σhibi-vrfy(mpk',0○id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',1○id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する(S149)。
【００４８】
次に、図27を参照して、本実施例の階層型IDベース認証システム2が適応可能な攻撃のバリエーションについて説明する。図27は、各実施例の階層型IDベース認証システムが何れの攻撃のバリエーションに適応可能に構成されているかを示す図である。図27に示すように、実施例2の階層型IDベース認証システム2は全ての攻撃バリエーションに対して適応可能である。
【００４９】
このように、本実施例の階層型IDベース認証システム2によれば、実施例1の効果に加えて、全ての攻撃バリエーションに対して適応可能なHIBIプロトコルを構成できる。
【実施例３】
【００５０】
以下、図14から図19を参照して本発明の実施例3の階層型IDベース認証システム3について説明する。図14は本実施例の階層型IDベース認証システム3の構成を示すブロック図である。図15は本実施例の鍵発行局装置31の構成を示すブロック図である。図16は本実施例の第n装置32-nの構成を示すブロック図である。図17は本実施例の証明者装置33の構成を示すブロック図である。図18は本実施例の鍵発行局装置31および第n装置32-nの動作を示すシーケンス図である。図19は本実施例の証明者装置33および検証者装置14の動作を示すシーケンス図である。
【００５１】
図14に示すように、本実施例の階層型IDベース認証システム3は、実施例1と異なる鍵発行局装置31と、実施例1と異なるk-1個(kは2以上の整数)の第1装置32-1、…、第(k-1)装置32-(k-1)よりなる中間鍵発行局装置32と、実施例1と異なる証明者装置33と、実施例1と同じ検証者装置14とからなる。以下、実施例1と異なる鍵発行局装置31、中間鍵発行局装置32、証明者装置33について説明する。
【００５２】
図15に示すように鍵発行局装置31は、マスター鍵生成部311と、ルート秘密鍵生成部312と、パース部313と、第1秘密鍵生成部114とを備える。
【００５３】
マスター鍵生成部311は、セキュリティパラメータ1κを取得して(mpk',msk')←SetUp'(1κ)を実行し、マスターIDであるidmasterを選択してマスター公開鍵(mpk',idmaster)、マスター秘密鍵msk'を生成する(S311)。ルート秘密鍵生成部312は、ルート秘密鍵sk[id(0)]=msk'を生成する(S312)。パース部313は、mpk=(mpk',idmaster)にパースし、id(1)=idmasterであればreject⊥を出力して停止する。そうでなければsk[id(0)]=sk[id(0)]'にパースする(S313)。第1秘密鍵生成部114は、第1装置のIDであるid(1)を取得して、sk[id(1)]'←KG'(mpk',sk[id(0)]',id(1))を実行し、第1秘密鍵sk[id(1)]=sk[id(1)]'を生成する(S114)。
【００５４】
図16に示すように中間鍵発行局装置32の第n(n=1,2,…,k-1)装置32-nは、パース部323-nと、第n+1秘密鍵生成部124-nと、ID記憶部125-nとを備える。
【００５５】
パース部323-nは、mpk=(mpk',idmaster)にパースし、id(n+1)=idmasterであれば⊥を出力して停止する。そうでなければsk[id(n)]=sk[id(n)]'にパースする(S323-n)。第n+1秘密鍵生成部124-nは、装置のIDであるid(n+1)を取得して、sk[id(n+1)]'←KG'(mpk',sk[id(n)]',id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=sk[id(n+1)]'を生成する(S124-n)。
【００５６】
図17に示すように、証明者装置33は、パース部333と、ID記憶部135と、コミットメント生成部136-1と、チャレンジ生成部336-2と、シミュレーション生成部136-3と、チャレンジ分割部338と、レスポンス生成部339と、実施例1と同じ検証用データ送受信部137とを備える。以下、136-1、336-2、136-3をまとめて検証用データ生成部336と呼ぶ。
【００５７】
パース部333は、mpk=(mpk',idmaster)に、sk[id(k)]=sk[id(k)]'にパースする(S333)。コミットメント生成部136-1は、(a0,st)←Σhibi-com(mpk',id(k),sk[id(k)]')を実行する(S136-1)。チャレンジ生成部336-2は、c2←Σ+hibi-ch(mpk')を実行する(S336-2)。シミュレーション生成部136-3は、(a1,z1)←Σhibi-sim(mpk',idmaster,c2)を実行する(S136-3)。チャレンジ分割部338は、検証者装置14からチャレンジcを取得して、チャレンジの分割c0=c-c2を実行する(S338)。レスポンス生成部339は、z0←Σhibi-res(mpk',id(k),sk[id(k)]',a0,c0,st)を実行する(S339)。
【００５８】
検証者装置14は、実施例1と同じ構成であるため図示を省略する。パース部143は、mpk=(mpk',idmaster)にパースする(S143)。チャレンジ生成部146は、c←Σ+hibi-ch(mpk')を実行する(S146)。チャレンジ分割部148は、証明者装置33からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行する(S148)。検証部149は、dec0←Σhibi-vrfy(mpk',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk',idmaster,a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する(S149)。
【００５９】
このように、本実施例の階層型IDベース認証システム3によれば、実施例1の効果に加えて、マスターIDを用いることとしたため、秘密鍵を一つのみとすることができ、各装置におけるハードウェア処理を削減することができる。
【実施例４】
【００６０】
以下、図20から図26を参照して本発明の実施例4の階層型IDベース認証システム4について説明する。図20は本実施例の階層型IDベース認証システム4の構成を示すブロック図である。図21は本実施例の鍵発行局装置41の構成を示すブロック図である。図22は本実施例の第n装置42-nの構成を示すブロック図である。図23は本実施例の証明者装置43の構成を示すブロック図である。図24は本実施例の検証者装置44の構成を示すブロック図である。図25は本実施例の鍵発行局装置41および第n装置42-nの動作を示すシーケンス図である。図26は本実施例の証明者装置43および検証者装置44の動作を示すシーケンス図である。
【００６１】
図20に示すように、本実施例の階層型IDベース認証システム4は、実施例1と異なる鍵発行局装置41と、k-1個(kは2以上の整数)の第1装置42-1、…、第(k-1)装置42-(k-1)よりなる中間鍵発行局装置42と、証明者装置43と、検証者装置44とからなる。
【００６２】
図21に示すように鍵発行局装置41は、マスター鍵生成部411と、ルート秘密鍵生成部412と、パース部413と、第1秘密鍵生成部114とを備える。
マスター鍵生成部411は、セキュリティパラメータ1κを取得して(mpk0',msk0')←SetUp'(1κ)および(mpk1',msk1')←SetUp'(1κ)を実行してマスター公開鍵(1κ,mpk0',mpk1')と、マスター秘密鍵(msk0',msk1')を生成する(S411)。ルート秘密鍵生成部412は、ルート秘密鍵sk[id(0)]=(msk0',msk1')を生成する(S412)。パース部413は、mpk=(1κ,mpk0',mpk1')に、sk[id(0)]=(sk0'[id(0)],sk1'[id(0)])にパースする(S413)。第1秘密鍵生成部114は、第1装置のIDであるid(1)を取得して、各b∈{0,1}に対して、skb'[id(1)]←KG'(mpkb',skb'[id(0)],id(1))を実行し、第1秘密鍵sk[id(1)]=(sk0'[id(1)],sk1'[id(1)])を生成する(S114)。
【００６３】
図22に示すように中間鍵発行局装置42の第n(n=1,2,…,k-1)装置42-nは、パース部423-nと、第n+1秘密鍵生成部124-nと、ID記憶部125-nとを備える。
【００６４】
パース部423-nは、mpk=(1κ,mpk0',mpk1')に、sk[id(n)]=(sk0'[id(n)],sk1'[id(n)])にパースする(S423-n)。第n+1秘密鍵生成部124-nは、装置のIDであるid(n+1)を取得して、各b∈{0,1}に対して、skb'[id(n+1)]←KG'(mpkb',skb'[id(n)],id(n+1))を実行し、第n+1秘密鍵sk[id(n+1)]=(sk0'[id(n+1)],sk1'[id(n+1)])を生成する(S124-n)。
【００６５】
図23に示すように、証明者装置43は、パース部433と、ID記憶部135と、コミットメント生成部136-1と、チャレンジ生成部436-2と、シミュレーション生成部136-3と、実施例1と同じチャレンジ分割部138と、レスポンス生成部139と、検証用データ送受信部137とを備える。以下、136-1、436-2、136-3をまとめて検証用データ生成部436と呼ぶ。
【００６６】
パース部433は、mpk=(1κ,mpk0',mpk1')に、sk[id(k)]=(sk0'[id(k)],sk1'[id(k)])にパースする(S433)。コミットメント生成部136-1は、b←{0,1}をランダムに選んで、(ab,st)←Σhibi-com(mpkb',id(k),skb'[id(k)])を実行する(S136-1)。チャレンジ生成部436-2は、b~を1-bとしてcb~←Σ*hibi-ch(1κ)を実行する(S436-2)。シミュレーション生成部136-3は、(ab~,zb~)←Σhibi-sim(mpkb~',id(k),cb~)を実行する(S136-3)。チャレンジ分割部138は、検証者装置44からチャレンジcを取得して、チャレンジの分割cb=c-cb~を実行する(S138)。レスポンス生成部139は、zb←Σhibi-res(mpkb',id(k),skb'[id(k)],ab,cb,st)を実行する(S139)。
【００６７】
図24に示すように検証者装置44は、パース部143と、チャレンジ生成部446と、実施例1と同じ検証用データ送受信部147と、チャレンジ分割部148と、検証部149とを備える。
【００６８】
パース部143は、mpk=(1κ,mpk0',mpk1')にパースする(S143)。チャレンジ生成部446は、c←Σ*hibi-ch(1κ)を実行する(S446)。チャレンジ分割部148は、証明者装置43からチャレンジc0を取得して、チャレンジの分割c1=c-c0を実行する(S148)。検証部149は、dec0←Σhibi-vrfy(mpk0',id(k),a0,c0,z0)およびdec1←Σhibi-vrfy(mpk1',id(k),a1,c1,z1)を実行して、dec0とdec1がともにacceptであれば、acceptを出力し、それ以外であればrejectを出力する(S149)。
【００６９】
図27に示すように、本実施例の階層型IDベース認証システム4は、実施例2と同様に、全ての攻撃バリエーションに対して適応可能である。
【００７０】
このように、本実施例の階層型IDベース認証システム4によれば、実施例1の効果に加えて、全ての攻撃バリエーションに対して適応可能なHIBIプロトコルを構成できる。
【図１】
2014078796.tif 000003
【図２】
2014078796.tif 000004
【図３】
2014078796.tif 000005
【図４】
2014078796.tif 000006
【図５】
2014078796.tif 000007
【図６】
2014078796.tif 000008
【図７】
2014078796.tif 000009
【図８】
2014078796.tif 000010
【図９】
2014078796.tif 000011
【図１０】
2014078796.tif 000012
【図１１】
2014078796.tif 000013
【図１２】
2014078796.tif 000014
【図１３】
2014078796.tif 000015
【図１４】
2014078796.tif 000016
【図１５】
2014078796.tif 000017
【図１６】
2014078796.tif 000018
【図１７】
2014078796.tif 000019
【図１８】
2014078796.tif 000020
【図１９】
2014078796.tif 000021
【図２０】
2014078796.tif 000022
【図２１】
2014078796.tif 000023
【図２２】
2014078796.tif 000024
【図２３】
2014078796.tif 000025
【図２４】
2014078796.tif 000026
【図２５】
2014078796.tif 000027
【図２６】
2014078796.tif 000028
【図２７】
2014078796.tif 000029