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 CryptographyPublic Key EncryptionPartial 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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2022/679}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.