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?

  • $\begingroup$ 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}$ $\endgroup$
    – user991
    Commented Jun 19, 2015 at 18:30
  • $\begingroup$ @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. $\endgroup$
    – user13676
    Commented Jun 19, 2015 at 18:38
  • $\begingroup$ ... resulting in $2^l$? $\endgroup$
    – SEJPM
    Commented Jun 19, 2015 at 19:24

1 Answer 1


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}$.


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.