Welcome to the resource topic for 2022/679
Title:
Vandermonde meets Regev: Public Key Encryption Schemes Based on Partial Vandermonde Problems
Authors: Katharina Boudgoust, Amin Sakzad, and Ron Steinfeld
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.
ePrint: https://eprint.iacr.org/2022/679
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .