Security of DL-based Signature
數位簽章安全性的證明，在 random oracle model 中常透過 forking lemma 來進行。其核心想法是：若一個 adversary 能在某個 hash-query 的回答下產生合法 forgery，則 reduction 可以在相同 random tape 下重跑 adversary，並只改動那個關鍵 hash-query 的回覆，從而得到兩個彼此相關、但 challenge 不同的偽造簽章。接著再利用這兩份輸出之間的代數關係，恢復底層 hard problem 的解。
對離散對數型簽章而言，這種方法並不是一體適用。Schnorr signatures 中，forking 後會保留相同的 commitment，因此可直接解出 secret key；DSA 中則因為 reduction modulo $q$ 的存在，無法從相同的 $r$ 推回相同的 ephemeral key；EC-DSA 也有類似障礙，但在某些額外條件下可以部分修補。當 adversary 由 passive 升級為 active 時，關鍵則變成：reduction 能否在不知道私鑰的情況下，模擬 signing oracle。
Forking Lemma
在這裡考慮的簽章方案中，簽章通常可以抽象寫成下列形式，SIGNER 動作如下：
- 產生一個可能為空的 commitment $\sigma_1$
- 再計算 $h = H(\sigma_1 | m)$
- 最後利用 $\sigma_1$ 與 $h$ 算出第二部分 $\sigma_2$
因此輸出可記為 $(\sigma_1, H(\sigma_1 | m), \sigma_2)$。
- DSA: $\sigma_1 = \emptyset$, $h = H(m)$, $$\sigma_2 = \left(r,\frac{h+xr}{k} \bmod q\right),$$ where $r = (g^k \bmod p) \bmod q$
- EC-DSA: $\sigma_1 = \emptyset$, $h = H(m)$, $$\sigma_2 = \left(r,\frac{h+xr}{k} \bmod q\right),$$ where $r = x\text{-coord}([k]G)$
- Schnorr signatures: $\sigma_1 = g^k$, $h = H(\sigma_1 \| m)$, $$\sigma_2 = xh + k \bmod q.$$
在 random oracle model 中，reduction $B^A$ 可以控制 hash oracle 的回答。若 adversary $A$ 能以 non-negligible probability 產生 existential forgery，則可假設它一定曾查詢過關鍵的 hash 值 $h = H(\sigma_1 | m)$；否則 reduction 可以代為補查，不影響分析。
forking lemma 的操作是：讓 $A$ 在相同 random tape 下執行兩次。第一次正常回答所有 hash queries；第二次則挑某一個 hash query，將其回答改成另一個值。若剛好被改動的是 critical hash query，則兩次執行會得到同一訊息上的兩份 forgery： \((m,\sigma_1,h,\sigma_2), \qquad (m,\sigma_1,h',\sigma_2').\) 兩份輸出之間唯一關鍵的差異，在於 hash challenge 由 $h$ 變成 $h’$。接下來是否能把這兩份簽章轉化為底層 hard problem 的解，就取決於 scheme 本身的代數結構。
Passive Adversary
Passive Adversary 只觀察 public key、hash oracle，以及可能的公開資訊，不具備額外的 signing oracle 互動能力。
Schnorr Signature (Passive Adversary)
Schnorr signature 的公開金鑰寫作 $y=g^x$。對訊息 $m$，簽章者隨機選取 $k$，令
\[r = g^k, \qquad h = H(r \| m), \qquad s = xh + k \pmod q.\]因此簽章可寫為 $(h,s)$，驗證條件則可重寫成 $g^s = y^h r$。
Schnorr 的關鍵，在於 fork 後保留下來的是同一個 commitment $g^k$。一旦 commitment 相同，就能推出兩次用到的是同一個 $k$，因而把未知量只剩下 $x$，最終直接解出 discrete logarithm。
DSA Signature
DSA 的簽章形式為
\[r = (g^k \bmod p) \bmod q, \qquad s = \frac{h+xr}{k} \pmod q,\]其中 $h = H(m)$。若照著 Schnorr 的思路對 DSA 使用 forking lemma，則會得到兩份簽章：
\[(m,\emptyset,h,(r,s))\]與
\[(m,\emptyset,h',(r',s')).\]對應的方程式為
\[r = (g^k \bmod p)\bmod q, \qquad s = \frac{h+xr}{k} \pmod q,\] \[r' = (g^{k'} \bmod p)\bmod q, \qquad s' = \frac{h'+xr'}{k'} \pmod q.\]這裡的問題在於：和 Schnorr 不同，fork 後並沒有明確保留下某個能唯一決定 $k$ 的 group element。特別是，連 $r=r’$ 都不一定成立，因此完全無法推出 $k=k’$。少了這一步，就不能把兩條方程式相減來消去 $k$。
即使進一步修改 DSA，把 hash 改成
\[h = H(m \| r),\]使它更像 Schnorr 的結構，fork 後可以保證兩次 critical hash query 都對應同一個 $r$，仍然只會得到
\[r = r',\]以及
\[r = (g^k \bmod p)\bmod q, \qquad r' = (g^{k'} \bmod p)\bmod q.\]但從
\[(g^k \bmod p)\bmod q = (g^{k'} \bmod p)\bmod q\]仍然無法推出
\[k = k'.\]障礙就在於最後那個 reduction modulo $q$：它把原本群元素中的資訊壓縮掉了。若沒有這一步 reduction，理論上就比較有機會走出像 Schnorr 那樣的 proof；但 DSA 正是靠這個設計才保有較小的 signature size。因此，DSA 的效率特性也正是這種 reduction proof 卡住的來源。
對 DSA 而言，這套 proof technique 不適用，而且目前也沒有已知的安全性證明可由這條路線建立。
EC-DSA Signature
EC-DSA 的簽章形式與 DSA 類似，只是把 multiplicative group 換成 elliptic curve group。對修改後的版本，假設
\[h = H(m \| r),\]其中
\[r = x\text{-coord}([k]P) \bmod q,\]簽章方程式為
\[s = \frac{h+xr}{k} \pmod q.\]fork 後得到兩份簽章資料：
\[r = x\text{-coord}([k]P) \bmod q, \qquad s = \frac{h+xr}{k} \pmod q,\] \[r' = x\text{-coord}([k']P) \bmod q, \qquad s' = \frac{h'+xr'}{k'} \pmod q,\]其中還有
\[r = r'.\]和 DSA 不同的是，在某些條件下，從相同的 $x$-coordinate 可以推出
\[[k']P = [k]P \quad \text{or} \quad [k']P = -[k]P.\]因此可得
\[k' \equiv k \pmod q \qquad \text{or} \qquad k' \equiv -k \pmod q.\]也就是
\[k' = \pm k \pmod q.\]把這兩種可能分開看。
若 $k’ = k$，則
\[s = \frac{h+xr}{k}, \qquad s' = \frac{h'+xr}{k}.\]兩式相減可得
\[s-s' = \frac{h-h'}{k} \pmod q,\]因此
\[(s-s')k = h-h' \pmod q.\]若 $k’ = -k$，則
\[s' = \frac{h'+xr}{-k} = -\frac{h'+xr}{k} \pmod q.\]因此
\[s+s' = \frac{h-h'}{k} \pmod q,\]亦即
\[(s+s')k = h-h' \pmod q.\]這兩種情形可統一寫成
\[(s \mp s')k = h-h' \pmod q.\]因此 reduction 可以得到 兩個候選值：
\[k = \frac{h-h'}{\,s-s'\,} \pmod q \qquad \text{or} \qquad k = \frac{h-h'}{\,s+s'\,} \pmod q.\]一旦得到候選的 $k$，就可由
\[s = \frac{h+xr}{k} \pmod q\]改寫為
\[x = \frac{sk-h}{r} \pmod q.\]因此對每個候選的 $k$，都可算出對應的候選 secret key
\[x = (sk-h)r^{-1} \pmod q.\]最後再檢查哪一個滿足
\[[x]P = Y.\]這裡與 DSA 最本質的差別是：在 elliptic curve 上，相同的 $x$-coordinate 至多對應到兩個互為相反數的點，因此雖然不能唯一恢復 $k$，但仍可以把候選數量壓到 2 個，最後再檢查公開金鑰即可。這也是修改版 EC-DSA 在特定條件下能建立 passive security 的原因。
Active Adversary
一旦 adversary 可以發出 signing queries，reduction 不只要處理最終 forgery，還必須在不知道私鑰的情況下，回答對方的簽章請求。這一步稱為 simulation of signing queries。
若 hash function 只吃訊息 $m$，則 adversary 可能在要求簽章之前，就先查過 $H(m)$。這樣 reduction 之後便無法再修改這個 hash 回應，也就無法自由地構造模擬簽章。這也是 Schnorr 這類方案中，hash 輸入要包含像 $\sigma_1$ 這樣直到簽章當下才決定之值的原因。
因此，在 random oracle model 中，只要能成功模擬 signing oracle，active attack 所需的互動便可被 reduction 重現，安全性分析也就能延續 passive case 的思路。
Schnorr Signature (Active Adversary)
Schnorr 的真實簽章為：對訊息 $m$，選隨機 $k$，令 \(r = g^k, \qquad h = H(r \| m), \qquad s = xh + k \pmod q.\) 輸出 $(h,s)$。
模擬器在不知道 $x$ 的情況下，改成反過來做：
- 隨機選 $s,h \in \mathbb F_q$；
- 設 \(r = g^s y^{-h};\)
- 若之前的 random-oracle list 中已存在 $(r | m,h’)$ 且 $h’ \ne h$，則重選；
- 將 hash oracle 編程為 \(H(r \| m) = h;\)
- 輸出「簽章」$(h,s)$。
現在驗證這確實是一份合法 Schnorr signature。因為公開金鑰為 $y=g^x$，所以 \(r = g^s y^{-h} = g^s g^{-xh} = g^{s-xh}.\) 因此若令 \(k = s-xh \pmod q,\) 就有 \(r = g^k.\) 而且 \(s = xh + k \pmod q.\) 這正是 Schnorr signature 的正確關係式，所以 $(h,s)$ 的分佈與真實簽章一致。
重點在於：模擬器不是先選 $k$ 再算 $s$，而是先隨機選出最終要輸出的 $(h,s)$，再反推出對應的 $r$，最後把 random oracle 在 $(r | m)$ 上的值程式化成 $h$。這種作法之所以可行，正是因為在 random oracle model 中，reduction 可以控制 hash oracle 的回答。
Schnorr 在 active case 中依然可證，最核心的原因就是：其 hash 輸入包含 $r$，而 $r$ 又可以先由 simulator 反推構造，再把 oracle 回答補上。若 hash 只依賴 $m$，這種 simulation 通常就做不到。對 DSA 而言，並不存在相同型態的安全結論；EC-DSA 的已知證明方向也不是這裡這種將 hash 當作 generic object 再歸約到 discrete logarithm 的路線。
References
- Nigel P. Smart, Cryptography: An Introduction (3rd ed.), Chapter 20. PDF