ark_ec/scalar_mul/
glv.rs

1use crate::{
2    short_weierstrass::{Affine, Projective, SWCurveConfig},
3    AdditiveGroup, CurveGroup,
4};
5use ark_ff::{PrimeField, Zero};
6use ark_std::ops::{AddAssign, Neg};
7use num_bigint::{BigInt, BigUint, Sign};
8use num_integer::Integer;
9use num_traits::{One, Signed};
10
11/// The GLV parameters for computing the endomorphism and scalar decomposition.
12pub trait GLVConfig: Send + Sync + 'static + SWCurveConfig {
13    /// Constants that are used to calculate `phi(G) := lambda*G`.
14
15    /// The coefficients of the endomorphism
16    const ENDO_COEFFS: &'static [Self::BaseField];
17
18    /// The eigenvalue corresponding to the endomorphism.
19    const LAMBDA: Self::ScalarField;
20
21    /// A 4-element vector representing a 2x2 matrix of coefficients the for scalar decomposition, s.t. k-th entry in the vector is at col i, row j in the matrix, with ij = BE binary decomposition of k.
22    /// The entries are the LLL-reduced bases.
23    /// The determinant of this matrix must equal `ScalarField::characteristic()`.
24    const SCALAR_DECOMP_COEFFS: [(bool, <Self::ScalarField as PrimeField>::BigInt); 4];
25
26    /// Decomposes a scalar s into k1, k2, s.t. s = k1 + lambda k2,
27    fn scalar_decomposition(
28        k: Self::ScalarField,
29    ) -> ((bool, Self::ScalarField), (bool, Self::ScalarField)) {
30        let scalar: BigInt = k.into_bigint().into().into();
31
32        let coeff_bigints: [BigInt; 4] = Self::SCALAR_DECOMP_COEFFS.map(|x| {
33            BigInt::from_biguint(x.0.then_some(Sign::Plus).unwrap_or(Sign::Minus), x.1.into())
34        });
35
36        let [n11, n12, n21, n22] = coeff_bigints;
37
38        let r = BigInt::from(Self::ScalarField::MODULUS.into());
39
40        // beta = vector([k,0]) * self.curve.N_inv
41        // The inverse of N is 1/r * Matrix([[n22, -n12], [-n21, n11]]).
42        // so β = (k*n22, -k*n12)/r
43
44        let beta_1 = {
45            let (mut div, rem) = (&scalar * &n22).div_rem(&r);
46            if (&rem + &rem) > r {
47                div.add_assign(BigInt::one());
48            }
49            div
50        };
51        let beta_2 = {
52            let (mut div, rem) = (&scalar * &n12.clone().neg()).div_rem(&r);
53            if (&rem + &rem) > r {
54                div.add_assign(BigInt::one());
55            }
56            div
57        };
58
59        // b = vector([int(beta[0]), int(beta[1])]) * self.curve.N
60        // b = (β1N11 + β2N21, β1N12 + β2N22) with the signs!
61        //   = (b11   + b12  , b21   + b22)   with the signs!
62
63        // b1
64        let b11 = &beta_1 * &n11;
65        let b12 = &beta_2 * &n21;
66        let b1 = b11 + b12;
67
68        // b2
69        let b21 = &beta_1 * &n12;
70        let b22 = &beta_2 * &n22;
71        let b2 = b21 + b22;
72
73        let k1 = &scalar - b1;
74        let k1_abs = BigUint::try_from(k1.abs()).unwrap();
75
76        // k2
77        let k2 = -b2;
78        let k2_abs = BigUint::try_from(k2.abs()).unwrap();
79
80        (
81            (k1.sign() == Sign::Plus, Self::ScalarField::from(k1_abs)),
82            (k2.sign() == Sign::Plus, Self::ScalarField::from(k2_abs)),
83        )
84    }
85
86    fn endomorphism(p: &Projective<Self>) -> Projective<Self>;
87
88    fn endomorphism_affine(p: &Affine<Self>) -> Affine<Self>;
89
90    fn glv_mul_projective(p: Projective<Self>, k: Self::ScalarField) -> Projective<Self> {
91        let ((sgn_k1, k1), (sgn_k2, k2)) = Self::scalar_decomposition(k);
92
93        let mut b1 = p;
94        let mut b2 = Self::endomorphism(&p);
95
96        if !sgn_k1 {
97            b1 = -b1;
98        }
99        if !sgn_k2 {
100            b2 = -b2;
101        }
102
103        let b1b2 = b1 + b2;
104
105        let iter_k1 = ark_ff::BitIteratorBE::new(k1.into_bigint());
106        let iter_k2 = ark_ff::BitIteratorBE::new(k2.into_bigint());
107
108        let mut res = Projective::<Self>::zero();
109        let mut skip_zeros = true;
110        for pair in iter_k1.zip(iter_k2) {
111            if skip_zeros && pair == (false, false) {
112                skip_zeros = false;
113                continue;
114            }
115            res.double_in_place();
116            match pair {
117                (true, false) => res += b1,
118                (false, true) => res += b2,
119                (true, true) => res += b1b2,
120                (false, false) => {},
121            }
122        }
123        res
124    }
125
126    fn glv_mul_affine(p: Affine<Self>, k: Self::ScalarField) -> Affine<Self> {
127        let ((sgn_k1, k1), (sgn_k2, k2)) = Self::scalar_decomposition(k);
128
129        let mut b1 = p;
130        let mut b2 = Self::endomorphism_affine(&p);
131
132        if !sgn_k1 {
133            b1 = -b1;
134        }
135        if !sgn_k2 {
136            b2 = -b2;
137        }
138
139        let b1b2 = b1 + b2;
140
141        let iter_k1 = ark_ff::BitIteratorBE::new(k1.into_bigint());
142        let iter_k2 = ark_ff::BitIteratorBE::new(k2.into_bigint());
143
144        let mut res = Projective::<Self>::zero();
145        let mut skip_zeros = true;
146        for pair in iter_k1.zip(iter_k2) {
147            if skip_zeros && pair == (false, false) {
148                skip_zeros = false;
149                continue;
150            }
151            res.double_in_place();
152            match pair {
153                (true, false) => res += b1,
154                (false, true) => res += b2,
155                (true, true) => res += b1b2,
156                (false, false) => {},
157            }
158        }
159        res.into_affine()
160    }
161}
ark_ec/scalar_mul/glv.rs

ark_ec/scalar_mul/
glv.rs
