Timeline for Why are NIST curves still used?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 12, 2021 at 5:17 | comment | added | Mark Schultz-Wu♦ | @poncho Yes, that is why I wrote $\Omega(2^{\lambda/2})$ and not $\omega(2^{\lambda/2})$. I wrote $\Omega(\cdot)$ instead of $\Theta(\cdot)$ to highlight that the argument cares about the lower bound specifically (and the fact that a matching upper bound exists doesn't matter), perhaps this was somewhat pedantic. | |
| Aug 12, 2021 at 2:14 | comment | added | poncho | @Mark: actually, there are generic techniques in classical computing that break ECC in time $\Theta(2^{\lambda/2})$ - these attacks rely on the group structure of ECC | |
| Aug 11, 2021 at 19:25 | comment | added | Mark Schultz-Wu♦ | The energy expenditure bound itself essentially says "you pay a minimum amount of energy for each bit of energy that is erased". This probably means that there isn't a quantum analog (quantum computing is, up until you measure, "reversible"), but you could bound the amount of energy to solve DLOG over a generic group (which has a lower bound of $\Omega(2^{\lambda/2})$ in the classical setting --- the bound itself isn't specific to symmetric crypto. | |
| Aug 11, 2021 at 19:21 | comment | added | Mark Schultz-Wu♦ | @miraunpajaro if one were brute forcing ECC, it would take $\Theta(2^\lambda)$ time (essentially by definition). Generic techniques in quantum computing (Grover's algorithm) often let you bring this down to $\Theta(2^{\lambda/2})$ - you can stop this via doubling key sizes though. The issue with ECC is that Schor's algorithm exists, which brings the complexity of DLOG (over a group of size $O(2^\lambda)$) down to (quantum) polynomial time, e.g. $\lambda^{O(1)}$. | |
| Aug 11, 2021 at 19:18 | comment | added | miraunpajaro | @Mark Could you elaborate? How exactly? | |
| Aug 11, 2021 at 19:17 | comment | added | miraunpajaro | Aahh I see. And symmetric crypto is quantum resistent, I see. | |
| Aug 11, 2021 at 19:16 | comment | added | Mark Schultz-Wu♦ | @Lery the important point is actually that it is for brute forcing, while a functioning QC allows one to do much better than brute force against ECC. | |
| Aug 11, 2021 at 18:45 | comment | added | Lery | No, any ECC algo (that isn't isogney-based) is broken by a quantum computer. Also, you are probably mixing up with the famous bound on the energy it would take to bruteforce a 256 bits key, but that's for symmetric algorithms, not ECC. | |
| Aug 11, 2021 at 18:39 | vote | accept | miraunpajaro | ||
| Aug 11, 2021 at 18:39 | comment | added | miraunpajaro | Very nice! One question about quantum computers. AFAI, there are lower bounds on how much energy it would take to brute force some ecc algos. Do these bounds apply to quantum computing? My guess is no, but idk. | |
| Aug 11, 2021 at 17:49 | comment | added | Lery | Yup, that's the expectation I was mentioning. But I have doubts we'll be able to have "stable" enough QC to achieve this ^^' | |
| Aug 11, 2021 at 17:47 | comment | added | poncho | One "real" Quantum Computers exist (where "real" means 'large and reliable enough to run Shor's algorithm on the size of curves we use), all elliptic curves become insecure (exception: supersingular isogeny-based methods, which works completely differently) | |
| Aug 11, 2021 at 16:25 | history | answered | Lery | CC BY-SA 4.0 |