# Cardinality of the key space $\{0,1\}^\ell$

Imagine we have a scheme whose key is chosen from the set $\{0,1\}^\ell$.

My question is: What is the size of key space for this scheme?

• Should $\:\{\hspace{-0.03 in}0,\hspace{-0.04 in}1\hspace{-0.04 in}\}^{\hspace{-0.02 in}10}\:$ be replaced with $1024$? $\;\;\;$ If no, what does your $<$ symbol mean? $\hspace{1.54 in}$
– user991
Commented Jun 19, 2015 at 18:30
• @RickyDemer Yes, you right. Only for simplicity I just picked 10. But of course there should be $\{0,1\}^{l}$ where $l$ is security parameter. Commented Jun 19, 2015 at 18:38
• ... resulting in $2^l$? Commented Jun 19, 2015 at 19:24

For all $\ell\in\mathbb N$, the cardinality of the set $\{0,1\}^\ell$ is $2^\ell$.
This can be obtained inductively: We have $\{0,1\}^0=\{()\}$ (the empty tuple) which has cardinality $1=2^0$. If $\lvert\{0,1\}^\ell\rvert=2^\ell$, the elements of $\{0,1\}^{\ell+1}$ can be partitioned into two classes: The sequences that start with $0$ and those that start with $1$. Both (disjoint) partition classes admit a bijection to $\{0,1\}^\ell$, hence their cardinality is $2^\ell$. Therefore the cardinality of $\{0,1\}^{\ell+1}$ is $2\cdot2^\ell = 2^{\ell+1}$.