3 ms·
In cryptography, the goal is not to find problems that require O(n^k) steps to solve, but to find trapdoor one-way function families (the basis of public key cr
by SilasX 11y ago
In cryptography, the goal is not to find problems that require O(n^k) steps to solve, but to find trapdoor one-way function families (the basis of public key cryptography) where the easy direction is O(n) and the hard direction (without the private key) is O(n^k) for arbitrarily high k.
This would be easier to prove than O(exp(n)) and may even be quantum-computer resistant but I'm not sure if there are such cryptosystems, and if there are, they're not in common use since traditional models assume a polynomially strong adversary (as assumption we may want to relax).
- dllthomas 11y agoRight, relaxing the "it must grow faster than polynomial" might free up some new methods that we've foregone. But it's also the case that existing methods might still work fine - breaking them wouldn't be Omega(exp(n)), but may still have a high enough lower-bound for realistic values. Of course, if we discover that P=NP, getting at those lower bounds would be a priority...