krypteia-quantica 0.1.0

//! Hypertree: a multi-layer tree-of-XMSS-trees structure (FIPS 205, Algorithms 12-13).
//!
//! The hypertree is a `d`-layer construction where each layer consists of XMSS trees
//! of height `h'`. The leaves of each upper-layer XMSS tree certify the roots of
//! lower-layer trees, forming a hierarchy with total height `h = d * h'`.
//!
//! This structure allows the scheme to support `2^h` FORS signing key pairs while
//! keeping each individual XMSS tree small (only `2^h'` leaves). The hypertree
//! signature consists of `d` XMSS signatures, one per layer, chained from the
//! bottom (layer 0) to the top (layer `d - 1`).

use super::address::Adrs;
use super::params::Params;
use super::xmss;
use alloc::vec::Vec;

/// Sign a message using the hypertree.
///
/// Implements Algorithm 12 of FIPS 205. Signs the `n`-byte message `m` (typically
/// a FORS public key) at the position identified by `idx_tree` and `idx_leaf`.
///
/// The signing process starts at layer 0, signs `m` with the XMSS tree at
/// `(layer=0, tree=idx_tree)` using leaf `idx_leaf`, then propagates the resulting
/// root up through layers 1 to `d - 1`, each time signing the previous layer's root.
///
/// Returns `SIG_HT`, the concatenation of `d` XMSS signatures, totaling
/// `d * (len + h') * n` bytes.
pub fn ht_sign<P: Params>(m: &[u8], sk_seed: &[u8], pk_seed: &[u8], idx_tree: u64, idx_leaf: u32) -> Vec<u8> {
    let xmss_sig_len = (P::LEN + P::H_PRIME) * P::N;
    let mut sig_ht = alloc::vec![0u8; P::D * xmss_sig_len];
    ht_sign_into::<P>(m, sk_seed, pk_seed, idx_tree, idx_leaf, &mut sig_ht);
    sig_ht
}

/// Streaming variant of [`ht_sign`] — writes the `D * (LEN + H') * N`
/// byte hypertree signature into the start of `out` (which must be
/// at least that size).
///
/// Each of the `D` XMSS signatures is written directly into its slot
/// inside `out`; the layer-`j` root is recovered from the slot that
/// was just written (`xmss_pk_from_sig`) rather than from a
/// temporary per-layer `Vec<u8>`.
pub fn ht_sign_into<P: Params>(m: &[u8], sk_seed: &[u8], pk_seed: &[u8], idx_tree: u64, idx_leaf: u32, out: &mut [u8]) {
    let xmss_sig_len = (P::LEN + P::H_PRIME) * P::N;
    debug_assert!(out.len() >= P::D * xmss_sig_len);

    let mut adrs = Adrs::new();
    adrs.set_tree_address(idx_tree);

    // Sign M at layer 0 directly into slot 0.
    adrs.set_layer_address(0);
    {
        let slot = &mut out[..xmss_sig_len];
        xmss::xmss_sign_into::<P>(m, sk_seed, idx_leaf, pk_seed, &mut adrs, slot);
    }
    // Recover the layer-0 root from the slot we just wrote.
    let mut root = xmss::xmss_pk_from_sig::<P>(idx_leaf, &out[..xmss_sig_len], m, pk_seed, &mut adrs);

    let mut current_idx_tree = idx_tree;
    for j in 1..P::D {
        let current_idx_leaf = (current_idx_tree & ((1u64 << P::H_PRIME) - 1)) as u32;
        current_idx_tree >>= P::H_PRIME;

        adrs.set_layer_address(j as u32);
        adrs.set_tree_address(current_idx_tree);

        let slot_start = j * xmss_sig_len;
        let slot_end = slot_start + xmss_sig_len;
        {
            let slot = &mut out[slot_start..slot_end];
            xmss::xmss_sign_into::<P>(&root, sk_seed, current_idx_leaf, pk_seed, &mut adrs, slot);
        }

        if j < P::D - 1 {
            root = xmss::xmss_pk_from_sig::<P>(current_idx_leaf, &out[slot_start..slot_end], &root, pk_seed, &mut adrs);
        }
    }
}

/// Verify a hypertree signature.
///
/// Implements Algorithm 13 of FIPS 205. Recomputes the XMSS root at each of the `d`
/// layers, starting from the signed message `m` at layer 0 and propagating upward.
/// Returns `true` if the reconstructed top-layer root matches `pk_root`.
///
/// Each XMSS signature in `sig_ht` is `(len + h') * n` bytes; the full hypertree
/// signature contains `d` such signatures.
pub fn ht_verify<P: Params>(
    m: &[u8],
    sig_ht: &[u8],
    pk_seed: &[u8],
    idx_tree: u64,
    idx_leaf: u32,
    pk_root: &[u8],
) -> bool {
    let mut adrs = Adrs::new();
    adrs.set_tree_address(idx_tree);

    // Each XMSS signature is (len + h') * n bytes
    let xmss_sig_len = (P::LEN + P::H_PRIME) * P::N;

    // Verify layer 0
    adrs.set_layer_address(0);
    let sig_tmp = &sig_ht[..xmss_sig_len];
    let mut node = xmss::xmss_pk_from_sig::<P>(idx_leaf, sig_tmp, m, pk_seed, &mut adrs);

    // Verify remaining layers
    let mut current_idx_tree = idx_tree;
    for j in 1..P::D {
        let current_idx_leaf = (current_idx_tree & ((1u64 << P::H_PRIME) - 1)) as u32;
        current_idx_tree >>= P::H_PRIME;

        adrs.set_layer_address(j as u32);
        adrs.set_tree_address(current_idx_tree);

        let sig_tmp = &sig_ht[j * xmss_sig_len..(j + 1) * xmss_sig_len];
        node = xmss::xmss_pk_from_sig::<P>(current_idx_leaf, sig_tmp, &node, pk_seed, &mut adrs);
    }

    node == pk_root
}