Paper 2014/334

LCPR: High Performance Compression Algorithm for Lattice-Based Signatures

Rachid El Bansarkhani and Johannes Buchmann


Many lattice-based signature schemes have been proposed in recent years. However, all of them suffer from huge signature sizes as compared to their classical counterparts. We present a novel and generic construction of a lossless compression algorithm for Schnorr-like signatures utilizing publicly accessible randomness. Conceptually, exploiting public randomness in order to reduce the signature size has never been considered in cryptographic applications. We illustrate the applicability of our compression algorithm using the example of a current state-of-the-art signature scheme due to Gentry et al. (GPV scheme) instantiated with the efficient trapdoor construction from Micciancio and Peikert. This scheme benefits from increasing the main security parameter $n$, which is positively correlated with the compression rate measuring the amount of storage savings. For instance, GPV signatures admit improvement factors of approximately $\lg n$ implying compression rates of about $65$\% at a security level of about 100 bits without suffering loss of information or decrease in security, meaning that the original signature can always be recovered from its compressed state. As a further result, we propose a multi-signer compression strategy in case more than one signer agree to share the same source of public randomness. Such a strategy of bundling compressed signatures together to an aggregate has many advantages over the single signer approach.

Available format(s)
Publication info
Preprint. MINOR revision.
Lattice-Based CryptographyLattice-Based SignaturesAggregate SignaturesPublic RandomnessLattice-Based Assumptions
Contact author(s)
elbansarkhani @ cdc informatik tu-darmstadt de
2015-01-13: last of 3 revisions
2014-05-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rachid El Bansarkhani and Johannes Buchmann},
      title = {LCPR: High Performance Compression Algorithm for Lattice-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2014/334},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.