9
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.