In SKE, can we assume without loss that the ciphers of a fixed plaintext distribute identically? Let $(KG,D,E)$ be a symmetric encryption scheme. Fix $sk\gets KG(\lambda)$ and an arbitrary plaintext $m$.
Generally speaking, $E_{sk}$ is not deterministic, so that $E_{sk}(m)$ is a random variable, which could distribute in many different ways.
Is there a way to generically transform such a scheme to a scheme in which, for any $m$ and $sk$, $E_{sk}(m)$ distributes uniformly on its support (or at least it is indistinguishable from uniform)? Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?
Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?

Yes, symmetric-key encryption implies the existence of &quot;uniform&quot; symmetric-key encryption. But I don't know of a particularly direct way to show it. Below is an extremely convoluted, theoretical, impractical way to do such a transformation.

If CPA-secure symmetric-key encryption schemes exist, then so do one-way functions. This is shown in Impagliazzo-Luby.

If one-way functions exist, then PRGs exist; this is the classic &quot;HILL&quot; result.

If PRGs exist then PRFs exist; this is the classic GGM result.

Once you have a PRF you can construct an authenticated encryption scheme based on counter mode with a MAC like Carter-Wegman. This scheme will have the property that you need, since the ciphertext is a deterministic function of the (uniform) initialization vector + key + plaintext, and no two choices of initialization vector give the same output (since the IV is included in the output). Hence the output is uniform over the support.