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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.