Common Notation

Partial Vandermonde LWE (PV-LWE)

Propose Edit

Updated:

Partial Vandermonde LWE (PV-LWE) was proposed by Boudgoust, Sakzad, and Steinfeld in 2022 [1] as an LWE alternative to the Partial Vandermonde Knapsack problem (also referred to as Partial Fourier Recovery Problem) [2][3].

Definition

Before we can define PV-LWE, we need to define some preliminaries.

Partial Vandermonde Transform\(_{\nu,n,q}\)

Let \(\set{\omega_j}_{j \in [n]}\) be the set of primitive \(\nu\)-th roots of unity in \(\ZZ_q\). We divide the set \(\set{\omega_j}_{j \in [n]}\) into two disjoint subsets \(\Omega\) and \(\Omega^c\) of size \(\abs{\Omega} = t\) and \(\abs{\Omega^c} = n - t\). The partial Vandermonde transform matrix \(\bar{\mat{V}}_\Omega \in \ZZ_q^{t \times n}\) and its complement \(\bar{\mat{V}}_{\Omega^c} \in \ZZ_q^{(n-t) \times n}\) are given by

\[\bar{\mat{V}}_\Omega = \begin{bmatrix} 1 &\omega_{i_1} &\dots &\omega_{i_1}^{n-1} \\ \vdots &\vdots & &\vdots \\ 1 &\omega_{i_t} &\dots &\omega_{i_t}^{n-1} \\ \end{bmatrix} \text{ and } \bar{\mat{V}}_{\Omega^c} = \begin{bmatrix} 1 &\omega_{i_{t+1}} &\dots &\omega_{i_{t+1}}^{n-1} \\ \vdots &\vdots & &\vdots \\ 1 &\omega_{i_n} &\dots &\omega_{i_n}^{n-1} \\ \end{bmatrix},\]

where \(\omega_{i_j} \in \Omega\) for \(j \in [t]\) and \(\omega_{i_{t+k}} \in \Omega^c\) for \(k \in [n-t]\).

Define the set \(\mathcal{P}_t := \set{\Omega \subset \set{\omega_j}_{j \in [n]} : \abs{\Omega} = t}\) of all subsets of primitive \(\nu\)-th roots of unity in \(\ZZ_q\) of size \(t\).

PV-LWE\(_{n,q,\beta,\nu,t,\chi}\)

Let \(\chi\) be a distribution over \(\ZZ^n\). Sample \(\Omega \sample \mathcal{U}(\mathcal{P}_t)\), \(\vec{s} \sample \ZZ_q^t\), \(\vec{e} \sample \chi\), and \(\vec{u} \sample \ZZ_q^n\). An adversary is asked to distinguish between the distribution

\[\left( \bar{\mat{V}}_\Omega, \bar{\mat{V}}_\Omega^T \cdot \vec{s} + \vec{e} \right) \text{ and } \left( \bar{\mat{V}}_\Omega, \vec{u} \right).\]

Variants

PNTT-PLWE\(_{n,q,\beta,\nu,t,\chi}\)

Let \(\chi\) denote a distribution over \(\RR\). Sample \(\Omega \sample \mathcal{U}(\mathcal{P}_t)\), \(\vec{s} \sample \ZZ_q^t\), \(\vec{b} \sample \mathcal{R}_q\), \(\vec{e}_1, \vec{e}_2 \sample \chi^n\), and \(\vec{y}_1, \vec{y}_2 \sample \mathcal{R}_q\). An adverary is asked to distinguish between the distribution

\[\left( \bar{\mat{V}}_\Omega, \vec{b}, \bar{\mat{V}}_\Omega^T \cdot \vec{s} + \vec{e}_1, \mathsf{rot}(\vec{b}) \cdot \bar{\mat{V}}_\Omega^T \cdot \vec{s} + \vec{e}_2 \right) \text{ and } \left( \bar{\mat{V}}_\Omega, \vec{b}, \vec{y}_1, \vec{y}_2 \right).\]

Partial-NTT Polynomial-LWE (PNTT-PLWE) is a relaxed version of Ring-LWE (referred to as Polynomial LWE in the corresponding paper), which is dual to PNTT-PSIS. Moreover, the search version of PNTT-PLWE is at least as hard as PNTT-PSIS according to Lemma 10 of [1].

