4
$\begingroup$

In ECC, it is apparently easy to verify the final point given the starting point and the number of hops. But it is difficult to compute the number of hops given just the starting point and the final point.

Can anyone explain in regular English why this is the case (no intense math, please).

From my understanding, hopping along the curve is analogous to addition, and thus the iterative hopping is analogous to multiplication. I've read that the reason it's faster to compute the final point given the number of hops is that we can use exponentiation by squaring to make logN computations as opposed to N.

My question is this: wouldn't there still be a large number of points to hop in between two squares?

E.g. if the number of hops is 1524, then we would compute 2, 4, 8, 16, ..., 512, 1024 — but then we'd still need to do 500 hops after getting to 1024. Or would we use squaring again to get from 1024 to 1524?

$\endgroup$
3
3
$\begingroup$

On an elliptic curve as used in crypto, we can add any two points $P$ and $Q$ of the elliptic curve, yielding a new point of the elliptic curve: $X\gets P+Q$. It holds $(P+Q)+R=P+(Q+R)$, making $P+Q+R$ unambiguous.

For any integer $k>0$ and point $P$, that lets us define $k$ times $P$, noted e.g. $k\times P$, as the result obtained by adding $k$ copies of $P$, that is $k\times P\;\underset{\text{def}}=\;\underbrace{P+\ldots+P}_{k\text{ times}}$

We can efficiently compute $k\times P$ per the following (recursive) method:

  • if $k=1$ then return $P$
  • otherwise, if $k$ is even, compute $Q=(k/2)\times P$ and return $Q+Q$
  • otherwise, compute $Q=(k-1)\times P$ and return $Q+P$

This efficient computation method for $k\times P$ takes time proportional to the number of bits in $k$, whereas applying the definition would take time proportional to $k$. The $k$ used in crypto are often about $2^{256}$, which is many times the conjectured number of atoms in the universe, but the computation still takes a fraction of a second with the efficient method.

Now, consider the problem of finding $k>0$ such that $Q=k\times P$, given $P$ and $Q$. A basic method is to start from $P$ and, while $Q$ is not reached, add $P$. The desired $k$ is one more than the number of additions made. Problem is, that takes time proportional to $k$.

We know better methods that take time proportional to $\sqrt k$. The main ones are baby step/giant step¹ and Pollard's rho². But when $k$ is about $2^{256}$, $\sqrt k$ is about $2^{128}$, and we can't even count to that number: collectively, all the computing devices ever made by man did not count to that, much less made that number of elliptic curve operations.

We know³ no better method than those requiring time proportional to $\sqrt k$, and that explains the difficulty of reversing multiplication on an elliptic curve with the parameters used in cryptography.


Extra meat for thought:

¹ Baby step/giant step works as follows:

  • chose an $l$ large enough that we'll have $k\le l^2$
  • store the point $Q_0\gets Q$
  • for $i$ from $1$ to $l-1$
    • compute and store the point $Q_i\gets Q_{i-1}+P$ (these are the baby steps)
  • compute the point $R\gets l\times P$
  • initialize the point $S\gets R$
  • for $j$ from $1$ to $l$
    • search $S$ among the $Q_i$ (this can be done without scanning all the $Q_i$, much like we can find a book in a library), and if there's a match
      • compute and output $k\gets j\,l-i$, done!
    • update the point $S\gets S+R$ (these are the giant steps)

² Pollard's rho replaces the systematic search of baby step/giant step¹ by a pseudo-random walk, and replaces the impractically large array $Q_i$ by a detection that the walk goes along an already explored path. The point where the paths merge yields the solution.

³ Q: But why can't we find a better method, when we have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given ordinary integers $u$ and $v$ ? $k$ is the quotient of $v$ divided by $u$ in Euclidean division, and that's feasible for numbers with million bits.
A: Euclidean division relies on comparing integers and finding the smallest, for a definition of smallest compatible with addition, in the sense that if $a<b$, then $a+b<a+c$. But there can't be any such notion of order on a large but finite set like an elliptic curve as used in crypto, hence Euclidean division won't cut it⁴.

⁴ Q: But that argument does not hold water! We have efficient methods to solve the similar problem of finding $k>0$ such that $v=k\times u$ given $u$ and $v$ when working in some large but finite sets. For example, in arithmetic modulo $p$, there's a systematic method published in 1621 by Bachet, using an extension of the so-called Euclidean algorithm, which uses Euclidean division.
A: This does not cut it either, but for a different reason: in arithmetic modulo $p$ and all cases where similar methods are known, it is relied not only on addition of elements $a$, $b$, $c$ of the set, but also on multiplying them in a way compatible with the premise that $a\,(b+c)=a\,b+a\,c$ . When in elliptic curve arithmetic we can add points, but not meaningfully multiply them together.

$\endgroup$
0
$\begingroup$

Suppose you want to compute $100 \times 3$, but you only know how to do addition. You can do it with 99 additions: $$3+3=6$$ $$6+3=9$$ $$9+3=2$$ $$...$$ $$294+3=297$$ $$297+3=300$$ But this is slow. How can we speed this up?

First we make bundles of 2, 4, 8, 16, 32 and 64 hops. $$2 \times 3 = 3+3=6$$ $$4 \times 3 = 6+6=12$$ $$8 \times 3 = 12+12=24$$ $$16 \times 3 = 24+24=48$$ $$32 \times 3 = 48+48=96$$ $$64 \times 3 = 96+96=192$$

$100$ hops can be done, by doing 64 hops, then 32 hops and then another 4 hops. $$100 = 64 + 32 + 4$$

So now we can add three numbers to get your answer. $$(64 \times 3) + (32 \times 3) + (4 \times 3) = 100 \times 3$$ $$192 + 96 + 12 = 300$$

Same technique can be used to compute $3^{100}$. First compute $3^2$, $3^4$, $3^8$, $3^{16}$, $3^{32}$ and $3^{64}$. Then multiply $3^{64}$, $3^{32}$ and $3^4$ to get $3^{100}$.

And also with elyptic curve with starting point $P$, you can compute $100P$ by first computing $2P$, $4P$, $8P$, $16P$, $32P$ and $64P$. And finally you add $64P$, $32P$ and $4P$ to get $100P$.

$\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.