Paper 2024/1353
On the overflow and $p$adic theory applied to homomorphic encryption
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, CTRSA'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 wellbounded, intermediate values can go arbitrarily large without affecting output correctness. This kind of overflow is called pseudooverflow and does not need to be avoided. Secondly, we note that for primepower 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, CTRSA'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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. Short paper. CSCML24
 Keywords
 OverflowHomomorphic encryption$p$adic theory
 Contact author(s)

jb4816 @ columbia edu
jhcheon @ snu ac kr
gg2845 @ cumc columbia edu
jiayi kang @ esat kuleuven be  History
 20240830: approved
 20240828: received
 See all versions
 Short URL
 https://ia.cr/2024/1353
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1353, author = {Jacob Blindenbach and Jung Hee Cheon and Gamze Gürsoy and Jiayi Kang}, title = {On the overflow and $p$adic theory applied to homomorphic encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1353}, year = {2024}, url = {https://eprint.iacr.org/2024/1353} }