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

ark_ec/scalar_mul/
glv.rs
