Exposing the field element API

[kayabaNerve]

I'm personally interested in implementing a hash to curve (an existing one, not a new one), which I understand isn't something that comes up often (lack of other issues with this request). I am currently unable to do so with dalek due to the fact it doesn't expose FieldElement. I believe dalek's current stance is to be opinionated, only supporting Elligator 2 as included in the Ristretto specification, which is a blocker towards me moving existing C code into Rust (either that or there hasn't been a demand for it yet and it's a pain to offer).

I'm not entirely sure how in depth these changes would be due to the multiple backends which make dalek the incredibly performant library it is, yet I'd hope they wouldn't be too pervasive given those backends already seem to resolve to a single API. The question then becomes if that API is sufficient for implementing hash to fields (which I assume it is as the Elligator 2 implementation is singular and based on it?).

Workarounds currently include:

• Forking dalek
• Grabbing a number library and implementing the field element arithmetic myself

Yet I don't actually know why dalek shouldn't expose a field element API. I don't believe it'll reduce application security further than dalek's existence already does. At the very least, getting it exposed with a feature flag would be appreciated.

Clarification would also be appreciated if this isn't feasible :) Thanks.

[AiyionPrime]

An expose-field-feature would be really nice for extensibility.

[kayabaNerve]

I actually did implement a FieldElement struct, with horrible performance, in dalek-ff-group, which I used to implement a specific hash to curve. While it's absolutely not a replacement for proper FE impl (either exposing dalek's or at least one sufficiently performant), it is an available stub.

[AiyionPrime]

My Implementation based on this library is now a working PoC. I developed using a local copy of curve25519-dalek.

It appears I'm interested in having a feature-flag in curve25519-dalek that exposes both FieldElement in general, as well as if possible, the constant EDWARDS_D (which is a FieldElement).

Is there already a decision on whether exposing such things through a feature-flag would be acceptable for @dalek-cryptography?

[AiyionPrime]

@kayabaNerve The three tings I currently use are

• FieldElement::from_bytes()
• FieldElement::one()
• FieldElement::sqrt_ratio_i()

Are those publicly available in your crate? If so, I'd like to use it until this Issue is resolved, performance is not that big of a deal for my use-case.

[AiyionPrime]

I think one() may be provided by your used ff crate, the other two I do not see, yet.

One thing that might be missing as well is an implementation subtraction like &_ - &FieldElement though.

[kayabaNerve]

impl PrimeField for FieldElement {
  type Repr = [u8; 32];
  const NUM_BITS: u32 = 255;
  const CAPACITY: u32 = 254;
  fn from_repr(bytes: [u8; 32]) -> CtOption<Self> {
    let res = Self(U256::from_le_bytes(bytes));
    CtOption::new(res, res.0.add_mod(&U256::ZERO, &FIELD_MODULUS).ct_eq(&res.0))
  }
  fn to_repr(&self) -> [u8; 32] {
    self.0.to_le_bytes()
  }

We do have a to_repr and from_repr, in the PrimeField API. We don't offer sqrt_ratio_i, but I did implement most of it in my own use case.

def sqrRootRatio(
  u: FieldElement,
  v: FieldElement
) -> Tuple[bool, FieldElement]:
  v3: FieldElement = v ** mpz(3)
  v7: FieldElement = v3 * v3 * v
  r: FieldElement = u * v3 * ((u * v7) ** ((q - mpz(5)) // mpz(8)))
  c: FieldElement = v * (r ** mpz(2))
  correctSign: bool = c == u
  flippedSign: bool = c == u.negate()
  flippedSignI: bool = c == (u.negate() * SQRT_M1)
  if flippedSign or flippedSignI:
    r = r * SQRT_M1
  if r.isNegative():
    r = r.negate()
  return (correctSign or flippedSign, r)

Assuming you mean the above Python:

  #[allow(non_snake_case)]
  let X = {
    let u = w;
    let v = x;
    let v3 = v * v * v;
    let uv3 = u * v3;
    let v7 = v3 * v3 * v;
    let uv7 = u * v7;
    uv3 * uv7.pow((-FieldElement::from(5u8)) * FieldElement::from(8u8).invert().unwrap())
  };
  let x = X.square() * x;

I did have a bit more implemented, but didn't need it in my use case, so that's all that remains a direct analogue. SQRT_M1 is exposed as well though. I'd be open to a PR to formally expose it :)

[AiyionPrime]

This looks great, I'll look into what I am missing tomorrow. I do not follow regarding your Python-reference though, sorry?

[kayabaNerve]

Oh. Sorry, I grabbed the Python for my personal reference to verify the Rust I was about to send was equivalent (as my Python was explicitly named, yet my Rust was embedded into another function). When I then realized my Rust code didn't implement sqrt_ratio, just the first half of it, I posted that half with the above note. I just left the Python in case you wanted a reference on how to write such a function ;) I'm used to cryptographers with a few different skill levels and just wanted to help as I can.

[AiyionPrime]

Sorry, I overlooked the python code in between the rust. def should have given it away. Way to go on my end, but really appreciating your help.

[AiyionPrime]

Not sure whether my implementation works, I appear to have a problem with loading CompressedEdwardsY into your implementation...

#[cfg(test)]
mod tests {
    use curve25519_dalek::edwards::CompressedEdwardsY;
    use hex::FromHex;
    use curve25519_dalek::field::FieldElement as dalek_FieldElement;
    use dalek_ff_group::field::FieldElement;
    use ff::PrimeField;

    #[test] 
    fn error_on_unwrap() {
        let expected_compressed_y = "1EE08564F758E3B2FDA686428D29D008E31D3D9B3F8E4CE51A80C0544A15FFA4";
        let cy = CompressedEdwardsY(<[u8; 32]>::from_hex(expected_compressed_y).expect("Decoding failed"));
        cy.decompress();
        let bytes = cy.to_bytes();
        let dalek_uc_y = dalek_FieldElement::from_bytes(&bytes);
        let uc_y = FieldElement::from_repr(bytes).unwrap();
    }
}

Not sure why, but the last unwrap() does fail, as from repr appears to fail on something the curve25519-dalek implementation does work properly. (decompress does not fail)

[kayabaNerve]

You're trying to parse a compressed Edwards point which has a flag bit. You would need to clear that bit to deserialize the FieldElement alone. It should be bytes[31] &= (!(1 << 7)) or so.

[AiyionPrime]

Thanks. I'll report back tomorrow, when I implemented that correctly -.-'

[tarcieri]

@kayabaNerve @AiyionPrime would either of you be interested in upstreaming this work to https://github.com/rustcrypto/elliptic-curves?

We own the curve25519 crate and could use it as a wrapper similar to what we do with the ed25519 crate and ed25519-dalek.

[kayabaNerve]

Yes and no. Yes, I would have no issue handing over dalek-ff-group to elliptic-curves. No, I don't consider it complete (couple unimplementeds/poor perf for the FieldElement API) and accordingly ready for upstreaming. I think ideally, RustCrypto fulfills that one issue and forks dalek, modernizing its dependencies, removing the need for my own crate (which also uses Zeroize 1.3 right now, which I'm not sure I can avoid due to dalek using 1.3...).

If you'd like it to be in RustCrypto as-is though, I'm happy to send it over :) I just want to note my complaints with it before doing so.

[AiyionPrime]

I've got no crypto-background at all, I'm just writing a migration for someone who implemented an implementation wrong.

[AiyionPrime]

@kayabaNerve finally got it working using your instructions. (Thanks!) Made a bracket mistake in the pow58 line, that took me long to find.

My code works now, getting a decision for FieldEleemnt in this issue would be nice though.

I've implemented these four on the way to my goal

pub trait FieldElementExt {
    fn conditional_negate(&mut self, negate: Choice);
    fn is_negative(&self) -> Choice;
    fn sqrt_ratio_i(u: &FieldElement, v: &FieldElement) -> (Choice, FieldElement);
    fn get_edwards_d() -> FieldElement;
}

as monkey patched trait on your FieldElement. (the last is a workaround for EDWARDS_D, due to FieldElements constructer privacy and would be something similar to SQRT_M1 instead of this helper function.)

Let me know if any of those would be welcome in dalek-ff-group, then I'd open a PR.

[kayabaNerve]

conditional_negate isn't one I care for unless it already exists under another API.

is_negative is likely is_odd, which I left unimplemented. I'd appreciate if you provided is_odd :)

sqrt_ratio_i would definitely be appreciated :D Shouldn't that be a CtOption though?

And then EDWARDS_D ala SQRT_M1 would be appreciated :)

