2
$\begingroup$

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.

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

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

$\endgroup$
  • 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 Feb 1 '17 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$ – David Richerby Feb 1 '17 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.