0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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