Paper 2017/327

MQ Signatures for PKI

Alan Szepieniec, Ward Beullens, and Bart Preneel

Abstract

It is well known that multivariate quadratic (MQ) digital signature schemes have small signatures but huge public keys. However, in some settings, such as public key infrastructure (PKI), both variables are important. This paper explains how to transform any MQ signature scheme into one with a much smaller public key at the cost of a larger signature. The transformation aims to reduce the combined size of the public key and signature and this metric is improved significantly. The security of our transformation reduces to that of the underlying MQ signature scheme in the random oracle model. It is possible to decrease signature sizes even further but then its security is related to the conjectured hardness of a new problem, the Approximate MQ Problem (AMQ).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCRYPTO 2017
Keywords
multivariate quadraticpublic key infrastructuresignaturerandom oraclepost-quantumhard problem
Contact author(s)
alan szepieniec @ esat kuleuven be
History
2017-04-17: received
Short URL
https://ia.cr/2017/327
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/327,
      author = {Alan Szepieniec and Ward Beullens and Bart Preneel},
      title = {MQ Signatures for PKI},
      howpublished = {Cryptology ePrint Archive, Paper 2017/327},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/327}},
      url = {https://eprint.iacr.org/2017/327}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.