Cryptography
one-time-pad
Updated Thu, 29 Sep 2022 04:16:53 GMT

(In)security of multiplicative blinding / one-time-pad in a commutative ring


As I understand, the one-time pad can be generalized to any finite group. So, for example, if you consider $\mathcal{P} := \mathcal{C} := \mathcal{K} := \{0, 1, ..., 2^{n}-1\}$ for an integer n, and you draw one-time keys $k$ uniformly from $\mathcal{K}$, then encrypting a plaintext $p$ by modular addition $c = p + k\; \text{mod}\; 2^{n}$ is perfectly secure. Similarly, if we constrain ourselves to a multiplicative group, we can use modular multiplication as a one-time pad where we decrypt by multiplying with the multiplicative inverse of the key.

My question is: What happens if we let $\mathcal{P} := \mathcal{C} := \{0, 1, ..., 2^{n} - 1\}$, but constrain the keyspace to $\mathcal{K} := P^{\times}$, i.e., the elements in $\mathcal{P}$ with multiplicative inverses (that would be the odd numbers), and use modular multiplication to encrypt each value. Does this entirely break the scheme, or is the degradation of the security limited in any way? Apart from obviously cutting the number of valid keys in half. Of course, since modular multiplication cannot encrypt "0", is guess we have to remove this value from plaintext and ciphertext space as well.

I realize this question is (somewhat?) related to the following question: Is multiplicative blinding less secure than additive?

However, the link in that question is no longer valid so the context of the answers is not quite clear.

Solution

Since this appears to be homework, I'll just give hints.

since modular multiplication cannot encrypt "0", is guess we have to remove this value from plaintext and ciphertext space as well.

Is the reason you remove 0 is that it's not a member of the group $P^{\times}$ (and so the proof of security would not apply there)? If so, what other potential plaintext elements are also not members of that group.

And, once you exclude those potential plaintext elements, does the general "it's a group, hence with equidistributed keys, you get a one-time pad" rule apply?

Comments (3)

  • +0 – Thanks for the answer. I suppose it sounds like a homework question, but it is just my own imagination. Regarding your hint: The reason I thought we had to remove 0 was because $0 \cdot k = 0$ so the plaintext is just mapped to itself. I suppose if we follow your hint, we just end up with the multiplicative group, and so we end up with the one-time pad. But what if we don't? Consider $n = 4$, message $m = 4 \notin \mathcal{P}^{\times}$ and $k = 3 \in \mathcal{P}^{\times}$. Then $k^{-1} = 11 (mod 16)$, and $c = 4 \cdot 3 = 12 (mod 16)$, and $m = 12 \cdot 11 \equiv 4 (mod 16)$. — Aug 29, 2022 at 14:10  
  • +1 – @T.Rocket: if the attacker sees a ciphertext of 12, can he deduce anything about the plaintext? — Aug 29, 2022 at 14:45  
  • +0 – Oh my, of course an even ciphertext would imply an even plaintext (and vice versa). I guess at the more fundamental level such a scheme could never work in terms of perfect secrecy anyways since the keyspace is smaller than than the plaintext space. But, this would break any similar "stream cipher"-construction in terms of IND-CPA hehe. — Aug 29, 2022 at 15:07  

External Links

External links referenced by this document:

References