Multi-Verifier Signatures

Multi-verifier signatures generalize traditional digital signatures to a secret-key setting. Just like digital signatures, these signatures are both transferable and secure under arbitrary (unbounded) adaptive chosen-message attacks. In contrast to digital signature schemes, however, the authors exhibit practical constructions of multi-verifier signature schemes that are provably secure and are based only on pseudorandom functions in the plain model without any random oracles. Digital signatures are relatively expensive to generate. Moreover, practical digital signature schemes rely on either strong number-theoretic assumptions or are proven secure only in the random oracle model.