3 ms·

Placing no time constraints, my gut tells me it’s almost inevitable those breakthroughs will eventually come. Either in mathematics or quantum computing. Or bot

Placing no time constraints, my gut tells me it’s almost inevitable those breakthroughs will eventually come. Either in mathematics or quantum computing. Or both. Namely I’d ask when not if. My opinion is that short of the one time pad, we won’t come up with provably unbreakable schemes.

segfaultbuserr 3y ago
> Namely I’d ask when not if. The big assumption of cryptography is that, there exists some problems that are not provably unsolvable but difficult enough for almost any practical purposes. To engineers, no assumption can be more reasonable than that. Given unlimited time, it's a provable fact that any (brand new) processor with asynchronous input signal will malfunction due to metastability in digital circuits, it's also a provable fact that metastability is a fundamental flaw in all digital electronics - but computers still work because the MTBF can be made as large as necessary, longer than the lifetime of the Solar system if you really want to. So the only problem here is, how long is the MTBF of today's building blocks of symmetric ciphers? If it's on the scale of 100 years or so, sure, everything is breakable if you're patient. If it's on the scale of 1000 years, well, breaking it is "only" a matter of time. But if it's on the scale of 10000 years, I don't believe it's relevant to the human civilization (as we know it) anymore - your standard may vary. The problem is that computerized cryptography is a young subject, the best data we have so far is symmetric ciphers tend to be more secure than asymmetric ones. We know that Feistel networks have an excellent safety record and remain unbroken after 50 years. We also know that we can break almost all widely used asymmetric ciphers today with large quantum computers if we can build one, but we can't do the same to symmetric ones - even the ancient DES is unbreakable if it's redesigned to use 256-bit keys. So while nobody knows for sure, but most rational agents will certainly assign higher and higher confidence every year - until a breakthrough occurs. > My opinion is that short of the one time pad, we won’t come up with provably unbreakable schemes. Many mathematicians and some physicists may prefer a higher standard of security than "lowly" practical engineers. This is the main motivation behind quantum cryptography - rather than placing security on empirical observations, its slogan is that the security is placed on the laws of physics. Many have pointed that the this slogan is misleading: any practical form of quantum cryptography must exist in the engineering sense, and there will certainly be some forms of security flaws such as sensor imperfection or at least side channels... That being said, I certainly understand why it looks so attractive to many people if you're the kind of person who really worry about provability.
- galeaspablo 3y ago
  > your standard may vary. Agreed. My overall / initial point was that I can’t say the time to crack = the time to brute force and start talking about the age of the universe. Even if we had to wait 10,000 years for cryptanalysis to break AES, it’s a blink of an eye in sideral timescale. > quantum cryptography Quantum cryptography is helpful in detecting eavesdropping (due to the no clone theorem). Ie quantum cryptography is helpful in avoiding asymmetric encryption for key exchange when communicating with symmetric encryption. Eg BB84. And given asymmetric encryption is most vulnerable to quantum attacks (compared to symmetric), quantum cryptography improves today’s state of the art. BUT, I insist that none of this gives provably uncrackable schemes. AND it might be that we never build such a scheme. After all we have Godel’s incompleteness theorem lying around.

segfaultbuserr 3y ago

> Namely I’d ask when not if. The big assumption of cryptography is that, there exists some problems that are not provably unsolvable but difficult enough for almost any practical purposes. To engineers, no assumption can be more reasonable than that. Given unlimited time, it's a provable fact that any (brand new) processor with asynchronous input signal will malfunction due to metastability in digital circuits, it's also a provable fact that metastability is a fundamental flaw in all digital electronics - but computers still work because the MTBF can be made as large as necessary, longer than the lifetime of the Solar system if you really want to. So the only problem here is, how long is the MTBF of today's building blocks of symmetric ciphers? If it's on the scale of 100 years or so, sure, everything is breakable if you're patient. If it's on the scale of 1000 years, well, breaking it is "only" a matter of time. But if it's on the scale of 10000 years, I don't believe it's relevant to the human civilization (as we know it) anymore - your standard may vary. The problem is that computerized cryptography is a young subject, the best data we have so far is symmetric ciphers tend to be more secure than asymmetric ones. We know that Feistel networks have an excellent safety record and remain unbroken after 50 years. We also know that we can break almost all widely used asymmetric ciphers today with large quantum computers if we can build one, but we can't do the same to symmetric ones - even the ancient DES is unbreakable if it's redesigned to use 256-bit keys. So while nobody knows for sure, but most rational agents will certainly assign higher and higher confidence every year - until a breakthrough occurs. > My opinion is that short of the one time pad, we won’t come up with provably unbreakable schemes. Many mathematicians and some physicists may prefer a higher standard of security than "lowly" practical engineers. This is the main motivation behind quantum cryptography - rather than placing security on empirical observations, its slogan is that the security is placed on the laws of physics. Many have pointed that the this slogan is misleading: any practical form of quantum cryptography must exist in the engineering sense, and there will certainly be some forms of security flaws such as sensor imperfection or at least side channels... That being said, I certainly understand why it looks so attractive to many people if you're the kind of person who really worry about provability.

galeaspablo 3y ago
> your standard may vary. Agreed. My overall / initial point was that I can’t say the time to crack = the time to brute force and start talking about the age of the universe. Even if we had to wait 10,000 years for cryptanalysis to break AES, it’s a blink of an eye in sideral timescale. > quantum cryptography Quantum cryptography is helpful in detecting eavesdropping (due to the no clone theorem). Ie quantum cryptography is helpful in avoiding asymmetric encryption for key exchange when communicating with symmetric encryption. Eg BB84. And given asymmetric encryption is most vulnerable to quantum attacks (compared to symmetric), quantum cryptography improves today’s state of the art. BUT, I insist that none of this gives provably uncrackable schemes. AND it might be that we never build such a scheme. After all we have Godel’s incompleteness theorem lying around.