eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2018/670

Public Key Compression for Constrained Linear Signature Schemes

Ward Beullens, Bart Preneel, and Alan Szepieniec


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)
Public-key cryptography
Publication info
digital signaturespost-quantumquantum random oracle modelkey size reduction
Contact author(s)
ward beullens @ esat kuleuven be
2018-07-13: received
Short URL
Creative Commons Attribution


      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.