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.
@article{56,
title = {Security of signature schemes in the presence of key-dependent messages},
journal = {Tatra Mountains Mathematical Publications},
volume = {49},
year = {2011},
doi = {10.2478/tatra.v47i0.56},
language = {EN},
url = {http://dml.mathdoc.fr/item/56}
}
González Muñiz, Madeline; Steinwandt, Rainer. Security of signature schemes in the presence of key-dependent messages. Tatra Mountains Mathematical Publications, Tome 49 (2011) . doi : 10.2478/tatra.v47i0.56. http://gdmltest.u-ga.fr/item/56/