A Constant-Round Resettably-Sound Resettable Zero-Knowledge Argument in the BPK model

はじめに

resettable ZK proofs

  • the notion of resettable zero knowledge:
    • proposed by Canetti et al [CGGM 00]
    • proofs be ZK even if a prover is reset and enforced to use the same random tape on various inputs as many times as an adeversarial verifier wants.
    • motivated by attacks against smart cards, where a stolen card can be reset as many times as an attacker wants.
    • Recent deployment of cloud computing gives the notion new importance, because virtual machines in a cloud are far more easier to reset than real machines in the user's perimeter [RY 10], [Yilek 10].
  • [CGGM 00] shows that
    • Assuming the existence of 2-round perfectly-hiding commitments, there exist resettable ZK proofs with a polynomial number of rounds for all NP languages.
    • Later, the round complexity is improved to poly-logarithmic number of rounds by [KP 01].
  • [CGGM 00] also presented the notion of the bare public key (BPK) model.
    • The only requirement in the BPK model is that all verifiers deposit some public-key in a public file before the prover begins the interaction.
    • They constructed constant-round resettable ZK arguments in the BPK model, assuming some sub-exponential hardness assumption.

resettable soundness

  • the dual notion, resettably-soundness.
    • proposed by Barak et al [BGGL 01]
    • proofs be sound even if a verifier is reset and enforced to use the same random tape on various inputs as many times as an adeversarial prover wants.
    • Resettably-sound zero-knowledge proofs exist only for languages in non-uniform P. [BGGL 01]
    • Even for arguments, no resettably-sound ZK arguments exist for language outside BPP if the simulator is black-box.
  • [BGGL 01] derived, using the Barak's non-black-box strategy [Barak 01], that
    • constant-round resettably-sound zero-knowledge arguments for NP are possible only assuming collision-resistant hash functions.
      • poly-logarithmic-round, resettable ZK arguments of knowledge exsit for NP assuming the existence of CR hash functions and 2-round perfectly-hiding commitments. Moreover,
    • a constant-round sequentially-sound resettable-zero-knowledge argument exists in the BPK model.
      • Soundenss is divided into four subcategories in the BPK model; stand-alone, sequential, concurrent and resettable soundness. [MR 01]

resettable-sound resettable-ZK argument

  • How about simultaneous resettability ?
  • [CPV 04] showed a constant-round concurrent-sound resettable ZK argument in the BPK model assuming some sub-exponential hardness assumption.
  • [DL 08] showed a constant-round concurrent-sound resettable ZK argument in the BPK model only assuming CR hash functions.
  • Recently, [DGS 09] gave a breakthrough:
    • a new non-back-box strategy based on the Barak's strategy and showed
    • there exists a resettably-sound resettable zero-knwoledge argument system for all languages in NP (in the plain model), assuming trapdoor permutations and collision-resistant hash function families.
    • Its round-complexity is square in the security parameter.

our contribution

  • This paper gives a first constant-round argument for all NP languages in the BPK model that is both resettable-sound and resettable zero-knowledge.
  • First, we construct a constant-round resettable-sound concurrent ZK argument in the BPK model, following the design principle of Deng and Lin [DL 08].
  • In the course, we define and utilize a new type of commitment scheme, resettably-extractable commitment scheme. It enables a simulator to extract a value comitted to by a cheating committer that can perform resetting attack against a victim receiver.
  • Then, we apply to the constructed argument system the transformation of [DGS 09] from resettable-sound relaxed-concurrent ZK arguments to resettable-sound resettable ZK arguments. That results in a constant-round resettable-sound and resettable zero-knowledge argument for all NP languages in the BPK model.

定義

対話証明システムに対するリセット攻撃

(P, V) : NP言語Lの対話証明システム
t = poly(n)
x = (x1,...,xt) (各xi ∈ L)
y = (y1,...,yt) (各yiはxi ∈ Lのwitness)

cheating検証者V*によるリセット攻撃
  1. t 個のランダムテープ ω1,...,ωt を選択し、i∈[t]、j∈[t]について、P(i,j) := P(xi, yi, ωj) とする。各P(i,j)を証明者Pのインカネーションと呼ぶ。
  2. V* は P(i,j)達と多項式回のセッションを(シーケンシャルに)実行する。V*は、つぎにどのインカネーションP(i,j)とセッションをもつか適応的に選択できる。
  3. V* は そのview にもとづいて何らかの出力を行い、終了する。この出力を(P(x,y), V*(x)) とかく。

定義 (resettable WI)
対話証明(P, V)がresettable WIとは、任意のcheating検証者V*によるリセット攻撃において、以下の2つのアンサンブルが識別不可能であることをいう:
  • { (P(x,y1), V*(x)) }(x,y1,y2),
  • { (P(x,y2), V*(x)) }(x,y1,y2).

定義 (resettable ZK)
対話証明(P, V)がresettable ZKとは、任意のcheating検証者V*によるリセット攻撃において、あるPPTシミュレータMが存在し、以下の2つのアンサンブルが識別不可能であることをいう:
  • { (P(x,y), V*(x)) }(x,y),
  • { M(x) }(x,y).

