1
$\begingroup$

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$?

$\endgroup$
3
  • $\begingroup$ Is this a homework question? $\endgroup$
    – Elias
    Commented Feb 23, 2018 at 6:57
  • $\begingroup$ 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? $\endgroup$
    – robinw
    Commented Feb 23, 2018 at 15:55
  • $\begingroup$ Congratulations, you have invented the one-time pad. $\endgroup$
    – fkraiem
    Commented Feb 23, 2018 at 16:46

1 Answer 1

2
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ Is it necessary that $n$ is a large prime? I am not sure what attack(s) will be possible if $n$ has small factors. $\endgroup$
    – robinw
    Commented Feb 23, 2018 at 16:20
  • $\begingroup$ @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$. $\endgroup$
    – user94293
    Commented Feb 23, 2018 at 16:29

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.