Paper 2022/179

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 Ω(N). In this work, we introduce the notion of locally verifiable aggregate signatures that enable efficient verification: given a short aggregate signature σ (corresponding to a set of messages), the verifier can check whether a particular message is in the set, in time independent of . Verification does not require knowledge of the entire set . 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 identities can be compressed into a single aggregate key, which can then be used to decrypt ciphertexts sent to any of the identities.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Aggregate SignaturesLocal VerifiabilityRSAPairingBlockchainsRedactableCertificate Transparency
Contact author(s)
goyal @ utexas edu
vinod nathan @ gmail com
History
2022-02-20: received
Short URL
https://ia.cr/2022/179
License
Creative Commons Attribution
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},
      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.