Paper 2022/679

Vandermonde meets Regev: Public Key Encryption Schemes Based on Partial Vandermonde Problems

Katharina Boudgoust, Aarhus University
Amin Sakzad, Monash University
Ron Steinfeld, Monash University

PASS Encrypt is a lattice-based public key encryption scheme introduced by Hoffstein and Silverman in 2015. The efficiency and algebraic properties of PASS Encrypt 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 PASS Encrypt is known. In this work, we make progress in this direction. First, we present a modified version of PASS Encrypt 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.

Available format(s)
Public-key cryptography
Publication info
Lattice-Based Cryptography Public Key Encryption Partial Vandermonde Problem
Contact author(s)
katharina boudgoust @ cs au dk
amin sakzad @ monash edu
ron steinfeld @ monash edu
2022-05-31: approved
2022-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Katharina Boudgoust and Amin Sakzad and Ron Steinfeld},
      title = {Vandermonde meets Regev: Public Key Encryption Schemes Based on Partial Vandermonde Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/679},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.