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