Research proof index

Binding reduces to Module-SIS for any commitment/Module-SIS shortness predicates closed under differences.

Core digit bound. Each base-b digit of zmodDigitDecomposition, viewed as a centered residue, has absolute value at most b - 1 , provided b - 1 ≤ q/2, so the digit (a natural number < b) does not wrap to a negative centered representative.

|R_q^H| ≤ q^k, from ψ : (R_q^H)^{d/k} ↪ R_q injective and |R_q| = q^{2^α}: |R_q^H|^{d/k} ≤ q^{2^α} = (q^k)^{d/k}.

Hachi [NOZ26, §3, Lemma 6]: ‖ψ(a)‖∞ ≤ 2β. If every entry of the vector a : (R_q^H)^{d/k} has centered coefficient ℓ∞-norm at most β (i.e. ‖a‖∞ ≤ β in the mod± q convention of [NOZ26, §2.1]), then the packed ring element ψ(a) ∈ R_q satisfies ‖ψ(a)‖∞ ≤ 2β. The hypotheses are the standing assumptions of [NOZ26, §3]: k = 2^κ divides `d/2...

Main combinatorial bound (at most two contributions per position). For p < d, the p-th coefficient of ψ(a) is ± c₁ ± c₂ where c₁, c₂ are coefficients of the (at most two) entries of a whose index matches p's residue class mod d/2k (j₁ := p mod d/2k from the first half, j₂ := d/2k + p mod d/2k from the second); all other summands...

σ_{-1}(X^e) = -X^{d-e} for 0 < e < d: the conjugate of a sub-d/2 monomial is minus the complementary monomial. The only nonzero coefficient of σ_{-1}(X^e) sits at d - e, with sign -1: from e·conjExp ≡ 2^{α+1} - e (mod 2^{α+1}) we get σ_{-1}(X^e) = X^{d + (d-e)} = -X^{d-e}.