I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
The lower bound for the generic group model is proved by Victor Shoup,
He showed in Lower bounds and Discrete Logarithm and Related Problems
Lower bounds on the complexity of these problems are proved that match the known upper bound: any generic algorithm must perform $\Omega(p^{1/2})$ group operations, where $p$ is the largest prime dividing the order of the group.
Generic Group model;
To process with a group we must present them with bit strings. This must be a bijection, 1-1 and onto. A generic algorithm works independently from the representation of the group. They are not allowed to work with efficient representation as field and rings instead they are working with an oracle with the random representation $\sigma$ of the group. The oracle executes the group operation $$\text{add}(\sigma(a),\sigma(b)) = \sigma(a+b)$$ and $$\text{inv}(\sigma(x)) = \sigma(-x) $$ The running time is measured by the number of oracle calls.
The importance of this model is providing an answer to the question
- What is the fastest generic algorithm for breaking a cryptographic hardness assumption?
The lower bound for the generic group model is proved by Victor Shoup. It is proven that any algorithm with constant success probability has at least $\mathcal{O}(\sqrt{q})$-time where $q$ is the largest factor of the group size $n$. The generic algorithms are
- Baby-step Giant-step needs an upper bound knowledge of the group size and has running time $\mathcal{O}(\sqrt{n} \log n)$.
- The Pohlig-Hellman algorithm needs the prime factorization of $n$ and has $\mathcal{O}(\sqrt{q} \log q)$ complexity.
Generic Group model has the same problem as the Random Oracle model - Real model vs Ideal model. It can be shown that Cryptographic schemes can be secure under the generic group model but trivially broken if instantiated 1,2
answered Sep 1, 2019 at 15:57
-
2$\begingroup$ Actually, in the 'generic group' model, where the only allowed operations are the group operation ("a+b"), inversion ("-a"), and checking for equality (does $a=b$?), you can prove that the best algorithm takes $O(\sqrt{n})$ time - he was asking for a write up of this. Of course, any implementation of a group will allow some operations beyond this (potentially not useful operations, but still, it makes the proof invalid). $\endgroup$– ponchoCommented Sep 1, 2019 at 16:18
-
$\begingroup$ @poncho I see now. Thanks. shoup.net/papers/dlbounds1.pdf $\endgroup$– kelalakaCommented Sep 1, 2019 at 16:24
-
$\begingroup$ I'll sketch the proof later, or someone can do it... $\endgroup$– kelalakaCommented Sep 1, 2019 at 21:48
-
1$\begingroup$ @Turbo: are you asking if we include in our allowed operations a CDH Oracle (given the elements $G, xG, yG$, returns $xyG$), does it still takes $\Omega( \sqrt{n} )$ time? At first glance, I would think so - the general idea of "you're computing values of the form $xG + yH$ and can't tell where you are until you happen upon a collision, that is, $xG + yH = zG + wH$, still would appear to hold with the additional operation - however, something might come up with a more detailed proof. Obviously Shoup's original proof wouldn't apply... $\endgroup$– ponchoCommented Jan 8 at 13:42
-
1$\begingroup$ @Turbo: there is no Alice and Bob here. Instead, you are handed the values $G, sG$ and also an Oracle that, given $xG, yG$, can give you $xyG$. The question is "how hard is finding $s$?". My first thought was "it doesn't look much easier than it would be if you didn't have the Oracle" - my latter thought was that there might be some clever way of using the Oracle (computing a high-degree polynomial might give you more information than what my proof outline accounted for). $\endgroup$– ponchoCommented Jul 30 at 18:35