Security

PVAC-HFHE’s security is based on the hardness of the Learning Parity with Noise (LPN) problem, a well-studied cryptographic assumption.

Learning Parity with Noise (LPN)

Problem definition

Given:

A random binary matrix A ∈ ^(t × n)
A secret binary vector s ∈ ^n
Noise rate τ ∈ (0, 1/2)
Samples y = As + e (mod 2) where each bit of e is 1 with probability τ

Problem: Recover the secret s from (A, y).

LPN is the binary variant of Learning With Errors (LWE). It’s considered quantum-resistant and has been studied extensively since the 1990s.

LPN in PVAC-HFHE

The scheme uses LPN with the following parameters (from include/pvac/core/types.hpp:58-61):

int lpn_n = 4096;      // Secret dimension
int lpn_t = 16384;     // Number of samples
int lpn_tau_num = 1;   // Noise rate numerator
int lpn_tau_den = 8;   // Noise rate denominator

Noise rate: τ = 1/8 = 0.125

Security analysis

From the source code comments (include/pvac/core/types.hpp:53-56):

// sec (tau = 1/8):
// info theor bound: 2226 bits
// classical: 200+ bits  
// quantum: 100+ bits

Security levels:

Information-theoretic bound: 2226 bits
Classical security: 200+ bits (exceeds 128-bit target)
Quantum security: 100+ bits (exceeds NIST PQC requirements)

The scheme provides 128-bit security against both classical and quantum adversaries when using the default parameters.

PRF construction

LPN-based PRF

The scheme derives pseudorandom field elements using LPN:

Fp prf_R(const PubKey& pk, const SecKey& sk, const RSeed& seed);

From include/pvac/crypto/lpn.hpp:263-268:

Fp prf_R(const PubKey& pk, const SecKey& sk, const RSeed& seed) {
    Fp r1 = prf_R_core(pk, sk, seed, Dom::PRF_R1);
    Fp r2 = prf_R_core(pk, sk, seed, Dom::PRF_R2);
    Fp r3 = prf_R_core(pk, sk, seed, Dom::PRF_R3);
    return fp_mul(fp_mul(r1, r2), r3);
}

Triple-product construction: Uses three independent LPN samples multiplied together for enhanced security.

PRF core algorithm

From include/pvac/crypto/lpn.hpp:235-261:

Fp prf_R_core(const PubKey& pk, const SecKey& sk, 
              const RSeed& seed, const char* dom) {
    // 1. Generate LPN samples y = As + e
    std::vector<uint64_t> ybits;
    lpn_make_ybits(pk, sk, seed, dom, ybits);
    
    // 2. Derive Toeplitz matrix seed
    uint8_t toep_key[32];
    uint64_t toep_nonce;
    derive_aes_key(pk, sk, seed, Dom::TOEP, toep_key, toep_nonce);
    toep_nonce ^= fnv1a_domain(dom);
    
    // 3. Generate random Toeplitz matrix
    AesCtr256 prg;
    prg.init(toep_key, toep_nonce);
    size_t top_words = (pk.prm.lpn_t + 127 + 63) / 64;
    std::vector<uint64_t> top(top_words);
    prg.fill_u64(top.data(), top_words);
    
    // 4. Apply Toeplitz hash to extract randomness
    uint64_t lo = 0;
    uint64_t hi = 0;
    toep_127(top, ybits, lo, hi);
    
    // 5. Map to nonzero field element
    return hash_to_fp_nonzero(lo, hi);
}

Steps:

Generate lpn_t = 16384 LPN samples using AES-CTR mode
Derive Toeplitz matrix randomness (domain-separated)
Apply Toeplitz hashing to extract 127 bits
Map to a nonzero field element

LPN sample generation

From include/pvac/crypto/lpn.hpp:194-233:

void lpn_make_ybits(const PubKey& pk, const SecKey& sk,
                    const RSeed& seed, const char* dom,
                    std::vector<uint64_t>& ybits) {
    int t = pk.prm.lpn_t;  // 16384
    int n = pk.prm.lpn_n;  // 4096
    size_t s_words = (n + 63) / 64;
    
    // Derive AES key from secret key + seed + domain
    uint8_t aes_key[32];
    uint64_t nonce;
    derive_aes_key(pk, sk, seed, dom, aes_key, nonce);
    
    // Initialize AES-CTR PRG
    AesCtr256 prg;
    prg.init(aes_key, nonce);
    
    ybits.assign((t + 63) / 64, 0ull);
    
    int num = pk.prm.lpn_tau_num;  // 1
    int den = pk.prm.lpn_tau_den;  // 8
    
    std::vector<uint64_t> row_buf(s_words);
    
    for (int r = 0; r < t; r++) {
        // Generate random row of A
        prg.fill_u64(row_buf.data(), s_words);
        
        // Compute dot product: A[r] · s (mod 2)
        uint64_t acc = 0;
        for (size_t wi = 0; wi < s_words; ++wi) {
            acc ^= row_buf[wi] & sk.lpn_s_bits[wi];
        }
        int dot = parity64(acc);
        
        // Add noise with probability τ = 1/8
        int e = (prg.bounded((uint64_t)den) < (uint64_t)num) ? 1 : 0;
        int y = dot ^ e;
        
        ybits[r >> 6] ^= ((uint64_t)y) << (r & 63);
    }
}

