Cryptology ePrint Archive: Report 2018/670

Public Key Compression for Constrained Linear Signature Schemes

Ward Beullens and 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.

Category / Keywords: public-key cryptography / digital signatures, post-quantum, quantum random oracle model, key size reduction

Date: received 10 Jul 2018

Contact author: ward beullens at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20180713:140559 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]