curveforge 0.3.0

//! Double-odd elliptic curve model implementation.
//!
//! Double-odd elliptic curves have their order of the form $2r$, where $r$ is an odd prime.
//! Thomas Pornin introduced this model in 2020, along with complete addition and doubling
//! formulas. When instantiated over well-chosen constants, the model outperforms many existing
//! cryptographic constructions.
//!
//! Double-odd curves also pop-up as embedding curves for various well-known curves. For example:
//! * The [rtr](crate::curves::rtr) curves were designed to embed NIST P-256 and P-384 curves.
//! * Curve25519 can be [embedded by a double-odd
//! curve](https://github.com/arkworks-rs/algebra/pull/986#issuecomment-2890678519), which remains
//! to be implemented.
//!
//! # References
//! * [Pornin 2024](https://doi.org/10.62056/akmp-4c2h) A Prime-Order Group with Complete Formulas
//! from Even-Order Elliptic Curves
//! * [Pornin 2022](https://eprint.iacr.org/2022/1052) Double-Odd Jacobi Quartic
//! * [Pornin 2020](https://eprint.iacr.org/2020/1558) Double-Odd Elliptic Curves

use crate::prelude::*;

elliptic_curve_model! {
    [attributes]
    name = DoubleOdd
    coordinates = (e, z, u, t)
    constants = (a, b)

    [functions]
    #[inline(always)]
    add: (P: Point, Q: Point) -> Point
        ee <- P.e * Q.e
        zz <- P.z * Q.z
        uu <- P.u * Q.u
        tt <- P.t * Q.t

        ztzt <- (P.z + P.t) * (Q.z + Q.t) - zz - tt
        eueu <- (P.e + P.u) * (Q.e + Q.u) - ee - uu
        c <- (a * a) - (b * 4)
        ctt <- c * tt
        zzc <- zz - ctt

        uud <- uu.dbl()

        e <- (zz + ctt) * (ee - (a * uud)) + c * uud * ztzt
        z <- zzc.sqr()
        t <- eueu.sqr()
        u <- zzc * eueu

        Point::new(e, z, u, t)

    #[inline(always)]
    dbl: (P: Point) -> Point
        c <- (a * a) - (b * 4)

        z <- -c.dbl() * P.t.sqr()
        t <- P.e
        e <- P.e.sqr()
        z <- z + e
        z <- z + (a * P.u.sqr()).dbl()

        t <- t * P.u
        t <- t.dbl()

        u <- t
        t <- t.sqr()

        u <- u * z
        z <- z.sqr()

        e <- e.sqr()
        e <- e.dbl()
        e <- e + (-z) + (a * t)

        Point::new(e, z, u, t)

    #[inline(always)]
    elligator: (z: Element, r: Element) -> Point
        w <- a.neg() * (1 + z * r.sqr()).inv()
        ww <- w.sqr()
        s <- (ww * w + a * ww + b * w).legendre()
        x <- s * w - (1 - s) * (a * 2.inv())
        xx <- x.sqr()
        // We don't compute y explicitely, because the formulas below are faster without explicit y
        // y <- s.neg() * (x * xx + a * xx + b * x).sqrt()

        e <- xx - b
        z <- xx + a * x + b
        u <- -s * (x * z).sqrt()
        t <- x

        Point::new(e, z, u, t)

    #[inline(always)]
    inverse_elligator: (z: Element, P: Point) -> Element
        ez <- P.e + P.z
        emz <- P.e - P.z
        at <- a * P.t
        ut <- P.u * P.t
        ez_plus_at <- ez + at
        ez_minus_at <- ez - at

        // Workaround for conditional reassign bug:
        ez_plus_at <- ez_plus_at * 1
        ez_minus_at_sq <- ez_minus_at.sqr()

        denominator <- (z * (ez.sqr() - at.sqr()) * ut).inv()
        r_sq_pos <- (ez_minus_at_sq * ut)
        r_sq_neg <- (ez_plus_at.sqr() * ut)

        y <- z * P.z * ez_minus_at_sq * ez_plus_at * denominator * 2.inv()

        numerator <- y.is_even() ? r_sq_pos : r_sq_neg

        // A point is infinite if e == ±z
        // We use a product here, because OR is not yet available in DSL
        infinity <- (ez * emz) = Element::from(0)

        r_sq <- -numerator * denominator
        r_sq <-  infinity ? Element::from(0) : r_sq

        r_sq.sqrt()

    #[inline(always)]
    elligator_invertible: (z: Element, P: Point) -> Bool
        // Test whether -z((E^2 +Z^2 + 2*E*Z)/(4T^2) - A^2/4) is a square
        ez2ez <- P.e.sqr() + P.z.sqr() + 2*P.e * P.z
        t <- ez2ez * 4*P.t.sqr().inv()
        t <- t - a.sqr() * 4.inv()
        (-z*t).legendre() = 1

    #[inline(always)]
    serialize: (P: Point) -> Bytes
        z_i <- P.z.inv()
        u <- P.u * z_i
        e <- P.e * z_i

        u <- e.is_even() ? u : u.neg()
        Bytes::from(u.serialize())

    #[inline(always)]
    deserialize: (x: Bytes) -> Point
        u <- Element::deserialize(x)
        t <- u.sqr()
        e <- ((a.sqr() - (4 * b)) * t.sqr() - 2 * a * t + 1).sqrt()
        e <- e.is_even() ? e : e.neg()

        Point::new(e, 1, u, t)

    #[inline(always)]
    equal: (P: Point, Q: Point) -> Bool
        P.e * Q.u = P.u * Q.e

    #[inline(always)]
    neg: (P: Point) -> Point
        Point::new(P.e, P.z, P.u.neg(), P.t)
}