5 ms·

The Caesar cipher was based on obfuscation, not on computational complexity. It is not unreasonable to expect humanity to soon have enough knowledge to make unb

The Caesar cipher was based on obfuscation, not on computational complexity. It is not unreasonable to expect humanity to soon have enough knowledge to make unbreakable cyphers. We might very well already have such symmetric cyphers. If you count one time pads then we definitely do.

est31 8y ago
Shannon's theorem about perfect secrecy says that it is only attainable by ciphers that have similar key lengths to OTP. We can get a lot smarter but that theorem will stay.
- krastanov 8y ago
  I was left with the impression that if "good" random number generators exist, then this is not a problem: you use your small key as a seed to make the big key. And we do not have a reason yet to doubt the existence of such RNGs. Did I get this wrong? Edit: I think I was right, as the mathematical term "perfect secrecy" from the theorem is not particularly practical (lack of perfect secrecy does not imply the existence of a way to break the cypher). http://www.cs.miami.edu/home/burt/learning/Csc609.011/Perfect/ http://www.cs.miami.edu/home/burt/learning/Csc609.011/Perfec...
  - gizmo686 8y ago
    We have no particuarly good reason to believe in the exsitence of a good PRNG. Worse, we have no good reason to trust that any particular PRNG is good.
- admax88q 8y ago
  Good ol symmetric crypto is not easily broken by quantum computers. It is reasonable to think that we could or have already built a symmetric cipher that may never be broken.
  - gizmo686 8y ago
    Their key size is effectivly halfed. Not a big deal, but if quantom computers reach near parity with classical, we will need to increase our key sizes.
- gizmo686 8y ago
  Physics gives us some tools to meaningfully talk about "unbreakable" without perfect secrecy. In particular, we can currently reason about "unbreakable on any classical computer operating in an ambiant temperature no less than the cosmic microwave background, and consuming no more energy than exists in the universe". Physics still has some backdoors (notably reversable computing which, as far as I am aware, has no fundamental limit), but the bigger problem is that complexity theory has not advanced to a point where we can make meaningfull use of this. (The most I have ever seen is computing the lowerbound on energy to enumerate all keys. ) This is probably a solvable problem, but is going to be harder than p vs np.

est31 8y ago

Shannon's theorem about perfect secrecy says that it is only attainable by ciphers that have similar key lengths to OTP. We can get a lot smarter but that theorem will stay.

krastanov 8y ago
I was left with the impression that if "good" random number generators exist, then this is not a problem: you use your small key as a seed to make the big key. And we do not have a reason yet to doubt the existence of such RNGs. Did I get this wrong? Edit: I think I was right, as the mathematical term "perfect secrecy" from the theorem is not particularly practical (lack of perfect secrecy does not imply the existence of a way to break the cypher). http://www.cs.miami.edu/home/burt/learning/Csc609.011/Perfect/ http://www.cs.miami.edu/home/burt/learning/Csc609.011/Perfec...
- gizmo686 8y ago
  We have no particuarly good reason to believe in the exsitence of a good PRNG. Worse, we have no good reason to trust that any particular PRNG is good.
admax88q 8y ago
Good ol symmetric crypto is not easily broken by quantum computers. It is reasonable to think that we could or have already built a symmetric cipher that may never be broken.
- gizmo686 8y ago
  Their key size is effectivly halfed. Not a big deal, but if quantom computers reach near parity with classical, we will need to increase our key sizes.
gizmo686 8y ago
Physics gives us some tools to meaningfully talk about "unbreakable" without perfect secrecy. In particular, we can currently reason about "unbreakable on any classical computer operating in an ambiant temperature no less than the cosmic microwave background, and consuming no more energy than exists in the universe". Physics still has some backdoors (notably reversable computing which, as far as I am aware, has no fundamental limit), but the bigger problem is that complexity theory has not advanced to a point where we can make meaningfull use of this. (The most I have ever seen is computing the lowerbound on energy to enumerate all keys. ) This is probably a solvable problem, but is going to be harder than p vs np.