Is 50% of bits changed in every round always gives 50% of changed bits in the end?

Question

Let's say we have a cipher with such property, that every round change 50% of bits in every block in average. Is it obvious or it means that after few rounds we will get exactly 50% changed bits?

If I think about it, it looks like it doesn't have to be like that. Next round can delete some changes from previous round and so on. In the end we we can get a different number of bits changed, even if each round changes exactly 50% of the bits.

Am I right? If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed? Can it be proven somehow or usually we have to rely on statistical tests?

Answer 1

If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed?

Well, obviously one can construct artificial examples where this doesn't happen; the most obvious (and trivial) being if round 1 and round 2 are inverses of each other (that is, round 1 followed by round 2 gives you the original plaintext); even if both rounds were individually ideal, we still don't get the avalanche effect after two rounds (even though we had it after one).

Symmetric ciphers are generally don't have enough structure to allow us to construct proofs that this doesn't happen (and adding structure generally makes the cipher weaker, not stronger; adversaries can also take advantage of structure); we generally have to rely on plausibility arguments.

Answer 2

Here is a different point of view. As pointed out in comments, you can make structured choices which mean all or half the bits are flipped. Instead let us consider a model where randomness is used.

Let $b$ be the blocklength, which is always even, in fact usually power of 2. To model the process , let us say we randomly flip half the bits (an integer since $b$ is even) in the first round; then randomly and independently of what happened in round 1, choose a subset of $b/2$ bits and flip them in the second round, and so on.

Since the process is independent, the eventual number of flipped bits, compared to the input vector, will be distributed as a binomial $\mathrm{Bin}(b,1/2).$

The probability that exactly half the bits are flipped is $$ 2^{-b} \binom{b}{b/2}\approx \frac1{\sqrt{\pi b}}. $$ Now this may look paradoxical, the probability that exactly half the bits are flipped is slowly going down with $b$. If $b=32,$ this probability calculated exactly is $0.134$ while for $b=128,$ it is halved to $0.070$ as expected from the approximation.

However there is no paradox. If we ask what is the probability that we are within 5% of exactly half the bits being flipped, we sum a few binomial coefficients around the middle coefficient, as in $$ 2^{-b} \sum_{\lceil (1-\epsilon)b/2\rceil}^{\lfloor(1+\epsilon)b/2\rfloor} \binom{b}{k}. $$ If $b=32,$ and $\epsilon=0.05$, this probability calculated exactly is $0.134$ while for $b=128,$ it is has increased to $0.464$ as expected from the approximation.