cheating証明者P*によるリセット攻撃
  1. t 個のランダムテープ ω1,...,ωt を選択し、j∈[t]について、V(j)(x) := V(x, ωj) とする。各V(j)(x)を検証者Vのインカネーションと呼ぶ。
  2. P* は V(i,j)達と多項式回のセッションを(シーケンシャルに)実行する。ただし、P*は、(必ずしもLに属すとは限らない)証明対象x を適応的に選ぶことができ、そのxについて、どのインカネーションV(j)とセッションをもつかも適応的に選択できる。

定義 (resettably-soundness)
対話証明(P, V)がresettably-soundとは、任意のcheating証明者P*によるリセット攻撃において、「いずれかのセッションにおいて、対応するV(j)が、L に属さないxを受理してしまう」確率がネグリジブルである、ことをいう。

The BPK Model

  • 公開ファイル F は、各検証者の公開鍵を記録したレコードの集まり。
  • 証明者Pは、入力として x∈L、そのwitness y、ランダムテープ r および公開ファイルF(と検証者Vの公開鍵のインデックス)を受け取る。
  • 検証者Vは、まず、第1ステージで鍵ペア(pk, sk)を出力し、公開鍵pkを公開ファイルFに記録する。つぎに、第2ステージで、秘密鍵sk、x∈L、ランダムテープ w を入力として、証明者Pとの間でプロトコルを実行し、accept か reject を出力する。

BPKモデルでは、concurrent ZK のシミュレータの構成が容易である。

Known Constructions

Our constructionsで用いるknown constructionsについてまとめる。

A resettable ZK argument

  • claw-free permutationsが存在するならば、任意のNP言語に対し、poly-logarithmic ラウンド resettable ZK argument が存在する。[KP 01]
  • BPKモデルでは、衝突困難なハッシュ関数が存在するならば、任意のNP言語に対し、定数ラウンド resettable ZK argument が存在する。[BGGL 01]

a constant-round public-coin ZK argument

Barak [Barak] により、non-black-box simulatorを用いることで、任意のNP言語に対し、定数ラウンド、パブリックコインの zero-knowledge argument が可能であることが示された。

Barakのプロトコル [Barak]
[部品]
  • ハッシュ関数 h : {0,1}* → {0,1}n
  • 統計的束縛コミットメント Com
  • 言語Λ = { (h, c, r) ∈ Hn x {0,1}n x {0,1}n |
    • ∃Π, ∃s, z = Com(h(Π);s), Π(z) outputs r within nlog log n/5 steps. }
[共通入力]: x ∈ L
[証明者のローカル入力]: witness w
[プロトコル]
  • P ← V : Send h ← Hn.
  • P → V : Choose s ← {0,1}*. Send c = Com(h(0n); s).
  • P ← V : Send r ← {0,1}n.
  • P ⇒ V : A WI universal argument : 『x ∈ L or (h,c,r) ∈ Λ.』

BGGL コンパイラ

[BGGL]により、任意のNP言語に関する、定数ラウンド、パブリックコインのargumentは、WI性やZK性を保存したまま、resettably-sound にすることができることが示された。

L : 任意のNP言語

構成(BGGLコンパイラ)
  • [部品] :
    • 疑似ランダム関数 fs
    • 定数ラウンド、パブリックコインのargument (P,V) for L
  • [プロトコル (P, W)] :
    • P : P と同じ
    • W : 以下を除いてVと同じ:
      • W determines the current round message by applying fs to the transcript so far. (sはWのランダムテープ。)

定理 (BGGLコンパイラ)
部品に示した仮定のもとで、(P, W) は a resettably-sound argument for L. ここで、(P, V) が ZK (resp., WI) ならば、(P, W)もZK (resp., WI) 。

  • (P, W)が定数ラウンドであることがポイント。

系 (BGGLコンパイラ)
  • Barakの定数ランド、パブリックコイン ZK argument をBGGLコンパイラで変換することで、任意のNP言語に対し、定数ラウンド resettably-sound ZK argumentを得る。
  • ハミルトニアンの3-round WI argumentをBGGLコンパイラで変換することで、任意のNP言語に対し、3-round resettably-sound WI argumentを得る。

A resettable WI argument of knowledge

[BGGL 01]は、上の定数ランドrsZKAを用いて、衝突困難なハッシュ関数が存在するとの仮定のもと、任意のNP言語について、定数ラウンド resettable WI argument of knowledge が存在することを示した。

L : 任意のNP言語

構成(rWI)
  • [部品]:
    • 疑似ランダム関数 fs
    • 統計的束縛コミットメント Com
    • a constant-round resettably-sound ZK argument of of NP language { (Com(e;r), (e,r)) }
    • a 3-round WI arugment of knowledge of L, with transcript (a,e,z).
  • [共通入力]: x ∈ L
  • [証明者のローカル入力]: witness w、ランダムテープ (R1,R2)
  • [プロトコル]
    • P ← V : Choose a random challenge e for the 3-round WIA. Send Ce ← Com(e).
    • P → V : R1* = fR1(Ce). 以下、the 3-round WIA の実行にはランダムテープとしてR1*を使用。 Send the first message for the 3-round WIA to prove x ∈ L.
    • P ← V : Send e. Then prove that『e is the string to which Ce was committed』 using the rsZKA with random tape R2.
    • P → V : If that proof by V is acceptable, reply z to V.

