1
$\begingroup$

I am trying to understand the use of pre-computed points in ECC for ECC signature, verification, key generation, and so on. After searching on the internet, I understand that pre-computed points aid faster execution. However, I am unable to get the complete picture. Can someone help with an example? Also, once the pre-computed points are calculated, are these secrets?

$\endgroup$
2
$\begingroup$

Can someone help with an example?

Ok, here's a simple example; suppose we precompute a table that contained all the points of the form $(a \cdot 256^b) G$, for $0 < a < 256$ and where $b$ be within the scalar we intend to support.

For example, the table (if we support 2 byte scalars) would contain the points $\text{0x01}G, \text{0x02}G, …,\text{0xff}G, \text{0x0100}G, \text{0x0200}G, …, \text{0xff00}G$

Then, to compute the value $0x1234G$, we would look up $0x1200G$ in our table and the value $34G$, and then add them $0x1200G + 0x34G = 0x1234G$; we just computed the point multiplication with a single addition (and some table lookups); using a table without precomputation would use at least 13 point additions/doublings.

It should be obvious how this table can be extended to support longer scalars; if we support 32-byte scalars (appropriate for 256-bit curves), we can do any point multiplication using 31 additions (and a large table).

There are a number of ways to build the table (including methods with much smaller tables and not that much more computation required); I picked this example solely because it was easy to understand.

Also, once the pre-computed points are calculated, are these secrets?

Only if the base point is secret. As this is most commonly used with the public curve generator point, there is usually no need.

Also, the tables/algorithms can be set up to run in constant time; however that is rather trickier.

$\endgroup$
5
  • $\begingroup$ I'm surprised that latex accepts the eclipses char. Is there an easy way to write it? $\endgroup$
    – kelalaka
    Nov 17 '20 at 16:46
  • $\begingroup$ @kelalaka: actually, I did just three periods in a row (following a space); the editor autoconverted that into an ellipsis. $\endgroup$
    – poncho
    Nov 17 '20 at 16:59
  • $\begingroup$ @poncho: Thanks you for clearing that up. What is the need to ever keep the base point secret? Is is not always public? $\endgroup$ Nov 18 '20 at 5:38
  • $\begingroup$ @AfiteliWells: well, the table needn't be based on the public generator; you can generate such a table based on any point, which might be private. That said, the only place I can think of where you might have a secret EC point might be in a PAKE, and that's really a corner case. I just threw that in there in case you were talking about such a corner case. $\endgroup$
    – poncho
    Nov 18 '20 at 13:26
  • $\begingroup$ @poncho Thanks! $\endgroup$ Nov 19 '20 at 11:16

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.