[BD20] 3 The Multi-Base Discrete Logarithm Problem

Mihir Bellare and Wei Dai INDOCRYPT 2020
發表於 2026-04-09 更新於 2026-04-15 square-root-barrier paper MBDL

It is chapter 3 of the paperBD20. Other chapters include:

Multi-Base Discrete Logarithm（MBDL）Problem 是 One-More Discrete Logarithm（OMDL）問題的一個變形。BNPS03

Fix a cyclic group $\mathrm{G}$ and generator $g$ of $\mathrm{G}$.

在 MBDL 中，攻擊者會得到

  • a challenge $Y \in \mathrm{G}$
  • a list generators $X_1, X_2, \dots, X_n \in \mathrm{G}^*$ of generators of $\mathrm{G}$
  • an oracle $\mathrm{DLO}$
    • the oracle, on input $(i, W)$, returns $\mathrm{DL}_{\mathrm{G}, X_i}(W)$
    • $\mathrm{DL}_{\mathrm{G}, X_i}(W)$ is the discrete logarithm of $W$ with respect to the base $X_i$, rather than the base $g$.

攻擊者若要獲勝，必須輸出 $\mathrm{DL}_{\mathrm{G}, g}(Y)$，也就是 the discrete logarithm of $Y$ with respect to the base $g$，同時整體 make at most one call to $\mathrm{DLO}$。 也就是說，它至多只能對一個 group element 求一次離散對數，不過這個 element 以及所選的 base $X_i$，都可以自行決定。

The number of bases $n$ 是問題的一個參數，因此可以稱為 $n$-MBDL problem or assumption。這篇論文的結果實際上只會依賴 $1$-MBDL，但仍保留一般形式的定義，以供未來可能的應用。

要求至多只能呼叫一次 $\mathrm{DLO}$ is necessary。因為如果允許兩次查詢，那麼

\[\mathrm{DL}_{\mathrm{G}, g}(Y) = \mathrm{DLO}(1,Y) \cdot \mathrm{DLO}(1,g)^{-1} \pmod p \qquad \text{ where } p = \lvert G \rvert\]

DL and OMDL

  • Fix a group $\mathrm{G}$ of prime order $p = \lvert G \rvert$.
  • Fix a generator $g \in \mathrm{G}^*$ of $\mathrm{G}$.
  • $\mathrm{DL}_{\mathrm{G}, g}$ is the discrete logarithm function in $\mathrm{G}$ with respect to the base $g$.

DL

Standard discrete logarithm（DL）問題可以用下列 game 描述。

Game $G^{\mathrm{dl}}_{G,g}$

Init:

  1. Set $p \leftarrow \lvert G \rvert \quad; \quad y \xleftarrow{\$} \mathbb{Z}_p \quad; \quad Y \leftarrow g^y$
  2. Return $Y$