Security note: Uses AES-CTR with hardware AES-NI for cryptographically secure randomness.

Domain separation

The scheme uses domain separation to ensure different PRF calls are independent: From include/pvac/core/types.hpp:14-31:

namespace Dom {
    inline constexpr const char* H_GEN = "pvac.dom.h_gen";
    inline constexpr const char* X_SEED = "pvac.dom.x_seed";
    inline constexpr const char* NOISE = "pvac.dom.noise";
    
    inline constexpr const char* PRF_LPN = "pvac.dom.prf_lpn";
    inline constexpr const char* TOEP = "pvac.dom.toeplitz";
    
    inline constexpr const char* ZTAG = "pvac.dom.ztag";
    inline constexpr const char* COMMIT = "pvac.dom.commit";
    
    inline constexpr const char* PRF_R1 = "pvac.prf.r.1";
    inline constexpr const char* PRF_R2 = "pvac.prf.r.2";
    inline constexpr const char* PRF_R3 = "pvac.prf.r.3";
    
    inline constexpr const char* PRF_NOISE1 = "pvac.prf.noise.1";
    inline constexpr const char* PRF_NOISE2 = "pvac.prf.noise.2";
    inline constexpr const char* PRF_NOISE3 = "pvac.prf.noise.3";
}

Domain separation prevents attacks where an adversary tries to correlate outputs from different PRF calls.

Hypergraph matrix H

The public key includes a random binary matrix H of size m_bits × n_bits: Parameters (from include/pvac/core/types.hpp:42-45):

int m_bits = 8192;     // Syndrome dimension (rows)
int n_bits = 16384;    // Column count
int h_col_wt = 192;    // Column weight (Hamming weight)
int x_col_wt = 128;    // Preimage vector sparsity
int err_wt = 128;      // Error weight

Matrix structure:

Dimensions: 8192 × 16384 bits (16 MB dense, or ~200 KB sparse representation)
Column weight: Each column has exactly 192 ones
Random generation: Using cryptographically secure PRG

Syndrome computation

Each edge has a syndrome vector:

s = H · x (mod 2)

where:

s ∈ ^8192 is the syndrome (stored in ciphertext)
x ∈ ^16384 has Hamming weight 128 (kept secret)
H is the public matrix

Security: Without the secret key, finding x from s requires solving a syndrome decoding problem, which is NP-hard.

The hypergraph matrix H is stored in the public key (~8 MB). This is a trade-off for fast encryption/decryption.

Key generation security

From include/pvac/crypto/keygen.hpp:35-136:

Secret key generation

// 1. Generate 256-bit PRF key
for (int i = 0; i < 4; i++) {
    sk.prf_k[i] = csprng_u64();
}

// 2. Generate random binary vector (LPN secret)
size_t s_words = (pk.prm.lpn_n + 63) / 64;  // 64 words
sk.lpn_s_bits.resize(s_words);

for (size_t i = 0; i < s_words; i++) {
    sk.lpn_s_bits[i] = csprng_u64();
}

Secret key size: 256 + 4096 = 4352 bits (544 bytes)

Multiplicative group generator

The scheme finds a generator g of the subgroup of order B = 337:

u128 pm1 = (((u128)1) << 127) - 2;  // p - 1
u128 E = pm1 / (u128)pk.prm.B;      // Exponent

for (;;) {
    Fp h = rand_fp();  // Random element
    Fp g = fp_pow_u64(h, (uint64_t)E);  // g = h^E
    
    // Check g is a generator (g ≠ 1)
    if (!ct::fp_is_one(g)) {
        break;
    }
}

Security check: Verifies that B | (p-1), ensuring the subgroup exists.

Root of unity

Finds a primitive B-th root of unity ω_B:

auto primes = factor_small(pk.prm.B);  // [337]

for (;;) {
    Fp h = rand_fp();
    Fp w = fp_pow_u64(h, (uint64_t)(pm1 / (u128)pk.prm.B));
    
    if (ct::fp_is_one(w)) {
        continue;  // Order too small
    }
    
    bool ok = true;
    for (int p : primes) {
        Fp t = fp_pow_u64(w, (uint64_t)(pk.prm.B / p));
        if (ct::fp_is_one(t)) {
            ok = false;  // Subgroup order is not primitive
            break;
        }
    }
    
    if (ok) {
        pk.omega_B = w;
        break;
    }
}

The root of unity enables efficient polynomial operations and is used in advanced features like recryption.

Constant-time operations

To prevent timing side-channels, key operations are constant-time:

Constant-time field inversion

From include/pvac/core/field.hpp:229-269, the fp_inv_ct function uses windowed exponentiation with:

Fixed-time table lookups
No data-dependent branches
Constant number of field multiplications

Constant-time equality test

bool fp_is_one(const Fp& a) {
    uint64_t z = (a.lo ^ 1) | a.hi;
    return ((z | -z) >> 63) ^ 1;
}

