1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$
    – T.Rocket
    Aug 29, 2022 at 14:10
  • 1
    $\begingroup$ @T.Rocket: if the attacker sees a ciphertext of 12, can he deduce anything about the plaintext? $\endgroup$
    – poncho
    Aug 29, 2022 at 14:45
  • $\begingroup$ 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. $\endgroup$
    – T.Rocket
    Aug 29, 2022 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.