# ECC: Lightweight proof of correct exponentiation

In the context of ECC.

There's an EC point $$P$$ which is supposed to be a known power of another known point $$G$$ (generator). That is:

$$P = [k]G$$ (in additive notation)

This should be verified on an embedded device, with limited capabilities (scarce memory and weak CPU).

Is there a better way to verify this expression, apart from calculating the point $$P$$ from scratch?

Can the prover provide some auxiliary data to prove the exponentiation correctness in an easier way?

UPDATE: To be precise, what I actually need is a multiexponentiation.

The point $$P$$ should be a commitment from 129 different NUMS generators. The device that should verify this commitment is a HW wallet. It has both strict memory restrictions (so that precalculating large tables with odd powers is problematic), as well as the computation time is limited.

• Can you provide more details about the embedded device ? e.g. CPU and RAM ? – Ruggero Jan 22 at 9:39
• @Ruggero please see my update – valdo Jan 22 at 11:01
• What is problem with double-and-add algorithm? – kelalaka Jan 22 at 12:39
• @kelalaka it's not fast enough – valdo Jan 22 at 15:48