This is from Dan Boneh's book

4.5 Constructing block ciphers from PRFs

Let F be a PRF, defined over $(K, X, X)$, where $X = \{0, 1\}^n$. We describe a block cipher $\varepsilon = (E, D)$ whose key space is $K^3$, and whose data block space is $X^2$.

Given a key $(k1, k2, k3) \in K^3$ and a data block $(u, v) \in X^2$, the encryption algorithm E runs as follows: (snipped)

What exactly is $K^3$ & $X^2$ here? Why has the KeySpace been cubed & the datablock space been squared?


What exactly are $K^3$ and $X^2$ here?

The notation $K^3$ where $K$ is the set of keys $k$ stands for $K\times K\times K$, that is the set of triplets $(k_1,k_2,k_3)$ with $k_1\in K$, $k_2\in K$, $k_3\in K$. When $K=\{0,1\}^n$ (the set of $n$-bit bitsrings), we can assimilate $K^3$ to $\{0,1\}^{3n}$ (mathematicians do this when there's a trivial bijection between two sets; here that's concatenation of bitstrings in one direction, and splitting into 3 equaly-sized bitstrings in the other).

Similarly the notation $X^2$ where $X$ is the set of blocks $x$ stands for $X\times X$, that is the set of pairs $(x_1,x_2)$ with $x_1\in X$, $x_2\in X$. When $X=\{0,1\}^b$, we can assimilate $X^2$ to $\{0,1\}^{2n}$.

Why has the key space been cubed and the block space been squared?

That must be the objective of the skipped construction. Increasing the keyspace is easy and there's one common example: 3DES cubes or squares the keyspace, leaving the blockspace unchanged. Increasing the blockspace is slightly trickier.

The cardinality of the key space is cubed: it goes from $2^n$ to $2^{3n}=\left(2^n\right)^3$. The cardinality of the block space is squared: it goes from $2^b$ to $2^{2b}=\left(2^b\right)^2$.

  • $\begingroup$ Thank you - I was wondering if the cardinality of the Key Space has also got cubed. From your answer, quite obviously, it hasn't. $\endgroup$
    – user93353
    Dec 22 '20 at 6:38
  • $\begingroup$ @user93353: uh, that's incorrect. See additional last paragraph in the answer. $\endgroup$
    – fgrieu
    Dec 22 '20 at 6:42
  • $\begingroup$ No, I understand that the total keyspace has got cubed when 3 keys are used. But I was wondering if each key k1, k2 & k3's keyspace itself increased. Which hasn't. $k1, k2, k3 \in K^3$ is quite confusing. Better way would be to write it as $k1 || k2 || k3 \in K^3$ $\endgroup$
    – user93353
    Dec 22 '20 at 7:14
  • $\begingroup$ If you want to do an exhaustive search, it would be $2 powerof |K|^3$ - that I understand $\endgroup$
    – user93353
    Dec 22 '20 at 7:15
  • $\begingroup$ @user93353: the formal notation is $(k_1,k_2,k_3)\in K^3$. One would often write (slightly incorrectly) $k_1,k_2,k_3\in K$. Indeed $k_1,k_2,k_3\in K^3$ can be confusing, but is also seen. An exhaustive search would have cost ${|K^3|}\ =\ |K|^3$, not $2^{\left(|K|^3\right)}$ or $\left(2^{|K|}\right)^3\,=\ 2^{\left(3\,|K|\right)}$ [corrected]. $\endgroup$
    – fgrieu
    Dec 22 '20 at 7:27

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.