Practical signatures from the partial fourier recovery problem revisited: A provably-secure and gaussian-distributed construction

Abstract

© Springer International Publishing AG, part of Springer Nature 2018. In this paper, we present a new lattice-based signature scheme, PASSG, based on signatures from the partial Fourier recovery problem PASSRS introduced by Hoffstein et al. in 2014. Same as PASSRS, security of our construction relies on the average-case hardness of a special kind of Short Integer Solution (SIS) problem and the hardness of partial Fourier recovery problem. PASSG improves PASSRS in two aspects. Firstly, unlike PASSRS, PASSG comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2008 to reduce the signature size and improve the efficiency. More concretely, signatures of PASSG are Gaussian-distributed and is more space efficient. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011.