(57)【要約】  平均応答速度を低下させることなく、複数のグループ署名処理を少ない処理装置数、少ない電力消費で並列に実行する。署名処理装置は、署名処理手続きに含まれる基本演算の種類ごとにサブシステムを有する。各サブシステムは、１つまたは複数の基本演算実行部とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続した構成を有する。複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理する。このとき、各サブシステムは単一のリクエストに占有されることなく、異なるリクエスト中の演算であっても空いている基本演算部に割り付けて同時実行させる。
2012056608.tif 000002
【特許請求の範囲】
【請求項１】
署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行手段とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムを構成し、
演算リクエストを中継するバッファメモリを介して複数の前記サブシステムを接続した署名処理装置。
【請求項２】
請求項１に記載の署名処理装置において、
複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理し、
前記サブシステムはそれぞれ単一のリクエストに占有されることなく異なるリクエスト中の演算をそれぞれの基本演算手段に割り付けて同時実行する
ことを特徴とする署名処理装置。
【請求項３】
請求項1または請求項2に記載の署名処理装置において、
前記サブシステムとして、剰余演算サブシステムと、楕円曲線演算サブシステムと、整数演算・ハッシュ演算サブシステム、とを有し、
前記剰余演算サブシステムは、剰余演算を実行する複数の剰余演算手段とそれらの制御を行うディスパッチャとを含み、
楕円曲線演算サブシステムは、楕円曲線演算を実行する複数の楕円曲線演算手段とそれらの制御を行うディスパッチャとを含み、
整数演算・ハッシュ演算サブシステムは、ハッシュ演算を実行する一または複数のハッシュ演算手段と、整数演算を実行する一または複数の整数演算手段と、それらの制御を行うディスパッチャとを含んで構成されている
ことを特徴とする署名処理装置。
【請求項４】
請求項3に記載の署名処理装置において、
前記サブシステムとして、さらに、乱数生成演算サブシステムを含み、
前記乱数生成演算サブシステムは、乱数生成演算を実行する一または複数の乱数生成手段とそれらの制御を行うディスパッチャとを含んで構成されている
ことを特徴とする署名処理装置。
【請求項５】
請求項4に記載の署名処理装置において、
前記乱数生成演算サブシステムの前記乱数生成手段は一つである
ことを特徴とする署名処理装置。
【請求項６】
請求項3から請求項5のいずれかに記載の署名処理装置において、
楕円曲線演算サブシステムの前記楕円曲線演算手段の個数は、前記楕円曲線演算サブシステムの前記剰余演算手段の個数と同じかそれよりも少ない個数である
ことを特徴とする署名処理装置。
【請求項７】
請求項3から請求項6のいずれかに記載の署名処理装置において、
前記整数演算・ハッシュ演算サブシステムの前記整数演算手段が一つである
ことを特徴とする署名処理装置。
【請求項８】
請求項3から請求項7のいずれかに記載の署名処理装置において、
前記整数演算・ハッシュ演算サブシステムの前記ハッシュ演算手段が一つである
ことを特徴とする署名処理装置。
【請求項９】
署名処理手続きに含まれる基本演算を１つまたは複数の基本演算実行手段で同時に複数実行し、
演算状態を監視して受け付け可能な基本演算実行手段に順次演算実行を指示し、
単一のリクエストに占有されることなく異なるリクエスト中の演算をそれぞれの基本演算手段に割り付けて同時実行するようにさせる
ことを特徴とする署名処理方法。
【請求項１０】
複数のプロセッサを有するコンピュータを、
署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行手段とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムとして機能させ、
複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理させることを特徴とする署名処理プログラムを格納した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名処理装置に関し、詳しくは、複数のグループ署名を同時に処理するグループ署名処理装置に関する。
【背景技術】
【０００２】
近年、暗号および署名の分野では、グループ署名の技術が提案されている。グループ署名技術とは、グループに署名者が所属しているかどうかを認証する技術である。署名者は、自分自身がグループ内のどのメンバであるかは匿名にすることができる。ただし、特権者は必要に応じてメンバの匿名性を剥奪することが可能であり、匿名性の悪用を防止することができる。【０００３】
グループ署名技術は、例えば下記の文献（特許文献1、非特許文献1から3）に開示されている。非特許文献1には、グループ署名の生成および認証を行うための基本的なアルゴリズムが開示されている。さらに、非特許文献1には、小規模でありながらグループ署名の処理を高速に行うことができる回路が開示されている。
また、特許文献1には署名処理装置が開示されている。特許文献1では、図13に示すように、署名処理装置300は、楕円曲線演算ユニット301、剰余演算ユニット302、擬似乱数生成ユニット303、整数演算ユニット305およびハッシュ演算ユニット306を備え、それぞれのユニットが低帯域バスで接続されている。【０００４】
ところで、これらの文献で開示されているグループ署名装置は、単独の利用者が使用する可搬端末機器などを対象としており、同時に複数の利用者が取り扱うような装置を想定していない。しかしながら、図13に示すように、署名の処理は個人利用の端末だけでなく多数の利用者が同時にアクセスしてくる広域データセンタのサーバなどでも行う必要がある。この場合、署名処理も複数を同時に行う必要が生じてくる。【０００５】
同時に複数の処理リクエストが発生する場合には、発生したリクエストを順次キューに投入しておき、逐次プロセッサ等で処理するのが一般的である。共通鍵暗号演算や公開鍵暗号演算では、このような処理方式がよく用いられている。【０００６】
ところが、グループ署名では一回の処理に0.1〜数秒という時間がかかる。そのため、複数の利用者を対象とするグループ署名の処理においてリクエストの処理を逐次行うとすると、平均応答時間が著しく悪化し、サービス提供の体感速度が遅くなってしまうという問題が生じる。
ここで、複数の利用者を対象とするグループ署名の平均応答時間を単独の署名と同程度に保ったままにするには、図14に示すように、署名処理装置をリクエストの数だけ用意し並列に処理させるのが一般的解決手法とも考えられる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2010-014912号公報
【特許文献２】特開2006-243690号公報
【特許文献３】特開2007-234001号公報
【特許文献４】特表2009-500710号公報
【非特許文献】
【０００８】
【非特許文献１】森岡澄夫，荒木俊則，一色寿幸，尾花賢，佐古和恵，「二段階動作合成によるグループ署名ASICの実装と評価」，電子情報通信学会  VLSI研究会，VLD2009-128, pp.175-180, 2010年
【非特許文献２】J. Camenish and J. Groth, "Group signatures: Better efficiency and new theoretical aspects," SCN2004, LNCS Vol.3352, pp.120-133, 2004.
【非特許文献３】T. Isshiki, K. Mori, K. Sako, I. Teranishi, and S. Yonezawa, "Using Group Signature for Identity Management and its Implementation," DIM2006, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、N個のリクエストを扱うために署名処理装置を多重化するとなると、コストはN倍になる。署名処理をLSI回路やプログラム処理で実行する場合でも、処理を単純に多重化するとLSI回路のチップ面積がN倍になり、プログラム処理のためのプロセッサ数がN倍になる。また、これらに伴って消費電力もN倍になる。
ここで、例えば、広域データセンタに設置されるサーバ装置の場合、装置の数は設備費用や運用費に直接的に影響してくる。また、消費電力の増加は、装置の温度管理などを困難にする。【００１０】
このため、複数の利用者を対象とするグループ署名の処理において、署名処理の平均応答時間を悪化させることなく、なるべく少ない装置数で多数のリクエストを同時処理できることが望ましい。これは、署名処理をLSI回路やプログラムで行う場合についても同様である。【００１１】
本発明の目的は、署名処理の平均応答速度を低下させることなく、電力消費の増加率や回路規模の増大率を抑えつつも、多くの署名処理を行える署名生成装置および署名認証装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の署名処理装置は、署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行部とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムを構成し、
演算リクエストを中継するバッファメモリを介して複数の前記サブシステムを接続したことを特徴とする。【００１３】
本発明の署名処理方法は、
署名処理手続きに含まれる基本演算を１つまたは複数の基本演算実行部で同時に複数実行し、
演算状態を監視して受け付け可能な基本演算実行部に順次演算実行を指示し、
単一のリクエストに占有されることなく異なるリクエスト中の演算をそれぞれの基本演算部に割り付けて同時実行するようにさせる
ことを特徴とする。【００１４】
本発明の署名処理プログラムは、
複数のプロセッサを有するコンピュータを、
署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行部とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムとして機能させ、
複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理させることを特徴とする。
【図面の簡単な説明】
【００１５】
【図１】第1実施形態としての署名生成装置の全体構成を示す図。
【図２】第1実施形態において、乱数生成サブシステムの構成を示す図。
【図３】第1実施形態において、楕円曲線演算サブシステムの構成を示す図。
【図４】第1実施形態において、剰余演算サブシステムの構成を示す図。
【図５】第1実施形態において、ハッシュ・整数演算サブシステムの構成を示す図。
【図６】第1実施形態において、ディスパッチャの動作を示すフローチャート。
【図７】第1実施形態において、サブシステム間での通信に使われるパケットの構成図。
【図８】第1実施形態において、グループ署名生成のスキームを示すフローチャート。
【図９】本発明の効果を具体的に測定した結果を示すグラフ。
【図１０】第3実施形態としての署名認証装置の構成を示す図。
【図１１】第3実施形態において、グループ署名認証のアルゴリズムを示すフローチャート。
【図１２】演算種類を特定せずに、本発明の趣旨を実現するための署名処理装置を概念的に示した図。
【図１３】背景技術としての署名処理装置の構成を示す図。
【図１４】署名処理装置をリクエストの数だけ並列配置した状態を示す図。
【発明を実施するための形態】
【００１６】
次に、本発明の実施の形態を図示するとともに図中の各要素に付した符号を参照して説明する。
（第1実施形態）
本発明に係る第1実施形態について説明する。
図1は、本発明にかかる署名生成装置（署名処理装置）の構成を示す図である。
署名生成装置100は、
乱数生成サブシステム101と、
楕円曲線演算サブシステム107と、
剰余演算サブシステム112と、
ハッシュ・整数演算サブシステム118と、
パケット中継バッファメモリ105、106、117と、を備える。
【００１７】
ここで、乱数生成サブシステム101と楕円曲線演算サブシステム107とは、パケット中継バッファメモリ105を介して接続されている。
乱数生成サブシステム101と剰余演算サブシステム112とは、パケット中継バッファメモリ106を介して接続されている。
楕円曲線演算サブシステム107および剰余演算サブシステム112の演算結果は、パケット中継バッファメモリ117を介してハッシュ・整数演算サブシステム118に入力される。
【００１８】
署名生成装置100は、一つの投入口130と、一つの出力口131と、を有している。そして、前記投入口130から複数のリクエストパケットを順次受け付け、最終結果（署名または認証）を前記出力口131から順次出力する。リクエストパケットとは、例えば、開封管理者の公開鍵、ユーザの秘密鍵、発行管理者の公開鍵、失効管理者の公開鍵、メッセージなどである。
署名生成装置100は、一つのリクエストの処理が総て終わっていなくても、次のリクエストを受け付ける。受け付けられたリクエストは、パケット中継バッファメモリ105、106、117を介して前段から後段のサブシステム101、107、112、118へ順次送られていき、演算処理は進行する。
【００１９】
図2から図5に各サブシステムの構成を示す。
図2は、乱数生成サブシステム101の構成を示す図である。
図3は、楕円曲線演算サブシステム107の構成を示す図である。
図4は、剰余演算サブシステム112の構成を示す図である。
図5は、ハッシュ・整数演算サブシステム118の構成を示す図である。
【００２０】
本実施形態においては、各サブシステム101、107、112、118は、内部にディスパッチャ102、108、113、119と、ローカルバス104、111、116、123と、１つまたは複数の基本演算ユニット103、110、114、120、121を有する。また、サブシステム101、107、112、118には、内部にローカルなバッファメモリ109、115、122を持つものもある。
【００２１】
具体的には、乱数生成サブシステム101は、図2に示されるように、ディスパッチャ102と、擬似乱数生成ユニット103と、ローカルバス104と、を備える。
ここでは、擬似乱数生成ユニット103は一つだけ設けられている。
乱数生成サブシステム101は、署名生成処理において乱数生成を実行する。
【００２２】
楕円曲線演算サブシステム107は、図3に示されるように、ディスパッチャ108と、基本演算器としての楕円曲線演算ユニット110と、一時データバッファメモリ109と、ローカルバス111と、を備える。
ここで、楕円曲線演算ユニット110は複数設けられており、本実施形態では6つの楕円曲線演算ユニット110が設けられている。楕円曲線演算サブシステム107は、署名生成処理において楕円曲線演算を実行する。
【００２３】
剰余演算サブシステム112は、図4に示されるように、ディスパッチャ113と、基本演算器としての剰余演算ユニット114と、一時データバッファメモリ115と、ローカルバス116と、を備える。
ここで、剰余演算ユニット114は複数設けられており、本実施形態では9つの剰余演算ユニット114が設けられている。
剰余演算サブシステム112は、署名生成処理において剰余演算を実行する。
【００２４】
ハッシュ・整数演算サブシステム118は、ディスパッチャ119と、ハッシュ演算ユニット120と、整数演算ユニット121と、一時データバッファメモリ122と、ローカルバス123と、を備える。
ここでは、ハッシュ演算ユニット120と、整数演算ユニット121と、は一つずつ設けられている。
ハッシュ・整数演算サブシステム118は、署名生成および署名認証において、ハッシュ演算および整数演算を実行する。
【００２５】
一つのリクエストに対するグループ署名処理は、複数の乱数生成演算、複数の楕円曲線演算、複数の剰余演算、複数のハッシュ演算、複数の整数演算が組み合わされて構成されている。さらに、それぞれの演算処理において、仮に演算処理自体の種類が同じであっても扱うデータのビット幅は異なってくる。
このような複数の演算が組み合わされるので、サブシステムごとにかかる演算時間も異なってくるし、内部の各基本演算にかかる時間も一定ではない。したがって、各サブシステムについて着目すると、グループ署名の演算中であっても内部の基本演算ユニットには動いているものと停止しているものが混在する。各演算の実行開始タイミングは、入力パケットが到来する間隔や数によって動的に変化するものであり、静的には決定できない。
このため、入力パケットや演算実行状況を常時監視し、空いている演算器に演算を指示する制御機構が必要となる。
この働きをするものが、ディスパッチャ102、108、113、119である。
【００２６】
図6は、ディスパッチャの動作を示すフローチャートである。
ディスパッチャは、入力バッファおよび出力バッファ中のパケット数と、基本演算器の利用状況と、を常時モニタする。
入力バッファに入力パケットが存在する場合（ST502）、ディスパッチャはそれを取り出し（ST503）、そのパケット演算を実行するための引数の演算が総て終了しているかを判定する（ST504）。すなわち、ディスパッチャは、演算の依存関係についても監視し、あるリクエストがあるとき、それを開始するのに必要な演算が全て終了し、データが揃っているかを確認する（ST504）。そして、パケット演算を実行するための引数の演算が総て終了している場合（ST504：YES）、空いている演算ユニットがあるか否かを判断し（ST505）、演算を実行できる演算ユニットがあれば（ST505：YES）、その演算器に演算処理を割り当てて演算を開始させる（ST506）。
演算が終了したら（ST501：YES）、出力バッファないし一時データバッファへ結果を格納する（ST509）。
【００２７】
図7は、サブシステム間での通信に使われるパケットの構成図である。
パケット401は、行うべき演算処理の内容を指定するものである。
パケット401は、どの署名リクエストであるかを示すリクエスト番号402、署名処理のうち何番目の演算を行っているかを示す現演算番号403、この演算を開始するまでに終了していないといけない１つまたは複数の演算を示す前演算番号404、演算に必要な数値を表す演算引数405、得られた演算結果をどこへ転送するかの指定406、などのフィールドを有する。
【００２８】
次に、図8を参照して、グループ署名生成のスキームについて説明する。
なお、グループ署名の基本的アルゴリズムについては、非特許文献1にも開示されている。
【００２９】
グループ署名のスキームには、ユーザ、発行管理者、失効管理者、開封管理者の4つのエンティティが参加する。
ユーザは、グループのメンバであり、署名生成と署名認証とを行う。
発行管理者は、ユーザをグループに追加する権限を有する。
失効管理者は、ユーザをグループから除去する権限を有している。
開封管理者は、署名者を特定する権限を有する。
【００３０】
ここで、以下の説明のために、セキュリティパラメータK=(K[n], K[l], K[e], K[e'], K[q], K[c], K[S])を導入する。
K[n]、K[l]、K[e]、K[e']は、各パラメータn, l, e, e'それぞれについてのビッ ト数を示しており、つまり、K[n]、K[l]、K[e]、K[e']はそれぞれ所定のビット長K[n]、K[l]、K[e]、K[e']を有する。
K[q]は、楕円曲線に基づいて定義される有限群GGの次数である素数qのビット長を示す。
K[c]は、任意長のビット列に適用されるハッシュ関数Hashが返す値cのビット長を示す。
K[S]は、いかなる整数aに対しても|a|+K[S]ビット長の乱数rを選択したときに、a+rとaとが統計的に区別できなくなるようなビット長を示す。
【００３１】
グループ署名のアルゴリズムは、このようなセキュリティパラメータKと、整数λ=K[n]+K[q]+K[S]と、0以上2λ未満の整数を要素とする集合Λと、楕円曲線上でのスカラー倍演算と、楕円曲線上での点加算と、楕円曲線上での点減算と、に対する演算からなる。
なお、以下では、「xs」は楕円曲線上の点に対するスカラー倍演算を示し、「+e」は楕円曲線上での点加算を示し、「-e」は楕円曲線上での点減算を示す。
【００３２】
次に、グループ署名のユーザ、発行管理者、失効管理者および開封管理者がそれぞれ有する鍵対（公開鍵および秘密鍵）について以下に説明する。
【００３３】
グループ署名の発行管理者が持つ鍵対（ipk, isk）は、次の式に示すように、ビット長がK[n]/2である暗号数理的に安全な素数p[1]，p[2]と、これら素数の積n=p[1]p[2]と、この積nに対する巡回部分群QR(n)の要素a[0]，a[1]，a[2]と、に基づいて定められる。
なお、ipkは発行管理者の公開鍵であり、iskは発行管理者の秘密鍵である。
【００３４】
発行管理者の公開鍵ipk=(n, a[0], a[1], a[2])；
発行管理者の秘密鍵isk=(p[1], p[2])
【００３５】
グループ署名の開封管理者が持つ鍵対（opk, osk）は、次の式に示すように、上記素数qを法とする有限体Zqの要素y[1]，y[2]と、上記有限群GGの要素Gと、H[1]=y[1]xsGと、H[2]=y[2]xsGと、に基づいて定められる。
なお、opkは開封管理者の公開鍵であり、oskは開封管理者の秘密鍵である。
【００３６】
開封管理者の公開鍵opk=(q, G, H[1], H[2])；
開封管理者の秘密鍵osk=(y[1], y[2])
【００３７】
グループ署名の失効管理者が持つ鍵対（rpk, rsk）は、次の式に示すように、ビット長がK[l]/2である安全な素数l[1]，l[2]と、これら素数の積l=l[1]l[2]と、この積lに対する巡回部分群QR(l)の要素b，wと、に基づいて定められる。
なお、rpkは失効管理者の公開鍵であり、rskは失効管理者の秘密鍵である。
【００３８】
失効管理者の公開鍵rpk=(l, b, w)；
失効管理者の秘密鍵rsk=(l[1], l[2])
【００３９】
グループ署名のi番目のユーザがもつ鍵対（mpk, msk）は、次の式に示すように、集合Λの要素x[i]と、h[i]=x[i]xsGと、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]と、に基づいて定められる。
なお、mpk[i]はi番目のユーザの公開鍵であり、msk[i]はi番目のユーザの秘密鍵である。
【００４０】
i番目のユーザの公開鍵mpk[i]=(h[i],A[i],e'[i],B[i])；
i番目のユーザの秘密鍵msk[i]=x[i] 
【００４１】
図8を参照して、i番目のユーザがメッセージmに対する署名を生成する場合について説明する。
この場合、メッセージm、開封管理者の公開鍵opk、ユーザの秘密鍵msk[i]、発行管理者の公開鍵ipkおよび失効管理者の公開鍵rpkを入力とし、次のようにして署名を生成する。
【００４２】
ステップST100において、乱数生成サブシステム101により乱数を生成する。
すなわち、ρ[E]、ρ[m]、ρ[r]、μ[x]、μ[s]、μ[e']、μ[t]、μ[E]を、次のようにランダムに選択する。
ρ[E]：上記有限体Zqの要素
ρ[m]：ビット長K[n]/2のビット列
ρ[r]：ビット長K[l]/2のビット列
μ[x]：ビット長λ+K[c]+K[S]のビット列
μ[s]：ビット長K[e]+K[n]/2+K[c]+K[S]のビット列
μ[e']：ビット長K[e']+K[c]+K[S]のビット列
μ[t]：ビット長K[e']+K[l]/2+K[c]+K[S]のビット列
μ[E]：上記有限体Zqの要素
【００４３】
ステップST110において、楕円曲線演算サブシステム107の楕円曲線演算ユニット110により複数の楕円曲線演算を実行し、開封管理者の公開鍵と乱数とを用いてE[0]、E[1]、E[2]、E、V[ComCipher]を次のように求める。
【００４４】
E[0]=ρ[E]xsG
E[1]=h[i]+eρ[E]xsH[1]
E[2]=h[i]+eρ[E]xsH[2]
E=(E[0],E[1],E[2])
V[ComCipher]=(μ[E]xsG，μ[x]xsG+eμ[E]xsH[1]，μ[x]xsG+eμ[E]xsH[2])
【００４５】
このとき、ディスパッチャ108の働きにより、6つの楕円曲線演算ユニット110の状況を監視し、空いている楕円曲線演算ユニット110に次々にデータを送り込んで、効率よく演算を進めていく。
なお、演算「Z=(W, X, Y)」は、演算W、演算X、演算Yを別々に行った後に取りまとめることを示す（タップルの計算）。
【００４６】
ステップST120において、剰余演算サブシステム112の剰余演算ユニット114により複数の剰余演算を実行し、発行管理者の公開鍵と失効管理者の公開鍵と乱数とを用いてA[COM]、B[COM]、V[ComMPK]、V[ComREV]を次のように求める。
【００４７】
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)
【００４８】
このとき、ディスパッチャ113の働きにより、9つの剰余演算ユニット114の状況を監視し、空いている剰余演算ユニット114に次々にデータを送り込んで、効率よく演算を進めていく。
また、剰余演算は前記の楕円曲線演算と並行して実行されるものである。
このとき、楕円曲線演算と剰余演算とのレイテンシがほぼ同程度になるように設計してあり、一つのリクエストに対する楕円曲線演算結果と剰余演算結果とがほぼ同時にパケット中継バッファメモリ117に出力されるようになっている。この点については後述する。
【００４９】
ステップST130において、ハッシュ演算ユニット120により、楕円曲線演算の演算結果と剰余演算の演算結果とメッセージmとを用いて、ハッシュcを次のように演算して求める。
【００５０】
c=Hash(K, ipk, opk, rpk, E, A[COM], B[COM], V[ComCipher], V[ComMPK], V[ComRev], m)
【００５１】
ステップST140において、整数演算ユニット121により整数演算を実行し、ハッシュ演算の演算結果と乱数とを用いてτ[x]、τ[s]、τ[t]、τ[e']、τ[E]を次のように演算して求める。
【００５２】
τ[x]=cx[i]+μ[x](mod q)
τ[s]=ce[i]ρ[m]+μ[s](mod q)
τ[t]=ce'[i]ρ[r]+μ[t](mod q)
τ[e']=ce'[i]+μ[e'](mod q)
τ[E]=cρ[E]+μ[E](mod q)
【００５３】
ステップST150において、署名(E, A[COM], B[COM], c, τ[x], τ[s], τ[t], τ[e'], τ[E])を出力する。このようにして署名生成が行われる。
【００５４】
本実施形態では、上記のような構成にしたので、空いている演算ユニットはすぐに他のリクエスト処理に割り当てられることとなり、演算ユニットの空き時間が非常に短く抑えられる。これが処理時間の増加を抑えられる理由である。
例えば背景技術で説明した図14のように署名処理装置全体をリクエスト数ぶんだけ並べた場合、一の署名処理装置は一つのリクエストの演算しかできないので、仮に隣の署名処理装置の演算ユニット（例えば楕円曲線演算ユニットや剰余演算ユニット）が空いていたとしても、空いている演算ユニットを前記リクエストの処理に使うことはできない。したがって、図14の構成では、全体の回路規模が大きい割に稼働率が低く、演算処理速度が遅いということになる。
この点、本実施形態の構成によれば、全体の回路規模を小さくでき、複数のリクエストを高速に演算処理することができる。
【００５５】
ここで、各サブシステムを構成する基本演算ユニットの数をどのように設定するかについて説明する。
各サブシステムの内部にある基本演算ユニットの個数は、同時処理するリクエスト数と同一でなくてもよい。
例えば、6つのリクエストを同時処理するからといって、各サブシステムが6つずつ基本演算ユニットを持っていればよいというものではない。
基本演算の種類が異なれば演算の実行速度も違ってくる。そこで、処理が遅い基本演算については個数を多くし、処理が速い基本演算については個数を減らすように設計すればよい。そして、各サブシステムのレイテンシがほぼ同程度に揃ったときに、最も少ない装置量で最も高い性能を実現することができる。
【００５６】
より具体的には、剰余演算は署名処理全体の速度を最も律速するものであり、他の演算よりも10倍以上遅い。
また、署名処理においては数回の剰余演算が使われており、それらの演算速度も、データのビット幅が異なるために10倍ほどの開きがある。
このため、剰余演算サブシステム112における剰余演算ユニット114は、他のサブシステムの基本演算器よりも多い数が必要である。
例えば、本実施形態では、サブシステム同士のレイテンシを揃えるように、乱数生成サブシステム101の擬似乱数生成ユニット103は一つ、楕円曲線演算サブシステムは6つ、剰余演算ユニット114は9つ、ハッシュ演算ユニット120および整数演算ユニット121は1つとしている。
【００５７】
なお、一のリクエストを処理する場合には遅い剰余演算と速い剰余演算とが必要になるが、一の剰余演算ユニット114で遅い剰余演算を実行している間に、より速い剰余演算を他の剰余演算ユニット114で複数回実行することが可能である。したがって、剰余演算ユニットの数は、署名処理で行われる剰余演算回数よりも少ない演算器数でよい。
【００５８】
また、あるリクエストの剰余演算に時間がかかっている場合であっても、他に空いている剰余演算ユニットがあれば、他のリクエストの剰余演算を開始することができる。
このようにして演算器の利用効率を100％近くに保つことにより、少数の演算器でも多くのリクエストを処理できる。
【００５９】
また、剰余演算以外の演算は相対的に速度が速いので、少ない演算器数であっても、剰余演算が終わるまでに必要な演算を全て完了できる。このため、楕円曲線演算ユニットを6個、他の基本演算ユニットを1個にまで減らしても、署名処理全体の性能はとくに落ちない。結果として、本実施形態によれば、単純に署名回路を複数並べる場合と比べ、半分の回路規模で同一の処理性能を達成することができる。
また、消費電力は回路規模におおむね比例するので、単純に署名回路を複数並べる場合と比べ、本実施形態の消費電力は半分程度に抑えることができる。
【００６０】
図9は、発明の効果を具体的に測定した結果を示すグラフである。
第1実施形態の構成において、楕円曲線演算ユニットを６個、擬似乱数生成ユニットを１個、ハッシュ演算ユニットを１個、整数演算ユニットを１個に固定し、もっとも速度を律速する剰余演算ユニットの個数を１個から９個まで変化させた。そして、同時処理が要求されるリクエストの数と全リクエストを処理し終えるまでにかかる時間との関係を測定してグラフに示した。
【００６１】
剰余演算ユニットの数が1つの場合、図13に示した単一のリクエストを処理する署名回路と処理速度はほぼ同一となる。この場合、リクエスト数が9倍になれば、処理時間も9倍かかる。この構成で処理時間を減らすには、署名回路全体をリクエスト数と同一の数だけ並べなければならない。
【００６２】
これに対し、剰余演算ユニットの数を増やしていくと、リクエスト数が９倍になっても処理時間は９倍ではなく約４倍で済み、図１４の処理時間と同程度に抑えられる。その結果、図１４の半分以下の回路規模で、同じ処理速度を達成することができる。
【００６３】
（第2実施形態）
上記第1実施形態では、専用の演算回路を用いて署名生成処理を実行する構成を例示した。すなわち、各基本演算を実行処理する専用回路を用いていた。
これに対し、ソフトウェアを実行する1または複数のCPU（Central Processing Unit）を用いて署名生成の各基本演算を実行させてもよいことはもちろんである。この場合、署名生成装置は、楕円曲線演算を実行する複数の楕円曲線演算プロセッサコアと、剰余演算を実行する複数の剰余演算プロセッサコアと、整数演算を実行する複数の整数演算プロセッサコアと、乱数生成を実行する乱数生成プロセッサコアと、ハッシュ演算を実行するハッシュ演算プロセッサコアと、パケットを中継する共有メモリと、ディスパッチ処理を実行する複数のプロセッサコアと、を少なくとも備えている。そして、剰余演算プロセッサコアを９つ設けるのに対し、楕円曲線演算プロセッサコアを６つ設けるなど、各基本演算を実行するプロセッサコアの数を適宜設計する。
【００６４】
ディスパッチを行うプロセッサコアは、共有メモリや基本演算を行うプロセッサコアの状況を監視し、演算をリクエストするパケットが共有メモリに格納されたとき、空いている基本演算担当のプロセッサに演算を開始させる。
これにより、専用回路を用いて署名回路を構成した場合と同様に処理を実行させることができる。
【００６５】
なお、複数のCPUを用いてマルチコアを構成する場合、総ての基本演算実行ユニットをCPUで構成せずに、一部の基本演算実行ユニットをCPUで構成するようにしてもよい。
また、CPUを各演算器として機能させる署名処理プログラムは、コンピュータ読み取り可能な記録媒体に記録されて提供されてもよい。
【００６６】
（第3実施形態）
上記第1実施形態および第2実施形態では署名生成装置の例を説明したが、本発明は署名認証装置にも同様に適用できる。
図10は、本発明にかかる署名認証装置200の構成を示す図である。
署名認証装置200は、乱数生成を除き、署名生成装置100と同様の構成を採用できるので、第1実施形態と同じ要素には同じ符号を付しその説明を省略する。
図11は、署名認証アルゴリズムを示すフローチャートである。
署名認証アルゴリズムは、乱数生成を除き、署名生成とほぼ同じデータフローである。
署名認証アルゴリズムでは、発行管理者の公開鍵ipk、失効管理者の公開鍵rpk、開封管理者の公開鍵opk、メッセージm、署名δを入力として、次のようにして署名を認証する。
【００６７】
ステップST200において、|τ[x]|≦λ＋K[e]＋K[S]と、|τ[s]|≦K[e']＋K[e]＋K[S]と、が成立するか調べ，両方成立でなければ認証失敗を返す。
【００６８】
ステップST210において、楕円曲線演算により、V'[ComCipher]=(τ[E]xsG-e[c]xsE[0]，τ[x]xsG+eτ[E]xsH[1]-e[c]xsE[1]，τ[x]xsG+eτ[E]xsH[2]-e[c]xsE[2])を計算する。
【００６９】
ステップST220において、剰余演算により、V'[ComMPK]=a[0]ca[1]τ[x]a[2]τ[s]A[COM]-(e2K[e]+τ[e'])(mod n)と、V'[ComREV]=beωτ[t]B[COM]-τ[e'](mod l)と、を計算する。
【００７０】
ステップST230において、ハッシュ演算により、ハッシュc'を、次のように演算して求める。
【００７１】
c'=Hash(K, ipk, opk, rpk, E, A[COM], B[COM], V'[ComCipher], V'[ComMPK], V'[ComRev], m)
【００７２】
ステップST240において、ハッシュc'=署名δなら認証成功、そうでなければ認証失敗を返す。
このようにして署名認証が行われる。
【００７３】
このような証明認証装置においても上記第1実施形態と同じ作用効果を奏する。
【００７４】
また、署名認証装置についても、ソフトウェアを実行する1または複数のCPU（Central Processing Unit）を用いて構成できることはもちろんである。
【００７５】
なお、本発明は上記実施の形態に限られるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更することができる。
基本演算を実行する回路ユニットまたはプロセッサコアの数などは上記例示に限定されないことはもちろんである。
例えば、乱数生成サブシステムの擬似乱数生成ユニットは一つではなく2以上であってもよい。
楕円曲線演算サブシステムの楕円曲線ユニットは、6つに限定されず、それ以上でもそれ以下でもよい。
剰余演算サブシステムの剰余演算ユニットは、9つに限定されず、それ以上でもそれ以下でもよい。
ハッシュ・整数演算ユニットのハッシュ演算ユニット、整数演算ユニットの数は、一つに限定されず、二つ以上でもよい。
【００７６】
さらに、本発明は、グループ署名を生成または認証するための署名処理装置に限定されず、セキュリティ関連の複合演算を実行する他の装置に対しても適用することができる。図12は、演算種類を特定せずに、本発明の趣旨を実現するための署名処理装置を概念的に図示したものである。
【００７７】
この出願は、2010年10月29日に出願された日本出願特願2010-243321を基礎とする優先権を主張し、その開示のすべてをここに取り込む。
【００７８】
上記実施形態の一部または全部は以下のようにも記載されうるが、以下には限定されない。
【００７９】
（付記１）
署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行部とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムを構成し、
演算リクエストを中継するバッファメモリを介して複数の前記サブシステムを接続した署名処理装置。
（付記２）
【００８０】
付記１に記載の署名処理装置において、
複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理し、
前記サブシステムはそれぞれ単一のリクエストに占有されることなく異なるリクエスト中の演算をそれぞれの基本演算部に割り付けて同時実行する、
ことを特徴とする署名処理装置。
【００８１】
（付記3）
付記1または付記2に記載の署名処理装置において、
前記サブシステムとして、剰余演算サブシステムと、楕円曲線演算サブシステムと、整数演算・ハッシュ演算サブシステム、とを有し、
前記剰余演算サブシステムは、剰余演算を実行する複数の剰余演算部とそれらの制御を行うディスパッチャとを含み、
楕円曲線演算サブシステムは、楕円曲線演算を実行する複数の楕円曲線演算部とそれらの制御を行うディスパッチャとを含み、
整数演算・ハッシュ演算サブシステムは、ハッシュ演算を実行する一または複数のハッシュ演算部と、整数演算を実行する一または複数の整数演算部と、それらの制御を行うディスパッチャとを含んで構成されている
ことを特徴とする署名処理装置。
【００８２】
（付記4）
付記3に記載の署名処理装置において、
前記サブシステムとして、さらに、乱数生成演算サブシステムを含み、
前記乱数生成演算サブシステムは、乱数生成演算を実行する一または複数の乱数生成部とそれらの制御を行うディスパッチャとを含んで構成されている
ことを特徴とする署名処理装置。
【００８３】
（付記5）
付記4に記載の署名処理装置において、
前記乱数生成演算サブシステムの前記乱数生成部は一つである
ことを特徴とする署名処理装置。
【００８４】
（付記6）
付記3から付記5のいずれかに記載の署名処理装置において、
楕円曲線演算サブシステムの前記楕円曲線演算部の個数は、前記楕円曲線演算サブシステムの前記剰余演算部の個数と同じかそれよりも少ない個数である
ことを特徴とする署名処理装置。
【００８５】
（付記7）
付記3から付記6のいずれかに記載の署名処理装置において、
前記整数演算・ハッシュ演算サブシステムの前記整数演算部が一つである
ことを特徴とする署名処理装置。
【００８６】
（付記8）
付記3から付記7のいずれかに記載の署名処理装置において、
前記整数演算・ハッシュ演算サブシステムの前記ハッシュ演算部が一つである
ことを特徴とする署名処理装置。
【００８７】
（付記9）
付記1から付記9のいずれかに記載の署名処理装置において、
前記基本演算実行部の一部または全部と前記ディスパッチャの一部または全部がプロセッサコアを用いて構成されている
ことを特徴とする署名処理装置。
【００８８】
（付記10）
付記1から付記9のいずれかに記載の署名処理装置において、
前記署名処理装置は、グループ署名の生成を行うグループ署名生成装置、または、グループ署名の認証を行うグループ署名認証装置である
ことを特徴とする署名処理装置。
【００８９】
（付記11）
署名処理手続きに含まれる基本演算を１つまたは複数の基本演算実行部で同時に複数実行し、
演算状態を監視して受け付け可能な基本演算実行部に順次演算実行を指示し、
単一のリクエストに占有されることなく異なるリクエスト中の演算をそれぞれの基本演算部に割り付けて同時実行するようにさせる
ことを特徴とする署名処理方法。
【００９０】
（付記12）
複数のプロセッサを有するコンピュータを、
署名処理手続きに含まれる基本演算の種類ごとに１つまたは複数の基本演算実行部とそれらの演算状態を監視して演算実行を指示するディスパッチャとが相互接続したサブシステムとして機能させ、
複数の署名生成リクエストもしくは署名認証リクエストを単一の入力で受け付け、複数のリクエストを同時並行で処理させることを特徴とする署名処理プログラム。
【００９１】
（付記13）
付記12の署名処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【符号の説明】
【００９２】
100…署名生成装置、101…乱数生成サブシステム、102…ディスパッチャ、103…擬似乱数生成ユニット、104…ローカルバス、105…パケット中継バッファメモリ、106…パケット中継バッファメモリ、107…楕円曲線演算サブシステム、108…ディスパッチャ、109…一時データバッファメモリ、110…楕円曲線演算ユニット、111…ローカルバス、112…剰余演算サブシステム、113…ディスパッチャ、114…剰余演算ユニット、115…一時データバッファメモリ、116…ローカルバス、117…パケット中継バッファメモリ、118…ハッシュ・整数演算サブシステム、119…ディスパッチャ、120…ハッシュ演算ユニット、121…整数演算ユニット、122…一時データバッファメモリ、123…ローカルバス、130…投入口、131…出力口、301…楕円曲線演算ユニット、302…剰余演算ユニット、303…擬似乱数生成ユニット、305…整数演算ユニット、306…ハッシュ演算ユニット、401…パケット、402…リクエスト番号、403…現演算番号、404…前演算番号、405…演算引数、406…転送先指定。
【図１】
2012056608.tif 000003
【図２】
2012056608.tif 000004
【図３】
2012056608.tif 000005
【図４】
2012056608.tif 000006
【図５】
2012056608.tif 000007
【図６】
2012056608.tif 000008
【図７】
2012056608.tif 000009
【図８】
2012056608.tif 000010
【図９】
2012056608.tif 000011
【図１０】
2012056608.tif 000012
【図１１】
2012056608.tif 000013
【図１２】
2012056608.tif 000014
【図１３】
2012056608.tif 000015
【図１４】
2012056608.tif 000016
【国際調査報告】
2012056608.tif 000017
2012056608.tif 000018
2012056608.tif 000019
2012056608.tif 000020