[BD20] 4 Schnorr Identification and Signatures from MBDL
It is chapter 4 of the paperBD20. Other chapters include:
- 1 Introduction
- 2 Preliminaries
- 3 The Multi-Base Discrete Logarithm Problem
- 5 MBDL hardness in the Generic Group Model
- A Okamoto Identification and Signature from MBDL
- B Ratio-based tightness
Identification Schemes and the IMP-PA Game
See 4.1 Schnorr Identification from MBDL.
Tight Reduction from Schnorr Identification to 1-MBDL
Theorem 4.1
Let $\mathbb{G}$ be a group of prime order $p = \lvert \mathbb{G} \rvert$ and $g \in \mathbb{G}^\ast$ be a generator of $\mathbb{G}$.
Let $\mathrm{ID} = \mathrm{SchID}[\mathbb{G}, g]$ be the Schnorr identification scheme.
Let $\mathcal{A}$ be an adversary attacking the imp-pa security of $\mathrm{ID}$.
Then we can construct an adversary $\mathcal{B}$ such that $$ \mathbf{Adv}^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}(\mathcal{A}) \le \mathbf{Adv}^{\mathrm{mbdl}}_{\mathbb{G},g,1}(\mathcal{B}) + \frac{1}{p}. \tag{8} $$ Additionally, $T_{\mathcal{B}}$ is roughly $T_{\mathcal{A}}$ plus simulation overhead $\mathcal{O} (Q^{Tr}_{\mathcal{A}} \cdot T^{\mathrm{exp}}_\mathbb{G})$.
Let $\mathrm{ID} = \mathrm{SchID}[\mathbb{G}, g]$ be the Schnorr identification scheme.
Let $\mathcal{A}$ be an adversary attacking the imp-pa security of $\mathrm{ID}$.
Then we can construct an adversary $\mathcal{B}$ such that $$ \mathbf{Adv}^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}(\mathcal{A}) \le \mathbf{Adv}^{\mathrm{mbdl}}_{\mathbb{G},g,1}(\mathcal{B}) + \frac{1}{p}. \tag{8} $$ Additionally, $T_{\mathcal{B}}$ is roughly $T_{\mathcal{A}}$ plus simulation overhead $\mathcal{O} (Q^{Tr}_{\mathcal{A}} \cdot T^{\mathrm{exp}}_\mathbb{G})$.
Adversary $\mathcal{B}$
Adversary $\mathcal{B}^{\mathrm{DLO}}$
Init:
-
Set$(Y, X) \xleftarrow{\$} \mathrm{Init}()$ -
Run$z^\ast \xleftarrow{\$} \mathcal{A}^{\mathrm{Ch}, \mathrm{Tr}}(X)$ -
Return$z^\ast$
Ch($R^\ast$):
-
Set$W \leftarrow (R^\ast)^{-1} \cdot Y$ -
Set$c^\ast \leftarrow \mathrm{DLO}(1, W)$ -
Return$c^\ast$
Tr:
-
Set$z \xleftarrow{\$} \mathbb{Z}_p$ -
Set$c \xleftarrow{\$} \mathbb{Z}_p$ -
Set$R \leftarrow g^z \cdot X^{-c}$ -
Return$(R, c, z)$
Proof of Theorem 4.1
See Proof of Theorem 4.1.
Quantitative Comparison for 4.1
See Quantitative Comparison for 4.1.
Signature Schemes and the Transfer from IMP-PA to UF
See 4.2 Schnorr Signature from MBDL.
Lemma 4.2 [1]
Let $\mathbb{G}$ be a group of prime order $p = \lvert \mathbb{G} \rvert$ and $g \in \mathbb{G}^\ast$ be a generator of $\mathbb{G}$.
Let $\mathrm{ID} = \mathrm{SchID}[\mathbb{G}, g]$ and $\mathrm{DS} = \mathrm{SchSig}[\mathbb{G}, g]$ be the Schnorr identification and signature schemes, respectively.
Let $\mathcal{A}_{\mathrm{ds}}$ be an adversary attacking the uf-security of $\mathrm{DS}$. Let $$ \alpha = (1 + Q^{\mathrm{H}}_{\mathcal{A}_{\mathrm{ds}}} + Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}}) \cdot Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}} . $$ Then we can construct an adversary $\mathcal{A}_{\mathrm{id}}$ such that $$ \mathbf{Adv}^{\mathrm{uf}}_{DS}(\mathcal{A}_{\mathrm{ds}}) \le (1 + Q^{\mathrm{H}}_{\mathcal{A}_{\mathrm{ds}}}) \cdot \mathbf{Adv}^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}(\mathcal{A}_{\mathrm{id}}) + \frac{\alpha}{p}. $$ Additionally, $T_{\mathcal{A}_{\mathrm{id}}} \approx T_{\mathcal{A}_{\mathrm{ds}}}$ and $Q^{\mathrm{Tr}}_{\mathcal{A}_{\mathrm{id}}} = Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}}$.
Let $\mathrm{ID} = \mathrm{SchID}[\mathbb{G}, g]$ and $\mathrm{DS} = \mathrm{SchSig}[\mathbb{G}, g]$ be the Schnorr identification and signature schemes, respectively.
Let $\mathcal{A}_{\mathrm{ds}}$ be an adversary attacking the uf-security of $\mathrm{DS}$. Let $$ \alpha = (1 + Q^{\mathrm{H}}_{\mathcal{A}_{\mathrm{ds}}} + Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}}) \cdot Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}} . $$ Then we can construct an adversary $\mathcal{A}_{\mathrm{id}}$ such that $$ \mathbf{Adv}^{\mathrm{uf}}_{DS}(\mathcal{A}_{\mathrm{ds}}) \le (1 + Q^{\mathrm{H}}_{\mathcal{A}_{\mathrm{ds}}}) \cdot \mathbf{Adv}^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}(\mathcal{A}_{\mathrm{id}}) + \frac{\alpha}{p}. $$ Additionally, $T_{\mathcal{A}_{\mathrm{id}}} \approx T_{\mathcal{A}_{\mathrm{ds}}}$ and $Q^{\mathrm{Tr}}_{\mathcal{A}_{\mathrm{id}}} = Q^{\mathrm{SIGN}}_{\mathcal{A}_{\mathrm{ds}}}$.
Improved Bound for Schnorr Signatures from 1-MBDL
將 Theorem 4.1 與 Lemma 4.2 結合後，可直接得到 Schnorr signatures 的新界。
Theorem 4.3
Let $\mathbb{G}$ be a group of prime order $p = \lvert \mathbb{G} \rvert$ and $g \in \mathbb{G}^\ast$ be a generator of $\mathbb{G}$.
Let $\mathrm{DS} = \mathrm{SchSig}[\mathbb{G}, g]$ be the Schnorr signature scheme.
Let $\mathcal{A}$ be an adversary attacking the uf security of $\mathrm{DS}$.
Let $$ \beta = (1 + Q^{\mathrm{H}}_{\mathcal{A}} + Q^{\mathrm{SIGN}}_{\mathcal{A}}) Q^{\mathrm{SIGN}}_{\mathcal{A}} + (1 + Q^{\mathrm{H}}_{\mathcal{A}}). $$ Then we can construct an adversary $\mathcal{B}$ such that $$ \mathbf{Adv}^{\mathrm{uf}}_{\mathrm{DS}}(\mathcal{A}) \le (1 + Q^{\mathrm{H}}_{\mathcal{A}}) \cdot \mathbf{Adv}^{\mathrm{mbdl}}_{\mathbb{G},g,1}(\mathcal{B}) + \frac{\beta}{p}. \tag{13} $$ Additionally, $T_{\mathcal{B}}$ is roughly $T_{\mathcal{A}}$ plus simulation overhead $\mathcal{O} (Q^{\mathrm{SIGN}}_{\mathcal{A}} \cdot T^{\mathrm{exp}}_{\mathbb{G}})$.
Let $\mathrm{DS} = \mathrm{SchSig}[\mathbb{G}, g]$ be the Schnorr signature scheme.
Let $\mathcal{A}$ be an adversary attacking the uf security of $\mathrm{DS}$.
Let $$ \beta = (1 + Q^{\mathrm{H}}_{\mathcal{A}} + Q^{\mathrm{SIGN}}_{\mathcal{A}}) Q^{\mathrm{SIGN}}_{\mathcal{A}} + (1 + Q^{\mathrm{H}}_{\mathcal{A}}). $$ Then we can construct an adversary $\mathcal{B}$ such that $$ \mathbf{Adv}^{\mathrm{uf}}_{\mathrm{DS}}(\mathcal{A}) \le (1 + Q^{\mathrm{H}}_{\mathcal{A}}) \cdot \mathbf{Adv}^{\mathrm{mbdl}}_{\mathbb{G},g,1}(\mathcal{B}) + \frac{\beta}{p}. \tag{13} $$ Additionally, $T_{\mathcal{B}}$ is roughly $T_{\mathcal{A}}$ plus simulation overhead $\mathcal{O} (Q^{\mathrm{SIGN}}_{\mathcal{A}} \cdot T^{\mathrm{exp}}_{\mathbb{G}})$.
Comparison with prior bounds
Prior bound via Lemma 4.2 and equation (7)
\[\mathbf{Adv}^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}(\mathcal{A}) \le \sqrt{\mathbf{Adv}^{\mathrm{dl}}_{\mathbb{G}, g}(\mathcal{B})} + \frac{1}{p} \tag{7}\]一個從 DL 證明 $DS$ 的 UF-security 的簡單方法，是把 Lemma 4.2 與式 (7) 所給出的、基於 DL 的經典 identification security 結合起來。
對於一個攻擊 $DS$ 之 UF security 的 adversary $A$，這會導出一個 discrete-log adversary $B$，使得
其中 $\beta$ 如 Theorem 4.3 所定，而 $T_B$ 大約是 $2T_A$，再加上與前述相同的 simulation overhead。
Prior bound via the general Forking Lemma
透過如 PS00 那樣，直接套用 BN06 的 general Forking Lemma，可以得到更好的結果。
對於一個攻擊 $DS$ 之 UF security 的 adversary $A$，這會導出一個 discrete-log adversary $B$，使得
其中 $\beta$ 與 $T_B$ 與前面相同。
式 (15) 比式 (14) 更好的原因，在於 $1 + Q_A^H$ 這一項被移到了平方根之內。
儘管如此，仍可看出式 (13) 更佳；大致上（忽略 additive term），式 (13) 中的界是式 (15) 中那個界的平方，因此也就總是更小。
Quantitative Comparison for 4.3
See Quantitative Comparison for 4.3.
References
- BD20 M. Bellare and W. Dai. The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures. In Progress in Cryptology-INDOCRYPT '20, pages 529-552, 2020.
- BN06 M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In A. Juels, R. N. Wright, and S. De Capitani di Vimercati, editors, ACM CCS 2006, pages 390-399. ACM Press, Oct./Nov. 2006.
- PS00 D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361-396, June 2000.