International Association
for Cryptologic Research

Given an *arbitrary* one-way function F, is it possible to design a signature scheme where the secret key is an input x to F and the public key is y = F(x)? We show that signatures that are \"key-versatile\" in this sense, while also meeting stronger-than-usual security conditions we define, enable us to add signature-based integrity that is \"for-free\" in terms of key material, meaning we can sign with keys already in use for another purpose without impacting the security of the original purpose or in turn being impacted by it. We show applications across diverse areas including (1) security against related-key attack (RKA) (2) security for key-dependent messages (KDM), and (3) joint encryption and signing. We show how to build key versatile signature schemes and then obtain new results in all these application domains in a modular way.