miden-crypto/src/dsa/rpo_falcon512/signature.rs
src/dsa/rpo_falcon512/signature.rsRaw
1use alloc::{string::ToString, vec::Vec};
2use core::ops::Deref;
3
4use super::{
5 hash_to_point::hash_to_point_rpo256,
6 keys::PubKeyPoly,
7 math::{FalconFelt, FastFft, Polynomial},
8 ByteReader, ByteWriter, Deserializable, DeserializationError, Felt, Nonce, Rpo256,
9 Serializable, Word, LOG_N, MODULUS, N, SIG_L2_BOUND, SIG_POLY_BYTE_LEN,
10};
11use num::Zero;
12
13// FALCON SIGNATURE
14// ================================================================================================
15
16/// An RPO Falcon512 signature over a message.
17///
18/// The signature is a pair of polynomials (s1, s2) in (Z_p\[x\]/(phi))^2 a nonce `r`, and a public
19/// key polynomial `h` where:
20/// - p := 12289
21/// - phi := x^512 + 1
22///
23/// The signature verifies against a public key `pk` if and only if:
24/// 1. s1 = c - s2 * h
25/// 2. |s1|^2 + |s2|^2 <= SIG_L2_BOUND
26///
27/// where |.| is the norm and:
28/// - c = HashToPoint(r || message)
29/// - pk = Rpo256::hash(h)
30///
31/// Here h is a polynomial representing the public key and pk is its digest using the Rpo256 hash
32/// function. c is a polynomial that is the hash-to-point of the message being signed.
33///
34/// The polynomial h is serialized as:
35/// 1. 1 byte representing the log2(512) i.e., 9.
36/// 2. 896 bytes for the public key itself.
37///
38/// The signature is serialized as:
39/// 1. A header byte specifying the algorithm used to encode the coefficients of the `s2` polynomial
40/// together with the degree of the irreducible polynomial phi. For RPO Falcon512, the header
41/// byte is set to `10111001` which differentiates it from the standardized instantiation of
42/// the Falcon signature.
43/// 2. 40 bytes for the nonce.
44/// 4. 625 bytes encoding the `s2` polynomial above.
45///
46/// The total size of the signature (including the extended public key) is 1563 bytes.
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct Signature {
49 header: SignatureHeader,
50 nonce: Nonce,
51 s2: SignaturePoly,
52 h: PubKeyPoly,
53}
54
55impl Signature {
56 // CONSTRUCTOR
57 // --------------------------------------------------------------------------------------------
58 pub fn new(nonce: Nonce, h: PubKeyPoly, s2: SignaturePoly) -> Signature {
59 Self {
60 header: SignatureHeader::default(),
61 nonce,
62 s2,
63 h,
64 }
65 }
66
67 // PUBLIC ACCESSORS
68 // --------------------------------------------------------------------------------------------
69
70 /// Returns the public key polynomial h.
71 pub fn pk_poly(&self) -> &PubKeyPoly {
72 &self.h
73 }
74
75 // Returns the polynomial representation of the signature in Z_p[x]/(phi).
76 pub fn sig_poly(&self) -> &Polynomial<FalconFelt> {
77 &self.s2
78 }
79
80 /// Returns the nonce component of the signature.
81 pub fn nonce(&self) -> &Nonce {
82 &self.nonce
83 }
84
85 // SIGNATURE VERIFICATION
86 // --------------------------------------------------------------------------------------------
87
88 /// Returns true if this signature is a valid signature for the specified message generated
89 /// against the secret key matching the specified public key commitment.
90 pub fn verify(&self, message: Word, pubkey_com: Word) -> bool {
91 // compute the hash of the public key polynomial
92 let h_felt: Polynomial<Felt> = (&**self.pk_poly()).into();
93 let h_digest: Word = Rpo256::hash_elements(&h_felt.coefficients).into();
94 if h_digest != pubkey_com {
95 return false;
96 }
97
98 let c = hash_to_point_rpo256(message, &self.nonce);
99 h_digest == pubkey_com && verify_helper(&c, &self.s2, self.pk_poly())
100 }
101}
102
103impl Serializable for Signature {
104 fn write_into<W: ByteWriter>(&self, target: &mut W) {
105 target.write(&self.header);
106 target.write(&self.nonce);
107 target.write(&self.s2);
108 target.write(&self.h);
109 }
110}
111
112impl Deserializable for Signature {
113 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
114 let header = source.read()?;
115 let nonce = source.read()?;
116 let s2 = source.read()?;
117 let h = source.read()?;
118
119 Ok(Self { header, nonce, s2, h })
120 }
121}
122
123// SIGNATURE HEADER
124// ================================================================================================
125
126#[derive(Debug, Clone, PartialEq, Eq)]
127pub struct SignatureHeader(u8);
128
129impl Default for SignatureHeader {
130 /// According to section 3.11.3 in the specification [1], the signature header has the format
131 /// `0cc1nnnn` where:
132 ///
133 /// 1. `cc` signifies the encoding method. `01` denotes using the compression encoding method
134 /// and `10` denotes encoding using the uncompressed method.
135 /// 2. `nnnn` encodes `LOG_N`.
136 ///
137 /// For RPO Falcon 512 we use compression encoding and N = 512. Moreover, to differentiate the
138 /// RPO Falcon variant from the reference variant using SHAKE256, we flip the first bit in the
139 /// header. Thus, for RPO Falcon 512 the header is `10111001`
140 ///
141 /// [1]: https://falcon-sign.info/falcon.pdf
142 fn default() -> Self {
143 Self(0b1011_1001)
144 }
145}
146
147impl Serializable for &SignatureHeader {
148 fn write_into<W: ByteWriter>(&self, target: &mut W) {
149 target.write_u8(self.0)
150 }
151}
152
153impl Deserializable for SignatureHeader {
154 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
155 let header = source.read_u8()?;
156 let (encoding, log_n) = (header >> 4, header & 0b00001111);
157 if encoding != 0b1011 {
158 return Err(DeserializationError::InvalidValue(
159 "Failed to decode signature: not supported encoding algorithm".to_string(),
160 ));
161 }
162
163 if log_n != LOG_N {
164 return Err(DeserializationError::InvalidValue(
165 format!("Failed to decode signature: only supported irreducible polynomial degree is 512, 2^{log_n} was provided")
166 ));
167 }
168
169 Ok(Self(header))
170 }
171}
172
173// SIGNATURE POLYNOMIAL
174// ================================================================================================
175
176#[derive(Debug, Clone, PartialEq, Eq)]
177pub struct SignaturePoly(pub Polynomial<FalconFelt>);
178
179impl Deref for SignaturePoly {
180 type Target = Polynomial<FalconFelt>;
181
182 fn deref(&self) -> &Self::Target {
183 &self.0
184 }
185}
186
187impl From<Polynomial<FalconFelt>> for SignaturePoly {
188 fn from(pk_poly: Polynomial<FalconFelt>) -> Self {
189 Self(pk_poly)
190 }
191}
192
193impl TryFrom<&[i16; N]> for SignaturePoly {
194 type Error = ();
195
196 fn try_from(coefficients: &[i16; N]) -> Result<Self, Self::Error> {
197 if are_coefficients_valid(coefficients) {
198 Ok(Self(coefficients.to_vec().into()))
199 } else {
200 Err(())
201 }
202 }
203}
204
205impl Serializable for &SignaturePoly {
206 fn write_into<W: ByteWriter>(&self, target: &mut W) {
207 let sig_coeff: Vec<i16> = self.0.coefficients.iter().map(|a| a.balanced_value()).collect();
208 let mut sk_bytes = vec![0_u8; SIG_POLY_BYTE_LEN];
209
210 let mut acc = 0;
211 let mut acc_len = 0;
212 let mut v = 0;
213 let mut t;
214 let mut w;
215
216 // For each coefficient of x:
217 // - the sign is encoded on 1 bit
218 // - the 7 lower bits are encoded naively (binary)
219 // - the high bits are encoded in unary encoding
220 //
221 // Algorithm 17 p. 47 of the specification [1].
222 //
223 // [1]: https://falcon-sign.info/falcon.pdf
224 for &c in sig_coeff.iter() {
225 acc <<= 1;
226 t = c;
227
228 if t < 0 {
229 t = -t;
230 acc |= 1;
231 }
232 w = t as u16;
233
234 acc <<= 7;
235 let mask = 127_u32;
236 acc |= (w as u32) & mask;
237 w >>= 7;
238
239 acc_len += 8;
240
241 acc <<= w + 1;
242 acc |= 1;
243 acc_len += w + 1;
244
245 while acc_len >= 8 {
246 acc_len -= 8;
247
248 sk_bytes[v] = (acc >> acc_len) as u8;
249 v += 1;
250 }
251 }
252
253 if acc_len > 0 {
254 sk_bytes[v] = (acc << (8 - acc_len)) as u8;
255 }
256 target.write_bytes(&sk_bytes);
257 }
258}
259
260impl Deserializable for SignaturePoly {
261 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
262 let input = source.read_array::<SIG_POLY_BYTE_LEN>()?;
263
264 let mut input_idx = 0;
265 let mut acc = 0u32;
266 let mut acc_len = 0;
267 let mut coefficients = [FalconFelt::zero(); N];
268
269 // Algorithm 18 p. 48 of the specification [1].
270 //
271 // [1]: https://falcon-sign.info/falcon.pdf
272 for c in coefficients.iter_mut() {
273 acc = (acc << 8) | (input[input_idx] as u32);
274 input_idx += 1;
275 let b = acc >> acc_len;
276 let s = b & 128;
277 let mut m = b & 127;
278
279 loop {
280 if acc_len == 0 {
281 acc = (acc << 8) | (input[input_idx] as u32);
282 input_idx += 1;
283 acc_len = 8;
284 }
285 acc_len -= 1;
286 if ((acc >> acc_len) & 1) != 0 {
287 break;
288 }
289 m += 128;
290 if m >= 2048 {
291 return Err(DeserializationError::InvalidValue(
292 "Failed to decode signature: high bits {m} exceed 2048".to_string(),
293 ));
294 }
295 }
296 if s != 0 && m == 0 {
297 return Err(DeserializationError::InvalidValue(
298 "Failed to decode signature: -0 is forbidden".to_string(),
299 ));
300 }
301
302 let felt = if s != 0 { (MODULUS as u32 - m) as u16 } else { m as u16 };
303 *c = FalconFelt::new(felt as i16);
304 }
305
306 if (acc & ((1 << acc_len) - 1)) != 0 {
307 return Err(DeserializationError::InvalidValue(
308 "Failed to decode signature: Non-zero unused bits in the last byte".to_string(),
309 ));
310 }
311 Ok(Polynomial::new(coefficients.to_vec()).into())
312 }
313}
314
315// HELPER FUNCTIONS
316// ================================================================================================
317
318/// Takes the hash-to-point polynomial `c` of a message, the signature polynomial over
319/// the message `s2` and a public key polynomial and returns `true` is the signature is a valid
320/// signature for the given parameters, otherwise it returns `false`.
321fn verify_helper(c: &Polynomial<FalconFelt>, s2: &SignaturePoly, h: &PubKeyPoly) -> bool {
322 let h_fft = h.fft();
323 let s2_fft = s2.fft();
324 let c_fft = c.fft();
325
326 // compute the signature polynomial s1 using s1 = c - s2 * h
327 let s1_fft = c_fft - s2_fft.hadamard_mul(&h_fft);
328 let s1 = s1_fft.ifft();
329
330 // compute the norm squared of (s1, s2)
331 let length_squared_s1 = s1.norm_squared();
332 let length_squared_s2 = s2.norm_squared();
333 let length_squared = length_squared_s1 + length_squared_s2;
334
335 length_squared < SIG_L2_BOUND
336}
337
338/// Checks whether a set of coefficients is a valid one for a signature polynomial.
339fn are_coefficients_valid(x: &[i16]) -> bool {
340 if x.len() != N {
341 return false;
342 }
343
344 for &c in x {
345 if !(-2047..=2047).contains(&c) {
346 return false;
347 }
348 }
349
350 true
351}
352
353// TESTS
354// ================================================================================================
355
356#[cfg(test)]
357mod tests {
358 use super::{super::SecretKey, *};
359 use rand::SeedableRng;
360 use rand_chacha::ChaCha20Rng;
361
362 #[test]
363 fn test_serialization_round_trip() {
364 let seed = [0_u8; 32];
365 let mut rng = ChaCha20Rng::from_seed(seed);
366
367 let sk = SecretKey::with_rng(&mut rng);
368 let signature = sk.sign_with_rng(Word::default(), &mut rng);
369 let serialized = signature.to_bytes();
370 let deserialized = Signature::read_from_bytes(&serialized).unwrap();
371 assert_eq!(signature.sig_poly(), deserialized.sig_poly());
372 }
373}