In cryptography, why do we reduce elliptic curves over finite fields?

927 Views Asked by At

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?

2

There are 2 best solutions below

0
On BEST ANSWER

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.

0
On

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.