4 ms·

So there's a problem we have with today's cryptography that we basically have to hope it's secure, but we can't proove it. It's basically "enough people looked

by hannob 6y ago

So there's a problem we have with today's cryptography that we basically have to hope it's secure, but we can't proove it. It's basically "enough people looked at it, noone found a way to break it, it should be okay". That's what we have, but it's not really comforting. Now if you think what it'd mean to proove that e.g. a public key crypto system is secure, it almost implies that you'd need to proove p!=np before that. I.e. prooving p!=np would not proove that cryptography is secure, but it may be the first step and the understanding gained from prooving p!=np may mean that there's a much better understanding of complexity in general, which will help.

fooker 6y ago
What has cryptography got to do with p!=np ?
- macmmajor 6y ago
  If p == np, then interger factorization can be reduced to k-sat, which is solvable in p time https://cs.stackexchange.com/questions/6650/how-can-p-np-enhance-integer-factorization https://cs.stackexchange.com/questions/6650/how-can-p-np-enh...
  - fooker 6y ago
    Neat, thanks!
  - raverbashing 6y ago
    > then integer factorization can be reduced to k-sat, It can be reduced already, but then 3-sat can be solved in P time
- js8 6y ago
  If P=NP, then you can invert in polynomial time (assuming this is practical) arbitrary boolean functions and thus solve any equations (that can be specified as a boolean circuit), find keys to any cryptosystem etc. For example, you can assume part of the plaintext (like a header in transmission) and solve an equation (which can be restated as a SAT instance) that yields you a key assuming certain cryptographic algorithm was used. So pretty much all cryptography relies on P!=NP.
- tgflynn 6y ago
  If there's an efficient algorithm for solving NP-complete problems then 99% of current cryptography would be broken. Only one-time-pads would still be secure. But don't worry, if that happens the world would be so different there might no longer be a need for cryptography.
  - rrobukef 6y ago
    There exist crypto systems independent on P vs NP, both symmetric and asymnetric. The general approach exploits polynomial time complexity differences. However key-sizes increase accordingly: last I saw a key-pair was a few 100's of megabytes. (an enourmous reduction from originally GB's)
    - tgflynn 6y ago
      But there aren't a lot of proven bounds on polynomial time complexity either. For all we know it may be possible to solve 3-SAT in linear time.
SilasX 6y ago
And even then, we'd need to invent a cryptosystem whose hardness depends on an NP-complete problem, and be able to reliably find hard instance of that problem. There are interesting attempts at that which have failed e.g. the Knapsack cryptosystem: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...

by hannob 6y ago

fooker 6y ago

What has cryptography got to do with p!=np ?

macmmajor 6y ago
If p == np, then interger factorization can be reduced to k-sat, which is solvable in p time https://cs.stackexchange.com/questions/6650/how-can-p-np-enhance-integer-factorization https://cs.stackexchange.com/questions/6650/how-can-p-np-enh...
- fooker 6y ago
  Neat, thanks!
- raverbashing 6y ago
  > then integer factorization can be reduced to k-sat, It can be reduced already, but then 3-sat can be solved in P time
js8 6y ago
If P=NP, then you can invert in polynomial time (assuming this is practical) arbitrary boolean functions and thus solve any equations (that can be specified as a boolean circuit), find keys to any cryptosystem etc. For example, you can assume part of the plaintext (like a header in transmission) and solve an equation (which can be restated as a SAT instance) that yields you a key assuming certain cryptographic algorithm was used. So pretty much all cryptography relies on P!=NP.
tgflynn 6y ago
If there's an efficient algorithm for solving NP-complete problems then 99% of current cryptography would be broken. Only one-time-pads would still be secure. But don't worry, if that happens the world would be so different there might no longer be a need for cryptography.
- rrobukef 6y ago
  There exist crypto systems independent on P vs NP, both symmetric and asymnetric. The general approach exploits polynomial time complexity differences. However key-sizes increase accordingly: last I saw a key-pair was a few 100's of megabytes. (an enourmous reduction from originally GB's)
  - tgflynn 6y ago
    But there aren't a lot of proven bounds on polynomial time complexity either. For all we know it may be possible to solve 3-SAT in linear time.

SilasX 6y ago

And even then, we'd need to invent a cryptosystem whose hardness depends on an NP-complete problem, and be able to reliably find hard instance of that problem. There are interesting attempts at that which have failed e.g. the Knapsack cryptosystem: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...