Paper 2020/198

MPSign: A Signature from Small-Secret Middle-Product Learning with Errors

Shi Bai, Dipayan Das, Ryo Hiromasa, Miruna Rosca, Amin Sakzad, Damien Stehlé, Ron Steinfeld, and Zhenfei Zhang

Abstract

We describe a digital signature scheme MPSign, whose security relies on the conjectured hardness of the Polynomial Learning With Errors problem (PLWE) for at least one defining polynomial within an exponential-size family (as a function of the security parameter). The proposed signature scheme follows the Fiat-Shamir framework and can be viewed as the Learning With Errors counterpart of the signature scheme described by Lyubashevsky at Asiacrypt 2016, whose security relies on the conjectured hardness of the Polynomial Short Integer Solution (PSIS) problem for at least one defining polynomial within an exponential-size family. As opposed to the latter, MPSign enjoys a security proof from PLWE that is tight in the quantum-access random oracle model. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in PKC 2020
Keywords
middle-product lwepolynomial lwedigital signatures
Contact author(s)
mirunarosca @ gmail com
damien stehle @ gmail com
ron steinfeld @ monash edu
History
2020-02-18: received
Short URL
https://ia.cr/2020/198
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/198,
      author = {Shi Bai and Dipayan Das and Ryo Hiromasa and Miruna Rosca and Amin Sakzad and Damien Stehlé and Ron Steinfeld and Zhenfei Zhang},
      title = {MPSign: A Signature from Small-Secret Middle-Product Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2020/198},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/198}},
      url = {https://eprint.iacr.org/2020/198}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.