miden-crypto/src/dsa/rpo_falcon512/keys/secret_key.rs
src/dsa/rpo_falcon512/keys/secret_key.rsRaw
1use alloc::{string::ToString, vec::Vec};
2
3use num::Complex;
4#[cfg(not(feature = "std"))]
5use num::Float;
6use num_complex::Complex64;
7use rand::Rng;
8
9use super::{
10 super::{
11 math::{ffldl, ffsampling, gram, normalize_tree, FalconFelt, FastFft, LdlTree, Polynomial},
12 signature::SignaturePoly,
13 ByteReader, ByteWriter, Deserializable, DeserializationError, Nonce, Serializable,
14 ShortLatticeBasis, Signature, Word, MODULUS, N, SIGMA, SIG_L2_BOUND,
15 },
16 PubKeyPoly, PublicKey,
17};
18use crate::dsa::rpo_falcon512::{
19 hash_to_point::hash_to_point_rpo256, math::ntru_gen, SIG_NONCE_LEN, SK_LEN,
20};
21
22// CONSTANTS
23// ================================================================================================
24
25const WIDTH_BIG_POLY_COEFFICIENT: usize = 8;
26const WIDTH_SMALL_POLY_COEFFICIENT: usize = 6;
27
28// SECRET KEY
29// ================================================================================================
30
31/// The secret key is a quadruple [[g, -f], [G, -F]] of polynomials with integer coefficients.
32///
33/// Each polynomial is of degree at most N = 512 and computations with these polynomials are done
34/// modulo the monic irreducible polynomial ϕ = x^N + 1. The secret key is a basis for a lattice
35/// and has the property of being short with respect to a certain norm and an upper bound
36/// appropriate for a given security parameter. The public key on the other hand is another basis
37/// for the same lattice and can be described by a single polynomial h with integer coefficients
38/// modulo ϕ. The two keys are related by the following relation:
39///
40/// 1. h = g /f [mod ϕ][mod p]
41/// 2. f.G - g.F = p [mod ϕ]
42///
43/// where p = 12289 is the Falcon prime. Equation 2 is called the NTRU equation.
44/// The secret key is generated by first sampling a random pair (f, g) of polynomials using
45/// an appropriate distribution that yields short but not too short polynomials with integer
46/// coefficients modulo ϕ. The NTRU equation is then used to find a matching pair (F, G).
47/// The public key is then derived from the secret key using equation 1.
48///
49/// To allow for fast signature generation, the secret key is pre-processed into a more suitable
50/// form, called the LDL tree, and this allows for fast sampling of short vectors in the lattice
51/// using Fast Fourier sampling during signature generation (ffSampling algorithm 11 in [1]).
52///
53/// [1]: https://falcon-sign.info/falcon.pdf
54#[derive(Debug, Clone)]
55pub struct SecretKey {
56 secret_key: ShortLatticeBasis,
57 tree: LdlTree,
58}
59
60#[allow(clippy::new_without_default)]
61impl SecretKey {
62 // CONSTRUCTORS
63 // --------------------------------------------------------------------------------------------
64
65 /// Generates a secret key from OS-provided randomness.
66 #[cfg(feature = "std")]
67 pub fn new() -> Self {
68 use rand::{rngs::StdRng, SeedableRng};
69
70 let mut rng = StdRng::from_entropy();
71 Self::with_rng(&mut rng)
72 }
73
74 /// Generates a secret_key using the provided random number generator `Rng`.
75 pub fn with_rng<R: Rng>(rng: &mut R) -> Self {
76 let basis = ntru_gen(N, rng);
77 Self::from_short_lattice_basis(basis)
78 }
79
80 /// Given a short basis [[g, -f], [G, -F]], computes the normalized LDL tree i.e., Falcon tree.
81 fn from_short_lattice_basis(basis: ShortLatticeBasis) -> SecretKey {
82 // FFT each polynomial of the short basis.
83 let basis_fft = to_complex_fft(&basis);
84 // compute the Gram matrix.
85 let gram_fft = gram(basis_fft);
86 // construct the LDL tree of the Gram matrix.
87 let mut tree = ffldl(gram_fft);
88 // normalize the leaves of the LDL tree.
89 normalize_tree(&mut tree, SIGMA);
90 Self { secret_key: basis, tree }
91 }
92
93 // PUBLIC ACCESSORS
94 // --------------------------------------------------------------------------------------------
95
96 /// Returns the polynomials of the short lattice basis of this secret key.
97 pub fn short_lattice_basis(&self) -> &ShortLatticeBasis {
98 &self.secret_key
99 }
100
101 /// Returns the public key corresponding to this secret key.
102 pub fn public_key(&self) -> PublicKey {
103 self.compute_pub_key_poly().into()
104 }
105
106 /// Returns the LDL tree associated to this secret key.
107 pub fn tree(&self) -> &LdlTree {
108 &self.tree
109 }
110
111 // SIGNATURE GENERATION
112 // --------------------------------------------------------------------------------------------
113
114 /// Signs a message with this secret key.
115 #[cfg(feature = "std")]
116 pub fn sign(&self, message: Word) -> Signature {
117 use rand::{rngs::StdRng, SeedableRng};
118
119 let mut rng = StdRng::from_entropy();
120 self.sign_with_rng(message, &mut rng)
121 }
122
123 /// Signs a message with the secret key relying on the provided randomness generator.
124 pub fn sign_with_rng<R: Rng>(&self, message: Word, rng: &mut R) -> Signature {
125 let mut nonce_bytes = [0u8; SIG_NONCE_LEN];
126 rng.fill_bytes(&mut nonce_bytes);
127 let nonce = Nonce::new(nonce_bytes);
128
129 let h = self.compute_pub_key_poly();
130 let c = hash_to_point_rpo256(message, &nonce);
131 let s2 = self.sign_helper(c, rng);
132
133 Signature::new(nonce, h, s2)
134 }
135
136 // HELPER METHODS
137 // --------------------------------------------------------------------------------------------
138
139 /// Derives the public key corresponding to this secret key using h = g /f [mod ϕ][mod p].
140 pub fn compute_pub_key_poly(&self) -> PubKeyPoly {
141 let g: Polynomial<FalconFelt> = self.secret_key[0].clone().into();
142 let g_fft = g.fft();
143 let minus_f: Polynomial<FalconFelt> = self.secret_key[1].clone().into();
144 let f = -minus_f;
145 let f_fft = f.fft();
146 let h_fft = g_fft.hadamard_div(&f_fft);
147 h_fft.ifft().into()
148 }
149
150 /// Signs a message polynomial with the secret key.
151 ///
152 /// Takes a randomness generator implementing `Rng` and message polynomial representing `c`
153 /// the hash-to-point of the message to be signed. It outputs a signature polynomial `s2`.
154 fn sign_helper<R: Rng>(&self, c: Polynomial<FalconFelt>, rng: &mut R) -> SignaturePoly {
155 let one_over_q = 1.0 / (MODULUS as f64);
156 let c_over_q_fft = c.map(|cc| Complex::new(one_over_q * cc.value() as f64, 0.0)).fft();
157
158 // B = [[FFT(g), -FFT(f)], [FFT(G), -FFT(F)]]
159 let [g_fft, minus_f_fft, big_g_fft, minus_big_f_fft] = to_complex_fft(&self.secret_key);
160 let t0 = c_over_q_fft.hadamard_mul(&minus_big_f_fft);
161 let t1 = -c_over_q_fft.hadamard_mul(&minus_f_fft);
162
163 loop {
164 let bold_s = loop {
165 let z = ffsampling(&(t0.clone(), t1.clone()), &self.tree, rng);
166 let t0_min_z0 = t0.clone() - z.0;
167 let t1_min_z1 = t1.clone() - z.1;
168
169 // s = (t-z) * B
170 let s0 = t0_min_z0.hadamard_mul(&g_fft) + t1_min_z1.hadamard_mul(&big_g_fft);
171 let s1 =
172 t0_min_z0.hadamard_mul(&minus_f_fft) + t1_min_z1.hadamard_mul(&minus_big_f_fft);
173
174 // compute the norm of (s0||s1) and note that they are in FFT representation
175 let length_squared: f64 =
176 (s0.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>()
177 + s1.coefficients.iter().map(|a| (a * a.conj()).re).sum::<f64>())
178 / (N as f64);
179
180 if length_squared > (SIG_L2_BOUND as f64) {
181 continue;
182 }
183
184 break [-s0, s1];
185 };
186
187 let s2 = bold_s[1].ifft();
188 let s2_coef: [i16; N] = s2
189 .coefficients
190 .iter()
191 .map(|a| a.re.round() as i16)
192 .collect::<Vec<i16>>()
193 .try_into()
194 .expect("The number of coefficients should be equal to N");
195
196 if let Ok(s2) = SignaturePoly::try_from(&s2_coef) {
197 return s2;
198 }
199 }
200 }
201}
202
203// SERIALIZATION / DESERIALIZATION
204// ================================================================================================
205
206impl Serializable for SecretKey {
207 fn write_into<W: ByteWriter>(&self, target: &mut W) {
208 let basis = &self.secret_key;
209
210 // header
211 let n = basis[0].coefficients.len();
212 let l = n.checked_ilog2().unwrap() as u8;
213 let header: u8 = (5 << 4) | l;
214
215 let neg_f = &basis[1];
216 let g = &basis[0];
217 let neg_big_f = &basis[3];
218
219 let mut buffer = Vec::with_capacity(1281);
220 buffer.push(header);
221
222 let f_i8: Vec<i8> = neg_f
223 .coefficients
224 .iter()
225 .map(|&a| FalconFelt::new(-a).balanced_value() as i8)
226 .collect();
227 let f_i8_encoded = encode_i8(&f_i8, WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
228 buffer.extend_from_slice(&f_i8_encoded);
229
230 let g_i8: Vec<i8> = g
231 .coefficients
232 .iter()
233 .map(|&a| FalconFelt::new(a).balanced_value() as i8)
234 .collect();
235 let g_i8_encoded = encode_i8(&g_i8, WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
236 buffer.extend_from_slice(&g_i8_encoded);
237
238 let big_f_i8: Vec<i8> = neg_big_f
239 .coefficients
240 .iter()
241 .map(|&a| FalconFelt::new(-a).balanced_value() as i8)
242 .collect();
243 let big_f_i8_encoded = encode_i8(&big_f_i8, WIDTH_BIG_POLY_COEFFICIENT).unwrap();
244 buffer.extend_from_slice(&big_f_i8_encoded);
245 target.write_bytes(&buffer);
246 }
247}
248
249impl Deserializable for SecretKey {
250 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
251 let byte_vector: [u8; SK_LEN] = source.read_array()?;
252
253 // check length
254 if byte_vector.len() < 2 {
255 return Err(DeserializationError::InvalidValue("Invalid encoding length: Failed to decode as length is different from the one expected".to_string()));
256 }
257
258 // read fields
259 let header = byte_vector[0];
260
261 // check fixed bits in header
262 if (header >> 4) != 5 {
263 return Err(DeserializationError::InvalidValue("Invalid header format".to_string()));
264 }
265
266 // check log n
267 let logn = (header & 15) as usize;
268 let n = 1 << logn;
269
270 // match against const variant generic parameter
271 if n != N {
272 return Err(DeserializationError::InvalidValue(
273 "Unsupported Falcon DSA variant".to_string(),
274 ));
275 }
276
277 if byte_vector.len() != SK_LEN {
278 return Err(DeserializationError::InvalidValue("Invalid encoding length: Failed to decode as length is different from the one expected".to_string()));
279 }
280
281 let chunk_size_f = ((n * WIDTH_SMALL_POLY_COEFFICIENT) + 7) >> 3;
282 let chunk_size_g = ((n * WIDTH_SMALL_POLY_COEFFICIENT) + 7) >> 3;
283 let chunk_size_big_f = ((n * WIDTH_BIG_POLY_COEFFICIENT) + 7) >> 3;
284
285 let f = decode_i8(&byte_vector[1..chunk_size_f + 1], WIDTH_SMALL_POLY_COEFFICIENT).unwrap();
286 let g = decode_i8(
287 &byte_vector[chunk_size_f + 1..(chunk_size_f + chunk_size_g + 1)],
288 WIDTH_SMALL_POLY_COEFFICIENT,
289 )
290 .unwrap();
291 let big_f = decode_i8(
292 &byte_vector[(chunk_size_f + chunk_size_g + 1)
293 ..(chunk_size_f + chunk_size_g + chunk_size_big_f + 1)],
294 WIDTH_BIG_POLY_COEFFICIENT,
295 )
296 .unwrap();
297
298 let f = Polynomial::new(f.iter().map(|&c| FalconFelt::new(c.into())).collect());
299 let g = Polynomial::new(g.iter().map(|&c| FalconFelt::new(c.into())).collect());
300 let big_f = Polynomial::new(big_f.iter().map(|&c| FalconFelt::new(c.into())).collect());
301
302 // big_g * f - g * big_f = p (mod X^n + 1)
303 let big_g = g.fft().hadamard_div(&f.fft()).hadamard_mul(&big_f.fft()).ifft();
304 let basis = [
305 g.map(|f| f.balanced_value()),
306 -f.map(|f| f.balanced_value()),
307 big_g.map(|f| f.balanced_value()),
308 -big_f.map(|f| f.balanced_value()),
309 ];
310 Ok(Self::from_short_lattice_basis(basis))
311 }
312}
313
314// HELPER FUNCTIONS
315// ================================================================================================
316
317/// Computes the complex FFT of the secret key polynomials.
318fn to_complex_fft(basis: &[Polynomial<i16>; 4]) -> [Polynomial<Complex<f64>>; 4] {
319 let [g, f, big_g, big_f] = basis.clone();
320 let g_fft = g.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
321 let minus_f_fft = f.map(|cc| -Complex64::new(*cc as f64, 0.0)).fft();
322 let big_g_fft = big_g.map(|cc| Complex64::new(*cc as f64, 0.0)).fft();
323 let minus_big_f_fft = big_f.map(|cc| -Complex64::new(*cc as f64, 0.0)).fft();
324 [g_fft, minus_f_fft, big_g_fft, minus_big_f_fft]
325}
326
327/// Encodes a sequence of signed integers such that each integer x satisfies |x| < 2^(bits-1)
328/// for a given parameter bits. bits can take either the value 6 or 8.
329pub fn encode_i8(x: &[i8], bits: usize) -> Option<Vec<u8>> {
330 let maxv = (1 << (bits - 1)) - 1_usize;
331 let maxv = maxv as i8;
332 let minv = -maxv;
333
334 for &c in x {
335 if c > maxv || c < minv {
336 return None;
337 }
338 }
339
340 let out_len = ((N * bits) + 7) >> 3;
341 let mut buf = vec![0_u8; out_len];
342
343 let mut acc = 0_u32;
344 let mut acc_len = 0;
345 let mask = ((1_u16 << bits) - 1) as u8;
346
347 let mut input_pos = 0;
348 for &c in x {
349 acc = (acc << bits) | (c as u8 & mask) as u32;
350 acc_len += bits;
351 while acc_len >= 8 {
352 acc_len -= 8;
353 buf[input_pos] = (acc >> acc_len) as u8;
354 input_pos += 1;
355 }
356 }
357 if acc_len > 0 {
358 buf[input_pos] = (acc >> (8 - acc_len)) as u8;
359 }
360
361 Some(buf)
362}
363
364/// Decodes a sequence of bytes into a sequence of signed integers such that each integer x
365/// satisfies |x| < 2^(bits-1) for a given parameter bits. bits can take either the value 6 or 8.
366pub fn decode_i8(buf: &[u8], bits: usize) -> Option<Vec<i8>> {
367 let mut x = [0_i8; N];
368
369 let mut i = 0;
370 let mut j = 0;
371 let mut acc = 0_u32;
372 let mut acc_len = 0;
373 let mask = (1_u32 << bits) - 1;
374 let a = (1 << bits) as u8;
375 let b = ((1 << (bits - 1)) - 1) as u8;
376
377 while i < N {
378 acc = (acc << 8) | (buf[j] as u32);
379 j += 1;
380 acc_len += 8;
381
382 while acc_len >= bits && i < N {
383 acc_len -= bits;
384 let w = (acc >> acc_len) & mask;
385
386 let w = w as u8;
387
388 let z = if w > b { w as i8 - a as i8 } else { w as i8 };
389
390 x[i] = z;
391 i += 1;
392 }
393 }
394
395 if (acc & ((1u32 << acc_len) - 1)) == 0 {
396 Some(x.to_vec())
397 } else {
398 None
399 }
400}