2 ms·

PQ-Crypto is still a very young research area. There is no widespread (or even niche) use of PQ-Crypto algorithms, no consensus on how safe any of the proposed

by cyphar 7y ago

PQ-Crypto is still a very young research area. There is no widespread (or even niche) use of PQ-Crypto algorithms, no consensus on how safe any of the proposed algorithms are (and many proposals were found to be exceptionally broken -- on classical hardware -- within weeks of their submission[1]). I'm not really sure it's fair to say that just because there are some on-paper algorithms (which have no usage outside academia at the moment) that might solve the problem that it's false to say that "all modern PK crypto is broken with quantum attackers". But if you prefer, you could imagine that I said "all modern PK crypto [that is actually in use today] is broken". Because, at the end of the day, that's all that really matters. [As an aside, for RSA the security is provided by the hardness of factorisation which also breaks under QC attackers, not discrete log (it's discrete log for DH, and EC discrete log for ECDH).] [1]: https://www.youtube.com/watch?v=ZCmnQR3_qWg https://www.youtube.com/watch?v=ZCmnQR3_qWg

sweis 7y ago
It not exactly a young research area. We have had post-quantum public key cryptosystems based on linear codes for over 40 years. Classic McEliece (https://classic.mceliece.org https://classic.mceliece.org) was created in 1978 and is in the 2nd round of NIST's PQ-crypto contest ( https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions https://csrc.nist.gov/projects/post-quantum-cryptography/rou...). The PQCrypto conference started 13 years ago: https://pqcrypto.org/conferences.html https://pqcrypto.org/conferences.html Chrome ran large scale experiments with NewHope support 3 years ago: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p...
- deleted 7y ago
  [deleted]
ChrisLomont 7y ago
Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. I wrote a decently cited paper summarizing all this when I worked in quantum computing research around 2005, on arxiv. Track it down if you’re interested. I’ve followed the field for decades, giving talks once in a while on it. So I do know a bit of the details. The computational power of QC is very well studied. It is certain that it cannot crack certain (most) problems any faster than a classical computer. Thus algorithms not isomorphic to the few problems QC is better at are just as secure on both classical and quantum computers. There is consensus on this - there is no question about it. >all modern PK crypto [that is actually in use today] NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. NTRU is also used in many commercial products from chat to relays. Other non DLP methods are also used in commercial products and standards.
- cyphar 7y ago
  > Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation (and the wiki page for "RSA problem"[1] also refers to integer factorisation, not discrete log). > It is certain that it cannot crack certain (most) problems any faster than a classical computer. Yes, I was already well-aware of that. My point was that the overwhelming majority of PK crypto used today depends on the hardness of problems that are exponentially accelerated by QC algorithms. > NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. Okay, maybe then it has some non-academic use. But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? [1]: https://en.m.wikipedia.org/wiki/RSA_problem https://en.m.wikipedia.org/wiki/RSA_problem
  - ChrisLomont 7y ago
    >But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation Periodicity is discrete log. Discrete log is defined as given a mathematical group G, a generator g in G, and an element h in G, find the power of g that gives h. This is a logarithm, over a discrete set, a finite group. This is equivalent to finding the power of h so h^r = 1, since given either, the extended euclidean algorithm gives an efficient way to get the other number. This number r is called the order of h, and there is no (in general) known classical efficient algorithm to do it. This can be easy or hard, depending on the group. Shor period finding is taking a the integers mod N (which is a group, called an abelian group, about the simplest class of groups), and an integer a, and finding the power r of a that is so a^r is 1 mod N. This is exactly the discrete log problem. You found the order of the element h. Shor is a special, easy case of the more general problem - he solves it efficiently for Abelian cyclic groups, but it has been extended to many, many other groups. In fact, researchers realizing this was exactly the general problem Shor solved is why all discrete log problems are vulnerable to QC. His method of using a quantum Fourier transform (which has a nice generalization to groups) to find period (which FFT does nicely) is directly applicable to any group. Shor is not some odd outlier algorithm; it is exactly the core (and almost the only) algorithm QC is exponentially faster at. >But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? Yes, but that is a far cry from your original claim. We only use those systems because they are not widely broken, and like all crypto, if one gets broken, we simply replace. This is not new. Each is easily replaced by algorithms that quantum cannot touch (unless classical can too), so much so, that many places already use QC resistant algorithms to prevent nation-states messing with them.

by cyphar 7y ago

sweis 7y ago

It not exactly a young research area. We have had post-quantum public key cryptosystems based on linear codes for over 40 years. Classic McEliece (https://classic.mceliece.org https://classic.mceliece.org) was created in 1978 and is in the 2nd round of NIST's PQ-crypto contest ( https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions https://csrc.nist.gov/projects/post-quantum-cryptography/rou...). The PQCrypto conference started 13 years ago: https://pqcrypto.org/conferences.html https://pqcrypto.org/conferences.html Chrome ran large scale experiments with NewHope support 3 years ago: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p...

deleted 7y ago
[deleted]

ChrisLomont 7y ago

Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. I wrote a decently cited paper summarizing all this when I worked in quantum computing research around 2005, on arxiv. Track it down if you’re interested. I’ve followed the field for decades, giving talks once in a while on it. So I do know a bit of the details. The computational power of QC is very well studied. It is certain that it cannot crack certain (most) problems any faster than a classical computer. Thus algorithms not isomorphic to the few problems QC is better at are just as secure on both classical and quantum computers. There is consensus on this - there is no question about it. >all modern PK crypto [that is actually in use today] NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. NTRU is also used in many commercial products from chat to relays. Other non DLP methods are also used in commercial products and standards.

cyphar 7y ago
> Shor factoring for RSA works by period finding, which is all modern PK crypto discrete log. Read the wiki page. But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation (and the wiki page for "RSA problem"[1] also refers to integer factorisation, not discrete log). > It is certain that it cannot crack certain (most) problems any faster than a classical computer. Yes, I was already well-aware of that. My point was that the overwhelming majority of PK crypto used today depends on the hardness of problems that are exponentially accelerated by QC algorithms. > NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. Okay, maybe then it has some non-academic use. But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? [1]: https://en.m.wikipedia.org/wiki/RSA_problem https://en.m.wikipedia.org/wiki/RSA_problem
- ChrisLomont 7y ago
  >But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation Periodicity is discrete log. Discrete log is defined as given a mathematical group G, a generator g in G, and an element h in G, find the power of g that gives h. This is a logarithm, over a discrete set, a finite group. This is equivalent to finding the power of h so h^r = 1, since given either, the extended euclidean algorithm gives an efficient way to get the other number. This number r is called the order of h, and there is no (in general) known classical efficient algorithm to do it. This can be easy or hard, depending on the group. Shor period finding is taking a the integers mod N (which is a group, called an abelian group, about the simplest class of groups), and an integer a, and finding the power r of a that is so a^r is 1 mod N. This is exactly the discrete log problem. You found the order of the element h. Shor is a special, easy case of the more general problem - he solves it efficiently for Abelian cyclic groups, but it has been extended to many, many other groups. In fact, researchers realizing this was exactly the general problem Shor solved is why all discrete log problems are vulnerable to QC. His method of using a quantum Fourier transform (which has a nice generalization to groups) to find period (which FFT does nicely) is directly applicable to any group. Shor is not some odd outlier algorithm; it is exactly the core (and almost the only) algorithm QC is exponentially faster at. >But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least? Yes, but that is a far cry from your original claim. We only use those systems because they are not widely broken, and like all crypto, if one gets broken, we simply replace. This is not new. Each is easily replaced by algorithms that quantum cannot touch (unless classical can too), so much so, that many places already use QC resistant algorithms to prevent nation-states messing with them.