There's nothing incorrect, lattice-based cryptography has a chance of decryption failure and this chance increases as degree and noise grow relative to the modulus. I think that it's quite instructive to look at the actual numbers here in order to get a feel for some of the uncertainty that is inherent in lattice-based cryptography. If we expand your sage code to generate the two cases side by side
N = 11
p = 3
q1 = 31
q2 = 29
R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q1.<x> = PolynomialRing(Zmod(q1))
QQ1 = Q1.quotient(x^N - 1)
Q2.<x> = PolynomialRing(Zmod(q2))
QQ2 = Q2.quotient(x^N - 1)
f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])
fp = PP(f) ^ -1
fq1 = QQ1(f) ^ -1
fq2 = QQ2(f) ^ -1
assert fp * f == 1
assert fq1 * f == 1
assert fq2 * f == 1
h1 = QQ1( (p * fq1) * g )
h2 = QQ2( (p * fq2) * g )
m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1])
r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0])
e1 = QQ1(r * h1 + m)
e2 = QQ2(r * h2 + m)
a1 = QQ1(f) * e1
al1 = ZZ['x']([coeff.lift_centered() for coeff in a1.lift()])
a2 = QQ2(f) * e2
al2 = ZZ['x']([coeff.lift_centered() for coeff in a2.lift()])
b1 = PP(al1)
b2 = PP(al2)
c1 = fp * b1
c2 = fp * b2
note that I've also used separate variables for $a(x)\mod q$ and its lift to $\mathbb Z[x]$. If we compare a1
and a2
we see
sage: a1
27*xbar^10 + 3*xbar^9 + 30*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 20*xbar^3 + 27*xbar^2 + 24*xbar
sage: a2
25*xbar^10 + 3*xbar^9 + 28*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 18*xbar^3 + 25*xbar^2 + 22*xbar
these are reductions of the same polynomial $$a(x)=r(x)g(x)p+f(x)m(x)$$
$$=-4x^{10}+3x^9-x^8+4x^7+15x^6+10x^5+4x^4-11x^3-4x^2-7x$$
over the integers and for decryption we would like to lift each of the reductions of this polynomial to the original integer version. The coefficients of the integer polynomial are sums of products of small integers and so we hope that they do not grow to large. In particular, if all of the coefficients lie in the range $(-q/2,q/2)$ then the reduction can be interpreted as residues in this interval and lifted back to the original polynomial without error. However, if we look at the coefficient of $x^6$ t is 15. Although this lies in the interval $(-31/2,31/2)$, it does not lie in the interval $(-29/2,29/2)$ so that our reduction is not trivial and our lift does not work. Specifically, if we look at al1
and al2
we have
sage: al1
-4*x^10 + 3*x^9 - x^8 + 4*x^7 + 15*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x
sage: al2
-4*x^10 + 3*x^9 - x^8 + 4*x^7 - 14*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x
and in the second case we have recovered the wrong polynomial over the integers causing future steps to fail. The larger $q$ is, the less likely it is for coefficients of the integers polynomial to fall outside of the recoverable range and so decryption failures reduce. However, increasing $q$ can make life easier for the attacker and a trade-off must be reached.
In the case of decryption failure, it is possible to correct such errors by scanning the lifted polynomial for coefficients that are close to $q/2$ and then seeing what happens if we adjust these suspect coefficents by $\pm q$. However, this leads to non-constant decryption time and creates all manner of sidechannel, spoofing and fault injection vulnerabilities.