# What is the use of pre-computed points in ECC?

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?

## 1 Answer

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.

• I'm surprised that latex accepts the eclipses char. Is there an easy way to write it? – kelalaka Nov 17 '20 at 16:46
• @kelalaka: actually, I did just three periods in a row (following a space); the editor autoconverted that into an ellipsis. – poncho Nov 17 '20 at 16:59
• @poncho: Thanks you for clearing that up. What is the need to ever keep the base point secret? Is is not always public? – Afiteli Wells Nov 18 '20 at 5:38
• @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. – poncho Nov 18 '20 at 13:26
• @poncho Thanks! – Afiteli Wells Nov 19 '20 at 11:16