Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement inverse operation for FieldElement. #10

Open
CPerezz opened this issue May 28, 2019 · 2 comments
Open

Implement inverse operation for FieldElement. #10

CPerezz opened this issue May 28, 2019 · 2 comments

Comments

@CPerezz
Copy link

CPerezz commented May 28, 2019

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

On dusk-network/dusk-zerocaf#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

@hdevalence
Copy link
Contributor

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).

@CPerezz
Copy link
Author

CPerezz commented May 28, 2019

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants