2
$\begingroup$

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 large enough 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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Aren't all current cryptosystems like this? Do you have an example of a system where key size isn't $O(1)$ as a function of message length? $\endgroup$
    – Geoffrey Irving
    Commented Feb 12, 2015 at 22:16
  • $\begingroup$ In practice, one uses a fixed key length, but this is not justified if you give the adversary poly$(n)$ time to break the key. Also, is a fixed-size key sufficient to encrypt arbitrary size messages in practice? $\endgroup$
    – Lev Reyzin ♦
    Commented Feb 12, 2015 at 22:21
  • 2
    $\begingroup$ The key size depends only on the computational power of the attacker, not on the message length. If you give the attacker time $t$, elliptic curve cryptosystems for example need keys of size $O(\log t)$. If $t = \operatorname{poly}(n)$, this is $s = O(\log n)$. $\endgroup$
    – Geoffrey Irving
    Commented Feb 12, 2015 at 22:24
  • $\begingroup$ My understanding is that the usual assumption is that an adversary is poly-time bounded in the length of the messages. If you use $\log(n)$ keys, the adversary can just brute-force them in poly$(n)$ time. $\endgroup$
    – Lev Reyzin ♦
    Commented Feb 12, 2015 at 22:29
  • 6
    $\begingroup$ I don't think that's the usual assumption. It's routine in cryptography to want to send a few bits at a time securely. When you do this, it is bad to assume the attacker suddenly has only $O(1)$ time. The security parameter is usually kept entirely separate from the message length. $\endgroup$
    – Geoffrey Irving
    Commented Feb 12, 2015 at 22:30

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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! $\endgroup$
    – Lev Reyzin ♦
    Commented Feb 13, 2015 at 3:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Adam Smith
    Commented Feb 14, 2015 at 2:15
  • $\begingroup$ 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 ..." ? $\endgroup$
    – Lev Reyzin ♦
    Commented Feb 14, 2015 at 3:45
  • $\begingroup$ 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 $\;$. $\;\;\;\;$ $\endgroup$
    – user6973
    Commented Feb 14, 2015 at 9:25
  • $\begingroup$ 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?). $\endgroup$
    – Lev Reyzin ♦
    Commented Mar 2, 2015 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.