Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/octra-labs/pvac_hfhe_cpp/llms.txt

Use this file to discover all available pages before exploring further.

​
Overview

This module provides the BitVec structure for efficient storage and manipulation of binary vectors. BitVec is used extensively in LPN-based encryption and noise generation.

​
Structure

​
BitVec

Compact representation of a binary vector using packed 64-bit words. 
struct BitVec {
    size_t nbits;
    std::vector<uint64_t> w;
};
​
nbits
size_t
Number of bits in the vector
​
w
std::vector<uint64_t>
Storage array where each uint64_t holds 64 bits
Bits are packed into 64-bit words for efficient storage and operations. A vector of n bits uses ceil(n/64) words.

​
Construction

​
make

Creates a new BitVec initialized to all zeros. 
static BitVec make(size_t n);
​
n
size_t
Number of bits in the vector
​
return
BitVec
New BitVec with n bits, all initialized to 0
Example: 
// Create a 1024-bit vector
BitVec vec = BitVec::make(1024);

// Create a vector matching parameter size
BitVec h_row = BitVec::make(params.n_bits);

​
Operations

​
xor_with

Performs in-place XOR with another BitVec. 
void xor_with(const BitVec& b);
​
b
const BitVec&
Vector to XOR with
Example: 
BitVec a = BitVec::make(128);
BitVec b = BitVec::make(128);

// Set some bits in a and b...

// Compute a ^= b
a.xor_with(b);
If the vectors have different sizes, only the overlapping portion (minimum size) is affected.

​
popcnt

Counts the number of 1-bits in the vector (Hamming weight). 
size_t popcnt() const;
​
return
size_t
Number of bits set to 1
Example: 
BitVec vec = BitVec::make(1024);
// ... set some bits ...

size_t weight = vec.popcnt();
std::cout << "Hamming weight: " << weight << std::endl;
Uses the compiler’s __builtin_popcountll intrinsic for efficient population count on 64-bit words.

​
Utility functions

​
parity64

Computes the parity (XOR of all bits) of a 64-bit word in constant time. 
int parity64(uint64_t x);
​
x
uint64_t
Input word
​
return
int
0 if an even number of bits are set, 1 if odd
Example: 
uint64_t word = 0b1011; // 3 bits set (odd)
int p = parity64(word); // p = 1

word = 0b1001; // 2 bits set (even)
p = parity64(word); // p = 0
This function uses constant-time XOR shifts to compute parity, making it suitable for cryptographic applications where timing side-channels must be avoided.

​
Implementation details

​
Bit packing

Bits are stored in little-endian order within each 64-bit word:
  • Bit 0 is the LSB of w[0]
  • Bit 63 is the MSB of w[0]
  • Bit 64 is the LSB of w[1]
  • And so on…
Example: 
BitVec vec = BitVec::make(128);
// vec.w has size 2 (128 bits / 64 bits per word)

// To set bit 65:
vec.w[1] |= (1ULL << 1);

// To test bit 65:
bool is_set = (vec.w[1] & (1ULL << 1)) != 0;

​
Memory layout

For a BitVec with nbits bits:
  • Number of words: (nbits + 63) / 64
  • Memory usage: 8 * ((nbits + 63) / 64) bytes (plus overhead)
Example: 
BitVec vec = BitVec::make(1000);
// Uses ceil(1000/64) = 16 words
// Memory: 16 * 8 = 128 bytes

​
Usage patterns

​
LPN secret vector

// Create secret vector
BitVec s = BitVec::make(params.n_bits);

// Generate random bits with specific Hamming weight
for (int i = 0; i < params.err_wt; i++) {
    size_t pos = random_position();
    s.w[pos / 64] |= (1ULL << (pos % 64));
}

// Verify weight
assert(s.popcnt() == params.err_wt);

​
Combining vectors

BitVec result = BitVec::make(n);

for (const auto& vec : input_vectors) {
    result.xor_with(vec);
}

// result now contains the XOR of all input vectors

​
Computing inner product

int inner_product_mod2(const BitVec& a, const BitVec& b) {
    int result = 0;
    size_t nwords = std::min(a.w.size(), b.w.size());
    
    for (size_t i = 0; i < nwords; i++) {
        result ^= parity64(a.w[i] & b.w[i]);
    }
    
    return result;
}

​
Performance considerations

Optimization tips:
  • BitVec operations work on 64-bit words, providing 64x speedup over bit-by-bit operations
  • XOR operations are memory-bandwidth limited; keep vectors aligned
  • Population count (popcnt) uses hardware instructions on modern CPUs
  • Parity computation is constant-time for security

​
Constant-time operations

The parity64 function is implemented in constant time to prevent timing side-channels: 
x ^= x >> 32;  // 32-bit fold
x ^= x >> 16;  // 16-bit fold
x ^= x >> 8;   // 8-bit fold
x ^= x >> 4;   // 4-bit fold
x &= 0xF;      // Keep lower 4 bits
return (0x6996 >> x) & 1;  // Lookup table for 4 bits
This approach ensures the execution time is independent of the input value.

Build docs developers (and LLMs) love

Get started for freeTalk to us