Thanks, and sorry for the delay.

[AiyionPrime]

regarding conditional_negate, I only have seen it in this trait's impl: https://docs.rs/subtle/2.4.1/subtle/trait.ConditionallyNegatable.html

yes, is_negative is is_odd in the context of ed25519.

I think my impl of sqrt_ratio_i is close to but not yet ct, but that's something we'll get sorted out.

I'll start with EDWARDS_D then.

[AiyionPrime]

@tarcieri I'm still interested in the field element becoming an exposable feature; Is there a reason, why it does not?

[tarcieri]

@AiyionPrime it's not my call per se, however the rationale for not exposing it is preventing potential misuses.

Things that deal with hashing to a curve point or various point serializations do need access, though. It would be good to know if there are use cases beyond those.

For hash2field/hash2curve specifically it would be possible to pull in the elliptic-curve crate as a dependency, which has implementations of various related algorithms which are generic over curves. If curve25519-dalek pulled it in as a dependency, it can provide internal access to its own fields without leaking the type in the public API.

Are there other use cases people have in mind?

[kayabaNerve]

I needed to implement a specific hash to field which isn't standardized. While yes, by definition that is prone to misuse, it's also a use I needed. What I had to do is use crypto-bigint, wrapped into the Field API, to have a much less efficient, larger in scope, and more error-prone since I wrote it without review field impl.

I'd love if dalek just exposed its. I'm also unsure how misuse would be possible. If someone did try using the FieldElements directly, they'd conflict with all algorithms out there, unless they're impl'ing a new one/doing a custom one. It's exactly for those reasons FieldElements must be exposed though. I'd rather have the ability to do what I need, and the risk of messing it up, then be unable to do what I need so I can't mess it up, which just makes me do more myself anyways.

[marshallpierce]

FWIW, I would like to be able to use this -- in particular, I need to exponentiate a Scalar.

[tarcieri]

@marshallpierce is there a specific existing function which isn't public which you'd like public? This particular issue is about FieldElement, which is not currently part of the public API.

[marshallpierce]

I could well be misunderstanding how this would fit together, but it looks like if I got access to something like the serial u64's FieldElement::pow2k, then the ability of that implementation to exploit the underlying structural properties means it would be more efficient than what I could do via exponentiation by squaring on the Scalar.

[tarcieri]

Scalar and FieldElement are two different fields. If the function doesn't already exist on Scalar, we can't expose it. You're asking for a new feature at that point.

[marshallpierce]

Ah, I see; thanks.