hdevalence commented 7 years ago

The Back-Maxwell rangeproof construction we use in dalek-rangeproofs requires scalar inversion. Right now we just have an easy and naive implementation with no optimization, but which is nearly as expensive as a full point*scalar operation.

It could be made faster by some combination of:

[x] using fixed-window exponentiation with a lookup table (see the constant-time scalar-point multiplication for an example)
[x] adding an implementation of squaring for scalars
[x] optimizing the scalar arithmetic: maybe Karatsuba, Montgomery reduction, or some combination?
[x] maybe 64-bit implementation of scalar arithmetic ?

hdevalence commented 7 years ago

71 adds an implementation of squaring for scalars.

isislovecruft commented 7 years ago

72 uses a custom (more efficient) addition chain, this replaces the goal of using a fixed-window exponentiation.

isislovecruft commented 7 years ago

75 implements the Karatsuba portion of goal number 3.

hdevalence commented 7 years ago

Closing this issue now that Floodyberry's 64-bit scalar code is merged.

dalek-cryptography / curve25519-dalek

Accelerate scalar inversion #68

71 adds an implementation of squaring for scalars.

72 uses a custom (more efficient) addition chain, this replaces the goal of using a fixed-window exponentiation.

75 implements the Karatsuba portion of goal number 3.