decaf377/ark_curve/
elligator.rs

1#![allow(non_snake_case)]
2use ark_ec::twisted_edwards::TECurveConfig;
3
4use crate::ark_curve::edwards::{Decaf377EdwardsConfig, EdwardsProjective};
5
6use crate::{
7    ark_curve::constants::{ONE, TWO, ZETA},
8    ark_curve::on_curve::OnCurve,
9    sign::Sign,
10    Element, Fq,
11};
12
13impl Element {
14    /// Elligator 2 map to decaf377 point
15    fn elligator_map(r_0: &Fq) -> Element {
16        // Ref: `Decaf_1_1_Point.elligator` (optimized) in `ristretto.sage`
17        let A = Decaf377EdwardsConfig::COEFF_A;
18        let D = Decaf377EdwardsConfig::COEFF_D;
19
20        let r = ZETA * r_0.square();
21
22        let den = (D * r - (D - A)) * ((D - A) * r - D);
23        let num = (r + *ONE) * (A - *TWO * D);
24
25        let x = num * den;
26        let (iss, mut isri) = Fq::sqrt_ratio_zeta(&ONE, &x);
27
28        let sgn;
29        let twiddle;
30        if iss {
31            sgn = *ONE;
32            twiddle = *ONE;
33        } else {
34            sgn = -(*ONE);
35            twiddle = *r_0;
36        }
37
38        isri *= twiddle;
39
40        let mut s = isri * num;
41        let t = -(sgn) * isri * s * (r - *ONE) * (A - *TWO * D).square() - *ONE;
42
43        if s.is_negative() == iss {
44            s = -s
45        }
46
47        // Convert point to extended projective (X : Y : Z : T)
48        let E = *TWO * s;
49        let F = *ONE + Decaf377EdwardsConfig::COEFF_A * s.square();
50        let G = *ONE - Decaf377EdwardsConfig::COEFF_A * s.square();
51        let H = t;
52        let result = Element {
53            inner: EdwardsProjective::new(E * H, F * G, E * G, F * H),
54        };
55
56        debug_assert!(
57            result.inner.is_on_curve(),
58            "resulting point must be on the curve",
59        );
60
61        result
62    }
63
64    /// Maps two field elements to a uniformly distributed decaf377 `Element`.
65    ///
66    /// The two field elements provided as inputs should be independently chosen.
67    pub fn hash_to_curve(r_1: &Fq, r_2: &Fq) -> Element {
68        let R_1 = Element::elligator_map(r_1);
69        let R_2 = Element::elligator_map(r_2);
70        &R_1 + &R_2
71    }
72
73    /// Maps a field element to a decaf377 `Element` suitable for CDH challenges.
74    pub fn encode_to_curve(r: &Fq) -> Element {
75        Element::elligator_map(r)
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use crate::ark_curve::edwards::EdwardsAffine;
82
83    use super::*;
84
85    #[test]
86    fn test_elligator() {
87        // These are the test cases from testElligatorDeterministic in ristretto.sage
88        let inputs = [
89            [
90                221, 101, 215, 58, 170, 229, 36, 124, 172, 234, 94, 214, 186, 163, 242, 30, 65,
91                123, 76, 74, 56, 60, 24, 213, 240, 137, 49, 189, 138, 39, 90, 6,
92            ],
93            [
94                23, 203, 214, 51, 26, 149, 7, 160, 228, 239, 208, 147, 124, 109, 75, 72, 64, 16,
95                64, 215, 53, 185, 249, 168, 188, 49, 22, 194, 118, 7, 242, 16,
96            ],
97            [
98                177, 123, 90, 180, 115, 7, 108, 183, 161, 167, 24, 15, 248, 218, 206, 227, 76, 137,
99                162, 187, 148, 174, 66, 44, 205, 1, 211, 91, 140, 50, 144, 1,
100            ],
101            [
102                204, 225, 121, 228, 145, 30, 86, 208, 132, 242, 203, 9, 153, 90, 195, 150, 215, 49,
103                166, 70, 78, 68, 47, 98, 30, 130, 115, 139, 168, 242, 238, 8,
104            ],
105            [
106                59, 150, 40, 159, 229, 96, 201, 47, 170, 163, 9, 208, 205, 201, 112, 241, 179, 82,
107                198, 79, 207, 160, 184, 245, 63, 189, 101, 115, 217, 228, 74, 13,
108            ],
109            [
110                74, 159, 227, 190, 73, 213, 131, 200, 50, 102, 249, 230, 48, 103, 85, 168, 239,
111                149, 7, 164, 12, 42, 217, 177, 189, 97, 214, 98, 102, 73, 10, 16,
112            ],
113            [
114                183, 227, 227, 192, 119, 10, 155, 143, 64, 60, 249, 165, 240, 39, 31, 197, 159,
115                121, 64, 82, 10, 1, 34, 35, 121, 34, 146, 69, 226, 196, 156, 14,
116            ],
117            [
118                61, 21, 56, 224, 11, 181, 71, 186, 238, 126, 234, 240, 14, 168, 75, 73, 251, 111,
119                175, 85, 108, 9, 77, 2, 88, 249, 24, 235, 53, 96, 51, 15,
120            ],
121        ];
122
123        let expected_xy_coordinates = [
124            [
125                ark_ff::MontFp!(
126                    "1267955849280145133999011095767946180059440909377398529682813961428156596086"
127                ),
128                ark_ff::MontFp!(
129                    "5356565093348124788258444273601808083900527100008973995409157974880178412098"
130                ),
131            ],
132            [
133                ark_ff::MontFp!(
134                    "1502379126429822955521756759528876454108853047288874182661923263559139887582"
135                ),
136                ark_ff::MontFp!(
137                    "7074060208122316523843780248565740332109149189893811936352820920606931717751"
138                ),
139            ],
140            [
141                ark_ff::MontFp!(
142                    "2943006201157313879823661217587757631000260143892726691725524748591717287835"
143                ),
144                ark_ff::MontFp!(
145                    "4988568968545687084099497807398918406354768651099165603393269329811556860241"
146                ),
147            ],
148            [
149                ark_ff::MontFp!(
150                    "2893226299356126359042735859950249532894422276065676168505232431940642875576"
151                ),
152                ark_ff::MontFp!(
153                    "5540423804567408742733533031617546054084724133604190833318816134173899774745"
154                ),
155            ],
156            [
157                ark_ff::MontFp!(
158                    "2950911977149336430054248283274523588551527495862004038190631992225597951816"
159                ),
160                ark_ff::MontFp!(
161                    "4487595759841081228081250163499667279979722963517149877172642608282938805393"
162                ),
163            ],
164            [
165                ark_ff::MontFp!(
166                    "3318574188155535806336376903248065799756521242795466350457330678746659358665"
167                ),
168                ark_ff::MontFp!(
169                    "7706453242502782485686954136003233626318476373744684895503194201695334921001"
170                ),
171            ],
172            [
173                ark_ff::MontFp!(
174                    "3753408652523927772367064460787503971543824818235418436841486337042861871179"
175                ),
176                ark_ff::MontFp!(
177                    "2820605049615187268236268737743168629279853653807906481532750947771625104256"
178                ),
179            ],
180            [
181                ark_ff::MontFp!(
182                    "7803875556376973796629423752730968724982795310878526731231718944925551226171"
183                ),
184                ark_ff::MontFp!(
185                    "7033839813997913565841973681083930410776455889380940679209912201081069572111"
186                ),
187            ],
188        ];
189
190        use ark_serialize::CanonicalDeserialize;
191
192        for (ind, input) in inputs.iter().enumerate() {
193            let input_element =
194                Fq::deserialize_compressed(&input[..]).expect("encoding of test vector is valid");
195
196            let expected: Element = Element {
197                inner: EdwardsAffine::new(
198                    crate::ark_curve::constants::from_ark_fq(expected_xy_coordinates[ind][0]),
199                    crate::ark_curve::constants::from_ark_fq(expected_xy_coordinates[ind][1]),
200                )
201                .into(),
202            };
203
204            let actual = Element::elligator_map(&input_element);
205
206            assert_eq!(actual, expected);
207        }
208    }
209}
decaf377/ark_curve/elligator.rs

decaf377/ark_curve/
elligator.rs
