# Equivalent expression in English: Set Notation $\{0,1\}^K$

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.

• It's written on the slide – K is chosen at random from all binary strings of length $k$. – Yuval Filmus Jan 31 '17 at 22:03
• 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? – FutureUIUXDeveloper Jan 31 '17 at 22:12
• No, it has to have length exactly $k$. – Yuval Filmus Feb 1 '17 at 0:09

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$.
• 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. – Aristu Feb 1 '17 at 0:05
• @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 – David Richerby Feb 1 '17 at 9:13