///|
/// Generates a cryptographic key pair for the Dilithium post-quantum signature scheme.
///
/// This function implements the key generation algorithm from the NIST FIPS 204 standard.
/// It constructs a Module-LWE (MLWE) key pair where the public key is derived from
/// the secret key through matrix multiplication in the polynomial ring Z_q[X]/(X^N + 1).
///
/// # Algorithm Overview
///
/// The key generation follows the MLWE construction:
/// 1. Generate random seed ρ for matrix expansion and seed κ for secret key derivation
/// 2. Expand ρ into matrix A ∈ R_q^{k×l} using SHAKE128 (deterministic expansion)
/// 3. Sample secret vectors s1 ∈ R_q^l and s2 ∈ R_q^k with coefficients in {-η, ..., η}
/// 4. Compute public vector t = A·s1 + s2 (matrix-vector multiplication)
/// 5. Compress t into t1 (high bits) and t0 (low bits) using power-of-2 rounding
/// 6. Pack (ρ, t1) as public key and (ρ, tr, κ, t0, s1, s2) as secret key
///
/// # Security Construction
///
/// The security relies on the hardness of the Module Learning With Errors problem:
/// - Given (A, t), it's computationally hard to recover (s1, s2)
/// - The error term s2 provides the "learning with errors" hardness
/// - The rounding of t provides compression while maintaining security
///
/// # Parameters
///
/// * `seed` : Either:
///   - `Ok(seed_bytes)`: 32-byte seed for deterministic key generation (ρ = seed)
///   - `Err(rand)`: Random number generator for non-deterministic generation
///
/// # Returns
///
/// A tuple `(public_key, secret_key)` where:
/// - `public_key`: Packed (ρ, t1) - matrix seed + compressed public vector
/// - `secret_key`: Packed (ρ, tr, κ, t0, s1, s2) - complete key material
///
/// # Key Sizes by Security Level
///
/// | Level | Public Key | Secret Key | Security |
/// |-------|------------|------------|----------|
/// | 2     | 1312 bytes | 2528 bytes | 128-bit  |
/// | 3     | 1952 bytes | 4016 bytes | 192-bit  |
/// | 5     | 2592 bytes | 4864 bytes | 256-bit  |
pub fn keypair_gen(
  seed : Result[Array[Byte], Rand],
) -> (Array[Byte], Array[Byte]) {
  let init_seed : Array[Byte] = Array::make(SEEDBYTES, 0)
  let k = dilithium_context.get_params_set().k
  let l = dilithium_context.get_params_set().l
  let publickey_bytes = dilithium_context.get_params_set().publickey_bytes
  match seed {
    Ok(x) => {
      init_seed.clear()
      init_seed.append(x)
    }
    Err(rand) => {
      let x = randombytes(rand, SEEDBYTES)
      init_seed.clear()
      init_seed.append(x)
    }
  }
  let seedbuf : Array[Byte] = Array::make(2 * SEEDBYTES + CRHBYTES, 0)
  let tr : Array[Byte] = Array::make(SEEDBYTES, 0)
  let rho : Array[Byte] = Array::make(SEEDBYTES, 0)
  let rhoprime : Array[Byte] = Array::make(CRHBYTES, 0)
  let key : Array[Byte] = Array::make(SEEDBYTES, 0)
  let mat : Array[Polyvecl] = Array::new()
  let s1 : Polyvecl = Polyvecl::default()
  let s2 : Polyveck = Polyveck::default()
  let t1 : Polyveck = Polyveck::default()
  let t0 : Polyveck = Polyveck::default()
  for i in 0.. Array[Byte] {
  let k = dilithium_context.get_params_set().k
  let polyw1_packedbytes = dilithium_context.get_params_set().polyw1_packedbytes
  let gamma1 = dilithium_context.get_params_set().gamma1
  let gamma2 = dilithium_context.get_params_set().gamma2
  let beta = dilithium_context.get_params_set().beta
  let omega = dilithium_context.get_params_set().omega
  let sign_bytes = dilithium_context.get_params_set().sign_bytes
  // Step 1: Derive message digest
  // μ = H(tr || m) where tr = H(pk) is the public key commitment
  // This binds the signature to both the message and the public key
  let keymu : Array[Byte] = Array::make(SEEDBYTES + CRHBYTES, 0)
  let mat : Array[Polyvecl] = Array::new()
  let y : Polyvecl = Polyvecl::default()
  let w1 : Polyveck = Polyveck::default()
  let w0 : Polyveck = Polyveck::default()
  let h = Polyveck::default()
  let cp = Poly::default()
  let state = KeccakState::default()
  let rhoprime : Array[Byte] = Array::make(CRHBYTES, 0)
  let (rho, key, tr, t0, s1, s2) = unpack_sk(sk)
  for i in 0.. 0 {
      continue
    }

    // Check that subtracting cs2 does not change high bits of w and low bits
    // do not reveal secret information 
    Polyveck::pointwise_poly_montgomery(h, cp, s2)
    h.invntt_tomont()
    w0.sub(h)
    w0.reduce()
    if w0.chknorm(gamma2 - beta) > 0 {
      continue
    }

    // Compute hints for w1
    Polyveck::pointwise_poly_montgomery(h, cp, t0)
    h.invntt_tomont()
    h.reduce()
    if h.chknorm(gamma2) > 0 {
      continue
    }
    w0.add(h)
    let n = Polyveck::make_hint(h, w0, w1)
    if n > omega {
      continue
    }
    // Write signature
    let _ = pack_sig(sig, None, z, h)
    return sig
  }
  panic() // unreachable
}

