Elliptic curve discrete logarithm problem (decoding RistrettoPoints)

[cchudant]

Hi! As part of a freelance work for xelis, I have been working on an implementation of FastECDLP. My implementation works, and is quite fast :partying_face:

However, my work currently lives in a fork of this repository, because there are quite a lot of private items I need to access! Here is my implementation as of the current state: compare changes. It is still lacking in docs, tests and stuff.

Here are the private items I need to access:

• Most of FieldElement: addition, substraction, multiplication, sqrt_ratio_i, invert, batch_invert, square, ZERO and ONE constants.
• Ristretto to Edwards conversion.
• Edwards X/Y/Z/T fields if possible.
• MONTGOMERY_A (+ *_NEG) constants.

I may have missed some, but FieldElement is the most important part. Considering that, I'd like to know what the best course of action here is:

• should these elements be public, and should my code be in another crate?
• or, should this be part of curve25519-dalek directly
• is dalek interested in upstreaming it?

[tarcieri]

As far as FieldElement access goes, TwistedEdwardsPoint::Base would be one way of exposing it, at least when the next release of the group crate is available: https://github.com/zkcrypto/group/pull/49/files#diff-df25442eb916a316f39ccb89f7d38163eb8ca60413100a61b2848b17a4aad175R21

[cchudant]

As of right now, what do you think I should do then?

[tarcieri]

FieldElement is otherwise deliberately not part of the public API, though could potentially be exposed as "hazmat", though personally I'd prefer to wait for group-based APIs to expose it

[cchudant]

Thank you. FieldElement being deliberately not part of the public API is what I expected.

I did not know the group crate existed. I think you are right and it would be better if I were to use that. I have however a big concern: the PR you linked is a draft and has not received any update since July 30th. I'd like to get my work over the finish line as fast as possible, and I don't think I'll be available to do the needed refactor and cleanup when the group-based APIs will land.

[tarcieri]

Given your need to couple to the internals either opening a PR or maintaining the fork sound like options. If you're in a hurry the latter sounds like the most practical option.