Timeline for Cryptography with very small keys
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2015 at 21:30 | comment | added | Adam Smith | I meant that AES is thought to be secure against time $2^{ck}$ attacks for a few specific values of $k$.You can shrink $k$ by fixing bits of the key to random, public values. Each such fixing will reduce the attack time by at most 2. Do you need a construction believed to be secure for arbitrary $k$? Do you just need it to exist, or do you need a specific, practical instantiation? | |
| Mar 2, 2015 at 20:37 | comment | added | Lev Reyzin♦ | I've looked up the definition of AES, and it seems it's not even defined for key lengths other than 128, 192, and 256 bits; but my question is about asymptotic behavior. So I'm a bit confused about @AdamSmith's comment. (Or is there a plausible definition of AES for larger keys?). | |
| Feb 14, 2015 at 17:07 | vote | accept | Lev Reyzin♦ | ||
| Feb 14, 2015 at 9:25 | comment | added | user6973 | A stronger conclusion: "we can't prove that they satisfy bounds like that without, $\hspace{1.01 in}$ at the very least," proving that $\:$SAT $\not\in$ SUBEXP $\;$. $\;\;\;\;$ | |
| Feb 14, 2015 at 3:45 | comment | added | Lev Reyzin♦ | Is there some clean assumption that would imply such security of AES (or any other cryptosystem)? Or would one write a theorem such as "If AES is secure against an attacker with f(k) time then ..." ? | |
| Feb 14, 2015 at 2:15 | comment | added | Adam Smith | I am fairly certain that AES is thought to be secure (as a pseudorandom permutation) against an attacker with $2^{ck}$ time and queries for some $c>0$. I'm not sure what the best conjecture for $c$ is. | |
| Feb 13, 2015 at 3:56 | comment | added | Lev Reyzin♦ | Thanks. So do we have systems that use keys of length $k$ and are thought to be secure against adversaries running a $2^{o(k)}$ algorithm! | |
| Feb 13, 2015 at 3:44 | history | answered | Adam Smith | CC BY-SA 3.0 |