Paper 2022/679
Vandermonde meets Regev: Public Key Encryption Schemes Based on Partial Vandermonde Problems
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)
- 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
-
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} }