[Bug]: The correctness of dj

[maths644311798]

Issue Type

Usability

HEU Version

newest

OS Platform and Distribution

Ubuntu 22.04

Python Version

3.10

Compiler Version

gcc 14.2

Current Behavior?

In heu/library/algorithms/dj/README.md,

Decryption(sk, c):

- For each $j=1$ to $s$, do the following:
    - Compute $l_j = L_j(c^\lambda \bmod n^{j+1})$, where $L_j(z) = \frac{z-1}{n}\bmod n^j$
    - Compute $i_j=l_j-\sum_{k=2}^j{i_{j-1}\choose k}n^{k-1} \bmod n^k$

In this process, the module n^k is not correct. It should be n^j. Then in secret_key.cc, the sentence

MPInt::MulMod(tmp.P, ind.P - MPInt{i - 1}, lut_->pq_pow[j - i + 1].P,
                    &tmp.P);
      MPInt::MulMod(tmp.Q, ind.Q - MPInt{i - 1}, lut_->pq_pow[j - i + 1].Q,
                    &tmp.Q);

seems wrong. The module lut_->pq_pow[j - i + 1].P is strange. I think lut_->pq_pow[j].P is a correct one.

Standalone code to reproduce the issue

MPInt SecretKey::Decrypt(const MPInt &ct) const {
  MPInt2 z, ls;
  // compute z = c^d mod n^(s+1)
  const auto &[ps1, qs1] = lut_->pq_pow[s_ + 1];
  z = {(ct % ps1).PowMod(lambda_, ps1), (ct % qs1).PowMod(lambda_, qs1)};
  //  compute ls = L(z) mod n^s
  const auto &[ps, qs] = lut_->pq_pow[s_];
  ls = {inv_pq_.P.MulMod((z.P - MPInt::_1_) / n_.P, ps),
        inv_pq_.Q.MulMod((z.Q - MPInt::_1_) / n_.Q, qs)};

  MPInt2 ind{ls.P % lut_->pq_pow[1].P, ls.Q % lut_->pq_pow[1].Q};
  MPInt2 l, tmp;
  for (auto j = 2u; j <= s_; ++j) {
    // compute l = L(c^d mod n^{j+1}) = ls mod n^j
    l = {ls.P % lut_->pq_pow[j].P, ls.Q % lut_->pq_pow[j].Q};
    // compute ind mod n^j
    tmp = ind;
    for (auto i = 2u; i <= j; ++i) {
      MPInt::MulMod(tmp.P, ind.P - MPInt{i - 1}, lut_->pq_pow[j - i + 1].P,
                    &tmp.P);
      MPInt::MulMod(tmp.Q, ind.Q - MPInt{i - 1}, lut_->pq_pow[j - i + 1].Q,
                    &tmp.Q);
      l.P -= tmp.P.MulMod(lut_->precomp[j][i].P, lut_->pq_pow[j].P);
      l.Q -= tmp.Q.MulMod(lut_->precomp[j][i].Q, lut_->pq_pow[j].Q);
    }
    ind = {l.P % lut_->pq_pow[j].P, l.Q % lut_->pq_pow[j].Q};
  }
  auto m_lambda = (ind.P + (ind.Q - ind.P) * pp_) % pmod_;
  return m_lambda.MulMod(mu_, pmod_);
}

Relevant log output

No response

[shaojian-ant]

@zhangwfjh @xfap Could you please help with this issue? Thanks!

[maths644311798]

For the problem in secret_key.cc, I figure out the reason: the precomputed lut_->precomp[j][i] has a factor $n^{i-1}$, so tmp.P mod $n^{j-i+1}$ is enough.