Welcome to the resource topic for 2024/1353
Title:
On the overflow and p-adic theory applied to homomorphic encryption
Authors: Jacob Blindenbach, Jung Hee Cheon, Gamze Gürsoy, Jiayi Kang
Abstract:When integer and rational arithmetics are performed using modular arithmetics over \mathbb{Z}/q\mathbb{Z}, overflows naturally occur due to the mismatch between the infinite cardinality of \mathbb{Z} or \mathbb{Q} and the finite cardinality of \mathbb{Z}/q\mathbb{Z}. Since \mathbb{Z}/q\mathbb{Z} is also the (sub) message space for many secure computation designs, secure computations of integer and rational arithmetics using these schemes must also consider the overflow problem.
Previous works [CLPX, CT-RSA’18] and [HDRdS, ACNS’23] perform integer and rational arithmetics using the CLPX homomorphic encryption scheme, where overflows are avoided by restricting supported circuits. This introduces an additional constraint beyond the noise budget limitation. In our work, we discuss the possibilities of tolerating overflows. Firstly, we explain that when input messages and the final result are well-bounded, intermediate values can go arbitrarily large without affecting output correctness. This kind of overflow is called pseudo-overflow and does not need to be avoided. Secondly, we note that for prime-power modulus q=p^r, overflow errors are small in the p-adic norm. Therefore, we apply the p-adic encoding technique in [HDRdS, ACNS’23] to the BGV/BFV homomorphic encryption scheme with plaintext modulus p^r.
Compared to [CLPX, CT-RSA’18] and [HDRdS, ACNS’23], our method supports circuits that are up to 2 \times deeper under the same ciphertext parameters, at the cost of an output error bounded by p^{-r} in the p-adic norm.
ePrint: https://eprint.iacr.org/2024/1353
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 .