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 \(\textsf {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\text {-adic}\) norm. Therefore, we apply the \(p\text {-adic}\) encoding technique in [HDRdS, ACNS’23] to the \(\textsf {BGV}\) / \(\textsf {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\text {-adic}\) norm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Overflow and p-adic Theory Applied to Homomorphic Encryption

  • Jacob Blindenbach,
  • Jung Hee Cheon,
  • Gamze Gürsoy,
  • Jiayi Kang

摘要

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 \(\textsf {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\text {-adic}\) norm. Therefore, we apply the \(p\text {-adic}\) encoding technique in [HDRdS, ACNS’23] to the \(\textsf {BGV}\) / \(\textsf {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\text {-adic}\) norm.