Hacker News Reader

Comment by cvwright | Hacker News Reader

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…

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).

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.

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.

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.

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"

Reply on news.ycombinator.com