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?

  • 2
    $\begingroup$ This looks like homework. What have you done to answer this question yourself? Where are you stuck? $\endgroup$ – yyyyyyy Apr 4 at 14:32
  • $\begingroup$ Asides from the question seemingly being homework, what do you mean by 'secure'? Perfectly secure? Computationally secure? $\endgroup$ – ElectronicToothpick Apr 4 at 14:35
  • $\begingroup$ my intuition is that it is secure at least computationally. $\endgroup$ – user153465 Apr 4 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – SEJPM Apr 4 at 14:38
  • 1
    $\begingroup$ 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. $\endgroup$ – tylo Apr 4 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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