定義

のため，攻撃者が発行銀行の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節では，提案方式の効率について議論する．

• Gへの離散対数問題攻撃者A^は，(|p|^に対して)で確率的多項式時間アルゴリズムで，

その成功確率は，

Pr[A(p,g,g^a)=a]

とする．ただし，gはGの生成元である．もし，無視できない成功確率のGへの離散 対数問題攻撃者A^{が存在しないとき，}Gは離散対数仮定を満たすという．

• G^へのDDH攻撃者A^は，(|p|^に対して)確率的多項式時間アルゴリズムで，そのアド バンテージは，

|Pr[A(p,g,g^a,g^b,g^ab)=”true”]−Pr[A(p,g,g^a,g^b,g^c)=”true”]|

とする． ただし，gはG^{の生成元で，}a,b,cは{0, . . . ,p−1}から一様ランダムに選ば れるとする．無視できないアドバンテージを持つG^へのDDH攻撃者A^{が存在しない} とき，群G^はDDH仮定を満たすという．

複数の銀行による電子現金のモデルの定義を以下に与える．

定義11 (複数の銀行によるオフライン追跡不可能電子現金のモデル．)複数の銀行による追跡 不可能電子現金方式は，(G,{B_i}i,U,S)から構成される．ただし，{B_i}i は銀行の集合，U ^は ユーザー，S^{は商店である．}{Bi}i，U^，Sは確率的多項式時間対話型Turing機械(PPITM)と する．

鍵生成：Gは，セキュリティパラメタkを入力とし，公開鍵と秘密鍵のペア(pk,sk)を 出力する確率的多項式時間アルゴリズムである．鍵のペアを生成した後，銀行は，信頼 できる第三者機関PKIに対して，公開鍵を送付し，対応する秘密鍵の知識をゼロ知識対

話証明(ZKIP, [49, 84])を用いて証明し，公開鍵を登録する．

発行プロトコル： 各Bi は，G(1^k)によりpki,ski を生成し，U^{は，公開鍵の集合}{pki}i

を与えられる．{B_i}i とUは，ある多項式回数の通信プロトコルを実行し，発行プロト コルの最後には，各Bi は成功か失敗を出力し，Uも成功か失敗を出力する．U^が成功 を出力したとき，Uは電子現金を入手している．

支払プロトコル：U^は，e-cashをS^{に送る．ただし，}AS^は{pk_i}i を持っているとす る．そして，U ^とSは，ある多項式回のラウンドの対話プロトコルを実行する．この 支払プロトコルの最後には，Uは成功か失敗を出力し，Sは受理か不受理を出力する．

S^{が受理したとき，}Sは，その取引履歴を記録しする．ここでは，取引履歴は支払プロ トコルでやり取りされるデータをのことであり，U^のIDやIPアドレスなどユーザー の情報は含まれていない．

清算プロトコルS^{は，使用された}e-cashと対応する取引履歴を Bに送る．すると，B は，受理か不受理を出力する．Bが受理を出力したときは，本物の現金をS ^に送る．

5.2.2 電子現金システムの攻撃シナリオ

定義12 (電子現金システムへの攻撃シナリオ)

適応的選択メッセージ攻撃(Adaptive Chosen Message Attack，ACMA):攻撃者A^は，

銀行の任意の集合に対して，電子現金の発行を依頼できる．また，A^{は，任意の入力を} ランダムオラクル[18]に問い合わせ，対応するハッシュ値を入手できる．

制限付き適応的内部者攻撃(Restricted Adaptive Insider Attack，RAIA):攻撃者A^は，

信頼できる第三者機関(TTP)を除く任意の参加者を corruptできる．corruptされた参 加者は，彼らの秘密情報をAに漏えいするが，プロトコルの手順には従う．つまり，

corruptされた参加者は，Aにコントロールされない．その意味で，この攻撃をRAIA

と呼ぶ．

適応的内部者攻撃(Adaptive Insider Attack，AIA):攻撃者A^は，TTPを除く任意の参

加者をcorruptできる．corruptされた参加者は，彼らの秘密情報をA^{に漏えいし，}A

に完全にコントロールされる．

RAIAとAIAの違いは，次のとおりである．RAIA攻撃者は，corruptされた参加者をコン トロールしたり，漏えいした秘密情報を用いてcorruptされた参加者に成りすましたりする ことが許されていない．他方，AIA攻撃者は，corruptされた攻撃者をコントロールしたり，

corruptされた参加者に成りすましたりしても良い．

文献[53]で提案された電子現金方式は，ACMA & RAIAに対する安全性しか証明していな かった．本章では，ACMA & AIAに対して安全な新しい電子現金方式を与える．

5.2.3 複数銀行による追跡不可能電子現金方式の安全性要件

本小説では，複数銀行による追跡不可能電子現金方式の安全性要件を与える．追跡不可能電 子現金が次の5つの要件を満たしているとき，その方式は，ACMA & AIAに対して安全であ るという．

■完全性 完全性とは，秘密情報を保持している正しい参加者は，プロトコルを正しく実行で きるという性質である．電子現金プロトコルの場合，以下のように定義される．

定義13 (完全性) (pk,sk)は，鍵生成アルゴリズムGによって正しく生成された公開鍵と秘密

鍵の組とする．以下を満たすとき，追跡不可能電子現金方式は完全性を満たすという．(i)発 行プロトコルに従ったら，{Bi}i とUはいつも成功を出力し，(ii)支払プロトコルに従ったら，

({pki}i, e-cash)が{Bi}iとUで正しく発行されたものであれば，U ^とS^{は，いつも各々成功と} 受理を出力し，(iii){Bi}i は，(i)と(ii)で生成された({pki}i, e-cash, transaction history)に対し て，いつも受理を出力する．

