[BD20] 4.1 Schnorr Identification from MBDL
This note is subchapter 4.1 of chapter 4 Schnorr Identification and Signatures from MBDL in the paperBD20. The companion subchapter is 4.2 Schnorr Signature from MBDL. 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
Canonical identification scheme
本文先回顧 canonical identification scheme 的抽象定義。
一個 identification scheme 可以寫成
$ID = (\mathrm{Kg}, \mathrm{Cmt}, \mathrm{Rsp}, \mathrm{Vf}, \mathrm{Ch})$，
分別對應金鑰產生、承諾生成、回應生成、驗證，以及挑戰空間。
- $\mathrm{Kg}$ 是 key-generation algorithm，輸出 verification key 與對應的 secret key。
- $\mathrm{Cmt}$ 是 commitment-generation algorithm，輸入 verification key，輸出 commitment $R$ 與內部狀態 $st$。
- $\mathrm{Rsp}$ 是 response-generation algorithm，輸入 secret key、challenge 與 state，輸出 response。
- $\mathrm{Vf}$ 是 deterministic verification algorithm，輸入 verification key、commitment、challenge、response，輸出 accept 或 reject。
- $\mathrm{Ch}$ 是 challenge space。
correctness 的意思是：若 $(vk, sk)$ 由 $\mathrm{Kg}$ 產生，$(R, st)$ 由 $\mathrm{Cmt}(vk)$ 產生，$c$ 從 $\mathrm{Ch}$ 取樣，且 $z \gets \mathrm{Rsp}(sk, c, st)$， 那麼 $\mathrm{Vf}(vk, R, c, z)$ 應該接受。
IMP-PA game
Schnorr identification 的安全性以 IMP-PA（impersonation under passive attack）來描述。
攻擊者先透過 transcript oracle 取得 honest transcripts，之後再嘗試做一次 impersonation：先輸出 commitment $R^*$，收到 challenge $c^*$ 之後，再輸出 response $z^*$。若
$\mathrm{Vf}(vk, R^*, c^*, z^*)$
接受，則攻擊成功。
其 advantage 定義為 \(Adv^{\mathrm{imp\text{-}pa}}_{ID}(A) = \Pr\big[ G^{\mathrm{imp\text{-}pa}}_{ID}(A) \Rightarrow 1 \big].\)
Schnorr identification scheme
令 $G$ 是一個 prime-order group，$p = \lvert G \rvert$，且 $g \in G^\ast$ 是生成元。
Schnorr identification scheme 記為
$ID = \mathrm{SchID}[G, g]$。
secret key 取為 $x \gets \mathbb{Z}_p$，對應的 public key 是 \(X = g^x .\)
一次誠實執行中，prover 先取 $r \gets \mathbb{Z}_p$，計算 \(R = g^r .\) verifier 再送出 challenge \(c \gets \mathbb{Z}_p .\) prover 回傳 \(z = r + cx \bmod p .\) 最後 verifier 檢查 \(g^z = R X^c .\)
Prior result
對 Schnorr identification，先前已知的 DL-based bound 是 \(Adv^{\mathrm{imp\text{-}pa}}_{ID}(A) \le \sqrt{Adv^{\mathrm{dl}}_{G,g}(B)} + \frac{1}{p}. \tag{7}\)
這個 bound 帶有典型的 square-root loss，對應的 proof 依賴 rewinding reduction。
chapter 4 的主要目標，就是把這種鬆的 reduction 改成從 1-MBDL 出發的 tight reduction。
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.