(57)【要約】【課題】従来よりも効率の良い署名技術を提供する。【解決手段】pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵とする。使い捨て鍵生成装置２が、mｆを所定の値として、乱数r0を生成し、z0=h0(mf,r0)を計算することにより、使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を生成する。署名装置３が、Mを署名の対象となるメッセージとして、署名鍵sk=(h0-1)及び使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する。検証装置４が、検証鍵pk=(h0,h1)、使い捨て検証鍵opk=(z0)、メッセージM及び署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する。【選択図】図１
2016001263.tif 000002
【特許請求の範囲】
【請求項１】
(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵として、
mｆを所定の値として、乱数r0を生成し、z0=h0(mf,r0)を計算することにより、使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を生成する使い捨て鍵生成装置と、
Mを署名の対象となるメッセージとして、上記署名鍵sk=(h0-1)及び上記使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する署名装置と、
上記検証鍵pk=(h0,h1)、上記使い捨て検証鍵opk=(z0)、上記メッセージM及び上記署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する検証装置と、
を含む部分使い捨て署名システム。
【請求項２】
請求項１の部分使い捨て署名システムにおいて、
TCHをh1の値域からh0,h0-1の定義域への写像として、
上記署名装置は、乱数r1’を生成し、r0’=h0-1(mf,r0,TCH(h1(M,r1’)))を計算することにより、署名σ=(r0’,r1’)を生成し、
上記検証装置は、z0がh0(THC(h1(M,r1’)),r0’)と一致するかを検証する、
部分使い捨て署名システム。
【請求項３】
(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵とし、
mｆを所定の値とし、r0を乱数とし、z0=h0(mf,r0)とし、使い捨て検証鍵opk=(z0)とし、使い捨て署名鍵osk=(r0)として、
Mを署名の対象となるメッセージとして、上記署名鍵sk=(h0-1)及び上記使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する署名装置。
【請求項４】
(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵とし、
mｆを所定の値とし、r0を乱数とし、z0=h0(mf,r0)とし、使い捨て検証鍵opk=(z0)とし、使い捨て署名鍵osk=(r0)とし、
Mを署名の対象となるメッセージとし、r1’を乱数とし、r0’=h0-1(mf,r0,h1(M,r1’))とし、署名σ=(r0’,r1’)として、
上記検証鍵pk=(h0,h1)、上記使い捨て検証鍵opk=(z0)、上記メッセージM及び上記署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する検証装置。
【請求項５】
(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵として、
使い捨て鍵生成装置が、mｆを所定の値として、乱数r0を生成し、z0=h0(mf,r0)を計算することにより、使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を生成する使い捨て鍵生成ステップと、
署名装置が、Mを署名の対象となるメッセージとして、上記署名鍵sk=(h0-1)及び上記使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する署名ステップと、
検証装置が、上記検証鍵pk=(h0,h1)、上記使い捨て検証鍵opk=(z0)、上記メッセージM及び上記署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する検証ステップと、
を含む部分使い捨て署名方法。
【請求項６】
請求項３の署名装置又は請求項４の検証装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ディジタル署名に関するものである。
【背景技術】
【０００２】
使い捨て署名方式(One-Time Signature scheme:OTS)とは、ディジタル署名方式の一種であり、署名鍵が、使い捨て、すなわち一度の署名生成にしか使えない方式を指す。カメレオンハッシュ関数を使ったOTSの構成例が非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Payman Mohassel, “One-Time Signatures and Chameleon Hash Functions”, Selected Areas in Cryptography, 2010, p.302-319
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載の署名方式はOTSであり、全ての鍵を署名の度に毎回更新しなければならず、効率が悪いという問題があった。
【０００５】
この発明の目的は、非特許文献１に記載の方式よりも効率が良い部分使い捨て署名システム及び方法、署名装置、検証装置並びにプログラムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様による部分使い捨て署名システムは、(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵として、mｆを所定の値として、乱数r0を生成し、z0=h0(mf,r0)を計算することにより、使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を生成する使い捨て鍵生成装置と、Mを署名の対象となるメッセージとして、署名鍵sk=(h0-1)及び使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する署名装置と、検証鍵pk=(h0,h1)、使い捨て検証鍵opk=(z0)、メッセージM及び署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する検証装置と、を備えている。
【０００７】
この発明の一態様による署名装置は、(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵とし、mｆを所定の値とし、r0を乱数とし、z0=h0(mf,r0)とし、使い捨て検証鍵opk=(z0)とし、使い捨て署名鍵osk=(r0)として、Mを署名の対象となるメッセージとして、署名鍵sk=(h0-1)及び使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する。
【０００８】
この発明の一態様による検証装置は、(h0,h0-1)をカメレオンハッシュ関数の第１の組とし、(h1,h1-1)をカメレオンハッシュ関数の第２の組とし、pk=(h0,h1)を複数回の署名及び検証に使い回すことができる固定の検証鍵とし、sk=(h0-1)を複数回の署名及び検証に使い回すことができる固定の署名鍵とし、mｆを所定の値とし、r0を乱数とし、z0=h0(mf,r0)とし、使い捨て検証鍵opk=(z0)とし、使い捨て署名鍵osk=(r0)とし、Mを署名の対象となるメッセージとし、r1’を乱数とし、r0’=h0-1(mf,r0,h1(M,r1’))とし、署名σ=(r0’,r1’)として、検証鍵pk=(h0,h1)、使い捨て検証鍵opk=(z0)、メッセージM及び署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する。
【発明の効果】
【０００９】
署名鍵及び検証鍵の一部を使い回すことにより、非特許文献１に記載の方式よりも効率を良くすることができる。
【図面の簡単な説明】
【００１０】
【図１】部分使い捨て署名システムの例を説明するためのブロック図。
【図２】部分使い捨て署名方法の例を説明するための流れ図。
【発明を実施するための形態】
【００１１】
以下、図面を参照しながらこの発明の実施形態について説明する。
【００１２】
図１に示すように、部分使い捨て署名システムは、鍵生成装置１、使い捨て鍵生成装置２、署名装置３、検証装置４、送信装置５及び受信装置６を例えば備えている。部分使い捨て署名方法は、部分使い捨て署名システムが、図２のステップＳ１からステップＳ４の処理を行うことにより実現される。
【００１３】
この発明は、カメレオンハッシュ関数CMHを用いることによりいわゆる部分使い捨て署名を構成する。
【００１４】
ここで、部分使い捨て署名方式(Partial One-time Signatures: POS)とは、署名鍵及び検証鍵のそれぞれが繰り返し使用できる長期鍵と使い捨ての鍵とで構成されており、署名のたびごとに使い捨て鍵部分が新たに構成される署名方式のことを意味する。
【００１５】
カメレオンハッシュ関数CMHは、(h,h-1)の関数のペアからなる。関数h,h-1は以下の性質を有する。
【００１６】
関数hは、入力にメッセージMと乱数rを取り、ハッシュ値を出力する関数で、衝突困難ハッシュ関数の性質をもつ。すなわち、h(M,r)=h(M’,r’)となる対(M,r),(M’,r’)を見つけることは困難である。一方で、h-1は、(M,r,M’)を入力とし、h(M,r)=h(M’,r’)を満たすr’を出力する関数である。すなわち、関数h-1を知る者は、ある(M,r)に対するハッシュ値を別の(M’,r’)に対するハッシュ値としてこれを開示することが可能になる。
【００１７】
この発明で用いられるカメレオンハッシュ関数CMHを構成する関数h,h-1は、上記の性質を満たすものであれば、どのようなものであってもよい。
【００１８】
以下では、カメレオンハッシュ関数CMHを構成する関数h,h-1の一例を示す。
【００１９】
Gを素数位数qの乗法群とする。gを群Gの生成元とする。例えばG⊂Zpとする。ここで、pは素数であり、q|p-1であるとする。すなわち、qはp-1で割り切れるとする。また、sを1からq-1の正の整数とし、f=gsとする。G⊂Zpである場合には、f=gs (mod p)とする。
【００２０】
このとき、M,r∈Zqとして、関数h(M,r)=gMfrである。G⊂Zpである場合には、関数h(M,r)=gMfr(mod p)とする。
【００２１】
また、このとき、関数h-1(M,r,M’)を、M+s・r=M’+s・r’ (mod q)となるr’を出力する関数とする。すなわち、関数h-1(M,r,M’)=(M-M’)/s+r (mod q)とする。
【００２２】
＜鍵生成装置１＞
鍵生成装置１は、カメレオンハッシュ関数の第１のペア(h0,h0-1)及びカメレオンハッシュ関数の第２のペア(h1,h1-1)を生成することにより、複数回の署名及び検証に使い回すことができる固定の検証鍵pk=(h0,h1)及び複数回の署名及び検証に使い回すことができる固定の署名鍵sk=(h0-1)を生成する（ステップＳ１）。生成された検証鍵pk=(h0,h1)は、全体に公開される。生成された署名鍵sk=(h0-1)は、署名装置３に送信される。
【００２３】
鍵生成装置１の処理は、署名生成の前に一回のみ行われ、署名を生成する度ごとには行われない。一度生成された検証鍵pk=(h0,h1)及び署名鍵sk=(h0-1)は複数回の署名及び検証に使い回すことができる。
【００２４】
＜使い捨て鍵生成装置２＞
使い捨て鍵生成装置２は、mｆを所定の値として、乱数r0を生成し、z0=h0(mf,r0)を計算することにより、使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を生成する（ステップＳ２）。生成された使い捨て検証鍵opk=(z0)は、全体に公開される。生成された使い捨て署名鍵osk=(r0)は、署名装置３に送信される。
【００２５】
mｆは、所定の固定値であってもよいし、乱数r0と同様に、使い捨て署名鍵osk=(r0)の生成の度ごとに異なる値を取ってもよい。この場合、mｆは例えば乱数とする。また、mｆは、検証鍵pk=(h0,h1)の一部であってもよいし、固定値のシステムパラメータであってもよい。
【００２６】
使い捨て鍵生成装置２の処理は、署名を生成する度ごとに行われる。使い捨て検証鍵opk=(z0)及び使い捨て署名鍵osk=(r0)を使い回した場合には、安全性が低下する可能性がある。
【００２７】
＜署名装置３＞
署名装置３は、Mを署名の対象となるメッセージとして、署名鍵sk=(h0-1)及び使い捨て署名鍵osk=(r0)を用いて、乱数r1’を生成し、r0’=h0-1(mf,r0,h1(M,r1’))を計算することにより、署名σ=(r0’,r1’)を生成する（ステップＳ３）。
【００２８】
署名装置３の処理は、例えば送信装置５がメッセージMに対する署名を署名装置３に依頼することを契機に行われる。この場合、送信装置５は署名の対象となるメッセージMを署名装置３に送信し、署名装置３は受信したメッセージMに対して署名σを生成し、生成された署名σは送信装置５に送信される。
【００２９】
その後、送信装置５は、メッセージM及び生成された署名σを受信装置６に送信してもよい。
【００３０】
＜検証装置４＞
検証装置４は、検証鍵pk=(h0,h1)、使い捨て検証鍵opk=(z0)、メッセージM及び署名σ=(r0’,r1’)を用いて、z0がh0(h1(M,r1’),r0’)と一致するかを検証する（ステップＳ４）。
【００３１】
一致する場合には署名は正当なものであり、一致しない場合には署名σは正当でないと判断することができる。この判断結果が出力されてもよい。例えば、一致する場合には１が出力され、一致しない場合には０が出力される。
【００３２】
なお、h1(M,r1’)の計算結果が関数h0,h0-1の定義域の範囲外となる場合には、h0(h1(M,r1’),r0’)を計算することができない。また、この場合、署名装置３はh0-1(mf,r0,h1(M,r1’))を計算することはできない。このため、TCHをh1の値域からh0,h0-1の定義域への写像として、検証装置４が、z0がh0(h1(M,r1’),r0’)と一致するかではなく、z0がh0(THC(h1(M,r1’)),r0’)と一致するかを検証してもよい。この場合、署名装置３はr0’=h0-1(mf,r0,h1(M,r1’))ではなく、r0’=h0-1(mf,r0,TCH(h1(M,r1’)))を計算する。このように、TCHを用いて、h1(M,r1’)の計算結果が必ず関数h0,h0-1の定義域の範囲内になるようにすることにより、必ず関数h0,h0-1の値を計算することが可能となる。
【００３３】
TCHは、h1の値域からh0,h0-1の定義域への写像である関数であるとともに、ターゲット衝突困難ハッシュ関数であってもよい。すなわち、与えられたターゲットメッセージMに対してTCH(M)と同じ出力値を持つ異なる入力を推定することが困難な関数であってもよい。
【００３４】
検証装置４の処理は、例えば署名装置３が生成した署名σが正当なものであるか送信装置５が確かめるために行われる。この場合、送信装置５は、メッセージM及び生成された署名σを検証装置４に送信する。検証装置４は、受信したメッセージM及び生成された署名σを用いて上記の検証を行う。
【００３５】
検証装置４の処理は、送信装置５からメッセージM及び生成された署名σを受信した受信装置６が、署名σが正当なものであるか確かめるために行われてもよい。この場合、受信装置６は、メッセージM及び生成された署名σを検証装置４に送信する。検証装置４は、受信したメッセージM及び生成された署名σを用いて上記の検証を行う。
【００３６】
このように、署名鍵及び検証鍵の一部である署名鍵sk=(h0-1)及び検証鍵pk=(h0,h1)を使い回すことにより、非特許文献１に記載の方式よりも効率を良くすることができる。
【００３７】
[変形例等]
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３８】
また、各装置における各処理をコンピュータによって実現する場合、その各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００３９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４０】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００４１】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００４２】
１      鍵生成装置
２      使い捨て鍵生成装置
３      署名装置
４      検証装置
５      送信装置
６      受信装置
【図１】
2016001263.tif 000003
【図２】
2016001263.tif 000004