Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems

PASSEncrypt is a lattice-based public key encryption scheme introduced by Hoffstein and Silverman (Des Codes Cryptogr 77(2–3):541–552, 2015). The efficiency and algebraic properties of PASSEncrypt and of the underlying partial Vandermonde knapsack problem (PV - Knap) make them an attractive starting point for building efficient post-quantum cryptographic primitives. Recall that PV - Knap asks to recover a polynomial of small norm from a partial list of its Vandermonde transform. Unfortunately, the security foundations of PV - Knap -based encryption are not well understood, and in particular, no security proof for PASSEncrypt is known. In this work, we make progress in this direction. First, we present a modified version of PASSEncrypt with a security proof based on decision PV - Knap and a leaky variant of it, named the PASS problem. We next study an alternative approach to build encryption based on PV - Knap. To this end, we introduce the partial Vandermonde LWE problem (PV - LWE), which we show is computationally equivalent to PV - Knap. Following Regev’s design for LWE -based encryption, we use PV - LWE to construct an efficient encryption scheme. Its security is based on PV - LWE and a hybrid variant of PV - Knap and Polynomial LWE. Finally, we give a refined analysis of the concrete security of both schemes against best known lattice attacks.