Is anything known about doing cryptography with very small keys?  In particular, is there any theory involving cryptosystems (based on whatever assumption you want) that can encrypt messages of length $n$ with key sizes $s = o(n^{\epsilon})$ for all $\epsilon>0$? (Assume $s$ is still largeenough that one cannot brute-force search through the space of keys.)If there is no theory, are there real-world cryptosystems that would still behave with such small keys and for which much better than brute-force attacks are not known?
Cryptography with very small keys
cr.crypto security
Short version: You want a crypto system that, with keys of length $k$, is secure against attackers with running time $2^{k^\epsilon}$, or even $2^{\Omega(k)}$. Most schemes that anyone would want to use in practice are conjectured to satisfy such bounds. Of course, we can't prove that they satisfy bounds like that without, at the very least, separating P from NP.Longer version:Concrete security provides the kind of theory I think you are looking for, since it foregoes coarse categorizations (polynomial versus not) in favor of specific bounds.For example, you can define a public-key cryptosystem to be $(t,\epsilon)$ secure if no attacker running in time $t$ has probability more than $1/2 + \epsilon$ of winning a chosen-plaintext indistinguishability game. Because the running time includes calls to the underlying encryption schemes, this provides security for messages of length roughly $t$. If you want to be even more precise, you can track running time ($t$) and queries to cryptosystem ($q$) separately. Under sufficiently strong assumptions about the primitives (e.g. exponentially hard to invert one-way permutations), one can construct cryptosystems that are $(t,\epsilon)$-secure for very large $t,q$ (close-ish to $2^{key\ length}$) and very small $\epsilon$.These types of bounds are used a lot in research papers (especially in the symmetric-key world). They appear less often in lecture notes and textbooks, because they introduce extra bookkeeping and can tax the notation-absorption skills of students.Luca Trevisan's lecture notes on crypto, though, use this notation; they might be a good resource to start with.