Score:0

Crypto

Proving a variation of CDH is hard

yankovs

6/5/23, 1:37 PM

let $(\mathbb{G},q,p)$ be a group $\mathbb{G}$ with prime order $q$ and generator $g$. Assume that CDH is hard relative to this setup (Namely, given $(g,g^a,g^b)$, it is hard to find $g^{ab}$).

Now consider the following: for a probabilistic-polynomial time adversary $\mathcal{A}$, and given $(\mathbb{G},q,p)$, choose random $a,b,c\in \mathbb{Z}_q$ and run $\mathcal{A}(g,g^a,g^b,g^c)$. $\mathcal{A}$ succeeds if it outputs any of $g^{ab}, g^{ac}, g^{bc}$.

I am to show this is also hard. The somewhat obvious approach would be reduce the three possible outputs resulting in success to CDH, for example: $g^{bc}$ is exactly CDH if the input were $(g,g^b,g^c)$. However, in this case we are also given $g^a$ so this is not a simulation of CDH. I've also tried other approaches, trying to choose $c$ such that I am able to recover $g^{ab}$ with high probability in any case. I looked at $g^c=g^{a+b}$ but then I'm not sure how to get to $g^{ab}$ from $g^{a^2+ab}$.

Any help is appreciated, this is not homework.

0 + 0

diffie-hellman

Daniel S

6/5/23, 1:51 PM

HINT: Generate a random $x$; flip a coin. With heads consider $c=a+x$ and with tails consider something else.

yankovs

6/5/23, 1:56 PM

@DanielS when you write c = a + x you mean c = a + x mod q?

Daniel S

6/5/23, 2:00 PM

Yes, similarly, in your first attempt $a+b$ should be considered as $a+b\mod q$.

yankovs

6/5/23, 2:25 PM

@DanielS Assuming we set $c=a+x$ we also know $-x$ (might as well take $q-x$) so we can remove $bx$ from $g^{ab+bx}$ or square it and get $g^{(a+x)^2}$ from $g^{a^2+ax}$. But we don't know what output we got, I'm not really sure where this leads us

Daniel S

6/5/23, 2:47 PM

Two out of the three possible successes from $\mathcal A$ would lead to a solution fo CDH, but there is not a consistent probabilistic way for $\mathcal A$ to always return the unhelpful answer.

poncho

6/5/23, 2:52 PM

Actually, if we have a probabilistic way whose success probability is bounded away from zero, and for which we can determine when success happens, we win (actually, we also need to make sure the success probability is unaffected by the algorithm the Oracle uses to select which answer it gives). Can we do this (hint: yes)

poncho

6/5/23, 3:23 PM

There's also the approach of computing $g^{a^2}$ by simply passing $\mathcal{A}( g, g^a, g^a, g^a )$ (and CDH can be reduced to that problem). However, the Oracle may balk on odd-looking inputs like that; the previous solution I was eluding to sounds more robust

kelalaka

6/5/23, 9:58 PM

@poncho why oracle will bulk? due to non-random? Maybe another is $(a,b,1)$ and we can test the result

kelalaka

6/6/23, 12:01 AM

Really we don't know? We know $a,c,x,$ then we know $g^{\text{pair}}$

Elon Musk

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

EN: Proving a variation of CDH is hard

TH: การพิสูจน์ความแปรปรวนของ CDH นั้นยาก

RO: Demonstrarea unei variații a CDH este dificilă

RU: Доказать вариацию CDH сложно

VI: Chứng minh một biến thể của CDH là khó

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.