[Bug]: The critical condition judgment is wrong about spu HOT 5 CLOSED

@maths644311798

Nice catch. The Backward encoding is pretty old and already not used by other cheetah's code. And yes that is a bug.

The sign flip here is ok. You can consider in this way.

The Forward & Backward encodings are defined over the plaintext space which is modulo 2^k in SPU. Thus, the sign flip here should work over mod 2^k.

In more details, (-xvec[i] mod 2^k) mod q = -(xvec[i] mod q) when we view xvec[i] in the centric range [-2^{k-1}, 2^{k-1}) in stead of the unsigned range [0, 2^k)

from spu.

@fionser , is this a bug?
Similar problems appear at template <typename Scalar> void ModulusDownRNS(absl::Span<const uint64_t> src, absl::Span<Scalar> out) const :

          // [0, gamma) -> [-gamma/2, gamma/2]
          if (on_gamma > gamma_div_2) {
            return ((on_t + gamma_.value() - on_gamma) * inv_gamma_mod_t_) &
                   mod_t_mask_;
          } else {
            return ((on_t - on_gamma) * inv_gamma_mod_t_) & mod_t_mask_;
          }

from spu.

More questions:
(2) in packlwes.cc. The function void NegacyclicRightShiftInplace(RLWECt &ct, size_t shift, const seal::SEALContext &context) is just multiplying a plaintext $X^{shift}$. So it can be replaced by seal::Evaluator:: multiply_plain, right?
(3) at line 356 in packlwes_test.cc, the index in xtmp[num_coeffs - 1 - i] = -xvec[i]; is not right. And the minus sign will cause wrong answer, since we want -xvec[i] mod q[mod_idx], while -xvec[i] is computed module $2^{k}$.

from spu.

• Viewing $x \in [0, 2^k)$ as $[-2^{k-1}, 2^{k-1})$ or in $(-2^{k-1}, 2^{k-1}]$ should be all right for `CenteralizeAt.
• Yes, the document is mismatching the code in CenteralizeAt where the code is actually doing $(-2^{k-1}, 2^{k-1}]$
• For the [0, gamma) -> [-gamma/2, gamma/2] since gamma is an odd value.
• NegacyclicRightShiftInplace might be efficient than using multiply_plain. At least, you don't really need the plain polynomial except the non-zero index.
• -xvec[i] mod 2^k is fine, since that is what we what. The mod q part is defered to Line 365 or Line 367

from spu.

(3) xtmp[num_coeffs - 1 - i] should be xtmp[num_coeffs - i] . Note that -xvec[i] mod $2^k$ mod q is different from -xvec[i] mod q. Actually, a possible case is -xvec[i] mod $2^k$ = $2^k$ - xvec[i]. And I do not understand the part $2^k$ mod q.

from spu.