116 reputation
2
bio website
location
age
visits member for 2 years, 6 months
seen May 1 '12 at 20:37

Apr
25
comment Are asymptotic lower bounds relevant to cryptography?
Are there results of the kind you describe: concrete lower bound for "steps of calculation" to break AES or RSA? Or are you just saying that would be "more usable" if they did exist?
Apr
25
comment Are asymptotic lower bounds relevant to cryptography?
If a quantum computer were to be developed tomorrow, the world would have time to react, shifting to new forms of crypto. If a fast factoring algorithm were developed, there might be no lead time before it were deployable. In the realm of "anything could happen" the development of a new algorithm is hardly pie in the sky!
Apr
25
comment Are asymptotic lower bounds relevant to cryptography?
The same was true for Fermat's Last Theorem for 358 years.
Apr
25
awarded  Supporter
Apr
25
comment Are asymptotic lower bounds relevant to cryptography?
So if lower bounds are not the key to security, what makes us think that any particular system is secure (eg RSA)? Are security experts just hoping? I learned about public key cryptosystems in school, but now I don't know why I should have any confidence in them, even if P != NP and factoring is asymptotically hard and etc. etc
Apr
24
awarded  Student
Apr
24
comment Are asymptotic lower bounds relevant to cryptography?
There is no reason to bring P=NP into the discussion, or solutions by super-intelligent beings with computers that can guess big keys. Suppose I have a cryptosystem that is proven to be exponentially-hard to break, in the asymptotic sense. Does that characterization have any bearing at all on how secure it is in pratice? I would vote your answer down, but I lack the necessary reputation.
Apr
24
asked Are asymptotic lower bounds relevant to cryptography?