Proactive obfuscation is a new method for creating server replicas that are likely to have fewer shared vulnerabilities. It employs semantics-preserving code transformations to generate diverse executables from a single codebase and periodically restarts servers with these fresh images. Periodic restarts help bound the number of compromised replicas that a service ever concurrently runs, and therefore proactive obfuscation makes an adversary’s job more difficult. Proactive obfuscation was used in implementing two prototypes: a distributed firewall based on state-machine replication and a distributed storage service based on quorum systems. Costs intrinsic to supporting proactive obfuscation were quantified by measuring the performance of these prototypes. Authentication is a large cost in proactive obfuscation. And some protocols used in the prototypes require transferable signed messages (for example, using digital signatures), which can be slow to compute. To reduce authentication costs, we introduce multi-verifier signatures, a new family of signature schemes that generalizes traditional digital signatures to a secret-key setting. Some of our multi-verifier signature schemes are faster to compute than digital signatures. Moreover, just like digital signatures, these signatures are both transferable and secure under arbitrary (unbounded) adaptive chosen-message attacks. Practical constructions of digital signature schemes rely on either strong number-theoretic assumptions or are proven secure only in the random oracle model. In contrast, we exhibit practical constructions of multi-verifier signature schemes that are provably secure in the plain model assuming the existence of pseudorandom functions and without assuming access to random oracles.