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

Katharina Boudgoust; Amin Sakzad; Ron Steinfeld

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

Abstract

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.

Note: Update June 2023: publication venue added

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Designs, Codes and Cryptography 2022
DOI: 10.1007/s10623-022-01083-7
Keywords: 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
History: 2023-06-15: revised; 2022-05-30: received; See all versions
Short URL: https://ia.cr/2022/679
License: CC BY

BibTeX

@misc{cryptoeprint:2022/679,
      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},
      doi = {10.1007/s10623-022-01083-7},
      note = {\url{https://eprint.iacr.org/2022/679}},
      url = {https://eprint.iacr.org/2022/679}
}