### 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.

Available format(s)
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
Short URL
https://ia.cr/2018/670

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},
note = {\url{https://eprint.iacr.org/2018/670}},
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.