Score:0

Computationally indistinguishability using DDH assumption

tm flag

This is part of the explanation of the commitment scheme from DDH in this lecture notes by Vipul Goyal: https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture22.pdf

My question is not directly related to the content of the pdf, but in page 20-4, it says $\{g, g^a, g^b, m \cdot g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$ is computationally indistinguishable from $\{g, g^a, g^b, g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$. Why is that necessarily true? Can anyone please formally explain why that’s the case? Also, when texts describe distributions in such way, are the two $(a, b, r)$’s in the two distributions equal? Or is it just that the symbols are same, but they are in fact independently selected at random from $\mathbb{Z}_q$?

Thanks.

us flag
Hi, welcome to crypto.stackexchange. I'm confused because page 20-4 literally has a step-by-step justification for why those two distributions are indistinguishable. Is there a more specific step that doesn't make sense?
user658183 avatar
tm flag
I wasn't sure about the equation that is between 'But' and 'So we have' on page 20-4, but I think yacovm's answer helped.
Score:2
us flag

Well this $m$ is some element in the group $\mathbb{G}$ so there exists some $\alpha \in \mathbb{Z}_q$ such that $m=g^{\alpha}$, hence $m \cdot g^r = g^{\alpha+r}$ and notice that since $r$ is selected uniformly at random from $\mathbb{Z}_q$, then the distribution of $\alpha + r$ is exactly (not just computationally but exactly) uniform in $\mathbb{Z}_q$ as well.

Intuitively you can think of $r+\alpha$ as taking $\alpha$ which someone selected for you, and then adding to it a random number modulo $q$, and it is exactly uniform because for every possible result of $r+\alpha$ there is exactly a single $r$ that makes it that result, hence it is uniform.

As for the (a,b,r) - keep in mind, that the DDH assumption is trying to say something like: If you look at two random group elements $g^a, g^b$ and you have a third group element $h\in\mathbb{G}$, then you don't know if $h=g^{a\cdot b}$ or that $h$ is some completely random, unrelated group element $g^r$ for some random $r$. The way you write this, is you look at two distributions where the $g^a, g^b$ are the same in both sides of the equality, but the third element is different (it is either $g^{a \cdot b}$ or $g^r$ and you say that under the DDH assumption, there doesn't exist an efficient probabilistic polynomial time turing machine that can distinguish between $g^{a \cdot b}$ and a random group element.

user658183 avatar
tm flag
Thanks! How about the second question? In such notations, are the $a, b, r$ equal values for the two distributions, or are they randomly picked separately?
yacovm avatar
us flag
I updated the answer, tell me if it is clear now.
user658183 avatar
tm flag
Yes, I understood your answer. Thank you so much!
yacovm avatar
us flag
No problem, happy to help
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.