Preprint
BHDR: BSGS-Hoisted Diagonal Regression for Non-Interactive Single-Server Kernel SHAP under CKKS
Abstract
This technical report introduces BHDR (BSGS-Hoisted Diagonal Regression), a non-interactive single-server construction for computing Kernel SHAP explanations under CKKS fully homomorphic encryption for a deployed logistic-regression path.
The Kernel SHAP sampling matrix, kernel weights, and regression matrix are public build-time artefacts. This lets the server evaluate coalition outputs under encryption and perform weighted least-squares regression as a public encrypted matrix-vector product. BHDR uses a BSGS-hoisted diagonal matvec over a periodic CKKS slot encoding, reducing encrypted regression rotations from approximately 2,200 to 51 at d = 50.
The report provides an end-to-end UCI Adult implementation, benchmark results, an error-decomposition certificate for deployed releases, an analytical Matrix Bernstein baseline, and a circuit-depth feasibility study for tree ensembles.
Citation
@misc{alissaei2026bhdr,
author = {Bader Alissaei},
title = {BHDR: BSGS-Hoisted Diagonal Regression for Non-Interactive Single-Server Kernel SHAP under CKKS},
year = {2026},
publisher = {Zenodo},
doi = {10.5281/zenodo.19889993},
url = {https://doi.org/10.5281/zenodo.19889993}
}The PDF is available directly at /papers/bhdr.pdf without login, scripts, or an embedded viewer.