Timeline for Multi-target attacks of ECC public keys
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2021 at 6:00 | history | tweeted | twitter.com/StackCrypto/status/1408666354153050112 | ||
| Jun 25, 2021 at 21:09 | vote | accept | fgrieu♦ | ||
| Jun 25, 2021 at 20:21 | answer | added | poncho | timeline score: 2 | |
| Jun 25, 2021 at 16:16 | comment | added | Samuel Neves | No; finding all $k$ private keys costs $O(\sqrt{kn})$, that is, you save a $\sqrt{k}$ factor compared to solving each log separately. This has been explicitly proved by Yun, but was already the cost of the best attack since 1997 or so (Silverman). | |
| Jun 25, 2021 at 16:10 | comment | added | fgrieu♦ | @SamuelNeves: [Updated: following the next comment, I now get you, and that your existing answer does solve the question]. I don't get you. Are you saying finding all private keys is as hard as finding one? I'm ready to believe that, but how? | |
| Jun 25, 2021 at 16:08 | comment | added | Samuel Neves | There's no precomputation involved there either; the "precomputation" is really just solving the first target (or a dummy target, if one insists on precomputation). | |
| Jun 25, 2021 at 16:06 | comment | added | fgrieu♦ | @Samuel Neves: thanks for pointing that. Not quite the same maybe: precomputation is not the same as multi-target, because the target(s) are not known when a precomputation starts. In RSA at least, that makes a significant difference: I know no precomputation attack to factor RSA moduli, but there are some (borderline useful) multi-target attacks, like Pollard's p-1. | |
| Jun 25, 2021 at 16:04 | comment | added | Samuel Neves | This is basically the same as this answer | |
| Jun 25, 2021 at 15:59 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
no QC
|
| Jun 25, 2021 at 14:36 | comment | added | SAI Peregrinus | The issue with that is that it's from 2001. I expect there's new research, or that new attacks might be cheaper. So I don't really want to answer it with that alone, since it's a 20-year old paper. I just remembered that it's cited in the "Batch discrete logarithms" section of Bernstein's Curve25519 paper and looked it up. Certainly it's an upper-bound on the difficulty though. | |
| Jun 25, 2021 at 14:31 | comment | added | SAI Peregrinus | I know Kuhn and Struik proved in 2001 (section 4) that Pollard's rho method can compute $k$ discrete logs in $\sqrt k$ time. The first takes the full expected time, the second less, the next even less, etc. | |
| Jun 25, 2021 at 14:06 | history | asked | fgrieu♦ | CC BY-SA 4.0 |