///|
/// Verifies a Dilithium signature using the Fiat-Shamir verification equation.
///
/// This function implements the verification counterpart to the `sign` function,
/// checking whether a signature σ = (c, z, h) is valid for message m under public key pk = (ρ, t1).
/// It completes the signature lifecycle started by `keypair_gen` and `sign`.
///
/// # Relationship to Key Generation and Signing
///
/// This verification function validates signatures created by the `sign` function using
/// public keys generated by `keypair_gen`. The verification process reconstructs the
/// cryptographic proof that the signer knew the secret key corresponding to the public key.
///
/// # Verification Equation
///
/// The verifier checks the Fiat-Shamir equation: c = H(μ || w1) where:
/// - μ = H(H(ρ, t1) || m) - message digest (same computation as in `sign`)
/// - w1 = HighBits(A·z - c·t1) - reconstructed commitment using signature components
/// - HighBits() extracts high-order bits after rounding (inverse of `sign`'s decomposition)
///
/// # Algorithm Steps
///
/// 1. Parse signature: σ = (c, z, h) and public key: pk = (ρ, t1) (inverse of `pack_sig`)
/// 2. Verify signature format and component bounds (security check)
/// 3. Compute μ = H(H(ρ, t1) || m) - same message digest as used in `sign`
/// 4. Expand ρ into matrix A ∈ R_q^{k×l} using SHAKE128 (same expansion as `keypair_gen`)
/// 5. Reconstruct w1 = HighBits(A·z - c·t1) using hints h (inverse of `sign`'s hint generation)
/// 6. Compute c' = H(μ || w1) - expected challenge (same computation as in `sign`)
/// 7. Verify c = c' - signature validity (final check)
///
/// # Security Properties
///
/// The verification ensures the signature proves knowledge of the secret key without revealing it:
/// - Signature components are within valid ranges (prevents forgery)
/// - Response vector z has bounded coefficients (prevents key recovery)
/// - Reconstructed commitment matches expected value (proves secret key knowledge)
/// - No forgery attempts succeed (maintains unforgeability)
///
/// # Parameters
///
/// * `sig` : Byte array containing signature σ = (c, z, h) from `sign`
/// * `m` : Byte array containing the original message that was signed
/// * `pk` : Byte array containing public key pk = (ρ, t1) from `keypair_gen`
///
/// # Returns
///
/// - `Ok(())`: Signature is valid - verification equation holds, proving the signer knew the secret key
/// - `Err(SignError)`: Signature is invalid - specific failure reason indicating potential forgery or corruption
///
/// # Verification Failures
///
/// Common failure modes indicate security violations:
/// - Invalid signature format (wrong length or encoding) - malformed signature
/// - Response vector z has coefficients outside bounds - potential key recovery attack
/// - Reconstructed commitment doesn't match challenge - signature forgery attempt
/// - Signature components don't satisfy norm constraints - malformed signature
pub fn verify(
  sig : Array[Byte],
  m : Array[Byte],
  pk : Array[Byte],
) -> Result[Unit, SignError] {
  let sign_bytes = dilithium_context.get_params_set().sign_bytes
  let beta = dilithium_context.get_params_set().beta
  let gamma1 = dilithium_context.get_params_set().gamma1
  let k = dilithium_context.get_params_set().k
  let polyw1_packedbytes = dilithium_context.get_params_set().polyw1_packedbytes
  let publickey_bytes = dilithium_context.get_params_set().publickey_bytes
  let buf : Array[Byte] = Array::make(k * polyw1_packedbytes, 0)
  let mu : Array[Byte] = Array::make(CRHBYTES, 0)
  let mut c : Array[Byte] = Array::make(SEEDBYTES, 0)
  let c2 : Array[Byte] = Array::make(SEEDBYTES, 0)
  let cp = Poly::default()
  let mat : Array[Polyvecl] = Array::new()
  let mut z = Polyvecl::default()
  let w1 = Polyveck::default()
  let mut h = Polyveck::default()
  let state = KeccakState::default() // shake256_init()
  if sig.length() != sign_bytes {
    return Err(SignError("Wrong signature length"))
  }
  for i in 0.. return Err(e)
    Ok((sig_z, sig_h, sig_c)) => {
      c = sig_c
      z = sig_z
      h = sig_h
    }
  }
  if z.chknorm(gamma1 - beta) > 0 {
    return Err(SignError("Invalid signature"))
  }

  // Compute CRH(CRH(rho, t1), msg)
  shake256(
    output=mu,
    SEEDBYTES.reinterpret_as_uint(),
    input=pk,
    publickey_bytes.reinterpret_as_uint(),
  )
  shake256_absorb(state, mu, SEEDBYTES.reinterpret_as_uint())
  shake256_absorb(state, m, m.length().reinterpret_as_uint())
  shake256_finalize(state)
  shake256_squeeze(mu, CRHBYTES.reinterpret_as_uint(), state)

  // Matrix-vector multiplication; compute Az - c2^dt1
  cp.challenge(c)
  Polyvecl::matrix_expand(mat, rho)
  z.ntt()
  polyvec_matrix_pointwise_montgomery(w1, mat, z)
  cp.ntt()
  t1.shiftl()
  t1.ntt()
  let t1_2 = t1.copy()
  Polyveck::pointwise_poly_montgomery(t1, cp, t1_2)
  w1.sub(t1)
  w1.reduce()
  w1.invntt_tomont()

  // Reconstruct w1
  w1.caddq()
  w1.use_hint(h)
  w1.pack_w1(buf)

  // Call random oracle and verify challenge
  state.init()
  shake256_absorb(state, mu, CRHBYTES.reinterpret_as_uint())
  shake256_absorb(state, buf, (k * polyw1_packedbytes).reinterpret_as_uint())
  shake256_finalize(state)
  shake256_squeeze(c2, SEEDBYTES.reinterpret_as_uint(), state)
  // Doesn't require constant time equality check
  if c != c2 {
    Err(SignError("verify failed"))
  } else {
    Ok(())
  }
}