Matrix operations

The matrix module provides functions for generating and manipulating sparse parity check matrices and permutations used in PVAC-HFHE.

Matrix generation

gen_H()

Generates the sparse parity check matrix H for the public key.

void gen_H(PubKey& pk)

PubKey&

Public key containing parameters and canon_tag. The matrix H is written to pk.H and its digest to pk.H_digest.

Algorithm

For each column c = 0 to n_bits - 1:

Generate deterministic seed from (m_bits, n_bits, h_col_wt, c, canon_tag)
Use prg_choose_k() to select h_col_wt unique row indices in [0, m_bits)
Set those positions to 1 in the column bit vector

The resulting matrix H is n × m with each column having exactly h_col_wt ones.

Digest computation

After generation, a SHA-256 digest is computed over:

Domain separator "H|v2"
Matrix dimensions: m_bits, n_bits, h_col_wt
All column bit vectors in row-major order

The digest is stored in pk.H_digest for verification.

The matrix H is deterministic from canon_tag, allowing efficient verification without transmitting the full matrix.

gen_ubk_public()

Generates the public permutation (UBK) from a canonical tag.

Ubk gen_ubk_public(uint64_t canon_tag, int m_bits)

canon_tag

uint64_t

Random tag identifying the key (from pk.canon_tag)

m_bits

int

Dimension of the permutation (typically 8192)

return

Ubk

Structure containing both the permutation and its inverse

Algorithm

Uses the Fisher-Yates shuffle:

Initialize perm = [0, 1, 2, ..., m_bits-1]
Derive pseudorandom stream from canon_tag using SHA-256 with domain separator "UBK"
For i = m_bits-1 down to 1:
- Generate uniform random j in [0, i]
- Swap perm[i] and perm[j]
Compute inverse permutation: inv[perm[i]] = i

The resulting Ubk structure contains:

perm: forward permutation
inv: inverse permutation for decryption

prg_choose_k()

Selects k unique indices uniformly at random from [0, N).

std::vector<int> prg_choose_k(
    int k,
    int N,
    const char* label,
    const std::vector<uint64_t>& words
)

int

Number of indices to select

int

Size of the range [0, N)

label

const char*

Domain separator string (e.g., Dom::H_GEN, Dom::X_SEED)

words

const std::vector<uint64_t>&

Seed words for deterministic randomness

return

std::vector<int>

Vector of k unique indices in [0, N)

Sampling algorithm

Hash initialization: Creates PRG from SHA-256 of (label, words, counter)
Bounded sampling: Uses rejection sampling to avoid modulo bias
Uniqueness: Maintains hash set to ensure no duplicates
Uniform distribution: Each valid subset has equal probability

The function guarantees:

All indices are unique
All indices are in range [0, N)
Distribution is cryptographically uniform

This function requires k ≤ N. If k > N, it will loop indefinitely.

Permutation operations

apply_perm_sigma()

Applies an inverse permutation to a bit vector.

BitVec apply_perm_sigma(const BitVec& v, const std::vector<int>& inv)

const BitVec&

Input bit vector

inv

const std::vector<int>&

Inverse permutation (from Ubk::inv)

return

BitVec

Permuted bit vector where output[inv[i]] = input[i]

Iterates through set bits in the input vector and sets the corresponding bit in the output at the permuted position.

ubk_apply()

Applies the UBK inverse permutation to all edges in a ciphertext.

void ubk_apply(const PubKey& pk, Cipher& C)

const PubKey&

Public key containing the UBK permutation

Cipher&

Ciphertext whose edge syndrome vectors will be permuted

This function modifies the ciphertext in-place, applying pk.ubk.inv to the s vector of each edge.

Syndrome generation

sigma_from_H()

Generates a syndrome vector for an encryption edge.

BitVec sigma_from_H(
    const PubKey& pk,
    uint64_t ztag,
    Nonce128 nonce,
    uint16_t idx,
    uint8_t ch,
    uint64_t salt
)

const PubKey&

Public key containing matrix H and parameters

ztag

uint64_t

Layer tag (from RSeed::ztag)

nonce

Nonce128

128-bit nonce (from RSeed::nonce)

idx

uint16_t

Edge index

uint8_t

Channel/sign (0 for positive, 1 for negative)

salt

uint64_t

