3
$\begingroup$

Consider the Decision Diffie-Hellman (DDH) over $QR_n$ (the quadratic residue group over $n=pq$ where $p$ and $q$ are safe primes).According to Boneh's paper, DDH should be hard over $QR_n$ (https://link.springer.com/chapter/10.1007/BFb0054851):

[DDH] Given three randomly sampled $g^x, g^y, g^z$ it is hard to tell if $z = x*y$.

I'm wondering: if given an extra $x^2$ $mod$ $n$, is this problem still hard over $QR_n$? (The intuition is that computing the root of $x^2$ is hard, so intuitively this square should provide no additional information for solving DDH. The exceptions might be it leaks Jacobi/Legendre symbols, but the random pick of $z$ can be fixed correspondingly?).

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ given $x^2$ or $g^{x^2}$? $\endgroup$
    – Ievgeni
    Jun 30, 2021 at 13:09
  • $\begingroup$ "so intuitively this square should leak no additional information"; actually, from a provability standpoint, it's the other way around - if it were easy to compute, it wouldn't leak anything (the attacker could compute it himself, hence giving the value to the attacker doesn't tell him anything he doesn't already know). The most obvious counterexample, the value $g^{xy}$ is also hard to compute, but giving that value as well makes the attacker's problem trivial. I'm not saying that giving the value $g^{x^2}$ makes the attacker's problem easy; I'm saying it's not trivial to show. $\endgroup$
    – poncho
    Jun 30, 2021 at 13:21
  • $\begingroup$ Given $x^2$ (not $g^{x^2}$). So my question is: if given this extra $x^2$, would the decision DH still be hard (in the context of quadratic residue group) $\endgroup$
    – Sean
    Jun 30, 2021 at 13:47
  • $\begingroup$ but, we can compute the square-roots of $x^2$ in $\mathbb{R}$ easily, and one of these roots will be equal to $x^2$. Thus it's easy to check if it's a ddh-tuple or not. $\endgroup$
    – Ievgeni
    Jun 30, 2021 at 15:02
  • $\begingroup$ Interesting question! I see no obvious reduction to standard assumptions. A suggestion: you could start by considering a simplified version of the problem, where given $x^2 \bmod \phi(n)/4$, your task is to distinguish $g^x$ from a random element of $\mathsf{QR}_n$. $\endgroup$
    – Geoffroy Couteau
    Jun 30, 2021 at 22:03

0

Reset to default

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.

Browse other questions tagged or ask your own question.