Security of signature schemes in the presence of key-dependent messages

Abstract

In recent years, quite some progress has been made in understanding the security of encryption schemes in the presence of keydependent 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—even in the random oracle model. After discussing the connection beween 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.