Learning with Alternating Moduli (LwAM) implied

Propose Edit

Updated:

The Learning with Alternating Moduli (LwAM) problem was introduced by Chen, Ji, and Li in 2025 [1]. It formalises an assumption with similarity to LWE and Learning with Rounding that was previously utilised in (oblivious) pseudo-random functions [2][3].

Definition

Search LwAM\(_{n,m,q_0,q_1}\)

_Let \(q_0 > q_1 \geq 2\) and \(\mathsf{gcd}(q_0,q_1) = 1\). Let \(\vec{s} \in \ZZ_{q_0}^n\) and \(\mat{A} \sample \ZZ_{q_0}^{m \times n}\). Given \(\mat{A}\) and \((\mat{A} \cdot \vec{s} \bmod q_0) \bmod q_1\), an adversary is asked to find the secret vector \(\vec{s}\).

Decisional LwAM\(_{n,m,q_0,q_1}\)

Let \(q_0 > q_1 \geq 2\) and \(\mathsf{gcd}(q_0,q_1) = 1\). Let \(\vec{s} \in \ZZ_{q_0}^n\) and \(\mat{A} \sample \ZZ_{q_0}^{m \times n}\). An adversary is asked to distinguish between the distributions

\[\left(\mat{A}, (\mat{A} \cdot \vec{s} \bmod q_0) \bmod q_1 \right) \text{ and } \mathcal{U}\left( \ZZ_{q_0}^{n \times m} \right) \times \left( \mathcal{U}\left(\ZZ_{q_0}^m \right) \bmod q_1 \right).\]

Hardness

Chen, Ji, and Li [1] provide provable results as well as cryptanalytic results for LwAM assumptions. For LAM over constant moduli, they provide polynomial-time attacks on LwAM with constant prime-power moduli and certain non-prime-power moduli and evidence of the sub-exponential hardness of LAM with other moduli by analyzing the effect of typical attacks.

For “certain large” moduli, they provide the following reductions from LWE:

Theorem 22 of [1] states that Search LwAM\(_{n,m,q_0,q_1}\) is at least as hard as Search LWE\(_{n,m,q_0,D_B}\) if \(q_0 > 2Bmq_1\) if \(D_B\) is a \(B\)-bounded and balanced distribution for an arbitrary distribution of secret vector \(\vec{s}\) over \(\ZZ_{q_0}^n\).

For \(q_0 \in \poly{n}\) and uniform choice of \(\vec{s} \sample \ZZ_{q_0}^n\), Theorem 23 of [1] establishes that decisional LwAM\(_{n,m,q_0,q_1}\) is at least as hard as decisional LWE\(_{n/\log q_0 - c_0 \log n,m,q_0,D_\alpha}\) for \(c_0,c_1>0\) if \(m > 2n\), \(2\alpha\sqrt{n}mq_1 < q_0 < \poly{n}\), \(\alpha \geq \sqrt{c_1 \log n}\), and \(D_\alpha\) denotes the discrete Gaussian distribution. In Theorem 24, they lift the constraint to sample \(\vec{s}\) uniformly but require \(q_0 / (2Bmq_1)\) to be super-polynomial in \(n\).

Another Search LwAM to Search LWE reduction is given in Theorem 29 of [1] for more specific parameter sets. Finally, their Theorem 17 provides a search to decision reduction for LwAM with binary secrets. For further details, we refer to Section 3 of [1].

Constructions built from LwAM

To avoid confusion, we only list constructions built from the formalised LwAM assumption.

  • Weak pseudo-random functions [1]

References

  • [1]Yilei Chen, Liheng Ji, and Wenjie Li. 2025. Learning with Alternating Moduli, Arora-Ge over Composite Moduli, and Weak PRFs. IACR Cryptol. ePrint Arch. 2025, (2025), 968. Retrieved from https://ia.cr/2025/968
  • [2]Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. 2018. Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications. In Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II (Lecture Notes in Computer Science), 2018. Springer, 699–729. Retrieved from https://ia.cr/2018/1218
  • [3]Martin R. Albrecht, Alex Davidson, Amit Deo, and Daniel Gardham. 2024. Crypto Dark Matter on the Torus - Oblivious PRFs from Shallow PRFs and TFHE. In Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part VI (Lecture Notes in Computer Science), 2024. Springer, 447–476. Retrieved from https://ia.cr/2023/232