5
$\begingroup$

Many elliptic-curve cryptosystems today use GF(p) or GF(2^m). What if, say, we use big floating numbers with the classical point addition formulas - is a cryptosystem possible to build on that?

$\endgroup$
  • 2
    $\begingroup$ Yes, but you'll lose a property: the security. The point addition formulas are the same: usually the graphical explanation is given on a curve over the real numbers. So you can imagine to define your cryptosystem as usual over the Real. But it won't be secure. $\endgroup$ – ddddavidee Aug 30 '17 at 11:39
  • 1
    $\begingroup$ Never forget to ask yourself if what you're trying to do actually makes sense, or if it wouldn't be smarter to rely on existing well-vetted solutions. No matter how often I read your question, I fail to see why you would want to modify an existing cryptographic design in a way so that is uses floating point numbers. What are you hoping to gain by doing so? Which cryptographic problem(s) would such a design solve? $\endgroup$ – e-sushi Aug 30 '17 at 11:45
  • 2
    $\begingroup$ @ddddavidee: I can foresee a feasibility problem, but why the security loss? I do not see that the discrete logarithm problem (or should we say point division) is trivial on the group defined by point addition on an elliptic curve on $\mathbb R^2$, especially if the coordinates of $k\times g$ are truncated to little more than necessary to uniquely define the secret integer $k$. If it is indeed a hard problem, and if it was possible to work around the serious issues of numerical stability and how wide the coordinates should be, I do not rule out that ECDH or ECIES could be made to work. $\endgroup$ – fgrieu Aug 30 '17 at 11:51
  • 3
    $\begingroup$ @fgrieu: if you're doing ECC, it's important that properties such as $a(bG) = b(aG)$ are preserved. If you truncate the intermediate values $bG, aG$, does this still hold? $\endgroup$ – poncho Aug 30 '17 at 12:52
  • 2
    $\begingroup$ To build on the comment of @Poncho I guess there is a rather fundamental issue. Modern crypto is performed over bits / bytes. These can be easily mapped to large integer values, for instance by simply interpreting them as an unsigned number. Although we can do the same for floating point numbers, any loss of precision will mean loss of data. Any scheme that uses floating point must be programmed in such a way that loss of data due to loss of precision isn't possible. Even if that is possible it would probably not be all that easy nor efficient. FP usually doesn't make sense in crypto. $\endgroup$ – Maarten Bodewes Aug 30 '17 at 13:02
5
$\begingroup$

Summary: ECC over real numbers can be made to work, including for toy-sized security parameters and real numbers arithmetic as directly supported by typical CPUs and spreadsheets. But much more precision would be needed for private keys large enough to hope for security. That would be inefficient if secure; and perhaps just insecure.


We can mathematically define the infinite group of points on an elliptic curve on the continuous plane, e.g. with Cartesian representation in $\mathbb R^2$ under point addition (with an additional neutral element). We can define scalar multiplication on that. For any integers $k_A$ and $k_B$ and any point $g$ on the curve, it mathematically holds that $k_A\times(k_B\times g)=k_B\times(k_A\times g)$, as used by ECDH and ECIES.

However there is at least one huge problem facing a cryptosystem based on that line of thought: when using Floating Point to represent reals in $\mathbb R$ that are coordinates on the curve, $k_A\times(k_B\times g)=k_B\times(k_A\times g)$ no longer exactly holds due to round-off error, and that worsens with larger $k_A$ and $k_B$ for reasons of numerical stability.

The underlying problems are that

  1. When using FP arithmetic, each point addition on the curve involves (among other operations) addition, and the FP version of that is not associative; otherwise said, there are exceptions, occasionally quite notable, to $(x+y)+z=x+(y+z)$.
  2. Independent of FP arithmetic, the effect of a small variation of $g$ on $k\times g$ grows with $k$ (somewhat like the effect of a small variation of $x\in\mathbb R$ on $x^k$ grows about linearly with $k$).

With the $k_j$ in the hundreds of bits, there are many hundreds chained point additions in the computations of $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$, so that discrepancies between the two values at each step (due to 1) will have many chances to appear and grow (due to 2) to the point where the results are extremely different (much like for evaluation of the logistic map in the chaotic region for large number of iterations).

Increasing FP precision will help, but it is hard to tell exactly how precise a FP representation of coordinates on the curve we shall use for $g$, and intermediary values including $k_A\times g$ and $k_B\times g$, so that $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$ coincide well-enough to derive a shared secret.
Note: the practical issue of defining that well-enough and turning it into a consistent shared secret is non-trivial, but it can be solved by rounding to agreed-upon number of bits, combined with appropriate error correction like: detecting disagreement and, should that occur, retrying or trying nearby values; sending a small public additive correction, or other form of Forward Error Correction.

Floating Point arithmetic with direct hardware support on modern CPUs (that is typically at most 80-bit with 64-bit mantissa, or 64-bit with 53-bit mantissa) will not be precise enough that results coincide well-enough for realistic $k_j$; but it can be made to work most often for $k_j$ and shared key of a few bits. Making large shared keys from small ones is easy (just make multiple passes and concatenate); but I doubt we could make large private/public key pairs from small ones.

Arbitrary-precision FP arithmetic is possible, but inneficient. Typically it uses arbitrary-precision integer arithmetic, so we would be back to this.

Note: there are other serious numerical issues, including the risk of overflow, and how to extract the shared key from potentially very large coordinates.


I do not know if there is an additional issue with security.

