4
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ "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? $\endgroup$
    – Maarten Bodewes ♦
    Commented May 7, 2018 at 12:38
  • $\begingroup$ I think lattice schemes use discrete gaussian sampling for key generation, which would be indeed non-uniform. $\endgroup$
    – SEJPM
    Commented May 7, 2018 at 14:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Blanco
    Commented May 7, 2018 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented May 7, 2018 at 14:51
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented May 7, 2018 at 14:55

2 Answers 2

Reset to default
4
$\begingroup$

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.

For asymmetric encryption schemes, the same applies to the private key.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What if the random coins of G are not uniform? $\endgroup$
    – mercury0114
    Commented Mar 13, 2021 at 9:11
0
$\begingroup$

uniformness of key Generator algorithm is not necessary. Key generator algorithm only produces subkeys, that these subkeys used in every round to strengthen the cipher. It means that it is possible that some subkeys in some rounds may not give enough strength there, but the strength will be reached with the total of strengths that reached at the end of an encryption process. As an Example of linear structure of key Generator is DES that produces subkeys not in a uniform way and in a linear structure. It may possible you think about the weak and semi-weak keys of DES, But they don't relate about the key generator structure and the DES's own encryption structure causes this effect. We should remind that some attacks like related key attacks, use the weakness of key generator about producing subkeys that have a relation, but it does not mean that key Generator Algorithm should produce subkeys in a uniform way.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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