miden-crypto/src/dsa/rpo_falcon512/signature.rs
src/dsa/rpo_falcon512/signature.rsRaw
1use alloc::string::ToString;
2use core::cell::OnceCell;
3
4use super::{
5 ByteReader, ByteWriter, Deserializable, DeserializationError, Felt, NonceBytes, NonceElements,
6 Polynomial, PublicKeyBytes, Rpo256, Serializable, SignatureBytes, Word, MODULUS, N,
7 SIG_L2_BOUND, ZERO,
8};
9
10// FALCON SIGNATURE
11// ================================================================================================
12
13/// An RPO Falcon512 signature over a message.
14///
15/// The signature is a pair of polynomials (s1, s2) in (Z_p\[x\]/(phi))^2, where:
16/// - p := 12289
17/// - phi := x^512 + 1
18/// - s1 = c - s2 * h
19/// - h is a polynomial representing the public key and c is a polynomial that is the hash-to-point
20/// of the message being signed.
21///
22/// The signature verifies if and only if:
23/// 1. s1 = c - s2 * h
24/// 2. |s1|^2 + |s2|^2 <= SIG_L2_BOUND
25///
26/// where |.| is the norm.
27///
28/// [Signature] also includes the extended public key which is serialized as:
29/// 1. 1 byte representing the log2(512) i.e., 9.
30/// 2. 896 bytes for the public key. This is decoded into the `h` polynomial above.
31///
32/// The actual signature is serialized as:
33/// 1. A header byte specifying the algorithm used to encode the coefficients of the `s2` polynomial
34/// together with the degree of the irreducible polynomial phi.
35/// The general format of this byte is 0b0cc1nnnn where:
36/// a. cc is either 01 when the compressed encoding algorithm is used and 10 when the
37/// uncompressed algorithm is used.
38/// b. nnnn is log2(N) where N is the degree of the irreducible polynomial phi.
39/// The current implementation works always with cc equal to 0b01 and nnnn equal to 0b1001 and
40/// thus the header byte is always equal to 0b00111001.
41/// 2. 40 bytes for the nonce.
42/// 3. 625 bytes encoding the `s2` polynomial above.
43///
44/// The total size of the signature (including the extended public key) is 1563 bytes.
45#[derive(Debug, Clone)]
46pub struct Signature {
47 pub(super) pk: PublicKeyBytes,
48 pub(super) sig: SignatureBytes,
49
50 // Cached polynomial decoding for public key and signatures
51 pub(super) pk_polynomial: OnceCell<Polynomial>,
52 pub(super) sig_polynomial: OnceCell<Polynomial>,
53}
54
55impl Signature {
56 // PUBLIC ACCESSORS
57 // --------------------------------------------------------------------------------------------
58
59 /// Returns the public key polynomial h.
60 pub fn pub_key_poly(&self) -> Polynomial {
61 *self.pk_polynomial.get_or_init(|| {
62 // we assume that the signature was constructed with a valid public key, and thus
63 // expect() is OK here.
64 Polynomial::from_pub_key(&self.pk).expect("invalid public key")
65 })
66 }
67
68 /// Returns the nonce component of the signature represented as field elements.
69 ///
70 /// Nonce bytes are converted to field elements by taking consecutive 5 byte chunks
71 /// of the nonce and interpreting them as field elements.
72 pub fn nonce(&self) -> NonceElements {
73 // we assume that the signature was constructed with a valid signature, and thus
74 // expect() is OK here.
75 let nonce = self.sig[1..41].try_into().expect("invalid signature");
76 decode_nonce(nonce)
77 }
78
79 // Returns the polynomial representation of the signature in Z_p[x]/(phi).
80 pub fn sig_poly(&self) -> Polynomial {
81 *self.sig_polynomial.get_or_init(|| {
82 // we assume that the signature was constructed with a valid signature, and thus
83 // expect() is OK here.
84 Polynomial::from_signature(&self.sig).expect("invalid signature")
85 })
86 }
87
88 // HASH-TO-POINT
89 // --------------------------------------------------------------------------------------------
90
91 /// Returns a polynomial in Z_p\[x\]/(phi) representing the hash of the provided message.
92 pub fn hash_to_point(&self, message: Word) -> Polynomial {
93 hash_to_point(message, &self.nonce())
94 }
95
96 // SIGNATURE VERIFICATION
97 // --------------------------------------------------------------------------------------------
98 /// Returns true if this signature is a valid signature for the specified message generated
99 /// against key pair matching the specified public key commitment.
100 pub fn verify(&self, message: Word, pubkey_com: Word) -> bool {
101 // Make sure the expanded public key matches the provided public key commitment
102 let h = self.pub_key_poly();
103 let h_digest: Word = Rpo256::hash_elements(&h.to_elements()).into();
104 if h_digest != pubkey_com {
105 return false;
106 }
107
108 // Make sure the signature is valid
109 let s2 = self.sig_poly();
110 let c = self.hash_to_point(message);
111
112 let s1 = c - s2 * h;
113
114 let sq_norm = s1.sq_norm() + s2.sq_norm();
115 sq_norm <= SIG_L2_BOUND
116 }
117}
118
119// SERIALIZATION / DESERIALIZATION
120// ================================================================================================
121
122impl Serializable for Signature {
123 fn write_into<W: ByteWriter>(&self, target: &mut W) {
124 target.write_bytes(&self.pk);
125 target.write_bytes(&self.sig);
126 }
127}
128
129impl Deserializable for Signature {
130 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
131 let pk: PublicKeyBytes = source.read_array()?;
132 let sig: SignatureBytes = source.read_array()?;
133
134 // make sure public key and signature can be decoded correctly
135 let pk_polynomial = Polynomial::from_pub_key(&pk)
136 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?
137 .into();
138 let sig_polynomial = Polynomial::from_signature(&sig)
139 .map_err(|err| DeserializationError::InvalidValue(err.to_string()))?
140 .into();
141
142 Ok(Self { pk, sig, pk_polynomial, sig_polynomial })
143 }
144}
145
146// HELPER FUNCTIONS
147// ================================================================================================
148
149/// Returns a polynomial in Z_p[x]/(phi) representing the hash of the provided message and
150/// nonce.
151fn hash_to_point(message: Word, nonce: &NonceElements) -> Polynomial {
152 let mut state = [ZERO; Rpo256::STATE_WIDTH];
153
154 // absorb the nonce into the state
155 for (&n, s) in nonce.iter().zip(state[Rpo256::RATE_RANGE].iter_mut()) {
156 *s = n;
157 }
158 Rpo256::apply_permutation(&mut state);
159
160 // absorb message into the state
161 for (&m, s) in message.iter().zip(state[Rpo256::RATE_RANGE].iter_mut()) {
162 *s = m;
163 }
164
165 // squeeze the coefficients of the polynomial
166 let mut i = 0;
167 let mut res = [0_u16; N];
168 for _ in 0..64 {
169 Rpo256::apply_permutation(&mut state);
170 for a in &state[Rpo256::RATE_RANGE] {
171 res[i] = (a.as_int() % MODULUS as u64) as u16;
172 i += 1;
173 }
174 }
175
176 // using the raw constructor is OK here because we reduce all coefficients by the modulus above
177 unsafe { Polynomial::new(res) }
178}
179
180/// Converts byte representation of the nonce into field element representation.
181fn decode_nonce(nonce: &NonceBytes) -> NonceElements {
182 let mut buffer = [0_u8; 8];
183 let mut result = [ZERO; 8];
184 for (i, bytes) in nonce.chunks(5).enumerate() {
185 buffer[..5].copy_from_slice(bytes);
186 // we can safely (without overflow) create a new Felt from u64 value here since this value
187 // contains at most 5 bytes
188 result[i] = Felt::new(u64::from_le_bytes(buffer));
189 }
190
191 result
192}
193
194// TESTS
195// ================================================================================================
196
197#[cfg(all(test, feature = "std"))]
198mod tests {
199 use core::ffi::c_void;
200 use rand_utils::rand_vector;
201
202 use super::{
203 super::{ffi::*, KeyPair},
204 *,
205 };
206
207 // Wrappers for unsafe functions
208 impl Rpo128Context {
209 /// Initializes the RPO state.
210 pub fn init() -> Self {
211 let mut ctx = Rpo128Context { content: [0u64; 13] };
212 unsafe {
213 rpo128_init(&mut ctx as *mut Rpo128Context);
214 }
215 ctx
216 }
217
218 /// Absorbs data into the RPO state.
219 pub fn absorb(&mut self, data: &[u8]) {
220 unsafe {
221 rpo128_absorb(
222 self as *mut Rpo128Context,
223 data.as_ptr() as *const c_void,
224 data.len(),
225 )
226 }
227 }
228
229 /// Finalizes the RPO state to prepare for squeezing.
230 pub fn finalize(&mut self) {
231 unsafe { rpo128_finalize(self as *mut Rpo128Context) }
232 }
233 }
234
235 #[test]
236 fn test_hash_to_point() {
237 // Create a random message and transform it into a u8 vector
238 let msg_felts: Word = rand_vector::<Felt>(4).try_into().unwrap();
239 let msg_bytes = msg_felts
240 .iter()
241 .flat_map(|e| e.as_int().to_le_bytes())
242 .collect::<alloc::vec::Vec<_>>();
243
244 // Create a nonce i.e. a [u8; 40] array and pack into a [Felt; 8] array.
245 let nonce: [u8; 40] = rand_vector::<u8>(40).try_into().unwrap();
246
247 let mut buffer = [0_u8; 64];
248 for i in 0..8 {
249 buffer[8 * i] = nonce[5 * i];
250 buffer[8 * i + 1] = nonce[5 * i + 1];
251 buffer[8 * i + 2] = nonce[5 * i + 2];
252 buffer[8 * i + 3] = nonce[5 * i + 3];
253 buffer[8 * i + 4] = nonce[5 * i + 4];
254 }
255
256 // Initialize the RPO state
257 let mut rng = Rpo128Context::init();
258
259 // Absorb the nonce and message into the RPO state
260 rng.absorb(&buffer);
261 rng.absorb(&msg_bytes);
262 rng.finalize();
263
264 // Generate the coefficients of the hash-to-point polynomial.
265 let mut res: [u16; N] = [0; N];
266
267 unsafe {
268 PQCLEAN_FALCON512_CLEAN_hash_to_point_rpo(
269 &mut rng as *mut Rpo128Context,
270 res.as_mut_ptr(),
271 9,
272 );
273 }
274
275 // Check that the coefficients are correct
276 let nonce = decode_nonce(&nonce);
277 assert_eq!(res, hash_to_point(msg_felts, &nonce).inner());
278 }
279
280 #[test]
281 fn test_serialization_round_trip() {
282 let key = KeyPair::new().unwrap();
283 let signature = key.sign(Word::default()).unwrap();
284 let serialized = signature.to_bytes();
285 let deserialized = Signature::read_from_bytes(&serialized).unwrap();
286 assert_eq!(signature.sig_poly(), deserialized.sig_poly());
287 assert_eq!(signature.pub_key_poly(), deserialized.pub_key_poly());
288 }
289}