Paper 2026/537

On Phase Decompositions with Applications to Digit Decomposition

Leonard Schild, KU Leuven
Aysajan Abidin, KU Leuven
Bart Preneel, KU Leuven
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.