If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

Anon

9/6/23, 1:52 PM

I am trying to prove the following:

Given an ensemble $\{p_n, g_n\}$ ($p_n$ is an $n$-bit prime and $g_n \in \mathbb{Z}^*_{p_n}$ is a generator), if $A$ is a deterministic polynomial time algorithm such that:

$$ \Pr_{x \leftarrow \mathbb{Z}^*_{p_n}} [A(a)=x \text{ where } g_n^x=a]=\frac{1}{poly(n)}$$

then there is a PPT algorithm $A'$ that solves discrete log with high probability for this ensemble.

I would probably need to somehow call $A$ a polynomial number of times and use the results, but I have no concrete direction on how to proceed with this intuition to define $A'$. Obviously, I can verify the response by $A$, since computing $g^x$ can be done in polynomial time, but if it's wrong - then what?

Note, I have seen all sorts of questions on discrete log using something called baby step giant step, but I am not familiar with that at all (in case it may be useful here).

Any help would be greatly appreciated.

0 + 0

discrete-logarithm

group-theory

kelalaka

9/6/23, 5:47 PM

[If there is a backdoor to any base then there is a backdoor to all bases](https://crypto.stackexchange.com/a/91545/18298). Quite easy to see this.

Score:3

Crypto

Meir Maor

9/6/23, 2:34 PM

Yes, the discrete logarithm is random self reduceable, that is the worst case is as hard as the random case.

If we are given y and wish to find $x$ s.t $y=g^x \bmod p$ we can pick a random a and calculate b=$g^a\times y =g^{a+x}$

This value $b$ is uniformly distributed regardless of y. If however, we solve a discrete logarithm for it we can easily subtract $a$ and find $x$.

Q.E.D.

0 + 0

Elon Musk

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

EN: If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

TH: หากเราสามารถแก้ไขบันทึกแยกด้วยอินสแตนซ์ $\frac{1}{poly(n)}$ ได้ เราก็สามารถแก้ไขได้โดยมีความเป็นไปได้สูงสำหรับทุกอินสแตนซ์

RO: Dacă putem rezolva log discret cu pe $\frac{1}{poly(n)}$ instanțe, atunci putem rezolva, cu mare probabilitate, pentru toate instanțele

RU: Если мы можем решить дискретный логарифм с экземплярами $\frac{1}{poly(n)}$, то мы можем с высокой вероятностью решить для всех экземпляров

VI: Nếu chúng ta có thể giải log rời rạc với các trường hợp $\frac{1}{poly(n)}$, thì chúng ta có thể giải, với xác suất cao, cho tất cả các trường hợp

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.