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