The main ingredient is a reduction from PLWE for an arbitrary defining polynomial among exponentially many, to a variant of the Middle-Product Learning with Errors problem (MPLWE) that allows for secrets that are small compared to the working modulus. We present concrete parameters for MPSign using such small secrets, and show that they lead to significant savings in signature length over Lyubashevsky's Asiacrypt 2016 scheme (which uses larger secrets) at typical security levels. As an additional small contribution, and in contrast to MPSign (or MPLWE), we present an efficient key-recovery attack against Lyubashevsky's scheme (or the inhomogeneous PSIS problem), when it is used with sufficiently small secrets, showing the necessity of a lower bound on secret size for the security of that scheme.
Category / Keywords: cryptographic protocols / middle-product lwe, polynomial lwe, digital signatures Original Publication (in the same form): IACR-PKC-2020 Date: received 17 Feb 2020 Contact author: mirunarosca at gmail com, damien stehle at gmail com, ron steinfeld at monash edu Available format(s): PDF | BibTeX Citation Version: 20200218:091121 (All versions of this report) Short URL: ia.cr/2020/198