Homomorphic operations

PVAC-HFHE supports homomorphic addition, subtraction, and multiplication, allowing computation on encrypted data without decryption.

Overview

Homomorphic operations preserve the algebraic structure:

Enc(a) ⊕ Enc(b) = Enc(a + b)
Enc(a) ⊗ Enc(b) = Enc(a × b)

The server can compute on ciphertexts without knowing the plaintext values or secret key.

All operations are exact (no approximation errors) and work over the 127-bit prime field F_p.

Addition

Addition is extremely fast: simply concatenate the layer graphs and edge lists.

Cipher ct_add(const PubKey& pk, const Cipher& A, const Cipher& B);

From include/pvac/ops/arithmetic.hpp:165-188:

Cipher ct_add(const PubKey& pk, const Cipher& A, const Cipher& B) {
    Cipher C;
    C.slots = A.slots;
    
    // Add constant terms
    C.c0 = A.c0.empty() ? B.c0 
         : B.c0.empty() ? A.c0 
         : field::Op::add(A.c0, B.c0);
    
    C.L.reserve(A.L.size() + B.L.size());
    C.E.reserve(A.E.size() + B.E.size());
    
    // Copy A's layers
    C.L = A.L;
    uint32_t off = (uint32_t)A.L.size();
    
    // Copy B's layers with offset indices
    std::transform(B.L.begin(), B.L.end(), 
                   std::back_inserter(C.L),
        [off](Layer L) {
            if (L.rule == RRule::PROD) { 
                L.pa += off; 
                L.pb += off; 
            }
            return L;
        });
    
    // Copy edges
    C.E = A.E;
    std::transform(B.E.begin(), B.E.end(), 
                   std::back_inserter(C.E),
        [off](Edge e) { 
            e.layer_id += off; 
            return e; 
        });
    
    guard_budget(pk, C, "add");
    compact_layers(C);
    return C;
}

Why addition is fast

Addition doesn’t create new layers or multiply edges. It just:

Merges layer lists (adjusting PROD layer parent indices)
Concatenates edge lists (adjusting layer IDs)
Adds constant terms

Performance:

Time: 0.012 ms (12 microseconds)
Ciphertext growth: None (just concatenation)
Noise growth: Linear

Addition is 10-87× faster than RLWE schemes (BFV/BGV/CKKS) because it requires no polynomial operations.

Example

Cipher a = enc_value(pk, sk, 42);
Cipher b = enc_value(pk, sk, 17);

Cipher sum = ct_add(pk, a, b);
// dec_value(pk, sk, sum) == 59

Subtraction

Subtraction is addition with negation:

Cipher ct_sub(const PubKey& pk, const Cipher& A, const Cipher& B) {
    return ct_add(pk, A, ct_neg(pk, B));
}

Negation scales all edge weights and constants by -1:

Cipher ct_neg(const PubKey& pk, const Cipher& A) {
    return ct_scale(pk, A, fp_neg(fp_from_u64(1)));
}

Cipher ct_scale(const PubKey&, const Cipher& A, const Fp& s) {
    Cipher C = A;
    for (auto& e : C.E)
        e.w = field::Op::mul(e.w, s);
    for (size_t j = 0; j < C.c0.size(); ++j)
        C.c0[j] = fp_mul(C.c0[j], s);
    return C;
}

From include/pvac/ops/arithmetic.hpp:152-163. Performance: Same as addition (~0.012 ms).

Multiplication

Multiplication creates new PROD layers representing cross-products of parent layers.

Cipher ct_mul(const PubKey& pk, const Cipher& A, const Cipher& B, 
              size_t S = 8);

The parameter S controls the number of edges per product layer (default: 8). From include/pvac/ops/arithmetic.hpp:194-225:

Cipher ct_mul(const PubKey& pk, const Cipher& A, const Cipher& B, 
              size_t S = 8) {
    auto a0 = A.c0;  // Constant term from A
    auto b0 = B.c0;  // Constant term from B
    
    // Strip constant terms
    Cipher A_g = A;
    Cipher B_g = B;
    A_g.c0 = field::Op::zeros(A.slots);
    B_g.c0 = field::Op::zeros(B.slots);
    
    uint32_t LA = (uint32_t)A_g.L.size();
    uint32_t LB = (uint32_t)B_g.L.size();
    uint32_t off = LA;
    
    // Create PROD layers for all pairs (la, lb)
    Cipher C = detail::build_product_cipher(pk, A_g, &B_g,
        [LA, LB](auto&& emit) {
            for (uint32_t la = 0; la < LA; ++la)
                for (uint32_t lb = 0; lb < LB; ++lb)
                    emit(la, lb);
        },
        [](const auto& gA, const auto& gB, uint32_t la, uint32_t lb) {
            return field::Op::mul(gA[la], gB[lb]);
        },
        (size_t)LA * LB, S ? S : 1, "mul");
    
    // Add cross terms: a0 * B_g and b0 * A_g
    detail::append_scaled_edges(C.E, B_g.E, a0, off);
    detail::append_scaled_edges(C.E, A_g.E, b0, 0);
    
    // Constant term
    C.c0 = field::Op::mul(a0, b0);
    
    guard_budget(pk, C, "mul");
    compact_layers(C);
    return C;
}