From include/pvac/core/ct_safe.hpp (implied). No branches: Uses bitwise operations only.

Security assumptions

Primary assumption

LPN Hardness: Given (A, y = As + e) with noise rate τ = 1/8, it is computationally infeasible to recover s in time less than 2^128.

Supporting assumptions

AES-256 in CTR mode is a secure PRG
SHA-256 is collision-resistant (for key derivation)
Random oracle model for Toeplitz hashing

Known attacks

Best known attacks on LPN(n=4096, t=16384, τ=1/8):

Attack	Complexity	Reference
BKW algorithm	~2^200 classical	Blum-Kalai-Wasserman
Pooled Gauss	~2^180 classical	Levieil-Fouque
Quantum BKW	~2^100 quantum	Quantum speedup

All known attacks exceed the 128-bit security target by a significant margin.

Threat model

Honest-but-curious server

The server:

Can: Perform homomorphic operations on ciphertexts
Cannot: Decrypt ciphertexts without the secret key
Cannot: Learn anything about plaintexts beyond what’s leaked by operation patterns

What is NOT protected

PVAC-HFHE does not provide:

Circuit privacy: The server can see the computation graph structure
Access pattern hiding: The server knows which operations are performed
Ciphertext indistinguishability: Different plaintexts may yield different ciphertext sizes

Side-channel resistance

The implementation includes:

Constant-time field inversion
Constant-time comparisons
No secret-dependent memory accesses in critical paths

However:

Timing variations may leak information about ciphertext sizes
Cache timing attacks are not fully mitigated
Power analysis countermeasures are not implemented

For production use, additional hardening against side-channels would be required.

Security best practices

Key management

// ✓ Good: Generate fresh keys for each application
Params prm;
PubKey pk;
SecKey sk;
keygen(prm, pk, sk);

// ✗ Bad: Reuse keys across different security domains

Seed generation

// ✓ Good: Use cryptographically secure RNG
Nonce128 nonce = make_nonce128();  // Uses csprng_u64()

// ✗ Bad: Use predictable seeds
Nonce128 bad_nonce = {0, 0};  // NEVER do this!

Parameter selection

// ✓ Good: Use default parameters for 128-bit security
Params prm;  // Defaults are secure

// ✗ Bad: Reduce parameters without security analysis
Params weak_prm;
weak_prm.lpn_n = 1024;  // Too small! Insecure!

Comparison with other assumptions

Assumption	PVAC-HFHE	RLWE (BFV/BGV/CKKS)	TFHE
Base problem	LPN	Ring-LWE	LWE
Quantum security	✓	✓	✓
Maturity	Moderate (30+ years)	High (15+ years)	Moderate (10+ years)
Standardization	None	NIST (Kyber)	None
Best attacks	2^200+ classical	2^150+ classical	2^128+ classical

LPN is closely related to LWE but over binary fields. It’s considered quantum-resistant and has been studied extensively in coding theory and cryptography.

Get Started

Core Concepts

Guides

Examples

Learning Parity with Noise (LPN)

Problem definition

LPN in PVAC-HFHE

Security analysis

PRF construction

LPN-based PRF

PRF core algorithm

LPN sample generation

Domain separation

Hypergraph matrix H

Syndrome computation

Key generation security

Secret key generation

Multiplicative group generator

Root of unity

Constant-time operations

Constant-time field inversion

Constant-time equality test

Security assumptions

Primary assumption

Supporting assumptions

Known attacks

Threat model

Honest-but-curious server

What is NOT protected

Side-channel resistance

Security best practices

Key management

Seed generation

Parameter selection

Comparison with other assumptions

Next steps

Getting started

API reference

Build docs developers (and LLMs) love

Get Started

Core Concepts

Guides

Examples

Documentation Index

​Learning Parity with Noise (LPN)

​Problem definition

​LPN in PVAC-HFHE

​Security analysis

​PRF construction

​LPN-based PRF

​PRF core algorithm

​LPN sample generation

​Domain separation

​Hypergraph matrix H

​Syndrome computation

​Key generation security

​Secret key generation

​Multiplicative group generator

​Root of unity

​Constant-time operations

​Constant-time field inversion

​Constant-time equality test

​Security assumptions

​Primary assumption

​Supporting assumptions

​Known attacks

​Threat model

​Honest-but-curious server

​What is NOT protected

​Side-channel resistance

​Security best practices

​Key management

​Seed generation

​Parameter selection

​Comparison with other assumptions

​Next steps

Getting started

API reference

Build docs developers (and LLMs) love

Learning Parity with Noise (LPN)

Problem definition

LPN in PVAC-HFHE

Security analysis

PRF construction

LPN-based PRF

PRF core algorithm

LPN sample generation

Domain separation

Hypergraph matrix H

Syndrome computation

Key generation security

Secret key generation

Multiplicative group generator

Root of unity

Constant-time operations

Constant-time field inversion

Constant-time equality test

Security assumptions

Primary assumption

Supporting assumptions

Known attacks

Threat model

Honest-but-curious server

What is NOT protected

Side-channel resistance

Security best practices

Key management

Seed generation

Parameter selection

Comparison with other assumptions

Next steps