50 ms·

There'll probably be discovered a class of problems which is hard and Q hard, provably and we'll be set. Something basically new to cryptography, that was tried

There'll probably be discovered a class of problems which is hard and Q hard, provably and we'll be set. Something basically new to cryptography, that was tried once in the past but failed until seen through a new light of more recent maths or research fashion. But until then it seems to me like something based on the difficulty of attacking hash functions would be a good bet for Q resistant. Totally unsure how to make a PK scheme from that, but it has a few nice properties: - hashes are often tuneable, you can add more state and increase the keyspace/security - good hashes don't have any weaknesses that Q can exploit - hashes are often pretty fast - hashes are well studied - hashes seem to be hard in C and hard in Q

YoumuChan 3y ago
We don't even know the complexity class of factorization or discrete log, yet we still use those problems in DH, RSA, ECDSA, ...
- eru 3y ago
  All of those problems are known to be in NP and co-NP. In that sense, we know some complexity classes they belong to. However, we don't know if these bounds are tight, or whether they are eg in P, or something in between.
  - keepamovin 3y ago
    We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization. It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!! I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)
    - SJC_Hacker 3y ago
      I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel. So maybe it should really be P and NDP.
      - keepamovin 3y ago
        That's a good explanation. I didn't know that.
      - eru 3y ago
        > or alternatively, a function executing on all inputs in parallel. I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses). But as long as your parallel executions don't interact at all, the definitions are identical, I think.
    - eru 3y ago
      > We don't know that factorization is NP-complete. Yes? No one ever said it was. None of the common cryptographic problems are expected to be NP-complete, even if they aren't in P. That's because they are known to be in both NP and in co-NP, and it's expected that NP != co-NP. > I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". In what sense is that a 'better' definition than the standard definition? It sounds like what you are talking about is NP\P (where \ is set subtraction, ie 'NP minus P').
      - keepamovin 3y ago
        I think some people have asked whether it was. I'm not saying you did, just thought it was interesting! Haha :) I don't even know what co-NP is. Could you explain? I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Yeah, I guess what you're saying about NP\P is right in that it's a restatement of the definition of what I said, haha! I'm not an expert this is just what I think :)
  - openasocket 3y ago
    I always found that part odd. I’d assume you would want the problem you build your crypto system built around to be NP-complete, since that would seem to put you on the firmest possible ground. And yet those are most likely not NP-complete, and I think the post-quantum systems proposed aren’t NP complete either. Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
    - eru 3y ago
      No crypto-problem is NP-complete. People tried that for a while, see https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_cryptosystems but it didn't work. > Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system? To simplify a bit, the problem is that to work as a crypto system your particular problems needs to be both in NP and in co-NP. And we know of no problem that is both NP-complete and in co-NP. It's widely conjectured that there is no such problem. See https://en.wikipedia.org/wiki/Co-NP https://en.wikipedia.org/wiki/Co-NP that page even mentions integer factorisation. That's why you can't just take the NP-complete problem itself as a basis for your cryptosystem, you have to pick some subset of instances that's also in co-NP. And apparently it's almost impossible for us to pick such a subset, but still have the instances be hard enough to solve on average.
Vecr 3y ago
https://en.wikipedia.org/wiki/McEliece_cryptosystem https://en.wikipedia.org/wiki/McEliece_cryptosystem Yes, it's reasonably fast even at very long lengths, but the main problem is the very long lengths. Code based and not hash based though. Edit: not very fast to generate a key though. It's mostly used for non-ephemeral stuff.
- amluto 3y ago
  The new algorithm purports to solve LWE with certain choices of parameters. LWE is the problem of solving a linear system of equations over a finite ring, where each equation has an additive error from a certain distribution. McEliece has a public key that is a general linear code. A code is a bunch of linear equations constraining codewords, and codewords are vectors over a finite field, and decoding a code is solving those equations subject to errors from a given distribution. Sounds familiar? They’re not the same problem, and the distributions are different in rather fundamental ways (which may or may not make a difference), but they are quite related. I would not move my eggs to the McEliece basket right now. Hash-based signatures sound as safe as ever.
karl_gluck 3y ago
Check out the Winternitz One-Time Signature Sphere10.com/articles/cryptography/pqc/wots Signing many things with one identity is possible by precomputing a Merkle tree, but this takes time and the signatures get big.
- er4hn 3y ago
  SPHINCS+ is a complete signature scheme that carries that idea to it's completion. Shameless plug for where I explain it: https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/ https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step...
