Common Notation

Partial Vandermonde SIS (PV-SIS)

Propose Edit

Updated:

Partial Vandermonde SIS (PV-SIS) was proposed by Hoffstein, Pipher, Schanck, Silverman, and Whyte in 2014 under the name Vandermonde SIS [1]. The problem is a homogeneous version of the Partial Vandermonde Knapsack problem (also referred to as Partial Fourier Recovery Problem) [1][2][3].

Definition

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

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

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-SIS\(_{n,q,\beta,\nu,t}\)

Sample \(\Omega \sample \mathcal{U}(\mathcal{P}_t)\). Given \(\bar{\mat{V}}_\Omega\), an adversary is asked to find a short non-zero vector \(\vec{a} \in \ZZ_q^n\) s.t.

\[\bar{\mat{V}}_\Omega \cdot \vec{a} = \vec{0} \land 0 < \norm{a}_2 \leq \beta.\]

Variants

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

Sample \(\Omega \sample \mathcal{U}(\mathcal{P}_t)\) and \(\vec{b} \sample \mathcal{R}_q\). Given \(\bar{\mat{V}}_\Omega\), an adversary is asked to find \((\vec{z}_1,\vec{z}_2) \in \mathcal{R}\) s.t.

\[\bar{\mat{V}}_\Omega \cdot \left( \vec{z}_1 + \vec{b} \cdot \vec{z}_2 \right) = \vec{0} \land 0 < \norm{(\vec{z}_1, \vec{z}_2)}_2 \leq \beta,\]

where \(\vec{z}_1 + \vec{b} \cdot \vec{z}_2 = \vec{0} \bmod \mathcal{I}_{\Omega,q}\) with \(\mathcal{I}_{\Omega, q} = \prod_{\omega_j \in \Omega} \langle q, x-\omega_j \rangle\).

Partial-NTT Polynomial-SIS (PNTT-PSIS) is a relaxation of Ring-SIS (known as Polynomial-SIS), which instead of requiring \(\vec{z}_1 + \vec{b} \cdot \vec{z}_2\) to be \(\vec{0}\) in \(\mathcal{R}_q\), it only requires \(t\) out of \(n\) NTT coefficients to be zero. According to Lemma 9 of [3], PNTT-PSIS is hard if PV-SIS and NTRU are hard.

Hardness

Lemma 8 of [3] states that PV-SIS is at least as hard as PV-LWE.

As a specialisation of the Partial Vandermonde Knapsack problem (w.r.t. the Euclidean norm), PV-SIS can at most be as hard as PV-Knapsack. However, 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. Subsequent work [5] provides a key recovery attack, i.e. a polynomial-time algorithm to find \(\vec{a}\), 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-SIS

  • Partial Vandermonde Knapsack (also known as Partial Fourier Recovery Problem) [1][2] is the inhomogeneous version of PV-SIS.
  • Partial Vandermonde LWE is the LWE version of PV-SIS.

References

  • [1]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
  • [2]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
  • [3]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
  • [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