Multiplication algorithm

Given A = a0 + g_A and B = b0 + g_B where a0, b0 are constants and g_A, g_B are graph parts:

A × B = (a0 + g_A) × (b0 + g_B)
      = a0*b0 + a0*g_B + b0*g_A + g_A*g_B

Steps:

Product layers: For each pair (la, lb) where la ∈ layers(A) and lb ∈ layers(B), create a PROD layer:

Layer make_prod_layer(const PubKey& pk, uint32_t pa, uint32_t pb) {
    auto nonce = make_nonce128();
    return {RRule::PROD, 
            {prg_layer_ztag(pk.canon_tag, nonce), nonce},
            pa < pb ? pa : pb, 
            pa < pb ? pb : pa};
}

From include/pvac/ops/arithmetic.hpp:90-94.

Repack edges: For each PROD layer, create S new edges that encode the product value:

auto emit_repack_edges(const PubKey& pk, uint32_t lid, 
                       const Layer& L,
                       const std::vector<Fp>& target, 
                       size_t s) -> std::vector<Edge>

Choose s-1 random edges, then solve for the last edge’s weight to match the target sum. From include/pvac/ops/arithmetic.hpp:55-88.

Add cross terms: Scale B’s edges by a0 and A’s edges by b0.
Compute constant: c0 = a0 * b0.

Why multiplication is more expensive

Layer growth: |L_C| = |L_A| + |L_B| + |L_A| × |L_B|
Edge growth: New edges for each product layer
Compaction: May trigger edge merging if budget exceeded

Performance:

Time: 2.47 ms
vs BFV: 2.9× faster (shallow), 7.4× faster (leveled)
vs CKKS: 14.3× faster

From benchmarks/README.md:42-50, PVAC-HFHE multiplication is significantly faster than RLWE schemes for scalar operations.

Example

Cipher a = enc_value(pk, sk, 6);
Cipher b = enc_value(pk, sk, 7);

Cipher prod = ct_mul(pk, a, b);
// dec_value(pk, sk, prod) == 42

std::cout << "Layers: " << prod.L.size() << "\n";
std::cout << "Edges: " << prod.E.size() << "\n";

Squaring

Squaring is optimized compared to generic multiplication:

Cipher ct_square(const PubKey& pk, const Cipher& A, size_t S = 8);

From include/pvac/ops/arithmetic.hpp:227-255:

Cipher ct_square(const PubKey& pk, const Cipher& A, size_t S = 8) {
    auto a0 = A.c0;
    
    Cipher A_g = A;
    A_g.c0 = field::Op::zeros(A.slots);
    
    uint32_t LA = (uint32_t)A_g.L.size();
    size_t triangular = (size_t)LA * (LA + 1) / 2;
    
    // Only create PROD layers for (la, lb) where la ≤ lb
    Cipher C = detail::build_product_cipher(pk, A_g, nullptr,
        [LA](auto&& emit) {
            for (uint32_t la = 0; la < LA; ++la)
                for (uint32_t lb = la; lb < LA; ++lb)
                    emit(la, lb);
        },
        [](const auto& gA, const auto&, uint32_t la, uint32_t lb) {
            auto prod = field::Op::mul(gA[la], gA[lb]);
            // Double off-diagonal terms
            return la != lb ? field::Op::add(prod, prod) : prod;
        },
        triangular, S ? S : 1, "square");
    
    auto two_a0 = field::Op::add(a0, a0);
    detail::append_scaled_edges(C.E, A_g.E, two_a0, 0);
    C.c0 = field::Op::mul(a0, a0);
    
    guard_budget(pk, C, "square");
    compact_layers(C);
    return C;
}

Optimization: Only creates LA*(LA+1)/2 PROD layers instead of LA², exploiting symmetry.

Constant operations

Operations with public constants are much faster:

Addition with constant

Cipher ct_add_const(const PubKey&, const Cipher& A, uint64_t k) {
    Cipher C = A;
    Fp v = fp_from_u64(k);
    for (size_t j = 0; j < C.c0.size(); ++j)
        C.c0[j] = fp_add(C.c0[j], v);
    return C;
}

From include/pvac/ops/arithmetic.hpp:269-275. Free operation: Only updates constant term, no layer/edge changes.

Multiplication by constant

Cipher ct_mul_const(const PubKey& pk, const Cipher& A, uint64_t k) {
    return ct_scale(pk, A, fp_from_u64(k));
}

From include/pvac/ops/arithmetic.hpp:261-263. Fast operation: Scales all edge weights, no new layers.

Division by constant

Cipher ct_div_const(const PubKey& pk, const Cipher& A, const Fp& k) {
    return ct_scale(pk, A, fp_inv(k));
}

From include/pvac/ops/arithmetic.hpp:257-259. Requires field inversion of the constant.

Depth and noise growth

Multiplicative depth

The depth of a ciphertext is the longest path of multiplications from fresh encryptions:

