snarkvm_console_algorithms/elligator2/
decode.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use super::*;
17
18impl<E: Environment> Elligator2<E> {
19    /// Returns the decoded field element, given the encoded affine group element and sign.
20    pub fn decode(group: &Group<E>, sign_high: bool) -> Result<Field<E>> {
21        ensure!(
22            Group::<E>::EDWARDS_D.legendre().is_qnr(),
23            "D on the twisted Edwards curve must be a quadratic nonresidue"
24        );
25        ensure!(!group.is_zero(), "Inputs to Elligator2 must be nonzero (inverses will fail)");
26        ensure!((**group).to_affine().is_on_curve(), "Inputs to Elligator2 must be on the twisted Edwards curve");
27
28        // Compute the coefficients for the Weierstrass form: v^2 == u^3 + A * u^2 + B * u.
29        let (montgomery_b_inverse, a, b) = match Group::<E>::MONTGOMERY_B.inverse() {
30            Ok(b_inverse) => (b_inverse, Group::MONTGOMERY_A * b_inverse, b_inverse.square()),
31            Err(_) => bail!("Montgomery B must be invertible in order to use Elligator2"),
32        };
33
34        let (x, y) = group.to_xy_coordinates();
35
36        // Ensure that x != -A.
37        ensure!(x != -a, "Elligator2 failed: x == -A");
38
39        // Ensure that if y is 0, then x is 0.
40        if y.is_zero() {
41            ensure!(x.is_zero(), "Elligator2 failed: y == 0 but x != 0");
42        }
43
44        // Convert the twisted Edwards element (x, y) to the Weierstrass element (u, v)
45        let (u, v) = {
46            let one = Field::<E>::one();
47
48            let numerator = one + y;
49            let denominator = one - y;
50
51            // Compute u = (1 + y) / (1 - y).
52            let u = numerator * denominator.inverse().map_err(|_| anyhow!("Elligator2 failed: (1 - y) == 0"))?;
53
54            // Compute v = (1 + y) / ((1 - y) * x).
55            let v =
56                numerator * (denominator * x).inverse().map_err(|_| anyhow!("Elligator2 failed: x * (1 - y) == 0"))?;
57
58            // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u
59            let u2 = u.square();
60            ensure!(
61                Group::MONTGOMERY_B * v.square() == (u2 * u) + (Group::MONTGOMERY_A * u2) + u,
62                "Elligator2 failed: B * v^2 != u^3 + A * u^2 + u"
63            );
64
65            let u = u * montgomery_b_inverse;
66            let v = v * montgomery_b_inverse;
67
68            // Ensure (u, v) is a valid Weierstrass element on: v^2 == u^3 + A * u^2 + B * u
69            let u2 = u.square();
70            ensure!(v.square() == (u2 * u) + (a * u2) + (b * u), "Elligator2 failed: v^2 != u^3 + A * u^2 + B * u");
71
72            (u, v)
73        };
74
75        // Ensure -D * u * (u + A) is a residue.
76        let du = Group::EDWARDS_D * u;
77        let u_plus_a = u + a;
78        ensure!((-du * u_plus_a).legendre().is_qr(), "Elligator2 failed: -D * u * (u + A) is not a quadratic residue");
79
80        let v_reconstructed = v
81            .square()
82            .even_square_root()
83            .map_err(|_| anyhow!("Elligator2 failed: cannot compute the even square root for v^2"))?;
84        let exists_in_sqrt_fq2 = v_reconstructed == v;
85
86        let element = match exists_in_sqrt_fq2 {
87            // Let element = sqrt(-u / ((u + A) * D)).
88            true => {
89                -u * (u_plus_a * Group::EDWARDS_D)
90                    .inverse()
91                    .map_err(|_| anyhow!("Elligator2 failed: (u+A) * D == 0"))?
92            }
93            // Let element = sqrt(-(u + A) / Du)).
94            false => -u_plus_a * du.inverse().map_err(|_| anyhow!("Elligator2 failed: D * u == 0"))?,
95        }
96        .even_square_root()
97        .map_err(|_| anyhow!("Elligator2 failed: cannot compute the even square root for the element"))?;
98
99        match sign_high {
100            true => Ok(cmp::max(element, -element)),
101            false => Ok(cmp::min(element, -element)),
102        }
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109    use snarkvm_console_types::environment::Console;
110
111    type CurrentEnvironment = Console;
112
113    pub(crate) const ITERATIONS: usize = 10000;
114
115    #[test]
116    fn test_encode_and_decode() -> Result<()> {
117        let rng = &mut TestRng::default();
118
119        let mut high_ctr = 0usize;
120        let mut low_ctr = 0usize;
121
122        for _ in 0..ITERATIONS {
123            let expected = Uniform::rand(rng);
124
125            let (encoded, sign_high) = Elligator2::<CurrentEnvironment>::encode_without_cofactor_clear(&expected)?;
126            let decoded = Elligator2::<CurrentEnvironment>::decode(&encoded, sign_high)?;
127            assert_eq!(expected, decoded);
128
129            match sign_high {
130                true => high_ctr += 1,
131                false => low_ctr += 1,
132            }
133        }
134
135        println!("Sign high: {high_ctr}, sign low: {low_ctr}");
136        Ok(())
137    }
138
139    #[test]
140    fn test_zero_fails() {
141        let encode = Elligator2::<CurrentEnvironment>::encode(&Zero::zero());
142        assert!(encode.is_err());
143
144        let decode = Elligator2::<CurrentEnvironment>::decode(&Zero::zero(), true);
145        assert!(decode.is_err());
146        let decode = Elligator2::<CurrentEnvironment>::decode(&Zero::zero(), false);
147        assert!(decode.is_err());
148    }
149}
snarkvm_console_algorithms/elligator2/decode.rs

snarkvm_console_algorithms/elligator2/
decode.rs
