# Elliptic Curves and Small Message Space

Let $G$ be the generator of an elliptic curve $E$ of order $n$. Let $M$ denote a small (say, size $2^8$) message space. Elements of $M$ are mapped to points in $E$; the mapping is considered public. Let $s$ be a randomly choosen (secret) number from $[1,n-1]$. For some $m\in M$, is it computationally tractable to recover $m$ from an encoding of the form $sG+m$?

• Is this a homework question? Commented Feb 23, 2018 at 6:57
• No. I know that the public mapping of the message $m$ can be expressed as $kG$. So the resulting encoding is of the form $(s+k)G$, which should be difficult to solve for $s$ even if $k$ has only $2^8$ known values. What I want to be sure is that the generator $G$ does not have any properties (that I am unaware of) to make this tractable? Commented Feb 23, 2018 at 15:55
• Congratulations, you have invented the one-time pad. Commented Feb 23, 2018 at 16:46

Define $\mathbb{G} = \langle G \rangle$ the cyclic group generated by $G$. The order of $\mathbb{G}$ is $n$.
In your scheme, an 8-bit message is encoded as a point $m = kG$. An attacker gets access to the value of $sG + m$ for a random $s \in [0,n-1]$. The question is: can the attacker recover the value of $m$ (and then the value of the corresponding message)?
The answer is no. To see it, observe that the point $S = sG$ is a uniformly random element in $\mathbb{G}$. As a result, the point $S + m$ is in turn a uniformly random element in $\mathbb{G}$.
• Is it necessary that $n$ is a large prime? I am not sure what attack(s) will be possible if $n$ has small factors. Commented Feb 23, 2018 at 16:20
• @robinw: No. The elements of $\mathbb{G}$ are $\{\mathcal{O}, G, 2G, 3G, \dotsc, (n-1)G\}$. All these elements are different (and thus equiprobable) because $G$ has order $n$. Commented Feb 23, 2018 at 16:29