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, Zhenfei Zhang

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

We describe a digital signature scheme, whose security relies on the conjectured hardness of the Polynomial Learning With Errors problem 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 problem for at least one defining polynomial within an exponential-size family. As opposed to the latter, enjoys a security proof from that is tight in the quantum-access random oracle model. The main ingredient is a reduction from for an arbitrary defining polynomial among exponentially many, to a variant of the Middle-Product Learning with Errors problem that allows for secrets that are small compared to the working modulus. We present concrete parameters for 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 (or), we present an efficient key-recovery attack against Lyubashevsky’s scheme (or the inhomogeneous 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.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2020
Subtitle of host publication23rd IACR International Conference on Practice and Theory of Public-Key Cryptography Edinburgh, UK, May 4–7, 2020 Proceedings, Part II
EditorsAggelos Kiayias, Markulf Kohlweiss, Petros Wallden, Vassilis Zikas
Place of PublicationCham Switzerland
PublisherSpringer
Pages66-93
Number of pages28
ISBN (Electronic)9783030453886
ISBN (Print)9783030453879
DOIs
Publication statusPublished - 2020
EventInternational Conference/Workshop on Practice and Theory in Public Key Cryptography 2020 - Online
Duration: 1 Jun 20204 Jun 2020
Conference number: 23rd
https://link.springer.com/book/10.1007/978-3-030-45388-6 (Proceedings)
https://pkc.iacr.org/2020/ (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12111
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference/Workshop on Practice and Theory in Public Key Cryptography 2020
Abbreviated titlePKC 2020
Period1/06/204/06/20
Internet address

Cite this

Bai, S., Das, D., Hiromasa, R., Rosca, M., Sakzad, A., Stehlé, D., Steinfeld, R., & Zhang, Z. (2020). MPSign: a signature from small-secret middle-product learning with errors. In A. Kiayias, M. Kohlweiss, P. Wallden, & V. Zikas (Eds.), Public-Key Cryptography – PKC 2020 : 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography Edinburgh, UK, May 4–7, 2020 Proceedings, Part II (pp. 66-93). (Lecture Notes in Computer Science ; Vol. 12111 ). Springer. https://doi.org/10.1007/978-3-030-45388-6_3