緒言

電子商取引を含むオンライン上の商活動は広がっており，多くの応用が研究されている．特 に，電子現金方式は，基本方式であるため，非常に多くの研究が行われてきた．電子現金方式 の安全性は，正直なユーザーに対する追跡不可能性，不正なユーザーに対する追跡可能性，電 子現金の偽造不可能性からなる．追跡不可能性を実現するために，Chaumはブラインド署名 [35]を提案した．

ブラインド署名方式は，署名者，ユーザー，検証者の3つのエンティティより構成される．

署名者は，ユーザーによって秘匿されたメッセージに対する署名の発行者である．検証者は，

署名者のっ公開鍵を用いて，署名が正しいか否かを検証する．近年では，多くの証明可能安全 なブラインド署名方式が提案されている[80, 81, 17]．

商店がオフラインで電子現金の正当性を検査することができる追跡不可能電子現金方式に対 する研究が数多く行われている[36, 26, 45, 6]．これらの方式では，ブラインド署名のブライ

ンド性より，誰であっても電子現金とユーザーを対応付けることができない．つまり，ユー ザーのプライバシーは，ブラインド署名によって守られるが，他方，もし，ユーザーが同じ電 子現金を二回使用したら，そのユーザーは特定される．このように，不正なユーザーの追跡可 能性により，電子現金の二重使用を抑止する．

しかし，通常の追跡不可能電子現金は，次のような内部者攻撃に対して脆弱である．文献

[36, 26, 45, 6]のように，一つの銀行のみが電子現金を発行する方式を考える．この状況では，

もし，銀行の従業員が銀行の秘密鍵を盗んだら，その従業員は電子現金をいくらでも発行する ことができ，そのために銀行は甚大な被害をこうむる恐れがある．そのような攻撃に対する対 策の一つは，発行機能をいくつかの銀行間に分割することである．このようにすると，もし，

いくつかの銀行が信頼できるならば，前述の攻撃を防ぐことができる．

さらに，たとえ銀行のいくつかの秘密鍵が漏えいしたとしても，電子現金の正当性は他の銀 行により保証されるので，この解決法は電子現金システムの頑強性も増す．しかし，一つの銀 行のみが電子現金を発行するモデルでその銀行の秘密鍵が漏えいする場合と同様に，複数の銀 行が電子現金を発行するモデルでも，それらの銀行の全ての秘密鍵が漏えいしたら，それらに 対応する電子現金は不正に発行可能となることに注意が必要である．

機能を分割する単純な方法は，いくつかの銀行が個々に署名した従来のブラインド署名を連 結することである．しかし，その方法では，従来のブラインド署名と比較すると，署名長—つ まり，電子現金のビット長—はn倍となり，計算コストと通信コストもn倍となる．ただし，

nは銀行の数とする．別の方法として，ブラインド閾値署名[67]を使う方法がある．(k,n)ブ ラインド閾値署名方式は，n人の署名者のうち，いかなるk人以上の署名者に対しても，署名 が発行できるが，そのプロトコルに参加する署名者がk人よりも少ないとき，正しい署名が発 行できないプロトコルである．ブラインド閾値署名を使うと，検証者は ，n人の署名者のうち のk人以上の署名者が署名プロトコルに参加したことを確認できるが，誰であってもそのk人 の署名者を特定することができない．そのため，トラブルが生じたとき，いくつかの銀行は電 子現金の発行にかかわっていないのに，電子現金の補償や補填を求められる可能性がある．

我々の解決法は，複数の署名者がお互いに協力して署名を生成するブラインド多重署名[56]

を用いることある．多重署名では，検証者は，署名プロトコルに参加した署名者を特定するこ とができる．つまり，銀行は発行にかかわっていない電子現金の補填を行う必要はないため，

ブラインド多重署名は，電子現金方式に適している．

ブラインド多重署名方式では，署名者の集合，ユーザー，検証者の3種類の参加者からなる．

署名者はお互いに協力し，ユーザーによって秘匿されたメッセージに対するブラインド署名を 生成する．検証者は，ブラインド多重署名の正当性の検証を，生成に関わった署名者の公開鍵 を用いて行う．もし，ブラインド多重署名の発行機能が，いくつかの銀行間に分割され，少な

