Cryptology ePrint Archive: Report 2014/334

LCPR: High Performance Compression Algorithm for Lattice-Based Signatures and Schnorr-like Constructions

Rachid El Bansarkhani and Johannes Buchmann

Abstract: We present a novel and generic construction of a lossless compression algorithm for Schnorr-like signatures utilizing publicly accessible randomness. This strategy is from a mathematical and algorithmic point of view very interesting, since it is closely related to vector quantization techniques used for audio and video compression. Conceptually, exploiting public randomness in order to reduce the signature size has never been considered in cryptographic applications. This opens new directions for improving existing signature schemes. We illustrate the applicability of our compression algorithm using the examples of current-state-of-the-art signature schemes such as the efficient constructions due to Lyubashevsky et al. and the GPV signature scheme instantiated with the efficient trapdoor construction from Micciancio and Peikert. Both schemes benefit 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$\% for practical parameters without suffering loss of information or decrease in security, meaning that the original signature can always be recovered from its compressed state. Similarly, for signatures generated according to the scheme due to G\"uneysu et al. we achieve compression rates of approximately $60$\% and even $73$\%, when combining with previous compression algorithms. As a further interesting result, we propose a generic unrestricted aggregate signature scheme.

Category / Keywords: Lattice-Based Cryptography, Aggregate Signatures, Schnorr-Signatures, Generic Compression Algorithm, Public Randomness

Date: received 13 May 2014, last revised 15 May 2014

Contact author: elbansarkhani at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20140515:144638 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]