5
$\begingroup$

What's wrong with real numbers? Is the continuous logarithm problem "easy" to solve for elliptic curves?

Here's what I believe: elliptic curves over the real numbers have infinitely many points, many of them can't be represented by a computer (either because of floating point precision, or because of memory limitations). The discrete logarithm problem is not harder than the continuous one.

Is it right?

$\endgroup$
  • $\begingroup$ The discrete log problem only makes sense in cyclic groups. The group $E(\mathbb{R})$ will not be cyclic, so it's not clear what you would mean by the discrete log problem. I suppose you could pick an infinite cyclic subgroup of $E(\mathbb{R})$ but my guess would be that there is an analytic attack on discrete log in this case. $\endgroup$ – hunter Feb 18 '15 at 14:49
  • $\begingroup$ @hunter With "discrete logarithm problem" I mean: given X and Y, find n : nX = Y. $\endgroup$ – hey hey Feb 18 '15 at 14:51
  • $\begingroup$ Sure, but there is no solution for an arbitrary $X, Y \in E(\mathbb{R})$ because it is not a cyclic group. $\endgroup$ – hunter Feb 18 '15 at 14:56
  • 1
    $\begingroup$ @DylanYott: in the case of elliptic curve cryptography, we always use cyclic groups ($E(F_p)$ where $p$ is prime or a power of a prime). $\endgroup$ – hey hey Feb 18 '15 at 15:20
  • 2
    $\begingroup$ I'm not sure whether analytic attacks on DLP of $E(\Bbb{R})$ exist and would work well, but storing full precision real (or complex) numbers with infinite precision is a problem. Also different points on $E(\Bbb{R})$ may (will?) require different precision. In comparison $E(\Bbb{F}_q)$ is nice and clean. You know exactly how many bits you need to store a point. Compare to number of bits you need to store points on $E(\Bbb{Q})$ already. After a couple of point additions the numerators and denominators become huge. $\endgroup$ – Jyrki Lahtonen Feb 18 '15 at 15:53
1
$\begingroup$

Is the continuous logarithm problem "easy" to solve for elliptic curves?

The answer to that appears to be, we don't know. I don't know of any results that say it is easy or hard.

What's wrong with real numbers?

You mention one problem, representation on a computer with finite memory. This will result in rounding error, which is unsuitable for cryptography.

Another issue is speed. Working in the reals on a computer is much slower than working in a finite field. Finite field arithmetic on a computer is very fast.

Another thing to consider.

Let's say instead of working in $E(\mathbb{R})$ we work in $E(\mathbb{Q})$. This should be faster and not have rounding error. However, analyzability suffers in this case. When working over a finite field, we can say things about the order of the resulting group, the order of elements, etc. This all helps in analyzing the cryptosystem because we need all (or most) instances of a problem to be hard to solve, not just some. Analyzability is critical in cryptography these days.

$\endgroup$
2
$\begingroup$

In cryptography, numbers are not used as a measurement of a quantity; its simply a tag (a primary key in a data base). So two numbers close to each other means nothing about the objects for which they are tags. That is in internet banking instead of paying from the account of a person with a specific credit card number N, if we pay from a nearby number $N+k$ with $k\ll N$, it is no use. And as you suggested representing a real number in a computer will introduce round-off errors and depositing money into an account whose number agrees with my account number with $99.99\%$ accuracy does not make me $99.99\%$ happy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.