Join Log in
Score:0
xxxqqq avatar Crypto

Equivalence between "Discrete Log Relation" and Discrete Log

in flag
xxxqqq

I am trying to understand Bulletproofs and it uses the following assumption (Section 2.1): Discrete Log Relation Assumption Note: $\mathbb{G}$ is of prime order $p$.

My question is about the last sentence in the image -- I cannot prove it. Specifically, I want to prove that $(*)$ if Discrete Log Relation is "broken", then the "plain" Discrete Log is also broken. Intuitively this makes sense, but I must be careful since I am just beginning self-learning cryptography.

An attempt for proving $(*)$: To break plain DL, I must find $x\in\mathbb{Z}_p$ s.t. $g^x=h$. Adversary $\mathcal{A}$ breaking DLR for $n=2, g_1 = g, g_2 = -h$ would give $a_1', a_2' \in \mathbb{Z}_p$. However, there is no guarantee that $a_2' = 1$ so that $a_1' = x$, unless there is a way to "convert" $(a_1',a_2')$ to $(x, 1)$. I am stuck here.

43
1 + 0
Score:1
poncho avatar Crypto
my flag
poncho

However, there is no guarantee that $a_2' = 1$ so that $a_1' = x$, unless there is a way to "convert" $(a_1',a_2')$ to $(x, 1)$. I am stuck here.

I won't give you an answer (having you find the answer is much better for learning); I will give you a few hints:

  • $g^{a}(g^x)^{b} = 1$ is equivalent to saying that $a + bx = 0 \pmod q$, where $q$ is the order of the element $g$; this is true even if $g^x = h$

  • If we know a value $b \ne 0$, and $q$ is prime, then is it feasible to find a value $b'$ such that $b \cdot b' = 1 \pmod q$?

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.