miden-crypto/src/dsa/rpo_falcon512/polynomial.rs
src/dsa/rpo_falcon512/polynomial.rsRaw
1use super::{FalconError, Felt, Vec, LOG_N, MODULUS, MODULUS_MINUS_1_OVER_TWO, N, PK_LEN};
2use core::ops::{Add, Mul, Sub};
3
4// FALCON POLYNOMIAL
5// ================================================================================================
6
7/// A polynomial over Z_p[x]/(phi) where phi := x^512 + 1
8#[derive(Debug, Copy, Clone, PartialEq)]
9pub struct Polynomial([u16; N]);
10
11impl Polynomial {
12 // CONSTRUCTORS
13 // --------------------------------------------------------------------------------------------
14
15 /// Constructs a new polynomial from a list of coefficients.
16 ///
17 /// # Safety
18 /// This constructor validates that the coefficients are in the valid range only in debug mode.
19 pub unsafe fn new(data: [u16; N]) -> Self {
20 for value in data {
21 debug_assert!(value < MODULUS);
22 }
23
24 Self(data)
25 }
26
27 /// Decodes raw bytes representing a public key into a polynomial in Z_p[x]/(phi).
28 ///
29 /// # Errors
30 /// Returns an error if:
31 /// - The provided input is not exactly 897 bytes long.
32 /// - The first byte of the input is not equal to log2(512) i.e., 9.
33 /// - Any of the coefficients encoded in the provided input is greater than or equal to the
34 /// Falcon field modulus.
35 pub fn from_pub_key(input: &[u8]) -> Result<Self, FalconError> {
36 if input.len() != PK_LEN {
37 return Err(FalconError::PubKeyDecodingInvalidLength(input.len()));
38 }
39
40 if input[0] != LOG_N as u8 {
41 return Err(FalconError::PubKeyDecodingInvalidTag(input[0]));
42 }
43
44 let mut acc = 0_u32;
45 let mut acc_len = 0;
46
47 let mut output = [0_u16; N];
48 let mut output_idx = 0;
49
50 for &byte in input.iter().skip(1) {
51 acc = (acc << 8) | (byte as u32);
52 acc_len += 8;
53
54 if acc_len >= 14 {
55 acc_len -= 14;
56 let w = (acc >> acc_len) & 0x3FFF;
57 if w >= MODULUS as u32 {
58 return Err(FalconError::PubKeyDecodingInvalidCoefficient(w));
59 }
60 output[output_idx] = w as u16;
61 output_idx += 1;
62 }
63 }
64
65 if (acc & ((1u32 << acc_len) - 1)) == 0 {
66 Ok(Self(output))
67 } else {
68 Err(FalconError::PubKeyDecodingExtraData)
69 }
70 }
71
72 /// Decodes the signature into the coefficients of a polynomial in Z_p[x]/(phi). It assumes
73 /// that the signature has been encoded using the uncompressed format.
74 ///
75 /// # Errors
76 /// Returns an error if:
77 /// - The signature has been encoded using a different algorithm than the reference compressed
78 /// encoding algorithm.
79 /// - The encoded signature polynomial is in Z_p[x]/(phi') where phi' = x^N' + 1 and N' != 512.
80 /// - While decoding the high bits of a coefficient, the current accumulated value of its
81 /// high bits is larger than 2048.
82 /// - The decoded coefficient is -0.
83 /// - The remaining unused bits in the last byte of `input` are non-zero.
84 pub fn from_signature(input: &[u8]) -> Result<Self, FalconError> {
85 let (encoding, log_n) = (input[0] >> 4, input[0] & 0b00001111);
86
87 if encoding != 0b0011 {
88 return Err(FalconError::SigDecodingIncorrectEncodingAlgorithm);
89 }
90 if log_n != 0b1001 {
91 return Err(FalconError::SigDecodingNotSupportedDegree(log_n));
92 }
93
94 let input = &input[41..];
95 let mut input_idx = 0;
96 let mut acc = 0u32;
97 let mut acc_len = 0;
98 let mut output = [0_u16; N];
99
100 for e in output.iter_mut() {
101 acc = (acc << 8) | (input[input_idx] as u32);
102 input_idx += 1;
103 let b = acc >> acc_len;
104 let s = b & 128;
105 let mut m = b & 127;
106
107 loop {
108 if acc_len == 0 {
109 acc = (acc << 8) | (input[input_idx] as u32);
110 input_idx += 1;
111 acc_len = 8;
112 }
113 acc_len -= 1;
114 if ((acc >> acc_len) & 1) != 0 {
115 break;
116 }
117 m += 128;
118 if m >= 2048 {
119 return Err(FalconError::SigDecodingTooBigHighBits(m));
120 }
121 }
122 if s != 0 && m == 0 {
123 return Err(FalconError::SigDecodingMinusZero);
124 }
125
126 *e = if s != 0 { (MODULUS as u32 - m) as u16 } else { m as u16 };
127 }
128
129 if (acc & ((1 << acc_len) - 1)) != 0 {
130 return Err(FalconError::SigDecodingNonZeroUnusedBitsLastByte);
131 }
132
133 Ok(Self(output))
134 }
135
136 // PUBLIC ACCESSORS
137 // --------------------------------------------------------------------------------------------
138
139 /// Returns the coefficients of this polynomial as integers.
140 pub fn inner(&self) -> [u16; N] {
141 self.0
142 }
143
144 /// Returns the coefficients of this polynomial as field elements.
145 pub fn to_elements(&self) -> Vec<Felt> {
146 self.0.iter().map(|&a| Felt::from(a)).collect()
147 }
148
149 // POLYNOMIAL OPERATIONS
150 // --------------------------------------------------------------------------------------------
151
152 /// Multiplies two polynomials over Z_p[x] without reducing modulo p. Given that the degrees
153 /// of the input polynomials are less than 512 and their coefficients are less than the modulus
154 /// q equal to 12289, the resulting product polynomial is guaranteed to have coefficients less
155 /// than the Miden prime.
156 ///
157 /// Note that this multiplication is not over Z_p[x]/(phi).
158 pub fn mul_modulo_p(a: &Self, b: &Self) -> [u64; 1024] {
159 let mut c = [0; 2 * N];
160 for i in 0..N {
161 for j in 0..N {
162 c[i + j] += a.0[i] as u64 * b.0[j] as u64;
163 }
164 }
165
166 c
167 }
168
169 /// Reduces a polynomial, that is the product of two polynomials over Z_p[x], modulo
170 /// the irreducible polynomial phi. This results in an element in Z_p[x]/(phi).
171 pub fn reduce_negacyclic(a: &[u64; 1024]) -> Self {
172 let mut c = [0; N];
173 for i in 0..N {
174 let ai = a[N + i] % MODULUS as u64;
175 let neg_ai = (MODULUS - ai as u16) % MODULUS;
176
177 let bi = (a[i] % MODULUS as u64) as u16;
178 c[i] = (neg_ai + bi) % MODULUS;
179 }
180
181 Self(c)
182 }
183
184 /// Computes the norm squared of a polynomial in Z_p[x]/(phi) after normalizing its
185 /// coefficients to be in the interval (-p/2, p/2].
186 pub fn sq_norm(&self) -> u64 {
187 let mut res = 0;
188 for e in self.0 {
189 if e > MODULUS_MINUS_1_OVER_TWO {
190 res += (MODULUS - e) as u64 * (MODULUS - e) as u64
191 } else {
192 res += e as u64 * e as u64
193 }
194 }
195 res
196 }
197}
198
199// Returns a polynomial representing the zero polynomial i.e. default element.
200impl Default for Polynomial {
201 fn default() -> Self {
202 Self([0_u16; N])
203 }
204}
205
206/// Multiplication over Z_p[x]/(phi)
207impl Mul for Polynomial {
208 type Output = Self;
209
210 fn mul(self, other: Self) -> <Self as Mul<Self>>::Output {
211 let mut result = [0_u16; N];
212 for j in 0..N {
213 for k in 0..N {
214 let i = (j + k) % N;
215 let a = self.0[j] as usize;
216 let b = other.0[k] as usize;
217 let q = MODULUS as usize;
218 let mut prod = a * b % q;
219 if (N - 1) < (j + k) {
220 prod = (q - prod) % q;
221 }
222 result[i] = ((result[i] as usize + prod) % q) as u16;
223 }
224 }
225
226 Polynomial(result)
227 }
228}
229
230/// Addition over Z_p[x]/(phi)
231impl Add for Polynomial {
232 type Output = Self;
233
234 fn add(self, other: Self) -> <Self as Add<Self>>::Output {
235 let mut res = self;
236 res.0.iter_mut().zip(other.0.iter()).for_each(|(x, y)| *x = (*x + *y) % MODULUS);
237
238 res
239 }
240}
241
242/// Subtraction over Z_p[x]/(phi)
243impl Sub for Polynomial {
244 type Output = Self;
245
246 fn sub(self, other: Self) -> <Self as Add<Self>>::Output {
247 let mut res = self;
248 res.0
249 .iter_mut()
250 .zip(other.0.iter())
251 .for_each(|(x, y)| *x = (*x + MODULUS - *y) % MODULUS);
252
253 res
254 }
255}
256
257// TESTS
258// ================================================================================================
259
260#[cfg(test)]
261mod tests {
262 use super::{Polynomial, N};
263
264 #[test]
265 fn test_negacyclic_reduction() {
266 let coef1: [u16; N] = rand_utils::rand_array();
267 let coef2: [u16; N] = rand_utils::rand_array();
268
269 let poly1 = Polynomial(coef1);
270 let poly2 = Polynomial(coef2);
271
272 assert_eq!(
273 poly1 * poly2,
274 Polynomial::reduce_negacyclic(&Polynomial::mul_modulo_p(&poly1, &poly2))
275 );
276 }
277}