You are looking at a specific version 20140515:144638 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.