doppio icon indicating copy to clipboard operation
doppio copied to clipboard

Implement `inverse` operation for FieldElement.

Open CPerezz opened this issue 5 years ago • 2 comments

As seen on the code of field.rs, inverse() FieldElement function implementation remains unimplemented.

On https://github.com/dusk-network/dusk-corretto/pull/12 we've just implemented the Kalinski's Montgomery Modular Inverse algorithm for the Doppio's FieldElement mod 2^252 + 27742317777372353535851937790883648493 (prime of the field).

So maybe I can make a PR with the implementation of the Inverse operation and the proper tests and doc comments if it's useful.

References:

  • B. S. Kaliski Jr. - The Montgomery inverse and its applica-tions. IEEE Transactions on Computers, 44(8):1064–1065, August-1995.

  • Montgomery inversion - Erkay Sava ̧s & Çetin Kaya Koç J Cryptogr Eng (2018) 8:201–210 https://doi.org/10.1007/s13389-017-0161-x

CPerezz avatar May 28 '19 11:05 CPerezz

Hi!

The curve25519-dalek source code the field.rs implementation is copied from has an implementation of inversion using a hardcoded addition chain; we were planning to use that implementation, but we didn't get to it yet since we're still working on curve selection (the curve Sean found may not be optimal).

hdevalence avatar May 28 '19 18:05 hdevalence

I saw what I think you're referring to on https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/field.rs#L175 I was, however, unsure as to whether this method will allow for a different prime of the field value ( and if this could be done by just changing some limb values).

@Bounce23 and I plan to create set inclusion proofs using Doppio - with respect to the search for optimal curves, is that in relation to the optimization for those addition chains? Or for a larger goal of the project?

CPerezz avatar May 28 '19 19:05 CPerezz