(57)【要約】【構成】  楕円曲線E状の秘密のパラメータP,Q、秘密の数s,rに対し、クライアントのIDを衝突耐性ハッシュ関数ｈで処理してIiとし、クライアントの秘密鍵をKi=(s+Ii)-1Pとする。メッセージmを暗号化するセッション鍵Ksを  Ks=enc(P,Q)rkとし、ヘッダを、H1=ｋΠi=1〜N(s+Ii)R=kΣi=0〜NcisiR、H2=k(rP)、S＝{I1,I2,…,IN}で構成する。クライアントは、  A=en(Ki,H1)=en((s+Ii)-1P,kΠi=1〜N(s+Ii)R)  と、  B=en(H2,Π j=1〜N,j≠i(s+Ij)Q−Π j=1〜N,j≠iIjQ)=en(P,Q)rkΠj=1〜N,j≠i  Ij    とから、A/B=en(P,Q)rkΠ j=1〜N,j≠iIj,(A/B)Π j=1〜N,j≠iIj-1=Ks  によりセッション鍵を復元する。【効果】  IDに基づく放送用暗号を提供できる。【選択図】    図２
2008301391.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号システムであって、
デジタル情報処理装置からなる鍵生成部で、楕円曲線上の２元P,Qと、数s,rを生成して鍵生成部の秘密として記憶する手段と；
復号器のIDをハッシュ値Iiに変換する、衝突耐性ハッシュ関数ｈの記憶手段と；
記憶したハッシュ関数によりハッシュ値Iiを求めるための手段と；
求めた復号器のハッシュ値Iiにより、変数をsとし係数がハッシュ値Iiにより定まる多項式f(Ii)の値を求めて、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むように生成するための手段と；
復号器の総数以上の数をNとし、公開鍵としてR:  R=rQ、  双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータｙ、及びベクトルRv：  Rv=(sR，s２R，…，sNR）、ベクトルQv：  Qv=（sQ，s２Q，…，sN-1Q）を生成して公開するための手段とを備えたものと、
デジタル情報処理装置からなる暗号化部で、公開のパラメータｙのk乗  Ks＝ｙk  をセッション毎の鍵として生成するための手段と；
メッセージmをセッション鍵Ksで暗号化するための手段と；
復号器のIDのハッシュ値の集合をＳとして、ヘッダの第１成分H1を
H1＝ｋΠi∈Sf(Ii)R  として生成するための手段と；
ヘッダの第２成分H2をkとPとを因子に含むように生成するための手段と；
メッセージmとヘッダの第１成分H1及び第２成分H2を復号器に送信するための手段とを備えたものと、
デジタル情報処理装置からなる復号器で、ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めるための手段と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求めるための手段と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号するための手段と；    セッション鍵Ksから、メッセージmを復号するための手段とを備えた、放送用暗号システム。
【請求項２】
楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号通信方法であって、
デジタル情報処理装置からなる鍵生成部により、楕円曲線上の２元P,Qと、数s,rを生成して鍵生成部の秘密とし、復号器のIDを衝突耐性ハッシュ関数ｈによりハッシュ値Iiに変換して、変数をsとし係数がハッシュ値Iiにより定まる多項式f(Ii)により、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むように定めて、放送用暗号を受信する各復号器に提供し；
復号器の総数以上の数をNとして；
暗号化用の公開鍵として、R:  R=rQ、  双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータｙ、及びベクトルRv：  Rv=（sR，s２R，…，sNR）を公開し；
さらに復号用の公開鍵として、ベクトルQv：  Qv=（sQ，s２Q，…，sN-1Q）を公開し、
デジタル情報処理装置からなる暗号化部では、公開のパラメータｙのk乗  Ks＝ｙk  をセッション毎の鍵として、メッセージmをセッション鍵Ksで暗号化すると共に、復号器のIDのハッシュ値の集合をＳとして、ヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R  として生成し、ヘッダの第２成分H2をkとPとを因子に含むように生成し、メッセージmとヘッダの第１及び第２成分を復号器に送信し、
デジタル情報処理装置からなる復号器では、ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めると共に、楕円曲線上の元
Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：
B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求め、
A/BのΠ j∈S,j≠iIj−１乗  A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号して、メッセージmを復号する、放送用暗号通信方法。
【請求項３】
楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号の、デジタル情報処理装置からなる復号器であって、
楕円曲線上の秘密の２元をP,Q、秘密の数をs,r、個別の復号器のIDのハッシュ値をIi、変数をsとし係数がハッシュ値Iiにより定まる多項式をf(Ii)とし、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むものとし、復号器の総数以上の数をN、双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータをｙ、公開のベクトルQvを
Qv＝(sQ，s２Q，…，sN-1Q）、セッション鍵Ksを  Ks＝ｙk  として、メッセージmをセッション鍵Ksで暗号化した暗号文を復号するために、復号器のIDのハッシュ値の集合をＳとし、メッセージmと共に受信したヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R、ｋとPとを因子に含むヘッダの第２成分をH2として、
ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めるための手段と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求めるための手段と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号するための手段と；    セッション鍵Ksから、メッセージmを復号するための手段とを備えた、復号器。
【請求項４】
前記双線形写像が修正ペアリングen（,）で、前記多項式f(Ii)が
f(Ii)=s+Ii  で、復号器毎の秘密鍵Kiが  Ki=（s+Ii）-1Pで、前記パラメータｙが
y=en(P,Q)ｒ  で、前記第２成分H2がkrPであることを特徴とする、請求項３の復号器。
【請求項５】
ハッシュ値の集合Ｓと公開のベクトルQvとから、Πj∈S,j≠i(s+Ij)Qでのｓの各次数の係数を、(s+I1)から(s+I1)（s+I2）の順でΠj∈S,j≠i(s+Ij)まで、逐次的に求めるための係数生成手段を設けたことを特徴とする、請求項４の復号器。
【請求項６】
前記係数生成手段では、I1を０次の係数の初期値、1を１次の係数の初期値として、I1×I2の演算と１×I1＋I2の演算を行い、次いで(I1×I2）×I3の演算と（I1＋I2）×I3+I1×I2の演算と、I1＋I2＋I3の演算を行い、以降も逐次的にΠj∈S,j≠i(s+Ij)まで処理するようにしたことを特徴とする、請求項５の復号器。
【請求項７】
楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号の、デジタル情報処理装置からなる復号器のプログラムであって、
楕円曲線上の秘密の２元をP,Q、秘密の数をs,r、個別の復号器のIDのハッシュ値をIi、変数をsとし係数がハッシュ値Iiにより定まる多項式をf(Ii)とし、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むものとし、復号器の総数以上の数をN、双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータをｙ、公開のベクトルQvを
Qv＝(sQ，s２Q，…，sN-1Q）、セッション鍵Ksを  Ks＝ｙｋ  として、メッセージmをセッション鍵Ksで暗号化した暗号文を復号するために、復号器のIDのハッシュ値の集合をＳとして、メッセージmと共に受信したヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R、ｋとPとを因子に含むヘッダの第２成分をH2として、
ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を復号器により求めるための命令と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を復号器により求めるための命令と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号器により復号するための命令と；
セッション鍵Ksから、メッセージmを復号器により復号するための命令とを備えた、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は1:N(Nは２以上の自然数)の通信を行う放送用暗号に関し、特に受信者のIDに基づいた放送用暗号に関する。
【背景技術】
【０００２】
発明者らは、楕円曲線上のペアリングを用いた放送用暗号を提案した(非特許文献１：Shigeo MITSUNARI,Ryuichi SAKAI,and Masao KASAHARA,"A Ne Traitor Tracing", IEICE Transactions Vol.E85-A, No.2,pp.481-484,Feb.2002、；特許文献１：特開２００２−２７１３１０)。その後、Bonehらは、各クライアント、即ち復号器に一意の番号を付した、放送用暗号を提案した(非特許文献２：D.Boneh, G.Gentry,and B.Waters,"Collusion Resistant Broadcast Encryption With Short Cihertexts and Private Keys"  Euro-cypt 2005)。Bonehらの提案でも楕円曲線上のペアリングを用い、各クライアントは固有の秘密鍵を持ち、放送事業者はメッセージをセッション毎の鍵で暗号化したものに、ヘッダを付加して放送する。クライアントはヘッダと自己の秘密鍵からセッション鍵を復元して、メッセージを復号する。
【非特許文献１】Shigeo MITSUNARI,Ryuichi SAKAI,and Masao KASAHARA,"A New Traitor Tracing", IEICE Transactions Vol.E85-A, No.2,pp.481-484,Feb.2002
【非特許文献２】D.Boneh, C.Gentry,and B.Waters,"Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys"  Euro-cypt 2005
【非特許文献３】D.Boneh, Xavier BOYEN,and Eu-Jin GOH,"Hierarchical Identity Based Encryption with Consatant Size Ciphertext"  Euro-cypt 2005
【特許文献１】特開２００２−２７１３１０
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の課題は、新規な放送用暗号を提供することにあり、クライアントの脱退に対して、システムパラメータやクライアント毎の秘密鍵を変更する必要が無い放送用暗号を提供することにある。
【課題を解決するための手段】
【０００４】
この発明の、楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号システムは、
デジタル情報処理装置からなる鍵生成部で、楕円曲線上の２元P,Qと、数s,rを生成して鍵生成部の秘密として記憶する手段と；
復号器のIDをハッシュ値Iiに変換する、衝突耐性ハッシュ関数ｈの記憶手段と；
記憶したハッシュ関数によりハッシュ値Iiを求めるための手段と；
求めた復号器のハッシュ値Iiにより、変数をsとし係数がハッシュ値Iiにより定まる多項式f(Ii)の値を求めて、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むように生成するための手段と；
復号器の総数以上の数をNとし、公開鍵としてR:  R=rQ、  双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータｙ、及びベクトルRv：  Rv=(sR，s２R，…，sNR）、ベクトルQv：  Qv=（sQ，s２Q，…，sN-1Q）を生成して公開するための手段とを備えたものと、
デジタル情報処理装置からなる暗号化部で、公開のパラメータｙのk乗  Ks＝ｙk
をセッション毎の鍵として生成するための手段と；
メッセージmをセッション鍵Ksで暗号化するための手段と；
復号器のIDのハッシュ値の集合をＳとして、ヘッダの第１成分H1を
H1＝ｋΠi∈Sf(Ii)R  として生成するための手段と；
ヘッダの第２成分H2をkとPとを因子に含むように生成するための手段と；
メッセージmとヘッダの第１成分H1及び第２成分H2を復号器に送信するための手段とを備えたものと、
デジタル情報処理装置からなる復号器で、ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めるための手段と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求めるための手段と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号するための手段と；    セッション鍵Ksから、メッセージmを復号するための手段とを備えたている。
【０００５】
この発明の、楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号通信方法は、
デジタル情報処理装置からなる鍵生成部により、楕円曲線上の２元P,Qと、数s,rを生成して鍵生成部の秘密とし、復号器のIDを衝突耐性ハッシュ関数ｈによりハッシュ値Iiに変換して、変数をsとし係数がハッシュ値Iiにより定まる多項式f(Ii)により、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むように定めて、放送用暗号を受信する各復号器に提供し；
復号器の総数以上の数をNとして；
暗号化用の公開鍵として、R:  R=rQ、  双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータｙ、及びベクトルRv：  Rv=（sR，s２R，…，sNR）を公開し；
さらに復号用の公開鍵として、ベクトルQv：  Qv=（sQ，s２Q，…，sN-1Q）を公開し、
デジタル情報処理装置からなる暗号化部では、公開のパラメータｙのk乗  Ks＝ｙk  をセッション毎の鍵として、メッセージmをセッション鍵Ksで暗号化すると共に、復号器のIDのハッシュ値の集合をＳとして、ヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R  として生成し、ヘッダの第２成分H2をkとPとを因子に含むように生成し、メッセージmとヘッダの第１及び第２成分を復号器に送信し、
デジタル情報処理装置からなる復号器では、ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めると共に、楕円曲線上の元
Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：
B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求め、
A/BのΠ j∈S,j≠iIj−１乗  A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号して、メッセージmを復号する。
【０００６】
この発明の、楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号の、デジタル情報処理装置からなる復号器は、
楕円曲線上の秘密の２元をP,Q、秘密の数をs,r、個別の復号器のIDのハッシュ値をIi、変数をsとし係数がハッシュ値Iiにより定まる多項式をf(Ii)とし、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むものとし、復号器の総数以上の数をN、双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータをｙ、公開のベクトルQvを
Qv＝(sQ，s２Q，…，sN-1Q）、セッション鍵Ksを  Ks＝ｙk  として、メッセージmをセッション鍵Ksで暗号化した暗号文を復号するために、復号器のIDのハッシュ値の集合をＳとし、メッセージmと共に受信したヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R、ｋとPとを因子に含むヘッダの第２成分をH2として、
ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を求めるための手段と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を求めるための手段と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  からセッション鍵Ksを復号するための手段と；    セッション鍵Ksから、メッセージmを復号するための手段とを備えている。
【０００７】
好ましくは、前記双線形写像が修正ペアリングen（,）で、前記多項式f(Ii)が
f(Ii)=s+Ii  で、復号器毎の秘密鍵Kiが  Ki=（s+Ii）-1Pで、前記パラメータｙが
y=en(P,Q)ｒ  で、前記第２成分H2がkrPである。
より好ましくは、ハッシュ値の集合Ｓと公開のベクトルQvとから、Πj∈S,j≠i(s+Ij)Qでのｓの各次数の係数を、(s+I1)から(s+I1)（s+I2）の順でΠj∈S,j≠i(s+Ij)まで、逐次的に求めるための係数生成手段を設ける。
特に好ましくは、前記係数生成手段では、I1を０次の係数の初期値、1を１次の係数の初期値として、I1×I2の演算と１×I1＋I2の演算を行い、次いで(I1×I2）×I3の演算と（I1＋I2）×I3+I1×I2の演算と、I1＋I2＋I3の演算を行い、以降も逐次的に
Πj∈S,j≠i(s+Ij)まで処理する。
【０００８】
この発明の、楕円曲線上の双線形写像と離散対数問題とを用いた放送用暗号の、デジタル情報処理装置からなる復号器のプログラムは、
楕円曲線上の秘密の２元をP,Q、秘密の数をs,r、個別の復号器のIDのハッシュ値をIi、変数をsとし係数がハッシュ値Iiにより定まる多項式をf(Ii)とし、復号器毎の秘密鍵Kiをf(Ii)-1  と秘密の元Pとを因子に含むものとし、復号器の総数以上の数をN、双線形写像をbi(,)としてbi(P,Q)を因子に含むパラメータをｙ、公開のベクトルQvを
Qv＝(sQ，s２Q，…，sN-1Q）、セッション鍵Ksを  Ks＝ｙk  として、メッセージmをセッション鍵Ksで暗号化した暗号文を復号するために、復号器のIDのハッシュ値の集合をＳとして、メッセージmと共に受信したヘッダの第１成分H1を  H1＝ｋΠi∈Sf(Ii)R、ｋとPとを因子に含むヘッダの第２成分をH2として、
ヘッダの第１成分H1と自己の秘密鍵Kiとの双線形写像  A=bi(Ki,H1)  の値を復号器により求めるための命令と；
楕円曲線上の元  Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ  を求め、さらにパラメータB：  B＝bi(H2,Πj∈S,j≠i(s+Ij)Q−Π j∈S,j≠iIjQ)  を復号器により求めるための命令と、
A/BのΠ j∈S,j≠iIj−１乗 A/BΠ j∈S,j≠i Ij−１  （ここで指数部はIj-1ではなく、Ij−１）からセッション鍵Ksを復号器により復号するための命令と；
セッション鍵Ksから、メッセージmを復号器により復号するための命令とを備えている。
【発明の効果】
【０００９】
この発明では、クライアント（復号器）の秘密鍵がそのIDのハッシュ値の関数なので、秘密鍵が漏洩すると漏洩元を追跡できる。また秘密のパラメータP,Qと秘密の数は、楕円曲線上の離散対数問題により安全に保たれる。さらに攻撃者が、正規のヘッダの第１成分H1と同等の役割を果たす偽のヘッダを、脱退者の秘密鍵などに合わせて偽造することができない。従って、脱退者が生じても、システムパラメータや、正規の復号器の秘密鍵などを変更する必要がない。
【発明を実施するための最良の形態】
【００１０】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１１】
図１〜図１０に、実施例の放送用暗号システム２を示す。４は鍵生成器で、鍵生成センターに備えられ、６は暗号化器で、放送事業者やマルチキャストでの送信者、ＤＶＤなどのコンテンツの配給者、などに備えられている。８は公開ボードで、公開鍵を記憶し、１０は復号化器で、放送やマルチキャスト通信などを受信し、あるいはＤＶＤコンテンツを復号するクライアントに設けられている。システム２の要素４〜１０はそれぞれデジタル情報処理装置からなり、インターネットなどのネットワークとの通信手段と、ＲＡＭやＲＯＭ等のメモリ、モニター、キーボード、ＣＤドライブなどのディスクドライブなどを備えている。実施例では、放送事業者が多数のクライアントに対しメッセージmを暗号化し、ヘッダと共に送信する例を説明する。ここで鍵生成器４を暗号化器６と共に放送事業者に設けても良く、また放送以外のマルチキャスト通信やＤＶＤ等のコンテンツの配給に、この発明を応用しても良い。
【００１２】
図２に、鍵生成器４の構造を示す。セキュリティーパラメータに従って、公開パラメータ生成器１４は、楕円曲線E(Fq),楕円曲線E上のnねじれ群と位数が等しい整数環Z/nZの位数n,並びに及び衝突耐性ハッシュ関数hを発生する。衝突耐性ハッシュ関数ｈはクライアントのIDiをハッシュ値Iiに変換し、iは個々の復号化器１０もしくはそのユーザを表す添字で、ハッシュ値Iiは１００〜２００ビット程度のデータである。公開パラメータ生成器１４は、ベイユペアリングやテートペアリングなどの修正ペアリングen(,)を発生し、ペアリングen(,)は楕円曲線E上のnねじれ群の２元を位数ｎの１の乗法群の元に変換する。修正ペアリングに代えて通常のペアリングを用いても、あるいはより一般的な双線形写像を用いても良く、これらの性質自体は良く知られている(非特許文献３)。またNはクライアントの数を表すパラメータで、クライアントの数以上の値とし、クライアントの数と一致する必要はない。秘密鍵生成器１２は、楕円曲線E上のnねじれ群の元P,Qと、
整数環Z/nZ上の秘密の数s,rを発生する。P,Qは、無限遠点ではないものとする。
【００１３】
端末秘密鍵生成器１６は、ハッシュ関数hにより個別のクライアントのID(IDi)をハッシュ値Iiに変換する。ここにiはクライアントの番号である。秘密の数s(整数環Z/nZの元)の多項式で、ハッシュ値Iiにより係数が定まる多項式をf(Ii)とし、ここでは簡単のため
f(Ii)=s+Ii  とする。そしてクライアント毎の秘密鍵Kiを  (s＋Ii)-1P=ｆ(Ii)-1P  とする。秘密鍵Kiは楕円曲線E(Fq)上のnねじれ群の元で、クライアント毎に固有のパラメータであるため、漏洩した秘密鍵Kiが判明すると、どのクライアントから秘密鍵が漏洩したかが判明する。
【００１４】
公開鍵生成器１８は暗号化用公開鍵生成部１９と復号用公開鍵生成部２０とを備え、暗号化用公開鍵生成部１９では秘密の元Qと秘密の数rとにより、楕円曲線上のnねじれ群の元R=rQを計算する。そしてRi=siRとして、R1〜RNの各成分を求め、これらをR1〜RNの順に配列して、公開ベクトルRvとする。なお図では、ベクトルを太文字で表し、明細書では添え字vでベクトルを表す。暗号化用公開鍵生成部１９ではこれ以外に、元Pと秘密の数rから楕円曲線上のnねじれ群の元rPを求め、ペアリングenを用いて、  y=en(P,Q)r=en(rP,Q)
=en(P,rQ)を求める。復号用公開鍵生成部２０では、  Qi=siQ(i=1〜N-1)  を求め、成分QiからなるベクトルQvを求める。Qiは楕円曲線上のnねじれ群の元である。
【００１５】
公開ボード８はホームページなどを備えて、送信者６や復号化器１０が公開鍵を取得できるようにし、公開パラメータ記憶部２１には、パラメータn,E(Fq),h,en(,),Nを記憶する。暗号化用公開鍵記憶部２２には、暗号化用の公開鍵R,rP,y,Rvを記憶する。復号用公開鍵記憶部２３には復号用の公開鍵Qvを記憶する。端末秘密鍵生成器１６は、復号化器１０からIDを取得し、端末毎の秘密鍵Kiを復号化器１０に送信する。
【００１６】
図３に暗号化器６の構造を示す。乱数生成器３１は乱数k（整数環Z/nZの元）を生成し、セッション鍵作成部３０は  y=en(P,Q)r  から、セッション毎の鍵  Ks=yk=en(P,Q)rk  を求める。メッセージ暗号化部３３は、メッセージmとセッション鍵Ksとを用いて暗号文Cを作成し、図のEncは暗号化を行う写像を意味する。受信端末ID記憶部３２は、放送事業者と契約しているクライアントのIDを取得し、そのハッシュ値｛I1〜IN｝からなる集合Ｓを記憶している。なお集合Ｓは鍵生成器４で作成して公開ボード８で公開しても良いし、ハッシュ値ではなくIDそのものの集合でも良い。ヘッダ作成部３４はヘッダHの３成分H1〜H3を作成し、ヘッダの第１成分H1：
H1=kΠ(i=1〜N)(s+Ii)R=kΠ(i=1〜N)f(Ii)R  を求める。sは放送事業者にとっても秘密の数であり、H1を直接計算できないので、ヘッダH1をsの多項式として展開し、公開鍵ベクトルRvからヘッダH1を求める。H1を秘密の数sの多項式として展開すると、  
H1=kΣ(i=0〜N)cisiR  となり、係数ciの決定方法は図４に示す。ヘッダの第２成分H2はk(rP)からなり、これは楕円曲線E上のnねじれ群の元である。ヘッダの第３成分H3は受信端末のハッシュ値Iiの集合Ｓからなる。そして暗号化器６は、ヘッダH1,H2,H3と暗号文Cとを送信データ３６として、復号化器１０へインターネットなどを介して送信する。表１に鍵生成部４が生成する放送用暗号システム全体に関するパラメータを、表２に暗号化器６で生成するパラメータやクライアントの秘密鍵を示す。
【００１７】
表  １    記  号  と  そ  の  意  味  （システムパラメータ）    
E(Fq)      体Fq上の楕円曲線
en(,)      修正ペアリング：  ベイユペアリングやテートペアリング等
修正ペアリング以外のペアリングや、ペアリング以外の双線形写像でも可
R         楕円曲線E上の演算  R=rQ  で定まる公開パラメータ
rP        楕円曲線E上の公開パラメータ
y         楕円曲線E上の公開パラメータ  y=en(P,Q)r 
Rv        楕円曲線上の公開のベクトル  Rv=(R1,R2,…,RN)=(sR,s2R,…,sNR)  Ri=siR
Qv        楕円曲線上の公開のベクトル  Qv=(Q1,Q2,…,QN-1)=(sQ,s2Q,…,sN-1Q)
Qi=siQ
N         IDの個数（受信端末の数）以上の数
n         整数環Z/nZの位数  なおペアリングの値は１のｎ乗根がなす位数ｎの群の元
ｈ(IDi)   衝突耐性ハッシュ関数：  i番目のクライアントのIDiをハッシュ値Iiに変換し、          IDが異なれば同じハッシュ値となる確率は無視し得る   ｈ(IDi)=Ii
ハッシュ関数hは鍵生成部４の秘密とすることが好ましい
P,Q       秘密のパラメータ：  楕円曲線E(Fq)上のnねじれ群の元で、無限遠点ではない
s,r       秘密の数：  整数環Z/nZの元
*         P,Q,r,s  の安全性は楕円曲線上の離散対数問題により保証されている
例えばrQが既知でも、rやQは秘密に保たれる.
【００１８】
表  ２    記  号  と  そ  の  意  味  （暗号化器  等）        
Ki        クライアントIDiに対する端末iの秘密鍵：    Ki=(s+Ii)-1P  
sを変数とするIiの多項式をF(Ii)とし、Ki=f(Ii)-1P  としても良い
Ki=(s+Ii)-1P  はfi(Ii)をsの１次式とする例
k         暗号化器で生成する秘密の乱数：  kはセッション毎に変更する
Ks        セッション毎の暗号化鍵：  Ks=yk=en(P,Q)rk  メッセージmを暗号化鍵Ksで
暗号化したものを暗号文Cとする  C=Enc(m,Ks)  Encは暗号化を行う写像
H         ヘッダ：  H=(H1,H2,Ｓ)  H3=Ｓ
H1        ヘッダHの第１成分で楕円曲線E上のパラメータ：
H1=ｋΠi=1〜N(s+Ii)R=kΣi=0〜NcisiR  ciはΠi=1〜N(s+Ii)を展開した際のi次の係数
Σi=0〜NcisiRは公開鍵Rvと集合Ｓとから演算可能なパブリックなパラメータ；
kが秘密なため、ヘッダH1は暗号化器６でのみ計算可能
H2        ヘッダHの第２成分で楕円曲線E上のパラメータ  H2=ｋ(rP)
Ｓ        ハッシュ値｛Ii｝の集合で、ヘッダHの第３成分  Ｓ=｛I1,I2,…,IN｝
g         Π j=1〜N,j≠i(s+Ij)−Π j=1〜N,j≠iIj：  復号過程で現れるパラメータで、
sが秘密なためgは計算不能であるが、gQは公開鍵と集合Ｓとから計算可能
【００１９】
図４に、ヘッダ作成部３４中の係数生成部３５での、係数ciの生成を示す。図においてf0〜fNはN+1個のレジスタで、ＣＰＵ内の高速レジスタでも良く、あるいはシフトレジスタやＲＡＭで実現しても良い。３７は乗算器、３８は加算器で、レジスタ４０は次に処理するハッシュ値Ij(j=2〜N)を記憶している。最初のレジスタf0と最後のレジスタfNを除き、各レジスタfiでは、値j-1に対する記憶値とレジスタ４０で記憶しているハッシュ値Ijとを乗算器３７で乗算し、レジスタfi-1の値j-1での記憶値を加算器３８で加算し、元のレジスタfiに上書きする。レジスタf0〜fNの初期値は、レジスタf0に対してI1、レジスタf1に対して１,レジスタf2〜ｆNに対して０である。
【００２０】
係数ciの生成プロセスを示す。j=2とすると、レジスタf0の値は、I1・I2となり、レジスタf1の値はI2＋I1となり、レジスタf2の値はI1となる。レジスタf3の値は１で、レジスタf4〜ｆNの値は０のままである。j=3に対して、レジスタf0の値はI1・I2・I3となり、レジスタf1の値は(I1＋I2)I3+I1・I2、レジスタf3の値はI3+(I1+I2)となり、レジスタf4の値は１で、レジスタf5〜ｆNの値は０のままである。以下同様にしてj=Nまで処理を続行すると、レジスタｆNの値は１,レジスタｆN-1の値はI1+I2+…+INで、以下同様に展開係数が得られ、レジスタf0の値はI1・I2・I3・…・INとなる。以上の逐次的に係数ciを発生すると、比較的短い計算時間で係数ciを得ることができる。
【００２１】
図５に復号化器１０の構造を示す。セッション鍵復号器５１は端末毎の秘密鍵Kiとヘッダの第１成分〜第３成分H1〜H3とにより、セッション鍵Ksを求め、復号器５２で復号用の写像Decを用いて暗号文Cを平文mに復号する。復号に必要なパラメータや公開鍵は、公開ボード８から取得し、表３に復号化器での主な処理を示す。
【００２２】
表  ３    復  号  化  器  で  の  主  な  処  理                  
H1より      パラメータa：  A=en(Ki,H1)=en((s+Ii)-1P,ｋΠi=1〜N(s+Ii)R)
=en(P,Q)rkΠ j=1〜N,j≠i (s+Ij) 
H2より      パラメータB：  B=en(H2,Π j=1〜N,j≠i(s+Ij)Q−Π j=1〜N,j≠iIjQ)
=en(P,Q)rk(Π j=1〜N,j≠i(s+Ij)−Π j=1〜N,j≠iIj)=en(P,Q)rkg 
H1=ｋΠi=1〜N(s+Ii)R  はkがセッション毎の秘密の数であるため、
復号化器１０ではH1を自作できない.
クライアント毎の秘密鍵KiがパラメータPを因子として含み、
ヘッダの第１成分H1がkRを因子に含むことにより、Aは因子rkを含む.
秘密鍵Kiが因子（s+Ii）-1を含むため、Aは因子  Π j=1〜N,j≠i (s+Ij)
を含む
Π j=1〜N,j≠i(s+Ij)Q−Π j=1〜N,j≠iIjQ=gQ  はsの各次数の係数が判明すると、
公開鍵Qvより計算可能であるが、
Π j=1〜N,j≠i(s+Ij)−Π j=1〜N,j≠iIj=g  はsが秘密の数であるため、計算不能
A/B=en(P,Q)rkΠ j=1〜N,j≠iIj  =KsΠ j=1〜N,j≠iIj 
(A/B)Π j=1〜N,j≠iIj-1=Ks   （ここで指数部の"Ij−１"はIj−１を意味する）
Π j=1〜N,j≠i Ij は集合Ｓより計算可能なパラメータである．  
Bに代えて、B-1=en(H2,Π j=1〜N,j≠iIjQ−Π j=1〜N,j≠i(s+Ij)Q)=
en(P,Q)-rkｇを計算すると、
A/B=AB-1となり、乗算で処理できる
【００２３】
図６にセッション鍵復号器５１の構造を示す。５３,５４はペアリング演算器で、ペアリング演算器５３はヘッダの第１成分H1と、自己の秘密鍵Kiとにより、位数ｎの乗法群の元  A=en(Ki,H1)  を求める。  Ki=(s+Ii)-1P、  H1=ｋΠi=1〜N(s+Ii)R、  R=ｒQ  なので、
A=en(P,Q)rkΠj=1〜N j≠i (s+Ii)  となる。なおペアリング演算器５３で実際に演算するのは、
en(Ki,H1)の値である。ペアリング演算器５４では、ヘッダの第２成分H2と第３成分H3とにより、  B=en(H2,Π j=1〜N,j≠i(s+Ij)Q−Π j=1〜N,j≠iIjQ)  を求める。
【００２４】
g=Π j=1〜N,j≠i(s+Ij)−Π j=1〜N,j≠iIj  とすると、B=en(H2,gＱ)である。ハッシュ値I1〜INの値はヘッダの第３成分H3に含まれ、sjQ(j=1〜N-1)の値は復号用公開鍵Qvとして公開されている。従ってペアリングに用いる  
Π j=1〜N,j≠i(s+Ij)Q−Π j=1〜N,j≠iIjQ)=gQ  は演算可能であるが、gは秘密の数sを含むため演算可能ではない。gQを求める演算は係数生成部５８で行う。
H2=krP  なので、  B=en(P,Q)rk(Π j=1〜N,j≠i(s+Ij)−Π j=1〜N,j≠iIj)=
en(P,Q)rkg  となる。
【００２５】
演算器５５は除算器５５とべき乗演算器５７とを備え、除算器５６でAをBで除算する。なおペアリング演算器５４でB-1を求める場合、即ち
B-1=en(H2,Π j=1〜N,j≠iIjQ−Π j=1〜N,j≠i(s+Ij)Q)  を求める場合、除算器に代えて乗算器を用い、A・B-1を求めると良い。  A/B=en(P,Q)ｒｋΠ j=1〜N,j≠iIj=
KsΠ j=1〜N,j≠iIj  で、Π j=1〜N,j≠iIj-1  はヘッダの第３成分H3から求めることができるので、べき乗演算器５７により
(A/B)Π j=1〜N,j≠iIj-1  を求め、これをセッション鍵Ksとする。なおセッション鍵Ksとして、en(P,Q)rkΠj∈S  Ij  を用いることもでき、この場合、(A/B)Ii  によりセッション鍵を求めることもできる。
【００２６】
図７に、係数生成部５８の構成を示し、d0〜dNはレジスタで、その構造や動作は図４の係数生成部３５と同様である。３７は乗算器で図４の乗算器３７と同じ動作を行い、３８は加算器で、図４の加算器３８と同じ動作を行う。ただし係数生成部５８は、自己のハッシュ値Iiに対する処理を省略する。レジスタ６０はハッシュ値I2〜INを乗算器３７に供給し、レジスタd0〜dNの初期値は、レジスタd0がI1,レジスタd1が１、レジスタd2〜dNが０である。そして図４と同様の動作により、係数d1〜dNを求める。
【００２７】
図８にセッション鍵の復号アルゴリズムを示す。ステップ１で  en(Ki,H1)=A  を求め、図７の係数生成部５８を用いてサブルーチン１で係数djの値を求め、これは図７で求めた係数djから、d0の値を０を除いたもので、dNの値は１である。ステップ２で係数djを用いて、djｓjQ  からBの値を求め、ステップ３でA/Bを求める。なおステップ２のペアリング演算で第２成分の符号を反転すると、ステップ３で除算に代えて乗算を行う。ステップ４でA/Bの値に対してべき乗演算を行い、セッション鍵Ksを復号する。
【００２８】
図９に係数djの生成アルゴリズムを示す。ステップ１１で、レジスタd0をI1に、レジスタd1を１に、他のレジスタを０に、初期値をセットする。次いでj=2〜N（j≠i）に対して、jを１つずつ増加させながら（ステップ１２，１３）、ステップ１４〜ステップ１８の処理を行う。ステップ１４でtの値をNにセットし、ステップ１５でレジスタdtの値を
dt=dt・Ij+d(t-1)  とする。これは乗算器３７で、レジスタdtの記憶値とIjとを乗算し、加算器３８でレジスタd(t-1)の値を加算することに対応する。ステップ１６でtの値を１減少させ、ステップ１７でt=1となるまでこの処理を繰り返し、ステップ１８でレジスタd0に対してその値をd0=d0・Ijとする。以上の処理をj=Nとなるまで繰り返し(ステップ１９)、得られた係数d0〜dNを出力する(ステップ２０)。なお以上の処理は、j=iとなるjに対して省略する。
【００２９】
図１０に実施例の復号プログラムを示し、各命令は、図６のペアリング演算器５３,５４,係数生成部５８,除算器５６,べき乗演算器５７での処理を実行するためのものである。即ち、第１ペアリング演算命令７１はペアリング演算器５３に処理を実行させ、第２ペアリング演算命令７２はペアリング演算器５４に処理を実行させ、係数演算部７３は係数生成部５８に処理を実行させ、除算命令７４は除算器５６に処理を実行させ、べき乗演算命令７５はべき乗演算器５７に処理を実行させる。
【００３０】
実施例では、秘密鍵Kiを与えられている全クライアントが復号可能なように説明したが、集合Ｓの部分集合Ｔに属するクライアントに対してのみ復号可能にすることができる。この場合、ヘッダの第１成分H1を、H1=ｋΠi∈T(s+Ii)R  とし、第３成分H3をＴとする。また  A=en(Ki,H1)=en((s+Ii)-1P,ｋΠj∈T,j≠i(s+Ii)R)
B=en(H2,Πj∈T,j≠i(s+Ij)Q−Π j∈T,j≠iIjQ)  とする。このようにすると復号可能な端末を動的に変更できる。実施例の安全性の機構を表４に示す。
【００３１】
表  ４    シ  ス  テ  ム  の  安  全  性                      
秘密鍵の漏洩：        秘密鍵  Ki=（s+Ii）-1Pなため、どのクライアントから
漏洩したかを追跡できる
鍵生成部の秘密鍵：    P,Q,r,sは楕円曲線上の離散対数問題により安全
ヘッダH1の自作：      離散対数問題により、正規のヘッダH1と攻撃者が自作した
Πi=1〜N(s+Ii)R  とからkを求めることはできない．
従って脱退者の秘密鍵K0に合わせて、ヘッダH1に類似のヘッダH0                      H0=ｋΠi=0〜N(s+Ii)R  を偽造できない．
【図面の簡単な説明】
【００３２】
【図１】実施例の放送用暗号システムの全体構成を示すブロック図
【図２】実施例での、鍵生成部と公開ボード及び受信クライアントとの関係を示すブロック図
【図３】暗号化器のブロック部で送信データの生成を示す
【図４】暗号化器のヘッダ作成部での係数fiの生成を示す図
【図５】復号化器での送信データの復号を示すブロック図
【図６】セッション鍵復号器のブロック図
【図７】セッション鍵復号器の係数生成部のブロック図
【図８】セッション鍵の復号アルゴリズムを示すフローチャート
【図９】図８の復号アルゴリズムでの、係数生成サブルーチンのフローチャート
【図１０】実施例の復号プログラムのブロック図
【符号の説明】
【００３３】
２          放送用暗号システム
４          鍵生成器
６          暗号化器
８          公開ボード
１０        復号化器
１２        秘密鍵生成器
１４        公開パラメータ生成器
１６        端末秘密鍵生成器
１８        公開鍵生成器  
１９        暗号化用公開鍵生成部  
２０        復号用公開鍵生成部  
２１        公開パラメータ記憶部
２２        暗号化用公開鍵記憶部
２３        復号用公開鍵記憶部
３０        セッション鍵作成部
３１        乱数生成器
３２        受信端末ID記憶部
３３        メッセージ暗号化部
３４        ヘッダ作成部
３５        係数生成部
３６        送信データ
３７        乗算器
３８        加算器
f0〜fN      レジスタ
４０        レジスタ
５１        セッション鍵復号器
５２        復号器
５３,５４  ペアリング演算器
５５        演算器
５６        除算器
５７        べき乗演算器
５８        係数生成部
d0〜dN      レジスタ
６０        レジスタ
７１        第１ペアリング命令
７２        第２ペアリング命令
７３        係数演算命令
７４        除算命令
７５        べき乗演算命令
【図８】
2008301391.tif 000003
【図９】
2008301391.tif 000004
【図１０】
2008301391.tif 000005
【図１】
2008301391.tif 000006
【図２】
2008301391.tif 000007
【図３】
2008301391.tif 000008
【図４】
2008301391.tif 000009
【図５】
2008301391.tif 000010
【図６】
2008301391.tif 000011
【図７】
2008301391.tif 000012