Discrete Logarithm in the generic group model is hard - Theorem by Shoup

einsteinwein

2/20/23, 6:32 AM

In Shoups well-known paper Lower bounds for Discrete Logarithms and Related Problems he proves that the Discrete Logarithm Problem is hard in the generic group model (if group operation and inverse are the only computations that can be performed on group elements). Theorem 1 in the paper says that the probability that a generic algorithm $A$ solves this problem is bounded by $\mathcal{O}(m^2/p)$ (m is the number of oracle queries, p the prime group order). The part that I don't understand is the following:

If we insist that $A$ succeed with probability bounded by a positive constant (e.g., 1/2) to the below, this theorem translates into a lower bound $\Omega(\sqrt{p})$ of the number of group operations queried by $A$.

Can someone explain this conclusion to me?

132

0 + 0

discrete-logarithm

ggm

Score:5

Crypto

Ievgeni

2/20/23, 6:42 AM

Let $K$ be the constant (which doesn't depend of $p$) such that the probability is bounded by $K\frac{m^2}{p}$. (a such $K$ exists by definition of $\mathcal{O}$).

It means that if an adversary solves the discrete logarithm problem with probability more than $\frac{1}{2}$, we obtain.

$$K\frac{m^2}{p}\geq \frac{1}{2}$$.

It implies that

$$m\geq \sqrt{\frac{p}{2K}} $$

Thus we deduce that $m$ -which is in fact a function of $p$, is lower bounded by $K'\sqrt{p}$, with $K':=\sqrt{\frac{1}{2K}}$ a constant which doesn't depend of $p$.

It's equivalent to write $m\in \Omega(\sqrt{p})$ (according to the Knuth notation).

Notice now that $\sqrt{p}$ is exponential in the size of the input, and you will deduce that any generic adversary is not efficient against DLog.

0 + 0

einsteinwein

2/20/23, 2:05 PM

Thank you very much! :-)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Discrete Logarithm in the generic group model is hard - Theorem by Shoup

TH: ลอการิทึมแบบไม่ต่อเนื่องในแบบจำลองกลุ่มทั่วไปนั้นยาก - ทฤษฎีบทโดย Shoup

RO: Logaritmul discret în modelul de grup generic este greu - Teorema lui Shoup

RU: Дискретный логарифм в общей групповой модели сложен - Теорема Шоупа

VI: Logarit rời rạc trong mô hình nhóm chung là khó - Định lý của Shoup

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.