ihm 3y ago
There are a bunch of hash based signature schemes, e.g., SPHINCS https://sphincs.org/ https://sphincs.org/
somat 3y ago
Just remember that one time pads are not only one of the simplest encryption schemes they are proven secure in any quantum computing regime. It's a shame about the key transport problem. One of my favorite sci-fi macguffians, was in the book "Fire upon the deep" where they were space truckers with a cargo of one time pad keys.
- notfed 3y ago
  This is also true of most symmetric cryptography algorithms. (Of which one-time pad is one of. So is AES-256. It's more convenient to just use AES-256.) The implied context of "post-quantum cryptography" is usually asymmetric cryptography.

YoumuChan 3y ago

We don't even know the complexity class of factorization or discrete log, yet we still use those problems in DH, RSA, ECDSA, ...

eru 3y ago
All of those problems are known to be in NP and co-NP. In that sense, we know some complexity classes they belong to. However, we don't know if these bounds are tight, or whether they are eg in P, or something in between.
- keepamovin 3y ago
  We don't know that factorization is NP-complete> Show me a reduction from SAT to factorization. It's kind of trivial to say it's in NP because we can verify in P time, that's not a criticism of you just of the definition!! I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". By that definition of NP, we don't even know that it's in NP strictly because there could exist P algorithms for solving it. It's more in 'unknown-NP' if that were a class! hahaha! :)
  - SJC_Hacker 3y ago
    I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel. So maybe it should really be P and NDP.
    - keepamovin 3y ago
      That's a good explanation. I didn't know that.
    - eru 3y ago
      > or alternatively, a function executing on all inputs in parallel. I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses). But as long as your parallel executions don't interact at all, the definitions are identical, I think.
  - eru 3y ago
    > We don't know that factorization is NP-complete. Yes? No one ever said it was. None of the common cryptographic problems are expected to be NP-complete, even if they aren't in P. That's because they are known to be in both NP and in co-NP, and it's expected that NP != co-NP. > I think a better definition of NP is "only nonpoly algos can exist, no P algos can exist". In what sense is that a 'better' definition than the standard definition? It sounds like what you are talking about is NP\P (where \ is set subtraction, ie 'NP minus P').
    - keepamovin 3y ago
      I think some people have asked whether it was. I'm not saying you did, just thought it was interesting! Haha :) I don't even know what co-NP is. Could you explain? I think that's a better definition because I find it more predictive and useful to think about: pretty concrete to know that you can't have a polytime algo for it. Yeah, I guess what you're saying about NP\P is right in that it's a restatement of the definition of what I said, haha! I'm not an expert this is just what I think :)
- openasocket 3y ago
  I always found that part odd. I’d assume you would want the problem you build your crypto system built around to be NP-complete, since that would seem to put you on the firmest possible ground. And yet those are most likely not NP-complete, and I think the post-quantum systems proposed aren’t NP complete either. Maybe being NP-complete isn’t as important as I realize? Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system?
  - eru 3y ago
    No crypto-problem is NP-complete. People tried that for a while, see https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_cryptosystems but it didn't work. > Or maybe there’s something about NP-complete problems that make them less amenable to be a valid crypto system? To simplify a bit, the problem is that to work as a crypto system your particular problems needs to be both in NP and in co-NP. And we know of no problem that is both NP-complete and in co-NP. It's widely conjectured that there is no such problem. See https://en.wikipedia.org/wiki/Co-NP https://en.wikipedia.org/wiki/Co-NP that page even mentions integer factorisation. That's why you can't just take the NP-complete problem itself as a basis for your cryptosystem, you have to pick some subset of instances that's also in co-NP. And apparently it's almost impossible for us to pick such a subset, but still have the instances be hard enough to solve on average.

Vecr 3y ago

https://en.wikipedia.org/wiki/McEliece_cryptosystem https://en.wikipedia.org/wiki/McEliece_cryptosystem Yes, it's reasonably fast even at very long lengths, but the main problem is the very long lengths. Code based and not hash based though. Edit: not very fast to generate a key though. It's mostly used for non-ephemeral stuff.

amluto 3y ago
The new algorithm purports to solve LWE with certain choices of parameters. LWE is the problem of solving a linear system of equations over a finite ring, where each equation has an additive error from a certain distribution. McEliece has a public key that is a general linear code. A code is a bunch of linear equations constraining codewords, and codewords are vectors over a finite field, and decoding a code is solving those equations subject to errors from a given distribution. Sounds familiar? They’re not the same problem, and the distributions are different in rather fundamental ways (which may or may not make a difference), but they are quite related. I would not move my eggs to the McEliece basket right now. Hash-based signatures sound as safe as ever.

karl_gluck 3y ago

Check out the Winternitz One-Time Signature Sphere10.com/articles/cryptography/pqc/wots Signing many things with one identity is possible by precomputing a Merkle tree, but this takes time and the signatures get big.

er4hn 3y ago
SPHINCS+ is a complete signature scheme that carries that idea to it's completion. Shameless plug for where I explain it: https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/ https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step...

ihm 3y ago

There are a bunch of hash based signature schemes, e.g., SPHINCS https://sphincs.org/ https://sphincs.org/

somat 3y ago

Just remember that one time pads are not only one of the simplest encryption schemes they are proven secure in any quantum computing regime. It's a shame about the key transport problem. One of my favorite sci-fi macguffians, was in the book "Fire upon the deep" where they were space truckers with a cargo of one time pad keys.

notfed 3y ago
This is also true of most symmetric cryptography algorithms. (Of which one-time pad is one of. So is AES-256. It's more convenient to just use AES-256.) The implied context of "post-quantum cryptography" is usually asymmetric cryptography.