### Locally Verifiable Signature and Key Aggregation

Rishab Goyal and Vinod Vaikuntanathan

##### Abstract

Aggregate signatures (Boneh, Gentry, Lynn, Shacham, Eurocrypt 2003) enable compressing a set of $N$ signatures on $N$ different messages into a short aggregate signature. This reduces the space complexity of storing the signatures from linear in $N$ to a fixed constant (that depends only on the security parameter). However, verifying the aggregate signature requires access to all $N$ messages, resulting in the complexity of verification being at least $\Omega(N)$. In this work, we introduce the notion of locally verifiable aggregate signatures that enable efficient verification: given a short aggregate signature $\sigma$ (corresponding to a set $\mathcal{M}$ of $N$ messages), the verifier can check whether a particular message $m$ is in the set, in time independent of $N$. Verification does not require knowledge of the entire set $\mathcal{M}$. We demonstrate many natural applications of locally verifiable aggregate signature schemes: in the context of certificate transparency logs; in blockchains; and for redacting signatures, even when all the original signatures are produced by a single user. We provide two constructions of single-signer locally verifiable aggregate signatures, the first based on the RSA assumption and the second on the bilinear Diffie-Hellman inversion assumption, both in the random oracle model. As an additional contribution, we introduce the notion of compressing cryptographic keys in identity-based encryption (IBE) schemes, show applications of this notion, and construct an IBE scheme where the secret keys for $N$ identities can be compressed into a single aggregate key, which can then be used to decrypt ciphertexts sent to any of the $N$ identities.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Aggregate SignaturesLocal VerifiabilityRSAPairingBlockchainsRedactableCertificate Transparency
Contact author(s)
goyal @ utexas edu
vinod nathan @ gmail com
History
Short URL
https://ia.cr/2022/179

CC BY

BibTeX

@misc{cryptoeprint:2022/179,
author = {Rishab Goyal and Vinod Vaikuntanathan},
title = {Locally Verifiable Signature and Key Aggregation},
howpublished = {Cryptology ePrint Archive, Paper 2022/179},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/179}},
url = {https://eprint.iacr.org/2022/179}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.