Welcome to the resource topic for 2024/417
Title:
An improved exact CRR basis conversion algorithm for FHE without floating-point arithmetic
Authors: Hongyuan Qu, Guangwu Xu
Abstract:Fully homomorphic encryption (FHE) has attracted much attention recently. Chinese remainder representation (CRR) or RNS representation is one of the core technologies of FHE. CRR basis conversion is a key step of KeySwitching procedure. Bajard et al. proposed a fast basis conversion method for CRR basis conversion, but the elimination of error had to be ignored. Halevi et al. suggested a method using floating-point arithmetic to avoid errors, but floating-point arithmetic has its own issues such as low efficiency and complex chip design. In this work, we establish a more concise and efficient CRR basis conversion method by observing that each of the ciphertext modulus selected
by the CRR CKKS scheme is very close to an integer that is a power of 2. Our conversion algorithm eliminates errors and involves only integer arithmetic and bit operations. The proof of correctness of our algorithm is given. Extensive experiments are conducted and comparisons between the method of Halevi et al. and ours are obtained, which show that our method has the same accuracy and a slightly better effeciency. Our method is also applicable to the CRR variant of BGV and BFV schemes, and can be used to simplify chip design.
ePrint: https://eprint.iacr.org/2024/417
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .