[BD20] Proof of Theorem 4.1
This note records the proof page for Theorem 4.1 in chapter 4 of the paperBD20. Related chapters include:
- 1 Introduction
- 2 Preliminaries
- 3 The Multi-Base Discrete Logarithm Problem
- 4 Schnorr Identification and Signatures from MBDL
- 5 MBDL hardness in the Generic Group Model
- A Okamoto Identification and Signature from MBDL
- B Ratio-based tightness
Theorem 4.1
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}. $$ 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}. $$ Additionally, $T_{\mathcal{B}}$ is roughly $T_{\mathcal{A}}$ plus simulation overhead $\mathcal{O} (Q^{Tr}_{\mathcal{A}} \cdot T^{\mathrm{exp}}_\mathbb{G})$.
Proof of Theorem 4.1
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.