Is the one-more discrete log problem hard in the Generic Group Model?

Question

In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access to the encoded form of any input group elements (such as the generator/public key/...), and an oracle to apply the group operation on them. The encoding is unique, so group elements can be tested for equality. It can be seen as the analogue of the Random Oracle Model for groups instead of hashes.

It is well-known that the discrete logarithm problem is hard in the GGM: Shoup showed that any generic algorithm needs $\Omega(\sqrt{p})$ group operations, where $p$ is the largest prime factor of $n$.

My question is whether the one-more discrete logarithm problem (OMDL) is also hard in the GGM. To break OMDL, an adversary is given $k+1$ random group elements, can make $k$ queries to a DL oracle, and must then succeed in finding the discrete logarithm of all $k+1$ inputs.

Answer 1

More recent work by Bauer et al. [BFP] claims that the proof in a previous answer is flawed (and that Coretti et al. confirmed this). However, Bauer et al. prove hardness of OMDL in the GGM. They show that the probability that an adversary solves OMDL (without pre-computation) in a generic group of prime order $N$ and making at most $T$ oracle queries is at most $T^2/(N - T^2) + 1/N$.

[BFP]: Bauer, Fuchsbauer, Plouviez, The One-More Discrete Logarithm Assumption in the Generic Group Model

Answer 2

Yes, this was shown in a recent work of Coretti et al [CDG]. Loosely speaking, the lower bound states that an adversary that makes at most $T$ queries to the GGM oracle succeeds with probability at most $T^2/N$, where $N$ is the size of the group. They in fact consider a stronger model where the adversary is allowed arbitrary pre-computation in the GGM. See §5 for more precise statements and Table 2 for a summary of their results.

[CDG]: Coretti, Dodis and Guo, Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models, Crypto'18