Score:0

On a problem assuming Diffie-Hellman oracle

ru flag

If we have a Diffie-Hellman oracle then given $g^x$ and $g^y$ we can construct $g^{xy}$.

Can we construct $g^{x^{-1}}$ given $g^x$?

Score:3
kr flag

If the group is of known prime order $q$ (which is usually the setting in which DH is considered), then $g^{1/x} = g^{x^{q-2}}$, and the latter can be obtained with $O(\log q)$ calls to the DH oracle.

Turbo avatar
ru flag
I thought the order is 2q.
kr flag
That's not a standard setting (for example DDH is trivially broken in a group of order $2q$; moreover, note that $x^{-1}$ isn't even well defined for half of the possible values of $x$), but the same approach is straightforward to extend to that case as well.
Turbo avatar
ru flag
Thank you. I am curious about your comment ddh is broken trivially on a group of order 2q. Why?
kr flag
Because it's easy to recognize the subgroup of order q (which contains half of the elements) and in a DDH triple $(g^x, g^y, g^z)$, the last element being in the subgroup is clearly not independent of the other two being in the subgroup.
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.