Timeline for On getting beyond LSB in discrete log
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2020 at 17:36 | comment | added | poncho♦ | @1.. This is correct; $h'$ and $-h'$ will not both be qr's if $p \equiv 3 \pmod 4$. When you state $p = 2q+1$, I presumed $q$ was prime (as stated in the question), and most primes are not even. | |
| Dec 15, 2020 at 16:34 | comment | added | Turbo | If $h'$ is a quadratic residue then $h'^{q}\equiv1\bmod p$. Isn't $-h'$ also a quadratic residue? For example $6\bmod10$ is qr since $4^2\equiv 6\bmod 10$ and notice $2^2\equiv4\equiv-6\bmod10$. So both $h'$ and $-h'$ can be qr's. How can $-h'$ be odd order if $h'$ is odd order? Another example is $4\equiv-9\bmod 13$ and $2^2\equiv 4\bmod 13$ and $3^2\equiv9\equiv -4\bmod 13$. So both $h'$ and $-h'$ are qr's if and only if $q$ is even in $p=2q+1$ ('only if' clear)? | |
| Dec 15, 2020 at 13:23 | comment | added | poncho♦ | @1.. Yes, there is a second squareroot $-r$, however it is not a quadratic residue, and so does not have order $q$. | |
| Dec 15, 2020 at 7:46 | comment | added | Turbo | So supposing $r^2\equiv h\bmod p$ where $r$ has order $q$ and $p=2q+1$ then $h$ has exactly one 'square root' which is $r$ which can be found by $h^{2^{-1}}\bmod p$ since $2$ is invertible in exponent? Is there a second root which is $-r$ and is $r$ the principal root? | |
| Jul 15, 2017 at 14:42 | comment | added | poncho♦ | @Turbo: the lsbit is hard because, with an oracle that, given $g^y \bmod p$ gives you the lsbit of $y$, you can recover the entire value of $y$. The logic is the same as in the $\bmod 3$ case; you'd compute $h' = (hg^{-(y \bmod 2)})^{2^{-1} \bmod q} = g^{\lfloor y/2 \rfloor}$ to get the next bit. This works because the size of the subgroup $q = (p-1)/2$ is odd, and so $2^{-1} \bmod q$ exists. | |
| Jul 15, 2017 at 10:36 | comment | added | Turbo | if $p,\phi(p)/2$ are both large primes and $g\neq1$ is a qr mod $p$ why is least significant bit hard? | |
| Jun 2, 2017 at 2:47 | comment | added | poncho♦ | @Turbo: yes, if the order of $g$ is a large prime, then given $g^x$, then no one can directly deduce the value of any bit of $g$. In the above example ($p, (p-1)/2$ both prime), take $g$ to be any quadratic residue (other than 1)... | |
| Jun 2, 2017 at 1:40 | comment | added | Turbo | are there discrete logarithm schemes where even the last bit is secure? Or is that bit always insecure? | |
| Apr 23, 2017 at 17:43 | comment | added | poncho♦ | @Turbo: I mean the size of the group; I tried to edit it to be $p-1$, but the 5 minutes edit limit had passed... | |
| Apr 23, 2017 at 17:43 | vote | accept | Turbo | ||
| Apr 23, 2017 at 17:42 | comment | added | Turbo | you mean $\bmod (p-1)$ instead of $\bmod (q-1)$? | |
| Apr 23, 2017 at 17:36 | comment | added | poncho♦ | @Turbo: well, you would find $y \bmod 3$, and then compute $h' = (h g^{-(y \bmod 3)})^{3^{-1} \bmod q} = g^{\lfloor y/3\rfloor}$ ($q$ is the size of the group). Then, giving $h'$ to the Oracle will give the next ternary digit, and repeat until you've read the entire value of $y$ in ternary. | |
| Apr 23, 2017 at 17:31 | comment | added | Turbo | I do not see how to solve DLog if you know how to fine $y\bmod 3$. Could you please explain a bit? | |
| Apr 23, 2017 at 14:57 | history | answered | poncho♦ | CC BY-SA 3.0 |