# Can one construct OTPs without using XOR?

The typical version of the one-time-pad (OTP) uses XOR to combine a key pad and a message. ($c=m\oplus k$)

Now let's assume some other scenarios which have the practical application of blinding. Do the below "OTP" constructions provide perfect secrecy?

1. The key $r\in (0;n)$ is chosen uniformly at random such that $r^{-1}\bmod n$ exists and shared between both parties. Furthermore both parties share some common modulus $n$ which may be an RSA-modulus or a prime. For a message $m\in (0;n)$, is the construction $c=m\cdot r \bmod n$ perfectly secure?
2. $r\in (0;n)$ is chosen uniformly at random and shared between both parties. Furthermore both parties share some common modulus $n$ which may be an RSA-modulus or a prime. For a message $m\in (0;n)$, is the construction $c=m + r \bmod n$ perfectly secure? (I strongly suspect the answer to be "yes" here as this is a "commonly" cited method for secret message transmission via radio where $n=10^4$)
• Hint: what does "perfect secrecy" mean? In addition, you need to consider what precisely do you mean by $r \in (0;n)$. Is that equivalent to $0 < r < n$? – poncho Aug 12 '15 at 12:24
• “$c = m \times r \bmod n$” reads like an average PRNG. Just to be sure: I hope you are not ignoring the fact that – when using an RNG-alike construction (which is not cryptographically secure) – you are not talking about OTP! (And yes, XOR is merely a binary operator… as an example, it could bluntly be replaced with a “$+$” for encryption and “$-$” during encryption.) – e-sushi Aug 12 '15 at 12:25
• Additional hint for 1.: How many $r\in\mathbb Z/n$ are invertible? – yyyyyyy Aug 12 '15 at 12:26
• @e-sushi, the question originated from my previous one yesterday. So no, I don't want to use this construction as PRNG but rather I'm wondering if the blinded version I get back over the wire is "perfectly secure". And as it looks now I'd say the answer is "it's not perfectly secure (because the space for $r$ is smaller than for $m$) but you can't also easily recover $m$ from $c$." – SEJPM Aug 12 '15 at 12:37
• Yep… that’s why I hinted at the fact that your requires the keyspace K to be as large as the message space M is part of the OTP definition. Dump that and you lose OTPs “perfect security”. ;) – e-sushi Aug 12 '15 at 12:55

Both constructions are not perfectly secure!

In an attempt to express things a bit more mathematically, I'd say you can implement a one-time-pad with a message $m$ and a key $r$, when

• $m$ and $r$ are elements of $\mathbb{Z}/n\mathbb{Z}$, the additive group of integers modulo n, or when
• $m$ and $r$ are elements of a group $G$ isomorphic to $\mathbb{Z}/n\mathbb{Z}$.

Such groups would be a natural choice to implement an OTP.

There are however also other possibilities. For instance one can easily imagine a perfectly secure OTP construction where the key $r$ is an element of a group $G$ and the message $m$ is an element of a subgroup of $G$. (The key is then larger than the message).

Now, lets come back to your constructions. In both constructions you assume $r,m\in \{1,...,n-1\}$ using the unconventional notation $r,m\in(0;n)$.

• Construction 1: You compute $c=r\cdot m$ mod $n$. If $n$ is a prime, then you have the multiplicative group of a prime field and it will work. As you already found out, it will not work when $n$ is composite.

• Construction 2: You compute $c=r+ m$ mod $n$. It would be perfectly secure if you had $\mathbb{Z}/n\mathbb{Z}$. However, since you exclude the 0 element, you know that you always have $m\ne c$, and it is thus not perfectly secure. :)

• Funfact: It's totally sufficient if $m,r,c\in \mathbb G$ with some group operation to get perfect security. The definition of the group guarantees that every element is invertible (-> exclude no $r$), that $c$ always lies in the same space / group as $m,r$ do and so forth. – SEJPM Aug 13 '15 at 10:16
• Ok, then I'll use the icosahedral rotation group . :) – Chris Aug 13 '15 at 11:34
• This should work... If you can get some random r and can actually express your message as group member. – SEJPM Aug 13 '15 at 11:43
• @SEJPM: Yes, what you're saying is correct! I have no doubt about that. – Chris Aug 13 '15 at 11:56
• Not any group will work; you need a group that admits a uniform distribution. For example, $\mathbb{R}$ doesn't work. But any finite group will work. – Chris Peikert Aug 14 '15 at 1:39

After those very helpful hints by poncho and yyyyyyy the answers are now obvious and I'll briefly argue why each of the construction is perfectly secure or not.

### Concerning construction 1:

It can't be perfectly secure because it has been proven that perfect secrecy (=perfect security) requires the keyspace $\mathcal K$ to be as large as the message space $\mathcal M$ which is obviously not the case for arbitrary moduli because of the constraint that $r$ must be invertible $\bmod n$ which requires that $gcd(n,r)=1$. For any composite moduli it is obviously the case that there exists at least two $r$ such that $gcd(n,r)\neq 1$ (namely it's factors). Meaning the keyspace is smaller than the message space, implying that it can't be perfectly secure. If $n$ is prime than the modulus is co-prime with all $r$ with $0<r<n$ meaning that both spaces are equally large. This also implies that for any message $m'$ there's an $r'$ such that $m'=r'^{-1}\times c \bmod n$ meaning that every message is equally likely implying perfect secrecy.

### Concerning construction 2:

The classic XOR-based OTP is this construction with $n=2$. This generalization (with $0$ being allowed for $m,r$) is secure because message and key space are both equally large and one can find an $r'$ for any message $m'$ such that $m'=c-r'\bmod n$ is constructible. Because an attacker can not decide which $r'$ is the "right" one he can't know when he found the correct key and thus this scheme is perfectly secure.
However the construction as given in the question is not perfectly secure (as pointed out by Chris' answer)because $0$ isn't a valid value for $r$ and hence it's impossible that $m=c$ which yields some information about $m$ and thus breaking perfect secrecy.

• I made this one a community wiki as the answer was basically given by poncho and yyyyyyy and thus it's not genuinly my answer. – SEJPM Aug 12 '15 at 12:54
• If any of the explanations is wrong feel free to re-formulate and correct. – SEJPM Aug 12 '15 at 12:55
• You're off by 1 in the prime case of construction 1; 0 has no multiplicative inverse. I think you noted that but then miscounted. – bmm6o Aug 12 '15 at 20:24
• @bmm6o, 0 is explicitly excluded from message- and keyspace in both constructions by saying they need to be in (0;n) which means 0<r<n and 0<m<n. – SEJPM Aug 12 '15 at 20:27
• Ah, you're right. I missed that it was also excluded from the message. – bmm6o Aug 12 '15 at 21:53