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