0
$\begingroup$

From what I understand, an elliptic contains a set points satisfying the equation

$y^2=x^3 + ax + b$

together with the point at infity.

It seems clear how multiplication with a scalar and a point works, and how point addition works. Discussions about cryptographic applications usually jump right to curves defined over finite fields at this point. I think I understand how that works as well.

What doesn't make sense is whether a curve defined over the field of real numbers could also work as a trapdoor.

If I know that point Q results from multiplication of some integer with the generator point on a curve over real numbers

$Q = dG$

what feasible methods exist to compute d given only a, b, and Q, and G?

In other words, aside from convenience in implementation, what exactly does the finite field add to elliptic curves as trapdoors?

I've seen this discussion, but it doesn't seem to directly address the question here.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Real numbers don't work real well in crypto, because we typically hope to be able to express the values we use, and almost all real numbers cannot be expressed, even with an unbounded number of bits. $\endgroup$
    – poncho
    Commented Nov 18, 2014 at 20:42
  • 2
    $\begingroup$ The other potential issue would be how real-based elliptic curves behave. If (say) the x-coordinate of $dG$ was approximately $c a^d$ for some values $c, d$, this would imply an efficient way to do logs (I almost wrote 'discrete logs'...) $\endgroup$
    – poncho
    Commented Nov 18, 2014 at 20:59
  • $\begingroup$ @pomch What do you mean that not all real numbers can be represented with an unbounded number of bits? $\endgroup$
    – Melab
    Commented Feb 27, 2018 at 15:39

1 Answer 1

Reset to default
1
$\begingroup$

First, as poncho correctly noted in a comment, real-based values don't work well with computers, because they require an infinite series / sequence representation and handling infinite amounts of data with a finite amount of storage usually doesn't end well, especially if you don't want to give away structure like in this case.

Second, picking keys is hard if you consider infinite ranges (even if there's an infinite amount of numbers between any two numbers), because you can't sample from an infinite set uniformly at random (then every element would have probability 0 of being picked).

Third, real-numbers often allow for more structure than we'd like. Take for example the logarithm. Computing $\log_3 b$ is easy in $\mathbb R$ (we know efficient algorithms that will yield a solid approximation) whereas finding this over $\mathbb Z_p$ tends to be hard. The fear is that a similar property can be found for the elliptic curve discrete logarithm problem. Also most problems over $\mathbb R$ are a matter of finding a good enough approximation where you can use intermediate approximations and have helpful navigatory metrics and thelike, whereas with crypto you want "hit-or-miss" and no guidance in the right direction.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can't sample from an infinite set, but you can sample from finite sets like the floating-point numbers in [0, 1]. This doesn't really address the question of computing elliptic curve discrete logs over the real numbers, which may actually be difficult—it's not clear that the real number logarithm has much connection to it, and I'm not sure anyone even knows how hard it is to compute discrete logs in elliptic curves over fields of characteristic zero. See also crypto.stackexchange.com/q/51198/49826 for a related discussion. $\endgroup$
    – Squeamish Ossifrage
    Commented Nov 5, 2017 at 22:21
  • $\begingroup$ @SqueamishOssifrage actually, you can't sample from the floating point numbers in [0,1] if you don't have defined maximal precision :p And the security-point of the answer is that "well I don't know whether it's actually hard, but look at this other group where it's quite easy so it may be very well easy here as well, so it's not unreasonable to expect it to not be harder than GF(p) based ECC". $\endgroup$
    – SEJPM
    Commented Nov 5, 2017 at 22:26
  • $\begingroup$ On the contrary, it is very easy to sample from the floating-point numbers in [0,1]. There is a finite number of them (for any particular floating-point system, e.g. IEEE 754 binary64, the one most of us encounter), and there is a natural discrete distribution on them which is easy to sample from given a uniform bit sampler. $\endgroup$
    – Squeamish Ossifrage
    Commented Nov 5, 2017 at 22:49
  • $\begingroup$ @SqueamishOssifrage IEEE754 floats do not form a field, so they are not suitable to define elliptic curves. $\endgroup$
    – fkraiem
    Commented Nov 6, 2017 at 3:23
  • $\begingroup$ @fkraiem: That doesn't mean you can't approximate arithmetic in elliptic curve over $\mathbb Q$ with floating-point arithmetic; the original question was about curves over $\mathbb R$. Does the approximation explode beyond the range of floating-point numbers? My intuition said yes, but fgrieu suggested otherwise. Is elliptic curve addition or scalar multiplication over $\mathbb Q$ well-conditioned? I don't know! My intuition says there's nothing useful down this path, but these are questions that it might be interesting to see an answer to, not just brushed off because of a hunch. $\endgroup$
    – Squeamish Ossifrage
    Commented Nov 6, 2017 at 3:40

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.