Decisional Diffie-Hellman Assumption over Group of Quadratic Residue

Sean

10/30/22, 12:59 PM

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?).

109

0 + 8

diffie-hellman

hardness-assumptions

Ievgeni

10/30/22, 1:09 PM

given $x^2$ or $g^{x^2}$?

poncho

10/30/22, 1:21 PM

"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.

Sean

10/30/22, 1:47 PM

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)

Ievgeni

10/30/22, 3:02 PM

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.

Geoffroy Couteau

10/30/22, 10:03 PM

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

Sean

10/30/22, 10:10 PM

Regarding levgeni's comment: But in $QR_n$, this $n$ is the RSA composite, then trying to find root of a quadratic residue is equivalent to factoring $n$. See Couteau's eurocrypt17 paper for example: https://link.springer.com/chapter/10.1007/978-3-319-56614-6_11.

Sean

10/30/22, 10:13 PM

Here's a similar question I posted yesterday: -- does it make any difference that the modulus is $\phi(n)/4$ or $n$? https://crypto.stackexchange.com/questions/91786/group-of-quadratic-residue-over-blum-integer

Sean

11/1/22, 12:33 PM

I see the point of $\phi(n)/4$ now -- for the $x$ on the exponent of $g^x$. The difficulty here is that if exposing the totient $\phi(n)$ the $n$ would be then factored. What we could do is to ask a trusted sever provides $r \phi(n)$ where $r$ is a big random integer. In this way, a $x^2$ congruent over $r \phi(n)$ is provided. Thus the problem is slightly changed to: \n Given $x^2 \mod \phi(n)/4*r$ where $r$ and $\phi(n)$ is unknown, is it possible to distinguish $g^x$ with an efficient algorithm?

Elon Musk

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

EN: Decisional Diffie-Hellman Assumption over Group of Quadratic Residue

TH: ข้อสันนิษฐานของ Diffie-Hellman ที่ตัดสินใจเกี่ยวกับกลุ่มของสารตกค้างกำลังสอง

RO: Ipoteza decizională Diffie-Hellman asupra grupului de reziduuri cuadratice

RU: Решающее предположение Диффи-Хеллмана о группе квадратичных вычетов

VI: Giả định Diffie-Hellman quyết định đối với Nhóm dư lượng bậc hai

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.