Common Notation

Integer Polynomial LWE

Propose Edit

Updated:

The Integer Polynomial LWE (I-PLWE) problem was introduced by Gu in 2017 [1] as an integer-version of the Polynomial LWE assumption, today often referred to as Ring LWE.

Definition

First, we define the representatives range for \(\ZZ_{f(q)}\). Let \(q > 2\) and \(f \in \ZZ[X]\) monic of degree \(m>0\). Then, define

\[I_{f,q} = \begin{cases} \left(\frac{q}{2}\frac{q^m-1}{q-1} - f(q), \frac{q}{2}\frac{q^m-1}{q-1}\right] &\text{if } q \text{ even and } q\frac{q^m-1}{q-1}\geq f(w) \geq q^m, \\ \left(-\frac{q-2}{2}\frac{q^m-1}{q-1}, f(q)-\frac{q-2}{2}\frac{q^m-1}{q-1}\right] &\text{if } q \text{ even and } q^m > f(q) > (q-2)\frac{q^m-1}{q-1}, \\ \left(-f(q)/2, f(q)/2\right] &\text{otherwise.} \end{cases}\]

Whenever we consider an element \(\bar{a}\) of \(\ZZ_{f(q)}\) and want to choose a representative \(a \in \ZZ\) for it, we will choose it such that \(a \in I_{f,q}\).

I-PLWE\(_{q,f,\sigma,\sigma',t}\)

Let \(q>2\),\(\sigma > \sigma' > 0\),\(f\in \ZZ[X]\) monic of degree \(m>0\), and \(\sigma>0\). Define \(D_{\ZZ_{f(q)},\sigma,q}\) as the distribution obtained by sampling \(E \sample D_{\ZZ^{<m+1}[X],\sigma,q}\), setting \(e = E(q)\) and rejecting if it does not belong to \(I_{f,q}\). Sample \(s \sample D_{\ZZ_{f(q)},\sigma',q}\), \(\vec{a} \sample \ZZ_{f(q)}^t\), and \(e \sample D_{\ZZ_{f(q)},\sigma,q}^\ell\). Given \((\vec{a}, \vec{a} \cdot s + \vec{e}) \in \ZZ_{f(q)}^t \times \ZZ_{f(q)}^t\), an adversary is asked to find the secret \(s\).

Similarly, one can define an integer version of Module-LWE.

Hardness

Gu [1] shows that I-PLWE is asymptotically equivalent to Polynomial LWE. Concrete equivalence results (with polynomial-time reduction algorithms) for the search variant of I-PLWE was provided in [2]. Their results apply to a large class of defining polynomials \(f\).

Constructions built from I-PLWE

  • Public-Key Encryption [1][2]
  • Key Exchange Mechanism [3]
  • Ring-LWE, historically referred to as Polynomial LWE.

References

  • [1]Chunsheng Gu. 2019. Integer Version of Ring-LWE and Its Applications. In Security and Privacy in Social Networks and Big Data - 5th International Symposium, SocialSec 2019, Copenhagen, Denmark, July 14-17, 2019, Revised Selected Papers (Communications in Computer and Information Science), 2019. Springer, 110–122. Retrieved from https://ia.cr/2017/641
  • [2]Julien Devevey, Amin Sakzad, Damien Stehlé, and Ron Steinfeld. 2021. On the Integer Polynomial Learning with Errors Problem. In Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10-13, 2021, Proceedings, Part I (Lecture Notes in Computer Science), 2021. Springer, 184–214. Retrieved from https://ia.cr/2021/277
  • [3]Mike Hamburg. 2019. Post-quantum cryptography proposal: ThreeBears. NIST PQC Round 2, (2019), 4.