# Can the key-generation algorithm always be uniform?

Assume that the encryption uses $n$-bit keys to encrypt $l(n)$-length messages.

If a symmetric key encryption scheme is defined as $\Pi_{1} = ( \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, x_{1} \in \{0,1\}^{l(n)}$, $$\left\vert \Pr\left[ A (\mathrm{Enc}_{U_{n}}(x_{0})) = 1\right] - \Pr\left[ A (\mathrm{Enc}_{U_{n}}(x_{1})) = 1\right] \right\vert < \varepsilon(n)$$ if it is computational secure.

And if a symmetric key encryption scheme is defined as $\Pi_{2} = ( \mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, x_{1} \in \{0,1\}^{l(n)}$, $$\left\vert \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n)$$ if it is computational secure.

The definition of security is different because the definition of the encryption is different. Generally, we do not require that the distribution of $\mathrm{Gen}$ must be uniform. But it seems that the uniform distribution is always the best. So, if $\Pi_{2}$ is a computational secure scheme, I want to know whether there exists a PPT algorithm $\mathrm{Gen}'$ which is uniform such that $$\left\vert \Pr\left[\mathrm{Gen}'(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}'(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n)$$

• "Generally, the distribution of $Gen$ is not uniform. But it seems that the uniform distribution is always the best." What makes you think that "generally $Gen$ is not uniform"? It is supposed to be uniform for all symmetric ciphers using secret keys, right? Most symmetric ciphers use a key consisting of a specific number of random bits, usually generated by a seeded pseudo random number generator; you cannot get much more uniform than that. Or am I misunderstanding something about the question? – Maarten Bodewes May 7 '18 at 12:38
• I think lattice schemes use discrete gaussian sampling for key generation, which would be indeed non-uniform. – SEJPM May 7 '18 at 14:27
• @MaartenBodewes I modify it. Yes, for many schemes, $\mathrm{Gen}$ is uniform, but it is not necessary as for the definition. A result like this question may make me believe the uniform distribution is always the best. – TeamBright May 7 '18 at 14:32
• Define $Gen$ to be fully random but for a bit at the end. This bit at the end is set to zero 99 percent of the time. Now just use this bit to flip every bit after the ciphertext, encrypted using the other bits of the key. This scheme uses a non-uniform key generation and is still as secure as the original cipher. I think this positively proves that the output of $Gen$ doesn't need to be uniform to provide a certain level of security. It also breaks the assumption that an n-bit key provides around n-bits of security of course. – Maarten Bodewes May 7 '18 at 14:51
• I think this answer rather depends on the cipher. $Gen$ is specific to a cipher, so the existence of $Gen'$ also depends on the cipher. The output of $Gen$ must be acceptable to $Enc$ and $Dec$ after all. – Maarten Bodewes May 7 '18 at 14:55

For any symmetric encryption scheme, it is not a loss of generality to assume that the key is uniformly distributed: you can let the key be the random coins of the key generation algorithm $\mathcal G$, and incorporate the deterministic part of $\mathcal G$ (i.e., how it generates the key from its random coins) into the encryption and decryption algorithms.