Paper 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üneysu 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.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Lattice-Based CryptographyAggregate SignaturesSchnorr-SignaturesGeneric Compression AlgorithmPublic Randomness
- Contact author(s)
- elbansarkhani @ cdc informatik tu-darmstadt de
- History
- 2015-01-13: last of 3 revisions
- 2014-05-15: received
- See all versions
- Short URL
- https://ia.cr/2014/334
- License
-
CC BY