The problem of solving for integer $k$ given $k\times g$ and $g$ (which breaks ECDH) might not be as hard with coordinates of givens in $\mathbb R$ (as approximated by FP arithmetic) as it is for coordinates in $GF(p)$ or $GF(2^m)$. As an illustration that it can't be ruled out summarily, solving for $k$ given $x^k$ and $x$ is believed hard with givens in $GF(p)$ for appropriate choice of $p$, but is easy with givens in $\mathbb R$ (as approximated by FP arithmetic, and assuming no overflow) because $k=\log(x^k)/\log(x)$ (computed with rounding to the nearest for FP).

Also, there are conflicting interactions between the precision used and security:

  • Too low a precision on $g$ or/and $k\times g$ restricts the size of $k$ for a unique solution $k$, and short $k$ makes finding $k$ easy; there's no solution to that in sight beyond increasing precision.
  • Overly increasing precision for $k\times g$ (for constant range of $k$) could conceivably make the problem of finding $k$ easier, as we are getting more information about $k$ from low-order bits/digits of $k\times g$.
$\endgroup$
  • 2
    $\begingroup$ Do the ‘$\mathbb{FP}$-rational points of $E/\mathbb{R}$’ even form a group, where $\mathbb{FP}$ is the set of floating-point numbers? I can't imagine they do. A priori I would expect the coordinates of $[n]P$ to overflow on most curves $E$ for practical values of $n$. $\endgroup$ – Squeamish Ossifrage Aug 30 '17 at 14:06
  • $\begingroup$ When I talked about real number CSPRNGs in crypto.stackexchange.com/questions/46910/…, I got backlash suggesting that rounding errors are no longer an issue with modern CPUs. I'm with you but... $\endgroup$ – Paul Uszak Aug 30 '17 at 14:07
  • $\begingroup$ ‘Discrepancies in hardware’ are practically nonexistent today, unless you're trying to compute on a VAX or something similarly esoteric. With IEEE 754, for fixed format such as binary64 (double-precision) as long as you prescribe the precise set of basic floating-point operations to perform a computation (add, sub, mul, div—and a few others, but that's all you need for rational functions), and you don't change the rounding mode or other things from their default, you will get bit-for-bit identical results on practically all computers today. $\endgroup$ – Squeamish Ossifrage Aug 30 '17 at 14:10
  • 1
    $\begingroup$ @PaulUszak: Rounding errors in basic operations are ‘not an issue’ not in the sense that they don't exist, but rather, they are precisely specified by IEEE 754 and implemented identically on practically all ordinary CPUs. (By ‘basic operations’, I mean the ones specified in §5, including add, sub, mul, div, sqrt, etc., but not the ones in §9, such as the transcendental functions. Of course, you can always prescribe a specific rational approximation to a transcendental function to get bit-for-bit identical results.) $\endgroup$ – Squeamish Ossifrage Aug 30 '17 at 14:16
  • 3
    $\begingroup$ @PaulUszak: I fully accept that discrepancies in hardware can be avoided, perhaps because modern CPUs agree on FP for basic operations (at least for 32-bit, 64-bit and 80-bit FP when avaiable, and addition subtraction; though I would not bet the house on the last digit for division). Nevertheless it remains that rounding errors make addition non-associative, and that will grow into discrepancies between what the two sides compute in ECDH: $k_A\times(k_B\times g)$ on one side, and $k_B\times(k_A\times g)$ on the other. $\endgroup$ – fgrieu Aug 30 '17 at 14:38
1
$\begingroup$

It is difficult to define cryptography over any set which has some kind of a non-trivial metric .
The reason is simply that with a metric you can easily decide if you are near a solution to any equation. You can then perform Newton-Iteration to approximate your solution up to an required accuracy.

For instance, solving the "discrete logarithm problem" $y=g^n$ over the reals is simple.

This fact renders crypto-system hard to define over real numbers, complex numbers , p-adic numbers, Quternions over real numbers, etc.

$\endgroup$
  • 1
    $\begingroup$ What is the metric on the subgroup generated by a base point that corresponds to the scalars? $\endgroup$ – Squeamish Ossifrage Aug 31 '17 at 5:46
  • $\begingroup$ @SqueamishOssifrage good point. One first has to define a kind of continuous scalar multiplication with scalars from the reals. I am not sure if this works out. $\endgroup$ – user27950 Aug 31 '17 at 6:12
  • $\begingroup$ Why does one have to do that? The question was about curves over floating-point numbers (which would presumably mean floating-point approximations to curves over (field extensions of) $\mathbb{Q}$), not scalars that are floating-point numbers. Computing $a$ from $g$ and $g^a$ for $g \in \mathbb{R} \setminus \{0\}$ and $a \in \mathbb{Z}$ is relatively easy (assuming the exponentiation is representable!), but it's not clear that computing $n$ from $P$ and $[n]P$ for $P \in E(k)$ and $n \in \mathbb{Z}$ is easy for arbitrary curves $E/\mathbb{Q}$ and field extensions $k$ of $\mathbb{Q}$. $\endgroup$ – Squeamish Ossifrage Aug 31 '17 at 6:24
  • $\begingroup$ Assume, one can extend scalar multiplication of EC over the reals by having the scalar also from the reals and this multiplication is continuous. Assume also that one has a good numerical approximation to calculate the multiplication $P = x G$ by some closed formula. Then one could solve for x by numerical means. $\endgroup$ – user27950 Aug 31 '17 at 6:53
  • $\begingroup$ What part of the question suggests extending the concept of scalar multiplication to non-integer scalars? $\endgroup$ – Squeamish Ossifrage Aug 31 '17 at 13:56

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.