The protocol is a constant-round resettable WI argument of knowldge for L ∈ NP. [BGGL 01]

系(rWI)
衝突困難なハッシュ関数が存在すれば、任意のNP言語について、定数ラウンド resettable WI argument (of knowledge) が存在する。

Our Constructions

コミットメントスキームのバリエーションであるconditional commitment schemeを導入する。さらに、リセット攻撃が可能な悪意ある送信者S*に対しても、あるシミュレータがS*のコミットメントからそのコミット対象の値を抽出することのできる、resettably-extractableなconditional commitment schemeを構成する。

この、resettably-extractableなconditional commitment schemeを利用して、resettably-sound concurrent ZK argument in the BPK modelを構成する。

A conditional commitment scheme

コミットメントスキームのバリエーション。送信者はコミット対象文字列vのほかに、``条件''xを入力とする。ある言語Lについて、コミットメントの秘匿性はx∈Lのときのみ、また束縛性はx not∈Lのときのみに保障される。

定義 (conditional commitment scheme)
対話的チューリング機械の組(S, R)が言語Lを条件とするconditional commitment schemeとは、
  • (Correctness) ∀v∈{0,1}n, ∀x∈{0,1}n,
    • Pr[ (d, c) ← <S(v,x),R(x)>, (-, v') ← <S(d),R(c)> : v'=v] = 1.
  • (Conditional Hiding) ∀R* : a non-uniform PT cheating receiver, ∀x∈L∩{0,1}n,
    • Pr[ (v0,v1,s) ← R*(x), b ← {0,1}, (-,b') ← <S(vb,x),R*(s)> : b'=b ] ≦ 1/2 + ε(n).
  • (Conditional Binding) ∀C* : an efficinet cheating sender, ∀x ∈ {0,1}n s.t. x not ∈ L,
    • Pr[ ((d1,d2,c) ← <S*(x), R(x)>, (-, v1) ← <S*(d1), R(c)>, (-, v2) ← <S*(d2), R(c)> : v1 ≠⊥, v2 ≠⊥, v1 ≠v2 ] ≦ ε(n)


cheating送信者S*によるリセット攻撃
  1. t 個のランダムテープ ω1,...,ωt を選択し、j∈[t]について、R(j) := R(ωj) とする。各R(j)を受信者Rのインカネーションと呼ぶ。
  2. S* は R(j)達と多項式回の、Lに属さないxを条件とする、コミットメントフェーズのみのセッションを(シーケンシャルに)実行する。ただし、S*は、コミットメント対象vと条件x(not∈L)を適応的に選ぶことができ、そのv, xについて、どのインカネーションR(j)とセッションをもつかも適応的に選択できる。同じ、R(j)が同じv,x(や異なるv,x)について何度選ばれてもよい。

定義 (resettably-extractability)
言語Lを条件とする条件付コミットメントスキーム(S,R)がresettably-extractableであるとは、リセット攻撃を行う、任意のcheating送信者S*に対し、あるリセッタブルエクストラクター
  • (view, extracted_values) ← E(1n)
が存在し、Eの出力するviewは、S*のreal viewとcomputationalに識別不可能で、Eの出力するextracted_valuesは、viewにおいてS*が(Lに属さないxを条件として)コミットを完了したすべての値からなるリストである、ことをいう。

the resettably-extractable conditional commitment scheme
  • 部品
    • NP言語 L
    • 疑似ランダム関数 F
    • a one-way permutation f with a hardcore predicate h
    • a (computationally-hiding statistically-binding) standard non-interactive commitment scheme Com
    • a ZAP (two-round public-coin witness indistinguishable proof [DN 00])
    • a (stand-alone) ZK argument
    • a resettably-sound ZK argument
  • 入力
    • Sの入力:条件 x (∈{0,1}n), 値 v (∈{0,1}n), ランダムテープ ωS
    • Rの入力:条件 x, ランダムテープ ωR
  • プロトコル:
    • コミットフェーズ:
    • S → R : Select a one-way permutation f. Select a random string r1 of length n2 and commit to it : c1 ← Com(r1). Generate a first-round message σS of a ZAP. Commit to its (unused part of) random tape ωS : cS ← Com(ωS). Send f, c1, cS, σS.
    • S ← R : Compute ωR* = FωR(x, f, c1, cS, σS). Select a random string r2 of length n2 from ωR* and commit to it using ωR* as random tape : c2 ← Com(r2). Send c2.
    • S → R : Send r1.
    • S ⇒ R : resettably-sound ZKA with the (unused part of) random tape ωS  : 『 ∃w, c1 = Com(r1; w). 』
      • in this argument every S's message (as a prover) is coupled with a ZAP : 『the message being sent is computed using ωS as a random tape according to the protocol OR x ∈ L. 』
    • S ← R : Send r2.
    • S ←= R : ZKA with the (unused part of) random tape ωR*  : 『 ∃w, c2 = Com(r2; w). 』
      • in this argument every S's message (as a verifier) is coupled with a ZAP : 『the message being sent is computed using ωS as a random tape according to the protocol OR x ∈ L. 』
      • If any of the ZAPs is invalid, R aborts the protocol.
    • S → R : r1,...,rn = r = r1 + r2. For i = 1 to n, si = f-1(ri). Send C = v1+h(s1), ... , vn+h(sn).
    • デコミットフェーズ:
    • S → R : Send s, v = v1, ... , vn.
    • R : Let r1,...,rn = r1 + r2. Check whether ri = f(si) for all i = 1 to n and whether C = v1+h(s1), ... , vn+h(sn). If so output v, otherwize output ⊥.


定理 (resettably-extractabile conditional commitment scheme)
上記部品が存在するとの仮定のもとで、the scheme は resettably-extractable conditional commitment scheme である。

証明のスケッチ
(conditional hiding)
[Step 1]
a basic commitment scheme (S', R') :
  • 部品
    • a one-way permutation f with a hardcore predicate h
    • a (computationally-hiding statistically-binding) standard non-interactive commitment scheme Com
    • a (stand-alone) ZK argument
    • a (resettably-sound) ZK argument
  • 入力
    • S'の入力:値 v (∈{0,1}n)
    • R'の入力:1n
  • プロトコル:
    • コミットフェーズ:
    • S' → R' : Select a one-way permutation f. Select a random string r1 of length n2 and commit to it : c1 ← Com(r1). Send f, c1.
    • S' ← R' : Select a random string r2 of length n2 and commit to it : c2 ← Com(r2). Send c2.
    • S' → R' : Send r1.
    • S' ⇒ R' : (resettably-sound) ZKA :『 ∃w, c1 = Com(r1; w). 』
    • S' ← R' : Send r2.
    • S' ←= R' : ZKA :『 ∃w, c2 = Com(r2; w). 』
    • S' → R' : r1,...,rn = r = r1 + r2. For i = 1 to n, si = f-1(ri). Send C = v1+h(s1), ... , vn+h(sn).
    • デコミットフェーズ:
    • S' → R' : Send s, v = v1, ... , vn.
    • R' : Let r1,...,rn = r1 + r2. Check whether ri = f(si) for all i = 1 to n and whether C = v1+h(s1), ... , vn+h(sn). If so output v, otherwize output ⊥.

Claim 上記部品が存在するとの仮定のもとで、the above scheme is computationally hinding.
(Proof) あるefficinet cheating receiver (R')* が hiding property を破るとする。(R')*を用いて、f のハードコア述語 h を識別するアルゴリズム D を構成する。

D : r1 (= f(s1)), ..., rn (= f(sn))およびb1, ..., bnを入力として以下のように動作する。(biはすべてriのハードコアであるか、もしくはすべてランダムビットである)
  • (R')*を起動し、チャレンジの値 v0, v1を受け取る。
  • c1 ← Com(0n2)とし、f, c1 を(R')*に送る。
  • (R')*より c2 を受け取ったら、
    • n2ビットのランダム文字列r'を選択し、(R')*に送る。
    • the ZKA のシミュレータを用いて、c1がr'へのコミットメントであることを``証明''する。
  • (R')*より r2 を受け取り、その後のthe ZKA が妥当なら
    • r1 = r + r2とし、(R')*をc2を出力した直後にrewindし、r1を送る。さらに、the ZKA のシミュレータを用いて、c1がr1へのコミットメントであることを``証明''する。
  • (R')*より再び r2 を受け取り、その後のthe ZKA が妥当なら、
    • d ∈ {0,1} をランダムに選択し、vd1 + b1, .... , vdn + bn をR'* に送る。
  • (R')*の出力を自身の出力として出力して停止する。

もしも、 (R')*がhiding propertyを破るなら、このDがハードコアを識別することは見やすい。
[Step 2]
あるR*があるx∈Lを条件として、the schemeのhiding propertyを破るとする。R*を用いてthe basic schemeのhiding propertyを破る(R')*が構成できることを示す。

(R')* : x (∈L) とそのwitness w を補助入力として以下のように動作する。
  • xを入力としてR*を起動し、チャレンジの値 v0, v1を受け取り、v0, v1を自身のチャレンジとしてチャレンジャーS'に送る。
  • S'から、f, c1を受け取ったら、
    • cS ← Com(0*) とし、the ZAPのfirst message σSを計算し、cS, σS, f, c1をR*に送る。
  • R*よりc2を受け取ったら、そのままS'に転送する。
  • S'からr1を受け取ったら、そのままR*に転送する。さらに、S'よりつづくthe ZKAを受け取り、R*との間で中継する。ただし、ここでS'からの各メッセージには、wをwitnessとして計算したthe ZAPを添付する。
  • R*からr2を受け取ったら、そのままS'に転送する。さらに、R*よりつづくthe ZKAを受け取り、S'との間で中継する。ただし、ここでS'からの各メッセージには、wをwitnessとして計算したthe ZAPを添付する。
  • S'からCを受け取ったら、そのままR*に転送する。
  • R*の出力を自身の出力として出力して停止する。

ZAPのWI性より、(R')*がR*に提供するviewはreal viewと識別不可能である。よって、背理法の仮定より(R')*はthe basic schemeのhiding propertyを破り、上のClaimに矛盾する。

(conditional binding)

the schemeはBlumコミットメントを利用しているので、``unconditional''にbinding propertyをもつ。

(resttable-extractability)
Lに属さない条件xについて、リセット攻撃を行う、任意のcheating送信者S*に対し、リセッタブルエクストラクターEを以下のように構成する。

E:
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。value_list をφに初期化する。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、それがjについてfreshか否かをチェック:
      • fresh でないならば、fmsgを共有する、対応する過去のトランスクリプトからR(j)のメッセージを取り出して再送することでシミュレートを行う。
      • 以下、fmsg は freshであると仮定する。
    • freshなランダムテープ ω* を生成する。
    • ω*をランダムテープとして、c2ω* Com(0n2) を計算し、c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • ω*より長さn2のランダムストリング s を取り出し、r = f(s), r2 = r + r1 とし、r2 をS*に返す。さらに、ω*(の未使用部分)をランダムテープとして、the ZKA のシミュレータMを用いて、c2がr2へのコミットであることを``証明''する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取ったら、記録しておいたsを用いて、v = (v1, ... , vn)を計算し、value_list に追加する。
  • S*が停止したら、そのsimulated view と value_list を出力する。

Eの性能:
  • [time]
EはストレートラインにS*をシミュレートしているので、明らかに多項式時間で停止する。
  • [view]
  • S*の第1メッセージ fmsg =(x, f, c1, cS, σS) がjについてfreshでないとき、
    • ωR* = FωRj(fmsg)は、fmsgを共有する過去の該当セッションのそれとまったく同一である。よって、c2, r2も該当セッションのそれの再送である。
    • Comの束縛性と(r1に続く)the ZKAのresettableな健全性より、c1∈fmsgが束縛するr1も(ネグリジブルな確率の例外を除いて)該当セッションのそれの再送である。
    • 2つのZKAに属するメッセージについて。入力となるc1, r1, c2, r2, ωR*がすべて該当セッションと同一で、ZAPの健全性よりS*のメッセージは、cS∈fmsgが束縛するωSを用いて計算されているので(x not∈L に注意)、2つのZKAに属するすべてのメッセージも該当セッションのそれと同一であり、再送である。よって、上記Eの、該当セッションのトランスクリプトを再送するシミュレーションは妥当である。
  • S*の第1メッセージ fmsg =(x, f, c1, cS, σS) がjについてfreshなとき、
    • 関数Fの疑似ランダム性により、該当インカネーションR(j)はその都度フレッシュなランダムテープω* = FωRj(fmsg)を用いる。
    • よって、Comの秘匿性と(r2に続く)the argumentのZK性より、Eによるシミュレーションはリアルケースと識別不可能である。ここで、第1メッセージ fmsgがfreshな場合は、the argumentの証明対象ステートメント(c2, r2)は毎回異なるので、スタンドアローンのZK性で十分であることに注意する。
  • 以上より、Eが出力するS*のsimulated view は S*のreal view と識別不可能である。

  • [value_list]
    • Eが生成したs は コインフリッピングで共有された r=f(s)のfによる逆像となっているので、明らかに、上記のようにしてEが出力する 各v はS*がコミットした値である。

Q.E.D.

ZK argument としてBarakの定数ランドZKA、およびそれにBGGLコンパイラを適用して得られるresettably-soundな定数ラウンドZKAを用いることで、

系 (resettably-extractability)
  • one-way permutations と CR hash functionsが存在すれば、定数ランドのresettably-extractable conditional commitment scheme が存在する。


A resettably-sound concurrent ZK argument in the BPK model

構成(rs cZK)
L : 任意のNP言語
the resettably-sound concurrent ZK argument for L in the BPK model
  • 部品
    • a one-way function f
    • a constant-round resettably-extractable conditional commitment scheme rCom w.r.t. L
    • a constant-round resettable WI argument of knowledge for { (y0,y1) : ∃α, y0 = f(α) OR y1 = f(α) }
    • a constant-round resettably-sound WI argument for { (x, c, y0,y1) : ∃β, βはx∈Lのwitenss OR β=(β', r), c = rCom(x, β';r), y0 = f(β') OR β=(β', r), c = rCom(x, β';r), y1 = f(β') }
  • 入力
    • Pの入力: x, w, F, i (pki = (f, y0, y1) ∈ L)
    • Vの入力: x, α (yb = f(α))
  • プロトコル
    • P ←= V : rWI AOK 『∃α, y0 = f(α) OR y1 = f(α)』.
    • P ⇒ V : rCom を用いて条件xのもとで0n にコミット with transcript c。
    • P ⇒ V : rs WIA 『∃β, βはx∈Lのwitenss OR β=(β', r), c = rCom(x,β';r), y0 = f(β') OR β=(β', r), c = rCom(x,β';r), y1 = f(β')』.

定理(rs cZK)
上記部品が存在するとの仮定のもとで、the protocol は the BPK model において定数ラウンドの a resettably-sound concurrent ZK argument である。


証明
[completeness] 明らか。

[cZK]
the BPK model における standard argument.
concurrent 攻撃における任意のcheating verfier を V* とする。
V*に対するシミュレータ Sim を以下のように構成する。

Sim:
  • V*のfirst phaseを実行し、公開ファイルF を受け取る。
  • V*との間でsecond phaseを実行する。このとき:
    • あるインタラクション I について、V*がfirst proof をpassしたら:
      • インタラクション Iが対象とする公開鍵を pkiとするとき、その秘密鍵αiをまだ抽出していなかったら、the rWI AoK のスタンドアローンエクストラクタを用いて、αiを抽出しておく。(このとき、エクストラクタの対象はV*のインタラクションIのみなので、スタンドアローンエクストラクタで十分であることに注意する。)
    • あるインタラクション I について、コミットメント c を実行する段階になったら、
      • 抽出しておいたαiにコミットする with transcript c = rCom(x, αi;ri)。
    • あるインタラクション I について、the second proof を実行する段階になったら、
      • β = (αi;ri)を witness として the second proof を実行する。
Simの性能:
  • [time] Fは多項式サイズなので、スタンドアローンエクストラクタの呼び出しも多項式回。よって、Sim はexpected多項式時間。
  • [view] Comのconditional hiding propertyとthe second proofのWIより、Sim内のV*のviewはV*のreal viewと識別不可能。(Hybrid: cとしてαiにコミット。the second proof ではreal witness w を使用。)

[rs]
reset 攻撃において、ある x not∈ L についてnon-negligbleな確率であるインカネーションV(x)を説得する、任意のcheating prover を P* とする。
P*を用いて一方向関数 f を破るアルゴリズムAを構成する。
(以下では、簡単のため、P*はLに属さないxについてのみ検証者インカネーションV(x)を呼び出すとする。)

A: y (=f(β)) を入力として、
  • b ← {0,1}, yb = y  ※ This defines βb = β
  • β1-b ← {0,1}n, y1-b = f(β1-b)
  • 証明者P*を起動し、公開ファイル F = { (id, y0, y1) } を与える。
  • 証明者P*が呼び出す各インカーネーションV(x)を以下のようにシミュレートする(xはLに属さない)。
    • the first proof は、witness として β1-bを用いて実行する。
    • コミットメントrComについては、そのリセッタブルエクストラクターEを起動し、Eが出力するviewを用いてP*に対し受信者として振る舞う。
    • the second proofについてはオネストに検証者として振る舞う。
  • アクセプトしたインカネーションVj*(x*)をランダムに選び、それが受け取ったコミットメント c がコミットしている値を、Eが出力したvalue_listから取り出し、β'とする。
  • β'の第1成分β1'について、f(β1') = y がどうかチェックし、そうならばβ1'を、さもなければ⊥を出力して停止。

Aの性能:
  • [time] 多項式時間であることは明らか。
  • [view] ※ フォーマルには hybrid argument を用いるところだか。
    • the first proof と the second proof はオネストにシミュレートされている。問題はrComに関するviewのみ。
    • rComのresettable extractor Eが出力するviewのsimulatabilityより、コミットメントcのview は real view と識別不可能。(x not∈ L に注意)
    • 以上より、AがsimulateするP*のviewはreal viewと識別不可能。
  • [output]
    • 仮定より、Aが選択した Vj*(x*) は、x* not∈ L であるにも関わらず、non-negligibleな確率でVを説得する。
    • x* not∈ L なので、the second proofのresettable soundnessより、そのwitnessは β1'としてβ0またはβ1を含み、それはcでコミットされている。
    • よって、対応するインカネーションについて、rCom の resettable extractor E は、β1'としてβ0かβ1を抽出している。(x* not∈ L に注意)
    • the first proofのresettable WIより、それがβbである確率はネグリジブルな誤差を除いて1/2.

以上より、Aはnon-negligibleな確率でβ1'としてβ = βbを計算し出力する。これは、f の一方向性に反する。
Q.E.D.

系(rs cZK)
one-way permutations と CR hash functions が存在するならば、BPKモデルにおいて、任意のNP言語に対し定数ランドの a resettably-sound concurrent ZK argument が存在する。

(rs cZK)⇒ (rs rZK)


Deng-Goyal-Sahai のtransformation [DGS 09] :
  • resettably-sound relaxed-concurrent ZK argument ⇒ resettably-sound resettable ZK argument
    • the relaxed concurrency は concurrency を弱めた安全性。
  • the transformation works in the plain model
  • rs ZKA を部品として用いるが、rs ZKA は the plain model で定数ラウンド。よって、Goyal-Sahai のtransformationにおいて、変換元のプロトコルが定数ラウンドならば、変換後のプロトコルも定数ラウンド。

よって、定数ランドの the resettably-sound concurrent ZK argument in the BPK model に Goyal-Sahai のtransformation を適用することで、

系(rs rZK)
one-way permutations と CR hash functions が存在するならば、BPKモデルにおいて、任意のNP言語に対し定数ランドの a resettably-sound resettable ZK argument が存在する。


Appendix

Formal proof of resettable-extractability


We prove the resettable-extractability of the proposed conditional commitment scheme. We define a sequence of expreiments Real, Hyb1, ... , Hyb4, preserving indistinguishability of their outputs. The first experiment Real corresponds to a real resetting attack by a cheating sender S* and the final experiment Hyb4 gives us the claimed resettable-extractor.

Real :
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、ωR* = FωR(j)(x, f, c1, cS, σS) を計算し、ωR*をランダムテープとして長さn2のランダム文字列r2を選択し、(ωR*をランダムテープとして)それにコミットする:c2 ← Com(r2). c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、ωR*(の未使用部分)をランダムテープとして用いる。また、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • r2をS*に返す。
      • さらに、ωR*(の未使用部分)をランダムテープとして、the ZKA を用いて、c2がr2へのコミットであることを証明する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取る。
  • S*が停止したら、そのsimulated view を出力する。

Hyb1 :
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、それがjについてfreshか否かをチェック:
      • fresh でないならば、fmsgを共有する、対応する過去のトランスクリプトからR(j)のメッセージを取り出して再送することでシミュレートを行う。
      • 以下、fmsg は freshであると仮定する。
    • freshなランダムテープ ω* を生成する。以下、R(j)のシミュレーションにはランダムテープω* を用いる。
    • 長さn2のランダム文字列r2を選択し、それにコミットする:c2 ← Com(r2). c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • r2をS*に返す。
      • さらに、the ZKA を用いて、c2がr2へのコミットであることを証明する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取る。
  • S*が停止したら、そのsimulated view を出力する。

Claim 1 Hyb1 ≡c Real.
  • fmsg が j についてfreshなとき、Realにおいて、Fの擬似ランダム性よりωR*はfreshなランダム文字列と識別不可能。よって、Hyb1のシミュレートとRealのシミュレートはS*にとって識別不可能。
  • fmsg が j について、freshでないとき:
    • Realにおいて、the random tape ωR* = FωRj(fmsg) used by R(j) is the same as the one used in the past session between S* and R(j) that shares the first message fmsg. So, c2, r2 are replays of the ones sent in that session. Consider the messages belonging to the first zero-knowledge argument:
      • The common input of the argument is (c1, r1).
      • c1 must be a repaly since it is included in fmsg.
      • r1 must be also a replay by the binding property of Com and the resettably-soundness of the first argument.
      • Then, all of the messages in the first argument must be replays, by the soundness of the attached ZAPs. (Note that ZAPs are always resettably-sound.) Note that since x not∈ L, the messages from S* must be computed using ωS that is bound by cS in fmsg.
    • Similarly, we can see that all of the messages in the second zero-knowledge argumet also must be replays. Thus, we know that the above simulation by Hyb1 that replays the transcript of the corresponding past session is indistingusihable from Real also in the case of non-fresh fmsg □

Hyb2 :
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、それがjについてfreshか否かをチェック:
      • fresh でないならば、fmsgを共有する、対応する過去のトランスクリプトからR(j)のメッセージを取り出して再送することでシミュレートを行う。
      • 以下、fmsg は freshであると仮定する。
    • freshなランダムテープ ω* を生成する。以下、R(j)のシミュレーションにはランダムテープω* を用いる。
    • 長さn2のランダム文字列r2を選択し、それにコミットする:c2 ← Com(r2). c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • r2をS*に返す。
      • さらに、the ZKA のシミュレータMを用いて、c2がr2へのコミットであることを``証明''する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取る。
  • S*が停止したら、そのsimulated view を出力する。

In Hyb2, note that the statements (c2, r2) that the simulator M must prove are randomly generated every time M is invoked. So, by standard hybrid argument around the stand-alone ZK property of the second argument, we see :

Claim 2 Hyb2 ≡c Hyb1.

Hyb3 :
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、それがjについてfreshか否かをチェック:
      • fresh でないならば、fmsgを共有する、対応する過去のトランスクリプトからR(j)のメッセージを取り出して再送することでシミュレートを行う。
      • 以下、fmsg は freshであると仮定する。
    • freshなランダムテープ ω* を生成する。以下、R(j)のシミュレーションにはランダムテープω* を用いる。
    • ダミー文字列0n2にコミットする:c2 ← Com(0n2). c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • 長さn2のランダム文字列r2を選択する。r2をS*に返す。
      • さらに、the ZKA のシミュレータMを用いて、c2がr2へのコミットであることを``証明''する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取る。
  • S*が停止したら、そのsimulated view を出力する。

As easily shown, hiding property of Com means :

Claim 3 Hyb3 ≡c Hyb2.

Hyb4 :
  • t 個のランダムテープ ωR1,...,ωRt を選択し、j∈[t]について、R(j) := R(ωRj) とする。
  • S*を起動する。
  • S*が呼び出す各インカーネーションR(j)を以下のようにシミュレート:
    • S*より その第1メッセージ fmsg =(x, f, c1, cS, σS) を受け取ったら、それがjについてfreshか否かをチェック:
      • fresh でないならば、fmsgを共有する、対応する過去のトランスクリプトからR(j)のメッセージを取り出して再送することでシミュレートを行う。
      • 以下、fmsg は freshであると仮定する。
    • freshなランダムテープ ω* を生成する。以下、R(j)のシミュレーションにはランダムテープω* を用いる。
    • ダミー文字列0n2にコミットする:c2 ← Com(0n2). c2をS*に返す。
    • S*より r1 およびそれに続くconvincingなZKAを受けたら(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)、
      • 長さn2のランダム文字列s = s1, ... , sn を選択する。i = 1 to n について ri = f(si)を計算し、r = r1, ... , rnについて r2 = r + r1 をS*に返す。
      • さらに、the ZKA のシミュレータMを用いて、c2がr2へのコミットであることを``証明''する。(このとき、S*から受け取る各メッセージに付随するZAPが一つでもinvalidならアボートする。)
    • S*より、v1+h(s1), ... , vn+h(sn)を受け取る。
  • S*が停止したら、そのsimulated view を出力する。

Obviously, we have

Claim 4 Hyb4 ≡ Hyb3.

Now it is immediate that the simulation in Hyb4 gives the claimed resettable-extractor of the proposed commitment. Note that in Hyb4 we can extract the values committed under final commitments C using the knowledge of s = f-1(r). That completes the proof.

Deng-Goyal-Sahai のtransformation [DGS 09]

  • [部品] :
    • 疑似ランダム関数 fs
    • a non-interactive commitment scheme Com
    • a constant-round resettably-sound ZK argument
    • a concurrent ZK, resettably-sound argument
    • a rZAP
  • [Pの入力] : (x, w), ランダムテープRP = (RP,1, RP,2, RP,3)
  • [Vの入力] : x, ランダムテープRV = (RV,1, RV,2, RV,3)
  • [プロトコル]
  • 第1フェーズ:ランダムテープとして P は RP,1 を V は RV,1 を用いる。
    • P → V : σP ← the 1st msg of the rZAP, cP ← Com(RP,2), send σP, cP.
    • P ← V : σV ← the 1st msg of the rZAP, trap ← Com(0), send σV, trap.
  • 第2フェーズ:ランダムテープとして P は RP,2 を V は RV,2 を用いる。
    • P ←= V : the rs ZKA : 『 ∃r, trap = Com(0;r). 』
      • with rZAP : 『msg の計算に RP,2 を用いた OR x ∈ L』 for each prover-message
      • ランダムテープとして、VはRV,2* = fRV,2(cP)を用いる。
  • 第3フェーズ:ランダムテープとして P は RP,3 を V は RV,3 を用いる。
    • P ← V : cV ← Com(RV,3), send cV.
    • P ⇒ V : the cZK, rs Arg : 『x ∈ L. 』
      • with rZAP : 『msgの計算にRV,3を用いた OR trapは1へのコミットメント』 for each verifier-message
      • ランダムテープとして、PはRP,3* = fRP,3(cV)を用いる。


文献

  • [Barak 01] Boaz Barak, ``How to Go Beyond the Black-Box Simulation Barrier'', In 42nd FOCS, pp. 106-115, 2001.
  • [Barak 04] Boaz Barak, ``Non-Black-Box Techniques in Cryptography'', Thesis for the PH.D. Degree, The Weizmann Instutite of Science, 2004.
  • [BGGL 01] B. Barak and O. Goldreich and S. Goldwasser and Y. Lindell, ``Resettably-Sound Zero-Knowledge and its Applications," FOCS 2001, IEEE Computer Society, 2001.
  • [CGGM 00] Ran Canetti, Oded Goldreich, Shafi Goldwasser, and Silvio Micali, ``Resettable zero-knowledge," In STOC, pages 235-244, 2000.
  • [DGS 09] Yi Deng, Vipul Goyal, Amit Sahai, ``Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy," FOCS 09, pp. 251-260, 2009.
  • [DL 08] Yi Deng and Dongdai Lin, ``Resettable Zero Knowledge with Concurrent Soundness in the Bare Public-Key Model under Standard Assumption," Inscrypt 2007, LNCS 4990, pp. 123-137, 2008.
  • [DN 00] Cynthia Dwork and Moni Naor, ``Zaps and their applications,'' in FOCS, pp. 283-293, 2000.
  • [KP 01], Joe Kilian and Erez Petrank, ``Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds," STOC 01, 560-569, 2001.





















最終更新:2010年12月10日 20:28