1
$\begingroup$

There is a very popular method to represent a message $m$ (number) as a point on elliptic curve over a finite field:

  1. Set $i = 0$
  2. Check whether $m'=m\cdot K+i$ is on elliptic curve. If not, try again for $i+1$. If it is, compute such $y$ for $m'$ and you have point $(m', y)$

And it is very often said that chances of failure is $\frac{1}{2}^{k}$, because chances of point not being on elliptic curve is $\frac{1}{2}$. However, I can't find at least a brief proof of that.

$\endgroup$
2
  • $\begingroup$ This answer indicates that How to create an EC point from a plaintext message for encryptiont $\endgroup$
    – kelalaka
    Dec 4, 2023 at 16:35
  • $\begingroup$ That is: $x^3+ax+b$ is a square approximately half (QR/QNR) of all $x$, i.e. 50%. Therefore with only around $2^{-\kappa}$ probability this method will fail to embed a message to a point on $E$ over $\mathbb{F}_q$. $\endgroup$
    – kelalaka
    Dec 4, 2023 at 16:48

1 Answer 1

0
$\begingroup$

I'll restrict to a curve of equation $y^2\equiv x^3+ax+b\pmod p$ with prime $p$.

For a given integer $z\in[0,p)$, consider the number of integer solutions $y\in[0,p)$ for $y^2\equiv z\pmod p$. By Euler's criteria, there are

  • $2$ for $(p-1)/2$ values of $z$ known as quadratic residues modulo $p$ (those with $z^{(p-1)/2}\bmod p=+1\,$). Notice that if $y$ is a solution, that $p-y$ is another.
  • $1$ if and only if $z=0$. That solution is $y=0$.
  • $0$ for $(p-1)/2$ values of $z$ known as quadratic non-residues modulo $p$ (those with $z^{(p-1)/2}\bmod p=p-1\,$).

Under the first order approximation that one of the question's $m'$ for a certain $i$ yield $z=(m'^3+am'+b)\bmod p$ with probably of falling in either of the three cases mostly like for a random $z$, it would follow there's a solution $y$ making $(m′,y)$ on the curve with probability $\frac12+\frac1p$ (corresponding to the cases of $2$ or $1$ solutions). That probability converges to $\frac12$ for large $p$. Under the assumption that the probability is mostly independent for consecutive $i$, that yields probability near $\left(\frac12\right)^k$ of not finding a solution after trying $k$ values of $m'$, as asked.

This yields the correct result, but is far from rigorous. In particular, should we look at it closer, for curves of cryptographic interest, values of $a$, $b$ and $p$ are such that the case $(x^3+ax+b)\bmod n=0$ happens for no value of $x$. And the number of integers $x\in[0,p)$ such that the integer $z=(x^3+ax+b)\bmod n$ is among the cases with $2$ solutions is $(n-1)/2$, where $n$ is the order of the curve (that is the number of points on the curve plus the point at infinity), not $(p-1)/2$. However, by Hasse's theorem, $\left|n-1-p\right|\le\sqrt p$, thus $n/p$ converges to $1$ when $p$ grows, thus we have, rigorously now, a probability converging to $\frac12$ for large $p$ and random $i$. I know no proof that the probability is mostly independent for consecutive $i$, but that works well in practice.

$\endgroup$

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.