Paper 2026/2892

Phase-Hiding Programmable Bootstrapping with Online Client Assistance

Xingke Chai, School of Mathematics and Statistics, Heilongjiang University
Abstract

Programmable bootstrapping in Fast Fully Homomorphic Encryption over the Torus (TFHE) uses a bootstrapping key (BSK) to control successive external products during blind rotation, incurring computational cost and introducing and propagating error. We introduce Phase-Hiding Programmable Bootstrapping (PH-PBS), in which the key-holding client precomputes single-use phase tokens encrypting randomly shifted monomials and assists refresh online. Through phase sharing and a small garbled circuit, the parties compute a masked rotation correction that lets the server align a token for lookup, replacing BSK-driven blind rotation. Using the aligned monomial, the server evaluates private lookup tables, retains ciphertexts for further computation, and delivers only prescribed terminal plaintexts to the client. To reduce token preparation and transmission costs, we construct a projection independent of table values that, under matched randomness and quantization, produces the same complete learning-with-errors (LWE) output ciphertext as the full quantized-token path, coefficientwise. We analyze error propagation in both fixed key-switching orders and derive numerical failure-probability bounds for finite sequential tasks with fixed public schedules and shared key-switching material, under the specified finite-precision model and conditional on successful initialization. Under the stated cryptographic assumptions, we simulate each party's complete session view in the classical static semi-honest model and bound the distinguishing advantage. On a four-bit workload where PH-PBS and the TFHE-rs baseline both use 32-bit coefficients in their key-switching keys and matched decomposition parameters, mean local refresh time with pre-core key switching decreases from 18.392 ms to 3.713 ms, a 79.8% reduction, including both parties' computation and consumed-token preparation. Separate measurements with pre-core key switching place PH-PBS's normalized core-output error variance at approximately one three-thousandth of the corresponding baseline variance. Across the examined modes and network scenarios, estimated refresh-stage times are 46.3%–80.1% lower than those of the corresponding TFHE-rs baselines; these estimates assume serial computation and communication, completed initialization, and sufficient initial correlated oblivious-transfer material.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Programmable bootstrappingTFHEClient-assisted computationPrivate lookup tablesKey switchingError analysis
Contact author(s)
xingkechai @ gmail com
History
2026-11-18: approved
2026-11-14: received
See all versions
Short URL
https://ia.cr/2026/2892
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2892,
      author = {Xingke Chai},
      title = {Phase-Hiding Programmable Bootstrapping with Online Client Assistance},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2892},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2892}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.