Paper 2018/670

Public Key Compression for Constrained Linear Signature Schemes

Ward Beullens, Bart Preneel, and Alan Szepieniec

Abstract

We formalize the notion of a constrained linear trapdoor as an abstract strategy for the generation of signature schemes, concrete instantiations of which can be found in MQ-based, code-based, and lattice-based cryptography. Moreover, we revisit and expand on a transformation by Szepieniec et al. to shrink the public key at the cost of a larger signature while reducing their combined size. This transformation can be used in a way that is provably secure in the random oracle model, and in a more aggressive variant whose security remained unproven. In this paper we show that this transformation applies to any constrained linear trapdoor signature scheme, and prove the security of the first mode in the quantum random oracle model. Moreover, we identify a property of constrained linear trapdoors that is sufficient (and necessary) for the more aggressive variant to be secure in the quantum random oracle model. We apply the transformation to an MQ-based scheme, a code-based scheme and a lattice-based scheme targeting 128-bits of post quantum security, and we show that in some cases the combined size of a signature and a public key can be reduced by more than a factor 300.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
digital signaturespost-quantumquantum random oracle modelkey size reduction
Contact author(s)
ward beullens @ esat kuleuven be
History
2018-07-13: received
Short URL
https://ia.cr/2018/670
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/670,
      author = {Ward Beullens and Bart Preneel and Alan Szepieniec},
      title = {Public Key Compression for Constrained Linear Signature Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/670},
      year = {2018},
      url = {https://eprint.iacr.org/2018/670}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.