(57)【要約】【課題】製造コストを抑制しつつ、グループ署名の生成および検証を高速にする電子回路を実現するのに好適な、署名生成装置を提供する。【解決手段】署名生成装置は、i番目のユーザによるメッセージmに対する署名を生成するものであり、a[1]μ[x] (mod n)と、a[2]μ[s] (mod n)と、wμ[t] (mod l)と、の、いずれか２つもしくは３つを並列に計算するように、ＩＰコア３０１内に複数のサブＩＰ３０２を備える。ＩＰコア３０１内の各サブＩＰ３０２は、ローカルバス３０４を介して相互に接続される。【選択図】図３
2010014912.tif 000002
【特許請求の範囲】
【請求項１】
グループ署名の署名を生成する署名生成装置であって、
当該グループ署名は、
所定のビット長K[n]、
所定のビット長K[l]、
所定のビット長K[e]、
所定のビット長K[e']、
楕円曲線により定義される有限群GGの次数である素数qのビット長K[q]、
任意長のビット列に適用されるハッシュ関数Hashが返す値のビット長K[c]、
いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaが統計的に区別できなくなるようなビット長K[S]、
セキュリティパラメータK = (K[n],K[l],K[e],K[e'],K[q],K[c],K[S])、
整数λ = K[n]+K[q]+K[S]、
0以上2λ未満の整数を要素とする集合Λ、
当該楕円曲線上でのスカラーc倍演算[c](・)、
当該楕円曲線上での点加算(・)+e(・)、
当該楕円曲線上での点減算(・)-e(・)に対するグループ署名であり、
当該グループ署名の発行者鍵対
ipk = (n,a[0],a[1],a[2])；
isk = (p[1],p[2])
は、ビット長K[n]/2の安全な素数p[1]，p[2]、n = p[1]p[2]、当該nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]により定められ、
当該グループ署名の開示者鍵対
opk = (q,G,H[1],H[2])；
osk = (y[1],y[2])
は、当該素数qを法とする有限体Zqの要素y[1]，y[2]、当該有限群GGの要素G、H[1] = [y[1]]G，H[2] = [y[2]]Gにより定められ、
当該グループ署名のユーザ削除管理者鍵対
rpk = (l,b,w)；
rsk = (l[1],l[2])
は、ビット長K[l]/2の安全な素数l[1]，l[2]、l = l[1]l[2]、当該lに対する巡回部分群QR(l)の要素b，wにより定められ、
当該グループ署名のi番目のユーザに対するユーザ鍵対
msk[i] = x[i]；
mpk[i] = (h[i],A[i],e'[i],B[i])
は、当該集合Λの要素x[i]、h[i] = [x[i]]G、B[i] = b1/e'[i] (mod l)、e[i] = 2K[e] + e'[i]、a[0]a[1]x[i]≡A[i]e[i] (mod n)を満たすA[i]，B[i]，e[i]，e'[i]により定められ、
当該署名生成装置は、i番目のユーザによるメッセージmに対する署名を生成するものであり、
当該署名生成装置は、
当該有限体Zqの要素ρ[E]と、ビット長K[n]/2のビット列ρ[m]と、ビット長K[l]/2のビット列ρ[r]と、ビット長λ+K[c]+K[S]のビット列μ[x]と、ビット長K[e]+K[n]/2+K[c]+K[S]のビット列μ[s]と、ビット長K[e']+K[c]+K[S]のビット列μ[e']と、ビット長K[e']+K[l]/2+K[c]+K[S]のビット列μ[t]と、当該有限体Zqの要素μ[E]と、を、ランダムに選択する手段、
E[0] = [ρ[E]]Gと、E[1] = h[i] +e [ρ[E]]H[1]と、E[2] = h[i] +e [ρ[E]]H[2]と、E = (E[0],E[1],E[2])と、V[ComCipher] = ([μ[E]]G，[μ[x]]G +e [μ[E]]H[1]，[μ[x]]G +e [μ[E]]H[2])と、を計算する手段、
A[COM] = A[i]a[2]ρ[m] (mod n)と、B[COM] = B[i]wρ[r] (mod l)と、V[ComMPK] = a[1]μ[x]a[2]μ[s]A[COM]-μ[e'] (mod n)と、V[ComREV] = wμ[t]B[COM]-μ[e'] (mod l)と、を計算する手段、
c = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V[ComCipher],V[ComMPK],V[ComRev],m)を計算する手段、
τ[x] = c x[i] + μ[x] (mod q)と、τ[s] = c e[i] ρ[m] + μ[s] (mod q)と、τ[t] = c e'[i] ρ[r] + μ[t] (mod q)と、τ[e'] = c e'[i] + μ[e'] (mod q)と、τ[E] = c ρ[E] + μ[E] (mod q)と、を計算する手段、
署名(E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])を出力する手段
を備え、
当該計算のうち、a[1]μ[x] (mod n)と、a[2]μ[s] (mod n)と、wμ[t] (mod l)と、の、いずれか２つもしくは３つを並列に計算する
ことを特徴とする署名生成装置。
【請求項２】
請求項１に記載の署名生成装置であって、
当該計算のうち、当該楕円曲線上でのスカラーc倍演算[c](・)と、当該楕円曲線上での点加算(・)+e(・)と、当該楕円曲線上での点減算(・)-e(・)と、の計算を行う楕円計算回路と、
当該計算のうち、べき乗剰余、乗剰余の計算を行う１つまたは複数のＲＳＡ計算回路と、
当該計算のうち、Hashの計算を行うハッシュ計算回路と、
前記楕円計算回路と、前記１つまたは複数のＲＳＡ計算回路と、前記ハッシュ計算回路と、の間で計算結果を受け渡すバスと、
を備えることを特徴とする署名生成装置。
【請求項３】
請求項２に記載の署名生成装置であって、
前記ＲＳＡ計算回路は、１つ乃至５つのべき乗剰余計算回路
を備えることを特徴とする署名生成装置。
【請求項４】
グループ署名の署名を検証する署名検証装置であって、
当該グループ署名は、
所定のビット長K[n]、
所定のビット長K[l]、
所定のビット長K[e]、
所定のビット長K[e']、
楕円曲線により定義される有限群GGの次数である素数qのビット長K[q]、
任意長のビット列に適用されるハッシュ関数Hashが返す値のビット長K[c]、
いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaが統計的に区別できなくなるようなビット長K[S]、
セキュリティパラメータK = (K[n],K[l],K[e],K[e'],K[q],K[c],K[S])、
整数λ = K[n]+K[q]+K[S]、
0以上2λ未満の整数を要素とする集合Λ、
当該楕円曲線上でのスカラーc倍演算[c](・)、
当該楕円曲線上での点加算(・)+e(・)、
当該楕円曲線上での点減算(・)-e(・)に対するグループ署名であり、
当該グループ署名の発行者鍵対
ipk = (n,a[0],a[1],a[2])；
isk = (p[1],p[2])
は、ビット長K[n]/2の安全な素数p[1]，p[2]、n = p[1]p[2]、当該nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]により定められ、
当該グループ署名の開示者鍵対
opk = (q,G,H[1],H[2])；
osk = (y[1],y[2])
は、当該素数qを法とする有限体Zqの要素y[1]，y[2]、当該有限群GGの要素G、H[1] = [y[1]]G，H[2] = [y[2]]Gにより定められ、
当該グループ署名のユーザ削除管理者鍵対
rpk = (l,b,w)；
rsk = (l[1],l[2])
は、ビット長K[l]/2の安全な素数l[1]，l[2]、l = l[1]l[2]、当該lに対する巡回部分群QR(l)の要素b，wにより定められ、
当該グループ署名のi番目のユーザに対するユーザ鍵対
msk[i] = x[i]；
mpk[i] = (h[i],A[i],e'[i],B[i])
は、当該集合Λの要素x[i]、h[i] = [x[i]]G、B[i] = b1/e'[i] (mod l)、e[i] = 2K[e] + e'[i]、a[0]a[1]x[i]≡A[i]e[i] (mod n)を満たすA[i]，B[i]，e[i]，e'[i]により定められ、
当該署名検証装置は、メッセージmに対する署名σ = (E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])を検証するものであり、E = (E[0],E[1],E[2])であり、
V'[ComCipher] = ([τ[E]]G -e [c]E[0],[τ[x]]G +e [τ[E]]H[1],[τ[x]]G +e [τ[E]]H[2] -e [c]E[2])を計算する手段、
p = c 2K[2] + τ[e']と、V'[ComMPK] = a[0]ca[1]τ[x]a[2]τ[s]A[COM]-p (mod n)と、V'[ComREV] = bcwτ[t]B[COM]-τ[e'] (mod l)と、を計算する手段、
c' = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V'[ComCipher],V'[ComMPK],V'[ComREV],m)を計算する手段、
|τ[x]|≦λ+K[c]+K[S]、かつ、|τ[e']|≦K[e']+K[c]+K[S]、かつ、c' = cである場合、検証成功とし、そうでない場合、検証失敗とする手段
を備え、
当該計算のうち、a[1]τ[x] (mod n)と、a[2]τ[s] (mod n)と、wτ[t] (mod l)と、の、いずれか２つもしくは３つを並列に計算する
ことを特徴とする署名検証装置。
【請求項５】
請求項４に記載の署名検証装置であって、
当該計算のうち、当該楕円曲線上でのスカラーc倍演算[c](・)と、当該楕円曲線上での点加算(・)+e(・)と、当該楕円曲線上での点減算(・)-e(・)と、の計算を行う楕円計算回路と、
当該計算のうち、べき乗剰余、乗剰余の計算を行う１つまたは複数のＲＳＡ計算回路と、
当該計算のうち、Hashの計算を行うハッシュ計算回路と、
前記楕円計算回路と、前記１つまたは複数のＲＳＡ計算回路と、前記ハッシュ計算回路と、の間で計算結果を受け渡すバスと、
を備えることを特徴とする署名検証装置。
【請求項６】
請求項５に記載の署名検証装置であって、
前記ＲＳＡ計算回路は、１つ乃至５つのべき乗剰余計算回路
を備えることを特徴とする署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、製造コストを抑制しつつ、グループ署名の生成および検証を高速にする電子回路を実現するのに好適な、署名生成装置、ならびに、署名検証装置に関する。
【背景技術】
【０００２】
近年、暗号および署名の分野では、グループ署名の技術が提案されている。
【０００３】
一方で、特定の計算に特化した電子回路の設計において、Ｃ言語などの高級言語でその動作を記述し、動作合成を行うことで、電子回路の構成を出力させる技術も提案されている。すなわち、コンピュータ技術の進歩により、動作合成ツールや論理合成ツールを備えるＣＡＤ（Computer-Aided  Design）システムを使用して半導体集積回路の設計、解析および評価等を行うのが一般的になっている。
【０００４】
このような技術については、下記の文献に開示されている。
【特許文献１】特開２００７−２７２６７１号公報
【非特許文献１】寺西勇，従来方式の安全性設計を解消するグループ署名方式と安全性定義の改良，電子情報通信学会  基礎・境界ソサイエティ  情報通信基礎サブソサイエティ，情報セキュリティ研究会，ＩＳＥＣ  ２００４，２００４年
【非特許文献２】Multi-layer AHB Overview， ARM DVI 0045B, ARM, ２００１年−２００４年
【０００５】
ここで、特許文献１には、動作合成ツールや論理合成ツールを備える回路設計支援システムが開示されている。
【０００６】
回路設計支援システムを用いて半導体集積回路を設計する場合、設計者は、まず、入力ポートや変数のビット幅等のＨ／Ｗ化に必要な情報を含んだ動作レベル記述を用意する。
【０００７】
次に、設計者は、動作合成ツールを用いて、動作レベル記述を、実現する論理をレジスタとレジスタ間の論理機能で表現したＲＴＬ（Register  Transfer  Level；レジスタ転送レベル）記述に変換する。
【０００８】
そして、設計者は、論理合成ツールを用いて、ＲＴＬ記述をゲートレベルの論理回路に変換する。
【０００９】
このような回路設計の手法においては、非特許文献２に開示されるように、電子回路の配置をマルチレイヤ化して、情報をやりとりするための帯域を増やすことで、高速化を図るのが一般的となっている。
【００１０】
一方で、非特許文献１には、グループ署名の生成および検証を行うための基本的なアルゴリズムが開示されている。
【００１１】
すなわち、グループ署名は、所定のビット長K[n]、所定のビット長K[l]、所定のビット長K[e]、所定のビット長K[e']、楕円曲線により定義される有限群GGの次数である素数qのビット長K[q]、任意長のビット列に適用されるハッシュ関数Hashが返す値のビット長K[c]、いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaが統計的に区別できなくなるようなビット長K[S]、セキュリティパラメータK = (K[n],K[l],K[e],K[e'],K[q],K[c],K[S])、整数λ = K[n]+K[q]+K[S]、0以上2λ未満の整数を要素とする集合Λ、当該楕円曲線上でのスカラーc倍演算[c](・)、当該楕円曲線上での点加算(・)+e(・)、当該楕円曲線上での点減算(・)-e(・)に対するグループ署名である。
【００１２】
そして、当該グループ署名の発行者鍵対
ipk = (n,a[0],a[1],a[2])；
isk = (p[1],p[2])
は、ビット長K[n]/2の安全な素数p[1]，p[2]、n = p[1]p[2]、当該nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]により定められる。
【００１３】
さらに、当該グループ署名の開示者鍵対
opk = (q,G,H[1],H[2])；
osk = (y[1],y[2])
は、当該素数qを法とする有限体Zqの要素y[1]，y[2]、当該有限群GGの要素G、H[1] = [y[1]]G，H[2] = [y[2]]Gにより定められる。
【００１４】
一方、当該グループ署名のユーザ削除管理者鍵対
rpk = (l,b,w)；
rsk = (l[1],l[2])
は、ビット長K[l]/2の安全な素数l[1]，l[2]、l = l[1]l[2]、当該lに対する巡回部分群QR(l)の要素b，wにより定められる。
【００１５】
さらに、当該グループ署名のi番目のユーザに対するユーザ鍵対
msk[i] = x[i]；
mpk[i] = (h[i],A[i],e'[i],B[i])
は、当該集合Λの要素x[i]、h[i] = [x[i]]G、B[i] = b1/e'[i] (mod l)、e[i] = 2K[e] + e'[i]、a[0]a[1]x[i]≡A[i]e[i] (mod n)を満たすA[i]，B[i]，e[i]，e'[i]により定められる。
【００１６】
そして、i番目のユーザによるメッセージmに対する署名を生成する際には、まず、当該有限体Zqの要素ρ[E]と、ビット長K[n]/2のビット列ρ[m]と、ビット長K[l]/2のビット列ρ[r]と、ビット長λ+K[c]+K[S]のビット列μ[x]と、ビット長K[e]+K[n]/2+K[c]+K[S]のビット列μ[s]と、ビット長K[e']+K[c]+K[S]のビット列μ[e']と、ビット長K[e']+K[l]/2+K[c]+K[S]のビット列μ[t]と、当該有限体Zqの要素μ[E]と、を、ランダムに選択する。
【００１７】
次に、E[0] = [ρ[E]]Gと、E[1] = h[i] +e [ρ[E]]H[1]と、E[2] = h[i] +e [ρ[E]]H[2]と、E = (E[0],E[1],E[2])と、V[ComCipher] = ([μ[E]]G，[μ[x]]G +e [μ[E]]H[1]，[μ[x]]G +e [μ[E]]H[2])と、を計算する。
【００１８】
さらに、A[COM] = A[i]a[2]ρ[m] (mod n)と、B[COM] = B[i]wρ[r] (mod l)と、V[ComMPK] = a[1]μ[x]a[2]μ[s]A[COM]-μ[e'] (mod n)と、V[ComREV] = wμ[t]B[COM]-μ[e'] (mod l)と、を計算する。
【００１９】
そして、c = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V[ComCipher],V[ComMPK],V[ComRev],m)を計算する。
【００２０】
ついで、τ[x] = c x[i] + μ[x] (mod q)と、τ[s] = c e[i] ρ[m] + μ[s] (mod q)と、τ[t] = c e'[i] ρ[r] + μ[t] (mod q)と、τ[e'] = c e'[i] + μ[e'] (mod q)と、τ[E] = c ρ[E] + μ[E] (mod q)と、を計算する。
【００２１】
最後に、署名(E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])を出力する。
【００２２】
一方、メッセージmに対する署名σ = (E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])、ただしE = (E[0],E[1],E[2])を検証する際には、まず、V'[ComCipher] = ([τ[E]]G -e [c]E[0],[τ[x]]G +e [τ[E]]H[1],[τ[x]]G +e [τ[E]]H[2] -e [c]E[2])を計算する。
【００２３】
次に、p = c 2K[2] + τ[e']と、V'[ComMPK] = a[0]ca[1]τ[x]a[2]τ[s]A[COM]-p (mod n)と、V'[ComREV] = bcwτ[t]B[COM]-τ[e'] (mod l)と、を計算する。
【００２４】
さらに、c' = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V'[ComCipher],V'[ComMPK],V'[ComREV],m)を計算する。
【００２５】
そして、|τ[x]|≦λ+K[c]+K[S]、かつ、|τ[e']|≦K[e']+K[c]+K[S]、かつ、c' = cである場合、検証成功とし、そうでない場合、検証失敗とする。
【発明の開示】
【発明が解決しようとする課題】
【００２６】
したがって、このようなグループ署名の計算処理を、電子回路により、高速に実行する署名生成装置や署名検証装置が強く求められている。
【００２７】
一方で、マルチレイヤ化等により設計された電子回路は一般的にコストが上昇するので、高速化を図りつつも、製造コストを抑制できるような回路構成とすることが望ましい。
【００２８】
本発明は、上記のような課題を解決するもので、製造コストを抑制しつつ、グループ署名の生成および検証を高速にする電子回路を実現するのに好適な、署名生成装置、ならびに、署名検証装置を提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明の第１の観点に係る署名生成装置は、グループ署名の署名を生成する署名生成装置である。
【００３０】
ここで、当該グループ署名は、
所定のビット長K[n]、
所定のビット長K[l]、
所定のビット長K[e]、
所定のビット長K[e']、
楕円曲線により定義される有限群GGの次数である素数qのビット長K[q]、
任意長のビット列に適用されるハッシュ関数Hashが返す値のビット長K[c]、
いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaが統計的に区別できなくなるようなビット長K[S]、
セキュリティパラメータK = (K[n],K[l],K[e],K[e'],K[q],K[c],K[S])、
整数λ = K[n]+K[q]+K[S]、
0以上2λ未満の整数を要素とする集合Λ、
当該楕円曲線上でのスカラーc倍演算[c](・)、
当該楕円曲線上での点加算(・)+e(・)、
当該楕円曲線上での点減算(・)-e(・)に対するグループ署名である。
【００３１】
また、当該グループ署名の発行者鍵対
ipk = (n,a[0],a[1],a[2])；
isk = (p[1],p[2])
は、ビット長K[n]/2の安全な素数p[1]，p[2]、n = p[1]p[2]、当該nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]により定められる。
【００３２】
そして、当該グループ署名の開示者鍵対
opk = (q,G,H[1],H[2])；
osk = (y[1],y[2])
は、当該素数qを法とする有限体Zqの要素y[1]，y[2]、当該有限群GGの要素G、H[1] = [y[1]]G，H[2] = [y[2]]Gにより定められる。
【００３３】
さらに、当該グループ署名のユーザ削除管理者鍵対
rpk = (l,b,w)；
rsk = (l[1],l[2])
は、ビット長K[l]/2の安全な素数l[1]，l[2]、l = l[1]l[2]、当該lに対する巡回部分群QR(l)の要素b，wにより定められる。
【００３４】
また、当該グループ署名のi番目のユーザに対するユーザ鍵対
msk[i] = x[i]；
mpk[i] = (h[i],A[i],e'[i],B[i])
は、当該集合Λの要素x[i]、h[i] = [x[i]]G、B[i] = b1/e'[i] (mod l)、e[i] = 2K[e] + e'[i]、a[0]a[1]x[i]≡A[i]e[i] (mod n)を満たすA[i]，B[i]，e[i]，e'[i]により定められる。
【００３５】
なお、当該署名生成装置は、i番目のユーザによるメッセージmに対する署名を生成するものであり、以下のように構成する。
【００３６】
すなわち、当該署名生成装置は、
当該有限体Zqの要素ρ[E]と、ビット長K[n]/2のビット列ρ[m]と、ビット長K[l]/2のビット列ρ[r]と、ビット長λ+K[c]+K[S]のビット列μ[x]と、ビット長K[e]+K[n]/2+K[c]+K[S]のビット列μ[s]と、ビット長K[e']+K[c]+K[S]のビット列μ[e']と、ビット長K[e']+K[l]/2+K[c]+K[S]のビット列μ[t]と、当該有限体Zqの要素μ[E]と、を、ランダムに選択する手段、
E[0] = [ρ[E]]Gと、E[1] = h[i] +e [ρ[E]]H[1]と、E[2] = h[i] +e [ρ[E]]H[2]と、E = (E[0],E[1],E[2])と、V[ComCipher] = ([μ[E]]G，[μ[x]]G +e [μ[E]]H[1]，[μ[x]]G +e [μ[E]]H[2])と、を計算する手段、
A[COM] = A[i]a[2]ρ[m] (mod n)と、B[COM] = B[i]wρ[r] (mod l)と、V[ComMPK] = a[1]μ[x]a[2]μ[s]A[COM]-μ[e'] (mod n)と、V[ComREV] = wμ[t]B[COM]-μ[e'] (mod l)と、を計算する手段、
c = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V[ComCipher],V[ComMPK],V[ComRev],m)を計算する手段、
τ[x] = c x[i] + μ[x] (mod q)と、τ[s] = c e[i] ρ[m] + μ[s] (mod q)と、τ[t] = c e'[i] ρ[r] + μ[t] (mod q)と、τ[e'] = c e'[i] + μ[e'] (mod q)と、τ[E] = c ρ[E] + μ[E] (mod q)と、を計算する手段、
署名(E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])を出力する手段
を備える。
【００３７】
ここで、当該計算のうち、a[1]μ[x] (mod n)と、a[2]μ[s] (mod n)と、wμ[t] (mod l)と、の、いずれか２つもしくは３つを並列に計算する。
【００３８】
本発明のその他の観点に係る署名検証装置は、グループ署名の署名を検証する署名検証装置である。
【００３９】
ここで、当該グループ署名は、
所定のビット長K[n]、
所定のビット長K[l]、
所定のビット長K[e]、
所定のビット長K[e']、
楕円曲線により定義される有限群GGの次数である素数qのビット長K[q]、
任意長のビット列に適用されるハッシュ関数Hashが返す値のビット長K[c]、
いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaが統計的に区別できなくなるようなビット長K[S]、
セキュリティパラメータK = (K[n],K[l],K[e],K[e'],K[q],K[c],K[S])、
整数λ = K[n]+K[q]+K[S]、
0以上2λ未満の整数を要素とする集合Λ、
当該楕円曲線上でのスカラーc倍演算[c](・)、
当該楕円曲線上での点加算(・)+e(・)、
当該楕円曲線上での点減算(・)-e(・)に対するグループ署名である。
【００４０】
そして、当該グループ署名の発行者鍵対
ipk = (n,a[0],a[1],a[2])；
isk = (p[1],p[2])
は、ビット長K[n]/2の安全な素数p[1]，p[2]、n = p[1]p[2]、当該nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]により定められる。
【００４１】
また、当該グループ署名の開示者鍵対
opk = (q,G,H[1],H[2])；
osk = (y[1],y[2])
は、当該素数qを法とする有限体Zqの要素y[1]，y[2]、当該有限群GGの要素G、H[1] = [y[1]]G，H[2] = [y[2]]Gにより定められる。
【００４２】
そして、当該グループ署名のユーザ削除管理者鍵対
rpk = (l,b,w)；
rsk = (l[1],l[2])
は、ビット長K[l]/2の安全な素数l[1]，l[2]、l = l[1]l[2]、当該lに対する巡回部分群QR(l)の要素b，wにより定められる。
【００４３】
さらに、当該グループ署名のi番目のユーザに対するユーザ鍵対
msk[i] = x[i]；
mpk[i] = (h[i],A[i],e'[i],B[i])
は、当該集合Λの要素x[i]、h[i] = [x[i]]G、B[i] = b1/e'[i] (mod l)、e[i] = 2K[e] + e'[i]、a[0]a[1]x[i]≡A[i]e[i] (mod n)を満たすA[i]，B[i]，e[i]，e'[i]により定められる。
【００４４】
なお、当該署名検証装置は、メッセージmに対する署名σ = (E,A[COM],B[COM],c,τ[x],τ[s],τ[t],τ[e'],τ[E])を検証するものであり、E = (E[0],E[1],E[2])であり、以下のように構成する。
【００４５】
すなわち、V'[ComCipher] = ([τ[E]]G -e [c]E[0],[τ[x]]G +e [τ[E]]H[1],[τ[x]]G +e [τ[E]]H[2] -e [c]E[2])を計算する手段、
p = c 2K[2] + τ[e']と、V'[ComMPK] = a[0]ca[1]τ[x]a[2]τ[s]A[COM]-p (mod n)と、V'[ComREV] = bcwτ[t]B[COM]-τ[e'] (mod l)と、を計算する手段、
c' = Hash(K,ipk,opk,rpk,E,A[COM],B[COM],V'[ComCipher],V'[ComMPK],V'[ComREV],m)を計算する手段、
|τ[x]|≦λ+K[c]+K[S]、かつ、|τ[e']|≦K[e']+K[c]+K[S]、かつ、c' = cである場合、検証成功とし、そうでない場合、検証失敗とする手段
を備える。
【００４６】
そして、当該計算のうち、a[1]τ[x] (mod n)と、a[2]τ[s] (mod n)と、wτ[t] (mod l)と、の、いずれか２つもしくは３つを並列に計算する。
【発明の効果】
【００４７】
本発明によれば、製造コストを抑制しつつ、グループ署名の生成および検証を高速にする電子回路を実現するのに好適な、署名生成装置、ならびに、署名検証装置を提供することができる。
【発明を実施するための最良の形態】
【００４８】
発明者は、非特許文献１に開示されるアルゴリズムを単純に動作レベル記述として記述し、従来の電子回路設計における高速化の手法によって動作合成をしても、製造コストの抑制の問題が解決できないことに鑑み、以下のような手法によって、電子回路設計を行うこととした。
【００４９】
すなわち、当該アルゴリズムには、基本的な演算の複雑な組み合わせが多数含まれる。
【００５０】
図１は、グループ署名生成の際の各演算（Sub-IP operation）に対するビット長（Bit Length）、クロックサイクル数（CLK cycles）、実行回数（Times）、全体に占める割合（Ratio）を示す表を表す説明図である。
【００５１】
図２は、グループ署名検証の際の各演算（Sub-IP operation）に対するビット長（Bit Length）、クロックサイクル数（CLK cycles）、実行回数（Times）、全体に占める割合（Ratio）を示す表を表す説明図である。
【００５２】
この表を見ると、従来、電子回路化が進められてきたアルゴリズムにおけるものとは異なる種類の基本演算が利用されており、また、当該基本演算に要するクロックサイクル数も異なるため、速度を向上させるためには、従来とは異なる観点から並列化を進める必要があることがわかる。
【００５３】
また、図１および図２に示すように、データのビット幅が大きいことから、データのほとんどは、レジスタではなくＳＲＡＭ（Static Random Access Memory）に格納すべきものであることがわかる。そして、各基本演算に要する計算時間の大半は、ＳＲＡＭアクセスに要する時間である。
【００５４】
一方で、図１および図２からは、データを転送するために必要な時間の割合は極めて低いこともわかる。
【００５５】
このような観点から、発明者は、動作レベル記述に制約として付加すべき基本的なハードウェアアーキテクチャとして、単一のＩＰコアにグループ認証計算回路すべてを組み込んだ電子回路設計を進めることとした。
【００５６】
図３は、グループ署名ＩＰコアの概要構成を示す説明図である。以下、本図を参照して説明する。
【００５７】
ＩＰコア（グループ署名ＩＰコア）３０１は、複数の高速演算ユニット（サブＩＰ）３０２と、データ転送コントローラ３０３と、が、ローカルバス３０４を介して接続される内部構造となっている。
【００５８】
ローカルバス３０４のように、バンド幅の狭い単一バスを利用するのは、グループ署名アルゴリズムに特有の手法であり、発明者が上記のような分析を行い、従来の手法とは異なる観点から解決策を考案することで得られた手法である。
【００５９】
上記のように、グループ署名アルゴリズムに特有の事情として、データ転送に要する時間の占める割合が極めて低いことがある。このため、バス上の転送トラフィック量は少ないと考えられるので、高性能回路を構成する場合であっても、複数のバスや、バンド幅の広いバスは不要である。
すなわち、一般の回路アーキテクチャ設計では、高性能化を図る場合にはバスの広帯域化を行うのが常套手段であるが、グループ署名アルゴリズムでは上述した事情があるため、バスの広帯域化を行わずに高性能化を図ることができるのである。
しかも、グループ署名アルゴリズムにおける特定の演算には、データの依存性が低く、並列に計算することが可能であることがわかる。従って、サブＩＰ３０２毎に並列に計算を行い、必要に応じてローカルバス３０４を介して計算結果をやりとりすることで計算の高速化を図ることができる。
【００６０】
また、単一バスアーキテクチャを採用することによって、サブＩＰ３０２の個数を増減させるなどの構成設定の変更が極めて容易となる。この際には、グループ署名アルゴリズムに内在する並列可能性には、上限があると考えられるため、これに応じてサブＩＰ３０２の個数を定めれば電子回路の製造コスト等の抑制を図ることができる。
【００６１】
メインＣＰＵ３１０は、グローバルオンチップバス３３０に接続された各ＩＰコア（例えば、ＩＰコア３０１や別タスクのＩＰコア３２０等）を制御することにより、署名生成装置（署名検証装置）全体の動作を制御する。メインＣＰＵ３１０は、例えば、図示しないＲＯＭに記憶された署名生成プログラム（署名検証プログラム）を実行する。
【００６２】
グローバルオンチップバス３３０は、メインＣＰＵ３１０と、ＩＰコア３０１と、別タスクのＩＰコア３２０と、を相互に接続する。
【００６３】
バスブリッジ３０５は、ＩＰコア３０１内のローカルバス３０４と、グローバルオンチップバス３３０と、を相互に接続する。
【００６４】
各サブＩＰ３０２は、それぞれ、楕円曲線演算（ＥＣ；Elliptic Curve）、剰余演算、多倍長整数演算、ハッシュ演算に対応付けられている。また、演算の種類やデータビット幅に応じて、複数の機能モードが用意されている。
【００６５】
これらの演算は、非特許文献１に開示されるグループ認証アルゴリズムの計算において利用されるものである。すなわち、ＥＣ演算は、楕円曲線上でのスカラー倍、加算、減算（[c](・)，+e，-e）を行うものである。剰余演算は、べき乗剰余（ab (mod n)）や乗剰余（a b (mod n)）を計算するものである。ハッシュ演算は、ビット列からハッシュ値を計算する（Hash）ものである。
【００６６】
図４は、サブＩＰ３０２の内部構造を示す説明図である。以下、本図を参照して説明する。
【００６７】
本図に示すように、サブＩＰ３０２は、有限状態機械（ＦＳＭ；Finite State Machine）コントローラ４０１によって制御され、データＲＡＭ４０２には処理の対象となるデータが格納される。
【００６８】
演算回路４０３は、各種の演算を行うものであるが、高速計算のために、剰余演算は、モントゴメリードメインの上で計算され、ＥＣ演算は、モントゴメリー数値表現のヤコビアン座標の上で計算される。
【００６９】
データＲＡＭ４０２と演算回路４０３はデータバス４０４で接続されてデータのやり取りを行う。ここで、データＲＡＭ４０２に対するポートの個数は、同時に実行される読み書きアクセスの最大数に定めることとすれば、高速な処理が期待できる。
【００７０】
図５は、各サブＩＰ３０２が接続されたＩＰコア３０１の詳細を示す説明図である。以下、本図を参照して説明する。
【００７１】
本図に示すように、本実施形態に係るＩＰコア３０１では、ＥＣ演算サブＩＰ５０１は、１個乃至５個、剰余演算サブＩＰ５０２（「ＲＳＡ演算サブＩＰ」と呼ぶこともある。）は、１個乃至５個、多倍長整数演算サブＩＰ５０３は、１個、ハッシュ演算サブＩＰ５０４は、１個からなっており、狭バンド幅の単一レイヤーバスであるローカルバス３０４によって接続されている。
【００７２】
各サブＩＰ３０２の種類と個数は、計算の高速化および回路面積の抑制による低コスト化の観点から上記の範囲が望ましい。これ以上サブＩＰ３０２の個数を増やしても、高速になることはないからである。また、ローカルバス３０４を採用することにより、バス配線を簡略化することができ、これも低コストに貢献することができる。
【００７３】
図６は、本実施形態に係るＩＰコア３０１の設計手法を説明するためのフローチャートである。以下、本図を参照して説明する。
【００７４】
本設計においては、伝統的なブロック構築アプローチを採用する。すなわち、各サブＩＰ３０２を単独でテストしてから、ＩＰコア３０１全体の統合を行うのである。
【００７５】
まず、ステップ１においては、Ｃ言語やＣ＋＋言語を利用したプログラミングによって、ソフトウェア的に計算モデルを作成する。
【００７６】
次に、ステップ２においては、各サブＩＰ３０２がローカルバス３０３によって接続されるハードウェアモデルを適当に定めて作成する。
【００７７】
さらに、ステップ３においては、標準的な動作調整を行い、性能データを取得する。
【００７８】
そして、ステップ４では、各サブＩＰ３０２の動作調整を行い、これらが並列に動作するようにする。
【００７９】
最後に、ステップＳ５において、サブＩＰ３０２をＩＰコア３０１に統合して、ＦＰＧＡプロトタイプにおいて動作のデバッグを行う。
【００８０】
ステップ１、２、３、５においては、Ｃ言語を基本としたハードウェア設計、動作調整、ＦＰＧＡプロトタイプ作成を行う。この際には、図３乃至図５に示すような新規なモデルを採用することとするが、一旦モデルを採用してしまえば、具体的な手法については、公知の技術を採用することができる。このような構成としたのは、以下の理由による。
（１）ＲＴＬシミュレーションを行わなくとも、各サブＩＰ３０２を効率的に開発できる。各サブＩＰ３０２のシミュレーションは、ＩＰコア３０１全体のシミュレーションに比べて高速にでき、分割して設計を行ってから統合する方が、圧倒的に作業量が少ない。
（２）全体性能の設定を容易に変更することができるようになる。各サブＩＰ３０２の性能は、データＲＡＭ４０２の種類に大きく左右されるが、ＩＰコア３０１全体を構築してからデータＲＡＭ４０２の種類を変更することは、設計手法上難しい。
（３）ブロック構築アプローチを採用していても、全ＩＰコア３０１の検証は必要である。これは、データ転送コントローラ３０３のマイクロコード（ファームウェア）をデバッグするためである。この際、ＲＴＬシミュレーションはあまりに低速であるため、ＦＰＧＡプロトタイプを作成してデバッグするのが適切である。
【００８１】
近年、動作合成技術が大幅に発達しているが、純粋なＣ言語のソフトウェアコードから効率のよいハードウェアを何も変更せずに合成することは未だに難しい。このため、図６のステップ２において、ある程度の書き換え作業が必要である。以下に、必要な処理を示す。
（１）データビット幅の最適化と余分な演算の除去。グループ署名だけでなく公開鍵の暗号化ソフトウェアは大抵特別な関数ライブラリを使用する。なお、その関数ライブラリの関数は、Ｃに組み込まれた３２ビット或いは６４ビットの整数演算の組み合わせによる長いビットの算術演算を実行する。このため、注意深いオーバーフロー制御もまたソフトウェアに実装する必要がある。しかしながら、ハードウェアでは、任意のビット幅の直接的な演算が可能である。
（２）算術演算と数値表現の最適化。ソフトウェアでは、２の補数表現による整数演算のみが可能であるが、ハードウェアでは、様々な数値表現による様々な演算を行うように柔軟な構造（例えば、評価指数システムにおけるＧＦ演算）をとることが可能である。
（３）動的なメモリ割り当て、動的ポインタ及び再帰の除去。もし、平衡木や線形リストのようなソフトウェアのようなデータ型が使用されていれば、それらも除去しなければならない。
（４）ソースコードに適切な動作合成制御演算を追加する。最も頻繁に用いられるオプションの一つは、内側のループに配置される「ループホールディング」である。例えば、ループ内にＳＲＡＭへアクセスする記述（ＳＲＡＭをチェックするための記述）がある場合、動作合成装置は当該記述により表現される処理が冗長な処理であるとして当該記述を省略して動作合成する可能性がある。当該オプションは、このような事態を防止するために使用される。
動作合成により得られたユニットの性能（性能結果）は、ＲＳＡやＥＣＣの従来の手作りのＲＴＬの性能に匹敵する。なお、クロックサイクル数は、ＡＳＩＣ／ＦＰＧＡの製造ライブラリとは独立している。
【００８２】
ここで、総合的なＩＰ性能は、同時にどれだけの数のサブＩＰ演算が実行できるかによりほぼ決定する。しかしながら、標準的な動作合成は、Ｃに組み込まれた演算子（＋、−、×、／、％）の並列スケジュールをサポートするだけであり、より高水準の関数のスケジュールもサポートせず、また、実行時に動作モードが決定する関数のスケジュールもサポートしない。
【００８３】
そこで、サブＩＰレベル（Ｃ関数ライブラリレベル）の特注の動作合成装置（以下、単に「動作合成装置」という。）を製造して用いる。
この動作合成装置の入力は、
（ｉ）アルゴリズム全体の逐一的記述。
（ｉｉ）サブＩＰの番号。
（ｉｉｉ）ＲＴＬシミュレーション、ＦＰＧＡプロトタイピングあるいは理論的計算により得られる、サブＩＰにおける全ての演算のクロックサイクル数。
である。
【００８４】
動作合成装置は、それにより各サブＩＰ演算の開始順やサブＩＰユニット番号の割り当てが特定される、並列計算順序を出力する。この出力は、データ転送コントローラのマイクロコードを書くために用いられる。
【００８５】
動作合成装置は、サブＩＰが利用可能になった場合に、実行時間がなるべく長い演算を割り当てて直ちに実行を開始させる、といった近似的アルゴリズムを用いてＲＣＰＳＰ（Ｒｅｓｏｕｒｃｅ  Ｃｏｎｓｔｒａｉｎｅｄ  Ｐｒｏｊｅｃｔ  Ｓｃｈｅｄｕｌｉｎｇ  Ｐｒｏｂｌｅｍ）を解決する。
【００８６】
この動作合成装置は、グループ署名に特化しており、多くの一般的なＥＳＬ／ＴＬＭ合成の問題が以下の側面において除去される。
（１）サブＩＰ間のデータ転送時間が無視できる。
（２）ローカルバストポロジの探索と合成が不要である。
（３）マクロパイプラインの構築やデータ転送プロトコルの合成が不要である。
【００８７】
上述の動作合成装置を用いて、合計計算速度とサブＩＰの数との間の関係を調査した。標準／高水準セキュリティーレベルにおける署名生成／検証の結果を図７乃至１０に示す。
【００８８】
図７は、標準セキュリティーレベルにおける署名生成の際の剰余演算サブＩＰの数（Ｎｕｍｂｅｒ  ｏｆ  Ｍｏｄｕｌａｒ  ａｒｉｔｈｍｅｔｉｃ  ｓｕｂ−ＩＰｓ）と合計待ち時間（Ｔｏｔａｌ  ｌａｔｅｎｃｙ（ｍｓｅｃ  ａｔ  １００ＭＨｚ））との関係を示す。図８は、高水準セキュリティーレベルにおける署名生成の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す。図９は、標準セキュリティーレベルにおける署名検証の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す。図１０は、高水準セキュリティーレベルにおける署名検証の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す。
【００８９】
これらの結果は、図１、２に示すクロックサイクル数の絶対値から取得したものであるが、例え製造ライブラリやターゲット製品が代わったとしても同様の結果が得られるであろう。なぜなら、クロックサイクル数はライブラリとは独立しているためである。
【００９０】
もし、全ての演算が連続的に実行されれば、図１、２に示すように、全計算時間の８０％以上がべき乗剰余により占められる。そこで、剰余演算を実行するサブＩＰの数を増やすと、４、５個の剰余サブＩＰを用いたときに最高速度に達する。さらに、標準セキュリティーレベルにおいて６４ビットのべき乗剰余を用いる場合を除き、他のサブＩＰの数を増やしても効果がない。
【００９１】
また、ＲＡＭのデータビット幅と剰余演算サブＩＰ内のモントゴメリー乗算器とを増やせば、同様に効果的である。べき乗剰余により消費されるクロックサイクル数は、ｍをＲＡＭのビット幅、ｎ１を基数（１０２４又は２０４８）のビット幅、ｎ２を指数のビット幅として、Ｏ（（ｎ１／ｍ）２・ｎ２）となる。ｍが増加したときに最大クロック周波数はＯ（１／ｌｏｇｍ）のオーダで減少するが、その減少の効果はクロックサイクル数の減少と比較して小さい。
【００９２】
他の重要な注目すべき点は、サブＩＰの最適数は、署名生成と署名検証との間で同じである。このため、同じハードウェアを生成と検証とで性能を落とすことなく用いることが可能である。
【００９３】
例えば、１３０ｎｍ標準セルＡＳＩＣに実装する場合の、各サブＩＰ（標準セキュリティーレベル）の回路サイズを考える。もし、ＡＨＢシングルレイヤーバスをローカルバスとして用い、各サブＩＰの数が１である場合には、合計回路サイズは３５０Ｋゲートとなる。剰余演算ユニットを１つ付加すると、合計回路サイズは５０Ｋゲート増加する。
【００９４】
もし、高水準セキュリティーレベルが選択されると、論理ゲートの数は同じままであり、ＳＲＡＭ（Ｄｕａｌ  Ｐｏｒｔ  ＲＡＭ）の量が倍になる。もし、１３０ｎｍ標準セルライブラリに配置したなら、最悪の遅延条件での最大クロック周波数は、１５０〜２００ＭＨｚである。同様の回路をＦＰＧＡデバイスに配置し、署名生成と署名検証は予測時間内に正常に実行されることを確認した。
【００９５】
上述のように、本発明によれば、製造コストを抑制しつつ、グループ署名の生成および検証を高速にする電子回路を実現するのに好適な、署名生成装置、ならびに、署名検証装置を提供することができる。
【図面の簡単な説明】
【００９６】
【図１】グループ署名生成の際の各演算のクロックサイクル数等を説明するための図である。
【図２】グループ署名検証の際の各演算のクロックサイクル数等を説明するための図である。
【図３】本発明の実施形態に係る署名生成装置が備えるＩＰコアの概要構成を示すブロック図である。
【図４】サブＩＰの内部構造を説明するための図である。
【図５】ＩＰコアの詳細を説明するためのブロック図である。
【図６】ＩＰコアの設計手法を説明するためのフローチャートである。
【図７】標準セキュリティーレベルにおける署名生成の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す図である。
【図８】高水準セキュリティーレベルにおける署名生成の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す図である。
【図９】標準セキュリティーレベルにおける署名検証の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す図である。
【図１０】高水準セキュリティーレベルにおける署名検証の際の剰余演算サブＩＰの数と合計待ち時間との関係を示す図である。
【符号の説明】
【００９７】
３０１  ＩＰコア
３０２  サブＩＰ
３０３  データ転送コントローラ
３０４  ローカルバス
３０５  バスブリッジ
３１０  メインＣＰＵ
３２０  別タスクのＩＰコア
３３０  グローバルオンチップバス
４０１  ＦＳＭコントローラ
４０２  データＲＡＭ
４０３  演算回路
４０４  データバス
５０１  ＥＣ演算サブＩＰ
５０２  剰余演算サブＩＰ
５０３  多倍長整数演算サブＩＰ
５０４  ハッシュ演算サブＩＰ
【図１】
2010014912.tif 000003
【図２】
2010014912.tif 000004
【図３】
2010014912.tif 000005
【図４】
2010014912.tif 000006
【図５】
2010014912.tif 000007
【図６】
2010014912.tif 000008
【図７】
2010014912.tif 000009
【図８】
2010014912.tif 000010
【図９】
2010014912.tif 000011
【図１０】
2010014912.tif 000012