Prove that if we redefine the key space, we can assume Gen chooses a key uniformly 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}$
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
    else:
        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.