Cryptography Slide

I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\{{0,1}\}^k$ stands for? Im looking for an explanation in English like what I did below.

$K_e = \text{Encryption Key} $
$K_d = \text{Decryption Key}$
$\mathcal{E}_K(M)$ = Encryption using Key with Message M

$D_K(C)$ = Decryption using Key with Ciphertext

$K \oplus M$

Right now I think $K$ is just the word length of the string. Meaning the key could be either $0^k$ or $1^k$ which corresponds to the key being $0$ or $1$ being repeated $k$ times. e.g. $0^3 = 000$ or $1^5 = 11111$. I believe this is wrong though.

  • $\begingroup$ It's written on the slide – K is chosen at random from all binary strings of length $k$. $\endgroup$ Commented Jan 31, 2017 at 22:03
  • $\begingroup$ So any combination of 0 or 1 bits up to length k is valid? Lets say k = 5 then are 0, 01, 100, 1111, 01001 valid keys that can be generated? $\endgroup$ Commented Jan 31, 2017 at 22:12
  • $\begingroup$ No, it has to have length exactly $k$. $\endgroup$ Commented Feb 1, 2017 at 0:09

1 Answer 1


In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$.

In your specific case $\{0,1\}^k$ is the set of functions from the natural number $k$ -- a set with $k$ elements -- to $\{0,1\}$. An element $M\in\{0,1\}^k$ is then a $k$-tuple of zeros and ones, i.e., a binary string of length $k$, as said by Yuval Filmus in a comment.

Note that not any combination of 0's and 1's up to length $k$ is valid, but only those with exact length $k$.

  • 1
    $\begingroup$ Also, $k$ need not be a finite, you can also have things like $\{0, 1\}^{\mathbb{N}}$, which is the set of all infinite sequences of 0's and 1's. $\endgroup$
    – Aristu
    Commented Feb 1, 2017 at 0:05
  • $\begingroup$ @melchizedek Well, the set of all sequences of order type (length) $\omega$. It's possible to have infinite sequences of other lengths but they don't tend to come up in computer science $\endgroup$ Commented Feb 1, 2017 at 9:13

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.