SECURITY OF SIGNATURE SCHEMES IN THE PRESENCE OF KEY-DEPENDENT MESSAGES

In recent years, quite some progress has been made in understanding the security of encryption schemes in the presence of key-dependent plaintexts. Here, we motivate and explore the security of a setting, where an adversary against a signature scheme can access signatures on key-dependent messages. We propose a way to formalize the security of signature schemes in the presence of key-dependent signatures (KDS). It turns out that the situation is quite different from key-dependent encryption: already to achieve KDS-security under non-adaptive chosen message attacks, the use of a stateful signing algorithm is inevitable-oven in the random oracle model. After discussing the connection between key-dependent signing and forward security, we present a compiler to lift any EUF-CMA secure one-time signature scheme to a forward secure signature scheme offering KDS-CMA security.