snarkvm_console_algorithms/elligator2/
encode.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 encoded affine group element and sign, given a field element.
20    pub fn encode(input: &Field<E>) -> Result<(Group<E>, bool)> {
21        // Compute the encoding of the input field element.
22        let (encoding, sign_high) = Self::encode_without_cofactor_clear(input)?;
23
24        // Cofactor clear the twisted Edwards element (x, y).
25        let group = encoding.mul_by_cofactor().to_affine();
26        ensure!(group.is_on_curve(), "Elligator2 failed: element is not on curve");
27        ensure!(group.is_in_correct_subgroup_assuming_on_curve(), "Elligator2 failed: element in incorrect subgroup");
28
29        Ok((Group::new(group), sign_high))
30    }
31
32    /// Returns the encoded affine group element and sign, given a field element.
33    pub(crate) fn encode_without_cofactor_clear(input: &Field<E>) -> Result<(Group<E>, bool)> {
34        ensure!(
35            Group::<E>::EDWARDS_D.legendre().is_qnr(),
36            "D on the twisted Edwards curve must be a quadratic nonresidue"
37        );
38        ensure!(!input.is_zero(), "Inputs to Elligator2 must be nonzero (inverses will fail)");
39
40        let one = Field::<E>::one();
41
42        // Store the sign of the input, to be returned with the output.
43        let sign_high = input > &input.neg();
44
45        // Compute the mapping from Fq to E(Fq) as a Montgomery element (u, v).
46        let (u, v) = {
47            // Compute the coefficients for the Weierstrass form: y^2 == x^3 + A * x^2 + B * x.
48            let (a, b) = match Group::<E>::MONTGOMERY_B.inverse() {
49                Ok(b_inverse) => (Group::MONTGOMERY_A * b_inverse, b_inverse.square()),
50                Err(_) => bail!("Montgomery B must be invertible in order to use Elligator2"),
51            };
52
53            // Let (u, r) = (D, input).
54            let (u, r) = (Group::EDWARDS_D, input);
55
56            // Let ur2 = u * r^2;
57            let ur2 = u * r.square();
58
59            // Ensure A^2 * ur^2 != B(1 + ur^2)^2.
60            ensure!(a.square() * ur2 != b * (one + ur2).square(), "Elligator2 failed: A^2 * ur^2 == B(1 + ur^2)^2");
61
62            // Let v = -A / (1 + ur^2).
63            let v = -a * (one + ur2).inverse().map_err(|_| anyhow!("Elligator2 failed: (1 + ur^2) == 0"))?;
64
65            // Ensure v is nonzero.
66            ensure!(!v.is_zero(), "Elligator2 failed: v == 0");
67
68            // Let e = legendre(v^3 + Av^2 + Bv).
69            let v2 = v.square();
70            let e = ((v2 * v) + (a * v2) + (b * v)).legendre();
71
72            // Ensure e is nonzero.
73            ensure!(!e.is_zero(), "Elligator2 failed: e == 0");
74
75            // Let x = ev - ((1 - e) * A/2).
76            let x = match e {
77                LegendreSymbol::Zero => -a * Field::<E>::half(),
78                LegendreSymbol::QuadraticResidue => v,
79                LegendreSymbol::QuadraticNonResidue => -v - a,
80            };
81
82            // Ensure x is nonzero.
83            ensure!(!x.is_zero(), "Elligator2 failed: x == 0");
84
85            // Let y = -e * sqrt(x^3 + Ax^2 + Bx).
86            let x2 = x.square();
87            let rhs = (x2 * x) + (a * x2) + (b * x);
88            let value =
89                rhs.even_square_root().map_err(|_| anyhow!("Elligator2 failed: even_sqrt(x^3 + Ax^2 + Bx) failed"))?;
90
91            let y = match e {
92                LegendreSymbol::Zero => Field::<E>::zero(),
93                LegendreSymbol::QuadraticResidue => -value,
94                LegendreSymbol::QuadraticNonResidue => value,
95            };
96
97            // Ensure y is nonzero.
98            ensure!(!y.is_zero(), "Elligator2 failed: y == 0");
99
100            // Ensure (x, y) is a valid Weierstrass element on: y^2 == x^3 + A * x^2 + B * x.
101            ensure!(y.square() == rhs, "Elligator2 failed: y^2 != x^3 + A * x^2 + B * x");
102
103            // Convert the Weierstrass element (x, y) to Montgomery element (u, v).
104            let u = x * Group::MONTGOMERY_B;
105            let v = y * Group::MONTGOMERY_B;
106
107            // Ensure (u, v) is a valid Montgomery element on: B * v^2 == u^3 + A * u^2 + u
108            let u2 = u.square();
109            ensure!(
110                Group::MONTGOMERY_B * v.square() == (u2 * u) + (Group::MONTGOMERY_A * u2) + u,
111                "Elligator2 failed: B * v^2 != u^3 + A * u^2 + u"
112            );
113
114            (u, v)
115        };
116
117        // Convert the Montgomery element (u, v) to the twisted Edwards element (x, y).
118        let x = u * v.inverse().map_err(|_| anyhow!("Elligator2 failed: v == 0"))?;
119        let y = (u - one) * (u + one).inverse().map_err(|_| anyhow!("Elligator2 failed: (u + 1) == 0"))?;
120
121        // Recover the point from the twisted Edwards element (x, y).
122        let point = Group::from_xy_coordinates_unchecked(x, y);
123        // Ensure the recovered point is on the curve.
124        ensure!(point.to_affine().is_on_curve(), "Elligator2 failed: point is not on the curve");
125        // Return the recovered point.
126        Ok((point, sign_high))
127    }
128}
snarkvm_console_algorithms/elligator2/encode.rs

snarkvm_console_algorithms/elligator2/
encode.rs
