That reminds me of the Enigma machines in WWII: The thing was set up such that a given letter in plaintext could not end up as that same letter in cyphertext. This was supposedly to add security, but it turned out not only to be a weakness, but one that was critical in breaking the code.

That one makes sense, in a way: If you see a S in cyphertext, you know the plaintext did not have an S in that position. That eliminates 4% of all possible plaintexts, and by extension 4% of all private keys. That's kind of a metric ass-ton of entropy you just lost right there, for every single character.

My guess is, your proof works by a qualitatively similar principle: Restricting the keyspace, no matter how trivially, gives the attacker information. And encryption is all about magnifying information.

I think you meant "could not end up as that same letter"?

Usually that's an indication that the specific mathematical property that you're proving is not what we mean when we say 'secure'.

Yes, but in a good way, generally it's far stronger than our common sense idea of "secure".

I meant quite the opposite, that if what the GP said is true, than the specific theorem being proved does not share the properties implied by the common sense idea of "secure," and is therefore insufficient.

That's not neccessary true. Take for example, in the case where the proof shows that resulting ciphertext would be indistinguishable from a random function, so the adversary would have 1/2^n (with n = key length, 128/192/256 etc, ) chance to decipher the text by guessing the key uniformly random. And he also has another 1/2^n chance to break the system, by us picking the null key (randomly). That would result in the chance of 1/2^(n-1)

On the other hand, the proof shows that leaving the null key out of sample space means the adversary would have 1/2^48 (arbitrary number) to distinguish the ciphertext from a random function, which means that it's "insecure" in the context of the proof.

It seems to me that this notion of secure would still be stronger than our common sense idea of "secure".