
## miden::core::crypto::dsa::falcon512_poseidon2
| Procedure | Description |
| ----------- | ------------- |
| mod_12289 | Given dividend ( i.e. a u64 given by its lower and higher u32 decomposition ) on the stack,<br />this routine computes c = a % M where M = 12289<br /><br />Expected stack state<br /><br />[a_hi, a_lo, ...]<br /><br />Output stack state looks like<br /><br />[c, ...] \| c = a % M<br /><br />Note that it is the responsibility of the calling procedure to ensure that `a_hi` and `a_lo` are<br />within the appropriate range i.e., they are u32-s.<br /><br />Cycles: 29<br /> |
| hash_to_point | Takes as input a message digest, a nonce of size 40 bytes represented as 8 field elements<br />and a pointer. The procedure absorbs MSG and NONCE into a fresh Poseidon2 state and squeezes the<br />coefficients of a polynomial c representing the hash-to-point of (MSG \|\| NONCE). The coefficients<br />are then saved in the memory region [c_ptr, c_ptr + 512).<br />This implementation of the `hash_to_point` procedure avoids the rejection-sampling step<br />required in the per-the-spec algorithm by using the observation on page 31 in<br />https://falcon-sign.info/falcon.pdf<br /><br />Input: [c_ptr, MSG, NONCE1, NONCE0, ...]<br />Output: [...]<br /><br />Cycles: ~1430<br /> |
| load_h_s2_and_product | Takes as input PK, the hash of the coefficients of the polynomial `h` representing the expanded<br />public key, and a pointer to the memory location where the coefficients of the polynomial `h`<br />will be stored.<br />The procedure loads `h` from the advice stack and compares its hash with the provided hash `PK`.<br />It then loads the polynomial `s2` representing the signature from the advice stack and lays it<br />in memory right after `h`.<br />After that, it loads the claimed polynomial `h * s2` in Z_Q[x] where Q is the Miden VM prime<br />from the advice stack and lays it right after `s2`.<br />The hash of `h`, `s2` and the claimed product is also computed and the first two field elements<br />of the digest (i.e., the Fiat-Shamir challenge) are used in order to check that<br />pi == h * s2 in Z_Q[x] by evaluating both sides at the random point. Note that since we need<br />to hash the polynomials before computing their evaluations, the procedure receives<br />the evaluation point non-deterministically so that it can perform the evaluations while hashing<br />is still going on. After hashing of the polynomials is finished, the procedure checks that<br />the evaluation point was indeed derived correctly from the hash of all 3 polynomials.<br /><br />Inputs:<br />Operand stack: [ptr, PK, ...]<br />Advice stack:  [tau0, tau1, h_0, ..., h_511, s2_0, ..., s2_511, pi_0, ..., pi_1022, ...]<br />Outputs:<br />Operand stack: []<br />Advice stack:  []<br /><br />Cycles: 6780<br /> |
| norm_sq | Normalizes an `e` in [0, M) to be in [-(M-1) << 1, (M-1) << 1) and returns its square norm.<br /><br />We use the following formula to do so:<br />normalize(e) = e^2 - phi * (2*M*e - M^2) where phi := (e > (M - 1)/2)<br /><br />The formula implements:<br /><br />if e > (M-1)/2:<br />return (M - e)^2<br />else:<br />return e^2<br /><br />The use of the formula avoids using the if-else block.<br /><br />Input: [e, ...]<br />Output [norm(e)^2, ...]<br /><br />Cycles: 20<br /> |
| diff_mod_M | Given a tuple (u, w, v), we want to compute (v - (u + (- w % M) % M) % M), where:<br /><br />1. v is a field element given by its u32 decomposition i.e., (c_lo, c_hi) such that<br />v = c_hi * 2**32 + c_lo<br />2. w is a field element representing the (i+512)-th coefficient of the product polynomial<br />pi (i.e., h * s2). We are guaranteed that w is at most 512 * (M-1)^2.<br />3. u is a field element representing the i-th coefficient of the product polynomial<br />pi (i.e., h * s2). We are guaranteed that u is at most 512 * (M-1)^2.<br /><br />We can avoid doing three modular reductions by using the following facts:<br /><br />1. M is much smaller than the Miden prime Q. Precisely, M * 2^50 < Q<br />2. The coefficients of the product polynomial, u and w, are strictly less than J := 512 * M^2.<br />3. The coefficients of c are at most M - 1.<br /><br />This means that we can substitute (v - (u + (- w % M) % M) % M) with  v + w + J - u<br />(note J % M = 0) without risking Q-underflow but we can still overflow.<br />For this reason, we use the u32 decomposition of v and perform the addition of<br />v and w + J - u as u64. Note that \|w + J - u\| <= 1024 * (M - 1)^2<br />and hence there is the possibility of an overflow when we add v and w + J - u as u64.<br />When there is an overflow, we add 10952, which is equal to 2^32 % M, to the upper u32 limb of<br />the result of (v + (w + J - u)). Note that since \|w + J - u\| <= 1024 * (M-1)^2 < 2^38, and<br />10952 < M, we are guaranteed that this final u32 addition to the upper limb will not overflow.<br /><br />To get the final result we reduce (v + w + J - u) modulo M.<br /><br />Input: [pi0, pi512 + J, c_hi, c_lo, ...]<br />Output: [e, ...]<br /><br />Cycles: 45<br /> |
| compute_s1_norm_sq | Takes a pointer to a polynomial pi of degree less than 1024 with coefficients in Z_Q and<br />a polynomial c of degree 512 with coefficients also in Z_Q, where Q is the Miden prime.<br />The goal is to compute s1 = c - pi  = c - h * s2 in Z_M[x]/(phi) where M is the Falcon prime.<br />The pointer pi_ptr points both to pi and c through the relation c_ptr = pi_ptr + offset<br />where offset := 1281.<br />The naive way to compute s1 would be to first reduce the polynomial pi modulo the Falcon<br />prime M and then modulo the irreducible polynomial phi = x^512 + 1. Then we would need to negate<br />the coefficients of pi modulo M and only then can we add these coefficients to the coefficients<br />of c and then reduce the result modulo M one more time.<br />Knowing that the end goal of computing c is to compute its norm squared, we can do better.<br /><br />We can compute s1 in a single pass by delaying the M-modular reduction til the end. This can<br />be achieved through a careful analysis of the computation of the difference between pi and c.<br /><br />The i-th coefficient s1_i of s1 is equal to c_i - (pi_i - pi_{512 + i}) which is equal to<br />c_i  + pi_{512 + i} - pi_i. Now, we know that the size of the pi_i coefficients is bounded by<br />J := 512 * M^2 and this means that J + pi_{512 + i} - pi_i does not Q-underflow and since<br />J = 0 mod M, the addition of J does not affect the final result. It is also important to<br />note that adding J does not Q-overflow by virtue of M * 2^50 < Q.<br />All of the above implies that we can compute s1_i with only one modular reduction at the end,<br />in addition to one modular reduction applied to c_i.<br />Moreover, since we are only interested in the square norm of s1_i, we do not have to store<br />s1_i and then load it at a later point, and instead we can immediately follow the computation<br />of s1_i with computing its square norm.<br />After computing the square norm of s1_i, we can accumulate into an accumulator to compute the<br />sum of the square norms of all the coefficients of polynomial c. Using the overflow stack, this<br />can be delayed til the end.<br /><br />Input: [pi_ptr, ...]<br />Output: [norm_sq(s1), ...]<br /><br />Cycles: 40450<br /> |
| compute_s2_norm_sq | Compute the square norm of the polynomial s2 given a pointer to its coefficients.<br /><br />Input: [s2_ptr, ...]<br />Output: [norm_sq(s2), ...]<br /><br />Cycles: 11150<br /> |
| verify | Verifies a signature against a public key and a message. The procedure gets as inputs the hash<br />of the public key and the hash of the message via the operand stack. The signature is expected<br />to be present on the advice stack.<br /><br />The signature is valid if and only if the procedure returns.<br /><br />Inputs:<br />Operand stack: [PK, MSG, ...]<br />Advice stack:  [SIGNATURE]<br />Outputs:<br />Operand stack: []<br />Advice stack:  []<br /><br />where:<br />- tau = (tau0, tau1) is an element in the quadratic field extension at which the product relation<br />between `h * s2 = pi` is checked.<br />- h_i are the coefficients of the expanded public key polynomial.<br />- s2_i are the coefficients of the signature polynomial.<br />- pi_i are the coefficients of `h * s2` in Z_Q[x] where Q is the Miden VM prime.<br />- nonce_i are field elements representing the nonce associated to the signature.<br /><br />Cycles: ~ 59859<br /> |
| move_sig_from_map_to_adv_stack | Moves the signature from the advice map to the advice stack, where the signature is stored in<br />the hashmap at key `hash(MSG \|\| PK)`, where `hash()` is the Poseidon2 hash. The signature is<br />expected to be stored in reverse order, so that it gets pushed on the advice stack in the<br />correct order.<br /><br />Inputs:<br />Operand stack: [PK, MSG, ...]<br />Advice stack:  []<br />Advice map: hash(MSG \|\| PK) -> SIGNATURE<br />Outputs:<br />Operand stack: [PK, MSG, ...]<br />Advice stack:  [SIGNATURE]<br /> |
