[BD20] 2 Preliminaries

Mihir Bellare and Wei Dai INDOCRYPT 2020

發表於 2026-04-09 更新於 2026-04-14 square-root-barrier paper MBDL

It is chapter 2 of the paper BD20. Other chapters include:

Notation

If $n$ is a positive integer, then
- $\mathbb{Z}_n$ denotes the set $\set{0, \ldots, n-1}$,
- $[n]$ or $[1..n]$ denote the set $\set{1, \ldots, n}$.
Denote the number of coordinates of a vector $x$ by $\lvert x\rvert$. If $x$ is a vector, then
- $\lvert x\rvert$ denotes its length, the number of coordinates of $x$,
- $x[i]$ denotes the $i$-th coordinate of $x$,
- $[x] = {x[i]: 1 \le i \le \lvert x\rvert}$ denotes the set of all coordinates.
A string is identified with a vector over $\set{0, 1}$. If $x$ is a string, then
- $x[i]$ denotes its $i$-th bit,
- $\lvert x\rvert$ denotes its length.
Denote the empty vector or empty string by $\varepsilon$.
The size of a set $S$ is denoted by $\lvert S\rvert$.
For sets $D,R$, denote the set of all functions $f:D\to R$ by $\mathrm{FNS}(D,R)$.

Let $S$ be a finite set.
Let $x \xleftarrow{$} S$ denote sampling an element uniformly at random from $S$ and assigning it to $x$.
Let $y \leftarrow A^{O_1,\ldots}(x_1,\ldots; r)$ denote executing algorithm $A$ with input $x_1,\ldots$, random coins $r$, and oracle access to $O_1,\ldots$, and assigning the output to $y$.
Let $y \xleftarrow{$} A^{O_1,\ldots}(x_1,\ldots)$ denote the resulting of picking $r$ at random and letting $y \leftarrow A^{O_1,\ldots}(x_1,\ldots; r)$.
Let $[A^{O_1,\ldots}(x_1,\ldots)]$ denote the set of all possible outputs of $A$ when invoked with inputs $x_1,\ldots$ and oracle access to $O_1,\ldots$.

Note Algorithms are randomized unless otherwise indicated. Running time is worst case.

Note 使用文獻 BR06 的 code-based game playing framework。

一個 game 具有若干 procedures，也稱為 oracles。其中包括 Init 與 Fin。
在以 game $\mathrm{Gm}$ 執行 adversary $\mathcal{A}$ 時
1. 首先執行 procedure Init，其回傳值作為 $\mathcal{A}$ 的輸入。
2. 之後，$\mathcal{A}$ 可以呼叫除了 Init、Fin 之外的所有 game procedures。
3. 當 adversary 終止時，其輸出被視為 Fin 的輸入，而 Fin 的回傳值即為 game 的輸出。
Event: $\Pr[\mathrm{Gm}(\mathcal{A})]$ 表示 game $\mathrm{Gm}$ 與 adversary $\mathcal{A}$ 一起執行後輸出為 true 的事件。
Initialization: 在撰寫 game 或 adversary 的 pseudocode 時，預設
- boolean variables 初始化為 false
- integer variables 初始化為 $0$
- set-valued variables 初始化為空集合 $\emptyset$
Time: 當 adversary $\mathcal{A}$ 與 game $\mathrm{Gm}$ 一起執行時，adversary 的執行時間記為 $T_{\mathcal{A}}$，並假設 game procedures 的回應時間皆為單位時間。
Oracle: $Q_{\mathcal{A}}^O$ 表示在該次執行中，$\mathcal{A}$ 對 oracle $O$ 所做的查詢次數。

Note These counts are all worst case.

This is game defining $\mathrm{IMP-PA}$ security of $\mathrm{ID}$.

Game $G^{\mathrm{imp\text{-}pa}}_{\mathrm{ID}}$

Init:

Tr:

Ch($R_\ast$):// One query

Fin($z_\ast$):

Let $\mathrm{G}$ be a group of order $p$.
Use multiplicative notation for the group operation.
Let $1_{\mathrm{G}}$ denote the identity element of $\mathrm{G}$.
Let $\mathrm{G}^* = \mathrm{G} \setminus {1_{\mathrm{G}}}$ denote the set of non-identity elements, which is the set of generators of $\mathrm{G}$ if $\mathrm{G}$ is of prime order.
If $g \in \mathrm{G}^*$ is a generator and $X \in \mathrm{G}$,
- then the discrete logarithm of $X$ with respect to the base $g$ is denoted by $\mathrm{DL}{\mathrm{G},g}(X)$, and it belongs to the set $\mathbb{Z}{\lvert G\rvert}$.

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.
BR06 M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based gameplaying proofs. In S. Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 409–426. Springer, Heidelberg, May / June 2006.