Fin($y'$):

  1. Return $(y = y')$

INIT：隨機選取 $y \xleftarrow{$} \mathbb{Z}_p$，再令 $Y \leftarrow g^y$，接著把挑戰元素 $Y$ 交給攻擊者。

FIN：攻擊者的目標是輸出 $y’=\mathrm{DL}_{\mathrm{G},g}(Y)$，也就是求出 $Y$ 相對於基底 $g$ 的離散對數。若輸出的 $y’$ 恰好等於原本隨機選出的 $y$，則視為成功。

\[y' = \mathrm{DL}_{\mathrm{G},g}(Y)\]

OMDL

在 OMDL（One-More Discrete Logarithm）問題中，攻擊者不只得到一個挑戰，而是可以得到多個隨機挑戰 $Y_1,Y_2,\dots,Y_n \in G$。

同時，它還可以使用一個 discrete log oracle。對任意輸入 $W \in G$ 此 oracle 會回傳 $\mathrm{DL}_{\mathrm{G},g}(W)$。

為了和 MBDL 做比較，這裡只允許攻擊者對這個 oracle 查詢一次。即使只有一次查詢，攻擊者仍必須輸出給定列表中兩個群元素的離散對數。也就是說，它要從 $Y_1,Y_2,\dots,Y_n$ 之中，成功求出其中兩個元素相對於基底 $g$ 的離散對數。其中整數 $n \ge 2$ 是此問題的一個參數。

OMDL Game

Init:

  1. Set $Y_1, Y_2, \dots, Y_n \xleftarrow{\$} G$
  2. Return $(Y_1, Y_2, \dots, Y_n)$

DLO($W$):

  1. Return $\mathrm{DL}_{G,g}(W)$ with at most one query allowed overall

Fin($i,j,y_i',y_j'$):

  1. Return $\bigl(y_i'=\mathrm{DL}_{G,g}(Y_i)\bigr)\ \land\ \bigl(y_j'=\mathrm{DL}_{G,g}(Y_j)\bigr)$ for two distinct indices $i \ne j$

MBDL

給定一個隨機挑戰 $Y$，而攻擊者必須求出它在基底 $g$ 下的離散對數。攻擊者可以使用一個 oracle $\mathrm{DLO}$ 來計算離散對數，但和 OMDL 不同的是，這裡不是對基底 $g$ 做查詢，而是對一組公開且隨機的群元素 $X_1, X_2, \dots, X_n$ 作為基底來查詢。

整個過程中只允許對 $\mathrm{DLO}$ 做一次查詢。整數 $n \ge 1$ 是這個問題的一個參數。

考慮下列 game $G^{\mathrm{mbdl}}_{\mathrm{G}, g, n}$，其中 $n \ge 1$ 為基底的數量。

INIT：提供 inputs 給攻擊者，包括一個 random challenge group element $Y$，以及 random generators $X_1, X_2, \dots, X_n$。

DLO：攻擊者可以向 oracle $\mathrm{DLO}$ 查詢任意索引 $i \in [n]$ 以及任意群元素 $W \in G$，oracle 會回傳

\[\mathrm{DL}_{\mathrm{G},X_i}(W).\]

整體只允許查詢一次 oracle。

FIN：若攻擊者輸出

\[y'=\mathrm{DL}_{\mathrm{G},g}(Y),\]

則贏得此 game。

Game $G^{\mathrm{mbdl}}_{G,g,n}$

Init:

  1. Set $p \leftarrow \lvert G \rvert \quad; \quad y \xleftarrow{\$} \mathbb{Z}_p \quad; \quad Y \leftarrow g^y$
  2. For $i = 1, \dots, n$
  3. Set $x_i \xleftarrow{\$} \mathbb{Z}_p^\ast \quad; \quad X_i \leftarrow g^{x_i}$
  4. Return $Y, X_1, \dots, X_n$

DLO($i, W$):// One query

  1. Return $\mathrm{DL}_{G,X_i}(W)$

Fin($y'$):

  1. Return $(y = y')$

Define the mbdl-advantage of $\mathcal{A}$ by

\[\mathrm{Adv}^{\mathrm{mbdl}}_{G,g,n}(\mathcal{A}) = \Pr\!\bigl[G^{\mathrm{mbdl}}_{G,g,n}(\mathcal{A})\bigr].\]

Discussion

以 $n$-MBDL 表示參數為 $n$ 的問題。

Parameter Strength

若 $n$-MBDL 是困難的，那麼對任意滿足 $n’ \le n$ 的參數，$n’$-MBDL 也同樣是困難的。換句話說，可用的基底數量越少，攻擊者能利用的資訊就越有限，因此對應的假設也越弱。

  • $1$-MBDL 是這一系列中最弱的版本。

Restriction to One DLO Query

MBDL 會特別限制攻擊者至多只能呼叫一次 $\mathrm{DLO}$。這個限制是必要的，因為若允許兩次查詢，攻擊者便可以直接解出挑戰，使整個問題變得 trivial。

假設攻擊者可以查詢兩次。先計算

\[\begin{aligned} a &= \mathrm{DLO}(1,Y)=\mathrm{DL}_{G,X_1}(Y) \\ b &= \mathrm{DLO}(1,g)=\mathrm{DL}_{G,X_1}(g) \end{aligned}\]

由此可得

\[X_1^a=Y \qquad\text{and}\qquad X_1^b=g.\]

Let $y’ \leftarrow ab^{-1} \bmod p$. Then

\[g^{y'} = (X_1^b)^{ab^{-1}} = X_1^a = Y.\]

因此 $y’$ 正好就是 $Y$ 在基底 $g$ 下的離散對數，也就是 $y’=\mathrm{DL}_{G,g}(Y).$

這表示只要允許兩次 $\mathrm{DLO}$ 查詢，攻擊者就能直接解出挑戰，因而獲勝。所以在 MBDL 的定義中，$\mathrm{DLO}$ 的查詢次數必須限制為至多一次。

Evidence for Hardness

作為 MBDL 困難性的證據，Theorem 5.1 在 generic group model（GGM）中證明了不錯的攻擊者優勢界。

??? 另一個重要面向，是考慮橢圓曲線上離散對數問題的 non-generic 方法，包括 index-calculus methods 與 Semaev polynomials [48, 46, 49, 35, 29]。但依作者的判斷，這些方法並不能給出優於 Theorem 5.1 中 GGM 界的 MBDL 攻擊。

Possible Generalization

依照這個定義，MBDL 還可以再進一步一般化：允許多次 $\mathrm{DLO}$ 查詢，但限制為每個基底至多只能查詢一次，也就是對每個 $i$，至多允許一次 $\mathrm{DLO}(i,\cdot)$ 查詢。

這個延伸版本在論文中並未被使用，不過已可觀察到一些可能建立在其上的應用。

目前仍缺乏在 GGM 中對此延伸版 MBDL 的安全性證明，因此它仍是一個值得進一步研究的 open question；若能建立相應的 GGM 結果，也可能帶來新的應用方向。

Fixed Generator

在 DL 與 MBDL 的形式化中，generator 均固定為 $g$。

至於 fixed generator 與 random generator 兩種形式化方式之間的差異與討論，可參見 BZM19。

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.
  • BNPS03 M. Bellare, C. Namprempre, D. Pointcheval, and M. Semanko. The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology, 16(3):185–215, June 2003.
  • BZM19 J. Bartusek, F. Ma, and M. Zhandry. The distinction between fixed and random generators in group-based assumptions. In A. Boldyreva and D. Micciancio (eds.), CRYPTO 2019, Part II, LNCS, vol. 11693, pages 801–830. Springer, Heidelberg, Aug. 2019.
↑