Stream-BSGS

Memory-efficient tree-BSGS polynomial evaluation for RLWE-based FHE (BFV / BGV / CKKS), with noise-aware lazy-relinearization scheduling. This repository is the artifact for:

Stream-BSGS: Memory-Efficient Tree-BSGS with Optimized Relinearization Scheduling for FHE Polynomial Evaluation. Zhongqi Wang, Shintaro Narisada, Takashi Nishide. Selected Areas in Cryptography (SAC) 2026, to appear.

Everything runs on stock OpenFHE — no library fork. The building blocks:

• Single-step partial relinearization of K-polynomial ciphertexts, implemented in user space via GetScheme()->RelinearizeInPlace() with a custom evaluation-key subset (uses SetMaxRelinSkDeg).
• The level-wise scheduling policy H(k*) with r = 1 (Algorithm 1).
• Stream-BSGS: leaf generation and tree reduction fused into a single streaming pass through a stack-based fold (Algorithms 2–3), reducing the peak working set from b + s + log2(s) to b + 2·log2(s) + 2 live ciphertexts.
• PS and standard tree-BSGS baselines for all three schemes.

Repository layout

Path	Contents	Paper
src/ps_{bfv,bgv,ckks}.cpp	Paterson–Stockmeyer baseline	§5.2, Table 5
src/tree_bsgs_{bfv,bgv,ckks}.cpp	Standard tree-BSGS, full relinearization at every level (H(0))	§5.3, Tables 6–7
src/stream_bsgs_{bfv,bgv,ckks}.cpp	--mode original = tree-BSGS + H(k*) partial relin; --mode streaming = Stream-BSGS; --bHalved = reduced-baby-step variant	§5.2–5.3, Figs. 1–2
src/chebyshev_scheduling_partial.cpp	H(k) sweep with r = 1 on the CKKS Chebyshev tree-combination stage (bootstrapping-scale parameters)	§5.1, Tables 3–4
src/chebyshev_scheduling_full.cpp	Same sweep with full relinearization (r = k); exhibits the second-level barrier	§5.1, Table 3
microbench/	Marginal-cost (α = Δrelin/Δmul) and key-switching-noise probes	§3
tests/partial_relin_test_ckks.cpp	Correctness tests for the partial-relin building blocks	—
scripts/	Reproduction scripts	§5

Requirements

• Linux (the RSS sampler reads /proc/self/status)
• C++17 compiler, CMake ≥ 3.16
• OpenFHE; the paper's results were obtained with v1.2.3

Build

# 1) install OpenFHE v1.2.3
git clone --branch v1.2.3 https://github.com/openfheorg/openfhe-development.git
cmake -S openfhe-development -B openfhe-development/build
cmake --build openfhe-development/build -j
sudo cmake --install openfhe-development/build

# 2) build this repository
cmake -S . -B build
cmake --build build -j

Quick correctness check

./build/stream_bsgs_bfv  --logDeg 8 --mode both
./build/stream_bsgs_bgv  --logDeg 8 --mode both
./build/stream_bsgs_ckks --logDeg 8 --mode both
./build/partial_relin_test_ckks

--mode both runs phase-separated tree-BSGS and Stream-BSGS in one process, verifies each result against a plaintext-domain evaluation of the same random polynomial, and cross-checks that the two algorithms decrypt to the same value.

Reproducing the paper's experiments

Experiment	Script	Parameters (binary defaults)
§5.1 scheduling validation (Tables 3–4)	scripts/run_scheduling.sh	CKKS, N = 65536, depth 20, Δ = 2^59, first 60
§5.2 end-to-end (Table 5 / Fig. 1)	scripts/run_end_to_end.sh	N = 32768, depth 17, t = 65537, CKKS Δ = 2^50, first 60
§5.3 ablation (Tables 6–7 / Fig. 2)	scripts/run_ablation.sh	same as §5.2

Set REPS=5 to match the paper's five-run averaging. Every run appends a CSV row (phase times, relinearization counts, maximum polynomial count observed, correctness bit). Setting STREAM_BSGS_RSS_LOG=<file> additionally samples VmRSS/VmPeak from /proc/self/status every 100 ms.

Common command-line options

--logDeg D evaluates a random polynomial of degree 2^D − 1. All binaries also take --depth, --N, and --csv; BFV/BGV binaries take --ptmod (--t for the streaming ones) and CKKS binaries take --scalModSize / --firstModSize. The stream_bsgs_* binaries additionally take --mode original|streaming|both, --switchLevel k, --streamSwitch k, --maxPoly K, --bHalved (and --deepMatch for BGV). The chebyshev_scheduling_* binaries take --logS and --switchLevel. --switchLevel defaults to maxPoly − 2, the deepest level supported by the generated key material; the noise-feasible optimum k* of the paper is found by the trial-evaluation procedure of §3.4.

Citation

@inproceedings{WangNarisadaNishide2026StreamBSGS,
  author    = {Zhongqi Wang and Shintaro Narisada and Takashi Nishide},
  title     = {{Stream-BSGS}: Memory-Efficient Tree-{BSGS} with Optimized
               Relinearization Scheduling for {FHE} Polynomial Evaluation},
  booktitle = {Selected Areas in Cryptography (SAC 2026)},
  publisher = {Springer},
  year      = {2026},
  note      = {To appear}
}

License and acknowledgments

BSD 2-Clause (see LICENSE). This work was supported in part by JSPS KAKENHI Grant Number 25K03116 and JST SPRING Grant Number JPMJSP2124.