81–90 of 132 posts
Earlier quoted context omitted.
It's hard to say. Here is a great paper that tries to answer this question. https://arxiv.org/pdf/2009.05045v1.pdf See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.
The linked study is about RSA, not elliptical curve cryptography
Earlier quoted context omitted.
It's hard to say. Here is a great paper that tries to answer this question. https://arxiv.org/pdf/2009.05045v1.pdf See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.
The linked study is about RSA, not elliptical curve cryptography
HN Crypto and Quantum Experts. What is your prediction when classical public key encryption using elliptical curve cryptographic becomes practically vulnerable to quantum computers, such that we would need these PQC algorithms. 10 years out? 20 years out? 50 years out? 100 years out?
PQC = post quantum cryptography
Ah thank you. I figured the 'Q' stood for quantum but you saved me a fair amount of googling :)
Not sure what browser you use, but in most you can select what you wanna search for, click "Search on $searchEngine for $term" and there you go! For PQC, I get Wikipedia link with "PQC can refer to: Post-quantum cryptography" in the description as the 3rd result on Google.
Not sure what classifies as "fair amount", but for me it took about 1-2 seconds to find the Wikipedia link ;)
Obligatory djb warnings: https://ntruprime.cr.yp.to/warnings.html
Earlier quoted context omitted.
If NIST feels the need to hedge their bets, why are they publishing at all? The whole point of these recommendations is so that I, a non-expert, don't have to reason about cryptographic bets.
Non-cryptographers should not be implementing NIST standards. You should be using higher level APIs written by cryptographers which do employ NIST standards in the details.
> Additionally, SPHINCS+ will be standardized to avoid only relying on the security of lattices for signatures > Both BIKE and HQC are based on structured codes, and either would be suitable as a general-purpose KEM that is not based on lattices What's up with this caveat? Why would the standard require algorithms not based on lattices assuming there is confidence in the lattice based approach? Is this a security con…
A point rendering the choice even more curious: Germany and the Netherlands have recommended the use of encryption not relying on the shortest vector problem [1]. The two suggestions of FrodoKEM (relying on hardness of the learning with errors problem) and Classic McEliece (relying on hardness of decoding random codes?) aren't lattice-based apparently. Perhaps NIST knows something we don't ; ^ ) [1] - https://twitter…
At a very high level, all of the three rely on an n x n matrix at a certain point. The "structured lattice" schemes (Kyber/Saber) make structural assumptions about this matrix, say that each row is a cyclic shift of the previous row. This turns an O(n^2) object into an O(n) object, giving many performance improvements. The downside is that the additional structure can plausibly be used for attacks (but the best attacks ignore the structure, so this is a "potential issue", not a current issue).
Obligatory djb warnings: https://ntruprime.cr.yp.to/warnings.html
Is djb involved in any of the standardized algorithms here by the way?
Earlier quoted context omitted.
I it not tied to P vs NP as far as I’m aware. But it is the same sort of situation: number theory assumptions that are completely unproven despite many attempts.
I was thinking, if you could definitively prove these assumptions are hard, that would prove P != NP, because if P=NP that would imply there would be an algorithm to solve these types of problems, since they are the type of thing that can be solved in polynomial time with the key, but cannot without a key. (I'm a bit out of my depth here)
Earlier quoted context omitted.
I wrote up an introduction to a (severely unoptimized for pedagogical purposes) version of FrodoKEM https://mark-schultz.github.io/nist-standard-out/ It's the same base scheme as Saber/Kyber, although as Saber/Kyber are over algebraically structured lattices they are significantly more efficient.
Thanks for taking the time to write this up. But, woof, it's a bit more than ELI5. :) The python code makes it a little more clear since I'm not familiar with some of the notation. However, it does seem kind of magic that 'e' is derived during the encryption and then sort of vanishes. I also don't quite get the bounded vs uniform vector sampling calls (one for s and the other for chi). But this at least greases the w…
Quickly (cause I probably won't for a few days), (q//2)m can be seen as a form of error correction. You can check (either pen+paper or programmatically) that, provided |e| m + e, then round(noisy_m / (q/4)) = m. So e vanishes because it is bounded (not uniform), + we encode m as (q//2)*m (i.e. in the "most significant bits" of the number).