# Is one-time-pad still secure if the number of 1's in the key is revealed to the attacker?

For example, if $m = 10011$, $k = 11001$, $n=3$ (which is the number of 1's in k), $c = m \oplus k = 01010$. If $c$ and $n$ are revealed to the attacker, is this scheme still secure?

• Hint: what if you are given that $n = 1$? $n = 2$? How many keys does that rule out, and how many are left? (are they equiprobable?) Jul 7 '15 at 19:38
• Heh, what about $n = 0$ :) If an attacker gains more knowledge about $k$ any cipher will be less secure, including OTP. Jul 7 '15 at 22:50
• You definitely loose the information theoretic security. How bad it is depends on your $n$: In a bitstring of length $2x$ and hamming weight $x$, there are ${{2x}\choose{x}} \approx \frac{4^x}{\sqrt{\pi n}}$possibilities, which differs from the full $2^{2x}$ only by the denominator. However, the lower or higher values can give a lot of information about the key.
– tylo
Jul 8 '15 at 12:56

However, your proposal violates these principles. Assuming the key size (and plaintext size) is $S$, then the number of possible keys is not $2^S$ (i.e., all the possible keys of length $S$, as in the regular OTP), but $\binom{S}{n}$, which is much less than $2^S$. This has the consequence that for a given message $m$, not all possible ciphertexts are equiprobable, or conversely, for a given ciphertext not all possible messages are equiprobable (in fact, some of them have no probability).
Let's see it with your example. With regular OTP, for a length of 5 bits there are $2^5 = 32$ possible keys (as well as messages and ciphertexts). If an adversary gets $c$, there are 32 possible messages that correspond to that ciphertext. That is, the ciphertext is completely useless to the adversary. Now, in your proposal, for $n = 3$ there are $\binom{5}{3} = 10$ possible messages for a given ciphertext, since there are only 10 possible keys. The ciphertext $c$ and knowledge of $n$ makes possible to the adversary to deduce which 10 messages (out of the 32 possible) are related to the ciphertext. Therefore, he is gaining some knowledge about the original message.
• @JanLeo Sorry, that doesn't make any sense. The key should be of equal size than the ciphertext, therefore, $|k| = |c|$. And what is $r$? Jul 10 '15 at 19:38
• @cygnusy Sorry, that is a mistake. I mean if $|c|=256$ and $|n|=128$, then $|k|=\binom{|c|}{|n|}>2^{128}$. Is it computationally secure? Why key space should be of equal size to the ciphertext space? I don't need perfect security. If the key space is super-polynomial, then it is computationally-secure, isn't it? Jul 11 '15 at 7:31