International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Locally Verifiable Signature and Key Aggregation

Authors:
Rishab Goyal , MIT
Vinod Vaikuntanathan , MIT
Download:
Search ePrint
Search Google
Conference: CRYPTO 2022
Abstract: Aggregate signatures (Boneh, Gentry, Lynn, Shacham, Eu- rocrypt 2003) enable compressing a set of N signatures on N different messages into a short aggregate signature. This reduces the space com- plexity 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 sig- nature σ (corresponding to a set 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 M. We demon- strate 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 aggre- gate 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.
BibTeX
@inproceedings{crypto-2022-32243,
  title={Locally Verifiable Signature and Key Aggregation},
  publisher={Springer-Verlag},
  author={Rishab Goyal and Vinod Vaikuntanathan},
  year=2022
}