Let's assume all operations are done on $$\mathbb{Z}_p$$ where $$p$$ is a large non-prime number.

To mask a value $$a$$, we do the following:

1. Pick a uniformly random value: $$r$$, from the ring.

2. Do as follows: $$c= r+a \bmod p$$.

Question: Is the above one-time pad secure?

• This looks like homework. What have you done to answer this question yourself? Where are you stuck? – yyyyyyy Apr 4 '19 at 14:32
• Asides from the question seemingly being homework, what do you mean by 'secure'? Perfectly secure? Computationally secure? – ElectronicToothpick Apr 4 '19 at 14:35
• my intuition is that it is secure at least computationally. – user153465 Apr 4 '19 at 14:36
• Hint: Look at your favourite proof of security for the OTP and see if you can adapt it to work with the new set / structure. – SEJPM Apr 4 '19 at 14:38
• Calling an explicitly non-prime integer variable $p$ is slightly confusing. I would suggest using a different character for it. Regarding the question, keep in mind that the addition of a ring is always a group, but not necessarily abelean. And thus they are always closed and inverse elements exist. Add to that, that uniform distributions only make sense for finite structures. – tylo Apr 4 '19 at 15:13

The classical xor-based one-time pad can be generalized to finite groups.

Let $$(G,*)$$ be such group with order $$p$$ and $$*$$ is the group operation(like the xor). The message, the pad and the ciphertext are elements of $$G$$.

Now to encrypt a message $$m \in G$$, choose $$k \in G$$ uniformly at random and set $$c = m * k$$. One of the security proofs of the one-time pad consists of showing that $$c$$ does not give any information on $$m$$(i.e to find $$m$$ we might as well pick a $$c'$$ at random and ignore $$c$$ completely).

More precisely, if $$M$$ is a random variable for messages distributed somehow, $$K$$ is a uniform random variable for the keys, and $$C = M*K$$ the random variables for the ciphertexts.

What we need to show is that $$C = M*K$$ is independent of $$M$$. i.e $$C$$ does not give any information on $$M$$.

Proof: We want to show that $$P_{C|M}[c|m] = P_C[c]$$. First, It's easy to see that $$C$$ defined as above is uniform(i.e $$P_C[c] = \frac{1}{|G|}$$). Next observe that $$P_{C|M}[c|m] = P_{K|M}[c*(m)^{-1}| m] = P_K[c*(m)^{-1}] = \frac{1}{|G|}$$. This follows form the fact that $$K$$ and $$M$$ are independent.

Therefore we showed the 'perfect secrecy' property of this constriction.