# HQC Vector Operations Documentation
## Overview
This document provides comprehensive documentation of all vector operations in the HQC implementation, ensuring maintainability and audit readiness. All operations are designed to match the reference implementation exactly while maintaining constant-time execution for security.
## Core Vector Operations
### 1. `vect_write_support_to_vector`
**Purpose**: Writes a support set (array of bit positions) to a vector using constant-time operations.
**Implementation Details**:
```rust
pub fn vect_write_support_to_vector(&self, v: &mut [u64], support: &[u32], weight: usize) {
// Precompute index_tab and bit_tab like reference
let mut index_tab = vec![0u32; weight];
let mut bit_tab = vec![0u64; weight];
for i in 0..weight {
index_tab[i] = support[i] >> 6; // Word index (divide by 64)
let pos = support[i] & 0x3f; // Bit position within word (mod 64)
bit_tab[i] = 1u64 << pos; // Bit mask
}
// Constant-time vector write (matches reference exactly)
for i in 0..v.len() {
let mut val = 0u64;
for j in 0..weight {
let tmp = i.wrapping_sub(index_tab[j] as usize);
// Constant-time check if tmp == 0
let val1 = 1u32 ^ ((tmp as u32 | tmp.wrapping_neg() as u32) >> 31);
let mask = (-(val1 as i64)) as u64;
val |= bit_tab[j] & mask;
}
v[i] |= val; // Use |= to accumulate (critical for correctness)
}
}
```
**Key Features**:
- **Constant-time execution**: Prevents timing attacks
- **Accumulation semantics**: Uses `|=` to accumulate bits, not replace
- **Reference compatibility**: Matches reference implementation exactly
- **Bit position calculation**: `index = pos >> 6`, `bit = pos & 0x3f`
**Security Considerations**:
- All operations are constant-time to prevent side-channel attacks
- No conditional branches based on secret data
- Uses bitwise operations for all comparisons
### 2. `vect_sample_fixed_weight1`
**Purpose**: Samples a random vector with exactly `weight` non-zero bits.
**Implementation Details**:
```rust
pub fn vect_sample_fixed_weight1(
&self,
xof: &mut Shake256Xof,
output: &mut [u64],
weight: usize,
) -> Result<(), HqcPkeError> {
// Clear output first (critical for correctness)
for item in &mut *output {
*item = 0;
}
let mut support = vec![0u32; weight];
self.vect_generate_random_support1(xof, &mut support, weight)?;
self.vect_write_support_to_vector(output, &support, weight);
Ok(())
}
```
**Key Features**:
- **Deterministic sampling**: Uses XOF for reproducible randomness
- **Fixed weight guarantee**: Exactly `weight` bits will be set
- **Vector initialization**: Clears output before writing support
### 3. `vect_generate_random_support1`
**Purpose**: Generates a random support set of distinct indices using rejection sampling.
**Implementation Details**:
```rust
pub fn vect_generate_random_support1(
&self,
xof: &mut Shake256Xof,
support: &mut [u32],
weight: usize,
) -> Result<(), HqcPkeError> {
let random_bytes_size = 3 * weight;
let mut rand_bytes = vec![0u8; random_bytes_size];
let mut i = 0;
let mut j = random_bytes_size;
while i < weight {
loop {
if j == random_bytes_size {
xof.squeeze(&mut rand_bytes)
.map_err(|_| HqcPkeError::HashError)?;
j = 0;
}
// Construct 24-bit value from 3 bytes (big-endian)
support[i] = ((rand_bytes[j] as u32) << 16) |
((rand_bytes[j + 1] as u32) << 8) |
(rand_bytes[j + 2] as u32);
j += 3;
// Rejection sampling
if support[i] < P::UTILS_REJECTION_THRESHOLD {
break;
}
}
// Barrett reduction modulo PARAM_N
support[i] = self.barrett_reduce(support[i]);
// Constant-time duplicate check
let mut inc = 1;
for k in 0..i {
if support[k] == support[i] {
inc = 0;
}
}
i += inc;
}
Ok(())
}
```
**Key Features**:
- **Rejection sampling**: Ensures uniform distribution
- **Duplicate prevention**: Constant-time duplicate checking
- **Barrett reduction**: Efficient modular reduction
- **24-bit values**: Uses 3 bytes per support position
### 4. `barrett_reduce`
**Purpose**: Performs Barrett reduction modulo PARAM_N with constant-time execution.
**Implementation Details**:
```rust
pub fn barrett_reduce(&self, x: u32) -> u32 {
let q = ((x as u64) * P::N_MU) >> 32;
let mut r = x - (q * P::N as u64) as u32;
// Constant-time final reduction (matches reference exactly)
let reduce_flag = ((r.wrapping_sub(P::N as u32)) >> 31) ^ 1;
let mask = (-(reduce_flag as i32)) as u32;
r -= mask & (P::N as u32);
r
}
```
**Key Features**:
- **Constant-time execution**: No conditional branches
- **Reference compatibility**: Matches reference implementation exactly
- **Efficient reduction**: Uses precomputed N_MU for fast division
### 5. `vect_mul` (Polynomial Multiplication)
**Purpose**: Performs polynomial multiplication in GF(2)[x]/(x^n - 1).
**Implementation Details**:
```rust
fn vect_mul(&self, output: &mut [u64], a: &[u64], b: &[u64]) -> Result<(), HqcPkeError> {
let mut unreduced = vec![0u64; 2 * P::VEC_N_SIZE_64];
// Schoolbook multiplication into unreduced buffer (matching reference exactly)
for (i, &ai) in a.iter().enumerate().take(P::VEC_N_SIZE_64) {
for bit in 0..64 {
let mask = if (ai >> bit) & 1 == 1 { !0u64 } else { 0u64 };
let base = i;
let sh = bit;
let inv = 64 - sh;
if sh == 0 {
for j in 0..P::VEC_N_SIZE_64 {
unreduced[base + j] ^= b[j] & mask;
}
} else {
for j in 0..P::VEC_N_SIZE_64 {
unreduced[base + j] ^= (b[j] << sh) & mask;
unreduced[base + j + 1] ^= (b[j] >> inv) & mask;
}
}
}
}
// Reduce modulo x^n - 1 (matching reference exactly)
for i in 0..P::VEC_N_SIZE_64 {
let r = unreduced[i + P::VEC_N_SIZE_64 - 1] >> (P::N & 0x3F);
let carry = unreduced[i + P::VEC_N_SIZE_64] << (64 - (P::N & 0x3F));
output[i] = unreduced[i] ^ r ^ carry;
}
// Mask excess bits in the last word (using BITMASK equivalent)
output[P::VEC_N_SIZE_64 - 1] &= (1u64 << (P::N & 0x3F)) - 1;
Ok(())
}
```
**Key Features**:
- **Schoolbook multiplication**: Matches reference algorithm exactly
- **Modular reduction**: Reduces modulo x^n - 1
- **Bit masking**: Masks excess bits in final word
- **No bounds checking**: Matches reference behavior exactly
### 6. `vect_add`
**Purpose**: Performs vector addition in GF(2) (XOR).
**Implementation Details**:
```rust
fn vect_add(
&self,
output: &mut [u64],
a: &[u64],
b: &[u64],
len: usize,
) -> Result<(), HqcPkeError> {
for i in 0..len {
if i < output.len() && i < a.len() && i < b.len() {
output[i] = a[i] ^ b[i];
}
}
Ok(())
}
```
**Key Features**:
- **Simple XOR operation**: Element-wise XOR of vectors
- **Bounds checking**: Prevents buffer overflows
- **GF(2) arithmetic**: Addition in binary field
## Parameter Specifications
### HQC-1 Parameters
- **PARAM_N**: 17669 (polynomial degree)
- **PARAM_OMEGA**: 66 (weight of error vectors)
- **PARAM_OMEGA_R**: 75 (rejection sampling threshold)
- **VEC_N_SIZE_64**: 277 (number of 64-bit words)
- **UTILS_REJECTION_THRESHOLD**: 2^24 - 1 (rejection sampling threshold)
### Bit Manipulation Constants
- **Word size**: 64 bits
- **Index calculation**: `index = position >> 6`
- **Bit calculation**: `bit = position & 0x3f`
- **Bit mask**: `mask = 1u64 << bit`
## Security Considerations
### Constant-Time Operations
All vector operations are designed to execute in constant time to prevent timing attacks:
1. **No conditional branches** based on secret data
2. **Bitwise operations** for all comparisons
3. **Masking operations** instead of if-statements
4. **Uniform execution paths** regardless of input values
### Memory Safety
- **Bounds checking** in all operations
- **Buffer overflow prevention**
- **Proper initialization** of all vectors
- **Zeroization** of sensitive data when appropriate
## Testing and Validation
### Unit Tests
- **Vector write operations**: Test bit setting at various positions
- **Support generation**: Verify uniform distribution and no duplicates
- **Polynomial multiplication**: Test with known inputs
- **Barrett reduction**: Test modular arithmetic
### Integration Tests
- **End-to-end key generation**: Verify complete workflow
- **KAT compliance**: Match official test vectors
- **Cross-platform compatibility**: Test on different architectures
## Maintenance Guidelines
### Code Modifications
1. **Preserve constant-time properties** in all modifications
2. **Maintain reference compatibility** for correctness
3. **Add comprehensive tests** for any new functionality
4. **Document security implications** of changes
### Performance Optimization
1. **Profile before optimizing** to identify bottlenecks
2. **Maintain security properties** during optimization
3. **Benchmark against reference** implementation
4. **Consider Karatsuba multiplication** for performance gains
### Audit Preparation
1. **Document all design decisions** and rationale
2. **Maintain test coverage** above 95%
3. **Keep security analysis** up to date
4. **Prepare for third-party review**
## References
- [HQC Official Specification](https://pqc-hqc.org/)
- Upstream HQC reference C implementation (obtain from the HQC submission / project sources)
- [NIST Post-Quantum Cryptography Standards](https://csrc.nist.gov/projects/post-quantum-cryptography)
- [Constant-Time Programming](https://www.bearssl.org/constanttime.html)
---
**Last Updated**: December 2024
**Next Review**: Q2 2025
**Maintainer**: libQ Development Team