■正直なユーザーの追跡不可能性 正直なユーザーに対してプライバシーを提供する追跡不可 能性を定義する．追跡不可能電子現金方式では， 使用済みの電子現金(e-cashと取引履歴^*3) を解析したとしても，ユーザーが特定できない性質が必要である．

定義14 (正直なユーザーの追跡不可能性)D^{∗ は識別者，}{B^∗_i}i は銀行の集合，S^{∗ は商店とす} る．U0,U1 は，プロトコルに従って処理を行う正直なユーザーとする．view0B^∗ とview1B^∗ は，

それぞれ，U0 とU1 が電子現金を得るために発行プロトコルを実行した際の{B^∗_i}i のview — すなわち，{B^∗_i}i が得られるすべての情報—である．view_bS∗ は，Ub が電子現金を使うために 支払プロトコルを実行した際のS^∗のviewとする．

D^∗は，ACMA & AIAを実行する確率的多項式時間アルゴリズムとする．もし，以下のゲー

ムで無視できないアドバンテージを持つD^∗ が存在しなければ，電子現金方式は，ACMA &

AIAに対して，正直なユーザーの追跡不可能性を満たすという．

• D^{∗ は，任意の銀行}{B^∗_i}i と商店S^{∗ を適応的に}corruptすることが出来る．

• D^{∗ は，}corruptした{B^∗_i}i とS^{∗ をコントロールして，}U0 とU1 に対して，発行プロト コルと支払プロトコルを実行できる．

任意のタイミングで，D^{∗ は，}U0 とU1 と同じリストL^∗で，発行プロトコルを実行する．

ユーザーは，ランダムにb∈ {0,1}^{を選択し，}U_b^∗がS^∗と支払プロトコルを実行する最終的に

*3 電子現金とそれを使用する際の取引履歴には，IDやIPアドレスなど，Uの情報を含まないことに注意が必 要である．Uの情報を取引履歴に含むようなアプリケーションやシステムでは，それらの情報を適切に管理す る必要がある．例えば，匿名通信路[34]を使えば，オンラインでの匿名支払システムが実現でき，Dual署名

[68, 69]を使えば，匿名でのショッピングサービスが実現できる．本章では，電子現金システムの基本構成要素

としての電子現金プロトコルの追跡不可能性を議論するため，システムとして解決すべき性質については取り 扱わない.

に，D^{∗は，手に入れた}b∈R {0,1}^に対する(view_0B∗,view_1B∗,view_bS∗)をもとに，b^′ ∈ {0,1}^を 出力する．もし，b=b^′ ならばD^{∗の勝ちと呼び，}D^{∗ のアドバンテージを．}

Adv_D^∗ =|Pr[D^∗(view0B^∗,view1B^∗,viewbS^∗)→b]

−Pr[D^∗(view_0B∗,view_1B∗,view_(1−b)S∗)→b]|.

と定義する．

■不正なユーザーの追跡可能性 電子現金は，電子的なデータであるため容易に複製できる．

そのため，電子現金は，二重使用を防がなければならない．二重使用への対策のために，追跡 不可能電子現金には，以下のような不正なユーザーへの追跡可能性が必要となる．

定義15 (不正なユーザーの追跡可能性)

U₀^∗,U₁^∗は不正なユーザーで，どちらか一方のユーザーは同じ電子現金を2回使う（二重使 用）とする．{Bi}i はプロトコルに従って動作する正当な銀行の集合とし，{B^∗_i}i は(U₀^{∗ と}U₁^∗ によって) corruptされた銀行とする．S^∗は，(byU₀^∗,U^∗₁)によってcorruptされた商店とする．

さらに，VB は，U^∗₀ ^とU₁^∗ が電子現金を得るために発行プロトコルを実行した際の {Bi}i の viewの集合とする．

D^∗は，ACMA & AIAを実行する確率的多項式時間アルゴリズムとする．もし，以下のゲー

ムで圧倒的なアドバンテージを持つD^∗ が存在すれば，電子現金方式は，ACMA & AIAに対 して，不正なユーザーの追跡可能性を満たすという

任意のタイミングで，U^∗₀ ^とU₁^{∗は以下を実行する．}

• U₀^∗とU₁^{∗は，攻撃対象の銀行}{Bi}iを除いた，任意の銀行と商店をcorruptできる．

• U₀^∗とU₁^∗は，攻撃対象の銀行と発行プロトコルを実行できる．

そして，U₀^∗とU₁^{∗は，ランダムに} b∈ {0,1}^{を選択し，}U_b^∗に発行されたある電子現金を，

S^∗ で二重使用した取引履歴を出力する．

hist1(S^∗,U_b^∗)とhist2(S^∗,U_b^∗)は，それぞれ，U_b^{∗ が同じ電子現金}ECb に対して支払プロト コルを実行した際のS^∗の取引履歴とする.

清算プロトコルにより，攻撃対象の銀行が(ECb,hist1(S^∗,U_b^∗))と(ECb,hist2(S^∗,U_b^∗))を受 理したら，D^は(VB,ECb,hist1(S^∗,U_b^∗),hist2(S^∗,U_b^∗))を与えられ，b^′ ∈ {0,1}^{を出力する．も} し，b= b^′ならば，D^{の勝ちといい，}D^{のアドバンテージを}

Adv_D =|Pr[D(VB,ECb,hist1(S^∗,U_b^∗),hist2(S^∗,U_b^∗))→ b]

−Pr[D(V_B,EC_1−b,hist₁(S^∗,U1^∗−b),hist₂(S^∗,U1^∗−b))→b]|.