Hybrid-PV-P\(_{n,q,\beta,\nu,t,\chi_r,\chi_e}\)

Let \(n\) be a power of two and \(q\) be a prime s.t. \(q = 1 \bmod 2n\), defining \(\mathcal{R}_q := \ZZ_q[X] / (X^n + 1)\). Let \(\chi_r\), \(\chi_e\) be distributions over \(\ZZ\). Sample \(\Omega \sample \mathcal{U}(\mathcal{P}_t)\), \(\vec{b} \sample \mathcal{R}_q\), \(\vec{r} \sample \chi_r^n\), \(\vec{e} \sample \chi_e^n\), \(\vec{u} \sample \ZZ_q^t\), and \(\vec{v} \sample \mathcal{R}_q\). Define \(\tilde{\vec{r}} = (r_0, -r_{n-1}, \dots, -r_1)^T\). An adversary is asked to distinguish between the distribution

\[\left( \bar{\mat{V}}_\Omega, \vec{b}, \bar{\mat{V}}_\Omega \cdot \vec{r}, \vec{b} \cdot \tilde{\vec{r}} + \vec{e} \right) \text{ and } \left( \bar{\mat{V}}_\Omega, \vec{b}, \vec{u}, \vec{v} \right).\]

Hybrid-PV-P is a combination of Ring-LWE and PV-LWE, where the underlying secrets of both instances are related. According to Lemma 11 in [1], Hybrid-PV-P is at least as hard as PNTT-PLWE.

Hardness

Boudgoust et al. show that PV-LWE is equivalent to the decision version of PV-Knapsack in Lemma 6 and 7 of [1]. In subsequent work, Boudgoust, Gachon, and Pellet-Mary [4] present an efficient distinguisher for some proposed sets of parameters and a polynomial-time distinguisher for the decisional PV-Knapsack problem, which works for random instances of \(\Omega\) with non-negligible probability. Further, they reduce the bit-security of parameter sets drastically. Further, Das and Joux [5] provide a key recovery attack for a non-negligible (but efficiently identifiable) number of weak keys. These attacks are devestating in the case of adversarially chosen \(\Omega\) and therefore, choosing the set \(\Omega\) at random is crucial.

Constructions built from PV-LWE

  • Signatures [2][3]
  • Aggregate Signature [6]
  • Public-Key Encryption [1]
  • Partial Vandermonde Knapsack (also known as Partial Fourier Recovery Problem) [2][3] is equivalent to PV-LWE.
  • Partial Vandermonde SIS is the SIS version of PV-LWE.

References

  • [1]Katharina Boudgoust, Amin Sakzad, and Ron Steinfeld. 2022. Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems. Des. Codes Cryptogr. 90, 8 (2022), 1899–1936. Retrieved from https://ia.cr/2022/679
  • [2]Jeffrey Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, and William Whyte. 2014. Practical Signatures from the Partial Fourier Recovery Problem. In Applied Cryptography and Network Security - 12th International Conference, ACNS 2014, Lausanne, Switzerland, June 10-13, 2014. Proceedings (Lecture Notes in Computer Science), 2014. Springer, 476–493. Retrieved from https://ia.cr/2013/757
  • [3]Xingye Lu, Zhenfei Zhang, and Man Ho Au. 2018. Practical Signatures from the Partial Fourier Recovery Problem Revisited: A Provably-Secure and Gaussian-Distributed Construction. In Information Security and Privacy - 23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, July 11-13, 2018, Proceedings (Lecture Notes in Computer Science), 2018. Springer, 813–820. https://doi.org/10.1007/978-3-319-93638-3_50
  • [4]Katharina Boudgoust, Erell Gachon, and Alice Pellet-Mary. 2022. Some Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 480–509. Retrieved from https://ia.cr/2022/709
  • [5]Dipayan Das and Antoine Joux. 2024. Key Recovery Attack on the Partial Vandermonde Knapsack Problem. 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, 205–225. Retrieved from https://ia.cr/2024/366
  • [6]Yarkin Doröz, Jeffrey Hoffstein, Joseph H. Silverman, and Berk Sunar. 2020. MMSAT: A Scheme for Multimessage Multiuser Signature Aggregation. IACR Cryptol. ePrint Arch. 2020, (2020), 520. Retrieved from https://ia.cr/2020/520