Paper 2026/537
On Phase Decompositions with Applications to Digit Decomposition
Abstract
Fully homomorphic encryption schemes enable arbitrary computation on encrypted data. Although the first candidate were considered too computationally inefficient, modern cryptosystems are now featured in practical deployments. Yet, despite a plethora of advances, many non-polynomial operations remain computationally challenging. In this work, we investigate radix decomposition, i.e., the homomorphic conversion of an LWE ciphertext with a large plaintext message into encryptions of its digits. Such decompositions are a core building block for large-precision computation in FHEW/TFHE-like schemes, for instance for sign evaluation, comparisons, and large lookup tables. To this end, we introduce phase decomposition: decomposing the coefficients of an LWE ciphertext itself in a radix $\alpha$ yields small pseudo-LWE samples whose phases recombine linearly to the phase of the original ciphertext. For keys of bounded Hamming weight, these phases are small and can be made non-negative, and the base-$\alpha$ digits of the original phase follow from them through a simple carry recurrence. We evaluate this recurrence entirely in the exponent of an RLWE accumulator, using a new exact homomorphic truncation in the exponent based on automorphisms. The resulting digit decomposition requires a single blind rotation per digit, asymptotically half as many as the state of the art, introduces no modulus-switching error between iterations, and supports input moduli larger than the ring modulus. The same tools yield functional bootstrapping over the full ring $\mathbb{Z}_{2N}$, the evaluation of arbitrary, not necessarily negacyclic, functions on small plaintext spaces, and a scheme-independent digit decomposition for SIMD schemes based on parallel-prefix addition.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Fully Homomorphic EncryptionHomomorphic Digit DecompositionProgrammable BootstrappingFunctional Bootstrapping
- Contact author(s)
-
leonard schild @ esat kuleuven be
aysajan @ kuleuven be
bart preneel @ esat kuleuven be - History
- 2026-10-25: revised
- 2026-03-17: received
- See all versions
- Short URL
- https://ia.cr/2026/537
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/537,
author = {Leonard Schild and Aysajan Abidin and Bart Preneel},
title = {On Phase Decompositions with Applications to Digit Decomposition},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/537},
year = {2026},
url = {https://eprint.iacr.org/2026/537}
}