3 ms·

> For example, it could be possible that, if we generated a random map in some way, 99% percent of the time, the three-color map coloring problem would be easy,

> For example, it could be possible that, if we generated a random map in some way, 99% percent of the time, the three-color map coloring problem would be easy, but 1% of the time, it would be very difficult. > This would still be NP-complete, but would make for a terrible cryptosystem - a scheme based on this problem would be easily broken 99% of the time! I don’t think this explanation is great. We could just generate instances until we found the hard one and then use it. So the answer is more complex than just as written.

alexey-salmin 2y ago
I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.
- Vervious 2y ago
  That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.
cobbal 2y ago
The point is not that all NP hard problems make bad cryptosystems, but rather the NP-hardness guarantee fails to translate into a useful guarantee for a cryptosystem. It's about the proof, not the computation.
- ethanwillis 2y ago
  Can you explain your usage of NP hard in your comment?
  - saghm 2y ago
    A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems. https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
    - gpm 2y ago
      Not undecidable, it's just not possible to verify if an answer is correct in polynomial time. There are problems know to be decidable, known to be NP-hard and outside of NP. (E.g. in NEXPTIME)
      - saghm 2y ago
        Good to know! I guess I didn't recall as well as I thought.
Vervious 2y ago
how do you know if an instance you picked is hard? Another problem with your suggestion: Do we even know that a 1/polynomial sized fraction of 3-coloring instances are hard? (Else you'll never sample one). (NP-Hardness certainly does not give such a guarantee, even though it sounds weak)
goalieca 2y ago
RSA is kind of shaky like this. You generate key and then run some tests hoping it’s “good”. Most of the time it isn’t so you try again. Many products have failed because they were not.
- adgjlsfhk1 2y ago
  this mostly isn't true. for much smaller keys there were risks of "weak primes", but as general purpose factoring algorithms got better and pushed keys bigger a higher and higher percent of primes end up safe. with 2048 bit primes, the odds of your prime being significantly weaker than average drop to something like 1 in 2^1024
  - aleph_minus_one 2y ago
    What is a "weak prime" here (i.e. by which properties is such a prime number characterized)?
    - asimpletune 2y ago
      A prime pair that’s easily factorable
    - less_less 2y ago
      Suppose that p-1 has no large prime factors, eg suppose p-1 divides 10000!, then you can factor N by calculating something like x = random() ^ (10000!) % N. Then x will be 1 mod p (or rarely 0, if x was) but probably not mod q unless q has the same property. Then gcd(x-1,N) = p, and you've factored N. A similar trick works with Lucas sequences if p+1 has no large prime factors. So instead of attacking your key with a very expensive algorithm that doesn't care about special properties of p,q, they might gamble that your key is weak and try a cheaper algorithm first. So folks would avoid keys where p+1 or p-1 was "smooth" in this way. However, we don't care much about this attack anymore for two reasons. One is that N must now be big enough to resist attack by the Number Field Sieve (and not just the Quadratic Sieve). At least if there are only two primes in the RSA key, this means that p,q must be big enough for these attacks to be very unlikely to work. But just as importantly, it turns out that you can do the above attack with exponentiation on a random elliptic curve instead of regular exponentiation / Lucas sequences. This is how most math libraries implement factor(). It's slightly slower but since the random elliptic curve will have a random order instead of exactly p+1 or p-1, it is equally likely to work with any p,q of a given size, regardless of special properties they might have. In other words, an attacker can re-randomize how weak or strong a key is by using elliptic curves. So there's not much point in avoiding ones that look weak at first glance.
ars 2y ago
How do you know which ones are the hard ones? I don't think it's easy to figure that out.
ulrikrasmussen 2y ago
You don't know if the one you generated is hard. Graph coloring is easy for large but trivially connected graphs, and many many problem instances turn out to have structure that can be exploited to solve it efficiently. You would basically need to implement a procedure for determining the lower bound of the runtime of all known algorithms for the problem instance which is most likely very difficult, and even if possible, you don't know if your particular class of generated problems turns out to be easily solvable by a yet to be discovered algorithm. Amateur observation, take with a grain of salt: On the other hand, I guess we are doing something similar when generating a new public/private key pair on an elliptic curve. It just turns out that finite fields have very little (known) structure to exploit compared to e.g. colored graphs, so we have more confidence in the assumption that the generated discrete logarithm problem is indeed hard.

alexey-salmin 2y ago

I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.

Vervious 2y ago
That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.

cobbal 2y ago

The point is not that all NP hard problems make bad cryptosystems, but rather the NP-hardness guarantee fails to translate into a useful guarantee for a cryptosystem. It's about the proof, not the computation.

ethanwillis 2y ago
Can you explain your usage of NP hard in your comment?
- saghm 2y ago
  A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems. https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
  - gpm 2y ago
    Not undecidable, it's just not possible to verify if an answer is correct in polynomial time. There are problems know to be decidable, known to be NP-hard and outside of NP. (E.g. in NEXPTIME)
    - saghm 2y ago
      Good to know! I guess I didn't recall as well as I thought.

Vervious 2y ago

how do you know if an instance you picked is hard? Another problem with your suggestion: Do we even know that a 1/polynomial sized fraction of 3-coloring instances are hard? (Else you'll never sample one). (NP-Hardness certainly does not give such a guarantee, even though it sounds weak)

goalieca 2y ago

RSA is kind of shaky like this. You generate key and then run some tests hoping it’s “good”. Most of the time it isn’t so you try again. Many products have failed because they were not.

adgjlsfhk1 2y ago
this mostly isn't true. for much smaller keys there were risks of "weak primes", but as general purpose factoring algorithms got better and pushed keys bigger a higher and higher percent of primes end up safe. with 2048 bit primes, the odds of your prime being significantly weaker than average drop to something like 1 in 2^1024
- aleph_minus_one 2y ago
  What is a "weak prime" here (i.e. by which properties is such a prime number characterized)?
  - asimpletune 2y ago
    A prime pair that’s easily factorable
  - less_less 2y ago
    Suppose that p-1 has no large prime factors, eg suppose p-1 divides 10000!, then you can factor N by calculating something like x = random() ^ (10000!) % N. Then x will be 1 mod p (or rarely 0, if x was) but probably not mod q unless q has the same property. Then gcd(x-1,N) = p, and you've factored N. A similar trick works with Lucas sequences if p+1 has no large prime factors. So instead of attacking your key with a very expensive algorithm that doesn't care about special properties of p,q, they might gamble that your key is weak and try a cheaper algorithm first. So folks would avoid keys where p+1 or p-1 was "smooth" in this way. However, we don't care much about this attack anymore for two reasons. One is that N must now be big enough to resist attack by the Number Field Sieve (and not just the Quadratic Sieve). At least if there are only two primes in the RSA key, this means that p,q must be big enough for these attacks to be very unlikely to work. But just as importantly, it turns out that you can do the above attack with exponentiation on a random elliptic curve instead of regular exponentiation / Lucas sequences. This is how most math libraries implement factor(). It's slightly slower but since the random elliptic curve will have a random order instead of exactly p+1 or p-1, it is equally likely to work with any p,q of a given size, regardless of special properties they might have. In other words, an attacker can re-randomize how weak or strong a key is by using elliptic curves. So there's not much point in avoiding ones that look weak at first glance.

ars 2y ago

How do you know which ones are the hard ones? I don't think it's easy to figure that out.

ulrikrasmussen 2y ago

You don't know if the one you generated is hard. Graph coloring is easy for large but trivially connected graphs, and many many problem instances turn out to have structure that can be exploited to solve it efficiently. You would basically need to implement a procedure for determining the lower bound of the runtime of all known algorithms for the problem instance which is most likely very difficult, and even if possible, you don't know if your particular class of generated problems turns out to be easily solvable by a yet to be discovered algorithm. Amateur observation, take with a grain of salt: On the other hand, I guess we are doing something similar when generating a new public/private key pair on an elliptic curve. It just turns out that finite fields have very little (known) structure to exploit compared to e.g. colored graphs, so we have more confidence in the assumption that the generated discrete logarithm problem is indeed hard.