A Concretely Compact Lattice-Based Aggregate Signature Scheme

We present the first aggregate signature (AS) scheme that: (1) its security is based on the standard lattice-based assumptions in the random oracle model, (2) the size of the aggregated signature is logarithmic, (3) it has no one-time restriction, and (4) it can be aggregated non-interactively. In addition, our AS scheme is concretely compact because the size of the aggregated signature required to aggregate 10^6 signatures is only a few hundred kilobytes. This result shows that our scheme is superior to the existing lattice-based schemes in compressing many signatures. To obtain our scheme, we construct a new lattice-based succinct non-interactive argument of knowledge (SNARK) system for batch signature verification of a SNARK-friendly variant of Lyubashefsky's signature scheme.

We present the first aggregate signature (AS) scheme that: (1) its security is based on the standard lattice-based assumptions in the random oracle model, (2) the size of the aggregated signature is logarithmic, (3) it has no one-time restriction, and (4) it can be aggregated non-interactively. In addition, our AS scheme is concretely compact because the size of the aggregated signature required to aggregate 10^6 signatures is only a few hundred kilobytes. This result shows that our scheme is superior to the existing lattice-based schemes in compressing many signatures. To obtain our scheme, we construct a new lattice-based succinct non-interactive argument of knowledge (SNARK) system for batch signature verification of a SNARK-friendly variant of Lyubashefsky's signature scheme.