(57)【特許請求の範囲】
【請求項１】
所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、
上記部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを上記公開鍵epkを用いて暗号化することにより暗号文Enc(epk,psk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成するタグ鍵生成部とを含むタグ鍵生成装置と、
上記タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を上記秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを用いて上記部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する署名生成部とを含む署名装置と、
上記部分使い捨て署名方式の検証アルゴリズムに基づいて上記署名σの正当性を検証する検証部を含む検証装置と、
を含むタグ付き使い捨て署名システム。
【請求項２】
所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、
上記部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを上記公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成するタグ鍵生成部とを含むタグ鍵生成装置。
【請求項３】
所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、
上記部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて生成された使い捨て検証鍵及び使い捨て秘密鍵をそれぞれopk及びoskとして、生成された使い捨て秘密鍵oskを上記公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成されたタグをtag=(opk,Enc(epk,osk))として、
上記タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を上記秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを用いて上記部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する署名生成部とを含む署名装置。
【請求項４】
所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、
タグ鍵生成装置の使い捨て鍵生成部が、上記部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成する使い捨て鍵生成部ステップと、
上記タグ鍵生成装置のタグ鍵生成部が、生成された使い捨て秘密鍵oskを上記公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成するタグ鍵生成ステップと、
署名装置の使い捨て鍵生成部が、上記タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を上記秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生成する使い捨て鍵生成ステップと、
上記署名装置の署名生成部が、生成された使い捨て秘密鍵oskを用いて上記部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する署名ステップと、
検証装置の検証部が、上記部分使い捨て署名方式の検証アルゴリズムに基づいて上記署名σの正当性を検証する検証ステップと、
を含むタグ付き使い捨て署名方法。
【請求項５】
請求項２のタグ鍵生成装置又は請求項３の署名装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ディジタル署名に関するものである。
【背景技術】
【０００２】
タグ付き使い捨て署名方式(Taged One-time Signatures: TOS)とは、毎回の署名生成についてメッセージに対して固有のタグが準備され、そのメッセージ・タグに対する署名方式である。タグ付き使い捨て署名方式では、タグは毎回新しいものが使われる。
【０００３】
タグ付き使い捨て署名方式として、例えば非特許文献１に記載された方式が知られている（例えば、非特許文献１参照）。
【０００４】
このタグ付き使い捨て署名方式は、一から設計したものである。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions”, ASI-ACRYPT 2012
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１のタグ付き使い捨て署名方式は一から設計したものであり、既存の部分使い捨て署名方式をベースとするタグ付き使い捨て署名方式ではない。
【０００７】
ここで、部分使い捨て署名方式(Partial One-time Signatures: POS)とは、署名鍵及び検証鍵のそれぞれが繰り返し使用できる長期鍵と使い捨ての鍵とで構成されており、署名のたびごとに使い捨て鍵部分が新たに構成される署名方式のことを意味する。
【０００８】
この発明の目的は、既存の部分使い捨て署名方式をベースとするタグ付き使い捨て署名システム及び方法、タグ鍵生成装置、署名装置並びにプログラムを提供することである。
【課題を解決するための手段】
【０００９】
この発明の一態様によるタグ付き使い捨て署名システムは、所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成するタグ鍵生成部とを含むタグ鍵生成装置と、タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを用いて部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する署名生成部とを含む署名装置と、部分使い捨て署名方式の検証アルゴリズムに基づいて署名σの正当性を検証する検証部を含む検証装置と、を備えている。
【００１０】
この発明の一態様によるタグ鍵生成装置は、所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成するタグ鍵生成部とを含む。
【００１１】
この発明の一態様による署名装置は、所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて生成された検証鍵及び署名鍵をそれぞれppk及びpskとし、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて生成された公開鍵及び秘密鍵をそれぞれepk及びeskとして、部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて生成された使い捨て検証鍵及び使い捨て秘密鍵をそれぞれopk及びoskとして、生成された使い捨て秘密鍵oskを公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成されたタグをtag=(opk,Enc(epk,osk))として、タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生成する使い捨て鍵生成部と、生成された使い捨て秘密鍵oskを用いて部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する署名生成部とを含む。
【発明の効果】
【００１２】
公開鍵暗号方式で使い捨て署名鍵を暗号化及び／又は復号することにより、既存の部分使い捨て署名方式をベースにして、短時間で安全なタグ付き使い捨て署名方式を構成することができる。
【図面の簡単な説明】
【００１３】
【図１】タグ付き使い捨て署名システムの例を説明するためのブロック図。
【図２】タグ付き使い捨て署名方法の例を説明するための流れ図。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながらこの発明の実施形態について説明する。
【００１５】
図１に示すように、タグ付き使い捨て署名システムは、鍵生成装置１、タグ鍵生成装置２、署名装置３、検証装置４、送信装置５及び受信装置６を例えば備えている。タグ付き使い捨て署名方法は、タグ付き使い捨て署名システムが、図２のステップＳ１からステップＳ４の処理を行うことにより実現される。
【００１６】
＜鍵生成装置１＞
鍵生成装置１は、所定の部分使い捨て署名方式の鍵生成アルゴリズムに基づいて検証鍵ppk及び署名鍵pskを生成し、所定の公開鍵暗号方式の鍵生成アルゴリズムに基づいて公開鍵epk及び秘密鍵eskを生成する（ステップＳ１）。
【００１７】
生成された検証鍵ppk及び公開鍵epkは、タグ付き使い捨て署名方式の検証鍵pk=(ppk,epk)として全体に公開される。生成された署名鍵psk及び秘密鍵eskは、タグ付き使い捨て署名方式の署名鍵sk=(psk,esk)として、署名装置３に送信される。
【００１８】
所定の部分使い捨て署名方式として、既存の部分使い捨て署名方式を用いることができる。部分使い捨て署名方式の例については後述する。同様に、所定の公開鍵暗号方式として、既存の公開鍵暗号方式を用いることができる。
【００１９】
鍵生成装置１の処理は、署名生成の前に一回のみ行われ、署名を生成する度ごとには行われない。一度生成されたタグ付き使い捨て署名方式の検証鍵pk=(ppk,epk)及びタグ付き使い捨て署名方式の署名鍵sk=(psk,esk)は複数回の署名及び検証に使い回すことができる。
【００２０】
＜タグ鍵生成装置２＞
タグ鍵生成装置２は、上記部分使い捨て署名方式の使い捨て鍵生成アルゴリズムに基づいて使い捨て検証鍵opk及び使い捨て秘密鍵oskを生成し、生成された使い捨て秘密鍵oskを公開鍵epkを用いて暗号化することにより暗号文Enc(epk,osk)を生成することにより、タグtag=(opk,Enc(epk,osk))を生成する（ステップＳ２）。
【００２１】
生成されたタグtag=(opk,Enc(epk,osk))は、署名装置３に送信される。生成されたタグtag=(opk,Enc(epk,osk))は、公開され、必要に応じて送信装置５及び検証装置６に送信されてもよい。
【００２２】
生成された使い捨て秘密鍵oskの公開鍵epkによる暗号化は、上記公開鍵暗号方式の暗号化アルゴリズムに基づいて行われる。
【００２３】
タグ鍵生成装置２の処理は、署名を生成する度ごとに行われる。使い捨て検証鍵opk及び使い捨て秘密鍵oskを使い回した場合には、安全性が低下する可能性がある。
【００２４】
＜署名装置３＞
署名装置３は、タグtag=(opk,Enc(epk,osk))に含まれる暗号文Enc(epk,osk)を秘密鍵eskを用いて復号することにより使い捨て秘密鍵oskを生し、生成された使い捨て秘密鍵oskを用いて上記部分使い捨て署名方式の署名アルゴリズムに基づいてメッセージMに対する署名σを生成する（ステップＳ３）。
【００２５】
生成された使い捨て秘密鍵oskによる暗号文Enc(epk,osk)の復号は、上記公開鍵暗号方式の復号アルゴリズムに基づいて行われる。
【００２６】
署名装置３の処理は、例えば送信装置５がメッセージMに対する署名を署名装置３に依頼することを契機に行われる。この場合、送信装置５は署名の対象となるメッセージMを署名装置３に送信し、署名装置３は受信したメッセージMに対して署名σを生成し、生成された署名σは送信装置５に送信される。
【００２７】
その後、送信装置５は、メッセージM及び生成された署名σを受信装置６に送信してもよい。
【００２８】
＜検証装置４＞
検証装置４は、上記部分使い捨て署名方式の検証アルゴリズムに基づいて署名σの正当性を検証する（ステップＳ４）。
【００２９】
例えば、検証装置４は、タグ付き使い捨て署名方式の検証鍵pk=(ppk,epk)、タグtag=(opk,Enc(epk,osk))、メッセージM及び署名σを用いて、上記部分使い捨て署名方式の検証アルゴリズムに基づく等式の左辺の値と右辺の値とが一致するかどうかを判定することにより正当性の検証を行う。一致する場合には署名は正当なものであり、一致しない場合には署名σは正当でないと判断することができる。この判断結果が出力されてもよい。例えば、一致する場合には１が出力され、一致しない場合には０が出力される。
【００３０】
検証装置４の処理は、例えば署名装置３が生成した署名σが正当なものであるか送信装置５が確かめるために行われる。この場合、送信装置５は、メッセージM及び生成された署名σを検証装置４に送信する。検証装置４は、タグ付き使い捨て署名方式の検証鍵pk=(ppk,epk)、タグtag=(opk,Enc(epk,osk))、受信したメッセージM及び生成された署名σを用いて上記の検証を行う。
【００３１】
検証装置４の処理は、送信装置５からメッセージM及び生成された署名σを受信した受信装置６が、署名σが正当なものであるか確かめるために行われてもよい。この場合、受信装置６は、メッセージM及び生成された署名σを検証装置４に送信する。検証装置４は、タグ付き使い捨て署名方式の検証鍵pk=(ppk,epk)、タグtag=(opk,Enc(epk,osk))、受信したメッセージM及び生成された署名σを用いて上記の検証を行う。
【００３２】
検証装置３のタグtag=(opk,Enc(epk,osk))の入手経路は署名方式の構成に依存する。検証装置３は、公開されたタグtag=(opk,Enc(epk,osk))を入手してもよいし、メッセージMと共に署名装置３又は送信装置５からタグtag=(opk,Enc(epk,osk))を入手してもよい。
【００３３】
［部分使い捨て署名方式の例］
以下では、部分使い捨て署名方式の例を示す。
【００３４】
Gを素数位数qの乗法群とする。gを群Gの生成元とする。メッセージをMとする。ハッシュ関数Hash:{0,1}*→Zqとする。例えば、ハッシュ関数Hashは、入力された２個の値のビット結合をZqに写す関数である。
【００３５】
（鍵生成アルゴリズム）
乱数x∈Zqを生成し、y=gxを計算する。検証鍵ppk=yとし、署名鍵psk=xとする。
【００３６】
（使い捨て鍵生成アルゴリズム）
乱数a∈Zqを生成し、A=gaを計算する。使い捨て検証鍵opk=Aとし、使い捨て署名鍵osk=aとする。
【００３７】
（署名アルゴリズム）
c=Hash(A,M)を計算する。z=a+cx (mod q)を計算する。署名σ=zとする。
【００３８】
（検証アルゴリズム）
等式gz=A・yHash(A,M)の左辺の値と右辺の値とが一致するかを判定する。一致すれば署名σは正当なものであり、一致しない場合には署名σは正当なものではないと判断することができる。
【００３９】
[変形例等]
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４０】
また、各装置における各処理をコンピュータによって実現する場合、その各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００４１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４２】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００４３】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００４４】
１      鍵生成装置
２      タグ鍵生成装置
３      署名装置
４      検証装置
５      送信装置
６      受信装置
【図１】
0006267591.tif 000002
【図２】
0006267591.tif 000003