Additional entropy (typically 0)

return

BitVec

Syndrome vector of length m_bits

Algorithm

Select columns: Use prg_choose_k() to select x_col_wt columns from H
XOR columns: Compute s = H[c1] ⊕ H[c2] ⊕ ... ⊕ H[c_{x_col_wt}]
Add noise: Use prg_choose_k() to flip err_wt random bits in s

The seed for randomness includes all function parameters, ensuring each edge gets a unique syndrome.

prg_layer_ztag()

Computes the layer ztag from canon_tag and nonce.

uint64_t prg_layer_ztag(uint64_t canon_tag, Nonce128 n)

canon_tag

uint64_t

Public key canonical tag

Nonce128

128-bit layer nonce

return

uint64_t

64-bit layer tag derived via SHA-256

Hashes domain separator Dom::ZTAG with canon_tag and the nonce to produce a unique layer identifier.

Matrix properties

Sparse parity check matrix H

Dimensions: n_bits × m_bits (default: 16384 × 8192)
Column weight: Each column has exactly h_col_wt ones (default: 192)
Row weight: Variable, approximately n * h_col_wt / m ≈ 384 per row
Storage: Each column stored as a BitVec (compressed)

Syndrome properties

Each syndrome vector from sigma_from_H():

Results from XORing x_col_wt columns (default: 128)
Has approximately x_col_wt * h_col_wt / 2 ones (ignoring cancellations)
Includes err_wt additional noise bits (default: 128)
Is computationally hard to decode without the secret key

The syndrome decoding problem is related to the syndrome decoding problem for LDPC codes, which is NP-hard.

Example usage

#include <pvac/crypto/matrix.hpp>

using namespace pvac;

PubKey pk;
pk.prm = Params(); // default parameters
pk.canon_tag = csprng_u64();

// Generate parity check matrix
gen_H(pk);

// Generate public permutation
pk.ubk = gen_ubk_public(pk.canon_tag, pk.prm.m_bits);

// H and ubk are now ready for encryption

// Generate syndrome for an edge
uint64_t ztag = prg_layer_ztag(pk.canon_tag, make_nonce128());
BitVec sigma = sigma_from_H(pk, ztag, make_nonce128(), 0, 0, 0);

// Apply permutation
BitVec permuted = apply_perm_sigma(sigma, pk.ubk.inv);

Performance notes

gen_H(): Generates 16384 columns, takes ~10-50ms depending on hardware
gen_ubk_public(): Generates 8192-element permutation, takes less than 1ms
sigma_from_H(): Generates one syndrome, takes ~0.1ms
apply_perm_sigma(): Applies permutation to sparse vector, takes ~0.01ms

All operations are deterministic from their inputs and can be parallelized.

keygen() - Calls gen_H() and gen_ubk_public() during key generation
prg_choose_k() - Used internally for sparse sampling

Core

Cryptography

Operations

Utilities

Matrix generation

gen_H()

Algorithm

Digest computation

gen_ubk_public()

Algorithm

prg_choose_k()

Sampling algorithm

Permutation operations

apply_perm_sigma()

ubk_apply()

Syndrome generation

sigma_from_H()

Algorithm

prg_layer_ztag()

Matrix properties

Sparse parity check matrix H

Syndrome properties

Example usage

Performance notes

Build docs developers (and LLMs) love

Core

Cryptography

Operations

Utilities

Documentation Index

​Matrix generation

​gen_H()

​Algorithm

​Digest computation

​gen_ubk_public()

​Algorithm

​prg_choose_k()

​Sampling algorithm

​Permutation operations

​apply_perm_sigma()

​ubk_apply()

​Syndrome generation

​sigma_from_H()

​Algorithm

​prg_layer_ztag()

​Matrix properties

​Sparse parity check matrix H

​Syndrome properties

​Example usage

​Performance notes

​Related functions

Build docs developers (and LLMs) love

Matrix generation

gen_H()

Algorithm

Digest computation

gen_ubk_public()

Algorithm

prg_choose_k()

Sampling algorithm

Permutation operations

apply_perm_sigma()

ubk_apply()

Syndrome generation

sigma_from_H()

Algorithm

prg_layer_ztag()

Matrix properties

Sparse parity check matrix H

Syndrome properties

Example usage

Performance notes

Related functions