(57)【要約】【課題】  ハッシュ関数ｈを複数とし、衝突するまでハッシュ連鎖が一定長ｄ0 のハッシュ連鎖の束であり、電子マネーなどとして利用した場合に、偽造、変造が起り難いものを生成可能にする。【解決手段】  関数ｈを区別するパラメータｔを１とし（Ｓ２）、ハッシュ関数パラメータｄを１とし（Ｓ３）、ハッシュ値ｘtd＝ｈt(ｘtd-1)を求め（Ｓ４）、ｘtd∈ＤＰ（ｎビット列中の上位ｎ−ｕビットが０）もｎビット列と一致したかを調べ（Ｓ５）、偽でｄ≧ｄmax かを調べ（Ｓ６）、偽でｄを＋１してＳ４に戻り（Ｓ７）、Ｓ５で真であればｄ＜ｄ0 かを調べ（Ｓ８）、真でｔ＜ｔmax かを調べ（Ｓ９）、真でｔを＋１してＳ３へ戻り（Ｓ１０）、Ｓ８で偽であればｘtdをアドレスの記憶領域に（ｔ，ｘtd-d0）を格納し（Ｓ１１）、Ｓ６で真であればＳ９へ移る。記憶部の各記憶領域にはｄ0 回のハッシュにより同一ｘtdとなる組が格納されることになる。【選択図】  図４
2005134454.tif 000002
【特許請求の範囲】
【請求項１】
Ｙ：＝｛０，１｝n 
［ｙ］v ：＝｛ｙの上位ｖビット｝（０＜ｖ＜ｎ，ｙ∈Ｙ）
ＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ＝（０，…，０）｝（０＜ｕ＜ｎ）
ＩＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ≠（０，…，０）｝
Ｍ（ｙ）：ｙと対応する記憶領域（ｙ∈ＤＰ）
Ｔ：＝｛１，２，…，ｔmax ｝
ｈt ：互いに独立なハッシュ関数：Ｙ→Ｙ（ｔ∈Ｔ）
Ｄ：＝｛１，２，…，ｄmax ｝
ｘt0：＝｛０，…，０｝∈Ｙ（ｔ∈Ｔ）
ｘtd：＝ｈt(ｘtd-1)∈Ｙ（ｔ∈Ｔ，ｄ∈Ｄ）
Ａk0d0：＝１＋ｋ0(ｄ0 −１）
（ｄ0 ∈Ｄ，ｋ0 ∈｛２，３，…，ｔmax ｝）
ε：＝２-(n-u)
ここでｈt が「互いに独立」とは、それらの計算が独立な事象とみなせることとし、
ハッシュ連鎖生成部、制御・判定部、記憶部を備え、
各ハッシュ関数ｈt について、初期値ｘt0よりハッシュ関数計算ｘtd＝ｈt(ｘtd-1）を逐次行ってｘt１，ｘt2，…のハッシュ連鎖を、最長ｄ＝ｄmax まで上記ハッシュ連鎖生成部により生成し、
上記制御・判定部により上記ハッシュ連鎖中の上記特性点ＤＰの要素と一致し、かつハッシュ連鎖長が上記ｄ0 のハッシュ連鎖を選択し、上記記憶部の特性点ＤＰの要素と一致したときのハッシュ値ｘtdの記憶領域に分類格納することを特徴とするハッシュ連鎖つきコリジョン生成方法。
【請求項２】
上記制御・判定部により、上記記憶部の各記憶領域中に格納されているハッシュ連鎖の数が上記ｋ0 個以上のものを選択してハッシュ束として出力することを特徴とする請求項１記載のハッシュ連鎖つきコリジョン生成方法。
【請求項３】
ハッシュ連鎖の長さｄ0 、ハッシュ束生成時の個別のハッシュ関数でハッシュ連鎖を求めるときの上限の長さｄmax 、ハッシュ連鎖を求めるときの連鎖の数の上限ｔmax を設定し、
上記ハッシュ連鎖生成過程及び上記分類格納過程は、
ハッシュ関数識別パラメータｔを１に初期化する第１過程と、
連鎖長パラメータｄを１に初期化してハッシュ値ｘtd-1に対しハッシュ関数演算ｈt(ｘtd-1）を施してハッシュ値ｘtdを生成する第２過程と、
上記ハッシュ値ｘtdが上記特性点ＤＰの要素と一致するかを判定し、一致していれば第６過程に移る第３過程と、
上記第３過程の判定が一致していないのであれば上記連鎖長パラメータｄが上記上限値ｄmax 以上かを判定し、以上であれば第８過程に移る第４過程と、
上記第４過程の判定が以上でなければ上記連鎖長パラメータｄを＋１して、ハッシュ値ｘtd-1に対し、ハッシュ関数演算ｈt(ｘtd-1）を施してハッシュ値ｘtdを生成して上記第３過程へ戻る第５過程と、
上記第６過程の判定がｄ0 より小さくないのであれば、そのときのハッシュ値ｘtdと対応したハッシュ値ｘtd-d0とｔとの組を上記ハッシュ値ｘtdの記憶領域に格納する第７過程とを有し、
上記第６過程は上記連鎖長パラメータｄが上記設定ハッシュ連鎖長ｄ0 より小さければ、上記第８過程に移り、
上記第８過程は関数識別パラメータｔが上記上限ｔmax より小さいかを判定し、その判定が小さいのであればパラメータｔを＋1して、上記第２過程に戻り、小さいのでなければ処理を終了することを特徴とする請求項１又は２記載のハッシュ連鎖つきコリジョン生成方法。
【請求項４】
Ｙ：＝｛０，１｝n 
［ｙ］v ：＝｛ｙの上位ｖビット｝（０＜ｖ＜ｎ，ｙ∈Ｙ）
ＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ＝（０，…，０）｝（０＜ｕ＜ｎ）
ＩＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ≠（０，…，０）｝
Ｍ（ｙ）：ｙと対応する記憶領域（ｙ∈ＤＰ）
Ｔ：＝｛１，２，…，ｔmax ｝
ｈt ：互いに独立なハッシュ関数：Ｙ→Ｙ（ｔ∈Ｔ）
Ｄ：＝｛１，２，…，ｄmax ｝
ｘt0：＝｛０，…，０｝∈Ｙ（ｔ∈Ｔ）
ｘtd：＝ｈt(ｘtd-1)∈Ｙ（ｔ∈Ｔ，ｄ∈Ｄ）
Ａk0d0：＝１＋ｋ0(ｄ0 −１）
（ｄ0 ∈Ｄ，ｋ0 ∈｛２，３，…，ｔmax ｝）
ε：＝２-(n-u)
ここでｈt が「互いに独立」とは、それらの計算が独立な事象とみなせることとし、
ハッシュ連鎖長の上限ｄmax 、ハッシュ連鎖数の上限ｔmax が入力され、ｄを連鎖長パラメータ、ｔを関数識別パラメータとして、各ハッシュ関数ｈt について、初期値ｘt0よりハッシュ関数計算ｘtd＝ｈt(ｘtd-1）を逐次行ってｘt1，ｘt2，…のハッシュ連鎖を、ｄ＝ｄmax まで生成するハッシュ連鎖生成部と、
ハッシュ連鎖の長さｄ0 、上記連鎖長の上限ｄmax 、上記生成されたハッシュ連鎖ｘtdが入力され、これらハッシュ連鎖ｘtd中の、上記特性点ＤＰの要素と一致し、かつハッシュ連鎖長が上記ｄ0 のハッシュ連鎖を選択し、記憶部のその特性点ＤＰの要素と一致したときのハッシュ値ｘtdと対応した記憶領域に、そのハッシュ連鎖の初期値と関数識別パラメータｔを組にして格納する制御・判定部と、
上記一致した特性点ＤＰの要素ごとに、異なる領域にハッシュ連鎖の初期値と関数識別パラメータｔの組が記憶される上記記憶部と
を備えるハッシュ連鎖つきコリジョン生成装置。
【請求項５】
Ｙ：＝｛０，１｝n 
［ｙ］v ：＝｛ｙの上位ｖビット｝（０＜ｖ＜ｎ，ｙ∈Ｙ）
ＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ＝（０，…，０）｝（０＜ｕ＜ｎ）
ＩＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ≠（０，…，０）｝
Ｍ（ｙ）：ｙと対応する記憶領域（ｙ∈ＤＰ）
Ｔ：＝｛１，２，…，ｔmax ｝
ｈt ：互いに独立なハッシュ関数：Ｙ→Ｙ（ｔ∈Ｔ）
Ｄ：＝｛１，２，…，ｄmax ｝
ｘt0：＝｛０，…，０｝∈Ｙ（ｔ∈Ｔ）
ｘtd：＝ｈt(ｘtd-1)∈Ｙ（ｔ∈Ｔ，ｄ∈Ｄ）
Ａk0d0：＝１＋ｋ0(ｄ0 −１）
（ｄ0 ∈Ｄ，ｋ0 ∈｛２，３，…，ｔmax ｝）
ε：＝２-(n-u)
ここでｈt が「互いに独立」とは、それらの計算が独立な事象とみなせることとし、
ハッシュ連鎖の長さｄ0 、連鎖長の上限ｄmax 、ハッシュ関数の数の上限ｔmax 、上記ハッシュ関数ｈ1 ，…，ｈtmax が格納される設定記憶部と、
連鎖長パラメータｄを０から上記上限ｄmax まで、関数識別パラメータｔを１から上記上限ｔmax までそれぞれ順次更新するパラメータ更新部と、
ハッシュ値ｘtdが上記特性点ＤＰの要素と一致したか否かの判定、上記連鎖長パラメータｄが上記上限ｄmax 以上であるか否かの判定、上記連鎖長パラメータｄが上記連鎖長ｄ0 より小さいか否かの判定、上記関数識別パラメータｔが上記上限ｔmax より小さいか否かの判定を行う判定部と、
入力されたハッシュ値ｘtd-1に対しハッシュ関数ｈt を演算してハッシュ値ｘtd＝ｈt(ｘtd-1）を生成するハッシュ関数計算部と、
生成されたハッシュ束が記憶されるハッシュ束記憶部と、
上記各部を順次動作させ、上記各記憶部に対する読み書きを行い、上記特性点ＤＰの要素と一致し、かつそのときの連鎖長ｄが上記連鎖の長さｄ0 以上のハッシュ値ｘtdと対応するハッシュ値ｘtd-d0を初期値と、その関数識別パラメータｔを組として、上記ハッシュ束記憶部内のそのハッシュ値ｘtdと対応した記憶領域に格納する制御部と
を具備するハッシュ連鎖つきコリジョン生成装置。
【請求項６】
請求項１〜３のいずれかに記載したハッシュ連鎖つきコリジョン生成方法の各過程をコンピュータに実行させるためのプログラム。
【請求項７】
請求項６に記載したプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
ハッシュ関数ｈでｘd ←ｈ（ｘd-1）なる関係で、逐次ｘが連鎖をつくるとき、ハッシュ連鎖といい、そのハッシュ連鎖がｄ0 長のところで、複数の値が一致することをコリジョン（衝突）が起きるといい、コリジョンが同一長である複数種類のハッシュ関数のハッシュ連鎖の束の生成を、ハッシュ連鎖つきのコリジョン生成という。
この発明はハッシュ連鎖つきのコリジョン生成方法、その装置、そのプログラム、および記録媒体に関する。
【背景技術】
【０００２】
まずこの明細書で用いる記号を説明する。
Ｙ：＝｛０，１｝n 、ｎビット長のバイナリ系列を要素とする集合、
［ｙ］v ：＝｛ｙの上位ｖビット｝（０＜ｖ＜ｎ，ｙ∈Ｙ）
ＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ＝（０，…，０）｝（０＜ｕ＜ｎ）
集合Ｙの要素ｙ中の上位ｎ−ｕビットがすべて０の要素の集合であり、その要素を「特性点（distinguished point）」と呼ぶ。
ＩＤＰ：＝｛ｙ∈Ｙ｜［ｙ］n-u ≠（０，…，０）｝
Ｍ（ｙ）：ｙが格納されるメモリ（ｙ∈ＤＰ）
Ｔ：＝｛１，２，…，ｔmax ｝
ｈt ：互いに独立なハッシュ関数：Ｙ→Ｙ（ｔ∈Ｔ）
Ｄ：＝｛１，２，…，ｄmax ｝
ｘt0：＝（０，…，０）∈Ｙ（ｔ∈Ｔ）
ｘtd：＝ｈt(ｘtd-1)∈Ｙ（ｔ∈Ｔ，ｄ∈Ｄ）
Ａk0d0：＝１＋ｋ0(ｄ0 −１）
（ｄ0 ∈Ｄ，ｋ0 ∈｛２，３，…，ｔmax ｝）
ε：＝２-(n-u)
ｈt （ｔ∈Ｔ）が「互いに独立」とは、それらの計算が独立な事象とみなせることとする。ある特定のハッシュ関数Ｈ：｛０，１｝* →Ｙを基に、「互いに独立」なｈt ：Ｙ→Ｙを容易に作ることができる。
【０００３】
ｔ（１），…，ｔ（ｋ0 ）∈Ｔ（ｔ（１）＜…＜ｔ（ｋ0 ）），ｄt(1)，…，ｄt(k0)，ｄ0 ∈Ｄ（ｄt(1)＞ｄ0 ，…，ｄt(k0)＞ｄ0 ）とする。このとき、それぞれｄ0 回のハッシュ演算を行うと同一のあるｙ∈Ｙとなる場合に、
（（ｔ（１），ｘt(1)dt(1)-d0），…，（ｔ（ｋ0 ），ｘt(k0)dt(k0)-d0））
を「深さｄ0 のハッシュ連鎖つきｋ0 −ｗａｙコリジョン」又は単に「ハッシュ連鎖つきコリジョン」と呼び、ｘt(1)dt(1)-d0，…，ｘt(k0)dt(k0)-d0をその入力値、ｙをその出力値と呼ぶ。
ｈt(1)：ｘt(1)dt(1)-d0  →  …  →  ｘt(1)dt(1)-1  →  ｙ
：
ｈt(k)：ｘt(k)dt(k)-d0  →  …  →  ｘt(k)dt(k)-1  →  ｙ
：
ｈt(k0)：ｘt(k0)dt(k0)-d0  →  …  →  ｘt(k0)dt(k0)-1  →  ｙ
ハッシュ連鎖がコリジョン（衝突）を起こす時、この確率的にまれなコリジョンを起こしている値とともに、それらのハッシュ連鎖をさかのぼって示すことで、結果的に予めその連鎖列の情報をもっていることを示すことで、ディジタル署名によって裏付けられている（非特許文献１）に示すものと同様の電子マネーの価値を与えようとする提案がなされている（（非特許文献２）参照）。
【０００４】
以下に非特許文献１に示されている小額決済方法の１つMicroMintの処理手順を示す。
１：銀行Ｂが十分な個数の「ｋ0 −ｗａｙハッシュコリジョン」（ｄ0 −１）を生成する。
２：銀行Ｂはハッシュ関数ｈt(ｔ∈Ｔ）、値ｋ0 、コイン使用有効期間を公開する。
３：銀行Ｂは顧客に「ｋ0 −ｗａｙハッシュコリジョン」
ｃ：＝（（ｔ（１），ｘt(1)dt(1)-1），…，（ｔ（ｋ0 ），ｘt(k0)dt(k0)-1））
（１個のコイン）を売却する。
【０００５】
４：コインｃを受け取った顧客Ｃは、商店Ｓにコインｃを支払う。
５：商店Ｓはｈt(1)（ｘt(1)dt(1)-1）＝…＝ｈt(k0)（ｘt(k0)dt(k0)-1）の成立（コインの正当性）を検証する。
６：検証に合格したら商店Ｓは顧客Ｃへ商品を送る。
７：商店Ｓはコインｃを銀行Ｂへ送って清算する。
８：銀行Ｂは顧客Ｃがコインｃを二重使用していないか確認する。これはどのコインをどの顧客に配ったかを記録しておくことで、銀行Ｂはコインの二重使用に対処する。
【０００６】
次に非特許文献１に示す方法では、顧客と商店の商取引の「一連の支払い」においても、各コイン毎にｋ0 回のハッシュ演算が必要である。しかし、正当性のあるコインを１個支払った顧客からの２個目以降のコインの支払いには、１個目ほど検証の計算コストを掛けたくないとする立場もある。非特許文献２に示す方法は、そのような立場に立った小額決済方式として、１個の「深さｄ0 のハッシュ連鎖つきｋ0 −ｗａｙコリジョン」をＡk0d0個のコインとして用いる方式である。その方式では「コリジョン」を以下のように用いる：１個目のコインとして
ｃ1 ：＝（（ｔ（１），ｘt(1)dt(1)-1），…，（ｔ（ｋ0 ），ｘt(k0)dt(k0)-1））
を用い、２個目以降は、例えば｛１＋（ｋ−１）（ｄ0 −１）＋ｑ｝個目（ｋ＝１，２，…，ｋ0 ；ｑ＝１，２，…，ｄ0 −１）のコインとしてｃk,l ：＝（ｔ（ｋ），ｘt(k)d(k)-1-q）を用いる。１個目のコイン、２個目以降のコインの正当性は、それぞれハッシュ関数の耐衝突性、一方向性で保証する。２個目以降のコインは、それ以前のあるコインと関連付けられており、よって正当性検証の計算コストを軽減できる。
【非特許文献１】Ronald L.Rivest,Adi Shamir,“Pay Word and MicroMint：Two simple micropayment schemes,”Security Protocols Workshop(1996),pp.69-87.
【非特許文献２】青木聡，駒野雄一，宮永望，本間祐介，森田光，太田和夫“ハッシュ連鎖つきコリジョンを用いた小額決済方式，”信学技報，ISEC2002-122(2003-03)，pp.97-102.
【非特許文献３】Pollard's rho heuristic,pp.845-849,in Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest：Introduction to Algorithms,The MIT Press,1997.
【非特許文献４】青木聡，太田和夫，福島順子，“MicroMint方式におけるcollision生成法の解析，”信学技報，ISEC2002-77(2002-11),pp.39-44.
【非特許文献５】福島順子，太田和夫，森田光，“k-way collisionの探索法の提案〜コイン造幣局の構築に向けて〜，”2003年暗号と情報セキュリティシンポジウム予稿集，pp.101-106.
【非特許文献６】Paul C.van Oorschot,Michael J.Wiener,“Parallel Collision Search with Cryptanalytic Applications,”J.Cryptology(1999)12,pp.1-28.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
非特許文献２ではハッシュ連鎖つきコリジョンの生成法は明らかにされず、一般には、ρ法と呼ばれる擬似乱数関数の周期性を利用する技法（非特許文献３参照）を手がかりに、ハッシュ関数を擬似乱数関数とみなしてコリジョン（衝突）合流点を求める方法が使われた。しかし、これは一般にハッシュ関数が１種類の場合にしか適用できなかった。
これに対して、メモリに逐次蓄積しつつコリジョンを発見的に見つける方法ならびにその改良がなされた（非特許文献４、非特許文献５参照）。一方、効率化のためにはＤＰという特徴点（特性点）を導入し、それを手がかりに合流点を求める方法なども考案されてきた（非特許文献６参照）。
【０００８】
しかし、この非特許文献６に示す方法によるＤＰの導入は、ハッシュ連鎖の長さが１と言えるものであり、ハッシュ連鎖をその長さを活用とするコリジョン探索に適用するものではなく、かつ安全性の問題が生じるものであった。この発明の目的はハッシュ関数が複数種類あり、安全性が高く、かつ、衝突（合流）するまでハッシュ連鎖が一定長を持つハッシュ連鎖の束といえるもの（以下、ハッシュ束と呼ぶ）の効率的なコリジョン生成（以下、ハッシュ連鎖つきのコリジョン生成と呼ぶ）の方法、その装置、そのプログラムおよび記録媒体を提供することにある。
【課題を解決するための手段】
【０００９】
この発明の方法は以下の通りである。
（１）ハッシュ連鎖生成部、制御・判定部、記憶部を備え、各ハッシュ関数ｈt について、初期値ｘt0よりハッシュ関数計算ｘtd＝ｈt(ｘtd-1)を逐次行ってｘt１，ｘt2，…のハッシュ連鎖を、最長ｄ＝ｄmax まで上記ハッシュ連鎖生成部により生成し、上記制御・判定部により上記ハッシュ連鎖中の上記特性点ＤＰの要素と一致し、かつハッシュ連鎖長が上記ｄ0 のハッシュ連鎖を選択し、上記記憶部の特性点ＤＰの要素と一致したときのハッシュ値ｘtdの記憶領域に分類格納する。
（２）上記（１）項において、上記制御・判定部により、上記記憶部の各記憶領域中に格納されているハッシュ連鎖の数が上記ｋ0 個以上のものを選択してハッシュ束として出力することを特徴とする。
【００１０】
（３）上記（１）又は（２）項において、ハッシュ連鎖の長さｄ0 、ハッシュ束生成時の個別のハッシュ関数でハッシュ連鎖を求めるときの上限の長さｄmax 、ハッシュ連鎖を求めるときの連鎖の数の上限ｔmax を設定し、上記ハッシュ連鎖生成過程及び上記分類格納過程は、ハッシュ関数識別パラメータｔを１に初期化する第１過程と、連鎖長パラメータｄを１に初期化してハッシュ値ｘtd-1に対しハッシュ関数演算ｈt(ｘtd-1）を施してハッシュ値ｘtdを生成する第２過程と、上記ハッシュ値ｘtdが上記特性点ＤＰの要素と一致するかを判定し、一致していれば第６過程に移る第３過程と、上記第３過程の判定が一致していないのであれば上記連鎖長パラメータｄが上記上限値ｄmax 以上かを判定し、以上であれば第８過程に移る第４過程と、上記第４過程の判定が以上でなければ上記連鎖長パラメータｄを＋１して、ハッシュ値ｘtd-1に対し、ハッシュ関数演算ｈt(ｘtd-1）を施してハッシュ値ｘtdを生成して上記第３過程へ戻る第５過程と、上記第６過程の判定がｄ0 より小さくないのであれば、そのときのハッシュ値ｘtdと対応したハッシュ値ｘtd-d0とｔとの組を上記ハッシュ値ｘtdの記憶領域に格納する第７過程とを有し、上記第６過程は上記連鎖長パラメータｄが上記設定ハッシュ連鎖長ｄ0 より小さければ、上記第８過程に移り、上記第８過程は関数識別パラメータｔが上記上限ｔmax より小さいかを判定し、その判定が小さいのであればパラメータｔを＋１して、上記第２過程に戻り、小さいのでなければ処理を終了する。この場合第８過程で処理を終了することなく、第９過程であるハッシュ値ｘtdの記憶領域にｋ0個以上のｘtd-d0とｔとの組がある領域検索を行い、第１０過程でｋ0個以上の組からはｋ0個だけを選択的に抽出し、処理結果を出力して処理を終了してもよい。
【００１１】
この発明の装置は以下の通りである。
（１）ハッシュ連鎖長の上限ｄmax 、ハッシュ連鎖数の上限ｔmax が入力され、ｄを連鎖長パラメータ、ｔを関数識別パラメータとして、各ハッシュ関数ｈt について、初期値ｘt0よりハッシュ関数計算ｘtd＝ｈt(ｘtd-1)を逐次行ってｘt1，ｘt2，…ハッシュ連鎖を、ｄ＝ｄmax まで生成するハッシュ連鎖生成部と、ハッシュ連鎖の長さｄ0 、上記連鎖長の上限ｄmax 、上記生成されたハッシュ連鎖ｘtdが入力され、これらハッシュ連鎖ｘtd中の、上記特性点ＤＰの要素と一致し、かつハッシュ連鎖長が上記ｄ0 のハッシュ連鎖を選択し、記憶部のその特性点ＤＰの要素と一致したときのハッシュ値ｘtdと対応した記憶領域に、そのハッシュ連鎖の初期値と関数識別パラメータｔを組にして格納する制御・判定部と、上記一致した特性点ＤＰの要素ごとに、異なる領域にハッシュ連鎖の初期値と関数識別パラメータｔの組が記憶される上記記憶部とを備える。
【００１２】
（２）ハッシュ連鎖の長さｄ0 、連鎖長の上限ｄmax 、ハッシュ関数の数の上限ｔmax 、上記ハッシュ関数ｈ1 ，…，ｈtmax が格納される設定記憶部と、連鎖長パラメータｄを０から上記上限ｄmax まで、関数識別パラメータｔを１から上記上限ｔmax までそれぞれ順次更新するパラメータ更新部と、ハッシュ値ｘtdが上記特性点ＤＰの要素と一致したか否かの判定、上記連鎖長パラメータｄが上記上限ｄmax 以上であるか否かの判定、上記連鎖長パラメータｄが上記連鎖長ｄ0 より小さいか否かの判定、上記関数識別パラメータｔが上記上限ｔmax より小さいか否かの判定を行う判定部と、入力されたハッシュ値ｘtd-1に対しハッシュ関数ｈt を演算してハッシュ値ｘtd＝ｈt(ｘtd-1）を生成するハッシュ関数計算部と、生成されたハッシュ束とが記憶されるハッシュ束記憶部と、上記各部を順次動作させ、上記各記憶部に対する読み書きを行い、上記特性点ＤＰの要素と一致し、かつそのときの連鎖長ｄが上記連鎖の長さｄ0 以上のハッシュ値ｘtdと対応するハッシュ値ｘtd-d0を初期値と、その関数識別パラメータｔを組として、上記ハッシュ束記憶部内のそのハッシュ値ｘtdと対応した記憶領域に格納する制御部とを具備する。
【発明の効果】
【００１３】
以上述べたようにこの発明によれば複数のハッシュ関数を用い、かつ特性点ＤＰの一致を利用し、しかも、その一致した特性点ＤＰの値ごとにハッシュ連鎖とその関数を分類しているため、ハッシュ連鎖つきコリジョンを効率よく生成することができ、しかも安全性が高いものが得られる。
【発明を実施するための最良の形態】
【００１４】
以下この発明の実施形態を説明する。
この発明装置の機能構成の概略を図１に示す。この装置１０はハッシュ連鎖演算部１１と制御・判定部１２と、記憶部１３とを備えている。ハッシュ連鎖演算部１１は各ハッシュ関数ｈt（ｔは関数種類を識別するパラメータであり、１，２，…）について、図１中に示しているように、レジスタ１１ａよりの初期値ｘt0を入力として、そのハッシュ値ｘt1＝ｈt(ｘt0)がハッシュ関数計算部１１ｂで計算されてレジスタ１１ａに格納され、この値ｘt1に対し計算部１１ｂでハッシュ計算が行われ、以下順次同様のことが繰り返され、ハッシュ値ｘtdmaxが得られるまでｘt0を初期値として、ｘt1，ｘt2，…，ｘtdmaxが順次生成される。なお先に示したようにｘt0：＝｛０，…，０｝∈Ｙであり、従ってｘ１0，…，ｘtmax 0 はいずれも０のビット列であり、つまり同一初期値であるが、ハッシュ関数により、関数と加算定数が異なる。図１では理解し易いように、各ハッシュ関数ｈ1 ，…，ｈtmaxごとのハッシュ連鎖演算部を示したが、１つのハッシュ連鎖演算部によりそのハッシュ関数ｈt を順次変更して、各ハッシュ関数ｈt についてハッシュ連鎖を、制御・判定部１２の制御のもとに行ってもよい。
【００１５】
制御・判定部１２はハッシュ連鎖が、複数個のハッシュ連鎖の出力値が一致する特性点ＤＰの要素であり、かつそのハッシュ連鎖長がｄ0 のものを選択し、ハッシュ連鎖演算部１１の制御記憶部１３に対する読み書き制御などを行う。
記憶部１３は特性点となったハッシュ値ｘtd（ｄは連鎖長を示すパラメータであり、０，１，…，ｄmax）をアドレスとしてそのハッシュ値となったハッシュ連鎖長ｄ0 のハッシュ連鎖の初期値と対応ハッシュ関数の種類とが組として格納される。
このハッシュ連鎖つきコリジョン生成装置１０による生成処理手順を図２に示す。ステップＳ１で求めたいハッシュ連鎖つきコリジョンのハッシュ連鎖長ｄ0 、ハッシュ束生成時に個別のハッシュ関数でハッシュ連鎖を求めるときの上限の長さｄmax 、ハッシュ連鎖を求めるときの連鎖数の上限ｔmax 、１つのコリジョン束のハッシュ連鎖の数ｋ0 を生成装置１０に設定入力する。
【００１６】
ステップ２でハッシュ束を生成する。つまり生成装置１０におけるハッシュ連鎖演算部１１で各ハッシュ関数ｈ1 ，…，ｈtmax について初期値ｘt0を初期値としてハッシュ関数計算を繰り返し行ってｔmax 個のハッシュ連鎖ｘ11，ｘ12，…，ｘ1d-1，ｘ1d，……，ｘtmax1，ｘtmax2，…，ｘtmaxd-1，ｘtmaxdを生成する。その際、制御・判定部１２はハッシュ値ｘtdが特性点ＤＰの要素と一致するかを調べ、ハッシュ連鎖長ｄが上限値ｄmax になるまでハッシュ値ｘtdが特性点ＤＰの要素とならないハッシュ連鎖は棄却し、特性点ＤＰになった時のハッシュ連鎖長ｄが設定連鎖長ｄ0 より小さいハッシュ連鎖も棄却することを制御・判定部１２で行う。また制御・判定部１２は棄却しなかった残ったハッシュ値、つまり特性点ＤＰの要素と一致したハッシュ値ｘtdについて、これが得られたハッシュ関数の種類を識別するｔと、その関数ｈt でｄ−ｄ0 回ハッシュ演算を施したハッシュ値ｘtd-d0（初期値）とを組として、記憶部１３のハッシュ値ｘtdをアドレスとする記憶領域Ｍ(ｘtd)に分類、記憶する。従って、１つの記憶領域Ｍ(ｘtd)には上位ｎ−ｕビットのみならず、下位ｕビットも同一となり、ハッシュ連鎖が互いにコリジョンを起す。複数の組（ｔ，ｘtd-d0）が記憶されることになる。
ステップＳ３で制御・判定部１２は記憶部１３中の各記憶領域Ｍi(ｘtd)で保存されているｔと初期値の組（ｔ，ｘtd-d0）がｋ0 個以上の領域からｔと初期値の組をｋ0 個取り出して出力する。
【００１７】
ハッシュ束が生成されるが、ｘtdが特性点ＤＰの要素と一致しても、これらの組（ｔ，ｘtd-d0）の全てが衝突（コリジョン）を起すわけではない。特性点ＤＰは［ｙ］n-u なる集合Ｙ中の各要素の上位ｎ−ｕビットが、例えば全て０である特徴というだけで、下位ｕビットに対する種別が生じる。仮に、下位ｕビットも一致する場合、そのハッシュ連鎖は互いに、コリジョンを起したという。上述したように各記憶領域Ｍ(ｘtd)には上位ｎ−ｕビットのみならず下位ｕビットも互いに一致する（ｔ，ｘtd-d0）の組、つまり正しくコリジョンを起す組が格納されることになる。
組（ｔ，ｘtd-d0）によって識別したい数、例えば［背景技術］の項で述べたコインの数はＡk0d0：＝（１＋ｋ0(ｄ0 −１)）、つまりハッシュ束中のハッシュ連鎖の数により、ｄ0 ，ｋ0 が決められる。またｄmax はｄ0 よりわずか大きな値であって、ε：＝２-(n-u)と置くと、ｄmax ＝２／ε程度とする。ｔmax はハッシュ束のハッシュ連鎖数Ａk0d0だけ（ｔ，ｘtd-d0）がみつからない場合に、処理が無限に繰り返されるのを防止するための値である。
【００１８】
次に以上述べたハッシュ連鎖つきコリジョン生成方法及び装置の更に具体化した例を説明する。図３にその機能構成を示す。入力部２１はキーボードのような入力手段であり、設定記憶部２２には入力されたハッシュ連鎖長ｄ0 、連鎖長の上限ｄmax 、連鎖数の上限ｔmax 、所用連鎖数ｋ0 が記憶され、またハッシュ関数ｈ1 〜ｈtmaxも記憶されている。パラメータ更新部処理に伴ってパラメータｄ，ｔを更新させるもので、ｄ用カウンタ２３ｄとｔ用カウンタ２３ｔを備える。判定部２４は各種パラメータが所定値と一致したかあるいは所定値との大小関係を判定するもので、特性点判定部２４DP、ｄ上限判定部２４ｄｍ、ｄ0 判定部２４ｄ0 、ｔ上限判定部２４ｔｍが備えられている。この装置はハッシュ関数計算部２５、ハッシュ束記憶部２６、作業用記憶部２７を備える。制御部２８は各部を順次動作させたり記憶部に対する読み書きなどを行うものであり、コンピュータにより機能させる場合は、ＣＰＵ（あるいはマイクロプロセッサ）２８ａ、プログラムメモリ２８ｂよりなり、パラメータ更新部２３、判定部２４の各機能も実行し、場合によるとハッシュ関数計算なども実行する。
【００１９】
図４にこの装置の処理手順の例を示す。
ステップＳ１で所定値ｄ0 ，ｄmax ，ｔmax ，ｋ0 が入力されるとこれを取り込んで設定記憶部２２に記憶する。
ステップＳ２でパラメータｔを初期値１とし、つまりパラメータ更新部２３のｔ用カウンタ２３ｔに初期値１を設定する。
ステップＳ３でパラメータｄを初期値１とし、つまりｄ用カウンタ２３ｄに初期値１を設定する。
【００２０】
ステップＳ４でｘtd-1をハッシュ関数計算部２５に入力してハッシュ値ｘtd＝ｈt(ｘtd-1)を計算する。ｄ＝１では初期値ｘt0（先に述べたようにどのハッシュ関数ｈt に対しても同一値）に対しハッシュ関数ｈt の演算を行ってｘt1 を生成することになる。このハッシュ値ｘtdはハッシュ関数計算部２５内のレジスタ２５ｒに保持され、ステップＳ４でのハッシュ関数演算はｄ＝１以外はレジスタ２５ｒ内のデータに対してハッシュ関数演算を行う。
ステップＳ５でその生成したハッシュ値ｘtdが特性点集合ＤＰの１つの要素と一致するかをＤＰ判定部２４DPにより判定する。
【００２１】
ステップＳ６でステップＳ５の判定が特性点ＤＰの要素のいずれとも一致していなければパラメータｄが上限ｄmax 以上であるかをｄ上限判定部２４ｄｍで判定する。
ステップＳ７でステップＳ６の判定が上限ｄmax 以上でなければ、ｄ用カウンタ２３ｄを１歩進させ、パラメータｄを＋１してステップＳ４に戻る。
ステップＳ５でハッシュ値ｘtdが特性点ＤＰの１つと一致していれば、ステップＳ８でその時のパラメータｄが設定長ｄ0 より小さいかをｄ0 判定部２４ｄ0 で判定する。
ステップＳ８での判定がｄ0 より小さければステップＳ９でｔが上限ｔmax より小さいかをｔ上限判定部２４ｔｍにより判定し、その判定が小さければ、ステップＳ１０でパラメータｔを＋１し、つまりｔ用カウンタ２３ｔを１歩進させてステップＳ３に戻る。
【００２２】
ステップＳ８での判定がｄ0 より小さくなければ、ステップＳ１１でハッシュ束記憶部２６内のその時のハッシュ値ｘtdをアドレスとしている領域Ｍ(ｘtd)に、その時のｔと、ハッシュ関数初期値ｘtd-d0の組を格納してステップＳ９に移る。
ステップＳ９でｔの判定がｔmax より小さくないのであれば、ハッシュ束生成処理は終了する。なお初期値ｘtd-d0は先のハッシュ連鎖の生成時に生成した対応するものを保持しておいてもよいが、その記憶量が多くなるのでｘtd-d0をｘt0を初期値として改めて求めても、ｄmax はｄ0 よりわずか大きいだけであるから、計算の増加は全体ではごくわずかである。上記処理により、特性点ＤＰと一致してもｄがｄ0 以下のハッシュ値ｘtdは廃棄され、またｔがｔmax より超えても特性点ＤＰと一致しないハッシュ値ｘtdも廃棄されることになる。
【００２３】
以上のハッシュ束の生成処理の後に必要に応じてパラメータｋ0 が設定入力されていれば、ステップＳ１２でハッシュ束記憶部２６の各領域Ｍ中でｋ0 個以上の組が格納されているものを検索し、ステップＳ１３でその検索した領域Ｍからｋ0 個のｔと初期値ｘtd-d0の組を読み出して出力部２８より出力する。このｋ0 個の組は、同一記憶領域Ｍから読み出したものであるからこれらは必ず互いにコリジョンを起すことになり、これらのｋ0 個とそれ以外のものとを区別でき、（ｔ，ｘtd-d0）の正当性を検証できる。なお、図４中のステップＳ１は図２中のステップＳ１と、図４中のステップＳ２〜Ｓ１１が図２中のステップＳ２に、図４中のステップＳ１２とＳ１３が図２中のステップＳ３とそれぞれ対応する。
【００２４】
先に述べたようにこの発明のハッシュ連鎖つきコリジョン生成装置はコンピュータにより機能させることもでき、この場合は、例えば図４に示した各処理過程をコンピュータに実行させるためのプログラムをＣＤ−ＲＯＭ、磁気ディスクなどの記録媒体、あるいは通信回線を介してプログラムメモリ２８ｂにダウンロードして、このプログラムを実行させればよい。
この発明によれば、連鎖を生成するハッシュ関数を１種類に限定しなかったことにより、ハッシュ連鎖つきコリジョンに、別のハッシュ連鎖が合流し、例えば、電子マネーなどの用途でおきうる偽造や変造の類が起こりにくい。
【００２５】
また、ハッシュ関数を複数とする場合でも、ハッシュ束の中に、特性点ＤＰに属する要素を含めた場合、同種の安全性上の問題が生じる。その部分は、図４中のステップＳ５により排除される。
この結果、単純に生成されたハッシュ値を闇雲にメモリに蓄積し、そのコリジョンを求めていた従来に比べ、極めて安全なハッシュ束を作ることが可能となる。
【産業上の利用可能性】
【００２６】
この発明は先に述べたように電子マネーなどに利用することができる。
【図面の簡単な説明】
【００２７】
【図１】この発明装置の実施形態の概略機能構成例を示す図。
【図２】この発明方法の概略処理手順の例を示す流れ図。
【図３】この発明装置の具体的実施形態の機能構成例を示す図。
【図４】この発明方法の具体的処理手順の例を示す流れ図。
【図１】
2005134454.tif 000003
【図２】
2005134454.tif 000004
【図３】
2005134454.tif 000005
【図４】
2005134454.tif 000006