くとも一つの銀行が信頼できれば，内部者の攻撃による電子現金の偽造は防ぐことができる．

5.1.1 関連研究

部分ブラインド署名方式(partially blind signature scheme)[7, 8] は，メッセージの一部が秘 匿されないブラインド署名である．この秘匿されないメッセージを利用することで，署名者と ユーザーはタグ鍵を埋め込むことができる．

Abeらは，文献において，文献[8]の部分ブラインド署名を改良することで，セキュリティ パラメタの多項式個の署名に対して証明可能安全なブラインド署名を提案した[6]．この方式 は，ユーザーがタグ鍵をブラインドすることを許しており，その結果，署名は署名者の公開鍵 とユーザーがブラインドしたタグ鍵を用いて検査することができる．また，文献[6]では，そ のブラインド署名を応用した追跡不可能電子現金方式も提案されている．

多重署名の概念は，ItakuraとNakamura[57]により導入された．多重署名方式では，複数の 署名者が互いに協力し，メッセージに対して一つの署名を生成する．多重署名方式の狙いは，

個々の署名を連結するよりも署名帳を削減することにある．Micaliら[72]は，多重署名への 攻撃モデルを与え，離散対数仮定の下で証明可能安全な多重署名を提案した．

Horsterら[56]は，ブラインド署名の概念を多重署名に適用することで，ブラインド多重署

名の概念を導入した．そして，メタブラインド署名方式に基づくブラインド多重署名を提案し た．そのブラインド多重署名方式は，内部者攻撃に対しても安全な電子現金や電子投票システ ムを構築するのに利用されている．次に，Chenら[37]は，双線形写像を用いたブラインド多 重署名を提案した．残念ながら，上記の二つのブラインド多重署名は，安全性が証明されてい ない．そのため，それから構成される電子現金や電子投票システムの安全性には疑問が残され ている．

5.1.2 本章の貢献

我々は，文献[53]において，ブラインド多重署名を用いた追跡不可能電子現金方式の攻撃 をモデル化し，その安全性要件を定式化した．そして，電子現金のサイズが銀行の数に依存せ ず，前述の関連研究の問題点を克服した証明可能安全な方式を提案した．しかし，その方式の 安全性は，制約された攻撃モデルの下でのみ安全性が議論されており，制約のない攻撃モデル での安全性は明らかになっていなかった．文献[53]の方式では，発行銀行のみが，銀行が不正 なユーザーを追跡するためのタグ鍵を用いており，他の保証銀行はタグ鍵を用いなかった．そ

のため，攻撃者が発行銀行のfully corrupt攻撃^*1を行う制約のない攻撃モデルの下では，安全 性が証明できなかった．

さらに，文献[53]では，その電子現金方式の保証銀行がタグ鍵を用いるように変更するこ とで，変更した方式は，発行銀行がcorrupt^*2されたとしても安全性が証明できると主張してい た．しかし，文献[53]の定理5では，その偽造ゲームにおいて商店がcorruptされることを考 慮していなかった．つまり，商店が不正を行う場合の安全性は保証していなかった．

本章では，DDH仮定とランダムオラクル[18]の下で，制約のない攻撃に対して証明可能安 全な新しい追跡不可能電子現金方式を提案する．提案方式では，制約のない攻撃シナリオでの

銀行のfully corrupt攻撃に対して安全性を保証するために，発行銀行だけではなく保証銀行も

タグ鍵を用いる．電子現金は，各銀行がブラインドしたタグ鍵の知識の証明を含むため，その サイズは，銀行の数に依存する．共通のタグ鍵を用いてブラインドしたタグ鍵を生成すること で，そのサイズを削減した．さらに，商店へのcorrupt攻撃に対する安全性を保証するために，

電子現金に別の証明を追加した．

5.1.3 本章の構成

第5.2節では，提案方式が安全性の根拠とする計算量的仮定の定義と，複数の銀行からなる 電子現金方式のコンセプトと安全性要件を与える述べる，

第5.3節では，提案方式である電子現金方式を与える．

第5.4節では，提案方式の安全性証明を与える．この安全性証明は，全て人手により行われ ている．

第5.5節では，提案方式の効率について議論する．