4 ms·

Which order of n it is has no influence on crypto. The crux is whether there is a large difference in computing an answer and validating an answer. A technique

by dtech 11y ago

Which order of n it is has no influence on crypto. The crux is whether there is a large difference in computing an answer and validating an answer. A technique which requires both n^100 for validation and computing is useless, a technique which requires n^2 for computation and log(log(n)) for validation would be fine (you just have to use sufficiently large n). It's just that problems with an exponential computation and polynomial validation provide an almost unbeatable cost-to-benefit ratio in terms of n. A n^2/log(log(n)) algorithm might require 10MB encryption keys to be secure, while a n^a/n algorithm like the current prime-based cryptosystems require ~4KB.

Dylan16807 11y ago
Operations are not going to be sublinear. So that lower limit does make very small absolute orders matter. And I think it's implied that validation has to actually be possible on computers, so given that constraint an enormous number for brute-forcing will almost always be a solid option. So n^2/anything is going to suck. n^3/anything or n^4/anything may or may not suck. And n^100/n^small is great. Also RSA operations aren't n^a/n. They're sub-exponential to brute force, and n^3 to encrypt and decrypt. Unless you mean a different system.