ark_ec/hashing/curve_maps/
elligator2.rs

1use crate::models::twisted_edwards::{MontCurveConfig, TECurveConfig};
2use ark_ff::{Field, One, Zero};
3use core::marker::PhantomData;
4
5use crate::{
6    hashing::{curve_maps::parity, map_to_curve_hasher::MapToCurve, HashToCurveError},
7    models::twisted_edwards::{Affine, Projective},
8};
9
10/// Trait defining the necessary parameters for the Elligator2 hash-to-curve method
11/// for twisted edwards curves form of:
12/// `b * y² = x³ + a * x² + x`
13/// from [\[BHKL13\]], according to [\[HSSWW23\]]
14///
15/// - [\[BHKL13\]] <http://dx.doi.org/10.1145/2508859.2516734>
16/// - [\[HSSWW23\]] <https://datatracker.ietf.org/doc/html/rfc9380>
17pub trait Elligator2Config: TECurveConfig + MontCurveConfig {
18    /// An element of the base field that is not a square root see \[BHKL13, Section 5\].
19    /// When `BaseField` is a prime field, [\[HSSWW23\]] mandates that `Z` is the
20    /// non-square with lowest absolute value in the `BaseField` when its elements
21    /// are represented as [-(q-1)/2, (q-1)/2]
22    const Z: Self::BaseField;
23
24    /// This must be equal to 1/(MontCurveConfig::COEFF_B)^2;
25    const ONE_OVER_COEFF_B_SQUARE: Self::BaseField;
26
27    /// This must be equal to MontCurveConfig::COEFF_A/MontCurveConfig::COEFF_B;
28    const COEFF_A_OVER_COEFF_B: Self::BaseField;
29}
30
31/// Represents the Elligator2 hash-to-curve map defined by `P`.
32pub struct Elligator2Map<P: TECurveConfig>(PhantomData<fn() -> P>);
33
34impl<P: Elligator2Config> MapToCurve<Projective<P>> for Elligator2Map<P> {
35    /// Checks if `P` represents a valid Elligator2 map. Panics otherwise.
36    fn check_parameters() -> Result<(), HashToCurveError> {
37        // We assume that the Montgomery curve is correct and  as such we do
38        // not verify the prerequisite for applicability of Elligator2 map to the TECurveConfing.
39
40        // Verifying that Z is a non-square
41        debug_assert!(
42            !P::Z.legendre().is_qr(),
43            "Z should be a quadratic non-residue for the Elligator2 map"
44        );
45
46        debug_assert_eq!(
47            P::ONE_OVER_COEFF_B_SQUARE,
48            <P as MontCurveConfig>::COEFF_B
49                .square()
50                .inverse()
51                .expect("B coefficient cannot be zero in Montgomery form"),
52            "ONE_OVER_COEFF_B_SQUARE is not equal to 1/COEFF_B^2 in Montgomery form"
53        );
54
55        debug_assert_eq!(
56            P::COEFF_A_OVER_COEFF_B,
57            <P as MontCurveConfig>::COEFF_A / <P as MontCurveConfig>::COEFF_B,
58            "COEFF_A_OVER_COEFF_B is not equal to COEFF_A/COEFF_B in Montgomery form"
59        );
60        Ok(())
61    }
62
63    /// Map an arbitrary base field element `element` to a curve point.
64    fn map_to_curve(element: P::BaseField) -> Result<Affine<P>, HashToCurveError> {
65        // 1. x1 = -(J / K) * inv0(1 + Z * u^2)
66        // 2. If x1 == 0, set x1 = -(J / K)
67        // 3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
68        // 4. x2 = -x1 - (J / K)
69        // 5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
70        // 6. If is_square(gx1), set x = x1, y = sqrt(gx1) with sgn0(y) == 1.
71        // 7. Else set x = x2, y = sqrt(gx2) with sgn0(y) == 0.
72        // 8. s = x * K
73        // 9. t = y * K
74        // 10. return (s, t)
75
76        // ark a is irtf J
77        // ark b is irtf k
78        let k = <P as MontCurveConfig>::COEFF_B;
79        let j_on_k = P::COEFF_A_OVER_COEFF_B;
80        let ksq_inv = P::ONE_OVER_COEFF_B_SQUARE;
81
82        let den_1 = <P::BaseField as One>::one() + P::Z * element.square();
83
84        let x1 = -j_on_k
85            / (if den_1.is_zero() {
86                <P::BaseField as One>::one()
87            } else {
88                den_1
89            });
90        let x1sq = x1.square();
91        let x1cb = x1sq * x1;
92        let gx1 = x1cb + j_on_k * x1sq + x1 * ksq_inv;
93
94        let x2 = -x1 - j_on_k;
95        let x2sq = x2.square();
96        let x2cb = x2sq * x2;
97        let gx2 = x2cb + j_on_k * x2sq + x2 * ksq_inv;
98
99        let (x, mut y, sgn0) = if gx1.legendre().is_qr() {
100            (
101                x1,
102                gx1.sqrt()
103                    .expect("We have checked that gx1 is a quadratic residue. Q.E.D"),
104                true,
105            )
106        } else {
107            (
108                x2,
109                gx2.sqrt()
110                    .expect("gx2 is a quadratic residue because gx1 is not. Q.E.D"),
111                false,
112            )
113        };
114
115        if parity(&y) != sgn0 {
116            y = -y;
117        }
118
119        let s = x * k;
120        let t = y * k;
121
122        // `(s, t)` is an affine point on the Montgomery curve.
123        // Ideally, the TECurve would come with a mapping to its Montgomery curve,
124        // so we could just call that mapping here.
125        // This is currently not supported in arkworks, so
126        // we just implement the rational map here from [\[HSSWW23\]] Appendix D
127
128        let tv1 = s + <P::BaseField as One>::one();
129        let tv2 = tv1 * t;
130        let (v, w) = if tv2.is_zero() {
131            (<P::BaseField as Zero>::zero(), <P::BaseField as One>::one())
132        } else {
133            let tv2_inv = tv2
134                .inverse()
135                .expect("None zero element has inverse. Q.E.D.");
136            let v = tv2_inv * tv1 * s;
137            let w = tv2_inv * t * (s - <P::BaseField as One>::one());
138            (v, w)
139        };
140
141        let point_on_curve = Affine::new_unchecked(v, w);
142        debug_assert!(
143            point_on_curve.is_on_curve(),
144            "Elligator2 mapped to a point off the curve"
145        );
146        Ok(point_on_curve)
147    }
148}
149
150#[cfg(test)]
151mod test {
152    #[cfg(all(
153        target_has_atomic = "8",
154        target_has_atomic = "16",
155        target_has_atomic = "32",
156        target_has_atomic = "64",
157        target_has_atomic = "ptr"
158    ))]
159    type DefaultHasher = ahash::AHasher;
160
161    #[cfg(not(all(
162        target_has_atomic = "8",
163        target_has_atomic = "16",
164        target_has_atomic = "32",
165        target_has_atomic = "64",
166        target_has_atomic = "ptr"
167    )))]
168    type DefaultHasher = fnv::FnvHasher;
169
170    use crate::{
171        hashing::{map_to_curve_hasher::MapToCurveBasedHasher, HashToCurve},
172        CurveConfig,
173    };
174    use ark_ff::field_hashers::DefaultFieldHasher;
175    use ark_std::vec::*;
176
177    use super::*;
178    use ark_ff::{fields::Fp64, MontBackend, MontFp};
179    use hashbrown::HashMap;
180    use sha2::Sha256;
181
182    #[derive(ark_ff::MontConfig)]
183    #[modulus = "101"]
184    #[generator = "2"]
185    pub(crate) struct F101Config;
186    pub(crate) type F101 = Fp64<MontBackend<F101Config, 1>>;
187
188    #[derive(ark_ff::MontConfig)]
189    #[modulus = "11"]
190    #[generator = "2"]
191    pub(crate) struct F11Config;
192    pub(crate) type F11 = Fp64<MontBackend<F11Config, 1>>;
193
194    struct TestElligator2MapToCurveConfig;
195
196    impl CurveConfig for TestElligator2MapToCurveConfig {
197        const COFACTOR: &[u64] = &[8];
198
199        const COFACTOR_INV: F11 = MontFp!("7");
200
201        type BaseField = F101;
202        type ScalarField = F11;
203    }
204
205    /// sage: EnsureValidEdwards(F101,-1,12)
206    /// sage: Curve_EdwardsToMontgomery(F101, -1, 12)
207    /// (76, 23)
208    /// sage: Curve_EdwardsToWeierstrass(F101, -1, 12)
209    /// (11, 5)
210    /// sage: EllipticCurve(F101,[11,5])
211    /// Elliptic Curve defined by y^2 = x^3 + 11*x + 5 over Finite Field of size 101
212    /// sage: EW = EllipticCurve(F101,[11,5])
213    /// sage: EW.order().factor()
214    /// 2^3 * 11
215    /// sage: EW = EdwardsCurve(F101,-1,12)
216    /// sage: EW.gens()[0] * 8
217    /// (5 : 36 : 1)
218    /// Point_WeierstrassToEdwards(F101, 11, 5, F101(5), F101(36), a_given=-1, d_given=12)
219    /// (23, 24)
220    impl TECurveConfig for TestElligator2MapToCurveConfig {
221        /// COEFF_A = -1
222        const COEFF_A: F101 = MontFp!("-1");
223
224        /// COEFF_D = 12
225        const COEFF_D: F101 = MontFp!("12");
226
227        const GENERATOR: Affine<Self> = Affine::new_unchecked(MontFp!("23"), MontFp!("24"));
228
229        type MontCurveConfig = Self;
230    }
231
232    impl MontCurveConfig for TestElligator2MapToCurveConfig {
233        /// COEFF_A = 76
234        const COEFF_A: F101 = MontFp!("76");
235
236        /// COEFF_B = 23
237        const COEFF_B: F101 = MontFp!("23");
238
239        type TECurveConfig = Self;
240    }
241
242    /// sage: find_z_ell2(F101)
243    /// 2
244    /// sage: F101 = FiniteField(101)
245    /// sage: 1/F101("23")^2
246    /// 80
247    /// sage: F101("76")/F101("23")
248    /// 56
249    impl Elligator2Config for TestElligator2MapToCurveConfig {
250        const Z: F101 = MontFp!("2");
251        const ONE_OVER_COEFF_B_SQUARE: F101 = MontFp!("80");
252
253        const COEFF_A_OVER_COEFF_B: F101 = MontFp!("56");
254    }
255
256    /// The point of the test is to get a simple twisted edwards curve and make
257    /// simple hash
258    #[test]
259    fn hash_arbitary_string_to_curve_elligator2() {
260        let test_elligator2_to_curve_hasher = MapToCurveBasedHasher::<
261            Projective<TestElligator2MapToCurveConfig>,
262            DefaultFieldHasher<Sha256, 128>,
263            Elligator2Map<TestElligator2MapToCurveConfig>,
264        >::new(&[1])
265        .unwrap();
266
267        let hash_result = test_elligator2_to_curve_hasher.hash(b"if you stick a Babel fish in your ear you can instantly understand anything said to you in any form of language.").expect("fail to hash the string to curve");
268
269        assert!(
270            hash_result.is_on_curve(),
271            "hash results into a point off the curve"
272        );
273    }
274
275    /// Use a simple twisted edwards curve and map the whole field to it. We observe
276    /// the map behaviour. Specifically, the map should be non-constant, all
277    /// elements should be mapped to curve successfully. everything can be mapped
278    #[test]
279    fn map_field_to_curve_elligator2() {
280        Elligator2Map::<TestElligator2MapToCurveConfig>::check_parameters().unwrap();
281
282        let mut map_range: Vec<Affine<TestElligator2MapToCurveConfig>> = Vec::new();
283        // We are mapping all elements of the field to the curve, verifying that
284        // map is not constant on that set.
285        for current_field_element in 0..101 {
286            map_range.push(
287                Elligator2Map::map_to_curve(F101::from(current_field_element as u64)).unwrap(),
288            );
289        }
290
291        let mut counts =
292            HashMap::with_hasher(core::hash::BuildHasherDefault::<DefaultHasher>::default());
293
294        let mode = map_range
295            .iter()
296            .copied()
297            .max_by_key(|&n| {
298                let count = counts.entry(n).or_insert(0);
299                *count += 1;
300                *count
301            })
302            .unwrap();
303
304        assert!(
305            *counts.get(&mode).unwrap() != 101,
306            "a constant hash function is not good."
307        );
308    }
309}
ark_ec/hashing/curve_maps/elligator2.rs

ark_ec/hashing/curve_maps/
elligator2.rs
