I am working on problem 2.1 in Introduction to Modern Cryptography 2nd edition by Katz and Lindell.

2.1) Prove that by redefining the key space, we may assume that the key generation algorithm $\textsf{Gen}$ chooses a key uniformly at random from the key space without changing $\Pr[C=c\mid M=m]$ for any $m,c$

We are told to define the key space to be the set of all possible random tapes for the generalized algorithm $\textsf{Gen}$.

I don't understand how we are supposed to prove that this algorithm $\textsf{Gen}$ chooses a key uniformly without knowing the algorithm itself. I am not really sure where to even start with this as I am new to proofs and crypto in general, and and all help will be useful!

What I do know:

$\textsf{Gen}$ is a probabilistic algorithm that outputs some key $k$ chosen according to some distribution. The finite key space $\kappa$ is the set of all possible keys that can be output by $\textsf{Gen}$

  • $\begingroup$ If you are "new to proofs", I suggest you also look into some sort of "intro. to higher mathematics" books to learn about writing and understanding proofs. Crypto proofs can get obtuse very quickly. $\endgroup$
    – fkraiem
    Mar 28, 2015 at 20:09
  • $\begingroup$ I am doing that currently as well, thank you for the suggestion! $\endgroup$
    – Bubo
    Mar 28, 2015 at 20:51
  • $\begingroup$ fkraiem, is there any way you could shed some light on this question for me? $\endgroup$
    – Bubo
    Mar 28, 2015 at 21:04
  • 2
    $\begingroup$ Hint: The fact that you don't know how Gen works means that you should be looking at what you do know about Gen. What do you know about it? $\endgroup$
    – cpast
    Mar 28, 2015 at 23:20
  • $\begingroup$ Thanks for the response! I know that Gen is a probabilistic algorithm that outputs some key k chosen according to some distribution. The (finite) key space, is the set of all possible output keys that can be output by Gen. $\endgroup$
    – Bubo
    Mar 29, 2015 at 1:08

2 Answers 2


Sorry for the late answer, I got busy...

So, you know that $\mathsf{Gen}$ is a probabilistic algorithm. What's a probabilistic algorithm? It's an algorithm which, during its execution, can make some random choices, which can be modeled as coin tosses. In programming terms, the algorithm can use a special coin-tossing function, which returns $0$ or $1$ each with probability $1/2$. The random tape is where the machine will write down the result of its coin tosses (or equivalently, where an external coin-tossing device will write the result of the tosses for the machine to read them). Because the results of the coin tosses are uniformy distributed, the contents of the random tape will be uniformly distributed as well and you can use that as your key.

Consider for example a cryptosystem with $\mathcal{K} = \{0,1\}$, and $\mathsf{Gen}$ as follows (in Python-like pseudocode):

def Gen():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    if coin1 == 0:
        return 0
    elif coin2 == 0:
        return 0
        return 1

It is clear that the key is not chosen uniformly: $0$ is chosen with probability $3/4$. Now, consider a cryptosystem with $\mathcal{K}' = \{(0,0),(0,1),(1,0),(1,1)\}$ and $\mathsf{Gen}'$ as follows:

def Gen'():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    return (coin1, coin2)

Now the key is chosen uniformly. Define encryption and decryption with the keys $(0,0)$, $(0,1)$ and $(1,0)$ to be the same as with the key $0$ in the previous system (whatever that is), and encryption/decryption with the key $(1,1)$ to be the same as with the key $1$. It is clear that you get essentially the same cryptosystem, but with the key chosen uniformly.

  • $\begingroup$ This works only when the original algorithm Gen generates keys 0 and 1 with rational probabilities. What if $Gen$ generates key 0 with probability 1/e, and key 1 with probability 1 - 1/e, how can you then construct Gen` with equally probable keys? $\endgroup$ Mar 13, 2021 at 11:02

Consider what it means for a key $k$ to be chosen according to some distribution over key space $\kappa$:

  • Assume that $\mathsf{Gen}$ picks key $k$ from key space $\kappa$ with probability $p$.
  • Since $\mathsf{Gen}$ is randomized, this means that a $p$-fraction of all the random tapes will lead it to generate $k$ as the key.
  • If we now conceptually redefine the key space to be the set of all the random tapes $\mathcal{R}$, then the probability of creating the particular value $k$ (which should no longer be consider a key) is still $p$. This is because the number of tapes that leads $\mathsf{Gen}$ to generate $k$ is still a $p$-fraction of all random tapes.
  • Then, because the probability $\Pr[C = c | M = m]$ is solely determined by the distribution of the values $k$, we see that this conceptual change of key space does not change the value of $\Pr[C = c | M = m]$.
  • However, the selection of keys (which are no longer the values $k$) is now uniformly distributed over the new key space $\mathcal{R}$.

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