3 ms·

There are no proofs of the hardness of DDH or RSA etc. That’s why they’re called assumptions. OTOH if you want to win a Turing Award…

AnotherGoodName 1y ago
Just to add to the above for clarity a proof that key based encryption isn't reversible requires a proof of P!=NP which hasn't been done. That may surprise people but we have no proof of the robustness of the encryption we use. In fact it might not work! Consider a one time pad for really extreme security needs. One time pads do have a proof (see the work of Shannon).
- gary_0 1y ago
  Shor's algorithm suggests that a lot of encryption doesn't actually work, but of course it requires a quantum computer that hasn't yet been built, and may not be practical to build, so fingers crossed. At least there are quantum-resistant encryption algorithms, and OTPs are still provably secure like you say.
  - Tadpole9181 1y ago
    On "finger's crossed" - I think it's important to say that the majority of web traffic has switched over to PQC algorithms for key exchange that are not susceptible (thanks Cloudflare). We're not close to building a machine suitable for running Shor's in a practical sense, so even potential "store now, break later" attacks are now kinda pointless. Things like SSH keys are trivially revokable and often have enforced expirations, so they're not really a viable attack vector anyway. The symmetric encryption used for the vast majority of actual encryption has always been safe. Grover's algorithm does not scale appropriately (exponential on key length) unlike Shor's and cannot be parallelized. Worst case, AES-128 becomes as week as AES-64. So we bump it to AES-256 and we're back at the same difficulty as before (impossible). There's a degree of confidence this will always hold true.
vendiddy 1y ago
Can't someone learn this stuff with the assumption that certain functions are hard to invert? Like assuming f(x) is hard, let us try to prove these other properties of security.
- tgma 1y ago
  What you described is pretty much exactly how modern provable cryptography field works today. Reduction to assumptions about certain primitives and constructing the boundaries of security given such assumptions. E.g. "Assuming AES block cipher is a perfect pseudorandom function, prove AES-GCM construction is secure up to certain number of messages"

AnotherGoodName 1y ago

Just to add to the above for clarity a proof that key based encryption isn't reversible requires a proof of P!=NP which hasn't been done. That may surprise people but we have no proof of the robustness of the encryption we use. In fact it might not work! Consider a one time pad for really extreme security needs. One time pads do have a proof (see the work of Shannon).

gary_0 1y ago
Shor's algorithm suggests that a lot of encryption doesn't actually work, but of course it requires a quantum computer that hasn't yet been built, and may not be practical to build, so fingers crossed. At least there are quantum-resistant encryption algorithms, and OTPs are still provably secure like you say.
- Tadpole9181 1y ago
  On "finger's crossed" - I think it's important to say that the majority of web traffic has switched over to PQC algorithms for key exchange that are not susceptible (thanks Cloudflare). We're not close to building a machine suitable for running Shor's in a practical sense, so even potential "store now, break later" attacks are now kinda pointless. Things like SSH keys are trivially revokable and often have enforced expirations, so they're not really a viable attack vector anyway. The symmetric encryption used for the vast majority of actual encryption has always been safe. Grover's algorithm does not scale appropriately (exponential on key length) unlike Shor's and cannot be parallelized. Worst case, AES-128 becomes as week as AES-64. So we bump it to AES-256 and we're back at the same difficulty as before (impossible). There's a degree of confidence this will always hold true.

vendiddy 1y ago

Can't someone learn this stuff with the assumption that certain functions are hard to invert? Like assuming f(x) is hard, let us try to prove these other properties of security.

tgma 1y ago
What you described is pretty much exactly how modern provable cryptography field works today. Reduction to assumptions about certain primitives and constructing the boundaries of security given such assumptions. E.g. "Assuming AES block cipher is a perfect pseudorandom function, prove AES-GCM construction is secure up to certain number of messages"