Fresh encryption: depth 0
Addition/subtraction: max(depth(A), depth(B))
Multiplication: depth(A) + depth(B) + 1

Noise budget

Noise grows with depth:

struct Budget {
    static Budget compute(const Params& p, int d) {
        double cap = p.noise_entropy_bits 
                   + p.depth_slope_bits * std::max(0, d);
        // ...
    }
};

Default parameters:

Base: 120 bits
Growth: 16 bits per depth
At depth 5: 120 + 16*5 = 200 bits

When noise budget is exhausted, decryption will fail. The PoC supports depth up to ~5 before ciphertext size becomes impractical.

Performance comparison

From benchmarks/README.md:42-72:

Scalar multiplication

Scheme	Time (ms)	vs PVAC-HFHE
PVAC-HFHE	2.47	1.0×
BFV (shallow)	7.23	2.9× slower
BFV (leveled)	18.28	7.4× slower
BGV	17.61	7.1× slower
CKKS	35.23	14.3× slower

Scalar addition

Scheme	Time (ms)	vs PVAC-HFHE
PVAC-HFHE	0.012	1.0×
BFV	0.124	10× slower
BGV	0.552	46× slower
CKKS	1.050	87× slower

PVAC-HFHE excels at shallow circuits (depth 1-2) with scalar operations, significantly outperforming RLWE schemes.

Ciphertext management

Edge budget

When ciphertext edges exceed the budget (default: 1,200,000), automatic compaction triggers:

void guard_budget(const PubKey& pk, Cipher& C, const char* ctx) {
    if (C.E.size() > pk.prm.edge_budget) {
        compact_edges(pk, C);
    }
}

Compaction

Merges edges pointing to the same (layer, index, sign):

void compact_edges(const PubKey& pk, Cipher& C) {
    C.E = reduction::merge(
        alg::Carrier<Edge>{ std::move(C.E) }, pk).unwrap();
}

From include/pvac/ops/encrypt.hpp:658-660. Also removes unused layers:

void compact_layers(Cipher& C);

Code examples

Polynomial evaluation

// Compute f(x) = 3x³ + 2x² + 5x + 7
Cipher eval_poly(const PubKey& pk, const Cipher& x) {
    Cipher x2 = ct_square(pk, x);           // x²
    Cipher x3 = ct_mul(pk, x2, x);          // x³
    
    Cipher term3 = ct_mul_const(pk, x3, 3); // 3x³
    Cipher term2 = ct_mul_const(pk, x2, 2); // 2x²
    Cipher term1 = ct_mul_const(pk, x, 5);  // 5x
    
    Cipher sum = ct_add(pk, term3, term2);
    sum = ct_add(pk, sum, term1);
    sum = ct_add_const(pk, sum, 7);
    
    return sum;
}

Dot product

// Compute ⟨a, b⟩ = a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]
Cipher dot_product(const PubKey& pk, 
                   const std::vector<Cipher>& a,
                   const std::vector<Cipher>& b) {
    assert(a.size() == b.size());
    
    std::vector<Cipher> prods;
    for (size_t i = 0; i < a.size(); ++i) {
        prods.push_back(ct_mul(pk, a[i], b[i]));
    }
    
    Cipher sum = prods[0];
    for (size_t i = 1; i < prods.size(); ++i) {
        sum = ct_add(pk, sum, prods[i]);
    }
    
    return sum;
}

Get Started

Core Concepts

Guides

Examples

Homomorphic operations

Overview

Addition

Why addition is fast

Example

Subtraction

Multiplication

Multiplication algorithm

Why multiplication is more expensive

Example

Squaring

Constant operations

Addition with constant

Multiplication by constant

Division by constant

Depth and noise growth

Multiplicative depth

Noise budget

Performance comparison

Scalar multiplication

Scalar addition

Ciphertext management

Edge budget

Compaction

Code examples

Polynomial evaluation

Dot product

Next steps

Security

API reference

Build docs developers (and LLMs) love

Get Started

Core Concepts

Guides

Examples

Documentation Index

​Overview

​Addition

​Why addition is fast

​Example

​Subtraction

​Multiplication

​Multiplication algorithm

​Why multiplication is more expensive

​Example

​Squaring

​Constant operations

​Addition with constant

​Multiplication by constant

​Division by constant

​Depth and noise growth

​Multiplicative depth

​Noise budget

​Performance comparison

​Scalar multiplication

​Scalar addition

​Ciphertext management

​Edge budget

​Compaction

​Code examples

​Polynomial evaluation

​Dot product

​Next steps

Security

API reference

Build docs developers (and LLMs) love

Overview

Addition

Why addition is fast

Example

Subtraction

Multiplication

Multiplication algorithm

Why multiplication is more expensive

Example

Squaring

Constant operations

Addition with constant

Multiplication by constant

Division by constant

Depth and noise growth

Multiplicative depth

Noise budget

Performance comparison

Scalar multiplication

Scalar addition

Ciphertext management

Edge budget

Compaction

Code examples

Polynomial evaluation

Dot product

Next steps