<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>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.</p>

<p>Luca Trevisan's lecture notes on crypto, though, use this notation; they might be a good resource to start with.</p>

CC BY-SA 3.0
2015-02-13T03:56:55.443Z
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!
Lev Reyzin
CC BY-SA 3.0
2015-02-14T02:15:56.133Z
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.
Adam Smith
CC BY-SA 3.0
2015-02-14T03:45:20.650Z
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 ..." ?
Lev Reyzin
CC BY-SA 3.0
2015-03-02T20:37:43.227Z
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?).
Lev Reyzin
CC BY-SA 3.0
2015-03-03T21:30:44.207Z
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?
Adam Smith
CC BY-SA 3.0
2015-02-13T03:44:25.483Z
2015-02-13T03:44:25.483Z
Adam Smith
<p>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&gt;0$? (Assume $s$ is still large
enough that one cannot brute-force search through the space of keys.)</p>

<p>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?</p>

CC BY-SA 3.0
2015-02-12T22:16:04.547Z
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?
Geoffrey Irving
CC BY-SA 3.0
2015-02-12T22:21:41.460Z
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?
Lev Reyzin
CC BY-SA 3.0
2015-02-12T22:24:16.643Z
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)$.
Geoffrey Irving
CC BY-SA 3.0
2015-02-12T22:29:12.300Z
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.
Lev Reyzin
CC BY-SA 3.0
2015-02-12T22:30:35.657Z
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.
Geoffrey Irving
<cr.crypto-security>
Cryptography with very small keys
Lev Reyzin
# Cryptography with very small keys

(Asked by: username_0 on 2015-02-12)

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?

**Tags:** cr.crypto-security

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_1**: 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)$.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-02-13. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  
> **username_2**: 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.  
> **username_0**: 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 ..." ?  
> **username_0**: 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?).  
> **username_2**: 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?  

---

