pq-mayo 0.3.0

MAYO post-quantum signature scheme
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

// SPDX-License-Identifier: Apache-2.0 OR MIT

//! Constant-time solution sampling for the linearized MAYO system.

use crate::echelon::{ct_compare_8, ef};
use crate::gf16::{mat_mul, mul_fx8, sub_f};

/// Sample a solution x to Ax = y, with r used as randomness.
///
/// - `a` is an `m x a_cols` matrix (last column will be overwritten with y - Ar)
/// - `y` is a vector with `m` elements
/// - `r` and `x` are `k*o` bytes long
///
/// Returns `true` on success, `false` if the system is singular.
#[allow(clippy::too_many_arguments)]
pub(crate) fn sample_solution(
    a: &mut [u8],
    y: &[u8],
    r: &[u8],
    x: &mut [u8],
    k: usize,
    o: usize,
    m: usize,
    a_cols: usize,
) -> bool {
    let ko = k * o;

    // x <- r
    x[..ko].copy_from_slice(&r[..ko]);

    // Compute Ar
    let mut ar = vec![0u8; m];
    // Clear last column of A
    for i in 0..m {
        a[ko + i * a_cols] = 0;
    }
    mat_mul(a, r, &mut ar, a_cols, m, 1);

    // Move y - Ar to last column of matrix A
    for i in 0..m {
        a[ko + i * a_cols] = sub_f(y[i], ar[i]);
    }

    // Row echelon form
    ef(a, m, a_cols);

    // Compute rank indicator before back-substitution; the result is saved and
    // returned only after the unconditional back-substitution completes, so no
    // secret-dependent branch is visible before that work finishes.
    let mut full_rank: u8 = 0;
    for i in 0..(a_cols - 1) {
        full_rank |= a[(m - 1) * a_cols + i];
    }

    // Back substitution — runs unconditionally regardless of rank to prevent
    // timing leaks; caller retries when we return false.
    for row in (0..m).rev() {
        let mut finished: u8 = 0;
        let col_upper_bound = (row + 32 / (m - row)).min(ko);

        for col in row..=col_upper_bound {
            // Constant-time check if this is the pivot column
            let correct_column = ct_compare_8(a[row * a_cols + col], 0) & !finished;

            let u = correct_column & a[row * a_cols + a_cols - 1];
            x[col] ^= u;

            // Update rows above
            let mut i = 0;
            while i < row {
                let end = (i + 8).min(row);
                let mut tmp: u64 = 0;
                for ii in i..end {
                    tmp ^= u64::from(a[ii * a_cols + col]) << ((ii - i) * 8);
                }
                tmp = mul_fx8(u, tmp);

                for ii in i..end {
                    a[ii * a_cols + a_cols - 1] ^= ((tmp >> ((ii - i) * 8)) & 0xf) as u8;
                }
                i += 8;
            }

            finished |= correct_column;
        }
    }

    full_rank != 0
}