miden_crypto/dsa/rpo_falcon512/
signature.rs

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

miden_crypto/dsa/rpo_falcon512/
signature.rs
